lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h

   1 //===-- ModuloScheduling.h - Swing Modulo Scheduling------------*- C++ -*-===//
   2 //
   3 //                     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.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_MODULOSCHEDULING_H
  14 #define LLVM_MODULOSCHEDULING_H
  15
  16 #include "MSchedGraph.h"
  17 #include "llvm/Function.h"
  18 #include "llvm/Pass.h"
  19 #include <set>
  20
  21 namespace llvm {
  22
  23
  24   //Struct to contain ModuloScheduling Specific Information for each node
  25   struct MSNodeAttributes {
  26     int ASAP; //Earliest time at which the opreation can be scheduled
  27     int ALAP; //Latest time at which the operation can be scheduled.
  28     int MOB;
  29     int depth;
  30     int height;
  31     MSNodeAttributes(int asap=-1, int alap=-1, int mob=-1,
  32                              int d=-1, int h=-1) : ASAP(asap), ALAP(alap),
  33                                                    MOB(mob), depth(d),
  34                                                    height(h) {}
  35   };
  36
  37
  38   class ModuloSchedulingPass : public FunctionPass {
  39     const TargetMachine &target;
  40
  41     //Map that holds node to node attribute information
  42     std::map<MSchedGraphNode*, MSNodeAttributes> nodeToAttributesMap;
  43
  44     //Map to hold all reccurrences
  45     std::set<std::pair<int, std::vector<MSchedGraphNode*> > > recurrenceList;
  46
  47     //Set of edges to ignore, stored as src node and index into vector of successors
  48     std::set<std::pair<MSchedGraphNode*, unsigned> > edgesToIgnore;
  49
  50     //Vector containing the partial order
  51     std::vector<std::vector<MSchedGraphNode*> > partialOrder;
  52
  53     //Vector containing the final node order
  54     std::vector<MSchedGraphNode*> FinalNodeOrder;
  55
  56     //Schedule table, key is the cycle number and the vector is resource, node pairs
  57     std::map<unsigned, std::vector<std::pair<unsigned, std::vector<MSchedGraphNode*> > > > schedule;
  58
  59     //Current initiation interval
  60     int II;
  61
  62     //Internal functions
  63     bool MachineBBisValid(const MachineBasicBlock *BI);
  64     int calculateResMII(const MachineBasicBlock *BI);
  65     int calculateRecMII(MSchedGraph *graph, int MII);
  66     void calculateNodeAttributes(MSchedGraph *graph, int MII);
  67
  68     bool ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode);
  69
  70
  71     int calculateASAP(MSchedGraphNode *node, int MII,MSchedGraphNode *destNode);
  72     int calculateALAP(MSchedGraphNode *node, int MII, int maxASAP, MSchedGraphNode *srcNode);
  73
  74     int calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode);
  75     int calculateDepth(MSchedGraphNode *node, MSchedGraphNode *destNode);
  76
  77     int findMaxASAP();
  78     void orderNodes();
  79     void findAllReccurrences(MSchedGraphNode *node,
  80                              std::vector<MSchedGraphNode*> &visitedNodes, int II);
  81     void addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode*, MSchedGraphNode*);
  82
  83     void computePartialOrder();
  84     void computeSchedule();
  85     bool scheduleNode(MSchedGraphNode *node,
  86                       int start, int end);
  87
  88     void predIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult);
  89     void succIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult);
  90
  91   public:
  92     ModuloSchedulingPass(TargetMachine &targ) : target(targ) {}
  93     virtual bool runOnFunction(Function &F);
  94   };
  95
  96 }
  97
  98
  99 #endif