blob: 0105ae4562a988851d267582c11a459fc17b6aa7 [file] [log] [blame]
Chris Lattnerd1aaee02006-02-03 06:21:43 +00001Target Independent Opportunities:
2
Chris Lattner3cbd1602006-09-28 06:01:17 +00003//===---------------------------------------------------------------------===//
4
Chris Lattner6dc22332006-11-14 01:57:53 +00005With the recent changes to make the implicit def/use set explicit in
6machineinstrs, we should change the target descriptions for 'call' instructions
7so that the .td files don't list all the call-clobbered registers as implicit
8defs. Instead, these should be added by the code generator (e.g. on the dag).
9
10This has a number of uses:
11
121. PPC32/64 and X86 32/64 can avoid having multiple copies of call instructions
13 for their different impdef sets.
142. Targets with multiple calling convs (e.g. x86) which have different clobber
15 sets don't need copies of call instructions.
163. 'Interprocedural register allocation' can be done to reduce the clobber sets
17 of calls.
18
19//===---------------------------------------------------------------------===//
20
Chris Lattner2e339852010-12-15 07:25:55 +000021We should recognized various "overflow detection" idioms and translate them into
Chris Lattner5e0c0c72010-12-19 19:37:52 +000022llvm.uadd.with.overflow and similar intrinsics. Here is a multiply idiom:
Chris Lattner51749212010-12-15 07:28:58 +000023
24unsigned int mul(unsigned int a,unsigned int b) {
25 if ((unsigned long long)a*b>0xffffffff)
26 exit(0);
27 return a*b;
28}
29
Chris Lattner51415d22011-01-02 18:31:38 +000030The legalization code for mul-with-overflow needs to be made more robust before
31this can be implemented though.
32
Nate Begemanbb01d4f2006-03-17 01:40:33 +000033//===---------------------------------------------------------------------===//
Chris Lattnerd1aaee02006-02-03 06:21:43 +000034
35Get the C front-end to expand hypot(x,y) -> llvm.sqrt(x*x+y*y) when errno and
Chris Lattner56fe52e2008-12-10 01:30:48 +000036precision don't matter (ffastmath). Misc/mandel will like this. :) This isn't
37safe in general, even on darwin. See the libm implementation of hypot for
38examples (which special case when x/y are exactly zero to get signed zeros etc
39right).
Chris Lattnerd1aaee02006-02-03 06:21:43 +000040
Chris Lattnerd1aaee02006-02-03 06:21:43 +000041//===---------------------------------------------------------------------===//
42
Chris Lattnere43e5c02006-03-04 01:19:34 +000043On targets with expensive 64-bit multiply, we could LSR this:
44
45for (i = ...; ++i) {
46 x = 1ULL << i;
47
48into:
49 long long tmp = 1;
50 for (i = ...; ++i, tmp+=tmp)
51 x = tmp;
52
53This would be a win on ppc32, but not x86 or ppc64.
54
Chris Lattnerc9a318d2006-03-04 08:44:51 +000055//===---------------------------------------------------------------------===//
Chris Lattner5032c322006-03-05 20:00:08 +000056
57Shrink: (setlt (loadi32 P), 0) -> (setlt (loadi8 Phi), 0)
58
59//===---------------------------------------------------------------------===//
Chris Lattnerbccb0e02006-03-07 02:46:26 +000060
Chris Lattner71cf7c22010-01-01 01:29:26 +000061Reassociate should turn things like:
62
63int factorial(int X) {
64 return X*X*X*X*X*X*X*X;
65}
66
67into llvm.powi calls, allowing the code generator to produce balanced
68multiplication trees.
69
70First, the intrinsic needs to be extended to support integers, and second the
71code generator needs to be enhanced to lower these to multiplication trees.
Chris Lattner003f6332006-03-11 20:17:08 +000072
73//===---------------------------------------------------------------------===//
74
Chris Lattner4e56b682006-03-11 20:20:40 +000075Interesting? testcase for add/shift/mul reassoc:
76
77int bar(int x, int y) {
78 return x*x*x+y+x*x*x*x*x*y*y*y*y;
79}
80int foo(int z, int n) {
81 return bar(z, n) + bar(2*z, 2*n);
82}
83
Chris Lattner71cf7c22010-01-01 01:29:26 +000084This is blocked on not handling X*X*X -> powi(X, 3) (see note above). The issue
85is that we end up getting t = 2*X s = t*t and don't turn this into 4*X*X,
86which is the same number of multiplies and is canonical, because the 2*X has
87multiple uses. Here's a simple example:
88
89define i32 @test15(i32 %X1) {
90 %B = mul i32 %X1, 47 ; X1*47
91 %C = mul i32 %B, %B
92 ret i32 %C
93}
94
95
96//===---------------------------------------------------------------------===//
97
98Reassociate should handle the example in GCC PR16157:
99
100extern int a0, a1, a2, a3, a4; extern int b0, b1, b2, b3, b4;
101void f () { /* this can be optimized to four additions... */
102 b4 = a4 + a3 + a2 + a1 + a0;
103 b3 = a3 + a2 + a1 + a0;
104 b2 = a2 + a1 + a0;
105 b1 = a1 + a0;
106}
107
108This requires reassociating to forms of expressions that are already available,
109something that reassoc doesn't think about yet.
Chris Lattner2cca31f2007-05-05 22:29:06 +0000110
Chris Lattner7e3f8b62010-01-24 20:01:41 +0000111
112//===---------------------------------------------------------------------===//
113
114This function: (derived from GCC PR19988)
115double foo(double x, double y) {
116 return ((x + 0.1234 * y) * (x + -0.1234 * y));
117}
118
119compiles to:
120_foo:
121 movapd %xmm1, %xmm2
122 mulsd LCPI1_1(%rip), %xmm1
123 mulsd LCPI1_0(%rip), %xmm2
124 addsd %xmm0, %xmm1
125 addsd %xmm0, %xmm2
126 movapd %xmm1, %xmm0
127 mulsd %xmm2, %xmm0
128 ret
129
Chris Lattnere3a68d12010-01-24 20:17:09 +0000130Reassociate should be able to turn it into:
Chris Lattner7e3f8b62010-01-24 20:01:41 +0000131
132double foo(double x, double y) {
133 return ((x + 0.1234 * y) * (x - 0.1234 * y));
134}
135
136Which allows the multiply by constant to be CSE'd, producing:
137
138_foo:
139 mulsd LCPI1_0(%rip), %xmm1
140 movapd %xmm1, %xmm2
141 addsd %xmm0, %xmm2
142 subsd %xmm1, %xmm0
143 mulsd %xmm2, %xmm0
144 ret
145
146This doesn't need -ffast-math support at all. This is particularly bad because
147the llvm-gcc frontend is canonicalizing the later into the former, but clang
148doesn't have this problem.
149
Chris Lattner4e56b682006-03-11 20:20:40 +0000150//===---------------------------------------------------------------------===//
151
Chris Lattnerf1362992006-03-09 20:13:21 +0000152These two functions should generate the same code on big-endian systems:
153
154int g(int *j,int *l) { return memcmp(j,l,4); }
155int h(int *j, int *l) { return *j - *l; }
156
157this could be done in SelectionDAGISel.cpp, along with other special cases,
158for 1,2,4,8 bytes.
159
160//===---------------------------------------------------------------------===//
161
Chris Lattnere24cf9d2006-03-22 07:33:46 +0000162It would be nice to revert this patch:
163http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060213/031986.html
164
165And teach the dag combiner enough to simplify the code expanded before
166legalize. It seems plausible that this knowledge would let it simplify other
167stuff too.
168
Chris Lattner0affd762006-03-24 19:59:17 +0000169//===---------------------------------------------------------------------===//
170
Reid Spencer09575ba2007-02-15 03:39:18 +0000171For vector types, TargetData.cpp::getTypeInfo() returns alignment that is equal
Evan Chengdc1161c2006-03-31 22:35:14 +0000172to the type size. It works but can be overly conservative as the alignment of
Reid Spencer09575ba2007-02-15 03:39:18 +0000173specific vector types are target dependent.
Chris Lattner0baebb12006-04-01 04:08:29 +0000174
175//===---------------------------------------------------------------------===//
176
Dan Gohman1dbb40f2009-05-11 18:51:16 +0000177We should produce an unaligned load from code like this:
Chris Lattner0baebb12006-04-01 04:08:29 +0000178
179v4sf example(float *P) {
180 return (v4sf){P[0], P[1], P[2], P[3] };
181}
182
183//===---------------------------------------------------------------------===//
184
Chris Lattner4cda95b2006-05-18 18:26:13 +0000185Add support for conditional increments, and other related patterns. Instead
186of:
187
188 movl 136(%esp), %eax
189 cmpl $0, %eax
190 je LBB16_2 #cond_next
191LBB16_1: #cond_true
192 incl _foo
193LBB16_2: #cond_next
194
195emit:
196 movl _foo, %eax
197 cmpl $1, %edi
198 sbbl $-1, %eax
199 movl %eax, _foo
200
201//===---------------------------------------------------------------------===//
Chris Lattner240f8462006-05-19 20:45:08 +0000202
203Combine: a = sin(x), b = cos(x) into a,b = sincos(x).
204
205Expand these to calls of sin/cos and stores:
206 double sincos(double x, double *sin, double *cos);
207 float sincosf(float x, float *sin, float *cos);
208 long double sincosl(long double x, long double *sin, long double *cos);
209
210Doing so could allow SROA of the destination pointers. See also:
211http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17687
212
Chris Lattner56fe52e2008-12-10 01:30:48 +0000213This is now easily doable with MRVs. We could even make an intrinsic for this
214if anyone cared enough about sincos.
215
Chris Lattner240f8462006-05-19 20:45:08 +0000216//===---------------------------------------------------------------------===//
Chris Lattner29d7bde2006-05-19 21:01:38 +0000217
Chris Lattnerf7e34782006-09-16 23:57:51 +0000218quantum_sigma_x in 462.libquantum contains the following loop:
219
220 for(i=0; i<reg->size; i++)
221 {
222 /* Flip the target bit of each basis state */
223 reg->node[i].state ^= ((MAX_UNSIGNED) 1 << target);
224 }
225
226Where MAX_UNSIGNED/state is a 64-bit int. On a 32-bit platform it would be just
227so cool to turn it into something like:
228
Chris Lattner4a13d3b2006-09-18 04:54:35 +0000229 long long Res = ((MAX_UNSIGNED) 1 << target);
Chris Lattnerf7e34782006-09-16 23:57:51 +0000230 if (target < 32) {
231 for(i=0; i<reg->size; i++)
Chris Lattner4a13d3b2006-09-18 04:54:35 +0000232 reg->node[i].state ^= Res & 0xFFFFFFFFULL;
Chris Lattnerf7e34782006-09-16 23:57:51 +0000233 } else {
234 for(i=0; i<reg->size; i++)
Chris Lattner4a13d3b2006-09-18 04:54:35 +0000235 reg->node[i].state ^= Res & 0xFFFFFFFF00000000ULL
Chris Lattnerf7e34782006-09-16 23:57:51 +0000236 }
237
238... which would only do one 32-bit XOR per loop iteration instead of two.
239
240It would also be nice to recognize the reg->size doesn't alias reg->node[i], but
Chris Lattner8e09ad62009-11-26 01:51:18 +0000241this requires TBAA.
Chris Lattner61858782009-09-21 06:04:07 +0000242
243//===---------------------------------------------------------------------===//
244
Chris Lattnerf9325e52008-10-05 02:16:12 +0000245This isn't recognized as bswap by instcombine (yes, it really is bswap):
Chris Lattner4d475f62006-12-08 02:01:32 +0000246
247unsigned long reverse(unsigned v) {
248 unsigned t;
249 t = v ^ ((v << 16) | (v >> 16));
250 t &= ~0xff0000;
251 v = (v << 24) | (v >> 8);
252 return v ^ (t >> 8);
253}
254
Chris Lattnerf11327d2006-09-25 17:12:14 +0000255//===---------------------------------------------------------------------===//
256
Chris Lattnere9cba7b2011-02-21 02:13:39 +0000257[LOOP DELETION]
258
259We don't delete this output free loop, because trip count analysis doesn't
260realize that it is finite (if it were infinite, it would be undefined). Not
261having this blocks Loop Idiom from matching strlen and friends.
262
263void foo(char *C) {
264 int x = 0;
265 while (*C)
266 ++x,++C;
267}
268
269//===---------------------------------------------------------------------===//
270
Chris Lattner249da5c2010-01-23 18:49:30 +0000271[LOOP RECOGNITION]
272
Chris Lattner843dacc2008-10-15 16:02:15 +0000273These idioms should be recognized as popcount (see PR1488):
274
275unsigned countbits_slow(unsigned v) {
276 unsigned c;
277 for (c = 0; v; v >>= 1)
278 c += v & 1;
279 return c;
280}
281unsigned countbits_fast(unsigned v){
282 unsigned c;
283 for (c = 0; v; c++)
284 v &= v - 1; // clear the least significant bit set
285 return c;
286}
287
288BITBOARD = unsigned long long
289int PopCnt(register BITBOARD a) {
290 register int c=0;
291 while(a) {
292 c++;
293 a &= a - 1;
294 }
295 return c;
296}
297unsigned int popcount(unsigned int input) {
298 unsigned int count = 0;
299 for (unsigned int i = 0; i < 4 * 8; i++)
300 count += (input >> i) & i;
301 return count;
302}
303
Chris Lattner659c7932011-02-21 01:33:38 +0000304This should be recognized as CLZ: rdar://8459039
305
306unsigned clz_a(unsigned a) {
307 int i;
308 for (i=0;i<32;i++)
309 if (a & (1<<(31-i)))
310 return i;
311 return 32;
312}
313
Chris Lattner51415d22011-01-02 18:31:38 +0000314This sort of thing should be added to the loop idiom pass.
Chris Lattner8e09ad62009-11-26 01:51:18 +0000315
Chris Lattner843dacc2008-10-15 16:02:15 +0000316//===---------------------------------------------------------------------===//
317
Chris Lattnerf11327d2006-09-25 17:12:14 +0000318These should turn into single 16-bit (unaligned?) loads on little/big endian
319processors.
320
321unsigned short read_16_le(const unsigned char *adr) {
322 return adr[0] | (adr[1] << 8);
323}
324unsigned short read_16_be(const unsigned char *adr) {
325 return (adr[0] << 8) | adr[1];
326}
327
328//===---------------------------------------------------------------------===//
Chris Lattnerf0540032006-10-24 16:12:47 +0000329
Reid Spencer7e80b0b2006-10-26 06:15:43 +0000330-instcombine should handle this transform:
Reid Spencer266e42b2006-12-23 06:05:41 +0000331 icmp pred (sdiv X / C1 ), C2
Reid Spencer7e80b0b2006-10-26 06:15:43 +0000332when X, C1, and C2 are unsigned. Similarly for udiv and signed operands.
333
334Currently InstCombine avoids this transform but will do it when the signs of
335the operands and the sign of the divide match. See the FIXME in
336InstructionCombining.cpp in the visitSetCondInst method after the switch case
337for Instruction::UDiv (around line 4447) for more details.
338
339The SingleSource/Benchmarks/Shootout-C++/hash and hash2 tests have examples of
340this construct.
Chris Lattner20483732006-11-03 22:27:39 +0000341
342//===---------------------------------------------------------------------===//
343
Chris Lattner082da532010-01-23 17:59:23 +0000344[LOOP OPTIMIZATION]
345
346SingleSource/Benchmarks/Misc/dt.c shows several interesting optimization
347opportunities in its double_array_divs_variable function: it needs loop
348interchange, memory promotion (which LICM already does), vectorization and
349variable trip count loop unrolling (since it has a constant trip count). ICC
350apparently produces this very nice code with -ffast-math:
351
352..B1.70: # Preds ..B1.70 ..B1.69
353 mulpd %xmm0, %xmm1 #108.2
354 mulpd %xmm0, %xmm1 #108.2
355 mulpd %xmm0, %xmm1 #108.2
356 mulpd %xmm0, %xmm1 #108.2
357 addl $8, %edx #
358 cmpl $131072, %edx #108.2
359 jb ..B1.70 # Prob 99% #108.2
360
361It would be better to count down to zero, but this is a lot better than what we
362do.
363
364//===---------------------------------------------------------------------===//
365
Chris Lattner89e58132007-01-16 06:39:48 +0000366Consider:
367
368typedef unsigned U32;
369typedef unsigned long long U64;
370int test (U32 *inst, U64 *regs) {
371 U64 effective_addr2;
372 U32 temp = *inst;
373 int r1 = (temp >> 20) & 0xf;
374 int b2 = (temp >> 16) & 0xf;
375 effective_addr2 = temp & 0xfff;
376 if (b2) effective_addr2 += regs[b2];
377 b2 = (temp >> 12) & 0xf;
378 if (b2) effective_addr2 += regs[b2];
379 effective_addr2 &= regs[4];
380 if ((effective_addr2 & 3) == 0)
381 return 1;
382 return 0;
383}
384
385Note that only the low 2 bits of effective_addr2 are used. On 32-bit systems,
386we don't eliminate the computation of the top half of effective_addr2 because
387we don't have whole-function selection dags. On x86, this means we use one
388extra register for the function when effective_addr2 is declared as U64 than
389when it is declared U32.
390
Chris Lattner0169fd72009-11-10 23:47:45 +0000391PHI Slicing could be extended to do this.
392
Chris Lattner89e58132007-01-16 06:39:48 +0000393//===---------------------------------------------------------------------===//
394
Chris Lattner2cca31f2007-05-05 22:29:06 +0000395Tail call elim should be more aggressive, checking to see if the call is
396followed by an uncond branch to an exit block.
397
398; This testcase is due to tail-duplication not wanting to copy the return
399; instruction into the terminating blocks because there was other code
400; optimized out of the function after the taildup happened.
Chris Lattner6bb6a552008-02-18 18:46:39 +0000401; RUN: llvm-as < %s | opt -tailcallelim | llvm-dis | not grep call
Chris Lattner2cca31f2007-05-05 22:29:06 +0000402
Chris Lattner6bb6a552008-02-18 18:46:39 +0000403define i32 @t4(i32 %a) {
Chris Lattner2cca31f2007-05-05 22:29:06 +0000404entry:
Chris Lattner6bb6a552008-02-18 18:46:39 +0000405 %tmp.1 = and i32 %a, 1 ; <i32> [#uses=1]
406 %tmp.2 = icmp ne i32 %tmp.1, 0 ; <i1> [#uses=1]
407 br i1 %tmp.2, label %then.0, label %else.0
Chris Lattner2cca31f2007-05-05 22:29:06 +0000408
Chris Lattner6bb6a552008-02-18 18:46:39 +0000409then.0: ; preds = %entry
410 %tmp.5 = add i32 %a, -1 ; <i32> [#uses=1]
411 %tmp.3 = call i32 @t4( i32 %tmp.5 ) ; <i32> [#uses=1]
412 br label %return
Chris Lattner2cca31f2007-05-05 22:29:06 +0000413
Chris Lattner6bb6a552008-02-18 18:46:39 +0000414else.0: ; preds = %entry
415 %tmp.7 = icmp ne i32 %a, 0 ; <i1> [#uses=1]
416 br i1 %tmp.7, label %then.1, label %return
Chris Lattner2cca31f2007-05-05 22:29:06 +0000417
Chris Lattner6bb6a552008-02-18 18:46:39 +0000418then.1: ; preds = %else.0
419 %tmp.11 = add i32 %a, -2 ; <i32> [#uses=1]
420 %tmp.9 = call i32 @t4( i32 %tmp.11 ) ; <i32> [#uses=1]
421 br label %return
Chris Lattner2cca31f2007-05-05 22:29:06 +0000422
Chris Lattner6bb6a552008-02-18 18:46:39 +0000423return: ; preds = %then.1, %else.0, %then.0
424 %result.0 = phi i32 [ 0, %else.0 ], [ %tmp.3, %then.0 ],
Chris Lattner2cca31f2007-05-05 22:29:06 +0000425 [ %tmp.9, %then.1 ]
Chris Lattner6bb6a552008-02-18 18:46:39 +0000426 ret i32 %result.0
Chris Lattner2cca31f2007-05-05 22:29:06 +0000427}
Chris Lattner9958b822007-05-05 22:44:08 +0000428
429//===---------------------------------------------------------------------===//
430
Chris Lattner4afb0102008-08-10 00:47:21 +0000431Tail recursion elimination should handle:
432
433int pow2m1(int n) {
434 if (n == 0)
435 return 0;
436 return 2 * pow2m1 (n - 1) + 1;
437}
438
439Also, multiplies can be turned into SHL's, so they should be handled as if
440they were associative. "return foo() << 1" can be tail recursion eliminated.
441
442//===---------------------------------------------------------------------===//
443
Chris Lattner9958b822007-05-05 22:44:08 +0000444Argument promotion should promote arguments for recursive functions, like
445this:
446
Chris Lattner6bb6a552008-02-18 18:46:39 +0000447; RUN: llvm-as < %s | opt -argpromotion | llvm-dis | grep x.val
Chris Lattner9958b822007-05-05 22:44:08 +0000448
Chris Lattner6bb6a552008-02-18 18:46:39 +0000449define internal i32 @foo(i32* %x) {
Chris Lattner9958b822007-05-05 22:44:08 +0000450entry:
Chris Lattner6bb6a552008-02-18 18:46:39 +0000451 %tmp = load i32* %x ; <i32> [#uses=0]
452 %tmp.foo = call i32 @foo( i32* %x ) ; <i32> [#uses=1]
453 ret i32 %tmp.foo
Chris Lattner9958b822007-05-05 22:44:08 +0000454}
455
Chris Lattner6bb6a552008-02-18 18:46:39 +0000456define i32 @bar(i32* %x) {
Chris Lattner9958b822007-05-05 22:44:08 +0000457entry:
Chris Lattner6bb6a552008-02-18 18:46:39 +0000458 %tmp3 = call i32 @foo( i32* %x ) ; <i32> [#uses=1]
459 ret i32 %tmp3
Chris Lattner9958b822007-05-05 22:44:08 +0000460}
461
Chris Lattner5e224c32007-12-05 23:05:06 +0000462//===---------------------------------------------------------------------===//
Chris Lattner180f0e92007-12-28 04:42:05 +0000463
Chris Lattner9d53b612007-12-28 22:30:05 +0000464We should investigate an instruction sinking pass. Consider this silly
465example in pic mode:
466
467#include <assert.h>
468void foo(int x) {
469 assert(x);
470 //...
471}
472
473we compile this to:
474_foo:
475 subl $28, %esp
476 call "L1$pb"
477"L1$pb":
478 popl %eax
479 cmpl $0, 32(%esp)
480 je LBB1_2 # cond_true
481LBB1_1: # return
482 # ...
483 addl $28, %esp
484 ret
485LBB1_2: # cond_true
486...
487
488The PIC base computation (call+popl) is only used on one path through the
489code, but is currently always computed in the entry block. It would be
490better to sink the picbase computation down into the block for the
491assertion, as it is the only one that uses it. This happens for a lot of
492code with early outs.
493
Chris Lattner7cafd922007-12-29 01:05:01 +0000494Another example is loads of arguments, which are usually emitted into the
495entry block on targets like x86. If not used in all paths through a
496function, they should be sunk into the ones that do.
497
Chris Lattner9d53b612007-12-28 22:30:05 +0000498In this case, whole-function-isel would also handle this.
Chris Lattner180f0e92007-12-28 04:42:05 +0000499
500//===---------------------------------------------------------------------===//
Chris Lattner730d0882008-01-07 21:38:14 +0000501
502Investigate lowering of sparse switch statements into perfect hash tables:
503http://burtleburtle.net/bob/hash/perfect.html
504
505//===---------------------------------------------------------------------===//
Chris Lattner45e50322008-01-09 00:17:57 +0000506
507We should turn things like "load+fabs+store" and "load+fneg+store" into the
508corresponding integer operations. On a yonah, this loop:
509
510double a[256];
Chris Lattner6bb6a552008-02-18 18:46:39 +0000511void foo() {
512 int i, b;
513 for (b = 0; b < 10000000; b++)
514 for (i = 0; i < 256; i++)
515 a[i] = -a[i];
516}
Chris Lattner45e50322008-01-09 00:17:57 +0000517
518is twice as slow as this loop:
519
520long long a[256];
Chris Lattner6bb6a552008-02-18 18:46:39 +0000521void foo() {
522 int i, b;
523 for (b = 0; b < 10000000; b++)
524 for (i = 0; i < 256; i++)
525 a[i] ^= (1ULL << 63);
526}
Chris Lattner45e50322008-01-09 00:17:57 +0000527
528and I suspect other processors are similar. On X86 in particular this is a
529big win because doing this with integers allows the use of read/modify/write
530instructions.
531
532//===---------------------------------------------------------------------===//
Chris Lattner1d07b652008-01-10 18:25:41 +0000533
534DAG Combiner should try to combine small loads into larger loads when
535profitable. For example, we compile this C++ example:
536
537struct THotKey { short Key; bool Control; bool Shift; bool Alt; };
538extern THotKey m_HotKey;
539THotKey GetHotKey () { return m_HotKey; }
540
Chris Lattner51415d22011-01-02 18:31:38 +0000541into (-m64 -O3 -fno-exceptions -static -fomit-frame-pointer):
Chris Lattner1d07b652008-01-10 18:25:41 +0000542
Chris Lattner51415d22011-01-02 18:31:38 +0000543__Z9GetHotKeyv: ## @_Z9GetHotKeyv
544 movq _m_HotKey@GOTPCREL(%rip), %rax
545 movzwl (%rax), %ecx
546 movzbl 2(%rax), %edx
547 shlq $16, %rdx
548 orq %rcx, %rdx
549 movzbl 3(%rax), %ecx
550 shlq $24, %rcx
551 orq %rdx, %rcx
552 movzbl 4(%rax), %eax
553 shlq $32, %rax
554 orq %rcx, %rax
555 ret
Chris Lattner1d07b652008-01-10 18:25:41 +0000556
557//===---------------------------------------------------------------------===//
Chris Lattner87b0c132008-01-11 06:17:47 +0000558
Nate Begeman0fddc342008-02-18 18:39:23 +0000559We should add an FRINT node to the DAG to model targets that have legal
560implementations of ceil/floor/rint.
Chris Lattner765be882008-02-28 05:34:27 +0000561
562//===---------------------------------------------------------------------===//
563
564Consider:
565
566int test() {
Benjamin Kramerdfa40f82010-12-23 15:32:07 +0000567 long long input[8] = {1,0,1,0,1,0,1,0};
Chris Lattner765be882008-02-28 05:34:27 +0000568 foo(input);
569}
570
Chris Lattnere5d5a412011-01-01 22:52:11 +0000571Clang compiles this into:
Chris Lattner765be882008-02-28 05:34:27 +0000572
Chris Lattnere5d5a412011-01-01 22:52:11 +0000573 call void @llvm.memset.p0i8.i64(i8* %tmp, i8 0, i64 64, i32 16, i1 false)
574 %0 = getelementptr [8 x i64]* %input, i64 0, i64 0
575 store i64 1, i64* %0, align 16
576 %1 = getelementptr [8 x i64]* %input, i64 0, i64 2
577 store i64 1, i64* %1, align 16
578 %2 = getelementptr [8 x i64]* %input, i64 0, i64 4
579 store i64 1, i64* %2, align 16
580 %3 = getelementptr [8 x i64]* %input, i64 0, i64 6
581 store i64 1, i64* %3, align 16
Chris Lattner765be882008-02-28 05:34:27 +0000582
Chris Lattnere5d5a412011-01-01 22:52:11 +0000583Which gets codegen'd into:
584
585 pxor %xmm0, %xmm0
586 movaps %xmm0, -16(%rbp)
587 movaps %xmm0, -32(%rbp)
588 movaps %xmm0, -48(%rbp)
589 movaps %xmm0, -64(%rbp)
590 movq $1, -64(%rbp)
591 movq $1, -48(%rbp)
592 movq $1, -32(%rbp)
593 movq $1, -16(%rbp)
594
595It would be better to have 4 movq's of 0 instead of the movaps's.
Chris Lattner765be882008-02-28 05:34:27 +0000596
597//===---------------------------------------------------------------------===//
Chris Lattner647c6642008-03-02 02:51:40 +0000598
599http://llvm.org/PR717:
600
601The following code should compile into "ret int undef". Instead, LLVM
602produces "ret int 0":
603
604int f() {
605 int x = 4;
606 int y;
607 if (x == 3) y = 0;
608 return y;
609}
610
611//===---------------------------------------------------------------------===//
Chris Lattnerd51372a2008-03-02 19:29:42 +0000612
613The loop unroller should partially unroll loops (instead of peeling them)
614when code growth isn't too bad and when an unroll count allows simplification
615of some code within the loop. One trivial example is:
616
617#include <stdio.h>
618int main() {
619 int nRet = 17;
620 int nLoop;
621 for ( nLoop = 0; nLoop < 1000; nLoop++ ) {
622 if ( nLoop & 1 )
623 nRet += 2;
624 else
625 nRet -= 1;
626 }
627 return nRet;
628}
629
630Unrolling by 2 would eliminate the '&1' in both copies, leading to a net
631reduction in code size. The resultant code would then also be suitable for
632exit value computation.
633
634//===---------------------------------------------------------------------===//
Chris Lattneraf8d3c62008-03-17 01:47:51 +0000635
636We miss a bunch of rotate opportunities on various targets, including ppc, x86,
637etc. On X86, we miss a bunch of 'rotate by variable' cases because the rotate
638matching code in dag combine doesn't look through truncates aggressively
639enough. Here are some testcases reduces from GCC PR17886:
640
Chris Lattneraf8d3c62008-03-17 01:47:51 +0000641unsigned long long f5(unsigned long long x, unsigned long long y) {
642 return (x << 8) | ((y >> 48) & 0xffull);
643}
644unsigned long long f6(unsigned long long x, unsigned long long y, int z) {
645 switch(z) {
646 case 1:
647 return (x << 8) | ((y >> 48) & 0xffull);
648 case 2:
649 return (x << 16) | ((y >> 40) & 0xffffull);
650 case 3:
651 return (x << 24) | ((y >> 32) & 0xffffffull);
652 case 4:
653 return (x << 32) | ((y >> 24) & 0xffffffffull);
654 default:
655 return (x << 40) | ((y >> 16) & 0xffffffffffull);
656 }
657}
658
Chris Lattneraf8d3c62008-03-17 01:47:51 +0000659//===---------------------------------------------------------------------===//
Chris Lattnerfd5fe2a2008-03-20 04:46:13 +0000660
Chris Lattner27ecda12010-12-15 07:10:43 +0000661This (and similar related idioms):
662
663unsigned int foo(unsigned char i) {
664 return i | (i<<8) | (i<<16) | (i<<24);
665}
666
667compiles into:
668
669define i32 @foo(i8 zeroext %i) nounwind readnone ssp noredzone {
670entry:
671 %conv = zext i8 %i to i32
672 %shl = shl i32 %conv, 8
673 %shl5 = shl i32 %conv, 16
674 %shl9 = shl i32 %conv, 24
675 %or = or i32 %shl9, %conv
676 %or6 = or i32 %or, %shl5
677 %or10 = or i32 %or6, %shl
678 ret i32 %or10
679}
680
681it would be better as:
682
683unsigned int bar(unsigned char i) {
684 unsigned int j=i | (i << 8);
685 return j | (j<<16);
686}
687
688aka:
689
690define i32 @bar(i8 zeroext %i) nounwind readnone ssp noredzone {
691entry:
692 %conv = zext i8 %i to i32
693 %shl = shl i32 %conv, 8
694 %or = or i32 %shl, %conv
695 %shl5 = shl i32 %or, 16
696 %or6 = or i32 %shl5, %or
697 ret i32 %or6
698}
699
700or even i*0x01010101, depending on the speed of the multiplier. The best way to
701handle this is to canonicalize it to a multiply in IR and have codegen handle
702lowering multiplies to shifts on cpus where shifts are faster.
703
704//===---------------------------------------------------------------------===//
705
Chris Lattnerfd5fe2a2008-03-20 04:46:13 +0000706We do a number of simplifications in simplify libcalls to strength reduce
707standard library functions, but we don't currently merge them together. For
708example, it is useful to merge memcpy(a,b,strlen(b)) -> strcpy. This can only
709be done safely if "b" isn't modified between the strlen and memcpy of course.
710
711//===---------------------------------------------------------------------===//
712
Chris Lattner113b3362008-08-10 01:14:08 +0000713We compile this program: (from GCC PR11680)
714http://gcc.gnu.org/bugzilla/attachment.cgi?id=4487
715
716Into code that runs the same speed in fast/slow modes, but both modes run 2x
717slower than when compile with GCC (either 4.0 or 4.2):
718
719$ llvm-g++ perf.cpp -O3 -fno-exceptions
720$ time ./a.out fast
7211.821u 0.003s 0:01.82 100.0% 0+0k 0+0io 0pf+0w
722
723$ g++ perf.cpp -O3 -fno-exceptions
724$ time ./a.out fast
7250.821u 0.001s 0:00.82 100.0% 0+0k 0+0io 0pf+0w
726
727It looks like we are making the same inlining decisions, so this may be raw
728codegen badness or something else (haven't investigated).
729
730//===---------------------------------------------------------------------===//
731
Chris Lattner113b3362008-08-10 01:14:08 +0000732Divisibility by constant can be simplified (according to GCC PR12849) from
733being a mulhi to being a mul lo (cheaper). Testcase:
734
735void bar(unsigned n) {
736 if (n % 3 == 0)
737 true();
738}
739
Eli Friedman96cf7f42009-12-12 23:23:43 +0000740This is equivalent to the following, where 2863311531 is the multiplicative
741inverse of 3, and 1431655766 is ((2^32)-1)/3+1:
742void bar(unsigned n) {
743 if (n * 2863311531U < 1431655766U)
744 true();
745}
746
747The same transformation can work with an even modulo with the addition of a
748rotate: rotate the result of the multiply to the right by the number of bits
749which need to be zero for the condition to be true, and shrink the compare RHS
750by the same amount. Unless the target supports rotates, though, that
751transformation probably isn't worthwhile.
752
753The transformation can also easily be made to work with non-zero equality
754comparisons: just transform, for example, "n % 3 == 1" to "(n-1) % 3 == 0".
Chris Lattner113b3362008-08-10 01:14:08 +0000755
756//===---------------------------------------------------------------------===//
Chris Lattnerd7dd8b82008-08-19 06:22:16 +0000757
Chris Lattner6d275fd2008-10-15 16:06:03 +0000758Better mod/ref analysis for scanf would allow us to eliminate the vtable and a
759bunch of other stuff from this example (see PR1604):
760
761#include <cstdio>
762struct test {
763 int val;
764 virtual ~test() {}
765};
766
767int main() {
768 test t;
769 std::scanf("%d", &t.val);
770 std::printf("%d\n", t.val);
771}
772
773//===---------------------------------------------------------------------===//
774
Nick Lewyckyedd5d3e2008-11-27 22:41:45 +0000775These functions perform the same computation, but produce different assembly.
Nick Lewyckyb3dc4ad2008-11-27 22:12:22 +0000776
777define i8 @select(i8 %x) readnone nounwind {
778 %A = icmp ult i8 %x, 250
779 %B = select i1 %A, i8 0, i8 1
780 ret i8 %B
781}
782
783define i8 @addshr(i8 %x) readnone nounwind {
784 %A = zext i8 %x to i9
785 %B = add i9 %A, 6 ;; 256 - 250 == 6
786 %C = lshr i9 %B, 8
787 %D = trunc i9 %C to i8
788 ret i8 %D
789}
790
791//===---------------------------------------------------------------------===//
Eli Friedmane16c0ff2008-11-30 07:36:04 +0000792
793From gcc bug 24696:
794int
795f (unsigned long a, unsigned long b, unsigned long c)
796{
797 return ((a & (c - 1)) != 0) || ((b & (c - 1)) != 0);
798}
799int
800f (unsigned long a, unsigned long b, unsigned long c)
801{
802 return ((a & (c - 1)) != 0) | ((b & (c - 1)) != 0);
803}
804Both should combine to ((a|b) & (c-1)) != 0. Currently not optimized with
805"clang -emit-llvm-bc | opt -std-compile-opts".
806
807//===---------------------------------------------------------------------===//
808
809From GCC Bug 20192:
810#define PMD_MASK (~((1UL << 23) - 1))
811void clear_pmd_range(unsigned long start, unsigned long end)
812{
813 if (!(start & ~PMD_MASK) && !(end & ~PMD_MASK))
814 f();
815}
816The expression should optimize to something like
817"!((start|end)&~PMD_MASK). Currently not optimized with "clang
818-emit-llvm-bc | opt -std-compile-opts".
819
820//===---------------------------------------------------------------------===//
821
Eli Friedmane16c0ff2008-11-30 07:36:04 +0000822unsigned int f(unsigned int i, unsigned int n) {++i; if (i == n) ++i; return
823i;}
824unsigned int f2(unsigned int i, unsigned int n) {++i; i += i == n; return i;}
825These should combine to the same thing. Currently, the first function
826produces better code on X86.
827
828//===---------------------------------------------------------------------===//
829
Eli Friedmane16c0ff2008-11-30 07:36:04 +0000830From GCC Bug 15784:
831#define abs(x) x>0?x:-x
832int f(int x, int y)
833{
834 return (abs(x)) >= 0;
835}
836This should optimize to x == INT_MIN. (With -fwrapv.) Currently not
837optimized with "clang -emit-llvm-bc | opt -std-compile-opts".
838
839//===---------------------------------------------------------------------===//
840
841From GCC Bug 14753:
842void
843rotate_cst (unsigned int a)
844{
845 a = (a << 10) | (a >> 22);
846 if (a == 123)
847 bar ();
848}
849void
850minus_cst (unsigned int a)
851{
852 unsigned int tem;
853
854 tem = 20 - a;
855 if (tem == 5)
856 bar ();
857}
858void
859mask_gt (unsigned int a)
860{
861 /* This is equivalent to a > 15. */
862 if ((a & ~7) > 8)
863 bar ();
864}
865void
866rshift_gt (unsigned int a)
867{
868 /* This is equivalent to a > 23. */
869 if ((a >> 2) > 5)
870 bar ();
871}
Chris Lattner727eebe2011-02-17 01:43:46 +0000872
873void neg_eq_cst(unsigned int a) {
874if (-a == 123)
875bar();
876}
877
Eli Friedmane16c0ff2008-11-30 07:36:04 +0000878All should simplify to a single comparison. All of these are
879currently not optimized with "clang -emit-llvm-bc | opt
880-std-compile-opts".
881
882//===---------------------------------------------------------------------===//
883
884From GCC Bug 32605:
885int c(int* x) {return (char*)x+2 == (char*)x;}
886Should combine to 0. Currently not optimized with "clang
887-emit-llvm-bc | opt -std-compile-opts" (although llc can optimize it).
888
889//===---------------------------------------------------------------------===//
890
Eli Friedmane16c0ff2008-11-30 07:36:04 +0000891int a(unsigned b) {return ((b << 31) | (b << 30)) >> 31;}
892Should be combined to "((b >> 1) | b) & 1". Currently not optimized
893with "clang -emit-llvm-bc | opt -std-compile-opts".
894
895//===---------------------------------------------------------------------===//
896
897unsigned a(unsigned x, unsigned y) { return x | (y & 1) | (y & 2);}
898Should combine to "x | (y & 3)". Currently not optimized with "clang
899-emit-llvm-bc | opt -std-compile-opts".
900
901//===---------------------------------------------------------------------===//
902
Eli Friedmane16c0ff2008-11-30 07:36:04 +0000903int a(int a, int b, int c) {return (~a & c) | ((c|a) & b);}
904Should fold to "(~a & c) | (a & b)". Currently not optimized with
905"clang -emit-llvm-bc | opt -std-compile-opts".
906
907//===---------------------------------------------------------------------===//
908
909int a(int a,int b) {return (~(a|b))|a;}
910Should fold to "a|~b". Currently not optimized with "clang
911-emit-llvm-bc | opt -std-compile-opts".
912
913//===---------------------------------------------------------------------===//
914
915int a(int a, int b) {return (a&&b) || (a&&!b);}
916Should fold to "a". Currently not optimized with "clang -emit-llvm-bc
917| opt -std-compile-opts".
918
919//===---------------------------------------------------------------------===//
920
921int a(int a, int b, int c) {return (a&&b) || (!a&&c);}
922Should fold to "a ? b : c", or at least something sane. Currently not
923optimized with "clang -emit-llvm-bc | opt -std-compile-opts".
924
925//===---------------------------------------------------------------------===//
926
927int a(int a, int b, int c) {return (a&&b) || (a&&c) || (a&&b&&c);}
928Should fold to a && (b || c). Currently not optimized with "clang
929-emit-llvm-bc | opt -std-compile-opts".
930
931//===---------------------------------------------------------------------===//
932
933int a(int x) {return x | ((x & 8) ^ 8);}
934Should combine to x | 8. Currently not optimized with "clang
935-emit-llvm-bc | opt -std-compile-opts".
936
937//===---------------------------------------------------------------------===//
938
939int a(int x) {return x ^ ((x & 8) ^ 8);}
940Should also combine to x | 8. Currently not optimized with "clang
941-emit-llvm-bc | opt -std-compile-opts".
942
943//===---------------------------------------------------------------------===//
944
Eli Friedmane16c0ff2008-11-30 07:36:04 +0000945int a(int x) {return ((x | -9) ^ 8) & x;}
946Should combine to x & -9. Currently not optimized with "clang
947-emit-llvm-bc | opt -std-compile-opts".
948
949//===---------------------------------------------------------------------===//
950
951unsigned a(unsigned a) {return a * 0x11111111 >> 28 & 1;}
952Should combine to "a * 0x88888888 >> 31". Currently not optimized
953with "clang -emit-llvm-bc | opt -std-compile-opts".
954
955//===---------------------------------------------------------------------===//
956
957unsigned a(char* x) {if ((*x & 32) == 0) return b();}
958There's an unnecessary zext in the generated code with "clang
959-emit-llvm-bc | opt -std-compile-opts".
960
961//===---------------------------------------------------------------------===//
962
963unsigned a(unsigned long long x) {return 40 * (x >> 1);}
964Should combine to "20 * (((unsigned)x) & -2)". Currently not
965optimized with "clang -emit-llvm-bc | opt -std-compile-opts".
966
967//===---------------------------------------------------------------------===//
Bill Wendling85de4b32008-12-02 05:12:47 +0000968
Chris Lattner0cdc0bb2008-12-02 06:32:34 +0000969This was noticed in the entryblock for grokdeclarator in 403.gcc:
970
971 %tmp = icmp eq i32 %decl_context, 4
972 %decl_context_addr.0 = select i1 %tmp, i32 3, i32 %decl_context
973 %tmp1 = icmp eq i32 %decl_context_addr.0, 1
974 %decl_context_addr.1 = select i1 %tmp1, i32 0, i32 %decl_context_addr.0
975
976tmp1 should be simplified to something like:
977 (!tmp || decl_context == 1)
978
979This allows recursive simplifications, tmp1 is used all over the place in
980the function, e.g. by:
981
982 %tmp23 = icmp eq i32 %decl_context_addr.1, 0 ; <i1> [#uses=1]
983 %tmp24 = xor i1 %tmp1, true ; <i1> [#uses=1]
984 %or.cond8 = and i1 %tmp23, %tmp24 ; <i1> [#uses=1]
985
986later.
987
Chris Lattner543d6c62008-12-06 19:28:22 +0000988//===---------------------------------------------------------------------===//
989
Chris Lattner58ccf882009-11-29 02:19:52 +0000990[STORE SINKING]
991
Chris Lattner543d6c62008-12-06 19:28:22 +0000992Store sinking: This code:
993
994void f (int n, int *cond, int *res) {
995 int i;
996 *res = 0;
997 for (i = 0; i < n; i++)
998 if (*cond)
999 *res ^= 234; /* (*) */
1000}
1001
1002On this function GVN hoists the fully redundant value of *res, but nothing
1003moves the store out. This gives us this code:
1004
1005bb: ; preds = %bb2, %entry
1006 %.rle = phi i32 [ 0, %entry ], [ %.rle6, %bb2 ]
1007 %i.05 = phi i32 [ 0, %entry ], [ %indvar.next, %bb2 ]
1008 %1 = load i32* %cond, align 4
1009 %2 = icmp eq i32 %1, 0
1010 br i1 %2, label %bb2, label %bb1
1011
1012bb1: ; preds = %bb
1013 %3 = xor i32 %.rle, 234
1014 store i32 %3, i32* %res, align 4
1015 br label %bb2
1016
1017bb2: ; preds = %bb, %bb1
1018 %.rle6 = phi i32 [ %3, %bb1 ], [ %.rle, %bb ]
1019 %indvar.next = add i32 %i.05, 1
1020 %exitcond = icmp eq i32 %indvar.next, %n
1021 br i1 %exitcond, label %return, label %bb
1022
1023DSE should sink partially dead stores to get the store out of the loop.
1024
Chris Lattnerda930632008-12-06 22:52:12 +00001025Here's another partial dead case:
1026http://gcc.gnu.org/bugzilla/show_bug.cgi?id=12395
1027
Chris Lattner543d6c62008-12-06 19:28:22 +00001028//===---------------------------------------------------------------------===//
1029
1030Scalar PRE hoists the mul in the common block up to the else:
1031
1032int test (int a, int b, int c, int g) {
1033 int d, e;
1034 if (a)
1035 d = b * c;
1036 else
1037 d = b - c;
1038 e = b * c + g;
1039 return d + e;
1040}
1041
1042It would be better to do the mul once to reduce codesize above the if.
1043This is GCC PR38204.
1044
Chris Lattner245de782011-01-06 07:41:22 +00001045
1046//===---------------------------------------------------------------------===//
1047This simple function from 179.art:
1048
1049int winner, numf2s;
1050struct { double y; int reset; } *Y;
1051
1052void find_match() {
1053 int i;
1054 winner = 0;
1055 for (i=0;i<numf2s;i++)
1056 if (Y[i].y > Y[winner].y)
1057 winner =i;
1058}
1059
1060Compiles into (with clang TBAA):
1061
1062for.body: ; preds = %for.inc, %bb.nph
1063 %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %for.inc ]
1064 %i.01718 = phi i32 [ 0, %bb.nph ], [ %i.01719, %for.inc ]
1065 %tmp4 = getelementptr inbounds %struct.anon* %tmp3, i64 %indvar, i32 0
1066 %tmp5 = load double* %tmp4, align 8, !tbaa !4
1067 %idxprom7 = sext i32 %i.01718 to i64
1068 %tmp10 = getelementptr inbounds %struct.anon* %tmp3, i64 %idxprom7, i32 0
1069 %tmp11 = load double* %tmp10, align 8, !tbaa !4
1070 %cmp12 = fcmp ogt double %tmp5, %tmp11
1071 br i1 %cmp12, label %if.then, label %for.inc
1072
1073if.then: ; preds = %for.body
1074 %i.017 = trunc i64 %indvar to i32
1075 br label %for.inc
1076
1077for.inc: ; preds = %for.body, %if.then
1078 %i.01719 = phi i32 [ %i.01718, %for.body ], [ %i.017, %if.then ]
1079 %indvar.next = add i64 %indvar, 1
1080 %exitcond = icmp eq i64 %indvar.next, %tmp22
1081 br i1 %exitcond, label %for.cond.for.end_crit_edge, label %for.body
1082
1083
1084It is good that we hoisted the reloads of numf2's, and Y out of the loop and
1085sunk the store to winner out.
1086
1087However, this is awful on several levels: the conditional truncate in the loop
1088(-indvars at fault? why can't we completely promote the IV to i64?).
1089
1090Beyond that, we have a partially redundant load in the loop: if "winner" (aka
1091%i.01718) isn't updated, we reload Y[winner].y the next time through the loop.
1092Similarly, the addressing that feeds it (including the sext) is redundant. In
1093the end we get this generated assembly:
1094
1095LBB0_2: ## %for.body
1096 ## =>This Inner Loop Header: Depth=1
1097 movsd (%rdi), %xmm0
1098 movslq %edx, %r8
1099 shlq $4, %r8
1100 ucomisd (%rcx,%r8), %xmm0
1101 jbe LBB0_4
1102 movl %esi, %edx
1103LBB0_4: ## %for.inc
1104 addq $16, %rdi
1105 incq %rsi
1106 cmpq %rsi, %rax
1107 jne LBB0_2
1108
1109All things considered this isn't too bad, but we shouldn't need the movslq or
1110the shlq instruction, or the load folded into ucomisd every time through the
1111loop.
1112
1113On an x86-specific topic, if the loop can't be restructure, the movl should be a
1114cmov.
1115
Chris Lattner543d6c62008-12-06 19:28:22 +00001116//===---------------------------------------------------------------------===//
1117
Chris Lattner58ccf882009-11-29 02:19:52 +00001118[STORE SINKING]
1119
Chris Lattner543d6c62008-12-06 19:28:22 +00001120GCC PR37810 is an interesting case where we should sink load/store reload
1121into the if block and outside the loop, so we don't reload/store it on the
1122non-call path.
1123
1124for () {
1125 *P += 1;
1126 if ()
1127 call();
1128 else
1129 ...
1130->
1131tmp = *P
1132for () {
1133 tmp += 1;
1134 if () {
1135 *P = tmp;
1136 call();
1137 tmp = *P;
1138 } else ...
1139}
1140*P = tmp;
1141
Chris Lattner81ee7312008-12-15 07:49:24 +00001142We now hoist the reload after the call (Transforms/GVN/lpre-call-wrap.ll), but
1143we don't sink the store. We need partially dead store sinking.
1144
Chris Lattner543d6c62008-12-06 19:28:22 +00001145//===---------------------------------------------------------------------===//
1146
Chris Lattner58ccf882009-11-29 02:19:52 +00001147[LOAD PRE CRIT EDGE SPLITTING]
Chris Lattner81ee7312008-12-15 07:49:24 +00001148
Chris Lattner543d6c62008-12-06 19:28:22 +00001149GCC PR37166: Sinking of loads prevents SROA'ing the "g" struct on the stack
1150leading to excess stack traffic. This could be handled by GVN with some crazy
1151symbolic phi translation. The code we get looks like (g is on the stack):
1152
1153bb2: ; preds = %bb1
1154..
1155 %9 = getelementptr %struct.f* %g, i32 0, i32 0
1156 store i32 %8, i32* %9, align bel %bb3
1157
1158bb3: ; preds = %bb1, %bb2, %bb
1159 %c_addr.0 = phi %struct.f* [ %g, %bb2 ], [ %c, %bb ], [ %c, %bb1 ]
1160 %b_addr.0 = phi %struct.f* [ %b, %bb2 ], [ %g, %bb ], [ %b, %bb1 ]
1161 %10 = getelementptr %struct.f* %c_addr.0, i32 0, i32 0
1162 %11 = load i32* %10, align 4
1163
Chris Lattnerca9e0e82009-11-27 16:53:57 +00001164%11 is partially redundant, an in BB2 it should have the value %8.
Chris Lattner543d6c62008-12-06 19:28:22 +00001165
Chris Lattner58ccf882009-11-29 02:19:52 +00001166GCC PR33344 and PR35287 are similar cases.
Chris Lattnerda930632008-12-06 22:52:12 +00001167
Chris Lattner06c26d92009-11-05 18:19:19 +00001168
1169//===---------------------------------------------------------------------===//
1170
Chris Lattner58ccf882009-11-29 02:19:52 +00001171[LOAD PRE]
1172
Chris Lattnerda930632008-12-06 22:52:12 +00001173There are many load PRE testcases in testsuite/gcc.dg/tree-ssa/loadpre* in the
Chris Lattner58ccf882009-11-29 02:19:52 +00001174GCC testsuite, ones we don't get yet are (checked through loadpre25):
1175
1176[CRIT EDGE BREAKING]
1177loadpre3.c predcom-4.c
1178
1179[PRE OF READONLY CALL]
1180loadpre5.c
1181
1182[TURN SELECT INTO BRANCH]
1183loadpre14.c loadpre15.c
1184
1185actually a conditional increment: loadpre18.c loadpre19.c
1186
Chris Lattneraded09f2010-12-15 06:38:24 +00001187//===---------------------------------------------------------------------===//
1188
1189[LOAD PRE / STORE SINKING / SPEC HACK]
1190
1191This is a chunk of code from 456.hmmer:
1192
1193int f(int M, int *mc, int *mpp, int *tpmm, int *ip, int *tpim, int *dpp,
1194 int *tpdm, int xmb, int *bp, int *ms) {
1195 int k, sc;
1196 for (k = 1; k <= M; k++) {
1197 mc[k] = mpp[k-1] + tpmm[k-1];
1198 if ((sc = ip[k-1] + tpim[k-1]) > mc[k]) mc[k] = sc;
1199 if ((sc = dpp[k-1] + tpdm[k-1]) > mc[k]) mc[k] = sc;
1200 if ((sc = xmb + bp[k]) > mc[k]) mc[k] = sc;
1201 mc[k] += ms[k];
1202 }
1203}
1204
1205It is very profitable for this benchmark to turn the conditional stores to mc[k]
1206into a conditional move (select instr in IR) and allow the final store to do the
1207store. See GCC PR27313 for more details. Note that this is valid to xform even
1208with the new C++ memory model, since mc[k] is previously loaded and later
1209stored.
Chris Lattner58ccf882009-11-29 02:19:52 +00001210
1211//===---------------------------------------------------------------------===//
1212
1213[SCALAR PRE]
1214There are many PRE testcases in testsuite/gcc.dg/tree-ssa/ssa-pre-*.c in the
1215GCC testsuite.
Chris Lattnerda930632008-12-06 22:52:12 +00001216
Chris Lattner5d196e62008-12-15 08:32:28 +00001217//===---------------------------------------------------------------------===//
1218
1219There are some interesting cases in testsuite/gcc.dg/tree-ssa/pred-comm* in the
Chris Lattner58ccf882009-11-29 02:19:52 +00001220GCC testsuite. For example, we get the first example in predcom-1.c, but
1221miss the second one:
Chris Lattner5d196e62008-12-15 08:32:28 +00001222
Chris Lattner58ccf882009-11-29 02:19:52 +00001223unsigned fib[1000];
1224unsigned avg[1000];
Chris Lattner5d196e62008-12-15 08:32:28 +00001225
Chris Lattner58ccf882009-11-29 02:19:52 +00001226__attribute__ ((noinline))
1227void count_averages(int n) {
1228 int i;
1229 for (i = 1; i < n; i++)
1230 avg[i] = (((unsigned long) fib[i - 1] + fib[i] + fib[i + 1]) / 3) & 0xffff;
1231}
Chris Lattner5d196e62008-12-15 08:32:28 +00001232
Chris Lattner58ccf882009-11-29 02:19:52 +00001233which compiles into two loads instead of one in the loop.
Chris Lattner5d196e62008-12-15 08:32:28 +00001234
Chris Lattner58ccf882009-11-29 02:19:52 +00001235predcom-2.c is the same as predcom-1.c
Chris Lattner5d196e62008-12-15 08:32:28 +00001236
Chris Lattner5d196e62008-12-15 08:32:28 +00001237predcom-3.c is very similar but needs loads feeding each other instead of
1238store->load.
Chris Lattner5d196e62008-12-15 08:32:28 +00001239
1240
1241//===---------------------------------------------------------------------===//
1242
Chris Lattner082da532010-01-23 17:59:23 +00001243[ALIAS ANALYSIS]
1244
Chris Lattner5d196e62008-12-15 08:32:28 +00001245Type based alias analysis:
Chris Lattnerda930632008-12-06 22:52:12 +00001246http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14705
1247
Chris Lattner082da532010-01-23 17:59:23 +00001248We should do better analysis of posix_memalign. At the least it should
1249no-capture its pointer argument, at best, we should know that the out-value
1250result doesn't point to anything (like malloc). One example of this is in
1251SingleSource/Benchmarks/Misc/dt.c
1252
Chris Lattnerda930632008-12-06 22:52:12 +00001253//===---------------------------------------------------------------------===//
1254
Chris Lattnerda930632008-12-06 22:52:12 +00001255Interesting missed case because of control flow flattening (should be 2 loads):
1256http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26629
Chris Lattner5d196e62008-12-15 08:32:28 +00001257With: llvm-gcc t2.c -S -o - -O0 -emit-llvm | llvm-as |
1258 opt -mem2reg -gvn -instcombine | llvm-dis
Chris Lattner58ccf882009-11-29 02:19:52 +00001259we miss it because we need 1) CRIT EDGE 2) MULTIPLE DIFFERENT
Chris Lattner5d196e62008-12-15 08:32:28 +00001260VALS PRODUCED BY ONE BLOCK OVER DIFFERENT PATHS
Chris Lattnerda930632008-12-06 22:52:12 +00001261
1262//===---------------------------------------------------------------------===//
1263
1264http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19633
1265We could eliminate the branch condition here, loading from null is undefined:
1266
1267struct S { int w, x, y, z; };
1268struct T { int r; struct S s; };
1269void bar (struct S, int);
1270void foo (int a, struct T b)
1271{
1272 struct S *c = 0;
1273 if (a)
1274 c = &b.s;
1275 bar (*c, a);
1276}
1277
1278//===---------------------------------------------------------------------===//
Chris Lattner0cdc0bb2008-12-02 06:32:34 +00001279
Chris Lattner8a35adf2008-12-23 20:52:52 +00001280simplifylibcalls should do several optimizations for strspn/strcspn:
1281
Chris Lattner8a35adf2008-12-23 20:52:52 +00001282strcspn(x, "a") -> inlined loop for up to 3 letters (similarly for strspn):
1283
1284size_t __strcspn_c3 (__const char *__s, int __reject1, int __reject2,
1285 int __reject3) {
1286 register size_t __result = 0;
1287 while (__s[__result] != '\0' && __s[__result] != __reject1 &&
1288 __s[__result] != __reject2 && __s[__result] != __reject3)
1289 ++__result;
1290 return __result;
1291}
1292
1293This should turn into a switch on the character. See PR3253 for some notes on
1294codegen.
1295
1296456.hmmer apparently uses strcspn and strspn a lot. 471.omnetpp uses strspn.
1297
1298//===---------------------------------------------------------------------===//
Chris Lattnera4142252008-12-31 00:54:13 +00001299
Chris Lattner0c6cb462011-03-01 00:24:51 +00001300simplifylibcalls should turn these snprintf idioms into memcpy (GCC PR47917)
1301
1302char buf1[6], buf2[6], buf3[4], buf4[4];
1303int i;
1304
1305int foo (void) {
1306 int ret = snprintf (buf1, sizeof buf1, "abcde");
1307 ret += snprintf (buf2, sizeof buf2, "abcdef") * 16;
1308 ret += snprintf (buf3, sizeof buf3, "%s", i++ < 6 ? "abc" : "def") * 256;
1309 ret += snprintf (buf4, sizeof buf4, "%s", i++ > 10 ? "abcde" : "defgh")*4096;
1310 return ret;
1311}
1312
1313//===---------------------------------------------------------------------===//
1314
Chris Lattnera4142252008-12-31 00:54:13 +00001315"gas" uses this idiom:
1316 else if (strchr ("+-/*%|&^:[]()~", *intel_parser.op_string))
1317..
1318 else if (strchr ("<>", *intel_parser.op_string)
1319
1320Those should be turned into a switch.
1321
1322//===---------------------------------------------------------------------===//
Chris Lattner7cb3ae02009-01-08 06:52:57 +00001323
1324252.eon contains this interesting code:
1325
1326 %3072 = getelementptr [100 x i8]* %tempString, i32 0, i32 0
1327 %3073 = call i8* @strcpy(i8* %3072, i8* %3071) nounwind
1328 %strlen = call i32 @strlen(i8* %3072) ; uses = 1
1329 %endptr = getelementptr [100 x i8]* %tempString, i32 0, i32 %strlen
1330 call void @llvm.memcpy.i32(i8* %endptr,
1331 i8* getelementptr ([5 x i8]* @"\01LC42", i32 0, i32 0), i32 5, i32 1)
1332 %3074 = call i32 @strlen(i8* %endptr) nounwind readonly
1333
1334This is interesting for a couple reasons. First, in this:
1335
Benjamin Kramerdfa40f82010-12-23 15:32:07 +00001336The memcpy+strlen strlen can be replaced with:
Chris Lattner7cb3ae02009-01-08 06:52:57 +00001337
1338 %3074 = call i32 @strlen([5 x i8]* @"\01LC42") nounwind readonly
1339
1340Because the destination was just copied into the specified memory buffer. This,
1341in turn, can be constant folded to "4".
1342
1343In other code, it contains:
1344
1345 %endptr6978 = bitcast i8* %endptr69 to i32*
1346 store i32 7107374, i32* %endptr6978, align 1
1347 %3167 = call i32 @strlen(i8* %endptr69) nounwind readonly
1348
1349Which could also be constant folded. Whatever is producing this should probably
1350be fixed to leave this as a memcpy from a string.
1351
1352Further, eon also has an interesting partially redundant strlen call:
1353
1354bb8: ; preds = %_ZN18eonImageCalculatorC1Ev.exit
1355 %682 = getelementptr i8** %argv, i32 6 ; <i8**> [#uses=2]
1356 %683 = load i8** %682, align 4 ; <i8*> [#uses=4]
1357 %684 = load i8* %683, align 1 ; <i8> [#uses=1]
1358 %685 = icmp eq i8 %684, 0 ; <i1> [#uses=1]
1359 br i1 %685, label %bb10, label %bb9
1360
1361bb9: ; preds = %bb8
1362 %686 = call i32 @strlen(i8* %683) nounwind readonly
1363 %687 = icmp ugt i32 %686, 254 ; <i1> [#uses=1]
1364 br i1 %687, label %bb10, label %bb11
1365
1366bb10: ; preds = %bb9, %bb8
1367 %688 = call i32 @strlen(i8* %683) nounwind readonly
1368
1369This could be eliminated by doing the strlen once in bb8, saving code size and
1370improving perf on the bb8->9->10 path.
1371
1372//===---------------------------------------------------------------------===//
Chris Lattner6c2ee502009-01-08 07:34:55 +00001373
1374I see an interesting fully redundant call to strlen left in 186.crafty:InputMove
1375which looks like:
1376 %movetext11 = getelementptr [128 x i8]* %movetext, i32 0, i32 0
1377
1378
1379bb62: ; preds = %bb55, %bb53
1380 %promote.0 = phi i32 [ %169, %bb55 ], [ 0, %bb53 ]
1381 %171 = call i32 @strlen(i8* %movetext11) nounwind readonly align 1
1382 %172 = add i32 %171, -1 ; <i32> [#uses=1]
1383 %173 = getelementptr [128 x i8]* %movetext, i32 0, i32 %172
1384
1385... no stores ...
1386 br i1 %or.cond, label %bb65, label %bb72
1387
1388bb65: ; preds = %bb62
1389 store i8 0, i8* %173, align 1
1390 br label %bb72
1391
1392bb72: ; preds = %bb65, %bb62
1393 %trank.1 = phi i32 [ %176, %bb65 ], [ -1, %bb62 ]
1394 %177 = call i32 @strlen(i8* %movetext11) nounwind readonly align 1
1395
1396Note that on the bb62->bb72 path, that the %177 strlen call is partially
1397redundant with the %171 call. At worst, we could shove the %177 strlen call
1398up into the bb65 block moving it out of the bb62->bb72 path. However, note
1399that bb65 stores to the string, zeroing out the last byte. This means that on
1400that path the value of %177 is actually just %171-1. A sub is cheaper than a
1401strlen!
1402
1403This pattern repeats several times, basically doing:
1404
1405 A = strlen(P);
1406 P[A-1] = 0;
1407 B = strlen(P);
1408 where it is "obvious" that B = A-1.
1409
1410//===---------------------------------------------------------------------===//
1411
Chris Lattner6c2ee502009-01-08 07:34:55 +00001412186.crafty has this interesting pattern with the "out.4543" variable:
1413
1414call void @llvm.memcpy.i32(
1415 i8* getelementptr ([10 x i8]* @out.4543, i32 0, i32 0),
1416 i8* getelementptr ([7 x i8]* @"\01LC28700", i32 0, i32 0), i32 7, i32 1)
1417%101 = call@printf(i8* ... @out.4543, i32 0, i32 0)) nounwind
1418
1419It is basically doing:
1420
1421 memcpy(globalarray, "string");
1422 printf(..., globalarray);
1423
1424Anyway, by knowing that printf just reads the memory and forward substituting
1425the string directly into the printf, this eliminates reads from globalarray.
1426Since this pattern occurs frequently in crafty (due to the "DisplayTime" and
1427other similar functions) there are many stores to "out". Once all the printfs
1428stop using "out", all that is left is the memcpy's into it. This should allow
1429globalopt to remove the "stored only" global.
1430
1431//===---------------------------------------------------------------------===//
1432
Dan Gohman83d2e062009-01-20 01:07:33 +00001433This code:
1434
1435define inreg i32 @foo(i8* inreg %p) nounwind {
1436 %tmp0 = load i8* %p
1437 %tmp1 = ashr i8 %tmp0, 5
1438 %tmp2 = sext i8 %tmp1 to i32
1439 ret i32 %tmp2
1440}
1441
1442could be dagcombine'd to a sign-extending load with a shift.
1443For example, on x86 this currently gets this:
1444
1445 movb (%eax), %al
1446 sarb $5, %al
1447 movsbl %al, %eax
1448
1449while it could get this:
1450
1451 movsbl (%eax), %eax
1452 sarl $5, %eax
1453
1454//===---------------------------------------------------------------------===//
Chris Lattner705ac702009-01-22 07:16:03 +00001455
1456GCC PR31029:
1457
1458int test(int x) { return 1-x == x; } // --> return false
1459int test2(int x) { return 2-x == x; } // --> return x == 1 ?
1460
1461Always foldable for odd constants, what is the rule for even?
1462
1463//===---------------------------------------------------------------------===//
1464
Torok Edwin3cedd4d2009-01-24 19:30:25 +00001465PR 3381: GEP to field of size 0 inside a struct could be turned into GEP
1466for next field in struct (which is at same address).
1467
1468For example: store of float into { {{}}, float } could be turned into a store to
1469the float directly.
1470
Torok Edwin87d5ca02009-02-20 18:42:06 +00001471//===---------------------------------------------------------------------===//
Nick Lewycky5c10a3a2009-02-25 06:52:48 +00001472
Chris Lattner17a999e2009-05-11 17:41:40 +00001473The arg promotion pass should make use of nocapture to make its alias analysis
1474stuff much more precise.
1475
1476//===---------------------------------------------------------------------===//
1477
1478The following functions should be optimized to use a select instead of a
1479branch (from gcc PR40072):
1480
1481char char_int(int m) {if(m>7) return 0; return m;}
1482int int_char(char m) {if(m>7) return 0; return m;}
1483
1484//===---------------------------------------------------------------------===//
1485
Bill Wendlingfd2730e2009-10-27 22:48:31 +00001486int func(int a, int b) { if (a & 0x80) b |= 0x80; else b &= ~0x80; return b; }
1487
1488Generates this:
1489
1490define i32 @func(i32 %a, i32 %b) nounwind readnone ssp {
1491entry:
1492 %0 = and i32 %a, 128 ; <i32> [#uses=1]
1493 %1 = icmp eq i32 %0, 0 ; <i1> [#uses=1]
1494 %2 = or i32 %b, 128 ; <i32> [#uses=1]
1495 %3 = and i32 %b, -129 ; <i32> [#uses=1]
1496 %b_addr.0 = select i1 %1, i32 %3, i32 %2 ; <i32> [#uses=1]
1497 ret i32 %b_addr.0
1498}
1499
1500However, it's functionally equivalent to:
1501
1502 b = (b & ~0x80) | (a & 0x80);
1503
1504Which generates this:
1505
1506define i32 @func(i32 %a, i32 %b) nounwind readnone ssp {
1507entry:
1508 %0 = and i32 %b, -129 ; <i32> [#uses=1]
1509 %1 = and i32 %a, 128 ; <i32> [#uses=1]
1510 %2 = or i32 %0, %1 ; <i32> [#uses=1]
1511 ret i32 %2
1512}
1513
1514This can be generalized for other forms:
1515
1516 b = (b & ~0x80) | (a & 0x40) << 1;
1517
1518//===---------------------------------------------------------------------===//
Bill Wendling2e5198f2009-10-27 23:30:07 +00001519
1520These two functions produce different code. They shouldn't:
1521
1522#include <stdint.h>
1523
1524uint8_t p1(uint8_t b, uint8_t a) {
1525 b = (b & ~0xc0) | (a & 0xc0);
1526 return (b);
1527}
1528
1529uint8_t p2(uint8_t b, uint8_t a) {
1530 b = (b & ~0x40) | (a & 0x40);
1531 b = (b & ~0x80) | (a & 0x80);
1532 return (b);
1533}
1534
1535define zeroext i8 @p1(i8 zeroext %b, i8 zeroext %a) nounwind readnone ssp {
1536entry:
1537 %0 = and i8 %b, 63 ; <i8> [#uses=1]
1538 %1 = and i8 %a, -64 ; <i8> [#uses=1]
1539 %2 = or i8 %1, %0 ; <i8> [#uses=1]
1540 ret i8 %2
1541}
1542
1543define zeroext i8 @p2(i8 zeroext %b, i8 zeroext %a) nounwind readnone ssp {
1544entry:
1545 %0 = and i8 %b, 63 ; <i8> [#uses=1]
1546 %.masked = and i8 %a, 64 ; <i8> [#uses=1]
1547 %1 = and i8 %a, -128 ; <i8> [#uses=1]
1548 %2 = or i8 %1, %0 ; <i8> [#uses=1]
1549 %3 = or i8 %2, %.masked ; <i8> [#uses=1]
1550 ret i8 %3
1551}
1552
1553//===---------------------------------------------------------------------===//
Chris Lattner539bdf02009-11-11 17:51:27 +00001554
1555IPSCCP does not currently propagate argument dependent constants through
1556functions where it does not not all of the callers. This includes functions
1557with normal external linkage as well as templates, C99 inline functions etc.
1558Specifically, it does nothing to:
1559
1560define i32 @test(i32 %x, i32 %y, i32 %z) nounwind {
1561entry:
1562 %0 = add nsw i32 %y, %z
1563 %1 = mul i32 %0, %x
1564 %2 = mul i32 %y, %z
1565 %3 = add nsw i32 %1, %2
1566 ret i32 %3
1567}
1568
1569define i32 @test2() nounwind {
1570entry:
1571 %0 = call i32 @test(i32 1, i32 2, i32 4) nounwind
1572 ret i32 %0
1573}
1574
1575It would be interesting extend IPSCCP to be able to handle simple cases like
1576this, where all of the arguments to a call are constant. Because IPSCCP runs
1577before inlining, trivial templates and inline functions are not yet inlined.
1578The results for a function + set of constant arguments should be memoized in a
1579map.
1580
1581//===---------------------------------------------------------------------===//
Chris Lattner7a099642009-11-11 17:54:02 +00001582
1583The libcall constant folding stuff should be moved out of SimplifyLibcalls into
1584libanalysis' constantfolding logic. This would allow IPSCCP to be able to
1585handle simple things like this:
1586
1587static int foo(const char *X) { return strlen(X); }
1588int bar() { return foo("abcd"); }
1589
1590//===---------------------------------------------------------------------===//
Nick Lewyckyef4ea9a2009-11-15 17:51:23 +00001591
Duncan Sandsc8493da2010-01-06 15:37:47 +00001592functionattrs doesn't know much about memcpy/memset. This function should be
Duncan Sands78376ad2010-01-06 08:45:52 +00001593marked readnone rather than readonly, since it only twiddles local memory, but
1594functionattrs doesn't handle memset/memcpy/memmove aggressively:
Chris Lattnerf05330a2009-12-03 07:43:46 +00001595
1596struct X { int *p; int *q; };
1597int foo() {
1598 int i = 0, j = 1;
1599 struct X x, y;
1600 int **p;
1601 y.p = &i;
1602 x.q = &j;
1603 p = __builtin_memcpy (&x, &y, sizeof (int *));
1604 return **p;
1605}
1606
Chris Lattnere5d5a412011-01-01 22:52:11 +00001607This can be seen at:
1608$ clang t.c -S -o - -mkernel -O0 -emit-llvm | opt -functionattrs -S
1609
1610
Chris Lattnerd1e4ee32009-12-03 07:41:54 +00001611//===---------------------------------------------------------------------===//
1612
Eli Friedman9ed49c52010-01-18 22:36:59 +00001613Missed instcombine transformation:
1614define i1 @a(i32 %x) nounwind readnone {
1615entry:
1616 %cmp = icmp eq i32 %x, 30
1617 %sub = add i32 %x, -30
1618 %cmp2 = icmp ugt i32 %sub, 9
1619 %or = or i1 %cmp, %cmp2
1620 ret i1 %or
1621}
1622This should be optimized to a single compare. Testcase derived from gcc.
1623
1624//===---------------------------------------------------------------------===//
1625
Eli Friedman9ed49c52010-01-18 22:36:59 +00001626Missed instcombine or reassociate transformation:
1627int a(int a, int b) { return (a==12)&(b>47)&(b<58); }
1628
1629The sgt and slt should be combined into a single comparison. Testcase derived
1630from gcc.
1631
1632//===---------------------------------------------------------------------===//
1633
1634Missed instcombine transformation:
Chris Lattner9165d9d2010-11-21 07:05:31 +00001635
1636 %382 = srem i32 %tmp14.i, 64 ; [#uses=1]
1637 %383 = zext i32 %382 to i64 ; [#uses=1]
1638 %384 = shl i64 %381, %383 ; [#uses=1]
1639 %385 = icmp slt i32 %tmp14.i, 64 ; [#uses=1]
1640
Benjamin Kramer94a622a2010-11-23 20:33:57 +00001641The srem can be transformed to an and because if %tmp14.i is negative, the
1642shift is undefined. Testcase derived from 403.gcc.
Chris Lattner9165d9d2010-11-21 07:05:31 +00001643
1644//===---------------------------------------------------------------------===//
1645
1646This is a range comparison on a divided result (from 403.gcc):
1647
1648 %1337 = sdiv i32 %1336, 8 ; [#uses=1]
1649 %.off.i208 = add i32 %1336, 7 ; [#uses=1]
1650 %1338 = icmp ult i32 %.off.i208, 15 ; [#uses=1]
1651
1652We already catch this (removing the sdiv) if there isn't an add, we should
1653handle the 'add' as well. This is a common idiom with it's builtin_alloca code.
1654C testcase:
1655
1656int a(int x) { return (unsigned)(x/16+7) < 15; }
1657
1658Another similar case involves truncations on 64-bit targets:
1659
1660 %361 = sdiv i64 %.046, 8 ; [#uses=1]
1661 %362 = trunc i64 %361 to i32 ; [#uses=2]
1662...
1663 %367 = icmp eq i32 %362, 0 ; [#uses=1]
1664
Eli Friedman0de0b362010-01-31 04:55:32 +00001665//===---------------------------------------------------------------------===//
1666
1667Missed instcombine/dagcombine transformation:
1668define void @lshift_lt(i8 zeroext %a) nounwind {
1669entry:
1670 %conv = zext i8 %a to i32
1671 %shl = shl i32 %conv, 3
1672 %cmp = icmp ult i32 %shl, 33
1673 br i1 %cmp, label %if.then, label %if.end
1674
1675if.then:
1676 tail call void @bar() nounwind
1677 ret void
1678
1679if.end:
1680 ret void
1681}
1682declare void @bar() nounwind
1683
1684The shift should be eliminated. Testcase derived from gcc.
Eli Friedman9ed49c52010-01-18 22:36:59 +00001685
1686//===---------------------------------------------------------------------===//
Chris Lattner187242b2010-02-09 00:11:10 +00001687
1688These compile into different code, one gets recognized as a switch and the
1689other doesn't due to phase ordering issues (PR6212):
1690
1691int test1(int mainType, int subType) {
1692 if (mainType == 7)
1693 subType = 4;
1694 else if (mainType == 9)
1695 subType = 6;
1696 else if (mainType == 11)
1697 subType = 9;
1698 return subType;
1699}
1700
1701int test2(int mainType, int subType) {
1702 if (mainType == 7)
1703 subType = 4;
1704 if (mainType == 9)
1705 subType = 6;
1706 if (mainType == 11)
1707 subType = 9;
1708 return subType;
1709}
1710
1711//===---------------------------------------------------------------------===//
Chris Lattner1f6689a2010-03-10 21:42:42 +00001712
1713The following test case (from PR6576):
1714
1715define i32 @mul(i32 %a, i32 %b) nounwind readnone {
1716entry:
1717 %cond1 = icmp eq i32 %b, 0 ; <i1> [#uses=1]
1718 br i1 %cond1, label %exit, label %bb.nph
1719bb.nph: ; preds = %entry
1720 %tmp = mul i32 %b, %a ; <i32> [#uses=1]
1721 ret i32 %tmp
1722exit: ; preds = %entry
1723 ret i32 0
1724}
1725
1726could be reduced to:
1727
1728define i32 @mul(i32 %a, i32 %b) nounwind readnone {
1729entry:
1730 %tmp = mul i32 %b, %a
1731 ret i32 %tmp
1732}
1733
1734//===---------------------------------------------------------------------===//
1735
Chris Lattnercfc921c2010-04-16 23:52:30 +00001736We should use DSE + llvm.lifetime.end to delete dead vtable pointer updates.
1737See GCC PR34949
1738
Chris Lattner4dc833c2010-05-21 23:16:21 +00001739Another interesting case is that something related could be used for variables
1740that go const after their ctor has finished. In these cases, globalopt (which
1741can statically run the constructor) could mark the global const (so it gets put
1742in the readonly section). A testcase would be:
1743
1744#include <complex>
1745using namespace std;
1746const complex<char> should_be_in_rodata (42,-42);
1747complex<char> should_be_in_data (42,-42);
1748complex<char> should_be_in_bss;
1749
1750Where we currently evaluate the ctors but the globals don't become const because
1751the optimizer doesn't know they "become const" after the ctor is done. See
1752GCC PR4131 for more examples.
1753
Chris Lattnercfc921c2010-04-16 23:52:30 +00001754//===---------------------------------------------------------------------===//
1755
Dan Gohman73c81452010-05-03 14:31:00 +00001756In this code:
1757
1758long foo(long x) {
1759 return x > 1 ? x : 1;
1760}
1761
1762LLVM emits a comparison with 1 instead of 0. 0 would be equivalent
1763and cheaper on most targets.
1764
1765LLVM prefers comparisons with zero over non-zero in general, but in this
1766case it choses instead to keep the max operation obvious.
1767
1768//===---------------------------------------------------------------------===//
Eli Friedmane17e4ae2010-06-12 05:54:27 +00001769
Eli Friedman836fdbc2010-07-03 07:38:12 +00001770Switch lowering generates less than ideal code for the following switch:
1771define void @a(i32 %x) nounwind {
1772entry:
1773 switch i32 %x, label %if.end [
1774 i32 0, label %if.then
1775 i32 1, label %if.then
1776 i32 2, label %if.then
1777 i32 3, label %if.then
1778 i32 5, label %if.then
1779 ]
1780if.then:
1781 tail call void @foo() nounwind
1782 ret void
1783if.end:
1784 ret void
1785}
1786declare void @foo()
1787
1788Generated code on x86-64 (other platforms give similar results):
1789a:
1790 cmpl $5, %edi
1791 ja .LBB0_2
1792 movl %edi, %eax
1793 movl $47, %ecx
1794 btq %rax, %rcx
1795 jb .LBB0_3
1796.LBB0_2:
1797 ret
1798.LBB0_3:
Eli Friedmanc8f59522010-07-03 08:43:32 +00001799 jmp foo # TAILCALL
Eli Friedman836fdbc2010-07-03 07:38:12 +00001800
1801The movl+movl+btq+jb could be simplified to a cmpl+jne.
1802
Eli Friedmanc8f59522010-07-03 08:43:32 +00001803Or, if we wanted to be really clever, we could simplify the whole thing to
1804something like the following, which eliminates a branch:
1805 xorl $1, %edi
1806 cmpl $4, %edi
1807 ja .LBB0_2
1808 ret
1809.LBB0_2:
1810 jmp foo # TAILCALL
1811
Eli Friedman836fdbc2010-07-03 07:38:12 +00001812//===---------------------------------------------------------------------===//
Chris Lattner4d94e472010-11-09 19:37:28 +00001813
Chris Lattner932aab32010-11-11 18:23:57 +00001814We compile this:
1815
1816int foo(int a) { return (a & (~15)) / 16; }
1817
1818Into:
1819
1820define i32 @foo(i32 %a) nounwind readnone ssp {
1821entry:
1822 %and = and i32 %a, -16
1823 %div = sdiv i32 %and, 16
1824 ret i32 %div
1825}
1826
1827but this code (X & -A)/A is X >> log2(A) when A is a power of 2, so this case
1828should be instcombined into just "a >> 4".
1829
1830We do get this at the codegen level, so something knows about it, but
1831instcombine should catch it earlier:
1832
1833_foo: ## @foo
1834## BB#0: ## %entry
1835 movl %edi, %eax
1836 sarl $4, %eax
1837 ret
1838
1839//===---------------------------------------------------------------------===//
1840
Chris Lattner14cb11d2010-12-13 00:15:25 +00001841This code (from GCC PR28685):
1842
1843int test(int a, int b) {
1844 int lt = a < b;
1845 int eq = a == b;
1846 if (lt)
1847 return 1;
1848 return eq;
1849}
1850
1851Is compiled to:
1852
1853define i32 @test(i32 %a, i32 %b) nounwind readnone ssp {
1854entry:
1855 %cmp = icmp slt i32 %a, %b
1856 br i1 %cmp, label %return, label %if.end
1857
1858if.end: ; preds = %entry
1859 %cmp5 = icmp eq i32 %a, %b
1860 %conv6 = zext i1 %cmp5 to i32
1861 ret i32 %conv6
1862
1863return: ; preds = %entry
1864 ret i32 1
1865}
1866
1867it could be:
1868
1869define i32 @test__(i32 %a, i32 %b) nounwind readnone ssp {
1870entry:
1871 %0 = icmp sle i32 %a, %b
1872 %retval = zext i1 %0 to i32
1873 ret i32 %retval
1874}
1875
1876//===---------------------------------------------------------------------===//
Duncan Sands772749a2011-01-01 20:08:02 +00001877
Benjamin Kramer134cde92011-01-07 20:42:20 +00001878This code can be seen in viterbi:
1879
1880 %64 = call noalias i8* @malloc(i64 %62) nounwind
1881...
1882 %67 = call i64 @llvm.objectsize.i64(i8* %64, i1 false) nounwind
1883 %68 = call i8* @__memset_chk(i8* %64, i32 0, i64 %62, i64 %67) nounwind
1884
1885llvm.objectsize.i64 should be taught about malloc/calloc, allowing it to
1886fold to %62. This is a security win (overflows of malloc will get caught)
1887and also a performance win by exposing more memsets to the optimizer.
1888
1889This occurs several times in viterbi.
1890
1891Note that this would change the semantics of @llvm.objectsize which by its
1892current definition always folds to a constant. We also should make sure that
1893we remove checking in code like
1894
1895 char *p = malloc(strlen(s)+1);
1896 __strcpy_chk(p, s, __builtin_objectsize(p, 0));
1897
1898//===---------------------------------------------------------------------===//
1899
Chris Lattner73552c22011-01-06 07:09:23 +00001900This code (from Benchmarks/Dhrystone/dry.c):
1901
1902define i32 @Func1(i32, i32) nounwind readnone optsize ssp {
1903entry:
1904 %sext = shl i32 %0, 24
1905 %conv = ashr i32 %sext, 24
1906 %sext6 = shl i32 %1, 24
1907 %conv4 = ashr i32 %sext6, 24
1908 %cmp = icmp eq i32 %conv, %conv4
1909 %. = select i1 %cmp, i32 10000, i32 0
1910 ret i32 %.
1911}
1912
1913Should be simplified into something like:
1914
1915define i32 @Func1(i32, i32) nounwind readnone optsize ssp {
1916entry:
1917 %sext = shl i32 %0, 24
1918 %conv = and i32 %sext, 0xFF000000
1919 %sext6 = shl i32 %1, 24
1920 %conv4 = and i32 %sext6, 0xFF000000
1921 %cmp = icmp eq i32 %conv, %conv4
1922 %. = select i1 %cmp, i32 10000, i32 0
1923 ret i32 %.
1924}
1925
1926and then to:
1927
1928define i32 @Func1(i32, i32) nounwind readnone optsize ssp {
1929entry:
1930 %conv = and i32 %0, 0xFF
1931 %conv4 = and i32 %1, 0xFF
1932 %cmp = icmp eq i32 %conv, %conv4
1933 %. = select i1 %cmp, i32 10000, i32 0
1934 ret i32 %.
1935}
1936//===---------------------------------------------------------------------===//
Chris Lattner6c3fc0a2011-01-01 22:57:31 +00001937
Benjamin Kramer1e01ade2011-01-06 17:35:50 +00001938clang -O3 currently compiles this code
1939
1940int g(unsigned int a) {
1941 unsigned int c[100];
1942 c[10] = a;
1943 c[11] = a;
1944 unsigned int b = c[10] + c[11];
1945 if(b > a*2) a = 4;
1946 else a = 8;
1947 return a + 7;
1948}
1949
1950into
1951
1952define i32 @g(i32 a) nounwind readnone {
1953 %add = shl i32 %a, 1
1954 %mul = shl i32 %a, 1
1955 %cmp = icmp ugt i32 %add, %mul
1956 %a.addr.0 = select i1 %cmp, i32 11, i32 15
1957 ret i32 %a.addr.0
1958}
1959
1960The icmp should fold to false. This CSE opportunity is only available
1961after GVN and InstCombine have run.
1962
1963//===---------------------------------------------------------------------===//
Chris Lattner84184b72011-01-06 22:25:00 +00001964
1965memcpyopt should turn this:
1966
1967define i8* @test10(i32 %x) {
1968 %alloc = call noalias i8* @malloc(i32 %x) nounwind
1969 call void @llvm.memset.p0i8.i32(i8* %alloc, i8 0, i32 %x, i32 1, i1 false)
1970 ret i8* %alloc
1971}
1972
1973into a call to calloc. We should make sure that we analyze calloc as
1974aggressively as malloc though.
1975
1976//===---------------------------------------------------------------------===//
Chandler Carruth5d684c12011-01-09 01:32:55 +00001977
Chris Lattner78cdd2a2011-01-10 21:01:17 +00001978clang -O3 doesn't optimize this:
Chandler Carruth5d684c12011-01-09 01:32:55 +00001979
1980void f1(int* begin, int* end) {
1981 std::fill(begin, end, 0);
1982}
1983
Chris Lattner5b358c62011-01-09 23:48:41 +00001984into a memset. This is PR8942.
Chandler Carruth5d684c12011-01-09 01:32:55 +00001985
1986//===---------------------------------------------------------------------===//
Chandler Carruthf3261932011-01-09 09:58:33 +00001987
1988clang -O3 -fno-exceptions currently compiles this code:
1989
1990void f(int N) {
1991 std::vector<int> v(N);
Chandler Carruth43f6d1b2011-01-09 10:10:59 +00001992
1993 extern void sink(void*); sink(&v);
Chandler Carruthf3261932011-01-09 09:58:33 +00001994}
1995
1996into
1997
1998define void @_Z1fi(i32 %N) nounwind {
1999entry:
2000 %v2 = alloca [3 x i32*], align 8
2001 %v2.sub = getelementptr inbounds [3 x i32*]* %v2, i64 0, i64 0
2002 %tmpcast = bitcast [3 x i32*]* %v2 to %"class.std::vector"*
2003 %conv = sext i32 %N to i64
2004 store i32* null, i32** %v2.sub, align 8, !tbaa !0
2005 %tmp3.i.i.i.i.i = getelementptr inbounds [3 x i32*]* %v2, i64 0, i64 1
2006 store i32* null, i32** %tmp3.i.i.i.i.i, align 8, !tbaa !0
2007 %tmp4.i.i.i.i.i = getelementptr inbounds [3 x i32*]* %v2, i64 0, i64 2
2008 store i32* null, i32** %tmp4.i.i.i.i.i, align 8, !tbaa !0
2009 %cmp.i.i.i.i = icmp eq i32 %N, 0
2010 br i1 %cmp.i.i.i.i, label %_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.thread.i.i, label %cond.true.i.i.i.i
2011
2012_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.thread.i.i: ; preds = %entry
2013 store i32* null, i32** %v2.sub, align 8, !tbaa !0
2014 store i32* null, i32** %tmp3.i.i.i.i.i, align 8, !tbaa !0
2015 %add.ptr.i5.i.i = getelementptr inbounds i32* null, i64 %conv
2016 store i32* %add.ptr.i5.i.i, i32** %tmp4.i.i.i.i.i, align 8, !tbaa !0
2017 br label %_ZNSt6vectorIiSaIiEEC1EmRKiRKS0_.exit
2018
2019cond.true.i.i.i.i: ; preds = %entry
2020 %cmp.i.i.i.i.i = icmp slt i32 %N, 0
2021 br i1 %cmp.i.i.i.i.i, label %if.then.i.i.i.i.i, label %_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.i.i
2022
2023if.then.i.i.i.i.i: ; preds = %cond.true.i.i.i.i
2024 call void @_ZSt17__throw_bad_allocv() noreturn nounwind
2025 unreachable
2026
2027_ZNSt12_Vector_baseIiSaIiEEC2EmRKS0_.exit.i.i: ; preds = %cond.true.i.i.i.i
2028 %mul.i.i.i.i.i = shl i64 %conv, 2
2029 %call3.i.i.i.i.i = call noalias i8* @_Znwm(i64 %mul.i.i.i.i.i) nounwind
2030 %0 = bitcast i8* %call3.i.i.i.i.i to i32*
2031 store i32* %0, i32** %v2.sub, align 8, !tbaa !0
2032 store i32* %0, i32** %tmp3.i.i.i.i.i, align 8, !tbaa !0
2033 %add.ptr.i.i.i = getelementptr inbounds i32* %0, i64 %conv
2034 store i32* %add.ptr.i.i.i, i32** %tmp4.i.i.i.i.i, align 8, !tbaa !0
2035 call void @llvm.memset.p0i8.i64(i8* %call3.i.i.i.i.i, i8 0, i64 %mul.i.i.i.i.i, i32 4, i1 false)
2036 br label %_ZNSt6vectorIiSaIiEEC1EmRKiRKS0_.exit
2037
2038This is just the handling the construction of the vector. Most surprising here
Chris Lattnerc326ebd2011-01-16 06:39:44 +00002039is the fact that all three null stores in %entry are dead (because we do no
2040cross-block DSE).
2041
Chandler Carruthf3261932011-01-09 09:58:33 +00002042Also surprising is that %conv isn't simplified to 0 in %....exit.thread.i.i.
Chris Lattnerc326ebd2011-01-16 06:39:44 +00002043This is a because the client of LazyValueInfo doesn't simplify all instruction
2044operands, just selected ones.
Chandler Carruthf3261932011-01-09 09:58:33 +00002045
2046//===---------------------------------------------------------------------===//
Chandler Carruthad6e1f02011-01-09 09:58:36 +00002047
2048clang -O3 -fno-exceptions currently compiles this code:
2049
Chandler Carruthef28abe2011-01-16 01:40:23 +00002050void f(char* a, int n) {
2051 __builtin_memset(a, 0, n);
2052 for (int i = 0; i < n; ++i)
2053 a[i] = 0;
Chandler Carruthad6e1f02011-01-09 09:58:36 +00002054}
2055
Chandler Carruthef28abe2011-01-16 01:40:23 +00002056into:
Chandler Carruthad6e1f02011-01-09 09:58:36 +00002057
Chandler Carruthef28abe2011-01-16 01:40:23 +00002058define void @_Z1fPci(i8* nocapture %a, i32 %n) nounwind {
2059entry:
2060 %conv = sext i32 %n to i64
2061 tail call void @llvm.memset.p0i8.i64(i8* %a, i8 0, i64 %conv, i32 1, i1 false)
2062 %cmp8 = icmp sgt i32 %n, 0
2063 br i1 %cmp8, label %for.body.lr.ph, label %for.end
Chandler Carruthad6e1f02011-01-09 09:58:36 +00002064
Chandler Carruthef28abe2011-01-16 01:40:23 +00002065for.body.lr.ph: ; preds = %entry
2066 %tmp10 = add i32 %n, -1
2067 %tmp11 = zext i32 %tmp10 to i64
2068 %tmp12 = add i64 %tmp11, 1
2069 call void @llvm.memset.p0i8.i64(i8* %a, i8 0, i64 %tmp12, i32 1, i1 false)
2070 ret void
Chandler Carruthad6e1f02011-01-09 09:58:36 +00002071
Chandler Carruthef28abe2011-01-16 01:40:23 +00002072for.end: ; preds = %entry
2073 ret void
2074}
2075
2076This shouldn't need the ((zext (%n - 1)) + 1) game, and it should ideally fold
Eli Friedman822e7bc2011-03-22 20:49:53 +00002077the two memset's together.
Chandler Carruthad6e1f02011-01-09 09:58:36 +00002078
Eli Friedman822e7bc2011-03-22 20:49:53 +00002079The issue with the addition only occurs in 64-bit mode, and appears to be at
2080least partially caused by Scalar Evolution not keeping its cache updated: it
2081returns the "wrong" result immediately after indvars runs, but figures out the
2082expected result if it is run from scratch on IR resulting from running indvars.
Chris Lattnerc326ebd2011-01-16 06:39:44 +00002083
Chandler Carruthad6e1f02011-01-09 09:58:36 +00002084//===---------------------------------------------------------------------===//
Chandler Carruth82e6f6a2011-01-09 11:29:57 +00002085
2086clang -O3 -fno-exceptions currently compiles this code:
2087
2088struct S {
2089 unsigned short m1, m2;
2090 unsigned char m3, m4;
2091};
2092
2093void f(int N) {
2094 std::vector<S> v(N);
2095 extern void sink(void*); sink(&v);
2096}
2097
2098into poor code for zero-initializing 'v' when N is >0. The problem is that
2099S is only 6 bytes, but each element is 8 byte-aligned. We generate a loop and
21004 stores on each iteration. If the struct were 8 bytes, this gets turned into
2101a memset.
2102
Chris Lattnerc326ebd2011-01-16 06:39:44 +00002103In order to handle this we have to:
2104 A) Teach clang to generate metadata for memsets of structs that have holes in
2105 them.
2106 B) Teach clang to use such a memset for zero init of this struct (since it has
2107 a hole), instead of doing elementwise zeroing.
2108
Chandler Carruth82e6f6a2011-01-09 11:29:57 +00002109//===---------------------------------------------------------------------===//
Chandler Carruth0c68a6682011-01-09 21:00:19 +00002110
2111clang -O3 currently compiles this code:
2112
2113extern const int magic;
2114double f() { return 0.0 * magic; }
2115
2116into
2117
2118@magic = external constant i32
2119
2120define double @_Z1fv() nounwind readnone {
2121entry:
2122 %tmp = load i32* @magic, align 4, !tbaa !0
2123 %conv = sitofp i32 %tmp to double
2124 %mul = fmul double %conv, 0.000000e+00
2125 ret double %mul
2126}
2127
Chris Lattnereef14552011-01-10 00:33:01 +00002128We should be able to fold away this fmul to 0.0. More generally, fmul(x,0.0)
2129can be folded to 0.0 if we can prove that the LHS is not -0.0, not a NaN, and
2130not an INF. The CannotBeNegativeZero predicate in value tracking should be
2131extended to support general "fpclassify" operations that can return
2132yes/no/unknown for each of these predicates.
2133
Chris Lattner78cdd2a2011-01-10 21:01:17 +00002134In this predicate, we know that uitofp is trivially never NaN or -0.0, and
Chris Lattnereef14552011-01-10 00:33:01 +00002135we know that it isn't +/-Inf if the floating point type has enough exponent bits
2136to represent the largest integer value as < inf.
Chandler Carruth0c68a6682011-01-09 21:00:19 +00002137
2138//===---------------------------------------------------------------------===//
Chandler Carruthd011d532011-01-09 22:36:18 +00002139
Chris Lattner78cdd2a2011-01-10 21:01:17 +00002140When optimizing a transformation that can change the sign of 0.0 (such as the
21410.0*val -> 0.0 transformation above), it might be provable that the sign of the
2142expression doesn't matter. For example, by the above rules, we can't transform
2143fmul(sitofp(x), 0.0) into 0.0, because x might be -1 and the result of the
2144expression is defined to be -0.0.
2145
2146If we look at the uses of the fmul for example, we might be able to prove that
2147all uses don't care about the sign of zero. For example, if we have:
2148
2149 fadd(fmul(sitofp(x), 0.0), 2.0)
2150
2151Since we know that x+2.0 doesn't care about the sign of any zeros in X, we can
2152transform the fmul to 0.0, and then the fadd to 2.0.
2153
2154//===---------------------------------------------------------------------===//
Chris Lattnerb9cdf392011-01-13 22:08:15 +00002155
2156We should enhance memcpy/memcpy/memset to allow a metadata node on them
2157indicating that some bytes of the transfer are undefined. This is useful for
Chris Lattnerb6c3aff2011-01-13 22:11:56 +00002158frontends like clang when lowering struct copies, when some elements of the
Chris Lattnerb9cdf392011-01-13 22:08:15 +00002159struct are undefined. Consider something like this:
2160
2161struct x {
2162 char a;
2163 int b[4];
2164};
2165void foo(struct x*P);
2166struct x testfunc() {
2167 struct x V1, V2;
2168 foo(&V1);
2169 V2 = V1;
2170
2171 return V2;
2172}
2173
2174We currently compile this to:
2175$ clang t.c -S -o - -O0 -emit-llvm | opt -scalarrepl -S
2176
2177
2178%struct.x = type { i8, [4 x i32] }
2179
2180define void @testfunc(%struct.x* sret %agg.result) nounwind ssp {
2181entry:
2182 %V1 = alloca %struct.x, align 4
2183 call void @foo(%struct.x* %V1)
2184 %tmp1 = bitcast %struct.x* %V1 to i8*
2185 %0 = bitcast %struct.x* %V1 to i160*
2186 %srcval1 = load i160* %0, align 4
2187 %tmp2 = bitcast %struct.x* %agg.result to i8*
2188 %1 = bitcast %struct.x* %agg.result to i160*
2189 store i160 %srcval1, i160* %1, align 4
2190 ret void
2191}
2192
2193This happens because SRoA sees that the temp alloca has is being memcpy'd into
2194and out of and it has holes and it has to be conservative. If we knew about the
2195holes, then this could be much much better.
2196
2197Having information about these holes would also improve memcpy (etc) lowering at
2198llc time when it gets inlined, because we can use smaller transfers. This also
2199avoids partial register stalls in some important cases.
2200
2201//===---------------------------------------------------------------------===//
Chris Lattner28bf91f2011-02-16 19:16:34 +00002202
Chris Lattner727eebe2011-02-17 01:43:46 +00002203We don't fold (icmp (add) (add)) unless the two adds only have a single use.
2204There are a lot of cases that we're refusing to fold in (e.g.) 256.bzip2, for
2205example:
2206
2207 %indvar.next90 = add i64 %indvar89, 1 ;; Has 2 uses
2208 %tmp96 = add i64 %tmp95, 1 ;; Has 1 use
2209 %exitcond97 = icmp eq i64 %indvar.next90, %tmp96
2210
2211We don't fold this because we don't want to introduce an overlapped live range
2212of the ivar. However if we can make this more aggressive without causing
2213performance issues in two ways:
2214
22151. If *either* the LHS or RHS has a single use, we can definitely do the
2216 transformation. In the overlapping liverange case we're trading one register
2217 use for one fewer operation, which is a reasonable trade. Before doing this
2218 we should verify that the llc output actually shrinks for some benchmarks.
22192. If both ops have multiple uses, we can still fold it if the operations are
2220 both sinkable to *after* the icmp (e.g. in a subsequent block) which doesn't
2221 increase register pressure.
2222
2223There are a ton of icmp's we aren't simplifying because of the reg pressure
2224concern. Care is warranted here though because many of these are induction
2225variables and other cases that matter a lot to performance, like the above.
2226Here's a blob of code that you can drop into the bottom of visitICmp to see some
2227missed cases:
2228
2229 { Value *A, *B, *C, *D;
2230 if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&
2231 match(Op1, m_Add(m_Value(C), m_Value(D))) &&
2232 (A == C || A == D || B == C || B == D)) {
2233 errs() << "OP0 = " << *Op0 << " U=" << Op0->getNumUses() << "\n";
2234 errs() << "OP1 = " << *Op1 << " U=" << Op1->getNumUses() << "\n";
2235 errs() << "CMP = " << I << "\n\n";
2236 }
2237 }
2238
2239//===---------------------------------------------------------------------===//
2240
Benjamin Kramerdc0082b2011-03-25 17:32:40 +00002241define i1 @test1(i32 %x) nounwind {
2242 %and = and i32 %x, 3
2243 %cmp = icmp ult i32 %and, 2
2244 ret i1 %cmp
2245}
Chris Lattner727eebe2011-02-17 01:43:46 +00002246
Benjamin Kramerdc0082b2011-03-25 17:32:40 +00002247Can be folded to (x & 2) == 0.
2248
2249define i1 @test2(i32 %x) nounwind {
2250 %and = and i32 %x, 3
2251 %cmp = icmp ugt i32 %and, 1
2252 ret i1 %cmp
2253}
2254
2255Can be folded to (x & 2) != 0.
2256
2257SimplifyDemandedBits shrinks the "and" constant to 2 but instcombine misses the
2258icmp transform.
2259
2260//===---------------------------------------------------------------------===//
Chris Lattner1d313c62011-04-14 04:21:42 +00002261
Chris Lattner6e298922011-04-25 18:44:26 +00002262This code:
2263
2264typedef struct {
2265int f1:1;
2266int f2:1;
2267int f3:1;
2268int f4:29;
2269} t1;
2270
2271typedef struct {
2272int f1:1;
2273int f2:1;
2274int f3:30;
2275} t2;
2276
2277t1 s1;
2278t2 s2;
2279
2280void func1(void)
2281{
2282s1.f1 = s2.f1;
2283s1.f2 = s2.f2;
2284}
2285
2286Compiles into this IR (on x86-64 at least):
2287
2288%struct.t1 = type { i8, [3 x i8] }
2289@s2 = global %struct.t1 zeroinitializer, align 4
2290@s1 = global %struct.t1 zeroinitializer, align 4
2291define void @func1() nounwind ssp noredzone {
2292entry:
2293 %0 = load i32* bitcast (%struct.t1* @s2 to i32*), align 4
2294 %bf.val.sext5 = and i32 %0, 1
2295 %1 = load i32* bitcast (%struct.t1* @s1 to i32*), align 4
2296 %2 = and i32 %1, -4
2297 %3 = or i32 %2, %bf.val.sext5
2298 %bf.val.sext26 = and i32 %0, 2
2299 %4 = or i32 %3, %bf.val.sext26
2300 store i32 %4, i32* bitcast (%struct.t1* @s1 to i32*), align 4
2301 ret void
2302}
2303
2304The two or/and's should be merged into one each.
2305
2306//===---------------------------------------------------------------------===//
2307
Chris Lattnerbbc40ac2011-05-22 05:45:06 +00002308Machine level code hoisting can be useful in some cases. For example, PR9408
2309is about:
Chris Lattner6e298922011-04-25 18:44:26 +00002310
Chris Lattnerbbc40ac2011-05-22 05:45:06 +00002311typedef union {
2312 void (*f1)(int);
2313 void (*f2)(long);
2314} funcs;
2315
2316void foo(funcs f, int which) {
2317 int a = 5;
2318 if (which) {
2319 f.f1(a);
2320 } else {
2321 f.f2(a);
2322 }
2323}
2324
2325which we compile to:
2326
2327foo: # @foo
2328# BB#0: # %entry
2329 pushq %rbp
2330 movq %rsp, %rbp
2331 testl %esi, %esi
2332 movq %rdi, %rax
2333 je .LBB0_2
2334# BB#1: # %if.then
2335 movl $5, %edi
2336 callq *%rax
2337 popq %rbp
2338 ret
2339.LBB0_2: # %if.else
2340 movl $5, %edi
2341 callq *%rax
2342 popq %rbp
2343 ret
2344
2345Note that bb1 and bb2 are the same. This doesn't happen at the IR level
2346because one call is passing an i32 and the other is passing an i64.
2347
2348//===---------------------------------------------------------------------===//