[Bug rtl-optimization/33828] Issues with the implementation of code hoisting in gcse.c

[steven at gcc dot gnu dot org]

------- Comment #2 from steven at gcc dot gnu dot org  2007-10-20 10:48 -------
A second issue with code hoisting in gcse.c is that it only looks at basic
blocks immediately dominated by the branch point to hoist to.  Quoting
gcse.c:hoist_code():

  /* Walk over each basic block looking for potentially hoistable
     expressions, nothing gets hoisted from the entry block.  */
  FOR_EACH_BB (bb)
    {
      int found = 0;
      int insn_inserted_p;

      domby = get_dominated_by (CDI_DOMINATORS, bb);
      ...

An expression can be very busy at some point in the CFG, and be computed in a
block that is not immediately dominated at that point, e.g.

BB1
if (...) goto BB2 else goto BB3
{ succ BB2, BB3 }

{ pred BB1 }
BB2
r1 <- exp1
goto BB6
{ succ BB6 }

{ pred BB1}
BB3
if (...) goto BB4 else goto BB5
{ succ BB4, BB5 }

{ pred BB3 }
BB4
r2 <- exp1
goto BB6
{ succ BB6 }

{ pred BB3 }
BB5
r3 <- exp1
goto BB6
{ succ BB6 }

{ pred BB2, BB4, BB5 }
BB6
// etc.

The expression exp1 is hoistable to BB1, but BB4 and BB5 are not immediately
dominated by BB1, so gcse.c's code hoisting implementation never optimizes
this.


-- 


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