Implementing Basic Escape Analysis in Go

Escape analysis is a compiler optimization technique that determines whether a variable's memory can be allocated on the stack or must be allocated on the heap. Stack allocation is significantly faster and more memory-efficient. This challenge involves understanding and simulating a simplified version of escape analysis in Go.

Problem Description

Your task is to implement a simplified escape analysis mechanism for a subset of Go code. You will be given a representation of Go functions and their variable declarations and assignments. Your goal is to determine for each variable whether it "escapes" the function it's declared in. A variable escapes if its lifetime extends beyond the execution of the function. This typically happens when a variable is returned, used in a closure, or passed by pointer to another function that might outlive the current one.

You should create a system that can analyze a program's structure and output which variables escape.

Key Requirements:

• Input Representation: You will receive a structured representation of Go functions, including variable declarations, assignments, and function calls.
• Escape Rules: Implement the following simplified escape rules:
  • A variable declared on the stack escapes if its address is taken and:
    • It is returned from the function.
    • It is assigned to a global variable.
    • It is passed by reference to another function that is known to escape (e.g., a hypothetical print_address function).
    • It is captured in a closure (for simplicity, we'll consider any variable used within an anonymous function as potentially escaping).
  • Variables that do not meet any of the above conditions are considered stack-allocated and do not escape.
• Output: For each function, provide a list of variables that escape.

Expected Behavior:

The analysis should accurately identify variables that are allocated on the heap due to their lifetime extending beyond the current function's scope.

Edge Cases:

• Nested function calls.
• Variables declared but not used.
• Variables assigned to themselves (no escape).
• Complex data structures (for this challenge, assume simple primitive types or pointers to them).

Examples

Example 1:

Input Program Representation:

Function: foo
  Variables:
    x: int (declared locally)
    y: *int (declared locally)

  Statements:
    assign x = 10
    assign y = &x
    return y

Output:

foo:
  x: escapes
  y: escapes

Explanation: x escapes because its address is taken and it is returned (via y). y escapes because it is the return value.

Example 2:

Input Program Representation:

Function: bar
  Variables:
    a: int (declared locally)
    b: int (declared locally)

  Statements:
    assign a = 5
    assign b = a

Output:

bar:
  a: does not escape
  b: does not escape

Explanation: a and b are simple local variables whose lifetimes are confined to the bar function. Their addresses are not taken, and they are not returned or used in closures.

Example 3:

Input Program Representation:

Function: baz
  Variables:
    ptr_to_z: *int (declared locally)

  Closures:
    anon_func:
      Uses: z (external variable)
      Statements:
        assign *ptr_to_z = z

  Statements:
    z: int (declared locally)
    assign z = 20
    assign ptr_to_z = &z
    execute anon_func

Output:

baz:
  ptr_to_z: escapes
  z: escapes

Explanation: z escapes because it is used in an anonymous function that is executed within baz. ptr_to_z escapes because it points to z, which itself escapes, and its address is taken.

Constraints

• The input program representation will be a predefined Go struct or a JSON format that you will parse.
• Assume only basic types (int, bool, etc.) and pointers to them.
• Function calls are limited to hypothetical built-in functions (like print_address) or other defined functions within the input.
• The analysis depth will be limited to a few levels of nested calls.
• Focus on the logic of escape analysis, not on parsing complex Go syntax.

Notes

• You will likely need to define data structures to represent functions, variables, and statements.
• A recursive approach or a worklist algorithm can be useful for propagating escape information.
• Consider how to track the "address taken" status of variables.
• For simplicity, assume that any variable passed by pointer to a function that could potentially outlive the current scope (e.g., print_address) will escape.
• The definition of "closure" for this challenge is simplified: any variable from the outer scope used within an anonymous function definition is considered to be captured and thus potentially escaping.