Coverage Report

Created: 2022-05-17 06:19

/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