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

474

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

502

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?

1390

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

1392

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

test/Transforms/LoopReroll/ptrindvar.ll

43

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

464

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

478

Why declare NewSCEV here, instead of inside the if?

499

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

500

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

501

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.

515

This would read better as:

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

703

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

1390

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

1391

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)

1394

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.

1401

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.

1403

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.

1416

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

1424

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

1431

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

1391

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

371

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

466

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;"

480

return dyn_cast<SCEVConstant>(...);

481

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

482

return dyn_cast<SCEVConstant>(...)

493

Braces or no braces, not mixed braces.

1421

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

[• hulx2000]

lib/Transforms/Scalar/LoopRerollPass.cpp

466

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

478

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

1376

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

lib/Transforms/Scalar/LoopRerollPass.cpp

struct DAGRootTracker {
       /// Stage 1: Find all the DAG roots for the induction variable.
       bool findRoots();
       /// Stage 2: Validate if the found roots are valid.
       bool validate(ReductionTracker &Reductions);
       /// Stage 3: Assuming validate() returned true, perform the
       /// replacement.
       /// @param IterCount The maximum iteration count of L.
       void replace(const SCEV *IterCount);
 
     protected:
       typedef MapVector<Instruction*, SmallBitVector> UsesTy;
 
       bool findRootsRecursive(Instruction *IVU,
                               SmallInstructionSet SubsumedInsts);
       bool findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts);
       bool collectPossibleRoots(Instruction *Base,
                                 std::map<int64_t,Instruction*> &Roots);
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;
     int PrevIter = 0, BaseCount = 0, Count = 0;
     for (Instruction *J : PossibleReds[i]) {
       // Note that all instructions in the chain must have been found because
       // all instructions in the function must have been assigned to some
       // iteration.
       int Iter = PossibleRedIter[J];
       if (Iter != PrevIter && Iter != PrevIter + 1 &&
           !PossibleReds[i].getReducedValue()->isAssociative()) {
         DEBUG(dbgs() << "LRR: Out-of-order non-associative reduction: " <<
                         J << "\n");
         return false;
       }
 
       if (Iter != PrevIter) {
         if (Count != BaseCount) {
           DEBUG(dbgs() << "LRR: Iteration " << PrevIter <<
                 " reduction use count " << Count <<
                 " is not equal to the base use count " <<
                 BaseCount << "\n");
           return false;
         }
 
         Count = 0;
       }
 
       ++Count;
       if (Iter == 0)

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
+}