Browse Prior Art Database

Architecture Considerations for Smart Variables Preassignment Decision

IP.com Disclosure Number: IPCOM000240577D
Publication Date: 2015-Feb-10
Document File: 5 page(s) / 420K

Publishing Venue

The IP.com Prior Art Database

Abstract

The paper presents a method for efficient use of resources in the context of architectures with various types of specificities and constraints. By defining a method for efficient assignment of variables to registers without losing the architecture specific considerations, the number of memory locations within a program is reduced to minimum. The method has impact on many components of the compiler and it was designed to be easily applied into a retargetable compiler environment.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 34% of the total text.

Architecture Considerations for Smart

Variables Preassignment Decision

Abstract

The paper presents a method for efficient use of resources in the context of architectures with various types of specificities and constraints. By defining a method for efficient assignment of variables to registers without losing the architecture specific considerations, the number of memory locations within a program is reduced to minimum.  The method has impact on many components of the compiler and it was designed to be easily applied into a retargetable compiler environment.

Introduction

The common belief  that a compiler can generate code by loading everything to virtual registers (during instruction selection) and then start spilling them (during register coloring) has proven to not be very well suited for all types of architectures. For some architectures this well-known technique might lead to an increase in the number of spill locations. An alternative would be to do a preassignment evaluation in order to establish the most suited location of each local variable before instruction selection. The heuristic on which the preassignment algorithm is based takes into account two types of considerations:

·         General considerations like:

o    Variable live ranges

o    Variable interference graph

o    Data types

·         Architecture specific considerations like:

o    Register set architecture

o    Inter-operand constraints

o    Addressing modes with auto-update

o    Hardware loops

Architecture specific considerations

The general considerations are a powerful set of rules that help the preassignment algorithm in taking the best decision when choosing the storage location of a variable. But what really makes the difference when it comes to code efficiency are the architecture specific considerations.

The article presents a method to model architecture specific features in order to improve the register allocation. It proposes a technique that is opposed to the common mechanism of generating the code using an infinite number of virtual registers and then coloring/spilling these virtual registers during register allocation. In order to achieve this, a component responsible for determining the optimum storage-location of variables based on general considerations and architecture specific considerations was designed. The component has to walk through different checks (that are modeled as cost functions) and compute a spill value for each local/temporary variable. A cost function is a one-to-one mapping with an architecture specific feature. The method presented in this article uses the following cost functions:

·         A cost function to evaluate the efficiency of substituting a register class with another register class. At some point in a program, when a new instruction has to be encoded, it is possible to run out of registers of a specific class. Instead of spilling one of the already allocated register, a search can be performed to check if registers from another class (of greater size) can be u...