blob: 3ee2b1f1d19688ac5247e56ffa8a1e2edf143962 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#pragma once
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
//=== InstructionWorklist.h - Worklist for InstCombine & others -*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_UTILS_INSTRUCTIONWORKLIST_H
#define LLVM_TRANSFORMS_UTILS_INSTRUCTIONWORKLIST_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/Instruction.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
namespace llvm {
/// InstructionWorklist - This is the worklist management logic for
/// InstCombine and other simplification passes.
class InstructionWorklist {
SmallVector<Instruction *, 256> Worklist;
DenseMap<Instruction *, unsigned> WorklistMap;
/// These instructions will be added in reverse order after the current
/// combine has finished. This means that these instructions will be visited
/// in the order they have been added.
SmallSetVector<Instruction *, 16> Deferred;
public:
InstructionWorklist() = default;
InstructionWorklist(InstructionWorklist &&) = default;
InstructionWorklist &operator=(InstructionWorklist &&) = default;
bool isEmpty() const { return Worklist.empty() && Deferred.empty(); }
/// Add instruction to the worklist.
/// Instructions will be visited in the order they are added.
/// You likely want to use this method.
void add(Instruction *I) {
if (Deferred.insert(I))
LLVM_DEBUG(dbgs() << "ADD DEFERRED: " << *I << '\n');
}
/// Add value to the worklist if it is an instruction.
/// Instructions will be visited in the order they are added.
void addValue(Value *V) {
if (Instruction *I = dyn_cast<Instruction>(V))
add(I);
}
/// Push the instruction onto the worklist stack.
/// Instructions that have been added first will be visited last.
void push(Instruction *I) {
assert(I);
assert(I->getParent() && "Instruction not inserted yet?");
if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
LLVM_DEBUG(dbgs() << "ADD: " << *I << '\n');
Worklist.push_back(I);
}
}
void pushValue(Value *V) {
if (Instruction *I = dyn_cast<Instruction>(V))
push(I);
}
Instruction *popDeferred() {
if (Deferred.empty())
return nullptr;
return Deferred.pop_back_val();
}
void reserve(size_t Size) {
Worklist.reserve(Size + 16);
WorklistMap.reserve(Size);
}
/// Remove I from the worklist if it exists.
void remove(Instruction *I) {
DenseMap<Instruction *, unsigned>::iterator It = WorklistMap.find(I);
if (It != WorklistMap.end()) {
// Don't bother moving everything down, just null out the slot.
Worklist[It->second] = nullptr;
WorklistMap.erase(It);
}
Deferred.remove(I);
}
Instruction *removeOne() {
if (Worklist.empty())
return nullptr;
Instruction *I = Worklist.pop_back_val();
WorklistMap.erase(I);
return I;
}
/// When an instruction is simplified, add all users of the instruction
/// to the work lists because they might get more simplified now.
void pushUsersToWorkList(Instruction &I) {
for (User *U : I.users())
push(cast<Instruction>(U));
}
/// Check that the worklist is empty and nuke the backing store for the map.
void zap() {
assert(WorklistMap.empty() && "Worklist empty, but map not?");
assert(Deferred.empty() && "Deferred instructions left over");
// Do an explicit clear, this shrinks the map if needed.
WorklistMap.clear();
}
};
} // end namespace llvm.
#endif
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
|
