Skip to content

Annotated CAST Part 1: Overview

Jump to bottom
jobagy edited this page May 18, 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_vars 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_before_mod attribute of the container. Variables g and z are on the RHS and will be added to the modified_vars 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 the following two dictionaries: 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. The variable versioning is critical to linking the GrFN variables in later passes.

This pass performs the following 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
  • creates GrFN variables for modified variables
  • creates GrFN variables for the arguments and parameters of function calls and the return value of a function (if present)

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

A container consists of a grouping of primitive nodes 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 nodes, i.e., the top interface, conditional, decision, and bottom interface nodes with the variable versions coming out of them.

For the top interface of the IF container the inputs will be the current highest version of the variables in the enclosing scope. By convention, the versions of the variables coming out of the interface will be version 0 in the current if0 scope. For the decision, the versions of the variables coming out will be version 1 in the current if0 scope.

To illustrate this, we will use the if expression example above. We can see from the annotated CAST that the current highest versions of x and y coming in to the if from the enclosing scope are x.2.2.module.main_id0 and y.1.2.module.main_id0 respectively. The IF top interface will have the following input and output variables:

  • inputs: x.2.2.module.main_id0, y.1.2.module.main_id0
  • outputs: x.2.0.module.main_id0.if0, y.1.0.module.main_id0.if0

The outputs of the top IF interface will propagate to the if conditional expression, the if body, and the else body.

For a decision node of an IF container, the inputs will be the highest versions of each variable along each possible execution path. 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 outputs of the decision, per the convention, the versions will always be version 1 and will have the scope of the IF container. In this case, there is a single output shown below:

  • output: x.2.1.module.main.if0

In addition, the outputs of the top IF interface will propagate to the if conditional expression, the if body, and the else body. (TODO: explain top_interface_vars and the bot_interface_vars, i.e., the top_interface_vars are the used_vars of the container and the bot_interface_vars are the modified_vars.)

Interfaces

The GrFN node types that have input and output variables as described above are the following:

  • interface
  • loop top interface
  • condition
  • decision

For ease of discussion, we loosely refer to all of these as interfaces. The AnnCast nodes of the container types each have attributes to store the variables of their respective interfaces. For example, the AnnCastModelIf node has the following additional attributes:

        # dicts mapping a variable id to its fullid
        self.top_interface_in = {}
        self.top_interface_out = {}
        self.bot_interface_in = {}
        self.bot_interface_out = {}
        self.condition_in = {}
        self.condition_out = {}
        self.decision_in = {}
        self.decision_out = {}

As the comment indicates, the attributes store dictionaries mapping variable id's to fullids. For the if example above, the top interface is populated as shown below:

  • top_interface_in is {2: x.2.2.module.main_id0, 1: y.1.2.module.main_id0}
  • top_interface_out is {2: x.2.0.module.main_id0.if0, 1: y.1.0.module.main_id0.if0 }

GrFN variables

The GrFN is a data flow representation of the original source file. As such, the GrFN is a collection of nodes with directed edges representing the data flow. During this pass, we begin to create some of the nodes of the GrFN, specifically, a subset of the variable nodes.

A GrFN variable is represented by the VariableNode class, which is defined in networks.py. It consists of the following components:

  • VariableIdentifier: a GrFN identifier
    • namespace: str
    • scope: str
    • var_name: str
    • index: int (which is the version attribute in AnnCastName nodes)
    • metadata: List[TypedMetadata]

(TODO: explain making the GrFNs for arguments/calls and the modified variables.)

grfn_var_creation_pass.py

In this pass, we will complete the creation of all of the nodes that represent GrFN variables.

Specifically, this pass will

  • create GrFN variables nodes for all remaining variables
  • create the GrFN variables for the conditionals
  • record which GrFN variables are used at container interfaces, container decision nodes, and container conditional nodes
  • alias the GrFB variables across container scopes

The remaining GrFN nodes for the interfaces, decisions, and conditions will be created in later passes.

(Note: 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.)

TODO: Move this to the correct place. 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 by the end of this pass. The annotated CAST with the fully populated IF interface is shown here:

ex_AnnCAST-interfaces

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.

Clone this wiki locally