Update prebuilt Clang to r416183b from Android.
https://android.googlesource.com/platform/prebuilts/clang/host/
linux-x86/+/06a71ddac05c22edb2d10b590e1769b3f8619bef
clang 12.0.5 (based on r416183b) from build 7284624.
Change-Id: I277a316abcf47307562d8b748b84870f31a72866
Signed-off-by: Olivier Deprez <olivier.deprez@arm.com>
diff --git a/linux-x64/clang/include/llvm/Support/GenericDomTree.h b/linux-x64/clang/include/llvm/Support/GenericDomTree.h
index 9962080..28b2537 100644
--- a/linux-x64/clang/include/llvm/Support/GenericDomTree.h
+++ b/linux-x64/clang/include/llvm/Support/GenericDomTree.h
@@ -25,10 +25,10 @@
#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/CFGDiff.h"
#include "llvm/Support/CFGUpdate.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
@@ -38,7 +38,6 @@
#include <memory>
#include <type_traits>
#include <utility>
-#include <vector>
namespace llvm {
@@ -61,7 +60,7 @@
NodeT *TheBB;
DomTreeNodeBase *IDom;
unsigned Level;
- std::vector<DomTreeNodeBase *> Children;
+ SmallVector<DomTreeNodeBase *, 4> Children;
mutable unsigned DFSNumIn = ~0;
mutable unsigned DFSNumOut = ~0;
@@ -69,27 +68,34 @@
DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
: TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
- using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
+ using iterator = typename SmallVector<DomTreeNodeBase *, 4>::iterator;
using const_iterator =
- typename std::vector<DomTreeNodeBase *>::const_iterator;
+ typename SmallVector<DomTreeNodeBase *, 4>::const_iterator;
iterator begin() { return Children.begin(); }
iterator end() { return Children.end(); }
const_iterator begin() const { return Children.begin(); }
const_iterator end() const { return Children.end(); }
+ DomTreeNodeBase *const &back() const { return Children.back(); }
+ DomTreeNodeBase *&back() { return Children.back(); }
+
+ iterator_range<iterator> children() { return make_range(begin(), end()); }
+ iterator_range<const_iterator> children() const {
+ return make_range(begin(), end());
+ }
+
NodeT *getBlock() const { return TheBB; }
DomTreeNodeBase *getIDom() const { return IDom; }
unsigned getLevel() const { return Level; }
- const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
-
std::unique_ptr<DomTreeNodeBase> addChild(
std::unique_ptr<DomTreeNodeBase> C) {
Children.push_back(C.get());
return C;
}
+ bool isLeaf() const { return Children.empty(); }
size_t getNumChildren() const { return Children.size(); }
void clearAllChildren() { Children.clear(); }
@@ -205,7 +211,10 @@
template <typename DomTreeT>
void ApplyUpdates(DomTreeT &DT,
- ArrayRef<typename DomTreeT::UpdateType> Updates);
+ GraphDiff<typename DomTreeT::NodePtr,
+ DomTreeT::IsPostDominator> &PreViewCFG,
+ GraphDiff<typename DomTreeT::NodePtr,
+ DomTreeT::IsPostDominator> *PostViewCFG);
template <typename DomTreeT>
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
@@ -225,7 +234,7 @@
using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
static_assert(std::is_pointer<ParentPtr>::value,
"Currently NodeT's parent must be a pointer type");
- using ParentType = typename std::remove_pointer<ParentPtr>::type;
+ using ParentType = std::remove_pointer_t<ParentPtr>;
static constexpr bool IsPostDominator = IsPostDom;
using UpdateType = cfg::Update<NodePtr>;
@@ -242,7 +251,7 @@
using DomTreeNodeMapType =
DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
DomTreeNodeMapType DomTreeNodes;
- DomTreeNodeBase<NodeT> *RootNode;
+ DomTreeNodeBase<NodeT> *RootNode = nullptr;
ParentPtr Parent = nullptr;
mutable bool DFSInfoValid = false;
@@ -277,11 +286,27 @@
DominatorTreeBase(const DominatorTreeBase &) = delete;
DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
- /// getRoots - Return the root blocks of the current CFG. This may include
- /// multiple blocks if we are computing post dominators. For forward
- /// dominators, this will always be a single block (the entry node).
+ /// Iteration over roots.
///
- const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
+ /// This may include multiple blocks if we are computing post dominators.
+ /// For forward dominators, this will always be a single block (the entry
+ /// block).
+ using root_iterator = typename SmallVectorImpl<NodeT *>::iterator;
+ using const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator;
+
+ root_iterator root_begin() { return Roots.begin(); }
+ const_root_iterator root_begin() const { return Roots.begin(); }
+ root_iterator root_end() { return Roots.end(); }
+ const_root_iterator root_end() const { return Roots.end(); }
+
+ size_t root_size() const { return Roots.size(); }
+
+ iterator_range<root_iterator> roots() {
+ return make_range(root_begin(), root_end());
+ }
+ iterator_range<const_root_iterator> roots() const {
+ return make_range(root_begin(), root_end());
+ }
/// isPostDominator - Returns true if analysis based of postdoms
///
@@ -319,8 +344,6 @@
return false;
}
- void releaseMemory() { reset(); }
-
/// getNode - return the (Post)DominatorTree node for the specified basic
/// block. This is the same as using operator[] on this class. The result
/// may (but is not required to) be null for a forward (backwards)
@@ -440,8 +463,8 @@
return this->Roots[0];
}
- /// findNearestCommonDominator - Find nearest common dominator basic block
- /// for basic block A and B. If there is no such block then return nullptr.
+ /// Find nearest common dominator basic block for basic block A and B. A and B
+ /// must have tree nodes.
NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
assert(A && B && "Pointers are not valid");
assert(A->getParent() == B->getParent() &&
@@ -457,18 +480,18 @@
DomTreeNodeBase<NodeT> *NodeA = getNode(A);
DomTreeNodeBase<NodeT> *NodeB = getNode(B);
-
- if (!NodeA || !NodeB) return nullptr;
+ assert(NodeA && "A must be in the tree");
+ assert(NodeB && "B must be in the tree");
// Use level information to go up the tree until the levels match. Then
// continue going up til we arrive at the same node.
- while (NodeA && NodeA != NodeB) {
+ while (NodeA != NodeB) {
if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
NodeA = NodeA->IDom;
}
- return NodeA ? NodeA->getBlock() : nullptr;
+ return NodeA->getBlock();
}
const NodeT *findNearestCommonDominator(const NodeT *A,
@@ -515,10 +538,39 @@
/// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
/// with the same template parameter T.
///
- /// \param Updates An unordered sequence of updates to perform.
+ /// \param Updates An unordered sequence of updates to perform. The current
+ /// CFG and the reverse of these updates provides the pre-view of the CFG.
///
void applyUpdates(ArrayRef<UpdateType> Updates) {
- DomTreeBuilder::ApplyUpdates(*this, Updates);
+ GraphDiff<NodePtr, IsPostDominator> PreViewCFG(
+ Updates, /*ReverseApplyUpdates=*/true);
+ DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, nullptr);
+ }
+
+ /// \param Updates An unordered sequence of updates to perform. The current
+ /// CFG and the reverse of these updates provides the pre-view of the CFG.
+ /// \param PostViewUpdates An unordered sequence of update to perform in order
+ /// to obtain a post-view of the CFG. The DT will be updated assuming the
+ /// obtained PostViewCFG is the desired end state.
+ void applyUpdates(ArrayRef<UpdateType> Updates,
+ ArrayRef<UpdateType> PostViewUpdates) {
+ if (Updates.empty()) {
+ GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
+ DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG);
+ } else {
+ // PreViewCFG needs to merge Updates and PostViewCFG. The updates in
+ // Updates need to be reversed, and match the direction in PostViewCFG.
+ // The PostViewCFG is created with updates reversed (equivalent to changes
+ // made to the CFG), so the PreViewCFG needs all the updates reverse
+ // applied.
+ SmallVector<UpdateType> AllUpdates(Updates.begin(), Updates.end());
+ for (auto &Update : PostViewUpdates)
+ AllUpdates.push_back(Update);
+ GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates,
+ /*ReverseApplyUpdates=*/true);
+ GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
+ DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG);
+ }
}
/// Inform the dominator tree about a CFG edge insertion and update the tree.
@@ -570,8 +622,7 @@
DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
assert(IDomNode && "Not immediate dominator specified for block!");
DFSInfoValid = false;
- return (DomTreeNodes[BB] = IDomNode->addChild(
- llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
+ return createChild(BB, IDomNode);
}
/// Add a new node to the forward dominator tree and make it a new root.
@@ -584,8 +635,7 @@
assert(!this->isPostDominator() &&
"Cannot change root of post-dominator tree");
DFSInfoValid = false;
- DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
- llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
+ DomTreeNodeBase<NodeT> *NewNode = createNode(BB);
if (Roots.empty()) {
addRoot(BB);
} else {
@@ -620,7 +670,7 @@
void eraseNode(NodeT *BB) {
DomTreeNodeBase<NodeT> *Node = getNode(BB);
assert(Node && "Removing node that isn't in dominator tree.");
- assert(Node->getChildren().empty() && "Node is not a leaf node.");
+ assert(Node->isLeaf() && "Node is not a leaf node.");
DFSInfoValid = false;
@@ -754,9 +804,6 @@
return DomTreeBuilder::Verify(*this, VL);
}
-protected:
- void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
-
void reset() {
DomTreeNodes.clear();
Roots.clear();
@@ -766,6 +813,21 @@
SlowQueries = 0;
}
+protected:
+ void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
+
+ DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) {
+ return (DomTreeNodes[BB] = IDom->addChild(
+ std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom)))
+ .get();
+ }
+
+ DomTreeNodeBase<NodeT> *createNode(NodeT *BB) {
+ return (DomTreeNodes[BB] =
+ std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr))
+ .get();
+ }
+
// NewBB is split and now it has one successor. Update dominator tree to
// reflect this change.
template <class N>
@@ -777,14 +839,14 @@
"NewBB should have a single successor!");
NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
- std::vector<NodeRef> PredBlocks;
- for (const auto &Pred : children<Inverse<N>>(NewBB))
+ SmallVector<NodeRef, 4> PredBlocks;
+ for (auto Pred : children<Inverse<N>>(NewBB))
PredBlocks.push_back(Pred);
assert(!PredBlocks.empty() && "No predblocks?");
bool NewBBDominatesNewBBSucc = true;
- for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
+ for (auto Pred : children<Inverse<N>>(NewBBSucc)) {
if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
isReachableFromEntry(Pred)) {
NewBBDominatesNewBBSucc = false;