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