LLVM 17.0.0git
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/ArrayRef.h"
18#include "llvm/ADT/DenseMap.h"
21#include "llvm/Support/Debug.h"
23
24namespace llvm {
25namespace cfg {
26enum class UpdateKind : unsigned char { Insert, Delete };
27
28template <typename NodePtr> class Update {
30 NodePtr From;
31 NodeKindPair ToAndKind;
32
33public:
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.
62template <typename NodePtr>
65 bool InverseGraph, bool ReverseResultOrder = false) {
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, [&](const Update<NodePtr> &A, const Update<NodePtr> &B) {
108 const auto &OpA = Operations[{A.getFrom(), A.getTo()}];
109 const auto &OpB = Operations[{B.getFrom(), B.getTo()}];
110 return ReverseResultOrder ? OpA < OpB : OpA > OpB;
111 });
112}
113
114} // end namespace cfg
115} // end namespace llvm
116
117#endif // LLVM_SUPPORT_CFGUPDATE_H
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
This file defines the DenseMap class.
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
unsigned size() const
Definition: DenseMap.h:99
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:103
IntType getInt() const
PointerTy getPointer() const
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
UpdateKind getKind() const
Definition: CFGUpdate.h:37
Update(UpdateKind Kind, NodePtr From, NodePtr To)
Definition: CFGUpdate.h:34
bool operator==(const Update &RHS) const
Definition: CFGUpdate.h:40
NodePtr getFrom() const
Definition: CFGUpdate.h:38
NodePtr getTo() const
Definition: CFGUpdate.h:39
void print(raw_ostream &OS) const
Definition: CFGUpdate.h:44
LLVM_DUMP_METHOD void dump() const
Definition: CFGUpdate.h:52
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
void LegalizeUpdates(ArrayRef< Update< NodePtr > > AllUpdates, SmallVectorImpl< Update< NodePtr > > &Result, bool InverseGraph, bool ReverseResultOrder=false)
Definition: CFGUpdate.h:63
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1730
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853