[llvm] Bug fix: tightlyNested() of Loop interchange

[masakazu.ueno]

Summary

There is an error in the determination of whether the loop is tightly nested.
Therefore, the execution result may not be correct.
So I added a check to see if there are instructions between nested loops.

• Example

#include <stdio.h>
static   long  int i,j,k=3,m=3;
unsigned long  int x[50];
long double a[50][50];

int main() {

for (i=0; i<50; i++) for (j=0; j<50; j++) a[i][j]=i; for (i=0; i<50; i++) x[i]=1;

j=0;
for(i=40;i>1;i--) {
  k=20;
  while(k++<40) x[k]=x[j]%40;
  a[i][i]+=a[i][j]+a[j][i];
  for(m=9;;) if (--m<5) break;
}

for (i=0; i<50; i++) for (j=0; j<50; j++)
  printf("a:%ld %5.5Le \n",i,a[i][j]);

  return 0;
}

*) Specified options are "-Ofast -mllvm -enable-loopinterchange=true -flegacy-pass-manager".

The difference between the results when loop interchange is enabled and disabled is shown below.

$ clang -O2 -flegacy-pass-manager -mllvm -enable-loopinterchange=true -Rpass=loop-interchange bug1362_tightlynested.c -o a_error.out
bug1362_tightlynested.c:13:3: remark: Loop interchanged with enclosing loop. [-Rpass=loop-interchange]
  while(k++<40) x[k]=x[j]%40;
  ^
$ clang -O2 -flegacy-pass-manager -mllvm -enable-loopinterchange=false -Rpass=loop-interchange bug1362_tightlynested.c -o a_ok.out
$ ./a_error.out > a_error.res
$ ./a_ok.out > a_ok.res
$ diff a_ok.res a_error.res 
103c103
< a:2 4.00000e+00 
---
> a:2 4.20000e+01 
154c154
< a:3 6.00000e+00 
---
> a:3 6.30000e+01 
205c205
< a:4 8.00000e+00 
---
> a:4 8.40000e+01
 :
 Omit the following.

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

590

Is there any underlying reason that we selectively allow these instructions in InnerLoopPreheader, for example why zext? I'm wondering if there are specific reasons or is it an ad-hoc solution for now? The test program you provided does not seem to have these instructions in particular.

I have the same question for InnerLoopExit.

649

Maybe add some comment to self-explain this piece of code? If containsUnsafeInstructionsInInnerLoop() then it means the loops are not tightly nested? It all depends on how we define "tightly nested" in loop interchange. For example, if we have an add instruction in the inner loop preheader then containsUnsafeInstructionsInInnerLoop() would return true -> but having a add %x + 1 instruction in the inner loop preheader does not necessarily mean the loops are not tightly nested? Am I missing something?

llvm/test/Transforms/LoopInterchange/pr43797-lcssa-for-multiple-outer-loop-blocks.ll

9 ↗

(On Diff #323953)

I understand with this patch, these tests would fail legality check. I'm wondering if these tests are really not interchangable? If we did do loop interchange on the tests it would give us something wrong?

[masakazu.ueno]

I added some comments to the source code.

[congzhe]

In D96708#2605502, @masakazu.ueno wrote:

I added some comments to the source code.

Thanks for the comments!

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

public:
   bool currentLimitations();
 
   const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
     return OuterInnerReductions;
   }
 
 private:
   bool tightlyNested(Loop *Outer, Loop *Inner);
+  bool containsUnsafeInstructionsInInnerLoop(void);
   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,
assert(OuterLoop->isLCSSAForm(*DT) &&
            "Outer loop not left in LCSSA form after loop interchange!");
 
     return true;
   }
 };
 
 } // end anonymous namespace
 
+/// Returns true if there are unsafe instructions above or below
+/// the inner loop.
+bool LoopInterchangeLegality::containsUnsafeInstructionsInInnerLoop() {
+  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
+  BasicBlock *InnerLoopExit = InnerLoop->getExitBlock();
+  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
+  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
+
+  // Check loop preheader.
+  if (InnerLoopPreHeader != OuterLoopHeader) {
+    for (Instruction &I : *InnerLoopPreHeader) {
+      if (!isa<BranchInst>(&I) && !isa<DbgInfoIntrinsic>(&I))
+        return true;
+    }
+  }
+  // Check loop latch
+  if (InnerLoopExit != OuterLoopLatch) {
+    for (Instruction &I : *InnerLoopExit) {
+      if (!isa<BranchInst>(&I) && !isa<PHINode>(&I) &&
+          !isa<DbgInfoIntrinsic>(&I))
+        return true;
+    }
+  }
+
+  return false;
+}
+
 bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
   return any_of(*BB, [](const Instruction &I) {
     return I.mayHaveSideEffects() || I.mayReadFromMemory();
   });
 }
 
 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
 
   // Also make sure the inner loop preheader does not contain any unsafe
   // instructions. Note that all instructions in the preheader will be moved to
   // the outer loop header when interchanging.
   if (InnerLoopPreHeader != OuterLoopHeader &&
       containsUnsafeInstructions(InnerLoopPreHeader))
     return false;
 
+  if (containsUnsafeInstructionsInInnerLoop())
+    return false;
+
   LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
   // We have a perfect loop nest.
   return true;
 }
 
 bool LoopInterchangeLegality::isLoopStructureUnderstood(
     PHINode *InnerInduction) {
   unsigned Num = InnerInduction->getNumOperands();