1; RUN: opt < %s -indvars -enable-iv-rewrite=false -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. 156define void @geplftr(i8* %base, i32 %x, i32 %y, i32 %n) nounwind { 157entry: 158 %x.ext = sext i32 %x to i64 159 %add.ptr = getelementptr inbounds i8* %base, i64 %x.ext 160 %y.ext = sext i32 %y to i64 161 %add.ptr10 = getelementptr inbounds i8* %add.ptr, i64 %y.ext 162 %lim = add i32 %x, %n 163 %cmp.ph = icmp ult i32 %x, %lim 164 br i1 %cmp.ph, label %loop, label %exit 165 166; CHECK: loop: 167; CHECK: phi i8* 168; CHECK-NOT: phi 169; CHECK: getelementptr 170; CHECK: store 171; CHECK: icmp ne i8* 172; CHECK: br i1 173loop: 174 %i = phi i32 [ %x, %entry ], [ %inc, %loop ] 175 %aptr = phi i8* [ %add.ptr10, %entry ], [ %incdec.ptr, %loop ] 176 %incdec.ptr = getelementptr inbounds i8* %aptr, i32 1 177 store i8 3, i8* %aptr 178 %inc = add i32 %i, 1 179 %cmp = icmp ult i32 %inc, %lim 180 br i1 %cmp, label %loop, label %exit 181 182exit: 183 ret void 184} 185 186; Exercise backedge taken count verification with a never-taken loop. 187define void @nevertaken() nounwind uwtable ssp { 188entry: 189 br label %loop 190 191; CHECK: loop: 192; CHECK-NOT: phi 193; CHECK-NOT: add 194; CHECK-NOT: icmp 195; CHECK: exit: 196loop: 197 %i = phi i32 [ 0, %entry ], [ %inc, %loop ] 198 %inc = add nsw i32 %i, 1 199 %cmp = icmp sle i32 %inc, 0 200 br i1 %cmp, label %loop, label %exit 201 202exit: 203 ret void 204} 205 206; Test LFTR on an IV whose recurrence start is a non-unit pointer type. 207define void @aryptriv([256 x i8]* %base, i32 %n) nounwind { 208entry: 209 %ivstart = getelementptr inbounds [256 x i8]* %base, i32 0, i32 0 210 %ivend = getelementptr inbounds [256 x i8]* %base, i32 0, i32 %n 211 %cmp.ph = icmp ult i8* %ivstart, %ivend 212 br i1 %cmp.ph, label %loop, label %exit 213 214; CHECK: loop: 215; CHECK: phi i8* 216; CHECK-NOT: phi 217; CHECK: getelementptr 218; CHECK: store 219; CHECK: icmp ne i8* 220; CHECK: br i1 221loop: 222 %aptr = phi i8* [ %ivstart, %entry ], [ %incdec.ptr, %loop ] 223 %incdec.ptr = getelementptr inbounds i8* %aptr, i32 1 224 store i8 3, i8* %aptr 225 %cmp = icmp ult i8* %incdec.ptr, %ivend 226 br i1 %cmp, label %loop, label %exit 227 228exit: 229 ret void 230} 231