diff options
Diffstat (limited to 'lib/Target/SparcV9/ModuloScheduling')
7 files changed, 638 insertions, 638 deletions
diff --git a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp b/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp index db228b35c8..a4461de80b 100644 --- a/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp @@ -25,14 +25,14 @@ namespace llvm { /// Create ModuloSchedulingPass FunctionPass *createDependenceAnalyzer() { - return new DependenceAnalyzer(); + return new DependenceAnalyzer(); } } Statistic<> NoDeps("depanalyzer-nodeps", "Number of dependences eliminated"); -Statistic<> NumDeps("depanalyzer-deps", +Statistic<> NumDeps("depanalyzer-deps", "Number of dependences could not eliminate"); -Statistic<> AdvDeps("depanalyzer-advdeps", +Statistic<> AdvDeps("depanalyzer-advdeps", "Number of dependences using advanced techniques"); bool DependenceAnalyzer::runOnFunction(Function &F) { @@ -43,25 +43,25 @@ bool DependenceAnalyzer::runOnFunction(Function &F) { return false; } -static RegisterAnalysis<DependenceAnalyzer>X("depanalyzer", +static RegisterAnalysis<DependenceAnalyzer>X("depanalyzer", "Dependence Analyzer"); - + // - Get inter and intra dependences between loads and stores // -// Overview of Method: -// Step 1: Use alias analysis to determine dependencies if values are loop -// invariant -// Step 2: If pointers are not GEP, then there is a dependence. -// Step 3: Compare GEP base pointers with AA. If no alias, no dependence. -// If may alias, then add a dependence. If must alias, then analyze -// further (Step 4) +// Overview of Method: +// Step 1: Use alias analysis to determine dependencies if values are loop +// invariant +// Step 2: If pointers are not GEP, then there is a dependence. +// Step 3: Compare GEP base pointers with AA. If no alias, no dependence. +// If may alias, then add a dependence. If must alias, then analyze +// further (Step 4) // Step 4: do advanced analysis -void DependenceAnalyzer::AnalyzeDeps(Value *val, Value *val2, bool valLoad, - bool val2Load, - std::vector<Dependence> &deps, - BasicBlock *BB, +void DependenceAnalyzer::AnalyzeDeps(Value *val, Value *val2, bool valLoad, + bool val2Load, + std::vector<Dependence> &deps, + BasicBlock *BB, bool srcBeforeDest) { - + bool loopInvariant = true; //Check if both are instructions and prove not loop invariant if possible @@ -71,8 +71,8 @@ void DependenceAnalyzer::AnalyzeDeps(Value *val, Value *val2, bool valLoad, if(Instruction *val2Inst = dyn_cast<Instruction>(val2)) if(val2Inst->getParent() == BB) loopInvariant = false; - - + + //If Loop invariant, let AA decide if(loopInvariant) { if(AA->alias(val, (unsigned)TD->getTypeSize(val->getType()), @@ -84,7 +84,7 @@ void DependenceAnalyzer::AnalyzeDeps(Value *val, Value *val2, bool valLoad, ++NoDeps; return; } - + //Otherwise, continue with step 2 GetElementPtrInst *GP = dyn_cast<GetElementPtrInst>(val); @@ -120,7 +120,7 @@ void DependenceAnalyzer::AnalyzeDeps(Value *val, Value *val2, bool valLoad, // advancedDepAnalysis - Do advanced data dependence tests -void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1, +void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1, GetElementPtrInst *gp2, bool valLoad, bool val2Load, @@ -139,7 +139,7 @@ void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1, if(Constant *c2 = dyn_cast<Constant>(gp2->getOperand(1))) if(c1->isNullValue() && c2->isNullValue()) GPok = true; - + if(!GPok) { createDep(deps, valLoad, val2Load, srcBeforeDest); return; @@ -153,7 +153,7 @@ void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1, Gep1Idx = c1->getOperand(0); if(CastInst *c2 = dyn_cast<CastInst>(Gep2Idx)) Gep2Idx = c2->getOperand(0); - + //Get SCEV for each index into the area SCEVHandle SV1 = SE->getSCEV(Gep1Idx); SCEVHandle SV2 = SE->getSCEV(Gep2Idx); @@ -188,7 +188,7 @@ void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1, createDep(deps, valLoad, val2Load, srcBeforeDest); return; } - + if(B1->getValue()->getRawValue() != 1 || B2->getValue()->getRawValue() != 1) { createDep(deps, valLoad, val2Load, srcBeforeDest); return; @@ -214,7 +214,7 @@ void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1, ++NoDeps; return; } - + //Find constant index difference int diff = A1->getValue()->getRawValue() - A2->getValue()->getRawValue(); //std::cerr << diff << "\n"; @@ -223,14 +223,14 @@ void DependenceAnalyzer::advancedDepAnalysis(GetElementPtrInst *gp1, if(diff > 0) createDep(deps, valLoad, val2Load, srcBeforeDest, diff); - + //assert(diff > 0 && "Expected diff to be greater then 0"); } // Create dependences once its determined these two instructions // references the same memory -void DependenceAnalyzer::createDep(std::vector<Dependence> &deps, - bool valLoad, bool val2Load, +void DependenceAnalyzer::createDep(std::vector<Dependence> &deps, + bool valLoad, bool val2Load, bool srcBeforeDest, int diff) { //If the source instruction occurs after the destination instruction @@ -240,7 +240,7 @@ void DependenceAnalyzer::createDep(std::vector<Dependence> &deps, //If load/store pair if(valLoad && !val2Load) { - if(srcBeforeDest) + if(srcBeforeDest) //Anti Dep deps.push_back(Dependence(diff, Dependence::AntiDep)); else @@ -250,7 +250,7 @@ void DependenceAnalyzer::createDep(std::vector<Dependence> &deps, } //If store/load pair else if(!valLoad && val2Load) { - if(srcBeforeDest) + if(srcBeforeDest) //True Dep deps.push_back(Dependence(diff, Dependence::TrueDep)); else @@ -266,10 +266,10 @@ void DependenceAnalyzer::createDep(std::vector<Dependence> &deps, } - + //Get Dependence Info for a pair of Instructions -DependenceResult DependenceAnalyzer::getDependenceInfo(Instruction *inst1, - Instruction *inst2, +DependenceResult DependenceAnalyzer::getDependenceInfo(Instruction *inst1, + Instruction *inst2, bool srcBeforeDest) { std::vector<Dependence> deps; @@ -281,24 +281,24 @@ DependenceResult DependenceAnalyzer::getDependenceInfo(Instruction *inst1, return DependenceResult(deps); if(LoadInst *ldInst = dyn_cast<LoadInst>(inst1)) { - + if(StoreInst *stInst = dyn_cast<StoreInst>(inst2)) - AnalyzeDeps(ldInst->getOperand(0), stInst->getOperand(1), + AnalyzeDeps(ldInst->getOperand(0), stInst->getOperand(1), true, false, deps, ldInst->getParent(), srcBeforeDest); } else if(StoreInst *stInst = dyn_cast<StoreInst>(inst1)) { - + if(LoadInst *ldInst = dyn_cast<LoadInst>(inst2)) - AnalyzeDeps(stInst->getOperand(1), ldInst->getOperand(0), false, true, + AnalyzeDeps(stInst->getOperand(1), ldInst->getOperand(0), false, true, deps, ldInst->getParent(), srcBeforeDest); - + else if(StoreInst *stInst2 = dyn_cast<StoreInst>(inst2)) - AnalyzeDeps(stInst->getOperand(1), stInst2->getOperand(1), false, false, + AnalyzeDeps(stInst->getOperand(1), stInst2->getOperand(1), false, false, deps, stInst->getParent(), srcBeforeDest); } else assert(0 && "Expected a load or a store\n"); - + DependenceResult dr = DependenceResult(deps); return dr; } diff --git a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp index 3513d5c9d3..f690054508 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/MSSchedule.cpp @@ -21,7 +21,7 @@ using namespace llvm; //Check if all resources are free -bool resourcesFree(MSchedGraphNode*, int, +bool resourcesFree(MSchedGraphNode*, int, std::map<int, std::map<int, int> > &resourceNumPerCycle); //Returns a boolean indicating if the start cycle needs to be increased/decreased @@ -84,12 +84,12 @@ bool MSSchedule::resourceAvailable(int resourceNum, int cycle) { isFree = false; } } - + return isFree; } void MSSchedule::useResource(int resourceNum, int cycle) { - + //Get Map for this cycle if(resourceNumPerCycle.count(cycle)) { if(resourceNumPerCycle[cycle].count(resourceNum)) { @@ -105,7 +105,7 @@ void MSSchedule::useResource(int resourceNum, int cycle) { resourceUse[resourceNum] = 1; resourceNumPerCycle[cycle] = resourceUse; } - + } bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle, int II) { @@ -129,34 +129,34 @@ bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle, int II) { //Now check all cycles for conflicts for(int index = 0; index < (int) cyclesMayConflict.size(); ++index) { currentCycle = cyclesMayConflict[index]; - + //Get resource usage for this instruction InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode()); std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle; - + //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) { - + //Get Resource to check its availability int resourceNum = resources[i][j]; - + DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n"); - - success = resourceAvailable(resourceNum, currentCycle); - + + success = resourceAvailable(resourceNum, currentCycle); + if(!success) break; - + } - + if(!success) break; - + //Increase cycle currentCycle++; } - + if(!success) return false; } @@ -168,7 +168,7 @@ bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle, int II) { //Get resource usage for this instruction InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode()); std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle; - + //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) { @@ -195,7 +195,7 @@ bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches //Using the schedule, fold up into kernel and check resource conflicts as we go std::vector<std::pair<MSchedGraphNode*, int> > tempKernel; - + int stageNum = ((schedule.rbegin()->first-offset)+1)/ II; int maxSN = 0; @@ -212,7 +212,7 @@ bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches tempKernel.push_back(std::make_pair(*I, count)); maxSN = std::max(maxSN, count); - + } } ++count; @@ -286,7 +286,7 @@ bool MSSchedule::defPreviousStage(Value *def, int stage) { } } } - + assert(0 && "We should always have found the def in our kernel\n"); } diff --git a/lib/Target/SparcV9/ModuloScheduling/MSScheduleSB.cpp b/lib/Target/SparcV9/ModuloScheduling/MSScheduleSB.cpp index ef21b80104..d4e65e4ee0 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSScheduleSB.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/MSScheduleSB.cpp @@ -21,7 +21,7 @@ using namespace llvm; //Check if all resources are free -bool resourcesFree(MSchedGraphSBNode*, int, +bool resourcesFree(MSchedGraphSBNode*, int, std::map<int, std::map<int, int> > &resourceNumPerCycle); //Returns a boolean indicating if the start cycle needs to be increased/decreased @@ -84,12 +84,12 @@ bool MSScheduleSB::resourceAvailable(int resourceNum, int cycle) { isFree = false; } } - + return isFree; } void MSScheduleSB::useResource(int resourceNum, int cycle) { - + //Get Map for this cycle if(resourceNumPerCycle.count(cycle)) { if(resourceNumPerCycle[cycle].count(resourceNum)) { @@ -105,7 +105,7 @@ void MSScheduleSB::useResource(int resourceNum, int cycle) { resourceUse[resourceNum] = 1; resourceNumPerCycle[cycle] = resourceUse; } - + } bool MSScheduleSB::resourcesFree(MSchedGraphSBNode *node, int cycle, int II) { @@ -129,34 +129,34 @@ bool MSScheduleSB::resourcesFree(MSchedGraphSBNode *node, int cycle, int II) { //Now check all cycles for conflicts for(int index = 0; index < (int) cyclesMayConflict.size(); ++index) { currentCycle = cyclesMayConflict[index]; - + //Get resource usage for this instruction InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode()); std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle; - + //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) { - + //Get Resource to check its availability int resourceNum = resources[i][j]; - + DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n"); - - success = resourceAvailable(resourceNum, currentCycle); - + + success = resourceAvailable(resourceNum, currentCycle); + if(!success) break; - + } - + if(!success) break; - + //Increase cycle currentCycle++; } - + if(!success) return false; } @@ -168,7 +168,7 @@ bool MSScheduleSB::resourcesFree(MSchedGraphSBNode *node, int cycle, int II) { //Get resource usage for this instruction InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode()); std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle; - + //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) { @@ -195,7 +195,7 @@ bool MSScheduleSB::constructKernel(int II, std::vector<MSchedGraphSBNode*> &bran //Using the schedule, fold up into kernel and check resource conflicts as we go std::vector<std::pair<MSchedGraphSBNode*, int> > tempKernel; - + int stageNum = ((schedule.rbegin()->first-offset)+1)/ II; int maxSN = 0; @@ -212,7 +212,7 @@ bool MSScheduleSB::constructKernel(int II, std::vector<MSchedGraphSBNode*> &bran tempKernel.push_back(std::make_pair(*I, count)); maxSN = std::max(maxSN, count); - + } } ++count; @@ -293,7 +293,7 @@ bool MSScheduleSB::defPreviousStage(Value *def, int stage) { } } } - + assert(0 && "We should always have found the def in our kernel\n"); } diff --git a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp index 055080a40b..ec68a968e2 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp @@ -34,8 +34,8 @@ using namespace llvm; //MSchedGraphNode constructor MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst, MSchedGraph *graph, unsigned idx, - unsigned late, bool isBranch) - : Inst(inst), Parent(graph), index(idx), latency(late), + unsigned late, bool isBranch) + : Inst(inst), Parent(graph), index(idx), latency(late), isBranchInstr(isBranch) { //Add to the graph @@ -75,7 +75,7 @@ MSchedGraphEdge MSchedGraphNode::getInEdge(MSchedGraphNode *pred) { //Get the iteration difference for the edge from this node to its successor unsigned MSchedGraphNode::getIteDiff(MSchedGraphNode *succ) { - for(std::vector<MSchedGraphEdge>::iterator I = Successors.begin(), + for(std::vector<MSchedGraphEdge>::iterator I = Successors.begin(), E = Successors.end(); I != E; ++I) { if(I->getDest() == succ) @@ -89,7 +89,7 @@ unsigned MSchedGraphNode::getInEdgeNum(MSchedGraphNode *pred) { //Loop over all the successors of our predecessor //return the edge the corresponds to this in edge int count = 0; - for(MSchedGraphNode::succ_iterator I = pred->succ_begin(), + for(MSchedGraphNode::succ_iterator I = pred->succ_begin(), E = pred->succ_end(); I != E; ++I) { if(*I == this) @@ -110,7 +110,7 @@ bool MSchedGraphNode::isSuccessor(MSchedGraphNode *succ) { //Dtermine if pred is a predecessor of this node bool MSchedGraphNode::isPredecessor(MSchedGraphNode *pred) { - if(std::find( Predecessors.begin(), Predecessors.end(), + if(std::find( Predecessors.begin(), Predecessors.end(), pred) != Predecessors.end()) return true; else @@ -148,10 +148,10 @@ void MSchedGraph::deleteNode(MSchedGraphNode *node) { //we ignore instructions associated to the index variable since this //is a special case in Modulo Scheduling. We only want to deal with //the body of the loop. -MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, - const TargetMachine &targ, - std::map<const MachineInstr*, unsigned> &ignoreInstrs, - DependenceAnalyzer &DA, +MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, + const TargetMachine &targ, + std::map<const MachineInstr*, unsigned> &ignoreInstrs, + DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm) : Target(targ) { @@ -159,7 +159,7 @@ MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, assert(bb != NULL && "Basic Block is null"); BBs.push_back(bb); - + //Create nodes and edges for this BB buildNodesAndEdges(ignoreInstrs, DA, machineTollvm); @@ -171,16 +171,16 @@ MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, //we ignore instructions associated to the index variable since this //is a special case in Modulo Scheduling. We only want to deal with //the body of the loop. -MSchedGraph::MSchedGraph(std::vector<const MachineBasicBlock*> &bbs, - const TargetMachine &targ, - std::map<const MachineInstr*, unsigned> &ignoreInstrs, - DependenceAnalyzer &DA, +MSchedGraph::MSchedGraph(std::vector<const MachineBasicBlock*> &bbs, + const TargetMachine &targ, + std::map<const MachineInstr*, unsigned> &ignoreInstrs, + DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm) : BBs(bbs), Target(targ) { //Make sure there is at least one BB and it is not null, assert(((bbs.size() >= 1) && bbs[1] != NULL) && "Basic Block is null"); - + //Create nodes and edges for this BB buildNodesAndEdges(ignoreInstrs, DA, machineTollvm); @@ -190,15 +190,15 @@ MSchedGraph::MSchedGraph(std::vector<const MachineBasicBlock*> &bbs, //Copies the graph and keeps a map from old to new nodes -MSchedGraph::MSchedGraph(const MSchedGraph &G, - std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes) +MSchedGraph::MSchedGraph(const MSchedGraph &G, + std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes) : Target(G.Target) { BBs = G.BBs; std::map<MSchedGraphNode*, MSchedGraphNode*> oldToNew; //Copy all nodes - for(MSchedGraph::const_iterator N = G.GraphMap.begin(), + for(MSchedGraph::const_iterator N = G.GraphMap.begin(), NE = G.GraphMap.end(); N != NE; ++N) { MSchedGraphNode *newNode = new MSchedGraphNode(*(N->second)); @@ -208,7 +208,7 @@ MSchedGraph::MSchedGraph(const MSchedGraph &G, } //Loop over nodes and update edges to point to new nodes - for(MSchedGraph::iterator N = GraphMap.begin(), NE = GraphMap.end(); + for(MSchedGraph::iterator N = GraphMap.begin(), NE = GraphMap.end(); N != NE; ++N) { //Get the node we are dealing with @@ -231,16 +231,16 @@ MSchedGraph::MSchedGraph(const MSchedGraph &G, //Deconstructor, deletes all nodes in the graph MSchedGraph::~MSchedGraph () { - for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); + for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I) delete I->second; } //Print out graph void MSchedGraph::print(std::ostream &os) const { - for(MSchedGraph::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); + for(MSchedGraph::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); N != NE; ++N) { - + //Get the node we are dealing with MSchedGraphNode *node = &*(N->second); @@ -261,9 +261,9 @@ void MSchedGraph::print(std::ostream &os) const { int MSchedGraph::totalDelay() { int sum = 0; - for(MSchedGraph::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); + for(MSchedGraph::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); N != NE; ++N) { - + //Get the node we are dealing with MSchedGraphNode *node = &*(N->second); sum += node->getLatency(); @@ -271,7 +271,7 @@ int MSchedGraph::totalDelay() { return sum; } //Experimental code to add edges from the branch to all nodes dependent upon it. -void hasPath(MSchedGraphNode *node, std::set<MSchedGraphNode*> &visited, +void hasPath(MSchedGraphNode *node, std::set<MSchedGraphNode*> &visited, std::set<MSchedGraphNode*> &branches, MSchedGraphNode *startNode, std::set<std::pair<MSchedGraphNode*,MSchedGraphNode*> > &newEdges ) { @@ -298,7 +298,7 @@ void MSchedGraph::addBranchEdges() { std::set<MSchedGraphNode*> branches; std::set<MSchedGraphNode*> nodes; - for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); + for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I) { if(I->second->isBranch()) if(I->second->hasPredecessors()) @@ -308,7 +308,7 @@ void MSchedGraph::addBranchEdges() { //See if there is a path first instruction to the branches, if so, add an //iteration dependence between that node and the branch std::set<std::pair<MSchedGraphNode*, MSchedGraphNode*> > newEdges; - for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); + for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I) { std::set<MSchedGraphNode*> visited; hasPath((I->second), visited, branches, (I->second), newEdges); @@ -347,7 +347,7 @@ void MSchedGraph::addBranchEdges() { void MSchedGraph::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ignoreInstrs, DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm) { - + //Get Machine target information for calculating latency const TargetInstrInfo *MTI = Target.getInstrInfo(); @@ -360,28 +360,28 @@ void MSchedGraph::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ig std::vector<const MachineInstr*> phiInstrs; unsigned index = 0; - for(std::vector<const MachineBasicBlock*>::iterator B = BBs.begin(), + for(std::vector<const MachineBasicBlock*>::iterator B = BBs.begin(), BE = BBs.end(); B != BE; ++B) { - + const MachineBasicBlock *BB = *B; //Loop over instructions in MBB and add nodes and edges - for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); + for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); MI != e; ++MI) { - + //Ignore indvar instructions if(ignoreInstrs.count(MI)) { ++index; continue; } - + //Get each instruction of machine basic block, get the delay //using the op code, create a new node for it, and add to the //graph. - + MachineOpCode opCode = MI->getOpcode(); int delay; - + #if 0 // FIXME: LOOK INTO THIS //Check if subsequent instructions can be issued before //the result is ready, if so use min delay. @@ -391,78 +391,78 @@ void MSchedGraph::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ig #endif //Get delay delay = MTI->maxLatency(opCode); - + //Create new node for this machine instruction and add to the graph. //Create only if not a nop if(MTI->isNop(opCode)) continue; - + //Sparc BE does not use PHI opcode, so assert on this case assert(opCode != TargetInstrInfo::PHI && "Did not expect PHI opcode"); - + bool isBranch = false; - + //We want to flag the branch node to treat it special if(MTI->isBranch(opCode)) isBranch = true; - + //Node is created and added to the graph automatically - MSchedGraphNode *node = new MSchedGraphNode(MI, this, index, delay, + MSchedGraphNode *node = new MSchedGraphNode(MI, this, index, delay, isBranch); - + DEBUG(std::cerr << "Created Node: " << *node << "\n"); - + //Check OpCode to keep track of memory operations to add memory //dependencies later. if(MTI->isLoad(opCode) || MTI->isStore(opCode)) memInstructions.push_back(node); - + //Loop over all operands, and put them into the register number to //graph node map for determining dependencies //If an operands is a use/def, we have an anti dependence to itself for(unsigned i=0; i < MI->getNumOperands(); ++i) { //Get Operand const MachineOperand &mOp = MI->getOperand(i); - + //Check if it has an allocated register if(mOp.hasAllocatedReg()) { int regNum = mOp.getReg(); - + if(regNum != SparcV9::g0) { //Put into our map regNumtoNodeMap[regNum].push_back(std::make_pair(i, node)); } continue; } - - + + //Add virtual registers dependencies //Check if any exist in the value map already and create dependencies //between them. - if(mOp.getType() == MachineOperand::MO_VirtualRegister + if(mOp.getType() == MachineOperand::MO_VirtualRegister || mOp.getType() == MachineOperand::MO_CCRegister) { - + //Make sure virtual register value is not null assert((mOp.getVRegValue() != NULL) && "Null value is defined"); - + //Check if this is a read operation in a phi node, if so DO NOT PROCESS if(mOp.isUse() && (opCode == TargetInstrInfo::PHI)) { DEBUG(std::cerr << "Read Operation in a PHI node\n"); continue; } - + if (const Value* srcI = mOp.getVRegValue()) { - + //Find value in the map std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V = valuetoNodeMap.find(srcI); - + //If there is something in the map already, add edges from //those instructions //to this one we are processing if(V != valuetoNodeMap.end()) { addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs); - + //Add to value map V->second.push_back(std::make_pair(i,node)); } @@ -475,11 +475,11 @@ void MSchedGraph::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ig } ++index; } - + //Loop over LLVM BB, examine phi instructions, and add them to our //phiInstr list to process const BasicBlock *llvm_bb = BB->getBasicBlock(); - for(BasicBlock::const_iterator I = llvm_bb->begin(), E = llvm_bb->end(); + for(BasicBlock::const_iterator I = llvm_bb->begin(), E = llvm_bb->end(); I != E; ++I) { if(const PHINode *PN = dyn_cast<PHINode>(I)) { MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(PN); @@ -490,46 +490,46 @@ void MSchedGraph::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ig } } } - + } - + addMemEdges(memInstructions, DA, machineTollvm); addMachRegEdges(regNumtoNodeMap); - + //Finally deal with PHI Nodes and Value* - for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), + for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), E = phiInstrs.end(); I != E; ++I) { - + //Get Node for this instruction std::map<const MachineInstr*, MSchedGraphNode*>::iterator X; X = find(*I); - + if(X == GraphMap.end()) continue; - + MSchedGraphNode *node = X->second; - + DEBUG(std::cerr << "Adding ite diff edges for node: " << *node << "\n"); - + //Loop over operands for this instruction and add value edges for(unsigned i=0; i < (*I)->getNumOperands(); ++i) { //Get Operand const MachineOperand &mOp = (*I)->getOperand(i); - if((mOp.getType() == MachineOperand::MO_VirtualRegister + if((mOp.getType() == MachineOperand::MO_VirtualRegister || mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) { - + //find the value in the map if (const Value* srcI = mOp.getVRegValue()) { - + //Find value in the map std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V = valuetoNodeMap.find(srcI); - + //If there is something in the map already, add edges from //those instructions //to this one we are processing if(V != valuetoNodeMap.end()) { - addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), + addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs, 1); } } @@ -582,7 +582,7 @@ void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& //Loop over all machine registers in the map, and add dependencies //between the instructions that use it typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap; - for(regNodeMap::iterator I = regNumtoNodeMap.begin(); + for(regNodeMap::iterator I = regNumtoNodeMap.begin(); I != regNumtoNodeMap.end(); ++I) { //Get the register number int regNum = (*I).first; @@ -609,33 +609,33 @@ void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& //Look at all instructions after this in execution order for(unsigned j=i+1; j < Nodes.size(); ++j) { - + //Sink node is a write if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { //Src only uses the register (read) if(srcIsUse) - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::AntiDep); - + else if(srcIsUseandDef) { - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::AntiDep); - - srcNode->addOutEdge(Nodes[j].second, + + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::OutputDep); } else - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::OutputDep); } //Dest node is a read else { if(!srcIsUse || srcIsUseandDef) - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::TrueDep); } @@ -649,31 +649,31 @@ void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { //Src only uses the register (read) if(srcIsUse) - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::AntiDep, 1); else if(srcIsUseandDef) { - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::AntiDep, 1); - - srcNode->addOutEdge(Nodes[j].second, + + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::OutputDep, 1); } else - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::OutputDep, 1); } //Dest node is a read else { if(!srcIsUse || srcIsUseandDef) - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister, MSchedGraphEdge::TrueDep,1 ); } - + } @@ -685,8 +685,8 @@ void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& //Add edges between all loads and stores //Can be less strict with alias analysis and data dependence analysis. -void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst, - DependenceAnalyzer &DA, +void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst, + DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm) { //Get Target machine instruction info @@ -700,7 +700,7 @@ void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst, //Get the machine opCode to determine type of memory instruction MachineOpCode srcNodeOpCode = srcInst->getOpcode(); - + //All instructions after this one in execution order have an //iteration delay of 0 for(unsigned destIndex = 0; destIndex < memInst.size(); ++destIndex) { @@ -713,19 +713,19 @@ void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst, DEBUG(std::cerr << "MInst1: " << *srcInst << "\n"); DEBUG(std::cerr << "MInst2: " << *destInst << "\n"); - + //Assuming instructions without corresponding llvm instructions //are from constant pools. if (!machineTollvm.count(srcInst) || !machineTollvm.count(destInst)) continue; - + bool useDepAnalyzer = true; //Some machine loads and stores are generated by casts, so be //conservative and always add deps Instruction *srcLLVM = machineTollvm[srcInst]; Instruction *destLLVM = machineTollvm[destInst]; - if(!isa<LoadInst>(srcLLVM) + if(!isa<LoadInst>(srcLLVM) && !isa<StoreInst>(srcLLVM)) { if(isa<BinaryOperator>(srcLLVM)) { if(isa<ConstantFP>(srcLLVM->getOperand(0)) || isa<ConstantFP>(srcLLVM->getOperand(1))) @@ -733,7 +733,7 @@ void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst, } useDepAnalyzer = false; } - if(!isa<LoadInst>(destLLVM) + if(!isa<LoadInst>(destLLVM) && !isa<StoreInst>(destLLVM)) { if(isa<BinaryOperator>(destLLVM)) { if(isa<ConstantFP>(destLLVM->getOperand(0)) || isa<ConstantFP>(destLLVM->getOperand(1))) @@ -748,29 +748,29 @@ void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst, if(destIndex < srcIndex) srcBeforeDest = false; - DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst], - machineTollvm[destInst], + DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst], + machineTollvm[destInst], srcBeforeDest); - - for(std::vector<Dependence>::iterator d = dr.dependences.begin(), + + for(std::vector<Dependence>::iterator d = dr.dependences.begin(), de = dr.dependences.end(); d != de; ++d) { //Add edge from load to store - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, d->getDepType(), d->getIteDiff()); - + } } //Otherwise, we can not do any further analysis and must make a dependence else { - + //Get the machine opCode to determine type of memory instruction MachineOpCode destNodeOpCode = destInst->getOpcode(); //Get the Value* that we are reading from the load, always the first op const MachineOperand &mOp = srcInst->getOperand(0); const MachineOperand &mOp2 = destInst->getOperand(0); - + if(mOp.hasAllocatedReg()) if(mOp.getReg() == SparcV9::g0) continue; @@ -783,19 +783,19 @@ void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst, if(TMI->isLoad(srcNodeOpCode)) { if(TMI->isStore(destNodeOpCode)) - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, MSchedGraphEdge::AntiDep, 0); } else if(TMI->isStore(srcNodeOpCode)) { if(TMI->isStore(destNodeOpCode)) - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, MSchedGraphEdge::OutputDep, 0); else - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphEdge::MemoryDep, MSchedGraphEdge::TrueDep, 0); } } diff --git a/lib/Target/SparcV9/ModuloScheduling/MSchedGraphSB.cpp b/lib/Target/SparcV9/ModuloScheduling/MSchedGraphSB.cpp index f7b2ce0589..0d3d720ea5 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSchedGraphSB.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/MSchedGraphSB.cpp @@ -36,8 +36,8 @@ using namespace llvm; //MSchedGraphSBNode constructor MSchedGraphSBNode::MSchedGraphSBNode(const MachineInstr* inst, MSchedGraphSB *graph, unsigned idx, - unsigned late, bool isBranch) - : Inst(inst), Parent(graph), index(idx), latency(late), + unsigned late, bool isBranch) + : Inst(inst), Parent(graph), index(idx), latency(late), isBranchInstr(isBranch) { //Add to the graph @@ -50,7 +50,7 @@ MSchedGraphSBNode::MSchedGraphSBNode(const MachineInstr* inst, MSchedGraphSB *graph, unsigned idx, unsigned late, bool isPNode) : Inst(inst), otherInstrs(other), Parent(graph), index(idx), latency(late), isPredicateNode(isPNode) { - + isBranchInstr = false; @@ -94,7 +94,7 @@ MSchedGraphSBEdge MSchedGraphSBNode::getInEdge(MSchedGraphSBNode *pred) { //Get the iteration difference for the edge from this node to its successor unsigned MSchedGraphSBNode::getIteDiff(MSchedGraphSBNode *succ) { - for(std::vector<MSchedGraphSBEdge>::iterator I = Successors.begin(), + for(std::vector<MSchedGraphSBEdge>::iterator I = Successors.begin(), E = Successors.end(); I != E; ++I) { if(I->getDest() == succ) @@ -108,7 +108,7 @@ unsigned MSchedGraphSBNode::getInEdgeNum(MSchedGraphSBNode *pred) { //Loop over all the successors of our predecessor //return the edge the corresponds to this in edge int count = 0; - for(MSchedGraphSBNode::succ_iterator I = pred->succ_begin(), + for(MSchedGraphSBNode::succ_iterator I = pred->succ_begin(), E = pred->succ_end(); I != E; ++I) { if(*I == this) @@ -129,7 +129,7 @@ bool MSchedGraphSBNode::isSuccessor(MSchedGraphSBNode *succ) { //Dtermine if pred is a predecessor of this node bool MSchedGraphSBNode::isPredecessor(MSchedGraphSBNode *pred) { - if(std::find( Predecessors.begin(), Predecessors.end(), + if(std::find( Predecessors.begin(), Predecessors.end(), pred) != Predecessors.end()) return true; else @@ -167,45 +167,45 @@ void MSchedGraphSB::deleteNode(MSchedGraphSBNode *node) { //we ignore instructions associated to the index variable since this //is a special case in Modulo Scheduling. We only want to deal with //the body of the loop. -MSchedGraphSB::MSchedGraphSB(std::vector<const MachineBasicBlock*> &bbs, - const TargetMachine &targ, - std::map<const MachineInstr*, unsigned> &ignoreInstrs, - DependenceAnalyzer &DA, +MSchedGraphSB::MSchedGraphSB(std::vector<const MachineBasicBlock*> &bbs, + const TargetMachine &targ, + std::map<const MachineInstr*, unsigned> &ignoreInstrs, + DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm) : BBs(bbs), Target(targ) { //Make sure there is at least one BB and it is not null, assert(((bbs.size() >= 1) && bbs[1] != NULL) && "Basic Block is null"); - + std::map<MSchedGraphSBNode*, std::set<MachineInstr*> > liveOutsideTrace; std::set<const BasicBlock*> llvmBBs; - for(std::vector<const MachineBasicBlock*>::iterator MBB = bbs.begin(), ME = bbs.end()-1; + for(std::vector<const MachineBasicBlock*>::iterator MBB = bbs.begin(), ME = bbs.end()-1; MBB != ME; ++MBB) llvmBBs.insert((*MBB)->getBasicBlock()); //create predicate nodes DEBUG(std::cerr << "Create predicate nodes\n"); - for(std::vector<const MachineBasicBlock*>::iterator MBB = bbs.begin(), ME = bbs.end()-1; + for(std::vector<const MachineBasicBlock*>::iterator MBB = bbs.begin(), ME = bbs.end()-1; MBB != ME; ++MBB) { //Get LLVM basic block BasicBlock *BB = (BasicBlock*) (*MBB)->getBasicBlock(); - + //Get Terminator BranchInst *b = dyn_cast<BranchInst>(BB->getTerminator()); std::vector<const MachineInstr*> otherInstrs; MachineInstr *instr = 0; - + //Get the condition for the branch (we already checked if it was conditional) if(b->isConditional()) { Value *cond = b->getCondition(); - + DEBUG(std::cerr << "Condition: " << *cond << "\n"); - + assert(cond && "Condition must not be null!"); - + if(Instruction *I = dyn_cast<Instruction>(cond)) { MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(I); if(tempMvec.size() > 0) { @@ -217,7 +217,7 @@ MSchedGraphSB::MSchedGraphSB(std::vector<const MachineBasicBlock*> &bbs, //Get Machine target information for calculating latency const TargetInstrInfo *MTI = Target.getInstrInfo(); - + MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(b); int offset = tempMvec.size(); for (unsigned j = 0; j < tempMvec.size(); j++) { @@ -234,10 +234,10 @@ MSchedGraphSB::MSchedGraphSB(std::vector<const MachineBasicBlock*> &bbs, otherInstrs.push_back(mi); } } - + //Node is created and added to the graph automatically MSchedGraphSBNode *node = new MSchedGraphSBNode(instr, otherInstrs, this, (*MBB)->size()-offset-1, 3, true); - + DEBUG(std::cerr << "Created Node: " << *node << "\n"); //Now loop over all instructions and see if their def is live outside the trace @@ -264,7 +264,7 @@ MSchedGraphSB::MSchedGraphSB(std::vector<const MachineBasicBlock*> &bbs, } } - + } //Create nodes and edges for this BB @@ -274,15 +274,15 @@ MSchedGraphSB::MSchedGraphSB(std::vector<const MachineBasicBlock*> &bbs, //Copies the graph and keeps a map from old to new nodes -MSchedGraphSB::MSchedGraphSB(const MSchedGraphSB &G, - std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes) +MSchedGraphSB::MSchedGraphSB(const MSchedGraphSB &G, + std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes) : Target(G.Target) { BBs = G.BBs; std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> oldToNew; //Copy all nodes - for(MSchedGraphSB::const_iterator N = G.GraphMap.begin(), + for(MSchedGraphSB::const_iterator N = G.GraphMap.begin(), NE = G.GraphMap.end(); N != NE; ++N) { MSchedGraphSBNode *newNode = new MSchedGraphSBNode(*(N->second)); @@ -292,7 +292,7 @@ MSchedGraphSB::MSchedGraphSB(const MSchedGraphSB &G, } //Loop over nodes and update edges to point to new nodes - for(MSchedGraphSB::iterator N = GraphMap.begin(), NE = GraphMap.end(); + for(MSchedGraphSB::iterator N = GraphMap.begin(), NE = GraphMap.end(); N != NE; ++N) { //Get the node we are dealing with @@ -315,16 +315,16 @@ MSchedGraphSB::MSchedGraphSB(const MSchedGraphSB &G, //Deconstructor, deletes all nodes in the graph MSchedGraphSB::~MSchedGraphSB () { - for(MSchedGraphSB::iterator I = GraphMap.begin(), E = GraphMap.end(); + for(MSchedGraphSB::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I) delete I->second; } //Print out graph void MSchedGraphSB::print(std::ostream &os) const { - for(MSchedGraphSB::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); + for(MSchedGraphSB::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); N != NE; ++N) { - + //Get the node we are dealing with MSchedGraphSBNode *node = &*(N->second); @@ -345,9 +345,9 @@ void MSchedGraphSB::print(std::ostream &os) const { int MSchedGraphSB::totalDelay() { int sum = 0; - for(MSchedGraphSB::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); + for(MSchedGraphSB::const_iterator N = GraphMap.begin(), NE = GraphMap.end(); N != NE; ++N) { - + //Get the node we are dealing with MSchedGraphSBNode *node = &*(N->second); sum += node->getLatency(); @@ -357,20 +357,20 @@ int MSchedGraphSB::totalDelay() { bool MSchedGraphSB::instrCauseException(MachineOpCode opCode) { //Check for integer divide - if(opCode == V9::SDIVXr || opCode == V9::SDIVXi + if(opCode == V9::SDIVXr || opCode == V9::SDIVXi || opCode == V9::UDIVXr || opCode == V9::UDIVXi) return true; - + //Check for loads or stores const TargetInstrInfo *MTI = Target.getInstrInfo(); - //if( MTI->isLoad(opCode) || + //if( MTI->isLoad(opCode) || if(MTI->isStore(opCode)) return true; //Check for any floating point operation const TargetSchedInfo *msi = Target.getSchedInfo(); InstrSchedClass sc = msi->getSchedClass(opCode); - + //FIXME: Should check for floating point instructions! //if(sc == SPARC_FGA || sc == SPARC_FGM) //return true; @@ -384,7 +384,7 @@ void MSchedGraphSB::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> & DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm, std::map<MSchedGraphSBNode*, std::set<MachineInstr*> > &liveOutsideTrace) { - + //Get Machine target information for calculating latency const TargetInstrInfo *MTI = Target.getInstrInfo(); @@ -398,48 +398,48 @@ void MSchedGraphSB::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> & unsigned index = 0; MSchedGraphSBNode *lastPred = 0; - - for(std::vector<const MachineBasicBlock*>::iterator B = BBs.begin(), + + for(std::vector<const MachineBasicBlock*>::iterator B = BBs.begin(), BE = BBs.end(); B != BE; ++B) { - + const MachineBasicBlock *BB = *B; //Loop over instructions in MBB and add nodes and edges - for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); + for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); MI != e; ++MI) { - + //Ignore indvar instructions if(ignoreInstrs.count(MI)) { ++index; continue; } - + //Get each instruction of machine basic block, get the delay //using the op code, create a new node for it, and add to the //graph. - + MachineOpCode opCode = MI->getOpcode(); int delay; - + //Get delay delay = MTI->maxLatency(opCode); - + //Create new node for this machine instruction and add to the graph. //Create only if not a nop if(MTI->isNop(opCode)) continue; - + //Sparc BE does not use PHI opcode, so assert on this case assert(opCode != TargetInstrInfo::PHI && "Did not expect PHI opcode"); - + bool isBranch = false; //Skip branches if(MTI->isBranch(opCode)) continue; - + //Node is created and added to the graph automatically MSchedGraphSBNode *node = 0; if(!GraphMap.count(MI)){ @@ -453,7 +453,7 @@ void MSchedGraphSB::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> & if(lastPred) { lastPred->addOutEdge(node, MSchedGraphSBEdge::PredDep, MSchedGraphSBEdge::NonDataDep, 0); - + if(liveOutsideTrace.count(lastPred)) { for(std::set<MachineInstr*>::iterator L = liveOutsideTrace[lastPred].begin(), LE = liveOutsideTrace[lastPred].end(); L != LE; ++L) lastPred->addOutEdge(GraphMap[*L], MSchedGraphSBEdge::PredDep, @@ -461,7 +461,7 @@ void MSchedGraphSB::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> & } } - + lastPred = node; } } @@ -476,59 +476,59 @@ void MSchedGraphSB::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> & MSchedGraphSBEdge::NonDataDep, 0); } } - + //Check OpCode to keep track of memory operations to add memory //dependencies later. if(MTI->isLoad(opCode) || MTI->isStore(opCode)) memInstructions.push_back(node); - + //Loop over all operands, and put them into the register number to //graph node map for determining dependencies //If an operands is a use/def, we have an anti dependence to itself for(unsigned i=0; i < MI->getNumOperands(); ++i) { //Get Operand const MachineOperand &mOp = MI->getOperand(i); - + //Check if it has an allocated register if(mOp.hasAllocatedReg()) { int regNum = mOp.getReg(); - + if(regNum != SparcV9::g0) { //Put into our map regNumtoNodeMap[regNum].push_back(std::make_pair(i, node)); } continue; } - - + + //Add virtual registers dependencies //Check if any exist in the value map already and create dependencies //between them. - if(mOp.getType() == MachineOperand::MO_VirtualRegister + if(mOp.getType() == MachineOperand::MO_VirtualRegister || mOp.getType() == MachineOperand::MO_CCRegister) { - + //Make sure virtual register value is not null assert((mOp.getVRegValue() != NULL) && "Null value is defined"); - + //Check if this is a read operation in a phi node, if so DO NOT PROCESS if(mOp.isUse() && (opCode == TargetInstrInfo::PHI)) { DEBUG(std::cerr << "Read Operation in a PHI node\n"); continue; } - + if (const Value* srcI = mOp.getVRegValue()) { - + //Find value in the map std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V = valuetoNodeMap.find(srcI); - + //If there is something in the map already, add edges from //those instructions //to this one we are processing if(V != valuetoNodeMap.end()) { addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs); - + //Add to value map V->second.push_back(std::make_pair(i,node)); } @@ -541,11 +541,11 @@ void MSchedGraphSB::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> & } ++index; } - + //Loop over LLVM BB, examine phi instructions, and add them to our //phiInstr list to process const BasicBlock *llvm_bb = BB->getBasicBlock(); - for(BasicBlock::const_iterator I = llvm_bb->begin(), E = llvm_bb->end(); + for(BasicBlock::const_iterator I = llvm_bb->begin(), E = llvm_bb->end(); I != E; ++I) { if(const PHINode *PN = dyn_cast<PHINode>(I)) { MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(PN); @@ -556,46 +556,46 @@ void MSchedGraphSB::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> & } } } - + } - + addMemEdges(memInstructions, DA, machineTollvm); addMachRegEdges(regNumtoNodeMap); - + //Finally deal with PHI Nodes and Value* - for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), + for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), E = phiInstrs.end(); I != E; ++I) { - + //Get Node for this instruction std::map<const MachineInstr*, MSchedGraphSBNode*>::iterator X; X = find(*I); - + if(X == GraphMap.end()) continue; - + MSchedGraphSBNode *node = X->second; - + DEBUG(std::cerr << "Adding ite diff edges for node: " << *node << "\n"); - + //Loop over operands for this instruction and add value edges for(unsigned i=0; i < (*I)->getNumOperands(); ++i) { //Get Operand const MachineOperand &mOp = (*I)->getOperand(i); - if((mOp.getType() == MachineOperand::MO_VirtualRegister + if((mOp.getType() == MachineOperand::MO_VirtualRegister || mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) { - + //find the value in the map if (const Value* srcI = mOp.getVRegValue()) { - + //Find value in the map std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V = valuetoNodeMap.find(srcI); - + //If there is something in the map already, add edges from //those instructions //to this one we are processing if(V != valuetoNodeMap.end()) { - addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), + addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs, 1); } } @@ -648,7 +648,7 @@ void MSchedGraphSB::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> > //Loop over all machine registers in the map, and add dependencies //between the instructions that use it typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap; - for(regNodeMap::iterator I = regNumtoNodeMap.begin(); + for(regNodeMap::iterator I = regNumtoNodeMap.begin(); I != regNumtoNodeMap.end(); ++I) { //Get the register number int regNum = (*I).first; @@ -675,33 +675,33 @@ void MSchedGraphSB::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> > //Look at all instructions after this in execution order for(unsigned j=i+1; j < Nodes.size(); ++j) { - + //Sink node is a write if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { //Src only uses the register (read) if(srcIsUse) - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::AntiDep); - + else if(srcIsUseandDef) { - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::AntiDep); - - srcNode->addOutEdge(Nodes[j].second, + + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::OutputDep); } else - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::OutputDep); } //Dest node is a read else { if(!srcIsUse || srcIsUseandDef) - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::TrueDep); } @@ -715,31 +715,31 @@ void MSchedGraphSB::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> > if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) { //Src only uses the register (read) if(srcIsUse) - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::AntiDep, 1); else if(srcIsUseandDef) { - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::AntiDep, 1); - - srcNode->addOutEdge(Nodes[j].second, + + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::OutputDep, 1); } else - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::OutputDep, 1); } //Dest node is a read else { if(!srcIsUse || srcIsUseandDef) - srcNode->addOutEdge(Nodes[j].second, + srcNode->addOutEdge(Nodes[j].second, MSchedGraphSBEdge::MachineRegister, MSchedGraphSBEdge::TrueDep,1 ); } - + } @@ -751,8 +751,8 @@ void MSchedGraphSB::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> > //Add edges between all loads and stores //Can be less strict with alias analysis and data dependence analysis. -void MSchedGraphSB::addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst, - DependenceAnalyzer &DA, +void MSchedGraphSB::addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst, + DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm) { //Get Target machine instruction info @@ -766,7 +766,7 @@ void MSchedGraphSB::addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst, //Get the machine opCode to determine type of memory instruction MachineOpCode srcNodeOpCode = srcInst->getOpcode(); - + //All instructions after this one in execution order have an //iteration delay of 0 for(unsigned destIndex = 0; destIndex < memInst.size(); ++destIndex) { @@ -779,19 +779,19 @@ void MSchedGraphSB::addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst, DEBUG(std::cerr << "MInst1: " << *srcInst << "\n"); DEBUG(std::cerr << "MInst2: " << *destInst << "\n"); - + //Assuming instructions without corresponding llvm instructions //are from constant pools. if (!machineTollvm.count(srcInst) || !machineTollvm.count(destInst)) continue; - + bool useDepAnalyzer = true; //Some machine loads and stores are generated by casts, so be //conservative and always add deps Instruction *srcLLVM = machineTollvm[srcInst]; Instruction *destLLVM = machineTollvm[destInst]; - if(!isa<LoadInst>(srcLLVM) + if(!isa<LoadInst>(srcLLVM) && !isa<StoreInst>(srcLLVM)) { if(isa<BinaryOperator>(srcLLVM)) { if(isa<ConstantFP>(srcLLVM->getOperand(0)) || isa<ConstantFP>(srcLLVM->getOperand(1))) @@ -799,7 +799,7 @@ void MSchedGraphSB::addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst, } useDepAnalyzer = false; } - if(!isa<LoadInst>(destLLVM) + if(!isa<LoadInst>(destLLVM) && !isa<StoreInst>(destLLVM)) { if(isa<BinaryOperator>(destLLVM)) { if(isa<ConstantFP>(destLLVM->getOperand(0)) || isa<ConstantFP>(destLLVM->getOperand(1))) @@ -814,29 +814,29 @@ void MSchedGraphSB::addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst, if(destIndex < srcIndex) srcBeforeDest = false; - DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst], - machineTollvm[destInst], + DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst], + machineTollvm[destInst], srcBeforeDest); - - for(std::vector<Dependence>::iterator d = dr.dependences.begin(), + + for(std::vector<Dependence>::iterator d = dr.dependences.begin(), de = dr.dependences.end(); d != de; ++d) { //Add edge from load to store - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphSBEdge::MemoryDep, + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphSBEdge::MemoryDep, d->getDepType(), d->getIteDiff()); - + } } //Otherwise, we can not do any further analysis and must make a dependence else { - + //Get the machine opCode to determine type of memory instruction MachineOpCode destNodeOpCode = destInst->getOpcode(); //Get the Value* that we are reading from the load, always the first op const MachineOperand &mOp = srcInst->getOperand(0); const MachineOperand &mOp2 = destInst->getOperand(0); - + if(mOp.hasAllocatedReg()) if(mOp.getReg() == SparcV9::g0) continue; @@ -849,19 +849,19 @@ void MSchedGraphSB::addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst, if(TMI->isLoad(srcNodeOpCode)) { if(TMI->isStore(destNodeOpCode)) - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphSBEdge::MemoryDep, + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphSBEdge::MemoryDep, MSchedGraphSBEdge::AntiDep, 0); } else if(TMI->isStore(srcNodeOpCode)) { if(TMI->isStore(destNodeOpCode)) - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphSBEdge::MemoryDep, + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphSBEdge::MemoryDep, MSchedGraphSBEdge::OutputDep, 0); else - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphSBEdge::MemoryDep, + memInst[srcIndex]->addOutEdge(memInst[destIndex], + MSchedGraphSBEdge::MemoryDep, MSchedGraphSBEdge::TrueDep, 0); } } diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp index efc203bcc6..a5e9661f1c 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp @@ -112,7 +112,7 @@ namespace llvm { //Label each edge with the type of dependence std::string edgelabel = ""; switch (I.getEdge().getDepOrderType()) { - + case MSchedGraphEdge::TrueDep: edgelabel = "True"; break; @@ -120,11 +120,11 @@ namespace llvm { case MSchedGraphEdge::AntiDep: edgelabel = "Anti"; break; - + case MSchedGraphEdge::OutputDep: edgelabel = "Output"; break; - + default: edgelabel = "Unknown"; break; @@ -171,14 +171,14 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) { //Iterate over BasicBlocks and put them into our worklist if they are valid for (MachineFunction::iterator BI = MF.begin(); BI != MF.end(); ++BI) - if(MachineBBisValid(BI)) { + if(MachineBBisValid(BI)) { if(BI->size() < 100) { Worklist.push_back(&*BI); ++ValidLoops; } else ++JumboBB; - + } defaultInst = 0; @@ -393,7 +393,7 @@ bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) { ++LoopsWithCalls; return false; } - + //Look for conditional move if(OC == V9::MOVRZr || OC == V9::MOVRZi || OC == V9::MOVRLEZr || OC == V9::MOVRLEZi || OC == V9::MOVRLZr || OC == V9::MOVRLZi || OC == V9::MOVRNZr || OC == V9::MOVRNZi @@ -752,13 +752,13 @@ int ModuloSchedulingPass::calculateALAP(MSchedGraphNode *node, int MII, 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); @@ -893,7 +893,7 @@ void ModuloSchedulingPass::addReccurrence(std::vector<MSchedGraphNode*> &recurre destBENode = recurrence[i+1]; break; } - + } } @@ -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; @@ -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); @@ -1053,7 +1053,7 @@ void ModuloSchedulingPass::addSCC(std::vector<MSchedGraphNode*> &SCC, std::map<M for(std::vector<MSchedGraphNode*>::iterator N = SCC.begin(), NE = SCC.end(); N != NE; ++N) { DEBUG(std::cerr << **N << "\n"); totalDelay += (*N)->getLatency(); - + for(unsigned i = 0; i < (*N)->succ_size(); ++i) { MSchedGraphEdge *edge = (*N)->getSuccessor(i); if(find(SCC.begin(), SCC.end(), edge->getDest()) != SCC.end()) { @@ -1063,7 +1063,7 @@ void ModuloSchedulingPass::addSCC(std::vector<MSchedGraphNode*> &SCC, std::map<M 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]))); @@ -1144,7 +1144,7 @@ void ModuloSchedulingPass::findAllCircuits(MSchedGraph *g, int II) { 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]; @@ -1209,7 +1209,7 @@ void ModuloSchedulingPass::findAllCircuits(MSchedGraph *g, int II) { } else break; - } + } DEBUG(std::cerr << "Num Circuits found: " << CircCount << "\n"); } @@ -1303,7 +1303,7 @@ void ModuloSchedulingPass::searchPath(MSchedGraphNode *node, //Check if we should ignore this edge first if(ignoreEdge(node,*S)) continue; - + //check if successor is in this recurrence, we will get to it eventually if(new_reccurrence.count(*S)) continue; @@ -1372,7 +1372,7 @@ void ModuloSchedulingPass::pathToRecc(MSchedGraphNode *node, void ModuloSchedulingPass::computePartialOrder() { TIME_REGION(X, "calculatePartialOrder"); - + DEBUG(std::cerr << "Computing Partial Order\n"); //Only push BA branches onto the final node order, we put other @@ -1380,13 +1380,13 @@ void ModuloSchedulingPass::computePartialOrder() { //it a specific order instead of relying on BA being there? std::vector<MSchedGraphNode*> branches; - + //Steps to add a recurrence to the partial order 1) Find reccurrence //with the highest RecMII. Add it to the partial order. 2) For each //recurrence with decreasing RecMII, add it to the partial order //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 + for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::reverse_iterator I = recurrenceList.rbegin(), E=recurrenceList.rend(); I !=E; ++I) { std::set<MSchedGraphNode*> new_recurrence; @@ -1445,15 +1445,15 @@ void ModuloSchedulingPass::computePartialOrder() { partialOrder.push_back(new_recurrence); - + //Dump out partial order - DEBUG(for(std::vector<std::set<MSchedGraphNode*> >::iterator I = partialOrder.begin(), + 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"; }); - + } } @@ -1530,7 +1530,7 @@ void ModuloSchedulingPass::predIntersect(std::set<MSchedGraphNode*> &CurrentSet, //Check if we are supposed to ignore this edge or not if(ignoreEdge(*P,FinalNodeOrder[j])) continue; - + if(CurrentSet.count(*P)) if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end()) IntersectResult.insert(*P); @@ -1617,7 +1617,7 @@ void ModuloSchedulingPass::orderNodes() { //Get node attributes MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*J)->second; //assert(nodeAttr != nodeToAttributesMap.end() && "Node not in attributes map!"); - + if(maxASAP <= nodeAttr.ASAP) { maxASAP = nodeAttr.ASAP; node = *J; @@ -1637,15 +1637,15 @@ void ModuloSchedulingPass::orderNodes() { while(IntersectCurrent.size() > 0) { DEBUG(std::cerr << "Intersection is not empty, so find heighest height\n"); - + int MOB = 0; int height = 0; MSchedGraphNode *highestHeightNode = *(IntersectCurrent.begin()); - + //Find node in intersection with highest heigh and lowest MOB for(std::set<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(), E = IntersectCurrent.end(); I != E; ++I) { - + //Get current nodes properties MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second; @@ -1662,7 +1662,7 @@ void ModuloSchedulingPass::orderNodes() { } } } - + //Append our node with greatest height to the NodeOrder if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestHeightNode) == FinalNodeOrder.end()) { DEBUG(std::cerr << "Adding node to Final Order: " << *highestHeightNode << "\n"); @@ -1695,9 +1695,9 @@ void ModuloSchedulingPass::orderNodes() { //Reset Intersect to reflect changes in OrderNodes IntersectCurrent.clear(); predIntersect(*CurrentSet, IntersectCurrent); - + } //End If TOP_DOWN - + //Begin if BOTTOM_UP else { DEBUG(std::cerr << "Order is BOTTOM UP\n"); @@ -1711,12 +1711,12 @@ void ModuloSchedulingPass::orderNodes() { int MOB = 0; int depth = 0; MSchedGraphNode *highestDepthNode = *(IntersectCurrent.begin()); - + for(std::set<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(), E = IntersectCurrent.end(); I != E; ++I) { //Find node attribute in graph MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second; - + if(depth < nodeAttr.depth) { highestDepthNode = *I; depth = nodeAttr.depth; @@ -1730,8 +1730,8 @@ void ModuloSchedulingPass::orderNodes() { } } } - - + + //Append highest depth node to the NodeOrder if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestDepthNode) == FinalNodeOrder.end()) { @@ -1740,7 +1740,7 @@ void ModuloSchedulingPass::orderNodes() { } //Remove heightestDepthNode from IntersectOrder IntersectCurrent.erase(highestDepthNode); - + //Intersect heightDepthNode's pred with CurrentSet for(MSchedGraphNode::pred_iterator P = highestDepthNode->pred_begin(), @@ -1748,23 +1748,23 @@ void ModuloSchedulingPass::orderNodes() { if(CurrentSet->count(*P)) { if(ignoreEdge(*P, highestDepthNode)) continue; - + //If not already in Intersect, add if(!IntersectCurrent.count(*P)) IntersectCurrent.insert(*P); } } - + } //End while loop over Intersect Size - + //Change order order = TOP_DOWN; - + //Reset IntersectCurrent to reflect changes in OrderNodes IntersectCurrent.clear(); succIntersect(*CurrentSet, IntersectCurrent); } //End if BOTTOM_DOWN - + DEBUG(std::cerr << "Current Intersection Size: " << IntersectCurrent.size() << "\n"); } //End Wrapping while loop @@ -1808,7 +1808,7 @@ bool ModuloSchedulingPass::computeSchedule(const MachineBasicBlock *BB, MSchedGr bool initialLSVal = false; bool initialESVal = false; int EarlyStart = 0; - int LateStart = 0; + int LateStart = 0; bool hasSucc = false; bool hasPred = false; bool sched; @@ -1826,10 +1826,10 @@ bool ModuloSchedulingPass::computeSchedule(const MachineBasicBlock *BB, MSchedGr //or successors of the node we are trying to schedule for(MSSchedule::schedule_iterator nodesByCycle = schedule.begin(), nodesByCycleEnd = schedule.end(); nodesByCycle != nodesByCycleEnd; ++nodesByCycle) { - + //For this cycle, get the vector of nodes schedule and loop over it for(std::vector<MSchedGraphNode*>::iterator schedNode = nodesByCycle->second.begin(), SNE = nodesByCycle->second.end(); schedNode != SNE; ++schedNode) { - + if((*I)->isPredecessor(*schedNode)) { int diff = (*I)->getInEdge(*schedNode).getIteDiff(); int ES_Temp = nodesByCycle->first + (*schedNode)->getLatency() - diff * II; @@ -1877,7 +1877,7 @@ bool ModuloSchedulingPass::computeSchedule(const MachineBasicBlock *BB, MSchedGr EarlyStart = std::max(EarlyStart, ES_Temp); hasPred = true; } - + if((*I)->isSuccessor(*B)) { int diff = (*B)->getInEdge(*I).getIteDiff(); int LS_Temp = (II+count-1) - (*I)->getLatency() + diff * II; @@ -1886,7 +1886,7 @@ bool ModuloSchedulingPass::computeSchedule(const MachineBasicBlock *BB, MSchedGr LateStart = std::min(LateStart, LS_Temp); hasSucc = true; } - + count--; }*/ @@ -1916,7 +1916,7 @@ bool ModuloSchedulingPass::computeSchedule(const MachineBasicBlock *BB, MSchedGr success = scheduleNode(*I, EarlyStart, EarlyStart + II - 1); if(!success) { - ++II; + ++II; schedule.clear(); break; } @@ -1933,7 +1933,7 @@ bool ModuloSchedulingPass::computeSchedule(const MachineBasicBlock *BB, MSchedGr } DEBUG(std::cerr << "Final II: " << II << "\n"); } - + if(II >= capII) { DEBUG(std::cerr << "Maximum II reached, giving up\n"); @@ -2033,18 +2033,18 @@ void ModuloSchedulingPass::writePrologues(std::vector<MachineBasicBlock *> &prol if(inKernel[j].count(&*MI)) { MachineInstr *instClone = MI->clone(); machineBB->push_back(instClone); - + //If its a branch, insert a nop if(mii->isBranch(instClone->getOpcode())) BuildMI(machineBB, V9::NOP, 0); - + DEBUG(std::cerr << "Cloning: " << *MI << "\n"); //After cloning, we may need to save the value that this instruction defines for(unsigned opNum=0; opNum < MI->getNumOperands(); ++opNum) { Instruction *tmp; - + //get machine operand MachineOperand &mOp = instClone->getOperand(opNum); if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) { @@ -2053,18 +2053,18 @@ void ModuloSchedulingPass::writePrologues(std::vector<MachineBasicBlock *> &prol if(valuesToSave.count(mOp.getVRegValue())) { //Save copy in tmpInstruction tmp = new TmpInstruction(mOp.getVRegValue()); - + //Add TmpInstruction to safe LLVM Instruction MCFI MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(defaultInst); tempMvec.addTemp((Value*) tmp); DEBUG(std::cerr << "Value: " << *(mOp.getVRegValue()) << " New Value: " << *tmp << " Stage: " << i << "\n"); - + newValues[mOp.getVRegValue()][i]= tmp; newValLocation[tmp] = machineBB; DEBUG(std::cerr << "Machine Instr Operands: " << *(mOp.getVRegValue()) << ", 0, " << *tmp << "\n"); - + //Create machine instruction and put int machineBB MachineInstr *saveValue; if(mOp.getVRegValue()->getType() == Type::FloatTy) @@ -2073,7 +2073,7 @@ void ModuloSchedulingPass::writePrologues(std::vector<MachineBasicBlock *> &prol saveValue = BuildMI(machineBB, V9::FMOVD, 3).addReg(mOp.getVRegValue()).addRegDef(tmp); else saveValue = BuildMI(machineBB, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp); - + DEBUG(std::cerr << "Created new machine instr: " << *saveValue << "\n"); } @@ -2161,26 +2161,26 @@ void ModuloSchedulingPass::writeEpilogues(std::vector<MachineBasicBlock *> &epil if(inKernel[j].count(&*MI)) { DEBUG(std::cerr << "Cloning instruction " << *MI << "\n"); MachineInstr *clone = MI->clone(); - + //Update operands that need to use the result from the phi for(unsigned opNum=0; opNum < clone->getNumOperands(); ++opNum) { //get machine operand const MachineOperand &mOp = clone->getOperand(opNum); - + if((mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse())) { - + DEBUG(std::cerr << "Writing PHI for " << (mOp.getVRegValue()) << "\n"); - + //If this is the last instructions for the max iterations ago, don't update operands if(inEpilogue.count(mOp.getVRegValue())) if(inEpilogue[mOp.getVRegValue()] == i) continue; - + //Quickly write appropriate phis for this operand if(newValues.count(mOp.getVRegValue())) { if(newValues[mOp.getVRegValue()].count(i)) { Instruction *tmp = new TmpInstruction(newValues[mOp.getVRegValue()][i]); - + //Get machine code for this instruction MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(defaultInst); tempMvec.addTemp((Value*) tmp); @@ -2193,7 +2193,7 @@ void ModuloSchedulingPass::writeEpilogues(std::vector<MachineBasicBlock *> &epil valPHIs[mOp.getVRegValue()] = tmp; } } - + if(valPHIs.count(mOp.getVRegValue())) { //Update the operand in the cloned instruction clone->getOperand(opNum).setValueReg(valPHIs[mOp.getVRegValue()]); @@ -2215,7 +2215,7 @@ void ModuloSchedulingPass::writeEpilogues(std::vector<MachineBasicBlock *> &epil BL.insert(BLI,machineBB); epilogues.push_back(machineBB); llvm_epilogues.push_back(llvmBB); - + DEBUG(std::cerr << "EPILOGUE #" << i << "\n"); DEBUG(machineBB->print(std::cerr)); } @@ -2272,14 +2272,14 @@ void ModuloSchedulingPass::writeKernel(BasicBlock *llvmBB, MachineBasicBlock *ma //Only create phi if the operand def is from a stage before this one if(schedule.defPreviousStage(mOp.getVRegValue(), I->second)) { TmpInstruction *tmp = new TmpInstruction(mOp.getVRegValue()); - + //Get machine code for this instruction MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(defaultInst); tempMvec.addTemp((Value*) tmp); - + //Update the operand in the cloned instruction instClone->getOperand(i).setValueReg(tmp); - + //save this as our final phi finalPHIValue[mOp.getVRegValue()] = tmp; newValLocation[tmp] = machineBB; @@ -2295,9 +2295,9 @@ void ModuloSchedulingPass::writeKernel(BasicBlock *llvmBB, MachineBasicBlock *ma if(I->second != schedule.getMaxStage()) { if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) { if(valuesToSave.count(mOp.getVRegValue())) { - + TmpInstruction *tmp = new TmpInstruction(mOp.getVRegValue()); - + //Get machine code for this instruction MachineCodeForInstruction & tempVec = MachineCodeForInstruction::get(defaultInst); tempVec.addTemp((Value*) tmp); @@ -2310,8 +2310,8 @@ void ModuloSchedulingPass::writeKernel(BasicBlock *llvmBB, MachineBasicBlock *ma saveValue = BuildMI(machineBB, V9::FMOVD, 3).addReg(mOp.getVRegValue()).addRegDef(tmp); else saveValue = BuildMI(machineBB, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp); - - + + //Save for future cleanup kernelValue[mOp.getVRegValue()] = tmp; newValLocation[tmp] = machineBB; @@ -2383,7 +2383,7 @@ void ModuloSchedulingPass::writeKernel(BasicBlock *llvmBB, MachineBasicBlock *ma //Get machine code for this instruction MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(defaultInst); tempMvec.addTemp((Value*) tmp); - + MachineInstr *saveValue = BuildMI(*machineBB, machineBB->begin(), V9::PHI, 3).addReg(lastPhi).addReg(I->second).addRegDef(tmp); DEBUG(std::cerr << "Resulting PHI: " << *saveValue << "\n"); @@ -2439,7 +2439,7 @@ void ModuloSchedulingPass::removePHIs(const MachineBasicBlock *origBB, std::vect //Get Operand const MachineOperand &mOp = I->getOperand(i); assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Should be a Value*\n"); - + if(!tmp) { tmp = new TmpInstruction(mOp.getVRegValue()); addToMCFI.push_back(tmp); @@ -2463,10 +2463,10 @@ void ModuloSchedulingPass::removePHIs(const MachineBasicBlock *origBB, std::vect BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::FMOVD, 3).addReg(mOp.getVRegValue()).addRegDef(tmp); else BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp); - + break; } - + } } @@ -2480,11 +2480,11 @@ void ModuloSchedulingPass::removePHIs(const MachineBasicBlock *origBB, std::vect BuildMI(*kernelBB, I, V9::FMOVD, 3).addReg(tmp).addRegDef(mOp.getVRegValue()); else BuildMI(*kernelBB, I, V9::ORr, 3).addReg(tmp).addImm(0).addRegDef(mOp.getVRegValue()); - - + + worklist.push_back(std::make_pair(kernelBB, I)); } - + } } @@ -2515,12 +2515,12 @@ void ModuloSchedulingPass::removePHIs(const MachineBasicBlock *origBB, std::vect //Get Operand const MachineOperand &mOp = I->getOperand(i); assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Should be a Value*\n"); - + if(!tmp) { tmp = new TmpInstruction(mOp.getVRegValue()); addToMCFI.push_back(tmp); } - + //Now for all our arguments we read, OR to the new TmpInstruction that we created if(mOp.isUse()) { DEBUG(std::cerr << "Use: " << mOp << "\n"); @@ -2539,13 +2539,13 @@ void ModuloSchedulingPass::removePHIs(const MachineBasicBlock *origBB, std::vect BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::FMOVD, 3).addReg(mOp.getVRegValue()).addRegDef(tmp); else BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp); - + break; } - + } - + } else { //Remove the phi and replace it with an OR @@ -2559,7 +2559,7 @@ void ModuloSchedulingPass::removePHIs(const MachineBasicBlock *origBB, std::vect worklist.push_back(std::make_pair(*MB,I)); } - + } } @@ -2581,7 +2581,7 @@ void ModuloSchedulingPass::removePHIs(const MachineBasicBlock *origBB, std::vect DEBUG(std::cerr << "Deleting PHI " << *I->second << "\n"); I->first->erase(I->second); - + } @@ -2617,7 +2617,7 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) { for(unsigned i=0; i < inst->getNumOperands(); ++i) { //get machine operand const MachineOperand &mOp = inst->getOperand(i); - + if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse()) { //find the value in the map if (const Value* srcI = mOp.getVRegValue()) { @@ -2629,7 +2629,7 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) { //make sure its def is not of the same stage as this instruction //because it will be consumed before its used Instruction *defInst = (Instruction*) srcI; - + //Should we save this value? bool save = true; @@ -2638,20 +2638,20 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) { continue; MachineInstr *defInstr = defMap[srcI]; - + if(lastInstrs.count(defInstr)) { if(lastInstrs[defInstr] == I->second) { save = false; - + } } - + if(save) { assert(!phiUses.count(srcI) && "Did not expect to see phi use twice"); if(isa<PHINode>(srcI)) phiUses[srcI] = I->second; - + valuesToSave[srcI] = std::make_pair(I->first, i); } @@ -2669,7 +2669,7 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) { } } } - + if(mOp.getType() != MachineOperand::MO_VirtualRegister && mOp.isUse()) { assert("Our assumption is wrong. We have another type of register that needs to be saved\n"); } @@ -2706,7 +2706,7 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) { BasicBlock *llvmKernelBB = new BasicBlock("Kernel", (Function*) (BB->getBasicBlock()->getParent())); MachineBasicBlock *machineKernelBB = new MachineBasicBlock(llvmKernelBB); - + MachineFunction *F = (((MachineBasicBlock*)BB)->getParent()); MachineFunction::BasicBlockListType &BL = F->getBasicBlockList(); MachineFunction::BasicBlockListType::iterator BLI = BB; @@ -2815,14 +2815,14 @@ void ModuloSchedulingPass::fixBranches(std::vector<MachineBasicBlock *> &prologu if(TMI->isBranch(OC)) { for(unsigned opNum = 0; opNum < mInst->getNumOperands(); ++opNum) { MachineOperand &mOp = mInst->getOperand(opNum); - + if(mOp.getType() == MachineOperand::MO_PCRelativeDisp) { if(mOp.getVRegValue() == BB->getBasicBlock()) mOp.setValueReg(llvmKernelBB); else if(llvm_epilogues.size() > 0) { assert(origBranchExit == 0 && "There should only be one branch out of the loop"); - + origBranchExit = mOp.getVRegValue(); mOp.setValueReg(llvm_epilogues[0]); } diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp index a9a6b6b770..8b3185155e 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp @@ -73,11 +73,11 @@ namespace llvm { Statistic<> NumLoops("moduloschedSB-numLoops", "Total Number of Loops"); Statistic<> NumSB("moduloschedSB-numSuperBlocks", "Total Number of SuperBlocks"); Statistic<> BBWithCalls("modulosched-BBCalls", "Basic Blocks rejected due to calls"); - Statistic<> BBWithCondMov("modulosched-loopCondMov", + Statistic<> BBWithCondMov("modulosched-loopCondMov", "Basic Blocks rejected due to conditional moves"); - Statistic<> SBResourceConstraint("modulosched-resourceConstraint", + Statistic<> SBResourceConstraint("modulosched-resourceConstraint", "Loops constrained by resources"); - Statistic<> SBRecurrenceConstraint("modulosched-recurrenceConstraint", + Statistic<> SBRecurrenceConstraint("modulosched-recurrenceConstraint", "Loops constrained by recurrences"); Statistic<> SBFinalIISum("modulosched-finalIISum", "Sum of all final II"); Statistic<> SBIISum("modulosched-IISum", "Sum of all theoretical II"); @@ -113,7 +113,7 @@ namespace llvm { //Label each edge with the type of dependence std::string edgelabel = ""; switch (I.getEdge().getDepOrderType()) { - + case MSchedGraphSBEdge::TrueDep: edgelabel = "True"; break; @@ -121,11 +121,11 @@ namespace llvm { case MSchedGraphSBEdge::AntiDep: edgelabel = "Anti"; break; - + case MSchedGraphSBEdge::OutputDep: edgelabel = "Output"; break; - + case MSchedGraphSBEdge::NonDataDep: edgelabel = "Pred"; break; @@ -149,7 +149,7 @@ namespace llvm { bool ModuloSchedulingSBPass::runOnFunction(Function &F) { bool Changed = false; - + //Get MachineFunction MachineFunction &MF = MachineFunction::get(&F); @@ -160,55 +160,55 @@ namespace llvm { //Worklist of superblocks std::vector<std::vector<const MachineBasicBlock*> > Worklist; FindSuperBlocks(F, LI, Worklist); - + DEBUG(if(Worklist.size() == 0) std::cerr << "No superblocks in function to ModuloSchedule\n"); - + //Loop over worklist and ModuloSchedule each SuperBlock for(std::vector<std::vector<const MachineBasicBlock*> >::iterator SB = Worklist.begin(), SBE = Worklist.end(); SB != SBE; ++SB) { - + //Print out Superblock DEBUG(std::cerr << "ModuloScheduling SB: \n"; - for(std::vector<const MachineBasicBlock*>::const_iterator BI = SB->begin(), + for(std::vector<const MachineBasicBlock*>::const_iterator BI = SB->begin(), BE = SB->end(); BI != BE; ++BI) { (*BI)->print(std::cerr);}); - + if(!CreateDefMap(*SB)) { defaultInst = 0; defMap.clear(); continue; } - MSchedGraphSB *MSG = new MSchedGraphSB(*SB, target, indVarInstrs[*SB], DA, + MSchedGraphSB *MSG = new MSchedGraphSB(*SB, target, indVarInstrs[*SB], DA, machineTollvm[*SB]); //Write Graph out to file DEBUG(WriteGraphToFileSB(std::cerr, F.getName(), MSG)); - + //Calculate Resource II int ResMII = calculateResMII(*SB); //Calculate Recurrence II int RecMII = calculateRecMII(MSG, ResMII); - + DEBUG(std::cerr << "Number of reccurrences found: " << recurrenceList.size() << "\n"); - + //Our starting initiation interval is the maximum of RecMII and ResMII if(RecMII < ResMII) ++SBRecurrenceConstraint; else ++SBResourceConstraint; - + II = std::max(RecMII, ResMII); int mII = II; - - + + //Print out II, RecMII, and ResMII DEBUG(std::cerr << "II starts out as " << II << " ( RecMII=" << RecMII << " and ResMII=" << ResMII << ")\n"); - + //Calculate Node Properties calculateNodeAttributes(MSG, ResMII); - + //Dump node properties if in debug mode DEBUG(for(std::map<MSchedGraphSBNode*, MSNodeSBAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I !=E; ++I) { @@ -216,11 +216,11 @@ namespace llvm { << 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<MSchedGraphSBNode*> >::iterator I = partialOrder.begin(), E = partialOrder.end(); I !=E; ++I) { @@ -231,19 +231,19 @@ namespace llvm { //Place nodes in final order orderNodes(); - + //Dump out order of nodes DEBUG(for(std::vector<MSchedGraphSBNode*>::iterator I = FinalNodeOrder.begin(), E = FinalNodeOrder.end(); I != E; ++I) { std::cerr << "FO:" << **I << "\n"; }); - + //Finally schedule nodes bool haveSched = computeSchedule(*SB, MSG); - + //Print out final schedule DEBUG(schedule.print(std::cerr)); - + //Final scheduling step is to reconstruct the loop only if we actual have //stage > 0 if(haveSched) { @@ -253,13 +253,13 @@ namespace llvm { //Changed = true; SBIISum += mII; SBFinalIISum += II; - + if(schedule.getMaxStage() == 0) ++SBSameStage; } else ++SBNoSched; - + //Clear out our maps for the next basic block that is processed nodeToAttributesMap.clear(); partialOrder.clear(); @@ -267,7 +267,7 @@ namespace llvm { FinalNodeOrder.clear(); schedule.clear(); defMap.clear(); - + } return Changed; } @@ -277,7 +277,7 @@ namespace llvm { //Get MachineFunction MachineFunction &MF = MachineFunction::get(&F); - + //Map of LLVM BB to machine BB std::map<BasicBlock*, MachineBasicBlock*> bbMap; @@ -295,16 +295,16 @@ namespace llvm { //If loop is not single entry, try the next one if(!L->getLoopPreheader()) continue; - + //Check size of this loop, we don't want SBB loops if(L->getBlocks().size() == 1) continue; - + //Check if this loop contains no sub loops if(L->getSubLoops().size() == 0) { - + std::vector<const MachineBasicBlock*> superBlock; - + //Get Loop Headers BasicBlock *header = L->getHeader(); @@ -324,7 +324,7 @@ namespace llvm { for(succ_iterator I = succ_begin(current), E = succ_end(current); I != E; ++I) { if(L->contains(*I)) { - if(!next) + if(!next) next = *I; else { done = true; @@ -333,7 +333,7 @@ namespace llvm { } } } - + if(success) { superBlock.push_back(currentMBB); if(next == header) @@ -352,7 +352,7 @@ namespace llvm { } - + if(success) { @@ -366,7 +366,7 @@ namespace llvm { } } } - + if(success) { if(getIndVar(superBlock, bbMap, indexMap)) { ++SBValid; @@ -379,9 +379,9 @@ namespace llvm { } } } - - - bool ModuloSchedulingSBPass::getIndVar(std::vector<const MachineBasicBlock*> &superBlock, std::map<BasicBlock*, MachineBasicBlock*> &bbMap, + + + bool ModuloSchedulingSBPass::getIndVar(std::vector<const MachineBasicBlock*> &superBlock, std::map<BasicBlock*, MachineBasicBlock*> &bbMap, std::map<const MachineInstr*, unsigned> &indexMap) { //See if we can get induction var instructions std::set<const BasicBlock*> llvmSuperBlock; @@ -391,23 +391,23 @@ namespace llvm { //Get Target machine instruction info const TargetInstrInfo *TMI = target.getInstrInfo(); - + //Get the loop back branch BranchInst *b = dyn_cast<BranchInst>(((BasicBlock*) (superBlock[superBlock.size()-1])->getBasicBlock())->getTerminator()); std::set<Instruction*> indVar; if(b->isConditional()) { - //Get the condition for the branch + //Get the condition for the branch Value *cond = b->getCondition(); - + DEBUG(std::cerr << "Condition: " << *cond << "\n"); - + //List of instructions associated with induction variable std::vector<Instruction*> stack; - + //Add branch indVar.insert(b); - + if(Instruction *I = dyn_cast<Instruction>(cond)) if(bbMap.count(I->getParent())) { if (!assocIndVar(I, indVar, stack, bbMap, superBlock[(superBlock.size()-1)]->getBasicBlock(), llvmSuperBlock)) @@ -423,11 +423,11 @@ namespace llvm { } //Dump out instructions associate with indvar for debug reasons - DEBUG(for(std::set<Instruction*>::iterator N = indVar.begin(), NE = indVar.end(); + DEBUG(for(std::set<Instruction*>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) { std::cerr << **N << "\n"; }); - + //Create map of machine instr to llvm instr std::map<MachineInstr*, Instruction*> mllvm; for(std::vector<const MachineBasicBlock*>::iterator MBB = superBlock.begin(), MBE = superBlock.end(); MBB != MBE; ++MBB) { @@ -442,9 +442,9 @@ namespace llvm { //Convert list of LLVM Instructions to list of Machine instructions std::map<const MachineInstr*, unsigned> mIndVar; - for(std::set<Instruction*>::iterator N = indVar.begin(), + for(std::set<Instruction*>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) { - + //If we have a load, we can't handle this loop because //there is no way to preserve dependences between loads //and stores @@ -462,23 +462,23 @@ namespace llvm { DEBUG(std::cerr << *(tempMvec[j]) << " at index " << indexMap[(MachineInstr*) tempMvec[j]] << "\n"); } } - + //Put into a map for future access indVarInstrs[superBlock] = mIndVar; machineTollvm[superBlock] = mllvm; - + return true; - + } - bool ModuloSchedulingSBPass::assocIndVar(Instruction *I, + bool ModuloSchedulingSBPass::assocIndVar(Instruction *I, std::set<Instruction*> &indVar, - std::vector<Instruction*> &stack, - std::map<BasicBlock*, MachineBasicBlock*> &bbMap, + std::vector<Instruction*> &stack, + std::map<BasicBlock*, MachineBasicBlock*> &bbMap, const BasicBlock *last, std::set<const BasicBlock*> &llvmSuperBlock) { stack.push_back(I); - + //If this is a phi node, check if its the canonical indvar if(PHINode *PN = dyn_cast<PHINode>(I)) { if(llvmSuperBlock.count(PN->getParent())) { @@ -506,24 +506,24 @@ namespace llvm { } } } - + stack.pop_back(); return true; } - + /// This function checks if a Machine Basic Block is valid for modulo /// scheduling. This means that it has no control flow (if/else or /// calls) in the block. Currently ModuloScheduling only works on /// single basic block loops. - bool ModuloSchedulingSBPass::MachineBBisValid(const MachineBasicBlock *BI, - std::map<const MachineInstr*, unsigned> &indexMap, + bool ModuloSchedulingSBPass::MachineBBisValid(const MachineBasicBlock *BI, + std::map<const MachineInstr*, unsigned> &indexMap, unsigned &offset) { - + //Check size of our basic block.. make sure we have more then just the terminator in it if(BI->getBasicBlock()->size() == 1) return false; - + //Get Target machine instruction info const TargetInstrInfo *TMI = target.getInstrInfo(); @@ -537,7 +537,7 @@ namespace llvm { ++BBWithCalls; return false; } - + //Look for conditional move if(OC == V9::MOVRZr || OC == V9::MOVRZi || OC == V9::MOVRLEZr || OC == V9::MOVRLEZi || OC == V9::MOVRLZr || OC == V9::MOVRLZi || OC == V9::MOVRNZr || OC == V9::MOVRNZi @@ -567,7 +567,7 @@ namespace llvm { bool ModuloSchedulingSBPass::CreateDefMap(std::vector<const MachineBasicBlock*> &SB) { defaultInst = 0; - for(std::vector<const MachineBasicBlock*>::iterator BI = SB.begin(), + for(std::vector<const MachineBasicBlock*>::iterator BI = SB.begin(), BE = SB.end(); BI != BE; ++BI) { for(MachineBasicBlock::const_iterator I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) { @@ -585,7 +585,7 @@ bool ModuloSchedulingSBPass::CreateDefMap(std::vector<const MachineBasicBlock*> defMap[V] = (MachineInstr*) &*I; } } - + //See if we can use this Value* as our defaultInst if(!defaultInst && mOp.getType() == MachineOperand::MO_VirtualRegister) { Value *V = mOp.getVRegValue(); @@ -595,10 +595,10 @@ bool ModuloSchedulingSBPass::CreateDefMap(std::vector<const MachineBasicBlock*> } } } - + if(!defaultInst) return false; - + return true; } @@ -670,22 +670,22 @@ int ModuloSchedulingSBPass::calculateResMII(std::vector<const MachineBasicBlock* } return ResMII; - + } /// calculateRecMII - Calculates the value of the highest recurrence /// By value we mean the total latency/distance int ModuloSchedulingSBPass::calculateRecMII(MSchedGraphSB *graph, int MII) { - + TIME_REGION(X, "calculateRecMII"); - + findAllCircuits(graph, MII); int RecMII = 0; - + for(std::set<std::pair<int, std::vector<MSchedGraphSBNode*> > >::iterator I = recurrenceList.begin(), E=recurrenceList.end(); I !=E; ++I) { RecMII = std::max(RecMII, I->first); } - + return MII; } @@ -722,7 +722,7 @@ void ModuloSchedulingSBPass::addSCC(std::vector<MSchedGraphSBNode*> &SCC, std::m for(std::vector<MSchedGraphSBNode*>::iterator N = SCC.begin(), NE = SCC.end(); N != NE; ++N) { DEBUG(std::cerr << **N << "\n"); totalDelay += (*N)->getLatency(); - + for(unsigned i = 0; i < (*N)->succ_size(); ++i) { MSchedGraphSBEdge *edge = (*N)->getSuccessor(i); if(find(SCC.begin(), SCC.end(), edge->getDest()) != SCC.end()) { @@ -732,7 +732,7 @@ void ModuloSchedulingSBPass::addSCC(std::vector<MSchedGraphSBNode*> &SCC, std::m start = *N; end = edge->getDest(); } - + } } @@ -744,11 +744,11 @@ void ModuloSchedulingSBPass::addSCC(std::vector<MSchedGraphSBNode*> &SCC, std::m } DEBUG(std::cerr << "End Recc\n"); - + 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]))); @@ -818,7 +818,7 @@ void ModuloSchedulingSBPass::addRecc(std::vector<MSchedGraphSBNode*> &stack, std std::vector<MSchedGraphSBNode*> recc; //Dump recurrence for now DEBUG(std::cerr << "Starting Recc\n"); - + int totalDelay = 0; int totalDistance = 0; MSchedGraphSBNode *lastN = 0; @@ -851,7 +851,7 @@ void ModuloSchedulingSBPass::addRecc(std::vector<MSchedGraphSBNode*> &stack, std DEBUG(std::cerr << "End Recc\n"); CircCountSB++; - 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]))); @@ -867,7 +867,7 @@ void ModuloSchedulingSBPass::addRecc(std::vector<MSchedGraphSBNode*> &stack, std int value = totalDelay-(RecMII * totalDistance); int lastII = II; while(value < 0) { - + lastII = RecMII; RecMII--; value = totalDelay-(RecMII * totalDistance); @@ -930,7 +930,7 @@ void ModuloSchedulingSBPass::findAllCircuits(MSchedGraphSB *g, int II) { if(nextSCC.size() > 1) { DEBUG(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 MSchedGraphSBNode *node = nextSCC[i]; @@ -941,7 +941,7 @@ void ModuloSchedulingSBPass::findAllCircuits(MSchedGraphSB *g, int II) { } DEBUG(std::cerr << "Num Edges: " << numEdges << "\n"); } - + //Ignore self loops if(nextSCC.size() > 1) { @@ -996,7 +996,7 @@ void ModuloSchedulingSBPass::findAllCircuits(MSchedGraphSB *g, int II) { } else break; - } + } DEBUG(std::cerr << "Num Circuits found: " << CircCountSB << "\n"); } /// calculateNodeAttributes - The following properties are calculated for @@ -1129,13 +1129,13 @@ int ModuloSchedulingSBPass::calculateALAP(MSchedGraphSBNode *node, int MII, 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); @@ -1230,7 +1230,7 @@ int ModuloSchedulingSBPass::calculateDepth(MSchedGraphSBNode *node, void ModuloSchedulingSBPass::computePartialOrder() { TIME_REGION(X, "calculatePartialOrder"); - + DEBUG(std::cerr << "Computing Partial Order\n"); //Steps to add a recurrence to the partial order 1) Find reccurrence @@ -1238,7 +1238,7 @@ void ModuloSchedulingSBPass::computePartialOrder() { //recurrence with decreasing RecMII, add it to the partial order //along with any nodes that connect this recurrence to recurrences //already in the partial order - for(std::set<std::pair<int, std::vector<MSchedGraphSBNode*> > >::reverse_iterator + for(std::set<std::pair<int, std::vector<MSchedGraphSBNode*> > >::reverse_iterator I = recurrenceList.rbegin(), E=recurrenceList.rend(); I !=E; ++I) { std::set<MSchedGraphSBNode*> new_recurrence; @@ -1339,7 +1339,7 @@ void ModuloSchedulingSBPass::computePartialOrder() { } void ModuloSchedulingSBPass::connectedComponentSet(MSchedGraphSBNode *node, std::set<MSchedGraphSBNode*> &ccSet, std::set<MSchedGraphSBNode*> &lastNodes) { - + //Add to final set if( !ccSet.count(node) && lastNodes.count(node)) { lastNodes.erase(node); @@ -1370,7 +1370,7 @@ void ModuloSchedulingSBPass::searchPath(MSchedGraphSBNode *node, //Check if we should ignore this edge first if(ignoreEdge(node,*S)) continue; - + //check if successor is in this recurrence, we will get to it eventually if(new_reccurrence.count(*S)) continue; @@ -1465,7 +1465,7 @@ void ModuloSchedulingSBPass::orderNodes() { //Get node attributes MSNodeSBAttributes nodeAttr= nodeToAttributesMap.find(*J)->second; //assert(nodeAttr != nodeToAttributesMap.end() && "Node not in attributes map!"); - + if(maxASAP <= nodeAttr.ASAP) { maxASAP = nodeAttr.ASAP; node = *J; @@ -1485,15 +1485,15 @@ void ModuloSchedulingSBPass::orderNodes() { while(IntersectCurrent.size() > 0) { DEBUG(std::cerr << "Intersection is not empty, so find heighest height\n"); - + int MOB = 0; int height = 0; MSchedGraphSBNode *highestHeightNode = *(IntersectCurrent.begin()); - + //Find node in intersection with highest heigh and lowest MOB for(std::set<MSchedGraphSBNode*>::iterator I = IntersectCurrent.begin(), E = IntersectCurrent.end(); I != E; ++I) { - + //Get current nodes properties MSNodeSBAttributes nodeAttr= nodeToAttributesMap.find(*I)->second; @@ -1510,7 +1510,7 @@ void ModuloSchedulingSBPass::orderNodes() { } } } - + //Append our node with greatest height to the NodeOrder if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestHeightNode) == FinalNodeOrder.end()) { DEBUG(std::cerr << "Adding node to Final Order: " << *highestHeightNode << "\n"); @@ -1543,9 +1543,9 @@ void ModuloSchedulingSBPass::orderNodes() { //Reset Intersect to reflect changes in OrderNodes IntersectCurrent.clear(); predIntersect(*CurrentSet, IntersectCurrent); - + } //End If TOP_DOWN - + //Begin if BOTTOM_UP else { DEBUG(std::cerr << "Order is BOTTOM UP\n"); @@ -1559,12 +1559,12 @@ void ModuloSchedulingSBPass::orderNodes() { int MOB = 0; int depth = 0; MSchedGraphSBNode *highestDepthNode = *(IntersectCurrent.begin()); - + for(std::set<MSchedGraphSBNode*>::iterator I = IntersectCurrent.begin(), E = IntersectCurrent.end(); I != E; ++I) { //Find node attribute in graph MSNodeSBAttributes nodeAttr= nodeToAttributesMap.find(*I)->second; - + if(depth < nodeAttr.depth) { highestDepthNode = *I; depth = nodeAttr.depth; @@ -1578,8 +1578,8 @@ void ModuloSchedulingSBPass::orderNodes() { } } } - - + + //Append highest depth node to the NodeOrder if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestDepthNode) == FinalNodeOrder.end()) { @@ -1588,7 +1588,7 @@ void ModuloSchedulingSBPass::orderNodes() { } //Remove heightestDepthNode from IntersectOrder IntersectCurrent.erase(highestDepthNode); - + //Intersect heightDepthNode's pred with CurrentSet for(MSchedGraphSBNode::pred_iterator P = highestDepthNode->pred_begin(), @@ -1596,23 +1596,23 @@ void ModuloSchedulingSBPass::orderNodes() { if(CurrentSet->count(*P)) { if(ignoreEdge(*P, highestDepthNode)) continue; - + //If not already in Intersect, add if(!IntersectCurrent.count(*P)) IntersectCurrent.insert(*P); } } - + } //End while loop over Intersect Size - + //Change order order = TOP_DOWN; - + //Reset IntersectCurrent to reflect changes in OrderNodes IntersectCurrent.clear(); succIntersect(*CurrentSet, IntersectCurrent); } //End if BOTTOM_DOWN - + DEBUG(std::cerr << "Current Intersection Size: " << IntersectCurrent.size() << "\n"); } //End Wrapping while loop @@ -1643,7 +1643,7 @@ void ModuloSchedulingSBPass::predIntersect(std::set<MSchedGraphSBNode*> &Current //Check if we are supposed to ignore this edge or not if(ignoreEdge(*P,FinalNodeOrder[j])) continue; - + if(CurrentSet.count(*P)) if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end()) IntersectResult.insert(*P); @@ -1693,7 +1693,7 @@ bool ModuloSchedulingSBPass::computeSchedule(std::vector<const MachineBasicBlock bool initialLSVal = false; bool initialESVal = false; int EarlyStart = 0; - int LateStart = 0; + int LateStart = 0; bool hasSucc = false; bool hasPred = false; bool sched; @@ -1711,10 +1711,10 @@ bool ModuloSchedulingSBPass::computeSchedule(std::vector<const MachineBasicBlock //or successors of the node we are trying to schedule for(MSScheduleSB::schedule_iterator nodesByCycle = schedule.begin(), nodesByCycleEnd = schedule.end(); nodesByCycle != nodesByCycleEnd; ++nodesByCycle) { - + //For this cycle, get the vector of nodes schedule and loop over it for(std::vector<MSchedGraphSBNode*>::iterator schedNode = nodesByCycle->second.begin(), SNE = nodesByCycle->second.end(); schedNode != SNE; ++schedNode) { - + if((*I)->isPredecessor(*schedNode)) { int diff = (*I)->getInEdge(*schedNode).getIteDiff(); int ES_Temp = nodesByCycle->first + (*schedNode)->getLatency() - diff * II; @@ -1775,7 +1775,7 @@ bool ModuloSchedulingSBPass::computeSchedule(std::vector<const MachineBasicBlock success = scheduleNode(*I, EarlyStart, EarlyStart + II - 1); if(!success) { - ++II; + ++II; schedule.clear(); break; } @@ -1791,7 +1791,7 @@ bool ModuloSchedulingSBPass::computeSchedule(std::vector<const MachineBasicBlock schedule.clear(); } DEBUG(std::cerr << "Final II: " << II << "\n"); - + } if(II >= capII) { @@ -1877,7 +1877,7 @@ void ModuloSchedulingSBPass::reconstructLoop(std::vector<const MachineBasicBlock //Loop over kernel and only look at instructions from a stage > 0 //Look at its operands and save values *'s that are read for(MSScheduleSB::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) { - + if(I->second !=0) { //For this instruction, get the Value*'s that it reads and put them into the set. //Assert if there is an operand of another type that we need to save @@ -1887,7 +1887,7 @@ void ModuloSchedulingSBPass::reconstructLoop(std::vector<const MachineBasicBlock for(unsigned i=0; i < inst->getNumOperands(); ++i) { //get machine operand const MachineOperand &mOp = inst->getOperand(i); - + if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse()) { //find the value in the map if (const Value* srcI = mOp.getVRegValue()) { @@ -1899,7 +1899,7 @@ void ModuloSchedulingSBPass::reconstructLoop(std::vector<const MachineBasicBlock //make sure its def is not of the same stage as this instruction //because it will be consumed before its used Instruction *defInst = (Instruction*) srcI; - + //Should we save this value? bool save = true; @@ -1908,27 +1908,27 @@ void ModuloSchedulingSBPass::reconstructLoop(std::vector<const MachineBasicBlock continue; MachineInstr *defInstr = defMap[srcI]; - + if(lastInstrs.count(defInstr)) { if(lastInstrs[defInstr] == I->second) { save = false; - + } } - + if(save) valuesToSave[srcI] = std::make_pair(I->first, i); - } + } } - + if(mOp.getType() != MachineOperand::MO_VirtualRegister && mOp.isUse()) { assert("Our assumption is wrong. We have another type of register that needs to be saved\n"); } } } - - + + //Do a check to see if instruction was moved below its original branch if(MTI->isBranch(I->first->getOpcode())) { seenBranchesBB.insert(I->first->getParent()); @@ -1959,7 +1959,7 @@ void ModuloSchedulingSBPass::reconstructLoop(std::vector<const MachineBasicBlock //Map to keep track of where the inner branches go std::map<const MachineBasicBlock*, Value*> sideExits; - + //Write prologue if(schedule.getMaxStage() != 0) writePrologues(prologues, SB, llvm_prologues, valuesToSave, newValues, newValLocation); @@ -1970,7 +1970,7 @@ void ModuloSchedulingSBPass::reconstructLoop(std::vector<const MachineBasicBlock for(unsigned i = 0; i < SB.size(); ++i) { llvmKernelBBs.push_back(new BasicBlock("Kernel", parent)); - + machineKernelBBs.push_back(new MachineBasicBlock(llvmKernelBBs[i])); (((MachineBasicBlock*)SB[0])->getParent())->getBasicBlockList().push_back(machineKernelBBs[i]); } @@ -2067,7 +2067,7 @@ void ModuloSchedulingSBPass::fixBranches(std::vector<std::vector<MachineBasicBlo for(unsigned j = 0; j < prologues[i].size(); ++j) { MachineBasicBlock *currentMBB = prologues[i][j]; - + //Find terminator since getFirstTerminator does not work! for(MachineBasicBlock::reverse_iterator mInst = currentMBB->rbegin(), mInstEnd = currentMBB->rend(); mInst != mInstEnd; ++mInst) { MachineOpCode OC = mInst->getOpcode(); @@ -2089,17 +2089,17 @@ void ModuloSchedulingSBPass::fixBranches(std::vector<std::vector<MachineBasicBlo else if(mOp.getVRegValue() == SB[j+1]->getBasicBlock()) { mOp.setValueReg(llvm_prologues[i][j+1]); } - + } } - + DEBUG(std::cerr << "New Prologue Branch: " << *mInst << "\n"); } } //Update llvm basic block with our new branch instr DEBUG(std::cerr << SB[i]->getBasicBlock()->getTerminator() << "\n"); - + const BranchInst *branchVal = dyn_cast<BranchInst>(SB[i]->getBasicBlock()->getTerminator()); //Check for inner branch @@ -2144,7 +2144,7 @@ void ModuloSchedulingSBPass::fixBranches(std::vector<std::vector<MachineBasicBlo if(TMI->isBranch(OC)) { for(unsigned opNum = 0; opNum < mInst->getNumOperands(); ++opNum) { MachineOperand &mOp = mInst->getOperand(opNum); - + if(mOp.getType() == MachineOperand::MO_PCRelativeDisp) { //Deal with inner kernel branches if(i < machineKernelBB.size()-1) { @@ -2170,10 +2170,10 @@ void ModuloSchedulingSBPass::fixBranches(std::vector<std::vector<MachineBasicBlo //Update kernelLLVM branches const BranchInst *branchVal = dyn_cast<BranchInst>(SB[0]->getBasicBlock()->getTerminator()); - + //deal with inner branch if(i < machineKernelBB.size()-1) { - + //Find our side exit LLVM basic block BasicBlock *sideExit = 0; for(unsigned s = 0; s < branchVal->getNumSuccessors(); ++s) { @@ -2204,38 +2204,38 @@ void ModuloSchedulingSBPass::fixBranches(std::vector<std::vector<MachineBasicBlo } if(schedule.getMaxStage() != 0) { - + //Lastly add unconditional branches for the epilogues for(unsigned i = 0; i < epilogues.size(); ++i) { for(unsigned j=0; j < epilogues[i].size(); ++j) { //Now since we don't have fall throughs, add a unconditional //branch to the next prologue - + //Before adding these, we need to check if the epilogue already has //a branch in it bool hasBranch = false; /*if(j < epilogues[i].size()-1) { MachineBasicBlock *currentMBB = epilogues[i][j]; for(MachineBasicBlock::reverse_iterator mInst = currentMBB->rbegin(), mInstEnd = currentMBB->rend(); mInst != mInstEnd; ++mInst) { - + MachineOpCode OC = mInst->getOpcode(); - + //If its a branch update its branchto if(TMI->isBranch(OC)) { hasBranch = true; for(unsigned opNum = 0; opNum < mInst->getNumOperands(); ++opNum) { MachineOperand &mOp = mInst->getOperand(opNum); if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) { - + if(mOp.getVRegValue() != sideExits[SB[j]]) { mOp.setValueReg(llvm_epilogues[i][j+1]); } - + } } - - + + DEBUG(std::cerr << "New Epilogue Branch: " << *mInst << "\n"); } } @@ -2249,7 +2249,7 @@ void ModuloSchedulingSBPass::fixBranches(std::vector<std::vector<MachineBasicBlo }*/ if(!hasBranch) { - + //Handle inner branches if(j < epilogues[i].size()-1) { BuildMI(epilogues[i][j], V9::BA, 1).addPCDisp(llvm_epilogues[i][j+1]); @@ -2257,24 +2257,24 @@ void ModuloSchedulingSBPass::fixBranches(std::vector<std::vector<MachineBasicBlo llvm_epilogues[i][j]); } else { - + //Check if this is the last epilogue if(i != epilogues.size()-1) { BuildMI(epilogues[i][j], V9::BA, 1).addPCDisp(llvm_epilogues[i+1][0]); //Add unconditional branch to end of epilogue TerminatorInst *newBranch = new BranchInst(llvm_epilogues[i+1][0], llvm_epilogues[i][j]); - + } else { BuildMI(epilogues[i][j], V9::BA, 1).addPCDisp(kernel_exit); TerminatorInst *newBranch = new BranchInst(kernel_exit, llvm_epilogues[i][j]); } } - + //Add one more nop! BuildMI(epilogues[i][j], V9::NOP, 0); - + } } } @@ -2283,10 +2283,10 @@ void ModuloSchedulingSBPass::fixBranches(std::vector<std::vector<MachineBasicBlo //Find all llvm basic blocks that branch to the loop entry and //change to our first prologue. const BasicBlock *llvmBB = SB[0]->getBasicBlock(); - + std::vector<const BasicBlock*>Preds (pred_begin(llvmBB), pred_end(llvmBB)); - - for(std::vector<const BasicBlock*>::iterator P = Preds.begin(), + + for(std::vector<const BasicBlock*>::iterator P = Preds.begin(), PE = Preds.end(); P != PE; ++P) { if(*P == SB[SB.size()-1]->getBasicBlock()) continue; @@ -2295,7 +2295,7 @@ void ModuloSchedulingSBPass::fixBranches(std::vector<std::vector<MachineBasicBlo DEBUG((*P)->print(std::cerr)); //Get the Terminator instruction for this basic block and print it out //DEBUG(std::cerr << *((*P)->getTerminator()) << "\n"); - + //Update the terminator TerminatorInst *term = ((BasicBlock*)*P)->getTerminator(); for(unsigned i=0; i < term->getNumSuccessors(); ++i) { @@ -2383,7 +2383,7 @@ void ModuloSchedulingSBPass::writePrologues(std::vector<std::vector<MachineBasic std::vector<MachineBasicBlock*> current_prologue; std::vector<BasicBlock*> current_llvm_prologue; - for(std::vector<const MachineBasicBlock*>::iterator MB = origSB.begin(), + for(std::vector<const MachineBasicBlock*>::iterator MB = origSB.begin(), MBE = origSB.end(); MB != MBE; ++MB) { const MachineBasicBlock *MBB = *MB; //Create new llvm and machine bb @@ -2394,46 +2394,46 @@ void ModuloSchedulingSBPass::writePrologues(std::vector<std::vector<MachineBasic for(int j = i; j >= 0; --j) { //iterate over instructions in original bb - for(MachineBasicBlock::const_iterator MI = MBB->begin(), + for(MachineBasicBlock::const_iterator MI = MBB->begin(), ME = MBB->end(); ME != MI; ++MI) { if(inKernel[j].count(&*MI)) { MachineInstr *instClone = MI->clone(); machineBB->push_back(instClone); - + //If its a branch, insert a nop if(mii->isBranch(instClone->getOpcode())) BuildMI(machineBB, V9::NOP, 0); - - + + DEBUG(std::cerr << "Cloning: " << *MI << "\n"); - + //After cloning, we may need to save the value that this instruction defines for(unsigned opNum=0; opNum < MI->getNumOperands(); ++opNum) { Instruction *tmp; - + //get machine operand MachineOperand &mOp = instClone->getOperand(opNum); - if(mOp.getType() == MachineOperand::MO_VirtualRegister + if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) { //Check if this is a value we should save if(valuesToSave.count(mOp.getVRegValue())) { //Save copy in tmpInstruction tmp = new TmpInstruction(mOp.getVRegValue()); - + //Add TmpInstruction to safe LLVM Instruction MCFI MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(defaultInst); tempMvec.addTemp((Value*) tmp); - DEBUG(std::cerr << "Value: " << *(mOp.getVRegValue()) + DEBUG(std::cerr << "Value: " << *(mOp.getVRegValue()) << " New Value: " << *tmp << " Stage: " << i << "\n"); - + newValues[mOp.getVRegValue()][i]= tmp; newValLocation[tmp] = machineBB; - DEBUG(std::cerr << "Machine Instr Operands: " + DEBUG(std::cerr << "Machine Instr Operands: " << *(mOp.getVRegValue()) << ", 0, " << *tmp << "\n"); - + //Create machine instruction and put int machineBB MachineInstr *saveValue; if(mOp.getVRegValue()->getType() == Type::FloatTy) @@ -2442,7 +2442,7 @@ void ModuloSchedulingSBPass::writePrologues(std::vector<std::vector<MachineBasic saveValue = BuildMI(machineBB, V9::FMOVD, 3).addReg(mOp.getVRegValue()).addRegDef(tmp); else saveValue = BuildMI(machineBB, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp); - + DEBUG(std::cerr << "Created new machine instr: " << *saveValue << "\n"); } @@ -2458,7 +2458,7 @@ void ModuloSchedulingSBPass::writePrologues(std::vector<std::vector<MachineBasic DEBUG(std::cerr << "Replaced this value: " << mOp.getVRegValue() << " With:" << (newValues[mOp.getVRegValue()][i-1]) << "\n"); //Update the operand with the right value mOp.setValueReg(newValues[mOp.getVRegValue()][i-1]); - + //Remove this value since we have consumed it //NOTE: Should this only be done if j != maxStage? consumedValues[oldV][i-1] = (newValues[oldV][i-1]); @@ -2511,55 +2511,55 @@ void ModuloSchedulingSBPass::writeEpilogues(std::vector<std::vector<MachineBasic for(int i = schedule.getMaxStage()-1; i >= 0; --i) { std::vector<MachineBasicBlock*> current_epilogue; std::vector<BasicBlock*> current_llvm_epilogue; - + for(std::vector<const MachineBasicBlock*>::iterator MB = origSB.begin(), MBE = origSB.end(); MB != MBE; ++MB) { const MachineBasicBlock *MBB = *MB; BasicBlock *llvmBB = new BasicBlock("EPILOGUE", (Function*) (MBB->getBasicBlock()->getParent())); MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB); - + DEBUG(std::cerr << " Epilogue #: " << i << "\n"); - + std::map<Value*, int> inEpilogue; - + for(MachineBasicBlock::const_iterator MI = MBB->begin(), ME = MBB->end(); ME != MI; ++MI) { for(int j=schedule.getMaxStage(); j > i; --j) { if(inKernel[j].count(&*MI)) { DEBUG(std::cerr << "Cloning instruction " << *MI << "\n"); MachineInstr *clone = MI->clone(); - + //Update operands that need to use the result from the phi for(unsigned opNum=0; opNum < clone->getNumOperands(); ++opNum) { //get machine operand const MachineOperand &mOp = clone->getOperand(opNum); - + if((mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isUse())) { - + DEBUG(std::cerr << "Writing PHI for " << (mOp.getVRegValue()) << "\n"); - + //If this is the last instructions for the max iterations ago, don't update operands if(inEpilogue.count(mOp.getVRegValue())) if(inEpilogue[mOp.getVRegValue()] == i) continue; - + //Quickly write appropriate phis for this operand if(newValues.count(mOp.getVRegValue())) { if(newValues[mOp.getVRegValue()].count(i)) { Instruction *tmp = new TmpInstruction(newValues[mOp.getVRegValue()][i]); - + //Get machine code for this instruction MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(defaultInst); tempMvec.addTemp((Value*) tmp); - + //assert of no kernelPHI for this value assert(kernelPHIs[mOp.getVRegValue()][i] !=0 && "Must have final kernel phi to construct epilogue phi"); - + MachineInstr *saveValue = BuildMI(machineBB, V9::PHI, 3).addReg(newValues[mOp.getVRegValue()][i]).addReg(kernelPHIs[mOp.getVRegValue()][i]).addRegDef(tmp); DEBUG(std::cerr << "Resulting PHI: " << *saveValue << "\n"); valPHIs[mOp.getVRegValue()] = tmp; } } - + if(valPHIs.count(mOp.getVRegValue())) { //Update the operand in the cloned instruction clone->getOperand(opNum).setValueReg(valPHIs[mOp.getVRegValue()]); @@ -2568,7 +2568,7 @@ void ModuloSchedulingSBPass::writeEpilogues(std::vector<std::vector<MachineBasic else if((mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef())) { inEpilogue[mOp.getVRegValue()] = i; } - + } machineBB->push_back(clone); //if(MTI->isBranch(clone->getOpcode())) @@ -2580,11 +2580,11 @@ void ModuloSchedulingSBPass::writeEpilogues(std::vector<std::vector<MachineBasic current_epilogue.push_back(machineBB); current_llvm_epilogue.push_back(llvmBB); } - + DEBUG(std::cerr << "EPILOGUE #" << i << "\n"); DEBUG(for(std::vector<MachineBasicBlock*>::iterator B = current_epilogue.begin(), BE = current_epilogue.end(); B != BE; ++B) { (*B)->print(std::cerr);}); - + epilogues.push_back(current_epilogue); llvm_epilogues.push_back(current_llvm_epilogue); } @@ -2635,7 +2635,7 @@ void ModuloSchedulingSBPass::writeKernel(std::vector<BasicBlock*> &llvmBB, std:: seenBranch = true; numBr++; } - + DEBUG(std::cerr << "Cloned Inst: " << *instClone << "\n"); //Loop over Machine Operands @@ -2659,14 +2659,14 @@ void ModuloSchedulingSBPass::writeKernel(std::vector<BasicBlock*> &llvmBB, std:: //Only create phi if the operand def is from a stage before this one if(schedule.defPreviousStage(mOp.getVRegValue(), I->second)) { TmpInstruction *tmp = new TmpInstruction(mOp.getVRegValue()); - + //Get machine code for this instruction MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(defaultInst); tempMvec.addTemp((Value*) tmp); - + //Update the operand in the cloned instruction instClone->getOperand(i).setValueReg(tmp); - + //save this as our final phi finalPHIValue[mOp.getVRegValue()] = tmp; newValLocation[tmp] = machineBB[index]; @@ -2682,9 +2682,9 @@ void ModuloSchedulingSBPass::writeKernel(std::vector<BasicBlock*> &llvmBB, std:: if(I->second != schedule.getMaxStage()) { if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) { if(valuesToSave.count(mOp.getVRegValue())) { - + TmpInstruction *tmp = new TmpInstruction(mOp.getVRegValue()); - + //Get machine code for this instruction MachineCodeForInstruction & tempVec = MachineCodeForInstruction::get(defaultInst); tempVec.addTemp((Value*) tmp); @@ -2697,8 +2697,8 @@ void ModuloSchedulingSBPass::writeKernel(std::vector<BasicBlock*> &llvmBB, std:: saveValue = BuildMI(machineBB[index], V9::FMOVD, 3).addReg(mOp.getVRegValue()).addRegDef(tmp); else saveValue = BuildMI(machineBB[index], V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp); - - + + //Save for future cleanup kernelValue[mOp.getVRegValue()] = tmp; newValLocation[tmp] = machineBB[index]; @@ -2760,7 +2760,7 @@ void ModuloSchedulingSBPass::writeKernel(std::vector<BasicBlock*> &llvmBB, std:: //Get machine code for this instruction MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(defaultInst); tempMvec.addTemp((Value*) tmp); - + MachineInstr *saveValue = BuildMI(*machineBB[0], machineBB[0]->begin(), V9::PHI, 3).addReg(lastPhi).addReg(I->second).addRegDef(tmp); DEBUG(std::cerr << "Resulting PHI: " << *saveValue << "\n"); @@ -2802,11 +2802,11 @@ void ModuloSchedulingSBPass::removePHIs(std::vector<const MachineBasicBlock*> &S //Start with the kernel and for each phi insert a copy for the phi //def and for each arg //phis are only in the first BB in the kernel - for(MachineBasicBlock::iterator I = kernelBB[0]->begin(), E = kernelBB[0]->end(); + for(MachineBasicBlock::iterator I = kernelBB[0]->begin(), E = kernelBB[0]->end(); I != E; ++I) { DEBUG(std::cerr << "Looking at Instr: " << *I << "\n"); - + //Get op code and check if its a phi if(I->getOpcode() == V9::PHI) { @@ -2814,12 +2814,12 @@ void ModuloSchedulingSBPass::removePHIs(std::vector<const MachineBasicBlock*> &S Instruction *tmp = 0; for(unsigned i = 0; i < I->getNumOperands(); ++i) { - + //Get Operand const MachineOperand &mOp = I->getOperand(i); - assert(mOp.getType() == MachineOperand::MO_VirtualRegister + assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Should be a Value*\n"); - + if(!tmp) { tmp = new TmpInstruction(mOp.getVRegValue()); addToMCFI.push_back(tmp); @@ -2844,10 +2844,10 @@ void ModuloSchedulingSBPass::removePHIs(std::vector<const MachineBasicBlock*> &S BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::FMOVD, 3).addReg(mOp.getVRegValue()).addRegDef(tmp); else BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp); - + break; } - + } } @@ -2861,11 +2861,11 @@ void ModuloSchedulingSBPass::removePHIs(std::vector<const MachineBasicBlock*> &S BuildMI(*kernelBB[0], I, V9::FMOVD, 3).addReg(tmp).addRegDef(mOp.getVRegValue()); else BuildMI(*kernelBB[0], I, V9::ORr, 3).addReg(tmp).addImm(0).addRegDef(mOp.getVRegValue()); - - + + worklist.push_back(std::make_pair(kernelBB[0], I)); } - + } } @@ -2884,12 +2884,12 @@ void ModuloSchedulingSBPass::removePHIs(std::vector<const MachineBasicBlock*> &S //Remove phis from epilogue - for(std::vector<std::vector<MachineBasicBlock*> >::iterator MB = epilogues.begin(), + for(std::vector<std::vector<MachineBasicBlock*> >::iterator MB = epilogues.begin(), ME = epilogues.end(); MB != ME; ++MB) { - + for(std::vector<MachineBasicBlock*>::iterator currentMBB = MB->begin(), currentME = MB->end(); currentMBB != currentME; ++currentMBB) { - - for(MachineBasicBlock::iterator I = (*currentMBB)->begin(), + + for(MachineBasicBlock::iterator I = (*currentMBB)->begin(), E = (*currentMBB)->end(); I != E; ++I) { DEBUG(std::cerr << "Looking at Instr: " << *I << "\n"); @@ -2901,12 +2901,12 @@ void ModuloSchedulingSBPass::removePHIs(std::vector<const MachineBasicBlock*> &S //Get Operand const MachineOperand &mOp = I->getOperand(i); assert(mOp.getType() == MachineOperand::MO_VirtualRegister && "Should be a Value*\n"); - + if(!tmp) { tmp = new TmpInstruction(mOp.getVRegValue()); addToMCFI.push_back(tmp); } - + //Now for all our arguments we read, OR to the new TmpInstruction that we created if(mOp.isUse()) { DEBUG(std::cerr << "Use: " << mOp << "\n"); @@ -2925,13 +2925,13 @@ void ModuloSchedulingSBPass::removePHIs(std::vector<const MachineBasicBlock*> &S BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::FMOVD, 3).addReg(mOp.getVRegValue()).addRegDef(tmp); else BuildMI(*(newValLocation[mOp.getVRegValue()]), ++inst, V9::ORr, 3).addReg(mOp.getVRegValue()).addImm(0).addRegDef(tmp); - - + + break; } - + } - + } else { //Remove the phi and replace it with an OR @@ -2942,7 +2942,7 @@ void ModuloSchedulingSBPass::removePHIs(std::vector<const MachineBasicBlock*> &S BuildMI(**currentMBB, I, V9::FMOVD, 3).addReg(tmp).addRegDef(mOp.getVRegValue()); else BuildMI(**currentMBB, I, V9::ORr, 3).addReg(tmp).addImm(0).addRegDef(mOp.getVRegValue()); - + worklist.push_back(std::make_pair(*currentMBB,I)); } } @@ -2959,12 +2959,12 @@ void ModuloSchedulingSBPass::removePHIs(std::vector<const MachineBasicBlock*> &S } addToMCFI.clear(); } - + //Delete the phis for(std::vector<std::pair<MachineBasicBlock*, MachineBasicBlock::iterator> >::iterator I = worklist.begin(), E = worklist.end(); I != E; ++I) { DEBUG(std::cerr << "Deleting PHI " << *I->second << "\n"); I->first->erase(I->second); - + } @@ -2990,7 +2990,7 @@ void ModuloSchedulingSBPass::writeSideExits(std::vector<std::vector<MachineBasic //Get the LLVM basic block BasicBlock *bb = (BasicBlock*) SB[sideExitNum]->getBasicBlock(); MachineBasicBlock *mbb = (MachineBasicBlock*) SB[sideExitNum]; - + int stage = branchStage[mbb]; //Create new basic blocks for our side exit instructios that were moved below the branch @@ -2998,17 +2998,17 @@ void ModuloSchedulingSBPass::writeSideExits(std::vector<std::vector<MachineBasic sideMBB = new MachineBasicBlock(sideBB); (((MachineBasicBlock*)SB[0])->getParent())->getBasicBlockList().push_back(sideMBB); - + if(instrsMovedDown.count(mbb)) { for(std::vector<std::pair<MachineInstr*, int> >::iterator I = instrsMovedDown[mbb].begin(), E = instrsMovedDown[mbb].end(); I != E; ++I) { if(branchStage[mbb] == I->second) sideMBB->push_back((I->first)->clone()); } - + //Add unconditional branches to original exits BuildMI(sideMBB, V9::BA, 1).addPCDisp(sideExits[mbb]); BuildMI(sideMBB, V9::NOP, 0); - + //Add unconditioal branch to llvm BB BasicBlock *extBB = dyn_cast<BasicBlock>(sideExits[mbb]); assert(extBB && "Side exit basicblock can not be null"); @@ -3019,19 +3019,19 @@ void ModuloSchedulingSBPass::writeSideExits(std::vector<std::vector<MachineBasic //only clone epilogues that are from a greater stage! for(unsigned i = 0; i < epilogues.size()-stage; ++i) { std::vector<MachineBasicBlock*> MB = epilogues[i]; - + std::vector<MachineBasicBlock*> newEp; std::vector<BasicBlock*> newLLVMEp; - - for(std::vector<MachineBasicBlock*>::iterator currentMBB = MB.begin(), + + for(std::vector<MachineBasicBlock*>::iterator currentMBB = MB.begin(), lastMBB = MB.end(); currentMBB != lastMBB; ++currentMBB) { BasicBlock *tmpBB = new BasicBlock("SideEpilogue", (Function*) (*currentMBB)->getBasicBlock()->getParent()); MachineBasicBlock *tmp = new MachineBasicBlock(tmpBB); - + //Clone instructions and insert into new MBB - for(MachineBasicBlock::iterator I = (*currentMBB)->begin(), + for(MachineBasicBlock::iterator I = (*currentMBB)->begin(), E = (*currentMBB)->end(); I != E; ++I) { - + MachineInstr *clone = I->clone(); if(clone->getOpcode() == V9::BA && (currentMBB+1 == lastMBB)) { //update branch to side exit @@ -3042,26 +3042,26 @@ void ModuloSchedulingSBPass::writeSideExits(std::vector<std::vector<MachineBasic } } } - + tmp->push_back(clone); - + } - + //Add llvm branch TerminatorInst *newBranch = new BranchInst(sideBB, tmpBB); - + newEp.push_back(tmp); (((MachineBasicBlock*)SB[0])->getParent())->getBasicBlockList().push_back(tmp); newLLVMEp.push_back(tmpBB); - + } side_llvm_epilogues.push_back(newLLVMEp); side_epilogues.push_back(newEp); } - + //Now stich up all the branches - + //Loop over prologues, and if its an inner branch and branches to our original side exit //then have it branch to the appropriate epilogue first (if it exists) for(unsigned P = 0; P < prologues.size(); ++P) { @@ -3072,7 +3072,7 @@ void ModuloSchedulingSBPass::writeSideExits(std::vector<std::vector<MachineBasic //Iterate backwards of machine instructions to find the branch we need to update for(MachineBasicBlock::reverse_iterator mInst = currentMBB->rbegin(), mInstEnd = currentMBB->rend(); mInst != mInstEnd; ++mInst) { MachineOpCode OC = mInst->getOpcode(); - + //If its a branch update its branchto if(TMI->isBranch(OC)) { for(unsigned opNum = 0; opNum < mInst->getNumOperands(); ++opNum) { @@ -3087,11 +3087,11 @@ void ModuloSchedulingSBPass::writeSideExits(std::vector<std::vector<MachineBasic DEBUG(std::cerr << "New Prologue Branch: " << *mInst << "\n"); } } - + //Update llvm branch TerminatorInst *branchVal = ((BasicBlock*) currentMBB->getBasicBlock())->getTerminator(); DEBUG(std::cerr << *branchVal << "\n"); - + for(unsigned i=0; i < branchVal->getNumSuccessors(); ++i) { if(branchVal->getSuccessor(i) == sideExits[mbb]) { DEBUG(std::cerr << "Replacing successor bb\n"); @@ -3117,7 +3117,7 @@ void ModuloSchedulingSBPass::writeSideExits(std::vector<std::vector<MachineBasic //Iterate backwards of machine instructions to find the branch we need to update for(MachineBasicBlock::reverse_iterator mInst = currentMBB->rbegin(), mInstEnd = currentMBB->rend(); mInst != mInstEnd; ++mInst) { MachineOpCode OC = mInst->getOpcode(); - + //If its a branch update its branchto if(TMI->isBranch(OC)) { for(unsigned opNum = 0; opNum < mInst->getNumOperands(); ++opNum) { @@ -3140,7 +3140,7 @@ void ModuloSchedulingSBPass::writeSideExits(std::vector<std::vector<MachineBasic //Update llvm branch TerminatorInst *branchVal = ((BasicBlock*)currentMBB->getBasicBlock())->getTerminator(); DEBUG(std::cerr << *branchVal << "\n"); - + for(unsigned i=0; i < branchVal->getNumSuccessors(); ++i) { if(branchVal->getSuccessor(i) == sideExits[mbb]) { DEBUG(std::cerr << "Replacing successor bb\n"); |