[Thumb] Select a BIC instead of AND if the immediate can be encoded more optimally negated

[jmolloy]

Summary

If an immediate is only used in an AND node, it is possible that the immediate can be more optimally materialized when negated. If this is the case, we can negate the immediate and use a BIC instead;

  int i(int a) {
    return a & 0xfffffeec;
  }

Used to produce:
    ldr r1, [CONSTPOOL]
    ands r0, r1
  CONSTPOOL: 0xfffffeec

And now produces:
    movs    r1, #255
    adds    r1, #20  ; Less costly immediate generation
    bics    r0, r1

[mcrosier]

lib/Target/ARM/ARMISelDAGToDAG.cpp

2799–2838

Please add a very brief description here similar to what is in your summary.

2808

How about 'TransformImm', 'UseBIC' or 'PreferBIC'?

[sbaranga]

lib/Target/ARM/ARMISelDAGToDAG.cpp

2801

If the constant ends up as an immediate, why limit it to only having one use?

[jmolloy]

lib/Target/ARM/ARMISelDAGToDAG.cpp

2801

The constant doesn't end up as an immediate. That's what the "ImmTransform" check below is doing - if it would just be promoted to an immediate, don't bother and bail out.

But if it can't be an immediate, then do the transform. And in that case we don't want to create more constants.

[jmolloy]

Thanks Chad and Silviu for the review.

Updated according to Chad's comments, and hopefully the new name "PreferImmediateEncoding" should address Silviu's comment too.

[mcrosier]

LGTM. Feel free to allow Silviu to comment before committing.

[sbaranga]

LGTM!

[jmolloy]

Thanks! committed in r272251.

lib/Target/ARM/ARMISelDAGToDAG.cpp

if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1))) {
         }
       }
     }
     break;
   case ISD::AND: {
     // Check for unsigned bitfield extract
     if (tryV6T2BitfieldExtractOp(N, false))
       return;
 
+    // If an immediate is used in an AND node, it is possible that the immediate
+    // can be more optimally materialized when negated. If this is the case we
+    // can negate the immediate and use a BIC instead.
+    auto *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1));
+    if (N1C && N1C->hasOneUse() && Subtarget->isThumb()) {
+      uint32_t Imm = (uint32_t) N1C->getZExtValue();
+
+      // In Thumb2 mode, an AND can take a 12-bit immediate. If this
+      // immediate can be negated and fit in the immediate operand of
+      // a t2BIC, don't do any manual transform here as this can be
+      // handled by the generic ISel machinery.
+      bool PreferImmediateEncoding =
+          Subtarget->hasThumb2() && !is_t2_so_imm(Imm) && is_t2_so_imm_not(Imm);
+      if (!PreferImmediateEncoding &&
+          ConstantMaterializationCost(Imm) >
+              ConstantMaterializationCost(~Imm)) {
+        // The current immediate costs more to materialize than a negated
+        // immediate, so negate the immediate and use a BIC.
+        SDValue NewImm =
+            CurDAG->getConstant(~N1C->getZExtValue(), dl, MVT::i32);
+        CurDAG->RepositionNode(N->getIterator(), NewImm.getNode());
+
+        if (!Subtarget->hasThumb2()) {
+          SDValue Ops[] = {CurDAG->getRegister(ARM::CPSR, MVT::i32),
+                           N->getOperand(0), NewImm, getAL(CurDAG, dl),
+                           CurDAG->getRegister(0, MVT::i32)};
+          ReplaceNode(N, CurDAG->getMachineNode(ARM::tBIC, dl, MVT::i32, Ops));
+          return;
+        } else {
+          SDValue Ops[] = {N->getOperand(0), NewImm, getAL(CurDAG, dl),
+                           CurDAG->getRegister(0, MVT::i32),
+                           CurDAG->getRegister(0, MVT::i32)};
+          ReplaceNode(N,
+                      CurDAG->getMachineNode(ARM::t2BICrr, dl, MVT::i32, Ops));
+          return;
+        }
+      }
+    }
+
     // (and (or x, c2), c1) and top 16-bits of c1 and c2 match, lower 16-bits
     // of c1 are 0xffff, and lower 16-bit of c2 are 0. That is, the top 16-bits
     // are entirely contributed by c2 and lower 16-bits are entirely contributed
     // by x. That's equal to (or (and x, 0xffff), (and c1, 0xffff0000)).
     // Select it to: "movt x, ((c1 & 0xffff) >> 16)
     EVT VT = N->getValueType(0);
     if (VT != MVT::i32)
       break;
     unsigned Opc = (Subtarget->isThumb() && Subtarget->hasThumb2())
       ? ARM::t2MOVTi16
       : (Subtarget->hasV6T2Ops() ? ARM::MOVTi16 : 0);
     if (!Opc)
       break;
     SDValue N0 = N->getOperand(0), N1 = N->getOperand(1);
-    ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
+    N1C = dyn_cast<ConstantSDNode>(N1);
     if (!N1C)
       break;
     if (N0.getOpcode() == ISD::OR && N0.getNode()->hasOneUse()) {
       SDValue N2 = N0.getOperand(1);
       ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
       if (!N2C)
         break;
       unsigned N1CVal = N1C->getZExtValue();

test/CodeGen/Thumb/bic_imm.ll

+; RUN: llc < %s -mtriple=thumbv7-linux-gnueabi -mcpu=cortex-m0 -verify-machineinstrs | FileCheck --check-prefix CHECK-T1 %s
+; RUN: llc < %s -mtriple=thumbv7-linux-gnueabi -mcpu=cortex-m3 -verify-machineinstrs | FileCheck --check-prefix CHECK-T2 %s
+
+; CHECK-T1-LABEL: @i
+; CHECK-T2-LABEL: @i
+; CHECK-T1: movs r1, #255
+; CHECK-T1: adds r1, #20
+; CHECK-T1: bics r0, r1
+; CHECK-T2: movw r1, #275
+; CHECK-T2: bics r0, r1
+define i32 @i(i32 %a) {
+entry:
+  %and = and i32 %a, -276
+  ret i32 %and
+}