1//===-- AArch64ISelDAGToDAG.cpp - A dag to dag inst selector for AArch64 --===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines an instruction selector for the AArch64 target.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "aarch64-isel"
15#include "AArch64.h"
16#include "AArch64InstrInfo.h"
17#include "AArch64Subtarget.h"
18#include "AArch64TargetMachine.h"
19#include "Utils/AArch64BaseInfo.h"
20#include "llvm/ADT/APSInt.h"
21#include "llvm/CodeGen/SelectionDAGISel.h"
22#include "llvm/IR/GlobalValue.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/raw_ostream.h"
25
26using namespace llvm;
27
28//===--------------------------------------------------------------------===//
29/// AArch64 specific code to select AArch64 machine instructions for
30/// SelectionDAG operations.
31///
32namespace {
33
34class AArch64DAGToDAGISel : public SelectionDAGISel {
35  AArch64TargetMachine &TM;
36  const AArch64InstrInfo *TII;
37
38  /// Keep a pointer to the AArch64Subtarget around so that we can
39  /// make the right decision when generating code for different targets.
40  const AArch64Subtarget *Subtarget;
41
42public:
43  explicit AArch64DAGToDAGISel(AArch64TargetMachine &tm,
44                               CodeGenOpt::Level OptLevel)
45    : SelectionDAGISel(tm, OptLevel), TM(tm),
46      TII(static_cast<const AArch64InstrInfo*>(TM.getInstrInfo())),
47      Subtarget(&TM.getSubtarget<AArch64Subtarget>()) {
48  }
49
50  virtual const char *getPassName() const {
51    return "AArch64 Instruction Selection";
52  }
53
54  // Include the pieces autogenerated from the target description.
55#include "AArch64GenDAGISel.inc"
56
57  template<unsigned MemSize>
58  bool SelectOffsetUImm12(SDValue N, SDValue &UImm12) {
59    const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
60    if (!CN || CN->getZExtValue() % MemSize != 0
61        || CN->getZExtValue() / MemSize > 0xfff)
62      return false;
63
64    UImm12 =  CurDAG->getTargetConstant(CN->getZExtValue() / MemSize, MVT::i64);
65    return true;
66  }
67
68  template<unsigned RegWidth>
69  bool SelectCVTFixedPosOperand(SDValue N, SDValue &FixedPos) {
70    return SelectCVTFixedPosOperand(N, FixedPos, RegWidth);
71  }
72
73  bool SelectFPZeroOperand(SDValue N, SDValue &Dummy);
74
75  bool SelectCVTFixedPosOperand(SDValue N, SDValue &FixedPos,
76                                unsigned RegWidth);
77
78  bool SelectInlineAsmMemoryOperand(const SDValue &Op,
79                                    char ConstraintCode,
80                                    std::vector<SDValue> &OutOps);
81
82  bool SelectLogicalImm(SDValue N, SDValue &Imm);
83
84  template<unsigned RegWidth>
85  bool SelectTSTBOperand(SDValue N, SDValue &FixedPos) {
86    return SelectTSTBOperand(N, FixedPos, RegWidth);
87  }
88
89  bool SelectTSTBOperand(SDValue N, SDValue &FixedPos, unsigned RegWidth);
90
91  SDNode *TrySelectToMoveImm(SDNode *N);
92  SDNode *LowerToFPLitPool(SDNode *Node);
93  SDNode *SelectToLitPool(SDNode *N);
94
95  SDNode* Select(SDNode*);
96private:
97};
98}
99
100bool
101AArch64DAGToDAGISel::SelectCVTFixedPosOperand(SDValue N, SDValue &FixedPos,
102                                              unsigned RegWidth) {
103  const ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N);
104  if (!CN) return false;
105
106  // An FCVT[SU] instruction performs: convertToInt(Val * 2^fbits) where fbits
107  // is between 1 and 32 for a destination w-register, or 1 and 64 for an
108  // x-register.
109  //
110  // By this stage, we've detected (fp_to_[su]int (fmul Val, THIS_NODE)) so we
111  // want THIS_NODE to be 2^fbits. This is much easier to deal with using
112  // integers.
113  bool IsExact;
114
115  // fbits is between 1 and 64 in the worst-case, which means the fmul
116  // could have 2^64 as an actual operand. Need 65 bits of precision.
117  APSInt IntVal(65, true);
118  CN->getValueAPF().convertToInteger(IntVal, APFloat::rmTowardZero, &IsExact);
119
120  // N.b. isPowerOf2 also checks for > 0.
121  if (!IsExact || !IntVal.isPowerOf2()) return false;
122  unsigned FBits = IntVal.logBase2();
123
124  // Checks above should have guaranteed that we haven't lost information in
125  // finding FBits, but it must still be in range.
126  if (FBits == 0 || FBits > RegWidth) return false;
127
128  FixedPos = CurDAG->getTargetConstant(64 - FBits, MVT::i32);
129  return true;
130}
131
132bool
133AArch64DAGToDAGISel::SelectInlineAsmMemoryOperand(const SDValue &Op,
134                                                 char ConstraintCode,
135                                                 std::vector<SDValue> &OutOps) {
136  switch (ConstraintCode) {
137  default: llvm_unreachable("Unrecognised AArch64 memory constraint");
138  case 'm':
139    // FIXME: more freedom is actually permitted for 'm'. We can go
140    // hunting for a base and an offset if we want. Of course, since
141    // we don't really know how the operand is going to be used we're
142    // probably restricted to the load/store pair's simm7 as an offset
143    // range anyway.
144  case 'Q':
145    OutOps.push_back(Op);
146  }
147
148  return false;
149}
150
151bool
152AArch64DAGToDAGISel::SelectFPZeroOperand(SDValue N, SDValue &Dummy) {
153  ConstantFPSDNode *Imm = dyn_cast<ConstantFPSDNode>(N);
154  if (!Imm || !Imm->getValueAPF().isPosZero())
155    return false;
156
157  // Doesn't actually carry any information, but keeps TableGen quiet.
158  Dummy = CurDAG->getTargetConstant(0, MVT::i32);
159  return true;
160}
161
162bool AArch64DAGToDAGISel::SelectLogicalImm(SDValue N, SDValue &Imm) {
163  uint32_t Bits;
164  uint32_t RegWidth = N.getValueType().getSizeInBits();
165
166  ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
167  if (!CN) return false;
168
169  if (!A64Imms::isLogicalImm(RegWidth, CN->getZExtValue(), Bits))
170    return false;
171
172  Imm = CurDAG->getTargetConstant(Bits, MVT::i32);
173  return true;
174}
175
176SDNode *AArch64DAGToDAGISel::TrySelectToMoveImm(SDNode *Node) {
177  SDNode *ResNode;
178  DebugLoc dl = Node->getDebugLoc();
179  EVT DestType = Node->getValueType(0);
180  unsigned DestWidth = DestType.getSizeInBits();
181
182  unsigned MOVOpcode;
183  EVT MOVType;
184  int UImm16, Shift;
185  uint32_t LogicalBits;
186
187  uint64_t BitPat = cast<ConstantSDNode>(Node)->getZExtValue();
188  if (A64Imms::isMOVZImm(DestWidth, BitPat, UImm16, Shift)) {
189    MOVType = DestType;
190    MOVOpcode = DestWidth == 64 ? AArch64::MOVZxii : AArch64::MOVZwii;
191  } else if (A64Imms::isMOVNImm(DestWidth, BitPat, UImm16, Shift)) {
192    MOVType = DestType;
193    MOVOpcode = DestWidth == 64 ? AArch64::MOVNxii : AArch64::MOVNwii;
194  } else if (DestWidth == 64 && A64Imms::isMOVNImm(32, BitPat, UImm16, Shift)) {
195    // To get something like 0x0000_0000_ffff_1234 into a 64-bit register we can
196    // use a 32-bit instruction: "movn w0, 0xedbc".
197    MOVType = MVT::i32;
198    MOVOpcode = AArch64::MOVNwii;
199  } else if (A64Imms::isLogicalImm(DestWidth, BitPat, LogicalBits))  {
200    MOVOpcode = DestWidth == 64 ? AArch64::ORRxxi : AArch64::ORRwwi;
201    uint16_t ZR = DestWidth == 64 ? AArch64::XZR : AArch64::WZR;
202
203    return CurDAG->getMachineNode(MOVOpcode, dl, DestType,
204                              CurDAG->getRegister(ZR, DestType),
205                              CurDAG->getTargetConstant(LogicalBits, MVT::i32));
206  } else {
207    // Can't handle it in one instruction. There's scope for permitting two (or
208    // more) instructions, but that'll need more thought.
209    return NULL;
210  }
211
212  ResNode = CurDAG->getMachineNode(MOVOpcode, dl, MOVType,
213                                   CurDAG->getTargetConstant(UImm16, MVT::i32),
214                                   CurDAG->getTargetConstant(Shift, MVT::i32));
215
216  if (MOVType != DestType) {
217    ResNode = CurDAG->getMachineNode(TargetOpcode::SUBREG_TO_REG, dl,
218                          MVT::i64, MVT::i32, MVT::Other,
219                          CurDAG->getTargetConstant(0, MVT::i64),
220                          SDValue(ResNode, 0),
221                          CurDAG->getTargetConstant(AArch64::sub_32, MVT::i32));
222  }
223
224  return ResNode;
225}
226
227SDNode *AArch64DAGToDAGISel::SelectToLitPool(SDNode *Node) {
228  DebugLoc DL = Node->getDebugLoc();
229  uint64_t UnsignedVal = cast<ConstantSDNode>(Node)->getZExtValue();
230  int64_t SignedVal = cast<ConstantSDNode>(Node)->getSExtValue();
231  EVT DestType = Node->getValueType(0);
232  EVT PtrVT = TLI.getPointerTy();
233
234  // Since we may end up loading a 64-bit constant from a 32-bit entry the
235  // constant in the pool may have a different type to the eventual node.
236  ISD::LoadExtType Extension;
237  EVT MemType;
238
239  assert((DestType == MVT::i64 || DestType == MVT::i32)
240         && "Only expect integer constants at the moment");
241
242  if (DestType == MVT::i32) {
243    Extension = ISD::NON_EXTLOAD;
244    MemType = MVT::i32;
245  } else if (UnsignedVal <= UINT32_MAX) {
246    Extension = ISD::ZEXTLOAD;
247    MemType = MVT::i32;
248  } else if (SignedVal >= INT32_MIN && SignedVal <= INT32_MAX) {
249    Extension = ISD::SEXTLOAD;
250    MemType = MVT::i32;
251  } else {
252    Extension = ISD::NON_EXTLOAD;
253    MemType = MVT::i64;
254  }
255
256  Constant *CV = ConstantInt::get(Type::getIntNTy(*CurDAG->getContext(),
257                                                  MemType.getSizeInBits()),
258                                  UnsignedVal);
259  SDValue PoolAddr;
260  unsigned Alignment = TLI.getDataLayout()->getABITypeAlignment(CV->getType());
261  PoolAddr = CurDAG->getNode(AArch64ISD::WrapperSmall, DL, PtrVT,
262                             CurDAG->getTargetConstantPool(CV, PtrVT, 0, 0,
263                                                         AArch64II::MO_NO_FLAG),
264                             CurDAG->getTargetConstantPool(CV, PtrVT, 0, 0,
265                                                           AArch64II::MO_LO12),
266                             CurDAG->getConstant(Alignment, MVT::i32));
267
268  return CurDAG->getExtLoad(Extension, DL, DestType, CurDAG->getEntryNode(),
269                            PoolAddr,
270                            MachinePointerInfo::getConstantPool(), MemType,
271                            /* isVolatile = */ false,
272                            /* isNonTemporal = */ false,
273                            Alignment).getNode();
274}
275
276SDNode *AArch64DAGToDAGISel::LowerToFPLitPool(SDNode *Node) {
277  DebugLoc DL = Node->getDebugLoc();
278  const ConstantFP *FV = cast<ConstantFPSDNode>(Node)->getConstantFPValue();
279  EVT PtrVT = TLI.getPointerTy();
280  EVT DestType = Node->getValueType(0);
281
282  unsigned Alignment = TLI.getDataLayout()->getABITypeAlignment(FV->getType());
283  SDValue PoolAddr;
284
285  assert(TM.getCodeModel() == CodeModel::Small &&
286         "Only small code model supported");
287  PoolAddr = CurDAG->getNode(AArch64ISD::WrapperSmall, DL, PtrVT,
288                             CurDAG->getTargetConstantPool(FV, PtrVT, 0, 0,
289                                                         AArch64II::MO_NO_FLAG),
290                             CurDAG->getTargetConstantPool(FV, PtrVT, 0, 0,
291                                                           AArch64II::MO_LO12),
292                             CurDAG->getConstant(Alignment, MVT::i32));
293
294  return CurDAG->getLoad(DestType, DL, CurDAG->getEntryNode(), PoolAddr,
295                         MachinePointerInfo::getConstantPool(),
296                         /* isVolatile = */ false,
297                         /* isNonTemporal = */ false,
298                         /* isInvariant = */ true,
299                         Alignment).getNode();
300}
301
302bool
303AArch64DAGToDAGISel::SelectTSTBOperand(SDValue N, SDValue &FixedPos,
304                                       unsigned RegWidth) {
305  const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
306  if (!CN) return false;
307
308  uint64_t Val = CN->getZExtValue();
309
310  if (!isPowerOf2_64(Val)) return false;
311
312  unsigned TestedBit = Log2_64(Val);
313  // Checks above should have guaranteed that we haven't lost information in
314  // finding TestedBit, but it must still be in range.
315  if (TestedBit >= RegWidth) return false;
316
317  FixedPos = CurDAG->getTargetConstant(TestedBit, MVT::i64);
318  return true;
319}
320
321SDNode *AArch64DAGToDAGISel::Select(SDNode *Node) {
322  // Dump information about the Node being selected
323  DEBUG(dbgs() << "Selecting: "; Node->dump(CurDAG); dbgs() << "\n");
324
325  if (Node->isMachineOpcode()) {
326    DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << "\n");
327    return NULL;
328  }
329
330  switch (Node->getOpcode()) {
331  case ISD::FrameIndex: {
332    int FI = cast<FrameIndexSDNode>(Node)->getIndex();
333    EVT PtrTy = TLI.getPointerTy();
334    SDValue TFI = CurDAG->getTargetFrameIndex(FI, PtrTy);
335    return CurDAG->SelectNodeTo(Node, AArch64::ADDxxi_lsl0_s, PtrTy,
336                                TFI, CurDAG->getTargetConstant(0, PtrTy));
337  }
338  case ISD::ConstantPool: {
339    // Constant pools are fine, just create a Target entry.
340    ConstantPoolSDNode *CN = cast<ConstantPoolSDNode>(Node);
341    const Constant *C = CN->getConstVal();
342    SDValue CP = CurDAG->getTargetConstantPool(C, CN->getValueType(0));
343
344    ReplaceUses(SDValue(Node, 0), CP);
345    return NULL;
346  }
347  case ISD::Constant: {
348    SDNode *ResNode = 0;
349    if (cast<ConstantSDNode>(Node)->getZExtValue() == 0) {
350      // XZR and WZR are probably even better than an actual move: most of the
351      // time they can be folded into another instruction with *no* cost.
352
353      EVT Ty = Node->getValueType(0);
354      assert((Ty == MVT::i32 || Ty == MVT::i64) && "unexpected type");
355      uint16_t Register = Ty == MVT::i32 ? AArch64::WZR : AArch64::XZR;
356      ResNode = CurDAG->getCopyFromReg(CurDAG->getEntryNode(),
357                                       Node->getDebugLoc(),
358                                       Register, Ty).getNode();
359    }
360
361    // Next best option is a move-immediate, see if we can do that.
362    if (!ResNode) {
363      ResNode = TrySelectToMoveImm(Node);
364    }
365
366    if (ResNode)
367      return ResNode;
368
369    // If even that fails we fall back to a lit-pool entry at the moment. Future
370    // tuning may change this to a sequence of MOVZ/MOVN/MOVK instructions.
371    ResNode = SelectToLitPool(Node);
372    assert(ResNode && "We need *some* way to materialise a constant");
373
374    // We want to continue selection at this point since the litpool access
375    // generated used generic nodes for simplicity.
376    ReplaceUses(SDValue(Node, 0), SDValue(ResNode, 0));
377    Node = ResNode;
378    break;
379  }
380  case ISD::ConstantFP: {
381    if (A64Imms::isFPImm(cast<ConstantFPSDNode>(Node)->getValueAPF())) {
382      // FMOV will take care of it from TableGen
383      break;
384    }
385
386    SDNode *ResNode = LowerToFPLitPool(Node);
387    ReplaceUses(SDValue(Node, 0), SDValue(ResNode, 0));
388
389    // We want to continue selection at this point since the litpool access
390    // generated used generic nodes for simplicity.
391    Node = ResNode;
392    break;
393  }
394  default:
395    break; // Let generic code handle it
396  }
397
398  SDNode *ResNode = SelectCode(Node);
399
400  DEBUG(dbgs() << "=> ";
401        if (ResNode == NULL || ResNode == Node)
402          Node->dump(CurDAG);
403        else
404          ResNode->dump(CurDAG);
405        dbgs() << "\n");
406
407  return ResNode;
408}
409
410/// This pass converts a legalized DAG into a AArch64-specific DAG, ready for
411/// instruction scheduling.
412FunctionPass *llvm::createAArch64ISelDAG(AArch64TargetMachine &TM,
413                                         CodeGenOpt::Level OptLevel) {
414  return new AArch64DAGToDAGISel(TM, OptLevel);
415}
416