Copyright © 2004, 2022
Robert W. Hasker

Ch. 9

• Instruction selection
• IR Tree ("language") nodes: simple operations
  • mem fetch/store
  • add/subtract/multiply
  • conditional jump
  • etc.
• Typically, instructions perform several operations
  • usually can fetch from memory and add to register in same instruction
• Example: Fig. 9.1
  • This is a fictitious machine the textbook calls the "Jouette" architecture
  • register 0 contains value 0
  • First line: captures that TEMP is implemented as a register
  • other instructions (except STORE, MOVEM): always compute result to a register
• Tiling: mapping instructions to portions of IR Trees
• Example: Figure 9.2
  • tiles: set of tree patterns corresponding to legal instructions
  • tiling: set of tiles which cover a complete tree
  • assuming reasonable instruction set, can always find a tiling with one tile per node
  • Figure 9.2: shows two possible tilings for the same tree (and corresponding Jouette (pseudo-)assembly instructions)
• Optimal Tiling
  • best tiling: lowest-cost instruction sequence
  • assign each tile a cost
  • optimum: sum of tiles is lowest possible value
  • optimal: no two adjacent tiles can be combined to create lower-cost tile
    • all optimum tilings are optimal, but not vice-versa
    • algorithms exist for both, but computing optimal tilings is simpler

Instruction Selection Algorithms

• maximal munch
  • algorithm
    1. find largest tile that fits root of tree (largest = most nodes covered)
    2. cover root and appropriate children by tile
    3. recurse on uncovered children
  • When done, generate instructions in reverse order
  • maximal munch computes an optimal tiling, but not an optimum tiling
• dynamic programming
  • algorithm:
    1. compute minimum cost tile for each leaf
    2. next level up: find best tile for node
       • 0 or more leaves will be not be covered by new tile
       • minimum cost for node: cost of tile + sum of uncovered leaves
    3. recurse until reach top
  • computes optimum tiling
  • has been generalized so that instruction are described by a CFG and a code-generator generator produces tools which can generate optimum instruction sequences
• which is better?
  • dynamic programming: optimum tiling
  • let

            N  = number of nodes in tree
            K  = average # of non-leaf nodes per tile
            K' = maximum number of nodes to examine in any tile
            T  = number of different tiles
            T' = average # of tiles matching at each node
    

    For example, typical RISC machines have T = 50, T' = 5, K = 2, and K' = 4.
  • Cost for maximumal munch: (K' + T') N / K, or O(N)
  • Cost of dynamic programming: (K' + T') N, also O(N)
    • constant of proportionality higher for dynamic programming
  • in practice, small amounts of work compared to other phases (esp. lexical analysis)

Instruction Sets

• typical RISC vs. typical CISC:

  Item	RISC	CISC
  registers	32	6, 8, 16
  register classes	one	many; dedicated registers for some ops
  arithmetic operations	register only	memory and register (modes)
  instruction type	three address: r1 <- r2 op r3	two address: r1 <- r1 op r2
  addressing modes	M[reg+const]	many
  instruction size	one word	variable
  side effects	none	auto-increment, others

• Pentium
  • registers: six general-purpose registers, sp, and fp
  • register classes: multiply must have arg in eax, result in eax and edx (high order bits in edx)
  • arithmetic operations: register and memory
  • instruction types: two address
    • mov t₁, t₂
    • add t₁, t₂
  • address modes: [edp - 8] accesses the memory location at edp - 8
  • instruction size: variable length, but this is just a headache for the assembler
  • side effects: yes (autoincrement)
    • how to use?
      • ignore autoincrement
      • match special cases in ad-hoc way
      • use instruction algorithm based on matching in directed graphs

Selecting Instructions for MiniJava

• note: generally can't know what registers are used until do register allocation
  • We will identify the instructions; filling registers will be later
• representing assembly instructions:
  • class Instr: represents assembly instructions with blanks for registers
    • holds temporaries used by instruction in variable TempList
  • abstract class Instr:
    • assembly text
      • use 'd0 to represent destination 0 (see below), 's0 for source 0, 'j0 for label 0
    • public abstract TempList use() - return list of temporaries accessed by instruction
      • can be null
    • public abstract TempList def() - return list of temporaries modified by instruction
      • can be null
      • include side-effects; eg eax, edx in Pentium multiply
    • public abstract Targets jumps() - return list of labels this instruction could branch to
      • always returns null for non-jumping instructions
      • always includes next instruction for jump instructions if it's possible to fall through (conditional jumps)
    • public String format(TempMap m) - given map for temporaries, returns formatted instruction
  • public class LABEL extends Instr - represent labels in code
    • assembly text: label in assembly language (as a string)
    • label component: internal label object being represented
  • public class OPER - operation
    • constructor: OPER(String instrname, TempList dst, TempList src, LabelList jump): instruction with destinations, sources, and jumps
    • constructor: OPER(String instrname, TempList dst, TempList src): oper with no jumps
  • public class MOVE extends OPER
    • operation which does just data transfers
    • usefulness: can delete if dst and src refer to same temporary or register
• Example (based on Jouette assembly language):

          MEM(BINOP(PLUS, TEMP(fp), CONST(8)))
  

  represented as

          new OPER("LOAD 'd0 <- M['s0+8]",
                   new TempList(new Temp(), null),
                   new TempList(frame.FP(), null))
  

• Another example: add t1, t2 would be represented as

          new OPER("add 'd0, 's1",
                   new TempList(t1),
                   new TempList(t1, new TempList(t2, null)))
  

• Generating
  • munchStm: "munch" statements, generating Instr objects as side-effects
    • Would have a different version for each target architecture
    • Fig. 9.5: munchStm for Jouette architecture
  • munchExp: "munch" expressions: generate Instr objects, return temporary holding result of expression
    • Fig. 9.6: munchExp for Jouette architecture
• Procedure Calls
  • munchArgs: process all arguments, returning list of temporaries passed to procedure call
    • temporaries must be listed as sources for instruction so register allocation doesn't trash them
  • CALL will typically "trash" some registers
    • Eg: architectures which use particular registers for arguments, updates to the frame pointer, using a register for a return value
    • Essentially, side-effects of the instruction
    • The x86 multiply is the same: multiplying two 32-bit registers gives a 64-bit result, implicitly modifying the B register
    • Include these registers in the instruction destination
• Frame Pointer
  • generally: replace FP+k by SP+k+f where f is the frame size
  • usually won't know frame size; use symbolic constant so assembler can fill in the constant
    • eg: function f emitted at label L14; use SP+k+L14_FrameSize where L14_FrameSize is a symbolic constant

Review

• tiling trees
• optimal vs. optimum tilings
• maximal munch, dynamic programming instruction selection algorithms
• RISC vs. CISC
• instruction selection in MiniJava