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 six 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.

The specific attributes for each annotated cast node are shown in Part 3. As an example, however, the code below shows the annotated cast class definition for an AnnCastName 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 represented by 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

There are containers for if statements, loops, and function definitions/calls. (TODO: make a naming convention for these container types.)

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 as shown above) to numbers that start at zero and increase as needed.

container_scope_pass.py

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.

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. The scoping information created for function definition and call containers follows typical scoping rules. For example, all functions in C are contained in the top-level namespace which we call module. The scopes for x and y in the snippet below are shown in the comments:

int main(){
   int x = 10;   // x has scope module.main
   int y = 0;    // y has scope module.main
   ...
}

However, the scopes for variables occurring in if and loop containers are refined to include the lexical context of where the variable occurs in the container. This refinement of scoping is used to make variable versions unique to the execution path.

For example, variable x appearing in an if body in main would have the scope module.main.if0.if-body, whereas variable x appearing in the else body would have the scope module.main.if0.else-body. We perform a similar refinement of scopes for loop containers.

variable_version_pass.py

The version of a variable is dependent on its container scope and the number of assignments made to that variable within the scope. This pass determines the version of each variable reference and stores that version in its respective AnnCastName node. In addition, each container has attributes to store the highest versions of the variables seen in that container scope. This pass stores that information for each container.

Within a container, each variable starts at version 0. If the variable is assigned to within that container scope, its version increases. This pass traverses the annotated CAST to determine scoping information for all containers and variables. Recall that for if and loop containers, the scopes make explicit the lexical context of the container the variable appears in. For example, x occurring in the body of an if statement has a different scope from x occurring in the else body and this affects the versioning of those variables.

For example, assuming that this code snippet is the first if in main, the scopes and variable versions of x are shown in the comments:

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

The AnnCastName nodes for x will be annotated with the correct versions during this pass.

This pass also determines the highest versions all variables used in each lexical context of the container and stores that information in the attributes of the container. In the above example, we see that the highest version of x in the if-body is version 2, and the highest version of x in the else-body is 1.

To maintain this information, the AnnCastModelIf node has the following attributes:

        self.expr_highest_var_vers = {}
        self.ifbody_highest_var_vers = {}
        self.elsebody_highest_var_vers = {}

Other containers have analogous attributes to maintain this information.

grfn_var_creation_pass.py

(NOTE: at this point, we want to create the GrFN graphs and are not concerned with the lambda's that are required for execution.)

To make a GrFN VariableNode, we need

• VariableIdentifier:
  • namespace: str
  • scope: str
  • var_name: str
  • index: int (which is the version attribute in AnnCastName nodes)
  • metadata: List[TypedMetadata] (for now just an empty list)

In Loop and Conditional containers, we will need to store the same GrFN VariableNodes at different AnnCastName nodes. For example, the version 0 of a variable in the If scope should be used for version 0 of ifbody and elsebody scope.

We also want to start on what VariableNodes will be on each side of an interface or decision node, and create the condtional VariableNodes.

Goal: At the end of this pass, we will have created all VariableNodes that will be used in the GrFN. We will also have made note of what VariableNodes are used at container interfaces, container decision nodes, and container conditional nodes.

to_grfn_pass.py