1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
//===-- ModuloScheduling.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.
//
//===----------------------------------------------------------------------===//
//
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_MODULOSCHEDULING_H
#define LLVM_MODULOSCHEDULING_H
#include "MSchedGraph.h"
#include "MSSchedule.h"
#include "llvm/Function.h"
#include "llvm/Pass.h"
#include <set>
namespace llvm {
//Struct to contain ModuloScheduling Specific Information for each node
struct MSNodeAttributes {
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;
MSNodeAttributes(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) {}
};
class ModuloSchedulingPass : public FunctionPass {
const TargetMachine ⌖
//Map that holds node to node attribute information
std::map<MSchedGraphNode*, MSNodeAttributes> nodeToAttributesMap;
//Map to hold all reccurrences
std::set<std::pair<int, std::vector<MSchedGraphNode*> > > recurrenceList;
//Set of edges to ignore, stored as src node and index into vector of successors
std::set<std::pair<MSchedGraphNode*, unsigned> > edgesToIgnore;
//Vector containing the partial order
std::vector<std::vector<MSchedGraphNode*> > partialOrder;
//Vector containing the final node order
std::vector<MSchedGraphNode*> FinalNodeOrder;
//Schedule table, key is the cycle number and the vector is resource, node pairs
MSSchedule schedule;
//Current initiation interval
int II;
//Internal functions
bool MachineBBisValid(const MachineBasicBlock *BI);
int calculateResMII(const MachineBasicBlock *BI);
int calculateRecMII(MSchedGraph *graph, int MII);
void calculateNodeAttributes(MSchedGraph *graph, int MII);
bool ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode);
int calculateASAP(MSchedGraphNode *node, int MII,MSchedGraphNode *destNode);
int calculateALAP(MSchedGraphNode *node, int MII, int maxASAP, MSchedGraphNode *srcNode);
int calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode);
int calculateDepth(MSchedGraphNode *node, MSchedGraphNode *destNode);
int findMaxASAP();
void orderNodes();
void findAllReccurrences(MSchedGraphNode *node,
std::vector<MSchedGraphNode*> &visitedNodes, int II);
void addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode*, MSchedGraphNode*);
void computePartialOrder();
void computeSchedule();
bool scheduleNode(MSchedGraphNode *node,
int start, int end);
void predIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult);
void succIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult);
void reconstructLoop(MachineBasicBlock*);
//void saveValue(const MachineInstr*, const std::set<Value*>&, std::vector<Value*>*);
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, std::vector<Value*> > > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation);
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, std::vector<Value*> > > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation);
void writeKernel(BasicBlock *llvmBB, MachineBasicBlock *machineBB, std::map<const Value*, std::pair<const MSchedGraphNode*, int> > &valuesToSave, std::map<Value*, std::map<int, std::vector<Value*> > > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation);
void removePHIs(const MachineBasicBlock *origBB, std::vector<MachineBasicBlock *> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation);
public:
ModuloSchedulingPass(TargetMachine &targ) : target(targ) {}
virtual bool runOnFunction(Function &F);
};
}
#endif
|
