From 78ec311bd5fcdf44ed64841a0f5df1124b3a9b17 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Mon, 11 Aug 2003 14:57:33 +0000 Subject: [PATCH] Initial checkin of SelectionDAG implementation. This is still rough and unfinished git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7717 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SelectionDAG/DAGBuilder.cpp | 222 ++++++++++++++++++++++ lib/CodeGen/SelectionDAG/Makefile | 5 + lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 105 ++++++++++ 3 files changed, 332 insertions(+) create mode 100644 lib/CodeGen/SelectionDAG/DAGBuilder.cpp create mode 100644 lib/CodeGen/SelectionDAG/Makefile create mode 100644 lib/CodeGen/SelectionDAG/SelectionDAG.cpp diff --git a/lib/CodeGen/SelectionDAG/DAGBuilder.cpp b/lib/CodeGen/SelectionDAG/DAGBuilder.cpp new file mode 100644 index 00000000000..aafde8ad668 --- /dev/null +++ b/lib/CodeGen/SelectionDAG/DAGBuilder.cpp @@ -0,0 +1,222 @@ +//===-- DAGBuilder.cpp - Turn an LLVM BasicBlock into a DAG for selection -===// +// +// This file turns an LLVM BasicBlock into a target independent SelectionDAG in +// preparation for target specific optimizations and instruction selection. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/SelectionDAG.h" +#include "llvm/Function.h" +#include "llvm/Instructions.h" +#include "llvm/Support/InstVisitor.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Type.h" +#include "llvm/Constants.h" + +struct SelectionDAGBuilder : public InstVisitor { + // DAG - the current dag we are building. + SelectionDAG &DAG; + + // BB - The current machine basic block we are working on. + MachineBasicBlock *BB; + + // CurRoot - The root built for the current basic block. + SelectionDAGNode *CurRoot; + + SelectionDAGBuilder(SelectionDAG &dag) : DAG(dag), BB(0), CurRoot(0) {} + + void visitBB(BasicBlock &bb); + + // Visitation methods for instructions: Create the appropriate DAG nodes for + // the instruction. + void visitAdd(BinaryOperator &BO); + void visitSub(BinaryOperator &BO); + void visitMul(BinaryOperator &BO); + void visitRet(ReturnInst &RI); + + void visitAnd(BinaryOperator &BO); + void visitOr (BinaryOperator &BO); + void visitXor(BinaryOperator &BO); + + void visitInstruction(Instruction &I) { + std::cerr << "Instruction Selection cannot select: " << I; + abort(); + } + +private: + SelectionDAGNode *getNodeFor(Value *V); + SelectionDAGNode *getNodeFor(Value &V) { return getNodeFor(&V); } + + SelectionDAGNode *addSeqNode(SelectionDAGNode *N); +}; + +/// addSeqNode - The same as addNode, but the node is also included in the +/// sequence nodes for this block. This method should be called for any +/// instructions which have a specified sequence they must be evaluated in. +/// +SelectionDAGNode *SelectionDAGBuilder::addSeqNode(SelectionDAGNode *N) { + DAG.addNode(N); // First, add the node to the selection DAG + + if (!CurRoot) + CurRoot = N; + else { + // Create and add a new chain node for the existing root and this node... + CurRoot = DAG.addNode(new SelectionDAGNode(ISD::ChainNode, MVT::isVoid, + BB, CurRoot, N)); + } + return N; +} + +/// getNodeFor - This method returns the SelectionDAGNode for the specified LLVM +/// value, creating a node as necessary. +/// +SelectionDAGNode *SelectionDAGBuilder::getNodeFor(Value *V) { + // If we already have the entry, return it. + SelectionDAGNode*& Entry = DAG.ValueMap[V]; + if (Entry) return Entry; + + // Otherwise, we need to create a node to return now... start by figuring out + // which type the node will be... + MVT::ValueType ValueType = DAG.getValueType(V->getType()); + + if (Instruction *I = dyn_cast(V)) + // Instructions will be filled in later. For now, just create and return a + // dummy node. + return Entry = new SelectionDAGNode(ISD::ProtoNode, ValueType); + + if (Constant *C = dyn_cast(V)) { + if (ConstantBool *CB = dyn_cast(C)) { + Entry = new SelectionDAGNode(ISD::Constant, ValueType); + Entry->addValue(new ReducedValue_Constant_i1(CB->getValue())); + } else if (ConstantInt *CI = dyn_cast(C)) { + Entry = new SelectionDAGNode(ISD::Constant, ValueType); + switch (ValueType) { + case MVT::i8: + Entry->addValue(new ReducedValue_Constant_i8(CI->getRawValue())); + break; + case MVT::i16: + Entry->addValue(new ReducedValue_Constant_i16(CI->getRawValue())); + break; + case MVT::i32: + Entry->addValue(new ReducedValue_Constant_i32(CI->getRawValue())); + break; + case MVT::i64: + Entry->addValue(new ReducedValue_Constant_i64(CI->getRawValue())); + break; + default: + assert(0 && "Invalid ValueType for an integer constant!"); + } + + } else if (ConstantFP *CFP = dyn_cast(C)) { + Entry = new SelectionDAGNode(ISD::Constant, ValueType); + if (ValueType == MVT::f32) + Entry->addValue(new ReducedValue_Constant_f32(CFP->getValue())); + else + Entry->addValue(new ReducedValue_Constant_f64(CFP->getValue())); + } + if (Entry) return Entry; + } + + std::cerr << "Unhandled LLVM value in DAG Builder!: " << *V << "\n"; + abort(); + return 0; +} + + +// visitBB - This method is used to visit a basic block in the program. It +// manages the CurRoot instance variable so that all of the visit(Instruction) +// methods can be written to assume that there is only one basic block being +// constructed. +// +void SelectionDAGBuilder::visitBB(BasicBlock &bb) { + BB = DAG.BlockMap[&bb]; // Update BB instance var + + // Save the current global DAG... + SelectionDAGNode *OldRoot = CurRoot; + CurRoot = 0; + + visit(bb.begin(), bb.end()); // Visit all of the instructions... + + if (OldRoot) { + if (!CurRoot) + CurRoot = OldRoot; // This block had no root of its own.. + else { + // The previous basic block AND this basic block had roots, insert a + // block chain node now... + CurRoot = DAG.addNode(new SelectionDAGNode(ISD::BlockChainNode, + MVT::isVoid, + BB, OldRoot, CurRoot)); + } + } +} + +//===----------------------------------------------------------------------===// +// ...Visitation Methods... +//===----------------------------------------------------------------------===// + +void SelectionDAGBuilder::visitAdd(BinaryOperator &BO) { + getNodeFor(BO)->setNode(ISD::Plus, BB, getNodeFor(BO.getOperand(0)), + getNodeFor(BO.getOperand(1))); +} +void SelectionDAGBuilder::visitSub(BinaryOperator &BO) { + getNodeFor(BO)->setNode(ISD::Minus, BB, getNodeFor(BO.getOperand(0)), + getNodeFor(BO.getOperand(1))); +} +void SelectionDAGBuilder::visitMul(BinaryOperator &BO) { + getNodeFor(BO)->setNode(ISD::Times, BB, getNodeFor(BO.getOperand(0)), + getNodeFor(BO.getOperand(1))); +} + +void SelectionDAGBuilder::visitAnd(BinaryOperator &BO) { + getNodeFor(BO)->setNode(ISD::And, BB, getNodeFor(BO.getOperand(0)), + getNodeFor(BO.getOperand(1))); +} +void SelectionDAGBuilder::visitOr(BinaryOperator &BO) { + getNodeFor(BO)->setNode(ISD::Or, BB, getNodeFor(BO.getOperand(0)), + getNodeFor(BO.getOperand(1))); +} +void SelectionDAGBuilder::visitXor(BinaryOperator &BO) { + getNodeFor(BO)->setNode(ISD::Xor, BB, getNodeFor(BO.getOperand(0)), + getNodeFor(BO.getOperand(1))); +} + +void SelectionDAGBuilder::visitRet(ReturnInst &RI) { + if (RI.getNumOperands()) { // Value return + addSeqNode(new SelectionDAGNode(ISD::Ret, MVT::isVoid, BB, + getNodeFor(RI.getOperand(0)))); + } else { // Void return + addSeqNode(new SelectionDAGNode(ISD::RetVoid, MVT::isVoid, BB)); + } +} + + + + +// SelectionDAG constructor - Just use the SeelectionDAGBuilder to do all of the +// dirty work... +SelectionDAG::SelectionDAG(MachineFunction &f, const TargetMachine &tm, + SelectionDAGTargetBuilder &SDTB) + : F(f), TM(tm) { + + switch (TM.getTargetData().getPointerSize()) { + default: assert(0 && "Unknown pointer size!"); abort(); + case 8: PointerType = MVT::i8; break; + case 16: PointerType = MVT::i16; break; + case 32: PointerType = MVT::i32; break; + case 64: PointerType = MVT::i64; break; + } + + // Create all of the machine basic blocks for the function... building the + // BlockMap. This map is used for PHI node conversion. + const Function &Fn = *F.getFunction(); + for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) + F.getBasicBlockList().push_back(BlockMap[I] = new MachineBasicBlock(I)); + + SDTB.expandArguments(*this, f); + + SelectionDAGBuilder SDB(*this); + for (Function::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) + SDB.visitBB(const_cast(*I)); + Root = SDB.CurRoot; +} diff --git a/lib/CodeGen/SelectionDAG/Makefile b/lib/CodeGen/SelectionDAG/Makefile new file mode 100644 index 00000000000..77fad10f39e --- /dev/null +++ b/lib/CodeGen/SelectionDAG/Makefile @@ -0,0 +1,5 @@ +LEVEL = ../../.. +PARALLEL_DIRS = +LIBRARYNAME = selection + +include $(LEVEL)/Makefile.common diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp new file mode 100644 index 00000000000..181abea9224 --- /dev/null +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -0,0 +1,105 @@ +//===-- SelectionDAG.cpp - Implement the SelectionDAG* classes ------------===// +// +// This file implements the SelectionDAG* classes, which are used to perform +// DAG-based instruction selection in a target-specific manner. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/SelectionDAG.h" +#include "llvm/Type.h" + +SelectionDAG::~SelectionDAG() { + for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) + delete AllNodes[i]; +} + + +/// dump - Print out the current Selection DAG... +void SelectionDAG::dump() const { + Root->dump(); // Print from the root... +} + +/// getValueType - Return the ValueType for the specified LLVM type. This +/// method works on all scalar LLVM types. +/// +MVT::ValueType SelectionDAG::getValueType(const Type *Ty) const { + switch (Ty->getPrimitiveID()) { + case Type::VoidTyID: assert(0 && "Void type object in getValueType!"); + default: assert(0 && "Unknown type in DAGBuilder!\n"); + case Type::BoolTyID: return MVT::i1; + case Type::SByteTyID: + case Type::UByteTyID: return MVT::i8; + case Type::ShortTyID: + case Type::UShortTyID: return MVT::i16; + case Type::IntTyID: + case Type::UIntTyID: return MVT::i32; + case Type::LongTyID: + case Type::ULongTyID: return MVT::i64; + case Type::FloatTyID: return MVT::f32; + case Type::DoubleTyID: return MVT::f64; + case Type::PointerTyID: return PointerType; + } +} + +void SelectionDAGNode::dump() const { + // Print out the DAG in post-order + std::map NodeIDs; + unsigned ID = 0; + printit(0, ID, NodeIDs); +} + +void SelectionDAGNode::printit(unsigned Offset, unsigned &LastID, + std::map &NodeIDs) const { + if (!NodeIDs.count(this)) { + // Emit all of the uses first... + for (unsigned i = 0, e = Uses.size(); i != e; ++i) + Uses[i]->printit(Offset+1, LastID, NodeIDs); + + NodeIDs[this] = LastID++; + + std::cerr << std::string(Offset, ' ') << "#" << LastID-1 << " "; + } else { + // Node has already been emitted... + std::cerr << std::string(Offset, ' ') << "#" << NodeIDs[this] << " "; + } + + switch (ValueType) { + case MVT::isVoid: std::cerr << "V:"; break; + case MVT::i1: std::cerr << "i1:"; break; + case MVT::i8: std::cerr << "i8:"; break; + case MVT::i16: std::cerr << "i16:"; break; + case MVT::i32: std::cerr << "i32:"; break; + case MVT::i64: std::cerr << "i64:"; break; + case MVT::f32: std::cerr << "f32:"; break; + case MVT::f64: std::cerr << "f64:"; break; + default: assert(0 && "Invalid node ValueType!"); + } + switch (NodeType) { + case ISD::ChainNode: std::cerr << "ChainNode"; break; + case ISD::BlockChainNode: std::cerr << "BlockChainNode"; break; + case ISD::ProtoNode: std::cerr << "ProtoNode"; break; + case ISD::Constant: std::cerr << "Constant"; break; + case ISD::FrameIndex: std::cerr << "FrameIndex"; break; + case ISD::Plus: std::cerr << "Plus"; break; + case ISD::Minus: std::cerr << "Minus"; break; + case ISD::Times: std::cerr << "Times"; break; + case ISD::SDiv: std::cerr << "SDiv"; break; + case ISD::UDiv: std::cerr << "UDiv"; break; + case ISD::SRem: std::cerr << "SRem"; break; + case ISD::URem: std::cerr << "URem"; break; + case ISD::And: std::cerr << "And"; break; + case ISD::Or: std::cerr << "Or"; break; + case ISD::Xor: std::cerr << "Xor"; break; + case ISD::Br: std::cerr << "Br"; break; + case ISD::Switch: std::cerr << "Switch"; break; + case ISD::Ret: std::cerr << "Ret"; break; + case ISD::RetVoid: std::cerr << "RetVoid"; break; + case ISD::Load: std::cerr << "Load"; break; + case ISD::Store: std::cerr << "Store"; break; + case ISD::PHI: std::cerr << "PHI"; break; + case ISD::Call: std::cerr << "Call"; break; + } + + std::cerr << "\n"; +} -- 2.34.1