/
CSE.cpp
413 lines (360 loc) · 15.3 KB
/
CSE.cpp
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
//===- CSE.cpp - Common Sub-expression Elimination ------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This transformation pass performs a simple common sub-expression elimination
// algorithm on operations within a region.
//
//===----------------------------------------------------------------------===//
#include "mlir/Transforms/CSE.h"
#include "mlir/IR/Dominance.h"
#include "mlir/IR/PatternMatch.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
#include "mlir/Pass/Pass.h"
#include "mlir/Transforms/Passes.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/ScopedHashTable.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/RecyclingAllocator.h"
#include <deque>
namespace mlir {
#define GEN_PASS_DEF_CSE
#include "mlir/Transforms/Passes.h.inc"
} // namespace mlir
using namespace mlir;
namespace {
struct SimpleOperationInfo : public llvm::DenseMapInfo<Operation *> {
static unsigned getHashValue(const Operation *opC) {
return OperationEquivalence::computeHash(
const_cast<Operation *>(opC),
/*hashOperands=*/OperationEquivalence::directHashValue,
/*hashResults=*/OperationEquivalence::ignoreHashValue,
OperationEquivalence::IgnoreLocations);
}
static bool isEqual(const Operation *lhsC, const Operation *rhsC) {
auto *lhs = const_cast<Operation *>(lhsC);
auto *rhs = const_cast<Operation *>(rhsC);
if (lhs == rhs)
return true;
if (lhs == getTombstoneKey() || lhs == getEmptyKey() ||
rhs == getTombstoneKey() || rhs == getEmptyKey())
return false;
return OperationEquivalence::isEquivalentTo(
const_cast<Operation *>(lhsC), const_cast<Operation *>(rhsC),
OperationEquivalence::IgnoreLocations);
}
};
} // namespace
namespace {
/// Simple common sub-expression elimination.
class CSEDriver {
public:
CSEDriver(RewriterBase &rewriter, DominanceInfo &domInfo)
: rewriter(rewriter), domInfo(domInfo) {}
/// Simplify all operations within the given op.
void simplify(Operation *op, bool *changed = nullptr);
int64_t getNumCSE() const { return numCSE; }
int64_t getNumDCE() const { return numDCE; }
private:
/// Shared implementation of operation elimination and scoped map definitions.
using AllocatorTy = llvm::RecyclingAllocator<
llvm::BumpPtrAllocator,
llvm::ScopedHashTableVal<Operation *, Operation *>>;
using ScopedMapTy = llvm::ScopedHashTable<Operation *, Operation *,
SimpleOperationInfo, AllocatorTy>;
/// Cache holding MemoryEffects information between two operations. The first
/// operation is stored has the key. The second operation is stored inside a
/// pair in the value. The pair also hold the MemoryEffects between those
/// two operations. If the MemoryEffects is nullptr then we assume there is
/// no operation with MemoryEffects::Write between the two operations.
using MemEffectsCache =
DenseMap<Operation *, std::pair<Operation *, MemoryEffects::Effect *>>;
/// Represents a single entry in the depth first traversal of a CFG.
struct CFGStackNode {
CFGStackNode(ScopedMapTy &knownValues, DominanceInfoNode *node)
: scope(knownValues), node(node), childIterator(node->begin()) {}
/// Scope for the known values.
ScopedMapTy::ScopeTy scope;
DominanceInfoNode *node;
DominanceInfoNode::const_iterator childIterator;
/// If this node has been fully processed yet or not.
bool processed = false;
};
/// Attempt to eliminate a redundant operation. Returns success if the
/// operation was marked for removal, failure otherwise.
LogicalResult simplifyOperation(ScopedMapTy &knownValues, Operation *op,
bool hasSSADominance);
void simplifyBlock(ScopedMapTy &knownValues, Block *bb, bool hasSSADominance);
void simplifyRegion(ScopedMapTy &knownValues, Region ®ion);
void replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op,
Operation *existing, bool hasSSADominance);
/// Check if there is side-effecting operations other than the given effect
/// between the two operations.
bool hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp);
/// A rewriter for modifying the IR.
RewriterBase &rewriter;
/// Operations marked as dead and to be erased.
std::vector<Operation *> opsToErase;
DominanceInfo &domInfo;
MemEffectsCache memEffectsCache;
// Various statistics.
int64_t numCSE = 0;
int64_t numDCE = 0;
};
} // namespace
void CSEDriver::replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op,
Operation *existing,
bool hasSSADominance) {
// If we find one then replace all uses of the current operation with the
// existing one and mark it for deletion. We can only replace an operand in
// an operation if it has not been visited yet.
if (hasSSADominance) {
// If the region has SSA dominance, then we are guaranteed to have not
// visited any use of the current operation.
if (auto *rewriteListener =
dyn_cast_if_present<RewriterBase::Listener>(rewriter.getListener()))
rewriteListener->notifyOperationReplaced(op, existing);
// Replace all uses, but do not remote the operation yet. This does not
// notify the listener because the original op is not erased.
rewriter.replaceAllUsesWith(op->getResults(), existing->getResults());
opsToErase.push_back(op);
} else {
// When the region does not have SSA dominance, we need to check if we
// have visited a use before replacing any use.
auto wasVisited = [&](OpOperand &operand) {
return !knownValues.count(operand.getOwner());
};
if (auto *rewriteListener = dyn_cast_if_present<RewriterBase::Listener>(
rewriter.getListener())) {
for (Value v : op->getResults()) {
if (all_of(v.getUses(), wasVisited)) {
rewriteListener->notifyOperationReplaced(op, existing);
}
}
}
// Replace all uses, but do not remote the operation yet. This does not
// notify the listener because the original op is not erased.
rewriter.replaceUsesWithIf(op->getResults(), existing->getResults(),
wasVisited);
// There may be some remaining uses of the operation.
if (op->use_empty())
opsToErase.push_back(op);
}
// If the existing operation has an unknown location and the current
// operation doesn't, then set the existing op's location to that of the
// current op.
if (isa<UnknownLoc>(existing->getLoc()) && !isa<UnknownLoc>(op->getLoc()))
existing->setLoc(op->getLoc());
++numCSE;
}
bool CSEDriver::hasOtherSideEffectingOpInBetween(Operation *fromOp,
Operation *toOp) {
assert(fromOp->getBlock() == toOp->getBlock());
assert(
isa<MemoryEffectOpInterface>(fromOp) &&
cast<MemoryEffectOpInterface>(fromOp).hasEffect<MemoryEffects::Read>() &&
isa<MemoryEffectOpInterface>(toOp) &&
cast<MemoryEffectOpInterface>(toOp).hasEffect<MemoryEffects::Read>());
Operation *nextOp = fromOp->getNextNode();
auto result =
memEffectsCache.try_emplace(fromOp, std::make_pair(fromOp, nullptr));
if (result.second) {
auto memEffectsCachePair = result.first->second;
if (memEffectsCachePair.second == nullptr) {
// No MemoryEffects::Write has been detected until the cached operation.
// Continue looking from the cached operation to toOp.
nextOp = memEffectsCachePair.first;
} else {
// MemoryEffects::Write has been detected before so there is no need to
// check further.
return true;
}
}
while (nextOp && nextOp != toOp) {
auto nextOpMemEffects = dyn_cast<MemoryEffectOpInterface>(nextOp);
// TODO: Do we need to handle other effects generically?
// If the operation does not implement the MemoryEffectOpInterface we
// conservatively assumes it writes.
if ((nextOpMemEffects &&
nextOpMemEffects.hasEffect<MemoryEffects::Write>()) ||
!nextOpMemEffects) {
result.first->second =
std::make_pair(nextOp, MemoryEffects::Write::get());
return true;
}
nextOp = nextOp->getNextNode();
}
result.first->second = std::make_pair(toOp, nullptr);
return false;
}
/// Attempt to eliminate a redundant operation.
LogicalResult CSEDriver::simplifyOperation(ScopedMapTy &knownValues,
Operation *op,
bool hasSSADominance) {
// Don't simplify terminator operations.
if (op->hasTrait<OpTrait::IsTerminator>())
return failure();
// If the operation is already trivially dead just add it to the erase list.
if (isOpTriviallyDead(op)) {
opsToErase.push_back(op);
++numDCE;
return success();
}
// Don't simplify operations with regions that have multiple blocks.
// TODO: We need additional tests to verify that we handle such IR correctly.
if (!llvm::all_of(op->getRegions(), [](Region &r) {
return r.getBlocks().empty() || llvm::hasSingleElement(r.getBlocks());
}))
return failure();
// Some simple use case of operation with memory side-effect are dealt with
// here. Operations with no side-effect are done after.
if (!isMemoryEffectFree(op)) {
auto memEffects = dyn_cast<MemoryEffectOpInterface>(op);
// TODO: Only basic use case for operations with MemoryEffects::Read can be
// eleminated now. More work needs to be done for more complicated patterns
// and other side-effects.
if (!memEffects || !memEffects.onlyHasEffect<MemoryEffects::Read>())
return failure();
// Look for an existing definition for the operation.
if (auto *existing = knownValues.lookup(op)) {
if (existing->getBlock() == op->getBlock() &&
!hasOtherSideEffectingOpInBetween(existing, op)) {
// The operation that can be deleted has been reach with no
// side-effecting operations in between the existing operation and
// this one so we can remove the duplicate.
replaceUsesAndDelete(knownValues, op, existing, hasSSADominance);
return success();
}
}
knownValues.insert(op, op);
return failure();
}
// Look for an existing definition for the operation.
if (auto *existing = knownValues.lookup(op)) {
replaceUsesAndDelete(knownValues, op, existing, hasSSADominance);
++numCSE;
return success();
}
// Otherwise, we add this operation to the known values map.
knownValues.insert(op, op);
return failure();
}
void CSEDriver::simplifyBlock(ScopedMapTy &knownValues, Block *bb,
bool hasSSADominance) {
for (auto &op : *bb) {
// Most operations don't have regions, so fast path that case.
if (op.getNumRegions() != 0) {
// If this operation is isolated above, we can't process nested regions
// with the given 'knownValues' map. This would cause the insertion of
// implicit captures in explicit capture only regions.
if (op.mightHaveTrait<OpTrait::IsIsolatedFromAbove>()) {
ScopedMapTy nestedKnownValues;
for (auto ®ion : op.getRegions())
simplifyRegion(nestedKnownValues, region);
} else {
// Otherwise, process nested regions normally.
for (auto ®ion : op.getRegions())
simplifyRegion(knownValues, region);
}
}
// If the operation is simplified, we don't process any held regions.
if (succeeded(simplifyOperation(knownValues, &op, hasSSADominance)))
continue;
}
// Clear the MemoryEffects cache since its usage is by block only.
memEffectsCache.clear();
}
void CSEDriver::simplifyRegion(ScopedMapTy &knownValues, Region ®ion) {
// If the region is empty there is nothing to do.
if (region.empty())
return;
bool hasSSADominance = domInfo.hasSSADominance(®ion);
// If the region only contains one block, then simplify it directly.
if (region.hasOneBlock()) {
ScopedMapTy::ScopeTy scope(knownValues);
simplifyBlock(knownValues, ®ion.front(), hasSSADominance);
return;
}
// If the region does not have dominanceInfo, then skip it.
// TODO: Regions without SSA dominance should define a different
// traversal order which is appropriate and can be used here.
if (!hasSSADominance)
return;
// Note, deque is being used here because there was significant performance
// gains over vector when the container becomes very large due to the
// specific access patterns. If/when these performance issues are no
// longer a problem we can change this to vector. For more information see
// the llvm mailing list discussion on this:
// http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
std::deque<std::unique_ptr<CFGStackNode>> stack;
// Process the nodes of the dom tree for this region.
stack.emplace_back(std::make_unique<CFGStackNode>(
knownValues, domInfo.getRootNode(®ion)));
while (!stack.empty()) {
auto ¤tNode = stack.back();
// Check to see if we need to process this node.
if (!currentNode->processed) {
currentNode->processed = true;
simplifyBlock(knownValues, currentNode->node->getBlock(),
hasSSADominance);
}
// Otherwise, check to see if we need to process a child node.
if (currentNode->childIterator != currentNode->node->end()) {
auto *childNode = *(currentNode->childIterator++);
stack.emplace_back(
std::make_unique<CFGStackNode>(knownValues, childNode));
} else {
// Finally, if the node and all of its children have been processed
// then we delete the node.
stack.pop_back();
}
}
}
void CSEDriver::simplify(Operation *op, bool *changed) {
/// Simplify all regions.
ScopedMapTy knownValues;
for (auto ®ion : op->getRegions())
simplifyRegion(knownValues, region);
/// Erase any operations that were marked as dead during simplification.
for (auto *op : opsToErase)
rewriter.eraseOp(op);
if (changed)
*changed = !opsToErase.empty();
/// Invalidate dominance info if the IR was changed.
if (!opsToErase.empty())
domInfo.invalidate();
}
void mlir::eliminateCommonSubExpressions(RewriterBase &rewriter,
DominanceInfo &domInfo, Operation *op,
bool *changed) {
CSEDriver driver(rewriter, domInfo);
driver.simplify(op, changed);
}
namespace {
/// CSE pass.
struct CSE : public impl::CSEBase<CSE> {
void runOnOperation() override;
};
} // namespace
void CSE::runOnOperation() {
// Simplify the IR.
IRRewriter rewriter(&getContext());
CSEDriver driver(rewriter, getAnalysis<DominanceInfo>());
bool changed = false;
driver.simplify(getOperation(), &changed);
// Set statistics.
numCSE = driver.getNumCSE();
numDCE = driver.getNumDCE();
// If there was no change to the IR, we mark all analyses as preserved.
if (!changed)
return markAllAnalysesPreserved();
// We currently don't remove region operations, so mark dominance as
// preserved.
markAnalysesPreserved<DominanceInfo, PostDominanceInfo>();
}
std::unique_ptr<Pass> mlir::createCSEPass() { return std::make_unique<CSE>(); }