717 lines · plain
1//===---------------------------------------------------------------------===//2// Random ideas for the ARM backend.3//===---------------------------------------------------------------------===//4 5Reimplement 'select' in terms of 'SEL'.6 7* We would really like to support UXTAB16, but we need to prove that the8 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 13A few ARMv6T2 ops should be pattern matched: BFI, SBFX, and UBFX14 15Interesting optimization for PIC codegen on arm-linux:16http://gcc.gnu.org/bugzilla/show_bug.cgi?id=4312917 18//===---------------------------------------------------------------------===//19 20Crazy idea: Consider code that uses lots of 8-bit or 16-bit values. By the21time regalloc happens, these values are now in a 32-bit register, usually with22the top-bits known to be sign or zero extended. If spilled, we should be able23to spill these to a 8-bit or 16-bit stack slot, zero or sign extending as part24of the reload.25 26Doing this reduces the size of the stack frame (important for thumb etc), and27also increases the likelihood that we will be able to reload multiple values28from the stack with a single load.29 30//===---------------------------------------------------------------------===//31 32The constant island pass is in good shape. Some cleanups might be desirable,33but there is unlikely to be much improvement in the generated code.34 351. There may be some advantage to trying to be smarter about the initial36placement, rather than putting everything at the end.37 382. There might be some compile-time efficiency to be had by representing39consecutive islands as a single block rather than multiple blocks.40 413. Use a priority queue to sort constant pool users in inverse order of42 position so we always process the one closed to the end of functions43 first. This may simply CreateNewWater.44 45//===---------------------------------------------------------------------===//46 47Eliminate copysign custom expansion. We are still generating crappy code with48default expansion + if-conversion.49 50//===---------------------------------------------------------------------===//51 52Eliminate one instruction from:53 54define i32 @_Z6slow4bii(i32 %x, i32 %y) {55 %tmp = icmp sgt i32 %x, %y56 %retval = select i1 %tmp, i32 %x, i32 %y57 ret i32 %retval58}59 60__Z6slow4bii:61 cmp r0, r162 movgt r1, r063 mov r0, r164 bx lr65=>66 67__Z6slow4bii:68 cmp r0, r169 movle r0, r170 bx lr71 72//===---------------------------------------------------------------------===//73 74Implement long long "X-3" with instructions that fold the immediate in. These75were disabled due to badness with the ARM carry flag on subtracts.76 77//===---------------------------------------------------------------------===//78 79More load / store optimizations:801) Better representation for block transfer? This is from Olden/power:81 82 fldd d0, [r4]83 fstd d0, [r4, #+32]84 fldd d0, [r4, #+8]85 fstd d0, [r4, #+40]86 fldd d0, [r4, #+16]87 fstd d0, [r4, #+48]88 fldd d0, [r4, #+24]89 fstd d0, [r4, #+56]90 91If we can spare the registers, it would be better to use fldm and fstm here.92Need major register allocator enhancement though.93 942) Can we recognize the relative position of constantpool entries? i.e. Treat95 96 ldr r0, LCPI17_397 ldr r1, LCPI17_498 ldr r2, LCPI17_599 100 as101 ldr r0, LCPI17102 ldr r1, LCPI17+4103 ldr r2, LCPI17+8104 105 Then the ldr's can be combined into a single ldm. See Olden/power.106 107Note for ARM v4 gcc uses ldmia to load a pair of 32-bit values to represent a108double 64-bit FP constant:109 110 adr r0, L6111 ldmia r0, {r0-r1}112 113 .align 2114L6:115 .long -858993459116 .long 1074318540117 1183) struct copies appear to be done field by field119instead of by words, at least sometimes:120 121struct foo { int x; short s; char c1; char c2; };122void cpy(struct foo*a, struct foo*b) { *a = *b; }123 124llvm code (-O2)125 ldrb r3, [r1, #+6]126 ldr r2, [r1]127 ldrb r12, [r1, #+7]128 ldrh r1, [r1, #+4]129 str r2, [r0]130 strh r1, [r0, #+4]131 strb r3, [r0, #+6]132 strb r12, [r0, #+7]133gcc code (-O2)134 ldmia r1, {r1-r2}135 stmia r0, {r1-r2}136 137In this benchmark poor handling of aggregate copies has shown up as138having a large effect on size, and possibly speed as well (we don't have139a good way to measure on ARM).140 141//===---------------------------------------------------------------------===//142 143* Consider this silly example:144 145double bar(double x) {146 double r = foo(3.1);147 return x+r;148}149 150_bar:151 stmfd sp!, {r4, r5, r7, lr}152 add r7, sp, #8153 mov r4, r0154 mov r5, r1155 fldd d0, LCPI1_0156 fmrrd r0, r1, d0157 bl _foo158 fmdrr d0, r4, r5159 fmsr s2, r0160 fsitod d1, s2161 faddd d0, d1, d0162 fmrrd r0, r1, d0163 ldmfd sp!, {r4, r5, r7, pc}164 165Ignore the prologue and epilogue stuff for a second. Note166 mov r4, r0167 mov r5, r1168the copys to callee-save registers and the fact they are only being used by the169fmdrr instruction. It would have been better had the fmdrr been scheduled170before the call and place the result in a callee-save DPR register. The two171mov ops would not have been necessary.172 173//===---------------------------------------------------------------------===//174 175Calling convention related stuff:176 177* gcc's parameter passing implementation is terrible and we suffer as a result:178 179e.g.180struct s {181 double d1;182 int s1;183};184 185void foo(struct s S) {186 printf("%g, %d\n", S.d1, S.s1);187}188 189'S' is passed via registers r0, r1, r2. But gcc stores them to the stack, and190then reload them to r1, r2, and r3 before issuing the call (r0 contains the191address of the format string):192 193 stmfd sp!, {r7, lr}194 add r7, sp, #0195 sub sp, sp, #12196 stmia sp, {r0, r1, r2}197 ldmia sp, {r1-r2}198 ldr r0, L5199 ldr r3, [sp, #8]200L2:201 add r0, pc, r0202 bl L_printf$stub203 204Instead of a stmia, ldmia, and a ldr, wouldn't it be better to do three moves?205 206* Return an aggregate type is even worse:207 208e.g.209struct s foo(void) {210 struct s S = {1.1, 2};211 return S;212}213 214 mov ip, r0215 ldr r0, L5216 sub sp, sp, #12217L2:218 add r0, pc, r0219 @ lr needed for prologue220 ldmia r0, {r0, r1, r2}221 stmia sp, {r0, r1, r2}222 stmia ip, {r0, r1, r2}223 mov r0, ip224 add sp, sp, #12225 bx lr226 227r0 (and later ip) is the hidden parameter from caller to store the value in. The228first ldmia loads the constants into r0, r1, r2. The last stmia stores r0, r1,229r2 into the address passed in. However, there is one additional stmia that230stores r0, r1, and r2 to some stack location. The store is dead.231 232The llvm-gcc generated code looks like this:233 234csretcc void %foo(%struct.s* %agg.result) {235entry:236 %S = alloca %struct.s, align 4 ; <%struct.s*> [#uses=1]237 %memtmp = alloca %struct.s ; <%struct.s*> [#uses=1]238 cast %struct.s* %S to sbyte* ; <sbyte*>:0 [#uses=2]239 call void %llvm.memcpy.i32( sbyte* %0, sbyte* cast ({ double, int }* %C.0.904 to sbyte*), uint 12, uint 4 )240 cast %struct.s* %agg.result to sbyte* ; <sbyte*>:1 [#uses=2]241 call void %llvm.memcpy.i32( sbyte* %1, sbyte* %0, uint 12, uint 0 )242 cast %struct.s* %memtmp to sbyte* ; <sbyte*>:2 [#uses=1]243 call void %llvm.memcpy.i32( sbyte* %2, sbyte* %1, uint 12, uint 0 )244 ret void245}246 247llc ends up issuing two memcpy's (the first memcpy becomes 3 loads from248constantpool). Perhaps we should 1) fix llvm-gcc so the memcpy is translated249into a number of load and stores, or 2) custom lower memcpy (of small size) to250be ldmia / stmia. I think option 2 is better but the current register251allocator cannot allocate a chunk of registers at a time.252 253A feasible temporary solution is to use specific physical registers at the254lowering time for small (<= 4 words?) transfer size.255 256* ARM CSRet calling convention requires the hidden argument to be returned by257the callee.258 259//===---------------------------------------------------------------------===//260 261We can definitely do a better job on BB placements to eliminate some branches.262It's very common to see llvm generated assembly code that looks like this:263 264LBB3:265 ...266LBB4:267...268 beq LBB3269 b LBB2270 271If BB4 is the only predecessor of BB3, then we can emit BB3 after BB4. We can272then eliminate beq and turn the unconditional branch to LBB2 to a bne.273 274See McCat/18-imp/ComputeBoundingBoxes for an example.275 276//===---------------------------------------------------------------------===//277 278Pre-/post- indexed load / stores:279 2801) We should not make the pre/post- indexed load/store transform if the base ptr281is guaranteed to be live beyond the load/store. This can happen if the base282ptr is live out of the block we are performing the optimization. e.g.283 284mov r1, r2285ldr r3, [r1], #4286...287 288vs.289 290ldr r3, [r2]291add r1, r2, #4292...293 294In most cases, this is just a wasted optimization. However, sometimes it can295negatively impact the performance because two-address code is more restrictive296when it comes to scheduling.297 298Unfortunately, liveout information is currently unavailable during DAG combine299time.300 3012) Consider spliting a indexed load / store into a pair of add/sub + load/store302 to solve #1 (in TwoAddressInstructionPass.cpp).303 3043) Enhance LSR to generate more opportunities for indexed ops.305 3064) Once we added support for multiple result patterns, write indexed loads307 patterns instead of C++ instruction selection code.308 3095) Use VLDM / VSTM to emulate indexed FP load / store.310 311//===---------------------------------------------------------------------===//312 313Implement support for some more tricky ways to materialize immediates. For314example, to get 0xffff8000, we can use:315 316mov r9, #&3f8000317sub r9, r9, #&400000318 319//===---------------------------------------------------------------------===//320 321We sometimes generate multiple add / sub instructions to update sp in prologue322and epilogue if the inc / dec value is too large to fit in a single immediate323operand. In some cases, perhaps it might be better to load the value from a324constantpool instead.325 326//===---------------------------------------------------------------------===//327 328GCC generates significantly better code for this function.329 330int foo(int StackPtr, unsigned char *Line, unsigned char *Stack, int LineLen) {331 int i = 0;332 333 if (StackPtr != 0) {334 while (StackPtr != 0 && i < (((LineLen) < (32768))? (LineLen) : (32768)))335 Line[i++] = Stack[--StackPtr];336 if (LineLen > 32768)337 {338 while (StackPtr != 0 && i < LineLen)339 {340 i++;341 --StackPtr;342 }343 }344 }345 return StackPtr;346}347 348//===---------------------------------------------------------------------===//349 350This should compile to the mlas instruction:351int mlas(int x, int y, int z) { return ((x * y + z) < 0) ? 7 : 13; }352 353//===---------------------------------------------------------------------===//354 355At some point, we should triage these to see if they still apply to us:356 357http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19598358http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18560359http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27016360 361http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11831362http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11826363http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11825364http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11824365http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11823366http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11820367http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10982368 369http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10242370http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9831371http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9760372http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9759373http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9703374http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9702375http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9663376 377http://www.inf.u-szeged.hu/gcc-arm/378http://citeseer.ist.psu.edu/debus04linktime.html379 380//===---------------------------------------------------------------------===//381 382gcc generates smaller code for this function at -O2 or -Os:383 384void foo(signed char* p) {385 if (*p == 3)386 bar();387 else if (*p == 4)388 baz();389 else if (*p == 5)390 quux();391}392 393llvm decides it's a good idea to turn the repeated if...else into a394binary tree, as if it were a switch; the resulting code requires -1395compare-and-branches when *p<=2 or *p==5, the same number if *p==4396or *p>6, and +1 if *p==3. So it should be a speed win397(on balance). However, the revised code is larger, with 4 conditional398branches instead of 3.399 400More seriously, there is a byte->word extend before401each comparison, where there should be only one, and the condition codes402are not remembered when the same two values are compared twice.403 404//===---------------------------------------------------------------------===//405 406More LSR enhancements possible:407 4081. Teach LSR about pre- and post- indexed ops to allow iv increment be merged409 in a load / store.4102. Allow iv reuse even when a type conversion is required. For example, i8411 and i32 load / store addressing modes are identical.412 413 414//===---------------------------------------------------------------------===//415 416This:417 418int foo(int a, int b, int c, int d) {419 long long acc = (long long)a * (long long)b;420 acc += (long long)c * (long long)d;421 return (int)(acc >> 32);422}423 424Should compile to use SMLAL (Signed Multiply Accumulate Long) which multiplies425two signed 32-bit values to produce a 64-bit value, and accumulates this with426a 64-bit value.427 428We currently get this with both v4 and v6:429 430_foo:431 smull r1, r0, r1, r0432 smull r3, r2, r3, r2433 adds r3, r3, r1434 adc r0, r2, r0435 bx lr436 437//===---------------------------------------------------------------------===//438 439This:440 #include <algorithm>441 std::pair<unsigned, bool> full_add(unsigned a, unsigned b)442 { return std::make_pair(a + b, a + b < a); }443 bool no_overflow(unsigned a, unsigned b)444 { return !full_add(a, b).second; }445 446Should compile to:447 448_Z8full_addjj:449 adds r2, r1, r2450 movcc r1, #0451 movcs r1, #1452 str r2, [r0, #0]453 strb r1, [r0, #4]454 mov pc, lr455 456_Z11no_overflowjj:457 cmn r0, r1458 movcs r0, #0459 movcc r0, #1460 mov pc, lr461 462not:463 464__Z8full_addjj:465 add r3, r2, r1466 str r3, [r0]467 mov r2, #1468 mov r12, #0469 cmp r3, r1470 movlo r12, r2471 str r12, [r0, #+4]472 bx lr473__Z11no_overflowjj:474 add r3, r1, r0475 mov r2, #1476 mov r1, #0477 cmp r3, r0478 movhs r1, r2479 mov r0, r1480 bx lr481 482//===---------------------------------------------------------------------===//483 484Some of the NEON intrinsics may be appropriate for more general use, either485as target-independent intrinsics or perhaps elsewhere in the ARM backend.486Some of them may also be lowered to target-independent SDNodes, and perhaps487some new SDNodes could be added.488 489For example, maximum, minimum, and absolute value operations are well-defined490and standard operations, both for vector and scalar types.491 492The current NEON-specific intrinsics for count leading zeros and count one493bits could perhaps be replaced by the target-independent ctlz and ctpop494intrinsics. It may also make sense to add a target-independent "ctls"495intrinsic for "count leading sign bits". Likewise, the backend could use496the target-independent SDNodes for these operations.497 498ARMv6 has scalar saturating and halving adds and subtracts. The same499intrinsics could possibly be used for both NEON's vector implementations of500those operations and the ARMv6 scalar versions.501 502//===---------------------------------------------------------------------===//503 504Split out LDR (literal) from normal ARM LDR instruction. Also consider spliting505LDR into imm12 and so_reg forms. This allows us to clean up some code. e.g.506ARMLoadStoreOptimizer does not need to look at LDR (literal) and LDR (so_reg)507while ARMConstantIslandPass only need to worry about LDR (literal).508 509//===---------------------------------------------------------------------===//510 511Constant island pass should make use of full range SoImm values for LEApcrel.512Be careful though as the last attempt caused infinite looping on lencod.513 514//===---------------------------------------------------------------------===//515 516Predication issue. This function:517 518extern unsigned array[ 128 ];519int foo( int x ) {520 int y;521 y = array[ x & 127 ];522 if ( x & 128 )523 y = 123456789 & ( y >> 2 );524 else525 y = 123456789 & y;526 return y;527}528 529compiles to:530 531_foo:532 and r1, r0, #127533 ldr r2, LCPI1_0534 ldr r2, [r2]535 ldr r1, [r2, +r1, lsl #2]536 mov r2, r1, lsr #2537 tst r0, #128538 moveq r2, r1539 ldr r0, LCPI1_1540 and r0, r2, r0541 bx lr542 543It would be better to do something like this, to fold the shift into the544conditional move:545 546 and r1, r0, #127547 ldr r2, LCPI1_0548 ldr r2, [r2]549 ldr r1, [r2, +r1, lsl #2]550 tst r0, #128551 movne r1, r1, lsr #2552 ldr r0, LCPI1_1553 and r0, r1, r0554 bx lr555 556it saves an instruction and a register.557 558//===---------------------------------------------------------------------===//559 560It might be profitable to cse MOVi16 if there are lots of 32-bit immediates561with the same bottom half.562 563//===---------------------------------------------------------------------===//564 565Robert Muth started working on an alternate jump table implementation that566does not put the tables in-line in the text. This is more like the llvm567default jump table implementation. This might be useful sometime. Several568revisions of patches are on the mailing list, beginning at:569http://lists.llvm.org/pipermail/llvm-dev/2009-June/022763.html570 571//===---------------------------------------------------------------------===//572 573Make use of the "rbit" instruction.574 575//===---------------------------------------------------------------------===//576 577Take a look at test/CodeGen/Thumb2/machine-licm.ll. ARM should be taught how578to licm and cse the unnecessary load from cp#1.579 580//===---------------------------------------------------------------------===//581 582The CMN instruction sets the flags like an ADD instruction, while CMP sets583them like a subtract. Therefore to be able to use CMN for comparisons other584than the Z bit, we'll need additional logic to reverse the conditionals585associated with the comparison. Perhaps a pseudo-instruction for the comparison,586with a post-codegen pass to clean up and handle the condition codes?587See PR5694 for testcase.588 589//===---------------------------------------------------------------------===//590 591Given the following on armv5:592int test1(int A, int B) {593 return (A&-8388481)|(B&8388480);594}595 596We currently generate:597 ldr r2, .LCPI0_0598 and r0, r0, r2599 ldr r2, .LCPI0_1600 and r1, r1, r2601 orr r0, r1, r0602 bx lr603 604We should be able to replace the second ldr+and with a bic (i.e. reuse the605constant which was already loaded). Not sure what's necessary to do that.606 607//===---------------------------------------------------------------------===//608 609The code generated for bswap on armv4/5 (CPUs without rev) is less than ideal:610 611int a(int x) { return __builtin_bswap32(x); }612 613a:614 mov r1, #255, 24615 mov r2, #255, 16616 and r1, r1, r0, lsr #8617 and r2, r2, r0, lsl #8618 orr r1, r1, r0, lsr #24619 orr r0, r2, r0, lsl #24620 orr r0, r0, r1621 bx lr622 623Something like the following would be better (fewer instructions/registers):624 eor r1, r0, r0, ror #16625 bic r1, r1, #0xff0000626 mov r1, r1, lsr #8627 eor r0, r1, r0, ror #8628 bx lr629 630A custom Thumb version would also be a slight improvement over the generic631version.632 633//===---------------------------------------------------------------------===//634 635Consider the following simple C code:636 637void foo(unsigned char *a, unsigned char *b, int *c) {638 if ((*a | *b) == 0) *c = 0;639}640 641currently llvm-gcc generates something like this (nice branchless code I'd say):642 643 ldrb r0, [r0]644 ldrb r1, [r1]645 orr r0, r1, r0646 tst r0, #255647 moveq r0, #0648 streq r0, [r2]649 bx lr650 651Note that both "tst" and "moveq" are redundant.652 653//===---------------------------------------------------------------------===//654 655When loading immediate constants with movt/movw, if there are multiple656constants needed with the same low 16 bits, and those values are not live at657the same time, it would be possible to use a single movw instruction, followed658by multiple movt instructions to rewrite the high bits to different values.659For example:660 661 volatile store i32 -1, i32* inttoptr (i32 1342210076 to i32*), align 4,662 !tbaa663!0664 volatile store i32 -1, i32* inttoptr (i32 1342341148 to i32*), align 4,665 !tbaa666!0667 668is compiled and optimized to:669 670 movw r0, #32796671 mov.w r1, #-1672 movt r0, #20480673 str r1, [r0]674 movw r0, #32796 @ <= this MOVW is not needed, value is there already675 movt r0, #20482676 str r1, [r0]677 678//===---------------------------------------------------------------------===//679 680Improve codegen for select's:681if (x != 0) x = 1682if (x == 1) x = 1683 684ARM codegen used to look like this:685 mov r1, r0686 cmp r1, #1687 mov r0, #0688 moveq r0, #1689 690The naive lowering select between two different values. It should recognize the691test is equality test so it's more a conditional move rather than a select:692 cmp r0, #1693 movne r0, #0694 695Currently this is a ARM specific dag combine. We probably should make it into a696target-neutral one.697 698//===---------------------------------------------------------------------===//699 700Clean up the test/MC/ARM files to have more robust register choices.701 702R0 should not be used as a register operand in the assembler tests as it's then703not possible to distinguish between a correct encoding and a missing operand704encoding, as zero is the default value for the binary encoder.705e.g.,706 add r0, r0 // bad707 add r3, r5 // good708 709Register operands should be distinct. That is, when the encoding does not710require two syntactical operands to refer to the same register, two different711registers should be used in the test so as to catch errors where the712operands are swapped in the encoding.713e.g.,714 subs.w r1, r1, r1 // bad715 subs.w r1, r2, r3 // good716 717