450 lines · plain
1; RUN: opt -S -verify-memoryssa -passes=loop-sink < %s | FileCheck %s2; RUN: opt -S -verify-memoryssa -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s3 4@g = global i32 0, align 45 6; b17; / \8; b2 b69; / \ |10; b3 b4 |11; \ / |12; b5 |13; \ /14; b715; preheader: 100016; b2: 1517; b3: 718; b4: 719; Sink load to b220; CHECK: t121; CHECK: .b2:22; CHECK: load i32, ptr @g23; CHECK: .b3:24; CHECK-NOT: load i32, ptr @g25define i32 @t1(i32, i32) #0 !prof !0 {26 %3 = icmp eq i32 %1, 027 br i1 %3, label %.exit, label %.preheader28 29.preheader:30 %invariant = load i32, ptr @g31 br label %.b132 33.b1:34 %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]35 %c1 = icmp sgt i32 %iv, %036 br i1 %c1, label %.b2, label %.b6, !prof !137 38.b2:39 %c2 = icmp sgt i32 %iv, 140 br i1 %c2, label %.b3, label %.b441 42.b3:43 %t3 = sub nsw i32 %invariant, %iv44 br label %.b545 46.b4:47 %t4 = add nsw i32 %invariant, %iv48 br label %.b549 50.b5:51 %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]52 %t5 = mul nsw i32 %p5, 553 br label %.b754 55.b6:56 %t6 = add nsw i32 %iv, 10057 br label %.b758 59.b7:60 %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]61 %t7 = add nuw nsw i32 %iv, 162 %c7 = icmp eq i32 %t7, %p763 br i1 %c7, label %.b1, label %.exit, !prof !364 65.exit:66 ret i32 1067}68 69; b170; / \71; b2 b672; / \ |73; b3 b4 |74; \ / |75; b5 |76; \ /77; b778; preheader: 50079; b1: 1601680; b3: 881; b6: 882; Sink load to b3 and b683; CHECK: t284; CHECK: .preheader:85; CHECK-NOT: load i32, ptr @g86; CHECK: .b3:87; CHECK: load i32, ptr @g88; CHECK: .b4:89; CHECK: .b6:90; CHECK: load i32, ptr @g91; CHECK: .b7:92define i32 @t2(i32, i32) #0 !prof !0 {93 %3 = icmp eq i32 %1, 094 br i1 %3, label %.exit, label %.preheader95 96.preheader:97 %invariant = load i32, ptr @g98 br label %.b199 100.b1:101 %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]102 %c1 = icmp sgt i32 %iv, %0103 br i1 %c1, label %.b2, label %.b6, !prof !2104 105.b2:106 %c2 = icmp sgt i32 %iv, 1107 br i1 %c2, label %.b3, label %.b4, !prof !1108 109.b3:110 %t3 = sub nsw i32 %invariant, %iv111 br label %.b5112 113.b4:114 %t4 = add nsw i32 5, %iv115 br label %.b5116 117.b5:118 %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]119 %t5 = mul nsw i32 %p5, 5120 br label %.b7121 122.b6:123 %t6 = add nsw i32 %iv, %invariant124 br label %.b7125 126.b7:127 %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]128 %t7 = add nuw nsw i32 %iv, 1129 %c7 = icmp eq i32 %t7, %p7130 br i1 %c7, label %.b1, label %.exit, !prof !3131 132.exit:133 ret i32 10134}135 136; b1137; / \138; b2 b6139; / \ |140; b3 b4 |141; \ / |142; b5 |143; \ /144; b7145; preheader: 500146; b3: 8147; b5: 16008148; Do not sink load from preheader.149; CHECK: t3150; CHECK: .preheader:151; CHECK: load i32, ptr @g152; CHECK: .b1:153; CHECK-NOT: load i32, ptr @g154define i32 @t3(i32, i32) #0 !prof !0 {155 %3 = icmp eq i32 %1, 0156 br i1 %3, label %.exit, label %.preheader157 158.preheader:159 %invariant = load i32, ptr @g160 br label %.b1161 162.b1:163 %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]164 %c1 = icmp sgt i32 %iv, %0165 br i1 %c1, label %.b2, label %.b6, !prof !2166 167.b2:168 %c2 = icmp sgt i32 %iv, 1169 br i1 %c2, label %.b3, label %.b4, !prof !1170 171.b3:172 %t3 = sub nsw i32 %invariant, %iv173 br label %.b5174 175.b4:176 %t4 = add nsw i32 5, %iv177 br label %.b5178 179.b5:180 %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]181 %t5 = mul nsw i32 %p5, %invariant182 br label %.b7183 184.b6:185 %t6 = add nsw i32 %iv, 5186 br label %.b7187 188.b7:189 %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]190 %t7 = add nuw nsw i32 %iv, 1191 %c7 = icmp eq i32 %t7, %p7192 br i1 %c7, label %.b1, label %.exit, !prof !3193 194.exit:195 ret i32 10196}197 198; For single-BB loop with <=1 avg trip count, sink load to body199; CHECK: t4200; CHECK: .header:201; CHECK-NOT: load i32, ptr @g202; CHECK: .body:203; CHECK: load i32, ptr @g204; CHECK: .exit:205define i32 @t4(i32, i32) #0 !prof !0 {206.entry:207 %invariant = load i32, ptr @g208 br label %.header209 210.header:211 %iv = phi i32 [ %t1, %.body ], [ 0, %.entry ]212 %c0 = icmp sgt i32 %iv, %0213 br i1 %c0, label %.body, label %.exit, !prof !1214 215.body:216 %t1 = add nsw i32 %invariant, %iv217 %c1 = icmp sgt i32 %iv, %0218 br label %.header219 220.exit:221 ret i32 10222}223 224; b1225; / \226; b2 b6227; / \ |228; b3 b4 |229; \ / |230; b5 |231; \ /232; b7233; preheader: 1000234; b2: 15235; b3: 7236; b4: 7237; There is alias store in loop, do not sink load238; CHECK: t5239; CHECK: .preheader:240; CHECK: load i32, ptr @g241; CHECK: .b1:242; CHECK-NOT: load i32, ptr @g243define i32 @t5(i32, ptr) #0 !prof !0 {244 %3 = icmp eq i32 %0, 0245 br i1 %3, label %.exit, label %.preheader246 247.preheader:248 %invariant = load i32, ptr @g249 br label %.b1250 251.b1:252 %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]253 %c1 = icmp sgt i32 %iv, %0254 br i1 %c1, label %.b2, label %.b6, !prof !1255 256.b2:257 %c2 = icmp sgt i32 %iv, 1258 br i1 %c2, label %.b3, label %.b4259 260.b3:261 %t3 = sub nsw i32 %invariant, %iv262 br label %.b5263 264.b4:265 %t4 = add nsw i32 %invariant, %iv266 br label %.b5267 268.b5:269 %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]270 %t5 = mul nsw i32 %p5, 5271 br label %.b7272 273.b6:274 %t6 = call i32 @foo()275 br label %.b7276 277.b7:278 %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]279 %t7 = add nuw nsw i32 %iv, 1280 %c7 = icmp eq i32 %t7, %p7281 br i1 %c7, label %.b1, label %.exit, !prof !3282 283.exit:284 ret i32 10285}286 287; b1288; / \289; b2 b6290; / \ |291; b3 b4 |292; \ / |293; b5 |294; \ /295; b7296; preheader: 1000297; b2: 15298; b3: 7299; b4: 7300; Regardless of aliasing store in loop this load from constant memory can be sunk.301; CHECK: t5_const_memory302; CHECK: .preheader:303; CHECK-NOT: load i32, ptr @g_const304; CHECK: .b2:305; CHECK: load i32, ptr @g_const306; CHECK: br i1 %c2, label %.b3, label %.b4307define i32 @t5_const_memory(i32, ptr) #0 !prof !0 {308 %3 = icmp eq i32 %0, 0309 br i1 %3, label %.exit, label %.preheader310 311.preheader:312 %invariant = load i32, ptr @g_const313 br label %.b1314 315.b1:316 %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]317 %c1 = icmp sgt i32 %iv, %0318 br i1 %c1, label %.b2, label %.b6, !prof !1319 320.b2:321 %c2 = icmp sgt i32 %iv, 1322 br i1 %c2, label %.b3, label %.b4323 324.b3:325 %t3 = sub nsw i32 %invariant, %iv326 br label %.b5327 328.b4:329 %t4 = add nsw i32 %invariant, %iv330 br label %.b5331 332.b5:333 %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]334 %t5 = mul nsw i32 %p5, 5335 br label %.b7336 337.b6:338 %t6 = call i32 @foo()339 br label %.b7340 341.b7:342 %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]343 %t7 = add nuw nsw i32 %iv, 1344 %c7 = icmp eq i32 %t7, %p7345 br i1 %c7, label %.b1, label %.exit, !prof !3346 347.exit:348 ret i32 10349}350 351; b1352; / \353; b2 b3354; \ /355; b4356; preheader: 1000357; b2: 15358; b3: 7359; Do not sink unordered atomic load to b2360; CHECK: t6361; CHECK: .preheader:362; CHECK: load atomic i32, ptr @g unordered, align 4363; CHECK: .b2:364; CHECK-NOT: load atomic i32, ptr @g unordered, align 4365define i32 @t6(i32, i32) #0 !prof !0 {366 %3 = icmp eq i32 %1, 0367 br i1 %3, label %.exit, label %.preheader368 369.preheader:370 %invariant = load atomic i32, ptr @g unordered, align 4371 br label %.b1372 373.b1:374 %iv = phi i32 [ %t3, %.b4 ], [ 0, %.preheader ]375 %c1 = icmp sgt i32 %iv, %0376 br i1 %c1, label %.b2, label %.b3, !prof !1377 378.b2:379 %t1 = add nsw i32 %invariant, %iv380 br label %.b4381 382.b3:383 %t2 = add nsw i32 %iv, 100384 br label %.b4385 386.b4:387 %p1 = phi i32 [ %t2, %.b3 ], [ %t1, %.b2 ]388 %t3 = add nuw nsw i32 %iv, 1389 %c2 = icmp eq i32 %t3, %p1390 br i1 %c2, label %.b1, label %.exit, !prof !3391 392.exit:393 ret i32 10394}395 396@g_const = constant i32 0, align 4397 398; b1399; / \400; b2 b3401; \ /402; b4403; preheader: 1000404; b2: 0.5405; b3: 999.5406; Sink unordered atomic load to b2. It is allowed to sink into loop unordered407; load from constant.408; CHECK: t7409; CHECK: .preheader:410; CHECK-NOT: load atomic i32, ptr @g_const unordered, align 4411; CHECK: .b2:412; CHECK: load atomic i32, ptr @g_const unordered, align 4413define i32 @t7(i32, i32) #0 !prof !0 {414 %3 = icmp eq i32 %1, 0415 br i1 %3, label %.exit, label %.preheader416 417.preheader:418 %invariant = load atomic i32, ptr @g_const unordered, align 4419 br label %.b1420 421.b1:422 %iv = phi i32 [ %t3, %.b4 ], [ 0, %.preheader ]423 %c1 = icmp sgt i32 %iv, %0424 br i1 %c1, label %.b2, label %.b3, !prof !1425 426.b2:427 %t1 = add nsw i32 %invariant, %iv428 br label %.b4429 430.b3:431 %t2 = add nsw i32 %iv, 100432 br label %.b4433 434.b4:435 %p1 = phi i32 [ %t2, %.b3 ], [ %t1, %.b2 ]436 %t3 = add nuw nsw i32 %iv, 1437 %c2 = icmp eq i32 %t3, %p1438 br i1 %c2, label %.b1, label %.exit, !prof !3439 440.exit:441 ret i32 10442}443 444declare i32 @foo()445 446!0 = !{!"function_entry_count", i64 1}447!1 = !{!"branch_weights", i32 1, i32 2000}448!2 = !{!"branch_weights", i32 2000, i32 1}449!3 = !{!"branch_weights", i32 100, i32 1}450