llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll

   1 ; REQUIRES: asserts
   2 ; RUN: opt < %s -basic-aa -loop-interchange -verify-dom-info -verify-loop-info \
   3 ; RUN:     -S -debug 2>&1 | FileCheck %s
   4
   5 @A = common global [100 x [100 x i64]] zeroinitializer
   6 @N = dso_local local_unnamed_addr global i64 100, align 8
   7
   8
   9 ;;  for(int i=0;i<100;i++)
  10 ;;    for(int j=0;j<i;j++)
  11 ;;      A[j][i] = A[j][i]+k;
  12
  13 ;; Inner loop induction variable exit condition depends on the
  14 ;; outer loop induction variable, i.e., triangular loops.
  15 ; CHECK: Loop structure not understood by pass
  16 ; CHECK: Not interchanging loops. Cannot prove legality.
  17
  18 define void @interchange_01(i64 %k) {
  19 entry:
  20   br label %for1.header
  21
  22 for1.header:
  23   %i = phi i64 [ 0, %entry ], [ %i.next, %for1.inc10 ]
  24   br label %for2
  25
  26 for2:
  27   %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]
  28   %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %i
  29   %lv = load i64, i64* %arrayidx5
  30   %add = add nsw i64 %lv, %k
  31   store i64 %add, i64* %arrayidx5
  32   %j.next = add nuw nsw i64 %j, 1
  33   %exitcond = icmp eq i64 %j, %i
  34   br i1 %exitcond, label %for1.inc10, label %for2
  35
  36 for1.inc10:
  37   %i.next = add nuw nsw i64 %i, 1
  38   %exitcond26 = icmp eq i64 %i, 99
  39   br i1 %exitcond26, label %for.end12, label %for1.header
  40
  41 for.end12:
  42   ret void
  43 }
  44
  45
  46 ;;  for(int i=0;i<100;i++)
  47 ;;    for(int j=0;j+i<100;j++)
  48 ;;      A[j][i] = A[j][i]+k;
  49
  50 ;; Inner loop induction variable exit condition depends on the
  51 ;; outer loop induction variable, i.e., triangular loops.
  52 ; CHECK: Loop structure not understood by pass
  53 ; CHECK: Not interchanging loops. Cannot prove legality.
  54
  55 define void @interchange_02(i64 %k) {
  56 entry:
  57   br label %for1.header
  58
  59 for1.header:
  60   %i = phi i64 [ 0, %entry ], [ %i.next, %for1.inc10 ]
  61   br label %for2
  62
  63 for2:
  64   %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]
  65   %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %i
  66   %lv = load i64, i64* %arrayidx5
  67   %add = add nsw i64 %lv, %k
  68   store i64 %add, i64* %arrayidx5
  69   %0 = add nuw nsw i64 %j, %i
  70   %j.next = add nuw nsw i64 %j, 1
  71   %exitcond = icmp eq i64 %0, 100
  72   br i1 %exitcond, label %for1.inc10, label %for2
  73
  74 for1.inc10:
  75   %i.next = add nuw nsw i64 %i, 1
  76   %exitcond26 = icmp eq i64 %i, 99
  77   br i1 %exitcond26, label %for.end12, label %for1.header
  78
  79 for.end12:
  80   ret void
  81 }
  82
  83 ;;  for(int i=0;i<100;i++)
  84 ;;    for(int j=0;i>j;j++)
  85 ;;      A[j][i] = A[j][i]+k;
  86
  87 ;; Inner loop induction variable exit condition depends on the
  88 ;; outer loop induction variable, i.e., triangular loops.
  89 ; CHECK: Loop structure not understood by pass
  90 ; CHECK: Not interchanging loops. Cannot prove legality.
  91
  92 define void @interchange_03(i64 %k) {
  93 entry:
  94   br label %for1.header
  95
  96 for1.header:
  97   %i = phi i64 [ 0, %entry ], [ %i.next, %for1.inc10 ]
  98   br label %for2
  99
 100 for2:
 101   %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]
 102   %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %i
 103   %lv = load i64, i64* %arrayidx5
 104   %add = add nsw i64 %lv, %k
 105   store i64 %add, i64* %arrayidx5
 106   %j.next = add nuw nsw i64 %j, 1
 107   %exitcond = icmp ne i64 %i, %j
 108   br i1 %exitcond, label %for2, label %for1.inc10
 109
 110 for1.inc10:
 111   %i.next = add nuw nsw i64 %i, 1
 112   %exitcond26 = icmp eq i64 %i, 99
 113   br i1 %exitcond26, label %for.end12, label %for1.header
 114
 115 for.end12:
 116   ret void
 117 }
 118
 119 ;;  for(int i=0;i<100;i++)
 120 ;;    for(int j=0;N>j;j++)
 121 ;;      A[j][i] = A[j][i]+k;
 122
 123 ;; Inner loop induction variable exit condition depends on
 124 ;; an outer loop invariant, can do interchange.
 125 ; CHECK: Loops interchanged
 126
 127 define void @interchange_04(i64 %k) {
 128 entry:
 129   %0 = load i64, i64* @N, align 4
 130   br label %for1.header
 131
 132 for1.header:
 133   %i = phi i64 [ 0, %entry ], [ %i.next, %for1.inc10 ]
 134   br label %for2
 135
 136 for2:
 137   %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]
 138   %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %i
 139   %lv = load i64, i64* %arrayidx5
 140   %add = add nsw i64 %lv, %k
 141   store i64 %add, i64* %arrayidx5
 142   %j.next = add nuw nsw i64 %j, 1
 143   %exitcond = icmp ne i64 %0, %j
 144   br i1 %exitcond, label %for2, label %for1.inc10
 145
 146 for1.inc10:
 147   %i.next = add nuw nsw i64 %i, 1
 148   %exitcond26 = icmp eq i64 %i, 99
 149   br i1 %exitcond26, label %for.end12, label %for1.header
 150
 151 for.end12:
 152   ret void
 153 }