ARM: use "add" instead of "orr" for code size

[t.p.northover]

Summary

The implementation here is a bit nasty, but the basic idea is that Thumb has more 16-bit encodings available for ADD than it does for ORR. Combine that with LLVM's (slightly perverse) desire to convert adds to ors as the canonical form and we end up with unnecessary bloat on Thumb targets.

So this patch tries to undo that canonicalization where possible. The implementation is not pretty, but I'm not sure there's a better way.

[efriedma]

llvm/lib/Target/ARM/ARMInstrThumb.td

1017

T1Pat?

Are you intentionally avoiding transforming x|256?

[t.p.northover]

llvm/lib/Target/ARM/ARMInstrThumb.td

1017

T1Pat?

That seems to require "IsThumb1Only", which I don't want.

Are you intentionally avoiding transforming x|256?

Yes. That would result in a MOV/ADD pair (with restricted register classes). With this patch we get ORR.W with an immediate, which is probably better all round.

It's a bit of a heuristic, and not optimal when both ADD and ORR require a separate immediate. But by that point the only benefit is whether the destination register is tied so I decided to draw the line before that point in my initial patch.

[efriedma]

llvm/lib/Target/ARM/ARMInstrThumb.td

1017

That seems to require "IsThumb1Only", which I don't want.

I think it's appropriate.

The way ISel for Thumb2 works is that we never select Thumb1 instructions, which have restrictive register allocation requirements (most instructions only take tGPR). Thumb2SizeReduce runs after register allocation and shrinks the instructions which are equivalent to a Thumb instruction. (This sometimes leads to bad register allocation decisions because the register allocator isn't aware of size reduction, but that's orthogonal to this patch.)

So in Thumb2 mode, you want five patterns, selecting the following five instructions: t2ADDri, t2ADDri12, t2SUBri, t2SUBri12, and t2ADDrr. And you don't want any patterns to select tADDi3, tADDi8, tSUBi8, or tADDrr.

[t.p.northover]

llvm/lib/Target/ARM/ARMInstrThumb.td

1017

OK, I'm convinced by your arguments on the Thumb1 side, I hadn't quite realised that was how it worked. But I don't think t2 side is quite right.

For a start, you generally can't map an OR to a SUB (maybe an XOR, but that's getting pretty convoluted). Also, I don't think the t2ADDri12 is needed: any squashable immediate would already be covered by t2ADDri.

t2ADDrr is probably what I had forgotten and led me to my Thumb1 mistake. I'll upload a new patch implementing those bits.

[t.p.northover]

Switched to T1Pat on Thumb-1 side and added t2ADDrr pattern.

[efriedma]

llvm/lib/Target/ARM/ARMInstrThumb.td

1017

you generally can't map an OR to a SUB

t2SUBri is just an ISD::ADD with a negated immediate.

any squashable immediate would already be covered by t2ADDri

Sure, but you still save an instruction over the alternative (movw+orrs).

1018

Maybe allow immediates not in the range 0-255 here? Or you could just allow any operand, and depend on pattern precedence to avoid matching this when one of the immediate forms would match instead.

[efriedma]

Also, I'd like to see some test coverage for the immediate patterns.

[t.p.northover]

llvm/lib/Target/ARM/ARMInstrThumb.td

1017

t2SUBri is just an ISD::ADD with a negated immediate.

OK, but that negation makes it a pretty unlikely combination.

Sure, but you still save an instruction over the alternative (movw+orrs).

Oh, go on then.

1018

Ah yes, a holdover from when that was covering Thumb-2 I think (I wanted to still allow ORR (imm) and ORN (imm)).

[t.p.northover]

Added t2ADDi12 and tests for the immediate cases.

[efriedma]

LGTM

llvm/lib/Target/ARM/ARMInstrThumb2.td

2606

I guess you could specifically try to check that it isn't t2_so_imm, t2_so_imm_not, or imm0_4095, but probably not worth bothering.

[efriedma]

This was merged in r335119.

llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp

bool SelectShiftRegShifterOperand(SDValue N, SDValue &A,
     return SelectRegShifterOperand(N, A, B, C, false);
   }
   bool SelectShiftImmShifterOperand(SDValue N, SDValue &A,
                                     SDValue &B) {
     // Don't apply the profitability check
     return SelectImmShifterOperand(N, A, B, false);
   }
 
+  bool SelectAddLikeOr(SDNode *Parent, SDValue N, SDValue &Out);
+
   bool SelectAddrModeImm12(SDValue N, SDValue &Base, SDValue &OffImm);
   bool SelectLdStSOReg(SDValue N, SDValue &Base, SDValue &Offset, SDValue &Opc);
 
   bool SelectCMOVPred(SDValue N, SDValue &Pred, SDValue &Reg) {
     const ConstantSDNode *CN = cast<ConstantSDNode>(N);
     Pred = CurDAG->getTargetConstant(CN->getZExtValue(), SDLoc(N), MVT::i32);
     Reg = CurDAG->getRegister(ARM::CPSR, MVT::i32);
     return true;
bool ARMDAGToDAGISel::SelectRegShifterOperand(SDValue N,
   ShReg = N.getOperand(1);
   if (CheckProfitability && !isShifterOpProfitable(N, ShOpcVal, ShImmVal))
     return false;
   Opc = CurDAG->getTargetConstant(ARM_AM::getSORegOpc(ShOpcVal, ShImmVal),
                                   SDLoc(N), MVT::i32);
   return true;
 }
 
+// Determine whether an ISD::OR's operands are suitable to turn the operation
+// into an addition, which often has more compact encodings.
+bool ARMDAGToDAGISel::SelectAddLikeOr(SDNode *Parent, SDValue N, SDValue &Out) {
+  assert(Parent->getOpcode() == ISD::OR && "unexpected parent");
+  Out = N;
+  return CurDAG->haveNoCommonBitsSet(N, Parent->getOperand(1));
+}
+
 
 bool ARMDAGToDAGISel::SelectAddrModeImm12(SDValue N,
                                           SDValue &Base,
                                           SDValue &OffImm) {
   // Match simple R + imm12 operands.
 
   // Base only.
   if (N.getOpcode() != ISD::ADD && N.getOpcode() != ISD::SUB &&

llvm/lib/Target/ARM/ARMInstrThumb.td

def t_addrmode_sp : MemOperand,
                     ComplexPattern<i32, 2, "SelectThumbAddrModeSP", []> {
   let EncoderMethod = "getAddrModeThumbSPOpValue";
   let DecoderMethod = "DecodeThumbAddrModeSP";
   let PrintMethod = "printThumbAddrModeSPOperand";
   let ParserMatchClass = t_addrmode_sp_asm_operand;
   let MIOperandInfo = (ops GPR:$base, i32imm:$offsimm);
 }
 
+// Inspects parent to determine whether an or instruction can be implemented as
+// an add (i.e. whether we know overflow won't occur in the add).
+def AddLikeOrOp : ComplexPattern<i32, 1, "SelectAddLikeOr", [],
+                                 [SDNPWantParent]>;
+
+// Pattern to exclude immediates from matching
+def non_imm32 : PatLeaf<(i32 GPR), [{ return !isa<ConstantSDNode>(N); }]>;
+
 //===----------------------------------------------------------------------===//
 //  Miscellaneous Instructions.
 //
 
 // FIXME: Marking these as hasSideEffects is necessary to prevent machine DCE
 // from removing one half of the matched pairs. That breaks PEI, which assumes
 // these will always be in pairs, and asserts if it finds otherwise. Better way?
 let Defs = [SP], Uses = [SP], hasSideEffects = 1 in {
def tADDhirr : T1pIt<(outs GPR:$Rdn), (ins GPR:$Rn, GPR:$Rm), IIC_iALUr,
     bits<4> Rdn;
     bits<4> Rm;
     let Inst{7}   = Rdn{3};
     let Inst{6-3} = Rm;
     let Inst{2-0} = Rdn{2-0};
   }
 }
 
+// Thumb has more flexible short encodings for ADD than ORR, so use those where
+// possible.
+let AddedComplexity = 20 in
+def : T1Pat<(or AddLikeOrOp:$Rn, imm0_7:$imm), (tADDi3 $Rn, imm0_7:$imm)>;
+
+let AddedComplexity = 10 in
+def : T1Pat<(or AddLikeOrOp:$Rn, imm8_255:$imm), (tADDi8 $Rn, imm8_255:$imm)>;
+
+// Exclude immediates on RHS here to give real or-like instructions that might
+// handle it a chance.
+def : T1Pat<(or AddLikeOrOp:$Rn, non_imm32:$Rm), (tADDrr $Rn, $Rm)>;
+
+
 def : tInstAlias <"add${s}${p} $Rdn, $Rm",
                  (tADDrr tGPR:$Rdn,s_cc_out:$s, tGPR:$Rdn, tGPR:$Rm, pred:$p)>;
 
 def : tInstSubst<"sub${s}${p} $rd, $rn, $imm",
                  (tADDi3 tGPR:$rd, s_cc_out:$s, tGPR:$rn, mod_imm1_7_neg:$imm, pred:$p)>;
 def : tInstSubst<"sub${s}${p} $rdn, $imm",
                  (tADDi8 tGPR:$rdn, s_cc_out:$s, mod_imm8_255_neg:$imm, pred:$p)>;
 

llvm/lib/Target/ARM/ARMInstrThumb2.td

 // FIXME: Disable this pattern on Darwin to workaround an assembler bug.
 def : T2Pat<(or      rGPR:$src, t2_so_imm_not:$imm),
             (t2ORNri rGPR:$src, t2_so_imm_not:$imm)>,
             Requires<[IsThumb2]>;
 
 def : T2Pat<(t2_so_imm_not:$src),
             (t2MVNi t2_so_imm_not:$src)>;
 
+// There are shorter Thumb encodings for ADD than ORR, so to increase
+// Thumb2SizeReduction's chances later on we select a t2ADD for an or where
+// possible.
+let AddedComplexity = 30 in
+def : T2Pat<(or AddLikeOrOp:$Rn, t2_so_imm:$imm),
+            (t2ADDri $Rn, t2_so_imm:$imm)>;
+
+def : T2Pat<(or AddLikeOrOp:$Rn, non_imm32:$Rm),
+            (t2ADDrr $Rn, $Rm)>;
+
 //===----------------------------------------------------------------------===//
 //  Multiply Instructions.
 //
 let isCommutable = 1 in
 def t2MUL: T2ThreeReg<(outs rGPR:$Rd), (ins rGPR:$Rn, rGPR:$Rm), IIC_iMUL32,
                 "mul", "\t$Rd, $Rn, $Rm",
                 [(set rGPR:$Rd, (mul rGPR:$Rn, rGPR:$Rm))]>,
            Sched<[WriteMUL32, ReadMUL, ReadMUL]> {

llvm/test/CodeGen/ARM/shift-combine.ll

 
 ; CHECK-LABEL: test_lshr_load64_4_unaligned
 ; CHECK-BE:         ldr [[HIGH:r[0-9]+]], [r0]
 ; CHECK-BE-NEXT:    ldrh [[LOW:r[0-9]+]], [r0, #4]
 ; CHECK-BE-NEXT:    orr r0, [[LOW]], [[HIGH]], lsl #16
 ; CHECK-V6M:        ldrh [[LOW:r[0-9]+]], [r0, #2]
 ; CHECK-V6M:        ldr [[HIGH:r[0-9]+]], [r0, #4]
 ; CHECK-V6M-NEXT:   lsls [[HIGH]], [[HIGH]], #16
-; CHECK-V6M-NEXT:   orrs r0, r1
+; CHECK-V6M-NEXT:   adds r0, r1, r0
 ; CHECK-ALIGN:      ldr [[HIGH:r[0-9]+]], [r0, #4]
 ; CHECK-ALIGN-NEXT: ldrh [[LOW:r[0-9]+]], [r0, #2]
 ; CHECK-ALIGN-NEXT: orr.w r0, [[LOW]], [[HIGH]], lsl #16
 ; CHECK-ARM:        ldr r0, [r0, #2]
 ; CHECK-THUMB:      ldr.w r0, [r0, #2]
 ; CHECK-COMMON:     bx
 define arm_aapcscc i32 @test_lshr_load64_4_unaligned(i64* %a) {
 entry:

llvm/test/CodeGen/Thumb2/2010-03-15-AsmCCClobber.ll

 %s1 = type { %s3, i32, %s4, i8*, void (i8*, i8*)*, i8*, i32*, i32*, i32*, i32, i64, [1 x i32] }
 %s2 = type { i32 (...)**, %s4 }
 %s3 = type { %s2, i32, i32, i32*, [4 x i8], float, %s4, i8*, i8* }
 %s4 = type { %s5 }
 %s5 = type { i32 }
 
 ; Make sure the cmp is not scheduled before the InlineAsm that clobbers cc.
 ; CHECK: bl _f2
-; CHECK: cmp r0, #0
+; CHECK: cmp {{r[0-9]+}}, #0
 ; CHECK-NOT: cmp
 ; CHECK: InlineAsm Start
 define void @test(%s1* %this, i32 %format, i32 %w, i32 %h, i32 %levels, i32* %s, i8* %data, i32* nocapture %rowbytes, void (i8*, i8*)* %release, i8* %info) nounwind {
 entry:
   %tmp1 = getelementptr inbounds %s1, %s1* %this, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0
   store volatile i32 1, i32* %tmp1, align 4
   %tmp12 = getelementptr inbounds %s1, %s1* %this, i32 0, i32 1
   store i32 %levels, i32* %tmp12, align 4

llvm/test/CodeGen/Thumb2/thumb2-uxtb.ll

 }
 
 define i32 @test10(i32 %p0) {
 ; CHECK-LABEL: test10
 ; CHECK-DSP: mov.w r1, #16253176
 ; CHECK-DSP: and.w r0, r1, r0, lsr #7
 ; CHECK-DSP: lsrs  r1, r0, #5
 ; CHECK-DSP: uxtb16  r1, r1
-; CHECk-DSP: orrs r0, r1
+; CHECk-DSP: adds r0, r1
 
 ; CHECK-NO-DSP: mov.w r1, #16253176
 ; CHECK-NO-DSP: and.w r0, r1, r0, lsr #7
 ; CHECK-NO-DSP: mov.w r1, #458759
 ; CHECK-NO-DSP: and.w r1, r1, r0, lsr #5
-; CHECK-NO-DSP: orrs r0, r1
+; CHECK-NO-DSP: add r0, r1
   %tmp1 = lshr i32 %p0, 7   ; <i32> [#uses=1]
   %tmp2 = and i32 %tmp1, 16253176   ; <i32> [#uses=2]
   %tmp4 = lshr i32 %tmp2, 5   ; <i32> [#uses=1]
   %tmp5 = and i32 %tmp4, 458759   ; <i32> [#uses=1]
   %tmp7 = or i32 %tmp5, %tmp2   ; <i32> [#uses=1]
   ret i32 %tmp7
 }