Critical Edge Splitting

submited by

Style Pass

2023-01-31 07:30:03

An edge between basic blocks is considered a critical edge if the predecessor has multiple successors, and the successor has multiple predecessors.

Given the above control flow graph, we have one critical edge between BB0 and BB3. (BB0 has multiple successors, but BB2 only has only one predecessor so the edge between them is not critical. BB3 has multiple predecessors, but BB1 has only one successor so the edge between them is also not critical).

Because BB0 has multiple successors, it might not be correct for such code to execute at the end of BB0 when the branch to BB2 is taken. Because BB3 has multiple predecessors, it would also not be correct to insert the new code at the beginning of BB3 since it would execute should the incoming branch from BB1 be taken.

Let’s say you’d like to add instrumentation to existing code to track whether a branch is taken or not (to ascertain whether execution paths are covered by testing). That’s a boolean decision; taken or not. Sometimes a count is more helpful for the purposes of profiling, which lets you calculate how hot or cold an edge is relative to another. Such information might influence the relative ordering of basic blocks when linearizing the control flow graph or making decisions about whether to inline or even outline the contents of those basic blocks. Think about the control flow graph above. Where would you insert the counter update if you hadn’t split the critical edge?