From 102acd5369bbb17c0d6ab868af376671acff7a93 Mon Sep 17 00:00:00 2001 From: Douglas Gregor Date: Thu, 25 Feb 2010 19:01:53 +0000 Subject: [PATCH] Restore Zhongxing's commits r97122 r97127 r97129 r97131 which were reverted due to a Clang-on-Clang failure git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@97162 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Analysis/ProgramPoint.h | 33 +++++++ include/clang/Checker/PathSensitive/Checker.h | 8 ++ .../Checker/PathSensitive/GRCoreEngine.h | 70 +++++++++++++ .../Checker/PathSensitive/GRExprEngine.h | 8 +- .../clang/Checker/PathSensitive/GRSubEngine.h | 8 ++ lib/Checker/CallInliner.cpp | 76 +------------- lib/Checker/GRCoreEngine.cpp | 98 ++++++++++++++++++- lib/Checker/GRExprEngine.cpp | 40 ++++++++ 8 files changed, 266 insertions(+), 75 deletions(-) diff --git a/include/clang/Analysis/ProgramPoint.h b/include/clang/Analysis/ProgramPoint.h index 332f9d384f..fb8d4d5ff5 100644 --- a/include/clang/Analysis/ProgramPoint.h +++ b/include/clang/Analysis/ProgramPoint.h @@ -26,6 +26,7 @@ namespace clang { class LocationContext; +class FunctionDecl; class ProgramPoint { public: @@ -41,6 +42,8 @@ public: PostPurgeDeadSymbolsKind, PostStmtCustomKind, PostLValueKind, + CallEnterKind, + CallExitKind, MinPostStmtKind = PostStmtKind, MaxPostStmtKind = PostLValueKind }; @@ -308,6 +311,36 @@ public: } }; +class CallEnter : public StmtPoint { +public: + // CallEnter uses the caller's location context. + CallEnter(const Stmt *S, const FunctionDecl *fd, const LocationContext *L) + : StmtPoint(S, fd, CallEnterKind, L, 0) {} + + const Stmt *getCallExpr() const { + return static_cast(getData1()); + } + + const FunctionDecl *getCallee() const { + return static_cast(getData2()); + } + + static bool classof(const ProgramPoint *Location) { + return Location->getKind() == CallEnterKind; + } +}; + +class CallExit : public StmtPoint { +public: + // CallExit uses the callee's location context. + CallExit(const Stmt *S, const LocationContext *L) + : StmtPoint(S, 0, CallExitKind, L, 0) {} + + static bool classof(const ProgramPoint *Location) { + return Location->getKind() == CallExitKind; + } +}; + } // end namespace clang diff --git a/include/clang/Checker/PathSensitive/Checker.h b/include/clang/Checker/PathSensitive/Checker.h index 519c00ec59..2401a72741 100644 --- a/include/clang/Checker/PathSensitive/Checker.h +++ b/include/clang/Checker/PathSensitive/Checker.h @@ -155,6 +155,14 @@ public: Dst.Add(Pred); } + // Generate a node with a new program point different from the one that will + // be created by the GRStmtNodeBuilder. + void addTransition(const GRState *state, ProgramPoint Loc) { + ExplodedNode *N = B.generateNode(Loc, state, Pred); + if (N) + addTransition(N); + } + void EmitReport(BugReport *R) { Eng.getBugReporter().EmitReport(R); } diff --git a/include/clang/Checker/PathSensitive/GRCoreEngine.h b/include/clang/Checker/PathSensitive/GRCoreEngine.h index 6da45815f9..dd789cb735 100644 --- a/include/clang/Checker/PathSensitive/GRCoreEngine.h +++ b/include/clang/Checker/PathSensitive/GRCoreEngine.h @@ -40,6 +40,8 @@ class GRCoreEngine { friend class GRIndirectGotoNodeBuilder; friend class GRSwitchNodeBuilder; friend class GREndPathNodeBuilder; + friend class GRCallEnterNodeBuilder; + friend class GRCallExitNodeBuilder; GRSubEngine& SubEngine; @@ -67,6 +69,9 @@ class GRCoreEngine { void HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock* B, ExplodedNode* Pred); + void HandleCallEnter(const CallEnter &L, const CFGBlock *Block, + unsigned Index, ExplodedNode *Pred); + void HandleCallExit(const CallExit &L, ExplodedNode *Pred); /// Get the initial state from the subengine. const GRState* getInitialState(const LocationContext *InitLoc) { @@ -90,6 +95,9 @@ class GRCoreEngine { void ProcessSwitch(GRSwitchNodeBuilder& Builder); + void ProcessCallEnter(GRCallEnterNodeBuilder &Builder); + void ProcessCallExit(GRCallExitNodeBuilder &Builder); + private: GRCoreEngine(const GRCoreEngine&); // Do not implement. GRCoreEngine& operator=(const GRCoreEngine&); @@ -194,6 +202,12 @@ public: return generateNode(S, St, Pred, PointKind); } + ExplodedNode *generateNode(const ProgramPoint &PP, const GRState* State, + ExplodedNode* Pred) { + HasGeneratedNode = true; + return generateNodeInternal(PP, State, Pred); + } + ExplodedNode* generateNodeInternal(const ProgramPoint &PP, const GRState* State, ExplodedNode* Pred); @@ -431,6 +445,8 @@ public: ExplodedNode* generateNode(const GRState* State, const void *tag = 0, ExplodedNode *P = 0); + void GenerateCallExitNode(const GRState *state); + CFGBlock* getBlock() const { return &B; } const GRState* getState() const { @@ -438,6 +454,60 @@ public: } }; +class GRCallEnterNodeBuilder { + GRCoreEngine &Eng; + + const ExplodedNode *Pred; + + // The call site. + const Stmt *CE; + + // The definition of callee. + const FunctionDecl *FD; + + // The parent block of the CallExpr. + const CFGBlock *Block; + + // The CFGBlock index of the CallExpr. + unsigned Index; + +public: + GRCallEnterNodeBuilder(GRCoreEngine &eng, const ExplodedNode *pred, + const Stmt *s, const FunctionDecl *fd, + const CFGBlock *blk, unsigned idx) + : Eng(eng), Pred(pred), CE(s), FD(fd), Block(blk), Index(idx) {} + + const GRState *getState() const { return Pred->getState(); } + + const LocationContext *getLocationContext() const { + return Pred->getLocationContext(); + } + + const Stmt *getCallExpr() const { return CE; } + + const FunctionDecl *getCallee() const { return FD; } + + const CFGBlock *getBlock() const { return Block; } + + unsigned getIndex() const { return Index; } + + void GenerateNode(const GRState *state, const LocationContext *LocCtx); +}; + +class GRCallExitNodeBuilder { + GRCoreEngine &Eng; + const ExplodedNode *Pred; + +public: + GRCallExitNodeBuilder(GRCoreEngine &eng, const ExplodedNode *pred) + : Eng(eng), Pred(pred) {} + + const ExplodedNode *getPredecessor() const { return Pred; } + + const GRState *getState() const { return Pred->getState(); } + + void GenerateNode(const GRState *state); +}; } // end clang namespace #endif diff --git a/include/clang/Checker/PathSensitive/GRExprEngine.h b/include/clang/Checker/PathSensitive/GRExprEngine.h index 90a2cd5597..763bbcc9e1 100644 --- a/include/clang/Checker/PathSensitive/GRExprEngine.h +++ b/include/clang/Checker/PathSensitive/GRExprEngine.h @@ -171,7 +171,13 @@ public: /// ProcessEndPath - Called by GRCoreEngine. Used to generate end-of-path /// nodes when the control reaches the end of a function. void ProcessEndPath(GREndPathNodeBuilder& builder); - + + // Generate the entry node of the callee. + void ProcessCallEnter(GRCallEnterNodeBuilder &builder); + + // Generate the first post callsite node. + void ProcessCallExit(GRCallExitNodeBuilder &builder); + /// EvalAssume - Callback function invoked by the ConstraintManager when /// making assumptions about state values. const GRState *ProcessAssume(const GRState *state, SVal cond, bool assumption); diff --git a/include/clang/Checker/PathSensitive/GRSubEngine.h b/include/clang/Checker/PathSensitive/GRSubEngine.h index ce57c2c68b..f2cd0486e3 100644 --- a/include/clang/Checker/PathSensitive/GRSubEngine.h +++ b/include/clang/Checker/PathSensitive/GRSubEngine.h @@ -28,6 +28,8 @@ class GRBranchNodeBuilder; class GRIndirectGotoNodeBuilder; class GRSwitchNodeBuilder; class GREndPathNodeBuilder; +class GRCallEnterNodeBuilder; +class GRCallExitNodeBuilder; class LocationContext; class GRSubEngine { @@ -64,6 +66,12 @@ public: /// ProcessEndPath - Called by GRCoreEngine. Used to generate end-of-path /// nodes when the control reaches the end of a function. virtual void ProcessEndPath(GREndPathNodeBuilder& builder) = 0; + + // Generate the entry node of the callee. + virtual void ProcessCallEnter(GRCallEnterNodeBuilder &builder) = 0; + + // Generate the first post callsite node. + virtual void ProcessCallExit(GRCallExitNodeBuilder &builder) = 0; /// EvalAssume - Called by ConstraintManager. Used to call checker-specific /// logic for handling assumptions on symbolic values. diff --git a/lib/Checker/CallInliner.cpp b/lib/Checker/CallInliner.cpp index 0279d46f22..659d9b8bcf 100644 --- a/lib/Checker/CallInliner.cpp +++ b/lib/Checker/CallInliner.cpp @@ -26,7 +26,6 @@ public: } virtual bool EvalCallExpr(CheckerContext &C, const CallExpr *CE); - virtual void EvalEndPath(GREndPathNodeBuilder &B,void *tag,GRExprEngine &Eng); }; } @@ -46,79 +45,10 @@ bool CallInliner::EvalCallExpr(CheckerContext &C, const CallExpr *CE) { if (!FD->isThisDeclarationADefinition()) return false; - GRStmtNodeBuilder &Builder = C.getNodeBuilder(); - // Make a new LocationContext. - const StackFrameContext *LocCtx = C.getAnalysisManager().getStackFrame(FD, - C.getPredecessor()->getLocationContext(), CE, - Builder.getBlock(), Builder.getIndex()); - - CFGBlock const *Entry = &(LocCtx->getCFG()->getEntry()); - - assert (Entry->empty() && "Entry block must be empty."); - - assert (Entry->succ_size() == 1 && "Entry block must have 1 successor."); - - // Get the solitary successor. - CFGBlock const *SuccB = *(Entry->succ_begin()); - - // Construct an edge representing the starting location in the function. - BlockEdge Loc(Entry, SuccB, LocCtx); - - state = C.getStoreManager().EnterStackFrame(state, LocCtx); - - // This is a hack. We really should not use the GRStmtNodeBuilder. - bool isNew; - GRExprEngine &Eng = C.getEngine(); - ExplodedNode *Pred = C.getPredecessor(); - - - ExplodedNode *SuccN = Eng.getGraph().getNode(Loc, state, &isNew); - SuccN->addPredecessor(Pred, Eng.getGraph()); - C.getNodeBuilder().Deferred.erase(Pred); - - if (isNew) - Builder.getWorkList()->Enqueue(SuccN); - - Builder.HasGeneratedNode = true; + // Now we have the definition of the callee, create a CallEnter node. + CallEnter Loc(CE, FD, C.getPredecessor()->getLocationContext()); + C.addTransition(state, Loc); return true; } -void CallInliner::EvalEndPath(GREndPathNodeBuilder &B, void *tag, - GRExprEngine &Eng) { - const GRState *state = B.getState(); - - ExplodedNode *Pred = B.getPredecessor(); - - const StackFrameContext *LocCtx = - cast(Pred->getLocationContext()); - // Check if this is the top level stack frame. - if (!LocCtx->getParent()) - return; - - const StackFrameContext *ParentSF = - cast(LocCtx->getParent()); - - SymbolReaper SymReaper(*ParentSF->getLiveVariables(), Eng.getSymbolManager(), - ParentSF); - const Stmt *CE = LocCtx->getCallSite(); - - state = Eng.getStateManager().RemoveDeadBindings(state, const_cast(CE), - SymReaper); - - - PostStmt NodeLoc(CE, LocCtx->getParent()); - - bool isNew; - ExplodedNode *Succ = Eng.getGraph().getNode(NodeLoc, state, &isNew); - Succ->addPredecessor(Pred, Eng.getGraph()); - - // When creating the new work list unit, increment the statement index to - // point to the statement after the CallExpr. - if (isNew) - B.getWorkList().Enqueue(Succ, - *const_cast(LocCtx->getCallSiteBlock()), - LocCtx->getIndex() + 1); - - B.HasGeneratedNode = true; -} diff --git a/lib/Checker/GRCoreEngine.cpp b/lib/Checker/GRCoreEngine.cpp index d54b0777ed..cc8abc870a 100644 --- a/lib/Checker/GRCoreEngine.cpp +++ b/lib/Checker/GRCoreEngine.cpp @@ -144,6 +144,14 @@ void GRCoreEngine::ProcessSwitch(GRSwitchNodeBuilder& Builder) { SubEngine.ProcessSwitch(Builder); } +void GRCoreEngine::ProcessCallEnter(GRCallEnterNodeBuilder &Builder) { + SubEngine.ProcessCallEnter(Builder); +} + +void GRCoreEngine::ProcessCallExit(GRCallExitNodeBuilder &Builder) { + SubEngine.ProcessCallExit(Builder); +} + /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. bool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) { @@ -196,6 +204,15 @@ bool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) { assert (false && "BlockExit location never occur in forward analysis."); break; + case ProgramPoint::CallEnterKind: + HandleCallEnter(cast(Node->getLocation()), WU.getBlock(), + WU.getIndex(), Node); + break; + + case ProgramPoint::CallExitKind: + HandleCallExit(cast(Node->getLocation()), Node); + break; + default: assert(isa(Node->getLocation())); HandlePostStmt(cast(Node->getLocation()), WU.getBlock(), @@ -207,6 +224,17 @@ bool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) { return WList->hasWork(); } +void GRCoreEngine::HandleCallEnter(const CallEnter &L, const CFGBlock *Block, + unsigned Index, ExplodedNode *Pred) { + GRCallEnterNodeBuilder Builder(*this, Pred, L.getCallExpr(), L.getCallee(), + Block, Index); + ProcessCallEnter(Builder); +} + +void GRCoreEngine::HandleCallExit(const CallExit &L, ExplodedNode *Pred) { + GRCallExitNodeBuilder Builder(*this, Pred); + ProcessCallExit(Builder); +} void GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) { @@ -400,6 +428,14 @@ GRStmtNodeBuilder::~GRStmtNodeBuilder() { void GRStmtNodeBuilder::GenerateAutoTransition(ExplodedNode* N) { assert (!N->isSink()); + // Check if this node entered a callee. + if (isa(N->getLocation())) { + // Still use the index of the CallExpr. It's needed to create the callee + // StackFrameContext. + Eng.WList->Enqueue(N, B, Idx); + return; + } + PostStmt Loc(getStmt(), N->getLocationContext()); if (Loc == N->getLocation()) { @@ -576,7 +612,13 @@ GRSwitchNodeBuilder::generateDefaultCaseNode(const GRState* St, bool isSink) { GREndPathNodeBuilder::~GREndPathNodeBuilder() { // Auto-generate an EOP node if one has not been generated. - if (!HasGeneratedNode) generateNode(Pred->State); + if (!HasGeneratedNode) { + // If we are in an inlined call, generate CallExit node. + if (Pred->getLocationContext()->getParent()) + GenerateCallExitNode(Pred->State); + else + generateNode(Pred->State); + } } ExplodedNode* @@ -597,3 +639,57 @@ GREndPathNodeBuilder::generateNode(const GRState* State, const void *tag, return NULL; } + +void GREndPathNodeBuilder::GenerateCallExitNode(const GRState *state) { + HasGeneratedNode = true; + // Create a CallExit node and enqueue it. + const StackFrameContext *LocCtx + = cast(Pred->getLocationContext()); + const Stmt *CE = LocCtx->getCallSite(); + + // Use the the callee location context. + CallExit Loc(CE, LocCtx); + + bool isNew; + ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew); + Node->addPredecessor(Pred, *Eng.G); + + if (isNew) + Eng.WList->Enqueue(Node); +} + + +void GRCallEnterNodeBuilder::GenerateNode(const GRState *state, + const LocationContext *LocCtx) { + // Get the callee entry block. + const CFGBlock *Entry = &(LocCtx->getCFG()->getEntry()); + assert(Entry->empty()); + assert(Entry->succ_size() == 1); + + // Get the solitary successor. + const CFGBlock *SuccB = *(Entry->succ_begin()); + + // Construct an edge representing the starting location in the callee. + BlockEdge Loc(Entry, SuccB, LocCtx); + + bool isNew; + ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew); + Node->addPredecessor(const_cast(Pred), *Eng.G); + + if (isNew) + Eng.WList->Enqueue(Node); +} + +void GRCallExitNodeBuilder::GenerateNode(const GRState *state) { + // Get the callee's location context. + const StackFrameContext *LocCtx + = cast(Pred->getLocationContext()); + + PostStmt Loc(LocCtx->getCallSite(), LocCtx->getParent()); + bool isNew; + ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew); + Node->addPredecessor(const_cast(Pred), *Eng.G); + if (isNew) + Eng.WList->Enqueue(Node, *const_cast(LocCtx->getCallSiteBlock()), + LocCtx->getIndex() + 1); +} diff --git a/lib/Checker/GRExprEngine.cpp b/lib/Checker/GRExprEngine.cpp index 7689a35c21..30b82f70ce 100644 --- a/lib/Checker/GRExprEngine.cpp +++ b/lib/Checker/GRExprEngine.cpp @@ -1290,6 +1290,38 @@ void GRExprEngine::ProcessSwitch(GRSwitchNodeBuilder& builder) { if (defaultIsFeasible) builder.generateDefaultCaseNode(DefaultSt); } +void GRExprEngine::ProcessCallEnter(GRCallEnterNodeBuilder &B) { + const FunctionDecl *FD = B.getCallee(); + const StackFrameContext *LocCtx = AMgr.getStackFrame(FD, + B.getLocationContext(), + B.getCallExpr(), + B.getBlock(), + B.getIndex()); + + const GRState *state = B.getState(); + state = getStoreManager().EnterStackFrame(state, LocCtx); + + B.GenerateNode(state, LocCtx); +} + +void GRExprEngine::ProcessCallExit(GRCallExitNodeBuilder &B) { + const GRState *state = B.getState(); + const ExplodedNode *Pred = B.getPredecessor(); + const StackFrameContext *LocCtx = + cast(Pred->getLocationContext()); + const StackFrameContext *ParentSF = + cast(LocCtx->getParent()); + + SymbolReaper SymReaper(*ParentSF->getLiveVariables(), getSymbolManager(), + ParentSF); + const Stmt *CE = LocCtx->getCallSite(); + + state = getStateManager().RemoveDeadBindings(state, const_cast(CE), + SymReaper); + + B.GenerateNode(state); +} + //===----------------------------------------------------------------------===// // Transfer functions: logical operations ('&&', '||'). //===----------------------------------------------------------------------===// @@ -3141,6 +3173,14 @@ struct DOTGraphTraits : assert (false); break; + case ProgramPoint::CallEnterKind: + Out << "CallEnter"; + break; + + case ProgramPoint::CallExitKind: + Out << "CallExit"; + break; + default: { if (StmtPoint *L = dyn_cast(&Loc)) { const Stmt* S = L->getStmt(); -- 2.40.0