lib/Target/X86/README.txt

   1 //===---------------------------------------------------------------------===//
   2 // Random ideas for the X86 backend.
   3 //===---------------------------------------------------------------------===//
   4
   5 Missing features:
   6   - Support for SSE4: http://www.intel.com/software/penryn
   7 http://softwarecommunity.intel.com/isn/Downloads/Intel%20SSE4%20Programming%20Reference.pdf
   8   - support for 3DNow!
   9   - weird abis?
  10
  11 //===---------------------------------------------------------------------===//
  12
  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:
  17
  18 long long test(long long X, long long Y) { return X*Y; }
  19
  20 by using the EAX result from the mul.  We should add a similar node for
  21 DIVREM.
  22
  23 another case is:
  24
  25 long long test(int X, int Y) { return (long long)X*Y; }
  26
  27 ... which should only be one imul instruction.
  28
  29 or:
  30
  31 unsigned long long int t2(unsigned int a, unsigned int b) {
  32        return (unsigned long long)a * b;
  33 }
  34
  35 ... which should be one mul instruction.
  36
  37
  38 This can be done with a custom expander, but it would be nice to move this to
  39 generic code.
  40
  41 //===---------------------------------------------------------------------===//
  42
  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.
  48
  49 //===---------------------------------------------------------------------===//
  50
  51 This should be one DIV/IDIV instruction, not a libcall:
  52
  53 unsigned test(unsigned long long X, unsigned Y) {
  54         return X/Y;
  55 }
  56
  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
  59
  60 //===---------------------------------------------------------------------===//
  61
  62 Improvements to the multiply -> shift/add algorithm:
  63 http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01590.html
  64
  65 //===---------------------------------------------------------------------===//
  66
  67 Improve code like this (occurs fairly frequently, e.g. in LLVM):
  68 long long foo(int x) { return 1LL << x; }
  69
  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
  73
  74 Another useful one would be  ~0ULL >> X and ~0ULL << X.
  75
  76 One better solution for 1LL << x is:
  77         xorl    %eax, %eax
  78         xorl    %edx, %edx
  79         testb   $32, %cl
  80         sete    %al
  81         setne   %dl
  82         sall    %cl, %eax
  83         sall    %cl, %edx
  84
  85 But that requires good 8-bit subreg support.
  86
  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.
  89
  90 //===---------------------------------------------------------------------===//
  91
  92 Compile this:
  93 _Bool f(_Bool a) { return a!=1; }
  94
  95 into:
  96         movzbl  %dil, %eax
  97         xorl    $1, %eax
  98         ret
  99
 100 //===---------------------------------------------------------------------===//
 101
 102 Some isel ideas:
 103
 104 1. Dynamic programming based approach when compile time if not an
 105    issue.
 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
 113
 114 //===---------------------------------------------------------------------===//
 115
 116 Should we promote i16 to i32 to avoid partial register update stalls?
 117
 118 //===---------------------------------------------------------------------===//
 119
 120 Leave any_extend as pseudo instruction and hint to register
 121 allocator. Delay codegen until post register allocation.
 122
 123 //===---------------------------------------------------------------------===//
 124
 125 Count leading zeros and count trailing zeros:
 126
 127 int clz(int X) { return __builtin_clz(X); }
 128 int ctz(int X) { return __builtin_ctz(X); }
 129
 130 $ gcc t.c -S -o - -O3  -fomit-frame-pointer -masm=intel
 131 clz:
 132         bsr     %eax, DWORD PTR [%esp+4]
 133         xor     %eax, 31
 134         ret
 135 ctz:
 136         bsf     %eax, DWORD PTR [%esp+4]
 137         ret
 138
 139 however, check that these are defined for 0 and 32.  Our intrinsics are, GCC's
 140 aren't.
 141
 142 Another example (use predsimplify to eliminate a select):
 143
 144 int foo (unsigned long j) {
 145   if (j)
 146     return __builtin_ffs (j) - 1;
 147   else
 148     return 0;
 149 }
 150
 151 //===---------------------------------------------------------------------===//
 152
 153 It appears icc use push for parameter passing. Need to investigate.
 154
 155 //===---------------------------------------------------------------------===//
 156
 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
 159 flags.
 160
 161 //===---------------------------------------------------------------------===//
 162
 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.
 168
 169 //===---------------------------------------------------------------------===//
 170
 171 How about intrinsics? An example is:
 172   *res = _mm_mulhi_epu16(*A, _mm_mul_epu32(*B, *C));
 173
 174 compiles to
 175         pmuludq (%eax), %xmm0
 176         movl 8(%esp), %eax
 177         movdqa (%eax), %xmm1
 178         pmulhuw %xmm0, %xmm1
 179
 180 The transformation probably requires a X86 specific pass or a DAG combiner
 181 target specific hook.
 182
 183 //===---------------------------------------------------------------------===//
 184
 185 In many cases, LLVM generates code like this:
 186
 187 _test:
 188         movl 8(%esp), %eax
 189         cmpl %eax, 4(%esp)
 190         setl %al
 191         movzbl %al, %eax
 192         ret
 193
 194 on some processors (which ones?), it is more efficient to do this:
 195
 196 _test:
 197         movl 8(%esp), %ebx
 198         xor  %eax, %eax
 199         cmpl %ebx, 4(%esp)
 200         setl %al
 201         ret
 202
 203 Doing this correctly is tricky though, as the xor clobbers the flags.
 204
 205 //===---------------------------------------------------------------------===//
 206
 207 We should generate bts/btr/etc instructions on targets where they are cheap or
 208 when codesize is important.  e.g., for:
 209
 210 void setbit(int *target, int bit) {
 211     *target |= (1 << bit);
 212 }
 213 void clearbit(int *target, int bit) {
 214     *target &= ~(1 << bit);
 215 }
 216
 217 //===---------------------------------------------------------------------===//
 218
 219 Instead of the following for memset char*, 1, 10:
 220
 221         movl $16843009, 4(%edx)
 222         movl $16843009, (%edx)
 223         movw $257, 8(%edx)
 224
 225 It might be better to generate
 226
 227         movl $16843009, %eax
 228         movl %eax, 4(%edx)
 229         movl %eax, (%edx)
 230         movw al, 8(%edx)
 231
 232 when we can spare a register. It reduces code size.
 233
 234 //===---------------------------------------------------------------------===//
 235
 236 Evaluate what the best way to codegen sdiv X, (2^C) is.  For X/8, we currently
 237 get this:
 238
 239 int %test1(int %X) {
 240         %Y = div int %X, 8
 241         ret int %Y
 242 }
 243
 244 _test1:
 245         movl 4(%esp), %eax
 246         movl %eax, %ecx
 247         sarl $31, %ecx
 248         shrl $29, %ecx
 249         addl %ecx, %eax
 250         sarl $3, %eax
 251         ret
 252
 253 GCC knows several different ways to codegen it, one of which is this:
 254
 255 _test1:
 256         movl    4(%esp), %eax
 257         cmpl    $-1, %eax
 258         leal    7(%eax), %ecx
 259         cmovle  %ecx, %eax
 260         sarl    $3, %eax
 261         ret
 262
 263 which is probably slower, but it's interesting at least :)
 264
 265 //===---------------------------------------------------------------------===//
 266
 267 The first BB of this code:
 268
 269 declare bool %foo()
 270 int %bar() {
 271         %V = call bool %foo()
 272         br bool %V, label %T, label %F
 273 T:
 274         ret int 1
 275 F:
 276         call bool %foo()
 277         ret int 12
 278 }
 279
 280 compiles to:
 281
 282 _bar:
 283         subl $12, %esp
 284         call L_foo$stub
 285         xorb $1, %al
 286         testb %al, %al
 287         jne LBB_bar_2   # F
 288
 289 It would be better to emit "cmp %al, 1" than a xor and test.
 290
 291 //===---------------------------------------------------------------------===//
 292
 293 Enable X86InstrInfo::convertToThreeAddress().
 294
 295 //===---------------------------------------------------------------------===//
 296
 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)
 301
 302 //===---------------------------------------------------------------------===//
 303
 304 Optimize this into something reasonable:
 305  x * copysign(1.0, y) * copysign(1.0, z)
 306
 307 //===---------------------------------------------------------------------===//
 308
 309 Optimize copysign(x, *y) to use an integer load from y.
 310
 311 //===---------------------------------------------------------------------===//
 312
 313 %X = weak global int 0
 314
 315 void %foo(int %N) {
 316         %N = cast int %N to uint
 317         %tmp.24 = setgt int %N, 0
 318         br bool %tmp.24, label %no_exit, label %return
 319
 320 no_exit:
 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
 327
 328 return:
 329         ret void
 330 }
 331
 332 compiles into:
 333
 334         .text
 335         .align  4
 336         .globl  _foo
 337 _foo:
 338         movl 4(%esp), %eax
 339         cmpl $1, %eax
 340         jl LBB_foo_4    # return
 341 LBB_foo_1:      # no_exit.preheader
 342         xorl %ecx, %ecx
 343 LBB_foo_2:      # no_exit
 344         movl L_X$non_lazy_ptr, %edx
 345         movl %ecx, (%edx)
 346         incl %ecx
 347         cmpl %eax, %ecx
 348         jne LBB_foo_2   # no_exit
 349 LBB_foo_3:      # return.loopexit
 350 LBB_foo_4:      # return
 351         ret
 352
 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.
 356
 357 //===---------------------------------------------------------------------===//
 358
 359 The following tests perform worse with LSR:
 360
 361 lambda, siod, optimizer-eval, ackermann, hash2, nestedloop, strcat, and Treesor.
 362
 363 //===---------------------------------------------------------------------===//
 364
 365 We are generating far worse code than gcc:
 366
 367 volatile short X, Y;
 368
 369 void foo(int N) {
 370   int i;
 371   for (i = 0; i < N; i++) { X = i; Y = i*4; }
 372 }
 373
 374 LBB1_1: #bb.preheader
 375         xorl %ecx, %ecx
 376         xorw %dx, %dx
 377 LBB1_2: #bb
 378         movl L_X$non_lazy_ptr, %esi
 379         movw %dx, (%esi)
 380         movw %dx, %si
 381         shlw $2, %si
 382         movl L_Y$non_lazy_ptr, %edi
 383         movw %si, (%edi)
 384         incl %ecx
 385         incw %dx
 386         cmpl %eax, %ecx
 387         jne LBB1_2      #bb
 388
 389 vs.
 390
 391         xorl    %edx, %edx
 392         movl    L_X$non_lazy_ptr-"L00000000001$pb"(%ebx), %esi
 393         movl    L_Y$non_lazy_ptr-"L00000000001$pb"(%ebx), %ecx
 394 L4:
 395         movw    %dx, (%esi)
 396         leal    0(,%edx,4), %eax
 397         movw    %ax, (%ecx)
 398         addl    $1, %edx
 399         cmpl    %edx, %edi
 400         jne     L4
 401
 402 There are 3 issues:
 403
 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.
 407
 408 //===---------------------------------------------------------------------===//
 409
 410 Teach the coalescer to coalesce vregs of different register classes. e.g. FR32 /
 411 FR64 to VR128.
 412
 413 //===---------------------------------------------------------------------===//
 414
 415 mov $reg, 48(%esp)
 416 ...
 417 leal 48(%esp), %eax
 418 mov %eax, (%esp)
 419 call _foo
 420
 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.
 423
 424 //===---------------------------------------------------------------------===//
 425
 426 Adding to the list of cmp / test poor codegen issues:
 427
 428 int test(__m128 *A, __m128 *B) {
 429   if (_mm_comige_ss(*A, *B))
 430     return 3;
 431   else
 432     return 4;
 433 }
 434
 435 _test:
 436         movl 8(%esp), %eax
 437         movaps (%eax), %xmm0
 438         movl 4(%esp), %eax
 439         movaps (%eax), %xmm1
 440         comiss %xmm0, %xmm1
 441         setae %al
 442         movzbl %al, %ecx
 443         movl $3, %eax
 444         movl $4, %edx
 445         cmpl $0, %ecx
 446         cmove %edx, %eax
 447         ret
 448
 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.
 453
 454 We probably need some kind of target DAG combine hook to fix this.
 455
 456 //===---------------------------------------------------------------------===//
 457
 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
 461
 462 There is also one case we do worse on PPC.
 463
 464 //===---------------------------------------------------------------------===//
 465
 466 If shorter, we should use things like:
 467 movzwl %ax, %eax
 468 instead of:
 469 andl $65535, %EAX
 470
 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).
 473
 474 //===---------------------------------------------------------------------===//
 475
 476 Consider this:
 477
 478 typedef struct pair { float A, B; } pair;
 479 void pairtest(pair P, float *FP) {
 480         *FP = P.A+P.B;
 481 }
 482
 483 We currently generate this code with llvmgcc4:
 484
 485 _pairtest:
 486         movl 8(%esp), %eax
 487         movl 4(%esp), %ecx
 488         movd %eax, %xmm0
 489         movd %ecx, %xmm1
 490         addss %xmm0, %xmm1
 491         movl 12(%esp), %eax
 492         movss %xmm1, (%eax)
 493         ret
 494
 495 we should be able to generate:
 496 _pairtest:
 497         movss 4(%esp), %xmm0
 498         movl 12(%esp), %eax
 499         addss 8(%esp), %xmm0
 500         movss %xmm0, (%eax)
 501         ret
 502
 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.
 507
 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).
 511
 512 //===---------------------------------------------------------------------===//
 513
 514 Another instruction selector deficiency:
 515
 516 void %bar() {
 517         %tmp = load int (int)** %foo
 518         %tmp = tail call int %tmp( int 3 )
 519         ret void
 520 }
 521
 522 _bar:
 523         subl $12, %esp
 524         movl L_foo$non_lazy_ptr, %eax
 525         movl (%eax), %eax
 526         call *%eax
 527         addl $12, %esp
 528         ret
 529
 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.
 532
 533 //===---------------------------------------------------------------------===//
 534
 535 Don't forget to find a way to squash noop truncates in the JIT environment.
 536
 537 //===---------------------------------------------------------------------===//
 538
 539 Implement anyext in the same manner as truncate that would allow them to be
 540 eliminated.
 541
 542 //===---------------------------------------------------------------------===//
 543
 544 How about implementing truncate / anyext as a property of machine instruction
 545 operand? i.e. Print as 32-bit super-class register / 16-bit sub-class register.
 546 Do this for the cases where a truncate / anyext is guaranteed to be eliminated.
 547 For IA32 that is truncate from 32 to 16 and anyext from 16 to 32.
 548
 549 //===---------------------------------------------------------------------===//
 550
 551 For this:
 552
 553 int test(int a)
 554 {
 555   return a * 3;
 556 }
 557
 558 We currently emits
 559         imull $3, 4(%esp), %eax
 560
 561 Perhaps this is what we really should generate is? Is imull three or four
 562 cycles? Note: ICC generates this:
 563         movl    4(%esp), %eax
 564         leal    (%eax,%eax,2), %eax
 565
 566 The current instruction priority is based on pattern complexity. The former is
 567 more "complex" because it folds a load so the latter will not be emitted.
 568
 569 Perhaps we should use AddedComplexity to give LEA32r a higher priority? We
 570 should always try to match LEA first since the LEA matching code does some
 571 estimate to determine whether the match is profitable.
 572
 573 However, if we care more about code size, then imull is better. It's two bytes
 574 shorter than movl + leal.
 575
 576 //===---------------------------------------------------------------------===//
 577
 578 Implement CTTZ, CTLZ with bsf and bsr.
 579
 580 //===---------------------------------------------------------------------===//
 581
 582 It appears gcc place string data with linkonce linkage in
 583 .section __TEXT,__const_coal,coalesced instead of
 584 .section __DATA,__const_coal,coalesced.
 585 Take a look at darwin.h, there are other Darwin assembler directives that we
 586 do not make use of.
 587
 588 //===---------------------------------------------------------------------===//
 589
 590 int %foo(int* %a, int %t) {
 591 entry:
 592         br label %cond_true
 593
 594 cond_true:              ; preds = %cond_true, %entry
 595         %x.0.0 = phi int [ 0, %entry ], [ %tmp9, %cond_true ]
 596         %t_addr.0.0 = phi int [ %t, %entry ], [ %tmp7, %cond_true ]
 597         %tmp2 = getelementptr int* %a, int %x.0.0
 598         %tmp3 = load int* %tmp2         ; <int> [#uses=1]
 599         %tmp5 = add int %t_addr.0.0, %x.0.0             ; <int> [#uses=1]
 600         %tmp7 = add int %tmp5, %tmp3            ; <int> [#uses=2]
 601         %tmp9 = add int %x.0.0, 1               ; <int> [#uses=2]
 602         %tmp = setgt int %tmp9, 39              ; <bool> [#uses=1]
 603         br bool %tmp, label %bb12, label %cond_true
 604
 605 bb12:           ; preds = %cond_true
 606         ret int %tmp7
 607 }
 608
 609 is pessimized by -loop-reduce and -indvars
 610
 611 //===---------------------------------------------------------------------===//
 612
 613 u32 to float conversion improvement:
 614
 615 float uint32_2_float( unsigned u ) {
 616   float fl = (int) (u & 0xffff);
 617   float fh = (int) (u >> 16);
 618   fh *= 0x1.0p16f;
 619   return fh + fl;
 620 }
 621
 622 00000000        subl    $0x04,%esp
 623 00000003        movl    0x08(%esp,1),%eax
 624 00000007        movl    %eax,%ecx
 625 00000009        shrl    $0x10,%ecx
 626 0000000c        cvtsi2ss        %ecx,%xmm0
 627 00000010        andl    $0x0000ffff,%eax
 628 00000015        cvtsi2ss        %eax,%xmm1
 629 00000019        mulss   0x00000078,%xmm0
 630 00000021        addss   %xmm1,%xmm0
 631 00000025        movss   %xmm0,(%esp,1)
 632 0000002a        flds    (%esp,1)
 633 0000002d        addl    $0x04,%esp
 634 00000030        ret
 635
 636 //===---------------------------------------------------------------------===//
 637
 638 When using fastcc abi, align stack slot of argument of type double on 8 byte
 639 boundary to improve performance.
 640
 641 //===---------------------------------------------------------------------===//
 642
 643 Codegen:
 644
 645 int f(int a, int b) {
 646   if (a == 4 || a == 6)
 647     b++;
 648   return b;
 649 }
 650
 651
 652 as:
 653
 654 or eax, 2
 655 cmp eax, 6
 656 jz label
 657
 658 //===---------------------------------------------------------------------===//
 659
 660 GCC's ix86_expand_int_movcc function (in i386.c) has a ton of interesting
 661 simplifications for integer "x cmp y ? a : b".  For example, instead of:
 662
 663 int G;
 664 void f(int X, int Y) {
 665   G = X < 0 ? 14 : 13;
 666 }
 667
 668 compiling to:
 669
 670 _f:
 671         movl $14, %eax
 672         movl $13, %ecx
 673         movl 4(%esp), %edx
 674         testl %edx, %edx
 675         cmovl %eax, %ecx
 676         movl %ecx, _G
 677         ret
 678
 679 it could be:
 680 _f:
 681         movl    4(%esp), %eax
 682         sarl    $31, %eax
 683         notl    %eax
 684         addl    $14, %eax
 685         movl    %eax, _G
 686         ret
 687
 688 etc.
 689
 690 //===---------------------------------------------------------------------===//
 691
 692 Currently we don't have elimination of redundant stack manipulations. Consider
 693 the code:
 694
 695 int %main() {
 696 entry:
 697         call fastcc void %test1( )
 698         call fastcc void %test2( sbyte* cast (void ()* %test1 to sbyte*) )
 699         ret int 0
 700 }
 701
 702 declare fastcc void %test1()
 703
 704 declare fastcc void %test2(sbyte*)
 705
 706
 707 This currently compiles to:
 708
 709         subl $16, %esp
 710         call _test5
 711         addl $12, %esp
 712         subl $16, %esp
 713         movl $_test5, (%esp)
 714         call _test6
 715         addl $12, %esp
 716
 717 The add\sub pair is really unneeded here.
 718
 719 //===---------------------------------------------------------------------===//
 720
 721 We currently compile sign_extend_inreg into two shifts:
 722
 723 long foo(long X) {
 724   return (long)(signed char)X;
 725 }
 726
 727 becomes:
 728
 729 _foo:
 730         movl 4(%esp), %eax
 731         shll $24, %eax
 732         sarl $24, %eax
 733         ret
 734
 735 This could be:
 736
 737 _foo:
 738         movsbl  4(%esp),%eax
 739         ret
 740
 741 //===---------------------------------------------------------------------===//
 742
 743 Consider the expansion of:
 744
 745 uint %test3(uint %X) {
 746         %tmp1 = rem uint %X, 255
 747         ret uint %tmp1
 748 }
 749
 750 Currently it compiles to:
 751
 752 ...
 753         movl $2155905153, %ecx
 754         movl 8(%esp), %esi
 755         movl %esi, %eax
 756         mull %ecx
 757 ...
 758
 759 This could be "reassociated" into:
 760
 761         movl $2155905153, %eax
 762         movl 8(%esp), %ecx
 763         mull %ecx
 764
 765 to avoid the copy.  In fact, the existing two-address stuff would do this
 766 except that mul isn't a commutative 2-addr instruction.  I guess this has
 767 to be done at isel time based on the #uses to mul?
 768
 769 //===---------------------------------------------------------------------===//
 770
 771 Make sure the instruction which starts a loop does not cross a cacheline
 772 boundary. This requires knowning the exact length of each machine instruction.
 773 That is somewhat complicated, but doable. Example 256.bzip2:
 774
 775 In the new trace, the hot loop has an instruction which crosses a cacheline
 776 boundary.  In addition to potential cache misses, this can't help decoding as I
 777 imagine there has to be some kind of complicated decoder reset and realignment
 778 to grab the bytes from the next cacheline.
 779
 780 532  532 0x3cfc movb     (1809(%esp, %esi), %bl   <<<--- spans 2 64 byte lines
 781 942  942 0x3d03 movl     %dh, (1809(%esp, %esi)
 782 937  937 0x3d0a incl     %esi
 783 3    3   0x3d0b cmpb     %bl, %dl
 784 27   27  0x3d0d jnz      0x000062db <main+11707>
 785
 786 //===---------------------------------------------------------------------===//
 787
 788 In c99 mode, the preprocessor doesn't like assembly comments like #TRUNCATE.
 789
 790 //===---------------------------------------------------------------------===//
 791
 792 This could be a single 16-bit load.
 793
 794 int f(char *p) {
 795     if ((p[0] == 1) & (p[1] == 2)) return 1;
 796     return 0;
 797 }
 798
 799 //===---------------------------------------------------------------------===//
 800
 801 We should inline lrintf and probably other libc functions.
 802
 803 //===---------------------------------------------------------------------===//
 804
 805 Start using the flags more.  For example, compile:
 806
 807 int add_zf(int *x, int y, int a, int b) {
 808      if ((*x += y) == 0)
 809           return a;
 810      else
 811           return b;
 812 }
 813
 814 to:
 815        addl    %esi, (%rdi)
 816        movl    %edx, %eax
 817        cmovne  %ecx, %eax
 818        ret
 819 instead of:
 820
 821 _add_zf:
 822         addl (%rdi), %esi
 823         movl %esi, (%rdi)
 824         testl %esi, %esi
 825         cmove %edx, %ecx
 826         movl %ecx, %eax
 827         ret
 828
 829 and:
 830
 831 int add_zf(int *x, int y, int a, int b) {
 832      if ((*x + y) < 0)
 833           return a;
 834      else
 835           return b;
 836 }
 837
 838 to:
 839
 840 add_zf:
 841         addl    (%rdi), %esi
 842         movl    %edx, %eax
 843         cmovns  %ecx, %eax
 844         ret
 845
 846 instead of:
 847
 848 _add_zf:
 849         addl (%rdi), %esi
 850         testl %esi, %esi
 851         cmovs %edx, %ecx
 852         movl %ecx, %eax
 853         ret
 854
 855 //===---------------------------------------------------------------------===//
 856
 857 This:
 858 #include <math.h>
 859 int foo(double X) { return isnan(X); }
 860
 861 compiles to (-m64):
 862
 863 _foo:
 864         pxor %xmm1, %xmm1
 865         ucomisd %xmm1, %xmm0
 866         setp %al
 867         movzbl %al, %eax
 868         ret
 869
 870 the pxor is not needed, we could compare the value against itself.
 871
 872 //===---------------------------------------------------------------------===//
 873
 874 These two functions have identical effects:
 875
 876 unsigned int f(unsigned int i, unsigned int n) {++i; if (i == n) ++i; return i;}
 877 unsigned int f2(unsigned int i, unsigned int n) {++i; i += i == n; return i;}
 878
 879 We currently compile them to:
 880
 881 _f:
 882         movl 4(%esp), %eax
 883         movl %eax, %ecx
 884         incl %ecx
 885         movl 8(%esp), %edx
 886         cmpl %edx, %ecx
 887         jne LBB1_2      #UnifiedReturnBlock
 888 LBB1_1: #cond_true
 889         addl $2, %eax
 890         ret
 891 LBB1_2: #UnifiedReturnBlock
 892         movl %ecx, %eax
 893         ret
 894 _f2:
 895         movl 4(%esp), %eax
 896         movl %eax, %ecx
 897         incl %ecx
 898         cmpl 8(%esp), %ecx
 899         sete %cl
 900         movzbl %cl, %ecx
 901         leal 1(%ecx,%eax), %eax
 902         ret
 903
 904 both of which are inferior to GCC's:
 905
 906 _f:
 907         movl    4(%esp), %edx
 908         leal    1(%edx), %eax
 909         addl    $2, %edx
 910         cmpl    8(%esp), %eax
 911         cmove   %edx, %eax
 912         ret
 913 _f2:
 914         movl    4(%esp), %eax
 915         addl    $1, %eax
 916         xorl    %edx, %edx
 917         cmpl    8(%esp), %eax
 918         sete    %dl
 919         addl    %edx, %eax
 920         ret
 921
 922 //===---------------------------------------------------------------------===//
 923
 924 This code:
 925
 926 void test(int X) {
 927   if (X) abort();
 928 }
 929
 930 is currently compiled to:
 931
 932 _test:
 933         subl $12, %esp
 934         cmpl $0, 16(%esp)
 935         jne LBB1_1
 936         addl $12, %esp
 937         ret
 938 LBB1_1:
 939         call L_abort$stub
 940
 941 It would be better to produce:
 942
 943 _test:
 944         subl $12, %esp
 945         cmpl $0, 16(%esp)
 946         jne L_abort$stub
 947         addl $12, %esp
 948         ret
 949
 950 This can be applied to any no-return function call that takes no arguments etc.
 951 Alternatively, the stack save/restore logic could be shrink-wrapped, producing
 952 something like this:
 953
 954 _test:
 955         cmpl $0, 4(%esp)
 956         jne LBB1_1
 957         ret
 958 LBB1_1:
 959         subl $12, %esp
 960         call L_abort$stub
 961
 962 Both are useful in different situations.  Finally, it could be shrink-wrapped
 963 and tail called, like this:
 964
 965 _test:
 966         cmpl $0, 4(%esp)
 967         jne LBB1_1
 968         ret
 969 LBB1_1:
 970         pop %eax   # realign stack.
 971         call L_abort$stub
 972
 973 Though this probably isn't worth it.
 974
 975 //===---------------------------------------------------------------------===//
 976
 977 We need to teach the codegen to convert two-address INC instructions to LEA
 978 when the flags are dead.  For example, on X86-64, compile:
 979
 980 int foo(int A, int B) {
 981   return A+1;
 982 }
 983
 984 to:
 985
 986 _foo:
 987         leal    1(%edi), %eax
 988         ret
 989
 990 instead of:
 991
 992 _foo:
 993         incl %edi
 994         movl %edi, %eax
 995         ret
 996
 997 Another example is:
 998
 999 ;; X's live range extends beyond the shift, so the register allocator
1000 ;; cannot coalesce it with Y.  Because of this, a copy needs to be
1001 ;; emitted before the shift to save the register value before it is
1002 ;; clobbered.  However, this copy is not needed if the register
1003 ;; allocator turns the shift into an LEA.  This also occurs for ADD.
1004
1005 ; Check that the shift gets turned into an LEA.
1006 ; RUN: llvm-upgrade < %s | llvm-as | llc -march=x86 -x86-asm-syntax=intel | \
1007 ; RUN:   not grep {mov E.X, E.X}
1008
1009 %G = external global int
1010
1011 int %test1(int %X, int %Y) {
1012         %Z = add int %X, %Y
1013         volatile store int %Y, int* %G
1014         volatile store int %Z, int* %G
1015         ret int %X
1016 }
1017
1018 int %test2(int %X) {
1019         %Z = add int %X, 1  ;; inc
1020         volatile store int %Z, int* %G
1021         ret int %X
1022 }
1023
1024 //===---------------------------------------------------------------------===//
1025
1026 This:
1027 #include <xmmintrin.h>
1028 unsigned test(float f) {
1029  return _mm_cvtsi128_si32( (__m128i) _mm_set_ss( f ));
1030 }
1031
1032 Compiles to:
1033 _test:
1034         movss 4(%esp), %xmm0
1035         movd %xmm0, %eax
1036         ret
1037
1038 it should compile to a move from the stack slot directly into eax.  DAGCombine
1039 has this xform, but it is currently disabled until the alignment fields of
1040 the load/store nodes are trustworthy.
1041
1042 //===---------------------------------------------------------------------===//
1043
1044 Sometimes it is better to codegen subtractions from a constant (e.g. 7-x) with
1045 a neg instead of a sub instruction.  Consider:
1046
1047 int test(char X) { return 7-X; }
1048
1049 we currently produce:
1050 _test:
1051         movl $7, %eax
1052         movsbl 4(%esp), %ecx
1053         subl %ecx, %eax
1054         ret
1055
1056 We would use one fewer register if codegen'd as:
1057
1058         movsbl 4(%esp), %eax
1059         neg %eax
1060         add $7, %eax
1061         ret
1062
1063 Note that this isn't beneficial if the load can be folded into the sub.  In
1064 this case, we want a sub:
1065
1066 int test(int X) { return 7-X; }
1067 _test:
1068         movl $7, %eax
1069         subl 4(%esp), %eax
1070         ret
1071
1072 //===---------------------------------------------------------------------===//
1073
1074 For code like:
1075 phi (undef, x)
1076
1077 We get an implicit def on the undef side. If the phi is spilled, we then get:
1078 implicitdef xmm1
1079 store xmm1 -> stack
1080
1081 It should be possible to teach the x86 backend to "fold" the store into the
1082 implicitdef, which just deletes the implicit def.
1083
1084 These instructions should go away:
1085 #IMPLICIT_DEF %xmm1
1086 movaps %xmm1, 192(%esp)
1087 movaps %xmm1, 224(%esp)
1088 movaps %xmm1, 176(%esp)
1089
1090 //===---------------------------------------------------------------------===//
1091
1092 This is a "commutable two-address" register coallescing deficiency:
1093
1094 define <4 x float> @test1(<4 x float> %V) {
1095 entry:
1096         %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]
1097         %add = add <4 x float> %tmp8, %V                ; <<4 x float>> [#uses=1]
1098         ret <4 x float> %add
1099 }
1100
1101 this codegens to:
1102
1103 _test1:
1104         pshufd  $27, %xmm0, %xmm1
1105         addps   %xmm0, %xmm1
1106         movaps  %xmm1, %xmm0
1107         ret
1108
1109 instead of:
1110
1111 _test1:
1112         pshufd  $27, %xmm0, %xmm1
1113         addps   %xmm1, %xmm0
1114         ret
1115