1 //===-- AdornedCFG.h ------------------------------------*- C++ -*-===// 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 an AdornedCFG class that is used by dataflow analyses that 10 // run over Control-Flow Graphs (CFGs). 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_ADORNEDCFG_H 15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_ADORNEDCFG_H 16 17 #include "clang/AST/ASTContext.h" 18 #include "clang/AST/Decl.h" 19 #include "clang/AST/Stmt.h" 20 #include "clang/Analysis/CFG.h" 21 #include "clang/Analysis/FlowSensitive/ASTOps.h" 22 #include "llvm/ADT/BitVector.h" 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/Support/Error.h" 25 #include <memory> 26 #include <utility> 27 28 namespace clang { 29 namespace dataflow { 30 31 namespace internal { 32 class StmtToBlockMap { 33 public: 34 StmtToBlockMap(const CFG &Cfg); 35 lookup(const Stmt & S)36 const CFGBlock *lookup(const Stmt &S) const { 37 return StmtToBlock.lookup(&ignoreCFGOmittedNodes(S)); 38 } 39 40 private: 41 llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock; 42 }; 43 } // namespace internal 44 45 /// Holds CFG with additional information derived from it that is needed to 46 /// perform dataflow analysis. 47 class AdornedCFG { 48 public: 49 /// Builds an `AdornedCFG` from a `FunctionDecl`. 50 /// `Func.doesThisDeclarationHaveABody()` must be true, and 51 /// `Func.isTemplated()` must be false. 52 static llvm::Expected<AdornedCFG> build(const FunctionDecl &Func); 53 54 /// Builds an `AdornedCFG` from an AST node. `D` is the function in which 55 /// `S` resides. `D.isTemplated()` must be false. 56 static llvm::Expected<AdornedCFG> build(const Decl &D, Stmt &S, 57 ASTContext &C); 58 59 /// Returns the `Decl` containing the statement used to construct the CFG, if 60 /// available. getDecl()61 const Decl &getDecl() const { return ContainingDecl; } 62 63 /// Returns the CFG that is stored in this context. getCFG()64 const CFG &getCFG() const { return *Cfg; } 65 66 /// Returns the basic block that contains `S`, or null if no basic block 67 /// containing `S` is found. blockForStmt(const Stmt & S)68 const CFGBlock *blockForStmt(const Stmt &S) const { 69 return StmtToBlock.lookup(S); 70 } 71 72 /// Returns whether `B` is reachable from the entry block. isBlockReachable(const CFGBlock & B)73 bool isBlockReachable(const CFGBlock &B) const { 74 return BlockReachable[B.getBlockID()]; 75 } 76 77 /// Returns whether `B` contains an expression that is consumed in a 78 /// different block than `B` (i.e. the parent of the expression is in a 79 /// different block). 80 /// This happens if there is control flow within a full-expression (triggered 81 /// by `&&`, `||`, or the conditional operator). Note that the operands of 82 /// these operators are not the only expressions that can be consumed in a 83 /// different block. For example, in the function call 84 /// `f(&i, cond() ? 1 : 0)`, `&i` is in a different block than the `CallExpr`. containsExprConsumedInDifferentBlock(const CFGBlock & B)85 bool containsExprConsumedInDifferentBlock(const CFGBlock &B) const { 86 return ContainsExprConsumedInDifferentBlock.contains(&B); 87 } 88 89 private: AdornedCFG(const Decl & D,std::unique_ptr<CFG> Cfg,internal::StmtToBlockMap StmtToBlock,llvm::BitVector BlockReachable,llvm::DenseSet<const CFGBlock * > ContainsExprConsumedInDifferentBlock)90 AdornedCFG( 91 const Decl &D, std::unique_ptr<CFG> Cfg, 92 internal::StmtToBlockMap StmtToBlock, llvm::BitVector BlockReachable, 93 llvm::DenseSet<const CFGBlock *> ContainsExprConsumedInDifferentBlock) 94 : ContainingDecl(D), Cfg(std::move(Cfg)), 95 StmtToBlock(std::move(StmtToBlock)), 96 BlockReachable(std::move(BlockReachable)), 97 ContainsExprConsumedInDifferentBlock( 98 std::move(ContainsExprConsumedInDifferentBlock)) {} 99 100 /// The `Decl` containing the statement used to construct the CFG. 101 const Decl &ContainingDecl; 102 std::unique_ptr<CFG> Cfg; 103 internal::StmtToBlockMap StmtToBlock; 104 llvm::BitVector BlockReachable; 105 llvm::DenseSet<const CFGBlock *> ContainsExprConsumedInDifferentBlock; 106 }; 107 108 } // namespace dataflow 109 } // namespace clang 110 111 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_ADORNEDCFG_H 112