Graph: Use Semi-NCA algorithm in compute_immediate_dominators

[emmanuel099]

The Semi-NCA algorithm is described in: Linear-Time Algorithms for Dominators and Related Problems https://www.cs.princeton.edu/research/techreps/TR-737-05

This algorithm drastically improves the performance of compute_immediate_dominators as shown in the following benchmark.

The graph shows the execution time of the SSA transformation (which requires the immediate dominators) for a small single-loop program. The control flow graph is obtained by unrolling the loop k times (roughly speaking: duplicating the loop body k times and adding additional CFG edges to obtain a loop-free program). The resulting CFG has 8+k*2 basic blocks, meaning that we measure the execution time of the SSA transformation of 8+k*2 basic blocks.

For k=150:

• master takes about 52 seconds
• master + optimized predecessors (https://github.com/falconre/falcon/pull/76) takes about 20 seconds
• SEMI-NCA takes about 19 milliseconds

[endeav0r]

I see the amazing number of PRs. I will set time aside this weekend to get to them.