336 lines · plain
1; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -pass-remarks-output=%t -disable-output \2; RUN: -verify-dom-info -verify-loop-info -verify-loop-lcssa3; RUN: FileCheck -input-file=%t %s4 5; Check that interchanging the loops is legal for the bitwise-or reduction.6;7; int b_or = 0;8; for (int i = 0; i < 2; i++)9; for (int j = 0; j < 2; j++)10; b_or |= A[j][i];11 12; CHECK: --- !Pass13; CHECK-NEXT: Pass: loop-interchange14; CHECK-NEXT: Name: Interchanged15; CHECK-NEXT: Function: reduction_or16define void @reduction_or(ptr %A) {17entry:18 br label %for.i.header19 20for.i.header:21 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]22 %or.i = phi i32 [ 0, %entry ], [ %or.i.lcssa, %for.i.latch ]23 br label %for.j24 25for.j:26 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]27 %or.j = phi i32 [ %or.i, %for.i.header ], [ %or.j.next, %for.j ]28 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i29 %a = load i32, ptr %idx, align 430 %or.j.next = or i32 %or.j, %a31 %j.inc = add i32 %j, 132 %cmp.j = icmp slt i32 %j.inc, 233 br i1 %cmp.j, label %for.j, label %for.i.latch34 35for.i.latch:36 %or.i.lcssa = phi i32 [ %or.j.next, %for.j ]37 %i.inc = add i32 %i, 138 %cmp.i = icmp slt i32 %i.inc, 239 br i1 %cmp.i, label %for.i.header, label %exit40 41exit:42 ret void43}44 45 46; Check that interchanging the loops is legal for the bitwise-and reduction.47;48; int b_and = -1;49; for (int i = 0; i < 2; i++)50; for (int j = 0; j < 2; j++)51; b_and &= A[j][i];52 53; CHECK: --- !Pass54; CHECK-NEXT: Pass: loop-interchange55; CHECK-NEXT: Name: Interchanged56; CHECK-NEXT: Function: reduction_and57define void @reduction_and(ptr %A) {58entry:59 br label %for.i.header60 61for.i.header:62 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]63 %and.i = phi i32 [ -1, %entry ], [ %and.i.lcssa, %for.i.latch ]64 br label %for.j65 66for.j:67 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]68 %and.j = phi i32 [ %and.i, %for.i.header ], [ %and.j.next, %for.j ]69 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i70 %a = load i32, ptr %idx, align 471 %and.j.next = and i32 %and.j, %a72 %j.inc = add i32 %j, 173 %cmp.j = icmp slt i32 %j.inc, 274 br i1 %cmp.j, label %for.j, label %for.i.latch75 76for.i.latch:77 %and.i.lcssa = phi i32 [ %and.j.next, %for.j ]78 %i.inc = add i32 %i, 179 %cmp.i = icmp slt i32 %i.inc, 280 br i1 %cmp.i, label %for.i.header, label %exit81 82exit:83 ret void84}85 86 87; Check that interchanging the loops is legal for the bitwise-xor reduction.88;89; int b_xor = 0;90; for (int i = 0; i < 2; i++)91; for (int j = 0; j < 2; j++)92; b_xor ^= A[j][i];93 94; CHECK: --- !Pass95; CHECK-NEXT: Pass: loop-interchange96; CHECK-NEXT: Name: Interchanged97; CHECK-NEXT: Function: reduction_xor98define void @reduction_xor(ptr %A) {99entry:100 br label %for.i.header101 102for.i.header:103 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]104 %xor.i = phi i32 [ 0, %entry ], [ %xor.i.lcssa, %for.i.latch ]105 br label %for.j106 107for.j:108 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]109 %xor.j = phi i32 [ %xor.i, %for.i.header ], [ %xor.j.next, %for.j ]110 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i111 %a = load i32, ptr %idx, align 4112 %xor.j.next = xor i32 %xor.j, %a113 %j.inc = add i32 %j, 1114 %cmp.j = icmp slt i32 %j.inc, 2115 br i1 %cmp.j, label %for.j, label %for.i.latch116 117for.i.latch:118 %xor.i.lcssa = phi i32 [ %xor.j.next, %for.j ]119 %i.inc = add i32 %i, 1120 %cmp.i = icmp slt i32 %i.inc, 2121 br i1 %cmp.i, label %for.i.header, label %exit122 123exit:124 ret void125}126 127 128; Check that interchanging the loops is legal for the signed-minimum reduction.129;130; int smin = init;131; for (int i = 0; i < 2; i++)132; for (int j = 0; j < 2; j++)133; smin = (A[j][i] < smin) ? A[j][i] : smin;134 135; CHECK: --- !Pass136; CHECK-NEXT: Pass: loop-interchange137; CHECK-NEXT: Name: Interchanged138; CHECK-NEXT: Function: reduction_smin139define void @reduction_smin(ptr %A, i32 %init) {140entry:141 br label %for.i.header142 143for.i.header:144 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]145 %smin.i = phi i32 [ %init, %entry ], [ %smin.i.lcssa, %for.i.latch ]146 br label %for.j147 148for.j:149 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]150 %smin.j = phi i32 [ %smin.i, %for.i.header ], [ %smin.j.next, %for.j ]151 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i152 %a = load i32, ptr %idx, align 4153 %cmp = icmp slt i32 %a, %smin.j154 %smin.j.next = select i1 %cmp, i32 %a, i32 %smin.j155 %j.inc = add i32 %j, 1156 %cmp.j = icmp slt i32 %j.inc, 2157 br i1 %cmp.j, label %for.j, label %for.i.latch158 159for.i.latch:160 %smin.i.lcssa = phi i32 [ %smin.j.next, %for.j ]161 %i.inc = add i32 %i, 1162 %cmp.i = icmp slt i32 %i.inc, 2163 br i1 %cmp.i, label %for.i.header, label %exit164 165exit:166 ret void167}168 169 170; Check that interchanging the loops is legal for the signed-maximum reduction.171;172; int smax = init;173; for (int i = 0; i < 2; i++)174; for (int j = 0; j < 2; j++)175; smax = (A[j][i] > smax) ? A[j][i] : smax;176 177; CHECK: --- !Pass178; CHECK-NEXT: Pass: loop-interchange179; CHECK-NEXT: Name: Interchanged180; CHECK-NEXT: Function: reduction_smax181define void @reduction_smax(ptr %A, i32 %init) {182entry:183 br label %for.i.header184 185for.i.header:186 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]187 %smax.i = phi i32 [ %init, %entry ], [ %smax.i.lcssa, %for.i.latch ]188 br label %for.j189 190for.j:191 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]192 %smax.j = phi i32 [ %smax.i, %for.i.header ], [ %smax.j.next, %for.j ]193 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i194 %a = load i32, ptr %idx, align 4195 %cmp = icmp sgt i32 %a, %smax.j196 %smax.j.next = select i1 %cmp, i32 %a, i32 %smax.j197 %j.inc = add i32 %j, 1198 %cmp.j = icmp slt i32 %j.inc, 2199 br i1 %cmp.j, label %for.j, label %for.i.latch200 201for.i.latch:202 %smax.i.lcssa = phi i32 [ %smax.j.next, %for.j ]203 %i.inc = add i32 %i, 1204 %cmp.i = icmp slt i32 %i.inc, 2205 br i1 %cmp.i, label %for.i.header, label %exit206 207exit:208 ret void209}210 211 212; Check that interchanging the loops is legal for the unsigned-minimum reduction.213;214; unsigned umin = init;215; for (int i = 0; i < 2; i++)216; for (int j = 0; j < 2; j++)217; umin = (A[j][i] < umin) ? A[j][i] : umin;218 219; CHECK: --- !Pass220; CHECK-NEXT: Pass: loop-interchange221; CHECK-NEXT: Name: Interchanged222; CHECK-NEXT: Function: reduction_umin223define void @reduction_umin(ptr %A, i32 %init) {224entry:225 br label %for.i.header226 227for.i.header:228 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]229 %umin.i = phi i32 [ %init, %entry ], [ %umin.i.lcssa, %for.i.latch ]230 br label %for.j231 232for.j:233 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]234 %umin.j = phi i32 [ %umin.i, %for.i.header ], [ %umin.j.next, %for.j ]235 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i236 %a = load i32, ptr %idx, align 4237 %cmp = icmp ult i32 %a, %umin.j238 %umin.j.next = select i1 %cmp, i32 %a, i32 %umin.j239 %j.inc = add i32 %j, 1240 %cmp.j = icmp slt i32 %j.inc, 2241 br i1 %cmp.j, label %for.j, label %for.i.latch242 243for.i.latch:244 %umin.i.lcssa = phi i32 [ %umin.j.next, %for.j ]245 %i.inc = add i32 %i, 1246 %cmp.i = icmp slt i32 %i.inc, 2247 br i1 %cmp.i, label %for.i.header, label %exit248 249exit:250 ret void251}252 253 254; Check that interchanging the loops is legal for the unsigned-maximum reduction.255;256; unsigned umax = 0;257; for (int i = 0; i < 2; i++)258; for (int j = 0; j < 2; j++)259; smax = (A[j][i] > smax) ? A[j][i] : smax;260 261; CHECK: --- !Pass262; CHECK-NEXT: Pass: loop-interchange263; CHECK-NEXT: Name: Interchanged264; CHECK-NEXT: Function: reduction_umax265define void @reduction_umax(ptr %A) {266entry:267 br label %for.i.header268 269for.i.header:270 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]271 %umax.i = phi i32 [ 0, %entry ], [ %umax.i.lcssa, %for.i.latch ]272 br label %for.j273 274for.j:275 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]276 %umax.j = phi i32 [ %umax.i, %for.i.header ], [ %umax.j.next, %for.j ]277 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i278 %a = load i32, ptr %idx, align 4279 %cmp = icmp ugt i32 %a, %umax.j280 %umax.j.next = select i1 %cmp, i32 %a, i32 %umax.j281 %j.inc = add i32 %j, 1282 %cmp.j = icmp slt i32 %j.inc, 2283 br i1 %cmp.j, label %for.j, label %for.i.latch284 285for.i.latch:286 %umax.i.lcssa = phi i32 [ %umax.j.next, %for.j ]287 %i.inc = add i32 %i, 1288 %cmp.i = icmp slt i32 %i.inc, 2289 br i1 %cmp.i, label %for.i.header, label %exit290 291exit:292 ret void293}294 295 296; Check that interchanging the loops is legal for the any-of reduction.297;298; int any_of = 0;299; for (int i = 0; i < 2; i++)300; for (int j = 0; j < 2; j++)301; any_of = (A[j][i] == 42) ? 1 : any_of;302 303; CHECK: --- !Pass304; CHECK-NEXT: Pass: loop-interchange305; CHECK-NEXT: Name: Interchanged306; CHECK-NEXT: Function: reduction_anyof307define void @reduction_anyof(ptr %A) {308entry:309 br label %for.i.header310 311for.i.header:312 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]313 %anyof.i = phi i32 [ 0, %entry ], [ %anyof.i.lcssa, %for.i.latch ]314 br label %for.j315 316for.j:317 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]318 %anyof.j = phi i32 [ %anyof.i, %for.i.header ], [ %anyof.j.next, %for.j ]319 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i320 %a = load i32, ptr %idx, align 4321 %cmp = icmp eq i32 %a, 42322 %anyof.j.next = select i1 %cmp, i32 1, i32 %anyof.j323 %j.inc = add i32 %j, 1324 %cmp.j = icmp slt i32 %j.inc, 2325 br i1 %cmp.j, label %for.j, label %for.i.latch326 327for.i.latch:328 %anyof.i.lcssa = phi i32 [ %anyof.j.next, %for.j ]329 %i.inc = add i32 %i, 1330 %cmp.i = icmp slt i32 %i.inc, 2331 br i1 %cmp.i, label %for.i.header, label %exit332 333exit:334 ret void335}336