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. There are containers for if statements, loops, and function definitions. We will refer to these container types respectively as IF, LOOP, and FUNCTION_DEF containers. In the annotated CAST, the respective node types are AnnCastModelIf, AnnCastLoop, and AnnCastFunctionDef.

The specific attributes needed for each type of container differ according to the semantics of container, however, some of the common attributes are 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

Refer to Part 3 for a detailed listing of the attributes of each container type.

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 stores that in 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-DEF containers follows the scoping rules of the source language. 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
   ...
}

The scoping information for IF and LOOP containers are refined to include the lexical context of where a variable occurs in the container. This refinement of scoping is used to make variable versions unique to the execution path.

For example, in an if statement, a variable can occur in the if expression, the if body, or the else body. A 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 loops.

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 that scope and its specific lexical point of reference. This pass performs three tasks:

• determines the version of each variable reference and stores that version in its respective AnnCastName node
• stores the highest versions of the variables seen in each container scope
• starts to populate the inputs and outputs of container interfaces

Variable versions

Within a container, each variable starts at version 0. If the variable is assigned to within that container scope, its version increases. Also, recall that 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.

To illustrate, 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.

Recall that the id_collapse pass determines the unique id of each variable. In the code snippet above, x has id 1 and y has id 0. A portion of the annotated CAST tree for the code above is shown here:

Highest variable version within a container

Once the container has been visited, we know the highest version of each variable used in the container (and also for each branch of an IF or LOOP container). In the example above, the highest version of x in the if expression is version 0, the highest version of x in the body is version 2, and the highest version of x in the else is 1.

To maintain this information, the AnnCastModelIf node for the IF container 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.

Interface variable version conventions

(TODO: Note that it is not just interfaces that need to know versions for inputs and outputs, but also decisions, etc. Will fix the phrasing here when the primitive "boxes" have been defined.)

The version information of the variables lays the foundation for creating the interfaces needed for the containers and the ability to link the versions going into an interface with the versions of the variables leaving the interface. Consider the GrFN for the example above:

For the decision node, the two possible versions of x will be the inputs (as well as the condition variable). In general, the inputs will be the highest versions of each variable along each possible path. For the outcome of the decision, the convention is that it will always be version 1, with the scope of the IF container. (Need to show an the decision node, or show the entire example for ex.c)

grfn_var_creation_pass.py

In order to create the GrFN, we must

(TODO: Provide an intro to this section.)

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 conditional 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

This pass uses the GrFN variables created previously to create a NetworkX graph. All of the GrFN variables are added as nodes to a NetworkX directed graph. The annotated cast is then traversed in order to create the additional nodes needed for containers (i.e., interfaces, decisions, and conditions) and for assignments. The information stored at each annotated cast node of a container or assignment is used to add the necessary edges to the directed graph.

(Thought: perhaps we could start with a list the components of the GrFN graph (interface, decision, assignment, etc.) and then describe the mapping from language construct to its GrFn components (i.e., if statement to the GrFN components use to represent it.)