1343171Sdim//===- CFGUpdate.h - Encode a CFG Edge Update. ------------------*- C++ -*-===// 2343171Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6343171Sdim// 7343171Sdim//===----------------------------------------------------------------------===// 8343171Sdim// 9343171Sdim// This file defines a CFG Edge Update: Insert or Delete, and two Nodes as the 10343171Sdim// Edge ends. 11343171Sdim// 12343171Sdim//===----------------------------------------------------------------------===// 13343171Sdim 14343171Sdim#ifndef LLVM_SUPPORT_CFGUPDATE_H 15343171Sdim#define LLVM_SUPPORT_CFGUPDATE_H 16343171Sdim 17343171Sdim#include "llvm/ADT/APInt.h" 18343171Sdim#include "llvm/ADT/DenseMap.h" 19343171Sdim#include "llvm/ADT/PointerIntPair.h" 20343171Sdim#include "llvm/Support/Compiler.h" 21343171Sdim#include "llvm/Support/Debug.h" 22343171Sdim#include "llvm/Support/raw_ostream.h" 23343171Sdim 24343171Sdimnamespace llvm { 25343171Sdimnamespace cfg { 26343171Sdimenum class UpdateKind : unsigned char { Insert, Delete }; 27343171Sdim 28343171Sdimtemplate <typename NodePtr> class Update { 29343171Sdim using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>; 30343171Sdim NodePtr From; 31343171Sdim NodeKindPair ToAndKind; 32343171Sdim 33343171Sdimpublic: 34343171Sdim Update(UpdateKind Kind, NodePtr From, NodePtr To) 35343171Sdim : From(From), ToAndKind(To, Kind) {} 36343171Sdim 37343171Sdim UpdateKind getKind() const { return ToAndKind.getInt(); } 38343171Sdim NodePtr getFrom() const { return From; } 39343171Sdim NodePtr getTo() const { return ToAndKind.getPointer(); } 40343171Sdim bool operator==(const Update &RHS) const { 41343171Sdim return From == RHS.From && ToAndKind == RHS.ToAndKind; 42343171Sdim } 43343171Sdim 44343171Sdim void print(raw_ostream &OS) const { 45343171Sdim OS << (getKind() == UpdateKind::Insert ? "Insert " : "Delete "); 46343171Sdim getFrom()->printAsOperand(OS, false); 47343171Sdim OS << " -> "; 48343171Sdim getTo()->printAsOperand(OS, false); 49343171Sdim } 50343171Sdim 51343171Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 52343171Sdim LLVM_DUMP_METHOD void dump() const { print(dbgs()); } 53343171Sdim#endif 54343171Sdim}; 55343171Sdim 56343171Sdim// LegalizeUpdates function simplifies updates assuming a graph structure. 57343171Sdim// This function serves double purpose: 58343171Sdim// a) It removes redundant updates, which makes it easier to reverse-apply 59343171Sdim// them when traversing CFG. 60343171Sdim// b) It optimizes away updates that cancel each other out, as the end result 61343171Sdim// is the same. 62343171Sdimtemplate <typename NodePtr> 63343171Sdimvoid LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates, 64343171Sdim SmallVectorImpl<Update<NodePtr>> &Result, 65343171Sdim bool InverseGraph) { 66343171Sdim // Count the total number of inserions of each edge. 67343171Sdim // Each insertion adds 1 and deletion subtracts 1. The end number should be 68343171Sdim // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence 69343171Sdim // of updates contains multiple updates of the same kind and we assert for 70343171Sdim // that case. 71343171Sdim SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations; 72343171Sdim Operations.reserve(AllUpdates.size()); 73343171Sdim 74343171Sdim for (const auto &U : AllUpdates) { 75343171Sdim NodePtr From = U.getFrom(); 76343171Sdim NodePtr To = U.getTo(); 77343171Sdim if (InverseGraph) 78343171Sdim std::swap(From, To); // Reverse edge for postdominators. 79343171Sdim 80343171Sdim Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1); 81343171Sdim } 82343171Sdim 83343171Sdim Result.clear(); 84343171Sdim Result.reserve(Operations.size()); 85343171Sdim for (auto &Op : Operations) { 86343171Sdim const int NumInsertions = Op.second; 87343171Sdim assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!"); 88343171Sdim if (NumInsertions == 0) 89343171Sdim continue; 90343171Sdim const UpdateKind UK = 91343171Sdim NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete; 92343171Sdim Result.push_back({UK, Op.first.first, Op.first.second}); 93343171Sdim } 94343171Sdim 95343171Sdim // Make the order consistent by not relying on pointer values within the 96343171Sdim // set. Reuse the old Operations map. 97343171Sdim // In the future, we should sort by something else to minimize the amount 98343171Sdim // of work needed to perform the series of updates. 99343171Sdim for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) { 100343171Sdim const auto &U = AllUpdates[i]; 101343171Sdim if (!InverseGraph) 102343171Sdim Operations[{U.getFrom(), U.getTo()}] = int(i); 103343171Sdim else 104343171Sdim Operations[{U.getTo(), U.getFrom()}] = int(i); 105343171Sdim } 106343171Sdim 107343171Sdim llvm::sort(Result, 108343171Sdim [&Operations](const Update<NodePtr> &A, const Update<NodePtr> &B) { 109343171Sdim return Operations[{A.getFrom(), A.getTo()}] > 110343171Sdim Operations[{B.getFrom(), B.getTo()}]; 111343171Sdim }); 112343171Sdim} 113343171Sdim 114343171Sdim} // end namespace cfg 115343171Sdim} // end namespace llvm 116343171Sdim 117343171Sdim#endif // LLVM_SUPPORT_CFGUPDATE_H 118