[ConstraintElim] Support decrementing inductions with step -1.

[fhahn]

Summary

Extend the logic in addInfoForInductions to support decrementing
inductions with a step of -1.

NOTE: I still need to add small tests for the patch.

Depends on D152730.

Fixes #64881.

[fhahn]

Superseded by PR https://github.com/llvm/llvm-project/pull/68644

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

else if (Pred == CmpInst::ICMP_EQ)
     Succ = cast<BranchInst>(BB.getTerminator())->getSuccessor(1);
   else
     return;
 
   if (!L->contains(Succ) || !L->isLoopExiting(&BB) || Succ == &BB)
     return;
 
   auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.getSCEV(PN));
-  if (!AR)
+  BasicBlock *LoopPred = L->getLoopPredecessor();
+  if (!AR || !LoopPred)
     return;
 
   const SCEV *StartSCEV = AR->getStart();
   Value *StartValue = nullptr;
   if (auto *C = dyn_cast<SCEVConstant>(StartSCEV))
     StartValue = C->getValue();
   else if (auto *U = dyn_cast<SCEVUnknown>(StartSCEV))
     StartValue = U->getValue();
-
-  if (!StartValue)
+  else {
+    StartValue = PN->getIncomingValueForBlock(LoopPred);
+    if (SE.getSCEV(StartValue) != AR->getStart())
       return;
+  }
 
   Type *StepTy = AR->getType();
   const DataLayout &DL = BB.getModule()->getDataLayout();
   unsigned BitWidth = StepTy->isPointerTy() ? DL.getIndexTypeSizeInBits(StepTy)
                                             : StepTy->getScalarSizeInBits();
   APInt StepOffset(BitWidth, 0);
   if (auto *C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
     StepOffset = C->getAPInt();
   else
     return;
 
+  // Handle negative steps.
+  if (StepOffset.isNegative()) {
+    // TODO: Extend to allow steps > -1.
+    if (!(-StepOffset).isOne())
+      return;
+
+    // AR may wrap. Add StartValue >= PN conditional on B <= StartValue which
+    // guarantees that the loop exits before wrapping with a step of -1.
+    auto *DTN = DT.getNode(Succ);
+    WorkList.push_back(FactOrCheck::getFact(DTN, CmpInst::ICMP_UGE, StartValue,
+                                            PN, CmpInst::ICMP_ULE, B,
+                                            StartValue));
+    // AR may wrap. Add PN > B conditional on B <= StartValue which guarantees
+    // that the loop exits when reaching B with a step of -1.
+    WorkList.push_back(FactOrCheck::getFact(DTN, CmpInst::ICMP_UGT, PN, B,
+                                            CmpInst::ICMP_ULE, B, StartValue));
+    return;
+  }
+
   // Make sure AR either steps by 1 or that the value we compare against is a
   // GEP based on the same start value and all offsets are a multiple of the
   // step size, to guarantee that the induction will reach the value.
   if (StepOffset.isZero() || StepOffset.isNegative())
     return;
 
   if (!StepOffset.isOne()) {
     auto *UpperGEP = dyn_cast<GetElementPtrInst>(B);

llvm/test/Transforms/PhaseOrdering/loop-access-checks.ll

 
 ; -------------------------------------------------------------------------
 ; Test case for runtime check removal when accessing elements in a nested loop
 ; (PR64881)
 
 
 define void @monkey(ptr noundef %arr, i32 noundef %len) {
 ; CHECK-LABEL: define void @monkey
-; CHECK-SAME: (ptr nocapture noundef [[ARR:%.*]], i32 noundef [[LEN:%.*]]) local_unnamed_addr {
+; CHECK-SAME: (ptr nocapture noundef [[ARR:%.*]], i32 noundef [[LEN:%.*]]) local_unnamed_addr #[[ATTR1:[0-9]+]] {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP8:%.*]] = icmp ugt i32 [[LEN]], 1
 ; CHECK-NEXT:    br i1 [[CMP8]], label [[FOR_BODY4_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
 ; CHECK:       for.body4.preheader:
 ; CHECK-NEXT:    [[I_09:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_COND_CLEANUP3:%.*]] ], [ 1, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
 ; CHECK:       for.cond.cleanup:
 ; CHECK-NEXT:    ret void
 ; CHECK:       for.cond.cleanup3:
 ; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_09]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY4_PREHEADER]], label [[FOR_COND_CLEANUP]]
 ; CHECK:       for.body4:
-; CHECK-NEXT:    [[K_07:%.*]] = phi i32 [ [[DEC:%.*]], [[AT_EXIT:%.*]] ], [ [[I_09]], [[FOR_BODY4_PREHEADER]] ]
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i32 [[K_07]], [[LEN]]
-; CHECK-NEXT:    br i1 [[CMP_NOT_I]], label [[AT_EXIT]], label [[IF_THEN_I:%.*]]
-; CHECK:       if.then.i:
-; CHECK-NEXT:    tail call void @abort()
-; CHECK-NEXT:    unreachable
-; CHECK:       at.exit:
+; CHECK-NEXT:    [[K_07:%.*]] = phi i32 [ [[DEC:%.*]], [[FOR_BODY4]] ], [ [[I_09]], [[FOR_BODY4_PREHEADER]] ]
 ; CHECK-NEXT:    [[IDX_EXT_I:%.*]] = zext i32 [[K_07]] to i64
 ; CHECK-NEXT:    [[ADD_PTR_I:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[IDX_EXT_I]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ADD_PTR_I]], align 4
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP0]], 1
 ; CHECK-NEXT:    store i32 [[ADD]], ptr [[ADD_PTR_I]], align 4
 ; CHECK-NEXT:    [[DEC]] = add i32 [[K_07]], -1
 ; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i32 [[DEC]], 0
 ; CHECK-NEXT:    br i1 [[CMP2_NOT]], label [[FOR_COND_CLEANUP3]], label [[FOR_BODY4]]