LLVM API Documentation

ModuloSchedulingSuperBlock.h

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