diff options
Diffstat (limited to 'lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h')
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h | 192 |
1 files changed, 192 insertions, 0 deletions
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h new file mode 100644 index 0000000000..669611e926 --- /dev/null +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h @@ -0,0 +1,192 @@ +//===-- ModuloSchedulingSuperBlock.h -Swing Modulo Scheduling-----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +//Swing Modulo Scheduling done on Superblocks ( entry, multiple exit, +//multiple basic block loops). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_MODULOSCHEDULINGSB_H +#define LLVM_MODULOSCHEDULINGSB_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Function.h" +#include "llvm/Pass.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "MSScheduleSB.h" +#include "MSchedGraphSB.h" + + +namespace llvm { + + //Struct to contain ModuloScheduling Specific Information for each node + struct MSNodeSBAttributes { + int ASAP; //Earliest time at which the opreation can be scheduled + int ALAP; //Latest time at which the operation can be scheduled. + int MOB; + 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) {} + }; + + + typedef std::vector<const MachineBasicBlock*> SuperBlock; + + class ModuloSchedulingSBPass : public FunctionPass { + const TargetMachine ⌖ + + //Map to hold Value* defs + std::map<const Value*, MachineInstr*> defMap; + + //Map to hold list of instructions associate to the induction var for each BB + std::map<SuperBlock, std::map<const MachineInstr*, unsigned> > indVarInstrs; + + //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; + + //Map that holds node to node attribute information + std::map<MSchedGraphSBNode*, MSNodeSBAttributes> nodeToAttributesMap; + + //Map to hold all reccurrences + std::set<std::pair<int, std::vector<MSchedGraphSBNode*> > > recurrenceList; + + //Set of edges to ignore, stored as src node and index into vector of successors + std::set<std::pair<MSchedGraphSBNode*, unsigned> > edgesToIgnore; + + //Vector containing the partial order + std::vector<std::set<MSchedGraphSBNode*> > partialOrder; + + //Vector containing the final node order + std::vector<MSchedGraphSBNode*> FinalNodeOrder; + + //Schedule table, key is the cycle number and the vector is resource, node pairs + MSScheduleSB schedule; + + //Current initiation interval + int II; + + //Internal Functions + 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); + 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 assocIndVar(Instruction *I, std::set<Instruction*> &indVar, + 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); + 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); + void unblock(MSchedGraphSBNode *u, std::set<MSchedGraphSBNode*> &blocked, + 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 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 searchPath(MSchedGraphSBNode *node, + 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); + + 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>(); + } + }; +} +#endif |