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"
25 //Struct to contain ModuloScheduling Specific Information for each node
26 struct MSNodeAttributes {
27 int ASAP; //Earliest time at which the opreation can be scheduled
28 int ALAP; //Latest time at which the operation can be scheduled.
32 MSNodeAttributes(int asap=-1, int alap=-1, int mob=-1,
33 int d=-1, int h=-1) : ASAP(asap), ALAP(alap),
39 class ModuloSchedulingPass : public FunctionPass {
40 const TargetMachine ⌖
42 //Map that holds node to node attribute information
43 std::map<MSchedGraphNode*, MSNodeAttributes> nodeToAttributesMap;
45 //Map to hold all reccurrences
46 std::set<std::pair<int, std::vector<MSchedGraphNode*> > > recurrenceList;
48 //Set of edges to ignore, stored as src node and index into vector of successors
49 std::set<std::pair<MSchedGraphNode*, unsigned> > edgesToIgnore;
51 //Vector containing the partial order
52 std::vector<std::set<MSchedGraphNode*> > partialOrder;
54 //Vector containing the final node order
55 std::vector<MSchedGraphNode*> FinalNodeOrder;
57 //Schedule table, key is the cycle number and the vector is resource, node pairs
60 //Current initiation interval
64 bool MachineBBisValid(const MachineBasicBlock *BI);
65 int calculateResMII(const MachineBasicBlock *BI);
66 int calculateRecMII(MSchedGraph *graph, int MII);
67 void calculateNodeAttributes(MSchedGraph *graph, int MII);
69 bool ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode);
71 int calculateASAP(MSchedGraphNode *node, int MII,MSchedGraphNode *destNode);
72 int calculateALAP(MSchedGraphNode *node, int MII, int maxASAP, MSchedGraphNode *srcNode);
74 int calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode);
75 int calculateDepth(MSchedGraphNode *node, MSchedGraphNode *destNode);
79 void findAllReccurrences(MSchedGraphNode *node,
80 std::vector<MSchedGraphNode*> &visitedNodes, int II);
81 void addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode*, MSchedGraphNode*);
83 void computePartialOrder();
84 void computeSchedule();
85 bool scheduleNode(MSchedGraphNode *node,
88 void predIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult);
89 void succIntersect(std::set<MSchedGraphNode*> &CurrentSet, std::set<MSchedGraphNode*> &IntersectResult);
91 void reconstructLoop(MachineBasicBlock*);
93 //void saveValue(const MachineInstr*, const std::set<Value*>&, std::vector<Value*>*);
95 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);
97 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);
100 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);
102 void removePHIs(const MachineBasicBlock *origBB, std::vector<MachineBasicBlock *> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation);
104 void connectedComponentSet(MSchedGraphNode *node, std::set<MSchedGraphNode*> &ccSet, std::set<MSchedGraphNode*> &lastNodes);
107 ModuloSchedulingPass(TargetMachine &targ) : target(targ) {}
108 virtual bool runOnFunction(Function &F);