Writing analyses using McSAF

This page gives a tutorial on how to write analysis using McSAF. We will start with a simple Name Collector, which collects the names of the variables on the LHS. Next we will implement a reaching definitions analysis. Note that we assume knowledge of Java and theoretical knowledge of compiler analyses. ###Name Collector Analysis The analysis for collecting the names is fairly straightforward. We do not require a fixed point to implement it. Hence, we will be using the AbstractDepthFirstAnalysis[1]. We start by extending the AbstractDepthFirstAnalysis class.

public class NameCollector extends AbstractDepthFirstAnalysis<Set<Name>> 

We call our analysis class NameCollector. AbstractDepthFirstAnalysis uses generics to define the type of the data structures used to hold the information collected from the analysis. In this case, we use a set of Name objects. The name class is a node of the McSAF AST.

Next we declare the class members that we need for the analysis.

protected Set<Name> fullSet;
protected boolean inLHS = false;

We define constructors for the class.

public NameCollector(ASTNode<?> tree)
    {
        super(tree);
        fullSet = newInitialFlow();
    }

The method newInitialFlow() is an abstract method from the AbstractDepthFirstAnalysis class which we are required to implement.

 @Override
    public Set<Name> newInitialFlow()
    {
        return new HashSet<>();
    }

We then define public methods to allow other classes to access the collected names.

public Set<Name> getAllNames()
    {
        return fullSet;
    }
    public Set<Name> getNames( AssignStmt node )
    {
      return flowSets.get(node);
    }

AbstractDepthFirstAnalysis provides a method for every node in the McSAF AST and defines the default behaviour for each of them. We will override the methods that we require to collect the names, namely, caseAssignStmt, caseParameterizedExpr, caseCelIndexExpr, caseDotExpr, caseFunction, caseGlobalStmt.

Let us look at the implementation of each method.

Assignment Statement

 @Override
    public void caseAssignStmt( AssignStmt node )
    {
        inLHS = true;
        currentSet = newInitialFlow();
        analyze( node.getLHS() );
        flowSets.put(node,currentSet);
        fullSet.addAll( currentSet );
        inLHS = false;
    }

In the above method, we set the class member variable inLHS to true. inLhs is used to ensure that only names that are on the LHS of the statements are collected. Members flowSets and currentSet are inherited through the AbstractDepthFirstAnalysis class. flowSets is a map which maps a ASTNode to its equivalent set of names. Note that the the type of the value in the map can differ depending on the generic type that is provided. currentSet is used to hold the set of names for the current node. fullSet is a member defined in this class and is a set of all the names on the LHS in the AST.

Index Operations

    @Override
    public void caseParameterizedExpr( ParameterizedExpr node )
    {
        analyze(node.getTarget());
    }

    @Override
    public void caseCellIndexExpr(CellIndexExpr node) {
      analyze(node.getTarget());
    }

    @Override
    public void caseDotExpr(DotExpr node) {
      analyze(node.getTarget());
    }

The above methods all traverse down to the child node referring to the index variable. For example, in case of the parametrised expression a(i), we traverse down the node referring to a.

Functions

    @Override
    public void caseFunction(Function f) {
      for (Name name : f.getInputParams()) {
        currentSet.add(name);
      }
      fullSet.addAll(currentSet);
      analyze(f.getStmts());
      analyze(f.getNestedFunctions());
    }

In case of functions, we analyse the input parameters, function body and the nested functions.

Global Statement

    @Override
    public void caseGlobalStmt(GlobalStmt node) {
      for (Name name : node.getNames()) {
        currentSet.add(name);
      }
      fullSet.addAll(currentSet);
    }

For the global statement, we analyse use the getNames method to fetch all the names and add them to the currentSet and the fullSet.

You can find the full code for this analysis here