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