[X86][CodeGenPrepare] Try to reuse IV's incremented value instead of adding the offset

[mkazantsev]

Summary

While optimizing the memory instruction, we sometimes need to add
offset to the value of IV. We could avoid doing so if the IV.next is
already defined at the point of interest. In this case, we may get two
possible advantages from this:

• If the IV step happens to match with the offset, we don't need to add the offset at all;
• We reduce overlap of live ranges of IV and IV.next. They may stop overlapping and it will lead to better register allocation. Even if the overlap will preserve, we are not introducing a new overlap, so it should be a neutral transform.

Currently I've only added support for IVs that get decremented using usub
intrinsic. We could also support AddInstr, however there is some weird
interaction with some other transform that may lead to infinite compilation
in this case (seems like same transform is done and undone over and over).
I need to investigate why it happens, but generally we could do that too.

[mkazantsev]

Found one reason of TODO, it may only happen with AddInstr, will add in follow-up patch. Seems that there is one more hang with AddInstr. So I suggest to have usub first and then follow-up with add support.

[mkazantsev]

Rebased

[mkazantsev]

Ping.

[aqjune]

The change from the previous output to the new output looks valid to me.

$ ./build/alive-tv D96399.srctgt.ll -disable-undef-input

----------------------------------------
define * @src(* %p, i64 %idx) {
%0:
  %addr1 = mul i64 %idx, 4
  %ptr = gep * %p, 1 x i64 %addr1
  %ptr2 = gep * %ptr, 1 x i64 -4
  ret * %ptr2
}
=>
define * @tgt(* %p, i64 %idx) {
%0:
  %res = usub_overflow {i64, i1, i24} %idx, 1
  %sub = extractvalue {i64, i1, i24} %res, 0
  %addr2 = mul i64 %sub, 4
  %ptr2 = gep * %p, 1 x i64 %addr2
  ret * %ptr2
}
Transformation seems to be correct!

(The disable-undef-input flag added to resolve timeout, but it is still okay with undef inputs I think)

[reames]

Max,

A couple of high level comments here.

1. You're code is specific to generating the address as GEPs. I think we want to handle this for the non-GEP path as well.
2. I think this makes more sense to phrase as an optimization step for the AddrMode we're about to sink. Doing it that way should also address (1) above.
3. I'm definitely not okay with the initial patch being so narrowly focused. If you were handling generic add and sub, but not the overflow intrinsics I'd be less concerned, but the very narrow focus on one of the overflow along with your todo makes me strongly suspect there is a lurking correctness issue which the usub tests simply happen not to expose.
4. I think I might see the correctness issue, or at least a hint of it. Consider the case where addressing does overflow. The wrapping semantics of a GEP are not the same as the usubo. That difference means that if overflow occurs, your optimized AddrMode is incorrect. I believe you need to restrict this transform to when you can prove overflow causes the memory inst not to be reached.

[mkazantsev]

You're code is specific to generating the address as GEPs. I think we want to handle this for the non-GEP path as well.

I think this makes more sense to phrase as an optimization step for the AddrMode we're about to sink. Doing it that way should also address (1) above.

Agreed. I tried doing this during AddrMode computation, but it's impossible because it's lacking knowledge about the user. But I think it can be hoisted out of condition.

I think I might see the correctness issue, or at least a hint of it. Consider the case where addressing does overflow. The wrapping semantics of a GEP are not the same as the usubo. That difference means that if overflow occurs, your optimized AddrMode is incorrect. I believe you need to restrict this transform to when you can prove overflow causes the memory inst not to be reached.

I don't quite get the point here. If overflow occurs in optimized case, it also occurs in non-optimized case. My transform does not change the actual offset, it just simplifies the way how it's computed.

[mkazantsev]

Moved the logic into AddrMode optimization code, so that GEP and non-GEP modes can use it separately. So it should resolve concerns 1 and 2.

As for potential functional bugs and TODO, need to think more. Placing (WIP) until resolved.

[mkazantsev]

Generalized to add/sub/uadd with overflow cases.

[mkazantsev]

Need to address correctness issue with overflow.

[mkazantsev]

Added tests & safety checks against add/sub with nuw/nsw flags to avoid potential misuse of poisoned values. So far we conservatively restrain from optimizing such doubteous cases. Follow-up planned: try to prove flags is possible, if not - drop them (?).

[reames]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1279

Can you precommit the extraction of the lambda to a static function? The diff is confusing to read.

1318–1319

Same with the rename here. (Or at least, this appears to be only a rename?)

3838

Please remove whitespace change, feel free to commit separately.

3868

You really should be able to factor out some common code here with the isIVIncrement function above. Maybe time for a getIVIncrement function?

Hm, though there appears to be a bug in this copy. The "incr" you identify doesn't appear to be tied to the PN.

5107–5108

The need for domtree here introduces a potential compile time problem given the way CGP manages domtree invalidation. Just noting it for now.

[reames]

I suggest taking a look at the matchSimpleRecurrence routine I just added to ValueTracking. I strongly suspect you can simplify some of this code a lot.

[mkazantsev]

llvm/lib/CodeGen/CodeGenPrepare.cpp

3868

IVInc is the incoming value of the Phi node from the backedge which has the same phi node as argument thru matcher. That makes it tied, no?

[mkazantsev]

llvm/lib/CodeGen/CodeGenPrepare.cpp

5107–5108

Let's see if it will have visible measurable impact, and if so, think how to tackle it.

[mkazantsev]

Addressed comments: all independent changes commited separately.

[reames]

LGTM w/required comments.

llvm/lib/CodeGen/CodeGenPrepare.cpp

3890

I'm not really convinced of your second point above (e.g. the generic offset one). In particular, it's not clear to me that an arbitrary offset is *always* better than an overlapped live interval.

I'm also not convinced you're wrong.

I'm not going to require you stage this, but if you need to revert for any reason I'll strongly suggest staging first the case where the existing base offset cancels, and then doing the general offset case in a second patch.

3897

As written, there's a potential overflow here for SINT_MAX and Scale = 8. Please use APInt.smul_ov here.

3900

If I'm reading the code correctly, you want this to be adding IVInc to the instruction list, not the phi node.

[xbolva00]

http://llvm-compile-time-tracker.com/compare.php?from=b15ce2f344ac7845729d2be0a8316b20a32c6292&to=d9e93e8e57fe63babc319cbaf84f1afeccb83696&stat=instructions

Can this be less expensive for compile time?

@nikic

[nikic]

From a cursory look, the problem is likely that you're doing an unconditional call to getDT(), which will lead to unnecessary DomTree calculations. The way this function is supposed to be used is directly when checking dominance, after other checks have already been done.

[reames]

I went ahead and pushed a change (e0cfd451) to lazily compute domtree as per @nikic's guess. @xbolva00 do you still see the compile time regression with this change?

[nikic]

In D96399#2604000, @reames wrote:

I went ahead and pushed a change (e0cfd451) to lazily compute domtree as per @nikic's guess. @xbolva00 do you still see the compile time regression with this change?

Thanks! Here are the results for the range with both commits (it does not look like any other relevant changes landed in the meantime): http://llvm-compile-time-tracker.com/compare.php?from=b15ce2f344ac7845729d2be0a8316b20a32c6292&to=e0cfd451718e2524cc5b8f98ecd72a75d37146cc&stat=instructions

For most programs the regression is resolved, only mafft still has a noteworthy regression, as well as the ReleaseLTO-g configurations (don't know if related to the LTO part or the -g part though).

[reames]

In D96399#2604070, @nikic wrote:

For most programs the regression is resolved, only mafft still has a noteworthy regression, as well as the ReleaseLTO-g configurations (don't know if related to the LTO part or the -g part though).

How concerned by this are you? To me this looks relatively isolated, and likely directly related to code changes in the respective benchmarks. (Though, is that an easy way to check that without building it all myself?) I can see one more small tweak I can make to defer domtree usage a bit further (will do so), but at some point it's pretty fundamental to this change (which I do think is worthwhile). Thoughts?

[reames]

Pushed 6af94d22 which defers the domtree compute slightly further.

As an aside, the analysis invalidation in this code is a mess. We appear to be leaving loopinfo (which is derived from DT) stale. It just happens that the particular variety of stale doesn't expose problems in practice (joy). It's also not clear why we don't just update DT in the various transforms which modify it. None of them appear particularly hard to do.

[nikic]

In D96399#2604109, @reames wrote:

In D96399#2604070, @nikic wrote:

For most programs the regression is resolved, only mafft still has a noteworthy regression, as well as the ReleaseLTO-g configurations (don't know if related to the LTO part or the -g part though).

How concerned by this are you? To me this looks relatively isolated, and likely directly related to code changes in the respective benchmarks. (Though, is that an easy way to check that without building it all myself?) I can see one more small tweak I can make to defer domtree usage a bit further (will do so), but at some point it's pretty fundamental to this change (which I do think is worthwhile). Thoughts?

I'm not very concerned about that particular regression, but rather the potential implications. If this is indeed still caused by domtree calculations (rather than second order effects -- that also sounds plausible), then it is quite likely that there are also pathological cases (this is a typical issue for domtree invalidation + use in the same pass).

As an aside, the analysis invalidation in this code is a mess. We appear to be leaving loopinfo (which is derived from DT) stale. It just happens that the particular variety of stale doesn't expose problems in practice (joy). It's also not clear why we don't just update DT in the various transforms which modify it. None of them appear particularly hard to do.

Yeah, it's a real mess. What I find particularly concerning is that a lot of transforms set a ModifiedDT flag, despite not doing any CFG changes! For example combineToUAddWithOverflow() seems to use this flag to avoid instruction iterator invalidation -- flushing the DT and reprocessing the whole function is a pretty big hammer for that problem.

[reames]

I think we're at the point where if we do see problematic cases due to dom tree handling, we should just fix CGP to not use the current invalidation scheme. Doing that is not a huge amount of work, and we're spending more time avoiding it than is warranted.

If necessary, I'll even volunteer to do it. I will put that off until we have a motivating test case though. :)

llvm/lib/CodeGen/CodeGenPrepare.cpp

static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI,
 
   // If, after promotion, these are the same types, this is a noop copy.
   if (SrcVT != DstVT)
     return false;
 
   return SinkCast(CI);
 }
 
 /// If given \p PN is an inductive variable with value IVInc coming from the
 /// backedge, and on each iteration it gets increased by Step, return pair
 /// <IVInc, Step>. Otherwise, return None.
 static Optional<std::pair<Instruction *, Constant *> >
 getIVIncrement(const PHINode *PN, const LoopInfo *LI) {
   const Loop *L = LI->getLoopFor(PN->getParent());
   if (!L || L->getHeader() != PN->getParent() || !L->getLoopLatch())
     return None;
   auto *IVInc =
if (auto IVInc = getIVIncrement(PN, LI))
     return IVInc->first == BO;
   return false;
 }
 
 bool CodeGenPrepare::replaceMathCmpWithIntrinsic(BinaryOperator *BO,
                                                  Value *Arg0, Value *Arg1,
                                                  CmpInst *Cmp,
                                                  Intrinsic::ID IID) {
   auto IsReplacableIVIncrement = [this, &Cmp](BinaryOperator *BO) {
     if (!isIVIncrement(BO, LI))
       return false;
     const Loop *L = LI->getLoopFor(BO->getParent());
     // IV increment may have other users than the IV. We do not want to make
     // dominance queries to analyze the legality of moving it towards the cmp,
     // so just check that there is no other users.
     if (!BO->hasOneUse())
       return false;
     // Do not risk on moving increment into a child loop.

 /// A helper class for matching addressing modes.
 ///
 /// This encapsulates the logic for matching the target-legal addressing modes.
 class AddressingModeMatcher {
   SmallVectorImpl<Instruction*> &AddrModeInsts;
   const TargetLowering &TLI;
   const TargetRegisterInfo &TRI;
   const DataLayout &DL;
+  const LoopInfo &LI;
+  const DominatorTree &DT;
 
   /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
   /// the memory instruction that we're computing this address for.
   Type *AccessTy;
   unsigned AddrSpace;
   Instruction *MemoryInst;
 
   /// This is the addressing mode that we're building up. This is
class AddressingModeMatcher {
   /// True if we are optimizing for size.
   bool OptSize;
 
   ProfileSummaryInfo *PSI;
   BlockFrequencyInfo *BFI;
 
   AddressingModeMatcher(
       SmallVectorImpl<Instruction *> &AMI, const TargetLowering &TLI,
-      const TargetRegisterInfo &TRI, Type *AT, unsigned AS, Instruction *MI,
+      const TargetRegisterInfo &TRI, const LoopInfo &LI,
+      const DominatorTree &DT, Type *AT, unsigned AS, Instruction *MI,
       ExtAddrMode &AM, const SetOfInstrs &InsertedInsts,
       InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
       std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
       bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI)
       : AddrModeInsts(AMI), TLI(TLI), TRI(TRI),
-        DL(MI->getModule()->getDataLayout()), AccessTy(AT), AddrSpace(AS),
-        MemoryInst(MI), AddrMode(AM), InsertedInsts(InsertedInsts),
-        PromotedInsts(PromotedInsts), TPT(TPT), LargeOffsetGEP(LargeOffsetGEP),
-        OptSize(OptSize), PSI(PSI), BFI(BFI) {
+        DL(MI->getModule()->getDataLayout()), LI(LI), DT(DT), AccessTy(AT),
+        AddrSpace(AS), MemoryInst(MI), AddrMode(AM),
+        InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
+        LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI), BFI(BFI) {
     IgnoreProfitability = false;
   }
 
 public:
   /// Find the maximal addressing mode that a load/store of V can fold,
   /// give an access type of AccessTy.  This returns a list of involved
   /// instructions in AddrModeInsts.
   /// \p InsertedInsts The instructions inserted by other CodeGenPrepare
   /// optimizations.
   /// \p PromotedInsts maps the instructions to their type before promotion.
   /// \p The ongoing transaction where every action should be registered.
   static ExtAddrMode
   Match(Value *V, Type *AccessTy, unsigned AS, Instruction *MemoryInst,
         SmallVectorImpl<Instruction *> &AddrModeInsts,
-        const TargetLowering &TLI, const TargetRegisterInfo &TRI,
-        const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
-        TypePromotionTransaction &TPT,
+        const TargetLowering &TLI, const LoopInfo &LI, const DominatorTree &DT,
+        const TargetRegisterInfo &TRI, const SetOfInstrs &InsertedInsts,
+        InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
         std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
         bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) {
     ExtAddrMode Result;
 
-    bool Success = AddressingModeMatcher(AddrModeInsts, TLI, TRI, AccessTy, AS,
-                                         MemoryInst, Result, InsertedInsts,
-                                         PromotedInsts, TPT, LargeOffsetGEP,
-                                         OptSize, PSI, BFI)
-                       .matchAddr(V, 0);
+    bool Success = AddressingModeMatcher(
+        AddrModeInsts, TLI, TRI, LI, DT, AccessTy, AS, MemoryInst, Result,
+        InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
+        BFI).matchAddr(V, 0);
     (void)Success; assert(Success && "Couldn't select *anything*?");
     return Result;
   }
 
 private:
   bool matchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
   bool matchAddr(Value *Addr, unsigned Depth);
   bool matchOperationAddr(User *AddrInst, unsigned Opcode, unsigned Depth,
bool AddressingModeMatcher::matchScaledValue(Value *ScaleReg, int64_t Scale,
   if (!TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace))
     return false;
 
   // It was legal, so commit it.
   AddrMode = TestAddrMode;
 
   // Okay, we decided that we can add ScaleReg+Scale to AddrMode.  Check now
   // to see if ScaleReg is actually X+C.  If so, we can turn this into adding
-  // X*Scale + C*Scale to addr mode.
+  // X*Scale + C*Scale to addr mode. If we found available IV increment, do not
+  // go any further: we can reuse it and cannot eliminate it.
   ConstantInt *CI = nullptr; Value *AddLHS = nullptr;
   if (isa<Instruction>(ScaleReg) && // not a constant expr.
       match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI))) &&
+      !isIVIncrement(cast<BinaryOperator>(ScaleReg), &LI) &&
       CI->getValue().isSignedIntN(64)) {
     TestAddrMode.InBounds = false;
     TestAddrMode.ScaledReg = AddLHS;
     TestAddrMode.BaseOffs += CI->getSExtValue() * TestAddrMode.Scale;
 
     // If this addressing mode is legal, commit it and remember that we folded
     // this instruction.
     if (TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace)) {
       AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
       AddrMode = TestAddrMode;
       return true;
     }
+    // Restore status quo.
+    TestAddrMode = AddrMode;
+  }
+
+  auto GetConstantStep = [this](const Value * V)
+      ->Optional<std::pair<Instruction *, APInt> > {
+    auto *PN = dyn_cast<PHINode>(V);
+    if (!PN)
+      return None;
+    auto IVInc = getIVIncrement(PN, &LI);
+    if (!IVInc)
+      return None;
+    // TODO: The result of the intrinsics above is two-compliment. However when
+    // IV inc is expressed as add or sub, iv.next is potentially a poison value.
+    // If it has nuw or nsw flags, we need to make sure that these flags are
+    // inferrable at the point of memory instruction. Otherwise we are replacing
+    // well-defined two-compliment computation with poison. Currently, to avoid
+    // potentially complex analysis needed to prove this, we reject such cases.
+    if (auto *OIVInc = dyn_cast<OverflowingBinaryOperator>(IVInc->first))
+      if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
+        return None;
+    if (auto *ConstantStep = dyn_cast<ConstantInt>(IVInc->second))
+      return std::make_pair(IVInc->first, ConstantStep->getValue());
+    return None;
+  };
+
+  // Try to account for the following special case:
+  // 1. ScaleReg is an inductive variable;
+  // 2. We use it with non-zero offset;
+  // 3. IV's increment is available at the point of memory instruction.
+  //
+  // In this case, we may reuse the IV increment instead of the IV Phi to
+  // achieve the following advantages:
+  // 1. If IV step matches the offset, we will have no need in the offset;
+  if (AddrMode.BaseOffs) {
+    if (auto IVStep = GetConstantStep(ScaleReg)) {
+      Instruction *IVInc = IVStep->first;
+      APInt Step = IVStep->second;
+      APInt Offset = Step * AddrMode.Scale;
+      if (Offset.isSignedIntN(64) && TestAddrMode.BaseOffs == Offset &&
+          DT.dominates(IVInc, MemoryInst)) {
+        TestAddrMode.InBounds = false;
+        TestAddrMode.ScaledReg = IVInc;
+        TestAddrMode.BaseOffs -= Offset.getLimitedValue();
+        // If this addressing mode is legal, commit it..
+        if (TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace)) {
+          AddrModeInsts.push_back(cast<Instruction>(IVInc));
+          AddrMode = TestAddrMode;
+          return true;
+        }
+        // Restore status quo.
+        TestAddrMode = AddrMode;
+      }
+    }
   }
 
-  // Otherwise, not (x+c)*scale, just return what we have.
+  // Otherwise, just return what we have.
   return true;
 }
 
 /// This is a little filter, which returns true if an addressing computation
 /// involving I might be folded into a load/store accessing it.
 /// This doesn't need to be perfect, but needs to accept at least
 /// the set of instructions that MatchOperationAddr can.
 static bool MightBeFoldableInst(Instruction *I) {
for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) {
     // Do a match against the root of this address, ignoring profitability. This
     // will tell us if the addressing mode for the memory operation will
     // *actually* cover the shared instruction.
     ExtAddrMode Result;
     std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(nullptr,
                                                                       0);
     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
         TPT.getRestorationPoint();
-    AddressingModeMatcher Matcher(
-        MatchedAddrModeInsts, TLI, TRI, AddressAccessTy, AS, MemoryInst, Result,
-        InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI, BFI);
+    AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, TRI, LI, DT,
+                                  AddressAccessTy, AS, MemoryInst, Result,
+                                  InsertedInsts, PromotedInsts, TPT,
+                                  LargeOffsetGEP, OptSize, PSI, BFI);
     Matcher.IgnoreProfitability = true;
     bool Success = Matcher.matchAddr(Address, 0);
     (void)Success; assert(Success && "Couldn't select *anything*?");
 
     // The match was to check the profitability, the changes made are not
     // part of the original matcher. Therefore, they should be dropped
     // otherwise the original matcher will not present the right state.
     TPT.rollback(LastKnownGood);
while (!worklist.empty()) {
     }
 
     // For non-PHIs, determine the addressing mode being computed.  Note that
     // the result may differ depending on what other uses our candidate
     // addressing instructions might have.
     AddrModeInsts.clear();
     std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(nullptr,
                                                                       0);
+    Function *F = MemoryInst->getParent()->getParent();
     ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
-        V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *TRI,
-        InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
+        V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDT(*F),
+        *TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
         BFI.get());
 
     GetElementPtrInst *GEP = LargeOffsetGEP.first;
     if (GEP && !NewGEPBases.count(GEP)) {
       // If splitting the underlying data structure can reduce the offset of a
       // GEP, collect the GEP.  Skip the GEPs that are the new bases of
       // previously split data structures.
       LargeOffsetGEPMap[GEP->getPointerOperand()].push_back(LargeOffsetGEP);

llvm/test/CodeGen/X86/2020_12_02_decrementing_loop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-apple-macosx | FileCheck %s
 
-; TODO: We can get rid of movq here by using different offset and %rax.
 define i32 @test_01(i32* %p, i64 %len, i32 %x) {
 ; CHECK-LABEL: test_01:
 ; CHECK:       ## %bb.0: ## %entry
-; CHECK-NEXT:    movq %rsi, %rax
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  LBB0_1: ## %loop
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    subq $1, %rax
+; CHECK-NEXT:    subq $1, %rsi
 ; CHECK-NEXT:    jb LBB0_4
 ; CHECK-NEXT:  ## %bb.2: ## %backedge
 ; CHECK-NEXT:    ## in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    cmpl %edx, -4(%rdi,%rsi,4)
-; CHECK-NEXT:    movq %rax, %rsi
+; CHECK-NEXT:    cmpl %edx, (%rdi,%rsi,4)
 ; CHECK-NEXT:    jne LBB0_1
 ; CHECK-NEXT:  ## %bb.3: ## %failure
 ; CHECK-NEXT:    ud2
 ; CHECK-NEXT:  LBB0_4: ## %exit
 ; CHECK-NEXT:    movl $-1, %eax
 ; CHECK-NEXT:    retq
 entry:
   br label %loop

 
 failure:                                          ; preds = %backedge
   unreachable
 }
 
 define i32 @test_02(i32* %p, i64 %len, i32 %x) {
 ; CHECK-LABEL: test_02:
 ; CHECK:       ## %bb.0: ## %entry
-; CHECK-NEXT:    movq %rsi, %rax
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  LBB2_1: ## %loop
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    subq $1, %rax
+; CHECK-NEXT:    subq $1, %rsi
 ; CHECK-NEXT:    jb LBB2_4
 ; CHECK-NEXT:  ## %bb.2: ## %backedge
 ; CHECK-NEXT:    ## in Loop: Header=BB2_1 Depth=1
-; CHECK-NEXT:    cmpl %edx, -4(%rdi,%rsi,4)
-; CHECK-NEXT:    movq %rax, %rsi
+; CHECK-NEXT:    cmpl %edx, (%rdi,%rsi,4)
 ; CHECK-NEXT:    jne LBB2_1
 ; CHECK-NEXT:  ## %bb.3: ## %failure
 ; CHECK-NEXT:    ud2
 ; CHECK-NEXT:  LBB2_4: ## %exit
 ; CHECK-NEXT:    movl $-1, %eax
 ; CHECK-NEXT:    retq
 entry:
   %start = add i64 %len, -1

 
 failure:                                          ; preds = %backedge
   unreachable
 }
 
 define i32 @test_03(i32* %p, i64 %len, i32 %x) {
 ; CHECK-LABEL: test_03:
 ; CHECK:       ## %bb.0: ## %entry
-; CHECK-NEXT:    movq %rsi, %rax
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  LBB3_1: ## %loop
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    subq $1, %rax
+; CHECK-NEXT:    subq $1, %rsi
 ; CHECK-NEXT:    jb LBB3_4
 ; CHECK-NEXT:  ## %bb.2: ## %backedge
 ; CHECK-NEXT:    ## in Loop: Header=BB3_1 Depth=1
-; CHECK-NEXT:    cmpl %edx, -4(%rdi,%rsi,4)
-; CHECK-NEXT:    movq %rax, %rsi
+; CHECK-NEXT:    cmpl %edx, (%rdi,%rsi,4)
 ; CHECK-NEXT:    jne LBB3_1
 ; CHECK-NEXT:  ## %bb.3: ## %failure
 ; CHECK-NEXT:    ud2
 ; CHECK-NEXT:  LBB3_4: ## %exit
 ; CHECK-NEXT:    movl $-1, %eax
 ; CHECK-NEXT:    retq
 entry:
   %start = add i64 %len, -100

llvm/test/CodeGen/X86/uadd_inc_iv.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -mtriple=x86_64-linux -codegenprepare -S < %s | FileCheck %s
 
 declare { i64, i1 } @llvm.uadd.with.overflow.i64(i64, i64)
 
 define i32 @test_01(i32* %p, i64 %len, i32 %x) {
 ; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[MATH:%.*]], [[BACKEDGE:%.*]] ], [ [[LEN:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 [[IV]], i64 1)
 ; CHECK-NEXT:    [[MATH]] = extractvalue { i64, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i64, i1 } [[TMP0]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[SUNKADDR:%.*]] = mul i64 [[IV]], 4
+; CHECK-NEXT:    [[SUNKADDR3:%.*]] = mul i64 [[MATH]], 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[P:%.*]] to i8*
-; CHECK-NEXT:    [[SUNKADDR1:%.*]] = getelementptr i8, i8* [[TMP1]], i64 [[SUNKADDR]]
-; CHECK-NEXT:    [[SUNKADDR2:%.*]] = getelementptr i8, i8* [[SUNKADDR1]], i64 4
-; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i8* [[SUNKADDR2]] to i32*
+; CHECK-NEXT:    [[SUNKADDR4:%.*]] = getelementptr i8, i8* [[TMP1]], i64 [[SUNKADDR3]]
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i8* [[SUNKADDR4]] to i32*
 ; CHECK-NEXT:    [[LOADED:%.*]] = load atomic i32, i32* [[TMP2]] unordered, align 4
 ; CHECK-NEXT:    [[COND_2:%.*]] = icmp eq i32 [[LOADED]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[COND_2]], label [[FAILURE:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;

llvm/test/CodeGen/X86/usub_inc_iv.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -mtriple=x86_64-linux -codegenprepare -S < %s | FileCheck %s
 
 define i32 @test_01(i32* %p, i64 %len, i32 %x) {
 ; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[MATH:%.*]], [[BACKEDGE:%.*]] ], [ [[LEN:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 [[IV]], i64 1)
 ; CHECK-NEXT:    [[MATH]] = extractvalue { i64, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i64, i1 } [[TMP0]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[SUNKADDR:%.*]] = mul i64 [[IV]], 4
+; CHECK-NEXT:    [[SUNKADDR:%.*]] = mul i64 [[MATH]], 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    [[SUNKADDR1:%.*]] = getelementptr i8, i8* [[TMP1]], i64 [[SUNKADDR]]
-; CHECK-NEXT:    [[SUNKADDR2:%.*]] = getelementptr i8, i8* [[SUNKADDR1]], i64 -4
-; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i8* [[SUNKADDR2]] to i32*
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i8* [[SUNKADDR1]] to i32*
 ; CHECK-NEXT:    [[LOADED:%.*]] = load atomic i32, i32* [[TMP2]] unordered, align 4
 ; CHECK-NEXT:    [[COND_2:%.*]] = icmp eq i32 [[LOADED]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[COND_2]], label [[FAILURE:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[MATH:%.*]], [[BACKEDGE:%.*]] ], [ [[LEN:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 [[IV]], i64 1)
 ; CHECK-NEXT:    [[MATH]] = extractvalue { i64, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i64, i1 } [[TMP0]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[SUNKADDR:%.*]] = mul i64 [[IV]], 4
+; CHECK-NEXT:    [[SUNKADDR:%.*]] = mul i64 [[MATH]], 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    [[SUNKADDR1:%.*]] = getelementptr i8, i8* [[TMP1]], i64 [[SUNKADDR]]
-; CHECK-NEXT:    [[SUNKADDR2:%.*]] = getelementptr i8, i8* [[SUNKADDR1]], i64 -4
-; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i8* [[SUNKADDR2]] to i32*
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i8* [[SUNKADDR1]] to i32*
 ; CHECK-NEXT:    [[LOADED:%.*]] = load atomic i32, i32* [[TMP2]] unordered, align 4
 ; CHECK-NEXT:    [[COND_2:%.*]] = icmp eq i32 [[LOADED]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[COND_2]], label [[FAILURE:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;

 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[LEN:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], -1
 ; CHECK-NEXT:    [[COND_0:%.*]] = call i1 @use(i64 [[IV_NEXT]])
 ; CHECK-NEXT:    br i1 [[COND_0]], label [[MIDDLE:%.*]], label [[FAILURE:%.*]]
 ; CHECK:       middle:
 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp eq i64 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[COND_1]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[SUNKADDR:%.*]] = mul i64 [[IV]], 4
+; CHECK-NEXT:    [[SUNKADDR:%.*]] = mul i64 [[IV_NEXT]], 4
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    [[SUNKADDR1:%.*]] = getelementptr i8, i8* [[TMP0]], i64 [[SUNKADDR]]
-; CHECK-NEXT:    [[SUNKADDR2:%.*]] = getelementptr i8, i8* [[SUNKADDR1]], i64 -4
-; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[SUNKADDR2]] to i32*
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[SUNKADDR1]] to i32*
 ; CHECK-NEXT:    [[LOADED:%.*]] = load atomic i32, i32* [[TMP1]] unordered, align 4
 ; CHECK-NEXT:    [[COND_2:%.*]] = icmp eq i32 [[LOADED]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[COND_2]], label [[FAILURE]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;

 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[LEN:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], -1
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[BACKEDGE]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp eq i64 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[COND_1]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[SUNKADDR:%.*]] = mul i64 [[IV]], 4
+; CHECK-NEXT:    [[SUNKADDR:%.*]] = mul i64 [[IV_NEXT]], 4
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    [[SUNKADDR1:%.*]] = getelementptr i8, i8* [[TMP0]], i64 [[SUNKADDR]]
-; CHECK-NEXT:    [[SUNKADDR2:%.*]] = getelementptr i8, i8* [[SUNKADDR1]], i64 -4
-; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[SUNKADDR2]] to i32*
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[SUNKADDR1]] to i32*
 ; CHECK-NEXT:    [[LOADED:%.*]] = load atomic i32, i32* [[TMP1]] unordered, align 4
 ; CHECK-NEXT:    [[COND_2:%.*]] = icmp eq i32 [[LOADED]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[COND_2]], label [[FAILURE:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;