ARMISelDAGToDAG.cpp revision 61369da0e5461047adce93f3c3f5ca1ff49707fc 
1//===-- ARMISelDAGToDAG.cpp - A dag to dag inst selector for ARM ----------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Chris Lattner and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines an instruction selector for the ARM target.
11//
12//===----------------------------------------------------------------------===//
13
14#include "ARM.h"
15#include "ARMTargetMachine.h"
16#include "llvm/CallingConv.h"
17#include "llvm/DerivedTypes.h"
18#include "llvm/Function.h"
19#include "llvm/Intrinsics.h"
20#include "llvm/CodeGen/MachineFrameInfo.h"
21#include "llvm/CodeGen/MachineFunction.h"
22#include "llvm/CodeGen/MachineInstrBuilder.h"
23#include "llvm/CodeGen/SelectionDAG.h"
24#include "llvm/CodeGen/SelectionDAGISel.h"
25#include "llvm/CodeGen/SSARegMap.h"
26#include "llvm/Target/TargetLowering.h"
27#include "llvm/Support/Debug.h"
28#include <iostream>
29#include <queue>
30#include <set>
31using namespace llvm;
32
33namespace {
34  class ARMTargetLowering : public TargetLowering {
35  public:
36    ARMTargetLowering(TargetMachine &TM);
37    virtual SDOperand LowerOperation(SDOperand Op, SelectionDAG &DAG);
38    virtual const char *getTargetNodeName(unsigned Opcode) const;
39  };
40
41}
42
43ARMTargetLowering::ARMTargetLowering(TargetMachine &TM)
44  : TargetLowering(TM) {
45  setOperationAction(ISD::RET,           MVT::Other, Custom);
46  setOperationAction(ISD::GlobalAddress, MVT::i32,   Custom);
47  setOperationAction(ISD::ConstantPool,  MVT::i32,   Custom);
48
49  setSchedulingPreference(SchedulingForRegPressure);
50}
51
52namespace llvm {
53  namespace ARMISD {
54    enum NodeType {
55      // Start the numbering where the builting ops and target ops leave off.
56      FIRST_NUMBER = ISD::BUILTIN_OP_END+ARM::INSTRUCTION_LIST_END,
57      /// CALL - A direct function call.
58      CALL,
59
60      /// Return with a flag operand.
61      RET_FLAG
62    };
63  }
64}
65
66const char *ARMTargetLowering::getTargetNodeName(unsigned Opcode) const {
67  switch (Opcode) {
68  default: return 0;
69  case ARMISD::CALL:          return "ARMISD::CALL";
70  case ARMISD::RET_FLAG:      return "ARMISD::RET_FLAG";
71  }
72}
73
74// This transforms a ISD::CALL node into a
75// callseq_star <- ARMISD:CALL <- callseq_end
76// chain
77static SDOperand LowerCALL(SDOperand Op, SelectionDAG &DAG) {
78  SDOperand Chain    = Op.getOperand(0);
79  unsigned CallConv  = cast<ConstantSDNode>(Op.getOperand(1))->getValue();
80  assert(CallConv == CallingConv::C && "unknown calling convention");
81  bool isVarArg      = cast<ConstantSDNode>(Op.getOperand(2))->getValue() != 0;
82  bool isTailCall    = cast<ConstantSDNode>(Op.getOperand(3))->getValue() != 0;
83  assert(isTailCall == false && "tail call not supported");
84  SDOperand Callee   = Op.getOperand(4);
85  unsigned NumOps    = (Op.getNumOperands() - 5) / 2;
86
87  // Count how many bytes are to be pushed on the stack. Initially
88  // only the link register.
89  unsigned NumBytes = 4;
90
91  // Add up all the space actually used.
92  for (unsigned i = 4; i < NumOps; ++i)
93    NumBytes += MVT::getSizeInBits(Op.getOperand(5+2*i).getValueType())/8;
94
95  // Adjust the stack pointer for the new arguments...
96  // These operations are automatically eliminated by the prolog/epilog pass
97  Chain = DAG.getCALLSEQ_START(Chain,
98                               DAG.getConstant(NumBytes, MVT::i32));
99
100  SDOperand StackPtr = DAG.getRegister(ARM::R13, MVT::i32);
101
102  static const unsigned int num_regs = 4;
103  static const unsigned regs[num_regs] = {
104    ARM::R0, ARM::R1, ARM::R2, ARM::R3
105  };
106
107  std::vector<std::pair<unsigned, SDOperand> > RegsToPass;
108  std::vector<SDOperand> MemOpChains;
109
110  for (unsigned i = 0; i != NumOps; ++i) {
111    SDOperand Arg = Op.getOperand(5+2*i);
112    assert(Arg.getValueType() == MVT::i32);
113    if (i < num_regs)
114      RegsToPass.push_back(std::make_pair(regs[i], Arg));
115    else {
116      unsigned ArgOffset = (i - num_regs) * 4;
117      SDOperand PtrOff = DAG.getConstant(ArgOffset, StackPtr.getValueType());
118      PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
119      MemOpChains.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
120                                          Arg, PtrOff, DAG.getSrcValue(NULL)));
121    }
122  }
123  if (!MemOpChains.empty())
124    Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
125                        &MemOpChains[0], MemOpChains.size());
126
127  // Build a sequence of copy-to-reg nodes chained together with token chain
128  // and flag operands which copy the outgoing args into the appropriate regs.
129  SDOperand InFlag;
130  for (unsigned i = 0, e = RegsToPass.size(); i != e; ++i) {
131    Chain = DAG.getCopyToReg(Chain, RegsToPass[i].first, RegsToPass[i].second,
132                             InFlag);
133    InFlag = Chain.getValue(1);
134  }
135
136  std::vector<MVT::ValueType> NodeTys;
137  NodeTys.push_back(MVT::Other);   // Returns a chain
138  NodeTys.push_back(MVT::Flag);    // Returns a flag for retval copy to use.
139
140  // If the callee is a GlobalAddress/ExternalSymbol node (quite common, every
141  // direct call is) turn it into a TargetGlobalAddress/TargetExternalSymbol
142  // node so that legalize doesn't hack it.
143  if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(Callee))
144    Callee = DAG.getTargetGlobalAddress(G->getGlobal(), Callee.getValueType());
145
146  // If this is a direct call, pass the chain and the callee.
147  assert (Callee.Val);
148  std::vector<SDOperand> Ops;
149  Ops.push_back(Chain);
150  Ops.push_back(Callee);
151
152  // Add argument registers to the end of the list so that they are known live
153  // into the call.
154  for (unsigned i = 0, e = RegsToPass.size(); i != e; ++i)
155    Ops.push_back(DAG.getRegister(RegsToPass[i].first,
156                                  RegsToPass[i].second.getValueType()));
157
158  unsigned CallOpc = ARMISD::CALL;
159  if (InFlag.Val)
160    Ops.push_back(InFlag);
161  Chain = DAG.getNode(CallOpc, NodeTys, &Ops[0], Ops.size());
162  InFlag = Chain.getValue(1);
163
164  std::vector<SDOperand> ResultVals;
165  NodeTys.clear();
166
167  // If the call has results, copy the values out of the ret val registers.
168  switch (Op.Val->getValueType(0)) {
169  default: assert(0 && "Unexpected ret value!");
170  case MVT::Other:
171    break;
172  case MVT::i32:
173    Chain = DAG.getCopyFromReg(Chain, ARM::R0, MVT::i32, InFlag).getValue(1);
174    ResultVals.push_back(Chain.getValue(0));
175    NodeTys.push_back(MVT::i32);
176  }
177
178  Chain = DAG.getNode(ISD::CALLSEQ_END, MVT::Other, Chain,
179                      DAG.getConstant(NumBytes, MVT::i32));
180  NodeTys.push_back(MVT::Other);
181
182  if (ResultVals.empty())
183    return Chain;
184
185  ResultVals.push_back(Chain);
186  SDOperand Res = DAG.getNode(ISD::MERGE_VALUES, NodeTys, &ResultVals[0],
187                              ResultVals.size());
188  return Res.getValue(Op.ResNo);
189}
190
191static SDOperand LowerRET(SDOperand Op, SelectionDAG &DAG) {
192  SDOperand Copy;
193  SDOperand Chain = Op.getOperand(0);
194  switch(Op.getNumOperands()) {
195  default:
196    assert(0 && "Do not know how to return this many arguments!");
197    abort();
198  case 1: {
199    SDOperand LR = DAG.getRegister(ARM::R14, MVT::i32);
200    return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Chain);
201  }
202  case 3:
203    Copy = DAG.getCopyToReg(Chain, ARM::R0, Op.getOperand(1), SDOperand());
204    if (DAG.getMachineFunction().liveout_empty())
205      DAG.getMachineFunction().addLiveOut(ARM::R0);
206    break;
207  }
208
209  //We must use RET_FLAG instead of BRIND because BRIND doesn't have a flag
210  return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Copy, Copy.getValue(1));
211}
212
213static SDOperand LowerFORMAL_ARGUMENT(SDOperand Op, SelectionDAG &DAG,
214				      unsigned ArgNo) {
215  MachineFunction &MF = DAG.getMachineFunction();
216  MVT::ValueType ObjectVT = Op.getValue(ArgNo).getValueType();
217  assert (ObjectVT == MVT::i32);
218  SDOperand Root = Op.getOperand(0);
219  SSARegMap *RegMap = MF.getSSARegMap();
220
221  unsigned num_regs = 4;
222  static const unsigned REGS[] = {
223    ARM::R0, ARM::R1, ARM::R2, ARM::R3
224  };
225
226  if(ArgNo < num_regs) {
227    unsigned VReg = RegMap->createVirtualRegister(&ARM::IntRegsRegClass);
228    MF.addLiveIn(REGS[ArgNo], VReg);
229    return DAG.getCopyFromReg(Root, VReg, MVT::i32);
230  } else {
231    // If the argument is actually used, emit a load from the right stack
232      // slot.
233    if (!Op.Val->hasNUsesOfValue(0, ArgNo)) {
234      unsigned ArgOffset = (ArgNo - num_regs) * 4;
235
236      MachineFrameInfo *MFI = MF.getFrameInfo();
237      unsigned ObjSize = MVT::getSizeInBits(ObjectVT)/8;
238      int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
239      SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
240      return DAG.getLoad(ObjectVT, Root, FIN,
241			 DAG.getSrcValue(NULL));
242    } else {
243      // Don't emit a dead load.
244      return DAG.getNode(ISD::UNDEF, ObjectVT);
245    }
246  }
247}
248
249static SDOperand LowerConstantPool(SDOperand Op, SelectionDAG &DAG) {
250  MVT::ValueType PtrVT = Op.getValueType();
251  ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(Op);
252  Constant *C = CP->get();
253  SDOperand CPI = DAG.getTargetConstantPool(C, PtrVT, CP->getAlignment());
254
255  return CPI;
256}
257
258static SDOperand LowerGlobalAddress(SDOperand Op,
259				    SelectionDAG &DAG) {
260  GlobalValue  *GV = cast<GlobalAddressSDNode>(Op)->getGlobal();
261  int alignment = 2;
262  SDOperand CPAddr = DAG.getConstantPool(GV, MVT::i32, alignment);
263  return DAG.getLoad(MVT::i32, DAG.getEntryNode(), CPAddr,
264		     DAG.getSrcValue(NULL));
265}
266
267static SDOperand LowerFORMAL_ARGUMENTS(SDOperand Op, SelectionDAG &DAG) {
268  std::vector<SDOperand> ArgValues;
269  SDOperand Root = Op.getOperand(0);
270
271  for (unsigned ArgNo = 0, e = Op.Val->getNumValues()-1; ArgNo != e; ++ArgNo) {
272    SDOperand ArgVal = LowerFORMAL_ARGUMENT(Op, DAG, ArgNo);
273
274    ArgValues.push_back(ArgVal);
275  }
276
277  bool isVarArg = cast<ConstantSDNode>(Op.getOperand(2))->getValue() != 0;
278  assert(!isVarArg);
279
280  ArgValues.push_back(Root);
281
282  // Return the new list of results.
283  std::vector<MVT::ValueType> RetVT(Op.Val->value_begin(),
284                                    Op.Val->value_end());
285  return DAG.getNode(ISD::MERGE_VALUES, RetVT, &ArgValues[0], ArgValues.size());
286}
287
288SDOperand ARMTargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
289  switch (Op.getOpcode()) {
290  default:
291    assert(0 && "Should not custom lower this!");
292    abort();
293  case ISD::ConstantPool:
294    return LowerConstantPool(Op, DAG);
295  case ISD::GlobalAddress:
296    return LowerGlobalAddress(Op, DAG);
297  case ISD::FORMAL_ARGUMENTS:
298    return LowerFORMAL_ARGUMENTS(Op, DAG);
299  case ISD::CALL:
300    return LowerCALL(Op, DAG);
301  case ISD::RET:
302    return LowerRET(Op, DAG);
303  }
304}
305
306//===----------------------------------------------------------------------===//
307// Instruction Selector Implementation
308//===----------------------------------------------------------------------===//
309
310//===--------------------------------------------------------------------===//
311/// ARMDAGToDAGISel - ARM specific code to select ARM machine
312/// instructions for SelectionDAG operations.
313///
314namespace {
315class ARMDAGToDAGISel : public SelectionDAGISel {
316  ARMTargetLowering Lowering;
317
318public:
319  ARMDAGToDAGISel(TargetMachine &TM)
320    : SelectionDAGISel(Lowering), Lowering(TM) {
321  }
322
323  SDNode *Select(SDOperand &Result, SDOperand Op);
324  virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
325  bool SelectAddrRegImm(SDOperand N, SDOperand &Offset, SDOperand &Base);
326
327  // Include the pieces autogenerated from the target description.
328#include "ARMGenDAGISel.inc"
329};
330
331void ARMDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
332  DEBUG(BB->dump());
333
334  DAG.setRoot(SelectRoot(DAG.getRoot()));
335  DAG.RemoveDeadNodes();
336
337  ScheduleAndEmitDAG(DAG);
338}
339
340static bool isInt12Immediate(SDNode *N, short &Imm) {
341  if (N->getOpcode() != ISD::Constant)
342    return false;
343
344  int32_t t = cast<ConstantSDNode>(N)->getValue();
345  int max = 2<<12 - 1;
346  int min = -max;
347  if (t > min && t < max) {
348    Imm = t;
349    return true;
350  }
351  else
352    return false;
353}
354
355static bool isInt12Immediate(SDOperand Op, short &Imm) {
356  return isInt12Immediate(Op.Val, Imm);
357}
358
359//register plus/minus 12 bit offset
360bool ARMDAGToDAGISel::SelectAddrRegImm(SDOperand N, SDOperand &Offset,
361				    SDOperand &Base) {
362  if (N.getOpcode() == ISD::ADD) {
363    short imm = 0;
364    if (isInt12Immediate(N.getOperand(1), imm)) {
365      Offset = CurDAG->getTargetConstant(imm, MVT::i32);
366      if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
367	Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
368      } else {
369	Base = N.getOperand(0);
370      }
371      return true; // [r+i]
372    }
373  }
374
375  Offset = CurDAG->getTargetConstant(0, MVT::i32);
376  if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N)) {
377    Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
378  }
379  else
380    Base = N;
381  return true;      //any address fits in a register
382}
383
384SDNode *ARMDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
385  SDNode *N = Op.Val;
386
387  switch (N->getOpcode()) {
388  default:
389    return SelectCode(Result, Op);
390    break;
391  }
392  return NULL;
393}
394
395}  // end anonymous namespace
396
397/// createARMISelDag - This pass converts a legalized DAG into a
398/// ARM-specific DAG, ready for instruction scheduling.
399///
400FunctionPass *llvm::createARMISelDag(TargetMachine &TM) {
401  return new ARMDAGToDAGISel(TM);
402}
403