[Bug rtl-optimization/17482] [4.0 Regression] GCSE after reload replacing changing instructions

["steven at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>]

------- Additional Comments From steven at gcc dot gnu dot org  2004-09-15 18:00 -------
On Wednesday 15 September 2004 02:49, David Edelsohn wrote: 
> 	I already tried the change you suggested and it does not work. 
> That is not the main problem -- it may be another problem but it is not 
> the fundamental design flaw in the restructuring. 
 
You keep saying that, but I really, honestly believe there 
is no such restructuring problem. 
 
Let me explain. 
 
First of all, GCSE2 is misnamed.  It is *not* global common sub- 
expression ellimination.  A more appropriate name would be, ehm, 
only-just-not-local subexpression elimination. 
If you think it is a truely global pass, that probably fooled you 
into thinking that this restructuring is fundamentally broken.  But 
that may in fact be not the problem at all (which doesn't mean that 
the bug wasn't my mistake, of course - but please read on...). 
 
The algorithm works as follows: 
 
a) Build the hash table of expressions (loads, if you will) that are 
   available at the end of each basic block.  Let us give it a name, 
   AVAIL_OUT. 
 
   The odd thing about postreload gcse is that AVAIL_OUT is only a 
   *local* property.  In classic GCSE, AVAIL_OUT is the union of 
   available expressions at the block entry minus the expressions 
   killed in the block: 
 
   AVAIL_IN(B)  = U AVAIL_OUT(S), S E pred(B) 
   AVAIL_OUT(B) = (AVAIL_IN(B) U EXPR_GEN (B)) - KILL(B) 
 
   This is clearly a global data flow problem, which needs to be 
   solved using a fixed-point iteration. 
   In postreload GCSE, this is not the case.  Instead, AVAIL_OUT(B) 
   is now the set of expressions generated in B that are not killed 
   before the end of the block, 
 
   AVAIL_IN(B)  = emtpy 
   AVAIL_OUT(B) = GEN_LOC(B) - KILL_LOC(B)      in postreload GCSE 
 
   This is computed as follows 
   1. Walk all instructions in the basic block from start to end, 
      and record the last point where each reg is modified. 
   2. Walk all instructions again from start to end, and add the 
      expressions to the hash table if the set destination of the 
      expression is not set after the current instruction. 
 
   Let's call the condition in step 2 "condition 1".  The CUIDs are 
   used to determine the value of the condition: 
 
     if CUID(last_set)>CUID(insn) then 
       the set in insn is killed in a later instruction - skip it. 
     else 
       add the set to AVAIL_OUT(B) where B is the basic block for insn. 
 
   There is no global dataflow involved, it is merely a local property 
   that tells you that the expression generated in insn in block B is 
   not killed before the end of block B. 
   An important consequence of this is that the expression is at least 
   partially available in the successors of B. 
 
b) Perform the partial redundancy elimination.  Again, postreload 
   GCSE does not actually do classic partial redundancy elimination. 
 
   Classic PRE uses global data flow analysis to determine AVAIL_OUT 
   and ANTIC_IN.  In postreload GCSE, ANTIC_IN(B) is empty (and in 
   fact not even defined, as such). 
 
   Instead, postreload uses an ad-hoc approach as follows: 
    1. Walk all instructions INSN in the basic block B, start to end. 
    2. If any of the operands of the expression generated by INSN have 
       changed since the beginning of the block, ignore the expression, 
       because even if it is in AVAIL_OUT of any pred(B) then it was 
       killed in B  before we saw insn. 
       Let's call this "condition 2". 
    3. If the expression was not killed, see if it is available in in 
       any predecessor of B, ie. in any E in AVAIL_OUT(pred(B)).  If 
       so, then E is partially redundant.  Try to eliminate it. 
    4. Finally record all registers/mems killed by INSN, so that for 
       the next instruction INSN in the walk of the instructions in B, 
       we can determine condition 2. 
 
c) Delete redundant expressions.  This part should not need explaining. 
 
 
 
Now, there are two important conclusions you can draw from this sketch 
of how this algorithm is supposed to work: 
 
1) Assume some expression E is generated in block A by insn1, and in 
   block B by insn2. 
 
   If condition 1 is satisfied in block A, and condition 2 is satisfied 
   in block B, and A is in pred(B), then the expression generated in 
   insn1 is not killed on the path from insn1 to insn2, or, 
 
   E is in AVAIL_OUT(E) and E is not killed in any insns between the 
   head of block B and insn2. 
 
   Therefore, the expression in insn1 is either partially or fully 
   redundant, depending on if E is in AVAIL_OUT(E) for all pred(B), or 
   only for some blocks in pred(B). 
 
   But condition 1 and condition 2 are both locally computed (!), hence 
   postreload gcse is in fact a local optimization. 
   This is why the last_bb and first_set checks, that is necessary for 
   the "real" global cse, are *not* necessary for postreload gcse. 
 
 
2) In your bug, you have the following two insns: 
 
(insn:HI 111 109 112 6 (set (reg:SI 11 11 [136]) 
        (mem/s:SI (pre_inc:SI (reg/f:SI 29 29 [orig:118 ivtmp.43 ] [118])) 
        [5 b S4 A8])) 265 {*movsi_internal1} (...)) 
    (expr_list:REG_INC (reg/f:SI 29 29 [orig:118 ivtmp.43 ] [118]) 
        (nil))) 
 
(insn:HI 112 111 113 6 (set (reg:SI 9 9 [137]) 
        (mem/s:SI (plus:SI (reg/f:SI 29 29 [orig:118 ivtmp.43 ] [118]) 
                (reg:SI 0 0 [135])) 
        [5 S4 A8])) 265 {*movsi_internal1} (...)) 
    (nil)) 
 
   both insn 111 and insn 112 are in basic block 6.  You say that 
   postreload gcse eliminates the load in insn 112, ignoring the pre_inc 
   in insn 111. 
 
   Now looking at the description of the algorithm given above, you 
   see that condition 2 is not satisfied, since reg 29 has been modified 
   between the start of basic block 6 and insn 112 in the same block. 
   Therefore, even though (apparently, I haven't seen the full dump) the 
   expression in insn 112 is also generated in at least one predecessor 
   of basic block 6, the expression in insn 112 is not redundant. 
 
   The bug is that condition 2 is somehow not being checked properly. 
 
 
Now, unfortunately my x86_64-suse-linux-gnu x powerpc-ibm-aix5.2 cross 
compiler refuses to reproduce the bug, so I'm sort of lost here. 
 
Could you please attach the full .postreload and .gcse2 dumps to the 
bug report? 
 

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17482