Page MenuHomePhabricator

[LVI] Make results independent of query order (WIP)
Needs ReviewPublic

Authored by nikic on Sat, Nov 9, 6:10 AM.

Details

Reviewers
reames
lebedev.ri
Summary

Related to D69686. Previously LVI broke cycles as they occurred, by assuming an overdefined result if pushBlockValue() failed. This means that the result depends on the query order, as this may start (and correspondingly break) the cycle at different points.

This patch proposes to instead break cycles at back-edges, so that the results computed by LVI are fixed by the control flow structure and do not depend on query order. We assume that the block value coming from the backedge is overdefined and only use any potential edge-local value in that case. This gives LVI a well-defined acyclic dependency graph.

This is a prototype implementation to get some feedback. The main problem is that right now, I'm aggressively clearing the backedge cache if any CFG change occurs. This might be expensive and it would be better to do more fine-grained updates. Not sure how hard that would be.

Another unfortunate bit is that we still need to check for cycles in pushBlockValue(), due to the degenerate case of unreachable basic blocks, which may contain self-referencing instructions.

Diff Detail