Linear scan. Register allocation - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Linear scan. Register allocation, слайд №1

Linear scan. Register allocation, слайд №2

Linear scan. Register allocation, слайд №3

Linear scan. Register allocation, слайд №4

Linear scan. Register allocation, слайд №5

Linear scan. Register allocation, слайд №6

Linear scan. Register allocation, слайд №7

Linear scan. Register allocation, слайд №8

Linear scan. Register allocation, слайд №9

Linear scan. Register allocation, слайд №10

Linear scan. Register allocation, слайд №11

Linear scan. Register allocation, слайд №12

Linear scan. Register allocation, слайд №13

Linear scan. Register allocation, слайд №14

Linear scan. Register allocation, слайд №15

Linear scan. Register allocation, слайд №16

Linear scan. Register allocation, слайд №17

Linear scan. Register allocation, слайд №18

Linear scan. Register allocation, слайд №19

Linear scan. Register allocation, слайд №20

Linear scan. Register allocation, слайд №21

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Linear scan. Register allocation. Доклад-сообщение содержит 21 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Linear Scan Register Allocation Massimiliano Poletto (MIT) and Vivek Sarkar (IBM Watson)

Слайд 2

Описание слайда:

Introduction Register Allocation: The problem of mapping an unbounded number of virtual registers to physical ones Good register allocation is necessary for performance Several SPEC benchmarks benefit an order of magnitude from good allocation Core memory (and even caches) are slow relative to registers Register allocation is expensive Most algorithms are variations on Graph Coloring Non-trivial algorithms require liveness analysis Allocators can be quadratic in the number of live intervals

Слайд 3

Описание слайда:

Motivation On-line compilers need generate code quickly Just-In-Time compilation Dynamic code generation in language extensions (‘C) Interactive environments (IDEs, etc.) Sacrifice code speed for a quicker compile. Find a faster allocation algorithm Compare it to the best allocation algorithms

Слайд 4

Описание слайда:

Definitions Live interval: A sequence of instructions, outside of which a variable v is never live. (For this paper, intervals are assumed to be contiguous) Spilling: Variables are spilled when they are stored on the stack Interference: Two live ranges interfere if they are simultaneously live in a program.

Слайд 5

Описание слайда:

Ye Olde Graph Coloring Model allocation as a graph coloring problem Nodes represent live ranges Edges represent interferences Colorings are safe allocations Order V2 in live variables (See Chaitin82 on PLDI list)

Слайд 6

Описание слайда:

Linear Scan Algorithm Compute live variable analysis Walk through intervals in order: Throw away expired live intervals. If there is contention, spill the interval that ends furthest in the future. Allocate new interval to any free register Complexity: O(V log R) for V vars and R registers

Слайд 7

Описание слайда:

Example With Two Registers 1. Active = < A >

Слайд 8

Описание слайда:

Example With Two Registers 1. Active = < A > 2. Active = < A, B >

Слайд 9

Описание слайда:

Example With Two Registers 1. Active = < A > 2. Active = < A, B > 3. Active = < A, B > ; Spill = < C >

Слайд 10

Описание слайда:

Example With Two Registers 1. Active = < A > 2. Active = < A, B > 3. Active = < A, B > ; Spill = < C > 4. Active = < D, B > ; Spill = < C >

Слайд 11

Описание слайда:

Example With Two Registers 1. Active = < A > 2. Active = < A, B > 3. Active = < A, B > ; Spill = < C > 4. Active = < D, B > ; Spill = < C > 5. Active = < D, E > ; Spill = < C >

Слайд 12

Описание слайда:

Evaluation Overview Evaluate both compile-time and run-time performance Two Implementations ICODE dynamic ‘C compiler; (already had efficient allocators) Benchmarks from the previously used ICODE suite (all small) Compare against tuned graph-coloring and usage counts Also evaluate a few pathological program examples Machine SUIF Selected benchmarks from SPEC92 and SPEC95 Compare against graph-coloring, usage counts, and second-chance binpacking Compare both metrics on both implementations

Слайд 13

Описание слайда:

Compile-Time on ICODE ‘C Usage Counts, Linear Scan, and Graph Coloring shown Linear Scan allocation is always faster than Graph Coloring

Слайд 14

Описание слайда:

Compile-Time on SUIF Linear Scan allocation is around twice as fast than Binpacking (Binpacking is known to be slower than Graph Coloring)

Слайд 15

Описание слайда:

Pathological Cases N live variable ranges interfering over the entire program execution Other pathological cases omitted for brevity; see Figure 6.

Слайд 16

Описание слайда:

Compile-Time Bottom Line Linear Scan is faster than Binpacking and Graph Coloring works in dynamic code generation (ICODE) scales more gracefully than Graph Coloring … but does it generate good code?

Слайд 17

Описание слайда:

Run-Time on ICODE ‘C Usage Counts, Linear Scan, and Graph Coloring shown Dynamic kernels do not have enough register pressure to illustrate differences

Слайд 18

Описание слайда:

Run-Time on SUIF / SPEC Usage Counts, Linear Scan, Graph Coloring and Binpacking shown Linear Scan makes a fair performance trade-off (5% - 10% slower than G.C.)

Слайд 19

Описание слайда:

Evaluation Summary Linear Scan is faster than Binpacking and Graph Coloring works in dynamic code generation (ICODE) scales more gracefully than Graph Coloring generates code within 5-10% of Graph Coloring Implementation alternatives evaluated in paper Fast Live Variable Analysis Spilling Hueristics

Слайд 20

Описание слайда:

Conclusions Linear Scan is a faster alternative to Graph Coloring for register allocation Linear Scan generates faster code than similar algorithms (Binpacking, Usage Counts) Where can we go from here? Reduce register interference with live range splitting Use register move coalescing to free up extra registers