Schedule approximation for clustering and showing the control-flow graph is an expensive computation that can take as much time as computing the layout of a graph and rendering it.

A preliminary study on a large graph (attached) shows that the majority of schedule approximation time is spent pre-computing the common dominators (getCommonDominator(b1, b2)) of all pairs of blocks, while the core of the scheduling algorithm (scheduleLatest()) only typically requires knowing a small subset of these.

Calling getCommonDominator() directly in scheduleLatest() instead of fetching pre-computed results speeds up the schedule approximation of the large graph attached by around 20x, from ~4s to ~200ms. This is because the graph has 1309 blocks, so pre-computation performs 1713481 calls to getCommonDominator() (no. blocks x no. blocks), but then it is only used 14952 times by scheduleLatest().

In the worst case, scheduleLatest() performs (no. nodes x no. nodes) calls to getCommonDominator(), but in practice it is closer to no. nodes only, because the graph is very sparse - nodes tend to have few successors.