Page MenuHomePhabricator

[SelectionDAG] Eliminate exponential behavior in WalkChainUsers

Authored by timshen on Jan 29 2016, 3:40 PM.



This patch fixes a potential exponential behavior due to no memoization in a DFS.

For example, consider such a graph:
ret -> a0, ret -> b0,
a0 -> a1, a0-> b1, b0 -> a1, b0 -> b1,
a1 -> a2, a1-> b2, b1 -> a2, b1 -> b2,
a2 -> a3, a2-> b3, b2 -> a3, b2 -> b3,

If this DAG has n layers, the all paths WalkChainUsers will walk through is O(2^n); after memoization it will be O(n).

There is no functional change.

Diff Detail

Event Timeline

timshen updated this revision to Diff 46443.Jan 29 2016, 3:40 PM
timshen retitled this revision from to [SelectionDAG] Eliminate exponential behavior in WalkChainUsers.
timshen updated this object.
timshen added reviewers: resistor, echristo, iteratee.
timshen updated this object.Jan 29 2016, 3:43 PM
timshen added a subscriber: llvm-commits.
resistor accepted this revision.Jan 29 2016, 4:05 PM
resistor edited edge metadata.

Functionality LGTM. I would add a comment at the use site of TokenFactorResult to point out that the walk is being memoized.

This revision is now accepted and ready to land.Jan 29 2016, 4:05 PM
timshen updated this revision to Diff 46475.Jan 30 2016, 1:32 PM
timshen edited edge metadata.

Updated comments.

Also use the DenseMap iterator correctly.