1; RUN: opt < %s -basic-aa -loop-interchange -pass-remarks-missed='loop-interchange' -verify-loop-lcssa -pass-remarks-output=%t -S 2; RUN: FileCheck --input-file %t --check-prefix REMARK %s 3 4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 5target triple = "x86_64-unknown-linux-gnu" 6 7@A = common global [100 x [100 x i32]] zeroinitializer 8@C = common global [100 x [100 x i32]] zeroinitializer 9@X = common global i32 0 10@Y = common global i64 0 11@F = common global float 0.0 12 13; We cannot interchange this loop at the moment, because iv.outer.next is 14; produced in the outer loop latch and used in the loop exit block. If the inner 15; loop body is not executed, the outer loop latch won't be executed either 16; after interchanging. 17; REMARK: UnsupportedExitPHI 18; REMARK-NEXT: lcssa_01 19 20define void @lcssa_01() { 21entry: 22 %cmp21 = icmp sgt i64 100, 1 23 br i1 %cmp21, label %outer.ph, label %for.end16 24 25outer.ph: ; preds = %entry 26 %cmp218 = icmp sgt i64 100, 1 27 br label %outer.header 28 29outer.header: ; preds = %outer.inc, %outer.ph 30 %iv.outer = phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ] 31 br i1 %cmp218, label %for.body3, label %outer.inc 32 33for.body3: ; preds = %for.body3, %outer.header 34 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ] 35 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer 36 %vA = load i32, i32* %arrayidx5 37 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer 38 %vC = load i32, i32* %arrayidx9 39 %add = add nsw i32 %vA, %vC 40 store i32 %add, i32* %arrayidx5 41 %iv.inner.next = add nuw nsw i64 %iv.inner, 1 42 %exitcond = icmp eq i64 %iv.inner.next, 100 43 br i1 %exitcond, label %outer.inc, label %for.body3 44 45outer.inc: ; preds = %for.body3, %outer.header 46 %iv.outer.next = add nsw i64 %iv.outer, 1 47 %cmp = icmp eq i64 %iv.outer.next, 100 48 br i1 %cmp, label %outer.header, label %for.exit 49 50for.exit: ; preds = %outer.inc 51 %iv.outer.next.lcssa = phi i64 [ %iv.outer.next, %outer.inc ] 52 store i64 %iv.outer.next.lcssa, i64* @Y 53 br label %for.end16 54 55for.end16: ; preds = %for.exit, %entry 56 ret void 57} 58 59; REMARK: UnsupportedExitPHI 60; REMARK-NEXT: lcssa_02 61define void @lcssa_02() { 62entry: 63 %cmp21 = icmp sgt i64 100, 1 64 br i1 %cmp21, label %outer.ph, label %for.end16 65 66outer.ph: ; preds = %entry 67 %cmp218 = icmp sgt i64 100, 1 68 br label %outer.header 69 70outer.header: ; preds = %outer.inc, %outer.ph 71 %iv.outer = phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ] 72 br i1 %cmp218, label %for.body3, label %outer.inc 73 74for.body3: ; preds = %for.body3, %outer.header 75 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ] 76 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer 77 %vA = load i32, i32* %arrayidx5 78 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer 79 %vC = load i32, i32* %arrayidx9 80 %add = add nsw i32 %vA, %vC 81 store i32 %add, i32* %arrayidx5 82 %iv.inner.next = add nuw nsw i64 %iv.inner, 1 83 %exitcond = icmp eq i64 %iv.inner.next, 100 84 br i1 %exitcond, label %outer.inc, label %for.body3 85 86outer.inc: ; preds = %for.body3, %outer.header 87 %iv.inner.end = phi i64 [ 0, %outer.header ], [ %iv.inner.next, %for.body3 ] 88 %iv.outer.next = add nsw i64 %iv.outer, 1 89 %cmp = icmp eq i64 %iv.outer.next, 100 90 br i1 %cmp, label %outer.header, label %for.exit 91 92for.exit: ; preds = %outer.inc 93 %iv.inner.end.lcssa = phi i64 [ %iv.inner.end, %outer.inc ] 94 store i64 %iv.inner.end.lcssa, i64* @Y 95 br label %for.end16 96 97for.end16: ; preds = %for.exit, %entry 98 ret void 99} 100 101; REMARK: Interchanged 102; REMARK-NEXT: lcssa_03 103define void @lcssa_03() { 104entry: 105 br label %outer.header 106 107outer.header: ; preds = %outer.inc, %entry 108 %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ] 109 br label %for.body3 110 111for.body3: ; preds = %for.body3, %outer.header 112 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ] 113 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer 114 %vA = load i32, i32* %arrayidx5 115 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer 116 %vC = load i32, i32* %arrayidx9 117 %add = add nsw i32 %vA, %vC 118 store i32 %add, i32* %arrayidx5 119 %iv.inner.next = add nuw nsw i64 %iv.inner, 1 120 %exitcond = icmp eq i64 %iv.inner.next, 100 121 br i1 %exitcond, label %outer.inc, label %for.body3 122 123outer.inc: ; preds = %for.body3 124 %iv.inner.lcssa = phi i64 [ %iv.inner, %for.body3 ] 125 %iv.outer.next = add nsw i64 %iv.outer, 1 126 %cmp = icmp eq i64 %iv.outer.next, 100 127 br i1 %cmp, label %outer.header, label %for.exit 128 129for.exit: ; preds = %outer.inc 130 %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ] 131 store i64 %iv.inner.lcssa.lcssa, i64* @Y 132 br label %for.end16 133 134for.end16: ; preds = %for.exit 135 ret void 136} 137 138; FIXME: We currently do not support LCSSA phi nodes involving floating point 139; types, as we fail to detect floating point reductions for now. 140; REMARK: UnsupportedPHIOuter 141; REMARK-NEXT: lcssa_04 142 143define void @lcssa_04() { 144entry: 145 br label %outer.header 146 147outer.header: ; preds = %outer.inc, %entry 148 %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ] 149 %float.outer = phi float [ 1.000000e+00, %entry ], [ 2.000000e+00, %outer.inc ] 150 br label %for.body3 151 152for.body3: ; preds = %for.body3, %outer.header 153 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ] 154 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer 155 %vA = load i32, i32* %arrayidx5 156 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer 157 %vC = load i32, i32* %arrayidx9 158 %add = add nsw i32 %vA, %vC 159 store i32 %add, i32* %arrayidx5 160 %iv.inner.next = add nuw nsw i64 %iv.inner, 1 161 %exitcond = icmp eq i64 %iv.inner.next, 100 162 br i1 %exitcond, label %outer.inc, label %for.body3 163 164outer.inc: ; preds = %for.body3 165 %iv.outer.next = add nsw i64 %iv.outer, 1 166 %cmp = icmp eq i64 %iv.outer.next, 100 167 br i1 %cmp, label %outer.header, label %for.exit 168 169for.exit: ; preds = %outer.inc 170 %float.outer.lcssa = phi float [ %float.outer, %outer.inc ] 171 store float %float.outer.lcssa, float* @F 172 br label %for.end16 173 174for.end16: ; preds = %for.exit 175 ret void 176} 177 178; PHI node in inner latch with multiple predecessors. 179; REMARK: Interchanged 180; REMARK-NEXT: lcssa_05 181 182define void @lcssa_05(i32* %ptr) { 183entry: 184 br label %outer.header 185 186outer.header: ; preds = %outer.inc, %entry 187 %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ] 188 br label %for.body3 189 190for.body3: ; preds = %bb3, %outer.header 191 %iv.inner = phi i64 [ %iv.inner.next, %bb3 ], [ 1, %outer.header ] 192 br i1 undef, label %bb2, label %bb3 193 194bb2: ; preds = %for.body3 195 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer 196 %vA = load i32, i32* %arrayidx5 197 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer 198 %vC = load i32, i32* %arrayidx9 199 %add = add nsw i32 %vA, %vC 200 br label %bb3 201 202bb3: ; preds = %bb2, %for.body3 203 %addp = phi i32 [ %add, %bb2 ], [ 0, %for.body3 ] 204 store i32 %addp, i32* %ptr 205 %iv.inner.next = add nuw nsw i64 %iv.inner, 1 206 %exitcond = icmp eq i64 %iv.inner.next, 100 207 br i1 %exitcond, label %outer.inc, label %for.body3 208 209outer.inc: ; preds = %bb3 210 %iv.inner.lcssa = phi i64 [ %iv.inner, %bb3 ] 211 %iv.outer.next = add nsw i64 %iv.outer, 1 212 %cmp = icmp eq i64 %iv.outer.next, 100 213 br i1 %cmp, label %outer.header, label %for.exit 214 215for.exit: ; preds = %outer.inc 216 %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ] 217 store i64 %iv.inner.lcssa.lcssa, i64* @Y 218 br label %for.end16 219 220for.end16: ; preds = %for.exit 221 ret void 222} 223 224; REMARK: UnsupportedExitPHI 225; REMARK-NEXT: lcssa_06 226 227define void @lcssa_06(i64* %ptr, i32* %ptr1) { 228entry: 229 br label %outer.header 230 231outer.header: ; preds = %outer.inc, %entry 232 %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ] 233 br i1 undef, label %for.body3, label %outer.inc 234 235for.body3: ; preds = %for.body3, %outer.header 236 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ] 237 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer 238 %vA = load i32, i32* %arrayidx5 239 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer 240 %vC = load i32, i32* %arrayidx9 241 %add = add nsw i32 %vA, %vC 242 store i32 %add, i32* %ptr1 243 %iv.inner.next = add nuw nsw i64 %iv.inner, 1 244 %exitcond = icmp eq i64 %iv.inner.next, 100 245 br i1 %exitcond, label %outer.inc, label %for.body3 246 247outer.inc: ; preds = %for.body3, %outer.header 248 %sv = phi i64 [ 0, %outer.header ], [ 1, %for.body3 ] 249 %iv.outer.next = add nsw i64 %iv.outer, 1 250 %cmp = icmp eq i64 %iv.outer.next, 100 251 br i1 %cmp, label %outer.header, label %for.exit 252 253for.exit: ; preds = %outer.inc 254 %sv.lcssa = phi i64 [ %sv, %outer.inc ] 255 store i64 %sv.lcssa, i64* @Y 256 br label %for.end16 257 258for.end16: ; preds = %for.exit 259 ret void 260} 261 262; REMARK: Interchanged 263; REMARK-NEXT: lcssa_07 264define void @lcssa_07() { 265entry: 266 br label %outer.header 267 268outer.header: ; preds = %outer.inc, %entry 269 %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ] 270 br label %for.body3 271 272for.body3: ; preds = %for.body3, %outer.header 273 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ] 274 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer 275 %vA = load i32, i32* %arrayidx5 276 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer 277 %vC = load i32, i32* %arrayidx9 278 %add = add nsw i32 %vA, %vC 279 store i32 %add, i32* %arrayidx5 280 %iv.inner.next = add nuw nsw i64 %iv.inner, 1 281 %exitcond = icmp eq i64 %iv.inner.next, 100 282 br i1 %exitcond, label %outer.bb, label %for.body3 283 284outer.bb: ; preds = %for.body3 285 %iv.inner.lcssa = phi i64 [ %iv.inner, %for.body3 ] 286 br label %outer.inc 287 288outer.inc: ; preds = %outer.bb 289 %iv.outer.next = add nsw i64 %iv.outer, 1 290 %cmp = icmp eq i64 %iv.outer.next, 100 291 br i1 %cmp, label %outer.header, label %for.exit 292 293for.exit: ; preds = %outer.inc 294 %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ] 295 store i64 %iv.inner.lcssa.lcssa, i64* @Y 296 br label %for.end16 297 298for.end16: ; preds = %for.exit 299 ret void 300} 301