Outline

• Instruction Selection
• Intermediate Representation is List of Trees
• Each Machine Instruction Represented as a Tree
• Try to Cover/Tile IR Tree with Machine Instruction Trees
• Locally Optimal Solutions, The Global Optimum
• Maximal Munch
• Top Down Pattern Match
• Generates Machine Instructions in Reverse Order (Last Instruction First)
• Finds an Optimal Tiling Given Cost Model
• Does Not Necessarily Find the Global Minimum
• Other Approaches
• Graham-Glanville Parser-Based Approach
• Dynamic Programming
• Naive/Canonical Generation Followed by Peepholing

• Intermediate Representation is List of Trees
• Keep tree structure to allow better matching to machine architecture
• Each Machine Instruction Represented as a Tree (Pattern)
• Writing these patterns effectively describes the machine
• Must ensure there is at least one "fallback" pattern for every IR operator with arbitrary operands
• Can keep adding patterns for special cases, even if multiple instructions are required to accomplish it
• Try to Cover/Tile IR Tree with Machine Instruction Trees
• The Machine Instructions are considered to be "Tile"s
• The IR Tree is like a surface to be covered with matching Tiles
• This is a classic optimization problem
• There are tools to automate this, given table of patterns
• We will probably do it by hand, following some (systematic) approach
• Locally Optimal Solutions, The Global Optimum
• A Locally Optimal Solution is one where no two tiles can be replaced by a single, "cheaper" tile
• The Global Optimum is a Tiling that minimizes total cost

• Top Down Pattern Match
• IR Tree Is Walked Recursively
• Instruction Patterns Are Tried, "Largest" First
• First To Fit Is Chosen
• Recurse With IR Nodes Matching Leaves of Pattern Tree
• Generates Machine Instructions in Reverse Order (Last Instruction First)
• Think About It...
• May Do Entire Program Back To Front (Useful For Determining Liveness)
• Or Just Process One IR Statement In Reverse
• Finds an Optimal Tiling Given Cost Model
• Choosing Largest That Fits Ensures Local Optimality
• If There Were Larger Tile That Matches Same As Two Smaller Tiles, It Would Have Been Chosen First
• Does Not Necessarily Find the Global Minimum
• Maximal Munch can "commit" too early
• Might miss a really "big" pattern below the top node
• Tiling is similar to parsing, can go down "blind alley"

• Graham-Glanville Parser-Based Approach
• Can write tree as sequence of tokens, operator/operand/operand
• Parsing this token sequence where each machine instruction corresponds to a non-terminal is analogous to tiling
• Tricky due to ambiguity and blind alleys
• Large Number of Shift/Reduce and Reduce/Reduce conflicts make parser-based code-generation a bit of an "art"
• Dynamic Programming
• Bottom Up Exhaustive Cataloging of Optimum Solutions
• Optimum Solution of Node Based on Optimum Solution of Subsidiary Nodes
• Delivers the Global Optimum
• Can be Made Very Efficient (e.g. Twig, BURG)
• Naive/Canonical Generation Followed by Peepholing
• Each IR Node turned into Sequence of Machine Instructions
• Works Well If IR relatively "high level"
• Can Create Lots of Temps -> more work for register allocator
• Can be improved by "peephole" optimization