1 //===---------------------------------------------------------------------===//
2 // Random ideas for the X86 backend.
3 //===---------------------------------------------------------------------===//
5 We should add support for the "movbe" instruction, which does a byte-swapping
6 copy (3-addr bswap + memory support?) This is available on Atom processors.
8 //===---------------------------------------------------------------------===//
10 CodeGen/X86/lea-3.ll:test3 should be a single LEA, not a shift/move. The X86
11 backend knows how to three-addressify this shift, but it appears the register
12 allocator isn't even asking it to do so in this case. We should investigate
13 why this isn't happening, it could have significant impact on other important
14 cases for X86 as well.
16 //===---------------------------------------------------------------------===//
18 This should be one DIV/IDIV instruction, not a libcall:
20 unsigned test(unsigned long long X, unsigned Y) {
24 This can be done trivially with a custom legalizer. What about overflow
25 though? http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14224
27 //===---------------------------------------------------------------------===//
29 Improvements to the multiply -> shift/add algorithm:
30 http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01590.html
32 //===---------------------------------------------------------------------===//
34 Improve code like this (occurs fairly frequently, e.g. in LLVM):
35 long long foo(int x) { return 1LL << x; }
37 http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01109.html
38 http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01128.html
39 http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01136.html
41 Another useful one would be ~0ULL >> X and ~0ULL << X.
43 One better solution for 1LL << x is:
52 But that requires good 8-bit subreg support.
54 Also, this might be better. It's an extra shift, but it's one instruction
55 shorter, and doesn't stress 8-bit subreg support.
56 (From http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01148.html,
57 but without the unnecessary and.)
65 64-bit shifts (in general) expand to really bad code. Instead of using
66 cmovs, we should expand to a conditional branch like GCC produces.
68 //===---------------------------------------------------------------------===//
71 _Bool f(_Bool a) { return a!=1; }
78 (Although note that this isn't a legal way to express the code that llvm-gcc
79 currently generates for that function.)
81 //===---------------------------------------------------------------------===//
85 1. Dynamic programming based approach when compile time if not an
87 2. Code duplication (addressing mode) during isel.
88 3. Other ideas from "Register-Sensitive Selection, Duplication, and
89 Sequencing of Instructions".
90 4. Scheduling for reduced register pressure. E.g. "Minimum Register
91 Instruction Sequence Problem: Revisiting Optimal Code Generation for DAGs"
92 and other related papers.
93 http://citeseer.ist.psu.edu/govindarajan01minimum.html
95 //===---------------------------------------------------------------------===//
97 Should we promote i16 to i32 to avoid partial register update stalls?
99 //===---------------------------------------------------------------------===//
101 Leave any_extend as pseudo instruction and hint to register
102 allocator. Delay codegen until post register allocation.
103 Note. any_extend is now turned into an INSERT_SUBREG. We still need to teach
104 the coalescer how to deal with it though.
106 //===---------------------------------------------------------------------===//
108 It appears icc use push for parameter passing. Need to investigate.
110 //===---------------------------------------------------------------------===//
112 Only use inc/neg/not instructions on processors where they are faster than
113 add/sub/xor. They are slower on the P4 due to only updating some processor
116 //===---------------------------------------------------------------------===//
118 The instruction selector sometimes misses folding a load into a compare. The
119 pattern is written as (cmp reg, (load p)). Because the compare isn't
120 commutative, it is not matched with the load on both sides. The dag combiner
121 should be made smart enough to cannonicalize the load into the RHS of a compare
122 when it can invert the result of the compare for free.
124 //===---------------------------------------------------------------------===//
126 In many cases, LLVM generates code like this:
135 on some processors (which ones?), it is more efficient to do this:
144 Doing this correctly is tricky though, as the xor clobbers the flags.
146 //===---------------------------------------------------------------------===//
148 We should generate bts/btr/etc instructions on targets where they are cheap or
149 when codesize is important. e.g., for:
151 void setbit(int *target, int bit) {
152 *target |= (1 << bit);
154 void clearbit(int *target, int bit) {
155 *target &= ~(1 << bit);
158 //===---------------------------------------------------------------------===//
160 Instead of the following for memset char*, 1, 10:
162 movl $16843009, 4(%edx)
163 movl $16843009, (%edx)
166 It might be better to generate
173 when we can spare a register. It reduces code size.
175 //===---------------------------------------------------------------------===//
177 Evaluate what the best way to codegen sdiv X, (2^C) is. For X/8, we currently
180 define i32 @test1(i32 %X) {
194 GCC knows several different ways to codegen it, one of which is this:
204 which is probably slower, but it's interesting at least :)
206 //===---------------------------------------------------------------------===//
208 We are currently lowering large (1MB+) memmove/memcpy to rep/stosl and rep/movsl
209 We should leave these as libcalls for everything over a much lower threshold,
210 since libc is hand tuned for medium and large mem ops (avoiding RFO for large
211 stores, TLB preheating, etc)
213 //===---------------------------------------------------------------------===//
215 Optimize this into something reasonable:
216 x * copysign(1.0, y) * copysign(1.0, z)
218 //===---------------------------------------------------------------------===//
220 Optimize copysign(x, *y) to use an integer load from y.
222 //===---------------------------------------------------------------------===//
224 The following tests perform worse with LSR:
226 lambda, siod, optimizer-eval, ackermann, hash2, nestedloop, strcat, and Treesor.
228 //===---------------------------------------------------------------------===//
230 Teach the coalescer to coalesce vregs of different register classes. e.g. FR32 /
233 //===---------------------------------------------------------------------===//
235 Adding to the list of cmp / test poor codegen issues:
237 int test(__m128 *A, __m128 *B) {
238 if (_mm_comige_ss(*A, *B))
258 Note the setae, movzbl, cmpl, cmove can be replaced with a single cmovae. There
259 are a number of issues. 1) We are introducing a setcc between the result of the
260 intrisic call and select. 2) The intrinsic is expected to produce a i32 value
261 so a any extend (which becomes a zero extend) is added.
263 We probably need some kind of target DAG combine hook to fix this.
265 //===---------------------------------------------------------------------===//
267 We generate significantly worse code for this than GCC:
268 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21150
269 http://gcc.gnu.org/bugzilla/attachment.cgi?id=8701
271 There is also one case we do worse on PPC.
273 //===---------------------------------------------------------------------===//
283 imull $3, 4(%esp), %eax
285 Perhaps this is what we really should generate is? Is imull three or four
286 cycles? Note: ICC generates this:
288 leal (%eax,%eax,2), %eax
290 The current instruction priority is based on pattern complexity. The former is
291 more "complex" because it folds a load so the latter will not be emitted.
293 Perhaps we should use AddedComplexity to give LEA32r a higher priority? We
294 should always try to match LEA first since the LEA matching code does some
295 estimate to determine whether the match is profitable.
297 However, if we care more about code size, then imull is better. It's two bytes
298 shorter than movl + leal.
300 On a Pentium M, both variants have the same characteristics with regard
301 to throughput; however, the multiplication has a latency of four cycles, as
302 opposed to two cycles for the movl+lea variant.
304 //===---------------------------------------------------------------------===//
306 __builtin_ffs codegen is messy.
308 int ffs_(unsigned X) { return __builtin_ffs(X); }
331 Another example of __builtin_ffs (use predsimplify to eliminate a select):
333 int foo (unsigned long j) {
335 return __builtin_ffs (j) - 1;
340 //===---------------------------------------------------------------------===//
342 It appears gcc place string data with linkonce linkage in
343 .section __TEXT,__const_coal,coalesced instead of
344 .section __DATA,__const_coal,coalesced.
345 Take a look at darwin.h, there are other Darwin assembler directives that we
348 //===---------------------------------------------------------------------===//
350 define i32 @foo(i32* %a, i32 %t) {
354 cond_true: ; preds = %cond_true, %entry
355 %x.0.0 = phi i32 [ 0, %entry ], [ %tmp9, %cond_true ] ; <i32> [#uses=3]
356 %t_addr.0.0 = phi i32 [ %t, %entry ], [ %tmp7, %cond_true ] ; <i32> [#uses=1]
357 %tmp2 = getelementptr i32* %a, i32 %x.0.0 ; <i32*> [#uses=1]
358 %tmp3 = load i32* %tmp2 ; <i32> [#uses=1]
359 %tmp5 = add i32 %t_addr.0.0, %x.0.0 ; <i32> [#uses=1]
360 %tmp7 = add i32 %tmp5, %tmp3 ; <i32> [#uses=2]
361 %tmp9 = add i32 %x.0.0, 1 ; <i32> [#uses=2]
362 %tmp = icmp sgt i32 %tmp9, 39 ; <i1> [#uses=1]
363 br i1 %tmp, label %bb12, label %cond_true
365 bb12: ; preds = %cond_true
368 is pessimized by -loop-reduce and -indvars
370 //===---------------------------------------------------------------------===//
372 u32 to float conversion improvement:
374 float uint32_2_float( unsigned u ) {
375 float fl = (int) (u & 0xffff);
376 float fh = (int) (u >> 16);
381 00000000 subl $0x04,%esp
382 00000003 movl 0x08(%esp,1),%eax
383 00000007 movl %eax,%ecx
384 00000009 shrl $0x10,%ecx
385 0000000c cvtsi2ss %ecx,%xmm0
386 00000010 andl $0x0000ffff,%eax
387 00000015 cvtsi2ss %eax,%xmm1
388 00000019 mulss 0x00000078,%xmm0
389 00000021 addss %xmm1,%xmm0
390 00000025 movss %xmm0,(%esp,1)
391 0000002a flds (%esp,1)
392 0000002d addl $0x04,%esp
395 //===---------------------------------------------------------------------===//
397 When using fastcc abi, align stack slot of argument of type double on 8 byte
398 boundary to improve performance.
400 //===---------------------------------------------------------------------===//
404 int f(int a, int b) {
405 if (a == 4 || a == 6)
417 //===---------------------------------------------------------------------===//
419 GCC's ix86_expand_int_movcc function (in i386.c) has a ton of interesting
420 simplifications for integer "x cmp y ? a : b". For example, instead of:
423 void f(int X, int Y) {
450 int usesbb(unsigned int a, unsigned int b) {
451 return (a < b ? -1 : 0);
465 movl $4294967295, %ecx
469 //===---------------------------------------------------------------------===//
471 Consider the expansion of:
473 define i32 @test3(i32 %X) {
474 %tmp1 = urem i32 %X, 255
478 Currently it compiles to:
481 movl $2155905153, %ecx
487 This could be "reassociated" into:
489 movl $2155905153, %eax
493 to avoid the copy. In fact, the existing two-address stuff would do this
494 except that mul isn't a commutative 2-addr instruction. I guess this has
495 to be done at isel time based on the #uses to mul?
497 //===---------------------------------------------------------------------===//
499 Make sure the instruction which starts a loop does not cross a cacheline
500 boundary. This requires knowning the exact length of each machine instruction.
501 That is somewhat complicated, but doable. Example 256.bzip2:
503 In the new trace, the hot loop has an instruction which crosses a cacheline
504 boundary. In addition to potential cache misses, this can't help decoding as I
505 imagine there has to be some kind of complicated decoder reset and realignment
506 to grab the bytes from the next cacheline.
508 532 532 0x3cfc movb (1809(%esp, %esi), %bl <<<--- spans 2 64 byte lines
509 942 942 0x3d03 movl %dh, (1809(%esp, %esi)
510 937 937 0x3d0a incl %esi
511 3 3 0x3d0b cmpb %bl, %dl
512 27 27 0x3d0d jnz 0x000062db <main+11707>
514 //===---------------------------------------------------------------------===//
516 In c99 mode, the preprocessor doesn't like assembly comments like #TRUNCATE.
518 //===---------------------------------------------------------------------===//
520 This could be a single 16-bit load.
523 if ((p[0] == 1) & (p[1] == 2)) return 1;
527 //===---------------------------------------------------------------------===//
529 We should inline lrintf and probably other libc functions.
531 //===---------------------------------------------------------------------===//
533 Start using the flags more. For example, compile:
535 int add_zf(int *x, int y, int a, int b) {
559 int add_zf(int *x, int y, int a, int b) {
583 //===---------------------------------------------------------------------===//
585 These two functions have identical effects:
587 unsigned int f(unsigned int i, unsigned int n) {++i; if (i == n) ++i; return i;}
588 unsigned int f2(unsigned int i, unsigned int n) {++i; i += i == n; return i;}
590 We currently compile them to:
598 jne LBB1_2 #UnifiedReturnBlock
602 LBB1_2: #UnifiedReturnBlock
612 leal 1(%ecx,%eax), %eax
615 both of which are inferior to GCC's:
633 //===---------------------------------------------------------------------===//
641 is currently compiled to:
652 It would be better to produce:
661 This can be applied to any no-return function call that takes no arguments etc.
662 Alternatively, the stack save/restore logic could be shrink-wrapped, producing
673 Both are useful in different situations. Finally, it could be shrink-wrapped
674 and tail called, like this:
681 pop %eax # realign stack.
684 Though this probably isn't worth it.
686 //===---------------------------------------------------------------------===//
688 We need to teach the codegen to convert two-address INC instructions to LEA
689 when the flags are dead (likewise dec). For example, on X86-64, compile:
691 int foo(int A, int B) {
710 ;; X's live range extends beyond the shift, so the register allocator
711 ;; cannot coalesce it with Y. Because of this, a copy needs to be
712 ;; emitted before the shift to save the register value before it is
713 ;; clobbered. However, this copy is not needed if the register
714 ;; allocator turns the shift into an LEA. This also occurs for ADD.
716 ; Check that the shift gets turned into an LEA.
717 ; RUN: llvm-as < %s | llc -march=x86 -x86-asm-syntax=intel | \
718 ; RUN: not grep {mov E.X, E.X}
720 @G = external global i32 ; <i32*> [#uses=3]
722 define i32 @test1(i32 %X, i32 %Y) {
723 %Z = add i32 %X, %Y ; <i32> [#uses=1]
724 volatile store i32 %Y, i32* @G
725 volatile store i32 %Z, i32* @G
729 define i32 @test2(i32 %X) {
730 %Z = add i32 %X, 1 ; <i32> [#uses=1]
731 volatile store i32 %Z, i32* @G
735 //===---------------------------------------------------------------------===//
737 Sometimes it is better to codegen subtractions from a constant (e.g. 7-x) with
738 a neg instead of a sub instruction. Consider:
740 int test(char X) { return 7-X; }
742 we currently produce:
749 We would use one fewer register if codegen'd as:
756 Note that this isn't beneficial if the load can be folded into the sub. In
757 this case, we want a sub:
759 int test(int X) { return 7-X; }
765 //===---------------------------------------------------------------------===//
767 Leaf functions that require one 4-byte spill slot have a prolog like this:
773 and an epilog like this:
778 It would be smaller, and potentially faster, to push eax on entry and to
779 pop into a dummy register instead of using addl/subl of esp. Just don't pop
780 into any return registers :)
782 //===---------------------------------------------------------------------===//
784 The X86 backend should fold (branch (or (setcc, setcc))) into multiple
785 branches. We generate really poor code for:
787 double testf(double a) {
788 return a == 0.0 ? 0.0 : (a > 0.0 ? 1.0 : -1.0);
791 For example, the entry BB is:
796 movsd 24(%esp), %xmm1
801 jne LBB1_5 # UnifiedReturnBlock
805 it would be better to replace the last four instructions with:
811 We also codegen the inner ?: into a diamond:
813 cvtss2sd LCPI1_0(%rip), %xmm2
814 cvtss2sd LCPI1_1(%rip), %xmm3
816 ja LBB1_3 # cond_true
823 We should sink the load into xmm3 into the LBB1_2 block. This should
824 be pretty easy, and will nuke all the copies.
826 //===---------------------------------------------------------------------===//
830 inline std::pair<unsigned, bool> full_add(unsigned a, unsigned b)
831 { return std::make_pair(a + b, a + b < a); }
832 bool no_overflow(unsigned a, unsigned b)
833 { return !full_add(a, b).second; }
843 FIXME: That code looks wrong; bool return is normally defined as zext.
855 //===---------------------------------------------------------------------===//
857 Re-materialize MOV32r0 etc. with xor instead of changing them to moves if the
858 condition register is dead. xor reg reg is shorter than mov reg, #0.
860 //===---------------------------------------------------------------------===//
864 bb114.preheader: ; preds = %cond_next94
865 %tmp231232 = sext i16 %tmp62 to i32 ; <i32> [#uses=1]
866 %tmp233 = sub i32 32, %tmp231232 ; <i32> [#uses=1]
867 %tmp245246 = sext i16 %tmp65 to i32 ; <i32> [#uses=1]
868 %tmp252253 = sext i16 %tmp68 to i32 ; <i32> [#uses=1]
869 %tmp254 = sub i32 32, %tmp252253 ; <i32> [#uses=1]
870 %tmp553554 = bitcast i16* %tmp37 to i8* ; <i8*> [#uses=2]
871 %tmp583584 = sext i16 %tmp98 to i32 ; <i32> [#uses=1]
872 %tmp585 = sub i32 32, %tmp583584 ; <i32> [#uses=1]
873 %tmp614615 = sext i16 %tmp101 to i32 ; <i32> [#uses=1]
874 %tmp621622 = sext i16 %tmp104 to i32 ; <i32> [#uses=1]
875 %tmp623 = sub i32 32, %tmp621622 ; <i32> [#uses=1]
880 LBB3_5: # bb114.preheader
881 movswl -68(%ebp), %eax
885 movswl -52(%ebp), %eax
888 movswl -70(%ebp), %eax
891 movswl -50(%ebp), %eax
894 movswl -42(%ebp), %eax
896 movswl -66(%ebp), %eax
900 This appears to be bad because the RA is not folding the store to the stack
901 slot into the movl. The above instructions could be:
906 This seems like a cross between remat and spill folding.
908 This has redundant subtractions of %eax from a stack slot. However, %ecx doesn't
909 change, so we could simply subtract %eax from %ecx first and then use %ecx (or
912 //===---------------------------------------------------------------------===//
916 %tmp659 = icmp slt i16 %tmp654, 0 ; <i1> [#uses=1]
917 br i1 %tmp659, label %cond_true662, label %cond_next715
923 jns LBB4_109 # cond_next715
925 Shark tells us that using %cx in the testw instruction is sub-optimal. It
926 suggests using the 32-bit register (which is what ICC uses).
928 //===---------------------------------------------------------------------===//
932 void compare (long long foo) {
933 if (foo < 4294967297LL)
949 jne .LBB1_2 # UnifiedReturnBlock
952 .LBB1_2: # UnifiedReturnBlock
956 (also really horrible code on ppc). This is due to the expand code for 64-bit
957 compares. GCC produces multiple branches, which is much nicer:
978 //===---------------------------------------------------------------------===//
980 Tail call optimization improvements: Tail call optimization currently
981 pushes all arguments on the top of the stack (their normal place for
982 non-tail call optimized calls) that source from the callers arguments
983 or that source from a virtual register (also possibly sourcing from
985 This is done to prevent overwriting of parameters (see example
986 below) that might be used later.
990 int callee(int32, int64);
991 int caller(int32 arg1, int32 arg2) {
992 int64 local = arg2 * 2;
993 return callee(arg2, (int64)local);
996 [arg1] [!arg2 no longer valid since we moved local onto it]
1000 Moving arg1 onto the stack slot of callee function would overwrite
1003 Possible optimizations:
1006 - Analyse the actual parameters of the callee to see which would
1007 overwrite a caller parameter which is used by the callee and only
1008 push them onto the top of the stack.
1010 int callee (int32 arg1, int32 arg2);
1011 int caller (int32 arg1, int32 arg2) {
1012 return callee(arg1,arg2);
1015 Here we don't need to write any variables to the top of the stack
1016 since they don't overwrite each other.
1018 int callee (int32 arg1, int32 arg2);
1019 int caller (int32 arg1, int32 arg2) {
1020 return callee(arg2,arg1);
1023 Here we need to push the arguments because they overwrite each
1026 //===---------------------------------------------------------------------===//
1031 unsigned long int z = 0;
1042 gcc compiles this to:
1068 jge LBB1_4 # cond_true
1071 addl $4294950912, %ecx
1081 1. LSR should rewrite the first cmp with induction variable %ecx.
1082 2. DAG combiner should fold
1088 //===---------------------------------------------------------------------===//
1090 define i64 @test(double %X) {
1091 %Y = fptosi double %X to i64
1099 movsd 24(%esp), %xmm0
1100 movsd %xmm0, 8(%esp)
1109 This should just fldl directly from the input stack slot.
1111 //===---------------------------------------------------------------------===//
1114 int foo (int x) { return (x & 65535) | 255; }
1116 Should compile into:
1119 movzwl 4(%esp), %eax
1130 //===---------------------------------------------------------------------===//
1132 We're codegen'ing multiply of long longs inefficiently:
1134 unsigned long long LLM(unsigned long long arg1, unsigned long long arg2) {
1138 We compile to (fomit-frame-pointer):
1146 imull 12(%esp), %esi
1148 imull 20(%esp), %ecx
1154 This looks like a scheduling deficiency and lack of remat of the load from
1155 the argument area. ICC apparently produces:
1158 imull 12(%esp), %ecx
1167 Note that it remat'd loads from 4(esp) and 12(esp). See this GCC PR:
1168 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17236
1170 //===---------------------------------------------------------------------===//
1172 We can fold a store into "zeroing a reg". Instead of:
1175 movl %eax, 124(%esp)
1181 if the flags of the xor are dead.
1183 Likewise, we isel "x<<1" into "add reg,reg". If reg is spilled, this should
1184 be folded into: shl [mem], 1
1186 //===---------------------------------------------------------------------===//
1188 This testcase misses a read/modify/write opportunity (from PR1425):
1190 void vertical_decompose97iH1(int *b0, int *b1, int *b2, int width){
1192 for(i=0; i<width; i++)
1193 b1[i] += (1*(b0[i] + b2[i])+0)>>0;
1196 We compile it down to:
1199 movl (%esi,%edi,4), %ebx
1200 addl (%ecx,%edi,4), %ebx
1201 addl (%edx,%edi,4), %ebx
1202 movl %ebx, (%ecx,%edi,4)
1207 the inner loop should add to the memory location (%ecx,%edi,4), saving
1208 a mov. Something like:
1210 movl (%esi,%edi,4), %ebx
1211 addl (%edx,%edi,4), %ebx
1212 addl %ebx, (%ecx,%edi,4)
1214 Here is another interesting example:
1216 void vertical_compose97iH1(int *b0, int *b1, int *b2, int width){
1218 for(i=0; i<width; i++)
1219 b1[i] -= (1*(b0[i] + b2[i])+0)>>0;
1222 We miss the r/m/w opportunity here by using 2 subs instead of an add+sub[mem]:
1225 movl (%ecx,%edi,4), %ebx
1226 subl (%esi,%edi,4), %ebx
1227 subl (%edx,%edi,4), %ebx
1228 movl %ebx, (%ecx,%edi,4)
1233 Additionally, LSR should rewrite the exit condition of these loops to use
1234 a stride-4 IV, would would allow all the scales in the loop to go away.
1235 This would result in smaller code and more efficient microops.
1237 //===---------------------------------------------------------------------===//
1239 In SSE mode, we turn abs and neg into a load from the constant pool plus a xor
1240 or and instruction, for example:
1242 xorpd LCPI1_0, %xmm2
1244 However, if xmm2 gets spilled, we end up with really ugly code like this:
1247 xorpd LCPI1_0, %xmm0
1250 Since we 'know' that this is a 'neg', we can actually "fold" the spill into
1251 the neg/abs instruction, turning it into an *integer* operation, like this:
1253 xorl 2147483648, [mem+4] ## 2147483648 = (1 << 31)
1255 you could also use xorb, but xorl is less likely to lead to a partial register
1256 stall. Here is a contrived testcase:
1259 void test(double *P) {
1269 //===---------------------------------------------------------------------===//
1271 handling llvm.memory.barrier on pre SSE2 cpus
1274 lock ; mov %esp, %esp
1276 //===---------------------------------------------------------------------===//
1278 The generated code on x86 for checking for signed overflow on a multiply the
1279 obvious way is much longer than it needs to be.
1281 int x(int a, int b) {
1282 long long prod = (long long)a*b;
1283 return prod > 0x7FFFFFFF || prod < (-0x7FFFFFFF-1);
1286 See PR2053 for more details.
1288 //===---------------------------------------------------------------------===//
1290 We should investigate using cdq/ctld (effect: edx = sar eax, 31)
1291 more aggressively; it should cost the same as a move+shift on any modern
1292 processor, but it's a lot shorter. Downside is that it puts more
1293 pressure on register allocation because it has fixed operands.
1296 int abs(int x) {return x < 0 ? -x : x;}
1298 gcc compiles this to the following when using march/mtune=pentium2/3/4/m/etc.:
1306 //===---------------------------------------------------------------------===//
1309 int test(unsigned long a, unsigned long b) { return -(a < b); }
1311 We currently compile this to:
1313 define i32 @test(i32 %a, i32 %b) nounwind {
1314 %tmp3 = icmp ult i32 %a, %b ; <i1> [#uses=1]
1315 %tmp34 = zext i1 %tmp3 to i32 ; <i32> [#uses=1]
1316 %tmp5 = sub i32 0, %tmp34 ; <i32> [#uses=1]
1330 Several deficiencies here. First, we should instcombine zext+neg into sext:
1332 define i32 @test2(i32 %a, i32 %b) nounwind {
1333 %tmp3 = icmp ult i32 %a, %b ; <i1> [#uses=1]
1334 %tmp34 = sext i1 %tmp3 to i32 ; <i32> [#uses=1]
1338 However, before we can do that, we have to fix the bad codegen that we get for
1350 This code should be at least as good as the code above. Once this is fixed, we
1351 can optimize this specific case even more to:
1358 //===---------------------------------------------------------------------===//
1360 Take the following code (from
1361 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16541):
1363 extern unsigned char first_one[65536];
1364 int FirstOnet(unsigned long long arg1)
1367 return (first_one[arg1 >> 48]);
1372 The following code is currently generated:
1377 jb .LBB1_2 # UnifiedReturnBlock
1380 movzbl first_one(%eax), %eax
1382 .LBB1_2: # UnifiedReturnBlock
1386 There are a few possible improvements here:
1387 1. We should be able to eliminate the dead load into %ecx
1388 2. We could change the "movl 8(%esp), %eax" into
1389 "movzwl 10(%esp), %eax"; this lets us change the cmpl
1390 into a testl, which is shorter, and eliminate the shift.
1392 We could also in theory eliminate the branch by using a conditional
1393 for the address of the load, but that seems unlikely to be worthwhile
1396 //===---------------------------------------------------------------------===//
1398 We compile this function:
1400 define i32 @foo(i32 %a, i32 %b, i32 %c, i8 zeroext %d) nounwind {
1402 %tmp2 = icmp eq i8 %d, 0 ; <i1> [#uses=1]
1403 br i1 %tmp2, label %bb7, label %bb
1405 bb: ; preds = %entry
1406 %tmp6 = add i32 %b, %a ; <i32> [#uses=1]
1409 bb7: ; preds = %entry
1410 %tmp10 = sub i32 %a, %c ; <i32> [#uses=1]
1430 The coalescer could coalesce "edx" with "eax" to avoid the movl in LBB1_2
1431 if it commuted the addl in LBB1_1.
1433 //===---------------------------------------------------------------------===//
1440 cvtss2sd LCPI1_0, %xmm1
1442 movsd 176(%esp), %xmm2
1447 mulsd LCPI1_23, %xmm4
1448 addsd LCPI1_24, %xmm4
1450 addsd LCPI1_25, %xmm4
1452 addsd LCPI1_26, %xmm4
1454 addsd LCPI1_27, %xmm4
1456 addsd LCPI1_28, %xmm4
1460 movsd 152(%esp), %xmm1
1462 movsd %xmm1, 152(%esp)
1466 LBB1_16: # bb358.loopexit
1467 movsd 152(%esp), %xmm0
1469 addsd LCPI1_22, %xmm0
1470 movsd %xmm0, 152(%esp)
1472 Rather than spilling the result of the last addsd in the loop, we should have
1473 insert a copy to split the interval (one for the duration of the loop, one
1474 extending to the fall through). The register pressure in the loop isn't high
1475 enough to warrant the spill.
1477 Also check why xmm7 is not used at all in the function.
1479 //===---------------------------------------------------------------------===//
1481 Legalize loses track of the fact that bools are always zero extended when in
1482 memory. This causes us to compile abort_gzip (from 164.gzip) from:
1484 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
1485 target triple = "i386-apple-darwin8"
1486 @in_exit.4870.b = internal global i1 false ; <i1*> [#uses=2]
1487 define fastcc void @abort_gzip() noreturn nounwind {
1489 %tmp.b.i = load i1* @in_exit.4870.b ; <i1> [#uses=1]
1490 br i1 %tmp.b.i, label %bb.i, label %bb4.i
1491 bb.i: ; preds = %entry
1492 tail call void @exit( i32 1 ) noreturn nounwind
1494 bb4.i: ; preds = %entry
1495 store i1 true, i1* @in_exit.4870.b
1496 tail call void @exit( i32 1 ) noreturn nounwind
1499 declare void @exit(i32) noreturn nounwind
1505 movb _in_exit.4870.b, %al
1512 //===---------------------------------------------------------------------===//
1516 int test(int x, int y) {
1528 it would be better to codegen as: x+~y (notl+addl)
1530 //===---------------------------------------------------------------------===//
1534 int foo(const char *str,...)
1536 __builtin_va_list a; int x;
1537 __builtin_va_start(a,str); x = __builtin_va_arg(a,int); __builtin_va_end(a);
1541 gets compiled into this on x86-64:
1543 movaps %xmm7, 160(%rsp)
1544 movaps %xmm6, 144(%rsp)
1545 movaps %xmm5, 128(%rsp)
1546 movaps %xmm4, 112(%rsp)
1547 movaps %xmm3, 96(%rsp)
1548 movaps %xmm2, 80(%rsp)
1549 movaps %xmm1, 64(%rsp)
1550 movaps %xmm0, 48(%rsp)
1557 movq %rax, 192(%rsp)
1558 leaq 208(%rsp), %rax
1559 movq %rax, 184(%rsp)
1562 movl 176(%rsp), %eax
1566 movq 184(%rsp), %rcx
1568 movq %rax, 184(%rsp)
1576 addq 192(%rsp), %rcx
1577 movl %eax, 176(%rsp)
1583 leaq 104(%rsp), %rax
1584 movq %rsi, -80(%rsp)
1586 movq %rax, -112(%rsp)
1587 leaq -88(%rsp), %rax
1588 movq %rax, -104(%rsp)
1592 movq -112(%rsp), %rdx
1600 addq -104(%rsp), %rdx
1602 movl %eax, -120(%rsp)
1607 and it gets compiled into this on x86:
1627 //===---------------------------------------------------------------------===//
1629 Teach tblgen not to check bitconvert source type in some cases. This allows us
1630 to consolidate the following patterns in X86InstrMMX.td:
1632 def : Pat<(v2i32 (bitconvert (i64 (vector_extract (v2i64 VR128:$src),
1634 (v2i32 (MMX_MOVDQ2Qrr VR128:$src))>;
1635 def : Pat<(v4i16 (bitconvert (i64 (vector_extract (v2i64 VR128:$src),
1637 (v4i16 (MMX_MOVDQ2Qrr VR128:$src))>;
1638 def : Pat<(v8i8 (bitconvert (i64 (vector_extract (v2i64 VR128:$src),
1640 (v8i8 (MMX_MOVDQ2Qrr VR128:$src))>;
1642 There are other cases in various td files.
1644 //===---------------------------------------------------------------------===//
1646 Take something like the following on x86-32:
1647 unsigned a(unsigned long long x, unsigned y) {return x % y;}
1649 We currently generate a libcall, but we really shouldn't: the expansion is
1650 shorter and likely faster than the libcall. The expected code is something
1662 A similar code sequence works for division.
1664 //===---------------------------------------------------------------------===//
1666 These should compile to the same code, but the later codegen's to useless
1667 instructions on X86. This may be a trivial dag combine (GCC PR7061):
1669 struct s1 { unsigned char a, b; };
1670 unsigned long f1(struct s1 x) {
1673 struct s2 { unsigned a: 8, b: 8; };
1674 unsigned long f2(struct s2 x) {
1678 //===---------------------------------------------------------------------===//
1680 We currently compile this:
1682 define i32 @func1(i32 %v1, i32 %v2) nounwind {
1684 %t = call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %v1, i32 %v2)
1685 %sum = extractvalue {i32, i1} %t, 0
1686 %obit = extractvalue {i32, i1} %t, 1
1687 br i1 %obit, label %overflow, label %normal
1691 call void @llvm.trap()
1694 declare {i32, i1} @llvm.sadd.with.overflow.i32(i32, i32)
1695 declare void @llvm.trap()
1702 jo LBB1_2 ## overflow
1708 it would be nice to produce "into" someday.
1710 //===---------------------------------------------------------------------===//
1714 void vec_mpys1(int y[], const int x[], int scaler) {
1716 for (i = 0; i < 150; i++)
1717 y[i] += (((long long)scaler * (long long)x[i]) >> 31);
1720 Compiles to this loop with GCC 3.x:
1725 shrdl $31, %edx, %eax
1726 addl %eax, (%esi,%ecx,4)
1731 llvm-gcc compiles it to the much uglier:
1735 movl (%eax,%edi,4), %ebx
1744 shldl $1, %eax, %ebx
1746 addl %ebx, (%eax,%edi,4)
1751 The issue is that we hoist the cast of "scaler" to long long outside of the
1752 loop, the value comes into the loop as two values, and
1753 RegsForValue::getCopyFromRegs doesn't know how to put an AssertSext on the
1754 constructed BUILD_PAIR which represents the cast value.
1756 //===---------------------------------------------------------------------===//
1758 Test instructions can be eliminated by using EFLAGS values from arithmetic
1759 instructions. This is currently not done for mul, and, or, xor, neg, shl,
1760 sra, srl, shld, shrd, atomic ops, and others. It is also currently not done
1761 for read-modify-write instructions. It is also current not done if the
1762 OF or CF flags are needed.
1764 The shift operators have the complication that when the shift count is
1765 zero, EFLAGS is not set, so they can only subsume a test instruction if
1766 the shift count is known to be non-zero. Also, using the EFLAGS value
1767 from a shift is apparently very slow on some x86 implementations.
1769 In read-modify-write instructions, the root node in the isel match is
1770 the store, and isel has no way for the use of the EFLAGS result of the
1771 arithmetic to be remapped to the new node.
1773 Add and subtract instructions set OF on signed overflow and CF on unsiged
1774 overflow, while test instructions always clear OF and CF. In order to
1775 replace a test with an add or subtract in a situation where OF or CF is
1776 needed, codegen must be able to prove that the operation cannot see
1777 signed or unsigned overflow, respectively.
1779 //===---------------------------------------------------------------------===//
1781 memcpy/memmove do not lower to SSE copies when possible. A silly example is:
1782 define <16 x float> @foo(<16 x float> %A) nounwind {
1783 %tmp = alloca <16 x float>, align 16
1784 %tmp2 = alloca <16 x float>, align 16
1785 store <16 x float> %A, <16 x float>* %tmp
1786 %s = bitcast <16 x float>* %tmp to i8*
1787 %s2 = bitcast <16 x float>* %tmp2 to i8*
1788 call void @llvm.memcpy.i64(i8* %s, i8* %s2, i64 64, i32 16)
1789 %R = load <16 x float>* %tmp2
1793 declare void @llvm.memcpy.i64(i8* nocapture, i8* nocapture, i64, i32) nounwind
1799 movaps %xmm3, 112(%esp)
1800 movaps %xmm2, 96(%esp)
1801 movaps %xmm1, 80(%esp)
1802 movaps %xmm0, 64(%esp)
1804 movl %eax, 124(%esp)
1806 movl %eax, 120(%esp)
1808 <many many more 32-bit copies>
1809 movaps (%esp), %xmm0
1810 movaps 16(%esp), %xmm1
1811 movaps 32(%esp), %xmm2
1812 movaps 48(%esp), %xmm3
1816 On Nehalem, it may even be cheaper to just use movups when unaligned than to
1817 fall back to lower-granularity chunks.
1819 //===---------------------------------------------------------------------===//
1821 Implement processor-specific optimizations for parity with GCC on these
1822 processors. GCC does two optimizations:
1824 1. ix86_pad_returns inserts a noop before ret instructions if immediately
1825 preceeded by a conditional branch or is the target of a jump.
1826 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of
1827 code contains more than 3 branches.
1829 The first one is done for all AMDs, Core2, and "Generic"
1830 The second one is done for: Atom, Pentium Pro, all AMDs, Pentium 4, Nocona,
1831 Core 2, and "Generic"
1833 //===---------------------------------------------------------------------===//
1836 int a(int x) { return (x & 127) > 31; }
1852 This should definitely be done in instcombine, canonicalizing the range
1853 condition into a != condition. We get this IR:
1855 define i32 @a(i32 %x) nounwind readnone {
1857 %0 = and i32 %x, 127 ; <i32> [#uses=1]
1858 %1 = icmp ugt i32 %0, 31 ; <i1> [#uses=1]
1859 %2 = zext i1 %1 to i32 ; <i32> [#uses=1]
1863 Instcombine prefers to strength reduce relational comparisons to equality
1864 comparisons when possible, this should be another case of that. This could
1865 be handled pretty easily in InstCombiner::visitICmpInstWithInstAndIntCst, but it
1866 looks like InstCombiner::visitICmpInstWithInstAndIntCst should really already
1867 be redesigned to use ComputeMaskedBits and friends.
1870 //===---------------------------------------------------------------------===//
1872 int x(int a) { return (a&0xf0)>>4; }
1881 movzbl 4(%esp), %eax
1885 //===---------------------------------------------------------------------===//
1888 int x(int a) { return (a & 0x80) ? 0x100 : 0; }
1889 int y(int a) { return (a & 0x80) *2; }
1904 This is another general instcombine transformation that is profitable on all
1905 targets. In LLVM IR, these functions look like this:
1907 define i32 @x(i32 %a) nounwind readnone {
1909 %0 = and i32 %a, 128
1910 %1 = icmp eq i32 %0, 0
1911 %iftmp.0.0 = select i1 %1, i32 0, i32 256
1915 define i32 @y(i32 %a) nounwind readnone {
1918 %1 = and i32 %0, 256
1922 Replacing an icmp+select with a shift should always be considered profitable in
1925 //===---------------------------------------------------------------------===//
1927 Re-implement atomic builtins __sync_add_and_fetch() and __sync_sub_and_fetch
1930 When the return value is not used (i.e. only care about the value in the
1931 memory), x86 does not have to use add to implement these. Instead, it can use
1932 add, sub, inc, dec instructions with the "lock" prefix.
1934 This is currently implemented using a bit of instruction selection trick. The
1935 issue is the target independent pattern produces one output and a chain and we
1936 want to map it into one that just output a chain. The current trick is to select
1937 it into a MERGE_VALUES with the first definition being an implicit_def. The
1938 proper solution is to add new ISD opcodes for the no-output variant. DAG
1939 combiner can then transform the node before it gets to target node selection.
1941 Problem #2 is we are adding a whole bunch of x86 atomic instructions when in
1942 fact these instructions are identical to the non-lock versions. We need a way to
1943 add target specific information to target nodes and have this information
1944 carried over to machine instructions. Asm printer (or JIT) can use this
1945 information to add the "lock" prefix.
1947 //===---------------------------------------------------------------------===//