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
  19 using namespace llvm;
  20
  21 bool MSSchedule::insert(MSchedGraphNode *node, int cycle) {
  22
  23   //First, check if the cycle has a spot free to start
  24   if(schedule.find(cycle) != schedule.end()) {
  25     if (schedule[cycle].size() < numIssue) {
  26       if(resourcesFree(node, cycle)) {
  27         schedule[cycle].push_back(node);
  28         DEBUG(std::cerr << "Found spot in map, and there is an issue slot\n");
  29         return false;
  30       }
  31     }
  32   }
  33   //Not in the map yet so put it in
  34   else {
  35     if(resourcesFree(node,cycle)) {
  36       std::vector<MSchedGraphNode*> nodes;
  37       nodes.push_back(node);
  38       schedule[cycle] = nodes;
  39       DEBUG(std::cerr << "Nothing in map yet so taking an issue slot\n");
  40       return false;
  41     }
  42   }
  43
  44   DEBUG(std::cerr << "All issue slots taken\n");
  45   return true;
  46
  47 }
  48
  49 bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle) {
  50
  51   //Get Resource usage for this instruction
  52   const TargetSchedInfo *msi = node->getParent()->getTarget()->getSchedInfo();
  53   int currentCycle = cycle;
  54   bool success = true;
  55
  56     //Get resource usage for this instruction
  57     InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
  58     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
  59
  60     //Loop over resources in each cycle and increments their usage count
  61     for(unsigned i=0; i < resources.size(); ++i) {
  62       for(unsigned j=0; j < resources[i].size(); ++j) {
  63         int resourceNum = resources[i][j];
  64
  65         //Check if this resource is available for this cycle
  66         std::map<int, std::map<int,int> >::iterator resourcesForCycle = resourceNumPerCycle.find(currentCycle);
  67
  68         //First check map of resources for this cycle
  69         if(resourcesForCycle != resourceNumPerCycle.end()) {
  70           //A map exists for this cycle, so lets check for the resource
  71           std::map<int, int>::iterator resourceUse = resourcesForCycle->second.find(resourceNum);
  72           if(resourceUse != resourcesForCycle->second.end()) {
  73             //Check if there are enough of this resource and if so, increase count and move on
  74             if(resourceUse->second < CPUResource::getCPUResource(resourceNum)->maxNumUsers)
  75               ++resourceUse->second;
  76             else {
  77               success = false;
  78             }
  79           }
  80           //Not in the map yet, so put it
  81           else
  82             resourcesForCycle->second[resourceNum] = 1;
  83
  84         }
  85         else {
  86           //Create a new map and put in our resource
  87           std::map<int, int> resourceMap;
  88           resourceMap[resourceNum] = 1;
  89           resourceNumPerCycle[cycle] = resourceMap;
  90         }
  91         if(!success)
  92           break;
  93       }
  94       if(!success)
  95         break;
  96         //Increase cycle
  97         currentCycle++;
  98       }
  99
 100     if(!success) {
 101       int oldCycle = cycle;
 102       DEBUG(std::cerr << "Backtrack\n");
 103       //Get resource usage for this instruction
 104       InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
 105       std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
 106
 107       //Loop over resources in each cycle and increments their usage count
 108       for(unsigned i=0; i < resources.size(); ++i) {
 109         if(oldCycle < currentCycle) {
 110
 111           //Check if this resource is available for this cycle
 112           std::map<int, std::map<int,int> >::iterator resourcesForCycle = resourceNumPerCycle.find(oldCycle);
 113
 114           for(unsigned j=0; j < resources[i].size(); ++j) {
 115             int resourceNum = resources[i][j];
 116             //remove from map
 117             std::map<int, int>::iterator resourceUse = resourcesForCycle->second.find(resourceNum);
 118             //assert if not in the map.. since it should be!
 119             //assert(resourceUse != resourcesForCycle.end() && "Resource should be in map!");
 120             --resourceUse->second;
 121           }
 122         }
 123         else
 124           break;
 125         oldCycle++;
 126       }
 127       return false;
 128
 129     }
 130
 131     return true;
 132
 133 }
 134
 135 bool MSSchedule::constructKernel(int II) {
 136   MSchedGraphNode *branchNode = 0;
 137
 138   int stageNum = (schedule.rbegin()->first)/ II;
 139   DEBUG(std::cerr << "Number of Stages: " << stageNum << "\n");
 140
 141   for(int index = 0; index < II; ++index) {
 142     int count = 0;
 143     for(int i = index; i <= (schedule.rbegin()->first); i+=II) {
 144       if(schedule.count(i)) {
 145         for(std::vector<MSchedGraphNode*>::iterator I = schedule[i].begin(),
 146               E = schedule[i].end(); I != E; ++I) {
 147           //Check if its a branch
 148           if((*I)->isBranch()) {
 149             branchNode = *I;
 150             assert(count == 0 && "Branch can not be from a previous iteration");
 151           }
 152           else
 153           //FIXME: Check if the instructions in the earlier stage conflict
 154           kernel.push_back(std::make_pair(*I, count));
 155         }
 156       }
 157       ++count;
 158     }
 159   }
 160
 161   //Add Branch to the end
 162   kernel.push_back(std::make_pair(branchNode, 0));
 163
 164   return true;
 165 }
 166
 167
 168 void MSSchedule::print(std::ostream &os) const {
 169   os << "Schedule:\n";
 170
 171   for(schedule_const_iterator I =  schedule.begin(), E = schedule.end(); I != E; ++I) {
 172     os << "Cycle: " << I->first << "\n";
 173     for(std::vector<MSchedGraphNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node)
 174     os << **node << "\n";
 175   }
 176
 177   os << "Kernel:\n";
 178   for(std::vector<std::pair<MSchedGraphNode*, int> >::const_iterator I = kernel.begin(),
 179         E = kernel.end(); I != E; ++I)
 180     os << "Node: " << *(I->first) << " Stage: " << I->second << "\n";
 181 }
 182