blob: 6e299263e66da24c2ed065e92377c6b6d7361c55 [file] [log] [blame]
//===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the DomTreeUpdater class, which provides a uniform way
// to update dominator tree related data structures.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Support/GenericDomTree.h"
#include <algorithm>
#include <functional>
#include <utility>
namespace llvm {
bool DomTreeUpdater::isUpdateValid(
const DominatorTree::UpdateType Update) const {
const auto *From = Update.getFrom();
const auto *To = Update.getTo();
const auto Kind = Update.getKind();
// Discard updates by inspecting the current state of successors of From.
// Since isUpdateValid() must be called *after* the Terminator of From is
// altered we can determine if the update is unnecessary for batch updates
// or invalid for a single update.
const bool HasEdge = llvm::is_contained(successors(From), To);
// If the IR does not match the update,
// 1. In batch updates, this update is unnecessary.
// 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
// Edge does not exist in IR.
if (Kind == DominatorTree::Insert && !HasEdge)
return false;
// Edge exists in IR.
if (Kind == DominatorTree::Delete && HasEdge)
return false;
return true;
}
bool DomTreeUpdater::isSelfDominance(
const DominatorTree::UpdateType Update) const {
// Won't affect DomTree and PostDomTree.
return Update.getFrom() == Update.getTo();
}
void DomTreeUpdater::applyDomTreeUpdates() {
// No pending DomTreeUpdates.
if (Strategy != UpdateStrategy::Lazy || !DT)
return;
// Only apply updates not are applied by DomTree.
if (hasPendingDomTreeUpdates()) {
const auto I = PendUpdates.begin() + PendDTUpdateIndex;
const auto E = PendUpdates.end();
assert(I < E && "Iterator range invalid; there should be DomTree updates.");
DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
PendDTUpdateIndex = PendUpdates.size();
}
}
void DomTreeUpdater::flush() {
applyDomTreeUpdates();
applyPostDomTreeUpdates();
dropOutOfDateUpdates();
}
void DomTreeUpdater::applyPostDomTreeUpdates() {
// No pending PostDomTreeUpdates.
if (Strategy != UpdateStrategy::Lazy || !PDT)
return;
// Only apply updates not are applied by PostDomTree.
if (hasPendingPostDomTreeUpdates()) {
const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
const auto E = PendUpdates.end();
assert(I < E &&
"Iterator range invalid; there should be PostDomTree updates.");
PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
PendPDTUpdateIndex = PendUpdates.size();
}
}
void DomTreeUpdater::tryFlushDeletedBB() {
if (!hasPendingUpdates())
forceFlushDeletedBB();
}
bool DomTreeUpdater::forceFlushDeletedBB() {
if (DeletedBBs.empty())
return false;
for (auto *BB : DeletedBBs) {
// After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
// validateDeleteBB() removes all instructions of DelBB and adds an
// UnreachableInst as its terminator. So we check whether the BasicBlock to
// delete only has an UnreachableInst inside.
assert(BB->getInstList().size() == 1 &&
isa<UnreachableInst>(BB->getTerminator()) &&
"DelBB has been modified while awaiting deletion.");
BB->removeFromParent();
eraseDelBBNode(BB);
delete BB;
}
DeletedBBs.clear();
Callbacks.clear();
return true;
}
void DomTreeUpdater::recalculate(Function &F) {
if (Strategy == UpdateStrategy::Eager) {
if (DT)
DT->recalculate(F);
if (PDT)
PDT->recalculate(F);
return;
}
// There is little performance gain if we pend the recalculation under
// Lazy UpdateStrategy so we recalculate available trees immediately.
// Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
// Because all trees are going to be up-to-date after recalculation,
// flush awaiting deleted BasicBlocks.
forceFlushDeletedBB();
if (DT)
DT->recalculate(F);
if (PDT)
PDT->recalculate(F);
// Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
dropOutOfDateUpdates();
}
bool DomTreeUpdater::hasPendingUpdates() const {
return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
}
bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
if (!DT)
return false;
return PendUpdates.size() != PendDTUpdateIndex;
}
bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
if (!PDT)
return false;
return PendUpdates.size() != PendPDTUpdateIndex;
}
bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
return false;
return DeletedBBs.contains(DelBB);
}
// The DT and PDT require the nodes related to updates
// are not deleted when update functions are called.
// So BasicBlock deletions must be pended when the
// UpdateStrategy is Lazy. When the UpdateStrategy is
// Eager, the BasicBlock will be deleted immediately.
void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
validateDeleteBB(DelBB);
if (Strategy == UpdateStrategy::Lazy) {
DeletedBBs.insert(DelBB);
return;
}
DelBB->removeFromParent();
eraseDelBBNode(DelBB);
delete DelBB;
}
void DomTreeUpdater::callbackDeleteBB(
BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
validateDeleteBB(DelBB);
if (Strategy == UpdateStrategy::Lazy) {
Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
DeletedBBs.insert(DelBB);
return;
}
DelBB->removeFromParent();
eraseDelBBNode(DelBB);
Callback(DelBB);
delete DelBB;
}
void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
if (DT && !IsRecalculatingDomTree)
if (DT->getNode(DelBB))
DT->eraseNode(DelBB);
if (PDT && !IsRecalculatingPostDomTree)
if (PDT->getNode(DelBB))
PDT->eraseNode(DelBB);
}
void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
assert(DelBB && "Invalid push_back of nullptr DelBB.");
assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
// DelBB is unreachable and all its instructions are dead.
while (!DelBB->empty()) {
Instruction &I = DelBB->back();
// Replace used instructions with an arbitrary value (undef).
if (!I.use_empty())
I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
DelBB->getInstList().pop_back();
}
// Make sure DelBB has a valid terminator instruction. As long as DelBB is a
// Child of Function F it must contain valid IR.
new UnreachableInst(DelBB->getContext(), DelBB);
}
void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
if (!DT && !PDT)
return;
if (Strategy == UpdateStrategy::Lazy) {
PendUpdates.reserve(PendUpdates.size() + Updates.size());
for (const auto &U : Updates)
if (!isSelfDominance(U))
PendUpdates.push_back(U);
return;
}
if (DT)
DT->applyUpdates(Updates);
if (PDT)
PDT->applyUpdates(Updates);
}
void DomTreeUpdater::applyUpdatesPermissive(
ArrayRef<DominatorTree::UpdateType> Updates) {
if (!DT && !PDT)
return;
SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
for (const auto &U : Updates) {
auto Edge = std::make_pair(U.getFrom(), U.getTo());
// Because it is illegal to submit updates that have already been applied
// and updates to an edge need to be strictly ordered,
// it is safe to infer the existence of an edge from the first update
// to this edge.
// If the first update to an edge is "Delete", it means that the edge
// existed before. If the first update to an edge is "Insert", it means
// that the edge didn't exist before.
//
// For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
// because
// 1. it is illegal to submit updates that have already been applied,
// i.e., user cannot delete an nonexistent edge,
// 2. updates to an edge need to be strictly ordered,
// So, initially edge A -> B existed.
// We can then safely ignore future updates to this edge and directly
// inspect the current CFG:
// a. If the edge still exists, because the user cannot insert an existent
// edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
// resulted in a no-op. DTU won't submit any update in this case.
// b. If the edge doesn't exist, we can then infer that {Delete, A, B}
// actually happened but {Insert, A, B} was an invalid update which never
// happened. DTU will submit {Delete, A, B} in this case.
if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
Seen.insert(Edge);
// If the update doesn't appear in the CFG, it means that
// either the change isn't made or relevant operations
// result in a no-op.
if (isUpdateValid(U)) {
if (isLazy())
PendUpdates.push_back(U);
else
DeduplicatedUpdates.push_back(U);
}
}
}
if (Strategy == UpdateStrategy::Lazy)
return;
if (DT)
DT->applyUpdates(DeduplicatedUpdates);
if (PDT)
PDT->applyUpdates(DeduplicatedUpdates);
}
DominatorTree &DomTreeUpdater::getDomTree() {
assert(DT && "Invalid acquisition of a null DomTree");
applyDomTreeUpdates();
dropOutOfDateUpdates();
return *DT;
}
PostDominatorTree &DomTreeUpdater::getPostDomTree() {
assert(PDT && "Invalid acquisition of a null PostDomTree");
applyPostDomTreeUpdates();
dropOutOfDateUpdates();
return *PDT;
}
void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
#ifndef NDEBUG
assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
"Inserted edge does not appear in the CFG");
#endif
if (!DT && !PDT)
return;
// Won't affect DomTree and PostDomTree; discard update.
if (From == To)
return;
if (Strategy == UpdateStrategy::Eager) {
if (DT)
DT->insertEdge(From, To);
if (PDT)
PDT->insertEdge(From, To);
return;
}
PendUpdates.push_back({DominatorTree::Insert, From, To});
}
void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
if (From == To)
return;
if (!DT && !PDT)
return;
if (!isUpdateValid({DominatorTree::Insert, From, To}))
return;
if (Strategy == UpdateStrategy::Eager) {
if (DT)
DT->insertEdge(From, To);
if (PDT)
PDT->insertEdge(From, To);
return;
}
PendUpdates.push_back({DominatorTree::Insert, From, To});
}
void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
#ifndef NDEBUG
assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
"Deleted edge still exists in the CFG!");
#endif
if (!DT && !PDT)
return;
// Won't affect DomTree and PostDomTree; discard update.
if (From == To)
return;
if (Strategy == UpdateStrategy::Eager) {
if (DT)
DT->deleteEdge(From, To);
if (PDT)
PDT->deleteEdge(From, To);
return;
}
PendUpdates.push_back({DominatorTree::Delete, From, To});
}
void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
if (From == To)
return;
if (!DT && !PDT)
return;
if (!isUpdateValid({DominatorTree::Delete, From, To}))
return;
if (Strategy == UpdateStrategy::Eager) {
if (DT)
DT->deleteEdge(From, To);
if (PDT)
PDT->deleteEdge(From, To);
return;
}
PendUpdates.push_back({DominatorTree::Delete, From, To});
}
void DomTreeUpdater::dropOutOfDateUpdates() {
if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
return;
tryFlushDeletedBB();
// Drop all updates applied by both trees.
if (!DT)
PendDTUpdateIndex = PendUpdates.size();
if (!PDT)
PendPDTUpdateIndex = PendUpdates.size();
const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
const auto B = PendUpdates.begin();
const auto E = PendUpdates.begin() + dropIndex;
assert(B <= E && "Iterator out of range.");
PendUpdates.erase(B, E);
// Calculate current index.
PendDTUpdateIndex -= dropIndex;
PendPDTUpdateIndex -= dropIndex;
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
raw_ostream &OS = llvm::dbgs();
OS << "Available Trees: ";
if (DT || PDT) {
if (DT)
OS << "DomTree ";
if (PDT)
OS << "PostDomTree ";
OS << "\n";
} else
OS << "None\n";
OS << "UpdateStrategy: ";
if (Strategy == UpdateStrategy::Eager) {
OS << "Eager\n";
return;
} else
OS << "Lazy\n";
int Index = 0;
auto printUpdates =
[&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
if (begin == end)
OS << " None\n";
Index = 0;
for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
auto U = *It;
OS << " " << Index << " : ";
++Index;
if (U.getKind() == DominatorTree::Insert)
OS << "Insert, ";
else
OS << "Delete, ";
BasicBlock *From = U.getFrom();
if (From) {
auto S = From->getName();
if (!From->hasName())
S = "(no name)";
OS << S << "(" << From << "), ";
} else {
OS << "(badref), ";
}
BasicBlock *To = U.getTo();
if (To) {
auto S = To->getName();
if (!To->hasName())
S = "(no_name)";
OS << S << "(" << To << ")\n";
} else {
OS << "(badref)\n";
}
}
};
if (DT) {
const auto I = PendUpdates.begin() + PendDTUpdateIndex;
assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
"Iterator out of range.");
OS << "Applied but not cleared DomTreeUpdates:\n";
printUpdates(PendUpdates.begin(), I);
OS << "Pending DomTreeUpdates:\n";
printUpdates(I, PendUpdates.end());
}
if (PDT) {
const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
"Iterator out of range.");
OS << "Applied but not cleared PostDomTreeUpdates:\n";
printUpdates(PendUpdates.begin(), I);
OS << "Pending PostDomTreeUpdates:\n";
printUpdates(I, PendUpdates.end());
}
OS << "Pending DeletedBBs:\n";
Index = 0;
for (const auto *BB : DeletedBBs) {
OS << " " << Index << " : ";
++Index;
if (BB->hasName())
OS << BB->getName() << "(";
else
OS << "(no_name)(";
OS << BB << ")\n";
}
OS << "Pending Callbacks:\n";
Index = 0;
for (const auto &BB : Callbacks) {
OS << " " << Index << " : ";
++Index;
if (BB->hasName())
OS << BB->getName() << "(";
else
OS << "(no_name)(";
OS << BB << ")\n";
}
}
#endif
} // namespace llvm