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 *>
buildStmtToBasicBlockMap(const CFG & Cfg)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
findReachableBlocks(const CFG & Cfg)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>
build(const FunctionDecl & Func)71 ControlFlowContext::build(const FunctionDecl &Func) {
72 if (!Func.doesThisDeclarationHaveABody())
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>
build(const Decl & D,Stmt & S,ASTContext & C)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 // The shape of certain elements of the AST can vary depending on the
88 // language. We currently only support C++.
89 if (!C.getLangOpts().CPlusPlus)
90 return llvm::createStringError(
91 std::make_error_code(std::errc::invalid_argument),
92 "Can only analyze C++");
93
94 CFG::BuildOptions Options;
95 Options.PruneTriviallyFalseEdges = true;
96 Options.AddImplicitDtors = true;
97 Options.AddTemporaryDtors = true;
98 Options.AddInitializers = true;
99 Options.AddCXXDefaultInitExprInCtors = true;
100 Options.AddLifetime = true;
101
102 // Ensure that all sub-expressions in basic blocks are evaluated.
103 Options.setAllAlwaysAdd();
104
105 auto Cfg = CFG::buildCFG(&D, &S, &C, Options);
106 if (Cfg == nullptr)
107 return llvm::createStringError(
108 std::make_error_code(std::errc::invalid_argument),
109 "CFG::buildCFG failed");
110
111 llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock =
112 buildStmtToBasicBlockMap(*Cfg);
113
114 llvm::BitVector BlockReachable = findReachableBlocks(*Cfg);
115
116 return ControlFlowContext(D, std::move(Cfg), std::move(StmtToBlock),
117 std::move(BlockReachable));
118 }
119
120 } // namespace dataflow
121 } // namespace clang
122