1 //===-- ModuloScheduling.cpp - ModuloScheduling ----------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This ModuloScheduling pass is based on the Swing Modulo Scheduling
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "ModuloSched"
17 #include "ModuloScheduling.h"
18 #include "llvm/Instructions.h"
19 #include "llvm/Function.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/Support/CFG.h"
23 #include "llvm/Target/TargetSchedInfo.h"
24 #include "Support/Debug.h"
25 #include "Support/GraphWriter.h"
26 #include "Support/StringExtras.h"
32 #include "../../Target/SparcV9/MachineCodeForInstruction.h"
33 #include "../../Target/SparcV9/SparcV9TmpInstr.h"
34 #include "../../Target/SparcV9/SparcV9Internals.h"
35 #include "../../Target/SparcV9/SparcV9RegisterInfo.h"
38 /// Create ModuloSchedulingPass
40 FunctionPass *llvm::createModuloSchedulingPass(TargetMachine & targ) {
41 DEBUG(std::cerr << "Created ModuloSchedulingPass\n");
42 return new ModuloSchedulingPass(targ);
46 //Graph Traits for printing out the dependence graph
47 template<typename GraphType>
48 static void WriteGraphToFile(std::ostream &O, const std::string &GraphName,
49 const GraphType >) {
50 std::string Filename = GraphName + ".dot";
51 O << "Writing '" << Filename << "'...";
52 std::ofstream F(Filename.c_str());
57 O << " error opening file for writing!";
61 //Graph Traits for printing out the dependence graph
65 struct DOTGraphTraits<MSchedGraph*> : public DefaultDOTGraphTraits {
66 static std::string getGraphName(MSchedGraph *F) {
67 return "Dependence Graph";
70 static std::string getNodeLabel(MSchedGraphNode *Node, MSchedGraph *Graph) {
71 if (Node->getInst()) {
73 ss << *(Node->getInst());
74 return ss.str(); //((MachineInstr*)Node->getInst());
79 static std::string getEdgeSourceLabel(MSchedGraphNode *Node,
80 MSchedGraphNode::succ_iterator I) {
81 //Label each edge with the type of dependence
82 std::string edgelabel = "";
83 switch (I.getEdge().getDepOrderType()) {
85 case MSchedGraphEdge::TrueDep:
89 case MSchedGraphEdge::AntiDep:
93 case MSchedGraphEdge::OutputDep:
98 edgelabel = "Unknown";
103 int iteDiff = I.getEdge().getIteDiff();
104 std::string intStr = "(IteDiff: ";
105 intStr += itostr(iteDiff);
115 /// ModuloScheduling::runOnFunction - main transformation entry point
116 /// The Swing Modulo Schedule algorithm has three basic steps:
117 /// 1) Computation and Analysis of the dependence graph
118 /// 2) Ordering of the nodes
121 bool ModuloSchedulingPass::runOnFunction(Function &F) {
123 bool Changed = false;
125 DEBUG(std::cerr << "Creating ModuloSchedGraph for each valid BasicBlock in" + F.getName() + "\n");
127 //Get MachineFunction
128 MachineFunction &MF = MachineFunction::get(&F);
130 //Print out machine function
131 DEBUG(MF.print(std::cerr));
134 std::vector<MachineBasicBlock*> Worklist;
136 //Iterate over BasicBlocks and put them into our worklist if they are valid
137 for (MachineFunction::iterator BI = MF.begin(); BI != MF.end(); ++BI)
138 if(MachineBBisValid(BI))
139 Worklist.push_back(&*BI);
142 //Iterate over the worklist and perform scheduling
143 for(std::vector<MachineBasicBlock*>::iterator BI = Worklist.begin(),
144 BE = Worklist.end(); BI != BE; ++BI) {
146 MSchedGraph *MSG = new MSchedGraph(*BI, target);
148 //Write Graph out to file
149 DEBUG(WriteGraphToFile(std::cerr, F.getName(), MSG));
151 //Print out BB for debugging
152 DEBUG((*BI)->print(std::cerr));
154 //Calculate Resource II
155 int ResMII = calculateResMII(*BI);
157 //Calculate Recurrence II
158 int RecMII = calculateRecMII(MSG, ResMII);
160 //Our starting initiation interval is the maximum of RecMII and ResMII
161 II = std::max(RecMII, ResMII);
163 //Print out II, RecMII, and ResMII
164 DEBUG(std::cerr << "II starts out as " << II << " ( RecMII=" << RecMII << "and ResMII=" << ResMII << "\n");
166 //Calculate Node Properties
167 calculateNodeAttributes(MSG, ResMII);
169 //Dump node properties if in debug mode
170 DEBUG(for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(),
171 E = nodeToAttributesMap.end(); I !=E; ++I) {
172 std::cerr << "Node: " << *(I->first) << " ASAP: " << I->second.ASAP << " ALAP: "
173 << I->second.ALAP << " MOB: " << I->second.MOB << " Depth: " << I->second.depth
174 << " Height: " << I->second.height << "\n";
177 //Put nodes in order to schedule them
178 computePartialOrder();
180 //Dump out partial order
181 DEBUG(for(std::vector<std::vector<MSchedGraphNode*> >::iterator I = partialOrder.begin(),
182 E = partialOrder.end(); I !=E; ++I) {
183 std::cerr << "Start set in PO\n";
184 for(std::vector<MSchedGraphNode*>::iterator J = I->begin(), JE = I->end(); J != JE; ++J)
185 std::cerr << "PO:" << **J << "\n";
188 //Place nodes in final order
191 //Dump out order of nodes
192 DEBUG(for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(), E = FinalNodeOrder.end(); I != E; ++I) {
193 std::cerr << "FO:" << **I << "\n";
196 //Finally schedule nodes
199 //Print out final schedule
200 DEBUG(schedule.print(std::cerr));
203 //Final scheduling step is to reconstruct the loop
204 reconstructLoop(*BI);
209 //Clear out our maps for the next basic block that is processed
210 nodeToAttributesMap.clear();
211 partialOrder.clear();
212 recurrenceList.clear();
213 FinalNodeOrder.clear();
216 //Clean up. Nuke old MachineBB and llvmBB
217 //BasicBlock *llvmBB = (BasicBlock*) (*BI)->getBasicBlock();
218 //Function *parent = (Function*) llvmBB->getParent();
219 //Should't std::find work??
220 //parent->getBasicBlockList().erase(std::find(parent->getBasicBlockList().begin(), parent->getBasicBlockList().end(), *llvmBB));
221 //parent->getBasicBlockList().erase(llvmBB);
232 /// This function checks if a Machine Basic Block is valid for modulo
233 /// scheduling. This means that it has no control flow (if/else or
234 /// calls) in the block. Currently ModuloScheduling only works on
235 /// single basic block loops.
236 bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) {
240 //Check first if its a valid loop
241 for(succ_const_iterator I = succ_begin(BI->getBasicBlock()),
242 E = succ_end(BI->getBasicBlock()); I != E; ++I) {
243 if (*I == BI->getBasicBlock()) // has single block loop
250 //Get Target machine instruction info
251 const TargetInstrInfo *TMI = target.getInstrInfo();
253 //Check each instruction and look for calls
254 for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
255 //Get opcode to check instruction type
256 MachineOpCode OC = I->getOpcode();
265 //ResMII is calculated by determining the usage count for each resource
266 //and using the maximum.
267 //FIXME: In future there should be a way to get alternative resources
268 //for each instruction
269 int ModuloSchedulingPass::calculateResMII(const MachineBasicBlock *BI) {
271 const TargetInstrInfo *mii = target.getInstrInfo();
272 const TargetSchedInfo *msi = target.getSchedInfo();
276 //Map to keep track of usage count of each resource
277 std::map<unsigned, unsigned> resourceUsageCount;
279 for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
281 //Get resource usage for this instruction
282 InstrRUsage rUsage = msi->getInstrRUsage(I->getOpcode());
283 std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
285 //Loop over resources in each cycle and increments their usage count
286 for(unsigned i=0; i < resources.size(); ++i)
287 for(unsigned j=0; j < resources[i].size(); ++j) {
288 if( resourceUsageCount.find(resources[i][j]) == resourceUsageCount.end()) {
289 resourceUsageCount[resources[i][j]] = 1;
292 resourceUsageCount[resources[i][j]] = resourceUsageCount[resources[i][j]] + 1;
297 //Find maximum usage count
299 //Get max number of instructions that can be issued at once. (FIXME)
300 int issueSlots = msi->maxNumIssueTotal;
302 for(std::map<unsigned,unsigned>::iterator RB = resourceUsageCount.begin(), RE = resourceUsageCount.end(); RB != RE; ++RB) {
304 //Get the total number of the resources in our cpu
305 int resourceNum = CPUResource::getCPUResource(RB->first)->maxNumUsers;
307 //Get total usage count for this resources
308 unsigned usageCount = RB->second;
310 //Divide the usage count by either the max number we can issue or the number of
311 //resources (whichever is its upper bound)
312 double finalUsageCount;
313 if( resourceNum <= issueSlots)
314 finalUsageCount = ceil(1.0 * usageCount / resourceNum);
316 finalUsageCount = ceil(1.0 * usageCount / issueSlots);
319 //Only keep track of the max
320 ResMII = std::max( (int) finalUsageCount, ResMII);
328 /// calculateRecMII - Calculates the value of the highest recurrence
329 /// By value we mean the total latency
330 int ModuloSchedulingPass::calculateRecMII(MSchedGraph *graph, int MII) {
331 std::vector<MSchedGraphNode*> vNodes;
332 //Loop over all nodes in the graph
333 for(MSchedGraph::iterator I = graph->begin(), E = graph->end(); I != E; ++I) {
334 findAllReccurrences(I->second, vNodes, MII);
340 for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::iterator I = recurrenceList.begin(), E=recurrenceList.end(); I !=E; ++I) {
341 DEBUG(for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
342 std::cerr << **N << "\n";
344 RecMII = std::max(RecMII, I->first);
350 /// calculateNodeAttributes - The following properties are calculated for
351 /// each node in the dependence graph: ASAP, ALAP, Depth, Height, and
353 void ModuloSchedulingPass::calculateNodeAttributes(MSchedGraph *graph, int MII) {
355 //Loop over the nodes and add them to the map
356 for(MSchedGraph::iterator I = graph->begin(), E = graph->end(); I != E; ++I) {
357 //Assert if its already in the map
358 assert(nodeToAttributesMap.find(I->second) == nodeToAttributesMap.end() && "Node attributes are already in the map");
360 //Put into the map with default attribute values
361 nodeToAttributesMap[I->second] = MSNodeAttributes();
364 //Create set to deal with reccurrences
365 std::set<MSchedGraphNode*> visitedNodes;
367 //Now Loop over map and calculate the node attributes
368 for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
369 calculateASAP(I->first, MII, (MSchedGraphNode*) 0);
370 visitedNodes.clear();
373 int maxASAP = findMaxASAP();
374 //Calculate ALAP which depends on ASAP being totally calculated
375 for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
376 calculateALAP(I->first, MII, maxASAP, (MSchedGraphNode*) 0);
377 visitedNodes.clear();
380 //Calculate MOB which depends on ASAP being totally calculated, also do depth and height
381 for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
382 (I->second).MOB = std::max(0,(I->second).ALAP - (I->second).ASAP);
384 DEBUG(std::cerr << "MOB: " << (I->second).MOB << " (" << *(I->first) << ")\n");
385 calculateDepth(I->first, (MSchedGraphNode*) 0);
386 calculateHeight(I->first, (MSchedGraphNode*) 0);
392 /// ignoreEdge - Checks to see if this edge of a recurrence should be ignored or not
393 bool ModuloSchedulingPass::ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode) {
394 if(destNode == 0 || srcNode ==0)
397 bool findEdge = edgesToIgnore.count(std::make_pair(srcNode, destNode->getInEdgeNum(srcNode)));
403 /// calculateASAP - Calculates the
404 int ModuloSchedulingPass::calculateASAP(MSchedGraphNode *node, int MII, MSchedGraphNode *destNode) {
406 DEBUG(std::cerr << "Calculating ASAP for " << *node << "\n");
408 //Get current node attributes
409 MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
411 if(attributes.ASAP != -1)
412 return attributes.ASAP;
414 int maxPredValue = 0;
416 //Iterate over all of the predecessors and find max
417 for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
419 //Only process if we are not ignoring the edge
420 if(!ignoreEdge(*P, node)) {
422 predASAP = calculateASAP(*P, MII, node);
424 assert(predASAP != -1 && "ASAP has not been calculated");
425 int iteDiff = node->getInEdge(*P).getIteDiff();
427 int currentPredValue = predASAP + (*P)->getLatency() - (iteDiff * MII);
428 DEBUG(std::cerr << "pred ASAP: " << predASAP << ", iteDiff: " << iteDiff << ", PredLatency: " << (*P)->getLatency() << ", Current ASAP pred: " << currentPredValue << "\n");
429 maxPredValue = std::max(maxPredValue, currentPredValue);
433 attributes.ASAP = maxPredValue;
435 DEBUG(std::cerr << "ASAP: " << attributes.ASAP << " (" << *node << ")\n");
441 int ModuloSchedulingPass::calculateALAP(MSchedGraphNode *node, int MII,
442 int maxASAP, MSchedGraphNode *srcNode) {
444 DEBUG(std::cerr << "Calculating ALAP for " << *node << "\n");
446 MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
448 if(attributes.ALAP != -1)
449 return attributes.ALAP;
451 if(node->hasSuccessors()) {
453 //Trying to deal with the issue where the node has successors, but
454 //we are ignoring all of the edges to them. So this is my hack for
455 //now.. there is probably a more elegant way of doing this (FIXME)
456 bool processedOneEdge = false;
458 //FIXME, set to something high to start
459 int minSuccValue = 9999999;
461 //Iterate over all of the predecessors and fine max
462 for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
463 E = node->succ_end(); P != E; ++P) {
465 //Only process if we are not ignoring the edge
466 if(!ignoreEdge(node, *P)) {
467 processedOneEdge = true;
469 succALAP = calculateALAP(*P, MII, maxASAP, node);
471 assert(succALAP != -1 && "Successors ALAP should have been caclulated");
473 int iteDiff = P.getEdge().getIteDiff();
475 int currentSuccValue = succALAP - node->getLatency() + iteDiff * MII;
477 DEBUG(std::cerr << "succ ALAP: " << succALAP << ", iteDiff: " << iteDiff << ", SuccLatency: " << (*P)->getLatency() << ", Current ALAP succ: " << currentSuccValue << "\n");
479 minSuccValue = std::min(minSuccValue, currentSuccValue);
484 attributes.ALAP = minSuccValue;
487 attributes.ALAP = maxASAP;
490 attributes.ALAP = maxASAP;
492 DEBUG(std::cerr << "ALAP: " << attributes.ALAP << " (" << *node << ")\n");
494 if(attributes.ALAP < 0)
497 return attributes.ALAP;
500 int ModuloSchedulingPass::findMaxASAP() {
503 for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(),
504 E = nodeToAttributesMap.end(); I != E; ++I)
505 maxASAP = std::max(maxASAP, I->second.ASAP);
510 int ModuloSchedulingPass::calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode) {
512 MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
514 if(attributes.height != -1)
515 return attributes.height;
519 //Iterate over all of the predecessors and find max
520 for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
521 E = node->succ_end(); P != E; ++P) {
524 if(!ignoreEdge(node, *P)) {
525 int succHeight = calculateHeight(*P, node);
527 assert(succHeight != -1 && "Successors Height should have been caclulated");
529 int currentHeight = succHeight + node->getLatency();
530 maxHeight = std::max(maxHeight, currentHeight);
533 attributes.height = maxHeight;
534 DEBUG(std::cerr << "Height: " << attributes.height << " (" << *node << ")\n");
539 int ModuloSchedulingPass::calculateDepth(MSchedGraphNode *node,
540 MSchedGraphNode *destNode) {
542 MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
544 if(attributes.depth != -1)
545 return attributes.depth;
549 //Iterate over all of the predecessors and fine max
550 for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
552 if(!ignoreEdge(*P, node)) {
554 predDepth = calculateDepth(*P, node);
556 assert(predDepth != -1 && "Predecessors ASAP should have been caclulated");
558 int currentDepth = predDepth + (*P)->getLatency();
559 maxDepth = std::max(maxDepth, currentDepth);
562 attributes.depth = maxDepth;
564 DEBUG(std::cerr << "Depth: " << attributes.depth << " (" << *node << "*)\n");
570 void ModuloSchedulingPass::addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode *srcBENode, MSchedGraphNode *destBENode) {
571 //Check to make sure that this recurrence is unique
575 //Loop over all recurrences already in our list
576 for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::iterator R = recurrenceList.begin(), RE = recurrenceList.end(); R != RE; ++R) {
578 bool all_same = true;
580 if(R->second.size() == recurrence.size()) {
582 for(std::vector<MSchedGraphNode*>::const_iterator node = R->second.begin(), end = R->second.end(); node != end; ++node) {
583 if(find(recurrence.begin(), recurrence.end(), *node) == recurrence.end()) {
584 all_same = all_same && false;
588 all_same = all_same && true;
598 srcBENode = recurrence.back();
599 destBENode = recurrence.front();
602 if(destBENode->getInEdge(srcBENode).getIteDiff() == 0) {
603 //DEBUG(std::cerr << "NOT A BACKEDGE\n");
604 //find actual backedge HACK HACK
605 for(unsigned i=0; i< recurrence.size()-1; ++i) {
606 if(recurrence[i+1]->getInEdge(recurrence[i]).getIteDiff() == 1) {
607 srcBENode = recurrence[i];
608 destBENode = recurrence[i+1];
615 DEBUG(std::cerr << "Back Edge to Remove: " << *srcBENode << " to " << *destBENode << "\n");
616 edgesToIgnore.insert(std::make_pair(srcBENode, destBENode->getInEdgeNum(srcBENode)));
617 recurrenceList.insert(std::make_pair(II, recurrence));
622 void ModuloSchedulingPass::findAllReccurrences(MSchedGraphNode *node,
623 std::vector<MSchedGraphNode*> &visitedNodes,
626 if(find(visitedNodes.begin(), visitedNodes.end(), node) != visitedNodes.end()) {
627 std::vector<MSchedGraphNode*> recurrence;
631 int RecMII = II; //Starting value
632 MSchedGraphNode *last = node;
633 MSchedGraphNode *srcBackEdge = 0;
634 MSchedGraphNode *destBackEdge = 0;
638 for(std::vector<MSchedGraphNode*>::iterator I = visitedNodes.begin(), E = visitedNodes.end();
646 delay = delay + (*I)->getLatency();
649 int diff = (*I)->getInEdge(last).getIteDiff();
657 recurrence.push_back(*I);
663 //Get final distance calc
664 distance += node->getInEdge(last).getIteDiff();
667 //Adjust II until we get close to the inequality delay - II*distance <= 0
669 int value = delay-(RecMII * distance);
675 value = delay-(RecMII * distance);
679 DEBUG(std::cerr << "Final II for this recurrence: " << lastII << "\n");
680 addReccurrence(recurrence, lastII, srcBackEdge, destBackEdge);
681 assert(distance != 0 && "Recurrence distance should not be zero");
685 for(MSchedGraphNode::succ_iterator I = node->succ_begin(), E = node->succ_end(); I != E; ++I) {
686 visitedNodes.push_back(node);
687 findAllReccurrences(*I, visitedNodes, II);
688 visitedNodes.pop_back();
696 void ModuloSchedulingPass::computePartialOrder() {
699 //Loop over all recurrences and add to our partial order
700 //be sure to remove nodes that are already in the partial order in
701 //a different recurrence and don't add empty recurrences.
702 for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::reverse_iterator I = recurrenceList.rbegin(), E=recurrenceList.rend(); I !=E; ++I) {
704 //Add nodes that connect this recurrence to the previous recurrence
706 //If this is the first recurrence in the partial order, add all predecessors
707 for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
712 std::vector<MSchedGraphNode*> new_recurrence;
713 //Loop through recurrence and remove any nodes already in the partial order
714 for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
716 for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PE = partialOrder.end(); PO != PE; ++PO) {
717 if(find(PO->begin(), PO->end(), *N) != PO->end())
721 new_recurrence.push_back(*N);
723 if(partialOrder.size() == 0)
724 //For each predecessors, add it to this recurrence ONLY if it is not already in it
725 for(MSchedGraphNode::pred_iterator P = (*N)->pred_begin(),
726 PE = (*N)->pred_end(); P != PE; ++P) {
728 //Check if we are supposed to ignore this edge or not
729 if(!ignoreEdge(*P, *N))
730 //Check if already in this recurrence
731 if(find(I->second.begin(), I->second.end(), *P) == I->second.end()) {
732 //Also need to check if in partial order
733 bool predFound = false;
734 for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PEND = partialOrder.end(); PO != PEND; ++PO) {
735 if(find(PO->begin(), PO->end(), *P) != PO->end())
740 if(find(new_recurrence.begin(), new_recurrence.end(), *P) == new_recurrence.end())
741 new_recurrence.push_back(*P);
749 if(new_recurrence.size() > 0)
750 partialOrder.push_back(new_recurrence);
753 //Add any nodes that are not already in the partial order
754 std::vector<MSchedGraphNode*> lastNodes;
755 for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
757 //Check if its already in our partial order, if not add it to the final vector
758 for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PE = partialOrder.end(); PO != PE; ++PO) {
759 if(find(PO->begin(), PO->end(), I->first) != PO->end())
763 lastNodes.push_back(I->first);
766 if(lastNodes.size() > 0)
767 partialOrder.push_back(lastNodes);
772 void ModuloSchedulingPass::predIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult) {
774 //Sort CurrentSet so we can use lowerbound
775 sort(CurrentSet.begin(), CurrentSet.end());
777 for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
778 for(MSchedGraphNode::pred_iterator P = FinalNodeOrder[j]->pred_begin(),
779 E = FinalNodeOrder[j]->pred_end(); P != E; ++P) {
781 //Check if we are supposed to ignore this edge or not
782 if(ignoreEdge(*P,FinalNodeOrder[j]))
785 if(find(CurrentSet.begin(),
786 CurrentSet.end(), *P) != CurrentSet.end())
787 if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end())
788 IntersectResult.push_back(*P);
793 void ModuloSchedulingPass::succIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult) {
795 //Sort CurrentSet so we can use lowerbound
796 sort(CurrentSet.begin(), CurrentSet.end());
798 for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
799 for(MSchedGraphNode::succ_iterator P = FinalNodeOrder[j]->succ_begin(),
800 E = FinalNodeOrder[j]->succ_end(); P != E; ++P) {
802 //Check if we are supposed to ignore this edge or not
803 if(ignoreEdge(FinalNodeOrder[j],*P))
806 if(find(CurrentSet.begin(),
807 CurrentSet.end(), *P) != CurrentSet.end())
808 if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end())
809 IntersectResult.push_back(*P);
814 void dumpIntersection(std::vector<MSchedGraphNode*> &IntersectCurrent) {
815 std::cerr << "Intersection (";
816 for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(), E = IntersectCurrent.end(); I != E; ++I)
817 std::cerr << **I << ", ";
823 void ModuloSchedulingPass::orderNodes() {
829 int order = BOTTOM_UP;
832 //Loop over all the sets and place them in the final node order
833 for(std::vector<std::vector<MSchedGraphNode*> >::iterator CurrentSet = partialOrder.begin(), E= partialOrder.end(); CurrentSet != E; ++CurrentSet) {
835 DEBUG(std::cerr << "Processing set in S\n");
836 DEBUG(dumpIntersection(*CurrentSet));
838 //Result of intersection
839 std::vector<MSchedGraphNode*> IntersectCurrent;
841 predIntersect(*CurrentSet, IntersectCurrent);
843 //If the intersection of predecessor and current set is not empty
844 //sort nodes bottom up
845 if(IntersectCurrent.size() != 0) {
846 DEBUG(std::cerr << "Final Node Order Predecessors and Current Set interesection is NOT empty\n");
849 //If empty, use successors
851 DEBUG(std::cerr << "Final Node Order Predecessors and Current Set interesection is empty\n");
853 succIntersect(*CurrentSet, IntersectCurrent);
856 if(IntersectCurrent.size() != 0) {
857 DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is NOT empty\n");
861 DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is empty\n");
862 //Find node with max ASAP in current Set
863 MSchedGraphNode *node;
865 DEBUG(std::cerr << "Using current set of size " << CurrentSet->size() << "to find max ASAP\n");
866 for(unsigned j=0; j < CurrentSet->size(); ++j) {
867 //Get node attributes
868 MSNodeAttributes nodeAttr= nodeToAttributesMap.find((*CurrentSet)[j])->second;
869 //assert(nodeAttr != nodeToAttributesMap.end() && "Node not in attributes map!");
870 DEBUG(std::cerr << "CurrentSet index " << j << "has ASAP: " << nodeAttr.ASAP << "\n");
871 if(maxASAP < nodeAttr.ASAP) {
872 maxASAP = nodeAttr.ASAP;
873 node = (*CurrentSet)[j];
876 assert(node != 0 && "In node ordering node should not be null");
877 IntersectCurrent.push_back(node);
882 //Repeat until all nodes are put into the final order from current set
883 while(IntersectCurrent.size() > 0) {
885 if(order == TOP_DOWN) {
886 DEBUG(std::cerr << "Order is TOP DOWN\n");
888 while(IntersectCurrent.size() > 0) {
889 DEBUG(std::cerr << "Intersection is not empty, so find heighest height\n");
893 MSchedGraphNode *highestHeightNode = IntersectCurrent[0];
895 //Find node in intersection with highest heigh and lowest MOB
896 for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(),
897 E = IntersectCurrent.end(); I != E; ++I) {
899 //Get current nodes properties
900 MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second;
902 if(height < nodeAttr.height) {
903 highestHeightNode = *I;
904 height = nodeAttr.height;
907 else if(height == nodeAttr.height) {
908 if(MOB > nodeAttr.height) {
909 highestHeightNode = *I;
910 height = nodeAttr.height;
916 //Append our node with greatest height to the NodeOrder
917 if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestHeightNode) == FinalNodeOrder.end()) {
918 DEBUG(std::cerr << "Adding node to Final Order: " << *highestHeightNode << "\n");
919 FinalNodeOrder.push_back(highestHeightNode);
922 //Remove V from IntersectOrder
923 IntersectCurrent.erase(find(IntersectCurrent.begin(),
924 IntersectCurrent.end(), highestHeightNode));
927 //Intersect V's successors with CurrentSet
928 for(MSchedGraphNode::succ_iterator P = highestHeightNode->succ_begin(),
929 E = highestHeightNode->succ_end(); P != E; ++P) {
930 //if(lower_bound(CurrentSet->begin(),
931 // CurrentSet->end(), *P) != CurrentSet->end()) {
932 if(find(CurrentSet->begin(), CurrentSet->end(), *P) != CurrentSet->end()) {
933 if(ignoreEdge(highestHeightNode, *P))
935 //If not already in Intersect, add
936 if(find(IntersectCurrent.begin(), IntersectCurrent.end(), *P) == IntersectCurrent.end())
937 IntersectCurrent.push_back(*P);
940 } //End while loop over Intersect Size
945 //Reset Intersect to reflect changes in OrderNodes
946 IntersectCurrent.clear();
947 predIntersect(*CurrentSet, IntersectCurrent);
953 DEBUG(std::cerr << "Order is BOTTOM UP\n");
954 while(IntersectCurrent.size() > 0) {
955 DEBUG(std::cerr << "Intersection of size " << IntersectCurrent.size() << ", finding highest depth\n");
958 DEBUG(dumpIntersection(IntersectCurrent));
959 //Get node with highest depth, if a tie, use one with lowest
963 MSchedGraphNode *highestDepthNode = IntersectCurrent[0];
965 for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(),
966 E = IntersectCurrent.end(); I != E; ++I) {
967 //Find node attribute in graph
968 MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second;
970 if(depth < nodeAttr.depth) {
971 highestDepthNode = *I;
972 depth = nodeAttr.depth;
975 else if(depth == nodeAttr.depth) {
976 if(MOB > nodeAttr.MOB) {
977 highestDepthNode = *I;
978 depth = nodeAttr.depth;
986 //Append highest depth node to the NodeOrder
987 if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestDepthNode) == FinalNodeOrder.end()) {
988 DEBUG(std::cerr << "Adding node to Final Order: " << *highestDepthNode << "\n");
989 FinalNodeOrder.push_back(highestDepthNode);
991 //Remove heightestDepthNode from IntersectOrder
992 IntersectCurrent.erase(find(IntersectCurrent.begin(),
993 IntersectCurrent.end(),highestDepthNode));
996 //Intersect heightDepthNode's pred with CurrentSet
997 for(MSchedGraphNode::pred_iterator P = highestDepthNode->pred_begin(),
998 E = highestDepthNode->pred_end(); P != E; ++P) {
999 //if(lower_bound(CurrentSet->begin(),
1000 // CurrentSet->end(), *P) != CurrentSet->end()) {
1001 if(find(CurrentSet->begin(), CurrentSet->end(), *P) != CurrentSet->end()) {
1003 if(ignoreEdge(*P, highestDepthNode))
1006 //If not already in Intersect, add
1007 if(find(IntersectCurrent.begin(),
1008 IntersectCurrent.end(), *P) == IntersectCurrent.end())
1009 IntersectCurrent.push_back(*P);
1013 } //End while loop over Intersect Size
1018 //Reset IntersectCurrent to reflect changes in OrderNodes
1019 IntersectCurrent.clear();
1020 succIntersect(*CurrentSet, IntersectCurrent);
1021 } //End if BOTTOM_DOWN
1024 //End Wrapping while loop
1026 }//End for over all sets of nodes
1028 //Return final Order
1029 //return FinalNodeOrder;
1032 void ModuloSchedulingPass::computeSchedule() {
1034 bool success = false;
1038 //Loop over the final node order and process each node
1039 for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(),
1040 E = FinalNodeOrder.end(); I != E; ++I) {
1042 //CalculateEarly and Late start
1043 int EarlyStart = -1;
1044 int LateStart = 99999; //Set to something higher then we would ever expect (FIXME)
1045 bool hasSucc = false;
1046 bool hasPred = false;
1048 if(!(*I)->isBranch()) {
1049 //Loop over nodes in the schedule and determine if they are predecessors
1050 //or successors of the node we are trying to schedule
1051 for(MSSchedule::schedule_iterator nodesByCycle = schedule.begin(), nodesByCycleEnd = schedule.end();
1052 nodesByCycle != nodesByCycleEnd; ++nodesByCycle) {
1054 //For this cycle, get the vector of nodes schedule and loop over it
1055 for(std::vector<MSchedGraphNode*>::iterator schedNode = nodesByCycle->second.begin(), SNE = nodesByCycle->second.end(); schedNode != SNE; ++schedNode) {
1057 if((*I)->isPredecessor(*schedNode)) {
1058 if(!ignoreEdge(*schedNode, *I)) {
1059 int diff = (*I)->getInEdge(*schedNode).getIteDiff();
1060 int ES_Temp = nodesByCycle->first + (*schedNode)->getLatency() - diff * II;
1061 DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n");
1062 DEBUG(std::cerr << "Temp EarlyStart: " << ES_Temp << " Prev EarlyStart: " << EarlyStart << "\n");
1063 EarlyStart = std::max(EarlyStart, ES_Temp);
1067 if((*I)->isSuccessor(*schedNode)) {
1068 if(!ignoreEdge(*I,*schedNode)) {
1069 int diff = (*schedNode)->getInEdge(*I).getIteDiff();
1070 int LS_Temp = nodesByCycle->first - (*I)->getLatency() + diff * II;
1071 DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n");
1072 DEBUG(std::cerr << "Temp LateStart: " << LS_Temp << " Prev LateStart: " << LateStart << "\n");
1073 LateStart = std::min(LateStart, LS_Temp);
1081 //WARNING: HACK! FIXME!!!!
1089 DEBUG(std::cerr << "Has Successors: " << hasSucc << ", Has Pred: " << hasPred << "\n");
1090 DEBUG(std::cerr << "EarlyStart: " << EarlyStart << ", LateStart: " << LateStart << "\n");
1092 //Check if the node has no pred or successors and set Early Start to its ASAP
1093 if(!hasSucc && !hasPred)
1094 EarlyStart = nodeToAttributesMap.find(*I)->second.ASAP;
1096 //Now, try to schedule this node depending upon its pred and successor in the schedule
1098 if(!hasSucc && hasPred)
1099 success = scheduleNode(*I, EarlyStart, (EarlyStart + II -1));
1100 else if(!hasPred && hasSucc)
1101 success = scheduleNode(*I, LateStart, (LateStart - II +1));
1102 else if(hasPred && hasSucc)
1103 success = scheduleNode(*I, EarlyStart, std::min(LateStart, (EarlyStart + II -1)));
1105 success = scheduleNode(*I, EarlyStart, EarlyStart + II - 1);
1115 DEBUG(std::cerr << "Constructing Kernel\n");
1116 success = schedule.constructKernel(II);
1125 bool ModuloSchedulingPass::scheduleNode(MSchedGraphNode *node,
1126 int start, int end) {
1127 bool success = false;
1129 DEBUG(std::cerr << *node << " (Start Cycle: " << start << ", End Cycle: " << end << ")\n");
1131 //Make sure start and end are not negative
1137 bool forward = true;
1141 bool increaseSC = true;
1149 increaseSC = schedule.insert(node, cycle);
1154 //Increment cycle to try again
1157 DEBUG(std::cerr << "Increase cycle: " << cycle << "\n");
1163 DEBUG(std::cerr << "Decrease cycle: " << cycle << "\n");
1172 void ModuloSchedulingPass::writePrologues(std::vector<MachineBasicBlock *> &prologues, MachineBasicBlock *origBB, std::vector<BasicBlock*> &llvm_prologues, std::map<const Value*, std::pair<const MSchedGraphNode*, int> > &valuesToSave, std::map<Value*, std::map<int, std::vector<Value*> > > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation) {
1174 //Keep a map to easily know whats in the kernel
1175 std::map<int, std::set<const MachineInstr*> > inKernel;
1176 int maxStageCount = 0;
1178 MSchedGraphNode *branch = 0;
1180 for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1181 maxStageCount = std::max(maxStageCount, I->second);
1183 //Ignore the branch, we will handle this separately
1184 if(I->first->isBranch()) {
1189 //Put int the map so we know what instructions in each stage are in the kernel
1190 DEBUG(std::cerr << "Inserting instruction " << *(I->first->getInst()) << " into map at stage " << I->second << "\n");
1191 inKernel[I->second].insert(I->first->getInst());
1194 //Get target information to look at machine operands
1195 const TargetInstrInfo *mii = target.getInstrInfo();
1197 //Now write the prologues
1198 for(int i = 0; i < maxStageCount; ++i) {
1199 BasicBlock *llvmBB = new BasicBlock("PROLOGUE", (Function*) (origBB->getBasicBlock()->getParent()));
1200 MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB);
1202 DEBUG(std::cerr << "i=" << i << "\n");
1203 for(int j = 0; j <= i; ++j) {
1204 for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) {
1205 if(inKernel[j].count(&*MI)) {
1206 machineBB->push_back(MI->clone());
1210 //After cloning, we may need to save the value that this instruction defines
1211 for(unsigned opNum=0; opNum < MI->getNumOperands(); ++opNum) {
1212 //get machine operand
1213 const MachineOperand &mOp = MI->getOperand(opNum);
1214 if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
1217 //Check if this is a value we should save
1218 if(valuesToSave.count(mOp.getVRegValue())) {
1219 //Save copy in tmpInstruction
1220 tmp = new TmpInstruction(mOp.getVRegValue());
1222 DEBUG(std::cerr << "Value: " << mOp.getVRegValue() << " New Value: " << tmp << " Stage: " << i << "\n");
1223 newValues[mOp.getVRegValue()][i].push_back(tmp);
1224 newValLocation[tmp] = machineBB;
1226 DEBUG(std::cerr << "Machine Instr Operands: " << mOp.getVRegValue() << ", 0, " << tmp << "\n");
1228 //Create machine instruction and put int machineBB
1229 MachineInstr *saveValue = BuildMI(machineBB, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp);
1231 DEBUG(std::cerr << "Created new machine instr: " << *saveValue << "\n");
1240 //Stick in branch at the end
1241 machineBB->push_back(branch->getInst()->clone());
1243 (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB);
1244 prologues.push_back(machineBB);
1245 llvm_prologues.push_back(llvmBB);
1249 void ModuloSchedulingPass::writeEpilogues(std::vector<MachineBasicBlock *> &epilogues, const MachineBasicBlock *origBB, std::vector<BasicBlock*> &llvm_epilogues, std::map<const Value*, std::pair<const MSchedGraphNode*, int> > &valuesToSave, std::map<Value*, std::map<int, std::vector<Value*> > > &newValues,std::map<Value*, MachineBasicBlock*> &newValLocation ) {
1251 std::map<int, std::set<const MachineInstr*> > inKernel;
1252 int maxStageCount = 0;
1253 for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1254 maxStageCount = std::max(maxStageCount, I->second);
1256 //Ignore the branch, we will handle this separately
1257 if(I->first->isBranch())
1260 //Put int the map so we know what instructions in each stage are in the kernel
1261 inKernel[I->second].insert(I->first->getInst());
1264 std::map<Value*, Value*> valPHIs;
1266 //Now write the epilogues
1267 for(int i = maxStageCount-1; i >= 0; --i) {
1268 BasicBlock *llvmBB = new BasicBlock("EPILOGUE", (Function*) (origBB->getBasicBlock()->getParent()));
1269 MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB);
1271 DEBUG(std::cerr << " i: " << i << "\n");
1273 //Spit out phi nodes
1274 for(std::map<Value*, std::map<int, std::vector<Value*> > >::iterator V = newValues.begin(), E = newValues.end();
1277 DEBUG(std::cerr << "Writing phi for" << *(V->first));
1278 for(std::map<int, std::vector<Value*> >::iterator I = V->second.begin(), IE = V->second.end(); I != IE; ++I) {
1280 DEBUG(std::cerr << "BLAH " << i << "\n");
1282 //Vector must have two elements in it:
1283 assert(I->second.size() == 2 && "Vector size should be two\n");
1285 Instruction *tmp = new TmpInstruction(I->second[0]);
1286 MachineInstr *saveValue = BuildMI(machineBB, V9::PHI, 3).addReg(I->second[0]).addReg(I->second[1]).addRegDef(tmp);
1287 valPHIs[V->first] = tmp;
1293 for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) {
1294 for(int j=maxStageCount; j > i; --j) {
1295 if(inKernel[j].count(&*MI)) {
1296 DEBUG(std::cerr << "Cloning instruction " << *MI << "\n");
1297 MachineInstr *clone = MI->clone();
1299 //Update operands that need to use the result from the phi
1300 for(unsigned i=0; i < clone->getNumOperands(); ++i) {
1301 //get machine operand
1302 const MachineOperand &mOp = clone->getOperand(i);
1303 if((mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse())) {
1304 if(valPHIs.count(mOp.getVRegValue())) {
1305 //Update the operand in the cloned instruction
1306 clone->getOperand(i).setValueReg(valPHIs[mOp.getVRegValue()]);
1310 machineBB->push_back(clone);
1315 (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB);
1316 epilogues.push_back(machineBB);
1317 llvm_epilogues.push_back(llvmBB);
1321 void ModuloSchedulingPass::writeKernel(BasicBlock *llvmBB, MachineBasicBlock *machineBB, std::map<const Value*, std::pair<const MSchedGraphNode*, int> > &valuesToSave, std::map<Value*, std::map<int, std::vector<Value*> > > &newValues, std::map<Value*, MachineBasicBlock*> &newValLocation) {
1323 //Keep track of operands that are read and saved from a previous iteration. The new clone
1324 //instruction will use the result of the phi instead.
1325 std::map<Value*, Value*> finalPHIValue;
1326 std::map<Value*, Value*> kernelValue;
1328 //Create TmpInstructions for the final phis
1329 for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1332 const MachineInstr *inst = I->first->getInst();
1333 MachineInstr *instClone = inst->clone();
1335 //If this instruction is from a previous iteration, update its operands
1337 //Loop over Machine Operands
1338 const MachineInstr *inst = I->first->getInst();
1339 for(unsigned i=0; i < inst->getNumOperands(); ++i) {
1340 //get machine operand
1341 const MachineOperand &mOp = inst->getOperand(i);
1343 if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse()) {
1344 //If its in the value saved, we need to create a temp instruction and use that instead
1345 if(valuesToSave.count(mOp.getVRegValue())) {
1346 TmpInstruction *tmp = new TmpInstruction(mOp.getVRegValue());
1348 //Update the operand in the cloned instruction
1349 instClone->getOperand(i).setValueReg(tmp);
1351 //save this as our final phi
1352 finalPHIValue[mOp.getVRegValue()] = tmp;
1353 newValLocation[tmp] = machineBB;
1358 //Insert into machine basic block
1359 machineBB->push_back(instClone);
1362 //Otherwise we just check if we need to save a value or not
1364 //Insert into machine basic block
1365 machineBB->push_back(instClone);
1367 //Loop over Machine Operands
1368 const MachineInstr *inst = I->first->getInst();
1369 for(unsigned i=0; i < inst->getNumOperands(); ++i) {
1370 //get machine operand
1371 const MachineOperand &mOp = inst->getOperand(i);
1373 if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) {
1374 if(valuesToSave.count(mOp.getVRegValue())) {
1376 TmpInstruction *tmp = new TmpInstruction(mOp.getVRegValue());
1378 //Create new machine instr and put in MBB
1379 MachineInstr *saveValue = BuildMI(machineBB, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp);
1381 //Save for future cleanup
1382 kernelValue[mOp.getVRegValue()] = tmp;
1383 newValLocation[tmp] = machineBB;
1390 //Clean up by writing phis
1391 for(std::map<Value*, std::map<int, std::vector<Value*> > >::iterator V = newValues.begin(), E = newValues.end();
1394 DEBUG(std::cerr << "Writing phi for" << *(V->first));
1400 Instruction *lastPHI = 0;
1402 for(std::map<int, std::vector<Value*> >::iterator I = V->second.begin(), IE = V->second.end();
1405 int stage = I->first;
1407 DEBUG(std::cerr << "Stage: " << I->first << " vector size: " << I->second.size() << "\n");
1409 //Assert if this vector is ever greater then 1. This should not happen
1410 //FIXME: Get rid of vector if we convince ourselves this won't happn
1411 assert(I->second.size() == 1 && "Vector of values should be of size \n");
1413 //We must handle the first and last phi specially
1414 if(stage == maxStage) {
1415 //The resulting value must be the Value* we created earlier
1416 assert(lastPHI != 0 && "Last phi is NULL!\n");
1417 MachineInstr *saveValue = BuildMI(*machineBB, machineBB->begin(), V9::PHI, 3).addReg(lastPHI).addReg(I->second[0]).addRegDef(finalPHIValue[V->first]);
1418 I->second.push_back(finalPHIValue[V->first]);
1420 else if(stage == 0) {
1421 lastPHI = new TmpInstruction(I->second[0]);
1422 MachineInstr *saveValue = BuildMI(*machineBB, machineBB->begin(), V9::PHI, 3).addReg(kernelValue[V->first]).addReg(I->second[0]).addRegDef(lastPHI);
1423 I->second.push_back(lastPHI);
1424 newValLocation[lastPHI] = machineBB;
1427 Instruction *tmp = new TmpInstruction(I->second[0]);
1428 MachineInstr *saveValue = BuildMI(*machineBB, machineBB->begin(), V9::PHI, 3).addReg(lastPHI).addReg(I->second[0]).addRegDef(tmp);
1430 I->second.push_back(lastPHI);
1431 newValLocation[tmp] = machineBB;
1437 void ModuloSchedulingPass::removePHIs(const MachineBasicBlock *origBB, std::vector<MachineBasicBlock *> &prologues, std::vector<MachineBasicBlock *> &epilogues, MachineBasicBlock *kernelBB, std::map<Value*, MachineBasicBlock*> &newValLocation) {
1439 //Worklist to delete things
1440 std::vector<std::pair<MachineBasicBlock*, MachineBasicBlock::iterator> > worklist;
1442 const TargetInstrInfo *TMI = target.getInstrInfo();
1444 //Start with the kernel and for each phi insert a copy for the phi def and for each arg
1445 for(MachineBasicBlock::iterator I = kernelBB->begin(), E = kernelBB->end(); I != E; ++I) {
1446 //Get op code and check if its a phi
1447 MachineOpCode OC = I->getOpcode();
1448 if(TMI->isDummyPhiInstr(OC)) {
1449 Instruction *tmp = 0;
1450 for(unsigned i = 0; i < I->getNumOperands(); ++i) {
1452 const MachineOperand &mOp = I->getOperand(i);
1453 assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Should be a Value*\n");
1456 tmp = new TmpInstruction(mOp.getVRegValue());
1459 //Now for all our arguments we read, OR to the new TmpInstruction that we created
1461 DEBUG(std::cerr << "Use: " << mOp << "\n");
1462 //Place a copy at the end of its BB but before the branches
1463 assert(newValLocation.count(mOp.getVRegValue()) && "We must know where this value is located\n");
1464 //Reverse iterate to find the branches, we can safely assume no instructions have been
1465 //put in the nop positions
1466 for(MachineBasicBlock::iterator inst = --(newValLocation[mOp.getVRegValue()])->end(), endBB = (newValLocation[mOp.getVRegValue()])->begin(); inst != endBB; --inst) {
1467 MachineOpCode opc = inst->getOpcode();
1468 if(TMI->isBranch(opc) || TMI->isNop(opc))
1471 BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp);
1479 //Remove the phi and replace it with an OR
1480 DEBUG(std::cerr << "Def: " << mOp << "\n");
1481 BuildMI(*kernelBB, I, V9::ORr, 3).addReg(tmp).addImm(0).addRegDef(mOp.getVRegValue());
1482 worklist.push_back(std::make_pair(kernelBB, I));
1490 //Remove phis from epilogue
1491 for(std::vector<MachineBasicBlock*>::iterator MB = epilogues.begin(), ME = epilogues.end(); MB != ME; ++MB) {
1492 for(MachineBasicBlock::iterator I = (*MB)->begin(), E = (*MB)->end(); I != E; ++I) {
1493 //Get op code and check if its a phi
1494 MachineOpCode OC = I->getOpcode();
1495 if(TMI->isDummyPhiInstr(OC)) {
1496 Instruction *tmp = 0;
1497 for(unsigned i = 0; i < I->getNumOperands(); ++i) {
1499 const MachineOperand &mOp = I->getOperand(i);
1500 assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Should be a Value*\n");
1503 tmp = new TmpInstruction(mOp.getVRegValue());
1506 //Now for all our arguments we read, OR to the new TmpInstruction that we created
1508 DEBUG(std::cerr << "Use: " << mOp << "\n");
1509 //Place a copy at the end of its BB but before the branches
1510 assert(newValLocation.count(mOp.getVRegValue()) && "We must know where this value is located\n");
1511 //Reverse iterate to find the branches, we can safely assume no instructions have been
1512 //put in the nop positions
1513 for(MachineBasicBlock::iterator inst = --(newValLocation[mOp.getVRegValue()])->end(), endBB = (newValLocation[mOp.getVRegValue()])->begin(); inst != endBB; --inst) {
1514 MachineOpCode opc = inst->getOpcode();
1515 if(TMI->isBranch(opc) || TMI->isNop(opc))
1518 BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp);
1526 //Remove the phi and replace it with an OR
1527 DEBUG(std::cerr << "Def: " << mOp << "\n");
1528 BuildMI(**MB, I, V9::ORr, 3).addReg(tmp).addImm(0).addRegDef(mOp.getVRegValue());
1529 worklist.push_back(std::make_pair(*MB,I));
1538 for(std::vector<std::pair<MachineBasicBlock*, MachineBasicBlock::iterator> >::iterator I = worklist.begin(), E = worklist.end(); I != E; ++I) {
1539 I->first->erase(I->second);
1546 void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) {
1548 //First find the value *'s that we need to "save"
1549 std::map<const Value*, std::pair<const MSchedGraphNode*, int> > valuesToSave;
1551 //Loop over kernel and only look at instructions from a stage > 0
1552 //Look at its operands and save values *'s that are read
1553 for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) {
1556 //For this instruction, get the Value*'s that it reads and put them into the set.
1557 //Assert if there is an operand of another type that we need to save
1558 const MachineInstr *inst = I->first->getInst();
1559 for(unsigned i=0; i < inst->getNumOperands(); ++i) {
1560 //get machine operand
1561 const MachineOperand &mOp = inst->getOperand(i);
1563 if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse()) {
1564 //find the value in the map
1565 if (const Value* srcI = mOp.getVRegValue())
1566 valuesToSave[srcI] = std::make_pair(I->first, i);
1570 if(mOp.getType() != MachineOperand::MO_VirtualRegister && mOp.isUse()) {
1571 assert("Our assumption is wrong. We have another type of register that needs to be saved\n");
1577 //The new loop will consist of one or more prologues, the kernel, and one or more epilogues.
1579 //Map to keep track of old to new values
1580 std::map<Value*, std::map<int, std::vector<Value*> > > newValues;
1582 //Another map to keep track of what machine basic blocks these new value*s are in since
1583 //they have no llvm instruction equivalent
1584 std::map<Value*, MachineBasicBlock*> newValLocation;
1586 std::vector<MachineBasicBlock*> prologues;
1587 std::vector<BasicBlock*> llvm_prologues;
1591 writePrologues(prologues, BB, llvm_prologues, valuesToSave, newValues, newValLocation);
1593 BasicBlock *llvmKernelBB = new BasicBlock("Kernel", (Function*) (BB->getBasicBlock()->getParent()));
1594 MachineBasicBlock *machineKernelBB = new MachineBasicBlock(llvmKernelBB);
1596 writeKernel(llvmKernelBB, machineKernelBB, valuesToSave, newValues, newValLocation);
1597 (((MachineBasicBlock*)BB)->getParent())->getBasicBlockList().push_back(machineKernelBB);
1599 std::vector<MachineBasicBlock*> epilogues;
1600 std::vector<BasicBlock*> llvm_epilogues;
1603 writeEpilogues(epilogues, BB, llvm_epilogues, valuesToSave, newValues, newValLocation);
1606 const TargetInstrInfo *TMI = target.getInstrInfo();
1608 //Fix up machineBB and llvmBB branches
1609 for(unsigned I = 0; I < prologues.size(); ++I) {
1611 MachineInstr *branch = 0;
1613 //Find terminator since getFirstTerminator does not work!
1614 for(MachineBasicBlock::reverse_iterator mInst = prologues[I]->rbegin(), mInstEnd = prologues[I]->rend(); mInst != mInstEnd; ++mInst) {
1615 MachineOpCode OC = mInst->getOpcode();
1616 if(TMI->isBranch(OC)) {
1618 DEBUG(std::cerr << *mInst << "\n");
1626 for(unsigned opNum = 0; opNum < branch->getNumOperands(); ++opNum) {
1627 MachineOperand &mOp = branch->getOperand(opNum);
1628 if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1629 mOp.setValueReg(llvm_epilogues[(llvm_epilogues.size()-1-I)]);
1633 //Update llvm basic block with our new branch instr
1634 DEBUG(std::cerr << BB->getBasicBlock()->getTerminator() << "\n");
1635 const BranchInst *branchVal = dyn_cast<BranchInst>(BB->getBasicBlock()->getTerminator());
1636 TmpInstruction *tmp = new TmpInstruction(branchVal->getCondition());
1637 if(I == prologues.size()-1) {
1638 TerminatorInst *newBranch = new BranchInst(llvmKernelBB,
1639 llvm_epilogues[(llvm_epilogues.size()-1-I)],
1644 TerminatorInst *newBranch = new BranchInst(llvm_prologues[I+1],
1645 llvm_epilogues[(llvm_epilogues.size()-1-I)],
1649 assert(branch != 0 && "There must be a terminator for this machine basic block!\n");
1651 //Push nop onto end of machine basic block
1652 BuildMI(prologues[I], V9::NOP, 0);
1654 //Now since I don't trust fall throughs, add a unconditional branch to the next prologue
1655 if(I != prologues.size()-1)
1656 BuildMI(prologues[I], V9::BA, 1).addReg(llvm_prologues[I+1]);
1658 BuildMI(prologues[I], V9::BA, 1).addReg(llvmKernelBB);
1661 BuildMI(prologues[I], V9::NOP, 0);
1664 //Fix up kernel machine branches
1665 MachineInstr *branch = 0;
1666 for(MachineBasicBlock::reverse_iterator mInst = machineKernelBB->rbegin(), mInstEnd = machineKernelBB->rend(); mInst != mInstEnd; ++mInst) {
1667 MachineOpCode OC = mInst->getOpcode();
1668 if(TMI->isBranch(OC)) {
1670 DEBUG(std::cerr << *mInst << "\n");
1675 assert(branch != 0 && "There must be a terminator for the kernel machine basic block!\n");
1677 //Update kernel self loop branch
1678 for(unsigned opNum = 0; opNum < branch->getNumOperands(); ++opNum) {
1679 MachineOperand &mOp = branch->getOperand(opNum);
1681 if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1682 mOp.setValueReg(llvmKernelBB);
1686 //Update kernelLLVM branches
1687 const BranchInst *branchVal = dyn_cast<BranchInst>(BB->getBasicBlock()->getTerminator());
1688 TerminatorInst *newBranch = new BranchInst(llvmKernelBB,
1690 new TmpInstruction(branchVal->getCondition()),
1694 BuildMI(machineKernelBB, V9::NOP, 0);
1696 //Add unconditional branch to first epilogue
1697 BuildMI(machineKernelBB, V9::BA, 1).addReg(llvm_epilogues[0]);
1700 BuildMI(machineKernelBB, V9::NOP, 0);
1702 //Lastly add unconditional branches for the epilogues
1703 for(unsigned I = 0; I < epilogues.size(); ++I) {
1705 //Now since I don't trust fall throughs, add a unconditional branch to the next prologue
1706 if(I != epilogues.size()-1) {
1707 BuildMI(epilogues[I], V9::BA, 1).addReg(llvm_epilogues[I+1]);
1708 //Add unconditional branch to end of epilogue
1709 TerminatorInst *newBranch = new BranchInst(llvm_epilogues[I+1],
1714 MachineBasicBlock *origBlock = (MachineBasicBlock*) BB;
1715 for(MachineBasicBlock::reverse_iterator inst = origBlock->rbegin(), instEnd = origBlock->rend(); inst != instEnd; ++inst) {
1716 MachineOpCode OC = inst->getOpcode();
1717 if(TMI->isBranch(OC)) {
1719 DEBUG(std::cerr << *inst << "\n");
1724 for(unsigned opNum = 0; opNum < branch->getNumOperands(); ++opNum) {
1725 MachineOperand &mOp = branch->getOperand(opNum);
1727 if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1728 BuildMI(epilogues[I], V9::BA, 1).addReg(mOp.getVRegValue());
1735 //Update last epilogue exit branch
1736 BranchInst *branchVal = (BranchInst*) dyn_cast<BranchInst>(BB->getBasicBlock()->getTerminator());
1737 //Find where we are supposed to branch to
1738 BasicBlock *nextBlock = 0;
1739 for(unsigned j=0; j <branchVal->getNumSuccessors(); ++j) {
1740 if(branchVal->getSuccessor(j) != BB->getBasicBlock())
1741 nextBlock = branchVal->getSuccessor(j);
1743 TerminatorInst *newBranch = new BranchInst(nextBlock, llvm_epilogues[I]);
1746 BuildMI(epilogues[I], V9::NOP, 0);
1750 //FIX UP Machine BB entry!!
1751 //We are looking at the predecesor of our loop basic block and we want to change its ba instruction
1754 //Find all llvm basic blocks that branch to the loop entry and change to our first prologue.
1755 const BasicBlock *llvmBB = BB->getBasicBlock();
1757 for(pred_const_iterator P = pred_begin(llvmBB), PE = pred_end(llvmBB); P != PE; ++PE) {
1761 DEBUG(std::cerr << "Found our entry BB\n");
1762 //Get the Terminator instruction for this basic block and print it out
1763 DEBUG(std::cerr << *((*P)->getTerminator()) << "\n");
1764 //Update the terminator
1765 TerminatorInst *term = ((BasicBlock*)*P)->getTerminator();
1766 for(unsigned i=0; i < term->getNumSuccessors(); ++i) {
1767 if(term->getSuccessor(i) == llvmBB) {
1768 DEBUG(std::cerr << "Replacing successor bb\n");
1769 if(llvm_prologues.size() > 0) {
1770 term->setSuccessor(i, llvm_prologues[0]);
1771 //Also update its corresponding machine instruction
1772 MachineCodeForInstruction & tempMvec =
1773 MachineCodeForInstruction::get(term);
1774 for (unsigned j = 0; j < tempMvec.size(); j++) {
1775 MachineInstr *temp = tempMvec[j];
1776 MachineOpCode opc = temp->getOpcode();
1777 if(TMI->isBranch(opc)) {
1778 DEBUG(std::cerr << *temp << "\n");
1780 for(unsigned opNum = 0; opNum < temp->getNumOperands(); ++opNum) {
1781 MachineOperand &mOp = temp->getOperand(opNum);
1782 if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1783 mOp.setValueReg(llvm_prologues[0]);
1790 term->setSuccessor(i, llvmKernelBB);
1791 //Also update its corresponding machine instruction
1792 MachineCodeForInstruction & tempMvec =
1793 MachineCodeForInstruction::get(term);
1794 for (unsigned j = 0; j < tempMvec.size(); j++) {
1795 MachineInstr *temp = tempMvec[j];
1796 MachineOpCode opc = temp->getOpcode();
1797 if(TMI->isBranch(opc)) {
1798 DEBUG(std::cerr << *temp << "\n");
1800 for(unsigned opNum = 0; opNum < temp->getNumOperands(); ++opNum) {
1801 MachineOperand &mOp = temp->getOperand(opNum);
1802 if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) {
1803 mOp.setValueReg(llvmKernelBB);
1815 removePHIs(BB, prologues, epilogues, machineKernelBB, newValLocation);
1819 //Print out epilogues and prologue
1820 DEBUG(for(std::vector<MachineBasicBlock*>::iterator I = prologues.begin(), E = prologues.end();
1822 std::cerr << "PROLOGUE\n";
1823 (*I)->print(std::cerr);
1826 DEBUG(std::cerr << "KERNEL\n");
1827 DEBUG(machineKernelBB->print(std::cerr));
1829 DEBUG(for(std::vector<MachineBasicBlock*>::iterator I = epilogues.begin(), E = epilogues.end();
1831 std::cerr << "EPILOGUE\n";
1832 (*I)->print(std::cerr);
1836 DEBUG(std::cerr << "New Machine Function" << "\n");
1837 DEBUG(std::cerr << BB->getParent() << "\n");
1839 BB->getParent()->getBasicBlockList().erase(BB);