Page MenuHomePhabricator

[WIP!][Dominators] Collect tree construction and update statistics

Authored by kuhar on Aug 18 2017, 11:15 AM.


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

Short braindump:
The main problem with measuring performance of the incremental algorithm is that it is implemented entirely in a header file, inside a class template. A solution to that would be to just insert some timer calls and collect total elapsed times during update function calls, but that's a rather hacky solution.
A better measure of the cost of dominator tree construction and updates is the number of nodes visited during DFS walks, which has a nice property of being free of noise, which is not case with measuring just the execution time. In my local tests, counting visited nodes showed to correlate quite well with execution time.

To collect those statistics, I wanted to use the Statictic class, but the problem is that is requires to be declared as a global, so I decided to put it in lib/IR/DominatorTree.cpp. Now, it turns out, that there is also problem with static initialization order of Statistics and Timers when both try to produce json output. If Statistics get initialized first, they print timers as json upon destruction, but when opposite happens, Timers only print themselves in a tabular format, and then Statistics print themselves as json. The permanent fix for that would be to emit Statistics and Timers as separate Json objects and to make them not know about each other (too remove the dependency cycle).

Diff Detail

Event Timeline

kuhar created this revision.Aug 18 2017, 11:15 AM
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