View Issue Details

IDProjectCategoryView StatusLast Update
0038956FPCCompilerpublic2021-06-05 23:31
ReporterJ. Gareth Moreton Assigned To 
PrioritynormalSeverityminorReproducibilityN/A
Status newResolutionopen 
PlatformCross-platformOSDebian GNU/LInux (Raspberry Pi) 
Product Version3.3.1 
Summary0038956: [Patch / Refactor] Register tracking class - minor overhaul
DescriptionThis patch redesigns some parts of TUsedRegs to make it more self-contained and removes some quirky behaviour where external methods accessed private fields. This also permits better extension of the class in the future. It also speeds up the use of TmpUsedRegs by removing the need to parse through a group of tai objects for every register type.
Steps To ReproduceApply patch and confirm correct compilation without any changes to generated code.
Additional InformationTimings on arm-linux (I can't test x86_64-win64 currently) suggest that the compiler runs very slightly faster, but it's not conclusive (pp3 stage of "make cycle" with -vs option):

Trunk

[29.691] 399115 lines compiled, 29.7 sec, 3914432 bytes code, 1122404 bytes data
[29.215] 399115 lines compiled, 29.2 sec, 3914432 bytes code, 1122404 bytes data
[29.492] 399115 lines compiled, 29.5 sec, 3914432 bytes code, 1122404 bytes data

Refactor

[29.152] 399138 lines compiled, 29.2 sec, 3914528 bytes code, 1122420 bytes data
[29.230] 399138 lines compiled, 29.2 sec, 3914528 bytes code, 1122420 bytes data
[29.164] 399138 lines compiled, 29.2 sec, 3914528 bytes code, 1122420 bytes data
Tagscompiler, patch, refactor
Fixed in Revision
FPCOldBugId
FPCTarget-
Attached Files

Activities

Florian

2021-06-02 18:06

administrator   ~0131128

Any reason why the constructors are virtual now?

J. Gareth Moreton

2021-06-02 18:24

developer   ~0131129

Last edited: 2021-06-02 18:26

View 2 revisions

The main reason is for future development. I started designing a descendent class that could handle virtual registers (using a dynamic array most likely), since that was the main roadblock with running parts of the peephole optimizer with virtual registers. And then it can switch back to the regular TUsedRegs for speed reasons once all the registers are real (parts of Pass 2 on x86, like the CMOVcc optimisations, can't be done on virtual registers).

I started work on this side of things when i noticed a number of routines could have push/pop pairs removed because my other optimisations have managed to completely remove a temporary register (the one pushed and popped from the stack), but I was unable to do it cleanly in post-peephole (I got something working, but it felt clunky and there were some test failures that I couldn't narrow down), so I figured working out how to optimise with virtual registers (something I had already been planning) would be far more efficient and handle edge cases better.

Long story short, the virtual keywords are there for a future extension (as is the virtual keyword on "SetUsed" that could otherwise be inlined since it generally collapses into a single statement). But for now they can be removed if you feel better about it.

Sven Barth

2021-06-03 10:09

manager   ~0131135

But Florian's question is whether there is really a need for virtual constructors. Those are only needed if a class is created using a class variable (like the various, global c* variables inside the compiler that are used for nodes, defs and symbols). If you simply want to do a TVirtualUsedRegs.Create then you don't need virtual constructors.

Also accessing private fields from another class inside the same unit is not considered quirky behavior per se, because that's a well defined behavior of the Object Pascal language and is this way, because types inside the same unit can be safely considered as tightly coupled. I agree though that it might hinder extension, thus a class that wants to allow for extension should provide suitable methods and code in the same unit should make use of these (like your patch does).

J. Gareth Moreton

2021-06-03 15:46

developer   ~0131139

Last edited: 2021-06-03 15:57

View 3 revisions

To answer, there isn't a need for virtual constructors right now. I suppose I can add the directive when I need to. TVirtualUsedRegs.Create would need to initialise the dynamic array for tracking the virtual registers. I'm maybe thinking too many steps ahead.

True, accessing private members in the same unit is well-defined, but is personally something I try to avoid, treating it like 'strict private/protected' instead. That and I'm thinking about extension in mind.

As it currently stands though, the methods don't need to be virtual to work. Do you want me to resubmit the patch with the directive removed?

Sven Barth

2021-06-04 08:31

manager   ~0131145

Last edited: 2021-06-04 08:32

View 2 revisions

TVirtualUsedRegs.Create can do its own initialization without any problems no matter if its virtual or not.

The question is whether you want to instantiate as follows as only then a virtual constructor is necessary:

type
  TUsedRegsClass = class of TUsedRegs;
var
  c: TUsedRegsClass;
  u: TUsedRegs;
begin
  c := TVirtualUsedRegs;
  u := c.Create;  // <- if the constructor is virtual then TVirtualUsedRegs.Create will be called
                  // without virtual TUsedRegs.Create will be called

  // otherwise

  u := TVirtualUsedRegs.Create; // <- this will always be TVirtualUsedRegs.Create
end.


I'll leave it up to Florian whether he wants a new patch or removes the directive himself.

J. Gareth Moreton

2021-06-04 13:37

developer   ~0131149

Last edited: 2021-06-04 13:39

View 2 revisions

Ah I see your point now. Guess it was just habit and convention to have a virtual constructor since I was changing its behaviour in the descendant class.

The other methods, like "SetUsed", will have to be virtual methods because TVIrtualUsedRegs has special handling for if the input register is not a real one (it still has to support real registers because of actual/formal parameters and opcodes like MUL, DIV and SHL on x86 that require specific registers).

I admit I've been slightly careless in interchanging "virtual" and "imaginary" when it comes to the registers as well.

J. Gareth Moreton

2021-06-04 15:30

developer   ~0131150

Well it looks like optimising with virtual registers will take a while to work out, since register tracking has to be fixed up prior to the peephole optimizer running, but the register allocator expects it to be messed up already and causes it to have a meltdown otherwise! Additionally, fixing the register tracking while the registers are still virtual seems to cause some of them to not be tracked at all, so I have a lot to work out and a lot to test by the looks of it. Still, I have arm-linux, aarch64-linux, i386-win32 and x86_64-win64 at my disposal, and I have x86_64-linux on a virtual machine if needs be.

Florian

2021-06-05 20:47

administrator   ~0131168

I think it makes no sense to do optimizations which depend on register allocation info in the pre. regalloc pass.

J. Gareth Moreton

2021-06-05 22:24

developer   ~0131171

Last edited: 2021-06-05 22:25

View 2 revisions

Theoretically it can perform better with virtual registers over real ones because some individual optimisations can strip out registers completely thanks to working out if they're equal to another register, for example. If the allocator has already run, there's a chance that this, or another virtual register, has been allocated to a non-volatile register that has to be preserved and restored in the function prologue and epilogue. Stripping these out later is very fiddly (e.g. due to stack alignment) and prone to error.

If a virtual register has been stripped out, it's much more likely that the colour graph will require fewer colours (unique registers) to fully allocate, and even if non-volatile registers still have to be used, there's a reduced chance of spillage. That's my logic anyway.

In the meantime, I'll re-create the patch but with the virtual directives removed, and I'll restore them if and when they're needed.

J. Gareth Moreton

2021-06-05 23:16

developer   ~0131172

Last edited: 2021-06-05 23:31

View 3 revisions

Removed the virtual directives and also updated the Include/ExcludeRegInUsedRegs functions that still directly modified the TUsedRegs state, but now uses the new SetUsed method (which is now inlined so it collapses to the relevant Include or Exclude statement). New "make cycle OPT=-vs" timings on arm-linux:

Trunk:

[28.721] 399115 lines compiled, 28.7 sec, 3914432 bytes code, 1122404 bytes data
[29.374] 399115 lines compiled, 29.4 sec, 3914432 bytes code, 1122404 bytes data
[29.086] 399115 lines compiled, 29.1 sec, 3914432 bytes code, 1122404 bytes data

Refactor:

[28.794] 399136 lines compiled, 28.8 sec, 3914864 bytes code, 1122404 bytes data
[28.793] 399136 lines compiled, 28.8 sec, 3914864 bytes code, 1122404 bytes data
[28.913] 399136 lines compiled, 28.9 sec, 3914864 bytes code, 1122404 bytes data

This will probably have much more effect on the x86 platforms that make extensive use of TmpUsedRegs. Hopefully I'll have my laptop repaired again(!) (different problem to last time) and I can verify that properly.

The whole virtual register thing is something I'll be playing with on the side - hopefully it will yield something worthwhile.
usedregs.patch (8,670 bytes)   
Index: compiler/aoptobj.pas
===================================================================
--- compiler/aoptobj.pas	(revision 49473)
+++ compiler/aoptobj.pas	(working copy)
@@ -81,17 +81,18 @@
         Destructor Destroy;override;
 
         Procedure Clear;
-        { update the info with the pairegalloc objects coming after
-          p                                                         }
+        { update the info with the tai_regalloc objects coming after p }
         procedure Update(p: Tai; IgnoreNewAllocs: Boolean=false);
         { is Reg currently in use }
-        Function IsUsed(Reg: TRegister): Boolean;
+        function IsUsed(Reg: TRegister): Boolean; {$ifdef USEINLINE}inline;{$endif USEINLINE}
         { get all the currently used registers }
-        Function GetUsedRegs: TRegSet;
+        function GetUsedRegs: TRegSet; {$ifdef USEINLINE}inline;{$endif USEINLINE}
+        { Set register to used or not }
+        procedure SetUsed(const SupReg: TSuperRegister; Used: Boolean); {$ifdef USEINLINE}inline;{$endif USEINLINE}
 
         { outputs  the current set }
-        Procedure Dump(var t : text);
-      Private
+        procedure Dump(var t : text);
+      protected
         Typ : TRegisterType;
         UsedRegs: TRegSet;
       End;
@@ -269,9 +270,9 @@
 
         { processor independent methods }
 
-        Procedure CreateUsedRegs(var regs: TAllUsedRegs);
-        Procedure ClearUsedRegs;
-        Procedure UpdateUsedRegs(p : Tai);
+        class procedure CreateUsedRegs(var regs: TAllUsedRegs); static;
+        procedure ClearUsedRegs;
+        procedure UpdateUsedRegs(p : Tai); {$ifdef USEINLINE}inline;{$endif USEINLINE}
         class procedure UpdateUsedRegs(var Regs: TAllUsedRegs; p: Tai); static;
 
         { If UpdateUsedRegsAndOptimize has read ahead, the result is one before
@@ -283,9 +284,9 @@
         procedure RestoreUsedRegs(const Regs : TAllUsedRegs);
         procedure TransferUsedRegs(var dest: TAllUsedRegs);
         class procedure ReleaseUsedRegs(const regs : TAllUsedRegs); static;
-        class function RegInUsedRegs(reg : TRegister;regs : TAllUsedRegs) : boolean; static;
-        class procedure IncludeRegInUsedRegs(reg : TRegister;var regs : TAllUsedRegs); static;
-        class procedure ExcludeRegFromUsedRegs(reg: TRegister;var regs : TAllUsedRegs); static;
+        class function RegInUsedRegs(reg : TRegister;regs : TAllUsedRegs) : boolean; static; {$ifdef USEINLINE}inline;{$endif USEINLINE}
+        class procedure IncludeRegInUsedRegs(reg : TRegister;var regs : TAllUsedRegs); static; {$ifdef USEINLINE}inline;{$endif USEINLINE}
+        class procedure ExcludeRegFromUsedRegs(reg: TRegister;var regs : TAllUsedRegs); static; {$ifdef USEINLINE}inline;{$endif USEINLINE}
 
         class function GetAllocationString(const regs : TAllUsedRegs) : string; static;
 
@@ -518,9 +519,9 @@
                   case tai_regalloc(p).ratype of
                     ra_alloc :
                       if not(IgnoreNewAllocs) then
-                        Include(UsedRegs, getsupreg(tai_regalloc(p).reg));
+                        SetUsed(getsupreg(tai_regalloc(p).reg), True);
                     ra_dealloc :
-                      Exclude(UsedRegs, getsupreg(tai_regalloc(p).reg));
+                      SetUsed(getsupreg(tai_regalloc(p).reg), False);
                     else
                       ;
                   end;
@@ -534,13 +535,13 @@
       End;
 
 
-    Function TUsedRegs.IsUsed(Reg: TRegister): Boolean;
+    Function TUsedRegs.IsUsed(Reg: TRegister): Boolean; {$ifdef USEINLINE}inline;{$endif USEINLINE}
       Begin
         IsUsed := (getregtype(Reg)=Typ) and (getsupreg(Reg) in UsedRegs);
       End;
 
 
-    Function TUsedRegs.GetUsedRegs: TRegSet; inline;
+    Function TUsedRegs.GetUsedRegs: TRegSet; {$ifdef USEINLINE}inline;{$endif USEINLINE}
       Begin
         GetUsedRegs := UsedRegs;
       End;
@@ -558,6 +559,14 @@
       end;
 
 
+    procedure TUsedRegs.SetUsed(const SupReg: TSuperRegister; Used: Boolean); {$ifdef USEINLINE}inline;{$endif USEINLINE}
+      begin
+        if Used then
+          Include(UsedRegs, SupReg)
+        else
+          Exclude(UsedRegs, SupReg);
+      end;
+
     Destructor TUsedRegs.Destroy;
       Begin
         inherited destroy;
@@ -971,7 +980,7 @@
         end;
 {$endif DEBUG_AOPTOBJ}
 
-      procedure TAOptObj.CreateUsedRegs(var regs: TAllUsedRegs);
+      class procedure TAOptObj.CreateUsedRegs(var regs: TAllUsedRegs);
         var
           i : TRegisterType;
         begin
@@ -995,6 +1004,9 @@
       function TAOptObj.UpdateUsedRegsAndOptimize(p : Tai): Tai;
         var
           NotFirst: Boolean;
+          ThisReg: TRegister;
+          i : TRegisterType;
+          s : TSuperRegister;
         begin
           { this code is based on TUsedRegs.Update to avoid multiple passes through the asmlist,
             the code is duplicated here }
@@ -1048,11 +1060,16 @@
                   (p.typ=ait_RegAlloc) Do
               begin
                 prefetch(pointer(p.Next)^);
+
+                ThisReg := tai_regalloc(p).reg;
+                i := getregtype(ThisReg);
+                s := getsupreg(ThisReg);
+
                 case tai_regalloc(p).ratype of
                   ra_alloc :
-                    Include(UsedRegs[getregtype(tai_regalloc(p).reg)].UsedRegs, getsupreg(tai_regalloc(p).reg));
+                    UsedRegs[i].SetUsed(s, True);
                   ra_dealloc :
-                    Exclude(UsedRegs[getregtype(tai_regalloc(p).reg)].UsedRegs, getsupreg(tai_regalloc(p).reg));
+                    UsedRegs[i].SetUsed(s, False);
                   else
                     { Do nothing };
                 end;
@@ -1067,8 +1084,18 @@
         end;
 
 
-      procedure TAOptObj.UpdateUsedRegs(p : Tai);
+      procedure TAOptObj.UpdateUsedRegs(p : Tai); {$ifdef USEINLINE}inline;{$endif USEINLINE}
         begin
+          UpdateUsedRegs(UsedRegs, p);
+        end;
+
+
+      class procedure TAOptObj.UpdateUsedRegs(var Regs : TAllUsedRegs;p : Tai);
+        var
+          ThisReg: TRegister;
+          i : TRegisterType;
+          s : TSuperRegister;
+        begin
           { this code is based on TUsedRegs.Update to avoid multiple passes through the asmlist,
             the code is duplicated here }
           repeat
@@ -1083,11 +1110,16 @@
                   (p.typ=ait_RegAlloc) Do
               begin
                 prefetch(pointer(p.Next)^);
+
+                ThisReg := tai_regalloc(p).reg;
+                i := getregtype(ThisReg);
+                s := getsupreg(ThisReg);
+
                 case tai_regalloc(p).ratype of
                   ra_alloc :
-                    Include(UsedRegs[getregtype(tai_regalloc(p).reg)].UsedRegs, getsupreg(tai_regalloc(p).reg));
+                    Regs[i].SetUsed(s, True);
                   ra_dealloc :
-                    Exclude(UsedRegs[getregtype(tai_regalloc(p).reg)].UsedRegs, getsupreg(tai_regalloc(p).reg));
+                    Regs[i].SetUsed(s, False);
                   else
                     ;
                 end;
@@ -1100,15 +1132,6 @@
         end;
 
 
-      class procedure TAOptObj.UpdateUsedRegs(var Regs : TAllUsedRegs;p : Tai);
-        var
-          i : TRegisterType;
-        begin
-          for i:=low(TRegisterType) to high(TRegisterType) do
-            Regs[i].Update(p);
-        end;
-
-
       function TAOptObj.CopyUsedRegs(var dest: TAllUsedRegs): boolean;
       var
         i : TRegisterType;
@@ -1152,23 +1175,21 @@
       end;
 
 
-      class Function TAOptObj.RegInUsedRegs(reg : TRegister;regs : TAllUsedRegs) : boolean;
+      class Function TAOptObj.RegInUsedRegs(reg : TRegister;regs : TAllUsedRegs) : boolean; {$ifdef USEINLINE}inline;{$endif USEINLINE}
       begin
         result:=regs[getregtype(reg)].IsUsed(reg);
       end;
 
 
-      class procedure TAOptObj.IncludeRegInUsedRegs(reg: TRegister;
-       var regs: TAllUsedRegs);
+      class procedure TAOptObj.IncludeRegInUsedRegs(reg: TRegister; var regs: TAllUsedRegs); {$ifdef USEINLINE}inline;{$endif USEINLINE}
       begin
-        include(regs[getregtype(reg)].UsedRegs,getsupreg(Reg));
+        regs[getregtype(reg)].SetUsed(getsupreg(Reg), True);
       end;
 
 
-      class procedure TAOptObj.ExcludeRegFromUsedRegs(reg: TRegister;
-       var regs: TAllUsedRegs);
+      class procedure TAOptObj.ExcludeRegFromUsedRegs(reg: TRegister; var regs: TAllUsedRegs); {$ifdef USEINLINE}inline;{$endif USEINLINE}
       begin
-        exclude(regs[getregtype(reg)].UsedRegs,getsupreg(Reg));
+        regs[getregtype(reg)].SetUsed(getsupreg(Reg), False);
       end;
 
 
usedregs.patch (8,670 bytes)   

Issue History

Date Modified Username Field Change
2021-06-02 15:16 J. Gareth Moreton New Issue
2021-06-02 15:16 J. Gareth Moreton File Added: usedregs.patch
2021-06-02 15:17 J. Gareth Moreton Steps to Reproduce Updated View Revisions
2021-06-02 15:17 J. Gareth Moreton Additional Information Updated View Revisions
2021-06-02 15:17 J. Gareth Moreton FPCTarget => -
2021-06-02 15:18 J. Gareth Moreton Tag Attached: patch
2021-06-02 15:18 J. Gareth Moreton Tag Attached: refactor
2021-06-02 15:18 J. Gareth Moreton Tag Attached: compiler
2021-06-02 18:06 Florian Note Added: 0131128
2021-06-02 18:24 J. Gareth Moreton Note Added: 0131129
2021-06-02 18:26 J. Gareth Moreton Note Edited: 0131129 View Revisions
2021-06-03 10:09 Sven Barth Note Added: 0131135
2021-06-03 15:46 J. Gareth Moreton Note Added: 0131139
2021-06-03 15:55 J. Gareth Moreton Note Edited: 0131139 View Revisions
2021-06-03 15:57 J. Gareth Moreton Note Edited: 0131139 View Revisions
2021-06-04 08:31 Sven Barth Note Added: 0131145
2021-06-04 08:32 Sven Barth Note Edited: 0131145 View Revisions
2021-06-04 13:37 J. Gareth Moreton Note Added: 0131149
2021-06-04 13:39 J. Gareth Moreton Note Edited: 0131149 View Revisions
2021-06-04 15:30 J. Gareth Moreton Note Added: 0131150
2021-06-05 20:47 Florian Note Added: 0131168
2021-06-05 22:24 J. Gareth Moreton Note Added: 0131171
2021-06-05 22:25 J. Gareth Moreton Note Edited: 0131171 View Revisions
2021-06-05 23:14 J. Gareth Moreton File Deleted: usedregs.patch
2021-06-05 23:16 J. Gareth Moreton Note Added: 0131172
2021-06-05 23:16 J. Gareth Moreton File Added: usedregs.patch
2021-06-05 23:27 J. Gareth Moreton Note Edited: 0131172 View Revisions
2021-06-05 23:31 J. Gareth Moreton Note Edited: 0131172 View Revisions