[LVI] Fix LVI compile time regression around constantFoldUser()

[hjyamauchi]

Summary

Avoid checking each operand and calling getValueFromCondition() before calling
constantFoldUser() when the instruction type isn't supported by
constantFoldUser().

This fixes a large compile time regression in an internal build.

[hjyamauchi]

Cleaned up.

[sanjoy]

lib/Analysis/LazyValueInfo.cpp

1417

Please add an assert in constantFolderUser that this is true for its input. Also please s/Value *Val/User *U/

1495–1496

Don't you need to guard this too?

[hjyamauchi]

Addressed comments.

[sanjoy]

lib/Analysis/LazyValueInfo.cpp

1497

Shouldn't this be canConstantFoldUser(Usr) && usesOperand(Usr, Condition)? Otherwise we're not really short-circuiting anything.

[hjyamauchi]

Addressed comment.

[sanjoy]

lgtm

lib/Analysis/LazyValueInfo.cpp

1377

I'd call this isOperationFoldable since we're not checking if Usr is foldable or not but only looking at its operation to see if it could possibly be constant folded.

1446–1449

s/checking the operands/linearly iterating over the operands unnecessarily/

s/large phi/instructions with many operands/ (I don't think "phi" is relevant here -- this could also have happened with a large call, invoke or GEP instruction).

1492

s/ValUsesConditionAndFoldable/ValUsesConditionAndMayBeFoldable/

[hjyamauchi]

Done.

lib/Analysis/LazyValueInfo.cpp

LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
   return getValueFromCondition(Val, Cond, isTrueDest, Visited);
 }
 
 // Return true if Usr has Op as an operand, otherwise false.
 static bool usesOperand(User *Usr, Value *Op) {
   return find(Usr->operands(), Op) != Usr->op_end();
 }
 
-// Check if Val can be simplified to an integer constant when the value of one
+// Return true if the instruction type of Val is supported by
+// constantFoldUser(). Currently CastInst and BinaryOperator only.  Call this
+// before calling constantFoldUser() to find out if it's even worth attempting
+// to call it.
+static bool isOperationFoldable(User *Usr) {
+  return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr);
+}
+
+// Check if Usr can be simplified to an integer constant when the value of one
 // of its operands Op is an integer constant OpConstVal. If so, return it as an
 // lattice value range with a single element or otherwise return an overdefined
 // lattice value.
-static LVILatticeVal constantFoldUser(Value *Val, Value *Op,
+static LVILatticeVal constantFoldUser(User *Usr, Value *Op,
                                       const APInt &OpConstVal,
                                       const DataLayout &DL) {
+  assert(isOperationFoldable(Usr) && "Precondition");
   Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
-  // Check if Val can be simplified to a constant.
-  if (auto *CI = dyn_cast<CastInst>(Val)) {
+  // Check if Usr can be simplified to a constant.
+  if (auto *CI = dyn_cast<CastInst>(Usr)) {
     assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
     if (auto *C = dyn_cast_or_null<ConstantInt>(
             SimplifyCastInst(CI->getOpcode(), OpConst,
                              CI->getDestTy(), DL))) {
       return LVILatticeVal::getRange(ConstantRange(C->getValue()));
     }
-  } else if (auto *BO = dyn_cast<BinaryOperator>(Val)) {
+  } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
     bool Op0Match = BO->getOperand(0) == Op;
     bool Op1Match = BO->getOperand(1) == Op;
     assert((Op0Match || Op1Match) &&
            "Operand 0 nor Operand 1 isn't a match");
     Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
     Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
     if (auto *C = dyn_cast_or_null<ConstantInt>(
             SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
       return LVILatticeVal::getRange(ConstantRange(C->getValue()));
     }
   }
   return LVILatticeVal::getOverdefined();
 }
 
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
 /// Val is not constrained on the edge.  Result is unspecified if return value
 /// is false.
 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
                               BasicBlock *BBTo, LVILatticeVal &Result) {
   // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
   // know that v != 0.
   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
     // If this is a conditional branch and only one successor goes to BBTo, then
     // we may be able to infer something from the condition.
     if (BI->isConditional() &&
         BI->getSuccessor(0) != BI->getSuccessor(1)) {
       bool isTrueDest = BI->getSuccessor(0) == BBTo;
if (BI->isConditional() &&
       // If the condition of the branch is an equality comparison, we may be
       // able to infer the value.
       Result = getValueFromCondition(Val, Condition, isTrueDest);
       if (!Result.isOverdefined())
         return true;
 
       if (User *Usr = dyn_cast<User>(Val)) {
         assert(Result.isOverdefined() && "Result isn't overdefined");
-        if (isa<IntegerType>(Val->getType())) {
+        // Check with isOperationFoldable() first to avoid linearly iterating
+        // over the operands unnecessarily which can be expensive for
+        // instructions with many operands.
+        if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
           const DataLayout &DL = BBTo->getModule()->getDataLayout();
           if (usesOperand(Usr, Condition)) {
             // If Val has Condition as an operand and Val can be folded into a
             // constant with either Condition == true or Condition == false,
             // propagate the constant.
             // eg.
             //   ; %Val is true on the edge to %then.
             //   %Val = and i1 %Condition, true.
             //   br %Condition, label %then, label %else
             APInt ConditionVal(1, isTrueDest ? 1 : 0);
-            Result = constantFoldUser(Val, Condition, ConditionVal, DL);
+            Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
           } else {
             // If one of Val's operand has an inferred value, we may be able to
             // infer the value of Val.
             // eg.
             //    ; %Val is 94 on the edge to %then.
             //    %Val = add i8 %Op, 1
             //    %Condition = icmp eq i8 %Op, 93
             //    br i1 %Condition, label %then, label %else
             for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
               Value *Op = Usr->getOperand(i);
               LVILatticeVal OpLatticeVal =
                   getValueFromCondition(Op, Condition, isTrueDest);
               if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
-                Result = constantFoldUser(Val, Op, OpConst.getValue(), DL);
+                Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
                 break;
               }
             }
           }
         }
       }
       if (!Result.isOverdefined())
         return true;
     }
   }
 
   // If the edge was formed by a switch on the value, then we may know exactly
   // what it is.
   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
     Value *Condition = SI->getCondition();
     if (!isa<IntegerType>(Val->getType()))
       return false;
-    bool ValUsesCondition = false;
+    bool ValUsesConditionAndMayBeFoldable = false;
     if (Condition != Val) {
       // Check if Val has Condition as an operand.
       if (User *Usr = dyn_cast<User>(Val))
-        ValUsesCondition = usesOperand(Usr, Condition);
-      if (!ValUsesCondition)
+        ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
+            usesOperand(Usr, Condition);
+      if (!ValUsesConditionAndMayBeFoldable)
         return false;
     }
-    assert((Condition == Val || ValUsesCondition) &&
+    assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
            "Condition != Val nor Val doesn't use Condition");
 
     bool DefaultCase = SI->getDefaultDest() == BBTo;
     unsigned BitWidth = Val->getType()->getIntegerBitWidth();
     ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
 
     for (auto Case : SI->cases()) {
       APInt CaseValue = Case.getCaseValue()->getValue();
       ConstantRange EdgeVal(CaseValue);
-      if (ValUsesCondition) {
+      if (ValUsesConditionAndMayBeFoldable) {
+        User *Usr = cast<User>(Val);
         const DataLayout &DL = BBTo->getModule()->getDataLayout();
         LVILatticeVal EdgeLatticeVal =
-            constantFoldUser(Val, Condition, CaseValue, DL);
+            constantFoldUser(Usr, Condition, CaseValue, DL);
         if (EdgeLatticeVal.isOverdefined())
           return false;
         EdgeVal = EdgeLatticeVal.getConstantRange();
       }
       if (DefaultCase) {
         // It is possible that the default destination is the destination of
         // some cases. We cannot perform difference for those cases.
         // We know Condition != CaseValue in BBTo.  In some cases we can use