From 5b07eeb24a03546ffcd2677a6be7f4d321dc03f1 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Fri, 25 Jan 2013 06:02:44 +0000 Subject: [PATCH] SchedDFS: Initial support for nested subtrees. This is mostly refactoring, along with adding an instruction count within the subtrees and ensuring we only look at data edges. llvm-svn: 173420 --- llvm/include/llvm/CodeGen/ScheduleDFS.h | 22 +++++-- llvm/lib/CodeGen/ScheduleDAGInstrs.cpp | 110 +++++++++++++++++++++----------- 2 files changed, 90 insertions(+), 42 deletions(-) diff --git a/llvm/include/llvm/CodeGen/ScheduleDFS.h b/llvm/include/llvm/CodeGen/ScheduleDFS.h index faabc7b..54b2232 100644 --- a/llvm/include/llvm/CodeGen/ScheduleDFS.h +++ b/llvm/include/llvm/CodeGen/ScheduleDFS.h @@ -27,6 +27,9 @@ class SUnit; /// \brief Represent the ILP of the subDAG rooted at a DAG node. /// +/// ILPValues summarize the DAG subtree rooted at each node. ILPValues are +/// valid for all nodes regardless of their subtree membership. +/// /// When computed using bottom-up DFS, this metric assumes that the DAG is a /// forest of trees with roots at the bottom of the schedule branching upward. struct ILPValue { @@ -62,19 +65,23 @@ struct ILPValue { }; /// \brief Compute the values of each DAG node for various metrics during DFS. -/// -/// ILPValues summarize the DAG subtree rooted at each node up to -/// SubtreeLimit. ILPValues are also valid for interior nodes of a subtree, not -/// just the root. class SchedDFSResult { friend class SchedDFSImpl; + static const unsigned InvalidSubtreeID = ~0u; + /// \brief Per-SUnit data computed during DFS for various metrics. + /// + /// A node's SubtreeID is set to itself when it is visited to indicate that it + /// is the root of a subtree. Later it is set to its parent to indicate an + /// interior node. Finally, it is set to a representative subtree ID during + /// finalization. struct NodeData { unsigned InstrCount; + unsigned SubInstrCount; unsigned SubtreeID; - NodeData(): InstrCount(0), SubtreeID(0) {} + NodeData(): InstrCount(0), SubInstrCount(0), SubtreeID(InvalidSubtreeID) {} }; /// \brief Record a connection between subtrees and the connection level. @@ -102,6 +109,11 @@ public: SchedDFSResult(bool IsBU, unsigned lim) : IsBottomUp(IsBU), SubtreeLimit(lim) {} + /// \brief Return true if this DFSResult is uninitialized. + /// + /// resize() initializes DFSResult, while compute() populates it. + bool empty() const { return DFSData.empty(); } + /// \brief Clear the results. void clear() { DFSData.clear(); diff --git a/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp b/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp index 3960c57..428c1a4 100644 --- a/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -1021,35 +1021,56 @@ class SchedDFSImpl { public: SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSData.size()) {} - /// SubtreID is initialized to zero, set to itself to flag the root of a - /// subtree, set to the parent to indicate an interior node, - /// then set to a representative subtree ID during finalization. + /// Return true if this node been visited by the DFS traversal. + /// + /// During visitPostorderNode the Node's SubtreeID is assigned to the Node + /// ID. Later, SubtreeID is updated but remains valid. bool isVisited(const SUnit *SU) const { - return R.DFSData[SU->NodeNum].SubtreeID; + return R.DFSData[SU->NodeNum].SubtreeID != SchedDFSResult::InvalidSubtreeID; } /// Initialize this node's instruction count. We don't need to flag the node /// visited until visitPostorder because the DAG cannot have cycles. void visitPreorder(const SUnit *SU) { R.DFSData[SU->NodeNum].InstrCount = SU->getInstr()->isTransient() ? 0 : 1; + R.DFSData[SU->NodeNum].SubInstrCount = R.DFSData[SU->NodeNum].InstrCount; } - /// Mark this node as either the root of a subtree or an interior - /// node. Increment the parent node's instruction count. - void visitPostorder(const SUnit *SU, const SDep *PredDep, const SUnit *Parent) { - R.DFSData[SU->NodeNum].SubtreeID = SU->NodeNum; + /// Called once for each tree edge after calling visitPostOrderNode on the + /// predecessor. Increment the parent node's instruction count and + /// preemptively join this subtree to its parent's if it is small enough. + void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) { + R.DFSData[Succ->NodeNum].InstrCount + += R.DFSData[PredDep.getSUnit()->NodeNum].InstrCount; + joinPredSubtree(PredDep, Succ); + } - if (!Parent) - return; - assert(PredDep && "PredDep required for non-root node"); + /// Called once for each node after all predecessors are visited. Revisit this + /// node's predecessors and potentially join them now that we know the ILP of + /// the other predecessors. + void visitPostorderNode(const SUnit *SU) { + // Mark this node as the root of a subtree. It may be joined with its + // successors later. + R.DFSData[SU->NodeNum].SubtreeID = SU->NodeNum; - joinPredSubtree(*PredDep, Parent); + // If any predecessors are still in their own subtree, they either cannot be + // joined or are large enough to remain separate. If this parent node's + // total instruction count is not greater than a child subtree by at least + // the subtree limit, then try to join it now since splitting subtrees is + // only useful if multiple high-pressure paths are possible. + unsigned InstrCount = R.DFSData[SU->NodeNum].InstrCount; + for (SUnit::const_pred_iterator + PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) { + if (PI->getKind() != SDep::Data) + continue; + unsigned PredNum = PI->getSUnit()->NodeNum; + if ((InstrCount - R.DFSData[PredNum].InstrCount) < R.SubtreeLimit) + joinPredSubtree(*PI, SU, /*CheckLimit=*/false); + } } - /// Determine whether the DFS cross edge should be considered a subtree edge - /// or a connection between subtrees. - void visitCross(const SDep &PredDep, const SUnit *Succ) { - joinPredSubtree(PredDep, Succ); + /// Add a connection for cross edges. + void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) { ConnectionPairs.push_back(std::make_pair(PredDep.getSUnit(), Succ)); } @@ -1079,32 +1100,35 @@ public: } protected: - void joinPredSubtree(const SDep &PredDep, const SUnit *Succ) { - // Join the child to its parent if they are connected via data dependence. - if (PredDep.getKind() != SDep::Data) - return; + /// Join the predecessor subtree with the successor that is its DFS + /// parent. Apply some heuristics before joining. + bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, + bool CheckLimit = true) { + assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges"); + + // Check if the predecessor is already joined. + const SUnit *PredSU = PredDep.getSUnit(); + unsigned PredNum = PredSU->NodeNum; + if (R.DFSData[PredNum].SubtreeID != PredNum) + return false; // Four is the magic number of successors before a node is considered a // pinch point. unsigned NumDataSucs = 0; - const SUnit *PredSU = PredDep.getSUnit(); for (SUnit::const_succ_iterator SI = PredSU->Succs.begin(), SE = PredSU->Succs.end(); SI != SE; ++SI) { if (SI->getKind() == SDep::Data) { if (++NumDataSucs >= 4) - return; + return false; } } - // If this is a cross edge to a root, join the subtrees. This happens when - // the root was first reached by a non-data dependence. - unsigned NodeNum = PredSU->NodeNum; - unsigned PredCnt = R.DFSData[NodeNum].InstrCount; - if (R.DFSData[NodeNum].SubtreeID == NodeNum && PredCnt < R.SubtreeLimit) { - R.DFSData[NodeNum].SubtreeID = Succ->NodeNum; - R.DFSData[Succ->NodeNum].InstrCount += PredCnt; - SubtreeClasses.join(Succ->NodeNum, NodeNum); - return; - } + if (CheckLimit && R.DFSData[PredNum].SubInstrCount > R.SubtreeLimit) + return false; + + R.DFSData[PredNum].SubtreeID = Succ->NodeNum; + R.DFSData[Succ->NodeNum].SubInstrCount += R.DFSData[PredNum].SubInstrCount; + SubtreeClasses.join(Succ->NodeNum, PredNum); + return true; } /// Called by finalize() to record a connection between trees. @@ -1153,6 +1177,15 @@ public: }; } // anonymous +static bool hasDataSucc(const SUnit *SU) { + for (SUnit::const_succ_iterator + SI = SU->Succs.begin(), SE = SU->Succs.end(); SI != SE; ++SI) { + if (SI->getKind() == SDep::Data) + return true; + } + return false; +} + /// Compute an ILP metric for all nodes in the subDAG reachable via depth-first /// search from this root. void SchedDFSResult::compute(ArrayRef Roots) { @@ -1170,11 +1203,12 @@ void SchedDFSResult::compute(ArrayRef Roots) { while (DFS.getPred() != DFS.getPredEnd()) { const SDep &PredDep = *DFS.getPred(); DFS.advance(); - // If the pred is already valid, skip it. We may preorder visit a node - // with InstrCount==0 more than once, but it won't affect heuristics - // because we don't care about cross edges to leaf copies. + // Ignore non-data edges. + if (PredDep.getKind() != SDep::Data) + continue; + // An already visited edge is a cross edge, assuming an acyclic DAG. if (Impl.isVisited(PredDep.getSUnit())) { - Impl.visitCross(PredDep, DFS.getCurr()); + Impl.visitCrossEdge(PredDep, DFS.getCurr()); continue; } Impl.visitPreorder(PredDep.getSUnit()); @@ -1183,7 +1217,9 @@ void SchedDFSResult::compute(ArrayRef Roots) { // Visit the top of the stack in postorder and backtrack. const SUnit *Child = DFS.getCurr(); const SDep *PredDep = DFS.backtrack(); - Impl.visitPostorder(Child, PredDep, PredDep ? DFS.getCurr() : 0); + Impl.visitPostorderNode(Child); + if (PredDep) + Impl.visitPostorderEdge(*PredDep, DFS.getCurr()); if (DFS.isComplete()) break; } -- 2.7.4