LLVM API Documentation

MSSchedule.cpp

Go to the documentation of this file.
00001 //===-- MSSchedule.cpp Schedule ---------------------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 //
00011 //
00012 //===----------------------------------------------------------------------===//
00013 #define DEBUG_TYPE "ModuloSched"
00014 
00015 #include "MSSchedule.h"
00016 #include "llvm/Support/Debug.h"
00017 #include "llvm/Target/TargetSchedInfo.h"
00018 #include "../SparcV9Internals.h"
00019 #include "llvm/CodeGen/MachineInstr.h"
00020 #include <iostream>
00021 using namespace llvm;
00022 
00023 //Check if all resources are free
00024 bool resourcesFree(MSchedGraphNode*, int,
00025 std::map<int, std::map<int, int> > &resourceNumPerCycle);
00026 
00027 //Returns a boolean indicating if the start cycle needs to be increased/decreased
00028 bool MSSchedule::insert(MSchedGraphNode *node, int cycle, int II) {
00029 
00030   //First, check if the cycle has a spot free to start
00031   if(schedule.find(cycle) != schedule.end()) {
00032     //Check if we have a free issue slot at this cycle
00033     if (schedule[cycle].size() < numIssue) {
00034       //Now check if all the resources in their respective cycles are available
00035       if(resourcesFree(node, cycle, II)) {
00036         //Insert to preserve dependencies
00037         addToSchedule(cycle,node);
00038         DEBUG(std::cerr << "Found spot in map, and there is an issue slot\n");
00039         return false;
00040       }
00041     }
00042   }
00043   //Not in the map yet so put it in
00044   else {
00045     if(resourcesFree(node,cycle,II)) {
00046       std::vector<MSchedGraphNode*> nodes;
00047       nodes.push_back(node);
00048       schedule[cycle] = nodes;
00049       DEBUG(std::cerr << "Nothing in map yet so taking an issue slot\n");
00050       return false;
00051     }
00052   }
00053 
00054   DEBUG(std::cerr << "All issue slots taken\n");
00055   return true;
00056 
00057 }
00058 
00059 void MSSchedule::addToSchedule(int cycle, MSchedGraphNode *node) {
00060   std::vector<MSchedGraphNode*> nodesAtCycle = schedule[cycle];
00061 
00062   std::map<unsigned, MSchedGraphNode*> indexMap;
00063   for(unsigned i=0; i < nodesAtCycle.size(); ++i) {
00064     indexMap[nodesAtCycle[i]->getIndex()] = nodesAtCycle[i];
00065   }
00066 
00067   indexMap[node->getIndex()] = node;
00068 
00069   std::vector<MSchedGraphNode*> nodes;
00070   for(std::map<unsigned, MSchedGraphNode*>::iterator I = indexMap.begin(), E = indexMap.end(); I != E; ++I)
00071     nodes.push_back(I->second);
00072 
00073   schedule[cycle] =  nodes;
00074 }
00075 
00076 bool MSSchedule::resourceAvailable(int resourceNum, int cycle) {
00077   bool isFree = true;
00078 
00079   //Get Map for this cycle
00080   if(resourceNumPerCycle.count(cycle)) {
00081     if(resourceNumPerCycle[cycle].count(resourceNum)) {
00082       int maxRes = CPUResource::getCPUResource(resourceNum)->maxNumUsers;
00083       if(resourceNumPerCycle[cycle][resourceNum] >= maxRes)
00084         isFree = false;
00085     }
00086   }
00087 
00088   return isFree;
00089 }
00090 
00091 void MSSchedule::useResource(int resourceNum, int cycle) {
00092 
00093   //Get Map for this cycle
00094   if(resourceNumPerCycle.count(cycle)) {
00095     if(resourceNumPerCycle[cycle].count(resourceNum)) {
00096       resourceNumPerCycle[cycle][resourceNum]++;
00097     }
00098     else {
00099       resourceNumPerCycle[cycle][resourceNum] = 1;
00100     }
00101   }
00102   //If no map, create one!
00103   else {
00104     std::map<int, int> resourceUse;
00105     resourceUse[resourceNum] = 1;
00106     resourceNumPerCycle[cycle] = resourceUse;
00107   }
00108 
00109 }
00110 
00111 bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle, int II) {
00112 
00113   //Get Resource usage for this instruction
00114   const TargetSchedInfo *msi = node->getParent()->getTarget()->getSchedInfo();
00115   int currentCycle = cycle;
00116   bool success = true;
00117 
00118   //Create vector of starting cycles
00119   std::vector<int> cyclesMayConflict;
00120   cyclesMayConflict.push_back(cycle);
00121 
00122   if(resourceNumPerCycle.size() > 0) {
00123     for(int i = cycle-II; i >= (resourceNumPerCycle.begin()->first); i-=II)
00124       cyclesMayConflict.push_back(i);
00125     for(int i = cycle+II; i <= resourceNumPerCycle.end()->first; i+=II)
00126       cyclesMayConflict.push_back(i);
00127   }
00128 
00129   //Now check all cycles for conflicts
00130   for(int index = 0; index < (int) cyclesMayConflict.size(); ++index) {
00131     currentCycle = cyclesMayConflict[index];
00132 
00133     //Get resource usage for this instruction
00134     InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
00135     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
00136 
00137     //Loop over resources in each cycle and increments their usage count
00138     for(unsigned i=0; i < resources.size(); ++i) {
00139       for(unsigned j=0; j < resources[i].size(); ++j) {
00140 
00141         //Get Resource to check its availability
00142         int resourceNum = resources[i][j];
00143 
00144         DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n");
00145 
00146         success = resourceAvailable(resourceNum, currentCycle);
00147 
00148         if(!success)
00149           break;
00150 
00151       }
00152 
00153       if(!success)
00154         break;
00155 
00156       //Increase cycle
00157       currentCycle++;
00158     }
00159 
00160     if(!success)
00161       return false;
00162   }
00163 
00164   //Actually put resources into the map
00165   if(success) {
00166 
00167     int currentCycle = cycle;
00168     //Get resource usage for this instruction
00169     InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
00170     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
00171 
00172     //Loop over resources in each cycle and increments their usage count
00173     for(unsigned i=0; i < resources.size(); ++i) {
00174       for(unsigned j=0; j < resources[i].size(); ++j) {
00175         int resourceNum = resources[i][j];
00176         useResource(resourceNum, currentCycle);
00177       }
00178       currentCycle++;
00179     }
00180   }
00181 
00182 
00183   return true;
00184 
00185 }
00186 
00187 bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches, std::map<const MachineInstr*, unsigned> &indVar) {
00188 
00189   //Our schedule is allowed to have negative numbers, so lets calculate this offset
00190   int offset = schedule.begin()->first;
00191   if(offset > 0)
00192     offset = 0;
00193 
00194   DEBUG(std::cerr << "Offset: " << offset << "\n");
00195 
00196   //Using the schedule, fold up into kernel and check resource conflicts as we go
00197   std::vector<std::pair<MSchedGraphNode*, int> > tempKernel;
00198 
00199   int stageNum = ((schedule.rbegin()->first-offset)+1)/ II;
00200   int maxSN = 0;
00201 
00202   DEBUG(std::cerr << "Number of Stages: " << stageNum << "\n");
00203 
00204   for(int index = offset; index < (II+offset); ++index) {
00205     int count = 0;
00206     for(int i = index; i <= (schedule.rbegin()->first); i+=II) {
00207       if(schedule.count(i)) {
00208         for(std::vector<MSchedGraphNode*>::iterator I = schedule[i].begin(),
00209               E = schedule[i].end(); I != E; ++I) {
00210           //Check if its a branch
00211           assert(!(*I)->isBranch() && "Branch should not be schedule!");
00212 
00213           tempKernel.push_back(std::make_pair(*I, count));
00214           maxSN = std::max(maxSN, count);
00215 
00216         }
00217       }
00218       ++count;
00219     }
00220   }
00221 
00222 
00223   //Add in induction var code
00224   for(std::vector<std::pair<MSchedGraphNode*, int> >::iterator I = tempKernel.begin(), IE = tempKernel.end();
00225       I != IE; ++I) {
00226     //Add indVar instructions before this one for the current iteration
00227     if(I->second == 0) {
00228       std::map<unsigned, MachineInstr*> tmpMap;
00229 
00230       //Loop over induction variable instructions in the map that come before this instr
00231       for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) {
00232 
00233 
00234         if(N->second < I->first->getIndex())
00235           tmpMap[N->second] = (MachineInstr*) N->first;
00236       }
00237 
00238       //Add to kernel, and delete from indVar
00239       for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) {
00240         kernel.push_back(std::make_pair(N->second, 0));
00241         indVar.erase(N->second);
00242       }
00243     }
00244 
00245     kernel.push_back(std::make_pair((MachineInstr*) I->first->getInst(), I->second));
00246 
00247   }
00248 
00249   std::map<unsigned, MachineInstr*> tmpMap;
00250 
00251   //Add remaining invar instructions
00252   for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) {
00253     tmpMap[N->second] = (MachineInstr*) N->first;
00254   }
00255 
00256   //Add to kernel, and delete from indVar
00257   for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) {
00258     kernel.push_back(std::make_pair(N->second, 0));
00259     indVar.erase(N->second);
00260   }
00261 
00262 
00263   maxStage = maxSN;
00264 
00265 
00266   return true;
00267 }
00268 
00269 bool MSSchedule::defPreviousStage(Value *def, int stage) {
00270 
00271   //Loop over kernel and determine if value is being defined in previous stage
00272   for(std::vector<std::pair<MachineInstr*, int> >::iterator P = kernel.begin(), PE = kernel.end(); P != PE; ++P) {
00273     MachineInstr* inst = P->first;
00274 
00275     //Loop over Machine Operands
00276     for(unsigned i=0; i < inst->getNumOperands(); ++i) {
00277       //get machine operand
00278      const MachineOperand &mOp = inst->getOperand(i);
00279      if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
00280        if(def == mOp.getVRegValue()) {
00281          if(P->second >= stage)
00282            return false;
00283          else
00284            return true;
00285        }
00286      }
00287     }
00288   }
00289 
00290   assert(0 && "We should always have found the def in our kernel\n");
00291   abort();
00292 }
00293 
00294 
00295 void MSSchedule::print(std::ostream &os) const {
00296   os << "Schedule:\n";
00297 
00298   for(schedule_const_iterator I =  schedule.begin(), E = schedule.end(); I != E; ++I) {
00299     os << "Cycle: " << I->first << "\n";
00300     for(std::vector<MSchedGraphNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node)
00301     os << **node << "\n";
00302   }
00303 
00304   os << "Kernel:\n";
00305   for(std::vector<std::pair<MachineInstr*, int> >::const_iterator I = kernel.begin(),
00306         E = kernel.end(); I != E; ++I)
00307     os << "Node: " << *(I->first) << " Stage: " << I->second << "\n";
00308 }
00309