Page MenuHomePhabricator

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

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



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

Event Timeline

nikic created this revision.Nov 9 2019, 6:10 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 9 2019, 6:11 AM

Any feedback on the general idea here?

nikic updated this revision to Diff 233852.Dec 13 2019, 12:39 PM

Rebase and use Optional.