From ac6e2dbf525a7628d58c73cc853520650353e66e Mon Sep 17 00:00:00 2001 From: Tanya Lattner Date: Tue, 5 Apr 2005 16:36:44 +0000 Subject: [PATCH] Updated to use dep analyzer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21097 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../SparcV9/ModuloScheduling/MSchedGraph.cpp | 122 +++--------- .../SparcV9/ModuloScheduling/MSchedGraph.h | 8 +- .../ModuloScheduling/ModuloScheduling.cpp | 175 +++++++++--------- .../ModuloScheduling/ModuloScheduling.h | 2 - 4 files changed, 113 insertions(+), 194 deletions(-) diff --git a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp index f60d3d5f613..dc5c3b0570c 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.cpp @@ -141,8 +141,8 @@ void MSchedGraph::deleteNode(MSchedGraphNode *node) { //Create a graph for a machine block. The ignoreInstrs map is so that 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, AliasAnalysis &AA, - TargetData &TD, std::map &ignoreInstrs, +MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ, + std::map &ignoreInstrs, DependenceAnalyzer &DA, std::map &machineTollvm ) : BB(bb), Target(targ) { @@ -153,7 +153,7 @@ MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ, //DEBUG(std::cerr << "Constructing graph for " << bb << "\n"); //Create nodes and edges for this BB - buildNodesAndEdges(AA, TD, ignoreInstrs, DA, machineTollvm); + buildNodesAndEdges(ignoreInstrs, DA, machineTollvm); //Experimental! //addBranchEdges(); @@ -273,8 +273,7 @@ void MSchedGraph::addBranchEdges() { //Add edges between the nodes -void MSchedGraph::buildNodesAndEdges(AliasAnalysis &AA, TargetData &TD, - std::map &ignoreInstrs, +void MSchedGraph::buildNodesAndEdges(std::map &ignoreInstrs, DependenceAnalyzer &DA, std::map &machineTollvm) { @@ -411,7 +410,7 @@ void MSchedGraph::buildNodesAndEdges(AliasAnalysis &AA, TargetData &TD, } - addMemEdges(memInstructions, AA, TD, DA, machineTollvm); + addMemEdges(memInstructions, DA, machineTollvm); addMachRegEdges(regNumtoNodeMap); //Finally deal with PHI Nodes and Value* @@ -590,8 +589,7 @@ void MSchedGraph::addMachRegEdges(std::map >& //Add edges between all loads and stores //Can be less strict with alias analysis and data dependence analysis. -void MSchedGraph::addMemEdges(const std::vector& memInst, AliasAnalysis &AA, - TargetData &TD, DependenceAnalyzer &DA, +void MSchedGraph::addMemEdges(const std::vector& memInst, DependenceAnalyzer &DA, std::map &machineTollvm) { //Get Target machine instruction info @@ -610,101 +608,23 @@ void MSchedGraph::addMemEdges(const std::vector& memInst, Alia for(unsigned destIndex = srcIndex + 1; destIndex < memInst.size(); ++destIndex) { MachineInstr *destInst = (MachineInstr*) memInst[destIndex]->getInst(); - bool malias = false; - + DEBUG(std::cerr << "MInst1: " << *srcInst << "\n"); DEBUG(std::cerr << "Inst1: " << *machineTollvm[srcInst] << "\n"); DEBUG(std::cerr << "MInst2: " << *destInst << "\n"); DEBUG(std::cerr << "Inst2: " << *machineTollvm[destInst] << "\n"); - //Add Anti dependencies (store after load) - //Source is a Load - if(TMI->isLoad(srcNodeOpCode)) { - - //Destination is a store - if(TMI->isStore(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; - else - malias = true; - if(mOp2.hasAllocatedReg()) - if(mOp2.getReg() == SparcV9::g0) - continue; - else - malias = true; - - //compare to DA - DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst], machineTollvm[destInst]); - - //Only add the edge if we can't verify that they do not alias - if(malias || AA.alias(mOp2.getVRegValue(), - (unsigned)TD.getTypeSize(mOp2.getVRegValue()->getType()), - mOp.getVRegValue(), - (unsigned)TD.getTypeSize(mOp.getVRegValue()->getType())) - != AliasAnalysis::NoAlias) { - - //Add edge from load to store - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, - MSchedGraphEdge::AntiDep); - - assert(dr.dependences.size() == 1 && "Expected at least one dependence\n"); - - } - else - assert(dr.dependences.size() == 0 && "Expected no dependence\n"); - } - } - - //If source is a store, add output and true dependencies - if(TMI->isStore(srcNodeOpCode)) { - - //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; - else - malias = true; - if(mOp2.hasAllocatedReg()) - if(mOp2.getReg() == SparcV9::g0) - continue; - else - malias = true; - - //compare to DA - DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst], machineTollvm[destInst]); - - //Only add the edge if we can't verify that they do not alias - if(malias || AA.alias(mOp2.getVRegValue(), - (unsigned)TD.getTypeSize(mOp2.getVRegValue()->getType()), - mOp.getVRegValue(), - (unsigned)TD.getTypeSize(mOp.getVRegValue()->getType())) - != AliasAnalysis::NoAlias) { - - if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, - MSchedGraphEdge::OutputDep); - else - memInst[srcIndex]->addOutEdge(memInst[destIndex], - MSchedGraphEdge::MemoryDep, - MSchedGraphEdge::TrueDep); - assert(dr.dependences.size() == 1 && "Expected at least one dependence\n"); + DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst], machineTollvm[destInst]); - } + for(std::vector::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, + d->getDepType(), d->getIteDiff()); - else - assert(dr.dependences.size() == 0 && "Expected no dependence\n"); } + } //All instructions before the src in execution order have an iteration delay of 1 @@ -732,16 +652,16 @@ void MSchedGraph::addMemEdges(const std::vector& memInst, Alia malias = true; //Only add the edge if we can't verify that they do not alias - if(AA.alias(mOp2.getVRegValue(), + /*if(AA.alias(mOp2.getVRegValue(), (unsigned)TD.getTypeSize(mOp2.getVRegValue()->getType()), mOp.getVRegValue(), (unsigned)TD.getTypeSize(mOp.getVRegValue()->getType())) - != AliasAnalysis::NoAlias) { + != AliasAnalysis::NoAlias) {*/ if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) memInst[srcIndex]->addOutEdge(memInst[destIndex], MSchedGraphEdge::MemoryDep, MSchedGraphEdge::AntiDep, 1); - } + //} } if(TMI->isStore(srcNodeOpCode)) { @@ -761,11 +681,11 @@ void MSchedGraph::addMemEdges(const std::vector& memInst, Alia malias = true; //Only add the edge if we can't verify that they do not alias - if(AA.alias(mOp2.getVRegValue(), + /*if(AA.alias(mOp2.getVRegValue(), (unsigned)TD.getTypeSize(mOp2.getVRegValue()->getType()), mOp.getVRegValue(), (unsigned)TD.getTypeSize(mOp.getVRegValue()->getType())) - != AliasAnalysis::NoAlias) { + != AliasAnalysis::NoAlias) {*/ if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode())) memInst[srcIndex]->addOutEdge(memInst[destIndex], @@ -775,7 +695,7 @@ void MSchedGraph::addMemEdges(const std::vector& memInst, Alia memInst[srcIndex]->addOutEdge(memInst[destIndex], MSchedGraphEdge::MemoryDep, MSchedGraphEdge::TrueDep, 1); - } + //} } } diff --git a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h index bcc78d0df33..070c928f03a 100644 --- a/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h +++ b/lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h @@ -241,19 +241,19 @@ namespace llvm { //Add Nodes and Edges to this graph for our BB typedef std::pair OpIndexNodePair; - void buildNodesAndEdges(AliasAnalysis &AA, TargetData &TD, std::map &ignoreInstrs, DependenceAnalyzer &DA, std::map &machineTollvm); + void buildNodesAndEdges(std::map &ignoreInstrs, DependenceAnalyzer &DA, std::map &machineTollvm); void addValueEdges(std::vector &NodesInMap, MSchedGraphNode *node, bool nodeIsUse, bool nodeIsDef, std::vector &phiInstrs, int diff=0); void addMachRegEdges(std::map >& regNumtoNodeMap); - void addMemEdges(const std::vector& memInst, AliasAnalysis &AA, TargetData &TD, + void addMemEdges(const std::vector& memInst, DependenceAnalyzer &DA, std::map &machineTollvm); void addBranchEdges(); public: - MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ, AliasAnalysis &AA, - TargetData &TD, std::map &ignoreInstrs, + MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ, + std::map &ignoreInstrs, DependenceAnalyzer &DA, std::map &machineTollvm); //Copy constructor with maps to link old nodes to new nodes diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp index 6adb5f5225d..f5faae5e31b 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp @@ -153,8 +153,7 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) { MachineFunction &MF = MachineFunction::get(&F); DependenceAnalyzer &DA = getAnalysis(); - AliasAnalysis &AA = getAnalysis(); - TargetData &TD = getAnalysis(); + //Worklist std::vector Worklist; @@ -192,7 +191,7 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) { continue; } - MSchedGraph *MSG = new MSchedGraph(*BI, target, AA, TD, indVarInstrs[*BI], DA, machineTollvm[*BI]); + MSchedGraph *MSG = new MSchedGraph(*BI, target, indVarInstrs[*BI], DA, machineTollvm[*BI]); //Write Graph out to file DEBUG(WriteGraphToFile(std::cerr, F.getName(), MSG)); @@ -260,18 +259,17 @@ bool ModuloSchedulingPass::runOnFunction(Function &F) { //Final scheduling step is to reconstruct the loop only if we actual have //stage > 0 - if(schedule.getMaxStage() != 0 && haveSched) { + if(haveSched) { reconstructLoop(*BI); ++MSLoops; Changed = true; - } - else { - if(!haveSched) - ++NoSched; - else + + if(schedule.getMaxStage() == 0) ++SameStage; - DEBUG(std::cerr << "Max stage is 0, so no change in loop or reached cap\n"); } + else + ++NoSched; + //Clear out our maps for the next basic block that is processed nodeToAttributesMap.clear(); partialOrder.clear(); @@ -437,6 +435,12 @@ bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) { //Convert list of LLVM Instructions to list of Machine instructions std::map mIndVar; for(std::set::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 + if(isa(*N)) + return false; + MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(*N); for (unsigned j = 0; j < tempMvec.size(); j++) { MachineOpCode OC = (tempMvec[j])->getOpcode(); @@ -449,8 +453,8 @@ bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) { } } - //Must have some guts to the loop body - if(mIndVar.size() >= (BI->size()-2)) + //Must have some guts to the loop body (more then 1 instr, dont count nops in size) + if(mIndVar.size() >= (BI->size()-3)) return false; //Put into a map for future access @@ -1332,17 +1336,8 @@ void ModuloSchedulingPass::computePartialOrder() { if(PO->count(I->first)) found = true; } - if(!found) { - if(I->first->isBranch() && !I->first->hasPredecessors()) { - if(std::find(branches.begin(), branches.end(), I->first) == branches.end()) - branches.push_back(I->first); - } - else { - lastNodes.insert(I->first); - if(!I->first->hasPredecessors()) - noPredNodes.insert(I->first); - } - } + if(!found) + lastNodes.insert(I->first); } //For each node w/out preds, see if there is a path to one of the @@ -1360,40 +1355,29 @@ void ModuloSchedulingPass::computePartialOrder() { //Break up remaining nodes that are not in the partial order ///into their connected compoenents - /*while(lastNodes.size() > 0) { + while(lastNodes.size() > 0) { std::set ccSet; connectedComponentSet(*(lastNodes.begin()),ccSet, lastNodes); if(ccSet.size() > 0) partialOrder.push_back(ccSet); - }*/ - if(lastNodes.size() > 0) - partialOrder.push_back(lastNodes); - - + } + + //Clean up branches by putting them in final order - std::map branchOrder; - for(std::vector::iterator I = branches.begin(), E = branches.end(); I != E; ++I) - branchOrder[(*I)->getIndex()] = *I; - - for(std::map::reverse_iterator I = branchOrder.rbegin(), E = branchOrder.rend(); I != E; ++I) - FinalNodeOrder.push_back(I->second); - + assert(branches.size() == 0 && "We should not have any branches in our graph"); } void ModuloSchedulingPass::connectedComponentSet(MSchedGraphNode *node, std::set &ccSet, std::set &lastNodes) { //Add to final set -if( !ccSet.count(node) && lastNodes.count(node)) { + if( !ccSet.count(node) && lastNodes.count(node)) { lastNodes.erase(node); - if(node->isBranch() && !node->hasPredecessors()) - FinalNodeOrder.push_back(node); - else - ccSet.insert(node); + ccSet.insert(node); } else return; - + //Loop over successors and recurse if we have not seen this node before for(MSchedGraphNode::succ_iterator node_succ = node->succ_begin(), end=node->succ_end(); node_succ != end; ++node_succ) { connectedComponentSet(*node_succ, ccSet, lastNodes); @@ -2552,7 +2536,8 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) { //Write prologue - writePrologues(prologues, BB, llvm_prologues, valuesToSave, newValues, newValLocation); + if(schedule.getMaxStage() != 0) + writePrologues(prologues, BB, llvm_prologues, valuesToSave, newValues, newValLocation); //Print out epilogues and prologue DEBUG(for(std::vector::iterator I = prologues.begin(), E = prologues.end(); @@ -2571,7 +2556,8 @@ void ModuloSchedulingPass::reconstructLoop(MachineBasicBlock *BB) { std::vector llvm_epilogues; //Write epilogues - writeEpilogues(epilogues, BB, llvm_epilogues, valuesToSave, newValues, newValLocation, kernelPHIs); + if(schedule.getMaxStage() != 0) + writeEpilogues(epilogues, BB, llvm_epilogues, valuesToSave, newValues, newValLocation, kernelPHIs); //Fix our branches @@ -2607,51 +2593,53 @@ void ModuloSchedulingPass::fixBranches(std::vector &prologu const TargetInstrInfo *TMI = target.getInstrInfo(); - //Fix prologue branches - for(unsigned I = 0; I < prologues.size(); ++I) { - - //Find terminator since getFirstTerminator does not work! - for(MachineBasicBlock::reverse_iterator mInst = prologues[I]->rbegin(), mInstEnd = prologues[I]->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) { - MachineOperand &mOp = mInst->getOperand(opNum); - if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) { - //Check if we are branching to the kernel, if not branch to epilogue - if(mOp.getVRegValue() == BB->getBasicBlock()) { - if(I == prologues.size()-1) - mOp.setValueReg(llvmKernelBB); - else - mOp.setValueReg(llvm_prologues[I+1]); - } - else { - mOp.setValueReg(llvm_epilogues[(llvm_epilogues.size()-1-I)]); + if(schedule.getMaxStage() != 0) { + //Fix prologue branches + for(unsigned I = 0; I < prologues.size(); ++I) { + + //Find terminator since getFirstTerminator does not work! + for(MachineBasicBlock::reverse_iterator mInst = prologues[I]->rbegin(), mInstEnd = prologues[I]->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) { + MachineOperand &mOp = mInst->getOperand(opNum); + if (mOp.getType() == MachineOperand::MO_PCRelativeDisp) { + //Check if we are branching to the kernel, if not branch to epilogue + if(mOp.getVRegValue() == BB->getBasicBlock()) { + if(I == prologues.size()-1) + mOp.setValueReg(llvmKernelBB); + else + mOp.setValueReg(llvm_prologues[I+1]); + } + else { + mOp.setValueReg(llvm_epilogues[(llvm_epilogues.size()-1-I)]); + } } } - } - DEBUG(std::cerr << "New Prologue Branch: " << *mInst << "\n"); + DEBUG(std::cerr << "New Prologue Branch: " << *mInst << "\n"); + } } - } - //Update llvm basic block with our new branch instr - DEBUG(std::cerr << BB->getBasicBlock()->getTerminator() << "\n"); - const BranchInst *branchVal = dyn_cast(BB->getBasicBlock()->getTerminator()); + //Update llvm basic block with our new branch instr + DEBUG(std::cerr << BB->getBasicBlock()->getTerminator() << "\n"); + const BranchInst *branchVal = dyn_cast(BB->getBasicBlock()->getTerminator()); - if(I == prologues.size()-1) { - TerminatorInst *newBranch = new BranchInst(llvmKernelBB, - llvm_epilogues[(llvm_epilogues.size()-1-I)], - branchVal->getCondition(), - llvm_prologues[I]); - } - else - TerminatorInst *newBranch = new BranchInst(llvm_prologues[I+1], - llvm_epilogues[(llvm_epilogues.size()-1-I)], - branchVal->getCondition(), - llvm_prologues[I]); + if(I == prologues.size()-1) { + TerminatorInst *newBranch = new BranchInst(llvmKernelBB, + llvm_epilogues[(llvm_epilogues.size()-1-I)], + branchVal->getCondition(), + llvm_prologues[I]); + } + else + TerminatorInst *newBranch = new BranchInst(llvm_prologues[I+1], + llvm_epilogues[(llvm_epilogues.size()-1-I)], + branchVal->getCondition(), + llvm_prologues[I]); + } } Value *origBranchExit = 0; @@ -2673,6 +2661,8 @@ void ModuloSchedulingPass::fixBranches(std::vector &prologu origBranchExit = mOp.getVRegValue(); mOp.setValueReg(llvm_epilogues[0]); } + else + origBranchExit = mOp.getVRegValue(); } } } @@ -2681,14 +2671,24 @@ void ModuloSchedulingPass::fixBranches(std::vector &prologu //Update kernelLLVM branches const BranchInst *branchVal = dyn_cast(BB->getBasicBlock()->getTerminator()); - assert(llvm_epilogues.size() != 0 && "We must have epilogues!"); + assert(origBranchExit != 0 && "We must have the original bb the kernel exits to!"); - TerminatorInst *newBranch = new BranchInst(llvmKernelBB, - llvm_epilogues[0], - branchVal->getCondition(), - llvmKernelBB); - + if(epilogues.size() > 0) { + TerminatorInst *newBranch = new BranchInst(llvmKernelBB, + llvm_epilogues[0], + branchVal->getCondition(), + llvmKernelBB); + } + else { + BasicBlock *origBBExit = dyn_cast(origBranchExit); + assert(origBBExit !=0 && "Original exit basic block must be set"); + TerminatorInst *newBranch = new BranchInst(llvmKernelBB, + origBBExit, + branchVal->getCondition(), + llvmKernelBB); + } + if(schedule.getMaxStage() != 0) { //Lastly add unconditional branches for the epilogues for(unsigned I = 0; I < epilogues.size(); ++I) { @@ -2720,6 +2720,7 @@ void ModuloSchedulingPass::fixBranches(std::vector &prologu BuildMI(epilogues[I], V9::NOP, 0); } + } //FIX UP Machine BB entry!! //We are looking at the predecesor of our loop basic block and we want to change its ba instruction diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h index b2dba19cb21..40d86f0fabf 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h @@ -149,8 +149,6 @@ namespace llvm { // getAnalysisUsage virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); - AU.addRequired(); - AU.addRequired(); } }; -- 2.34.1