A register allocation problem

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.

The following shows the procedural of register allocation.

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@640r w=4.310345e-03
AllocationOrder(WREG) = [ %W0 %W1 %W2 %W3 ] assigning %vreg140 to %W0: V16 [640r,704r:0) 0@640r V17 [640r,704r:0) 0@640r

selectOrSplit WREG:%vreg142 [752r,864r:0) 0@752r w=3.906250e-03 assigning %vreg142 to %W0: V16 [752r,864r:0) 0@752r V17 [752r,864r:0) 0@752r

selectOrSplit WREG:%vreg160 [800r,1200r:0) 0@800r w=2.500000e-03 assigning %vreg160 to %W1: V18 [800r,1200r:0) 0@800r V19 [800r,1200r:0) 0@800r

selectOrSplit WREG:%vreg173 [912r,1392r:0) 0@912r w=2.272727e-03 assigning %vreg173 to %W0: V16 [912r,1392r:0) 0@912r V17 [912r,1392r:0) 0@912r

selectOrSplit WREG:%vreg166 [992r,1248r:0) 0@992r w=3.048780e-03 assigning %vreg166 to %W2: V20 [992r,1248r:0) 0@992r V21 [992r,1248r:0) 0@992r

selectOrSplit WREG:%vreg145 [1024r,1120r:0) 0@1024r w=4.032258e-03 assigning %vreg145 to %W3: V22 [1024r,1120r:0) 0@1024r V23 [1024r,1120r:0) 0@1024r

selectOrSplit WREG:%vreg194 [1136r,1216r:0) 0@1136r w=4.166667e-03 assigning %vreg194 to %W3: V22 [1136r,1216r:0) 0@1136r V23 [1136r,1216r:0) 0@1136r

selectOrSplit WREG:%vreg161 [1200r,1344r:0) 0@1200r w=3.676471e-03 assigning %vreg161 to %W1: V18 [1200r,1344r:0) 0@1200r V19 [1200r,1344r:0) 0@1200r

selectOrSplit WREG:%vreg167 [1248r,1696r:0) 0@1248r w=2.358491e-03 assigning %vreg167 to %W2: V20 [1248r,1696r:0) 0@1248r V21 [1248r,1696r:0) 0@1248r

selectOrSplit WREG:%vreg196 [1328r,1536r:0) 0@1328r w=3.289474e-03 assigning %vreg196 to %W3: V22 [1328r,1536r:0) 0@1328r V23 [1328r,1536r:0) 0@1328r

selectOrSplit WREG:%vreg174 [1392r,1728r:0) 0@1392r w=2.717391e-03 assigning %vreg174 to %W0: V16 [1392r,1728r:0) 0@1392r V17 [1392r,1728r:0) 0@1392r

selectOrSplit WREG:%vreg164 [1488r,1632r:0) 0@1488r w=3.676471e-03 assigning %vreg164 to %W1: V18 [1488r,1632r:0) 0@1488r V19 [1488r,1632r:0) 0@1488r

selectOrSplit WREG:%vreg149 [1568r,1744r:0) 0@1568r w=3.472222e-03 assigning %vreg149 to %W3: V22 [1568r,1744r:0) 0@1568r V23 [1568r,1744r:0) 0@1568r

selectOrSplit WREG:%vreg168 [1696r,1776r:0) 0@1696r w=4.166667e-03 assigning %vreg168 to %W1: V18 [1696r,1776r:0) 0@1696r V19 [1696r,1776r:0) 0@1696r

selectOrSplit WREG:%vreg175 [1728r,1840r:0) 0@1728r w=3.906250e-03 assigning %vreg175 to %W0: V16 [1728r,1840r:0) 0@1728r V17 [1728r,1840r:0) 0@1728r

selectOrSplit WREG:%vreg360 [1760r,1872B:0)[1872B,1904r:2)[2672r,2944r:1) 0@1760r 1@2672r 2@1872B-phi w=1.587010e-01 assigning %vreg360 to %W2: V20 [1760r,1872B:0)[1872B,1904r:2)[2672r,2944r:1) 0@1760r 1@2672r 2@1872B-phi V21 [1760r,1872B:0)[1872B,1904r:2)[2672r,2944r:1) 0@1760r 1@2672r 2@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@1808r w=INF assigning %vreg171 to %W1: V18 [1808r,1824r:0) 0@1808r V19 [1808r,1824r:0) 0@1808r

selectOrSplit WREG:%vreg361 [1840r,1872B:0)[1872B,1984r:2)[2848r,3136r:1) 0@1840r 1@2848r 2@1872B-phi w=1.556490e-01 assigning %vreg361 to %W0: V16 [1840r,1872B:0)[1872B,1984r:2)[2848r,3136r:1) 0@1840r 1@2848r 2@1872B-phi V17 [1840r,1872B:0)[1872B,1984r:2)[2848r,3136r:1) 0@1840r 1@2848r 2@1872B-phi

selectOrSplit WREG:%vreg201 [1920r,2000r:0) 0@1920r w=1.328125e-01 assigning %vreg201 to %W1: V18 [1920r,2000r:0) 0@1920r V19 [1920r,2000r:0) 0@1920r

selectOrSplit WREG:%vreg206 [2000r,2128r:0) 0@2000r w=1.207386e-01 assigning %vreg206 to %W0: V16 [2000r,2128r:0) 0@2000r V17 [2000r,2128r:0) 0@2000r

selectOrSplit WREG:%vreg212 [2096r,2208r:0) 0@2096r w=1.245117e-01 assigning %vreg212 to %W1: V18 [2096r,2208r:0) 0@2096r V19 [2096r,2208r:0) 0@2096r

selectOrSplit WREG:%vreg213 [2112r,2240r:0) 0@2112r w=1.207386e-01 assigning %vreg213 to %W2: V20 [2112r,2240r:0) 0@2112r V21 [2112r,2240r:0) 0@2112r

selectOrSplit WREG:%vreg217 [2176r,2384r:0) 0@2176r w=1.048520e-01 assigning %vreg217 to %W0: V16 [2176r,2384r:0) 0@2176r V17 [2176r,2384r:0) 0@2176r

selectOrSplit WREG:%vreg234 [2240r,2432r:0)[2432r,2624r:1) 0@2240r 1@2432r w=1.626275e-01 assigning %vreg234 to %W1: V18 [2240r,2432r:0)[2432r,2624r:1) 0@2240r 1@2432r V19 [2240r,2432r:0)[2432r,2624r:1) 0@2240r 1@2432r

selectOrSplit WREG:%vreg222 [2256r,2368r:0) 0@2256r w=1.245117e-01 assigning %vreg222 to %W2: V20 [2256r,2368r:0) 0@2256r V21 [2256r,2368r:0) 0@2256r

selectOrSplit WREG:%vreg227 [2336r,2528r:0) 0@2336r w=1.076858e-01 assigning %vreg227 to %W3: V22 [2336r,2528r:0) 0@2336r V23 [2336r,2528r:0) 0@2336r

selectOrSplit WREG:%vreg230 [2384r,2448r:0) 0@2384r w=1.373922e-01 assigning %vreg230 to %W0: V16 [2384r,2448r:0) 0@2384r V17 [2384r,2448r:0) 0@2384r

selectOrSplit WREG:%vreg235 [2448r,2560r:0) 0@2448r w=1.245117e-01 assigning %vreg235 to %W0: V16 [2448r,2560r:0) 0@2448r V17 [2448r,2560r:0) 0@2448r

selectOrSplit WREG:%vreg239 [2512r,2864r:0) 0@2512r w=8.477394e-02 RS_Assign Cascade 0 wait for second round queuing new interval: %vreg239 [2512r,2864r:0) 0@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

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