this->Roots.push_back(MBB);
}
-EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
-EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<MachineBasicBlock>);
+extern template class DomTreeNodeBase<MachineBasicBlock>;
+extern template class DominatorTreeBase<MachineBasicBlock>;
typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
MachineBasicBlock *FromBB;
MachineBasicBlock *ToBB;
MachineBasicBlock *NewBB;
- CriticalEdge(MachineBasicBlock *FromBB, MachineBasicBlock *ToBB,
- MachineBasicBlock *NewBB)
- : FromBB(FromBB), ToBB(ToBB), NewBB(NewBB) {}
};
/// \brief Pile up all the critical edges to be split.
/// the fast query path of DT as much as possible.
///
/// \post CriticalEdgesToSplit.empty().
- void applySplitCriticalEdges() const {
- // Bail out early if there is nothing to do.
- if (CriticalEdgesToSplit.empty())
- return;
-
- // For each element in CriticalEdgesToSplit, remember whether or
- // not element is the new immediate domminator of its successor.
- // The mapping is done by index, i.e., the information for the ith
- // element of CriticalEdgesToSplit is the ith element of IsNewIDom.
- SmallVector<bool, 32> IsNewIDom;
- IsNewIDom.resize(CriticalEdgesToSplit.size());
- size_t Idx = 0;
-
- // Collect all the dominance properties info, before invalidating
- // the underlying DT.
- for (CriticalEdge &Edge : CriticalEdgesToSplit) {
- // Update dominator information.
- MachineBasicBlock *Succ = Edge.ToBB;
- MachineDomTreeNode *SucccDTNode = DT->getNode(Succ);
-
- IsNewIDom[Idx] = true;
- for (MachineBasicBlock *PredBB : Succ->predecessors()) {
- if (PredBB == Edge.NewBB)
- continue;
- // If we are in this situation:
- // FromBB1 FromBB2
- // + +
- // + + + +
- // + + + +
- // ... Split1 Split2 ...
- // + +
- // + +
- // +
- // Succ
- // Instead of checking the domiance property with Split2, we
- // check it with FromBB2 since Split2 is still unknown of the
- // underlying DT structure.
- if (NewBBs.count(PredBB)) {
- assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
- "critical edge split has more "
- "than one predecessor!");
- PredBB = *PredBB->pred_begin();
- }
- if (!DT->dominates(SucccDTNode, DT->getNode(PredBB))) {
- IsNewIDom[Idx] = false;
- break;
- }
- }
- ++Idx;
- }
-
- // Now, update DT with the collected dominance properties info.
- Idx = 0;
- for (CriticalEdge &Edge : CriticalEdgesToSplit) {
- // We know FromBB dominates NewBB.
- MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
- MachineDomTreeNode *SucccDTNode = DT->getNode(Edge.ToBB);
-
- // If all the other predecessors of "Succ" are dominated by "Succ" itself
- // then the new block is the new immediate dominator of "Succ". Otherwise,
- // the new block doesn't dominate anything.
- if (IsNewIDom[Idx])
- DT->changeImmediateDominator(SucccDTNode, NewDTNode);
- ++Idx;
- }
- NewBBs.clear();
- CriticalEdgesToSplit.clear();
- }
+ void applySplitCriticalEdges() const;
public:
static char ID; // Pass ID, replacement for typeid
MachineDominatorTree();
- ~MachineDominatorTree();
+ ~MachineDominatorTree() override;
DominatorTreeBase<MachineBasicBlock> &getBase() {
applySplitCriticalEdges();
void recordSplitCriticalEdge(MachineBasicBlock *FromBB,
MachineBasicBlock *ToBB,
MachineBasicBlock *NewBB) {
- bool Inserted = NewBBs.insert(NewBB);
+ bool Inserted = NewBBs.insert(NewBB).second;
(void)Inserted;
assert(Inserted &&
"A basic block inserted via edge splitting cannot appear twice");
- CriticalEdgesToSplit.push_back(CriticalEdge(FromBB, ToBB, NewBB));
+ CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
}
};
/// iterable by generic graph iterators.
///
-template<class T> struct GraphTraits;
-
-template <> struct GraphTraits<MachineDomTreeNode *> {
- typedef MachineDomTreeNode NodeType;
- typedef NodeType::iterator ChildIteratorType;
+template <class Node, class ChildIterator>
+struct MachineDomTreeGraphTraitsBase {
+ typedef Node NodeType;
+ typedef ChildIterator ChildIteratorType;
- static NodeType *getEntryNode(NodeType *N) {
- return N;
- }
- static inline ChildIteratorType child_begin(NodeType* N) {
+ static NodeType *getEntryNode(NodeType *N) { return N; }
+ static inline ChildIteratorType child_begin(NodeType *N) {
return N->begin();
}
- static inline ChildIteratorType child_end(NodeType* N) {
- return N->end();
- }
+ static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
+};
+
+template <class T> struct GraphTraits;
+
+template <>
+struct GraphTraits<MachineDomTreeNode *>
+ : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode,
+ MachineDomTreeNode::iterator> {};
+
+template <>
+struct GraphTraits<const MachineDomTreeNode *>
+ : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode,
+ MachineDomTreeNode::const_iterator> {
};
template <> struct GraphTraits<MachineDominatorTree*>