Skip to main content

Uninitialized Variables


Given a graph-like model of a program -a control flow graph-, how can we detect the uninitialized variables? This recipe is simplified to the bone to highlight the algorithm, as opposed to the intermediate representation.

import Relation;
import analysis::graphs::Graph;

We model expressions as line numbers here. Normally you could use a Location to uniquely identify an expression or an Algebraic Data Type of an abstract syntax tree of the expression or statement:

alias Expr = int;
alias Varname = str;

The first line number is 1:

Expr root = 1;
rascal>Graph[Expr] pred = {<1,3>, <3,4>, <4,5>, <5,6>, <5,8>, <6,10>, <8,10>};
Graph[int]: {
rascal>import vis::Graphs;


Now we represent the example definitions (assignments) of variables at given line numbers and the uses of variables at given lines:

rascal>rel[Varname,Expr] defs = {<"x", 3>, <"p", 4>, <"z", 6>, <"x", 8>, <"y", 10>};
rel[str,int]: {
rascal>rel[Varname, Expr] uses = {<"q", 5>, <"y", 6>, <"x", 6>, <"z", 10>};
rel[str,int]: {

The uninit function takes all the above information and computes for each variable name if it is used without being initialized at which line of code:

rel[Varname, Expr] uninit(rel[Varname,Expr] defs, rel[Varname, Expr] uses, Graph[Expr] pred) =
{ <v, e> | <Varname v, Expr e> <- uses,
e in reachX(pred, {root}, defs[v])

Let's give it a try:

rascal>UNINIT = uninit(defs, uses, pred);
rel[str,int]: {
rascal>assert UNINIT == {<"q", 5>, <"y", 6>, <"z", 10>};
bool: true

The unused variables should never be uninitialized:

rascal>UNUSED = domain(defs) - domain(uses);
set[str]: {"p"}
rascal>assert UNUSED == {"p"};
bool: true
rascal>assert UNUSED & UNINIT<0> == {}; // empty intersection
bool: true