File: | build/source/mlir/lib/Transforms/CSE.cpp |
Warning: | line 284, column 5 Address of stack memory associated with local variable 'scope' is still referred to by the stack variable 'knownValues' upon returning to the caller. This will be a dangling reference |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- CSE.cpp - Common Sub-expression Elimination ------------------------===// | |||
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 | // This transformation pass performs a simple common sub-expression elimination | |||
10 | // algorithm on operations within a region. | |||
11 | // | |||
12 | //===----------------------------------------------------------------------===// | |||
13 | ||||
14 | #include "mlir/Transforms/Passes.h" | |||
15 | ||||
16 | #include "mlir/IR/Dominance.h" | |||
17 | #include "mlir/Interfaces/SideEffectInterfaces.h" | |||
18 | #include "mlir/Pass/Pass.h" | |||
19 | #include "llvm/ADT/DenseMapInfo.h" | |||
20 | #include "llvm/ADT/Hashing.h" | |||
21 | #include "llvm/ADT/ScopedHashTable.h" | |||
22 | #include "llvm/Support/Allocator.h" | |||
23 | #include "llvm/Support/RecyclingAllocator.h" | |||
24 | #include <deque> | |||
25 | ||||
26 | namespace mlir { | |||
27 | #define GEN_PASS_DEF_CSE | |||
28 | #include "mlir/Transforms/Passes.h.inc" | |||
29 | } // namespace mlir | |||
30 | ||||
31 | using namespace mlir; | |||
32 | ||||
33 | namespace { | |||
34 | struct SimpleOperationInfo : public llvm::DenseMapInfo<Operation *> { | |||
35 | static unsigned getHashValue(const Operation *opC) { | |||
36 | return OperationEquivalence::computeHash( | |||
37 | const_cast<Operation *>(opC), | |||
38 | /*hashOperands=*/OperationEquivalence::directHashValue, | |||
39 | /*hashResults=*/OperationEquivalence::ignoreHashValue, | |||
40 | OperationEquivalence::IgnoreLocations); | |||
41 | } | |||
42 | static bool isEqual(const Operation *lhsC, const Operation *rhsC) { | |||
43 | auto *lhs = const_cast<Operation *>(lhsC); | |||
44 | auto *rhs = const_cast<Operation *>(rhsC); | |||
45 | if (lhs == rhs) | |||
46 | return true; | |||
47 | if (lhs == getTombstoneKey() || lhs == getEmptyKey() || | |||
48 | rhs == getTombstoneKey() || rhs == getEmptyKey()) | |||
49 | return false; | |||
50 | return OperationEquivalence::isEquivalentTo( | |||
51 | const_cast<Operation *>(lhsC), const_cast<Operation *>(rhsC), | |||
52 | OperationEquivalence::IgnoreLocations); | |||
53 | } | |||
54 | }; | |||
55 | } // namespace | |||
56 | ||||
57 | namespace { | |||
58 | /// Simple common sub-expression elimination. | |||
59 | struct CSE : public impl::CSEBase<CSE> { | |||
60 | /// Shared implementation of operation elimination and scoped map definitions. | |||
61 | using AllocatorTy = llvm::RecyclingAllocator< | |||
62 | llvm::BumpPtrAllocator, | |||
63 | llvm::ScopedHashTableVal<Operation *, Operation *>>; | |||
64 | using ScopedMapTy = llvm::ScopedHashTable<Operation *, Operation *, | |||
65 | SimpleOperationInfo, AllocatorTy>; | |||
66 | ||||
67 | /// Cache holding MemoryEffects information between two operations. The first | |||
68 | /// operation is stored has the key. The second operation is stored inside a | |||
69 | /// pair in the value. The pair also hold the MemoryEffects between those | |||
70 | /// two operations. If the MemoryEffects is nullptr then we assume there is | |||
71 | /// no operation with MemoryEffects::Write between the two operations. | |||
72 | using MemEffectsCache = | |||
73 | DenseMap<Operation *, std::pair<Operation *, MemoryEffects::Effect *>>; | |||
74 | ||||
75 | /// Represents a single entry in the depth first traversal of a CFG. | |||
76 | struct CFGStackNode { | |||
77 | CFGStackNode(ScopedMapTy &knownValues, DominanceInfoNode *node) | |||
78 | : scope(knownValues), node(node), childIterator(node->begin()) {} | |||
79 | ||||
80 | /// Scope for the known values. | |||
81 | ScopedMapTy::ScopeTy scope; | |||
82 | ||||
83 | DominanceInfoNode *node; | |||
84 | DominanceInfoNode::const_iterator childIterator; | |||
85 | ||||
86 | /// If this node has been fully processed yet or not. | |||
87 | bool processed = false; | |||
88 | }; | |||
89 | ||||
90 | /// Attempt to eliminate a redundant operation. Returns success if the | |||
91 | /// operation was marked for removal, failure otherwise. | |||
92 | LogicalResult simplifyOperation(ScopedMapTy &knownValues, Operation *op, | |||
93 | bool hasSSADominance); | |||
94 | void simplifyBlock(ScopedMapTy &knownValues, Block *bb, bool hasSSADominance); | |||
95 | void simplifyRegion(ScopedMapTy &knownValues, Region ®ion); | |||
96 | ||||
97 | void runOnOperation() override; | |||
98 | ||||
99 | private: | |||
100 | void replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op, | |||
101 | Operation *existing, bool hasSSADominance); | |||
102 | ||||
103 | /// Check if there is side-effecting operations other than the given effect | |||
104 | /// between the two operations. | |||
105 | bool hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp); | |||
106 | ||||
107 | /// Operations marked as dead and to be erased. | |||
108 | std::vector<Operation *> opsToErase; | |||
109 | DominanceInfo *domInfo = nullptr; | |||
110 | MemEffectsCache memEffectsCache; | |||
111 | }; | |||
112 | } // namespace | |||
113 | ||||
114 | void CSE::replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op, | |||
115 | Operation *existing, bool hasSSADominance) { | |||
116 | // If we find one then replace all uses of the current operation with the | |||
117 | // existing one and mark it for deletion. We can only replace an operand in | |||
118 | // an operation if it has not been visited yet. | |||
119 | if (hasSSADominance) { | |||
120 | // If the region has SSA dominance, then we are guaranteed to have not | |||
121 | // visited any use of the current operation. | |||
122 | op->replaceAllUsesWith(existing); | |||
123 | opsToErase.push_back(op); | |||
124 | } else { | |||
125 | // When the region does not have SSA dominance, we need to check if we | |||
126 | // have visited a use before replacing any use. | |||
127 | for (auto it : llvm::zip(op->getResults(), existing->getResults())) { | |||
128 | std::get<0>(it).replaceUsesWithIf( | |||
129 | std::get<1>(it), [&](OpOperand &operand) { | |||
130 | return !knownValues.count(operand.getOwner()); | |||
131 | }); | |||
132 | } | |||
133 | ||||
134 | // There may be some remaining uses of the operation. | |||
135 | if (op->use_empty()) | |||
136 | opsToErase.push_back(op); | |||
137 | } | |||
138 | ||||
139 | // If the existing operation has an unknown location and the current | |||
140 | // operation doesn't, then set the existing op's location to that of the | |||
141 | // current op. | |||
142 | if (existing->getLoc().isa<UnknownLoc>() && !op->getLoc().isa<UnknownLoc>()) | |||
143 | existing->setLoc(op->getLoc()); | |||
144 | ||||
145 | ++numCSE; | |||
146 | } | |||
147 | ||||
148 | bool CSE::hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp) { | |||
149 | assert(fromOp->getBlock() == toOp->getBlock())(static_cast <bool> (fromOp->getBlock() == toOp-> getBlock()) ? void (0) : __assert_fail ("fromOp->getBlock() == toOp->getBlock()" , "mlir/lib/Transforms/CSE.cpp", 149, __extension__ __PRETTY_FUNCTION__ )); | |||
150 | assert((static_cast <bool> (isa<MemoryEffectOpInterface> (fromOp) && cast<MemoryEffectOpInterface>(fromOp ).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface >(toOp) && cast<MemoryEffectOpInterface>(toOp ).hasEffect<MemoryEffects::Read>()) ? void (0) : __assert_fail ("isa<MemoryEffectOpInterface>(fromOp) && cast<MemoryEffectOpInterface>(fromOp).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface>(toOp) && cast<MemoryEffectOpInterface>(toOp).hasEffect<MemoryEffects::Read>()" , "mlir/lib/Transforms/CSE.cpp", 154, __extension__ __PRETTY_FUNCTION__ )) | |||
151 | isa<MemoryEffectOpInterface>(fromOp) &&(static_cast <bool> (isa<MemoryEffectOpInterface> (fromOp) && cast<MemoryEffectOpInterface>(fromOp ).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface >(toOp) && cast<MemoryEffectOpInterface>(toOp ).hasEffect<MemoryEffects::Read>()) ? void (0) : __assert_fail ("isa<MemoryEffectOpInterface>(fromOp) && cast<MemoryEffectOpInterface>(fromOp).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface>(toOp) && cast<MemoryEffectOpInterface>(toOp).hasEffect<MemoryEffects::Read>()" , "mlir/lib/Transforms/CSE.cpp", 154, __extension__ __PRETTY_FUNCTION__ )) | |||
152 | cast<MemoryEffectOpInterface>(fromOp).hasEffect<MemoryEffects::Read>() &&(static_cast <bool> (isa<MemoryEffectOpInterface> (fromOp) && cast<MemoryEffectOpInterface>(fromOp ).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface >(toOp) && cast<MemoryEffectOpInterface>(toOp ).hasEffect<MemoryEffects::Read>()) ? void (0) : __assert_fail ("isa<MemoryEffectOpInterface>(fromOp) && cast<MemoryEffectOpInterface>(fromOp).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface>(toOp) && cast<MemoryEffectOpInterface>(toOp).hasEffect<MemoryEffects::Read>()" , "mlir/lib/Transforms/CSE.cpp", 154, __extension__ __PRETTY_FUNCTION__ )) | |||
153 | isa<MemoryEffectOpInterface>(toOp) &&(static_cast <bool> (isa<MemoryEffectOpInterface> (fromOp) && cast<MemoryEffectOpInterface>(fromOp ).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface >(toOp) && cast<MemoryEffectOpInterface>(toOp ).hasEffect<MemoryEffects::Read>()) ? void (0) : __assert_fail ("isa<MemoryEffectOpInterface>(fromOp) && cast<MemoryEffectOpInterface>(fromOp).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface>(toOp) && cast<MemoryEffectOpInterface>(toOp).hasEffect<MemoryEffects::Read>()" , "mlir/lib/Transforms/CSE.cpp", 154, __extension__ __PRETTY_FUNCTION__ )) | |||
154 | cast<MemoryEffectOpInterface>(toOp).hasEffect<MemoryEffects::Read>())(static_cast <bool> (isa<MemoryEffectOpInterface> (fromOp) && cast<MemoryEffectOpInterface>(fromOp ).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface >(toOp) && cast<MemoryEffectOpInterface>(toOp ).hasEffect<MemoryEffects::Read>()) ? void (0) : __assert_fail ("isa<MemoryEffectOpInterface>(fromOp) && cast<MemoryEffectOpInterface>(fromOp).hasEffect<MemoryEffects::Read>() && isa<MemoryEffectOpInterface>(toOp) && cast<MemoryEffectOpInterface>(toOp).hasEffect<MemoryEffects::Read>()" , "mlir/lib/Transforms/CSE.cpp", 154, __extension__ __PRETTY_FUNCTION__ )); | |||
155 | Operation *nextOp = fromOp->getNextNode(); | |||
156 | auto result = | |||
157 | memEffectsCache.try_emplace(fromOp, std::make_pair(fromOp, nullptr)); | |||
158 | if (result.second) { | |||
159 | auto memEffectsCachePair = result.first->second; | |||
160 | if (memEffectsCachePair.second == nullptr) { | |||
161 | // No MemoryEffects::Write has been detected until the cached operation. | |||
162 | // Continue looking from the cached operation to toOp. | |||
163 | nextOp = memEffectsCachePair.first; | |||
164 | } else { | |||
165 | // MemoryEffects::Write has been detected before so there is no need to | |||
166 | // check further. | |||
167 | return true; | |||
168 | } | |||
169 | } | |||
170 | while (nextOp && nextOp != toOp) { | |||
171 | auto nextOpMemEffects = dyn_cast<MemoryEffectOpInterface>(nextOp); | |||
172 | // TODO: Do we need to handle other effects generically? | |||
173 | // If the operation does not implement the MemoryEffectOpInterface we | |||
174 | // conservatively assumes it writes. | |||
175 | if ((nextOpMemEffects && | |||
176 | nextOpMemEffects.hasEffect<MemoryEffects::Write>()) || | |||
177 | !nextOpMemEffects) { | |||
178 | result.first->second = | |||
179 | std::make_pair(nextOp, MemoryEffects::Write::get()); | |||
180 | return true; | |||
181 | } | |||
182 | nextOp = nextOp->getNextNode(); | |||
183 | } | |||
184 | result.first->second = std::make_pair(toOp, nullptr); | |||
185 | return false; | |||
186 | } | |||
187 | ||||
188 | /// Attempt to eliminate a redundant operation. | |||
189 | LogicalResult CSE::simplifyOperation(ScopedMapTy &knownValues, Operation *op, | |||
190 | bool hasSSADominance) { | |||
191 | // Don't simplify terminator operations. | |||
192 | if (op->hasTrait<OpTrait::IsTerminator>()) | |||
193 | return failure(); | |||
194 | ||||
195 | // If the operation is already trivially dead just add it to the erase list. | |||
196 | if (isOpTriviallyDead(op)) { | |||
197 | opsToErase.push_back(op); | |||
198 | ++numDCE; | |||
199 | return success(); | |||
200 | } | |||
201 | ||||
202 | // Don't simplify operations with regions that have multiple blocks. | |||
203 | // TODO: We need additional tests to verify that we handle such IR correctly. | |||
204 | if (!llvm::all_of(op->getRegions(), [](Region &r) { | |||
205 | return r.getBlocks().empty() || llvm::hasSingleElement(r.getBlocks()); | |||
206 | })) | |||
207 | return failure(); | |||
208 | ||||
209 | // Some simple use case of operation with memory side-effect are dealt with | |||
210 | // here. Operations with no side-effect are done after. | |||
211 | if (!isMemoryEffectFree(op)) { | |||
212 | auto memEffects = dyn_cast<MemoryEffectOpInterface>(op); | |||
213 | // TODO: Only basic use case for operations with MemoryEffects::Read can be | |||
214 | // eleminated now. More work needs to be done for more complicated patterns | |||
215 | // and other side-effects. | |||
216 | if (!memEffects || !memEffects.onlyHasEffect<MemoryEffects::Read>()) | |||
217 | return failure(); | |||
218 | ||||
219 | // Look for an existing definition for the operation. | |||
220 | if (auto *existing = knownValues.lookup(op)) { | |||
221 | if (existing->getBlock() == op->getBlock() && | |||
222 | !hasOtherSideEffectingOpInBetween(existing, op)) { | |||
223 | // The operation that can be deleted has been reach with no | |||
224 | // side-effecting operations in between the existing operation and | |||
225 | // this one so we can remove the duplicate. | |||
226 | replaceUsesAndDelete(knownValues, op, existing, hasSSADominance); | |||
227 | return success(); | |||
228 | } | |||
229 | } | |||
230 | knownValues.insert(op, op); | |||
231 | return failure(); | |||
232 | } | |||
233 | ||||
234 | // Look for an existing definition for the operation. | |||
235 | if (auto *existing = knownValues.lookup(op)) { | |||
236 | replaceUsesAndDelete(knownValues, op, existing, hasSSADominance); | |||
237 | ++numCSE; | |||
238 | return success(); | |||
239 | } | |||
240 | ||||
241 | // Otherwise, we add this operation to the known values map. | |||
242 | knownValues.insert(op, op); | |||
243 | return failure(); | |||
244 | } | |||
245 | ||||
246 | void CSE::simplifyBlock(ScopedMapTy &knownValues, Block *bb, | |||
247 | bool hasSSADominance) { | |||
248 | for (auto &op : *bb) { | |||
249 | // Most operations don't have regions, so fast path that case. | |||
250 | if (op.getNumRegions() != 0) { | |||
251 | // If this operation is isolated above, we can't process nested regions | |||
252 | // with the given 'knownValues' map. This would cause the insertion of | |||
253 | // implicit captures in explicit capture only regions. | |||
254 | if (op.mightHaveTrait<OpTrait::IsIsolatedFromAbove>()) { | |||
255 | ScopedMapTy nestedKnownValues; | |||
256 | for (auto ®ion : op.getRegions()) | |||
257 | simplifyRegion(nestedKnownValues, region); | |||
258 | } else { | |||
259 | // Otherwise, process nested regions normally. | |||
260 | for (auto ®ion : op.getRegions()) | |||
261 | simplifyRegion(knownValues, region); | |||
262 | } | |||
263 | } | |||
264 | ||||
265 | // If the operation is simplified, we don't process any held regions. | |||
266 | if (succeeded(simplifyOperation(knownValues, &op, hasSSADominance))) | |||
267 | continue; | |||
268 | } | |||
269 | // Clear the MemoryEffects cache since its usage is by block only. | |||
270 | memEffectsCache.clear(); | |||
271 | } | |||
272 | ||||
273 | void CSE::simplifyRegion(ScopedMapTy &knownValues, Region ®ion) { | |||
274 | // If the region is empty there is nothing to do. | |||
275 | if (region.empty()) | |||
276 | return; | |||
277 | ||||
278 | bool hasSSADominance = domInfo->hasSSADominance(®ion); | |||
279 | ||||
280 | // If the region only contains one block, then simplify it directly. | |||
281 | if (region.hasOneBlock()) { | |||
282 | ScopedMapTy::ScopeTy scope(knownValues); | |||
283 | simplifyBlock(knownValues, ®ion.front(), hasSSADominance); | |||
284 | return; | |||
| ||||
285 | } | |||
286 | ||||
287 | // If the region does not have dominanceInfo, then skip it. | |||
288 | // TODO: Regions without SSA dominance should define a different | |||
289 | // traversal order which is appropriate and can be used here. | |||
290 | if (!hasSSADominance) | |||
291 | return; | |||
292 | ||||
293 | // Note, deque is being used here because there was significant performance | |||
294 | // gains over vector when the container becomes very large due to the | |||
295 | // specific access patterns. If/when these performance issues are no | |||
296 | // longer a problem we can change this to vector. For more information see | |||
297 | // the llvm mailing list discussion on this: | |||
298 | // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html | |||
299 | std::deque<std::unique_ptr<CFGStackNode>> stack; | |||
300 | ||||
301 | // Process the nodes of the dom tree for this region. | |||
302 | stack.emplace_back(std::make_unique<CFGStackNode>( | |||
303 | knownValues, domInfo->getRootNode(®ion))); | |||
304 | ||||
305 | while (!stack.empty()) { | |||
306 | auto ¤tNode = stack.back(); | |||
307 | ||||
308 | // Check to see if we need to process this node. | |||
309 | if (!currentNode->processed) { | |||
310 | currentNode->processed = true; | |||
311 | simplifyBlock(knownValues, currentNode->node->getBlock(), | |||
312 | hasSSADominance); | |||
313 | } | |||
314 | ||||
315 | // Otherwise, check to see if we need to process a child node. | |||
316 | if (currentNode->childIterator != currentNode->node->end()) { | |||
317 | auto *childNode = *(currentNode->childIterator++); | |||
318 | stack.emplace_back( | |||
319 | std::make_unique<CFGStackNode>(knownValues, childNode)); | |||
320 | } else { | |||
321 | // Finally, if the node and all of its children have been processed | |||
322 | // then we delete the node. | |||
323 | stack.pop_back(); | |||
324 | } | |||
325 | } | |||
326 | } | |||
327 | ||||
328 | void CSE::runOnOperation() { | |||
329 | /// A scoped hash table of defining operations within a region. | |||
330 | ScopedMapTy knownValues; | |||
331 | ||||
332 | domInfo = &getAnalysis<DominanceInfo>(); | |||
333 | Operation *rootOp = getOperation(); | |||
334 | ||||
335 | for (auto ®ion : rootOp->getRegions()) | |||
| ||||
336 | simplifyRegion(knownValues, region); | |||
337 | ||||
338 | // If no operations were erased, then we mark all analyses as preserved. | |||
339 | if (opsToErase.empty()) | |||
340 | return markAllAnalysesPreserved(); | |||
341 | ||||
342 | /// Erase any operations that were marked as dead during simplification. | |||
343 | for (auto *op : opsToErase) | |||
344 | op->erase(); | |||
345 | opsToErase.clear(); | |||
346 | ||||
347 | // We currently don't remove region operations, so mark dominance as | |||
348 | // preserved. | |||
349 | markAnalysesPreserved<DominanceInfo, PostDominanceInfo>(); | |||
350 | domInfo = nullptr; | |||
351 | } | |||
352 | ||||
353 | std::unique_ptr<Pass> mlir::createCSEPass() { return std::make_unique<CSE>(); } |