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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
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,
|
