1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -S %s -passes=loop-instsimplify | FileCheck %s 3; RUN: opt -S %s -passes='loop-mssa(loop-instsimplify)' -verify-memoryssa | FileCheck %s 4 5; Test very basic folding and propagation occurs within a loop body. This should 6; collapse to the loop iteration structure and the LCSSA PHI node. 7define i32 @test1(i32 %n, i32 %x) { 8; CHECK-LABEL: @test1( 9; CHECK-NEXT: entry: 10; CHECK-NEXT: br label [[LOOP:%.*]] 11; CHECK: loop: 12; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] 13; CHECK-NEXT: [[I_NEXT]] = add nsw i32 [[I]], 1 14; CHECK-NEXT: [[I_CMP:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]] 15; CHECK-NEXT: br i1 [[I_CMP]], label [[LOOP]], label [[EXIT:%.*]] 16; CHECK: exit: 17; CHECK-NEXT: [[X_LCSSA:%.*]] = phi i32 [ [[X:%.*]], [[LOOP]] ] 18; CHECK-NEXT: ret i32 [[X_LCSSA]] 19; 20entry: 21 br label %loop 22 23loop: 24 %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 25 %x.add = add nsw i32 %x, 0 26 %x.sub = sub i32 %x.add, 0 27 %x.and = and i32 %x.sub, -1 28 %i.next = add nsw i32 %i, 1 29 %i.cmp = icmp slt i32 %i.next, %n 30 br i1 %i.cmp, label %loop, label %exit 31 32exit: 33 %x.lcssa = phi i32 [ %x.and, %loop ] 34 ret i32 %x.lcssa 35} 36 37; Test basic loop structure that still has a simplification feed a prior PHI. 38define i32 @test2(i32 %n, i32 %x) { 39; CHECK-LABEL: @test2( 40; CHECK-NEXT: entry: 41; CHECK-NEXT: br label [[LOOP:%.*]] 42; CHECK: loop: 43; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ] 44; CHECK-NEXT: [[I_NEXT]] = add nsw i32 [[I]], 1 45; CHECK-NEXT: [[I_CMP:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]] 46; CHECK-NEXT: br i1 [[I_CMP]], label [[LOOP]], label [[EXIT:%.*]] 47; CHECK: exit: 48; CHECK-NEXT: [[X_LCSSA:%.*]] = phi i32 [ [[X:%.*]], [[LOOP]] ] 49; CHECK-NEXT: ret i32 [[X_LCSSA]] 50; 51entry: 52 br label %loop 53 54loop: 55 %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 56 %x.loop = phi i32 [ %x, %entry ], [ %x.next, %loop ] 57 %x.next = add nsw i32 %x.loop, 0 58 %i.next = add nsw i32 %i, 1 59 %i.cmp = icmp slt i32 %i.next, %n 60 br i1 %i.cmp, label %loop, label %exit 61 62exit: 63 %x.lcssa = phi i32 [ %x.loop, %loop ] 64 ret i32 %x.lcssa 65} 66 67; Test a diamond CFG with inner PHI nodes. 68define i32 @test3(i32 %n, i32 %x) { 69; CHECK-LABEL: @test3( 70; CHECK-NEXT: entry: 71; CHECK-NEXT: br label [[LOOP:%.*]] 72; CHECK: loop: 73; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] 74; CHECK-NEXT: [[X_CMP:%.*]] = icmp slt i32 [[I]], 42 75; CHECK-NEXT: br i1 [[X_CMP]], label [[LOOP_LHS:%.*]], label [[LOOP_RHS:%.*]] 76; CHECK: loop.lhs: 77; CHECK-NEXT: br label [[LOOP_LATCH]] 78; CHECK: loop.rhs: 79; CHECK-NEXT: br label [[LOOP_LATCH]] 80; CHECK: loop.latch: 81; CHECK-NEXT: [[I_NEXT]] = add nsw i32 [[I]], 1 82; CHECK-NEXT: [[I_CMP:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]] 83; CHECK-NEXT: br i1 [[I_CMP]], label [[LOOP]], label [[EXIT:%.*]] 84; CHECK: exit: 85; CHECK-NEXT: [[X_LCSSA:%.*]] = phi i32 [ [[X:%.*]], [[LOOP_LATCH]] ] 86; CHECK-NEXT: ret i32 [[X_LCSSA]] 87; 88entry: 89 br label %loop 90 91loop: 92 %i = phi i32 [ 0, %entry ], [ %i.next, %loop.latch ] 93 %x.loop = phi i32 [ %x, %entry ], [ %x.phi, %loop.latch ] 94 %x.add = add nsw i32 %x.loop, 0 95 %x.cmp = icmp slt i32 %i, 42 96 br i1 %x.cmp, label %loop.lhs, label %loop.rhs 97 98loop.lhs: 99 %x.l.add = add nsw i32 %x.add, 0 100 br label %loop.latch 101 102loop.rhs: 103 %x.r.sub = sub nsw i32 %x.add, 0 104 br label %loop.latch 105 106loop.latch: 107 %x.phi = phi i32 [ %x.l.add, %loop.lhs ], [ %x.r.sub, %loop.rhs ] 108 %i.next = add nsw i32 %i, 1 109 %i.cmp = icmp slt i32 %i.next, %n 110 br i1 %i.cmp, label %loop, label %exit 111 112exit: 113 %x.lcssa = phi i32 [ %x.loop, %loop.latch ] 114 ret i32 %x.lcssa 115} 116 117; Test an inner loop that is only simplified when processing the outer loop, and 118; an outer loop only simplified when processing the inner loop. 119define i32 @test4(i32 %n, i32 %m, i32 %x) { 120; CHECK-LABEL: @test4( 121; CHECK-NEXT: entry: 122; CHECK-NEXT: br label [[LOOP:%.*]] 123; CHECK: loop: 124; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] 125; CHECK-NEXT: br label [[LOOP_INNER:%.*]] 126; CHECK: loop.inner: 127; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[LOOP]] ], [ [[J_NEXT:%.*]], [[LOOP_INNER]] ] 128; CHECK-NEXT: [[J_NEXT]] = add nsw i32 [[J]], 1 129; CHECK-NEXT: [[J_CMP:%.*]] = icmp slt i32 [[J_NEXT]], [[M:%.*]] 130; CHECK-NEXT: br i1 [[J_CMP]], label [[LOOP_INNER]], label [[LOOP_LATCH]] 131; CHECK: loop.latch: 132; CHECK-NEXT: [[I_NEXT]] = add nsw i32 [[I]], 1 133; CHECK-NEXT: [[I_CMP:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]] 134; CHECK-NEXT: br i1 [[I_CMP]], label [[LOOP]], label [[EXIT:%.*]] 135; CHECK: exit: 136; CHECK-NEXT: [[X_LCSSA:%.*]] = phi i32 [ [[X:%.*]], [[LOOP_LATCH]] ] 137; CHECK-NEXT: ret i32 [[X_LCSSA]] 138; 139entry: 140 br label %loop 141 142loop: 143 %i = phi i32 [ 0, %entry ], [ %i.next, %loop.latch ] 144 %x.loop = phi i32 [ %x, %entry ], [ %x.inner.lcssa, %loop.latch ] 145 %x.add = add nsw i32 %x.loop, 0 146 br label %loop.inner 147 148loop.inner: 149 %j = phi i32 [ 0, %loop ], [ %j.next, %loop.inner ] 150 %x.inner.loop = phi i32 [ %x.add, %loop ], [ %x.inner.add, %loop.inner ] 151 %x.inner.add = add nsw i32 %x.inner.loop, 0 152 %j.next = add nsw i32 %j, 1 153 %j.cmp = icmp slt i32 %j.next, %m 154 br i1 %j.cmp, label %loop.inner, label %loop.latch 155 156loop.latch: 157 %x.inner.lcssa = phi i32 [ %x.inner.loop, %loop.inner ] 158 %i.next = add nsw i32 %i, 1 159 %i.cmp = icmp slt i32 %i.next, %n 160 br i1 %i.cmp, label %loop, label %exit 161 162exit: 163 %x.lcssa = phi i32 [ %x.loop, %loop.latch ] 164 ret i32 %x.lcssa 165} 166