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 test/CodeGen/PowerPC/2007-03-24-cntlzd.ll compiles to:
 498
 499 __ZNK4llvm5APInt17countLeadingZerosEv:
 500         ld r2, 0(r3)
 501         cntlzd r2, r2
 502         or r2, r2, r2     <<-- silly.
 503         addi r3, r2, -64
 504         blr
 505
 506 The dead or is a 'truncate' from 64- to 32-bits.
 507
 508 ===-------------------------------------------------------------------------===
 509
 510 We generate horrible ppc code for this:
 511
 512 #define N  2000000
 513 double   a[N],c[N];
 514 void simpleloop() {
 515    int j;
 516    for (j=0; j<N; j++)
 517      c[j] = a[j];
 518 }
 519
 520 LBB1_1: ;bb
 521         lfdx f0, r3, r4
 522         addi r5, r5, 1                 ;; Extra IV for the exit value compare.
 523         stfdx f0, r2, r4
 524         addi r4, r4, 8
 525
 526         xoris r6, r5, 30               ;; This is due to a large immediate.
 527         cmplwi cr0, r6, 33920
 528         bne cr0, LBB1_1
 529
 530 //===---------------------------------------------------------------------===//
 531
 532 This:
 533         #include <algorithm>
 534         inline std::pair<unsigned, bool> full_add(unsigned a, unsigned b)
 535         { return std::make_pair(a + b, a + b < a); }
 536         bool no_overflow(unsigned a, unsigned b)
 537         { return !full_add(a, b).second; }
 538
 539 Should compile to:
 540
 541 __Z11no_overflowjj:
 542         add r4,r3,r4
 543         subfc r3,r3,r4
 544         li r3,0
 545         adde r3,r3,r3
 546         blr
 547
 548 (or better) not:
 549
 550 __Z11no_overflowjj:
 551         add r2, r4, r3
 552         cmplw cr7, r2, r3
 553         mfcr r2
 554         rlwinm r2, r2, 29, 31, 31
 555         xori r3, r2, 1
 556         blr
 557
 558 //===---------------------------------------------------------------------===//
 559
 560 We compile some FP comparisons into an mfcr with two rlwinms and an or.  For
 561 example:
 562 #include <math.h>
 563 int test(double x, double y) { return islessequal(x, y);}
 564 int test2(double x, double y) {  return islessgreater(x, y);}
 565 int test3(double x, double y) {  return !islessequal(x, y);}
 566
 567 Compiles into (all three are similar, but the bits differ):
 568
 569 _test:
 570         fcmpu cr7, f1, f2
 571         mfcr r2
 572         rlwinm r3, r2, 29, 31, 31
 573         rlwinm r2, r2, 31, 31, 31
 574         or r3, r2, r3
 575         blr
 576
 577 GCC compiles this into:
 578
 579  _test:
 580         fcmpu cr7,f1,f2
 581         cror 30,28,30
 582         mfcr r3
 583         rlwinm r3,r3,31,1
 584         blr
 585
 586 which is more efficient and can use mfocr.  See PR642 for some more context.
 587
 588 //===---------------------------------------------------------------------===//
 589
 590 void foo(float *data, float d) {
 591    long i;
 592    for (i = 0; i < 8000; i++)
 593       data[i] = d;
 594 }
 595 void foo2(float *data, float d) {
 596    long i;
 597    data--;
 598    for (i = 0; i < 8000; i++) {
 599       data[1] = d;
 600       data++;
 601    }
 602 }
 603
 604 These compile to:
 605
 606 _foo:
 607         li r2, 0
 608 LBB1_1: ; bb
 609         addi r4, r2, 4
 610         stfsx f1, r3, r2
 611         cmplwi cr0, r4, 32000
 612         mr r2, r4
 613         bne cr0, LBB1_1 ; bb
 614         blr
 615 _foo2:
 616         li r2, 0
 617 LBB2_1: ; bb
 618         addi r4, r2, 4
 619         stfsx f1, r3, r2
 620         cmplwi cr0, r4, 32000
 621         mr r2, r4
 622         bne cr0, LBB2_1 ; bb
 623         blr
 624
 625 The 'mr' could be eliminated to folding the add into the cmp better.
 626
 627 //===---------------------------------------------------------------------===//
 628 Codegen for the following (low-probability) case deteriorated considerably
 629 when the correctness fixes for unordered comparisons went in (PR 642, 58871).
 630 It should be possible to recover the code quality described in the comments.
 631
 632 ; RUN: llvm-as < %s | llc -march=ppc32  | grep or | count 3
 633 ; This should produce one 'or' or 'cror' instruction per function.
 634
 635 ; RUN: llvm-as < %s | llc -march=ppc32  | grep mfcr | count 3
 636 ; PR2964
 637
 638 define i32 @test(double %x, double %y) nounwind  {
 639 entry:
 640         %tmp3 = fcmp ole double %x, %y          ; <i1> [#uses=1]
 641         %tmp345 = zext i1 %tmp3 to i32          ; <i32> [#uses=1]
 642         ret i32 %tmp345
 643 }
 644
 645 define i32 @test2(double %x, double %y) nounwind  {
 646 entry:
 647         %tmp3 = fcmp one double %x, %y          ; <i1> [#uses=1]
 648         %tmp345 = zext i1 %tmp3 to i32          ; <i32> [#uses=1]
 649         ret i32 %tmp345
 650 }
 651
 652 define i32 @test3(double %x, double %y) nounwind  {
 653 entry:
 654         %tmp3 = fcmp ugt double %x, %y          ; <i1> [#uses=1]
 655         %tmp34 = zext i1 %tmp3 to i32           ; <i32> [#uses=1]
 656         ret i32 %tmp34
 657 }
 658 //===----------------------------------------------------------------------===//
 659 ; RUN: llvm-as < %s | llc -march=ppc32 | not grep fneg
 660
 661 ; This could generate FSEL with appropriate flags (FSEL is not IEEE-safe, and
 662 ; should not be generated except with -enable-finite-only-fp-math or the like).
 663 ; With the correctness fixes for PR642 (58871) LowerSELECT_CC would need to
 664 ; recognize a more elaborate tree than a simple SETxx.
 665
 666 define double @test_FNEG_sel(double %A, double %B, double %C) {
 667         %D = fsub double -0.000000e+00, %A               ; <double> [#uses=1]
 668         %Cond = fcmp ugt double %D, -0.000000e+00               ; <i1> [#uses=1]
 669         %E = select i1 %Cond, double %B, double %C              ; <double> [#uses=1]
 670         ret double %E
 671 }
 672
 673 //===----------------------------------------------------------------------===//
 674 The save/restore sequence for CR in prolog/epilog is terrible:
 675 - Each CR subreg is saved individually, rather than doing one save as a unit.
 676 - On Darwin, the save is done after the decrement of SP, which means the offset
 677 from SP of the save slot can be too big for a store instruction, which means we
 678 need an additional register (currently hacked in 96015+96020; the solution there
 679 is correct, but poor).
 680 - On SVR4 the same thing can happen, and I don't think saving before the SP
 681 decrement is safe on that target, as there is no red zone.  This is currently
 682 broken AFAIK, although it's not a target I can exercise.
 683 The following demonstrates the problem:
 684 extern void bar(char *p);
 685 void foo() {
 686   char x[100000];
 687   bar(x);
 688   __asm__("" ::: "cr2");
 689 }