From 4f839ccf4905906f6cb4327614c043aa4cafe554 Mon Sep 17 00:00:00 2001 From: Tanya Lattner Date: Thu, 28 Aug 2003 17:12:14 +0000 Subject: Putting my revised version of ModuloScheduling in cvs. This is not complete... git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8179 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp | 1519 +------------------- lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h | 398 +---- lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp | 984 +------------ lib/CodeGen/ModuloScheduling/ModuloScheduling.h | 194 --- .../SparcV9/ModuloScheduling/ModuloSchedGraph.cpp | 1519 +------------------- .../SparcV9/ModuloScheduling/ModuloSchedGraph.h | 398 +---- .../SparcV9/ModuloScheduling/ModuloScheduling.cpp | 984 +------------ .../SparcV9/ModuloScheduling/ModuloScheduling.h | 194 --- 8 files changed, 310 insertions(+), 5880 deletions(-) delete mode 100644 lib/CodeGen/ModuloScheduling/ModuloScheduling.h delete mode 100644 lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h (limited to 'lib') diff --git a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp index a29722aa61..1bdbb1a976 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp +++ b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp @@ -1,1507 +1,130 @@ -//===- ModuloSchedGraph.cpp - Graph datastructure for Modulo Scheduling ---===// -// -// +//===- ModuloSchedGraph.cpp - Modulo Scheduling Graph and Set -*- C++ -*---===// +// +// Description here //===----------------------------------------------------------------------===// -#include "llvm/CodeGen/InstrSelection.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/CodeGen/MachineCodeForInstruction.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/Target/TargetSchedInfo.h" -#include "Support/StringExtras.h" -#include "Support/STLExtras.h" -#include "Support/hash_map" -#include "Support/Statistic.h" -#include "ModuloScheduling.h" #include "ModuloSchedGraph.h" -#include -#include -#include -#include - - -#define UNIDELAY 1 - -using std::cerr; -using std::endl; -using std::vector; - - -/***********member functions for ModuloSchedGraphNode*********/ - - -ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned int in_nodeId, - const BasicBlock * in_bb, - const Instruction * in_inst, - int indexInBB, - const TargetMachine & target) - :SchedGraphNodeCommon(in_nodeId, indexInBB), inst(in_inst){ - - if (inst) { - //FIXME: find the latency - //currently set the latency to zero - latency = 0; - } -} - - -/***********member functions for ModuloSchedGraph*********/ - -void -ModuloSchedGraph::addDefUseEdges(const BasicBlock *bb){ - - //collect def instructions, store them in vector - const TargetInstrInfo & mii = target.getInstrInfo(); - vector < ModuloSchedGraphNode * > defVec; - - - //find those def instructions - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; ++I) { - if (I->getType() != Type::VoidTy) { - defVec.push_back(this->getGraphNodeForInst(I)); - } - } - - for (unsigned int i = 0; i < defVec.size(); i++) { - for (Value::use_const_iterator I = defVec[i]->getInst()->use_begin(); - I != defVec[i]->getInst()->use_end(); I++) { - //for each use of a def, add a flow edge from the def instruction to the - //ref instruction - - const Instruction *value = defVec[i]->getInst(); - Instruction *inst = (Instruction *) (*I); - ModuloSchedGraphNode *node = NULL; - - for (BasicBlock::const_iterator ins = bb->begin(), E = bb->end(); - ins != E; ++ins) - if ((const Instruction *) ins == inst) { - node = (*this)[inst]; - break; - } - - - if (node == NULL){ - - //inst is not an instruction in this block - //do nothing - - } else { - // Add a flow edge from the def instruction to the ref instruction - // This is a true dependence, so the delay is equal to the - //delay of the preceding node. - - int delay = 0; - - // self loop will not happen in SSA form - assert(defVec[i] != node && "same node?"); - - MachineCodeForInstruction & tempMvec = - MachineCodeForInstruction::get(value); - for (unsigned j = 0; j < tempMvec.size(); j++) { - MachineInstr *temp = tempMvec[j]; - delay = std::max(delay, mii.minLatency(temp->getOpCode())); - } - - SchedGraphEdge *trueEdge = - new SchedGraphEdge(defVec[i], node, value, - SchedGraphEdge::TrueDep, delay); - - // if the ref instruction is before the def instrution - // then the def instruction must be a phi instruction - // add an anti-dependence edge to from the ref instruction to the def - // instruction - if (node->getOrigIndexInBB() < defVec[i]->getOrigIndexInBB()) { - assert(PHINode::classof(inst) - && "the ref instruction befre def is not PHINode?"); - trueEdge->setIteDiff(1); - } - - } - - } - } -} - -void -ModuloSchedGraph::addCDEdges(const BasicBlock * bb) { - - // find the last instruction in the basic block - // see if it is an branch instruction. - // If yes, then add an edge from each node expcept the last node - // to the last node - - const Instruction *inst = &(bb->back()); - ModuloSchedGraphNode *lastNode = (*this)[inst]; - if (TerminatorInst::classof(inst)) - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; - I++) { - if (inst != I) { - ModuloSchedGraphNode *node = (*this)[I]; - //use latency of 0 - (void) new SchedGraphEdge(node, lastNode, SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - } - - } -} - -static const int SG_LOAD_REF = 0; -static const int SG_STORE_REF = 1; -static const int SG_CALL_REF = 2; - -static const unsigned int SG_DepOrderArray[][3] = { - {SchedGraphEdge::NonDataDep, - SchedGraphEdge::AntiDep, - SchedGraphEdge::AntiDep}, - {SchedGraphEdge::TrueDep, - SchedGraphEdge::OutputDep, - SchedGraphEdge::TrueDep | SchedGraphEdge::OutputDep}, - {SchedGraphEdge::TrueDep, - SchedGraphEdge::AntiDep | SchedGraphEdge::OutputDep, - SchedGraphEdge::TrueDep | SchedGraphEdge::AntiDep - | SchedGraphEdge::OutputDep} -}; - - -// Add a dependence edge between every pair of machine load/store/call -// instructions, where at least one is a store or a call. -// Use latency 1 just to ensure that memory operations are ordered; -// latency does not otherwise matter (true dependences enforce that). -// -void -ModuloSchedGraph::addMemEdges(const BasicBlock * bb) { - - vector memNodeVec; - - //construct the memNodeVec - for (BasicBlock::const_iterator I = bb->begin(), - E = bb->end(); I != E; ++I) { - - if (LoadInst::classof(I) || StoreInst::classof(I) - || CallInst::classof(I)) { - - ModuloSchedGraphNode *node = (*this)[(const Instruction *) I]; - memNodeVec.push_back(node); - - } - } - - // Instructions in memNodeVec are in execution order within the - // basic block, so simply look at all pairs - // i]>. - - for (unsigned im = 0, NM = memNodeVec.size(); im < NM; im++) { - - const Instruction *fromInst,*toInst; - int toType, fromType; - - //get the first mem instruction and instruction type - fromInst = memNodeVec[im]->getInst(); - fromType = CallInst::classof(fromInst) ? SG_CALL_REF - : LoadInst::classof(fromInst) ? SG_LOAD_REF : SG_STORE_REF; - - for (unsigned jm = im + 1; jm < NM; jm++) { - - //get the second mem instruction and instruction type - toInst = memNodeVec[jm]->getInst(); - toType = CallInst::classof(toInst) ? SG_CALL_REF - : LoadInst::classof(toInst) ? SG_LOAD_REF : SG_STORE_REF; - - //add two edges if not both of them are LOAD instructions - if (fromType != SG_LOAD_REF || toType != SG_LOAD_REF) { - (void) new SchedGraphEdge(memNodeVec[im], memNodeVec[jm], - SchedGraphEdge::MemoryDep, - SG_DepOrderArray[fromType][toType], 1); - - SchedGraphEdge *edge = - new SchedGraphEdge(memNodeVec[jm], memNodeVec[im], - SchedGraphEdge::MemoryDep, - SG_DepOrderArray[toType][fromType], 1); - - //set the iteration difference for this edge to 1. - edge->setIteDiff(1); - - } - } - } -} - -/* - this function build graph nodes for each instruction - in the basicblock -*/ - -void -ModuloSchedGraph::buildNodesforBB(const TargetMachine &target, - const BasicBlock *bb){ - - int i = 0; - ModuloSchedGraphNode *node; - - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); - I != E; ++I) { - - node=new ModuloSchedGraphNode(getNumNodes(), bb, I, i, target); - - i++; - - this->addHash(I, node); - } - -} - - -/* - determine if this basicblock includes a loop or not -*/ - -bool -ModuloSchedGraph::isLoop(const BasicBlock *bb) { - - //only if the last instruction in the basicblock is branch instruction and - //there is at least an option to branch itself - - const Instruction *inst = &(bb->back()); - - if (BranchInst::classof(inst)) { - for (unsigned i = 0; i < ((BranchInst *) inst)->getNumSuccessors(); - i++) { - BasicBlock *sb = ((BranchInst *) inst)->getSuccessor(i); - if (sb == bb) - return true; - } - } - - return false; - -} - -/* - compute every node's ASAP - -*/ - -//FIXME: now assume the only backward edges come from the edges from other -//nodes to the phi Node so i will ignore all edges to the phi node; after -//this, there shall be no recurrence. - -void -ModuloSchedGraph::computeNodeASAP(const BasicBlock *bb) { - - - unsigned numNodes = bb->size(); - for (unsigned i = 2; i < numNodes + 2; i++) { - ModuloSchedGraphNode *node = getNode(i); - node->setPropertyComputed(false); - } - - for (unsigned i = 2; i < numNodes + 2; i++) { - ModuloSchedGraphNode *node = getNode(i); - node->ASAP = 0; - if (i == 2 || node->getNumInEdges() == 0) { - node->setPropertyComputed(true); - continue; - } - for (ModuloSchedGraphNode::const_iterator I = node->beginInEdges(), E = - node->endInEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - ModuloSchedGraphNode *pred = - (ModuloSchedGraphNode *) (edge->getSrc()); - assert(pred->getPropertyComputed() - && "pred node property is not computed!"); - int temp = - pred->ASAP + edge->getMinDelay() - - edge->getIteDiff() * this->MII; - node->ASAP = std::max(node->ASAP, temp); - } - node->setPropertyComputed(true); - } -} - - -/* - compute every node's ALAP in the basic block -*/ - -void -ModuloSchedGraph::computeNodeALAP(const BasicBlock *bb) { - - unsigned numNodes = bb->size(); - int maxASAP = 0; - for (unsigned i = numNodes + 1; i >= 2; i--) { - - ModuloSchedGraphNode *node = getNode(i); - node->setPropertyComputed(false); - maxASAP = std::max(maxASAP, node->ASAP); - - } - - for (unsigned i = numNodes + 1; i >= 2; i--) { - ModuloSchedGraphNode *node = getNode(i); - - node->ALAP = maxASAP; - - for (ModuloSchedGraphNode::const_iterator I = - node->beginOutEdges(), E = node->endOutEdges(); I != E; I++) { - - SchedGraphEdge *edge = *I; - ModuloSchedGraphNode *succ = - (ModuloSchedGraphNode *) (edge->getSink()); - if (PHINode::classof(succ->getInst())) - continue; - - assert(succ->getPropertyComputed() - && "succ node property is not computed!"); - - int temp = - succ->ALAP - edge->getMinDelay() + - edge->getIteDiff() * this->MII; - - node->ALAP = std::min(node->ALAP, temp); - - } - node->setPropertyComputed(true); - } -} - -/* - compute every node's mov in this basicblock -*/ - -void -ModuloSchedGraph::computeNodeMov(const BasicBlock *bb){ - - unsigned numNodes = bb->size(); - for (unsigned i = 2; i < numNodes + 2; i++) { - - ModuloSchedGraphNode *node = getNode(i); - node->mov = node->ALAP - node->ASAP; - assert(node->mov >= 0 - && "move freedom for this node is less than zero? "); - - } - -} - - -/* - compute every node's depth in this basicblock -*/ -void -ModuloSchedGraph::computeNodeDepth(const BasicBlock * bb){ - - unsigned numNodes = bb->size(); - - for (unsigned i = 2; i < numNodes + 2; i++) { - - ModuloSchedGraphNode *node = getNode(i); - node->setPropertyComputed(false); - - } - - for (unsigned i = 2; i < numNodes + 2; i++) { - - ModuloSchedGraphNode *node = getNode(i); - node->depth = 0; - if (i == 2 || node->getNumInEdges() == 0) { - node->setPropertyComputed(true); - continue; - } - - for (ModuloSchedGraphNode::const_iterator I = node->beginInEdges(), E = - node->endInEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - ModuloSchedGraphNode *pred = - (ModuloSchedGraphNode *) (edge->getSrc()); - assert(pred->getPropertyComputed() - && "pred node property is not computed!"); - int temp = pred->depth + edge->getMinDelay(); - node->depth = std::max(node->depth, temp); - } - node->setPropertyComputed(true); - - } - -} - - -/* - compute every node's height in this basic block -*/ - -void -ModuloSchedGraph::computeNodeHeight(const BasicBlock *bb){ - - unsigned numNodes = bb->size(); - for (unsigned i = numNodes + 1; i >= 2; i--) { - ModuloSchedGraphNode *node = getNode(i); - node->setPropertyComputed(false); - } - - for (unsigned i = numNodes + 1; i >= 2; i--) { - ModuloSchedGraphNode *node = getNode(i); - node->height = 0; - for (ModuloSchedGraphNode::const_iterator I = - node->beginOutEdges(), E = node->endOutEdges(); I != E; ++I) { - SchedGraphEdge *edge = *I; - ModuloSchedGraphNode *succ = - (ModuloSchedGraphNode *) (edge->getSink()); - if (PHINode::classof(succ->getInst())) - continue; - assert(succ->getPropertyComputed() - && "succ node property is not computed!"); - node->height = std::max(node->height, succ->height + edge->getMinDelay()); - - } - node->setPropertyComputed(true); - } - -} - -/* - compute every node's property in a basicblock -*/ - -void ModuloSchedGraph::computeNodeProperty(const BasicBlock * bb) -{ - //FIXME: now assume the only backward edges come from the edges from other - //nodes to the phi Node so i will ignore all edges to the phi node; after - //this, there shall be no recurrence. - - this->computeNodeASAP(bb); - this->computeNodeALAP(bb); - this->computeNodeMov(bb); - this->computeNodeDepth(bb); - this->computeNodeHeight(bb); -} - - -/* - compute the preset of this set without considering the edges - between backEdgeSrc and backEdgeSink -*/ -std::vector -ModuloSchedGraph::predSet(std::vector set, - unsigned backEdgeSrc, - unsigned - backEdgeSink){ - - std::vector predS; - - for (unsigned i = 0; i < set.size(); i++) { - - ModuloSchedGraphNode *node = set[i]; - for (ModuloSchedGraphNode::const_iterator I = node->beginInEdges(), E = - node->endInEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - - //if edges between backEdgeSrc and backEdgeSink, omitted - if (edge->getSrc()->getNodeId() == backEdgeSrc - && edge->getSink()->getNodeId() == backEdgeSink) - continue; - ModuloSchedGraphNode *pred = - (ModuloSchedGraphNode *) (edge->getSrc()); - - //if pred is not in the predSet .... - bool alreadyInset = false; - for (unsigned j = 0; j < predS.size(); ++j) - if (predS[j]->getNodeId() == pred->getNodeId()) { - alreadyInset = true; - break; - } - - // and pred is not in the set .... - for (unsigned j = 0; j < set.size(); ++j) - if (set[j]->getNodeId() == pred->getNodeId()) { - alreadyInset = true; - break; - } - - //push it into the predS - if (!alreadyInset) - predS.push_back(pred); - } - } - return predS; -} - - -/* - return pred set to this set -*/ - -ModuloSchedGraph::NodeVec -ModuloSchedGraph::predSet(NodeVec set){ - - //node number increases from 2, - return predSet(set, 0, 0); -} - -/* - return pred set to _node, ignoring - any edge between backEdgeSrc and backEdgeSink -*/ -std::vector -ModuloSchedGraph::predSet(ModuloSchedGraphNode *_node, - unsigned backEdgeSrc, unsigned backEdgeSink){ - - std::vector set; - set.push_back(_node); - return predSet(set, backEdgeSrc, backEdgeSink); -} - - -/* - return pred set to _node, ignoring -*/ - -std::vector -ModuloSchedGraph::predSet(ModuloSchedGraphNode * _node){ - - return predSet(_node, 0, 0); - -} - -/* - return successor set to the input set - ignoring any edge between src and sink -*/ - -std::vector -ModuloSchedGraph::succSet(std::vector set, - unsigned src, unsigned sink){ - - std::vector succS; - - for (unsigned i = 0; i < set.size(); i++) { - ModuloSchedGraphNode *node = set[i]; - for (ModuloSchedGraphNode::const_iterator I = - node->beginOutEdges(), E = node->endOutEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - - //if the edge is between src and sink, skip - if (edge->getSrc()->getNodeId() == src - && edge->getSink()->getNodeId() == sink) - continue; - ModuloSchedGraphNode *succ = - (ModuloSchedGraphNode *) (edge->getSink()); - - //if pred is not in the successor set .... - bool alreadyInset = false; - for (unsigned j = 0; j < succS.size(); j++) - if (succS[j]->getNodeId() == succ->getNodeId()) { - alreadyInset = true; - break; - } - - //and not in this set .... - for (unsigned j = 0; j < set.size(); j++) - if (set[j]->getNodeId() == succ->getNodeId()) { - alreadyInset = true; - break; - } - - //push it into the successor set - if (!alreadyInset) - succS.push_back(succ); - } - } - return succS; -} - -/* - return successor set to the input set -*/ - -ModuloSchedGraph::NodeVec ModuloSchedGraph::succSet(NodeVec set){ - - return succSet(set, 0, 0); +#include "llvm/Type.h" +ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned id, int index, + const Instruction *inst, + const TargetMachine &targ) + : SchedGraphNodeCommon(id, index), Inst(inst), Target(targ) { } -/* - return successor set to the input node - ignoring any edge between src and sink -*/ - -std::vector -ModuloSchedGraph::succSet(ModuloSchedGraphNode *_node, - unsigned src, unsigned sink){ - - std::vectorset; - - set.push_back(_node); - - return succSet(set, src, sink); - +void ModuloSchedGraphNode::print(std::ostream &os) const { + os << "Modulo Scheduling Node\n"; } -/* - return successor set to the input node -*/ - -std::vector -ModuloSchedGraph::succSet(ModuloSchedGraphNode * _node){ - - return succSet(_node, 0, 0); - -} +ModuloSchedGraph::ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &targ) + : SchedGraphCommon(), BB(bb), Target(targ) { + assert(BB != NULL && "Basic Block is null"); -/* - find maximum delay between srcId and sinkId -*/ + //Builds nodes from each instruction in the basic block + buildNodesForBB(); -SchedGraphEdge* -ModuloSchedGraph::getMaxDelayEdge(unsigned srcId, - unsigned sinkId){ - - ModuloSchedGraphNode *node = getNode(srcId); - SchedGraphEdge *maxDelayEdge = NULL; - int maxDelay = -1; - for (ModuloSchedGraphNode::const_iterator I = node->beginOutEdges(), E = - node->endOutEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - if (edge->getSink()->getNodeId() == sinkId) - if (edge->getMinDelay() > maxDelay) { - maxDelayEdge = edge; - maxDelay = edge->getMinDelay(); - } - } - assert(maxDelayEdge != NULL && "no edge between the srcId and sinkId?"); - return maxDelayEdge; - } -/* - dump all circuits found -*/ - -void -ModuloSchedGraph::dumpCircuits(){ - - DEBUG_PRINT(std::cerr << "dumping circuits for graph:\n"); - int j = -1; - while (circuits[++j][0] != 0) { - int k = -1; - while (circuits[j][++k] != 0) - DEBUG_PRINT(std::cerr << circuits[j][k] << "\t"); - DEBUG_PRINT(std::cerr << "\n"); +void ModuloSchedGraph::buildNodesForBB() { + int count = 0; + for (BasicBlock::const_iterator i = BB->begin(), e = BB->end(); i != e; ++i) { + addNode(i,new ModuloSchedGraphNode(size(), count, i, Target)); + count++; } -} -/* - dump all sets found -*/ + //Get machine instruction(s) for the llvm instruction + //MachineCodeForInstruction &MC = MachineCodeForInstruction::get(Node->first); + -void -ModuloSchedGraph::dumpSet(std::vector < ModuloSchedGraphNode * >set){ - - for (unsigned i = 0; i < set.size(); i++) - DEBUG_PRINT(std::cerr << set[i]->getNodeId() << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } -/* - return union of set1 and set2 -*/ - -std::vector -ModuloSchedGraph::vectorUnion(std::vector set1, - std::vector set2){ - - std::vector unionVec; - for (unsigned i = 0; i < set1.size(); i++) - unionVec.push_back(set1[i]); - for (unsigned j = 0; j < set2.size(); j++) { - bool inset = false; - for (unsigned i = 0; i < unionVec.size(); i++) - if (set2[j] == unionVec[i]) - inset = true; - if (!inset) - unionVec.push_back(set2[j]); - } - return unionVec; +void ModuloSchedGraph::addNode(const Instruction *I, + ModuloSchedGraphNode *node) { + assert(node!= NULL && "New ModuloSchedGraphNode is null"); + GraphMap[I] = node; } -/* - return conjuction of set1 and set2 -*/ -std::vector -ModuloSchedGraph::vectorConj(std::vector set1, - std::vector set2){ +void ModuloSchedGraph::addDepEdges() { - std::vector conjVec; - for (unsigned i = 0; i < set1.size(); i++) - for (unsigned j = 0; j < set2.size(); j++) - if (set1[i] == set2[j]) - conjVec.push_back(set1[i]); - return conjVec; - -} - -/* - return the result of subtracting set2 from set1 - (set1 -set2) -*/ -ModuloSchedGraph::NodeVec -ModuloSchedGraph::vectorSub(NodeVec set1, - NodeVec set2){ + //Get Machine target information for calculating delay + const TargetInstrInfo &MTI = Target.getInstrInfo(); - NodeVec newVec; - for (NodeVec::iterator I = set1.begin(); I != set1.end(); I++) { - - bool inset = false; - for (NodeVec::iterator II = set2.begin(); II != set2.end(); II++) - if ((*I)->getNodeId() == (*II)->getNodeId()) { - inset = true; - break; - } - - if (!inset) - newVec.push_back(*I); + //Loop over instruction in BB and gather dependencies + for(BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) { - } - - return newVec; - -} - -/* - order all nodes in the basicblock - based on the sets information and node property - - output: ordered nodes are stored in oNodes -*/ - -void ModuloSchedGraph::orderNodes() { - oNodes.clear(); - - std::vector < ModuloSchedGraphNode * >set; - unsigned numNodes = bb->size(); - - // first order all the sets - int j = -1; - int totalDelay = -1; - int preDelay = -1; - while (circuits[++j][0] != 0) { - int k = -1; - preDelay = totalDelay; - - while (circuits[j][++k] != 0) { - ModuloSchedGraphNode *node = getNode(circuits[j][k]); - unsigned nextNodeId; - nextNodeId = - circuits[j][k + 1] != 0 ? circuits[j][k + 1] : circuits[j][0]; - SchedGraphEdge *edge = getMaxDelayEdge(circuits[j][k], nextNodeId); - totalDelay += edge->getMinDelay(); - } - if (preDelay != -1 && totalDelay > preDelay) { - // swap circuits[j][] and cuicuits[j-1][] - unsigned temp[MAXNODE]; - for (int k = 0; k < MAXNODE; k++) { - temp[k] = circuits[j - 1][k]; - circuits[j - 1][k] = circuits[j][k]; - circuits[j][k] = temp[k]; - } - //restart - j = -1; - } - } - - - // build the first set - int backEdgeSrc; - int backEdgeSink; - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "building the first set" << "\n"); - int setSeq = -1; - int k = -1; - setSeq++; - while (circuits[setSeq][++k] != 0) - set.push_back(getNode(circuits[setSeq][k])); - if (circuits[setSeq][0] != 0) { - backEdgeSrc = circuits[setSeq][k - 1]; - backEdgeSink = circuits[setSeq][0]; - } - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "the first set is:"); - dumpSet(set); - } - - // implement the ordering algorithm - enum OrderSeq { bottom_up, top_down }; - OrderSeq order; - std::vector R; - while (!set.empty()) { - std::vector pset = predSet(oNodes); - std::vector sset = succSet(oNodes); - - if (!pset.empty() && !vectorConj(pset, set).empty()) { - R = vectorConj(pset, set); - order = bottom_up; - } else if (!sset.empty() && !vectorConj(sset, set).empty()) { - R = vectorConj(sset, set); - order = top_down; - } else { - int maxASAP = -1; - int position = -1; - for (unsigned i = 0; i < set.size(); i++) { - int temp = set[i]->getASAP(); - if (temp > maxASAP) { - maxASAP = temp; - position = i; - } - } - R.push_back(set[position]); - order = bottom_up; - } - - while (!R.empty()) { - if (order == top_down) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "in top_down round\n"); - while (!R.empty()) { - int maxHeight = -1; - NodeVec::iterator chosenI; - for (NodeVec::iterator I = R.begin(); I != R.end(); I++) { - int temp = (*I)->height; - if ((temp > maxHeight) - || (temp == maxHeight && (*I)->mov <= (*chosenI)->mov)) { - - if ((temp > maxHeight) - || (temp == maxHeight && (*I)->mov < (*chosenI)->mov)) { - maxHeight = temp; - chosenI = I; - continue; - } - - //possible case: instruction A and B has the same height and mov, - //but A has dependence to B e.g B is the branch instruction in the - //end, or A is the phi instruction at the beginning - if ((*I)->mov == (*chosenI)->mov) - for (ModuloSchedGraphNode::const_iterator oe = - (*I)->beginOutEdges(), end = (*I)->endOutEdges(); - oe != end; oe++) { - if ((*oe)->getSink() == (*chosenI)) { - maxHeight = temp; - chosenI = I; - continue; - } - } - } - } - - ModuloSchedGraphNode *mu = *chosenI; - oNodes.push_back(mu); - R.erase(chosenI); - std::vector succ_mu = - succSet(mu, backEdgeSrc, backEdgeSink); - std::vector comm = - vectorConj(succ_mu, set); - comm = vectorSub(comm, oNodes); - R = vectorUnion(comm, R); - } - order = bottom_up; - R = vectorConj(predSet(oNodes), set); - } else { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "in bottom up round\n"); - while (!R.empty()) { - int maxDepth = -1; - NodeVec::iterator chosenI; - for (NodeVec::iterator I = R.begin(); I != R.end(); I++) { - int temp = (*I)->depth; - if ((temp > maxDepth) - || (temp == maxDepth && (*I)->mov < (*chosenI)->mov)) { - maxDepth = temp; - chosenI = I; - } - } - ModuloSchedGraphNode *mu = *chosenI; - oNodes.push_back(mu); - R.erase(chosenI); - std::vector pred_mu = - predSet(mu, backEdgeSrc, backEdgeSink); - std::vector comm = - vectorConj(pred_mu, set); - comm = vectorSub(comm, oNodes); - R = vectorUnion(comm, R); - } - order = top_down; - R = vectorConj(succSet(oNodes), set); - } - } - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "order finished\n"); - DEBUG_PRINT(std::cerr << "dumping the ordered nodes:\n"); - dumpSet(oNodes); - dumpCircuits(); - } - - //create a new set - //FIXME: the nodes between onodes and this circuit should also be include in - //this set - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "building the next set\n"); - set.clear(); - int k = -1; - setSeq++; - while (circuits[setSeq][++k] != 0) - set.push_back(getNode(circuits[setSeq][k])); - if (circuits[setSeq][0] != 0) { - backEdgeSrc = circuits[setSeq][k - 1]; - backEdgeSink = circuits[setSeq][0]; - } - - if (set.empty()) { - //no circuits any more - //collect all other nodes - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "no circuits any more, collect the rest nodes\n"); - for (unsigned i = 2; i < numNodes + 2; i++) { - bool inset = false; - for (unsigned j = 0; j < oNodes.size(); j++) - if (oNodes[j]->getNodeId() == i) { - inset = true; - break; - } - if (!inset) - set.push_back(getNode(i)); + //Ignore instructions of the void type + if(I->getType() != Type::VoidTy) { + + //Iterate over def-use chain and add true dependencies + for (Value::use_const_iterator U = I->use_begin(), e = I->use_end(); U != e; + ++U) { + if (Instruction *Inst = dyn_cast(*U)) { + //Check if a node already exists for this instruction + ModuloSchedGraph::iterator Sink = find(Inst); + + //If the instruction is in our graph, add appropriate edges + if(Sink->second != NULL) { + //assert if self loop + assert(&*I == Sink->first && "Use edge to itself!"); + + //Create edge and set delay equal to node latency + //FIXME: Is it safe to do this? + ModuloSchedGraph::iterator Src = find(I); + SchedGraphEdge *trueDep = new SchedGraphEdge(&*Src->second ,&*Sink->second, &*I, + SchedGraphEdge::TrueDep, + Src->second->getLatency()); + //Determine the iteration difference + //FIXME: Will this ever happen? + } + } } } - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "next set is:\n"); - dumpSet(set); - } - } - -} - - - -/* - - build graph for instructions in this basic block - -*/ -void ModuloSchedGraph::buildGraph(const TargetMachine & target) -{ - - assert(this->bb && "The basicBlock is NULL?"); - - // Make a dummy root node. We'll add edges to the real roots later. - graphRoot = new ModuloSchedGraphNode(0, NULL, NULL, -1, target); - graphLeaf = new ModuloSchedGraphNode(1, NULL, NULL, -1, target); - - if (ModuloScheduling::printScheduleProcess()) - this->dump(bb); - - if (isLoop(bb)) { - - DEBUG_PRINT(cerr << "building nodes for this BasicBlock\n"); - buildNodesforBB(target, bb); - DEBUG_PRINT(cerr << "adding def-use edge to this basic block\n"); - this->addDefUseEdges(bb); - - DEBUG_PRINT(cerr << "adding CD edges to this basic block\n"); - this->addCDEdges(bb); - - DEBUG_PRINT(cerr << "adding memory edges to this basicblock\n"); - this->addMemEdges(bb); - - int ResII = this->computeResII(bb); - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "ResII is " << ResII << "\n"); - - int RecII = this->computeRecII(bb); - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "RecII is " << RecII << "\n"); - - this->MII = std::max(ResII, RecII); - - this->computeNodeProperty(bb); - if (ModuloScheduling::printScheduleProcess()) - this->dumpNodeProperty(); - - this->orderNodes(); - - if (ModuloScheduling::printScheduleProcess()) - this->dump(); - } -} - -/* - get node with nodeId -*/ - -ModuloSchedGraphNode * -ModuloSchedGraph::getNode(const unsigned nodeId) const{ - - for (const_iterator I = begin(), E = end(); I != E; I++) - if ((*I).second->getNodeId() == nodeId) - return (ModuloSchedGraphNode *) (*I).second; - return NULL; - -} - -/* - compute RecurrenceII -*/ - -int -ModuloSchedGraph::computeRecII(const BasicBlock *bb){ - - int RecII = 0; - - - //FIXME: only deal with circuits starting at the first node: the phi node - //nodeId=2; - - //search all elementary circuits in the dependence graph - //assume maximum number of nodes is MAXNODE - - unsigned path[MAXNODE]; - unsigned stack[MAXNODE][MAXNODE]; - for (int j = 0; j < MAXNODE; j++) { - path[j] = 0; - for (int k = 0; k < MAXNODE; k++) - stack[j][k] = 0; - } - - //in our graph, the node number starts at 2 - const unsigned numNodes = bb->size(); - - int i = 0; - path[i] = 2; - - ModuloSchedGraphNode *initNode = getNode(path[0]); - unsigned initNodeId = initNode->getNodeId(); - ModuloSchedGraphNode *currentNode = initNode; - - while (currentNode != NULL) { - unsigned currentNodeId = currentNode->getNodeId(); - // DEBUG_PRINT(std::cerr<<"current node is "<beginOutEdges(), E = currentNode->endOutEdges(); - I != E; I++) { - //DEBUG_PRINT(std::cerr <<" searching in outgoint edges of node - //"<getSink()->getNodeId(); - bool inpath = false, instack = false; - int k; - - //DEBUG_PRINT(std::cerr<<"nodeId is "< currentNodeId && !inpath && !instack) { - nextNode = - (ModuloSchedGraphNode *) ((SchedGraphEdge *) * I)->getSink(); - break; - } - } - - if (nextNode != NULL) { - //DEBUG_PRINT(std::cerr<<"find the next Node "<getNodeId()<<"\n"); - - int j = 0; - while (stack[i][j] != 0) - j++; - stack[i][j] = nextNode->getNodeId(); - - i++; - path[i] = nextNode->getNodeId(); - currentNode = nextNode; - } else { - //DEBUG_PRINT(std::cerr<<"no expansion any more"<<"\n"); - //confirmCircuit(); - for (ModuloSchedGraphNode::const_iterator I = - currentNode->beginOutEdges(), E = currentNode->endOutEdges(); - I != E; I++) { - unsigned nodeId = ((SchedGraphEdge *) * I)->getSink()->getNodeId(); - if (nodeId == initNodeId) { - - int j = -1; - while (circuits[++j][0] != 0); - for (int k = 0; k < MAXNODE; k++) - circuits[j][k] = path[k]; - - } - } - //remove this node in the path and clear the corresponding entries in the - //stack - path[i] = 0; - int j = 0; - for (j = 0; j < MAXNODE; j++) - stack[i][j] = 0; - i--; - currentNode = getNode(path[i]); - } - if (i == 0) { - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "circuits found are:\n"); - int j = -1; - while (circuits[++j][0] != 0) { - int k = -1; - while (circuits[j][++k] != 0) - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << circuits[j][k] << "\t"); - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "\n"); - - //for this circuit, compute the sum of all edge delay - int sumDelay = 0; - k = -1; - while (circuits[j][++k] != 0) { - //ModuloSchedGraphNode* node =getNode(circuits[j][k]); - unsigned nextNodeId; - nextNodeId = - circuits[j][k + 1] != - 0 ? circuits[j][k + 1] : circuits[j][0]; - - sumDelay += - getMaxDelayEdge(circuits[j][k], nextNodeId)->getMinDelay(); - - } - // assume we have distance 1, in this case the sumDelay is RecII - // this is correct for SSA form only - // - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "The total Delay in the circuit is " << sumDelay - << "\n"); - - RecII = RecII > sumDelay ? RecII : sumDelay; - - } - return RecII; - } - - } - - return -1; -} - -/* - update resource usage vector (ruVec) -*/ -void -ModuloSchedGraph::addResourceUsage(std::vector > &ruVec, - int rid){ - bool alreadyExists = false; - for (unsigned i = 0; i < ruVec.size(); i++) { - if (rid == ruVec[i].first) { - ruVec[i].second++; - alreadyExists = true; - break; - } - } - if (!alreadyExists) - ruVec.push_back(std::make_pair(rid, 1)); - } -/* - dump the resource usage vector -*/ - -void -ModuloSchedGraph::dumpResourceUsage(std::vector > &ru){ - - TargetSchedInfo & msi = (TargetSchedInfo &) target.getSchedInfo(); - - std::vector > resourceNumVector = msi.resourceNumVector; - DEBUG_PRINT(std::cerr << "resourceID\t" << "resourceNum\n"); - for (unsigned i = 0; i < resourceNumVector.size(); i++) - DEBUG_PRINT(std::cerr << resourceNumVector[i]. - first << "\t" << resourceNumVector[i].second << "\n"); +void ModuloSchedGraph::ASAP() { - DEBUG_PRINT(std::cerr << " maxNumIssueTotal(issue slot in one cycle) = " << msi. - maxNumIssueTotal << "\n"); - DEBUG_PRINT(std::cerr << "resourceID\t resourceUsage\t ResourceNum\n"); - for (unsigned i = 0; i < ru.size(); i++) { - DEBUG_PRINT(std::cerr << ru[i].first << "\t" << ru[i].second); - const unsigned resNum = msi.getCPUResourceNum(ru[i].first); - DEBUG_PRINT(std::cerr << "\t" << resNum << "\n"); - } } -/* - compute thre resource restriction II -*/ +void ModuloSchedGraph::ALAP() { -int -ModuloSchedGraph::computeResII(const BasicBlock * bb){ - - const TargetInstrInfo & mii = target.getInstrInfo(); - const TargetSchedInfo & msi = target.getSchedInfo(); - - int ResII; - std::vector > resourceUsage; - - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; - I++) { - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "machine instruction for llvm instruction( node " << - getGraphNodeForInst(I)->getNodeId() << ")\n"); - DEBUG_PRINT(std::cerr << "\t" << *I); - } - MachineCodeForInstruction & tempMvec = - MachineCodeForInstruction::get(I); - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "size =" << tempMvec.size() << "\n"); - for (unsigned i = 0; i < tempMvec.size(); i++) { - MachineInstr *minstr = tempMvec[i]; - - unsigned minDelay = mii.minLatency(minstr->getOpCode()); - InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode()); - InstrClassRUsage classRUsage = - msi.getClassRUsage(mii.getSchedClass(minstr->getOpCode())); - unsigned totCycles = classRUsage.totCycles; - - std::vector > resources=rUsage.resourcesByCycle; - assert(totCycles == resources.size()); - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "resources Usage for this Instr(totCycles=" - << totCycles << ",mindLatency=" - << mii.minLatency(minstr->getOpCode()) << "): " << *minstr - << "\n"); - for (unsigned j = 0; j < resources.size(); j++) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "cycle " << j << ": "); - for (unsigned k = 0; k < resources[j].size(); k++) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "\t" << resources[j][k]); - addResourceUsage(resourceUsage, resources[j][k]); - } - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "\n"); - } - } - } - if (ModuloScheduling::printScheduleProcess()) - this->dumpResourceUsage(resourceUsage); - //compute ResII - ResII = 0; - int issueSlots = msi.maxNumIssueTotal; - for (unsigned i = 0; i < resourceUsage.size(); i++) { - int resourceNum = msi.getCPUResourceNum(resourceUsage[i].first); - int useNum = resourceUsage[i].second; - double tempII; - if (resourceNum <= issueSlots) - tempII = ceil(1.0 * useNum / resourceNum); - else - tempII = ceil(1.0 * useNum / issueSlots); - ResII = std::max((int) tempII, ResII); - } - return ResII; } +void ModuloSchedGraph::MOB() { - -/* - dump the basicblock -*/ - -void -ModuloSchedGraph::dump(const BasicBlock * bb){ - - DEBUG_PRINT(std::cerr << "dumping basic block:"); - DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block") - << " (" << bb << ")" << "\n"); - } -/* - dump the basicblock to ostream os -*/ +void ModuloSchedGraph::ComputeDepth() { -void -ModuloSchedGraph::dump(const BasicBlock * bb, std::ostream & os){ - - os << "dumping basic block:"; - os << (bb->hasName()? bb->getName() : "block") - << " (" << bb << ")" << "\n"; } -/* - dump the graph -*/ - -void ModuloSchedGraph::dump() const -{ - DEBUG_PRINT(std::cerr << " ModuloSchedGraph for basic Blocks:"); - - DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block") - << " (" << bb << ")" << ""); - - DEBUG_PRINT(std::cerr << "\n\n Actual Root nodes : "); - for (unsigned i = 0, N = graphRoot->outEdges.size(); i < N; i++) - DEBUG_PRINT(std::cerr << graphRoot->outEdges[i]->getSink()->getNodeId() - << ((i == N - 1) ? "" : ", ")); - - DEBUG_PRINT(std::cerr << "\n Graph Nodes:\n"); +void ModuloSchedGraph::ComputeHeight() { - unsigned numNodes = bb->size(); - for (unsigned i = 2; i < numNodes + 2; i++) { - ModuloSchedGraphNode *node = getNode(i); - DEBUG_PRINT(std::cerr << "\n" << *node); - } - - DEBUG_PRINT(std::cerr << "\n"); } - -/* - dump all node property -*/ - -void ModuloSchedGraph::dumpNodeProperty() const -{ - - unsigned numNodes = bb->size(); - for (unsigned i = 2; i < numNodes + 2; i++) { - ModuloSchedGraphNode *node = getNode(i); - DEBUG_PRINT(std::cerr << "NodeId " << node->getNodeId() << "\t"); - DEBUG_PRINT(std::cerr << "ASAP " << node->getASAP() << "\t"); - DEBUG_PRINT(std::cerr << "ALAP " << node->getALAP() << "\t"); - DEBUG_PRINT(std::cerr << "mov " << node->getMov() << "\t"); - DEBUG_PRINT(std::cerr << "depth " << node->getDepth() << "\t"); - DEBUG_PRINT(std::cerr << "height " << node->getHeight() << "\t\n"); - } +void ModuloSchedGraphSet::addGraph(ModuloSchedGraph *graph) { + assert(graph!=NULL && "Graph for BasicBlock is null"); + Graphs.push_back(graph); } +ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *F, + const TargetMachine &targ) + : function(F) { - -/************member functions for ModuloSchedGraphSet**************/ - -/* - constructor -*/ - -ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *function, - const TargetMachine &target) -: method(function){ - - buildGraphsForMethod(method, target); - + //Create graph for each BB in this function + for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI) + addGraph(new ModuloSchedGraph(BI, targ)); } -/* - destructor -*/ - - ModuloSchedGraphSet::~ModuloSchedGraphSet(){ //delete all the graphs - for (iterator I = begin(), E = end(); I != E; ++I) - delete *I; } - - -/* - build graph for each basicblock in this method -*/ - -void -ModuloSchedGraphSet::buildGraphsForMethod(const Function *F, - const TargetMachine &target){ - - for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI){ - const BasicBlock* local_bb; - - local_bb=BI; - addGraph(new ModuloSchedGraph((BasicBlock*)local_bb, target)); - } - -} - -/* - dump the graph set -*/ - -void -ModuloSchedGraphSet::dump() const{ - - DEBUG_PRINT(std::cerr << " ====== ModuloSched graphs for function `" << - method->getName() << "' =========\n\n"); - for (const_iterator I = begin(); I != end(); ++I) - (*I)->dump(); - - DEBUG_PRINT(std::cerr << "\n=========End graphs for function `" << method->getName() - << "' ==========\n\n"); -} - - - - -/********************misc functions***************************/ - - -/* - dump the input basic block -*/ - -static void -dumpBasicBlock(const BasicBlock * bb){ - - DEBUG_PRINT(std::cerr << "dumping basic block:"); - DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block") - << " (" << bb << ")" << "\n"); -} - -/* - dump the input node -*/ - -std::ostream& operator<<(std::ostream &os, - const ModuloSchedGraphNode &node) -{ - os << std::string(8, ' ') - << "Node " << node.nodeId << " : " - << "latency = " << node.latency << "\n" << std::string(12, ' '); - - if (node.getInst() == NULL) - os << "(Dummy node)\n"; - else { - os << *node.getInst() << "\n" << std::string(12, ' '); - os << node.inEdges.size() << " Incoming Edges:\n"; - for (unsigned i = 0, N = node.inEdges.size(); i < N; i++) - os << std::string(16, ' ') << *node.inEdges[i]; - - os << std::string(12, ' ') << node.outEdges.size() - << " Outgoing Edges:\n"; - for (unsigned i = 0, N = node.outEdges.size(); i < N; i++) - os << std::string(16, ' ') << *node.outEdges[i]; - } - - return os; -} diff --git a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h index 2abd448fcd..3404a747ee 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h +++ b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h @@ -1,367 +1,101 @@ //===- ModuloSchedGraph.h - Modulo Scheduling Graph and Set -*- C++ -*-----===// -// -// This header defines the primative classes that make up a data structure -// graph. +// // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_MODULO_SCHED_GRAPH_H -#define LLVM_CODEGEN_MODULO_SCHED_GRAPH_H +#ifndef LLVM_MODULO_SCHED_GRAPH_H +#define LLVM_MODULO_SCHED_GRAPH_H #include "llvm/Instruction.h" +#include "llvm/CodeGen/SchedGraphCommon.h" #include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "Support/GraphTraits.h" +#include "llvm/BasicBlock.h" +#include "llvm/Function.h" #include "Support/hash_map" -#include "../InstrSched/SchedGraphCommon.h" -#include +#include -//===----------------------------------------------------------------------===// -// ModuloSchedGraphNode - Implement a data structure based on the -// SchedGraphNodeCommon this class stores informtion needed later to order the -// nodes in modulo scheduling -// -class ModuloSchedGraphNode:public SchedGraphNodeCommon { -private: - // the corresponding instruction - const Instruction *inst; - // whether this node's property(ASAP,ALAP, ...) has been computed - bool propertyComputed; +class ModuloSchedGraphNode : public SchedGraphNodeCommon { - // ASAP: the earliest time the node could be scheduled - // ALAP: the latest time the node couldbe scheduled - // depth: the depth of the node - // height: the height of the node - // mov: the mobility function, computed as ALAP - ASAP - // scheTime: the scheduled time if this node has been scheduled - // earlyStart: the earliest time to be tried to schedule the node - // lateStart: the latest time to be tried to schedule the node - int ASAP, ALAP, depth, height, mov; - int schTime; - int earlyStart, lateStart; + const Instruction *Inst; //Node's Instruction + unsigned Earliest; //ASAP, or earliest time to be scheduled + unsigned Latest; //ALAP, or latested time to be scheduled + unsigned Depth; //Max Distance from node to the root + unsigned Height; //Max Distance from node to leaf + unsigned Mobility; //MOB, number of time slots it can be scheduled + const TargetMachine &Target; //Target information. public: - - //get the instruction - const Instruction *getInst() const { - return inst; - } - //get the instruction op-code name - const char *getInstOpcodeName() const { - return inst->getOpcodeName(); - } - //get the instruction op-code - const unsigned getInstOpcode() const { - return inst->getOpcode(); - } - - //return whether the node is NULL - bool isNullNode() const { - return (inst == NULL); - } - //return whether the property of the node has been computed - bool getPropertyComputed() { - return propertyComputed; - } - //set the propertyComputed - void setPropertyComputed(bool _propertyComputed) { - propertyComputed = _propertyComputed; - } + ModuloSchedGraphNode(unsigned ID, int index, const Instruction *inst, + const TargetMachine &target); - //get the corresponding property - int getASAP() { - return ASAP; - } - int getALAP() { - return ALAP; - } - int getMov() { - return mov; - } - int getDepth() { - return depth; - } - int getHeight() { - return height; - } - int getSchTime() { - return schTime; - } - int getEarlyStart() { - return earlyStart; - } - int getLateStart() { - return lateStart; - } - void setEarlyStart(int _earlyStart) { - earlyStart = _earlyStart; - } - void setLateStart(int _lateStart) { - lateStart = _lateStart; - } - void setSchTime(int _time) { - schTime = _time; - } - -private: - friend class ModuloSchedGraph; - friend class SchedGraphNode; - - //constructor: - //nodeId: the node id, unique within the each BasicBlock - //_bb: which BasicBlock the corresponding instruction belongs to - //_inst: the corresponding instruction - //indexInBB: the corresponding instruction's index in the BasicBlock - //target: the targetMachine - ModuloSchedGraphNode(unsigned int _nodeId, - const BasicBlock * _bb, - const Instruction * _inst, - int indexInBB, const TargetMachine &target); - + void print(std::ostream &os) const; + const Instruction* getInst() { return Inst; } + unsigned getEarliest() { return Earliest; } + unsigned getLatest() { return Latest; } + unsigned getDepth() { return Depth; } + unsigned getHeight() { return Height; } + unsigned getMobility() { return Mobility; } - friend std::ostream & operator<<(std::ostream & os, - const ModuloSchedGraphNode & edge); - -}; - -//FIXME: these two value should not be used -#define MAXNODE 100 -#define MAXCC 100 - -//===----------------------------------------------------------------------===// -/// ModuloSchedGraph- the data structure to store dependence between nodes -/// it catches data dependence and constrol dependence -/// -class ModuloSchedGraph : - public SchedGraphCommon, - protected hash_map { - -private: - - BasicBlock* bb; - - //iteration Interval - int MII; - - //target machine - const TargetMachine & target; + void setEarliest(unsigned early) { Earliest = early; } + void setLatest(unsigned late) { Latest = late; } + void setDepth(unsigned depth) { Depth = depth; } + void setHeight(unsigned height) { Height = height; } + void setMobility(unsigned mob) { Mobility = mob; } - //the circuits in the dependence graph - unsigned circuits[MAXCC][MAXNODE]; - //the order nodes - std::vector oNodes; - - typedef std::vector NodeVec; - - //the function to compute properties - void computeNodeASAP(const BasicBlock * in_bb); - void computeNodeALAP(const BasicBlock * in_bb); - void computeNodeMov(const BasicBlock * in_bb); - void computeNodeDepth(const BasicBlock * in_bb); - void computeNodeHeight(const BasicBlock * in_bb); - - //the function to compute node property - void computeNodeProperty(const BasicBlock * in_bb); - - //the function to sort nodes - void orderNodes(); - - //add the resource usage -void addResourceUsage(std::vector > &, int); - - //debug functions: - //dump circuits - void dumpCircuits(); - //dump the input set of nodes - void dumpSet(std::vector set); - //dump the input resource usage table - void dumpResourceUsage(std::vector > &); - -public: - //help functions - - //get the maxium the delay between two nodes - SchedGraphEdge *getMaxDelayEdge(unsigned srcId, unsigned sinkId); - - //FIXME: - //get the predessor Set of the set - NodeVec predSet(NodeVec set, unsigned, unsigned); - NodeVec predSet(NodeVec set); - - //get the predessor set of the node - NodeVec predSet(ModuloSchedGraphNode *node, unsigned, unsigned); - NodeVec predSet(ModuloSchedGraphNode *node); - - //get the successor set of the set - NodeVec succSet(NodeVec set, unsigned, unsigned); - NodeVec succSet(NodeVec set); - - //get the succssor set of the node - NodeVec succSet(ModuloSchedGraphNode *node, unsigned, unsigned); - NodeVec succSet(ModuloSchedGraphNode *node); +}; - //return the uniton of the two vectors - NodeVec vectorUnion(NodeVec set1, NodeVec set2); +class ModuloSchedGraph : public SchedGraphCommon { - //return the consjuction of the two vectors - NodeVec vectorConj(NodeVec set1, NodeVec set2); - - //return all nodes in set1 but not set2 - NodeVec vectorSub(NodeVec set1, NodeVec set2); - - typedef hash_map map_base; + const BasicBlock *BB; //The Basic block this graph represents + const TargetMachine &Target; + hash_map GraphMap; -public: - using map_base::iterator; - using map_base::const_iterator; - -public: - - //get target machine - const TargetMachine & getTarget() { - return target; - } - - //get the basic block - BasicBlock* getBasicBlock() const { - return bb; - } - - - //get the iteration interval - const int getMII() { - return MII; - } - - //get the ordered nodes - const NodeVec & getONodes() { - return oNodes; - } - - //get the number of nodes (including the root and leaf) - //note: actually root and leaf is not used - const unsigned int getNumNodes() const { - return size() + 2; - } - - //return wether the BasicBlock 'bb' contains a loop - bool isLoop(const BasicBlock *bb); - - //return the node for the input instruction - ModuloSchedGraphNode *getGraphNodeForInst(const Instruction *inst) const { - const_iterator onePair = this->find(inst); - return (onePair != this->end()) ? (*onePair).second : NULL; - } - - // Debugging support - //dump the graph - void dump() const; - - // dump the basicBlock - void dump(const BasicBlock *bb); - - //dump the basicBlock into 'os' stream - void dump(const BasicBlock *bb, std::ostream &os); - - //dump the node property - void dumpNodeProperty() const; - -private: - friend class ModuloSchedGraphSet; //give access to ctor + void buildNodesForBB(); public: - ModuloSchedGraph(BasicBlock * in_bb, - const TargetMachine & in_target) - :SchedGraphCommon(), bb(in_bb),target(in_target) - { - buildGraph(target); - } - - ~ModuloSchedGraph() { - for (const_iterator I = begin(); I != end(); ++I) - delete I->second; - } - - // Unorder iterators - // return values are pair - using map_base::begin; - using map_base::end; - - void addHash(const Instruction *inst, - ModuloSchedGraphNode *node){ - - assert((*this)[inst] == NULL); - (*this)[inst] = node; - - } - - // Graph builder - ModuloSchedGraphNode *getNode(const unsigned nodeId) const; - - // Build the graph from the basicBlock - void buildGraph(const TargetMachine &target); - - // Build nodes for BasicBlock - void buildNodesforBB(const TargetMachine &target, - const BasicBlock *bb); - - //find definitiona and use information for all nodes - void findDefUseInfoAtInstr(const TargetMachine &target, - ModuloSchedGraphNode *node, - NodeVec &memNode, - RegToRefVecMap ®ToRefVecMap, - ValueToDefVecMap &valueToDefVecMap); - - //add def-use edge - void addDefUseEdges(const BasicBlock *bb); - - //add control dependence edges - void addCDEdges(const BasicBlock *bb); - - //add memory dependence dges - void addMemEdges(const BasicBlock *bb); - - //computer source restrictoin II - int computeResII(const BasicBlock *bb); - - //computer recurrence II - int computeRecII(const BasicBlock *bb); + typedef hash_map::iterator iterator; + typedef hash_map::const_iterator const_iterator; + + + ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &targ); + + const BasicBlock* getBB() { return BB; } + void setBB(BasicBlock *bb) { BB = bb; } + unsigned size() { return GraphMap.size(); } + void addNode(const Instruction *I, ModuloSchedGraphNode *node); + void ASAP(); //Calculate earliest schedule time for all nodes in graph. + void ALAP(); //Calculate latest schedule time for all nodes in graph. + void MOB(); //Calculate mobility for all nodes in the graph. + void ComputeDepth(); //Compute depth of each node in graph + void ComputeHeight(); //Computer height of each node in graph + void addDepEdges(); //Add Dependencies + iterator find(const Instruction *I) { return GraphMap.find(I); } }; -//==================================- -// Graph set -class ModuloSchedGraphSet : public std::vector { -private: - const Function *method; - -public: - typedef std::vector baseVector; - using baseVector::iterator; - using baseVector::const_iterator; +class ModuloSchedGraphSet { + + const Function *function; //Function this set of graphs represent. + std::vector Graphs; public: - ModuloSchedGraphSet(const Function *function, const TargetMachine &target); + typedef std::vector::iterator iterator; + typedef std::vector::const_iterator const_iterator; + + iterator begin() { return Graphs.begin(); } + iterator end() { return Graphs.end(); } + + ModuloSchedGraphSet(const Function *func, const TargetMachine &target); ~ModuloSchedGraphSet(); - // Iterators - using baseVector::begin; - using baseVector::end; - - // Debugging support + void addGraph(ModuloSchedGraph *graph); void dump() const; -private: - void addGraph(ModuloSchedGraph *graph) { - assert(graph != NULL); - this->push_back(graph); - } - // Graph builder - void buildGraphsForMethod(const Function *F, - const TargetMachine &target); }; #endif diff --git a/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp b/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp index 49f4246c02..bad3e97e48 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp @@ -1,983 +1,35 @@ -//===- ModuloScheduling.cpp - Modulo Software Pipelining ------------------===// +//===-- ModuloScheduling.cpp - Software Pipeling Approach - SMS --*- C++ -*--=// // -// Implements the llvm/CodeGen/ModuloScheduling.h interface +// The is a software pipelining pass based on the Swing Modulo Scheduling +// alogrithm (SMS). // //===----------------------------------------------------------------------===// -#include "llvm/BasicBlock.h" -#include "llvm/Constants.h" -#include "llvm/iTerminators.h" -#include "llvm/iPHINode.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineCodeForInstruction.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/InstrSelection.h" -#include "llvm/Target/TargetSchedInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "Support/CommandLine.h" -#include "Support/Statistic.h" #include "ModuloSchedGraph.h" -#include "ModuloScheduling.h" -#include -#include -//************************************************************ -// printing Debug information -// ModuloSchedDebugLevel stores the value of debug level -// modsched_os is the ostream to dump debug information, which is written into -// the file 'moduloSchedDebugInfo.output' -// see ModuloSchedulingPass::runOnFunction() -//************************************************************ +#include "llvm/Pass.h" +#include "llvm/Function.h" -ModuloSchedDebugLevel_t ModuloSchedDebugLevel; - -cl::opt -SDL_opt("modsched", cl::Hidden, cl::location(ModuloSchedDebugLevel), - cl::desc("enable modulo scheduling debugging information"), - cl::values(clEnumValN(ModuloSchedDebugLevel_NoDebugInfo, - "none", "disable debug output"), - clEnumValN(ModuloSchedDebugLevel_PrintSchedule, - "psched", "print original and new schedule"), - clEnumValN(ModuloSchedDebugLevel_PrintScheduleProcess, - "pschedproc", - "print how the new schdule is produced"), - 0)); - -// Computes the schedule and inserts epilogue and prologue -// -void -ModuloScheduling::instrScheduling(){ - - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "************ computing modulo schedule ***********\n"); - - const TargetSchedInfo & msi = target.getSchedInfo(); - - //number of issue slots in the in each cycle - int numIssueSlots = msi.maxNumIssueTotal; - - //compute the schedule - bool success = false; - while (!success) { - //clear memory from the last round and initialize if necessary - clearInitMem(msi); - - //compute schedule and coreSchedule with the current II - success = computeSchedule(); - - if (!success) { - II++; - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "increase II to " << II << "\n"); - } - } - - //print the final schedule - dumpFinalSchedule(); - - //the schedule has been computed - //create epilogue, prologue and kernel BasicBlock - - //find the successor for this BasicBlock - BasicBlock *succ_bb = getSuccBB(bb); - - //print the original BasicBlock if necessary - if (ModuloScheduling::printSchedule()) { - DEBUG_PRINT(std::cerr << "dumping the orginal block\n"); - graph.dump(bb); - } - //construction of prologue, kernel and epilogue - - /* - BasicBlock *kernel = bb->splitBasicBlock(bb->begin()); - BasicBlock *prologue = bb; - BasicBlock *epilogue = kernel->splitBasicBlock(kernel->begin()); - */ - - // Construct prologue - /*constructPrologue(prologue);*/ - - // Construct kernel - - /*constructKernel(prologue, kernel, epilogue);*/ - - // Construct epilogue - - /*constructEpilogue(epilogue, succ_bb);*/ +namespace { - //print the BasicBlocks if necessary -// if (0){ -// DEBUG_PRINT(std::cerr << "dumping the prologue block:\n"); -// graph.dump(prologue); -// DEBUG_PRINT(std::cerr << "dumping the kernel block\n"); -// graph.dump(kernel); -// DEBUG_PRINT(std::cerr << "dumping the epilogue block\n"); -// graph.dump(epilogue); -// } - -} - - -// Clear memory from the last round and initialize if necessary -// - -void -ModuloScheduling::clearInitMem(const TargetSchedInfo & msi){ - - unsigned numIssueSlots = msi.maxNumIssueTotal; - // clear nodeScheduled from the last round - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "***** new round with II= " << II << " ***********\n"); - DEBUG_PRINT(std::cerr << - " ************clear the vector nodeScheduled*************\n"); - } - nodeScheduled.clear(); - - // clear resourceTable from the last round and reset it - resourceTable.clear(); - for (unsigned i = 0; i < II; ++i) - resourceTable.push_back(msi.resourceNumVector); - - // clear the schdule and coreSchedule from the last round - schedule.clear(); - coreSchedule.clear(); - - // create a coreSchedule of size II*numIssueSlots - // each entry is NULL - while (coreSchedule.size() < II) { - std::vector < ModuloSchedGraphNode * >*newCycle = - new std::vector < ModuloSchedGraphNode * >(); - for (unsigned k = 0; k < numIssueSlots; ++k) - newCycle->push_back(NULL); - coreSchedule.push_back(*newCycle); - } -} - -// Compute schedule and coreSchedule with the current II -// -bool -ModuloScheduling::computeSchedule(){ - - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "start to compute schedule\n"); - - // Loop over the ordered nodes - for (NodeVec::const_iterator I = oNodes.begin(); I != oNodes.end(); ++I) { - // Try to schedule for node I - if (ModuloScheduling::printScheduleProcess()) - dumpScheduling(); - ModuloSchedGraphNode *node = *I; - - // Compute whether this node has successor(s) - bool succ = true; - - // Compute whether this node has predessor(s) - bool pred = true; - - NodeVec schSucc = graph.vectorConj(nodeScheduled, graph.succSet(node)); - if (schSucc.empty()) - succ = false; - NodeVec schPred = graph.vectorConj(nodeScheduled, graph.predSet(node)); - if (schPred.empty()) - pred = false; - - //startTime: the earliest time we will try to schedule this node - //endTime: the latest time we will try to schedule this node - int startTime, endTime; - - //node's earlyStart: possible earliest time to schedule this node - //node's lateStart: possible latest time to schedule this node - node->setEarlyStart(-1); - node->setLateStart(9999); - - //this node has predessor but no successor - if (!succ && pred) { - // This node's earlyStart is it's predessor's schedule time + the edge - // delay - the iteration difference* II - for (unsigned i = 0; i < schPred.size(); i++) { - ModuloSchedGraphNode *predNode = schPred[i]; - SchedGraphEdge *edge = - graph.getMaxDelayEdge(predNode->getNodeId(), - node->getNodeId()); - int temp = - predNode->getSchTime() + edge->getMinDelay() - - edge->getIteDiff() * II; - node->setEarlyStart(std::max(node->getEarlyStart(), temp)); - } - startTime = node->getEarlyStart(); - endTime = node->getEarlyStart() + II - 1; - } - // This node has a successor but no predecessor - if (succ && !pred) { - for (unsigned i = 0; i < schSucc.size(); ++i) { - ModuloSchedGraphNode *succNode = schSucc[i]; - SchedGraphEdge *edge = - graph.getMaxDelayEdge(succNode->getNodeId(), - node->getNodeId()); - int temp = - succNode->getSchTime() - edge->getMinDelay() + - edge->getIteDiff() * II; - node->setLateStart(std::min(node->getEarlyStart(), temp)); - } - startTime = node->getLateStart() - II + 1; - endTime = node->getLateStart(); - } - // This node has both successors and predecessors - if (succ && pred) { - for (unsigned i = 0; i < schPred.size(); ++i) { - ModuloSchedGraphNode *predNode = schPred[i]; - SchedGraphEdge *edge = - graph.getMaxDelayEdge(predNode->getNodeId(), - node->getNodeId()); - int temp = - predNode->getSchTime() + edge->getMinDelay() - - edge->getIteDiff() * II; - node->setEarlyStart(std::max(node->getEarlyStart(), temp)); - } - for (unsigned i = 0; i < schSucc.size(); ++i) { - ModuloSchedGraphNode *succNode = schSucc[i]; - SchedGraphEdge *edge = - graph.getMaxDelayEdge(succNode->getNodeId(), - node->getNodeId()); - int temp = - succNode->getSchTime() - edge->getMinDelay() + - edge->getIteDiff() * II; - node->setLateStart(std::min(node->getEarlyStart(), temp)); - } - startTime = node->getEarlyStart(); - endTime = std::min(node->getLateStart(), - node->getEarlyStart() + ((int) II) - 1); - } - //this node has no successor or predessor - if (!succ && !pred) { - node->setEarlyStart(node->getASAP()); - startTime = node->getEarlyStart(); - endTime = node->getEarlyStart() + II - 1; - } - //try to schedule this node based on the startTime and endTime - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "scheduling the node " << (*I)->getNodeId() << "\n"); - - bool success = - this->ScheduleNode(node, startTime, endTime, nodeScheduled); - if (!success) - return false; - } - return true; -} - - -// Get the successor of the BasicBlock -// -BasicBlock * -ModuloScheduling::getSuccBB(BasicBlock *bb){ - - BasicBlock *succ_bb; - for (unsigned i = 0; i < II; ++i) - for (unsigned j = 0; j < coreSchedule[i].size(); ++j) - if (coreSchedule[i][j]) { - const Instruction *ist = coreSchedule[i][j]->getInst(); - - //we can get successor from the BranchInst instruction - //assume we only have one successor (besides itself) here - if (BranchInst::classof(ist)) { - BranchInst *bi = (BranchInst *) ist; - assert(bi->isConditional() && - "the branchInst is not a conditional one"); - assert(bi->getNumSuccessors() == 2 - && " more than two successors?"); - BasicBlock *bb1 = bi->getSuccessor(0); - BasicBlock *bb2 = bi->getSuccessor(1); - assert((bb1 == bb || bb2 == bb) && - " None of its successors is itself?"); - if (bb1 == bb) - succ_bb = bb2; - else - succ_bb = bb1; - return succ_bb; - } - } - assert(0 && "NO Successor?"); - return NULL; -} - - -// Get the predecessor of the BasicBlock -// -BasicBlock * -ModuloScheduling::getPredBB(BasicBlock *bb){ - - BasicBlock *pred_bb; - for (unsigned i = 0; i < II; ++i) - for (unsigned j = 0; j < coreSchedule[i].size(); ++j) - if (coreSchedule[i][j]) { - const Instruction *ist = coreSchedule[i][j]->getInst(); - - //we can get predecessor from the PHINode instruction - //assume we only have one predecessor (besides itself) here - if (PHINode::classof(ist)) { - PHINode *phi = (PHINode *) ist; - assert(phi->getNumIncomingValues() == 2 && - " the number of incoming value is not equal to two? "); - BasicBlock *bb1 = phi->getIncomingBlock(0); - BasicBlock *bb2 = phi->getIncomingBlock(1); - assert((bb1 == bb || bb2 == bb) && - " None of its predecessor is itself?"); - if (bb1 == bb) - pred_bb = bb2; - else - pred_bb = bb1; - return pred_bb; - } - } - assert(0 && " no predecessor?"); - return NULL; -} - - -// Construct the prologue -// -void -ModuloScheduling::constructPrologue(BasicBlock *prologue){ - - InstListType & prologue_ist = prologue->getInstList(); - vvNodeType & tempSchedule_prologue = - *(new std::vector >(schedule)); - - //compute the schedule for prologue - unsigned round = 0; - unsigned scheduleSize = schedule.size(); - while (round < scheduleSize / II) { - round++; - for (unsigned i = 0; i < scheduleSize; ++i) { - if (round * II + i >= scheduleSize) - break; - for (unsigned j = 0; j < schedule[i].size(); ++j) { - if (schedule[i][j]) { - assert(tempSchedule_prologue[round * II + i][j] == NULL && - "table not consitent with core table"); - // move the schedule one iteration ahead and overlap with the original - tempSchedule_prologue[round * II + i][j] = schedule[i][j]; - } - } - } - } - - // Clear the clone memory in the core schedule instructions - clearCloneMemory(); - - // Fill in the prologue - for (unsigned i = 0; i < ceil(1.0 * scheduleSize / II - 1) * II; ++i) - for (unsigned j = 0; j < tempSchedule_prologue[i].size(); ++j) - if (tempSchedule_prologue[i][j]) { - - //get the instruction - Instruction *orn = - (Instruction *) tempSchedule_prologue[i][j]->getInst(); - - //made a clone of it - Instruction *cln = cloneInstSetMemory(orn); - - //insert the instruction - prologue_ist.insert(prologue_ist.back(), cln); - - //if there is PHINode in the prologue, the incoming value from itself - //should be removed because it is not a loop any longer - if (PHINode::classof(cln)) { - PHINode *phi = (PHINode *) cln; - phi->removeIncomingValue(phi->getParent()); - } - } -} - - -// Construct the kernel BasicBlock -// -void -ModuloScheduling::constructKernel(BasicBlock *prologue, - BasicBlock *kernel, - BasicBlock *epilogue){ - - //*************fill instructions in the kernel**************** - InstListType & kernel_ist = kernel->getInstList(); - BranchInst *brchInst; - PHINode *phiInst, *phiCln; - - for (unsigned i = 0; i < coreSchedule.size(); ++i) - for (unsigned j = 0; j < coreSchedule[i].size(); ++j) - if (coreSchedule[i][j]) { - - // Take care of branch instruction differently with normal instructions - if (BranchInst::classof(coreSchedule[i][j]->getInst())) { - brchInst = (BranchInst *) coreSchedule[i][j]->getInst(); - continue; - } - // Take care of PHINode instruction differently with normal instructions - if (PHINode::classof(coreSchedule[i][j]->getInst())) { - phiInst = (PHINode *) coreSchedule[i][j]->getInst(); - Instruction *cln = cloneInstSetMemory(phiInst); - kernel_ist.insert(kernel_ist.back(), cln); - phiCln = (PHINode *) cln; - continue; - } - //for normal instructions: made a clone and insert it in the kernel_ist - Instruction *cln = - cloneInstSetMemory((Instruction *) coreSchedule[i][j]-> - getInst()); - kernel_ist.insert(kernel_ist.back(), cln); - } - // The two incoming BasicBlock for PHINode is the prologue and the kernel - // (itself) - phiCln->setIncomingBlock(0, prologue); - phiCln->setIncomingBlock(1, kernel); - - // The incoming value for the kernel (itself) is the new value which is - // computed in the kernel - Instruction *originalVal = (Instruction *) phiInst->getIncomingValue(1); - phiCln->setIncomingValue(1, originalVal->getClone()); - - // Make a clone of the branch instruction and insert it in the end - BranchInst *cln = (BranchInst *) cloneInstSetMemory(brchInst); - kernel_ist.insert(kernel_ist.back(), cln); - - // delete the unconditional branch instruction, which is generated when - // splitting the basicBlock - kernel_ist.erase(--kernel_ist.end()); - - // set the first successor to itself - cln->setSuccessor(0, kernel); - // set the second successor to eiplogue - cln->setSuccessor(1, epilogue); - - //*****change the condition******* - - //get the condition instruction - Instruction *cond = (Instruction *) cln->getCondition(); - - //get the condition's second operand, it should be a constant - Value *operand = cond->getOperand(1); - assert(ConstantSInt::classof(operand)); - - //change the constant in the condtion instruction - ConstantSInt *iteTimes = - ConstantSInt::get(operand->getType(), - ((ConstantSInt *) operand)->getValue() - II + 1); - cond->setOperand(1, iteTimes); - -} - - -// Construct the epilogue -// -void -ModuloScheduling::constructEpilogue(BasicBlock *epilogue, - BasicBlock *succ_bb){ - - //compute the schedule for epilogue - vvNodeType &tempSchedule_epilogue = - *(new std::vector >(schedule)); - unsigned scheduleSize = schedule.size(); - int round = 0; - while (round < ceil(1.0 * scheduleSize / II) - 1) { - round++; - for (unsigned i = 0; i < scheduleSize; i++) { - if (i + round * II >= scheduleSize) - break; - for (unsigned j = 0; j < schedule[i].size(); j++) - if (schedule[i + round * II][j]) { - assert(tempSchedule_epilogue[i][j] == NULL - && "table not consitant with core table"); - - //move the schdule one iteration behind and overlap - tempSchedule_epilogue[i][j] = schedule[i + round * II][j]; - } - } - } - - //fill in the epilogue - InstListType & epilogue_ist = epilogue->getInstList(); - for (unsigned i = II; i < scheduleSize; i++) - for (unsigned j = 0; j < tempSchedule_epilogue[i].size(); j++) - if (tempSchedule_epilogue[i][j]) { - Instruction *inst = - (Instruction *) tempSchedule_epilogue[i][j]->getInst(); - - //BranchInst and PHINode should be treated differently - //BranchInst:unecessary, simly omitted - //PHINode: omitted - if (!BranchInst::classof(inst) && !PHINode::classof(inst)) { - //make a clone instruction and insert it into the epilogue - Instruction *cln = cloneInstSetMemory(inst); - epilogue_ist.push_front(cln); - } - } - - //*************delete the original instructions****************// - //to delete the original instructions, we have to make sure their use is zero - - //update original core instruction's uses, using its clone instread - for (unsigned i = 0; i < II; i++) - for (unsigned j = 0; j < coreSchedule[i].size(); j++) { - if (coreSchedule[i][j]) - updateUseWithClone((Instruction *) coreSchedule[i][j]->getInst()); - } - - //erase these instructions - for (unsigned i = 0; i < II; i++) - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j]) { - Instruction *ist = (Instruction *) coreSchedule[i][j]->getInst(); - ist->getParent()->getInstList().erase(ist); - } - - - - //finally, insert an unconditional branch instruction at the end - epilogue_ist.push_back(new BranchInst(succ_bb)); - -} - - -//------------------------------------------------------------------------------ -//this function replace the value(instruction) ist in other instructions with -//its latest clone i.e. after this function is called, the ist is not used -//anywhere and it can be erased. -//------------------------------------------------------------------------------ -void -ModuloScheduling::updateUseWithClone(Instruction * ist){ - - - while (ist->use_size() > 0) { - bool destroyed = false; - - //other instruction is using this value ist - assert(Instruction::classof(*ist->use_begin())); - Instruction *inst = (Instruction *) (*ist->use_begin()); - - for (unsigned i = 0; i < inst->getNumOperands(); i++) - if (inst->getOperand(i) == ist && ist->getClone()) { - // if the instruction is TmpInstruction, simly delete it because it has - // no parent and it does not belongs to any BasicBlock - if (TmpInstruction::classof(inst)) { - delete inst; - destroyed = true; - break; - } - - //otherwise, set the instruction's operand to the value's clone - inst->setOperand(i, ist->getClone()); - - //the use from the original value ist is destroyed - destroyed = true; - break; - } - if (!destroyed) { - //if the use can not be destroyed , something is wrong - inst->dump(); - assert(0 && "this use can not be destroyed"); - } - } - -} - - -//******************************************************** -//this function clear all clone mememoy -//i.e. set all instruction's clone memory to NULL -//***************************************************** -void -ModuloScheduling::clearCloneMemory(){ - - for (unsigned i = 0; i < coreSchedule.size(); i++) - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j]) - ((Instruction *) coreSchedule[i][j]->getInst())->clearClone(); - -} - - -//****************************************************************************** -// this function make a clone of the instruction orn the cloned instruction will -// use the orn's operands' latest clone as its operands it is done this way -// because LLVM is in SSA form and we should use the correct value -//this fuction also update the instruction orn's latest clone memory -//****************************************************************************** -Instruction * -ModuloScheduling::cloneInstSetMemory(Instruction * orn){ - - // make a clone instruction - Instruction *cln = orn->clone(); - - // update the operands - for (unsigned k = 0; k < orn->getNumOperands(); k++) { - const Value *op = orn->getOperand(k); - if (Instruction::classof(op) && ((Instruction *) op)->getClone()) { - Instruction *op_inst = (Instruction *) op; - cln->setOperand(k, op_inst->getClone()); - } - } - - // update clone memory - orn->setClone(cln); - return cln; -} - - - -bool -ModuloScheduling::ScheduleNode(ModuloSchedGraphNode * node, - unsigned start, unsigned end, - NodeVec & nodeScheduled){ - - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned int numIssueSlots = msi.maxNumIssueTotal; - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "startTime= " << start << " endTime= " << end << "\n"); - bool isScheduled = false; - for (unsigned i = start; i <= end; i++) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << " now try cycle " << i << ":" << "\n"); - for (unsigned j = 0; j < numIssueSlots; j++) { - unsigned int core_i = i % II; - unsigned int core_j = j; - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "\t Trying slot " << j << "..........."); - //check the resouce table, make sure there is no resource conflicts - const Instruction *instr = node->getInst(); - MachineCodeForInstruction & tempMvec = - MachineCodeForInstruction::get(instr); - bool resourceConflict = false; - const TargetInstrInfo & mii = msi.getInstrInfo(); - - if (coreSchedule.size() < core_i + 1 - || !coreSchedule[core_i][core_j]) { - //this->dumpResourceUsageTable(); - int latency = 0; - for (unsigned k = 0; k < tempMvec.size(); k++) { - MachineInstr *minstr = tempMvec[k]; - InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode()); - std::vector < std::vector < resourceId_t > >resources - = rUsage.resourcesByCycle; - updateResourceTable(resources, i + latency); - latency += std::max(mii.minLatency(minstr->getOpCode()), 1); - } - - //this->dumpResourceUsageTable(); - - latency = 0; - if (resourceTableNegative()) { - - //undo-update the resource table - for (unsigned k = 0; k < tempMvec.size(); k++) { - MachineInstr *minstr = tempMvec[k]; - InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode()); - std::vector < std::vector < resourceId_t > >resources - = rUsage.resourcesByCycle; - undoUpdateResourceTable(resources, i + latency); - latency += std::max(mii.minLatency(minstr->getOpCode()), 1); - } - resourceConflict = true; - } - } - if (!resourceConflict && !coreSchedule[core_i][core_j]) { - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << " OK!" << "\n"); - DEBUG_PRINT(std::cerr << "Node " << node->getNodeId() << " scheduled.\n"); - } - //schedule[i][j]=node; - while (schedule.size() <= i) { - std::vector < ModuloSchedGraphNode * >*newCycle = - new std::vector < ModuloSchedGraphNode * >(); - for (unsigned k = 0; k < numIssueSlots; k++) - newCycle->push_back(NULL); - schedule.push_back(*newCycle); - } - std::vector::iterator startIterator; - startIterator = schedule[i].begin(); - schedule[i].insert(startIterator + j, node); - startIterator = schedule[i].begin(); - schedule[i].erase(startIterator + j + 1); - - //update coreSchedule - //coreSchedule[core_i][core_j]=node; - while (coreSchedule.size() <= core_i) { - std::vector *newCycle = - new std::vector(); - for (unsigned k = 0; k < numIssueSlots; k++) - newCycle->push_back(NULL); - coreSchedule.push_back(*newCycle); - } - - startIterator = coreSchedule[core_i].begin(); - coreSchedule[core_i].insert(startIterator + core_j, node); - startIterator = coreSchedule[core_i].begin(); - coreSchedule[core_i].erase(startIterator + core_j + 1); - - node->setSchTime(i); - isScheduled = true; - nodeScheduled.push_back(node); - - break; - } else if (coreSchedule[core_i][core_j]) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << " Slot not available\n"); - } else { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << " Resource conflicts\n"); - } - } - if (isScheduled) - break; - } - //assert(nodeScheduled &&"this node can not be scheduled?"); - return isScheduled; -} - - -void -ModuloScheduling::updateResourceTable(Resources useResources, - int startCycle){ - - for (unsigned i = 0; i < useResources.size(); i++) { - int absCycle = startCycle + i; - int coreCycle = absCycle % II; - std::vector > &resourceRemained = - resourceTable[coreCycle]; - std::vector < unsigned int >&resourceUsed = useResources[i]; - for (unsigned j = 0; j < resourceUsed.size(); j++) { - for (unsigned k = 0; k < resourceRemained.size(); k++) - if ((int) resourceUsed[j] == resourceRemained[k].first) { - resourceRemained[k].second--; - } - } - } -} - -void -ModuloScheduling::undoUpdateResourceTable(Resources useResources, - int startCycle){ - - for (unsigned i = 0; i < useResources.size(); i++) { - int absCycle = startCycle + i; - int coreCycle = absCycle % II; - std::vector > &resourceRemained = - resourceTable[coreCycle]; - std::vector < unsigned int >&resourceUsed = useResources[i]; - for (unsigned j = 0; j < resourceUsed.size(); j++) { - for (unsigned k = 0; k < resourceRemained.size(); k++) - if ((int) resourceUsed[j] == resourceRemained[k].first) { - resourceRemained[k].second++; - } - } - } -} - - -//----------------------------------------------------------------------- -// Function: resourceTableNegative -// return value: -// return false if any element in the resouceTable is negative -// otherwise return true -// Purpose: - -// this function is used to determine if an instruction is eligible for -// schedule at certain cycle -//----------------------------------------------------------------------- - - -bool -ModuloScheduling::resourceTableNegative(){ - - assert(resourceTable.size() == (unsigned) II - && "resouceTable size must be equal to II"); - bool isNegative = false; - for (unsigned i = 0; i < resourceTable.size(); i++) - for (unsigned j = 0; j < resourceTable[i].size(); j++) { - if (resourceTable[i][j].second < 0) { - isNegative = true; - break; - } - } - return isNegative; -} - - -//---------------------------------------------------------------------- -// Function: dumpResouceUsageTable -// Purpose: -// print out ResouceTable for debug -// -//------------------------------------------------------------------------ - -void -ModuloScheduling::dumpResourceUsageTable(){ - - DEBUG_PRINT(std::cerr << "dumping resource usage table\n"); - for (unsigned i = 0; i < resourceTable.size(); i++) { - for (unsigned j = 0; j < resourceTable[i].size(); j++) - DEBUG_PRINT(std::cerr << resourceTable[i][j].first - << ":" << resourceTable[i][j].second << " "); - DEBUG_PRINT(std::cerr << "\n"); - } - -} - -//---------------------------------------------------------------------- -//Function: dumpSchedule -//Purpose: -// print out thisSchedule for debug -// -//----------------------------------------------------------------------- -void -ModuloScheduling::dumpSchedule(vvNodeType thisSchedule){ - - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned numIssueSlots = msi.maxNumIssueTotal; - for (unsigned i = 0; i < numIssueSlots; i++) - DEBUG_PRINT(std::cerr << "\t#"); - DEBUG_PRINT(std::cerr << "\n"); - for (unsigned i = 0; i < thisSchedule.size(); i++) { - DEBUG_PRINT(std::cerr << "cycle" << i << ": "); - for (unsigned j = 0; j < thisSchedule[i].size(); j++) - if (thisSchedule[i][j] != NULL) - DEBUG_PRINT(std::cerr << thisSchedule[i][j]->getNodeId() << "\t"); - else - DEBUG_PRINT(std::cerr << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } -} - - -//---------------------------------------------------- -//Function: dumpScheduling -//Purpose: -// print out the schedule and coreSchedule for debug -// -//------------------------------------------------------- - -void -ModuloScheduling::dumpScheduling(){ - - DEBUG_PRINT(std::cerr << "dump schedule:" << "\n"); - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned numIssueSlots = msi.maxNumIssueTotal; - for (unsigned i = 0; i < numIssueSlots; i++) - DEBUG_PRINT(std::cerr << "\t#"); - DEBUG_PRINT(std::cerr << "\n"); - for (unsigned i = 0; i < schedule.size(); i++) { - DEBUG_PRINT(std::cerr << "cycle" << i << ": "); - for (unsigned j = 0; j < schedule[i].size(); j++) - if (schedule[i][j] != NULL) - DEBUG_PRINT(std::cerr << schedule[i][j]->getNodeId() << "\t"); - else - DEBUG_PRINT(std::cerr << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } - - DEBUG_PRINT(std::cerr << "dump coreSchedule:" << "\n"); - for (unsigned i = 0; i < numIssueSlots; i++) - DEBUG_PRINT(std::cerr << "\t#"); - DEBUG_PRINT(std::cerr << "\n"); - for (unsigned i = 0; i < coreSchedule.size(); i++) { - DEBUG_PRINT(std::cerr << "cycle" << i << ": "); - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j] != NULL) - DEBUG_PRINT(std::cerr << coreSchedule[i][j]->getNodeId() << "\t"); - else - DEBUG_PRINT(std::cerr << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } -} - -/* - print out final schedule -*/ - -void -ModuloScheduling::dumpFinalSchedule(){ - - std::cerr << "dump schedule:" << "\n"; - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned numIssueSlots = msi.maxNumIssueTotal; - - for (unsigned i = 0; i < numIssueSlots; i++) - std::cerr << "\t#"; - std::cerr << "\n"; - - for (unsigned i = 0; i < schedule.size(); i++) { - std::cerr << "cycle" << i << ": "; + class ModuloScheduling : public FunctionPass { - for (unsigned j = 0; j < schedule[i].size(); j++) - if (schedule[i][j] != NULL) - std::cerr << schedule[i][j]->getNodeId() << "\t"; - else - std::cerr << "\t"; - std::cerr << "\n"; - } - - std::cerr << "dump coreSchedule:" << "\n"; - for (unsigned i = 0; i < numIssueSlots; i++) - std::cerr << "\t#"; - std::cerr << "\n"; - - for (unsigned i = 0; i < coreSchedule.size(); i++) { - std::cerr << "cycle" << i << ": "; - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j] != NULL) - std::cerr << coreSchedule[i][j]->getNodeId() << "\t"; - else - std::cerr << "\t"; - std::cerr << "\n"; - } -} - -//--------------------------------------------------------------------------- -// Function: ModuloSchedulingPass -// -// Purpose: -// Entry point for Modulo Scheduling -// Schedules LLVM instruction -// -//--------------------------------------------------------------------------- - -namespace { - class ModuloSchedulingPass:public FunctionPass { - const TargetMachine ⌖ - public: - ModuloSchedulingPass(const TargetMachine &T):target(T) {} - - const char *getPassName() const { - return "Modulo Scheduling"; - } - - // getAnalysisUsage - We use LiveVarInfo... - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - //AU.addRequired(FunctionLiveVarInfo::ID); - } - - bool runOnFunction(Function & F); + virtual bool runOnFunction(Function &F); }; -} // end anonymous namespace + RegisterOpt X("modulo-sched", "Modulo Scheduling/Software Pipelining"); +} -bool -ModuloSchedulingPass::runOnFunction(Function &F){ - - ModuloSchedGraphSet *graphSet = new ModuloSchedGraphSet(&F, target); - - ModuloSchedulingSet ModuloSchedulingSet(*graphSet); - - DEBUG_PRINT(std::cerr<<"runOnFunction in ModuloSchedulingPass returns\n"<<"\n"); - return false; +//Create Modulo Scheduling Pass +Pass *createModuloSchedPass() { + return new ModuloScheduling(); } +//ModuloScheduling::runOnFunction - Main transformation entry point. +bool ModuloScheduling::runOnFunction(Function &F) { + bool Changed = false; -Pass * -createModuloSchedulingPass(const TargetMachine & tgt){ - DEBUG_PRINT(std::cerr<<"creating modulo scheduling\n"); - return new ModuloSchedulingPass(tgt); + return Changed; } + diff --git a/lib/CodeGen/ModuloScheduling/ModuloScheduling.h b/lib/CodeGen/ModuloScheduling/ModuloScheduling.h deleted file mode 100644 index 00cca149da..0000000000 --- a/lib/CodeGen/ModuloScheduling/ModuloScheduling.h +++ /dev/null @@ -1,194 +0,0 @@ -// ModuloScheduling.h -------------------------------------------*- C++ -*-===// -// -// This header defines the the classes ModuloScheduling and -// ModuloSchedulingSet's structure -// -//===----------------------------------------------------------------------===// - - -#ifndef LLVM_CODEGEN_MODULOSCHEDULING_H -#define LLVM_CODEGEN_MODULOSCHEDULING_H - -#include "ModuloSchedGraph.h" -#include -#include - -//#define DEBUG_PRINT(x) x - -#define DEBUG_PRINT(x) - -// for debug information selecton -enum ModuloSchedDebugLevel_t { - ModuloSchedDebugLevel_NoDebugInfo, - ModuloSchedDebugLevel_PrintSchedule, - ModuloSchedDebugLevel_PrintScheduleProcess, -}; - -class ModuloScheduling: NonCopyable { -private: - - typedef std::vector NodeVec; - typedef std::vector > Resources; - - // The graph to feed in - ModuloSchedGraph &graph; - const TargetMachine ⌖ - - // The BasicBlock to be scheduled - BasicBlock *bb; - - // Iteration Interval - // FIXME: II may be a better name for its meaning - unsigned II; - - // The vector containing the nodes which have been scheduled - NodeVec nodeScheduled; - - // The remaining unscheduled nodes - const NodeVec &oNodes; - - // The machine resource table - std::vector > > resourceTable; - - ///the schedule( with many schedule stage) - std::vector > schedule; - - ///the kernel(core) schedule(length = II) - std::vector > coreSchedule; - - typedef BasicBlock::InstListType InstListType; - typedef std::vector > vvNodeType; - - - - - -public: - - ModuloScheduling(ModuloSchedGraph & _graph): - graph(_graph), target(graph.getTarget()), oNodes(graph.getONodes()) - { - II = graph.getMII(); - bb = graph.getBasicBlock(); - instrScheduling(); - }; - - ~ModuloScheduling() {}; - - - - static bool - printSchedule() { - - //return ModuloScheduling::DebugLevel >= DebugLevel_PrintSchedule; - return true; - - - } - static bool - printScheduleProcess() { - - //return DebugLevel >= DebugLevel_PrintScheduleProcess; - return true; - - - } - - // The method to compute schedule and instert epilogue and prologue - void instrScheduling(); - - // Debug functions: - // Dump the schedule and core schedule - void dumpScheduling(); - void dumpFinalSchedule(); - - // Dump the input vector of nodes - // sch: the input vector of nodes - void dumpSchedule(std::vector > sch); - - // Dump the resource usage table - void dumpResourceUsageTable(); - - //*******************internal functions******************************* -private: - //clear memory from the last round and initialize if necessary - void clearInitMem(const TargetSchedInfo&); - - //compute schedule and coreSchedule with the current II - bool computeSchedule(); - - BasicBlock *getSuccBB(BasicBlock *); - BasicBlock *getPredBB(BasicBlock *); - void constructPrologue(BasicBlock *prologue); - void constructKernel(BasicBlock *prologue, - BasicBlock *kernel, - BasicBlock *epilogue); - void constructEpilogue(BasicBlock *epilogue, BasicBlock *succ_bb); - - // update the resource table at the startCycle - // vec: the resouce usage - // startCycle: the start cycle the resouce usage is - void updateResourceTable(std::vector > vec, - int startCycle); - - // un-do the update in the resource table in the startCycle - // vec: the resouce usage - // startCycle: the start cycle the resouce usage is - void undoUpdateResourceTable(std::vector > vec, - int startCycle); - - // return whether the resourcetable has negative element - // this function is called after updateResouceTable() to determine whether a - // node can be scheduled at certain cycle - bool resourceTableNegative(); - - // try to Schedule the node starting from start to end cycle(inclusive) - // if it can be scheduled, put it in the schedule and update nodeScheduled - // node: the node to be scheduled - // start: start cycle - // end : end cycle - // nodeScheduled: a vector storing nodes which has been scheduled - bool ScheduleNode(ModuloSchedGraphNode * node, unsigned start, - unsigned end, NodeVec &nodeScheduled); - - //each instruction has a memory of the latest clone instruction - //the clone instruction can be get using getClone() - //this function clears the memory, i.e. getClone() after calling this function - //returns null - void clearCloneMemory(); - - //this fuction make a clone of this input Instruction and update the clone - //memory - //inst: the instrution to be cloned - Instruction *cloneInstSetMemory(Instruction *inst); - - //this function update each instrutions which uses ist as its operand - //after update, each instruction will use ist's clone as its operand - void updateUseWithClone(Instruction * ist); - -}; - - -class ModuloSchedulingSet: -NonCopyable { -private: - - //the graphSet to feed in - ModuloSchedGraphSet & graphSet; - -public: - - //constructor - //Scheduling graph one by one - ModuloSchedulingSet(ModuloSchedGraphSet _graphSet): graphSet(_graphSet) { - for (unsigned i = 0; i < graphSet.size(); i++) { - ModuloSchedGraph & graph = *(graphSet[i]); - if (graph.isLoop(graph.getBasicBlock())) - ModuloScheduling ModuloScheduling(graph); - } - }; - - ~ModuloSchedulingSet() {}; -}; - -#endif diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.cpp index a29722aa61..1bdbb1a976 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.cpp @@ -1,1507 +1,130 @@ -//===- ModuloSchedGraph.cpp - Graph datastructure for Modulo Scheduling ---===// -// -// +//===- ModuloSchedGraph.cpp - Modulo Scheduling Graph and Set -*- C++ -*---===// +// +// Description here //===----------------------------------------------------------------------===// -#include "llvm/CodeGen/InstrSelection.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/CodeGen/MachineCodeForInstruction.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/Target/TargetSchedInfo.h" -#include "Support/StringExtras.h" -#include "Support/STLExtras.h" -#include "Support/hash_map" -#include "Support/Statistic.h" -#include "ModuloScheduling.h" #include "ModuloSchedGraph.h" -#include -#include -#include -#include - - -#define UNIDELAY 1 - -using std::cerr; -using std::endl; -using std::vector; - - -/***********member functions for ModuloSchedGraphNode*********/ - - -ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned int in_nodeId, - const BasicBlock * in_bb, - const Instruction * in_inst, - int indexInBB, - const TargetMachine & target) - :SchedGraphNodeCommon(in_nodeId, indexInBB), inst(in_inst){ - - if (inst) { - //FIXME: find the latency - //currently set the latency to zero - latency = 0; - } -} - - -/***********member functions for ModuloSchedGraph*********/ - -void -ModuloSchedGraph::addDefUseEdges(const BasicBlock *bb){ - - //collect def instructions, store them in vector - const TargetInstrInfo & mii = target.getInstrInfo(); - vector < ModuloSchedGraphNode * > defVec; - - - //find those def instructions - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; ++I) { - if (I->getType() != Type::VoidTy) { - defVec.push_back(this->getGraphNodeForInst(I)); - } - } - - for (unsigned int i = 0; i < defVec.size(); i++) { - for (Value::use_const_iterator I = defVec[i]->getInst()->use_begin(); - I != defVec[i]->getInst()->use_end(); I++) { - //for each use of a def, add a flow edge from the def instruction to the - //ref instruction - - const Instruction *value = defVec[i]->getInst(); - Instruction *inst = (Instruction *) (*I); - ModuloSchedGraphNode *node = NULL; - - for (BasicBlock::const_iterator ins = bb->begin(), E = bb->end(); - ins != E; ++ins) - if ((const Instruction *) ins == inst) { - node = (*this)[inst]; - break; - } - - - if (node == NULL){ - - //inst is not an instruction in this block - //do nothing - - } else { - // Add a flow edge from the def instruction to the ref instruction - // This is a true dependence, so the delay is equal to the - //delay of the preceding node. - - int delay = 0; - - // self loop will not happen in SSA form - assert(defVec[i] != node && "same node?"); - - MachineCodeForInstruction & tempMvec = - MachineCodeForInstruction::get(value); - for (unsigned j = 0; j < tempMvec.size(); j++) { - MachineInstr *temp = tempMvec[j]; - delay = std::max(delay, mii.minLatency(temp->getOpCode())); - } - - SchedGraphEdge *trueEdge = - new SchedGraphEdge(defVec[i], node, value, - SchedGraphEdge::TrueDep, delay); - - // if the ref instruction is before the def instrution - // then the def instruction must be a phi instruction - // add an anti-dependence edge to from the ref instruction to the def - // instruction - if (node->getOrigIndexInBB() < defVec[i]->getOrigIndexInBB()) { - assert(PHINode::classof(inst) - && "the ref instruction befre def is not PHINode?"); - trueEdge->setIteDiff(1); - } - - } - - } - } -} - -void -ModuloSchedGraph::addCDEdges(const BasicBlock * bb) { - - // find the last instruction in the basic block - // see if it is an branch instruction. - // If yes, then add an edge from each node expcept the last node - // to the last node - - const Instruction *inst = &(bb->back()); - ModuloSchedGraphNode *lastNode = (*this)[inst]; - if (TerminatorInst::classof(inst)) - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; - I++) { - if (inst != I) { - ModuloSchedGraphNode *node = (*this)[I]; - //use latency of 0 - (void) new SchedGraphEdge(node, lastNode, SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - } - - } -} - -static const int SG_LOAD_REF = 0; -static const int SG_STORE_REF = 1; -static const int SG_CALL_REF = 2; - -static const unsigned int SG_DepOrderArray[][3] = { - {SchedGraphEdge::NonDataDep, - SchedGraphEdge::AntiDep, - SchedGraphEdge::AntiDep}, - {SchedGraphEdge::TrueDep, - SchedGraphEdge::OutputDep, - SchedGraphEdge::TrueDep | SchedGraphEdge::OutputDep}, - {SchedGraphEdge::TrueDep, - SchedGraphEdge::AntiDep | SchedGraphEdge::OutputDep, - SchedGraphEdge::TrueDep | SchedGraphEdge::AntiDep - | SchedGraphEdge::OutputDep} -}; - - -// Add a dependence edge between every pair of machine load/store/call -// instructions, where at least one is a store or a call. -// Use latency 1 just to ensure that memory operations are ordered; -// latency does not otherwise matter (true dependences enforce that). -// -void -ModuloSchedGraph::addMemEdges(const BasicBlock * bb) { - - vector memNodeVec; - - //construct the memNodeVec - for (BasicBlock::const_iterator I = bb->begin(), - E = bb->end(); I != E; ++I) { - - if (LoadInst::classof(I) || StoreInst::classof(I) - || CallInst::classof(I)) { - - ModuloSchedGraphNode *node = (*this)[(const Instruction *) I]; - memNodeVec.push_back(node); - - } - } - - // Instructions in memNodeVec are in execution order within the - // basic block, so simply look at all pairs - // i]>. - - for (unsigned im = 0, NM = memNodeVec.size(); im < NM; im++) { - - const Instruction *fromInst,*toInst; - int toType, fromType; - - //get the first mem instruction and instruction type - fromInst = memNodeVec[im]->getInst(); - fromType = CallInst::classof(fromInst) ? SG_CALL_REF - : LoadInst::classof(fromInst) ? SG_LOAD_REF : SG_STORE_REF; - - for (unsigned jm = im + 1; jm < NM; jm++) { - - //get the second mem instruction and instruction type - toInst = memNodeVec[jm]->getInst(); - toType = CallInst::classof(toInst) ? SG_CALL_REF - : LoadInst::classof(toInst) ? SG_LOAD_REF : SG_STORE_REF; - - //add two edges if not both of them are LOAD instructions - if (fromType != SG_LOAD_REF || toType != SG_LOAD_REF) { - (void) new SchedGraphEdge(memNodeVec[im], memNodeVec[jm], - SchedGraphEdge::MemoryDep, - SG_DepOrderArray[fromType][toType], 1); - - SchedGraphEdge *edge = - new SchedGraphEdge(memNodeVec[jm], memNodeVec[im], - SchedGraphEdge::MemoryDep, - SG_DepOrderArray[toType][fromType], 1); - - //set the iteration difference for this edge to 1. - edge->setIteDiff(1); - - } - } - } -} - -/* - this function build graph nodes for each instruction - in the basicblock -*/ - -void -ModuloSchedGraph::buildNodesforBB(const TargetMachine &target, - const BasicBlock *bb){ - - int i = 0; - ModuloSchedGraphNode *node; - - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); - I != E; ++I) { - - node=new ModuloSchedGraphNode(getNumNodes(), bb, I, i, target); - - i++; - - this->addHash(I, node); - } - -} - - -/* - determine if this basicblock includes a loop or not -*/ - -bool -ModuloSchedGraph::isLoop(const BasicBlock *bb) { - - //only if the last instruction in the basicblock is branch instruction and - //there is at least an option to branch itself - - const Instruction *inst = &(bb->back()); - - if (BranchInst::classof(inst)) { - for (unsigned i = 0; i < ((BranchInst *) inst)->getNumSuccessors(); - i++) { - BasicBlock *sb = ((BranchInst *) inst)->getSuccessor(i); - if (sb == bb) - return true; - } - } - - return false; - -} - -/* - compute every node's ASAP - -*/ - -//FIXME: now assume the only backward edges come from the edges from other -//nodes to the phi Node so i will ignore all edges to the phi node; after -//this, there shall be no recurrence. - -void -ModuloSchedGraph::computeNodeASAP(const BasicBlock *bb) { - - - unsigned numNodes = bb->size(); - for (unsigned i = 2; i < numNodes + 2; i++) { - ModuloSchedGraphNode *node = getNode(i); - node->setPropertyComputed(false); - } - - for (unsigned i = 2; i < numNodes + 2; i++) { - ModuloSchedGraphNode *node = getNode(i); - node->ASAP = 0; - if (i == 2 || node->getNumInEdges() == 0) { - node->setPropertyComputed(true); - continue; - } - for (ModuloSchedGraphNode::const_iterator I = node->beginInEdges(), E = - node->endInEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - ModuloSchedGraphNode *pred = - (ModuloSchedGraphNode *) (edge->getSrc()); - assert(pred->getPropertyComputed() - && "pred node property is not computed!"); - int temp = - pred->ASAP + edge->getMinDelay() - - edge->getIteDiff() * this->MII; - node->ASAP = std::max(node->ASAP, temp); - } - node->setPropertyComputed(true); - } -} - - -/* - compute every node's ALAP in the basic block -*/ - -void -ModuloSchedGraph::computeNodeALAP(const BasicBlock *bb) { - - unsigned numNodes = bb->size(); - int maxASAP = 0; - for (unsigned i = numNodes + 1; i >= 2; i--) { - - ModuloSchedGraphNode *node = getNode(i); - node->setPropertyComputed(false); - maxASAP = std::max(maxASAP, node->ASAP); - - } - - for (unsigned i = numNodes + 1; i >= 2; i--) { - ModuloSchedGraphNode *node = getNode(i); - - node->ALAP = maxASAP; - - for (ModuloSchedGraphNode::const_iterator I = - node->beginOutEdges(), E = node->endOutEdges(); I != E; I++) { - - SchedGraphEdge *edge = *I; - ModuloSchedGraphNode *succ = - (ModuloSchedGraphNode *) (edge->getSink()); - if (PHINode::classof(succ->getInst())) - continue; - - assert(succ->getPropertyComputed() - && "succ node property is not computed!"); - - int temp = - succ->ALAP - edge->getMinDelay() + - edge->getIteDiff() * this->MII; - - node->ALAP = std::min(node->ALAP, temp); - - } - node->setPropertyComputed(true); - } -} - -/* - compute every node's mov in this basicblock -*/ - -void -ModuloSchedGraph::computeNodeMov(const BasicBlock *bb){ - - unsigned numNodes = bb->size(); - for (unsigned i = 2; i < numNodes + 2; i++) { - - ModuloSchedGraphNode *node = getNode(i); - node->mov = node->ALAP - node->ASAP; - assert(node->mov >= 0 - && "move freedom for this node is less than zero? "); - - } - -} - - -/* - compute every node's depth in this basicblock -*/ -void -ModuloSchedGraph::computeNodeDepth(const BasicBlock * bb){ - - unsigned numNodes = bb->size(); - - for (unsigned i = 2; i < numNodes + 2; i++) { - - ModuloSchedGraphNode *node = getNode(i); - node->setPropertyComputed(false); - - } - - for (unsigned i = 2; i < numNodes + 2; i++) { - - ModuloSchedGraphNode *node = getNode(i); - node->depth = 0; - if (i == 2 || node->getNumInEdges() == 0) { - node->setPropertyComputed(true); - continue; - } - - for (ModuloSchedGraphNode::const_iterator I = node->beginInEdges(), E = - node->endInEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - ModuloSchedGraphNode *pred = - (ModuloSchedGraphNode *) (edge->getSrc()); - assert(pred->getPropertyComputed() - && "pred node property is not computed!"); - int temp = pred->depth + edge->getMinDelay(); - node->depth = std::max(node->depth, temp); - } - node->setPropertyComputed(true); - - } - -} - - -/* - compute every node's height in this basic block -*/ - -void -ModuloSchedGraph::computeNodeHeight(const BasicBlock *bb){ - - unsigned numNodes = bb->size(); - for (unsigned i = numNodes + 1; i >= 2; i--) { - ModuloSchedGraphNode *node = getNode(i); - node->setPropertyComputed(false); - } - - for (unsigned i = numNodes + 1; i >= 2; i--) { - ModuloSchedGraphNode *node = getNode(i); - node->height = 0; - for (ModuloSchedGraphNode::const_iterator I = - node->beginOutEdges(), E = node->endOutEdges(); I != E; ++I) { - SchedGraphEdge *edge = *I; - ModuloSchedGraphNode *succ = - (ModuloSchedGraphNode *) (edge->getSink()); - if (PHINode::classof(succ->getInst())) - continue; - assert(succ->getPropertyComputed() - && "succ node property is not computed!"); - node->height = std::max(node->height, succ->height + edge->getMinDelay()); - - } - node->setPropertyComputed(true); - } - -} - -/* - compute every node's property in a basicblock -*/ - -void ModuloSchedGraph::computeNodeProperty(const BasicBlock * bb) -{ - //FIXME: now assume the only backward edges come from the edges from other - //nodes to the phi Node so i will ignore all edges to the phi node; after - //this, there shall be no recurrence. - - this->computeNodeASAP(bb); - this->computeNodeALAP(bb); - this->computeNodeMov(bb); - this->computeNodeDepth(bb); - this->computeNodeHeight(bb); -} - - -/* - compute the preset of this set without considering the edges - between backEdgeSrc and backEdgeSink -*/ -std::vector -ModuloSchedGraph::predSet(std::vector set, - unsigned backEdgeSrc, - unsigned - backEdgeSink){ - - std::vector predS; - - for (unsigned i = 0; i < set.size(); i++) { - - ModuloSchedGraphNode *node = set[i]; - for (ModuloSchedGraphNode::const_iterator I = node->beginInEdges(), E = - node->endInEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - - //if edges between backEdgeSrc and backEdgeSink, omitted - if (edge->getSrc()->getNodeId() == backEdgeSrc - && edge->getSink()->getNodeId() == backEdgeSink) - continue; - ModuloSchedGraphNode *pred = - (ModuloSchedGraphNode *) (edge->getSrc()); - - //if pred is not in the predSet .... - bool alreadyInset = false; - for (unsigned j = 0; j < predS.size(); ++j) - if (predS[j]->getNodeId() == pred->getNodeId()) { - alreadyInset = true; - break; - } - - // and pred is not in the set .... - for (unsigned j = 0; j < set.size(); ++j) - if (set[j]->getNodeId() == pred->getNodeId()) { - alreadyInset = true; - break; - } - - //push it into the predS - if (!alreadyInset) - predS.push_back(pred); - } - } - return predS; -} - - -/* - return pred set to this set -*/ - -ModuloSchedGraph::NodeVec -ModuloSchedGraph::predSet(NodeVec set){ - - //node number increases from 2, - return predSet(set, 0, 0); -} - -/* - return pred set to _node, ignoring - any edge between backEdgeSrc and backEdgeSink -*/ -std::vector -ModuloSchedGraph::predSet(ModuloSchedGraphNode *_node, - unsigned backEdgeSrc, unsigned backEdgeSink){ - - std::vector set; - set.push_back(_node); - return predSet(set, backEdgeSrc, backEdgeSink); -} - - -/* - return pred set to _node, ignoring -*/ - -std::vector -ModuloSchedGraph::predSet(ModuloSchedGraphNode * _node){ - - return predSet(_node, 0, 0); - -} - -/* - return successor set to the input set - ignoring any edge between src and sink -*/ - -std::vector -ModuloSchedGraph::succSet(std::vector set, - unsigned src, unsigned sink){ - - std::vector succS; - - for (unsigned i = 0; i < set.size(); i++) { - ModuloSchedGraphNode *node = set[i]; - for (ModuloSchedGraphNode::const_iterator I = - node->beginOutEdges(), E = node->endOutEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - - //if the edge is between src and sink, skip - if (edge->getSrc()->getNodeId() == src - && edge->getSink()->getNodeId() == sink) - continue; - ModuloSchedGraphNode *succ = - (ModuloSchedGraphNode *) (edge->getSink()); - - //if pred is not in the successor set .... - bool alreadyInset = false; - for (unsigned j = 0; j < succS.size(); j++) - if (succS[j]->getNodeId() == succ->getNodeId()) { - alreadyInset = true; - break; - } - - //and not in this set .... - for (unsigned j = 0; j < set.size(); j++) - if (set[j]->getNodeId() == succ->getNodeId()) { - alreadyInset = true; - break; - } - - //push it into the successor set - if (!alreadyInset) - succS.push_back(succ); - } - } - return succS; -} - -/* - return successor set to the input set -*/ - -ModuloSchedGraph::NodeVec ModuloSchedGraph::succSet(NodeVec set){ - - return succSet(set, 0, 0); +#include "llvm/Type.h" +ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned id, int index, + const Instruction *inst, + const TargetMachine &targ) + : SchedGraphNodeCommon(id, index), Inst(inst), Target(targ) { } -/* - return successor set to the input node - ignoring any edge between src and sink -*/ - -std::vector -ModuloSchedGraph::succSet(ModuloSchedGraphNode *_node, - unsigned src, unsigned sink){ - - std::vectorset; - - set.push_back(_node); - - return succSet(set, src, sink); - +void ModuloSchedGraphNode::print(std::ostream &os) const { + os << "Modulo Scheduling Node\n"; } -/* - return successor set to the input node -*/ - -std::vector -ModuloSchedGraph::succSet(ModuloSchedGraphNode * _node){ - - return succSet(_node, 0, 0); - -} +ModuloSchedGraph::ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &targ) + : SchedGraphCommon(), BB(bb), Target(targ) { + assert(BB != NULL && "Basic Block is null"); -/* - find maximum delay between srcId and sinkId -*/ + //Builds nodes from each instruction in the basic block + buildNodesForBB(); -SchedGraphEdge* -ModuloSchedGraph::getMaxDelayEdge(unsigned srcId, - unsigned sinkId){ - - ModuloSchedGraphNode *node = getNode(srcId); - SchedGraphEdge *maxDelayEdge = NULL; - int maxDelay = -1; - for (ModuloSchedGraphNode::const_iterator I = node->beginOutEdges(), E = - node->endOutEdges(); I != E; I++) { - SchedGraphEdge *edge = *I; - if (edge->getSink()->getNodeId() == sinkId) - if (edge->getMinDelay() > maxDelay) { - maxDelayEdge = edge; - maxDelay = edge->getMinDelay(); - } - } - assert(maxDelayEdge != NULL && "no edge between the srcId and sinkId?"); - return maxDelayEdge; - } -/* - dump all circuits found -*/ - -void -ModuloSchedGraph::dumpCircuits(){ - - DEBUG_PRINT(std::cerr << "dumping circuits for graph:\n"); - int j = -1; - while (circuits[++j][0] != 0) { - int k = -1; - while (circuits[j][++k] != 0) - DEBUG_PRINT(std::cerr << circuits[j][k] << "\t"); - DEBUG_PRINT(std::cerr << "\n"); +void ModuloSchedGraph::buildNodesForBB() { + int count = 0; + for (BasicBlock::const_iterator i = BB->begin(), e = BB->end(); i != e; ++i) { + addNode(i,new ModuloSchedGraphNode(size(), count, i, Target)); + count++; } -} -/* - dump all sets found -*/ + //Get machine instruction(s) for the llvm instruction + //MachineCodeForInstruction &MC = MachineCodeForInstruction::get(Node->first); + -void -ModuloSchedGraph::dumpSet(std::vector < ModuloSchedGraphNode * >set){ - - for (unsigned i = 0; i < set.size(); i++) - DEBUG_PRINT(std::cerr << set[i]->getNodeId() << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } -/* - return union of set1 and set2 -*/ - -std::vector -ModuloSchedGraph::vectorUnion(std::vector set1, - std::vector set2){ - - std::vector unionVec; - for (unsigned i = 0; i < set1.size(); i++) - unionVec.push_back(set1[i]); - for (unsigned j = 0; j < set2.size(); j++) { - bool inset = false; - for (unsigned i = 0; i < unionVec.size(); i++) - if (set2[j] == unionVec[i]) - inset = true; - if (!inset) - unionVec.push_back(set2[j]); - } - return unionVec; +void ModuloSchedGraph::addNode(const Instruction *I, + ModuloSchedGraphNode *node) { + assert(node!= NULL && "New ModuloSchedGraphNode is null"); + GraphMap[I] = node; } -/* - return conjuction of set1 and set2 -*/ -std::vector -ModuloSchedGraph::vectorConj(std::vector set1, - std::vector set2){ +void ModuloSchedGraph::addDepEdges() { - std::vector conjVec; - for (unsigned i = 0; i < set1.size(); i++) - for (unsigned j = 0; j < set2.size(); j++) - if (set1[i] == set2[j]) - conjVec.push_back(set1[i]); - return conjVec; - -} - -/* - return the result of subtracting set2 from set1 - (set1 -set2) -*/ -ModuloSchedGraph::NodeVec -ModuloSchedGraph::vectorSub(NodeVec set1, - NodeVec set2){ + //Get Machine target information for calculating delay + const TargetInstrInfo &MTI = Target.getInstrInfo(); - NodeVec newVec; - for (NodeVec::iterator I = set1.begin(); I != set1.end(); I++) { - - bool inset = false; - for (NodeVec::iterator II = set2.begin(); II != set2.end(); II++) - if ((*I)->getNodeId() == (*II)->getNodeId()) { - inset = true; - break; - } - - if (!inset) - newVec.push_back(*I); + //Loop over instruction in BB and gather dependencies + for(BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) { - } - - return newVec; - -} - -/* - order all nodes in the basicblock - based on the sets information and node property - - output: ordered nodes are stored in oNodes -*/ - -void ModuloSchedGraph::orderNodes() { - oNodes.clear(); - - std::vector < ModuloSchedGraphNode * >set; - unsigned numNodes = bb->size(); - - // first order all the sets - int j = -1; - int totalDelay = -1; - int preDelay = -1; - while (circuits[++j][0] != 0) { - int k = -1; - preDelay = totalDelay; - - while (circuits[j][++k] != 0) { - ModuloSchedGraphNode *node = getNode(circuits[j][k]); - unsigned nextNodeId; - nextNodeId = - circuits[j][k + 1] != 0 ? circuits[j][k + 1] : circuits[j][0]; - SchedGraphEdge *edge = getMaxDelayEdge(circuits[j][k], nextNodeId); - totalDelay += edge->getMinDelay(); - } - if (preDelay != -1 && totalDelay > preDelay) { - // swap circuits[j][] and cuicuits[j-1][] - unsigned temp[MAXNODE]; - for (int k = 0; k < MAXNODE; k++) { - temp[k] = circuits[j - 1][k]; - circuits[j - 1][k] = circuits[j][k]; - circuits[j][k] = temp[k]; - } - //restart - j = -1; - } - } - - - // build the first set - int backEdgeSrc; - int backEdgeSink; - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "building the first set" << "\n"); - int setSeq = -1; - int k = -1; - setSeq++; - while (circuits[setSeq][++k] != 0) - set.push_back(getNode(circuits[setSeq][k])); - if (circuits[setSeq][0] != 0) { - backEdgeSrc = circuits[setSeq][k - 1]; - backEdgeSink = circuits[setSeq][0]; - } - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "the first set is:"); - dumpSet(set); - } - - // implement the ordering algorithm - enum OrderSeq { bottom_up, top_down }; - OrderSeq order; - std::vector R; - while (!set.empty()) { - std::vector pset = predSet(oNodes); - std::vector sset = succSet(oNodes); - - if (!pset.empty() && !vectorConj(pset, set).empty()) { - R = vectorConj(pset, set); - order = bottom_up; - } else if (!sset.empty() && !vectorConj(sset, set).empty()) { - R = vectorConj(sset, set); - order = top_down; - } else { - int maxASAP = -1; - int position = -1; - for (unsigned i = 0; i < set.size(); i++) { - int temp = set[i]->getASAP(); - if (temp > maxASAP) { - maxASAP = temp; - position = i; - } - } - R.push_back(set[position]); - order = bottom_up; - } - - while (!R.empty()) { - if (order == top_down) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "in top_down round\n"); - while (!R.empty()) { - int maxHeight = -1; - NodeVec::iterator chosenI; - for (NodeVec::iterator I = R.begin(); I != R.end(); I++) { - int temp = (*I)->height; - if ((temp > maxHeight) - || (temp == maxHeight && (*I)->mov <= (*chosenI)->mov)) { - - if ((temp > maxHeight) - || (temp == maxHeight && (*I)->mov < (*chosenI)->mov)) { - maxHeight = temp; - chosenI = I; - continue; - } - - //possible case: instruction A and B has the same height and mov, - //but A has dependence to B e.g B is the branch instruction in the - //end, or A is the phi instruction at the beginning - if ((*I)->mov == (*chosenI)->mov) - for (ModuloSchedGraphNode::const_iterator oe = - (*I)->beginOutEdges(), end = (*I)->endOutEdges(); - oe != end; oe++) { - if ((*oe)->getSink() == (*chosenI)) { - maxHeight = temp; - chosenI = I; - continue; - } - } - } - } - - ModuloSchedGraphNode *mu = *chosenI; - oNodes.push_back(mu); - R.erase(chosenI); - std::vector succ_mu = - succSet(mu, backEdgeSrc, backEdgeSink); - std::vector comm = - vectorConj(succ_mu, set); - comm = vectorSub(comm, oNodes); - R = vectorUnion(comm, R); - } - order = bottom_up; - R = vectorConj(predSet(oNodes), set); - } else { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "in bottom up round\n"); - while (!R.empty()) { - int maxDepth = -1; - NodeVec::iterator chosenI; - for (NodeVec::iterator I = R.begin(); I != R.end(); I++) { - int temp = (*I)->depth; - if ((temp > maxDepth) - || (temp == maxDepth && (*I)->mov < (*chosenI)->mov)) { - maxDepth = temp; - chosenI = I; - } - } - ModuloSchedGraphNode *mu = *chosenI; - oNodes.push_back(mu); - R.erase(chosenI); - std::vector pred_mu = - predSet(mu, backEdgeSrc, backEdgeSink); - std::vector comm = - vectorConj(pred_mu, set); - comm = vectorSub(comm, oNodes); - R = vectorUnion(comm, R); - } - order = top_down; - R = vectorConj(succSet(oNodes), set); - } - } - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "order finished\n"); - DEBUG_PRINT(std::cerr << "dumping the ordered nodes:\n"); - dumpSet(oNodes); - dumpCircuits(); - } - - //create a new set - //FIXME: the nodes between onodes and this circuit should also be include in - //this set - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "building the next set\n"); - set.clear(); - int k = -1; - setSeq++; - while (circuits[setSeq][++k] != 0) - set.push_back(getNode(circuits[setSeq][k])); - if (circuits[setSeq][0] != 0) { - backEdgeSrc = circuits[setSeq][k - 1]; - backEdgeSink = circuits[setSeq][0]; - } - - if (set.empty()) { - //no circuits any more - //collect all other nodes - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "no circuits any more, collect the rest nodes\n"); - for (unsigned i = 2; i < numNodes + 2; i++) { - bool inset = false; - for (unsigned j = 0; j < oNodes.size(); j++) - if (oNodes[j]->getNodeId() == i) { - inset = true; - break; - } - if (!inset) - set.push_back(getNode(i)); + //Ignore instructions of the void type + if(I->getType() != Type::VoidTy) { + + //Iterate over def-use chain and add true dependencies + for (Value::use_const_iterator U = I->use_begin(), e = I->use_end(); U != e; + ++U) { + if (Instruction *Inst = dyn_cast(*U)) { + //Check if a node already exists for this instruction + ModuloSchedGraph::iterator Sink = find(Inst); + + //If the instruction is in our graph, add appropriate edges + if(Sink->second != NULL) { + //assert if self loop + assert(&*I == Sink->first && "Use edge to itself!"); + + //Create edge and set delay equal to node latency + //FIXME: Is it safe to do this? + ModuloSchedGraph::iterator Src = find(I); + SchedGraphEdge *trueDep = new SchedGraphEdge(&*Src->second ,&*Sink->second, &*I, + SchedGraphEdge::TrueDep, + Src->second->getLatency()); + //Determine the iteration difference + //FIXME: Will this ever happen? + } + } } } - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "next set is:\n"); - dumpSet(set); - } - } - -} - - - -/* - - build graph for instructions in this basic block - -*/ -void ModuloSchedGraph::buildGraph(const TargetMachine & target) -{ - - assert(this->bb && "The basicBlock is NULL?"); - - // Make a dummy root node. We'll add edges to the real roots later. - graphRoot = new ModuloSchedGraphNode(0, NULL, NULL, -1, target); - graphLeaf = new ModuloSchedGraphNode(1, NULL, NULL, -1, target); - - if (ModuloScheduling::printScheduleProcess()) - this->dump(bb); - - if (isLoop(bb)) { - - DEBUG_PRINT(cerr << "building nodes for this BasicBlock\n"); - buildNodesforBB(target, bb); - DEBUG_PRINT(cerr << "adding def-use edge to this basic block\n"); - this->addDefUseEdges(bb); - - DEBUG_PRINT(cerr << "adding CD edges to this basic block\n"); - this->addCDEdges(bb); - - DEBUG_PRINT(cerr << "adding memory edges to this basicblock\n"); - this->addMemEdges(bb); - - int ResII = this->computeResII(bb); - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "ResII is " << ResII << "\n"); - - int RecII = this->computeRecII(bb); - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "RecII is " << RecII << "\n"); - - this->MII = std::max(ResII, RecII); - - this->computeNodeProperty(bb); - if (ModuloScheduling::printScheduleProcess()) - this->dumpNodeProperty(); - - this->orderNodes(); - - if (ModuloScheduling::printScheduleProcess()) - this->dump(); - } -} - -/* - get node with nodeId -*/ - -ModuloSchedGraphNode * -ModuloSchedGraph::getNode(const unsigned nodeId) const{ - - for (const_iterator I = begin(), E = end(); I != E; I++) - if ((*I).second->getNodeId() == nodeId) - return (ModuloSchedGraphNode *) (*I).second; - return NULL; - -} - -/* - compute RecurrenceII -*/ - -int -ModuloSchedGraph::computeRecII(const BasicBlock *bb){ - - int RecII = 0; - - - //FIXME: only deal with circuits starting at the first node: the phi node - //nodeId=2; - - //search all elementary circuits in the dependence graph - //assume maximum number of nodes is MAXNODE - - unsigned path[MAXNODE]; - unsigned stack[MAXNODE][MAXNODE]; - for (int j = 0; j < MAXNODE; j++) { - path[j] = 0; - for (int k = 0; k < MAXNODE; k++) - stack[j][k] = 0; - } - - //in our graph, the node number starts at 2 - const unsigned numNodes = bb->size(); - - int i = 0; - path[i] = 2; - - ModuloSchedGraphNode *initNode = getNode(path[0]); - unsigned initNodeId = initNode->getNodeId(); - ModuloSchedGraphNode *currentNode = initNode; - - while (currentNode != NULL) { - unsigned currentNodeId = currentNode->getNodeId(); - // DEBUG_PRINT(std::cerr<<"current node is "<beginOutEdges(), E = currentNode->endOutEdges(); - I != E; I++) { - //DEBUG_PRINT(std::cerr <<" searching in outgoint edges of node - //"<getSink()->getNodeId(); - bool inpath = false, instack = false; - int k; - - //DEBUG_PRINT(std::cerr<<"nodeId is "< currentNodeId && !inpath && !instack) { - nextNode = - (ModuloSchedGraphNode *) ((SchedGraphEdge *) * I)->getSink(); - break; - } - } - - if (nextNode != NULL) { - //DEBUG_PRINT(std::cerr<<"find the next Node "<getNodeId()<<"\n"); - - int j = 0; - while (stack[i][j] != 0) - j++; - stack[i][j] = nextNode->getNodeId(); - - i++; - path[i] = nextNode->getNodeId(); - currentNode = nextNode; - } else { - //DEBUG_PRINT(std::cerr<<"no expansion any more"<<"\n"); - //confirmCircuit(); - for (ModuloSchedGraphNode::const_iterator I = - currentNode->beginOutEdges(), E = currentNode->endOutEdges(); - I != E; I++) { - unsigned nodeId = ((SchedGraphEdge *) * I)->getSink()->getNodeId(); - if (nodeId == initNodeId) { - - int j = -1; - while (circuits[++j][0] != 0); - for (int k = 0; k < MAXNODE; k++) - circuits[j][k] = path[k]; - - } - } - //remove this node in the path and clear the corresponding entries in the - //stack - path[i] = 0; - int j = 0; - for (j = 0; j < MAXNODE; j++) - stack[i][j] = 0; - i--; - currentNode = getNode(path[i]); - } - if (i == 0) { - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "circuits found are:\n"); - int j = -1; - while (circuits[++j][0] != 0) { - int k = -1; - while (circuits[j][++k] != 0) - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << circuits[j][k] << "\t"); - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "\n"); - - //for this circuit, compute the sum of all edge delay - int sumDelay = 0; - k = -1; - while (circuits[j][++k] != 0) { - //ModuloSchedGraphNode* node =getNode(circuits[j][k]); - unsigned nextNodeId; - nextNodeId = - circuits[j][k + 1] != - 0 ? circuits[j][k + 1] : circuits[j][0]; - - sumDelay += - getMaxDelayEdge(circuits[j][k], nextNodeId)->getMinDelay(); - - } - // assume we have distance 1, in this case the sumDelay is RecII - // this is correct for SSA form only - // - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "The total Delay in the circuit is " << sumDelay - << "\n"); - - RecII = RecII > sumDelay ? RecII : sumDelay; - - } - return RecII; - } - - } - - return -1; -} - -/* - update resource usage vector (ruVec) -*/ -void -ModuloSchedGraph::addResourceUsage(std::vector > &ruVec, - int rid){ - bool alreadyExists = false; - for (unsigned i = 0; i < ruVec.size(); i++) { - if (rid == ruVec[i].first) { - ruVec[i].second++; - alreadyExists = true; - break; - } - } - if (!alreadyExists) - ruVec.push_back(std::make_pair(rid, 1)); - } -/* - dump the resource usage vector -*/ - -void -ModuloSchedGraph::dumpResourceUsage(std::vector > &ru){ - - TargetSchedInfo & msi = (TargetSchedInfo &) target.getSchedInfo(); - - std::vector > resourceNumVector = msi.resourceNumVector; - DEBUG_PRINT(std::cerr << "resourceID\t" << "resourceNum\n"); - for (unsigned i = 0; i < resourceNumVector.size(); i++) - DEBUG_PRINT(std::cerr << resourceNumVector[i]. - first << "\t" << resourceNumVector[i].second << "\n"); +void ModuloSchedGraph::ASAP() { - DEBUG_PRINT(std::cerr << " maxNumIssueTotal(issue slot in one cycle) = " << msi. - maxNumIssueTotal << "\n"); - DEBUG_PRINT(std::cerr << "resourceID\t resourceUsage\t ResourceNum\n"); - for (unsigned i = 0; i < ru.size(); i++) { - DEBUG_PRINT(std::cerr << ru[i].first << "\t" << ru[i].second); - const unsigned resNum = msi.getCPUResourceNum(ru[i].first); - DEBUG_PRINT(std::cerr << "\t" << resNum << "\n"); - } } -/* - compute thre resource restriction II -*/ +void ModuloSchedGraph::ALAP() { -int -ModuloSchedGraph::computeResII(const BasicBlock * bb){ - - const TargetInstrInfo & mii = target.getInstrInfo(); - const TargetSchedInfo & msi = target.getSchedInfo(); - - int ResII; - std::vector > resourceUsage; - - for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; - I++) { - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "machine instruction for llvm instruction( node " << - getGraphNodeForInst(I)->getNodeId() << ")\n"); - DEBUG_PRINT(std::cerr << "\t" << *I); - } - MachineCodeForInstruction & tempMvec = - MachineCodeForInstruction::get(I); - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "size =" << tempMvec.size() << "\n"); - for (unsigned i = 0; i < tempMvec.size(); i++) { - MachineInstr *minstr = tempMvec[i]; - - unsigned minDelay = mii.minLatency(minstr->getOpCode()); - InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode()); - InstrClassRUsage classRUsage = - msi.getClassRUsage(mii.getSchedClass(minstr->getOpCode())); - unsigned totCycles = classRUsage.totCycles; - - std::vector > resources=rUsage.resourcesByCycle; - assert(totCycles == resources.size()); - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "resources Usage for this Instr(totCycles=" - << totCycles << ",mindLatency=" - << mii.minLatency(minstr->getOpCode()) << "): " << *minstr - << "\n"); - for (unsigned j = 0; j < resources.size(); j++) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "cycle " << j << ": "); - for (unsigned k = 0; k < resources[j].size(); k++) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "\t" << resources[j][k]); - addResourceUsage(resourceUsage, resources[j][k]); - } - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "\n"); - } - } - } - if (ModuloScheduling::printScheduleProcess()) - this->dumpResourceUsage(resourceUsage); - //compute ResII - ResII = 0; - int issueSlots = msi.maxNumIssueTotal; - for (unsigned i = 0; i < resourceUsage.size(); i++) { - int resourceNum = msi.getCPUResourceNum(resourceUsage[i].first); - int useNum = resourceUsage[i].second; - double tempII; - if (resourceNum <= issueSlots) - tempII = ceil(1.0 * useNum / resourceNum); - else - tempII = ceil(1.0 * useNum / issueSlots); - ResII = std::max((int) tempII, ResII); - } - return ResII; } +void ModuloSchedGraph::MOB() { - -/* - dump the basicblock -*/ - -void -ModuloSchedGraph::dump(const BasicBlock * bb){ - - DEBUG_PRINT(std::cerr << "dumping basic block:"); - DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block") - << " (" << bb << ")" << "\n"); - } -/* - dump the basicblock to ostream os -*/ +void ModuloSchedGraph::ComputeDepth() { -void -ModuloSchedGraph::dump(const BasicBlock * bb, std::ostream & os){ - - os << "dumping basic block:"; - os << (bb->hasName()? bb->getName() : "block") - << " (" << bb << ")" << "\n"; } -/* - dump the graph -*/ - -void ModuloSchedGraph::dump() const -{ - DEBUG_PRINT(std::cerr << " ModuloSchedGraph for basic Blocks:"); - - DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block") - << " (" << bb << ")" << ""); - - DEBUG_PRINT(std::cerr << "\n\n Actual Root nodes : "); - for (unsigned i = 0, N = graphRoot->outEdges.size(); i < N; i++) - DEBUG_PRINT(std::cerr << graphRoot->outEdges[i]->getSink()->getNodeId() - << ((i == N - 1) ? "" : ", ")); - - DEBUG_PRINT(std::cerr << "\n Graph Nodes:\n"); +void ModuloSchedGraph::ComputeHeight() { - unsigned numNodes = bb->size(); - for (unsigned i = 2; i < numNodes + 2; i++) { - ModuloSchedGraphNode *node = getNode(i); - DEBUG_PRINT(std::cerr << "\n" << *node); - } - - DEBUG_PRINT(std::cerr << "\n"); } - -/* - dump all node property -*/ - -void ModuloSchedGraph::dumpNodeProperty() const -{ - - unsigned numNodes = bb->size(); - for (unsigned i = 2; i < numNodes + 2; i++) { - ModuloSchedGraphNode *node = getNode(i); - DEBUG_PRINT(std::cerr << "NodeId " << node->getNodeId() << "\t"); - DEBUG_PRINT(std::cerr << "ASAP " << node->getASAP() << "\t"); - DEBUG_PRINT(std::cerr << "ALAP " << node->getALAP() << "\t"); - DEBUG_PRINT(std::cerr << "mov " << node->getMov() << "\t"); - DEBUG_PRINT(std::cerr << "depth " << node->getDepth() << "\t"); - DEBUG_PRINT(std::cerr << "height " << node->getHeight() << "\t\n"); - } +void ModuloSchedGraphSet::addGraph(ModuloSchedGraph *graph) { + assert(graph!=NULL && "Graph for BasicBlock is null"); + Graphs.push_back(graph); } +ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *F, + const TargetMachine &targ) + : function(F) { - -/************member functions for ModuloSchedGraphSet**************/ - -/* - constructor -*/ - -ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *function, - const TargetMachine &target) -: method(function){ - - buildGraphsForMethod(method, target); - + //Create graph for each BB in this function + for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI) + addGraph(new ModuloSchedGraph(BI, targ)); } -/* - destructor -*/ - - ModuloSchedGraphSet::~ModuloSchedGraphSet(){ //delete all the graphs - for (iterator I = begin(), E = end(); I != E; ++I) - delete *I; } - - -/* - build graph for each basicblock in this method -*/ - -void -ModuloSchedGraphSet::buildGraphsForMethod(const Function *F, - const TargetMachine &target){ - - for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI){ - const BasicBlock* local_bb; - - local_bb=BI; - addGraph(new ModuloSchedGraph((BasicBlock*)local_bb, target)); - } - -} - -/* - dump the graph set -*/ - -void -ModuloSchedGraphSet::dump() const{ - - DEBUG_PRINT(std::cerr << " ====== ModuloSched graphs for function `" << - method->getName() << "' =========\n\n"); - for (const_iterator I = begin(); I != end(); ++I) - (*I)->dump(); - - DEBUG_PRINT(std::cerr << "\n=========End graphs for function `" << method->getName() - << "' ==========\n\n"); -} - - - - -/********************misc functions***************************/ - - -/* - dump the input basic block -*/ - -static void -dumpBasicBlock(const BasicBlock * bb){ - - DEBUG_PRINT(std::cerr << "dumping basic block:"); - DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block") - << " (" << bb << ")" << "\n"); -} - -/* - dump the input node -*/ - -std::ostream& operator<<(std::ostream &os, - const ModuloSchedGraphNode &node) -{ - os << std::string(8, ' ') - << "Node " << node.nodeId << " : " - << "latency = " << node.latency << "\n" << std::string(12, ' '); - - if (node.getInst() == NULL) - os << "(Dummy node)\n"; - else { - os << *node.getInst() << "\n" << std::string(12, ' '); - os << node.inEdges.size() << " Incoming Edges:\n"; - for (unsigned i = 0, N = node.inEdges.size(); i < N; i++) - os << std::string(16, ' ') << *node.inEdges[i]; - - os << std::string(12, ' ') << node.outEdges.size() - << " Outgoing Edges:\n"; - for (unsigned i = 0, N = node.outEdges.size(); i < N; i++) - os << std::string(16, ' ') << *node.outEdges[i]; - } - - return os; -} diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.h b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.h index 2abd448fcd..3404a747ee 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.h +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedGraph.h @@ -1,367 +1,101 @@ //===- ModuloSchedGraph.h - Modulo Scheduling Graph and Set -*- C++ -*-----===// -// -// This header defines the primative classes that make up a data structure -// graph. +// // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_MODULO_SCHED_GRAPH_H -#define LLVM_CODEGEN_MODULO_SCHED_GRAPH_H +#ifndef LLVM_MODULO_SCHED_GRAPH_H +#define LLVM_MODULO_SCHED_GRAPH_H #include "llvm/Instruction.h" +#include "llvm/CodeGen/SchedGraphCommon.h" #include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "Support/GraphTraits.h" +#include "llvm/BasicBlock.h" +#include "llvm/Function.h" #include "Support/hash_map" -#include "../InstrSched/SchedGraphCommon.h" -#include +#include -//===----------------------------------------------------------------------===// -// ModuloSchedGraphNode - Implement a data structure based on the -// SchedGraphNodeCommon this class stores informtion needed later to order the -// nodes in modulo scheduling -// -class ModuloSchedGraphNode:public SchedGraphNodeCommon { -private: - // the corresponding instruction - const Instruction *inst; - // whether this node's property(ASAP,ALAP, ...) has been computed - bool propertyComputed; +class ModuloSchedGraphNode : public SchedGraphNodeCommon { - // ASAP: the earliest time the node could be scheduled - // ALAP: the latest time the node couldbe scheduled - // depth: the depth of the node - // height: the height of the node - // mov: the mobility function, computed as ALAP - ASAP - // scheTime: the scheduled time if this node has been scheduled - // earlyStart: the earliest time to be tried to schedule the node - // lateStart: the latest time to be tried to schedule the node - int ASAP, ALAP, depth, height, mov; - int schTime; - int earlyStart, lateStart; + const Instruction *Inst; //Node's Instruction + unsigned Earliest; //ASAP, or earliest time to be scheduled + unsigned Latest; //ALAP, or latested time to be scheduled + unsigned Depth; //Max Distance from node to the root + unsigned Height; //Max Distance from node to leaf + unsigned Mobility; //MOB, number of time slots it can be scheduled + const TargetMachine &Target; //Target information. public: - - //get the instruction - const Instruction *getInst() const { - return inst; - } - //get the instruction op-code name - const char *getInstOpcodeName() const { - return inst->getOpcodeName(); - } - //get the instruction op-code - const unsigned getInstOpcode() const { - return inst->getOpcode(); - } - - //return whether the node is NULL - bool isNullNode() const { - return (inst == NULL); - } - //return whether the property of the node has been computed - bool getPropertyComputed() { - return propertyComputed; - } - //set the propertyComputed - void setPropertyComputed(bool _propertyComputed) { - propertyComputed = _propertyComputed; - } + ModuloSchedGraphNode(unsigned ID, int index, const Instruction *inst, + const TargetMachine &target); - //get the corresponding property - int getASAP() { - return ASAP; - } - int getALAP() { - return ALAP; - } - int getMov() { - return mov; - } - int getDepth() { - return depth; - } - int getHeight() { - return height; - } - int getSchTime() { - return schTime; - } - int getEarlyStart() { - return earlyStart; - } - int getLateStart() { - return lateStart; - } - void setEarlyStart(int _earlyStart) { - earlyStart = _earlyStart; - } - void setLateStart(int _lateStart) { - lateStart = _lateStart; - } - void setSchTime(int _time) { - schTime = _time; - } - -private: - friend class ModuloSchedGraph; - friend class SchedGraphNode; - - //constructor: - //nodeId: the node id, unique within the each BasicBlock - //_bb: which BasicBlock the corresponding instruction belongs to - //_inst: the corresponding instruction - //indexInBB: the corresponding instruction's index in the BasicBlock - //target: the targetMachine - ModuloSchedGraphNode(unsigned int _nodeId, - const BasicBlock * _bb, - const Instruction * _inst, - int indexInBB, const TargetMachine &target); - + void print(std::ostream &os) const; + const Instruction* getInst() { return Inst; } + unsigned getEarliest() { return Earliest; } + unsigned getLatest() { return Latest; } + unsigned getDepth() { return Depth; } + unsigned getHeight() { return Height; } + unsigned getMobility() { return Mobility; } - friend std::ostream & operator<<(std::ostream & os, - const ModuloSchedGraphNode & edge); - -}; - -//FIXME: these two value should not be used -#define MAXNODE 100 -#define MAXCC 100 - -//===----------------------------------------------------------------------===// -/// ModuloSchedGraph- the data structure to store dependence between nodes -/// it catches data dependence and constrol dependence -/// -class ModuloSchedGraph : - public SchedGraphCommon, - protected hash_map { - -private: - - BasicBlock* bb; - - //iteration Interval - int MII; - - //target machine - const TargetMachine & target; + void setEarliest(unsigned early) { Earliest = early; } + void setLatest(unsigned late) { Latest = late; } + void setDepth(unsigned depth) { Depth = depth; } + void setHeight(unsigned height) { Height = height; } + void setMobility(unsigned mob) { Mobility = mob; } - //the circuits in the dependence graph - unsigned circuits[MAXCC][MAXNODE]; - //the order nodes - std::vector oNodes; - - typedef std::vector NodeVec; - - //the function to compute properties - void computeNodeASAP(const BasicBlock * in_bb); - void computeNodeALAP(const BasicBlock * in_bb); - void computeNodeMov(const BasicBlock * in_bb); - void computeNodeDepth(const BasicBlock * in_bb); - void computeNodeHeight(const BasicBlock * in_bb); - - //the function to compute node property - void computeNodeProperty(const BasicBlock * in_bb); - - //the function to sort nodes - void orderNodes(); - - //add the resource usage -void addResourceUsage(std::vector > &, int); - - //debug functions: - //dump circuits - void dumpCircuits(); - //dump the input set of nodes - void dumpSet(std::vector set); - //dump the input resource usage table - void dumpResourceUsage(std::vector > &); - -public: - //help functions - - //get the maxium the delay between two nodes - SchedGraphEdge *getMaxDelayEdge(unsigned srcId, unsigned sinkId); - - //FIXME: - //get the predessor Set of the set - NodeVec predSet(NodeVec set, unsigned, unsigned); - NodeVec predSet(NodeVec set); - - //get the predessor set of the node - NodeVec predSet(ModuloSchedGraphNode *node, unsigned, unsigned); - NodeVec predSet(ModuloSchedGraphNode *node); - - //get the successor set of the set - NodeVec succSet(NodeVec set, unsigned, unsigned); - NodeVec succSet(NodeVec set); - - //get the succssor set of the node - NodeVec succSet(ModuloSchedGraphNode *node, unsigned, unsigned); - NodeVec succSet(ModuloSchedGraphNode *node); +}; - //return the uniton of the two vectors - NodeVec vectorUnion(NodeVec set1, NodeVec set2); +class ModuloSchedGraph : public SchedGraphCommon { - //return the consjuction of the two vectors - NodeVec vectorConj(NodeVec set1, NodeVec set2); - - //return all nodes in set1 but not set2 - NodeVec vectorSub(NodeVec set1, NodeVec set2); - - typedef hash_map map_base; + const BasicBlock *BB; //The Basic block this graph represents + const TargetMachine &Target; + hash_map GraphMap; -public: - using map_base::iterator; - using map_base::const_iterator; - -public: - - //get target machine - const TargetMachine & getTarget() { - return target; - } - - //get the basic block - BasicBlock* getBasicBlock() const { - return bb; - } - - - //get the iteration interval - const int getMII() { - return MII; - } - - //get the ordered nodes - const NodeVec & getONodes() { - return oNodes; - } - - //get the number of nodes (including the root and leaf) - //note: actually root and leaf is not used - const unsigned int getNumNodes() const { - return size() + 2; - } - - //return wether the BasicBlock 'bb' contains a loop - bool isLoop(const BasicBlock *bb); - - //return the node for the input instruction - ModuloSchedGraphNode *getGraphNodeForInst(const Instruction *inst) const { - const_iterator onePair = this->find(inst); - return (onePair != this->end()) ? (*onePair).second : NULL; - } - - // Debugging support - //dump the graph - void dump() const; - - // dump the basicBlock - void dump(const BasicBlock *bb); - - //dump the basicBlock into 'os' stream - void dump(const BasicBlock *bb, std::ostream &os); - - //dump the node property - void dumpNodeProperty() const; - -private: - friend class ModuloSchedGraphSet; //give access to ctor + void buildNodesForBB(); public: - ModuloSchedGraph(BasicBlock * in_bb, - const TargetMachine & in_target) - :SchedGraphCommon(), bb(in_bb),target(in_target) - { - buildGraph(target); - } - - ~ModuloSchedGraph() { - for (const_iterator I = begin(); I != end(); ++I) - delete I->second; - } - - // Unorder iterators - // return values are pair - using map_base::begin; - using map_base::end; - - void addHash(const Instruction *inst, - ModuloSchedGraphNode *node){ - - assert((*this)[inst] == NULL); - (*this)[inst] = node; - - } - - // Graph builder - ModuloSchedGraphNode *getNode(const unsigned nodeId) const; - - // Build the graph from the basicBlock - void buildGraph(const TargetMachine &target); - - // Build nodes for BasicBlock - void buildNodesforBB(const TargetMachine &target, - const BasicBlock *bb); - - //find definitiona and use information for all nodes - void findDefUseInfoAtInstr(const TargetMachine &target, - ModuloSchedGraphNode *node, - NodeVec &memNode, - RegToRefVecMap ®ToRefVecMap, - ValueToDefVecMap &valueToDefVecMap); - - //add def-use edge - void addDefUseEdges(const BasicBlock *bb); - - //add control dependence edges - void addCDEdges(const BasicBlock *bb); - - //add memory dependence dges - void addMemEdges(const BasicBlock *bb); - - //computer source restrictoin II - int computeResII(const BasicBlock *bb); - - //computer recurrence II - int computeRecII(const BasicBlock *bb); + typedef hash_map::iterator iterator; + typedef hash_map::const_iterator const_iterator; + + + ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &targ); + + const BasicBlock* getBB() { return BB; } + void setBB(BasicBlock *bb) { BB = bb; } + unsigned size() { return GraphMap.size(); } + void addNode(const Instruction *I, ModuloSchedGraphNode *node); + void ASAP(); //Calculate earliest schedule time for all nodes in graph. + void ALAP(); //Calculate latest schedule time for all nodes in graph. + void MOB(); //Calculate mobility for all nodes in the graph. + void ComputeDepth(); //Compute depth of each node in graph + void ComputeHeight(); //Computer height of each node in graph + void addDepEdges(); //Add Dependencies + iterator find(const Instruction *I) { return GraphMap.find(I); } }; -//==================================- -// Graph set -class ModuloSchedGraphSet : public std::vector { -private: - const Function *method; - -public: - typedef std::vector baseVector; - using baseVector::iterator; - using baseVector::const_iterator; +class ModuloSchedGraphSet { + + const Function *function; //Function this set of graphs represent. + std::vector Graphs; public: - ModuloSchedGraphSet(const Function *function, const TargetMachine &target); + typedef std::vector::iterator iterator; + typedef std::vector::const_iterator const_iterator; + + iterator begin() { return Graphs.begin(); } + iterator end() { return Graphs.end(); } + + ModuloSchedGraphSet(const Function *func, const TargetMachine &target); ~ModuloSchedGraphSet(); - // Iterators - using baseVector::begin; - using baseVector::end; - - // Debugging support + void addGraph(ModuloSchedGraph *graph); void dump() const; -private: - void addGraph(ModuloSchedGraph *graph) { - assert(graph != NULL); - this->push_back(graph); - } - // Graph builder - void buildGraphsForMethod(const Function *F, - const TargetMachine &target); }; #endif diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp index 49f4246c02..bad3e97e48 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp @@ -1,983 +1,35 @@ -//===- ModuloScheduling.cpp - Modulo Software Pipelining ------------------===// +//===-- ModuloScheduling.cpp - Software Pipeling Approach - SMS --*- C++ -*--=// // -// Implements the llvm/CodeGen/ModuloScheduling.h interface +// The is a software pipelining pass based on the Swing Modulo Scheduling +// alogrithm (SMS). // //===----------------------------------------------------------------------===// -#include "llvm/BasicBlock.h" -#include "llvm/Constants.h" -#include "llvm/iTerminators.h" -#include "llvm/iPHINode.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineCodeForInstruction.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/InstrSelection.h" -#include "llvm/Target/TargetSchedInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "Support/CommandLine.h" -#include "Support/Statistic.h" #include "ModuloSchedGraph.h" -#include "ModuloScheduling.h" -#include -#include -//************************************************************ -// printing Debug information -// ModuloSchedDebugLevel stores the value of debug level -// modsched_os is the ostream to dump debug information, which is written into -// the file 'moduloSchedDebugInfo.output' -// see ModuloSchedulingPass::runOnFunction() -//************************************************************ +#include "llvm/Pass.h" +#include "llvm/Function.h" -ModuloSchedDebugLevel_t ModuloSchedDebugLevel; - -cl::opt -SDL_opt("modsched", cl::Hidden, cl::location(ModuloSchedDebugLevel), - cl::desc("enable modulo scheduling debugging information"), - cl::values(clEnumValN(ModuloSchedDebugLevel_NoDebugInfo, - "none", "disable debug output"), - clEnumValN(ModuloSchedDebugLevel_PrintSchedule, - "psched", "print original and new schedule"), - clEnumValN(ModuloSchedDebugLevel_PrintScheduleProcess, - "pschedproc", - "print how the new schdule is produced"), - 0)); - -// Computes the schedule and inserts epilogue and prologue -// -void -ModuloScheduling::instrScheduling(){ - - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "************ computing modulo schedule ***********\n"); - - const TargetSchedInfo & msi = target.getSchedInfo(); - - //number of issue slots in the in each cycle - int numIssueSlots = msi.maxNumIssueTotal; - - //compute the schedule - bool success = false; - while (!success) { - //clear memory from the last round and initialize if necessary - clearInitMem(msi); - - //compute schedule and coreSchedule with the current II - success = computeSchedule(); - - if (!success) { - II++; - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "increase II to " << II << "\n"); - } - } - - //print the final schedule - dumpFinalSchedule(); - - //the schedule has been computed - //create epilogue, prologue and kernel BasicBlock - - //find the successor for this BasicBlock - BasicBlock *succ_bb = getSuccBB(bb); - - //print the original BasicBlock if necessary - if (ModuloScheduling::printSchedule()) { - DEBUG_PRINT(std::cerr << "dumping the orginal block\n"); - graph.dump(bb); - } - //construction of prologue, kernel and epilogue - - /* - BasicBlock *kernel = bb->splitBasicBlock(bb->begin()); - BasicBlock *prologue = bb; - BasicBlock *epilogue = kernel->splitBasicBlock(kernel->begin()); - */ - - // Construct prologue - /*constructPrologue(prologue);*/ - - // Construct kernel - - /*constructKernel(prologue, kernel, epilogue);*/ - - // Construct epilogue - - /*constructEpilogue(epilogue, succ_bb);*/ +namespace { - //print the BasicBlocks if necessary -// if (0){ -// DEBUG_PRINT(std::cerr << "dumping the prologue block:\n"); -// graph.dump(prologue); -// DEBUG_PRINT(std::cerr << "dumping the kernel block\n"); -// graph.dump(kernel); -// DEBUG_PRINT(std::cerr << "dumping the epilogue block\n"); -// graph.dump(epilogue); -// } - -} - - -// Clear memory from the last round and initialize if necessary -// - -void -ModuloScheduling::clearInitMem(const TargetSchedInfo & msi){ - - unsigned numIssueSlots = msi.maxNumIssueTotal; - // clear nodeScheduled from the last round - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << "***** new round with II= " << II << " ***********\n"); - DEBUG_PRINT(std::cerr << - " ************clear the vector nodeScheduled*************\n"); - } - nodeScheduled.clear(); - - // clear resourceTable from the last round and reset it - resourceTable.clear(); - for (unsigned i = 0; i < II; ++i) - resourceTable.push_back(msi.resourceNumVector); - - // clear the schdule and coreSchedule from the last round - schedule.clear(); - coreSchedule.clear(); - - // create a coreSchedule of size II*numIssueSlots - // each entry is NULL - while (coreSchedule.size() < II) { - std::vector < ModuloSchedGraphNode * >*newCycle = - new std::vector < ModuloSchedGraphNode * >(); - for (unsigned k = 0; k < numIssueSlots; ++k) - newCycle->push_back(NULL); - coreSchedule.push_back(*newCycle); - } -} - -// Compute schedule and coreSchedule with the current II -// -bool -ModuloScheduling::computeSchedule(){ - - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "start to compute schedule\n"); - - // Loop over the ordered nodes - for (NodeVec::const_iterator I = oNodes.begin(); I != oNodes.end(); ++I) { - // Try to schedule for node I - if (ModuloScheduling::printScheduleProcess()) - dumpScheduling(); - ModuloSchedGraphNode *node = *I; - - // Compute whether this node has successor(s) - bool succ = true; - - // Compute whether this node has predessor(s) - bool pred = true; - - NodeVec schSucc = graph.vectorConj(nodeScheduled, graph.succSet(node)); - if (schSucc.empty()) - succ = false; - NodeVec schPred = graph.vectorConj(nodeScheduled, graph.predSet(node)); - if (schPred.empty()) - pred = false; - - //startTime: the earliest time we will try to schedule this node - //endTime: the latest time we will try to schedule this node - int startTime, endTime; - - //node's earlyStart: possible earliest time to schedule this node - //node's lateStart: possible latest time to schedule this node - node->setEarlyStart(-1); - node->setLateStart(9999); - - //this node has predessor but no successor - if (!succ && pred) { - // This node's earlyStart is it's predessor's schedule time + the edge - // delay - the iteration difference* II - for (unsigned i = 0; i < schPred.size(); i++) { - ModuloSchedGraphNode *predNode = schPred[i]; - SchedGraphEdge *edge = - graph.getMaxDelayEdge(predNode->getNodeId(), - node->getNodeId()); - int temp = - predNode->getSchTime() + edge->getMinDelay() - - edge->getIteDiff() * II; - node->setEarlyStart(std::max(node->getEarlyStart(), temp)); - } - startTime = node->getEarlyStart(); - endTime = node->getEarlyStart() + II - 1; - } - // This node has a successor but no predecessor - if (succ && !pred) { - for (unsigned i = 0; i < schSucc.size(); ++i) { - ModuloSchedGraphNode *succNode = schSucc[i]; - SchedGraphEdge *edge = - graph.getMaxDelayEdge(succNode->getNodeId(), - node->getNodeId()); - int temp = - succNode->getSchTime() - edge->getMinDelay() + - edge->getIteDiff() * II; - node->setLateStart(std::min(node->getEarlyStart(), temp)); - } - startTime = node->getLateStart() - II + 1; - endTime = node->getLateStart(); - } - // This node has both successors and predecessors - if (succ && pred) { - for (unsigned i = 0; i < schPred.size(); ++i) { - ModuloSchedGraphNode *predNode = schPred[i]; - SchedGraphEdge *edge = - graph.getMaxDelayEdge(predNode->getNodeId(), - node->getNodeId()); - int temp = - predNode->getSchTime() + edge->getMinDelay() - - edge->getIteDiff() * II; - node->setEarlyStart(std::max(node->getEarlyStart(), temp)); - } - for (unsigned i = 0; i < schSucc.size(); ++i) { - ModuloSchedGraphNode *succNode = schSucc[i]; - SchedGraphEdge *edge = - graph.getMaxDelayEdge(succNode->getNodeId(), - node->getNodeId()); - int temp = - succNode->getSchTime() - edge->getMinDelay() + - edge->getIteDiff() * II; - node->setLateStart(std::min(node->getEarlyStart(), temp)); - } - startTime = node->getEarlyStart(); - endTime = std::min(node->getLateStart(), - node->getEarlyStart() + ((int) II) - 1); - } - //this node has no successor or predessor - if (!succ && !pred) { - node->setEarlyStart(node->getASAP()); - startTime = node->getEarlyStart(); - endTime = node->getEarlyStart() + II - 1; - } - //try to schedule this node based on the startTime and endTime - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "scheduling the node " << (*I)->getNodeId() << "\n"); - - bool success = - this->ScheduleNode(node, startTime, endTime, nodeScheduled); - if (!success) - return false; - } - return true; -} - - -// Get the successor of the BasicBlock -// -BasicBlock * -ModuloScheduling::getSuccBB(BasicBlock *bb){ - - BasicBlock *succ_bb; - for (unsigned i = 0; i < II; ++i) - for (unsigned j = 0; j < coreSchedule[i].size(); ++j) - if (coreSchedule[i][j]) { - const Instruction *ist = coreSchedule[i][j]->getInst(); - - //we can get successor from the BranchInst instruction - //assume we only have one successor (besides itself) here - if (BranchInst::classof(ist)) { - BranchInst *bi = (BranchInst *) ist; - assert(bi->isConditional() && - "the branchInst is not a conditional one"); - assert(bi->getNumSuccessors() == 2 - && " more than two successors?"); - BasicBlock *bb1 = bi->getSuccessor(0); - BasicBlock *bb2 = bi->getSuccessor(1); - assert((bb1 == bb || bb2 == bb) && - " None of its successors is itself?"); - if (bb1 == bb) - succ_bb = bb2; - else - succ_bb = bb1; - return succ_bb; - } - } - assert(0 && "NO Successor?"); - return NULL; -} - - -// Get the predecessor of the BasicBlock -// -BasicBlock * -ModuloScheduling::getPredBB(BasicBlock *bb){ - - BasicBlock *pred_bb; - for (unsigned i = 0; i < II; ++i) - for (unsigned j = 0; j < coreSchedule[i].size(); ++j) - if (coreSchedule[i][j]) { - const Instruction *ist = coreSchedule[i][j]->getInst(); - - //we can get predecessor from the PHINode instruction - //assume we only have one predecessor (besides itself) here - if (PHINode::classof(ist)) { - PHINode *phi = (PHINode *) ist; - assert(phi->getNumIncomingValues() == 2 && - " the number of incoming value is not equal to two? "); - BasicBlock *bb1 = phi->getIncomingBlock(0); - BasicBlock *bb2 = phi->getIncomingBlock(1); - assert((bb1 == bb || bb2 == bb) && - " None of its predecessor is itself?"); - if (bb1 == bb) - pred_bb = bb2; - else - pred_bb = bb1; - return pred_bb; - } - } - assert(0 && " no predecessor?"); - return NULL; -} - - -// Construct the prologue -// -void -ModuloScheduling::constructPrologue(BasicBlock *prologue){ - - InstListType & prologue_ist = prologue->getInstList(); - vvNodeType & tempSchedule_prologue = - *(new std::vector >(schedule)); - - //compute the schedule for prologue - unsigned round = 0; - unsigned scheduleSize = schedule.size(); - while (round < scheduleSize / II) { - round++; - for (unsigned i = 0; i < scheduleSize; ++i) { - if (round * II + i >= scheduleSize) - break; - for (unsigned j = 0; j < schedule[i].size(); ++j) { - if (schedule[i][j]) { - assert(tempSchedule_prologue[round * II + i][j] == NULL && - "table not consitent with core table"); - // move the schedule one iteration ahead and overlap with the original - tempSchedule_prologue[round * II + i][j] = schedule[i][j]; - } - } - } - } - - // Clear the clone memory in the core schedule instructions - clearCloneMemory(); - - // Fill in the prologue - for (unsigned i = 0; i < ceil(1.0 * scheduleSize / II - 1) * II; ++i) - for (unsigned j = 0; j < tempSchedule_prologue[i].size(); ++j) - if (tempSchedule_prologue[i][j]) { - - //get the instruction - Instruction *orn = - (Instruction *) tempSchedule_prologue[i][j]->getInst(); - - //made a clone of it - Instruction *cln = cloneInstSetMemory(orn); - - //insert the instruction - prologue_ist.insert(prologue_ist.back(), cln); - - //if there is PHINode in the prologue, the incoming value from itself - //should be removed because it is not a loop any longer - if (PHINode::classof(cln)) { - PHINode *phi = (PHINode *) cln; - phi->removeIncomingValue(phi->getParent()); - } - } -} - - -// Construct the kernel BasicBlock -// -void -ModuloScheduling::constructKernel(BasicBlock *prologue, - BasicBlock *kernel, - BasicBlock *epilogue){ - - //*************fill instructions in the kernel**************** - InstListType & kernel_ist = kernel->getInstList(); - BranchInst *brchInst; - PHINode *phiInst, *phiCln; - - for (unsigned i = 0; i < coreSchedule.size(); ++i) - for (unsigned j = 0; j < coreSchedule[i].size(); ++j) - if (coreSchedule[i][j]) { - - // Take care of branch instruction differently with normal instructions - if (BranchInst::classof(coreSchedule[i][j]->getInst())) { - brchInst = (BranchInst *) coreSchedule[i][j]->getInst(); - continue; - } - // Take care of PHINode instruction differently with normal instructions - if (PHINode::classof(coreSchedule[i][j]->getInst())) { - phiInst = (PHINode *) coreSchedule[i][j]->getInst(); - Instruction *cln = cloneInstSetMemory(phiInst); - kernel_ist.insert(kernel_ist.back(), cln); - phiCln = (PHINode *) cln; - continue; - } - //for normal instructions: made a clone and insert it in the kernel_ist - Instruction *cln = - cloneInstSetMemory((Instruction *) coreSchedule[i][j]-> - getInst()); - kernel_ist.insert(kernel_ist.back(), cln); - } - // The two incoming BasicBlock for PHINode is the prologue and the kernel - // (itself) - phiCln->setIncomingBlock(0, prologue); - phiCln->setIncomingBlock(1, kernel); - - // The incoming value for the kernel (itself) is the new value which is - // computed in the kernel - Instruction *originalVal = (Instruction *) phiInst->getIncomingValue(1); - phiCln->setIncomingValue(1, originalVal->getClone()); - - // Make a clone of the branch instruction and insert it in the end - BranchInst *cln = (BranchInst *) cloneInstSetMemory(brchInst); - kernel_ist.insert(kernel_ist.back(), cln); - - // delete the unconditional branch instruction, which is generated when - // splitting the basicBlock - kernel_ist.erase(--kernel_ist.end()); - - // set the first successor to itself - cln->setSuccessor(0, kernel); - // set the second successor to eiplogue - cln->setSuccessor(1, epilogue); - - //*****change the condition******* - - //get the condition instruction - Instruction *cond = (Instruction *) cln->getCondition(); - - //get the condition's second operand, it should be a constant - Value *operand = cond->getOperand(1); - assert(ConstantSInt::classof(operand)); - - //change the constant in the condtion instruction - ConstantSInt *iteTimes = - ConstantSInt::get(operand->getType(), - ((ConstantSInt *) operand)->getValue() - II + 1); - cond->setOperand(1, iteTimes); - -} - - -// Construct the epilogue -// -void -ModuloScheduling::constructEpilogue(BasicBlock *epilogue, - BasicBlock *succ_bb){ - - //compute the schedule for epilogue - vvNodeType &tempSchedule_epilogue = - *(new std::vector >(schedule)); - unsigned scheduleSize = schedule.size(); - int round = 0; - while (round < ceil(1.0 * scheduleSize / II) - 1) { - round++; - for (unsigned i = 0; i < scheduleSize; i++) { - if (i + round * II >= scheduleSize) - break; - for (unsigned j = 0; j < schedule[i].size(); j++) - if (schedule[i + round * II][j]) { - assert(tempSchedule_epilogue[i][j] == NULL - && "table not consitant with core table"); - - //move the schdule one iteration behind and overlap - tempSchedule_epilogue[i][j] = schedule[i + round * II][j]; - } - } - } - - //fill in the epilogue - InstListType & epilogue_ist = epilogue->getInstList(); - for (unsigned i = II; i < scheduleSize; i++) - for (unsigned j = 0; j < tempSchedule_epilogue[i].size(); j++) - if (tempSchedule_epilogue[i][j]) { - Instruction *inst = - (Instruction *) tempSchedule_epilogue[i][j]->getInst(); - - //BranchInst and PHINode should be treated differently - //BranchInst:unecessary, simly omitted - //PHINode: omitted - if (!BranchInst::classof(inst) && !PHINode::classof(inst)) { - //make a clone instruction and insert it into the epilogue - Instruction *cln = cloneInstSetMemory(inst); - epilogue_ist.push_front(cln); - } - } - - //*************delete the original instructions****************// - //to delete the original instructions, we have to make sure their use is zero - - //update original core instruction's uses, using its clone instread - for (unsigned i = 0; i < II; i++) - for (unsigned j = 0; j < coreSchedule[i].size(); j++) { - if (coreSchedule[i][j]) - updateUseWithClone((Instruction *) coreSchedule[i][j]->getInst()); - } - - //erase these instructions - for (unsigned i = 0; i < II; i++) - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j]) { - Instruction *ist = (Instruction *) coreSchedule[i][j]->getInst(); - ist->getParent()->getInstList().erase(ist); - } - - - - //finally, insert an unconditional branch instruction at the end - epilogue_ist.push_back(new BranchInst(succ_bb)); - -} - - -//------------------------------------------------------------------------------ -//this function replace the value(instruction) ist in other instructions with -//its latest clone i.e. after this function is called, the ist is not used -//anywhere and it can be erased. -//------------------------------------------------------------------------------ -void -ModuloScheduling::updateUseWithClone(Instruction * ist){ - - - while (ist->use_size() > 0) { - bool destroyed = false; - - //other instruction is using this value ist - assert(Instruction::classof(*ist->use_begin())); - Instruction *inst = (Instruction *) (*ist->use_begin()); - - for (unsigned i = 0; i < inst->getNumOperands(); i++) - if (inst->getOperand(i) == ist && ist->getClone()) { - // if the instruction is TmpInstruction, simly delete it because it has - // no parent and it does not belongs to any BasicBlock - if (TmpInstruction::classof(inst)) { - delete inst; - destroyed = true; - break; - } - - //otherwise, set the instruction's operand to the value's clone - inst->setOperand(i, ist->getClone()); - - //the use from the original value ist is destroyed - destroyed = true; - break; - } - if (!destroyed) { - //if the use can not be destroyed , something is wrong - inst->dump(); - assert(0 && "this use can not be destroyed"); - } - } - -} - - -//******************************************************** -//this function clear all clone mememoy -//i.e. set all instruction's clone memory to NULL -//***************************************************** -void -ModuloScheduling::clearCloneMemory(){ - - for (unsigned i = 0; i < coreSchedule.size(); i++) - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j]) - ((Instruction *) coreSchedule[i][j]->getInst())->clearClone(); - -} - - -//****************************************************************************** -// this function make a clone of the instruction orn the cloned instruction will -// use the orn's operands' latest clone as its operands it is done this way -// because LLVM is in SSA form and we should use the correct value -//this fuction also update the instruction orn's latest clone memory -//****************************************************************************** -Instruction * -ModuloScheduling::cloneInstSetMemory(Instruction * orn){ - - // make a clone instruction - Instruction *cln = orn->clone(); - - // update the operands - for (unsigned k = 0; k < orn->getNumOperands(); k++) { - const Value *op = orn->getOperand(k); - if (Instruction::classof(op) && ((Instruction *) op)->getClone()) { - Instruction *op_inst = (Instruction *) op; - cln->setOperand(k, op_inst->getClone()); - } - } - - // update clone memory - orn->setClone(cln); - return cln; -} - - - -bool -ModuloScheduling::ScheduleNode(ModuloSchedGraphNode * node, - unsigned start, unsigned end, - NodeVec & nodeScheduled){ - - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned int numIssueSlots = msi.maxNumIssueTotal; - - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "startTime= " << start << " endTime= " << end << "\n"); - bool isScheduled = false; - for (unsigned i = start; i <= end; i++) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << " now try cycle " << i << ":" << "\n"); - for (unsigned j = 0; j < numIssueSlots; j++) { - unsigned int core_i = i % II; - unsigned int core_j = j; - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << "\t Trying slot " << j << "..........."); - //check the resouce table, make sure there is no resource conflicts - const Instruction *instr = node->getInst(); - MachineCodeForInstruction & tempMvec = - MachineCodeForInstruction::get(instr); - bool resourceConflict = false; - const TargetInstrInfo & mii = msi.getInstrInfo(); - - if (coreSchedule.size() < core_i + 1 - || !coreSchedule[core_i][core_j]) { - //this->dumpResourceUsageTable(); - int latency = 0; - for (unsigned k = 0; k < tempMvec.size(); k++) { - MachineInstr *minstr = tempMvec[k]; - InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode()); - std::vector < std::vector < resourceId_t > >resources - = rUsage.resourcesByCycle; - updateResourceTable(resources, i + latency); - latency += std::max(mii.minLatency(minstr->getOpCode()), 1); - } - - //this->dumpResourceUsageTable(); - - latency = 0; - if (resourceTableNegative()) { - - //undo-update the resource table - for (unsigned k = 0; k < tempMvec.size(); k++) { - MachineInstr *minstr = tempMvec[k]; - InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode()); - std::vector < std::vector < resourceId_t > >resources - = rUsage.resourcesByCycle; - undoUpdateResourceTable(resources, i + latency); - latency += std::max(mii.minLatency(minstr->getOpCode()), 1); - } - resourceConflict = true; - } - } - if (!resourceConflict && !coreSchedule[core_i][core_j]) { - if (ModuloScheduling::printScheduleProcess()) { - DEBUG_PRINT(std::cerr << " OK!" << "\n"); - DEBUG_PRINT(std::cerr << "Node " << node->getNodeId() << " scheduled.\n"); - } - //schedule[i][j]=node; - while (schedule.size() <= i) { - std::vector < ModuloSchedGraphNode * >*newCycle = - new std::vector < ModuloSchedGraphNode * >(); - for (unsigned k = 0; k < numIssueSlots; k++) - newCycle->push_back(NULL); - schedule.push_back(*newCycle); - } - std::vector::iterator startIterator; - startIterator = schedule[i].begin(); - schedule[i].insert(startIterator + j, node); - startIterator = schedule[i].begin(); - schedule[i].erase(startIterator + j + 1); - - //update coreSchedule - //coreSchedule[core_i][core_j]=node; - while (coreSchedule.size() <= core_i) { - std::vector *newCycle = - new std::vector(); - for (unsigned k = 0; k < numIssueSlots; k++) - newCycle->push_back(NULL); - coreSchedule.push_back(*newCycle); - } - - startIterator = coreSchedule[core_i].begin(); - coreSchedule[core_i].insert(startIterator + core_j, node); - startIterator = coreSchedule[core_i].begin(); - coreSchedule[core_i].erase(startIterator + core_j + 1); - - node->setSchTime(i); - isScheduled = true; - nodeScheduled.push_back(node); - - break; - } else if (coreSchedule[core_i][core_j]) { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << " Slot not available\n"); - } else { - if (ModuloScheduling::printScheduleProcess()) - DEBUG_PRINT(std::cerr << " Resource conflicts\n"); - } - } - if (isScheduled) - break; - } - //assert(nodeScheduled &&"this node can not be scheduled?"); - return isScheduled; -} - - -void -ModuloScheduling::updateResourceTable(Resources useResources, - int startCycle){ - - for (unsigned i = 0; i < useResources.size(); i++) { - int absCycle = startCycle + i; - int coreCycle = absCycle % II; - std::vector > &resourceRemained = - resourceTable[coreCycle]; - std::vector < unsigned int >&resourceUsed = useResources[i]; - for (unsigned j = 0; j < resourceUsed.size(); j++) { - for (unsigned k = 0; k < resourceRemained.size(); k++) - if ((int) resourceUsed[j] == resourceRemained[k].first) { - resourceRemained[k].second--; - } - } - } -} - -void -ModuloScheduling::undoUpdateResourceTable(Resources useResources, - int startCycle){ - - for (unsigned i = 0; i < useResources.size(); i++) { - int absCycle = startCycle + i; - int coreCycle = absCycle % II; - std::vector > &resourceRemained = - resourceTable[coreCycle]; - std::vector < unsigned int >&resourceUsed = useResources[i]; - for (unsigned j = 0; j < resourceUsed.size(); j++) { - for (unsigned k = 0; k < resourceRemained.size(); k++) - if ((int) resourceUsed[j] == resourceRemained[k].first) { - resourceRemained[k].second++; - } - } - } -} - - -//----------------------------------------------------------------------- -// Function: resourceTableNegative -// return value: -// return false if any element in the resouceTable is negative -// otherwise return true -// Purpose: - -// this function is used to determine if an instruction is eligible for -// schedule at certain cycle -//----------------------------------------------------------------------- - - -bool -ModuloScheduling::resourceTableNegative(){ - - assert(resourceTable.size() == (unsigned) II - && "resouceTable size must be equal to II"); - bool isNegative = false; - for (unsigned i = 0; i < resourceTable.size(); i++) - for (unsigned j = 0; j < resourceTable[i].size(); j++) { - if (resourceTable[i][j].second < 0) { - isNegative = true; - break; - } - } - return isNegative; -} - - -//---------------------------------------------------------------------- -// Function: dumpResouceUsageTable -// Purpose: -// print out ResouceTable for debug -// -//------------------------------------------------------------------------ - -void -ModuloScheduling::dumpResourceUsageTable(){ - - DEBUG_PRINT(std::cerr << "dumping resource usage table\n"); - for (unsigned i = 0; i < resourceTable.size(); i++) { - for (unsigned j = 0; j < resourceTable[i].size(); j++) - DEBUG_PRINT(std::cerr << resourceTable[i][j].first - << ":" << resourceTable[i][j].second << " "); - DEBUG_PRINT(std::cerr << "\n"); - } - -} - -//---------------------------------------------------------------------- -//Function: dumpSchedule -//Purpose: -// print out thisSchedule for debug -// -//----------------------------------------------------------------------- -void -ModuloScheduling::dumpSchedule(vvNodeType thisSchedule){ - - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned numIssueSlots = msi.maxNumIssueTotal; - for (unsigned i = 0; i < numIssueSlots; i++) - DEBUG_PRINT(std::cerr << "\t#"); - DEBUG_PRINT(std::cerr << "\n"); - for (unsigned i = 0; i < thisSchedule.size(); i++) { - DEBUG_PRINT(std::cerr << "cycle" << i << ": "); - for (unsigned j = 0; j < thisSchedule[i].size(); j++) - if (thisSchedule[i][j] != NULL) - DEBUG_PRINT(std::cerr << thisSchedule[i][j]->getNodeId() << "\t"); - else - DEBUG_PRINT(std::cerr << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } -} - - -//---------------------------------------------------- -//Function: dumpScheduling -//Purpose: -// print out the schedule and coreSchedule for debug -// -//------------------------------------------------------- - -void -ModuloScheduling::dumpScheduling(){ - - DEBUG_PRINT(std::cerr << "dump schedule:" << "\n"); - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned numIssueSlots = msi.maxNumIssueTotal; - for (unsigned i = 0; i < numIssueSlots; i++) - DEBUG_PRINT(std::cerr << "\t#"); - DEBUG_PRINT(std::cerr << "\n"); - for (unsigned i = 0; i < schedule.size(); i++) { - DEBUG_PRINT(std::cerr << "cycle" << i << ": "); - for (unsigned j = 0; j < schedule[i].size(); j++) - if (schedule[i][j] != NULL) - DEBUG_PRINT(std::cerr << schedule[i][j]->getNodeId() << "\t"); - else - DEBUG_PRINT(std::cerr << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } - - DEBUG_PRINT(std::cerr << "dump coreSchedule:" << "\n"); - for (unsigned i = 0; i < numIssueSlots; i++) - DEBUG_PRINT(std::cerr << "\t#"); - DEBUG_PRINT(std::cerr << "\n"); - for (unsigned i = 0; i < coreSchedule.size(); i++) { - DEBUG_PRINT(std::cerr << "cycle" << i << ": "); - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j] != NULL) - DEBUG_PRINT(std::cerr << coreSchedule[i][j]->getNodeId() << "\t"); - else - DEBUG_PRINT(std::cerr << "\t"); - DEBUG_PRINT(std::cerr << "\n"); - } -} - -/* - print out final schedule -*/ - -void -ModuloScheduling::dumpFinalSchedule(){ - - std::cerr << "dump schedule:" << "\n"; - const TargetSchedInfo & msi = target.getSchedInfo(); - unsigned numIssueSlots = msi.maxNumIssueTotal; - - for (unsigned i = 0; i < numIssueSlots; i++) - std::cerr << "\t#"; - std::cerr << "\n"; - - for (unsigned i = 0; i < schedule.size(); i++) { - std::cerr << "cycle" << i << ": "; + class ModuloScheduling : public FunctionPass { - for (unsigned j = 0; j < schedule[i].size(); j++) - if (schedule[i][j] != NULL) - std::cerr << schedule[i][j]->getNodeId() << "\t"; - else - std::cerr << "\t"; - std::cerr << "\n"; - } - - std::cerr << "dump coreSchedule:" << "\n"; - for (unsigned i = 0; i < numIssueSlots; i++) - std::cerr << "\t#"; - std::cerr << "\n"; - - for (unsigned i = 0; i < coreSchedule.size(); i++) { - std::cerr << "cycle" << i << ": "; - for (unsigned j = 0; j < coreSchedule[i].size(); j++) - if (coreSchedule[i][j] != NULL) - std::cerr << coreSchedule[i][j]->getNodeId() << "\t"; - else - std::cerr << "\t"; - std::cerr << "\n"; - } -} - -//--------------------------------------------------------------------------- -// Function: ModuloSchedulingPass -// -// Purpose: -// Entry point for Modulo Scheduling -// Schedules LLVM instruction -// -//--------------------------------------------------------------------------- - -namespace { - class ModuloSchedulingPass:public FunctionPass { - const TargetMachine ⌖ - public: - ModuloSchedulingPass(const TargetMachine &T):target(T) {} - - const char *getPassName() const { - return "Modulo Scheduling"; - } - - // getAnalysisUsage - We use LiveVarInfo... - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - //AU.addRequired(FunctionLiveVarInfo::ID); - } - - bool runOnFunction(Function & F); + virtual bool runOnFunction(Function &F); }; -} // end anonymous namespace + RegisterOpt X("modulo-sched", "Modulo Scheduling/Software Pipelining"); +} -bool -ModuloSchedulingPass::runOnFunction(Function &F){ - - ModuloSchedGraphSet *graphSet = new ModuloSchedGraphSet(&F, target); - - ModuloSchedulingSet ModuloSchedulingSet(*graphSet); - - DEBUG_PRINT(std::cerr<<"runOnFunction in ModuloSchedulingPass returns\n"<<"\n"); - return false; +//Create Modulo Scheduling Pass +Pass *createModuloSchedPass() { + return new ModuloScheduling(); } +//ModuloScheduling::runOnFunction - Main transformation entry point. +bool ModuloScheduling::runOnFunction(Function &F) { + bool Changed = false; -Pass * -createModuloSchedulingPass(const TargetMachine & tgt){ - DEBUG_PRINT(std::cerr<<"creating modulo scheduling\n"); - return new ModuloSchedulingPass(tgt); + return Changed; } + diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h deleted file mode 100644 index 00cca149da..0000000000 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h +++ /dev/null @@ -1,194 +0,0 @@ -// ModuloScheduling.h -------------------------------------------*- C++ -*-===// -// -// This header defines the the classes ModuloScheduling and -// ModuloSchedulingSet's structure -// -//===----------------------------------------------------------------------===// - - -#ifndef LLVM_CODEGEN_MODULOSCHEDULING_H -#define LLVM_CODEGEN_MODULOSCHEDULING_H - -#include "ModuloSchedGraph.h" -#include -#include - -//#define DEBUG_PRINT(x) x - -#define DEBUG_PRINT(x) - -// for debug information selecton -enum ModuloSchedDebugLevel_t { - ModuloSchedDebugLevel_NoDebugInfo, - ModuloSchedDebugLevel_PrintSchedule, - ModuloSchedDebugLevel_PrintScheduleProcess, -}; - -class ModuloScheduling: NonCopyable { -private: - - typedef std::vector NodeVec; - typedef std::vector > Resources; - - // The graph to feed in - ModuloSchedGraph &graph; - const TargetMachine ⌖ - - // The BasicBlock to be scheduled - BasicBlock *bb; - - // Iteration Interval - // FIXME: II may be a better name for its meaning - unsigned II; - - // The vector containing the nodes which have been scheduled - NodeVec nodeScheduled; - - // The remaining unscheduled nodes - const NodeVec &oNodes; - - // The machine resource table - std::vector > > resourceTable; - - ///the schedule( with many schedule stage) - std::vector > schedule; - - ///the kernel(core) schedule(length = II) - std::vector > coreSchedule; - - typedef BasicBlock::InstListType InstListType; - typedef std::vector > vvNodeType; - - - - - -public: - - ModuloScheduling(ModuloSchedGraph & _graph): - graph(_graph), target(graph.getTarget()), oNodes(graph.getONodes()) - { - II = graph.getMII(); - bb = graph.getBasicBlock(); - instrScheduling(); - }; - - ~ModuloScheduling() {}; - - - - static bool - printSchedule() { - - //return ModuloScheduling::DebugLevel >= DebugLevel_PrintSchedule; - return true; - - - } - static bool - printScheduleProcess() { - - //return DebugLevel >= DebugLevel_PrintScheduleProcess; - return true; - - - } - - // The method to compute schedule and instert epilogue and prologue - void instrScheduling(); - - // Debug functions: - // Dump the schedule and core schedule - void dumpScheduling(); - void dumpFinalSchedule(); - - // Dump the input vector of nodes - // sch: the input vector of nodes - void dumpSchedule(std::vector > sch); - - // Dump the resource usage table - void dumpResourceUsageTable(); - - //*******************internal functions******************************* -private: - //clear memory from the last round and initialize if necessary - void clearInitMem(const TargetSchedInfo&); - - //compute schedule and coreSchedule with the current II - bool computeSchedule(); - - BasicBlock *getSuccBB(BasicBlock *); - BasicBlock *getPredBB(BasicBlock *); - void constructPrologue(BasicBlock *prologue); - void constructKernel(BasicBlock *prologue, - BasicBlock *kernel, - BasicBlock *epilogue); - void constructEpilogue(BasicBlock *epilogue, BasicBlock *succ_bb); - - // update the resource table at the startCycle - // vec: the resouce usage - // startCycle: the start cycle the resouce usage is - void updateResourceTable(std::vector > vec, - int startCycle); - - // un-do the update in the resource table in the startCycle - // vec: the resouce usage - // startCycle: the start cycle the resouce usage is - void undoUpdateResourceTable(std::vector > vec, - int startCycle); - - // return whether the resourcetable has negative element - // this function is called after updateResouceTable() to determine whether a - // node can be scheduled at certain cycle - bool resourceTableNegative(); - - // try to Schedule the node starting from start to end cycle(inclusive) - // if it can be scheduled, put it in the schedule and update nodeScheduled - // node: the node to be scheduled - // start: start cycle - // end : end cycle - // nodeScheduled: a vector storing nodes which has been scheduled - bool ScheduleNode(ModuloSchedGraphNode * node, unsigned start, - unsigned end, NodeVec &nodeScheduled); - - //each instruction has a memory of the latest clone instruction - //the clone instruction can be get using getClone() - //this function clears the memory, i.e. getClone() after calling this function - //returns null - void clearCloneMemory(); - - //this fuction make a clone of this input Instruction and update the clone - //memory - //inst: the instrution to be cloned - Instruction *cloneInstSetMemory(Instruction *inst); - - //this function update each instrutions which uses ist as its operand - //after update, each instruction will use ist's clone as its operand - void updateUseWithClone(Instruction * ist); - -}; - - -class ModuloSchedulingSet: -NonCopyable { -private: - - //the graphSet to feed in - ModuloSchedGraphSet & graphSet; - -public: - - //constructor - //Scheduling graph one by one - ModuloSchedulingSet(ModuloSchedGraphSet _graphSet): graphSet(_graphSet) { - for (unsigned i = 0; i < graphSet.size(); i++) { - ModuloSchedGraph & graph = *(graphSet[i]); - if (graph.isLoop(graph.getBasicBlock())) - ModuloScheduling ModuloScheduling(graph); - } - }; - - ~ModuloSchedulingSet() {}; -}; - -#endif -- cgit v1.2.3