clang 19.0.0git
AdornedCFG.cpp
Go to the documentation of this file.
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
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
24namespace clang {
25namespace dataflow {
26
27/// Returns a map from statements to basic blocks that contain them.
28static llvm::DenseMap<const Stmt *, const CFGBlock *>
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 }
43 // Some terminator conditions don't appear as a `CFGElement` anywhere else -
44 // for example, this is true if the terminator condition is a `&&` or `||`
45 // operator.
46 // We associate these conditions with the block the terminator appears in,
47 // but only if the condition has not already appeared as a regular
48 // `CFGElement`. (The `insert()` below does nothing if the key already exists
49 // in the map.)
50 for (const CFGBlock *Block : Cfg) {
51 if (Block != nullptr)
52 if (const Stmt *TerminatorCond = Block->getTerminatorCondition())
53 StmtToBlock.insert({TerminatorCond, Block});
54 }
55 // Terminator statements typically don't appear as a `CFGElement` anywhere
56 // else, so we want to associate them with the block that they terminate.
57 // However, there are some important special cases:
58 // - The conditional operator is a type of terminator, but it also appears
59 // as a regular `CFGElement`, and we want to associate it with the block
60 // in which it appears as a `CFGElement`.
61 // - The `&&` and `||` operators are types of terminators, but like the
62 // conditional operator, they can appear as a regular `CFGElement` or
63 // as a terminator condition (see above).
64 // We process terminators last to make sure that we only associate them with
65 // the block they terminate if they haven't previously occurred as a regular
66 // `CFGElement` or as a terminator condition.
67 for (const CFGBlock *Block : Cfg) {
68 if (Block != nullptr)
69 if (const Stmt *TerminatorStmt = Block->getTerminatorStmt())
70 StmtToBlock.insert({TerminatorStmt, Block});
71 }
72 return StmtToBlock;
73}
74
75static llvm::BitVector findReachableBlocks(const CFG &Cfg) {
76 llvm::BitVector BlockReachable(Cfg.getNumBlockIDs(), false);
77
79 BlocksToVisit.push_back(&Cfg.getEntry());
80 while (!BlocksToVisit.empty()) {
81 const CFGBlock *Block = BlocksToVisit.back();
82 BlocksToVisit.pop_back();
83
84 if (BlockReachable[Block->getBlockID()])
85 continue;
86
87 BlockReachable[Block->getBlockID()] = true;
88
89 for (const CFGBlock *Succ : Block->succs())
90 if (Succ)
91 BlocksToVisit.push_back(Succ);
92 }
93
94 return BlockReachable;
95}
96
99 const CFG &Cfg,
100 const llvm::DenseMap<const Stmt *, const CFGBlock *> &StmtToBlock) {
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
129llvm::Expected<AdornedCFG> AdornedCFG::build(const FunctionDecl &Func) {
130 if (!Func.doesThisDeclarationHaveABody())
131 return llvm::createStringError(
132 std::make_error_code(std::errc::invalid_argument),
133 "Cannot analyze function without a body");
134
135 return build(Func, *Func.getBody(), Func.getASTContext());
136}
137
138llvm::Expected<AdornedCFG> AdornedCFG::build(const Decl &D, Stmt &S,
139 ASTContext &C) {
140 if (D.isTemplated())
141 return llvm::createStringError(
142 std::make_error_code(std::errc::invalid_argument),
143 "Cannot analyze templated declarations");
144
145 // The shape of certain elements of the AST can vary depending on the
146 // language. We currently only support C++.
147 if (!C.getLangOpts().CPlusPlus || C.getLangOpts().ObjC)
148 return llvm::createStringError(
149 std::make_error_code(std::errc::invalid_argument),
150 "Can only analyze C++");
151
152 CFG::BuildOptions Options;
153 Options.PruneTriviallyFalseEdges = true;
154 Options.AddImplicitDtors = true;
155 Options.AddTemporaryDtors = true;
156 Options.AddInitializers = true;
157 Options.AddCXXDefaultInitExprInCtors = true;
158 Options.AddLifetime = true;
159
160 // Ensure that all sub-expressions in basic blocks are evaluated.
161 Options.setAllAlwaysAdd();
162
163 auto Cfg = CFG::buildCFG(&D, &S, &C, Options);
164 if (Cfg == nullptr)
165 return llvm::createStringError(
166 std::make_error_code(std::errc::invalid_argument),
167 "CFG::buildCFG failed");
168
169 llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock =
171
172 llvm::BitVector BlockReachable = findReachableBlocks(*Cfg);
173
174 llvm::DenseSet<const CFGBlock *> ContainsExprConsumedInDifferentBlock =
176
177 return AdornedCFG(D, std::move(Cfg), std::move(StmtToBlock),
178 std::move(BlockReachable),
179 std::move(ContainsExprConsumedInDifferentBlock));
180}
181
182} // namespace dataflow
183} // namespace clang
Defines the clang::ASTContext interface.
const CFGBlock * Block
Definition: HTMLLogger.cpp:153
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:185
Represents a single basic block in a source-level CFG.
Definition: CFG.h:604
Represents a top-level expression in a basic block.
Definition: CFG.h:55
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1214
CFGBlock & getEntry()
Definition: CFG.h:1322
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1402
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
bool isTemplated() const
Determine whether this declaration is a templated entity (whether it is.
Definition: DeclBase.cpp:284
Represents a function declaration or definition.
Definition: Decl.h:1971
Stmt - This represents one statement.
Definition: Stmt.h:84
Holds CFG with additional information derived from it that is needed to perform dataflow analysis.
Definition: AdornedCFG.h:32
static llvm::DenseSet< const CFGBlock * > buildContainsExprConsumedInDifferentBlock(const CFG &Cfg, const llvm::DenseMap< const Stmt *, const CFGBlock * > &StmtToBlock)
Definition: AdornedCFG.cpp:98
static llvm::DenseMap< const Stmt *, const CFGBlock * > buildStmtToBasicBlockMap(const CFG &Cfg)
Returns a map from statements to basic blocks that contain them.
Definition: AdornedCFG.cpp:29
static llvm::BitVector findReachableBlocks(const CFG &Cfg)
Definition: AdornedCFG.cpp:75
The JSON file list parser is used to communicate input to InstallAPI.