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