This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by nikic on Nov 9 2019, 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

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.

lebedev.ri resigned from this revision.Apr 8 2020, 11:46 PM

No idea who is comfortable/qualified doing LVI reviews, but that isn't me.

nikic abandoned this revision.Aug 9 2023, 6:09 AM

This is still a problem, but the solution isn't great and I don't plan to work on this in the near future.

Herald added a project: Restricted Project. · View Herald TranscriptAug 9 2023, 6:09 AM
Herald added a subscriber: StephenFan. · View Herald Transcript