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

(On Diff #155792)

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

1965–1975 ↗

(On Diff #156199)

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

[efriedma]

lib/Transforms/Scalar/SCCP.cpp

1965–1975 ↗

(On Diff #156199)

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

1965–1975 ↗

(On Diff #156199)

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.

llvm/trunk/lib/Transforms/Scalar/SCCP.cpp

public:
   /// method should be use to handle this.  If this returns true, the solver
   /// should be rerun.
   bool ResolvedUndefsIn(Function &F);
 
   bool isBlockExecutable(BasicBlock *BB) const {
     return BBExecutable.count(BB);
   }
 
+  // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
+  // block to the 'To' basic block is currently feasible.
+  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
+
   std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const {
     std::vector<LatticeVal> StructValues;
     auto *STy = dyn_cast<StructType>(V->getType());
     assert(STy && "getStructLatticeValueFor() can be called only on structs");
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       auto I = StructValueState.find(std::make_pair(V, i));
       assert(I != StructValueState.end() && "Value not in valuemap!");
       StructValues.push_back(I->second);
LatticeVal &getStructValueState(Value *V, unsigned i) {
     }
 
     // All others are underdefined by default.
     return LV;
   }
 
   /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
   /// work list if it is not already executable.
-  void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
+  bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
     if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
-      return;  // This edge is already known to be executable!
+      return false;  // This edge is already known to be executable!
 
     if (!MarkBlockExecutable(Dest)) {
       // If the destination is already executable, we just made an *edge*
       // feasible that wasn't before.  Revisit the PHI nodes in the block
       // because they have potentially new operands.
       LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
                         << " -> " << Dest->getName() << '\n');
 
       for (PHINode &PN : Dest->phis())
         visitPHINode(PN);
     }
+    return true;
   }
 
   // getFeasibleSuccessors - Return a vector of booleans to indicate which
   // successors are reachable from a given terminator instruction.
   void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs);
 
-  // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
-  // block to the 'To' basic block is currently feasible.
-  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
-
   // OperandChangedState - This method is invoked on all of the users of an
   // instruction that was just changed state somehow.  Based on this
   // information, we need to update the specified user of this instruction.
   void OperandChangedState(Instruction *I) {
     if (BBExecutable.count(I->getParent()))   // Inst is executable?
       visit(*I);
   }
 
void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
 
   LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
   llvm_unreachable("SCCP: Don't know how to handle this terminator!");
 }
 
 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 // block to the 'To' basic block is currently feasible.
 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
-  assert(BBExecutable.count(To) && "Dest should always be alive!");
-
-  // Make sure the source basic block is executable!!
-  if (!BBExecutable.count(From)) return false;
-
-  // Check to make sure this edge itself is actually feasible now.
-  TerminatorInst *TI = From->getTerminator();
-  if (auto *BI = dyn_cast<BranchInst>(TI)) {
-    if (BI->isUnconditional())
-      return true;
-
-    LatticeVal BCValue = getValueState(BI->getCondition());
-
-    // Overdefined condition variables mean the branch could go either way,
-    // undef conditions mean that neither edge is feasible yet.
-    ConstantInt *CI = BCValue.getConstantInt();
-    if (!CI)
-      return !BCValue.isUnknown();
-
-    // Constant condition variables mean the branch can only go a single way.
-    return BI->getSuccessor(CI->isZero()) == To;
-  }
-
-  // Unwinding instructions successors are always executable.
-  if (TI->isExceptional())
-    return true;
-
-  if (auto *SI = dyn_cast<SwitchInst>(TI)) {
-    if (SI->getNumCases() < 1)
-      return true;
-
-    LatticeVal SCValue = getValueState(SI->getCondition());
-    ConstantInt *CI = SCValue.getConstantInt();
-
-    if (!CI)
-      return !SCValue.isUnknown();
-
-    return SI->findCaseValue(CI)->getCaseSuccessor() == To;
-  }
-
-  // In case of indirect branch and its address is a blockaddress, we mark
-  // the target as executable.
-  if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
-    LatticeVal IBRValue = getValueState(IBR->getAddress());
-    BlockAddress *Addr = IBRValue.getBlockAddress();
-
-    if (!Addr)
-      return !IBRValue.isUnknown();
-
-    // At this point, the indirectbr is branching on a blockaddress.
-    return Addr->getBasicBlock() == To;
-  }
-
-  LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << *TI << '\n');
-  llvm_unreachable("SCCP: Don't know how to handle this terminator!");
+  // Check if we've called markEdgeExecutable on the edge yet. (We could
+  // be more aggressive and try to consider edges which haven't been marked
+  // yet, but there isn't any need.)
+  return KnownFeasibleEdges.count(Edge(From, To));
 }
 
 // visit Implementations - Something changed in this instruction, either an
 // operand made a transition, or the instruction is newly executable.  Change
 // the value type of I to reflect these changes if appropriate.  This method
 // makes sure to do the following actions:
 //
 // 1. If a phi node merges two constants in, and has conflicting value coming
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 (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 (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 (markEdgeExecutable(&BB, DefaultSuccessor))
         return true;
+
+      continue;
     }
   }
 
   return false;
 }
 
 static bool tryToReplaceWithConstantRange(SCCPSolver &Solver, Value *V) {
   bool Changed = false;
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;
+          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/ipsccp-branch-unresolved-undef.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -ipsccp | FileCheck %s
+
+define void @main() {
+; CHECK-LABEL: @main(
+; CHECK:         %call = call i1 @patatino(i1 undef)
+; CHECK-NEXT:    ret void
+;
+  %call = call i1 @patatino(i1 undef)
+  ret void
+}
+
+define internal i1 @patatino(i1 %a) {
+; CHECK-LABEL: define internal i1 @patatino(
+; CHECK-NEXT:    br label [[ONFALSE:%.*]]
+; CHECK-EMPTY:
+; CHECK-NEXT:  onfalse:
+; CHECK-NEXT:    ret i1 undef
+  br i1 %a, label %ontrue, label %onfalse
+ontrue:
+  ret i1 false
+onfalse:
+  ret i1 false
+}

llvm/trunk/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

llvm/trunk/test/Transforms/SCCP/return-zapped.ll

+; RUN: opt < %s -S -ipsccp | FileCheck %s
+
+; After the first round of Solver.Solve(), the return value of @testf still
+; undefined as we hit a branch on undef. Therefore the conditional branch on
+; @testf's return value in @bar is unknown. In ResolvedUndefsIn, we force the
+; false branch to be feasible. We later discover that @testf actually
+; returns true, so we end up with an unfolded "br i1 true".
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-LABEL: if.then:
+; CHECK:         [[CALL:%.+]] = call i1 @testf()
+; CHECK-NEXT:    br i1 true, label %if.end, label %if.then
+;
+entry:
+  br label %if.then
+if.then:                                          ; preds = %entry, %if.then
+  %foo = phi i32 [ 0, %entry], [ %next, %if.then]
+  %next = add i32 %foo, 1
+  %call = call i1 @testf()
+  br i1 %call, label %if.end, label %if.then
+
+if.end:                                           ; preds = %if.then, %entry
+  ret void
+}
+
+define internal i1 @testf() {
+; CHECK-LABEL: define internal i1 @testf(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IF_END3:%.*]]
+; CHECK:       if.end3:
+; CHECK-NEXT:    ret i1 undef
+;
+entry:
+  br i1 undef, label %if.then1, label %if.end3
+
+if.then1:                                         ; preds = %if.end
+  br label %if.end3
+
+if.end3:                                          ; preds = %if.then1, %entry
+  ret i1 true
+}
+
+
+; Call sites in unreachable blocks should not be a problem.
+; CHECK-LABEL: define i1 @test2() {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   br label %if.end
+; CHECK-LABEL: if.end:                                           ; preds = %entry
+; CHECK-NEXT:   %call2 = call i1 @testf()
+; CHECK-NEXT:   ret i1 true
+define i1 @test2() {
+entry:
+  br label %if.end
+
+if.then:                                          ; preds = %entry, %if.then
+  %call = call i1 @testf()
+  br i1 %call, label %if.end, label %if.then
+
+if.end:                                           ; preds = %if.then, %entry
+  %call2 = call i1 @testf()
+  ret i1 %call2
+}