ARMISelDAGToDAG.cpp revision 5f450d2948ac5bd83a31fbfff89e17b0e2536a80
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 int VarArgsFrameIndex; // FrameIndex for start of varargs area. 36 public: 37 ARMTargetLowering(TargetMachine &TM); 38 virtual SDOperand LowerOperation(SDOperand Op, SelectionDAG &DAG); 39 virtual const char *getTargetNodeName(unsigned Opcode) const; 40 }; 41 42} 43 44ARMTargetLowering::ARMTargetLowering(TargetMachine &TM) 45 : TargetLowering(TM) { 46 addRegisterClass(MVT::i32, ARM::IntRegsRegisterClass); 47 48 //LLVM requires that a register class supports MVT::f64! 49 addRegisterClass(MVT::f64, ARM::IntRegsRegisterClass); 50 51 setOperationAction(ISD::RET, MVT::Other, Custom); 52 setOperationAction(ISD::GlobalAddress, MVT::i32, Custom); 53 setOperationAction(ISD::ConstantPool, MVT::i32, Custom); 54 55 setOperationAction(ISD::SETCC, MVT::i32, Expand); 56 setOperationAction(ISD::SELECT_CC, MVT::i32, Custom); 57 setOperationAction(ISD::BR_CC, MVT::i32, Custom); 58 59 setOperationAction(ISD::VASTART, MVT::Other, Custom); 60 setOperationAction(ISD::VAEND, MVT::Other, Expand); 61 62 setSchedulingPreference(SchedulingForRegPressure); 63 computeRegisterProperties(); 64} 65 66namespace llvm { 67 namespace ARMISD { 68 enum NodeType { 69 // Start the numbering where the builting ops and target ops leave off. 70 FIRST_NUMBER = ISD::BUILTIN_OP_END+ARM::INSTRUCTION_LIST_END, 71 /// CALL - A direct function call. 72 CALL, 73 74 /// Return with a flag operand. 75 RET_FLAG, 76 77 CMP, 78 79 SELECT, 80 81 BR 82 }; 83 } 84} 85 86/// DAGCCToARMCC - Convert a DAG integer condition code to an ARM CC 87static ARMCC::CondCodes DAGCCToARMCC(ISD::CondCode CC) { 88 switch (CC) { 89 default: assert(0 && "Unknown condition code!"); 90 case ISD::SETNE: return ARMCC::NE; 91 case ISD::SETEQ: return ARMCC::EQ; 92 case ISD::SETGE: return ARMCC::GE; 93 case ISD::SETUGE: return ARMCC::CS; 94 } 95} 96 97const char *ARMTargetLowering::getTargetNodeName(unsigned Opcode) const { 98 switch (Opcode) { 99 default: return 0; 100 case ARMISD::CALL: return "ARMISD::CALL"; 101 case ARMISD::RET_FLAG: return "ARMISD::RET_FLAG"; 102 case ARMISD::SELECT: return "ARMISD::SELECT"; 103 case ARMISD::CMP: return "ARMISD::CMP"; 104 case ARMISD::BR: return "ARMISD::BR"; 105 } 106} 107 108// This transforms a ISD::CALL node into a 109// callseq_star <- ARMISD:CALL <- callseq_end 110// chain 111static SDOperand LowerCALL(SDOperand Op, SelectionDAG &DAG) { 112 SDOperand Chain = Op.getOperand(0); 113 unsigned CallConv = cast<ConstantSDNode>(Op.getOperand(1))->getValue(); 114 assert(CallConv == CallingConv::C && "unknown calling convention"); 115 bool isVarArg = cast<ConstantSDNode>(Op.getOperand(2))->getValue() != 0; 116 bool isTailCall = cast<ConstantSDNode>(Op.getOperand(3))->getValue() != 0; 117 assert(isTailCall == false && "tail call not supported"); 118 SDOperand Callee = Op.getOperand(4); 119 unsigned NumOps = (Op.getNumOperands() - 5) / 2; 120 121 // Count how many bytes are to be pushed on the stack. 122 unsigned NumBytes = 0; 123 124 // Add up all the space actually used. 125 for (unsigned i = 4; i < NumOps; ++i) 126 NumBytes += MVT::getSizeInBits(Op.getOperand(5+2*i).getValueType())/8; 127 128 // Adjust the stack pointer for the new arguments... 129 // These operations are automatically eliminated by the prolog/epilog pass 130 Chain = DAG.getCALLSEQ_START(Chain, 131 DAG.getConstant(NumBytes, MVT::i32)); 132 133 SDOperand StackPtr = DAG.getRegister(ARM::R13, MVT::i32); 134 135 static const unsigned int num_regs = 4; 136 static const unsigned regs[num_regs] = { 137 ARM::R0, ARM::R1, ARM::R2, ARM::R3 138 }; 139 140 std::vector<std::pair<unsigned, SDOperand> > RegsToPass; 141 std::vector<SDOperand> MemOpChains; 142 143 for (unsigned i = 0; i != NumOps; ++i) { 144 SDOperand Arg = Op.getOperand(5+2*i); 145 assert(Arg.getValueType() == MVT::i32); 146 if (i < num_regs) 147 RegsToPass.push_back(std::make_pair(regs[i], Arg)); 148 else { 149 unsigned ArgOffset = (i - num_regs) * 4; 150 SDOperand PtrOff = DAG.getConstant(ArgOffset, StackPtr.getValueType()); 151 PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff); 152 MemOpChains.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain, 153 Arg, PtrOff, DAG.getSrcValue(NULL))); 154 } 155 } 156 if (!MemOpChains.empty()) 157 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, 158 &MemOpChains[0], MemOpChains.size()); 159 160 // Build a sequence of copy-to-reg nodes chained together with token chain 161 // and flag operands which copy the outgoing args into the appropriate regs. 162 SDOperand InFlag; 163 for (unsigned i = 0, e = RegsToPass.size(); i != e; ++i) { 164 Chain = DAG.getCopyToReg(Chain, RegsToPass[i].first, RegsToPass[i].second, 165 InFlag); 166 InFlag = Chain.getValue(1); 167 } 168 169 std::vector<MVT::ValueType> NodeTys; 170 NodeTys.push_back(MVT::Other); // Returns a chain 171 NodeTys.push_back(MVT::Flag); // Returns a flag for retval copy to use. 172 173 // If the callee is a GlobalAddress/ExternalSymbol node (quite common, every 174 // direct call is) turn it into a TargetGlobalAddress/TargetExternalSymbol 175 // node so that legalize doesn't hack it. 176 if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(Callee)) 177 Callee = DAG.getTargetGlobalAddress(G->getGlobal(), Callee.getValueType()); 178 179 // If this is a direct call, pass the chain and the callee. 180 assert (Callee.Val); 181 std::vector<SDOperand> Ops; 182 Ops.push_back(Chain); 183 Ops.push_back(Callee); 184 185 // Add argument registers to the end of the list so that they are known live 186 // into the call. 187 for (unsigned i = 0, e = RegsToPass.size(); i != e; ++i) 188 Ops.push_back(DAG.getRegister(RegsToPass[i].first, 189 RegsToPass[i].second.getValueType())); 190 191 unsigned CallOpc = ARMISD::CALL; 192 if (InFlag.Val) 193 Ops.push_back(InFlag); 194 Chain = DAG.getNode(CallOpc, NodeTys, &Ops[0], Ops.size()); 195 InFlag = Chain.getValue(1); 196 197 std::vector<SDOperand> ResultVals; 198 NodeTys.clear(); 199 200 // If the call has results, copy the values out of the ret val registers. 201 switch (Op.Val->getValueType(0)) { 202 default: assert(0 && "Unexpected ret value!"); 203 case MVT::Other: 204 break; 205 case MVT::i32: 206 Chain = DAG.getCopyFromReg(Chain, ARM::R0, MVT::i32, InFlag).getValue(1); 207 ResultVals.push_back(Chain.getValue(0)); 208 NodeTys.push_back(MVT::i32); 209 } 210 211 Chain = DAG.getNode(ISD::CALLSEQ_END, MVT::Other, Chain, 212 DAG.getConstant(NumBytes, MVT::i32)); 213 NodeTys.push_back(MVT::Other); 214 215 if (ResultVals.empty()) 216 return Chain; 217 218 ResultVals.push_back(Chain); 219 SDOperand Res = DAG.getNode(ISD::MERGE_VALUES, NodeTys, &ResultVals[0], 220 ResultVals.size()); 221 return Res.getValue(Op.ResNo); 222} 223 224static SDOperand LowerRET(SDOperand Op, SelectionDAG &DAG) { 225 SDOperand Copy; 226 SDOperand Chain = Op.getOperand(0); 227 switch(Op.getNumOperands()) { 228 default: 229 assert(0 && "Do not know how to return this many arguments!"); 230 abort(); 231 case 1: { 232 SDOperand LR = DAG.getRegister(ARM::R14, MVT::i32); 233 return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Chain); 234 } 235 case 3: 236 Copy = DAG.getCopyToReg(Chain, ARM::R0, Op.getOperand(1), SDOperand()); 237 if (DAG.getMachineFunction().liveout_empty()) 238 DAG.getMachineFunction().addLiveOut(ARM::R0); 239 break; 240 } 241 242 //We must use RET_FLAG instead of BRIND because BRIND doesn't have a flag 243 return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Copy, Copy.getValue(1)); 244} 245 246static SDOperand LowerFORMAL_ARGUMENT(SDOperand Op, SelectionDAG &DAG, 247 unsigned *vRegs, 248 unsigned ArgNo) { 249 MachineFunction &MF = DAG.getMachineFunction(); 250 MVT::ValueType ObjectVT = Op.getValue(ArgNo).getValueType(); 251 assert (ObjectVT == MVT::i32); 252 SDOperand Root = Op.getOperand(0); 253 SSARegMap *RegMap = MF.getSSARegMap(); 254 255 unsigned num_regs = 4; 256 static const unsigned REGS[] = { 257 ARM::R0, ARM::R1, ARM::R2, ARM::R3 258 }; 259 260 if(ArgNo < num_regs) { 261 unsigned VReg = RegMap->createVirtualRegister(&ARM::IntRegsRegClass); 262 MF.addLiveIn(REGS[ArgNo], VReg); 263 vRegs[ArgNo] = VReg; 264 return DAG.getCopyFromReg(Root, VReg, MVT::i32); 265 } else { 266 // If the argument is actually used, emit a load from the right stack 267 // slot. 268 if (!Op.Val->hasNUsesOfValue(0, ArgNo)) { 269 unsigned ArgOffset = (ArgNo - num_regs) * 4; 270 271 MachineFrameInfo *MFI = MF.getFrameInfo(); 272 unsigned ObjSize = MVT::getSizeInBits(ObjectVT)/8; 273 int FI = MFI->CreateFixedObject(ObjSize, ArgOffset); 274 SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32); 275 return DAG.getLoad(ObjectVT, Root, FIN, 276 DAG.getSrcValue(NULL)); 277 } else { 278 // Don't emit a dead load. 279 return DAG.getNode(ISD::UNDEF, ObjectVT); 280 } 281 } 282} 283 284static SDOperand LowerConstantPool(SDOperand Op, SelectionDAG &DAG) { 285 MVT::ValueType PtrVT = Op.getValueType(); 286 ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(Op); 287 Constant *C = CP->get(); 288 SDOperand CPI = DAG.getTargetConstantPool(C, PtrVT, CP->getAlignment()); 289 290 return CPI; 291} 292 293static SDOperand LowerGlobalAddress(SDOperand Op, 294 SelectionDAG &DAG) { 295 GlobalValue *GV = cast<GlobalAddressSDNode>(Op)->getGlobal(); 296 int alignment = 2; 297 SDOperand CPAddr = DAG.getConstantPool(GV, MVT::i32, alignment); 298 return DAG.getLoad(MVT::i32, DAG.getEntryNode(), CPAddr, 299 DAG.getSrcValue(NULL)); 300} 301 302static SDOperand LowerVASTART(SDOperand Op, SelectionDAG &DAG, 303 unsigned VarArgsFrameIndex) { 304 // vastart just stores the address of the VarArgsFrameIndex slot into the 305 // memory location argument. 306 MVT::ValueType PtrVT = DAG.getTargetLoweringInfo().getPointerTy(); 307 SDOperand FR = DAG.getFrameIndex(VarArgsFrameIndex, PtrVT); 308 return DAG.getNode(ISD::STORE, MVT::Other, Op.getOperand(0), FR, 309 Op.getOperand(1), Op.getOperand(2)); 310} 311 312static SDOperand LowerFORMAL_ARGUMENTS(SDOperand Op, SelectionDAG &DAG, 313 int &VarArgsFrameIndex) { 314 std::vector<SDOperand> ArgValues; 315 SDOperand Root = Op.getOperand(0); 316 unsigned VRegs[4]; 317 318 unsigned NumArgs = Op.Val->getNumValues()-1; 319 for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo) { 320 SDOperand ArgVal = LowerFORMAL_ARGUMENT(Op, DAG, VRegs, ArgNo); 321 322 ArgValues.push_back(ArgVal); 323 } 324 325 bool isVarArg = cast<ConstantSDNode>(Op.getOperand(2))->getValue() != 0; 326 if (isVarArg) { 327 MachineFunction &MF = DAG.getMachineFunction(); 328 SSARegMap *RegMap = MF.getSSARegMap(); 329 MachineFrameInfo *MFI = MF.getFrameInfo(); 330 VarArgsFrameIndex = MFI->CreateFixedObject(MVT::getSizeInBits(MVT::i32)/8, 331 -16 + NumArgs * 4); 332 333 334 static const unsigned REGS[] = { 335 ARM::R0, ARM::R1, ARM::R2, ARM::R3 336 }; 337 // If this function is vararg, store r0-r3 to their spots on the stack 338 // so that they may be loaded by deferencing the result of va_next. 339 SmallVector<SDOperand, 4> MemOps; 340 for (unsigned ArgNo = 0; ArgNo < 4; ++ArgNo) { 341 int ArgOffset = - (4 - ArgNo) * 4; 342 int FI = MFI->CreateFixedObject(MVT::getSizeInBits(MVT::i32)/8, 343 ArgOffset); 344 SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32); 345 346 unsigned VReg; 347 if (ArgNo < NumArgs) 348 VReg = VRegs[ArgNo]; 349 else 350 VReg = RegMap->createVirtualRegister(&ARM::IntRegsRegClass); 351 if (ArgNo >= NumArgs) 352 MF.addLiveIn(REGS[ArgNo], VReg); 353 354 SDOperand Val = DAG.getCopyFromReg(Root, VReg, MVT::i32); 355 SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Val.getValue(1), 356 Val, FIN, DAG.getSrcValue(NULL)); 357 MemOps.push_back(Store); 358 } 359 Root = DAG.getNode(ISD::TokenFactor, MVT::Other,&MemOps[0],MemOps.size()); 360 } 361 362 ArgValues.push_back(Root); 363 364 // Return the new list of results. 365 std::vector<MVT::ValueType> RetVT(Op.Val->value_begin(), 366 Op.Val->value_end()); 367 return DAG.getNode(ISD::MERGE_VALUES, RetVT, &ArgValues[0], ArgValues.size()); 368} 369 370static SDOperand LowerSELECT_CC(SDOperand Op, SelectionDAG &DAG) { 371 SDOperand LHS = Op.getOperand(0); 372 SDOperand RHS = Op.getOperand(1); 373 ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(4))->get(); 374 SDOperand TrueVal = Op.getOperand(2); 375 SDOperand FalseVal = Op.getOperand(3); 376 SDOperand ARMCC = DAG.getConstant(DAGCCToARMCC(CC), MVT::i32); 377 378 SDOperand Cmp = DAG.getNode(ARMISD::CMP, MVT::Flag, LHS, RHS); 379 return DAG.getNode(ARMISD::SELECT, MVT::i32, FalseVal, TrueVal, ARMCC, Cmp); 380} 381 382static SDOperand LowerBR_CC(SDOperand Op, SelectionDAG &DAG) { 383 SDOperand Chain = Op.getOperand(0); 384 ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(1))->get(); 385 SDOperand LHS = Op.getOperand(2); 386 SDOperand RHS = Op.getOperand(3); 387 SDOperand Dest = Op.getOperand(4); 388 SDOperand ARMCC = DAG.getConstant(DAGCCToARMCC(CC), MVT::i32); 389 390 SDOperand Cmp = DAG.getNode(ARMISD::CMP, MVT::Flag, LHS, RHS); 391 return DAG.getNode(ARMISD::BR, MVT::Other, Chain, Dest, ARMCC, Cmp); 392} 393 394SDOperand ARMTargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) { 395 switch (Op.getOpcode()) { 396 default: 397 assert(0 && "Should not custom lower this!"); 398 abort(); 399 case ISD::ConstantPool: 400 return LowerConstantPool(Op, DAG); 401 case ISD::GlobalAddress: 402 return LowerGlobalAddress(Op, DAG); 403 case ISD::FORMAL_ARGUMENTS: 404 return LowerFORMAL_ARGUMENTS(Op, DAG, VarArgsFrameIndex); 405 case ISD::CALL: 406 return LowerCALL(Op, DAG); 407 case ISD::RET: 408 return LowerRET(Op, DAG); 409 case ISD::SELECT_CC: 410 return LowerSELECT_CC(Op, DAG); 411 case ISD::BR_CC: 412 return LowerBR_CC(Op, DAG); 413 case ISD::VASTART: 414 return LowerVASTART(Op, DAG, VarArgsFrameIndex); 415 } 416} 417 418//===----------------------------------------------------------------------===// 419// Instruction Selector Implementation 420//===----------------------------------------------------------------------===// 421 422//===--------------------------------------------------------------------===// 423/// ARMDAGToDAGISel - ARM specific code to select ARM machine 424/// instructions for SelectionDAG operations. 425/// 426namespace { 427class ARMDAGToDAGISel : public SelectionDAGISel { 428 ARMTargetLowering Lowering; 429 430public: 431 ARMDAGToDAGISel(TargetMachine &TM) 432 : SelectionDAGISel(Lowering), Lowering(TM) { 433 } 434 435 SDNode *Select(SDOperand Op); 436 virtual void InstructionSelectBasicBlock(SelectionDAG &DAG); 437 bool SelectAddrRegImm(SDOperand N, SDOperand &Offset, SDOperand &Base); 438 439 // Include the pieces autogenerated from the target description. 440#include "ARMGenDAGISel.inc" 441}; 442 443void ARMDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) { 444 DEBUG(BB->dump()); 445 446 DAG.setRoot(SelectRoot(DAG.getRoot())); 447 DAG.RemoveDeadNodes(); 448 449 ScheduleAndEmitDAG(DAG); 450} 451 452static bool isInt12Immediate(SDNode *N, short &Imm) { 453 if (N->getOpcode() != ISD::Constant) 454 return false; 455 456 int32_t t = cast<ConstantSDNode>(N)->getValue(); 457 int max = 2<<12 - 1; 458 int min = -max; 459 if (t > min && t < max) { 460 Imm = t; 461 return true; 462 } 463 else 464 return false; 465} 466 467static bool isInt12Immediate(SDOperand Op, short &Imm) { 468 return isInt12Immediate(Op.Val, Imm); 469} 470 471//register plus/minus 12 bit offset 472bool ARMDAGToDAGISel::SelectAddrRegImm(SDOperand N, SDOperand &Offset, 473 SDOperand &Base) { 474 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(N)) { 475 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32); 476 Offset = CurDAG->getTargetConstant(0, MVT::i32); 477 return true; 478 } 479 if (N.getOpcode() == ISD::ADD) { 480 short imm = 0; 481 if (isInt12Immediate(N.getOperand(1), imm)) { 482 Offset = CurDAG->getTargetConstant(imm, MVT::i32); 483 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) { 484 Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType()); 485 } else { 486 Base = N.getOperand(0); 487 } 488 return true; // [r+i] 489 } 490 } 491 492 Offset = CurDAG->getTargetConstant(0, MVT::i32); 493 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N)) { 494 Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType()); 495 } 496 else 497 Base = N; 498 return true; //any address fits in a register 499} 500 501SDNode *ARMDAGToDAGISel::Select(SDOperand Op) { 502 SDNode *N = Op.Val; 503 504 switch (N->getOpcode()) { 505 default: 506 return SelectCode(Op); 507 break; 508 } 509 return NULL; 510} 511 512} // end anonymous namespace 513 514/// createARMISelDag - This pass converts a legalized DAG into a 515/// ARM-specific DAG, ready for instruction scheduling. 516/// 517FunctionPass *llvm::createARMISelDag(TargetMachine &TM) { 518 return new ARMDAGToDAGISel(TM); 519} 520