ExprEngineCallAndReturn.cpp [plain text]
#define DEBUG_TYPE "ExprEngine"
#include "clang/Analysis/Analyses/LiveVariables.h"
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
#include "clang/AST/CXXInheritance.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/ParentMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/SaveAndRestore.h"
using namespace clang;
using namespace ento;
STATISTIC(NumOfDynamicDispatchPathSplits,
"The # of times we split the path due to imprecise dynamic dispatch info");
STATISTIC(NumInlinedCalls,
"The # of times we inlined a call");
void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
const StackFrameContext *calleeCtx = CE.getCalleeContext();
const CFG *CalleeCFG = calleeCtx->getCFG();
const CFGBlock *Entry = &(CalleeCFG->getEntry());
assert(Entry->empty());
assert(Entry->succ_size() == 1);
const CFGBlock *Succ = *(Entry->succ_begin());
BlockEdge Loc(Entry, Succ, calleeCtx);
ProgramStateRef state = Pred->getState();
bool isNew;
ExplodedNode *Node = G.getNode(Loc, state, false, &isNew);
Node->addPredecessor(Pred, G);
if (isNew)
Engine.getWorkList()->enqueue(Node);
}
static std::pair<const Stmt*,
const CFGBlock*> getLastStmt(const ExplodedNode *Node) {
const Stmt *S = 0;
const StackFrameContext *SF =
Node->getLocation().getLocationContext()->getCurrentStackFrame();
while (Node) {
const ProgramPoint &PP = Node->getLocation();
if (PP.getLocationContext()->getCurrentStackFrame() == SF) {
if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) {
S = SP->getStmt();
break;
} else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&PP)) {
S = CEE->getCalleeContext()->getCallSite();
if (S)
break;
const CallEnter *CE;
do {
Node = Node->getFirstPred();
CE = Node->getLocationAs<CallEnter>();
} while (!CE || CE->getCalleeContext() != CEE->getCalleeContext());
}
} else if (const CallEnter *CE = dyn_cast<CallEnter>(&PP)) {
if (CE->getCalleeContext() == SF)
break;
}
Node = *Node->pred_begin();
}
const CFGBlock *Blk = 0;
if (S) {
while (Node && Node->pred_size() >=1 ) {
const ProgramPoint &PP = Node->getLocation();
if (isa<BlockEdge>(PP) &&
(PP.getLocationContext()->getCurrentStackFrame() == SF)) {
BlockEdge &EPP = cast<BlockEdge>(PP);
Blk = EPP.getDst();
break;
}
Node = *Node->pred_begin();
}
}
return std::pair<const Stmt*, const CFGBlock*>(S, Blk);
}
static SVal adjustReturnValue(SVal V, QualType ExpectedTy, QualType ActualTy,
StoreManager &StoreMgr) {
if (!isa<Loc>(V))
return V;
ExpectedTy = ExpectedTy.getCanonicalType();
ActualTy = ActualTy.getCanonicalType();
if (ExpectedTy == ActualTy)
return V;
if (ExpectedTy->isObjCObjectPointerType() &&
ActualTy->isObjCObjectPointerType())
return V;
const CXXRecordDecl *ExpectedClass = ExpectedTy->getPointeeCXXRecordDecl();
const CXXRecordDecl *ActualClass = ActualTy->getPointeeCXXRecordDecl();
if (ExpectedClass && ActualClass) {
CXXBasePaths Paths(true, true,
false);
if (ActualClass->isDerivedFrom(ExpectedClass, Paths) &&
!Paths.isAmbiguous(ActualTy->getCanonicalTypeUnqualified())) {
return StoreMgr.evalDerivedToBase(V, Paths.front());
}
}
return UnknownVal();
}
static bool wasDifferentDeclUsedForInlining(CallEventRef<> Call,
const StackFrameContext *calleeCtx) {
const Decl *RuntimeCallee = calleeCtx->getDecl();
const Decl *StaticDecl = Call->getDecl();
assert(RuntimeCallee);
if (!StaticDecl)
return true;
return RuntimeCallee->getCanonicalDecl() != StaticDecl->getCanonicalDecl();
}
void ExprEngine::processCallExit(ExplodedNode *CEBNode) {
const StackFrameContext *calleeCtx =
CEBNode->getLocationContext()->getCurrentStackFrame();
const StackFrameContext *callerCtx =
calleeCtx->getParent()->getCurrentStackFrame();
const Stmt *CE = calleeCtx->getCallSite();
ProgramStateRef state = CEBNode->getState();
const Stmt *LastSt = 0;
const CFGBlock *Blk = 0;
llvm::tie(LastSt, Blk) = getLastStmt(CEBNode);
CallEventManager &CEMgr = getStateManager().getCallEventManager();
CallEventRef<> Call = CEMgr.getCaller(calleeCtx, state);
if (CE) {
if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) {
const LocationContext *LCtx = CEBNode->getLocationContext();
SVal V = state->getSVal(RS, LCtx);
if (wasDifferentDeclUsedForInlining(Call, calleeCtx)) {
QualType ReturnedTy =
CallEvent::getDeclaredResultType(calleeCtx->getDecl());
if (!ReturnedTy.isNull()) {
if (const Expr *Ex = dyn_cast<Expr>(CE)) {
V = adjustReturnValue(V, Ex->getType(), ReturnedTy,
getStoreManager());
}
}
}
state = state->BindExpr(CE, callerCtx, V);
}
if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
loc::MemRegionVal This =
svalBuilder.getCXXThis(CCE->getConstructor()->getParent(), calleeCtx);
SVal ThisV = state->getSVal(This);
if (!CCE->isGLValue())
if (const MemRegion *MR = ThisV.getAsRegion())
if (isa<CXXTempObjectRegion>(MR))
ThisV = state->getSVal(cast<Loc>(ThisV));
state = state->BindExpr(CCE, callerCtx, ThisV);
}
}
ExplodedNodeSet CleanedNodes;
if (LastSt && Blk && AMgr.options.AnalysisPurgeOpt != PurgeNone) {
static SimpleProgramPointTag retValBind("ExprEngine : Bind Return Value");
PostStmt Loc(LastSt, calleeCtx, &retValBind);
bool isNew;
ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew);
BindedRetNode->addPredecessor(CEBNode, G);
if (!isNew)
return;
NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode);
currBldrCtx = &Ctx;
removeDead(BindedRetNode, CleanedNodes, 0, callerCtx, LastSt,
ProgramPoint::PostStmtPurgeDeadSymbolsKind);
currBldrCtx = 0;
} else {
CleanedNodes.Add(CEBNode);
}
for (ExplodedNodeSet::iterator I = CleanedNodes.begin(),
E = CleanedNodes.end(); I != E; ++I) {
CallExitEnd Loc(calleeCtx, callerCtx);
bool isNew;
ProgramStateRef CEEState = (*I == CEBNode) ? state : (*I)->getState();
ExplodedNode *CEENode = G.getNode(Loc, CEEState, false, &isNew);
CEENode->addPredecessor(*I, G);
if (!isNew)
return;
NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode);
SaveAndRestore<const NodeBuilderContext*> NBCSave(currBldrCtx,
&Ctx);
SaveAndRestore<unsigned> CBISave(currStmtIdx, calleeCtx->getIndex());
CallEventRef<> UpdatedCall = Call.cloneWithState(CEEState);
ExplodedNodeSet DstPostCall;
getCheckerManager().runCheckersForPostCall(DstPostCall, CEENode,
*UpdatedCall, *this,
true);
ExplodedNodeSet Dst;
if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Call)) {
getCheckerManager().runCheckersForPostObjCMessage(Dst, DstPostCall, *Msg,
*this,
true);
} else if (CE) {
getCheckerManager().runCheckersForPostStmt(Dst, DstPostCall, CE,
*this, true);
} else {
Dst.insert(DstPostCall);
}
for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end();
PSI != PSE; ++PSI) {
Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(),
calleeCtx->getIndex()+1);
}
}
}
void ExprEngine::examineStackFrames(const Decl *D, const LocationContext *LCtx,
bool &IsRecursive, unsigned &StackDepth) {
IsRecursive = false;
StackDepth = 0;
while (LCtx) {
if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LCtx)) {
const Decl *DI = SFC->getDecl();
if (DI == D) {
IsRecursive = true;
++StackDepth;
LCtx = LCtx->getParent();
continue;
}
AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(DI);
const CFG *CalleeCFG = CalleeADC->getCFG();
if (CalleeCFG->getNumBlockIDs() > AMgr.options.getAlwaysInlineSize())
++StackDepth;
}
LCtx = LCtx->getParent();
}
}
static bool IsInStdNamespace(const FunctionDecl *FD) {
const DeclContext *DC = FD->getEnclosingNamespaceContext();
const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(DC);
if (!ND)
return false;
while (const DeclContext *Parent = ND->getParent()) {
if (!isa<NamespaceDecl>(Parent))
break;
ND = cast<NamespaceDecl>(Parent);
}
return ND->getName() == "std";
}
bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) {
AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
const CFG *CalleeCFG = CalleeADC->getCFG();
if (!CalleeCFG)
return false;
bool IsRecursive = false;
unsigned StackDepth = 0;
examineStackFrames(D, Pred->getLocationContext(), IsRecursive, StackDepth);
if ((StackDepth >= AMgr.options.InlineMaxStackDepth) &&
((CalleeCFG->getNumBlockIDs() > AMgr.options.getAlwaysInlineSize())
|| IsRecursive))
return false;
if (Engine.FunctionSummaries->hasReachedMaxBlockCount(D))
return false;
if (CalleeCFG->getNumBlockIDs() > AMgr.options.InlineMaxFunctionSize)
return false;
if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
if (BD->isVariadic())
return false;
}
else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
if (FD->isVariadic())
return false;
}
if (getContext().getLangOpts().CPlusPlus) {
if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
if (!getAnalysisManager().options.mayInlineTemplateFunctions())
if (FD->getTemplatedKind() != FunctionDecl::TK_NonTemplate)
return false;
if (!getAnalysisManager().options.mayInlineCXXStandardLibrary())
if (getContext().getSourceManager().isInSystemHeader(FD->getLocation()))
if (IsInStdNamespace(FD))
return false;
}
}
if (!CalleeADC->getAnalysis<RelaxedLiveVariables>())
return false;
return true;
}
namespace clang {
namespace ento {
enum DynamicDispatchMode { DynamicDispatchModeInlined = 1,
DynamicDispatchModeConservative };
struct DynamicDispatchBifurcationMap {};
typedef llvm::ImmutableMap<const MemRegion*,
unsigned int> DynamicDispatchBifur;
template<> struct ProgramStateTrait<DynamicDispatchBifurcationMap>
: public ProgramStatePartialTrait<DynamicDispatchBifur> {
static void *GDMIndex() { static int index; return &index; }
};
}}
bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D,
NodeBuilder &Bldr, ExplodedNode *Pred,
ProgramStateRef State) {
assert(D);
const LocationContext *CurLC = Pred->getLocationContext();
const StackFrameContext *CallerSFC = CurLC->getCurrentStackFrame();
const LocationContext *ParentOfCallee = 0;
AnalyzerOptions &Opts = getAnalysisManager().options;
switch (Call.getKind()) {
case CE_Function:
break;
case CE_CXXMember:
case CE_CXXMemberOperator:
if (!Opts.mayInlineCXXMemberFunction(CIMK_MemberFunctions))
return false;
break;
case CE_CXXConstructor: {
if (!Opts.mayInlineCXXMemberFunction(CIMK_Constructors))
return false;
const CXXConstructorCall &Ctor = cast<CXXConstructorCall>(Call);
const MemRegion *Target = Ctor.getCXXThisVal().getAsRegion();
if (Target && isa<ElementRegion>(Target))
return false;
const CXXConstructExpr *CtorExpr = Ctor.getOriginExpr();
if (const Stmt *Parent = CurLC->getParentMap().getParent(CtorExpr))
if (isa<CXXNewExpr>(Parent))
return false;
const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext();
assert(ADC->getCFGBuildOptions().AddInitializers && "No CFG initializers");
(void)ADC;
if (Ctor.getDecl()->getParent()->hasTrivialDestructor())
break;
if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors))
return false;
if (CtorExpr->getConstructionKind() == CXXConstructExpr::CK_Complete)
if (!Target || !isa<DeclRegion>(Target))
return false;
break;
}
case CE_CXXDestructor: {
if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors))
return false;
const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext();
assert(ADC->getCFGBuildOptions().AddImplicitDtors && "No CFG destructors");
(void)ADC;
const CXXDestructorCall &Dtor = cast<CXXDestructorCall>(Call);
const MemRegion *Target = Dtor.getCXXThisVal().getAsRegion();
if (Target && isa<ElementRegion>(Target))
return false;
break;
}
case CE_CXXAllocator:
return false;
case CE_Block: {
const BlockDataRegion *BR = cast<BlockCall>(Call).getBlockRegion();
assert(BR && "If we have the block definition we should have its region");
AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(D);
ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC,
cast<BlockDecl>(D),
BR);
break;
}
case CE_ObjCMessage:
if (!Opts.mayInlineObjCMethod())
return false;
if (!(getAnalysisManager().options.IPAMode == DynamicDispatch ||
getAnalysisManager().options.IPAMode == DynamicDispatchBifurcate))
return false;
break;
}
if (!shouldInlineDecl(D, Pred))
return false;
if (!ParentOfCallee)
ParentOfCallee = CallerSFC;
const Expr *CallE = Call.getOriginExpr();
AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
const StackFrameContext *CalleeSFC =
CalleeADC->getStackFrame(ParentOfCallee, CallE,
currBldrCtx->getBlock(),
currStmtIdx);
CallEnter Loc(CallE, CalleeSFC, CurLC);
State = State->enterStackFrame(Call, CalleeSFC);
bool isNew;
if (ExplodedNode *N = G.getNode(Loc, State, false, &isNew)) {
N->addPredecessor(Pred, G);
if (isNew)
Engine.getWorkList()->enqueue(N);
}
Bldr.takeNodes(Pred);
NumInlinedCalls++;
if (VisitedCallees)
VisitedCallees->insert(D);
return true;
}
static ProgramStateRef getInlineFailedState(ProgramStateRef State,
const Stmt *CallE) {
void *ReplayState = State->get<ReplayWithoutInlining>();
if (!ReplayState)
return 0;
assert(ReplayState == (const void*)CallE && "Backtracked to the wrong call.");
(void)CallE;
return State->remove<ReplayWithoutInlining>();
}
void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
ExplodedNodeSet &dst) {
ExplodedNodeSet dstPreVisit;
getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this);
CallEventManager &CEMgr = getStateManager().getCallEventManager();
CallEventRef<> CallTemplate
= CEMgr.getSimpleCall(CE, Pred->getState(), Pred->getLocationContext());
ExplodedNodeSet dstCallEvaluated;
for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();
I != E; ++I) {
evalCall(dstCallEvaluated, *I, *CallTemplate);
}
getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE,
*this);
}
void ExprEngine::evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
const CallEvent &Call) {
ExplodedNodeSet dstPreVisit;
getCheckerManager().runCheckersForPreCall(dstPreVisit, Pred, Call, *this);
ExplodedNodeSet dstCallEvaluated;
getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, dstPreVisit,
Call, *this);
getCheckerManager().runCheckersForPostCall(Dst, dstCallEvaluated,
Call, *this);
}
ProgramStateRef ExprEngine::bindReturnValue(const CallEvent &Call,
const LocationContext *LCtx,
ProgramStateRef State) {
const Expr *E = Call.getOriginExpr();
if (!E)
return State;
if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(&Call)) {
switch (Msg->getMethodFamily()) {
default:
break;
case OMF_autorelease:
case OMF_retain:
case OMF_self: {
return State->BindExpr(E, LCtx, Msg->getReceiverSVal());
}
}
} else if (const CXXConstructorCall *C = dyn_cast<CXXConstructorCall>(&Call)){
return State->BindExpr(E, LCtx, C->getCXXThisVal());
}
QualType ResultTy = Call.getResultType();
SValBuilder &SVB = getSValBuilder();
unsigned Count = currBldrCtx->blockCount();
SVal R = SVB.conjureSymbolVal(0, E, LCtx, ResultTy, Count);
return State->BindExpr(E, LCtx, R);
}
void ExprEngine::conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr,
ExplodedNode *Pred, ProgramStateRef State) {
State = Call.invalidateRegions(currBldrCtx->blockCount(), State);
State = bindReturnValue(Call, Pred->getLocationContext(), State);
Bldr.generateNode(Call.getProgramPoint(), State, Pred);
}
void ExprEngine::defaultEvalCall(NodeBuilder &Bldr, ExplodedNode *Pred,
const CallEvent &CallTemplate) {
ProgramStateRef State = Pred->getState();
CallEventRef<> Call = CallTemplate.cloneWithState(State);
if (!getAnalysisManager().shouldInlineCall()) {
conservativeEvalCall(*Call, Bldr, Pred, State);
return;
}
const Expr *E = Call->getOriginExpr();
ProgramStateRef InlinedFailedState = getInlineFailedState(State, E);
if (InlinedFailedState) {
State = InlinedFailedState;
} else {
RuntimeDefinition RD = Call->getRuntimeDefinition();
const Decl *D = RD.getDecl();
if (D) {
if (RD.mayHaveOtherDefinitions()) {
if (getAnalysisManager().options.IPAMode == DynamicDispatchBifurcate) {
BifurcateCall(RD.getDispatchRegion(), *Call, D, Bldr, Pred);
return;
}
if (getAnalysisManager().options.IPAMode != DynamicDispatch) {
conservativeEvalCall(*Call, Bldr, Pred, State);
return;
}
}
if (inlineCall(*Call, D, Bldr, Pred, State))
return;
}
}
conservativeEvalCall(*Call, Bldr, Pred, State);
}
void ExprEngine::BifurcateCall(const MemRegion *BifurReg,
const CallEvent &Call, const Decl *D,
NodeBuilder &Bldr, ExplodedNode *Pred) {
assert(BifurReg);
BifurReg = BifurReg->StripCasts();
ProgramStateRef State = Pred->getState();
const unsigned int *BState =
State->get<DynamicDispatchBifurcationMap>(BifurReg);
if (BState) {
if (*BState == DynamicDispatchModeInlined)
if (inlineCall(Call, D, Bldr, Pred, State))
return;
conservativeEvalCall(Call, Bldr, Pred, State);
return;
}
ProgramStateRef IState =
State->set<DynamicDispatchBifurcationMap>(BifurReg,
DynamicDispatchModeInlined);
inlineCall(Call, D, Bldr, Pred, IState);
ProgramStateRef NoIState =
State->set<DynamicDispatchBifurcationMap>(BifurReg,
DynamicDispatchModeConservative);
conservativeEvalCall(Call, Bldr, Pred, NoIState);
NumOfDynamicDispatchPathSplits++;
return;
}
void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
ExplodedNodeSet &Dst) {
ExplodedNodeSet dstPreVisit;
getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this);
StmtNodeBuilder B(dstPreVisit, Dst, *currBldrCtx);
if (RS->getRetValue()) {
for (ExplodedNodeSet::iterator it = dstPreVisit.begin(),
ei = dstPreVisit.end(); it != ei; ++it) {
B.generateNode(RS, *it, (*it)->getState());
}
}
}