sccp.diff

diff --git llvm/lib/Transforms/Scalar/SCCP.cpp llvm/lib/Transforms/Scalar/SCCP.cpp
index 6d640fe8f9f4..d6ddc7592001 100644
--- llvm/lib/Transforms/Scalar/SCCP.cpp
+++ llvm/lib/Transforms/Scalar/SCCP.cpp
@@ -100,7 +100,7 @@ bool isOverdefined(const ValueLatticeElement &LV) {
 class SCCPSolver : public InstVisitor<SCCPSolver> {
   const DataLayout &DL;
   std::function<const TargetLibraryInfo &(Function &)> GetTLI;
-  SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
+
   DenseMap<Value *, ValueLatticeElement>
       ValueState; // The state each value is in.
 
@@ -147,8 +147,12 @@ class SCCPSolver : public InstVisitor<SCCPSolver> {
   SmallVector<Value *, 64> OverdefinedInstWorkList;
   SmallVector<Value *, 64> InstWorkList;
 
-  // The BasicBlock work list
-  SmallVector<BasicBlock *, 64>  BBWorkList;
+  /// Number of not (yet) feasible predecessors.
+  DenseMap<BasicBlock *, unsigned> BBUnresolvedPreds;
+  /// Basic blocks where all incoming edges are feasible.
+  SmallVector<BasicBlock *, 32> BBWorkListComplete;
+  /// Basic blocks where not all incoming edges were feasible at insertion time.
+  SmallVector<BasicBlock *, 32> BBWorkListPartial;
 
   /// KnownFeasibleEdges - Entries in this set are edges which have already had
   /// PHI nodes retriggered.
@@ -183,16 +187,10 @@ public:
              LLVMContext &Ctx)
       : DL(DL), GetTLI(std::move(GetTLI)), Ctx(Ctx) {}
 
-  /// MarkBlockExecutable - This method can be used by clients to mark all of
-  /// the blocks that are known to be intrinsically live in the processed unit.
-  ///
-  /// This returns true if the block was not considered live before.
-  bool MarkBlockExecutable(BasicBlock *BB) {
-    if (!BBExecutable.insert(BB).second)
-      return false;
+  void addEntryBlock(BasicBlock *BB) {
     LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
-    BBWorkList.push_back(BB);  // Add the block to the work list!
-    return true;
+    BBWorkListComplete.push_back(BB);
+    BBUnresolvedPreds[BB] = 0;
   }
 
   /// TrackValueOfGlobalVariable - Clients can use this method to
@@ -255,7 +253,7 @@ public:
   bool ResolvedUndefsIn(Function &F);
 
   bool isBlockExecutable(BasicBlock *BB) const {
-    return BBExecutable.count(BB);
+    return BBUnresolvedPreds.count(BB);
   }
 
   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
@@ -476,7 +474,20 @@ private:
     if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
       return false;  // This edge is already known to be executable!
 
-    if (!MarkBlockExecutable(Dest)) {
+    bool NewlyExecutable = !BBUnresolvedPreds.count(Dest);
+    unsigned &UnresolvedPreds = BBUnresolvedPreds[Dest];
+    if (NewlyExecutable)
+      UnresolvedPreds = std::distance(pred_begin(Dest), pred_end(Dest));
+
+    assert(UnresolvedPreds > 0 && "No unresolved predecessors");
+    --UnresolvedPreds;
+
+    if (UnresolvedPreds == 0)
+      BBWorkListComplete.push_back(Dest);
+    else if (NewlyExecutable)
+      BBWorkListPartial.push_back(Dest);
+
+    if (!NewlyExecutable) {
       // 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.
@@ -497,7 +508,7 @@ private:
   // 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?
+    if (isBlockExecutable(I->getParent()))   // Inst is executable?
       visit(*I);
   }
 
@@ -1185,7 +1196,7 @@ void SCCPSolver::handleCallArguments(CallBase &CB) {
   // the formal arguments of the function.
   if (!TrackingIncomingArguments.empty() &&
       TrackingIncomingArguments.count(F)) {
-    MarkBlockExecutable(&F->front());
+    addEntryBlock(&F->front());
 
     // Propagate information from this call site into the callee.
     auto CAI = CB.arg_begin();
@@ -1329,8 +1340,8 @@ void SCCPSolver::handleCallResult(CallBase &CB) {
 
 void SCCPSolver::Solve() {
   // Process the work lists until they are empty!
-  while (!BBWorkList.empty() || !InstWorkList.empty() ||
-         !OverdefinedInstWorkList.empty()) {
+  while (!BBWorkListComplete.empty() || !BBWorkListPartial.empty() ||
+         !InstWorkList.empty() || !OverdefinedInstWorkList.empty()) {
     // Process the overdefined instruction's work list first, which drives other
     // things to overdefined more quickly.
     while (!OverdefinedInstWorkList.empty()) {
@@ -1366,11 +1377,24 @@ void SCCPSolver::Solve() {
     }
 
     // Process the basic block work list.
-    while (!BBWorkList.empty()) {
-      BasicBlock *BB = BBWorkList.back();
-      BBWorkList.pop_back();
+    while (!BBWorkListComplete.empty()) {
+      BasicBlock *BB = BBWorkListComplete.back();
+      BBWorkListComplete.pop_back();
+
+      LLVM_DEBUG(dbgs() << "\nPopped off BBWL (complete): " << *BB << '\n');
+
+      // Notify all instructions in this basic block that they are newly
+      // executable.
+      visit(BB);
+    }
+
+    while (!BBWorkListPartial.empty()) {
+      BasicBlock *BB = BBWorkListPartial.back();
+      BBWorkListPartial.pop_back();
+      if (!isBlockExecutable(BB))
+        continue;
 
-      LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
+      LLVM_DEBUG(dbgs() << "\nPopped off BBWL (partial): " << *BB << '\n');
 
       // Notify all instructions in this basic block that they are newly
       // executable.
@@ -1397,7 +1421,7 @@ void SCCPSolver::Solve() {
 /// them as overdefined.
 bool SCCPSolver::ResolvedUndefsIn(Function &F) {
   for (BasicBlock &BB : F) {
-    if (!BBExecutable.count(&BB))
+    if (!isBlockExecutable(&BB))
       continue;
 
     for (Instruction &I : BB) {
@@ -1595,7 +1619,7 @@ static bool runSCCP(Function &F, const DataLayout &DL,
       F.getContext());
 
   // Mark the first block of the function as being executable.
-  Solver.MarkBlockExecutable(&F.front());
+  Solver.addEntryBlock(&F.front());
 
   // Mark all arguments to the function as being overdefined.
   for (Argument &AI : F.args())
@@ -1818,7 +1842,7 @@ bool llvm::runIPSCCP(
     }
 
     // Assume the function is called.
-    Solver.MarkBlockExecutable(&F.front());
+    Solver.addEntryBlock(&F.front());
 
     // Assume nothing about the incoming arguments.
     for (Argument &AI : F.args())
diff --git llvm/test/Transforms/SCCP/conditions-ranges-with-undef.ll llvm/test/Transforms/SCCP/conditions-ranges-with-undef.ll
index f142a426cc13..6861d210ca84 100644
--- llvm/test/Transforms/SCCP/conditions-ranges-with-undef.ll
+++ llvm/test/Transforms/SCCP/conditions-ranges-with-undef.ll
@@ -82,8 +82,7 @@ define void @val_singlecrfromundef_range(i1 %cond) {
 ; CHECK-NEXT:    br label [[TRUE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    call void @use(i1 false)
-; CHECK-NEXT:    [[P_127:%.*]] = and i32 10, 127
-; CHECK-NEXT:    call void @use.i32(i32 [[P_127]])
+; CHECK-NEXT:    call void @use.i32(i32 10)
 ; CHECK-NEXT:    ret void
 ;
 entry:
diff --git llvm/test/Transforms/SCCP/float-nan-simplification.ll llvm/test/Transforms/SCCP/float-nan-simplification.ll
index 1cedbaa69e44..0e1acccba0ef 100644
--- llvm/test/Transforms/SCCP/float-nan-simplification.ll
+++ llvm/test/Transforms/SCCP/float-nan-simplification.ll
@@ -17,8 +17,7 @@ define float @test1(float %a, i1 %bc) {
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[P:%.*]] = phi float [ [[A:%.*]], [[BB1]] ], [ 0x7FF8000000000000, [[BB2]] ]
 ; CHECK-NEXT:    [[V_1:%.*]] = fmul float [[P]], 0.000000e+00
-; CHECK-NEXT:    [[V_2:%.*]] = fadd float [[V_1]], 0xFFF8000000000000
-; CHECK-NEXT:    ret float [[V_2]]
+; CHECK-NEXT:    ret float 0xFFF8000000000000
 ;
 entry:
   br i1 %bc, label %bb1, label %bb2
diff --git llvm/test/Transforms/SCCP/widening.ll llvm/test/Transforms/SCCP/widening.ll
index 8e4f3b520596..0d517392967d 100644
--- llvm/test/Transforms/SCCP/widening.ll
+++ llvm/test/Transforms/SCCP/widening.ll
@@ -17,10 +17,8 @@ define void @test_2_incoming_constants(i32 %x) {
 ; SCCP:       exit:
 ; SCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ]
 ; SCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
-; SCCP-NEXT:    [[T_1:%.*]] = icmp ult i32 [[A]], 20
-; SCCP-NEXT:    call void @use(i1 [[T_1]])
-; SCCP-NEXT:    [[F_1:%.*]] = icmp ugt i32 [[A]], 10
-; SCCP-NEXT:    call void @use(i1 [[F_1]])
+; SCCP-NEXT:    call void @use(i1 true)
+; SCCP-NEXT:    call void @use(i1 false)
 ; SCCP-NEXT:    ret void
 ;
 ; IPSCCP-LABEL: @test_2_incoming_constants(
@@ -32,10 +30,8 @@ define void @test_2_incoming_constants(i32 %x) {
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ]
 ; IPSCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
-; IPSCCP-NEXT:    [[T_1:%.*]] = icmp ult i32 [[A]], 20
-; IPSCCP-NEXT:    call void @use(i1 [[T_1]])
-; IPSCCP-NEXT:    [[F_1:%.*]] = icmp ugt i32 [[A]], 10
-; IPSCCP-NEXT:    call void @use(i1 [[F_1]])
+; IPSCCP-NEXT:    call void @use(i1 true)
+; IPSCCP-NEXT:    call void @use(i1 false)
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
@@ -68,10 +64,8 @@ define void @test_3_incoming_constants(i32 %x) {
 ; SCCP:       exit:
 ; SCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ]
 ; SCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
-; SCCP-NEXT:    [[T_1:%.*]] = icmp ult i32 [[A]], 20
-; SCCP-NEXT:    call void @use(i1 [[T_1]])
-; SCCP-NEXT:    [[F_1:%.*]] = icmp ugt i32 [[A]], 10
-; SCCP-NEXT:    call void @use(i1 [[F_1]])
+; SCCP-NEXT:    call void @use(i1 true)
+; SCCP-NEXT:    call void @use(i1 false)
 ; SCCP-NEXT:    ret void
 ;
 ; IPSCCP-LABEL: @test_3_incoming_constants(
@@ -86,10 +80,8 @@ define void @test_3_incoming_constants(i32 %x) {
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ]
 ; IPSCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
-; IPSCCP-NEXT:    [[T_1:%.*]] = icmp ult i32 [[A]], 20
-; IPSCCP-NEXT:    call void @use(i1 [[T_1]])
-; IPSCCP-NEXT:    [[F_1:%.*]] = icmp ugt i32 [[A]], 10
-; IPSCCP-NEXT:    call void @use(i1 [[F_1]])
+; IPSCCP-NEXT:    call void @use(i1 true)
+; IPSCCP-NEXT:    call void @use(i1 false)
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
@@ -132,10 +124,8 @@ define void @test_5_incoming_constants(i32 %x) {
 ; SCCP:       exit:
 ; SCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ], [ 3, [[BB3]] ], [ 4, [[BB4]] ]
 ; SCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
-; SCCP-NEXT:    [[T_1:%.*]] = icmp ult i32 [[A]], 20
-; SCCP-NEXT:    call void @use(i1 [[T_1]])
-; SCCP-NEXT:    [[F_1:%.*]] = icmp ugt i32 [[A]], 10
-; SCCP-NEXT:    call void @use(i1 [[F_1]])
+; SCCP-NEXT:    call void @use(i1 true)
+; SCCP-NEXT:    call void @use(i1 false)
 ; SCCP-NEXT:    ret void
 ;
 ; IPSCCP-LABEL: @test_5_incoming_constants(
@@ -156,10 +146,8 @@ define void @test_5_incoming_constants(i32 %x) {
 ; IPSCCP:       exit:
 ; IPSCCP-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 1, [[BB1]] ], [ 2, [[BB2]] ], [ 3, [[BB3]] ], [ 4, [[BB4]] ]
 ; IPSCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
-; IPSCCP-NEXT:    [[T_1:%.*]] = icmp ult i32 [[A]], 20
-; IPSCCP-NEXT:    call void @use(i1 [[T_1]])
-; IPSCCP-NEXT:    [[F_1:%.*]] = icmp ugt i32 [[A]], 10
-; IPSCCP-NEXT:    call void @use(i1 [[F_1]])
+; IPSCCP-NEXT:    call void @use(i1 true)
+; IPSCCP-NEXT:    call void @use(i1 false)
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
@@ -744,11 +732,10 @@ define i8* @wobble(%struct.blam.2* %arg, i32 %arg1) align 2 {
 ; IPSCCP-NEXT:    [[C_2:%.*]] = icmp eq i32 [[TMP11]], 8
 ; IPSCCP-NEXT:    br i1 [[C_2]], label [[BB39:%.*]], label [[BB58:%.*]]
 ; IPSCCP:       bb39:
-; IPSCCP-NEXT:    [[TMP40:%.*]] = add nsw i32 [[TMP11]], -1
 ; IPSCCP-NEXT:    [[TMP41:%.*]] = trunc i32 [[TMP3]] to i16
 ; IPSCCP-NEXT:    store i16 [[TMP41]], i16* bitcast ([4 x i8]* @global.11 to i16*), align 1
 ; IPSCCP-NEXT:    [[TMP42:%.*]] = getelementptr inbounds [[STRUCT_BLAM_2]], %struct.blam.2* [[ARG]], i32 0, i32 0
-; IPSCCP-NEXT:    [[TMP43:%.*]] = add i32 [[TMP7]], [[TMP40]]
+; IPSCCP-NEXT:    [[TMP43:%.*]] = add i32 [[TMP7]], 7
 ; IPSCCP-NEXT:    [[TMP44:%.*]] = mul i32 [[TMP43]], 4
 ; IPSCCP-NEXT:    [[TMP45:%.*]] = add i32 [[TMP44]], 2
 ; IPSCCP-NEXT:    [[TMP46:%.*]] = call dereferenceable(1) i8* @spam(%struct.baz.1* [[TMP42]], i32 [[TMP45]])
@@ -763,14 +750,13 @@ define i8* @wobble(%struct.blam.2* %arg, i32 %arg1) align 2 {
 ; IPSCCP-NEXT:    [[TMP55:%.*]] = icmp sgt i32 [[TMP48]], [[TMP54]]
 ; IPSCCP-NEXT:    br i1 [[TMP55]], label [[BB56:%.*]], label [[BB60:%.*]]
 ; IPSCCP:       bb56:
-; IPSCCP-NEXT:    [[TMP57:%.*]] = add nsw i32 [[TMP40]], -1
 ; IPSCCP-NEXT:    br label [[BB60]]
 ; IPSCCP:       bb58:
 ; IPSCCP-NEXT:    [[TMP59:%.*]] = bitcast i16* [[TMP33]] to i8*
 ; IPSCCP-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 getelementptr inbounds ([4 x i8], [4 x i8]* @global.11, i64 0, i64 0), i8* align 2 [[TMP59]], i64 4, i1 false)
 ; IPSCCP-NEXT:    br label [[BB60]]
 ; IPSCCP:       bb60:
-; IPSCCP-NEXT:    [[TMP61:%.*]] = phi i32 [ [[TMP57]], [[BB56]] ], [ [[TMP40]], [[BB39]] ], [ [[TMP11]], [[BB58]] ]
+; IPSCCP-NEXT:    [[TMP61:%.*]] = phi i32 [ 6, [[BB56]] ], [ 7, [[BB39]] ], [ [[TMP11]], [[BB58]] ]
 ; IPSCCP-NEXT:    [[TMP62:%.*]] = getelementptr inbounds [[STRUCT_BLAM_2]], %struct.blam.2* [[ARG]], i32 0, i32 0
 ; IPSCCP-NEXT:    [[TMP63:%.*]] = add i32 [[TMP7]], 1
 ; IPSCCP-NEXT:    [[TMP64:%.*]] = mul i32 [[TMP63]], 4