Page MenuHomePhabricator

StructurizeCFG: Fix broken backedge detection

Authored by arsenm on Dec 27 2017, 5:57 PM.



The work order was changed in r228186 from SCC order
to RPO with an arbitrary sorting function. The sorting
function attempted to move inner loop nodes earlier. This
was was apparently relying on an assumption that every block
in a given loop / the same loop depth would be seen before
visiting another loop. In the broken testcase, a block
outside of the loop was encountered before moving onto
another block in the same loop. The testcase would then
structurize such that one blocks unconditional successor
could never be reached.

Revert to RPO for the analysis phase. This fixes
detecting edges as backedges that aren't really.

The processing phase does use another visited set, and
I'm unclear on whether the order there is as important.
An arbitrary order doesn't work, and triggers some infinite
loops. The reversed RPO list seems to work and is closer
to the order that was used before, minus the arbitary
custom sorting.

A few of the changed tests now produce smaller code,
and a few are slightly worse looking.

Diff Detail

Event Timeline

arsenm created this revision.Dec 27 2017, 5:57 PM

Reading the old code you are replacing I don't feel like I understand the graph theory behind the algorithm.

Reading the new code and analyzeLoops, et al

It is true the way this is structured requires RPO to detect back edges properly, but FWIW: it's very unclear to me why it's done this way.
The visitation order is unrelated to the back-edgeness, despite what analyzeLoops thinks.

In particular, an edge x->y is a backedge in the CFG if rpo[x] >= rpo[y].
Nothing else is necessary. The visitation testing, etc, is redundant. It just discovers this fact (and makes you require visitation in RPO order). You could create the set of backedges directly from the RPO computation you do, and in fact, during it, if you wanted to. It is already computing backedges as it is visiting.

This may or may not be what you want to consider loops. In particular, it is not maximal (even in the current code). SCCs are maximal, and include cycles that are irreducible.

The trivial example cfg being:

  /    \
 /      \
b  <- >  c

(IE a->b, a->c, b->c, c->b)

b and c form a cycle, and an SCC.
whether you detect b->c or c->b as the backedge is a coin flip depending on whether you visit left subtree or right subtree first.
It is not a natural loop.

You would currently detect this as some form of loop, but again, most of the algorithms used here do not look like the ones i'm familiar with (I feel like i can find a ton of edge cases in it).

In any case, it is definitely true that RPO is required for backedge detection as the rest of this code is currently written.

You would currently detect this as some form of loop, but again, most of the algorithms used here do not look like the ones i'm familiar with (I feel like i can find a ton of edge cases in it).

There are definitely a lot of strange things going on here and I don't really understand how this manages to work at all. I think part of the problem was using RegionInfo for this was a mistake, and this should probably be rewritten to not depend on it. For example because the pass itself only sees one region at a time, it won't even see the example you posted as something it can try to process. There isn't a well formed single exit region, so I think the pass will just see the function top level region and bail out. I've variants of the same problem pop up from time to time. Fundamentally using an analysis to look at well formed regions probably doesn't make sense for a pass which is trying to produce well formed regions. I've also been surprised by some of the visitation order decisions for the various graph iterators with RegionNode compared to the same orders over the entire function. The various places that need to differently handle subregion nodes vs. individual blocks also seems more confusing to me.

arsenm updated this revision to Diff 128428.Jan 2 2018, 9:18 AM

Don't have a separate loop discover backedges, and avoid needing to reverse the vector. Still uses the visited set, since the alternative would be to somehow track the visit number which is essentially the same thing.

arsenm added a comment.Jan 3 2018, 9:58 AM

ping, this should make it into the release

This revision is now accepted and ready to land.Jan 3 2018, 10:01 AM
arsenm closed this revision.Jan 3 2018, 10:46 AM