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

   1 ; REQUIRES: asserts
   2 ; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info \
   3 ; RUN:     -S -debug 2>&1 | FileCheck %s
   4
   5 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   6
   7 @A = common global [100 x [100 x i32]] zeroinitializer
   8 @B = common global [100 x i32] zeroinitializer
   9 @C = common global [100 x [100 x i32]] zeroinitializer
  10 @D = common global [100 x [100 x [100 x i32]]] zeroinitializer
  11
  12 ;; Loops not tightly nested are not interchanged
  13 ;;  for(int j=0;j<N;j++) {
  14 ;;    B[j] = j+k;
  15 ;;    for(int i=0;i<N;i++)
  16 ;;      A[j][i] = A[j][i]+B[j];
  17 ;;  }
  18
  19 ; CHECK: Not interchanging loops. Cannot prove legality.
  20
  21 define void @interchange_05(i32 %k, i32 %N){
  22 entry:
  23   %cmp30 = icmp sgt i32 %N, 0
  24   br i1 %cmp30, label %for.body.lr.ph, label %for.end17
  25
  26 for.body.lr.ph:
  27   %0 = add i32 %N, -1
  28   %1 = zext i32 %k to i64
  29   br label %for.body
  30
  31 for.body:
  32   %indvars.iv32 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next33, %for.inc15 ]
  33   %2 = add nsw i64 %indvars.iv32, %1
  34   %arrayidx = getelementptr inbounds [100 x i32], ptr @B, i64 0, i64 %indvars.iv32
  35   %3 = trunc i64 %2 to i32
  36   store i32 %3, ptr %arrayidx
  37   br label %for.body3
  38
  39 for.body3:
  40   %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body3 ]
  41   %arrayidx7 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv32, i64 %indvars.iv
  42   %4 = load i32, ptr %arrayidx7
  43   %add10 = add nsw i32 %3, %4
  44   store i32 %add10, ptr %arrayidx7
  45   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  46   %lftr.wideiv = trunc i64 %indvars.iv to i32
  47   %exitcond = icmp eq i32 %lftr.wideiv, %0
  48   br i1 %exitcond, label %for.inc15, label %for.body3
  49
  50 for.inc15:
  51   %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1
  52   %lftr.wideiv35 = trunc i64 %indvars.iv32 to i32
  53   %exitcond36 = icmp eq i32 %lftr.wideiv35, %0
  54   br i1 %exitcond36, label %for.end17, label %for.body
  55
  56 for.end17:
  57   ret void
  58 }
  59
  60 declare void @foo(...) readnone
  61
  62 ;; Loops not tightly nested are not interchanged
  63 ;;  for(int j=0;j<N;j++) {
  64 ;;    foo();
  65 ;;    for(int i=2;i<N;i++)
  66 ;;      A[j][i] = A[j][i]+k;
  67 ;;  }
  68
  69 ; CHECK: Not interchanging loops. Cannot prove legality.
  70
  71 define void @interchange_06(i32 %k, i32 %N) {
  72 entry:
  73   %cmp22 = icmp sgt i32 %N, 0
  74   br i1 %cmp22, label %for.body.lr.ph, label %for.end12
  75
  76 for.body.lr.ph:
  77   %0 = add i32 %N, -1
  78   br label %for.body
  79
  80 for.body:
  81   %indvars.iv24 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next25, %for.inc10 ]
  82   tail call void (...) @foo()
  83   br label %for.body3
  84
  85 for.body3:
  86   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 2, %for.body ]
  87   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv24, i64 %indvars.iv
  88   %1 = load i32, ptr %arrayidx5
  89   %add = add nsw i32 %1, %k
  90   store i32 %add, ptr %arrayidx5
  91   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  92   %lftr.wideiv = trunc i64 %indvars.iv to i32
  93   %exitcond = icmp eq i32 %lftr.wideiv, %0
  94   br i1 %exitcond, label %for.inc10, label %for.body3
  95
  96 for.inc10:
  97   %indvars.iv.next25 = add nuw nsw i64 %indvars.iv24, 1
  98   %lftr.wideiv26 = trunc i64 %indvars.iv24 to i32
  99   %exitcond27 = icmp eq i32 %lftr.wideiv26, %0
 100   br i1 %exitcond27, label %for.end12, label %for.body
 101
 102 for.end12:
 103   ret void
 104 }
 105
 106 ;; The following Loop is not considered tightly nested and is not interchanged.
 107 ;; The outer loop header does not branch to the inner loop preheader, or the
 108 ;; inner loop header, or the outer loop latch.
 109 ; CHECK: Not interchanging loops. Cannot prove legality.
 110 define void @interchange_07(i32 %k, i32 %N, i64 %ny) {
 111 entry:
 112   br label %for1.header
 113
 114 for1.header:
 115   %j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ]
 116   %cmp21 = icmp slt i64 0, %ny
 117   br label %singleSucc
 118
 119 singleSucc:
 120   br i1 %cmp21, label %preheader.j, label %for1.inc10
 121
 122 preheader.j:
 123   br label %for2
 124
 125 for2:
 126   %j = phi i64 [ %j.next, %for2 ], [ 0, %preheader.j ]
 127   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j, i64 %j23
 128   %lv = load i32, ptr %arrayidx5
 129   %add = add nsw i32 %lv, %k
 130   store i32 %add, ptr %arrayidx5
 131   %j.next = add nuw nsw i64 %j, 1
 132   %exitcond = icmp eq i64 %j, 99
 133   br i1 %exitcond, label %for1.inc10, label %for2
 134
 135 for1.inc10:
 136   %j.next24 = add nuw nsw i64 %j23, 1
 137   %exitcond26 = icmp eq i64 %j23, 99
 138   br i1 %exitcond26, label %for.end12, label %for1.header
 139
 140 for.end12:
 141   ret void
 142 }