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

[• hulx2000]

Summary

Handle loop with negtive induction variable increment

This patch extends LoopReroll pass to hand the loops which
are similar to the following:

      while (len > 1) {
            sum4 += buf[len];
            sum4 += buf[len-1];
            len -= 2;
        }

Basically, negative loop increment.

The original patch will be split into 3, that's the first one.

[• hulx2000]

handle some of Ana's comments

[hfinkel]

Please enhance your patch description to explain, not just what he patch enables (which you've done), but generically how it does it. There is a bunch of new code here, and it will be good to get a high-level overview of what it does (and I'd expect such a description to appear in the commit message anyway, so this is not "just for review").

Please upload the patch with full context, see:

http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

for instructions.

lib/Transforms/Scalar/LoopRerollPass.cpp

447

We generally abbreviate Instruction to Inst, not Insn. Please rename this function.

Also, please comment what this function does. It is certainly more than just determining if the instruction is a comparison of some kind.

[• hulx2000]

Thanks, Hal, sorry for the delay, just saw your comments this morning

[jmolloy]

Hi,

I'm afraid there are too many different changes bundled together here for me to really review. Please could you split this out into:

1. Adding negative offset support
2. Adding pointer induction variable support
3. Adding multiple induction variable support.

Cheers,

James

[• hulx2000]

Hi, James:

Thank you very much for your comment.

Those patches are bundled together because they are strongly correlated, for an example, if I add support for pointer induction variable, I must support multiple induction variable, otherwise a lot of test will be broken.

I will see if I can split it into three with some extra safety check.

Regards

Lawrence Hu

[• hulx2000]

remove white spaces

[• hulx2000]

upload the full context diff

[jmolloy]

Hi,

Thanks for making these changes - it looks much better now. A few comments still.

Cheers,

James

lib/Transforms/Scalar/LoopRerollPass.cpp

496

I think this line and line 503 can both be merged, and put on line 505. There's no need to ZExt this one and SExt the other - both can be SExted.

499

This can be much simpler. You can just use APInt::abs():

AInt = AInt.abs();
if (AInt.isZero() || AInt.uge(MaxInc))
  continue;
IVToIncMap[I] = AInt.getSExtValue();

677

I'm not sure how adding GEP support here relates to negative values. Was this an accidentally added hunk?

725

I think you need to use std::abs() above, on line 721 too. Otherwise the guard on line 721 is useless.

1280

Double semicolon (;;).

Also, you can squash this into just one statement:

bool Negative = IVToIncMap[IV] < 0;

[• hulx2000]

lib/Transforms/Scalar/LoopRerollPass.cpp

677

Ｏｈ，　ｓｏｒｒｙ，　ｔｈｉｓ　ｉｓ　ｌｅｆｔ　ｏｖｅｒ　ｗｈｅｎ　Ｉ　ｓｐｌｉｔ　ｍｙ　ｐａｔｃｈ，　ｉｔ　ｉｓ　ｒｅｑｕｉｒｅ　ｆｏｒ　ｐｏｉｎｔｅｒ　ｉｎｄｕｃｔｉｏｎ　ｖａｒｉａｂｌｅ　ｔｈｏｕｇｈ，　ｂｕｔ　Ｉ　ｃａｎ　ｒｅｍｏｖｅ　ｉｔ　ｆｏｒ　ｎｏｗ．

Ｗｉｌｌ　ｆｉｘ　ｔｈｅ　ｒｅｓｔ，　ｔｈａｎｋｓ．``

[• hulx2000]

Thanks, James for your valuable comments.

I have updated my patch.

[jmolloy]

Hi,

This is looking a lot better, thanks!

James

lib/Transforms/Scalar/LoopRerollPass.cpp

372

This should be const, to notify a user that it is not captured or modified.

437

Please add a docstring, like all other variables.

664

I think this is still relating to adding GEP support, is it not?

test/Transforms/LoopReroll/negative.ll

17

This test will fail in release builds because registers will lose their names. Please either make it not rely on named variables or add a

; REQUIRES: asserts

to the top (please also check the line above is actually correct, I've just pasted it from memory!)

[• hulx2000]

Thanks Jame.

Sorry that missed a few thing last time, this time should be better.

Best, I didn't change the const thing, compiler complains, and I didn't see testcase asset in release build, I tried pass, it is fine, are yours a special build?

Regards

Lawrence Hu

[• hulx2000]

lib/Transforms/Scalar/LoopRerollPass.cpp

372

unfortunately, compiler always contains if I do that.

[jmolloy]

LGTM, thanks for making those changes.

If you don't add REQUIRES: asserts, you'll get complaints on the list when this goes in. I forget exactly which cmake variable you change to remove value names completely, but rest assured there are people who use it - I've found that out myself :)

Cheers,

James

[• hulx2000]

Great, Thanks, James.

I will add Assert from the next test and on.

Would you mind to commit it for you so I can start the next one? I don't have commit right yet.

[• hulx2000]

typo: for me.

[mzolotukhin]

lib/Transforms/Scalar/LoopRerollPass.cpp

169

s/it's/its/

172

I'd rather commit this typo fix immediately when I found it (no pre-commit review is required for this kind of changes).

438

s/it's/its/

665

No need to add a blank line here.

1268

Redundant whitespaces.

test/Transforms/LoopReroll/negative.ll

20–28

Do we really need to check that we generate *exactly* these statements? Would it be possible to look for, say, a specific branch (or absence of the branch) - this would make the test much more stable.

30–39

Do we really need to have this body, or would the test work with almost empty loop?
Like this:

while (len > 1) {
            len -= 2;
        }

instead of

while (len > 1) {
            sum4 += buf[len];
            sum4 += buf[len-1];
            len -= 2;
        }

Since you only run loop-reroll, it shouldn't be collapsed to nop.

54–55

Maybe just return i32 %sum4.0.lcssa to get rid of the goo function?

[• hulx2000]

test/Transforms/LoopReroll/negative.ll

30–39

The simple loop won't do enough test for the logic in LoopReroll

[• hulx2000]

Addressed Michael's comment

[• hulx2000]

Hi, Michael

Could you please accept it if you have now further comment? It will be easier for me to prepare next two patches.

Thanks.

Lawrence Hu

[• hulx2000]

Hi, Hal:

Do you have any other comments about this patch, could you please accept it if not?

Thanks

Lawrence Hu

[hfinkel]

lib/Transforms/Scalar/LoopRerollPass.cpp

1278

Line is too long.

1296

Line is too long.

test/Transforms/LoopReroll/negative.ll

3

Remove this. There is no valid reason why a test like this needs to be asserts-mode only. And it is really important that we have as much testing as possible for the NDEBUG builds (even if that were to require using more regexes in the test). That having been said, what James said was not quite right. The NDEBUG opt does not remove all variable names (certain passes did that, or used to, but that's another matter). What is true is that NDEBUG Clang does not produce variable names for locals.

[• hulx2000]

Thanks, Hal,

Updated.

Regards

[hfinkel]

LGTM now too, thanks!

[• hulx2000]

committed as git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@243171 91177308-0d34-0410-b5e6-96231b3b80d8

lib/Transforms/Scalar/LoopRerollPass.cpp

     typedef SmallVector<Instruction *, 16> SmallInstructionVector;
     typedef SmallSet<Instruction *, 16>   SmallInstructionSet;
 
-    // A chain of isomorphic instructions, indentified by a single-use PHI,
+    DenseMap<Instruction *, int64_t> IVToIncMap;
+
+    // A chain of isomorphic instructions, identified by a single-use PHI,
     // representing a reduction. Only the last value may be used outside the
     // loop.
     struct SimpleLoopReduction {

     //   x[i*3+1] = y2
     //   x[i*3+2] = y3
     //
-    //   Base instruction -> i*3               
+    //   Base instruction -> i*3
     //                    +---+----+
     //                   /    |     \
     //               ST[y1]  +1     +2  <-- Roots

     struct DAGRootTracker {
       DAGRootTracker(LoopReroll *Parent, Loop *L, Instruction *IV,
                      ScalarEvolution *SE, AliasAnalysis *AA,
-                     TargetLibraryInfo *TLI)
-          : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), IV(IV) {}
+                     TargetLibraryInfo *TLI,
+                     DenseMap<Instruction *, int64_t> &IncrMap)
+          : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), IV(IV),
+            IVToIncMap(IncrMap) {}
 
       /// Stage 1: Find all the DAG roots for the induction variable.
       bool findRoots();

       // The loop induction variable.
       Instruction *IV;
       // Loop step amount.
-      uint64_t Inc;
+      int64_t Inc;
       // Loop reroll count; if Inc == 1, this records the scaling applied
       // to the indvar: a[i*2+0] = ...; a[i*2+1] = ... ;
       // If Inc is not 1, Scale = Inc.

       // they are used in (or specially, IL_All for instructions
       // used in the loop increment mechanism).
       UsesTy Uses;
+      DenseMap<Instruction *, int64_t> &IVToIncMap;
     };
 
     void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs);

         continue;
       if (const SCEVConstant *IncSCEV =
           dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE))) {
-        if (!IncSCEV->getValue()->getValue().isStrictlyPositive())
-          continue;
+        const APInt &AInt = IncSCEV->getValue()->getValue();
+        if (AInt.isStrictlyPositive()) {
           if (IncSCEV->getValue()->uge(MaxInc))
             continue;
+          IVToIncMap[I] = IncSCEV->getValue()->getZExtValue();
+        } else if (AInt.isNegative()) {
+          const SCEVConstant *PIncSCEV =
+              dyn_cast<SCEVConstant>(SE->getNegativeSCEV(IncSCEV));
+          if (!PIncSCEV || PIncSCEV->getValue()->uge(MaxInc))
+            continue;
+          IVToIncMap[I] = IncSCEV->getValue()->getSExtValue();
+        }
 
         DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " <<
               *PHISCEV << "\n");

 
 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)
+    return false;
+
+  if (!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;

       // No duplicates, please.
       return false;
 
-    // FIXME: Add support for negative values.
-    if (V < 0) {
-      DEBUG(dbgs() << "LRR: Aborting due to negative value: " << V << "\n");
-      return false;
-    }
-
-    Roots[V] = cast<Instruction>(I);
+    Roots[std::abs(V)] = cast<Instruction>(I);
   }
 
   if (Roots.empty())

   unsigned NumBaseUses = BaseUsers.size();
   if (NumBaseUses == 0)
     NumBaseUses = Roots.begin()->second->getNumUses();
-  
   // Check that every node has the same number of users.
   for (auto &KV : Roots) {
     if (KV.first == 0)

     }
   }
 
-  return true; 
+  return true;
 }
 
 bool LoopReroll::DAGRootTracker::

   if (!collectPossibleRoots(IVU, V))
     return false;
 
-  // If we didn't get a root for index zero, then IVU must be 
+  // If we didn't get a root for index zero, then IVU must be
   // subsumed.
   if (V.find(0) == V.end())
     SubsumedInsts.insert(IVU);

 }
 
 bool LoopReroll::DAGRootTracker::findRoots() {
-
-  const SCEVAddRecExpr *RealIVSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(IV));
-  Inc = cast<SCEVConstant>(RealIVSCEV->getOperand(1))->
-    getValue()->getZExtValue();
+  Inc = IVToIncMap[IV];
 
   assert(RootSets.empty() && "Unclean state!");
-  if (Inc == 1) {
+  if (std::abs(Inc) == 1) {
     for (auto *IVU : IV->users()) {
       if (isLoopIncrement(IVU, IV))
         LoopIncs.push_back(cast<Instruction>(IVU));

                 " vs. " << *RootInst << "\n");
           return false;
         }
-        
         RootIt = TryIt;
         RootInst = TryIt->first;
       }
 
       // All instructions between the last root and this root
-      // may belong to some other iteration. If they belong to a 
+      // may belong to some other iteration. If they belong to a
       // future iteration, then they're dangerous to alias with.
-      // 
+      //
       // Note that because we allow a limited amount of flexibility in the order
       // that we visit nodes, LastRootIt might be *before* RootIt, in which
       // case we've already checked this set of instructions so we shouldn't

 
     ++J;
   }
+  int64_t Inc = IVToIncMap[IV];
+  bool Negative = Inc < 0;
+  ;
   const DataLayout &DL = Header->getModule()->getDataLayout();
 
   // We need to create a new induction variable for each different BaseInst.

     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(), 1),
-                         L, SCEV::FlagAnyWrap));
+    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->begin());

           const SCEV *ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE);
 
           // Iteration count SCEV minus 1
-          const SCEV *ICMinus1SCEV =
-            SE->getMinusSCEV(ICSCEV, SE->getConstant(ICSCEV->getType(), 1));
+          const SCEV *ICMinus1SCEV = SE->getMinusSCEV(
+              ICSCEV, SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1));
 
           Value *ICMinus1; // Iteration count minus 1
           if (isa<SCEVConstant>(ICMinus1SCEV)) {

 bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
                         const SCEV *IterCount,
                         ReductionTracker &Reductions) {
-  DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI);
+  DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, IVToIncMap);
 
   if (!DAGRoots.findRoots())
     return false;
   DEBUG(dbgs() << "LRR: Found all root induction increments for: " <<
                   *IV << "\n");
-  
   if (!DAGRoots.validate(Reductions))
     return false;
   if (!Reductions.validateSelected())

   // First, we need to find the induction variable with respect to which we can
   // reroll (there may be several possible options).
   SmallInstructionVector PossibleIVs;
+  IVToIncMap.clear();
   collectPossibleIVs(L, PossibleIVs);
 
   if (PossibleIVs.empty()) {

test/Transforms/LoopReroll/negative.ll

+; RUN: opt -S  -loop-reroll   %s | FileCheck %s
+target triple = "aarch64--linux-gnu"
+@buf = global [16 x i8] c"\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A", align 1
+declare i32 @goo(i32)
+
+define i32 @test1(i32 %len, i8* nocapture readonly %buf) #0 {
+entry:
+  %cmp.13 = icmp sgt i32 %len, 1
+  br i1 %cmp.13, label %while.body.lr.ph, label %while.end
+
+while.body.lr.ph:                                 ; preds = %entry
+  br label %while.body
+
+while.body:
+;CHECK-LABEL: while.body:
+;CHECK-NEXT:    %indvar = phi i32 [ %indvar.next, %while.body ], [ 0, %while.body.lr.ph ]
+;CHECK-NEXT:    %sum4.015 = phi i64 [ 0, %while.body.lr.ph ], [ %add, %while.body ]
+;CHECK-NEXT:    %5 = mul i32 %indvar, -1
+;CHECK-NEXT:    %6 = add i32 %len, %5
+;CHECK-NEXT:    %idxprom = sext i32 %6 to i64
+;CHECK-NEXT:    %arrayidx = getelementptr inbounds i8, i8* %buf, i64 %idxprom
+;CHECK-NEXT:    %7 = load i8, i8* %arrayidx, align 1
+;CHECK-NEXT:    %conv = zext i8 %7 to i64
+;CHECK-NEXT:    %add = add i64 %conv, %sum4.015
+;CHECK-NEXT:    %indvar.next = add i32 %indvar, 1
+;CHECK-NEXT:    %exitcond = icmp eq i32 %6, %4
+;CHECK-NEXT:    br i1 %exitcond, label %while.cond.while.end_crit_edge, label %while.body
+
+  %sum4.015 = phi i64 [ 0, %while.body.lr.ph ], [ %add4, %while.body ]
+  %len.addr.014 = phi i32 [ %len, %while.body.lr.ph ], [ %sub5, %while.body ]
+  %idxprom = sext i32 %len.addr.014 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %buf, i64 %idxprom
+  %0 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %0 to i64
+  %add = add i64 %conv, %sum4.015
+  %sub = add nsw i32 %len.addr.014, -1
+  %idxprom1 = sext i32 %sub to i64
+  %arrayidx2 = getelementptr inbounds i8, i8* %buf, i64 %idxprom1
+  %1 = load i8, i8* %arrayidx2, align 1
+  %conv3 = zext i8 %1 to i64
+  %add4 = add i64 %add, %conv3
+  %sub5 = add nsw i32 %len.addr.014, -2
+  %cmp = icmp sgt i32 %sub5, 1
+  br i1 %cmp, label %while.body, label %while.cond.while.end_crit_edge
+
+while.cond.while.end_crit_edge:                   ; preds = %while.body
+  %add4.lcssa = phi i64 [ %add4, %while.body ]
+  %phitmp = trunc i64 %add4.lcssa to i32
+  br label %while.end
+
+while.end:                                        ; preds = %while.cond.while.end_crit_edge, %entry
+  %sum4.0.lcssa = phi i32 [ %phitmp, %while.cond.while.end_crit_edge ], [ 0, %entry ]
+  %call = tail call i32 @goo(i32 %sum4.0.lcssa)
+  unreachable
+}
+