/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- TypeErasedDataflowAnalysis.cpp -------------------------------------===// |
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 file defines type-erased base types and functions for building dataflow |
10 | | // analyses that run over Control-Flow Graphs (CFGs). |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include <memory> |
15 | | #include <system_error> |
16 | | #include <utility> |
17 | | #include <vector> |
18 | | |
19 | | #include "clang/AST/DeclCXX.h" |
20 | | #include "clang/AST/OperationKinds.h" |
21 | | #include "clang/AST/StmtVisitor.h" |
22 | | #include "clang/Analysis/Analyses/PostOrderCFGView.h" |
23 | | #include "clang/Analysis/CFG.h" |
24 | | #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" |
25 | | #include "clang/Analysis/FlowSensitive/DataflowWorklist.h" |
26 | | #include "clang/Analysis/FlowSensitive/Transfer.h" |
27 | | #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h" |
28 | | #include "clang/Analysis/FlowSensitive/Value.h" |
29 | | #include "llvm/ADT/ArrayRef.h" |
30 | | #include "llvm/ADT/DenseSet.h" |
31 | | #include "llvm/ADT/None.h" |
32 | | #include "llvm/ADT/Optional.h" |
33 | | #include "llvm/ADT/STLExtras.h" |
34 | | #include "llvm/Support/Error.h" |
35 | | #include "llvm/Support/ErrorHandling.h" |
36 | | |
37 | | namespace clang { |
38 | | namespace dataflow { |
39 | | |
40 | | class StmtToEnvMapImpl : public StmtToEnvMap { |
41 | | public: |
42 | | StmtToEnvMapImpl( |
43 | | const ControlFlowContext &CFCtx, |
44 | | llvm::ArrayRef<llvm::Optional<TypeErasedDataflowAnalysisState>> |
45 | | BlockToState) |
46 | 6.18k | : CFCtx(CFCtx), BlockToState(BlockToState) {} |
47 | | |
48 | 48 | const Environment *getEnvironment(const Stmt &S) const override { |
49 | 48 | auto BlockIT = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S)); |
50 | 48 | assert(BlockIT != CFCtx.getStmtToBlock().end()); |
51 | 0 | const auto &State = BlockToState[BlockIT->getSecond()->getBlockID()]; |
52 | 48 | assert(State.hasValue()); |
53 | 0 | return &State.getValue().Env; |
54 | 48 | } |
55 | | |
56 | | private: |
57 | | const ControlFlowContext &CFCtx; |
58 | | llvm::ArrayRef<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockToState; |
59 | | }; |
60 | | |
61 | | /// Returns the index of `Block` in the successors of `Pred`. |
62 | | static int blockIndexInPredecessor(const CFGBlock &Pred, |
63 | 412 | const CFGBlock &Block) { |
64 | 412 | auto BlockPos = llvm::find_if( |
65 | 616 | Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) { |
66 | 616 | return Succ && Succ->getBlockID() == Block.getBlockID(); |
67 | 616 | }); |
68 | 412 | return BlockPos - Pred.succ_begin(); |
69 | 412 | } |
70 | | |
71 | | /// Extends the flow condition of an environment based on a terminator |
72 | | /// statement. |
73 | | class TerminatorVisitor : public ConstStmtVisitor<TerminatorVisitor> { |
74 | | public: |
75 | | TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, |
76 | | int BlockSuccIdx) |
77 | 412 | : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx) {} |
78 | | |
79 | 268 | void VisitIfStmt(const IfStmt *S) { |
80 | 268 | auto *Cond = S->getCond(); |
81 | 268 | assert(Cond != nullptr); |
82 | 0 | extendFlowCondition(*Cond); |
83 | 268 | } |
84 | | |
85 | 12 | void VisitWhileStmt(const WhileStmt *S) { |
86 | 12 | auto *Cond = S->getCond(); |
87 | 12 | assert(Cond != nullptr); |
88 | 0 | extendFlowCondition(*Cond); |
89 | 12 | } |
90 | | |
91 | 32 | void VisitBinaryOperator(const BinaryOperator *S) { |
92 | 32 | assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr); |
93 | 0 | auto *LHS = S->getLHS(); |
94 | 32 | assert(LHS != nullptr); |
95 | 0 | extendFlowCondition(*LHS); |
96 | 32 | } |
97 | | |
98 | 48 | void VisitConditionalOperator(const ConditionalOperator *S) { |
99 | 48 | auto *Cond = S->getCond(); |
100 | 48 | assert(Cond != nullptr); |
101 | 0 | extendFlowCondition(*Cond); |
102 | 48 | } |
103 | | |
104 | | private: |
105 | 360 | void extendFlowCondition(const Expr &Cond) { |
106 | | // The terminator sub-expression might not be evaluated. |
107 | 360 | if (Env.getValue(Cond, SkipPast::None) == nullptr) |
108 | 28 | transfer(StmtToEnv, Cond, Env); |
109 | | |
110 | | // FIXME: The flow condition must be an r-value, so `SkipPast::None` should |
111 | | // suffice. |
112 | 360 | auto *Val = |
113 | 360 | cast_or_null<BoolValue>(Env.getValue(Cond, SkipPast::Reference)); |
114 | | // Value merging depends on flow conditions from different environments |
115 | | // being mutually exclusive -- that is, they cannot both be true in their |
116 | | // entirety (even if they may share some clauses). So, we need *some* value |
117 | | // for the condition expression, even if just an atom. |
118 | 360 | if (Val == nullptr) { |
119 | | // FIXME: Consider introducing a helper for this get-or-create pattern. |
120 | 16 | auto *Loc = Env.getStorageLocation(Cond, SkipPast::None); |
121 | 16 | if (Loc == nullptr) { |
122 | 16 | Loc = &Env.createStorageLocation(Cond); |
123 | 16 | Env.setStorageLocation(Cond, *Loc); |
124 | 16 | } |
125 | 16 | Val = &Env.makeAtomicBoolValue(); |
126 | 16 | Env.setValue(*Loc, *Val); |
127 | 16 | } |
128 | | |
129 | | // The condition must be inverted for the successor that encompasses the |
130 | | // "else" branch, if such exists. |
131 | 360 | if (BlockSuccIdx == 1) |
132 | 180 | Val = &Env.makeNot(*Val); |
133 | | |
134 | 360 | Env.addToFlowCondition(*Val); |
135 | 360 | } |
136 | | |
137 | | const StmtToEnvMap &StmtToEnv; |
138 | | Environment &Env; |
139 | | int BlockSuccIdx; |
140 | | }; |
141 | | |
142 | | /// Computes the input state for a given basic block by joining the output |
143 | | /// states of its predecessors. |
144 | | /// |
145 | | /// Requirements: |
146 | | /// |
147 | | /// All predecessors of `Block` except those with loop back edges must have |
148 | | /// already been transferred. States in `BlockStates` that are set to |
149 | | /// `llvm::None` represent basic blocks that are not evaluated yet. |
150 | | static TypeErasedDataflowAnalysisState computeBlockInputState( |
151 | | const ControlFlowContext &CFCtx, |
152 | | std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates, |
153 | | const CFGBlock &Block, const Environment &InitEnv, |
154 | 67.4k | TypeErasedDataflowAnalysis &Analysis) { |
155 | 67.4k | llvm::DenseSet<const CFGBlock *> Preds; |
156 | 67.4k | Preds.insert(Block.pred_begin(), Block.pred_end()); |
157 | 67.4k | if (Block.getTerminator().isTemporaryDtorsBranch()) { |
158 | | // This handles a special case where the code that produced the CFG includes |
159 | | // a conditional operator with a branch that constructs a temporary and |
160 | | // calls a destructor annotated as noreturn. The CFG models this as follows: |
161 | | // |
162 | | // B1 (contains the condition of the conditional operator) - succs: B2, B3 |
163 | | // B2 (contains code that does not call a noreturn destructor) - succs: B4 |
164 | | // B3 (contains code that calls a noreturn destructor) - succs: B4 |
165 | | // B4 (has temporary destructor terminator) - succs: B5, B6 |
166 | | // B5 (noreturn block that is associated with the noreturn destructor call) |
167 | | // B6 (contains code that follows the conditional operator statement) |
168 | | // |
169 | | // The first successor (B5 above) of a basic block with a temporary |
170 | | // destructor terminator (B4 above) is the block that evaluates the |
171 | | // destructor. If that block has a noreturn element then the predecessor |
172 | | // block that constructed the temporary object (B3 above) is effectively a |
173 | | // noreturn block and its state should not be used as input for the state |
174 | | // of the block that has a temporary destructor terminator (B4 above). This |
175 | | // holds regardless of which branch of the ternary operator calls the |
176 | | // noreturn destructor. However, it doesn't cases where a nested ternary |
177 | | // operator includes a branch that contains a noreturn destructor call. |
178 | | // |
179 | | // See `NoreturnDestructorTest` for concrete examples. |
180 | 18 | if (Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) { |
181 | 8 | auto StmtBlock = CFCtx.getStmtToBlock().find(Block.getTerminatorStmt()); |
182 | 8 | assert(StmtBlock != CFCtx.getStmtToBlock().end()); |
183 | 0 | Preds.erase(StmtBlock->getSecond()); |
184 | 8 | } |
185 | 18 | } |
186 | | |
187 | 0 | llvm::Optional<TypeErasedDataflowAnalysisState> MaybeState; |
188 | 67.4k | bool ApplyBuiltinTransfer = Analysis.applyBuiltinTransfer(); |
189 | | |
190 | 89.2k | for (const CFGBlock *Pred : Preds) { |
191 | | // Skip if the `Block` is unreachable or control flow cannot get past it. |
192 | 89.2k | if (!Pred || Pred->hasNoReturnElement()89.1k ) |
193 | 22 | continue; |
194 | | |
195 | | // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a |
196 | | // loop back edge to `Block`. |
197 | 89.1k | const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState = |
198 | 89.1k | BlockStates[Pred->getBlockID()]; |
199 | 89.1k | if (!MaybePredState.hasValue()) |
200 | 9 | continue; |
201 | | |
202 | 89.1k | TypeErasedDataflowAnalysisState PredState = MaybePredState.getValue(); |
203 | 89.1k | if (ApplyBuiltinTransfer) { |
204 | 1.77k | if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) { |
205 | 412 | const StmtToEnvMapImpl StmtToEnv(CFCtx, BlockStates); |
206 | 412 | TerminatorVisitor(StmtToEnv, PredState.Env, |
207 | 412 | blockIndexInPredecessor(*Pred, Block)) |
208 | 412 | .Visit(PredTerminatorStmt); |
209 | 412 | } |
210 | 1.77k | } |
211 | | |
212 | 89.1k | if (MaybeState.hasValue()) { |
213 | 22.0k | Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice); |
214 | 22.0k | MaybeState->Env.join(PredState.Env, Analysis); |
215 | 67.1k | } else { |
216 | 67.1k | MaybeState = std::move(PredState); |
217 | 67.1k | } |
218 | 89.1k | } |
219 | 67.4k | if (!MaybeState.hasValue()) { |
220 | | // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()` |
221 | | // to enable building analyses like computation of dominators that |
222 | | // initialize the state of each basic block differently. |
223 | 294 | MaybeState.emplace(Analysis.typeErasedInitialElement(), InitEnv); |
224 | 294 | } |
225 | 67.4k | return *MaybeState; |
226 | 67.4k | } |
227 | | |
228 | | /// Transfers `State` by evaluating `CfgStmt` in the context of `Analysis`. |
229 | | /// `HandleTransferredStmt` (if provided) will be applied to `CfgStmt`, after it |
230 | | /// is evaluated. |
231 | | static void transferCFGStmt( |
232 | | const ControlFlowContext &CFCtx, |
233 | | llvm::ArrayRef<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates, |
234 | | const CFGStmt &CfgStmt, TypeErasedDataflowAnalysis &Analysis, |
235 | | TypeErasedDataflowAnalysisState &State, |
236 | | std::function<void(const CFGStmt &, |
237 | | const TypeErasedDataflowAnalysisState &)> |
238 | 27.6k | HandleTransferredStmt) { |
239 | 27.6k | const Stmt *S = CfgStmt.getStmt(); |
240 | 27.6k | assert(S != nullptr); |
241 | | |
242 | 27.6k | if (Analysis.applyBuiltinTransfer()) |
243 | 5.77k | transfer(StmtToEnvMapImpl(CFCtx, BlockStates), *S, State.Env); |
244 | 27.6k | Analysis.transferTypeErased(S, State.Lattice, State.Env); |
245 | | |
246 | 27.6k | if (HandleTransferredStmt != nullptr) |
247 | 2.88k | HandleTransferredStmt(CfgStmt, State); |
248 | 27.6k | } |
249 | | |
250 | | /// Transfers `State` by evaluating `CfgInit`. |
251 | | static void transferCFGInitializer(const CFGInitializer &CfgInit, |
252 | 10 | TypeErasedDataflowAnalysisState &State) { |
253 | 10 | const auto &ThisLoc = *cast<AggregateStorageLocation>( |
254 | 10 | State.Env.getThisPointeeStorageLocation()); |
255 | | |
256 | 10 | const CXXCtorInitializer *Initializer = CfgInit.getInitializer(); |
257 | 10 | assert(Initializer != nullptr); |
258 | | |
259 | 0 | auto *InitStmt = Initializer->getInit(); |
260 | 10 | assert(InitStmt != nullptr); |
261 | | |
262 | 0 | auto *InitStmtLoc = |
263 | 10 | State.Env.getStorageLocation(*InitStmt, SkipPast::Reference); |
264 | 10 | if (InitStmtLoc == nullptr) |
265 | 4 | return; |
266 | | |
267 | 6 | auto *InitStmtVal = State.Env.getValue(*InitStmtLoc); |
268 | 6 | if (InitStmtVal == nullptr) |
269 | 0 | return; |
270 | | |
271 | 6 | const FieldDecl *Member = Initializer->getMember(); |
272 | 6 | assert(Member != nullptr); |
273 | | |
274 | 6 | if (Member->getType()->isReferenceType()) { |
275 | 2 | auto &MemberLoc = ThisLoc.getChild(*Member); |
276 | 2 | State.Env.setValue(MemberLoc, |
277 | 2 | State.Env.takeOwnership( |
278 | 2 | std::make_unique<ReferenceValue>(*InitStmtLoc))); |
279 | 4 | } else { |
280 | 4 | auto &MemberLoc = ThisLoc.getChild(*Member); |
281 | 4 | State.Env.setValue(MemberLoc, *InitStmtVal); |
282 | 4 | } |
283 | 6 | } |
284 | | |
285 | | TypeErasedDataflowAnalysisState transferBlock( |
286 | | const ControlFlowContext &CFCtx, |
287 | | std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates, |
288 | | const CFGBlock &Block, const Environment &InitEnv, |
289 | | TypeErasedDataflowAnalysis &Analysis, |
290 | | std::function<void(const CFGStmt &, |
291 | | const TypeErasedDataflowAnalysisState &)> |
292 | 67.4k | HandleTransferredStmt) { |
293 | 67.4k | TypeErasedDataflowAnalysisState State = |
294 | 67.4k | computeBlockInputState(CFCtx, BlockStates, Block, InitEnv, Analysis); |
295 | 67.4k | for (const CFGElement &Element : Block) { |
296 | 27.6k | switch (Element.getKind()) { |
297 | 27.6k | case CFGElement::Statement: |
298 | 27.6k | transferCFGStmt(CFCtx, BlockStates, *Element.getAs<CFGStmt>(), Analysis, |
299 | 27.6k | State, HandleTransferredStmt); |
300 | 27.6k | break; |
301 | 10 | case CFGElement::Initializer: |
302 | 10 | if (Analysis.applyBuiltinTransfer()) |
303 | 10 | transferCFGInitializer(*Element.getAs<CFGInitializer>(), State); |
304 | 10 | break; |
305 | 34 | default: |
306 | | // FIXME: Evaluate other kinds of `CFGElement`. |
307 | 34 | break; |
308 | 27.6k | } |
309 | 27.6k | } |
310 | 67.4k | return State; |
311 | 67.4k | } |
312 | | |
313 | | llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>> |
314 | | runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx, |
315 | | TypeErasedDataflowAnalysis &Analysis, |
316 | 296 | const Environment &InitEnv) { |
317 | 296 | PostOrderCFGView POV(&CFCtx.getCFG()); |
318 | 296 | ForwardDataflowWorklist Worklist(CFCtx.getCFG(), &POV); |
319 | | |
320 | 296 | std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates; |
321 | 296 | BlockStates.resize(CFCtx.getCFG().size(), llvm::None); |
322 | | |
323 | | // The entry basic block doesn't contain statements so it can be skipped. |
324 | 296 | const CFGBlock &Entry = CFCtx.getCFG().getEntry(); |
325 | 296 | BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(), |
326 | 296 | InitEnv}; |
327 | 296 | Worklist.enqueueSuccessors(&Entry); |
328 | | |
329 | | // Bugs in lattices and transfer functions can prevent the analysis from |
330 | | // converging. To limit the damage (infinite loops) that these bugs can cause, |
331 | | // limit the number of iterations. |
332 | | // FIXME: Consider making the maximum number of iterations configurable. |
333 | | // FIXME: Set up statistics (see llvm/ADT/Statistic.h) to count average number |
334 | | // of iterations, number of functions that time out, etc. |
335 | 296 | uint32_t Iterations = 0; |
336 | 296 | static constexpr uint32_t MaxIterations = 1 << 16; |
337 | 66.6k | while (const CFGBlock *Block = Worklist.dequeue()) { |
338 | 66.3k | if (++Iterations > MaxIterations) { |
339 | 1 | return llvm::createStringError(std::errc::timed_out, |
340 | 1 | "maximum number of iterations reached"); |
341 | 1 | } |
342 | | |
343 | 66.3k | const llvm::Optional<TypeErasedDataflowAnalysisState> &OldBlockState = |
344 | 66.3k | BlockStates[Block->getBlockID()]; |
345 | 66.3k | TypeErasedDataflowAnalysisState NewBlockState = |
346 | 66.3k | transferBlock(CFCtx, BlockStates, *Block, InitEnv, Analysis); |
347 | | |
348 | 66.3k | if (OldBlockState.hasValue() && |
349 | 66.3k | Analysis.isEqualTypeErased(OldBlockState.getValue().Lattice, |
350 | 65.5k | NewBlockState.Lattice) && |
351 | 66.3k | OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis)6 ) { |
352 | | // The state of `Block` didn't change after transfer so there's no need to |
353 | | // revisit its successors. |
354 | 6 | continue; |
355 | 6 | } |
356 | | |
357 | 66.3k | BlockStates[Block->getBlockID()] = std::move(NewBlockState); |
358 | | |
359 | | // Do not add unreachable successor blocks to `Worklist`. |
360 | 66.3k | if (Block->hasNoReturnElement()) |
361 | 7 | continue; |
362 | | |
363 | 66.3k | Worklist.enqueueSuccessors(Block); |
364 | 66.3k | } |
365 | | // FIXME: Consider evaluating unreachable basic blocks (those that have a |
366 | | // state set to `llvm::None` at this point) to also analyze dead code. |
367 | | |
368 | 295 | return BlockStates; |
369 | 296 | } |
370 | | |
371 | | } // namespace dataflow |
372 | | } // namespace clang |