[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 ↗

(On Diff #165972)

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 ↗

(On Diff #166080)

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

1895 ↗

(On Diff #166080)

one ; too much

1924 ↗

(On Diff #166080)

no need for explicit return here.

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

8 ↗

(On Diff #166080)

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 ↗

(On Diff #165972)

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.

llvm/trunk/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);
   }
 }
 
+// Update the condition for terminators that are branching on indeterminate
+// values, forcing them to use a specific edge.
+static void forceIndeterminateEdge(Instruction* I, SCCPSolver &Solver) {
+  BasicBlock *Dest = nullptr;
+  Constant *C = nullptr;
+  if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
+    if (!isa<ConstantInt>(SI->getCondition())) {
+      // Indeterminate switch; use first case value.
+      Dest = SI->case_begin()->getCaseSuccessor();
+      C = SI->case_begin()->getCaseValue();
+    }
+  } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
+    if (!isa<ConstantInt>(BI->getCondition())) {
+      // Indeterminate branch; use false.
+      Dest = BI->getSuccessor(1);
+      C = ConstantInt::getFalse(BI->getContext());
+    }
+  } else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I)) {
+    if (!isa<BlockAddress>(IBR->getAddress()->stripPointerCasts())) {
+      // Indeterminate indirectbr; use successor 0.
+      Dest = IBR->getSuccessor(0);
+      C = BlockAddress::get(IBR->getSuccessor(0));
+    }
+  } else {
+    llvm_unreachable("Unexpected terminator instruction");
+  }
+  if (C) {
+    assert(Solver.isEdgeFeasible(I->getParent(), Dest) &&
+           "Didn't find feasible edge?");
+    (void)Dest;
+
+    I->setOperand(0, C);
+  }
+}
+
+
 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) {
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;
 
+        // If we have forced an edge for an indeterminate value, then force the
+        // terminator to fold to that edge.
+        forceIndeterminateEdge(I, Solver);
         bool Folded = ConstantFoldTerminator(I->getParent());
-        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());
-        }
         assert(Folded &&
               "Expect TermInst on constantint or blockaddress to be folded");
         (void) Folded;
       }
 
       // Finally, delete the basic block.
       F.getBasicBlockList().erase(DeadBB);
     }

llvm/trunk/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: 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
+}
+