Page MenuHomePhabricator

[WIP!][Dominators] Add a tool for benchmarking the incremental updater

Authored by kuhar on Aug 18 2017, 2:10 PM.


NOTE: This is a *very* work-in-progress patch and I don't intend to commit it. Please ignore it.

A short braindump:
Benchmarking the DominatorTree batch updater is a bit difficult right now, because it doesn't get widely used. Profiling it directly produces just a lot of noise. The other problem is that the update sequences produces by LoopRotation and LoopUnswitching ten to be very short (<= 3), which won't be representative of other real-world uses.

My idea for benchmarking it is to create a new tool that reads bitcode files and turns them into new modules with IR emitted with the CFGBuilder, so that it's easy to randomly generate some update sequence and apply it on the CFG. It should be easy to add a command line parameter for specifying absolute and relative update sequence lengths, ratio of insertions to deletions, etc.

My initial benchmarks on CFGs and update sequences generated manually suggest that there isn't any obvious *static* scheduling for batch updates. This is kind of expected, as different permutations of updates affect the dynamic depth in dominator trees. Because of that, we need to find a way to estimate the intermediate depth in the domiantor tree at the update point. The general heuristic that seems to work fine in my test is to maximize the total depth where the updates start, meaning, we want to perform the updates as deep in the tree as possible. This should work by minimizing the chance of recomputing bigger subtrees, as the incremental algorithm performs tree updates that are bounded by the depth in the tree.
But at this point, I don't know how to do that, and I need more data too support my intuition and observe some properties of the incremental algorithm.

Diff Detail

Event Timeline

kuhar created this revision.Aug 18 2017, 2:10 PM
kuhar added a comment.Aug 18 2017, 2:30 PM

To make it more clear, the simplest dynamic scheduling that I'd expect to work somewhat reasonably would be to look ahead on the next N updates in the update sequence, and greedily pick the one that us lowest in the tree. (And N could be min(UpdatesLeft, SmallConstant = 64)).

grosser requested changes to this revision.Sep 24 2017, 12:23 AM

I mark this as requesting changes such that it does not appear in my "to-review" queue. Looking forward to see this evolve.

This revision now requires changes to proceed.Sep 24 2017, 12:23 AM
kuhar abandoned this revision.Jan 24 2018, 1:27 PM