LLVM API Documentation
00001 //===-- ModuloScheduling.h - Swing Modulo Scheduling------------*- 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 // 00011 //===----------------------------------------------------------------------===// 00012 00013 #ifndef LLVM_MODULOSCHEDULING_H 00014 #define LLVM_MODULOSCHEDULING_H 00015 00016 #include "MSchedGraph.h" 00017 #include "MSSchedule.h" 00018 #include "llvm/Function.h" 00019 #include "llvm/Pass.h" 00020 #include "DependenceAnalyzer.h" 00021 #include "llvm/Target/TargetData.h" 00022 #include "llvm/Analysis/LoopInfo.h" 00023 #include "llvm/Analysis/ScalarEvolution.h" 00024 #include <set> 00025 00026 namespace llvm { 00027 00028 00029 //Struct to contain ModuloScheduling Specific Information for each node 00030 struct MSNodeAttributes { 00031 int ASAP; //Earliest time at which the opreation can be scheduled 00032 int ALAP; //Latest time at which the operation can be scheduled. 00033 int MOB; 00034 int depth; 00035 int height; 00036 MSNodeAttributes(int asap=-1, int alap=-1, int mob=-1, 00037 int d=-1, int h=-1) : ASAP(asap), ALAP(alap), 00038 MOB(mob), depth(d), 00039 height(h) {} 00040 }; 00041 00042 00043 class ModuloSchedulingPass : public FunctionPass { 00044 const TargetMachine ⌖ 00045 00046 //Map to hold Value* defs 00047 std::map<const Value*, MachineInstr*> defMap; 00048 00049 //Map to hold list of instructions associate to the induction var for each BB 00050 std::map<const MachineBasicBlock*, std::map<const MachineInstr*, unsigned> > indVarInstrs; 00051 00052 //Map to hold machine to llvm instrs for each valid BB 00053 std::map<const MachineBasicBlock*, std::map<MachineInstr*, Instruction*> > machineTollvm; 00054 00055 //LLVM Instruction we know we can add TmpInstructions to its MCFI 00056 Instruction *defaultInst; 00057 00058 //Map that holds node to node attribute information 00059 std::map<MSchedGraphNode*, MSNodeAttributes> nodeToAttributesMap; 00060 00061 //Map to hold all reccurrences 00062 std::set<std::pair<int, std::vector<MSchedGraphNode*> > > recurrenceList; 00063 00064 //Set of edges to ignore, stored as src node and index into vector of successors 00065 std::set<std::pair<MSchedGraphNode*, unsigned> > edgesToIgnore; 00066 00067 //Vector containing the partial order 00068 std::vector<std::set<MSchedGraphNode*> > partialOrder; 00069 00070 //Vector containing the final node order 00071 std::vector<MSchedGraphNode*> FinalNodeOrder; 00072 00073 //Schedule table, key is the cycle number and the vector is resource, node pairs 00074 MSSchedule schedule; 00075 00076 //Current initiation interval 00077 int II; 00078 00079 //Internal functions 00080 bool CreateDefMap(MachineBasicBlock *BI); 00081 bool MachineBBisValid(const MachineBasicBlock *BI); 00082 bool assocIndVar(Instruction *I, std::set<Instruction*> &indVar, 00083 std::vector<Instruction*> &stack, BasicBlock *BB); 00084 int calculateResMII(const MachineBasicBlock *BI); 00085 int calculateRecMII(MSchedGraph *graph, int MII); 00086 void calculateNodeAttributes(MSchedGraph *graph, int MII); 00087 00088 bool ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode); 00089 00090 int calculateASAP(MSchedGraphNode *node, int MII,MSchedGraphNode *destNode); 00091 int calculateALAP(MSchedGraphNode *node, int MII, int maxASAP, MSchedGraphNode *srcNode); 00092 00093 int calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode); 00094 int calculateDepth(MSchedGraphNode *node, MSchedGraphNode *destNode); 00095 00096 int findMaxASAP(); 00097 void orderNodes(); 00098 void findAllReccurrences(MSchedGraphNode *node, 00099 std::vector<MSchedGraphNode*> &visitedNodes, int II); 00100 void addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode*, MSchedGraphNode*); 00101 void addSCC(std::vector<MSchedGraphNode*> &SCC, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes); 00102 00103 void findAllCircuits(MSchedGraph *MSG, int II); 00104 bool circuit(MSchedGraphNode *v, std::vector<MSchedGraphNode*> &stack, 00105 std::set<MSchedGraphNode*> &blocked, 00106 std::vector<MSchedGraphNode*> &SCC, MSchedGraphNode *s, 00107 std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B, int II, 00108 std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes); 00109 00110 void unblock(MSchedGraphNode *u, std::set<MSchedGraphNode*> &blocked, 00111 std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B); 00112 00113 void addRecc(std::vector<MSchedGraphNode*> &stack, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes); 00114 00115 void searchPath(MSchedGraphNode *node, 00116 std::vector<MSchedGraphNode*> &path, 00117 std::set<MSchedGraphNode*> &nodesToAdd, 00118 std::set<MSchedGraphNode*> &new_reccurence); 00119 00120 void pathToRecc(MSchedGraphNode *node, 00121 std::vector<MSchedGraphNode*> &path, 00122 std::set<MSchedGraphNode*> &poSet, std::set<MSchedGraphNode*> &lastNodes); 00123 00124 void computePartialOrder(); 00125 00126 bool computeSchedule(const MachineBasicBlock *BB, MSchedGraph *MSG); 00127 bool scheduleNode(MSchedGraphNode *node, 00128 int start, int end); 00129 00130 void predIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult); 00131 void succIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult); 00132 00133 void reconstructLoop(MachineBasicBlock*); 00134 00135 //void saveValue(const MachineInstr*, const std::set<Value*>&, std::vector<Value*>*); 00136 00137 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*); 00138 00139 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); 00140 00141 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); 00142 00143 00144 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); 00145 00146 void removePHIs(const MachineBasicBlock* SB, std::vector<MachineBasicBlock*> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation); 00147 00148 void connectedComponentSet(MSchedGraphNode *node, std::set<MSchedGraphNode*> &ccSet, std::set<MSchedGraphNode*> &lastNodes); 00149 00150 public: 00151 ModuloSchedulingPass(TargetMachine &targ) : target(targ) {} 00152 virtual bool runOnFunction(Function &F); 00153 virtual const char* getPassName() const { return "ModuloScheduling"; } 00154 00155 // getAnalysisUsage 00156 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00157 /// HACK: We don't actually need loopinfo or scev, but we have 00158 /// to say we do so that the pass manager does not delete it 00159 /// before we run. 00160 AU.addRequired<LoopInfo>(); 00161 AU.addRequired<ScalarEvolution>(); 00162 00163 AU.addRequired<DependenceAnalyzer>(); 00164 } 00165 00166 }; 00167 00168 } 00169 00170 00171 #endif