lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp

   1 //===-- MSSchedule.cpp Schedule ---------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   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.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #define DEBUG_TYPE "ModuloSched"
  14
  15 #include "MSSchedule.h"
  16 #include "llvm/Support/Debug.h"
  17 #include "llvm/Target/TargetSchedInfo.h"
  18 #include "../SparcV9Internals.h"
  19 #include "llvm/CodeGen/MachineInstr.h"
  20 #include <iostream>
  21 using namespace llvm;
  22
  23 //Check if all resources are free
  24 bool resourcesFree(MSchedGraphNode*, int,
  25 std::map<int, std::map<int, int> > &resourceNumPerCycle);
  26
  27 //Returns a boolean indicating if the start cycle needs to be increased/decreased
  28 bool MSSchedule::insert(MSchedGraphNode *node, int cycle, int II) {
  29
  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");
  39         return false;
  40       }
  41     }
  42   }
  43   //Not in the map yet so put it in
  44   else {
  45     if(resourcesFree(node,cycle,II)) {
  46       std::vector<MSchedGraphNode*> nodes;
  47       nodes.push_back(node);
  48       schedule[cycle] = nodes;
  49       DEBUG(std::cerr << "Nothing in map yet so taking an issue slot\n");
  50       return false;
  51     }
  52   }
  53
  54   DEBUG(std::cerr << "All issue slots taken\n");
  55   return true;
  56
  57 }
  58
  59 void MSSchedule::addToSchedule(int cycle, MSchedGraphNode *node) {
  60   std::vector<MSchedGraphNode*> nodesAtCycle = schedule[cycle];
  61
  62   std::map<unsigned, MSchedGraphNode*> indexMap;
  63   for(unsigned i=0; i < nodesAtCycle.size(); ++i) {
  64     indexMap[nodesAtCycle[i]->getIndex()] = nodesAtCycle[i];
  65   }
  66
  67   indexMap[node->getIndex()] = node;
  68
  69   std::vector<MSchedGraphNode*> nodes;
  70   for(std::map<unsigned, MSchedGraphNode*>::iterator I = indexMap.begin(), E = indexMap.end(); I != E; ++I)
  71     nodes.push_back(I->second);
  72
  73   schedule[cycle] =  nodes;
  74 }
  75
  76 bool MSSchedule::resourceAvailable(int resourceNum, int cycle) {
  77   bool isFree = true;
  78
  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)
  84         isFree = false;
  85     }
  86   }
  87
  88   return isFree;
  89 }
  90
  91 void MSSchedule::useResource(int resourceNum, int cycle) {
  92
  93   //Get Map for this cycle
  94   if(resourceNumPerCycle.count(cycle)) {
  95     if(resourceNumPerCycle[cycle].count(resourceNum)) {
  96       resourceNumPerCycle[cycle][resourceNum]++;
  97     }
  98     else {
  99       resourceNumPerCycle[cycle][resourceNum] = 1;
 100     }
 101   }
 102   //If no map, create one!
 103   else {
 104     std::map<int, int> resourceUse;
 105     resourceUse[resourceNum] = 1;
 106     resourceNumPerCycle[cycle] = resourceUse;
 107   }
 108
 109 }
 110
 111 bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle, int II) {
 112
 113   //Get Resource usage for this instruction
 114   const TargetSchedInfo *msi = node->getParent()->getTarget()->getSchedInfo();
 115   int currentCycle = cycle;
 116   bool success = true;
 117
 118   //Create vector of starting cycles
 119   std::vector<int> cyclesMayConflict;
 120   cyclesMayConflict.push_back(cycle);
 121
 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);
 127   }
 128
 129   //Now check all cycles for conflicts
 130   for(int index = 0; index < (int) cyclesMayConflict.size(); ++index) {
 131     currentCycle = cyclesMayConflict[index];
 132
 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;
 136
 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) {
 140
 141         //Get Resource to check its availability
 142         int resourceNum = resources[i][j];
 143
 144         DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n");
 145
 146         success = resourceAvailable(resourceNum, currentCycle);
 147
 148         if(!success)
 149           break;
 150
 151       }
 152
 153       if(!success)
 154         break;
 155
 156       //Increase cycle
 157       currentCycle++;
 158     }
 159
 160     if(!success)
 161       return false;
 162   }
 163
 164   //Actually put resources into the map
 165   if(success) {
 166
 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;
 171
 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);
 177       }
 178       currentCycle++;
 179     }
 180   }
 181
 182
 183   return true;
 184
 185 }
 186
 187 bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches, std::map<const MachineInstr*, unsigned> &indVar) {
 188
 189   //Our schedule is allowed to have negative numbers, so lets calculate this offset
 190   int offset = schedule.begin()->first;
 191   if(offset > 0)
 192     offset = 0;
 193
 194   DEBUG(std::cerr << "Offset: " << offset << "\n");
 195
 196   //Using the schedule, fold up into kernel and check resource conflicts as we go
 197   std::vector<std::pair<MSchedGraphNode*, int> > tempKernel;
 198
 199   int stageNum = ((schedule.rbegin()->first-offset)+1)/ II;
 200   int maxSN = 0;
 201
 202   DEBUG(std::cerr << "Number of Stages: " << stageNum << "\n");
 203
 204   for(int index = offset; index < (II+offset); ++index) {
 205     int count = 0;
 206     for(int i = index; i <= (schedule.rbegin()->first); i+=II) {
 207       if(schedule.count(i)) {
 208         for(std::vector<MSchedGraphNode*>::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!");
 212
 213           tempKernel.push_back(std::make_pair(*I, count));
 214           maxSN = std::max(maxSN, count);
 215
 216         }
 217       }
 218       ++count;
 219     }
 220   }
 221
 222
 223   //Add in induction var code
 224   for(std::vector<std::pair<MSchedGraphNode*, int> >::iterator I = tempKernel.begin(), IE = tempKernel.end();
 225       I != IE; ++I) {
 226     //Add indVar instructions before this one for the current iteration
 227     if(I->second == 0) {
 228       std::map<unsigned, MachineInstr*> tmpMap;
 229
 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) {
 232
 233
 234         if(N->second < I->first->getIndex())
 235           tmpMap[N->second] = (MachineInstr*) N->first;
 236       }
 237
 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);
 242       }
 243     }
 244
 245     kernel.push_back(std::make_pair((MachineInstr*) I->first->getInst(), I->second));
 246
 247   }
 248
 249   std::map<unsigned, MachineInstr*> tmpMap;
 250
 251   //Add remaining invar instructions
 252   for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) {
 253     tmpMap[N->second] = (MachineInstr*) N->first;
 254   }
 255
 256   //Add to kernel, and delete from indVar
 257   for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) {
 258     kernel.push_back(std::make_pair(N->second, 0));
 259     indVar.erase(N->second);
 260   }
 261
 262
 263   maxStage = maxSN;
 264
 265
 266   return true;
 267 }
 268
 269 bool MSSchedule::defPreviousStage(Value *def, int stage) {
 270
 271   //Loop over kernel and determine if value is being defined in previous stage
 272   for(std::vector<std::pair<MachineInstr*, int> >::iterator P = kernel.begin(), PE = kernel.end(); P != PE; ++P) {
 273     MachineInstr* inst = P->first;
 274
 275     //Loop over Machine Operands
 276     for(unsigned i=0; i < inst->getNumOperands(); ++i) {
 277       //get machine operand
 278      const MachineOperand &mOp = inst->getOperand(i);
 279      if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
 280        if(def == mOp.getVRegValue()) {
 281          if(P->second >= stage)
 282            return false;
 283          else
 284            return true;
 285        }
 286      }
 287     }
 288   }
 289
 290   assert(0 && "We should always have found the def in our kernel\n");
 291   abort();
 292 }
 293
 294
 295 void MSSchedule::print(std::ostream &os) const {
 296   os << "Schedule:\n";
 297
 298   for(schedule_const_iterator I =  schedule.begin(), E = schedule.end(); I != E; ++I) {
 299     os << "Cycle: " << I->first << "\n";
 300     for(std::vector<MSchedGraphNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node)
 301     os << **node << "\n";
 302   }
 303
 304   os << "Kernel:\n";
 305   for(std::vector<std::pair<MachineInstr*, int> >::const_iterator I = kernel.begin(),
 306         E = kernel.end(); I != E; ++I)
 307     os << "Node: " << *(I->first) << " Stage: " << I->second << "\n";
 308 }
 309