diff options
author | Andrew Trick <atrick@apple.com> | 2013-01-25 06:52:30 +0000 |
---|---|---|
committer | Andrew Trick <atrick@apple.com> | 2013-01-25 06:52:30 +0000 |
commit | a5a73ad15905c18843a8312bb3f20f5c501744de (patch) | |
tree | 96af883ec3f24e32ba541774bdab6a4c94689cd1 | |
parent | 988d06b0e574d8e50b043fd74dbf91c1dc403542 (diff) | |
download | llvm-a5a73ad15905c18843a8312bb3f20f5c501744de.tar.gz llvm-a5a73ad15905c18843a8312bb3f20f5c501744de.tar.bz2 llvm-a5a73ad15905c18843a8312bb3f20f5c501744de.tar.xz |
ScheduleDAG: Added isBoundaryNode to conveniently detect a common corner case.
This fixes DAG subtree analysis at the boundary.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173427 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/CodeGen/ScheduleDAG.h | 13 | ||||
-rw-r--r-- | lib/CodeGen/ScheduleDAGInstrs.cpp | 26 |
2 files changed, 31 insertions, 8 deletions
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 9f4f66f860..18bef1c402 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -258,6 +258,8 @@ namespace llvm { /// SUnit - Scheduling unit. This is a node in the scheduling DAG. class SUnit { private: + enum { BoundaryID = ~0u }; + SDNode *Node; // Representative node. MachineInstr *Instr; // Alternatively, a MachineInstr. public: @@ -343,7 +345,7 @@ namespace llvm { /// SUnit - Construct a placeholder SUnit. SUnit() - : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(~0u), + : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(BoundaryID), NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), @@ -354,6 +356,15 @@ namespace llvm { isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} + /// \brief Boundary nodes are placeholders for the boundary of the + /// scheduling region. + /// + /// BoundaryNodes can have DAG edges, including Data edges, but they do not + /// correspond to schedulable entities (e.g. instructions) and do not have a + /// valid ID. Consequently, always check for boundary nodes before accessing + /// an assoicative data structure keyed on node ID. + bool isBoundaryNode() const { return NodeNum == BoundaryID; }; + /// setNode - Assign the representative SDNode for this SUnit. /// This may be used during pre-regalloc scheduling. void setNode(SDNode *N) { diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp index ef504067d1..f27b970aff 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -1078,9 +1078,17 @@ public: joinPredSubtree(*PI, SU, /*CheckLimit=*/false); // Either link or merge the TreeData entry from the child to the parent. - if (R.DFSNodeData[PredNum].SubtreeID == PredNum) - RootSet[PredNum].ParentNodeID = SU->NodeNum; - else { + if (R.DFSNodeData[PredNum].SubtreeID == PredNum) { + // If the predecessor's parent is invalid, this is a tree edge and the + // current node is the parent. + if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID) + RootSet[PredNum].ParentNodeID = SU->NodeNum; + } + else if (RootSet.count(PredNum)) { + // The predecessor is not a root, but is still in the root set. This + // must be the new parent that it was just joined to. Note that + // RootSet[PredNum].ParentNodeID may either be invalid or may still be + // set to the original parent. RData.SubInstrCount += RootSet[PredNum].SubInstrCount; RootSet.erase(PredNum); } @@ -1115,8 +1123,10 @@ public: if (RI->ParentNodeID != SchedDFSResult::InvalidSubtreeID) R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[RI->ParentNodeID]; R.DFSTreeData[TreeID].SubInstrCount = RI->SubInstrCount; - assert(RI->SubInstrCount <= R.DFSNodeData[RI->NodeID].InstrCount && - "Bad SubInstrCount"); + // Note that SubInstrCount may be greater than InstrCount if we joined + // subtrees across a cross edge. InstrCount will be attributed to the + // original parent, while SubInstrCount will be attributed to the joined + // parent. } R.SubtreeConnections.resize(SubtreeClasses.getNumClasses()); R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses()); @@ -1221,7 +1231,7 @@ public: 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) + if (SI->getKind() == SDep::Data && !SI->getSUnit()->isBoundaryNode()) return true; } return false; @@ -1249,8 +1259,10 @@ void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) { const SDep &PredDep = *DFS.getPred(); DFS.advance(); // Ignore non-data edges. - if (PredDep.getKind() != SDep::Data) + if (PredDep.getKind() != SDep::Data + || PredDep.getSUnit()->isBoundaryNode()) { continue; + } // An already visited edge is a cross edge, assuming an acyclic DAG. if (Impl.isVisited(PredDep.getSUnit())) { Impl.visitCrossEdge(PredDep, DFS.getCurr()); |