diff options
author | Jeff Cohen <jeffc@jolt-lang.org> | 2005-07-27 05:53:44 +0000 |
---|---|---|
committer | Jeff Cohen <jeffc@jolt-lang.org> | 2005-07-27 05:53:44 +0000 |
commit | 9eb59ec548b861d6ede05b4e6dc22aabf645e665 (patch) | |
tree | 97ffa1993e23e29ccabac9646fc950717bd94dda /lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp | |
parent | 50e9ef8792c5c91b7ea6f24f878d1abbcb6024a4 (diff) |
Eliminate tabs and trailing spaces.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@22520 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp')
-rw-r--r-- | lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp | 1864 |
1 files changed, 932 insertions, 932 deletions
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp index 65008a67f8..efc203bcc6 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp @@ -100,34 +100,34 @@ namespace llvm { static std::string getNodeLabel(MSchedGraphNode *Node, MSchedGraph *Graph) { if (Node->getInst()) { - std::stringstream ss; - ss << *(Node->getInst()); - return ss.str(); //((MachineInstr*)Node->getInst()); + std::stringstream ss; + ss << *(Node->getInst()); + return ss.str(); //((MachineInstr*)Node->getInst()); } else - return "No Inst"; + return "No Inst"; } static std::string getEdgeSourceLabel(MSchedGraphNode *Node, - MSchedGraphNode::succ_iterator I) { + MSchedGraphNode::succ_iterator I) { //Label each edge with the type of dependence std::string edgelabel = ""; switch (I.getEdge().getDepOrderType()) { - + case MSchedGraphEdge::TrueDep: - edgelabel = "True"; - break; + edgelabel = "True"; + break; case MSchedGraphEdge::AntiDep: - edgelabel = "Anti"; - break; - + edgelabel = "Anti"; + break; + case MSchedGraphEdge::OutputDep: - edgelabel = "Output"; - break; - + edgelabel = "Output"; + break; + default: - edgelabel = "Unknown"; - break; + edgelabel = "Unknown"; + break; } //FIXME @@ -173,11 +173,11 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) { for (MachineFunction::iterator BI = MF.begin(); BI != MF.end(); ++BI) if(MachineBBisValid(BI)) { if(BI->size() < 100) { - Worklist.push_back(&*BI); - ++ValidLoops; + Worklist.push_back(&*BI); + ++ValidLoops; } else - ++JumboBB; + ++JumboBB; } @@ -187,7 +187,7 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) { //Iterate over the worklist and perform scheduling for(std::vector<MachineBasicBlock*>::iterator BI = Worklist.begin(), - BE = Worklist.end(); BI != BE; ++BI) { + BE = Worklist.end(); BI != BE; ++BI) { //Print out BB for debugging DEBUG(std::cerr << "BB Size: " << (*BI)->size() << "\n"); @@ -236,41 +236,41 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) { //Dump node properties if in debug mode DEBUG(for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), - E = nodeToAttributesMap.end(); I !=E; ++I) { - std::cerr << "Node: " << *(I->first) << " ASAP: " << I->second.ASAP << " ALAP: " - << I->second.ALAP << " MOB: " << I->second.MOB << " Depth: " << I->second.depth - << " Height: " << I->second.height << "\n"; - }); + E = nodeToAttributesMap.end(); I !=E; ++I) { + std::cerr << "Node: " << *(I->first) << " ASAP: " << I->second.ASAP << " ALAP: " + << I->second.ALAP << " MOB: " << I->second.MOB << " Depth: " << I->second.depth + << " Height: " << I->second.height << "\n"; + }); //Calculate Node Properties calculateNodeAttributes(MSG, ResMII); //Dump node properties if in debug mode DEBUG(for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), - E = nodeToAttributesMap.end(); I !=E; ++I) { - std::cerr << "Node: " << *(I->first) << " ASAP: " << I->second.ASAP << " ALAP: " - << I->second.ALAP << " MOB: " << I->second.MOB << " Depth: " << I->second.depth - << " Height: " << I->second.height << "\n"; - }); + E = nodeToAttributesMap.end(); I !=E; ++I) { + std::cerr << "Node: " << *(I->first) << " ASAP: " << I->second.ASAP << " ALAP: " + << I->second.ALAP << " MOB: " << I->second.MOB << " Depth: " << I->second.depth + << " Height: " << I->second.height << "\n"; + }); //Put nodes in order to schedule them computePartialOrder(); //Dump out partial order DEBUG(for(std::vector<std::set<MSchedGraphNode*> >::iterator I = partialOrder.begin(), - E = partialOrder.end(); I !=E; ++I) { - std::cerr << "Start set in PO\n"; - for(std::set<MSchedGraphNode*>::iterator J = I->begin(), JE = I->end(); J != JE; ++J) - std::cerr << "PO:" << **J << "\n"; - }); + E = partialOrder.end(); I !=E; ++I) { + std::cerr << "Start set in PO\n"; + for(std::set<MSchedGraphNode*>::iterator J = I->begin(), JE = I->end(); J != JE; ++J) + std::cerr << "PO:" << **J << "\n"; + }); //Place nodes in final order orderNodes(); //Dump out order of nodes DEBUG(for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(), E = FinalNodeOrder.end(); I != E; ++I) { - std::cerr << "FO:" << **I << "\n"; - }); + std::cerr << "FO:" << **I << "\n"; + }); //Finally schedule nodes bool haveSched = computeSchedule(*BI, MSG); @@ -288,7 +288,7 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) { IISum += mII; if(schedule.getMaxStage() == 0) - ++SameStage; + ++SameStage; } else { ++NoSched; @@ -323,20 +323,20 @@ bool ModuloSchedulingPass::CreateDefMap(MachineBasicBlock *BI) { for(unsigned opNum = 0; opNum < I->getNumOperands(); ++opNum) { const MachineOperand &mOp = I->getOperand(opNum); if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) { - //assert if this is the second def we have seen - //DEBUG(std::cerr << "Putting " << *(mOp.getVRegValue()) << " into map\n"); - //assert(!defMap.count(mOp.getVRegValue()) && "Def already in the map"); - if(defMap.count(mOp.getVRegValue())) - return false; + //assert if this is the second def we have seen + //DEBUG(std::cerr << "Putting " << *(mOp.getVRegValue()) << " into map\n"); + //assert(!defMap.count(mOp.getVRegValue()) && "Def already in the map"); + if(defMap.count(mOp.getVRegValue())) + return false; - defMap[mOp.getVRegValue()] = &*I; + defMap[mOp.getVRegValue()] = &*I; } //See if we can use this Value* as our defaultInst if(!defaultInst && mOp.getType() == MachineOperand::MO_VirtualRegister) { - Value *V = mOp.getVRegValue(); - if(!isa<TmpInstruction>(V) && !isa<Argument>(V) && !isa<Constant>(V) && !isa<PHINode>(V)) - defaultInst = (Instruction*) V; + Value *V = mOp.getVRegValue(); + if(!isa<TmpInstruction>(V) && !isa<Argument>(V) && !isa<Constant>(V) && !isa<PHINode>(V)) + defaultInst = (Instruction*) V; } } } @@ -357,7 +357,7 @@ bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) { //Check first if its a valid loop for(succ_const_iterator I = succ_begin(BI->getBasicBlock()), - E = succ_end(BI->getBasicBlock()); I != E; ++I) { + E = succ_end(BI->getBasicBlock()); I != E; ++I) { if (*I == BI->getBasicBlock()) // has single block loop isLoop = true; } @@ -437,8 +437,8 @@ bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) { if(Instruction *I = dyn_cast<Instruction>(cond)) if(I->getParent() == BB) { if (!assocIndVar(I, indVar, stack, BB)) { - ++InvalidLoops; - return false; + ++InvalidLoops; + return false; } } else { @@ -455,8 +455,8 @@ bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) { //Dump out instructions associate with indvar for debug reasons DEBUG(for(std::set<Instruction*>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) { - std::cerr << **N << "\n"; - }); + std::cerr << **N << "\n"; + }); //Create map of machine instr to llvm instr std::map<MachineInstr*, Instruction*> mllvm; @@ -480,9 +480,9 @@ bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) { for (unsigned j = 0; j < tempMvec.size(); j++) { MachineOpCode OC = (tempMvec[j])->getOpcode(); if(TMI->isNop(OC)) - continue; + continue; if(!indexMap.count(tempMvec[j])) - continue; + continue; mIndVar[(MachineInstr*) tempMvec[j]] = indexMap[(MachineInstr*) tempMvec[j]]; DEBUG(std::cerr << *(tempMvec[j]) << " at index " << indexMap[(MachineInstr*) tempMvec[j]] << "\n"); } @@ -499,7 +499,7 @@ bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) { } bool ModuloSchedulingPass::assocIndVar(Instruction *I, std::set<Instruction*> &indVar, - std::vector<Instruction*> &stack, BasicBlock *BB) { + std::vector<Instruction*> &stack, BasicBlock *BB) { stack.push_back(I); @@ -510,21 +510,21 @@ bool ModuloSchedulingPass::assocIndVar(Instruction *I, std::set<Instruction*> &i if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN) if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) if (CI->equalsInt(1)) { - //We have found the indvar, so add the stack, and inc instruction to the set - indVar.insert(stack.begin(), stack.end()); - indVar.insert(Inc); - stack.pop_back(); - return true; - } + //We have found the indvar, so add the stack, and inc instruction to the set + indVar.insert(stack.begin(), stack.end()); + indVar.insert(Inc); + stack.pop_back(); + return true; + } return false; } else { //Loop over each of the instructions operands, check if they are an instruction and in this BB for(unsigned i = 0; i < I->getNumOperands(); ++i) { if(Instruction *N = dyn_cast<Instruction>(I->getOperand(i))) { - if(N->getParent() == BB) - if(!assocIndVar(N, indVar, stack, BB)) - return false; + if(N->getParent() == BB) + if(!assocIndVar(N, indVar, stack, BB)) + return false; } } } @@ -558,12 +558,12 @@ int ModuloSchedulingPass::calculateResMII(const MachineBasicBlock *BI) { //Loop over resources in each cycle and increments their usage count for(unsigned i=0; i < resources.size(); ++i) for(unsigned j=0; j < resources[i].size(); ++j) { - if(!resourceUsageCount.count(resources[i][j])) { - resourceUsageCount[resources[i][j]] = 1; - } - else { - resourceUsageCount[resources[i][j]] = resourceUsageCount[resources[i][j]] + 1; - } + if(!resourceUsageCount.count(resources[i][j])) { + resourceUsageCount[resources[i][j]] = 1; + } + else { + resourceUsageCount[resources[i][j]] = resourceUsageCount[resources[i][j]] + 1; + } } } @@ -638,7 +638,7 @@ void ModuloSchedulingPass::calculateNodeAttributes(MSchedGraph *graph, int MII) //Assert if its already in the map assert(nodeToAttributesMap.count(I->second) == 0 && - "Node attributes are already in the map"); + "Node attributes are already in the map"); //Put into the map with default attribute values nodeToAttributesMap[I->second] = MSNodeAttributes(); @@ -724,7 +724,7 @@ int ModuloSchedulingPass::calculateASAP(MSchedGraphNode *node, int MII, MSchedG int ModuloSchedulingPass::calculateALAP(MSchedGraphNode *node, int MII, - int maxASAP, MSchedGraphNode *srcNode) { + int maxASAP, MSchedGraphNode *srcNode) { DEBUG(std::cerr << "Calculating ALAP for " << *node << "\n"); @@ -745,28 +745,28 @@ int ModuloSchedulingPass::calculateALAP(MSchedGraphNode *node, int MII, //Iterate over all of the predecessors and fine max for(MSchedGraphNode::succ_iterator P = node->succ_begin(), - E = node->succ_end(); P != E; ++P) { + E = node->succ_end(); P != E; ++P) { //Only process if we are not ignoring the edge if(!ignoreEdge(node, *P)) { - processedOneEdge = true; - int succALAP = -1; - succALAP = calculateALAP(*P, MII, maxASAP, node); - - assert(succALAP != -1 && "Successors ALAP should have been caclulated"); - - int iteDiff = P.getEdge().getIteDiff(); - - int currentSuccValue = succALAP - node->getLatency() + iteDiff * MII; - - DEBUG(std::cerr << "succ ALAP: " << succALAP << ", iteDiff: " << iteDiff << ", SuccLatency: " << (*P)->getLatency() << ", Current ALAP succ: " << currentSuccValue << "\n"); - - minSuccValue = std::min(minSuccValue, currentSuccValue); + processedOneEdge = true; + int succALAP = -1; + succALAP = calculateALAP(*P, MII, maxASAP, node); + + assert(succALAP != -1 && "Successors ALAP should have been caclulated"); + + int iteDiff = P.getEdge().getIteDiff(); + + int currentSuccValue = succALAP - node->getLatency() + iteDiff * MII; + + DEBUG(std::cerr << "succ ALAP: " << succALAP << ", iteDiff: " << iteDiff << ", SuccLatency: " << (*P)->getLatency() << ", Current ALAP succ: " << currentSuccValue << "\n"); + + minSuccValue = std::min(minSuccValue, currentSuccValue); } } if(processedOneEdge) - attributes.ALAP = minSuccValue; + attributes.ALAP = minSuccValue; else attributes.ALAP = maxASAP; @@ -786,7 +786,7 @@ int ModuloSchedulingPass::findMaxASAP() { int maxASAP = 0; for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), - E = nodeToAttributesMap.end(); I != E; ++I) + E = nodeToAttributesMap.end(); I != E; ++I) maxASAP = std::max(maxASAP, I->second.ASAP); return maxASAP; } @@ -803,7 +803,7 @@ int ModuloSchedulingPass::calculateHeight(MSchedGraphNode *node,MSchedGraphNode //Iterate over all of the predecessors and find max for(MSchedGraphNode::succ_iterator P = node->succ_begin(), - E = node->succ_end(); P != E; ++P) { + E = node->succ_end(); P != E; ++P) { if(!ignoreEdge(node, *P)) { @@ -822,7 +822,7 @@ int ModuloSchedulingPass::calculateHeight(MSchedGraphNode *node,MSchedGraphNode int ModuloSchedulingPass::calculateDepth(MSchedGraphNode *node, - MSchedGraphNode *destNode) { + MSchedGraphNode *destNode) { MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second; @@ -865,16 +865,16 @@ void ModuloSchedulingPass::addReccurrence(std::vector<MSchedGraphNode*> &recurre if(R->second.size() == recurrence.size()) { for(std::vector<MSchedGraphNode*>::const_iterator node = R->second.begin(), end = R->second.end(); node != end; ++node) { - if(std::find(recurrence.begin(), recurrence.end(), *node) == recurrence.end()) { - all_same = all_same && false; - break; - } - else - all_same = all_same && true; + if(std::find(recurrence.begin(), recurrence.end(), *node) == recurrence.end()) { + all_same = all_same && false; + break; + } + else + all_same = all_same && true; } if(all_same) { - same = true; - break; + same = true; + break; } } } @@ -888,12 +888,12 @@ void ModuloSchedulingPass::addReccurrence(std::vector<MSchedGraphNode*> &recurre //DEBUG(std::cerr << "NOT A BACKEDGE\n"); //find actual backedge HACK HACK for(unsigned i=0; i< recurrence.size()-1; ++i) { - if(recurrence[i+1]->getInEdge(recurrence[i]).getIteDiff() == 1) { - srcBENode = recurrence[i]; - destBENode = recurrence[i+1]; - break; - } - + if(recurrence[i+1]->getInEdge(recurrence[i]).getIteDiff() == 1) { + srcBENode = recurrence[i]; + destBENode = recurrence[i+1]; + break; + } + } } @@ -907,7 +907,7 @@ void ModuloSchedulingPass::addReccurrence(std::vector<MSchedGraphNode*> &recurre int CircCount; void ModuloSchedulingPass::unblock(MSchedGraphNode *u, std::set<MSchedGraphNode*> &blocked, - std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B) { + std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B) { //Unblock u DEBUG(std::cerr << "Unblocking: " << *u << "\n"); @@ -926,9 +926,9 @@ void ModuloSchedulingPass::unblock(MSchedGraphNode *u, std::set<MSchedGraphNode* } bool ModuloSchedulingPass::circuit(MSchedGraphNode *v, std::vector<MSchedGraphNode*> &stack, - std::set<MSchedGraphNode*> &blocked, std::vector<MSchedGraphNode*> &SCC, - MSchedGraphNode *s, std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B, - int II, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes) { + std::set<MSchedGraphNode*> &blocked, std::vector<MSchedGraphNode*> &SCC, + MSchedGraphNode *s, std::map<MSchedGraphNode*, std::set<MSchedGraphNode*> > &B, + int II, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes) { bool f = false; DEBUG(std::cerr << "Finding Circuits Starting with: ( " << v << ")"<< *v << "\n"); @@ -955,7 +955,7 @@ bool ModuloSchedulingPass::circuit(MSchedGraphNode *v, std::vector<MSchedGraphNo } else if(!blocked.count(*I)) { if(circuit(*I, stack, blocked, SCC, s, B, II, newNodes)) - f = true; + f = true; } else DEBUG(std::cerr << "Blocked: " << **I << "\n"); @@ -982,7 +982,7 @@ void ModuloSchedulingPass::addRecc(std::vector<MSchedGraphNode*> &stack, std::ma std::vector<MSchedGraphNode*> recc; //Dump recurrence for now DEBUG(std::cerr << "Starting Recc\n"); - + int totalDelay = 0; int totalDistance = 0; MSchedGraphNode *lastN = 0; @@ -998,8 +998,8 @@ void ModuloSchedulingPass::addRecc(std::vector<MSchedGraphNode*> &stack, std::ma totalDistance += iteDiff; if(iteDiff > 0) { - start = lastN; - end = *N; + start = lastN; + end = *N; } } //Get the original node @@ -1015,7 +1015,7 @@ void ModuloSchedulingPass::addRecc(std::vector<MSchedGraphNode*> &stack, std::ma DEBUG(std::cerr << "End Recc\n"); CircCount++; - if(start && end) { + if(start && end) { //Insert reccurrence into the list DEBUG(std::cerr << "Ignore Edge from!!: " << *start << " to " << *end << "\n"); edgesToIgnore.insert(std::make_pair(newNodes[start], (newNodes[end])->getInEdgeNum(newNodes[start]))); @@ -1031,7 +1031,7 @@ void ModuloSchedulingPass::addRecc(std::vector<MSchedGraphNode*> &stack, std::ma int value = totalDelay-(RecMII * totalDistance); int lastII = II; while(value < 0) { - + lastII = RecMII; RecMII--; value = totalDelay-(RecMII * totalDistance); @@ -1057,13 +1057,13 @@ void ModuloSchedulingPass::addSCC(std::vector<MSchedGraphNode*> &SCC, std::map<M for(unsigned i = 0; i < (*N)->succ_size(); ++i) { MSchedGraphEdge *edge = (*N)->getSuccessor(i); if(find(SCC.begin(), SCC.end(), edge->getDest()) != SCC.end()) { - totalDistance += edge->getIteDiff(); - if(edge->getIteDiff() > 0) - if(!start && !end) { - start = *N; - end = edge->getDest(); - } - + totalDistance += edge->getIteDiff(); + if(edge->getIteDiff() > 0) + if(!start && !end) { + start = *N; + end = edge->getDest(); + } + } } @@ -1079,7 +1079,7 @@ void ModuloSchedulingPass::addSCC(std::vector<MSchedGraphNode*> &SCC, std::map<M assert( (start && end) && "Must have start and end node to ignore edge for SCC"); - if(start && end) { + if(start && end) { //Insert reccurrence into the list DEBUG(std::cerr << "Ignore Edge from!!: " << *start << " to " << *end << "\n"); edgesToIgnore.insert(std::make_pair(newNodes[start], (newNodes[end])->getInEdgeNum(newNodes[start]))); @@ -1135,76 +1135,76 @@ void ModuloSchedulingPass::findAllCircuits(MSchedGraph *g, int II) { //Find scc with the least vertex for (MSchedGraph::iterator GI = MSG->begin(), E = MSG->end(); GI != E; ++GI) if (Visited.insert(GI->second).second) { - for (scc_iterator<MSchedGraphNode*> SCCI = scc_begin(GI->second), - E = scc_end(GI->second); SCCI != E; ++SCCI) { - std::vector<MSchedGraphNode*> &nextSCC = *SCCI; - - if (Visited.insert(nextSCC[0]).second) { - Visited.insert(nextSCC.begin()+1, nextSCC.end()); - - if(nextSCC.size() > 1) { - std::cerr << "SCC size: " << nextSCC.size() << "\n"; - - for(unsigned i = 0; i < nextSCC.size(); ++i) { - //Loop over successor and see if in scc, then count edge - MSchedGraphNode *node = nextSCC[i]; - for(MSchedGraphNode::succ_iterator S = node->succ_begin(), SE = node->succ_end(); S != SE; ++S) { - if(find(nextSCC.begin(), nextSCC.end(), *S) != nextSCC.end()) - numEdges++; - } - } - std::cerr << "Num Edges: " << numEdges << "\n"; - } - - //Ignore self loops - if(nextSCC.size() > 1) { - - //Get least vertex in Vk - if(!s) { - s = nextSCC[0]; - Vk = nextSCC; - } - - for(unsigned i = 0; i < nextSCC.size(); ++i) { - if(nextSCC[i] < s) { - s = nextSCC[i]; - Vk = nextSCC; - } - } - } - } - } + for (scc_iterator<MSchedGraphNode*> SCCI = scc_begin(GI->second), + E = scc_end(GI->second); SCCI != E; ++SCCI) { + std::vector<MSchedGraphNode*> &nextSCC = *SCCI; + + if (Visited.insert(nextSCC[0]).second) { + Visited.insert(nextSCC.begin()+1, nextSCC.end()); + + if(nextSCC.size() > 1) { + std::cerr << "SCC size: " << nextSCC.size() << "\n"; + + for(unsigned i = 0; i < nextSCC.size(); ++i) { + //Loop over successor and see if in scc, then count edge + MSchedGraphNode *node = nextSCC[i]; + for(MSchedGraphNode::succ_iterator S = node->succ_begin(), SE = node->succ_end(); S != SE; ++S) { + if(find(nextSCC.begin(), nextSCC.end(), *S) != nextSCC.end()) + numEdges++; + } + } + std::cerr << "Num Edges: " << numEdges << "\n"; + } + + //Ignore self loops + if(nextSCC.size() > 1) { + + //Get least vertex in Vk + if(!s) { + s = nextSCC[0]; + Vk = nextSCC; + } + + for(unsigned i = 0; i < nextSCC.size(); ++i) { + if(nextSCC[i] < s) { + s = nextSCC[i]; + Vk = nextSCC; + } + } + } + } + } } //Process SCC DEBUG(for(std::vector<MSchedGraphNode*>::iterator N = Vk.begin(), NE = Vk.end(); - N != NE; ++N) { std::cerr << *((*N)->getInst()); }); + N != NE; ++N) { std::cerr << *((*N)->getInst()); }); //Iterate over all nodes in this scc for(std::vector<MSchedGraphNode*>::iterator N = Vk.begin(), NE = Vk.end(); - N != NE; ++N) { + N != NE; ++N) { blocked.erase(*N); B[*N].clear(); } if(Vk.size() > 1) { if(numEdges < 98) - circuit(s, stack, blocked, Vk, s, B, II, newNodes); + circuit(s, stack, blocked, Vk, s, B, II, newNodes); else - addSCC(Vk, newNodes); + addSCC(Vk, newNodes); //Delete nodes from the graph //Find all nodes up to s and delete them std::vector<MSchedGraphNode*> nodesToRemove; nodesToRemove.push_back(s); for(MSchedGraph::iterator N = MSG->begin(), NE = MSG->end(); N != NE; ++N) { - if(N->second < s ) - nodesToRemove.push_back(N->second); + if(N->second < s ) + nodesToRemove.push_back(N->second); } for(std::vector<MSchedGraphNode*>::iterator N = nodesToRemove.begin(), NE = nodesToRemove.end(); N != NE; ++N) { - DEBUG(std::cerr << "Deleting Node: " << **N << "\n"); - MSG->deleteNode(*N); + DEBUG(std::cerr << "Deleting Node: " << **N << "\n"); + MSG->deleteNode(*N); } } else @@ -1215,8 +1215,8 @@ void ModuloSchedulingPass::findAllCircuits(MSchedGraph *g, int II) { void ModuloSchedulingPass::findAllReccurrences(MSchedGraphNode *node, - std::vector<MSchedGraphNode*> &visitedNodes, - int II) { + std::vector<MSchedGraphNode*> &visitedNodes, + int II) { if(std::find(visitedNodes.begin(), visitedNodes.end(), node) != visitedNodes.end()) { @@ -1232,22 +1232,22 @@ void ModuloSchedulingPass::findAllReccurrences(MSchedGraphNode *node, for(std::vector<MSchedGraphNode*>::iterator I = visitedNodes.begin(), E = visitedNodes.end(); - I !=E; ++I) { + I !=E; ++I) { if(*I == node) - first = false; + first = false; if(first) - continue; + continue; delay = delay + (*I)->getLatency(); if(*I != node) { - int diff = (*I)->getInEdge(last).getIteDiff(); - distance += diff; - if(diff > 0) { - srcBackEdge = last; - destBackEdge = *I; - } + int diff = (*I)->getInEdge(last).getIteDiff(); + distance += diff; + if(diff > 0) { + srcBackEdge = last; + destBackEdge = *I; + } } recurrence.push_back(*I); @@ -1289,9 +1289,9 @@ void ModuloSchedulingPass::findAllReccurrences(MSchedGraphNode *node, } void ModuloSchedulingPass::searchPath(MSchedGraphNode *node, - std::vector<MSchedGraphNode*> &path, - std::set<MSchedGraphNode*> &nodesToAdd, - std::set<MSchedGraphNode*> &new_reccurrence) { + std::vector<MSchedGraphNode*> &path, + std::set<MSchedGraphNode*> &nodesToAdd, + std::set<MSchedGraphNode*> &new_reccurrence) { //Push node onto the path path.push_back(node); @@ -1314,11 +1314,11 @@ void ModuloSchedulingPass::searchPath(MSchedGraphNode *node, //final vector bool found = false; for(std::vector<std::set<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), - PE = partialOrder.end(); PO != PE; ++PO) { + PE = partialOrder.end(); PO != PE; ++PO) { if(PO->count(*S)) { - found = true; - break; + found = true; + break; } } @@ -1333,9 +1333,9 @@ void ModuloSchedulingPass::searchPath(MSchedGraphNode *node, } void ModuloSchedulingPass::pathToRecc(MSchedGraphNode *node, - std::vector<MSchedGraphNode*> &path, - std::set<MSchedGraphNode*> &poSet, - std::set<MSchedGraphNode*> &lastNodes) { + std::vector<MSchedGraphNode*> &path, + std::set<MSchedGraphNode*> &poSet, + std::set<MSchedGraphNode*> &lastNodes) { //Push node onto the path path.push_back(node); @@ -1354,11 +1354,11 @@ void ModuloSchedulingPass::pathToRecc(MSchedGraphNode *node, DEBUG(std::cerr << "Found path to recc from no pred\n"); //Loop over path, if it exists in lastNodes, then add to poset, and remove from lastNodes for(std::vector<MSchedGraphNode*>::iterator I = path.begin(), IE = path.end(); I != IE; ++I) { - if(lastNodes.count(*I)) { - DEBUG(std::cerr << "Inserting node into recc: " << **I << "\n"); - poSet.insert(*I); - lastNodes.erase(*I); - } + if(lastNodes.count(*I)) { + DEBUG(std::cerr << "Inserting node into recc: " << **I << "\n"); + poSet.insert(*I); + lastNodes.erase(*I); + } } } else @@ -1387,28 +1387,28 @@ void ModuloSchedulingPass::computePartialOrder() { //along with any nodes that connect this recurrence to recurrences //already in the partial order for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::reverse_iterator - I = recurrenceList.rbegin(), E=recurrenceList.rend(); I !=E; ++I) { + I = recurrenceList.rbegin(), E=recurrenceList.rend(); I !=E; ++I) { std::set<MSchedGraphNode*> new_recurrence; //Loop through recurrence and remove any nodes already in the partial order for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), - NE = I->second.end(); N != NE; ++N) { + NE = I->second.end(); N != NE; ++N) { bool found = false; for(std::vector<std::set<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), - PE = partialOrder.end(); PO != PE; ++PO) { - if(PO->count(*N)) - found = true; + PE = partialOrder.end(); PO != PE; ++PO) { + if(PO->count(*N)) + found = true; } //Check if its a branch, and remove to handle special if(!found) { - if((*N)->isBranch() && !(*N)->hasPredecessors()) { - branches.push_back(*N); - } - else - new_recurrence.insert(*N); + if((*N)->isBranch() && !(*N)->hasPredecessors()) { + branches.push_back(*N); + } + else + new_recurrence.insert(*N); } } @@ -1426,21 +1426,21 @@ void ModuloSchedulingPass::computePartialOrder() { //Add nodes that connect this recurrence to recurrences in the partial path for(std::set<MSchedGraphNode*>::iterator N = new_recurrence.begin(), NE = new_recurrence.end(); N != NE; ++N) - searchPath(*N, path, nodesToAdd, new_recurrence); + searchPath(*N, path, nodesToAdd, new_recurrence); //Add nodes to this recurrence if they are not already in the partial order for(std::set<MSchedGraphNode*>::iterator N = nodesToAdd.begin(), NE = nodesToAdd.end(); - N != NE; ++N) { - bool found = false; - for(std::vector<std::set<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), - PE = partialOrder.end(); PO != PE; ++PO) { - if(PO->count(*N)) - found = true; - } - if(!found) { - assert("FOUND CONNECTOR"); - new_recurrence.insert(*N); - } + N != NE; ++N) { + bool found = false; + for(std::vector<std::set<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), + PE = partialOrder.end(); PO != PE; ++PO) { + if(PO->count(*N)) + found = true; + } + if(!found) { + assert("FOUND CONNECTOR"); + new_recurrence.insert(*N); + } } partialOrder.push_back(new_recurrence); @@ -1448,11 +1448,11 @@ void ModuloSchedulingPass::computePartialOrder() { //Dump out partial order DEBUG(for(std::vector<std::set<MSchedGraphNode*> >::iterator I = partialOrder.begin(), - E = partialOrder.end(); I !=E; ++I) { - std::cerr << "Start set in PO\n"; - for(std::set<MSchedGraphNode*>::iterator J = I->begin(), JE = I->end(); J != JE; ++J) - std::cerr << "PO:" << **J << "\n"; - }); + E = partialOrder.end(); I !=E; ++I) { + std::cerr << "Start set in PO\n"; + for(std::set<MSchedGraphNode*>::iterator J = I->begin(), JE = I->end(); J != JE; ++J) + std::cerr << "PO:" << **J << "\n"; + }); } } @@ -1462,15 +1462,15 @@ void ModuloSchedulingPass::computePartialOrder() { std::set<MSchedGraphNode*> lastNodes; std::set<MSchedGraphNode*> noPredNodes; for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), - E = nodeToAttributesMap.end(); I != E; ++I) { + E = nodeToAttributesMap.end(); I != E; ++I) { bool found = false; //Check if its already in our partial order, if not add it to the final vector for(std::vector<std::set<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), - PE = partialOrder.end(); PO != PE; ++PO) { + PE = partialOrder.end(); PO != PE; ++PO) { if(PO->count(I->first)) - found = true; + found = true; } if(!found) lastNodes.insert(I->first); @@ -1482,7 +1482,7 @@ void ModuloSchedulingPass::computePartialOrder() { N != NE; ++N) { DEBUG(std::cerr << "No Pred Path from: " << **N << "\n"); for(std::vector<std::set<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), - PE = partialOrder.end(); PO != PE; ++PO) { + PE = partialOrder.end(); PO != PE; ++PO) { std::vector<MSchedGraphNode*> path; pathToRecc(*N, path, *PO, lastNodes); } @@ -1495,7 +1495,7 @@ void ModuloSchedulingPass::computePartialOrder() { std::set<MSchedGraphNode*> ccSet; connectedComponentSet(*(lastNodes.begin()),ccSet, lastNodes); if(ccSet.size() > 0) - partialOrder.push_back(ccSet); + partialOrder.push_back(ccSet); } @@ -1525,15 +1525,15 @@ void ModuloSchedulingPass::predIntersect(std::set<MSchedGraphNode*> &CurrentSet, for(unsigned j=0; j < FinalNodeOrder.size(); ++j) { for(MSchedGraphNode::pred_iterator P = FinalNodeOrder[j]->pred_begin(), - E = FinalNodeOrder[j]->pred_end(); P != E; ++P) { + E = FinalNodeOrder[j]->pred_end(); P != E; ++P) { //Check if we are supposed to ignore this edge or not if(ignoreEdge(*P,FinalNodeOrder[j])) - continue; - + continue; + if(CurrentSet.count(*P)) - if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end()) - IntersectResult.insert(*P); + if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end()) + IntersectResult.insert(*P); } } } @@ -1546,15 +1546,15 @@ void ModuloSchedulingPass::succIntersect(std::set<MSchedGraphNode*> &CurrentSet, for(unsigned j=0; j < FinalNodeOrder.size(); ++j) { for(MSchedGraphNode::succ_iterator P = FinalNodeOrder[j]->succ_begin(), - E = FinalNodeOrder[j]->succ_end(); P != E; ++P) { + E = FinalNodeOrder[j]->succ_end(); P != E; ++P) { //Check if we are supposed to ignore this edge or not if(ignoreEdge(FinalNodeOrder[j],*P)) - continue; + continue; if(CurrentSet.count(*P)) - if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end()) - IntersectResult.insert(*P); + if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end()) + IntersectResult.insert(*P); } } } @@ -1604,28 +1604,28 @@ void ModuloSchedulingPass::orderNodes() { //sort top-down if(IntersectCurrent.size() != 0) { - DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is NOT empty\n"); - order = TOP_DOWN; + DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is NOT empty\n"); + order = TOP_DOWN; } else { - DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is empty\n"); - //Find node with max ASAP in current Set - MSchedGraphNode *node; - int maxASAP = 0; - DEBUG(std::cerr << "Using current set of size " << CurrentSet->size() << |