[Bug tree-optimization/57972] New: Statement sinking algorithm should just be replaced with GCM algorithm's late scheduler

[Bug tree-optimization/57972] New: Statement sinking algorithm should just be replaced with GCM algorithm's late scheduler

[dberlin at gcc dot gnu.org]

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

            Bug ID: 57972
           Summary: Statement sinking algorithm should just be replaced
                    with GCM algorithm's late scheduler
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dberlin at gcc dot gnu.org

The store sinking algorithm in tree-ssa-sink.c has grown to the point where it
is *almost*, but not exactly, equivalent to the GCM's schedule_late phase
algorithm presented by Cliff Click in PLDI '95
(http://www.cs.washington.edu/education/courses/cse501/06wi/reading/click-pldi95.pdf)


The current algorithm is basically:


For each bb in post-dominator order:
  For each statement in reverse:
   find sink location using nearest common dominators of users.
   compute validity
   move to sink location

This requires computing post dominators, among other things.

The GCM algorithm is, basically:

FOr each unmovable instruction I
  mark I as pinned
  I.visit = true
  for each use U of I
    schedule_late (U)

For every other instruction I
  schedule_late (I) 


schedule_late is essentially the same as statement_sink_location + movement,
with the different that it recursively calls itself to on the users to move
them first.

//Find latest legal block for instruction i
Schedule_Late( instruction i ) {
  if i.visit = True then
  return;
  i.visit:= True;
  Block lca = empty
  forall uses y of i do {
    Schedule_Late( y );
    Block use := y.block;
    if y is a PHI then {
     // Reverse dependence edge from i to y
    Pick j so that the jth input of y is i
    // Use matching block from CFG
    use := y.block.CFG_pred[j];
    }
 lca := Find_LCA( lca, use );
  }
// You can place i in lca.
}

This should do slightly better than GCC's algorithm, and not require computing
postdominators explicitly.

The LCA computation performed is equivalent to using nearest_common_dominator.

[Bug tree-optimization/57972] Statement sinking algorithm should just be replaced with GCM algorithm's late scheduler

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
postdominator compute isn't exactly expensive.  Elsewhere we discussed that
SSU-PRE (partial dead code elimination, PRE on the reverse data dependence
graph) would be the appropriate thing to implement.