Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -140,6 +140,10 @@ let ParentPackage = CoreAlpha in { +def StackSizeChecker : Checker<"StackSize">, + HelpText<"Warn if estimated stack usage exceeds the StackUsageLimit parameter (measured in bytes, defaults to 100000)">, + DescFile<"StackSizeChecker.cpp">; + def BoolAssignmentChecker : Checker<"BoolAssignment">, HelpText<"Warn about assigning non-{0,1} values to Boolean variables">, DescFile<"BoolAssignmentChecker.cpp">; Index: include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h =================================================================== --- /dev/null +++ include/clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h @@ -0,0 +1,144 @@ +//==-- StackUsageMeasuringVisitor.h -------------------------------*- C++ -*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares the StackUsageMeasuringVisitor, a RecursiveASTVisitor +// based class for summarizing the stack usage of statement trees. +// It can calculate the complete usage of a tree or only a subtree up to +// the point where the given predicate becomes true. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/DenseMap.h" + +#include "clang/AST/ASTConsumer.h" +#include "clang/AST/RecursiveASTVisitor.h" +#include "clang/Frontend/CompilerInstance.h" +#include "clang/Frontend/FrontendAction.h" +#include "clang/Tooling/Tooling.h" +#include +#include + +namespace clang { +namespace stack { + +struct Usage { + + Usage &operator+=(const Usage &U); + + bool operator==(const Usage &U) const { + return Constant == U.Constant && Maximal == U.Maximal && + DynAlloc == U.DynAlloc && ExitFlag == U.ExitFlag; + } + + int Constant; // The amount of used space that survives the statement, + // important for variable declarations and temporaries extended + // by const references. + int Maximal; // Greater or equal to 'Constant', includes temporaries created + // by the statement. + bool DynAlloc; // Flag for dynamic stack allocation in the statement or any of + // its children. + bool ExitFlag; // Tells the visitor to cease consuming the tree. + + static const Usage Empty, EmptyFlagged; +}; + +class StackUsageMeasuringVisitor + : public clang::RecursiveASTVisitor { + +public: + using Predicate = std::function; + + explicit StackUsageMeasuringVisitor(ASTContext &Context) + : Context(Context), ContinueTraversing(true), ExitFlag(false), + HardExit(false), ForceTemporariesToConstant(false), + ExitPredicate(nullptr) {} + + Usage collected() const; + + // The visitor should traver post-order, because each node needs + // precalculated information in their children. + bool shouldTraversePostOrder() const { return true; } + + bool VisitStmt(const Stmt *); + + bool VisitDeclStmt(const DeclStmt *); + bool VisitExpr(const Expr *); + bool VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *); + bool VisitLambdaExpr(const LambdaExpr *); + bool VisitCXXThrowExpr(const CXXThrowExpr *); + bool VisitArraySubscriptExpr(const ArraySubscriptExpr *); + bool VisitCompoundStmt(const CompoundStmt *); + bool VisitIfStmt(const IfStmt *); + bool VisitSwitchStmt(const SwitchStmt *); + bool VisitForStmt(const ForStmt *); + bool VisitCXXForRangeStmt(const CXXForRangeStmt *); + bool VisitWhileStmt(const WhileStmt *); + bool VisitDoStmt(const DoStmt *); + bool VisitCXXTryStmt(const CXXTryStmt *); + bool VisitReturnStmt(const ReturnStmt *); + bool VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *); + bool VisitVarDecl(const VarDecl *); + + Usage calculateFunctionUsage(const FunctionDecl *, Predicate, bool); + Usage sumFunctionUpUntil(const FunctionDecl *, const Stmt *); + Usage sumFunctionUpUntilTemplate(const FunctionDecl *); + Usage sumStmtWithTemporariesExtracted(const Stmt *); + Usage sumStmt(const Stmt *, Predicate, bool, bool); +private: + void clear(); + bool hasUsageStored(const Stmt *S) const { + return StmtSubtreeUsages.find(S) != StmtSubtreeUsages.end(); + } + bool hasUsageStored(const Decl *D) const { + return DeclSubtreeUsages.find(D) != DeclSubtreeUsages.end(); + } + + bool hasEmptyFlaggedUsageStored(const Stmt *S) const { + auto iter = StmtSubtreeUsages.find(S); + return iter != StmtSubtreeUsages.end() && + iter->second == Usage::EmptyFlagged; + } + bool hasEmptyFlaggedUsageStored(const Decl *D) const { + auto iter = DeclSubtreeUsages.find(D); + return iter != DeclSubtreeUsages.end() && + iter->second == Usage::EmptyFlagged; + } + void putUsage(const Stmt *, Usage); + Usage retrieveUsage(const Stmt *) const; + void putUsage(const Decl *, Usage); + Usage retrieveUsage(const Decl *) const; + + int varSize(const VarDecl *Var) const { + return Var->hasLocalStorage() * sizeInBytes(Var->getType()); + } + + int sizeInBytes(QualType T) const { + return T->isIncompleteType() || T->isPlaceholderType() + ? 0 + : Context.getTypeSize(T) / Context.getCharWidth(); + } + int exprRetSize(const Expr *) const; + + ASTContext &Context; + + llvm::DenseMap StmtSubtreeUsages; + llvm::DenseMap DeclSubtreeUsages; + + Stmt* rootStmt; + + bool ContinueTraversing; + bool ExitFlag; + bool HardExit; + bool ForceTemporariesToConstant; + + Predicate ExitPredicate; +}; + +} // stack +} // clang Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -83,6 +83,7 @@ RunLoopAutoreleaseLeakChecker.cpp SimpleStreamChecker.cpp StackAddrEscapeChecker.cpp + StackSizeChecker.cpp StdLibraryFunctionsChecker.cpp StreamChecker.cpp TaintTesterChecker.cpp Index: lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Checkers/StackSizeChecker.cpp @@ -0,0 +1,159 @@ +//=======- StackSizeChecker.cpp ----------------------------------*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a checker that checks for suspiciously high stack use. +// The checker produces a warning whenever the given stack limit is exceeded. +// The limit is defined by the "StackUsageLimit" analyzer parameter, +// or defaults to 100000 bytes. +// +//===----------------------------------------------------------------------===// + +#include "ClangSACheckers.h" +#include "clang/AST/StmtCXX.h" +#include "clang/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.h" +#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" +#include + +using namespace clang; +using namespace clang::ento; + +namespace { + +struct StackInt { + int Used; + bool operator==(const StackInt &Other) const { return Used == Other.Used; } + void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Used); } + operator int() const { return Used; } +}; + +class StackSizeChecker + : public Checker { + mutable std::unique_ptr StackOverflowBugType; + + void generateError(int NumBytes, SourceRange Range, CheckerContext &C) const; + +public: + StackSizeChecker() : StackUsageLimit(0) {} + int StackUsageLimit; + + void checkPreCall(const CallEvent &Call, CheckerContext &C) const; + void checkPostCall(const CallEvent &Call, CheckerContext &C) const; + void checkEndFunction(CheckerContext &C) const; +}; + +int countPredecessors(const CheckerContext &C) { + const auto *Frame = C.getStackFrame()->getParent(); + int N = 0; + while (Frame) { + const auto *D = dyn_cast_or_null(Frame->getDecl()); + if (D) + ++N; + else + break; + Frame = dyn_cast_or_null(Frame->getParent()); + } + return N; +} + +int length(const llvm::ImmutableList& L) { + int N = 0; + auto I = L.begin(); + auto E = L.end(); + while(I != E){ + ++N; + ++I; + } + return N; +} +} + +REGISTER_LIST_WITH_PROGRAMSTATE(StackSizeList, StackInt) + +void StackSizeChecker::generateError(int NumBytes, SourceRange Range, + CheckerContext &C) const { + ExplodedNode *ErrNode = C.generateNonFatalErrorNode(); + // If we've already reached this node on another path, return. + if (!ErrNode) + return; + + if (!StackOverflowBugType) { + StackOverflowBugType.reset( + new BugType(this, "Stack overuse", "Program error")); + } + // Generate the report. + std::ostringstream ErrorMessage; + ErrorMessage << "Estimated stack usage is " << NumBytes << " bytes"; + auto R = llvm::make_unique(*StackOverflowBugType, + ErrorMessage.str(), ErrNode); + R->addRange(Range); + C.emitReport(std::move(R)); +} + +void StackSizeChecker::checkEndFunction(CheckerContext &C) const { + ProgramStateRef State = C.getState(); + auto StackLevels = State->get(); + if (length(StackLevels) != countPredecessors(C)) + return; + stack::StackUsageMeasuringVisitor Visitor(C.getASTContext()); + auto Declaration = + dyn_cast_or_null(C.getLocationContext()->getDecl()); + int NumBytes = + Visitor + .sumFunctionUpUntilTemplate(const_cast(Declaration)) + .Maximal; + if (!StackLevels.isEmpty()) + NumBytes += StackLevels.getHead(); + + if (NumBytes > StackUsageLimit) + generateError(NumBytes, Declaration->getSourceRange(), C); +} + +void StackSizeChecker::checkPreCall(const CallEvent &Call, + CheckerContext &C) const { + ProgramStateRef State = C.getState(); + auto StackLevels = State->get(); + if (length(StackLevels) != countPredecessors(C)) + return; + + stack::StackUsageMeasuringVisitor Visitor(C.getASTContext()); + + auto *Declaration = + dyn_cast_or_null(C.getLocationContext()->getDecl()); + int NumBytes = + Visitor.sumFunctionUpUntil(Declaration, Call.getOriginExpr()).Constant + + Visitor.sumStmtWithTemporariesExtracted(Call.getOriginExpr()).Constant; + if (!StackLevels.isEmpty()) + NumBytes += StackLevels.getHead(); + + if (NumBytes > StackUsageLimit) { + generateError(NumBytes, Call.getSourceRange(), C); + } + State = State->add({NumBytes}); + C.addTransition(State); +} + +void StackSizeChecker::checkPostCall(const CallEvent &Call, + CheckerContext &C) const { + ProgramStateRef State = C.getState(); + auto StackLevels = State->get(); + if (length(StackLevels) != countPredecessors(C) + 1) + return; + State = State->set(StackLevels.getTail()); + C.addTransition(State); +} + +void clang::ento::registerStackSizeChecker(CheckerManager &Mgr) { + StackSizeChecker *Check = Mgr.registerChecker(); + Check->StackUsageLimit = Mgr.getAnalyzerOptions().getOptionAsInteger( + "StackUsageLimit", 100000, Check); +} Index: lib/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Checkers/StackUsageMeasuringVisitor.cpp @@ -0,0 +1,477 @@ +//==-- StackUsageMeasuringVisitor.cpp -----------------------------*- C++ -*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the StackUsageMeasuringVisitor, a RecursiveASTVisitor +// based class for summarizing the stack usage of statement trees. +// It can calculate the complete usage of a tree or only a subtree up to +// the point where the given predicate becomes true. +// +//===----------------------------------------------------------------------===// + +#include + +namespace clang { +namespace stack { + +const Usage Usage::Empty = {0, 0, false, false}; +const Usage Usage::EmptyFlagged = {0, 0, false, true}; + +Usage &Usage::operator+=(const Usage &U) { + if (ExitFlag) + return *this; + Maximal = std::max(Maximal, Constant + U.Maximal); + Constant += U.Constant; + DynAlloc = DynAlloc || U.DynAlloc; + ExitFlag = ExitFlag || U.ExitFlag; + return *this; +} + +namespace { + +Usage withoutConstant(Usage U) { + return {0, U.Maximal, U.DynAlloc, U.ExitFlag}; +} + +bool countsAsZero(const Expr *Ex) { + auto Cls = Ex->getStmtClass(); + return Cls == Stmt::StmtClass::DeclRefExprClass || + Cls == Stmt::StmtClass::MemberExprClass || + Cls == Stmt::StmtClass::CharacterLiteralClass || + Cls == Stmt::StmtClass::CXXBoolLiteralExprClass || + Cls == Stmt::StmtClass::CXXNullPtrLiteralExprClass || + Cls == Stmt::StmtClass::FloatingLiteralClass || + Cls == Stmt::StmtClass::ImaginaryLiteralClass || + Cls == Stmt::StmtClass::IntegerLiteralClass || + Cls == Stmt::StmtClass::StringLiteralClass; +} + +bool isTypeDependent(const Stmt *S) { + if (const auto *E = dyn_cast(S)) { + return E->isTypeDependent(); + } + return false; +} +} + +void StackUsageMeasuringVisitor::putUsage(const Stmt *S, Usage U) { + if (U.ExitFlag) { + ExitFlag = true; + ContinueTraversing = !HardExit; + } + StmtSubtreeUsages[S] = U; +} + +Usage StackUsageMeasuringVisitor::retrieveUsage(const Stmt *S) const { + if (S == nullptr) + return Usage::Empty; + auto Iter = StmtSubtreeUsages.find(S); + if (Iter != StmtSubtreeUsages.end()) { + Usage U = Iter->second; + return U; + } else { + return Usage::Empty; + } +} + +void StackUsageMeasuringVisitor::clear() { + StmtSubtreeUsages.clear(); + DeclSubtreeUsages.clear(); + ExitFlag = false; + ContinueTraversing = true; +} + +void StackUsageMeasuringVisitor::putUsage(const Decl *D, Usage U) { + if (U.ExitFlag) { + ExitFlag = true; + ContinueTraversing = !HardExit; + } + DeclSubtreeUsages[D] = U; +} + +Usage StackUsageMeasuringVisitor::retrieveUsage(const Decl *D) const { + if (D == nullptr) + return Usage::Empty; + auto Iter = DeclSubtreeUsages.find(D); + if (Iter != DeclSubtreeUsages.end()) { + Usage U = Iter->second; + return U; + } else { + return Usage::Empty; + } +} + +int StackUsageMeasuringVisitor::exprRetSize(const Expr *E) const { + auto StmtCls = E->getStmtClass(); + // If it's a NoOp expression the returned value does not use extra space. + // Also constructors and 'ExprWithCleanups' expressions are assumed to have + // no extra return space costs. + if (E->IgnoreParenNoopCasts(Context) != E || + StmtCls == Stmt::StmtClass::ExprWithCleanupsClass || + StmtCls == Stmt::StmtClass::CXXConstructExprClass) { + return 0; + } + return sizeInBytes(E->isLValue() + ? Context.getLValueReferenceType(E->getType()) + : E->getType()); +} + +bool StackUsageMeasuringVisitor::VisitStmt(const Stmt *S) { + // This will flag the statement or expression if it is the desired one. + if (ExitPredicate(S)) { + putUsage(S, Usage::EmptyFlagged); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitDeclStmt(const DeclStmt *D) { + if (!hasEmptyFlaggedUsageStored(D)) { + Usage Summary = Usage::Empty; + // Summarize the variable declarations and their initializing expressions. + for (const auto *Dec : D->getDeclGroup()) { + Usage Var = retrieveUsage(Dec); + Summary += Var; + if (Var.ExitFlag) + break; + } + putUsage(D, Summary); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitVarDecl(const VarDecl *D) { + if (!hasEmptyFlaggedUsageStored(D)) { + if (D->isInvalidDecl()) { + // Invalid declarations count as zero. + putUsage(D, Usage::Empty); + } else if (D->getType()->isDependentType()) { + // A template declaration was found, signal the algorithm. + putUsage(D, Usage::EmptyFlagged); + } else { + int VarSize = varSize(D); + Usage Var = {VarSize, VarSize, D->getType()->isVariableArrayType(), + false}; + Usage Init = retrieveUsage(D->getInit()); + Init.Maximal -= VarSize * isa(D->getType()); + Var += Init; + putUsage(D, Var); + } + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitExpr(const Expr *Ex) { + if (!hasEmptyFlaggedUsageStored(Ex)) { + Usage Summary = Usage::Empty; + if (!countsAsZero(Ex)) { + for (const auto &Child : Ex->children()) { + // The way we summarize the subexpressions is special here, + // because all of the temporary objects remain until the end of the + // execution of the whole line. + Usage U = retrieveUsage(Child); + Summary.Constant += U.Constant; + Summary.Maximal += U.Maximal; + Summary.DynAlloc = Summary.DynAlloc || U.DynAlloc; + Summary.ExitFlag = Summary.ExitFlag || U.ExitFlag; + if (Summary.ExitFlag) + break; + } + Summary.Maximal += exprRetSize(Ex); + } + putUsage(Ex, Summary); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitMaterializeTemporaryExpr( + const MaterializeTemporaryExpr *Ex) { + if (!hasEmptyFlaggedUsageStored(Ex)) { + // We have a temporary object whose lifetime may be extended by a constant + // reference. + auto *Temporary = Ex->GetTemporaryExpr(); + + Usage U = retrieveUsage(Temporary); + if (ForceTemporariesToConstant) { + // In this case, we force all the temporaries into the constant usage + // if they are not held by static references. This way of calculation + // is useful for summarizing an expression locally. + int Constant = + (Ex->getStorageDuration() != SD_Static) * + sizeInBytes(Temporary->IgnoreParenNoopCasts(Context)->getType()); + U.Constant += Constant; + } else { + // Usually we count constant usage only if there is a non-static variable + // declaration that keeps the temporary alive. + int Constant = + (Ex->getExtendingDecl() && Ex->getStorageDuration() != SD_Static) + ? exprRetSize(Temporary) + : 0; + U.Constant += Constant; + } + U.Maximal = std::max(U.Maximal, U.Constant); + putUsage(Ex, U); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitLambdaExpr(const LambdaExpr *Ex) { + if (!hasEmptyFlaggedUsageStored(Ex)) { + // In this case we are only interested in the result type, + // the body is checked as a separate function by the checker. + int Result = exprRetSize(Ex); + putUsage(Ex, {0, Result, false, false}); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitCXXThrowExpr(const CXXThrowExpr *Ex) { + if (!hasEmptyFlaggedUsageStored(Ex)) { + // We assume no 'constant' stack usage here. + Usage Sub = retrieveUsage(Ex->getSubExpr()); + putUsage(Ex, {0, Sub.Maximal, Sub.DynAlloc, Sub.ExitFlag}); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitArraySubscriptExpr( + const ArraySubscriptExpr *Ex) { + if (!hasEmptyFlaggedUsageStored(Ex)) { + // We assume no extra usage for array elements, but the way the are reached + // may create extra usage. + Usage Base = retrieveUsage(Ex->getBase()); + Usage Idx = retrieveUsage(Ex->getIdx()); + putUsage(Ex, {Base.Constant + Idx.Constant, Base.Maximal + Idx.Maximal, + Base.DynAlloc || Idx.DynAlloc, Idx.ExitFlag}); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitCompoundStmt(const CompoundStmt *CS) { + if (!hasEmptyFlaggedUsageStored(CS)) { + // The 'Constant' usage adds up from all the children, + // the 'Maximal' usage is the maximum of all children values. + Usage Summary = Usage::Empty; + for (const auto *Child : CS->body()) { + Summary += retrieveUsage(Child); + if (Summary.ExitFlag) + break; + } + // All the compound statements except for the function body have + // zero constant usage. In the function body constant usage can be + // used for partial summaries. + if (CS != rootStmt) + Summary.Constant = 0; + putUsage(CS, Summary); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitIfStmt(const IfStmt *If) { + if (!hasEmptyFlaggedUsageStored(If)) { + // The variables declared in the condition field exist during the execution + // of the chosen branch, but only one of the branches get executed, + // so we take the maximal one and add the condition. + // We also have to take into account the ExitFlags of the branches, so if + // a branch has less usage but is flagged, it must be the one we use. + Usage IfUsage = retrieveUsage(If->getInit()); + const DeclStmt *Decl = If->getConditionVariableDeclStmt(); + IfUsage += Decl ? retrieveUsage(Decl) : retrieveUsage(If->getCond()); + + Usage ThenUs = retrieveUsage(If->getThen()); + Usage ElseUs = retrieveUsage(If->getElse()); + // We have to choose the branch that has greater maximal usage or is + // flagged. + if (ThenUs.ExitFlag || + (!ElseUs.ExitFlag && ThenUs.Maximal > ElseUs.Maximal)) { + IfUsage += ThenUs; + } else { + IfUsage += ElseUs; + } + putUsage(If, withoutConstant(IfUsage)); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitSwitchStmt(const SwitchStmt *S) { + if (!hasEmptyFlaggedUsageStored(S)) { + // The the condition variable is handled like in the if statement, + // the body is treated as one big compound statement, + // since we are mainly interested in the maximal usage and declarations + // can't be case specific or they exist in substatements, + // where they go into the maximal usage. + Usage SwitchUsage = retrieveUsage(S->getInit()); + const DeclStmt *Decl = S->getConditionVariableDeclStmt(); + + SwitchUsage += Decl ? retrieveUsage(Decl) : retrieveUsage(S->getCond()); + SwitchUsage += retrieveUsage(S->getBody()); + + putUsage(S, withoutConstant(SwitchUsage)); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitForStmt(const ForStmt *For) { // TODO + if (!hasEmptyFlaggedUsageStored(For)) { + // From the head only the loop variable exists during the execution of the + // body, but the subexpressions in the condition and the increment fields + // may affect the maximal usage. + Usage ForUsage = retrieveUsage(For->getInit()); + + const DeclStmt *Decl = For->getConditionVariableDeclStmt(); + ForUsage += Decl ? retrieveUsage(Decl) : retrieveUsage(For->getCond()); + ForUsage += retrieveUsage(For->getInc()); + ForUsage += retrieveUsage(For->getBody()); + + putUsage(For, withoutConstant(ForUsage)); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitCXXForRangeStmt( + const CXXForRangeStmt *For) { + if (!hasEmptyFlaggedUsageStored(For)) { + // Similar logic to the for statement, every hidden declaration is + // taken into account. + Usage ForRangeUsage = retrieveUsage(For->getLoopVarStmt()); + ForRangeUsage += retrieveUsage(For->getBeginStmt()); + ForRangeUsage += retrieveUsage(For->getEndStmt()); + ForRangeUsage += retrieveUsage(For->getBody()); + ForRangeUsage += retrieveUsage(For->getInc()); + ForRangeUsage += retrieveUsage(For->getRangeStmt()); + + putUsage(For, withoutConstant(ForRangeUsage)); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitWhileStmt(const WhileStmt *While) { + if (!hasEmptyFlaggedUsageStored(While)) { + // Similar logic to the for statement, head and body handled according to + // lifetime rules. + Usage WhileUsage = retrieveUsage(While->getCond()); + WhileUsage += retrieveUsage(While->getBody()); + + putUsage(While, withoutConstant(WhileUsage)); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitDoStmt(const DoStmt *DoWhile) { + if (!hasEmptyFlaggedUsageStored(DoWhile)) { + // Similar logic to the while statment, but taking into account that + // the lifetime of the variables in the body end before the condition + Usage DoWhileUsage = withoutConstant(retrieveUsage(DoWhile->getBody())); + DoWhileUsage += withoutConstant(retrieveUsage(DoWhile->getCond())); + putUsage(DoWhile, DoWhileUsage); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitCXXTryStmt(const CXXTryStmt *Try) { + if (!hasEmptyFlaggedUsageStored(Try)) { + // The maximal usage is calculated between try and except blocks. + // Try block allocations are assumed to be cleared before the execution of + // any handlers. + + // Function bodies can be try statements. If this is the body, it needs + // constant usage statistic in case we do a partial summary. + bool isRootStmt = rootStmt == Try; + Usage TryUsage = isRootStmt + ? retrieveUsage(Try->getTryBlock()) + : withoutConstant(retrieveUsage(Try->getTryBlock())); + + for (unsigned i = 0; i < Try->getNumHandlers() && !TryUsage.ExitFlag; ++i) { + auto Dec = Try->getHandler(i)->getExceptionDecl(); + int Hdecl = Dec ? varSize(Dec) : 0; + Usage HandlerBodyUsage = + isRootStmt ? retrieveUsage(Try->getHandler(i)->getHandlerBlock()) + : withoutConstant(retrieveUsage( + Try->getHandler(i)->getHandlerBlock())); + HandlerBodyUsage.Maximal += Hdecl; + TryUsage += HandlerBodyUsage; + } + putUsage(Try, TryUsage); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitReturnStmt(const ReturnStmt *Return) { + if (!hasEmptyFlaggedUsageStored(Return)) { + putUsage(Return, retrieveUsage(Return->getRetValue())); + } + return ContinueTraversing; +} + +bool StackUsageMeasuringVisitor::VisitUnaryExprOrTypeTraitExpr( + const UnaryExprOrTypeTraitExpr *Ex) { + if (!hasEmptyFlaggedUsageStored(Ex) && Ex->getKind() == UETT_SizeOf) { + // The sizeof expression is special case where the children are not + // evaluated during execution. + Usage Returned = Usage::Empty; + Returned.Maximal = exprRetSize(Ex); + Returned.Constant = 0; + Returned.ExitFlag = retrieveUsage(Ex).ExitFlag; + putUsage(Ex, Returned); + } + // Other cases are handled by the generic Expr branch. + return ContinueTraversing; +} + +Usage StackUsageMeasuringVisitor::sumStmt(const Stmt *S, Predicate ExitPred, + bool Hard, + bool ForceTempsToConstant) { + HardExit = Hard; + ForceTemporariesToConstant = ForceTempsToConstant; + clear(); + ExitPredicate = ExitPred; + TraverseStmt(const_cast(S)); + auto U = hasUsageStored(S) ? retrieveUsage(S) : Usage::EmptyFlagged; + return U; +} + +Usage StackUsageMeasuringVisitor::calculateFunctionUsage( + const FunctionDecl *Func, Predicate ExitPred, bool Hard) { + if (!Func || + Func->getTemplatedKind() != FunctionDecl::TemplatedKind::TK_NonTemplate || + Func->isPure() || !Func->hasBody()) + return Usage::EmptyFlagged; + int SizeCounter = 0; + for (const auto *Param : Func->parameters()) { + // It is no use calculating usage on templates. + if (Param->getType()->isDependentType()) + return Usage::EmptyFlagged; + int ParamSize = sizeInBytes(Param->getType()); + SizeCounter += ParamSize; + } + // then check the body. + auto *Body = Func->getBody(); + rootStmt = Body; + Usage Us = sumStmt(Body, ExitPred, Hard, false); + Us.Maximal += SizeCounter; + Us.Constant += SizeCounter; + return Us; +} + +Usage StackUsageMeasuringVisitor::sumFunctionUpUntil(const FunctionDecl *Func, + const Stmt *Particular) { + return calculateFunctionUsage( + Func, [Particular](const Stmt *S) { return S == Particular; }, false); +} + +Usage StackUsageMeasuringVisitor::sumFunctionUpUntilTemplate( + const FunctionDecl *Func) { + return calculateFunctionUsage(Func, isTypeDependent, true); +} + +Usage StackUsageMeasuringVisitor::sumStmtWithTemporariesExtracted( + const Stmt *S) { + return sumStmt(S, isTypeDependent, false, true); +} + +} // stack +} // clang Index: test/Analysis/stack-size-callchain.cpp =================================================================== --- /dev/null +++ test/Analysis/stack-size-callchain.cpp @@ -0,0 +1,22 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.core.StackSize -analyzer-config alpha.core.StackSize:StackUsageLimit=200 -std=c++11 -triple x86_64-unknown-linux-gnu -verify %s + +// The checker accumulates variables from each level of the call chain. +// In this case from function 'c' to 'a' each body has 10 long integers +// on the stack, which accumulates to 30 * 8 = 240 bytes. + +void function_a() { + long A[10]; // expected-warning {{Estimated stack usage is 240 bytes}} +} + +void function_b() { + long B1[10]; + function_a(); + long B2[5]; +} + +void function_c() { + long C1[10]; + function_b(); + long C2[5]; +} + Index: test/Analysis/stack-size.cpp =================================================================== --- /dev/null +++ test/Analysis/stack-size.cpp @@ -0,0 +1,59 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.core.StackSize -analyzer-config alpha.core.StackSize:StackUsageLimit=1 -std=c++11 -triple x86_64-unknown-linux-gnu -verify %s + +// In this test an integer is 4 bytes, a bool is 1 byte. +// The analysis uses the same method of calculation as the misc-stack-size +// checker in clang-tidy. +// (see clang-tools-extra/test/clang-tidy/misc-stack-size.cpp for examples) + +// If a call happens in a function body, the stack space used by the function +// will be registered as the space used up until that point. Each time the +// execution of a function body is completely finished, the maximal amount +// of space used is estimated and checked against the limit. + +// This function gets called multiple times. The space used is varying each time. +int f(int X) { return X; } // expected-warning {{Estimated stack usage is 8 bytes}} + // expected-warning@-1 {{Estimated stack usage is 12 bytes}} + +// This function illustrates the partial summation ability. +// Before each call, the stack usage at that point is registered, +// so it can be added to the statistics of the called function. +void linear() { + int X = 1; + f(X); // expected-warning {{Estimated stack usage is 4 bytes}} + int Y = 2; + f(Y); // expected-warning {{Estimated stack usage is 8 bytes}} +} // expected-warning {{Estimated stack usage is 20 bytes}} + +// This function shows the ability of this checker to calculate with recursion +// far as the analyzer follows it. +void recursion(int N) { + int X; + + if (N <= 0) + return; // expected-warning {{Estimated stack usage is 44 bytes}} + + recursion(N - 1); // expected-warning {{Estimated stack usage is 8 bytes}} + // expected-warning@-1 {{Estimated stack usage is 16 bytes}} + // expected-warning@-2 {{Estimated stack usage is 24 bytes}} + // expected-warning@-3 {{Estimated stack usage is 20 bytes}} + // expected-warning@-4 {{Estimated stack usage is 28 bytes}} + // expected-warning@-5 {{Estimated stack usage is 36 bytes}} +} + +// This is only included so recursion is called by the analyzer. +void call_recursion() { + recursion(3); +} // expected-warning {{Estimated stack usage is 8 bytes}} + +void simple_branching() { + int A = 1; + if (A < 2) { + f(A); // expected-warning {{Estimated stack usage is 4 bytes}} + } else { + //This branch is not executed so we do not get warnings here. + f(2 * A); + } + // We do get the maximal usage calculated with the never executed branch + // included. +} // expected-warning {{Estimated stack usage is 20 bytes}} +