编译_chapter09.pptx

Instruction Selection;References;Backend Optimizations;Outline;Tree Patterns;Tree patterns;;Example;Example;;One tile covers one node;Optimal And Optimum Tilings;Optimal is not necessarily optimum;Algorithms For Instruction Selection;Algorithms For Instruction Selection;Maximal Munch - Optimal tiling;Implementation ?;Exercise 2;Dynamic Programming;Example;Example - Cost is number of tilings;Using minimum cost of subtree;;Tree Grammars;Fast Matching;Example;Efficiency of Tiling Algorithms;MM vs DP;CISCRISC;CISCRISC;Example;Low-level IR to IR Tree/DAG;Instruction Selection;Instruction Selection;Example;Example;Possible Translation;Another Translation;Yet Another Translation;Issue: Instruction Costs;How to Solve the Problem?;Tree Representation;Tiles;Tiling;Tiling;Directed Acyclic Graphs;Example;Big Picture;DAG Construction;Algorithm;Issues;Summary