aboutsummaryrefslogtreecommitdiff
path: root/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp
diff options
context:
space:
mode:
authorJeff Cohen <jeffc@jolt-lang.org>2005-07-27 05:53:44 +0000
committerJeff Cohen <jeffc@jolt-lang.org>2005-07-27 05:53:44 +0000
commit9eb59ec548b861d6ede05b4e6dc22aabf645e665 (patch)
tree97ffa1993e23e29ccabac9646fc950717bd94dda /lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp
parent50e9ef8792c5c91b7ea6f24f878d1abbcb6024a4 (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.cpp1864
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() <<