[Static Analyzer] Properly clean up the dynamic type information for dead regions.

[xazax.hun]

Summary

This patch is intended to clean up the dynamic type information for regions that are dead. The behavior should not change.

[xazax.hun]

• Updated to latest trunk.
• Separated the set/getDynamicTypeInfo APIs out from ProgramState

Note that it is not advised to put the implementations of set/getDynamicTypeInfo into a checker, because in that case there is a circular dependency during linking. The checkers use the symbols that are implemented in the clangStaticAnalyzerCore module and this way clangStaticAnalyzerCore would use symbols from that are implemented in the checkers as well.

[zaks.anna]

lib/StaticAnalyzer/Core/DynamicTypeMap.cpp

10 ↗

(On Diff #34507)

"that track and query"

lib/StaticAnalyzer/Core/ProgramState.cpp

17 ↗

(On Diff #34507)

Why is this header included?

[xazax.hun]

• Addressed the comments.

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h

+//== DynamicTypeMap.h - Dynamic type map ----------------------- -*- C++ -*--=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file provides APIs for tracking dynamic type information.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICTYPEMAP_H
+#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICTYPEMAP_H
+#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
+#include "llvm/ADT/ImmutableMap.h"
+
+namespace clang {
+namespace ento {
+
+/// The GDM component containing the dynamic type info. This is a map from a
+/// symbol to its most likely type.
+struct DynamicTypeMap {};
+typedef llvm::ImmutableMap<const MemRegion *, DynamicTypeInfo>
+    DynamicTypeMapImpl;
+template <>
+struct ProgramStateTrait<DynamicTypeMap>
+    : public ProgramStatePartialTrait<DynamicTypeMapImpl> {
+  static void *GDMIndex() {
+    static int index = 0;
+    return &index;
+  }
+};
+
+/// \brief Get dynamic type information for a region.
+DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State,
+                                   const MemRegion *Reg);
+
+/// \brief Set dynamic type information of the region; return the new state.
+ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *Reg,
+                                   DynamicTypeInfo NewTy);
+
+/// \brief Set dynamic type information of the region; return the new state.
+inline ProgramStateRef setDynamicTypeInfo(ProgramStateRef State,
+                                          const MemRegion *Reg, QualType NewTy,
+                                          bool CanBeSubClassed = true) {
+  return setDynamicTypeInfo(State, Reg,
+                            DynamicTypeInfo(NewTy, CanBeSubClassed));
+}
+
+} // ento
+} // clang
+
+#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICTYPEMAP_H

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h

public:
 
   /// Check if the statement is tainted in the current state.
   bool isTainted(const Stmt *S, const LocationContext *LCtx,
                  TaintTagType Kind = TaintTagGeneric) const;
   bool isTainted(SVal V, TaintTagType Kind = TaintTagGeneric) const;
   bool isTainted(SymbolRef Sym, TaintTagType Kind = TaintTagGeneric) const;
   bool isTainted(const MemRegion *Reg, TaintTagType Kind=TaintTagGeneric) const;
 
-  /// \brief Get dynamic type information for a region.
-  DynamicTypeInfo getDynamicTypeInfo(const MemRegion *Reg) const;
-
-  /// \brief Set dynamic type information of the region; return the new state.
-  ProgramStateRef setDynamicTypeInfo(const MemRegion *Reg,
-                                     DynamicTypeInfo NewTy) const;
-
-  /// \brief Set dynamic type information of the region; return the new state.
-  ProgramStateRef setDynamicTypeInfo(const MemRegion *Reg,
-                                     QualType NewTy,
-                                     bool CanBeSubClassed = true) const {
-    return setDynamicTypeInfo(Reg, DynamicTypeInfo(NewTy, CanBeSubClassed));
-  }
-
   //==---------------------------------------------------------------------==//
   // Accessing the Generic Data Map (GDM).
   //==---------------------------------------------------------------------==//
 
   void *const* FindGDM(void *K) const;
 
   template<typename T>
   ProgramStateRef add(typename ProgramStateTrait<T>::key_type K) const;

cfe/trunk/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp

 //===----------------------------------------------------------------------===//
 
 #include "ClangSACheckers.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class DynamicTypePropagation:
     public Checker< check::PreCall,
                     check::PostCall,
+                    check::DeadSymbols,
                     check::PostStmt<ImplicitCastExpr>,
                     check::PostStmt<CXXNewExpr> > {
   const ObjCObjectType *getObjectTypeForAllocAndNew(const ObjCMessageExpr *MsgE,
                                                     CheckerContext &C) const;
 
   /// \brief Return a better dynamic type if one can be derived from the cast.
   const ObjCObjectPointerType *getBetterObjCType(const Expr *CastE,
                                                  CheckerContext &C) const;
 public:
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPostStmt(const ImplicitCastExpr *CastE, CheckerContext &C) const;
   void checkPostStmt(const CXXNewExpr *NewE, CheckerContext &C) const;
+  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 };
 }
 
+void DynamicTypePropagation::checkDeadSymbols(SymbolReaper &SR,
+                                              CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  DynamicTypeMapImpl TypeMap = State->get<DynamicTypeMap>();
+  for (DynamicTypeMapImpl::iterator I = TypeMap.begin(), E = TypeMap.end();
+       I != E; ++I) {
+    if (!SR.isLiveRegion(I->first)) {
+      State = State->remove<DynamicTypeMap>(I->first);
+    }
+  }
+  C.addTransition(State);
+}
+
 static void recordFixedType(const MemRegion *Region, const CXXMethodDecl *MD,
                             CheckerContext &C) {
   assert(Region);
   assert(MD);
 
   ASTContext &Ctx = C.getASTContext();
   QualType Ty = Ctx.getPointerType(Ctx.getRecordType(MD->getParent()));
 
   ProgramStateRef State = C.getState();
-  State = State->setDynamicTypeInfo(Region, Ty, /*CanBeSubclass=*/false);
+  State = setDynamicTypeInfo(State, Region, Ty, /*CanBeSubclass=*/false);
   C.addTransition(State);
   return;
 }
 
 void DynamicTypePropagation::checkPreCall(const CallEvent &Call,
                                           CheckerContext &C) const {
   if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(&Call)) {
     // C++11 [class.cdtor]p4: When a virtual function is called directly or
if (D && D->hasRelatedResultType()) {
       case OMF_new: {
         // Get the type of object that will get created.
         const ObjCMessageExpr *MsgE = Msg->getOriginExpr();
         const ObjCObjectType *ObjTy = getObjectTypeForAllocAndNew(MsgE, C);
         if (!ObjTy)
           return;
         QualType DynResTy =
                  C.getASTContext().getObjCObjectPointerType(QualType(ObjTy, 0));
-        C.addTransition(State->setDynamicTypeInfo(RetReg, DynResTy, false));
+        C.addTransition(setDynamicTypeInfo(State, RetReg, DynResTy, false));
         break;
       }
       case OMF_init: {
         // Assume, the result of the init method has the same dynamic type as
         // the receiver and propagate the dynamic type info.
         const MemRegion *RecReg = Msg->getReceiverSVal().getAsRegion();
         if (!RecReg)
           return;
-        DynamicTypeInfo RecDynType = State->getDynamicTypeInfo(RecReg);
-        C.addTransition(State->setDynamicTypeInfo(RetReg, RecDynType));
+        DynamicTypeInfo RecDynType = getDynamicTypeInfo(State, RecReg);
+        C.addTransition(setDynamicTypeInfo(State, RetReg, RecDynType));
         break;
       }
       }
     }
     return;
   }
 
   if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(&Call)) {
if (!ToR)
     return;
 
   switch (CastE->getCastKind()) {
   default:
     break;
   case CK_BitCast:
     // Only handle ObjCObjects for now.
     if (const Type *NewTy = getBetterObjCType(CastE, C))
-      C.addTransition(C.getState()->setDynamicTypeInfo(ToR, QualType(NewTy,0)));
+      C.addTransition(setDynamicTypeInfo(C.getState(), ToR, QualType(NewTy,0)));
     break;
   }
   return;
 }
 
 void DynamicTypePropagation::checkPostStmt(const CXXNewExpr *NewE,
                                            CheckerContext &C) const {
   if (NewE->isArray())
     return;
 
   // We only track dynamic type info for regions.
   const MemRegion *MR = C.getSVal(NewE).getAsRegion();
   if (!MR)
     return;
 
-  C.addTransition(C.getState()->setDynamicTypeInfo(MR, NewE->getType(),
-                                                   /*CanBeSubclass=*/false));
+  C.addTransition(setDynamicTypeInfo(C.getState(), MR, NewE->getType(),
 }
 
 const ObjCObjectType *
 DynamicTypePropagation::getObjectTypeForAllocAndNew(const ObjCMessageExpr *MsgE,
                                                     CheckerContext &C) const {
   if (MsgE->getReceiverKind() == ObjCMessageExpr::Class) {
     if (const ObjCObjectType *ObjTy
           = MsgE->getClassReceiver()->getAs<ObjCObjectType>())
DynamicTypePropagation::getBetterObjCType(const Expr *CastE,
   const MemRegion *ToR = C.getSVal(CastE).getAsRegion();
   assert(ToR);
 
   // Get the old and new types.
   const ObjCObjectPointerType *NewTy =
       CastE->getType()->getAs<ObjCObjectPointerType>();
   if (!NewTy)
     return nullptr;
-  QualType OldDTy = C.getState()->getDynamicTypeInfo(ToR).getType();
+  QualType OldDTy = getDynamicTypeInfo(C.getState(), ToR).getType();
   if (OldDTy.isNull()) {
     return NewTy;
   }
   const ObjCObjectPointerType *OldTy =
     OldDTy->getAs<ObjCObjectPointerType>();
   if (!OldTy)
     return nullptr;
 
   // Id the old type is 'id', the new one is more precise.
   if (OldTy->isObjCIdType() && !NewTy->isObjCIdType())
     return NewTy;
 
   // Return new if it's a subclass of old.
   const ObjCInterfaceDecl *ToI = NewTy->getInterfaceDecl();
   const ObjCInterfaceDecl *FromI = OldTy->getInterfaceDecl();
   if (ToI && FromI && FromI->isSuperClassOf(ToI))
     return NewTy;
 
   return nullptr;
 }
 
 void ento::registerDynamicTypePropagation(CheckerManager &mgr) {
   mgr.registerChecker<DynamicTypePropagation>();
 }
+

cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCore
   Checker.cpp
   CheckerContext.cpp
   CheckerHelpers.cpp
   CheckerManager.cpp
   CheckerRegistry.cpp
   CommonBugCategories.cpp
   ConstraintManager.cpp
   CoreEngine.cpp
+  DynamicTypeMap.cpp
   Environment.cpp
   ExplodedGraph.cpp
   ExprEngine.cpp
   ExprEngineC.cpp
   ExprEngineCXX.cpp
   ExprEngineCallAndReturn.cpp
   ExprEngineObjC.cpp
   FunctionSummary.cpp

cfe/trunk/lib/StaticAnalyzer/Core/CallEvent.cpp

 /// (C, C++, and Objective-C).
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/AST/ParentMap.h"
 #include "clang/Analysis/ProgramPoint.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
 
 QualType CallEvent::getResultType() const {
if (!MD->isVirtual())
     return AnyFunctionCall::getRuntimeDefinition();
 
   // Do we know the implicit 'this' object being called?
   const MemRegion *R = getCXXThisVal().getAsRegion();
   if (!R)
     return RuntimeDefinition();
 
   // Do we know anything about the type of 'this'?
-  DynamicTypeInfo DynType = getState()->getDynamicTypeInfo(R);
+  DynamicTypeInfo DynType = getDynamicTypeInfo(getState(), R);
   if (!DynType.isValid())
     return RuntimeDefinition();
 
   // Is the type a C++ class? (This is mostly a defensive check.)
   QualType RegionType = DynType.getType()->getPointeeType();
   assert(!RegionType.isNull() && "DynamicTypeInfo should always be a pointer.");
 
   const CXXRecordDecl *RD = RegionType->getAsCXXRecordDecl();
if (!SupersType.isNull()) {
       // Super always means the type of immediate predecessor to the method
       // where the call occurs.
       ReceiverT = cast<ObjCObjectPointerType>(SupersType);
     } else {
       Receiver = getReceiverSVal().getAsRegion();
       if (!Receiver)
         return RuntimeDefinition();
 
-      DynamicTypeInfo DTI = getState()->getDynamicTypeInfo(Receiver);
+      DynamicTypeInfo DTI = getDynamicTypeInfo(getState(), Receiver);
       QualType DynType = DTI.getType();
       CanBeSubClassed = DTI.canBeASubClass();
       ReceiverT = dyn_cast<ObjCObjectPointerType>(DynType);
 
       if (ReceiverT && CanBeSubClassed)
         if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterfaceDecl())
           if (!canBeOverridenInSubclass(IDecl, Sel))
             CanBeSubClassed = false;

cfe/trunk/lib/StaticAnalyzer/Core/DynamicTypeMap.cpp

+//==- DynamicTypeMap.cpp - Dynamic Type Info related APIs ----------*- C++ -*-//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines APIs that track and query dynamic type information. This
+//  information can be used to devirtualize calls during the symbolic exection
+//  or do type checking.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
+
+namespace clang {
+namespace ento {
+
+DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State,
+                                   const MemRegion *Reg) {
+  Reg = Reg->StripCasts();
+
+  // Look up the dynamic type in the GDM.
+  const DynamicTypeInfo *GDMType = State->get<DynamicTypeMap>(Reg);
+  if (GDMType)
+    return *GDMType;
+
+  // Otherwise, fall back to what we know about the region.
+  if (const TypedRegion *TR = dyn_cast<TypedRegion>(Reg))
+    return DynamicTypeInfo(TR->getLocationType(), /*CanBeSubclass=*/false);
+
+  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) {
+    SymbolRef Sym = SR->getSymbol();
+    return DynamicTypeInfo(Sym->getType());
+  }
+
+  return DynamicTypeInfo();
+}
+
+ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *Reg,
+                                   DynamicTypeInfo NewTy) {
+  Reg = Reg->StripCasts();
+  ProgramStateRef NewState = State->set<DynamicTypeMap>(Reg, NewTy);
+  assert(NewState);
+  return NewState;
+}
+
+} // namespace ento
+} // namespace clang

cfe/trunk/lib/StaticAnalyzer/Core/ProgramState.cpp

for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end();
 
     if (Tainted)
       return true;
   }
 
   return Tainted;
 }
 
-/// The GDM component containing the dynamic type info. This is a map from a
-/// symbol to its most likely type.
-REGISTER_TRAIT_WITH_PROGRAMSTATE(DynamicTypeMap,
-                                 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *,
-                                                             DynamicTypeInfo))
-
-DynamicTypeInfo ProgramState::getDynamicTypeInfo(const MemRegion *Reg) const {
-  Reg = Reg->StripCasts();
-
-  // Look up the dynamic type in the GDM.
-  const DynamicTypeInfo *GDMType = get<DynamicTypeMap>(Reg);
-  if (GDMType)
-    return *GDMType;
-
-  // Otherwise, fall back to what we know about the region.
-  if (const TypedRegion *TR = dyn_cast<TypedRegion>(Reg))
-    return DynamicTypeInfo(TR->getLocationType(), /*CanBeSubclass=*/false);
-
-  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) {
-    SymbolRef Sym = SR->getSymbol();
-    return DynamicTypeInfo(Sym->getType());
-  }
-
-  return DynamicTypeInfo();
-}
-
-ProgramStateRef ProgramState::setDynamicTypeInfo(const MemRegion *Reg,
-                                                 DynamicTypeInfo NewTy) const {
-  Reg = Reg->StripCasts();
-  ProgramStateRef NewState = set<DynamicTypeMap>(Reg, NewTy);
-  assert(NewState);
-  return NewState;
-}