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