Expand loop reroll to handle loop with multiple induction variables and negative increment -part 2/3

[• hulx2000]

Summary

This patch enable LoopReroll to reroll loop with pointer induction
variable, such as:

while (buf !=end ) {
   S += buf[0];
   S += buf[1];
   buf +=2;
};

[hfinkel]

lib/Transforms/Scalar/LoopRerollPass.cpp

485 ↗

(On Diff #35688)

dyn_cast -> cast (you've already tested IV->getType()->isPointerTy()).

513 ↗

(On Diff #35688)

Don't you need an:

} else {
  break;
}

here. If the MulSCEV operands are a constant and some other expression, you don't always want to return the constant). Also, do you want to look through extensions and/or truncations here?

1340 ↗

(On Diff #35688)

I realize it was like this before, but we should name this something more explanatory than H.

1342 ↗

(On Diff #35688)

This is not really just 'One', how about we name it IncExpr, or IncrementExpr, etc.?

test/Transforms/LoopReroll/ptrindvar.ll

42 ↗

(On Diff #35688)

We should also have a test case where the pointer operand is being decremented.

[• hulx2000]

Thanks Hal for your prompt comments, I have updated the patch.

Regards

Lawrence Hu

[jmolloy]

Hi,

Thanks for working on this. I have plenty of comments :)

Cheers,

James

lib/Transforms/Scalar/LoopRerollPass.cpp

475 ↗

(On Diff #35916)

This only works for pointers, not for integer steps, so can this be renamed to make that clear?

489 ↗

(On Diff #35916)

Why declare NewSCEV here, instead of inside the if?

510 ↗

(On Diff #35916)

I think this debug statement might not be that useful - can it be removed when committed?

511 ↗

(On Diff #35916)

Braces {} around the else. if/elses should either both have braces or both not.

512 ↗

(On Diff #35916)

Surely these breaks should be "return nullptr"? What if the first operand is a constant but the second is not an unknown? or is an unknown but !isSizeOf()? then currently you'll return the first operand but actually this method should fail.

528 ↗

(On Diff #35916)

This would read better as:

if (!I->getType()->isIntegerTy() && !I->getType()->isPointerTy())

716 ↗

(On Diff #35916)

It might read better if both these ifs were squashed together?

1360 ↗

(On Diff #35916)

I really don't think "AddRecExpr" is any more helpful than "H". How about NewIVSCEV?

1361 ↗

(On Diff #35916)

I don't like that these are declared outside of scope and initialized to nullptr - this isn't C, we can declare variables where we use them! :) Please sink these into the if expression (you can just use auto too)

1364 ↗

(On Diff #35916)

You need to use cast<> instead of dyn_cast<> below. Instead, what you can do is this:

if (auto *PTy = dyn_cast<PointerTy>(Inst->getType())) {

then just use PTy below.

1371 ↗

(On Diff #35916)

I realise it was like this before, but I don't actually think we need this to be of type SCEVAddRecExpr. I think const SCEV * should be sufficient, which means you can remove this cast.

1373 ↗

(On Diff #35916)

I notice you've removed the compound braces around this but kept the comment... either keep the braces or remove the comment too, but give a rationale for removal if you're going to do that.

1386 ↗

(On Diff #35916)

This nullptr initialization again... can we get rid of these? I mean, there seems to be no reason to even touch this line :/

1394 ↗

(On Diff #35916)

This is disingenuous, as Minus1SCEV no longer holds minus one! The variable should be renamed.

1401 ↗

(On Diff #35916)

Please replace the braces you've removed here. Mixing one-liners and braces isn't LLVM style.

[• hulx2000]

Thanks, James, most of your concerns are addressed

lib/Transforms/Scalar/LoopRerollPass.cpp

1361 ↗

(On Diff #35916)

SizeOfExpr is used later, can't be declared in side if statement

[• hulx2000]

ping

[jmolloy]

Hi Lawrence,

I've got some more style complaints, but nothing major.

Cheers,

James

lib/Transforms/Scalar/LoopRerollPass.cpp

385 ↗

(On Diff #36169)

Please either document this or move it to the protected: section below where all the helpers are.

477 ↗

(On Diff #36169)

I don't think it's very useful to have this CIncSCEV variable. It'd be a lot neater (and more up to coding style) if instead of "CIncSCEV = ..; ...; return CIncSCEV;", just "return CIncSCEV;"

491 ↗

(On Diff #36169)

return dyn_cast<SCEVConstant>(...);

492 ↗

(On Diff #36169)

There should either be braces around both the if and else or around neither of them.

493 ↗

(On Diff #36169)

return dyn_cast<SCEVConstant>(...)

504 ↗

(On Diff #36169)

Braces or no braces, not mixed braces.

1386 ↗

(On Diff #36169)

Please assert(SizeOfExpr); here, to ensure it's initialized (if someone changes the if() above!)

[• hulx2000]

lib/Transforms/Scalar/LoopRerollPass.cpp

477 ↗

(On Diff #36169)

CIncSCEV is still needed later but I reduced the lifespan of it.

489 ↗

(On Diff #36169)

I didn't change this, The purpose of declaring NewSCEV here just to break the long statement into two shorter ones, and compiler will generate temp anyway even if I don't that.

[• hulx2000]

clang-format it

[• hulx2000]

ping

[hfinkel]

LGTM.

We should really get this enabled by default for functions when optimizing for size. Care to take a stab at that?

lib/Transforms/Scalar/LoopRerollPass.cpp

1370 ↗

(On Diff #38553)

No space after first "

[jmolloy]

Sorry, I didn't realise that according to phab I was blocking this. I saw Hal's LGTM and ignored it.

[• hulx2000]

Hi, Guys:

Very sorry that it took too long before I get back to this patch due to our release related work, now I need to rebase the code and fix the checking pattern of the testcase, could you please take a look again and give me a LGTM again? This time it will merged quickly.

Nice day.

Regards

Lawrence Hu

[• hulx2000]

fix a minor format issue

[• hulx2000]

Remove one space spotted by Hal

[hfinkel]

Still LGTM; please proceed.

[• hulx2000]

Thanks a lot for your quick response, Hal.

Have a nice day.

Regards

Lawrence Hu

llvm/trunk/lib/Transforms/Scalar/LoopRerollPass.cpp

protected:
       UsesTy::iterator nextInstr(int Val, UsesTy &In,
                                  const SmallInstructionSet &Exclude,
                                  UsesTy::iterator *StartI=nullptr);
       bool isBaseInst(Instruction *I);
       bool isRootInst(Instruction *I);
       bool instrDependsOn(Instruction *I,
                           UsesTy::iterator Start,
                           UsesTy::iterator End);
+      void replaceIV(Instruction *Inst, Instruction *IV, const SCEV *IterCount);
 
       LoopReroll *Parent;
 
       // Members of Parent, replicated here for brevity.
       Loop *L;
       ScalarEvolution *SE;
       AliasAnalysis *AA;
       TargetLibraryInfo *TLI;

 static bool hasUsesOutsideLoop(Instruction *I, Loop *L) {
   for (User *U : I->users()) {
     if (!L->contains(cast<Instruction>(U)))
       return true;
   }
   return false;
 }
 
+static const SCEVConstant *getIncrmentFactorSCEV(ScalarEvolution *SE,
+                                                 const SCEV *SCEVExpr,
+                                                 Instruction &IV) {
+  const SCEVMulExpr *MulSCEV = dyn_cast<SCEVMulExpr>(SCEVExpr);
+
+  // If StepRecurrence of a SCEVExpr is a constant (c1 * c2, c2 = sizeof(ptr)),
+  // Return c1.
+  if (!MulSCEV && IV.getType()->isPointerTy())
+    if (const SCEVConstant *IncSCEV = dyn_cast<SCEVConstant>(SCEVExpr)) {
+      const PointerType *PTy = cast<PointerType>(IV.getType());
+      Type *ElTy = PTy->getElementType();
+      const SCEV *SizeOfExpr =
+          SE->getSizeOfExpr(SE->getEffectiveSCEVType(IV.getType()), ElTy);
+      if (IncSCEV->getValue()->getValue().isNegative()) {
+        const SCEV *NewSCEV =
+            SE->getUDivExpr(SE->getNegativeSCEV(SCEVExpr), SizeOfExpr);
+        return dyn_cast<SCEVConstant>(SE->getNegativeSCEV(NewSCEV));
+      } else {
+        return dyn_cast<SCEVConstant>(SE->getUDivExpr(SCEVExpr, SizeOfExpr));
+      }
+    }
+
+  if (!MulSCEV)
+    return nullptr;
+
+  // If StepRecurrence of a SCEVExpr is a c * sizeof(x), where c is constant,
+  // Return c.
+  const SCEVConstant *CIncSCEV = nullptr;
+  for (const SCEV *Operand : MulSCEV->operands()) {
+    if (const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Operand)) {
+      CIncSCEV = Constant;
+    } else if (const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Operand)) {
+      Type *AllocTy;
+      if (!Unknown->isSizeOf(AllocTy))
+        break;
+    } else {
+      return nullptr;
+    }
+  }
+  return CIncSCEV;
+}
+
 // Collect the list of loop induction variables with respect to which it might
 // be possible to reroll the loop.
 void LoopReroll::collectPossibleIVs(Loop *L,
                                     SmallInstructionVector &PossibleIVs) {
   BasicBlock *Header = L->getHeader();
   for (BasicBlock::iterator I = Header->begin(),
        IE = Header->getFirstInsertionPt(); I != IE; ++I) {
     if (!isa<PHINode>(I))
       continue;
-    if (!I->getType()->isIntegerTy())
+    if (!I->getType()->isIntegerTy() && !I->getType()->isPointerTy())
       continue;
 
     if (const SCEVAddRecExpr *PHISCEV =
             dyn_cast<SCEVAddRecExpr>(SE->getSCEV(&*I))) {
       if (PHISCEV->getLoop() != L)
         continue;
       if (!PHISCEV->isAffine())
         continue;
-      if (const SCEVConstant *IncSCEV =
-          dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE))) {
-        const APInt &AInt = IncSCEV->getAPInt().abs();
+      const SCEVConstant *IncSCEV = nullptr;
+      if (I->getType()->isPointerTy())
+        IncSCEV =
+            getIncrmentFactorSCEV(SE, PHISCEV->getStepRecurrence(*SE), *I);
+      else
+        IncSCEV = dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE));
+      if (IncSCEV) {
+        const APInt &AInt = IncSCEV->getValue()->getValue().abs();
         if (IncSCEV->getValue()->isZero() || AInt.uge(MaxInc))
           continue;
         IVToIncMap[&*I] = IncSCEV->getValue()->getSExtValue();
         DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << *PHISCEV
                      << "\n");
         PossibleIVs.push_back(&*I);
       }
     }
case Instruction::SExt:
       return true;
     }
   }
   return false;
 }
 
 static bool isLoopIncrement(User *U, Instruction *IV) {
   BinaryOperator *BO = dyn_cast<BinaryOperator>(U);
-  if (!BO || BO->getOpcode() != Instruction::Add)
+
+  if ((BO && BO->getOpcode() != Instruction::Add) ||
+      (!BO && !isa<GetElementPtrInst>(U)))
     return false;
 
-  for (auto *UU : BO->users()) {
+  for (auto *UU : U->users()) {
     PHINode *PN = dyn_cast<PHINode>(UU);
     if (PN && PN == IV)
       return true;
   }
   return false;
 }
 
 bool LoopReroll::DAGRootTracker::
if (I > 0 && I < IL_All) {
       Instruction *D = &*J;
       DEBUG(dbgs() << "LRR: removing: " << *D << "\n");
       D->eraseFromParent();
       continue;
     }
 
     ++J;
   }
-  bool Negative = IVToIncMap[IV] < 0;
-  const DataLayout &DL = Header->getModule()->getDataLayout();
 
   // We need to create a new induction variable for each different BaseInst.
-  for (auto &DRS : RootSets) {
+  for (auto &DRS : RootSets)
     // Insert the new induction variable.
-    const SCEVAddRecExpr *RealIVSCEV =
-      cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
-    const SCEV *Start = RealIVSCEV->getStart();
-    const SCEVAddRecExpr *H = cast<SCEVAddRecExpr>(SE->getAddRecExpr(
-        Start, SE->getConstant(RealIVSCEV->getType(), Negative ? -1 : 1), L,
-        SCEV::FlagAnyWrap));
-    { // Limit the lifetime of SCEVExpander.
-      SCEVExpander Expander(*SE, DL, "reroll");
-      Value *NewIV = Expander.expandCodeFor(H, IV->getType(), &Header->front());
+    replaceIV(DRS.BaseInst, IV, IterCount);
+
+  SimplifyInstructionsInBlock(Header, TLI);
+  DeleteDeadPHIs(Header, TLI);
+}
+
+void LoopReroll::DAGRootTracker::replaceIV(Instruction *Inst,
+                                           Instruction *InstIV,
+                                           const SCEV *IterCount) {
+  BasicBlock *Header = L->getHeader();
+  int64_t Inc = IVToIncMap[InstIV];
+  bool Negative = Inc < 0;
+
+  const SCEVAddRecExpr *RealIVSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(Inst));
+
+  const SCEV *SizeOfExpr = nullptr;
+  const SCEV *IncrExpr =
+      SE->getConstant(RealIVSCEV->getType(), Negative ? -1 : 1);
+  if (auto *PTy = dyn_cast<PointerType>(Inst->getType())) {
+    Type *ElTy = PTy->getElementType();
+    SizeOfExpr =
+        SE->getSizeOfExpr(SE->getEffectiveSCEVType(Inst->getType()), ElTy);
+    IncrExpr = SE->getMulExpr(IncrExpr, SizeOfExpr);
+  }
+  const SCEV *NewIVSCEV =
+      SE->getAddRecExpr(Start, IncrExpr, L, SCEV::FlagAnyWrap);
+
+    const DataLayout &DL = Header->getModule()->getDataLayout();
+    Value *NewIV =
+        Expander.expandCodeFor(NewIVSCEV, InstIV->getType(), &Header->front());
 
-      for (auto &KV : Uses) {
-        if (KV.second.find_first() == 0)
-          KV.first->replaceUsesOfWith(DRS.BaseInst, NewIV);
-      }
+    for (auto &KV : Uses)
+        KV.first->replaceUsesOfWith(Inst, NewIV);
 
-      if (BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator())) {
-        // FIXME: Why do we need this check?
-        if (Uses[BI].find_first() == IL_All) {
-          const SCEV *ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE);
 
-          // Iteration count SCEV minus 1
-          const SCEV *ICMinus1SCEV = SE->getMinusSCEV(
-              ICSCEV, SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1));
-
-          Value *ICMinus1; // Iteration count minus 1
-          if (isa<SCEVConstant>(ICMinus1SCEV)) {
-            ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(), BI);
-          } else {
-            BasicBlock *Preheader = L->getLoopPreheader();
-            if (!Preheader)
-              Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
-
-            ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(),
-                                              Preheader->getTerminator());
-          }
+        // Iteration count SCEV minus or plus 1
+        const SCEV *MinusPlus1SCEV =
+            SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1);
+        if (Inst->getType()->isPointerTy()) {
+          assert(SizeOfExpr && "SizeOfExpr is not initialized");
+          MinusPlus1SCEV = SE->getMulExpr(MinusPlus1SCEV, SizeOfExpr);
+        }
+
+        const SCEV *ICMinusPlus1SCEV = SE->getMinusSCEV(ICSCEV, MinusPlus1SCEV);
+        // Iteration count minus 1
+        Value *ICMinusPlus1 = nullptr;
+        if (isa<SCEVConstant>(ICMinusPlus1SCEV)) {
+          ICMinusPlus1 =
+              Expander.expandCodeFor(ICMinusPlus1SCEV, NewIV->getType(), BI);
+          ICMinusPlus1 = Expander.expandCodeFor(
+              ICMinusPlus1SCEV, NewIV->getType(), Preheader->getTerminator());
 
-          Value *Cond =
-            new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, ICMinus1, "exitcond");
-          BI->setCondition(Cond);
+            new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, ICMinusPlus1, "exitcond");
 
-          if (BI->getSuccessor(1) != Header)
-            BI->swapSuccessors();
-        }
-      }
-    }
-  }
 
-  SimplifyInstructionsInBlock(Header, TLI);
-  DeleteDeadPHIs(Header, TLI);
-}
-
 // Validate the selected reductions. All iterations must have an isomorphic
 // part of the reduction chain and, for non-associative reductions, the chain
 // entries must appear in order.
 bool LoopReroll::ReductionTracker::validateSelected() {
   // For a non-associative reduction, the chain entries must appear in order.
   for (DenseSet<int>::iterator RI = Reds.begin(), RIE = Reds.end();
        RI != RIE; ++RI) {
     int i = *RI;

llvm/trunk/test/Transforms/LoopReroll/ptrindvar.ll

+; RUN: opt -S  -loop-reroll   %s | FileCheck %s
+target triple = "aarch64--linux-gnu"
+
+define i32 @test(i32* readonly %buf, i32* readnone %end) #0 {
+entry:
+  %cmp.9 = icmp eq i32* %buf, %end
+  br i1 %cmp.9, label %while.end, label %while.body.preheader
+
+while.body.preheader:
+  br label %while.body
+
+while.body:
+;CHECK-LABEL: while.body:
+;CHECK-NEXT:    %indvar = phi i64 [ %indvar.next, %while.body ], [ 0, %while.body.preheader ]
+;CHECK-NEXT:    %S.011 = phi i32 [ %add, %while.body ], [ undef, %while.body.preheader ]
+;CHECK-NEXT:    %scevgep = getelementptr i32, i32* %buf, i64 %indvar
+;CHECK-NEXT:    %4 = load i32, i32* %scevgep, align 4
+;CHECK-NEXT:    %add = add nsw i32 %4, %S.011
+;CHECK-NEXT:    %indvar.next = add i64 %indvar, 1
+;CHECK-NEXT:    %exitcond = icmp eq i32* %scevgep, %scevgep5
+;CHECK-NEXT:    br i1 %exitcond, label %while.end.loopexit, label %while.body
+
+  %S.011 = phi i32 [ %add2, %while.body ], [ undef, %while.body.preheader ]
+  %buf.addr.010 = phi i32* [ %add.ptr, %while.body ], [ %buf, %while.body.preheader ]
+  %0 = load i32, i32* %buf.addr.010, align 4
+  %add = add nsw i32 %0, %S.011
+  %arrayidx1 = getelementptr inbounds i32, i32* %buf.addr.010, i64 1
+  %1 = load i32, i32* %arrayidx1, align 4
+  %add2 = add nsw i32 %add, %1
+  %add.ptr = getelementptr inbounds i32, i32* %buf.addr.010, i64 2
+  %cmp = icmp eq i32* %add.ptr, %end
+  br i1 %cmp, label %while.end.loopexit, label %while.body
+
+while.end.loopexit:
+  %add2.lcssa = phi i32 [ %add2, %while.body ]
+  br label %while.end
+
+while.end:
+  %S.0.lcssa = phi i32 [ undef, %entry ], [ %add2.lcssa, %while.end.loopexit ]
+  ret i32 %S.0.lcssa
+}
+
+define i32 @test2(i32* readonly %buf, i32* readnone %end) #0 {
+entry:
+  %cmp.9 = icmp eq i32* %buf, %end
+  br i1 %cmp.9, label %while.end, label %while.body.preheader
+
+while.body.preheader:
+  br label %while.body
+
+while.body:
+;CHECK-LABEL: while.body:
+;CHECK-NEXT:    %indvar = phi i64 [ %indvar.next, %while.body ], [ 0, %while.body.preheader ]
+;CHECK-NEXT:    %S.011 = phi i32 [ %add, %while.body ], [ undef, %while.body.preheader ]
+;CHECK-NEXT:    %4 = mul i64 %indvar, -1
+;CHECK-NEXT:    %scevgep = getelementptr i32, i32* %buf, i64 %4
+;CHECK-NEXT:    %5 = load i32, i32* %scevgep, align 4
+;CHECK-NEXT:    %add = add nsw i32 %5, %S.011
+;CHECK-NEXT:    %indvar.next = add i64 %indvar, 1
+;CHECK-NEXT:    %exitcond = icmp eq i32* %scevgep, %scevgep5
+;CHECK-NEXT:    br i1 %exitcond, label %while.end.loopexit, label %while.body
+
+  %S.011 = phi i32 [ %add2, %while.body ], [ undef, %while.body.preheader ]
+  %buf.addr.010 = phi i32* [ %add.ptr, %while.body ], [ %buf, %while.body.preheader ]
+  %0 = load i32, i32* %buf.addr.010, align 4
+  %add = add nsw i32 %0, %S.011
+  %arrayidx1 = getelementptr inbounds i32, i32* %buf.addr.010, i64 -1
+  %1 = load i32, i32* %arrayidx1, align 4
+  %add2 = add nsw i32 %add, %1
+  %add.ptr = getelementptr inbounds i32, i32* %buf.addr.010, i64 -2
+  %cmp = icmp eq i32* %add.ptr, %end
+  br i1 %cmp, label %while.end.loopexit, label %while.body
+
+while.end.loopexit:
+  %add2.lcssa = phi i32 [ %add2, %while.body ]
+  br label %while.end
+
+while.end:
+  %S.0.lcssa = phi i32 [ undef, %entry ], [ %add2.lcssa, %while.end.loopexit ]
+  ret i32 %S.0.lcssa
+}