1; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s 2; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,irce' -S < %s 2>&1 | FileCheck %s 3 4; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 5; CHECK: irce: in function test_02: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 6; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 7; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 8; CHECK-NOT: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 9; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 10 11; UGT condition for increasing loop. 12define void @test_01(i32* %arr, i32* %a_len_ptr) #0 { 13 14; CHECK: test_01( 15; CHECK: entry: 16; CHECK-NEXT: %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0 17; CHECK-NEXT: [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at 18; CHECK-NEXT: br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit 19; CHECK: loop: 20; CHECK-NEXT: %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ] 21; CHECK-NEXT: %idx.next = add nuw nsw i32 %idx, 1 22; CHECK-NEXT: %abc = icmp ult i32 %idx, %exit.mainloop.at 23; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 24; CHECK-NOT: loop.preloop: 25; CHECK: loop.postloop: 26; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ] 27; CHECK-NEXT: %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1 28; CHECK-NEXT: %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at 29; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit 30 31entry: 32 %len = load i32, i32* %a_len_ptr, !range !0 33 br label %loop 34 35loop: 36 %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ] 37 %idx.next = add nsw nuw i32 %idx, 1 38 %abc = icmp ult i32 %idx, %len 39 br i1 %abc, label %in.bounds, label %out.of.bounds 40 41in.bounds: 42 %addr = getelementptr i32, i32* %arr, i32 %idx 43 store i32 0, i32* %addr 44 %next = icmp ugt i32 %idx.next, 100 45 br i1 %next, label %exit, label %loop 46 47out.of.bounds: 48 ret void 49 50exit: 51 ret void 52} 53 54; UGT condition for decreasing loop. 55define void @test_02(i32* %arr, i32* %a_len_ptr) #0 { 56 57; CHECK: test_02( 58; CHECK: entry: 59; CHECK-NEXT: %len = load i32, i32* %a_len_ptr, align 4, !range !0 60; CHECK-NEXT: [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1 61; CHECK-NEXT: [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1 62; CHECK-NEXT: %exit.preloop.at = add nsw i32 [[UMIN]], -1 63; CHECK-NEXT: [[COND2:%[^ ]+]] = icmp ugt i32 100, %exit.preloop.at 64; CHECK-NEXT: br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit 65; CHECK: mainloop: 66; CHECK-NEXT: br label %loop 67; CHECK: loop: 68; CHECK-NEXT: %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ] 69; CHECK-NEXT: %idx.next = add i32 %idx, -1 70; CHECK-NEXT: %abc = icmp ult i32 %idx, %len 71; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 72; CHECK-NOT: loop.postloop: 73; CHECK: loop.preloop: 74; CHECK-NEXT: %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ 100, %loop.preloop.preheader ] 75; CHECK-NEXT: %idx.next.preloop = add i32 %idx.preloop, -1 76; CHECK-NEXT: %abc.preloop = icmp ult i32 %idx.preloop, %len 77; CHECK-NEXT: br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit 78 79entry: 80 %len = load i32, i32* %a_len_ptr, !range !0 81 br label %loop 82 83loop: 84 %idx = phi i32 [ 100, %entry ], [ %idx.next, %in.bounds ] 85 %idx.next = add i32 %idx, -1 86 %abc = icmp ult i32 %idx, %len 87 br i1 %abc, label %in.bounds, label %out.of.bounds 88 89in.bounds: 90 %addr = getelementptr i32, i32* %arr, i32 %idx 91 store i32 0, i32* %addr 92 %next = icmp ugt i32 %idx.next, 0 93 br i1 %next, label %loop, label %exit 94 95out.of.bounds: 96 ret void 97 98exit: 99 ret void 100} 101 102; Check SINT_MAX + 1, test is similar to test_01. 103define void @test_03(i32* %arr, i32* %a_len_ptr) #0 { 104 105; CHECK: test_03( 106; CHECK: entry: 107; CHECK-NEXT: %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0 108; CHECK-NEXT: [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at 109; CHECK-NEXT: br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit 110; CHECK: loop: 111; CHECK-NEXT: %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ] 112; CHECK-NEXT: %idx.next = add nuw nsw i32 %idx, 1 113; CHECK-NEXT: %abc = icmp ult i32 %idx, %exit.mainloop.at 114; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 115; CHECK-NOT: loop.preloop: 116; CHECK: loop.postloop: 117; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ] 118; CHECK-NEXT: %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1 119; CHECK-NEXT: %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at 120; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit 121 122entry: 123 %len = load i32, i32* %a_len_ptr, !range !0 124 br label %loop 125 126loop: 127 %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ] 128 %idx.next = add nsw nuw i32 %idx, 1 129 %abc = icmp ult i32 %idx, %len 130 br i1 %abc, label %in.bounds, label %out.of.bounds 131 132in.bounds: 133 %addr = getelementptr i32, i32* %arr, i32 %idx 134 store i32 0, i32* %addr 135 %next = icmp ugt i32 %idx.next, 2147483648 136 br i1 %next, label %exit, label %loop 137 138out.of.bounds: 139 ret void 140 141exit: 142 ret void 143} 144 145; Check SINT_MAX + 1, test is similar to test_02. 146define void @test_04(i32* %arr, i32* %a_len_ptr) #0 { 147 148; CHECK: test_04( 149; CHECK: entry: 150; CHECK-NEXT: %len = load i32, i32* %a_len_ptr, align 4, !range !0 151; CHECK-NEXT: [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1 152; CHECK-NEXT: [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1 153; CHECK-NEXT: %exit.preloop.at = add nsw i32 [[UMIN]], -1 154; CHECK-NEXT: [[COND2:%[^ ]+]] = icmp ugt i32 -2147483648, %exit.preloop.at 155; CHECK-NEXT: br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit 156; CHECK: mainloop: 157; CHECK-NEXT: br label %loop 158; CHECK: loop: 159; CHECK-NEXT: %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ] 160; CHECK-NEXT: %idx.next = add i32 %idx, -1 161; CHECK-NEXT: %abc = icmp ult i32 %idx, %len 162; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 163; CHECK-NOT: loop.postloop: 164; CHECK: loop.preloop: 165; CHECK-NEXT: %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ -2147483648, %loop.preloop.preheader ] 166; CHECK-NEXT: %idx.next.preloop = add i32 %idx.preloop, -1 167; CHECK-NEXT: %abc.preloop = icmp ult i32 %idx.preloop, %len 168; CHECK-NEXT: br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit 169 170entry: 171 %len = load i32, i32* %a_len_ptr, !range !0 172 br label %loop 173 174loop: 175 %idx = phi i32 [ 2147483648, %entry ], [ %idx.next, %in.bounds ] 176 %idx.next = add i32 %idx, -1 177 %abc = icmp ult i32 %idx, %len 178 br i1 %abc, label %in.bounds, label %out.of.bounds 179 180in.bounds: 181 %addr = getelementptr i32, i32* %arr, i32 %idx 182 store i32 0, i32* %addr 183 %next = icmp ugt i32 %idx.next, 0 184 br i1 %next, label %loop, label %exit 185 186out.of.bounds: 187 ret void 188 189exit: 190 ret void 191} 192 193; Increasing loop, UINT_MAX. Negative test: we cannot add 1 to UINT_MAX. 194define void @test_05(i32* %arr, i32* %a_len_ptr) #0 { 195 196; CHECK: test_05( 197; CHECK-NOT: loop.preloop: 198; CHECK-NOT: loop.postloop: 199 200entry: 201 %len = load i32, i32* %a_len_ptr, !range !0 202 br label %loop 203 204loop: 205 %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ] 206 %idx.next = add nsw nuw i32 %idx, 1 207 %abc = icmp ult i32 %idx, %len 208 br i1 %abc, label %in.bounds, label %out.of.bounds 209 210in.bounds: 211 %addr = getelementptr i32, i32* %arr, i32 %idx 212 store i32 0, i32* %addr 213 %next = icmp ugt i32 %idx.next, 4294967295 214 br i1 %next, label %exit, label %loop 215 216out.of.bounds: 217 ret void 218 219exit: 220 ret void 221} 222 223; Decreasing loop, UINT_MAX. Positive test. 224define void @test_06(i32* %arr, i32* %a_len_ptr) #0 { 225 226; CHECK: test_06( 227; CHECK: mainloop: 228; CHECK-NEXT: br label %loop 229; CHECK: loop: 230; CHECK-NEXT: %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ] 231; CHECK-NEXT: %idx.next = add nuw i32 %idx, -1 232; CHECK-NEXT: %abc = icmp ult i32 %idx, %len 233; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 234; CHECK-NOT: loop.postloop: 235; CHECK: loop.preloop: 236; CHECK-NEXT: %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ -1, %loop.preloop.preheader ] 237; CHECK-NEXT: %idx.next.preloop = add nuw i32 %idx.preloop, -1 238; CHECK-NEXT: %abc.preloop = icmp ult i32 %idx.preloop, %len 239; CHECK-NEXT: br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit 240 241entry: 242 %len = load i32, i32* %a_len_ptr, !range !0 243 br label %loop 244 245loop: 246 %idx = phi i32 [ 4294967295, %entry ], [ %idx.next, %in.bounds ] 247 %idx.next = add nuw i32 %idx, -1 248 %abc = icmp ult i32 %idx, %len 249 br i1 %abc, label %in.bounds, label %out.of.bounds 250 251in.bounds: 252 %addr = getelementptr i32, i32* %arr, i32 %idx 253 store i32 0, i32* %addr 254 %next = icmp ugt i32 %idx.next, 0 255 br i1 %next, label %loop, label %exit 256 257out.of.bounds: 258 ret void 259 260exit: 261 ret void 262} 263 264!0 = !{i32 0, i32 50} 265