LLVM  9.0.0svn
CFGUpdate.h
Go to the documentation of this file.
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"
20 #include "llvm/Support/Compiler.h"
21 #include "llvm/Support/Debug.h"
23 
24 namespace llvm {
25 namespace cfg {
26 enum class UpdateKind : unsigned char { Insert, Delete };
27 
28 template <typename NodePtr> class Update {
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>
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.
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
NodePtr getTo() const
Definition: CFGUpdate.h:39
This class represents lattice values for constants.
Definition: AllocatorList.h:23
PointerTy getPointer() const
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
NodePtr getFrom() const
Definition: CFGUpdate.h:38
This file implements a class to represent arbitrary precision integral constant values and operations...
void print(raw_ostream &OS) const
Definition: CFGUpdate.h:44
IntType getInt() const
LLVM_DUMP_METHOD void dump() const
Definition: CFGUpdate.h:52
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void LegalizeUpdates(ArrayRef< Update< NodePtr >> AllUpdates, SmallVectorImpl< Update< NodePtr >> &Result, bool InverseGraph)
Definition: CFGUpdate.h:63
bool operator==(const Update &RHS) const
Definition: CFGUpdate.h:40
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:129
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
BlockVerifier::State From
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1212
UpdateKind getKind() const
Definition: CFGUpdate.h:37
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Update(UpdateKind Kind, NodePtr From, NodePtr To)
Definition: CFGUpdate.h:34