Visitor pattern and compiler code generation, how to get children attributes?

Question

I'd like to modify my compiler's code generator to use visitor pattern since the current approach must use multiple conditional statement to check the real type of a child before generating the corresponding code. However, I have problems to get children attributes after they're visited. For instance, in binary expression I use this:

LHSCode := GenerateExpressionCode(LHSNode);
RHSCode := GenerateExpressionCode(RHSNode);
CreateBinaryExpression(Self,LHS,RHS);

In visitor pattern the visit method is usually void, so I can't get the expression code from LHS and RHS. Keeping shared global variables isn't an option since expression code generation is recursive thus could erase previous values kept in the variables.

I'll just show the binary expression as this is the most complicated part (for now):

function TLLVMCodeGenerator.GenerateExpressionCode(
  Expr: TASTExpression): TLLVMValue;
var
  BinExpr: TASTBinaryExpression;
  UnExpr: TASTUnaryExpression;
  LHSCode, RHSCode, ExprCode: TLLVMValue;
  VarExpr: TASTVariableExpression;
begin
  if Expr is TASTBinaryExpression then begin
    BinExpr := Expr as TASTBinaryExpression;
    LHSCode := GenerateExpressionCode(BinExpr.LHS);
    RHSCode := GenerateExpressionCode(BinExpr.RHS);
    case BinExpr.Op of
      '<': Result := FBuilder.CreateICmp(ccSLT, LHSCode, RHSCode);
      '<=': Result := FBuilder.CreateICmp(ccSLE, LHSCode, RHSCode);
      '>': Result := FBuilder.CreateICmp(ccSGT, LHSCode, RHSCode);
      '>=': Result := FBuilder.CreateICmp(ccSGE, LHSCode, RHSCode);
      '==': Result := FBuilder.CreateICmp(ccEQ, LHSCode, RHSCode);
      '<>': Result := FBuilder.CreateICmp(ccNE, LHSCode, RHSCode);
      '/\': Result := FBuilder.CreateAnd(LHSCode, RHSCode);
      '\/': Result := FBuilder.CreateOr(LHSCode, RHSCode);
      '+': Result := FBuilder.CreateAdd(LHSCode, RHSCode);
      '-': Result := FBuilder.CreateSub(LHSCode, RHSCode);
      '*': Result := FBuilder.CreateMul(LHSCode, RHSCode);
      '/': Result := FBuilder.CreateSDiv(LHSCode, RHSCode);
    end;
  end else if Expr is TASTPrimaryExpression then
    if Expr is TASTBooleanConstant then
      with Expr as TASTBooleanConstant do
        Result := FBuilder.CreateConstant(Ord(Value), ltI1)
    else if Expr is TASTIntegerConstant then
      with Expr as TASTIntegerConstant do
        Result := FBuilder.CreateConstant(Value, ltI32)
    else if Expr is TASTUnaryExpression then begin
      UnExpr := Expr as TASTUnaryExpression;
      ExprCode := GenerateExpressionCode(UnExpr.Expr);
      case UnExpr.Op of
        '~': Result := FBuilder.CreateXor(
            FBuilder.CreateConstant(1, ltI1), ExprCode);
        '-': Result := FBuilder.CreateSub(
            FBuilder.CreateConstant(0, ltI32), ExprCode);
      end;
    end else if Expr is TASTVariableExpression then begin
      VarExpr := Expr as TASTVariableExpression;
      with VarExpr.VarDecl do
        Result := FBuilder.CreateVar(Ident, BaseTypeLLVMTypeMap[BaseType]);
    end;
end;

Hope you understand it :)

Answer 1

In visitor pattern the visit method is usually void, so I can't get the expression code from LHS and RHS. Keeping shared global variables isn't an option since expression code generation is recursive thus could erase previous values kept in the variables.

You need to get child attributes when they're visited, hold onto any attributes you need and ensure that you still have them when you need them. That may make the internal structure of your visitor a bit more complex, but it's certainly feasible. Code generation is definitely a common use of the Visitor pattern.

Usually you don't have to hold on to attributes, but you do need to hold onto intermediate results and combine them into other intermediate results in visits to other objects. I think this is the case here, but the interaction is complex enough to be a bit confusing.

I'm not an expert on Object Pascal, so rather than trying to write actual code, I'll just describe how I would handle it.

In this case, I would probably use a stack holding onto intermediate results.

Traversal order can be driven in the nodes' accept methods or in the visitor's visit methods or in an external iterator. For simplicity, I'll assume its in the accept methods.

In the accept method of the simple objects, you would simply do the standard visitor.visit(this) (however you say that in Object Pascal).

In the visit method for simpler objects like your TASTBooleanConstant you would call the appropriate method, in this case FBuilder.CreateConstant with values that you pull from the object and push the result of that method onto the visitor's stack.

In the accept method of a more complex object like your TASTBinaryExpression, you would first call the accept methods on the children and then do the standard visitor.visit(this), ensuring that the children are visited first.

Then, since the children were visited first, their results should be on the stack when the visit method for the complex object is called. In that visit method, you would pop the appropriate results off the stack into local variables, call the appropriate FBuilder.CreateXxx method based on which operator you have, passing those values as parameters, and put the result onto the stack.

For the TASTUnaryExpression objects it would be similar, but with only one child to worry about in the accept method, and only one intermediate result to pop off the stack and use in the visit method.

In your client code, you create the visitor and call the accept method of your top node passing the visitor as argument. After all the recursion is done, the stack should contain only the final result, and the visitor class should provide a getResult method allowing the client to retrieve it.

Sorry this is so long-winded - it might be clearer in code, but hopefully this gives you an idea of how to deal with this.

A good resource for learning how refactor to introduce patterns in existing code like this is Joshua Kerievsky's book Refactoring to Patterns.