CMU CS 15745 - Progressive Register Allocation for Irregular Architectures (13 pages)

Previewing pages 1, 2, 3, 4 of 13 page document View the full content.
View Full Document

Progressive Register Allocation for Irregular Architectures



Previewing pages 1, 2, 3, 4 of actual document.

View the full content.
View Full Document
View Full Document

Progressive Register Allocation for Irregular Architectures

107 views


Pages:
13
School:
Carnegie Mellon University
Course:
Cs 15745 - Optimizing Compilers for Modern Architectures
Optimizing Compilers for Modern Architectures Documents

Unformatted text preview:

Outline Progressive Register Allocation for Irregular Architectures Register Allocation for Irregular Architectures Previous Work Progressive Register Allocation David Koes 2 1 2005 Irregular Architectures Few registers Register usage restrictions Irregular Architectures Register Allocation Graph coloring register allocation used gcc ORC SUIF GHS IMPACT IBM address registers hardwired registers Memory operands Examples x86 68k ColdFire ARM Thumb MIPS16 V800 various DSPs Assertion eax ebx ecx edx esi edi esp ebp Graph coloring is the wrong representation for performing register allocation on irregular architectures 1 Fewer Registers More Spills PPC 32 registers Used gcc to compile 10 000 functions from Mediabench Spec95 Spec2000 and microbenchmarks Recorded for which functions graph coloring failed 68k 16 registers x86 8 registers 2 Graph Coloring and Spills Register Usage Restrictions Graph coloring solves the register sufficiency problem Example Even if P NP suboptimal if spills necessary No optimization of spill code Many spills may slow down allocator has to rebuild interference graph address register data register 68k MOVE ptr tmp1 EOR 3 tmp1 any register MOVEQ 32 tmp2 or MOVEA 32 tmp2 ADD tmp2 ptr MOVE tmp1 D0 Register Usage Restrictions Memory Operands Instructions may require or prefer a specific subset of registers A variable allocated to memory may not require load store to access 68k address data registers MOVEA 1 A0 4 byte instruction MOVEQ 1 D0 2 byte instruction x86 div instruction Graph coloring assumes all colors are equally applicable no principled way to express preferences requirements may be mutually exclusive depends upon instruction still less efficient than register access Graph coloring usually spills variables which make graph easier to color may not be an efficient variable to spill 3 Graph Coloring Wrong Approach for Irregular Architectures Outline Solves wrong problem Register Allocation for Irregular Architectures Previous Work focuses



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Progressive Register Allocation for Irregular Architectures and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Progressive Register Allocation for Irregular Architectures and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?