Go Constant Propagation: Optimizing Your Code

Constant propagation is a compiler optimization technique that replaces variable occurrences with their known constant values. This can lead to significant performance improvements by reducing redundant calculations and simplifying code. This challenge will test your understanding of how to implement a basic form of constant propagation for simple arithmetic expressions in Go.

Problem Description

Your task is to implement a function that takes a Go abstract syntax tree (AST) representing a simple program and performs constant propagation. The program will consist of variable declarations and assignments. You should identify variables that are assigned a constant value and then replace subsequent uses of those variables with their constant values.

Key Requirements:

1. Identify Constant Assignments: Detect when a variable is assigned a literal constant value (integers, floats, strings, booleans).
2. Propagate Constants: Replace all occurrences of a variable that has been assigned a constant value with that constant value.
3. Handle Reassignment: If a variable is reassigned a new constant value, update its propagated value accordingly.
4. Ignore Non-Constant Assignments: Do not attempt to propagate values from assignments involving variables, function calls, or complex expressions.
5. Support Basic Types: Handle int, float64, string, and bool literals.
6. Handle Arithmetic Operations: For assignments involving arithmetic operations on constants, evaluate the result and propagate it. For example, if x = 5 + 3, propagate x = 8.

Expected Behavior:

The function should return a modified AST where constant values have been propagated. If an expression can be fully evaluated to a constant after propagation, it should be.

Edge Cases:

• Variables declared but never assigned a value.
• Variables assigned non-constant values and then later assigned constant values.
• Arithmetic operations involving a mix of constants and variables (only evaluate if all operands are constants).
• Division by zero (this should be caught and handled appropriately, perhaps by not propagating or by representing it as an error in the AST).

Examples

Example 1:

Input AST (simplified representation):

[
  {Type: "Decl", Name: "x", Value: {Type: "LiteralInt", Val: 5}},
  {Type: "Decl", Name: "y", Value: {Type: "LiteralInt", Val: 10}},
  {Type: "Assign", Name: "z", Value: {Type: "BinaryExpr", Op: "+", Left: "x", Right: "y"}}
]

Output AST:

[
  {Type: "Decl", Name: "x", Value: {Type: "LiteralInt", Val: 5}},
  {Type: "Decl", Name: "y", Value: {Type: "LiteralInt", Val: 10}},
  {Type: "Assign", Name: "z", Value: {Type: "LiteralInt", Val: 15}}
]

Explanation: x is assigned 5, y is assigned 10. z is assigned x + y. Since both x and y are constants, the expression x + y can be evaluated to 15, and z is then assigned the constant 15.

Example 2:

Input AST:

[
  {Type: "Decl", Name: "a", Value: {Type: "LiteralInt", Val: 3}},
  {Type: "Assign", Name: "b", Value: {Type: "LiteralInt", Val: 7}},
  {Type: "Assign", Name: "a", Value: {Type: "BinaryExpr", Op: "*", Left: "a", Right: {Type: "LiteralInt", Val: 2}}}, // Reassignment
  {Type: "Assign", Name: "c", Value: {Type: "BinaryExpr", Op: "-", Left: "b", Right: "a"}}
]

Output AST:

[
  {Type: "Decl", Name: "a", Value: {Type: "LiteralInt", Val: 6}}, // 'a' is updated
  {Type: "Assign", Name: "b", Value: {Type: "LiteralInt", Val: 7}},
  {Type: "Assign", Name: "a", Value: {Type: "LiteralInt", Val: 6}}, // The reassignment itself is simplified
  {Type: "Assign", Name: "c", Value: {Type: "LiteralInt", Val: 1}}  // 'c' is calculated using propagated values (7 - 6)
]

Explanation: a starts as 3. b is assigned 7. a is reassigned a * 2. Since the current a is 3, this evaluates to 6. c is assigned b - a. Propagating the current values of b (7) and a (6), c becomes 7 - 6 = 1. The reassignment to a itself is also simplified to its constant value.

Example 3: (Handling non-constant assignments)

Input AST:

[
  {Type: "Decl", Name: "val1", Value: {Type: "LiteralInt", Val: 10}},
  {Type: "Decl", Name: "val2", Value: {Type: "LiteralInt", Val: 2}},
  {Type: "Decl", Name: "varA", Value: {Type: "LiteralInt", Val: 5}},
  {Type: "Assign", Name: "result1", Value: {Type: "BinaryExpr", Op: "/", Left: "val1", Right: "val2"}},
  {Type: "Assign", Name: "result2", Value: {Type: "BinaryExpr", Op: "*", Left: "varA", Right: {Type: "Variable", Name: "unknownVar"}}} // Non-constant operand
]

Output AST:

[
  {Type: "Decl", Name: "val1", Value: {Type: "LiteralInt", Val: 10}},
  {Type: "Decl", Name: "val2", Value: {Type: "LiteralInt", Val: 2}},
  {Type: "Decl", Name: "varA", Value: {Type: "LiteralInt", Val: 5}},
  {Type: "Assign", Name: "result1", Value: {Type: "LiteralInt", Val: 5}}, // Propagated: 10 / 2 = 5
  {Type: "Assign", Name: "result2", Value: {Type: "BinaryExpr", Op: "*", Left: {Type: "Variable", Name: "varA"}, Right: {Type: "Variable", Name: "unknownVar"}}} // Not simplified as 'unknownVar' is not a constant
]

Explanation: result1 is simplified to 5 because val1 and val2 are constants. result2 is not simplified because unknownVar is not a constant, even though varA is. The AST for varA is kept as is in the expression for result2 because we only propagate when all operands are constants.

Constraints

• The input AST will be a slice of structs/objects representing Go statements. You'll need to define a suitable Go AST representation for this challenge.
• Statements will include variable declarations and assignments.
• Assignments will be of the form variable = expression.
• Expressions can be:
  • Literal values (integers, floats, strings, booleans).
  • Binary operations (+, -, *, /, %) between two operands.
  • References to other variables.
• Integer division should behave like Go's standard integer division (truncating towards zero).
• Division by zero in an arithmetic expression should result in the expression not being evaluated to a constant and instead remain as is (or be marked with an error if your AST supports it).
• The implementation should be reasonably efficient, though extreme performance optimization is not the primary goal.

Notes

• You'll need to define the Go data structures (structs) to represent the AST. Consider how to represent expressions, literals, and variable references.
• A map can be a useful data structure to keep track of the current constant values of variables as you traverse the AST.
• Think about the order of operations when evaluating expressions.
• Consider a recursive approach for traversing and transforming the AST.
• The problem focuses on the propagation aspect. You don't need to handle complex Go syntax like control flow (if statements, loops), function calls, or complex types beyond basic literals.