Decrease Control Dependency complexity

Created by: cargaji

The current control dependence algorithm has a polynomial complexity, when there exist algorithms linear w. r. t. the number of edges of the graph. The postdominator tree can be built to represent the postdomination property between two edges of a graph, and so it can be easily queried.

This issue could be edited, adding further explanations of the algorithm as we understand it.

Further reading:

• Slides from university courses on the topic: slides1, slides2, slides explaining the (post)dominator tree.
• Paper on the topic (explains the history and optimizations of the algorithm).
• Wiki page on dominator (the opposite property, related the the start instead of the end).