Andreas Hartmann
email: andreas.hartmann@math.u-bordeaux1.fr

INTERPOLATION AND HARMONIC MAJORANTS IN BIG HARDY-ORLICZ SPACES

Keywords: Mathematics Subject Classification. 30E05, 31A05 free interpolation, Hardy-Orlicz spaces, harmonic majorants

Free interpolation in Hardy spaces is characterized by the well-known Carleson condition. The result extends to Hardy-Orlicz spaces contained in the scale of classical Hardy spaces H p , p > 0. For the Smirnov and the Nevanlinna classes, interpolating sequences have been characterized in a recent paper in terms of the existence of harmonic majorants (quasi-bounded in the case of the Smirnov class). Since the Smirnov class can be regarded as the union over all Hardy-Orlicz spaces associated with a so-called strongly convex function, it is natural to ask how the condition changes from the Carleson condition in classical Hardy spaces to harmonic majorants in the Smirnov class. The aim of this paper is to narrow down this gap from the Smirnov class to "big" Hardy-Orlicz spaces. More precisely, we characterize interpolating sequences for a class of Hardy-Orlicz spaces that carry an algebraic structure and that are strictly bigger than p>0 H p . It turns out that the interpolating sequences are again characterized by the existence of quasi-bounded majorants, but now the functions defining these quasi-bounded majorants have to be in suitable Orlicz spaces. The existence of harmonic majorants in such Orlicz spaces will also be discussed in the general situation. We finish the paper with a class of examples of separated Blaschke sequences that are interpolating for certain Hardy-Orlicz spaces without being interpolating for slightly smaller ones.

INTRODUCTION

For a sequence Λ in the unit disk D and a space of holomorphic functions X ⊂ Hol(D), the interpolation problem consists in describing the trace of X on Λ, i.e. the set of restrictions X|Λ regarded as a sequence space. This problem has been considered for many spaces and also for domains different from D.

In this paper, which can be regarded as a continuation of the work in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF], we will focus on spaces included in the Nevanlinna or the Smirnov class, and in particular on Hardy-like spaces. Carleson described in 1958 the interpolating sequences for the Hardy space of bounded analytic functions on the unit disk by the condition that is now called the Carleson condition [START_REF] Carleson | An interpolation problem for bounded analytic functions[END_REF]. It turns out that this condition still characterizes interpolating sequences in a much broader situation. It was successively proved to be the right condition in H p , p ≥ 1 [ShHSh], in H p , p < 1 [START_REF] Kabaȋla | Interpolation sequences for the H p classes in the case p < 1[END_REF], and for Hardy-Orlicz spaces H Φ contained in the scale H p , p > 0, in [START_REF] Hartmann | Free interpolation in Hardy-Orlicz spaces[END_REF] (even for the weaker notion of free interpolation, see the definition below).

A natural question is then to ask what happens beyond p>0 H p . It is here where we enter the territory of "big" Hardy-Orlicz spaces.

Two observations should be made at this junction. First, it is known on the one hand that the union of all Hardy-Orlicz spaces corresponds to the Smirnov class (see [START_REF] Rosenblum | Hardy classes and operator theory[END_REF]), and this union will be the same if only big Hardy-Orlicz spaces are included. On the other hand, interpolating sequences for the Smirnov class (and the Nevanlinna class) have been characterized recently in the paper [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF]. So, one could try to examine interpolating sequences for big Hardy-Orlicz spaces in the light of these results. Since the characterization for the Smirnov and Nevanlinna classes is no longer given by the Carleson condition this leads to the still open question where exactly the Carleson condition ceases to be valid (see also the Question at the end of this section).

The second observation concerns the notion of interpolating sequences itself. When one wants to characterize for example interpolating sequences for the Smirnov or the Nevanlinna class, which kind of natural trace space can one hope for a priori? The problem had been studied in the past for a priori fixed trace spaces (see [START_REF] Naftalevič | On interpolation by functions of bounded characteristic (Russian), Vilniaus Valst[END_REF] for the Nevanlinna class and [START_REF] Yanagihara | Interpolation theorems for the class N +[END_REF] for the Smirnov class), but those traces turned out to be too big (Naftalevič's case) or too small (Yanagihara's case), see [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF] for more detailed comments on this. The notion that finally appeared to be natural is that of free interpolating sequences. This notion goes back to work by Vinogradov and Havin in the middle of the seventies and has been used for general interpolation problems by Nikolski and Vasyunin for Hilbert spaces (it works also in certain Banach spaces). It has been succesfully used in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF] for the Smirnov class and the Nevanlinna class (the latter being even not a topological vector space).

Let us introduce the notion of free interpolation that we will use in this paper.

Definition.

A sequence space l is called ideal if ∞ l ⊂ l, i.e. whenever (a n ) n ∈ l and (ω n ) n ∈ ∞ , then also (ω n a n ) n ∈ l.

Definition. Let X be a space of holomorphic functions in D. A sequence Λ ⊂ D is called free interpolating for X if X|Λ is ideal. We denote Λ ∈ Int X.

Remark 1.1. For any function algebra X containing the constants, Λ ∈ Int X -or equivalently X|Λ is ideal -if and only if

∞ ⊂ X|Λ.
This remark is quite easy to check and a proof is given in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF]. Let us repeat this proof here for completeness. The inclusion is obviously necessary. In order to see that it is sufficient notice that, by assumption, for any

(ω λ ) λ ∈ ∞ there exists g ∈ X such that g(λ) = ω λ . Thus, if (f (λ)) λ ∈ X|Λ, then the sequence of values (ω λ f (λ)) λ can be interpolated by f g ∈ X.
An almost trivial but nevertheless useful remark in our context is that if Λ ∈ Int X (i.e. X|Λ is ideal) then Λ ∈ Int X (i.e. X|Λ is ideal) for any subsequence Λ ⊂ Λ.

In the case of the Nevanlinna and Smirnov classes the characterization of free interpolating sequences is given in terms of the existence of (quasi-bounded) harmonic majorants of a certain density associated with the sequence Λ. This density is expressed in terms of Blaschke products. More precisely, let b λ (z) = |λ| λ λ-z 1-λz be the elementary Blaschke factor (or Möbius transform). For a sequence Λ satisfying the Blaschke condition λ∈Λ (1 -|λ| 2 ) < ∞ -which will be assumed throughout this paper -we set B = B Λ = λ∈Λ b λ for the corresponding Blaschke product, and B λ := B Λ\{λ} . Define then

ϕ Λ (z) :=    log |B λ (λ)| -1 if z = λ ∈ Λ 0 if z / ∈ Λ.
The majorants we are interested in are positive harmonic functions. Recall that any such function h is the Poisson integral of a positive finite Borel measure µ h on T, i.e.

h(z) = P [µ h ](z) = T P z (ζ) dµ h (ζ) = T 1 -|z| 2 |ζ -z| 2 dµ h (ζ), z ∈ D,
where P z (ζ) is the usual Poisson kernel. We will denote by Har + (D) the set of all positive harmonic functions on D. A harmonic function h for which the measure µ h is absolutely continuous, dµ h = w dm for some w ∈ L 1 (T), will be called quasi-bounded. In this case we will shortly write

P [w] for P [µ h ].
The result of [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF] we are interested in is the following (we give here only an almost complete form). Recall that the Smirnov class N + is the class of holomorphic functions f on the unit disk such that

lim r→1 1 2π 2π 0 log + |f (re iθ )| dθ = 1 2π 2π 0 log + |f (e iθ )| dθ.
(Note that the existence of the limit on the left hand side implies the existence of the boundary values of f on T a.e. appearing on the right hand side).

Theorem ([HMNT04]

). Let Λ be a sequence in D. The following statements are equivalent: (c) The trace space is given by

N + |Λ = l N + := {(a λ ) λ : ∃ h ∈ Har + (D) quasi-bounded, h(λ) ≥ log + |a λ |, λ ∈ Λ}. (d) lim n→∞ sup (c λ) ∈B Λ λ:ϕ Λ (λ)≥n c λ ϕ Λ (λ) = 0, where B Λ = {(c λ ) : c λ ≥ 0 for any λ ∈ Λ and c λ P λ ∞ ≤ 1}.
The condition (d) may appear quite technical. It is in a sense a "little-o"-version of the condition that characterizes interpolation in the Nevanlinna class. In that case (see [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF]) free interpolating sequences are characterized by the fact that ϕ Λ admits a positive harmonic majorant (be it quasi-bounded or not). Such a majorant exists if and only if there is a constant C such that for every finite positive sequence (c λ ) we have

c λ ϕ Λ (λ) ≤ C c λ P λ ∞ . (1.1) (In view of discussions to come we observe that L ∞ = (L 1 ) * .)
In the light of the above theorem, and since the Hardy-Orlicz spaces we are interested in are in a sense close to the Smirnov class, it seems natural to seek a condition in the spirit of condition (b) in the theorem. The modification should involve a more precise hypothesis on the weight w adapted to the defining function of the Hardy-Orlicz space that we will introduce below. We will also see that the dual condition (d) of the theorem -or rather (1.1) -has a counterpart in the Hardy-Orlicz situation (replacing (L 1 ) * by the dual of a suitable Orlicz space).

Let ϕ : R -→ [0, ∞) be a convex, nondecreasing function satisfying (i) lim t→∞ ϕ(t)/t = ∞ (ii) ∆2 -condition: ϕ(t + 2) ≤ M ϕ(t) + K, t ≥ t 0 for some constants M, K ≥ 0 and t 0 ∈ R. Such a function is called strongly convex (see [START_REF] Rosenblum | Hardy classes and operator theory[END_REF]), and one can associate with it the corresponding Hardy-Orlicz class

H ϕ•log = {f ∈ N + : T ϕ(log |f (ζ)|) dσ(ζ) < ∞},
where f (ζ) is the non-tangential boundary value of f at ζ ∈ T, which exists almost everywhere since f ∈ N + . Throughout this paper we shall use the notation

Φ = ϕ • log .
It should be noted that the ∆2 -condition is formulated in such a way that Φ satisfies the usual ∆ 2 -condition: there exist constants M , K ≥ 0 and s 0 such that for all s ≥ s 0 we have

Φ(2s) ≤ M Φ(s) + K (1.2)
(see also Section 2 for more on Hardy-Orlicz spaces).

In [START_REF] Hartmann | Free interpolation in Hardy-Orlicz spaces[END_REF], the following result was proved.

Theorem [START_REF] Hartmann | Free interpolation in Hardy-Orlicz spaces[END_REF]). Let ϕ be a strongly convex function satisfying (i), (ii) and the V 2 -condition:

2ϕ(t) ≤ ϕ(t + α), t ≥ t 1 ,
where α > 0 is a suitable constant and t 1 ∈ R. Then Λ ⊂ D is free interpolating for H Φ if and only if Λ satisfies the so-called Carleson condition:

inf λ∈Λ |B λ (λ)| = δ > 0.

And in this case

H Φ |Λ = {a = (a λ ) λ : |a| ϕ = λ∈Λ (1 -|λ|)ϕ(log |a λ |) < ∞}.
Observe that the Carleson condition can be reformulated in terms of ϕ Λ :

M = sup λ ϕ Λ (λ) < +∞, (1.3)
i.e. ϕ Λ is bounded and admits a fortiori a harmonic majorant. We shall occasionally call M the constant associated with a sequence verifying the Carleson condition (such sequences are usually called H ∞ -interpolating sequences).

The conditions on ϕ in the theorem imply that there exist p, q ∈ (0, ∞) such that H p ⊂ H Φ ⊂ H q . In particular, the V 2 -condition implies the inclusion H Φ ⊂ H p for some p > 0. This V 2 -condition has a strong topological impact on the spaces. In fact, it guarantees that metric bounded sets are also bounded in the topology of the space (and so the usual functional analysis tools still apply in this situation; see [START_REF] Hartmann | Free interpolation in Hardy-Orlicz spaces[END_REF] for more on this and for further references). It was not clear whether this was only a technical problem or if there existed a critical growth for ϕ (below exponential growth ϕ(t) = e pt corresponding to H p spaces) giving a breakpoint in the behavior of interpolating sequences for H Φ .

We shall now turn to the case of big Hardy-Orlicz spaces. Let ϕ be a strongly convex function with associated Hardy-Orlicz space H Φ . Our central assumption on ϕ is the quasi-triangular inequality

ϕ(a + b) ≤ c(ϕ(a) + ϕ(b)) (1.4)
for some fixed constant c ≥ 1 and for all a, b ≥ t 0 . This condition obviously implies that H Φ is stable with respect to multiplication so that under this condition H Φ is an algebra. Observe that (1.4) is an equivalent formulation of the usual ∆ 2 -condition (1.2) (now for ϕ instead of Φ), and we will henceforth denote the condition (1.4) by ∆ 2 . Note that the ∆ 2 -condition obviously implies ∆2 .

Another condition on ϕ will be used. We say that ϕ satisfies the ∇ 2 -condition (see e.g. [START_REF] Leśniewicz | On linear functionals in Hardy-Orlicz spaces, I[END_REF]) if there exist d > 1 and t 0 > 0 such that

2ϕ(t) ≤ 1 d ϕ(dt), t ≥ t 0 ,
(see Section 2 for more on this).

The main result of this paper then reads as follows.

Theorem 1.2. Let ϕ : R -→ [0, ∞) be a strongly convex function satisfying the ∆ 2 -condition.

The following assertions are equivalent.

(a) Λ is a free interpolating sequence for

H Φ : Λ ∈ Int H Φ (b) There exists a positive measurable function w ∈ L ϕ (T) such that ϕ Λ ≤ P [w]. (c)
The trace space is given by

H Φ |Λ = l Φ := {(a λ ) : ∃0 ≤ w ∈ L ϕ (T) with log + |a λ | ≤ P [w](λ)}.
If moreover ϕ satisfies the ∇ 2 -condition then the above three conditions are equivalent to the following.

(d) There exists a constant C > 0 such that for any sequence of non-negative numbers (c λ ),

λ∈Λ c λ log 1 |B λ (λ)| ≤ C λ∈Λ c λ P λ (ζ) (L ϕ ) *
The standard examples of functions satisfying ∆ 2 and ∇ 2 are ϕ(t) = ϕ p (t) := t p for fixed p > 1 and t ≥ t 0 , or ϕ = ψ ε (t) := t log ε t for some fixed ε > 0 and t ≥ t 0 . Note that ϕ p satisfies both conditions also for p ∈ (0, 1] but this range is excluded by the definition of strongly convex functions.

The space L ϕ appearing in the theorem is the standard Orlicz space of measurable functions u such that ϕ • |u| ∈ L 1 (T). As a consequence of the ∆ 2 -condition (1.4) it turns out that its dual space (L ϕ ) * is in fact also an Orlicz space (associated with the complementary function of ϕ, see Section 2 for more comments and details).

It is interesting to note the analogy between condition (d) of this theorem and (1.1) which characterizes the interpolating sequences for the Nevanlinna class. Recall that (1.1) was not sufficient for the existence of a quasi-bounded harmonic majorant. In our situation however, any growth strictly faster than in the L 1 -situation suffices to eliminate the singular part of the measure defining the harmonic majorant (this is maybe not so surprising, there is a kind of "de la Vallée Poussin effect", see [RosRov85, Theorem 4.14]).

As in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF] we will investigate the problem of existence of harmonic majorants in the general setting. More precisely we are interested in the question when a Borel function defined on D admits a harmonic majorant P [w] with w ∈ L ϕ . The answer to this problem is given by the following result which involves the so-called Poisson balayage. Recall that the Poisson balayage of a finite positive measure µ in the closed unit disk is defined as

B(µ)(ζ) = D P z (ζ) dµ(z), ζ ∈ T.
Theorem 1.3. Let ϕ be a strongly convex function that satisfies the ∆ 2 -condition and the ∇ 2condition. If u is a non-negative Borel function on the unit disk then the following two assertions are equivalent.

Bµ (L ϕ ) * ≤ 1}.
It is again interesting to point out the analogy between this result and that given in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF]Theorem 1.4]. Note also that the corresponding condition (b) in that theorem does not give a quasi-bounded majorant but only a harmonic majorant, and a more subtle condition is needed to handle the case of quasi-bounded majorants (see [HMNT04, Theorem 1.6]).

The paper is organized as follows. In the next section we shall add some more comments on Orlicz and Hardy-Orlicz spaces. The sufficiency part of our main theorem has been given in [HMNT04, Theorem 9.1] and we refer the reader to that paper for a proof. The general structure of the proof of the necessity goes along the lines of the necessary part for the Smirnov class. However, the key result [HMNT04, Proposition 4.2] does not work any longer in our context. Note that it is precisely that proposition which shows that separated Blaschke sequences are interpolating for the Nevanlinna and Smirnov classes. We will actually discuss in some details in Section 6 an example showing that such a result cannot be expected in Hardy-Orlicz classes. The example shows that there are big Hardy-Orlicz spaces which are close to each other in a sense and for which there exist even separated Blaschke sequences that are interpolating for one space but not for the other one. For this reason we need a new idea which will be discussed in Section 3. The key is to factor the Blaschke product B Λ into two subproducts that behave essentially in the same way as B Λ (in a sense to be made precise). This will be achieved through a theorem by Hoffman. The trace space characterization is quite immediate and will be discussed in Section 4. Concerning harmonic majorants, we will discuss this problem in Section 5. We have already insisted on the analogy between our Theorem 1.3 and Theorems 1.4 and 1.6 in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF]. The techniques that apply in our situation are more classical than those used in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF]: we will use some duality arguments and a theorem by Mazur-Orlicz on positive linear functionals (which is essentially the Hahn-Banach theorem). The equivalence of (b) and (d) of Theorem 1.2 then follows from Theorem 1.3 (it suffices to consider positive measures µ supported on Λ).

Question. With our big Hardy-Orlicz spaces we narrow down the gap in the description of interpolating sequences from above: coming from the Smirnov class where the harmonic majorant must have an absolutely continuous measure, and so with an integrable weight w ∈ L 1 , we obtain now that the weight has to be in L ϕ (and we can get in a way arbitrarily close to L 1 , see also Section 6). Now, we have already indicated that the ∆ 2 -condition (1.4) implies a polynomial growth on ϕ. Observe that for classical Hardy spaces H p -where the Carleson condition characterizes the interpolating sequences -the defining functions are given by t -→ e pt . So one could ask what happens for defining functions with subexponential growth like e.g. ϕ(t) = e √ t

and whether there are Hardy-Orlicz spaces beyond H p , p > 0, for which the Carleson condition still characterizes the interpolating sequences.

Remark. To finish this introduction, we should add a comment on "small" Hardy-Orlicz spaces, more precisely, Hardy-Orlicz spaces contained between H ∞ and p<∞ H p . An example is given for Φ(t) = e t (note that this function does not define the ∆ 2 -condition, see (1.4)). With a reasonable definition of the associated small Hardy-Orlicz space (e.g. those holomorphic functions on D for which f Φ < ∞, where • Φ is defined in (2.1)), H ∞ is in the multiplier space of H Φ , which implies that H ∞ -interpolating sequences are interpolating for H Φ . On the other hand, as in [Har99, Lemma 2.1, Theorem 2.2] one shows that a free interpolating sequence for such a H Φ is necessarily H ∞ -interpolating.

(HARDY-) ORLICZ SPACES

For the background on the notions related to Hardy-Orlicz classes used in this section we refer to [START_REF] Rosenblum | Hardy classes and operator theory[END_REF], [START_REF] Leśniewicz | On linear functionals in Hardy-Orlicz spaces, I[END_REF] and [START_REF] Krasnosel | Convex functions and Orlicz spaces[END_REF].

Let ϕ be a strongly convex function. One way of introducing the Hardy-Orlicz class H Φ is to take all the functions f ∈ N + such that the subharmonic function ϕ(log + |f |) admits a harmonic majorant on D (see [RosRov85, Definition 3.15]). We have already introduced the notation Φ = ϕ • log keeping in mind that the function Φ is chosen in a way guaranteeing that Φ(|f |) is subharmonic.

Since f is in the Smirnov class, the fact that Φ(|f |) has a harmonic majorant is equivalent to (see [START_REF] Rosenblum | Hardy classes and operator theory[END_REF]Theorem 4.18])

J Φ (f ) = T Φ(|f (e it )|) dt = T ϕ(log |f (e it )|) dt < ∞,
so that H Φ can be defined as

H Φ = {f ∈ N + : J Φ (f ) = T ϕ(log |f (e it )|) dt < ∞}.
Observe that H Φ does not depend on the behaviour of ϕ for t ≤ t 0 whenever a t 0 ∈ R is fixed.

The integral expression J Φ is called a modular, and it does not define a metric on H Φ . A metric can be defined by d(f, g) = f -g Φ where

f Φ = inf{t > 0 : J Φ (f /t) ≤ t}, (2.1)
and H Φ equipped with this metric is a complete space.

In our situation, thanks to the ∆ 2 -condition, J Φ (af ) < ∞ for any a > 0 when J Φ (f ) < ∞ so that we do not need to distinguish between the Orlicz class, the Orlicz space and the space of finite elements (in the terminology of [START_REF] Leśniewicz | On linear functionals in Hardy-Orlicz spaces, I[END_REF]).

It is clear that if f ∈ H Φ then by the Riesz-Smirnov factorization f = Ih where I is an inner function and h is outer in

N + . Clearly J Φ (f ) = J Φ (h). Since h is outer in N + we have h(z) = exp( (ζ + z)/(ζ -z)w(ζ) dm(ζ))
for some real function w ∈ L 1 (T), so that |h| = exp(P [w]) in D which has boundary values exp(w) m-almost everywhere on T. Hence

J Φ (h) = T ϕ(log(exp w)) dm = T ϕ(w) dm ≥ T ϕ(w + ) dm = J ϕ (w + ),
where w + = max(0, w). In other words w + is in the Orlicz class L ϕ of measurable functions u such that J ϕ (u) < ∞.

Moreover lim t→∞ ϕ(t)/t = +∞, and L 1 = L ϕ 1 (recall that ϕ 1 (t) = t, t ≥ 1), so that by standard results on Orlicz spaces we get L ϕ ⊂ L 1 . In particular, if we now take any real-valued w ∈ L ϕ , then w ∈ L 1 , and we can define an outer function in the Smirnov class by

f w (z) = exp ζ + z ζ -z w(ζ) dm(ζ) .
For the same reasons as above the modulus of this function has boundary limits exp(w) a.e. on T and

J Φ (f w ) = T ϕ(w) dm = w≥0 ϕ(|w|) dm + w<0 ϕ(w) dm = ϕ(|w|)dm + w<0 ϕ(w) -ϕ(|w|) dm ≤ ϕ(0) + J ϕ (w) < ∞,
so that w gives rise to an outer function in H Φ .

Another important fact on Hardy-Orlicz classes that will be useful for us later is an estimate on point evaluations. Indeed, the maximal radial growth that we can attain for f ∈ H Φ is

|f (z)| ≤ Φ (-1) J Φ (f ) 1 -|z| .
This can be deduced from the subharmonicity of Φ(|f |) and the change of variable u -→ b z (u) (see also [Leś73, II.1.2]). Hence

log |f (z)| ≤ ϕ -1 c f 1 -|z| . (2.2)
For classical Hardy spaces H p one recovers from this the usual estimate on the point evaluation.

We will use the above estimate to show that certain separate sequences are not interpolating for "big" Hardy-Orlicz classes (see Section 6). Some more tools need to be introduced in the context of Orlicz spaces. In the above arguments, we did not need to appeal to topological considerations in L ϕ . Thus the definition of L ϕ as the set of measurable functions w for which ϕ • |w| ∈ L 1 was sufficient. Later on however we will have to consider in particular the dual and the bidual of L ϕ , and hence we need a proper norm in L ϕ . The alerted reader might have observed that ϕ is not a so-called N -function since for instance it does not vanish at 0 and hence it is not appropriated to define a topology on L ϕ . In the sequel, when considering L ϕ we will think of ϕ as being suitably replaced on [0, t 0 ] in order that the resulting function regarded as a function on [0, +∞) is convex and vanishing conveniently in 0. Then, in view of the convexity of ϕ the Orlicz space L ϕ equipped with the metric (2.1) (Φ replaced by ϕ) is a Banach space.

With the adjusted function ϕ we can define the so-called complementary function. It is defined by ϕ * (s) = max t≥0 {st -ϕ(t)} (it is also possible to define ϕ * using the "inverse" of the right derivative of ϕ). Since ϕ satisfies the ∆ 2 -condition, we get (L ϕ ) * = L ϕ * (see for instance [START_REF] Krasnosel | Convex functions and Orlicz spaces[END_REF] for this). Note also that (ϕ * ) * = ϕ.

We have also mentioned the ∇ 2 -condition. Recall that ϕ satisfies the ∇ 2 -condition if there are constants d > 1 and t 0 ≥ 0 such that for all t ≥ t 0 we have 2ϕ(t) ≤ ϕ(dt)/d. This condition is actually equivalent to the fact that ϕ * satisfies the ∆ 2 -condition ([KrRu61, Chapter 1, Theorem 4.2]) so that (L ϕ ) * * = (L ϕ * ) * = L ϕ * * = L ϕ . In particular, if the strongly convex function ϕ satisfies both the ∆ 2 -condition and the ∇ 2 -condition, then L ϕ is a reflexive space (and the converse is also true, see [Leś73, p.56]).

NECESSARY CONDITION

The central Proposition 4.1 of [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF] which claims that log(1/|B(z)|) is controlled by a (quasi-bounded) positive harmonic function for those z which are uniformly bounded away in the pseudohyperbolic metric from the zeros of B cannot be applied to our situation since the function defining the quasi-bounded majorant need not be in L ϕ . In Section 6 we will give examples of separated sequences for which the majorants are in no L ϕ whenever ϕ(t) ≥ t log ε t for t ≥ t 0 and ε > 0. To overcome this difficulty we need a more precise results which is based on a theorem by Hoffman (see [START_REF] Garnett | Bounded analytic functions[END_REF]p.

Λ = Λ 1 • ∪ Λ 2 and constants c, η > 0 such that log 1 |(B k ) λ (λ)| ≥ c log 1 |B λ (λ)| -η, (3.1) where B k = B Λ k = µ∈Λ k b µ and (B k ) λ = B Λ k \{λ} if λ ∈ Λ k , (B k ) λ = B k otherwise.
Proof. One should first note that the constants in Hoffman's theorem depend only on δ.

Let δ be the separation constant of the sequence Λ and fix Λ = Λ 1 • ∪ Λ 2 a partition of Λ obtained from Hoffman's theorem.

Pick λ ∈ Λ, say λ ∈ Λ 1 (so that in the following considerations we will assume k = 1). Then Λ \ {λ} = Λ 1 \ {λ} ∪ Λ 2 . A careful inspection of the proof of Hoffman's theorem (see e.g. the indicated reference) shows that we have

a|B Λ 1 \{λ} (z)| 1/b ≤ |B Λ 2 (z)| ≤ 1 a |B Λ 1 \{λ} (z)| b (3.2)
for z ∈ D \ µ∈Λ\{λ} D(µ, δ), and so in particular for λ.

We should pause here to add some comments on the proof of Hoffman's theorem given in [START_REF] Garnett | Bounded analytic functions[END_REF]. The fact that we take away λ implies a possible shift between the odd and the even indexed points in the strip T k (according to the terminology in [START_REF] Garnett | Bounded analytic functions[END_REF]) containing λ, and so the choice of Λ 1 and Λ 2 depends on λ. However, this is of no harm since these shifts mean in fact that we just add or take away at most one term in each layer T k . Since the layers T k are of pseudohyperbolic constant thickness, the terms added or subtracted correspond to an H ∞interpolating sequence the constant (in the sense of (1.3)) of which is bounded by that of an H ∞ -interpolating sequence in a radius with given separation constant. So in the estimates (3.2), the constant b is the same as in the splitting of the original sequence Λ = Λ 1 • ∪ Λ 2 whereas the constant a should be replaced by a different one, but independent on λ.

So log 1 |B Λ\{λ} (λ)| = log 1 |B Λ 1 \{λ} (λ)| + log 1 |B Λ 2 (λ)| ≤ log 1 |B Λ 1 \{λ} (λ)| + log 1 a|B Λ 1 \{λ} (λ)| 1/b = b + 1 b log 1 |B Λ 1 \{λ} (λ)| -log a,
and we can set c = (b + 1)/b and η = log a.

The cases λ ∈ Λ 2 , k = 2 are treated in a similar way.

We are now in a position to state the desired result for separated sequences.

Corollary 3.3. If Λ is a separated sequence that is interpolating for H Φ then there is a positive measurable function w with ϕ • w ∈ L 1 such that

log 1 |B λ (λ)| ≤ P [w](λ), λ ∈ Λ.
Proof. Suppose that Λ is a separated sequence. By Corollary 3.2, there exists a partition

Λ = Λ 1 • ∪ Λ 2 , λ ∈ Λ,
and constants c, η > 0 such that for all λ ∈ Λ log 1 |(B k ) λ (λ)| ≥ c log 1 |B λ (λ)| -η. (3.3)
Since Λ is moreover interpolating for H Φ there exist two functions f i ∈ H Φ , i = 1, 2, such that

f i |Λ i = 1, f i |(Λ \ Λ i ) = 0.
Now H Φ ⊂ N + , and we can factor f i in the following way

f i = B Λ\Λ i I i h i , i = 1, 2,
where I i is an inner function, h i is outer in H Φ :

h i (z) = exp 1 2π ζ + z ζ -z w i (ζ)dm(ζ) ,
and

(w i ) + ∈ L ϕ . Then for every λ ∈ Λ i 1 = f i (λ) = |f i (λ)| ≤ |B Λ\Λ i (λ)| • |h i (λ)|, so that log 1 |B Λ\Λ i (λ)| ≤ P [w i ](λ) ≤ P [(w i ) + ](λ).
Using (3.3), we get

log 1 |B λ (λ)| ≤ 1 c η + log 1 |B Λ\Λ i (λ)| ≤ P [ 1 c ((w i ) + + η)](λ).
The corollary then follows by setting w = 1 c ((w 1 ) + + (w 2 ) + + η) which is still in L ϕ .

Let us now switch to the necessary condition in the general situation. The central trick in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF] is to decompose the disk D into Whitney "cubes" that split the sequence into four pieces that are uniformly separated from each other in the pseudohyperbolic metric. This allows one to reduce the situation to the separated one.

We will repeat here the proof given in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF] for completeness adding the necessary changes for the situation of big Hardy-Orlicz spaces.

1 3 4 1 2 1 2 3 4 3 4 3 4 3 4 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 Figure 1: dyadic partition Let I n,k := {e iθ : θ ∈ [2πk2 -n , 2π(k + 1)2 -n )}, 0 ≤ k < 2 n , be the dyadic arcs and Q n,k := {re iθ : e iθ ∈ I n,k , 1 -2 -n ≤ r < 1 -2 -n-1 } the associated "dyadic squares".
The splitting of the sequence into four pieces will be done in the following way: Λ = 4 i=1 Λ i such that each piece Λ i lies in a union of dyadic squares that are uniformly separated from each other (see Figure 1). More precisely, set

Λ 1 = Λ ∩ Q (1) ,
where the family Q (1) is given by {Q 2n,2k } n,k (for the remaining three sequences we respectively choose {Q 2n,2k+1 } n,k , {Q 2n+1,2k } n,k and {Q 2n+1,2k+1 } n,k ). In order to avoid technical difficulties we count only those Q containing points of Λ. In what follows we will argue on one sequence, say Λ 1 . The arguments are the same for the other sequences.

By construction, for

Q, L ∈ Q (1) , Q = L, ρ(Q, L) := inf z∈Q,w∈L ρ(z, w) ≥ δ > 0,
for some fixed δ. In what follows, the letters j, k... will stand for indices in N 2 of the form (n, l), 0 ≤ l < 2 n . The closed rectangles Q j are compact in D so that Λ 1 ∩ Q j can only contain a finite number of points (they contain at least one point, by assumption). Therefore 0 < m j := min

λ∈Λ 1 ∩Q j |B λ (λ)|
(note that we consider the entire Blaschke product B λ associated with Λ \ {λ}). Take λ

1 j ∈ Q j such that m j = |B λ 1 j (λ 1 j )|. Assume now that Λ ∈ Int H Φ . So, since ∞ ⊂ H Φ |Λ, there exists a function f 1 ∈ H Φ such that f 1 (λ) =    1 if λ ∈ {λ 1 j } j 0 if λ ∈ Λ \ {λ 1 j } j . By the Riesz-Smirnov factorization we have (3.4) f 1 = B Λ\{λ 1 j } j I 1 g 1 ,
where I 1 is some inner function and g 1 is outer in H Φ . Hence there exists a weight w 1 ∈ L 1 such that g 1 = f w 1 and (w 1 ) + ∈ L ϕ . As in the proof of Corollary 3.3 we get

1 = |f 1 (λ 1 k )| ≤ |B Λ\{λ 1 j } j (λ 1 k )| • |g 1 (λ)|, so that log 1 |B Λ\{λ 1 j } j (λ 1 k )| ≤ P [w 1 ](λ 1 k ), k ∈ N. (3.5)
Replacing possibly w 1 by (w 1 ) + we can assume w 1 ≥ 0, so that P [w 1 ] is a positive harmonic function. By Harnack's inequality, there exists a constant c H ≥ 1 such that

1 c H P [w 1 ](λ 1 k ) ≤ P [w 1 ](z) ≤ c H P [w 1 ](λ 1 k ), z ∈ Q k ,
and in particular for every

λ ∈ Λ 1 ∩ Q k .
At this point we have to change the argument from [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF]. Instead of using Proposition 4.1 of that paper we have to invoke Corollary 3.3. By construction, the sequence {λ 1 j } j ⊂ Λ 1 is separated. Moreover, as a subsequence of an interpolating sequence it is also interpolating (cf. Remark 1.1). By Corollary 3.3 there exists a function v 1 ∈ L ϕ such that

log 1 |B {λ 1 j } j \{λ 1 k } (λ 1 k )| ≤ P [v 1 ](λ 1 k ), k ∈ N.
Recall that the weight v 1 can be supposed positive, so that P [v 1 ] is a positive harmonic function, and again by Harnack's inequality we get

P [v 1 ](λ 1 k ) ≤ c H P [v 1 ](λ ) for every λ ∈ Λ 1 ∪ Q k .
This together with (3.5) and our definition of λ 1 k give

log 1 |B Λ\{λ } (λ )| ≤ log 1 |B Λ\{λ 1 k } (λ 1 k )| = log 1 |B Λ\{λ 1 j } j (λ 1 k )| + log 1 |B {λ 1 j } j \{λ 1 k } (λ 1 k )| ≤ P [w 1 + v 1 ](λ 1 k ) ≤ P [c H (w 1 + v 1 )](λ ) for every λ ∈ Q k and Q k ∈ Q (1) . We set u 1 := c H (w 1 + v 1 ) which is clearly in L ϕ .
Construct in a similar way functions u i for the sequences Λ i , i = 2, 3, 4, and set u = 4 i=1 u i which is still in L ϕ by the quasi-triangular inequality (1.4). So, whenever λ ∈ Λ, there exists k ∈ {1, 2, 3, 4} such that λ ∈ Λ k , and hence

(3.6) log 1 |B λ (λ)| ≤ P [u k ](λ) ≤ P [u](λ).

THE TRACE SPACES

The proof of the trace space characterization is easier than that given in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF] for the Nevanlinna class.

In order to see that (c) in Theorem 1.2 implies free interpolation it suffices to observe that ∞ ⊂ l Φ and use Remark 1.1.

Assume now that Λ is of free interpolation. Suppose that (a λ ) λ ∈ H Φ |Λ and f ∈ H Φ is such that f (λ) = a λ , λ ∈ Λ. Let w ∈ L 1 be the representing measure of the outer part of f , i.e. f = If w , where I is inner and w + ∈ L ϕ . Obvioulsy log + |a λ | ≤ log + (exp(P [w](λ))) ≤ P [w + ](λ), and so (a λ ) ∈ l Φ .

Conversely, suppose that (a λ ) λ is such that there is a positive function w ∈ L ϕ with log

+ |a λ | ≤ P [w](λ). Since f w ∈ H Φ and log + |f w | = log |f w | = P [w] we have |a λ | ≤ |f w (λ)| for every λ ∈ Λ. Since Λ is of free interpolation, i.e. H Φ |Λ is ideal, there exists a function f 0 ∈ H Φ interpolating (a λ ) λ .

HARMONIC MAJORANTS

We begin by recalling the definition of the Poisson balayage: for a positive finite measure µ on the closed unit disk we set

B(µ)(ζ) = D 1 -|z| 2 |ζ -z| 2 dµ(z) = D P z (ζ) dµ(z). Let Har + ϕ = {P [w] : 0 ≤ w ∈ L ϕ }.
We will begin with an analog of [HMNT04, Proposition 6.1] and that does not require the ∇ 2 -condition.

Proposition 5.1. Let ϕ be a strongly convex function, and let µ be a positive finite Borel measure on T. Then B(µ) (L ϕ ) * < ∞ if and only if for every f ∈ Har + ϕ we have D h dµ < ∞. Moreover we have the following relation:

B(µ) (L ϕ ) * = sup D h dµ : h = P [w] ∈ Har + ϕ , w ϕ ≤ 1 .
So, this proposition furnishes a description of those positive finite measures on D that act against positive harmonic functions P [w] with w ∈ L ϕ . The proof of this result is short. It is essentially based on an application of Fubini's theorem and the definition of the norm in L ϕ by duality. We give it for completeness.

Proof.

sup D h dµ : h = P [w] ∈ Har + ϕ , w ϕ ≤ 1 = sup{ D T 1 -|z| 2 |ζ -z| 2 w(ζ) dm(ζ) dµ(z) : 0 ≤ w ∈ L ϕ , w ϕ ≤ 1} = sup{ T w(ζ) D 1 -|z| 2 |ζ -z| 2 dµ(z) dm(ζ) : 0 ≤ w ∈ L ϕ , w ϕ ≤ 1} = sup{ T w(ζ)B(µ)(ζ) dm(ζ) : w ∈ L ϕ , w ϕ ≤ 1} = B(µ) (L ϕ ) * = B(µ) L ϕ * .
In the above identities, we have also used the fact that µ is a positive measure so that its balayage is also positive. Hence it is enough to test against positive functions in L ϕ .

We are now in a position to prove Theorem 1.3. where B ϕ * = {µ : positive measure on D such that Bµ (L ϕ ) * ≤ 1}. We want to prove that u admits a harmonic majorant P [w] with w ∈ L ϕ .

We will begin as in [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF] by discretizing the problem (see in particular [HMNT04, Lemma 6.3]). For this, let again Q n,k be the dyadic cubes and z n,k the corresponding center. Fix

z * n,k ∈ Q n,k such that u(z * n,k ) ≥ (sup Q n,k u)/2.
We will set u n,k := u(z * n,k ) and ûn,k = sup Q n,k u. Let us check that if u satisfies (5.1) then there is a constant C such that whenever (c n,k ) is a finite sequence of non-negative coefficients with

c n,k P z n,k ϕ * ≤ 1, we get c n,k ûn,k ≤ C .
Indeed, setting µ := c n,k δ z * n,k we obtain a positive finite measure on D such that

B(µ)(ζ) ϕ * = D P z (ζ) dµ(z) ϕ * = c n,k P z * n,k ϕ * ≤ K c n,k P z n,k ϕ * ≤ K.
In the last estimate we have used the existence of a constant

K = K(δ) such that |b u (v)| ≤ δ implies that 1 K P v (ζ) ≤ P u (ζ) ≤ KP v (ζ)
for all ζ ∈ T and the fact that the Orlicz space L ϕ has the lattice property (which can be seen by using the dual representation of the norm). Now, using (5.1), we get

0 ≤ c n,k ûn,k ≤ 2 c n,k u n,k = 2 udµ ≤ 2CK So sup c n,
T P z n,k . So T ∈ E * = (L ϕ * ) * = L ϕ * * = L ϕ . Hence there exists w u ∈ L ϕ such that for all v = c n,k P z n,k we have T v = T vw u dm = c n,k P [w u ](z n,k ).
In particular for every n, k

0 ≤ ûn,k ≤ T P z n,k = P [w u ](z n,k ) ≤ P [(w u ) + ](z n,k ).
By Harnack's inequality the last term is bounded by P [c H (w u ) + ](z) for and every z ∈ Q n,k so that for every z

∈ Q n,k 0 ≤ u(z) ≤ ûn,k ≤ P [(w u ) + ](z n,k ) ≤ P [c H (w u ) + ](z).
Since this is true for all n, k and since clearly c H (w u ) + ∈ L ϕ we have achieved the proof.

AN EXAMPLE

In this section we will consider concrete separated sequences and check whether they are interpolating for Hardy-Orlicz spaces H Φ associated with Φ = Φ ε = ψ ε • log where ψ ε = t log ε t for some ε > 0 (even if this has no special meaning for our situation one could observe that for ε = 1 the space L ψ 1 is the Zygmund space L log L). Proposition 6.1. For every ε > 0 there exists a separated sequence Λ that is interpolating for H ψ δ whenever 0 < δ < ε but not for H ψε .

Proof. Fix ε > 0 and let λ

n,k = (1 -1/2 n )e k2πi/2 n , where n ∈ N * , k ∈ {-k n , . . . , k n } and k n := [2 n /(n log 1+ε n)]. Then n,k (1-|λ n,k |) n [1/(n log 1+ε n)] < ∞ so that Λ = {λ n,k } n,k satisfies the Blaschke condition.
Since Λ is separated we have for λ, µ ∈ Λ by standard estimates

log 1 |b µ (λ)| 1 -|b µ (λ)| (1 -|µ|)(1 -|λ|) |1 -µλ| 2 .
We will compute log(1/|B λ (λ)|) for λ = λ n,0 = 1 -1/2 n , n ∈ N, and show that this exceeds the maximal admissible growth in H Φε .

log 1 |B λ (λ)| = j≥1 k j l=-k j l =0 if j=n log 1 |b λ j,l (λ)| j≥1 k j l=-k j l =0 if j=n (1 -|λ|)(1 -|λ j,l |) |1 -λ j,l λ| 2 = 1 2 n j≥1 1 2 j k j l=-k j l =0 if j=n 1 |1 -λ j,l λ| 2 ≥ 1 2 n j≥2n 1 2 j k j l=-k j 1 |1 -λ j,l λ| 2 We get for j ≥ 2n 1 2 j k j l=-k j 1 |1 -λ j,l λ| 2 = k j l=-k j 1 2 j 1 |e l2πi/2 j -r n,j | 2 , (6.1)
where r n,j = (1 -1/2 n )(1 -1/2 j ). It can be noted that for fixed n, r n,j goes rapidly and increasingly to λ = 1 -1/2 n as j → +∞ (see Figure 2). The sum in 6.1 is a Riemann sum for

I j 1 |e iϑ -r n,j | 2 dϑ,
where I j = [-2πk j /2 j , 2πk j /2 j ] = [-2π/(j log 1+ε j), 2π/(j log 1+ε j)]. Then, since the function to be integrated is continuous, we get for fixed n and j ≥ 2n

1 2 j k j l=-k j 1 |1 -λ j,l λ| 2 I j 1 |e iϑ -r n,j | 2 dϑ
(for a better control on the constants it is possible to replace j ≥ 2n by j ≥ 2n + K for some fixed K > 0). rn,j

I j λ = 1 -1/2 n αn,j T Figure 2
It is well known (see e.g. [Gar81, p.13]) that

I j 1 -r 2 n,j |e iϑ -r n,j | 2 dϑ
α n,j π (α n,j is the angle indicated in Figure 2). As we have already mentioned 1 -r n,j ≥ 1 -λ = 1/2 n , and so for fixed n we get α n,j → 0 as j

→ +∞. So α n,j = 2α n,j /2 ∼ 2 tan(α n,j /2) = 2(|I j |/2)/(1 -r n,j ) ∼ |I j |/(1 -λ) = 2 n |I j | = 4π2 n /(j log 1+ε j). Hence log 1 |B λ (λ)| ≥ 1 2 n j≥2n 1 1 -r 2 n,j k j l=-k j 1 2 j 1 -r 2 n,j |e l2πi/2 j -r n,j | 2 1 2 n j≥2n 1 1 -r 2 n,j I j 1 -r 2 n,j |e iϑ -r n,j | 2 dϑ 1 2 n j≥2n 1 1 -r 2 n,j 4 • 2 n j log 1+ε j = j≥2n 1 1 -r 2 n,j 4 j log 1+ε j Moreover j ≥ 2n, so that 1-r 2 n,j 1-r n,j = 1 2 n + 1 2 j -1 2 n+j 1 2 n . Using 1-|λ| = 1-λ = 1/2 n and so n = log(1/(1 -|λ|))/ log 2 we get log 1 |B λ (λ)| 2 n j≥2n 4 j log 1+ε j ∼ 2 n 4 log ε (2n) ∼ 4 1 -|λ| 1 log ε n ∼ 4 1 -|λ| 1 log ε log 1 1-|λ| . (6.2)
Let us check that this is not compatible with free interpolation in H Φε . Suppose to the contrary that Λ is an interpolating sequence for H Φε . Then, by Theorem 1. Note that ψ ε (u/ log ε u) ∼ u as u → +∞, so that ψ -1 ε (u) ∼ u/ log ε u. Hence, setting u = 1/(1 -|z|) we get for z sufficiently close to T,

P [w](z) c f 1 1 -|z| 1 log ε c f 1-|z| .
Since the right hand side of the last inequality is negligible with respect to the right hand side of (6.2) we have reached a contradiction. So, the sequence Λ is not interpolating for H Φε and hence for no H Φ with Φ = ϕ • log and ϕ a stronly convex function with ϕ(t) ≥ ψ ε (t), t ≥ t ε .

In order to finish the proof, we check that the above constructed sequence is interpolating for H Φ δ whenever 0 < δ < ε. Since Λ is separated it is of course interpolating for the Smirnov (and Nevanlinna) class, see [HMNT04, Corollary 1.9], which means that there is a function u ∈ L 1 (T) such that log(1/|B λ (λ)|) ≤ P [u](λ). (6.3) It is known that the function u can be chosen explicitly by: u = c 0 λ∈Λ χ I λ (see [START_REF] Hartmann | Interpolation in the Nevanlinna and Smirnov classes and harmonic majorants[END_REF]Proposition 4.1] and also [START_REF] Nicolau | Smallness sets for bounded holomorphic functions[END_REF]p.124]), the interval I λ = {e it ∈ T : |targ λ| ≤ c(1 -|λ|)} appearing in the above formula being the so-called Privalov shadow. It turns out that in the present situation this intuitive candidate for u is the right one to get a harmonic majorant. In other words, we have to check that u ∈ L ψ δ , 0 < δ < ε, and this will finish the proof. So, let us suppose that the constant c in the definition of I λ is adapted in such a way that I λ n,k and I λ n,k+1 touch without overlap (this is not really of importance). We then consider the shadow of the stage n: j=1,...,kn I λ n,j = [-1/2 n -1/(n log 1+ε n), 1/(n log 1+ε n) + 1/2 n ] which is essentially the interval [-1/(n log 1+ε n), 1/(n log 1+ε n)]. So the function u is essentially equal to k on [-1/(k log 1+ε k), -1/((k +1) log 1+ε (k +1))[∪]1/((k +1) log 1+ε (k +1)), 1/(k log 1+ε k)]. In order that ψ δ • u ∈ L 1 it thus suffices (using some Fubini) that k≥1 ψ δ (k + 1) -ψ δ (k) k log 1+ε k < ∞, and this holds for 0 < δ < ε.

If one wishes to get closer to L 1 , one could e.g. consider strongly convex functions ϕ(t) = t log ε log t by choosing k j = 2 j /(j log j log 1+ε log j).

We wanted to emphasize in this section the behaviour of separated Blaschke sequences since these were already interpolating for the Smirnov class. Our examples make it clear that the situation is much more delicate in big Hardy-Orlicz spaces.

Another and of course easier way of producing examples of interpolating sequences for our spaces is to take two H ∞ -interpolating sequences that approach each other in a critical way: if Λ 1 = {λ n } n is such an H ∞ -interpolating sequence, take µ n = λ n close to λ n and define Λ 2 = {µ n } n . Then, for B = B Λ 1 ∪Λ 2 we get log(1/|B λn (λ n )|) log(1/|b λn (µ n )| =: η n , so that suitable choices of (η n ) n yield interpolating sequences for some big Hardy-Orlicz spaces which are not interpolating for others (see e.g. [HMNT04, Example 9.2] and [START_REF] Hartmann | Interpolating sequences for holomorphic functions of restricted growth[END_REF] for such constructions).

  (a) Λ is a free interpolating sequence for the Smirnov class N + : Λ ∈ Int N + . (b) ϕ Λ admits a quasi-bounded harmonic majorant, i.e. there exists a positive weight w ∈ L 1 (T) such that ϕ Λ (λ) ≤ P [w](λ).

( a )

 a There exists a function w ∈ L ϕ such that u(z) ≤ P [w](z) for all z ∈ D. (b) There exists a constant C ≥ 0 such that sup µ∈B ϕ * u(z) dµ(z) ≤ C, where B ϕ * = {µ positive measure on D:

  411]): Theorem 3.1 (Hoffman's theorem). For 0 < δ < 1 there are constants a = a(δ) and b = b(δ) such that the Blaschke product B(z) with zero set Λ has a nontrivial factorization B = B 1 B 2 such that a|B 1 (z)| 1/b ≤ |B 2 (z)| ≤ 1 a |B 1 (z)| b for every z ∈ D \ λ∈Λ D(λ, δ) where D(λ, δ) = {z ∈ D : |b λ (z)| < δ} is the pseudohyperbolic disk centered at λ with radius δ. Corollary 3.2. Let Λ = {λ n } n ⊂ D be a separated Blaschke sequence. Then there exists a partition

  Proof of Theorem 1.3. Condition (b) is clearly necessary. It suffices indeed to plug the estimate u ≤ P [w] into the chain of equalities in the previous proof: if u ≤ h = P [w] for some 0 ≤ w ∈ L ϕ then 0 ≤ D udµ ≤ D hdµ ≤ w ϕ Bµ ϕ * (Hölder's inequality for Orlicz spaces, see [KrRu61, Theorem 9.3]). Let us consider the sufficiency. So suppose that there exists a constant C ≥ 0 such that sup µ∈B ϕ * u(z) dµ(z) ≤ C, (5.1)

  2, there exists a positive function w ∈ L ψε (T) such that log(1/|B λ (λ)|) ≤ P [w](λ) for every λ ∈ Λ. As we have already discussed in Section 2, f (z) = exp( (ζ + z)/(ζ -z)w(ζ) dm(ζ)) is an outer function in H Φε . Hence P [w](z) = log |f (z)| ≤ ψ -1 ε c f 1 -|z| .

  k ûn,k : c n,k ≥ 0 for all n, k andc n,k P z n,k ϕ * ≤ 1 ≤ 2CK,in other words, for all positive finite sequences (c n,k ) we havec n,k ûn,k ≤ 2CK c n,k P z n,k ϕ * .Let E be the closure in L ϕ * of the R-space generated by the Poisson kernels P z n,k for all n, k (which in fact corresponds to L ϕ * ). By the theorem of Mazur-Orlicz (see e.g. [Pe67, Chapter 2, Proposition 2.2]), there exists a linear continuous mapping T : E -→ R with same norm 2CK such that

ûn,k ≤

Acknowledgements: K. Dyakonov reminded me that Theorem 3.1 is due to Hoffman.


Pierre Guillou -Cri Mines

Compiling Image Processing Applications for Many-Core Accelerators

detect geometrical structures in an image mathematical morphology: image analysis theory and technique based on lattices theory

Mathematical Morphology Base Operators

  ⊗ parameter, 1 input image) binary (pixel ⊗ pixel, 2 input images) + -× ÷ min max = & | ∼

Image processing applications Relative energy consumption

Future Work

Other programming models:

Pthreads/OpenMP on compute clusters, communication library between clusters OpenCL via local memory pagination Improve data-parallelism to take better advantage of the curent architecture Implement more complex algorithms: watershed, arrow, labelling, minima, . . .


Nelson Lossing

Pierre Guillou

Mehdi Amini

François Irigoin

Keywords: Source-to-Source Compiler, Data Dependence Graph, C Language, Declaration Scheduling

Program optimizations, transformations and analyses are applied to intermediate representations, which usually do not include explicit variable declarations. This description level is fine for middle-ends and for source-to-source optimizers of simple languages. However, the C language is much more flexible: variable and type declarations can appear almost anywhere in source code, and they cannot become implicit in the output code of a C source-to-source compiler. We show that declaration statements can be handled like the other statements and with the same algorithms if new effect information is defined and handled by the compiler, such as writing the environment when a variable is declared and reading it when it is accessed. This extension has been used for several years in our PIPS framework and has remained compatible with its new developments such as offloading compilers for GPUs and coprocessors.

From Data to Effects Dependence Graphs: Source-to-Source Transformations for C 1 Introduction

Program optimizations, transformations and analyses are applied to intermediate representations, traditionnaly built with basic blocks of three-address code and a control flow graph. They usually do not include explicit variable declarations, because these have been processed by a previous pass and have generated constant addresses in the static area or offsets for stack allocations. This description level is used, for instance, in the Optimization chapter of the Dragon Book [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF]. It is fine for middle-ends and for source-to-source optimizers of simple languages, such as Fortran77, that separate declarations from executable statements. However, the C language, especially its C99 standard [11], is much more flexible. Variable and type declarations, which include expressions to define initial values and dependent types, can appear almost anywhere in the source code. And they cannot become implicit in the output code of a C source-to-source compiler, if the output source code is to be as close as possible to the input code and easy to read by a programmer. Thus source-to-source compiler passes that schedule statements must necessarily deal with type and variable declarations.

However, these statements have none or little impact in terms of the classical def-use chains or data dependence graphs [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF][START_REF] Kennedy | Optimizing Compilers for Modern Architectures: A Dependence-based Approach[END_REF][START_REF] Wolfe | High Performance Compilers for Parallel Computing[END_REF], which deal only with memory accesses. As a consequence, C declarations would be (incorrectly) moved away from the statements that use the declared variables, with no respect for the scope information. Is it possible to fix this problem without modifying classical compilation algorithms?

We have explored three main techniques applicable for a source-to-source framework. The first one is to move the declarations at the main scope level. The second one is to mimic a conventional binary compiler and to transform typedef and declaration statements into memory operations, which is, for instance, what is performed in Clang. The third one is to extend def-use chains and data dependence graphs to encompass effects on the environment and on the set of types.

In Section 2, we motivate the use of C source-to-source compilation, and we show, with an example, how Allen&Kennedy (or loop distribution) Algorithm misbehaves when classical use-def chains and data dependence graphs are used in the presence of declaration statements. We then provide in Section 3 some background information about the semantics of a programming language, and about automatic parallelization. We review in Section 4 the standard use-def chains and data dependence graphs and introduce in Section 5 and Section 6 our proposed extension, the Effects Dependence Graph (FXDG), to be fed to existing compilation passes. We look at its impact on them in Section 7 and observe that the new effect arcs are sometimes detrimental and must be filtered out, or insufficient because the scheduling constraints are not used. We then conclude and discuss future work.

Motivation

Why use source-to-source compilation? C source-to-source compilers have several key advantages over assembler or low-level intermediate compilers: the output code is more readable and can be easily compared to the input. Moreover, a C code is stable and portable; therefore maintenance is easier, so that the C language is also often used as an intermediate language [START_REF] Kreinin | C as an intermediate language[END_REF].

Practical Example

Consider the C99 for loop example in Listing 1. This code contains in its loop body declarations for a type and a variable at Lines 6-7. When loop fission/distribution [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF][START_REF] Wolfe | High Performance Compilers for Parallel Computing[END_REF] is applied blindly onto this loop, the typedef statement and the variable declaration are also distributed, as shown in Listing 2.

The loop distribution algorithm relies on the Data Dependence Graph to detect cyclic dependencies between the loop body statements. Yet the type and variable declarations carry no data dependencies towards the following statements or the next iteration, thus causing an incorrect distribution. The Data Dependence Graph (DDG) of Listing 1 is represented Figure 1. According to this DDG, no dependence exists between the type declaration statement (typedef This example highlights the inadequacy of the Data Dependence Graph for some classic transformations when applied on C99 source code. Should we design a new algorithm or expand the Data Dependence Graph with new precedence constraints?

Related Work

We did not find any related work as recent research compilers are dealing either with restricted input, e.g. polyhedral compilers and static control parts (SCoPs [4]), a good example being Pluto [START_REF] Bondhugula | A Practical Automatic Polyhedral Parallelizer and Locality Optimizer[END_REF], or are using robust parsers such as Clang [START_REF]Clang: A C Language Family Frontend for LLVM[END_REF]. The latter delivers low-level intermediate representations, such as the three-address code LLVM IR [START_REF] Lattner | LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation[END_REF], from which regenerating a higher-level source code is complex. Other source-to-source research compil-ers simply do not support the C99 standard: among them, Oscar [START_REF] Kasahara | Automatic Coarse Grain Task Parallel Processing on SMP Using OpenMP[END_REF][START_REF] Obata | Hierarchical Parallelism Control for Multigrain Parallel Processing[END_REF] and Cetus [START_REF] Lee | Cetus -An Extensible Compiler Infrastructure for Source-to-Source Transformation[END_REF].

Background and Notations

We have based our work on some code transformation passes of the PIPS compiler and on its high-level intermediate representation. PIPS is a source-to-source compilation framework [START_REF] Irigoin | Semantical interprocedural parallelization: an overview of the PIPS project[END_REF] developed at MINES ParisTech. Aiming at automatic code parallelization, it features a wide range of analyses over Fortran and C code. To carry out these analyses, PIPS relies on the notion of effects, which reflect how a code statement interacts with the computer memory. To better understand the benefits of this approach, we have to introduce several basic concepts about the semantics of procedural programming languages.

In Fortran and C, variables are linked to three different concepts: an Identifier is the name given to a specific variable; a Memory Location is the underlying memory address, usually used to evaluate Identifier; and a Value is the piece of data effectively stored at that memory address. For instance, a C variable declaration such as int a; maps an Identifier to a Memory Location, represented by &a, and usually allocated in the stack. To link these concepts, two functions are usually defined: the Environment function ρ takes an Identifier and yields some corresponding Memory Locations; and the Memory State or Store function σ gives the Value stored in a Memory Location. With the above, a Statement S can be seen as transforming a Store and Environment (in case of additional declarations) into another. We call memory effects of a Statement S the set of Memory Locations whose Values have been used or modified during the execution of S. Effects E are formally defined as a function taking a Statement and returning a mapping between a pre-existing Memory State and a set of Memory Locations. Equation 1 to Equation 4 provide the formal representation of the concepts defined above.

ρ ∈ Env = Identifier -→ Location (1) σ ∈ Store = Location -→ V alue (2) S : Store × Env -→ Store × Env (3) E : Statement -→ (Store × Env -→ P(Location)) (4)
Effects are divided into two categories: READ effects R S represent a set of Memory Locations whose Values are accessed, but not modified, whereas WRITE effects W S represent Memory Locations whose Values are written during the execution of S on a given Memory State. A statement's READ and WRITE effects, usually over-approximated for safety by static analyses, satisfy specific properties [START_REF] Irigoin | Polyèdres et Compilation[END_REF], which can be used to show that Bernstein's conditions [START_REF] Bernstein | Analysis of Programs for Parallel Processing[END_REF] are sufficient to exchange two statements without modifying their combined semantics. This is also the foundation of automatic loop parallelization.

These READ and WRITE effects can be refined into IN and OUT effects to specify the Values that "really" have an impact on the semantics of the statement (IN), or are used by its continuation (OUT). These are similar to the live-in and live-out variables [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF].

The data structure used in PIPS for modelling effects is represented in Listing 3. More precisely, PIPS effects associate an action -READ or WRITEto a so-called memory cell, which represents a reference and can be a variable memory address, a combination of an array pointer and an index, or a struct and one of its fields. The unit keyword means that no additional information is carried by the corresponding field.

Many analysis and transformation passes in PIPS are based on effects, called effects for simple scalar variables, or regions for arrays. In particular, effects are used to build use-def chains and the Data Dependence Graph between statements. More information about effects and regions can be found in [START_REF] Creusillet | Array Region Analyses and Applications[END_REF].

Data Dependence Graph

The Data Dependence Graph is used by compilers to reschedule statements and loops. A standard Data Dependence Graph [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF][START_REF] Wolfe | High Performance Compilers for Parallel Computing[END_REF] exposes essential constraints to prevent incorrect reordering of operations, statements, or loop iterations. A Data Dependence Graph is composed of three different types of constraints: flow dependence, anti-dependence and output dependence.

Note that the Data Dependence Graph is based on memory read and write operations, a.k.a. uses and definitions. So, to take into account the implicit mechanisms used by the compiler, implicit memory accesses have to be added to obtain consistent READ and WRITE effects. We want to keep these new accesses implicit to make further analyses and transformations easier, and to be able to regenerate a source code as close as possible to the original. Standard high-level use-def chains and DDG are unaware of these implicit dependencies. However, they are key when generating distributed code [START_REF] Wolfe | High Performance Compilers for Parallel Computing[END_REF] or when isolating statements [START_REF] Guelton | Beyond Do Loops: Data Transfer Generation with Convex Array Regions[END_REF].

Limitations

The problem with the standard Data Dependence Graph is that the ordering constraints are only linked to memory accesses. A conventional Data Dependence Graph does not take into account the address of the variables, and even less the declaration of new types, even when they are necessary to compute a location. In fact, when the C language, especially the C99 standard, is considered, many features imply new scheduling constraints for passes using the Data Dependence Graph:

Declarations anywhere is a new feature of C99, also available in C ++ . This feature implies for a source-to-source compiler to consider these declarations and to regenerate the source code with the declarations at the right place within the proper scope. Dependent types, especially variable-length arrays (VLA), are a new way to declare dynamic variables in C99. The declarations cannot be grouped at the same place, regardless of precedence constraints. User-defined types such as struct, union, enum or typedef can also be defined anywhere inside the source code, creating dependences with the following uses of this type to declare new variables.

Workarounds

A possible approach for solving these issues in a source-to-source compiler is to mimic the behavior of a standard compiler that generates machine code with no type definitions or memory allocations. In this case, we can distinguish two solutions.

The first one works only on simple code, without dependent types. The declarations can be grouped at the expense of stack size and name obfuscation at the beginning of the enclosing function scope.

The second one is more general. The memory allocations inserted by the binary compiler can be reproduced. Analyses and code transformations are performed on this low-level IR. Then the source code is regenerated without the low-level information.

Flatten Code Pass Code flattening is designed to move all the declarations at the beginning of functions in order to remove as many environment extensions (introduced by braces, in C) as possible and to make basic blocks as large as possible. So all the variables end up in the function scope, and declaration statements can be ignored when scheduling executable statements.

Some alpha-renaming must also be performed during this scope modification: if two variables share the same name but have been declared in different scopes, new names are generated, considering the scope, to replace the old names while making sure that two variables never have the same name.

This solution is easy to implement and can suit a simple compiler.

The result of Listing 1 after calling flatten code is visible on Listing 41 . Listing 5 is the result of a loop distribution performed on Listing 4. Note that the second loop is no longer parallel and that a privatization pass is necessary to reverse the hoisting of the declaration of x. However, this solution only works on simple programs without dependent types, because dependent types imply a flow dependence between statements and the declarations. As a consequence, the declarations cannot be moved up anymore.

Besides, even in simple programs, the operational semantic of the code can be changed. In our above example, flatten code implies losing the locality of the variable x. As a consequence, the second loop cannot be parallelized, because of the dependence to the shared variable x. Without flatten code, the variable x is kept in the second loop, which remains parallel.

Furthermore, code flattening can produce an increase in stack usage. For instance, if a function has s successive scopes that declare and use an array a of size n, the same memory space can be used by each scope. Instead, with code flattening, s declarations of different variables a1, a2, a3. . . are performed, so s×n memory space is used.

Code flattening also reduces the readability of the code, which is unwanted in a source-to-source compiler. The final code should be as close as possible to the original code.

Frame Pointer Another solution is to reproduce the assembly code generated by a standard compiler, e.g. gcc. A hidden variable, called the current frame pointer (fp), corresponds to the location where the next declared variable is allocated. At each variable declaration, the value of this hidden variable is updated according to the size of the variable type. In x86 assembly code, the stack base pointer ([e|r]bp) with an offset is used. Moreover, for all user-defined types, hidden variables are also added to hold the sizes of the new types. In this way, the source-to-source compiler performs like a binary compiler.

However, this method implies to add many hidden variables. All of these hidden variables must have a special status into the internal representation of the source-to-source compiler. Besides, this solution adds constraints between declarations that do not exist. Since all declarations depend on the frame pointer, which is modified after each declaration, no reordering between declarations is legal, for instance. With the special status of these new variables, the generation of the new source code is also modified and can be much harder to perform.

Listing 7 illustrates a possible resulting informal internal representation inside a source-to-source compiler. On the corresponding Data Dependence Graph, the declaration of the type mytype, the declaration of Variable x and the initialization of x and b are strongly connected, and therefore will not be separated when applying loop distribution.

Nevertheless, the regeneration of a high-level source code with the new internal representation has to be redesigned completely so as to ignore the hidden variables while considering the type and program variable declarations. Thus this solution is not attractive for a source-to-source compiler.

Effects Dependence Graph

Instead of modifying the source code or adding hidden variables, we propose to use the code variables, including the type variables, to model the transfor-mations of the environment and type functions. For this purpose, we extend the memory effects analysis presented in Section 3 by adding an environment function for read/write on variable memory locations, and a type declaration function for read/write on user-defined types. By extending the effects analysis with two new kinds of reads and writes, we define a new dependence graph that extends the standard Data Dependence Graph. We name it the Effects Dependence Graph (FXDG).

Environment function

The effects on the environment function ρ, read and write, are strictly equivalent to the effects on the store function σ, a.k.a. the memory. A read is an applicability of ρ, which returns the location of an identifier. A write updates the function ρ and maps a newly declared identifier to a new location. So when a variable is declared, a new memory location is allocated, which implies a write effect on the function ρ. Its set of bindings is extended by the new pair (identifier, location). Similarly, when a variable is accessed within a statement or an expression, be it for a read or a write, the environment function ρ is used to obtain the corresponding location, needed to update the store function σ. So effects on the function ρ track all accesses and modifications of ρ, without ever taking into account the value that σ maps to a location. Type function τ To support memory allocation, the type function τ maps a type identifier to the number of bytes required to store its values. It is used for all user-defined types, be they typedef, struct, union or enum. The effects on τ , read and write, correspond to apply and update operations. When a new user-defined type is declared, τ is updated with a new pair (identifier, size). This is modeled by a write effect on τ . When a new variable is declared with a user-defined type, the type function τ is applied to the type identifier, i.e., a read effect occurs.

The traditional read and write effects on the store function, a.k.a. memory, are thus extended in a natural way to two other semantic functions, the environment and the type functions. The common domain of these two new functions is the identifier set, for variables and user-defined types. In practice, the parser uses scope information to alpha-rename all identifiers. The traditional memory effects are more difficult to implement because they map locations and not identifiers to values. Static analyses should be based on an abstract location domain. However, a subset of this domain is mapped one-to-one to alpha-renamed identifiers. Thus, the three different kind of effects can be considered as related to maps from locations to some ranges, which unify their implementation.

The advantage of this solution is the preservation of the original source code, unlike the above flatten code solution. Also, no new variable is introduced to transform effects on the environment and types into effects on store, as is shown by the generated assembly code. Moreover, no modification is required for the source code prettyprinter. Furthermore, loop parallelization can be properly performed using this new dependence graph.

The new effects can be implemented in two different ways, with different impacts on the classical transformations based on the Data Dependence Graph.

The first possibility is to consider separately the effects on stores, environments and types, and to generate use-def chains and dependence graphs for each of them, and possibly fusing them when it is necessary.

The second possibility is to colorize the effects and then use a unique Effects Dependence Graph to represent the arcs due to each kind of functions. Passes based purely on the Data Dependence Graph have to filter out arcs not related to the store function. Merging different dependence graphs This first approach creates a specific dependence graph for each kind of effects, a Data Dependence Graph, an Environment Dependence Graph and a Type Dependence Graph. To obtain the global Effects Dependence Graph required as input by passes such as loop distribution, these three graphs are fused via a new pass in PIPS.

As an example, PIPS manages resources for effects on variable values and could manage two new resources for effects on environment and for effects on types. With three effect resources, it is now possible to generate three different dependence graphs, one for each of our effect resources: a Data Dependence Graph, an Environment Dependence Graph and a Type Declaration Dependence Graph. The union of the three different dependence graphs of the example in Listing 1, the total Effects Dependence Graph, is presented in Figure 2.

With these new dependence graphs, the loop distribution algorithm produces the expected Listing 8. The loops can then be properly parallelized, as shown in Listing 9. Since we have a dependence graph for each kind of effects, we can independently select which dependence graph we need to compute or use. Still, at the implementation level, these independent dependence graphs also imply to launch three different analyses and to fuse their results with a fourth pass to obtain the Effects Dependence Graph for loop distribution.

A unique dependence graph with three colors This second approach consists in extending the current use-def chains and data dependence graph with the different kinds of effects. On this Effects Dependence Graph, some colorization is used to distinguish between the different kinds of effects: data values, memory locations and types.

With this approach, the data structure for effects in PIPS is refined with information about the action kind as shown in Listing 10. Since the change is applied at the lowest level of the data structure definition, the existing passes dealing with reads and writes are left totally unchanged. The Effects Dependence Graph for Listing 1 is identical to the result of the first approach (Figure 2). This implementation leads to the same output of loop distribution and loop parallelization than the three-graphs approach (see Listing 8). Besides, only one dependence graph is generated; so we do not need to manage three different ones, plus their union.

However, since we only have one global dependence graph 2 , all the transformations that use the data dependence graph have access to all the dependence constraints on all kinds of effects. Sometimes, these new constraints might pre-Transformations That Should Filter the FXDG When the legality of a pass is linked to the values reaching a statement, the new arcs, which embody address or type information, are not relevant. For instance, a forward substitution pass uses the use-def chains, also known as reaching definitions, to determine if a variable value is computed at one place or not. Additional arcs due to the environment are not relevant and should not be taken into account.

When applying Forward Substitution to the loop body of Listing 8, the Read after Write Environment dependency between the statements mytype x; and b[i] = x; prevents the compiler from subtitution, x by i. Filtering out the Environment and Type Declaration effects is, in this case, necessary to retrieve the expected behavior.

The Isolate Statement pass [START_REF] Guelton | Beyond Do Loops: Data Transfer Generation with Convex Array Regions[END_REF] is used to generate code for accelerators with private memories such as most GPUs and FPGA-based ones. The purpose is to transform one initial statement S into three statements, S1, S2 and S3. The first statement, S1, copies the current values of locations used by S into new locations. The second statement, S2, is a copy of statement S, but it uses the new locations. Finally, the third statement, S3, copies the values back from the new locations into the initial locations. This S2 has no impact per se on the initial store and can be performed on an accelerator. Statement S1 is linked to the IN regions of Statement S, while Statement S3 is linked to the OUT regions of Statement S. Since only values are copied, it is useless to count variables declarations as some kind of IN effect, although type information may be needed to declare the new variables, especially if dependent types are used.

Transformations That Need Further Work Some transformations do not use scheduling information, but the standard implementations may not be compatible with type declarations or dependent types.

For instance, the pass that moves declaration statements at the beginning of a function in PIPS (flatten code) does not use data dependence arcs. When dependent types or simply variable-length arrays are used in typedef or variable declaration statements, scheduling constraints exist and must be taken into account. A new algorithm is required for this pass, and the legality of the existing pass can be temporarily enforced by not dealing with codes containing dependent types.

In the same way, loop unrolling, full or partial, does not modify the statement order and does not take any scheduling constraint into consideration. However, its current implementation in PIPS is based on alpha-renaming and declaration hoisting to avoid multiple scopes within the unrolled loop or the resulting basic block. This is not compatible with dependent types, and non-dependent types are uselessly renamed like ordinary variables.

Conclusion

C99 is a challenge for source-to-source compilers that intend to respect as much as possible the scopes defined by the programmers because of the flexibility of the type system and the lack of rules about declaration statement locations. We show that some traditional algorithms fail because the use-def chains and the data dependence graph do not carry enough scheduling constraints. We explore three different ways to solve this problem and showed that adding arcs for transformations of the current type set and environment was the most respectful for the original source code and existing passes. The new kinds of read and write effects fit easily in the traditional use-def chains and data dependence graph structures. Passes that need the new constraints are working right away when fed the effects dependence graph. Some passes are hindered by these new constraints and must filter them out, which is very easy to implement. Finally, some other passes are invalid for C99 declarations, but are not fixed by using the Effects Dependence Graph because they do not use scheduling constraints.

The newer C11 standard [12], released in 2011 by the ISO/IEC as a revision of C99, is more conservative in terms of disruptive features. In some ways, C11 is actually a step backwards: some mandatory C99 features have become optional. Indeed, due to implementation difficulties in compilers, Variable-Length Arrays (VLA) support is not required by the C11 standard. With VLAs out of the scope, declarations can more easily be moved around without modifying the code semantic. The solution proposed in this article is still valid for C11 code.

Listing 2 :

 2 After (incorrect) loop distribution of Listing 1 int mytype;), the variable declaration (mytype x;) and the two statements referencing variable x (x = i; b[i] = x;).

Fig. 1 :

 1 Fig. 1: Data Dependence Graph of Listing 1

  effects = effects : effect * ; effect = cell x action x [...] ; cell = reference + [...] ; reference = variable : entity x indices : expression * ; entity = name : string x [...] ; expression = syntax ; syntax = reference + [...] ; action = read : unit + write : unit ; Listing 3: READ/WRITE effects syntax in PIPS

Listing 6 :

 6 Initial code example from Listing 1 void example () { int fp =0; a = fp ; fp -= 10* $int ; b = fp ; fp -= 10* $int ; { & i = fp ; fp -= $int ; for (*(& i )=0;*(& i ) <=9;*(& i )+=1) { a [*(& i )] = *(& i ); $mytype = $int ; & x = fp ; fp -= $mytype ; *(& x ) = *(& i ); b [*(& i )] = *(& x );} fp += $mytype ;} fp += $int ; return ; } Listing 7: IR with frame pointer of Listing 6: sizeof(xxx) are represented as $xxx and dynamic adresses as &x

Fig. 2 :

 2 Fig. 2: Effects Dependence Graph for Listing 1. (full arc = data dependence (W, R), dashed arcs = environment dependence (WE, RE), dotted arcs = type dependence (WT, RT))

Generated variables are really new variables because they have different scopes.

We can also use a PIPS property to compute and use either the Data Dependence Graph or the Effects Dependence Graph, but it is hard to maintain consistency when properties are changed.

vent some optimizations, even though these constraints are always correct. These issues are studied in the next section.

Impact on Transformations and Analyses

The introduction of the Effects Dependence Graph allows source-to-source compilers to better support the C99 specification. However, not all classical code transformations and analyses benefit from this new data structure. In this section, we discuss the impact of replacing the Data Dependence Graph by the Effects Dependence Graph in source-to-source compilers.

Transformations Using the Effects Dependence Graph Some transformations require the new environment effects and the corresponding dependencies. In fact, in some passes, we cannot move or remove the declaration statements.

The first example is the Allen & Kennedy [START_REF] Allen | Automatic Translation of FORTRAN Programs to Vector Form[END_REF] algorithm on for loop parallelization and distribution that we used in Section 2. These algorithms were designed for the Fortran language initially. When proposing solutions to extend them for the C language, Allen & Kennedy [START_REF] Kennedy | Optimizing Compilers for Modern Architectures: A Dependence-based Approach[END_REF] only focused on pointer issues and not on declarations ones.

Another typical algorithm that requires our Effects Dependence Graph is Dead Code Elimination [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF]. Without our Effects Dependence Graph, the traditional dead code elimination pass either does not take declarations into count, i.e., never eliminates a type or variable declaration statement, or always eliminates them since no dependence arcs link them to useful statements. So, either the dead code elimination pass performs half of its job, or it generates illegal code when the classical use-def chains is the underlying graph, when applied to the internal representation of a source-to-source compiler instead of to three-address code.