Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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