[InstCombine] Aggressively fold compares that can be discovered to be constant

[jmolloy]

Summary

There are situations where we may not be able to determine that a value is a particular constant, but we may be able to determine that it must be one of a set of constants. A good example is when trawling through selects or PHIs:

%1 = select i1 %a, i32 42, i32 64
%2 = icmp sgt i32 %1, i32 78

We know %1 must either be 42 or 64. We should be able to use that knowledge to fold %2 to false. In fact, we can do this already for the above simple case due to peepholes in InstCombineCompares. However the following case does not get caught:

%1 = select i1 %a, i32 42, i32 64
%2 = add i32 %1, 1
%3 = icmp sgt i32 %2, i32 78

Because the peepholes in InstCombine can't see through the add.

This patch introduces a general GetUnderlyingValues() function, sort of a corrollary to GetUnderlyingObjects(). It will take a value and attempt to determine a set of other values it could possibly be. In this case GetUnderlyingValues(%2) would return {43, 64}.

We then use this in InstCombineCompares - if all the results returned by GetUnderlyingValues are constant, and the constant folder determines the result of the compare is the same in all cases, constant fold the compare.

We do this in InstCombine rather than InstSimplify primarily because GetUnderlyingValues (like GetUnderlyingObjects) can call into InstSimplify itself and therefore cause unchecked recursion. Calling this only from InstCombine is very nearly as powerful and uses less compile time too (no measured compile time increase).

[majnemer]

lib/Analysis/ValueTracking.cpp

3049

auto *

3055

auto *

3062

auto *

3065

auto *

3068–3069

Does isa<ConstantInt> fulfill UnaryPredicate? If so, you don't need the lambda.

3077–3082

It doesn't look like NewVs will be used if Fail is true. Why not break out of the loop?

3090

auto *

lib/Transforms/InstCombine/InstCombineCompares.cpp

2764

auto *

[jmolloy]

Hi David,

Thanks for the quick review! All the auto's done apart from one due to a strange type deduction error:

error: variable 'IncValue' with type 'auto *' has incompatible initializer of type 'llvm::Use'
    for (auto *IncValue : PN->incoming_values())

Unfortunately isa<> can't be deduced as a UnaryPredicate either, which is a pity because I thought that would look really neat.

Cheers,

James

[bkramer]

In D15232#302528, @jmolloy wrote:

Unfortunately isa<> can't be deduced as a UnaryPredicate either, which is a pity because I thought that would look really neat.

You can't use isa<Foo>, but you can use isa<Foo, const Value *>. It's not as pretty though.

[reames]

At a high level, I'm a bit unsure about the formulation chosen here. I'm worried that seeking to find a set of constant values through a potentially large value graph might be expensive.

A couple of specific questions:

• The examples you've listed should be entirely handled by LazyValueInfo and either JumpThreading or CVP. Do you have a strong reason InstCombine needs to perform the same optimization?
• Have you considered phrasing this as pushing the query (i.e. icmp) back along the inputs? Doing this might a) let you terminate earlier or b) unswitch the comparison if the select is only used by the compare.

[hfinkel]

Can you provide a better example, because InstCombine seems to get the one you mentioned already (I just tried with a build using r254106):

$ cat /tmp/f.cpp 
bool check(bool i) {
  int f = i ? 42 : 64;
  f += 1;
  return f > 78;
}

which eventually gets down to:

define zeroext i1 @_Z5checkb(i1 zeroext %i) #0 {
entry:
  %frombool = zext i1 %i to i8
  %tobool = trunc i8 %frombool to i1
  %cond = select i1 %tobool, i32 42, i32 64
  %add = add nsw i32 %cond, 1
  %cmp = icmp sgt i32 %add, 78
  ret i1 %cmp
}

and then (after instcombine):

; Function Attrs: nounwind
define zeroext i1 @_Z5checkb(i1 zeroext %i) #0 {
entry:
  ret i1 false
}

Beyond this, if we need further functionality in instcombine, did you consider using LVI directly?

[jmolloy]

Hi Philip,

Would you feel comfortable reviewing the rest of the code? I'm aware that David is rather swamped with reviews and am trying to find alternative reviewers.

Cheers,

James

include/llvm/Analysis/ValueTracking.h

namespace llvm {
   ///
   /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
   /// should not assume that Curr and Prev share the same underlying object thus
   /// it shouldn't look through the phi above.
   void GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
                             const DataLayout &DL, LoopInfo *LI = nullptr,
                             unsigned MaxLookup = 6);
 
+  /// Trace a value through selects and PHIs, returning the set of possible
+  /// values that V could be. Unlike GetUnderlyingObjects, this does not strip
+  /// away any information - if this returns a single value in Values, that
+  /// value can be used as a replacement for V. For example, given this
+  /// expression (which is the equivalent of a GEP, which GetUnderlyingObjects
+  /// would skip over):
+  ///
+  ///    %1 = add i32 %2, 1
+  ///
+  /// GetUnderlyingValues would return %1, or if %2 was found to be constant,
+  /// %2+1.  This function can recurse through binary operators such as the \c
+  /// add above if the operator has a constant as its right hand operand. It
+  /// will only recurse to a depth of \c MaxRecurse.
+  void GetUnderlyingValues(Value *V, SmallVectorImpl<Value *> &Values,
+                           const DataLayout &DL, unsigned MaxRecurse = 2);
+
   /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer
   /// are lifetime markers.
   bool onlyUsedByLifetimeMarkers(const Value *V);
 
   /// isDereferenceablePointer - Return true if this is always a dereferenceable
   /// pointer. If the context instruction is specified perform context-sensitive
   /// analysis and return true if the pointer is dereferenceable at the
   /// specified instruction.

lib/Analysis/ValueTracking.cpp

static bool isSameUnderlyingObjectInLoop(PHINode *PN, LoopInfo *LI) {
   //       int *p = a[i];
   //       ...
   if (auto *Load = dyn_cast<LoadInst>(PrevValue))
     if (!L->isLoopInvariant(Load->getPointerOperand()))
       return false;
   return true;
 }
 
+void llvm::GetUnderlyingValues(Value *V, SmallVectorImpl<Value *> &Objects,
+                               const DataLayout &DL, unsigned MaxRecurse) {
+  if (MaxRecurse == 0) {
+    Objects.push_back(V);
+    return;
+  }
+
+  SmallPtrSet<Value *, 4> Visited;
+  SmallVector<Value *, 4> Worklist;
+  Worklist.push_back(V);
+  do {
+    Value *P = Worklist.pop_back_val();
+    if (!Visited.insert(P).second)
+      continue;
+
+    if (auto *SI = dyn_cast<SelectInst>(P)) {
+      Worklist.push_back(SI->getTrueValue());
+      Worklist.push_back(SI->getFalseValue());
+      continue;
+    }
+
+    if (auto *PN = dyn_cast<PHINode>(P)) {
+      for (Value *IncValue : PN->incoming_values())
+        Worklist.push_back(IncValue);
+      continue;
+    }
+
+    if (MaxRecurse > 1)
+      if (auto *BO = dyn_cast<BinaryOperator>(P))
+        // If this operator has a RHS of a constant int, we can possibly
+        // constant fold it if the LHS turns out also to be a constant.
+        if (auto *RHS = dyn_cast<ConstantInt>(BO->getOperand(1))) {
+          SmallVector<Value *, 4> Vs;
+          GetUnderlyingValues(BO->getOperand(0), Vs, DL, MaxRecurse - 1);
+          if (std::all_of(Vs.begin(), Vs.end(), [](const Value *V) {
+                return isa<ConstantInt>(V);
+              })) {
+            SmallVector<Value *, 4> NewVs;
+            for (auto *V : Vs) {
+              auto *C =
+                  ConstantFoldInstOperands(BO->getOpcode(), V->getType(),
+                                           {cast<ConstantInt>(V), RHS}, DL);
+              if (!C)
+                break;
+              NewVs.push_back(C);
+            }
+            if (NewVs.size() == Vs.size()) {
+              Worklist.insert(Worklist.end(), NewVs.begin(), NewVs.end());
+              continue;
+            }
+          }
+        }
+
+    // See if InstructionSimplify knows any relevant tricks.
+    if (auto *I = dyn_cast<Instruction>(P))
+      // TODO: Acquire a DominatorTree and AssumptionCache and use them.
+      if (auto *Simplified = SimplifyInstruction(I, DL, nullptr)) {
+        Worklist.push_back(Simplified);
+        continue;
+      }
+
+    Objects.push_back(P);
+  } while (!Worklist.empty());
+}
+
 Value *llvm::GetUnderlyingObject(Value *V, const DataLayout &DL,
                                  unsigned MaxLookup) {
   if (!V->getType()->isPointerTy())
     return V;
   for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||

lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Op0Cplxity < Op1Cplxity ||
         (Op0Cplxity == Op1Cplxity &&
          swapMayExposeCSEOpportunities(Op0, Op1))) {
     I.swapOperands();
     std::swap(Op0, Op1);
     Changed = true;
   }
 
   if (Value *V =
-          SimplifyICmpInst(I.getPredicate(), Op0, Op1, DL, TLI, DT, AC, &I))
     return ReplaceInstUsesWith(I, V);
 
+  // If one operand of the compare is constant, can we determine the set of
+  // values the other operand can take? if so, and they're all constant,
+  // fold the compare.
+  if (auto *CRHS = dyn_cast<ConstantInt>(Op1)) {
+    SmallVector<Value *, 4> Values;
+    GetUnderlyingValues(Op0, Values, DL);
+    if (!Values.empty() &&
+        std::all_of(Values.begin(), Values.end(),
+                    [](const Value *V) { return isa<ConstantInt>(V); })) {
+      SmallVector<Constant *, 4> Cs;
+      for (auto *V : Values)
+        Cs.push_back(ConstantFoldCompareInstOperands(
+            I.getPredicate(), cast<Constant>(V), CRHS, DL, TLI));
+
+      if (std::all_of(Cs.begin(), Cs.end(),
+                      [&](const Constant *C) { return C == Cs[0]; }))
+        return ReplaceInstUsesWith(I, Cs[0]);
+    }
+  }
+
   // comparing -val or val with non-zero is the same as just comparing val
   // ie, abs(val) != 0 -> val != 0
   if (I.getPredicate() == ICmpInst::ICMP_NE && match(Op1, m_Zero()))
   {
     Value *Cond, *SelectTrue, *SelectFalse;
     if (match(Op0, m_Select(m_Value(Cond), m_Value(SelectTrue),
                             m_Value(SelectFalse)))) {
       if (Value *V = dyn_castNegVal(SelectTrue)) {

test/Transforms/InstCombine/icmp.ll

 ; CHECK-NOT: add
 ; CHECK: icmp sle i32 %conv, %i
 define i1 @cmp_slt_rhs_inc(float %x, i32 %i) {
   %conv = fptosi float %x to i32
   %inc = add nsw i32 %i, 1
   %cmp = icmp slt i32 %conv, %inc
   ret i1 %cmp
 }
+
+; CHECK-LABEL: @cmp_select
+; CHECK: ret i1 true
+define i1 @cmp_select(i1 %i, i1 %j) {
+entry:
+  br i1 %j, label %one, label %two
+
+one:
+  br label %three
+
+two:
+  br label %three
+  
+three:
+  %z = phi i32 [ 67, %one ], [ 111, %two ]
+  %a = select i1 %i, i32 %z, i32 200
+  %b = add i32 %a, 5
+  %c = icmp slt i32 %b, 256
+  ret i1 %c
+}
+
+; CHECK-LABEL: @cmp_select_negative
+; CHECK-NOT: ret i1 {{true|false}}
+; CHECK: }
+define i1 @cmp_select_negative(i1 %i, i1 %j) {
+entry:
+  br i1 %j, label %one, label %two
+
+one:
+  br label %three
+
+two:
+  br label %three
+  
+three:
+  %z = phi i32 [ 251, %one ], [ 111, %two ]
+  %a = select i1 %i, i32 %z, i32 200
+  %b = add i32 %a, 5
+  %c = icmp slt i32 %b, 256
+  ret i1 %c
+}