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 <set> 00021 00022 namespace llvm { 00023 00024 00025 //Struct to contain ModuloScheduling Specific Information for each node 00026 struct MSNodeAttributes { 00027 int ASAP; //Earliest time at which the opreation can be scheduled 00028 int ALAP; //Latest time at which the operation can be scheduled. 00029 int MOB; 00030 int depth; 00031 int height; 00032 MSNodeAttributes(int asap=-1, int alap=-1, int mob=-1, 00033 int d=-1, int h=-1) : ASAP(asap), ALAP(alap), 00034 MOB(mob), depth(d), 00035 height(h) {} 00036 }; 00037 00038 00039 class ModuloSchedulingPass : public FunctionPass { 00040 const TargetMachine ⌖ 00041 00042 //Map to hold Value* defs 00043 std::map<const Value*, MachineInstr*> defMap; 00044 00045 //LLVM Instruction we know we can add TmpInstructions to its MCFI 00046 Instruction *defaultInst; 00047 00048 //Map that holds node to node attribute information 00049 std::map<MSchedGraphNode*, MSNodeAttributes> nodeToAttributesMap; 00050 00051 //Map to hold all reccurrences 00052 std::set<std::pair<int, std::vector<MSchedGraphNode*> > > recurrenceList; 00053 00054 //Set of edges to ignore, stored as src node and index into vector of successors 00055 std::set<std::pair<MSchedGraphNode*, unsigned> > edgesToIgnore; 00056 00057 //Vector containing the partial order 00058 std::vector<std::set<MSchedGraphNode*> > partialOrder; 00059 00060 //Vector containing the final node order 00061 std::vector<MSchedGraphNode*> FinalNodeOrder; 00062 00063 //Schedule table, key is the cycle number and the vector is resource, node pairs 00064 MSSchedule schedule; 00065 00066 //Current initiation interval 00067 int II; 00068 00069 //Internal functions 00070 void CreateDefMap(MachineBasicBlock *BI); 00071 bool MachineBBisValid(const MachineBasicBlock *BI); 00072 int calculateResMII(const MachineBasicBlock *BI); 00073 int calculateRecMII(MSchedGraph *graph, int MII); 00074 void calculateNodeAttributes(MSchedGraph *graph, int MII); 00075 00076 bool ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode); 00077 00078 int calculateASAP(MSchedGraphNode *node, int MII,MSchedGraphNode *destNode); 00079 int calculateALAP(MSchedGraphNode *node, int MII, int maxASAP, MSchedGraphNode *srcNode); 00080 00081 int calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode); 00082 int calculateDepth(MSchedGraphNode *node, MSchedGraphNode *destNode); 00083 00084 int findMaxASAP(); 00085 void orderNodes(); 00086 void findAllReccurrences(MSchedGraphNode *node, 00087 std::vector<MSchedGraphNode*> &visitedNodes, int II); 00088 void addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode*, MSchedGraphNode*); 00089 00090 void computePartialOrder(); 00091 bool computeSchedule(); 00092 bool scheduleNode(MSchedGraphNode *node, 00093 int start, int end); 00094 00095 void predIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult); 00096 void succIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult); 00097 00098 void reconstructLoop(MachineBasicBlock*); 00099 00100 //void saveValue(const MachineInstr*, const std::set<Value*>&, std::vector<Value*>*); 00101 00102 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*); 00103 00104 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, Value*> > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation); 00105 00106 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, Value*> > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation, std::map<Value*, std::map<int, Value*> > &kernelPHIs); 00107 00108 00109 void writeKernel(BasicBlock *llvmBB, MachineBasicBlock *machineBB, std::map<const Value*, std::pair<const MSchedGraphNode*, int> > &valuesToSave, std::map<Value*, std::map<int, Value*> > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation, std::map<Value*, std::map<int, Value*> > &kernelPHIs); 00110 00111 void removePHIs(const MachineBasicBlock *origBB, std::vector<MachineBasicBlock *> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation); 00112 00113 void connectedComponentSet(MSchedGraphNode *node, std::set<MSchedGraphNode*> &ccSet, std::set<MSchedGraphNode*> &lastNodes); 00114 00115 public: 00116 ModuloSchedulingPass(TargetMachine &targ) : target(targ) {} 00117 virtual bool runOnFunction(Function &F); 00118 virtual const char* getPassName() const { return "ModuloScheduling"; } 00119 }; 00120 00121 } 00122 00123 00124 #endif