blob: 01e76c1b42394d7c558db52116974f662902b257 [file] [log] [blame]
Chris Lattner7a60d912005-01-07 07:47:53 +00001//===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
Misha Brukman835702a2005-04-21 22:36:52 +00002//
Chris Lattner7a60d912005-01-07 07:47:53 +00003// 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 Brukman835702a2005-04-21 22:36:52 +00007//
Chris Lattner7a60d912005-01-07 07:47:53 +00008//===----------------------------------------------------------------------===//
9//
10// This implements the SelectionDAGISel class.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "isel"
15#include "llvm/CodeGen/SelectionDAGISel.h"
Chris Lattner2e77db62005-05-13 18:50:42 +000016#include "llvm/CallingConv.h"
Chris Lattner7a60d912005-01-07 07:47:53 +000017#include "llvm/Constants.h"
18#include "llvm/DerivedTypes.h"
19#include "llvm/Function.h"
20#include "llvm/Instructions.h"
21#include "llvm/Intrinsics.h"
22#include "llvm/CodeGen/MachineFunction.h"
23#include "llvm/CodeGen/MachineFrameInfo.h"
24#include "llvm/CodeGen/MachineInstrBuilder.h"
25#include "llvm/CodeGen/SelectionDAG.h"
26#include "llvm/CodeGen/SSARegMap.h"
Chris Lattnerd4382f02005-09-13 19:30:54 +000027#include "llvm/Target/MRegisterInfo.h"
Chris Lattner7a60d912005-01-07 07:47:53 +000028#include "llvm/Target/TargetData.h"
29#include "llvm/Target/TargetFrameInfo.h"
30#include "llvm/Target/TargetInstrInfo.h"
31#include "llvm/Target/TargetLowering.h"
32#include "llvm/Target/TargetMachine.h"
Chris Lattnerc9950c12005-08-17 06:37:43 +000033#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Chris Lattnere05a4612005-01-12 03:41:21 +000034#include "llvm/Support/CommandLine.h"
Chris Lattner43535a12005-11-09 04:45:33 +000035#include "llvm/Support/MathExtras.h"
Chris Lattner7a60d912005-01-07 07:47:53 +000036#include "llvm/Support/Debug.h"
37#include <map>
38#include <iostream>
39using namespace llvm;
40
Chris Lattner975f5c92005-09-01 18:44:10 +000041#ifndef NDEBUG
Chris Lattnere05a4612005-01-12 03:41:21 +000042static cl::opt<bool>
43ViewDAGs("view-isel-dags", cl::Hidden,
44 cl::desc("Pop up a window to show isel dags as they are selected"));
45#else
Chris Lattnerb6cde172005-09-02 07:09:28 +000046static const bool ViewDAGs = 0;
Chris Lattnere05a4612005-01-12 03:41:21 +000047#endif
48
Chris Lattner7a60d912005-01-07 07:47:53 +000049namespace llvm {
50 //===--------------------------------------------------------------------===//
51 /// FunctionLoweringInfo - This contains information that is global to a
52 /// function that is used when lowering a region of the function.
Chris Lattnerd0061952005-01-08 19:52:31 +000053 class FunctionLoweringInfo {
54 public:
Chris Lattner7a60d912005-01-07 07:47:53 +000055 TargetLowering &TLI;
56 Function &Fn;
57 MachineFunction &MF;
58 SSARegMap *RegMap;
59
60 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF);
61
62 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry.
63 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap;
64
65 /// ValueMap - Since we emit code for the function a basic block at a time,
66 /// we must remember which virtual registers hold the values for
67 /// cross-basic-block values.
68 std::map<const Value*, unsigned> ValueMap;
69
70 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in
71 /// the entry block. This allows the allocas to be efficiently referenced
72 /// anywhere in the function.
73 std::map<const AllocaInst*, int> StaticAllocaMap;
74
75 unsigned MakeReg(MVT::ValueType VT) {
76 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
77 }
Misha Brukman835702a2005-04-21 22:36:52 +000078
Chris Lattner7a60d912005-01-07 07:47:53 +000079 unsigned CreateRegForValue(const Value *V) {
80 MVT::ValueType VT = TLI.getValueType(V->getType());
81 // The common case is that we will only create one register for this
82 // value. If we have that case, create and return the virtual register.
83 unsigned NV = TLI.getNumElements(VT);
Chris Lattnera8d34fb2005-01-16 00:37:38 +000084 if (NV == 1) {
85 // If we are promoting this value, pick the next largest supported type.
Chris Lattnerd58384f2005-01-16 01:11:19 +000086 return MakeReg(TLI.getTypeToTransformTo(VT));
Chris Lattnera8d34fb2005-01-16 00:37:38 +000087 }
Misha Brukman835702a2005-04-21 22:36:52 +000088
Chris Lattner7a60d912005-01-07 07:47:53 +000089 // If this value is represented with multiple target registers, make sure
90 // to create enough consequtive registers of the right (smaller) type.
91 unsigned NT = VT-1; // Find the type to use.
92 while (TLI.getNumElements((MVT::ValueType)NT) != 1)
93 --NT;
Misha Brukman835702a2005-04-21 22:36:52 +000094
Chris Lattner7a60d912005-01-07 07:47:53 +000095 unsigned R = MakeReg((MVT::ValueType)NT);
96 for (unsigned i = 1; i != NV; ++i)
97 MakeReg((MVT::ValueType)NT);
98 return R;
99 }
Misha Brukman835702a2005-04-21 22:36:52 +0000100
Chris Lattner7a60d912005-01-07 07:47:53 +0000101 unsigned InitializeRegForValue(const Value *V) {
102 unsigned &R = ValueMap[V];
103 assert(R == 0 && "Already initialized this value register!");
104 return R = CreateRegForValue(V);
105 }
106 };
107}
108
109/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
110/// PHI nodes or outside of the basic block that defines it.
111static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
112 if (isa<PHINode>(I)) return true;
113 BasicBlock *BB = I->getParent();
114 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
115 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI))
116 return true;
117 return false;
118}
119
Chris Lattner6871b232005-10-30 19:42:35 +0000120/// isOnlyUsedInEntryBlock - If the specified argument is only used in the
121/// entry block, return true.
122static bool isOnlyUsedInEntryBlock(Argument *A) {
123 BasicBlock *Entry = A->getParent()->begin();
124 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI)
125 if (cast<Instruction>(*UI)->getParent() != Entry)
126 return false; // Use not in entry block.
127 return true;
128}
129
Chris Lattner7a60d912005-01-07 07:47:53 +0000130FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli,
Misha Brukman835702a2005-04-21 22:36:52 +0000131 Function &fn, MachineFunction &mf)
Chris Lattner7a60d912005-01-07 07:47:53 +0000132 : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) {
133
Chris Lattner6871b232005-10-30 19:42:35 +0000134 // Create a vreg for each argument register that is not dead and is used
135 // outside of the entry block for the function.
136 for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end();
137 AI != E; ++AI)
138 if (!isOnlyUsedInEntryBlock(AI))
139 InitializeRegForValue(AI);
140
Chris Lattner7a60d912005-01-07 07:47:53 +0000141 // Initialize the mapping of values to registers. This is only set up for
142 // instruction values that are used outside of the block that defines
143 // them.
Jeff Cohenf8a5e5ae2005-10-01 03:57:14 +0000144 Function::iterator BB = Fn.begin(), EB = Fn.end();
Chris Lattner7a60d912005-01-07 07:47:53 +0000145 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
146 if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
147 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(AI->getArraySize())) {
148 const Type *Ty = AI->getAllocatedType();
149 uint64_t TySize = TLI.getTargetData().getTypeSize(Ty);
Nate Begeman3ee3e692005-11-06 09:00:38 +0000150 unsigned Align =
151 std::max((unsigned)TLI.getTargetData().getTypeAlignment(Ty),
152 AI->getAlignment());
Chris Lattnercbefe722005-05-13 23:14:17 +0000153
154 // If the alignment of the value is smaller than the size of the value,
155 // and if the size of the value is particularly small (<= 8 bytes),
156 // round up to the size of the value for potentially better performance.
157 //
158 // FIXME: This could be made better with a preferred alignment hook in
159 // TargetData. It serves primarily to 8-byte align doubles for X86.
160 if (Align < TySize && TySize <= 8) Align = TySize;
Chris Lattner8396a302005-10-18 22:11:42 +0000161 TySize *= CUI->getValue(); // Get total allocated size.
Chris Lattner0a71a9a2005-10-18 22:14:06 +0000162 if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
Chris Lattner7a60d912005-01-07 07:47:53 +0000163 StaticAllocaMap[AI] =
Chris Lattnerd0061952005-01-08 19:52:31 +0000164 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
Chris Lattner7a60d912005-01-07 07:47:53 +0000165 }
166
Jeff Cohenf8a5e5ae2005-10-01 03:57:14 +0000167 for (; BB != EB; ++BB)
168 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
Chris Lattner7a60d912005-01-07 07:47:53 +0000169 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
170 if (!isa<AllocaInst>(I) ||
171 !StaticAllocaMap.count(cast<AllocaInst>(I)))
172 InitializeRegForValue(I);
173
174 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This
175 // also creates the initial PHI MachineInstrs, though none of the input
176 // operands are populated.
Jeff Cohenf8a5e5ae2005-10-01 03:57:14 +0000177 for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) {
Chris Lattner7a60d912005-01-07 07:47:53 +0000178 MachineBasicBlock *MBB = new MachineBasicBlock(BB);
179 MBBMap[BB] = MBB;
180 MF.getBasicBlockList().push_back(MBB);
181
182 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
183 // appropriate.
184 PHINode *PN;
185 for (BasicBlock::iterator I = BB->begin();
Chris Lattner8ea875f2005-01-07 21:34:19 +0000186 (PN = dyn_cast<PHINode>(I)); ++I)
187 if (!PN->use_empty()) {
188 unsigned NumElements =
189 TLI.getNumElements(TLI.getValueType(PN->getType()));
190 unsigned PHIReg = ValueMap[PN];
191 assert(PHIReg &&"PHI node does not have an assigned virtual register!");
192 for (unsigned i = 0; i != NumElements; ++i)
193 BuildMI(MBB, TargetInstrInfo::PHI, PN->getNumOperands(), PHIReg+i);
194 }
Chris Lattner7a60d912005-01-07 07:47:53 +0000195 }
196}
197
198
199
200//===----------------------------------------------------------------------===//
201/// SelectionDAGLowering - This is the common target-independent lowering
202/// implementation that is parameterized by a TargetLowering object.
203/// Also, targets can overload any lowering method.
204///
205namespace llvm {
206class SelectionDAGLowering {
207 MachineBasicBlock *CurMBB;
208
209 std::map<const Value*, SDOperand> NodeMap;
210
Chris Lattner4d9651c2005-01-17 22:19:26 +0000211 /// PendingLoads - Loads are not emitted to the program immediately. We bunch
212 /// them up and then emit token factor nodes when possible. This allows us to
213 /// get simple disambiguation between loads without worrying about alias
214 /// analysis.
215 std::vector<SDOperand> PendingLoads;
216
Chris Lattner7a60d912005-01-07 07:47:53 +0000217public:
218 // TLI - This is information that describes the available target features we
219 // need for lowering. This indicates when operations are unavailable,
220 // implemented with a libcall, etc.
221 TargetLowering &TLI;
222 SelectionDAG &DAG;
223 const TargetData &TD;
224
225 /// FuncInfo - Information about the function as a whole.
226 ///
227 FunctionLoweringInfo &FuncInfo;
228
229 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
Misha Brukman835702a2005-04-21 22:36:52 +0000230 FunctionLoweringInfo &funcinfo)
Chris Lattner7a60d912005-01-07 07:47:53 +0000231 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
232 FuncInfo(funcinfo) {
233 }
234
Chris Lattner4108bb02005-01-17 19:43:36 +0000235 /// getRoot - Return the current virtual root of the Selection DAG.
236 ///
237 SDOperand getRoot() {
Chris Lattner4d9651c2005-01-17 22:19:26 +0000238 if (PendingLoads.empty())
239 return DAG.getRoot();
Misha Brukman835702a2005-04-21 22:36:52 +0000240
Chris Lattner4d9651c2005-01-17 22:19:26 +0000241 if (PendingLoads.size() == 1) {
242 SDOperand Root = PendingLoads[0];
243 DAG.setRoot(Root);
244 PendingLoads.clear();
245 return Root;
246 }
247
248 // Otherwise, we have to make a token factor node.
249 SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other, PendingLoads);
250 PendingLoads.clear();
251 DAG.setRoot(Root);
252 return Root;
Chris Lattner4108bb02005-01-17 19:43:36 +0000253 }
254
Chris Lattner7a60d912005-01-07 07:47:53 +0000255 void visit(Instruction &I) { visit(I.getOpcode(), I); }
256
257 void visit(unsigned Opcode, User &I) {
258 switch (Opcode) {
259 default: assert(0 && "Unknown instruction type encountered!");
260 abort();
261 // Build the switch statement using the Instruction.def file.
262#define HANDLE_INST(NUM, OPCODE, CLASS) \
263 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I);
264#include "llvm/Instruction.def"
265 }
266 }
267
268 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; }
269
270
271 SDOperand getIntPtrConstant(uint64_t Val) {
272 return DAG.getConstant(Val, TLI.getPointerTy());
273 }
274
275 SDOperand getValue(const Value *V) {
276 SDOperand &N = NodeMap[V];
277 if (N.Val) return N;
278
279 MVT::ValueType VT = TLI.getValueType(V->getType());
280 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V)))
281 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
282 visit(CE->getOpcode(), *CE);
283 assert(N.Val && "visit didn't populate the ValueMap!");
284 return N;
285 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
286 return N = DAG.getGlobalAddress(GV, VT);
287 } else if (isa<ConstantPointerNull>(C)) {
288 return N = DAG.getConstant(0, TLI.getPointerTy());
289 } else if (isa<UndefValue>(C)) {
Nate Begemanaf1c0f72005-04-12 23:12:17 +0000290 return N = DAG.getNode(ISD::UNDEF, VT);
Chris Lattner7a60d912005-01-07 07:47:53 +0000291 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
292 return N = DAG.getConstantFP(CFP->getValue(), VT);
293 } else {
294 // Canonicalize all constant ints to be unsigned.
295 return N = DAG.getConstant(cast<ConstantIntegral>(C)->getRawValue(),VT);
296 }
297
298 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
299 std::map<const AllocaInst*, int>::iterator SI =
300 FuncInfo.StaticAllocaMap.find(AI);
301 if (SI != FuncInfo.StaticAllocaMap.end())
302 return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
303 }
304
305 std::map<const Value*, unsigned>::const_iterator VMI =
306 FuncInfo.ValueMap.find(V);
307 assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!");
Chris Lattner209f5852005-01-16 02:23:07 +0000308
Chris Lattner33182322005-08-16 21:55:35 +0000309 unsigned InReg = VMI->second;
310
311 // If this type is not legal, make it so now.
312 MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT);
313
314 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
315 if (DestVT < VT) {
316 // Source must be expanded. This input value is actually coming from the
317 // register pair VMI->second and VMI->second+1.
318 N = DAG.getNode(ISD::BUILD_PAIR, VT, N,
319 DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT));
320 } else {
321 if (DestVT > VT) { // Promotion case
322 if (MVT::isFloatingPoint(VT))
323 N = DAG.getNode(ISD::FP_ROUND, VT, N);
324 else
325 N = DAG.getNode(ISD::TRUNCATE, VT, N);
326 }
327 }
328
329 return N;
Chris Lattner7a60d912005-01-07 07:47:53 +0000330 }
331
332 const SDOperand &setValue(const Value *V, SDOperand NewN) {
333 SDOperand &N = NodeMap[V];
334 assert(N.Val == 0 && "Already set a value for this node!");
335 return N = NewN;
336 }
337
338 // Terminator instructions.
339 void visitRet(ReturnInst &I);
340 void visitBr(BranchInst &I);
341 void visitUnreachable(UnreachableInst &I) { /* noop */ }
342
343 // These all get lowered before this pass.
344 void visitSwitch(SwitchInst &I) { assert(0 && "TODO"); }
345 void visitInvoke(InvokeInst &I) { assert(0 && "TODO"); }
346 void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); }
347
348 //
Chris Lattner7f9e0782005-08-22 17:28:31 +0000349 void visitBinary(User &I, unsigned Opcode, bool isShift = false);
Chris Lattner6f3b5772005-09-28 22:28:18 +0000350 void visitAdd(User &I) {
351 visitBinary(I, I.getType()->isFloatingPoint() ? ISD::FADD : ISD::ADD);
352 }
Chris Lattnerf68fd0b2005-04-02 05:04:50 +0000353 void visitSub(User &I);
Chris Lattner6f3b5772005-09-28 22:28:18 +0000354 void visitMul(User &I) {
355 visitBinary(I, I.getType()->isFloatingPoint() ? ISD::FMUL : ISD::MUL);
356 }
Chris Lattner7a60d912005-01-07 07:47:53 +0000357 void visitDiv(User &I) {
Chris Lattner6f3b5772005-09-28 22:28:18 +0000358 unsigned Opc;
359 const Type *Ty = I.getType();
360 if (Ty->isFloatingPoint())
361 Opc = ISD::FDIV;
362 else if (Ty->isUnsigned())
363 Opc = ISD::UDIV;
364 else
365 Opc = ISD::SDIV;
366 visitBinary(I, Opc);
Chris Lattner7a60d912005-01-07 07:47:53 +0000367 }
368 void visitRem(User &I) {
Chris Lattner6f3b5772005-09-28 22:28:18 +0000369 unsigned Opc;
370 const Type *Ty = I.getType();
371 if (Ty->isFloatingPoint())
372 Opc = ISD::FREM;
373 else if (Ty->isUnsigned())
374 Opc = ISD::UREM;
375 else
376 Opc = ISD::SREM;
377 visitBinary(I, Opc);
Chris Lattner7a60d912005-01-07 07:47:53 +0000378 }
379 void visitAnd(User &I) { visitBinary(I, ISD::AND); }
380 void visitOr (User &I) { visitBinary(I, ISD::OR); }
381 void visitXor(User &I) { visitBinary(I, ISD::XOR); }
Chris Lattner7f9e0782005-08-22 17:28:31 +0000382 void visitShl(User &I) { visitBinary(I, ISD::SHL, true); }
Chris Lattner7a60d912005-01-07 07:47:53 +0000383 void visitShr(User &I) {
Chris Lattner7f9e0782005-08-22 17:28:31 +0000384 visitBinary(I, I.getType()->isUnsigned() ? ISD::SRL : ISD::SRA, true);
Chris Lattner7a60d912005-01-07 07:47:53 +0000385 }
386
387 void visitSetCC(User &I, ISD::CondCode SignedOpc, ISD::CondCode UnsignedOpc);
388 void visitSetEQ(User &I) { visitSetCC(I, ISD::SETEQ, ISD::SETEQ); }
389 void visitSetNE(User &I) { visitSetCC(I, ISD::SETNE, ISD::SETNE); }
390 void visitSetLE(User &I) { visitSetCC(I, ISD::SETLE, ISD::SETULE); }
391 void visitSetGE(User &I) { visitSetCC(I, ISD::SETGE, ISD::SETUGE); }
392 void visitSetLT(User &I) { visitSetCC(I, ISD::SETLT, ISD::SETULT); }
393 void visitSetGT(User &I) { visitSetCC(I, ISD::SETGT, ISD::SETUGT); }
394
395 void visitGetElementPtr(User &I);
396 void visitCast(User &I);
397 void visitSelect(User &I);
398 //
399
400 void visitMalloc(MallocInst &I);
401 void visitFree(FreeInst &I);
402 void visitAlloca(AllocaInst &I);
403 void visitLoad(LoadInst &I);
404 void visitStore(StoreInst &I);
405 void visitPHI(PHINode &I) { } // PHI nodes are handled specially.
406 void visitCall(CallInst &I);
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000407 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic);
Chris Lattner7a60d912005-01-07 07:47:53 +0000408
Chris Lattner7a60d912005-01-07 07:47:53 +0000409 void visitVAStart(CallInst &I);
Chris Lattner7a60d912005-01-07 07:47:53 +0000410 void visitVAArg(VAArgInst &I);
411 void visitVAEnd(CallInst &I);
412 void visitVACopy(CallInst &I);
Chris Lattner58cfd792005-01-09 00:00:49 +0000413 void visitFrameReturnAddress(CallInst &I, bool isFrameAddress);
Chris Lattner7a60d912005-01-07 07:47:53 +0000414
Chris Lattner875def92005-01-11 05:56:49 +0000415 void visitMemIntrinsic(CallInst &I, unsigned Op);
Chris Lattner7a60d912005-01-07 07:47:53 +0000416
417 void visitUserOp1(Instruction &I) {
418 assert(0 && "UserOp1 should not exist at instruction selection time!");
419 abort();
420 }
421 void visitUserOp2(Instruction &I) {
422 assert(0 && "UserOp2 should not exist at instruction selection time!");
423 abort();
424 }
425};
426} // end namespace llvm
427
428void SelectionDAGLowering::visitRet(ReturnInst &I) {
429 if (I.getNumOperands() == 0) {
Chris Lattner4108bb02005-01-17 19:43:36 +0000430 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot()));
Chris Lattner7a60d912005-01-07 07:47:53 +0000431 return;
432 }
433
434 SDOperand Op1 = getValue(I.getOperand(0));
Chris Lattnerdb45f7d2005-03-29 19:09:56 +0000435 MVT::ValueType TmpVT;
436
Chris Lattner7a60d912005-01-07 07:47:53 +0000437 switch (Op1.getValueType()) {
438 default: assert(0 && "Unknown value type!");
439 case MVT::i1:
440 case MVT::i8:
441 case MVT::i16:
Chris Lattnerdb45f7d2005-03-29 19:09:56 +0000442 case MVT::i32:
443 // If this is a machine where 32-bits is legal or expanded, promote to
444 // 32-bits, otherwise, promote to 64-bits.
445 if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote)
446 TmpVT = TLI.getTypeToTransformTo(MVT::i32);
Chris Lattner7a60d912005-01-07 07:47:53 +0000447 else
Chris Lattnerdb45f7d2005-03-29 19:09:56 +0000448 TmpVT = MVT::i32;
449
450 // Extend integer types to result type.
451 if (I.getOperand(0)->getType()->isSigned())
452 Op1 = DAG.getNode(ISD::SIGN_EXTEND, TmpVT, Op1);
453 else
454 Op1 = DAG.getNode(ISD::ZERO_EXTEND, TmpVT, Op1);
Chris Lattner7a60d912005-01-07 07:47:53 +0000455 break;
456 case MVT::f32:
Chris Lattner7a60d912005-01-07 07:47:53 +0000457 case MVT::i64:
458 case MVT::f64:
459 break; // No extension needed!
460 }
Nate Begeman78afac22005-10-18 23:23:37 +0000461 // Allow targets to lower this further to meet ABI requirements
462 DAG.setRoot(TLI.LowerReturnTo(getRoot(), Op1, DAG));
Chris Lattner7a60d912005-01-07 07:47:53 +0000463}
464
465void SelectionDAGLowering::visitBr(BranchInst &I) {
466 // Update machine-CFG edges.
467 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)];
Chris Lattner7a60d912005-01-07 07:47:53 +0000468
469 // Figure out which block is immediately after the current one.
470 MachineBasicBlock *NextBlock = 0;
471 MachineFunction::iterator BBI = CurMBB;
472 if (++BBI != CurMBB->getParent()->end())
473 NextBlock = BBI;
474
475 if (I.isUnconditional()) {
476 // If this is not a fall-through branch, emit the branch.
477 if (Succ0MBB != NextBlock)
Chris Lattner4108bb02005-01-17 19:43:36 +0000478 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
Misha Brukman77451162005-04-22 04:01:18 +0000479 DAG.getBasicBlock(Succ0MBB)));
Chris Lattner7a60d912005-01-07 07:47:53 +0000480 } else {
481 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
Chris Lattner7a60d912005-01-07 07:47:53 +0000482
483 SDOperand Cond = getValue(I.getCondition());
Chris Lattner7a60d912005-01-07 07:47:53 +0000484 if (Succ1MBB == NextBlock) {
485 // If the condition is false, fall through. This means we should branch
486 // if the condition is true to Succ #0.
Chris Lattner4108bb02005-01-17 19:43:36 +0000487 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(),
Misha Brukman77451162005-04-22 04:01:18 +0000488 Cond, DAG.getBasicBlock(Succ0MBB)));
Chris Lattner7a60d912005-01-07 07:47:53 +0000489 } else if (Succ0MBB == NextBlock) {
490 // If the condition is true, fall through. This means we should branch if
491 // the condition is false to Succ #1. Invert the condition first.
492 SDOperand True = DAG.getConstant(1, Cond.getValueType());
493 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True);
Chris Lattner4108bb02005-01-17 19:43:36 +0000494 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(),
Misha Brukman77451162005-04-22 04:01:18 +0000495 Cond, DAG.getBasicBlock(Succ1MBB)));
Chris Lattner7a60d912005-01-07 07:47:53 +0000496 } else {
Chris Lattner8a98c7f2005-04-09 03:30:29 +0000497 std::vector<SDOperand> Ops;
498 Ops.push_back(getRoot());
499 Ops.push_back(Cond);
500 Ops.push_back(DAG.getBasicBlock(Succ0MBB));
501 Ops.push_back(DAG.getBasicBlock(Succ1MBB));
502 DAG.setRoot(DAG.getNode(ISD::BRCONDTWOWAY, MVT::Other, Ops));
Chris Lattner7a60d912005-01-07 07:47:53 +0000503 }
504 }
505}
506
Chris Lattnerf68fd0b2005-04-02 05:04:50 +0000507void SelectionDAGLowering::visitSub(User &I) {
508 // -0.0 - X --> fneg
Chris Lattner6f3b5772005-09-28 22:28:18 +0000509 if (I.getType()->isFloatingPoint()) {
510 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0)))
511 if (CFP->isExactlyValue(-0.0)) {
512 SDOperand Op2 = getValue(I.getOperand(1));
513 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
514 return;
515 }
516 visitBinary(I, ISD::FSUB);
517 } else {
518 visitBinary(I, ISD::SUB);
519 }
Chris Lattnerf68fd0b2005-04-02 05:04:50 +0000520}
521
Chris Lattner7f9e0782005-08-22 17:28:31 +0000522void SelectionDAGLowering::visitBinary(User &I, unsigned Opcode, bool isShift) {
Chris Lattner7a60d912005-01-07 07:47:53 +0000523 SDOperand Op1 = getValue(I.getOperand(0));
524 SDOperand Op2 = getValue(I.getOperand(1));
Chris Lattner96c26752005-01-19 22:31:21 +0000525
Chris Lattner7f9e0782005-08-22 17:28:31 +0000526 if (isShift)
Chris Lattnera66403d2005-09-02 00:19:37 +0000527 Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2);
Chris Lattner96c26752005-01-19 22:31:21 +0000528
Chris Lattner7a60d912005-01-07 07:47:53 +0000529 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2));
530}
531
532void SelectionDAGLowering::visitSetCC(User &I,ISD::CondCode SignedOpcode,
533 ISD::CondCode UnsignedOpcode) {
534 SDOperand Op1 = getValue(I.getOperand(0));
535 SDOperand Op2 = getValue(I.getOperand(1));
536 ISD::CondCode Opcode = SignedOpcode;
537 if (I.getOperand(0)->getType()->isUnsigned())
538 Opcode = UnsignedOpcode;
Chris Lattnerd47675e2005-08-09 20:20:18 +0000539 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode));
Chris Lattner7a60d912005-01-07 07:47:53 +0000540}
541
542void SelectionDAGLowering::visitSelect(User &I) {
543 SDOperand Cond = getValue(I.getOperand(0));
544 SDOperand TrueVal = getValue(I.getOperand(1));
545 SDOperand FalseVal = getValue(I.getOperand(2));
546 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
547 TrueVal, FalseVal));
548}
549
550void SelectionDAGLowering::visitCast(User &I) {
551 SDOperand N = getValue(I.getOperand(0));
552 MVT::ValueType SrcTy = TLI.getValueType(I.getOperand(0)->getType());
553 MVT::ValueType DestTy = TLI.getValueType(I.getType());
554
555 if (N.getValueType() == DestTy) {
556 setValue(&I, N); // noop cast.
Chris Lattner2d8b55c2005-05-09 22:17:13 +0000557 } else if (DestTy == MVT::i1) {
558 // Cast to bool is a comparison against zero, not truncation to zero.
559 SDOperand Zero = isInteger(SrcTy) ? DAG.getConstant(0, N.getValueType()) :
560 DAG.getConstantFP(0.0, N.getValueType());
Chris Lattnerd47675e2005-08-09 20:20:18 +0000561 setValue(&I, DAG.getSetCC(MVT::i1, N, Zero, ISD::SETNE));
Chris Lattner2a6db3c2005-01-08 08:08:56 +0000562 } else if (isInteger(SrcTy)) {
563 if (isInteger(DestTy)) { // Int -> Int cast
564 if (DestTy < SrcTy) // Truncating cast?
565 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestTy, N));
566 else if (I.getOperand(0)->getType()->isSigned())
567 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestTy, N));
568 else
569 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestTy, N));
570 } else { // Int -> FP cast
571 if (I.getOperand(0)->getType()->isSigned())
572 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestTy, N));
573 else
574 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestTy, N));
575 }
Chris Lattner7a60d912005-01-07 07:47:53 +0000576 } else {
Chris Lattner2a6db3c2005-01-08 08:08:56 +0000577 assert(isFloatingPoint(SrcTy) && "Unknown value type!");
578 if (isFloatingPoint(DestTy)) { // FP -> FP cast
579 if (DestTy < SrcTy) // Rounding cast?
580 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestTy, N));
581 else
582 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestTy, N));
583 } else { // FP -> Int cast.
584 if (I.getType()->isSigned())
585 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestTy, N));
586 else
587 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestTy, N));
588 }
Chris Lattner7a60d912005-01-07 07:47:53 +0000589 }
590}
591
592void SelectionDAGLowering::visitGetElementPtr(User &I) {
593 SDOperand N = getValue(I.getOperand(0));
594 const Type *Ty = I.getOperand(0)->getType();
595 const Type *UIntPtrTy = TD.getIntPtrType();
596
597 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end();
598 OI != E; ++OI) {
599 Value *Idx = *OI;
600 if (const StructType *StTy = dyn_cast<StructType> (Ty)) {
601 unsigned Field = cast<ConstantUInt>(Idx)->getValue();
602 if (Field) {
603 // N = N + Offset
604 uint64_t Offset = TD.getStructLayout(StTy)->MemberOffsets[Field];
605 N = DAG.getNode(ISD::ADD, N.getValueType(), N,
Misha Brukman77451162005-04-22 04:01:18 +0000606 getIntPtrConstant(Offset));
Chris Lattner7a60d912005-01-07 07:47:53 +0000607 }
608 Ty = StTy->getElementType(Field);
609 } else {
610 Ty = cast<SequentialType>(Ty)->getElementType();
Chris Lattner19a83992005-01-07 21:56:57 +0000611
Chris Lattner43535a12005-11-09 04:45:33 +0000612 // If this is a constant subscript, handle it quickly.
613 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
614 if (CI->getRawValue() == 0) continue;
Chris Lattner19a83992005-01-07 21:56:57 +0000615
Chris Lattner43535a12005-11-09 04:45:33 +0000616 uint64_t Offs;
617 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(CI))
618 Offs = (int64_t)TD.getTypeSize(Ty)*CSI->getValue();
619 else
620 Offs = TD.getTypeSize(Ty)*cast<ConstantUInt>(CI)->getValue();
621 N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs));
622 continue;
Chris Lattner7a60d912005-01-07 07:47:53 +0000623 }
Chris Lattner43535a12005-11-09 04:45:33 +0000624
625 // N = N + Idx * ElementSize;
626 uint64_t ElementSize = TD.getTypeSize(Ty);
627 SDOperand IdxN = getValue(Idx);
628
629 // If the index is smaller or larger than intptr_t, truncate or extend
630 // it.
631 if (IdxN.getValueType() < N.getValueType()) {
632 if (Idx->getType()->isSigned())
633 IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN);
634 else
635 IdxN = DAG.getNode(ISD::ZERO_EXTEND, N.getValueType(), IdxN);
636 } else if (IdxN.getValueType() > N.getValueType())
637 IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN);
638
639 // If this is a multiply by a power of two, turn it into a shl
640 // immediately. This is a very common case.
641 if (isPowerOf2_64(ElementSize)) {
642 unsigned Amt = Log2_64(ElementSize);
643 IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN,
Chris Lattner41fd6d52005-11-09 16:50:40 +0000644 DAG.getConstant(Amt, TLI.getShiftAmountTy()));
Chris Lattner43535a12005-11-09 04:45:33 +0000645 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
646 continue;
647 }
648
649 SDOperand Scale = getIntPtrConstant(ElementSize);
650 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale);
651 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN);
Chris Lattner7a60d912005-01-07 07:47:53 +0000652 }
653 }
654 setValue(&I, N);
655}
656
657void SelectionDAGLowering::visitAlloca(AllocaInst &I) {
658 // If this is a fixed sized alloca in the entry block of the function,
659 // allocate it statically on the stack.
660 if (FuncInfo.StaticAllocaMap.count(&I))
661 return; // getValue will auto-populate this.
662
663 const Type *Ty = I.getAllocatedType();
664 uint64_t TySize = TLI.getTargetData().getTypeSize(Ty);
Nate Begeman3ee3e692005-11-06 09:00:38 +0000665 unsigned Align = std::max((unsigned)TLI.getTargetData().getTypeAlignment(Ty),
666 I.getAlignment());
Chris Lattner7a60d912005-01-07 07:47:53 +0000667
668 SDOperand AllocSize = getValue(I.getArraySize());
Chris Lattnereccb73d2005-01-22 23:04:37 +0000669 MVT::ValueType IntPtr = TLI.getPointerTy();
670 if (IntPtr < AllocSize.getValueType())
671 AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize);
672 else if (IntPtr > AllocSize.getValueType())
673 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize);
Chris Lattner7a60d912005-01-07 07:47:53 +0000674
Chris Lattnereccb73d2005-01-22 23:04:37 +0000675 AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize,
Chris Lattner7a60d912005-01-07 07:47:53 +0000676 getIntPtrConstant(TySize));
677
678 // Handle alignment. If the requested alignment is less than or equal to the
679 // stack alignment, ignore it and round the size of the allocation up to the
680 // stack alignment size. If the size is greater than the stack alignment, we
681 // note this in the DYNAMIC_STACKALLOC node.
682 unsigned StackAlign =
683 TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
684 if (Align <= StackAlign) {
685 Align = 0;
686 // Add SA-1 to the size.
687 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
688 getIntPtrConstant(StackAlign-1));
689 // Mask out the low bits for alignment purposes.
690 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
691 getIntPtrConstant(~(uint64_t)(StackAlign-1)));
692 }
693
Chris Lattner96c262e2005-05-14 07:29:57 +0000694 std::vector<MVT::ValueType> VTs;
695 VTs.push_back(AllocSize.getValueType());
696 VTs.push_back(MVT::Other);
697 std::vector<SDOperand> Ops;
698 Ops.push_back(getRoot());
699 Ops.push_back(AllocSize);
700 Ops.push_back(getIntPtrConstant(Align));
701 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops);
Chris Lattner7a60d912005-01-07 07:47:53 +0000702 DAG.setRoot(setValue(&I, DSA).getValue(1));
703
704 // Inform the Frame Information that we have just allocated a variable-sized
705 // object.
706 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject();
707}
708
709
710void SelectionDAGLowering::visitLoad(LoadInst &I) {
711 SDOperand Ptr = getValue(I.getOperand(0));
Misha Brukman835702a2005-04-21 22:36:52 +0000712
Chris Lattner4d9651c2005-01-17 22:19:26 +0000713 SDOperand Root;
714 if (I.isVolatile())
715 Root = getRoot();
716 else {
717 // Do not serialize non-volatile loads against each other.
718 Root = DAG.getRoot();
719 }
720
Chris Lattnerf5675a02005-05-09 04:08:33 +0000721 SDOperand L = DAG.getLoad(TLI.getValueType(I.getType()), Root, Ptr,
Andrew Lenharth2edc1882005-06-29 18:54:02 +0000722 DAG.getSrcValue(I.getOperand(0)));
Chris Lattner4d9651c2005-01-17 22:19:26 +0000723 setValue(&I, L);
724
725 if (I.isVolatile())
726 DAG.setRoot(L.getValue(1));
727 else
728 PendingLoads.push_back(L.getValue(1));
Chris Lattner7a60d912005-01-07 07:47:53 +0000729}
730
731
732void SelectionDAGLowering::visitStore(StoreInst &I) {
733 Value *SrcV = I.getOperand(0);
734 SDOperand Src = getValue(SrcV);
735 SDOperand Ptr = getValue(I.getOperand(1));
Chris Lattnerf5675a02005-05-09 04:08:33 +0000736 DAG.setRoot(DAG.getNode(ISD::STORE, MVT::Other, getRoot(), Src, Ptr,
Andrew Lenharth2edc1882005-06-29 18:54:02 +0000737 DAG.getSrcValue(I.getOperand(1))));
Chris Lattner7a60d912005-01-07 07:47:53 +0000738}
739
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000740/// visitIntrinsicCall - Lower the call to the specified intrinsic function. If
741/// we want to emit this as a call to a named external function, return the name
742/// otherwise lower it and return null.
743const char *
744SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
745 switch (Intrinsic) {
746 case Intrinsic::vastart: visitVAStart(I); return 0;
747 case Intrinsic::vaend: visitVAEnd(I); return 0;
748 case Intrinsic::vacopy: visitVACopy(I); return 0;
749 case Intrinsic::returnaddress: visitFrameReturnAddress(I, false); return 0;
750 case Intrinsic::frameaddress: visitFrameReturnAddress(I, true); return 0;
751 case Intrinsic::setjmp:
752 return "_setjmp"+!TLI.usesUnderscoreSetJmpLongJmp();
753 break;
754 case Intrinsic::longjmp:
755 return "_longjmp"+!TLI.usesUnderscoreSetJmpLongJmp();
756 break;
757 case Intrinsic::memcpy: visitMemIntrinsic(I, ISD::MEMCPY); return 0;
758 case Intrinsic::memset: visitMemIntrinsic(I, ISD::MEMSET); return 0;
759 case Intrinsic::memmove: visitMemIntrinsic(I, ISD::MEMMOVE); return 0;
760
761 case Intrinsic::readport:
762 case Intrinsic::readio: {
763 std::vector<MVT::ValueType> VTs;
764 VTs.push_back(TLI.getValueType(I.getType()));
765 VTs.push_back(MVT::Other);
766 std::vector<SDOperand> Ops;
767 Ops.push_back(getRoot());
768 Ops.push_back(getValue(I.getOperand(1)));
769 SDOperand Tmp = DAG.getNode(Intrinsic == Intrinsic::readport ?
770 ISD::READPORT : ISD::READIO, VTs, Ops);
771
772 setValue(&I, Tmp);
773 DAG.setRoot(Tmp.getValue(1));
774 return 0;
775 }
776 case Intrinsic::writeport:
777 case Intrinsic::writeio:
778 DAG.setRoot(DAG.getNode(Intrinsic == Intrinsic::writeport ?
779 ISD::WRITEPORT : ISD::WRITEIO, MVT::Other,
780 getRoot(), getValue(I.getOperand(1)),
781 getValue(I.getOperand(2))));
782 return 0;
783 case Intrinsic::dbg_stoppoint:
784 case Intrinsic::dbg_region_start:
785 case Intrinsic::dbg_region_end:
786 case Intrinsic::dbg_func_start:
787 case Intrinsic::dbg_declare:
788 if (I.getType() != Type::VoidTy)
789 setValue(&I, DAG.getNode(ISD::UNDEF, TLI.getValueType(I.getType())));
790 return 0;
791
792 case Intrinsic::isunordered:
793 setValue(&I, DAG.getSetCC(MVT::i1,getValue(I.getOperand(1)),
794 getValue(I.getOperand(2)), ISD::SETUO));
795 return 0;
796
797 case Intrinsic::sqrt:
798 setValue(&I, DAG.getNode(ISD::FSQRT,
799 getValue(I.getOperand(1)).getValueType(),
800 getValue(I.getOperand(1))));
801 return 0;
802 case Intrinsic::pcmarker: {
803 SDOperand Tmp = getValue(I.getOperand(1));
804 DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp));
805 return 0;
806 }
Andrew Lenharthde1b5d62005-11-11 22:48:54 +0000807 case Intrinsic::readcyclecounter: {
808 std::vector<MVT::ValueType> VTs;
809 VTs.push_back(MVT::i64);
810 VTs.push_back(MVT::Other);
811 std::vector<SDOperand> Ops;
812 Ops.push_back(getRoot());
813 SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER, VTs, Ops);
814 setValue(&I, Tmp);
815 DAG.setRoot(Tmp.getValue(1));
Andrew Lenharth01aa5632005-11-11 16:47:30 +0000816 return 0;
Andrew Lenharthde1b5d62005-11-11 22:48:54 +0000817 }
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000818 case Intrinsic::cttz:
819 setValue(&I, DAG.getNode(ISD::CTTZ,
820 getValue(I.getOperand(1)).getValueType(),
821 getValue(I.getOperand(1))));
822 return 0;
823 case Intrinsic::ctlz:
824 setValue(&I, DAG.getNode(ISD::CTLZ,
825 getValue(I.getOperand(1)).getValueType(),
826 getValue(I.getOperand(1))));
827 return 0;
828 case Intrinsic::ctpop:
829 setValue(&I, DAG.getNode(ISD::CTPOP,
830 getValue(I.getOperand(1)).getValueType(),
831 getValue(I.getOperand(1))));
832 return 0;
833 default:
834 std::cerr << I;
835 assert(0 && "This intrinsic is not implemented yet!");
836 return 0;
837 }
838}
839
840
Chris Lattner7a60d912005-01-07 07:47:53 +0000841void SelectionDAGLowering::visitCall(CallInst &I) {
Chris Lattner18d2b342005-01-08 22:48:57 +0000842 const char *RenameFn = 0;
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000843 if (Function *F = I.getCalledFunction()) {
Chris Lattner0c140002005-04-02 05:26:53 +0000844 if (F->isExternal())
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000845 if (unsigned IID = F->getIntrinsicID()) {
846 RenameFn = visitIntrinsicCall(I, IID);
847 if (!RenameFn)
848 return;
849 } else { // Not an LLVM intrinsic.
850 const std::string &Name = F->getName();
851 if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) {
Chris Lattner0c140002005-04-02 05:26:53 +0000852 if (I.getNumOperands() == 2 && // Basic sanity checks.
853 I.getOperand(1)->getType()->isFloatingPoint() &&
854 I.getType() == I.getOperand(1)->getType()) {
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000855 SDOperand Tmp = getValue(I.getOperand(1));
Chris Lattner0c140002005-04-02 05:26:53 +0000856 setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
857 return;
858 }
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000859 } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) {
Chris Lattner80026402005-04-30 04:43:14 +0000860 if (I.getNumOperands() == 2 && // Basic sanity checks.
861 I.getOperand(1)->getType()->isFloatingPoint() &&
862 I.getType() == I.getOperand(1)->getType()) {
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000863 SDOperand Tmp = getValue(I.getOperand(1));
Chris Lattner80026402005-04-30 04:43:14 +0000864 setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
865 return;
866 }
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000867 } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) {
Chris Lattner80026402005-04-30 04:43:14 +0000868 if (I.getNumOperands() == 2 && // Basic sanity checks.
869 I.getOperand(1)->getType()->isFloatingPoint() &&
870 I.getType() == I.getOperand(1)->getType()) {
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000871 SDOperand Tmp = getValue(I.getOperand(1));
Chris Lattner80026402005-04-30 04:43:14 +0000872 setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
873 return;
874 }
875 }
Chris Lattnere4f71d02005-05-14 13:56:55 +0000876 }
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000877 }
Misha Brukman835702a2005-04-21 22:36:52 +0000878
Chris Lattner18d2b342005-01-08 22:48:57 +0000879 SDOperand Callee;
880 if (!RenameFn)
881 Callee = getValue(I.getOperand(0));
882 else
883 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
Chris Lattner7a60d912005-01-07 07:47:53 +0000884 std::vector<std::pair<SDOperand, const Type*> > Args;
Chris Lattnercd6f0f42005-11-09 19:44:01 +0000885 Args.reserve(I.getNumOperands());
Chris Lattner7a60d912005-01-07 07:47:53 +0000886 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
887 Value *Arg = I.getOperand(i);
888 SDOperand ArgNode = getValue(Arg);
889 Args.push_back(std::make_pair(ArgNode, Arg->getType()));
890 }
Misha Brukman835702a2005-04-21 22:36:52 +0000891
Nate Begemanf6565252005-03-26 01:29:23 +0000892 const PointerType *PT = cast<PointerType>(I.getCalledValue()->getType());
893 const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
Misha Brukman835702a2005-04-21 22:36:52 +0000894
Chris Lattner1f45cd72005-01-08 19:26:18 +0000895 std::pair<SDOperand,SDOperand> Result =
Chris Lattner111778e2005-05-12 19:56:57 +0000896 TLI.LowerCallTo(getRoot(), I.getType(), FTy->isVarArg(), I.getCallingConv(),
Chris Lattner2e77db62005-05-13 18:50:42 +0000897 I.isTailCall(), Callee, Args, DAG);
Chris Lattner7a60d912005-01-07 07:47:53 +0000898 if (I.getType() != Type::VoidTy)
Chris Lattner1f45cd72005-01-08 19:26:18 +0000899 setValue(&I, Result.first);
900 DAG.setRoot(Result.second);
Chris Lattner7a60d912005-01-07 07:47:53 +0000901}
902
903void SelectionDAGLowering::visitMalloc(MallocInst &I) {
904 SDOperand Src = getValue(I.getOperand(0));
905
906 MVT::ValueType IntPtr = TLI.getPointerTy();
Chris Lattnereccb73d2005-01-22 23:04:37 +0000907
908 if (IntPtr < Src.getValueType())
909 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src);
910 else if (IntPtr > Src.getValueType())
911 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
Chris Lattner7a60d912005-01-07 07:47:53 +0000912
913 // Scale the source by the type size.
914 uint64_t ElementSize = TD.getTypeSize(I.getType()->getElementType());
915 Src = DAG.getNode(ISD::MUL, Src.getValueType(),
916 Src, getIntPtrConstant(ElementSize));
917
918 std::vector<std::pair<SDOperand, const Type*> > Args;
919 Args.push_back(std::make_pair(Src, TLI.getTargetData().getIntPtrType()));
Chris Lattner1f45cd72005-01-08 19:26:18 +0000920
921 std::pair<SDOperand,SDOperand> Result =
Chris Lattner2e77db62005-05-13 18:50:42 +0000922 TLI.LowerCallTo(getRoot(), I.getType(), false, CallingConv::C, true,
Chris Lattner1f45cd72005-01-08 19:26:18 +0000923 DAG.getExternalSymbol("malloc", IntPtr),
924 Args, DAG);
925 setValue(&I, Result.first); // Pointers always fit in registers
926 DAG.setRoot(Result.second);
Chris Lattner7a60d912005-01-07 07:47:53 +0000927}
928
929void SelectionDAGLowering::visitFree(FreeInst &I) {
930 std::vector<std::pair<SDOperand, const Type*> > Args;
931 Args.push_back(std::make_pair(getValue(I.getOperand(0)),
932 TLI.getTargetData().getIntPtrType()));
933 MVT::ValueType IntPtr = TLI.getPointerTy();
Chris Lattner1f45cd72005-01-08 19:26:18 +0000934 std::pair<SDOperand,SDOperand> Result =
Chris Lattner2e77db62005-05-13 18:50:42 +0000935 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, CallingConv::C, true,
Chris Lattner1f45cd72005-01-08 19:26:18 +0000936 DAG.getExternalSymbol("free", IntPtr), Args, DAG);
937 DAG.setRoot(Result.second);
Chris Lattner7a60d912005-01-07 07:47:53 +0000938}
939
Chris Lattner13d7c252005-08-26 20:54:47 +0000940// InsertAtEndOfBasicBlock - This method should be implemented by targets that
941// mark instructions with the 'usesCustomDAGSchedInserter' flag. These
942// instructions are special in various ways, which require special support to
943// insert. The specified MachineInstr is created but not inserted into any
944// basic blocks, and the scheduler passes ownership of it to this method.
945MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI,
946 MachineBasicBlock *MBB) {
947 std::cerr << "If a target marks an instruction with "
948 "'usesCustomDAGSchedInserter', it must implement "
949 "TargetLowering::InsertAtEndOfBasicBlock!\n";
950 abort();
951 return 0;
952}
953
Nate Begeman78afac22005-10-18 23:23:37 +0000954SDOperand TargetLowering::LowerReturnTo(SDOperand Chain, SDOperand Op,
955 SelectionDAG &DAG) {
956 return DAG.getNode(ISD::RET, MVT::Other, Chain, Op);
957}
958
Chris Lattnerf5473e42005-07-05 19:57:53 +0000959SDOperand TargetLowering::LowerVAStart(SDOperand Chain,
960 SDOperand VAListP, Value *VAListV,
961 SelectionDAG &DAG) {
Chris Lattner7a60d912005-01-07 07:47:53 +0000962 // We have no sane default behavior, just emit a useful error message and bail
963 // out.
Chris Lattner58cfd792005-01-09 00:00:49 +0000964 std::cerr << "Variable arguments handling not implemented on this target!\n";
Chris Lattner7a60d912005-01-07 07:47:53 +0000965 abort();
Chris Lattnerf5473e42005-07-05 19:57:53 +0000966 return SDOperand();
Chris Lattner7a60d912005-01-07 07:47:53 +0000967}
968
Chris Lattnerf5473e42005-07-05 19:57:53 +0000969SDOperand TargetLowering::LowerVAEnd(SDOperand Chain, SDOperand LP, Value *LV,
Chris Lattner58cfd792005-01-09 00:00:49 +0000970 SelectionDAG &DAG) {
971 // Default to a noop.
972 return Chain;
973}
974
Chris Lattnerf5473e42005-07-05 19:57:53 +0000975SDOperand TargetLowering::LowerVACopy(SDOperand Chain,
976 SDOperand SrcP, Value *SrcV,
977 SDOperand DestP, Value *DestV,
978 SelectionDAG &DAG) {
979 // Default to copying the input list.
980 SDOperand Val = DAG.getLoad(getPointerTy(), Chain,
981 SrcP, DAG.getSrcValue(SrcV));
Andrew Lenharth25314522005-06-22 21:04:42 +0000982 SDOperand Result = DAG.getNode(ISD::STORE, MVT::Other, Val.getValue(1),
Chris Lattnerf5473e42005-07-05 19:57:53 +0000983 Val, DestP, DAG.getSrcValue(DestV));
984 return Result;
Chris Lattner58cfd792005-01-09 00:00:49 +0000985}
986
987std::pair<SDOperand,SDOperand>
Chris Lattnerf5473e42005-07-05 19:57:53 +0000988TargetLowering::LowerVAArg(SDOperand Chain, SDOperand VAListP, Value *VAListV,
989 const Type *ArgTy, SelectionDAG &DAG) {
Chris Lattner58cfd792005-01-09 00:00:49 +0000990 // We have no sane default behavior, just emit a useful error message and bail
991 // out.
992 std::cerr << "Variable arguments handling not implemented on this target!\n";
993 abort();
Misha Brukman73e929f2005-02-17 21:39:27 +0000994 return std::make_pair(SDOperand(), SDOperand());
Chris Lattner58cfd792005-01-09 00:00:49 +0000995}
996
997
998void SelectionDAGLowering::visitVAStart(CallInst &I) {
Chris Lattnerf5473e42005-07-05 19:57:53 +0000999 DAG.setRoot(TLI.LowerVAStart(getRoot(), getValue(I.getOperand(1)),
1000 I.getOperand(1), DAG));
Chris Lattner58cfd792005-01-09 00:00:49 +00001001}
1002
1003void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
1004 std::pair<SDOperand,SDOperand> Result =
Chris Lattnerf5473e42005-07-05 19:57:53 +00001005 TLI.LowerVAArg(getRoot(), getValue(I.getOperand(0)), I.getOperand(0),
Andrew Lenharth9144ec42005-06-18 18:34:52 +00001006 I.getType(), DAG);
Chris Lattner58cfd792005-01-09 00:00:49 +00001007 setValue(&I, Result.first);
1008 DAG.setRoot(Result.second);
Chris Lattner7a60d912005-01-07 07:47:53 +00001009}
1010
1011void SelectionDAGLowering::visitVAEnd(CallInst &I) {
Jeff Cohen5f4ef3c2005-07-27 06:12:32 +00001012 DAG.setRoot(TLI.LowerVAEnd(getRoot(), getValue(I.getOperand(1)),
Chris Lattnerf5473e42005-07-05 19:57:53 +00001013 I.getOperand(1), DAG));
Chris Lattner7a60d912005-01-07 07:47:53 +00001014}
1015
1016void SelectionDAGLowering::visitVACopy(CallInst &I) {
Chris Lattnerf5473e42005-07-05 19:57:53 +00001017 SDOperand Result =
1018 TLI.LowerVACopy(getRoot(), getValue(I.getOperand(2)), I.getOperand(2),
1019 getValue(I.getOperand(1)), I.getOperand(1), DAG);
1020 DAG.setRoot(Result);
Chris Lattner7a60d912005-01-07 07:47:53 +00001021}
1022
Chris Lattner58cfd792005-01-09 00:00:49 +00001023
1024// It is always conservatively correct for llvm.returnaddress and
1025// llvm.frameaddress to return 0.
1026std::pair<SDOperand, SDOperand>
1027TargetLowering::LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain,
1028 unsigned Depth, SelectionDAG &DAG) {
1029 return std::make_pair(DAG.getConstant(0, getPointerTy()), Chain);
Chris Lattner7a60d912005-01-07 07:47:53 +00001030}
1031
Chris Lattner29dcc712005-05-14 05:50:48 +00001032SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
Chris Lattner897cd7d2005-01-16 07:28:41 +00001033 assert(0 && "LowerOperation not implemented for this target!");
1034 abort();
Misha Brukman73e929f2005-02-17 21:39:27 +00001035 return SDOperand();
Chris Lattner897cd7d2005-01-16 07:28:41 +00001036}
1037
Chris Lattner58cfd792005-01-09 00:00:49 +00001038void SelectionDAGLowering::visitFrameReturnAddress(CallInst &I, bool isFrame) {
1039 unsigned Depth = (unsigned)cast<ConstantUInt>(I.getOperand(1))->getValue();
1040 std::pair<SDOperand,SDOperand> Result =
Chris Lattner4108bb02005-01-17 19:43:36 +00001041 TLI.LowerFrameReturnAddress(isFrame, getRoot(), Depth, DAG);
Chris Lattner58cfd792005-01-09 00:00:49 +00001042 setValue(&I, Result.first);
1043 DAG.setRoot(Result.second);
Chris Lattner7a60d912005-01-07 07:47:53 +00001044}
1045
Chris Lattner875def92005-01-11 05:56:49 +00001046void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) {
1047 std::vector<SDOperand> Ops;
Chris Lattner4108bb02005-01-17 19:43:36 +00001048 Ops.push_back(getRoot());
Chris Lattner875def92005-01-11 05:56:49 +00001049 Ops.push_back(getValue(I.getOperand(1)));
1050 Ops.push_back(getValue(I.getOperand(2)));
1051 Ops.push_back(getValue(I.getOperand(3)));
1052 Ops.push_back(getValue(I.getOperand(4)));
1053 DAG.setRoot(DAG.getNode(Op, MVT::Other, Ops));
Chris Lattner7a60d912005-01-07 07:47:53 +00001054}
1055
Chris Lattner875def92005-01-11 05:56:49 +00001056//===----------------------------------------------------------------------===//
1057// SelectionDAGISel code
1058//===----------------------------------------------------------------------===//
Chris Lattner7a60d912005-01-07 07:47:53 +00001059
1060unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
1061 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
1062}
1063
Chris Lattnerc9950c12005-08-17 06:37:43 +00001064void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
Chris Lattner1a908c82005-08-18 17:35:14 +00001065 // FIXME: we only modify the CFG to split critical edges. This
1066 // updates dom and loop info.
Chris Lattnerc9950c12005-08-17 06:37:43 +00001067}
Chris Lattner7a60d912005-01-07 07:47:53 +00001068
Chris Lattner7a60d912005-01-07 07:47:53 +00001069bool SelectionDAGISel::runOnFunction(Function &Fn) {
1070 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
1071 RegMap = MF.getSSARegMap();
1072 DEBUG(std::cerr << "\n\n\n=== " << Fn.getName() << "\n");
1073
Chris Lattnerc9950c12005-08-17 06:37:43 +00001074 // First pass, split all critical edges for PHI nodes with incoming values
1075 // that are constants, this way the load of the constant into a vreg will not
1076 // be placed into MBBs that are used some other way.
Chris Lattner1a908c82005-08-18 17:35:14 +00001077 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
1078 PHINode *PN;
1079 for (BasicBlock::iterator BBI = BB->begin();
1080 (PN = dyn_cast<PHINode>(BBI)); ++BBI)
1081 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1082 if (isa<Constant>(PN->getIncomingValue(i)))
1083 SplitCriticalEdge(PN->getIncomingBlock(i), BB);
1084 }
Chris Lattnercd6f0f42005-11-09 19:44:01 +00001085
Chris Lattner7a60d912005-01-07 07:47:53 +00001086 FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
1087
1088 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
1089 SelectBasicBlock(I, MF, FuncInfo);
Misha Brukman835702a2005-04-21 22:36:52 +00001090
Chris Lattner7a60d912005-01-07 07:47:53 +00001091 return true;
1092}
1093
1094
Chris Lattner718b5c22005-01-13 17:59:43 +00001095SDOperand SelectionDAGISel::
1096CopyValueToVirtualRegister(SelectionDAGLowering &SDL, Value *V, unsigned Reg) {
Chris Lattner613f79f2005-01-11 22:03:46 +00001097 SDOperand Op = SDL.getValue(V);
Chris Lattnere727af02005-01-13 20:50:02 +00001098 assert((Op.getOpcode() != ISD::CopyFromReg ||
Chris Lattner33182322005-08-16 21:55:35 +00001099 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
Chris Lattnere727af02005-01-13 20:50:02 +00001100 "Copy from a reg to the same reg!");
Chris Lattner33182322005-08-16 21:55:35 +00001101
1102 // If this type is not legal, we must make sure to not create an invalid
1103 // register use.
1104 MVT::ValueType SrcVT = Op.getValueType();
1105 MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT);
1106 SelectionDAG &DAG = SDL.DAG;
1107 if (SrcVT == DestVT) {
1108 return DAG.getCopyToReg(SDL.getRoot(), Reg, Op);
1109 } else if (SrcVT < DestVT) {
1110 // The src value is promoted to the register.
Chris Lattnerba28c272005-08-17 06:06:25 +00001111 if (MVT::isFloatingPoint(SrcVT))
1112 Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op);
1113 else
Chris Lattnera66403d2005-09-02 00:19:37 +00001114 Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op);
Chris Lattner33182322005-08-16 21:55:35 +00001115 return DAG.getCopyToReg(SDL.getRoot(), Reg, Op);
1116 } else {
1117 // The src value is expanded into multiple registers.
1118 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
1119 Op, DAG.getConstant(0, MVT::i32));
1120 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
1121 Op, DAG.getConstant(1, MVT::i32));
1122 Op = DAG.getCopyToReg(SDL.getRoot(), Reg, Lo);
1123 return DAG.getCopyToReg(Op, Reg+1, Hi);
1124 }
Chris Lattner7a60d912005-01-07 07:47:53 +00001125}
1126
Chris Lattner16f64df2005-01-17 17:15:02 +00001127void SelectionDAGISel::
1128LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL,
1129 std::vector<SDOperand> &UnorderedChains) {
1130 // If this is the entry block, emit arguments.
1131 Function &F = *BB->getParent();
Chris Lattnere3c2cf42005-01-17 17:55:19 +00001132 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo;
Chris Lattner6871b232005-10-30 19:42:35 +00001133 SDOperand OldRoot = SDL.DAG.getRoot();
1134 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG);
Chris Lattner16f64df2005-01-17 17:15:02 +00001135
Chris Lattner6871b232005-10-30 19:42:35 +00001136 unsigned a = 0;
1137 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
1138 AI != E; ++AI, ++a)
1139 if (!AI->use_empty()) {
1140 SDL.setValue(AI, Args[a]);
Chris Lattnerd4382f02005-09-13 19:30:54 +00001141
Chris Lattner6871b232005-10-30 19:42:35 +00001142 // If this argument is live outside of the entry block, insert a copy from
1143 // whereever we got it to the vreg that other BB's will reference it as.
1144 if (FuncInfo.ValueMap.count(AI)) {
1145 SDOperand Copy =
1146 CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]);
1147 UnorderedChains.push_back(Copy);
1148 }
Chris Lattnere3c2cf42005-01-17 17:55:19 +00001149 }
Chris Lattner6871b232005-10-30 19:42:35 +00001150
1151 // Next, if the function has live ins that need to be copied into vregs,
1152 // emit the copies now, into the top of the block.
1153 MachineFunction &MF = SDL.DAG.getMachineFunction();
1154 if (MF.livein_begin() != MF.livein_end()) {
1155 SSARegMap *RegMap = MF.getSSARegMap();
1156 const MRegisterInfo &MRI = *MF.getTarget().getRegisterInfo();
1157 for (MachineFunction::livein_iterator LI = MF.livein_begin(),
1158 E = MF.livein_end(); LI != E; ++LI)
1159 if (LI->second)
1160 MRI.copyRegToReg(*MF.begin(), MF.begin()->end(), LI->second,
1161 LI->first, RegMap->getRegClass(LI->second));
Chris Lattner16f64df2005-01-17 17:15:02 +00001162 }
Chris Lattner6871b232005-10-30 19:42:35 +00001163
1164 // Finally, if the target has anything special to do, allow it to do so.
1165 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
Chris Lattner16f64df2005-01-17 17:15:02 +00001166}
1167
1168
Chris Lattner7a60d912005-01-07 07:47:53 +00001169void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
1170 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
1171 FunctionLoweringInfo &FuncInfo) {
1172 SelectionDAGLowering SDL(DAG, TLI, FuncInfo);
Chris Lattner718b5c22005-01-13 17:59:43 +00001173
1174 std::vector<SDOperand> UnorderedChains;
Misha Brukman835702a2005-04-21 22:36:52 +00001175
Chris Lattner6871b232005-10-30 19:42:35 +00001176 // Lower any arguments needed in this block if this is the entry block.
1177 if (LLVMBB == &LLVMBB->getParent()->front())
1178 LowerArguments(LLVMBB, SDL, UnorderedChains);
Chris Lattner7a60d912005-01-07 07:47:53 +00001179
1180 BB = FuncInfo.MBBMap[LLVMBB];
1181 SDL.setCurrentBasicBlock(BB);
1182
1183 // Lower all of the non-terminator instructions.
1184 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
1185 I != E; ++I)
1186 SDL.visit(*I);
1187
1188 // Ensure that all instructions which are used outside of their defining
1189 // blocks are available as virtual registers.
1190 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
Chris Lattner613f79f2005-01-11 22:03:46 +00001191 if (!I->use_empty() && !isa<PHINode>(I)) {
Chris Lattnera2c5d912005-01-09 01:16:24 +00001192 std::map<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
Chris Lattner7a60d912005-01-07 07:47:53 +00001193 if (VMI != FuncInfo.ValueMap.end())
Chris Lattner718b5c22005-01-13 17:59:43 +00001194 UnorderedChains.push_back(
1195 CopyValueToVirtualRegister(SDL, I, VMI->second));
Chris Lattner7a60d912005-01-07 07:47:53 +00001196 }
1197
1198 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to
1199 // ensure constants are generated when needed. Remember the virtual registers
1200 // that need to be added to the Machine PHI nodes as input. We cannot just
1201 // directly add them, because expansion might result in multiple MBB's for one
1202 // BB. As such, the start of the BB might correspond to a different MBB than
1203 // the end.
Misha Brukman835702a2005-04-21 22:36:52 +00001204 //
Chris Lattner7a60d912005-01-07 07:47:53 +00001205
1206 // Emit constants only once even if used by multiple PHI nodes.
1207 std::map<Constant*, unsigned> ConstantsOut;
1208
1209 // Check successor nodes PHI nodes that expect a constant to be available from
1210 // this block.
1211 TerminatorInst *TI = LLVMBB->getTerminator();
1212 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
1213 BasicBlock *SuccBB = TI->getSuccessor(succ);
1214 MachineBasicBlock::iterator MBBI = FuncInfo.MBBMap[SuccBB]->begin();
1215 PHINode *PN;
1216
1217 // At this point we know that there is a 1-1 correspondence between LLVM PHI
1218 // nodes and Machine PHI nodes, but the incoming operands have not been
1219 // emitted yet.
1220 for (BasicBlock::iterator I = SuccBB->begin();
Chris Lattner8ea875f2005-01-07 21:34:19 +00001221 (PN = dyn_cast<PHINode>(I)); ++I)
1222 if (!PN->use_empty()) {
1223 unsigned Reg;
1224 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
1225 if (Constant *C = dyn_cast<Constant>(PHIOp)) {
1226 unsigned &RegOut = ConstantsOut[C];
1227 if (RegOut == 0) {
1228 RegOut = FuncInfo.CreateRegForValue(C);
Chris Lattner718b5c22005-01-13 17:59:43 +00001229 UnorderedChains.push_back(
1230 CopyValueToVirtualRegister(SDL, C, RegOut));
Chris Lattner8ea875f2005-01-07 21:34:19 +00001231 }
1232 Reg = RegOut;
1233 } else {
1234 Reg = FuncInfo.ValueMap[PHIOp];
Chris Lattnera2c5d912005-01-09 01:16:24 +00001235 if (Reg == 0) {
Misha Brukman835702a2005-04-21 22:36:52 +00001236 assert(isa<AllocaInst>(PHIOp) &&
Chris Lattnera2c5d912005-01-09 01:16:24 +00001237 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) &&
1238 "Didn't codegen value into a register!??");
1239 Reg = FuncInfo.CreateRegForValue(PHIOp);
Chris Lattner718b5c22005-01-13 17:59:43 +00001240 UnorderedChains.push_back(
1241 CopyValueToVirtualRegister(SDL, PHIOp, Reg));
Chris Lattnera2c5d912005-01-09 01:16:24 +00001242 }
Chris Lattner7a60d912005-01-07 07:47:53 +00001243 }
Misha Brukman835702a2005-04-21 22:36:52 +00001244
Chris Lattner8ea875f2005-01-07 21:34:19 +00001245 // Remember that this register needs to added to the machine PHI node as
1246 // the input for this MBB.
1247 unsigned NumElements =
1248 TLI.getNumElements(TLI.getValueType(PN->getType()));
1249 for (unsigned i = 0, e = NumElements; i != e; ++i)
1250 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
Chris Lattner7a60d912005-01-07 07:47:53 +00001251 }
Chris Lattner7a60d912005-01-07 07:47:53 +00001252 }
1253 ConstantsOut.clear();
1254
Chris Lattner718b5c22005-01-13 17:59:43 +00001255 // Turn all of the unordered chains into one factored node.
Chris Lattner24516842005-01-13 19:53:14 +00001256 if (!UnorderedChains.empty()) {
Chris Lattnerb7cad902005-11-09 05:03:03 +00001257 SDOperand Root = SDL.getRoot();
1258 if (Root.getOpcode() != ISD::EntryToken) {
1259 unsigned i = 0, e = UnorderedChains.size();
1260 for (; i != e; ++i) {
1261 assert(UnorderedChains[i].Val->getNumOperands() > 1);
1262 if (UnorderedChains[i].Val->getOperand(0) == Root)
1263 break; // Don't add the root if we already indirectly depend on it.
1264 }
1265
1266 if (i == e)
1267 UnorderedChains.push_back(Root);
1268 }
Chris Lattner718b5c22005-01-13 17:59:43 +00001269 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, UnorderedChains));
1270 }
1271
Chris Lattner7a60d912005-01-07 07:47:53 +00001272 // Lower the terminator after the copies are emitted.
1273 SDL.visit(*LLVMBB->getTerminator());
Chris Lattner4108bb02005-01-17 19:43:36 +00001274
1275 // Make sure the root of the DAG is up-to-date.
1276 DAG.setRoot(SDL.getRoot());
Chris Lattner7a60d912005-01-07 07:47:53 +00001277}
1278
1279void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
1280 FunctionLoweringInfo &FuncInfo) {
Chris Lattnerffcb0ae2005-01-23 04:36:26 +00001281 SelectionDAG DAG(TLI, MF);
Chris Lattner7a60d912005-01-07 07:47:53 +00001282 CurDAG = &DAG;
1283 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate;
1284
1285 // First step, lower LLVM code to some DAG. This DAG may use operations and
1286 // types that are not supported by the target.
1287 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo);
1288
Chris Lattnerbcfebeb2005-10-10 16:47:10 +00001289 // Run the DAG combiner in pre-legalize mode.
1290 DAG.Combine(false);
Nate Begeman007c6502005-09-07 00:15:36 +00001291
Chris Lattner7a60d912005-01-07 07:47:53 +00001292 DEBUG(std::cerr << "Lowered selection DAG:\n");
1293 DEBUG(DAG.dump());
1294
1295 // Second step, hack on the DAG until it only uses operations and types that
1296 // the target supports.
Chris Lattnerffcb0ae2005-01-23 04:36:26 +00001297 DAG.Legalize();
Chris Lattner7a60d912005-01-07 07:47:53 +00001298
1299 DEBUG(std::cerr << "Legalized selection DAG:\n");
1300 DEBUG(DAG.dump());
1301
Chris Lattnerbcfebeb2005-10-10 16:47:10 +00001302 // Run the DAG combiner in post-legalize mode.
1303 DAG.Combine(true);
Nate Begeman007c6502005-09-07 00:15:36 +00001304
Chris Lattner6bd8fd02005-10-05 06:09:10 +00001305 if (ViewDAGs) DAG.viewGraph();
1306
Chris Lattner5ca31d92005-03-30 01:10:47 +00001307 // Third, instruction select all of the operations to machine code, adding the
1308 // code to the MachineBasicBlock.
Chris Lattner7a60d912005-01-07 07:47:53 +00001309 InstructionSelectBasicBlock(DAG);
1310
Chris Lattner7a60d912005-01-07 07:47:53 +00001311 DEBUG(std::cerr << "Selected machine code:\n");
1312 DEBUG(BB->dump());
1313
Chris Lattner5ca31d92005-03-30 01:10:47 +00001314 // Next, now that we know what the last MBB the LLVM BB expanded is, update
Chris Lattner7a60d912005-01-07 07:47:53 +00001315 // PHI nodes in successors.
1316 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
1317 MachineInstr *PHI = PHINodesToUpdate[i].first;
1318 assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
1319 "This is not a machine PHI node that we are updating!");
1320 PHI->addRegOperand(PHINodesToUpdate[i].second);
1321 PHI->addMachineBasicBlockOperand(BB);
1322 }
Chris Lattner5ca31d92005-03-30 01:10:47 +00001323
1324 // Finally, add the CFG edges from the last selected MBB to the successor
1325 // MBBs.
1326 TerminatorInst *TI = LLVMBB->getTerminator();
1327 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1328 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[TI->getSuccessor(i)];
1329 BB->addSuccessor(Succ0MBB);
1330 }
Chris Lattner7a60d912005-01-07 07:47:53 +00001331}