How is an assignment expression with return value optimized at assembly level in stack-based virtual machines?

Question

In Java and C# and many common programming languages and runtimes using stack-based virtual machines, we write fundamental assignment expressions as simple as this:

a = 1;

and the compiler initially generates (pseudo) assembly codes (or intermediate language) like this:

PUSHINT 1  # push 1 into the top of evaluation stack
DUP        # duplicate the top of evaluation stack
ST a       # store the value at the top of evaluation stack to variable a
DROP       # drop the top of evaluation stack

instead of

PUSHINT 1
ST a

I believe the reason is that, a=1 is an expression with return value 1. This is used for continuous assignments such as a=b=1. However we cannot always accept the redundant DUP and DROP everywhere.

How are the redundant DUP and DROP automatically deleted in the optimized assembly codes?

en.wikipedia.org/wiki/Peephole_optimization

Hans Passant
– Hans Passant

2024-12-31 01:45:57 +00:00
Commented Dec 31, 2024 at 1:45 — Hans Passant
– Hans Passant, Commented Dec 31, 2024 at 1:45

Holger · Accepted Answer · 2024-09-13 10:59:41Z

This is, how it gets compiled in Java:

import java.util.spi.ToolProvider;
 
interface CompiledForm {
  public static void main(String[] args) {
      int a;
      a = 1;
      showCompiledForm();
  }
 
  private static void showCompiledForm() {
      ToolProvider.findFirst("javap")
        .ifPresent(p -> p.run(System.out, System.err, "-c", "CompiledForm"));
  }
}

Demo on Ideone

Compiled from "Main.java"
interface CompiledForm {
  public static void main(java.lang.String[]);
    Code:
       0: iconst_1
       1: istore_1
       2: invokestatic  #1                  // InterfaceMethod showCompiledForm:()V
       5: return
}

You are assuming a very simple implementation having a tree of expressions where each node has a method to generate the code for that expression. So, to generate the code for a node used as a statement, the compiler would have to call that method, followed by emitting an instruction to drop the result.

But for languages like Java, the AST of a method starts with a block of statements and there are several types of statements which can not be used in an expression context. Expressions may only occur in the context of another construct that uses it.

So the compilers starts traversing a tree of statements, invoking a dedicated method to generate the statement code which does not produce a value in the first place. Those methods may then invoke the methods on expressions to generate expression code.

In case of constructs which can be expressions and statements, like assignments, they may implement both types. This may be done in a generic way like (pseudo code):

class ExpressionStatement implements Statement, Expression {
    @Override // defined in interface Expression
    public void generateExpressionCode() {
      // TODO 
    }
  
    @Override // defined in interface Statement
    public void generateStatementCode() {
      generateExpressionCode();
      generatePopInstruction();
    }
}

and this may indeed be used for some constructs, e.g. method invocations, but it’s easy to imagine how a dedicated sub class, e.g. for assignments, simply implements both methods to generate straight-forward code in either case.

Note that even the opposite exists. Implementations, like for increments, may have a genuine statement implementation and an expression version decorating the statement form:

import java.util.spi.ToolProvider;

interface CompiledForm {
    public static void main(String[] args) {
        showCompiledForm();
    }
  
    static void incrementAsExpression(int input) {
        int x = input++;
    }
  
    static void incrementAsStatement(int input) {
        input++;
    }
  
    private static void showCompiledForm() {
        ToolProvider.findFirst("javap")
          .ifPresent(p -> p.run(System.out, System.err, "-c", "CompiledForm"));
    }
}

Demo on Ideone

Compiled from "Main.java"
interface CompiledForm {
  public static void main(java.lang.String[]);
    Code:
       0: invokestatic  #1                  // InterfaceMethod showCompiledForm:()V
       3: return

  public static void incrementAsExpression(int);
    Code:
       0: iload_0
       1: iinc          0, 1
       4: istore_1
       5: return

  public static void incrementAsStatement(int);
    Code:
       0: iinc          0, 1
       3: return
}

rick roll · Accepted Answer · 2024-09-13 09:35:16Z

Pretty much all stack-based VMs have what is called a stack frame - info on what values a stack contains at a certain point of time. This is the reason why you cannot for example push elements on the stack in a loop - the stack values need to align with the stack frame types. This stack frame in turn allows for a lot of optimizations, but the simplest example is just assigning the pushed value to a variable that represents a stack space. The reason we can do this is that due to the stack frame declarations, for every stack modification we know the structure of the stack in advance. In your case this could look like this:

PUSHINT 1 -> stack1 = 1
DUP       -> stack2 = stack1
ST a      -> a = stack2
DROP      -> # do nothing

From this form, the useless stack1 and stack2 can be easily optimized out and we get just a = 1.

Collectives™ on Stack Overflow

How is an assignment expression with return value optimized at assembly level in stack-based virtual machines?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related