From d70cee2d5aba9c049af3109abcaa842e165a6164 Mon Sep 17 00:00:00 2001 From: Tanya Lattner Date: Fri, 17 Jun 2005 04:16:14 +0000 Subject: [PATCH] Special dep graph for SMS for superblocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@22242 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../SparcV9/ModuloScheduling/MSchedGraphSB.h | 410 ++++++++++++++++++ 1 file changed, 410 insertions(+) create mode 100644 lib/Target/SparcV9/ModuloScheduling/MSchedGraphSB.h diff --git a/lib/Target/SparcV9/ModuloScheduling/MSchedGraphSB.h b/lib/Target/SparcV9/ModuloScheduling/MSchedGraphSB.h new file mode 100644 index 00000000000..bea72026a06 --- /dev/null +++ b/lib/Target/SparcV9/ModuloScheduling/MSchedGraphSB.h @@ -0,0 +1,410 @@ +//===-- MSchedGraphSB.h - Scheduling Graph ------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// A graph class for dependencies. This graph only contains true, anti, and +// output data dependencies for a vector of MachineBasicBlock. Dependencies +// across iterations are also computed. Unless data dependence analysis +// is provided, a conservative approach of adding dependencies between all +// loads and stores is taken. It also includes pseudo predicate nodes for +// modulo scheduling superblocks. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_MSCHEDGRAPHSB_H +#define LLVM_MSCHEDGRAPHSB_H +#include "DependenceAnalyzer.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetData.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/iterator" +#include + + +namespace llvm { + + class MSchedGraphSB; + class MSchedGraphSBNode; + template + class MSchedGraphSBNodeIterator; + + //MSchedGraphSBEdge encapsulates the data dependence between nodes. It + //identifies the dependence type, on what, and the iteration + //difference + struct MSchedGraphSBEdge { + enum DataDepOrderType { + TrueDep, AntiDep, OutputDep, NonDataDep + }; + + enum MSchedGraphSBEdgeType { + MemoryDep, ValueDep, MachineRegister, PredDep + }; + + //Get or set edge data + MSchedGraphSBNode *getDest() const { return dest; } + unsigned getIteDiff() { return iteDiff; } + unsigned getDepOrderType() { return depOrderType; } + void setDest(MSchedGraphSBNode *newDest) { dest = newDest; } + + private: + friend class MSchedGraphSBNode; + MSchedGraphSBEdge(MSchedGraphSBNode *destination, MSchedGraphSBEdgeType type, + unsigned deptype, unsigned diff) + : dest(destination), depType(type), depOrderType(deptype), iteDiff(diff) {} + + MSchedGraphSBNode *dest; + MSchedGraphSBEdgeType depType; + unsigned depOrderType; + unsigned iteDiff; + }; + + //MSchedGraphSBNode represents a machine instruction and its + //corresponding latency. Each node also contains a list of its + //predecessors and sucessors. + class MSchedGraphSBNode { + + const MachineInstr* Inst; //Machine Instruction + std::vector otherInstrs; + + MSchedGraphSB* Parent; //Graph this node belongs to + unsigned index; //Index in BB + unsigned latency; //Latency of Instruction + bool isBranchInstr; //Is this node the branch instr or not + bool isPredicateNode; //Indicate if this node should be treated like a predicate + + std::vector Predecessors; //Predecessor Nodes + std::vector Successors; //Successor edges + + public: + MSchedGraphSBNode(const MachineInstr* inst, MSchedGraphSB *graph, + unsigned index, unsigned late=0, bool isBranch=false); + MSchedGraphSBNode(const MachineInstr* inst, std::vector &other, + MSchedGraphSB *graph, + unsigned index, unsigned late=0, bool isPNode=true); + MSchedGraphSBNode(const MSchedGraphSBNode &N); + + //Iterators - Predecessor and Succussor + typedef std::vector::iterator pred_iterator; + pred_iterator pred_begin() { return Predecessors.begin(); } + pred_iterator pred_end() { return Predecessors.end(); } + unsigned pred_size() { return Predecessors.size(); } + + typedef std::vector::const_iterator pred_const_iterator; + pred_const_iterator pred_begin() const { return Predecessors.begin(); } + pred_const_iterator pred_end() const { return Predecessors.end(); } + + typedef MSchedGraphSBNodeIterator::const_iterator, + const MSchedGraphSBNode> succ_const_iterator; + succ_const_iterator succ_begin() const; + succ_const_iterator succ_end() const; + + typedef MSchedGraphSBNodeIterator::iterator, + MSchedGraphSBNode> succ_iterator; + succ_iterator succ_begin(); + succ_iterator succ_end(); + unsigned succ_size() { return Successors.size(); } + + //Get or set predecessor nodes, or successor edges + void setPredecessor(unsigned index, MSchedGraphSBNode *dest) { + Predecessors[index] = dest; + } + + MSchedGraphSBNode* getPredecessor(unsigned index) { + return Predecessors[index]; + } + + MSchedGraphSBEdge* getSuccessor(unsigned index) { + return &Successors[index]; + } + + void deleteSuccessor(MSchedGraphSBNode *node) { + for (unsigned i = 0; i != Successors.size(); ++i) + if (Successors[i].getDest() == node) { + Successors.erase(Successors.begin()+i); + node->Predecessors.erase(std::find(node->Predecessors.begin(), + node->Predecessors.end(), this)); + --i; //Decrease index var since we deleted a node + } + } + + void addOutEdge(MSchedGraphSBNode *destination, + MSchedGraphSBEdge::MSchedGraphSBEdgeType type, + unsigned deptype, unsigned diff=0) { + Successors.push_back(MSchedGraphSBEdge(destination, type, deptype,diff)); + destination->Predecessors.push_back(this); + } + + //General methods to get and set data for the node + const MachineInstr* getInst() { return Inst; } + MSchedGraphSB* getParent() { return Parent; } + bool hasPredecessors() { return (Predecessors.size() > 0); } + bool hasSuccessors() { return (Successors.size() > 0); } + unsigned getLatency() { return latency; } + unsigned getLatency() const { return latency; } + unsigned getIndex() { return index; } + unsigned getIteDiff(MSchedGraphSBNode *succ); + MSchedGraphSBEdge getInEdge(MSchedGraphSBNode *pred); + unsigned getInEdgeNum(MSchedGraphSBNode *pred); + bool isSuccessor(MSchedGraphSBNode *); + bool isPredecessor(MSchedGraphSBNode *); + bool isBranch() { return isBranchInstr; } + bool isPredicate() { return isPredicateNode; } + bool isPredicate() const { return isPredicateNode; } + std::vector getOtherInstrs() { return otherInstrs; } + + //Debug support + void print(std::ostream &os) const; + void setParent(MSchedGraphSB *p) { Parent = p; } + }; + + //Node iterator for graph generation + template + class MSchedGraphSBNodeIterator : public forward_iterator { + IteratorType I; // std::vector::iterator or const_iterator + public: + MSchedGraphSBNodeIterator(IteratorType i) : I(i) {} + + bool operator==(const MSchedGraphSBNodeIterator RHS) const { return I == RHS.I; } + bool operator!=(const MSchedGraphSBNodeIterator RHS) const { return I != RHS.I; } + + const MSchedGraphSBNodeIterator &operator=(const MSchedGraphSBNodeIterator &RHS) { + I = RHS.I; + return *this; + } + + NodeType* operator*() const { + return I->getDest(); + } + NodeType* operator->() const { return operator*(); } + + MSchedGraphSBNodeIterator& operator++() { // Preincrement + ++I; + return *this; + } + MSchedGraphSBNodeIterator operator++(int) { // Postincrement + MSchedGraphSBNodeIterator tmp = *this; ++*this; return tmp; + } + + MSchedGraphSBEdge &getEdge() { + return *I; + } + const MSchedGraphSBEdge &getEdge() const { + return *I; + } + }; + + inline MSchedGraphSBNode::succ_const_iterator MSchedGraphSBNode::succ_begin() const { + return succ_const_iterator(Successors.begin()); + } + inline MSchedGraphSBNode::succ_const_iterator MSchedGraphSBNode::succ_end() const { + return succ_const_iterator(Successors.end()); + } + inline MSchedGraphSBNode::succ_iterator MSchedGraphSBNode::succ_begin() { + return succ_iterator(Successors.begin()); + } + inline MSchedGraphSBNode::succ_iterator MSchedGraphSBNode::succ_end() { + return succ_iterator(Successors.end()); + } + + // ostream << operator for MSGraphNode class + inline std::ostream &operator<<(std::ostream &os, + const MSchedGraphSBNode &node) { + node.print(os); + return os; + } + + + // Provide specializations of GraphTraits to be able to use graph + // iterators on the scheduling graph! + // + template <> struct GraphTraits { + typedef MSchedGraphSBNode NodeType; + typedef MSchedGraphSBNode::succ_iterator ChildIteratorType; + + static inline ChildIteratorType child_begin(NodeType *N) { + return N->succ_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->succ_end(); + } + + static NodeType *getEntryNode(NodeType* N) { return N; } + }; + + + + //Graph class to represent dependence graph + class MSchedGraphSB { + + std::vector BBs; //Machine basic block + const TargetMachine &Target; //Target Machine + + //Nodes + std::map GraphMap; + + //Add Nodes and Edges to this graph for our BB + typedef std::pair OpIndexNodePair; + void buildNodesAndEdges(std::map &ignoreInstrs, DependenceAnalyzer &DA, std::map &machineTollvm, std::map > &liveOutsideTrace); + void addValueEdges(std::vector &NodesInMap, + MSchedGraphSBNode *node, + bool nodeIsUse, bool nodeIsDef, std::vector &phiInstrs, int diff=0); + void addMachRegEdges(std::map >& regNumtoNodeMap); + void addMemEdges(const std::vector& memInst, + DependenceAnalyzer &DA, std::map &machineTollvm); + + + bool instrCauseException(MachineOpCode opCode); + + public: + MSchedGraphSB(const MachineBasicBlock *bb, const TargetMachine &targ, + std::map &ignoreInstrs, + DependenceAnalyzer &DA, std::map &machineTollvm); + + //Copy constructor with maps to link old nodes to new nodes + MSchedGraphSB(const MSchedGraphSB &G, std::map &newNodes); + + MSchedGraphSB(std::vector &bbs, + const TargetMachine &targ, + std::map &ignoreInstrs, + DependenceAnalyzer &DA, + std::map &machineTollvm); + + //Print graph + void print(std::ostream &os) const; + + //Deconstructor! + ~MSchedGraphSB(); + + //Add or delete nodes from the Graph + void addNode(const MachineInstr* MI, MSchedGraphSBNode *node); + void deleteNode(MSchedGraphSBNode *node); + int totalDelay(); + + //iterators + typedef std::map::iterator iterator; + typedef std::map::const_iterator const_iterator; + typedef std::map::reverse_iterator reverse_iterator; + iterator find(const MachineInstr* I) { return GraphMap.find(I); } + iterator end() { return GraphMap.end(); } + iterator begin() { return GraphMap.begin(); } + unsigned size() { return GraphMap.size(); } + reverse_iterator rbegin() { return GraphMap.rbegin(); } + reverse_iterator rend() { return GraphMap.rend(); } + + //Get Target or original machine basic block + const TargetMachine* getTarget() { return &Target; } + std::vector getBBs() { return BBs; } + }; + + + + + + // Provide specializations of GraphTraits to be able to use graph + // iterators on the scheduling graph + static MSchedGraphSBNode& getSecond(std::pair &Pair) { + return *Pair.second; + } + + template <> struct GraphTraits { + typedef MSchedGraphSBNode NodeType; + typedef MSchedGraphSBNode::succ_iterator ChildIteratorType; + + static inline ChildIteratorType child_begin(NodeType *N) { + return N->succ_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->succ_end(); + } + + typedef std::pointer_to_unary_function&, MSchedGraphSBNode&> DerefFun; + + typedef mapped_iterator nodes_iterator; + static nodes_iterator nodes_begin(MSchedGraphSB *G) { + return map_iterator(((MSchedGraphSB*)G)->begin(), DerefFun(getSecond)); + } + static nodes_iterator nodes_end(MSchedGraphSB *G) { + return map_iterator(((MSchedGraphSB*)G)->end(), DerefFun(getSecond)); + } + + }; + + template <> struct GraphTraits { + typedef const MSchedGraphSBNode NodeType; + typedef MSchedGraphSBNode::succ_const_iterator ChildIteratorType; + + static inline ChildIteratorType child_begin(NodeType *N) { + return N->succ_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->succ_end(); + } + typedef std::pointer_to_unary_function&, MSchedGraphSBNode&> DerefFun; + + typedef mapped_iterator nodes_iterator; + static nodes_iterator nodes_begin(MSchedGraphSB *G) { + return map_iterator(((MSchedGraphSB*)G)->begin(), DerefFun(getSecond)); + } + static nodes_iterator nodes_end(MSchedGraphSB *G) { + return map_iterator(((MSchedGraphSB*)G)->end(), DerefFun(getSecond)); + } + }; + + template <> struct GraphTraits > { + typedef MSchedGraphSBNode NodeType; + typedef MSchedGraphSBNode::pred_iterator ChildIteratorType; + + static inline ChildIteratorType child_begin(NodeType *N) { + return N->pred_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->pred_end(); + } + typedef std::pointer_to_unary_function&, MSchedGraphSBNode&> DerefFun; + + typedef mapped_iterator nodes_iterator; + static nodes_iterator nodes_begin(MSchedGraphSB *G) { + return map_iterator(((MSchedGraphSB*)G)->begin(), DerefFun(getSecond)); + } + static nodes_iterator nodes_end(MSchedGraphSB *G) { + return map_iterator(((MSchedGraphSB*)G)->end(), DerefFun(getSecond)); + } + }; + + template <> struct GraphTraits > { + typedef const MSchedGraphSBNode NodeType; + typedef MSchedGraphSBNode::pred_const_iterator ChildIteratorType; + + static inline ChildIteratorType child_begin(NodeType *N) { + return N->pred_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->pred_end(); + } + + typedef std::pointer_to_unary_function&, MSchedGraphSBNode&> DerefFun; + + typedef mapped_iterator nodes_iterator; + static nodes_iterator nodes_begin(MSchedGraphSB *G) { + return map_iterator(((MSchedGraphSB*)G)->begin(), DerefFun(getSecond)); + } + static nodes_iterator nodes_end(MSchedGraphSB *G) { + return map_iterator(((MSchedGraphSB*)G)->end(), DerefFun(getSecond)); + } + }; +} + +#endif -- 2.34.1