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"
19#include "llvm/Support/raw_ostream.h"
20
21#define DEBUG_TYPE "instcombine"
22
23namespace llvm {
24
25/// InstCombineWorklist - This is the worklist management logic for
26/// InstCombine.
27class InstCombineWorklist {
28  SmallVector<Instruction *, 256> Worklist;
29  DenseMap<Instruction *, unsigned> WorklistMap;
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.
33  SmallSetVector<Instruction *, 16> Deferred;
34
35public:
36  InstCombineWorklist() = default;
37
38  InstCombineWorklist(InstCombineWorklist &&) = default;
39  InstCombineWorklist &operator=(InstCombineWorklist &&) = default;
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
75  Instruction *popDeferred() {
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) {
88    DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(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
98  Instruction *removeOne() {
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.
108  void pushUsersToWorkList(Instruction &I) {
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
129