[SCEV] Use lshr in implications

[mkazantsev]

Summary

This patch adds support for implication inference logic for the
following pattern:

lhs < (y >> z) <= y, y <= rhs --> lhs < rhs

We should be able to use the fact that value shifted to right is
not greater than the original value (provided it is non-negative).

[mkazantsev]

Ping

[apilipenko]

llvm/lib/Analysis/ScalarEvolution.cpp

11476

Could you please outline the implication rule you are about to use here? Otherwise, it's not clear why you need this canonicalization.

11495

I find this comment cryptic (maybe this is because I'm not familiar with the lingo of the SCEV implication engine). I think what you meant here is:

LHS <u (shiftee >> shiftvalue) && shiftee <=u RHS ---> x <u RHS
LHS <=u (shiftee >> shiftvalue) && shiftee <=u RHS ---> x <=u RHS
LHS <s (shiftee >> shiftvalue) && shiftee >= 0 && shiftee <=s RHS ---> x <s RHS
LHS <=s (shiftee >> shiftvalue) && shiftee >= 0 && shiftee <=s RHS ---> x <=s RHS

[apilipenko]

llvm/lib/Analysis/ScalarEvolution.cpp

11496–11505

Looking better, but now there is a mismatch between the code and the comment. You don't check for isKnownNonNegative for unsigned predicates, but the comment suggest that this is a precondition for all cases.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

11496–11505

All numbers are non-negative w.r.t. unsigned predicate.

[mkazantsev]

Just for certainity:
https://alive2.llvm.org/ce/z/j6FopD
https://alive2.llvm.org/ce/z/wXGnbw
https://alive2.llvm.org/ce/z/nrLSbv
https://alive2.llvm.org/ce/z/u9xREq

[mkazantsev]

Updated comment.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   /// This routine tries to figure out predicate for Phis which are SCEVUnknown
   /// if it is true for every possible incoming value from their respective
   /// basic blocks.
   bool isImpliedViaMerge(ICmpInst::Predicate Pred,
                          const SCEV *LHS, const SCEV *RHS,
                          const SCEV *FoundLHS, const SCEV *FoundRHS,
                          unsigned Depth);
 
+  /// Test whether the condition described by Pred, LHS, and RHS is true
+  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
+  /// true.
+  ///
+  /// This routine tries to reason about shifts.
+  bool isImpliedCondOperandsViaShift(ICmpInst::Predicate Pred, const SCEV *LHS,
+                                     const SCEV *RHS, const SCEV *FoundLHS,
+                                     const SCEV *FoundRHS);
+
   /// If we know that the specified Phi is in the header of its containing
   /// loop, we know the loop executes a constant number of times, and the PHI
   /// node is just a recurrence involving constants, fold it.
   Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
                                               const Loop *L);
 
   /// Test if the given expression is known to satisfy the condition described
   /// by Pred and the known constant ranges of LHS and RHS.

llvm/lib/Analysis/ScalarEvolution.cpp

for (const BasicBlock *IncBB : predecessors(LBB)) {
         return false;
       if (!ProvedEasily(L, RHS))
         return false;
     }
   }
   return true;
 }
 
+bool ScalarEvolution::isImpliedCondOperandsViaShift(ICmpInst::Predicate Pred,
+                                                    const SCEV *LHS,
+                                                    const SCEV *RHS,
+                                                    const SCEV *FoundLHS,
+                                                    const SCEV *FoundRHS) {
+  // We want to imply LHS < RHS from LHS < (RHS >> shiftvalue).  First, make
+  // sure that we are dealing with same LHS.
+  if (RHS == FoundRHS) {
+    std::swap(LHS, RHS);
+    std::swap(FoundLHS, FoundRHS);
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+  if (LHS != FoundLHS)
+    return false;
+
+  auto *SUFoundRHS = dyn_cast<SCEVUnknown>(FoundRHS);
+  if (!SUFoundRHS)
+    return false;
+
+  Value *Shiftee, *ShiftValue;
+
+  using namespace PatternMatch;
+  if (match(SUFoundRHS->getValue(),
+            m_LShr(m_Value(Shiftee), m_Value(ShiftValue)))) {
+    auto *ShifteeS = getSCEV(Shiftee);
+    // Prove one of the following:
+    // LHS <u (shiftee >> shiftvalue) && shiftee <=u RHS ---> LHS <u RHS
+    // LHS <=u (shiftee >> shiftvalue) && shiftee <=u RHS ---> LHS <=u RHS
+    // LHS <s (shiftee >> shiftvalue) && shiftee <=s RHS && shiftee >=s 0
+    //   ---> LHS <s RHS
+    // LHS <=s (shiftee >> shiftvalue) && shiftee <=s RHS && shiftee >=s 0
+    //   ---> LHS <=s RHS
+    if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE)
+      return isKnownPredicate(ICmpInst::ICMP_ULE, ShifteeS, RHS);
+    if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE)
+      if (isKnownNonNegative(ShifteeS))
+        return isKnownPredicate(ICmpInst::ICMP_SLE, ShifteeS, RHS);
+  }
+
+  return false;
+}
+
 bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
                                             const SCEV *LHS, const SCEV *RHS,
                                             const SCEV *FoundLHS,
                                             const SCEV *FoundRHS,
                                             const Instruction *CtxI) {
   if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundLHS, FoundRHS))
     return true;
 
   if (isImpliedCondOperandsViaNoOverflow(Pred, LHS, RHS, FoundLHS, FoundRHS))
     return true;
 
+  if (isImpliedCondOperandsViaShift(Pred, LHS, RHS, FoundLHS, FoundRHS))
+    return true;
+
   if (isImpliedCondOperandsViaAddRecStart(Pred, LHS, RHS, FoundLHS, FoundRHS,
                                           CtxI))
     return true;
 
   return isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      FoundLHS, FoundRHS);
 }
 

llvm/test/Transforms/IndVarSimplify/shift-range-checks.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S < %s -indvars | FileCheck %s
 ; RUN: opt -S < %s -passes=indvars | FileCheck %s
 
 declare i1 @cond()
 declare void @exit(i32 %code)
 
-; FIXME: We can remove 2nd check here because it is implied by check
-; against the shifted value.
 define void @test_01(i32* %p, i32 %shift) {
 ; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4, !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X]], [[SHIFT:%.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[LESS_THAN_SHIFTED:%.*]] = icmp slt i32 [[IV]], [[X_SHIFTED]]
 ; CHECK-NEXT:    br i1 [[LESS_THAN_SHIFTED]], label [[GUARDED:%.*]], label [[FAILURE:%.*]]
 ; CHECK:       guarded:
-; CHECK-NEXT:    [[LESS_THAN_X:%.*]] = icmp ult i32 [[IV]], [[X]]
-; CHECK-NEXT:    br i1 [[LESS_THAN_X]], label [[BACKEDGE]], label [[NEVER_HAPPENS:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[NEVER_HAPPENS:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       done:
 ; CHECK-NEXT:    ret void
 ; CHECK:       failure:
 ; CHECK-NEXT:    call void @exit(i32 1)
failure:
   call void @exit(i32 1)
   unreachable
 
 never_happens:
   call void @exit(i32 0)
   unreachable
 }
 
-; FIXME: We can remove 2nd check here because it is implied by check
-; against the shifted value.
 define void @test_02(i32* %p, i32 %shift) {
 ; CHECK-LABEL: @test_02(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X]], [[SHIFT:%.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[LESS_THAN_SHIFTED:%.*]] = icmp sgt i32 [[X_SHIFTED]], [[IV]]
 ; CHECK-NEXT:    br i1 [[LESS_THAN_SHIFTED]], label [[GUARDED:%.*]], label [[FAILURE:%.*]]
 ; CHECK:       guarded:
-; CHECK-NEXT:    [[LESS_THAN_X:%.*]] = icmp ugt i32 [[X]], [[IV]]
-; CHECK-NEXT:    br i1 [[LESS_THAN_X]], label [[BACKEDGE]], label [[NEVER_HAPPENS:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[NEVER_HAPPENS:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       done:
 ; CHECK-NEXT:    ret void
 ; CHECK:       failure:
 ; CHECK-NEXT:    call void @exit(i32 1)
failure:
   call void @exit(i32 1)
   unreachable
 
 never_happens:
   call void @exit(i32 0)
   unreachable
 }
 
-; FIXME: We can remove 2nd check here because it is implied by check
-; against the shifted value.
 define void @test_03(i32* %p, i32 %shift) {
 ; CHECK-LABEL: @test_03(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X]], [[SHIFT:%.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[LESS_THAN_SHIFTED:%.*]] = icmp ult i32 [[IV]], [[X_SHIFTED]]
 ; CHECK-NEXT:    br i1 [[LESS_THAN_SHIFTED]], label [[GUARDED:%.*]], label [[FAILURE:%.*]]
 ; CHECK:       guarded:
-; CHECK-NEXT:    [[LESS_THAN_X:%.*]] = icmp ult i32 [[IV]], [[X]]
-; CHECK-NEXT:    br i1 [[LESS_THAN_X]], label [[BACKEDGE]], label [[NEVER_HAPPENS:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[NEVER_HAPPENS:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       done:
 ; CHECK-NEXT:    ret void
 ; CHECK:       failure:
 ; CHECK-NEXT:    call void @exit(i32 1)
failure:
   call void @exit(i32 1)
   unreachable
 
 never_happens:
   call void @exit(i32 0)
   unreachable
 }
 
-; FIXME: We can remove 2nd check here because it is implied by check
-; against the shifted value.
 define void @test_04(i32* %p, i32 %shift) {
 ; CHECK-LABEL: @test_04(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X]], [[SHIFT:%.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[LESS_THAN_SHIFTED:%.*]] = icmp ugt i32 [[X_SHIFTED]], [[IV]]
 ; CHECK-NEXT:    br i1 [[LESS_THAN_SHIFTED]], label [[GUARDED:%.*]], label [[FAILURE:%.*]]
 ; CHECK:       guarded:
-; CHECK-NEXT:    [[LESS_THAN_X:%.*]] = icmp ugt i32 [[X]], [[IV]]
-; CHECK-NEXT:    br i1 [[LESS_THAN_X]], label [[BACKEDGE]], label [[NEVER_HAPPENS:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[NEVER_HAPPENS:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       done:
 ; CHECK-NEXT:    ret void
 ; CHECK:       failure:
 ; CHECK-NEXT:    call void @exit(i32 1)