[Bug rtl-optimization/109009] Shrink Wrap missed opportunity

["jskumari at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109009

--- Comment #6 from Surya Kumari Jangala <jskumari at gcc dot gnu.org> ---
Continuing with the analysis of the test cases specified in comment 5, here are
some findings:

After graph colouring, when we do improve_allocation(), we find that in the
failing test case, the hard_reg_cost[r31] for allocno r118 is 0. (Note: not
just r31, for several other registers the cost is 0). The cost for r3 is 2390.

I spent some time investigating why the hard_reg_cost is 0. In the failing
test, the hard_reg_cost[] array is initialized to ALLOCNO_CLASS_COST in the
routine setup_allocno_class_and_costs(). ALLOCNO_CLASS_COST for allocno r118 is
0.

In the passing test, the hard_reg_cost[] array is initialized to
ALLOCNO_CLASS_COST in the routine process_bb_node_for_hard_reg_moves().
ALLOCNO_CLASS_COST is 2000 for allocno r117.

The reason the initialization happens in a different routine in the passing and
failing tests is because the preferred register class is different from the
allocno class in the failing case (the former is BASE_REGS while the latter is
GENERAL_REGS), while in the passing case both are same (GENERAL_REGS).

ALLOCNO_CLASS_COST is minimal accumulated register class cost of the allocno
class.

In the failing case, while the initial value of hard_reg_cost[r3] is 0, it is
changed in the following routines:
1. ira_tune_allocno_costs() : 0->2640
 (this routine checks if the register is caller save and if it is live across a
call. r3 is caller save while r31 is not. So, only cost for r3 is changed.)
2. process_regs_for_copy() : 2640->2390
 (this routine processes the 'set r3, r118+1' insn and reduces the cost of r3
in order to make it more preferential for r118. Again, cost of r31 is not
changed as there is no insn involving r31 & r118)

Even though r31 has 0 cost, r3 is chosen to be assigned to r118 because r31 is
a callee save register and it's use will have save/restore cost.

In the passing case, both r31 and r3 initially have a cost of 2000. 

The cost for r3 is then changed in the following routines:
1. process_bb_node_for_hard_reg_moves() : 2000->0
     (the cost is reduced in order to give preference to r3 for allocno r117.
This is due to the 'set r3, r117' insn)
2. ira_tune_allocno_costs () : 0->2640
3. process_regs_for_copy() : 2640->640

r3 is chosen for allocno r117 as it has lesser cost than r31.

Next, I checked why ALLOCNO_CLASS_COST is 0 in the failing case while in the
passing case it is 2000.

In the routine find_costs_and_classes(), we compute the cost of each register
class for each allocno. First we go thru all the insns in the routine. Then for
each insn which involves a copy from/to a hard reg to/from a pseudo reg, we
compute the cost of the 'move' if the pseudo is assigned a register from a
specific register class. This cost is the register class cost of this allocno
for this specific insn. We add up all such costs to get the register class cost
for an allocno.

In the passing case, we have the insn 'set r3, r117' which is processed in
find_costs_and_classes(). For this insn, we check the cost of the move if r117
is assigned to different register classes. The minimum of these costs is the
ALLOCNO_CLASS_COST for r117.

But in the failing case, there is no 'set' insn involving a hard register and
the pseudo register r118. So the ALLOCNO_CLASS_COST is 0.