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