[SimplifyCFG] produces incorrect callbr's

[nickdesaulniers]

Bugzilla Link	43222
Resolution	FIXED
Resolved on	Sep 09, 2019 02:01
Version	trunk
OS	Linux
Blocks	#4440 #41819
Attachments	z.ll, z2.ll
CC	@topperc,@zmodem,@nathanchance,@stephenhines

Extended Description

With the attached test case, and new verifier check from (https://reviews.llvm.org/D67196) I observe a failure in SimplifyCFG:

$ opt --simplifycfg z.ll -o /dev/null
Indirect label missing from arglist.
callbr void asm sideeffect "// XXX: ${0:l}", "X"(i8* blockaddress(@andy_test, %if.then))
to label %land.rhs.i [label %if.end]
in function andy_test
LLVM ERROR: Broken function found, compilation aborted!

the indirect label list [label %if.end].

Attaching z2.ll, which is the post-simplyifycfg-ed version that violates the invariant.

Looks like a simple phi is being replaced:

branch_test.exit: ; preds = %entry, %land.rhs.i
%0 = phi i1 [ true, %entry ], [ false, %land.rhs.i ]
br i1 %0, label %if.end, label %if.then

where the blockaddress of %if.then is being updated correctly, but the indirect label list is not.

[nickdesaulniers]

assigned to @nickdesaulniers

[nickdesaulniers]

One potentially larger looming issue I suspect is that BasicBlock::ReplaceAllUsesWith() updates the BlockAddress function arguments to callbr instructions, but it does not update the indirect destination list. On initial findings, that seems wrong. I don't know if the Use list is wrong, or what.

TryToSimplifyUncondBranchFromEmptyBlock() in llvm/lib/Transforms/Utils/Local.cpp seems suspect, too, but it seems that our invariants are already violated by the time the "critedge" is created.

[nickdesaulniers]

A quick fix is:

diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index 3a18b52a4de8..e409ea3a58ba 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -2210,7 +2210,8 @@ static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL,
if (RealDest == BB)
continue; // Skip self loops.
// Skip if the predecessor's terminator is an indirect branch.

• if (isa(PredBB->getTerminator()))

• if (isa(PredBB->getTerminator()) ||

•    isa<CallBrInst>(PredBB->getTerminator()))
   continue;
  

  // The dest block might have PHI nodes, other predecessors and other

I don't like the generated code though, so let's see if we can fix the optimization, rather than kneecap it.

[nickdesaulniers]

Setting the successor BasicBlock of a CallBrInst has a bug:

In FoldCondBranchOnPHI() in llvm/lib/Transforms/Utils/SimplifyCFG.cpp, we have:

2273 // Loop over all of the edges from PredBB to BB, changing them to branch
2274 // to EdgeBB instead.
2275 Instruction *PredBBTI = PredBB->getTerminator();
2276 for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i)
2277 if (PredBBTI->getSuccessor(i) == BB) {
2278 BB->removePredecessor(PredBB);
2279 PredBBTI->setSuccessor(i, EdgeBB);
2280 }

When BB is:

branch_test.exit: ; preds = %land.rhs.i, %entry
%0 = phi i1 [ true, %entry ], [ false, %land.rhs.i ]
br i1 %0, label %if.end, label %if.then

and PredBBTI is:

callbr void asm sideeffect "// XXX: ${0:l}", "X"(i8* blockaddress(@andy_test, %branch_test.exit))
to label %land.rhs.i [label %branch_test.exit]

PredBBTI has 2 successors; the first is the fallthrough BasicBlock, the second is the indirect jump destination. After executing PredBBTI->setSuccessor(i, EdgeBB); when i == 1, PredBBTI becomes:

callbr void asm sideeffect "// XXX: ${0:l}", "X"(i8* blockaddress(@andy_test, %branch_test.exit))
to label %land.rhs.i [label %if.end.critedge]

Oops! Invariant violated!

CallBrInst::setSuccessor() needs additional logic when an indirect jump destination is set to additionally update the BlockAddress Constant passed to the inline assembly.

[nickdesaulniers]

https://reviews.llvm.org/D67252

[zmodem]

https://reviews.llvm.org/D67252

That landed in r371262 and was merged to release_90 in r371376.