1 //===-- ASTOps.cc -------------------------------*- C++ -*-===//
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 // Operations on AST nodes that are used in flow-sensitive analysis.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "clang/Analysis/FlowSensitive/ASTOps.h"
14 #include "clang/AST/ComputeDependence.h"
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclBase.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/ExprCXX.h"
20 #include "clang/AST/Stmt.h"
21 #include "clang/AST/Type.h"
22 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
23 #include "clang/Basic/LLVM.h"
24 #include "llvm/ADT/DenseSet.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include <cassert>
27 #include <iterator>
28 #include <vector>
29
30 #define DEBUG_TYPE "dataflow"
31
32 namespace clang::dataflow {
33
ignoreCFGOmittedNodes(const Expr & E)34 const Expr &ignoreCFGOmittedNodes(const Expr &E) {
35 const Expr *Current = &E;
36 const Expr *Last = nullptr;
37 while (Current != Last) {
38 Last = Current;
39 if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {
40 Current = EWC->getSubExpr();
41 assert(Current != nullptr);
42 }
43 if (auto *CE = dyn_cast<ConstantExpr>(Current)) {
44 Current = CE->getSubExpr();
45 assert(Current != nullptr);
46 }
47 Current = Current->IgnoreParens();
48 assert(Current != nullptr);
49 }
50 return *Current;
51 }
52
ignoreCFGOmittedNodes(const Stmt & S)53 const Stmt &ignoreCFGOmittedNodes(const Stmt &S) {
54 if (auto *E = dyn_cast<Expr>(&S))
55 return ignoreCFGOmittedNodes(*E);
56 return S;
57 }
58
59 // FIXME: Does not precisely handle non-virtual diamond inheritance. A single
60 // field decl will be modeled for all instances of the inherited field.
getFieldsFromClassHierarchy(QualType Type,FieldSet & Fields)61 static void getFieldsFromClassHierarchy(QualType Type, FieldSet &Fields) {
62 if (Type->isIncompleteType() || Type->isDependentType() ||
63 !Type->isRecordType())
64 return;
65
66 for (const FieldDecl *Field : Type->getAsRecordDecl()->fields())
67 Fields.insert(Field);
68 if (auto *CXXRecord = Type->getAsCXXRecordDecl())
69 for (const CXXBaseSpecifier &Base : CXXRecord->bases())
70 getFieldsFromClassHierarchy(Base.getType(), Fields);
71 }
72
73 /// Gets the set of all fields in the type.
getObjectFields(QualType Type)74 FieldSet getObjectFields(QualType Type) {
75 FieldSet Fields;
76 getFieldsFromClassHierarchy(Type, Fields);
77 return Fields;
78 }
79
containsSameFields(const FieldSet & Fields,const RecordStorageLocation::FieldToLoc & FieldLocs)80 bool containsSameFields(const FieldSet &Fields,
81 const RecordStorageLocation::FieldToLoc &FieldLocs) {
82 if (Fields.size() != FieldLocs.size())
83 return false;
84 for ([[maybe_unused]] auto [Field, Loc] : FieldLocs)
85 if (!Fields.contains(cast_or_null<FieldDecl>(Field)))
86 return false;
87 return true;
88 }
89
90 /// Returns the fields of a `RecordDecl` that are initialized by an
91 /// `InitListExpr` or `CXXParenListInitExpr`, in the order in which they appear
92 /// in `InitListExpr::inits()` / `CXXParenListInitExpr::getInitExprs()`.
93 /// `InitList->getType()` must be a record type.
94 template <class InitListT>
95 static std::vector<const FieldDecl *>
getFieldsForInitListExpr(const InitListT * InitList)96 getFieldsForInitListExpr(const InitListT *InitList) {
97 const RecordDecl *RD = InitList->getType()->getAsRecordDecl();
98 assert(RD != nullptr);
99
100 std::vector<const FieldDecl *> Fields;
101
102 if (InitList->getType()->isUnionType()) {
103 if (const FieldDecl *Field = InitList->getInitializedFieldInUnion())
104 Fields.push_back(Field);
105 return Fields;
106 }
107
108 // Unnamed bitfields are only used for padding and do not appear in
109 // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s
110 // field list, and we thus need to remove them before mapping inits to
111 // fields to avoid mapping inits to the wrongs fields.
112 llvm::copy_if(
113 RD->fields(), std::back_inserter(Fields),
114 [](const FieldDecl *Field) { return !Field->isUnnamedBitField(); });
115 return Fields;
116 }
117
RecordInitListHelper(const InitListExpr * InitList)118 RecordInitListHelper::RecordInitListHelper(const InitListExpr *InitList)
119 : RecordInitListHelper(InitList->getType(),
120 getFieldsForInitListExpr(InitList),
121 InitList->inits()) {}
122
RecordInitListHelper(const CXXParenListInitExpr * ParenInitList)123 RecordInitListHelper::RecordInitListHelper(
124 const CXXParenListInitExpr *ParenInitList)
125 : RecordInitListHelper(ParenInitList->getType(),
126 getFieldsForInitListExpr(ParenInitList),
127 ParenInitList->getInitExprs()) {}
128
RecordInitListHelper(QualType Ty,std::vector<const FieldDecl * > Fields,ArrayRef<Expr * > Inits)129 RecordInitListHelper::RecordInitListHelper(
130 QualType Ty, std::vector<const FieldDecl *> Fields,
131 ArrayRef<Expr *> Inits) {
132 auto *RD = Ty->getAsCXXRecordDecl();
133 assert(RD != nullptr);
134
135 // Unions initialized with an empty initializer list need special treatment.
136 // For structs/classes initialized with an empty initializer list, Clang
137 // puts `ImplicitValueInitExpr`s in `InitListExpr::inits()`, but for unions,
138 // it doesn't do this -- so we create an `ImplicitValueInitExpr` ourselves.
139 SmallVector<Expr *> InitsForUnion;
140 if (Ty->isUnionType() && Inits.empty()) {
141 assert(Fields.size() <= 1);
142 if (!Fields.empty()) {
143 ImplicitValueInitForUnion.emplace(Fields.front()->getType());
144 InitsForUnion.push_back(&*ImplicitValueInitForUnion);
145 }
146 Inits = InitsForUnion;
147 }
148
149 size_t InitIdx = 0;
150
151 assert(Fields.size() + RD->getNumBases() == Inits.size());
152 for (const CXXBaseSpecifier &Base : RD->bases()) {
153 assert(InitIdx < Inits.size());
154 Expr *Init = Inits[InitIdx++];
155 BaseInits.emplace_back(&Base, Init);
156 }
157
158 assert(Fields.size() == Inits.size() - InitIdx);
159 for (const FieldDecl *Field : Fields) {
160 assert(InitIdx < Inits.size());
161 Expr *Init = Inits[InitIdx++];
162 FieldInits.emplace_back(Field, Init);
163 }
164 }
165
insertIfGlobal(const Decl & D,llvm::DenseSet<const VarDecl * > & Globals)166 static void insertIfGlobal(const Decl &D,
167 llvm::DenseSet<const VarDecl *> &Globals) {
168 if (auto *V = dyn_cast<VarDecl>(&D))
169 if (V->hasGlobalStorage())
170 Globals.insert(V);
171 }
172
insertIfFunction(const Decl & D,llvm::DenseSet<const FunctionDecl * > & Funcs)173 static void insertIfFunction(const Decl &D,
174 llvm::DenseSet<const FunctionDecl *> &Funcs) {
175 if (auto *FD = dyn_cast<FunctionDecl>(&D))
176 Funcs.insert(FD);
177 }
178
getMemberForAccessor(const CXXMemberCallExpr & C)179 static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr &C) {
180 // Use getCalleeDecl instead of getMethodDecl in order to handle
181 // pointer-to-member calls.
182 const auto *MethodDecl = dyn_cast_or_null<CXXMethodDecl>(C.getCalleeDecl());
183 if (!MethodDecl)
184 return nullptr;
185 auto *Body = dyn_cast_or_null<CompoundStmt>(MethodDecl->getBody());
186 if (!Body || Body->size() != 1)
187 return nullptr;
188 if (auto *RS = dyn_cast<ReturnStmt>(*Body->body_begin()))
189 if (auto *Return = RS->getRetValue())
190 return dyn_cast<MemberExpr>(Return->IgnoreParenImpCasts());
191 return nullptr;
192 }
193
194 class ReferencedDeclsVisitor
195 : public AnalysisASTVisitor<ReferencedDeclsVisitor> {
196 public:
ReferencedDeclsVisitor(ReferencedDecls & Referenced)197 ReferencedDeclsVisitor(ReferencedDecls &Referenced)
198 : Referenced(Referenced) {}
199
TraverseConstructorInits(const CXXConstructorDecl * Ctor)200 void TraverseConstructorInits(const CXXConstructorDecl *Ctor) {
201 for (const CXXCtorInitializer *Init : Ctor->inits()) {
202 if (Init->isMemberInitializer()) {
203 Referenced.Fields.insert(Init->getMember());
204 } else if (Init->isIndirectMemberInitializer()) {
205 for (const auto *I : Init->getIndirectMember()->chain())
206 Referenced.Fields.insert(cast<FieldDecl>(I));
207 }
208
209 Expr *InitExpr = Init->getInit();
210
211 // Also collect declarations referenced in `InitExpr`.
212 TraverseStmt(InitExpr);
213
214 // If this is a `CXXDefaultInitExpr`, also collect declarations referenced
215 // within the default expression.
216 if (auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(InitExpr))
217 TraverseStmt(DefaultInit->getExpr());
218 }
219 }
220
VisitDecl(Decl * D)221 bool VisitDecl(Decl *D) {
222 insertIfGlobal(*D, Referenced.Globals);
223 insertIfFunction(*D, Referenced.Functions);
224 return true;
225 }
226
VisitDeclRefExpr(DeclRefExpr * E)227 bool VisitDeclRefExpr(DeclRefExpr *E) {
228 insertIfGlobal(*E->getDecl(), Referenced.Globals);
229 insertIfFunction(*E->getDecl(), Referenced.Functions);
230 return true;
231 }
232
VisitCXXMemberCallExpr(CXXMemberCallExpr * C)233 bool VisitCXXMemberCallExpr(CXXMemberCallExpr *C) {
234 // If this is a method that returns a member variable but does nothing else,
235 // model the field of the return value.
236 if (MemberExpr *E = getMemberForAccessor(*C))
237 if (const auto *FD = dyn_cast<FieldDecl>(E->getMemberDecl()))
238 Referenced.Fields.insert(FD);
239 return true;
240 }
241
VisitMemberExpr(MemberExpr * E)242 bool VisitMemberExpr(MemberExpr *E) {
243 // FIXME: should we be using `E->getFoundDecl()`?
244 const ValueDecl *VD = E->getMemberDecl();
245 insertIfGlobal(*VD, Referenced.Globals);
246 insertIfFunction(*VD, Referenced.Functions);
247 if (const auto *FD = dyn_cast<FieldDecl>(VD))
248 Referenced.Fields.insert(FD);
249 return true;
250 }
251
VisitInitListExpr(InitListExpr * InitList)252 bool VisitInitListExpr(InitListExpr *InitList) {
253 if (InitList->getType()->isRecordType())
254 for (const auto *FD : getFieldsForInitListExpr(InitList))
255 Referenced.Fields.insert(FD);
256 return true;
257 }
258
VisitCXXParenListInitExpr(CXXParenListInitExpr * ParenInitList)259 bool VisitCXXParenListInitExpr(CXXParenListInitExpr *ParenInitList) {
260 if (ParenInitList->getType()->isRecordType())
261 for (const auto *FD : getFieldsForInitListExpr(ParenInitList))
262 Referenced.Fields.insert(FD);
263 return true;
264 }
265
266 private:
267 ReferencedDecls &Referenced;
268 };
269
getReferencedDecls(const FunctionDecl & FD)270 ReferencedDecls getReferencedDecls(const FunctionDecl &FD) {
271 ReferencedDecls Result;
272 ReferencedDeclsVisitor Visitor(Result);
273 Visitor.TraverseStmt(FD.getBody());
274 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(&FD))
275 Visitor.TraverseConstructorInits(CtorDecl);
276
277 return Result;
278 }
279
getReferencedDecls(const Stmt & S)280 ReferencedDecls getReferencedDecls(const Stmt &S) {
281 ReferencedDecls Result;
282 ReferencedDeclsVisitor Visitor(Result);
283 Visitor.TraverseStmt(const_cast<Stmt *>(&S));
284 return Result;
285 }
286
287 } // namespace clang::dataflow
288