lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h

   1 //===-- ModuloSchedulingSuperBlock.h -Swing Modulo Scheduling-----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //Swing Modulo Scheduling done on Superblocks ( entry, multiple exit,
  10 //multiple basic block loops).
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_MODULOSCHEDULINGSB_H
  15 #define LLVM_MODULOSCHEDULINGSB_H
  16
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/Analysis/ScalarEvolution.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/Pass.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "MSScheduleSB.h"
  23 #include "MSchedGraphSB.h"
  24
  25
  26 namespace llvm {
  27
  28   //Struct to contain ModuloScheduling Specific Information for each node
  29   struct MSNodeSBAttributes {
  30     int ASAP; //Earliest time at which the opreation can be scheduled
  31     int ALAP; //Latest time at which the operation can be scheduled.
  32     int MOB;
  33     int depth;
  34     int height;
  35     MSNodeSBAttributes(int asap=-1, int alap=-1, int mob=-1,
  36                              int d=-1, int h=-1) : ASAP(asap), ALAP(alap),
  37                                                    MOB(mob), depth(d),
  38                                                    height(h) {}
  39   };
  40
  41
  42   typedef std::vector<const MachineBasicBlock*> SuperBlock;
  43
  44   class ModuloSchedulingSBPass : public FunctionPass {
  45     const TargetMachine &target;
  46
  47     //Map to hold Value* defs
  48     std::map<const Value*, MachineInstr*> defMap;
  49
  50     //Map to hold list of instructions associate to the induction var for each BB
  51     std::map<SuperBlock, std::map<const MachineInstr*, unsigned> > indVarInstrs;
  52
  53     //Map to hold machine to  llvm instrs for each valid BB
  54     std::map<SuperBlock, std::map<MachineInstr*, Instruction*> > machineTollvm;
  55
  56     //LLVM Instruction we know we can add TmpInstructions to its MCFI
  57     Instruction *defaultInst;
  58
  59     //Map that holds node to node attribute information
  60     std::map<MSchedGraphSBNode*, MSNodeSBAttributes> nodeToAttributesMap;
  61
  62     //Map to hold all reccurrences
  63     std::set<std::pair<int, std::vector<MSchedGraphSBNode*> > > recurrenceList;
  64
  65     //Set of edges to ignore, stored as src node and index into vector of successors
  66     std::set<std::pair<MSchedGraphSBNode*, unsigned> > edgesToIgnore;
  67
  68     //Vector containing the partial order
  69     std::vector<std::set<MSchedGraphSBNode*> > partialOrder;
  70
  71     //Vector containing the final node order
  72     std::vector<MSchedGraphSBNode*> FinalNodeOrder;
  73
  74     //Schedule table, key is the cycle number and the vector is resource, node pairs
  75     MSScheduleSB schedule;
  76
  77     //Current initiation interval
  78     int II;
  79
  80     //Internal Functions
  81     void FindSuperBlocks(Function &F, LoopInfo &LI,
  82                          std::vector<std::vector<const MachineBasicBlock*> > &Worklist);
  83     bool MachineBBisValid(const MachineBasicBlock *B,
  84                           std::map<const MachineInstr*, unsigned> &indexMap,
  85                           unsigned &offset);
  86     bool CreateDefMap(std::vector<const MachineBasicBlock*> &SB);
  87     bool getIndVar(std::vector<const MachineBasicBlock*> &superBlock,
  88                    std::map<BasicBlock*, MachineBasicBlock*> &bbMap,
  89                    std::map<const MachineInstr*, unsigned> &indexMap);
  90     bool assocIndVar(Instruction *I, std::set<Instruction*> &indVar,
  91                      std::vector<Instruction*> &stack,
  92                      std::map<BasicBlock*, MachineBasicBlock*> &bbMap,
  93                      const BasicBlock *first,
  94                      std::set<const BasicBlock*> &llvmSuperBlock);
  95     int calculateResMII(std::vector<const MachineBasicBlock*> &superBlock);
  96     int calculateRecMII(MSchedGraphSB *graph, int MII);
  97     void findAllCircuits(MSchedGraphSB *g, int II);
  98     void addRecc(std::vector<MSchedGraphSBNode*> &stack,
  99                  std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
 100     bool circuit(MSchedGraphSBNode *v, std::vector<MSchedGraphSBNode*> &stack,
 101                  std::set<MSchedGraphSBNode*> &blocked, std::vector<MSchedGraphSBNode*> &SCC,
 102                  MSchedGraphSBNode *s, std::map<MSchedGraphSBNode*,
 103                  std::set<MSchedGraphSBNode*> > &B,
 104                  int II, std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
 105     void unblock(MSchedGraphSBNode *u, std::set<MSchedGraphSBNode*> &blocked,
 106                  std::map<MSchedGraphSBNode*, std::set<MSchedGraphSBNode*> > &B);
 107     void addSCC(std::vector<MSchedGraphSBNode*> &SCC, std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
 108     void calculateNodeAttributes(MSchedGraphSB *graph, int MII);
 109     bool ignoreEdge(MSchedGraphSBNode *srcNode, MSchedGraphSBNode *destNode);
 110     int  calculateASAP(MSchedGraphSBNode *node, int MII, MSchedGraphSBNode *destNode);
 111     int calculateALAP(MSchedGraphSBNode *node, int MII,
 112                       int maxASAP, MSchedGraphSBNode *srcNode);
 113     int findMaxASAP();
 114     int calculateHeight(MSchedGraphSBNode *node,MSchedGraphSBNode *srcNode);
 115     int calculateDepth(MSchedGraphSBNode *node, MSchedGraphSBNode *destNode);
 116     void computePartialOrder();
 117     void connectedComponentSet(MSchedGraphSBNode *node, std::set<MSchedGraphSBNode*> &ccSet,
 118                                std::set<MSchedGraphSBNode*> &lastNodes);
 119     void searchPath(MSchedGraphSBNode *node,
 120                     std::vector<MSchedGraphSBNode*> &path,
 121                     std::set<MSchedGraphSBNode*> &nodesToAdd,
 122                     std::set<MSchedGraphSBNode*> &new_reccurrence);
 123     void orderNodes();
 124     bool computeSchedule(std::vector<const MachineBasicBlock*> &BB, MSchedGraphSB *MSG);
 125     bool scheduleNode(MSchedGraphSBNode *node, int start, int end);
 126       void predIntersect(std::set<MSchedGraphSBNode*> &CurrentSet, std::set<MSchedGraphSBNode*> &IntersectResult);
 127     void succIntersect(std::set<MSchedGraphSBNode*> &CurrentSet, std::set<MSchedGraphSBNode*> &IntersectResult);
 128     void reconstructLoop(std::vector<const MachineBasicBlock*> &SB);
 129     void fixBranches(std::vector<std::vector<MachineBasicBlock*> > &prologues,
 130                      std::vector<std::vector<BasicBlock*> > &llvm_prologues,
 131                      std::vector<MachineBasicBlock*> &machineKernelBB,
 132                      std::vector<BasicBlock*> &llvmKernelBB,
 133                      std::vector<std::vector<MachineBasicBlock*> > &epilogues,
 134                      std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
 135                      std::vector<const MachineBasicBlock*> &SB,
 136                      std::map<const MachineBasicBlock*, Value*> &sideExits);
 137
 138     void writePrologues(std::vector<std::vector<MachineBasicBlock *> > &prologues,
 139                         std::vector<const MachineBasicBlock*> &origBB,
 140                         std::vector<std::vector<BasicBlock*> > &llvm_prologues,
 141                         std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave,
 142                         std::map<Value*, std::map<int, Value*> > &newValues,
 143                         std::map<Value*, MachineBasicBlock*> &newValLocation);
 144
 145     void writeKernel(std::vector<BasicBlock*> &llvmBB, std::vector<MachineBasicBlock*> &machineBB,
 146                      std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave,
 147                      std::map<Value*, std::map<int, Value*> > &newValues,
 148                      std::map<Value*, MachineBasicBlock*> &newValLocation,
 149                      std::map<Value*, std::map<int, Value*> > &kernelPHIs);
 150
 151     void removePHIs(std::vector<const MachineBasicBlock*> &SB,
 152                     std::vector<std::vector<MachineBasicBlock*> > &prologues,
 153                     std::vector<std::vector<MachineBasicBlock*> > &epilogues,
 154                     std::vector<MachineBasicBlock*> &kernelBB,
 155                     std::map<Value*, MachineBasicBlock*> &newValLocation);
 156
 157     void writeEpilogues(std::vector<std::vector<MachineBasicBlock*> > &epilogues,
 158                         std::vector<const MachineBasicBlock*> &origSB,
 159                         std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
 160                         std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave,
 161                         std::map<Value*, std::map<int, Value*> > &newValues,
 162                         std::map<Value*, MachineBasicBlock*> &newValLocation,
 163                         std::map<Value*, std::map<int, Value*> > &kernelPHIs);
 164
 165     void writeSideExits(std::vector<std::vector<MachineBasicBlock *> > &prologues,
 166                         std::vector<std::vector<BasicBlock*> > &llvm_prologues,
 167                         std::vector<std::vector<MachineBasicBlock *> > &epilogues,
 168                         std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
 169                         std::map<const MachineBasicBlock*, Value*> &sideExits,
 170                         std::map<MachineBasicBlock*, std::vector<std::pair<MachineInstr*, int> > > &instrsMovedDown,
 171                         std::vector<const MachineBasicBlock*> &SB,
 172                         std::vector<MachineBasicBlock*> &kernelMBBs,
 173                           std::map<MachineBasicBlock*, int> branchStage);
 174
 175  public:
 176     ModuloSchedulingSBPass(TargetMachine &targ) : target(targ) {}
 177       virtual bool runOnFunction(Function &F);
 178       virtual const char* getPassName() const { return "ModuloScheduling-SuperBlock"; }
 179
 180
 181       // getAnalysisUsage
 182       virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 183         /// HACK: We don't actually need scev, but we have
 184         /// to say we do so that the pass manager does not delete it
 185         /// before we run.
 186         AU.addRequired<LoopInfo>();
 187         AU.addRequired<ScalarEvolution>();
 188         AU.addRequired<DependenceAnalyzer>();
 189       }
 190   };
 191 }
 192 #endif