SelectionDAGISel.cpp revision d5d0f9bd20d9df07d6b4d41b7e8ed6d33b6a649d
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/CallingConv.h" 17#include "llvm/Constants.h" 18#include "llvm/DerivedTypes.h" 19#include "llvm/Function.h" 20#include "llvm/Instructions.h" 21#include "llvm/Intrinsics.h" 22#include "llvm/CodeGen/MachineFunction.h" 23#include "llvm/CodeGen/MachineFrameInfo.h" 24#include "llvm/CodeGen/MachineInstrBuilder.h" 25#include "llvm/CodeGen/SelectionDAG.h" 26#include "llvm/CodeGen/SSARegMap.h" 27#include "llvm/Target/TargetData.h" 28#include "llvm/Target/TargetFrameInfo.h" 29#include "llvm/Target/TargetInstrInfo.h" 30#include "llvm/Target/TargetLowering.h" 31#include "llvm/Target/TargetMachine.h" 32#include "llvm/Support/CommandLine.h" 33#include "llvm/Support/Debug.h" 34#include <map> 35#include <iostream> 36using namespace llvm; 37 38#ifndef _NDEBUG 39static cl::opt<bool> 40ViewDAGs("view-isel-dags", cl::Hidden, 41 cl::desc("Pop up a window to show isel dags as they are selected")); 42#else 43static const bool ViewDAGS = 0; 44#endif 45 46namespace llvm { 47 //===--------------------------------------------------------------------===// 48 /// FunctionLoweringInfo - This contains information that is global to a 49 /// function that is used when lowering a region of the function. 50 class FunctionLoweringInfo { 51 public: 52 TargetLowering &TLI; 53 Function &Fn; 54 MachineFunction &MF; 55 SSARegMap *RegMap; 56 57 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF); 58 59 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry. 60 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap; 61 62 /// ValueMap - Since we emit code for the function a basic block at a time, 63 /// we must remember which virtual registers hold the values for 64 /// cross-basic-block values. 65 std::map<const Value*, unsigned> ValueMap; 66 67 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in 68 /// the entry block. This allows the allocas to be efficiently referenced 69 /// anywhere in the function. 70 std::map<const AllocaInst*, int> StaticAllocaMap; 71 72 /// BlockLocalArguments - If any arguments are only used in a single basic 73 /// block, and if the target can access the arguments without side-effects, 74 /// avoid emitting CopyToReg nodes for those arguments. This map keeps 75 /// track of which arguments are local to each BB. 76 std::multimap<BasicBlock*, std::pair<Argument*, 77 unsigned> > BlockLocalArguments; 78 79 80 unsigned MakeReg(MVT::ValueType VT) { 81 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 82 } 83 84 unsigned CreateRegForValue(const Value *V) { 85 MVT::ValueType VT = TLI.getValueType(V->getType()); 86 // The common case is that we will only create one register for this 87 // value. If we have that case, create and return the virtual register. 88 unsigned NV = TLI.getNumElements(VT); 89 if (NV == 1) { 90 // If we are promoting this value, pick the next largest supported type. 91 return MakeReg(TLI.getTypeToTransformTo(VT)); 92 } 93 94 // If this value is represented with multiple target registers, make sure 95 // to create enough consequtive registers of the right (smaller) type. 96 unsigned NT = VT-1; // Find the type to use. 97 while (TLI.getNumElements((MVT::ValueType)NT) != 1) 98 --NT; 99 100 unsigned R = MakeReg((MVT::ValueType)NT); 101 for (unsigned i = 1; i != NV; ++i) 102 MakeReg((MVT::ValueType)NT); 103 return R; 104 } 105 106 unsigned InitializeRegForValue(const Value *V) { 107 unsigned &R = ValueMap[V]; 108 assert(R == 0 && "Already initialized this value register!"); 109 return R = CreateRegForValue(V); 110 } 111 }; 112} 113 114/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by 115/// PHI nodes or outside of the basic block that defines it. 116static bool isUsedOutsideOfDefiningBlock(Instruction *I) { 117 if (isa<PHINode>(I)) return true; 118 BasicBlock *BB = I->getParent(); 119 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) 120 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI)) 121 return true; 122 return false; 123} 124 125FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, 126 Function &fn, MachineFunction &mf) 127 : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) { 128 129 // Initialize the mapping of values to registers. This is only set up for 130 // instruction values that are used outside of the block that defines 131 // them. 132 for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end(); 133 AI != E; ++AI) 134 InitializeRegForValue(AI); 135 136 Function::iterator BB = Fn.begin(), E = Fn.end(); 137 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 138 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 139 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(AI->getArraySize())) { 140 const Type *Ty = AI->getAllocatedType(); 141 uint64_t TySize = TLI.getTargetData().getTypeSize(Ty); 142 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); 143 144 // If the alignment of the value is smaller than the size of the value, 145 // and if the size of the value is particularly small (<= 8 bytes), 146 // round up to the size of the value for potentially better performance. 147 // 148 // FIXME: This could be made better with a preferred alignment hook in 149 // TargetData. It serves primarily to 8-byte align doubles for X86. 150 if (Align < TySize && TySize <= 8) Align = TySize; 151 152 TySize *= CUI->getValue(); // Get total allocated size. 153 StaticAllocaMap[AI] = 154 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 155 } 156 157 for (; BB != E; ++BB) 158 for (BasicBlock::iterator I = BB->begin(), e = BB->end(); I != e; ++I) 159 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I)) 160 if (!isa<AllocaInst>(I) || 161 !StaticAllocaMap.count(cast<AllocaInst>(I))) 162 InitializeRegForValue(I); 163 164 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This 165 // also creates the initial PHI MachineInstrs, though none of the input 166 // operands are populated. 167 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 168 MachineBasicBlock *MBB = new MachineBasicBlock(BB); 169 MBBMap[BB] = MBB; 170 MF.getBasicBlockList().push_back(MBB); 171 172 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as 173 // appropriate. 174 PHINode *PN; 175 for (BasicBlock::iterator I = BB->begin(); 176 (PN = dyn_cast<PHINode>(I)); ++I) 177 if (!PN->use_empty()) { 178 unsigned NumElements = 179 TLI.getNumElements(TLI.getValueType(PN->getType())); 180 unsigned PHIReg = ValueMap[PN]; 181 assert(PHIReg &&"PHI node does not have an assigned virtual register!"); 182 for (unsigned i = 0; i != NumElements; ++i) 183 BuildMI(MBB, TargetInstrInfo::PHI, PN->getNumOperands(), PHIReg+i); 184 } 185 } 186} 187 188 189 190//===----------------------------------------------------------------------===// 191/// SelectionDAGLowering - This is the common target-independent lowering 192/// implementation that is parameterized by a TargetLowering object. 193/// Also, targets can overload any lowering method. 194/// 195namespace llvm { 196class SelectionDAGLowering { 197 MachineBasicBlock *CurMBB; 198 199 std::map<const Value*, SDOperand> NodeMap; 200 201 /// PendingLoads - Loads are not emitted to the program immediately. We bunch 202 /// them up and then emit token factor nodes when possible. This allows us to 203 /// get simple disambiguation between loads without worrying about alias 204 /// analysis. 205 std::vector<SDOperand> PendingLoads; 206 207public: 208 // TLI - This is information that describes the available target features we 209 // need for lowering. This indicates when operations are unavailable, 210 // implemented with a libcall, etc. 211 TargetLowering &TLI; 212 SelectionDAG &DAG; 213 const TargetData &TD; 214 215 /// FuncInfo - Information about the function as a whole. 216 /// 217 FunctionLoweringInfo &FuncInfo; 218 219 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli, 220 FunctionLoweringInfo &funcinfo) 221 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()), 222 FuncInfo(funcinfo) { 223 } 224 225 /// getRoot - Return the current virtual root of the Selection DAG. 226 /// 227 SDOperand getRoot() { 228 if (PendingLoads.empty()) 229 return DAG.getRoot(); 230 231 if (PendingLoads.size() == 1) { 232 SDOperand Root = PendingLoads[0]; 233 DAG.setRoot(Root); 234 PendingLoads.clear(); 235 return Root; 236 } 237 238 // Otherwise, we have to make a token factor node. 239 SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other, PendingLoads); 240 PendingLoads.clear(); 241 DAG.setRoot(Root); 242 return Root; 243 } 244 245 void visit(Instruction &I) { visit(I.getOpcode(), I); } 246 247 void visit(unsigned Opcode, User &I) { 248 switch (Opcode) { 249 default: assert(0 && "Unknown instruction type encountered!"); 250 abort(); 251 // Build the switch statement using the Instruction.def file. 252#define HANDLE_INST(NUM, OPCODE, CLASS) \ 253 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I); 254#include "llvm/Instruction.def" 255 } 256 } 257 258 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 259 260 261 SDOperand getIntPtrConstant(uint64_t Val) { 262 return DAG.getConstant(Val, TLI.getPointerTy()); 263 } 264 265 SDOperand getValue(const Value *V) { 266 SDOperand &N = NodeMap[V]; 267 if (N.Val) return N; 268 269 MVT::ValueType VT = TLI.getValueType(V->getType()); 270 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) 271 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 272 visit(CE->getOpcode(), *CE); 273 assert(N.Val && "visit didn't populate the ValueMap!"); 274 return N; 275 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) { 276 return N = DAG.getGlobalAddress(GV, VT); 277 } else if (isa<ConstantPointerNull>(C)) { 278 return N = DAG.getConstant(0, TLI.getPointerTy()); 279 } else if (isa<UndefValue>(C)) { 280 return N = DAG.getNode(ISD::UNDEF, VT); 281 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 282 return N = DAG.getConstantFP(CFP->getValue(), VT); 283 } else { 284 // Canonicalize all constant ints to be unsigned. 285 return N = DAG.getConstant(cast<ConstantIntegral>(C)->getRawValue(),VT); 286 } 287 288 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 289 std::map<const AllocaInst*, int>::iterator SI = 290 FuncInfo.StaticAllocaMap.find(AI); 291 if (SI != FuncInfo.StaticAllocaMap.end()) 292 return DAG.getFrameIndex(SI->second, TLI.getPointerTy()); 293 } 294 295 std::map<const Value*, unsigned>::const_iterator VMI = 296 FuncInfo.ValueMap.find(V); 297 assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!"); 298 299 unsigned InReg = VMI->second; 300 301 // If this type is not legal, make it so now. 302 MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT); 303 304 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT); 305 if (DestVT < VT) { 306 // Source must be expanded. This input value is actually coming from the 307 // register pair VMI->second and VMI->second+1. 308 N = DAG.getNode(ISD::BUILD_PAIR, VT, N, 309 DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT)); 310 } else { 311 if (DestVT > VT) { // Promotion case 312 if (MVT::isFloatingPoint(VT)) 313 N = DAG.getNode(ISD::FP_ROUND, VT, N); 314 else 315 N = DAG.getNode(ISD::TRUNCATE, VT, N); 316 } 317 } 318 319 return N; 320 } 321 322 const SDOperand &setValue(const Value *V, SDOperand NewN) { 323 SDOperand &N = NodeMap[V]; 324 assert(N.Val == 0 && "Already set a value for this node!"); 325 return N = NewN; 326 } 327 328 // Terminator instructions. 329 void visitRet(ReturnInst &I); 330 void visitBr(BranchInst &I); 331 void visitUnreachable(UnreachableInst &I) { /* noop */ } 332 333 // These all get lowered before this pass. 334 void visitSwitch(SwitchInst &I) { assert(0 && "TODO"); } 335 void visitInvoke(InvokeInst &I) { assert(0 && "TODO"); } 336 void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); } 337 338 // 339 void visitBinary(User &I, unsigned Opcode); 340 void visitAdd(User &I) { visitBinary(I, ISD::ADD); } 341 void visitSub(User &I); 342 void visitMul(User &I) { visitBinary(I, ISD::MUL); } 343 void visitDiv(User &I) { 344 visitBinary(I, I.getType()->isUnsigned() ? ISD::UDIV : ISD::SDIV); 345 } 346 void visitRem(User &I) { 347 visitBinary(I, I.getType()->isUnsigned() ? ISD::UREM : ISD::SREM); 348 } 349 void visitAnd(User &I) { visitBinary(I, ISD::AND); } 350 void visitOr (User &I) { visitBinary(I, ISD::OR); } 351 void visitXor(User &I) { visitBinary(I, ISD::XOR); } 352 void visitShl(User &I) { visitBinary(I, ISD::SHL); } 353 void visitShr(User &I) { 354 visitBinary(I, I.getType()->isUnsigned() ? ISD::SRL : ISD::SRA); 355 } 356 357 void visitSetCC(User &I, ISD::CondCode SignedOpc, ISD::CondCode UnsignedOpc); 358 void visitSetEQ(User &I) { visitSetCC(I, ISD::SETEQ, ISD::SETEQ); } 359 void visitSetNE(User &I) { visitSetCC(I, ISD::SETNE, ISD::SETNE); } 360 void visitSetLE(User &I) { visitSetCC(I, ISD::SETLE, ISD::SETULE); } 361 void visitSetGE(User &I) { visitSetCC(I, ISD::SETGE, ISD::SETUGE); } 362 void visitSetLT(User &I) { visitSetCC(I, ISD::SETLT, ISD::SETULT); } 363 void visitSetGT(User &I) { visitSetCC(I, ISD::SETGT, ISD::SETUGT); } 364 365 void visitGetElementPtr(User &I); 366 void visitCast(User &I); 367 void visitSelect(User &I); 368 // 369 370 void visitMalloc(MallocInst &I); 371 void visitFree(FreeInst &I); 372 void visitAlloca(AllocaInst &I); 373 void visitLoad(LoadInst &I); 374 void visitStore(StoreInst &I); 375 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 376 void visitCall(CallInst &I); 377 378 void visitVAStart(CallInst &I); 379 void visitVAArg(VAArgInst &I); 380 void visitVAEnd(CallInst &I); 381 void visitVACopy(CallInst &I); 382 void visitFrameReturnAddress(CallInst &I, bool isFrameAddress); 383 384 void visitMemIntrinsic(CallInst &I, unsigned Op); 385 386 void visitUserOp1(Instruction &I) { 387 assert(0 && "UserOp1 should not exist at instruction selection time!"); 388 abort(); 389 } 390 void visitUserOp2(Instruction &I) { 391 assert(0 && "UserOp2 should not exist at instruction selection time!"); 392 abort(); 393 } 394}; 395} // end namespace llvm 396 397void SelectionDAGLowering::visitRet(ReturnInst &I) { 398 if (I.getNumOperands() == 0) { 399 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot())); 400 return; 401 } 402 403 SDOperand Op1 = getValue(I.getOperand(0)); 404 MVT::ValueType TmpVT; 405 406 switch (Op1.getValueType()) { 407 default: assert(0 && "Unknown value type!"); 408 case MVT::i1: 409 case MVT::i8: 410 case MVT::i16: 411 case MVT::i32: 412 // If this is a machine where 32-bits is legal or expanded, promote to 413 // 32-bits, otherwise, promote to 64-bits. 414 if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote) 415 TmpVT = TLI.getTypeToTransformTo(MVT::i32); 416 else 417 TmpVT = MVT::i32; 418 419 // Extend integer types to result type. 420 if (I.getOperand(0)->getType()->isSigned()) 421 Op1 = DAG.getNode(ISD::SIGN_EXTEND, TmpVT, Op1); 422 else 423 Op1 = DAG.getNode(ISD::ZERO_EXTEND, TmpVT, Op1); 424 break; 425 case MVT::f32: 426 case MVT::i64: 427 case MVT::f64: 428 break; // No extension needed! 429 } 430 431 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot(), Op1)); 432} 433 434void SelectionDAGLowering::visitBr(BranchInst &I) { 435 // Update machine-CFG edges. 436 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)]; 437 438 // Figure out which block is immediately after the current one. 439 MachineBasicBlock *NextBlock = 0; 440 MachineFunction::iterator BBI = CurMBB; 441 if (++BBI != CurMBB->getParent()->end()) 442 NextBlock = BBI; 443 444 if (I.isUnconditional()) { 445 // If this is not a fall-through branch, emit the branch. 446 if (Succ0MBB != NextBlock) 447 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(), 448 DAG.getBasicBlock(Succ0MBB))); 449 } else { 450 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)]; 451 452 SDOperand Cond = getValue(I.getCondition()); 453 if (Succ1MBB == NextBlock) { 454 // If the condition is false, fall through. This means we should branch 455 // if the condition is true to Succ #0. 456 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), 457 Cond, DAG.getBasicBlock(Succ0MBB))); 458 } else if (Succ0MBB == NextBlock) { 459 // If the condition is true, fall through. This means we should branch if 460 // the condition is false to Succ #1. Invert the condition first. 461 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 462 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 463 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), 464 Cond, DAG.getBasicBlock(Succ1MBB))); 465 } else { 466 std::vector<SDOperand> Ops; 467 Ops.push_back(getRoot()); 468 Ops.push_back(Cond); 469 Ops.push_back(DAG.getBasicBlock(Succ0MBB)); 470 Ops.push_back(DAG.getBasicBlock(Succ1MBB)); 471 DAG.setRoot(DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops)); 472 } 473 } 474} 475 476void SelectionDAGLowering::visitSub(User &I) { 477 // -0.0 - X --> fneg 478 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0))) 479 if (CFP->isExactlyValue(-0.0)) { 480 SDOperand Op2 = getValue(I.getOperand(1)); 481 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2)); 482 return; 483 } 484 485 visitBinary(I, ISD::SUB); 486} 487 488void SelectionDAGLowering::visitBinary(User &I, unsigned Opcode) { 489 SDOperand Op1 = getValue(I.getOperand(0)); 490 SDOperand Op2 = getValue(I.getOperand(1)); 491 492 if (isa<ShiftInst>(I)) 493 Op2 = DAG.getNode(ISD::ZERO_EXTEND, TLI.getShiftAmountTy(), Op2); 494 495 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2)); 496} 497 498void SelectionDAGLowering::visitSetCC(User &I,ISD::CondCode SignedOpcode, 499 ISD::CondCode UnsignedOpcode) { 500 SDOperand Op1 = getValue(I.getOperand(0)); 501 SDOperand Op2 = getValue(I.getOperand(1)); 502 ISD::CondCode Opcode = SignedOpcode; 503 if (I.getOperand(0)->getType()->isUnsigned()) 504 Opcode = UnsignedOpcode; 505 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode)); 506} 507 508void SelectionDAGLowering::visitSelect(User &I) { 509 SDOperand Cond = getValue(I.getOperand(0)); 510 SDOperand TrueVal = getValue(I.getOperand(1)); 511 SDOperand FalseVal = getValue(I.getOperand(2)); 512 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond, 513 TrueVal, FalseVal)); 514} 515 516void SelectionDAGLowering::visitCast(User &I) { 517 SDOperand N = getValue(I.getOperand(0)); 518 MVT::ValueType SrcTy = TLI.getValueType(I.getOperand(0)->getType()); 519 MVT::ValueType DestTy = TLI.getValueType(I.getType()); 520 521 if (N.getValueType() == DestTy) { 522 setValue(&I, N); // noop cast. 523 } else if (DestTy == MVT::i1) { 524 // Cast to bool is a comparison against zero, not truncation to zero. 525 SDOperand Zero = isInteger(SrcTy) ? DAG.getConstant(0, N.getValueType()) : 526 DAG.getConstantFP(0.0, N.getValueType()); 527 setValue(&I, DAG.getSetCC(MVT::i1, N, Zero, ISD::SETNE)); 528 } else if (isInteger(SrcTy)) { 529 if (isInteger(DestTy)) { // Int -> Int cast 530 if (DestTy < SrcTy) // Truncating cast? 531 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestTy, N)); 532 else if (I.getOperand(0)->getType()->isSigned()) 533 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestTy, N)); 534 else 535 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestTy, N)); 536 } else { // Int -> FP cast 537 if (I.getOperand(0)->getType()->isSigned()) 538 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestTy, N)); 539 else 540 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestTy, N)); 541 } 542 } else { 543 assert(isFloatingPoint(SrcTy) && "Unknown value type!"); 544 if (isFloatingPoint(DestTy)) { // FP -> FP cast 545 if (DestTy < SrcTy) // Rounding cast? 546 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestTy, N)); 547 else 548 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestTy, N)); 549 } else { // FP -> Int cast. 550 if (I.getType()->isSigned()) 551 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestTy, N)); 552 else 553 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestTy, N)); 554 } 555 } 556} 557 558void SelectionDAGLowering::visitGetElementPtr(User &I) { 559 SDOperand N = getValue(I.getOperand(0)); 560 const Type *Ty = I.getOperand(0)->getType(); 561 const Type *UIntPtrTy = TD.getIntPtrType(); 562 563 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end(); 564 OI != E; ++OI) { 565 Value *Idx = *OI; 566 if (const StructType *StTy = dyn_cast<StructType> (Ty)) { 567 unsigned Field = cast<ConstantUInt>(Idx)->getValue(); 568 if (Field) { 569 // N = N + Offset 570 uint64_t Offset = TD.getStructLayout(StTy)->MemberOffsets[Field]; 571 N = DAG.getNode(ISD::ADD, N.getValueType(), N, 572 getIntPtrConstant(Offset)); 573 } 574 Ty = StTy->getElementType(Field); 575 } else { 576 Ty = cast<SequentialType>(Ty)->getElementType(); 577 if (!isa<Constant>(Idx) || !cast<Constant>(Idx)->isNullValue()) { 578 // N = N + Idx * ElementSize; 579 uint64_t ElementSize = TD.getTypeSize(Ty); 580 SDOperand IdxN = getValue(Idx), Scale = getIntPtrConstant(ElementSize); 581 582 // If the index is smaller or larger than intptr_t, truncate or extend 583 // it. 584 if (IdxN.getValueType() < Scale.getValueType()) { 585 if (Idx->getType()->isSigned()) 586 IdxN = DAG.getNode(ISD::SIGN_EXTEND, Scale.getValueType(), IdxN); 587 else 588 IdxN = DAG.getNode(ISD::ZERO_EXTEND, Scale.getValueType(), IdxN); 589 } else if (IdxN.getValueType() > Scale.getValueType()) 590 IdxN = DAG.getNode(ISD::TRUNCATE, Scale.getValueType(), IdxN); 591 592 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale); 593 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 594 } 595 } 596 } 597 setValue(&I, N); 598} 599 600void SelectionDAGLowering::visitAlloca(AllocaInst &I) { 601 // If this is a fixed sized alloca in the entry block of the function, 602 // allocate it statically on the stack. 603 if (FuncInfo.StaticAllocaMap.count(&I)) 604 return; // getValue will auto-populate this. 605 606 const Type *Ty = I.getAllocatedType(); 607 uint64_t TySize = TLI.getTargetData().getTypeSize(Ty); 608 unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); 609 610 SDOperand AllocSize = getValue(I.getArraySize()); 611 MVT::ValueType IntPtr = TLI.getPointerTy(); 612 if (IntPtr < AllocSize.getValueType()) 613 AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize); 614 else if (IntPtr > AllocSize.getValueType()) 615 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize); 616 617 AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize, 618 getIntPtrConstant(TySize)); 619 620 // Handle alignment. If the requested alignment is less than or equal to the 621 // stack alignment, ignore it and round the size of the allocation up to the 622 // stack alignment size. If the size is greater than the stack alignment, we 623 // note this in the DYNAMIC_STACKALLOC node. 624 unsigned StackAlign = 625 TLI.getTargetMachine().getFrameInfo()->getStackAlignment(); 626 if (Align <= StackAlign) { 627 Align = 0; 628 // Add SA-1 to the size. 629 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize, 630 getIntPtrConstant(StackAlign-1)); 631 // Mask out the low bits for alignment purposes. 632 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize, 633 getIntPtrConstant(~(uint64_t)(StackAlign-1))); 634 } 635 636 std::vector<MVT::ValueType> VTs; 637 VTs.push_back(AllocSize.getValueType()); 638 VTs.push_back(MVT::Other); 639 std::vector<SDOperand> Ops; 640 Ops.push_back(getRoot()); 641 Ops.push_back(AllocSize); 642 Ops.push_back(getIntPtrConstant(Align)); 643 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops); 644 DAG.setRoot(setValue(&I, DSA).getValue(1)); 645 646 // Inform the Frame Information that we have just allocated a variable-sized 647 // object. 648 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject(); 649} 650 651 652void SelectionDAGLowering::visitLoad(LoadInst &I) { 653 SDOperand Ptr = getValue(I.getOperand(0)); 654 655 SDOperand Root; 656 if (I.isVolatile()) 657 Root = getRoot(); 658 else { 659 // Do not serialize non-volatile loads against each other. 660 Root = DAG.getRoot(); 661 } 662 663 SDOperand L = DAG.getLoad(TLI.getValueType(I.getType()), Root, Ptr, 664 DAG.getSrcValue(I.getOperand(0))); 665 setValue(&I, L); 666 667 if (I.isVolatile()) 668 DAG.setRoot(L.getValue(1)); 669 else 670 PendingLoads.push_back(L.getValue(1)); 671} 672 673 674void SelectionDAGLowering::visitStore(StoreInst &I) { 675 Value *SrcV = I.getOperand(0); 676 SDOperand Src = getValue(SrcV); 677 SDOperand Ptr = getValue(I.getOperand(1)); 678 DAG.setRoot(DAG.getNode(ISD::STORE, MVT::Other, getRoot(), Src, Ptr, 679 DAG.getSrcValue(I.getOperand(1)))); 680} 681 682void SelectionDAGLowering::visitCall(CallInst &I) { 683 const char *RenameFn = 0; 684 SDOperand Tmp; 685 if (Function *F = I.getCalledFunction()) 686 if (F->isExternal()) 687 switch (F->getIntrinsicID()) { 688 case 0: // Not an LLVM intrinsic. 689 if (F->getName() == "fabs" || F->getName() == "fabsf") { 690 if (I.getNumOperands() == 2 && // Basic sanity checks. 691 I.getOperand(1)->getType()->isFloatingPoint() && 692 I.getType() == I.getOperand(1)->getType()) { 693 Tmp = getValue(I.getOperand(1)); 694 setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp)); 695 return; 696 } 697 } 698 else if (F->getName() == "sin" || F->getName() == "sinf") { 699 if (I.getNumOperands() == 2 && // Basic sanity checks. 700 I.getOperand(1)->getType()->isFloatingPoint() && 701 I.getType() == I.getOperand(1)->getType()) { 702 Tmp = getValue(I.getOperand(1)); 703 setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp)); 704 return; 705 } 706 } 707 else if (F->getName() == "cos" || F->getName() == "cosf") { 708 if (I.getNumOperands() == 2 && // Basic sanity checks. 709 I.getOperand(1)->getType()->isFloatingPoint() && 710 I.getType() == I.getOperand(1)->getType()) { 711 Tmp = getValue(I.getOperand(1)); 712 setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp)); 713 return; 714 } 715 } 716 break; 717 case Intrinsic::vastart: visitVAStart(I); return; 718 case Intrinsic::vaend: visitVAEnd(I); return; 719 case Intrinsic::vacopy: visitVACopy(I); return; 720 case Intrinsic::returnaddress: visitFrameReturnAddress(I, false); return; 721 case Intrinsic::frameaddress: visitFrameReturnAddress(I, true); return; 722 723 case Intrinsic::setjmp: RenameFn = "setjmp"; break; 724 case Intrinsic::longjmp: RenameFn = "longjmp"; break; 725 case Intrinsic::memcpy: visitMemIntrinsic(I, ISD::MEMCPY); return; 726 case Intrinsic::memset: visitMemIntrinsic(I, ISD::MEMSET); return; 727 case Intrinsic::memmove: visitMemIntrinsic(I, ISD::MEMMOVE); return; 728 729 case Intrinsic::readport: 730 case Intrinsic::readio: { 731 std::vector<MVT::ValueType> VTs; 732 VTs.push_back(TLI.getValueType(I.getType())); 733 VTs.push_back(MVT::Other); 734 std::vector<SDOperand> Ops; 735 Ops.push_back(getRoot()); 736 Ops.push_back(getValue(I.getOperand(1))); 737 Tmp = DAG.getNode(F->getIntrinsicID() == Intrinsic::readport ? 738 ISD::READPORT : ISD::READIO, VTs, Ops); 739 740 setValue(&I, Tmp); 741 DAG.setRoot(Tmp.getValue(1)); 742 return; 743 } 744 case Intrinsic::writeport: 745 case Intrinsic::writeio: 746 DAG.setRoot(DAG.getNode(F->getIntrinsicID() == Intrinsic::writeport ? 747 ISD::WRITEPORT : ISD::WRITEIO, MVT::Other, 748 getRoot(), getValue(I.getOperand(1)), 749 getValue(I.getOperand(2)))); 750 return; 751 case Intrinsic::dbg_stoppoint: 752 case Intrinsic::dbg_region_start: 753 case Intrinsic::dbg_region_end: 754 case Intrinsic::dbg_func_start: 755 case Intrinsic::dbg_declare: 756 if (I.getType() != Type::VoidTy) 757 setValue(&I, DAG.getNode(ISD::UNDEF, TLI.getValueType(I.getType()))); 758 return; 759 760 case Intrinsic::isunordered: 761 setValue(&I, DAG.getSetCC(MVT::i1,getValue(I.getOperand(1)), 762 getValue(I.getOperand(2)), ISD::SETUO)); 763 return; 764 765 case Intrinsic::sqrt: 766 setValue(&I, DAG.getNode(ISD::FSQRT, 767 getValue(I.getOperand(1)).getValueType(), 768 getValue(I.getOperand(1)))); 769 return; 770 771 case Intrinsic::pcmarker: 772 Tmp = getValue(I.getOperand(1)); 773 DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp)); 774 return; 775 case Intrinsic::cttz: 776 setValue(&I, DAG.getNode(ISD::CTTZ, 777 getValue(I.getOperand(1)).getValueType(), 778 getValue(I.getOperand(1)))); 779 return; 780 case Intrinsic::ctlz: 781 setValue(&I, DAG.getNode(ISD::CTLZ, 782 getValue(I.getOperand(1)).getValueType(), 783 getValue(I.getOperand(1)))); 784 return; 785 case Intrinsic::ctpop: 786 setValue(&I, DAG.getNode(ISD::CTPOP, 787 getValue(I.getOperand(1)).getValueType(), 788 getValue(I.getOperand(1)))); 789 return; 790 default: 791 std::cerr << I; 792 assert(0 && "This intrinsic is not implemented yet!"); 793 return; 794 } 795 796 SDOperand Callee; 797 if (!RenameFn) 798 Callee = getValue(I.getOperand(0)); 799 else 800 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy()); 801 std::vector<std::pair<SDOperand, const Type*> > Args; 802 803 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 804 Value *Arg = I.getOperand(i); 805 SDOperand ArgNode = getValue(Arg); 806 Args.push_back(std::make_pair(ArgNode, Arg->getType())); 807 } 808 809 const PointerType *PT = cast<PointerType>(I.getCalledValue()->getType()); 810 const FunctionType *FTy = cast<FunctionType>(PT->getElementType()); 811 812 std::pair<SDOperand,SDOperand> Result = 813 TLI.LowerCallTo(getRoot(), I.getType(), FTy->isVarArg(), I.getCallingConv(), 814 I.isTailCall(), Callee, Args, DAG); 815 if (I.getType() != Type::VoidTy) 816 setValue(&I, Result.first); 817 DAG.setRoot(Result.second); 818} 819 820void SelectionDAGLowering::visitMalloc(MallocInst &I) { 821 SDOperand Src = getValue(I.getOperand(0)); 822 823 MVT::ValueType IntPtr = TLI.getPointerTy(); 824 825 if (IntPtr < Src.getValueType()) 826 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src); 827 else if (IntPtr > Src.getValueType()) 828 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src); 829 830 // Scale the source by the type size. 831 uint64_t ElementSize = TD.getTypeSize(I.getType()->getElementType()); 832 Src = DAG.getNode(ISD::MUL, Src.getValueType(), 833 Src, getIntPtrConstant(ElementSize)); 834 835 std::vector<std::pair<SDOperand, const Type*> > Args; 836 Args.push_back(std::make_pair(Src, TLI.getTargetData().getIntPtrType())); 837 838 std::pair<SDOperand,SDOperand> Result = 839 TLI.LowerCallTo(getRoot(), I.getType(), false, CallingConv::C, true, 840 DAG.getExternalSymbol("malloc", IntPtr), 841 Args, DAG); 842 setValue(&I, Result.first); // Pointers always fit in registers 843 DAG.setRoot(Result.second); 844} 845 846void SelectionDAGLowering::visitFree(FreeInst &I) { 847 std::vector<std::pair<SDOperand, const Type*> > Args; 848 Args.push_back(std::make_pair(getValue(I.getOperand(0)), 849 TLI.getTargetData().getIntPtrType())); 850 MVT::ValueType IntPtr = TLI.getPointerTy(); 851 std::pair<SDOperand,SDOperand> Result = 852 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, CallingConv::C, true, 853 DAG.getExternalSymbol("free", IntPtr), Args, DAG); 854 DAG.setRoot(Result.second); 855} 856 857SDOperand TargetLowering::LowerVAStart(SDOperand Chain, 858 SDOperand VAListP, Value *VAListV, 859 SelectionDAG &DAG) { 860 // We have no sane default behavior, just emit a useful error message and bail 861 // out. 862 std::cerr << "Variable arguments handling not implemented on this target!\n"; 863 abort(); 864 return SDOperand(); 865} 866 867SDOperand TargetLowering::LowerVAEnd(SDOperand Chain, SDOperand LP, Value *LV, 868 SelectionDAG &DAG) { 869 // Default to a noop. 870 return Chain; 871} 872 873SDOperand TargetLowering::LowerVACopy(SDOperand Chain, 874 SDOperand SrcP, Value *SrcV, 875 SDOperand DestP, Value *DestV, 876 SelectionDAG &DAG) { 877 // Default to copying the input list. 878 SDOperand Val = DAG.getLoad(getPointerTy(), Chain, 879 SrcP, DAG.getSrcValue(SrcV)); 880 SDOperand Result = DAG.getNode(ISD::STORE, MVT::Other, Val.getValue(1), 881 Val, DestP, DAG.getSrcValue(DestV)); 882 return Result; 883} 884 885std::pair<SDOperand,SDOperand> 886TargetLowering::LowerVAArg(SDOperand Chain, SDOperand VAListP, Value *VAListV, 887 const Type *ArgTy, SelectionDAG &DAG) { 888 // We have no sane default behavior, just emit a useful error message and bail 889 // out. 890 std::cerr << "Variable arguments handling not implemented on this target!\n"; 891 abort(); 892 return std::make_pair(SDOperand(), SDOperand()); 893} 894 895 896void SelectionDAGLowering::visitVAStart(CallInst &I) { 897 DAG.setRoot(TLI.LowerVAStart(getRoot(), getValue(I.getOperand(1)), 898 I.getOperand(1), DAG)); 899} 900 901void SelectionDAGLowering::visitVAArg(VAArgInst &I) { 902 std::pair<SDOperand,SDOperand> Result = 903 TLI.LowerVAArg(getRoot(), getValue(I.getOperand(0)), I.getOperand(0), 904 I.getType(), DAG); 905 setValue(&I, Result.first); 906 DAG.setRoot(Result.second); 907} 908 909void SelectionDAGLowering::visitVAEnd(CallInst &I) { 910 DAG.setRoot(TLI.LowerVAEnd(getRoot(), getValue(I.getOperand(1)), 911 I.getOperand(1), DAG)); 912} 913 914void SelectionDAGLowering::visitVACopy(CallInst &I) { 915 SDOperand Result = 916 TLI.LowerVACopy(getRoot(), getValue(I.getOperand(2)), I.getOperand(2), 917 getValue(I.getOperand(1)), I.getOperand(1), DAG); 918 DAG.setRoot(Result); 919} 920 921 922// It is always conservatively correct for llvm.returnaddress and 923// llvm.frameaddress to return 0. 924std::pair<SDOperand, SDOperand> 925TargetLowering::LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, 926 unsigned Depth, SelectionDAG &DAG) { 927 return std::make_pair(DAG.getConstant(0, getPointerTy()), Chain); 928} 929 930SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) { 931 assert(0 && "LowerOperation not implemented for this target!"); 932 abort(); 933 return SDOperand(); 934} 935 936void SelectionDAGLowering::visitFrameReturnAddress(CallInst &I, bool isFrame) { 937 unsigned Depth = (unsigned)cast<ConstantUInt>(I.getOperand(1))->getValue(); 938 std::pair<SDOperand,SDOperand> Result = 939 TLI.LowerFrameReturnAddress(isFrame, getRoot(), Depth, DAG); 940 setValue(&I, Result.first); 941 DAG.setRoot(Result.second); 942} 943 944void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) { 945 std::vector<SDOperand> Ops; 946 Ops.push_back(getRoot()); 947 Ops.push_back(getValue(I.getOperand(1))); 948 Ops.push_back(getValue(I.getOperand(2))); 949 Ops.push_back(getValue(I.getOperand(3))); 950 Ops.push_back(getValue(I.getOperand(4))); 951 DAG.setRoot(DAG.getNode(Op, MVT::Other, Ops)); 952} 953 954//===----------------------------------------------------------------------===// 955// SelectionDAGISel code 956//===----------------------------------------------------------------------===// 957 958unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) { 959 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 960} 961 962 963 964bool SelectionDAGISel::runOnFunction(Function &Fn) { 965 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine()); 966 RegMap = MF.getSSARegMap(); 967 DEBUG(std::cerr << "\n\n\n=== " << Fn.getName() << "\n"); 968 969 FunctionLoweringInfo FuncInfo(TLI, Fn, MF); 970 971 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 972 SelectBasicBlock(I, MF, FuncInfo); 973 974 return true; 975} 976 977 978SDOperand SelectionDAGISel:: 979CopyValueToVirtualRegister(SelectionDAGLowering &SDL, Value *V, unsigned Reg) { 980 SDOperand Op = SDL.getValue(V); 981 assert((Op.getOpcode() != ISD::CopyFromReg || 982 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) && 983 "Copy from a reg to the same reg!"); 984 985 // If this type is not legal, we must make sure to not create an invalid 986 // register use. 987 MVT::ValueType SrcVT = Op.getValueType(); 988 MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT); 989 SelectionDAG &DAG = SDL.DAG; 990 if (SrcVT == DestVT) { 991 return DAG.getCopyToReg(SDL.getRoot(), Reg, Op); 992 } else if (SrcVT < DestVT) { 993 // The src value is promoted to the register. 994 Op = DAG.getNode(ISD::ZERO_EXTEND, DestVT, Op); 995 return DAG.getCopyToReg(SDL.getRoot(), Reg, Op); 996 } else { 997 // The src value is expanded into multiple registers. 998 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT, 999 Op, DAG.getConstant(0, MVT::i32)); 1000 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT, 1001 Op, DAG.getConstant(1, MVT::i32)); 1002 Op = DAG.getCopyToReg(SDL.getRoot(), Reg, Lo); 1003 return DAG.getCopyToReg(Op, Reg+1, Hi); 1004 } 1005} 1006 1007/// IsOnlyUsedInOneBasicBlock - If the specified argument is only used in a 1008/// single basic block, return that block. Otherwise, return a null pointer. 1009static BasicBlock *IsOnlyUsedInOneBasicBlock(Argument *A) { 1010 if (A->use_empty()) return 0; 1011 BasicBlock *BB = cast<Instruction>(A->use_back())->getParent(); 1012 for (Argument::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; 1013 ++UI) 1014 if (isa<PHINode>(*UI) || cast<Instruction>(*UI)->getParent() != BB) 1015 return 0; // Disagreement among the users? 1016 1017 // Okay, there is a single BB user. Only permit this optimization if this is 1018 // the entry block, otherwise, we might sink argument loads into loops and 1019 // stuff. Later, when we have global instruction selection, this won't be an 1020 // issue clearly. 1021 if (BB == BB->getParent()->begin()) 1022 return BB; 1023 return 0; 1024} 1025 1026void SelectionDAGISel:: 1027LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL, 1028 std::vector<SDOperand> &UnorderedChains) { 1029 // If this is the entry block, emit arguments. 1030 Function &F = *BB->getParent(); 1031 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo; 1032 1033 if (BB == &F.front()) { 1034 SDOperand OldRoot = SDL.DAG.getRoot(); 1035 1036 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG); 1037 1038 // If there were side effects accessing the argument list, do not do 1039 // anything special. 1040 if (OldRoot != SDL.DAG.getRoot()) { 1041 unsigned a = 0; 1042 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 1043 AI != E; ++AI,++a) 1044 if (!AI->use_empty()) { 1045 SDL.setValue(AI, Args[a]); 1046 SDOperand Copy = 1047 CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]); 1048 UnorderedChains.push_back(Copy); 1049 } 1050 } else { 1051 // Otherwise, if any argument is only accessed in a single basic block, 1052 // emit that argument only to that basic block. 1053 unsigned a = 0; 1054 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 1055 AI != E; ++AI,++a) 1056 if (!AI->use_empty()) { 1057 if (BasicBlock *BBU = IsOnlyUsedInOneBasicBlock(AI)) { 1058 FuncInfo.BlockLocalArguments.insert(std::make_pair(BBU, 1059 std::make_pair(AI, a))); 1060 } else { 1061 SDL.setValue(AI, Args[a]); 1062 SDOperand Copy = 1063 CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]); 1064 UnorderedChains.push_back(Copy); 1065 } 1066 } 1067 } 1068 1069 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction()); 1070 } 1071 1072 // See if there are any block-local arguments that need to be emitted in this 1073 // block. 1074 1075 if (!FuncInfo.BlockLocalArguments.empty()) { 1076 std::multimap<BasicBlock*, std::pair<Argument*, unsigned> >::iterator BLAI = 1077 FuncInfo.BlockLocalArguments.lower_bound(BB); 1078 if (BLAI != FuncInfo.BlockLocalArguments.end() && BLAI->first == BB) { 1079 // Lower the arguments into this block. 1080 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG); 1081 1082 // Set up the value mapping for the local arguments. 1083 for (; BLAI != FuncInfo.BlockLocalArguments.end() && BLAI->first == BB; 1084 ++BLAI) 1085 SDL.setValue(BLAI->second.first, Args[BLAI->second.second]); 1086 1087 // Any dead arguments will just be ignored here. 1088 } 1089 } 1090} 1091 1092 1093void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, 1094 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate, 1095 FunctionLoweringInfo &FuncInfo) { 1096 SelectionDAGLowering SDL(DAG, TLI, FuncInfo); 1097 1098 std::vector<SDOperand> UnorderedChains; 1099 1100 // Lower any arguments needed in this block. 1101 LowerArguments(LLVMBB, SDL, UnorderedChains); 1102 1103 BB = FuncInfo.MBBMap[LLVMBB]; 1104 SDL.setCurrentBasicBlock(BB); 1105 1106 // Lower all of the non-terminator instructions. 1107 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end(); 1108 I != E; ++I) 1109 SDL.visit(*I); 1110 1111 // Ensure that all instructions which are used outside of their defining 1112 // blocks are available as virtual registers. 1113 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I) 1114 if (!I->use_empty() && !isa<PHINode>(I)) { 1115 std::map<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I); 1116 if (VMI != FuncInfo.ValueMap.end()) 1117 UnorderedChains.push_back( 1118 CopyValueToVirtualRegister(SDL, I, VMI->second)); 1119 } 1120 1121 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to 1122 // ensure constants are generated when needed. Remember the virtual registers 1123 // that need to be added to the Machine PHI nodes as input. We cannot just 1124 // directly add them, because expansion might result in multiple MBB's for one 1125 // BB. As such, the start of the BB might correspond to a different MBB than 1126 // the end. 1127 // 1128 1129 // Emit constants only once even if used by multiple PHI nodes. 1130 std::map<Constant*, unsigned> ConstantsOut; 1131 1132 // Check successor nodes PHI nodes that expect a constant to be available from 1133 // this block. 1134 TerminatorInst *TI = LLVMBB->getTerminator(); 1135 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 1136 BasicBlock *SuccBB = TI->getSuccessor(succ); 1137 MachineBasicBlock::iterator MBBI = FuncInfo.MBBMap[SuccBB]->begin(); 1138 PHINode *PN; 1139 1140 // At this point we know that there is a 1-1 correspondence between LLVM PHI 1141 // nodes and Machine PHI nodes, but the incoming operands have not been 1142 // emitted yet. 1143 for (BasicBlock::iterator I = SuccBB->begin(); 1144 (PN = dyn_cast<PHINode>(I)); ++I) 1145 if (!PN->use_empty()) { 1146 unsigned Reg; 1147 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 1148 if (Constant *C = dyn_cast<Constant>(PHIOp)) { 1149 unsigned &RegOut = ConstantsOut[C]; 1150 if (RegOut == 0) { 1151 RegOut = FuncInfo.CreateRegForValue(C); 1152 UnorderedChains.push_back( 1153 CopyValueToVirtualRegister(SDL, C, RegOut)); 1154 } 1155 Reg = RegOut; 1156 } else { 1157 Reg = FuncInfo.ValueMap[PHIOp]; 1158 if (Reg == 0) { 1159 assert(isa<AllocaInst>(PHIOp) && 1160 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) && 1161 "Didn't codegen value into a register!??"); 1162 Reg = FuncInfo.CreateRegForValue(PHIOp); 1163 UnorderedChains.push_back( 1164 CopyValueToVirtualRegister(SDL, PHIOp, Reg)); 1165 } 1166 } 1167 1168 // Remember that this register needs to added to the machine PHI node as 1169 // the input for this MBB. 1170 unsigned NumElements = 1171 TLI.getNumElements(TLI.getValueType(PN->getType())); 1172 for (unsigned i = 0, e = NumElements; i != e; ++i) 1173 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); 1174 } 1175 } 1176 ConstantsOut.clear(); 1177 1178 // Turn all of the unordered chains into one factored node. 1179 if (!UnorderedChains.empty()) { 1180 UnorderedChains.push_back(SDL.getRoot()); 1181 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, UnorderedChains)); 1182 } 1183 1184 // Lower the terminator after the copies are emitted. 1185 SDL.visit(*LLVMBB->getTerminator()); 1186 1187 // Make sure the root of the DAG is up-to-date. 1188 DAG.setRoot(SDL.getRoot()); 1189} 1190 1191void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, 1192 FunctionLoweringInfo &FuncInfo) { 1193 SelectionDAG DAG(TLI, MF); 1194 CurDAG = &DAG; 1195 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 1196 1197 // First step, lower LLVM code to some DAG. This DAG may use operations and 1198 // types that are not supported by the target. 1199 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo); 1200 1201 DEBUG(std::cerr << "Lowered selection DAG:\n"); 1202 DEBUG(DAG.dump()); 1203 1204 // Second step, hack on the DAG until it only uses operations and types that 1205 // the target supports. 1206 DAG.Legalize(); 1207 1208 DEBUG(std::cerr << "Legalized selection DAG:\n"); 1209 DEBUG(DAG.dump()); 1210 1211 // Third, instruction select all of the operations to machine code, adding the 1212 // code to the MachineBasicBlock. 1213 InstructionSelectBasicBlock(DAG); 1214 1215 if (ViewDAGs) DAG.viewGraph(); 1216 1217 DEBUG(std::cerr << "Selected machine code:\n"); 1218 DEBUG(BB->dump()); 1219 1220 // Next, now that we know what the last MBB the LLVM BB expanded is, update 1221 // PHI nodes in successors. 1222 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 1223 MachineInstr *PHI = PHINodesToUpdate[i].first; 1224 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 1225 "This is not a machine PHI node that we are updating!"); 1226 PHI->addRegOperand(PHINodesToUpdate[i].second); 1227 PHI->addMachineBasicBlockOperand(BB); 1228 } 1229 1230 // Finally, add the CFG edges from the last selected MBB to the successor 1231 // MBBs. 1232 TerminatorInst *TI = LLVMBB->getTerminator(); 1233 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 1234 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[TI->getSuccessor(i)]; 1235 BB->addSuccessor(Succ0MBB); 1236 } 1237} 1238