[llvm-dev] A register allocation problem

Thu Nov 1 00:44:25 PDT 2018

> -----Original Message-----
> From: mbraun at apple.com [mailto:mbraun at apple.com]
> Sent: Wednesday, October 31, 2018 1:37 AM
> To: Sunqiang (Compiler) <sunqiang13 at huawei.com>
> Cc: llvm-dev at lists.llvm.org; Yuchao (Michael) <michael.yuchao at huawei.com>
> Subject: Re: [llvm-dev] A register allocation problem
> 
> 
> > On Oct 29, 2018, at 11:59 PM, Sunqiang (Compiler) via llvm-dev <llvm-
> dev at lists.llvm.org> wrote:
> >
> > To whom it may concern,
> >
> > On our target we have a register class including four registers.
> > Spilling of these registers is very expensive and it is very important for us to
> avoid that.
> > I have a testcase where register pressure is 4 but I have one spill.
> > A small change in allocation would have fixed the problem.
> In general it's a heuristic so you have no guarantee to get the optiomal
> solution. That said, I saw something odd:
> 
> >
> > The following shows the procedural of register allocation.
> >
> ==========================================================
> ==========
> > selectOrSplit WREG:%vreg140 [640r,704r:0)  0 at 640r w=4.310345e-03
> > AllocationOrder(WREG) = [ %W0 %W1 %W2 %W3 ] assigning %vreg140
> to %W0: V16 [640r,704r:0)  0 at 640r V17 [640r,704r:0)  0 at 640r
> >
> > selectOrSplit WREG:%vreg142 [752r,864r:0)  0 at 752r w=3.906250e-03
> assigning %vreg142 to %W0: V16 [752r,864r:0)  0 at 752r V17 [752r,864r:0)
> 0 at 752r
> >
> > selectOrSplit WREG:%vreg160 [800r,1200r:0)  0 at 800r w=2.500000e-03
> assigning %vreg160 to %W1: V18 [800r,1200r:0)  0 at 800r V19 [800r,1200r:0)
> 0 at 800r
> >
> > selectOrSplit WREG:%vreg173 [912r,1392r:0)  0 at 912r w=2.272727e-03
> assigning %vreg173 to %W0: V16 [912r,1392r:0)  0 at 912r V17 [912r,1392r:0)
> 0 at 912r
> >
> > selectOrSplit WREG:%vreg166 [992r,1248r:0)  0 at 992r w=3.048780e-03
> assigning %vreg166 to %W2: V20 [992r,1248r:0)  0 at 992r V21 [992r,1248r:0)
> 0 at 992r
> >
> > selectOrSplit WREG:%vreg145 [1024r,1120r:0)  0 at 1024r w=4.032258e-03
> assigning %vreg145 to %W3: V22 [1024r,1120r:0)  0 at 1024r V23 [1024r,1120r:0)
> 0 at 1024r
> >
> > selectOrSplit WREG:%vreg194 [1136r,1216r:0)  0 at 1136r w=4.166667e-03
> assigning %vreg194 to %W3: V22 [1136r,1216r:0)  0 at 1136r V23 [1136r,1216r:0)
> 0 at 1136r
> >
> > selectOrSplit WREG:%vreg161 [1200r,1344r:0)  0 at 1200r w=3.676471e-03
> assigning %vreg161 to %W1: V18 [1200r,1344r:0)  0 at 1200r V19 [1200r,1344r:0)
> 0 at 1200r
> >
> > selectOrSplit WREG:%vreg167 [1248r,1696r:0)  0 at 1248r w=2.358491e-03
> assigning %vreg167 to %W2: V20 [1248r,1696r:0)  0 at 1248r V21 [1248r,1696r:0)
> 0 at 1248r
> >
> > selectOrSplit WREG:%vreg196 [1328r,1536r:0)  0 at 1328r w=3.289474e-03
> assigning %vreg196 to %W3: V22 [1328r,1536r:0)  0 at 1328r V23 [1328r,1536r:0)
> 0 at 1328r
> >
> > selectOrSplit WREG:%vreg174 [1392r,1728r:0)  0 at 1392r w=2.717391e-03
> assigning %vreg174 to %W0: V16 [1392r,1728r:0)  0 at 1392r V17 [1392r,1728r:0)
> 0 at 1392r
> >
> > selectOrSplit WREG:%vreg164 [1488r,1632r:0)  0 at 1488r w=3.676471e-03
> assigning %vreg164 to %W1: V18 [1488r,1632r:0)  0 at 1488r V19 [1488r,1632r:0)
> 0 at 1488r
> >
> > selectOrSplit WREG:%vreg149 [1568r,1744r:0)  0 at 1568r w=3.472222e-03
> assigning %vreg149 to %W3: V22 [1568r,1744r:0)  0 at 1568r V23 [1568r,1744r:0)
> 0 at 1568r
> >
> > selectOrSplit WREG:%vreg168 [1696r,1776r:0)  0 at 1696r w=4.166667e-03
> assigning %vreg168 to %W1: V18 [1696r,1776r:0)  0 at 1696r V19 [1696r,1776r:0)
> 0 at 1696r
> >
> > selectOrSplit WREG:%vreg175 [1728r,1840r:0)  0 at 1728r w=3.906250e-03
> assigning %vreg175 to %W0: V16 [1728r,1840r:0)  0 at 1728r V17 [1728r,1840r:0)
> 0 at 1728r
> >
> > selectOrSplit WREG:%vreg360 [1760r,1872B:0)[1872B,1904r:2)[2672r,2944r:1)
> 0 at 1760r 1 at 2672r 2 at 1872B-phi w=1.587010e-01 assigning %vreg360 to %W2:
> V20 [1760r,1872B:0)[1872B,1904r:2)[2672r,2944r:1)  0 at 1760r 1 at 2672r
> 2 at 1872B-phi V21 [1760r,1872B:0)[1872B,1904r:2)[2672r,2944r:1)  0 at 1760r
> 1 at 2672r 2 at 1872B-phi
> 
> I think something is off here (though it may be easier to confirm if the actual
> instructions are available): To my reading the [2672r,2944r:1) segment is
> disconnected from the other two segments [1760r,1872B:0)[1872B,1904r:2)
> 
> This would mean you are unnecessarily forcing the register allocator to assign
> the same register to them even though you just as well could have used two
> separate vregs here to allow the allocator to choose different registers.
> 
> Did you run your backend with -verify-machineinstrs enabled? It should
> abort and print an error message for disconnected components.

I have checked multiple connected components for all the virtual registers. 
There is no multiple connected component during the register allocation.

Best regards,

Sun Qiang