New entries.
[oota-llvm.git] / lib / Target / X86 / README.txt
1 //===---------------------------------------------------------------------===//
2 // Random ideas for the X86 backend.
3 //===---------------------------------------------------------------------===//
4
5 Add a MUL2U and MUL2S nodes to represent a multiply that returns both the
6 Hi and Lo parts (combination of MUL and MULH[SU] into one node).  Add this to
7 X86, & make the dag combiner produce it when needed.  This will eliminate one
8 imul from the code generated for:
9
10 long long test(long long X, long long Y) { return X*Y; }
11
12 by using the EAX result from the mul.  We should add a similar node for
13 DIVREM.
14
15 another case is:
16
17 long long test(int X, int Y) { return (long long)X*Y; }
18
19 ... which should only be one imul instruction.
20
21 This can be done with a custom expander, but it would be nice to move this to
22 generic code.
23
24 //===---------------------------------------------------------------------===//
25
26 This should be one DIV/IDIV instruction, not a libcall:
27
28 unsigned test(unsigned long long X, unsigned Y) {
29         return X/Y;
30 }
31
32 This can be done trivially with a custom legalizer.  What about overflow 
33 though?  http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14224
34
35 //===---------------------------------------------------------------------===//
36
37 Improvements to the multiply -> shift/add algorithm:
38 http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01590.html
39
40 //===---------------------------------------------------------------------===//
41
42 Improve code like this (occurs fairly frequently, e.g. in LLVM):
43 long long foo(int x) { return 1LL << x; }
44
45 http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01109.html
46 http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01128.html
47 http://gcc.gnu.org/ml/gcc-patches/2004-09/msg01136.html
48
49 Another useful one would be  ~0ULL >> X and ~0ULL << X.
50
51 One better solution for 1LL << x is:
52         xorl    %eax, %eax
53         xorl    %edx, %edx
54         testb   $32, %cl
55         sete    %al
56         setne   %dl
57         sall    %cl, %eax
58         sall    %cl, %edx
59
60 But that requires good 8-bit subreg support.
61
62 64-bit shifts (in general) expand to really bad code.  Instead of using
63 cmovs, we should expand to a conditional branch like GCC produces.
64
65 //===---------------------------------------------------------------------===//
66
67 Compile this:
68 _Bool f(_Bool a) { return a!=1; }
69
70 into:
71         movzbl  %dil, %eax
72         xorl    $1, %eax
73         ret
74
75 //===---------------------------------------------------------------------===//
76
77 Some isel ideas:
78
79 1. Dynamic programming based approach when compile time if not an
80    issue.
81 2. Code duplication (addressing mode) during isel.
82 3. Other ideas from "Register-Sensitive Selection, Duplication, and
83    Sequencing of Instructions".
84 4. Scheduling for reduced register pressure.  E.g. "Minimum Register 
85    Instruction Sequence Problem: Revisiting Optimal Code Generation for DAGs" 
86    and other related papers.
87    http://citeseer.ist.psu.edu/govindarajan01minimum.html
88
89 //===---------------------------------------------------------------------===//
90
91 Should we promote i16 to i32 to avoid partial register update stalls?
92
93 //===---------------------------------------------------------------------===//
94
95 Leave any_extend as pseudo instruction and hint to register
96 allocator. Delay codegen until post register allocation.
97
98 //===---------------------------------------------------------------------===//
99
100 Count leading zeros and count trailing zeros:
101
102 int clz(int X) { return __builtin_clz(X); }
103 int ctz(int X) { return __builtin_ctz(X); }
104
105 $ gcc t.c -S -o - -O3  -fomit-frame-pointer -masm=intel
106 clz:
107         bsr     %eax, DWORD PTR [%esp+4]
108         xor     %eax, 31
109         ret
110 ctz:
111         bsf     %eax, DWORD PTR [%esp+4]
112         ret
113
114 however, check that these are defined for 0 and 32.  Our intrinsics are, GCC's
115 aren't.
116
117 Another example (use predsimplify to eliminate a select):
118
119 int foo (unsigned long j) {
120   if (j)
121     return __builtin_ffs (j) - 1;
122   else
123     return 0;
124 }
125
126 //===---------------------------------------------------------------------===//
127
128 Use push/pop instructions in prolog/epilog sequences instead of stores off 
129 ESP (certain code size win, perf win on some [which?] processors).
130 Also, it appears icc use push for parameter passing. Need to investigate.
131
132 //===---------------------------------------------------------------------===//
133
134 Only use inc/neg/not instructions on processors where they are faster than
135 add/sub/xor.  They are slower on the P4 due to only updating some processor
136 flags.
137
138 //===---------------------------------------------------------------------===//
139
140 The instruction selector sometimes misses folding a load into a compare.  The
141 pattern is written as (cmp reg, (load p)).  Because the compare isn't 
142 commutative, it is not matched with the load on both sides.  The dag combiner
143 should be made smart enough to cannonicalize the load into the RHS of a compare
144 when it can invert the result of the compare for free.
145
146 //===---------------------------------------------------------------------===//
147
148 How about intrinsics? An example is:
149   *res = _mm_mulhi_epu16(*A, _mm_mul_epu32(*B, *C));
150
151 compiles to
152         pmuludq (%eax), %xmm0
153         movl 8(%esp), %eax
154         movdqa (%eax), %xmm1
155         pmulhuw %xmm0, %xmm1
156
157 The transformation probably requires a X86 specific pass or a DAG combiner
158 target specific hook.
159
160 //===---------------------------------------------------------------------===//
161
162 In many cases, LLVM generates code like this:
163
164 _test:
165         movl 8(%esp), %eax
166         cmpl %eax, 4(%esp)
167         setl %al
168         movzbl %al, %eax
169         ret
170
171 on some processors (which ones?), it is more efficient to do this:
172
173 _test:
174         movl 8(%esp), %ebx
175         xor  %eax, %eax
176         cmpl %ebx, 4(%esp)
177         setl %al
178         ret
179
180 Doing this correctly is tricky though, as the xor clobbers the flags.
181
182 //===---------------------------------------------------------------------===//
183
184 We should generate bts/btr/etc instructions on targets where they are cheap or
185 when codesize is important.  e.g., for:
186
187 void setbit(int *target, int bit) {
188     *target |= (1 << bit);
189 }
190 void clearbit(int *target, int bit) {
191     *target &= ~(1 << bit);
192 }
193
194 //===---------------------------------------------------------------------===//
195
196 Instead of the following for memset char*, 1, 10:
197
198         movl $16843009, 4(%edx)
199         movl $16843009, (%edx)
200         movw $257, 8(%edx)
201
202 It might be better to generate
203
204         movl $16843009, %eax
205         movl %eax, 4(%edx)
206         movl %eax, (%edx)
207         movw al, 8(%edx)
208         
209 when we can spare a register. It reduces code size.
210
211 //===---------------------------------------------------------------------===//
212
213 Evaluate what the best way to codegen sdiv X, (2^C) is.  For X/8, we currently
214 get this:
215
216 int %test1(int %X) {
217         %Y = div int %X, 8
218         ret int %Y
219 }
220
221 _test1:
222         movl 4(%esp), %eax
223         movl %eax, %ecx
224         sarl $31, %ecx
225         shrl $29, %ecx
226         addl %ecx, %eax
227         sarl $3, %eax
228         ret
229
230 GCC knows several different ways to codegen it, one of which is this:
231
232 _test1:
233         movl    4(%esp), %eax
234         cmpl    $-1, %eax
235         leal    7(%eax), %ecx
236         cmovle  %ecx, %eax
237         sarl    $3, %eax
238         ret
239
240 which is probably slower, but it's interesting at least :)
241
242 //===---------------------------------------------------------------------===//
243
244 The first BB of this code:
245
246 declare bool %foo()
247 int %bar() {
248         %V = call bool %foo()
249         br bool %V, label %T, label %F
250 T:
251         ret int 1
252 F:
253         call bool %foo()
254         ret int 12
255 }
256
257 compiles to:
258
259 _bar:
260         subl $12, %esp
261         call L_foo$stub
262         xorb $1, %al
263         testb %al, %al
264         jne LBB_bar_2   # F
265
266 It would be better to emit "cmp %al, 1" than a xor and test.
267
268 //===---------------------------------------------------------------------===//
269
270 Enable X86InstrInfo::convertToThreeAddress().
271
272 //===---------------------------------------------------------------------===//
273
274 We are currently lowering large (1MB+) memmove/memcpy to rep/stosl and rep/movsl
275 We should leave these as libcalls for everything over a much lower threshold,
276 since libc is hand tuned for medium and large mem ops (avoiding RFO for large
277 stores, TLB preheating, etc)
278
279 //===---------------------------------------------------------------------===//
280
281 Optimize this into something reasonable:
282  x * copysign(1.0, y) * copysign(1.0, z)
283
284 //===---------------------------------------------------------------------===//
285
286 Optimize copysign(x, *y) to use an integer load from y.
287
288 //===---------------------------------------------------------------------===//
289
290 %X = weak global int 0
291
292 void %foo(int %N) {
293         %N = cast int %N to uint
294         %tmp.24 = setgt int %N, 0
295         br bool %tmp.24, label %no_exit, label %return
296
297 no_exit:
298         %indvar = phi uint [ 0, %entry ], [ %indvar.next, %no_exit ]
299         %i.0.0 = cast uint %indvar to int
300         volatile store int %i.0.0, int* %X
301         %indvar.next = add uint %indvar, 1
302         %exitcond = seteq uint %indvar.next, %N
303         br bool %exitcond, label %return, label %no_exit
304
305 return:
306         ret void
307 }
308
309 compiles into:
310
311         .text
312         .align  4
313         .globl  _foo
314 _foo:
315         movl 4(%esp), %eax
316         cmpl $1, %eax
317         jl LBB_foo_4    # return
318 LBB_foo_1:      # no_exit.preheader
319         xorl %ecx, %ecx
320 LBB_foo_2:      # no_exit
321         movl L_X$non_lazy_ptr, %edx
322         movl %ecx, (%edx)
323         incl %ecx
324         cmpl %eax, %ecx
325         jne LBB_foo_2   # no_exit
326 LBB_foo_3:      # return.loopexit
327 LBB_foo_4:      # return
328         ret
329
330 We should hoist "movl L_X$non_lazy_ptr, %edx" out of the loop after
331 remateralization is implemented. This can be accomplished with 1) a target
332 dependent LICM pass or 2) makeing SelectDAG represent the whole function. 
333
334 //===---------------------------------------------------------------------===//
335
336 The following tests perform worse with LSR:
337
338 lambda, siod, optimizer-eval, ackermann, hash2, nestedloop, strcat, and Treesor.
339
340 //===---------------------------------------------------------------------===//
341
342 Teach the coalescer to coalesce vregs of different register classes. e.g. FR32 /
343 FR64 to VR128.
344
345 //===---------------------------------------------------------------------===//
346
347 mov $reg, 48(%esp)
348 ...
349 leal 48(%esp), %eax
350 mov %eax, (%esp)
351 call _foo
352
353 Obviously it would have been better for the first mov (or any op) to store
354 directly %esp[0] if there are no other uses.
355
356 //===---------------------------------------------------------------------===//
357
358 Adding to the list of cmp / test poor codegen issues:
359
360 int test(__m128 *A, __m128 *B) {
361   if (_mm_comige_ss(*A, *B))
362     return 3;
363   else
364     return 4;
365 }
366
367 _test:
368         movl 8(%esp), %eax
369         movaps (%eax), %xmm0
370         movl 4(%esp), %eax
371         movaps (%eax), %xmm1
372         comiss %xmm0, %xmm1
373         setae %al
374         movzbl %al, %ecx
375         movl $3, %eax
376         movl $4, %edx
377         cmpl $0, %ecx
378         cmove %edx, %eax
379         ret
380
381 Note the setae, movzbl, cmpl, cmove can be replaced with a single cmovae. There
382 are a number of issues. 1) We are introducing a setcc between the result of the
383 intrisic call and select. 2) The intrinsic is expected to produce a i32 value
384 so a any extend (which becomes a zero extend) is added.
385
386 We probably need some kind of target DAG combine hook to fix this.
387
388 //===---------------------------------------------------------------------===//
389
390 We generate significantly worse code for this than GCC:
391 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21150
392 http://gcc.gnu.org/bugzilla/attachment.cgi?id=8701
393
394 There is also one case we do worse on PPC.
395
396 //===---------------------------------------------------------------------===//
397
398 If shorter, we should use things like:
399 movzwl %ax, %eax
400 instead of:
401 andl $65535, %EAX
402
403 The former can also be used when the two-addressy nature of the 'and' would
404 require a copy to be inserted (in X86InstrInfo::convertToThreeAddress).
405
406 //===---------------------------------------------------------------------===//
407
408 Bad codegen:
409
410 char foo(int x) { return x; }
411
412 _foo:
413         movl 4(%esp), %eax
414         shll $24, %eax
415         sarl $24, %eax
416         ret
417
418 SIGN_EXTEND_INREG can be implemented as (sext (trunc)) to take advantage of 
419 sub-registers.
420
421 //===---------------------------------------------------------------------===//
422
423 Consider this:
424
425 typedef struct pair { float A, B; } pair;
426 void pairtest(pair P, float *FP) {
427         *FP = P.A+P.B;
428 }
429
430 We currently generate this code with llvmgcc4:
431
432 _pairtest:
433         subl $12, %esp
434         movl 20(%esp), %eax
435         movl %eax, 4(%esp)
436         movl 16(%esp), %eax
437         movl %eax, (%esp)
438         movss (%esp), %xmm0
439         addss 4(%esp), %xmm0
440         movl 24(%esp), %eax
441         movss %xmm0, (%eax)
442         addl $12, %esp
443         ret
444
445 we should be able to generate:
446 _pairtest:
447         movss 4(%esp), %xmm0
448         movl 12(%esp), %eax
449         addss 8(%esp), %xmm0
450         movss %xmm0, (%eax)
451         ret
452
453 The issue is that llvmgcc4 is forcing the struct to memory, then passing it as
454 integer chunks.  It does this so that structs like {short,short} are passed in
455 a single 32-bit integer stack slot.  We should handle the safe cases above much
456 nicer, while still handling the hard cases.
457
458 //===---------------------------------------------------------------------===//
459
460 Another instruction selector deficiency:
461
462 void %bar() {
463         %tmp = load int (int)** %foo
464         %tmp = tail call int %tmp( int 3 )
465         ret void
466 }
467
468 _bar:
469         subl $12, %esp
470         movl L_foo$non_lazy_ptr, %eax
471         movl (%eax), %eax
472         call *%eax
473         addl $12, %esp
474         ret
475
476 The current isel scheme will not allow the load to be folded in the call since
477 the load's chain result is read by the callseq_start.
478
479 //===---------------------------------------------------------------------===//
480
481 Don't forget to find a way to squash noop truncates in the JIT environment.
482
483 //===---------------------------------------------------------------------===//
484
485 Implement anyext in the same manner as truncate that would allow them to be
486 eliminated.
487
488 //===---------------------------------------------------------------------===//
489
490 How about implementing truncate / anyext as a property of machine instruction
491 operand? i.e. Print as 32-bit super-class register / 16-bit sub-class register.
492 Do this for the cases where a truncate / anyext is guaranteed to be eliminated.
493 For IA32 that is truncate from 32 to 16 and anyext from 16 to 32.
494
495 //===---------------------------------------------------------------------===//
496
497 For this:
498
499 int test(int a)
500 {
501   return a * 3;
502 }
503
504 We currently emits
505         imull $3, 4(%esp), %eax
506
507 Perhaps this is what we really should generate is? Is imull three or four
508 cycles? Note: ICC generates this:
509         movl    4(%esp), %eax
510         leal    (%eax,%eax,2), %eax
511
512 The current instruction priority is based on pattern complexity. The former is
513 more "complex" because it folds a load so the latter will not be emitted.
514
515 Perhaps we should use AddedComplexity to give LEA32r a higher priority? We
516 should always try to match LEA first since the LEA matching code does some
517 estimate to determine whether the match is profitable.
518
519 However, if we care more about code size, then imull is better. It's two bytes
520 shorter than movl + leal.
521
522 //===---------------------------------------------------------------------===//
523
524 Implement CTTZ, CTLZ with bsf and bsr.
525
526 //===---------------------------------------------------------------------===//
527
528 It appears gcc place string data with linkonce linkage in
529 .section __TEXT,__const_coal,coalesced instead of
530 .section __DATA,__const_coal,coalesced.
531 Take a look at darwin.h, there are other Darwin assembler directives that we
532 do not make use of.
533
534 //===---------------------------------------------------------------------===//
535
536 We should handle __attribute__ ((__visibility__ ("hidden"))).
537
538 //===---------------------------------------------------------------------===//
539
540 int %foo(int* %a, int %t) {
541 entry:
542         br label %cond_true
543
544 cond_true:              ; preds = %cond_true, %entry
545         %x.0.0 = phi int [ 0, %entry ], [ %tmp9, %cond_true ]  
546         %t_addr.0.0 = phi int [ %t, %entry ], [ %tmp7, %cond_true ]
547         %tmp2 = getelementptr int* %a, int %x.0.0              
548         %tmp3 = load int* %tmp2         ; <int> [#uses=1]
549         %tmp5 = add int %t_addr.0.0, %x.0.0             ; <int> [#uses=1]
550         %tmp7 = add int %tmp5, %tmp3            ; <int> [#uses=2]
551         %tmp9 = add int %x.0.0, 1               ; <int> [#uses=2]
552         %tmp = setgt int %tmp9, 39              ; <bool> [#uses=1]
553         br bool %tmp, label %bb12, label %cond_true
554
555 bb12:           ; preds = %cond_true
556         ret int %tmp7
557 }
558
559 is pessimized by -loop-reduce and -indvars
560
561 //===---------------------------------------------------------------------===//
562
563 u32 to float conversion improvement:
564
565 float uint32_2_float( unsigned u ) {
566   float fl = (int) (u & 0xffff);
567   float fh = (int) (u >> 16);
568   fh *= 0x1.0p16f;
569   return fh + fl;
570 }
571
572 00000000        subl    $0x04,%esp
573 00000003        movl    0x08(%esp,1),%eax
574 00000007        movl    %eax,%ecx
575 00000009        shrl    $0x10,%ecx
576 0000000c        cvtsi2ss        %ecx,%xmm0
577 00000010        andl    $0x0000ffff,%eax
578 00000015        cvtsi2ss        %eax,%xmm1
579 00000019        mulss   0x00000078,%xmm0
580 00000021        addss   %xmm1,%xmm0
581 00000025        movss   %xmm0,(%esp,1)
582 0000002a        flds    (%esp,1)
583 0000002d        addl    $0x04,%esp
584 00000030        ret
585
586 //===---------------------------------------------------------------------===//
587
588 When using fastcc abi, align stack slot of argument of type double on 8 byte
589 boundary to improve performance.
590
591 //===---------------------------------------------------------------------===//
592
593 Codegen:
594
595 int f(int a, int b) {
596   if (a == 4 || a == 6)
597     b++;
598   return b;
599 }
600
601
602 as:
603
604 or eax, 2
605 cmp eax, 6
606 jz label
607
608 //===---------------------------------------------------------------------===//
609
610 GCC's ix86_expand_int_movcc function (in i386.c) has a ton of interesting
611 simplifications for integer "x cmp y ? a : b".  For example, instead of:
612
613 int G;
614 void f(int X, int Y) {
615   G = X < 0 ? 14 : 13;
616 }
617
618 compiling to:
619
620 _f:
621         movl $14, %eax
622         movl $13, %ecx
623         movl 4(%esp), %edx
624         testl %edx, %edx
625         cmovl %eax, %ecx
626         movl %ecx, _G
627         ret
628
629 it could be:
630 _f:
631         movl    4(%esp), %eax
632         sarl    $31, %eax
633         notl    %eax
634         addl    $14, %eax
635         movl    %eax, _G
636         ret
637
638 etc.
639
640 //===---------------------------------------------------------------------===//
641
642 Currently we don't have elimination of redundant stack manipulations. Consider
643 the code:
644
645 int %main() {
646 entry:
647         call fastcc void %test1( )
648         call fastcc void %test2( sbyte* cast (void ()* %test1 to sbyte*) )
649         ret int 0
650 }
651
652 declare fastcc void %test1()
653
654 declare fastcc void %test2(sbyte*)
655
656
657 This currently compiles to:
658
659         subl $16, %esp
660         call _test5
661         addl $12, %esp
662         subl $16, %esp
663         movl $_test5, (%esp)
664         call _test6
665         addl $12, %esp
666
667 The add\sub pair is really unneeded here.
668
669 //===---------------------------------------------------------------------===//
670
671 We generate really bad code in some cases due to lowering SETCC/SELECT at 
672 legalize time, which prevents the post-legalize dag combine pass from
673 understanding the code.  As a silly example, this prevents us from folding 
674 stuff like this:
675
676 bool %test(ulong %x) {
677   %tmp = setlt ulong %x, 4294967296
678   ret bool %tmp
679 }
680
681 into x.h == 0
682
683 //===---------------------------------------------------------------------===//
684
685 We currently compile sign_extend_inreg into two shifts:
686
687 long foo(long X) {
688   return (long)(signed char)X;
689 }
690
691 becomes:
692
693 _foo:
694         movl 4(%esp), %eax
695         shll $24, %eax
696         sarl $24, %eax
697         ret
698
699 This could be:
700
701 _foo:
702         movsbl  4(%esp),%eax
703         ret
704
705 //===---------------------------------------------------------------------===//
706
707 Consider the expansion of:
708
709 uint %test3(uint %X) {
710         %tmp1 = rem uint %X, 255
711         ret uint %tmp1
712 }
713
714 Currently it compiles to:
715
716 ...
717         movl $2155905153, %ecx
718         movl 8(%esp), %esi
719         movl %esi, %eax
720         mull %ecx
721 ...
722
723 This could be "reassociated" into:
724
725         movl $2155905153, %eax
726         movl 8(%esp), %ecx
727         mull %ecx
728
729 to avoid the copy.  In fact, the existing two-address stuff would do this
730 except that mul isn't a commutative 2-addr instruction.  I guess this has
731 to be done at isel time based on the #uses to mul?
732
733 //===---------------------------------------------------------------------===//
734
735 Make sure the instruction which starts a loop does not cross a cacheline
736 boundary. This requires knowning the exact length of each machine instruction.
737 That is somewhat complicated, but doable. Example 256.bzip2:
738
739 In the new trace, the hot loop has an instruction which crosses a cacheline
740 boundary.  In addition to potential cache misses, this can't help decoding as I
741 imagine there has to be some kind of complicated decoder reset and realignment
742 to grab the bytes from the next cacheline.
743
744 532  532 0x3cfc movb     (1809(%esp, %esi), %bl   <<<--- spans 2 64 byte lines
745 942  942 0x3d03 movl     %dh, (1809(%esp, %esi)                                                                          
746 937  937 0x3d0a incl     %esi                           
747 3    3   0x3d0b cmpb     %bl, %dl                                               
748 27   27  0x3d0d jnz      0x000062db <main+11707>
749
750 //===---------------------------------------------------------------------===//
751
752 In c99 mode, the preprocessor doesn't like assembly comments like #TRUNCATE.