diff options
Diffstat (limited to 'lib/Target/SparcV9/ModuloScheduling')
15 files changed, 0 insertions, 10154 deletions
diff --git a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp b/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp deleted file mode 100644 index 9c3422d54a..0000000000 --- a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp +++ /dev/null @@ -1,305 +0,0 @@ -//===-- DependenceAnalyzer.cpp - DependenceAnalyzer ------------*- 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. -// -//===----------------------------------------------------------------------===// -// -// -// -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "ModuloSched" - -#include "DependenceAnalyzer.h" -#include "llvm/Type.h" -#include "llvm/Support/Debug.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Constants.h" -#include <iostream> -using namespace llvm; - -namespace llvm { - - /// Create ModuloSchedulingPass - FunctionPass *createDependenceAnalyzer() { - return new DependenceAnalyzer(); - } -} - -Statistic<> NoDeps("depanalyzer-nodeps", "Number of dependences eliminated"); -Statistic<> NumDeps("depanalyzer-deps", - "Number of dependences could not eliminate"); -Statistic<> AdvDeps("depanalyzer-advdeps", - "Number of dependences using advanced techniques"); - -bool DependenceAnalyzer::runOnFunction(Function &F) { - AA = &getAnalysis<AliasAnalysis>(); - TD = &getAnalysis<TargetData>(); - SE = &getAnalysis<ScalarEvolution>(); - - return false; -} - -static RegisterAnalysis<DependenceAnalyzer>X("depanalyzer", - "Dependence Analyzer"); - -// - Get inter and intra dependences between loads and stores -// -// Overview of Method: -// Step 1: Use alias analysis to determine dependencies if values are loop -// invariant -// Step 2: If pointers are not GEP, then there is a dependence. -// Step 3: Compare GEP base pointers with AA. If no alias, no dependence. -// If may alias, then add a dependence. If must alias, then analyze -// further (Step 4) -// Step 4: do advanced analysis -void DependenceAnalyzer::AnalyzeDeps(Value *val, Value *val2, bool valLoad, - bool val2Load, - std::vector<Dependence> &deps, - BasicBlock *BB, - bool srcBeforeDest) { - - bool loopInvariant = true; - - //Check if both are instructions and prove not loop invariant if possible - if(Instruction *valInst = dyn_cast<Instruction>(val)) - if(valInst->getParent() == BB) - loopInvariant = false; - if(Instruction *val2Inst = dyn_cast<Instruction>(val2)) - if(val2Inst->getParent() == BB) - loopInvariant = false; - - - //If Loop invariant, let AA decide - if(loopInvariant) { - if(AA->alias(val, (unsigned)TD->getTypeSize(val->getType()), - val2,(unsigned)TD->getTypeSize(val2->getType())) - != AliasAnalysis::NoAlias) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - } - else - ++NoDeps; - return; - } - - //Otherwise, continue with step 2 - - GetElementPtrInst *GP = dyn_cast<GetElementPtrInst>(val); - GetElementPtrInst *GP2 = dyn_cast<GetElementPtrInst>(val2); - - //If both are not GP instructions, we can not do further analysis - if(!GP || !GP2) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - return; - } - - - //Otherwise, compare GEP bases (op #0) with Alias Analysis - - Value *GPop = GP->getOperand(0); - Value *GP2op = GP2->getOperand(0); - int alias = AA->alias(GPop, (unsigned)TD->getTypeSize(GPop->getType()), - GP2op,(unsigned)TD->getTypeSize(GP2op->getType())); - - - if(alias == AliasAnalysis::MustAlias) { - //Further dep analysis to do - advancedDepAnalysis(GP, GP2, valLoad, val2Load, deps, srcBeforeDest); - ++AdvDeps; - } - else if(alias == AliasAnalysis::MayAlias) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - } - //Otherwise no dependence since there is no alias - else - ++NoDeps; -} - - -// advancedDepAnalysis - Do advanced data dependence tests -void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1, - GetElementPtrInst *gp2, - bool valLoad, - bool val2Load, - std::vector<Dependence> &deps, - bool srcBeforeDest) { - - //Check if both GEPs are in a simple form: 3 ops, constant 0 as second arg - if(gp1->getNumOperands() != 3 || gp2->getNumOperands() != 3) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - return; - } - - //Check second arg is constant 0 - bool GPok = false; - if(Constant *c1 = dyn_cast<Constant>(gp1->getOperand(1))) - if(Constant *c2 = dyn_cast<Constant>(gp2->getOperand(1))) - if(c1->isNullValue() && c2->isNullValue()) - GPok = true; - - if(!GPok) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - return; - - } - - Value *Gep1Idx = gp1->getOperand(2); - Value *Gep2Idx = gp2->getOperand(2); - - if(CastInst *c1 = dyn_cast<CastInst>(Gep1Idx)) - Gep1Idx = c1->getOperand(0); - if(CastInst *c2 = dyn_cast<CastInst>(Gep2Idx)) - Gep2Idx = c2->getOperand(0); - - //Get SCEV for each index into the area - SCEVHandle SV1 = SE->getSCEV(Gep1Idx); - SCEVHandle SV2 = SE->getSCEV(Gep2Idx); - - //Now handle special cases of dependence analysis - //SV1->print(std::cerr); - //std::cerr << "\n"; - //SV2->print(std::cerr); - //std::cerr << "\n"; - - //Check if we have an SCEVAddExpr, cause we can only handle those - SCEVAddRecExpr *SVAdd1 = dyn_cast<SCEVAddRecExpr>(SV1); - SCEVAddRecExpr *SVAdd2 = dyn_cast<SCEVAddRecExpr>(SV2); - - //Default to having a dependence since we can't analyze further - if(!SVAdd1 || !SVAdd2) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - return; - } - - //Check if not Affine, we can't handle those - if(!SVAdd1->isAffine( ) || !SVAdd2->isAffine()) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - return; - } - - //We know the SCEV is in the form A + B*x, check that B is the same for both - SCEVConstant *B1 = dyn_cast<SCEVConstant>(SVAdd1->getOperand(1)); - SCEVConstant *B2 = dyn_cast<SCEVConstant>(SVAdd2->getOperand(1)); - - if(B1->getValue() != B2->getValue()) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - return; - } - - if(B1->getValue()->getRawValue() != 1 || B2->getValue()->getRawValue() != 1) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - return; - } - - - SCEVConstant *A1 = dyn_cast<SCEVConstant>(SVAdd1->getOperand(0)); - SCEVConstant *A2 = dyn_cast<SCEVConstant>(SVAdd2->getOperand(0)); - - //Come back and deal with nested SCEV! - if(!A1 || !A2) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - return; - } - - //If equal, create dep as normal - if(A1->getValue() == A2->getValue()) { - createDep(deps, valLoad, val2Load, srcBeforeDest); - return; - } - //Eliminate a dep if this is a intra dep - else if(srcBeforeDest) { - ++NoDeps; - return; - } - - //Find constant index difference - int diff = A1->getValue()->getRawValue() - A2->getValue()->getRawValue(); - //std::cerr << diff << "\n"; - if(diff > 5) - diff = 2; - - if(diff > 0) - createDep(deps, valLoad, val2Load, srcBeforeDest, diff); - - //assert(diff > 0 && "Expected diff to be greater then 0"); -} - -// Create dependences once its determined these two instructions -// references the same memory -void DependenceAnalyzer::createDep(std::vector<Dependence> &deps, - bool valLoad, bool val2Load, - bool srcBeforeDest, int diff) { - - //If the source instruction occurs after the destination instruction - //(execution order), then this dependence is across iterations - if(!srcBeforeDest && (diff==0)) - diff = 1; - - //If load/store pair - if(valLoad && !val2Load) { - if(srcBeforeDest) - //Anti Dep - deps.push_back(Dependence(diff, Dependence::AntiDep)); - else - deps.push_back(Dependence(diff, Dependence::TrueDep)); - - ++NumDeps; - } - //If store/load pair - else if(!valLoad && val2Load) { - if(srcBeforeDest) - //True Dep - deps.push_back(Dependence(diff, Dependence::TrueDep)); - else - deps.push_back(Dependence(diff, Dependence::AntiDep)); - ++NumDeps; - } - //If store/store pair - else if(!valLoad && !val2Load) { - //True Dep - deps.push_back(Dependence(diff, Dependence::OutputDep)); - ++NumDeps; - } -} - - - -//Get Dependence Info for a pair of Instructions -DependenceResult DependenceAnalyzer::getDependenceInfo(Instruction *inst1, - Instruction *inst2, - bool srcBeforeDest) { - std::vector<Dependence> deps; - - DEBUG(std::cerr << "Inst1: " << *inst1 << "\n"); - DEBUG(std::cerr << "Inst2: " << *inst2 << "\n"); - - //No self deps - if(inst1 == inst2) - return DependenceResult(deps); - - if(LoadInst *ldInst = dyn_cast<LoadInst>(inst1)) { - - if(StoreInst *stInst = dyn_cast<StoreInst>(inst2)) - AnalyzeDeps(ldInst->getOperand(0), stInst->getOperand(1), - true, false, deps, ldInst->getParent(), srcBeforeDest); - } - else if(StoreInst *stInst = dyn_cast<StoreInst>(inst1)) { - - if(LoadInst *ldInst = dyn_cast<LoadInst>(inst2)) - AnalyzeDeps(stInst->getOperand(1), ldInst->getOperand(0), false, true, - deps, ldInst->getParent(), srcBeforeDest); - - else if(StoreInst *stInst2 = dyn_cast<StoreInst>(inst2)) - AnalyzeDeps(stInst->getOperand(1), stInst2->getOperand(1), false, false, - deps, stInst->getParent(), srcBeforeDest); - } - else - assert(0 && "Expected a load or a store\n"); - - DependenceResult dr = DependenceResult(deps); - return dr; -} - diff --git a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.h b/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.h deleted file mode 100644 index f9aac5c010..0000000000 --- a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.h +++ /dev/null @@ -1,92 +0,0 @@ -//===-- DependenceAnalyzer.h - Dependence Analyzer--------------*- 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. -// -//===----------------------------------------------------------------------===// -// -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_DEPENDENCEANALYZER_H -#define LLVM_DEPENDENCEANALYZER_H - -#include "llvm/Instructions.h" -#include "llvm/Function.h" -#include "llvm/Pass.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Target/TargetData.h" -#include <vector> - -namespace llvm { - - - //class to represent a dependence - struct Dependence { - - enum DataDepType { - TrueDep, AntiDep, OutputDep, NonDateDep, - }; - - Dependence(int diff, DataDepType dep) : iteDiff(diff), depType(dep) {} - unsigned getIteDiff() { return iteDiff; } - unsigned getDepType() { return depType; } - - private: - - unsigned iteDiff; - unsigned depType; - }; - - - struct DependenceResult { - std::vector<Dependence> dependences; - DependenceResult(const std::vector<Dependence> &d) : dependences(d) {} - }; - - - class DependenceAnalyzer : public FunctionPass { - - - AliasAnalysis *AA; - TargetData *TD; - ScalarEvolution *SE; - - void advancedDepAnalysis(GetElementPtrInst *gp1, GetElementPtrInst *gp2, - bool valLoad, bool val2Load, - std::vector<Dependence> &deps, bool srcBeforeDest); - - void AnalyzeDeps(Value *val, Value *val2, bool val1Load, bool val2Load, - std::vector<Dependence> &deps, BasicBlock *BB, - bool srcBeforeDest); - - void createDep(std::vector<Dependence> &deps, bool valLoad, bool val2Load, - bool srcBeforeDest, int diff = 0); - - public: - DependenceAnalyzer() { AA = 0; TD = 0; SE = 0; } - virtual bool runOnFunction(Function &F); - virtual const char* getPassName() const { return "DependenceAnalyzer"; } - - // getAnalysisUsage - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<AliasAnalysis>(); - AU.addRequired<TargetData>(); - AU.addRequired<ScalarEvolution>(); - AU.setPreservesAll(); - } - - //get dependence info - DependenceResult getDependenceInfo(Instruction *inst1, Instruction *inst2, - bool srcBeforeDest); - - }; - -} - - - -#endif diff --git a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp deleted file mode 100644 index 52d53243f9..0000000000 --- a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp +++ /dev/null @@ -1,309 +0,0 @@ -//===-- MSSchedule.cpp Schedule ---------------------------------*- 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. -// -//===----------------------------------------------------------------------===// -// -// -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "ModuloSched" - -#include "MSSchedule.h" -#include "llvm/Support/Debug.h" -#include "llvm/Target/TargetSchedInfo.h" -#include "../SparcV9Internals.h" -#include "llvm/CodeGen/MachineInstr.h" -#include <iostream> -using namespace llvm; - -//Check if all resources are free -bool resourcesFree(MSchedGraphNode*, int, -std::map<int, std::map<int, int> > &resourceNumPerCycle); - -//Returns a boolean indicating if the start cycle needs to be increased/decreased -bool MSSchedule::insert(MSchedGraphNode *node, int cycle, int II) { - - //First, check if the cycle has a spot free to start - if(schedule.find(cycle) != schedule.end()) { - //Check if we have a free issue slot at this cycle - if (schedule[cycle].size() < numIssue) { - //Now check if all the resources in their respective cycles are available - if(resourcesFree(node, cycle, II)) { - //Insert to preserve dependencies - addToSchedule(cycle,node); - DEBUG(std::cerr << "Found spot in map, and there is an issue slot\n"); - return false; - } - } - } - //Not in the map yet so put it in - else { - if(resourcesFree(node,cycle,II)) { - std::vector<MSchedGraphNode*> nodes; - nodes.push_back(node); - schedule[cycle] = nodes; - DEBUG(std::cerr << "Nothing in map yet so taking an issue slot\n"); - return false; - } - } - - DEBUG(std::cerr << "All issue slots taken\n"); - return true; - -} - -void MSSchedule::addToSchedule(int cycle, MSchedGraphNode *node) { - std::vector<MSchedGraphNode*> nodesAtCycle = schedule[cycle]; - - std::map<unsigned, MSchedGraphNode*> indexMap; - for(unsigned i=0; i < nodesAtCycle.size(); ++i) { - indexMap[nodesAtCycle[i]->getIndex()] = nodesAtCycle[i]; - } - - indexMap[node->getIndex()] = node; - - std::vector<MSchedGraphNode*> nodes; - for(std::map<unsigned, MSchedGraphNode*>::iterator I = indexMap.begin(), E = indexMap.end(); I != E; ++I) - nodes.push_back(I->second); - - schedule[cycle] = nodes; -} - -bool MSSchedule::resourceAvailable(int resourceNum, int cycle) { - bool isFree = true; - - //Get Map for this cycle - if(resourceNumPerCycle.count(cycle)) { - if(resourceNumPerCycle[cycle].count(resourceNum)) { - int maxRes = CPUResource::getCPUResource(resourceNum)->maxNumUsers; - if(resourceNumPerCycle[cycle][resourceNum] >= maxRes) - isFree = false; - } - } - - return isFree; -} - -void MSSchedule::useResource(int resourceNum, int cycle) { - - //Get Map for this cycle - if(resourceNumPerCycle.count(cycle)) { - if(resourceNumPerCycle[cycle].count(resourceNum)) { - resourceNumPerCycle[cycle][resourceNum]++; - } - else { - resourceNumPerCycle[cycle][resourceNum] = 1; - } - } - //If no map, create one! - else { - std::map<int, int> resourceUse; - resourceUse[resourceNum] = 1; - resourceNumPerCycle[cycle] = resourceUse; - } - -} - -bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle, int II) { - - //Get Resource usage for this instruction - const TargetSchedInfo *msi = node->getParent()->getTarget()->getSchedInfo(); - int currentCycle = cycle; - bool success = true; - - //Create vector of starting cycles - std::vector<int> cyclesMayConflict; - cyclesMayConflict.push_back(cycle); - - if(resourceNumPerCycle.size() > 0) { - for(int i = cycle-II; i >= (resourceNumPerCycle.begin()->first); i-=II) - cyclesMayConflict.push_back(i); - for(int i = cycle+II; i <= resourceNumPerCycle.end()->first; i+=II) - cyclesMayConflict.push_back(i); - } - - //Now check all cycles for conflicts - for(int index = 0; index < (int) cyclesMayConflict.size(); ++index) { - currentCycle = cyclesMayConflict[index]; - - //Get resource usage for this instruction - InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode()); - std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle; - - //Loop over resources in each cycle and increments their usage count - for(unsigned i=0; i < resources.size(); ++i) { - for(unsigned j=0; j < resources[i].size(); ++j) { - - //Get Resource to check its availability - int resourceNum = resources[i][j]; - - DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n"); - - success = resourceAvailable(resourceNum, currentCycle); - - if(!success) - break; - - } - - if(!success) - break; - - //Increase cycle - currentCycle++; - } - - if(!success) - return false; - } - - //Actually put resources into the map - if(success) { - - int currentCycle = cycle; - //Get resource usage for this instruction - InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode()); - std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle; - - //Loop over resources in each cycle and increments their usage count - for(unsigned i=0; i < resources.size(); ++i) { - for(unsigned j=0; j < resources[i].size(); ++j) { - int resourceNum = resources[i][j]; - useResource(resourceNum, currentCycle); - } - currentCycle++; - } - } - - - return true; - -} - -bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches, std::map<const MachineInstr*, unsigned> &indVar) { - - //Our schedule is allowed to have negative numbers, so lets calculate this offset - int offset = schedule.begin()->first; - if(offset > 0) - offset = 0; - - DEBUG(std::cerr << "Offset: " << offset << "\n"); - - //Using the schedule, fold up into kernel and check resource conflicts as we go - std::vector<std::pair<MSchedGraphNode*, int> > tempKernel; - - int stageNum = ((schedule.rbegin()->first-offset)+1)/ II; - int maxSN = 0; - - DEBUG(std::cerr << "Number of Stages: " << stageNum << "\n"); - - for(int index = offset; index < (II+offset); ++index) { - int count = 0; - for(int i = index; i <= (schedule.rbegin()->first); i+=II) { - if(schedule.count(i)) { - for(std::vector<MSchedGraphNode*>::iterator I = schedule[i].begin(), - E = schedule[i].end(); I != E; ++I) { - //Check if its a branch - assert(!(*I)->isBranch() && "Branch should not be schedule!"); - - tempKernel.push_back(std::make_pair(*I, count)); - maxSN = std::max(maxSN, count); - - } - } - ++count; - } - } - - - //Add in induction var code - for(std::vector<std::pair<MSchedGraphNode*, int> >::iterator I = tempKernel.begin(), IE = tempKernel.end(); - I != IE; ++I) { - //Add indVar instructions before this one for the current iteration - if(I->second == 0) { - std::map<unsigned, MachineInstr*> tmpMap; - - //Loop over induction variable instructions in the map that come before this instr - for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) { - - - if(N->second < I->first->getIndex()) - tmpMap[N->second] = (MachineInstr*) N->first; - } - - //Add to kernel, and delete from indVar - for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) { - kernel.push_back(std::make_pair(N->second, 0)); - indVar.erase(N->second); - } - } - - kernel.push_back(std::make_pair((MachineInstr*) I->first->getInst(), I->second)); - - } - - std::map<unsigned, MachineInstr*> tmpMap; - - //Add remaining invar instructions - for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) { - tmpMap[N->second] = (MachineInstr*) N->first; - } - - //Add to kernel, and delete from indVar - for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) { - kernel.push_back(std::make_pair(N->second, 0)); - indVar.erase(N->second); - } - - - maxStage = maxSN; - - - return true; -} - -bool MSSchedule::defPreviousStage(Value *def, int stage) { - - //Loop over kernel and determine if value is being defined in previous stage - for(std::vector<std::pair<MachineInstr*, int> >::iterator P = kernel.begin(), PE = kernel.end(); P != PE; ++P) { - MachineInstr* inst = P->first; - - //Loop over Machine Operands - for(unsigned i=0; i < inst->getNumOperands(); ++i) { - //get machine operand - const MachineOperand &mOp = inst->getOperand(i); - if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) { - if(def == mOp.getVRegValue()) { - if(P->second >= stage) - return false; - else - return true; - } - } - } - } - - assert(0 && "We should always have found the def in our kernel\n"); - abort(); -} - - -void MSSchedule::print(std::ostream &os) const { - os << "Schedule:\n"; - - for(schedule_const_iterator I = schedule.begin(), E = schedule.end(); I != E; ++I) { - os << "Cycle: " << I->first << "\n"; - for(std::vector<MSchedGraphNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node) - os << **node << "\n"; - } - - os << "Kernel:\n"; - for(std::vector<std::pair<MachineInstr*, int> >::const_iterator I = kernel.begin(), - E = kernel.end(); I != E; ++I) - os << "Node: " << *(I->first) << " Stage: " << I->second << "\n"; -} - diff --git a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.h b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.h deleted file mode 100644 index 34a37db8b6..0000000000 --- a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.h +++ /dev/null @@ -1,72 +0,0 @@ -//===-- MSSchedule.h - Schedule ------- -------------------------*- 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. -// -//===----------------------------------------------------------------------===// -// -// The schedule generated by a scheduling algorithm -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_MSSCHEDULE_H -#define LLVM_MSSCHEDULE_H - -#include "MSchedGraph.h" -#include <vector> -#include <set> - -namespace llvm { - - class MSSchedule { - std::map<int, std::vector<MSchedGraphNode*> > schedule; - unsigned numIssue; - - //Internal map to keep track of explicit resources - std::map<int, std::map<int, int> > resourceNumPerCycle; - - //Check if all resources are free - bool resourcesFree(MSchedGraphNode*, int, int II); - bool resourceAvailable(int resourceNum, int cycle); - void useResource(int resourceNum, int cycle); - - //Resulting kernel - std::vector<std::pair<MachineInstr*, int> > kernel; - - //Max stage count - int maxStage; - - //add at the right spot in the schedule - void addToSchedule(int, MSchedGraphNode*); - - public: - MSSchedule(int num) : numIssue(num) {} - MSSchedule() : numIssue(4) {} - bool insert(MSchedGraphNode *node, int cycle, int II); - int getStartCycle(MSchedGraphNode *node); - void clear() { schedule.clear(); resourceNumPerCycle.clear(); kernel.clear(); } - std::vector<std::pair<MachineInstr*, int> >* getKernel() { return &kernel; } - bool constructKernel(int II, std::vector<MSchedGraphNode*> &branches, std::map<const MachineInstr*, unsigned> &indVar); - int getMaxStage() { return maxStage; } - bool defPreviousStage(Value *def, int stage); - - //iterators - typedef std::map<int, std::vector<MSchedGraphNode*> >::iterator schedule_iterator; - typedef std::map<int, std::vector<MSchedGraphNode*> >::const_iterator schedule_const_iterator; - schedule_iterator begin() { return schedule.begin(); }; - schedule_iterator end() { return schedule.end(); }; - void print(std::ostream &os) const; - - typedef std::vector<std::pair<MachineInstr*, int> >::iterator kernel_iterator; - typedef std::vector<std::pair<MachineInstr*, int> >::const_iterator kernel_const_iterator; - kernel_iterator kernel_begin() { return kernel.begin(); } - kernel_iterator kernel_end() { return kernel.end(); } - - }; - -} - - -#endif diff --git a/lib/Target/SparcV9/ModuloScheduling/MSScheduleSB.cpp b/lib/Target/SparcV9/ModuloScheduling/MSScheduleSB.cpp deleted file mode 100644 index 487fb336e0..0000000000 --- a/lib/Target/SparcV9/ModuloScheduling/MSScheduleSB.cpp +++ /dev/null @@ -1,325 +0,0 @@ -//===-- MSScheduleSB.cpp Schedule ---------------------------------*- 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. -// -//===----------------------------------------------------------------------===// -// -// -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "ModuloSchedSB" - -#include "MSScheduleSB.h" -#include "llvm/Support/Debug.h" -#include "llvm/Target/TargetSchedInfo.h" -#include "../SparcV9Internals.h" -#include "llvm/CodeGen/MachineInstr.h" -#include <iostream> -using namespace llvm; - -//Check if all resources are free -bool resourcesFree(MSchedGraphSBNode*, int, -std::map<int, std::map<int, int> > &resourceNumPerCycle); - -//Returns a boolean indicating if the start cycle needs to be increased/decreased -bool MSScheduleSB::insert(MSchedGraphSBNode *node, int cycle, int II) { - - //First, check if the cycle has a spot free to start - if(schedule.find(cycle) != schedule.end()) { - //Check if we have a free issue slot at this cycle - if (schedule[cycle].size() < numIssue) { - //Now check if all the resources in their respective cycles are available - if(resourcesFree(node, cycle, II)) { - //Insert to preserve dependencies - addToSchedule(cycle,node); - DEBUG(std::cerr << "Found spot in map, and there is an issue slot\n"); - return false; - } - } - } - //Not in the map yet so put it in - else { - if(resourcesFree(node,cycle,II)) { - std::vector<MSchedGraphSBNode*> nodes; - nodes.push_back(node); - schedule[cycle] = nodes; - DEBUG(std::cerr << "Nothing in map yet so taking an issue slot\n"); - return false; - } - } - - DEBUG(std::cerr << "All issue slots taken\n"); - return true; - -} - -void MSScheduleSB::addToSchedule(int cycle, MSchedGraphSBNode *node) { - std::vector<MSchedGraphSBNode*> nodesAtCycle = schedule[cycle]; - - std::map<unsigned, MSchedGraphSBNode*> indexMap; - for(unsigned i=0; i < nodesAtCycle.size(); ++i) { - indexMap[nodesAtCycle[i]->getIndex()] = nodesAtCycle[i]; - } - - indexMap[node->getIndex()] = node; - - std::vector<MSchedGraphSBNode*> nodes; - for(std::map<unsigned, MSchedGraphSBNode*>::iterator I = indexMap.begin(), E = indexMap.end(); I != E; ++I) - nodes.push_back(I->second); - - schedule[cycle] = nodes; -} - -bool MSScheduleSB::resourceAvailable(int resourceNum, int cycle) { - bool isFree = true; - - //Get Map for this cycle - if(resourceNumPerCycle.count(cycle)) { - if(resourceNumPerCycle[cycle].count(resourceNum)) { - int maxRes = CPUResource::getCPUResource(resourceNum)->maxNumUsers; - if(resourceNumPerCycle[cycle][resourceNum] >= maxRes) - isFree = false; - } - } - - return isFree; -} - -void MSScheduleSB::useResource(int resourceNum, int cycle) { - - //Get Map for this cycle - if(resourceNumPerCycle.count(cycle)) { - if(resourceNumPerCycle[cycle].count(resourceNum)) { - resourceNumPerCycle[cycle][resourceNum]++; - } - else { - resourceNumPerCycle[cycle][resourceNum] = 1; - } |