[analyzer; alternate edges] improve support for edges with PseudoObjectExprs.

This optimizes some spurious edges resulting from PseudoObjectExprs.
This required far more changes than I anticipated.  The current
ParentMap does not record any hierarchy information between
a PseudoObjectExpr and its *semantic* expressions that may be
wrapped in OpaqueValueExprs, which are the expressions actually
laid out in the CFG.  This means the arrow pruning logic could
not map from an expression to its containing PseudoObjectExprs.

To solve this, this patch adds a variant of ParentMap that
returns the "semantic" parentage of expressions (essentially
as they are viewed by the CFG).  This alternate ParentMap is then
used by the arrow reducing logic to identify edges into pseudo
object expressions, and then eliminate them.

llvm-svn: 182083

5 files changed, 156 insertions, 26 deletions

diff --git a/clang/include/clang/AST/ParentMap.h b/clang/include/clang/AST/ParentMap.h
index 62eae02c152..9ec77530128 100644
--- a/clang/include/clang/AST/ParentMap.h
+++ b/clang/include/clang/AST/ParentMap.h
@@ -20,8 +20,9 @@ class Expr;
 
 class ParentMap {
   void* Impl;
+  bool IsSemantic;
 public:
-  ParentMap(Stmt* ASTRoot);
+  ParentMap(Stmt* ASTRoot, bool isSemantic = false);
   ~ParentMap();
 
   /// \brief Adds and/or updates the parent/child-relations of the complete
diff --git a/clang/include/clang/Analysis/AnalysisContext.h b/clang/include/clang/Analysis/AnalysisContext.h
index 46d7d07e090..1e6d70591cb 100644
--- a/clang/include/clang/Analysis/AnalysisContext.h
+++ b/clang/include/clang/Analysis/AnalysisContext.h
@@ -82,6 +82,7 @@ class AnalysisDeclContext {
 
   bool builtCFG, builtCompleteCFG;
   OwningPtr<ParentMap> PM;
+  OwningPtr<ParentMap> SemanticPM;
   OwningPtr<PseudoConstantAnalysis> PCA;
   OwningPtr<CFGReverseBlockReachabilityAnalysis> CFA;
 
@@ -165,6 +166,9 @@ public:
   bool isCFGBuilt() const { return builtCFG; }
 
   ParentMap &getParentMap();
+
+  ParentMap &getSemanticParentMap();
+
   PseudoConstantAnalysis *getPseudoConstantAnalysis();
 
   typedef const VarDecl * const * referenced_decls_iterator;
@@ -245,6 +249,10 @@ public:
     return getAnalysisDeclContext()->getParentMap();
   }
 
+  ParentMap &getSemanticParentMap() const {
+    return getAnalysisDeclContext()->getSemanticParentMap();
+  }
+
   const ImplicitParamDecl *getSelfDecl() const {
     return Ctx->getSelfDecl();
   }
diff --git a/clang/lib/AST/ParentMap.cpp b/clang/lib/AST/ParentMap.cpp
index 113592860b7..735926d81df 100644
--- a/clang/lib/AST/ParentMap.cpp
+++ b/clang/lib/AST/ParentMap.cpp
@@ -25,7 +25,7 @@ enum OpaqueValueMode {
   OV_Opaque
 };
 
-static void BuildParentMap(MapTy& M, Stmt* S,
+static void BuildParentMap(MapTy& M, Stmt* S, bool isSemantic,
                            OpaqueValueMode OVMode = OV_Transparent) {
 
   switch (S->getStmtClass()) {
@@ -33,14 +33,17 @@ static void BuildParentMap(MapTy& M, Stmt* S,
     assert(OVMode == OV_Transparent && "Should not appear alongside OVEs");
     PseudoObjectExpr *POE = cast<PseudoObjectExpr>(S);
 
-    M[POE->getSyntacticForm()] = S;
-    BuildParentMap(M, POE->getSyntacticForm(), OV_Transparent);
+    if (!isSemantic) {
+      M[POE->getSyntacticForm()] = S;
+      BuildParentMap(M, POE->getSyntacticForm(), OV_Transparent);
+    }
 
     for (PseudoObjectExpr::semantics_iterator I = POE->semantics_begin(),
                                               E = POE->semantics_end();
          I != E; ++I) {
       M[*I] = S;
-      BuildParentMap(M, *I, OV_Opaque);
+      BuildParentMap(M, *I, isSemantic,
+                     isSemantic ? OV_Transparent : OV_Opaque);
     }
     break;
   }
@@ -49,16 +52,16 @@ static void BuildParentMap(MapTy& M, Stmt* S,
     BinaryConditionalOperator *BCO = cast<BinaryConditionalOperator>(S);
 
     M[BCO->getCommon()] = S;
-    BuildParentMap(M, BCO->getCommon(), OV_Transparent);
+    BuildParentMap(M, BCO->getCommon(), isSemantic, OV_Transparent);
 
     M[BCO->getCond()] = S;
-    BuildParentMap(M, BCO->getCond(), OV_Opaque);
+    BuildParentMap(M, BCO->getCond(), isSemantic, OV_Opaque);
 
     M[BCO->getTrueExpr()] = S;
-    BuildParentMap(M, BCO->getTrueExpr(), OV_Opaque);
+    BuildParentMap(M, BCO->getTrueExpr(), isSemantic, OV_Opaque);
 
     M[BCO->getFalseExpr()] = S;
-    BuildParentMap(M, BCO->getFalseExpr(), OV_Transparent);
+    BuildParentMap(M, BCO->getFalseExpr(), isSemantic, OV_Transparent);
 
     break;
   }
@@ -66,24 +69,25 @@ static void BuildParentMap(MapTy& M, Stmt* S,
     if (OVMode == OV_Transparent) {
       OpaqueValueExpr *OVE = cast<OpaqueValueExpr>(S);
       M[OVE->getSourceExpr()] = S;
-      BuildParentMap(M, OVE->getSourceExpr(), OV_Transparent);
+      BuildParentMap(M, OVE->getSourceExpr(), isSemantic, OV_Transparent);
     }
     break;
   default:
     for (Stmt::child_range I = S->children(); I; ++I) {
       if (*I) {
         M[*I] = S;
-        BuildParentMap(M, *I, OVMode);
+        BuildParentMap(M, *I, isSemantic, OVMode);
       }
     }
     break;
   }
 }
 
-ParentMap::ParentMap(Stmt* S) : Impl(0) {
+ParentMap::ParentMap(Stmt* S, bool isSemantic) : Impl(0),
+                                                 IsSemantic(isSemantic) {
   if (S) {
     MapTy *M = new MapTy();
-    BuildParentMap(*M, S);
+    BuildParentMap(*M, S, isSemantic);
     Impl = M;
   }
 }
@@ -94,7 +98,7 @@ ParentMap::~ParentMap() {
 
 void ParentMap::addStmt(Stmt* S) {
   if (S) {
-    BuildParentMap(*(MapTy*) Impl, S);
+    BuildParentMap(*(MapTy*) Impl, S, IsSemantic);
   }
 }
 
diff --git a/clang/lib/Analysis/AnalysisDeclContext.cpp b/clang/lib/Analysis/AnalysisDeclContext.cpp
index 5ff7842407a..316892ea915 100644
--- a/clang/lib/Analysis/AnalysisDeclContext.cpp
+++ b/clang/lib/Analysis/AnalysisDeclContext.cpp
@@ -212,20 +212,34 @@ void AnalysisDeclContext::dumpCFG(bool ShowColors) {
     getCFG()->dump(getASTContext().getLangOpts(), ShowColors);
 }
 
+static ParentMap *constructParentMap(bool isSemantic,
+                                     Stmt *Body,
+                                     const Decl *D) {
+  ParentMap *PM = new ParentMap(Body, isSemantic);
+  if (const CXXConstructorDecl *C = dyn_cast<CXXConstructorDecl>(D)) {
+    for (CXXConstructorDecl::init_const_iterator I = C->init_begin(),
+         E = C->init_end();
+         I != E; ++I) {
+      PM->addStmt((*I)->getInit());
+    }
+  }
+  return PM;
+}
+
 ParentMap &AnalysisDeclContext::getParentMap() {
   if (!PM) {
-    PM.reset(new ParentMap(getBody()));
-    if (const CXXConstructorDecl *C = dyn_cast<CXXConstructorDecl>(getDecl())) {
-      for (CXXConstructorDecl::init_const_iterator I = C->init_begin(),
-                                                   E = C->init_end();
-           I != E; ++I) {
-        PM->addStmt((*I)->getInit());
-      }
-    }
+    PM.reset(constructParentMap(false, getBody(), getDecl()));
   }
   return *PM;
 }
 
+ParentMap &AnalysisDeclContext::getSemanticParentMap() {
+  if (!SemanticPM) {
+    SemanticPM.reset(constructParentMap(true, getBody(), getDecl()));
+  }
+  return *SemanticPM;
+}
+
 PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() {
   if (!PCA)
     PCA.reset(new PseudoConstantAnalysis(getBody()));
diff --git a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
index 519555396dd..ab3464507de 100644
--- a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
+++ b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
@@ -1873,9 +1873,78 @@ static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) {
 typedef llvm::DenseSet<const PathDiagnosticCallPiece *>
         OptimizedCallsSet;
 
+typedef llvm::DenseMap<const Stmt *,
+                       Optional<const PseudoObjectExpr *> >
+        PseudoObjectExprMap;
+
+/// Return the PseudoObjectExpr that contains this statement (if any).
+static const PseudoObjectExpr *
+getContainingPseudoObjectExpr(PseudoObjectExprMap &PEM,
+                              ParentMap &PM,
+                              const Stmt *S) {
+  if (!S)
+    return 0;
+
+  Optional<const PseudoObjectExpr *> &Entry = PEM[S];
+  if (!Entry.hasValue()) {
+    const Stmt *Parent = PM.getParentIgnoreParens(S);
+    if (const PseudoObjectExpr *PE = dyn_cast_or_null<PseudoObjectExpr>(Parent))
+      Entry = PE;
+    else
+      Entry = getContainingPseudoObjectExpr(PEM, PM, Parent);
+  }
+  return Entry.getValue();
+}
+
+#if 0
+static void printPath(PathPieces &path, ParentMap &PM) {
+  unsigned index = 0;
+  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I ) {
+    llvm::errs() << "[" << index++ << "]\n";
+    if (isa<PathDiagnosticCallPiece>(*I)) {
+      llvm::errs() << "  CALL\n";
+      continue;
+    }
+    if (isa<PathDiagnosticEventPiece>(*I)) {
+      llvm::errs() << "  EVENT\n";
+      continue;
+    }
+    if (const PathDiagnosticControlFlowPiece *CP = dyn_cast<PathDiagnosticControlFlowPiece>(*I)) {
+      llvm::errs() << "  CONTROL\n";
+      const Stmt *s1Start = getLocStmt(CP->getStartLocation());
+      const Stmt *s1End   = getLocStmt(CP->getEndLocation());
+      if (s1Start) {
+        s1Start->dump();
+        llvm::errs() << "PARENT: \n";
+        const Stmt *Parent = getStmtParent(s1Start, PM);
+        if (Parent) {
+          Parent->dump();
+        }
+      }
+      else {
+        llvm::errs() << "NULL\n";
+      }
+      llvm::errs() << " --------- ===== ----- \n";
+      if (s1End) {
+        s1End->dump();
+        llvm::errs() << "PARENT: \n";
+        const Stmt *Parent = getStmtParent(s1End, PM);
+        if (Parent) {
+          Parent->dump();
+        }
+      }
+      else {
+        llvm::errs() << "NULL\n";
+      }
+    }
+  }
+}
+#endif
+
 static bool optimizeEdges(PathPieces &path, SourceManager &SM,
                           OptimizedCallsSet &OCS,
-                          LocationContextMap &LCM) {
+                          LocationContextMap &LCM,
+                          PseudoObjectExprMap &PEM) {
   bool hasChanges = false;
   const LocationContext *LC = LCM[&path];
   assert(LC);
@@ -1890,7 +1959,7 @@ static bool optimizeEdges(PathPieces &path, SourceManager &SM,
       // Record the fact that a call has been optimized so we only do the
       // effort once.
       if (!OCS.count(CallI)) {
-        while (optimizeEdges(CallI->path, SM, OCS, LCM)) {}
+        while (optimizeEdges(CallI->path, SM, OCS, LCM, PEM)) {}
         OCS.insert(CallI);
       }
       ++I;
@@ -1906,7 +1975,7 @@ static bool optimizeEdges(PathPieces &path, SourceManager &SM,
       continue;
     }
 
-    ParentMap &PM = LC->getParentMap();
+    ParentMap &PM = LC->getSemanticParentMap();
     const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
     const Stmt *s1End   = getLocStmt(PieceI->getEndLocation());
     const Stmt *level1 = getStmtParent(s1Start, PM);
@@ -1933,6 +2002,39 @@ static bool optimizeEdges(PathPieces &path, SourceManager &SM,
       }
     }
 
+    // Prune out edges for pseudo object expressions.
+    //
+    // Case 1: incoming into a pseudo expr.
+    //
+    // An edge into a subexpression of a pseudo object expression
+    // should be replaced with an edge to the pseudo object expression
+    // itself.
+    const PseudoObjectExpr *PE = getContainingPseudoObjectExpr(PEM, PM, s1End);
+    if (PE) {
+      PathDiagnosticLocation L(PE, SM, LC);
+      PieceI->setEndLocation(L);
+      // Do not increment the iterator.  It is possible we will match again.
+      hasChanges = true;
+      continue;
+    }
+
+    // Prune out edges for pseudo object expressions.
+    //
+    // Case 2: outgoing from a pseudo expr.
+    //
+    // An edge into a subexpression of a pseudo object expression
+    // should be replaced with an edge to the pseudo object expression
+    // itself.
+    PE = getContainingPseudoObjectExpr(PEM, PM, s1Start);
+    if (PE) {
+      PathDiagnosticLocation L(PE, SM, LC);
+      PieceI->setStartLocation(L);
+      // Do not increment the iterator.  It is possible we will match again.
+      hasChanges = true;
+      continue;
+    }
+
+    // Pattern match on two edges after this point.
     PathPieces::iterator NextI = I; ++NextI;
     if (NextI == E)
       break;
@@ -2782,7 +2884,8 @@ bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD,
         // to an aesthetically pleasing subset that conveys the
         // necessary information.
         OptimizedCallsSet OCS;
-        while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM)) {}
+        PseudoObjectExprMap PEM;
+        while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM, PEM)) {}
 
         // Adjust edges into loop conditions to make them more uniform
         // and aesthetically pleasing.