COL729 Lab 4 : Writing Compiler Passes

Due date - 23:55, 10 November 2026

Weightage: 60 Marks (Actual weightage will be decided later)

Part A : Study Clang's Unchecked Optional Access Model Dataflow Analysis (30 marks)

In the previous assignment, we were introduced to Clang's control flow graph, and also studied Clang's single-variable constant propagation dataflow analysis. In this part of the assignment, we will study a more complex dataflow analysis, namely the Unchecked Optional Access Model dataflow analysis. Here is an example program that motivates this analysis:

  #include 

  void demo(std::optional opt, bool cond) {
    int a = *opt;                     // (1) FLAGGED: opt may be empty here

    if (opt.has_value()) {
      int b = *opt;                  // (2) OK: has_value() proven true on this branch
    } else {
      int c = *opt;                  // (3) FLAGGED: proven empty on this branch
    }

    if (!opt) {
      opt = 42;
    }
    int d = *opt;                    // (4) OK: both incoming edges guarantee a value

    while (cond) {
      if (!opt.has_value())          //Consider what happens if this is removed
        opt = 0;                     //Consider what happens if this is removed
      int e = *opt;                  // (5) OK: fixed point at loop header proves "has value"
      opt.reset();
    }
  }

You may run this analysis with clang-tidy -checks='-*,bugprone-unchecked-optional-access' demo.cpp -- -std=c++17. Consider what happens if the lines with code if (!opt.has_value()) opt = 0 are removed or commented out; what are the warnings we expect in that case?

In lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp

The lattice type is given by using LatticeTransferState = TransferState.
The transfer function is implemented in buildTransferMatchSwitch().
The check function is implemented in buildDiagnoseMatchSwitch().

The value (at each program point) in Clang's analysis is encoded by using UncheckedOptionalAccessLattice = CachedConstAccessorsLattice; in clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h. The CachedConstAccessorsLattice maintains two maps, namely ConstMethodReturnValues and ConstMethodReturnStorageLocations. The former tracks a storage location (e.g., a local variable) of record type (e.g., class, struct, union, ...) to its properties. One of the properties maps a const-qualified member function to the value it is expected to return (for a value type), and another maps it to a storage location it is supposed to return (for a reference type).

The joinConstMethodMap() function in clang/include/clang/Analysis/FlowSensitive/CachedConstAccessorsLattice.h implements the join operator for the semi-lattice.

Are the values copied at each program point (as we know that has quadratic space complexity)? Answer: The Environment object itself represents the program state (declarations, storage locations, mapped values, and path conditions) at a specific point in time. However, the complex heap-allocated elements within it (such as expressions, formulas, and values) do not live directly inside the environment. They are allocated in an Arena owned by the long-lived DataflowAnalysisContext. Environments store lightweight pointers (e.g., Value*, StorageLocation*, Formula*) pointing to these shared arena-allocated entities. When an environment is cloned or updated across CFG edges, only the mapping pointers are passed around, the underlying semantic objects are never duplicated. Inside the Environment, the maps that link program elements to their abstract states (like variable-to-location or location-to-value mappings) use llvm::DenseMap or persistent data structures (like llvm::ImmutableMap in parts of Clang's analysis suite): When moving from statement to statement, transfer functions create a shallow copy or delta modification of the mapping tables. Mappings that remain unchanged between basic blocks point to the exact same pointer addresses in memory.

How are meet-points (or join-points) handled, e.g., how are loops handled, do we have PHI nodes? Answer: No, Clang has no PHI nodes/SSA form. Instead, the dataflow engine (clang/lib/Analysis/FlowSensitive/{TypeErased}DataFlowAnalysis.cpp) is purely CFG-structural, not statement-type-specific: computeBlockInputState() joins the states of all predecessors of any block that has more than one (this is the generic meet/join, used identically for if-then-else, switch, &&/||/?:, and loop merges — the engine never special-cases which source construct produced the branch, since CFGBuilder has already lowered all of them into the same block/edge primitives discussed in the previous assignment). For a predecessor with a conditional terminator, the branch condition (or its negation) is asserted into a copy of that predecessor's environment before it is joined in, which is what gives path-sensitivity (e.g., has_value() being provably true down one edge and false down the other, as in the example above). A hard cap MaxBlockVisits bounds the total number of block visits regardless, returning a timed_out error if exceeded — this protects against non-terminating or very slow analyses on pathological/huge CFGs.

Widening: Unlike what we discussed in our lectures, for faster convergence, loop back-edges are handled specially in Clang's dataflow analysis: rather than a plain join, blocks identified by isBackedgeCFGNode() apply widening (widenTypeErased/Env.widen) to guarantee convergence, and the worklist keeps re-visiting the loop header/body until widening reports no change (LatticeJoinEffect::Unchanged). This separation of "meet behaviour" for forward edges and back edges provides the framework with better control over the convergence properties of the analysis. Think of the widening operator as a "long downward jump", whereas a join operator is a "short downward jump". In other words, at back edges, the analysis wants to make longer jumps towards the bottom (or top in Clang's parlance) --- this is done for reducing compile time (at the cost of potential imprecision) and increasing the chances of convergence within MaxBlockVisits.

Turn in:

Draw the semi-lattice of this dataflow analysis.
Can you show the mathematical representation of the transfer function for a few statements?
Can you show a mathematical representation of the widening operator? Can you show an example where widening causes a longer jump than the regular join operator?

While you may use AI for this part, please use it as sparingly as possible. Your first few attempts should always be manual --- looking through the code and understanding for yourself will likely help you learn many things (much more than what this assignment is asking). Remember that the exams may question you on this material.

Part B: Strongly-live variables (or faint variables elimination) [30 marks]

In this assignment, we will change the liveness analysis in clang/lib/Analysis/LiveVariables.cpp so that transitively dead values are also considered dead. In the literature, this is also called strongly-live variables analysis, or conversely faint-variables elimination.

In Clang's analysis implementation, DeclRefExpr represents a use of a previously-declared entity — most commonly a variable, but not exclusively. An expression of type Expr * can be checked if it is a DeclRefExpr using a dynamic cast, such as if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) .... Clang identifies liveness for values of DeclRefExpr type.

Observe the following two functions:

VisitBinaryOperator (that visits binary operators in an expression tree, like addition, subtraction, assignment, etc) handles x = rhs;: it computes Killed and removes x from liveDecls — but it never checks whether x was live before killing it, and never uses that fact for anything.
VisitDeclRefExpr: for any use of a variable that isn't the LHS target of an assignment, it unconditionally adds the referenced VarDecl to liveDecls — regardless of whether the expression this use feeds into ever produces a live result.

So today, a = b + c; always marks b and c live, even if a is never used afterward.

The expressions b, c, b+c, and a=b+c in a = b + c; are each their own CFGElement in that order, visited as separate steps in runOnBlock's reverse loop (LiveVariables.cpp). Thus, the reverse sweep first visits a=b+c (through VisitBinaryOperator), and then visits b,c (through VisitDeclRefExpr). Thus, the liveness of b and c (as computed by the liveness analysis) can benefit from the information of the assignment expression (in particular, the liveness of a).

Use the observations above to implement the strong-liveness analysis as follows:

Add a DenseSet<const DeclRefExpr *> to LiveVariablesImpl (parallel to the existing inAssignment set) — call it deadDefRHS.
In VisitBinaryOperator, for a plain assignment (=) to a DeclRefExpr LHS: compute bool WasLive = val.isLive(VD); (is the variable live in the current computed value) before the existing kill logic. If !WasLive && !B->getRHS()->HasSideEffects(Ctx), do one AST walk over B->getRHS() and insert every DeclRefExpr found into deadDefRHS, something like the following:
```
// every time VisitBinaryOperator processes this assignment (first visit or a re-visit):
for (each DeclRefExpr *DR found in B->getRHS()'s subtree) {
  if (!WasLive && !B->getRHS()->HasSideEffects(Ctx))
    LV.deadDefRHS.insert(DR);
  else
    LV.deadDefRHS.erase(DR);
}
        
```
Notice that Expr::HasSideEffects(ASTContext&) is Clang's existing conservative helper which accounts for calls, volatile accesses, etc. In your report, can you explain why the call to erase() is needed?
- Here is an example implementation for walk the AST of the RHS to identify the constituent DeclRefExprs.
```
static void collectDeclRefExprs(const Stmt *S,
                                llvm::SmallVectorImpl &Out) {
  if (!S)
    return;
  if (const auto *DR = dyn_cast(S))
    Out.push_back(DR);
  for (const Stmt *Child : S->children())
    collectDeclRefExprs(Child, Out);
}
			
```
In VisitDeclRefExpr, add if (LV.deadDefRHS.contains(DR)) return; before the existing logic that adds to liveDecls, etc.

Use git diff to generate a patch that contains your implementation, and submit it along with your report. Also, answer the questions asked above in your report, along with any other interesting observations you want to make.