Coverage Report

Created: 2022-01-18 06:27

/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 <utility>
16
#include <vector>
17
18
#include "clang/AST/DeclCXX.h"
19
#include "clang/Analysis/Analyses/PostOrderCFGView.h"
20
#include "clang/Analysis/CFG.h"
21
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
22
#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
23
#include "clang/Analysis/FlowSensitive/Transfer.h"
24
#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
25
#include "clang/Analysis/FlowSensitive/Value.h"
26
#include "llvm/ADT/None.h"
27
#include "llvm/ADT/Optional.h"
28
#include "llvm/Support/raw_ostream.h"
29
30
namespace clang {
31
namespace dataflow {
32
33
/// Computes the input state for a given basic block by joining the output
34
/// states of its predecessors.
35
///
36
/// Requirements:
37
///
38
///   All predecessors of `Block` except those with loop back edges must have
39
///   already been transferred. States in `BlockStates` that are set to
40
///   `llvm::None` represent basic blocks that are not evaluated yet.
41
static TypeErasedDataflowAnalysisState computeBlockInputState(
42
    const ControlFlowContext &CFCtx,
43
    std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
44
    const CFGBlock &Block, const Environment &InitEnv,
45
65.9k
    TypeErasedDataflowAnalysis &Analysis) {
46
65.9k
  llvm::DenseSet<const CFGBlock *> Preds;
47
65.9k
  Preds.insert(Block.pred_begin(), Block.pred_end());
48
65.9k
  if (Block.getTerminator().isTemporaryDtorsBranch()) {
49
    // This handles a special case where the code that produced the CFG includes
50
    // a conditional operator with a branch that constructs a temporary and
51
    // calls a destructor annotated as noreturn. The CFG models this as follows:
52
    //
53
    // B1 (contains the condition of the conditional operator) - succs: B2, B3
54
    // B2 (contains code that does not call a noreturn destructor) - succs: B4
55
    // B3 (contains code that calls a noreturn destructor) - succs: B4
56
    // B4 (has temporary destructor terminator) - succs: B5, B6
57
    // B5 (noreturn block that is associated with the noreturn destructor call)
58
    // B6 (contains code that follows the conditional operator statement)
59
    //
60
    // The first successor (B5 above) of a basic block with a temporary
61
    // destructor terminator (B4 above) is the block that evaluates the
62
    // destructor. If that block has a noreturn element then the predecessor
63
    // block that constructed the temporary object (B3 above) is effectively a
64
    // noreturn block and its state should not be used as input for the state
65
    // of the block that has a temporary destructor terminator (B4 above). This
66
    // holds regardless of which branch of the ternary operator calls the
67
    // noreturn destructor. However, it doesn't cases where a nested ternary
68
    // operator includes a branch that contains a noreturn destructor call.
69
    //
70
    // See `NoreturnDestructorTest` for concrete examples.
71
10
    if (Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
72
8
      auto StmtBlock = CFCtx.getStmtToBlock().find(Block.getTerminatorStmt());
73
8
      assert(StmtBlock != CFCtx.getStmtToBlock().end());
74
0
      Preds.erase(StmtBlock->getSecond());
75
8
    }
76
10
  }
77
78
0
  llvm::Optional<TypeErasedDataflowAnalysisState> MaybeState;
79
87.8k
  for (const CFGBlock *Pred : Preds) {
80
    // Skip if the `Block` is unreachable or control flow cannot get past it.
81
87.8k
    if (!Pred || 
Pred->hasNoReturnElement()87.8k
)
82
14
      continue;
83
84
    // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
85
    // loop back edge to `Block`.
86
87.8k
    const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState =
87
87.8k
        BlockStates[Pred->getBlockID()];
88
87.8k
    if (!MaybePredState.hasValue())
89
3
      continue;
90
91
87.8k
    const TypeErasedDataflowAnalysisState &PredState =
92
87.8k
        MaybePredState.getValue();
93
87.8k
    if (MaybeState.hasValue()) {
94
21.8k
      Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice);
95
21.8k
      MaybeState->Env.join(PredState.Env);
96
65.9k
    } else {
97
65.9k
      MaybeState = PredState;
98
65.9k
    }
99
87.8k
  }
100
65.9k
  if (!MaybeState.hasValue()) {
101
    // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
102
    // to enable building analyses like computation of dominators that
103
    // initialize the state of each basic block differently.
104
66
    MaybeState.emplace(Analysis.typeErasedInitialElement(), InitEnv);
105
66
  }
106
65.9k
  return *MaybeState;
107
65.9k
}
108
109
/// Transfers `State` by evaluating `CfgStmt` in the context of `Analysis`.
110
/// `HandleTransferredStmt` (if provided) will be applied to `CfgStmt`, after it
111
/// is evaluated.
112
static void
113
transferCFGStmt(const CFGStmt &CfgStmt, TypeErasedDataflowAnalysis &Analysis,
114
                TypeErasedDataflowAnalysisState &State,
115
                std::function<void(const CFGStmt &,
116
                                   const TypeErasedDataflowAnalysisState &)>
117
22.7k
                    HandleTransferredStmt) {
118
22.7k
  const Stmt *S = CfgStmt.getStmt();
119
22.7k
  assert(S != nullptr);
120
121
0
  transfer(*S, State.Env);
122
22.7k
  Analysis.transferTypeErased(S, State.Lattice, State.Env);
123
124
22.7k
  if (HandleTransferredStmt != nullptr)
125
454
    HandleTransferredStmt(CfgStmt, State);
126
22.7k
}
127
128
/// Transfers `State` by evaluating `CfgInit`.
129
static void transferCFGInitializer(const CFGInitializer &CfgInit,
130
10
                                   TypeErasedDataflowAnalysisState &State) {
131
10
  const auto &ThisLoc = *cast<AggregateStorageLocation>(
132
10
      State.Env.getThisPointeeStorageLocation());
133
134
10
  const CXXCtorInitializer *Initializer = CfgInit.getInitializer();
135
10
  assert(Initializer != nullptr);
136
137
0
  auto *InitStmt = Initializer->getInit();
138
10
  assert(InitStmt != nullptr);
139
140
0
  auto *InitStmtLoc =
141
10
      State.Env.getStorageLocation(*InitStmt, SkipPast::Reference);
142
10
  if (InitStmtLoc == nullptr)
143
4
    return;
144
145
6
  auto *InitStmtVal = State.Env.getValue(*InitStmtLoc);
146
6
  if (InitStmtVal == nullptr)
147
0
    return;
148
149
6
  const FieldDecl *Member = Initializer->getMember();
150
6
  assert(Member != nullptr);
151
152
6
  if (Member->getType()->isReferenceType()) {
153
2
    auto &MemberLoc = ThisLoc.getChild(*Member);
154
2
    State.Env.setValue(MemberLoc,
155
2
                       State.Env.takeOwnership(
156
2
                           std::make_unique<ReferenceValue>(*InitStmtLoc)));
157
4
  } else {
158
4
    auto &MemberLoc = ThisLoc.getChild(*Member);
159
4
    State.Env.setValue(MemberLoc, *InitStmtVal);
160
4
  }
161
6
}
162
163
TypeErasedDataflowAnalysisState transferBlock(
164
    const ControlFlowContext &CFCtx,
165
    std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
166
    const CFGBlock &Block, const Environment &InitEnv,
167
    TypeErasedDataflowAnalysis &Analysis,
168
    std::function<void(const CFGStmt &,
169
                       const TypeErasedDataflowAnalysisState &)>
170
65.9k
        HandleTransferredStmt) {
171
65.9k
  TypeErasedDataflowAnalysisState State =
172
65.9k
      computeBlockInputState(CFCtx, BlockStates, Block, InitEnv, Analysis);
173
65.9k
  for (const CFGElement &Element : Block) {
174
22.7k
    switch (Element.getKind()) {
175
22.7k
    case CFGElement::Statement:
176
22.7k
      transferCFGStmt(*Element.getAs<CFGStmt>(), Analysis, State,
177
22.7k
                      HandleTransferredStmt);
178
22.7k
      break;
179
10
    case CFGElement::Initializer:
180
10
      transferCFGInitializer(*Element.getAs<CFGInitializer>(), State);
181
10
      break;
182
14
    default:
183
      // FIXME: Evaluate other kinds of `CFGElement`.
184
14
      break;
185
22.7k
    }
186
22.7k
  }
187
65.9k
  return State;
188
65.9k
}
189
190
std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
191
runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx,
192
                              TypeErasedDataflowAnalysis &Analysis,
193
68
                              const Environment &InitEnv) {
194
  // FIXME: Consider enforcing that `Cfg` meets the requirements that
195
  // are specified in the header. This could be done by remembering
196
  // what options were used to build `Cfg` and asserting on them here.
197
198
68
  PostOrderCFGView POV(&CFCtx.getCFG());
199
68
  ForwardDataflowWorklist Worklist(CFCtx.getCFG(), &POV);
200
201
68
  std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates;
202
68
  BlockStates.resize(CFCtx.getCFG().size(), llvm::None);
203
204
  // The entry basic block doesn't contain statements so it can be skipped.
205
68
  const CFGBlock &Entry = CFCtx.getCFG().getEntry();
206
68
  BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
207
68
                                     InitEnv};
208
68
  Worklist.enqueueSuccessors(&Entry);
209
210
  // Bugs in lattices and transfer functions can prevent the analysis from
211
  // converging. To limit the damage (infinite loops) that these bugs can cause,
212
  // limit the number of iterations.
213
  // FIXME: Consider making the maximum number of iterations configurable.
214
  // FIXME: Set up statistics (see llvm/ADT/Statistic.h) to count average number
215
  // of iterations, number of functions that time out, etc.
216
68
  unsigned Iterations = 0;
217
68
  static constexpr unsigned MaxIterations = 1 << 16;
218
65.7k
  while (const CFGBlock *Block = Worklist.dequeue()) {
219
65.7k
    if (++Iterations > MaxIterations) {
220
1
      llvm::errs() << "Maximum number of iterations reached, giving up.\n";
221
1
      break;
222
1
    }
223
224
65.7k
    const llvm::Optional<TypeErasedDataflowAnalysisState> &OldBlockState =
225
65.7k
        BlockStates[Block->getBlockID()];
226
65.7k
    TypeErasedDataflowAnalysisState NewBlockState =
227
65.7k
        transferBlock(CFCtx, BlockStates, *Block, InitEnv, Analysis);
228
229
65.7k
    if (OldBlockState.hasValue() &&
230
65.7k
        Analysis.isEqualTypeErased(OldBlockState.getValue().Lattice,
231
65.5k
                                   NewBlockState.Lattice) &&
232
65.7k
        
OldBlockState->Env == NewBlockState.Env0
) {
233
      // The state of `Block` didn't change after transfer so there's no need to
234
      // revisit its successors.
235
0
      continue;
236
0
    }
237
238
65.7k
    BlockStates[Block->getBlockID()] = std::move(NewBlockState);
239
240
    // Do not add unreachable successor blocks to `Worklist`.
241
65.7k
    if (Block->hasNoReturnElement())
242
5
      continue;
243
244
65.7k
    Worklist.enqueueSuccessors(Block);
245
65.7k
  }
246
  // FIXME: Consider evaluating unreachable basic blocks (those that have a
247
  // state set to `llvm::None` at this point) to also analyze dead code.
248
249
68
  return BlockStates;
250
68
}
251
252
} // namespace dataflow
253
} // namespace clang