lib/Target/ARM/ARMISelDAGToDAG.cpp

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