Remove many restrictions for identifying jump threads across backedges

It's amazing what 10 years away from a hunk of code will do...

So we've long had an arbitrary restriction in the jump thread 
identification code which made it very conservative when searching for 
threading opportunities once it encountered a back edge.

I've always known the problem was pollution of the tables with 
equivalences that were not valid once we cross the backedge.  But I'd 
never *really* looked at the problem.  I'd just had a sneaking suspicion 
the problems were related to the equivalences we record for the 
true/false arms of conditionals, PHIs and maybe other lurkers.

So for example, if we have a PHI

x2 = PHI (x0 (bb2), x1 (bb3));
[ ... ]
x1 = <whatever>

Where the incoming edge from bb3 is the backedge.  We will record a 
temporary equivalence x2 = x1.  Once x1 gets reassigned, we can no 
longer use that equivalence.

So we record in bitmaps the PHI arg of any PHI nodes that are used to 
create equivalences and the LHS of PHI nodes into another bitmap.  We 
only do this after traversing a backedge.

If we see an assignment to anything recorded in the bitmap for the PHI 
arg names, then we iterate over the recorded LHS names to see if any are 
currently equivalent to the RHS that just changed.  Obviously if such a 
situation is found, we eliminate the equivalence.  This is probably 
somewhat imprecise, but it's good enough.

We also have problems with expressions in the hash tables.  These are 
pretty trivial to solve -- the hash tables are only used by the SIMPLIFY 
callback.  Thus, we can just use a dummy SIMPLIFY callback once we've 
passed a backedge in the CFG.

Finally, for assignments that set a SSA_NAME to a value that isn't 
particularly useful, we need to record *something* in the equivalence 
tables (a NULL_TREE is good).  That effectively invalidates any 
equivalences with that name.  This is useful if we had used a 
conditional to derive a single point range for an SSA_NAME but the 
SSA_NAME's assignment statement doesn't provide such range precision.

This patch has bootstrapped and tested in various forms over the last 
couple weeks.  However, I made some simplifications late tonight and 
thus it needs to go through another spin.

Bootstrapped, regression test is in progress.  Will commit in the AM if 
everything is clean and a final once-over doesn't cause something to 
jump out as wrong.

Onwards to stage3 bugfixing :-)

Jeff
* tree-ssa-threadedge.c (record_temporary_equivalence): Handle
	NULL for RHS, which we used to invalidate equivalences.
	(record_temporary_equivalences_from_phis): New bitmap arguments
	and a boolean indicating if we have passed a backedge.  If we
	have passed a backedge, then set the appropriate bit in the
	bitmaps for the SRC & DEST of PHIs creating equivalences.
	(invalidate_equivalences, dummy_simplify): New functions.
	(cond_arg_set_in_b): Remove.
	(record_temporary_equivalences_from_stmts_at_dest): New bitmap
	arguments and a boolean indicating if we have passed a backedge.
	If we have passed a backedge, then perform invalidations as
	needed.
	(thread_around_empty_blocks): If we have seen a backedge, then
	use the dummy simplify routine.
	(thread_through_normal_block): Likewise.  Pass bitmaps and
	backedge status to children.  Do not pessimize so much when
	traversing backedges in the CFG.
	(thread_across_edge): Manage the SRC_MAP/DST_MAP bitmaps.
	If we have seen a backedge, then use the dummy simplify routine.
	Do not pessimize so much when traversing backedges.

Remove many restrictions for identifying jump threads across backedges

Commit Message

Comments

Patch