[SCCP] Don't use markForcedConstant on branch conditions.

[efriedma]

Summary

It's more aggressive than we need to be, and leads to strange workarounds in other places like call return value inference. Instead, just directly mark an edge viable.

Tests by Florian Hahn.

[fhahn]

I just collected stats with this patch on the test-suite with LTO. The only difference in stats counters across IPSCCP and SCCP is that with this patch, we get 2 more instructions eliminated in SCCP (sccp.NumInstRemoved).

Thinking about it, I am not too surprised that the impact of not forcing the condition to false is tiny. IIUC the only benefit would be if our guess (condition false) is actually true and the condition is used somewhere in the else branch. As mentioned in the discussion at D49384, this helps us to avoid obscure bugs caused by back-propagating information to the condition and resolves D49384 and D48327. I think we could come back to actually distinguishing between dead code and an LLVM "undef" value once there is a bigger need, e.g. because IPSCCP became more powerful

lib/Transforms/Scalar/SCCP.cpp

1594

markEdgeExecutable also checks if the edge is already known to be feasible. Maybe it's worth changing markEdgeExecutable to return false, when a unfeasible edge is passed?

[efriedma]

Cleaned up, added some tests.

[davide]

LGTM modulo minor. Thanks.

lib/Transforms/Scalar/SCCP.cpp

1987–1997

do you need the else here? IIRC they are all mutually exclusive.

[efriedma]

lib/Transforms/Scalar/SCCP.cpp

1987–1997

Just trying to make clear that this isn't an exhaustive list of possible terminator instructions (there are also exception-handling instructions, but we always treat their successors as feasible).

[davide]

lib/Transforms/Scalar/SCCP.cpp

1987–1997

OK, makes sense.

[fhahn]

LGTM, thanks!

test/Transforms/SCCP/ipsccp-paramstate-forcedconst.ll

1 ↗

(On Diff #156199)

nit: forcedconstant is not involved any more, maybe we should drop it from the name to avoid confusion or combine it with return-zapped.ll to something like ipsccp-branch-condition-unknown-initially.ll?

test/Transforms/SCCP/return-zapped.ll

46 ↗

(On Diff #156199)

Is this test valuable with the new approach?

[efriedma]

test/Transforms/SCCP/ipsccp-paramstate-forcedconst.ll

1 ↗

(On Diff #156199)

K

test/Transforms/SCCP/return-zapped.ll

9 ↗

(On Diff #156199)

I'll fix this comment before merging.

46 ↗

(On Diff #156199)

I don't think it does any harm to keep it.

lib/Transforms/Scalar/SCCP.cpp

if (auto *BI = dyn_cast<BranchInst>(TI)) {
       // false.
       if (isa<UndefValue>(BI->getCondition())) {
         BI->setCondition(ConstantInt::getFalse(BI->getContext()));
         markEdgeExecutable(&BB, TI->getSuccessor(1));
         return true;
       }
 
       // Otherwise, it is a branch on a symbolic value which is currently
-      // considered to be undef.  Handle this by forcing the input value to the
-      // branch to false.
-      markForcedConstant(BI->getCondition(),
-                         ConstantInt::getFalse(TI->getContext()));
+      // considered to be undef.  Make sure some edge is executable, so a
+      // branch on "undef" always flows somewhere.
+      // FIXME: Distinguish between dead code and an LLVM "undef" value.
+      BasicBlock *DefaultSuccessor = TI->getSuccessor(1);
+      if (!KnownFeasibleEdges.count({&BB, DefaultSuccessor})) {
+        markEdgeExecutable(&BB, DefaultSuccessor);
         return true;
       }
 
+      continue;
+    }
+
    if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
       // Indirect branch with no successor ?. Its ok to assume it branches
       // to no target.
       if (IBR->getNumSuccessors() < 1)
         continue;
 
       if (!getValueState(IBR->getAddress()).isUnknown())
         continue;
 
       // If the input to SCCP is actually branch on undef, fix the undef to
       // the first successor of the indirect branch.
       if (isa<UndefValue>(IBR->getAddress())) {
         IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
         markEdgeExecutable(&BB, IBR->getSuccessor(0));
         return true;
       }
 
       // Otherwise, it is a branch on a symbolic value which is currently
-      // considered to be undef.  Handle this by forcing the input value to the
-      // branch to the first successor.
-      markForcedConstant(IBR->getAddress(),
-                         BlockAddress::get(IBR->getSuccessor(0)));
+      // considered to be undef.  Make sure some edge is executable, so a
+      // branch on "undef" always flows somewhere.
+      // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
+      // we can assume the branch has undefined behavior instead.
+      BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
+      if (!KnownFeasibleEdges.count({&BB, DefaultSuccessor})) {
+        markEdgeExecutable(&BB, DefaultSuccessor);
         return true;
       }
 
+      continue;
+    }
+
     if (auto *SI = dyn_cast<SwitchInst>(TI)) {
       if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown())
         continue;
 
       // If the input to SCCP is actually switch on undef, fix the undef to
       // the first constant.
       if (isa<UndefValue>(SI->getCondition())) {
         SI->setCondition(SI->case_begin()->getCaseValue());
         markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
         return true;
       }
 
-      markForcedConstant(SI->getCondition(), SI->case_begin()->getCaseValue());
+      // Otherwise, it is a branch on a symbolic value which is currently
+      // considered to be undef.  Make sure some edge is executable, so a
+      // branch on "undef" always flows somewhere.
+      // FIXME: Distinguish between dead code and an LLVM "undef" value.
+      BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor();
+      if (!KnownFeasibleEdges.count({&BB, DefaultSuccessor})) {
+        markEdgeExecutable(&BB, DefaultSuccessor);
         return true;
       }
+
+      continue;
+    }
   }
 
   return false;
 }
 
 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
   Constant *Const = nullptr;
   if (V->getType()->isStructTy()) {
for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
         // 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());
+        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;
+          if (SwitchInst *SI = dyn_cast<SwitchInst>(I))
+            C = SI->case_begin()->getCaseValue();
+          else if (BranchInst *BI = dyn_cast<BranchInst>(I))
+            C = ConstantInt::getFalse(BI->getContext());
+          else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I))
+            C = BlockAddress::get(IBR->getSuccessor(0));
+          else
+            llvm_unreachable("Unexpected terminator instruction");
+
+          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);
     }

test/Transforms/SCCP/ipsccp-phi-one-pred-dead.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -ipsccp | FileCheck %s
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @test() {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label %Flow5.pre
 ; CHECK:       Flow6:
-; CHECK-NEXT:    br label %end2
+; CHECK-NEXT:    br i1 undef, label %end1, label %end2
 ; CHECK:       Flow5.pre:
 ; CHECK-NEXT:    br label %Flow5
 ; CHECK:       Flow5:
 ; CHECK-NEXT:    br label %Flow6
+; CHECK:       end1:
+; CHECK-NEXT:    unreachable
 ; CHECK:       end2:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br i1 true, label %Flow5.pre, label %Flow5.pre.unreachable
 
 Flow5.pre.unreachable:
   br label %Flow5