LLVM  8.0.0svn
InstCombineWorklist.h
Go to the documentation of this file.
1 //===- InstCombineWorklist.h - Worklist for InstCombine pass ----*- 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 #ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H
11 #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H
12 
13 #include "llvm/ADT/DenseMap.h"
14 #include "llvm/ADT/STLExtras.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 
31 public:
32  InstCombineWorklist() = default;
33 
36 
37  bool isEmpty() const { return Worklist.empty(); }
38 
39  /// Add - Add the specified instruction to the worklist if it isn't already
40  /// in it.
41  void Add(Instruction *I) {
42  if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
43  LLVM_DEBUG(dbgs() << "IC: ADD: " << *I << '\n');
44  Worklist.push_back(I);
45  }
46  }
47 
48  void AddValue(Value *V) {
49  if (Instruction *I = dyn_cast<Instruction>(V))
50  Add(I);
51  }
52 
53  /// AddInitialGroup - Add the specified batch of stuff in reverse order.
54  /// which should only be done when the worklist is empty and when the group
55  /// has no duplicates.
57  assert(Worklist.empty() && "Worklist must be empty to add initial group");
58  Worklist.reserve(List.size()+16);
59  WorklistMap.reserve(List.size());
60  LLVM_DEBUG(dbgs() << "IC: ADDING: " << List.size()
61  << " instrs to worklist\n");
62  unsigned Idx = 0;
63  for (Instruction *I : reverse(List)) {
64  WorklistMap.insert(std::make_pair(I, Idx++));
65  Worklist.push_back(I);
66  }
67  }
68 
69  // Remove - remove I from the worklist if it exists.
70  void Remove(Instruction *I) {
72  if (It == WorklistMap.end()) return; // Not in worklist.
73 
74  // Don't bother moving everything down, just null out the slot.
75  Worklist[It->second] = nullptr;
76 
77  WorklistMap.erase(It);
78  }
79 
81  Instruction *I = Worklist.pop_back_val();
82  WorklistMap.erase(I);
83  return I;
84  }
85 
86  /// AddUsersToWorkList - When an instruction is simplified, add all users of
87  /// the instruction to the work lists because they might get more simplified
88  /// now.
89  ///
91  for (User *U : I.users())
92  Add(cast<Instruction>(U));
93  }
94 
95 
96  /// Zap - check that the worklist is empty and nuke the backing store for
97  /// the map if it is large.
98  void Zap() {
99  assert(WorklistMap.empty() && "Worklist empty, but map not?");
100 
101  // Do an explicit clear, this shrinks the map if needed.
102  WorklistMap.clear();
103  }
104 };
105 
106 } // end namespace llvm.
107 
108 #undef DEBUG_TYPE
109 
110 #endif
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void Remove(Instruction *I)
void Add(Instruction *I)
Add - Add the specified instruction to the worklist if it isn&#39;t already in it.
void reserve(size_type N)
Definition: SmallVector.h:376
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
InstCombineWorklist & operator=(InstCombineWorklist &&)=default
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:251
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
void AddUsersToWorkList(Instruction &I)
AddUsersToWorkList - When an instruction is simplified, add all users of the instruction to the work ...
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
void AddInitialGroup(ArrayRef< Instruction *> List)
AddInitialGroup - Add the specified batch of stuff in reverse order.
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:100
InstCombineWorklist - This is the worklist management logic for InstCombine.
size_t size() const
Definition: SmallVector.h:53
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
iterator_range< user_iterator > users()
Definition: Value.h:400
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
const NodeList & List
Definition: RDFGraph.cpp:210
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
#define LLVM_DEBUG(X)
Definition: Debug.h:123
void Zap()
Zap - check that the worklist is empty and nuke the backing store for the map if it is large...