1 //===-- DAGBuilder.cpp - Turn an LLVM BasicBlock into a DAG for selection -===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file turns an LLVM BasicBlock into a target independent SelectionDAG in
11 // preparation for target specific optimizations and instruction selection.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/CodeGen/SelectionDAG.h"
16 #include "llvm/Constants.h"
17 #include "llvm/Function.h"
18 #include "llvm/Instructions.h"
19 #include "llvm/Type.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/Target/TargetMachine.h"
22 #include "llvm/Support/InstVisitor.h"
26 struct SelectionDAGBuilder : public InstVisitor<SelectionDAGBuilder> {
27 // DAG - the current dag we are building.
30 // SDTB - The target-specific builder interface, which indicates how to expand
31 // extremely target-specific aspects of the representation, such as function
32 // calls and arguments.
33 SelectionDAGTargetBuilder &SDTB;
35 // BB - The current machine basic block we are working on.
36 MachineBasicBlock *BB;
38 // CurRoot - The root built for the current basic block.
39 SelectionDAGNode *CurRoot;
41 SelectionDAGBuilder(SelectionDAG &dag, SelectionDAGTargetBuilder &sdtb)
42 : DAG(dag), SDTB(sdtb), BB(0), CurRoot(0) {}
44 void visitBB(BasicBlock &bb);
46 // Visitation methods for instructions: Create the appropriate DAG nodes for
48 void visitAdd(BinaryOperator &BO);
49 void visitSub(BinaryOperator &BO);
50 void visitMul(BinaryOperator &BO);
52 void visitAnd(BinaryOperator &BO);
53 void visitOr (BinaryOperator &BO);
54 void visitXor(BinaryOperator &BO);
56 void visitSetEQ(BinaryOperator &BO);
58 void visitLoad(LoadInst &LI);
59 void visitCall(CallInst &CI);
61 void visitBr(BranchInst &BI);
62 void visitRet(ReturnInst &RI);
64 void visitInstruction(Instruction &I) {
65 std::cerr << "DAGBuilder: Cannot instruction select: " << I;
70 SelectionDAGNode *getNodeFor(Value *V);
71 SelectionDAGNode *getNodeFor(Value &V) { return getNodeFor(&V); }
73 SelectionDAGNode *addSeqNode(SelectionDAGNode *N);
76 /// addSeqNode - The same as addNode, but the node is also included in the
77 /// sequence nodes for this block. This method should be called for any
78 /// instructions which have a specified sequence they must be evaluated in.
80 SelectionDAGNode *SelectionDAGBuilder::addSeqNode(SelectionDAGNode *N) {
81 DAG.addNode(N); // First, add the node to the selection DAG
86 // Create and add a new chain node for the existing root and this node...
87 CurRoot = DAG.addNode(new SelectionDAGNode(ISD::ChainNode, MVT::isVoid,
93 /// getNodeFor - This method returns the SelectionDAGNode for the specified LLVM
94 /// value, creating a node as necessary.
96 SelectionDAGNode *SelectionDAGBuilder::getNodeFor(Value *V) {
97 // If we already have the entry, return it.
98 SelectionDAGNode*& Entry = DAG.ValueMap[V];
99 if (Entry) return Entry;
101 // Otherwise, we need to create a node to return now... start by figuring out
102 // which type the node will be...
103 MVT::ValueType ValueType = DAG.getValueType(V->getType());
105 if (Instruction *I = dyn_cast<Instruction>(V))
106 // Instructions will be filled in later. For now, just create and return a
108 return Entry = new SelectionDAGNode(ISD::ProtoNode, ValueType);
110 if (Constant *C = dyn_cast<Constant>(V)) {
111 if (ConstantBool *CB = dyn_cast<ConstantBool>(C)) {
112 Entry = new SelectionDAGNode(ISD::Constant, ValueType);
113 Entry->addValue(new ReducedValue_Constant_i1(CB->getValue()));
114 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
115 Entry = new SelectionDAGNode(ISD::Constant, ValueType);
118 Entry->addValue(new ReducedValue_Constant_i8(CI->getRawValue()));
121 Entry->addValue(new ReducedValue_Constant_i16(CI->getRawValue()));
124 Entry->addValue(new ReducedValue_Constant_i32(CI->getRawValue()));
127 Entry->addValue(new ReducedValue_Constant_i64(CI->getRawValue()));
130 assert(0 && "Invalid ValueType for an integer constant!");
133 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
134 Entry = new SelectionDAGNode(ISD::Constant, ValueType);
135 if (ValueType == MVT::f32)
136 Entry->addValue(new ReducedValue_Constant_f32(CFP->getValue()));
138 Entry->addValue(new ReducedValue_Constant_f64(CFP->getValue()));
140 if (Entry) return Entry;
141 } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
142 Entry = new SelectionDAGNode(ISD::BasicBlock, ValueType);
143 Entry->addValue(new ReducedValue_BasicBlock_i32(DAG.BlockMap[BB]));
147 std::cerr << "Unhandled LLVM value in DAG Builder!: " << *V << "\n";
153 // visitBB - This method is used to visit a basic block in the program. It
154 // manages the CurRoot instance variable so that all of the visit(Instruction)
155 // methods can be written to assume that there is only one basic block being
158 void SelectionDAGBuilder::visitBB(BasicBlock &bb) {
159 BB = DAG.BlockMap[&bb]; // Update BB instance var
161 // Save the current global DAG...
162 SelectionDAGNode *OldRoot = CurRoot;
165 visit(bb.begin(), bb.end()); // Visit all of the instructions...
169 CurRoot = OldRoot; // This block had no root of its own..
171 // The previous basic block AND this basic block had roots, insert a
172 // block chain node now...
173 CurRoot = DAG.addNode(new SelectionDAGNode(ISD::BlockChainNode,
175 BB, OldRoot, CurRoot));
180 //===----------------------------------------------------------------------===//
181 // ...Visitation Methods...
182 //===----------------------------------------------------------------------===//
184 void SelectionDAGBuilder::visitAdd(BinaryOperator &BO) {
185 getNodeFor(BO)->setNode(ISD::Plus, BB, getNodeFor(BO.getOperand(0)),
186 getNodeFor(BO.getOperand(1)));
188 void SelectionDAGBuilder::visitSub(BinaryOperator &BO) {
189 getNodeFor(BO)->setNode(ISD::Minus, BB, getNodeFor(BO.getOperand(0)),
190 getNodeFor(BO.getOperand(1)));
192 void SelectionDAGBuilder::visitMul(BinaryOperator &BO) {
193 getNodeFor(BO)->setNode(ISD::Times, BB, getNodeFor(BO.getOperand(0)),
194 getNodeFor(BO.getOperand(1)));
197 void SelectionDAGBuilder::visitAnd(BinaryOperator &BO) {
198 getNodeFor(BO)->setNode(ISD::And, BB, getNodeFor(BO.getOperand(0)),
199 getNodeFor(BO.getOperand(1)));
201 void SelectionDAGBuilder::visitOr(BinaryOperator &BO) {
202 getNodeFor(BO)->setNode(ISD::Or, BB, getNodeFor(BO.getOperand(0)),
203 getNodeFor(BO.getOperand(1)));
205 void SelectionDAGBuilder::visitXor(BinaryOperator &BO) {
206 getNodeFor(BO)->setNode(ISD::Xor, BB, getNodeFor(BO.getOperand(0)),
207 getNodeFor(BO.getOperand(1)));
209 void SelectionDAGBuilder::visitSetEQ(BinaryOperator &BO) {
210 getNodeFor(BO)->setNode(ISD::SetEQ, BB, getNodeFor(BO.getOperand(0)),
211 getNodeFor(BO.getOperand(1)));
215 void SelectionDAGBuilder::visitRet(ReturnInst &RI) {
216 if (RI.getNumOperands()) { // Value return
217 addSeqNode(new SelectionDAGNode(ISD::Ret, MVT::isVoid, BB,
218 getNodeFor(RI.getOperand(0))));
219 } else { // Void return
220 addSeqNode(new SelectionDAGNode(ISD::RetVoid, MVT::isVoid, BB));
225 void SelectionDAGBuilder::visitBr(BranchInst &BI) {
226 if (BI.isUnconditional())
227 addSeqNode(new SelectionDAGNode(ISD::Br, MVT::isVoid, BB,
228 getNodeFor(BI.getOperand(0))));
230 addSeqNode(new SelectionDAGNode(ISD::BrCond, MVT::isVoid, BB,
231 getNodeFor(BI.getCondition()),
232 getNodeFor(BI.getSuccessor(0)),
233 getNodeFor(BI.getSuccessor(1))));
237 void SelectionDAGBuilder::visitLoad(LoadInst &LI) {
238 // FIXME: this won't prevent reordering of loads!
239 getNodeFor(LI)->setNode(ISD::Load, BB, getNodeFor(LI.getOperand(0)));
242 void SelectionDAGBuilder::visitCall(CallInst &CI) {
243 SDTB.expandCall(DAG, CI);
248 // SelectionDAG constructor - Just use the SelectionDAGBuilder to do all of the
250 SelectionDAG::SelectionDAG(MachineFunction &f, const TargetMachine &tm,
251 SelectionDAGTargetBuilder &SDTB)
254 switch (TM.getTargetData().getPointerSize()) {
255 default: assert(0 && "Unknown pointer size!"); abort();
256 case 8: PointerType = MVT::i8; break;
257 case 16: PointerType = MVT::i16; break;
258 case 32: PointerType = MVT::i32; break;
259 case 64: PointerType = MVT::i64; break;
262 // Create all of the machine basic blocks for the function... building the
263 // BlockMap. This map is used for PHI node conversion.
264 const Function &Fn = *F.getFunction();
265 for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
266 F.getBasicBlockList().push_back(BlockMap[I] = new MachineBasicBlock(I));
268 SDTB.expandArguments(*this);
270 SelectionDAGBuilder SDB(*this, SDTB);
271 for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
272 SDB.visitBB(const_cast<BasicBlock&>(*I));
276 } // End llvm namespace