Gradual Notes

Recent Writing

Recent Notes

YARV Stack Manipulation Instructions

9 min read

source

Beyond the basic push instructions that place values onto the stack data structure, YARV provides a sophisticated set of stack manipulation instructions that reorder, duplicate, and remove values. These instructions are essential for complex operations like method calls, variable assignments, and control flow.

Why Stack Manipulation Matters

In a stack-based virtual machine, the order and position of values on the stack determines how operations execute. Consider a simple assignment:

x = 5

This seemingly simple operation requires careful stack orchestration:

  1. Push the value 5 onto the stack
  2. Duplicate it (one copy for the assignment, one for the expression result)
  3. Store one copy in the local variable x
  4. Leave the other copy on the stack as the expression’s return value

Stack manipulation instructions enable this precise control over value positioning and lifetime.

Removal Instructions

pop - Discarding Values

The pop instruction removes and discards the top value from the stack. This is the simplest cleanup operation.

Pseudocode:

# instruction: pop
stack.pop  # Remove and discard top value

Stack visualization:

Before pop:              After pop:
┌─────────────┐         ┌─────────────┐
│     42      │ ← top   │    "hi"     │ ← top
├─────────────┤         ├─────────────┤
│    "hi"     │         │    :sym     │
├─────────────┤         └─────────────┘
│    :sym     │
└─────────────┘

Use cases:

  • Cleaning up intermediate values
  • Discarding unused expression results
  • Maintaining stack discipline in methods and blocks

Example:

# Ruby code:
puts "hello"
 
# YARV instructions (simplified):
putstring "hello"    # Push "hello"
send :puts           # Call puts, pushes return value (nil)
pop                  # Discard the nil return value

The pop ensures the stack remains balanced after the method call.

adjuststack - Bulk Removal

The adjuststack instruction removes multiple values from the stack in a single operation. This is more efficient than multiple pop instructions.

Pseudocode:

# instruction: adjuststack number
stack.pop(number)  # Remove 'number' values from stack

Stack visualization:

adjuststack 3:

Before:                  After:
┌─────────────┐         ┌─────────────┐
│     "d"     │ ← top   │     "a"     │ ← top
├─────────────┤         └─────────────┘
│     "c"     │
├─────────────┤
│     "b"     │
├─────────────┤
│     "a"     │
└─────────────┘

Performance benefit:

Instead of:

pop
pop
pop

YARV uses:

adjuststack 3

This reduces instruction count and improves bytecode density.

Use cases:

  • Cleaning up after exception handling
  • Discarding multiple temporary values
  • Optimizing stack cleanup in loops

Duplication Instructions

dup - Single Value Duplication

The dup instruction duplicates the top value on the stack, creating an exact copy. This is crucial for operations that both consume and return a value.

Pseudocode:

# instruction: dup
stack.push(stack.last)  # Push copy of top value

Stack visualization:

Before dup:             After dup:
┌─────────────┐        ┌─────────────┐
│     42      │ ← top  │     42      │ ← top (copy)
├─────────────┤        ├─────────────┤
│    :sym     │        │     42      │ (original)
└─────────────┘        ├─────────────┤
                        │    :sym     │
                        └─────────────┘

Critical use case - Variable assignment:

x = 5  # Assignment returns the assigned value

YARV instructions:

putobject 5    # Stack: [5]
dup            # Stack: [5, 5]
setlocal x     # Stack: [5]  (one copy stored in x)
               # Stack top (5) is the expression result

Without dup, the assignment would consume the value, leaving nothing for the expression to return.

Other use cases:

  • Chained assignments: x = y = 5
  • Method chaining preserving receiver
  • Conditional operations that inspect values

Mermaid diagram - Assignment flow:

graph TD
    A[Push value 5] --> B[dup instruction]
    B --> C[Two copies on stack]
    C --> D[One copy → variable x]
    C --> E[One copy → expression result]

    style A fill:#e1f5ff
    style B fill:#fff4e1
    style D fill:#e8f5e9
    style E fill:#e8f5e9

dupn - Multiple Value Duplication

The dupn instruction duplicates the top n values on the stack. This handles complex scenarios like multiple assignment.

Pseudocode:

# instruction: dupn number
values = stack.last(number)
stack.push(*values)

Stack visualization:

dupn 2:

Before:                    After:
┌─────────────┐           ┌─────────────┐
│     "b"     │ ← top     │     "b"     │ ← top (copy)
├─────────────┤           ├─────────────┤
│     "a"     │           │     "a"     │ (copy)
├─────────────┤           ├─────────────┤
│     42      │           │     "b"     │ (original)
└─────────────┘           ├─────────────┤
                          │     "a"     │ (original)
                          ├─────────────┤
                          │     42      │
                          └─────────────┘

Use case - Multiple assignment:

x, y = 1, 2

The multiple values need to be duplicated so they can be:

  1. Assigned to variables x and y
  2. Returned as the expression result [1, 2]

Efficiency consideration:

dupn 3 is more efficient than:

topn 2
topn 1
topn 0

Single instruction vs three instructions reduces both execution time and bytecode size.

Reordering Instructions

swap - Exchanging Top Two Values

The swap instruction exchanges the positions of the top two stack values. This is essential for operations where argument order matters.

Pseudocode:

# instruction: swap
b = stack.pop
a = stack.pop
stack.push(b)
stack.push(a)

Stack visualization:

Before swap:            After swap:
┌─────────────┐        ┌─────────────┐
│     "y"     │ ← top  │     "x"     │ ← top
├─────────────┤        ├─────────────┤
│     "x"     │        │     "y"     │
├─────────────┤        ├─────────────┤
│     42      │        │     42      │
└─────────────┘        └─────────────┘

Critical use case - Argument reordering:

Some operations push values in the wrong order for consumption. Consider:

array[index] = value

The natural evaluation order is:

  1. Evaluate array
  2. Evaluate index
  3. Evaluate value

But the []= method expects: array, index, value

If they’re pushed as [array, index, value] on stack but need to be consumed as value, index, array, swap helps reorder them.

ASCII diagram - Swap operation:

Initial state:     After swap:      Purpose:
┌──────┐          ┌──────┐
│  B   │ ← top    │  A   │ ← top   Reversed order
├──────┤          ├──────┤         for operation
│  A   │          │  B   │         that needs A first
└──────┘          └──────┘

topn - Accessing Arbitrary Stack Positions

The topn instruction pushes a value from a specific stack depth to the top, without removing it from its original position.

Pseudocode:

# instruction: topn number
value = stack[-number - 1]  # Get value at depth 'number'
stack.push(value)

Stack visualization:

topn 2:

Before:                    After:
┌─────────────┐           ┌─────────────┐
│     "c"     │ ← top     │     "a"     │ ← top (copy from depth 2)
├─────────────┤           ├─────────────┤
│     "b"     │           │     "c"     │
├─────────────┤           ├─────────────┤
│     "a"     │ ← depth 2 │     "b"     │
├─────────────┤           ├─────────────┤
│     42      │           │     "a"     │ ← still here (original)
└─────────────┘           ├─────────────┤
                          │     42      │
                          └─────────────┘

Use cases:

  • Accessing method receiver during argument preparation
  • Retrieving values for conditional branches
  • Setting up complex method call stacks

Example - Method call preparation:

obj.method(arg1, arg2)

Stack state during preparation:

1. Push obj          # [obj]
2. Push arg1         # [obj, arg1]
3. Push arg2         # [obj, arg1, arg2]
4. topn 2            # [obj, arg1, arg2, obj]  ← obj copied to top for send
5. send :method      # Method needs receiver (obj) on top

The topn 2 instruction retrieves the receiver (obj) from its position under the arguments.

setn - Setting Arbitrary Stack Positions

The setn instruction sets a specific stack slot to the current top value. This provides precise control over stack value placement.

Pseudocode:

# instruction: setn number
value = stack.last           # Get top value
stack[-number - 1] = value   # Set position 'number' to this value

Stack visualization:

setn 2:

Before:                    After:
┌─────────────┐           ┌─────────────┐
│    "new"    │ ← top     │    "new"    │ ← top (unchanged)
├─────────────┤           ├─────────────┤
│     "b"     │           │     "b"     │
├─────────────┤           ├─────────────┤
│     "a"     │ ← depth 2 │    "new"    │ ← replaced!
├─────────────┤           ├─────────────┤
│     42      │           │     42      │
└─────────────┘           └─────────────┘

Critical use case - Keyword argument handling:

When calling methods with keyword arguments, YARV needs to place values in specific stack positions:

def method(a:, b:, c:)
end
 
method(c: 3, a: 1, b: 2)  # Arguments provided out of order

The VM must:

  1. Collect the keyword arguments
  2. Reorder them to match method signature
  3. Use setn to place values in correct positions

Difference from topn:

  • topn: Reads from arbitrary position → pushes to top
  • setn: Writes top value → to arbitrary position
graph LR
    A[topn: Read from depth N] --> B[Push to top]
    C[setn: Read from top] --> D[Write to depth N]

    style A fill:#e1f5ff
    style C fill:#fff4e1

Instruction Combinations

Real Ruby code often requires combining multiple stack manipulation instructions:

Example: Parallel assignment with swap

a, b = b, a

Simplified YARV:

getlocal a        # [a_value]
getlocal b        # [a_value, b_value]
swap              # [b_value, a_value]
setlocal a        # [b_value]  (a now has b's original value)
setlocal b        # []         (b now has a's original value)

Example: Method call with multiple arguments

receiver.method(arg1, arg2, arg3)

Stack preparation:

putobject receiver    # [receiver]
putobject arg1        # [receiver, arg1]
putobject arg2        # [receiver, arg1, arg2]
putobject arg3        # [receiver, arg1, arg2, arg3]
topn 3                # [receiver, arg1, arg2, arg3, receiver]
send :method, 3       # Consumes receiver + 3 args, pushes result

Performance Implications

Understanding stack manipulation helps explain Ruby performance:

1. Instruction Count Matters

# More stack manipulation → slower
x = complex_method(a, b, c)
 
# vs simpler:
x = simple_value

Complex expressions generate more stack manipulation instructions.

2. Optimization Opportunities

YARV’s JIT compiler can optimize stack operations:

  • Eliminate redundant dup/pop pairs
  • Combine multiple stack operations
  • Convert stack operations to register operations

3. Stack Depth Considerations

Deep stacks require:

  • More memory for stack storage
  • Higher topn/setn offset values
  • Potentially slower access times

Stack Manipulation Patterns

Common patterns emerge across Ruby features:

Pattern 1: Preserve and Consume

dup          # Preserve value
operation    # Consume original
             # Copy remains for further use

Pattern 2: Reorder and Execute

swap         # Fix argument order
send         # Execute with correct order

Pattern 3: Deep Access

topn N       # Access buried value
operation    # Use it
adjuststack  # Clean up afterwards

Pattern 4: Bulk Cleanup

complex_operation    # Leaves multiple temp values
adjuststack N        # Remove them all at once

Debugging Stack Operations

To visualize stack manipulation, use Ruby’s --dump=insns flag:

ruby --dump=insns -e 'x = 5'

This shows the exact sequence of stack instructions, including all manipulation operations.

Example output:

== disasm: #<ISeq:<main>@-e:1 (1,0)-(1,5)>
0000 putobject        5           # Push 5
0002 dup                          # Duplicate it
0003 setlocal_WC_0    x@0         # Store in x
0006 leave                        # Return top value

Stack Discipline

All these instructions maintain YARV’s critical stack discipline:

Rules:

  1. Operations must leave stack in predictable state
  2. Methods consume their arguments
  3. Methods push exactly one return value
  4. Exception handling must restore stack balance

Visual representation of method contract:

Method entry:           Method exit:
┌─────────────┐        ┌─────────────┐
│    arg2     │        │   result    │ ← One return value
├─────────────┤        └─────────────┘
│    arg1     │
├─────────────┤
│  receiver   │
└─────────────┘

Stack height change: -2 (consumed 2 args + receiver, produced 1 result)

Stack manipulation instructions enable maintaining this discipline while performing complex operations.

Recent Writing

Recent Notes

Graph View

Backlinks