[analyzer] Bifurcate the path with dynamic dispatch.

This is an initial (unoptimized) version. We split the path when
inlining ObjC instance methods. On one branch we always assume that the
type information for the given memory region is precise. On the other we
assume that we don't have the exact type info. It is important to check
since the class could be subclassed and the method can be overridden. If
we always inline we can loose coverage.

Had to refactor some of the call eval functions.

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

6 files changed, 206 insertions, 49 deletions

diff --git a/include/clang/Frontend/Analyses.def b/include/clang/Frontend/Analyses.def
index 3859ea75fa..29ddc9e176 100644
--- a/include/clang/Frontend/Analyses.def
+++ b/include/clang/Frontend/Analyses.def
@@ -49,6 +49,7 @@ ANALYSIS_PURGE(PurgeNone,  "none", "Do not purge symbols, bindings, or constrain
 ANALYSIS_IPA(None, "none", "Perform only intra-procedural analysis")
 ANALYSIS_IPA(Inlining, "inlining", "Inline callees when their definitions are available")
 ANALYSIS_IPA(DynamicDispatch, "dynamic", "Experimental: Enable inlining of dynamically dispatched methods")
+ANALYSIS_IPA(DynamicDispatchBifurcate, "dynamic-bifurcate", "Experimental: Enable inlining of dynamically dispatched methods, bifurcate paths when exact type info is unavailable")
 
 #ifndef ANALYSIS_INLINING_MODE
 #define ANALYSIS_INLINING_MODE(NAME, CMDFLAG, DESC)
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
index 0843baa089..ab1bcf1152 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h
@@ -68,6 +68,14 @@ public:
   }
 };
 
+struct RuntimeDefinition {
+  const Decl *Decl;
+  const MemRegion *Reg;
+  RuntimeDefinition(): Decl(0), Reg(0) {}
+  RuntimeDefinition(const class Decl *D): Decl(D), Reg(0) {}
+  RuntimeDefinition(const class Decl *D, const MemRegion *R): Decl(D), Reg(R){}
+};
+
 /// \brief Represents an abstract call to a function or method along a
 /// particular path.
 ///
@@ -161,7 +169,7 @@ public:
   /// \brief Returns the definition of the function or method that will be
   /// called. Returns NULL if the definition cannot be found; ex: due to
   /// dynamic dispatch in ObjC methods.
-  virtual const Decl *getRuntimeDefinition() const = 0;
+  virtual RuntimeDefinition getRuntimeDefinition() const = 0;
 
   /// \brief Returns the expression whose value will be the result of this call.
   /// May be null.
@@ -336,12 +344,12 @@ public:
     return cast<FunctionDecl>(CallEvent::getDecl());
   }
 
-  virtual const Decl *getRuntimeDefinition() const {
+  virtual RuntimeDefinition getRuntimeDefinition() const {
     const FunctionDecl *FD = getDecl();
     // Note that hasBody() will fill FD with the definition FunctionDecl.
     if (FD && FD->hasBody(FD))
-      return FD;
-    return 0;
+      return RuntimeDefinition(FD, 0);
+    return RuntimeDefinition();
   }
 
   virtual bool argumentsMayEscape() const;
@@ -432,7 +440,7 @@ public:
     return getSVal(Base);
   }
 
-  virtual const Decl *getRuntimeDefinition() const;
+  virtual RuntimeDefinition getRuntimeDefinition() const;
 
   virtual void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
                                             BindingsTy &Bindings) const;
@@ -545,8 +553,8 @@ public:
     return BR->getDecl();
   }
 
-  virtual const Decl *getRuntimeDefinition() const {
-    return getBlockDecl();
+  virtual RuntimeDefinition getRuntimeDefinition() const {
+    return RuntimeDefinition(getBlockDecl(), 0);
   }
 
   virtual void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
@@ -650,7 +658,7 @@ public:
   /// \brief Returns the value of the implicit 'this' object.
   virtual SVal getCXXThisVal() const;
 
-  virtual const Decl *getRuntimeDefinition() const;
+  virtual RuntimeDefinition getRuntimeDefinition() const;
 
   virtual void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
                                             BindingsTy &Bindings) const;
@@ -786,7 +794,7 @@ public:
     llvm_unreachable("Unknown message kind");
   }
 
-  virtual const Decl *getRuntimeDefinition() const;
+  virtual RuntimeDefinition getRuntimeDefinition() const;
 
   virtual void getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
                                             BindingsTy &Bindings) const;
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
index 5a82b1fe13..792b24e5b4 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
@@ -489,7 +489,19 @@ private:
                     const ProgramPointTag *tag, bool isLoad);
 
   bool shouldInlineDecl(const Decl *D, ExplodedNode *Pred);
-  bool inlineCall(const CallEvent &Call, ExplodedNode *Pred);
+  bool inlineCall(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
+                  ExplodedNode *Pred, ProgramStateRef State);
+
+  /// \brief Conservatively evaluate call by invalidating regions and binding
+  /// a conjured return value.
+  void conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr,
+                            ExplodedNode *Pred, ProgramStateRef State);
+
+  /// \brief Either inline or process the call conservatively (or both), based
+  /// on DynamicDispatchBifurcation data.
+  void BifurcateCall(const MemRegion *BifurReg,
+                     const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
+                     ExplodedNode *Pred);
 
   bool replayWithoutInlining(ExplodedNode *P, const LocationContext *CalleeLC);
 };
diff --git a/lib/StaticAnalyzer/Core/CallEvent.cpp b/lib/StaticAnalyzer/Core/CallEvent.cpp
index 006ca1043a..2d96a1ea76 100644
--- a/lib/StaticAnalyzer/Core/CallEvent.cpp
+++ b/lib/StaticAnalyzer/Core/CallEvent.cpp
@@ -382,14 +382,14 @@ static const CXXMethodDecl *devirtualize(const CXXMethodDecl *MD, SVal ThisVal){
 }
 
 
-const Decl *CXXInstanceCall::getRuntimeDefinition() const {
-  const Decl *D = SimpleCall::getRuntimeDefinition();
+RuntimeDefinition CXXInstanceCall::getRuntimeDefinition() const {
+  const Decl *D = SimpleCall::getRuntimeDefinition().Decl;
   if (!D)
-    return 0;
+    return RuntimeDefinition();
 
   const CXXMethodDecl *MD = cast<CXXMethodDecl>(D);
   if (!MD->isVirtual())
-    return MD;
+    return RuntimeDefinition(MD, 0);
 
   // If the method is virtual, see if we can find the actual implementation
   // based on context-sensitivity.
@@ -398,9 +398,9 @@ const Decl *CXXInstanceCall::getRuntimeDefinition() const {
   // because a /partially/ constructed object can be referred to through a
   // base pointer. We'll eventually want to use DynamicTypeInfo here.
   if (const CXXMethodDecl *Devirtualized = devirtualize(MD, getCXXThisVal()))
-    return Devirtualized;
+    return RuntimeDefinition(Devirtualized, 0);
 
-  return 0;
+  return RuntimeDefinition();
 }
 
 void CXXInstanceCall::getInitialStackFrameContents(
@@ -512,14 +512,14 @@ void CXXDestructorCall::getExtraInvalidatedRegions(RegionList &Regions) const {
     Regions.push_back(static_cast<const MemRegion *>(Data));
 }
 
-const Decl *CXXDestructorCall::getRuntimeDefinition() const {
-  const Decl *D = AnyFunctionCall::getRuntimeDefinition();
+RuntimeDefinition CXXDestructorCall::getRuntimeDefinition() const {
+  const Decl *D = AnyFunctionCall::getRuntimeDefinition().Decl;
   if (!D)
-    return 0;
+    return RuntimeDefinition();
 
   const CXXMethodDecl *MD = cast<CXXMethodDecl>(D);
   if (!MD->isVirtual())
-    return MD;
+    return RuntimeDefinition(MD, 0);
 
   // If the method is virtual, see if we can find the actual implementation
   // based on context-sensitivity.
@@ -528,9 +528,9 @@ const Decl *CXXDestructorCall::getRuntimeDefinition() const {
   // because a /partially/ constructed object can be referred to through a
   // base pointer. We'll eventually want to use DynamicTypeInfo here.
   if (const CXXMethodDecl *Devirtualized = devirtualize(MD, getCXXThisVal()))
-    return Devirtualized;
+    return RuntimeDefinition(Devirtualized, 0);
 
-  return 0;
+  return RuntimeDefinition();
 }
 
 void CXXDestructorCall::getInitialStackFrameContents(
@@ -659,7 +659,7 @@ ObjCMessageKind ObjCMethodCall::getMessageKind() const {
   return static_cast<ObjCMessageKind>(Info.getInt());
 }
 
-const Decl *ObjCMethodCall::getRuntimeDefinition() const {
+RuntimeDefinition ObjCMethodCall::getRuntimeDefinition() const {
   const ObjCMessageExpr *E = getOriginExpr();
   assert(E);
   Selector Sel = E->getSelector();
@@ -669,12 +669,16 @@ const Decl *ObjCMethodCall::getRuntimeDefinition() const {
     // Find the the receiver type.
     const ObjCObjectPointerType *ReceiverT = 0;
     QualType SupersType = E->getSuperType();
+    const MemRegion *Receiver = 0;
+
     if (!SupersType.isNull()) {
+      // Super always means the type of immediate predecessor to the method
+      // where the call occurs.
       ReceiverT = cast<ObjCObjectPointerType>(SupersType);
     } else {
-      const MemRegion *Receiver = getReceiverSVal().getAsRegion();
+      Receiver = getReceiverSVal().getAsRegion();
       if (!Receiver)
-        return 0;
+        return RuntimeDefinition();
 
       QualType DynType = getState()->getDynamicTypeInfo(Receiver).getType();
       ReceiverT = dyn_cast<ObjCObjectPointerType>(DynType);
@@ -683,7 +687,7 @@ const Decl *ObjCMethodCall::getRuntimeDefinition() const {
     // Lookup the method implementation.
     if (ReceiverT)
       if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterfaceDecl())
-        return IDecl->lookupPrivateMethod(Sel);
+        return RuntimeDefinition(IDecl->lookupPrivateMethod(Sel), Receiver);
 
   } else {
     // This is a class method.
@@ -691,11 +695,11 @@ const Decl *ObjCMethodCall::getRuntimeDefinition() const {
     // class name.
     if (ObjCInterfaceDecl *IDecl = E->getReceiverInterface()) {
       // Find/Return the method implementation.
-      return IDecl->lookupPrivateClassMethod(Sel);
+      return RuntimeDefinition(IDecl->lookupPrivateClassMethod(Sel), 0);
     }
   }
 
-  return 0;
+  return RuntimeDefinition();
 }
 
 void ObjCMethodCall::getInitialStackFrameContents(
diff --git a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
index c1e010073c..9dd100ad77 100644
--- a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
+++ b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
@@ -11,12 +11,15 @@
 //
 //===----------------------------------------------------------------------===//
 
+#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/DeclCXX.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/Support/SaveAndRestore.h"
 
 #define CXX_INLINING_ENABLED 1
@@ -24,6 +27,9 @@
 using namespace clang;
 using namespace ento;
 
+STATISTIC(NumOfDynamicDispatchPathSplits,
+  "The # of times we split the path due to imprecise dynamic dispatch info");
+
 void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
   // Get the entry block in the CFG of the callee.
   const StackFrameContext *calleeCtx = CE.getCalleeContext();
@@ -273,14 +279,27 @@ bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) {
   return true;
 }
 
-bool ExprEngine::inlineCall(const CallEvent &Call,
-                            ExplodedNode *Pred) {
-  if (!getAnalysisManager().shouldInlineCall())
-    return false;
-
-  const Decl *D = Call.getRuntimeDefinition();
-  if (!D)
-    return false;
+/// The GDM component containing the dynamic dispatch bifurcation info. When
+/// the exact type of the receiver is not known, we want to explore both paths -
+/// one on which we do inline it and the other one on which we don't. This is
+/// done to ensure we do not drop coverage.
+/// This is the map from the receiver region to a bool, specifying either we
+/// consider this region's information precise or not along the given path.
+namespace clang {
+namespace ento {
+struct DynamicDispatchBifurcationMap {};
+typedef llvm::ImmutableMap<const MemRegion*,
+                           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();
@@ -359,7 +378,8 @@ bool ExprEngine::inlineCall(const CallEvent &Call,
     break;
   }
   case CE_ObjCMessage:
-    if (getAnalysisManager().IPAMode != DynamicDispatch)
+    if (!(getAnalysisManager().IPAMode == DynamicDispatch ||
+          getAnalysisManager().IPAMode == DynamicDispatchBifurcate))
       return false;
     break;
   }
@@ -384,7 +404,7 @@ bool ExprEngine::inlineCall(const CallEvent &Call,
 
   // Construct a new state which contains the mapping from actual to
   // formal arguments.
-  ProgramStateRef State = Pred->getState()->enterStackFrame(Call, CalleeSFC);
+  State = State->enterStackFrame(Call, CalleeSFC);
 
   bool isNew;
   if (ExplodedNode *N = G.getNode(Loc, State, false, &isNew)) {
@@ -392,6 +412,11 @@ bool ExprEngine::inlineCall(const CallEvent &Call,
     if (isNew)
       Engine.getWorkList()->enqueue(N);
   }
+
+  // If we decided to inline the call, the successor has been manually
+  // added onto the work list so remove it from the node builder.
+  Bldr.takeNodes(Pred);
+
   return true;
 }
 
@@ -491,6 +516,18 @@ ProgramStateRef ExprEngine::bindReturnValue(const CallEvent &Call,
   return State->BindExpr(E, LCtx, R);
 }
 
+// Conservatively evaluate call by invalidating regions and binding
+// a conjured return value.
+void ExprEngine::conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr,
+                                      ExplodedNode *Pred, ProgramStateRef State) {
+  unsigned Count = currentBuilderContext->getCurrentBlockCount();
+  State = Call.invalidateRegions(Count, State);
+  State = bindReturnValue(Call, Pred->getLocationContext(), State);
+
+  // And make the result node.
+  Bldr.generateNode(Call.getProgramPoint(), State, Pred);
+}
+
 void ExprEngine::defaultEvalCall(NodeBuilder &Bldr, ExplodedNode *Pred,
                                  const CallEvent &CallTemplate) {
   // Make sure we have the most recent state attached to the call.
@@ -506,23 +543,67 @@ void ExprEngine::defaultEvalCall(NodeBuilder &Bldr, ExplodedNode *Pred,
   if (InlinedFailedState) {
     // If we already tried once and failed, make sure we don't retry later.
     State = InlinedFailedState;
-  } else if (inlineCall(*Call, Pred)) {
-    // If we decided to inline the call, the successor has been manually
-    // added onto the work list and we should not perform our generic
-    // call-handling steps.
-    Bldr.takeNodes(Pred);
-    return;
+  } else if (getAnalysisManager().shouldInlineCall()) {
+    RuntimeDefinition RD = Call->getRuntimeDefinition();
+    const Decl *D = RD.Decl;
+    if (D) {
+      // Explore with and without inlining the call.
+      const MemRegion *BifurReg = RD.Reg;
+      if (BifurReg &&
+          getAnalysisManager().IPAMode == DynamicDispatchBifurcate) {
+        BifurcateCall(BifurReg, *Call, D, Bldr, Pred);
+        return;
+      } else {
+        // We are not bifurcating and we do have a Decl, so just inline.
+        if (inlineCall(*Call, D, Bldr, Pred, State))
+          return;
+      }
+    }
   }
 
   // If we can't inline it, handle the return value and invalidate the regions.
-  unsigned Count = currentBuilderContext->getCurrentBlockCount();
-  State = Call->invalidateRegions(Count, State);
-  State = bindReturnValue(*Call, Pred->getLocationContext(), State);
+  conservativeEvalCall(*Call, Bldr, Pred, State);
+}
 
-  // And make the result node.
-  Bldr.generateNode(Call->getProgramPoint(), State, Pred);
+void ExprEngine::BifurcateCall(const MemRegion *BifurReg,
+                               const CallEvent &Call, const Decl *D,
+                               NodeBuilder &Bldr, ExplodedNode *Pred) {
+  assert(BifurReg);
+
+  // Check if we've performed the split already - note, we only want
+  // to split the path once per memory region.
+  ProgramStateRef State = Pred->getState();
+  DynamicDispatchBifur BM = State->get<DynamicDispatchBifurcationMap>();
+  for (DynamicDispatchBifur::iterator I = BM.begin(),
+                                      E = BM.end(); I != E; ++I) {
+    if (I->first == BifurReg) {
+      // If we are on "inline path", keep inlining if possible.
+      if (I->second == true)
+        if (inlineCall(Call, D, Bldr, Pred, State))
+          return;
+      // If inline failed, or we are on the path where we assume we
+      // don't have enough info about the receiver to inline, conjure the
+      // return value and invalidate the regions.
+      conservativeEvalCall(Call, Bldr, Pred, State);
+      return;
+    }
+  }
+
+  // If we got here, this is the first time we process a message to this
+  // region, so split the path.
+  ProgramStateRef IState =
+      State->set<DynamicDispatchBifurcationMap>(BifurReg, true);
+  inlineCall(Call, D, Bldr, Pred, IState);
+
+  ProgramStateRef NoIState =
+      State->set<DynamicDispatchBifurcationMap>(BifurReg, false);
+  conservativeEvalCall(Call, Bldr, Pred, NoIState);
+
+  NumOfDynamicDispatchPathSplits++;
+  return;
 }
 
+
 void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
                                  ExplodedNodeSet &Dst) {
   
diff --git a/test/Analysis/inlining/DynDispatchBifurcate.m b/test/Analysis/inlining/DynDispatchBifurcate.m
new file mode 100644
index 0000000000..7616c1136b
--- /dev/null
+++ b/test/Analysis/inlining/DynDispatchBifurcate.m
@@ -0,0 +1,51 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core -analyzer-ipa=dynamic-bifurcate -verify %s
+
+typedef signed char BOOL;
+typedef struct objc_class *Class;
+typedef struct objc_object {
+    Class isa;
+} *id;
+@protocol NSObject  - (BOOL)isEqual:(id)object; @end
+@interface NSObject <NSObject> {}
++(id)alloc;
+-(id)init;
+-(id)autorelease;
+-(id)copy;
+- (Class)class;
+-(id)retain;
+@end
+
+@interface MyParent : NSObject
+- (int)getZero;
+@end
+@implementation MyParent
+- (int)getZero {
+    return 0;
+}
+@end
+
+@interface MyClass : MyParent
+- (int)getZero;
+@end
+
+MyClass *getObj();
+
+// Check that we explore both paths - on one the calla are inlined and they are 
+// not inlined on the other.
+// In this case, p can be either the object of type MyParent* or MyClass*:
+// - If it's MyParent*, getZero returns 0.
+// - If it's MyClass*, getZero returns 1 and 'return 5/m' is reachable.
+@implementation MyClass
++ (int) testTypeFromParam:(MyParent*) p {
+  int m = 0;
+  int z = [p getZero];
+  if (z)
+    return 5/m; // expected-warning {{Division by zero}}
+  return 5/[p getZero];// expected-warning {{Division by zero}}
+}
+
+- (int)getZero {
+    return 1;
+}
+
+@end
\ No newline at end of file