From 72905cfa81cfd126f322c4173f56d332aac5539e Mon Sep 17 00:00:00 2001 From: Jordy Rose Date: Wed, 4 Aug 2010 07:10:57 +0000 Subject: [PATCH] Change the checker callback cache in GRExprEngine to be more compact (and IMHO a little easier to understand), and add the same sort of caching for EvalAssume (tied for least-used callback), mostly as proof-of-concept. Before we go further with these, we should figure out a way to reuse the visit-and-cache code in CheckerVisit. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@110191 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Checker/PathSensitive/Checker.h | 3 +- .../Checker/PathSensitive/GRExprEngine.h | 23 ++++- lib/Checker/GRExprEngine.cpp | 89 +++++++++++++------ lib/Checker/MallocChecker.cpp | 6 +- 4 files changed, 89 insertions(+), 32 deletions(-) diff --git a/include/clang/Checker/PathSensitive/Checker.h b/include/clang/Checker/PathSensitive/Checker.h index d254071bdf..1c9f85b937 100644 --- a/include/clang/Checker/PathSensitive/Checker.h +++ b/include/clang/Checker/PathSensitive/Checker.h @@ -279,7 +279,8 @@ public: } virtual const GRState *EvalAssume(const GRState *state, SVal Cond, - bool Assumption) { + bool Assumption, bool *respondsToCallback) { + *respondsToCallback = false; return state; } diff --git a/include/clang/Checker/PathSensitive/GRExprEngine.h b/include/clang/Checker/PathSensitive/GRExprEngine.h index ffdf9de049..f7b7d7012a 100644 --- a/include/clang/Checker/PathSensitive/GRExprEngine.h +++ b/include/clang/Checker/PathSensitive/GRExprEngine.h @@ -75,10 +75,25 @@ class GRExprEngine : public GRSubEngine { llvm::OwningPtr BatchAuditor; + enum CallbackKind { + PreVisitStmtCallback, + PostVisitStmtCallback, + ProcessAssumeCallback + }; + + typedef uint32_t CallbackTag; + + /// GetCallbackTag - Create a tag for a certain kind of callback. The 'Sub' + /// argument can be used to differentiate callbacks that depend on another + /// value from a small set of possibilities, such as statement classes. + static inline CallbackTag GetCallbackTag(CallbackKind K, uint32_t Sub = 0) { + assert(Sub == ((Sub << 8) >> 8) && "Tag sub-kind must fit into 24 bits"); + return K | (Sub << 8); + } + typedef llvm::DenseMap CheckerMap; typedef std::vector > CheckersOrdered; - typedef llvm::DenseMap, CheckersOrdered *> - CheckersOrderedCache; + typedef llvm::DenseMap CheckersOrderedCache; /// A registration map from checker tag to the index into the /// ordered checkers vector. @@ -89,7 +104,7 @@ class GRExprEngine : public GRSubEngine { CheckersOrdered Checkers; /// A map used for caching the checkers that respond to the callback for - /// a particular statement and visitation order. + /// a particular callback tag. CheckersOrderedCache COCache; /// The BugReporter associated with this engine. It is important that @@ -258,7 +273,7 @@ public: /// CheckerVisit - Dispatcher for performing checker-specific logic /// at specific statements. void CheckerVisit(const Stmt *S, ExplodedNodeSet &Dst, ExplodedNodeSet &Src, - bool isPrevisit); + CallbackKind Kind); bool CheckerEvalCall(const CallExpr *CE, ExplodedNodeSet &Dst, diff --git a/lib/Checker/GRExprEngine.cpp b/lib/Checker/GRExprEngine.cpp index 7f8bb9b0cf..c6551e604d 100644 --- a/lib/Checker/GRExprEngine.cpp +++ b/lib/Checker/GRExprEngine.cpp @@ -170,16 +170,17 @@ public: //===----------------------------------------------------------------------===// void GRExprEngine::CheckerVisit(const Stmt *S, ExplodedNodeSet &Dst, - ExplodedNodeSet &Src, bool isPrevisit) { + ExplodedNodeSet &Src, CallbackKind Kind) { // Determine if we already have a cached 'CheckersOrdered' vector - // specifically tailored for the provided . This + // specifically tailored for the provided . This // can reduce the number of checkers actually called. CheckersOrdered *CO = &Checkers; llvm::OwningPtr NewCO; - - const std::pair &K = - std::make_pair((unsigned)S->getStmtClass(), isPrevisit ? 1U : 0U); + + // The cache key is made up of the and the callback kind (pre- or post-visit) + // and the statement kind. + CallbackTag K = GetCallbackTag(Kind, S->getStmtClass()); CheckersOrdered *& CO_Ref = COCache[K]; @@ -219,8 +220,8 @@ void GRExprEngine::CheckerVisit(const Stmt *S, ExplodedNodeSet &Dst, for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end(); NI != NE; ++NI) { - checker->GR_Visit(*CurrSet, *Builder, *this, S, *NI, tag, isPrevisit, - respondsToCallback); + checker->GR_Visit(*CurrSet, *Builder, *this, S, *NI, tag, + Kind == PreVisitStmtCallback, respondsToCallback); } @@ -500,15 +501,53 @@ const GRState* GRExprEngine::getInitialState(const LocationContext *InitLoc) { /// logic for handling assumptions on symbolic values. const GRState *GRExprEngine::ProcessAssume(const GRState *state, SVal cond, bool assumption) { - for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end(); - I != E; ++I) { + // Determine if we already have a cached 'CheckersOrdered' vector + // specifically tailored for processing assumptions. This + // can reduce the number of checkers actually called. + CheckersOrdered *CO = &Checkers; + llvm::OwningPtr NewCO; - if (!state) - return NULL; + CallbackTag K = GetCallbackTag(ProcessAssumeCallback); + CheckersOrdered *& CO_Ref = COCache[K]; + + if (!CO_Ref) { + // If we have no previously cached CheckersOrdered vector for this + // statement kind, then create one. + NewCO.reset(new CheckersOrdered); + } + else { + // Use the already cached set. + CO = CO_Ref; + } + + if (!CO->empty()) { + // Let the checkers have a crack at the assume before the transfer functions + // get their turn. + for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end(); + I != E; ++I) { + + // If any checker declares the state infeasible (or if it starts that + // way), bail out. + if (!state) + return NULL; + + Checker *C = I->second; + bool respondsToCallback = true; + + state = C->EvalAssume(state, cond, assumption, &respondsToCallback); + + // Check if we're building the cache of checkers that care about Assumes. + if (NewCO.get() && respondsToCallback) + NewCO->push_back(*I); + } - state = I->second->EvalAssume(state, cond, assumption); + // If we got through all the checkers, and we built a list of those that + // care about Assumes, save it. + if (NewCO.get()) + CO_Ref = NewCO.take(); } + // If the state is infeasible at this point, bail out. if (!state) return NULL; @@ -1563,7 +1602,7 @@ void GRExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred, ProgramPoint::PostLValueKind); // Post-visit the BlockExpr. - CheckerVisit(BE, Dst, Tmp, false); + CheckerVisit(BE, Dst, Tmp, PostVisitStmtCallback); } void GRExprEngine::VisitDeclRefExpr(const DeclRefExpr *Ex, ExplodedNode *Pred, @@ -1647,7 +1686,7 @@ void GRExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr* A, Visit(Idx, *I1, Tmp2); // Evaluate the index. ExplodedNodeSet Tmp3; - CheckerVisit(A, Tmp3, Tmp2, true); + CheckerVisit(A, Tmp3, Tmp2, PreVisitStmtCallback); for (ExplodedNodeSet::iterator I2=Tmp3.begin(),E2=Tmp3.end();I2!=E2; ++I2) { const GRState* state = GetState(*I2); @@ -1974,7 +2013,7 @@ void GRExprEngine::VisitCall(const CallExpr* CE, ExplodedNode* Pred, ExplodedNodeSet DstTmp2; Visit(Callee, *NI, DstTmp2); // Perform the previsit of the CallExpr, storing the results in DstTmp. - CheckerVisit(CE, DstTmp, DstTmp2, true); + CheckerVisit(CE, DstTmp, DstTmp2, PreVisitStmtCallback); } // Finally, evaluate the function call. We try each of the checkers @@ -2029,7 +2068,7 @@ void GRExprEngine::VisitCall(const CallExpr* CE, ExplodedNode* Pred, // If the callee returns a reference and we want an rvalue, skip this check // and do the load. if (!(!asLValue && CalleeReturnsReference(CE))) { - CheckerVisit(CE, Dst, DstTmp3, false); + CheckerVisit(CE, Dst, DstTmp3, PostVisitStmtCallback); return; } @@ -2039,7 +2078,7 @@ void GRExprEngine::VisitCall(const CallExpr* CE, ExplodedNode* Pred, // FIXME: This conversion doesn't actually happen unless the result // of CallExpr is consumed by another expression. ExplodedNodeSet DstTmp4; - CheckerVisit(CE, DstTmp4, DstTmp3, false); + CheckerVisit(CE, DstTmp4, DstTmp3, PostVisitStmtCallback); QualType LoadTy = CE->getType(); static int *ConvertToRvalueTag = 0; @@ -2283,7 +2322,7 @@ void GRExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr* ME, // Now that the arguments are processed, handle the previsits checks. ExplodedNodeSet DstPrevisit; - CheckerVisit(ME, DstPrevisit, ArgsEvaluated, true); + CheckerVisit(ME, DstPrevisit, ArgsEvaluated, PreVisitStmtCallback); // Proceed with evaluate the message expression. ExplodedNodeSet DstEval; @@ -2386,7 +2425,7 @@ void GRExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr* ME, // Finally, perform the post-condition check of the ObjCMessageExpr and store // the created nodes in 'Dst'. if (!(!asLValue && ReceiverReturnsReference(ME))) { - CheckerVisit(ME, Dst, DstEval, false); + CheckerVisit(ME, Dst, DstEval, PostVisitStmtCallback); return; } @@ -2396,7 +2435,7 @@ void GRExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr* ME, // FIXME: This conversion doesn't actually happen unless the result // of ObjCMessageExpr is consumed by another expression. ExplodedNodeSet DstRValueConvert; - CheckerVisit(ME, DstRValueConvert, DstEval, false); + CheckerVisit(ME, DstRValueConvert, DstEval, PostVisitStmtCallback); QualType LoadTy = ME->getType(); static int *ConvertToRvalueTag = 0; @@ -2429,7 +2468,7 @@ void GRExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, Visit(Ex, Pred, S1); ExplodedNodeSet S2; - CheckerVisit(CastE, S2, S1, true); + CheckerVisit(CastE, S2, S1, PreVisitStmtCallback); // If we are evaluating the cast in an lvalue context, we implicitly want // the cast to evaluate to a location. @@ -2558,7 +2597,7 @@ void GRExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred, Tmp.Add(Pred); ExplodedNodeSet Tmp2; - CheckerVisit(DS, Tmp2, Tmp, true); + CheckerVisit(DS, Tmp2, Tmp, PreVisitStmtCallback); for (ExplodedNodeSet::iterator I=Tmp2.begin(), E=Tmp2.end(); I!=E; ++I) { ExplodedNode *N = *I; @@ -3165,7 +3204,7 @@ void GRExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, } ExplodedNodeSet CheckedSet; - CheckerVisit(RS, CheckedSet, Src, true); + CheckerVisit(RS, CheckedSet, Src, PreVisitStmtCallback); for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) { @@ -3218,7 +3257,7 @@ void GRExprEngine::VisitBinaryOperator(const BinaryOperator* B, Visit(RHS, *I1, Tmp2); ExplodedNodeSet CheckedSet; - CheckerVisit(B, CheckedSet, Tmp2, true); + CheckerVisit(B, CheckedSet, Tmp2, PreVisitStmtCallback); // With both the LHS and RHS evaluated, process the operation itself. @@ -3349,7 +3388,7 @@ void GRExprEngine::VisitBinaryOperator(const BinaryOperator* B, } } - CheckerVisit(B, Dst, Tmp3, false); + CheckerVisit(B, Dst, Tmp3, PostVisitStmtCallback); } //===----------------------------------------------------------------------===// diff --git a/lib/Checker/MallocChecker.cpp b/lib/Checker/MallocChecker.cpp index 4ed309513e..f6125636f2 100644 --- a/lib/Checker/MallocChecker.cpp +++ b/lib/Checker/MallocChecker.cpp @@ -75,7 +75,8 @@ public: void EvalDeadSymbols(CheckerContext &C, SymbolReaper &SymReaper); void EvalEndPath(GREndPathNodeBuilder &B, void *tag, GRExprEngine &Eng); void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S); - const GRState *EvalAssume(const GRState *state, SVal Cond, bool Assumption); + const GRState *EvalAssume(const GRState *state, SVal Cond, bool Assumption, + bool *respondsToCallback); void VisitLocation(CheckerContext &C, const Stmt *S, SVal l); virtual void PreVisitBind(CheckerContext &C, const Stmt *AssignE, const Stmt *StoreE, SVal location, @@ -629,7 +630,8 @@ void MallocChecker::PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S) { } const GRState *MallocChecker::EvalAssume(const GRState *state, SVal Cond, - bool Assumption) { + bool Assumption, + bool * /* respondsToCallback */) { // If a symblic region is assumed to NULL, set its state to AllocateFailed. // FIXME: should also check symbols assumed to non-null. -- 2.40.0