1; RUN: opt < %s -indvars -enable-iv-rewrite=false -S | FileCheck %s 2; 3; Make sure that indvars isn't inserting canonical IVs. 4; This is kinda hard to do until linear function test replacement is removed. 5 6target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" 7 8define i32 @sum(i32* %arr, i32 %n) nounwind { 9entry: 10 %precond = icmp slt i32 0, %n 11 br i1 %precond, label %ph, label %return 12 13ph: 14 br label %loop 15 16; CHECK: loop: 17; 18; We should only have 2 IVs. 19; CHECK: phi 20; CHECK: phi 21; CHECK-NOT: phi 22; 23; sext should be eliminated while preserving gep inboundsness. 24; CHECK-NOT: sext 25; CHECK: getelementptr inbounds 26; CHECK: exit: 27loop: 28 %i.02 = phi i32 [ 0, %ph ], [ %iinc, %loop ] 29 %s.01 = phi i32 [ 0, %ph ], [ %sinc, %loop ] 30 %ofs = sext i32 %i.02 to i64 31 %adr = getelementptr inbounds i32* %arr, i64 %ofs 32 %val = load i32* %adr 33 %sinc = add nsw i32 %s.01, %val 34 %iinc = add nsw i32 %i.02, 1 35 %cond = icmp slt i32 %iinc, %n 36 br i1 %cond, label %loop, label %exit 37 38exit: 39 %s.lcssa = phi i32 [ %sinc, %loop ] 40 br label %return 41 42return: 43 %s.0.lcssa = phi i32 [ %s.lcssa, %exit ], [ 0, %entry ] 44 ret i32 %s.0.lcssa 45} 46 47define i64 @suml(i32* %arr, i32 %n) nounwind { 48entry: 49 %precond = icmp slt i32 0, %n 50 br i1 %precond, label %ph, label %return 51 52ph: 53 br label %loop 54 55; CHECK: loop: 56; 57; We should only have 2 IVs. 58; CHECK: phi 59; CHECK: phi 60; CHECK-NOT: phi 61; 62; %ofs sext should be eliminated while preserving gep inboundsness. 63; CHECK-NOT: sext 64; CHECK: getelementptr inbounds 65; %vall sext should obviously not be eliminated 66; CHECK: sext 67; CHECK: exit: 68loop: 69 %i.02 = phi i32 [ 0, %ph ], [ %iinc, %loop ] 70 %s.01 = phi i64 [ 0, %ph ], [ %sinc, %loop ] 71 %ofs = sext i32 %i.02 to i64 72 %adr = getelementptr inbounds i32* %arr, i64 %ofs 73 %val = load i32* %adr 74 %vall = sext i32 %val to i64 75 %sinc = add nsw i64 %s.01, %vall 76 %iinc = add nsw i32 %i.02, 1 77 %cond = icmp slt i32 %iinc, %n 78 br i1 %cond, label %loop, label %exit 79 80exit: 81 %s.lcssa = phi i64 [ %sinc, %loop ] 82 br label %return 83 84return: 85 %s.0.lcssa = phi i64 [ %s.lcssa, %exit ], [ 0, %entry ] 86 ret i64 %s.0.lcssa 87} 88 89define void @outofbounds(i32* %first, i32* %last, i32 %idx) nounwind { 90 %precond = icmp ne i32* %first, %last 91 br i1 %precond, label %ph, label %return 92 93; CHECK: ph: 94; It's not indvars' job to perform LICM on %ofs 95; CHECK-NOT: sext 96ph: 97 br label %loop 98 99; CHECK: loop: 100; 101; Preserve exactly one pointer type IV. 102; CHECK: phi i32* 103; CHECK-NOT: phi 104; 105; Don't create any extra adds. 106; CHECK-NOT: add 107; 108; Preserve gep inboundsness, and don't factor it. 109; CHECK: getelementptr inbounds i32* %ptriv, i32 1 110; CHECK-NOT: add 111; CHECK: exit: 112loop: 113 %ptriv = phi i32* [ %first, %ph ], [ %ptrpost, %loop ] 114 %ofs = sext i32 %idx to i64 115 %adr = getelementptr inbounds i32* %ptriv, i64 %ofs 116 store i32 3, i32* %adr 117 %ptrpost = getelementptr inbounds i32* %ptriv, i32 1 118 %cond = icmp ne i32* %ptrpost, %last 119 br i1 %cond, label %loop, label %exit 120 121exit: 122 br label %return 123 124return: 125 ret void 126} 127 128%structI = type { i32 } 129 130define void @bitcastiv(i32 %start, i32 %limit, i32 %step, %structI* %base) 131nounwind 132{ 133entry: 134 br label %loop 135 136; CHECK: loop: 137; 138; Preserve casts 139; CHECK: phi i32 140; CHECK: bitcast 141; CHECK: getelementptr 142; CHECK: exit: 143loop: 144 %iv = phi i32 [%start, %entry], [%next, %loop] 145 %p = phi %structI* [%base, %entry], [%pinc, %loop] 146 %adr = getelementptr %structI* %p, i32 0, i32 0 147 store i32 3, i32* %adr 148 %pp = bitcast %structI* %p to i32* 149 store i32 4, i32* %pp 150 %pinc = getelementptr %structI* %p, i32 1 151 %next = add i32 %iv, 1 152 %cond = icmp ne i32 %next, %limit 153 br i1 %cond, label %loop, label %exit 154 155exit: 156 ret void 157} 158 159define void @maxvisitor(i32 %limit, i32* %base) nounwind { 160entry: 161 br label %loop 162 163; Test inserting a truncate at a phi use. 164; 165; CHECK: loop: 166; CHECK: phi i64 167; CHECK: trunc 168; CHECK: exit: 169loop: 170 %idx = phi i32 [ 0, %entry ], [ %idx.next, %loop.inc ] 171 %max = phi i32 [ 0, %entry ], [ %max.next, %loop.inc ] 172 %idxprom = sext i32 %idx to i64 173 %adr = getelementptr inbounds i32* %base, i64 %idxprom 174 %val = load i32* %adr 175 %cmp19 = icmp sgt i32 %val, %max 176 br i1 %cmp19, label %if.then, label %if.else 177 178if.then: 179 br label %loop.inc 180 181if.else: 182 br label %loop.inc 183 184loop.inc: 185 %max.next = phi i32 [ %idx, %if.then ], [ %max, %if.else ] 186 %idx.next = add nsw i32 %idx, 1 187 %cmp = icmp slt i32 %idx.next, %limit 188 br i1 %cmp, label %loop, label %exit 189 190exit: 191 ret void 192} 193 194define void @identityphi(i32 %limit) nounwind { 195entry: 196 br label %loop 197 198; Test an edge case of removing an identity phi that directly feeds 199; back to the loop iv. 200; 201; CHECK: loop: 202; CHECK: phi i32 203; CHECK-NOT: phi 204; CHECK: exit: 205loop: 206 %iv = phi i32 [ 0, %entry], [ %iv.next, %control ] 207 br i1 undef, label %if.then, label %control 208 209if.then: 210 br label %control 211 212control: 213 %iv.next = phi i32 [ %iv, %loop ], [ undef, %if.then ] 214 %cmp = icmp slt i32 %iv.next, %limit 215 br i1 %cmp, label %loop, label %exit 216 217exit: 218 ret void 219} 220 221define i64 @cloneOr(i32 %limit, i64* %base) nounwind { 222entry: 223 ; ensure that the loop can't overflow 224 %halfLim = ashr i32 %limit, 2 225 br label %loop 226 227; Test cloning an or, which is not an OverflowBinaryOperator. 228; 229; CHECK: loop: 230; CHECK: phi i64 231; CHECK-NOT: sext 232; CHECK: or i64 233; CHECK: exit: 234loop: 235 %iv = phi i32 [ 0, %entry], [ %iv.next, %loop ] 236 %t1 = sext i32 %iv to i64 237 %adr = getelementptr i64* %base, i64 %t1 238 %val = load i64* %adr 239 %t2 = or i32 %iv, 1 240 %t3 = sext i32 %t2 to i64 241 %iv.next = add i32 %iv, 2 242 %cmp = icmp slt i32 %iv.next, %halfLim 243 br i1 %cmp, label %loop, label %exit 244 245exit: 246 %result = and i64 %val, %t3 247 ret i64 %result 248} 249 250; The i induction variable looks like a wrap-around, but it really is just 251; a simple affine IV. Make sure that indvars simplifies through. 252define i32 @indirectRecurrence() nounwind { 253entry: 254 br label %loop 255 256; ReplaceLoopExitValue should fold the return value to constant 9. 257; CHECK: loop: 258; CHECK: phi i32 259; CHECK: ret i32 9 260loop: 261 %j.0 = phi i32 [ 1, %entry ], [ %j.next, %cond_true ] 262 %i.0 = phi i32 [ 0, %entry ], [ %j.0, %cond_true ] 263 %tmp = icmp ne i32 %j.0, 10 264 br i1 %tmp, label %cond_true, label %return 265 266cond_true: 267 %j.next = add i32 %j.0, 1 268 br label %loop 269 270return: 271 ret i32 %i.0 272} 273 274; Eliminate the congruent phis j, k, and l. 275; Eliminate the redundant IV increments k.next and l.next. 276; Two phis should remain, one starting at %init, and one at %init1. 277; Two increments should remain, one by %step and one by %step1. 278; CHECK: loop: 279; CHECK: phi i32 280; CHECK: phi i32 281; CHECK-NOT: phi 282; CHECK: add i32 283; CHECK: add i32 284; CHECK: add i32 285; CHECK-NOT: add 286; CHECK: return: 287; 288; Five live-outs should remain. 289; CHECK: lcssa = phi 290; CHECK: lcssa = phi 291; CHECK: lcssa = phi 292; CHECK: lcssa = phi 293; CHECK: lcssa = phi 294; CHECK-NOT: phi 295; CHECK: ret 296define i32 @isomorphic(i32 %init, i32 %step, i32 %lim) nounwind { 297entry: 298 %step1 = add i32 %step, 1 299 %init1 = add i32 %init, %step1 300 %l.0 = sub i32 %init1, %step1 301 br label %loop 302 303loop: 304 %ii = phi i32 [ %init1, %entry ], [ %ii.next, %loop ] 305 %i = phi i32 [ %init, %entry ], [ %ii, %loop ] 306 %j = phi i32 [ %init, %entry ], [ %j.next, %loop ] 307 %k = phi i32 [ %init1, %entry ], [ %k.next, %loop ] 308 %l = phi i32 [ %l.0, %entry ], [ %l.next, %loop ] 309 %ii.next = add i32 %ii, %step1 310 %j.next = add i32 %j, %step1 311 %k.next = add i32 %k, %step1 312 %l.step = add i32 %l, %step 313 %l.next = add i32 %l.step, 1 314 %cmp = icmp ne i32 %ii.next, %lim 315 br i1 %cmp, label %loop, label %return 316 317return: 318 %sum1 = add i32 %i, %j.next 319 %sum2 = add i32 %sum1, %k.next 320 %sum3 = add i32 %sum1, %l.step 321 %sum4 = add i32 %sum1, %l.next 322 ret i32 %sum4 323} 324 325; Test a GEP IV that is derived from another GEP IV by a nop gep that 326; lowers the type without changing the expression. 327%structIF = type { i32, float } 328 329define void @congruentgepiv(%structIF* %base) nounwind uwtable ssp { 330entry: 331 %first = getelementptr inbounds %structIF* %base, i64 0, i32 0 332 br label %loop 333 334; CHECK: loop: 335; CHECK: phi %structIF* 336; CHECK: phi i32* 337; CHECK: getelementptr inbounds 338; CHECK: getelementptr inbounds 339; CHECK: exit: 340loop: 341 %ptr.iv = phi %structIF* [ %ptr.inc, %latch ], [ %base, %entry ] 342 %next = phi i32* [ %next.inc, %latch ], [ %first, %entry ] 343 store i32 4, i32* %next 344 br i1 undef, label %latch, label %exit 345 346latch: ; preds = %for.inc50.i 347 %ptr.inc = getelementptr inbounds %structIF* %ptr.iv, i64 1 348 %next.inc = getelementptr inbounds %structIF* %ptr.inc, i64 0, i32 0 349 br label %loop 350 351exit: 352 ret void 353} 354 355; Test a widened IV that is used by a phi on different paths within the loop. 356; 357; CHECK: for.body: 358; CHECK: phi i64 359; CHECK: trunc i64 360; CHECK: if.then: 361; CHECK: for.inc: 362; CHECK: phi i32 363; CHECK: for.end: 364define void @phiUsesTrunc() nounwind { 365entry: 366 br i1 undef, label %for.body, label %for.end 367 368for.body: 369 %iv = phi i32 [ %inc, %for.inc ], [ 1, %entry ] 370 br i1 undef, label %if.then, label %if.else 371 372if.then: 373 br i1 undef, label %if.then33, label %for.inc 374 375if.then33: 376 br label %for.inc 377 378if.else: 379 br i1 undef, label %if.then97, label %for.inc 380 381if.then97: 382 %idxprom100 = sext i32 %iv to i64 383 br label %for.inc 384 385for.inc: 386 %kmin.1 = phi i32 [ %iv, %if.then33 ], [ 0, %if.then ], [ %iv, %if.then97 ], [ 0, %if.else ] 387 %inc = add nsw i32 %iv, 1 388 br i1 undef, label %for.body, label %for.end 389 390for.end: 391 ret void 392} 393