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 "MSSchedule.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/Pass.h"
  20 #include "DependenceAnalyzer.h"
  21 #include "llvm/Target/TargetData.h"
  22 #include "llvm/Analysis/LoopInfo.h"
  23 #include "llvm/Analysis/ScalarEvolution.h"
  24 #include <set>
  25
  26 namespace llvm {
  27
  28
  29   //Struct to contain ModuloScheduling Specific Information for each node
  30   struct MSNodeAttributes {
  31     int ASAP; //Earliest time at which the opreation can be scheduled
  32     int ALAP; //Latest time at which the operation can be scheduled.
  33     int MOB;
  34     int depth;
  35     int height;
  36     MSNodeAttributes(int asap=-1, int alap=-1, int mob=-1,
  37                              int d=-1, int h=-1) : ASAP(asap), ALAP(alap),
  38                                                    MOB(mob), depth(d),
  39                                                    height(h) {}
  40   };
  41
  42
  43   class ModuloSchedulingPass : public FunctionPass {
  44     const TargetMachine &target;
  45
  46     //Map to hold Value* defs
  47     std::map<const Value*, MachineInstr*> defMap;
  48
  49     //Map to hold list of instructions associate to the induction var for each BB
  50     std::map<const MachineBasicBlock*, std::map<const MachineInstr*, unsigned> > indVarInstrs;
  51
  52     //Map to hold machine to  llvm instrs for each valid BB
  53     std::map<const MachineBasicBlock*, std::map<MachineInstr*, Instruction*> > machineTollvm;
  54
  55     //LLVM Instruction we know we can add TmpInstructions to its MCFI
  56     Instruction *defaultInst;
  57
  58     //Map that holds node to node attribute information
  59     std::map<MSchedGraphNode*, MSNodeAttributes> nodeToAttributesMap;
  60
  61     //Map to hold all reccurrences
  62     std::set<std::pair<int, std::vector<MSchedGraphNode*> > > recurrenceList;
  63
  64     //Set of edges to ignore, stored as src node and index into vector of successors
  65     std::set<std::pair<MSchedGraphNode*, unsigned> > edgesToIgnore;
  66
  67     //Vector containing the partial order
  68     std::vector<std::set<MSchedGraphNode*> > partialOrder;
  69
  70     //Vector containing the final node order
  71     std::vector<MSchedGraphNode*> FinalNodeOrder;
  72
  73     //Schedule table, key is the cycle number and the vector is resource, node pairs
  74     MSSchedule schedule;
  75
  76     //Current initiation interval
  77     int II;
  78
  79     //Internal functions
  80     bool CreateDefMap(MachineBasicBlock *BI);
  81     bool MachineBBisValid(const MachineBasicBlock *BI);
  82     bool assocIndVar(Instruction *I, std::set<Instruction*> &indVar,
  83                      std::vector<Instruction*> &stack, BasicBlock *BB);
  84     int calculateResMII(const MachineBasicBlock *BI);
  85     int calculateRecMII(MSchedGraph *graph, int MII);
  86     void calculateNodeAttributes(MSchedGraph *graph, int MII);
  87
  88     bool ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode);
  89
  90     int calculateASAP(MSchedGraphNode *node, int MII,MSchedGraphNode *destNode);
  91     int calculateALAP(MSchedGraphNode *node, int MII, int maxASAP, MSchedGraphNode *srcNode);
  92
  93     int calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode);
  94     int calculateDepth(MSchedGraphNode *node, MSchedGraphNode *destNode);
  95
  96     int findMaxASAP();
  97     void orderNodes();
  98     void findAllReccurrences(MSchedGraphNode *node,
  99                              std::vector<MSchedGraphNode*> &visitedNodes, int II);
 100     void addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode*, MSchedGraphNode*);
 101     void addSCC(std::vector<MSchedGraphNode*> &SCC, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes);
 102
 103     void findAllCircuits(MSchedGraph *MSG, int II);
 104     bool circuit(MSchedGraphNode *v, std::vector<MSchedGraphNode*> &stack,
 105                  std::set<MSchedGraphNode*> &blocked,
 106                  std::vector<MSchedGraphNode*> &SCC, MSchedGraphNode *s,
 107                  std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B, int II,
 108                  std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes);
 109
 110     void unblock(MSchedGraphNode *u, std::set<MSchedGraphNode*> &blocked,
 111                  std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B);
 112
 113     void addRecc(std::vector<MSchedGraphNode*> &stack, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes);
 114
 115     void searchPath(MSchedGraphNode *node,
 116                     std::vector<MSchedGraphNode*> &path,
 117                     std::set<MSchedGraphNode*> &nodesToAdd,
 118                     std::set<MSchedGraphNode*> &new_reccurence);
 119
 120     void pathToRecc(MSchedGraphNode *node,
 121                     std::vector<MSchedGraphNode*> &path,
 122                     std::set<MSchedGraphNode*> &poSet, std::set<MSchedGraphNode*> &lastNodes);
 123
 124     void computePartialOrder();
 125
 126     bool computeSchedule(const MachineBasicBlock *BB, MSchedGraph *MSG);
 127     bool scheduleNode(MSchedGraphNode *node,
 128                       int start, int end);
 129
 130     void predIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult);
 131     void succIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult);
 132
 133     void reconstructLoop(MachineBasicBlock*);
 134
 135     //void saveValue(const MachineInstr*, const std::set<Value*>&, std::vector<Value*>*);
 136
 137     void fixBranches(std::vector<MachineBasicBlock *> &prologues, std::vector<BasicBlock*> &llvm_prologues, MachineBasicBlock *machineBB, BasicBlock *llvmBB, std::vector<MachineBasicBlock *> &epilogues, std::vector<BasicBlock*> &llvm_epilogues, MachineBasicBlock*);
 138
 139     void writePrologues(std::vector<MachineBasicBlock *> &prologues, MachineBasicBlock *origBB, std::vector<BasicBlock*> &llvm_prologues, std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave, std::map<Value*, std::map<int, Value*> > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation);
 140
 141     void writeEpilogues(std::vector<MachineBasicBlock *> &epilogues, const MachineBasicBlock *origBB, std::vector<BasicBlock*> &llvm_epilogues, std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave,std::map<Value*, std::map<int, Value*> > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation,  std::map<Value*, std::map<int, Value*> > &kernelPHIs);
 142
 143
 144     void writeKernel(BasicBlock *llvmBB, MachineBasicBlock *machineBB, std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave, std::map<Value*, std::map<int, Value*> > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation, std::map<Value*, std::map<int, Value*> > &kernelPHIs);
 145
 146     void removePHIs(const MachineBasicBlock* SB, std::vector<MachineBasicBlock*> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation);
 147
 148     void connectedComponentSet(MSchedGraphNode *node, std::set<MSchedGraphNode*> &ccSet, std::set<MSchedGraphNode*> &lastNodes);
 149
 150   public:
 151     ModuloSchedulingPass(TargetMachine &targ) : target(targ) {}
 152     virtual bool runOnFunction(Function &F);
 153     virtual const char* getPassName() const { return "ModuloScheduling"; }
 154
 155     // getAnalysisUsage
 156     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 157       /// HACK: We don't actually need loopinfo or scev, but we have
 158       /// to say we do so that the pass manager does not delete it
 159       /// before we run.
 160       AU.addRequired<LoopInfo>();
 161       AU.addRequired<ScalarEvolution>();
 162
 163       AU.addRequired<DependenceAnalyzer>();
 164     }
 165
 166   };
 167
 168 }
 169
 170
 171 #endif