LLVM  6.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  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  DEBUG(dbgs() << "IC: ADDING: " << List.size() << " instrs to worklist\n");
61  unsigned Idx = 0;
62  for (Instruction *I : reverse(List)) {
63  WorklistMap.insert(std::make_pair(I, Idx++));
64  Worklist.push_back(I);
65  }
66  }
67 
68  // Remove - remove I from the worklist if it exists.
69  void Remove(Instruction *I) {
71  if (It == WorklistMap.end()) return; // Not in worklist.
72 
73  // Don't bother moving everything down, just null out the slot.
74  Worklist[It->second] = nullptr;
75 
76  WorklistMap.erase(It);
77  }
78 
80  Instruction *I = Worklist.pop_back_val();
81  WorklistMap.erase(I);
82  return I;
83  }
84 
85  /// AddUsersToWorkList - When an instruction is simplified, add all users of
86  /// the instruction to the work lists because they might get more simplified
87  /// now.
88  ///
90  for (User *U : I.users())
91  Add(cast<Instruction>(U));
92  }
93 
94 
95  /// Zap - check that the worklist is empty and nuke the backing store for
96  /// the map if it is large.
97  void Zap() {
98  assert(WorklistMap.empty() && "Worklist empty, but map not?");
99 
100  // Do an explicit clear, this shrinks the map if needed.
101  WorklistMap.clear();
102  }
103 };
104 
105 } // end namespace llvm.
106 
107 #undef DEBUG_TYPE
108 
109 #endif
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
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:380
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:232
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.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
iterator_range< user_iterator > users()
Definition: Value.h:401
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
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 DEBUG(X)
Definition: Debug.h:118
void Zap()
Zap - check that the worklist is empty and nuke the backing store for the map if it is large...