Quick recap on non-POD array evaluation in the Clang Static Analyzer

This post intends to summarize how non-POD array construction/destruction has been implemented in the Clang Static Analyzer so that someone might have an easier time in the future if they need to tweak or extend it. It also tries to be as verbose as possible and go into details why certain things are needed and what to pay attention to.

Non-POD arrays

When a non-POD type array is created, the constructor is invoked for each element in order, from first to last. When the lifetime of such array ends the destructors are invoked for each element but this time it happens in reverse order, so the destructor of the last element is invoked first, and the destructor of the first element is invoked last.

C++ also allows to create multidimensional arrays and some compilers including gcc and clang allow the creation of 0 length arrays too. 0 length arrays are treated as names/labels, so no machine code is generated for them, which means the constructor/destructor isn’t invoked either (gcc in fact generates code for the destructor, but doesn’t invoke it) [See it on godbolt].

Multidimensional arrays on the other hand are first unwrapped in a row major order and then they are treated as if they were single dimensional ones. This is due to the fact that their layout in memory is a single contiguous sequence of elements. S arr[2][2] = {{1, 2}, {3, 4}} has the exact same layout in memory as S arr[4] = {1, 2, 3, 4};, where S is struct S { S(int){}; };. The invocation order of the constructors and destructors is also the same for both arrays. The numbers in the initializer lists correspond to the order in which the constructors are invoked (1234) and for destructor invocation order this sequence needs to be reversed (4321).

Arrays can also be implicitly copied/moved in the following cases:

  • in the implicit copy/move constructor for a class with an array member
  • when a lambda-expression captures an array by value
  • when a decomposition declaration decomposes an array

In each of these scenarios the array is copied/moved by looping over the elements and invoking the copy/move constructor of each element in order from first to last [See it in the Clang reference].

Implementation

The analyzer intends to replicate the behaviours described in the previous section. The difficulty is that multiple different parts of the analyzer are involved in the process, so at first glance it might be hard to keep track of what happens where.

Moving data around

There are certain values multiple unrelated functions from different modules need to access, like certain indices and the size of the array being copied/moved. These infromations are stored and shared between functions with the help of the following state traits:

  • IndexOfElementToConstruct stores the index of the element of which the constructor should be invoked next. This state doesn’t store 0, so if the constructor of the first element (arr[0]) is to be invoked next, this trait is empty.

  • PendingInitLoop stores the flattened size of the array being copied by an ArrayInitLoopExpr. For S arr[2][2]; the flattened size is 4 as well as for S arr[4];.

  • PendingArrayDestruction stores the index of the current element under destruction.

Each of these traits has it’s own getTraitName(), setTraitName() and removeTraitName() utility function.

Constructors

For constructors the idea is that when the analyzer sees a CXXConstructExpr that has an array type, it visits the expression as many times as many elements the array has, and inlines the constructor for every element (if possible).

For example if the analyzer sees CXXConstructExpr 'S[4]' 'void ()' it’s going to visit the expression 4 times after each other and inlines the constructor for each element.

Step 1: Preparing for construction

When a CXXConstructExpr is visited, it gets passed to ExprEngine::handleConstructor(), which is responsible for setting up the MemRegion in which the object will be constructed and dispatching the call evaluation.

In this function the analyzer first checks if it deals with an array and whether it’s zero length or not. If it’s zero length, it ignores it otherwise it selects the index of the current element. It also needs to record if the current constructor is part of an ArrayInitLoopsExpr as that case needs special handling.

void ExprEngine::handleConstructor(...) {
  ...
  auto *AILE = CC ? CC->getArrayInitLoop() : nullptr;  

  unsigned Idx = 0;
  if (CE->getType()->isArrayType() || AILE) {
    ...
    // No element construction will happen in a 0 size array.
    if (isZeroSizeArray()) {
      StmtNodeBuilder Bldr(Pred, destNodes, *currBldrCtx);
      static SimpleProgramPointTag T{"ExprEngine",
                                     "Skipping 0 size array construction"};
      Bldr.generateNode(CE, Pred, State, &T);
      return;
    }

    Idx = getIndexOfElementToConstruct(State, CE, LCtx).value_or(0u);
    State = setIndexOfElementToConstruct(State, CE, LCtx, Idx + 1);
  }
  ...
}

When the index of the element has been selected, it is passed down to ExprEngine::handleConstructionContext() which passes it to ExprEngine::computeObjectUnderConstruction(), which is responsible for returning the region in which the object will be constructed and setting the marker that an array is being constructed.

In ExprEngine::computeObjectUnderConstruction() the region is created by either ExprEngine::makeElementRegion() or MemRegionManager::getElementRegion(), depending on the construction context. The idea is the same in both cases. The analyzer gets the element type of the array and then creates an element region with the appropriate index.

SVal ExprEngine::computeObjectUnderConstruction(...) {
  ...
  case ConstructionContext::SimpleVariableKind: {
    ...
    return makeElementRegion(State, State->getLValue(Var, LCtx), Ty,
                             CallOpts.IsArrayCtorOrDtor, Idx);
  }  
  ...
  case ConstructionContext::NewAllocatedObjectKind: {
    ...
    auto R = MRMgr.getElementRegion(Ty, svalBuilder.makeArrayIndex(Idx), MR,
                                      SVB.getContext());
    return loc::MemRegionVal(R);
  }
  ...
}

Step 2: Handling copy/move constructor (if need)

An implicit copy/move construction of an array in the Clang AST is represented by an ArrayInitLoopExpr. This expression stores information about the source array and the initializer, which is used for each element. Also it has a child node, that stores the current index, but in it’s current form that’s just a placeholder without any information.

|-ArrayInitLoopExpr 'S[4]'
| |-OpaqueValueExpr 'S[4]' lvalue
| | `-DeclRefExpr 'S[4]' lvalue Var 'arr' 'S[4]'              <-- the source array
| `-CXXConstructExpr 'S' 'void (const S &) noexcept'          <-- the initializer 
|   `-ImplicitCastExpr 'const S' lvalue <NoOp>                    of the elements 
|     `-ArraySubscriptExpr 'S' lvalue                             
|       |-ImplicitCastExpr 'S *' <ArrayToPointerDecay>
|       | `-OpaqueValueExpr 'S[4]' lvalue
|       |   `-DeclRefExpr 'S[4]' lvalue Var 'arr' 'S[4]'
|       `-ArrayInitIndexExpr <<invalid sloc>> 'unsigned long' <-- the current index

This step is in fact a hack. The copy/move constructor expects it’s first argument to be the object being copied/moved. In this case this object is one of the elements in the array, but the analyzer doesn’t know which one it is by default.

Looking at the AST of the ArrayInitLoopExpr above, it can be seen that the element getting passed to the copy constructor is the one that has the index inside the ArrayInitIndexExpr. But since that node is just a placeholder and besides it’s only referenced once in the CFG, some manual works needs to be done to select the required element anyway.

As a sidenote, one solution here would be to unroll the ArrayInitLoopExpr during CFG construction and replace the ArrayInitIndexExpr with a constant expression, that stores the actual index. That way the analyzer could copy/move construct each element automatically. Also even though this approach saves some manual work, it also reduces the amount of control the analyzer has over ArrayInitLoopExpr evaluation.

The current implementation selects the specific element of the array based on the index that has been computed in the previous step and binds that element to the argument of the copy/move constructor.

static ProgramStateRef bindRequiredArrayElementToEnvironment(...) {
  ...
  const auto *CE =
      cast<CXXConstructExpr>(extractElementInitializerFromNestedAILE(AILE));

  SVal Base = ...;
  SVal NthElem = State->getLValue(CE->getType(), Idx, Base);

  return State->BindExpr(CE->getArg(0), LCtx, NthElem);
}

void ExprEngine::handleConstructor() {
  ...
  if (AILE) {
    // Only set this once even though we loop through it multiple times.    
    if (!getPendingInitLoop(State, CE, LCtx))
      State = setPendingInitLoop(
          State, CE, LCtx, getContext().getArrayInitLoopExprElementCount(AILE));

    State = bindRequiredArrayElementToEnvironment(
        State, AILE, LCtx, svalBuilder.makeArrayIndex(Idx));
  }
  ...
}

Step 3: Deciding about inlining

After the region for the first element has been created, the analyzer needs to decide if it wants to inline the constructor and evaluate all other elements as well or it wants to fall back to conservative evaluation and wipe the region, as it happened before non-POD array evaluation was implemented.

The constructor needs to be invoked multiple times after each other. To avoid infinite loops, there’s a limit on how many times the analyzer can visit the same block in a row. This limit lives in AMgr.options.maxBlockVisitOnPath and is set to 4 by default.

Since the constructor has it’s own CFG block, the same block is going to be visited multiple times in a row, so this limit needs to be kept in mind. Moreover since the analyzer doesn’t know what side effect the constructor has, it either has to call the constructor for all of the elements or none of them. So if the element count of the array is less than or equal to AMgr.options.maxBlockVisitOnPath the constructors are inlined, otherwise conservative evaluation is used.

The logic for this lives in ExprEngine::shouldInlineArrayConstruction(), which is dispatched in ExprEngine::mayInlineCallKind().

ExprEngine::CallInlinePolicy ExprEngine::mayInlineCallKind(...) {
  ...
  if (CallOpts.IsArrayCtorOrDtor) {
    if (!shouldInlineArrayConstruction(Pred->getState(), CtorExpr, CurLC))
      return CIP_DisallowedOnce;
  }
  ...
}

Step 4: Calling the constructor again

Assuming that the constructor has been inlined at least once, the analyzer needs to decide if it should be called again or not. This is happens in ExprEngine::processCallExit(). This function handles everything that needs to be done to exit a function call (e.g.: binding the return value, switching to the caller context, etc.). It takes the CFG block of the caller and the index of the statement that dispatched the call, then increments that index by one (jumps to the next statement) and enques the next statement onto the worklist.

The current implementation ensures the same function is evaluated again by not incrementing the index if not required. In case of arrays this only happens when the index of the current element is less than the size of the array. The logic for that lives in ExprEngine::shouldRepeatCtorCall().

void ExprEngine::processCallExit(...) {
  ...
  bool ShouldRepeatCall = false;
  ...
  ShouldRepeatCall = shouldRepeatCtorCall(state, CCE, callerCtx);
  ...
  // Enqueue the next element in the block.
  for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end(); PSI != PSE;
       ++PSI) {
    unsigned Idx = calleeCtx->getIndex() + (ShouldRepeatCall ? 0 : 1);

    Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(), Idx);
  }
  ...
}

Destructors

Evaluating the destructors is nearly the same as evaluating the constructors. One key difference is that the analyzer modells destructor calls as method calls. As a result there is a lot less information that can be extracted from a destructor call. Also there are certain cases when even though the analyzer knows that an array is being destructed, it can’t extract information about it’s element count. One such case is calling delete[], which takes only a pointer to the array.

Step 1: Preparing for destruction

The functions in which arrays need to be specially handled are ExprEngine::ProcessAutomaticObjDtor(), ExprEngine::ProcessMemberDtor() and ExprEngine::ProcessDeleteDtor().

ExprEngine::ProcessTemporaryDtor() can also be invoked with array types but that case is ignored for now. For more details please see the FIXME inside that function.

The data that each of these functions can access is the region and the type of the object. These two informations are sufficient to compute the element count of the array using DynamicExtent.

Note that the element count is not always a constant value. It can also be Unknown or symbolic.

If the element count is a known constant, the initial index can also be computed easily. The logic for computing the element count and setting the current index lives in ExprEngine::prepareStateForArrayDestruction().

If the size and the index are know, the analyzer can look up the corresponding element region, otherwise the 0 element region is used and the region of the array is invalidated as it happened before.

Technically 0 length array destruction only needs special handling in case of DeleteDtors. In that case the analyzer generates a node about skipping the destruction and returns from the appropriate function. For AutomaticObjectDtors and MemberDtors it’s the CFGBuilder that skips generating the destructor for a 0 length array, so it shouldn’t appear in ExprEngine, but it’s handled regardless.

Step 2: Deciding about inlining

Ideally the destructors should only be inlined if the constructors have also been inlined. The problem is that when a destructor is called the analyzer doesn’t have access to any information about the construction of the object, so the decision about destructor inlining is made based solely on the element count. If the element count is less than or equal to AMgr.options.maxBlockVisitOnPath, the destructors are inlined, otherwise conservative evaluation is used.

In fact shouldInlineArrayConstruction() calls shouldInlineArrayDestruction() to make a decision. So technically the constructors are only inlined, if the destructors can also be inlined later.

ExprEngine::CallInlinePolicy ExprEngine::mayInlineCallKind(...) {
  ...
  if (CallOpts.IsArrayCtorOrDtor) {
    if (!shouldInlineArrayDestruction(getElementCountOfArrayBeingDestructed(
            Call, Pred->getState(), svalBuilder))) {
      return CIP_DisallowedOnce;
    }
  }
  ...
}

Step 3: Calling the destructor again

Deciding whether the destructor should be invoked again or not happens in ExprEngine::processCallExit() as in case of constructors. The call only needs to be repeated if the index of the current element is higher than 0. If it equals to 0, the analyzer is just about to finish the destruction of the last element it needs to destruct (which is the first element of the array).

It’s also important that every time the analyzer exits an element destructor call, it removes the this region from the store manually. This happens because invoking the SymbolReaper and cleaning up the unused regions is tied to statements, but an implicit destructor call is not a statement and there are scenarios when the SymbolReaper is not invoked between two destructor calls, which leads to a crash.

This problem is present if the elements in the array have an empty user defined destructor (e.g.: ~Dtor(){}). In this case the body of the destructor doesn’t contain any statements and the destructor invocation isn’t a statement either, so there’s no place for the analyzer to invoke the SymbolReaper between two consecutive destructor calls.

This leads to the this region remaining in the store after the first destructor has been exited and later when the analyzer wants to enter the second destructor, it attempts to bind the same this region to the store, but since it’s already there, it hits an assertion failure and crashes.

void ExprEngine::processCallExit(...) {
  ...
  if (const auto *DtorDecl =
          dyn_cast_or_null<CXXDestructorDecl>(Call->getDecl())) {
    if (auto Idx = getPendingArrayDestruction(state, callerCtx)) {
      ShouldRepeatCall = *Idx > 0;

      auto ThisVal = svalBuilder.getCXXThis(DtorDecl->getParent(), calleeCtx);
      state = state->killBinding(ThisVal);
    }
  }
  ...
}