1 //===- AdornedCFG.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 an `AdornedCFG` class that is used by dataflow analyses 10 // that run over Control-Flow Graphs (CFGs). 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/Analysis/FlowSensitive/AdornedCFG.h" 15 #include "clang/AST/ASTContext.h" 16 #include "clang/AST/Decl.h" 17 #include "clang/AST/Stmt.h" 18 #include "clang/Analysis/CFG.h" 19 #include "clang/Analysis/FlowSensitive/ASTOps.h" 20 #include "llvm/ADT/BitVector.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/Support/Error.h" 23 #include <utility> 24 25 namespace clang { 26 namespace dataflow { 27 28 /// Returns a map from statements to basic blocks that contain them. 29 static llvm::DenseMap<const Stmt *, const CFGBlock *> 30 buildStmtToBasicBlockMap(const CFG &Cfg) { 31 llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock; 32 for (const CFGBlock *Block : Cfg) { 33 if (Block == nullptr) 34 continue; 35 36 for (const CFGElement &Element : *Block) { 37 auto Stmt = Element.getAs<CFGStmt>(); 38 if (!Stmt) 39 continue; 40 41 StmtToBlock[Stmt->getStmt()] = Block; 42 } 43 } 44 // Some terminator conditions don't appear as a `CFGElement` anywhere else - 45 // for example, this is true if the terminator condition is a `&&` or `||` 46 // operator. 47 // We associate these conditions with the block the terminator appears in, 48 // but only if the condition has not already appeared as a regular 49 // `CFGElement`. (The `insert()` below does nothing if the key already exists 50 // in the map.) 51 for (const CFGBlock *Block : Cfg) { 52 if (Block != nullptr) 53 if (const Stmt *TerminatorCond = Block->getTerminatorCondition()) 54 StmtToBlock.insert({TerminatorCond, Block}); 55 } 56 // Terminator statements typically don't appear as a `CFGElement` anywhere 57 // else, so we want to associate them with the block that they terminate. 58 // However, there are some important special cases: 59 // - The conditional operator is a type of terminator, but it also appears 60 // as a regular `CFGElement`, and we want to associate it with the block 61 // in which it appears as a `CFGElement`. 62 // - The `&&` and `||` operators are types of terminators, but like the 63 // conditional operator, they can appear as a regular `CFGElement` or 64 // as a terminator condition (see above). 65 // We process terminators last to make sure that we only associate them with 66 // the block they terminate if they haven't previously occurred as a regular 67 // `CFGElement` or as a terminator condition. 68 for (const CFGBlock *Block : Cfg) { 69 if (Block != nullptr) 70 if (const Stmt *TerminatorStmt = Block->getTerminatorStmt()) 71 StmtToBlock.insert({TerminatorStmt, Block}); 72 } 73 return StmtToBlock; 74 } 75 76 static llvm::BitVector findReachableBlocks(const CFG &Cfg) { 77 llvm::BitVector BlockReachable(Cfg.getNumBlockIDs(), false); 78 79 llvm::SmallVector<const CFGBlock *> BlocksToVisit; 80 BlocksToVisit.push_back(&Cfg.getEntry()); 81 while (!BlocksToVisit.empty()) { 82 const CFGBlock *Block = BlocksToVisit.back(); 83 BlocksToVisit.pop_back(); 84 85 if (BlockReachable[Block->getBlockID()]) 86 continue; 87 88 BlockReachable[Block->getBlockID()] = true; 89 90 for (const CFGBlock *Succ : Block->succs()) 91 if (Succ) 92 BlocksToVisit.push_back(Succ); 93 } 94 95 return BlockReachable; 96 } 97 98 static llvm::DenseSet<const CFGBlock *> 99 buildContainsExprConsumedInDifferentBlock( 100 const CFG &Cfg, const internal::StmtToBlockMap &StmtToBlock) { 101 llvm::DenseSet<const CFGBlock *> Result; 102 103 auto CheckChildExprs = [&Result, &StmtToBlock](const Stmt *S, 104 const CFGBlock *Block) { 105 for (const Stmt *Child : S->children()) { 106 if (!isa_and_nonnull<Expr>(Child)) 107 continue; 108 const CFGBlock *ChildBlock = StmtToBlock.lookup(*Child); 109 if (ChildBlock != Block) 110 Result.insert(ChildBlock); 111 } 112 }; 113 114 for (const CFGBlock *Block : Cfg) { 115 if (Block == nullptr) 116 continue; 117 118 for (const CFGElement &Element : *Block) 119 if (auto S = Element.getAs<CFGStmt>()) 120 CheckChildExprs(S->getStmt(), Block); 121 122 if (const Stmt *TerminatorCond = Block->getTerminatorCondition()) 123 CheckChildExprs(TerminatorCond, Block); 124 } 125 126 return Result; 127 } 128 129 namespace internal { 130 131 StmtToBlockMap::StmtToBlockMap(const CFG &Cfg) 132 : StmtToBlock(buildStmtToBasicBlockMap(Cfg)) {} 133 134 } // namespace internal 135 136 llvm::Expected<AdornedCFG> AdornedCFG::build(const FunctionDecl &Func) { 137 if (!Func.doesThisDeclarationHaveABody()) 138 return llvm::createStringError( 139 std::make_error_code(std::errc::invalid_argument), 140 "Cannot analyze function without a body"); 141 142 return build(Func, *Func.getBody(), Func.getASTContext()); 143 } 144 145 llvm::Expected<AdornedCFG> AdornedCFG::build(const Decl &D, Stmt &S, 146 ASTContext &C) { 147 if (D.isTemplated()) 148 return llvm::createStringError( 149 std::make_error_code(std::errc::invalid_argument), 150 "Cannot analyze templated declarations"); 151 152 // The shape of certain elements of the AST can vary depending on the 153 // language. We currently only support C++. 154 if (!C.getLangOpts().CPlusPlus || C.getLangOpts().ObjC) 155 return llvm::createStringError( 156 std::make_error_code(std::errc::invalid_argument), 157 "Can only analyze C++"); 158 159 CFG::BuildOptions Options; 160 Options.PruneTriviallyFalseEdges = true; 161 Options.AddImplicitDtors = true; 162 Options.AddTemporaryDtors = true; 163 Options.AddInitializers = true; 164 Options.AddCXXDefaultInitExprInCtors = true; 165 Options.AddLifetime = true; 166 167 // Ensure that all sub-expressions in basic blocks are evaluated. 168 Options.setAllAlwaysAdd(); 169 170 auto Cfg = CFG::buildCFG(&D, &S, &C, Options); 171 if (Cfg == nullptr) 172 return llvm::createStringError( 173 std::make_error_code(std::errc::invalid_argument), 174 "CFG::buildCFG failed"); 175 176 internal::StmtToBlockMap StmtToBlock(*Cfg); 177 178 llvm::BitVector BlockReachable = findReachableBlocks(*Cfg); 179 180 llvm::DenseSet<const CFGBlock *> ContainsExprConsumedInDifferentBlock = 181 buildContainsExprConsumedInDifferentBlock(*Cfg, StmtToBlock); 182 183 return AdornedCFG(D, std::move(Cfg), std::move(StmtToBlock), 184 std::move(BlockReachable), 185 std::move(ContainsExprConsumedInDifferentBlock)); 186 } 187 188 } // namespace dataflow 189 } // namespace clang 190