include/llvm/Support/CFGUpdate.h

   1 //===- CFGUpdate.h - Encode a CFG Edge Update. ------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines a CFG Edge Update: Insert or Delete, and two Nodes as the
  10 // Edge ends.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_SUPPORT_CFGUPDATE_H
  15 #define LLVM_SUPPORT_CFGUPDATE_H
  16
  17 #include "llvm/ADT/APInt.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/PointerIntPair.h"
  20 #include "llvm/Support/Compiler.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/raw_ostream.h"
  23
  24 namespace llvm {
  25 namespace cfg {
  26 enum class UpdateKind : unsigned char { Insert, Delete };
  27
  28 template <typename NodePtr> class Update {
  29   using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
  30   NodePtr From;
  31   NodeKindPair ToAndKind;
  32
  33 public:
  34   Update(UpdateKind Kind, NodePtr From, NodePtr To)
  35       : From(From), ToAndKind(To, Kind) {}
  36
  37   UpdateKind getKind() const { return ToAndKind.getInt(); }
  38   NodePtr getFrom() const { return From; }
  39   NodePtr getTo() const { return ToAndKind.getPointer(); }
  40   bool operator==(const Update &RHS) const {
  41     return From == RHS.From && ToAndKind == RHS.ToAndKind;
  42   }
  43
  44   void print(raw_ostream &OS) const {
  45     OS << (getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
  46     getFrom()->printAsOperand(OS, false);
  47     OS << " -> ";
  48     getTo()->printAsOperand(OS, false);
  49   }
  50
  51 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  52   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
  53 #endif
  54 };
  55
  56 // LegalizeUpdates function simplifies updates assuming a graph structure.
  57 // This function serves double purpose:
  58 // a) It removes redundant updates, which makes it easier to reverse-apply
  59 //    them when traversing CFG.
  60 // b) It optimizes away updates that cancel each other out, as the end result
  61 //    is the same.
  62 template <typename NodePtr>
  63 void LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates,
  64                      SmallVectorImpl<Update<NodePtr>> &Result,
  65                      bool InverseGraph) {
  66   // Count the total number of inserions of each edge.
  67   // Each insertion adds 1 and deletion subtracts 1. The end number should be
  68   // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
  69   // of updates contains multiple updates of the same kind and we assert for
  70   // that case.
  71   SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
  72   Operations.reserve(AllUpdates.size());
  73
  74   for (const auto &U : AllUpdates) {
  75     NodePtr From = U.getFrom();
  76     NodePtr To = U.getTo();
  77     if (InverseGraph)
  78       std::swap(From, To); // Reverse edge for postdominators.
  79
  80     Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
  81   }
  82
  83   Result.clear();
  84   Result.reserve(Operations.size());
  85   for (auto &Op : Operations) {
  86     const int NumInsertions = Op.second;
  87     assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
  88     if (NumInsertions == 0)
  89       continue;
  90     const UpdateKind UK =
  91         NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
  92     Result.push_back({UK, Op.first.first, Op.first.second});
  93   }
  94
  95   // Make the order consistent by not relying on pointer values within the
  96   // set. Reuse the old Operations map.
  97   // In the future, we should sort by something else to minimize the amount
  98   // of work needed to perform the series of updates.
  99   for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
 100     const auto &U = AllUpdates[i];
 101     if (!InverseGraph)
 102       Operations[{U.getFrom(), U.getTo()}] = int(i);
 103     else
 104       Operations[{U.getTo(), U.getFrom()}] = int(i);
 105   }
 106
 107   llvm::sort(Result,
 108              [&Operations](const Update<NodePtr> &A, const Update<NodePtr> &B) {
 109                return Operations[{A.getFrom(), A.getTo()}] >
 110                       Operations[{B.getFrom(), B.getTo()}];
 111              });
 112 }
 113
 114 } // end namespace cfg
 115 } // end namespace llvm
 116
 117 #endif // LLVM_SUPPORT_CFGUPDATE_H