diff options
author | Dan Gohman <gohman@apple.com> | 2008-11-13 23:24:17 +0000 |
---|---|---|
committer | Dan Gohman <gohman@apple.com> | 2008-11-13 23:24:17 +0000 |
commit | d23e0f81bc76902052e9198cad3a0d87a412a632 (patch) | |
tree | ad74c00b8471cdc6ebaa7fc968c9be16848203de | |
parent | e4f309e5823e4cbd5f5b123e348f2ef204f67c11 (diff) | |
download | external_llvm-d23e0f81bc76902052e9198cad3a0d87a412a632.zip external_llvm-d23e0f81bc76902052e9198cad3a0d87a412a632.tar.gz external_llvm-d23e0f81bc76902052e9198cad3a0d87a412a632.tar.bz2 |
Remove the FlaggedNodes member from SUnit. Instead of requiring each SUnit
to carry a SmallVector of flagged nodes, just calculate the flagged nodes
dynamically when they are needed.
The local-liveness change is due to a trivial scheduling change where
the scheduler arbitrary decision differently.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59273 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/CodeGen/ScheduleDAG.h | 1 | ||||
-rw-r--r-- | include/llvm/CodeGen/SelectionDAGNodes.h | 9 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAG.cpp | 56 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp | 9 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp | 7 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp | 8 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp | 9 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp | 19 | ||||
-rw-r--r-- | test/CodeGen/X86/local-liveness.ll | 2 |
9 files changed, 59 insertions, 61 deletions
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 890dc0f..2d4592b 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -95,7 +95,6 @@ namespace llvm { private: SDNode *Node; // Representative node. public: - SmallVector<SDNode*,4> FlaggedNodes;// All nodes flagged to Node. SUnit *OrigNode; // If not this, the node from which // this node was cloned. diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 94bb2ae..839db7d 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -1308,6 +1308,15 @@ public: SDVTList X = { ValueList, NumValues }; return X; }; + + /// getFlaggedNode - If this node has a flag operand, return the node + /// to which the flag operand points. Otherwise return NULL. + SDNode *getFlaggedNode() const { + if (getNumOperands() != 0 && + getOperand(getNumOperands()-1).getValueType() == MVT::Flag) + return getOperand(getNumOperands()-1).getNode(); + return 0; + } /// getNumValues - Return the number of values defined/returned by this /// operator. diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp index 7dd8f50..6d6b9c7 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp @@ -60,7 +60,6 @@ static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, SUnit *ScheduleDAG::Clone(SUnit *Old) { SUnit *SU = NewSUnit(Old->getNode()); SU->OrigNode = Old->OrigNode; - SU->FlaggedNodes = Old->FlaggedNodes; SU->Latency = Old->Latency; SU->isTwoAddress = Old->isTwoAddress; SU->isCommutable = Old->isCommutable; @@ -99,23 +98,19 @@ void ScheduleDAG::BuildSchedUnits() { // nodes. Nodes can have at most one flag input and one flag output. Flags // are required the be the last operand and result of a node. - // Scan up, adding flagged preds to FlaggedNodes. + // Scan up to find flagged preds. SDNode *N = NI; if (N->getNumOperands() && N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { do { N = N->getOperand(N->getNumOperands()-1).getNode(); - NodeSUnit->FlaggedNodes.push_back(N); assert(N->getNodeId() == -1 && "Node already inserted!"); N->setNodeId(NodeSUnit->NodeNum); } while (N->getNumOperands() && N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag); - std::reverse(NodeSUnit->FlaggedNodes.begin(), - NodeSUnit->FlaggedNodes.end()); } - // Scan down, adding this node and any flagged succs to FlaggedNodes if they - // have a user of the flag operand. + // Scan down to find any flagged succs. N = NI; while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { SDValue FlagVal(N, N->getNumValues()-1); @@ -126,7 +121,6 @@ void ScheduleDAG::BuildSchedUnits() { UI != E; ++UI) if (FlagVal.isOperandOf(*UI)) { HasFlagUse = true; - NodeSUnit->FlaggedNodes.push_back(N); assert(N->getNodeId() == -1 && "Node already inserted!"); N->setNodeId(NodeSUnit->NodeNum); N = *UI; @@ -135,8 +129,9 @@ void ScheduleDAG::BuildSchedUnits() { if (!HasFlagUse) break; } - // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node. - // Update the SUnit + // If there are flag operands involved, N is now the bottom-most node + // of the sequence of nodes that are flagged together. + // Update the SUnit. NodeSUnit->setNode(N); assert(N->getNodeId() == -1 && "Node already inserted!"); N->setNodeId(NodeSUnit->NodeNum); @@ -163,11 +158,7 @@ void ScheduleDAG::BuildSchedUnits() { } // Find all predecessors and successors of the group. - // Temporarily add N to make code simpler. - SU->FlaggedNodes.push_back(MainNode); - - for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) { - SDNode *N = SU->FlaggedNodes[n]; + for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).getImplicitDefs() && CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs()) @@ -191,9 +182,6 @@ void ScheduleDAG::BuildSchedUnits() { SU->addPred(OpSU, isChain, false, PhysReg, Cost); } } - - // Remove MainNode from FlaggedNodes again. - SU->FlaggedNodes.pop_back(); } } @@ -209,17 +197,9 @@ void ScheduleDAG::ComputeLatency(SUnit *SU) { } SU->Latency = 0; - if (SU->getNode()->isMachineOpcode()) { - unsigned SchedClass = TII->get(SU->getNode()->getMachineOpcode()).getSchedClass(); - const InstrStage *S = InstrItins.begin(SchedClass); - const InstrStage *E = InstrItins.end(SchedClass); - for (; S != E; ++S) - SU->Latency += S->Cycles; - } - for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i) { - SDNode *FNode = SU->FlaggedNodes[i]; - if (FNode->isMachineOpcode()) { - unsigned SchedClass = TII->get(FNode->getMachineOpcode()).getSchedClass(); + for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { + if (N->isMachineOpcode()) { + unsigned SchedClass = TII->get(N->getMachineOpcode()).getSchedClass(); const InstrStage *S = InstrItins.begin(SchedClass); const InstrStage *E = InstrItins.end(SchedClass); for (; S != E; ++S) @@ -397,17 +377,19 @@ void ScheduleDAG::Run() { /// a group of nodes flagged together. void SUnit::dump(const SelectionDAG *G) const { cerr << "SU(" << NodeNum << "): "; - if (Node) - Node->dump(G); + if (getNode()) + getNode()->dump(G); else cerr << "CROSS RC COPY "; cerr << "\n"; - if (FlaggedNodes.size() != 0) { - for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) { - cerr << " "; - FlaggedNodes[i]->dump(G); - cerr << "\n"; - } + SmallVector<SDNode *, 4> FlaggedNodes; + for (SDNode *N = getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) + FlaggedNodes.push_back(N); + while (!FlaggedNodes.empty()) { + cerr << " "; + FlaggedNodes.back()->dump(G); + cerr << "\n"; + FlaggedNodes.pop_back(); } } diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp index 7d5822f..2c40d97 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp @@ -684,8 +684,13 @@ MachineBasicBlock *ScheduleDAG::EmitSchedule() { EmitNoop(); continue; } - for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; ++j) - EmitNode(SU->FlaggedNodes[j], SU->OrigNode != SU, VRBaseMap); + SmallVector<SDNode *, 4> FlaggedNodes; + for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) + FlaggedNodes.push_back(N); + while (!FlaggedNodes.empty()) { + EmitNode(FlaggedNodes.back(), SU->OrigNode != SU, VRBaseMap); + FlaggedNodes.pop_back(); + } if (!SU->getNode()) EmitCrossRCCopy(SU, CopyVRBaseMap); else diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp index 51a784e..ae20774 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp @@ -221,7 +221,7 @@ bool ScheduleDAGFast::RemovePred(SUnit *M, SUnit *N, /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled /// successors to the newly created node. SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { - if (SU->FlaggedNodes.size()) + if (SU->getNode()->getFlaggedNode()) return NULL; SDNode *N = SU->getNode(); @@ -485,9 +485,8 @@ bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU, } } - for (unsigned i = 0, e = SU->FlaggedNodes.size()+1; i != e; ++i) { - SDNode *Node = (i == 0) ? SU->getNode() : SU->FlaggedNodes[i-1]; - if (!Node || !Node->isMachineOpcode()) + for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) { + if (!Node->isMachineOpcode()) continue; const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode()); if (!TID.ImplicitDefs) diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index 8921545..14042ed 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp @@ -205,9 +205,11 @@ void ScheduleDAGList::ListScheduleTopDown() { // If this is a pseudo op, like copyfromreg, look to see if there is a // real target node flagged to it. If so, use the target node. - for (unsigned i = 0, e = CurSUnit->FlaggedNodes.size(); - !FoundNode->isMachineOpcode() && i != e; ++i) - FoundNode = CurSUnit->FlaggedNodes[i]; + while (!FoundNode->isMachineOpcode()) { + SDNode *N = FoundNode->getFlaggedNode(); + if (!N) break; + FoundNode = N; + } HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode); if (HT == HazardRecognizer::NoHazard) { diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp index 15fffdf..15ba266 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp @@ -626,7 +626,7 @@ void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle, /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled /// successors to the newly created node. SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) { - if (SU->FlaggedNodes.size()) + if (SU->getNode()->getFlaggedNode()) return NULL; SDNode *N = SU->getNode(); @@ -903,9 +903,8 @@ bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, } } - for (unsigned i = 0, e = SU->FlaggedNodes.size()+1; i != e; ++i) { - SDNode *Node = (i == 0) ? SU->getNode() : SU->FlaggedNodes[i-1]; - if (!Node || !Node->isMachineOpcode()) + for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) { + if (!Node->isMachineOpcode()) continue; const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode()); if (!TID.ImplicitDefs) @@ -1736,7 +1735,7 @@ void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() { continue; SDNode *Node = SU->getNode(); - if (!Node || !Node->isMachineOpcode() || SU->FlaggedNodes.size() > 0) + if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode()) continue; unsigned Opc = Node->getMachineOpcode(); diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp index 1f45729..a356b6d 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp @@ -433,16 +433,19 @@ std::string DOTGraphTraits<ScheduleDAG*>::getNodeLabel(const SUnit *SU, const ScheduleDAG *G) { std::string Op; - for (unsigned i = 0; i < SU->FlaggedNodes.size(); ++i) { - Op += DOTGraphTraits<SelectionDAG*>::getNodeLabel(SU->FlaggedNodes[i], - G->DAG) + "\n"; + if (!SU->getNode()) + Op = "<CROSS RC COPY>"; + else { + SmallVector<SDNode *, 4> FlaggedNodes; + for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) + FlaggedNodes.push_back(N); + while (!FlaggedNodes.empty()) { + Op += DOTGraphTraits<SelectionDAG*>::getNodeLabel(FlaggedNodes.back(), + G->DAG) + "\n"; + FlaggedNodes.pop_back(); + } } - if (SU->getNode()) - Op += DOTGraphTraits<SelectionDAG*>::getNodeLabel(SU->getNode(), G->DAG); - else - Op += "<CROSS RC COPY>"; - return Op; } diff --git a/test/CodeGen/X86/local-liveness.ll b/test/CodeGen/X86/local-liveness.ll index f176ec2..18d999b 100644 --- a/test/CodeGen/X86/local-liveness.ll +++ b/test/CodeGen/X86/local-liveness.ll @@ -1,4 +1,4 @@ -; RUN: llvm-as < %s | llc -march=x86 -regalloc=local | grep {subl %eax, %esi} +; RUN: llvm-as < %s | llc -march=x86 -regalloc=local | grep {subl %eax, %edx} ; Local regalloc shouldn't assume that both the uses of the ; sub instruction are kills, because one of them is tied |