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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x}
• Do stuff that doesn't depend on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} while Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is being loaded
  • this section should be at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle delay} cycles long
  • Puts pressure on competition for registers: make sure we don't use the register that is reserved for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x}
  • Need to minimize this pressure
• Use Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle minReg} for each subtree
   • create ordering of operations
2. Put loads into canonical order
   • Uses Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle minReg + 1} regs
   • Requires some renaming

Canonical order

Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} registers,

1. Schedule Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} loads
2. Schedule series of op/load pairs
3. Schedule remaining Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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