[LSR] Unify scheduling of existing and inserted addrecs

[reames]

Summary

LSR goes to some lengths to schedule IV increments such that %iv and %iv.next never need to overlap. This is fairly fundamental to LSRs cost model. LSR assumes that an addrec can be represented with a single register. If %iv and %iv.next have to overlap, then that assumption does not hold.

The bug - which this patch is fixing - is that LSR only does this scheduling for IVs which it inserts, but it's cost model assumes the same for existing IVs that it reuses. It will rewrite existing IV users such that the no-overlap property holds, but will not actually reschedule said IV increment.

As you can see from the relatively lack of test updates, this doesn't actually impact codegen much. The main reason for doing it is to make a follow up patch series which improves post-increment use and scheduling easier to follow.

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5578

nit: let's avoid || by splitting this into two checks.

5583

I'm pretty sure that at this point having constant as 2nd operand is the canonical form. Do we really care about add 2, phi case? If not, I'd propose match (m_Add(m_Specific(PN), m_ConstantInt(Step))) (and same for sub - if we care, because subs are also canonicalized to adds).

5597

I think DT.dominates(IncV, IVIncInsertPos) is not what we should be checking to enforce legality. It's totally legal to move IncV before IVIncInsertPos if DT.dominates(IVIncInsertPos, IncV). It's maybe not what we want performance-wise, but it's legal.

I think the real legality check needed here is DT.dominates(IVIncInsertPos, Latch).

llvm/test/Transforms/LoopStrengthReduce/post-increment-insertion.ll

140

Please commit these tests separately so the diff from this patch is obvious.

[reames]

address review comments

[reames]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5597

(previous response comment got lost?)

It turns out the whole check is unneeded. What I actually needed to check was that all of the operands dominate the insert location, but that's already implied from the other checks. We know the phi must dominate everything in the loop, and constants trivially dominate.

[mkazantsev]

LGTM for now. I'm currently factoring out functions like isIVStep, getIVStep for other purposes. We can reuse it here once all pieces are pulled together.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5581

I would still advice using matchers here.

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5574

Because of simplifications, isa<SCEVAddRecExpr>(SE.getSCEV(&PN)) is potentially more expensive than everything you are going to make here. If it's not a legality check, I think it should be removed.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

for (const IVChain &Chain : IVChainVec) {
     Changed = true;
   }
   // Clean up after ourselves. This must be done before deleting any
   // instructions.
   Rewriter.clear();
 
   Changed |= RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts,
                                                                   &TLI, MSSAU);
+
+  // In our cost analysis above, we assume that each addrec consumes exactly
+  // one register, and arrange to have increments inserted just before the
+  // latch to maximimize the chance this is true.  However, if we reused
+  // existing IVs, we now need to move the increments to match our
+  // expectations.  Otherwise, our cost modeling results in us having a
+  // chosen a non-optimal result for the actual schedule.  (And yes, this
+  // scheduling decision does impact later codegen.)
+  for (PHINode &PN : L->getHeader()->phis()) {
+    // First, filter out anything not an obvious addrec
+    if (!SE.isSCEVable(PN.getType()) || !isa<SCEVAddRecExpr>(SE.getSCEV(&PN)))
+      continue;
+    Instruction *IncV =
+        dyn_cast<Instruction>(PN.getIncomingValueForBlock(L->getLoopLatch()));
+    if (!IncV || (IncV->getOpcode() != Instruction::Add &&
+                  IncV->getOpcode() != Instruction::Sub))
+      continue;
+
+    unsigned PhiOp = IncV->getOperand(0) == &PN ? 0 : 1;
+    if (IncV->getOperand(PhiOp) != &PN)
+      continue;
+
+    if (!isa<Constant>(IncV->getOperand(1-PhiOp)))
+      // If not a constant step, might increase register pressure
+      continue;
+
+    if (IncV->getParent() == IVIncInsertPos->getParent())
+      // Only bother moving across blocks.  Isel can handle block local case.
+      continue;
+
+    // Can we legally schedule inc at the desired point?
+    if (!DT.dominates(IncV, IVIncInsertPos) ||
+        !llvm::all_of(IncV->uses(),
+                      [&](Use &U) {return DT.dominates(IVIncInsertPos, U);}))
+      continue;
+    IncV->moveBefore(IVIncInsertPos);
+    Changed = true;
+  }
+
+
 }
 
 LSRInstance::LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE,
                          DominatorTree &DT, LoopInfo &LI,
                          const TargetTransformInfo &TTI, AssumptionCache &AC,
                          TargetLibraryInfo &TLI, MemorySSAUpdater *MSSAU)
     : IU(IU), SE(SE), DT(DT), LI(LI), AC(AC), TLI(TLI), TTI(TTI), L(L),
       MSSAU(MSSAU), AMK(PreferredAddresingMode.getNumOccurrences() > 0 ?

llvm/test/Transforms/LoopStrengthReduce/post-increment-insertion.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -loop-reduce -S | FileCheck %s
 ; REQUIRES: x86-registered-target
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
-; FIXME: iv.next is supposed to be inserted in the backedge.
 define i32 @test_01(i32* %p, i64 %len, i32 %x) {
 ; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32* [[P:%.*]], i64 -1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[LEN:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[IV_NEXT]] = add nsw i64 [[IV]], -1
 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp eq i64 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[COND_1]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr i32, i32* [[SCEVGEP]], i64 [[IV]]
 ; CHECK-NEXT:    [[LOADED:%.*]] = load atomic i32, i32* [[SCEVGEP1]] unordered, align 4
 ; CHECK-NEXT:    [[COND_2:%.*]] = icmp eq i32 [[LOADED]], [[X:%.*]]
+; CHECK-NEXT:    [[IV_NEXT]] = add nsw i64 [[IV]], -1
 ; CHECK-NEXT:    br i1 [[COND_2]], label [[FAILURE:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %loop
backedge:                                         ; preds = %loop
   br i1 %cond_2, label %failure, label %loop
 
 exit:                                             ; preds = %loop
   ret i32 -1
 
 failure:                                          ; preds = %backedge
   unreachable
 }
+
+define i32 @test_04(i32* %p, i64 %len, i32 %x) {
+; CHECK-LABEL: @test_04(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32* [[P:%.*]], i64 -1
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[LEN:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[COND_1:%.*]] = icmp eq i64 [[IV]], 0
+; CHECK-NEXT:    br i1 [[COND_1]], label [[EXIT:%.*]], label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr i32, i32* [[SCEVGEP]], i64 [[IV]]
+; CHECK-NEXT:    [[LOADED:%.*]] = load atomic i32, i32* [[SCEVGEP1]] unordered, align 4
+; CHECK-NEXT:    [[COND_2:%.*]] = icmp eq i32 [[LOADED]], [[X:%.*]]
+; CHECK-NEXT:    [[IV_NEXT]] = sub i64 [[IV]], 1
+; CHECK-NEXT:    br i1 [[COND_2]], label [[FAILURE:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+; CHECK:       failure:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %backedge, %entry
+  %iv = phi i64 [ %iv.next, %backedge ], [ %len, %entry ]
+  %iv.next = sub i64 %iv, 1
+  %cond_1 = icmp eq i64 %iv, 0
+  br i1 %cond_1, label %exit, label %backedge
+
+backedge:                                         ; preds = %loop
+  %addr = getelementptr inbounds i32, i32* %p, i64 %iv.next
+  %loaded = load atomic i32, i32* %addr unordered, align 4
+  %cond_2 = icmp eq i32 %loaded, %x
+  br i1 %cond_2, label %failure, label %loop
+
+exit:                                             ; preds = %loop
+  ret i32 -1
+
+failure:                                          ; preds = %backedge
+  unreachable
+}
+
+define i32 @test_05(i32* %p, i64 %len, i32 %x) {
+; CHECK-LABEL: @test_05(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[LEN:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = mul i64 [[IV]], 2
+; CHECK-NEXT:    [[COND_1:%.*]] = icmp eq i64 [[IV]], 0
+; CHECK-NEXT:    br i1 [[COND_1]], label [[EXIT:%.*]], label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 [[IV_NEXT]]
+; CHECK-NEXT:    [[LOADED:%.*]] = load atomic i32, i32* [[ADDR]] 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
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %backedge, %entry
+  %iv = phi i64 [ %iv.next, %backedge ], [ %len, %entry ]
+  %iv.next = mul i64 %iv, 2
+  %cond_1 = icmp eq i64 %iv, 0
+  br i1 %cond_1, label %exit, label %backedge
+
+backedge:                                         ; preds = %loop
+  %addr = getelementptr inbounds i32, i32* %p, i64 %iv.next
+  %loaded = load atomic i32, i32* %addr unordered, align 4
+  %cond_2 = icmp eq i32 %loaded, %x
+  br i1 %cond_2, label %failure, label %loop
+
+exit:                                             ; preds = %loop
+  ret i32 -1
+
+failure:                                          ; preds = %backedge
+  unreachable
+}
+
+define i32 @test_06(i32* %p, i64 %len, i32 %x, i64 %step) {
+; CHECK-LABEL: @test_06(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32* [[P:%.*]], i64 [[STEP:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[LEN:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], [[STEP]]
+; CHECK-NEXT:    [[COND_1:%.*]] = icmp eq i64 [[STEP]], [[IV_NEXT]]
+; CHECK-NEXT:    br i1 [[COND_1]], label [[EXIT:%.*]], label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr i32, i32* [[SCEVGEP]], i64 [[IV]]
+; CHECK-NEXT:    [[LOADED:%.*]] = load atomic i32, i32* [[SCEVGEP1]] 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
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %backedge, %entry
+  %iv = phi i64 [ %iv.next, %backedge ], [ %len, %entry ]
+  %iv.next = add nsw i64 %iv, %step
+  %cond_1 = icmp eq i64 %iv, 0
+  br i1 %cond_1, label %exit, label %backedge
+
+backedge:                                         ; preds = %loop
+  %addr = getelementptr inbounds i32, i32* %p, i64 %iv.next
+  %loaded = load atomic i32, i32* %addr unordered, align 4
+  %cond_2 = icmp eq i32 %loaded, %x
+  br i1 %cond_2, label %failure, label %loop
+
+exit:                                             ; preds = %loop
+  ret i32 -1
+
+failure:                                          ; preds = %backedge
+  unreachable
+}