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