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.
