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 We generate really bad code for this:
 215
 216 int f(signed char *a, _Bool b, _Bool c) {
 217    signed char t = 0;
 218   if (b)  t = *a;
 219   if (c)  *a = t;
 220 }
 221
 222 ===-------------------------------------------------------------------------===
 223
 224 On the G5, logical CR operations are more expensive in their three
 225 address form: ops that read/write the same register are half as expensive as
 226 those that read from two registers that are different from their destination.
 227
 228 We should model this with two separate instructions.  The isel should generate
 229 the "two address" form of the instructions.  When the register allocator
 230 detects that it needs to insert a copy due to the two-addresness of the CR
 231 logical op, it will invoke PPCInstrInfo::convertToThreeAddress.  At this point
 232 we can convert to the "three address" instruction, to save code space.
 233
 234 This only matters when we start generating cr logical ops.
 235
 236 ===-------------------------------------------------------------------------===
 237
 238 We should compile these two functions to the same thing:
 239
 240 #include <stdlib.h>
 241 void f(int a, int b, int *P) {
 242   *P = (a-b)>=0?(a-b):(b-a);
 243 }
 244 void g(int a, int b, int *P) {
 245   *P = abs(a-b);
 246 }
 247
 248 Further, they should compile to something better than:
 249
 250 _g:
 251         subf r2, r4, r3
 252         subfic r3, r2, 0
 253         cmpwi cr0, r2, -1
 254         bgt cr0, LBB2_2 ; entry
 255 LBB2_1: ; entry
 256         mr r2, r3
 257 LBB2_2: ; entry
 258         stw r2, 0(r5)
 259         blr
 260
 261 GCC produces:
 262
 263 _g:
 264         subf r4,r4,r3
 265         srawi r2,r4,31
 266         xor r0,r2,r4
 267         subf r0,r2,r0
 268         stw r0,0(r5)
 269         blr
 270
 271 ... which is much nicer.
 272
 273 This theoretically may help improve twolf slightly (used in dimbox.c:142?).
 274
 275 ===-------------------------------------------------------------------------===
 276
 277 PR5945: This:
 278 define i32 @clamp0g(i32 %a) {
 279 entry:
 280         %cmp = icmp slt i32 %a, 0
 281         %sel = select i1 %cmp, i32 0, i32 %a
 282         ret i32 %sel
 283 }
 284
 285 Is compile to this with the PowerPC (32-bit) backend:
 286
 287 _clamp0g:
 288         cmpwi cr0, r3, 0
 289         li r2, 0
 290         blt cr0, LBB1_2
 291 ; BB#1:                                                     ; %entry
 292         mr r2, r3
 293 LBB1_2:                                                     ; %entry
 294         mr r3, r2
 295         blr
 296
 297 This could be reduced to the much simpler:
 298
 299 _clamp0g:
 300         srawi r2, r3, 31
 301         andc r3, r3, r2
 302         blr
 303
 304 ===-------------------------------------------------------------------------===
 305
 306 int foo(int N, int ***W, int **TK, int X) {
 307   int t, i;
 308
 309   for (t = 0; t < N; ++t)
 310     for (i = 0; i < 4; ++i)
 311       W[t / X][i][t % X] = TK[i][t];
 312
 313   return 5;
 314 }
 315
 316 We generate relatively atrocious code for this loop compared to gcc.
 317
 318 We could also strength reduce the rem and the div:
 319 http://www.lcs.mit.edu/pubs/pdf/MIT-LCS-TM-600.pdf
 320
 321 ===-------------------------------------------------------------------------===
 322
 323 float foo(float X) { return (int)(X); }
 324
 325 Currently produces:
 326
 327 _foo:
 328         fctiwz f0, f1
 329         stfd f0, -8(r1)
 330         lwz r2, -4(r1)
 331         extsw r2, r2
 332         std r2, -16(r1)
 333         lfd f0, -16(r1)
 334         fcfid f0, f0
 335         frsp f1, f0
 336         blr
 337
 338 We could use a target dag combine to turn the lwz/extsw into an lwa when the
 339 lwz has a single use.  Since LWA is cracked anyway, this would be a codesize
 340 win only.
 341
 342 ===-------------------------------------------------------------------------===
 343
 344 We generate ugly code for this:
 345
 346 void func(unsigned int *ret, float dx, float dy, float dz, float dw) {
 347   unsigned code = 0;
 348   if(dx < -dw) code |= 1;
 349   if(dx > dw)  code |= 2;
 350   if(dy < -dw) code |= 4;
 351   if(dy > dw)  code |= 8;
 352   if(dz < -dw) code |= 16;
 353   if(dz > dw)  code |= 32;
 354   *ret = code;
 355 }
 356
 357 ===-------------------------------------------------------------------------===
 358
 359 %struct.B = type { i8, [3 x i8] }
 360
 361 define void @bar(%struct.B* %b) {
 362 entry:
 363         %tmp = bitcast %struct.B* %b to i32*              ; <uint*> [#uses=1]
 364         %tmp = load i32* %tmp          ; <uint> [#uses=1]
 365         %tmp3 = bitcast %struct.B* %b to i32*             ; <uint*> [#uses=1]
 366         %tmp4 = load i32* %tmp3                ; <uint> [#uses=1]
 367         %tmp8 = bitcast %struct.B* %b to i32*             ; <uint*> [#uses=2]
 368         %tmp9 = load i32* %tmp8                ; <uint> [#uses=1]
 369         %tmp4.mask17 = shl i32 %tmp4, i8 1          ; <uint> [#uses=1]
 370         %tmp1415 = and i32 %tmp4.mask17, 2147483648            ; <uint> [#uses=1]
 371         %tmp.masked = and i32 %tmp, 2147483648         ; <uint> [#uses=1]
 372         %tmp11 = or i32 %tmp1415, %tmp.masked          ; <uint> [#uses=1]
 373         %tmp12 = and i32 %tmp9, 2147483647             ; <uint> [#uses=1]
 374         %tmp13 = or i32 %tmp12, %tmp11         ; <uint> [#uses=1]
 375         store i32 %tmp13, i32* %tmp8
 376         ret void
 377 }
 378
 379 We emit:
 380
 381 _foo:
 382         lwz r2, 0(r3)
 383         slwi r4, r2, 1
 384         or r4, r4, r2
 385         rlwimi r2, r4, 0, 0, 0
 386         stw r2, 0(r3)
 387         blr
 388
 389 We could collapse a bunch of those ORs and ANDs and generate the following
 390 equivalent code:
 391
 392 _foo:
 393         lwz r2, 0(r3)
 394         rlwinm r4, r2, 1, 0, 0
 395         or r2, r2, r4
 396         stw r2, 0(r3)
 397         blr
 398
 399 ===-------------------------------------------------------------------------===
 400
 401 Consider a function like this:
 402
 403 float foo(float X) { return X + 1234.4123f; }
 404
 405 The FP constant ends up in the constant pool, so we need to get the LR register.
 406  This ends up producing code like this:
 407
 408 _foo:
 409 .LBB_foo_0:     ; entry
 410         mflr r11
 411 ***     stw r11, 8(r1)
 412         bl "L00000$pb"
 413 "L00000$pb":
 414         mflr r2
 415         addis r2, r2, ha16(.CPI_foo_0-"L00000$pb")
 416         lfs f0, lo16(.CPI_foo_0-"L00000$pb")(r2)
 417         fadds f1, f1, f0
 418 ***     lwz r11, 8(r1)
 419         mtlr r11
 420         blr
 421
 422 This is functional, but there is no reason to spill the LR register all the way
 423 to the stack (the two marked instrs): spilling it to a GPR is quite enough.
 424
 425 Implementing this will require some codegen improvements.  Nate writes:
 426
 427 "So basically what we need to support the "no stack frame save and restore" is a
 428 generalization of the LR optimization to "callee-save regs".
 429
 430 Currently, we have LR marked as a callee-save reg.  The register allocator sees
 431 that it's callee save, and spills it directly to the stack.
 432
 433 Ideally, something like this would happen:
 434
 435 LR would be in a separate register class from the GPRs. The class of LR would be
 436 marked "unspillable".  When the register allocator came across an unspillable
 437 reg, it would ask "what is the best class to copy this into that I *can* spill"
 438 If it gets a class back, which it will in this case (the gprs), it grabs a free
 439 register of that class.  If it is then later necessary to spill that reg, so be
 440 it.
 441
 442 ===-------------------------------------------------------------------------===
 443
 444 We compile this:
 445 int test(_Bool X) {
 446   return X ? 524288 : 0;
 447 }
 448
 449 to:
 450 _test:
 451         cmplwi cr0, r3, 0
 452         lis r2, 8
 453         li r3, 0
 454         beq cr0, LBB1_2 ;entry
 455 LBB1_1: ;entry
 456         mr r3, r2
 457 LBB1_2: ;entry
 458         blr
 459
 460 instead of:
 461 _test:
 462         addic r2,r3,-1
 463         subfe r0,r2,r3
 464         slwi r3,r0,19
 465         blr
 466
 467 This sort of thing occurs a lot due to globalopt.
 468
 469 ===-------------------------------------------------------------------------===
 470
 471 We compile:
 472
 473 define i32 @bar(i32 %x) nounwind readnone ssp {
 474 entry:
 475   %0 = icmp eq i32 %x, 0                          ; <i1> [#uses=1]
 476   %neg = sext i1 %0 to i32              ; <i32> [#uses=1]
 477   ret i32 %neg
 478 }
 479
 480 to:
 481
 482 _bar:
 483         cntlzw r2, r3
 484         slwi r2, r2, 26
 485         srawi r3, r2, 31
 486         blr
 487
 488 it would be better to produce:
 489
 490 _bar:
 491         addic r3,r3,-1
 492         subfe r3,r3,r3
 493         blr
 494
 495 ===-------------------------------------------------------------------------===
 496
 497 We generate horrible ppc code for this:
 498
 499 #define N  2000000
 500 double   a[N],c[N];
 501 void simpleloop() {
 502    int j;
 503    for (j=0; j<N; j++)
 504      c[j] = a[j];
 505 }
 506
 507 LBB1_1: ;bb
 508         lfdx f0, r3, r4
 509         addi r5, r5, 1                 ;; Extra IV for the exit value compare.
 510         stfdx f0, r2, r4
 511         addi r4, r4, 8
 512
 513         xoris r6, r5, 30               ;; This is due to a large immediate.
 514         cmplwi cr0, r6, 33920
 515         bne cr0, LBB1_1
 516
 517 //===---------------------------------------------------------------------===//
 518
 519 This:
 520         #include <algorithm>
 521         inline std::pair<unsigned, bool> full_add(unsigned a, unsigned b)
 522         { return std::make_pair(a + b, a + b < a); }
 523         bool no_overflow(unsigned a, unsigned b)
 524         { return !full_add(a, b).second; }
 525
 526 Should compile to:
 527
 528 __Z11no_overflowjj:
 529         add r4,r3,r4
 530         subfc r3,r3,r4
 531         li r3,0
 532         adde r3,r3,r3
 533         blr
 534
 535 (or better) not:
 536
 537 __Z11no_overflowjj:
 538         add r2, r4, r3
 539         cmplw cr7, r2, r3
 540         mfcr r2
 541         rlwinm r2, r2, 29, 31, 31
 542         xori r3, r2, 1
 543         blr
 544
 545 //===---------------------------------------------------------------------===//
 546
 547 We compile some FP comparisons into an mfcr with two rlwinms and an or.  For
 548 example:
 549 #include <math.h>
 550 int test(double x, double y) { return islessequal(x, y);}
 551 int test2(double x, double y) {  return islessgreater(x, y);}
 552 int test3(double x, double y) {  return !islessequal(x, y);}
 553
 554 Compiles into (all three are similar, but the bits differ):
 555
 556 _test:
 557         fcmpu cr7, f1, f2
 558         mfcr r2
 559         rlwinm r3, r2, 29, 31, 31
 560         rlwinm r2, r2, 31, 31, 31
 561         or r3, r2, r3
 562         blr
 563
 564 GCC compiles this into:
 565
 566  _test:
 567         fcmpu cr7,f1,f2
 568         cror 30,28,30
 569         mfcr r3
 570         rlwinm r3,r3,31,1
 571         blr
 572
 573 which is more efficient and can use mfocr.  See PR642 for some more context.
 574
 575 //===---------------------------------------------------------------------===//
 576
 577 void foo(float *data, float d) {
 578    long i;
 579    for (i = 0; i < 8000; i++)
 580       data[i] = d;
 581 }
 582 void foo2(float *data, float d) {
 583    long i;
 584    data--;
 585    for (i = 0; i < 8000; i++) {
 586       data[1] = d;
 587       data++;
 588    }
 589 }
 590
 591 These compile to:
 592
 593 _foo:
 594         li r2, 0
 595 LBB1_1: ; bb
 596         addi r4, r2, 4
 597         stfsx f1, r3, r2
 598         cmplwi cr0, r4, 32000
 599         mr r2, r4
 600         bne cr0, LBB1_1 ; bb
 601         blr
 602 _foo2:
 603         li r2, 0
 604 LBB2_1: ; bb
 605         addi r4, r2, 4
 606         stfsx f1, r3, r2
 607         cmplwi cr0, r4, 32000
 608         mr r2, r4
 609         bne cr0, LBB2_1 ; bb
 610         blr
 611
 612 The 'mr' could be eliminated to folding the add into the cmp better.
 613
 614 //===---------------------------------------------------------------------===//
 615 Codegen for the following (low-probability) case deteriorated considerably
 616 when the correctness fixes for unordered comparisons went in (PR 642, 58871).
 617 It should be possible to recover the code quality described in the comments.
 618
 619 ; RUN: llvm-as < %s | llc -march=ppc32  | grep or | count 3
 620 ; This should produce one 'or' or 'cror' instruction per function.
 621
 622 ; RUN: llvm-as < %s | llc -march=ppc32  | grep mfcr | count 3
 623 ; PR2964
 624
 625 define i32 @test(double %x, double %y) nounwind  {
 626 entry:
 627         %tmp3 = fcmp ole double %x, %y          ; <i1> [#uses=1]
 628         %tmp345 = zext i1 %tmp3 to i32          ; <i32> [#uses=1]
 629         ret i32 %tmp345
 630 }
 631
 632 define i32 @test2(double %x, double %y) nounwind  {
 633 entry:
 634         %tmp3 = fcmp one double %x, %y          ; <i1> [#uses=1]
 635         %tmp345 = zext i1 %tmp3 to i32          ; <i32> [#uses=1]
 636         ret i32 %tmp345
 637 }
 638
 639 define i32 @test3(double %x, double %y) nounwind  {
 640 entry:
 641         %tmp3 = fcmp ugt double %x, %y          ; <i1> [#uses=1]
 642         %tmp34 = zext i1 %tmp3 to i32           ; <i32> [#uses=1]
 643         ret i32 %tmp34
 644 }
 645 //===----------------------------------------------------------------------===//
 646 ; RUN: llvm-as < %s | llc -march=ppc32 | not grep fneg
 647
 648 ; This could generate FSEL with appropriate flags (FSEL is not IEEE-safe, and
 649 ; should not be generated except with -enable-finite-only-fp-math or the like).
 650 ; With the correctness fixes for PR642 (58871) LowerSELECT_CC would need to
 651 ; recognize a more elaborate tree than a simple SETxx.
 652
 653 define double @test_FNEG_sel(double %A, double %B, double %C) {
 654         %D = fsub double -0.000000e+00, %A               ; <double> [#uses=1]
 655         %Cond = fcmp ugt double %D, -0.000000e+00               ; <i1> [#uses=1]
 656         %E = select i1 %Cond, double %B, double %C              ; <double> [#uses=1]
 657         ret double %E
 658 }
 659
 660 //===----------------------------------------------------------------------===//
 661 The save/restore sequence for CR in prolog/epilog is terrible:
 662 - Each CR subreg is saved individually, rather than doing one save as a unit.
 663 - On Darwin, the save is done after the decrement of SP, which means the offset
 664 from SP of the save slot can be too big for a store instruction, which means we
 665 need an additional register (currently hacked in 96015+96020; the solution there
 666 is correct, but poor).
 667 - On SVR4 the same thing can happen, and I don't think saving before the SP
 668 decrement is safe on that target, as there is no red zone.  This is currently
 669 broken AFAIK, although it's not a target I can exercise.
 670 The following demonstrates the problem:
 671 extern void bar(char *p);
 672 void foo() {
 673   char x[100000];
 674   bar(x);
 675   __asm__("" ::: "cr2");
 676 }