LLVM API Documentation

ModuloScheduling.h

Go to the documentation of this file.
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 &target;
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