[LoopInterchange] Do not interchange loops with function calls.

[fhahn]

Summary

Without any information about the called function, we cannot be sure
that it is safe to interchange loops which contain function calls. For
example there could be dependences that prevent interchanging between
accesses in the called function and the loops. Even functions without any
parameters could cause problems, as they could access memory using
global pointers.

For now, I think it is only safe to interchange loops with calls marked
as readnone.

With this patch, the LLVM test suite passes with `-O3 -mllvm
-enable-loopinterchange` and LoopInterchangeProfitability::isProfitable
returning true for all loops. check-llvm and check-clang also pass when
bootstrapped in a similar fashion, although only 3 loops got
interchanged.

[fhahn]

ping

[mcrosier]

Sounds reasonable to me.

[mcrosier]

test/Transforms/LoopInterchange/call-instructions.ll

60 ↗

(On Diff #107699)

It might be worth while to future proof this by adding CHECK directives that actually make sure the CFG structure doesn't change.

[fhahn]

Added more checks to test case, thanks @mcrosier for having a look! :)

lib/Transforms/Scalar/LoopInterchange.cpp

if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
     ORE->emit(OptimizationRemarkMissed(DEBUG_TYPE,
                                        "Dependence",
                                        InnerLoop->getStartLoc(),
                                        InnerLoop->getHeader())
               << "Cannot interchange loops due to dependences.");
     return false;
   }
 
+  // Check if outer and inner loop contain legal instructions only.
+  for (auto *BB : OuterLoop->blocks())
+    for (Instruction &I : *BB)
+      if (CallInst *CI = dyn_cast<CallInst>(&I)) {
+        // readnone functions do not prevent interchanging.
+        if (CI->doesNotReadMemory())
+          continue;
+        DEBUG(dbgs() << "Loops with call instructions cannot be interchanged "
+                     << "safely.");
+        return false;
+      }
+
   // Create unique Preheaders if we already do not have one.
   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 
   // Create  a unique outer preheader -
   // 1) If OuterLoop preheader is not present.
   // 2) If OuterLoop Preheader is same as OuterLoop Header
   // 3) If OuterLoop Preheader is same as Header of the previous loop.

test/Transforms/LoopInterchange/interchange-call-instructions-readnone.ll

+; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@A = common global [100 x [100 x i32]] zeroinitializer
+@B = common global [100 x i32] zeroinitializer
+@C = common global [100 x [100 x i32]] zeroinitializer
+@D = common global [100 x [100 x [100 x i32]]] zeroinitializer
+
+declare void @foo(i64 %a) readnone
+
+;;--------------------------------------Test case 01------------------------------------
+;;  for(int i=0;i<N;i++) {
+;;    for(int j=1;j<N;j++) {
+;;      foo(i);
+;;      A[j][i] = A[j][i]+k;
+;;    }
+;; }
+
+define void @interchange_01(i32 %k, i32 %N) {
+entry:
+  %cmp21 = icmp sgt i32 %N, 0
+  br i1 %cmp21, label %for.cond1.preheader.lr.ph, label %for.end12
+
+for.cond1.preheader.lr.ph:
+  %cmp219 = icmp sgt i32 %N, 1
+  %0 = add i32 %N, -1
+  br label %for.cond1.preheader
+
+for.cond1.preheader:
+  %indvars.iv23 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next24, %for.inc10 ]
+  br i1 %cmp219, label %for.body3, label %for.inc10
+
+for.body3:
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.cond1.preheader ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv23
+  call void @foo(i64 %indvars.iv23)
+  %1 = load i32, i32* %arrayidx5
+  %add = add nsw i32 %1, %k
+  store i32 %add, i32* %arrayidx5
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %0
+  br i1 %exitcond, label %for.inc10, label %for.body3
+
+for.inc10:
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %lftr.wideiv25 = trunc i64 %indvars.iv23 to i32
+  %exitcond26 = icmp eq i32 %lftr.wideiv25, %0
+  br i1 %exitcond26, label %for.end12, label %for.cond1.preheader
+
+for.end12:
+  ret void
+}
+
+; CHECK-LABEL: @interchange_01
+; CHECK: split

test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll

 ; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
 ;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
-@A = common global [100 x [100 x i32]] zeroinitializer
-@B = common global [100 x i32] zeroinitializer
-@C = common global [100 x [100 x i32]] zeroinitializer
-@D = common global [100 x [100 x [100 x i32]]] zeroinitializer
+@T = internal global [100 x double] zeroinitializer, align 4
+@Arr = internal global [1000 x [1000 x i32]] zeroinitializer, align 4
 
 ;; Test that a flow dependency in outer loop doesn't prevent interchange in
 ;; loops i and j.
 ;;
+;;  res = 0
 ;;  for (int k = 0; k < 100; ++k) {
-;;    T[k] = fn1();
+;;    T[k] = x;
 ;;    for (int i = 0; i < 1000; ++i)
 ;;      for(int j = 1; j < 1000; ++j)
 ;;        Arr[j][i] = Arr[j][i]+k;
-;;    fn2(T[k]);
+;;    res = T[k]
 ;;  }
 
-@T = internal global [100 x double] zeroinitializer, align 4
-@Arr = internal global [1000 x [1000 x i32]] zeroinitializer, align 4
-
-define void @interchange_09(i32 %k) {
+define void @interchange_09(i32 %k, double %x) {
 entry:
   br label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.cond.cleanup4
   ret void
 
 for.body:                                         ; preds = %for.cond.cleanup4, %entry
   %indvars.iv45 = phi i64 [ 0, %entry ], [ %indvars.iv.next46, %for.cond.cleanup4 ]
-  %call = call double @fn1()
   %arrayidx = getelementptr inbounds [100 x double], [100 x double]* @T, i64 0, i64 %indvars.iv45
-  store double %call, double* %arrayidx, align 8
+  store double %x, double* %arrayidx, align 8
   br label %for.cond6.preheader
 
 for.cond6.preheader:                              ; preds = %for.cond.cleanup8, %for.body
   %indvars.iv42 = phi i64 [ 0, %for.body ], [ %indvars.iv.next43, %for.cond.cleanup8 ]
   br label %for.body9
 
 for.cond.cleanup4:                                ; preds = %for.cond.cleanup8
   %tmp = load double, double* %arrayidx, align 8
-  call void @fn2(double %tmp)
   %indvars.iv.next46 = add nuw nsw i64 %indvars.iv45, 1
   %exitcond47 = icmp ne i64 %indvars.iv.next46, 100
   br i1 %exitcond47, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup8:                                ; preds = %for.body9
   %indvars.iv.next43 = add nuw nsw i64 %indvars.iv42, 1
   %exitcond44 = icmp ne i64 %indvars.iv.next43, 1000
   br i1 %exitcond44, label %for.cond6.preheader, label %for.cond.cleanup4
for.body9:                                        ; preds = %for.body9, %for.cond6.preheader
   %exitcond = icmp ne i64 %indvars.iv.next, 1000
   br i1 %exitcond, label %for.body9, label %for.cond.cleanup8
 }
 
 declare double @fn1()
 declare void @fn2(double)
 
 
+
+
+
 ;; After interchange %indvars.iv (j) should increment as the middle loop.
 ;; After interchange %indvars.iv42 (i) should increment with the inner most loop.
 
 ; CHECK-LABEL: @interchange_09
 
 ; CHECK: for.body:
 ; CHECK:   %indvars.iv45 = phi i64 [ %indvars.iv.next46, %for.cond.cleanup4 ], [ 0, %for.body.preheader ]
-; CHECK:   %call = call double @fn1()
 ; CHECK:   %arrayidx = getelementptr inbounds [100 x double], [100 x double]* @T, i64 0, i64 %indvars.iv45
-; CHECK:   store double %call, double* %arrayidx, align 8
+; CHECK:   store double %x, double* %arrayidx, align 8
 ; CHECK:   br label %for.body9.preheader
 
 ; CHECK: for.cond6.preheader.preheader:
 ; CHECK:   br label %for.cond6.preheader
 
 ; CHECK: for.cond6.preheader:
 ; CHECK:   %indvars.iv42 = phi i64 [ %indvars.iv.next43, %for.cond.cleanup8 ], [ 0, %for.cond6.preheader.preheader ]
 ; CHECK:   br label %for.body9.split1
 
 ; CHECK: for.body9.preheader:
 ; CHECK:   br label %for.body9
 
 ; CHECK: for.cond.cleanup4:
 ; CHECK:   %tmp = load double, double* %arrayidx, align 8
-; CHECK:   call void @fn2(double %tmp)
 ; CHECK:   %indvars.iv.next46 = add nuw nsw i64 %indvars.iv45, 1
 ; CHECK:   %exitcond47 = icmp ne i64 %indvars.iv.next46, 100
 ; CHECK:   br i1 %exitcond47, label %for.body, label %for.cond.cleanup
 
 ; CHECK: for.cond.cleanup8:
 ; CHECK:   %indvars.iv.next43 = add nuw nsw i64 %indvars.iv42, 1
 ; CHECK:   %exitcond44 = icmp ne i64 %indvars.iv.next43, 1000
 ; CHECK:   br i1 %exitcond44, label %for.cond6.preheader, label %for.body9.split

test/Transforms/LoopInterchange/not-interchanged-call-instructions.ll

+; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@A = common global [100 x [100 x i32]] zeroinitializer
+@B = common global [100 x i32] zeroinitializer
+@C = common global [100 x [100 x i32]] zeroinitializer
+@D = common global [100 x [100 x [100 x i32]]] zeroinitializer
+
+declare void @foo(i64 %a)
+
+;;--------------------------------------Test case 01------------------------------------
+;;  for(int i=0;i<N;i++) {
+;;    for(int j=1;j<N;j++) {
+;;      foo(i);
+;;      A[j][i] = A[j][i]+k;
+;;    }
+;; }
+
+define void @interchange_01(i32 %k, i32 %N) {
+entry:
+  %cmp21 = icmp sgt i32 %N, 0
+  br i1 %cmp21, label %for.cond1.preheader.lr.ph, label %for.end12
+
+for.cond1.preheader.lr.ph:
+  %cmp219 = icmp sgt i32 %N, 1
+  %0 = add i32 %N, -1
+  br label %for.cond1.preheader
+
+for.cond1.preheader:
+  %indvars.iv23 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next24, %for.inc10 ]
+  br i1 %cmp219, label %for.body3, label %for.inc10
+
+for.body3:
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.cond1.preheader ]
+  call void @foo(i64 %indvars.iv23)
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv23
+  %1 = load i32, i32* %arrayidx5
+  %add = add nsw i32 %1, %k
+  store i32 %add, i32* %arrayidx5
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %0
+  br i1 %exitcond, label %for.inc10, label %for.body3
+
+for.inc10:
+  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
+  %lftr.wideiv25 = trunc i64 %indvars.iv23 to i32
+  %exitcond26 = icmp eq i32 %lftr.wideiv25, %0
+  br i1 %exitcond26, label %for.end12, label %for.cond1.preheader
+
+for.end12:
+  ret void
+}
+
+; CHECK-LABEL: @interchange_01
+; CHECK-NOT: split

test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll

 ; CHECK: %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1
 ; CHECK: %lftr.wideiv35 = trunc i64 %indvars.iv32 to i32
 ; CHECK: %exitcond36 = icmp eq i32 %lftr.wideiv35, %0
 ; CHECK: br i1 %exitcond36, label %for.end17.loopexit, label %for.body
 ; CHECK: for.end17.loopexit:
 ; CHECK: br label %for.end17
 ; CHECK: for.end17:
 ; CHECK: ret void
-
-
-declare void @foo(...)
-
-;; Loops not tightly nested are not interchanged
-;;  for(int j=0;j<N;j++) {
-;;    foo();
-;;    for(int i=2;i<N;i++)
-;;      A[j][i] = A[j][i]+k;
-;;  }
-
-define void @interchange_06(i32 %k, i32 %N) {
-entry:
-  %cmp22 = icmp sgt i32 %N, 0
-  br i1 %cmp22, label %for.body.lr.ph, label %for.end12
-
-for.body.lr.ph:
-  %0 = add i32 %N, -1
-  br label %for.body
-
-for.body:
-  %indvars.iv24 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next25, %for.inc10 ]
-  tail call void (...) @foo()
-  br label %for.body3
-
-for.body3:
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 2, %for.body ]
-  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv24, i64 %indvars.iv
-  %1 = load i32, i32* %arrayidx5
-  %add = add nsw i32 %1, %k
-  store i32 %add, i32* %arrayidx5
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-  %lftr.wideiv = trunc i64 %indvars.iv to i32
-  %exitcond = icmp eq i32 %lftr.wideiv, %0
-  br i1 %exitcond, label %for.inc10, label %for.body3
-
-for.inc10:
-  %indvars.iv.next25 = add nuw nsw i64 %indvars.iv24, 1
-  %lftr.wideiv26 = trunc i64 %indvars.iv24 to i32
-  %exitcond27 = icmp eq i32 %lftr.wideiv26, %0
-  br i1 %exitcond27, label %for.end12, label %for.body
-
-for.end12:
-  ret void
-}
-;; Here we are checking if the inner phi is not split then we have not interchanged.
-; CHECK-LABEL: @interchange_06
-; CHECK:  phi i64 [ %indvars.iv.next, %for.body3 ], [ 2, %for.body3.preheader ]
-; CHECK-NEXT: getelementptr
-; CHECK-NEXT: %1 = load