diff options
Diffstat (limited to 'lib/Analysis')
| -rw-r--r-- | lib/Analysis/AnalysisDeclContext.cpp | 38 | ||||
| -rw-r--r-- | lib/Analysis/BodyFarm.cpp | 366 | ||||
| -rw-r--r-- | lib/Analysis/BodyFarm.h | 51 | ||||
| -rw-r--r-- | lib/Analysis/CFG.cpp | 449 | ||||
| -rw-r--r-- | lib/Analysis/CallGraph.cpp | 38 | ||||
| -rw-r--r-- | lib/Analysis/CloneDetection.cpp | 155 | ||||
| -rw-r--r-- | lib/Analysis/CocoaConventions.cpp | 13 | ||||
| -rw-r--r-- | lib/Analysis/Consumed.cpp | 5 | ||||
| -rw-r--r-- | lib/Analysis/LiveVariables.cpp | 2 | ||||
| -rw-r--r-- | lib/Analysis/PrintfFormatString.cpp | 5 | ||||
| -rw-r--r-- | lib/Analysis/ReachableCode.cpp | 2 | ||||
| -rw-r--r-- | lib/Analysis/ScanfFormatString.cpp | 9 | ||||
| -rw-r--r-- | lib/Analysis/ThreadSafety.cpp | 21 | ||||
| -rw-r--r-- | lib/Analysis/ThreadSafetyCommon.cpp | 11 | ||||
| -rw-r--r-- | lib/Analysis/ThreadSafetyTIL.cpp | 1 | ||||
| -rw-r--r-- | lib/Analysis/UninitializedValues.cpp | 17 |
16 files changed, 838 insertions, 345 deletions
diff --git a/lib/Analysis/AnalysisDeclContext.cpp b/lib/Analysis/AnalysisDeclContext.cpp index ec15f34fb231d..181edff0a03f5 100644 --- a/lib/Analysis/AnalysisDeclContext.cpp +++ b/lib/Analysis/AnalysisDeclContext.cpp @@ -12,8 +12,7 @@ // //===----------------------------------------------------------------------===// -#include "clang/Analysis/AnalysisContext.h" -#include "BodyFarm.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/AST/ASTContext.h" #include "clang/AST/Decl.h" #include "clang/AST/DeclObjC.h" @@ -23,6 +22,7 @@ #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" +#include "clang/Analysis/BodyFarm.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/CFGStmtMap.h" #include "clang/Analysis/Support/BumpVector.h" @@ -63,33 +63,25 @@ AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr, cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs; } -AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG, - bool addImplicitDtors, - bool addInitializers, - bool addTemporaryDtors, - bool addLifetime, - bool synthesizeBodies, - bool addStaticInitBranch, - bool addCXXNewAllocator, - CodeInjector *injector) - : Injector(injector), SynthesizeBodies(synthesizeBodies) -{ +AnalysisDeclContextManager::AnalysisDeclContextManager( + ASTContext &ASTCtx, bool useUnoptimizedCFG, bool addImplicitDtors, + bool addInitializers, bool addTemporaryDtors, bool addLifetime, + bool addLoopExit, bool synthesizeBodies, bool addStaticInitBranch, + bool addCXXNewAllocator, CodeInjector *injector) + : Injector(injector), FunctionBodyFarm(ASTCtx, injector), + SynthesizeBodies(synthesizeBodies) { cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG; cfgBuildOptions.AddImplicitDtors = addImplicitDtors; cfgBuildOptions.AddInitializers = addInitializers; cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors; cfgBuildOptions.AddLifetime = addLifetime; + cfgBuildOptions.AddLoopExit = addLoopExit; cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch; cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator; } void AnalysisDeclContextManager::clear() { Contexts.clear(); } -static BodyFarm &getBodyFarm(ASTContext &C, CodeInjector *injector = nullptr) { - static BodyFarm *BF = new BodyFarm(C, injector); - return *BF; -} - Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const { IsAutosynthesized = false; if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { @@ -97,8 +89,7 @@ Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const { if (auto *CoroBody = dyn_cast_or_null<CoroutineBodyStmt>(Body)) Body = CoroBody->getBody(); if (Manager && Manager->synthesizeBodies()) { - Stmt *SynthesizedBody = - getBodyFarm(getASTContext(), Manager->Injector.get()).getBody(FD); + Stmt *SynthesizedBody = Manager->getBodyFarm().getBody(FD); if (SynthesizedBody) { Body = SynthesizedBody; IsAutosynthesized = true; @@ -109,8 +100,7 @@ Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const { else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { Stmt *Body = MD->getBody(); if (Manager && Manager->synthesizeBodies()) { - Stmt *SynthesizedBody = - getBodyFarm(getASTContext(), Manager->Injector.get()).getBody(MD); + Stmt *SynthesizedBody = Manager->getBodyFarm().getBody(MD); if (SynthesizedBody) { Body = SynthesizedBody; IsAutosynthesized = true; @@ -315,6 +305,8 @@ AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) { return AC.get(); } +BodyFarm &AnalysisDeclContextManager::getBodyFarm() { return FunctionBodyFarm; } + const StackFrameContext * AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S, const CFGBlock *Blk, unsigned Idx) { @@ -608,8 +600,6 @@ AnalysisDeclContext::~AnalysisDeclContext() { } } -AnalysisDeclContextManager::~AnalysisDeclContextManager() {} - LocationContext::~LocationContext() {} LocationContextManager::~LocationContextManager() { diff --git a/lib/Analysis/BodyFarm.cpp b/lib/Analysis/BodyFarm.cpp index 59127246105d3..e5d3c5ce5bc2a 100644 --- a/lib/Analysis/BodyFarm.cpp +++ b/lib/Analysis/BodyFarm.cpp @@ -12,13 +12,20 @@ // //===----------------------------------------------------------------------===// -#include "BodyFarm.h" +#include "clang/Analysis/BodyFarm.h" #include "clang/AST/ASTContext.h" +#include "clang/AST/CXXInheritance.h" #include "clang/AST/Decl.h" #include "clang/AST/Expr.h" +#include "clang/AST/ExprCXX.h" #include "clang/AST/ExprObjC.h" +#include "clang/AST/NestedNameSpecifier.h" #include "clang/Analysis/CodeInjector.h" +#include "clang/Basic/OperatorKinds.h" #include "llvm/ADT/StringSwitch.h" +#include "llvm/Support/Debug.h" + +#define DEBUG_TYPE "body-farm" using namespace clang; @@ -55,7 +62,8 @@ public: CompoundStmt *makeCompound(ArrayRef<Stmt*>); /// Create a new DeclRefExpr for the referenced variable. - DeclRefExpr *makeDeclRefExpr(const VarDecl *D); + DeclRefExpr *makeDeclRefExpr(const VarDecl *D, + bool RefersToEnclosingVariableOrCapture = false); /// Create a new UnaryOperator representing a dereference. UnaryOperator *makeDereference(const Expr *Arg, QualType Ty); @@ -66,9 +74,19 @@ public: /// Create an implicit cast to a builtin boolean type. ImplicitCastExpr *makeIntegralCastToBoolean(const Expr *Arg); - // Create an implicit cast for lvalue-to-rvaluate conversions. + /// Create an implicit cast for lvalue-to-rvaluate conversions. ImplicitCastExpr *makeLvalueToRvalue(const Expr *Arg, QualType Ty); + /// Make RValue out of variable declaration, creating a temporary + /// DeclRefExpr in the process. + ImplicitCastExpr * + makeLvalueToRvalue(const VarDecl *Decl, + bool RefersToEnclosingVariableOrCapture = false); + + /// Create an implicit cast of the given type. + ImplicitCastExpr *makeImplicitCast(const Expr *Arg, QualType Ty, + CastKind CK = CK_LValueToRValue); + /// Create an Objective-C bool literal. ObjCBoolLiteralExpr *makeObjCBool(bool Val); @@ -78,6 +96,18 @@ public: /// Create a Return statement. ReturnStmt *makeReturn(const Expr *RetVal); + /// Create an integer literal expression of the given type. + IntegerLiteral *makeIntegerLiteral(uint64_t Value, QualType Ty); + + /// Create a member expression. + MemberExpr *makeMemberExpression(Expr *base, ValueDecl *MemberDecl, + bool IsArrow = false, + ExprValueKind ValueKind = VK_LValue); + + /// Returns a *first* member field of a record declaration with a given name. + /// \return an nullptr if no member with such a name exists. + ValueDecl *findMemberField(const RecordDecl *RD, StringRef Name); + private: ASTContext &C; }; @@ -106,16 +136,14 @@ CompoundStmt *ASTMaker::makeCompound(ArrayRef<Stmt *> Stmts) { return new (C) CompoundStmt(C, Stmts, SourceLocation(), SourceLocation()); } -DeclRefExpr *ASTMaker::makeDeclRefExpr(const VarDecl *D) { - DeclRefExpr *DR = - DeclRefExpr::Create(/* Ctx = */ C, - /* QualifierLoc = */ NestedNameSpecifierLoc(), - /* TemplateKWLoc = */ SourceLocation(), - /* D = */ const_cast<VarDecl*>(D), - /* RefersToEnclosingVariableOrCapture = */ false, - /* NameLoc = */ SourceLocation(), - /* T = */ D->getType(), - /* VK = */ VK_LValue); +DeclRefExpr *ASTMaker::makeDeclRefExpr( + const VarDecl *D, + bool RefersToEnclosingVariableOrCapture) { + QualType Type = D->getType().getNonReferenceType(); + + DeclRefExpr *DR = DeclRefExpr::Create( + C, NestedNameSpecifierLoc(), SourceLocation(), const_cast<VarDecl *>(D), + RefersToEnclosingVariableOrCapture, SourceLocation(), Type, VK_LValue); return DR; } @@ -125,8 +153,25 @@ UnaryOperator *ASTMaker::makeDereference(const Expr *Arg, QualType Ty) { } ImplicitCastExpr *ASTMaker::makeLvalueToRvalue(const Expr *Arg, QualType Ty) { - return ImplicitCastExpr::Create(C, Ty, CK_LValueToRValue, - const_cast<Expr*>(Arg), nullptr, VK_RValue); + return makeImplicitCast(Arg, Ty, CK_LValueToRValue); +} + +ImplicitCastExpr * +ASTMaker::makeLvalueToRvalue(const VarDecl *Arg, + bool RefersToEnclosingVariableOrCapture) { + QualType Type = Arg->getType().getNonReferenceType(); + return makeLvalueToRvalue(makeDeclRefExpr(Arg, + RefersToEnclosingVariableOrCapture), + Type); +} + +ImplicitCastExpr *ASTMaker::makeImplicitCast(const Expr *Arg, QualType Ty, + CastKind CK) { + return ImplicitCastExpr::Create(C, Ty, + /* CastKind=*/ CK, + /* Expr=*/ const_cast<Expr *>(Arg), + /* CXXCastPath=*/ nullptr, + /* ExprValueKind=*/ VK_RValue); } Expr *ASTMaker::makeIntegralCast(const Expr *Arg, QualType Ty) { @@ -161,12 +206,259 @@ ReturnStmt *ASTMaker::makeReturn(const Expr *RetVal) { nullptr); } +IntegerLiteral *ASTMaker::makeIntegerLiteral(uint64_t Value, QualType Ty) { + llvm::APInt APValue = llvm::APInt(C.getTypeSize(Ty), Value); + return IntegerLiteral::Create(C, APValue, Ty, SourceLocation()); +} + +MemberExpr *ASTMaker::makeMemberExpression(Expr *base, ValueDecl *MemberDecl, + bool IsArrow, + ExprValueKind ValueKind) { + + DeclAccessPair FoundDecl = DeclAccessPair::make(MemberDecl, AS_public); + return MemberExpr::Create( + C, base, IsArrow, SourceLocation(), NestedNameSpecifierLoc(), + SourceLocation(), MemberDecl, FoundDecl, + DeclarationNameInfo(MemberDecl->getDeclName(), SourceLocation()), + /* TemplateArgumentListInfo=*/ nullptr, MemberDecl->getType(), ValueKind, + OK_Ordinary); +} + +ValueDecl *ASTMaker::findMemberField(const RecordDecl *RD, StringRef Name) { + + CXXBasePaths Paths( + /* FindAmbiguities=*/false, + /* RecordPaths=*/false, + /* DetectVirtual=*/ false); + const IdentifierInfo &II = C.Idents.get(Name); + DeclarationName DeclName = C.DeclarationNames.getIdentifier(&II); + + DeclContextLookupResult Decls = RD->lookup(DeclName); + for (NamedDecl *FoundDecl : Decls) + if (!FoundDecl->getDeclContext()->isFunctionOrMethod()) + return cast<ValueDecl>(FoundDecl); + + return nullptr; +} + //===----------------------------------------------------------------------===// // Creation functions for faux ASTs. //===----------------------------------------------------------------------===// typedef Stmt *(*FunctionFarmer)(ASTContext &C, const FunctionDecl *D); +static CallExpr *create_call_once_funcptr_call(ASTContext &C, ASTMaker M, + const ParmVarDecl *Callback, + ArrayRef<Expr *> CallArgs) { + + QualType Ty = Callback->getType(); + DeclRefExpr *Call = M.makeDeclRefExpr(Callback); + CastKind CK; + if (Ty->isRValueReferenceType()) { + CK = CK_LValueToRValue; + } else { + assert(Ty->isLValueReferenceType()); + CK = CK_FunctionToPointerDecay; + Ty = C.getPointerType(Ty.getNonReferenceType()); + } + + return new (C) + CallExpr(C, M.makeImplicitCast(Call, Ty.getNonReferenceType(), CK), + /*args=*/CallArgs, + /*QualType=*/C.VoidTy, + /*ExprValueType=*/VK_RValue, + /*SourceLocation=*/SourceLocation()); +} + +static CallExpr *create_call_once_lambda_call(ASTContext &C, ASTMaker M, + const ParmVarDecl *Callback, + CXXRecordDecl *CallbackDecl, + ArrayRef<Expr *> CallArgs) { + assert(CallbackDecl != nullptr); + assert(CallbackDecl->isLambda()); + FunctionDecl *callOperatorDecl = CallbackDecl->getLambdaCallOperator(); + assert(callOperatorDecl != nullptr); + + DeclRefExpr *callOperatorDeclRef = + DeclRefExpr::Create(/* Ctx =*/ C, + /* QualifierLoc =*/ NestedNameSpecifierLoc(), + /* TemplateKWLoc =*/ SourceLocation(), + const_cast<FunctionDecl *>(callOperatorDecl), + /* RefersToEnclosingVariableOrCapture=*/ false, + /* NameLoc =*/ SourceLocation(), + /* T =*/ callOperatorDecl->getType(), + /* VK =*/ VK_LValue); + + return new (C) + CXXOperatorCallExpr(/*AstContext=*/C, OO_Call, callOperatorDeclRef, + /*args=*/CallArgs, + /*QualType=*/C.VoidTy, + /*ExprValueType=*/VK_RValue, + /*SourceLocation=*/SourceLocation(), FPOptions()); +} + +/// Create a fake body for std::call_once. +/// Emulates the following function body: +/// +/// \code +/// typedef struct once_flag_s { +/// unsigned long __state = 0; +/// } once_flag; +/// template<class Callable> +/// void call_once(once_flag& o, Callable func) { +/// if (!o.__state) { +/// func(); +/// } +/// o.__state = 1; +/// } +/// \endcode +static Stmt *create_call_once(ASTContext &C, const FunctionDecl *D) { + DEBUG(llvm::dbgs() << "Generating body for call_once\n"); + + // We need at least two parameters. + if (D->param_size() < 2) + return nullptr; + + ASTMaker M(C); + + const ParmVarDecl *Flag = D->getParamDecl(0); + const ParmVarDecl *Callback = D->getParamDecl(1); + + if (!Callback->getType()->isReferenceType()) { + llvm::dbgs() << "libcxx03 std::call_once implementation, skipping.\n"; + return nullptr; + } + if (!Flag->getType()->isReferenceType()) { + llvm::dbgs() << "unknown std::call_once implementation, skipping.\n"; + return nullptr; + } + + QualType CallbackType = Callback->getType().getNonReferenceType(); + + // Nullable pointer, non-null iff function is a CXXRecordDecl. + CXXRecordDecl *CallbackRecordDecl = CallbackType->getAsCXXRecordDecl(); + QualType FlagType = Flag->getType().getNonReferenceType(); + auto *FlagRecordDecl = dyn_cast_or_null<RecordDecl>(FlagType->getAsTagDecl()); + + if (!FlagRecordDecl) { + DEBUG(llvm::dbgs() << "Flag field is not a record: " + << "unknown std::call_once implementation, " + << "ignoring the call.\n"); + return nullptr; + } + + // We initially assume libc++ implementation of call_once, + // where the once_flag struct has a field `__state_`. + ValueDecl *FlagFieldDecl = M.findMemberField(FlagRecordDecl, "__state_"); + + // Otherwise, try libstdc++ implementation, with a field + // `_M_once` + if (!FlagFieldDecl) { + FlagFieldDecl = M.findMemberField(FlagRecordDecl, "_M_once"); + } + + if (!FlagFieldDecl) { + DEBUG(llvm::dbgs() << "No field _M_once or __state_ found on " + << "std::once_flag struct: unknown std::call_once " + << "implementation, ignoring the call."); + return nullptr; + } + + bool isLambdaCall = CallbackRecordDecl && CallbackRecordDecl->isLambda(); + if (CallbackRecordDecl && !isLambdaCall) { + DEBUG(llvm::dbgs() << "Not supported: synthesizing body for functors when " + << "body farming std::call_once, ignoring the call."); + return nullptr; + } + + SmallVector<Expr *, 5> CallArgs; + const FunctionProtoType *CallbackFunctionType; + if (isLambdaCall) { + + // Lambda requires callback itself inserted as a first parameter. + CallArgs.push_back( + M.makeDeclRefExpr(Callback, + /* RefersToEnclosingVariableOrCapture=*/ true)); + CallbackFunctionType = CallbackRecordDecl->getLambdaCallOperator() + ->getType() + ->getAs<FunctionProtoType>(); + } else if (!CallbackType->getPointeeType().isNull()) { + CallbackFunctionType = + CallbackType->getPointeeType()->getAs<FunctionProtoType>(); + } else { + CallbackFunctionType = CallbackType->getAs<FunctionProtoType>(); + } + + if (!CallbackFunctionType) + return nullptr; + + // First two arguments are used for the flag and for the callback. + if (D->getNumParams() != CallbackFunctionType->getNumParams() + 2) { + DEBUG(llvm::dbgs() << "Types of params of the callback do not match " + << "params passed to std::call_once, " + << "ignoring the call\n"); + return nullptr; + } + + // All arguments past first two ones are passed to the callback, + // and we turn lvalues into rvalues if the argument is not passed by + // reference. + for (unsigned int ParamIdx = 2; ParamIdx < D->getNumParams(); ParamIdx++) { + const ParmVarDecl *PDecl = D->getParamDecl(ParamIdx); + Expr *ParamExpr = M.makeDeclRefExpr(PDecl); + if (!CallbackFunctionType->getParamType(ParamIdx - 2)->isReferenceType()) { + QualType PTy = PDecl->getType().getNonReferenceType(); + ParamExpr = M.makeLvalueToRvalue(ParamExpr, PTy); + } + CallArgs.push_back(ParamExpr); + } + + CallExpr *CallbackCall; + if (isLambdaCall) { + + CallbackCall = create_call_once_lambda_call(C, M, Callback, + CallbackRecordDecl, CallArgs); + } else { + + // Function pointer case. + CallbackCall = create_call_once_funcptr_call(C, M, Callback, CallArgs); + } + + DeclRefExpr *FlagDecl = + M.makeDeclRefExpr(Flag, + /* RefersToEnclosingVariableOrCapture=*/true); + + + MemberExpr *Deref = M.makeMemberExpression(FlagDecl, FlagFieldDecl); + assert(Deref->isLValue()); + QualType DerefType = Deref->getType(); + + // Negation predicate. + UnaryOperator *FlagCheck = new (C) UnaryOperator( + /* input=*/ + M.makeImplicitCast(M.makeLvalueToRvalue(Deref, DerefType), DerefType, + CK_IntegralToBoolean), + /* opc=*/ UO_LNot, + /* QualType=*/ C.IntTy, + /* ExprValueKind=*/ VK_RValue, + /* ExprObjectKind=*/ OK_Ordinary, SourceLocation()); + + // Create assignment. + BinaryOperator *FlagAssignment = M.makeAssignment( + Deref, M.makeIntegralCast(M.makeIntegerLiteral(1, C.IntTy), DerefType), + DerefType); + + IfStmt *Out = new (C) + IfStmt(C, SourceLocation(), + /* IsConstexpr=*/ false, + /* init=*/ nullptr, + /* var=*/ nullptr, + /* cond=*/ FlagCheck, + /* then=*/ M.makeCompound({CallbackCall, FlagAssignment})); + + return Out; +} + /// Create a fake body for dispatch_once. static Stmt *create_dispatch_once(ASTContext &C, const FunctionDecl *D) { // Check if we have at least two parameters. @@ -193,8 +485,8 @@ static Stmt *create_dispatch_once(ASTContext &C, const FunctionDecl *D) { // sets it, and calls the block. Basically, an AST dump of: // // void dispatch_once(dispatch_once_t *predicate, dispatch_block_t block) { - // if (!*predicate) { - // *predicate = 1; + // if (*predicate != ~0l) { + // *predicate = ~0l; // block(); // } // } @@ -202,22 +494,26 @@ static Stmt *create_dispatch_once(ASTContext &C, const FunctionDecl *D) { ASTMaker M(C); // (1) Create the call. - DeclRefExpr *DR = M.makeDeclRefExpr(Block); - ImplicitCastExpr *ICE = M.makeLvalueToRvalue(DR, Ty); - CallExpr *CE = new (C) CallExpr(C, ICE, None, C.VoidTy, VK_RValue, - SourceLocation()); + CallExpr *CE = new (C) CallExpr( + /*ASTContext=*/C, + /*StmtClass=*/M.makeLvalueToRvalue(/*Expr=*/Block), + /*args=*/None, + /*QualType=*/C.VoidTy, + /*ExprValueType=*/VK_RValue, + /*SourceLocation=*/SourceLocation()); // (2) Create the assignment to the predicate. - IntegerLiteral *IL = - IntegerLiteral::Create(C, llvm::APInt(C.getTypeSize(C.IntTy), (uint64_t) 1), - C.IntTy, SourceLocation()); + Expr *DoneValue = + new (C) UnaryOperator(M.makeIntegerLiteral(0, C.LongTy), UO_Not, C.LongTy, + VK_RValue, OK_Ordinary, SourceLocation()); + BinaryOperator *B = M.makeAssignment( M.makeDereference( M.makeLvalueToRvalue( M.makeDeclRefExpr(Predicate), PredicateQPtrTy), PredicateTy), - M.makeIntegralCast(IL, PredicateTy), + M.makeIntegralCast(DoneValue, PredicateTy), PredicateTy); // (3) Create the compound statement. @@ -233,14 +529,15 @@ static Stmt *create_dispatch_once(ASTContext &C, const FunctionDecl *D) { PredicateQPtrTy), PredicateTy), PredicateTy); - - UnaryOperator *UO = new (C) UnaryOperator(LValToRval, UO_LNot, C.IntTy, - VK_RValue, OK_Ordinary, - SourceLocation()); - + + Expr *GuardCondition = M.makeComparison(LValToRval, DoneValue, BO_NE); // (5) Create the 'if' statement. - IfStmt *If = new (C) IfStmt(C, SourceLocation(), false, nullptr, nullptr, - UO, CS); + IfStmt *If = new (C) IfStmt(C, SourceLocation(), + /* IsConstexpr=*/ false, + /* init=*/ nullptr, + /* var=*/ nullptr, + /* cond=*/ GuardCondition, + /* then=*/ CS); return If; } @@ -370,8 +667,9 @@ Stmt *BodyFarm::getBody(const FunctionDecl *D) { if (Name.startswith("OSAtomicCompareAndSwap") || Name.startswith("objc_atomicCompareAndSwap")) { FF = create_OSAtomicCompareAndSwap; - } - else { + } else if (Name == "call_once" && D->getDeclContext()->isStdNamespace()) { + FF = create_call_once; + } else { FF = llvm::StringSwitch<FunctionFarmer>(Name) .Case("dispatch_sync", create_dispatch_sync) .Case("dispatch_once", create_dispatch_once) diff --git a/lib/Analysis/BodyFarm.h b/lib/Analysis/BodyFarm.h deleted file mode 100644 index edbe996246515..0000000000000 --- a/lib/Analysis/BodyFarm.h +++ /dev/null @@ -1,51 +0,0 @@ -//== BodyFarm.h - Factory for conjuring up fake bodies -------------*- C++ -*-// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// BodyFarm is a factory for creating faux implementations for functions/methods -// for analysis purposes. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_LIB_ANALYSIS_BODYFARM_H -#define LLVM_CLANG_LIB_ANALYSIS_BODYFARM_H - -#include "clang/AST/DeclBase.h" -#include "clang/Basic/LLVM.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/Optional.h" - -namespace clang { - -class ASTContext; -class FunctionDecl; -class ObjCMethodDecl; -class ObjCPropertyDecl; -class Stmt; -class CodeInjector; - -class BodyFarm { -public: - BodyFarm(ASTContext &C, CodeInjector *injector) : C(C), Injector(injector) {} - - /// Factory method for creating bodies for ordinary functions. - Stmt *getBody(const FunctionDecl *D); - - /// Factory method for creating bodies for Objective-C properties. - Stmt *getBody(const ObjCMethodDecl *D); - -private: - typedef llvm::DenseMap<const Decl *, Optional<Stmt *> > BodyMap; - - ASTContext &C; - BodyMap Bodies; - CodeInjector *Injector; -}; -} - -#endif diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp index 6a77455edeef6..714b85d3a9fff 100644 --- a/lib/Analysis/CFG.cpp +++ b/lib/Analysis/CFG.cpp @@ -1,4 +1,4 @@ -//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// +//===- CFG.cpp - Classes for representing and building CFGs ---------------===// // // The LLVM Compiler Infrastructure // @@ -15,23 +15,53 @@ #include "clang/Analysis/CFG.h" #include "clang/AST/ASTContext.h" #include "clang/AST/Attr.h" -#include "clang/AST/CharUnits.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclBase.h" #include "clang/AST/DeclCXX.h" +#include "clang/AST/DeclGroup.h" +#include "clang/AST/Expr.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/OperationKinds.h" #include "clang/AST/PrettyPrinter.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/StmtCXX.h" +#include "clang/AST/StmtObjC.h" #include "clang/AST/StmtVisitor.h" +#include "clang/AST/Type.h" +#include "clang/Analysis/Support/BumpVector.h" #include "clang/Basic/Builtins.h" +#include "clang/Basic/ExceptionSpecificationType.h" +#include "clang/Basic/LLVM.h" +#include "clang/Basic/LangOptions.h" +#include "clang/Basic/SourceLocation.h" +#include "clang/Basic/Specifiers.h" +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/APSInt.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" -#include <memory> +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/DOTGraphTraits.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/Format.h" #include "llvm/Support/GraphWriter.h" #include "llvm/Support/SaveAndRestore.h" +#include "llvm/Support/raw_ostream.h" +#include <cassert> +#include <memory> +#include <string> +#include <tuple> +#include <utility> +#include <vector> using namespace clang; -namespace { - static SourceLocation GetEndLoc(Decl *D) { if (VarDecl *VD = dyn_cast<VarDecl>(D)) if (Expr *Ex = VD->getInit()) @@ -41,7 +71,7 @@ static SourceLocation GetEndLoc(Decl *D) { /// Helper for tryNormalizeBinaryOperator. Attempts to extract an IntegerLiteral /// or EnumConstantDecl from the given Expr. If it fails, returns nullptr. -const Expr *tryTransformToIntOrEnumConstant(const Expr *E) { +static const Expr *tryTransformToIntOrEnumConstant(const Expr *E) { E = E->IgnoreParens(); if (isa<IntegerLiteral>(E)) return E; @@ -111,6 +141,8 @@ static bool areExprTypesCompatible(const Expr *E1, const Expr *E2) { return DC1 == DC2; } +namespace { + class CFGBuilder; /// The CFG builder uses a recursive algorithm to build the CFG. When @@ -125,7 +157,6 @@ class CFGBuilder; /// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then /// the builder has an option not to add a subexpression as a /// block-level expression. -/// class AddStmtChoice { public: enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 }; @@ -168,23 +199,24 @@ private: /// class LocalScope { public: - typedef BumpVector<VarDecl*> AutomaticVarsTy; + friend class const_iterator; + + using AutomaticVarsTy = BumpVector<VarDecl *>; /// const_iterator - Iterates local scope backwards and jumps to previous /// scope on reaching the beginning of currently iterated scope. class const_iterator { - const LocalScope* Scope; + const LocalScope* Scope = nullptr; /// VarIter is guaranteed to be greater then 0 for every valid iterator. /// Invalid iterator (with null Scope) has VarIter equal to 0. - unsigned VarIter; + unsigned VarIter = 0; public: /// Create invalid iterator. Dereferencing invalid iterator is not allowed. /// Incrementing invalid iterator is allowed and will result in invalid /// iterator. - const_iterator() - : Scope(nullptr), VarIter(0) {} + const_iterator() = default; /// Create valid iterator. In case when S.Prev is an invalid iterator and /// I is equal to 0, this will create invalid iterator. @@ -197,8 +229,8 @@ public: } VarDecl *const* operator->() const { - assert (Scope && "Dereferencing invalid iterator is not allowed"); - assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); + assert(Scope && "Dereferencing invalid iterator is not allowed"); + assert(VarIter != 0 && "Iterator has invalid value of VarIter member"); return &Scope->Vars[VarIter - 1]; } VarDecl *operator*() const { @@ -209,7 +241,7 @@ public: if (!Scope) return *this; - assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); + assert(VarIter != 0 && "Iterator has invalid value of VarIter member"); --VarIter; if (VarIter == 0) *this = Scope->Prev; @@ -236,13 +268,12 @@ public: const_iterator shared_parent(const_iterator L); }; - friend class const_iterator; - private: BumpVectorContext ctx; /// Automatic variables in order of declaration. AutomaticVarsTy Vars; + /// Iterator to variable in previous scope that was declared just before /// begin of this scope. const_iterator Prev; @@ -260,6 +291,8 @@ public: } }; +} // namespace + /// distance - Calculates distance from this to L. L must be reachable from this /// (with use of ++ operator). Cost of calculating the distance is linear w.r.t. /// number of scopes between this and L. @@ -267,8 +300,8 @@ int LocalScope::const_iterator::distance(LocalScope::const_iterator L) { int D = 0; const_iterator F = *this; while (F.Scope != L.Scope) { - assert (F != const_iterator() - && "L iterator is not reachable from F iterator."); + assert(F != const_iterator() && + "L iterator is not reachable from F iterator."); D += F.VarIter; F = F.Scope->Prev; } @@ -300,16 +333,18 @@ LocalScope::const_iterator::shared_parent(LocalScope::const_iterator L) { } } +namespace { + /// Structure for specifying position in CFG during its build process. It /// consists of CFGBlock that specifies position in CFG and /// LocalScope::const_iterator that specifies position in LocalScope graph. struct BlockScopePosPair { - BlockScopePosPair() : block(nullptr) {} + CFGBlock *block = nullptr; + LocalScope::const_iterator scopePosition; + + BlockScopePosPair() = default; BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos) : block(b), scopePosition(scopePos) {} - - CFGBlock *block; - LocalScope::const_iterator scopePosition; }; /// TryResult - a class representing a variant over the values @@ -317,37 +352,46 @@ struct BlockScopePosPair { /// and is used by the CFGBuilder to decide if a branch condition /// can be decided up front during CFG construction. class TryResult { - int X; + int X = -1; + public: + TryResult() = default; TryResult(bool b) : X(b ? 1 : 0) {} - TryResult() : X(-1) {} bool isTrue() const { return X == 1; } bool isFalse() const { return X == 0; } bool isKnown() const { return X >= 0; } + void negate() { assert(isKnown()); X ^= 0x1; } }; -TryResult bothKnownTrue(TryResult R1, TryResult R2) { +} // namespace + +static TryResult bothKnownTrue(TryResult R1, TryResult R2) { if (!R1.isKnown() || !R2.isKnown()) return TryResult(); return TryResult(R1.isTrue() && R2.isTrue()); } +namespace { + class reverse_children { llvm::SmallVector<Stmt *, 12> childrenBuf; - ArrayRef<Stmt*> children; + ArrayRef<Stmt *> children; + public: reverse_children(Stmt *S); - typedef ArrayRef<Stmt*>::reverse_iterator iterator; + using iterator = ArrayRef<Stmt *>::reverse_iterator; + iterator begin() const { return children.rbegin(); } iterator end() const { return children.rend(); } }; +} // namespace reverse_children::reverse_children(Stmt *S) { if (CallExpr *CE = dyn_cast<CallExpr>(S)) { @@ -374,6 +418,8 @@ reverse_children::reverse_children(Stmt *S) { children = childrenBuf; } +namespace { + /// CFGBuilder - This class implements CFG construction from an AST. /// The builder is stateful: an instance of the builder should be used to only /// construct a single CFG. @@ -387,62 +433,65 @@ reverse_children::reverse_children(Stmt *S) { /// the AST in reverse order so that the successor of a basic block is /// constructed prior to its predecessor. This allows us to nicely capture /// implicit fall-throughs without extra basic blocks. -/// class CFGBuilder { - typedef BlockScopePosPair JumpTarget; - typedef BlockScopePosPair JumpSource; + using JumpTarget = BlockScopePosPair; + using JumpSource = BlockScopePosPair; ASTContext *Context; std::unique_ptr<CFG> cfg; - CFGBlock *Block; - CFGBlock *Succ; + // Current block. + CFGBlock *Block = nullptr; + + // Block after the current block. + CFGBlock *Succ = nullptr; + JumpTarget ContinueJumpTarget; JumpTarget BreakJumpTarget; - CFGBlock *SwitchTerminatedBlock; - CFGBlock *DefaultCaseBlock; - CFGBlock *TryTerminatedBlock; + JumpTarget SEHLeaveJumpTarget; + CFGBlock *SwitchTerminatedBlock = nullptr; + CFGBlock *DefaultCaseBlock = nullptr; + + // This can point either to a try or a __try block. The frontend forbids + // mixing both kinds in one function, so having one for both is enough. + CFGBlock *TryTerminatedBlock = nullptr; // Current position in local scope. LocalScope::const_iterator ScopePos; // LabelMap records the mapping from Label expressions to their jump targets. - typedef llvm::DenseMap<LabelDecl*, JumpTarget> LabelMapTy; + using LabelMapTy = llvm::DenseMap<LabelDecl *, JumpTarget>; LabelMapTy LabelMap; // A list of blocks that end with a "goto" that must be backpatched to their // resolved targets upon completion of CFG construction. - typedef std::vector<JumpSource> BackpatchBlocksTy; + using BackpatchBlocksTy = std::vector<JumpSource>; BackpatchBlocksTy BackpatchBlocks; // A list of labels whose address has been taken (for indirect gotos). - typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy; + using LabelSetTy = llvm::SmallSetVector<LabelDecl *, 8>; LabelSetTy AddressTakenLabels; - bool badCFG; + bool badCFG = false; const CFG::BuildOptions &BuildOpts; // State to track for building switch statements. - bool switchExclusivelyCovered; - Expr::EvalResult *switchCond; + bool switchExclusivelyCovered = false; + Expr::EvalResult *switchCond = nullptr; - CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry; - const Stmt *lastLookup; + CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry = nullptr; + const Stmt *lastLookup = nullptr; // Caches boolean evaluations of expressions to avoid multiple re-evaluations // during construction of branches for chained logical operators. - typedef llvm::DenseMap<Expr *, TryResult> CachedBoolEvalsTy; + using CachedBoolEvalsTy = llvm::DenseMap<Expr *, TryResult>; CachedBoolEvalsTy CachedBoolEvals; public: explicit CFGBuilder(ASTContext *astContext, - const CFG::BuildOptions &buildOpts) - : Context(astContext), cfg(new CFG()), // crew a new CFG - Block(nullptr), Succ(nullptr), - SwitchTerminatedBlock(nullptr), DefaultCaseBlock(nullptr), - TryTerminatedBlock(nullptr), badCFG(false), BuildOpts(buildOpts), - switchExclusivelyCovered(false), switchCond(nullptr), - cachedEntry(nullptr), lastLookup(nullptr) {} + const CFG::BuildOptions &buildOpts) + : Context(astContext), cfg(new CFG()), // crew a new CFG + BuildOpts(buildOpts) {} // buildCFG - Used by external clients to construct the CFG. std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement); @@ -501,6 +550,10 @@ private: CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E); CFGBlock *VisitReturnStmt(ReturnStmt *R); + CFGBlock *VisitSEHExceptStmt(SEHExceptStmt *S); + CFGBlock *VisitSEHFinallyStmt(SEHFinallyStmt *S); + CFGBlock *VisitSEHLeaveStmt(SEHLeaveStmt *S); + CFGBlock *VisitSEHTryStmt(SEHTryStmt *S); CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); CFGBlock *VisitSwitchStmt(SwitchStmt *S); CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, @@ -542,13 +595,9 @@ private: /// if the CXXBindTemporaryExpr was marked executed, and otherwise /// branches to the stored successor. struct TempDtorContext { - TempDtorContext() - : IsConditional(false), KnownExecuted(true), Succ(nullptr), - TerminatorExpr(nullptr) {} - + TempDtorContext() = default; TempDtorContext(TryResult KnownExecuted) - : IsConditional(true), KnownExecuted(KnownExecuted), Succ(nullptr), - TerminatorExpr(nullptr) {} + : IsConditional(true), KnownExecuted(KnownExecuted) {} /// Returns whether we need to start a new branch for a temporary destructor /// call. This is the case when the temporary destructor is @@ -567,10 +616,10 @@ private: TerminatorExpr = E; } - const bool IsConditional; - const TryResult KnownExecuted; - CFGBlock *Succ; - CXXBindTemporaryExpr *TerminatorExpr; + const bool IsConditional = false; + const TryResult KnownExecuted = true; + CFGBlock *Succ = nullptr; + CXXBindTemporaryExpr *TerminatorExpr = nullptr; }; // Visitors to walk an AST and generate destructors of temporaries in @@ -601,7 +650,9 @@ private: CFGBlock *addStmt(Stmt *S) { return Visit(S, AddStmtChoice::AlwaysAdd); } + CFGBlock *addInitializer(CXXCtorInitializer *I); + void addLoopExit(const Stmt *LoopStmt); void addAutomaticObjDtors(LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt *S); void addLifetimeEnds(LocalScope::const_iterator B, @@ -621,6 +672,7 @@ private: void addLocalScopeAndDtors(Stmt *S); // Interface to CFGBlock - adding CFGElements. + void appendStmt(CFGBlock *B, const Stmt *S) { if (alwaysAdd(S) && cachedEntry) cachedEntry->second = B; @@ -629,21 +681,27 @@ private: assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S); B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext()); } + void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) { B->appendInitializer(I, cfg->getBumpVectorContext()); } + void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) { B->appendNewAllocator(NE, cfg->getBumpVectorContext()); } + void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) { B->appendBaseDtor(BS, cfg->getBumpVectorContext()); } + void appendMemberDtor(CFGBlock *B, FieldDecl *FD) { B->appendMemberDtor(FD, cfg->getBumpVectorContext()); } + void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) { B->appendTemporaryDtor(E, cfg->getBumpVectorContext()); } + void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) { B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext()); } @@ -652,6 +710,10 @@ private: B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext()); } + void appendLoopExit(CFGBlock *B, const Stmt *LoopStmt) { + B->appendLoopExit(LoopStmt, cfg->getBumpVectorContext()); + } + void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) { B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext()); } @@ -799,10 +861,10 @@ private: const BinaryOperator *RHS = dyn_cast<BinaryOperator>(B->getRHS()->IgnoreParens()); if (!LHS || !RHS) - return TryResult(); + return {}; if (!LHS->isComparisonOp() || !RHS->isComparisonOp()) - return TryResult(); + return {}; const DeclRefExpr *Decl1; const Expr *Expr1; @@ -810,7 +872,7 @@ private: std::tie(Decl1, BO1, Expr1) = tryNormalizeBinaryOperator(LHS); if (!Decl1 || !Expr1) - return TryResult(); + return {}; const DeclRefExpr *Decl2; const Expr *Expr2; @@ -818,26 +880,26 @@ private: std::tie(Decl2, BO2, Expr2) = tryNormalizeBinaryOperator(RHS); if (!Decl2 || !Expr2) - return TryResult(); + return {}; // Check that it is the same variable on both sides. if (Decl1->getDecl() != Decl2->getDecl()) - return TryResult(); + return {}; // Make sure the user's intent is clear (e.g. they're comparing against two // int literals, or two things from the same enum) if (!areExprTypesCompatible(Expr1, Expr2)) - return TryResult(); + return {}; llvm::APSInt L1, L2; if (!Expr1->EvaluateAsInt(L1, *Context) || !Expr2->EvaluateAsInt(L2, *Context)) - return TryResult(); + return {}; // Can't compare signed with unsigned or with different bit width. if (L1.isSigned() != L2.isSigned() || L1.getBitWidth() != L2.getBitWidth()) - return TryResult(); + return {}; // Values that will be used to determine if result of logical // operator is always true/false @@ -868,7 +930,7 @@ private: Res2 = analyzeLogicOperatorCondition(BO2, Value, L2); if (!Res1.isKnown() || !Res2.isKnown()) - return TryResult(); + return {}; if (B->getOpcode() == BO_LAnd) { AlwaysTrue &= (Res1.isTrue() && Res2.isTrue()); @@ -884,7 +946,7 @@ private: BuildOpts.Observer->compareAlwaysTrue(B, AlwaysTrue); return TryResult(AlwaysTrue); } - return TryResult(); + return {}; } /// Try and evaluate an expression to an integer constant. @@ -901,7 +963,7 @@ private: TryResult tryEvaluateBool(Expr *S) { if (!BuildOpts.PruneTriviallyFalseEdges || S->isTypeDependent() || S->isValueDependent()) - return TryResult(); + return {}; if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) { if (Bop->isLogicalOp()) { @@ -976,7 +1038,7 @@ private: } } - return TryResult(); + return {}; } else if (Bop->isEqualityOp()) { TryResult BopRes = checkIncorrectEqualityOperator(Bop); if (BopRes.isKnown()) @@ -992,12 +1054,14 @@ private: if (E->EvaluateAsBooleanCondition(Result, *Context)) return Result; - return TryResult(); + return {}; } bool hasTrivialDestructor(VarDecl *VD); }; +} // namespace + inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder, const Stmt *stmt) const { return builder.alwaysAdd(stmt) || kind == AlwaysAdd; @@ -1119,7 +1183,6 @@ std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) { if (CFGBlock *B = cfg->getIndirectGotoBlock()) for (LabelSetTy::iterator I = AddressTakenLabels.begin(), E = AddressTakenLabels.end(); I != E; ++I ) { - // Lookup the target block. LabelMapTy::iterator LI = LabelMap.find(*I); @@ -1253,6 +1316,15 @@ static QualType getReferenceInitTemporaryType(ASTContext &Context, return Init->getType(); } +// TODO: Support adding LoopExit element to the CFG in case where the loop is +// ended by ReturnStmt, GotoStmt or ThrowExpr. +void CFGBuilder::addLoopExit(const Stmt *LoopStmt){ + if(!BuildOpts.AddLoopExit) + return; + autoCreateBlock(); + appendLoopExit(Block, LoopStmt); +} + void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt *S) { @@ -1351,8 +1423,8 @@ void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B, /// addImplicitDtorsForDestructor - Add implicit destructors generated for /// base and member objects in destructor. void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) { - assert (BuildOpts.AddImplicitDtors - && "Can be called only when dtors should be added"); + assert(BuildOpts.AddImplicitDtors && + "Can be called only when dtors should be added"); const CXXRecordDecl *RD = DD->getParent(); // At the end destroy virtual base objects. @@ -1555,6 +1627,7 @@ void CFGBuilder::prependAutomaticObjLifetimeWithTerminator( for (LocalScope::const_iterator I = B; I != E; ++I) InsertPos = Blk->insertLifetimeEnds(InsertPos, *I, Blk->getTerminator()); } + /// Visit - Walk the subtree of a statement and add extra /// blocks for ternary operators, &&, and ||. We also process "," and /// DeclStmts (which may contain nested control-flow). @@ -1716,6 +1789,18 @@ CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { case Stmt::ReturnStmtClass: return VisitReturnStmt(cast<ReturnStmt>(S)); + case Stmt::SEHExceptStmtClass: + return VisitSEHExceptStmt(cast<SEHExceptStmt>(S)); + + case Stmt::SEHFinallyStmtClass: + return VisitSEHFinallyStmt(cast<SEHFinallyStmt>(S)); + + case Stmt::SEHLeaveStmtClass: + return VisitSEHLeaveStmt(cast<SEHLeaveStmt>(S)); + + case Stmt::SEHTryStmtClass: + return VisitSEHTryStmt(cast<SEHTryStmt>(S)); + case Stmt::UnaryExprOrTypeTraitExprClass: return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), asc); @@ -1797,7 +1882,6 @@ CFGBuilder::VisitLogicalOperator(BinaryOperator *B, Stmt *Term, CFGBlock *TrueBlock, CFGBlock *FalseBlock) { - // Introspect the RHS. If it is a nested logical operation, we recursively // build the CFG using this function. Otherwise, resort to default // CFG construction behavior. @@ -1886,7 +1970,6 @@ CFGBuilder::VisitLogicalOperator(BinaryOperator *B, return std::make_pair(EntryLHSBlock, ExitBlock); } - CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc) { // && or || @@ -1948,7 +2031,6 @@ CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { } else badCFG = true; - return Block; } @@ -2072,7 +2154,6 @@ CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, return addStmt(C->getCond()); } - CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C) { LocalScope::const_iterator scopeBeginPos = ScopePos; addLocalScopeForStmt(C); @@ -2423,7 +2504,6 @@ CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) { return LastBlock; } - CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) { // If we were in the middle of a block we stop processing that block. // @@ -2447,6 +2527,117 @@ CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) { return VisitStmt(R, AddStmtChoice::AlwaysAdd); } +CFGBlock *CFGBuilder::VisitSEHExceptStmt(SEHExceptStmt *ES) { + // SEHExceptStmt are treated like labels, so they are the first statement in a + // block. + + // Save local scope position because in case of exception variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + addStmt(ES->getBlock()); + CFGBlock *SEHExceptBlock = Block; + if (!SEHExceptBlock) + SEHExceptBlock = createBlock(); + + appendStmt(SEHExceptBlock, ES); + + // Also add the SEHExceptBlock as a label, like with regular labels. + SEHExceptBlock->setLabel(ES); + + // Bail out if the CFG is bad. + if (badCFG) + return nullptr; + + // We set Block to NULL to allow lazy creation of a new block (if necessary). + Block = nullptr; + + return SEHExceptBlock; +} + +CFGBlock *CFGBuilder::VisitSEHFinallyStmt(SEHFinallyStmt *FS) { + return VisitCompoundStmt(FS->getBlock()); +} + +CFGBlock *CFGBuilder::VisitSEHLeaveStmt(SEHLeaveStmt *LS) { + // "__leave" is a control-flow statement. Thus we stop processing the current + // block. + if (badCFG) + return nullptr; + + // Now create a new block that ends with the __leave statement. + Block = createBlock(false); + Block->setTerminator(LS); + + // If there is no target for the __leave, then we are looking at an incomplete + // AST. This means that the CFG cannot be constructed. + if (SEHLeaveJumpTarget.block) { + addAutomaticObjHandling(ScopePos, SEHLeaveJumpTarget.scopePosition, LS); + addSuccessor(Block, SEHLeaveJumpTarget.block); + } else + badCFG = true; + + return Block; +} + +CFGBlock *CFGBuilder::VisitSEHTryStmt(SEHTryStmt *Terminator) { + // "__try"/"__except"/"__finally" is a control-flow statement. Thus we stop + // processing the current block. + CFGBlock *SEHTrySuccessor = nullptr; + + if (Block) { + if (badCFG) + return nullptr; + SEHTrySuccessor = Block; + } else SEHTrySuccessor = Succ; + + // FIXME: Implement __finally support. + if (Terminator->getFinallyHandler()) + return NYS(); + + CFGBlock *PrevSEHTryTerminatedBlock = TryTerminatedBlock; + + // Create a new block that will contain the __try statement. + CFGBlock *NewTryTerminatedBlock = createBlock(false); + + // Add the terminator in the __try block. + NewTryTerminatedBlock->setTerminator(Terminator); + + if (SEHExceptStmt *Except = Terminator->getExceptHandler()) { + // The code after the try is the implicit successor if there's an __except. + Succ = SEHTrySuccessor; + Block = nullptr; + CFGBlock *ExceptBlock = VisitSEHExceptStmt(Except); + if (!ExceptBlock) + return nullptr; + // Add this block to the list of successors for the block with the try + // statement. + addSuccessor(NewTryTerminatedBlock, ExceptBlock); + } + if (PrevSEHTryTerminatedBlock) + addSuccessor(NewTryTerminatedBlock, PrevSEHTryTerminatedBlock); + else + addSuccessor(NewTryTerminatedBlock, &cfg->getExit()); + + // The code after the try is the implicit successor. + Succ = SEHTrySuccessor; + + // Save the current "__try" context. + SaveAndRestore<CFGBlock *> save_try(TryTerminatedBlock, + NewTryTerminatedBlock); + cfg->addTryDispatchBlock(TryTerminatedBlock); + + // Save the current value for the __leave target. + // All __leaves should go to the code following the __try + // (FIXME: or if the __try has a __finally, to the __finally.) + SaveAndRestore<JumpTarget> save_break(SEHLeaveJumpTarget); + SEHLeaveJumpTarget = JumpTarget(SEHTrySuccessor, ScopePos); + + assert(Terminator->getTryBlock() && "__try must contain a non-NULL body"); + Block = nullptr; + return addStmt(Terminator->getTryBlock()); +} + CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) { // Get the block of the labeled statement. Add it to our map. addStmt(L->getSubStmt()); @@ -2543,6 +2734,8 @@ CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) { addAutomaticObjHandling(ScopePos, save_scope_pos.get(), F); + addLoopExit(F); + // "for" is a control-flow statement. Thus we stop processing the current // block. if (Block) { @@ -2668,7 +2861,6 @@ CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) { // false branch). addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor); - } while (false); // Link up the loop-back block to the entry condition block. @@ -2730,7 +2922,6 @@ CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) { // the same with newVariable replaced with existingItem; the binding works // the same except that for one ObjCForCollectionStmt::getElement() returns // a DeclStmt and the other returns a DeclRefExpr. - // CFGBlock *LoopSuccessor = nullptr; @@ -2882,6 +3073,7 @@ CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) { addLocalScopeForVarDecl(VD); addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W); } + addLoopExit(W); // "while" is a control-flow statement. Thus we stop processing the current // block. @@ -2981,7 +3173,6 @@ CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) { // false branch). addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor); - } while(false); // Link up the loop-back block to the entry condition block. @@ -2996,7 +3187,6 @@ CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) { return EntryConditionBlock; } - CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) { // FIXME: For now we pretend that @catch and the code it contains does not // exit. @@ -3045,6 +3235,8 @@ CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) { CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) { CFGBlock *LoopSuccessor = nullptr; + addLoopExit(D); + // "do...while" is a control-flow statement. Thus we stop processing the // current block. if (Block) { @@ -3167,7 +3359,6 @@ CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) { CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, AddStmtChoice asc) { - if (asc.alwaysAdd(*this, E)) { autoCreateBlock(); appendStmt(Block, E); @@ -3688,7 +3879,6 @@ CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C, CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE, AddStmtChoice asc) { - autoCreateBlock(); appendStmt(Block, NE); @@ -3991,8 +4181,6 @@ CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors( return Block; } -} // end anonymous namespace - /// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has /// no successors or predecessors. If this is the first block created in the /// CFG, it is automatically set to be the Entry and Exit of the CFG. @@ -4025,6 +4213,7 @@ CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const { case CFGElement::Statement: case CFGElement::Initializer: case CFGElement::NewAllocator: + case CFGElement::LoopExit: case CFGElement::LifetimeEnds: llvm_unreachable("getDestructorDecl should only be used with " "ImplicitDtors"); @@ -4066,7 +4255,6 @@ CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const { } case CFGElement::BaseDtor: case CFGElement::MemberDtor: - // Not yet supported. return nullptr; } @@ -4084,14 +4272,14 @@ bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const { //===----------------------------------------------------------------------===// CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, bool IsReachable) - : ReachableBlock(IsReachable ? B : nullptr), - UnreachableBlock(!IsReachable ? B : nullptr, - B && IsReachable ? AB_Normal : AB_Unreachable) {} + : ReachableBlock(IsReachable ? B : nullptr), + UnreachableBlock(!IsReachable ? B : nullptr, + B && IsReachable ? AB_Normal : AB_Unreachable) {} CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock) - : ReachableBlock(B), - UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock, - B == AlternateBlock ? AB_Alternate : AB_Normal) {} + : ReachableBlock(B), + UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock, + B == AlternateBlock ? AB_Alternate : AB_Normal) {} void CFGBlock::addSuccessor(AdjacentBlock Succ, BumpVectorContext &C) { @@ -4106,7 +4294,6 @@ void CFGBlock::addSuccessor(AdjacentBlock Succ, bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F, const CFGBlock *From, const CFGBlock *To) { - if (F.IgnoreNullPredecessors && !From) return true; @@ -4133,18 +4320,18 @@ bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F, namespace { class StmtPrinterHelper : public PrinterHelper { - typedef llvm::DenseMap<const Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; - typedef llvm::DenseMap<const Decl*,std::pair<unsigned,unsigned> > DeclMapTy; + using StmtMapTy = llvm::DenseMap<const Stmt *, std::pair<unsigned, unsigned>>; + using DeclMapTy = llvm::DenseMap<const Decl *, std::pair<unsigned, unsigned>>; + StmtMapTy StmtMap; DeclMapTy DeclMap; - signed currentBlock; - unsigned currStmt; + signed currentBlock = 0; + unsigned currStmt = 0; const LangOptions &LangOpts; -public: +public: StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) - : currentBlock(0), currStmt(0), LangOpts(LO) - { + : LangOpts(LO) { for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { unsigned j = 1; for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; @@ -4199,7 +4386,7 @@ public: } } - ~StmtPrinterHelper() override {} + ~StmtPrinterHelper() override = default; const LangOptions &getLangOpts() const { return LangOpts; } void setBlockID(signed i) { currentBlock = i; } @@ -4235,20 +4422,17 @@ public: return true; } }; -} // end anonymous namespace - -namespace { class CFGBlockTerminatorPrint - : public StmtVisitor<CFGBlockTerminatorPrint,void> { - + : public StmtVisitor<CFGBlockTerminatorPrint,void> { raw_ostream &OS; StmtPrinterHelper* Helper; PrintingPolicy Policy; + public: CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper, const PrintingPolicy &Policy) - : OS(os), Helper(helper), Policy(Policy) { + : OS(os), Helper(helper), Policy(Policy) { this->Policy.IncludeNewlines = false; } @@ -4302,6 +4486,10 @@ public: OS << "try ..."; } + void VisitSEHTryStmt(SEHTryStmt *CS) { + OS << "__try ..."; + } + void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) { if (Stmt *Cond = C->getCond()) Cond->printPretty(OS, Helper, Policy); @@ -4353,7 +4541,8 @@ public: Visit(T.getStmt()); } }; -} // end anonymous namespace + +} // namespace static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper, const CFGElement &E) { @@ -4403,7 +4592,6 @@ static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper, // Expressions need a newline. if (isa<Expr>(S)) OS << '\n'; - } else if (Optional<CFGInitializer> IE = E.getAs<CFGInitializer>()) { const CXXCtorInitializer *I = IE->getInitializer(); if (I->isBaseInitializer()) @@ -4422,7 +4610,6 @@ static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper, else if (I->isDelegatingInitializer()) OS << " (Delegating initializer)\n"; else OS << " (Member initializer)\n"; - } else if (Optional<CFGAutomaticObjDtor> DE = E.getAs<CFGAutomaticObjDtor>()) { const VarDecl *VD = DE->getVarDecl(); @@ -4435,13 +4622,14 @@ static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper, OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()"; OS << " (Implicit destructor)\n"; - } else if (Optional<CFGLifetimeEnds> DE = E.getAs<CFGLifetimeEnds>()) { const VarDecl *VD = DE->getVarDecl(); Helper.handleDecl(VD, OS); OS << " (Lifetime ends)\n"; - + } else if (Optional<CFGLoopExit> LE = E.getAs<CFGLoopExit>()) { + const Stmt *LoopStmt = LE->getLoopStmt(); + OS << LoopStmt->getStmtClassName() << " (LoopExit)\n"; } else if (Optional<CFGNewAllocator> NE = E.getAs<CFGNewAllocator>()) { OS << "CFGNewAllocator("; if (const CXXNewExpr *AllocExpr = NE->getAllocatorExpr()) @@ -4460,14 +4648,12 @@ static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper, const CXXBaseSpecifier *BS = BE->getBaseSpecifier(); OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()"; OS << " (Base object destructor)\n"; - } else if (Optional<CFGMemberDtor> ME = E.getAs<CFGMemberDtor>()) { const FieldDecl *FD = ME->getFieldDecl(); const Type *T = FD->getType()->getBaseElementTypeUnsafe(); OS << "this->" << FD->getName(); OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()"; OS << " (Member object destructor)\n"; - } else if (Optional<CFGTemporaryDtor> TE = E.getAs<CFGTemporaryDtor>()) { const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr(); OS << "~"; @@ -4480,7 +4666,6 @@ static void print_block(raw_ostream &OS, const CFG* cfg, const CFGBlock &B, StmtPrinterHelper &Helper, bool print_edges, bool ShowColors) { - Helper.setBlockID(B.getBlockID()); // Print the header. @@ -4505,7 +4690,6 @@ static void print_block(raw_ostream &OS, const CFG* cfg, // Print the label of this block. if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) { - if (print_edges) OS << " "; @@ -4531,7 +4715,11 @@ static void print_block(raw_ostream &OS, const CFG* cfg, else OS << "..."; OS << ")"; - + } else if (SEHExceptStmt *ES = dyn_cast<SEHExceptStmt>(Label)) { + OS << "__except ("; + ES->getFilterExpr()->printPretty(OS, &Helper, + PrintingPolicy(Helper.getLangOpts()), 0); + OS << ")"; } else llvm_unreachable("Invalid label statement in CFGBlock."); @@ -4543,7 +4731,6 @@ static void print_block(raw_ostream &OS, const CFG* cfg, for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; I != E ; ++I, ++j ) { - // Print the statement # in the basic block and the statement itself. if (print_edges) OS << " "; @@ -4590,7 +4777,6 @@ static void print_block(raw_ostream &OS, const CFG* cfg, for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); I != E; ++I, ++i) { - if (i % 10 == 8) OS << "\n "; @@ -4628,7 +4814,6 @@ static void print_block(raw_ostream &OS, const CFG* cfg, for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); I != E; ++I, ++i) { - if (i % 10 == 8) OS << "\n "; @@ -4657,7 +4842,6 @@ static void print_block(raw_ostream &OS, const CFG* cfg, } } - /// dump - A simple pretty printer of a CFG that outputs to stderr. void CFG::dump(const LangOptions &LO, bool ShowColors) const { print(llvm::errs(), LO, ShowColors); @@ -4780,7 +4964,6 @@ Stmt *CFGBlock::getTerminatorCondition(bool StripParens) { // CFG Graphviz Visualization //===----------------------------------------------------------------------===// - #ifndef NDEBUG static StmtPrinterHelper* GraphHelper; #endif @@ -4795,13 +4978,12 @@ void CFG::viewCFG(const LangOptions &LO) const { } namespace llvm { + template<> struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { - - DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} + DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} static std::string getNodeLabel(const CFGBlock *Node, const CFG* Graph) { - #ifndef NDEBUG std::string OutSStr; llvm::raw_string_ostream Out(OutSStr); @@ -4819,8 +5001,9 @@ struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { return OutStr; #else - return ""; + return {}; #endif } }; -} // end namespace llvm + +} // namespace llvm diff --git a/lib/Analysis/CallGraph.cpp b/lib/Analysis/CallGraph.cpp index 6d9530bf0c68d..fb6d7e87a9a31 100644 --- a/lib/Analysis/CallGraph.cpp +++ b/lib/Analysis/CallGraph.cpp @@ -1,4 +1,4 @@ -//== CallGraph.cpp - AST-based Call graph ----------------------*- C++ -*--==// +//===- CallGraph.cpp - AST-based Call graph -------------------------------===// // // The LLVM Compiler Infrastructure // @@ -10,13 +10,28 @@ // This file defines the AST-based CallGraph. // //===----------------------------------------------------------------------===// + #include "clang/Analysis/CallGraph.h" -#include "clang/AST/ASTContext.h" #include "clang/AST/Decl.h" +#include "clang/AST/DeclBase.h" +#include "clang/AST/DeclObjC.h" +#include "clang/AST/Expr.h" +#include "clang/AST/ExprObjC.h" +#include "clang/AST/Stmt.h" #include "clang/AST/StmtVisitor.h" +#include "clang/Basic/IdentifierTable.h" +#include "clang/Basic/LLVM.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/DOTGraphTraits.h" #include "llvm/Support/GraphWriter.h" +#include "llvm/Support/raw_ostream.h" +#include <cassert> +#include <memory> +#include <string> using namespace clang; @@ -26,6 +41,7 @@ STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); STATISTIC(NumBlockCallEdges, "Number of block call edges"); namespace { + /// A helper class, which walks the AST and locates all the call sites in the /// given function body. class CGBuilder : public StmtVisitor<CGBuilder> { @@ -33,8 +49,7 @@ class CGBuilder : public StmtVisitor<CGBuilder> { CallGraphNode *CallerNode; public: - CGBuilder(CallGraph *g, CallGraphNode *N) - : G(g), CallerNode(N) {} + CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} void VisitStmt(Stmt *S) { VisitChildren(S); } @@ -90,7 +105,7 @@ public: } }; -} // end anonymous namespace +} // namespace void CallGraph::addNodesForBlocks(DeclContext *D) { if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) @@ -105,7 +120,7 @@ CallGraph::CallGraph() { Root = getOrInsertNode(nullptr); } -CallGraph::~CallGraph() {} +CallGraph::~CallGraph() = default; bool CallGraph::includeInGraph(const Decl *D) { assert(D); @@ -164,8 +179,8 @@ void CallGraph::print(raw_ostream &OS) const { // We are going to print the graph in reverse post order, partially, to make // sure the output is deterministic. - llvm::ReversePostOrderTraversal<const clang::CallGraph*> RPOT(this); - for (llvm::ReversePostOrderTraversal<const clang::CallGraph*>::rpo_iterator + llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this); + for (llvm::ReversePostOrderTraversal<const CallGraph *>::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { const CallGraphNode *N = *I; @@ -209,8 +224,7 @@ namespace llvm { template <> struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { - - DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} + DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} static std::string getNodeLabel(const CallGraphNode *Node, const CallGraph *CG) { @@ -222,6 +236,6 @@ struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { else return "< >"; } - }; -} + +} // namespace llvm diff --git a/lib/Analysis/CloneDetection.cpp b/lib/Analysis/CloneDetection.cpp index 5ea74989a7ec9..098803f9a417d 100644 --- a/lib/Analysis/CloneDetection.cpp +++ b/lib/Analysis/CloneDetection.cpp @@ -13,16 +13,12 @@ #include "clang/Analysis/CloneDetection.h" -#include "clang/AST/ASTContext.h" -#include "clang/AST/RecursiveASTVisitor.h" -#include "clang/AST/Stmt.h" -#include "clang/Lex/Lexer.h" +#include "clang/AST/DataCollection.h" +#include "clang/AST/DeclTemplate.h" #include "llvm/Support/MD5.h" -#include "llvm/Support/raw_ostream.h" #include "llvm/Support/Path.h" using namespace clang; -using namespace clang::clone_detection; StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D, unsigned StartIndex, unsigned EndIndex) @@ -91,34 +87,6 @@ SourceRange StmtSequence::getSourceRange() const { return SourceRange(getStartLoc(), getEndLoc()); } -/// Prints the macro name that contains the given SourceLocation into the given -/// raw_string_ostream. -static void printMacroName(llvm::raw_string_ostream &MacroStack, - ASTContext &Context, SourceLocation Loc) { - MacroStack << Lexer::getImmediateMacroName(Loc, Context.getSourceManager(), - Context.getLangOpts()); - - // Add an empty space at the end as a padding to prevent - // that macro names concatenate to the names of other macros. - MacroStack << " "; -} - -std::string clone_detection::getMacroStack(SourceLocation Loc, - ASTContext &Context) { - std::string MacroStack; - llvm::raw_string_ostream MacroStackStream(MacroStack); - SourceManager &SM = Context.getSourceManager(); - - // Iterate over all macros that expanded into the given SourceLocation. - while (Loc.isMacroID()) { - // Add the macro name to the stream. - printMacroName(MacroStackStream, Context, Loc); - Loc = SM.getImmediateMacroCallerLoc(Loc); - } - MacroStackStream.flush(); - return MacroStack; -} - void CloneDetector::analyzeCodeBody(const Decl *D) { assert(D); assert(D->hasBody()); @@ -184,16 +152,17 @@ void OnlyLargestCloneConstraint::constrain( } } -bool FilenamePatternConstraint::isAutoGenerated(const CloneDetector::CloneGroup &Group) { +bool FilenamePatternConstraint::isAutoGenerated( + const CloneDetector::CloneGroup &Group) { std::string Error; - if (IgnoredFilesPattern.empty() || Group.empty() || + if (IgnoredFilesPattern.empty() || Group.empty() || !IgnoredFilesRegex->isValid(Error)) return false; for (const StmtSequence &S : Group) { const SourceManager &SM = S.getASTContext().getSourceManager(); - StringRef Filename = llvm::sys::path::filename(SM.getFilename( - S.getContainingDecl()->getLocation())); + StringRef Filename = llvm::sys::path::filename( + SM.getFilename(S.getContainingDecl()->getLocation())); if (IgnoredFilesRegex->match(Filename)) return true; } @@ -201,6 +170,59 @@ bool FilenamePatternConstraint::isAutoGenerated(const CloneDetector::CloneGroup return false; } +/// This class defines what a type II code clone is: If it collects for two +/// statements the same data, then those two statements are considered to be +/// clones of each other. +/// +/// All collected data is forwarded to the given data consumer of the type T. +/// The data consumer class needs to provide a member method with the signature: +/// update(StringRef Str) +namespace { +template <class T> +class CloneTypeIIStmtDataCollector + : public ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>> { + ASTContext &Context; + /// The data sink to which all data is forwarded. + T &DataConsumer; + + template <class Ty> void addData(const Ty &Data) { + data_collection::addDataToConsumer(DataConsumer, Data); + } + +public: + CloneTypeIIStmtDataCollector(const Stmt *S, ASTContext &Context, + T &DataConsumer) + : Context(Context), DataConsumer(DataConsumer) { + this->Visit(S); + } + +// Define a visit method for each class to collect data and subsequently visit +// all parent classes. This uses a template so that custom visit methods by us +// take precedence. +#define DEF_ADD_DATA(CLASS, CODE) \ + template <class = void> void Visit##CLASS(const CLASS *S) { \ + CODE; \ + ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ + } + +#include "clang/AST/StmtDataCollectors.inc" + +// Type II clones ignore variable names and literals, so let's skip them. +#define SKIP(CLASS) \ + void Visit##CLASS(const CLASS *S) { \ + ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ + } + SKIP(DeclRefExpr) + SKIP(MemberExpr) + SKIP(IntegerLiteral) + SKIP(FloatingLiteral) + SKIP(StringLiteral) + SKIP(CXXBoolLiteralExpr) + SKIP(CharacterLiteral) +#undef SKIP +}; +} // end anonymous namespace + static size_t createHash(llvm::MD5 &Hash) { size_t HashCode; @@ -216,13 +238,22 @@ static size_t createHash(llvm::MD5 &Hash) { return HashCode; } -size_t RecursiveCloneTypeIIConstraint::saveHash( - const Stmt *S, const Decl *D, - std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) { +/// Generates and saves a hash code for the given Stmt. +/// \param S The given Stmt. +/// \param D The Decl containing S. +/// \param StmtsByHash Output parameter that will contain the hash codes for +/// each StmtSequence in the given Stmt. +/// \return The hash code of the given Stmt. +/// +/// If the given Stmt is a CompoundStmt, this method will also generate +/// hashes for all possible StmtSequences in the children of this Stmt. +static size_t +saveHash(const Stmt *S, const Decl *D, + std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) { llvm::MD5 Hash; ASTContext &Context = D->getASTContext(); - StmtDataCollector<llvm::MD5>(S, Context, Hash); + CloneTypeIIStmtDataCollector<llvm::MD5>(S, Context, Hash); auto CS = dyn_cast<CompoundStmt>(S); SmallVector<size_t, 8> ChildHashes; @@ -288,8 +319,8 @@ public: static void CollectStmtSequenceData(const StmtSequence &Sequence, FoldingSetNodeIDWrapper &OutputData) { for (const Stmt *S : Sequence) { - StmtDataCollector<FoldingSetNodeIDWrapper>(S, Sequence.getASTContext(), - OutputData); + CloneTypeIIStmtDataCollector<FoldingSetNodeIDWrapper>( + S, Sequence.getASTContext(), OutputData); for (const Stmt *Child : S->children()) { if (!Child) @@ -318,7 +349,7 @@ static bool areSequencesClones(const StmtSequence &LHS, return DataLHS == DataRHS; } -void RecursiveCloneTypeIIConstraint::constrain( +void RecursiveCloneTypeIIHashConstraint::constrain( std::vector<CloneDetector::CloneGroup> &Sequences) { // FIXME: Maybe we can do this in-place and don't need this additional vector. std::vector<CloneDetector::CloneGroup> Result; @@ -339,7 +370,7 @@ void RecursiveCloneTypeIIConstraint::constrain( // Sort hash_codes in StmtsByHash. std::stable_sort(StmtsByHash.begin(), StmtsByHash.end(), [](std::pair<size_t, StmtSequence> LHS, - std::pair<size_t, StmtSequence> RHS) { + std::pair<size_t, StmtSequence> RHS) { return LHS.first < RHS.first; }); @@ -359,8 +390,7 @@ void RecursiveCloneTypeIIConstraint::constrain( for (; i < StmtsByHash.size(); ++i) { // A different hash value means we have reached the end of the sequence. - if (PrototypeHash != StmtsByHash[i].first || - !areSequencesClones(StmtsByHash[i].second, Current.second)) { + if (PrototypeHash != StmtsByHash[i].first) { // The current sequence could be the start of a new CloneGroup. So we // decrement i so that we visit it again in the outer loop. // Note: i can never be 0 at this point because we are just comparing @@ -383,8 +413,17 @@ void RecursiveCloneTypeIIConstraint::constrain( Sequences = Result; } +void RecursiveCloneTypeIIVerifyConstraint::constrain( + std::vector<CloneDetector::CloneGroup> &Sequences) { + CloneConstraint::splitCloneGroups( + Sequences, [](const StmtSequence &A, const StmtSequence &B) { + return areSequencesClones(A, B); + }); +} + size_t MinComplexityConstraint::calculateStmtComplexity( - const StmtSequence &Seq, const std::string &ParentMacroStack) { + const StmtSequence &Seq, std::size_t Limit, + const std::string &ParentMacroStack) { if (Seq.empty()) return 0; @@ -393,8 +432,8 @@ size_t MinComplexityConstraint::calculateStmtComplexity( ASTContext &Context = Seq.getASTContext(); // Look up what macros expanded into the current statement. - std::string StartMacroStack = getMacroStack(Seq.getStartLoc(), Context); - std::string EndMacroStack = getMacroStack(Seq.getEndLoc(), Context); + std::string MacroStack = + data_collection::getMacroStack(Seq.getStartLoc(), Context); // First, check if ParentMacroStack is not empty which means we are currently // dealing with a parent statement which was expanded from a macro. @@ -404,8 +443,7 @@ size_t MinComplexityConstraint::calculateStmtComplexity( // macro expansion will only increase the total complexity by one. // Note: This is not the final complexity of this statement as we still // add the complexity of the child statements to the complexity value. - if (!ParentMacroStack.empty() && (StartMacroStack == ParentMacroStack && - EndMacroStack == ParentMacroStack)) { + if (!ParentMacroStack.empty() && MacroStack == ParentMacroStack) { Complexity = 0; } @@ -414,12 +452,16 @@ size_t MinComplexityConstraint::calculateStmtComplexity( if (Seq.holdsSequence()) { for (const Stmt *S : Seq) { Complexity += calculateStmtComplexity( - StmtSequence(S, Seq.getContainingDecl()), StartMacroStack); + StmtSequence(S, Seq.getContainingDecl()), Limit, MacroStack); + if (Complexity >= Limit) + return Limit; } } else { for (const Stmt *S : Seq.front()->children()) { Complexity += calculateStmtComplexity( - StmtSequence(S, Seq.getContainingDecl()), StartMacroStack); + StmtSequence(S, Seq.getContainingDecl()), Limit, MacroStack); + if (Complexity >= Limit) + return Limit; } } return Complexity; @@ -437,7 +479,8 @@ void MatchingVariablePatternConstraint::constrain( void CloneConstraint::splitCloneGroups( std::vector<CloneDetector::CloneGroup> &CloneGroups, - std::function<bool(const StmtSequence &, const StmtSequence &)> Compare) { + llvm::function_ref<bool(const StmtSequence &, const StmtSequence &)> + Compare) { std::vector<CloneDetector::CloneGroup> Result; for (auto &HashGroup : CloneGroups) { // Contains all indexes in HashGroup that were already added to a diff --git a/lib/Analysis/CocoaConventions.cpp b/lib/Analysis/CocoaConventions.cpp index be1262dc99108..4d57623e21611 100644 --- a/lib/Analysis/CocoaConventions.cpp +++ b/lib/Analysis/CocoaConventions.cpp @@ -47,12 +47,19 @@ bool cocoa::isRefType(QualType RetTy, StringRef Prefix, return Name.startswith(Prefix); } +/// Returns true when the passed-in type is a CF-style reference-counted +/// type from the DiskArbitration framework. +static bool isDiskArbitrationAPIRefType(QualType T) { + return cocoa::isRefType(T, "DADisk") || + cocoa::isRefType(T, "DADissenter") || + cocoa::isRefType(T, "DASessionRef"); +} + bool coreFoundation::isCFObjectRef(QualType T) { return cocoa::isRefType(T, "CF") || // Core Foundation. cocoa::isRefType(T, "CG") || // Core Graphics. - cocoa::isRefType(T, "DADisk") || // Disk Arbitration API. - cocoa::isRefType(T, "DADissenter") || - cocoa::isRefType(T, "DASessionRef"); + cocoa::isRefType(T, "CM") || // Core Media. + isDiskArbitrationAPIRefType(T); } diff --git a/lib/Analysis/Consumed.cpp b/lib/Analysis/Consumed.cpp index f6fe78ac4619c..96edad0c3019f 100644 --- a/lib/Analysis/Consumed.cpp +++ b/lib/Analysis/Consumed.cpp @@ -22,7 +22,7 @@ #include "clang/AST/StmtVisitor.h" #include "clang/AST/Type.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "clang/Basic/OperatorKinds.h" #include "clang/Basic/SourceLocation.h" @@ -749,8 +749,7 @@ void ConsumedStmtVisitor::VisitCallExpr(const CallExpr *Call) { // Special case for the std::move function. // TODO: Make this more specific. (Deferred) - if (Call->getNumArgs() == 1 && FunDecl->getNameAsString() == "move" && - FunDecl->isInStdNamespace()) { + if (Call->isCallToStdMove()) { copyInfo(Call->getArg(0), Call, CS_Consumed); return; } diff --git a/lib/Analysis/LiveVariables.cpp b/lib/Analysis/LiveVariables.cpp index cd73a62e6918c..4752c2b020aea 100644 --- a/lib/Analysis/LiveVariables.cpp +++ b/lib/Analysis/LiveVariables.cpp @@ -15,7 +15,7 @@ #include "clang/AST/Stmt.h" #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PostOrderIterator.h" diff --git a/lib/Analysis/PrintfFormatString.cpp b/lib/Analysis/PrintfFormatString.cpp index 50a3aa20bd195..dfaed26564e6f 100644 --- a/lib/Analysis/PrintfFormatString.cpp +++ b/lib/Analysis/PrintfFormatString.cpp @@ -505,9 +505,7 @@ ArgType PrintfSpecifier::getArgType(ASTContext &Ctx, ? ArgType(Ctx.UnsignedLongLongTy, "unsigned __int64") : ArgType(Ctx.UnsignedIntTy, "unsigned __int32"); case LengthModifier::AsPtrDiff: - // FIXME: How to get the corresponding unsigned - // version of ptrdiff_t? - return ArgType(); + return ArgType(Ctx.getUnsignedPointerDiffType(), "unsigned ptrdiff_t"); case LengthModifier::AsAllocate: case LengthModifier::AsMAllocate: case LengthModifier::AsWide: @@ -654,6 +652,7 @@ bool PrintfSpecifier::fixType(QualType QT, const LangOptions &LangOpt, case BuiltinType::UInt128: case BuiltinType::Int128: case BuiltinType::Half: + case BuiltinType::Float16: case BuiltinType::Float128: // Various types which are non-trivial to correct. return false; diff --git a/lib/Analysis/ReachableCode.cpp b/lib/Analysis/ReachableCode.cpp index 60724ea60b25a..7e72795a47f69 100644 --- a/lib/Analysis/ReachableCode.cpp +++ b/lib/Analysis/ReachableCode.cpp @@ -18,7 +18,7 @@ #include "clang/AST/ExprObjC.h" #include "clang/AST/ParentMap.h" #include "clang/AST/StmtCXX.h" -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "clang/Basic/SourceManager.h" #include "clang/Lex/Preprocessor.h" diff --git a/lib/Analysis/ScanfFormatString.cpp b/lib/Analysis/ScanfFormatString.cpp index 534225985460b..8398a4b82d5a3 100644 --- a/lib/Analysis/ScanfFormatString.cpp +++ b/lib/Analysis/ScanfFormatString.cpp @@ -251,8 +251,7 @@ ArgType ScanfSpecifier::getArgType(ASTContext &Ctx) const { case LengthModifier::AsIntMax: return ArgType::PtrTo(ArgType(Ctx.getIntMaxType(), "intmax_t")); case LengthModifier::AsSizeT: - // FIXME: ssize_t. - return ArgType(); + return ArgType::PtrTo(ArgType(Ctx.getSignedSizeType(), "ssize_t")); case LengthModifier::AsPtrDiff: return ArgType::PtrTo(ArgType(Ctx.getPointerDiffType(), "ptrdiff_t")); case LengthModifier::AsLongDouble: @@ -292,8 +291,8 @@ ArgType ScanfSpecifier::getArgType(ASTContext &Ctx) const { case LengthModifier::AsSizeT: return ArgType::PtrTo(ArgType(Ctx.getSizeType(), "size_t")); case LengthModifier::AsPtrDiff: - // FIXME: Unsigned version of ptrdiff_t? - return ArgType(); + return ArgType::PtrTo( + ArgType(Ctx.getUnsignedPointerDiffType(), "unsigned ptrdiff_t")); case LengthModifier::AsLongDouble: // GNU extension. return ArgType::PtrTo(Ctx.UnsignedLongLongTy); @@ -386,7 +385,7 @@ ArgType ScanfSpecifier::getArgType(ASTContext &Ctx) const { case LengthModifier::AsIntMax: return ArgType::PtrTo(ArgType(Ctx.getIntMaxType(), "intmax_t")); case LengthModifier::AsSizeT: - return ArgType(); // FIXME: ssize_t + return ArgType::PtrTo(ArgType(Ctx.getSignedSizeType(), "ssize_t")); case LengthModifier::AsPtrDiff: return ArgType::PtrTo(ArgType(Ctx.getPointerDiffType(), "ptrdiff_t")); case LengthModifier::AsLongDouble: diff --git a/lib/Analysis/ThreadSafety.cpp b/lib/Analysis/ThreadSafety.cpp index 879a15c9c2a8e..6a9c9a04c55d1 100644 --- a/lib/Analysis/ThreadSafety.cpp +++ b/lib/Analysis/ThreadSafety.cpp @@ -26,7 +26,7 @@ #include "clang/Analysis/Analyses/ThreadSafetyLogical.h" #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/CFGStmtMap.h" #include "clang/Basic/OperatorKinds.h" @@ -1735,8 +1735,23 @@ void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) { CapExprSet AssertLocks; Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); for (const auto &AssertLock : AssertLocks) - Analyzer->addLock(FSet, llvm::make_unique<LockableFactEntry>( - AssertLock, LK_Shared, Loc, false, true), + Analyzer->addLock(FSet, + llvm::make_unique<LockableFactEntry>( + AssertLock, LK_Shared, Loc, false, true), + ClassifyDiagnostic(A)); + break; + } + + case attr::AssertCapability: { + AssertCapabilityAttr *A = cast<AssertCapabilityAttr>(At); + CapExprSet AssertLocks; + Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); + for (const auto &AssertLock : AssertLocks) + Analyzer->addLock(FSet, + llvm::make_unique<LockableFactEntry>( + AssertLock, + A->isShared() ? LK_Shared : LK_Exclusive, Loc, + false, true), ClassifyDiagnostic(A)); break; } diff --git a/lib/Analysis/ThreadSafetyCommon.cpp b/lib/Analysis/ThreadSafetyCommon.cpp index cbd5464c34d7c..99284f07b45b3 100644 --- a/lib/Analysis/ThreadSafetyCommon.cpp +++ b/lib/Analysis/ThreadSafetyCommon.cpp @@ -19,7 +19,7 @@ #include "clang/AST/StmtCXX.h" #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "clang/Basic/OperatorKinds.h" #include "clang/Basic/SourceLocation.h" @@ -319,11 +319,11 @@ static bool hasCppPointerType(const til::SExpr *E) { static const CXXMethodDecl *getFirstVirtualDecl(const CXXMethodDecl *D) { while (true) { D = D->getCanonicalDecl(); - CXXMethodDecl::method_iterator I = D->begin_overridden_methods(), - E = D->end_overridden_methods(); - if (I == E) + auto OverriddenMethods = D->overridden_methods(); + if (OverriddenMethods.begin() == OverriddenMethods.end()) return D; // Method does not override anything - D = *I; // FIXME: this does not work with multiple inheritance. + // FIXME: this does not work with multiple inheritance. + D = *OverriddenMethods.begin(); } return nullptr; } @@ -505,6 +505,7 @@ til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO, case BO_GE: return translateBinOp(til::BOP_Leq, BO, Ctx, true); case BO_EQ: return translateBinOp(til::BOP_Eq, BO, Ctx); case BO_NE: return translateBinOp(til::BOP_Neq, BO, Ctx); + case BO_Cmp: return translateBinOp(til::BOP_Cmp, BO, Ctx); case BO_And: return translateBinOp(til::BOP_BitAnd, BO, Ctx); case BO_Xor: return translateBinOp(til::BOP_BitXor, BO, Ctx); case BO_Or: return translateBinOp(til::BOP_BitOr, BO, Ctx); diff --git a/lib/Analysis/ThreadSafetyTIL.cpp b/lib/Analysis/ThreadSafetyTIL.cpp index 83aa90435e2a5..cd7cdc69ab73a 100644 --- a/lib/Analysis/ThreadSafetyTIL.cpp +++ b/lib/Analysis/ThreadSafetyTIL.cpp @@ -38,6 +38,7 @@ StringRef til::getBinaryOpcodeString(TIL_BinaryOpcode Op) { case BOP_Neq: return "!="; case BOP_Lt: return "<"; case BOP_Leq: return "<="; + case BOP_Cmp: return "<=>"; case BOP_LogicAnd: return "&&"; case BOP_LogicOr: return "||"; } diff --git a/lib/Analysis/UninitializedValues.cpp b/lib/Analysis/UninitializedValues.cpp index d5289fb9d4271..5f11d8a2a36b5 100644 --- a/lib/Analysis/UninitializedValues.cpp +++ b/lib/Analysis/UninitializedValues.cpp @@ -18,7 +18,7 @@ #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/Analyses/UninitializedValues.h" -#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" #include "llvm/ADT/DenseMap.h" @@ -440,16 +440,11 @@ static bool isPointerToConst(const QualType &QT) { void ClassifyRefs::VisitCallExpr(CallExpr *CE) { // Classify arguments to std::move as used. - if (CE->getNumArgs() == 1) { - if (FunctionDecl *FD = CE->getDirectCallee()) { - if (FD->isInStdNamespace() && FD->getIdentifier() && - FD->getIdentifier()->isStr("move")) { - // RecordTypes are handled in SemaDeclCXX.cpp. - if (!CE->getArg(0)->getType()->isRecordType()) - classify(CE->getArg(0), Use); - return; - } - } + if (CE->isCallToStdMove()) { + // RecordTypes are handled in SemaDeclCXX.cpp. + if (!CE->getArg(0)->getType()->isRecordType()) + classify(CE->getArg(0), Use); + return; } // If a value is passed by const pointer or by const reference to a function, |