LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 <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 &target;
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