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 It appears icc use push for parameter passing. Need to investigate.
155 //===---------------------------------------------------------------------===//
157 Only use inc/neg/not instructions on processors where they are faster than
158 add/sub/xor. They are slower on the P4 due to only updating some processor
161 //===---------------------------------------------------------------------===//
163 The instruction selector sometimes misses folding a load into a compare. The
164 pattern is written as (cmp reg, (load p)). Because the compare isn't
165 commutative, it is not matched with the load on both sides. The dag combiner
166 should be made smart enough to cannonicalize the load into the RHS of a compare
167 when it can invert the result of the compare for free.
169 //===---------------------------------------------------------------------===//
171 How about intrinsics? An example is:
172 *res = _mm_mulhi_epu16(*A, _mm_mul_epu32(*B, *C));
175 pmuludq (%eax), %xmm0
180 The transformation probably requires a X86 specific pass or a DAG combiner
181 target specific hook.
183 //===---------------------------------------------------------------------===//
185 In many cases, LLVM generates code like this:
194 on some processors (which ones?), it is more efficient to do this:
203 Doing this correctly is tricky though, as the xor clobbers the flags.
205 //===---------------------------------------------------------------------===//
207 We should generate bts/btr/etc instructions on targets where they are cheap or
208 when codesize is important. e.g., for:
210 void setbit(int *target, int bit) {
211 *target |= (1 << bit);
213 void clearbit(int *target, int bit) {
214 *target &= ~(1 << bit);
217 //===---------------------------------------------------------------------===//
219 Instead of the following for memset char*, 1, 10:
221 movl $16843009, 4(%edx)
222 movl $16843009, (%edx)
225 It might be better to generate
232 when we can spare a register. It reduces code size.
234 //===---------------------------------------------------------------------===//
236 Evaluate what the best way to codegen sdiv X, (2^C) is. For X/8, we currently
253 GCC knows several different ways to codegen it, one of which is this:
263 which is probably slower, but it's interesting at least :)
265 //===---------------------------------------------------------------------===//
267 The first BB of this code:
271 %V = call bool %foo()
272 br bool %V, label %T, label %F
289 It would be better to emit "cmp %al, 1" than a xor and test.
291 //===---------------------------------------------------------------------===//
293 Enable X86InstrInfo::convertToThreeAddress().
295 //===---------------------------------------------------------------------===//
297 We are currently lowering large (1MB+) memmove/memcpy to rep/stosl and rep/movsl
298 We should leave these as libcalls for everything over a much lower threshold,
299 since libc is hand tuned for medium and large mem ops (avoiding RFO for large
300 stores, TLB preheating, etc)
302 //===---------------------------------------------------------------------===//
304 Optimize this into something reasonable:
305 x * copysign(1.0, y) * copysign(1.0, z)
307 //===---------------------------------------------------------------------===//
309 Optimize copysign(x, *y) to use an integer load from y.
311 //===---------------------------------------------------------------------===//
313 %X = weak global int 0
316 %N = cast int %N to uint
317 %tmp.24 = setgt int %N, 0
318 br bool %tmp.24, label %no_exit, label %return
321 %indvar = phi uint [ 0, %entry ], [ %indvar.next, %no_exit ]
322 %i.0.0 = cast uint %indvar to int
323 volatile store int %i.0.0, int* %X
324 %indvar.next = add uint %indvar, 1
325 %exitcond = seteq uint %indvar.next, %N
326 br bool %exitcond, label %return, label %no_exit
340 jl LBB_foo_4 # return
341 LBB_foo_1: # no_exit.preheader
344 movl L_X$non_lazy_ptr, %edx
348 jne LBB_foo_2 # no_exit
349 LBB_foo_3: # return.loopexit
353 We should hoist "movl L_X$non_lazy_ptr, %edx" out of the loop after
354 remateralization is implemented. This can be accomplished with 1) a target
355 dependent LICM pass or 2) makeing SelectDAG represent the whole function.
357 //===---------------------------------------------------------------------===//
359 The following tests perform worse with LSR:
361 lambda, siod, optimizer-eval, ackermann, hash2, nestedloop, strcat, and Treesor.
363 //===---------------------------------------------------------------------===//
365 We are generating far worse code than gcc:
371 for (i = 0; i < N; i++) { X = i; Y = i*4; }
374 LBB1_1: #bb.preheader
378 movl L_X$non_lazy_ptr, %esi
382 movl L_Y$non_lazy_ptr, %edi
392 movl L_X$non_lazy_ptr-"L00000000001$pb"(%ebx), %esi
393 movl L_Y$non_lazy_ptr-"L00000000001$pb"(%ebx), %ecx
396 leal 0(,%edx,4), %eax
404 1. Lack of post regalloc LICM.
405 2. LSR unable to reused IV for a different type (i16 vs. i32) even though
406 the cast would be free.
408 //===---------------------------------------------------------------------===//
410 Teach the coalescer to coalesce vregs of different register classes. e.g. FR32 /
413 //===---------------------------------------------------------------------===//
421 Obviously it would have been better for the first mov (or any op) to store
422 directly %esp[0] if there are no other uses.
424 //===---------------------------------------------------------------------===//
426 Adding to the list of cmp / test poor codegen issues:
428 int test(__m128 *A, __m128 *B) {
429 if (_mm_comige_ss(*A, *B))
449 Note the setae, movzbl, cmpl, cmove can be replaced with a single cmovae. There
450 are a number of issues. 1) We are introducing a setcc between the result of the
451 intrisic call and select. 2) The intrinsic is expected to produce a i32 value
452 so a any extend (which becomes a zero extend) is added.
454 We probably need some kind of target DAG combine hook to fix this.
456 //===---------------------------------------------------------------------===//
458 We generate significantly worse code for this than GCC:
459 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21150
460 http://gcc.gnu.org/bugzilla/attachment.cgi?id=8701
462 There is also one case we do worse on PPC.
464 //===---------------------------------------------------------------------===//
466 If shorter, we should use things like:
471 The former can also be used when the two-addressy nature of the 'and' would
472 require a copy to be inserted (in X86InstrInfo::convertToThreeAddress).
474 //===---------------------------------------------------------------------===//
478 typedef struct pair { float A, B; } pair;
479 void pairtest(pair P, float *FP) {
483 We currently generate this code with llvmgcc4:
495 we should be able to generate:
503 The issue is that llvmgcc4 is forcing the struct to memory, then passing it as
504 integer chunks. It does this so that structs like {short,short} are passed in
505 a single 32-bit integer stack slot. We should handle the safe cases above much
506 nicer, while still handling the hard cases.
508 While true in general, in this specific case we could do better by promoting
509 load int + bitcast to float -> load fload. This basically needs alignment info,
510 the code is already implemented (but disabled) in dag combine).
512 //===---------------------------------------------------------------------===//
514 Another instruction selector deficiency:
517 %tmp = load int (int)** %foo
518 %tmp = tail call int %tmp( int 3 )
524 movl L_foo$non_lazy_ptr, %eax
530 The current isel scheme will not allow the load to be folded in the call since
531 the load's chain result is read by the callseq_start.
533 //===---------------------------------------------------------------------===//
543 imull $3, 4(%esp), %eax
545 Perhaps this is what we really should generate is? Is imull three or four
546 cycles? Note: ICC generates this:
548 leal (%eax,%eax,2), %eax
550 The current instruction priority is based on pattern complexity. The former is
551 more "complex" because it folds a load so the latter will not be emitted.
553 Perhaps we should use AddedComplexity to give LEA32r a higher priority? We
554 should always try to match LEA first since the LEA matching code does some
555 estimate to determine whether the match is profitable.
557 However, if we care more about code size, then imull is better. It's two bytes
558 shorter than movl + leal.
560 //===---------------------------------------------------------------------===//
562 Implement CTTZ, CTLZ with bsf and bsr.
564 //===---------------------------------------------------------------------===//
566 It appears gcc place string data with linkonce linkage in
567 .section __TEXT,__const_coal,coalesced instead of
568 .section __DATA,__const_coal,coalesced.
569 Take a look at darwin.h, there are other Darwin assembler directives that we
572 //===---------------------------------------------------------------------===//
574 int %foo(int* %a, int %t) {
578 cond_true: ; preds = %cond_true, %entry
579 %x.0.0 = phi int [ 0, %entry ], [ %tmp9, %cond_true ]
580 %t_addr.0.0 = phi int [ %t, %entry ], [ %tmp7, %cond_true ]
581 %tmp2 = getelementptr int* %a, int %x.0.0
582 %tmp3 = load int* %tmp2 ; <int> [#uses=1]
583 %tmp5 = add int %t_addr.0.0, %x.0.0 ; <int> [#uses=1]
584 %tmp7 = add int %tmp5, %tmp3 ; <int> [#uses=2]
585 %tmp9 = add int %x.0.0, 1 ; <int> [#uses=2]
586 %tmp = setgt int %tmp9, 39 ; <bool> [#uses=1]
587 br bool %tmp, label %bb12, label %cond_true
589 bb12: ; preds = %cond_true
593 is pessimized by -loop-reduce and -indvars
595 //===---------------------------------------------------------------------===//
597 u32 to float conversion improvement:
599 float uint32_2_float( unsigned u ) {
600 float fl = (int) (u & 0xffff);
601 float fh = (int) (u >> 16);
606 00000000 subl $0x04,%esp
607 00000003 movl 0x08(%esp,1),%eax
608 00000007 movl %eax,%ecx
609 00000009 shrl $0x10,%ecx
610 0000000c cvtsi2ss %ecx,%xmm0
611 00000010 andl $0x0000ffff,%eax
612 00000015 cvtsi2ss %eax,%xmm1
613 00000019 mulss 0x00000078,%xmm0
614 00000021 addss %xmm1,%xmm0
615 00000025 movss %xmm0,(%esp,1)
616 0000002a flds (%esp,1)
617 0000002d addl $0x04,%esp
620 //===---------------------------------------------------------------------===//
622 When using fastcc abi, align stack slot of argument of type double on 8 byte
623 boundary to improve performance.
625 //===---------------------------------------------------------------------===//
629 int f(int a, int b) {
630 if (a == 4 || a == 6)
642 //===---------------------------------------------------------------------===//
644 GCC's ix86_expand_int_movcc function (in i386.c) has a ton of interesting
645 simplifications for integer "x cmp y ? a : b". For example, instead of:
648 void f(int X, int Y) {
674 //===---------------------------------------------------------------------===//
676 Currently we don't have elimination of redundant stack manipulations. Consider
681 call fastcc void %test1( )
682 call fastcc void %test2( sbyte* cast (void ()* %test1 to sbyte*) )
686 declare fastcc void %test1()
688 declare fastcc void %test2(sbyte*)
691 This currently compiles to:
701 The add\sub pair is really unneeded here.
703 //===---------------------------------------------------------------------===//
705 We currently compile sign_extend_inreg into two shifts:
708 return (long)(signed char)X;
725 //===---------------------------------------------------------------------===//
727 Consider the expansion of:
729 uint %test3(uint %X) {
730 %tmp1 = rem uint %X, 255
734 Currently it compiles to:
737 movl $2155905153, %ecx
743 This could be "reassociated" into:
745 movl $2155905153, %eax
749 to avoid the copy. In fact, the existing two-address stuff would do this
750 except that mul isn't a commutative 2-addr instruction. I guess this has
751 to be done at isel time based on the #uses to mul?
753 //===---------------------------------------------------------------------===//
755 Make sure the instruction which starts a loop does not cross a cacheline
756 boundary. This requires knowning the exact length of each machine instruction.
757 That is somewhat complicated, but doable. Example 256.bzip2:
759 In the new trace, the hot loop has an instruction which crosses a cacheline
760 boundary. In addition to potential cache misses, this can't help decoding as I
761 imagine there has to be some kind of complicated decoder reset and realignment
762 to grab the bytes from the next cacheline.
764 532 532 0x3cfc movb (1809(%esp, %esi), %bl <<<--- spans 2 64 byte lines
765 942 942 0x3d03 movl %dh, (1809(%esp, %esi)
766 937 937 0x3d0a incl %esi
767 3 3 0x3d0b cmpb %bl, %dl
768 27 27 0x3d0d jnz 0x000062db <main+11707>
770 //===---------------------------------------------------------------------===//
772 In c99 mode, the preprocessor doesn't like assembly comments like #TRUNCATE.
774 //===---------------------------------------------------------------------===//
776 This could be a single 16-bit load.
779 if ((p[0] == 1) & (p[1] == 2)) return 1;
783 //===---------------------------------------------------------------------===//
785 We should inline lrintf and probably other libc functions.
787 //===---------------------------------------------------------------------===//
789 Start using the flags more. For example, compile:
791 int add_zf(int *x, int y, int a, int b) {
815 int add_zf(int *x, int y, int a, int b) {
839 //===---------------------------------------------------------------------===//
843 int foo(double X) { return isnan(X); }
854 the pxor is not needed, we could compare the value against itself.
856 //===---------------------------------------------------------------------===//
858 These two functions have identical effects:
860 unsigned int f(unsigned int i, unsigned int n) {++i; if (i == n) ++i; return i;}
861 unsigned int f2(unsigned int i, unsigned int n) {++i; i += i == n; return i;}
863 We currently compile them to:
871 jne LBB1_2 #UnifiedReturnBlock
875 LBB1_2: #UnifiedReturnBlock
885 leal 1(%ecx,%eax), %eax
888 both of which are inferior to GCC's:
906 //===---------------------------------------------------------------------===//
914 is currently compiled to:
925 It would be better to produce:
934 This can be applied to any no-return function call that takes no arguments etc.
935 Alternatively, the stack save/restore logic could be shrink-wrapped, producing
946 Both are useful in different situations. Finally, it could be shrink-wrapped
947 and tail called, like this:
954 pop %eax # realign stack.
957 Though this probably isn't worth it.
959 //===---------------------------------------------------------------------===//
961 We need to teach the codegen to convert two-address INC instructions to LEA
962 when the flags are dead. For example, on X86-64, compile:
964 int foo(int A, int B) {
983 ;; X's live range extends beyond the shift, so the register allocator
984 ;; cannot coalesce it with Y. Because of this, a copy needs to be
985 ;; emitted before the shift to save the register value before it is
986 ;; clobbered. However, this copy is not needed if the register
987 ;; allocator turns the shift into an LEA. This also occurs for ADD.
989 ; Check that the shift gets turned into an LEA.
990 ; RUN: llvm-upgrade < %s | llvm-as | llc -march=x86 -x86-asm-syntax=intel | \
991 ; RUN: not grep {mov E.X, E.X}
993 %G = external global int
995 int %test1(int %X, int %Y) {
997 volatile store int %Y, int* %G
998 volatile store int %Z, int* %G
1002 int %test2(int %X) {
1003 %Z = add int %X, 1 ;; inc
1004 volatile store int %Z, int* %G
1008 //===---------------------------------------------------------------------===//
1011 #include <xmmintrin.h>
1012 unsigned test(float f) {
1013 return _mm_cvtsi128_si32( (__m128i) _mm_set_ss( f ));
1018 movss 4(%esp), %xmm0
1022 it should compile to a move from the stack slot directly into eax. DAGCombine
1023 has this xform, but it is currently disabled until the alignment fields of
1024 the load/store nodes are trustworthy.
1026 //===---------------------------------------------------------------------===//
1028 Sometimes it is better to codegen subtractions from a constant (e.g. 7-x) with
1029 a neg instead of a sub instruction. Consider:
1031 int test(char X) { return 7-X; }
1033 we currently produce:
1036 movsbl 4(%esp), %ecx
1040 We would use one fewer register if codegen'd as:
1042 movsbl 4(%esp), %eax
1047 Note that this isn't beneficial if the load can be folded into the sub. In
1048 this case, we want a sub:
1050 int test(int X) { return 7-X; }
1056 //===---------------------------------------------------------------------===//
1061 We get an implicit def on the undef side. If the phi is spilled, we then get:
1065 It should be possible to teach the x86 backend to "fold" the store into the
1066 implicitdef, which just deletes the implicit def.
1068 These instructions should go away:
1070 movaps %xmm1, 192(%esp)
1071 movaps %xmm1, 224(%esp)
1072 movaps %xmm1, 176(%esp)
1074 //===---------------------------------------------------------------------===//
1076 This is a "commutable two-address" register coallescing deficiency:
1078 define <4 x float> @test1(<4 x float> %V) {
1080 %tmp8 = shufflevector <4 x float> %V, <4 x float> undef, <4 x i32> < i32 3, i32 2, i32 1, i32 0 > ; <<4 x float>> [#uses=1]
1081 %add = add <4 x float> %tmp8, %V ; <<4 x float>> [#uses=1]
1082 ret <4 x float> %add
1088 pshufd $27, %xmm0, %xmm1
1096 pshufd $27, %xmm0, %xmm1