int depth;
int height;
MSNodeSBAttributes(int asap=-1, int alap=-1, int mob=-1,
- int d=-1, int h=-1) : ASAP(asap), ALAP(alap),
- MOB(mob), depth(d),
- height(h) {}
+ int d=-1, int h=-1) : ASAP(asap), ALAP(alap),
+ MOB(mob), depth(d),
+ height(h) {}
};
class ModuloSchedulingSBPass : public FunctionPass {
const TargetMachine ⌖
-
+
//Map to hold Value* defs
std::map<const Value*, MachineInstr*> defMap;
//Map to hold machine to llvm instrs for each valid BB
std::map<SuperBlock, std::map<MachineInstr*, Instruction*> > machineTollvm;
-
+
//LLVM Instruction we know we can add TmpInstructions to its MCFI
Instruction *defaultInst;
//Current initiation interval
int II;
-
+
//Internal Functions
- void FindSuperBlocks(Function &F, LoopInfo &LI,
- std::vector<std::vector<const MachineBasicBlock*> > &Worklist);
+ void FindSuperBlocks(Function &F, LoopInfo &LI,
+ std::vector<std::vector<const MachineBasicBlock*> > &Worklist);
bool MachineBBisValid(const MachineBasicBlock *B,
- std::map<const MachineInstr*, unsigned> &indexMap,
- unsigned &offset);
+ std::map<const MachineInstr*, unsigned> &indexMap,
+ unsigned &offset);
bool CreateDefMap(std::vector<const MachineBasicBlock*> &SB);
- bool getIndVar(std::vector<const MachineBasicBlock*> &superBlock,
- std::map<BasicBlock*, MachineBasicBlock*> &bbMap,
- std::map<const MachineInstr*, unsigned> &indexMap);
+ bool getIndVar(std::vector<const MachineBasicBlock*> &superBlock,
+ std::map<BasicBlock*, MachineBasicBlock*> &bbMap,
+ std::map<const MachineInstr*, unsigned> &indexMap);
bool assocIndVar(Instruction *I, std::set<Instruction*> &indVar,
- std::vector<Instruction*> &stack,
- std::map<BasicBlock*, MachineBasicBlock*> &bbMap,
- const BasicBlock *first,
- std::set<const BasicBlock*> &llvmSuperBlock);
+ std::vector<Instruction*> &stack,
+ std::map<BasicBlock*, MachineBasicBlock*> &bbMap,
+ const BasicBlock *first,
+ std::set<const BasicBlock*> &llvmSuperBlock);
int calculateResMII(std::vector<const MachineBasicBlock*> &superBlock);
int calculateRecMII(MSchedGraphSB *graph, int MII);
void findAllCircuits(MSchedGraphSB *g, int II);
- void addRecc(std::vector<MSchedGraphSBNode*> &stack,
- std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
+ void addRecc(std::vector<MSchedGraphSBNode*> &stack,
+ std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
bool circuit(MSchedGraphSBNode *v, std::vector<MSchedGraphSBNode*> &stack,
- std::set<MSchedGraphSBNode*> &blocked, std::vector<MSchedGraphSBNode*> &SCC,
- MSchedGraphSBNode *s, std::map<MSchedGraphSBNode*,
- std::set<MSchedGraphSBNode*> > &B,
- int II, std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
+ std::set<MSchedGraphSBNode*> &blocked, std::vector<MSchedGraphSBNode*> &SCC,
+ MSchedGraphSBNode *s, std::map<MSchedGraphSBNode*,
+ std::set<MSchedGraphSBNode*> > &B,
+ int II, std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
void unblock(MSchedGraphSBNode *u, std::set<MSchedGraphSBNode*> &blocked,
- std::map<MSchedGraphSBNode*, std::set<MSchedGraphSBNode*> > &B);
+ std::map<MSchedGraphSBNode*, std::set<MSchedGraphSBNode*> > &B);
void addSCC(std::vector<MSchedGraphSBNode*> &SCC, std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
void calculateNodeAttributes(MSchedGraphSB *graph, int MII);
bool ignoreEdge(MSchedGraphSBNode *srcNode, MSchedGraphSBNode *destNode);
int calculateASAP(MSchedGraphSBNode *node, int MII, MSchedGraphSBNode *destNode);
int calculateALAP(MSchedGraphSBNode *node, int MII,
- int maxASAP, MSchedGraphSBNode *srcNode);
+ int maxASAP, MSchedGraphSBNode *srcNode);
int findMaxASAP();
int calculateHeight(MSchedGraphSBNode *node,MSchedGraphSBNode *srcNode);
int calculateDepth(MSchedGraphSBNode *node, MSchedGraphSBNode *destNode);
void computePartialOrder();
- void connectedComponentSet(MSchedGraphSBNode *node, std::set<MSchedGraphSBNode*> &ccSet,
- std::set<MSchedGraphSBNode*> &lastNodes);
+ void connectedComponentSet(MSchedGraphSBNode *node, std::set<MSchedGraphSBNode*> &ccSet,
+ std::set<MSchedGraphSBNode*> &lastNodes);
void searchPath(MSchedGraphSBNode *node,
- std::vector<MSchedGraphSBNode*> &path,
- std::set<MSchedGraphSBNode*> &nodesToAdd,
- std::set<MSchedGraphSBNode*> &new_reccurrence);
+ std::vector<MSchedGraphSBNode*> &path,
+ std::set<MSchedGraphSBNode*> &nodesToAdd,
+ std::set<MSchedGraphSBNode*> &new_reccurrence);
void orderNodes();
bool computeSchedule(std::vector<const MachineBasicBlock*> &BB, MSchedGraphSB *MSG);
bool scheduleNode(MSchedGraphSBNode *node, int start, int end);
void predIntersect(std::set<MSchedGraphSBNode*> &CurrentSet, std::set<MSchedGraphSBNode*> &IntersectResult);
void succIntersect(std::set<MSchedGraphSBNode*> &CurrentSet, std::set<MSchedGraphSBNode*> &IntersectResult);
void reconstructLoop(std::vector<const MachineBasicBlock*> &SB);
- void fixBranches(std::vector<std::vector<MachineBasicBlock*> > &prologues,
- std::vector<std::vector<BasicBlock*> > &llvm_prologues,
- std::vector<MachineBasicBlock*> &machineKernelBB,
- std::vector<BasicBlock*> &llvmKernelBB,
- std::vector<std::vector<MachineBasicBlock*> > &epilogues,
- std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
- std::vector<const MachineBasicBlock*> &SB,
- std::map<const MachineBasicBlock*, Value*> &sideExits);
-
- void writePrologues(std::vector<std::vector<MachineBasicBlock *> > &prologues,
- std::vector<const MachineBasicBlock*> &origBB,
- std::vector<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);
-
- void writeKernel(std::vector<BasicBlock*> &llvmBB, std::vector<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);
-
- void removePHIs(std::vector<const MachineBasicBlock*> &SB,
- std::vector<std::vector<MachineBasicBlock*> > &prologues,
- std::vector<std::vector<MachineBasicBlock*> > &epilogues,
- std::vector<MachineBasicBlock*> &kernelBB,
- std::map<Value*, MachineBasicBlock*> &newValLocation);
-
- void writeEpilogues(std::vector<std::vector<MachineBasicBlock*> > &epilogues,
- std::vector<const MachineBasicBlock*> &origSB,
- std::vector<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);
-
- void writeSideExits(std::vector<std::vector<MachineBasicBlock *> > &prologues,
- std::vector<std::vector<BasicBlock*> > &llvm_prologues,
- std::vector<std::vector<MachineBasicBlock *> > &epilogues,
- std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
- std::map<const MachineBasicBlock*, Value*> &sideExits,
- std::map<MachineBasicBlock*, std::vector<std::pair<MachineInstr*, int> > > &instrsMovedDown,
- std::vector<const MachineBasicBlock*> &SB,
- std::vector<MachineBasicBlock*> &kernelMBBs,
- std::map<MachineBasicBlock*, int> branchStage);
+ void fixBranches(std::vector<std::vector<MachineBasicBlock*> > &prologues,
+ std::vector<std::vector<BasicBlock*> > &llvm_prologues,
+ std::vector<MachineBasicBlock*> &machineKernelBB,
+ std::vector<BasicBlock*> &llvmKernelBB,
+ std::vector<std::vector<MachineBasicBlock*> > &epilogues,
+ std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
+ std::vector<const MachineBasicBlock*> &SB,
+ std::map<const MachineBasicBlock*, Value*> &sideExits);
+
+ void writePrologues(std::vector<std::vector<MachineBasicBlock *> > &prologues,
+ std::vector<const MachineBasicBlock*> &origBB,
+ std::vector<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);
+
+ void writeKernel(std::vector<BasicBlock*> &llvmBB, std::vector<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);
+
+ void removePHIs(std::vector<const MachineBasicBlock*> &SB,
+ std::vector<std::vector<MachineBasicBlock*> > &prologues,
+ std::vector<std::vector<MachineBasicBlock*> > &epilogues,
+ std::vector<MachineBasicBlock*> &kernelBB,
+ std::map<Value*, MachineBasicBlock*> &newValLocation);
+
+ void writeEpilogues(std::vector<std::vector<MachineBasicBlock*> > &epilogues,
+ std::vector<const MachineBasicBlock*> &origSB,
+ std::vector<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);
+
+ void writeSideExits(std::vector<std::vector<MachineBasicBlock *> > &prologues,
+ std::vector<std::vector<BasicBlock*> > &llvm_prologues,
+ std::vector<std::vector<MachineBasicBlock *> > &epilogues,
+ std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
+ std::map<const MachineBasicBlock*, Value*> &sideExits,
+ std::map<MachineBasicBlock*, std::vector<std::pair<MachineInstr*, int> > > &instrsMovedDown,
+ std::vector<const MachineBasicBlock*> &SB,
+ std::vector<MachineBasicBlock*> &kernelMBBs,
+ std::map<MachineBasicBlock*, int> branchStage);
public:
ModuloSchedulingSBPass(TargetMachine &targ) : target(targ) {}
virtual bool runOnFunction(Function &F);
virtual const char* getPassName() const { return "ModuloScheduling-SuperBlock"; }
-
-
+
+
// getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- /// HACK: We don't actually need scev, but we have
- /// to say we do so that the pass manager does not delete it
- /// before we run.
- AU.addRequired<LoopInfo>();
- AU.addRequired<ScalarEvolution>();
- AU.addRequired<DependenceAnalyzer>();
+ /// HACK: We don't actually need scev, but we have
+ /// to say we do so that the pass manager does not delete it
+ /// before we run.
+ AU.addRequired<LoopInfo>();
+ AU.addRequired<ScalarEvolution>();
+ AU.addRequired<DependenceAnalyzer>();
}
};
}
projects / oota-llvm.git / blobdiff