New user self-registration is disabled due to spam. For an account please email bugs-admin@lists.llvm.org with your e-mail address and full name.

Bug 43222 - [SimplifyCFG] produces incorrect callbr's
Summary: [SimplifyCFG] produces incorrect callbr's
Status: RESOLVED FIXED
Alias: None
Product: libraries
Classification: Unclassified
Component: Transformation Utilities (show other bugs)
Version: trunk
Hardware: PC Linux
: P enhancement
Assignee: Nick Desaulniers
URL:
Keywords:
Depends on:
Blocks: 4068 release-9.0.0
  Show dependency tree
 
Reported: 2019-09-04 18:31 PDT by Nick Desaulniers
Modified: 2019-09-09 02:01 PDT (History)
5 users (show)

See Also:
Fixed By Commit(s):


Attachments
z.ll (865 bytes, text/plain)
2019-09-04 18:31 PDT, Nick Desaulniers
Details
z2.ll (642 bytes, text/plain)
2019-09-04 18:31 PDT, Nick Desaulniers
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Nick Desaulniers 2019-09-04 18:31:28 PDT
Created attachment 22471 [details]
z.ll

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.
Comment 1 Nick Desaulniers 2019-09-04 18:31:44 PDT
Created attachment 22472 [details]
z2.ll
Comment 2 Nick Desaulniers 2019-09-05 09:19:04 PDT
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.
Comment 3 Nick Desaulniers 2019-09-05 09:29:10 PDT
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<IndirectBrInst>(PredBB->getTerminator()))
+    if (isa<IndirectBrInst>(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.
Comment 4 Nick Desaulniers 2019-09-05 10:40:08 PDT
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.
Comment 5 Nick Desaulniers 2019-09-05 18:24:13 PDT
https://reviews.llvm.org/D67252
Comment 6 Hans Wennborg 2019-09-09 02:01:47 PDT
(In reply to Nick Desaulniers from comment #5)
> https://reviews.llvm.org/D67252

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