Hi Vladimir,
I have been analyzing a test case for which shrink wrapping fails
(on powerpc, 64bit LE). But if the same test case is slightly modified,
shrink wrapping kicks in.
Here are the two tests:
Test1 (shrink wrapped)
long
foo (long i, long cond)
{
i = i + 1;
if (cond)
bar ();
return i;
}
Test2 (not shrink wrapped)
long
foo (long i, long cond)
{
if (cond)
bar ();
return i+1;
}
The difference between the two tests is when ‘i’ is incremented.
There is a difference in register allocation by IRA in the two cases.
Input RTL to IRA (Test1: passing case)
BB2:
set r123, r4
set r122, r3
set r120, compare(r123, 0)
set r117, r122 + 1
if r120 jump BB4 else jump BB3
BB3:
call bar()
BB4:
set r3, r117
return r3
Input RTL to IRA (Test2: failing case)
BB2:
set r123, r4
set r122, r3
set r120, compare(r123, 0)
set r118, r122
if r120 jump BB4 else jump BB3
BB3:
call bar()
BB4:
set r3, r118+1
return r3
There is a difference in registers allocated for the pseudo register
r117 (passing case) and pseudo register r118 (failing case) by IRA.
r117 is allocated r3 while r118 is allocated r31.
Since r117 is allocated r3, r3 is spilled across the call to bar() by LRA.
And so only BB3 requires a prolog and shrink wrap is successful.
In the failing case, since r31 is assigned to r118, BB2 requires a prolog
and shrink wrap fails.
In the IRA pass, after graph coloring, both r117 and r118 get assigned
to r3. However, the routine improve_allocation() assigns r31 to r118.
The routine improve_allocation() is called after graph coloring. In this
routine, IRA checks for each allocno if spilling any conflicting allocnos
can improve the allocation of this allocno.
Going into more detail, improve_allocation() does the following:
Step 1: We first compute the cost improvement for usage of each profitable
hard register for a given allocno A. The cost improvement is computed as
follows:
costs[regno] = A->hard_reg_costs[regno] // ‘hard_reg_costs’ is an array
of usage costs for each hard register
costs[regno] -= allocno_copy_cost_saving (A, regno);
costs[regno] -= base_cost; //Say, ‘reg’ is assigned to A. Then
‘base_cost’ is the usage cost of ‘reg’ for A.
Step 2: Then we process each conflicting allocno of A and update the cost
improvement for the profitable hard registers of A. Basically, we compute
the spill costs of the conflicting allocnos and update the cost (for A) of
the register that was assigned to the conflicting allocno.
Step 3: We then find the best register among the profitable registers, spill
the conflicting allocno that uses this best register and assign the best
register to A.
However, the initial hard register costs for some of the profitable hard
registers is different in the passing and failing test cases. More
specifically, the costs in hard_reg_costs[] array are 0 for regs 14-31
in the failing case. In the passing case, the costs in hard_reg_costs[]
for regs 14-31 is 2000.
At the end of step 1, costs[r31] is -390 for failing case(for allocno r118)
and 1610 for passing case (for allocno r117).
In step 2 for the failing test, the only conflicting allocno for r118 is
the allocno for r120 which is used to hold the value of the compare operation.
The pseudo r120 has been assigned to r100 by the graph coloring step. But
r100 is not in the set of profitable hard registers for r118. (The profitable
hard regs are: [0, 3-12, 14-31]). So the allocno for r120 is not considered
for spilling. And finally in step 3, r31 is assigned to r118.
I have a few queries:
1. A zero cost seems strange for the regs r14-r31. If using a reg in the
set [14..31] has zero cost, then why wasn’t such a reg chosen for r118
in the first place, instead of r3?
2. In step 3, shouldn’t we restrict the register chosen to be a register
that has been assigned to a conflicting allocno? This is not the case for
the failing test. The allocno for r118 is assigned r31, but there is no
conflicting allocno that has been assigned r31.
3. In steps 1 & 2, shouldn’t we consider the register save and restore
cost too? ’r31’ being a callee-save (non-volatile) register has to be
saved before being used, whereas this is not required for r3 which is a
caller-save (volatile) register.
Thanks in advance,
Surya
