Page MenuHomePhabricator

BreakCriticalEdges: bail if loop-simplify form requested for CallBr terminated BB
Needs ReviewPublic

Authored by nickdesaulniers on Sep 28 2020, 11:43 AM.

Details

Summary

Otherwise we'll fail the assertion in SplitBlockPredecessors() related
to splitting the edges from CallBr's.

Fixes: https://github.com/ClangBuiltLinux/linux/issues/1161

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptSep 28 2020, 11:43 AM
nickdesaulniers requested review of this revision.Sep 28 2020, 11:43 AM
void added a comment.Sep 30 2020, 4:34 PM

I believe that a critical edge may be split on the default path, but not the indirect path.

I believe that a critical edge may be split on the default path, but not the indirect path.

I don't think https://github.com/llvm/llvm-project/commit/2fe457690da0fc38bc7f9f1d0aee2ba6a6a16ada made a similar distinction?

I think if I add a bool CallBrInst::isIndirectDest(BasicBlock&); method, I would be able to use that here and in the above cases linked without regressing the test case added in the above link.

The concept of splitting a critical edge is still relatively new to me; any thoughts on *why* it would not be ok to split a critical branch of an indirect-like jump?

(oh, I never git add'ed my test case, let me do so now).

  • add test case
llvm/test/CodeGen/PowerPC/loop-reduce-callbr.ll
1

is there a better way to express: "this should not trip an assertion build?"

5

TODO(Nick): delete

The concept of splitting a critical edge is still relatively new to me; any thoughts on *why* it would not be ok to split a critical branch of an indirect-like jump?

The problem has to do with blockaddress.

For normal branches, splitting an edge is usually straightforward: you just introduce a new block that branches to the original block, and then you rewrite the branch in the predecessor. But suppose you have a block with two indirectbr predecessors, and you want to split the edge. In that case, the "rewrite the branch" step doesn't work: you can't rewrite the address argument to the indirectbr. (Or at least, you can't without performing some invasive rewrite like indirectbr->switch lowering.)

efriedma added inline comments.Sep 30 2020, 6:08 PM
llvm/test/CodeGen/PowerPC/loop-reduce-callbr.ll
1

Just running opt will automatically check the exit code, so this works. Generally you'd want to add a few CHECK lines to ensure loop-reduce is actually doing what you expect it to, though, so the test doesn't bitrot.

void added a comment.Sep 30 2020, 7:18 PM

The concept of splitting a critical edge is still relatively new to me; any thoughts on *why* it would not be ok to split a critical branch of an indirect-like jump?

The problem has to do with blockaddress.

For normal branches, splitting an edge is usually straightforward: you just introduce a new block that branches to the original block, and then you rewrite the branch in the predecessor. But suppose you have a block with two indirectbr predecessors, and you want to split the edge. In that case, the "rewrite the branch" step doesn't work: you can't rewrite the address argument to the indirectbr. (Or at least, you can't without performing some invasive rewrite like indirectbr->switch lowering.)

Correkt. We had a long discussion during the original implementation. I eventually relented, because I couldn't figure out a way to implement it without making the code unbearably horrible.

The best way to think about critical edges is to imagine trying to resolve a PHI node in block BB. The PHI node is a pseudo instruction, which has to become a concrete instruction during code gen. Let's take a simple case where the value is an immediate: 42 on branch A (from predecessor P1) and 37 on branch B (from predecessor P2), and further that the result of the PHI node is some register rN. When resolving the PHI node, you'll push rN <- 42 to the bottom of P1 and rN <- 37 to the bottom of P2. Nice!

Now if you have critical edges, things get messy. You can no longer push rN <- 42 and rN <- 37 into the predecessor blocks, because rN may be used for another value on edges not going to BB. In this case, we "split" the critical edge. I.e. we create an empty block between P1 and BB on edge A and another between P2 and BB on edge B. This provides us with a place to insert the rN <- 42 and rN <- 37 instructions respectively.

void added a comment.Sep 30 2020, 7:23 PM

I believe that a critical edge may be split on the default path, but not the indirect path.

I don't think https://github.com/llvm/llvm-project/commit/2fe457690da0fc38bc7f9f1d0aee2ba6a6a16ada made a similar distinction?

Yeah. I made an error there...

I think if I add a bool CallBrInst::isIndirectDest(BasicBlock&); method, I would be able to use that here and in the above cases linked without regressing the test case added in the above link.

It should be enough that the block isn't the default destination. (Though recent bug reports seem troubling for this.)

I don't know if it's important enough to allow splitting default edges right now. It may be okay to wait.