LLVM API Documentation

MSchedGraphSB.h

Go to the documentation of this file.
00001 //===-- MSchedGraphSB.h - Scheduling Graph ------------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // A graph class for dependencies. This graph only contains true, anti, and
00011 // output data dependencies for a vector of MachineBasicBlock. Dependencies
00012 // across iterations are also computed. Unless data dependence analysis
00013 // is provided, a conservative approach of adding dependencies between all
00014 // loads and stores is taken. It also includes pseudo predicate nodes for
00015 // modulo scheduling superblocks.
00016 //===----------------------------------------------------------------------===//
00017 
00018 #ifndef LLVM_MSCHEDGRAPHSB_H
00019 #define LLVM_MSCHEDGRAPHSB_H
00020 #include "DependenceAnalyzer.h"
00021 #include "llvm/Analysis/AliasAnalysis.h"
00022 #include "llvm/CodeGen/MachineInstr.h"
00023 #include "llvm/Target/TargetMachine.h"
00024 #include "llvm/Target/TargetData.h"
00025 #include "llvm/ADT/GraphTraits.h"
00026 #include "llvm/ADT/STLExtras.h"
00027 #include "llvm/ADT/iterator"
00028 #include <vector>
00029 
00030 
00031 namespace llvm {
00032 
00033   class MSchedGraphSB;
00034   class MSchedGraphSBNode;
00035   template<class IteratorType, class NodeType>
00036   class MSchedGraphSBNodeIterator;
00037 
00038   //MSchedGraphSBEdge encapsulates the data dependence between nodes. It
00039   //identifies the dependence type, on what, and the iteration
00040   //difference
00041   struct MSchedGraphSBEdge {
00042     enum DataDepOrderType {
00043       TrueDep, AntiDep, OutputDep, NonDataDep
00044     };
00045 
00046     enum MSchedGraphSBEdgeType {
00047       MemoryDep, ValueDep, MachineRegister, PredDep
00048     };
00049 
00050     //Get or set edge data
00051     MSchedGraphSBNode *getDest() const { return dest; }
00052     unsigned getIteDiff() { return iteDiff; }
00053     unsigned getDepOrderType() { return depOrderType; }
00054     void setDest(MSchedGraphSBNode *newDest) { dest = newDest; }
00055 
00056   private:
00057     friend class MSchedGraphSBNode;
00058     MSchedGraphSBEdge(MSchedGraphSBNode *destination, MSchedGraphSBEdgeType type,
00059                     unsigned deptype, unsigned diff)
00060       : dest(destination), depType(type), depOrderType(deptype), iteDiff(diff) {}
00061 
00062     MSchedGraphSBNode *dest;
00063     MSchedGraphSBEdgeType depType;
00064     unsigned depOrderType;
00065     unsigned iteDiff;
00066   };
00067 
00068   //MSchedGraphSBNode represents a machine instruction and its
00069   //corresponding latency. Each node also contains a list of its
00070   //predecessors and sucessors.
00071   class MSchedGraphSBNode {
00072 
00073     const MachineInstr* Inst; //Machine Instruction
00074     std::vector<const MachineInstr*> otherInstrs;
00075 
00076     MSchedGraphSB* Parent; //Graph this node belongs to
00077     unsigned index; //Index in BB
00078     unsigned latency; //Latency of Instruction
00079     bool isBranchInstr; //Is this node the branch instr or not
00080     bool isPredicateNode; //Indicate if this node should be treated like a predicate
00081 
00082     std::vector<MSchedGraphSBNode*> Predecessors; //Predecessor Nodes
00083     std::vector<MSchedGraphSBEdge> Successors; //Successor edges
00084 
00085   public:
00086     MSchedGraphSBNode(const MachineInstr* inst, MSchedGraphSB *graph,
00087                     unsigned index, unsigned late=0, bool isBranch=false);
00088     MSchedGraphSBNode(const MachineInstr* inst, std::vector<const MachineInstr*> &other,
00089                       MSchedGraphSB *graph,
00090                       unsigned index, unsigned late=0, bool isPNode=true);
00091     MSchedGraphSBNode(const MSchedGraphSBNode &N);
00092 
00093     //Iterators - Predecessor and Succussor
00094     typedef std::vector<MSchedGraphSBNode*>::iterator pred_iterator;
00095     pred_iterator pred_begin() { return Predecessors.begin(); }
00096     pred_iterator pred_end() { return Predecessors.end(); }
00097     unsigned pred_size() { return Predecessors.size(); }
00098 
00099     typedef std::vector<MSchedGraphSBNode*>::const_iterator pred_const_iterator;
00100     pred_const_iterator pred_begin() const { return Predecessors.begin(); }
00101     pred_const_iterator pred_end() const { return Predecessors.end(); }
00102 
00103     typedef MSchedGraphSBNodeIterator<std::vector<MSchedGraphSBEdge>::const_iterator,
00104                                     const MSchedGraphSBNode> succ_const_iterator;
00105     succ_const_iterator succ_begin() const;
00106     succ_const_iterator succ_end() const;
00107 
00108     typedef MSchedGraphSBNodeIterator<std::vector<MSchedGraphSBEdge>::iterator,
00109                                     MSchedGraphSBNode> succ_iterator;
00110     succ_iterator succ_begin();
00111     succ_iterator succ_end();
00112     unsigned succ_size() { return Successors.size(); }
00113 
00114     //Get or set predecessor nodes, or successor edges
00115     void setPredecessor(unsigned index, MSchedGraphSBNode *dest) {
00116       Predecessors[index] = dest;
00117     }
00118 
00119     MSchedGraphSBNode* getPredecessor(unsigned index) {
00120       return Predecessors[index];
00121     }
00122 
00123     MSchedGraphSBEdge* getSuccessor(unsigned index) {
00124       return &Successors[index];
00125     }
00126 
00127     void deleteSuccessor(MSchedGraphSBNode *node) {
00128       for (unsigned i = 0; i != Successors.size(); ++i)
00129         if (Successors[i].getDest() == node) {
00130           Successors.erase(Successors.begin()+i);
00131           node->Predecessors.erase(std::find(node->Predecessors.begin(),
00132                                              node->Predecessors.end(), this));
00133           --i; //Decrease index var since we deleted a node
00134         }
00135     }
00136 
00137     void addOutEdge(MSchedGraphSBNode *destination,
00138                     MSchedGraphSBEdge::MSchedGraphSBEdgeType type,
00139                     unsigned deptype, unsigned diff=0) {
00140       Successors.push_back(MSchedGraphSBEdge(destination, type, deptype,diff));
00141       destination->Predecessors.push_back(this);
00142     }
00143 
00144     //General methods to get and set data for the node
00145     const MachineInstr* getInst() { return Inst; }
00146     MSchedGraphSB* getParent() { return Parent; }
00147     bool hasPredecessors() { return (Predecessors.size() > 0); }
00148     bool hasSuccessors() { return (Successors.size() > 0); }
00149     unsigned getLatency() { return latency; }
00150     unsigned getLatency() const { return latency; }
00151     unsigned getIndex() { return index; }
00152     unsigned getIteDiff(MSchedGraphSBNode *succ);
00153     MSchedGraphSBEdge getInEdge(MSchedGraphSBNode *pred);
00154     unsigned getInEdgeNum(MSchedGraphSBNode *pred);
00155     bool isSuccessor(MSchedGraphSBNode *);
00156     bool isPredecessor(MSchedGraphSBNode *);
00157     bool isBranch() { return isBranchInstr; }
00158     bool isPredicate() { return isPredicateNode; }
00159     bool isPredicate() const { return isPredicateNode; }
00160     std::vector<const MachineInstr*> getOtherInstrs() { return otherInstrs; }
00161 
00162     //Debug support
00163     void print(std::ostream &os) const;
00164     void setParent(MSchedGraphSB *p) { Parent = p; }
00165   };
00166 
00167   //Node iterator for graph generation
00168   template<class IteratorType, class NodeType>
00169   class MSchedGraphSBNodeIterator : public forward_iterator<NodeType*, ptrdiff_t> {
00170     IteratorType I;   // std::vector<MSchedGraphSBEdge>::iterator or const_iterator
00171   public:
00172     MSchedGraphSBNodeIterator(IteratorType i) : I(i) {}
00173 
00174     bool operator==(const MSchedGraphSBNodeIterator RHS) const { return I == RHS.I; }
00175     bool operator!=(const MSchedGraphSBNodeIterator RHS) const { return I != RHS.I; }
00176 
00177     const MSchedGraphSBNodeIterator &operator=(const MSchedGraphSBNodeIterator &RHS) {
00178       I = RHS.I;
00179       return *this;
00180     }
00181 
00182     NodeType* operator*() const {
00183       return I->getDest();
00184     }
00185     NodeType* operator->() const { return operator*(); }
00186 
00187     MSchedGraphSBNodeIterator& operator++() {                // Preincrement
00188       ++I;
00189       return *this;
00190     }
00191     MSchedGraphSBNodeIterator operator++(int) { // Postincrement
00192       MSchedGraphSBNodeIterator tmp = *this; ++*this; return tmp;
00193     }
00194 
00195     MSchedGraphSBEdge &getEdge() {
00196       return *I;
00197     }
00198     const MSchedGraphSBEdge &getEdge() const {
00199       return *I;
00200     }
00201   };
00202 
00203   inline MSchedGraphSBNode::succ_const_iterator MSchedGraphSBNode::succ_begin() const {
00204     return succ_const_iterator(Successors.begin());
00205   }
00206   inline MSchedGraphSBNode::succ_const_iterator MSchedGraphSBNode::succ_end() const {
00207     return succ_const_iterator(Successors.end());
00208   }
00209   inline MSchedGraphSBNode::succ_iterator MSchedGraphSBNode::succ_begin() {
00210     return succ_iterator(Successors.begin());
00211   }
00212   inline MSchedGraphSBNode::succ_iterator MSchedGraphSBNode::succ_end() {
00213     return succ_iterator(Successors.end());
00214   }
00215 
00216   // ostream << operator for MSGraphNode class
00217   inline std::ostream &operator<<(std::ostream &os,
00218                                   const MSchedGraphSBNode &node) {
00219     node.print(os);
00220     return os;
00221   }
00222 
00223 
00224   // Provide specializations of GraphTraits to be able to use graph
00225   // iterators on the scheduling graph!
00226   //
00227   template <> struct GraphTraits<MSchedGraphSBNode*> {
00228     typedef MSchedGraphSBNode NodeType;
00229     typedef MSchedGraphSBNode::succ_iterator ChildIteratorType;
00230 
00231     static inline ChildIteratorType child_begin(NodeType *N) {
00232       return N->succ_begin();
00233     }
00234     static inline ChildIteratorType child_end(NodeType *N) {
00235       return N->succ_end();
00236     }
00237 
00238     static NodeType *getEntryNode(NodeType* N) { return N; }
00239   };
00240 
00241 
00242 
00243   //Graph class to represent dependence graph
00244   class MSchedGraphSB {
00245 
00246     std::vector<const MachineBasicBlock *> BBs; //Machine basic block
00247     const TargetMachine &Target; //Target Machine
00248 
00249     //Nodes
00250     std::map<const MachineInstr*, MSchedGraphSBNode*> GraphMap;
00251 
00252     //Add Nodes and Edges to this graph for our BB
00253     typedef std::pair<int, MSchedGraphSBNode*> OpIndexNodePair;
00254     void buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ignoreInstrs, DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm, std::map<MSchedGraphSBNode*, std::set<MachineInstr*> > &liveOutsideTrace);
00255     void addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
00256                        MSchedGraphSBNode *node,
00257                        bool nodeIsUse, bool nodeIsDef, std::vector<const MachineInstr*> &phiInstrs, int diff=0);
00258     void addMachRegEdges(std::map<int,
00259                          std::vector<OpIndexNodePair> >& regNumtoNodeMap);
00260     void addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst,
00261                      DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm);
00262 
00263 
00264     bool instrCauseException(MachineOpCode opCode);
00265 
00266   public:
00267     MSchedGraphSB(const MachineBasicBlock *bb, const TargetMachine &targ,
00268                 std::map<const MachineInstr*, unsigned> &ignoreInstrs,
00269                 DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm);
00270 
00271     //Copy constructor with maps to link old nodes to new nodes
00272     MSchedGraphSB(const MSchedGraphSB &G, std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
00273 
00274     MSchedGraphSB(std::vector<const MachineBasicBlock*> &bbs,
00275                 const TargetMachine &targ,
00276                 std::map<const MachineInstr*, unsigned> &ignoreInstrs,
00277                 DependenceAnalyzer &DA,
00278                 std::map<MachineInstr*, Instruction*> &machineTollvm);
00279 
00280     //Print graph
00281     void print(std::ostream &os) const;
00282 
00283     //Deconstructor!
00284     ~MSchedGraphSB();
00285 
00286     //Add or delete nodes from the Graph
00287     void addNode(const MachineInstr* MI, MSchedGraphSBNode *node);
00288     void deleteNode(MSchedGraphSBNode *node);
00289     int totalDelay();
00290 
00291     //iterators
00292     typedef std::map<const MachineInstr*, MSchedGraphSBNode*>::iterator iterator;
00293     typedef std::map<const MachineInstr*, MSchedGraphSBNode*>::const_iterator const_iterator;
00294     typedef std::map<const MachineInstr*, MSchedGraphSBNode*>::reverse_iterator reverse_iterator;
00295     iterator find(const MachineInstr* I) { return GraphMap.find(I); }
00296     iterator end() { return GraphMap.end(); }
00297     iterator begin() { return GraphMap.begin(); }
00298     unsigned size() { return GraphMap.size(); }
00299     reverse_iterator rbegin() { return GraphMap.rbegin(); }
00300     reverse_iterator rend() { return GraphMap.rend(); }
00301 
00302     //Get Target or original machine basic block
00303     const TargetMachine* getTarget() { return &Target; }
00304     std::vector<const MachineBasicBlock*> getBBs() { return BBs; }
00305   };
00306 
00307 
00308 
00309 
00310 
00311   // Provide specializations of GraphTraits to be able to use graph
00312   // iterators on the scheduling graph
00313   static MSchedGraphSBNode& getSecond(std::pair<const MachineInstr* const,
00314                                     MSchedGraphSBNode*> &Pair) {
00315     return *Pair.second;
00316   }
00317 
00318   template <> struct GraphTraits<MSchedGraphSB*> {
00319     typedef MSchedGraphSBNode NodeType;
00320     typedef MSchedGraphSBNode::succ_iterator ChildIteratorType;
00321 
00322     static inline ChildIteratorType child_begin(NodeType *N) {
00323       return N->succ_begin();
00324     }
00325     static inline ChildIteratorType child_end(NodeType *N) {
00326       return N->succ_end();
00327     }
00328 
00329     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00330            MSchedGraphSBNode*>&, MSchedGraphSBNode&> DerefFun;
00331 
00332     typedef mapped_iterator<MSchedGraphSB::iterator, DerefFun> nodes_iterator;
00333     static nodes_iterator nodes_begin(MSchedGraphSB *G) {
00334       return map_iterator(((MSchedGraphSB*)G)->begin(), DerefFun(getSecond));
00335     }
00336     static nodes_iterator nodes_end(MSchedGraphSB *G) {
00337       return map_iterator(((MSchedGraphSB*)G)->end(), DerefFun(getSecond));
00338     }
00339 
00340   };
00341 
00342   template <> struct GraphTraits<const MSchedGraphSB*> {
00343     typedef const MSchedGraphSBNode NodeType;
00344     typedef MSchedGraphSBNode::succ_const_iterator ChildIteratorType;
00345 
00346     static inline ChildIteratorType child_begin(NodeType *N) {
00347       return N->succ_begin();
00348     }
00349     static inline ChildIteratorType child_end(NodeType *N) {
00350       return N->succ_end();
00351     }
00352     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00353                                                      MSchedGraphSBNode*>&, MSchedGraphSBNode&> DerefFun;
00354 
00355     typedef mapped_iterator<MSchedGraphSB::iterator, DerefFun> nodes_iterator;
00356     static nodes_iterator nodes_begin(MSchedGraphSB *G) {
00357       return map_iterator(((MSchedGraphSB*)G)->begin(), DerefFun(getSecond));
00358     }
00359     static nodes_iterator nodes_end(MSchedGraphSB *G) {
00360       return map_iterator(((MSchedGraphSB*)G)->end(), DerefFun(getSecond));
00361     }
00362   };
00363 
00364   template <> struct GraphTraits<Inverse<MSchedGraphSB*> > {
00365     typedef MSchedGraphSBNode NodeType;
00366     typedef MSchedGraphSBNode::pred_iterator ChildIteratorType;
00367 
00368     static inline ChildIteratorType child_begin(NodeType *N) {
00369       return N->pred_begin();
00370     }
00371     static inline ChildIteratorType child_end(NodeType *N) {
00372       return N->pred_end();
00373     }
00374     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00375            MSchedGraphSBNode*>&, MSchedGraphSBNode&> DerefFun;
00376 
00377     typedef mapped_iterator<MSchedGraphSB::iterator, DerefFun> nodes_iterator;
00378     static nodes_iterator nodes_begin(MSchedGraphSB *G) {
00379       return map_iterator(((MSchedGraphSB*)G)->begin(), DerefFun(getSecond));
00380     }
00381     static nodes_iterator nodes_end(MSchedGraphSB *G) {
00382       return map_iterator(((MSchedGraphSB*)G)->end(), DerefFun(getSecond));
00383     }
00384   };
00385 
00386   template <> struct GraphTraits<Inverse<const MSchedGraphSB*> > {
00387     typedef const MSchedGraphSBNode NodeType;
00388     typedef MSchedGraphSBNode::pred_const_iterator ChildIteratorType;
00389 
00390     static inline ChildIteratorType child_begin(NodeType *N) {
00391       return N->pred_begin();
00392     }
00393     static inline ChildIteratorType child_end(NodeType *N) {
00394       return N->pred_end();
00395     }
00396 
00397     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00398                                                      MSchedGraphSBNode*>&, MSchedGraphSBNode&> DerefFun;
00399 
00400     typedef mapped_iterator<MSchedGraphSB::iterator, DerefFun> nodes_iterator;
00401     static nodes_iterator nodes_begin(MSchedGraphSB *G) {
00402       return map_iterator(((MSchedGraphSB*)G)->begin(), DerefFun(getSecond));
00403     }
00404     static nodes_iterator nodes_end(MSchedGraphSB *G) {
00405       return map_iterator(((MSchedGraphSB*)G)->end(), DerefFun(getSecond));
00406     }
00407   };
00408 }
00409 
00410 #endif