LLVM  14.0.0git
InstructionWorklist.h
Go to the documentation of this file.
1 //=== InstructionWorklist.h - Worklist for InstCombine & others -*- 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_UTILS_INSTRUCTIONWORKLIST_H
10 #define LLVM_TRANSFORMS_UTILS_INSTRUCTIONWORKLIST_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 namespace llvm {
22 
23 /// InstructionWorklist - This is the worklist management logic for
24 /// InstCombine and other simplification passes.
28  /// These instructions will be added in reverse order after the current
29  /// combine has finished. This means that these instructions will be visited
30  /// in the order they have been added.
32 
33 public:
34  InstructionWorklist() = default;
35 
38 
39  bool isEmpty() const { return Worklist.empty() && Deferred.empty(); }
40 
41  /// Add instruction to the worklist.
42  /// Instructions will be visited in the order they are added.
43  /// You likely want to use this method.
44  void add(Instruction *I) {
45  if (Deferred.insert(I))
46  LLVM_DEBUG(dbgs() << "ADD DEFERRED: " << *I << '\n');
47  }
48 
49  /// Add value to the worklist if it is an instruction.
50  /// Instructions will be visited in the order they are added.
51  void addValue(Value *V) {
52  if (Instruction *I = dyn_cast<Instruction>(V))
53  add(I);
54  }
55 
56  /// Push the instruction onto the worklist stack.
57  /// Instructions that have been added first will be visited last.
58  void push(Instruction *I) {
59  assert(I);
60  assert(I->getParent() && "Instruction not inserted yet?");
61 
62  if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
63  LLVM_DEBUG(dbgs() << "ADD: " << *I << '\n');
64  Worklist.push_back(I);
65  }
66  }
67 
68  void pushValue(Value *V) {
69  if (Instruction *I = dyn_cast<Instruction>(V))
70  push(I);
71  }
72 
74  if (Deferred.empty())
75  return nullptr;
76  return Deferred.pop_back_val();
77  }
78 
79  void reserve(size_t Size) {
80  Worklist.reserve(Size + 16);
81  WorklistMap.reserve(Size);
82  }
83 
84  /// Remove I from the worklist if it exists.
85  void remove(Instruction *I) {
87  if (It != WorklistMap.end()) {
88  // Don't bother moving everything down, just null out the slot.
89  Worklist[It->second] = nullptr;
90  WorklistMap.erase(It);
91  }
92 
93  Deferred.remove(I);
94  }
95 
97  if (Worklist.empty())
98  return nullptr;
99  Instruction *I = Worklist.pop_back_val();
100  WorklistMap.erase(I);
101  return I;
102  }
103 
104  /// When an instruction is simplified, add all users of the instruction
105  /// to the work lists because they might get more simplified now.
107  for (User *U : I.users())
108  push(cast<Instruction>(U));
109  }
110 
111  /// Check that the worklist is empty and nuke the backing store for the map.
112  void zap() {
113  assert(WorklistMap.empty() && "Worklist empty, but map not?");
114  assert(Deferred.empty() && "Deferred instructions left over");
115 
116  // Do an explicit clear, this shrinks the map if needed.
117  WorklistMap.clear();
118  }
119 };
120 
121 } // end namespace llvm.
122 
123 #endif
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::InstructionWorklist::operator=
InstructionWorklist & operator=(InstructionWorklist &&)=default
llvm::InstructionWorklist::addValue
void addValue(Value *V)
Add value to the worklist if it is an instruction.
Definition: InstructionWorklist.h:51
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::InstructionWorklist::isEmpty
bool isEmpty() const
Definition: InstructionWorklist.h:39
llvm::InstructionWorklist::reserve
void reserve(size_t Size)
Definition: InstructionWorklist.h:79
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::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::InstructionWorklist::add
void add(Instruction *I)
Add instruction to the worklist.
Definition: InstructionWorklist.h:44
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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::InstructionWorklist::remove
void remove(Instruction *I)
Remove I from the worklist if it exists.
Definition: InstructionWorklist.h:85
llvm::Instruction
Definition: Instruction.h:45
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::InstructionWorklist::InstructionWorklist
InstructionWorklist()=default
llvm::InstructionWorklist::zap
void zap()
Check that the worklist is empty and nuke the backing store for the map.
Definition: InstructionWorklist.h:112
llvm::InstructionWorklist::removeOne
Instruction * removeOne()
Definition: InstructionWorklist.h:96
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::InstructionWorklist::push
void push(Instruction *I)
Push the instruction onto the worklist stack.
Definition: InstructionWorklist.h:58
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
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::InstructionWorklist::pushValue
void pushValue(Value *V)
Definition: InstructionWorklist.h:68
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::InstructionWorklist
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
Definition: InstructionWorklist.h:25
llvm::InstructionWorklist::popDeferred
Instruction * popDeferred()
Definition: InstructionWorklist.h:73
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::InstructionWorklist::pushUsersToWorkList
void pushUsersToWorkList(Instruction &I)
When an instruction is simplified, add all users of the instruction to the work lists because they mi...
Definition: InstructionWorklist.h:106
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
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:74
Debug.h
SetVector.h