Sid-Ahmed-Ali Touati
email: touati@prism.uvsq.fr

Register Saturation in Instruction Level Parallelism

Keywords: Register Requirement, Register Pressure, Instruction Level Parallelism, Integer Linear Programming, Optimizing Compilation

The registers constraints are usually taken into account during the scheduling pass of an acyclic data dependence graph (DAG): any schedule of the instructions inside a basic block must bound the register requirement under a certain limit. In this work, we show how to handle the register pressure before the instruction scheduling of a DAG. We mathematically study an approach which consists in managing the exact upper-bound of the register need for all the valid schedules of a considered DAG, independently of the functional unit constraints. We call this computed limit the register saturation (RS) of the DAG. Its aim is to detect possible obsolete register constraints, i.e., when RS does not exceed the number of available registers. If it does, we add some serial edges to the original DAG such that the worst register need does not exceed the number of available registers. We propose an appropriate mathematical formalism for this problem. Our generic processor model takes into account superscalar, VLIW and EPIC/IA64 architectures. Our deeper analysis of the problem and our formal methods enable us to provide nearly optimal heuristics and strategies for register optimization in the face of ILP.

Introduction

The introduction of instruction level parallelism (ILP) has rendered the classical techniques of register allocation for sequential code semantics inadequate. In [START_REF] Freudenberger | Phase Ordering of Register Allocation and Instruction Scheduling[END_REF], the authors showed that there is a phase ordering problem between classical register allocation techniques and ILP instruction scheduling. If a classical register allocation is done early, the introduced false dependences inhibit instruction scheduling from extracting a schedule with high amount of ILP. However, this conclusion does not prevent a compiler from effectively performing an early register allocation, with the condition that the allocator is sensitive to the scheduler, as done in [START_REF] Ambrosch | Dependence-Conscious Global Register Allocation[END_REF][START_REF] Goodman | Code Scheduling and Register Allocation in Large Basic Blocks[END_REF][START_REF] Govindarajan | Minimum Register Instruction Sequencing to Reduce Register Spills in Out-of-Order Issue Superscalar Architecture[END_REF][START_REF] Janssen | Compilers Strategies for Transport Triggered Architectures[END_REF][START_REF] Norris | A Scheduler-Sensitive Global Register Allocator[END_REF][START_REF] Pinter | Register Allocation with Instruction Scheduling: A New Approach[END_REF]. Some other studies [START_REF] Bernstein | Scheduling Arithmetic and Load Operations in parallel with No Spilling[END_REF][START_REF] Brasier | CRAIG: A Practical Framework for Combining Instruction Scheduling and Register Assignment[END_REF][START_REF] Freudenberger | Phase Ordering of Register Allocation and Instruction Scheduling[END_REF][START_REF] Meleis | Dural-Issue Scheduling for Binary Trees with Spills and Pipelined Loads[END_REF][START_REF] Silvera | A Register Pressure Sensitive Instruction Scheduler for Dynamic Issue Processors[END_REF] claim that it is better to combine instruction scheduling and register allocation in a single complex pass, arguing that applying each method separately has a negative influence on the efficiency of the other. However, we think that this phase ordering problem arises only if the applied first pass (ILP scheduler or register allocator) is "selfish". Indeed, we can effectively decouple register constraints from instruction scheduling if enough care is taken. In this paper, we show how we can treat register constraints before scheduling, and we explain why we think that our methods provide better techniques than the existing solutions.

The principal reason for handling register constraints before instruction scheduling is that register allocation is more important as an optimization issue than code scheduling. This is because performance is far more sensitive to memory accesses than to fine-grain scheduling (memory gap): a cache miss may inhibit the processor from achieving a high dynamic ILP, even if the scheduler has extracted it at compile time. Even if we expect spill code to exhibit high locality, and hence likely produces cache hits, this cannot be asserted at compile time. It is very hard for a compiler to guarantee the existence of data inside a memory hierarchy level. Consequently, it is difficult to really guarantee the latency of a memory operation at compile time. So, the schedule of the instructions computed by the compiler wouldn't act in harmony with the dynamic execution of the hardware. The authors in [START_REF] Lin | Reducing DRAM Latencies with an Integrated Memory Hierarchy Design[END_REF] relate that about 66% of application execution times are spent satisfying memory requests. Furthermore, memory requests exhibit a high potential for conflicts, even if they are data independent. These conflicts are due to micro-architectural restrictions and simplifications in the memory disambiguation mechanisms (load/store queues) and possible banking structure in cache levels [START_REF] Jalby | Improving Load/Store Queues Usage in Scientific Computing[END_REF]. These possible conflicts may cause severe performance degradation even in the presence of high levels of ILP, and even if the data is located in the cache [START_REF] Jalby | An Efficient Memory Operations Optimization Technique for Vector Loops on Itanium 2 Processors[END_REF]. Of course, our claim that spill code is more damaging than a weak static ILP extraction is more appropriate for those architectures where memory access latency is very long compared to the delay of calculation. This is the case in almost all high performance processors. If memory access delay is not critical, the register saturation concept may be useless.

Another reason for handling register constraints prior to ILP scheduling is that register constraints are much more complex than resource constraints. Scheduling under resource constraints is a performance issue. Given a data dependence graph (DDG), we are sure to find at least one valid schedule for any underlying hardware properties (a sequential schedule in extreme case, i.e., no ILP). However, scheduling a DDG with a limited number of registers is more complex. Unless we generate superscalar codes with sequential semantics, we cannot guarantee in the case of VLIW the existence of at least one schedule. In some cases, we must introduce spill code and hence we change the problem (the input DDG). Also, a combined pass of scheduling with register allocation presents an important drawback if not enough registers are available. During scheduling, we may need to insert load-store operations if not enough free registers exist. We cannot guarantee the existence of a valid issue time for these introduced memory accesses in already scheduled code; resource or data dependence constraints may prohibit all possible issue slots inside the scheduled code. This fact forces an iterative process of scheduling followed by spilling until reaching a solution. Even if we can experimentally reduce the backtracking as in [START_REF] Zalamea | Modulo Scheduling with Integrated Register Spilling for Clustered VLIW Architectures[END_REF], this iterative aspect adds a high algorithmic complexity factor to a pass integrating both register allocation and scheduling. As far as we know, there is no formal solution that effectively solves this problem.

The above arguments suggest that we consider new ways of handling register pressure before starting the scheduling process. The scheduler should be freed from register constraints so that the schedule does not suffer from excessive serialization. This article synthesizes our contributions from [START_REF] Touati | Register Saturation in Superscalar and VLIW Codes[END_REF][START_REF] Touati | Register Pressure in Instruction Level Parallelisme[END_REF]. We study the concept of register saturation (RS), which prevents a DAG from producing an excessive number of simultaneously live values for all the valid schedules. Our pre-pass analyzes a DAG (with respect to control flow) to deduce the maximum register need among all schedules. We call this limit the register saturation (RS), because the register need can reach this limit but never exceed it. If RS exceeds the number of available registers, we introduce new edges in the DAG to reduce RS, as illustrated in Figure 1. In this paper, we give some theoretical results on RS and provide exact (optimal) and approximate methods for the problems of computing and reducing RS. After our RS analysis pass, the DAG is free from register constraints and can be sent to the scheduler and the register allocator. This article is organized as follows. Section 2 presents our DAG and processor model which can be used for most of existing ILP architectures (superscalar, VLIW, EPIC/IA64). Section 3 provides some theoretical results on computing the RS that prove the NP-completeness of this problem. Section 4 presents an algorithmic heuristics for computing RS. Computing the optimal RS by integer linear programming (intLP) is given in Section 5. Our intLP formulation use the linear writing of logical formulas (=⇒, ⇐⇒, ∨) and the max operator (max(x, y)) by introducing extra binary variables. If the RS exceeds the number of available registers, RS must be reduced. Section 6 proves that this problem is NP-hard. An algorithmic heuristics for reducing RS is given in Section 7 and an exact optimal solution is presented in Section 8. Section 9 presents our large range of experiments, which show that our heuristics are nearly optimal in practice. Before concluding, in Section 10 we discuss why the RS concept is a better way to handle register constraints prior to ILP scheduling compared to register minimization. To enhance readability, only the most important formal proofs are presented in this paper. The complete theoretical proofs are provided in the cited references.

DAG and Processor Model

A DAG G = (V, E, δ) in our study represents the data dependences between the operations and any other serial constraints. Each operation u has a strictly positive latency lat(u). The DAG is defined by its set of nodes (operations) V , its set of edges (data dependences and serial constraints) E = {(u, v)| u, v ∈ V }, and δ such that δ(e) is the latency of the edge e in terms of processor clock cycles. We assume that the initial DAG contains only edges with positive latencies. This assumption is useful for some formal proofs. However, we will see in later sections (when reducing RS) that we can insert new edges with non-positive latencies.

A schedule σ of G is a function which gives an integer execution (issue) time for each operation:

σ is valid ⇐⇒ ∀e = (u, v) ∈ E, σ(v) -σ(u) ≥ δ(e)
The set of all valid acyclic schedules of G is denoted by Σ(G).

To simplify the writing of some mathematical formulas, we assume that the DAG has one source (⊤) and one sink (⊥). If not, we introduce two fictitious nodes (⊤, ⊥) representing nops (evicted at the end of the RS analysis). We add a virtual serial edge e 1 = (⊤, s) to each source with δ(e 1 ) = 0, and an edge e 2 = (t, ⊥) from each sink with the latency of the sink operation δ(e 2 ) = lat(t). The total schedule time of a schedule is then σ(⊥). The null latency of an added edge e 1 is not inconsistent with our assumption that latencies must be strictly positive because the added virtual serial edges do not exist in the original DAG. Furthermore, we can avoid introducing these virtual nodes without any impact on our theoretical study, since their purpose is only to simplify some mathematical expressions.

We consider a target RISC-style architecture with multiple register types, where T denotes the set of register types (for instance, T = {int, f loat}). We differentiate between statements and precedence constraints, based on whether they refer to values to be stored in registers or not.

• V R,t ⊆ V is the set of statements (operations) which define values to be stored in registers of type t ∈ T . We simply call such statements values. We assume that each statement u ∈ V R,t writes into at most one register of a type t ∈ T . Statements which define multiple values with different types are accepted in our model if they do not define more than one value of a single type. We denote by u t the value of type t defined by the operation u.

• E R,t ⊆ E is the set of data flow dependence edges through a value of type t ∈ T . We call them flow edges.

• All the edges in E -E R,t , i.e. edges which are not data flow dependences, are called serial edges.

Basically, there are three types of ILP codes : superscalar, VLIW and EPIC. Superscalar codes can be simply considered as linear sequential programs. Even if the compiler try to generate efficient superscalar codes, the processor is the unique responsible for dynamically extracting ILP at execution time. So, code generation for such ILP codes write sequential ones, as if they would be executed by a sequential processor. However, VLIW codes contain information about parallel operations. The compiler has the task of statically extracting ILP and then generating the code by compacting the parallel operations into Very Long Instructions Words. The processor executes such instructions (containing many independent operations) sequentially. So, the compiler has the complete control of the dynamic execution of VLIW codes (except dynamic events, such as cache misses, exceptions, etc.). EPIC codes have a semantics that may be considered as a mixture between VLIW and superscalar: while the compiler include information about ILP in the code, the processor can use such ILP information at execution time, or can simply execute sequentially the program. From the compiler point of view, an EPIC processor can be viewed as a sequential (superscalar) or as VLIW processor.

(a) fload [i1], f Ra (b) fload [i2], f R b (c) fload [i3], f Rc (d) fmult f Ra, f R b , f R d (g) ftoint f Rc, iRg (i) iadd iRg , 4, iRi (h) fdiv f R d , iRe, f R h (e) imultadd f Ra, f R b , f Rc, iRe (j) g f ? fadd setbnz f Rj , 1 , f Rj , gj (k) g f |gj ? fsub f R k , 1 , f R k (f) fmultadd setz f R b , iRi, f Rc, f R f ,g f (c) P K(G) (b) the DDG G

Figure 2. DAG Model

To accommodate static issue VLIW and EPIC/IA64 processors in which the hardware pipeline steps are visible to compilers (we allow for dynamically scheduled superscalar processors as well), we assume that reading from and writing into a register may be delayed from the beginning of the schedule time, and these delays are visible to the compiler (architecturally visible). We define two delay (offset) functions δ r,t and δ w,t in which: the read cycle of u t from a register of type t is σ(u) + δ r,t (u), and the write cycle of u t into a register of type t is σ(u) + δ w,t (u). By definition, we have δ r,t (u) ≤ δ w,t (u) < lat(u). For instance, according to superscalar and EPIC/IA64 code semantics, δ r,t and δ w,t are equal to zero. This is because, according to the semantics provided by the vendors, such codes can be considered as sequential (linear). Any register written by operation u at time slot c in the code, that register is assumed as busy at the program point c (no delay is architecturally visible). The same remark holds when reading from registers. Figure 2.b gives the DAG that we use in this paper constructed from the code of part (a). In this example, we focus on the floating point registers: the values and flow edges are illustrated by bold lines. We assume for instance that each read occurs exactly at the schedule time and each write at the final execution step (δ r (u) = 0, δ w (u) = lat(u) -1). The nodes with non-bold lines are any other operations that do not write into registers (as stores), or write into registers of unconsidered types. The edges with non-bold lines represent the precedence constraints that are not flow dependences through registers, such as data dependences through memory, or through registers of unconsidered types, or any other serial constraints.

Notation and Definitions on DAGs

In this paper, we use the following notations for a given DAG G = (V, E) (as those usually used in lattices and orders algebra):

• Γ + G (u) = {v ∈ V |(u, v) ∈ E} successors of u in the graph G; • Γ - G (u) = {v ∈ V |(v, u) ∈ E} predecessors of u in the graph G; • ∀e = (u, v) ∈ E source(e) = u ∧ target(e) = v. u, v are called endpoints; • ∀u, v ∈ V : u < v ⇐⇒ ∃ a path (u, . . . , v) in G; • ∀u, v ∈ V : u||v ⇐⇒ ¬(u < v) ∧ ¬(v < u)
. u and v are said to be parallel;

• ∀u ∈ V ↑ u = {v ∈ V |v = u ∨ v < u} u's ascendants including u.
In other terms, a node u is an ascendant of a node v iff u = v or if there exists a path from u to v;

• ∀u ∈ V ↓ u = {v ∈ V |v = u ∨ u < v} u's descendants including u.
In other terms, a node u is a descendant of a node v iff u = v or if there exists a path from v to u;

• two edges e, e ′ are adjacent iff they share an endpoint;

• A ⊆ V is an antichain iff all nodes belonging to A are parallel. Formally, A ⊆ V is an antichain in G iff ∀u, v ∈ A, u||v;

• AM is a maximal antichain iff its size in terms of number of nodes is maximal. Formally, AM is a maximal antichain ∀A antichain in G, |A| ≤ |AM |;

• the extended DAG G\ E ′ of G generated by the edges set E ′ ⊆ V 2 is the DAG obtained from G after adding the edges in E ′ . As a consequence, any valid schedule of G ′ is necessarily a valid schedule for G:

G ′ = G\ E ′ =⇒ Σ(G ′ ) ⊆ Σ(G)
• an extended graph has a similar definition as above, but it is not restricted to be a DAG;

• let I 1 = [a 1 , b 1 ] ⊂ N and I 2 = [a 2 , b 2 ]
⊂ N be two integer intervals. We say that I 1 is before I 2 , noted by

I 1 ≺ I 2 , iff b 1 < a 2 . We say that I 1 finishes I 2 iff b 1 = b 2 .

Some Theoretical Results on Computing Register Saturation

In this section, we study some formal properties of register saturation in order to help us compute it algorithmically. For clarity and without loss of generality, let us focus on a single register type. Accordingly, our notation becomes V R for the set of values of the implicit type we consider, E R for the set of flow edges through a register of that type, and δ r and δ w for reading/writing delays. Also, we use the notation u for both the operation u and the value it produces.

Register Need of a Schedule

Given a DAG G = (V, E, δ), a value u ∈ V R is alive from the point just after the writing clock cycle of u until the point of its last use (consumption). Values which are not read in G or are still alive when exiting the DAG are assumed to be kept in registers as exit values. We model these exit values by considering that the bottom node ⊥ consumes them. We define the set of consumers for each value u ∈ V R as:

Cons(u) = {v ∈ V |(u, v) ∈ E R } if ∃(u, v) ∈ E R ⊥ otherwise
Given a schedule σ ∈ Σ(G), the last consumption of a value is called the killing date and noted :

∀u ∈ V R , kill σ (u) = max v∈Cons(u) σ(v) + δ r (v)
All the consumers of u whose reading time is equal to the killing date of u are called the killers of u1 . We assume that a value written at instant i in a register is available one step later. That is to say, if operation u reads from a register at instant i while operation v is writing in the same register at the same time, u does not get v's result but, gets the value previously stored in the register. Then, the lifetime interval LT σ (u) of a value u according to σ is ]σ(u) + δ w (u), kill σ (u)]. This interval is left-open by convention only and can be changed without any consequence on our mathematical study.

Given the lifetime intervals of all the values, the register need of σ is the maximum number of values simultaneously alive:

RN σ (G) = max 0≤i≤σ(⊥) |vsa σ (i)| where vsa σ (i) = {u ∈ V R |i ∈ LT σ (u)}

Register Saturation Problem

The RS is the maximal register need for all the valid schedules of the DAG:

RS(G) = max σ∈Σ(G) RN σ (G)
We call σ a saturating schedule iff RN σ (G) = RS(G). In this section, we study how to compute RS(G). We will see that this problem comes down to answering the question "which operation must kill this value ?" When looking for saturating schedules, we do not worry about the total schedule time. Our aim is only to prove that the register need can reach the RS but cannot exceed it. Minimizing the total schedule time is considered in Section 6 when we reduce the RS. Furthermore, we will prove that, for the purpose of maximizing the register need, looking for only one suitable killer of a value is sufficient rather than looking for a group of killers: for any schedule that assigns more than one killer for a value u, we can build another schedule with at least the same register need such that this value u is killed by only one consumer. Therefore, the purpose of this section is to select a suitable killer for each value in order to saturate the register requirement.

Since we do not assume any schedule, the lifetime intervals are not defined yet, so we cannot know at which date a value is killed. However, we can deduce which consumers in Cons(u) are impossible killers for the value u. If v 1 , v 2 ∈ Cons(u) and ∃ a path (v 1 • • • v 2 ), v 1 is always scheduled before v 2 by at least lat(v 1 ) processor cycles. Then v 1 can never be the last reader of u (remember our assumption of positive latencies in the initial DAG). We can consequently deduce which consumers can "potentially" kill a value (possible killers). We denote by pkill G (u) the set of operations which can kill a value. u ∈ V R :

pkill G (u) = v ∈ Cons(u)| ↓ v ∩ Cons(u) = {v}
A potential killing operation for a value u is simply a consumer of u that is neither a descendant nor an ascendant of another consumer of u. One can check that all operations in pkill G (u) are parallel in G. Any operation which does not belong to pkill G (u) can never kill the value u. The following lemma proves that for any value u and for any schedule σ, there exists a potential killer v that is a killer of u according to σ. Furthermore, for any potential killer v of a value u, there exists a schedule σ that makes v a killer of u. The proof of ( 1) is directly derived from the definition of pkill. Since

Lemma 1 Given a DAG G = (V, E, δ), then ∀u ∈ V R ∀σ ∈ Σ(G), ∃v ∈ pkill G (u) : σ(v) + δ r (v) = kill σ (u) (1) ∀v ∈ pkill G (u), ∃σ ∈ Σ(G) : kill σ (u) = σ(v) + δ r (v) (2)
v ∈ pkill(u) =⇒ ∄v ′ ∈ Cons(u) v < v ′
then the killing date of u must be the schedule date of some operations in pkill(u). Let us prove that

∀u ∈ V R , ∄v ′ ∈ Cons(u) -pkill(u), ∃σ ∈ Σ(G) : kill σ (u) = σ(v ′ ) + δ r (v ′ )
Suppose the converse is true.

∃v ′ ∈ Cons(u) -pkill(u) =⇒ ∃v ∈ pkill(u)|v ′ < v Let lp(v ′ , v) be the longest path from v ′ to v. since lp(v ′ , v) ≥ lat(v ′ ) > δ r (v ′ ) =⇒ σ(v) -σ(v ′ ) > δ r (v ′ ) Since δ r (v) ≥ 0: σ(v) + δ r (v) -σ(v ′ ) > δ r (v ′ ) =⇒ σ(v) + δ r (v) > σ(v ′ ) + δ r (v ′ ) Then kill σ (u) ≥ σ(v) + δ r (v) > σ(v ′ ) + δ r (v ′ )
In order to prove (2) we create an extended DAG G u v = G\ E ′ , for each v ∈ pkill(u), to enforce v to be the last read of the value u. ∀v ′ ∈ pkill(u) -{v}, we add a serial edge e from v ′ to v with latency δ(e

) = δ r (v ′ ) -δ r (v). Then, any schedule σ ∈ Σ(G u v ) ensures σ(v) + δ r (v) ≥ σ(v ′ ) + δ r (v ′ ) which means kill σ (u) = σ(v). Let's prove that G u v is still a DAG. Suppose the converse is true, i.e., ∃u ∈ V R , ∃v ∈ pkill(u) such that G u v is cyclic. Let C = (v, • • • , v ′ , v) be this cycle where the introduced edge is (v ′ , v).
We know that all the potential killing operations pkill(u) of a value u are parallel in G. However, before introducing this edge, a path

P = v ; v ′ means that v < v ′ in G which is a contradiction.
Figure 4 shows the two extended DAGs associated with e. The original DAG is presented in Figure 4. Here, we assume that all read delay are null. e has two potential killing operations {h, i}, so we have two extended DAG: G e i ensures that i kills e, and G e h that ensures that h kills e.

A potential killing DAG of G, noted P K(G) = (V, E P K ), is built to model the potential killing relations between the operations, (see Figure 2.c), where:

E P K = {(u, v)| u ∈ V R ∧ v ∈ pkill G (u)}
There may be more than one operation candidate for killing a value. Next, we prove that looking for a unique suitable killer for each value is sufficient for maximizing the register need: the next theorem proves that for any schedule that assigns more than one killer for a value, we can build another schedule with at least the same register need such that this value is killed by only one consumer. Consequently, our formal study will look for a unique killer for each value instead of looking for a group of killers.

Theorem 1 Let G = (V, E, δ) be a DAG and a schedule σ ∈ Σ(G). If there is at least one excessive value that has more than one killer according to σ, then there exists another schedule σ ′ ∈ Σ(G) such that:

RN σ ′ (G) ≥ RN σ (G)
and each excessive value is killed by a unique killer according to σ ′ .

Proof :

We suppose that there exists a schedule σ ∈ Σ(G) with at least one excessive value that has more than one killer:

∃σ ∈ Σ(G), ∃u ∈ EV σ (G) : |killers σ (u)| > 1
where EV σ (G) is a set of excessive values assuming σ as a schedule for G. We show in this proof how to build a new schedule σ ′ ∈ Σ(G) such that u is killed by a unique killer and σ ′ needs at least as many registers as σ does.

Suppose that u has j killers according to σ, and we note them:

killers σ (u) = {k 1 , ..., k j } with kill σ (u) = σ(k 1 ) + δ r (k 1 ) = • • • = σ(k j ) + δ r (k j ).
We choose one killer within this set to be the only one killer of u according to σ ′ , say k 1 . We build σ ′ by "shifting" down k 1 and all its descendants with a strictly positive factor, say 1:

∀v ∈ V σ ′ (v) = σ(v) + 1 if v ∈↓ k 1 σ(v) otherwise
Now, we prove that σ ′ is valid and needs at least as many registers as σ does, and that k 1 is the only killer of u according to σ ′ .

σ ′ is valid: we can easily check that any dependence ∀e

= (v 1 , v 2 ) ∈ E is satisfied by σ ′ : 1. if both v 1 , v 2 ∈↓ k 1 , then σ ′ (v 2 ) -σ ′ (v 1 ) = σ(v 2 ) -σ(v 1 ) ≥ δ(e)
2. in the case where

v 1 ∈↓ k 1 ∧ v 2 ∈↓ k 1 σ ′ (v 2 ) -σ ′ (v 1 ) = σ(v 2 ) + 1 -σ(v 1 ) > δ(e) 3. the case of v 1 ∈↓ k 1 ∧ v 2 ∈↓ k 1 is impossible because the edge e = (v 1 , v 2 ) exists; 4. in the case where both v 1 , v 2 ∈↓ k 1 , then σ ′ (v 2 ) -σ ′ (v 1 ) = σ(v 2 ) + 1 -σ(v 1 ) -1 ≥ δ(e)
RN σ ′ ≥ RN σ : let t be an excessive clock cycle according to σ, i.e, a clock cycle t where the excessive values are simultaneously alive during it:

∀v ∈ EV σ (G) : t ∈ LT σ (v) =⇒ ∀v ∈ EV σ (G) : σ(v) + δ w (v) < t ≤ kill σ (v)
Here, we want to prove that these excessive values according to σ are still alive during t according to σ ′ . Any value v ∈ EV σ (G) has the same definition date in σ ′ as in σ, this is because only ↓ k 1 nodes have been shifted down and :

∀v ∈ EV σ (G) -{u} : v ∈↓ k 1 otherwise LT σ (u) ≺ LT σ (v) which is in contradiction with u, v ∈ EV σ (G). Then ∀v ∈ EV σ (G) : σ ′ (v) = σ(v)
However, the killing date of any excessive value v ∈ EV σ (G) could be increased by the translation factor 1:

∀v ∈ EV σ (G) : kill σ (v) ≤ kill σ ′ (v) which gives ∀v ∈ EV σ (G) : σ ′ (v) < t ≤ kill σ ′ (v) =⇒ RN σ ′ ≥ |EV σ (G)| = RN σ (G) k 1 is the unique killer of u: since k 1 ∈ pkill G (u), there is no other potential killer k ∈ pkill(u) ∧ k = k 1 such as k ∈↓ k 1 . Otherwise, k 1 cannot kill u (pkill operations property). In this case σ ′ (k) = σ(k) while σ ′ (k 1 ) = σ(k) + 1. We conclude ∀k ∈ pkill G (u) -{k 1 } σ ′ (k 1 ) + δ r (k 1 ) > σ ′ (k) + δ r (k) =⇒ killers σ ′ (u) = {k 1 }
Finally, generalizing to an arbitrary number of excessive values like u (those that have more than one killer and that are simultaneously alive with u) is obviously done by iteratively building new σ ′ schedule for each of these values. However, we must take a precaution. Indeed, if we treat an excessive value u 1 by shifting down one of its killers, and then we proceed to another excessive value u 2 , we cannot guarantee that shifting down u 2 's killer would not shift down other u 1 consumers (and hence, u 1 becomes killed by multiple consumers). To break this recursivity, we proceed as follows. When we treat an excessive value u by shifting down its killer k(v), we add an edge to the DAG from each potential killer of u (except k(u)) to k(u). Hence, when we iterate over the remaining excessive values, any shifting down action would always guarantee the existence of a unique killer for the previously treated values. The added edges does not introduce a cycle since they define a strict order between the potential killing nodes.

Corollary 1 Given a DDG G = (V, E, δ), there is always a saturating schedule for G with the property that each saturating value has a unique killer.

Proof :

Direct consequence of Theorem 1. Let us begin by assuming a killing function, k, which guarantees that an operation v ∈ pkill G (u) is the killer of u ∈ V R . If we assume that k(u) is the unique killer of u ∈ V R , we must always verify the following assertion:

∀v ∈ pkill G (u) -{k(u)} : σ(v) + δ r (v) < σ k(u) + δ r k(u) (3)
There is a family of schedules that ensures this assertion. In order to define them, we extend G by new serial edges that force all the potential killing operations of each value u to be scheduled before k(u). This leads us to define an extended DAG associated with k and denoted G →k = G\ E k where:

E k = e = (v, k(u))|u ∈ V R v ∈ pkill G (u) -{k(u)} with δ(e) = δ r (v) -δ r k(u) + 1
Then, any schedule σ ∈ Σ(G →k ) ensures Property 3. The necessary existence of such a schedule defines the condition for a valid killing function:

k is a valid killing function ⇐⇒ G →k is acyclic According to our definition, invalid killing functions may exist. Figure 6 is an example, where Part (a) illustrates an arbitrary DAG with a killing function (the source of each bold edge is killed by its sink). Part (b) shows that the extended graph associated with the killing function is cyclic. According to our definition, the killing function defined in Part (a) isn't valid.

Provided a valid killing function k, we can deduce the values which can never be simultaneously alive for any σ ∈ Σ(G →k ). Let ↓ R (u) =↓ u ∩ V R be the set of the descendant operations of u ∈ V that are values. We call them descendant values.

Lemma 2 Given a DAG G = (V, E, δ) and a valid killing function k, then:

1. the descendant values of k(u) cannot be simultaneously alive with u:

∀u ∈ V R , ∀σ ∈ Σ(G →k ), ∀v ∈↓ R k(u) : LT σ (u) ≺ LT σ (v) (4)

there exists a valid schedule which makes any values non-descendant of k(u) simultaneously alive with

u, i.e. ∀u ∈ V R , ∃σ ∈ Σ(G →k ): ∀v ∈   v ′ ∈pkillG (u) ↓ R v ′   -↓ R k(u) : LT σ (u) ∩ LT σ (v) = φ (5)
Proof :

A complete proof is given in [START_REF] Touati | Register Pressure in Instruction Level Parallelisme[END_REF], Appendix A, Section A.1.4, page 253.

We define a DAG which models the values that can never be simultaneously alive when assuming k as a killing function. The disjoint value DAG of G associated with k, and denoted DV k (G) = (V R , E DV ) is defined by:

E DV = (u, v)|u, v ∈ V R ∧ v ∈↓ R k(u)
Any edge (u, v) in DV k (G) means that u's lifetime interval is always before v's lifetime interval according to any schedule of G →k , see Figure 5.c (this DAG is simplified by transitive reduction). This definition permits us to state Theorem 2 as follows.

Theorem 2 Given a DAG G = (V, E, δ) and a valid killing function k, let AM k be a maximal antichain in the disjoint value DAG DV k (G). Then:

• the register need of any schedule of G →k is always less than or equal to the size of a maximal antichain in DV k (G).

Formally,

∀σ ∈ Σ(G →k ), RN σ (G) ≤ |AM k |
• there is always a schedule which makes all the values in this maximal antichain simultaneously alive. Formally,

∃σ ∈ Σ(G →k ), RN σ (G) = |AM k | Proof :
First property Let us begin by proving that:

∀σ ∈ Σ(G →k ) : RN σ (G) ≤ |AM k | DV k (G)
, the disjoint value DAG, models the order between value lifetime in any schedule of G →k . The definition of the disjoint value DAG states that

∀σ ∈ Σ(G →k ), ∀u, v ∈ V R : u < v in DV k (G) ⇐⇒ u < k(u) ≤ v in G →k If v = k(u), then σ(u) + δ w (u) < σ(v) + δ r (v), because of true data dependence. By hypothesis on DAG model we have δ r (v) ≤ δ w (v), then σ(u) + δ w (u) < σ(v) + δ w (v).
In the case where v = k(u), any path from k(u) to v is a data dependence path with strictly positive integer latencies. We deduce that:

∀σ ∈ Σ(G →k ) σ k(u) + δ r k(u) ≤ σ(v) + δ w (v)
That is,

kill σ (u) ≤ σ(v) + δ w (v)
We deduce that the following assertion is correct:

∀σ ∈ Σ(G →k ) u ∼ v in DV k (G) =⇒ LT σ (u) ∩ LT σ (v) = φ We rewrite it: ∀σ ∈ Σ(G →k ) LT σ (u) ∩ LT σ (v) = φ =⇒ u||v in DV k (G) =⇒ {u, v} ∈ vsa σ (c) , c ∈ LT σ (u) ∩ LT σ (v)
Then, any values simultaneously alive for σ ∈ Σ(G →k ) belong to an antichain in DV k (G):

∀0 ≤ c < σ, ∃A an antichain of DV k (G) vsa σ (c) ⊆ A Since RN σ (G →k ) = max 0≤c≤σ |vsa σ (c)| and |vsa σ (c)| ≤ |AM k |, we conclude that RN σ (G) = max 0≤c≤σ |vsa σ (c)| ≤ |AM k |.
Second Property Now, given a set of excessive values AM k , we must prove that:

∃σ ∈ Σ(G →k ) : RN σ (G) = |AM k |
We have to build a schedule σ such that RN σ (G) = |AM k |. For this purpose, we consider G →k in order to ensure the killing relation, and we add some serial edges to enforce the values in AM k in order to be simultaneously alive. This leads us to a new extended DAG

G ′ = G →k \ E ′ and ∀σ ∈ Σ(G ′ ) ∀u, v ∈ AM k : LT σ (u) ∩ LT σ (v) = φ
A sufficient condition that two values u, v in AM k must satisfy to be simultaneously alive for any schedule of

G →k is v < u < k(v) ∧ lp(v, u) ≥ δ w (v) -δ w (u) ∧ ∧ lp u, k(v) > δ w (u) -δ r k(v) (6)
∨ u < v < k(u) ∧ lp(u, v) ≥ δ w (u) -δ w (v) ∧ ∧ lp v, k(u) > δ w (v) -δ r k(u) (7)
∨ k(u) = k(v) (8)
with lp(u, v) for u, v ∈ V denoting the longest path from u to v.

These conditions ensure that ∀σ ∈ Σ(G →k ) ∀u, v ∈ V R : u, v satisfy (6) =⇒ σ(u) + δ w (u) ≥ σ(v) + δ w (v) ∧ σ(k(v)) + δ r (k(v)) > σ(u) + δ w (u) u, v satisfy (7) =⇒ σ(v) + δ w (v) ≥ σ(u) + δ w (u) ∧ σ(k(u)) + δ r (k(u)) > σ(v) + δ w (v) u, v satisfy (8) =⇒ kill σ (u) = kill σ (v)
Then, by using usual interval order algebra notations:

u, v satisfy Cond. (6) =⇒ ¬(LT σ (u) ≺ LT σ (v) ∨ LT σ (u) ≻ LT σ (v)) u, v satisfy Cond. (7) =⇒ ¬(LT σ (u) ≻ LT σ (v) ∨ LT σ (u) ≺ LT σ (v)) u, v satisfy Cond. (8) =⇒ LT σ (u) finishes LT σ (v)
If two values in u, v ∈ AM k do not satisfy any of these conditions, then we use Algorithm 1 to enforce them. This algorithm uses the boolean function vsa G ′ (u, v) to check if two values u, v satisfy one of the above conditions. We add iteratively serial edges until all values in AM k satisfy one of these conditions. The added serial edges do not introduce a cycle and any schedule σ of

G ′ has RN σ (G ′ ) = |AM k |.
(G) for all u ∈ AM k do for all v ∈ AM k | u = v do if ¬vsa G ′ (u, v) then if u||v in G ′ then if ¬(k(u) < v) then add the serial edges e = (u, v), e ′ = (v, k(u)) to G ′ with δ(e) = δ w (u) -δ w (v) and δ(e ′ ) = δ w (v) - δ r k(u) + 1 else {¬(k(v) < u) certainly} add the serial edges e = (v, u), e ′ = (u, k(v)) to G ′ with δ(e) = δ w (v) -δ w (u) and δ(e ′ ) = δ w (u) - δ r k(v) + 1 end if else if v < u then add the serial edges e = (v, u) and e ′ = (u, k(v)) to G ′ with δ(e) = δ w (v) -δ w (u) and δ(e ′ ) = δ w (u) - δ r k(v) + 1 else {u < v} add the serial edges e = (u, v) and e ′ = (v, k(u)) to G ′ with δ(e) = δ w (u) -δ w (v) and δ(e ′ ) = δ w (v) - δ r k(u) + 1;

end if end if end if end for end for

Lemma 3 Let G = (V, E, δ) be a DAG. Let k be a killing function and AM k be a maximal antichain in the disjoint value DAG DV k (G). The extended graph G ′ = G →k \ E ′ produced by Algorithm 1 has the two following properties:

1. it a DAG;

for any schedule σ of G ′ , the lifetime intervals of any two values belonging to the maximal antichain

AM k interfere. Formally, ∀u, v ∈ AM k , ∀σ ∈ Σ(G ′ ) : LT σ (u) ∩ LT σ (v) = φ Proof :
We proceed by induction. We prove that after exiting Algorithm 1, G ′ is still a DAG. We also prove that the algorithm makes all values in AM k satisfying one of the conditions ( 6), [START_REF] Berson | URSA: A Unified ReSource Allocator for Registers and Functional Units in VLIW Architectures[END_REF] or [START_REF] Brasier | CRAIG: A Practical Framework for Combining Instruction Scheduling and Register Assignment[END_REF]. For this last condition, if two values do not satisfy it in the DAG G →k , they cannot satisfy it in G ′ : this is because the killing operations [START_REF] Berson | Unification of Register Allocation and Instruction Scheduling in Compilers for Fine-Grain Parallel Architecture[END_REF] or Condition [START_REF] Berson | URSA: A Unified ReSource Allocator for Registers and Functional Units in VLIW Architectures[END_REF].

We prove also the following property

∀u, v ∈ AM k ¬ k(v) < u ∨ k(u) < v in G ′
which is the same as proving that Algorithm 1 guarantees that all values in AM k are forced to be simultaneously alive in

G ′ : ∄u, v ∈ AM k |u ∼ v in DV k (G ′ ) Initially, this is correct because u, v ∈ AM k =⇒ u ∈↓ R k(v) ∧ v ∈↓ R k(u).
In this proof, we note G ′ i the graph built after exiting iteration i. Suppose that after exiting iteration i -1,

G ′ i-1 is still a DAG and ∀u, v ∈ AM k ¬ k(v) < u ∨ k(u) < v in G ′ i-1
Let u i and v i be the two chosen values at iteration i which do not satisfy any of the conditions. Let us prove now that G ′ i is still a DAG and the two chosen values u i , v i ∈ AM k satisfy one of the conditions after exiting iteration i. Furthermore, we prove that after exiting this iteration

∄w ∈ AM k |k(u i ) < w ∨ k(v i ) < w in G ′ i
Our algorithm introduces serial edges in four cases:

1. u i ||v i in G ′ i-1 , then • if ¬(k(u i ) < v i ), the two introduced edges e = (u i , v i ), e ′ = (v i , k(u i )) cannot introduce a cycle, because u i < k(u i ) in G ′ i-1
, see Figure 7.a. Now they are satisfying Cond. [START_REF] Berson | URSA: A Unified ReSource Allocator for Registers and Functional Units in VLIW Architectures[END_REF]. Also, after introducing these edges, the following property is satisfied:

∄w ∈ AM k |k(u i ) < w ∨ k(v i ) < w in G ′ i Suppose the converse is true, i.e., ∃w ∈ AM k |k(u i ) < w ∨ k(v i ) < w in G ′ i If k(u i ) < w in G ′ i , =⇒ k(u i ) < w in G ′ i-1 because we have not introduced a serial edge from k(u i ), which is impossible because of induction hypothesis. If k(v i ) < w in G ′ i , =⇒ k(v i ) < w in G ′
i-1 because we have not introduced a serial edge from k(v i ), which is also impossible because of induction hypothesis;

• else ¬(k(v i ) < u i ) certainly, because otherwise v i < k(v i ) < u i ∧ u i < k(u i ) < v i =⇒ u i < v i ∧ v i < u i in G ′ i-1 (impossible) Then the introduced edges e = (v i , u i ), e ′ = (u i , k(v i )) cannot introduce any cycle because v i < k(v i ) in G ′ i-1
, see Figure 7.b. Now they are satisfying Cond. [START_REF] Berson | Unification of Register Allocation and Instruction Scheduling in Compilers for Fine-Grain Parallel Architecture[END_REF]. Also, after introducing these edges, the following property is satisfied:

∄w ∈ AM k |k(u i ) < w ∨ k(v i ) < w in G ′ i
The proof is similar to the above case;

2. if v i < u i in G ′ i-1 , then by induction hypothesis ¬(k(v i ) < u i ) in G ′ i-1 .
The two introduced edges e = (v i , u i ) and e ′ = (u i , k(v i )) cannot cause any cycle. Now they are satisfying Cond. [START_REF] Berson | Unification of Register Allocation and Instruction Scheduling in Compilers for Fine-Grain Parallel Architecture[END_REF]. Also, after introducing these edges,

∄w ∈ AM k |k(u i ) < w ∨ k(v i ) < w in G ′ i
The proof is similar to the case above;

3.

u i < v i in G ′ i-1
, this case is similar to above. Now they are satisfying Cond. [START_REF] Berson | URSA: A Unified ReSource Allocator for Registers and Functional Units in VLIW Architectures[END_REF].

After n = |AM k | 2 iterations, we conclude that :

∀u, v ∈ AM k u, v satisfy one of the conditions ( 6), ( 7) or ( 8)

and then ∀u, v ∈ AM k ∀σ ∈ Σ(G ′ ) LT σ (u) ∩ LT σ (v) = φ
Theorem 2 allows us to rewrite the RS formula as

RS(G) = max k a valid killing function |AM k |
where AM k is a maximal antichain in DV k (G). We refer to the problem of finding such a killing function as the maximizing maximal antichain problem (MMA). We call each solution for the MMA problem a saturating killing function, and AM k its saturating values. A saturating killing function means a killing function that produces a saturated register need. The saturating values are the values that are simultaneously alive, and their number reaches the maximal possible register need. Unfortunately, Theorem 3 Given a DAG G = (V, E, δ), computing a saturating killing function is NP-complete.

Proof :

A complete proof is given in [START_REF] Touati | Register Pressure in Instruction Level Parallelisme[END_REF], Appendix A, Section A.1.5, page 253.

Corollary 2 Given a DAG G = (V, E, δ), computing the register saturation is NP-complete.

Proof :

A complete proof is given in [START_REF] Touati | Register Pressure in Instruction Level Parallelisme[END_REF], Appendix A, Section A.1.6, page 257.

A Heuristics for Computing the RS

This section presents our heuristics to approximate an optimal k by another valid killing function k * . An optimal k is simply a killing function that defines the optimal register saturation. We have to choose a killing operation for each value such that we maximize the parallel values in DV k (G). Our heuristics compute a valid killing function by focusing on the potential killing DAG P K(G), starting from source nodes to sinks. Our aim is to select a group of killing operations for a group of parents that keeps as many descendant values alive as possible. The main steps of our heuristics are:

1. decompose the potential killing DAG P K(G) into connected bipartite components; 2. for each bipartite component, search for the best saturating killing set (defined below); 3. choose a killing operation within the saturating killing set (defined below).

We decompose the potential killing DAG into connected bipartite components (CBC) in order to choose a common saturating killing set for a group of parents. Our purpose is to have a maximum number of children and their descendant's values simultaneously alive with their parent's values. A CBC cb = (S cb , T cb , E cb ) is a partition of a subset of operations into two disjoint sets where:

• E cb ⊆ E P K is a subset of the potential killing relations;

• S cb ⊆ V R is the set of the parent values, such that each parent is killed by at least one operation in T cb ;

• T cb ⊂ V is the set of the children, such that any operation in T cb can potentially kill at least one value in S cb .

A bipartite decomposition of the potential killing graph P K(G) is the set (see Figure 5.d)

B(G) = {cb = (S cb , T cb , E cb )| ∀e ∈ E P K ∃cb ∈ B(G) : e ∈ E cb }
Note that the parents, as well as the children, are parallel inside the potential killing DAGP K(G). Formally,

∀cb ∈ B(G) ∀s, s ′ ∈ S cb ∀t, t ′ ∈ T cb : s||s ′ ∧ t||t ′ in P K(G) A saturating killing set SKS(cb) of a bipartite component cb = (S cb , T cb , E cb ) is a subset of children T ′ cb ⊆ T cb .
Such subset provides a unique killer for each value present in the set S cb of parents. Such unique killer is chosen so as to minimize the number of descendant values of all the killers in T cb . The dual consequence is to get a maximal number of values simultaneously alive with the parent values belonging to S cb . Definition 1 (Saturating Killing Set) Given a DAG G = (V, E, δ), a saturating killing set SKS(cb) of a connected bipartite component cb ∈ B(G) is a subset T ′ cb ⊆ T cb , such that:

1. killing constraints: each parent must be killed

t∈T ′ cb Γ - cb (t) = S cb

objective function: minimize the number of descendant values of T

′ cb min | t∈T ′ cb ↓ R t|
Unfortunately, computing a SKS is also NP-complete (the proof is the same as Theorem 3's proof).

A Heuristics for Finding a SKS Intuitively and according to Lemma 2, we should choose a subset of children in a bipartite component that would kill the greatest number of parents while minimizing the number of descendant values. We define a cost function ρ that enables us to choose the best candidate child. Given a bipartite component cb = (S cb , T cb , E cb ) and a set Y of (cumulated) descendant values and a set X of not (yet) killed parents, the cost of a child t ∈ T cb is :

ρ X,Y (t) =      |Γ - cb (t)∩X| |↓Rt∪Y | if ↓ R t ∪ Y = φ |Γ - cb (t) ∩ X| otherwise
The first case enables us to select the child which covers the greatest number of non-killed parents, with a corresponding minimum number of descendant values. If there are no descendant values, then we choose the child that covers the most non-killed parents. Since the approximated killing function k * is valid, Theorem 2 ensures that we can always find a valid schedule which requires exactly |AM k * | registers. Consequently, our heuristics do not compute an upper bound of the optimal register saturation, and the optimal RS can be greater than the one computed by Greedy-k. A conservative heuristic which computes a solution exceeding the optimal RS cannot ensure the existence of a valid schedule which reaches the computed limit, and hence it would imply an unnecessary RS reduction process and a waste of registers. The validity of the killing function is a key condition because it ensures the existence of a register allocation requiring exactly |AM k * | registers. As a summary, here are our steps to compute the RS:

1. apply Greedy-k on G. The result is a valid killing function k * ;

2. construct the disjoint value DAG DV k * (G);

3. find a maximal antichain AM k * of DV k * (G) using Dilworth decomposition [START_REF] Crawley | Algebraic Theory of Lattices[END_REF]. The approximated set of saturating values is the nodes belonging to AM k * . The approximated RS is equal to

RS * (G) = |AM k * | ≤ RS(G).

Exact Register Saturation Computation

First, if |V R,t |, the total number of values of type t, is less than or equal to R t , the number of available registers of type t, then we are sure that any schedule cannot require more than |V R,t | ≤ R t registers. Otherwise, we must compute the register saturation (RS).

Let RN σ t (G) denote the register need of register type t given a schedule σ ∈ Σ(G), which is equal to the maximal number of values of type t simultaneously alive. The RS of a register type t for a DAG G is the maximal register need of type t among all valid schedules of G:

RS t (G) = max σ∈Σ(G) RN σ t (G)
Below, we give the set of variables and constraints of an exact integer linear programming (intLP) formulation for computing the optimal RS t (G). Our intLP formulation expresses the logical operators (=⇒, ∨, ⇐⇒) and the max operator (max(x, y)) by introducing extra binary variables. However, expressing these additional operators requires that we bound the domain of the integer variables, as explained below.

Expressing Logical Operators by Integer Programming

In [START_REF] Garfinkel | Integer Programming[END_REF], the authors show how to model the disjunctive operator ∨. Consider the problem: maximize (or minimize) f (x) subject to : g(x) ≥ 0 ∨ h(x) ≥ 0 By introducing a binary variable α ∈ {0, 1}, this disjunction is equivalent to:

g(x) ≥ αg h(x) ≥ (1 -α)h
where g and h are two known non null finite lower bounds for g and h respectively. We deduce the linear constraints of any other logical operator:

1. g(x) ≥ 0 =⇒ h(x) ≥ 0 can be written g(x) < 0 ∨ h(x) ≥ 0 2. g(x) ≥ 0 ⇐⇒ h(x) ≥ 0 can be written g(x) ≥ 0 ∧ h(x) ≥ 0 ∨ h(x) < 0 ∧ g(x) < 0 Also, z = max(x, y) can be written x ≥ y =⇒ z = x y ≥ x =⇒ z = y .
Thanks to the use of binary variables for expressing logical operators, our intLP formulation of register constraints contains a polynomial number of variables and constraints, i.e, it depends only on the number of nodes and edges of the input DAG. Unfortunately, this is not the case of the existing techniques in the literature where the number of variables and constraints is pseudo-polynomial, since this number depends on the total schedule time. The following section presents our intLP formulation of RS computation.

Scheduling Variables

For all operations u ∈ V , we define the integer variable σ u ≥ 0 that identifies the schedule time for each operation. Note that these schedule variables do not represent the final schedule under resource constraints (that will be computed after our RS pass), they only represent intermediate variables for our intLP formulation. The first linear constraints are those that describe precedence relations (the constraints that ensure the existence of at least one valid schedule), so we write into the intLP system:

∀e = (u, v) ∈ E : σ v -σ u ≥ δ(e)
In order to bound the domain set of our variables, we define T a worst possible schedule time. We choose T sufficiently large, where for instance T = e∈E δ(e) is a suitable worst total schedule time (the extreme case of a sequential schedule, i.e, no ILP). Then, we write the following constraint:

σ ⊥ ≤ T
As a consequence, we deduce for any u ∈ V :

• σ u ≥ σ u = LongestP athT o(u) is the shortest schedule time;

• σ u ≤ σ u = T -LongestP athF rom(u) is the longest schedule time according to the worst total schedule time T .

Register Need Constraints

Interference Graph The lifetime interval of a value u t of type t is (given a schedule σ)

LT σ (u t ) =]σ u + δ w,t (u), max v∈Cons(u t ) σ v + δ r,t (v) ]
That is, we assume that a value written at instant c in a register is available one step later. Thus, if an operation u reads from a register r at instant c while another operation v is writing to the r at the same time, u does not get v's result, but rather gets the value previously stored in r. Note that these semantics are explicitly chosen and encoded in the definition of LT σ (u t ), and are not a limitation of the model. We define for each value u t the variable k u t ≥ 0 which computes its killing date (the last time that u t is read). Since our variable domains are bounded (assuming a finite T ), we know that k u t is bounded by the two following finite schedule times:

∀t ∈ T , ∀u t ∈ V R,t : k u t < k u t ≤ k u t
where

• k u t = σ u + δ w,t (u)
is the first possible definition date of u t ;

• k u t = max v∈Cons(u t ) σ v + δ r,t (v) is the latest possible killing date of u t .

We use the linear constraints of the max operator to compute k u t as explained in Section 5.1. We write into the intLP system:

∀u t ∈ V R,t : k u t = max v∈Cons(u t ) σ v + δ r,t (v)
Now, we can consider H t the undirected interference graph of G for the register type t. For any pair of distinct values u t , v t ∈ V R,t , we define a binary variable s t u,v ∈ {0, 1} such that it is set to 1 if the two lifetimes intervals of type t interfere: ∀t ∈ T , ∀ couple u t , v t ∈ V R,t :

s t u,v = 1 if LT σ (u t ) ∩ LT σ (v t ) = φ 0 otherwise
The number of variables s t u,v is the number of combinations of two values among |V R,t |, i.e., |V R,t | × (|V R,t | -1) /2. LT σ (u t ) ∩ LT σ (v t ) = φ means that one of the two lifetime intervals is "before" the other, i.e., LT σ (u t ) ≺ LT σ (v t ) ∨ LT σ (v t ) ≺ LT σ (u t ) , where ≺ denotes the "before" relation in interval algebra. Then, we have to express the following constraints:

s t u,v = 1 ⇐⇒ ¬ LT σ (u t ) ≺ LT σ (v t ) ∨ LT σ (v t ) ≺ LT σ (u t ) where LT σ (u t ) ≺ LT σ (v t ) iff k u t ≤ σ v + δ w,t (v). The negation of this constraint is k u t > σ v + δ w,t (v), i.e., k u t -σ v -δ w,t (v) -1 ≥ 0. Since s t u,v ∈ {0, 1}
, these variables are constrained as follows :

s t u,v ≥ 1 ⇐⇒ k u t -σ v -δ w,t (v) -1 ≥ 0 k v t -σ u -δ w,t (u) -1 ≥ 0
Given three logical expressions (P, Q, S), (P ⇐⇒ (Q ∧ S)) is equivalent to the expression (P ∧ Q ∧ S) ∨ (¬P ∧ ¬Q) ∨ (¬P ∧ ¬S). We write these two disjunctions with linear constraints by introducing binary variables [START_REF] Touati | Register Pressure in Instruction Level Parallelisme[END_REF]) and by computing the finite lower bounds of the linear functions.

Maximal Clique in the Interference Graph

The maximum number of values of type t simultaneously alive corresponds to a maximal clique in H t = (V R,t , E t ), where (u t , v t ) ∈ E t iff their lifetime intervals interfere (s t u,v = 1). For simplicity, rather than considering the interference graph itself, we prefer to consider its complementary graph H ′ t = (V R,t , E ′ t ) where (u t , v t ) ∈ E ′ t iff their lifetime intervals do not interfere (s t u,v = 0). Then, the maximum number of values of type t simultaneously alive corresponds to a maximal independent set in H ′ t .

To write the constraints that describe independent sets (IS), we define a binary variable x u t ∈ {0, 1} for each value x u t ∈ V R,t such that x u t = 1 if u t belongs to some IS of H ′ t . We express in the model the following linear constraints:

∀x u t , x v t ∈ V R,t : s t u,v = 0 =⇒ x u t + x v t ≤ 1
This equations means that if two nodes u and v are connected in H ′ , then one and only one of them may belong to a given IS.

Linear Objective Function and General Remarks

The register requirement of type t is a maximal IS in H ′ t , i.e., the maximal u t ∈VR,t x u t . Thus, the register saturation of type t is computed by: Maximize

u t ∈VR,t x u t
The total number of integer variables in the intLP formulation is bounded by O(|V | 2 ), and the total number of constraints is at most O(|E| + |V | 2 ). Note that our intLP formulation may be optimized by considering that:

• an edge e = (u, v) in the initial DAG is redundant for the scheduling constraints and can be safely ignored if lp(u, v) > δ(e) where lp(u, v) denotes the longest path from u to v (with the condition that this edge doesn't belong to this longest path);

• two values (u t , v t ) ∈ V R,t can never be simultaneously alive iff for all the possible schedules, one value is always defined after the killing date of the other. This is the case if any of the two following conditions is satisfied:

∀v ′ ∈ Cons(v t ) : lp(v ′ , u) ≥ δ r (v ′ ) -δ w (u) ∨ ∀u ′ ∈ Cons(u t ) : lp(u ′ , v) ≥ δ r (u ′ ) -δ w (v)
The next section explores the problem of reducing RS if it exceeds the number of available registers.

The Complexity of Register Saturation Reduction

In the case where the register saturation RS t (G) exceeds the number of available registers R t of the type t, then we must add extra serial edges into the DAG G to reduce RS t (G) below this limit. The added edges must save ILP as much as possible by taking care of the critical path. We note by E the set of extra edges that we add to G to build a new extended DAG, namely G = G\ E , such that RS t (G) ≤ R t . We want to first solve the formal problem stated below.

Definition 2 (ReduceRS Problem)

Let G = (V, E, δ) be a DAG. Let R t and P be two positive integers. Does there exist an extended DDG G = G\ E of G such that:

RS t (G) ≤ R t and
CriticalP ath(G) ≤ P

Note that an extended DDG may contain a cycle (as we will see later), while an extended DAG is restricted to stay a DAG.

Theorem 4

The ReduceRS problem is NP-hard.

Proof :

We prove that ReduceRS problem reduces from the problem of scheduling under register constraints (SRC). Let us start by defining the latter problem. For the sake of clarity, we assume that the considered register type t is implicit (we do not include t in our notations inside this proof).

Definition 3 (SRC problem)

Let G = (V, E, δ) be a DAG, R be a positive integer, and P be a length. Does there exist a valid schedule σ ∈ Σ(G) such that:

RN σ (G) ≤ R

and total schedule time ≤ P

The SRC problem has been proven NP-hard in [START_REF] Eisenbeis | Allocating Registers in Multiple Instruction-Issuing Processors[END_REF]. Now we prove the equivalence of ReduceRS and SRC in terms of computational complexity.

ReduceRS =⇒ SRC

Let G be a solution for the ReduceRS problem. Then trivially, any "as soon as possible" schedule σ ∈ Σ(G) is a solution for SRC.

SRC =⇒ ReduceRS

Let σ be a solution for SRC, i.e., RN σ (G) ≤ R with a total schedule time of ≤ P. We build an extended DDG G by adding serial edges to impose the same precedence relations as defined by σ on the value lifetimes of any schedule of G. Then, ∀u, v ∈ V R |LT σ (u) ≺ LT σ (v) we add the following edges:

• If v ∈ Cons(u), add serial edges from the readers of u (except v) to v; the set of added edges is:

e = (u ′ , v)| u ′ ∈ Cons(u) -{v}
• Otherwise, add serial edges from all u's readers to v; the set of added edges is:

e = (u ′ , v)| u ′ ∈ Cons(u)
The latency of these added edges has to be assigned based on the target architecture. There are two cases:

1. in the case of superscalar codes, there are sequential code semantics. So, the latency of each added edge is set to 1;

2. in the case of VLIW or EPIC/IA64, there are reading and writing offsets. Thus, for each added edge e = (u ′ , v), the latency is set to δ(e) = δ r (u ′ ) -δ w (v).

Indeed, the added edges and the chosen latencies force the following assertion:

LT σ (u) ≺ LT σ (v) =⇒ ∀σ ′ ∈ Σ(G) : LT σ ′ (u) ≺ LT σ ′ (v)
Then, for all values not simultaneously alive according to σ, there is no schedule σ ′ of G that makes them simultaneously alive. Formally, :

¬ ∃u, v ∈ V R , LT σ (u) ≺ LT σ (v), ∃σ ′ ∈ Σ(G)| LT σ ′ (u) ∩ LT σ ′ (v) = φ
In other words, we ensure that any schedule of G will guarantee the precedence relations between the lifetime intervals of G according σ. Consequently, any schedule σ ′ of G cannot require more than the register need of σ and

RS(G) = RN σ (G) ≤ R
A solution for the SRC problem may create a cycle in the solution of ReduceRS. We are sure that if any cycle is introduced in G, then it must be non-positive because there exists at least the valid schedule σ ∈ Σ(G). Consequently, a solution of the ReduceRS problem may produce a cyclic DDG. We will see later how to eliminate these solutions.

With regard to the critical path of G, the introduced serial edges ensure that at least σ ∈ Σ(G). Since there exists such a schedule with a total time ≤ P, the critical path of G cannot be longer than P.

The next section provides an algorithmic heuristics that tries to reduce RS below a limit. This section follows the ideas and notations used in Section 4.

An Algorithmic Heuristics for Reducing the Register Saturation

For clarity and without loss of generality, let us focus on only one register type2 . Then, our notations become V R for the set of values of the implicit type we consider, E R for the set of flow edges through a register of that type, δ r and δ w for reading/writing delays, and RN σ (G) for the register need of the type we consider. Also, we use the notation u for both the operation u and the value of the considered type it produces.

In this section we build an extended DAG G = G\ E such that the RS is limited by a strictly positive integer (number of available registers) with the respect of the critical path. Let R be this limit. Then : This section presents a heuristics that adds serial edges to prevent some saturating values in AM k (according to a saturating killing function k) from being simultaneously alive for any schedule. Also, we take care not to increase the critical path, if possible.

∀σ ∈ Σ(G) : RN σ (G) ≤ RS(G) ≤ R
Serializing two values u, v ∈ V R means that the killing of u must always be carried out before the definition of v, or vice-versa, as illustrated by Figure 9. A value serialization u → v for two values u, v ∈ V R is defined by:

• if v ∈ pkill G (u) then add the serial edges e = (v ′ , v)|v ′ ∈ pkill G (u) -{v} . Textually, this means that if v is a
potential killer of u, the value serialization u → v means to add a serial edge from any potential killer of u (except v) to v itself, see Figure 9.c.

• otherwise add the serial edges e = (u

′ , v)|u ′ ∈ pkill G (u) ∧ ¬(v < u ′ )
Textually, this means that if v is not a potential killer of u, the value serialization u → v means to add a serial edge from any potential killer of u to v itself, see Figure 9.d.

The latency of these added edges has to be chosen depending on the target codes. We have two cases:

1. in the case of superscalar codes, the semantics is sequential. So, the latency of each added edge is set to 1;

2. in the case of VLIW or EPIC/IA64, there exist reading and writing offsets 3 . Thus, for each added edge e = (u ′ , v), the latency is set to δ(e) = δ r (u ′ ) -δ w (v).

In order to not violate the DAG property (we must not introduce a cycle), some serializations must be filtered out. The condition for applying u → v is that ∀v ′ ∈ pkill G (u) : ¬(v < v ′ ). We chose the best serialization within the set of all the possible serializations by using a cost function ω(u → v) = (ω 1 , ω 2 ), such that:

• ω 1 = µ 1 -µ 2 tries to predict how much RS would be reduced (in the best case) if we carry out this value serialization, where µ 1 is the number of saturating values serialized after u if we carry out this value serialization u → v; -µ 2 is the predicted number of u's descendant values that can become simultaneously alive with u;

• ω 2 is the predicted increase in the critical path.

Our heuristics is described in Algorithm 3. It iterates value serializations within the saturating values until we get the limit R or until no more serializations are possible (or none is expected to reduce the RS). One can check that if there is no possible value serialization in the original DAG, our algorithm exits at the first iteration of the outer while-loop. If it succeeds, then any schedule of G needs at most R registers. If not, it still decreases the original RS, and thus limits the register need.

Introducing and minimizing the spill code is another NP-complete problem studied in [START_REF] Bergner | Spill Code Minimization via Interference Region Spilling[END_REF][START_REF] Bernstein | Spill Code Minimization Techniques for Optimizing Compilers[END_REF][START_REF] Callahan | Register Allocation via Hierarchical Graph Coloring[END_REF][START_REF] Chaitin | Register Allocation and Spilling via Graph Coloring[END_REF][START_REF] Poletto | Linear Scan Register Allocation[END_REF] and is not addressed in this article. Now, we explain how to compute the prediction parameters µ 1 , µ 2 , ω 2 . We note G i the extended DAG of step i, k i its saturating function, and AM ki its saturating values and ↓ Ri u the descendant values of u in G i :

1. (u → v) ensures that k i+1 (u) < v in G i+1 . According to Lemma 2, µ 1 = | ↓ Ri v ∩ AM ki | is the number of saturating
values in G i which cannot be simultaneously alive with u in G i+1 ;

2. new saturating values could be introduced into

G i+1 : if v ∈ pkill Gi (u), we force k i+1 (u) = v. According to Lemma 2, µ 2 =   v ′ ∈pkill G i (u) ↓ Ri v ′   -↓ Ri v
is the number of values which could be simultaneously alive with u in G i+1 . µ 2 = 0 otherwise;

3. if we carry out (u → v) in G i , the introduced serial edges could enlarge the critical path. Let lp i (v ′ , v) be the longest path going from v ′ to v in G i . The new longest path in G i+1 going through the serialized nodes is:

max introduced e=(v ′ ,v) δ(e)>lpi (v ′ ,v) lp i (⊤, v ′ ) + lp i (v, ⊥) + δ(e)
If this path is greater than the critical path in G i , then ω 2 is the difference between them, 0 otherwise.

Algorithm 3 Value Serialization Heuristics

Require: a DAG G = (V, E, δ) and a strictly positive integer R

G := G compute AM k , saturating values of G; while |AM k | > R do construct the set U k of all admissible serializations between saturating values in AM k with their costs (ω 1 , ω 2 ); if ∄(u → v) ∈ U |ω 1 (u → v) > 0 then {no more possible RS reduction} exit; end if X := {(u → v) ∈ U |ω 2 (u → v) = 0}
{the set of value serializations that do not increase the critical path} if X = φ then choose a value serialization (u → v) in X with the minimum cost R -ω 1 ; else choose a value serialization (u → v) in X with the minimum cost ω 2 ; end if carry out the serialization (u → v) in G; compute the new saturating values AM k of G; end while ensure potential killing operations property {check longest paths between pkill operations} At the end of the algorithm, we apply a general check step to ensure the potential killing property proved in Lemma 1 (page 6) for the original DAG. Lemma 1 proves that the operations which do not belong to pkill G (u) cannot kill the value u. After adding the serial edges that build G, we may violate this assertion because we introduce some edges with negative latencies. If this assertion is not verified, the computed RS may be incorrect. To overcome this problem, we must guarantee the following assertion:

∀u ∈ V R , ∀v ′ ∈ Cons(u) -pkill G (u) : ∃v ∈ pkill G (u)|v ′ < v in G =⇒ lp G (v ′ , v) > δ r (v ′ ) -δ r (v) (9)
In fact, this problem occurs if we create a path in G from v ′ to v where v, v ′ ∈ pkill G (u). If assertion ( 9) is not verified, we add a serial edge e = (v ′ , v) with δ(e) = δ r (v ′ ) -δ r (v) + 1 as illustrated in Figure 10: after two value serializations during step 1 and 2, assertion ( 9) is forced to be verified during step 3. without increasing the critical path. The maximal introduced longest path through this serialization is (⊤, a, d, f, k, ⊥) = 8, which is less than the original critical path [START_REF] Pinter | Register Allocation with Instruction Scheduling: A New Approach[END_REF]. The extended DAG G is presented in part (b) where the value serialization a → f is introduced: we add the serial edges (e, f ) and (d, f ) with a -4 latency. Finally, we add the serial edges (e, f ) and (d, f ) with a unit latency to ensure the pkill G (b) property. The whole critical path does not increase and RS is reduced to 4.

Part (c) gives a saturating killing function for G, presented with bold edges in P K(G). DV k (G) is presented in part (d) to show that the new RS is 4 floating point registers.

After providing an approximate algorithm for RS reduction, the next section presents an optimal exact method using integer linear programming.

An Optimal Method for RS Reduction

The proof of Theorem 4 gives the intuition for our optimal solution for the ReduceRS problem using integer programming. It is computed in two steps:

1. we first compute a valid schedule σ such that the register need of type t is maximized but does not exceed R t , while the total schedule time is bounded. Again, this schedule is different from the final one to be computed under resource constraints;

2. then, we add serial edges as described by the proof of Theorem 4. This results in an extended DDG that has a bounded register saturation with a minimized critical path.

In order to compute such a minimal schedule that does not require more than R t registers, we use our intLP formulation previously defined in Section 5 that maximizes the register need. We keep all the constraints and variables of Section 5, except those that compute a maximal independent set. Now, we use a binary variable x i u t for each value u t which is set to 1 if the value u t is stored in the register i. Since there are R t available registers, we have at most |V | × R t variables. Since R t is a constant in our problem (the number of registers in the target machine), the number of these variables is O(|V |).

The intLP system tries to build a coloring of the interference graph with exactly R t colors (the maximal number of available registers). If no solution can be found with R t registers, then solve another intLP after decrementing R t (until to 1). If no final solution can be found when reaching one available register, then the register saturation cannot be reduced and spilling is unavoidable. The variables x i u t are computed using the following constraints.

• a value u t is stored in only one register of type t:

∀t ∈ T , ∀u t ∈ V R,t : Rt i=1 x i u t = 1
• if two values interfere, then they cannot share the same register:

∀t ∈ T , ∀ couple u t , v t ∈ V R,t : s t u,v ≥ 1 =⇒ x i u t + x i v t ≤ 1, ∀i = 1, ..., R t There are at most O(V 2 × R t ) = O(V 2 ) such constraints.
• The objective function minimizes the total schedule time:

Minimise σ ⊥ As explained before, our DAG and processor model includes writing and reading offsets. Consequently, in some cases, the optimal RS reduction may need to introduce non-positive cycles into the original DAG. Even if such non-positive cycles do not prevent the graph from being scheduled, they still violate the DAG property and impose hard scheduling constraints that may not be satisfiable under resource constraints in the subsequent instruction scheduling pass. We must eliminate such optimal solutions as explained in the following section.

Eliminating Cycles with Non-positive Latencies

As presented in the proof of Theorem 4, the latency of any added edge e = (u ′ , v) is equal to δ(e) = δ r (u ′ ) -δ w (v) in the case of VLIW code. Thus, if δ r (u ′ ) ≤ δ w (v) then δ(e) becomes non-positive, producing possible non-positive cycles.

Remember that the purpose of the register saturation analysis is to ensure in the first steps of compilation that any schedule of a given DAG will not require more registers than those available. The scheduling phase is mainly constrained by resources (functional units) of the target architecture. If the extended DDG produced by the register saturation reduction contains a nonpositive cycle, we cannot guarantee the existence of a schedule under resource constraints. This is because non-positive cycles introduce some "not later than" scheduling constraints which may not be satisfied in the presence of resource constraints 4 .

For instance, let us assume a zero weighted cycle between two operations u and v. Theoretically, any schedule such that σ(u) = σ(v) satisfies this zero weighted cycle. However, if we have a resource constraint that prohibits these two operations from being scheduled at the same clock cycle, then there is no valid schedule that meets these constraints. When we reduce the register saturation, we must ensure than there is always a schedule for any resource constraints. The following example gives an illustration.

Example 2

We use Figure 12 in this example. The register saturation of the DAG in Part ( 1) is equal to 3 (easy to see that we can schedule {a, b, c} to be simultaneously alive). Here we assume that the reading and writing delays are equal to zero. Let ask the question: does there exist an extended DDG of the DAG in Part [START_REF] Altman | Optimal Software Pipelining with Functional Units and Registers[END_REF] with a RS equal to two while the critical path is equal to eight ? The answer is yes. The extended DDG is presented in Part [START_REF] Bergner | Spill Code Minimization via Interference Region Spilling[END_REF]. The VLIW schedule in Part [START_REF] Ambrosch | Dependence-Conscious Global Register Allocation[END_REF] shows that it requires two registers while its total schedule time is equal to 8. As can be seen, the extended DDG constructed from this schedule has a null cycle between c and d. We can easily see that we cannot construct any extended DDG without a cycle, since the minimal register need of the DAG is 2: the lifetimes intervals of the values c and d must be necessary serialized after the intervals of a and b if we want to require only two registers. These two lifetime intervals serializations are responsible for introducing the null cycle between c and d. Now, if we accept the extended DDG of Part (3) as a solution, we cannot guarantee the existence of a schedule under any resource constraints. For instance, if c and d cannot be scheduled in parallel because of resource conflicts, then no valid schedule exists. We do admit such situation in the process of RS reduction.

Note that the problem of non-positive cycles does not arise for superscalar (sequential) codes because all the introduced edges have a positive latency equal to 1. As example, the minimal register saturation (in the case of superscalar codes) of the DAG in Figure 12.( 1) is equal to 3 (instead of 2 in the case of VLIW codes). The superscalar schedule is presented in Part (4) with its corresponding extended DAG in Part [START_REF] Bernstein | Scheduling Arithmetic and Load Operations in parallel with No Spilling[END_REF].

To eliminate this problem of non-positive cycles, we impose the restriction that the extended graph G must be a DAG. This is done by guaranteeing the existence of a topological sort for the extended graph. Therefore, we add some variables and constraints to the optimal intLP system. • We define integer variables that hold a topological ordering of the graph. For each u ∈ V , we associate an integer variable d u , such that for any two nodes u and w, d u < d w means that u is topologically sorted before w.

• We bound the topological sort by the number of nodes: ∀u ∈ V :

d u ≤ |V |
• We write the topological sort constraints for each edge in the original DAG: ∀e = (u, v) ∈ E :

d u < d v
• If we add a serial edge in the extended DDG, we must satisfy the topological sort constraints. If two lifetime intervals LT σ (u t ) and LT σ (v t ) do not interfere with each other, serial edges will be introduced. ∀u, v ∈ V R,t :

-if v ∈ Cons(u t ), serial edges will be added from the u's other readers to v. We then write the constraints:

LT σ (u t ) ≺ LT σ (v t ) =⇒ ∀u ′ ∈ Cons(u t ) -{v} : d u ′ < d v That is, σ v + δ w,t (v) -k u t ≥ 0 =⇒ ∀u ′ ∈ Cons(u t ) -{v} : d u ′ < d v -if v ∈ Cons(u t )
, serial edges will be added from all u's readers to v. We then write the constraints:

LT σ (u t ) ≺ LT σ (v t ) =⇒ ∀u ′ ∈ Cons(u t ) : d u ′ < d v That is, σ v + δ w,t (v) -k u t ≥ 0 =⇒ ∀u ′ ∈ Cons(u t ) : d u ′ < d v
Note that these constraints may be optimized by considering the fact that some values can never interfere, see Section 5.4. We add at most O(|V | 3 ) variables and O(|V | 3 +|E|) constraints to guarantee that reducing RS always produces an acyclic extended DAG. Again, these constraints are only added for VLIW and EPIC codes, not for superscalar codes.

We continue in the next section with the result of our experimental implementation.

Experiments

This section presents our experimental results from some DDGs extracted from SpecFP, whetstone, livermore and linpack. Such graphs can be explored in [START_REF] Touati | Register Pressure in Instruction Level Parallelisme[END_REF]. These DDGs are those that have been used in the prior studies [START_REF] De Werra | On a Graph-Theoretical Model for Cyclic Register Allocation[END_REF][START_REF] Govindarajan | Minimizing Register Requirements under Resource-Constrained Rate-Optimal Software Pipelining[END_REF]. In our experiments, we focus on floating point registers and we assume that we target superscalar codes. The DAGs used for the experiments are the loop bodies. This section presents our concluding analysis.

Before starting the presentation of our experiments, we would like to argue why we chose to evaluate our method using graphs instead of implementing it inside a real compiler. First, since our study focuses on register optimization in DDGs, we decide to check the efficiency of our heuristics on some realistic graphs extracted from real codes. This way of evaluation that does not require a complete implementation inside a compiler allows us to isolate our contribution by demonstrating the efficiency of our heuristics on DDGs. If we include our heuristics inside an existing optimizing compiler, it would be hard to isolate our contribution, since the optimizing compilation passes are numerous nowadays, and their interactions (whether they are with the hardware or with other compilation passes) are difficult to analyze. In other words, for any value of the resulted speedup (positive or negative), it is very hard to certify that the speedup gain or loss results directly and only from our heuristics. It is possible that the interaction with other compilation passes may inhibit or accentuate the performance gain. So, we think that it is better for us to concentrate our attention on graphs.

Second, we think that our experiments are realistic because our theoretical model takes into account VLIW, EPIC and superscalar codes. Usually, not all register optimization methods, even those implemented inside compilers, work for these three types of program semantics. Third and last, our experiments clearly demonstrates nearly optimal results, which is an important aspect in our case of combinatorial problems.

Computing RS

The first experiments check the efficiency of our Greedy-k algorithm compared to optimal RS (computed by integer programming). The next section summarizes our results.

Optimal vs. Approximated Methods

Let RS denote the optimal register saturation computed by intLP, and RS * the approximated RS as computed by our heuristics. The experimental results show that our approximate algorithm is very efficient: in almost all cases, it computes the exact register saturation. The maximal experimental error is 1, i.e., the optimal register saturation is one larger than the saturation computed by our heuristics. We have unrolled the loops to increase register pressure in order to study the efficiency of our heuristics in larger DAGs. DAGs are the bodies of these unrolled loops: the number of nodes in these unrolled loops ranges from 4 to 120.

Our approximated algorithm clearly computes nearly optimal solutions in polynomial time. In the 134 DAGs used in this study (up to 120 nodes per DAG), we do not reach RS optimality in only 7 cases. Our worst empirical error is 1, i.e., RS * ≤ RS ≤ RS * + 1.

After evaluating the efficiency of our method, we use it to experimentally study the RS behavior in unrolled loops.

RS Behavior in Unrolled Loops

In this experiment, we study the RS evolution as a function of the unrolling degree in each loop. Figure 13 shows the plots of RS (computed by our heuristics) versus the unrolling degree. Loops are unrolled from 1 to 20 times, producing DAGs with between 4 to 400 nodes, which is sufficient to study the RS behavior in real applications. As we expect, RS is evidently a non-decreasing function: since unrolling a loop produces more values because of loop bodies duplication, RS could not decrease. The RS versus the unrolling factor produces a function that can be one of the two following cases:

1. constant or non strictly increasing because of recurrent data dependences;

2. linear in the case of, for instance, fully parallel loops.

If the number of available registers is bounded, we must keep RS under control. The next section summarizes our results. 1. In the case where RS = RS * , our algorithm succeeds in optimally reducing RS. Then, the ILP loss may be:

(a) ILP = ILP * (family 1). Our algorithm succeeds in optimally reducing RS with the optimal ILP loss. 72.22% of all the results belong to this family.

(b) ILP < ILP * (family 2). Our algorithm succeeds in optimally reducing RS but with sub-optimal ILP loss. 18.5% of all the results belong to this family.

(c) ILP > ILP * is not possible.

2. In the case where RS > RS * , our algorithm did not succeed in optimally reducing RS. Then, the ILP loss may be:

(a) ILP = ILP * (family 3). Our algorithm has sub-optimal RS reduction but optimal ILP loss. 4.63% of all the results belong to this family.

(b) ILP < ILP * (family 4). Our algorithm has sub-optimal RS reduction with sub-optimal ILP loss. Less than 1% of all the results belong to this family.

(c) ILP > ILP * (family 5). Our algorithm has sub-optimal RS reduction but with super-optimal ILP loss. This case is interesting: since our algorithm has sub-optimal RS reduction, it has extra registers which allow more ILP.

3.7% of all the results belong to this family.

3. The case where RS < RS * is impossible because our heuristics compute a valid RS * .

Clearly, our RS reduction algorithm is very efficient: in most cases, it optimally reduces RS with optimal ILP loss. Sub-optimal ILP loss is, in most cases, accompanied by optimal RS reduction, while sub-optimal RS reduction is mostly accompanied by super-optimal ILP loss. We get both sub-optimal ILP loss and sub-optimal RS reducing in less than 1% of the cases.

Having established the efficiency of value serialization, we use it to study ILP loss in unrolled loops.

ILP Loss after RS reduction in Unrolled Loops

We unroll the loops up to 20 times to get larger DAGs (up to 400 nodes). We try to maintain their RS under 32 FP registers. Figure 15 plots ILP loss according to unrolling degree. In most cases, our heuristics do not produce a loss of ILP, i.e., critical paths do not increase. However, in some cases, ILP loss exceeds 60% (the case of spec-spice-loop8) in order to maintain a RS under 32.

As in the RS reduction experiments, the ILP loss is not an increasing function. The explanation is that the more independent nodes are available in the DAG, the more lifetime interval serialization opportunities are possible. Our heuristics have more freedom to choose the best interval serialization that minimizes critical path growth. We note that, in these experiments, some operations have long specified latencies (up to 17 for an FP division). These long latencies can dramatically increases the critical path, since we may introduce serial edges that merge two long paths.

Before concluding, we wish to argue that the RS approach is a better way to satisfy register constraints before ILP scheduling than existing register need minimization approaches.

Related Work and Discussion

The literature contains a lot of techniques for minimizing the register requirement in superscalar (sequential) codes that are sensitive to ILP scheduling [START_REF] Ambrosch | Dependence-Conscious Global Register Allocation[END_REF][START_REF] Goodman | Code Scheduling and Register Allocation in Large Basic Blocks[END_REF][START_REF] Govindarajan | Minimum Register Instruction Sequencing to Reduce Register Spills in Out-of-Order Issue Superscalar Architecture[END_REF][START_REF] Janssen | Compilers Strategies for Transport Triggered Architectures[END_REF][START_REF] Norris | A Scheduler-Sensitive Global Register Allocator[END_REF][START_REF] Pinter | Register Allocation with Instruction Scheduling: A New Approach[END_REF]. Others prefer to combine ILP scheduling with register allocation [START_REF] Bernstein | Scheduling Arithmetic and Load Operations in parallel with No Spilling[END_REF][START_REF] Brasier | CRAIG: A Practical Framework for Combining Instruction Scheduling and Register Assignment[END_REF][START_REF] Freudenberger | Phase Ordering of Register Allocation and Instruction Scheduling[END_REF][START_REF] Meleis | Dural-Issue Scheduling for Binary Trees with Spills and Pipelined Loads[END_REF][START_REF] Silvera | A Register Pressure Sensitive Instruction Scheduler for Dynamic Issue Processors[END_REF]. All these techniques try to minimize the register requirement. In our method, we use the contrary approach : we maximize the register requirement in order to minimize the number of edges added to the DAG, as previously done by Berson [START_REF] Berson | Unification of Register Allocation and Instruction Scheduling in Compilers for Fine-Grain Parallel Architecture[END_REF]. Minimizing the register requirement is an inherently worse technique than saturating the register requirement for many reasons, which we explain below. Case where register constraints are obsolete Given a DAG, we do not need to add serial edges if the RS does not exceed the number of available registers. Unfortunately, the minimization approach adds extra edges if the register requirement can be further reduced, even if RS does not exceed the limit. For instance, look at Figure 16, where bold circles are the values to be stored in registers and bold edges are the flow dependences. The initial DAG has a register saturation equal to 4 : this is because we can schedule the 4 operations {a, b, c, d} so as to produce 4 values simultaneously alive. If the processor has at least 4 registers, then the DAG is not modified before the scheduling pass. However, with a minimization approach, the new DAG in Part (b) is restricted to not require more than 2 registers5 , regardless the number of available registers. The DAG in Part (b) is more restrictive than the initial DAG, which is left unmodified by the RS analysis pass.

How many edges are introduced If the inherent data dependences of a DAG produce restrictive register pressure for an ILP scheduler (when RS exceeds the number of available registers), the minimization approach adds more edges than the RS reduction approach. This is because our method introduces only the necessary number of edges to reduce RS below the register limit. However, the minimization approaches tries to reduce the register need to the lowest possible level. This is not an appropriate approach, since it does not fully utilize the available registers. For instance, look at Figure 16 and assume we have 3 registers available. Part (c) shows the new DAG produced by the RS reduction pass: here, RS is reduced from 4 to 3, and hence we have fewer serialization edges than those produced by the minimization approach presented in Part (b). Using the RS approach, the final allocator could use 1, 2 or 3 registers depending on the schedule. Using a register minimization approach, the scheduler could use only 1 or 2 registers. Hence, the RS approach helps the scheduler make better use of the available registers.

When both methods are equivalent If the target processor is superscalar with out-of-order execution, and if its dynamic scheduler is optimal and the register renaming hardware has an infinite number of hidden registers, both methods (RS and register need minimization) should be equivalent. With a limited number of hidden registers for renaming, and a sub-optimal runtime scheduler, our RS method is likely to produce better code because it makes better use of the available registers.

Our methods apply for explicit reading/writing offsets Our DAG and processor model allows for explicit delays when reading from and writing into registers. Thus, our method is more generic than existing techniques, and can be applied to superscalar, VLIW and EPIC architectures. For the last two cases, special care must be taken when reducing RS: we must prohibit non-positive cycles in the resulting DAGs.

In the case of a global scheduler Our model assumes that there is only one possible definition per value. This assumption is correct inside a basic bloc (BB), i.e., if the code does not contain branches. In the case of a global control flow graph (CFG), a static data dependence analysis may result in some values with more than one definition because it cannot determine which execution path is taken. We show in [START_REF] Touati | Register Pressure in Instruction Level Parallelisme[END_REF] how to extend RS analysis to a global acyclic CFG (excluding loops), and its interaction with a global instruction scheduler that may move operations from one BB to another.

Comparison to URSA Our work is an extension to URSA [START_REF] Berson | Unification of Register Allocation and Instruction Scheduling in Compilers for Fine-Grain Parallel Architecture[END_REF][START_REF] Berson | URSA: A Unified ReSource Allocator for Registers and Functional Units in VLIW Architectures[END_REF]. Their minimum killing set technique tries to saturate the register requirement in a DAG by keeping the values alive as long as possible: the authors proceed by keeping as many children in a bipartite component alive as possible by computing the minimum set which kills all the parent's values. First, since the authors did not formalize the RS problem, we can easily give examples to show that a minimum killing set does not saturate the register need, even if the solution is optimal. Figure. 17 shows an example where the RS computed by our heuristics (Part (b)) is 6 where the optimal solution for URSA yields a RS of 5 (Part (c)). This is because URSA did not take into account the descendant values while computing the killing sets. Second, the validity of the killing function is an important condition to compute the RS and unfortunately is not included in URSA. We showed in Section 3 that invalid killing functions exist. So, the proof in [START_REF] Berson | URSA: A Unified ReSource Allocator for Registers and Functional Units in VLIW Architectures[END_REF] about the NP-completeness of RS computation is incomplete, since they did not prove the validity of the computed killing function. Finally, the URSA DAG model did not differentiate between the types of values and did not take into account delays in reading from and writing into the registers file.

Resource constraints Our experimental results are presented in the form of joint statements about critical path length and register requirement. Can anything formal be said about machines with finite resources ? Since our techniques assume infinite resources, it is theoretically possible that edges inserted to decrease register pressure might lead to unbalanced functional unit usage. Thus, edges might accidentally dictate bursts of all integer, all memory, or all floating point operations.

Let us answer this possible limitation. First, our work focus on data dependence graphs. Thus, a schedule can certainly be found on a machine with finite resources. Reporting resource conflicts at the graph level can only be done with simple resource descriptions (no structural hazards, i.e., a FU is used during a contiguous interval of time), as done by Berson in [START_REF] Berson | Unification of Register Allocation and Instruction Scheduling in Compilers for Fine-Grain Parallel Architecture[END_REF] and Pinter in [START_REF] Pinter | Register Allocation with Instruction Scheduling: A New Approach[END_REF]. This strategy gives exactly the same solution as scheduling under resource and register constraints, i.e., it is nothing but a combined approach of scheduling and register allocation. Second, the FU usage may be decreased especially if we try to minimize the register requirement. In our framework, we saturate the register requirement, thus the RS concept helps us reduce the number of serialization edges added to the DAG. Third and last, we give priority to register constraints over ILP scheduler (but we are still sensitive to this later) because we believe that spill code is more damaging to performance than a weak ILP extraction.

The methods of [START_REF] Berson | Unification of Register Allocation and Instruction Scheduling in Compilers for Fine-Grain Parallel Architecture[END_REF][START_REF] Pinter | Register Allocation with Instruction Scheduling: A New Approach[END_REF] combine resource and register constraints. Their methods are only studied for superscalar codes with a unique register type, while our method works for VLIW, EPIC and superscalar codes with multiple register types. Furthermore, we did not read any experimental results that highlight if the heuristics of [START_REF] Berson | Unification of Register Allocation and Instruction Scheduling in Compilers for Fine-Grain Parallel Architecture[END_REF][START_REF] Pinter | Register Allocation with Instruction Scheduling: A New Approach[END_REF] are near or far from the optimal, while we propose nearly optimal heuristics.

Conclusion

In this paper, we formally study the register saturation (RS) notion to manage register pressure in acyclic data dependence graphs (DAGs). RS helps to avoid inserting spill code before instruction scheduling and register allocation steps. We believe that register constraints must be taken into account before ILP scheduling, but by using the RS concept instead of the existing strategies that minimize the register need. Otherwise, the subsequent ILP scheduler is restricted even if enough registers exist.

We give many fundamental results regarding the RS computation. First, we prove that choosing an appropriated unique killer is sufficient to saturate the register need. Second, we prove that fixing a unique killer per value allows to optimally compute the register saturation with polynomial time algorithms. If a unique killer is not fixed per value, we prove that computing the register saturation of a DAG is NP-complete in the general case (except for expression trees for instance). An exact formulation using integer programming and an efficient approximate algorithm are presented. Our formal mathematical modeling and theoretical study enable us to give nearly optimal heuristics. Our experiments show that register constraints may be obsolete in many codes, and can therefore be ignored in order to simplify the instruction scheduling process. The heuristics we use manage to reduce RS in most cases while some ILP is lost in few DAGs.

If RS exceeds the number of available registers, we must reduce it while minimizing the increase to the critical path. We prove that this is an NP-hard problem. An optimal exact RS reduction method based on integer programming is presented, as well as an efficient approximate algorithm. If we assume writing offsets (such as those in VLIW and EPIC codes), some optimal solutions may require the insertion of non-positive cycles in the original DAG. These cycles may prevent the extended DDG from being scheduled in the presence of resource constraints. A sufficient and necessary condition to overcome this problem is to guarantee the existence of a topological sort for the extended graph. This is done by adding new constraints to the intLP formulation.

The size complexity of our intLP formulations depends only the size of the input DAG (quadratic on the number of edges and nodes). This is better than the size complexity of the existing technique in the literature that model register constraints [START_REF] Altman | Optimal Software Pipelining with Functional Units and Registers[END_REF][START_REF] Eisenbeis | Allocating Registers in Multiple Instruction-Issuing Processors[END_REF][START_REF] Eisenbeis | Optimal Loop Parallelization under Register Constraints[END_REF]. Indeed, these exact intLP systems have a size complexity that depends on a worst-case total schedule time factor, which does not depend on the size of the input DAG. Thus, the resulting size complexity is pseudo-polynomial, and not polynomial as in our intLP system.

An important problem (left for a future work) is the insertion of minimal spill code in data dependence graphs. The existing studies insert spill operations either in sequential codes (regardless on FUs usage), or by iterating ILP scheduling followed by spilling. We think that this problem must be taken into account at the data dependence graph level in order to break this iterative problem.

Figure 1 .

 1 Figure 1. Early Register Pressure Management

Figure 3 .

 3 Figure 3. Register Need of Acyclic Schedules

Figure 4 .

 4 Figure 4. Each Potential Killing Operation can Kill the Value

Figure 5 Figure 6 .

 56 Figure 5. Valid Killing Function and Bipartite Decomposition

Figure 5

 5 Figure 5 gives an example of a valid killing function k. This function is illustrated by bold edges in part (a), where each target of a bold edge kills its source. Part (b) is the DAG associated with k.According to our definition, invalid killing functions may exist. Figure6is an example, where Part (a) illustrates an arbitrary DAG with a killing function (the source of each bold edge is killed by its sink). Part (b) shows that the extended graph associated with the killing function is cyclic. According to our definition, the killing function defined in Part (a) isn't valid.Provided a valid killing function k, we can deduce the values which can never be simultaneously alive for any σ ∈ Σ(G →k ). Let ↓ R (u) =↓ u ∩ V R be the set of the descendant operations of u ∈ V that are values. We call them descendant values.

Figure 7 .

 7 Figure 7. Making Values Simultaneously Alive

Algorithm 2 Corollary 3 1 ⊥Figure 8 .

 2318 Figure 8. Example of Computing the Register Saturation

Figure 8 .

 8 Figure 8.a shows a saturating killing function k * computed by Greedy-k: bold edges mean that each source is killed by its sink. Each killer is labeled by its cost ρ. Part (b) gives the disjoint value DAG associated with k * . The Saturating values are {a, b, c, d, f, j, k}, so the RS is 7.

Figure 9 .

 9 Figure 9. Value Serialization

Example 1 Figure 10 Figure 11 .

 11011 Figure 10. Checking the Potential Killers Property

Figure 12 .

 12 Figure 12. Example of Non-positive Cycles

Figure 14 .

 14 Figure 14. RS Reduction in Unrolled Loops (R = 32)

Figure 15 .Figure 16 .

 1516 Figure 15. ILP Loss in Unrolled Loops (R = 32)

Figure 17

 17 Figure 17. URSA Drawback

  is the set of values alive at time step i. A maximal set of values simultaneously alive are called excessive values. In other terms, if the register need at time step i is maximal, then all the values alive at this time step are called excessive values. Figure3is an example of a valid schedule for the previous DAG that needs three FP registers. The bars represent the lifetime intervals. {e, f } are the killers of b. {a, b, d} is a set of FP excessive values since they are the maximum number of values simultaneously alive of type float. 9 is a FP excessive clock cycle since at this time there are three FP values simultaneously alive. Note that we may have more than one set of excessive values, since the register need may be defined with many sets of values simultaneously alive.

	0: a ; b ; c
	3:
	4: d ; g
	LT(d)
	8:
	11:
	12: h ; i
	LT(i)
	16:
	LT(h)
	28:
	time

  All this is proved by Lemma 3, as follows. Extended G →k to enforce values to be simultaneously alive Require: a valid killing function k construct the extended graph G →k associated with k G ′ ← G →k {the final extended graph is initialized} search for a maximal antichain AM k in the disjoint value DAG DV k

	Algorithm 1

While it is evident that a killer is unique in the case of linear codes (superscalar), VLIW codes may leads to multiple killers per value.

If more than one register type exists, we apply our algorithm on each type.

On EPIC/IA64 architectures, a writer and a reader can be scheduled at the same instruction group, so the writing delay is statically considered as zero.

Such constraints are similar to real time constraints, which cannot always be satisfied.

Here, we minimize the register requirement under critical path constraints.

Acknowledgement

We would like to thank Alain Darte from École Normale Supérieur de Lyon and Franc ¸ois Thomasset from INRIA-Rocquencourt for their help to improve this work.

Reducing RS

In this section, we experimentally study our techniques for reducing RS under critical path constraints. At first, we investigate the efficiency of our heuristics versus the optimal results.

(Approximated) Value Serialization Heuristics versus Optimal RS Reduction

Let us begin by stressing our heuristics to check their limitations. We consider DAGs of loop bodies and try to reduce the register saturation to the lowest possible value. This is done by setting the number of available registers R = 1. Our value serialization heuristics get sub-optimal results for only 7 of the 27 DAGs used in the experiment. The optimally reduced RS is less than our heuristics results by two registers in the worst case.

In the second set of experiments, we unroll the loops with multiple factors (up to 6, with up to 80 node DAGs) and we try to reduce their RS under a limit computed as the first power of 2 lower than the original RS. For example, if the original RS is 12 then we reduce it to 8, etc.

Here, we also get a maximal experimental error of 2 registers. We didn't check for larger unrolling degrees because computing optimal RS reduction of larger DAGs is computational intractable. We think that the experiments that we have performed are sufficient to study the efficiency of our strategies (the number of nodes in all these unrolled loops ranges from 4 to 80).

After evaluating the efficiency of value serialization, we use it to investigate unrolled loops.

Value Serialization Heuristics Behavior in Unrolled Loops

We study the limit of RS reduction versus the degree of loop unrolling (we consider the DAG of the loop bodies after unrolling). Figure 14 plots RS reduced to 32 registers using our heuristics on various loops with unroll factors ranging from 1 to 20. In almost all practical cases, RS is maintained under the 32-register limit, except for Livermore-loop23. In that case, RS is maintained under 32 until the loop is unrolled by a factor of 12. After that, the register pressure is sufficiently high to always keep the register need above 32. The reason is shared by both intrinsic data dependences properties (intrinsic register pressure, i.e., register sufficiency) and our heuristics limitations. If RS cannot be reduced below the limit, we have to insert spill operations, which is outside the scope of this paper. A special remark is that reduced RS in unrolled loops is not an increasing function. That is, if we reduce the RS to R 1 > R in the loop unrolled n times, and to R 2 > R in the loop unrolled n + 1 times, this does not necessary mean that R 1 ≤ R 2 (see Livermore-loop23 in Figure 14). The explanation is that as more independent nodes are available in a DAG, the more serialization opportunities are possible. Consequently, this results in more freedom and more choices for our heuristics.

ILP Loss after RS Reduction

In this last section, we study the ILP lost due to RS reduction. We evaluate the maximal theoretical ILP of a DAG G = (V, E, δ) as:

The ratio used for expressing the ILP loss is original ILPnew ILP original ILP We start by examining the efficiency of the value serialization heuristics in terms of ILP loss.

Optimal versus Approximated ILP Loss

Let us examine the ILP loss in our experiments. Results can be decomposed into five families, depending on the obtained RS and ILP loss after reduction. We denote by RS and ILP the RS reduction and ILP loss resulting from optimal intLP programs; we denote by RS * and ILP * the RS reduction and ILP loss resulting from our heuristics. Then, the five families of results are the following.