| 1 |
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5 |
| 2 |
; RUN: opt < %s -passes=loop-interchange -verify-dom-info -verify-loop-info -S 2>&1 | FileCheck %s |
| 3 |
|
| 4 |
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" |
| 5 |
|
| 6 |
@A = common global [100 x [100 x i32]] zeroinitializer |
| 7 |
@B = common global [100 x i32] zeroinitializer |
| 8 |
@C = common global [100 x [100 x i32]] zeroinitializer |
| 9 |
@D = common global [100 x [100 x [100 x i32]]] zeroinitializer |
| 10 |
|
| 11 |
; Loops not tightly nested are not interchanged |
| 12 |
; |
| 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 |
define void @interchange_05(i32 %k, i32 %N){ |
| 20 |
; CHECK-LABEL: define void @interchange_05( |
| 21 |
; CHECK-SAME: i32 [[K:%.*]], i32 [[N:%.*]]) { |
| 22 |
; CHECK-NEXT: [[ENTRY:.*:]] |
| 23 |
; CHECK-NEXT: [[CMP30:%.*]] = icmp sgt i32 [[N]], 0 |
| 24 |
; CHECK-NEXT: br i1 [[CMP30]], label %[[FOR_BODY_LR_PH:.*]], label %[[FOR_END17:.*]] |
| 25 |
; CHECK: [[FOR_BODY_LR_PH]]: |
| 26 |
; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N]], -1 |
| 27 |
; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[K]] to i64 |
| 28 |
; CHECK-NEXT: br label %[[FOR_BODY:.*]] |
| 29 |
; CHECK: [[FOR_BODY]]: |
| 30 |
; CHECK-NEXT: [[INDVARS_IV32:%.*]] = phi i64 [ 0, %[[FOR_BODY_LR_PH]] ], [ [[INDVARS_IV_NEXT33:%.*]], %[[FOR_INC15:.*]] ] |
| 31 |
; CHECK-NEXT: [[TMP2:%.*]] = add nsw i64 [[INDVARS_IV32]], [[TMP1]] |
| 32 |
; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds [100 x i32], ptr @B, i64 0, i64 [[INDVARS_IV32]] |
| 33 |
; CHECK-NEXT: [[TMP3:%.*]] = trunc i64 [[TMP2]] to i32 |
| 34 |
; CHECK-NEXT: store i32 [[TMP3]], ptr [[ARRAYIDX]], align 4 |
| 35 |
; CHECK-NEXT: br label %[[FOR_BODY3:.*]] |
| 36 |
; CHECK: [[FOR_BODY3]]: |
| 37 |
; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ 0, %[[FOR_BODY]] ], [ [[INDVARS_IV_NEXT:%.*]], %[[FOR_BODY3]] ] |
| 38 |
; CHECK-NEXT: [[ARRAYIDX7:%.*]] = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 [[INDVARS_IV32]], i64 [[INDVARS_IV]] |
| 39 |
; CHECK-NEXT: [[TMP4:%.*]] = load i32, ptr [[ARRAYIDX7]], align 4 |
| 40 |
; CHECK-NEXT: [[ADD10:%.*]] = add nsw i32 [[TMP3]], [[TMP4]] |
| 41 |
; CHECK-NEXT: store i32 [[ADD10]], ptr [[ARRAYIDX7]], align 4 |
| 42 |
; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1 |
| 43 |
; CHECK-NEXT: [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV]] to i32 |
| 44 |
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[LFTR_WIDEIV]], [[TMP0]] |
| 45 |
; CHECK-NEXT: br i1 [[EXITCOND]], label %[[FOR_INC15]], label %[[FOR_BODY3]] |
| 46 |
; CHECK: [[FOR_INC15]]: |
| 47 |
; CHECK-NEXT: [[INDVARS_IV_NEXT33]] = add nuw nsw i64 [[INDVARS_IV32]], 1 |
| 48 |
; CHECK-NEXT: [[LFTR_WIDEIV35:%.*]] = trunc i64 [[INDVARS_IV32]] to i32 |
| 49 |
; CHECK-NEXT: [[EXITCOND36:%.*]] = icmp eq i32 [[LFTR_WIDEIV35]], [[TMP0]] |
| 50 |
; CHECK-NEXT: br i1 [[EXITCOND36]], label %[[FOR_END17_LOOPEXIT:.*]], label %[[FOR_BODY]] |
| 51 |
; CHECK: [[FOR_END17_LOOPEXIT]]: |
| 52 |
; CHECK-NEXT: br label %[[FOR_END17]] |
| 53 |
; CHECK: [[FOR_END17]]: |
| 54 |
; CHECK-NEXT: ret void |
| 55 |
; |
| 56 |
entry: |
| 57 |
%cmp30 = icmp sgt i32 %N, 0 |
| 58 |
br i1 %cmp30, label %for.body.lr.ph, label %for.end17 |
| 59 |
|
| 60 |
for.body.lr.ph: |
| 61 |
%0 = add i32 %N, -1 |
| 62 |
%1 = zext i32 %k to i64 |
| 63 |
br label %for.body |
| 64 |
|
| 65 |
for.body: |
| 66 |
%indvars.iv32 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next33, %for.inc15 ] |
| 67 |
%2 = add nsw i64 %indvars.iv32, %1 |
| 68 |
%arrayidx = getelementptr inbounds [100 x i32], ptr @B, i64 0, i64 %indvars.iv32 |
| 69 |
%3 = trunc i64 %2 to i32 |
| 70 |
store i32 %3, ptr %arrayidx |
| 71 |
br label %for.body3 |
| 72 |
|
| 73 |
for.body3: |
| 74 |
%indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body3 ] |
| 75 |
%arrayidx7 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv32, i64 %indvars.iv |
| 76 |
%4 = load i32, ptr %arrayidx7 |
| 77 |
%add10 = add nsw i32 %3, %4 |
| 78 |
store i32 %add10, ptr %arrayidx7 |
| 79 |
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 |
| 80 |
%lftr.wideiv = trunc i64 %indvars.iv to i32 |
| 81 |
%exitcond = icmp eq i32 %lftr.wideiv, %0 |
| 82 |
br i1 %exitcond, label %for.inc15, label %for.body3 |
| 83 |
|
| 84 |
for.inc15: |
| 85 |
%indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1 |
| 86 |
%lftr.wideiv35 = trunc i64 %indvars.iv32 to i32 |
| 87 |
%exitcond36 = icmp eq i32 %lftr.wideiv35, %0 |
| 88 |
br i1 %exitcond36, label %for.end17, label %for.body |
| 89 |
|
| 90 |
for.end17: |
| 91 |
ret void |
| 92 |
} |
| 93 |
|
| 94 |
declare void @foo(...) readnone |
| 95 |
|
| 96 |
; Loops not tightly nested are not interchanged |
| 97 |
; for(int j=0;j<N;j++) { |
| 98 |
; foo(); |
| 99 |
; for(int i=2;i<N;i++) |
| 100 |
; A[j][i] = A[j][i]+k; |
| 101 |
; } |
| 102 |
; |
| 103 |
define void @interchange_06(i32 %k, i32 %N) { |
| 104 |
; CHECK-LABEL: define void @interchange_06( |
| 105 |
; CHECK-SAME: i32 [[K:%.*]], i32 [[N:%.*]]) { |
| 106 |
; CHECK-NEXT: [[ENTRY:.*:]] |
| 107 |
; CHECK-NEXT: [[CMP22:%.*]] = icmp sgt i32 [[N]], 0 |
| 108 |
; CHECK-NEXT: br i1 [[CMP22]], label %[[FOR_BODY_LR_PH:.*]], label %[[FOR_END12:.*]] |
| 109 |
; CHECK: [[FOR_BODY_LR_PH]]: |
| 110 |
; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N]], -1 |
| 111 |
; CHECK-NEXT: br label %[[FOR_BODY:.*]] |
| 112 |
; CHECK: [[FOR_BODY]]: |
| 113 |
; CHECK-NEXT: [[INDVARS_IV24:%.*]] = phi i64 [ 0, %[[FOR_BODY_LR_PH]] ], [ [[INDVARS_IV_NEXT25:%.*]], %[[FOR_INC10:.*]] ] |
| 114 |
; CHECK-NEXT: tail call void (...) @foo() |
| 115 |
; CHECK-NEXT: br label %[[FOR_BODY3:.*]] |
| 116 |
; CHECK: [[FOR_BODY3]]: |
| 117 |
; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], %[[FOR_BODY3]] ], [ 2, %[[FOR_BODY]] ] |
| 118 |
; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 [[INDVARS_IV24]], i64 [[INDVARS_IV]] |
| 119 |
; CHECK-NEXT: [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4 |
| 120 |
; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[TMP1]], [[K]] |
| 121 |
; CHECK-NEXT: store i32 [[ADD]], ptr [[ARRAYIDX5]], align 4 |
| 122 |
; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1 |
| 123 |
; CHECK-NEXT: [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV]] to i32 |
| 124 |
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[LFTR_WIDEIV]], [[TMP0]] |
| 125 |
; CHECK-NEXT: br i1 [[EXITCOND]], label %[[FOR_INC10]], label %[[FOR_BODY3]] |
| 126 |
; CHECK: [[FOR_INC10]]: |
| 127 |
; CHECK-NEXT: [[INDVARS_IV_NEXT25]] = add nuw nsw i64 [[INDVARS_IV24]], 1 |
| 128 |
; CHECK-NEXT: [[LFTR_WIDEIV26:%.*]] = trunc i64 [[INDVARS_IV24]] to i32 |
| 129 |
; CHECK-NEXT: [[EXITCOND27:%.*]] = icmp eq i32 [[LFTR_WIDEIV26]], [[TMP0]] |
| 130 |
; CHECK-NEXT: br i1 [[EXITCOND27]], label %[[FOR_END12_LOOPEXIT:.*]], label %[[FOR_BODY]] |
| 131 |
; CHECK: [[FOR_END12_LOOPEXIT]]: |
| 132 |
; CHECK-NEXT: br label %[[FOR_END12]] |
| 133 |
; CHECK: [[FOR_END12]]: |
| 134 |
; CHECK-NEXT: ret void |
| 135 |
; |
| 136 |
entry: |
| 137 |
%cmp22 = icmp sgt i32 %N, 0 |
| 138 |
br i1 %cmp22, label %for.body.lr.ph, label %for.end12 |
| 139 |
|
| 140 |
for.body.lr.ph: |
| 141 |
%0 = add i32 %N, -1 |
| 142 |
br label %for.body |
| 143 |
|
| 144 |
for.body: |
| 145 |
%indvars.iv24 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next25, %for.inc10 ] |
| 146 |
tail call void (...) @foo() |
| 147 |
br label %for.body3 |
| 148 |
|
| 149 |
for.body3: |
| 150 |
%indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 2, %for.body ] |
| 151 |
%arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv24, i64 %indvars.iv |
| 152 |
%1 = load i32, ptr %arrayidx5 |
| 153 |
%add = add nsw i32 %1, %k |
| 154 |
store i32 %add, ptr %arrayidx5 |
| 155 |
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 |
| 156 |
%lftr.wideiv = trunc i64 %indvars.iv to i32 |
| 157 |
%exitcond = icmp eq i32 %lftr.wideiv, %0 |
| 158 |
br i1 %exitcond, label %for.inc10, label %for.body3 |
| 159 |
|
| 160 |
for.inc10: |
| 161 |
%indvars.iv.next25 = add nuw nsw i64 %indvars.iv24, 1 |
| 162 |
%lftr.wideiv26 = trunc i64 %indvars.iv24 to i32 |
| 163 |
%exitcond27 = icmp eq i32 %lftr.wideiv26, %0 |
| 164 |
br i1 %exitcond27, label %for.end12, label %for.body |
| 165 |
|
| 166 |
for.end12: |
| 167 |
ret void |
| 168 |
} |
| 169 |
|
| 170 |
; The following Loop is not considered tightly nested and is not interchanged. |
| 171 |
; The outer loop header does not branch to the inner loop preheader, or the |
| 172 |
; inner loop header, or the outer loop latch. |
| 173 |
; |
| 174 |
define void @interchange_07(i32 %k, i32 %N, i64 %ny) { |
| 175 |
; CHECK-LABEL: define void @interchange_07( |
| 176 |
; CHECK-SAME: i32 [[K:%.*]], i32 [[N:%.*]], i64 [[NY:%.*]]) { |
| 177 |
; CHECK-NEXT: [[ENTRY:.*]]: |
| 178 |
; CHECK-NEXT: br label %[[FOR1_HEADER:.*]] |
| 179 |
; CHECK: [[FOR1_HEADER]]: |
| 180 |
; CHECK-NEXT: [[J23:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[J_NEXT24:%.*]], %[[FOR1_INC10:.*]] ] |
| 181 |
; CHECK-NEXT: [[CMP21:%.*]] = icmp slt i64 0, [[NY]] |
| 182 |
; CHECK-NEXT: br label %[[SINGLESUCC:.*]] |
| 183 |
; CHECK: [[SINGLESUCC]]: |
| 184 |
; CHECK-NEXT: br i1 [[CMP21]], label %[[PREHEADER_J:.*]], label %[[FOR1_INC10]] |
| 185 |
; CHECK: [[PREHEADER_J]]: |
| 186 |
; CHECK-NEXT: br label %[[FOR2:.*]] |
| 187 |
; CHECK: [[FOR2]]: |
| 188 |
; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[J_NEXT:%.*]], %[[FOR2]] ], [ 0, %[[PREHEADER_J]] ] |
| 189 |
; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 [[J]], i64 [[J23]] |
| 190 |
; CHECK-NEXT: [[LV:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4 |
| 191 |
; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[LV]], [[K]] |
| 192 |
; CHECK-NEXT: store i32 [[ADD]], ptr [[ARRAYIDX5]], align 4 |
| 193 |
; CHECK-NEXT: [[J_NEXT]] = add nuw nsw i64 [[J]], 1 |
| 194 |
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[J]], 99 |
| 195 |
; CHECK-NEXT: br i1 [[EXITCOND]], label %[[FOR1_INC10_LOOPEXIT:.*]], label %[[FOR2]] |
| 196 |
; CHECK: [[FOR1_INC10_LOOPEXIT]]: |
| 197 |
; CHECK-NEXT: br label %[[FOR1_INC10]] |
| 198 |
; CHECK: [[FOR1_INC10]]: |
| 199 |
; CHECK-NEXT: [[J_NEXT24]] = add nuw nsw i64 [[J23]], 1 |
| 200 |
; CHECK-NEXT: [[EXITCOND26:%.*]] = icmp eq i64 [[J23]], 99 |
| 201 |
; CHECK-NEXT: br i1 [[EXITCOND26]], label %[[FOR_END12:.*]], label %[[FOR1_HEADER]] |
| 202 |
; CHECK: [[FOR_END12]]: |
| 203 |
; CHECK-NEXT: ret void |
| 204 |
; |
| 205 |
entry: |
| 206 |
br label %for1.header |
| 207 |
|
| 208 |
for1.header: |
| 209 |
%j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ] |
| 210 |
%cmp21 = icmp slt i64 0, %ny |
| 211 |
br label %singleSucc |
| 212 |
|
| 213 |
singleSucc: |
| 214 |
br i1 %cmp21, label %preheader.j, label %for1.inc10 |
| 215 |
|
| 216 |
preheader.j: |
| 217 |
br label %for2 |
| 218 |
|
| 219 |
for2: |
| 220 |
%j = phi i64 [ %j.next, %for2 ], [ 0, %preheader.j ] |
| 221 |
%arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j, i64 %j23 |
| 222 |
%lv = load i32, ptr %arrayidx5 |
| 223 |
%add = add nsw i32 %lv, %k |
| 224 |
store i32 %add, ptr %arrayidx5 |
| 225 |
%j.next = add nuw nsw i64 %j, 1 |
| 226 |
%exitcond = icmp eq i64 %j, 99 |
| 227 |
br i1 %exitcond, label %for1.inc10, label %for2 |
| 228 |
|
| 229 |
for1.inc10: |
| 230 |
%j.next24 = add nuw nsw i64 %j23, 1 |
| 231 |
%exitcond26 = icmp eq i64 %j23, 99 |
| 232 |
br i1 %exitcond26, label %for.end12, label %for1.header |
| 233 |
|
| 234 |
for.end12: |
| 235 |
ret void |
| 236 |
} |