llvm/Support/CFGUpdate.h

0001 //===- CFGUpdate.h - Encode a CFG Edge Update. ------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines a CFG Edge Update: Insert or Delete, and two Nodes as the
0010 // Edge ends.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_SUPPORT_CFGUPDATE_H
0015 #define LLVM_SUPPORT_CFGUPDATE_H
0016
0017 #include "llvm/ADT/ArrayRef.h"
0018 #include "llvm/ADT/DenseMap.h"
0019 #include "llvm/ADT/PointerIntPair.h"
0020 #include "llvm/Support/Compiler.h"
0021 #include "llvm/Support/Debug.h"
0022 #include "llvm/Support/raw_ostream.h"
0023
0024 namespace llvm {
0025 namespace cfg {
0026 enum class UpdateKind : unsigned char { Insert, Delete };
0027
0028 template <typename NodePtr> class Update {
0029   using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
0030   NodePtr From;
0031   NodeKindPair ToAndKind;
0032
0033 public:
0034   Update(UpdateKind Kind, NodePtr From, NodePtr To)
0035       : From(From), ToAndKind(To, Kind) {}
0036
0037   UpdateKind getKind() const { return ToAndKind.getInt(); }
0038   NodePtr getFrom() const { return From; }
0039   NodePtr getTo() const { return ToAndKind.getPointer(); }
0040   bool operator==(const Update &RHS) const {
0041     return From == RHS.From && ToAndKind == RHS.ToAndKind;
0042   }
0043
0044   void print(raw_ostream &OS) const {
0045     OS << (getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
0046     getFrom()->printAsOperand(OS, false);
0047     OS << " -> ";
0048     getTo()->printAsOperand(OS, false);
0049   }
0050
0051 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
0052   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
0053 #endif
0054 };
0055
0056 // LegalizeUpdates function simplifies updates assuming a graph structure.
0057 // This function serves double purpose:
0058 // a) It removes redundant updates, which makes it easier to reverse-apply
0059 //    them when traversing CFG.
0060 // b) It optimizes away updates that cancel each other out, as the end result
0061 //    is the same.
0062 template <typename NodePtr>
0063 void LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates,
0064                      SmallVectorImpl<Update<NodePtr>> &Result,
0065                      bool InverseGraph, bool ReverseResultOrder = false) {
0066   // Count the total number of inserions of each edge.
0067   // Each insertion adds 1 and deletion subtracts 1. The end number should be
0068   // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
0069   // of updates contains multiple updates of the same kind and we assert for
0070   // that case.
0071   SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
0072   Operations.reserve(AllUpdates.size());
0073
0074   for (const auto &U : AllUpdates) {
0075     NodePtr From = U.getFrom();
0076     NodePtr To = U.getTo();
0077     if (InverseGraph)
0078       std::swap(From, To); // Reverse edge for postdominators.
0079
0080     Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
0081   }
0082
0083   Result.clear();
0084   Result.reserve(Operations.size());
0085   for (auto &Op : Operations) {
0086     const int NumInsertions = Op.second;
0087     assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
0088     if (NumInsertions == 0)
0089       continue;
0090     const UpdateKind UK =
0091         NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
0092     Result.push_back({UK, Op.first.first, Op.first.second});
0093   }
0094
0095   // Make the order consistent by not relying on pointer values within the
0096   // set. Reuse the old Operations map.
0097   // In the future, we should sort by something else to minimize the amount
0098   // of work needed to perform the series of updates.
0099   for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
0100     const auto &U = AllUpdates[i];
0101     if (!InverseGraph)
0102       Operations[{U.getFrom(), U.getTo()}] = int(i);
0103     else
0104       Operations[{U.getTo(), U.getFrom()}] = int(i);
0105   }
0106
0107   llvm::sort(Result, [&](const Update<NodePtr> &A, const Update<NodePtr> &B) {
0108     const auto &OpA = Operations[{A.getFrom(), A.getTo()}];
0109     const auto &OpB = Operations[{B.getFrom(), B.getTo()}];
0110     return ReverseResultOrder ? OpA < OpB : OpA > OpB;
0111   });
0112 }
0113
0114 } // end namespace cfg
0115 } // end namespace llvm
0116
0117 #endif // LLVM_SUPPORT_CFGUPDATE_H