1 //===-- MSScheduleSB.cpp Schedule ---------------------------------*- 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 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
13 #define DEBUG_TYPE "ModuloSchedSB"
15 #include "MSScheduleSB.h"
16 #include "llvm/Support/Debug.h"
17 #include "llvm/Target/TargetSchedInfo.h"
18 #include "../SparcV9Internals.h"
19 #include "llvm/CodeGen/MachineInstr.h"
23 //Check if all resources are free
24 bool resourcesFree(MSchedGraphSBNode*, int,
25 std::map<int, std::map<int, int> > &resourceNumPerCycle);
27 //Returns a boolean indicating if the start cycle needs to be increased/decreased
28 bool MSScheduleSB::insert(MSchedGraphSBNode *node, int cycle, int II) {
30 //First, check if the cycle has a spot free to start
31 if(schedule.find(cycle) != schedule.end()) {
32 //Check if we have a free issue slot at this cycle
33 if (schedule[cycle].size() < numIssue) {
34 //Now check if all the resources in their respective cycles are available
35 if(resourcesFree(node, cycle, II)) {
36 //Insert to preserve dependencies
37 addToSchedule(cycle,node);
38 DEBUG(std::cerr << "Found spot in map, and there is an issue slot\n");
43 //Not in the map yet so put it in
45 if(resourcesFree(node,cycle,II)) {
46 std::vector<MSchedGraphSBNode*> nodes;
47 nodes.push_back(node);
48 schedule[cycle] = nodes;
49 DEBUG(std::cerr << "Nothing in map yet so taking an issue slot\n");
54 DEBUG(std::cerr << "All issue slots taken\n");
59 void MSScheduleSB::addToSchedule(int cycle, MSchedGraphSBNode *node) {
60 std::vector<MSchedGraphSBNode*> nodesAtCycle = schedule[cycle];
62 std::map<unsigned, MSchedGraphSBNode*> indexMap;
63 for(unsigned i=0; i < nodesAtCycle.size(); ++i) {
64 indexMap[nodesAtCycle[i]->getIndex()] = nodesAtCycle[i];
67 indexMap[node->getIndex()] = node;
69 std::vector<MSchedGraphSBNode*> nodes;
70 for(std::map<unsigned, MSchedGraphSBNode*>::iterator I = indexMap.begin(), E = indexMap.end(); I != E; ++I)
71 nodes.push_back(I->second);
73 schedule[cycle] = nodes;
76 bool MSScheduleSB::resourceAvailable(int resourceNum, int cycle) {
79 //Get Map for this cycle
80 if(resourceNumPerCycle.count(cycle)) {
81 if(resourceNumPerCycle[cycle].count(resourceNum)) {
82 int maxRes = CPUResource::getCPUResource(resourceNum)->maxNumUsers;
83 if(resourceNumPerCycle[cycle][resourceNum] >= maxRes)
91 void MSScheduleSB::useResource(int resourceNum, int cycle) {
93 //Get Map for this cycle
94 if(resourceNumPerCycle.count(cycle)) {
95 if(resourceNumPerCycle[cycle].count(resourceNum)) {
96 resourceNumPerCycle[cycle][resourceNum]++;
99 resourceNumPerCycle[cycle][resourceNum] = 1;
102 //If no map, create one!
104 std::map<int, int> resourceUse;
105 resourceUse[resourceNum] = 1;
106 resourceNumPerCycle[cycle] = resourceUse;
111 bool MSScheduleSB::resourcesFree(MSchedGraphSBNode *node, int cycle, int II) {
113 //Get Resource usage for this instruction
114 const TargetSchedInfo *msi = node->getParent()->getTarget()->getSchedInfo();
115 int currentCycle = cycle;
118 //Create vector of starting cycles
119 std::vector<int> cyclesMayConflict;
120 cyclesMayConflict.push_back(cycle);
122 if(resourceNumPerCycle.size() > 0) {
123 for(int i = cycle-II; i >= (resourceNumPerCycle.begin()->first); i-=II)
124 cyclesMayConflict.push_back(i);
125 for(int i = cycle+II; i <= resourceNumPerCycle.end()->first; i+=II)
126 cyclesMayConflict.push_back(i);
129 //Now check all cycles for conflicts
130 for(int index = 0; index < (int) cyclesMayConflict.size(); ++index) {
131 currentCycle = cyclesMayConflict[index];
133 //Get resource usage for this instruction
134 InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
135 std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
137 //Loop over resources in each cycle and increments their usage count
138 for(unsigned i=0; i < resources.size(); ++i) {
139 for(unsigned j=0; j < resources[i].size(); ++j) {
141 //Get Resource to check its availability
142 int resourceNum = resources[i][j];
144 DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n");
146 success = resourceAvailable(resourceNum, currentCycle);
164 //Actually put resources into the map
167 int currentCycle = cycle;
168 //Get resource usage for this instruction
169 InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
170 std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
172 //Loop over resources in each cycle and increments their usage count
173 for(unsigned i=0; i < resources.size(); ++i) {
174 for(unsigned j=0; j < resources[i].size(); ++j) {
175 int resourceNum = resources[i][j];
176 useResource(resourceNum, currentCycle);
187 bool MSScheduleSB::constructKernel(int II, std::vector<MSchedGraphSBNode*> &branches, std::map<const MachineInstr*, unsigned> &indVar) {
189 //Our schedule is allowed to have negative numbers, so lets calculate this offset
190 int offset = schedule.begin()->first;
194 DEBUG(std::cerr << "Offset: " << offset << "\n");
196 //Using the schedule, fold up into kernel and check resource conflicts as we go
197 std::vector<std::pair<MSchedGraphSBNode*, int> > tempKernel;
199 int stageNum = ((schedule.rbegin()->first-offset)+1)/ II;
202 DEBUG(std::cerr << "Number of Stages: " << stageNum << "\n");
204 for(int index = offset; index < (II+offset); ++index) {
206 for(int i = index; i <= (schedule.rbegin()->first); i+=II) {
207 if(schedule.count(i)) {
208 for(std::vector<MSchedGraphSBNode*>::iterator I = schedule[i].begin(),
209 E = schedule[i].end(); I != E; ++I) {
210 //Check if its a branch
211 assert(!(*I)->isBranch() && "Branch should not be schedule!");
213 tempKernel.push_back(std::make_pair(*I, count));
214 maxSN = std::max(maxSN, count);
223 //Add in induction var code
224 for(std::vector<std::pair<MSchedGraphSBNode*, int> >::iterator I = tempKernel.begin(), IE = tempKernel.end();
226 //Add indVar instructions before this one for the current iteration
228 std::map<unsigned, MachineInstr*> tmpMap;
230 //Loop over induction variable instructions in the map that come before this instr
231 for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) {
234 if(N->second < I->first->getIndex())
235 tmpMap[N->second] = (MachineInstr*) N->first;
238 //Add to kernel, and delete from indVar
239 for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) {
240 kernel.push_back(std::make_pair(N->second, 0));
241 indVar.erase(N->second);
245 kernel.push_back(std::make_pair((MachineInstr*) I->first->getInst(), I->second));
246 if(I->first->isPredicate()) {
247 //assert(I->second == 0 && "Predicate node must be from current iteration\n");
248 std::vector<const MachineInstr*> otherInstrs = I->first->getOtherInstrs();
249 for(std::vector<const MachineInstr*>::iterator O = otherInstrs.begin(), OE = otherInstrs.end(); O != OE; ++O) {
250 kernel.push_back(std::make_pair((MachineInstr*) *O, I->second));
256 std::map<unsigned, MachineInstr*> tmpMap;
258 //Add remaining invar instructions
259 for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) {
260 tmpMap[N->second] = (MachineInstr*) N->first;
263 //Add to kernel, and delete from indVar
264 for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) {
265 kernel.push_back(std::make_pair(N->second, 0));
266 indVar.erase(N->second);
276 bool MSScheduleSB::defPreviousStage(Value *def, int stage) {
278 //Loop over kernel and determine if value is being defined in previous stage
279 for(std::vector<std::pair<MachineInstr*, int> >::iterator P = kernel.begin(), PE = kernel.end(); P != PE; ++P) {
280 MachineInstr* inst = P->first;
282 //Loop over Machine Operands
283 for(unsigned i=0; i < inst->getNumOperands(); ++i) {
284 //get machine operand
285 const MachineOperand &mOp = inst->getOperand(i);
286 if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
287 if(def == mOp.getVRegValue()) {
288 if(P->second >= stage)
297 assert(0 && "We should always have found the def in our kernel\n");
302 void MSScheduleSB::print(std::ostream &os) const {
305 for(schedule_const_iterator I = schedule.begin(), E = schedule.end(); I != E; ++I) {
306 os << "Cycle: " << I->first << "\n";
307 for(std::vector<MSchedGraphSBNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node)
308 os << **node << "\n";
312 for(std::vector<std::pair<MachineInstr*, int> >::const_iterator I = kernel.begin(),
313 E = kernel.end(); I != E; ++I)
314 os << "Node: " << *(I->first) << " Stage: " << I->second << "\n";
317 void MSScheduleSB::printSchedule(std::ostream &os) const {
320 for(schedule_const_iterator I = schedule.begin(), E = schedule.end(); I != E; ++I) {
321 os << "Cycle: " << I->first << "\n";
322 for(std::vector<MSchedGraphSBNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node)
323 os << **node << "\n";