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