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