Some compilers have utility functions that split critical edges in the control flow graph. I assume that this is not done as an optimization in itself, but rather to simplify other analyses and transformations. In what cases would splitting critical edges be useful?


An easy google search shows in Muchnick, Advanced Compiler Design & Implementation, Section 13.3 Partial-Redundancy Elimination, pp 407-408:

A key point in the algorithm is that it can be much more effective if the critical edges in the flowgraph have been split before the flow analysis is performed.

So the notion is useful to increase the efficiency of certain flow analyses in redudancy elimination, which aims to find portions of code with common sub-expressions and hoist them out into a single computation, which is facilitated in the absence of critical edges.

  • $\begingroup$ thanks for the answer. Can you please be more specific on how the flow analysis algorithm is simplified as a result of the splitting? $\endgroup$
    – zr.
    Oct 19 '16 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.