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