Skip to content

Annotated CAST Part 1: Overview

Jump to bottom
jobagy edited this page May 17, 2022 · 84 revisions

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 run_ann_cast_pipeline.py takes a json file that contains the CAST representation of a program and runs a series of passes that transform the CAST to GrFN json. The first pass reads the CAST json file 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 seven passes in the CAST to GrFN pipleline, 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
  • lambda_expression_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.

In addition to the information that will be populated in the attributes of the annotated CAST nodes, there is also "global" state that is incrementally filled out during the passes. The PipelineState class defines the attributes used to hold the global pipeline state. A portion of the class is shown below:

class PipelineState:
    def __init__(self, ann_nodes: typing.List, grfn2_2: bool):
        self.GENERATE_GRFN_2_2 = grfn2_2
        self.nodes = ann_nodes
        # the fullid of a AnnCastName node is a string which includes its
        # variable name, numerical id, version, and scope
        self.fullid_to_grfn_id = {}
        self.grfn_id_to_grfn_var = {}
        ...

The information gathered in the various passes is extensive and includes, for example, the version, scope and GrFN identifier of each variable reference, the variables modified and used by each container, and the GrFN variables used for the interfaces.

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):
        super().__init__(self)
        self.name = name
        self.id = id
        self.source_refs = source_refs
        # the container scope this Name node is contained in
        self.con_scope = None
        # the function scope this Name node is contained in  
        self.base_func_scopestr: str = ""
        # 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, which we call the fullid of the variable. The fullids are used to track the GrFN variables as they are created during the various passes. The following two attributes of the PipelineState object are dictionaries used for this purpose:

        # a map of fullid's to GrFN id's
        self.fullid_to_grfn_id = {}
        # a map of GrFN id's to GrFN variables
        self.grfn_id_to_grfn_var = {}

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.

After traversing all of the CAST nodes and creating the AnnCastNode versions of each node, the cast_to_annotated.py pass instantiates a PipelineState object with a reference to the new annotated CAST and returns this object.

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.

This pass also collects and stores the following additional information needed in later passes:

  • determines the set of global variables in this module
  • determines the set of function definitions in this module
  • for each call, determines if the called function has a function definition (i.e., is not a library function)
  • for each call to a function, determines its invocation index

A function call's invocation index is used to differentiate multiple calls to the same function. The first invocation has index 0, the second invocation has index 1, and so on.

As the nodes are visited, this pass populates two dictionaries:

  • a mapping of calling scopes to AnnCastCall nodes (stored locally and used only in this pass)
  • a mapping of function IDs to AnnCastFunctionDef nodes (stored in the PipelineState object)

The AnnCastCall node has two attributes that are populated in this pass, one for the calling index and one to indicate that the function being called has a function definition:

class AnnCastCall(AnnCastNode):
    def __init__(self, func, arguments, source_refs):
        super().__init__(self)
        self.func: AnnCastName = func
        self.arguments = arguments
        self.source_refs = source_refs

        # the index of this Call node over all invocations of this function
        self.invocation_index: int
        # keep track of whether the Call has an associated FunctionDef
        self.has_func_def: bool = False
        ...

When the AnnCastCall node is visited, we increment the index counter and also add the node to the local dictionary of calling scopes to AnnCastCall nodes. However when visiting the call node, we don't know yet whether the function being called has a function definition (i.e., is defined in this module). All nodes must be visited first to determine that.

When an AnnCastFunctionDef is visited, it is added to the dictionary of id's to AnnCastFunctionDef nodes, which is stored in the following attribute of the PiplelineState object:

        # dict mapping function IDs to their FunctionDef nodes.
        self.func_id_to_def = {}

Once all the nodes have been visited, the dictionary of cached calling scopes to AnnCastCall nodes is processed and the attribute in the AnnCastCall nodes are set according to information in the PiplelineState's dictionary of stored function definitions.

container_scope_pass.py

This pass traverses the annotated CAST to determine scoping information for all variables and containers. 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.

Scoping

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 and this placement is reflected in the scope information for the variable. To illustrate, assuming that this code snippet is the first if in main, the scopes of x and y are shown in the comments:

   if (x > 100)     // x has scope module.main.if0.if-expr
   {
           
       x = x + y;   // x has scope module.main.if0.if-body 
                    // y has scope module.main.if0.if-body 
               
       x = x + 1;   // x has scope module.main.if0.if-body 
                  
   }
   else
   {
       x = x + 100; // x has scope module.main.if0.else-body 
                  
   }

We perform a similar refinement of scopes for loops.

Modified and accessed variables

This pass determines the variables that are accessed, modified, or used by each container. For each container type, the corresponding AnnCastNode has attributes to store this information as well as the scope information for the container itself. Those attributes are shown below:

        # container scope
        self.con_scope: typing.List
        # function scope that this container node is contained in   
        self.base_func_scopestr: str = ""

        # dicts mapping a Name id to string name
        # used for container interfaces
        self.modified_vars: typing.Dict[int, str]
        self.vars_accessed_before_mod: typing.Dict[int, str]
        self.used_vars: typing.Dict[int, str]

For this pass, the visitor methods take arguments for the current scope and also the scope of the function that is currently being processed. This is necessary in order to correctly propagate information about variable usage through the scopes. For example, consider the function in the code snippet below:

int g = 100;
int func(int x){
   int y = 10*x;
   int z = 0;
   if (x > 20)        // x has scope module.func.if0.if-expr
   {
           
       x = x + y;     // x has scope module.func.if0.if-body 
                      // y has scope module.func.if0.if-body 
       if (y > 100)
          g = y + 1;  //g has scope module.func.if0.if-body.if0.if-body
       else:
          z = x + 1;  //z has scope module.func.if0.if-body.if0.else-body        
   }
   else
   ...

It is not known that variable g is modified until we visit that node. At that point, the scope for g is module.func.if0.if-body.if0.if-body. We will update the modified variables attribute of the inner IF container, however we also need to propagate this information back to the enclosing IF container and the enclosing base FUNCTION-DEF container. The variable z will be added to the modified variables attributes of those containers. For local variables, we can stop propagation at the base function level. However, since z is global, we need to propagate that information to the containers of all enclosing scopes, in this case, the container for the module.

In order to determine if a variable is accessed or modified, during the traversal we keep track of whether the current node is on the RHS or LHS of an assignment. In the example above, in the inner if, variables y and x are on the RHS only and consequently will be added to the accessed variables attribute of the container. Variables g and z are on the RHS and will be added to the modified variables attribute of the inner IF container.

A note on implementation details

For ease of access, this pass records the modified, accessed before modified, and used variables for each container in a separate data structure called ContainerData. The class definition is shown below:

class ContainerData:
    modified_vars: typing.Dict[int, str]
    vars_accessed_before_mod: typing.Dict[int, str]
    used_vars: typing.Dict[int, str]

    def __init__(self):
        self.modified_vars = {}
        self.vars_accessed_before_mod = {}
        self.used_vars = {}

As the nodes are visited, any new containers are added to 1) a dictionary that maps container scope strings to ContainerData, and 2) a dictionary that maps container scope strings to container nodes. After visiting all nodes and collecting the variable usage information for all containers, the information in the dictionaries is written to the attributes of the container nodes.

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, continuing with the previous if example, 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.

To illustrate this, recall that the id_collapse pass determines the unique id of each variable. Assume that y has id 1 and x has id 2. A portion of the annotated CAST tree for the code above is shown here:

ex_annCAST

Note that each AnnCastName node is annotated with its variable name, scope, version and id.

To accomplish this, we maintain a dictionary mapping each container scope to a dictionary of the highest variable version for each variable used in that container. When a container is visited, we initialize its dictionary of variable versions to 0 for all of the used variables in the container. When an AnnCastName node is visited, if it is on the LHS of an assignment, we increment the variable version for the variable in the corresponding dictionary of the container scope. The AnnCastName version attribute is set to that version. Otherwise, the AnnCastName node is on the LHS and is being accessed only and not modified. We use the version of the variable that is currently in the container scope's dictionary of variable versions and set the AnnCastName version attribute accordingly.

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 the highest versions of the variables used in the container.

Variable version conventions

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

A container consists of a grouping of primitive boxes and, possibly, nested containers. For example, the container for the if statement above is shown here:

ex_GrFN

In order to represent the GrFN data flow, we must connect the versions of variables coming in to the primitive interfaces and decision nodes with the variable versions coming out of them.

For a decision node of an IF container, the inputs will be the highest versions of each variable along the each possible execution path. The outputs will be version 1 of those variables, with the scope of the IF container. For example, for the decision node in the IF container example above, the inputs are the two possible versions of x of the execution paths:

inputs: x.2.2.module.main.if0.if-body, x.2.1.module.main.if0.else-body

For the outcome of the decision, the convention is that it will always be version 1, and will have the scope of the IF container.

output: x.2.1.module.main.if0

(TODO: more discussion of the convention)

The annotated cast node for the IF container is populated with the fullids of all incoming and outgoing variables for each of its primitive boxes. For this example, the annotated CAST is shown here:

ex_AnnCAST-interfaces

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.

lambda_expression_pass.py

This pass creates the lambda expressions that are used to represent computations in the source code and also those lambda expressions that are required to implement the control flow paths of execution.

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

Clone this wiki locally