316 lines · cpp
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-exception6//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/ASTLambda.h"15#include "clang/AST/ComputeDependence.h"16#include "clang/AST/Decl.h"17#include "clang/AST/DeclBase.h"18#include "clang/AST/DeclCXX.h"19#include "clang/AST/Expr.h"20#include "clang/AST/ExprCXX.h"21#include "clang/AST/Stmt.h"22#include "clang/AST/Type.h"23#include "clang/Analysis/FlowSensitive/StorageLocation.h"24#include "clang/Basic/LLVM.h"25#include "llvm/ADT/STLExtras.h"26#include "llvm/ADT/SetVector.h"27#include <cassert>28#include <iterator>29#include <vector>30 31#define DEBUG_TYPE "dataflow"32 33namespace clang::dataflow {34 35const Expr &ignoreCFGOmittedNodes(const Expr &E) {36 const Expr *Current = &E;37 const Expr *Last = nullptr;38 while (Current != Last) {39 Last = Current;40 if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {41 Current = EWC->getSubExpr();42 assert(Current != nullptr);43 }44 if (auto *CE = dyn_cast<ConstantExpr>(Current)) {45 Current = CE->getSubExpr();46 assert(Current != nullptr);47 }48 Current = Current->IgnoreParens();49 assert(Current != nullptr);50 }51 return *Current;52}53 54const Stmt &ignoreCFGOmittedNodes(const Stmt &S) {55 if (auto *E = dyn_cast<Expr>(&S))56 return ignoreCFGOmittedNodes(*E);57 return S;58}59 60// FIXME: Does not precisely handle non-virtual diamond inheritance. A single61// field decl will be modeled for all instances of the inherited field.62static void getFieldsFromClassHierarchy(QualType Type, FieldSet &Fields) {63 if (Type->isIncompleteType() || Type->isDependentType() ||64 !Type->isRecordType())65 return;66 67 Fields.insert_range(Type->getAsRecordDecl()->fields());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.74FieldSet getObjectFields(QualType Type) {75 FieldSet Fields;76 getFieldsFromClassHierarchy(Type, Fields);77 return Fields;78}79 80bool containsSameFields(const FieldSet &Fields,81 const RecordStorageLocation::FieldToLoc &FieldLocs) {82 if (Fields.size() != FieldLocs.size())83 return false;84 for (const auto &Field : FieldLocs.keys())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 an91/// `InitListExpr` or `CXXParenListInitExpr`, in the order in which they appear92/// in `InitListExpr::inits()` / `CXXParenListInitExpr::getInitExprs()`.93/// `InitList->getType()` must be a record type.94template <class InitListT>95static std::vector<const FieldDecl *>96getFieldsForInitListExpr(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 in109 // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s110 // field list, and we thus need to remove them before mapping inits to111 // 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 118RecordInitListHelper::RecordInitListHelper(const InitListExpr *InitList)119 : RecordInitListHelper(InitList->getType(),120 getFieldsForInitListExpr(InitList),121 InitList->inits()) {}122 123RecordInitListHelper::RecordInitListHelper(124 const CXXParenListInitExpr *ParenInitList)125 : RecordInitListHelper(ParenInitList->getType(),126 getFieldsForInitListExpr(ParenInitList),127 ParenInitList->getInitExprs()) {}128 129RecordInitListHelper::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, Clang137 // 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 166static void insertIfGlobal(const Decl &D,167 llvm::SetVector<const VarDecl *> &Globals) {168 if (auto *V = dyn_cast<VarDecl>(&D))169 if (V->hasGlobalStorage())170 Globals.insert(V);171}172 173static void insertIfLocal(const Decl &D,174 llvm::SetVector<const VarDecl *> &Locals) {175 if (auto *V = dyn_cast<VarDecl>(&D))176 if (V->hasLocalStorage() && !isa<ParmVarDecl>(V))177 Locals.insert(V);178}179 180static void insertIfFunction(const Decl &D,181 llvm::SetVector<const FunctionDecl *> &Funcs) {182 if (auto *FD = dyn_cast<FunctionDecl>(&D))183 Funcs.insert(FD);184}185 186static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr &C) {187 // Use getCalleeDecl instead of getMethodDecl in order to handle188 // pointer-to-member calls.189 const auto *MethodDecl = dyn_cast_or_null<CXXMethodDecl>(C.getCalleeDecl());190 if (!MethodDecl)191 return nullptr;192 auto *Body = dyn_cast_or_null<CompoundStmt>(MethodDecl->getBody());193 if (!Body || Body->size() != 1)194 return nullptr;195 if (auto *RS = dyn_cast<ReturnStmt>(*Body->body_begin()))196 if (auto *Return = RS->getRetValue())197 return dyn_cast<MemberExpr>(Return->IgnoreParenImpCasts());198 return nullptr;199}200 201class ReferencedDeclsVisitor : public AnalysisASTVisitor {202public:203 ReferencedDeclsVisitor(ReferencedDecls &Referenced)204 : Referenced(Referenced) {}205 206 void traverseConstructorInits(const CXXConstructorDecl *Ctor) {207 for (const CXXCtorInitializer *Init : Ctor->inits()) {208 if (Init->isMemberInitializer()) {209 Referenced.Fields.insert(Init->getMember());210 } else if (Init->isIndirectMemberInitializer()) {211 for (const auto *I : Init->getIndirectMember()->chain())212 Referenced.Fields.insert(cast<FieldDecl>(I));213 }214 215 Expr *InitExpr = Init->getInit();216 217 // Also collect declarations referenced in `InitExpr`.218 TraverseStmt(InitExpr);219 220 // If this is a `CXXDefaultInitExpr`, also collect declarations referenced221 // within the default expression.222 if (auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(InitExpr))223 TraverseStmt(DefaultInit->getExpr());224 }225 }226 227 bool VisitDecl(Decl *D) override {228 insertIfGlobal(*D, Referenced.Globals);229 insertIfLocal(*D, Referenced.Locals);230 insertIfFunction(*D, Referenced.Functions);231 return true;232 }233 234 bool VisitDeclRefExpr(DeclRefExpr *E) override {235 insertIfGlobal(*E->getDecl(), Referenced.Globals);236 insertIfLocal(*E->getDecl(), Referenced.Locals);237 insertIfFunction(*E->getDecl(), Referenced.Functions);238 return true;239 }240 241 bool VisitCXXMemberCallExpr(CXXMemberCallExpr *C) override {242 // If this is a method that returns a member variable but does nothing else,243 // model the field of the return value.244 if (MemberExpr *E = getMemberForAccessor(*C))245 if (const auto *FD = dyn_cast<FieldDecl>(E->getMemberDecl()))246 Referenced.Fields.insert(FD);247 return true;248 }249 250 bool VisitMemberExpr(MemberExpr *E) override {251 // FIXME: should we be using `E->getFoundDecl()`?252 const ValueDecl *VD = E->getMemberDecl();253 insertIfGlobal(*VD, Referenced.Globals);254 insertIfFunction(*VD, Referenced.Functions);255 if (const auto *FD = dyn_cast<FieldDecl>(VD))256 Referenced.Fields.insert(FD);257 return true;258 }259 260 bool VisitInitListExpr(InitListExpr *InitList) override {261 if (InitList->getType()->isRecordType())262 Referenced.Fields.insert_range(getFieldsForInitListExpr(InitList));263 return true;264 }265 266 bool VisitCXXParenListInitExpr(CXXParenListInitExpr *ParenInitList) override {267 if (ParenInitList->getType()->isRecordType())268 Referenced.Fields.insert_range(getFieldsForInitListExpr(ParenInitList));269 return true;270 }271 272private:273 ReferencedDecls &Referenced;274};275 276ReferencedDecls getReferencedDecls(const FunctionDecl &FD) {277 ReferencedDecls Result;278 ReferencedDeclsVisitor Visitor(Result);279 Visitor.TraverseStmt(FD.getBody());280 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(&FD))281 Visitor.traverseConstructorInits(CtorDecl);282 283 // If analyzing a lambda call operator, collect all captures of parameters (of284 // the surrounding function). This collects them even if they are not285 // referenced in the body of the lambda call operator. Non-parameter local286 // variables that are captured are already collected into287 // `ReferencedDecls.Locals` when traversing the call operator body, but we288 // collect parameters here to avoid needing to check at each referencing node289 // whether the parameter is a lambda capture from a surrounding function or is290 // a parameter of the current function. If it becomes necessary to limit this291 // set to the parameters actually referenced in the body, alternative292 // optimizations can be implemented to minimize duplicative work.293 if (const auto *Method = dyn_cast<CXXMethodDecl>(&FD);294 Method && isLambdaCallOperator(Method)) {295 for (const auto &Capture : Method->getParent()->captures()) {296 if (Capture.capturesVariable()) {297 if (const auto *Param =298 dyn_cast<ParmVarDecl>(Capture.getCapturedVar())) {299 Result.LambdaCapturedParams.insert(Param);300 }301 }302 }303 }304 305 return Result;306}307 308ReferencedDecls getReferencedDecls(const Stmt &S) {309 ReferencedDecls Result;310 ReferencedDeclsVisitor Visitor(Result);311 Visitor.TraverseStmt(const_cast<Stmt *>(&S));312 return Result;313}314 315} // namespace clang::dataflow316