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