[analyzer] Don't inline virtual calls unless we can devirtualize properly.

Previously we were using the static type of the base object to inline
methods, whether virtual or non-virtual. Now, we try to see if the base
object has a known type, and if so ask for its implementation of the method.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@160094 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 194 insertions, 55 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Calls.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Calls.h
index 77eb3bea74..dc7e7344a4 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/Calls.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Calls.h
@@ -33,6 +33,8 @@ enum CallEventKind {
   CE_Function,
   CE_CXXMember,
   CE_CXXMemberOperator,
+  CE_BEG_CXX_INSTANCE_CALLS = CE_CXXMember,
+  CE_END_CXX_INSTANCE_CALLS = CE_CXXMemberOperator,
   CE_Block,
   CE_BEG_SIMPLE_CALLS = CE_Function,
   CE_END_SIMPLE_CALLS = CE_Block,
@@ -84,7 +86,15 @@ public:
   /// called. May be null.
   ///
   /// This is used when deciding how to inline the call.
-  virtual const Decl *getDefinition() const { return getDecl(); }
+  ///
+  /// \param IsDynamicDispatch True if the definition returned may not be the
+  ///   definition that is actually invoked at runtime. Note that if we have
+  ///   sufficient type information to devirtualize a dynamic method call,
+  ///   we will (and \p IsDynamicDispatch will be set to \c false).
+  virtual const Decl *getDefinition(bool &IsDynamicDispatch) const {
+    IsDynamicDispatch = false;
+    return getDecl();
+  }
 
   /// \brief Returns the expression whose value will be the result of this call.
   /// May be null.
@@ -238,7 +248,8 @@ protected:
 public:
   virtual const FunctionDecl *getDecl() const = 0;
 
-  const Decl *getDefinition() const {
+  const Decl *getDefinition(bool &IsDynamicDispatch) const {
+    IsDynamicDispatch = false;
     const FunctionDecl *FD = getDecl();
     // Note that hasBody() will fill FD with the definition FunctionDecl.
     if (FD && FD->hasBody(FD))
@@ -296,17 +307,35 @@ public:
   }
 };
 
-/// \brief Represents a non-static C++ member function call.
-///
-/// Example: \c obj.fun()
-class CXXMemberCall : public SimpleCall {
+/// \brief Represents a non-static C++ member function call, no matter how
+/// it is written.
+class CXXInstanceCall : public SimpleCall {
 protected:
   void addExtraInvalidatedRegions(RegionList &Regions) const;
 
+  CXXInstanceCall(const CallExpr *CE, ProgramStateRef St,
+                  const LocationContext *LCtx, Kind K)
+    : SimpleCall(CE, St, LCtx, K) {}
+
+public:
+  SVal getCXXThisVal() const = 0;
+
+  const Decl *getDefinition(bool &IsDynamicDispatch) const;
+
+  static bool classof(const CallEvent *CA) {
+    return CA->getKind() >= CE_BEG_CXX_INSTANCE_CALLS &&
+           CA->getKind() <= CE_END_CXX_INSTANCE_CALLS;
+  }
+};
+
+/// \brief Represents a non-static C++ member function call.
+///
+/// Example: \c obj.fun()
+class CXXMemberCall : public CXXInstanceCall {
 public:
   CXXMemberCall(const CXXMemberCallExpr *CE, ProgramStateRef St,
-               const LocationContext *LCtx)
-    : SimpleCall(CE, St, LCtx, CE_CXXMember) {}
+                const LocationContext *LCtx)
+    : CXXInstanceCall(CE, St, LCtx, CE_CXXMember) {}
 
   const CXXMemberCallExpr *getOriginExpr() const {
     return cast<CXXMemberCallExpr>(SimpleCall::getOriginExpr());
@@ -323,14 +352,11 @@ public:
 /// implemented as a non-static member function.
 ///
 /// Example: <tt>iter + 1</tt>
-class CXXMemberOperatorCall : public SimpleCall {
-protected:
-  void addExtraInvalidatedRegions(RegionList &Regions) const;
-
+class CXXMemberOperatorCall : public CXXInstanceCall {
 public:
   CXXMemberOperatorCall(const CXXOperatorCallExpr *CE, ProgramStateRef St,
                         const LocationContext *LCtx)
-    : SimpleCall(CE, St, LCtx, CE_CXXMemberOperator) {}
+    : CXXInstanceCall(CE, St, LCtx, CE_CXXMemberOperator) {}
 
   const CXXOperatorCallExpr *getOriginExpr() const {
     return cast<CXXOperatorCallExpr>(SimpleCall::getOriginExpr());
@@ -381,7 +407,8 @@ public:
     return BR->getDecl();
   }
 
-  const Decl *getDefinition() const {
+  const Decl *getDefinition(bool &IsDynamicDispatch) const {
+    IsDynamicDispatch = false;
     return getBlockDecl();
   }
 
@@ -454,6 +481,7 @@ public:
   unsigned getNumArgs() const { return 0; }
 
   SVal getCXXThisVal() const;
+  const Decl *getDefinition(bool &IsDynamicDispatch) const;
 
   static bool classof(const CallEvent *CA) {
     return CA->getKind() == CE_CXXDestructor;
@@ -546,7 +574,9 @@ public:
     return Msg->getReceiverRange();
   }
 
-  const Decl *getDefinition() const {
+  const Decl *getDefinition(bool &IsDynamicDispatch) const {
+    IsDynamicDispatch = true;
+    
     const ObjCMethodDecl *MD = getDecl();
     for (Decl::redecl_iterator I = MD->redecls_begin(), E = MD->redecls_end();
          I != E; ++I) {
diff --git a/lib/StaticAnalyzer/Core/Calls.cpp b/lib/StaticAnalyzer/Core/Calls.cpp
index 94fc5fc8c0..cf4d188e43 100644
--- a/lib/StaticAnalyzer/Core/Calls.cpp
+++ b/lib/StaticAnalyzer/Core/Calls.cpp
@@ -221,7 +221,9 @@ bool CallEvent::mayBeInlined(const Stmt *S) {
 
 CallEvent::param_iterator
 AnyFunctionCall::param_begin(bool UseDefinitionParams) const {
-  const Decl *D = UseDefinitionParams ? getDefinition() : getDecl();
+  bool IgnoredDynamicDispatch;
+  const Decl *D = UseDefinitionParams ? getDefinition(IgnoredDynamicDispatch)
+                                      : getDecl();
   if (!D)
     return 0;
 
@@ -230,7 +232,9 @@ AnyFunctionCall::param_begin(bool UseDefinitionParams) const {
 
 CallEvent::param_iterator
 AnyFunctionCall::param_end(bool UseDefinitionParams) const {
-  const Decl *D = UseDefinitionParams ? getDefinition() : getDecl();
+  bool IgnoredDynamicDispatch;
+  const Decl *D = UseDefinitionParams ? getDefinition(IgnoredDynamicDispatch)
+                                      : getDecl();
   if (!D)
     return 0;
 
@@ -329,6 +333,56 @@ void CallEvent::dump(raw_ostream &Out) const {
 }
 
 
+void CXXInstanceCall::addExtraInvalidatedRegions(RegionList &Regions) const {
+  if (const MemRegion *R = getCXXThisVal().getAsRegion())
+    Regions.push_back(R);
+}
+
+static const CXXMethodDecl *devirtualize(const CXXMethodDecl *MD, SVal ThisVal){
+  const MemRegion *R = ThisVal.getAsRegion();
+  if (!R)
+    return 0;
+
+  const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R->StripCasts());
+  if (!TR)
+    return 0;
+
+  const CXXRecordDecl *RD = TR->getValueType()->getAsCXXRecordDecl();
+  if (!RD)
+    return 0;
+
+  RD = RD->getDefinition();
+  if (!RD)
+    return 0;
+
+  const CXXMethodDecl *Result = MD->getCorrespondingMethodInClass(RD);
+  const FunctionDecl *Definition;
+  if (!Result->hasBody(Definition))
+    return 0;
+
+  return cast<CXXMethodDecl>(Definition);
+}
+
+
+const Decl *CXXInstanceCall::getDefinition(bool &IsDynamicDispatch) const {
+  const Decl *D = SimpleCall::getDefinition(IsDynamicDispatch);
+  if (!D)
+    return 0;
+
+  const CXXMethodDecl *MD = cast<CXXMethodDecl>(D);
+  if (!MD->isVirtual())
+    return MD;
+
+  // If the method is virtual, see if we can find the actual implementation
+  // based on context-sensitivity.
+  if (const CXXMethodDecl *Devirtualized = devirtualize(MD, getCXXThisVal()))
+    return Devirtualized;
+
+  IsDynamicDispatch = true;
+  return MD;
+}
+
+
 SVal CXXMemberCall::getCXXThisVal() const {
   const Expr *Base = getOriginExpr()->getImplicitObjectArgument();
 
@@ -340,23 +394,12 @@ SVal CXXMemberCall::getCXXThisVal() const {
   return getSVal(Base);
 }
 
-void CXXMemberCall::addExtraInvalidatedRegions(RegionList &Regions) const {    
-  if (const MemRegion *R = getCXXThisVal().getAsRegion())
-    Regions.push_back(R);
-}
-
 
 SVal CXXMemberOperatorCall::getCXXThisVal() const {
   const Expr *Base = getOriginExpr()->getArg(0);
   return getSVal(Base);
 }
 
-void
-CXXMemberOperatorCall::addExtraInvalidatedRegions(RegionList &Regions) const {
-  if (const MemRegion *R = getCXXThisVal().getAsRegion())
-    Regions.push_back(R);
-}
-
 
 const BlockDataRegion *BlockCall::getBlockRegion() const {
   const Expr *Callee = getOriginExpr()->getCallee();
@@ -425,10 +468,30 @@ void CXXDestructorCall::addExtraInvalidatedRegions(RegionList &Regions) const {
     Regions.push_back(Target);
 }
 
+const Decl *CXXDestructorCall::getDefinition(bool &IsDynamicDispatch) const {
+  const Decl *D = AnyFunctionCall::getDefinition(IsDynamicDispatch);
+  if (!D)
+    return 0;
+
+  const CXXMethodDecl *MD = cast<CXXMethodDecl>(D);
+  if (!MD->isVirtual())
+    return MD;
+
+  // If the method is virtual, see if we can find the actual implementation
+  // based on context-sensitivity.
+  if (const CXXMethodDecl *Devirtualized = devirtualize(MD, getCXXThisVal()))
+    return Devirtualized;
+
+  IsDynamicDispatch = true;
+  return MD;
+}
+
 
 CallEvent::param_iterator
 ObjCMethodCall::param_begin(bool UseDefinitionParams) const {
-  const Decl *D = UseDefinitionParams ? getDefinition() : getDecl();
+  bool IgnoredDynamicDispatch;
+  const Decl *D = UseDefinitionParams ? getDefinition(IgnoredDynamicDispatch)
+                                      : getDecl();
   if (!D)
     return 0;
 
@@ -437,7 +500,9 @@ ObjCMethodCall::param_begin(bool UseDefinitionParams) const {
 
 CallEvent::param_iterator
 ObjCMethodCall::param_end(bool UseDefinitionParams) const {
-  const Decl *D = UseDefinitionParams ? getDefinition() : getDecl();
+  bool IgnoredDynamicDispatch;
+  const Decl *D = UseDefinitionParams ? getDefinition(IgnoredDynamicDispatch)
+                                      : getDecl();
   if (!D)
     return 0;
 
diff --git a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
index 0d9a6d79c9..493ca91b48 100644
--- a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
+++ b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
@@ -230,10 +230,6 @@ static unsigned getNumberStackFrames(const LocationContext *LCtx) {
 
 // Determine if we should inline the call.
 bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) {
-  // FIXME: default constructors don't have bodies.
-  if (!D->hasBody())
-    return false;
-
   AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
   const CFG *CalleeCFG = CalleeADC->getCFG();
 
@@ -276,13 +272,13 @@ bool ExprEngine::inlineCall(ExplodedNodeSet &Dst,
   if (!getAnalysisManager().shouldInlineCall())
     return false;
 
-  const StackFrameContext *CallerSFC =
-    Pred->getLocationContext()->getCurrentStackFrame();
-
-  const Decl *D = Call.getDefinition();
-  if (!D)
+  bool IsDynamicDispatch;
+  const Decl *D = Call.getDefinition(IsDynamicDispatch);
+  if (!D || IsDynamicDispatch)
     return false;
 
+  const LocationContext *CurLC = Pred->getLocationContext();
+  const StackFrameContext *CallerSFC = CurLC->getCurrentStackFrame();
   const LocationContext *ParentOfCallee = 0;
 
   switch (Call.getKind()) {
@@ -313,7 +309,7 @@ bool ExprEngine::inlineCall(ExplodedNodeSet &Dst,
   case CE_ObjCPropertyAccess:
     // These always use dynamic dispatch; enabling inlining means assuming
     // that a particular method will be called at runtime.
-    return false;
+    llvm_unreachable("Dynamic dispatch should be handled above.");
   }
 
   if (!shouldInlineDecl(D, Pred))
@@ -332,7 +328,7 @@ bool ExprEngine::inlineCall(ExplodedNodeSet &Dst,
                              currentBuilderContext->getBlock(),
                              currentStmtIdx);
   
-  CallEnter Loc(CallE, CalleeSFC, Pred->getLocationContext());
+  CallEnter Loc(CallE, CalleeSFC, CurLC);
 
   // Construct a new state which contains the mapping from actual to
   // formal arguments.
diff --git a/lib/StaticAnalyzer/Core/MemRegion.cpp b/lib/StaticAnalyzer/Core/MemRegion.cpp
index bcf7c3fe7d..54090783e2 100644
--- a/lib/StaticAnalyzer/Core/MemRegion.cpp
+++ b/lib/StaticAnalyzer/Core/MemRegion.cpp
@@ -954,21 +954,21 @@ const MemRegion *MemRegion::getBaseRegion() const {
 const MemRegion *MemRegion::StripCasts() const {
   const MemRegion *R = this;
   while (true) {
-    if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
-      // FIXME: generalize.  Essentially we want to strip away ElementRegions
-      // that were layered on a symbolic region because of casts.  We only
-      // want to strip away ElementRegions, however, where the index is 0.
-      SVal index = ER->getIndex();
-      if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
-        if (CI->getValue().getSExtValue() == 0) {
-          R = ER->getSuperRegion();
-          continue;
-        }
-      }
+    switch (R->getKind()) {
+    case ElementRegionKind: {
+      const ElementRegion *ER = cast<ElementRegion>(R);
+      if (!ER->getIndex().isZeroConstant())
+        return R;
+      R = ER->getSuperRegion();
+      break;
+    }
+    case CXXBaseObjectRegionKind:
+      R = cast<CXXBaseObjectRegion>(R)->getSuperRegion();
+      break;
+    default:
+      return R;
     }
-    break;
   }
-  return R;
 }
 
 // FIXME: Merge with the implementation of the same method in Store.cpp
diff --git a/test/Analysis/dynamic-cast.cpp b/test/Analysis/dynamic-cast.cpp
index 8e63b2bcb3..215bc49742 100644
--- a/test/Analysis/dynamic-cast.cpp
+++ b/test/Analysis/dynamic-cast.cpp
@@ -1,4 +1,4 @@
-// RUN: %clang_cc1 -triple i386-apple-darwin10 -analyze -analyzer-checker=core -verify %s
+// RUN: %clang_cc1 -triple i386-apple-darwin10 -analyze -analyzer-checker=core -analyzer-ipa=none -verify %s
 
 class A {
 public:
@@ -196,6 +196,9 @@ int testDynCastMostLikelyWillFail(C *c) {
   } else {
       res = 0;
   }
+
+  // Note: IPA is turned off for this test because the code below shows how the
+  // dynamic_cast could succeed.
   return *res; // expected-warning{{Dereference of null pointer}}
 }
 
diff --git a/test/Analysis/inline.cpp b/test/Analysis/inline.cpp
new file mode 100644
index 0000000000..d16eeaf619
--- /dev/null
+++ b/test/Analysis/inline.cpp
@@ -0,0 +1,45 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,debug.ExprInspection -analyzer-ipa=inlining -verify %s
+
+void clang_analyzer_eval(bool);
+
+class A {
+public:
+  int getZero() { return 0; }
+  virtual int getNum() { return 0; }
+};
+
+void test(A &a) {
+  clang_analyzer_eval(a.getZero() == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(a.getNum() == 0); // expected-warning{{UNKNOWN}}
+
+  A copy(a);
+  clang_analyzer_eval(copy.getZero() == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(copy.getNum() == 0); // expected-warning{{TRUE}}
+}
+
+
+class One : public A {
+public:
+  virtual int getNum() { return 1; }
+};
+
+void testPathSensitivity(int x) {
+  A a;
+  One b;
+
+  A *ptr;
+  switch (x) {
+  case 0:
+    ptr = &a;
+    break;
+  case 1:
+    ptr = &b;
+    break;
+  default:
+    return;
+  }
+
+  // This should be true on both branches.
+  clang_analyzer_eval(ptr->getNum() == x); // expected-warning {{TRUE}}
+}
+