1 of 17

Code Generation �and Optimization

2 of 17

Translation

fun(y) {

x = y - 2;

};

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

sub

store_local 1

load_const 0

return

]

}

​

function __function_1 (y) : {

%x = alloca int64_t

%0 = %y

%1 = 2

%2 = sub %0 %1

store %x %2

%3 = 0

return %3

}

__function_1 :

sub 8 %rsp

mov %rsp %rbp

mov (%rbp, 2, 8) %rax

mov 2 %rcx

sub %rcx %rax

mov %rax (%rbp)

mov 0 %rax

ret

High-Level

VM

Low-Level

VM

Machine Code

Language

3 of 17

Why?

4 of 17

Why? Performance.

5 of 17

The Translation Task

​

​

​

​

​

​

  • Infinite resources
  • No performance specification

Registers

Control

CPU

ALU

fun(y) {

x = y - 2;

};

Language

Machine

​

​

​

​

​

​

  • Finite resources
  • Extremely performance sensitive

6 of 17

Sources of Performance Issues

  • Implementation
    • Implementation approach is naïve

​

  • Language/Abstraction
    • The language itself inherently forces an abstraction with non-optimal performance
    • Dynamic languages: type checks required everywhere and object shape may change

​

  • Machine Limitations
    • Maxed out capabilities of the machine

7 of 17

Your Interpreter (Likely)

void interpret(Function *func) {

Frame f = ...; OperandStack s;

Instruction* inst = func->instructions().begin();

​

while(inst != func->instructions().end()) {

switch(inst->operation()) {

case Operation::LoadLocal:

s.push(f.locals[inst->operand0]); break;

case Operation::LoadConst:

s.push(f.constants[inst->operand0]); break;

case Operation::Sub:

Integer* op2 = s.pop_int();

Integer* op1 = s.pop_int();

auto* result = new Integer(op1->value - op2->value);

s.push(result); break;

...

}

++inst;

}}

8 of 17

Performance Issues

  • Interpreter Loop (Implementation)
    • Problem: Data-dependent control flow on operation code
    • Symptom: Poor performance on pipelined processors
      • After completing bytecode action, which instruction do we fetch?
      • Stalls pipeline until address is resolved
    • Solution: Partial Evaluation of the control flow to eliminate jumps (Threaded Code)
  • Stack (Language/Abstraction - stack-based VM)
    • Problem: Intermediate operations stored into memory
    • Symptom: not the best performance because to memory is slow and on-chip storage is available
    • Solution: use registers (Stack Caching)
  • Boxed Values (Language)
    • Problem: Integers, Booleans, etc., are objects
    • Symptom: extremely slow performance due to memory accesses and memory allocations
    • Solution: Unbox integers

9 of 17

Pre-Evaluate Control Flow

  • Partial Evaluation: specialize code to information known statically (general technique)

void execute_0() {

Frame f = ...;

​

push(f.locals[0]);

push(f.constants[1]);

Integer* op2 = pop_int(stack);

Integer* op1 = pop_int(stack);

auto* result = new Integer(op1->value - op2->value);

push(result);

Value* op3 = pop(stack);

f.locals[1] = op3;

push(f.constants[0]);

Value* op4 = pop(stack);

return op4;

}

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

sub

store_local 1

load_const 0

return

]

}

10 of 17

But that’s not all…

__execute_0 :

push %rdi

call assert_integer

pop %rdi

mov %rdi %rax

shr $3 %rax

mov $2 %rcx

sub %rcx %rax

shl $3 %rax

or $1 %rax

ret

void execute_0() {

Frame f = ...;

​

push(f.locals[0]);

push(f.constants[1]);

Integer* op2 = pop_int(stack);

Integer* op1 = pop_int(stack);

auto* result = new Integer(op1->value - op2->value);

push(result);

Value* op3 = pop(stack);

f.locals[1] = op3;

push(f.constants[0]);

Value* op4 = pop(stack);

return op4;

}

Instructions: > 1000s -> 9

Function Calls: 10s -> 1

Memory Accesses: 100s -> 2

Allocations: > 1 -> 0

11 of 17

How? Many optimizations

  • Stack Caching (Register Allocation)
    • Instead of using stack to store temporaries, use registers when possible
  • Tagged Pointers (Optimized Runtime Techniques)
    • Avoid accesses to memory
  • Abstract Interpretation/Data-based Optimizations
    • x + y where x and y are integers can be replaced with arithmetic (Specialization)
    • 1 + 2 => 3 (Constant Folding) and x / 2 = x >> 1 (Strength Reduction)

12 of 17

When?

  • Static
    • Compile application prior to deployment
  • Dynamic
    • Ahead-of-Time
      • Distribute intermediate representation, but compile at load time
    • Just-in-Time
      • Demand-driven compilation. Block, function, or module is not compiled until there is a need to execute it.
    • Adaptive or Profile-Driven
      • After one (or multiple) interpretations, compile application

13 of 17

Language Implementations

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Interpreted

​

​

​

​

​

​

Interpreted

Swift

LLVM

EVM

Java

Python VM

Ethereum

Java VM

x86

ARM

SPARC

PowerPC

Language

High-Level

VM

Machine Code

C/C++ (Clang)

Low-Level

VM

JavaScript

C/C++ (gcc)

GIMPLE (HL)

GIMPLE (LL, SSA)

MIPS

LLVM (MC)

Direct

Translation

Python

SIL

LLVM (MC)

LLVM

14 of 17

When?

  • “Bare Metal” Languages
    • C/C++/Fortran
    • Static for predictable performance
    • Platform is a given -- code itself may include platform specific optimizations
  • Modern Languages
    • Dynamic Compilation (of a variety of forms)
    • Distributed representations are designed to be portable
    • Trade-off between code size and compilation time
      • Compiled machine code is typically large (poor fit for web code)
    • Tight Development Loop
      • Do not want to wait for compilation. Incremental AoT is difficult to get right.

​

​

15 of 17

Courtesy of Mario Wolczko

16 of 17

Next Lectures

  • Unoptimized Code Generation
    • Direct mapping of VM representation to machine representation
    • Goal: familiarize ourselves with the machine
  • Advanced Code Generation
    • Generate intermediate representation on which to perform static analysis
    • Goal: leverage static analysis for more efficient code generation

17 of 17

Resources

​

”Threaded Code.” by James Bell. In, Communications of the ACM, 1973.

​

“Stack Caching for Interpreters.” by M. Anton Erlt. In EuroForth, 1994.

​

“The Structure and Performance of Efficient Interpreters.” by M. Anton Erlt and David Gregg in Journal of Instruction-Level Paralleism, 2003

​

“Friday Q&A 2012-07-27: Let's Build Tagged Pointers”

https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-build-tagged-pointers.html

​

“An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes.” by Craig Chambers, David Ungar, and Elgin Lee. In LISP and Symbolic Computation, 1991

​