summaryrefslogtreecommitdiff
path: root/include/llvm/Support
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/Support')
-rw-r--r--include/llvm/Support/AArch64TargetParser.def5
-rw-r--r--include/llvm/Support/BinaryItemStream.h39
-rw-r--r--include/llvm/Support/Format.h25
-rw-r--r--include/llvm/Support/GenericDomTree.h160
-rw-r--r--include/llvm/Support/GenericDomTreeConstruction.h670
-rw-r--r--include/llvm/Support/TargetParser.h4
-rw-r--r--include/llvm/Support/YAMLTraits.h4
7 files changed, 723 insertions, 184 deletions
diff --git a/include/llvm/Support/AArch64TargetParser.def b/include/llvm/Support/AArch64TargetParser.def
index 8eccebcd932a0..09f9602a24d94 100644
--- a/include/llvm/Support/AArch64TargetParser.def
+++ b/include/llvm/Support/AArch64TargetParser.def
@@ -43,8 +43,9 @@ AARCH64_ARCH_EXT_NAME("crypto", AArch64::AEK_CRYPTO, "+crypto","-crypto")
AARCH64_ARCH_EXT_NAME("fp", AArch64::AEK_FP, "+fp-armv8", "-fp-armv8")
AARCH64_ARCH_EXT_NAME("simd", AArch64::AEK_SIMD, "+neon", "-neon")
AARCH64_ARCH_EXT_NAME("fp16", AArch64::AEK_FP16, "+fullfp16", "-fullfp16")
-AARCH64_ARCH_EXT_NAME("profile", AArch64::AEK_PROFILE, "+spe", "-spe")
-AARCH64_ARCH_EXT_NAME("ras", AArch64::AEK_RAS, "+ras", "-ras")
+AARCH64_ARCH_EXT_NAME("profile", AArch64::AEK_PROFILE, "+spe", "-spe")
+AARCH64_ARCH_EXT_NAME("ras", AArch64::AEK_RAS, "+ras", "-ras")
+AARCH64_ARCH_EXT_NAME("sve", AArch64::AEK_SVE, "+sve", "-sve")
#undef AARCH64_ARCH_EXT_NAME
#ifndef AARCH64_CPU_NAME
diff --git a/include/llvm/Support/BinaryItemStream.h b/include/llvm/Support/BinaryItemStream.h
index f4b319217819e..fe7e6caeaafb7 100644
--- a/include/llvm/Support/BinaryItemStream.h
+++ b/include/llvm/Support/BinaryItemStream.h
@@ -62,32 +62,45 @@ public:
return Error::success();
}
- void setItems(ArrayRef<T> ItemArray) { Items = ItemArray; }
+ void setItems(ArrayRef<T> ItemArray) {
+ Items = ItemArray;
+ computeItemOffsets();
+ }
uint32_t getLength() override {
- uint32_t Size = 0;
- for (const auto &Item : Items)
- Size += Traits::length(Item);
- return Size;
+ return ItemEndOffsets.empty() ? 0 : ItemEndOffsets.back();
}
private:
- Expected<uint32_t> translateOffsetIndex(uint32_t Offset) const {
+ void computeItemOffsets() {
+ ItemEndOffsets.clear();
+ ItemEndOffsets.reserve(Items.size());
uint32_t CurrentOffset = 0;
- uint32_t CurrentIndex = 0;
for (const auto &Item : Items) {
- if (CurrentOffset >= Offset)
- break;
- CurrentOffset += Traits::length(Item);
- ++CurrentIndex;
+ uint32_t Len = Traits::length(Item);
+ assert(Len > 0 && "no empty items");
+ CurrentOffset += Len;
+ ItemEndOffsets.push_back(CurrentOffset);
}
- if (CurrentOffset != Offset)
+ }
+
+ Expected<uint32_t> translateOffsetIndex(uint32_t Offset) {
+ // Make sure the offset is somewhere in our items array.
+ if (Offset >= getLength())
return make_error<BinaryStreamError>(stream_error_code::stream_too_short);
- return CurrentIndex;
+ ++Offset;
+ auto Iter =
+ std::lower_bound(ItemEndOffsets.begin(), ItemEndOffsets.end(), Offset);
+ size_t Idx = std::distance(ItemEndOffsets.begin(), Iter);
+ assert(Idx < Items.size() && "binary search for offset failed");
+ return Idx;
}
llvm::support::endianness Endian;
ArrayRef<T> Items;
+
+ // Sorted vector of offsets to accelerate lookup.
+ std::vector<uint32_t> ItemEndOffsets;
};
} // end namespace llvm
diff --git a/include/llvm/Support/Format.h b/include/llvm/Support/Format.h
index 017b4973f1ffc..bcbd2bec57228 100644
--- a/include/llvm/Support/Format.h
+++ b/include/llvm/Support/Format.h
@@ -125,30 +125,39 @@ inline format_object<Ts...> format(const char *Fmt, const Ts &... Vals) {
return format_object<Ts...>(Fmt, Vals...);
}
-/// This is a helper class used for left_justify() and right_justify().
+/// This is a helper class for left_justify, right_justify, and center_justify.
class FormattedString {
+public:
+ enum Justification { JustifyNone, JustifyLeft, JustifyRight, JustifyCenter };
+ FormattedString(StringRef S, unsigned W, Justification J)
+ : Str(S), Width(W), Justify(J) {}
+
+private:
StringRef Str;
unsigned Width;
- bool RightJustify;
+ Justification Justify;
friend class raw_ostream;
-
-public:
- FormattedString(StringRef S, unsigned W, bool R)
- : Str(S), Width(W), RightJustify(R) { }
};
/// left_justify - append spaces after string so total output is
/// \p Width characters. If \p Str is larger that \p Width, full string
/// is written with no padding.
inline FormattedString left_justify(StringRef Str, unsigned Width) {
- return FormattedString(Str, Width, false);
+ return FormattedString(Str, Width, FormattedString::JustifyLeft);
}
/// right_justify - add spaces before string so total output is
/// \p Width characters. If \p Str is larger that \p Width, full string
/// is written with no padding.
inline FormattedString right_justify(StringRef Str, unsigned Width) {
- return FormattedString(Str, Width, true);
+ return FormattedString(Str, Width, FormattedString::JustifyRight);
+}
+
+/// center_justify - add spaces before and after string so total output is
+/// \p Width characters. If \p Str is larger that \p Width, full string
+/// is written with no padding.
+inline FormattedString center_justify(StringRef Str, unsigned Width) {
+ return FormattedString(Str, Width, FormattedString::JustifyCenter);
}
/// This is a helper class used for format_hex() and format_decimal().
diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h
index 394a45387d8ac..706320fed9a72 100644
--- a/include/llvm/Support/GenericDomTree.h
+++ b/include/llvm/Support/GenericDomTree.h
@@ -41,27 +41,21 @@
namespace llvm {
-template <class NodeT> class DominatorTreeBase;
+template <typename NodeT, bool IsPostDom>
+class DominatorTreeBase;
-namespace detail {
-
-template <typename GT> struct DominatorTreeBaseTraits {
- static_assert(std::is_pointer<typename GT::NodeRef>::value,
- "Currently NodeRef must be a pointer type.");
- using type = DominatorTreeBase<
- typename std::remove_pointer<typename GT::NodeRef>::type>;
-};
-
-} // end namespace detail
-
-template <typename GT>
-using DominatorTreeBaseByGraphTraits =
- typename detail::DominatorTreeBaseTraits<GT>::type;
+namespace DomTreeBuilder {
+template <class DomTreeT>
+struct SemiNCAInfo;
+} // namespace DomTreeBuilder
/// \brief Base class for the actual dominator tree node.
template <class NodeT> class DomTreeNodeBase {
friend struct PostDominatorTree;
- template <class N> friend class DominatorTreeBase;
+ friend class DominatorTreeBase<NodeT, false>;
+ friend class DominatorTreeBase<NodeT, true>;
+ friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
+ friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
NodeT *TheBB;
DomTreeNodeBase *IDom;
@@ -192,58 +186,69 @@ void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
}
namespace DomTreeBuilder {
-template <class NodeT>
-struct SemiNCAInfo;
+// The routines below are provided in a separate header but referenced here.
+template <typename DomTreeT, typename FuncT>
+void Calculate(DomTreeT &DT, FuncT &F);
+
+template <class DomTreeT>
+void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
+ typename DomTreeT::NodePtr To);
-// The calculate routine is provided in a separate header but referenced here.
-template <class FuncT, class N>
-void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT, FuncT &F);
+template <class DomTreeT>
+void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
+ typename DomTreeT::NodePtr To);
-// The verify function is provided in a separate header but referenced here.
-template <class N>
-bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT);
+template <typename DomTreeT>
+bool Verify(const DomTreeT &DT);
} // namespace DomTreeBuilder
/// \brief Core dominator tree base class.
///
/// This class is a generic template over graph nodes. It is instantiated for
/// various graphs in the LLVM IR or in the code generator.
-template <class NodeT> class DominatorTreeBase {
+template <typename NodeT, bool IsPostDom>
+class DominatorTreeBase {
protected:
std::vector<NodeT *> Roots;
- bool IsPostDominators;
using DomTreeNodeMapType =
DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
DomTreeNodeMapType DomTreeNodes;
DomTreeNodeBase<NodeT> *RootNode;
+ using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
+ ParentPtr Parent = nullptr;
mutable bool DFSInfoValid = false;
mutable unsigned int SlowQueries = 0;
- friend struct DomTreeBuilder::SemiNCAInfo<NodeT>;
- using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo<NodeT>;
+ friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
public:
- explicit DominatorTreeBase(bool isPostDom) : IsPostDominators(isPostDom) {}
+ static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
+ "Currently DominatorTreeBase supports only pointer nodes");
+ using NodeType = NodeT;
+ using NodePtr = NodeT *;
+ static constexpr bool IsPostDominator = IsPostDom;
+
+ DominatorTreeBase() {}
DominatorTreeBase(DominatorTreeBase &&Arg)
: Roots(std::move(Arg.Roots)),
- IsPostDominators(Arg.IsPostDominators),
DomTreeNodes(std::move(Arg.DomTreeNodes)),
- RootNode(std::move(Arg.RootNode)),
- DFSInfoValid(std::move(Arg.DFSInfoValid)),
- SlowQueries(std::move(Arg.SlowQueries)) {
+ RootNode(Arg.RootNode),
+ Parent(Arg.Parent),
+ DFSInfoValid(Arg.DFSInfoValid),
+ SlowQueries(Arg.SlowQueries) {
Arg.wipe();
}
DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
Roots = std::move(RHS.Roots);
- IsPostDominators = RHS.IsPostDominators;
DomTreeNodes = std::move(RHS.DomTreeNodes);
- RootNode = std::move(RHS.RootNode);
- DFSInfoValid = std::move(RHS.DFSInfoValid);
- SlowQueries = std::move(RHS.SlowQueries);
+ RootNode = RHS.RootNode;
+ Parent = RHS.Parent;
+ DFSInfoValid = RHS.DFSInfoValid;
+ SlowQueries = RHS.SlowQueries;
RHS.wipe();
return *this;
}
@@ -259,11 +264,12 @@ template <class NodeT> class DominatorTreeBase {
/// isPostDominator - Returns true if analysis based of postdoms
///
- bool isPostDominator() const { return IsPostDominators; }
+ bool isPostDominator() const { return IsPostDominator; }
/// compare - Return false if the other dominator tree base matches this
/// dominator tree base. Otherwise return true.
bool compare(const DominatorTreeBase &Other) const {
+ if (Parent != Other.Parent) return true;
const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
if (DomTreeNodes.size() != OtherDomTreeNodes.size())
@@ -443,10 +449,50 @@ template <class NodeT> class DominatorTreeBase {
const_cast<NodeT *>(B));
}
+ bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
+ return isPostDominator() && !A->getBlock();
+ }
+
//===--------------------------------------------------------------------===//
// API to update (Post)DominatorTree information based on modifications to
// the CFG...
+ /// Inform the dominator tree about a CFG edge insertion and update the tree.
+ ///
+ /// This function has to be called just before or just after making the update
+ /// on the actual CFG. There cannot be any other updates that the dominator
+ /// tree doesn't know about.
+ ///
+ /// Note that for postdominators it automatically takes care of inserting
+ /// a reverse edge internally (so there's no need to swap the parameters).
+ ///
+ void insertEdge(NodeT *From, NodeT *To) {
+ assert(From);
+ assert(To);
+ assert(From->getParent() == Parent);
+ assert(To->getParent() == Parent);
+ DomTreeBuilder::InsertEdge(*this, From, To);
+ }
+
+ /// Inform the dominator tree about a CFG edge deletion and update the tree.
+ ///
+ /// This function has to be called just after making the update
+ /// on the actual CFG. There cannot be any other updates that the dominator
+ /// tree doesn't know about. The only exception is when the deletion that the
+ /// tree is informed about makes some (domominator) subtree unreachable -- in
+ /// this case, it is fine to perform deletions within this subtree.
+ ///
+ /// Note that for postdominators it automatically takes care of deleting
+ /// a reverse edge internally (so there's no need to swap the parameters).
+ ///
+ void deleteEdge(NodeT *From, NodeT *To) {
+ assert(From);
+ assert(To);
+ assert(From->getParent() == Parent);
+ assert(To->getParent() == Parent);
+ DomTreeBuilder::DeleteEdge(*this, From, To);
+ }
+
/// Add a new node to the dominator tree information.
///
/// This creates a new node as a child of DomBB dominator node, linking it
@@ -530,7 +576,7 @@ template <class NodeT> class DominatorTreeBase {
/// splitBlock - BB is split and now it has one successor. Update dominator
/// tree to reflect this change.
void splitBlock(NodeT *NewBB) {
- if (this->IsPostDominators)
+ if (IsPostDominator)
Split<Inverse<NodeT *>>(NewBB);
else
Split<NodeT *>(NewBB);
@@ -607,37 +653,33 @@ public:
template <class FT> void recalculate(FT &F) {
using TraitsTy = GraphTraits<FT *>;
reset();
+ Parent = &F;
- if (!this->IsPostDominators) {
+ if (!IsPostDominator) {
// Initialize root
NodeT *entry = TraitsTy::getEntryNode(&F);
addRoot(entry);
-
- DomTreeBuilder::Calculate<FT, NodeT *>(*this, F);
} else {
// Initialize the roots list
for (auto *Node : nodes(&F))
if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node))
addRoot(Node);
-
- DomTreeBuilder::Calculate<FT, Inverse<NodeT *>>(*this, F);
}
+
+ DomTreeBuilder::Calculate(*this, F);
}
/// verify - check parent and sibling property
- bool verify() const {
- return this->isPostDominator()
- ? DomTreeBuilder::Verify<Inverse<NodeT *>>(*this)
- : DomTreeBuilder::Verify<NodeT *>(*this);
- }
+ bool verify() const { return DomTreeBuilder::Verify(*this); }
protected:
void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
void reset() {
DomTreeNodes.clear();
- this->Roots.clear();
+ Roots.clear();
RootNode = nullptr;
+ Parent = nullptr;
DFSInfoValid = false;
SlowQueries = 0;
}
@@ -719,13 +761,21 @@ public:
void wipe() {
DomTreeNodes.clear();
RootNode = nullptr;
+ Parent = nullptr;
}
};
+template <typename T>
+using DomTreeBase = DominatorTreeBase<T, false>;
+
+template <typename T>
+using PostDomTreeBase = DominatorTreeBase<T, true>;
+
// These two functions are declared out of line as a workaround for building
// with old (< r147295) versions of clang because of pr11642.
-template <class NodeT>
-bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const {
+template <typename NodeT, bool IsPostDom>
+bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
+ const NodeT *B) const {
if (A == B)
return true;
@@ -735,9 +785,9 @@ bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const {
return dominates(getNode(const_cast<NodeT *>(A)),
getNode(const_cast<NodeT *>(B)));
}
-template <class NodeT>
-bool DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A,
- const NodeT *B) const {
+template <typename NodeT, bool IsPostDom>
+bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
+ const NodeT *A, const NodeT *B) const {
if (A == B)
return false;
diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h
index a0fec668e05ca..be90afa4c3c8e 100644
--- a/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/include/llvm/Support/GenericDomTreeConstruction.h
@@ -20,15 +20,28 @@
/// out that the theoretically slower O(n*log(n)) implementation is actually
/// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
///
+/// The file uses the Depth Based Search algorithm to perform incremental
+/// upates (insertion and deletions). The implemented algorithm is based on this
+/// publication:
+///
+/// An Experimental Study of Dynamic Dominators
+/// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10:
+/// https://arxiv.org/pdf/1604.02711.pdf
+///
//===----------------------------------------------------------------------===//
#ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
#define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
+#include <queue>
+#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/Debug.h"
#include "llvm/Support/GenericDomTree.h"
+#define DEBUG_TYPE "dom-tree-builder"
+
namespace llvm {
namespace DomTreeBuilder {
@@ -46,13 +59,14 @@ struct ChildrenGetter<NodePtr, true> {
}
};
-// Information record used by Semi-NCA during tree construction.
-template <typename NodeT>
+template <typename DomTreeT>
struct SemiNCAInfo {
- using NodePtr = NodeT *;
- using DomTreeT = DominatorTreeBase<NodeT>;
+ using NodePtr = typename DomTreeT::NodePtr;
+ using NodeT = typename DomTreeT::NodeType;
using TreeNodePtr = DomTreeNodeBase<NodeT> *;
+ static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
+ // Information record used by Semi-NCA during tree construction.
struct InfoRec {
unsigned DFSNum = 0;
unsigned Parent = 0;
@@ -62,11 +76,13 @@ struct SemiNCAInfo {
SmallVector<NodePtr, 2> ReverseChildren;
};
- std::vector<NodePtr> NumToNode;
+ // Number to node mapping is 1-based. Initialize the mapping to start with
+ // a dummy element.
+ std::vector<NodePtr> NumToNode = {nullptr};
DenseMap<NodePtr, InfoRec> NodeToInfo;
void clear() {
- NumToNode.clear();
+ NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
NodeToInfo.clear();
}
@@ -90,12 +106,28 @@ struct SemiNCAInfo {
// Add a new tree node for this NodeT, and link it as a child of
// IDomNode
return (DT.DomTreeNodes[BB] = IDomNode->addChild(
- llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
+ llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
.get();
}
static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
+ struct BlockNamePrinter {
+ NodePtr N;
+
+ BlockNamePrinter(NodePtr Block) : N(Block) {}
+ BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {}
+
+ friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {
+ if (!BP.N)
+ O << "nullptr";
+ else
+ BP.N->printAsOperand(O, false);
+
+ return O;
+ }
+ };
+
// Custom DFS implementation which can skip nodes based on a provided
// predicate. It also collects ReverseChildren so that we don't have to spend
// time getting predecessors in SemiNCA.
@@ -177,44 +209,42 @@ struct SemiNCAInfo {
return VInInfo.Label;
}
- template <typename NodeType>
- void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) {
- // Step #1: Number blocks in depth-first order and initialize variables used
- // in later stages of the algorithm.
- const unsigned N = doFullDFSWalk(DT, AlwaysDescend);
-
- // It might be that some blocks did not get a DFS number (e.g., blocks of
- // infinite loops). In these cases an artificial exit node is required.
- const bool MultipleRoots =
- DT.Roots.size() > 1 || (DT.isPostDominator() && N != NumBlocks);
-
+ // This function requires DFS to be run before calling it.
+ void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
+ const unsigned NextDFSNum(NumToNode.size());
// Initialize IDoms to spanning tree parents.
- for (unsigned i = 1; i <= N; ++i) {
+ for (unsigned i = 1; i < NextDFSNum; ++i) {
const NodePtr V = NumToNode[i];
auto &VInfo = NodeToInfo[V];
VInfo.IDom = NumToNode[VInfo.Parent];
}
- // Step #2: Calculate the semidominators of all vertices.
- for (unsigned i = N; i >= 2; --i) {
+ // Step #1: Calculate the semidominators of all vertices.
+ for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
NodePtr W = NumToNode[i];
auto &WInfo = NodeToInfo[W];
// Initialize the semi dominator to point to the parent node.
WInfo.Semi = WInfo.Parent;
- for (const auto &N : WInfo.ReverseChildren)
- if (NodeToInfo.count(N)) { // Only if this predecessor is reachable!
- unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
- if (SemiU < WInfo.Semi)
- WInfo.Semi = SemiU;
- }
+ for (const auto &N : WInfo.ReverseChildren) {
+ if (NodeToInfo.count(N) == 0) // Skip unreachable predecessors.
+ continue;
+
+ const TreeNodePtr TN = DT.getNode(N);
+ // Skip predecessors whose level is above the subtree we are processing.
+ if (TN && TN->getLevel() < MinLevel)
+ continue;
+
+ unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
+ if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
+ }
}
- // Step #3: Explicitly define the immediate dominator of each vertex.
+ // Step #2: Explicitly define the immediate dominator of each vertex.
// IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
// Note that the parents were stored in IDoms and later got invalidated
// during path compression in Eval.
- for (unsigned i = 2; i <= N; ++i) {
+ for (unsigned i = 2; i < NextDFSNum; ++i) {
const NodePtr W = NumToNode[i];
auto &WInfo = NodeToInfo[W];
const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
@@ -224,6 +254,36 @@ struct SemiNCAInfo {
WInfo.IDom = WIDomCandidate;
}
+ }
+
+ template <typename DescendCondition>
+ unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
+ unsigned Num = 0;
+
+ if (DT.Roots.size() > 1) {
+ auto &BBInfo = NodeToInfo[nullptr];
+ BBInfo.DFSNum = BBInfo.Semi = ++Num;
+ BBInfo.Label = nullptr;
+
+ NumToNode.push_back(nullptr); // NumToNode[n] = V;
+ }
+
+ if (DT.isPostDominator()) {
+ for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
+ } else {
+ assert(DT.Roots.size() == 1);
+ Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
+ }
+
+ return Num;
+ }
+
+ void calculateFromScratch(DomTreeT &DT, const unsigned NumBlocks) {
+ // Step #0: Number blocks in depth-first order and initialize variables used
+ // in later stages of the algorithm.
+ const unsigned LastDFSNum = doFullDFSWalk(DT, AlwaysDescend);
+
+ runSemiNCA(DT);
if (DT.Roots.empty()) return;
@@ -231,25 +291,32 @@ struct SemiNCAInfo {
// one exit block, or it may be the virtual exit (denoted by
// (BasicBlock *)0) which postdominates all real exits if there are multiple
// exit blocks, or an infinite loop.
+ // It might be that some blocks did not get a DFS number (e.g., blocks of
+ // infinite loops). In these cases an artificial exit node is required.
+ const bool MultipleRoots = DT.Roots.size() > 1 || (DT.isPostDominator() &&
+ LastDFSNum != NumBlocks);
NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
- DT.RootNode =
- (DT.DomTreeNodes[Root] =
- llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
- .get();
+ DT.RootNode = (DT.DomTreeNodes[Root] =
+ llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
+ .get();
+ attachNewSubtree(DT, DT.RootNode);
+ }
- // Loop over all of the reachable blocks in the function...
- for (unsigned i = 2; i <= N; ++i) {
+ void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
+ // Attach the first unreachable block to AttachTo.
+ NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
+ // Loop over all of the discovered blocks in the function...
+ for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
NodePtr W = NumToNode[i];
+ DEBUG(dbgs() << "\tdiscovered a new reachable node "
+ << BlockNamePrinter(W) << "\n");
// Don't replace this with 'count', the insertion side effect is important
- if (DT.DomTreeNodes[W])
- continue; // Haven't calculated this node yet?
+ if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet?
NodePtr ImmDom = getIDom(W);
- assert(ImmDom || DT.DomTreeNodes[nullptr]);
-
// Get or calculate the node for the immediate dominator
TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
@@ -260,34 +327,208 @@ struct SemiNCAInfo {
}
}
- template <typename DescendCondition>
- unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
- unsigned Num = 0;
- NumToNode.push_back(nullptr);
+ void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
+ NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
+ for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
+ const NodePtr N = NumToNode[i];
+ const TreeNodePtr TN = DT.getNode(N);
+ assert(TN);
+ const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
+ TN->setIDom(NewIDom);
+ }
+ }
- if (DT.Roots.size() > 1) {
- auto &BBInfo = NodeToInfo[nullptr];
- BBInfo.DFSNum = BBInfo.Semi = ++Num;
- BBInfo.Label = nullptr;
+ // Helper struct used during edge insertions.
+ struct InsertionInfo {
+ using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
+ struct DecreasingLevel {
+ bool operator()(const BucketElementTy &First,
+ const BucketElementTy &Second) const {
+ 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;
+ SmallDenseSet<TreeNodePtr, 8> Visited;
+ SmallVector<TreeNodePtr, 8> AffectedQueue;
+ SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
+ };
- NumToNode.push_back(nullptr); // NumToNode[n] = V;
+ static void InsertEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) {
+ assert(From && To && "Cannot connect nullptrs");
+ DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
+ << BlockNamePrinter(To) << "\n");
+ const TreeNodePtr FromTN = DT.getNode(From);
+
+ // Ignore edges from unreachable nodes.
+ if (!FromTN) return;
+
+ DT.DFSInfoValid = false;
+
+ const TreeNodePtr ToTN = DT.getNode(To);
+ if (!ToTN)
+ InsertUnreachable(DT, FromTN, To);
+ else
+ InsertReachable(DT, FromTN, ToTN);
+ }
+
+ // Handles insertion to a node already in the dominator tree.
+ static void InsertReachable(DomTreeT &DT, const TreeNodePtr From,
+ const TreeNodePtr To) {
+ DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
+ << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
+ const NodePtr NCDBlock =
+ DT.findNearestCommonDominator(From->getBlock(), To->getBlock());
+ assert(NCDBlock || DT.isPostDominator());
+ const TreeNodePtr NCD = DT.getNode(NCDBlock);
+ assert(NCD);
+
+ DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
+ const TreeNodePtr ToIDom = To->getIDom();
+
+ // Nothing affected -- NCA property holds.
+ // (Based on the lemma 2.5 from the second paper.)
+ if (NCD == To || NCD == ToIDom) return;
+
+ // Identify and collect affected nodes.
+ InsertionInfo II;
+ DEBUG(dbgs() << "Marking " << BlockNamePrinter(To) << " as affected\n");
+ II.Affected.insert(To);
+ const unsigned ToLevel = To->getLevel();
+ DEBUG(dbgs() << "Putting " << BlockNamePrinter(To) << " into a Bucket\n");
+ II.Bucket.push({ToLevel, To});
+
+ while (!II.Bucket.empty()) {
+ const TreeNodePtr CurrentNode = II.Bucket.top().second;
+ II.Bucket.pop();
+ DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
+ << BlockNamePrinter(CurrentNode) << "\n");
+ II.Visited.insert(CurrentNode);
+ II.AffectedQueue.push_back(CurrentNode);
+
+ // Discover and collect affected successors of the current node.
+ VisitInsertion(DT, CurrentNode, CurrentNode->getLevel(), NCD, II);
}
- if (DT.isPostDominator()) {
- for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
- } else {
- assert(DT.Roots.size() == 1);
- Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
+ // Finish by updating immediate dominators and levels.
+ UpdateInsertion(DT, NCD, II);
+ }
+
+ // Visits an affected node and collect its affected successors.
+ static void VisitInsertion(DomTreeT &DT, const TreeNodePtr TN,
+ const unsigned RootLevel, const TreeNodePtr NCD,
+ InsertionInfo &II) {
+ const unsigned NCDLevel = NCD->getLevel();
+ DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << "\n");
+
+ assert(TN->getBlock());
+ for (const NodePtr Succ :
+ ChildrenGetter<NodePtr, IsPostDom>::Get(TN->getBlock())) {
+ const TreeNodePtr SuccTN = DT.getNode(Succ);
+ assert(SuccTN && "Unreachable successor found at reachable insertion");
+ const unsigned SuccLevel = SuccTN->getLevel();
+
+ DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
+ << ", level = " << SuccLevel << "\n");
+
+ // Succ dominated by subtree From -- not affected.
+ // (Based on the lemma 2.5 from the second paper.)
+ if (SuccLevel > RootLevel) {
+ DEBUG(dbgs() << "\t\tDominated by subtree From\n");
+ if (II.Visited.count(SuccTN) != 0) continue;
+
+ DEBUG(dbgs() << "\t\tMarking visited not affected "
+ << BlockNamePrinter(Succ) << "\n");
+ II.Visited.insert(SuccTN);
+ II.VisitedNotAffectedQueue.push_back(SuccTN);
+ VisitInsertion(DT, SuccTN, RootLevel, NCD, II);
+ } else if ((SuccLevel > NCDLevel + 1) && II.Affected.count(SuccTN) == 0) {
+ DEBUG(dbgs() << "\t\tMarking affected and adding "
+ << BlockNamePrinter(Succ) << " to a Bucket\n");
+ II.Affected.insert(SuccTN);
+ II.Bucket.push({SuccLevel, SuccTN});
+ }
}
+ }
- return Num;
+ // Updates immediate dominators and levels after insertion.
+ static void UpdateInsertion(DomTreeT &DT, const TreeNodePtr NCD,
+ InsertionInfo &II) {
+ DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
+
+ for (const TreeNodePtr TN : II.AffectedQueue) {
+ DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
+ << ") = " << BlockNamePrinter(NCD) << "\n");
+ TN->setIDom(NCD);
+ }
+
+ UpdateLevelsAfterInsertion(II);
}
- static void PrintBlockOrNullptr(raw_ostream &O, NodePtr Obj) {
- if (!Obj)
- O << "nullptr";
- else
- Obj->printAsOperand(O, false);
+ static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
+ DEBUG(dbgs() << "Updating levels for visited but not affected nodes\n");
+
+ for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
+ DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
+ << BlockNamePrinter(TN->getIDom()) << ") "
+ << TN->getIDom()->getLevel() << " + 1\n");
+ TN->UpdateLevel();
+ }
+ }
+
+ // Handles insertion to previously unreachable nodes.
+ static void InsertUnreachable(DomTreeT &DT, const TreeNodePtr From,
+ const NodePtr To) {
+ DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
+ << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
+
+ // Collect discovered edges to already reachable nodes.
+ SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
+ // Discover and connect nodes that became reachable with the insertion.
+ ComputeUnreachableDominators(DT, To, From, DiscoveredEdgesToReachable);
+
+ DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
+ << " -> (prev unreachable) " << BlockNamePrinter(To) << "\n");
+
+ DEBUG(DT.print(dbgs()));
+
+ // Used the discovered edges and inset discovered connecting (incoming)
+ // edges.
+ for (const auto &Edge : DiscoveredEdgesToReachable) {
+ DEBUG(dbgs() << "\tInserting discovered connecting edge "
+ << BlockNamePrinter(Edge.first) << " -> "
+ << BlockNamePrinter(Edge.second) << "\n");
+ InsertReachable(DT, DT.getNode(Edge.first), Edge.second);
+ }
+ }
+
+ // Connects nodes that become reachable with an insertion.
+ static void ComputeUnreachableDominators(
+ DomTreeT &DT, const NodePtr Root, const TreeNodePtr Incoming,
+ SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
+ &DiscoveredConnectingEdges) {
+ assert(!DT.getNode(Root) && "Root must not be reachable");
+
+ // Visit only previously unreachable nodes.
+ auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
+ NodePtr To) {
+ const TreeNodePtr ToTN = DT.getNode(To);
+ if (!ToTN) return true;
+
+ DiscoveredConnectingEdges.push_back({From, ToTN});
+ return false;
+ };
+
+ SemiNCAInfo SNCA;
+ SNCA.runDFS<IsPostDom>(Root, 0, UnreachableDescender, 0);
+ SNCA.runSemiNCA(DT);
+ SNCA.attachNewSubtree(DT, Incoming);
+
+ DEBUG(dbgs() << "After adding unreachable nodes\n");
+ DEBUG(DT.print(dbgs()));
}
// Checks if the tree contains all reachable nodes in the input graph.
@@ -298,12 +539,23 @@ struct SemiNCAInfo {
for (auto &NodeToTN : DT.DomTreeNodes) {
const TreeNodePtr TN = NodeToTN.second.get();
const NodePtr BB = TN->getBlock();
- if (!BB) continue;
+
+ // Virtual root has a corresponding virtual CFG node.
+ if (DT.isVirtualRoot(TN)) continue;
if (NodeToInfo.count(BB) == 0) {
- errs() << "DomTree node ";
- PrintBlockOrNullptr(errs(), BB);
- errs() << " not found by DFS walk!\n";
+ errs() << "DomTree node " << BlockNamePrinter(BB)
+ << " not found by DFS walk!\n";
+ errs().flush();
+
+ return false;
+ }
+ }
+
+ for (const NodePtr N : NumToNode) {
+ if (N && !DT.getNode(N)) {
+ errs() << "CFG node " << BlockNamePrinter(N)
+ << " not found in the DomTree!\n";
errs().flush();
return false;
@@ -313,6 +565,215 @@ struct SemiNCAInfo {
return true;
}
+ static void DeleteEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) {
+ assert(From && To && "Cannot disconnect nullptrs");
+ DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
+ << BlockNamePrinter(To) << "\n");
+
+#ifndef NDEBUG
+ // Ensure that the edge was in fact deleted from the CFG before informing
+ // the DomTree about it.
+ // The check is O(N), so run it only in debug configuration.
+ auto IsSuccessor = [](const NodePtr SuccCandidate, const NodePtr Of) {
+ auto Successors = ChildrenGetter<NodePtr, IsPostDom>::Get(Of);
+ return llvm::find(Successors, SuccCandidate) != Successors.end();
+ };
+ (void)IsSuccessor;
+ assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
+#endif
+
+ const TreeNodePtr FromTN = DT.getNode(From);
+ // Deletion in an unreachable subtree -- nothing to do.
+ if (!FromTN) return;
+
+ const TreeNodePtr ToTN = DT.getNode(To);
+ assert(ToTN && "To already unreachable -- there is no edge to delete");
+ const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
+ const TreeNodePtr NCD = DT.getNode(NCDBlock);
+
+ // To dominates From -- nothing to do.
+ if (ToTN == NCD) return;
+
+ const TreeNodePtr ToIDom = ToTN->getIDom();
+ DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
+ << BlockNamePrinter(ToIDom) << "\n");
+
+ // To remains reachable after deletion.
+ // (Based on the caption under Figure 4. from the second paper.)
+ if (FromTN != ToIDom || HasProperSupport(DT, ToTN))
+ DeleteReachable(DT, FromTN, ToTN);
+ else
+ DeleteUnreachable(DT, ToTN);
+ }
+
+ // Handles deletions that leave destination nodes reachable.
+ static void DeleteReachable(DomTreeT &DT, const TreeNodePtr FromTN,
+ const TreeNodePtr ToTN) {
+ DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> "
+ << BlockNamePrinter(ToTN) << "\n");
+ DEBUG(dbgs() << "\tRebuilding subtree\n");
+
+ // Find the top of the subtree that needs to be rebuilt.
+ // (Based on the lemma 2.6 from the second paper.)
+ const NodePtr ToIDom =
+ DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
+ assert(ToIDom || DT.isPostDominator());
+ const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
+ assert(ToIDomTN);
+ const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
+ // Top of the subtree to rebuild is the root node. Rebuild the tree from
+ // scratch.
+ if (!PrevIDomSubTree) {
+ DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
+ DT.recalculate(*DT.Parent);
+ return;
+ }
+
+ // Only visit nodes in the subtree starting at To.
+ const unsigned Level = ToIDomTN->getLevel();
+ auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
+ return DT.getNode(To)->getLevel() > Level;
+ };
+
+ DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n");
+
+ SemiNCAInfo SNCA;
+ SNCA.runDFS<IsPostDom>(ToIDom, 0, DescendBelow, 0);
+ DEBUG(dbgs() << "\tRunning Semi-NCA\n");
+ SNCA.runSemiNCA(DT, Level);
+ SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
+ }
+
+ // Checks if a node has proper support, as defined on the page 3 and later
+ // explained on the page 7 of the second paper.
+ static bool HasProperSupport(DomTreeT &DT, const TreeNodePtr TN) {
+ DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n");
+ for (const NodePtr Pred :
+ ChildrenGetter<NodePtr, !IsPostDom>::Get(TN->getBlock())) {
+ DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
+ if (!DT.getNode(Pred)) continue;
+
+ const NodePtr Support =
+ DT.findNearestCommonDominator(TN->getBlock(), Pred);
+ DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
+ if (Support != TN->getBlock()) {
+ DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
+ << " is reachable from support "
+ << BlockNamePrinter(Support) << "\n");
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ // Handle deletions that make destination node unreachable.
+ // (Based on the lemma 2.7 from the second paper.)
+ static void DeleteUnreachable(DomTreeT &DT, const TreeNodePtr ToTN) {
+ DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN)
+ << "\n");
+ assert(ToTN);
+ assert(ToTN->getBlock());
+
+ SmallVector<NodePtr, 16> AffectedQueue;
+ const unsigned Level = ToTN->getLevel();
+
+ // Traverse destination node's descendants with greater level in the tree
+ // and collect visited nodes.
+ auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
+ const TreeNodePtr TN = DT.getNode(To);
+ assert(TN);
+ if (TN->getLevel() > Level) return true;
+ if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
+ AffectedQueue.push_back(To);
+
+ return false;
+ };
+
+ SemiNCAInfo SNCA;
+ unsigned LastDFSNum =
+ SNCA.runDFS<IsPostDom>(ToTN->getBlock(), 0, DescendAndCollect, 0);
+
+ TreeNodePtr MinNode = ToTN;
+
+ // Identify the top of the subtree to rebuilt by finding the NCD of all
+ // the affected nodes.
+ for (const NodePtr N : AffectedQueue) {
+ const TreeNodePtr TN = DT.getNode(N);
+ const NodePtr NCDBlock =
+ DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
+ assert(NCDBlock || DT.isPostDominator());
+ const TreeNodePtr NCD = DT.getNode(NCDBlock);
+ assert(NCD);
+
+ DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
+ << " with NCD = " << BlockNamePrinter(NCD)
+ << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
+ if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
+ }
+
+ // Root reached, rebuild the whole tree from scratch.
+ if (!MinNode->getIDom()) {
+ DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
+ DT.recalculate(*DT.Parent);
+ return;
+ }
+
+ // Erase the unreachable subtree in reverse preorder to process all children
+ // before deleting their parent.
+ for (unsigned i = LastDFSNum; i > 0; --i) {
+ const NodePtr N = SNCA.NumToNode[i];
+ const TreeNodePtr TN = DT.getNode(N);
+ DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
+
+ EraseNode(DT, TN);
+ }
+
+ // The affected subtree start at the To node -- there's no extra work to do.
+ if (MinNode == ToTN) return;
+
+ DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
+ << BlockNamePrinter(MinNode) << "\n");
+ const unsigned MinLevel = MinNode->getLevel();
+ const TreeNodePtr PrevIDom = MinNode->getIDom();
+ assert(PrevIDom);
+ SNCA.clear();
+
+ // Identify nodes that remain in the affected subtree.
+ auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
+ const TreeNodePtr ToTN = DT.getNode(To);
+ return ToTN && ToTN->getLevel() > MinLevel;
+ };
+ SNCA.runDFS<IsPostDom>(MinNode->getBlock(), 0, DescendBelow, 0);
+
+ DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom)
+ << "\nRunning Semi-NCA\n");
+
+ // Rebuild the remaining part of affected subtree.
+ SNCA.runSemiNCA(DT, MinLevel);
+ SNCA.reattachExistingSubtree(DT, PrevIDom);
+ }
+
+ // Removes leaf tree nodes from the dominator tree.
+ static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
+ assert(TN);
+ assert(TN->getNumChildren() == 0 && "Not a tree leaf");
+
+ const TreeNodePtr IDom = TN->getIDom();
+ assert(IDom);
+
+ auto ChIt = llvm::find(IDom->Children, TN);
+ assert(ChIt != IDom->Children.end());
+ std::swap(*ChIt, IDom->Children.back());
+ IDom->Children.pop_back();
+
+ DT.DomTreeNodes.erase(TN->getBlock());
+ }
+
+ //~~
+ //===--------------- DomTree correctness verification ---------------------===
+ //~~
+
// Check if for every parent with a level L in the tree all of its children
// have level L + 1.
static bool VerifyLevels(const DomTreeT &DT) {
@@ -323,20 +784,18 @@ struct SemiNCAInfo {
const TreeNodePtr IDom = TN->getIDom();
if (!IDom && TN->getLevel() != 0) {
- errs() << "Node without an IDom ";
- PrintBlockOrNullptr(errs(), BB);
- errs() << " has a nonzero level " << TN->getLevel() << "!\n";
+ errs() << "Node without an IDom " << BlockNamePrinter(BB)
+ << " has a nonzero level " << TN->getLevel() << "!\n";
errs().flush();
return false;
}
if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
- errs() << "Node ";
- PrintBlockOrNullptr(errs(), BB);
- errs() << " has level " << TN->getLevel() << " while it's IDom ";
- PrintBlockOrNullptr(errs(), IDom->getBlock());
- errs() << " has level " << IDom->getLevel() << "!\n";
+ errs() << "Node " << BlockNamePrinter(BB) << " has level "
+ << TN->getLevel() << " while its IDom "
+ << BlockNamePrinter(IDom->getBlock()) << " has level "
+ << IDom->getLevel() << "!\n";
errs().flush();
return false;
@@ -363,18 +822,14 @@ struct SemiNCAInfo {
assert(ToTN);
const NodePtr NCD = DT.findNearestCommonDominator(From, To);
- const TreeNodePtr NCDTN = NCD ? DT.getNode(NCD) : nullptr;
+ const TreeNodePtr NCDTN = DT.getNode(NCD);
const TreeNodePtr ToIDom = ToTN->getIDom();
if (NCDTN != ToTN && NCDTN != ToIDom) {
- errs() << "NearestCommonDominator verification failed:\n\tNCD(From:";
- PrintBlockOrNullptr(errs(), From);
- errs() << ", To:";
- PrintBlockOrNullptr(errs(), To);
- errs() << ") = ";
- PrintBlockOrNullptr(errs(), NCD);
- errs() << ",\t (should be To or IDom[To]: ";
- PrintBlockOrNullptr(errs(), ToIDom ? ToIDom->getBlock() : nullptr);
- errs() << ")\n";
+ errs() << "NearestCommonDominator verification failed:\n\tNCD(From:"
+ << BlockNamePrinter(From) << ", To:" << BlockNamePrinter(To)
+ << ") = " << BlockNamePrinter(NCD)
+ << ",\t (should be To or IDom[To]: " << BlockNamePrinter(ToIDom)
+ << ")\n";
errs().flush();
return false;
@@ -440,11 +895,9 @@ struct SemiNCAInfo {
for (TreeNodePtr Child : TN->getChildren())
if (NodeToInfo.count(Child->getBlock()) != 0) {
- errs() << "Child ";
- PrintBlockOrNullptr(errs(), Child->getBlock());
- errs() << " reachable after its parent ";
- PrintBlockOrNullptr(errs(), BB);
- errs() << " is removed!\n";
+ errs() << "Child " << BlockNamePrinter(Child)
+ << " reachable after its parent " << BlockNamePrinter(BB)
+ << " is removed!\n";
errs().flush();
return false;
@@ -477,11 +930,9 @@ struct SemiNCAInfo {
if (S == N) continue;
if (NodeToInfo.count(S->getBlock()) == 0) {
- errs() << "Node ";
- PrintBlockOrNullptr(errs(), S->getBlock());
- errs() << " not reachable when its sibling ";
- PrintBlockOrNullptr(errs(), N->getBlock());
- errs() << " is removed!\n";
+ errs() << "Node " << BlockNamePrinter(S)
+ << " not reachable when its sibling " << BlockNamePrinter(N)
+ << " is removed!\n";
errs().flush();
return false;
@@ -494,23 +945,30 @@ struct SemiNCAInfo {
}
};
-template <class FuncT, class NodeT>
-void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
- FuncT &F) {
- using NodePtr = typename GraphTraits<NodeT>::NodeRef;
- static_assert(std::is_pointer<NodePtr>::value,
- "NodePtr should be a pointer type");
- SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
- SNCA.template runSemiNCA<NodeT>(DT, GraphTraits<FuncT *>::size(&F));
+
+template <class DomTreeT, class FuncT>
+void Calculate(DomTreeT &DT, FuncT &F) {
+ SemiNCAInfo<DomTreeT> SNCA;
+ SNCA.calculateFromScratch(DT, GraphTraits<FuncT *>::size(&F));
}
-template <class NodeT>
-bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
- using NodePtr = typename GraphTraits<NodeT>::NodeRef;
- static_assert(std::is_pointer<NodePtr>::value,
- "NodePtr should be a pointer type");
- SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
+template <class DomTreeT>
+void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
+ typename DomTreeT::NodePtr To) {
+ if (DT.isPostDominator()) std::swap(From, To);
+ SemiNCAInfo<DomTreeT>::InsertEdge(DT, From, To);
+}
+
+template <class DomTreeT>
+void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
+ typename DomTreeT::NodePtr To) {
+ if (DT.isPostDominator()) std::swap(From, To);
+ SemiNCAInfo<DomTreeT>::DeleteEdge(DT, From, To);
+}
+template <class DomTreeT>
+bool Verify(const DomTreeT &DT) {
+ SemiNCAInfo<DomTreeT> SNCA;
return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) &&
SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) &&
SNCA.verifySiblingProperty(DT);
@@ -519,4 +977,6 @@ bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
} // namespace DomTreeBuilder
} // namespace llvm
+#undef DEBUG_TYPE
+
#endif
diff --git a/include/llvm/Support/TargetParser.h b/include/llvm/Support/TargetParser.h
index 72c28865ac575..e13582f6a6d3d 100644
--- a/include/llvm/Support/TargetParser.h
+++ b/include/llvm/Support/TargetParser.h
@@ -85,6 +85,7 @@ enum ArchExtKind : unsigned {
AEK_DSP = 0x400,
AEK_FP16 = 0x800,
AEK_RAS = 0x1000,
+ AEK_SVE = 0x2000,
// Unsupported extensions.
AEK_OS = 0x8000000,
AEK_IWMMXT = 0x10000000,
@@ -166,7 +167,8 @@ enum ArchExtKind : unsigned {
AEK_FP16 = 0x20,
AEK_PROFILE = 0x40,
AEK_RAS = 0x80,
- AEK_LSE = 0x100
+ AEK_LSE = 0x100,
+ AEK_SVE = 0x200
};
StringRef getCanonicalArchName(StringRef Arch);
diff --git a/include/llvm/Support/YAMLTraits.h b/include/llvm/Support/YAMLTraits.h
index 15b3b11db0451..71fdf47f1979a 100644
--- a/include/llvm/Support/YAMLTraits.h
+++ b/include/llvm/Support/YAMLTraits.h
@@ -1114,6 +1114,10 @@ public:
void *Ctxt = nullptr,
SourceMgr::DiagHandlerTy DiagHandler = nullptr,
void *DiagHandlerCtxt = nullptr);
+ Input(MemoryBufferRef Input,
+ void *Ctxt = nullptr,
+ SourceMgr::DiagHandlerTy DiagHandler = nullptr,
+ void *DiagHandlerCtxt = nullptr);
~Input() override;
// Check if there was an syntax or semantic error during parsing.
generated by cgit v1.2.3 (git 2.25.1) at 2025-06-18 04:52:30 +0000