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