lib/Target/PowerPC/README.txt

   1 //===- README.txt - Notes for improving PowerPC-specific code gen ---------===//
   2
   3 TODO:
   4 * lmw/stmw pass a la arm load store optimizer for prolog/epilog
   5
   6 ===-------------------------------------------------------------------------===
   7
   8 This code:
   9
  10 unsigned add32carry(unsigned sum, unsigned x) {
  11  unsigned z = sum + x;
  12  if (sum + x < x)
  13      z++;
  14  return z;
  15 }
  16
  17 Should compile to something like:
  18
  19         addc r3,r3,r4
  20         addze r3,r3
  21
  22 instead we get:
  23
  24         add r3, r4, r3
  25         cmplw cr7, r3, r4
  26         mfcr r4 ; 1
  27         rlwinm r4, r4, 29, 31, 31
  28         add r3, r3, r4
  29
  30 Ick.
  31
  32 ===-------------------------------------------------------------------------===
  33
  34 We compile the hottest inner loop of viterbi to:
  35
  36         li r6, 0
  37         b LBB1_84       ;bb432.i
  38 LBB1_83:        ;bb420.i
  39         lbzx r8, r5, r7
  40         addi r6, r7, 1
  41         stbx r8, r4, r7
  42 LBB1_84:        ;bb432.i
  43         mr r7, r6
  44         cmplwi cr0, r7, 143
  45         bne cr0, LBB1_83        ;bb420.i
  46
  47 The CBE manages to produce:
  48
  49         li r0, 143
  50         mtctr r0
  51 loop:
  52         lbzx r2, r2, r11
  53         stbx r0, r2, r9
  54         addi r2, r2, 1
  55         bdz later
  56         b loop
  57
  58 This could be much better (bdnz instead of bdz) but it still beats us.  If we
  59 produced this with bdnz, the loop would be a single dispatch group.
  60
  61 ===-------------------------------------------------------------------------===
  62
  63 Lump the constant pool for each function into ONE pic object, and reference
  64 pieces of it as offsets from the start.  For functions like this (contrived
  65 to have lots of constants obviously):
  66
  67 double X(double Y) { return (Y*1.23 + 4.512)*2.34 + 14.38; }
  68
  69 We generate:
  70
  71 _X:
  72         lis r2, ha16(.CPI_X_0)
  73         lfd f0, lo16(.CPI_X_0)(r2)
  74         lis r2, ha16(.CPI_X_1)
  75         lfd f2, lo16(.CPI_X_1)(r2)
  76         fmadd f0, f1, f0, f2
  77         lis r2, ha16(.CPI_X_2)
  78         lfd f1, lo16(.CPI_X_2)(r2)
  79         lis r2, ha16(.CPI_X_3)
  80         lfd f2, lo16(.CPI_X_3)(r2)
  81         fmadd f1, f0, f1, f2
  82         blr
  83
  84 It would be better to materialize .CPI_X into a register, then use immediates
  85 off of the register to avoid the lis's.  This is even more important in PIC
  86 mode.
  87
  88 Note that this (and the static variable version) is discussed here for GCC:
  89 http://gcc.gnu.org/ml/gcc-patches/2006-02/msg00133.html
  90
  91 Here's another example (the sgn function):
  92 double testf(double a) {
  93        return a == 0.0 ? 0.0 : (a > 0.0 ? 1.0 : -1.0);
  94 }
  95
  96 it produces a BB like this:
  97 LBB1_1: ; cond_true
  98         lis r2, ha16(LCPI1_0)
  99         lfs f0, lo16(LCPI1_0)(r2)
 100         lis r2, ha16(LCPI1_1)
 101         lis r3, ha16(LCPI1_2)
 102         lfs f2, lo16(LCPI1_2)(r3)
 103         lfs f3, lo16(LCPI1_1)(r2)
 104         fsub f0, f0, f1
 105         fsel f1, f0, f2, f3
 106         blr
 107
 108 ===-------------------------------------------------------------------------===
 109
 110 PIC Code Gen IPO optimization:
 111
 112 Squish small scalar globals together into a single global struct, allowing the
 113 address of the struct to be CSE'd, avoiding PIC accesses (also reduces the size
 114 of the GOT on targets with one).
 115
 116 Note that this is discussed here for GCC:
 117 http://gcc.gnu.org/ml/gcc-patches/2006-02/msg00133.html
 118
 119 ===-------------------------------------------------------------------------===
 120
 121 No loads or stores of the constants should be needed:
 122
 123 struct foo { double X, Y; };
 124 void xxx(struct foo F);
 125 void bar() { struct foo R = { 1.0, 2.0 }; xxx(R); }
 126
 127 ===-------------------------------------------------------------------------===
 128
 129 Darwin Stub removal:
 130
 131 We still generate calls to foo$stub, and stubs, on Darwin.  This is not
 132 necessary when building with the Leopard (10.5) or later linker, as stubs are
 133 generated by ld when necessary.  Parameterizing this based on the deployment
 134 target (-mmacosx-version-min) is probably enough.  x86-32 does this right, see
 135 its logic.
 136
 137 ===-------------------------------------------------------------------------===
 138
 139 Darwin Stub LICM optimization:
 140
 141 Loops like this:
 142
 143   for (...)  bar();
 144
 145 Have to go through an indirect stub if bar is external or linkonce.  It would
 146 be better to compile it as:
 147
 148      fp = &bar;
 149      for (...)  fp();
 150
 151 which only computes the address of bar once (instead of each time through the
 152 stub).  This is Darwin specific and would have to be done in the code generator.
 153 Probably not a win on x86.
 154
 155 ===-------------------------------------------------------------------------===
 156
 157 Simple IPO for argument passing, change:
 158   void foo(int X, double Y, int Z) -> void foo(int X, int Z, double Y)
 159
 160 the Darwin ABI specifies that any integer arguments in the first 32 bytes worth
 161 of arguments get assigned to r3 through r10. That is, if you have a function
 162 foo(int, double, int) you get r3, f1, r6, since the 64 bit double ate up the
 163 argument bytes for r4 and r5. The trick then would be to shuffle the argument
 164 order for functions we can internalize so that the maximum number of
 165 integers/pointers get passed in regs before you see any of the fp arguments.
 166
 167 Instead of implementing this, it would actually probably be easier to just
 168 implement a PPC fastcc, where we could do whatever we wanted to the CC,
 169 including having this work sanely.
 170
 171 ===-------------------------------------------------------------------------===
 172
 173 Fix Darwin FP-In-Integer Registers ABI
 174
 175 Darwin passes doubles in structures in integer registers, which is very very
 176 bad.  Add something like a BITCAST to LLVM, then do an i-p transformation that
 177 percolates these things out of functions.
 178
 179 Check out how horrible this is:
 180 http://gcc.gnu.org/ml/gcc/2005-10/msg01036.html
 181
 182 This is an extension of "interprocedural CC unmunging" that can't be done with
 183 just fastcc.
 184
 185 ===-------------------------------------------------------------------------===
 186
 187 Fold add and sub with constant into non-extern, non-weak addresses so this:
 188
 189 static int a;
 190 void bar(int b) { a = b; }
 191 void foo(unsigned char *c) {
 192   *c = a;
 193 }
 194
 195 So that
 196
 197 _foo:
 198         lis r2, ha16(_a)
 199         la r2, lo16(_a)(r2)
 200         lbz r2, 3(r2)
 201         stb r2, 0(r3)
 202         blr
 203
 204 Becomes
 205
 206 _foo:
 207         lis r2, ha16(_a+3)
 208         lbz r2, lo16(_a+3)(r2)
 209         stb r2, 0(r3)
 210         blr
 211
 212 ===-------------------------------------------------------------------------===
 213
 214 On the G5, logical CR operations are more expensive in their three
 215 address form: ops that read/write the same register are half as expensive as
 216 those that read from two registers that are different from their destination.
 217
 218 We should model this with two separate instructions.  The isel should generate
 219 the "two address" form of the instructions.  When the register allocator
 220 detects that it needs to insert a copy due to the two-addresness of the CR
 221 logical op, it will invoke PPCInstrInfo::convertToThreeAddress.  At this point
 222 we can convert to the "three address" instruction, to save code space.
 223
 224 This only matters when we start generating cr logical ops.
 225
 226 ===-------------------------------------------------------------------------===
 227
 228 We should compile these two functions to the same thing:
 229
 230 #include <stdlib.h>
 231 void f(int a, int b, int *P) {
 232   *P = (a-b)>=0?(a-b):(b-a);
 233 }
 234 void g(int a, int b, int *P) {
 235   *P = abs(a-b);
 236 }
 237
 238 Further, they should compile to something better than:
 239
 240 _g:
 241         subf r2, r4, r3
 242         subfic r3, r2, 0
 243         cmpwi cr0, r2, -1
 244         bgt cr0, LBB2_2 ; entry
 245 LBB2_1: ; entry
 246         mr r2, r3
 247 LBB2_2: ; entry
 248         stw r2, 0(r5)
 249         blr
 250
 251 GCC produces:
 252
 253 _g:
 254         subf r4,r4,r3
 255         srawi r2,r4,31
 256         xor r0,r2,r4
 257         subf r0,r2,r0
 258         stw r0,0(r5)
 259         blr
 260
 261 ... which is much nicer.
 262
 263 This theoretically may help improve twolf slightly (used in dimbox.c:142?).
 264
 265 ===-------------------------------------------------------------------------===
 266
 267 PR5945: This:
 268 define i32 @clamp0g(i32 %a) {
 269 entry:
 270         %cmp = icmp slt i32 %a, 0
 271         %sel = select i1 %cmp, i32 0, i32 %a
 272         ret i32 %sel
 273 }
 274
 275 Is compile to this with the PowerPC (32-bit) backend:
 276
 277 _clamp0g:
 278         cmpwi cr0, r3, 0
 279         li r2, 0
 280         blt cr0, LBB1_2
 281 ; BB#1:                                                     ; %entry
 282         mr r2, r3
 283 LBB1_2:                                                     ; %entry
 284         mr r3, r2
 285         blr
 286
 287 This could be reduced to the much simpler:
 288
 289 _clamp0g:
 290         srawi r2, r3, 31
 291         andc r3, r3, r2
 292         blr
 293
 294 ===-------------------------------------------------------------------------===
 295
 296 int foo(int N, int ***W, int **TK, int X) {
 297   int t, i;
 298
 299   for (t = 0; t < N; ++t)
 300     for (i = 0; i < 4; ++i)
 301       W[t / X][i][t % X] = TK[i][t];
 302
 303   return 5;
 304 }
 305
 306 We generate relatively atrocious code for this loop compared to gcc.
 307
 308 We could also strength reduce the rem and the div:
 309 http://www.lcs.mit.edu/pubs/pdf/MIT-LCS-TM-600.pdf
 310
 311 ===-------------------------------------------------------------------------===
 312
 313 float foo(float X) { return (int)(X); }
 314
 315 Currently produces:
 316
 317 _foo:
 318         fctiwz f0, f1
 319         stfd f0, -8(r1)
 320         lwz r2, -4(r1)
 321         extsw r2, r2
 322         std r2, -16(r1)
 323         lfd f0, -16(r1)
 324         fcfid f0, f0
 325         frsp f1, f0
 326         blr
 327
 328 We could use a target dag combine to turn the lwz/extsw into an lwa when the
 329 lwz has a single use.  Since LWA is cracked anyway, this would be a codesize
 330 win only.
 331
 332 ===-------------------------------------------------------------------------===
 333
 334 We generate ugly code for this:
 335
 336 void func(unsigned int *ret, float dx, float dy, float dz, float dw) {
 337   unsigned code = 0;
 338   if(dx < -dw) code |= 1;
 339   if(dx > dw)  code |= 2;
 340   if(dy < -dw) code |= 4;
 341   if(dy > dw)  code |= 8;
 342   if(dz < -dw) code |= 16;
 343   if(dz > dw)  code |= 32;
 344   *ret = code;
 345 }
 346
 347 ===-------------------------------------------------------------------------===
 348
 349 %struct.B = type { i8, [3 x i8] }
 350
 351 define void @bar(%struct.B* %b) {
 352 entry:
 353         %tmp = bitcast %struct.B* %b to i32*              ; <uint*> [#uses=1]
 354         %tmp = load i32* %tmp          ; <uint> [#uses=1]
 355         %tmp3 = bitcast %struct.B* %b to i32*             ; <uint*> [#uses=1]
 356         %tmp4 = load i32* %tmp3                ; <uint> [#uses=1]
 357         %tmp8 = bitcast %struct.B* %b to i32*             ; <uint*> [#uses=2]
 358         %tmp9 = load i32* %tmp8                ; <uint> [#uses=1]
 359         %tmp4.mask17 = shl i32 %tmp4, i8 1          ; <uint> [#uses=1]
 360         %tmp1415 = and i32 %tmp4.mask17, 2147483648            ; <uint> [#uses=1]
 361         %tmp.masked = and i32 %tmp, 2147483648         ; <uint> [#uses=1]
 362         %tmp11 = or i32 %tmp1415, %tmp.masked          ; <uint> [#uses=1]
 363         %tmp12 = and i32 %tmp9, 2147483647             ; <uint> [#uses=1]
 364         %tmp13 = or i32 %tmp12, %tmp11         ; <uint> [#uses=1]
 365         store i32 %tmp13, i32* %tmp8
 366         ret void
 367 }
 368
 369 We emit:
 370
 371 _foo:
 372         lwz r2, 0(r3)
 373         slwi r4, r2, 1
 374         or r4, r4, r2
 375         rlwimi r2, r4, 0, 0, 0
 376         stw r2, 0(r3)
 377         blr
 378
 379 We could collapse a bunch of those ORs and ANDs and generate the following
 380 equivalent code:
 381
 382 _foo:
 383         lwz r2, 0(r3)
 384         rlwinm r4, r2, 1, 0, 0
 385         or r2, r2, r4
 386         stw r2, 0(r3)
 387         blr
 388
 389 ===-------------------------------------------------------------------------===
 390
 391 Consider a function like this:
 392
 393 float foo(float X) { return X + 1234.4123f; }
 394
 395 The FP constant ends up in the constant pool, so we need to get the LR register.
 396  This ends up producing code like this:
 397
 398 _foo:
 399 .LBB_foo_0:     ; entry
 400         mflr r11
 401 ***     stw r11, 8(r1)
 402         bl "L00000$pb"
 403 "L00000$pb":
 404         mflr r2
 405         addis r2, r2, ha16(.CPI_foo_0-"L00000$pb")
 406         lfs f0, lo16(.CPI_foo_0-"L00000$pb")(r2)
 407         fadds f1, f1, f0
 408 ***     lwz r11, 8(r1)
 409         mtlr r11
 410         blr
 411
 412 This is functional, but there is no reason to spill the LR register all the way
 413 to the stack (the two marked instrs): spilling it to a GPR is quite enough.
 414
 415 Implementing this will require some codegen improvements.  Nate writes:
 416
 417 "So basically what we need to support the "no stack frame save and restore" is a
 418 generalization of the LR optimization to "callee-save regs".
 419
 420 Currently, we have LR marked as a callee-save reg.  The register allocator sees
 421 that it's callee save, and spills it directly to the stack.
 422
 423 Ideally, something like this would happen:
 424
 425 LR would be in a separate register class from the GPRs. The class of LR would be
 426 marked "unspillable".  When the register allocator came across an unspillable
 427 reg, it would ask "what is the best class to copy this into that I *can* spill"
 428 If it gets a class back, which it will in this case (the gprs), it grabs a free
 429 register of that class.  If it is then later necessary to spill that reg, so be
 430 it.
 431
 432 ===-------------------------------------------------------------------------===
 433
 434 We compile this:
 435 int test(_Bool X) {
 436   return X ? 524288 : 0;
 437 }
 438
 439 to:
 440 _test:
 441         cmplwi cr0, r3, 0
 442         lis r2, 8
 443         li r3, 0
 444         beq cr0, LBB1_2 ;entry
 445 LBB1_1: ;entry
 446         mr r3, r2
 447 LBB1_2: ;entry
 448         blr
 449
 450 instead of:
 451 _test:
 452         addic r2,r3,-1
 453         subfe r0,r2,r3
 454         slwi r3,r0,19
 455         blr
 456
 457 This sort of thing occurs a lot due to globalopt.
 458
 459 ===-------------------------------------------------------------------------===
 460
 461 We compile:
 462
 463 define i32 @bar(i32 %x) nounwind readnone ssp {
 464 entry:
 465   %0 = icmp eq i32 %x, 0                          ; <i1> [#uses=1]
 466   %neg = sext i1 %0 to i32              ; <i32> [#uses=1]
 467   ret i32 %neg
 468 }
 469
 470 to:
 471
 472 _bar:
 473         cntlzw r2, r3
 474         slwi r2, r2, 26
 475         srawi r3, r2, 31
 476         blr
 477
 478 it would be better to produce:
 479
 480 _bar:
 481         addic r3,r3,-1
 482         subfe r3,r3,r3
 483         blr
 484
 485 ===-------------------------------------------------------------------------===
 486
 487 We generate horrible ppc code for this:
 488
 489 #define N  2000000
 490 double   a[N],c[N];
 491 void simpleloop() {
 492    int j;
 493    for (j=0; j<N; j++)
 494      c[j] = a[j];
 495 }
 496
 497 LBB1_1: ;bb
 498         lfdx f0, r3, r4
 499         addi r5, r5, 1                 ;; Extra IV for the exit value compare.
 500         stfdx f0, r2, r4
 501         addi r4, r4, 8
 502
 503         xoris r6, r5, 30               ;; This is due to a large immediate.
 504         cmplwi cr0, r6, 33920
 505         bne cr0, LBB1_1
 506
 507 //===---------------------------------------------------------------------===//
 508
 509 This:
 510         #include <algorithm>
 511         inline std::pair<unsigned, bool> full_add(unsigned a, unsigned b)
 512         { return std::make_pair(a + b, a + b < a); }
 513         bool no_overflow(unsigned a, unsigned b)
 514         { return !full_add(a, b).second; }
 515
 516 Should compile to:
 517
 518 __Z11no_overflowjj:
 519         add r4,r3,r4
 520         subfc r3,r3,r4
 521         li r3,0
 522         adde r3,r3,r3
 523         blr
 524
 525 (or better) not:
 526
 527 __Z11no_overflowjj:
 528         add r2, r4, r3
 529         cmplw cr7, r2, r3
 530         mfcr r2
 531         rlwinm r2, r2, 29, 31, 31
 532         xori r3, r2, 1
 533         blr
 534
 535 //===---------------------------------------------------------------------===//
 536
 537 We compile some FP comparisons into an mfcr with two rlwinms and an or.  For
 538 example:
 539 #include <math.h>
 540 int test(double x, double y) { return islessequal(x, y);}
 541 int test2(double x, double y) {  return islessgreater(x, y);}
 542 int test3(double x, double y) {  return !islessequal(x, y);}
 543
 544 Compiles into (all three are similar, but the bits differ):
 545
 546 _test:
 547         fcmpu cr7, f1, f2
 548         mfcr r2
 549         rlwinm r3, r2, 29, 31, 31
 550         rlwinm r2, r2, 31, 31, 31
 551         or r3, r2, r3
 552         blr
 553
 554 GCC compiles this into:
 555
 556  _test:
 557         fcmpu cr7,f1,f2
 558         cror 30,28,30
 559         mfcr r3
 560         rlwinm r3,r3,31,1
 561         blr
 562
 563 which is more efficient and can use mfocr.  See PR642 for some more context.
 564
 565 //===---------------------------------------------------------------------===//
 566
 567 void foo(float *data, float d) {
 568    long i;
 569    for (i = 0; i < 8000; i++)
 570       data[i] = d;
 571 }
 572 void foo2(float *data, float d) {
 573    long i;
 574    data--;
 575    for (i = 0; i < 8000; i++) {
 576       data[1] = d;
 577       data++;
 578    }
 579 }
 580
 581 These compile to:
 582
 583 _foo:
 584         li r2, 0
 585 LBB1_1: ; bb
 586         addi r4, r2, 4
 587         stfsx f1, r3, r2
 588         cmplwi cr0, r4, 32000
 589         mr r2, r4
 590         bne cr0, LBB1_1 ; bb
 591         blr
 592 _foo2:
 593         li r2, 0
 594 LBB2_1: ; bb
 595         addi r4, r2, 4
 596         stfsx f1, r3, r2
 597         cmplwi cr0, r4, 32000
 598         mr r2, r4
 599         bne cr0, LBB2_1 ; bb
 600         blr
 601
 602 The 'mr' could be eliminated to folding the add into the cmp better.
 603
 604 //===---------------------------------------------------------------------===//
 605 Codegen for the following (low-probability) case deteriorated considerably
 606 when the correctness fixes for unordered comparisons went in (PR 642, 58871).
 607 It should be possible to recover the code quality described in the comments.
 608
 609 ; RUN: llvm-as < %s | llc -march=ppc32  | grep or | count 3
 610 ; This should produce one 'or' or 'cror' instruction per function.
 611
 612 ; RUN: llvm-as < %s | llc -march=ppc32  | grep mfcr | count 3
 613 ; PR2964
 614
 615 define i32 @test(double %x, double %y) nounwind  {
 616 entry:
 617         %tmp3 = fcmp ole double %x, %y          ; <i1> [#uses=1]
 618         %tmp345 = zext i1 %tmp3 to i32          ; <i32> [#uses=1]
 619         ret i32 %tmp345
 620 }
 621
 622 define i32 @test2(double %x, double %y) nounwind  {
 623 entry:
 624         %tmp3 = fcmp one double %x, %y          ; <i1> [#uses=1]
 625         %tmp345 = zext i1 %tmp3 to i32          ; <i32> [#uses=1]
 626         ret i32 %tmp345
 627 }
 628
 629 define i32 @test3(double %x, double %y) nounwind  {
 630 entry:
 631         %tmp3 = fcmp ugt double %x, %y          ; <i1> [#uses=1]
 632         %tmp34 = zext i1 %tmp3 to i32           ; <i32> [#uses=1]
 633         ret i32 %tmp34
 634 }
 635 //===----------------------------------------------------------------------===//
 636 ; RUN: llvm-as < %s | llc -march=ppc32 | not grep fneg
 637
 638 ; This could generate FSEL with appropriate flags (FSEL is not IEEE-safe, and
 639 ; should not be generated except with -enable-finite-only-fp-math or the like).
 640 ; With the correctness fixes for PR642 (58871) LowerSELECT_CC would need to
 641 ; recognize a more elaborate tree than a simple SETxx.
 642
 643 define double @test_FNEG_sel(double %A, double %B, double %C) {
 644         %D = fsub double -0.000000e+00, %A               ; <double> [#uses=1]
 645         %Cond = fcmp ugt double %D, -0.000000e+00               ; <i1> [#uses=1]
 646         %E = select i1 %Cond, double %B, double %C              ; <double> [#uses=1]
 647         ret double %E
 648 }
 649
 650 //===----------------------------------------------------------------------===//
 651 The save/restore sequence for CR in prolog/epilog is terrible:
 652 - Each CR subreg is saved individually, rather than doing one save as a unit.
 653 - On Darwin, the save is done after the decrement of SP, which means the offset
 654 from SP of the save slot can be too big for a store instruction, which means we
 655 need an additional register (currently hacked in 96015+96020; the solution there
 656 is correct, but poor).
 657 - On SVR4 the same thing can happen, and I don't think saving before the SP
 658 decrement is safe on that target, as there is no red zone.  This is currently
 659 broken AFAIK, although it's not a target I can exercise.
 660 The following demonstrates the problem:
 661 extern void bar(char *p);
 662 void foo() {
 663   char x[100000];
 664   bar(x);
 665   __asm__("" ::: "cr2");
 666 }