[analyzer] Cache computation of regionAsOffset

[george.karpenkov]

Summary

Achieves almost a 200% speedup on the example where the performance of visitors was problematic.

Performance on sqlite3 is unaffected.

rdar://38818362

[NoQ]

The huge switch in getAsOffset() does really nothing good compared to a virtual function. I suspect that this alone could have made it faster, depending on how the switch is compiled. And with a virtual function, we could also easily add the new field and the lookup only to those 3-4 regions that aren't base regions - which might as well be faster. But this already looks good, we should have tried this earlier!

[george.karpenkov]

I'm not so sure complicated mutual recursion is better than a loop...

include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h

public:
   enum Kind {
 #define REGION(Id, Parent) Id ## Kind,
 #define REGION_RANGE(Id, First, Last) BEGIN_##Id = First, END_##Id = Last,
 #include "clang/StaticAnalyzer/Core/PathSensitive/Regions.def"
   };
 
 private:
   const Kind kind;
+  mutable Optional<RegionOffset> cachedOffset;
 
 protected:
   MemRegion(Kind k) : kind(k) {}
   virtual ~MemRegion();
 
 public:
   ASTContext &getContext() const;
 

lib/StaticAnalyzer/Core/MemRegion.cpp

static bool isImmediateBase(const CXXRecordDecl *Child,
   for (const auto &I : Child->bases()) {
     if (I.getType()->getAsCXXRecordDecl() == Base)
       return true;
   }
 
   return false;
 }
 
-RegionOffset MemRegion::getAsOffset() const {
-  const MemRegion *R = this;
+static RegionOffset calculateOffset(const MemRegion *R) {
   const MemRegion *SymbolicOffsetBase = nullptr;
   int64_t Offset = 0;
 
   while (1) {
     switch (R->getKind()) {
-    case CodeSpaceRegionKind:
-    case StackLocalsSpaceRegionKind:
-    case StackArgumentsSpaceRegionKind:
-    case HeapSpaceRegionKind:
-    case UnknownSpaceRegionKind:
-    case StaticGlobalSpaceRegionKind:
-    case GlobalInternalSpaceRegionKind:
-    case GlobalSystemSpaceRegionKind:
-    case GlobalImmutableSpaceRegionKind:
+    case MemRegion::CodeSpaceRegionKind:
+    case MemRegion::StackLocalsSpaceRegionKind:
+    case MemRegion::StackArgumentsSpaceRegionKind:
+    case MemRegion::HeapSpaceRegionKind:
+    case MemRegion::UnknownSpaceRegionKind:
+    case MemRegion::StaticGlobalSpaceRegionKind:
+    case MemRegion::GlobalInternalSpaceRegionKind:
+    case MemRegion::GlobalSystemSpaceRegionKind:
+    case MemRegion::GlobalImmutableSpaceRegionKind:
       // Stores can bind directly to a region space to set a default value.
       assert(Offset == 0 && !SymbolicOffsetBase);
       goto Finish;
 
-    case FunctionCodeRegionKind:
-    case BlockCodeRegionKind:
-    case BlockDataRegionKind:
+    case MemRegion::FunctionCodeRegionKind:
+    case MemRegion::BlockCodeRegionKind:
+    case MemRegion::BlockDataRegionKind:
       // These will never have bindings, but may end up having values requested
       // if the user does some strange casting.
       if (Offset != 0)
         SymbolicOffsetBase = R;
       goto Finish;
 
-    case SymbolicRegionKind:
-    case AllocaRegionKind:
-    case CompoundLiteralRegionKind:
-    case CXXThisRegionKind:
-    case StringRegionKind:
-    case ObjCStringRegionKind:
-    case VarRegionKind:
-    case CXXTempObjectRegionKind:
+    case MemRegion::SymbolicRegionKind:
+    case MemRegion::AllocaRegionKind:
+    case MemRegion::CompoundLiteralRegionKind:
+    case MemRegion::CXXThisRegionKind:
+    case MemRegion::StringRegionKind:
+    case MemRegion::ObjCStringRegionKind:
+    case MemRegion::VarRegionKind:
+    case MemRegion::CXXTempObjectRegionKind:
       // Usual base regions.
       goto Finish;
 
-    case ObjCIvarRegionKind:
+    case MemRegion::ObjCIvarRegionKind:
       // This is a little strange, but it's a compromise between
       // ObjCIvarRegions having unknown compile-time offsets (when using the
       // non-fragile runtime) and yet still being distinct, non-overlapping
       // regions. Thus we treat them as "like" base regions for the purposes
       // of computing offsets.
       goto Finish;
 
-    case CXXBaseObjectRegionKind: {
+    case MemRegion::CXXBaseObjectRegionKind: {
       const CXXBaseObjectRegion *BOR = cast<CXXBaseObjectRegion>(R);
       R = BOR->getSuperRegion();
 
       QualType Ty;
       bool RootIsSymbolic = false;
       if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) {
-        Ty = TVR->getDesugaredValueType(getContext());
+        Ty = TVR->getDesugaredValueType(R->getContext());
       } else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
         // If our base region is symbolic, we don't know what type it really is.
         // Pretend the type of the symbol is the true dynamic type.
         // (This will at least be self-consistent for the life of the symbol.)
         Ty = SR->getSymbol()->getType()->getPointeeType();
         RootIsSymbolic = true;
       }
 
case MemRegion::CXXBaseObjectRegionKind: {
       }
 
       // Don't bother calculating precise offsets if we already have a
       // symbolic offset somewhere in the chain.
       if (SymbolicOffsetBase)
         continue;
 
       CharUnits BaseOffset;
-      const ASTRecordLayout &Layout = getContext().getASTRecordLayout(Child);
+      const ASTRecordLayout &Layout = R->getContext().getASTRecordLayout(Child);
       if (BOR->isVirtual())
         BaseOffset = Layout.getVBaseClassOffset(BOR->getDecl());
       else
         BaseOffset = Layout.getBaseClassOffset(BOR->getDecl());
 
       // The base offset is in chars, not in bits.
-      Offset += BaseOffset.getQuantity() * getContext().getCharWidth();
+      Offset += BaseOffset.getQuantity() * R->getContext().getCharWidth();
       break;
     }
-    case ElementRegionKind: {
+    case MemRegion::ElementRegionKind: {
       const ElementRegion *ER = cast<ElementRegion>(R);
       R = ER->getSuperRegion();
 
       QualType EleTy = ER->getValueType();
       if (EleTy->isIncompleteType()) {
         // We cannot compute the offset of the base class.
         SymbolicOffsetBase = R;
         continue;
       }
 
       SVal Index = ER->getIndex();
       if (Optional<nonloc::ConcreteInt> CI =
               Index.getAs<nonloc::ConcreteInt>()) {
         // Don't bother calculating precise offsets if we already have a
         // symbolic offset somewhere in the chain.
         if (SymbolicOffsetBase)
           continue;
 
         int64_t i = CI->getValue().getSExtValue();
         // This type size is in bits.
-        Offset += i * getContext().getTypeSize(EleTy);
+        Offset += i * R->getContext().getTypeSize(EleTy);
       } else {
         // We cannot compute offset for non-concrete index.
         SymbolicOffsetBase = R;
       }
       break;
     }
-    case FieldRegionKind: {
+    case MemRegion::FieldRegionKind: {
       const FieldRegion *FR = cast<FieldRegion>(R);
       R = FR->getSuperRegion();
 
       const RecordDecl *RD = FR->getDecl()->getParent();
       if (RD->isUnion() || !RD->isCompleteDefinition()) {
         // We cannot compute offset for incomplete type.
         // For unions, we could treat everything as offset 0, but we'd rather
         // treat each field as a symbolic offset so they aren't stored on top
case MemRegion::FieldRegionKind: {
 
       // Get the field number.
       unsigned idx = 0;
       for (RecordDecl::field_iterator FI = RD->field_begin(),
              FE = RD->field_end(); FI != FE; ++FI, ++idx) {
         if (FR->getDecl() == *FI)
           break;
       }
-      const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
+      const ASTRecordLayout &Layout = R->getContext().getASTRecordLayout(RD);
       // This is offset in bits.
       Offset += Layout.getFieldOffset(idx);
       break;
     }
     }
   }
 
  Finish:
   if (SymbolicOffsetBase)
     return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic);
   return RegionOffset(R, Offset);
 }
 
+RegionOffset MemRegion::getAsOffset() const {
+  if (!cachedOffset)
+    cachedOffset = calculateOffset(this);
+  return *cachedOffset;
+}
+
 //===----------------------------------------------------------------------===//
 // BlockDataRegion
 //===----------------------------------------------------------------------===//
 
 std::pair<const VarRegion *, const VarRegion *>
 BlockDataRegion::getCaptureRegions(const VarDecl *VD) {
   MemRegionManager &MemMgr = *getMemRegionManager();
   const VarRegion *VR = nullptr;