From af00d485a409983639881b4d34f0cd89e1eb4d38 Mon Sep 17 00:00:00 2001 From: "Vikram S. Adve" Date: Mon, 12 Nov 2001 14:18:01 +0000 Subject: [PATCH] Major improvement to how nodes are built for a BB. LLVM instruction is no longer recorded in each node, but BB is. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1262 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/InstrSched/InstrScheduling.cpp | 24 +++--- lib/CodeGen/InstrSched/SchedGraph.cpp | 80 ++++++++++++++----- lib/CodeGen/InstrSched/SchedGraph.h | 6 +- lib/CodeGen/InstrSched/SchedPriorities.cpp | 2 +- .../SparcV9/InstrSched/InstrScheduling.cpp | 24 +++--- lib/Target/SparcV9/InstrSched/SchedGraph.cpp | 80 ++++++++++++++----- lib/Target/SparcV9/InstrSched/SchedGraph.h | 6 +- .../SparcV9/InstrSched/SchedPriorities.cpp | 2 +- 8 files changed, 150 insertions(+), 74 deletions(-) diff --git a/lib/CodeGen/InstrSched/InstrScheduling.cpp b/lib/CodeGen/InstrSched/InstrScheduling.cpp index 7a9a801715d..0ba218da1c7 100644 --- a/lib/CodeGen/InstrSched/InstrScheduling.cpp +++ b/lib/CodeGen/InstrSched/InstrScheduling.cpp @@ -1235,33 +1235,27 @@ ReplaceNopsWithUsefulInstr(SchedulingManager& S, // If not enough useful instructions were found, use the NOPs to // fill delay slots, otherwise, just discard them. // - MachineCodeForVMInstr& termMvec = node->getInstr()->getMachineInstrVec(); - unsigned int firstDelaySlotIdx; - for (unsigned i=0; i < termMvec.size(); ++i) - if (termMvec[i] == brInstr) - { - firstDelaySlotIdx = i+1; - break; - } - assert(firstDelaySlotIdx <= termMvec.size()-1 && - "This sucks! Where's that delay slot instruction?"); + unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1; + MachineCodeForBasicBlock& bbMvec = node->getBB()->getMachineInstrVec(); + assert(bbMvec[firstDelaySlotIdx - 1] == brInstr && + "Incorrect instr. index in basic block for brInstr"); // First find all useful instructions already in the delay slots // and USE THEM. We'll throw away the unused alternatives below // for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i) - if (! mii.isNop(termMvec[i]->getOpCode())) + if (! mii.isNop(bbMvec[i]->getOpCode())) sdelayNodeVec.insert(sdelayNodeVec.begin(), - graph->getGraphNodeForInstr(termMvec[i])); + graph->getGraphNodeForInstr(bbMvec[i])); // Then find the NOPs and keep only as many as are needed. // Put the rest in nopNodeVec to be deleted. for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i) - if (mii.isNop(termMvec[i]->getOpCode())) + if (mii.isNop(bbMvec[i]->getOpCode())) if (sdelayNodeVec.size() < ndelays) - sdelayNodeVec.push_back(graph->getGraphNodeForInstr(termMvec[i])); + sdelayNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i])); else - nopNodeVec.push_back(graph->getGraphNodeForInstr(termMvec[i])); + nopNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i])); assert(sdelayNodeVec.size() >= ndelays); diff --git a/lib/CodeGen/InstrSched/SchedGraph.cpp b/lib/CodeGen/InstrSched/SchedGraph.cpp index 33436be4aa2..0954ed5efb4 100644 --- a/lib/CodeGen/InstrSched/SchedGraph.cpp +++ b/lib/CodeGen/InstrSched/SchedGraph.cpp @@ -138,12 +138,12 @@ void SchedGraphEdge::dump(int indent=0) const { /*ctor*/ SchedGraphNode::SchedGraphNode(unsigned int _nodeId, - const Instruction* _instr, + const BasicBlock* _bb, const MachineInstr* _minstr, int indexInBB, const TargetMachine& target) : nodeId(_nodeId), - instr(_instr), + bb(_bb), minstr(_minstr), origIndexInBB(indexInBB), latency(0) @@ -603,9 +603,6 @@ SchedGraph::addEdgesForInstruction(const MachineInstr& minstr, if (node == NULL) return; - assert(node->getInstr() && "Should be no dummy nodes here!"); - const Instruction* instr = node->getInstr(); - // Add edges for all operands of the machine instruction. // for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++) @@ -778,26 +775,73 @@ SchedGraph::buildNodesforBB(const TargetMachine& target, ValueToDefVecMap& valueToDefVecMap) { const MachineInstrInfo& mii = target.getInstrInfo(); - int origIndexInBB = 0; // Build graph nodes for each VM instruction and gather def/use info. // Do both those together in a single pass over all machine instructions. - for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II) - { - const Instruction *instr = *II; - const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec(); - for (unsigned i=0; i < mvec.size(); i++) - if (! mii.isDummyPhiInstr(mvec[i]->getOpCode())) + const MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec(); + for (unsigned i=0; i < mvec.size(); i++) + if (! mii.isDummyPhiInstr(mvec[i]->getOpCode())) + { + SchedGraphNode* node = new SchedGraphNode(getNumNodes(), bb, + mvec[i], i, target); + this->noteGraphNodeForInstr(mvec[i], node); + + // Remember all register references and value defs + findDefUseInfoAtInstr(target, node, + memNodeVec, regToRefVecMap,valueToDefVecMap); + } + +#undef REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS +#ifdef REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS + // This is a BIG UGLY HACK. IT NEEDS TO BE ELIMINATED. + // Look for copy instructions inserted in this BB due to Phi instructions + // in the successor BBs. + // There MUST be exactly one copy per Phi in successor nodes. + // + for (BasicBlock::succ_const_iterator SI=bb->succ_begin(), SE=bb->succ_end(); + SI != SE; ++SI) + for (BasicBlock::const_iterator PI=(*SI)->begin(), PE=(*SI)->end(); + PI != PE; ++PI) + { + if ((*PI)->getOpcode() != Instruction::PHINode) + break; // No more Phis in this successor + + // Find the incoming value from block bb to block (*SI) + int bbIndex = cast(*PI)->getBasicBlockIndex(bb); + assert(bbIndex >= 0 && "But I know bb is a predecessor of (*SI)?"); + Value* inVal = cast(*PI)->getIncomingValue(bbIndex); + assert(inVal != NULL && "There must be an in-value on every edge"); + + // Find the machine instruction that makes a copy of inval to (*PI). + // This must be in the current basic block (bb). + const MachineCodeForVMInstr& mvec = (*PI)->getMachineInstrVec(); + const MachineInstr* theCopy = NULL; + for (unsigned i=0; i < mvec.size() && theCopy == NULL; i++) + if (! mii.isDummyPhiInstr(mvec[i]->getOpCode())) + // not a Phi: assume this is a copy and examine its operands + for (int o=0, N=(int) mvec[i]->getNumOperands(); o < N; o++) + { + const MachineOperand& mop = mvec[i]->getOperand(o); + if (mvec[i]->operandIsDefined(o)) + assert(mop.getVRegValue() == (*PI) && "dest shd be my Phi"); + else if (mop.getVRegValue() == inVal) + { // found the copy! + theCopy = mvec[i]; + break; + } + } + + // Found the dang instruction. Now create a node and do the rest... + if (theCopy != NULL) { - SchedGraphNode* node = new SchedGraphNode(getNumNodes(), instr, - mvec[i], origIndexInBB++, target); - this->noteGraphNodeForInstr(mvec[i], node); - - // Remember all register references and value defs + SchedGraphNode* node = new SchedGraphNode(getNumNodes(), bb, + theCopy, origIndexInBB++, target); + this->noteGraphNodeForInstr(theCopy, node); findDefUseInfoAtInstr(target, node, memNodeVec, regToRefVecMap,valueToDefVecMap); } - } + } +#endif REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS } diff --git a/lib/CodeGen/InstrSched/SchedGraph.h b/lib/CodeGen/InstrSched/SchedGraph.h index dc5d0059e57..1fec41e4ba8 100644 --- a/lib/CodeGen/InstrSched/SchedGraph.h +++ b/lib/CodeGen/InstrSched/SchedGraph.h @@ -142,7 +142,7 @@ private: class SchedGraphNode: public NonCopyable { private: unsigned int nodeId; - const Instruction* instr; + const BasicBlock* bb; const MachineInstr* minstr; vector inEdges; vector outEdges; @@ -160,13 +160,13 @@ public: // Accessor methods // unsigned int getNodeId () const { return nodeId; } - const Instruction* getInstr () const { return instr; } const MachineInstr* getMachineInstr () const { return minstr; } const MachineOpCode getOpCode () const { return minstr->getOpCode();} int getLatency () const { return latency; } unsigned int getNumInEdges () const { return inEdges.size(); } unsigned int getNumOutEdges () const { return outEdges.size(); } bool isDummyNode () const { return (minstr == NULL); } + const BasicBlock* getBB () const { return bb; } int getOrigIndexInBB() const { return origIndexInBB; } // @@ -203,7 +203,7 @@ private: // disable default constructor and provide a ctor for single-block graphs /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT /*ctor*/ SchedGraphNode (unsigned int _nodeId, - const Instruction* _instr, + const BasicBlock* _bb, const MachineInstr* _minstr, int indexInBB, const TargetMachine& _target); diff --git a/lib/CodeGen/InstrSched/SchedPriorities.cpp b/lib/CodeGen/InstrSched/SchedPriorities.cpp index 7840a250984..31d9f6c5926 100644 --- a/lib/CodeGen/InstrSched/SchedPriorities.cpp +++ b/lib/CodeGen/InstrSched/SchedPriorities.cpp @@ -264,7 +264,7 @@ SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo, // else check if instruction is a last use and save it in the hash_map bool hasLastUse = false; - const BasicBlock* bb = graphNode->getInstr()->getParent(); + const BasicBlock* bb = graphNode->getBB(); const LiveVarSet* liveVars = methodLiveVarInfo.getLiveVarSetBeforeMInst(minstr, bb); diff --git a/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp b/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp index 7a9a801715d..0ba218da1c7 100644 --- a/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp +++ b/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp @@ -1235,33 +1235,27 @@ ReplaceNopsWithUsefulInstr(SchedulingManager& S, // If not enough useful instructions were found, use the NOPs to // fill delay slots, otherwise, just discard them. // - MachineCodeForVMInstr& termMvec = node->getInstr()->getMachineInstrVec(); - unsigned int firstDelaySlotIdx; - for (unsigned i=0; i < termMvec.size(); ++i) - if (termMvec[i] == brInstr) - { - firstDelaySlotIdx = i+1; - break; - } - assert(firstDelaySlotIdx <= termMvec.size()-1 && - "This sucks! Where's that delay slot instruction?"); + unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1; + MachineCodeForBasicBlock& bbMvec = node->getBB()->getMachineInstrVec(); + assert(bbMvec[firstDelaySlotIdx - 1] == brInstr && + "Incorrect instr. index in basic block for brInstr"); // First find all useful instructions already in the delay slots // and USE THEM. We'll throw away the unused alternatives below // for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i) - if (! mii.isNop(termMvec[i]->getOpCode())) + if (! mii.isNop(bbMvec[i]->getOpCode())) sdelayNodeVec.insert(sdelayNodeVec.begin(), - graph->getGraphNodeForInstr(termMvec[i])); + graph->getGraphNodeForInstr(bbMvec[i])); // Then find the NOPs and keep only as many as are needed. // Put the rest in nopNodeVec to be deleted. for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i) - if (mii.isNop(termMvec[i]->getOpCode())) + if (mii.isNop(bbMvec[i]->getOpCode())) if (sdelayNodeVec.size() < ndelays) - sdelayNodeVec.push_back(graph->getGraphNodeForInstr(termMvec[i])); + sdelayNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i])); else - nopNodeVec.push_back(graph->getGraphNodeForInstr(termMvec[i])); + nopNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i])); assert(sdelayNodeVec.size() >= ndelays); diff --git a/lib/Target/SparcV9/InstrSched/SchedGraph.cpp b/lib/Target/SparcV9/InstrSched/SchedGraph.cpp index 33436be4aa2..0954ed5efb4 100644 --- a/lib/Target/SparcV9/InstrSched/SchedGraph.cpp +++ b/lib/Target/SparcV9/InstrSched/SchedGraph.cpp @@ -138,12 +138,12 @@ void SchedGraphEdge::dump(int indent=0) const { /*ctor*/ SchedGraphNode::SchedGraphNode(unsigned int _nodeId, - const Instruction* _instr, + const BasicBlock* _bb, const MachineInstr* _minstr, int indexInBB, const TargetMachine& target) : nodeId(_nodeId), - instr(_instr), + bb(_bb), minstr(_minstr), origIndexInBB(indexInBB), latency(0) @@ -603,9 +603,6 @@ SchedGraph::addEdgesForInstruction(const MachineInstr& minstr, if (node == NULL) return; - assert(node->getInstr() && "Should be no dummy nodes here!"); - const Instruction* instr = node->getInstr(); - // Add edges for all operands of the machine instruction. // for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++) @@ -778,26 +775,73 @@ SchedGraph::buildNodesforBB(const TargetMachine& target, ValueToDefVecMap& valueToDefVecMap) { const MachineInstrInfo& mii = target.getInstrInfo(); - int origIndexInBB = 0; // Build graph nodes for each VM instruction and gather def/use info. // Do both those together in a single pass over all machine instructions. - for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II) - { - const Instruction *instr = *II; - const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec(); - for (unsigned i=0; i < mvec.size(); i++) - if (! mii.isDummyPhiInstr(mvec[i]->getOpCode())) + const MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec(); + for (unsigned i=0; i < mvec.size(); i++) + if (! mii.isDummyPhiInstr(mvec[i]->getOpCode())) + { + SchedGraphNode* node = new SchedGraphNode(getNumNodes(), bb, + mvec[i], i, target); + this->noteGraphNodeForInstr(mvec[i], node); + + // Remember all register references and value defs + findDefUseInfoAtInstr(target, node, + memNodeVec, regToRefVecMap,valueToDefVecMap); + } + +#undef REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS +#ifdef REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS + // This is a BIG UGLY HACK. IT NEEDS TO BE ELIMINATED. + // Look for copy instructions inserted in this BB due to Phi instructions + // in the successor BBs. + // There MUST be exactly one copy per Phi in successor nodes. + // + for (BasicBlock::succ_const_iterator SI=bb->succ_begin(), SE=bb->succ_end(); + SI != SE; ++SI) + for (BasicBlock::const_iterator PI=(*SI)->begin(), PE=(*SI)->end(); + PI != PE; ++PI) + { + if ((*PI)->getOpcode() != Instruction::PHINode) + break; // No more Phis in this successor + + // Find the incoming value from block bb to block (*SI) + int bbIndex = cast(*PI)->getBasicBlockIndex(bb); + assert(bbIndex >= 0 && "But I know bb is a predecessor of (*SI)?"); + Value* inVal = cast(*PI)->getIncomingValue(bbIndex); + assert(inVal != NULL && "There must be an in-value on every edge"); + + // Find the machine instruction that makes a copy of inval to (*PI). + // This must be in the current basic block (bb). + const MachineCodeForVMInstr& mvec = (*PI)->getMachineInstrVec(); + const MachineInstr* theCopy = NULL; + for (unsigned i=0; i < mvec.size() && theCopy == NULL; i++) + if (! mii.isDummyPhiInstr(mvec[i]->getOpCode())) + // not a Phi: assume this is a copy and examine its operands + for (int o=0, N=(int) mvec[i]->getNumOperands(); o < N; o++) + { + const MachineOperand& mop = mvec[i]->getOperand(o); + if (mvec[i]->operandIsDefined(o)) + assert(mop.getVRegValue() == (*PI) && "dest shd be my Phi"); + else if (mop.getVRegValue() == inVal) + { // found the copy! + theCopy = mvec[i]; + break; + } + } + + // Found the dang instruction. Now create a node and do the rest... + if (theCopy != NULL) { - SchedGraphNode* node = new SchedGraphNode(getNumNodes(), instr, - mvec[i], origIndexInBB++, target); - this->noteGraphNodeForInstr(mvec[i], node); - - // Remember all register references and value defs + SchedGraphNode* node = new SchedGraphNode(getNumNodes(), bb, + theCopy, origIndexInBB++, target); + this->noteGraphNodeForInstr(theCopy, node); findDefUseInfoAtInstr(target, node, memNodeVec, regToRefVecMap,valueToDefVecMap); } - } + } +#endif REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS } diff --git a/lib/Target/SparcV9/InstrSched/SchedGraph.h b/lib/Target/SparcV9/InstrSched/SchedGraph.h index dc5d0059e57..1fec41e4ba8 100644 --- a/lib/Target/SparcV9/InstrSched/SchedGraph.h +++ b/lib/Target/SparcV9/InstrSched/SchedGraph.h @@ -142,7 +142,7 @@ private: class SchedGraphNode: public NonCopyable { private: unsigned int nodeId; - const Instruction* instr; + const BasicBlock* bb; const MachineInstr* minstr; vector inEdges; vector outEdges; @@ -160,13 +160,13 @@ public: // Accessor methods // unsigned int getNodeId () const { return nodeId; } - const Instruction* getInstr () const { return instr; } const MachineInstr* getMachineInstr () const { return minstr; } const MachineOpCode getOpCode () const { return minstr->getOpCode();} int getLatency () const { return latency; } unsigned int getNumInEdges () const { return inEdges.size(); } unsigned int getNumOutEdges () const { return outEdges.size(); } bool isDummyNode () const { return (minstr == NULL); } + const BasicBlock* getBB () const { return bb; } int getOrigIndexInBB() const { return origIndexInBB; } // @@ -203,7 +203,7 @@ private: // disable default constructor and provide a ctor for single-block graphs /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT /*ctor*/ SchedGraphNode (unsigned int _nodeId, - const Instruction* _instr, + const BasicBlock* _bb, const MachineInstr* _minstr, int indexInBB, const TargetMachine& _target); diff --git a/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp index 7840a250984..31d9f6c5926 100644 --- a/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp +++ b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp @@ -264,7 +264,7 @@ SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo, // else check if instruction is a last use and save it in the hash_map bool hasLastUse = false; - const BasicBlock* bb = graphNode->getInstr()->getParent(); + const BasicBlock* bb = graphNode->getBB(); const LiveVarSet* liveVars = methodLiveVarInfo.getLiveVarSetBeforeMInst(minstr, bb); -- 2.34.1