Optimal Bitwise Register Allocation using Integer Linear Programming

Rajkishore Barik^{∗}  Christian Grothoff^{†}  Rahul Gupta^{‡}  Vinayaka Pandit^{§}

Raghavendra Udupa^{¶} IBM India Research Lab

Abstract

This paper addresses the problem of optimal global register allocation. The register allocation problem is expressed as an integer linear programming problem and solved optimally. The model is more flexible than previous graph-coloring based methods and thus allows for register allocations with fewer moves and spills. The formulation can model complex architectural features, such as bit-wise access to registers. With bit-wise access to registers multiple subword temporaries can be stored in a single register and accessed efficiently, resulting in a register allocation problem that cannot be addressed with simple graph coloring. The paper describes techniques that can help reduce the problem size of the ILP formulation and reports preliminary empirical results from an implementation prototype.

1 Introduction

The traditional approach towards optimal register allocation is to color the interference graph [7]. If the number of colors exceeds the number of registers, temporaries are selected for spilling until the graph becomes colorable. The approach presented in this paper makes a radical departure from the graph coloring model in order to avoid the boolean decision of spilling or not spilling a temporary. The basic idea is to allow temporaries to switch registers at any time and to use constraints to force temporaries that are used at a given instruction into appropriate registers only at the time of use. Moving a variable between registers or between registers and the stack is associated with a cost in the goal function of the ILP. The search space for the ILP solver is reduced using observations about the time at which it makes sense for a temporary to be spilled in an optimal allocation.

In order to show the expressive power of the approach, this work describes a way to perform optimal register allocation for architectures that allow bit-wise access to registers as proposed in [16]. Various applications, in particular from the embedded domain, make extensive use of sub-word sized values. Examples include network stack implementations and signal- and image-processing as well as hardware drivers. For these applications, bit-wise register allocation can reduce register pressure. Under the assumption that the cost of adding instructions that support sub-word access is smaller than the cost of adding additional registers (or increasing the processor speed to offset the spill-costs), bit-wise register allocation can help reduce total system cost.

The goal of this work is the formulation and evaluation of an algorithm that produces optimal register assignments for embedded processors, including processors with sub-word access to registers. While instruction scheduling is not within the scope of the paper, the presented algorithm is able to take structural properties of a program, such as loops, into consideration. Given perfect loop information (in terms of number of iterations) as well as exact estimates for the cost of registerto-register and register-to-stack moves, the algorithm produces a register assignment with minimal cost.

The proposed approach uses Integer Linear Programming (ILP) [22] for bitwise register allocation and assignment. While the focus of the paper is on bitwise register allocation, the technique presented encompasses a large body of previous work on register allocation. In addition to bit-wise register allocation, the model used in the ILP formulation supports coalescing, spilling, use of registers for both spilling and ordinary temporaries, non-orthogonal register sets and rematerialization. The ILP formulation allows the ILP solver to consider all of these options and to produce a solution which results in optimal code in terms of the cost metric. The cost metric used models the cost of spilling (including increased cost for spill code in loops) register-to-register moves as well as reduced costs for rematerialized constant values.

∗rajbarik@in.ibm.com †christian@grothoff.org ‡rahulgupta@in.ibm.com §pvinayak@in.ibm.com ¶raghavendra udupa@in.ibm.com

The input to the algorithm consists of variable liveness information, access cost for accessing a spilled temporary for each program point and processor-specific cost metrics for the various operations that the register allocator may use. Variable liveness information is given in the form of the number of bits of a temporary that may be live at each point in the program. There are various known algorithms to conservatively approximate the bit-width of a temporary [25, 26]. The presented algorithm would work with any of these algorithms. The experimental evaluation given in this paper uses range limitations based on the type of the temporary.

The remainder of the paper is organized as follows. After an overview of related work in section 2 the ILP formulation for the bit-wise register allocation is introduced in section 3. The implementation is described in section 4. Section 4 presents performance data for various benchmarks and concludes the paper with a discussion of the benefits and limitations of this approach.

2 Related Work

Previous work has focussed on register allocation at local, global, intraprocedural, and interprocedural levels. Intraprocedural register allocation is known to be a NPhard problem and several heuristics have been proposed to solve the problem [6, 7, 5]. In [14] a polynomial time algorithm for interprocedural register allocation is presented. The algorithm uses profile information to determine the allocation of registers to procedures and the placement of spilling. Interprocedural register allocation as modeled by the authors belongs to a special class of ILP called minimum cost network flow problem.

ILP has been used previously for register allocation and instruction scheduling. In [20] ILP is used to allocate temporaries to registers for the Z86, an architecture with register banks in which the size of the generated code depends on the location of temporaries with respect to the current bank. The resulting ILP formulation can be used to enforce constraints on code size. In [21] ILP is used to find opportunities for performing parallel loads of two spilled 32-bit values on a 64-bit bus by computing optimal stack co-locations.

An approach to combined instruction scheduling and register allocation for DSP based on ILP is described in [12]. The author discusses and enhances ILP formulations for instruction scheduling based on [27] and [9, 10], which optimally group instructions into bundles according to architectural constraints. The ILP solution includes a feasible register allocation, but the ILP solver fails if a feasible solution for the given instruction sequence a feasible solution would require the addition of spill-code. The author claims that spilling cannot be integrated since the ILP is always constructed for a fixed instruction sequence. In contrast, this work shows that it is possible to formulate an ILP for register allocation that includes spilling. The integration of instruction scheduling and register allocation with spilling is left for future work.

In [3], the authors solve the register allocation problem for CISC machines by dividing it into two subproblems - optimal spilling and register coalescing. The optimal spilling problem is solved optimally using ILP, while a variant of Park and Moon’s heuristic [23] is used for solving the register coalescing problem (sub-optimally). The authors exploit the CISC instruction set to optimize the cost of loads and stores. They take into account that number of available registers may vary from program point to program point, but do not consider variable bit-width requirements of temporaries. In [17] an approach to speculative subword register allocation based on optimistic register allocation is proposed. The idea behind this paper is that there are more opportunities for subword allocation at run-time than what can be statically determined to be safe. The authors propose to use profiling data to speculatively pack variables that are most of the time sufficiently small into a register and to have the processor dynamically detect and flag the case where the size constraints are not met. This requires support by the processor which needs to keep an additional bit per register. If the flag is raised for a given register, the processor executes the appropriate stack accesses instead. The problem with this approach is that in addition to needing additional processor support the authors fail to establish that their dynamic technique yields significantly more subword allocation opportunities compared to designs based on static analysis like the ones presented in this paper.

A common complication in register allocation is that not all registers are equal, which is the case for many processors. On such processors, registers are grouped into classes or register families. A simple example is that of floating point registers that are required for floating-point operations and not supported for ordinary instructions. Extending the ILP formulation presented in this paper to support register classes can be done by adding the appropriate constraints and by adjusting the weights in the cost function accordingly. However, in order to simplify the presentation, the rest of this paper will be presented for the case where all registers are equal.

3 ILP Formulations

The key idea for the algorithm is to avoid assigning a temporary a fixed location and instead to formulate certain constraints on the location in the form of an integer linear problem (ILP) [22]. The goal function of the ILP captures the cost of the resulting register allocation. The ILP is then solved using off-the-shelf ILP solver technology.

The input to the ILP-solver is a set of constraints that describe the register allocation problem. The basic constraints are that each temporary must be assigned to exactly one register, and that a register must have enough space to hold all temporaries assigned to it. Dead temporaries do not use any space. Throughout the paper, the stack is modeled as a special register σ that has no space constraints. All other registers can only store b bits of information.

In order to make the ILP formulation more accessible, the required constraint-system is grown in several steps, each step adding additional capabilities. Section 3.1 introduces the basic ILP formulation that computes optimal register allocations under the constraint that temporaries are fixed to just one register (or the stack) for the entire duration of the function. The resulting solutions correspond to traditional graph coloring designs, except that it already includes bit-wise register allocation. The first extension (section 3.2) allows storage of the temporary in different registers (including the stack) at differt times. The second extension (section 3.5) removes this restriction and replaces the linear model of time with the control-flow graph of the function. These first two models assume that accessing spilled temporaries merely incurs an additional access cost, the registers required to access spilled temporaries are not made available to the allocator. The third model (section 3.6) allows the allocator to assign temporaries to all registers with the additional constraint that it must also reserve register space for spilled temporaries at the times where instructions access such values. Various minor extensions and optimizations to the formulation are discussed where applicable.

3.1 Basic formulation

The basic formulation only considers allocating one register per temporary for the lifetime of that temporary. Moving a temporary between registers or between registers and the stack is not allowed in this model. The casual reader can ignore the bit-wise nature of the register allocation and view the problem in a simplified manner where dead temporaries have a bit-width of zero and all live temporaries are word-sized. This would also be the natural simplification to the algorithm for architectures without bit-wise access to registers.

The input to the problem is sets of temporaries i ∈ V and registers r ∈ R, spill costs S_{i} for each temporary i ∈ V and the size w_{i,t} for temporary i ∈ V at time t ∈ T. For now, a linear model of time is assumed with timestamps t ∈ T before and after each instruction. The temporary σ ∈ R is used to represent the stack, which is not constrained in size and is used for spilling. All other registers r ∈ R − {σ} are limited to b bits (b is typically 32). The result of the computation is an allocation X_{i,r} ∈ {0, 1}, with i ∈ V and r ∈ R, that assigns every temporary a unique register (or the stack σ). The problem can then be stated in a way suitable for integer-linear programming (ILP):

min ∑_{i∈V} S_{i} · x_{i,σ}  (1)
such that ⋀_{{r∈R−\{σ\} \atop t∈T}}  ∑_{i∈V} x_{i,r} · w_{i,t} ≤ b  (2)

⋀_{i∈V} ∑_{r∈R} x_{i,r} = 1  (3)
⋀_{{i∈V \atop r∈R}} x_{i,r} ∈ \{0, 1\}  (4)

Equation (1) models the cost of the solution by summing up the costs of loading temporaries i ∈ V that have been spilled (x_{i,σ} = 1) from the stack. Equation (2) states that at all times and for all registers except the stack, the total size of all temporaries stored in any register must not exceed the register size b. Equations (3) and (4) state that every temporary must be assigned exactly one location.

3.2 Optimal spilling

The optimal register allocation often requires that a temporary is spilled part of the time or that it is moved from one register to another (in order to reclaim fragmented space in the registers). This problem can be formulated using linear constraints by introducing additional temporaries c_{i,r,t} ∈ {0, 1} that capture at which times t ∈ T register r ∈ R has been allocated to a new temporary i ∈ V. Let t_{0} ∈ T be the time before the first instruction of the function. Let x_{i,r,t} ∈ {0, 1} be the decision function that places temporary i ∈ V into register r ∈ R at time t ∈ T.

Let S_{i,t} be the spill cost of i ∈ V at time t ∈ T. S_{i,t} is zero if i is not accessed at time t. S_{i,t} gives the cost of loading i from the stack if i is used at the instruction after time t. If i is defined at the instruction before t, then S_{i,t} is the cost of spilling i to the stack.

Let μ_{r} ∈ ℝ be the cost of moving a value to or from register r ∈ R. Using μ_{r}, the cost of a move between register a and b is assumed to be given by μ_{a} + μ_{b}. For example, given only one family of registers, the value for μ_{r} for r ∈ R−{σ} is half the cost of a register-to-register move. In this case, if S is the cost of moving a value between the stack and a register, then μ_{σ} = S − μ_{r}. The resulting ILP formulation is:

min ∑_{{i∈V \atop t∈T}} S_{i,t} · x_{i,σ,t} + ∑_{{i∈V \atop r∈R}} μ_{r} · ∑_{t∈T} c_{i,r,t}  (5)

such that ⋀_{{r∈R−\{σ\} \atop t∈T}}  ∑_{i∈V} x_{i,r,t} · w_{i,t} ≤ b (6)

⋀_{{i∈V \atop t∈T}}  ∑_{r∈R} x_{i,r,t} ≥ 1 (7)

⋀_{{i∈V,r∈R \atop t∈T −\{t_{0}\}}} (x_{i,r,t} − x_{i,r,t−1}) + c_{i,r,t} ≥ 0 (8)

⋀_{{i∈V,r∈R \atop t∈T −\{t_{0}\}}} (x_{i,r,t−1} − x_{i,r,t}) + c_{i,r,t} ≥ 0 (9)

⋀_{{i∈V,r∈R \atop t∈T}} x_{i,r,t} ∈ \{0, 1\}  (10)

⋀_{{i∈V,r∈R \atop t∈T}} c_{i,r,t} ∈ \{0, 1\}  (11)

The new constraints (8) and (9) ensure that c_{i,r,t} must be 1 each time that x_{i,r,t} changes. The modified goal function (5) makes accomodations for the accumulated cost of all moves. Note that this formulation assumes that the cost of a move is independent of its direction, a simplification that may not be correct for some architectures. Handling asymmetric move costs would increase the size of the ILP significantly. The ILP formulations presented in this paper only model symmetric move costs; nevertheless, the allocations computed are still sound (though possibly suboptimal) for architectures with asymmetric move costs. An evaluation of the possible benefits of modeling asymmetric move costs is left for future work.

3.3 Zero-cost moves

Dead temporaries can be moved between registers at no cost. The model so far considers all moves to be of equal cost, regardless of the liveness of the temporary. A good way to allow for zero-cost moves is to split all temporaries with multiple disjoint live-times into multiple temporaries, one for each live-time. While this increases the size of the set V, the simplification presented in the next section avoids significant growth of the problem due to this extension.

In GCC, data-flow of temporaries is modeled using webs, where a single program temporary can correspond to multiple webs. The way GCC splits temporaries into webs exactly follows the requirements stated above, that is, temporaries with disjoint lifetimes are split into multiple webs, with exactly one web per lifetime.

3.4 Optimizations to the ILP

The ILP stated so far can be optimized in order to achieve faster solution times. The basic idea is to reduce the search space for the ILP solver by adding constraints that fix the value of problem variables without changing the value of the goal function for the optimal solution.

Let L_{t} ⊆ V be the set of temporaries that are not accessed at time t ∈ T. Considering that S_{i,t} specifies the spill-cost for temporary i at time t ∈ T, the exact definition of L_{t} is

L_{t} := {i ∈ V |S_{i,t} = 0}.  (12)

Let M_{t} ⊆ L_{t} be the set of temporaries that are not accessed at time t ∈ T and that are either dead or have maximum size (in the number of bits) at time t ∈ T. Formally

M_{t} := {i ∈ L_{t}|w_{i,t} ∈ {0, b}}.  (13)

Lemma 1 The optimality of the solution computed by the ILP solver is preserved if the constraint

⋀_{{r∈R \atop t∈T}} ⋀_{i∈M_{t}} x_{i,r,t} = x_{i,r,t+1}  (14)

is added. The constraint further implies that

⋀_{{r∈R \atop t∈T}} ⋀_{i∈M_{t}} c_{i,r,t} = 0.  (15)

Proof: Suppose for some r ∈ R, t ∈ T, i ∈ L_{t} an optimal solution to the ILP exists with x_{i,r,t} ≠ x_{i,r,t−1}. If x_{i,r,t} = 1, then i was moved at time t out of register r ∈ R. If w_{i,t} = 0, perfoming the move earlier at time t − 1 makes no difference at all (since the temporary is dead and only assigned a register pro-forma). Suppose w_{i,t} = b. In that case, i must be moving from the stack into a register or vice versa, since moving i from one register r ∈ R − {σ} to another register r′ ∈ R − {r, σ} must be a useless move in an architecture with orthogonal registers and can thus not occur in an optimal solution.^{1} Assume that i is moved from σ to register r ∈ R − {σ}. Then this move can be deferred until time t + 1 (change to the previous optimal solution requires setting x_{i,r,t} = 0 and x_{i,σ,t} = 1). This is always possible, since deferring the move only reduces register pressure (σ has no space constraint). Similarly, if the move is from register r inR−{σ} to σ, the move can be performed earlier at t − 1, again strictly reducing register pressure. The situation for x_{i,r,t} = 0 is analogous.

□

3.5 Graph coloring formulation

The ILP formulation presented so far only models a linear instruction sequence using timestamps t ∈ T. In practice, however, control-flow is often not linear. Linear models of the instruction sequence and in particular of live-times of temporaries result in suboptimal register allocations. The algorithms presented so far are akin to linear-scan register allocation [24]. By modeling time relationships in a graph, the resulting register allocation algorithm is a stronger formulation of the well-known graph coloring algorithms [7], only that this approach integrates spilling and takes variable size temporaries into consideration.

Let (N, E) be the control-flow graph with nodes n ∈ N and directed edges (a, b) ∈ N ×N. Note that the control-flow graph does not use basic blocks; instead, each individual statement corresponds to two nodes in the graph, one for the register allocation before the instruction and another one for the register allocation after the instruction (see Figure 1).

Let w_{i,n} be the number of bits that temporary i ∈ V requires at node n ∈ N. Let pred(n) = {p|(p, n) ∈ E} be the set of immediate predecessors of node n ∈ N. Let μ_{r,n} be the cost of spilling to or from register r at node n. The idea behind adding the dimension n ∈ N to μ is to allow the specification of a higher cost for code within loops. Let S_{i,n} be the spill-cost for temporary i ∈ V at node n ∈ N. The spill-cost at node n ∈ N for a node preceeding an instruction is the cost of loading the value from the stack if the temporary is accessed by the instruction. The spill-cost for a node succeeding an instruction is the cost of spilling the temporary to the stack. The final version of the ILP problem is then:

\xymatrix{ & n_{0} \ar[d]^{IF} \\  & n_{1} \ar[dr] \ar[dl] \\ n_{2} \ar[d]_{ADD} &  & n_{3} \ar[d]^{SUB} \\ n_{4} \ar[dr] &  & n_{5} \ar[dl] \\  & n_{6} \ar[d]^{RET} \\  & n_{7}}

Figure 1: Illustration of the relationship between the nodes n ∈ N and the instructions.

min ∑_{{i∈V \atop n∈N}} S_{i,n} · x_{i,σ,n} + ∑_{{i∈V \atop r∈R,n∈N}} μ_{r,n} · c_{i,r,n}  (16)

such that ⋀_{{r∈R−\{σ\} \atop n∈N}}  ∑_{i∈V} x_{i,r,n} · w_{i,n} ≤ b (17)

⋀_{{i∈V \atop n∈N}}  ∑_{r∈R} x_{i,r,n} ≥ 1 (18)

⋀_{{i∈V,r∈R \atop n∈N}} ⋀_{p∈pred(n)} (x_{i,r,n} − x_{i,r,p}) + c_{i,r,n} ≥ 0 (19)

⋀_{{i∈V,r∈R \atop n∈N}} ⋀_{p∈pred(n)} (x_{i,r,p} − x_{i,r,n}) + c_{i,r,n} ≥ 0 (20)

⋀_{{i∈V,r∈R \atop n∈N}} x_{i,r,n} ∈ \{0, 1\}  (21)

⋀_{{i∈V,r∈R \atop n∈N}} c_{i,r,n} ∈ \{0, 1\}  (22)

Optimizations for graph coloring formulation

The search space reduction from 3.4 only applies for linear sequences of code since moving a move across a branch may increase the total number of moves. Furthermore, the search space reduction assumes that μ_{r,n} is constant for such linear code sequences, but considering that μ_{r,n} models the impact of loops, this assumption should be always hold in practice. However, the optimization can be applied across basic blocks for dead variables (w_{i,n} = 0).

1Note that this would not be true for w_{i,t} ∈ (0, b), since such a move might defragment the available space in the registers in that case.

3.6 Avoiding to block registers for spilling

Whenever a spilled temporary is used by an instruction, it must be loaded into a register before execution of that instruction. Similarly, if an instruction produces a temporary that is not allocated a register at that point, the result must be temporarily stored in a register before it can be spilled onto the stack. A common technique is to reserve a few registers for accessing the spilled temporaries. These registers are then excluded from the ordinary register allocation process. The formulation presented so far assumes that a sufficient number of such registers exist outside of the set of available registers R that is made available to the ILP solver.

Such a formulation can result in sub-optimal register allocation. The reason is that if the registers used for accessing spilled temporaries were made available to the register allocator, spilling might not be required at all. A pre-pass without these reserved registers may still not be sufficient to compute the optimal solution since spilling may only be required for part of the time, allowing for registers to be assigned to (non-spilled) temporaries at other times, even within the same function. Furthermore, why should always the same registers be used for spilled temporaries? The following formulation relaxes these unnecessarily strict restrictions and instead merely states the exact requirements for a correct register allocation in order to allow the ILP solver to produce better solutions.

Let a_{i,n} ∈ {0, 1} be a condition temporary that indicates that at node n temporary i is accessed (used or defined). Since S_{i,n} gives the cost for accessing a spilled variable, this means a_{i,n} := sgn(S_{i,n}). Let b_{r,n} ∈ {0, 1} indicate that register r is used for at least one assigned temporary at node n. The term “assigned temporary” is used to differenciate these temporaries from “spilled temporaries” in the classical sense. The following constraint is then sufficient to reserve registers for spilling (extending the ILP model from section 3.5):

⋀_{n∈N} ∑_{i∈V} a_{i,n} · x_{i,σ,n} + ∑_{r∈R−{σ}} b_{r,n} ≤ |R − {σ}| (23)
⋀_{{i∈V,r∈R \atop n∈N}} b_{r,n} · w_{i,n} ≥ x_{i,r,n} · w_{i,n}  (24)

⋀_{{r∈R \atop n∈N}} b_{r,n} ∈ \{0, 1\}  (25)

In (24) the value of b_{r,n} is forced to be one if a live temporary i exists (w_{i,n} ≠ 0) that is assigned to register r at node n (x_{i,r,n} = 1). As a result, ∑_{i∈V} a_{i,n} ·x_{i,σ,n} is the number of registers that must be reserved for spilled temporaries at node n and ∑_{r∈R−{σ}} b_{r,n} is the number of registers assigned to registers at that instruction.

Equation (23) describes that the number of allocated registers for both the spilled and register-allocated temporaries must not exceed the total number of registers.

Note that this formulation does not take bit-wise access to registers into account. While the ILP solution does allow assignment of temporaries to all registers at times, the formulation does not allow for the possibility of allocating just some bits of registers for the spilled temporaries. The problem with a formulation supporting this kind of allocation is that one would still have to ensure that the spilled temporaries are not scattered over multiple registers. This precludes a simple formulation over the sum of all bits assigned to temporaries.

3.7 Coalescing

Coalescing is an important step in register allocation that assigns the same register to temporaries that are connected by a move in order to reduce the number of move instructions. The problem with coalesing for previous register allocators is that forcing two temporaries to be in the same register can result in additional spilling. In [11] an algorithm is presented that attempts to minimize the number of moves without introducing any additional spills.

Since the ILP formulations presented in this paper (with the exception of the basic formulation in section 3.1) allow spilling temporaries on a per-instruction basis, they do not have the problem of additional spills due to too aggressive coalesing. Where in [6] the merging of move-connected temporaries would force these temporaries to be either spilled or kept in a register throughout their lifetime, the ILP formulation allows for partial spilling. Hence it is possible to merge all temporaries that are connected by moves upfront. The ILP solver will insert the necessary minimal number of moves and spills as required.

Also note that coalesing reduces the total number of variables and thus reduces the problem size of the ILP. From that perspective, coalescing should also be considered an optimization that improves the run-time of the register allocation algorithm.

3.8 Rematerialization

Rematerialization [4] is an important technique based on the realization that temporaries often have constant values and that loading a constant is typically significantly cheaper than loading the value from memory. Spilling of constants can therefore be avoided. Still, using an instruction to load a constant can be more expensive than keeping the constant in a register if a register is available. Thus, replacing all uses of a constant with a fresh temporary does not result in optimal code.

Rematerialization can be handled easily by the ILP formulation. The cost of loading an immediate value can be modeled exactly in the goal function. This can be achieved by modifying the goal function to allow for temporary-specific spill costs. Let μ_{i,r,n} be the cost of spilling temporary i ∈ V at time n ∈ N to or from register r ∈ R. For temporaries of constant value, the spill-cost to the stack would be zero. The spill-cost for loading a constant-value temporary from the stack would be the cost of a load-immediate instruction. The resulting goal function that incorporates the differenciated spill-cost due to rematerialization is then:

min ∑_{{i∈V \atop n∈N}} S_{i,n} · x_{i,σ,n} + ∑_{{i∈V \atop r∈R,n∈N}} μ_{i,r,n} · c_{i,r,n}  (26)

3.9 Summary

Figure 2 summarizes the final formulation of the ILP including support for rematerialization, coalescing, control-flow graph-based variable live-times, reusing registers for spilling and temporary allocation and bitwise register allocation. The problem size in terms of memory is O(|V | · |R| · |N|). The number of equations is O(|V | · |R| · (|N| + |E|)) where E is the set of edges in the control-flow graph.

4 Results

The ILP-based register allocator is implemented for gcc [2] using the GNU Linear Programming Kit [1]. The number of bits required for each temporary at various times in the execution is determined using type information available within gcc. The various cost-parameters in the ILP formulation were set using gcc’s built-in cost estimation functions.

gcc was instrumented to output an ILP formulation for the register allocation which was then passed to the ILP solver. Binary code is not generated, since a target platform with bit-wise access does not yet exist to the best of our knowledge. For the same reason run-time performance numbers cannot be given. The best performance metric is thus the static cost estimate given by the goal function in the ILP formulation (26) for different numbers of registers.

The evaluation five register allocators were compared. These include the basic ILP formulation from section 3.1 without coalescing, the graph-based ILP formulation from section 3.5 including coalescing with two registers reserved for accessing spilled temporaries and the final ILP formulation with all features from Figure 2. These new allocators were compared against two allocators implemented in gcc, which are Appel’s ([3]) and gcc’s own register allocator ([18]).

min ∑_{{i∈V \atop n∈N}} S_{i,n} · x_{i,σ,n} + ∑_{{i∈V \atop r∈R,n∈N}} μ_{i,r,n} · c_{i,r,n}  (27)

⋀_{{r∈R−\{σ\} \atop n∈N}}  ∑_{i∈V} x_{i,r,n} · w_{i,n} ≤ b  (28)

⋀_{{i∈V \atop n∈N}}  ∑_{r∈R} x_{i,r,n} ≥ 1  (29)

⋀_{{i∈V,r∈R \atop n∈N}} ⋀_{p∈pred(n)} (x_{i,r,n} − x_{i,r,p}) + c_{i,r,n} ≥ 0  (30)

⋀_{{i∈V,r∈R \atop n∈N}} ⋀_{p∈pred(n)} (x_{i,r,p} − x_{i,r,n}) + c_{i,r,n} ≥ 0  (31)

⋀_{n∈N} ∑_{i∈V} a_{i,n} · x_{i,σ,n} + ∑_{r∈R−{σ}} b_{r,n} ≤ |R − {σ}| (32)

⋀_{{i∈V,r∈R \atop n∈N}} b_{r,n} · w_{i,n} ≥ x_{i,r,n} · w_{i,n}  (33)

⋀_{{i∈V,r∈R \atop n∈N}} x_{i,r,n} ∈ \{0, 1\}  (34)

⋀_{{i∈V,r∈R \atop n∈N}} c_{i,r,n} ∈ \{0, 1\}  (35)

⋀_{{r∈R \atop n∈N}} b_{r,n} ∈ \{0, 1\}  (36)

Figure 2: The complete ILP formulation with all features. w_{i,n} is the number of live bits of variable i at node n. The cost of spilling i to or from register r at node n is given by μ_{i,r,n}. The cost of accessing the variable i at node n if i is spilled at that point is S_{i,n}. The resulting allocation is given by x_{i,r,n} = 1 if and only if variable i is stored in register r at node n. Spilling is indicated using the special register σ ∈ R.

4.1 Benchmarks

The performance of the approach is evaluated using benchmarks from the Mediabench [15], NetBench [19] and Bitwise [25] suites. These benchmarks are appropriate since they correspond to the real-world applications where sub-word access to temporaries is common. Furthermore, using the same benchmarks as [26] enables comparisson with prior work on bitwise register allocation. In addition a C implementation of the RipeMD160 cryptographic hash function [8] was evaluated. These function results in the largest ILP problem among all functions evaluated and thus gives an insight into the scalability of the proposed approach.

4.2 Impact of the optimizations

Applying Lemma 1 to the ILP formulation reduces the number of problem variables between 66 and 98%. Most benchmarks see a reduction of 85–90%. Note that the reduction of problem variables does not only reduce the space requirements but also significantly reduces the search space for the ILP solver. Performing coalescing eliminates in the range of XX to YY% of all variables, again resulting in dramatic improvements in scalability for the algorithm.

4.3 Performance

Figure 3 shows the cost as estimated by the goal function (26) for the various register allocation algorithms for all benchmarks.

The impact of changing the total number of available registers is shown in Figure 4 for the Ripe160MD benchmark.

Figure 5 lists the time it took to solve the different ILP problems using the GLPK ILP solver [1] on a Pentium IV with 3 Ghz and 512 MB memory running Linux 2.4.18. The ILP approach is clearly the slowest of the compared algorithms, but the times are still feasible when compiling small programs for embedded systems where high performance and low per-unit cost are paramount.

4.4 Discussion

Extending the ILP formulation to architectures with non-orthogonal register sets (like x86) is straightforward. If node n requires temporary i to be in registers N ⊂ R, the constraint ∑_{r∈N} x_{i,r,n} = 1 is sufficient to model the requirement. The ILP optimization presented in section 3.4 needs to be restricted further for non-orthogonal architectures; equation (13) needs to be restricted to dead temporaries:

M′_{t} := {i ∈ L_{t}|w_{i,t} = 0}.  (37)

The presented algorithm does not take intra-register fragmentation of space into account. It is thus theoretically possible that the computed allocations for a given register will result in a situation where additional moves within the same register are required to ensure that a temporary is using consecutive bits in the same register. The ILP does currently not model the cost of such moves. This is not a serious drawback since such moves should be both inexpensive and extraordinarily rare in practice.

The presentation so far has focused on hardware with bit-wise access to registers. The formulation can be adjusted for processors that merely support subword access. An example of actual hardware supporting sub-word access to registers is the AH/AL split in the Intel 8086. Here, the 16-bit AX register is split into two 8-bit registers that can be accessed individually. The algorithms presented in this paper can be applied to this processor using the number of bytes instead of bits for the w_{i,t}s (with b = 2).

Note that it is trivial to simplify the presented algorithm to handle more ordinary architectures that only support word-size access to registers. For those architectures, the resulting register allocation will still be optimal, but the differences with conventional heuristics [11] are likely to be less pronounced. Future work will have to compare the integrated ILP formulation with not only these heuristics but also with approaches that combine instruction scheduling and register allocation [12, 13].

Future work will have to focus on improving the ILP solution times. Using heuristics to compute a feasible register allocation and feeding this as an input into the ILP solver is one path that is likely to result in significant improvements. With the current approach the solver sometimes spends a lot of time merely computing a feasible solution. Another approach is to avoid computing an optimal solution by aborting the ILP solver if the computation takes too long. This will allow the user to select an appropriate trade-off between register allocation quality and compile-time.

5 Conclusion

This paper introduced a new ILP-based algorithm for bit-wise register allocation. The presented formulation expands the expressiveness of the model of existing ILPbased register allocation algorithms and hence allows for better solutions. The algorithm integrates previous techniques including coalesing, spilling, rematerialization and register families and allows for temporaries to be temporarily spilled. The formulation supports using the same register for access to spilled temporaries or direct temporary assignment at different times. Experimental results show that the resulting ILP problems can be solved by modern of-the-shelf ILP software, resulting in register assignments that substancially improve on assignments computed by state-of-the-art techniques.

References

[1] http://www.gnu.org/software/glpk/.

[2] http://gcc.gnu.org/, 2004.

[3] Andrew W. Appel and Lal George. Optimal spilling for cisc machines with few registers. In Proceedings of the ACM SIGPLAN 2001 conference on

Suite  Mediabench [15] NetBench [19]  Bitwise [25]
Benchmark  adpcm  g721 crc  dh SoftFloat NewLife MotionTest Bubblesort Histogram

ILP (Section 3.1) ILP (Section 3.5) ILP (Figure 2)

Figure 3: Cumulative cost of the register allocation for 16 registers as estimated by the ILP’s target function. Smaller is better.

Registers  1 2 3 4 8 16 32

ILP (Section 3.1) ILP (Section 3.5) ILP (Figure 2)

Figure 4: Cumulative cost of the register allocation for different numbers of registers as estimated by the ILP’s target function for the Ripe160MD benchmark. Smaller is better.

Programming language design and implementation, pages 243–253, 2001.

[4] Preston Briggs, Keith D. Cooper, and Linda Torczon. Rematerialization. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI), volume 27, pages 311–321, New York, NY, 1992. ACM Press.

[5] Preston Briggs, Keith D. Cooper, and Linda Torczon. Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems, 16(3):428–455, May 1994.

[6] G. J. Chaitin. Register allocation and spilling via graph coloring. In Proceedings of the ACM SIG-PLAN ’82 Symposium on Compiler Construction, pages 98–105, Jun.

[7] Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. Register allocation via coloring. Computer Languages, 6:47–57, 1981.

[8] Hans Dobbertin, Antoon Bosselaers, and Bart Preneel. RIPEMD-160: A strengthened version of RIPEMD. In Fast Software Encryption, pages 71– 82, 1996.

[9] Catherine H. Gebotys and Mohamed I. Elmasry. Optimal VLSI Architectural Synthesis. Kluwer Academic Publishers, 1992.

[10] Catherine H. Gebotys and Mohamed I. Elmasry.

Global optimization approach for architectural synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 1266–1278, September 1993.

[11] Lal George and Andrew W. Appel. Iterated register coalescing. ACM Transactions on Programming Languages and Systems, 18(3):300–324, May 1996.

[12] Daniel Kästner. Instruktionsanordnung und Registerallokation auf der Basis ganzzahliger linearer Programmierung für den digitalen Signalprozessor ADSP-2106x. Master’s thesis, Universität des Saarlandes, 1997.

[13] Daniel Kästner and Sebastian Winkel. ILP-based Instruction Scheduling for IA-64. In Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers and Tools for Embedded Systems, Snowbird, June 2001.

[14] Steven M. Kurlander and Charles N. Fischer. Minimum cost interprocedural register allocation. In Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 230–241, 1996.

[15] Chunho Lee, Miodrag Potkonjak, and William H. Mangione-Smith. Mediabench: A tool for evaluating and synthesizing multimedia and communicatons systems. In International Symposium on Microarchitecture, 1997.

[16] Bengu Li and Rajiv Gupta. Bit section instruction set extension of arm for embedded applications. In Proceedings of the international conference on Compilers, architecture, and synthesis for embedded systems, pages 69–78. ACM Press, 2002.

[17] Bengu Li, Youtao Zhang, and Rajiv Gupta. Speculative subword register allocation in embedded processors. In Proceedings of the LCPC 2004 Workshop, 2004.

Suite  Mediabench [15] NetBench [19]  Bitwise [25]
Benchmark  adpcm  g721 crc  dh SoftFloat NewLife MotionTest Bubblesort Histogram

ILP (Section 3.1) ILP (Section 3.5) ILP (Figure 2)

Figure 5: Execution time for solving the different ILPs in minutes.

[18] Michael Matz. Design and implementation of a graph coloring register allocator for gcc. In Proceedings of the GCC Developers Summit, pages 151–169, May 2003.

[19] Gokhan Memik, William H. Mangione-Smith, and Wendong Hu. Netbench: a benchmarking suite for network processors. pages 39–43.

[20] Mayur Naik and Jens Palsberg. Compiling with code-size constraints. ACM Transactions on Embedded Computing Systems, 3(1):163–181, 2004.

[21] V. Krishna Nandivada and Jens Palsberg. Efficient spill code for sdram. In Proceedings of the 2003 international conference on Compilers, architectures and synthesis for embedded systems, pages 24–31. ACM Press, 2003.

[22] John L. Nazareth. Computer Solution of Linear Programs. Oxford University Press, 1987.

[23] Jinpyo Park and Soo-Mook Moon. Optimistic register coalescing. In Jean-Luc Gaudiot, editor, International Conference on Parallel Architectures and Compilation Techniques, pages 196–204, Paris, October 1998. IFIP,ACM,IEEE, North-Holland.

[24] Massimiliano Poletto and Vivek Sarkar. Linear scan register allocation. ACM Transactions on Programming Languages and Systems, 21(5):895– 913, 1999.

[25] Mark Stephenson, Johnathan Babb, and Saman Amarasinghe. Bitwidth analysis with application to silicon compilation.

[26] Sriraman Tallam and Rajiv Gupta. Bitwidth aware global register allocation. ACM SIGPLAN Notices, 38(1):85–96, January 2003.

[27] L. Zhang. SILP. Scheduling and Allocating with Integer Linear Programming. PhD thesis, Technische Fakultät der Universität des Saarlandes, 1996.