Page MenuHomePhabricator

D58349.id187239.diff
No OneTemporary

File Metadata

Created
Sat, Aug 17, 3:30 AM

D58349.id187239.diff

Index: include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
--- include/llvm/Support/GenericDomTreeConstruction.h
+++ include/llvm/Support/GenericDomTreeConstruction.h
@@ -620,18 +620,17 @@
// Helper struct used during edge insertions.
struct InsertionInfo {
using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
- struct DecreasingLevel {
+ struct Compare {
bool operator()(const BucketElementTy &First,
const BucketElementTy &Second) const {
- return First.first > Second.first;
+ return First.first < Second.first;
}
};
std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
- DecreasingLevel>
- Bucket; // Queue of tree nodes sorted by level in descending order.
- SmallDenseSet<TreeNodePtr, 8> Affected;
- SmallDenseMap<TreeNodePtr, unsigned, 8> Visited;
+ Compare>
+ Bucket; // Queue of tree nodes sorted by level in descending order.
+ SmallDenseSet<TreeNodePtr, 8> Visited;
SmallVector<TreeNodePtr, 8> AffectedQueue;
SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
};
@@ -744,13 +743,14 @@
// Identify and collect affected nodes.
InsertionInfo II;
+ SmallVector<TreeNodePtr, 8> Stack;
LLVM_DEBUG(dbgs() << "Marking " << BlockNamePrinter(To)
<< " as affected\n");
- II.Affected.insert(To);
const unsigned ToLevel = To->getLevel();
LLVM_DEBUG(dbgs() << "Putting " << BlockNamePrinter(To)
<< " into a Bucket\n");
II.Bucket.push({ToLevel, To});
+ II.Visited.insert(To);
while (!II.Bucket.empty()) {
const TreeNodePtr CurrentNode = II.Bucket.top().second;
@@ -759,11 +759,10 @@
LLVM_DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
<< BlockNamePrinter(CurrentNode) << "\n");
- II.Visited.insert({CurrentNode, CurrentLevel});
II.AffectedQueue.push_back(CurrentNode);
// Discover and collect affected successors of the current node.
- VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II);
+ VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, Stack, NCD, II);
}
// Finish by updating immediate dominators and levels.
@@ -772,23 +771,20 @@
// Visits an affected node and collect its affected successors.
static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
- const TreeNodePtr TN, const unsigned RootLevel,
+ TreeNodePtr TN, const unsigned RootLevel,
+ SmallVectorImpl<TreeNodePtr> &Stack,
const TreeNodePtr NCD, InsertionInfo &II) {
const unsigned NCDLevel = NCD->getLevel();
LLVM_DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << ", RootLevel "
<< RootLevel << "\n");
- SmallVector<TreeNodePtr, 8> Stack = {TN};
assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
- SmallPtrSet<TreeNodePtr, 8> Processed;
-
- do {
- TreeNodePtr Next = Stack.pop_back_val();
- LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n");
+ while (1) {
+ LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(TN) << "\n");
for (const NodePtr Succ :
- ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
+ ChildrenGetter<IsPostDom>::Get(TN->getBlock(), BUI)) {
const TreeNodePtr SuccTN = DT.getNode(Succ);
assert(SuccTN && "Unreachable successor found at reachable insertion");
const unsigned SuccLevel = SuccTN->getLevel();
@@ -796,41 +792,25 @@
LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
<< ", level = " << SuccLevel << "\n");
- // Do not process the same node multiple times.
- if (Processed.count(Next) > 0)
+ if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second)
continue;
- // Succ dominated by subtree From -- not affected.
- // (Based on the lemma 2.5 from the second paper.)
if (SuccLevel > RootLevel) {
- LLVM_DEBUG(dbgs() << "\t\tDominated by subtree From\n");
- if (II.Visited.count(SuccTN) != 0) {
- LLVM_DEBUG(dbgs() << "\t\t\talready visited at level "
- << II.Visited[SuccTN] << "\n\t\t\tcurrent level "
- << RootLevel << ")\n");
-
- // A node can be necessary to visit again if we see it again at
- // a lower level than before.
- if (II.Visited[SuccTN] >= RootLevel)
- continue;
- }
-
LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
<< BlockNamePrinter(Succ) << "\n");
- II.Visited.insert({SuccTN, RootLevel});
II.VisitedNotAffectedQueue.push_back(SuccTN);
Stack.push_back(SuccTN);
- } else if ((SuccLevel > NCDLevel + 1) &&
- II.Affected.count(SuccTN) == 0) {
+ } else {
LLVM_DEBUG(dbgs() << "\t\tMarking affected and adding "
<< BlockNamePrinter(Succ) << " to a Bucket\n");
- II.Affected.insert(SuccTN);
II.Bucket.push({SuccLevel, SuccTN});
}
}
- Processed.insert(Next);
- } while (!Stack.empty());
+ if (Stack.empty())
+ break;
+ TN = Stack.pop_back_val();
+ }
}
// Updates immediate dominators and levels after insertion.

Event Timeline