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