1 //===- ControlFlowContext.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 a ControlFlowContext class that is used by dataflow 10 // analyses that run over Control-Flow Graphs (CFGs). 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/Analysis/FlowSensitive/ControlFlowContext.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 "llvm/ADT/BitVector.h" 20 #include "llvm/ADT/DenseMap.h" 21 #include "llvm/Support/Error.h" 22 #include <utility> 23 24 namespace clang { 25 namespace dataflow { 26 27 /// Returns a map from statements to basic blocks that contain them. 28 static llvm::DenseMap<const Stmt *, const CFGBlock *> 29 buildStmtToBasicBlockMap(const CFG &Cfg) { 30 llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock; 31 for (const CFGBlock *Block : Cfg) { 32 if (Block == nullptr) 33 continue; 34 35 for (const CFGElement &Element : *Block) { 36 auto Stmt = Element.getAs<CFGStmt>(); 37 if (!Stmt) 38 continue; 39 40 StmtToBlock[Stmt->getStmt()] = Block; 41 } 42 if (const Stmt *TerminatorStmt = Block->getTerminatorStmt()) 43 StmtToBlock[TerminatorStmt] = Block; 44 } 45 return StmtToBlock; 46 } 47 48 static llvm::BitVector findReachableBlocks(const CFG &Cfg) { 49 llvm::BitVector BlockReachable(Cfg.getNumBlockIDs(), false); 50 51 llvm::SmallVector<const CFGBlock *> BlocksToVisit; 52 BlocksToVisit.push_back(&Cfg.getEntry()); 53 while (!BlocksToVisit.empty()) { 54 const CFGBlock *Block = BlocksToVisit.back(); 55 BlocksToVisit.pop_back(); 56 57 if (BlockReachable[Block->getBlockID()]) 58 continue; 59 60 BlockReachable[Block->getBlockID()] = true; 61 62 for (const CFGBlock *Succ : Block->succs()) 63 if (Succ) 64 BlocksToVisit.push_back(Succ); 65 } 66 67 return BlockReachable; 68 } 69 70 llvm::Expected<ControlFlowContext> 71 ControlFlowContext::build(const FunctionDecl &Func) { 72 if (!Func.hasBody()) 73 return llvm::createStringError( 74 std::make_error_code(std::errc::invalid_argument), 75 "Cannot analyze function without a body"); 76 77 return build(Func, *Func.getBody(), Func.getASTContext()); 78 } 79 80 llvm::Expected<ControlFlowContext> 81 ControlFlowContext::build(const Decl &D, Stmt &S, ASTContext &C) { 82 if (D.isTemplated()) 83 return llvm::createStringError( 84 std::make_error_code(std::errc::invalid_argument), 85 "Cannot analyze templated declarations"); 86 87 CFG::BuildOptions Options; 88 Options.PruneTriviallyFalseEdges = true; 89 Options.AddImplicitDtors = true; 90 Options.AddTemporaryDtors = true; 91 Options.AddInitializers = true; 92 Options.AddCXXDefaultInitExprInCtors = true; 93 94 // Ensure that all sub-expressions in basic blocks are evaluated. 95 Options.setAllAlwaysAdd(); 96 97 auto Cfg = CFG::buildCFG(&D, &S, &C, Options); 98 if (Cfg == nullptr) 99 return llvm::createStringError( 100 std::make_error_code(std::errc::invalid_argument), 101 "CFG::buildCFG failed"); 102 103 llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock = 104 buildStmtToBasicBlockMap(*Cfg); 105 106 llvm::BitVector BlockReachable = findReachableBlocks(*Cfg); 107 108 return ControlFlowContext(&D, std::move(Cfg), std::move(StmtToBlock), 109 std::move(BlockReachable)); 110 } 111 112 llvm::Expected<ControlFlowContext> 113 ControlFlowContext::build(const Decl *D, Stmt &S, ASTContext &C) { 114 if (D == nullptr) 115 return llvm::createStringError( 116 std::make_error_code(std::errc::invalid_argument), 117 "Declaration must not be null"); 118 119 return build(*D, S, C); 120 } 121 122 } // namespace dataflow 123 } // namespace clang 124