1; RUN: opt < %s -indvars -S | FileCheck %s 2; 3; Make sure that indvars can perform LFTR without a canonical IV. 4 5target 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" 6 7; Perform LFTR using the original pointer-type IV. 8 9; for(char* p = base; p < base + n; ++p) { 10; *p = p-base; 11; } 12define void @ptriv(i8* %base, i32 %n) nounwind { 13entry: 14 %idx.ext = sext i32 %n to i64 15 %add.ptr = getelementptr inbounds i8* %base, i64 %idx.ext 16 %cmp1 = icmp ult i8* %base, %add.ptr 17 br i1 %cmp1, label %for.body, label %for.end 18 19; CHECK: for.body: 20; CHECK: phi i8* 21; CHECK-NOT: phi 22; CHECK-NOT: add 23; CHECK: icmp ne i8* 24; CHECK: br i1 25for.body: 26 %p.02 = phi i8* [ %base, %entry ], [ %incdec.ptr, %for.body ] 27 ; cruft to make the IV useful 28 %sub.ptr.lhs.cast = ptrtoint i8* %p.02 to i64 29 %sub.ptr.rhs.cast = ptrtoint i8* %base to i64 30 %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast 31 %conv = trunc i64 %sub.ptr.sub to i8 32 store i8 %conv, i8* %p.02 33 %incdec.ptr = getelementptr inbounds i8* %p.02, i32 1 34 %cmp = icmp ult i8* %incdec.ptr, %add.ptr 35 br i1 %cmp, label %for.body, label %for.end 36 37for.end: 38 ret void 39} 40 41; It would be nice if SCEV and any loop analysis could assume that 42; preheaders exist. Unfortunately it is not always the case. This test 43; checks that SCEVExpander can handle an outer loop that has not yet 44; been simplified. As a result, the inner loop's exit test will not be 45; rewritten. 46define void @expandOuterRecurrence(i32 %arg) nounwind { 47entry: 48 %sub1 = sub nsw i32 %arg, 1 49 %cmp1 = icmp slt i32 0, %sub1 50 br i1 %cmp1, label %outer, label %exit 51 52outer: 53 %i = phi i32 [ 0, %entry ], [ %i.inc, %outer.inc ] 54 %sub2 = sub nsw i32 %arg, %i 55 %sub3 = sub nsw i32 %sub2, 1 56 %cmp2 = icmp slt i32 0, %sub3 57 br i1 %cmp2, label %inner.ph, label %outer.inc 58 59inner.ph: 60 br label %inner 61 62; CHECK: inner: 63; CHECK: icmp slt 64; CHECK: br i1 65inner: 66 %j = phi i32 [ 0, %inner.ph ], [ %j.inc, %inner ] 67 %j.inc = add nsw i32 %j, 1 68 %cmp3 = icmp slt i32 %j.inc, %sub3 69 br i1 %cmp3, label %inner, label %outer.inc 70 71; CHECK: outer.inc: 72; CHECK: icmp ne 73; CHECK: br i1 74outer.inc: 75 %i.inc = add nsw i32 %i, 1 76 %cmp4 = icmp slt i32 %i.inc, %sub1 77 br i1 %cmp4, label %outer, label %exit 78 79exit: 80 ret void 81} 82 83; Force SCEVExpander to look for an existing well-formed phi. 84; Perform LFTR without generating extra preheader code. 85define void @guardedloop([0 x double]* %matrix, [0 x double]* %vector, 86 i32 %irow, i32 %ilead) nounwind { 87; CHECK: entry: 88; CHECK-NOT: zext 89; CHECK-NOT: add 90; CHECK: loop: 91; CHECK: phi i64 92; CHECK: phi i64 93; CHECK-NOT: phi 94; CHECK: icmp ne 95; CHECK: br i1 96entry: 97 %cmp = icmp slt i32 1, %irow 98 br i1 %cmp, label %loop, label %return 99 100loop: 101 %rowidx = phi i32 [ 0, %entry ], [ %row.inc, %loop ] 102 %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ] 103 %diagidx = add nsw i32 %rowidx, %i 104 %diagidxw = sext i32 %diagidx to i64 105 %matrixp = getelementptr inbounds [0 x double]* %matrix, i32 0, i64 %diagidxw 106 %v1 = load double* %matrixp 107 %iw = sext i32 %i to i64 108 %vectorp = getelementptr inbounds [0 x double]* %vector, i32 0, i64 %iw 109 %v2 = load double* %vectorp 110 %row.inc = add nsw i32 %rowidx, %ilead 111 %i.inc = add nsw i32 %i, 1 112 %cmp196 = icmp slt i32 %i.inc, %irow 113 br i1 %cmp196, label %loop, label %return 114 115return: 116 ret void 117} 118 119; Avoid generating extra code to materialize a trip count. Skip LFTR. 120define void @unguardedloop([0 x double]* %matrix, [0 x double]* %vector, 121 i32 %irow, i32 %ilead) nounwind { 122entry: 123 br label %loop 124 125; CHECK: entry: 126; CHECK-NOT: zext 127; CHECK-NOT: add 128; CHECK: loop: 129; CHECK: phi i64 130; CHECK: phi i64 131; CHECK-NOT: phi 132; CHECK: icmp slt 133; CHECK: br i1 134loop: 135 %rowidx = phi i32 [ 0, %entry ], [ %row.inc, %loop ] 136 %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ] 137 %diagidx = add nsw i32 %rowidx, %i 138 %diagidxw = sext i32 %diagidx to i64 139 %matrixp = getelementptr inbounds [0 x double]* %matrix, i32 0, i64 %diagidxw 140 %v1 = load double* %matrixp 141 %iw = sext i32 %i to i64 142 %vectorp = getelementptr inbounds [0 x double]* %vector, i32 0, i64 %iw 143 %v2 = load double* %vectorp 144 %row.inc = add nsw i32 %rowidx, %ilead 145 %i.inc = add nsw i32 %i, 1 146 %cmp196 = icmp slt i32 %i.inc, %irow 147 br i1 %cmp196, label %loop, label %return 148 149return: 150 ret void 151} 152 153; Remove %i which is only used by the exit test. 154; Verify that SCEV can still compute a backedge count from the sign 155; extended %n, used for pointer comparison by LFTR. 156; 157; TODO: Fix for PR13371 currently makes this impossible. See 158; IndVarSimplify.cpp hasConcreteDef(). We may want to change to undef rules. 159define void @geplftr(i8* %base, i32 %x, i32 %y, i32 %n) nounwind { 160entry: 161 %x.ext = sext i32 %x to i64 162 %add.ptr = getelementptr inbounds i8* %base, i64 %x.ext 163 %y.ext = sext i32 %y to i64 164 %add.ptr10 = getelementptr inbounds i8* %add.ptr, i64 %y.ext 165 %lim = add i32 %x, %n 166 %cmp.ph = icmp ult i32 %x, %lim 167 br i1 %cmp.ph, label %loop, label %exit 168; CHECK: @geplftr 169; CHECK: loop: 170; CHECK: phi i8* 171; DISABLE-NOT: phi // This check is currently disabled 172; CHECK: getelementptr 173; CHECK: store 174; DISABLE: icmp ne i8* // This check is currently disabled 175; CHECK: br i1 176loop: 177 %i = phi i32 [ %x, %entry ], [ %inc, %loop ] 178 %aptr = phi i8* [ %add.ptr10, %entry ], [ %incdec.ptr, %loop ] 179 %incdec.ptr = getelementptr inbounds i8* %aptr, i32 1 180 store i8 3, i8* %aptr 181 %inc = add i32 %i, 1 182 %cmp = icmp ult i32 %inc, %lim 183 br i1 %cmp, label %loop, label %exit 184 185exit: 186 ret void 187} 188 189; Exercise backedge taken count verification with a never-taken loop. 190define void @nevertaken() nounwind uwtable ssp { 191entry: 192 br label %loop 193; CHECK: @nevertaken 194; CHECK: loop: 195; CHECK-NOT: phi 196; CHECK-NOT: add 197; CHECK-NOT: icmp 198; CHECK: exit: 199loop: 200 %i = phi i32 [ 0, %entry ], [ %inc, %loop ] 201 %inc = add nsw i32 %i, 1 202 %cmp = icmp sle i32 %inc, 0 203 br i1 %cmp, label %loop, label %exit 204 205exit: 206 ret void 207} 208 209; Test LFTR on an IV whose recurrence start is a non-unit pointer type. 210define void @aryptriv([256 x i8]* %base, i32 %n) nounwind { 211entry: 212 %ivstart = getelementptr inbounds [256 x i8]* %base, i32 0, i32 0 213 %ivend = getelementptr inbounds [256 x i8]* %base, i32 0, i32 %n 214 %cmp.ph = icmp ult i8* %ivstart, %ivend 215 br i1 %cmp.ph, label %loop, label %exit 216 217; CHECK: loop: 218; CHECK: phi i8* 219; CHECK-NOT: phi 220; CHECK: getelementptr 221; CHECK: store 222; CHECK: icmp ne i8* 223; CHECK: br i1 224loop: 225 %aptr = phi i8* [ %ivstart, %entry ], [ %incdec.ptr, %loop ] 226 %incdec.ptr = getelementptr inbounds i8* %aptr, i32 1 227 store i8 3, i8* %aptr 228 %cmp = icmp ult i8* %incdec.ptr, %ivend 229 br i1 %cmp, label %loop, label %exit 230 231exit: 232 ret void 233} 234