CSCE 434 Lecture 38

« previous | Monday, November 25, 2013 | next »

Lecture Slides

Optimal Code Generation

• Loading from memory takes extra $delay$ cycles.
• Regular instructions take 1 cycle

If CPU is caught up waiting for memory access, we call this state interlock

Interlocking (occurs when $delay>0$) wastes resaurces because nothing is being done while we wait for data

Solution: move loads to be executed as early as possible before they are used:

• Load $x$
• Do stuff that doesn't depend on $x$ while $x$ is being loaded
  • this section should be at least $delay$ cycles long
  • Puts pressure on competition for registers: make sure we don't use the register that is reserved for $x$
  • Need to minimize this pressure
• Use $x$

Phase Ordering

• Allocate first and then schedule instructions → poor scheduling
• Schedule first and then allocate → poor allocation

Consider two problems simultaneously.

Legal ordering:

• children of an operator appear before it (i.e. preserve ordering between operations)
• each load occurs before the operation that uses it (i.e. preserve ordering between loads)

DLS Algorithm

1. Run Sethi-Ullman algorithm
   • Calculate $minReg$ for each subtree
   • create ordering of operations
2. Put loads into canonical order
   • Uses $minReg+1$ regs
   • Requires some renaming

Canonical order

Given $R$ registers,

1. Schedule $R$ loads
2. Schedule series of op/load pairs
3. Schedule remaining $R-1$ operations

Code Generator Generators

Like bison for machine code

Remember the name Berton Smith: Tera Computers.

Two approaches:

• Tree-matching
• Instruction-matching

Table-Driven code generator reads machine-specific table produced by a code generator generator

Example pattern:

When you see r = + a b, emit load r1, a; load r2, b; add r1 r2;

Tree Parsing

Use LR Parsers

• Encode pattern matching as parsing problem
• reductions emit code instead of producing AST
• BUT: grammars are very ambiguous

Instruction Matching

Peephole optimization: very narrow field of view

Compiler Design Philosophy

Spend time (and money) in

• Optimize
• Schedule
• Allocate