365 lines · plain
1; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -pass-remarks-missed='loop-interchange' -pass-remarks-output=%t -S \2; RUN: -verify-dom-info -verify-loop-info -verify-loop-lcssa -stats 2>&1 | FileCheck %s3; RUN: FileCheck --input-file=%t --check-prefix=REMARKS %s4 5 6target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"7 8; REMARKS: --- !Analysis9; REMARKS-NEXT: Pass: loop-interchange10; REMARKS-NEXT: Name: Dependence11; REMARKS-NEXT: Function: test112; REMARKS-NEXT: Args:13; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.14; REMARKS-NEXT: ...15 16; REMARKS: --- !Passed17; REMARKS-NEXT: Pass: loop-interchange18; REMARKS-NEXT: Name: Interchanged19; REMARKS-NEXT: Function: test120 21define i64 @test1(ptr %Arr) {22; CHECK-LABEL: @test1(23; CHECK-NEXT: entry:24; CHECK-NEXT: br label [[FOR2_PREHEADER:%.*]]25; CHECK: for1.header.preheader:26; CHECK-NEXT: br label [[FOR1_HEADER:%.*]]27; CHECK: for1.header:28; CHECK-NEXT: [[INDVARS_IV23:%.*]] = phi i64 [ [[INDVARS_IV_NEXT24:%.*]], [[FOR1_INC:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ]29; CHECK-NEXT: [[SUM_INNER:%.*]] = phi i64 [ [[SUM_INC:%.*]], [[FOR1_INC]] ], [ [[SUM_OUTER:%.*]], [[FOR1_HEADER_PREHEADER]] ]30; CHECK-NEXT: br label [[FOR2_SPLIT1:%.*]]31; CHECK: for2.preheader:32; CHECK-NEXT: br label [[FOR2:%.*]]33; CHECK: for2:34; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT_3:%.*]], [[FOR2_SPLIT:%.*]] ], [ 0, [[FOR2_PREHEADER]] ]35; CHECK-NEXT: [[SUM_OUTER]] = phi i64 [ [[SUM_INC_LCSSA:%.*]], [[FOR2_SPLIT]] ], [ 0, [[FOR2_PREHEADER]] ]36; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]]37; CHECK: for2.split1:38; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds [100 x [100 x i64]], ptr [[ARR:%.*]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV23]]39; CHECK-NEXT: [[LV:%.*]] = load i64, ptr [[ARRAYIDX]], align 440; CHECK-NEXT: [[SUM_INC]] = add i64 [[SUM_INNER]], [[LV]]41; CHECK-NEXT: [[IV_ORIGINAL:%.*]] = add nuw nsw i64 [[INDVARS_IV]], 142; CHECK-NEXT: [[EXIT1_ORIGINAL:%.*]] = icmp eq i64 [[IV_ORIGINAL]], 10043; CHECK-NEXT: br label [[FOR1_INC]]44; CHECK: for2.split:45; CHECK-NEXT: [[SUM_INC_LCSSA]] = phi i64 [ [[SUM_INC]], %for1.inc ]46; CHECK-NEXT: [[INDVARS_IV_NEXT_3]] = add nuw nsw i64 [[INDVARS_IV]], 147; CHECK-NEXT: [[EXIT1:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT_3]], 10048; CHECK-NEXT: br i1 [[EXIT1]], label [[FOR1_LOOPEXIT:%.*]], label [[FOR2]]49; CHECK: for1.inc:50; CHECK-NEXT: [[INDVARS_IV_NEXT24]] = add nuw nsw i64 [[INDVARS_IV23]], 151; CHECK-NEXT: [[EXIT2:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT24]], 10052; CHECK-NEXT: br i1 [[EXIT2]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]]53; CHECK: for1.loopexit:54; CHECK-NEXT: [[SUM_INC_LCSSA2:%.*]] = phi i64 [ [[SUM_INC_LCSSA]], [[FOR2_SPLIT]] ]55; CHECK-NEXT: ret i64 [[SUM_INC_LCSSA2]]56;57entry:58 br label %for1.header59 60for1.header: ; preds = %for1.inc, %entry61 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]62 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]63 br label %for264 65for2: ; preds = %for2, %for1.header66 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]67 %sum.inner = phi i64 [ %sum.outer, %for1.header ], [ %sum.inc, %for2 ]68 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv2369 %lv = load i64, ptr %arrayidx, align 470 %sum.inc = add i64 %sum.inner, %lv71 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 172 %exit1 = icmp eq i64 %indvars.iv.next.3, 10073 br i1 %exit1, label %for1.inc, label %for274 75for1.inc: ; preds = %for276 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]77 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 178 %exit2 = icmp eq i64 %indvars.iv.next24, 10079 br i1 %exit2, label %for1.loopexit, label %for1.header80 81for1.loopexit: ; preds = %for1.inc82 %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]83 ret i64 %sum.inc.lcssa284}85 86; In this test case, the inner reduction PHI %inner does not involve the outer87; reduction PHI %sum.outer, do not interchange.88; REMARKS: --- !Analysis89; REMARKS-NEXT: Pass: loop-interchange90; REMARKS-NEXT: Name: Dependence91; REMARKS-NEXT: Function: test292; REMARKS-NEXT: Args:93; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.94; REMARKS-NEXT: ...95 96; REMARKS: --- !Missed97; REMARKS-NEXT: Pass: loop-interchange98; REMARKS-NEXT: Name: UnsupportedPHIOuter99; REMARKS-NEXT: Function: test2100 101define i64 @test2(ptr %Arr) {102entry:103 br label %for1.header104 105for1.header: ; preds = %for1.inc, %entry106 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]107 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]108 br label %for2109 110for2: ; preds = %for2, %for1.header111 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]112 %inner = phi i64 [ %indvars.iv23, %for1.header ], [ %sum.inc, %for2 ]113 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23114 %lv = load i64, ptr %arrayidx, align 4115 %sum.inc = add i64 %inner, %lv116 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1117 %exit1 = icmp eq i64 %indvars.iv.next.3, 100118 br i1 %exit1, label %for1.inc, label %for2119 120for1.inc: ; preds = %for2121 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]122 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1123 %exit2 = icmp eq i64 %indvars.iv.next24, 100124 br i1 %exit2, label %for1.loopexit, label %for1.header125 126for1.loopexit: ; preds = %for1.inc127 %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]128 ret i64 %sum.inc.lcssa2129}130 131; Check that we do not interchange if there is an additional instruction132; between the outer and inner reduction PHIs.133; REMARKS: --- !Analysis134; REMARKS-NEXT: Pass: loop-interchange135; REMARKS-NEXT: Name: Dependence136; REMARKS-NEXT: Function: test3137; REMARKS-NEXT: Args:138; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.139; REMARKS-NEXT: ...140 141; REMARKS: --- !Missed142; REMARKS-NEXT: Pass: loop-interchange143; REMARKS-NEXT: Name: UnsupportedPHIOuter144; REMARKS-NEXT: Function: test3145 146define i64 @test3(ptr %Arr) {147entry:148 br label %for1.header149 150for1.header: ; preds = %for1.inc, %entry151 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]152 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]153 %so = add i64 %sum.outer, 10154 br label %for2155 156for2: ; preds = %for2, %for1.header157 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]158 %sum.inner = phi i64 [ %so, %for1.header ], [ %sum.inc, %for2 ]159 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23160 %lv = load i64, ptr %arrayidx, align 4161 %sum.inc = add i64 %sum.inner, %lv162 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1163 %exit1 = icmp eq i64 %indvars.iv.next.3, 100164 br i1 %exit1, label %for1.inc, label %for2165 166for1.inc: ; preds = %for2167 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]168 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1169 %exit2 = icmp eq i64 %indvars.iv.next24, 100170 br i1 %exit2, label %for1.loopexit, label %for1.header171 172for1.loopexit: ; preds = %for1.inc173 %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]174 ret i64 %sum.inc.lcssa2175}176 177; Check that we do not interchange if reduction is stored in an invariant address inside inner loop178; REMARKS: --- !Analysis179; REMARKS-NEXT: Pass: loop-interchange180; REMARKS-NEXT: Name: Dependence181; REMARKS-NEXT: Function: test4182; REMARKS-NEXT: Args:183; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.184; REMARKS-NEXT: ...185 186; REMARKS: --- !Missed187; REMARKS-NEXT: Pass: loop-interchange188; REMARKS-NEXT: Name: Dependence189; REMARKS-NEXT: Function: test4190 191define i64 @test4(ptr %Arr, ptr %dst) {192entry:193 %gep.dst = getelementptr inbounds i64, ptr %dst, i64 42194 br label %for1.header195 196for1.header: ; preds = %for1.inc, %entry197 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]198 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.lcssa, %for1.inc ]199 br label %for2200 201for2: ; preds = %for2, %for1.header202 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]203 %sum.inner = phi i64 [ %sum.outer, %for1.header ], [ %sum.inc, %for2 ]204 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23205 %lv = load i64, ptr %arrayidx, align 4206 %sum.inc = add i64 %sum.inner, %lv207 store i64 %sum.inc, ptr %gep.dst, align 4208 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1209 %exit1 = icmp eq i64 %indvars.iv.next.3, 100210 br i1 %exit1, label %for1.inc, label %for2211 212for1.inc: ; preds = %for2213 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]214 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1215 %exit2 = icmp eq i64 %indvars.iv.next24, 100216 br i1 %exit2, label %for1.loopexit, label %for1.header217 218for1.loopexit: ; preds = %for1.inc219 %sum.inc.lcssa2 = phi i64 [ %sum.inc.lcssa, %for1.inc ]220 ret i64 %sum.inc.lcssa2221}222 223; Check that we do not interchange or crash if the PHI in the outer loop gets a224; constant from the inner loop.225; REMARKS: --- !Analysis226; REMARKS-NEXT: Pass: loop-interchange227; REMARKS-NEXT: Name: Dependence228; REMARKS-NEXT: Function: test_constant_inner_loop_res229; REMARKS-NEXT: Args:230; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.231; REMARKS-NEXT: ...232 233; REMARKS: --- !Missed234; REMARKS-NEXT: Pass: loop-interchange235; REMARKS-NEXT: Name: UnsupportedPHIOuter236; REMARKS-NEXT: Function: test_constant_inner_loop_res237 238define i64 @test_constant_inner_loop_res(ptr %Arr) {239entry:240 br label %for1.header241 242for1.header: ; preds = %for1.inc, %entry243 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]244 %sum.outer = phi i64 [ 0, %entry ], [ %sum.inc.amend, %for1.inc ]245 br label %for2246 247for2: ; preds = %for2, %for1.header248 %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]249 %sum.inner = phi i64 [ %sum.outer, %for1.header ], [ %sum.inc, %for2 ]250 %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23251 %lv = load i64, ptr %arrayidx, align 4252 %sum.inc = add i64 %sum.inner, %lv253 %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1254 %exit1 = icmp eq i64 %indvars.iv.next.3, 100255 br i1 %exit1, label %for1.inc, label %for2256 257for1.inc: ; preds = %for2258 %sum.inc.lcssa = phi i64 [ %sum.inc, %for2 ]259 %const.lcssa = phi i64 [ 0, %for2 ]260 %sum.inc.amend = add i64 %const.lcssa, %sum.inc.lcssa261 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1262 %exit2 = icmp eq i64 %indvars.iv.next24, 100263 br i1 %exit2, label %for1.loopexit, label %for1.header264 265for1.loopexit: ; preds = %for1.inc266 %il.res.lcssa2 = phi i64 [ %sum.inc.amend, %for1.inc ]267 ret i64 %il.res.lcssa2268}269 270; Floating point reductions are interchanged if all the fp instructions271; involved allow reassociation.272; REMARKS: --- !Analysis273; REMARKS-NEXT: Pass: loop-interchange274; REMARKS-NEXT: Name: Dependence275; REMARKS-NEXT: Function: test5276; REMARKS-NEXT: Args:277; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.278; REMARKS-NEXT: ...279 280; REMARKS: --- !Passed281; REMARKS-NEXT: Pass: loop-interchange282; REMARKS-NEXT: Name: Interchanged283; REMARKS-NEXT: Function: test5284 285define float @test5(ptr %Arr, ptr %Arr2) {286entry:287 br label %outer.header288 289outer.header: ; preds = %outer.inc, %entry290 %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]291 %float.outer = phi float [ 1.000000e+00, %entry ], [ %float.inner.lcssa, %outer.inc ]292 br label %for.body3293 294for.body3: ; preds = %for.body3, %outer.header295 %float.inner = phi float [ %float.outer , %outer.header ], [ %float.inner.inc.inc, %for.body3 ]296 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]297 %arrayidx5 = getelementptr inbounds [100 x [100 x float]], ptr %Arr, i64 0, i64 %iv.inner, i64 %iv.outer298 %vA = load float, ptr %arrayidx5299 %float.inner.inc = fadd fast float %float.inner, %vA300 %arrayidx6 = getelementptr inbounds [100 x [100 x float]], ptr %Arr2, i64 0, i64 %iv.inner, i64 %iv.outer301 %vB = load float, ptr %arrayidx6302 %float.inner.inc.inc = fadd fast float %float.inner.inc, %vB303 %iv.inner.next = add nuw nsw i64 %iv.inner, 1304 %exitcond = icmp slt i64 %iv.inner.next, 100305 br i1 %exitcond, label %for.body3, label %outer.inc306 307outer.inc: ; preds = %for.body3308 %float.inner.lcssa = phi float [ %float.inner.inc.inc, %for.body3 ]309 %iv.outer.next = add nsw i64 %iv.outer, 1310 %cmp = icmp slt i64 %iv.outer.next, 100311 br i1 %cmp, label %outer.header, label %for.exit312 313for.exit: ; preds = %outer.inc314 %float.outer.lcssa = phi float [ %float.inner.lcssa, %outer.inc ]315 ret float %float.outer.lcssa316}317 318; Floating point reductions are not interchanged if not all the fp instructions319; involved allow reassociation.320; REMARKS: --- !Analysis321; REMARKS-NEXT: Pass: loop-interchange322; REMARKS-NEXT: Name: Dependence323; REMARKS-NEXT: Function: test6324; REMARKS-NEXT: Args:325; REMARKS-NEXT: - String: Computed dependence info, invoking the transform.326; REMARKS-NEXT: ...327 328; REMARKS: --- !Missed329; REMARKS-NEXT: Pass: loop-interchange330; REMARKS-NEXT: Name: UnsupportedPHIOuter331; REMARKS-NEXT: Function: test6332 333define float @test6(ptr %Arr, ptr %Arr2) {334entry:335 br label %outer.header336 337outer.header: ; preds = %outer.inc, %entry338 %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]339 %float.outer = phi float [ 1.000000e+00, %entry ], [ %float.inner.lcssa, %outer.inc ]340 br label %for.body3341 342for.body3: ; preds = %for.body3, %outer.header343 %float.inner = phi float [ %float.outer , %outer.header ], [ %float.inner.inc.inc, %for.body3 ]344 %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]345 %arrayidx5 = getelementptr inbounds [100 x [100 x float]], ptr %Arr, i64 0, i64 %iv.inner, i64 %iv.outer346 %vA = load float, ptr %arrayidx5347 %float.inner.inc = fadd float %float.inner, %vA ; do not allow reassociation348 %arrayidx6 = getelementptr inbounds [100 x [100 x float]], ptr %Arr2, i64 0, i64 %iv.inner, i64 %iv.outer349 %vB = load float, ptr %arrayidx6350 %float.inner.inc.inc = fadd fast float %float.inner.inc, %vB351 %iv.inner.next = add nuw nsw i64 %iv.inner, 1352 %exitcond = icmp eq i64 %iv.inner.next, 100353 br i1 %exitcond, label %outer.inc, label %for.body3354 355outer.inc: ; preds = %for.body3356 %float.inner.lcssa = phi float [ %float.inner.inc.inc, %for.body3 ]357 %iv.outer.next = add nsw i64 %iv.outer, 1358 %cmp = icmp eq i64 %iv.outer.next, 100359 br i1 %cmp, label %outer.header, label %for.exit360 361for.exit: ; preds = %outer.inc362 %float.outer.lcssa = phi float [ %float.inner.lcssa, %outer.inc ]363 ret float %float.outer.lcssa364}365