Annotated CAST Part 1: Overview

Annotated CAST Passes Overview

Note: 'pass' has a conventional use in language implementation and compilers to denote a pass across the data structure that infers additional properties based on existing properties, and adds those new properties in-place in the data structure or as part of new data structure.

The Python script cast_to_annotated.py reads a JSON file that contains the CAST representation of a program and transforms it to annotated CAST. It then calls a series of additional passes that each augment the information in the annotated CAST nodes in preparation for the GrFN generation. The final pass uses the information in the annotated CAST to generate the GrFN json and the visual representation.

There are currently five passes in this process, implemented in the following .py files:

• cast_to_annotated.py
• id_collapse_pass.py
• container_scope_pass.py
• variable_version_pass.py
• grfn_var_creation_pass.py
• to_grfn_pass.py

cast_to_annotated.py

This pass traverses the CAST nodes and generates an annotated cast version of the CAST. It does this by copying each CAST node to a corresponding AnnCastNode which has additional attributes (fields) that are used in later passes to maintain information for GrFN generation. The information gathered in the various passes includes, for example, the variables modified and used by each container, and the version, scope and GrFN identifier of each variable reference.

TODO: what are the additional attributes for Annotated CAST? This information should be somewhere, along with CAST node attributes

The code below shows the annotated cast for a CAST Name node:

class AnnCastName(AnnCastNode):
    def __init__(self, name, id, source_refs):
        self.name = name
        self.id = id
        self.source_refs = source_refs
        # container_scope is used to aid GrFN generation
        self.con_scope = None
        # versions are bound to the scope of the variable
        self.version = None
        self.grfn_id = None

Ultimately, each reference to a variable held in an AnnCastName node is disambiguated by its variable name, numerical id, version, and scope. We call this the fullid of the variable and track the fullids in the following two attributes of the primary AnnCastNode:

        self.grfn_id_to_grfn_var = {}
        # the fullid of a AnnCastName node is a string which includes its
        # variable name, numerical id, version, and scope
        self.fullid_to_grfn_id = {}

The annotated cast for a node representing a container must maintain extensive information for GrFN generation. Each of the container types have attributes for the following:

• the modified, accessed, and used variables
• the container scope
• the highest versions of all variables used in the container
• dictionaries for each of the interfaces required by the container that map variable ids to their fullids

id_collapse_pass.py

The GCC compiler maps all variable names to unique numerical identifiers, which is required to correctly disambiguate global and local variables that use the same name (i.e., a local variable x versus a global variable x). However, the ids generated are overly long, which complicates manual inspection and debugging.

During this pass, we collapse the variable ids (stored in AnnCastName nodes) to numbers that start at zero and increase as needed.

container_scope_pass.py

As mentioned, we distinguish each instance of a variable reference with its fullid, which consists of the variable name and its numerical id, version, and scope. For GrFN, the normal meaning of scope is augmented with container scoping information. For example, variable x appearing in an if body in main would have the scope module.main.if0-ifbody, whereas variable x appearing in a nested if body in main would have the scope module.main.if0.if-body.if0.if-body.

This pass traverses the annotated CAST to determine scoping information for all containers and variables. In addition, for each container, it keeps track of which variables are modified or accessed within the container and modifies the container attributes accordingly.

variable_version_pass.py

TODO:(Describe variable version scheme.) Within a container, each variable starts at version 0. If the variable is assigned to within that container scope, its version increases. For example, assuming that this code snippet is the first if in main, the variable versions of x are shown in the comments:

   if (x > 100)     # x ver 0 id 1 in module.main.if0.if-expr
   {
           
       x = x + y;   # x ver 0 id 1  module.main.if0.if-body (on RHS)
                    # x ver 1 id 1  module.main.if0.if-body (on LHS)
               
       x = x + 1;   # x ver 1 id 1  module.main.if0.if-body (on RHS)
                    # x ver 2 id 1  module.main.if0.if-body (on LHS)
   }

This pass determines the correct version of each instance of a variable reference and stores that version in the respective AnnCastName node. In addition, each container has an attribute to store the highest versions of the variables seen in that container scope. This pass stores that information for each container. TODO: Mention that we distinguish highest versions along different branches, etc. This allows us to retain most (all?) of the lexical scoping information that would be lost if we only had container scope.

grfn_var_creation_pass.py

to_grfn_pass.py

Annotated CAST Passes Details

Prototype for new Annotated Cast pass:

Each pass does a traversal of the annotated CAST, which means that code for the visitor pattern is repeated on any given pass. To facilitate implementing a new pass, we have a prototype of the visitor code that can be used as a starting point for a new pass. This is in the branch in the file ann_cast_prototype.py.

(TODO: Instead remove this here and instead add pointer ann_cast_prototype.py as that is the reference implementation.)