[cfe-dev] Proposed: change tracking for RegionStore

[Ted Kremenek]

On Aug 9, 2010, at 3:50 PM, Jordy Rose wrote:

> I've attached my local version of CStringChecker, so you can see how I'm
> using all of this. Much of it is very simple usage and can probably be
> cleaned up to be more efficient.

Thanks Jordy.

I'm not certain if you were looking for feedback.  Looking at CStringChecker::EvalRegionChanges() raises a few questions in my head, and it also makes me wonder if we can further optimize when this callback is called. Right now we've been talking about conditionally calling this callback only when a checker responds to it, but there are many cases when even when a checker responds to it the callback won't do any work.  In the case of CStringChecker, that case happens when Entries is empty.  Not doing the work of recording the invalidated regions might be a big savings if we only do it in the cases that matter.

More comments inline:


const GRState *CStringChecker::EvalRegionChanges(const GRState *state,
                                                 const MemRegion * const *Begin,
                                                 const MemRegion * const *End,
                                                 bool *) {
  llvm::SmallPtrSet<const MemRegion *, 8> SuperRegions;

  for ( ; Begin != End; ++Begin) {
    // Get the entry map. We do this every loop to take invalidations into
    // account.
    CStringLength::EntryMap Entries = state->get<CStringLength>();

I'm not certain why this lookup is done on every iteration of the loop.  It looks like all you do is remove entries, and querying it in this fashion from the GDM is really inefficient.


    // If there are no entries, bail out.
    if (Entries.isEmpty())
      break;


Why not check for this before the loop runs?


    // First build a list of the changed region's super-regions.
    const MemRegion *MR = *Begin;
    SuperRegions.clear();
    SuperRegions.insert(MR);

    const MemRegion *Super = MR;
    while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
      Super = SR->getSuperRegion();
      SuperRegions.insert(Super);
    }


Can't we just aggregate all the regions that you care about into one DenseSet by looping over the invalidated regions, and then batch modify Entries?


    // Then loop over the entries in the current state.
    for (CStringLength::EntryMap::iterator I = Entries.begin(),
         E = Entries.end(); I != E; ++I) {
      MR = I.getKey();

      // Is this entry for a super-region of the changed region?
      if (SuperRegions.count(MR)) {
        state = state->remove<CStringLength>(MR);

This is really inefficient.  If you are going to be modifying Entries in bulk, it's better to keep a copy of the Entries map around, modify it, and then create a new state at the very end.  This is what is done in RegionStoreManager with bulk changes to the symbolic store.

        continue;
      }

      // Is this entry for a sub-region of the changed region?
      Super = MR;
      while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
        Super = SR->getSuperRegion();
        if (Super == *Begin) {
          state = state->remove<CStringLength>(MR);
          break;
        }
      }

It really looks to me like you can just accumulate all of these regions in a DenseSet, and then prune them out from Entries in one fell swoop.

    }
  }