diff options
Diffstat (limited to 'lib/Target/SparcV9/ModuloScheduling')
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp | 80 | ||||
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/MSSchedule.h | 11 | ||||
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp | 305 | ||||
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h | 76 | ||||
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp | 419 | ||||
| -rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h | 26 |
6 files changed, 724 insertions, 193 deletions
diff --git a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp index 96662dd887..5855f0a3cb 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp @@ -165,12 +165,27 @@ bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle) { } -bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches) { +bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches, std::map<const MachineInstr*, unsigned> &indVar) { - int stageNum = (schedule.rbegin()->first)/ II; + //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"); + + //Not sure what happens in this case, but assert if offset is > II + //assert(offset > -II && "Offset can not be more then II"); + + 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 = 0; index < II; ++index) { + 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)) { @@ -179,26 +194,61 @@ bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches //Check if its a branch if((*I)->isBranch()) { assert(count == 0 && "Branch can not be from a previous iteration"); - kernel.push_back(std::make_pair(*I, count)); + tempKernel.push_back(std::make_pair(*I, count)); } - else + else { //FIXME: Check if the instructions in the earlier stage conflict - kernel.push_back(std::make_pair(*I, count)); + tempKernel.push_back(std::make_pair(*I, count)); + maxSN = std::max(maxSN, count); + } } } ++count; } } - - //Push on branches. Branch vector is in order of last branch to first. - for(std::vector<MSchedGraphNode*>::reverse_iterator B = branches.rbegin() , BE = branches.rend(); B != BE; ++B) { - kernel.push_back(std::make_pair(*B, 0)); + + //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); } - if(stageNum > 0) - maxStage = stageNum; - else - maxStage = 0; + + maxStage = maxSN; + return true; } @@ -214,7 +264,7 @@ void MSSchedule::print(std::ostream &os) const { } os << "Kernel:\n"; - for(std::vector<std::pair<MSchedGraphNode*, int> >::const_iterator I = kernel.begin(), + 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 index b94ab3eb54..16cbab13f2 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.h +++ b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.h @@ -16,6 +16,7 @@ #include "MSchedGraph.h" #include <vector> +#include <set> namespace llvm { @@ -30,7 +31,7 @@ namespace llvm { bool resourcesFree(MSchedGraphNode*, int); //Resulting kernel - std::vector<std::pair<MSchedGraphNode*, int> > kernel; + std::vector<std::pair<MachineInstr*, int> > kernel; //Max stage count int maxStage; @@ -44,8 +45,8 @@ namespace llvm { bool insert(MSchedGraphNode *node, int cycle); int getStartCycle(MSchedGraphNode *node); void clear() { schedule.clear(); resourceNumPerCycle.clear(); kernel.clear(); } - std::vector<std::pair<MSchedGraphNode*, int> >* getKernel() { return &kernel; } - bool constructKernel(int II, std::vector<MSchedGraphNode*> &branches); + 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; } @@ -56,8 +57,8 @@ namespace llvm { schedule_iterator end() { return schedule.end(); }; void print(std::ostream &os) const; - typedef std::vector<std::pair<MSchedGraphNode*, int> >::iterator kernel_iterator; - typedef std::vector<std::pair<MSchedGraphNode*, int> >::const_iterator kernel_const_iterator; + 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(); } diff --git a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp index 9ac38b4dd3..7b4680ebe2 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp @@ -7,8 +7,11 @@ // //===----------------------------------------------------------------------===// // -// A graph class for dependencies -// +// A graph class for dependencies. This graph only contains true, anti, and +// output data dependencies for a given MachineBasicBlock. Dependencies +// across iterations are also computed. Unless data dependence analysis +// is provided, a conservative approach of adding dependencies between all +// loads and stores is taken. //===----------------------------------------------------------------------===// #define DEBUG_TYPE "ModuloSched" @@ -22,8 +25,11 @@ #include "llvm/Support/Debug.h" #include <cstdlib> #include <algorithm> +#include <set> + using namespace llvm; +//MSchedGraphNode constructor MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst, MSchedGraph *graph, unsigned idx, unsigned late, bool isBranch) @@ -33,6 +39,7 @@ MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst, graph->addNode(inst, this); } +//MSchedGraphNode copy constructor MSchedGraphNode::MSchedGraphNode(const MSchedGraphNode &N) : Predecessors(N.Predecessors), Successors(N.Successors) { @@ -44,10 +51,13 @@ MSchedGraphNode::MSchedGraphNode(const MSchedGraphNode &N) } +//Print the node (instruction and latency) void MSchedGraphNode::print(std::ostream &os) const { os << "MSchedGraphNode: Inst=" << *Inst << ", latency= " << latency << "\n"; } + +//Get the edge from a predecessor to this node MSchedGraphEdge MSchedGraphNode::getInEdge(MSchedGraphNode *pred) { //Loop over all the successors of our predecessor //return the edge the corresponds to this in edge @@ -60,6 +70,7 @@ MSchedGraphEdge MSchedGraphNode::getInEdge(MSchedGraphNode *pred) { abort(); } +//Get the iteration difference for the edge from this node to its successor unsigned MSchedGraphNode::getIteDiff(MSchedGraphNode *succ) { for(std::vector<MSchedGraphEdge>::iterator I = Successors.begin(), E = Successors.end(); I != E; ++I) { @@ -69,7 +80,7 @@ unsigned MSchedGraphNode::getIteDiff(MSchedGraphNode *succ) { return 0; } - +//Get the index into the vector of edges for the edge from pred to this node unsigned MSchedGraphNode::getInEdgeNum(MSchedGraphNode *pred) { //Loop over all the successors of our predecessor //return the edge the corresponds to this in edge @@ -83,6 +94,8 @@ unsigned MSchedGraphNode::getInEdgeNum(MSchedGraphNode *pred) { assert(0 && "Should have found edge between this node and its predecessor!"); abort(); } + +//Determine if succ is a successor of this node bool MSchedGraphNode::isSuccessor(MSchedGraphNode *succ) { for(succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) if(*I == succ) @@ -90,7 +103,7 @@ bool MSchedGraphNode::isSuccessor(MSchedGraphNode *succ) { return false; } - +//Dtermine if pred is a predecessor of this node bool MSchedGraphNode::isPredecessor(MSchedGraphNode *pred) { if(std::find( Predecessors.begin(), Predecessors.end(), pred) != Predecessors.end()) return true; @@ -98,7 +111,7 @@ bool MSchedGraphNode::isPredecessor(MSchedGraphNode *pred) { return false; } - +//Add a node to the graph void MSchedGraph::addNode(const MachineInstr *MI, MSchedGraphNode *node) { @@ -109,6 +122,7 @@ void MSchedGraph::addNode(const MachineInstr *MI, GraphMap[MI] = node; } +//Delete a node to the graph void MSchedGraph::deleteNode(MSchedGraphNode *node) { //Delete the edge to this node from all predecessors @@ -123,7 +137,10 @@ void MSchedGraph::deleteNode(MSchedGraphNode *node) { } -MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ) +//Create a graph for a machine block. The ignoreInstrs map is so that we ignore instructions +//associated to the index variable since this is a special case in Modulo Scheduling. +//We only want to deal with the body of the loop. +MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ, AliasAnalysis &AA, TargetData &TD, std::map<const MachineInstr*, unsigned> &ignoreInstrs) : BB(bb), Target(targ) { //Make sure BB is not null, @@ -132,9 +149,13 @@ MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ) //DEBUG(std::cerr << "Constructing graph for " << bb << "\n"); //Create nodes and edges for this BB - buildNodesAndEdges(); + buildNodesAndEdges(AA, TD, ignoreInstrs); + + //Experimental! + //addBranchEdges(); } +//Copies the graph and keeps a map from old to new nodes MSchedGraph::MSchedGraph(const MSchedGraph &G, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes) : BB(G.BB), Target(G.Target) { @@ -169,13 +190,86 @@ MSchedGraph::MSchedGraph(const MSchedGraph &G, std::map<MSchedGraphNode*, MSched } } - +//Deconstructor, deletes all nodes in the graph MSchedGraph::~MSchedGraph () { for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I) delete I->second; } -void MSchedGraph::buildNodesAndEdges() { + +//Experimental code to add edges from the branch to all nodes dependent upon it. +void hasPath(MSchedGraphNode *node, std::set<MSchedGraphNode*> &visited, + std::set<MSchedGraphNode*> &branches, MSchedGraphNode *startNode, + std::set<std::pair<MSchedGraphNode*,MSchedGraphNode*> > &newEdges ) { + + visited.insert(node); + DEBUG(std::cerr << "Visiting: " << *node << "\n"); + //Loop over successors + for(unsigned i = 0; i < node->succ_size(); ++i) { + MSchedGraphEdge *edge = node->getSuccessor(i); + MSchedGraphNode *dest = edge->getDest(); + if(branches.count(dest)) + newEdges.insert(std::make_pair(dest, startNode)); + + //only visit if we have not already + else if(!visited.count(dest)) { + if(edge->getIteDiff() == 0) + hasPath(dest, visited, branches, startNode, newEdges);} + + } + +} + +//Experimental code to add edges from the branch to all nodes dependent upon it. +void MSchedGraph::addBranchEdges() { + std::set<MSchedGraphNode*> branches; + std::set<MSchedGraphNode*> nodes; + + for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I) { + if(I->second->isBranch()) + if(I->second->hasPredecessors()) + branches.insert(I->second); + } + + //See if there is a path first instruction to the branches, if so, add an + //iteration dependence between that node and the branch + std::set<std::pair<MSchedGraphNode*, MSchedGraphNode*> > newEdges; + for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I) { + std::set<MSchedGraphNode*> visited; + hasPath((I->second), visited, branches, (I->second), newEdges); + } + + //Spit out all edges we are going to add + unsigned min = GraphMap.size(); + if(newEdges.size() == 1) { + ((newEdges.begin())->first)->addOutEdge(((newEdges.begin())->second), + MSchedGraphEdge::BranchDep, + MSchedGraphEdge::NonDataDep, 1); + } + else { + + unsigned count = 0; + MSchedGraphNode *start; + MSchedGraphNode *end; + for(std::set<std::pair<MSchedGraphNode*, MSchedGraphNode*> >::iterator I = newEdges.begin(), E = newEdges.end(); I != E; ++I) { + + DEBUG(std::cerr << "Branch Edge from: " << *(I->first) << " to " << *(I->second) << "\n"); + + // if(I->second->getIndex() <= min) { + start = I->first; + end = I->second; + //min = I->second->getIndex(); + //} + start->addOutEdge(end, + MSchedGraphEdge::BranchDep, + MSchedGraphEdge::NonDataDep, 1); + } + } +} + + +//Add edges between the nodes +void MSchedGraph::buildNodesAndEdges(AliasAnalysis &AA, TargetData &TD, std::map<const MachineInstr*, unsigned> &ignoreInstrs) { //Get Machine target information for calculating latency const TargetInstrInfo *MTI = Target.getInstrInfo(); @@ -190,6 +284,13 @@ void MSchedGraph::buildNodesAndEdges() { //Loop over instructions in MBB and add nodes and edges for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); MI != e; ++MI) { + + //Ignore indvar instructions + if(ignoreInstrs.count(MI)) { + ++index; + continue; + } + //Get each instruction of machine basic block, get the delay //using the op code, create a new node for it, and add to the //graph. @@ -262,7 +363,6 @@ void MSchedGraph::buildNodesAndEdges() { DEBUG(std::cerr << "Read Operation in a PHI node\n"); continue; } - if (const Value* srcI = mOp.getVRegValue()) { @@ -274,7 +374,7 @@ void MSchedGraph::buildNodesAndEdges() { //those instructions //to this one we are processing if(V != valuetoNodeMap.end()) { - addValueEdges(V->second, node, mOp.isUse(), mOp.isDef()); + addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs); //Add to value map V->second.push_back(std::make_pair(i,node)); @@ -295,14 +395,16 @@ void MSchedGraph::buildNodesAndEdges() { if(const PHINode *PN = dyn_cast<PHINode>(I)) { MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(PN); for (unsigned j = 0; j < tempMvec.size(); j++) { - DEBUG(std::cerr << "Inserting phi instr into map: " << *tempMvec[j] << "\n"); - phiInstrs.push_back((MachineInstr*) tempMvec[j]); + if(!ignoreInstrs.count(tempMvec[j])) { + DEBUG(std::cerr << "Inserting phi instr into map: " << *tempMvec[j] << "\n"); + phiInstrs.push_back((MachineInstr*) tempMvec[j]); + } } } } - addMemEdges(memInstructions); + addMemEdges(memInstructions, AA, TD); addMachRegEdges(regNumtoNodeMap); //Finally deal with PHI Nodes and Value* @@ -324,28 +426,30 @@ void MSchedGraph::buildNodesAndEdges() { //Get Operand const MachineOperand &mOp = (*I)->getOperand(i); if((mOp.getType() == MachineOperand::MO_VirtualRegister || mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) { + //find the value in the map if (const Value* srcI = mOp.getVRegValue()) { - + //Find value in the map std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V - = valuetoNodeMap.find(srcI); - + = valuetoNodeMap.find(srcI); + //If there is something in the map already, add edges from //those instructions //to this one we are processing if(V != valuetoNodeMap.end()) { - addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), 1); + addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs, 1); } } } } - } -} + } +} +//Add dependencies for Value*s void MSchedGraph::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap, MSchedGraphNode *destNode, bool nodeIsUse, - bool nodeIsDef, int diff) { + bool nodeIsDef, std::vector<const MachineInstr*> &phiInstrs, int diff) { for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(), E = NodesInMap.end(); I != E; ++I) { @@ -354,26 +458,34 @@ void MSchedGraph::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap, MSchedGraphNode *srcNode = I->second; MachineOperand mOp = srcNode->getInst()->getOperand(I->first); + if(diff > 0) + if(std::find(phiInstrs.begin(), phiInstrs.end(), srcNode->getInst()) == phiInstrs.end()) + continue; + //Node is a Def, so add output dep. if(nodeIsDef) { if(mOp.isUse()) { + DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=anti)\n"); srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep, MSchedGraphEdge::AntiDep, diff); } if(mOp.isDef()) { + DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=output)\n"); srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep, MSchedGraphEdge::OutputDep, diff); } } if(nodeIsUse) { - if(mOp.isDef()) + if(mOp.isDef()) { + DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=true)\n"); srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep, MSchedGraphEdge::TrueDep, diff); + } } } } - +//Add dependencies for machine registers across iterations void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap) { //Loop over all machine registers in the map, and add dependencies //between the instructions that use it @@ -469,7 +581,9 @@ void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& } -void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst) { +//Add edges between all loads and stores +//Can be less strict with alias analysis and data dependence analysis. +void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst, AliasAnalysis &AA, TargetData &TD) { //Get Target machine instruction info const TargetInstrInfo *TMI = Target.getInstrInfo(); @@ -478,51 +592,132 @@ void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst) { //Knowing that they are in execution, add true, anti, and output dependencies for (unsigned srcIndex = 0; srcIndex < memInst.size(); ++srcIndex) { + MachineInstr *srcInst = (MachineInstr*) memInst[srcIndex]->getInst(); + //Get the machine opCode to determine type of memory instruction - MachineOpCode srcNodeOpCode = memInst[srcIndex]->getInst()->getOpcode(); + MachineOpCode srcNodeOpCode = srcInst->getOpcode(); + //All instructions after this one in execution order have an iteration delay of 0 for(unsigned destIndex = srcIndex + 1; destIndex < memInst.size(); ++destIndex) { - - //source is a Load, so add anti-dependencies (store after load) - if(TMI->isLoad(srcNodeOpCode)) - if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, - MSchedGraphEdge::AntiDep); - + + MachineInstr *destInst = (MachineInstr*) memInst[destIndex]->getInst(); + + //Add Anti dependencies (store after load) + //Source is a Load + if(TMI->isLoad(srcNodeOpCode)) { + + //Destination is a store + if(TMI->isStore(destInst->getOpcode())) { + + //Get the Value* that we are reading from the load, always the first op + const MachineOperand &mOp = srcInst->getOperand(0); + assert((mOp.isUse() && (mOp.getType() == MachineOperand::MO_VirtualRegister)) && "Assumed first operand was a use and a value*\n"); + + //Get the value* for the store + const MachineOperand &mOp2 = destInst->getOperand(0); + assert(mOp2.getType() == MachineOperand::MO_VirtualRegister && "Assumed first operand was a value*\n"); + + //Only add the edge if we can't verify that they do not alias + if(AA.alias(mOp2.getVRegValue(), + (unsigned)TD.getTypeSize(mOp2.getVRegValue()->getType()), + mOp.getVRegValue(), + (unsigned)TD.getTypeSize(mOp.getVRegValue()->getType())) + != AliasAnalysis::NoAlias) { + + //Add edge from load to store + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, + MSchedGraphEdge::AntiDep); + } + } + } + //If source is a store, add output and true dependencies if(TMI->isStore(srcNodeOpCode)) { - if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, - MSchedGraphEdge::OutputDep); - else - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, - MSchedGraphEdge::TrueDep); + + //Get the Value* that we are reading from the store (src), always the first op + const MachineOperand &mOp = srcInst->getOperand(0); + assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Assumed first operand was a use and a value*\n"); + + //Get the Value* that we are reading from the load, always the first op + const MachineOperand &mOp2 = srcInst->getOperand(0); + assert((mOp2.isUse() && (mOp2.getType() == MachineOperand::MO_VirtualRegister)) && "Assumed first operand was a use and a value*\n"); + + //Only add the edge if we can't verify that they do not alias + if(AA.alias(mOp2.getVRegValue(), + (unsigned)TD.getTypeSize(mOp2.getVRegValue()->getType()), + mOp.getVRegValue(), + (unsigned)TD.getTypeSize(mOp.getVRegValue()->getType())) + != AliasAnalysis::NoAlias) { + + if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, + MSchedGraphEdge::OutputDep); + else + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, + MSchedGraphEdge::TrueDep); + } } } //All instructions before the src in execution order have an iteration delay of 1 for(unsigned destIndex = 0; destIndex < srcIndex; ++destIndex) { + + MachineInstr *destInst = (MachineInstr*) memInst[destIndex]->getInst(); + //source is a Load, so add anti-dependencies (store after load) - if(TMI->isLoad(srcNodeOpCode)) - if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, - MSchedGraphEdge::AntiDep, 1); + if(TMI->isLoad(srcNodeOpCode)) { + //Get the Value* that we are reading from the load, always the first op + const MachineOperand &mOp = srcInst->getOperand(0); + assert((mOp.isUse() && (mOp.getType() == MachineOperand::MO_VirtualRegister)) && "Assumed first operand was a use and a value*\n"); + + //Get the value* for the store + const MachineOperand &mOp2 = destInst->getOperand(0); + assert(mOp2.getType() == MachineOperand::MO_VirtualRegister && "Assumed first operand was a value*\n"); + + //Only add the edge if we can't verify that they do not alias + if(AA.alias(mOp2.getVRegValue(), + (unsigned)TD.getTypeSize(mOp2.getVRegValue()->getType()), + mOp.getVRegValue(), + (unsigned)TD.getTypeSize(mOp.getVRegValue()->getType())) + != AliasAnalysis::NoAlias) { + if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, + MSchedGraphEdge::AntiDep, 1); + } + } if(TMI->isStore(srcNodeOpCode)) { - if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, - MSchedGraphEdge::OutputDep, 1); - else - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, - MSchedGraphEdge::TrueDep, 1); + + //Get the Value* that we are reading from the store (src), always the first op + const MachineOperand &mOp = srcInst->getOperand(0); + assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Assumed first operand was a use and a value*\n"); + + //Get the Value* that we are reading from the load, always the first op + const MachineOperand &mOp2 = srcInst->getOperand(0); + assert((mOp2.isUse() && (mOp2.getType() == MachineOperand::MO_VirtualRegister)) && "Assumed first operand was a use and a value*\n"); + + //Only add the edge if we can't verify that they do not alias + if(AA.alias(mOp2.getVRegValue(), + (unsigned)TD.getTypeSize(mOp2.getVRegValue()->getType()), + mOp.getVRegValue(), + (unsigned)TD.getTypeSize(mOp.getVRegValue()->getType())) + != AliasAnalysis::NoAlias) { + + if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, + MSchedGraphEdge::OutputDep, 1); + else + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, + MSchedGraphEdge::TrueDep, 1); + } } - + } } diff --git a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h index 4a341ef3c6..ebff43e590 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h +++ b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h @@ -7,37 +7,45 @@ // //===----------------------------------------------------------------------===// // -// A graph class for dependencies -// +// A graph class for dependencies. This graph only contains true, anti, and +// output data dependencies for a given MachineBasicBlock. Dependencies +// across iterations are also computed. Unless data dependence analysis +// is provided, a conservative approach of adding dependencies between all +// loads and stores is taken. //===----------------------------------------------------------------------===// #ifndef LLVM_MSCHEDGRAPH_H #define LLVM_MSCHEDGRAPH_H +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetData.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/iterator" #include <vector> - namespace llvm { + class MSchedGraph; class MSchedGraphNode; template<class IteratorType, class NodeType> class MSchedGraphNodeIterator; - + //MSchedGraphEdge encapsulates the data dependence between nodes. It + //identifies the dependence type, on what, and the iteration + //difference struct MSchedGraphEdge { enum DataDepOrderType { TrueDep, AntiDep, OutputDep, NonDataDep }; enum MSchedGraphEdgeType { - MemoryDep, ValueDep, MachineRegister + MemoryDep, ValueDep, MachineRegister, BranchDep }; + //Get or set edge data MSchedGraphNode *getDest() const { return dest; } unsigned getIteDiff() { return iteDiff; } unsigned getDepOrderType() { return depOrderType; } @@ -55,6 +63,9 @@ namespace llvm { unsigned iteDiff; }; + //MSchedGraphNode represents a machine instruction and its + //corresponding latency. Each node also contains a list of its + //predecessors and sucessors. class MSchedGraphNode { const MachineInstr* Inst; //Machine Instruction @@ -63,9 +74,8 @@ namespace llvm { unsigned latency; //Latency of Instruction bool isBranchInstr; //Is this node the branch instr or not - std::vector<MSchedGraphNode*> Predecessors; //Predecessor Nodes - std::vector<MSchedGraphEdge> Successors; + std::vector<MSchedGraphEdge> Successors; //Successor edges public: MSchedGraphNode(const MachineInstr *inst, MSchedGraph *graph, @@ -73,7 +83,7 @@ namespace llvm { MSchedGraphNode(const MSchedGraphNode &N); - //Iterators + //Iterators - Predecessor and Succussor typedef std::vector<MSchedGraphNode*>::iterator pred_iterator; pred_iterator pred_begin() { return Predecessors.begin(); } pred_iterator pred_end() { return Predecessors.end(); } @@ -83,7 +93,6 @@ namespace llvm { pred_const_iterator pred_begin() const { return Predecessors.begin(); } pred_const_iterator pred_end() const { return Predecessors.end(); } - // Successor iterators. typedef MSchedGraphNodeIterator<std::vector<MSchedGraphEdge>::const_iterator, const MSchedGraphNode> succ_const_iterator; succ_const_iterator succ_begin() const; @@ -93,39 +102,39 @@ namespace llvm { MSchedGraphNode> succ_iterator; succ_iterator succ_begin(); succ_iterator succ_end(); - unsigned succ_size() { return Successors.size(); } + //Get or set predecessor nodes, or successor edges void setPredecessor(unsigned index, MSchedGraphNode *dest) { Predecessors[index] = dest; } - + MSchedGraphNode* getPredecessor(unsigned index) { return Predecessors[index]; } - + MSchedGraphEdge* getSuccessor(unsigned index) { return &Successors[index]; } - + void deleteSuccessor(MSchedGraphNode *node) { for (unsigned i = 0; i != Successors.size(); ++i) if (Successors[i].getDest() == node) { Successors.erase(Successors.begin()+i); node->Predecessors.erase(std::find(node->Predecessors.begin(), node->Predecessors.end(), this)); - --i; + --i; //Decrease index var since we deleted a node } } - - void addOutEdge(MSchedGraphNode *destination, MSchedGraphEdge::MSchedGraphEdgeType type, unsigned deptype, unsigned diff=0) { Successors.push_back(MSchedGraphEdge(destination, type, deptype,diff)); destination->Predecessors.push_back(this); } + + //General methods to get and set data for the node const MachineInstr* getInst() { return Inst; } MSchedGraph* getParent() { return Parent; } bool hasPredecessors() { return (Predecessors.size() > 0); } @@ -139,11 +148,13 @@ namespace llvm { bool isSuccessor(MSchedGraphNode *); bool isPredecessor(MSchedGraphNode *); bool isBranch() { return isBranchInstr; } + //Debug support void print(std::ostream &os) const; void setParent(MSchedGraph *p) { Parent = p; } }; + //Node iterator for graph generation template<class IteratorType, class NodeType> class MSchedGraphNodeIterator : public forward_iterator<NodeType*, ptrdiff_t> { IteratorType I; // std::vector<MSchedGraphEdge>::iterator or const_iterator @@ -219,6 +230,7 @@ namespace llvm { + //Graph class to represent dependence graph class MSchedGraph { const MachineBasicBlock *BB; //Machine basic block @@ -229,20 +241,26 @@ namespace llvm { //Add Nodes and Edges to this graph for our BB typedef std::pair<int, MSchedGraphNode*> OpIndexNodePair; - void buildNodesAndEdges(); + void buildNodesAndEdges(AliasAnalysis &AA, TargetData &TD, std::map<const MachineInstr*, unsigned> &ignoreInstrs); void addValueEdges(std::vector<OpIndexNodePair> &NodesInMap, MSchedGraphNode *node, - bool nodeIsUse, bool nodeIsDef, int diff=0); + bool nodeIsUse, bool nodeIsDef, std::vector<const MachineInstr*> &phiInstrs, int diff=0); void addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap); - void addMemEdges(const std::vector<MSchedGraphNode*>& memInst); + void addMemEdges(const std::vector<MSchedGraphNode*>& memInst, AliasAnalysis &AA, TargetData &TD); + void addBranchEdges(); public: - MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ); + MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ, AliasAnalysis &AA, TargetData &TD, + std::map<const MachineInstr*, unsigned> &ignoreInstrs); + + //Copy constructor with maps to link old nodes to new nodes MSchedGraph(const MSchedGraph &G, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes); + + //Deconstructor! ~MSchedGraph(); - //Add Nodes to the Graph + //Add or delete nodes from the Graph void addNode(const MachineInstr* MI, MSchedGraphNode *node); void deleteNode(MSchedGraphNode *node); @@ -256,21 +274,23 @@ namespace llvm { unsigned size() { return GraphMap.size(); } reverse_iterator rbegin() { return GraphMap.rbegin(); } reverse_iterator rend() { return GraphMap.rend(); } + + //Get Target or original machine basic block const TargetMachine* getTarget() { return &Target; } const MachineBasicBlock* getBB() { return BB; } }; |