SelectionDAGISel.cpp revision 18c2f13e0f9d0e5d6227cf6d1881e9ee3d1b6109
1//===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the SelectionDAGISel class. 11// 12//===----------------------------------------------------------------------===// 13 14#define DEBUG_TYPE "isel" 15#include "llvm/CodeGen/SelectionDAGISel.h" 16#include "llvm/Constants.h" 17#include "llvm/DerivedTypes.h" 18#include "llvm/Function.h" 19#include "llvm/Instructions.h" 20#include "llvm/Intrinsics.h" 21#include "llvm/CodeGen/MachineFunction.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/MachineInstrBuilder.h" 24#include "llvm/CodeGen/SelectionDAG.h" 25#include "llvm/CodeGen/SSARegMap.h" 26#include "llvm/Target/TargetData.h" 27#include "llvm/Target/TargetFrameInfo.h" 28#include "llvm/Target/TargetInstrInfo.h" 29#include "llvm/Target/TargetLowering.h" 30#include "llvm/Target/TargetMachine.h" 31#include "llvm/Support/CommandLine.h" 32#include "llvm/Support/Debug.h" 33#include <map> 34#include <iostream> 35using namespace llvm; 36 37#ifndef _NDEBUG 38static cl::opt<bool> 39ViewDAGs("view-isel-dags", cl::Hidden, 40 cl::desc("Pop up a window to show isel dags as they are selected")); 41#else 42static const bool ViewDAGS = 0; 43#endif 44 45namespace llvm { 46 //===--------------------------------------------------------------------===// 47 /// FunctionLoweringInfo - This contains information that is global to a 48 /// function that is used when lowering a region of the function. 49 class FunctionLoweringInfo { 50 public: 51 TargetLowering &TLI; 52 Function &Fn; 53 MachineFunction &MF; 54 SSARegMap *RegMap; 55 56 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF); 57 58 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry. 59 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap; 60 61 /// ValueMap - Since we emit code for the function a basic block at a time, 62 /// we must remember which virtual registers hold the values for 63 /// cross-basic-block values. 64 std::map<const Value*, unsigned> ValueMap; 65 66 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in 67 /// the entry block. This allows the allocas to be efficiently referenced 68 /// anywhere in the function. 69 std::map<const AllocaInst*, int> StaticAllocaMap; 70 71 unsigned MakeReg(MVT::ValueType VT) { 72 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 73 } 74 75 unsigned CreateRegForValue(const Value *V) { 76 MVT::ValueType VT = TLI.getValueType(V->getType()); 77 // The common case is that we will only create one register for this 78 // value. If we have that case, create and return the virtual register. 79 unsigned NV = TLI.getNumElements(VT); 80 if (NV == 1) return MakeReg(VT); 81 82 // If this value is represented with multiple target registers, make sure 83 // to create enough consequtive registers of the right (smaller) type. 84 unsigned NT = VT-1; // Find the type to use. 85 while (TLI.getNumElements((MVT::ValueType)NT) != 1) 86 --NT; 87 88 unsigned R = MakeReg((MVT::ValueType)NT); 89 for (unsigned i = 1; i != NV; ++i) 90 MakeReg((MVT::ValueType)NT); 91 return R; 92 } 93 94 unsigned InitializeRegForValue(const Value *V) { 95 unsigned &R = ValueMap[V]; 96 assert(R == 0 && "Already initialized this value register!"); 97 return R = CreateRegForValue(V); 98 } 99 }; 100} 101 102/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by 103/// PHI nodes or outside of the basic block that defines it. 104static bool isUsedOutsideOfDefiningBlock(Instruction *I) { 105 if (isa<PHINode>(I)) return true; 106 BasicBlock *BB = I->getParent(); 107 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) 108 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI)) 109 return true; 110 return false; 111} 112 113FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, 114 Function &fn, MachineFunction &mf) 115 : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) { 116 117 // Initialize the mapping of values to registers. This is only set up for 118 // instruction values that are used outside of the block that defines 119 // them. 120 for (Function::aiterator AI = Fn.abegin(), E = Fn.aend(); AI != E; ++AI) 121 InitializeRegForValue(AI); 122 123 Function::iterator BB = Fn.begin(), E = Fn.end(); 124 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 125 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 126 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(AI->getArraySize())) { 127 const Type *Ty = AI->getAllocatedType(); 128 uint64_t TySize = TLI.getTargetData().getTypeSize(Ty); 129 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); 130 TySize *= CUI->getValue(); // Get total allocated size. 131 StaticAllocaMap[AI] = 132 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 133 } 134 135 for (; BB != E; ++BB) 136 for (BasicBlock::iterator I = BB->begin(), e = BB->end(); I != e; ++I) 137 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I)) 138 if (!isa<AllocaInst>(I) || 139 !StaticAllocaMap.count(cast<AllocaInst>(I))) 140 InitializeRegForValue(I); 141 142 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This 143 // also creates the initial PHI MachineInstrs, though none of the input 144 // operands are populated. 145 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 146 MachineBasicBlock *MBB = new MachineBasicBlock(BB); 147 MBBMap[BB] = MBB; 148 MF.getBasicBlockList().push_back(MBB); 149 150 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as 151 // appropriate. 152 PHINode *PN; 153 for (BasicBlock::iterator I = BB->begin(); 154 (PN = dyn_cast<PHINode>(I)); ++I) 155 if (!PN->use_empty()) { 156 unsigned NumElements = 157 TLI.getNumElements(TLI.getValueType(PN->getType())); 158 unsigned PHIReg = ValueMap[PN]; 159 assert(PHIReg &&"PHI node does not have an assigned virtual register!"); 160 for (unsigned i = 0; i != NumElements; ++i) 161 BuildMI(MBB, TargetInstrInfo::PHI, PN->getNumOperands(), PHIReg+i); 162 } 163 } 164} 165 166 167 168//===----------------------------------------------------------------------===// 169/// SelectionDAGLowering - This is the common target-independent lowering 170/// implementation that is parameterized by a TargetLowering object. 171/// Also, targets can overload any lowering method. 172/// 173namespace llvm { 174class SelectionDAGLowering { 175 MachineBasicBlock *CurMBB; 176 177 std::map<const Value*, SDOperand> NodeMap; 178 179public: 180 // TLI - This is information that describes the available target features we 181 // need for lowering. This indicates when operations are unavailable, 182 // implemented with a libcall, etc. 183 TargetLowering &TLI; 184 SelectionDAG &DAG; 185 const TargetData &TD; 186 187 /// FuncInfo - Information about the function as a whole. 188 /// 189 FunctionLoweringInfo &FuncInfo; 190 191 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli, 192 FunctionLoweringInfo &funcinfo) 193 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()), 194 FuncInfo(funcinfo) { 195 } 196 197 void visit(Instruction &I) { visit(I.getOpcode(), I); } 198 199 void visit(unsigned Opcode, User &I) { 200 switch (Opcode) { 201 default: assert(0 && "Unknown instruction type encountered!"); 202 abort(); 203 // Build the switch statement using the Instruction.def file. 204#define HANDLE_INST(NUM, OPCODE, CLASS) \ 205 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I); 206#include "llvm/Instruction.def" 207 } 208 } 209 210 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 211 212 213 SDOperand getIntPtrConstant(uint64_t Val) { 214 return DAG.getConstant(Val, TLI.getPointerTy()); 215 } 216 217 SDOperand getValue(const Value *V) { 218 SDOperand &N = NodeMap[V]; 219 if (N.Val) return N; 220 221 MVT::ValueType VT = TLI.getValueType(V->getType()); 222 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) 223 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 224 visit(CE->getOpcode(), *CE); 225 assert(N.Val && "visit didn't populate the ValueMap!"); 226 return N; 227 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) { 228 return N = DAG.getGlobalAddress(GV, VT); 229 } else if (isa<ConstantPointerNull>(C)) { 230 return N = DAG.getConstant(0, TLI.getPointerTy()); 231 } else if (isa<UndefValue>(C)) { 232 /// FIXME: Implement UNDEFVALUE better. 233 if (MVT::isInteger(VT)) 234 return N = DAG.getConstant(0, VT); 235 else if (MVT::isFloatingPoint(VT)) 236 return N = DAG.getConstantFP(0, VT); 237 else 238 assert(0 && "Unknown value type!"); 239 240 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 241 return N = DAG.getConstantFP(CFP->getValue(), VT); 242 } else { 243 // Canonicalize all constant ints to be unsigned. 244 return N = DAG.getConstant(cast<ConstantIntegral>(C)->getRawValue(),VT); 245 } 246 247 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 248 std::map<const AllocaInst*, int>::iterator SI = 249 FuncInfo.StaticAllocaMap.find(AI); 250 if (SI != FuncInfo.StaticAllocaMap.end()) 251 return DAG.getFrameIndex(SI->second, TLI.getPointerTy()); 252 } 253 254 std::map<const Value*, unsigned>::const_iterator VMI = 255 FuncInfo.ValueMap.find(V); 256 assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!"); 257 return N = DAG.getCopyFromReg(VMI->second, VT); 258 } 259 260 const SDOperand &setValue(const Value *V, SDOperand NewN) { 261 SDOperand &N = NodeMap[V]; 262 assert(N.Val == 0 && "Already set a value for this node!"); 263 return N = NewN; 264 } 265 266 // Terminator instructions. 267 void visitRet(ReturnInst &I); 268 void visitBr(BranchInst &I); 269 void visitUnreachable(UnreachableInst &I) { /* noop */ } 270 271 // These all get lowered before this pass. 272 void visitSwitch(SwitchInst &I) { assert(0 && "TODO"); } 273 void visitInvoke(InvokeInst &I) { assert(0 && "TODO"); } 274 void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); } 275 276 // 277 void visitBinary(User &I, unsigned Opcode); 278 void visitAdd(User &I) { visitBinary(I, ISD::ADD); } 279 void visitSub(User &I) { visitBinary(I, ISD::SUB); } 280 void visitMul(User &I) { visitBinary(I, ISD::MUL); } 281 void visitDiv(User &I) { 282 visitBinary(I, I.getType()->isUnsigned() ? ISD::UDIV : ISD::SDIV); 283 } 284 void visitRem(User &I) { 285 visitBinary(I, I.getType()->isUnsigned() ? ISD::UREM : ISD::SREM); 286 } 287 void visitAnd(User &I) { visitBinary(I, ISD::AND); } 288 void visitOr (User &I) { visitBinary(I, ISD::OR); } 289 void visitXor(User &I) { visitBinary(I, ISD::XOR); } 290 void visitShl(User &I) { visitBinary(I, ISD::SHL); } 291 void visitShr(User &I) { 292 visitBinary(I, I.getType()->isUnsigned() ? ISD::SRL : ISD::SRA); 293 } 294 295 void visitSetCC(User &I, ISD::CondCode SignedOpc, ISD::CondCode UnsignedOpc); 296 void visitSetEQ(User &I) { visitSetCC(I, ISD::SETEQ, ISD::SETEQ); } 297 void visitSetNE(User &I) { visitSetCC(I, ISD::SETNE, ISD::SETNE); } 298 void visitSetLE(User &I) { visitSetCC(I, ISD::SETLE, ISD::SETULE); } 299 void visitSetGE(User &I) { visitSetCC(I, ISD::SETGE, ISD::SETUGE); } 300 void visitSetLT(User &I) { visitSetCC(I, ISD::SETLT, ISD::SETULT); } 301 void visitSetGT(User &I) { visitSetCC(I, ISD::SETGT, ISD::SETUGT); } 302 303 void visitGetElementPtr(User &I); 304 void visitCast(User &I); 305 void visitSelect(User &I); 306 // 307 308 void visitMalloc(MallocInst &I); 309 void visitFree(FreeInst &I); 310 void visitAlloca(AllocaInst &I); 311 void visitLoad(LoadInst &I); 312 void visitStore(StoreInst &I); 313 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 314 void visitCall(CallInst &I); 315 316 void visitVAStart(CallInst &I); 317 void visitVANext(VANextInst &I); 318 void visitVAArg(VAArgInst &I); 319 void visitVAEnd(CallInst &I); 320 void visitVACopy(CallInst &I); 321 void visitFrameReturnAddress(CallInst &I, bool isFrameAddress); 322 323 void visitMemIntrinsic(CallInst &I, unsigned Op); 324 325 void visitUserOp1(Instruction &I) { 326 assert(0 && "UserOp1 should not exist at instruction selection time!"); 327 abort(); 328 } 329 void visitUserOp2(Instruction &I) { 330 assert(0 && "UserOp2 should not exist at instruction selection time!"); 331 abort(); 332 } 333}; 334} // end namespace llvm 335 336void SelectionDAGLowering::visitRet(ReturnInst &I) { 337 if (I.getNumOperands() == 0) { 338 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, DAG.getRoot())); 339 return; 340 } 341 342 SDOperand Op1 = getValue(I.getOperand(0)); 343 switch (Op1.getValueType()) { 344 default: assert(0 && "Unknown value type!"); 345 case MVT::i1: 346 case MVT::i8: 347 case MVT::i16: 348 // Extend integer types to 32-bits. 349 if (I.getOperand(0)->getType()->isSigned()) 350 Op1 = DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Op1); 351 else 352 Op1 = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Op1); 353 break; 354 case MVT::f32: 355 // Extend float to double. 356 Op1 = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Op1); 357 break; 358 case MVT::i32: 359 case MVT::i64: 360 case MVT::f64: 361 break; // No extension needed! 362 } 363 364 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, DAG.getRoot(), Op1)); 365} 366 367void SelectionDAGLowering::visitBr(BranchInst &I) { 368 // Update machine-CFG edges. 369 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)]; 370 CurMBB->addSuccessor(Succ0MBB); 371 372 // Figure out which block is immediately after the current one. 373 MachineBasicBlock *NextBlock = 0; 374 MachineFunction::iterator BBI = CurMBB; 375 if (++BBI != CurMBB->getParent()->end()) 376 NextBlock = BBI; 377 378 if (I.isUnconditional()) { 379 // If this is not a fall-through branch, emit the branch. 380 if (Succ0MBB != NextBlock) 381 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, DAG.getRoot(), 382 DAG.getBasicBlock(Succ0MBB))); 383 } else { 384 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)]; 385 CurMBB->addSuccessor(Succ1MBB); 386 387 SDOperand Cond = getValue(I.getCondition()); 388 389 if (Succ1MBB == NextBlock) { 390 // If the condition is false, fall through. This means we should branch 391 // if the condition is true to Succ #0. 392 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, DAG.getRoot(), 393 Cond, DAG.getBasicBlock(Succ0MBB))); 394 } else if (Succ0MBB == NextBlock) { 395 // If the condition is true, fall through. This means we should branch if 396 // the condition is false to Succ #1. Invert the condition first. 397 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 398 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 399 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, DAG.getRoot(), 400 Cond, DAG.getBasicBlock(Succ1MBB))); 401 } else { 402 // Neither edge is a fall through. If the comparison is true, jump to 403 // Succ#0, otherwise branch unconditionally to succ #1. 404 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, DAG.getRoot(), 405 Cond, DAG.getBasicBlock(Succ0MBB))); 406 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, DAG.getRoot(), 407 DAG.getBasicBlock(Succ1MBB))); 408 } 409 } 410} 411 412void SelectionDAGLowering::visitBinary(User &I, unsigned Opcode) { 413 SDOperand Op1 = getValue(I.getOperand(0)); 414 SDOperand Op2 = getValue(I.getOperand(1)); 415 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2)); 416} 417 418void SelectionDAGLowering::visitSetCC(User &I,ISD::CondCode SignedOpcode, 419 ISD::CondCode UnsignedOpcode) { 420 SDOperand Op1 = getValue(I.getOperand(0)); 421 SDOperand Op2 = getValue(I.getOperand(1)); 422 ISD::CondCode Opcode = SignedOpcode; 423 if (I.getOperand(0)->getType()->isUnsigned()) 424 Opcode = UnsignedOpcode; 425 setValue(&I, DAG.getSetCC(Opcode, Op1, Op2)); 426} 427 428void SelectionDAGLowering::visitSelect(User &I) { 429 SDOperand Cond = getValue(I.getOperand(0)); 430 SDOperand TrueVal = getValue(I.getOperand(1)); 431 SDOperand FalseVal = getValue(I.getOperand(2)); 432 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond, 433 TrueVal, FalseVal)); 434} 435 436void SelectionDAGLowering::visitCast(User &I) { 437 SDOperand N = getValue(I.getOperand(0)); 438 MVT::ValueType SrcTy = TLI.getValueType(I.getOperand(0)->getType()); 439 MVT::ValueType DestTy = TLI.getValueType(I.getType()); 440 441 if (N.getValueType() == DestTy) { 442 setValue(&I, N); // noop cast. 443 } else if (isInteger(SrcTy)) { 444 if (isInteger(DestTy)) { // Int -> Int cast 445 if (DestTy < SrcTy) // Truncating cast? 446 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestTy, N)); 447 else if (I.getOperand(0)->getType()->isSigned()) 448 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestTy, N)); 449 else 450 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestTy, N)); 451 } else { // Int -> FP cast 452 if (I.getOperand(0)->getType()->isSigned()) 453 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestTy, N)); 454 else 455 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestTy, N)); 456 } 457 } else { 458 assert(isFloatingPoint(SrcTy) && "Unknown value type!"); 459 if (isFloatingPoint(DestTy)) { // FP -> FP cast 460 if (DestTy < SrcTy) // Rounding cast? 461 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestTy, N)); 462 else 463 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestTy, N)); 464 } else { // FP -> Int cast. 465 if (I.getType()->isSigned()) 466 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestTy, N)); 467 else 468 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestTy, N)); 469 } 470 } 471} 472 473void SelectionDAGLowering::visitGetElementPtr(User &I) { 474 SDOperand N = getValue(I.getOperand(0)); 475 const Type *Ty = I.getOperand(0)->getType(); 476 const Type *UIntPtrTy = TD.getIntPtrType(); 477 478 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end(); 479 OI != E; ++OI) { 480 Value *Idx = *OI; 481 if (const StructType *StTy = dyn_cast<StructType> (Ty)) { 482 unsigned Field = cast<ConstantUInt>(Idx)->getValue(); 483 if (Field) { 484 // N = N + Offset 485 uint64_t Offset = TD.getStructLayout(StTy)->MemberOffsets[Field]; 486 N = DAG.getNode(ISD::ADD, N.getValueType(), N, 487 getIntPtrConstant(Offset)); 488 } 489 Ty = StTy->getElementType(Field); 490 } else { 491 Ty = cast<SequentialType>(Ty)->getElementType(); 492 if (!isa<Constant>(Idx) || !cast<Constant>(Idx)->isNullValue()) { 493 // N = N + Idx * ElementSize; 494 uint64_t ElementSize = TD.getTypeSize(Ty); 495 SDOperand IdxN = getValue(Idx), Scale = getIntPtrConstant(ElementSize); 496 497 // If the index is smaller or larger than intptr_t, truncate or extend 498 // it. 499 if (IdxN.getValueType() < Scale.getValueType()) { 500 if (Idx->getType()->isSigned()) 501 IdxN = DAG.getNode(ISD::SIGN_EXTEND, Scale.getValueType(), IdxN); 502 else 503 IdxN = DAG.getNode(ISD::ZERO_EXTEND, Scale.getValueType(), IdxN); 504 } else if (IdxN.getValueType() > Scale.getValueType()) 505 IdxN = DAG.getNode(ISD::TRUNCATE, Scale.getValueType(), IdxN); 506 507 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale); 508 509 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 510 } 511 } 512 } 513 setValue(&I, N); 514} 515 516void SelectionDAGLowering::visitAlloca(AllocaInst &I) { 517 // If this is a fixed sized alloca in the entry block of the function, 518 // allocate it statically on the stack. 519 if (FuncInfo.StaticAllocaMap.count(&I)) 520 return; // getValue will auto-populate this. 521 522 const Type *Ty = I.getAllocatedType(); 523 uint64_t TySize = TLI.getTargetData().getTypeSize(Ty); 524 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); 525 526 SDOperand AllocSize = getValue(I.getArraySize()); 527 528 assert(AllocSize.getValueType() == TLI.getPointerTy() && 529 "FIXME: should extend or truncate to pointer size!"); 530 531 AllocSize = DAG.getNode(ISD::MUL, TLI.getPointerTy(), AllocSize, 532 getIntPtrConstant(TySize)); 533 534 // Handle alignment. If the requested alignment is less than or equal to the 535 // stack alignment, ignore it and round the size of the allocation up to the 536 // stack alignment size. If the size is greater than the stack alignment, we 537 // note this in the DYNAMIC_STACKALLOC node. 538 unsigned StackAlign = 539 TLI.getTargetMachine().getFrameInfo()->getStackAlignment(); 540 if (Align <= StackAlign) { 541 Align = 0; 542 // Add SA-1 to the size. 543 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize, 544 getIntPtrConstant(StackAlign-1)); 545 // Mask out the low bits for alignment purposes. 546 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize, 547 getIntPtrConstant(~(uint64_t)(StackAlign-1))); 548 } 549 550 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, AllocSize.getValueType(), 551 DAG.getRoot(), AllocSize, 552 getIntPtrConstant(Align)); 553 DAG.setRoot(setValue(&I, DSA).getValue(1)); 554 555 // Inform the Frame Information that we have just allocated a variable-sized 556 // object. 557 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject(); 558} 559 560 561void SelectionDAGLowering::visitLoad(LoadInst &I) { 562 SDOperand Ptr = getValue(I.getOperand(0)); 563 SDOperand L = DAG.getLoad(TLI.getValueType(I.getType()), DAG.getRoot(), Ptr); 564 DAG.setRoot(setValue(&I, L).getValue(1)); 565} 566 567 568void SelectionDAGLowering::visitStore(StoreInst &I) { 569 Value *SrcV = I.getOperand(0); 570 SDOperand Src = getValue(SrcV); 571 SDOperand Ptr = getValue(I.getOperand(1)); 572 DAG.setRoot(DAG.getNode(ISD::STORE, MVT::Other, DAG.getRoot(), Src, Ptr)); 573 return; 574} 575 576void SelectionDAGLowering::visitCall(CallInst &I) { 577 const char *RenameFn = 0; 578 if (Function *F = I.getCalledFunction()) 579 switch (F->getIntrinsicID()) { 580 case 0: break; // Not an intrinsic. 581 case Intrinsic::vastart: visitVAStart(I); return; 582 case Intrinsic::vaend: visitVAEnd(I); return; 583 case Intrinsic::vacopy: visitVACopy(I); return; 584 case Intrinsic::returnaddress: visitFrameReturnAddress(I, false); return; 585 case Intrinsic::frameaddress: visitFrameReturnAddress(I, true); return; 586 default: 587 // FIXME: IMPLEMENT THESE. 588 // readport, writeport, readio, writeio 589 assert(0 && "This intrinsic is not implemented yet!"); 590 return; 591 case Intrinsic::setjmp: RenameFn = "setjmp"; break; 592 case Intrinsic::longjmp: RenameFn = "longjmp"; break; 593 case Intrinsic::memcpy: visitMemIntrinsic(I, ISD::MEMCPY); return; 594 case Intrinsic::memset: visitMemIntrinsic(I, ISD::MEMSET); return; 595 case Intrinsic::memmove: visitMemIntrinsic(I, ISD::MEMMOVE); return; 596 597 case Intrinsic::isunordered: 598 setValue(&I, DAG.getSetCC(ISD::SETUO, getValue(I.getOperand(1)), 599 getValue(I.getOperand(2)))); 600 return; 601 } 602 603 SDOperand Callee; 604 if (!RenameFn) 605 Callee = getValue(I.getOperand(0)); 606 else 607 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy()); 608 std::vector<std::pair<SDOperand, const Type*> > Args; 609 610 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 611 Value *Arg = I.getOperand(i); 612 SDOperand ArgNode = getValue(Arg); 613 Args.push_back(std::make_pair(ArgNode, Arg->getType())); 614 } 615 616 std::pair<SDOperand,SDOperand> Result = 617 TLI.LowerCallTo(DAG.getRoot(), I.getType(), Callee, Args, DAG); 618 if (I.getType() != Type::VoidTy) 619 setValue(&I, Result.first); 620 DAG.setRoot(Result.second); 621} 622 623void SelectionDAGLowering::visitMalloc(MallocInst &I) { 624 SDOperand Src = getValue(I.getOperand(0)); 625 626 MVT::ValueType IntPtr = TLI.getPointerTy(); 627 // FIXME: Extend or truncate to the intptr size. 628 assert(Src.getValueType() == IntPtr && "Need to adjust the amount!"); 629 630 // Scale the source by the type size. 631 uint64_t ElementSize = TD.getTypeSize(I.getType()->getElementType()); 632 Src = DAG.getNode(ISD::MUL, Src.getValueType(), 633 Src, getIntPtrConstant(ElementSize)); 634 635 std::vector<std::pair<SDOperand, const Type*> > Args; 636 Args.push_back(std::make_pair(Src, TLI.getTargetData().getIntPtrType())); 637 638 std::pair<SDOperand,SDOperand> Result = 639 TLI.LowerCallTo(DAG.getRoot(), I.getType(), 640 DAG.getExternalSymbol("malloc", IntPtr), 641 Args, DAG); 642 setValue(&I, Result.first); // Pointers always fit in registers 643 DAG.setRoot(Result.second); 644} 645 646void SelectionDAGLowering::visitFree(FreeInst &I) { 647 std::vector<std::pair<SDOperand, const Type*> > Args; 648 Args.push_back(std::make_pair(getValue(I.getOperand(0)), 649 TLI.getTargetData().getIntPtrType())); 650 MVT::ValueType IntPtr = TLI.getPointerTy(); 651 std::pair<SDOperand,SDOperand> Result = 652 TLI.LowerCallTo(DAG.getRoot(), Type::VoidTy, 653 DAG.getExternalSymbol("free", IntPtr), Args, DAG); 654 DAG.setRoot(Result.second); 655} 656 657std::pair<SDOperand, SDOperand> 658TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) { 659 // We have no sane default behavior, just emit a useful error message and bail 660 // out. 661 std::cerr << "Variable arguments handling not implemented on this target!\n"; 662 abort(); 663} 664 665SDOperand TargetLowering::LowerVAEnd(SDOperand Chain, SDOperand L, 666 SelectionDAG &DAG) { 667 // Default to a noop. 668 return Chain; 669} 670 671std::pair<SDOperand,SDOperand> 672TargetLowering::LowerVACopy(SDOperand Chain, SDOperand L, SelectionDAG &DAG) { 673 // Default to returning the input list. 674 return std::make_pair(L, Chain); 675} 676 677std::pair<SDOperand,SDOperand> 678TargetLowering::LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList, 679 const Type *ArgTy, SelectionDAG &DAG) { 680 // We have no sane default behavior, just emit a useful error message and bail 681 // out. 682 std::cerr << "Variable arguments handling not implemented on this target!\n"; 683 abort(); 684} 685 686 687void SelectionDAGLowering::visitVAStart(CallInst &I) { 688 std::pair<SDOperand,SDOperand> Result = TLI.LowerVAStart(DAG.getRoot(), DAG); 689 setValue(&I, Result.first); 690 DAG.setRoot(Result.second); 691} 692 693void SelectionDAGLowering::visitVAArg(VAArgInst &I) { 694 std::pair<SDOperand,SDOperand> Result = 695 TLI.LowerVAArgNext(false, DAG.getRoot(), getValue(I.getOperand(0)), 696 I.getType(), DAG); 697 setValue(&I, Result.first); 698 DAG.setRoot(Result.second); 699} 700 701void SelectionDAGLowering::visitVANext(VANextInst &I) { 702 std::pair<SDOperand,SDOperand> Result = 703 TLI.LowerVAArgNext(true, DAG.getRoot(), getValue(I.getOperand(0)), 704 I.getArgType(), DAG); 705 setValue(&I, Result.first); 706 DAG.setRoot(Result.second); 707} 708 709void SelectionDAGLowering::visitVAEnd(CallInst &I) { 710 DAG.setRoot(TLI.LowerVAEnd(DAG.getRoot(), getValue(I.getOperand(1)), DAG)); 711} 712 713void SelectionDAGLowering::visitVACopy(CallInst &I) { 714 std::pair<SDOperand,SDOperand> Result = 715 TLI.LowerVACopy(DAG.getRoot(), getValue(I.getOperand(1)), DAG); 716 setValue(&I, Result.first); 717 DAG.setRoot(Result.second); 718} 719 720 721// It is always conservatively correct for llvm.returnaddress and 722// llvm.frameaddress to return 0. 723std::pair<SDOperand, SDOperand> 724TargetLowering::LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, 725 unsigned Depth, SelectionDAG &DAG) { 726 return std::make_pair(DAG.getConstant(0, getPointerTy()), Chain); 727} 728 729void SelectionDAGLowering::visitFrameReturnAddress(CallInst &I, bool isFrame) { 730 unsigned Depth = (unsigned)cast<ConstantUInt>(I.getOperand(1))->getValue(); 731 std::pair<SDOperand,SDOperand> Result = 732 TLI.LowerFrameReturnAddress(isFrame, DAG.getRoot(), Depth, DAG); 733 setValue(&I, Result.first); 734 DAG.setRoot(Result.second); 735} 736 737void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) { 738 std::vector<SDOperand> Ops; 739 Ops.push_back(DAG.getRoot()); 740 Ops.push_back(getValue(I.getOperand(1))); 741 Ops.push_back(getValue(I.getOperand(2))); 742 Ops.push_back(getValue(I.getOperand(3))); 743 Ops.push_back(getValue(I.getOperand(4))); 744 DAG.setRoot(DAG.getNode(Op, MVT::Other, Ops)); 745} 746 747//===----------------------------------------------------------------------===// 748// SelectionDAGISel code 749//===----------------------------------------------------------------------===// 750 751unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) { 752 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 753} 754 755 756 757bool SelectionDAGISel::runOnFunction(Function &Fn) { 758 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine()); 759 RegMap = MF.getSSARegMap(); 760 DEBUG(std::cerr << "\n\n\n=== " << Fn.getName() << "\n"); 761 762 FunctionLoweringInfo FuncInfo(TLI, Fn, MF); 763 764 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 765 SelectBasicBlock(I, MF, FuncInfo); 766 767 return true; 768} 769 770 771SDOperand SelectionDAGISel:: 772CopyValueToVirtualRegister(SelectionDAGLowering &SDL, Value *V, unsigned Reg) { 773 SelectionDAG &DAG = SDL.DAG; 774 SDOperand Op = SDL.getValue(V); 775 assert((Op.getOpcode() != ISD::CopyFromReg || 776 cast<RegSDNode>(Op)->getReg() != Reg) && 777 "Copy from a reg to the same reg!"); 778 return DAG.getCopyToReg(DAG.getRoot(), Op, Reg); 779} 780 781void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, 782 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate, 783 FunctionLoweringInfo &FuncInfo) { 784 SelectionDAGLowering SDL(DAG, TLI, FuncInfo); 785 786 std::vector<SDOperand> UnorderedChains; 787 788 // If this is the entry block, emit arguments. 789 Function *F = LLVMBB->getParent(); 790 if (LLVMBB == &F->front()) { 791 // FIXME: If an argument is only used in one basic block, we could directly 792 // emit it (ONLY) into that block, not emitting the COPY_TO_VREG node. This 793 // would improve codegen in several cases on X86 by allowing the loads to be 794 // folded into the user operation. 795 std::vector<SDOperand> Args = TLI.LowerArguments(*LLVMBB->getParent(), DAG); 796 797 unsigned a = 0; 798 for (Function::aiterator AI = F->abegin(), E = F->aend(); AI != E; ++AI,++a) 799 if (!AI->use_empty()) { 800 SDL.setValue(AI, Args[a]); 801 UnorderedChains.push_back( 802 CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI])); 803 } 804 } 805 806 BB = FuncInfo.MBBMap[LLVMBB]; 807 SDL.setCurrentBasicBlock(BB); 808 809 // Lower all of the non-terminator instructions. 810 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end(); 811 I != E; ++I) 812 SDL.visit(*I); 813 814 // Ensure that all instructions which are used outside of their defining 815 // blocks are available as virtual registers. 816 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I) 817 if (!I->use_empty() && !isa<PHINode>(I)) { 818 std::map<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I); 819 if (VMI != FuncInfo.ValueMap.end()) 820 UnorderedChains.push_back( 821 CopyValueToVirtualRegister(SDL, I, VMI->second)); 822 } 823 824 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to 825 // ensure constants are generated when needed. Remember the virtual registers 826 // that need to be added to the Machine PHI nodes as input. We cannot just 827 // directly add them, because expansion might result in multiple MBB's for one 828 // BB. As such, the start of the BB might correspond to a different MBB than 829 // the end. 830 // 831 832 // Emit constants only once even if used by multiple PHI nodes. 833 std::map<Constant*, unsigned> ConstantsOut; 834 835 // Check successor nodes PHI nodes that expect a constant to be available from 836 // this block. 837 TerminatorInst *TI = LLVMBB->getTerminator(); 838 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 839 BasicBlock *SuccBB = TI->getSuccessor(succ); 840 MachineBasicBlock::iterator MBBI = FuncInfo.MBBMap[SuccBB]->begin(); 841 PHINode *PN; 842 843 // At this point we know that there is a 1-1 correspondence between LLVM PHI 844 // nodes and Machine PHI nodes, but the incoming operands have not been 845 // emitted yet. 846 for (BasicBlock::iterator I = SuccBB->begin(); 847 (PN = dyn_cast<PHINode>(I)); ++I) 848 if (!PN->use_empty()) { 849 unsigned Reg; 850 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 851 if (Constant *C = dyn_cast<Constant>(PHIOp)) { 852 unsigned &RegOut = ConstantsOut[C]; 853 if (RegOut == 0) { 854 RegOut = FuncInfo.CreateRegForValue(C); 855 UnorderedChains.push_back( 856 CopyValueToVirtualRegister(SDL, C, RegOut)); 857 } 858 Reg = RegOut; 859 } else { 860 Reg = FuncInfo.ValueMap[PHIOp]; 861 if (Reg == 0) { 862 assert(isa<AllocaInst>(PHIOp) && 863 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) && 864 "Didn't codegen value into a register!??"); 865 Reg = FuncInfo.CreateRegForValue(PHIOp); 866 UnorderedChains.push_back( 867 CopyValueToVirtualRegister(SDL, PHIOp, Reg)); 868 } 869 } 870 871 // Remember that this register needs to added to the machine PHI node as 872 // the input for this MBB. 873 unsigned NumElements = 874 TLI.getNumElements(TLI.getValueType(PN->getType())); 875 for (unsigned i = 0, e = NumElements; i != e; ++i) 876 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); 877 } 878 } 879 ConstantsOut.clear(); 880 881 // Turn all of the unordered chains into one factored node. 882 if (!UnorderedChains.empty()) { 883 UnorderedChains.push_back(DAG.getRoot()); 884 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, UnorderedChains)); 885 } 886 887 // Lower the terminator after the copies are emitted. 888 SDL.visit(*LLVMBB->getTerminator()); 889} 890 891void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, 892 FunctionLoweringInfo &FuncInfo) { 893 SelectionDAG DAG(TLI.getTargetMachine(), MF); 894 CurDAG = &DAG; 895 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 896 897 // First step, lower LLVM code to some DAG. This DAG may use operations and 898 // types that are not supported by the target. 899 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo); 900 901 DEBUG(std::cerr << "Lowered selection DAG:\n"); 902 DEBUG(DAG.dump()); 903 904 // Second step, hack on the DAG until it only uses operations and types that 905 // the target supports. 906 DAG.Legalize(TLI); 907 908 DEBUG(std::cerr << "Legalized selection DAG:\n"); 909 DEBUG(DAG.dump()); 910 911 // Finally, instruction select all of the operations to machine code, adding 912 // the code to the MachineBasicBlock. 913 InstructionSelectBasicBlock(DAG); 914 915 if (ViewDAGs) DAG.viewGraph(); 916 917 DEBUG(std::cerr << "Selected machine code:\n"); 918 DEBUG(BB->dump()); 919 920 // Finally, now that we know what the last MBB the LLVM BB expanded is, update 921 // PHI nodes in successors. 922 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 923 MachineInstr *PHI = PHINodesToUpdate[i].first; 924 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 925 "This is not a machine PHI node that we are updating!"); 926 PHI->addRegOperand(PHINodesToUpdate[i].second); 927 PHI->addMachineBasicBlockOperand(BB); 928 } 929} 930