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"
19#include "llvm/Support/raw_ostream.h"
20
21namespace llvm {
22
23/// InstructionWorklist - This is the worklist management logic for
24/// InstCombine and other simplification passes.
25class InstructionWorklist {
26  SmallVector<Instruction *, 256> Worklist;
27  DenseMap<Instruction *, unsigned> WorklistMap;
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.
31  SmallSetVector<Instruction *, 16> Deferred;
32
33public:
34  InstructionWorklist() = default;
35
36  InstructionWorklist(InstructionWorklist &&) = default;
37  InstructionWorklist &operator=(InstructionWorklist &&) = default;
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
73  Instruction *popDeferred() {
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) {
86    DenseMap<Instruction *, unsigned>::iterator It = WorklistMap.find(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
96  Instruction *removeOne() {
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.
106  void pushUsersToWorkList(Instruction &I) {
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
124