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