LLVM  13.0.0git
InstCombineWorklist.h
Go to the documentation of this file.
1 //===- InstCombineWorklist.h - Worklist for InstCombine pass ----*- 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 #ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H
10 #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H
11 
12 #include "llvm/ADT/DenseMap.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/ADT/SetVector.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/IR/Instruction.h"
17 #include "llvm/Support/Compiler.h"
18 #include "llvm/Support/Debug.h"
20 
21 #define DEBUG_TYPE "instcombine"
22 
23 namespace llvm {
24 
25 /// InstCombineWorklist - This is the worklist management logic for
26 /// InstCombine.
30  /// These instructions will be added in reverse order after the current
31  /// combine has finished. This means that these instructions will be visited
32  /// in the order they have been added.
34 
35 public:
36  InstCombineWorklist() = default;
37 
40 
41  bool isEmpty() const { return Worklist.empty() && Deferred.empty(); }
42 
43  /// Add instruction to the worklist.
44  /// Instructions will be visited in the order they are added.
45  /// You likely want to use this method.
46  void add(Instruction *I) {
47  if (Deferred.insert(I))
48  LLVM_DEBUG(dbgs() << "IC: ADD DEFERRED: " << *I << '\n');
49  }
50 
51  /// Add value to the worklist if it is an instruction.
52  /// Instructions will be visited in the order they are added.
53  void addValue(Value *V) {
54  if (Instruction *I = dyn_cast<Instruction>(V))
55  add(I);
56  }
57 
58  /// Push the instruction onto the worklist stack.
59  /// Instructions that have been added first will be visited last.
60  void push(Instruction *I) {
61  assert(I);
62  assert(I->getParent() && "Instruction not inserted yet?");
63 
64  if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
65  LLVM_DEBUG(dbgs() << "IC: ADD: " << *I << '\n');
66  Worklist.push_back(I);
67  }
68  }
69 
70  void pushValue(Value *V) {
71  if (Instruction *I = dyn_cast<Instruction>(V))
72  push(I);
73  }
74 
76  if (Deferred.empty())
77  return nullptr;
78  return Deferred.pop_back_val();
79  }
80 
81  void reserve(size_t Size) {
82  Worklist.reserve(Size + 16);
83  WorklistMap.reserve(Size);
84  }
85 
86  /// Remove I from the worklist if it exists.
87  void remove(Instruction *I) {
89  if (It != WorklistMap.end()) {
90  // Don't bother moving everything down, just null out the slot.
91  Worklist[It->second] = nullptr;
92  WorklistMap.erase(It);
93  }
94 
95  Deferred.remove(I);
96  }
97 
99  if (Worklist.empty())
100  return nullptr;
101  Instruction *I = Worklist.pop_back_val();
102  WorklistMap.erase(I);
103  return I;
104  }
105 
106  /// When an instruction is simplified, add all users of the instruction
107  /// to the work lists because they might get more simplified now.
109  for (User *U : I.users())
110  push(cast<Instruction>(U));
111  }
112 
113 
114  /// Check that the worklist is empty and nuke the backing store for the map.
115  void zap() {
116  assert(WorklistMap.empty() && "Worklist empty, but map not?");
117  assert(Deferred.empty() && "Deferred instructions left over");
118 
119  // Do an explicit clear, this shrinks the map if needed.
120  WorklistMap.clear();
121  }
122 };
123 
124 } // end namespace llvm.
125 
126 #undef DEBUG_TYPE
127 
128 #endif
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::InstCombineWorklist::reserve
void reserve(size_t Size)
Definition: InstCombineWorklist.h:81
llvm
Definition: AllocatorList.h:23
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::InstCombineWorklist::InstCombineWorklist
InstCombineWorklist()=default
llvm::DenseMapIterator
Definition: DenseMap.h:56
DenseMap.h
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Instruction.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::remove
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:157
llvm::User
Definition: User.h:44
llvm::InstCombineWorklist::isEmpty
bool isEmpty() const
Definition: InstCombineWorklist.h:41
llvm::Instruction
Definition: Instruction.h:45
llvm::InstCombineWorklist
InstCombineWorklist - This is the worklist management logic for InstCombine.
Definition: InstCombineWorklist.h:27
llvm::InstCombineWorklist::pushValue
void pushValue(Value *V)
Definition: InstCombineWorklist.h:70
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::InstCombineWorklist::popDeferred
Instruction * popDeferred()
Definition: InstCombineWorklist.h:75
llvm::InstCombineWorklist::push
void push(Instruction *I)
Push the instruction onto the worklist stack.
Definition: InstCombineWorklist.h:60
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::InstCombineWorklist::addValue
void addValue(Value *V)
Add value to the worklist if it is an instruction.
Definition: InstCombineWorklist.h:53
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::InstCombineWorklist::remove
void remove(Instruction *I)
Remove I from the worklist if it exists.
Definition: InstCombineWorklist.h:87
Compiler.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:97
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::InstCombineWorklist::add
void add(Instruction *I)
Add instruction to the worklist.
Definition: InstCombineWorklist.h:46
llvm::InstCombineWorklist::removeOne
Instruction * removeOne()
Definition: InstCombineWorklist.h:98
SmallVector.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::reserve
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:104
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::InstCombineWorklist::pushUsersToWorkList
void pushUsersToWorkList(Instruction &I)
When an instruction is simplified, add all users of the instruction to the work lists because they mi...
Definition: InstCombineWorklist.h:108
llvm::InstCombineWorklist::zap
void zap()
Check that the worklist is empty and nuke the backing store for the map.
Definition: InstCombineWorklist.h:115
raw_ostream.h
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:232
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::InstCombineWorklist::operator=
InstCombineWorklist & operator=(InstCombineWorklist &&)=default
SetVector.h