[llvm-dev] A register allocation problem

Tue Oct 30 10:36:45 PDT 2018

> 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.

> 
> selectOrSplit WREG:%vreg171 [1808r,1824r:0)  0 at 1808r w=INF assigning %vreg171 to %W1: V18 [1808r,1824r:0)  0 at 1808r V19 [1808r,1824r:0)  0 at 1808r
> 
> selectOrSplit WREG:%vreg361 [1840r,1872B:0)[1872B,1984r:2)[2848r,3136r:1)  0 at 1840r 1 at 2848r 2 at 1872B-phi w=1.556490e-01 assigning %vreg361 to %W0: V16 [1840r,1872B:0)[1872B,1984r:2)[2848r,3136r:1)  0 at 1840r 1 at 2848r 2 at 1872B-phi V17 [1840r,1872B:0)[1872B,1984r:2)[2848r,3136r:1)  0 at 1840r 1 at 2848r 2 at 1872B-phi
> 
> selectOrSplit WREG:%vreg201 [1920r,2000r:0)  0 at 1920r w=1.328125e-01 assigning %vreg201 to %W1: V18 [1920r,2000r:0)  0 at 1920r V19 [1920r,2000r:0)  0 at 1920r
> 
> selectOrSplit WREG:%vreg206 [2000r,2128r:0)  0 at 2000r w=1.207386e-01 assigning %vreg206 to %W0: V16 [2000r,2128r:0)  0 at 2000r V17 [2000r,2128r:0)  0 at 2000r
> 
> selectOrSplit WREG:%vreg212 [2096r,2208r:0)  0 at 2096r w=1.245117e-01 assigning %vreg212 to %W1: V18 [2096r,2208r:0)  0 at 2096r V19 [2096r,2208r:0)  0 at 2096r
> 
> selectOrSplit WREG:%vreg213 [2112r,2240r:0)  0 at 2112r w=1.207386e-01 assigning %vreg213 to %W2: V20 [2112r,2240r:0)  0 at 2112r V21 [2112r,2240r:0)  0 at 2112r
> 
> selectOrSplit WREG:%vreg217 [2176r,2384r:0)  0 at 2176r w=1.048520e-01 assigning %vreg217 to %W0: V16 [2176r,2384r:0)  0 at 2176r V17 [2176r,2384r:0)  0 at 2176r
> 
> selectOrSplit WREG:%vreg234 [2240r,2432r:0)[2432r,2624r:1)  0 at 2240r 1 at 2432r w=1.626275e-01 assigning %vreg234 to %W1: V18 [2240r,2432r:0)[2432r,2624r:1)  0 at 2240r 1 at 2432r V19 [2240r,2432r:0)[2432r,2624r:1)  0 at 2240r 1 at 2432r
> 
> selectOrSplit WREG:%vreg222 [2256r,2368r:0)  0 at 2256r w=1.245117e-01 assigning %vreg222 to %W2: V20 [2256r,2368r:0)  0 at 2256r V21 [2256r,2368r:0)  0 at 2256r
> 
> selectOrSplit WREG:%vreg227 [2336r,2528r:0)  0 at 2336r w=1.076858e-01 assigning %vreg227 to %W3: V22 [2336r,2528r:0)  0 at 2336r V23 [2336r,2528r:0)  0 at 2336r
> 
> selectOrSplit WREG:%vreg230 [2384r,2448r:0)  0 at 2384r w=1.373922e-01 assigning %vreg230 to %W0: V16 [2384r,2448r:0)  0 at 2384r V17 [2384r,2448r:0)  0 at 2384r
> 
> selectOrSplit WREG:%vreg235 [2448r,2560r:0)  0 at 2448r w=1.245117e-01 assigning %vreg235 to %W0: V16 [2448r,2560r:0)  0 at 2448r V17 [2448r,2560r:0)  0 at 2448r
> 
> selectOrSplit WREG:%vreg239 [2512r,2864r:0)  0 at 2512r w=8.477394e-02 RS_Assign Cascade 0 wait for second round queuing new interval: %vreg239 [2512r,2864r:0)  0 at 2512r 
> 
> ... ...
> ====================================================================
> If we assign %vreg360 to W3, %vreg239 can be assigned to W2. The W register SPILL can be avoided.
> 
> How to tune the register allocation for this kind of cases ?
> 
> Best regards,
> 
> Sun Qiang

- Matthias