1 //===---------------------------------------------------------------------===//
2 // Random ideas for the X86 backend.
3 //===---------------------------------------------------------------------===//
6 - Support for SSE4: http://www.intel.com/software/penryn
7 http://softwarecommunity.intel.com/isn/Downloads/Intel%20SSE4%20Programming%20Reference.pdf
11 //===---------------------------------------------------------------------===//
13 Add a MUL2U and MUL2S nodes to represent a multiply that returns both the
14 Hi and Lo parts (combination of MUL and MULH[SU] into one node). Add this to
15 X86, & make the dag combiner produce it when needed. This will eliminate one
16 imul from the code generated for:
18 long long test(long long X, long long Y) { return X*Y; }
20 by using the EAX result from the mul. We should add a similar node for
25 long long test(int X, int Y) { return (long long)X*Y; }
27 ... which should only be one imul instruction.
31 unsigned long long int t2(unsigned int a, unsigned int b) {
32 return (unsigned long long)a * b;
35 ... which should be one mul instruction.
38 This can be done with a custom expander, but it would be nice to move this to
41 //===---------------------------------------------------------------------===//
43 CodeGen/X86/lea-3.ll:test3 should be a single LEA, not a shift/move. The X86
44 backend knows how to three-addressify this shift, but it appears the register
45 allocator isn't even asking it to do so in this case. We should investigate
46 why this isn't happening, it could have significant impact on other important
47 cases for X86 as well.
49 //===---------------------------------------------------------------------===//
51 This should be one DIV/IDIV instruction, not a libcall:
53 unsigned test(unsigned long long X, unsigned Y) {
57 This can be done trivially with a custom legalizer. What about overflow
58 though? http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14224
60 //===---------------------------------------------------------------------===//
62 Improvements to the multiply -> shift/add algorithm:
63 http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01590.html
65 //===---------------------------------------------------------------------===//
67 Improve code like this (occurs fairly frequently, e.g. in LLVM):
68 long long foo(int x) { return 1LL << x; }
70 http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01109.html
71 http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01128.html
72 http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01136.html
74 Another useful one would be ~0ULL >> X and ~0ULL << X.
76 One better solution for 1LL << x is:
85 But that requires good 8-bit subreg support.
87 64-bit shifts (in general) expand to really bad code. Instead of using
88 cmovs, we should expand to a conditional branch like GCC produces.
90 //===---------------------------------------------------------------------===//
93 _Bool f(_Bool a) { return a!=1; }
100 //===---------------------------------------------------------------------===//
104 1. Dynamic programming based approach when compile time if not an
106 2. Code duplication (addressing mode) during isel.
107 3. Other ideas from "Register-Sensitive Selection, Duplication, and
108 Sequencing of Instructions".
109 4. Scheduling for reduced register pressure. E.g. "Minimum Register
110 Instruction Sequence Problem: Revisiting Optimal Code Generation for DAGs"
111 and other related papers.
112 http://citeseer.ist.psu.edu/govindarajan01minimum.html
114 //===---------------------------------------------------------------------===//
116 Should we promote i16 to i32 to avoid partial register update stalls?
118 //===---------------------------------------------------------------------===//
120 Leave any_extend as pseudo instruction and hint to register
121 allocator. Delay codegen until post register allocation.
123 //===---------------------------------------------------------------------===//
125 Count leading zeros and count trailing zeros:
127 int clz(int X) { return __builtin_clz(X); }
128 int ctz(int X) { return __builtin_ctz(X); }
130 $ gcc t.c -S -o - -O3 -fomit-frame-pointer -masm=intel
132 bsr %eax, DWORD PTR [%esp+4]
136 bsf %eax, DWORD PTR [%esp+4]
139 however, check that these are defined for 0 and 32. Our intrinsics are, GCC's
142 Another example (use predsimplify to eliminate a select):
144 int foo (unsigned long j) {
146 return __builtin_ffs (j) - 1;
151 //===---------------------------------------------------------------------===//
153 Use push/pop instructions in prolog/epilog sequences instead of stores off
154 ESP (certain code size win, perf win on some [which?] processors).
155 Also, it appears icc use push for parameter passing. Need to investigate.
157 //===---------------------------------------------------------------------===//
159 Only use inc/neg/not instructions on processors where they are faster than
160 add/sub/xor. They are slower on the P4 due to only updating some processor
163 //===---------------------------------------------------------------------===//
165 The instruction selector sometimes misses folding a load into a compare. The
166 pattern is written as (cmp reg, (load p)). Because the compare isn't
167 commutative, it is not matched with the load on both sides. The dag combiner
168 should be made smart enough to cannonicalize the load into the RHS of a compare
169 when it can invert the result of the compare for free.
171 //===---------------------------------------------------------------------===//
173 How about intrinsics? An example is:
174 *res = _mm_mulhi_epu16(*A, _mm_mul_epu32(*B, *C));
177 pmuludq (%eax), %xmm0
182 The transformation probably requires a X86 specific pass or a DAG combiner
183 target specific hook.
185 //===---------------------------------------------------------------------===//
187 In many cases, LLVM generates code like this:
196 on some processors (which ones?), it is more efficient to do this:
205 Doing this correctly is tricky though, as the xor clobbers the flags.
207 //===---------------------------------------------------------------------===//
209 We should generate bts/btr/etc instructions on targets where they are cheap or
210 when codesize is important. e.g., for:
212 void setbit(int *target, int bit) {
213 *target |= (1 << bit);
215 void clearbit(int *target, int bit) {
216 *target &= ~(1 << bit);
219 //===---------------------------------------------------------------------===//
221 Instead of the following for memset char*, 1, 10:
223 movl $16843009, 4(%edx)
224 movl $16843009, (%edx)
227 It might be better to generate
234 when we can spare a register. It reduces code size.
236 //===---------------------------------------------------------------------===//
238 Evaluate what the best way to codegen sdiv X, (2^C) is. For X/8, we currently
255 GCC knows several different ways to codegen it, one of which is this:
265 which is probably slower, but it's interesting at least :)
267 //===---------------------------------------------------------------------===//
269 The first BB of this code:
273 %V = call bool %foo()
274 br bool %V, label %T, label %F
291 It would be better to emit "cmp %al, 1" than a xor and test.
293 //===---------------------------------------------------------------------===//
295 Enable X86InstrInfo::convertToThreeAddress().
297 //===---------------------------------------------------------------------===//
299 We are currently lowering large (1MB+) memmove/memcpy to rep/stosl and rep/movsl
300 We should leave these as libcalls for everything over a much lower threshold,
301 since libc is hand tuned for medium and large mem ops (avoiding RFO for large
302 stores, TLB preheating, etc)
304 //===---------------------------------------------------------------------===//
306 Optimize this into something reasonable:
307 x * copysign(1.0, y) * copysign(1.0, z)
309 //===---------------------------------------------------------------------===//
311 Optimize copysign(x, *y) to use an integer load from y.
313 //===---------------------------------------------------------------------===//
315 %X = weak global int 0
318 %N = cast int %N to uint
319 %tmp.24 = setgt int %N, 0
320 br bool %tmp.24, label %no_exit, label %return
323 %indvar = phi uint [ 0, %entry ], [ %indvar.next, %no_exit ]
324 %i.0.0 = cast uint %indvar to int
325 volatile store int %i.0.0, int* %X
326 %indvar.next = add uint %indvar, 1
327 %exitcond = seteq uint %indvar.next, %N
328 br bool %exitcond, label %return, label %no_exit
342 jl LBB_foo_4 # return
343 LBB_foo_1: # no_exit.preheader
346 movl L_X$non_lazy_ptr, %edx
350 jne LBB_foo_2 # no_exit
351 LBB_foo_3: # return.loopexit
355 We should hoist "movl L_X$non_lazy_ptr, %edx" out of the loop after
356 remateralization is implemented. This can be accomplished with 1) a target
357 dependent LICM pass or 2) makeing SelectDAG represent the whole function.
359 //===---------------------------------------------------------------------===//
361 The following tests perform worse with LSR:
363 lambda, siod, optimizer-eval, ackermann, hash2, nestedloop, strcat, and Treesor.
365 //===---------------------------------------------------------------------===//
367 We are generating far worse code than gcc:
373 for (i = 0; i < N; i++) { X = i; Y = i*4; }
376 LBB1_1: #bb.preheader
380 movl L_X$non_lazy_ptr, %esi
384 movl L_Y$non_lazy_ptr, %edi
394 movl L_X$non_lazy_ptr-"L00000000001$pb"(%ebx), %esi
395 movl L_Y$non_lazy_ptr-"L00000000001$pb"(%ebx), %ecx
398 leal 0(,%edx,4), %eax
406 1. Lack of post regalloc LICM.
407 2. Poor sub-regclass support. That leads to inability to promote the 16-bit
408 arithmetic op to 32-bit and making use of leal.
409 3. LSR unable to reused IV for a different type (i16 vs. i32) even though
410 the cast would be free.
412 //===---------------------------------------------------------------------===//
414 Teach the coalescer to coalesce vregs of different register classes. e.g. FR32 /
417 //===---------------------------------------------------------------------===//
425 Obviously it would have been better for the first mov (or any op) to store
426 directly %esp[0] if there are no other uses.
428 //===---------------------------------------------------------------------===//
430 Adding to the list of cmp / test poor codegen issues:
432 int test(__m128 *A, __m128 *B) {
433 if (_mm_comige_ss(*A, *B))
453 Note the setae, movzbl, cmpl, cmove can be replaced with a single cmovae. There
454 are a number of issues. 1) We are introducing a setcc between the result of the
455 intrisic call and select. 2) The intrinsic is expected to produce a i32 value
456 so a any extend (which becomes a zero extend) is added.
458 We probably need some kind of target DAG combine hook to fix this.
460 //===---------------------------------------------------------------------===//
462 We generate significantly worse code for this than GCC:
463 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21150
464 http://gcc.gnu.org/bugzilla/attachment.cgi?id=8701
466 There is also one case we do worse on PPC.
468 //===---------------------------------------------------------------------===//
470 If shorter, we should use things like:
475 The former can also be used when the two-addressy nature of the 'and' would
476 require a copy to be inserted (in X86InstrInfo::convertToThreeAddress).
478 //===---------------------------------------------------------------------===//
482 char foo(int x) { return x; }
490 SIGN_EXTEND_INREG can be implemented as (sext (trunc)) to take advantage of
493 //===---------------------------------------------------------------------===//
497 typedef struct pair { float A, B; } pair;
498 void pairtest(pair P, float *FP) {
502 We currently generate this code with llvmgcc4:
514 we should be able to generate:
522 The issue is that llvmgcc4 is forcing the struct to memory, then passing it as
523 integer chunks. It does this so that structs like {short,short} are passed in
524 a single 32-bit integer stack slot. We should handle the safe cases above much
525 nicer, while still handling the hard cases.
527 While true in general, in this specific case we could do better by promoting
528 load int + bitcast to float -> load fload. This basically needs alignment info,
529 the code is already implemented (but disabled) in dag combine).
531 //===---------------------------------------------------------------------===//
533 Another instruction selector deficiency:
536 %tmp = load int (int)** %foo
537 %tmp = tail call int %tmp( int 3 )
543 movl L_foo$non_lazy_ptr, %eax
549 The current isel scheme will not allow the load to be folded in the call since
550 the load's chain result is read by the callseq_start.
552 //===---------------------------------------------------------------------===//
554 Don't forget to find a way to squash noop truncates in the JIT environment.
556 //===---------------------------------------------------------------------===//
558 Implement anyext in the same manner as truncate that would allow them to be
561 //===---------------------------------------------------------------------===//
563 How about implementing truncate / anyext as a property of machine instruction
564 operand? i.e. Print as 32-bit super-class register / 16-bit sub-class register.
565 Do this for the cases where a truncate / anyext is guaranteed to be eliminated.
566 For IA32 that is truncate from 32 to 16 and anyext from 16 to 32.
568 //===---------------------------------------------------------------------===//
578 imull $3, 4(%esp), %eax
580 Perhaps this is what we really should generate is? Is imull three or four
581 cycles? Note: ICC generates this:
583 leal (%eax,%eax,2), %eax
585 The current instruction priority is based on pattern complexity. The former is
586 more "complex" because it folds a load so the latter will not be emitted.
588 Perhaps we should use AddedComplexity to give LEA32r a higher priority? We
589 should always try to match LEA first since the LEA matching code does some
590 estimate to determine whether the match is profitable.
592 However, if we care more about code size, then imull is better. It's two bytes
593 shorter than movl + leal.
595 //===---------------------------------------------------------------------===//
597 Implement CTTZ, CTLZ with bsf and bsr.
599 //===---------------------------------------------------------------------===//
601 It appears gcc place string data with linkonce linkage in
602 .section __TEXT,__const_coal,coalesced instead of
603 .section __DATA,__const_coal,coalesced.
604 Take a look at darwin.h, there are other Darwin assembler directives that we
607 //===---------------------------------------------------------------------===//
609 int %foo(int* %a, int %t) {
613 cond_true: ; preds = %cond_true, %entry
614 %x.0.0 = phi int [ 0, %entry ], [ %tmp9, %cond_true ]
615 %t_addr.0.0 = phi int [ %t, %entry ], [ %tmp7, %cond_true ]
616 %tmp2 = getelementptr int* %a, int %x.0.0
617 %tmp3 = load int* %tmp2 ; <int> [#uses=1]
618 %tmp5 = add int %t_addr.0.0, %x.0.0 ; <int> [#uses=1]
619 %tmp7 = add int %tmp5, %tmp3 ; <int> [#uses=2]
620 %tmp9 = add int %x.0.0, 1 ; <int> [#uses=2]
621 %tmp = setgt int %tmp9, 39 ; <bool> [#uses=1]
622 br bool %tmp, label %bb12, label %cond_true
624 bb12: ; preds = %cond_true
628 is pessimized by -loop-reduce and -indvars
630 //===---------------------------------------------------------------------===//
632 u32 to float conversion improvement:
634 float uint32_2_float( unsigned u ) {
635 float fl = (int) (u & 0xffff);
636 float fh = (int) (u >> 16);
641 00000000 subl $0x04,%esp
642 00000003 movl 0x08(%esp,1),%eax
643 00000007 movl %eax,%ecx
644 00000009 shrl $0x10,%ecx
645 0000000c cvtsi2ss %ecx,%xmm0
646 00000010 andl $0x0000ffff,%eax
647 00000015 cvtsi2ss %eax,%xmm1
648 00000019 mulss 0x00000078,%xmm0
649 00000021 addss %xmm1,%xmm0
650 00000025 movss %xmm0,(%esp,1)
651 0000002a flds (%esp,1)
652 0000002d addl $0x04,%esp
655 //===---------------------------------------------------------------------===//
657 When using fastcc abi, align stack slot of argument of type double on 8 byte
658 boundary to improve performance.
660 //===---------------------------------------------------------------------===//
664 int f(int a, int b) {
665 if (a == 4 || a == 6)
677 //===---------------------------------------------------------------------===//
679 GCC's ix86_expand_int_movcc function (in i386.c) has a ton of interesting
680 simplifications for integer "x cmp y ? a : b". For example, instead of:
683 void f(int X, int Y) {
709 //===---------------------------------------------------------------------===//
711 Currently we don't have elimination of redundant stack manipulations. Consider
716 call fastcc void %test1( )
717 call fastcc void %test2( sbyte* cast (void ()* %test1 to sbyte*) )
721 declare fastcc void %test1()
723 declare fastcc void %test2(sbyte*)
726 This currently compiles to:
736 The add\sub pair is really unneeded here.
738 //===---------------------------------------------------------------------===//
740 We currently compile sign_extend_inreg into two shifts:
743 return (long)(signed char)X;
760 //===---------------------------------------------------------------------===//
762 Consider the expansion of:
764 uint %test3(uint %X) {
765 %tmp1 = rem uint %X, 255
769 Currently it compiles to:
772 movl $2155905153, %ecx
778 This could be "reassociated" into:
780 movl $2155905153, %eax
784 to avoid the copy. In fact, the existing two-address stuff would do this
785 except that mul isn't a commutative 2-addr instruction. I guess this has
786 to be done at isel time based on the #uses to mul?
788 //===---------------------------------------------------------------------===//
790 Make sure the instruction which starts a loop does not cross a cacheline
791 boundary. This requires knowning the exact length of each machine instruction.
792 That is somewhat complicated, but doable. Example 256.bzip2:
794 In the new trace, the hot loop has an instruction which crosses a cacheline
795 boundary. In addition to potential cache misses, this can't help decoding as I
796 imagine there has to be some kind of complicated decoder reset and realignment
797 to grab the bytes from the next cacheline.
799 532 532 0x3cfc movb (1809(%esp, %esi), %bl <<<--- spans 2 64 byte lines
800 942 942 0x3d03 movl %dh, (1809(%esp, %esi)
801 937 937 0x3d0a incl %esi
802 3 3 0x3d0b cmpb %bl, %dl
803 27 27 0x3d0d jnz 0x000062db <main+11707>
805 //===---------------------------------------------------------------------===//
807 In c99 mode, the preprocessor doesn't like assembly comments like #TRUNCATE.
809 //===---------------------------------------------------------------------===//
811 This could be a single 16-bit load.
814 if ((p[0] == 1) & (p[1] == 2)) return 1;
818 //===---------------------------------------------------------------------===//
820 We should inline lrintf and probably other libc functions.
822 //===---------------------------------------------------------------------===//
824 Start using the flags more. For example, compile:
826 int add_zf(int *x, int y, int a, int b) {
850 int add_zf(int *x, int y, int a, int b) {
874 //===---------------------------------------------------------------------===//
878 int foo(double X) { return isnan(X); }
889 the pxor is not needed, we could compare the value against itself.
891 //===---------------------------------------------------------------------===//
893 These two functions have identical effects:
895 unsigned int f(unsigned int i, unsigned int n) {++i; if (i == n) ++i; return i;}
896 unsigned int f2(unsigned int i, unsigned int n) {++i; i += i == n; return i;}
898 We currently compile them to:
906 jne LBB1_2 #UnifiedReturnBlock
910 LBB1_2: #UnifiedReturnBlock
920 leal 1(%ecx,%eax), %eax
923 both of which are inferior to GCC's:
941 //===---------------------------------------------------------------------===//
949 is currently compiled to:
960 It would be better to produce:
969 This can be applied to any no-return function call that takes no arguments etc.
970 Alternatively, the stack save/restore logic could be shrink-wrapped, producing
981 Both are useful in different situations. Finally, it could be shrink-wrapped
982 and tail called, like this:
989 pop %eax # realign stack.
992 Though this probably isn't worth it.
994 //===---------------------------------------------------------------------===//
996 We need to teach the codegen to convert two-address INC instructions to LEA
997 when the flags are dead. For example, on X86-64, compile:
999 int foo(int A, int B) {
1018 ;; X's live range extends beyond the shift, so the register allocator
1019 ;; cannot coalesce it with Y. Because of this, a copy needs to be
1020 ;; emitted before the shift to save the register value before it is
1021 ;; clobbered. However, this copy is not needed if the register
1022 ;; allocator turns the shift into an LEA. This also occurs for ADD.
1024 ; Check that the shift gets turned into an LEA.
1025 ; RUN: llvm-upgrade < %s | llvm-as | llc -march=x86 -x86-asm-syntax=intel | \
1026 ; RUN: not grep {mov E.X, E.X}
1028 %G = external global int
1030 int %test1(int %X, int %Y) {
1032 volatile store int %Y, int* %G
1033 volatile store int %Z, int* %G
1037 int %test2(int %X) {
1038 %Z = add int %X, 1 ;; inc
1039 volatile store int %Z, int* %G
1043 //===---------------------------------------------------------------------===//
1045 We use push/pop of stack space around calls in situations where we don't have to.
1046 Call to f below produces:
1047 subl $16, %esp <<<<<
1050 addl $16, %esp <<<<<
1051 The stack push/pop can be moved into the prolog/epilog. It does this because it's
1052 building the frame pointer, but this should not be sufficient, only the use of alloca
1053 should cause it to do this.
1054 (There are other issues shown by this code, but this is one.)
1056 typedef struct _range_t {
1062 unsigned char lut[];
1074 const range_t*const*range;
1077 typedef struct _decode_t decode_t;
1079 extern int f(const decode_t* decode);
1081 int decode_byte (const decode_t* decode) {
1082 if (decode->swap != 0)
1088 //===---------------------------------------------------------------------===//
1091 #include <xmmintrin.h>
1092 unsigned test(float f) {
1093 return _mm_cvtsi128_si32( (__m128i) _mm_set_ss( f ));
1098 movss 4(%esp), %xmm0
1102 it should compile to a move from the stack slot directly into eax. DAGCombine
1103 has this xform, but it is currently disabled until the alignment fields of
1104 the load/store nodes are trustworthy.
1106 //===---------------------------------------------------------------------===//
1108 Sometimes it is better to codegen subtractions from a constant (e.g. 7-x) with
1109 a neg instead of a sub instruction. Consider:
1111 int test(char X) { return 7-X; }
1113 we currently produce:
1116 movsbl 4(%esp), %ecx
1120 We would use one fewer register if codegen'd as:
1122 movsbl 4(%esp), %eax
1127 Note that this isn't beneficial if the load can be folded into the sub. In
1128 this case, we want a sub:
1130 int test(int X) { return 7-X; }