Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 2,431 papers for “Register allocation”

Register Allocation

Andrew W. Appel · Cambridge University Press eBooks · 1997

reg-is-ter: a device for storing small amounts of dataal-lo-cate: to apportion for a specific purposeWebster's Dictionary

Cited by 0

Register windows vs. register allocation

D. W. Wall · 1988

A large register set can be exploited by keeping variables and constants in registers instead of in memory. Hardware register windows and compile-time or link-time global register allocation are ways to do this. A measure of the effectiveness of any of these register management schemes is how thoroughly they remove loads and stores. This measure must also count extra loads and stores executed because of window overflow or conflicts between procedures.

Cited by 35Open access

Register Windows vs. Register Allocation

David Wall December, David W. Wall · 1988

A large register set can be exploited by keeping variables and constants in registers instead of in memory. Hardware register windows and compiletime or link-time global register allocation are ways to do this. A measure of the effectiveness of any of these register management schemes is how thoroughly they manage to remove loads and stores. This measure also must count extra loads and stores that had to be executed because of window overflow or conflicts between procedures. By combining profiling, instrumentation, and in-line simulation, we measured the effectiveness of several register management schemes. These included compile-time and link-time schemes for allocating 52 registers, and register window schemes using 128 registers organized into fixed-size or variable-sized windows. Link-time allocation based on profile information was the clear winner in some cases and did about as well as windows in the rest. Even link-time allocation based on an estimated profile was about as good...

Cited by 0

Register Allocation Algorithms

Shiliang Liu, Weiming Zhao · 2008

Register allocation is the process of multiplexing a huge number of target program variables onto a small number of on chip registers. And the ultimate goal is to keep as many operands as possible in registers to minimize the communications between memory and CPU, and in the meantime, maximize the execution speed of program execution. Register allocation is a well known NP-complete problem. Even though plenty of efforts have been dedicated to register allocation, there are still a lot of challenging problems facing concurrent compiler scientists; this paper is aimed to provide a general survey on present register allocation algorithms and analyze the main perplexing issues and their possible solutions. Mainly the following are the register allocation algorithm topics we have been

Cited by 0

Index Register Allocation

L. P. Horwitz, Richard M. Karp, Raymond E. Miller et al. · Journal of the ACM · 1966

A procedure for index register allocation is described. The rules of this procedure are shown to yield an optimal allocation for “straight line” programs.

Cited by 77Open access

Register allocation deconstructed

David Ryan Koes, Seth Copen Goldstein · 2009

Register allocation is a fundamental part of any optimizing compiler. Effectively managing the limited register resources of the constrained architectures commonly found in embedded systems is essential in order to maximize code quality. In this paper we deconstruct the register allocation problem into distinct components: coalescing, spilling, move insertion, and assignment. Using an optimal register allocation framework, we empirically evaluate the importance of each of the components, the impact of component integration, and the effectiveness of existing heuristics. We evaluate code quality both in terms of code performance and code size and consider four distinct instruction set architectures: ARM, Thumb, x86, and x86-64. The results of our investigation reveal general principles for register allocation design.

Cited by 13

Probabilistic register allocation

Todd A. Proebsting, Charles N. Fischer · ACM SIGPLAN Notices · 1992

A new global register allocation technique, probabilistic register allocation , is described. Probabilistic register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that excellent allocation choices can be made. Local allocation is done first, and then global allocation is done iteratively beginning in the most deeply nested loops. Because local allocation precedes global allocation, probabilistic allocation does not interfere with the use of well-known, high-quality local register allocation and instruction scheduling techniques.

Cited by 5Open access

Register Allocation for Banked Register File

Jinpyo Park, Je-Hyung Lee, Soo‐Mook Moon · 2001

A banked register file is a register file partitioned into banks. A register in a banked register file is addressed with the register number in conjunction with the active bank number. A banked register file may be employed to reduce the number of bits for register operands in the instruction encoding at the cost of bank changes and inter-bank data transfers. Although a banked register file is introduced to provide sufficient registers and reduce memory traffic, it may on the other hand inflate code by unwanted bank hanges and excessive inter-bank data movements. In this context, code quality heavily depends on the register allocator that decides the location of each variable. This paper addresses a heuristic approach to register allocation for exploiting two register banks. It performs global register allocation with the primary bank registers, while reducing the register pressure by doing local register allocation with the secondary bank registers. Experimental results show that the proposed register allocator eliminates a significant amount of memory traffic while achieving smaller code size compared to an allocator that utilizes the primary bank only.

Cited by 3

Register allocation for free

David R. Ditzel, Hubert R. McLellan · 1982

The Bell Labs C Machine project is investigating computer architectures to support the C programming language.1 One of the goals is to match an efficient architecture to the language and the compiler technology available. Measurements of different C programs show that roughly one out of every twenty instructions executed is either a procedure call or return.2 Procedure call overhead is therefore a very important consideration in the overall machine design. A second and related area of primary concern in overall machine efficiency is the register allocation strategy. While use of additional registers can offer considerable improvement in execution times, adding registers usually has the adverse effects of increasing the procedure call overhead due to register saving and creating an undue burden on the compiler. In this paper we describe a piece of the C Machine architecture which effectively eliminates the register allocation problem, and improves procedure calling by drastically reducing storage references required by traditional register saving. The technique can be generalized for other languages and architectures, though we will only directly address those issues involving the C language.

Cited by 129Open access

Register allocation for free

David R. Ditzel, Hubert R. McLellan · ACM SIGARCH Computer Architecture News · 1982

The Bell Labs C Machine project is investigating computer architectures to support the C programming language. 1 One of the goals is to match an efficient architecture to the language and the compiler technology available. Measurements of different C programs show that roughly one out of every twenty instructions executed is either a procedure call or return. 2 Procedure call overhead is therefore a very important consideration in the overall machine design. A second and related area of primary concern in overall machine efficiency is the register allocation strategy. While use of additional registers can offer considerable improvement in execution times, adding registers usually has the adverse effects of increasing the procedure call overhead due to register saving and creating an undue burden on the compiler. In this paper we describe a piece of the C Machine architecture which effectively eliminates the register allocation problem, and improves procedure calling by drastically reducing storage references required by traditional register saving. The technique can be generalized for other languages and architectures, though we will only directly address those issues involving the C language.

Cited by 3Open access

Register allocation for free

David R. Ditzel, Hubert R. McLellan · ACM SIGPLAN Notices · 1982

The Bell Labs C Machine project is investigating computer architectures to support the C programming language. 1 One of the goals is to match an efficient architecture to the language and the compiler technology available. Measurements of different C programs show that roughly one out of every twenty instructions executed is either a procedure call or return. 2 Procedure call overhead is therefore a very important consideration in the overall machine design. A second and related area of primary concern in overall machine efficiency is the register allocation strategy. While use of additional registers can offer considerable improvement in execution times, adding registers usually has the adverse effects of increasing the procedure call overhead due to register saving and creating an undue burden on the compiler. In this paper we describe a piece of the C Machine architecture which effectively eliminates the register allocation problem, and improves procedure calling by drastically reducing storage references required by traditional register saving. The technique can be generalized for other languages and architectures, though we will only directly address those issues involving the C language.

Cited by 14

Fusion-based register allocation

Guei-Yuan Lueh, Thomas R. Gross, Ali-Reza Adl-Tabatabai · ACM Transactions on Programming Languages and Systems · 2000

The register allocation phase of a compiler maps live ranges of a program to registers. If there are more candidates than there are physical registers, the register allocator must spill a live range (the home location is in memory) or split a live range (the live range occupies multiple locations). One of the challenges for a register allocator is to deal with spilling and splitting together. Fusion-based register allocation uses the structure of the program to make splitting and spilling decisions, with the goal to move overhead operations to infrequently executed parts of a program. The basic idea of fusion-based register allocation is to build up the interference graph. Starting with some base region (e.g., a basic block, a loop), the register allocator adds basic blocks to the region and incrementallly builds the interference graph. When there are more live ranges than registers, the register allocator selects live ranges to split; these live ranges are split along the edge that was most recently added to the region. This article describes fusion-based register allocation in detail and compares it with other approaches to register allocation. For programs from the SPEC92 suite, fusion-based register allocation can improve the execution time (of optimized programs, for the MIPS architecture) by up to 8.4% over Chaitin-style register allocation.

Cited by 48Open access

Register Allocation using GPUs

Nilesh Mahajan, Kailash Nagarkoti · 2012

Register allocation is one the most important compiler passes. The quality of the generated code both in terms of code size and performance depends on this important pass. Unfortunately, the problem is NP-complete so unless P equals NP , there is no efficient solution to this problem. Thus various heuristics are applied to get an approximate solution. Our approach is to leverage the parallelism provided by GPUs to solve this problem.

Cited by 0

Complete Register Allocation Problems

Ravi Sethi · SIAM Journal on Computing · 1975

The search for efficient register allocation algorithms dates back to the time of the first FORTRAN compiler for the IBM 704. The model we use in this paper is a single processor with an arbitrarily large number of general registers. The objective is to use as few registers as possible, under the,constraint that no stores into memory are permitted. The programs under consideration are sequences of assignment instructions. We show that, given a program and an integer k, determining if the program can be computed using k registers is polynomial complete. It should be noted that k can be any integer.

Cited by 199

Register Allocation sans Coloring

Ksheerabdhi Krishna, Sanjay M. Krishnamurthy · 1994

The time spent on register allocation must be reasonable compared to other global optimizations in a compiler. While graph coloring is an excellent abstraction for global register allocation, it incurs high overhead with respect to both memory consumption and compile time. We describe a new algorithm for global register allocation called fast allocation to address this problem. Fast allocation avoids graph coloring but achieves a global allocation by allocating and assigning registers in two passes -- a local pass and a global pass. While it affects the execution time performance of codes, the fast allocator is attractive when one seeks a reasonable balance between compile and execute time. Experimental results of an implementation of fast allocation are presented to validate our claim. Keywords: register allocation, graph coloring, interference graph, data flow analysis, live ranges, coalescing, instruction scheduling. Make it as simple as possible but not simpler. Albert Einstein 1...

Cited by 0

Architecture Independent Register Allocation

Felix Stanley, Klock Ii, Martin C. Rinard et al. · 2001

This thesis presents a framework for generic register allocation, in which the alloca-tion algorithm is completely seperated from the constraints of the source language or target architecture. This allows the backend of a compiler to be designed in a modu-lar fashion: one module implements the allocation algorithm, while another module describes the properties of the targetted architecture. The design of the framework is described using the Alloy modelling language, in order to illustrate the approaches used to handle various issues that arise when attempting to abstractly represent the constraints introduced by the assembly code processed by the allocator. The frame-work is one component of the MIT Flex compiler infrastructure, which is written in Java and compiles Java bytecodes into a variety of target assembly languages, such as MIPS and ARM.

Cited by 0