Bug Summary

File:build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/mlir/lib/Transforms/CSE.cpp
Warning:line 287, 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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name CSE.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D MLIR_CUDA_CONVERSIONS_ENABLED=1 -D MLIR_ROCM_CONVERSIONS_ENABLED=1 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/mlir/lib/Transforms -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/mlir/lib/Transforms -I include -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/include -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/mlir/include -I tools/mlir/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-10-03-140002-15933-1 -x c++ /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/mlir/lib/Transforms/CSE.cpp
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
26namespace mlir {
27#define GEN_PASS_DEF_CSE
28#include "mlir/Transforms/Passes.h.inc"
29} // namespace mlir
30
31using namespace mlir;
32
33namespace {
34struct 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 /*mapOperands=*/OperationEquivalence::exactValueMatch,
53 /*mapResults=*/OperationEquivalence::ignoreValueEquivalence,
54 OperationEquivalence::IgnoreLocations);
55 }
56};
57} // namespace
58
59namespace {
60/// Simple common sub-expression elimination.
61struct CSE : public impl::CSEBase<CSE> {
62 /// Shared implementation of operation elimination and scoped map definitions.
63 using AllocatorTy = llvm::RecyclingAllocator<
64 llvm::BumpPtrAllocator,
65 llvm::ScopedHashTableVal<Operation *, Operation *>>;
66 using ScopedMapTy = llvm::ScopedHashTable<Operation *, Operation *,
67 SimpleOperationInfo, AllocatorTy>;
68
69 /// Cache holding MemoryEffects information between two operations. The first
70 /// operation is stored has the key. The second operation is stored inside a
71 /// pair in the value. The pair also hold the MemoryEffects between those
72 /// two operations. If the MemoryEffects is nullptr then we assume there is
73 /// no operation with MemoryEffects::Write between the two operations.
74 using MemEffectsCache =
75 DenseMap<Operation *, std::pair<Operation *, MemoryEffects::Effect *>>;
76
77 /// Represents a single entry in the depth first traversal of a CFG.
78 struct CFGStackNode {
79 CFGStackNode(ScopedMapTy &knownValues, DominanceInfoNode *node)
80 : scope(knownValues), node(node), childIterator(node->begin()) {}
81
82 /// Scope for the known values.
83 ScopedMapTy::ScopeTy scope;
84
85 DominanceInfoNode *node;
86 DominanceInfoNode::const_iterator childIterator;
87
88 /// If this node has been fully processed yet or not.
89 bool processed = false;
90 };
91
92 /// Attempt to eliminate a redundant operation. Returns success if the
93 /// operation was marked for removal, failure otherwise.
94 LogicalResult simplifyOperation(ScopedMapTy &knownValues, Operation *op,
95 bool hasSSADominance);
96 void simplifyBlock(ScopedMapTy &knownValues, Block *bb, bool hasSSADominance);
97 void simplifyRegion(ScopedMapTy &knownValues, Region &region);
98
99 void runOnOperation() override;
100
101private:
102 void replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op,
103 Operation *existing, bool hasSSADominance);
104
105 /// Check if there is side-effecting operations other than the given effect
106 /// between the two operations.
107 bool hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp);
108
109 /// Operations marked as dead and to be erased.
110 std::vector<Operation *> opsToErase;
111 DominanceInfo *domInfo = nullptr;
112 MemEffectsCache memEffectsCache;
113};
114} // namespace
115
116void CSE::replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op,
117 Operation *existing, bool hasSSADominance) {
118 // If we find one then replace all uses of the current operation with the
119 // existing one and mark it for deletion. We can only replace an operand in
120 // an operation if it has not been visited yet.
121 if (hasSSADominance) {
122 // If the region has SSA dominance, then we are guaranteed to have not
123 // visited any use of the current operation.
124 op->replaceAllUsesWith(existing);
125 opsToErase.push_back(op);
126 } else {
127 // When the region does not have SSA dominance, we need to check if we
128 // have visited a use before replacing any use.
129 for (auto it : llvm::zip(op->getResults(), existing->getResults())) {
130 std::get<0>(it).replaceUsesWithIf(
131 std::get<1>(it), [&](OpOperand &operand) {
132 return !knownValues.count(operand.getOwner());
133 });
134 }
135
136 // There may be some remaining uses of the operation.
137 if (op->use_empty())
138 opsToErase.push_back(op);
139 }
140
141 // If the existing operation has an unknown location and the current
142 // operation doesn't, then set the existing op's location to that of the
143 // current op.
144 if (existing->getLoc().isa<UnknownLoc>() && !op->getLoc().isa<UnknownLoc>())
145 existing->setLoc(op->getLoc());
146
147 ++numCSE;
148}
149
150bool CSE::hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp) {
151 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", 151, __extension__ __PRETTY_FUNCTION__
))
;
152 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", 156, __extension__ __PRETTY_FUNCTION__
))
153 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", 156, __extension__ __PRETTY_FUNCTION__
))
154 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", 156, __extension__ __PRETTY_FUNCTION__
))
155 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", 156, __extension__ __PRETTY_FUNCTION__
))
156 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", 156, __extension__ __PRETTY_FUNCTION__
))
;
157 Operation *nextOp = fromOp->getNextNode();
158 auto result =
159 memEffectsCache.try_emplace(fromOp, std::make_pair(fromOp, nullptr));
160 if (result.second) {
161 auto memEffectsCachePair = result.first->second;
162 if (memEffectsCachePair.second == nullptr) {
163 // No MemoryEffects::Write has been detected until the cached operation.
164 // Continue looking from the cached operation to toOp.
165 nextOp = memEffectsCachePair.first;
166 } else {
167 // MemoryEffects::Write has been detected before so there is no need to
168 // check further.
169 return true;
170 }
171 }
172 while (nextOp && nextOp != toOp) {
173 auto nextOpMemEffects = dyn_cast<MemoryEffectOpInterface>(nextOp);
174 // TODO: Do we need to handle other effects generically?
175 // If the operation does not implement the MemoryEffectOpInterface we
176 // conservatively assumes it writes.
177 if ((nextOpMemEffects &&
178 nextOpMemEffects.hasEffect<MemoryEffects::Write>()) ||
179 !nextOpMemEffects) {
180 result.first->second =
181 std::make_pair(nextOp, MemoryEffects::Write::get());
182 return true;
183 }
184 nextOp = nextOp->getNextNode();
185 }
186 result.first->second = std::make_pair(toOp, nullptr);
187 return false;
188}
189
190/// Attempt to eliminate a redundant operation.
191LogicalResult CSE::simplifyOperation(ScopedMapTy &knownValues, Operation *op,
192 bool hasSSADominance) {
193 // Don't simplify terminator operations.
194 if (op->hasTrait<OpTrait::IsTerminator>())
195 return failure();
196
197 // If the operation is already trivially dead just add it to the erase list.
198 if (isOpTriviallyDead(op)) {
199 opsToErase.push_back(op);
200 ++numDCE;
201 return success();
202 }
203
204 // Don't simplify operations with nested blocks. We don't currently model
205 // equality comparisons correctly among other things. It is also unclear
206 // whether we would want to CSE such operations.
207 if (op->getNumRegions() != 0)
208 return failure();
209
210 // Some simple use case of operation with memory side-effect are dealt with
211 // here. Operations with no side-effect are done after.
212 if (!MemoryEffectOpInterface::hasNoEffect(op)) {
213 auto memEffects = dyn_cast<MemoryEffectOpInterface>(op);
214 // TODO: Only basic use case for operations with MemoryEffects::Read can be
215 // eleminated now. More work needs to be done for more complicated patterns
216 // and other side-effects.
217 if (!memEffects || !memEffects.onlyHasEffect<MemoryEffects::Read>())
218 return failure();
219
220 // Look for an existing definition for the operation.
221 if (auto *existing = knownValues.lookup(op)) {
222 if (existing->getBlock() == op->getBlock() &&
223 !hasOtherSideEffectingOpInBetween(existing, op)) {
224 // The operation that can be deleted has been reach with no
225 // side-effecting operations in between the existing operation and
226 // this one so we can remove the duplicate.
227 replaceUsesAndDelete(knownValues, op, existing, hasSSADominance);
228 return success();
229 }
230 }
231 knownValues.insert(op, op);
232 return failure();
233 }
234
235 // Look for an existing definition for the operation.
236 if (auto *existing = knownValues.lookup(op)) {
237 replaceUsesAndDelete(knownValues, op, existing, hasSSADominance);
238 ++numCSE;
239 return success();
240 }
241
242 // Otherwise, we add this operation to the known values map.
243 knownValues.insert(op, op);
244 return failure();
245}
246
247void CSE::simplifyBlock(ScopedMapTy &knownValues, Block *bb,
248 bool hasSSADominance) {
249 for (auto &op : *bb) {
250 // If the operation is simplified, we don't process any held regions.
251 if (succeeded(simplifyOperation(knownValues, &op, hasSSADominance)))
252 continue;
253
254 // Most operations don't have regions, so fast path that case.
255 if (op.getNumRegions() == 0)
256 continue;
257
258 // If this operation is isolated above, we can't process nested regions with
259 // the given 'knownValues' map. This would cause the insertion of implicit
260 // captures in explicit capture only regions.
261 if (op.mightHaveTrait<OpTrait::IsIsolatedFromAbove>()) {
262 ScopedMapTy nestedKnownValues;
263 for (auto &region : op.getRegions())
264 simplifyRegion(nestedKnownValues, region);
265 continue;
266 }
267
268 // Otherwise, process nested regions normally.
269 for (auto &region : op.getRegions())
270 simplifyRegion(knownValues, region);
271 }
272 // Clear the MemoryEffects cache since its usage is by block only.
273 memEffectsCache.clear();
274}
275
276void CSE::simplifyRegion(ScopedMapTy &knownValues, Region &region) {
277 // If the region is empty there is nothing to do.
278 if (region.empty())
3
Assuming the condition is false
4
Taking false branch
279 return;
280
281 bool hasSSADominance = domInfo->hasSSADominance(&region);
282
283 // If the region only contains one block, then simplify it directly.
284 if (region.hasOneBlock()) {
5
Assuming the condition is true
6
Taking true branch
285 ScopedMapTy::ScopeTy scope(knownValues);
286 simplifyBlock(knownValues, &region.front(), hasSSADominance);
287 return;
7
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
288 }
289
290 // If the region does not have dominanceInfo, then skip it.
291 // TODO: Regions without SSA dominance should define a different
292 // traversal order which is appropriate and can be used here.
293 if (!hasSSADominance)
294 return;
295
296 // Note, deque is being used here because there was significant performance
297 // gains over vector when the container becomes very large due to the
298 // specific access patterns. If/when these performance issues are no
299 // longer a problem we can change this to vector. For more information see
300 // the llvm mailing list discussion on this:
301 // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
302 std::deque<std::unique_ptr<CFGStackNode>> stack;
303
304 // Process the nodes of the dom tree for this region.
305 stack.emplace_back(std::make_unique<CFGStackNode>(
306 knownValues, domInfo->getRootNode(&region)));
307
308 while (!stack.empty()) {
309 auto &currentNode = stack.back();
310
311 // Check to see if we need to process this node.
312 if (!currentNode->processed) {
313 currentNode->processed = true;
314 simplifyBlock(knownValues, currentNode->node->getBlock(),
315 hasSSADominance);
316 }
317
318 // Otherwise, check to see if we need to process a child node.
319 if (currentNode->childIterator != currentNode->node->end()) {
320 auto *childNode = *(currentNode->childIterator++);
321 stack.emplace_back(
322 std::make_unique<CFGStackNode>(knownValues, childNode));
323 } else {
324 // Finally, if the node and all of its children have been processed
325 // then we delete the node.
326 stack.pop_back();
327 }
328 }
329}
330
331void CSE::runOnOperation() {
332 /// A scoped hash table of defining operations within a region.
333 ScopedMapTy knownValues;
334
335 domInfo = &getAnalysis<DominanceInfo>();
336 Operation *rootOp = getOperation();
337
338 for (auto &region : rootOp->getRegions())
1
Assuming '__begin1' is not equal to '__end1'
339 simplifyRegion(knownValues, region);
2
Calling 'CSE::simplifyRegion'
340
341 // If no operations were erased, then we mark all analyses as preserved.
342 if (opsToErase.empty())
343 return markAllAnalysesPreserved();
344
345 /// Erase any operations that were marked as dead during simplification.
346 for (auto *op : opsToErase)
347 op->erase();
348 opsToErase.clear();
349
350 // We currently don't remove region operations, so mark dominance as
351 // preserved.
352 markAnalysesPreserved<DominanceInfo, PostDominanceInfo>();
353 domInfo = nullptr;
354}
355
356std::unique_ptr<Pass> mlir::createCSEPass() { return std::make_unique<CSE>(); }