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