Primary Goals

• management of run-time resources
• correspondence between static and dynamic data structures
• storage organization

Run time execution

• execution of a program is under the control of the OS
• when a program is invoked…
  1. the OS allocates space for the program
  2. the load is loaded into a part of that space
  3. the OS jumps to the entropy point for the first instruction

Typically the order is

Assumptions

1. execution is sequential: control pass from one point to another
   • concurrency break this
2. when a procedure is called, control should return to the point immediately after the call
   • exceptions break this, but we won’t have them

activation

• invocation of procedure \(P\) is what we call an “activation” of \(P\)
• lifetime of \(P\) is
  1. all steps for activating \(P\)
  2. all steps in \(P\)

activation tree

• when \(P\) calls \(Q\), \(Q\) returns before \(P\)
• activation lifetimes can therefore be a tree

since there’s only ever one path from main to the current active function call, we can use a stack and keep track of information in the call stack on the stack.

“If \(B\) is a subclass of \(A\), then an object of \(B\) can be used wherever \(A\) is expected.”

To do this, we will lay out:

the pointer * points to a method table

Other Semantics than structural operational semantics

1. denotational semantics
2. axiomatic semantics

Runtime Errors

We have to catch some runtime errors:

• calling on voids
• method dispatch problems

What to track in context?

• environment: where in memory a variable is stored? Map<Symbol, void *>
• store: what is in memory? Map<void *, Value>

This means that a judgment is:

Its optimization time!!

Program Optimization

“maximum benefit for minimal cost”

When should optimization happen?

AST?

• pro: machine independent
• con: no notion registers, not language dependent

Assembly?

• pro: many optimization opportunities
• con: machine dependent

And so, we really should be doing this with some IR.

Three-address intermediate code

Each instruction is of the form:

x := y op z
x := op z

where x, z are registers, constants, etc.

basic block

A basic block is a sequence with no labels (except in the first point) an no jumps (except in the last point). So when we are inside a basic block, we can optimize the code inside sans worry about control flow.

more Program Optimization

Memory Hierachy

• registers: 1 cycle (256 bytes or so)
• cache: 4 cycles (100MB or so)
• memory: 100-500 cycles (128GB)
• disk: millions of cycles (1-10TB)

Trends

• power usage limits: with a fixed power budget, we can’t really get more transistors in the same space (i.e. stuff can’t be faster)
• cache miss cost is quite high, so using multiple lines of cache

register allocation

see Register Allocation

performance engineering

example

Consider:

for (int j=1; j<10; j++)
    for (int i=1; i<10000; i++)
        a[i] *= b[i]

you can see that, by the time you get to b[100000], you probably have lost b[1] from your cache.