[LoopUnrollAnalyzer] Try to simplify address computation outside of loop.

[fhahn]

Summary

The analyzer tries to simplify address computations inside the loop
body, but not outside the loop. This means we currently fail to
recognize some pointer compares as free.

This patch adds machinery to simplify address computations outside the
loop. We use it directly in visitCmpInst, because it do not visit the
instructions outside the loop currently.

This helps with cost modelling of loops like the on in PR43305.

[fhahn]

ping.

This improves cost modeling for loops with exit conditions with pointer arithmetic.

[efriedma]

Not exactly a comment on this patch specifically, but should unrolled loop analysis have some sort of special case for the loop exit? If a compare is only used by the loop exit branch, it will be dead after full unroll, so it doesn't make sense to include its cost. (I mean, in theory, if SCEV can compute the trip count of a loop, UnrolledInstAnalyzer should be able to as well, but realistically it might not be worthwhile to reach parity.)

llvm/lib/Analysis/LoopUnrollAnalyzer.cpp

76

Requiring the base to be a SCEVUnknown seems too restrictive to me... but I guess it's an existing restriction, so I guess it's okay for now.

llvm/include/llvm/Analysis/LoopUnrollAnalyzer.h

private:
   /// post-unrolling.
   DenseMap<Value *, Constant *> &SimplifiedValues;
 
   ScalarEvolution &SE;
   const Loop *L;
 
   bool simplifyInstWithSCEV(Instruction *I);
 
+  /// Try to simplify an address computation outside of the loop body, so we can
+  /// compare it with simplified addresses in the loop.
+  void simplifyNonLoopAddress(Value *V);
+
   bool visitInstruction(Instruction &I) { return simplifyInstWithSCEV(&I); }
   bool visitBinaryOperator(BinaryOperator &I);
   bool visitLoad(LoadInst &I);
   bool visitCastInst(CastInst &I);
   bool visitCmpInst(CmpInst &I);
   bool visitPHINode(PHINode &PN);
 };
 }
 #endif

llvm/lib/Analysis/LoopUnrollAnalyzer.cpp

if (!Offset)
     return false;
   SimplifiedAddress Address;
   Address.Base = Base->getValue();
   Address.Offset = Offset->getValue();
   SimplifiedAddresses[I] = Address;
   return false;
 }
 
+void UnrolledInstAnalyzer::simplifyNonLoopAddress(Value *V) {
+  Instruction *Inst = dyn_cast<Instruction>(V);
+  // For now we only try to simplify address computation instructions outside
+  // the current loop.
+  if (!Inst || !Inst->getType()->isPointerTy() ||
+      !SE.isSCEVable(Inst->getType()) || L->contains(Inst))
+    return;
+  auto Iter = SimplifiedAddresses.find(Inst);
+  if (Iter != SimplifiedAddresses.end())
+    return;
+
+  const SCEV *S = SE.getSCEV(Inst);
+  // Check if the offset from the base address becomes a constant.
+  auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
+  if (!Base)
+    return;
+  auto *Offset = dyn_cast<SCEVConstant>(SE.getMinusSCEV(S, Base));
+  if (!Offset)
+    return;
+
+  SimplifiedAddress Address;
+  Address.Base = Base->getValue();
+  Address.Offset = Offset->getValue();
+  SimplifiedAddresses[V] = Address;
+}
+
 /// Try to simplify binary operator I.
 ///
 /// TODO: Probably it's worth to hoist the code for estimating the
 /// simplifications effects to a separate class, since we have a very similar
 /// code in InlineCost already.
 bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   if (!isa<Constant>(LHS))
bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
   if (!isa<Constant>(LHS))
     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
       LHS = SimpleLHS;
   if (!isa<Constant>(RHS))
     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
       RHS = SimpleRHS;
 
   if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
+    simplifyNonLoopAddress(LHS);
+    simplifyNonLoopAddress(RHS);
     auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
     if (SimplifiedLHS != SimplifiedAddresses.end()) {
       auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
       if (SimplifiedRHS != SimplifiedAddresses.end()) {
         SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
         SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
         if (LHSAddr.Base == RHSAddr.Base) {
           LHS = LHSAddr.Offset;

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

for (;; --Iteration) {
                     PhiI->getIncomingValueForBlock(L->getLoopLatch())))
               if (L->contains(OpI))
                 PHIUsedList.push_back(OpI);
             continue;
           }
 
         // First accumulate the cost of this instruction.
         if (!Cost.IsFree) {
-          UnrolledCost += TTI.getUserCost(I);
+          unsigned UserCost = TTI.getUserCost(I);
+          UnrolledCost += UserCost;
           LLVM_DEBUG(dbgs() << "Adding cost of instruction (iteration "
-                            << Iteration << "): ");
+                            << Iteration << "): " << UserCost << " ");
           LLVM_DEBUG(I->dump());
         }
 
         // We must count the cost of every operand which is not free,
         // recursively. If we reach a loop PHI node, simply add it to the set
         // to be considered on the next iteration (backwards!).
         for (Value *Op : I->operands()) {
           // Check whether this operand is free due to being a constant or

llvm/test/Transforms/LoopUnroll/unrolled-inst-analyzer-pointers.ll

+; RUN: opt -loop-unroll -debug < %s 2>&1 | FileCheck %s
+
+; REQUIRES: asserts
+
+; Check that we simplify pointers outside of the loop for comparisons.
+; %cmp1.i.i is free when unrolling.
+
+define i32 @test_2_iters(i32 %a, i32 %b, i32 %c, i32 %d) optsize {
+; CHECK-LABEL: Loop Unroll: F[test_2_iters] Loop %loop
+; CHECK-NEXT:  Loop Size = 7
+; CHECK-NEXT:  Starting LoopUnroll profitability analysis...
+; CHECK-NEXT:   Analyzing iteration 0
+; CHECK-NEXT:   Analyzing iteration 1
+; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %spec.select.i.i = select i1 %cmp.i.i.i, i32* %incdec.ptr.i.i8, i32* %spec.select.i.i7
+; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %cmp.i.i.i = icmp slt i32 %.pre, %.pre3
+; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %.pre3 = load i32, i32* %incdec.ptr.i.i8, align 4
+; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %.pre = load i32, i32* %spec.select.i.i7, align 4
+; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %incdec.ptr.i.i = getelementptr inbounds i32, i32* %incdec.ptr.i.i8, i64 1
+; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %spec.select.i.i = select i1 %cmp.i.i.i, i32* %incdec.ptr.i.i8, i32* %spec.select.i.i7
+; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %cmp.i.i.i = icmp slt i32 %.pre, %.pre3
+; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %.pre3 = load i32, i32* %incdec.ptr.i.i8, align 4
+; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %.pre = load i32, i32* %spec.select.i.i7, align 4
+; CHECK-NEXT:  Analysis finished:
+; CHECK-NEXT:    UnrolledCost: 9, RolledDynamicCost: 14
+
+
+entry:
+  %ref.tmp = alloca [4 x i32], align 4
+  %0 = bitcast [4 x i32]* %ref.tmp to i8*
+  %arrayinit.begin = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 0
+  store i32 %a, i32* %arrayinit.begin, align 4
+  %arrayinit.element = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 1
+  store i32 %b, i32* %arrayinit.element, align 4
+  %arrayinit.element1 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 2
+  store i32 %c, i32* %arrayinit.element1, align 4
+  %arrayinit.element2 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 3
+  store i32 %d, i32* %arrayinit.element2, align 4
+  %add.ptr.i.i = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 4
+  %cmp.i.i.i4 = icmp slt i32 %a, %b
+  %spec.select.i.i5 = select i1 %cmp.i.i.i4, i32* %arrayinit.element, i32* %arrayinit.begin
+  %incdec.ptr.i.i6 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 2
+  br label %loop
+
+loop:                           ; preds = %entry, %loop
+  %incdec.ptr.i.i8 = phi i32* [ %incdec.ptr.i.i6, %entry ], [ %incdec.ptr.i.i, %loop ]
+  %spec.select.i.i7 = phi i32* [ %spec.select.i.i5, %entry ], [ %spec.select.i.i, %loop ]
+  %.pre = load i32, i32* %spec.select.i.i7, align 4
+  %.pre3 = load i32, i32* %incdec.ptr.i.i8, align 4
+  %cmp.i.i.i = icmp slt i32 %.pre, %.pre3
+  %spec.select.i.i = select i1 %cmp.i.i.i, i32* %incdec.ptr.i.i8, i32* %spec.select.i.i7
+  %incdec.ptr.i.i = getelementptr inbounds i32, i32* %incdec.ptr.i.i8, i64 1
+  %cmp1.i.i = icmp eq i32* %incdec.ptr.i.i, %add.ptr.i.i
+  br i1 %cmp1.i.i, label %exit, label %loop
+
+exit:                           ; preds = %loop
+  %1 = load i32, i32* %spec.select.i.i, align 4
+  ret i32 %1
+}