[IPSCCP] Fix a problem with removing labels in a switch with undef condition

[bjope]

Summary

Before removing basic blocks that ipsccp has considered as dead
all uses of the basic block label must be removed. That is done
by calling ConstantFoldTerminator on the users. An exception
is when the branch condition is an undef value. In such
scenarios ipsccp is using some internal assumptions regarding
which edge in the control flow that should remain, while
ConstantFoldTerminator don't know how to fold the terminator.

The problem addressed here is related to ConstantFoldTerminator's
ability to rewrite a 'switch' into a conditional 'br'. In such
situations ConstantFoldTerminator returns true indicating that
the terminator has been rewritten. However, ipsccp treated the
true value as if the edge to the dead basic block had been
removed. So the code for resolving an undef branch condition
did not trigger, and we ended up with assertion that there were
uses remaining when deleting the basic block.

For ipsccp it is important that the original terminator is kept
untouched by ConstantFoldTerminator when branching on undef values.
Otherwise the logic for which edge that should remain in case of
undef conditions will be messed up.
The solution is to add a parameter to ConstantFoldTerminator
to optionally restrict the folding to leave the terminator untouched
unless it can be folded into an unconditional branch.

[efriedma]

lib/Transforms/Scalar/SCCP.cpp

2020

Maybe it would be more straightforward here to figure out the valid successor using isEdgeFeasible(), and explicitly emit the unconditional branch we want, instead of calling ConstantFoldTerminator.

I mean, the patch works as-is, but adding more flags to commonly used APIs like ConstantFoldTerminator makes them more difficult to understand.

[bjope]

• Got rid of the changes in ConstantFoldTerminator.
• Now we force folding for indeterminate values before calling ConstantFoldTerminator (so now we only need to call ConstantFoldTerminator one time for the indeterminate case).

[bjope]

Removed a code comment uploaded by mistake in previous diff.

[fhahn]

LGTM

lib/Transforms/Scalar/SCCP.cpp

1891

This is an internal function, not sure if we need a doxygen comment here.

1895

one ; too much

1924

no need for explicit return here.

test/Transforms/SCCP/switch-undef-constantfoldterminator.ll

9

I would drop the reference to the line number in Value.cpp, as it is subject to change.

[fhahn]

It's probably worth waiting with committing until tomorrow, in case Eli has any more suggestions

[bjope]

Fixed some mistakes detected by Florian. Thanks alot for those comments!

[bjope]

lib/Transforms/Scalar/SCCP.cpp

2020

I got rid of the changes to ConstantFoldTerminator by always forcing the edge for the indeteminate case before calling ConstantFoldTerminator. Maybe not exactly what you meant by using isEdgeFeasible(), but it makes it possible to still reuse ConstantFoldTerminator for rewriting the terminator into an unconditional branch.

include/llvm/Transforms/Utils/Local.h

 
 /// If a terminator instruction is predicated on a constant value, convert it
 /// into an unconditional branch to the constant destination.
 /// This is a nontrivial operation because the successors of this basic block
 /// must have their PHI nodes updated.
 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
 /// conditions and indirectbr addresses this might make dead if
 /// DeleteDeadConditions is true.
+/// If \p OnlyFoldToUnconditional is true, then no partial simplifications are
+/// allowed. Either the terminator is folded to become unconditional, or no
+/// folding at all will be made.
 bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
                             const TargetLibraryInfo *TLI = nullptr,
-                            DomTreeUpdater *DTU = nullptr);
+                            DomTreeUpdater *DTU = nullptr,
+                            bool OnlyFoldToUnconditional = false);
+
 
 //===----------------------------------------------------------------------===//
 //  Local dead code elimination.
 //
 
 /// Return true if the result produced by the instruction is not used, and the
 /// instruction has no side effects.
 bool isInstructionTriviallyDead(Instruction *I,

lib/Transforms/Scalar/SCCP.cpp

for (BasicBlock &BB : F) {
     }
 
     if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
       if (!isa<UndefValue>(RI->getOperand(0)))
         ReturnsToZap.push_back(RI);
   }
 }
 
 bool llvm::runIPSCCP(
     Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI,
     function_ref<std::unique_ptr<PredicateInfo>(Function &)> getPredicateInfo) {
   SCCPSolver Solver(DL, TLI);
 
   // Loop over all functions, marking arguments to those with their addresses
   // taken or that are external as overdefined.
   for (Function &F : M) {
     if (F.isDeclaration())
       continue;
 
     Solver.addPredInfo(F, getPredicateInfo(F));
     // Determine if we can track the function's return values. If so, add the
for (Function &F : M) {
     Solver.MarkBlockExecutable(&F.front());
 
     // Assume nothing about the incoming arguments.
     for (Argument &AI : F.args())
       Solver.markOverdefined(&AI);
   }
 
   // Determine if we can track any of the module's global variables. If so, add
   // the global variables we can track to the solver's set of tracked global
   // variables.
   for (GlobalVariable &G : M.globals()) {
     G.removeDeadConstantUsers();
     if (canTrackGlobalVariableInterprocedurally(&G))
       Solver.TrackValueOfGlobalVariable(&G);
   }
 
   // Solve for constants.
for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
         // Grab the user and then increment the iterator early, as the user
         // will be deleted. Step past all adjacent uses from the same user.
         auto *I = dyn_cast<Instruction>(*UI);
         do { ++UI; } while (UI != UE && *UI == I);
 
         // Ignore blockaddress users; BasicBlock's dtor will handle them.
         if (!I) continue;
 
-        bool Folded = ConstantFoldTerminator(I->getParent());
+        bool Folded = ConstantFoldTerminator(I->getParent(),
+                                             false, nullptr, nullptr,
+                                             true /* OnlyFoldToUnconditional */);
         if (!Folded) {
           // If the branch can't be folded, we must have forced an edge
           // for an indeterminate value. Force the terminator to fold
           // to that edge.
           Constant *C;
           BasicBlock *Dest;
           if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
             Dest = SI->case_begin()->getCaseSuccessor();
             C = SI->case_begin()->getCaseValue();
           } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
             Dest = BI->getSuccessor(1);
             C = ConstantInt::getFalse(BI->getContext());
           } else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I)) {
             Dest = IBR->getSuccessor(0);
             C = BlockAddress::get(IBR->getSuccessor(0));
           } else {
             llvm_unreachable("Unexpected terminator instruction");
           }
           assert(Solver.isEdgeFeasible(I->getParent(), Dest) &&
                  "Didn't find feasible edge?");
           (void)Dest;
 
           I->setOperand(0, C);
-          Folded = ConstantFoldTerminator(I->getParent());
+          Folded = ConstantFoldTerminator(I->getParent(),
+                                          false, nullptr, nullptr,
+                                          true /* OnlyFoldToUnconditional */);
         }
         assert(Folded &&
               "Expect TermInst on constantint or blockaddress to be folded");
         (void) Folded;
       }
 
       // Finally, delete the basic block.
       F.getBasicBlockList().erase(DeadBB);

lib/Transforms/Utils/Local.cpp

 #define DEBUG_TYPE "local"
 
 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
 
 //===----------------------------------------------------------------------===//
 //  Local constant propagation.
 //
 
-/// ConstantFoldTerminator - If a terminator instruction is predicated on a
-/// constant value, convert it into an unconditional branch to the constant
-/// destination.  This is a nontrivial operation because the successors of this
-/// basic block must have their PHI nodes updated.
-/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
-/// conditions and indirectbr addresses this might make dead if
-/// DeleteDeadConditions is true.
 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
                                   const TargetLibraryInfo *TLI,
-                                  DomTreeUpdater *DTU) {
+                                  DomTreeUpdater *DTU,
+                                  bool OnlyFoldToUnconditional) {
   TerminatorInst *T = BB->getTerminator();
   IRBuilder<> Builder(T);
 
   // Branch - See if we are conditional jumping on constant
   if (auto *BI = dyn_cast<BranchInst>(T)) {
     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
     BasicBlock *Dest1 = BI->getSuccessor(0);
     BasicBlock *Dest2 = BI->getSuccessor(1);
for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
       // Found case matching a constant operand?
       if (i->getCaseValue() == CI) {
         TheOnlyDest = i->getCaseSuccessor();
         break;
       }
 
       // Check to see if this branch is going to the same place as the default
       // dest.  If so, eliminate it as an explicit compare.
-      if (i->getCaseSuccessor() == DefaultDest) {
+      if (i->getCaseSuccessor() == DefaultDest && !OnlyFoldToUnconditional) {
         MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
         unsigned NCases = SI->getNumCases();
         // Fold the case metadata into the default if there will be any branches
         // left, unless the metadata doesn't match the switch.
         if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) {
           // Collect branch weights into a vector.
           SmallVector<uint32_t, 8> Weights;
           for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
if (TheOnlyDest) {
       SI->eraseFromParent();
       if (DeleteDeadConditions)
         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
       if (DTU)
         DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
       return true;
     }
 
-    if (SI->getNumCases() == 1) {
+    if (SI->getNumCases() == 1 && !OnlyFoldToUnconditional) {
       // Otherwise, we can fold this switch into a conditional branch
       // instruction if it has only one non-default destination.
       auto FirstCase = *SI->case_begin();
       Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
           FirstCase.getCaseValue(), "cond");
 
       // Insert the new branch.
       BranchInst *NewBr = Builder.CreateCondBr(Cond,

test/Transforms/SCCP/switch-undef-constantfoldterminator.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -ipsccp -S | FileCheck %s
+
+; This test case used to end up like this:
+;
+;    While deleting: label %lor.rhs
+;    Use still stuck around after Def is destroyed:  br i1 undef, label %lor.rhs, label %land.end
+;    opt: ../lib/IR/Value.cpp:92: llvm::Value::~Value(): Assertion `use_empty() && "Uses remain when a value is destroyed!"' failed.
+;
+; due to ConstantFoldTerminator rewriting the switch into
+;
+;    br i1 undef, label %lor.rhs, label %land.end
+;
+; while SCCP implementation relied on the terminator to always be folded into
+; an unconditional branch when ConstantFoldTerminator returned true.
+
+define void @f4() {
+; CHECK-LABEL: define void @f4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = call i16 @f3(i16 undef)
+; CHECK-NEXT:    ret void
+;
+entry:
+  %call = call i16 @f3(i16 undef)
+  ret void
+}
+
+define internal i16 @f3(i16 %p1) {
+; CHECK-LABEL: define internal i16 @f3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LAND_END:%.*]]
+; CHECK:       land.end:
+; CHECK-NEXT:    ret i16 undef
+;
+entry:
+  switch i16 %p1, label %land.end [
+  i16 0, label %land.end
+  i16 1, label %lor.rhs
+  ]
+
+lor.rhs:
+  br label %land.end
+
+land.end:
+  ret i16 0
+}
+