lib/Target/ARM/README.txt

   1 //===---------------------------------------------------------------------===//
   2 // Random ideas for the ARM backend.
   3 //===---------------------------------------------------------------------===//
   4
   5 Reimplement 'select' in terms of 'SEL'.
   6
   7 * We would really like to support UXTAB16, but we need to prove that the
   8   add doesn't need to overflow between the two 16-bit chunks.
   9
  10 * Implement pre/post increment support.  (e.g. PR935)
  11 * Implement smarter constant generation for binops with large immediates.
  12
  13 A few ARMv6T2 ops should be pattern matched: BFI, SBFX, and UBFX
  14
  15 //===---------------------------------------------------------------------===//
  16
  17 Crazy idea:  Consider code that uses lots of 8-bit or 16-bit values.  By the
  18 time regalloc happens, these values are now in a 32-bit register, usually with
  19 the top-bits known to be sign or zero extended.  If spilled, we should be able
  20 to spill these to a 8-bit or 16-bit stack slot, zero or sign extending as part
  21 of the reload.
  22
  23 Doing this reduces the size of the stack frame (important for thumb etc), and
  24 also increases the likelihood that we will be able to reload multiple values
  25 from the stack with a single load.
  26
  27 //===---------------------------------------------------------------------===//
  28
  29 The constant island pass is in good shape.  Some cleanups might be desirable,
  30 but there is unlikely to be much improvement in the generated code.
  31
  32 1.  There may be some advantage to trying to be smarter about the initial
  33 placement, rather than putting everything at the end.
  34
  35 2.  There might be some compile-time efficiency to be had by representing
  36 consecutive islands as a single block rather than multiple blocks.
  37
  38 3.  Use a priority queue to sort constant pool users in inverse order of
  39     position so we always process the one closed to the end of functions
  40     first. This may simply CreateNewWater.
  41
  42 //===---------------------------------------------------------------------===//
  43
  44 Eliminate copysign custom expansion. We are still generating crappy code with
  45 default expansion + if-conversion.
  46
  47 //===---------------------------------------------------------------------===//
  48
  49 Eliminate one instruction from:
  50
  51 define i32 @_Z6slow4bii(i32 %x, i32 %y) {
  52         %tmp = icmp sgt i32 %x, %y
  53         %retval = select i1 %tmp, i32 %x, i32 %y
  54         ret i32 %retval
  55 }
  56
  57 __Z6slow4bii:
  58         cmp r0, r1
  59         movgt r1, r0
  60         mov r0, r1
  61         bx lr
  62 =>
  63
  64 __Z6slow4bii:
  65         cmp r0, r1
  66         movle r0, r1
  67         bx lr
  68
  69 //===---------------------------------------------------------------------===//
  70
  71 Implement long long "X-3" with instructions that fold the immediate in.  These
  72 were disabled due to badness with the ARM carry flag on subtracts.
  73
  74 //===---------------------------------------------------------------------===//
  75
  76 More load / store optimizations:
  77 1) Better representation for block transfer? This is from Olden/power:
  78
  79         fldd d0, [r4]
  80         fstd d0, [r4, #+32]
  81         fldd d0, [r4, #+8]
  82         fstd d0, [r4, #+40]
  83         fldd d0, [r4, #+16]
  84         fstd d0, [r4, #+48]
  85         fldd d0, [r4, #+24]
  86         fstd d0, [r4, #+56]
  87
  88 If we can spare the registers, it would be better to use fldm and fstm here.
  89 Need major register allocator enhancement though.
  90
  91 2) Can we recognize the relative position of constantpool entries? i.e. Treat
  92
  93         ldr r0, LCPI17_3
  94         ldr r1, LCPI17_4
  95         ldr r2, LCPI17_5
  96
  97    as
  98         ldr r0, LCPI17
  99         ldr r1, LCPI17+4
 100         ldr r2, LCPI17+8
 101
 102    Then the ldr's can be combined into a single ldm. See Olden/power.
 103
 104 Note for ARM v4 gcc uses ldmia to load a pair of 32-bit values to represent a
 105 double 64-bit FP constant:
 106
 107         adr     r0, L6
 108         ldmia   r0, {r0-r1}
 109
 110         .align 2
 111 L6:
 112         .long   -858993459
 113         .long   1074318540
 114
 115 3) struct copies appear to be done field by field
 116 instead of by words, at least sometimes:
 117
 118 struct foo { int x; short s; char c1; char c2; };
 119 void cpy(struct foo*a, struct foo*b) { *a = *b; }
 120
 121 llvm code (-O2)
 122         ldrb r3, [r1, #+6]
 123         ldr r2, [r1]
 124         ldrb r12, [r1, #+7]
 125         ldrh r1, [r1, #+4]
 126         str r2, [r0]
 127         strh r1, [r0, #+4]
 128         strb r3, [r0, #+6]
 129         strb r12, [r0, #+7]
 130 gcc code (-O2)
 131         ldmia   r1, {r1-r2}
 132         stmia   r0, {r1-r2}
 133
 134 In this benchmark poor handling of aggregate copies has shown up as
 135 having a large effect on size, and possibly speed as well (we don't have
 136 a good way to measure on ARM).
 137
 138 //===---------------------------------------------------------------------===//
 139
 140 * Consider this silly example:
 141
 142 double bar(double x) {
 143   double r = foo(3.1);
 144   return x+r;
 145 }
 146
 147 _bar:
 148         stmfd sp!, {r4, r5, r7, lr}
 149         add r7, sp, #8
 150         mov r4, r0
 151         mov r5, r1
 152         fldd d0, LCPI1_0
 153         fmrrd r0, r1, d0
 154         bl _foo
 155         fmdrr d0, r4, r5
 156         fmsr s2, r0
 157         fsitod d1, s2
 158         faddd d0, d1, d0
 159         fmrrd r0, r1, d0
 160         ldmfd sp!, {r4, r5, r7, pc}
 161
 162 Ignore the prologue and epilogue stuff for a second. Note
 163         mov r4, r0
 164         mov r5, r1
 165 the copys to callee-save registers and the fact they are only being used by the
 166 fmdrr instruction. It would have been better had the fmdrr been scheduled
 167 before the call and place the result in a callee-save DPR register. The two
 168 mov ops would not have been necessary.
 169
 170 //===---------------------------------------------------------------------===//
 171
 172 Calling convention related stuff:
 173
 174 * gcc's parameter passing implementation is terrible and we suffer as a result:
 175
 176 e.g.
 177 struct s {
 178   double d1;
 179   int s1;
 180 };
 181
 182 void foo(struct s S) {
 183   printf("%g, %d\n", S.d1, S.s1);
 184 }
 185
 186 'S' is passed via registers r0, r1, r2. But gcc stores them to the stack, and
 187 then reload them to r1, r2, and r3 before issuing the call (r0 contains the
 188 address of the format string):
 189
 190         stmfd   sp!, {r7, lr}
 191         add     r7, sp, #0
 192         sub     sp, sp, #12
 193         stmia   sp, {r0, r1, r2}
 194         ldmia   sp, {r1-r2}
 195         ldr     r0, L5
 196         ldr     r3, [sp, #8]
 197 L2:
 198         add     r0, pc, r0
 199         bl      L_printf$stub
 200
 201 Instead of a stmia, ldmia, and a ldr, wouldn't it be better to do three moves?
 202
 203 * Return an aggregate type is even worse:
 204
 205 e.g.
 206 struct s foo(void) {
 207   struct s S = {1.1, 2};
 208   return S;
 209 }
 210
 211         mov     ip, r0
 212         ldr     r0, L5
 213         sub     sp, sp, #12
 214 L2:
 215         add     r0, pc, r0
 216         @ lr needed for prologue
 217         ldmia   r0, {r0, r1, r2}
 218         stmia   sp, {r0, r1, r2}
 219         stmia   ip, {r0, r1, r2}
 220         mov     r0, ip
 221         add     sp, sp, #12
 222         bx      lr
 223
 224 r0 (and later ip) is the hidden parameter from caller to store the value in. The
 225 first ldmia loads the constants into r0, r1, r2. The last stmia stores r0, r1,
 226 r2 into the address passed in. However, there is one additional stmia that
 227 stores r0, r1, and r2 to some stack location. The store is dead.
 228
 229 The llvm-gcc generated code looks like this:
 230
 231 csretcc void %foo(%struct.s* %agg.result) {
 232 entry:
 233         %S = alloca %struct.s, align 4          ; <%struct.s*> [#uses=1]
 234         %memtmp = alloca %struct.s              ; <%struct.s*> [#uses=1]
 235         cast %struct.s* %S to sbyte*            ; <sbyte*>:0 [#uses=2]
 236         call void %llvm.memcpy.i32( sbyte* %0, sbyte* cast ({ double, int }* %C.0.904 to sbyte*), uint 12, uint 4 )
 237         cast %struct.s* %agg.result to sbyte*           ; <sbyte*>:1 [#uses=2]
 238         call void %llvm.memcpy.i32( sbyte* %1, sbyte* %0, uint 12, uint 0 )
 239         cast %struct.s* %memtmp to sbyte*               ; <sbyte*>:2 [#uses=1]
 240         call void %llvm.memcpy.i32( sbyte* %2, sbyte* %1, uint 12, uint 0 )
 241         ret void
 242 }
 243
 244 llc ends up issuing two memcpy's (the first memcpy becomes 3 loads from
 245 constantpool). Perhaps we should 1) fix llvm-gcc so the memcpy is translated
 246 into a number of load and stores, or 2) custom lower memcpy (of small size) to
 247 be ldmia / stmia. I think option 2 is better but the current register
 248 allocator cannot allocate a chunk of registers at a time.
 249
 250 A feasible temporary solution is to use specific physical registers at the
 251 lowering time for small (<= 4 words?) transfer size.
 252
 253 * ARM CSRet calling convention requires the hidden argument to be returned by
 254 the callee.
 255
 256 //===---------------------------------------------------------------------===//
 257
 258 We can definitely do a better job on BB placements to eliminate some branches.
 259 It's very common to see llvm generated assembly code that looks like this:
 260
 261 LBB3:
 262  ...
 263 LBB4:
 264 ...
 265   beq LBB3
 266   b LBB2
 267
 268 If BB4 is the only predecessor of BB3, then we can emit BB3 after BB4. We can
 269 then eliminate beq and and turn the unconditional branch to LBB2 to a bne.
 270
 271 See McCat/18-imp/ComputeBoundingBoxes for an example.
 272
 273 //===---------------------------------------------------------------------===//
 274
 275 Pre-/post- indexed load / stores:
 276
 277 1) We should not make the pre/post- indexed load/store transform if the base ptr
 278 is guaranteed to be live beyond the load/store. This can happen if the base
 279 ptr is live out of the block we are performing the optimization. e.g.
 280
 281 mov r1, r2
 282 ldr r3, [r1], #4
 283 ...
 284
 285 vs.
 286
 287 ldr r3, [r2]
 288 add r1, r2, #4
 289 ...
 290
 291 In most cases, this is just a wasted optimization. However, sometimes it can
 292 negatively impact the performance because two-address code is more restrictive
 293 when it comes to scheduling.
 294
 295 Unfortunately, liveout information is currently unavailable during DAG combine
 296 time.
 297
 298 2) Consider spliting a indexed load / store into a pair of add/sub + load/store
 299    to solve #1 (in TwoAddressInstructionPass.cpp).
 300
 301 3) Enhance LSR to generate more opportunities for indexed ops.
 302
 303 4) Once we added support for multiple result patterns, write indexed loads
 304    patterns instead of C++ instruction selection code.
 305
 306 5) Use VLDM / VSTM to emulate indexed FP load / store.
 307
 308 //===---------------------------------------------------------------------===//
 309
 310 Implement support for some more tricky ways to materialize immediates.  For
 311 example, to get 0xffff8000, we can use:
 312
 313 mov r9, #&3f8000
 314 sub r9, r9, #&400000
 315
 316 //===---------------------------------------------------------------------===//
 317
 318 We sometimes generate multiple add / sub instructions to update sp in prologue
 319 and epilogue if the inc / dec value is too large to fit in a single immediate
 320 operand. In some cases, perhaps it might be better to load the value from a
 321 constantpool instead.
 322
 323 //===---------------------------------------------------------------------===//
 324
 325 GCC generates significantly better code for this function.
 326
 327 int foo(int StackPtr, unsigned char *Line, unsigned char *Stack, int LineLen) {
 328     int i = 0;
 329
 330     if (StackPtr != 0) {
 331        while (StackPtr != 0 && i < (((LineLen) < (32768))? (LineLen) : (32768)))
 332           Line[i++] = Stack[--StackPtr];
 333         if (LineLen > 32768)
 334         {
 335             while (StackPtr != 0 && i < LineLen)
 336             {
 337                 i++;
 338                 --StackPtr;
 339             }
 340         }
 341     }
 342     return StackPtr;
 343 }
 344
 345 //===---------------------------------------------------------------------===//
 346
 347 This should compile to the mlas instruction:
 348 int mlas(int x, int y, int z) { return ((x * y + z) < 0) ? 7 : 13; }
 349
 350 //===---------------------------------------------------------------------===//
 351
 352 At some point, we should triage these to see if they still apply to us:
 353
 354 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19598
 355 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18560
 356 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27016
 357
 358 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11831
 359 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11826
 360 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11825
 361 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11824
 362 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11823
 363 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11820
 364 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10982
 365
 366 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10242
 367 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9831
 368 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9760
 369 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9759
 370 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9703
 371 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9702
 372 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9663
 373
 374 http://www.inf.u-szeged.hu/gcc-arm/
 375 http://citeseer.ist.psu.edu/debus04linktime.html
 376
 377 //===---------------------------------------------------------------------===//
 378
 379 gcc generates smaller code for this function at -O2 or -Os:
 380
 381 void foo(signed char* p) {
 382   if (*p == 3)
 383      bar();
 384    else if (*p == 4)
 385     baz();
 386   else if (*p == 5)
 387     quux();
 388 }
 389
 390 llvm decides it's a good idea to turn the repeated if...else into a
 391 binary tree, as if it were a switch; the resulting code requires -1
 392 compare-and-branches when *p<=2 or *p==5, the same number if *p==4
 393 or *p>6, and +1 if *p==3.  So it should be a speed win
 394 (on balance).  However, the revised code is larger, with 4 conditional
 395 branches instead of 3.
 396
 397 More seriously, there is a byte->word extend before
 398 each comparison, where there should be only one, and the condition codes
 399 are not remembered when the same two values are compared twice.
 400
 401 //===---------------------------------------------------------------------===//
 402
 403 More LSR enhancements possible:
 404
 405 1. Teach LSR about pre- and post- indexed ops to allow iv increment be merged
 406    in a load / store.
 407 2. Allow iv reuse even when a type conversion is required. For example, i8
 408    and i32 load / store addressing modes are identical.
 409
 410
 411 //===---------------------------------------------------------------------===//
 412
 413 This:
 414
 415 int foo(int a, int b, int c, int d) {
 416   long long acc = (long long)a * (long long)b;
 417   acc += (long long)c * (long long)d;
 418   return (int)(acc >> 32);
 419 }
 420
 421 Should compile to use SMLAL (Signed Multiply Accumulate Long) which multiplies
 422 two signed 32-bit values to produce a 64-bit value, and accumulates this with
 423 a 64-bit value.
 424
 425 We currently get this with both v4 and v6:
 426
 427 _foo:
 428         smull r1, r0, r1, r0
 429         smull r3, r2, r3, r2
 430         adds r3, r3, r1
 431         adc r0, r2, r0
 432         bx lr
 433
 434 //===---------------------------------------------------------------------===//
 435
 436 This:
 437         #include <algorithm>
 438         std::pair<unsigned, bool> full_add(unsigned a, unsigned b)
 439         { return std::make_pair(a + b, a + b < a); }
 440         bool no_overflow(unsigned a, unsigned b)
 441         { return !full_add(a, b).second; }
 442
 443 Should compile to:
 444
 445 _Z8full_addjj:
 446         adds    r2, r1, r2
 447         movcc   r1, #0
 448         movcs   r1, #1
 449         str     r2, [r0, #0]
 450         strb    r1, [r0, #4]
 451         mov     pc, lr
 452
 453 _Z11no_overflowjj:
 454         cmn     r0, r1
 455         movcs   r0, #0
 456         movcc   r0, #1
 457         mov     pc, lr
 458
 459 not:
 460
 461 __Z8full_addjj:
 462         add r3, r2, r1
 463         str r3, [r0]
 464         mov r2, #1
 465         mov r12, #0
 466         cmp r3, r1
 467         movlo r12, r2
 468         str r12, [r0, #+4]
 469         bx lr
 470 __Z11no_overflowjj:
 471         add r3, r1, r0
 472         mov r2, #1
 473         mov r1, #0
 474         cmp r3, r0
 475         movhs r1, r2
 476         mov r0, r1
 477         bx lr
 478
 479 //===---------------------------------------------------------------------===//
 480
 481 Some of the NEON intrinsics may be appropriate for more general use, either
 482 as target-independent intrinsics or perhaps elsewhere in the ARM backend.
 483 Some of them may also be lowered to target-independent SDNodes, and perhaps
 484 some new SDNodes could be added.
 485
 486 For example, maximum, minimum, and absolute value operations are well-defined
 487 and standard operations, both for vector and scalar types.
 488
 489 The current NEON-specific intrinsics for count leading zeros and count one
 490 bits could perhaps be replaced by the target-independent ctlz and ctpop
 491 intrinsics.  It may also make sense to add a target-independent "ctls"
 492 intrinsic for "count leading sign bits".  Likewise, the backend could use
 493 the target-independent SDNodes for these operations.
 494
 495 ARMv6 has scalar saturating and halving adds and subtracts.  The same
 496 intrinsics could possibly be used for both NEON's vector implementations of
 497 those operations and the ARMv6 scalar versions.
 498
 499 //===---------------------------------------------------------------------===//
 500
 501 ARM::MOVCCr is commutable (by flipping the condition). But we need to implement
 502 ARMInstrInfo::commuteInstruction() to support it.
 503
 504 //===---------------------------------------------------------------------===//
 505
 506 Split out LDR (literal) from normal ARM LDR instruction. Also consider spliting
 507 LDR into imm12 and so_reg forms. This allows us to clean up some code. e.g.
 508 ARMLoadStoreOptimizer does not need to look at LDR (literal) and LDR (so_reg)
 509 while ARMConstantIslandPass only need to worry about LDR (literal).
 510
 511 //===---------------------------------------------------------------------===//
 512
 513 Constant island pass should make use of full range SoImm values for LEApcrel.
 514 Be careful though as the last attempt caused infinite looping on lencod.
 515
 516 //===---------------------------------------------------------------------===//
 517
 518 Predication issue. This function:
 519
 520 extern unsigned array[ 128 ];
 521 int     foo( int x ) {
 522   int     y;
 523   y = array[ x & 127 ];
 524   if ( x & 128 )
 525      y = 123456789 & ( y >> 2 );
 526   else
 527      y = 123456789 & y;
 528   return y;
 529 }
 530
 531 compiles to:
 532
 533 _foo:
 534         and r1, r0, #127
 535         ldr r2, LCPI1_0
 536         ldr r2, [r2]
 537         ldr r1, [r2, +r1, lsl #2]
 538         mov r2, r1, lsr #2
 539         tst r0, #128
 540         moveq r2, r1
 541         ldr r0, LCPI1_1
 542         and r0, r2, r0
 543         bx lr
 544
 545 It would be better to do something like this, to fold the shift into the
 546 conditional move:
 547
 548         and r1, r0, #127
 549         ldr r2, LCPI1_0
 550         ldr r2, [r2]
 551         ldr r1, [r2, +r1, lsl #2]
 552         tst r0, #128
 553         movne r1, r1, lsr #2
 554         ldr r0, LCPI1_1
 555         and r0, r1, r0
 556         bx lr
 557
 558 it saves an instruction and a register.
 559
 560 //===---------------------------------------------------------------------===//
 561
 562 It might be profitable to cse MOVi16 if there are lots of 32-bit immediates
 563 with the same bottom half.
 564
 565 //===---------------------------------------------------------------------===//
 566
 567 Robert Muth started working on an alternate jump table implementation that
 568 does not put the tables in-line in the text.  This is more like the llvm
 569 default jump table implementation.  This might be useful sometime.  Several
 570 revisions of patches are on the mailing list, beginning at:
 571 http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-June/022763.html
 572
 573 //===---------------------------------------------------------------------===//
 574
 575 Make use of the "rbit" instruction.
 576
 577 //===---------------------------------------------------------------------===//
 578
 579 Take a look at test/CodeGen/Thumb2/machine-licm.ll. ARM should be taught how
 580 to licm and cse the unnecessary load from cp#1.
 581
 582 //===---------------------------------------------------------------------===//
 583
 584 The CMN instruction sets the flags like an ADD instruction, while CMP sets
 585 them like a subtract. Therefore to be able to use CMN for comparisons other
 586 than the Z bit, we'll need additional logic to reverse the conditionals
 587 associated with the comparison. Perhaps a pseudo-instruction for the comparison,
 588 with a post-codegen pass to clean up and handle the condition codes?
 589 See PR5694 for testcase.