lib/CodeGen/ModuloScheduling/ModuloScheduling.h

   1 // ModuloScheduling.h -------------------------------------------*- C++ -*-===//
   2 //
   3 // This header defines the the classes ModuloScheduling and
   4 // ModuloSchedulingSet's structure
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8
   9 #ifndef LLVM_CODEGEN_MODULOSCHEDULING_H
  10 #define LLVM_CODEGEN_MODULOSCHEDULING_H
  11
  12 #include "ModuloSchedGraph.h"
  13 #include <iostream>
  14 #include <vector>
  15
  16 class ModuloScheduling: NonCopyable {
  17 private:
  18
  19   typedef std::vector<ModuloSchedGraphNode*> NodeVec;
  20   typedef std::vector<std::vector<unsigned> > Resources;
  21
  22   // The graph to feed in
  23   ModuloSchedGraph &graph;
  24   const TargetMachine &target;
  25
  26   // The BasicBlock to be scheduled
  27   BasicBlock *bb;
  28
  29   // Iteration Interval
  30   // FIXME: II may be a better name for its meaning
  31   unsigned II;
  32
  33   // The vector containing the nodes which have been scheduled
  34   NodeVec nodeScheduled;
  35
  36   // The remaining unscheduled nodes
  37   const NodeVec &oNodes;
  38
  39   // The machine resource table
  40   std::vector<std::vector<std::pair<int,int> > > resourceTable;
  41
  42   ///the schedule( with many schedule stage)
  43   std::vector<std::vector<ModuloSchedGraphNode*> > schedule;
  44
  45   ///the kernel(core) schedule(length = II)
  46   std::vector<std::vector<ModuloSchedGraphNode*> > coreSchedule;
  47
  48   typedef BasicBlock::InstListType InstListType;
  49   typedef std::vector<std::vector<ModuloSchedGraphNode*> > vvNodeType;
  50
  51 public:
  52
  53   ModuloScheduling(ModuloSchedGraph & _graph):
  54     graph(_graph), target(graph.getTarget()), oNodes(graph.getONodes())
  55   {
  56     II = graph.getMII();
  57     bb = (BasicBlock *) graph.getBasicBlocks()[0];
  58     instrScheduling();
  59   };
  60
  61   ~ModuloScheduling() {};
  62
  63   // for debug information selecton
  64   enum DebugLevel_t {
  65     DebugLevel_NoDebugInfo,
  66     DebugLevel_PrintSchedule,
  67     DebugLevel_PrintScheduleProcess,
  68   };
  69
  70   static DebugLevel_t DebugLevel;
  71
  72   static bool printSchedule() { return DebugLevel >= DebugLevel_PrintSchedule; }
  73   static bool printScheduleProcess() {
  74     return DebugLevel >= DebugLevel_PrintScheduleProcess;
  75   }
  76
  77   // The method to compute schedule and instert epilogue and prologue
  78   void instrScheduling();
  79
  80   // Debug functions:
  81   // Dump the schedule and core schedule
  82   void dumpScheduling();
  83
  84   // Dump the input vector of nodes
  85   // sch: the input vector of nodes
  86   void dumpSchedule(std::vector<std::vector<ModuloSchedGraphNode*> > sch);
  87
  88   // Dump the resource usage table
  89   void dumpResourceUsageTable();
  90
  91   //*******************internal functions*******************************
  92 private:
  93   //clear memory from the last round and initialize if necessary
  94   void clearInitMem(const TargetSchedInfo&);
  95
  96   //compute schedule and coreSchedule with the current II
  97   bool computeSchedule();
  98
  99   BasicBlock *getSuccBB(BasicBlock *);
 100   BasicBlock *getPredBB(BasicBlock *);
 101   void constructPrologue(BasicBlock *prologue);
 102   void constructKernel(BasicBlock *prologue,
 103                        BasicBlock *kernel,
 104                        BasicBlock *epilogue);
 105   void constructEpilogue(BasicBlock *epilogue, BasicBlock *succ_bb);
 106
 107   // update the resource table at the startCycle
 108   // vec: the resouce usage
 109   // startCycle: the start cycle the resouce usage is
 110   void updateResourceTable(std::vector<std::vector<unsigned> > vec,
 111                            int startCycle);
 112
 113   // un-do the update in the resource table in the startCycle
 114   // vec: the resouce usage
 115   // startCycle: the start cycle the resouce usage is
 116   void undoUpdateResourceTable(std::vector<std::vector<unsigned> > vec,
 117                                int startCycle);
 118
 119   // return whether the resourcetable has negative element
 120   // this function is called after updateResouceTable() to determine whether a
 121   // node can be scheduled at certain cycle
 122   bool resourceTableNegative();
 123
 124   // try to Schedule the node starting from start to end cycle(inclusive)
 125   // if it can be scheduled, put it in the schedule and update nodeScheduled
 126   // node: the node to be scheduled
 127   // start: start cycle
 128   // end : end cycle
 129   // nodeScheduled: a vector storing nodes which has been scheduled
 130   bool ScheduleNode(ModuloSchedGraphNode * node, unsigned start,
 131                     unsigned end, NodeVec &nodeScheduled);
 132
 133   //each instruction has a memory of the latest clone instruction
 134   //the clone instruction can be get using getClone()
 135   //this function clears the memory, i.e. getClone() after calling this function
 136   //returns null
 137   void clearCloneMemory();
 138
 139   //this fuction make a clone of this input Instruction and update the clone
 140   //memory
 141   //inst: the instrution to be cloned
 142   Instruction *cloneInstSetMemory(Instruction *inst);
 143
 144   //this function update each instrutions which uses ist as its operand
 145   //after update, each instruction will use ist's clone as its operand
 146   void updateUseWithClone(Instruction * ist);
 147
 148 };
 149
 150
 151 class ModuloSchedulingSet:
 152 NonCopyable {
 153 private:
 154
 155   //the graphSet to feed in
 156   ModuloSchedGraphSet & graphSet;
 157
 158 public:
 159
 160   //constructor
 161   //Scheduling graph one by one
 162   ModuloSchedulingSet(ModuloSchedGraphSet _graphSet): graphSet(_graphSet) {
 163     for (unsigned i = 0; i < graphSet.size(); i++) {
 164       ModuloSchedGraph & graph = *(graphSet[i]);
 165       if (graph.isLoop())
 166         ModuloScheduling ModuloScheduling(graph);
 167     }
 168   };
 169
 170   ~ModuloSchedulingSet() {};
 171 };
 172
 173 #endif