1 ; RUN: llc < %s -O3 -march=x86-64 -mcpu=core2 | FileCheck %s -check-prefix=X64 2 ; RUN: llc < %s -O3 -march=x86 -mcpu=core2 | FileCheck %s -check-prefix=X32 3 4 ; @simple is the most basic chain of address induction variables. Chaining 5 ; saves at least one register and avoids complex addressing and setup 6 ; code. 7 ; 8 ; X64: @simple 9 ; %x * 4 10 ; X64: shlq $2 11 ; no other address computation in the preheader 12 ; X64-NEXT: xorl 13 ; X64-NEXT: .align 14 ; X64: %loop 15 ; no complex address modes 16 ; X64-NOT: (%{{[^)]+}},%{{[^)]+}}, 17 ; 18 ; X32: @simple 19 ; no expensive address computation in the preheader 20 ; X32-NOT: imul 21 ; X32: %loop 22 ; no complex address modes 23 ; X32-NOT: (%{{[^)]+}},%{{[^)]+}}, 24 define i32 @simple(i32* %a, i32* %b, i32 %x) nounwind { 25 entry: 26 br label %loop 27 loop: 28 %iv = phi i32* [ %a, %entry ], [ %iv4, %loop ] 29 %s = phi i32 [ 0, %entry ], [ %s4, %loop ] 30 %v = load i32* %iv 31 %iv1 = getelementptr inbounds i32* %iv, i32 %x 32 %v1 = load i32* %iv1 33 %iv2 = getelementptr inbounds i32* %iv1, i32 %x 34 %v2 = load i32* %iv2 35 %iv3 = getelementptr inbounds i32* %iv2, i32 %x 36 %v3 = load i32* %iv3 37 %s1 = add i32 %s, %v 38 %s2 = add i32 %s1, %v1 39 %s3 = add i32 %s2, %v2 40 %s4 = add i32 %s3, %v3 41 %iv4 = getelementptr inbounds i32* %iv3, i32 %x 42 %cmp = icmp eq i32* %iv4, %b 43 br i1 %cmp, label %exit, label %loop 44 exit: 45 ret i32 %s4 46 } 47 48 ; @user is not currently chained because the IV is live across memory ops. 49 ; 50 ; X64: @user 51 ; X64: shlq $4 52 ; X64: lea 53 ; X64: lea 54 ; X64: %loop 55 ; complex address modes 56 ; X64: (%{{[^)]+}},%{{[^)]+}}, 57 ; 58 ; X32: @user 59 ; expensive address computation in the preheader 60 ; X32: imul 61 ; X32: %loop 62 ; complex address modes 63 ; X32: (%{{[^)]+}},%{{[^)]+}}, 64 define i32 @user(i32* %a, i32* %b, i32 %x) nounwind { 65 entry: 66 br label %loop 67 loop: 68 %iv = phi i32* [ %a, %entry ], [ %iv4, %loop ] 69 %s = phi i32 [ 0, %entry ], [ %s4, %loop ] 70 %v = load i32* %iv 71 %iv1 = getelementptr inbounds i32* %iv, i32 %x 72 %v1 = load i32* %iv1 73 %iv2 = getelementptr inbounds i32* %iv1, i32 %x 74 %v2 = load i32* %iv2 75 %iv3 = getelementptr inbounds i32* %iv2, i32 %x 76 %v3 = load i32* %iv3 77 %s1 = add i32 %s, %v 78 %s2 = add i32 %s1, %v1 79 %s3 = add i32 %s2, %v2 80 %s4 = add i32 %s3, %v3 81 %iv4 = getelementptr inbounds i32* %iv3, i32 %x 82 store i32 %s4, i32* %iv 83 %cmp = icmp eq i32* %iv4, %b 84 br i1 %cmp, label %exit, label %loop 85 exit: 86 ret i32 %s4 87 } 88 89 ; @extrastride is a slightly more interesting case of a single 90 ; complete chain with multiple strides. The test case IR is what LSR 91 ; used to do, and exactly what we don't want to do. LSR's new IV 92 ; chaining feature should now undo the damage. 93 ; 94 ; X64: extrastride: 95 ; We currently don't handle this on X64 because the sexts cause 96 ; strange increment expressions like this: 97 ; IV + ((sext i32 (2 * %s) to i64) + (-1 * (sext i32 %s to i64))) 98 ; 99 ; X32: extrastride: 100 ; no spills in the preheader 101 ; X32-NOT: mov{{.*}}(%esp){{$}} 102 ; X32: %for.body{{$}} 103 ; no complex address modes 104 ; X32-NOT: (%{{[^)]+}},%{{[^)]+}}, 105 ; no reloads 106 ; X32-NOT: (%esp) 107 define void @extrastride(i8* nocapture %main, i32 %main_stride, i32* nocapture %res, i32 %x, i32 %y, i32 %z) nounwind { 108 entry: 109 %cmp8 = icmp eq i32 %z, 0 110 br i1 %cmp8, label %for.end, label %for.body.lr.ph 111 112 for.body.lr.ph: ; preds = %entry 113 %add.ptr.sum = shl i32 %main_stride, 1 ; s*2 114 %add.ptr1.sum = add i32 %add.ptr.sum, %main_stride ; s*3 115 %add.ptr2.sum = add i32 %x, %main_stride ; s + x 116 %add.ptr4.sum = shl i32 %main_stride, 2 ; s*4 117 %add.ptr3.sum = add i32 %add.ptr2.sum, %add.ptr4.sum ; total IV stride = s*5+x 118 br label %for.body 119 120 for.body: ; preds = %for.body.lr.ph, %for.body 121 %main.addr.011 = phi i8* [ %main, %for.body.lr.ph ], [ %add.ptr6, %for.body ] 122 %i.010 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ] 123 %res.addr.09 = phi i32* [ %res, %for.body.lr.ph ], [ %add.ptr7, %for.body ] 124 %0 = bitcast i8* %main.addr.011 to i32* 125 %1 = load i32* %0, align 4 126 %add.ptr = getelementptr inbounds i8* %main.addr.011, i32 %main_stride 127 %2 = bitcast i8* %add.ptr to i32* 128 %3 = load i32* %2, align 4 129 %add.ptr1 = getelementptr inbounds i8* %main.addr.011, i32 %add.ptr.sum 130 %4 = bitcast i8* %add.ptr1 to i32* 131 %5 = load i32* %4, align 4 132 %add.ptr2 = getelementptr inbounds i8* %main.addr.011, i32 %add.ptr1.sum 133 %6 = bitcast i8* %add.ptr2 to i32* 134 %7 = load i32* %6, align 4 135 %add.ptr3 = getelementptr inbounds i8* %main.addr.011, i32 %add.ptr4.sum 136 %8 = bitcast i8* %add.ptr3 to i32* 137 %9 = load i32* %8, align 4 138 %add = add i32 %3, %1 139 %add4 = add i32 %add, %5 140 %add5 = add i32 %add4, %7 141 %add6 = add i32 %add5, %9 142 store i32 %add6, i32* %res.addr.09, align 4 143 %add.ptr6 = getelementptr inbounds i8* %main.addr.011, i32 %add.ptr3.sum 144 %add.ptr7 = getelementptr inbounds i32* %res.addr.09, i32 %y 145 %inc = add i32 %i.010, 1 146 %cmp = icmp eq i32 %inc, %z 147 br i1 %cmp, label %for.end, label %for.body 148 149 for.end: ; preds = %for.body, %entry 150 ret void 151 } 152 153 ; @foldedidx is an unrolled variant of this loop: 154 ; for (unsigned long i = 0; i < len; i += s) { 155 ; c[i] = a[i] + b[i]; 156 ; } 157 ; where 's' can be folded into the addressing mode. 158 ; Consequently, we should *not* form any chains. 159 ; 160 ; X64: foldedidx: 161 ; X64: movzbl -3( 162 ; 163 ; X32: foldedidx: 164 ; X32: movzbl -3( 165 define void @foldedidx(i8* nocapture %a, i8* nocapture %b, i8* nocapture %c) nounwind ssp { 166 entry: 167 br label %for.body 168 169 for.body: ; preds = %for.body, %entry 170 %i.07 = phi i32 [ 0, %entry ], [ %inc.3, %for.body ] 171 %arrayidx = getelementptr inbounds i8* %a, i32 %i.07 172 %0 = load i8* %arrayidx, align 1 173 %conv5 = zext i8 %0 to i32 174 %arrayidx1 = getelementptr inbounds i8* %b, i32 %i.07 175 %1 = load i8* %arrayidx1, align 1 176 %conv26 = zext i8 %1 to i32 177 %add = add nsw i32 %conv26, %conv5 178 %conv3 = trunc i32 %add to i8 179 %arrayidx4 = getelementptr inbounds i8* %c, i32 %i.07 180 store i8 %conv3, i8* %arrayidx4, align 1 181 %inc1 = or i32 %i.07, 1 182 %arrayidx.1 = getelementptr inbounds i8* %a, i32 %inc1 183 %2 = load i8* %arrayidx.1, align 1 184 %conv5.1 = zext i8 %2 to i32 185 %arrayidx1.1 = getelementptr inbounds i8* %b, i32 %inc1 186 %3 = load i8* %arrayidx1.1, align 1 187 %conv26.1 = zext i8 %3 to i32 188 %add.1 = add nsw i32 %conv26.1, %conv5.1 189 %conv3.1 = trunc i32 %add.1 to i8 190 %arrayidx4.1 = getelementptr inbounds i8* %c, i32 %inc1 191 store i8 %conv3.1, i8* %arrayidx4.1, align 1 192 %inc.12 = or i32 %i.07, 2 193 %arrayidx.2 = getelementptr inbounds i8* %a, i32 %inc.12 194 %4 = load i8* %arrayidx.2, align 1 195 %conv5.2 = zext i8 %4 to i32 196 %arrayidx1.2 = getelementptr inbounds i8* %b, i32 %inc.12 197 %5 = load i8* %arrayidx1.2, align 1 198 %conv26.2 = zext i8 %5 to i32 199 %add.2 = add nsw i32 %conv26.2, %conv5.2 200 %conv3.2 = trunc i32 %add.2 to i8 201 %arrayidx4.2 = getelementptr inbounds i8* %c, i32 %inc.12 202 store i8 %conv3.2, i8* %arrayidx4.2, align 1 203 %inc.23 = or i32 %i.07, 3 204 %arrayidx.3 = getelementptr inbounds i8* %a, i32 %inc.23 205 %6 = load i8* %arrayidx.3, align 1 206 %conv5.3 = zext i8 %6 to i32 207 %arrayidx1.3 = getelementptr inbounds i8* %b, i32 %inc.23 208 %7 = load i8* %arrayidx1.3, align 1 209 %conv26.3 = zext i8 %7 to i32 210 %add.3 = add nsw i32 %conv26.3, %conv5.3 211 %conv3.3 = trunc i32 %add.3 to i8 212 %arrayidx4.3 = getelementptr inbounds i8* %c, i32 %inc.23 213 store i8 %conv3.3, i8* %arrayidx4.3, align 1 214 %inc.3 = add nsw i32 %i.07, 4 215 %exitcond.3 = icmp eq i32 %inc.3, 400 216 br i1 %exitcond.3, label %for.end, label %for.body 217 218 for.end: ; preds = %for.body 219 ret void 220 } 221 222 ; @multioper tests instructions with multiple IV user operands. We 223 ; should be able to chain them independent of each other. 224 ; 225 ; X64: @multioper 226 ; X64: %for.body 227 ; X64: movl %{{.*}},4) 228 ; X64-NEXT: leal 1( 229 ; X64-NEXT: movl %{{.*}},4) 230 ; X64-NEXT: leal 2( 231 ; X64-NEXT: movl %{{.*}},4) 232 ; X64-NEXT: leal 3( 233 ; X64-NEXT: movl %{{.*}},4) 234 ; 235 ; X32: @multioper 236 ; X32: %for.body 237 ; X32: movl %{{.*}},4) 238 ; X32-NEXT: leal 1( 239 ; X32-NEXT: movl %{{.*}},4) 240 ; X32-NEXT: leal 2( 241 ; X32-NEXT: movl %{{.*}},4) 242 ; X32-NEXT: leal 3( 243 ; X32-NEXT: movl %{{.*}},4) 244 define void @multioper(i32* %a, i32 %n) nounwind { 245 entry: 246 br label %for.body 247 248 for.body: 249 %p = phi i32* [ %p.next, %for.body ], [ %a, %entry ] 250 %i = phi i32 [ %inc4, %for.body ], [ 0, %entry ] 251 store i32 %i, i32* %p, align 4 252 %inc1 = or i32 %i, 1 253 %add.ptr.i1 = getelementptr inbounds i32* %p, i32 1 254 store i32 %inc1, i32* %add.ptr.i1, align 4 255 %inc2 = add nsw i32 %i, 2 256 %add.ptr.i2 = getelementptr inbounds i32* %p, i32 2 257 store i32 %inc2, i32* %add.ptr.i2, align 4 258 %inc3 = add nsw i32 %i, 3 259 %add.ptr.i3 = getelementptr inbounds i32* %p, i32 3 260 store i32 %inc3, i32* %add.ptr.i3, align 4 261 %p.next = getelementptr inbounds i32* %p, i32 4 262 %inc4 = add nsw i32 %i, 4 263 %cmp = icmp slt i32 %inc4, %n 264 br i1 %cmp, label %for.body, label %exit 265 266 exit: 267 ret void 268 } 269 270 ; @testCmpZero has a ICmpZero LSR use that should not be hidden from 271 ; LSR. Profitable chains should have more than one nonzero increment 272 ; anyway. 273 ; 274 ; X32: @testCmpZero 275 ; X32: %for.body82.us 276 ; X32: dec 277 ; X32: jne 278 define void @testCmpZero(i8* %src, i8* %dst, i32 %srcidx, i32 %dstidx, i32 %len) nounwind ssp { 279 entry: 280 %dest0 = getelementptr inbounds i8* %src, i32 %srcidx 281 %source0 = getelementptr inbounds i8* %dst, i32 %dstidx 282 %add.ptr79.us.sum = add i32 %srcidx, %len 283 %lftr.limit = getelementptr i8* %src, i32 %add.ptr79.us.sum 284 br label %for.body82.us 285 286 for.body82.us: 287 %dest = phi i8* [ %dest0, %entry ], [ %incdec.ptr91.us, %for.body82.us ] 288 %source = phi i8* [ %source0, %entry ], [ %add.ptr83.us, %for.body82.us ] 289 %0 = bitcast i8* %source to i32* 290 %1 = load i32* %0, align 4 291 %trunc = trunc i32 %1 to i8 292 %add.ptr83.us = getelementptr inbounds i8* %source, i32 4 293 %incdec.ptr91.us = getelementptr inbounds i8* %dest, i32 1 294 store i8 %trunc, i8* %dest, align 1 295 %exitcond = icmp eq i8* %incdec.ptr91.us, %lftr.limit 296 br i1 %exitcond, label %return, label %for.body82.us 297 298 return: 299 ret void 300 } 301
