437 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 the loops aren't exchanged if there is a reduction of6; non-reassociative floating-point addition.7;8; float sum = 0;9; for (int i = 0; i < 2; i++)10; for (int j = 0; j < 2; j++)11; sum += A[j][i];12 13; CHECK: --- !Missed14; CHECK-NEXT: Pass: loop-interchange15; CHECK-NEXT: Name: UnsupportedPHIOuter16; CHECK-NEXT: Function: reduction_fadd17define void @reduction_fadd(ptr %A) {18entry:19 br label %for.i.header20 21for.i.header:22 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]23 %sum.i = phi float [ 0.0, %entry ], [ %sum.i.lcssa, %for.i.latch ]24 br label %for.j25 26for.j:27 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]28 %sum.j = phi float [ %sum.i, %for.i.header ], [ %sum.j.next, %for.j ]29 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i30 %a = load float, ptr %idx, align 431 %sum.j.next = fadd float %sum.j, %a32 %j.inc = add i32 %j, 133 %cmp.j = icmp slt i32 %j.inc, 234 br i1 %cmp.j, label %for.j, label %for.i.latch35 36for.i.latch:37 %sum.i.lcssa = phi float [ %sum.j.next, %for.j ]38 %i.inc = add i32 %i, 139 %cmp.i = icmp slt i32 %i.inc, 240 br i1 %cmp.i, label %for.i.header, label %exit41 42exit:43 ret void44}45 46; Check that the interchange is legal if the floating-point addition is marked47; as reassoc.48;49; CHECK: --- !Pass50; CHECK-NEXT: Pass: loop-interchange51; CHECK-NEXT: Name: Interchanged52; CHECK-NEXT: Function: reduction_reassoc_fadd53define void @reduction_reassoc_fadd(ptr %A) {54entry:55 br label %for.i.header56 57for.i.header:58 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]59 %sum.i = phi float [ 0.0, %entry ], [ %sum.i.lcssa, %for.i.latch ]60 br label %for.j61 62for.j:63 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]64 %sum.j = phi float [ %sum.i, %for.i.header ], [ %sum.j.next, %for.j ]65 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i66 %a = load float, ptr %idx, align 467 %sum.j.next = fadd reassoc float %sum.j, %a68 %j.inc = add i32 %j, 169 %cmp.j = icmp slt i32 %j.inc, 270 br i1 %cmp.j, label %for.j, label %for.i.latch71 72for.i.latch:73 %sum.i.lcssa = phi float [ %sum.j.next, %for.j ]74 %i.inc = add i32 %i, 175 %cmp.i = icmp slt i32 %i.inc, 276 br i1 %cmp.i, label %for.i.header, label %exit77 78exit:79 ret void80}81 82; FIXME: Is it really legal to interchange the loops when83; both reassoc and ninf are set?84; Check that the interchange is legal if the floating-point addition is marked85; as reassoc.86;87; CHECK: --- !Pass88; CHECK-NEXT: Pass: loop-interchange89; CHECK-NEXT: Name: Interchanged90; CHECK-NEXT: Function: reduction_reassoc_ninf_fadd91define void @reduction_reassoc_ninf_fadd(ptr %A) {92entry:93 br label %for.i.header94 95for.i.header:96 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]97 %sum.i = phi float [ 0.0, %entry ], [ %sum.i.lcssa, %for.i.latch ]98 br label %for.j99 100for.j:101 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]102 %sum.j = phi float [ %sum.i, %for.i.header ], [ %sum.j.next, %for.j ]103 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i104 %a = load float, ptr %idx, align 4105 %sum.j.next = fadd reassoc ninf float %sum.j, %a106 %j.inc = add i32 %j, 1107 %cmp.j = icmp slt i32 %j.inc, 2108 br i1 %cmp.j, label %for.j, label %for.i.latch109 110for.i.latch:111 %sum.i.lcssa = phi float [ %sum.j.next, %for.j ]112 %i.inc = add i32 %i, 1113 %cmp.i = icmp slt i32 %i.inc, 2114 br i1 %cmp.i, label %for.i.header, label %exit115 116exit:117 ret void118}119 120; Check that the loops aren't exchanged if there is a reduction of121; non-reassociative floating-point multiplication.122;123; float prod = 1;124; for (int i = 0; i < 2; i++)125; for (int j = 0; j < 2; j++)126; prod *= A[j][i];127 128; CHECK: --- !Missed129; CHECK-NEXT: Pass: loop-interchange130; CHECK-NEXT: Name: UnsupportedPHIOuter131; CHECK-NEXT: Function: reduction_fmul132define void @reduction_fmul(ptr %A) {133entry:134 br label %for.i.header135 136for.i.header:137 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]138 %prod.i = phi float [ 1.0, %entry ], [ %prod.i.lcssa, %for.i.latch ]139 br label %for.j140 141for.j:142 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]143 %prod.j = phi float [ %prod.i, %for.i.header ], [ %prod.j.next, %for.j ]144 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i145 %a = load float, ptr %idx, align 4146 %prod.j.next = fmul float %prod.j, %a147 %j.inc = add i32 %j, 1148 %cmp.j = icmp slt i32 %j.inc, 2149 br i1 %cmp.j, label %for.j, label %for.i.latch150 151for.i.latch:152 %prod.i.lcssa = phi float [ %prod.j.next, %for.j ]153 %i.inc = add i32 %i, 1154 %cmp.i = icmp slt i32 %i.inc, 2155 br i1 %cmp.i, label %for.i.header, label %exit156 157exit:158 ret void159}160 161; Check that the interchange is legal if the floating-point multiplication is162; marked as reassoc.163;164; CHECK: --- !Pass165; CHECK-NEXT: Pass: loop-interchange166; CHECK-NEXT: Name: Interchanged167; CHECK-NEXT: Function: reduction_reassoc_fmul168define void @reduction_reassoc_fmul(ptr %A) {169entry:170 br label %for.i.header171 172for.i.header:173 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]174 %prod.i = phi float [ 1.0, %entry ], [ %prod.i.lcssa, %for.i.latch ]175 br label %for.j176 177for.j:178 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]179 %prod.j = phi float [ %prod.i, %for.i.header ], [ %prod.j.next, %for.j ]180 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i181 %a = load float, ptr %idx, align 4182 %prod.j.next = fmul reassoc float %prod.j, %a183 %j.inc = add i32 %j, 1184 %cmp.j = icmp slt i32 %j.inc, 2185 br i1 %cmp.j, label %for.j, label %for.i.latch186 187for.i.latch:188 %prod.i.lcssa = phi float [ %prod.j.next, %for.j ]189 %i.inc = add i32 %i, 1190 %cmp.i = icmp slt i32 %i.inc, 2191 br i1 %cmp.i, label %for.i.header, label %exit192 193exit:194 ret void195}196 197; Check that the loops aren't exchanged if there is a reduction of198; non-reassociative floating-point fmuladd.199;200; float fmuladd = 0;201; for (int i = 0; i < 2; i++)202; for (int j = 0; j < 2; j++)203; fmuladd += A[j][i] * B[j][i];204 205; CHECK: --- !Missed206; CHECK-NEXT: Pass: loop-interchange207; CHECK-NEXT: Name: UnsupportedPHIOuter208; CHECK-NEXT: Function: reduction_fmuladd209define void @reduction_fmuladd(ptr %A, ptr %B) {210entry:211 br label %for.i.header212 213for.i.header:214 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]215 %fmuladd.i = phi float [ 1.0, %entry ], [ %fmuladd.i.lcssa, %for.i.latch ]216 br label %for.j217 218for.j:219 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]220 %fmuladd.j = phi float [ %fmuladd.i, %for.i.header ], [ %fmuladd.j.next, %for.j ]221 %idx.a = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i222 %idx.b = getelementptr inbounds [2 x [2 x i32]], ptr %B, i32 0, i32 %j, i32 %i223 %a = load float, ptr %idx.a, align 4224 %b = load float, ptr %idx.b, align 4225 %fmuladd.j.next = call float @llvm.fmuladd.f32(float %a, float %b, float %fmuladd.j)226 %j.inc = add i32 %j, 1227 %cmp.j = icmp slt i32 %j.inc, 2228 br i1 %cmp.j, label %for.j, label %for.i.latch229 230for.i.latch:231 %fmuladd.i.lcssa = phi float [ %fmuladd.j.next, %for.j ]232 %i.inc = add i32 %i, 1233 %cmp.i = icmp slt i32 %i.inc, 2234 br i1 %cmp.i, label %for.i.header, label %exit235 236exit:237 ret void238}239 240; Check that the interchange is legal if the floating-point fmuladd is marked241; as reassoc.242;243; CHECK: --- !Pass244; CHECK-NEXT: Pass: loop-interchange245; CHECK-NEXT: Name: Interchanged246; CHECK-NEXT: Function: reduction_reassoc_fmuladd247define void @reduction_reassoc_fmuladd(ptr %A, ptr %B) {248entry:249 br label %for.i.header250 251for.i.header:252 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]253 %fmuladd.i = phi float [ 1.0, %entry ], [ %fmuladd.i.lcssa, %for.i.latch ]254 br label %for.j255 256for.j:257 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]258 %fmuladd.j = phi float [ %fmuladd.i, %for.i.header ], [ %fmuladd.j.next, %for.j ]259 %idx.a = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i260 %idx.b = getelementptr inbounds [2 x [2 x i32]], ptr %B, i32 0, i32 %j, i32 %i261 %a = load float, ptr %idx.a, align 4262 %b = load float, ptr %idx.b, align 4263 %fmuladd.j.next = call reassoc float @llvm.fmuladd.f32(float %a, float %b, float %fmuladd.j)264 %j.inc = add i32 %j, 1265 %cmp.j = icmp slt i32 %j.inc, 2266 br i1 %cmp.j, label %for.j, label %for.i.latch267 268for.i.latch:269 %fmuladd.i.lcssa = phi float [ %fmuladd.j.next, %for.j ]270 %i.inc = add i32 %i, 1271 %cmp.i = icmp slt i32 %i.inc, 2272 br i1 %cmp.i, label %for.i.header, label %exit273 274exit:275 ret void276}277 278; Check that interchanging the loops is legal for the reassociative279; floating-point minimum.280;281; float fmin = init;282; for (int i = 0; i < 2; i++)283; for (int j = 0; j < 2; j++)284; fmin = (A[j][i] < fmin) ? A[j][i] : fmin;285 286; CHECK: --- !Pass287; CHECK-NEXT: Pass: loop-interchange288; CHECK-NEXT: Name: Interchanged289; CHECK-NEXT: Function: reduction_fmin290define void @reduction_fmin(ptr %A, float %init) {291entry:292 br label %for.i.header293 294for.i.header:295 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]296 %fmin.i = phi float [ %init, %entry ], [ %fmin.i.lcssa, %for.i.latch ]297 br label %for.j298 299for.j:300 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]301 %fmin.j = phi float [ %fmin.i, %for.i.header ], [ %fmin.j.next, %for.j ]302 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i303 %a = load float, ptr %idx, align 4304 %cmp = fcmp nnan nsz olt float %a, %fmin.j305 %fmin.j.next = select nnan nsz i1 %cmp, float %a, float %fmin.j306 %j.inc = add i32 %j, 1307 %cmp.j = icmp slt i32 %j.inc, 2308 br i1 %cmp.j, label %for.j, label %for.i.latch309 310for.i.latch:311 %fmin.i.lcssa = phi float [ %fmin.j.next, %for.j ]312 %i.inc = add i32 %i, 1313 %cmp.i = icmp slt i32 %i.inc, 2314 br i1 %cmp.i, label %for.i.header, label %exit315 316exit:317 ret void318}319 320 321; Check that interchanging the loops is legal for the floating-point322; llvm.minimumnum.323;324; CHECK: --- !Pass325; CHECK-NEXT: Pass: loop-interchange326; CHECK-NEXT: Name: Interchanged327; CHECK-NEXT: Function: reduction_fmininumnum328define void @reduction_fmininumnum(ptr %A, float %init) {329entry:330 br label %for.i.header331 332for.i.header:333 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]334 %fmin.i = phi float [ %init, %entry ], [ %fmin.i.lcssa, %for.i.latch ]335 br label %for.j336 337for.j:338 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]339 %fmin.j = phi float [ %fmin.i, %for.i.header ], [ %fmin.j.next, %for.j ]340 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i341 %a = load float, ptr %idx, align 4342 %fmin.j.next = call float @llvm.minimumnum.f32(float %a, float %fmin.j)343 %j.inc = add i32 %j, 1344 %cmp.j = icmp slt i32 %j.inc, 2345 br i1 %cmp.j, label %for.j, label %for.i.latch346 347for.i.latch:348 %fmin.i.lcssa = phi float [ %fmin.j.next, %for.j ]349 %i.inc = add i32 %i, 1350 %cmp.i = icmp slt i32 %i.inc, 2351 br i1 %cmp.i, label %for.i.header, label %exit352 353exit:354 ret void355}356 357; Check that interchanging the loops is legal for the reassociative358; floating-point maximum.359;360; float fmax = init;361; for (int i = 0; i < 2; i++)362; for (int j = 0; j < 2; j++)363; fmax = (A[j][i] > fmax) ? A[j][i] : fmax;364 365; CHECK: --- !Pass366; CHECK-NEXT: Pass: loop-interchange367; CHECK-NEXT: Name: Interchanged368; CHECK-NEXT: Function: reduction_fmax369define void @reduction_fmax(ptr %A, float %init) {370entry:371 br label %for.i.header372 373for.i.header:374 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]375 %fmax.i = phi float [ %init, %entry ], [ %fmax.i.lcssa, %for.i.latch ]376 br label %for.j377 378for.j:379 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]380 %fmax.j = phi float [ %fmax.i, %for.i.header ], [ %fmax.j.next, %for.j ]381 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i382 %a = load float, ptr %idx, align 4383 %cmp = fcmp nnan nsz ogt float %a, %fmax.j384 %fmax.j.next = select nnan nsz i1 %cmp, float %a, float %fmax.j385 %j.inc = add i32 %j, 1386 %cmp.j = icmp slt i32 %j.inc, 2387 br i1 %cmp.j, label %for.j, label %for.i.latch388 389for.i.latch:390 %fmax.i.lcssa = phi float [ %fmax.j.next, %for.j ]391 %i.inc = add i32 %i, 1392 %cmp.i = icmp slt i32 %i.inc, 2393 br i1 %cmp.i, label %for.i.header, label %exit394 395exit:396 ret void397}398 399; Check that interchanging the loops is legal for the floating-point400; llvm.maximumnum.401 402; CHECK: --- !Pass403; CHECK-NEXT: Pass: loop-interchange404; CHECK-NEXT: Name: Interchanged405; CHECK-NEXT: Function: reduction_fmaxinumnum406define void @reduction_fmaxinumnum(ptr %A, float %init) {407entry:408 br label %for.i.header409 410for.i.header:411 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]412 %fmax.i = phi float [ %init, %entry ], [ %fmax.i.lcssa, %for.i.latch ]413 br label %for.j414 415for.j:416 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j ]417 %fmax.j = phi float [ %fmax.i, %for.i.header ], [ %fmax.j.next, %for.j ]418 %idx = getelementptr inbounds [2 x [2 x i32]], ptr %A, i32 0, i32 %j, i32 %i419 %a = load float, ptr %idx, align 4420 %fmax.j.next = call float @llvm.maximumnum.f32(float %a, float %fmax.j)421 %j.inc = add i32 %j, 1422 %cmp.j = icmp slt i32 %j.inc, 2423 br i1 %cmp.j, label %for.j, label %for.i.latch424 425for.i.latch:426 %fmax.i.lcssa = phi float [ %fmax.j.next, %for.j ]427 %i.inc = add i32 %i, 1428 %cmp.i = icmp slt i32 %i.inc, 2429 br i1 %cmp.i, label %for.i.header, label %exit430 431exit:432 ret void433}434 435declare float @llvm.fmuladd.f32(float %a, float %b, float %c)436declare float @llvm.minimumnum.f32(float %a, float %b)437declare float @llvm.maximumnum.f32(float %a, float %b)