summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/IR/Dominators.h6
-rw-r--r--llvm/include/llvm/Support/GenericDomTree.h49
-rw-r--r--llvm/include/llvm/Support/GenericDomTreeConstruction.h80
-rw-r--r--llvm/lib/IR/Dominators.cpp2
-rw-r--r--llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp8
5 files changed, 28 insertions, 117 deletions
diff --git a/llvm/include/llvm/IR/Dominators.h b/llvm/include/llvm/IR/Dominators.h
index 250d1cbfb22..47032c00481 100644
--- a/llvm/include/llvm/IR/Dominators.h
+++ b/llvm/include/llvm/IR/Dominators.h
@@ -37,13 +37,13 @@ extern template class DomTreeNodeBase<BasicBlock>;
extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
+extern template class cfg::Update<BasicBlock *>;
+
namespace DomTreeBuilder {
using BBDomTree = DomTreeBase<BasicBlock>;
using BBPostDomTree = PostDomTreeBase<BasicBlock>;
-extern template struct Update<BasicBlock *>;
-
-using BBUpdates = ArrayRef<Update<BasicBlock *>>;
+using BBUpdates = ArrayRef<llvm::cfg::Update<BasicBlock *>>;
extern template void Calculate<BBDomTree>(BBDomTree &DT);
extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h
index c716e4a4d30..3c3ec092101 100644
--- a/llvm/include/llvm/Support/GenericDomTree.h
+++ b/llvm/include/llvm/Support/GenericDomTree.h
@@ -24,6 +24,14 @@
#ifndef LLVM_SUPPORT_GENERICDOMTREE_H
#define LLVM_SUPPORT_GENERICDOMTREE_H
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/CFGUpdate.h"
+#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
@@ -32,13 +40,6 @@
#include <type_traits>
#include <utility>
#include <vector>
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/PointerIntPair.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/Support/raw_ostream.h"
namespace llvm {
@@ -199,36 +200,6 @@ template <typename DomTreeT>
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
typename DomTreeT::NodePtr To);
-// UpdateKind and Update are used by the batch update API and it's easiest to
-// define them here.
-enum class UpdateKind : unsigned char { Insert, Delete };
-
-template <typename NodePtr>
-struct Update {
- using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
-
- NodePtr From;
- NodeKindPair ToAndKind;
-
- Update(UpdateKind Kind, NodePtr From, NodePtr To)
- : From(From), ToAndKind(To, Kind) {}
-
- UpdateKind getKind() const { return ToAndKind.getInt(); }
- NodePtr getFrom() const { return From; }
- NodePtr getTo() const { return ToAndKind.getPointer(); }
- bool operator==(const Update &RHS) const {
- return From == RHS.From && ToAndKind == RHS.ToAndKind;
- }
-
- friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) {
- OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
- U.getFrom()->printAsOperand(OS, false);
- OS << " -> ";
- U.getTo()->printAsOperand(OS, false);
- return OS;
- }
-};
-
template <typename DomTreeT>
void ApplyUpdates(DomTreeT &DT,
ArrayRef<typename DomTreeT::UpdateType> Updates);
@@ -254,8 +225,8 @@ class DominatorTreeBase {
using ParentType = typename std::remove_pointer<ParentPtr>::type;
static constexpr bool IsPostDominator = IsPostDom;
- using UpdateType = DomTreeBuilder::Update<NodePtr>;
- using UpdateKind = DomTreeBuilder::UpdateKind;
+ using UpdateType = cfg::Update<NodePtr>;
+ using UpdateKind = cfg::UpdateKind;
static constexpr UpdateKind Insert = UpdateKind::Insert;
static constexpr UpdateKind Delete = UpdateKind::Delete;
diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
index 103ff8ca476..80d3b276c6d 100644
--- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -71,6 +71,7 @@ struct SemiNCAInfo {
DenseMap<NodePtr, InfoRec> NodeToInfo;
using UpdateT = typename DomTreeT::UpdateType;
+ using UpdateKind = typename DomTreeT::UpdateKind;
struct BatchUpdateInfo {
SmallVector<UpdateT, 4> Updates;
using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
@@ -1166,7 +1167,8 @@ struct SemiNCAInfo {
}
BatchUpdateInfo BUI;
- LegalizeUpdates(Updates, BUI.Updates);
+ LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
+ cfg::LegalizeUpdates<NodePtr>(Updates, BUI.Updates, IsPostDom);
const size_t NumLegalized = BUI.Updates.size();
BUI.FutureSuccessors.reserve(NumLegalized);
@@ -1182,8 +1184,11 @@ struct SemiNCAInfo {
LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U
- : reverse(BUI.Updates)) dbgs()
- << '\t' << U << "\n");
+ : reverse(BUI.Updates)) {
+ dbgs() << "\t";
+ U.dump();
+ dbgs() << "\n";
+ });
LLVM_DEBUG(dbgs() << "\n");
// If the DominatorTree was recalculated at some point, stop the batch
@@ -1193,76 +1198,11 @@ struct SemiNCAInfo {
ApplyNextUpdate(DT, BUI);
}
- // This function serves double purpose:
- // a) It removes redundant updates, which makes it easier to reverse-apply
- // them when traversing CFG.
- // b) It optimizes away updates that cancel each other out, as the end result
- // is the same.
- //
- // It relies on the property of the incremental updates that says that the
- // order of updates doesn't matter. This allows us to reorder them and end up
- // with the exact same DomTree every time.
- //
- // Following the same logic, the function doesn't care about the order of
- // input updates, so it's OK to pass it an unordered sequence of updates, that
- // doesn't make sense when applied sequentially, eg. performing double
- // insertions or deletions and then doing an opposite update.
- //
- // In the future, it should be possible to schedule updates in way that
- // minimizes the amount of work needed done during incremental updates.
- static void LegalizeUpdates(ArrayRef<UpdateT> AllUpdates,
- SmallVectorImpl<UpdateT> &Result) {
- LLVM_DEBUG(dbgs() << "Legalizing " << AllUpdates.size() << " updates\n");
- // Count the total number of inserions of each edge.
- // Each insertion adds 1 and deletion subtracts 1. The end number should be
- // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
- // of updates contains multiple updates of the same kind and we assert for
- // that case.
- SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
- Operations.reserve(AllUpdates.size());
-
- for (const auto &U : AllUpdates) {
- NodePtr From = U.getFrom();
- NodePtr To = U.getTo();
- if (IsPostDom) std::swap(From, To); // Reverse edge for postdominators.
-
- Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
- }
-
- Result.clear();
- Result.reserve(Operations.size());
- for (auto &Op : Operations) {
- const int NumInsertions = Op.second;
- assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
- if (NumInsertions == 0) continue;
- const UpdateKind UK =
- NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
- Result.push_back({UK, Op.first.first, Op.first.second});
- }
-
- // Make the order consistent by not relying on pointer values within the
- // set. Reuse the old Operations map.
- // In the future, we should sort by something else to minimize the amount
- // of work needed to perform the series of updates.
- for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
- const auto &U = AllUpdates[i];
- if (!IsPostDom)
- Operations[{U.getFrom(), U.getTo()}] = int(i);
- else
- Operations[{U.getTo(), U.getFrom()}] = int(i);
- }
-
- llvm::sort(Result.begin(), Result.end(),
- [&Operations](const UpdateT &A, const UpdateT &B) {
- return Operations[{A.getFrom(), A.getTo()}] >
- Operations[{B.getFrom(), B.getTo()}];
- });
- }
-
static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
assert(!BUI.Updates.empty() && "No updates to apply!");
UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
- LLVM_DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n");
+ LLVM_DEBUG(dbgs() << "Applying update: ");
+ LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n");
// Move to the next snapshot of the CFG by removing the reverse-applied
// current update. Since updates are performed in the same order they are
diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp
index 13828af4f1b..dc4fa9eee66 100644
--- a/llvm/lib/IR/Dominators.cpp
+++ b/llvm/lib/IR/Dominators.cpp
@@ -67,7 +67,7 @@ template class llvm::DomTreeNodeBase<BasicBlock>;
template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
-template struct llvm::DomTreeBuilder::Update<BasicBlock *>;
+template class llvm::cfg::Update<BasicBlock *>;
template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
DomTreeBuilder::BBDomTree &DT);
diff --git a/llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp b/llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
index 85308685e5d..6775fc1ab5c 100644
--- a/llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
+++ b/llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp
@@ -58,9 +58,9 @@ TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) {
{Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
{Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
SmallVector<DomUpdate, 4> Legalized;
- DomSNCA::LegalizeUpdates(Updates, Legalized);
+ cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, false);
LLVM_DEBUG(dbgs() << "Legalized updates:\t");
- LLVM_DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
+ LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
LLVM_DEBUG(dbgs() << "\n");
EXPECT_EQ(Legalized.size(), 3UL);
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end());
@@ -81,9 +81,9 @@ TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) {
{Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
{Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
SmallVector<DomUpdate, 4> Legalized;
- PostDomSNCA::LegalizeUpdates(Updates, Legalized);
+ cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, true);
LLVM_DEBUG(dbgs() << "Legalized postdom updates:\t");
- LLVM_DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
+ LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
LLVM_DEBUG(dbgs() << "\n");
EXPECT_EQ(Legalized.size(), 3UL);
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end());
OpenPOWER on IntegriCloud