TU Wien:Codegeneratoren VO (Krall)/Index Skriptum WS10

Papers

Architecture

The PowerPC 604 RISC Microprocessor - Song & Denman (Seite 1)

• out-of-order Execution (Seite 1)
• Register renaming (Seite 2)
• Branch prediction, speculative execution (Seite 3)
• Serialazation (Seite 3)

Link: https://ieeexplore.ieee.org/document/363071/

Alpha AXP Architecture - Sites (Seite 11)

• Definition Computer Architecture (Seite 11)
• Definition Implemetation (Micro Architecture)(Seite 11)
• Load-Store architecture (Seite 12)

Link: https://www.linux-mips.org/pub/linux/mips/people/macro/DEC/DTJ/DTJ801/DTJ801PF.PDF

Discovery 6, Intels Sternenschiff P6 im Detail - Schnurer (Seite 23)

Hinweis: Bei diesem Artikel sind die Seiten vertauscht. Die richtige Reihenfolge: 23, 24, 28, 29, 26, 25

Compiler Optimizations

Advanced Compiler Optimizations For Supercomputers - Padua & Wolfe (Seite 29)

• Data Dependence (Seite 30)
• true dependence/flow dependance (Seite 30)
• antidependence (Seite 30)
• output dependence, write-after-write (WAW) (Seite 30)
• control dependence (Seite 30)
• Loop Vectorication (Seite 32)
• Loop Concurrentization (Seite 33)

Link: http://polaris.cs.uiuc.edu/~padua/cs320/p1184-padua.pdf

The CONVEX FORTRAN 5.0 Compiler - Mercer (Seite 47)

Hinweis: Seite 53/54 vertauscht.

• Local Scalar Optimization (Seite 53)
  • redundant assignment elimination
  • redundant use elimination
  • assignment substitution
  • common expression elimination
  • simple strength reduction
  • algebraic simplification
  • branch simplification
  • constant folding

• Global Scalar Optimization (Seite 53/55)
  • constant propagation
  • copy propagation
  • unreachable/useless code elimination
  • induction variable optimization
  • common expression elimination

• Inline Expansion/Inlining (Seite 56)

Effectiveness of a Machine-Level, Global Optimizer - Johnson & Miller (Seite 59)

Link: http://dl.acm.org/citation.cfm?id=13321&bnc=1

Code Generators

Engineering a Simple, Efficient Code Generator Generator - Fraser & Hanson & Proebsting (Seite 69)

Link: http://dl.acm.org/citation.cfm?id=151642&bnc=1

Engineering a Simple, Efficient Code Generator Generator - Fraser & Hanson & Proebsting (Seite 83)

• BURG
• iBURG

Fast and Flexible Instruction Selection with Constraints - Thier & Ertl & Krall

• FFISC

Link: http://www.complang.tuwien.ac.at/andi/papers/cc_18.pdf

Generalized Instruction Selection using SSA Graphs - Ebner & Brandner & Scholz & Krall & Wiedermann & Kadlec (Seite 108)

• SSA

Link: http://llvm.org/pubs/2008-06-LCTES-ISelUsingSSAGraphs.pdf

Register Allocation

Coloring Heuristics for Register Allocation - Briggs & Cooper & Kennedy & Torczon (Seite 118)

• Register Allocation
• Graph Coloring
• Chaitin's Heuristic (Seite 119)

Link: http://dl.acm.org/citation.cfm?id=74843&bnc=1

Register Allocation & Spilling via Graph Coloring - Chaitin (Seite 128)

• Register Allocation
• Graph Coloring
• Interference Graph (Seite 129)
• Coalescing (Seite 129)
• Variable Propagation/Subsumption (Seite 129)

Link: http://dl.acm.org/citation.cfm?id=806984&bnc=1

Register Allocation via Coloring - Chaitin & Auslander & Chandra & Cocke & Hopkins & Markstein (Seite 136)

• Register Allocation
• Graph Coloring
• Interference
• Register Pressure (Seite 142)
• Rematerialization (Seite 143)

Link: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.452.8606&rep=rep1&type=pdf

The Priority-Based Coloring Approacht to Register Allocation - Chow & Hennessy (Seite 147)

• Register Allocation
• Chromatic Number (Seite 148, links unten)
• Live Ranges (Seite 150)
• Priority Based Coloring (Seite 152)
• Live Range Splitting (Seite 153)

Link: http://dl.acm.org/citation.cfm?id=88621&bnc=1

Optimistic Register Coalescing - Park & Moon (Seite 166)

• Agressive Coalescing (Seite 168)
• Conservative Coalescing (Seite 168)
  • rematerialization
• Optimistic Coalescing (Seite 169)

Link: https://ieeexplore.ieee.org/document/727246/

Optimal and Near-optimal Global Register Allocation Using 0-1 Integer Programming - Goodwin & Wilken (Seite 175)

• Optimal Register Allocation (ORA) (Seite 176)
• CPLEX (Solver) (Seite 177)

Link: http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1097-024X(199608)26:8%3C929::AID-SPE40%3E3.0.CO;2-T/abstract

A Faster Optimal Register Allocation - Wilken (Seite 194)

Link: https://ieeexplore.ieee.org/document/1176254/

Interprocedural Register Allocation

Global Register Allocation at Link Time - Wall (Seite 206)

• Link Time Register Allocation

Link: http://dl.acm.org/citation.cfm?id=13338

Register Allocation Across Procedure and Module Boundries - Santharnam & Odnert (Seite 218)

• Link Time Register Allocation
• L_REF (Local Reference Set) (Seite 220)
• C_REF (Child Reference Set) (Seite 220)
• P_REF (Parent Reference Set) (Seite 220)
• Spill Code Movement/Spill Code Motion (Seite 222)

Link: http://dl.acm.org/citation.cfm?id=93551&bnc=1

Instruction Scheduling

Instruction scheduling for the IBM RISC System/6000 processor - Warren (Seite 230)

• IBM Paper zu Instruction Scheduling
• List Scheduling (Seite 234/235)

Link: https://ieeexplore.ieee.org/document/5389862/?arnumber=5389862 (nicht verfügbar über die UB)

Das Paper ist auch auf Sci Hub via "10.1147/rd.341.0085" zu finden.

Efficient Instruction Scheduling for a Pipelined Architecture - Gibbons & Muchnick (Seite 238)

• HP Paper zu Instruction Scheduling

Link: http://dl.acm.org/citation.cfm?id=13312&bnc=1

Integrated Register Allocation and Instruction Scheduling

Code Scheduling an Register Allocation in Large Basic Blocks - Goodman & Hsu (Seite 244)

• CSP (Code Scheduling for Pipelined processors) (Seite 245)
• CSR (Code Scheduling to minimize Register usage) (Seite 246)
• AVLREG (bumber of Available Registers) (Seite 247)
• Integrated Scheduling Algorithm (Algorithm 1) (Seite 247)
• Free WAR (write-after-read) Dependencies
• DAG-Driven Allocation Algorithm (Algorithm 2) (Seite 252)

Link: http://dl.acm.org/citation.cfm?id=55407&bnc=1

Integrated Register Allocation and Instruction Scheduling for RISCs - Bradlee & Eggers & Henry (Seite 254)

• RASE (Register Allocation with Schedule Estimates) (Seite 255)
• RASE Code Generation (TODO:?) (Seite 257)

Link: http://dl.acm.org/citation.cfm?id=106986&bnc=1

Phase Ordering of Register Allocation and Instruction Scheduling - Freudenberger & Ruttenberg (Seite 264)

Trace: Pfad von Instruktionen mit Ein- und Aussprüngen aber ohne Schleife außer zum Anfang. (TODO: wording)

• VLM Data Structure (Value-Location Mapping) (Seite 267)

Software Pipelining

Software Pipelining: An Effective Scheduling Technique for VLIW Machines - LAM (Seite 283)

• Modulo variable expansion (Seite 287)

Link: http://dl.acm.org/citation.cfm?id=53990.54022

A Realistic Resouce-Comstrained Sowfware Pipelining Algorithm - Aiken & Nicolau (Seite 294)

Problem: Keine Heuristik zum auswählen der Befehle angegeben

Link: https://theory.stanford.edu/~aiken/publications/papers/ieeetpds95.pdf

Iterative Modulo Scheduling: An Algorithm For Software Pipelining Loops - Rau (Seite 303)

• MII (minimum initiation interval) (Seite 304)
• Iterative modulo scheduling (Seite 307)
• Characterization of iterative modulo scheduling (Seite 311)

Link: http://dl.acm.org/citation.cfm?id=192731&bnc=1

Compiler optimazations for processors with SIMD instructions - Pryanishnikov & Krall & Horspool (Seite 314)

• SIMD (single instruction multiple data)
• Generation of LOAD & STORE SIMD instructions (Seite 320)
• Alignment Analysis (Seite 323)

Link: http://onlinelibrary.wiley.com/doi/10.1002/spe.751/abstract