[LoopInterchange] Enable loop interchange with multiple outer loop indvars

[congzhe]

Summary

This is a feature patch.

Currently loop interchange only works when the outer loop has one induction variable. This patch extends it to work with more than one outer induction variables. After interchange, reduction phis in the original outer loop header should be moved to the original inner loop header, which becomes the outer loop header. All other phis, i.e., induction phis, stay in the original position.

[congzhe]

gentle ping @Whitney @bmahjour

[bmahjour]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

841

this imposes an ordering constraint...the OuterLoopInduction member variable is invalid until we get here. It would be cleaner to introduce an initialization step before calling either urrentLimitations() or adjustLoopBranches().

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

14

can these tests be changed to something more canonical (eg not relying on zero initialization of globals, and signed integer wrap for termination)?

[congzhe]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

14

Thanks for your comment! While working on the revision, can I clarify that regarding "signed integer wrap for termination", did you suggest to remove those nsw flags that are involved in the loop exit condition?

[bmahjour]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

14

Removing the nsw flags would make things worse, since the loop seems to rely on sign wrap to terminate. The way it's written the loop body won't even get entered since the initial values of c and e would fail the c && e check. What I'm asking is to change this test to a more typical counted loop format, eg:

for (int i1 = 0, i2 = 0; i1 > n && i2 > m; i1++, i2++)
  for (int j1 = m; j >= 0;  j--)
     ...

[congzhe]

Thanks for the comments, I've updated the patch accordingly. @bmahjour

The updates include:

1. Reworked on test cases, made them cleaner by renaming IR variable names and removing unnecessary instructions, etc. Specifically, I made the tests more canonical by not relying on zero initialization of globals but using standard PHI nodes with proper intial values. The loop exit conditions are also updated and now cover different scenarios.

2. Updated the code in LoopInterchange.cpp. Especially, after investigation I now find OuterLoopInductions is not necessarily needed and the current pass trivially supports multiple outer loop indvars already. This is resulted from my previous patch https://reviews.llvm.org/D102743 which has properly handled PHI node movements.

So I removed OuterLoopInduction which I added to this patch earlier.

I'd appreciate any further comment, thanks in advance.

[bmahjour]

Looks good....I just added a couple more comments in the tests. Once they are addressed, I'll accept this revision.

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

20

Please use CHECK-NEXT and show full context

102

Same comment as above.

[congzhe]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

20

Thanks for the comment! I intentionally used "CHECK" instead of "CHECK-NEXT" since some time down the road even some trivial change in the pass could fail "CHECK-NEXT" (and one needs to update the tests accordingly), hence I extracted the essential IR I'd like to check using "CHECK".

But your comment also makes sense, I'll use "CHECK-NEXT" and update them shortly.

[congzhe]

Updated test cases by using "CHECK-NEXT".

[bmahjour]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

20

I have had the same dilemma as well, but based on feedback from others, I'm now realizing the benefit of having full context in the LIT tests. It makes it much easier to follow the structure and semantics of the generated code. In case of future changes, the tests can be trivially regenerated (via utils/update_test_checks.py).

[bmahjour]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

19

based on these checks, it doesn't look like the loops have been interchanged!

[congzhe]

Updated test cases.

My apologies, my last update used "update_test_checks.py" with a wrong opt binary.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

public:
   bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
 
   bool currentLimitations();
 
   const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
     return OuterInnerReductions;
   }
 
+  const SmallVectorImpl<PHINode *> &getOuterLoopInductions() const {
+    return OuterLoopInductions;
+  }
+
 private:
   bool tightlyNested(Loop *Outer, Loop *Inner);
   bool containsUnsafeInstructions(BasicBlock *BB);
 
   /// Discover induction and reduction PHIs in the header of \p L. Induction
   /// PHIs are added to \p Inductions, reductions are added to
   /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
   /// to be passed as \p InnerLoop.
   bool findInductionAndReductions(Loop *L,
                                   SmallVector<PHINode *, 8> &Inductions,
                                   Loop *InnerLoop);
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   ScalarEvolution *SE;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 
   /// Set of reduction PHIs taking part of a reduction across the inner and
   /// outer loop.
   SmallPtrSet<PHINode *, 4> OuterInnerReductions;
+
+  /// Set of outer loop induction PHIs.
+  SmallVector<PHINode *, 8> OuterLoopInductions;
 };
 
 /// LoopInterchangeProfitability checks if it is profitable to interchange the
 /// loop.
 class LoopInterchangeProfitability {
 public:
   LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                                OptimizationRemarkEmitter *ORE)
ORE->emit([&]() {
                                       OuterLoop->getStartLoc(),
                                       OuterLoop->getHeader())
              << "Only outer loops with induction or reduction PHI nodes can be"
                 " interchanged currently.";
     });
     return true;
   }
 
-  // TODO: Currently we handle only loops with 1 induction variable.
-  if (Inductions.size() != 1) {
-    LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "
-                      << "supported currently.\n");
-    ORE->emit([&]() {
-      return OptimizationRemarkMissed(DEBUG_TYPE, "MultiIndutionOuter",
-                                      OuterLoop->getStartLoc(),
-                                      OuterLoop->getHeader())
-             << "Only outer loops with 1 induction variable can be "
-                "interchanged currently.";
-    });
-    return true;
-  }
+  OuterLoopInductions = Inductions;
 
   Inductions.clear();
   if (!findInductionAndReductions(InnerLoop, Inductions, nullptr)) {
     LLVM_DEBUG(
         dbgs() << "Only inner loops with induction or reduction PHI nodes "
                << "are supported currently.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
bool LoopInterchangeTransform::adjustLoopBranches() {
   OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
 
   auto &OuterInnerReductions = LIL.getOuterInnerReductions();
   // Now update the reduction PHIs in the inner and outer loop headers.
   SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
   for (PHINode &PHI : InnerLoopHeader->phis())
     if (OuterInnerReductions.contains(&PHI))
       InnerLoopPHIs.push_back(cast<PHINode>(&PHI));
-  for (PHINode &PHI : OuterLoopHeader->phis())
-    if (OuterInnerReductions.contains(&PHI))
-      OuterLoopPHIs.push_back(cast<PHINode>(&PHI));
+
+  auto OuterLoopInductions = LIL.getOuterLoopInductions();
+  for (PHINode &PHI : OuterLoopHeader->phis()) {
+    if (std::find(OuterLoopInductions.begin(), OuterLoopInductions.end(),
+                  &PHI) != OuterLoopInductions.end())
+      continue;
+  }
 
   // Now move the remaining reduction PHIs from outer to inner loop header and
   // vice versa. The PHI nodes must be part of a reduction across the inner and
   // outer loop and all the remains to do is and updating the incoming blocks.
   for (PHINode *PHI : OuterLoopPHIs) {
+    LLVM_DEBUG(dbgs() << "Outer loop reduction PHIs:\n"; PHI->dump(););
     PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
     assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
   }
   for (PHINode *PHI : InnerLoopPHIs) {
     PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
     assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
   }
 

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s --basic-aa -loop-interchange -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s
+
+@c = common dso_local local_unnamed_addr global i32 0, align 4
+@e = common dso_local local_unnamed_addr global i32 0, align 4
+@d = common dso_local local_unnamed_addr global i32 0, align 4
+@b = common dso_local local_unnamed_addr global [2 x [10 x i32]] zeroinitializer, align 4
+@a = common dso_local local_unnamed_addr global i32 0, align 4
+
+; int a, c, d, e;
+; int b[2][10];
+; void fn1() {
+;  for (; c && e; c++,e++) {
+;    d = 5;
+;    for (; d; d--)
+;      a |= b[d][c + 9];
+;   }
+; }
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK:       for.cond2.preheader:
+; CHECK:    [[INDVARS_IV16:%.*]] = phi i64 [ [[TMP5:%.*]], [[FOR_COND2_PREHEADER_LR_PH:%.*]] ], [ [[INDVARS_IV_NEXT17:%.*]], [[FOR_INC7:%.*]] ]
+; CHECK:    [[TMP3:%.*]] = phi i32 [ [[TMP1:%.*]], [[FOR_COND2_PREHEADER_LR_PH]] ], [ [[INC8:%.*]], [[FOR_INC7]] ]
+; CHECK:    [[OR13:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_LCSSA15:%.*]], [[FOR_COND2_PREHEADER_LR_PH]] ]
+; CHECK:       for.body4:
+; CHECK:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP9:%.*]], [[FOR_BODY4_SPLIT:%.*]] ], [ 5, [[FOR_BODY4_PREHEADER:%.*]] ]
+; CHECK:    [[OR_LCSSA15]] = phi i32 [ [[A_PROMOTED14:%.*]], [[FOR_BODY4_PREHEADER]] ], [ [[OR_LCSSA:%.*]], [[FOR_BODY4_SPLIT:%.*]] ]
+; CHECK:    br label [[FOR_COND2_PREHEADER_LR_PH]]
+; CHECK:       for.body4.split:
+; CHECK:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
+; CHECK:    [[TMP7:%.*]] = phi i64 [ [[INDVARS_IV_NEXT17]], [[FOR_INC7]] ]
+; CHECK:    [[TMP8:%.*]] = phi i32 [ [[INC8]], [[FOR_INC7]] ]
+; CHECK:       for.inc7:
+; CHECK:    [[INDVARS_IV_NEXT17]] = add nsw i64 [[INDVARS_IV16]], 1
+; CHECK:    [[INC8]] = add nsw i32 [[TMP3]], 1
+; CHECK:       for.cond.for.end9_crit_edge:
+; CHECK:    [[INC_LCSSA_WIDE:%.*]] = phi i64 [ [[TMP7]], [[FOR_BODY4_SPLIT]] ]
+; CHECK:    [[INC8_LCSSA:%.*]] = phi i32 [ [[TMP8]], [[FOR_BODY4_SPLIT]] ]
+; CHECK:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY4_SPLIT]] ]
+
+
+
+entry:
+  %0 = load i32, i32* @c, align 4
+  %tobool11 = icmp ne i32 %0, 0
+  %1 = load i32, i32* @e, align 4
+  %tobool112 = icmp ne i32 %1, 0
+  %2 = and i1 %tobool11, %tobool112
+  br i1 %2, label %for.cond2.preheader.lr.ph, label %for.end9
+
+for.cond2.preheader.lr.ph:                        ; preds = %entry
+  %a.promoted14 = load i32, i32* @a, align 4
+  %3 = sext i32 %0 to i64
+  br label %for.cond2.preheader
+
+for.cond2.preheader:                              ; preds = %for.cond2.preheader.lr.ph, %for.inc7
+  %indvars.iv16 = phi i64 [ %3, %for.cond2.preheader.lr.ph ], [ %indvars.iv.next17, %for.inc7 ]
+  %or.lcssa15 = phi i32 [ %a.promoted14, %for.cond2.preheader.lr.ph ], [ %or.lcssa, %for.inc7 ]
+  %4 = phi i32 [ %1, %for.cond2.preheader.lr.ph ], [ %inc8, %for.inc7 ]
+  %5 = add nsw i64 %indvars.iv16, 9
+  br label %for.body4
+
+for.body4:                                        ; preds = %for.cond2.preheader, %for.body4
+  %indvars.iv = phi i64 [ 5, %for.cond2.preheader ], [ %indvars.iv.next, %for.body4 ]
+  %or13 = phi i32 [ %or.lcssa15, %for.cond2.preheader ], [ %or, %for.body4 ]
+  %arrayidx6 = getelementptr inbounds [2 x [10 x i32]], [2 x [10 x i32]]* @b, i64 0, i64 %indvars.iv, i64 %5
+  %6 = load i32, i32* %arrayidx6, align 4
+  %or = or i32 %or13, %6
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %tobool3 = icmp eq i64 %indvars.iv.next, 0
+  br i1 %tobool3, label %for.inc7, label %for.body4
+
+for.inc7:                                         ; preds = %for.body4
+  %or.lcssa = phi i32 [ %or, %for.body4 ]
+  %indvars.iv.next17 = add nsw i64 %indvars.iv16, 1
+  %inc8 = add nsw i32 %4, 1
+  %7 = trunc i64 %indvars.iv.next17 to i32
+  %tobool = icmp ne i32 %7, 0
+  %tobool1 = icmp ne i32 %inc8, 0
+  %8 = and i1 %tobool, %tobool1
+  br i1 %8, label %for.cond2.preheader, label %for.cond.for.end9_crit_edge
+
+for.cond.for.end9_crit_edge:                      ; preds = %for.inc7
+  %inc.lcssa.wide = phi i64 [ %indvars.iv.next17, %for.inc7 ]
+  %inc8.lcssa = phi i32 [ %inc8, %for.inc7 ]
+  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
+  %9 = trunc i64 %inc.lcssa.wide to i32
+  store i32 0, i32* @d, align 4
+  store i32 %or.lcssa.lcssa, i32* @a, align 4
+  store i32 %9, i32* @c, align 4
+  store i32 %inc8.lcssa, i32* @e, align 4
+  br label %for.end9
+
+for.end9:                                         ; preds = %for.cond.for.end9_crit_edge, %entry
+  ret void
+}
+
+; int a, c, d, e;
+; int b[2][10];
+; void fn1() {
+;   for (; c && e; c++,e++) {
+;     d = 5;
+;     for (; d; d--)
+;       a |= b[d+e][c+1];
+;   }
+; }
+
+define void @test2() {
+; CHECK-LABEL: @test2(
+; CHECK:       for.cond2.preheader:
+; CHECK:    [[INDVARS_IV19:%.*]] = phi i64 [ [[TMP4:%.*]], [[FOR_COND2_PREHEADER_LR_PH:%.*]] ], [ [[INDVARS_IV_NEXT20:%.*]], [[FOR_INC7:%.*]] ]
+; CHECK:    [[INDVARS_IV17:%.*]] = phi i64 [ [[TMP3:%.*]], [[FOR_COND2_PREHEADER_LR_PH]] ], [ [[INDVARS_IV_NEXT18:%.*]], [[FOR_INC7]] ]
+; CHECK:    [[OR13:%.*]] = phi i32 [ [[OR:%.*]], [[FOR_INC7]] ], [ [[OR_LCSSA15:%.*]], [[FOR_COND2_PREHEADER_LR_PH]] ]
+; CHECK:       for.body4:
+; CHECK:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP9:%.*]], [[FOR_BODY4_SPLIT:%.*]] ], [ 5, [[FOR_BODY4_PREHEADER]] ]
+; CHECK:    [[OR_LCSSA15]] = phi i32 [ [[A_PROMOTED14]], [[FOR_BODY4_PREHEADER]] ], [ [[OR_LCSSA:%.*]], [[FOR_BODY4_SPLIT]] ]
+; CHECK:       for.body4.split1:
+; CHECK:    [[INDVARS_IV19_ADD:%.*]] = add nsw i64 [[INDVARS_IV19]], 1
+; CHECK:    [[TMP5:%.*]] = add nsw i64 [[INDVARS_IV]], [[INDVARS_IV17]]
+; CHECK:    [[ARRAYIDX6:%.*]] = getelementptr inbounds [2 x [10 x i32]], [2 x [10 x i32]]* @b, i64 0, i64 [[TMP5]], i64 [[INDVARS_IV19_ADD]]
+; CHECK:       for.body4.split:
+; CHECK:    [[OR_LCSSA]] = phi i32 [ [[OR]], [[FOR_INC7]] ]
+; CHECK:    [[TMP7:%.*]] = phi i64 [ [[INDVARS_IV_NEXT20]], [[FOR_INC7]] ]
+; CHECK:    [[TMP8:%.*]] = phi i64 [ [[INDVARS_IV_NEXT18]], [[FOR_INC7]] ]
+; CHECK:       for.inc7:
+; CHECK:    [[INDVARS_IV_NEXT20]] = add nsw i64 [[INDVARS_IV19]], 1
+; CHECK:    [[INDVARS_IV_NEXT18]] = add nsw i64 [[INDVARS_IV17]], 1
+; CHECK:       for.cond.for.end9_crit_edge:
+; CHECK:    [[INC_LCSSA_WIDE:%.*]] = phi i64 [ [[TMP7]], [[FOR_BODY4_SPLIT]] ]
+; CHECK:    [[INC8_LCSSA_WIDE:%.*]] = phi i64 [ [[TMP8]], [[FOR_BODY4_SPLIT]] ]
+; CHECK:    [[OR_LCSSA_LCSSA:%.*]] = phi i32 [ [[OR_LCSSA]], [[FOR_BODY4_SPLIT]] ]
+
+
+entry:
+  %0 = load i32, i32* @c, align 4
+  %tobool11 = icmp ne i32 %0, 0
+  %1 = load i32, i32* @e, align 4
+  %tobool112 = icmp ne i32 %1, 0
+  %2 = and i1 %tobool11, %tobool112
+  br i1 %2, label %for.cond2.preheader.lr.ph, label %for.end9
+
+for.cond2.preheader.lr.ph:                        ; preds = %entry
+  %a.promoted14 = load i32, i32* @a, align 4
+  %3 = sext i32 %1 to i64
+  %4 = sext i32 %0 to i64
+  br label %for.cond2.preheader
+
+for.cond2.preheader:                              ; preds = %for.cond2.preheader.lr.ph, %for.inc7
+  %indvars.iv19 = phi i64 [ %4, %for.cond2.preheader.lr.ph ], [ %indvars.iv.next20, %for.inc7 ]
+  %indvars.iv17 = phi i64 [ %3, %for.cond2.preheader.lr.ph ], [ %indvars.iv.next18, %for.inc7 ]
+  %or.lcssa15 = phi i32 [ %a.promoted14, %for.cond2.preheader.lr.ph ], [ %or.lcssa, %for.inc7 ]
+  br label %for.body4
+
+for.body4:                                        ; preds = %for.cond2.preheader, %for.body4
+  %indvars.iv = phi i64 [ 5, %for.cond2.preheader ], [ %indvars.iv.next, %for.body4 ]
+  %or13 = phi i32 [ %or.lcssa15, %for.cond2.preheader ], [ %or, %for.body4 ]
+  %indvars.iv19.add = add nsw i64 %indvars.iv19, 1
+  %5 = add nsw i64 %indvars.iv, %indvars.iv17
+  %arrayidx6 = getelementptr inbounds [2 x [10 x i32]], [2 x [10 x i32]]* @b, i64 0, i64 %5, i64 %indvars.iv19.add
+  %6 = load i32, i32* %arrayidx6, align 4
+  %or = or i32 %or13, %6
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %tobool3 = icmp eq i64 %indvars.iv.next, 0
+  br i1 %tobool3, label %for.inc7, label %for.body4
+
+for.inc7:                                         ; preds = %for.body4
+  %or.lcssa = phi i32 [ %or, %for.body4 ]
+  %indvars.iv.next20 = add nsw i64 %indvars.iv19, 1
+  %indvars.iv.next18 = add nsw i64 %indvars.iv17, 1
+  %7 = trunc i64 %indvars.iv.next20 to i32
+  %tobool = icmp ne i32 %7, 0
+  %8 = trunc i64 %indvars.iv.next18 to i32
+  %tobool1 = icmp ne i32 %8, 0
+  %9 = and i1 %tobool, %tobool1
+  br i1 %9, label %for.cond2.preheader, label %for.cond.for.end9_crit_edge
+
+for.cond.for.end9_crit_edge:                      ; preds = %for.inc7
+  %inc.lcssa.wide = phi i64 [ %indvars.iv.next20, %for.inc7 ]
+  %inc8.lcssa.wide = phi i64 [ %indvars.iv.next18, %for.inc7 ]
+  %or.lcssa.lcssa = phi i32 [ %or.lcssa, %for.inc7 ]
+  %10 = trunc i64 %inc.lcssa.wide to i32
+  %11 = trunc i64 %inc8.lcssa.wide to i32
+  store i32 0, i32* @d, align 4
+  store i32 %or.lcssa.lcssa, i32* @a, align 4
+  store i32 %10, i32* @c, align 4
+  store i32 %11, i32* @e, align 4
+  br label %for.end9
+
+for.end9:                                         ; preds = %for.cond.for.end9_crit_edge, %entry
+  ret void
+}