[SCEV] Avoid creating unnecessary SCEVs for SelectInsts.

[fhahn]

Summary

After 675080a4533b, we always create SCEVs for all operands of a
SelectInst. This can cause notable compile-time regressions compared to
the recursive algorithm, which only evaluates the operands if the select
is in a form we can create a usable expression.

This approach adds additional logic to getOperandsToCreate to only
queue operands for selects if we will later be able to construct a
usable SCEV.

Unfortunately this introduces a bit of coupling between actual SCEV
construction for selects and getOperandsToCreate, but I am not sure if
there are better alternatives to address the regression mentioned for
675080a4533b.

This doesn't have any notable compile-time impact on CTMark.

[nikic]

LGTM

I was wondering if we can't drop that code for select -> min/max formation now that we canonicalize to intrinsics, but then I remembered that we still use the select form for pointers.

[foad]

I can confirm that this fixes the compile time regression I reported - thanks!

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops) {
 
   case Instruction::IntToPtr:
     return getUnknown(V);
 
   case Instruction::PHI:
     // Keep constructing SCEVs' for phis recursively for now.
     return nullptr;
 
-  case Instruction::Select:
+  case Instruction::Select: {
+    // Check if U is a select that can be simplified to a SCEVUnknown.
+    auto CanSimplifyToUnknown = [this, U]() {
+      if (U->getType()->isIntegerTy(1) || isa<ConstantInt>(U->getOperand(0)))
+        return false;
+
+      auto *ICI = dyn_cast<ICmpInst>(U->getOperand(0));
+      if (!ICI)
+        return false;
+      Value *LHS = ICI->getOperand(0);
+      Value *RHS = ICI->getOperand(1);
+      if (ICI->getPredicate() == CmpInst::ICMP_EQ ||
+          ICI->getPredicate() == CmpInst::ICMP_NE) {
+        if (!(isa<ConstantInt>(RHS) && cast<ConstantInt>(RHS)->isZero()))
+          return true;
+      } else if (getTypeSizeInBits(LHS->getType()) >
+                 getTypeSizeInBits(U->getType()))
+        return true;
+      return false;
+    };
+    if (CanSimplifyToUnknown())
+      return getUnknown(U);
+
     for (Value *Inc : U->operands())
       Ops.push_back(Inc);
     return nullptr;
     break;
-
+  }
   case Instruction::Call:
   case Instruction::Invoke:
     if (Value *RV = cast<CallBase>(U)->getReturnedArgOperand()) {
       Ops.push_back(RV);
       return nullptr;
     }
 
     if (auto *II = dyn_cast<IntrinsicInst>(U)) {