1 //===-- ModuloScheduling.h - Swing Modulo Scheduling------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_MODULOSCHEDULING_H
14 #define LLVM_MODULOSCHEDULING_H
16 #include "MSchedGraph.h"
17 #include "MSSchedule.h"
18 #include "llvm/Function.h"
19 #include "llvm/Pass.h"
20 #include "DependenceAnalyzer.h"
21 #include "llvm/Target/TargetData.h"
22 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/Analysis/ScalarEvolution.h"
29 //Struct to contain ModuloScheduling Specific Information for each node
30 struct MSNodeAttributes {
31 int ASAP; //Earliest time at which the opreation can be scheduled
32 int ALAP; //Latest time at which the operation can be scheduled.
36 MSNodeAttributes(int asap=-1, int alap=-1, int mob=-1,
37 int d=-1, int h=-1) : ASAP(asap), ALAP(alap),
43 class ModuloSchedulingPass : public FunctionPass {
44 const TargetMachine ⌖
46 //Map to hold Value* defs
47 std::map<const Value*, MachineInstr*> defMap;
49 //Map to hold list of instructions associate to the induction var for each BB
50 std::map<const MachineBasicBlock*, std::map<const MachineInstr*, unsigned> > indVarInstrs;
52 //Map to hold machine to llvm instrs for each valid BB
53 std::map<const MachineBasicBlock*, std::map<MachineInstr*, Instruction*> > machineTollvm;
55 //LLVM Instruction we know we can add TmpInstructions to its MCFI
56 Instruction *defaultInst;
58 //Map that holds node to node attribute information
59 std::map<MSchedGraphNode*, MSNodeAttributes> nodeToAttributesMap;
61 //Map to hold all reccurrences
62 std::set<std::pair<int, std::vector<MSchedGraphNode*> > > recurrenceList;
64 //Set of edges to ignore, stored as src node and index into vector of successors
65 std::set<std::pair<MSchedGraphNode*, unsigned> > edgesToIgnore;
67 //Vector containing the partial order
68 std::vector<std::set<MSchedGraphNode*> > partialOrder;
70 //Vector containing the final node order
71 std::vector<MSchedGraphNode*> FinalNodeOrder;
73 //Schedule table, key is the cycle number and the vector is resource, node pairs
76 //Current initiation interval
80 bool CreateDefMap(MachineBasicBlock *BI);
81 bool MachineBBisValid(const MachineBasicBlock *BI);
82 bool assocIndVar(Instruction *I, std::set<Instruction*> &indVar,
83 std::vector<Instruction*> &stack, BasicBlock *BB);
84 int calculateResMII(const MachineBasicBlock *BI);
85 int calculateRecMII(MSchedGraph *graph, int MII);
86 void calculateNodeAttributes(MSchedGraph *graph, int MII);
88 bool ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode);
90 int calculateASAP(MSchedGraphNode *node, int MII,MSchedGraphNode *destNode);
91 int calculateALAP(MSchedGraphNode *node, int MII, int maxASAP, MSchedGraphNode *srcNode);
93 int calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode);
94 int calculateDepth(MSchedGraphNode *node, MSchedGraphNode *destNode);
98 void findAllReccurrences(MSchedGraphNode *node,
99 std::vector<MSchedGraphNode*> &visitedNodes, int II);
100 void addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode*, MSchedGraphNode*);
101 void addSCC(std::vector<MSchedGraphNode*> &SCC, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes);
103 void findAllCircuits(MSchedGraph *MSG, int II);
104 bool circuit(MSchedGraphNode *v, std::vector<MSchedGraphNode*> &stack,
105 std::set<MSchedGraphNode*> &blocked,
106 std::vector<MSchedGraphNode*> &SCC, MSchedGraphNode *s,
107 std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B, int II,
108 std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes);
110 void unblock(MSchedGraphNode *u, std::set<MSchedGraphNode*> &blocked,
111 std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B);
113 void addRecc(std::vector<MSchedGraphNode*> &stack, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes);
115 void searchPath(MSchedGraphNode *node,
116 std::vector<MSchedGraphNode*> &path,
117 std::set<MSchedGraphNode*> &nodesToAdd,
118 std::set<MSchedGraphNode*> &new_reccurence);
120 void pathToRecc(MSchedGraphNode *node,
121 std::vector<MSchedGraphNode*> &path,
122 std::set<MSchedGraphNode*> &poSet, std::set<MSchedGraphNode*> &lastNodes);
124 void computePartialOrder();
126 bool computeSchedule(const MachineBasicBlock *BB, MSchedGraph *MSG);
127 bool scheduleNode(MSchedGraphNode *node,
130 void predIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult);
131 void succIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult);
133 void reconstructLoop(MachineBasicBlock*);
135 //void saveValue(const MachineInstr*, const std::set<Value*>&, std::vector<Value*>*);
137 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*);
139 void writePrologues(std::vector<MachineBasicBlock *> &prologues, MachineBasicBlock *origBB, 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);
141 void writeEpilogues(std::vector<MachineBasicBlock *> &epilogues, const MachineBasicBlock *origBB, 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);
144 void writeKernel(BasicBlock *llvmBB, 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);
146 void removePHIs(const MachineBasicBlock* SB, std::vector<MachineBasicBlock*> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation);
148 void connectedComponentSet(MSchedGraphNode *node, std::set<MSchedGraphNode*> &ccSet, std::set<MSchedGraphNode*> &lastNodes);
151 ModuloSchedulingPass(TargetMachine &targ) : target(targ) {}
152 virtual bool runOnFunction(Function &F);
153 virtual const char* getPassName() const { return "ModuloScheduling"; }
156 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
157 /// HACK: We don't actually need loopinfo or scev, but we have
158 /// to say we do so that the pass manager does not delete it
160 AU.addRequired<LoopInfo>();
161 AU.addRequired<ScalarEvolution>();
163 AU.addRequired<DependenceAnalyzer>();