| //===- CFGDiff.h - Define a CFG snapshot. -----------------------*- 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 defines specializations of GraphTraits that allows generic |
| // algorithms to see a different snapshot of a CFG. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_SUPPORT_CFGDIFF_H |
| #define LLVM_SUPPORT_CFGDIFF_H |
| |
| #include "llvm/ADT/GraphTraits.h" |
| #include "llvm/ADT/iterator.h" |
| #include "llvm/ADT/iterator_range.h" |
| #include "llvm/Support/CFGUpdate.h" |
| #include "llvm/Support/type_traits.h" |
| #include <cassert> |
| #include <cstddef> |
| #include <iterator> |
| |
| // Two booleans are used to define orders in graphs: |
| // InverseGraph defines when we need to reverse the whole graph and is as such |
| // also equivalent to applying updates in reverse. |
| // InverseEdge defines whether we want to change the edges direction. E.g., for |
| // a non-inversed graph, the children are naturally the successors when |
| // InverseEdge is false and the predecessors when InverseEdge is true. |
| |
| namespace llvm { |
| |
| namespace detail { |
| template <typename Range> |
| auto reverse_if_helper(Range &&R, std::integral_constant<bool, false>) { |
| return std::forward<Range>(R); |
| } |
| |
| template <typename Range> |
| auto reverse_if_helper(Range &&R, std::integral_constant<bool, true>) { |
| return llvm::reverse(std::forward<Range>(R)); |
| } |
| |
| template <bool B, typename Range> auto reverse_if(Range &&R) { |
| return reverse_if_helper(std::forward<Range>(R), |
| std::integral_constant<bool, B>{}); |
| } |
| } // namespace detail |
| |
| // GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provides |
| // a getChildren method to get a Node's children based on the additional updates |
| // in the snapshot. The current diff treats the CFG as a graph rather than a |
| // multigraph. Added edges are pruned to be unique, and deleted edges will |
| // remove all existing edges between two blocks. |
| template <typename NodePtr, bool InverseGraph = false> class GraphDiff { |
| struct DeletesInserts { |
| SmallVector<NodePtr, 2> DI[2]; |
| }; |
| using UpdateMapType = SmallDenseMap<NodePtr, DeletesInserts>; |
| UpdateMapType Succ; |
| UpdateMapType Pred; |
| |
| // By default, it is assumed that, given a CFG and a set of updates, we wish |
| // to apply these updates as given. If UpdatedAreReverseApplied is set, the |
| // updates will be applied in reverse: deleted edges are considered re-added |
| // and inserted edges are considered deleted when returning children. |
| bool UpdatedAreReverseApplied; |
| |
| // Keep the list of legalized updates for a deterministic order of updates |
| // when using a GraphDiff for incremental updates in the DominatorTree. |
| // The list is kept in reverse to allow popping from end. |
| SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates; |
| |
| void printMap(raw_ostream &OS, const UpdateMapType &M) const { |
| StringRef DIText[2] = {"Delete", "Insert"}; |
| for (auto Pair : M) { |
| for (unsigned IsInsert = 0; IsInsert <= 1; ++IsInsert) { |
| OS << DIText[IsInsert] << " edges: \n"; |
| for (auto Child : Pair.second.DI[IsInsert]) { |
| OS << "("; |
| Pair.first->printAsOperand(OS, false); |
| OS << ", "; |
| Child->printAsOperand(OS, false); |
| OS << ") "; |
| } |
| } |
| } |
| OS << "\n"; |
| } |
| |
| public: |
| GraphDiff() : UpdatedAreReverseApplied(false) {} |
| GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates, |
| bool ReverseApplyUpdates = false) { |
| cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph); |
| for (auto U : LegalizedUpdates) { |
| unsigned IsInsert = |
| (U.getKind() == cfg::UpdateKind::Insert) == !ReverseApplyUpdates; |
| Succ[U.getFrom()].DI[IsInsert].push_back(U.getTo()); |
| Pred[U.getTo()].DI[IsInsert].push_back(U.getFrom()); |
| } |
| UpdatedAreReverseApplied = ReverseApplyUpdates; |
| } |
| |
| auto getLegalizedUpdates() const { |
| return make_range(LegalizedUpdates.begin(), LegalizedUpdates.end()); |
| } |
| |
| unsigned getNumLegalizedUpdates() const { return LegalizedUpdates.size(); } |
| |
| cfg::Update<NodePtr> popUpdateForIncrementalUpdates() { |
| assert(!LegalizedUpdates.empty() && "No updates to apply!"); |
| auto U = LegalizedUpdates.pop_back_val(); |
| unsigned IsInsert = |
| (U.getKind() == cfg::UpdateKind::Insert) == !UpdatedAreReverseApplied; |
| auto &SuccDIList = Succ[U.getFrom()]; |
| auto &SuccList = SuccDIList.DI[IsInsert]; |
| assert(SuccList.back() == U.getTo()); |
| SuccList.pop_back(); |
| if (SuccList.empty() && SuccDIList.DI[!IsInsert].empty()) |
| Succ.erase(U.getFrom()); |
| |
| auto &PredDIList = Pred[U.getTo()]; |
| auto &PredList = PredDIList.DI[IsInsert]; |
| assert(PredList.back() == U.getFrom()); |
| PredList.pop_back(); |
| if (PredList.empty() && PredDIList.DI[!IsInsert].empty()) |
| Pred.erase(U.getTo()); |
| return U; |
| } |
| |
| using VectRet = SmallVector<NodePtr, 8>; |
| template <bool InverseEdge> VectRet getChildren(NodePtr N) const { |
| using DirectedNodeT = |
| std::conditional_t<InverseEdge, Inverse<NodePtr>, NodePtr>; |
| auto R = children<DirectedNodeT>(N); |
| VectRet Res = VectRet(detail::reverse_if<!InverseEdge>(R)); |
| |
| // Remove nullptr children for clang. |
| llvm::erase_value(Res, nullptr); |
| |
| auto &Children = (InverseEdge != InverseGraph) ? Pred : Succ; |
| auto It = Children.find(N); |
| if (It == Children.end()) |
| return Res; |
| |
| // Remove children present in the CFG but not in the snapshot. |
| for (auto *Child : It->second.DI[0]) |
| llvm::erase_value(Res, Child); |
| |
| // Add children present in the snapshot for not in the real CFG. |
| auto &AddedChildren = It->second.DI[1]; |
| llvm::append_range(Res, AddedChildren); |
| |
| return Res; |
| } |
| |
| void print(raw_ostream &OS) const { |
| OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n" |
| "===== (Note: notion of children/inverse_children depends on " |
| "the direction of edges and the graph.)\n"; |
| OS << "Children to delete/insert:\n\t"; |
| printMap(OS, Succ); |
| OS << "Inverse_children to delete/insert:\n\t"; |
| printMap(OS, Pred); |
| OS << "\n"; |
| } |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| LLVM_DUMP_METHOD void dump() const { print(dbgs()); } |
| #endif |
| }; |
| } // end namespace llvm |
| |
| #endif // LLVM_SUPPORT_CFGDIFF_H |