[SCCP] Reduce the number of times ResolvedUndefsIn is called for large modules.

[efriedma]

Summary

If a module has many values that need to be resolved by ResolvedUndefsIn, compilation takes quadratic time overall. Solve should do a small amount of work, since not much is added to the worklists each time markOverdefined is called. But ResolvedUndefsIn is linear over the length of the function/module, so resolving one undef at a time is quadratic in general.

To solve this, make ResolvedUndefsIn resolve every undef value at once, instead of resolving them one at a time. This loses a little optimization power, but can be a lot faster.

We still need a loop around ResolvedUndefsIn because markOverdefined could change the set of blocks that are live. That should be uncommon, hopefully. We could optimize it by tracking which blocks transition from dead to live, instead of iterating over the whole module to find them. But I'll leave that for later. (The whole function will become a lot simpler once we start pruning branches on undef.)

The regression test changes seem minor. The specific cases in question could probably be optimized with a bit more work, but they seem like edge cases that don't really matter.

Fixes an "infinite" compile issue my team found on an internal workoad.

[fhahn]

This looks reasonable to me and IIUC this mostly restores the original behaviour. LGTM.

Out of curiosity, do you think keeping track of which functions may contain undef states may help with compile-time in your case? E.g. like in D74535

[efriedma]

I would assume that the first pass of ResolveUndefsIn isn't that expensive relative to the other work SCCP does, so it would be more important to ensure we don't need additional passes. And probably we want to work towards removing the branch handling before we invest more effort into optimizing ResolveUndefsIn.

[fhahn]

In D89080#2322612, @efriedma wrote:

I would assume that the first pass of ResolveUndefsIn isn't that expensive relative to the other work SCCP does, so it would be more important to ensure we don't need additional passes. And probably we want to work towards removing the branch handling before we invest more effort into optimizing ResolveUndefsIn.

SGTM

llvm/lib/Transforms/Scalar/SCCP.cpp

 /// CFG and only slightly pessimizes the analysis results (by marking one,
 /// potentially infeasible, edge feasible).  This cannot usefully modify the
 /// constraints on the condition of the branch, as that would impact other users
 /// of the value.
 ///
 /// This scan also checks for values that use undefs. It conservatively marks
 /// them as overdefined.
 bool SCCPSolver::ResolvedUndefsIn(Function &F) {
+  bool MadeChange = false;
   for (BasicBlock &BB : F) {
     if (!BBExecutable.count(&BB))
       continue;
 
     for (Instruction &I : BB) {
       // Look for instructions which produce undef values.
       if (I.getType()->isVoidTy()) continue;
 
for (Instruction &I : BB) {
         // extractvalue and insertvalue don't need to be marked; they are
         // tracked as precisely as their operands.
         if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
           continue;
         // Send the results of everything else to overdefined.  We could be
         // more precise than this but it isn't worth bothering.
         for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
           ValueLatticeElement &LV = getStructValueState(&I, i);
-          if (LV.isUnknownOrUndef())
+          if (LV.isUnknownOrUndef()) {
             markOverdefined(LV, &I);
+            MadeChange = true;
+          }
         }
         continue;
       }
 
       ValueLatticeElement &LV = getValueState(&I);
       if (!LV.isUnknownOrUndef())
         continue;
 
for (Instruction &I : BB) {
       if (isa<LoadInst>(I)) {
         // A load here means one of two things: a load of undef from a global,
         // a load from an unknown pointer.  Either way, having it return undef
         // is okay.
         continue;
       }
 
       markOverdefined(&I);
-      return true;
+      MadeChange = true;
     }
 
     // Check to see if we have a branch or switch on an undefined value.  If so
     // we force the branch to go one way or the other to make the successor
     // values live.  It doesn't really matter which way we force it.
     Instruction *TI = BB.getTerminator();
     if (auto *BI = dyn_cast<BranchInst>(TI)) {
       if (!BI->isConditional()) continue;
       if (!getValueState(BI->getCondition()).isUnknownOrUndef())
         continue;
 
       // If the input to SCCP is actually branch on undef, fix the undef to
       // false.
       if (isa<UndefValue>(BI->getCondition())) {
         BI->setCondition(ConstantInt::getFalse(BI->getContext()));
         markEdgeExecutable(&BB, TI->getSuccessor(1));
-        return true;
+        MadeChange = true;
+        continue;
       }
 
       // 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 = TI->getSuccessor(1);
       if (markEdgeExecutable(&BB, DefaultSuccessor))
-        return true;
+        MadeChange = 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()).isUnknownOrUndef())
         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;
+        MadeChange = true;
+        continue;
       }
 
       // 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: 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;
+        MadeChange = true;
 
       continue;
     }
 
     if (auto *SI = dyn_cast<SwitchInst>(TI)) {
       if (!SI->getNumCases() ||
           !getValueState(SI->getCondition()).isUnknownOrUndef())
         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;
+        MadeChange = true;
+        continue;
       }
 
       // 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;
+        MadeChange = true;
 
       continue;
     }
   }
 
-  return false;
+  return MadeChange;
 }
 
 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
   Constant *Const = nullptr;
   if (V->getType()->isStructTy()) {
     std::vector<ValueLatticeElement> IVs = Solver.getStructLatticeValueFor(V);
     if (any_of(IVs,
                [](const ValueLatticeElement &LV) { return isOverdefined(LV); }))
bool llvm::runIPSCCP(
   }
 
   // Solve for constants.
   bool ResolvedUndefs = true;
   Solver.Solve();
   while (ResolvedUndefs) {
     LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
     ResolvedUndefs = false;
-    for (Function &F : M)
-      if (Solver.ResolvedUndefsIn(F)) {
-        // We run Solve() after we resolved an undef in a function, because
-        // we might deduce a fact that eliminates an undef in another function.
-        Solver.Solve();
+    for (Function &F : M) {
+      if (Solver.ResolvedUndefsIn(F))
         ResolvedUndefs = true;
-      }
+    if (ResolvedUndefs)
+      Solver.Solve();
   }
 
   bool MadeChanges = false;
 
   // Iterate over all of the instructions in the module, replacing them with
   // constants if we have found them to be of constant values.
 
   for (Function &F : M) {

llvm/test/Transforms/SCCP/2004-12-10-UndefBranchBug.ll

-; RUN: opt < %s -sccp -S | grep "ret i32 1"
+; RUN: opt < %s -sccp -S | grep "ret i32 %X"
 
 ; This function definitely returns 1, even if we don't know the direction
 ; of the branch.
 
 define i32 @foo() {
   br i1 undef, label %T, label %T
 T:    ; preds = %0, %0
   %X = add i32 0, 1   ; <i32> [#uses=1]
   ret i32 %X
 }
 

llvm/test/Transforms/SCCP/resolvedundefsin-tracked-fn.ll

bb:
   ret void
 }
 
 define internal void @test4_b(i8* %arg) {
 ; CHECK-LABEL: define {{[^@]+}}@test4_b
 ; CHECK-SAME: (i8* [[ARG:%.*]])
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP:%.*]] = bitcast i8* null to i16*
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 false, i8* null, i8* null
 ; CHECK-NEXT:    call void @use.16(i16* [[TMP]])
-; CHECK-NEXT:    call void @use.8(i8* null)
+; CHECK-NEXT:    call void @use.8(i8* [[SEL]])
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %tmp = bitcast i8* %arg to i16*
   %sel = select i1 false, i8* %arg, i8* %arg
   call void @use.16(i16* %tmp)
   call void @use.8(i8* %sel)
   ret void

 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* @pcount, align 4
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[DIV]], [[SUB19]]
 ; CHECK-NEXT:    [[CMP20:%.*]] = icmp sgt i32 [[TMP2]], [[MUL]]
 ; CHECK-NEXT:    br i1 [[CMP20]], label [[IF_THEN22:%.*]], label [[IF_END24:%.*]]
 ; CHECK:       if.then22:
 ; CHECK-NEXT:    store i32 [[MUL]], i32* @pcount, align 4
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.end24:
-; CHECK-NEXT:    br label [[FOR_END:%.*]]
+; CHECK-NEXT:    [[CMP25474:%.*]] = icmp sgt i32 [[TMP2]], 0
+; CHECK-NEXT:    br i1 [[CMP25474]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    ret void
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %if.end16
 
 if.end16:                                         ; preds = %entry
   %0 = load i32, i32* @contextsize, align 4