IRMAR Bernard Delyon
email: bernard.delyon@univ-rennes1.fr

Exponential inequalities for dependent processes

We give exponential inequalities and Gaussian approximation results for sums of weakly dependent variables. These results lead to generalizations of Bernstein and Hoeffding inequalities, where an extra control term is added; this term contains conditional moments of the variables.

Introduction

In the whole paper (X i ) 1 i n is a sequence of centred random variables. Our objective is to give new exponential inequalities and Gaussian approximation results for the sum S = X 1 + • • • + X n in the case where first and second order mixing conditions are assumed (first order mixing conditions involve conditional means and second order ones involve conditional covariances). This paper improves a previous one [START_REF] Delyon | Exponential inequalities for sums of weakly dependent variables[END_REF] by extending some results, simplifying the presentation, and correcting two errors: a term was forgotten in the expression of q Theorem 1, and another in the expression of w p given in the remark following Theorem 9.

The essential application of exponential inequalities is to give small event probabilities; typically, we would like here to extend the Hoeffding and Bernstein inequalities to mixing processes, that is

P (S A) exp - 2A 2 i b 2 i + ρ , a i X i a i + b i (1)
P (S A) exp - A 2 2E[S 2 ] + 2Am/3 + ρ , m = sup k X k ∞ (2)
where ρ = 0 if the variables are independent. We shall obtain here a value of ρ which depends on conditional moments of the variables. We also want to provide inequalities which generalize what is already known for martingales. Actually Equation ( 2) is not satisfied for a martingale (E[S 2 ] has to be replaced with a bound on the total variation); this will lead us to two different alternatives

P (S A) exp - A 2 2v + 2Am/3 + ρ , (3)
where v is a bound on some kind of quadratic variation and ρ = 0 in the case of a martingale (cf. Theorem 7 for a precise statement), or

P (S A) exp - A 2 2E[S 2 ] + 2Aw/3 , (4) 1
where w is a third order quantity (i.e. if S is replaced with tS, w becomes t 3 w) which involves conditional moments and is in the independent case smaller than 3 2 X 3 k ∞ (Theorem 14). For instance, if we are close to the independent case and S is a normalized sum, that is X k = U k / √ k where (U k ) k is a sequence of weakly dependent bounded random variables, w has order 1/ √ n and the second term in the denominator is residual as long as A ≪ √ n.

Bounds like Equation (3) will be obtained through what we call here the first order approach whereas (4) will require the second order approach. We present the main ideas below.

First order approach for spatial processes. Considering the sequence X 1 , . . . X n as a time series, for instance a martingale, it is natural to introduce the σ-fields

F k = σ(X 1 , . . . X k ).
(

) 5
It will appear that the remainder ρ will involve essentially terms of the form

n k=1 k-1 i=1 X i ∞ E[X k |F i ] ∞
(cf. the constant q in Theorem 1 and Theorem 7).

If the sequence is a random field this filtration will generally not be very useful because of the arbitrariness of the order on the variables, and we shall need to proceed in a such way that the sequence F i in the interior sum actually depends on k. This is done as follows: to each index k we associate a reordering of the sequence which corresponds (hopefully) to increasing dependence with X k ; this brings on a new sequence, depending on k: X k j . This idea goes back to [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF]. More precisely:

For any 1 k n is given a sequence X k j , j = 1, . . . k, which is a reordering of (X j , j = 1, . . . k) with X k k = X k . We attach to each k a family of σ-algebras (F k j ) j k such that

F k j ⊃ σ(X k i , i j), j k. ( 6
)
The σ-algebras (F j ) j n associated to the initial ordering are still defined by [START_REF] Catoni | Laplace transform estimates and deviation inequalities[END_REF].

In particular, we have

F k k ⊃ F k F k k-1 ⊃ F k-1 .
This is how we get a new constant q (Eq. ( 26)) involving now terms of the form

k-1 i=1 X k i ∞ E[X k |F k i ] ∞ . (7)
If (X i ) is a time series, it is natural to set X k i = X i and F k j = F j = σ(X i , i j): the superscripts can be dropped. Later on, the term "times series" will refer to to this situation, whereas the general case will be rather referred to as "random fields".

When dealing with mixing random fields of R d , each index k corresponds to some point P k of the space where X k sits; for each k, the sequence (X k j ) will be typically obtained by sorting the original sequence (X j ) j k in decreasing order of the distance d(P j , P k ). A simple example is the case of m-dependent fields indexed by Z d , that is, a process X a , a ∈ Z d , such that the set of variables X A = {X a : a ∈ A} is independent of X B if the sets A and B have distance at least m; they are typically fields of the form X a = h(Y a+C ) where Y a is an i.i.d. random field, C a finite neighbourhood of 0 in Z d , and h a measurable function of |C| variables.

We would like to point out that this framework covers quite different situations. For instance, in the Erdös-Rényi model of an unoriented random graph with n vertices, edges are represented by n 2 i.i.d. Bernoulli variables Y ab , 1 a < b n, with the convention Y ab = Y ba and Y aa = 0 (see [START_REF] Boucheron | Concentration inequalities using the entropy method[END_REF] and references therein). The number of triangles (for instance) in such a model is

a,b,c Y ab Y bc Y ac = a,b,c X abc .
The process X is here an m-dependent process on the set of three element subsets of {1, . . . n}. We shall treat this example in Section 7.2.

Within this framework, we are able to control exponential moments of S with the help of formulas which generalize the Hoeffding and Bernstein inequalities for independent variables (Theorem 4 and Theorem 5).

The bound of Theorem 4 involves

v = k E[X 2 k |F k-1 ] ∞ , and a remainder term involving conditional expectations E[X k |F k i ] ∞
. This is slightly unsatisfactory since it is known that the key quantity in the case of a martingale is the quadratic variation

X = n k=1 E[X 2 k |F k-1 ]
, and in most cases effective bounds will actually involve X ∞ , which is smaller than v. This is corrected in Theorem 1, where we give a result which generalizes what is known from martingale theory and improves on classical papers concerned with mixing [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF]. However, inspection of the bounds shows that this improvement is really effective only if the conditional expectations |E[X k |F k i ]| are significantly smaller than |X k |; if not, the only way to improve accuracy is to use the second order approach of Sections 5 and 6 briefly discussed below.

Second order results. By this terminology, we mean the following fact: the Hoeffding inequality (Equation 1 with ρ = 0) for instance is obtained from the exponential inequality

E[e tS ] e t 2 i b 2 i /8 . (8)
One obvious drawback of this upper bound is that when t tends to 0, it does not look like 1 + t 2 E[S 2 ]. One would rather expect something like

E[e tS ] e t 2 E[S 2 ]/2+Ct 3 (9)
which has more interesting scaling properties; this approach would hopefully lead to significant improvements in a moderate deviation domain; this is what has been done in [START_REF] Catoni | Laplace transform estimates and deviation inequalities[END_REF], but there S is an arbitrary function of independent variables, in the spirit of the McDiarmid inequality. In order to get closer, like in Equation ( 45) below, we have to pay with higher order extra terms: the remainder terms will not only contain conditional expectations E[X k |F k i ] but also conditional covariances; this will force us to consider for each pair of indices (i, j) another reordering of the sequence which corresponds to increasing dependence with the pair (X i , X j ), and to introduce σ-fields H ij k ; we postpone details to Section 6. In this context we shall give inequality of the form

|E[e S ] -e E[S 2 ]/2 | e E[S 2 ]/2+Ct 3 ( 10
)
The paper is organized as follows. The three forthcoming sections deal with first order order exponential inequalities. A classical use of the exponential inequalities leads to Theorem 7 which generalizes the Bernstein and Hoeffding inequalities. An application to concentration inequalities and triangle counts is given in Section 4.

Section 5 to 7 are concerned with the second order approach, with applications to bounded difference inequalities and triangle counts.

In Section 8 we give some estimates under mixing assumptions.

First order approach for time series

This section is devoted to bounds for the Laplace transform of S in the case of time series (spatial processes are considered in the forthcoming section). The corresponding deviation probabilities will be obtained in Section 4.1 through classical arguments.

In Theorem 1 we present bounds which generalize known results concerning martingales.

In Theorem 4 we give a Hoeffding bound which is valid in both cases (time series and random fields), and Theorem 5 gives a Bennett bound for random fields which does not exactly generalizes (11) because the quadratic variation X is changed into the more drastic upper bound v.

The applicability of the following theorem depends on the way one can bound the quadratic variations involved. In the forthcoming examples, we shall consider only Equation (11) through a bound on X ∞ ; however Equations ( 12) and ( 13) have the advantage of not involving m.

Theorem 1. Let us consider a sequence of centred random variables (X i ) 1 i n with the filtration defined by [START_REF] Catoni | Laplace transform estimates and deviation inequalities[END_REF]. We define

m = sup 1 k n ess sup X k S = n k=1 X k [X] = n k=1 X 2 k X = n k=1 E[X 2 k |F k-1 ] [X + ] = n k=1 (X k ) 2 + X -= n k=1 E[(X k ) 2 -|F k-1 ] q = n k=1 k-1 i=1 X i ∞ E[X k |F i ] ∞ + 1 3 n k=1 X k ∞ E[X k |F k-1 ] ∞
where the notation

x 2 + (resp. x 2 -) stands for x 2 1 x>0 (resp. x 2 1 x<0 ). Then E exp S - X m 2 (e m -m -1) e 3q (11)
E exp S - 1 2 [X + ] - 1 2 X - e 3q (12)
E exp S - 1 6 [X] - 1 3 X e 3q . ( 13
)
If S k = X 1 + X 2 + . . . X k is a supermartingale, these inequalities hold true with q = 0.

Remark. We recommend [START_REF] Bercu | Exponential inequalities for self-normalized martingales with applications[END_REF] for an account on recent work concerning exponential inequalities for martingales.

Proof. The key of the proof will be to use pairs of functions θ(x) and ψ(x) such that ψ 0, e x-θ(x) 1 + x + ψ(x).

These functions are meant to be O(x 2 ) in the neighbourhood of 0. Three examples of such functions are

θ(x) = 0, ψ(x) = e x -x -1 θ(x) = ζ(x + ), ψ(x) = ζ(x -), ζ(x) = e -x + x -1 θ(x) = x 2 6 , ψ(x) = x 2 3 .
Inequality ( 14) for these functions is proved in Proposition 15 of the Appendix. Set

T k = k i=1 X i -θ(X i ) -log(1 + ξ i ), where ξ i = E[ψ(X i )|F i-1 ].
Then

E[e Tn ] = E[e Xn-θ(Xn) (1 + ξ n ) -1 e Tn-1 ] E[(1 + X n + ψ(X n ))(1 + ξ n ) -1 e Tn-1 ] = E[X n (1 + ξ n ) -1 e Tn-1 ] + E[e Tn-1 ]
In the supermartingale case one gets

E[e Tn ] E[e Tn-1 ]. ( 15
)
In the general case we proceed as follows

E[e Tn ] E[X n ((1 + ξ n ) -1 -1)e Tn-1 ] + E[X n e Tn-1 ] + E[e Tn-1 ] = r 1 + r 2 + E[e Tn-1 ]. (16)
We have

r 1 = E[E[X n |F n-1 ]e Tn-1 ξ n /(1 + ξ n )] E[|E[X n |F n-1 ]|e Tn-1 ]( ψ(X n ) ∞ ∧ 1). (17)
The above defined function ψ is convex with ψ(0) = 0, ψ(-1) 1 and ψ(1) 1. Hence |ψ(x)| ∧ 1 |x| and therefore

r 1 X n ∞ E[X n |F n-1 ] ∞ E[e Tn-1 ]. Let ∆ i = T i -T i-1
; the second remainder is bounded as follows:

r 2 = E n-1 i=1 X n (e Ti -e Ti-1 ) = E n-1 i=1 X n tanh(∆ i /2)(e Ti + e Ti-1 ) E n-1 i=1 |E[X n |F i ] tanh(∆ i /2)|(e Ti + e Ti-1 ) n-1 i=1 E[X n |F i ] tanh(∆ i /2) ∞ 2 sup j n-1 E[e Tj ].
Equation (68) of the Appendix implies that

| tanh(∆ i /2)| 3 X i ∞ /2, hence r 2 3 n-1 i=1 X i ∞ E[X n |F i ] ∞ sup i n-1 E[e Ti ]. (18)
Finally, bringing together ( 16), ( 17) and ( 18)

E[e Tn ] (1 + ρ n ) sup i n-1 E[e Ti ], ρ n = X n ∞ E[X n |F n-1 ] ∞ + 3 n-1 i=1 X i ∞ E[X n |F i ] ∞ exp(ρ n ) sup i n-1 E[e Ti ]
and we get by induction that

sup i k E[e Ti ] exp k i=1 ρ i .
The right hand side can be set to 1 in the supermartingale case (cf. ( 15)). In particular

E exp n i=1 X i -θ(X i ) -log(1 + E[ψ(X i )|F i-1 ]) exp(3q) hence E exp n i=1 X i -θ(X i ) -E[ψ(X i )|F i-1 ] exp(3q).
This leads to the three bounds by using the three pairs of functions and by noticing that for m 0 and

x m ϕ(x) ϕ(m), ϕ(x) = e x -x -1 x 2 (19)
which is a consequence of L'Hospital's rule for monotonicity [START_REF] Pinelis | l'Hospital type rules for monotonicity, with applications[END_REF], and that for x ≥ 0

ζ(x) x 2 2
since the function x 2 /2 -ζ(x) has a non-negative derivative.

Next theorem concerns an inequality which only involves [X] (and not X ). The advantage is that no boundedness assumption is required since q does not appear. A definition is needed [START_REF] Bercu | Exponential inequalities for self-normalized martingales with applications[END_REF]: Definition 2. We shall say that an integrable random variable Y is heavy on left if

∀a > 0, E[T a (Y )] 0, where T a (y) = min(|y|, a) sign(y)
is the truncated version of y.

Many classical distributions satisfy this property for a reasonably large subset of parameter values [START_REF] Bercu | Exponential inequalities for self-normalized martingales with applications[END_REF]. Our definition differs slightly from [START_REF] Bercu | Exponential inequalities for self-normalized martingales with applications[END_REF] in the sense that we do not require Y to be centred; thus Theorem 3 below may be seen as an extension of Lemma C.1 of [START_REF] Bercu | Exponential inequalities for self-normalized martingales with applications[END_REF] to supermartingales: Theorem 3. Let us consider a sequence of non-necessarily centred random variables (X i ) 1 i n with the filtration defined by [START_REF] Catoni | Laplace transform estimates and deviation inequalities[END_REF]. If for all k, the variable X k is conditionally heavy on the left in the sense that

∀a > 0, E[T a (X k )|F k-1 ] ≤ 0, ( 20
)
then

E exp S -1 2 [X] 1. ( 21
)
Proof. Using the classical inequality log cosh x ≤ x 2 /2, and the identity cosh x = e x /(1 + tanh x) we get

e x-x 2 /2 1 + tanh x. Thus exp S -1 2 [X] n i=1 1 + tanh X k .
On the other hand since tanh(

x) = - ∞ 0 tanh ′′ (a)T a (x)da, one has E[tanh(X k )|F k-1
] ≤ 0, and the above product is clearly a supermartingale.

Next theorem is a Hoeffding inequality. A weaker version of this theorem could be obtained by using (13):

Theorem 4. Assume that we are in the setting described in the introduction, with a family of σ-fields satisfying [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF]. The variables X k are centred. We define now q as the first term in the expression of q:

q = n k=1 k-1 i=1 X i ∞ E[X k |F i ] ∞ .
If the variables are lower and upper bounded with probability one:

a i X i a i + b i ( 22
)
the following inequality holds

E exp S -1 8 i b 2 i e 8q . ( 23
)
In the supermartingale case (i.e. E[X i |F i-1 ] 0), this inequality remains true if we allow a i and b i to be an F i-1 -measurable random variables. It is well known that the first term of the right hand side, say e c , is smaller than exp(b 2 /8) independently of a (this a key step for proving the Hoeffding inequality, see for instance Appendix B of [START_REF] Pollard | Convergence of Stochastic Processes[END_REF]). On the other hand, it is clear that c a + b (bound e a with e a+b in the expression of e c ). Hence, if we define c i and d i with the equations

c i = min b 2 i 8 , a i + b i , d i = e ai e bi -1 b i
we have

e x e ci + d i x, a i x a i + b i .
Now let the random variables T j be defined as

T k = k i=1 (X i -c i )
We obtain

E[e Tn ] = E[e Xn e Tn-1-cn ] E[(e cn + d n X n )e Tn-1-cn ]
In the supermartingale case, the term involving d n is 0 and this equation gives immediately the result. We assume now that we are not necessarily in this case but a i and b i are deterministic. We can assume in addition, without loss of generality, that a i and b i are chosen so that ( 22) is tight. Notice that in this case we also have a i 0 a i + b i since E[X i ] = 0. The previous equation implies

E[e Tn ] d n e -cn E[X n e Tn-1 ] + E[e Tn-1 ] = d n e -cn E n-1 i=1 X n (e Ti -e Ti-1 ) + E[e Tn-1 ] = d n e -cn r 2 + E[e Tn-1 ]. ( 24
) Let ∆ i = T i -T i-1 = X i -c i ;
bounding r 2 as in the proof of Theorem 1 we get

r 2 = E n-1 i=1 X n tanh(∆ i /2)(e Ti + e Ti-1 ) E n-1 i=1 |E[X n |F i ]∆ i |(e Ti + e Ti-1 )/2 n-1 i=1 E[X n |F i ]∆ i ∞ sup j n-1 E[e Tj ]
and since

|∆ i | max(a i + b i -c i , c i -a i ) b i 2 X i ∞
(b i is the difference between the essential supremum and the essential infimum) we get that

r 2 2ρ n sup i n-1 E[e Ti ], with ρ n = n-1 i=1 X i ∞ E[X n |F i ] ∞ .
On the other hand, since a i 0, Equation (70) in Proposition 16 of the appendix leads to d n e -cn 4, and Equation (24) becomes finally

E[e Tn ] (1 + 8ρ n ) sup i n-1 E[e Ti ] e 8ρn sup i n-1 E[e Ti ].
Hence

E[e Tn ] exp 8 n i=1 ρ i .
and we obtain (23) by using that c i b 2 i /8 in the expression of T n .

We introduce now a theorem which is almost a consequence of (11), except that q has been replaced by q. Its real interest is that unlike Theorem 1, this result will extend to the more general setting given by Equation (6).

Theorem 5. Assume that we are in the setting described in the introduction, with a family of σ-fields satisfying [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF]. The variables X k are centred. We define

v = n k=1 E[X 2 k |F k-1 ] ∞ ,
m as in Theorem 1, and q as in Theorem 4. Then for any t > 0

E[e S ] exp v m 2 (e m -m -1) + q . ( 25
)
Proof. We set

S i = X 1 + X 2 + • • • + X i , i n
and S 0 = 0. Equation [START_REF] Maurey | Construction de suites symétriques[END_REF] implies that

e Xn 1 + X n + X 2 n ϕ(m) hence E[e S ] E[(1 + X n + X 2 n ϕ(m))e Sn-1 ] = E n-1 i=1 X n (e Si -e Si-1 ) + E[(1 + X 2 n ϕ(m))e Sn-1 ] = E n-1 i=1 X n tanh(X i /2)(e Si + e Si-1 ) + ϕ(m)E[X 2 n e Sn-1 ] + E[e Sn-1 ] E n-1 i=1 E[X n |F i ]X i ∞ (e Si + e Si-1 )/2 + ϕ(m)E[E[X 2 n |F n-1 ]e Sn-1 ] + E[e Sn-1 ] (1 + qn + ϕ(m)v n ) sup i n-1 E[e Si ] e qn +ϕ(m)v n sup i n-1 E[e Si ]
where qn and v n are the terms corresponding to k = n in the definition of q and v. This proves the result by induction.

3 First order approach for spatial processes

The proofs Theorem 4 and Theorem 5 are based on a recursion like

E[e Sn ] e qn E[e Sn-1 ].
(Note that this is not the case in Theorem 1 since in its proof we consider E[e Tn ] whose definition depends on the initial ordering of variables because of the conditionings.) At each step, the variables can be reordered in a more suitable order, as explained in the introduction. The proofs can be performed in the same way and we get Theorem 6. Assume that we are in the setting described in the introduction, with a family of σ-fields satisfying [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF]. The variables X k are centred. We define

q = n k=1 k-1 i=1 X k i ∞ E[X k |F k i ] ∞ (26) v = n k=1 E[X 2 k |F k-1 ] ∞ , (27)
Then Theorem 4 and Theorem 5 hold true.

The m-dependent case. Let us consider the case of a m-dependent process in the following sense:

• for each k, there exist a set

I k of m k indices (k included) such that E[X k |X i , i / ∈ I k ] = 0. ( 28
)
One can start with an arbitrary initial ordering of the random variables. For any k, we can choose the sequence X k j in such a way that if k -j m k , X k j = X i for some i / ∈ I k , in order to get

E[X k |X k j , j k -m k ] = 0. ( 29
)
F k i are the corresponding σ-fields. In this case

q = n k=1 j<k E[X k |F k j ] ∞ X k j ∞ sup j X j ∞ n k=1 (m k -1) E[X k |F k-1 ] ∞ 4

Applications of first order bounds

We postpone the discussion concerning spatial processes over a metric space to Section 8.

Deviation bounds

In this section we give the deviation inequalities that can be deduced from the preceding exponential inequalities. We generalize the Bernstein inequality in Equations ( 30) and (34), and the Hoeffding inequality in Equation (33); one could get Bennett inequalities through a similar process, we refer to Appendix B of [START_REF] Pollard | Convergence of Stochastic Processes[END_REF]. In the martingale case, Equations ( 31) and (32) do not assume that the variables are bounded, but sums of squares are involved.

Theorem 7. With the notations of Theorem 1 we have for any A, y > 0

P (S A, X y) exp - A 2 2(y + 6q) + 2Am/3 (30)
P (S A, [X + ] + X - y) exp - A 2 2(y + 6q) (31)
P (S A, [X] + 2 X 3y) exp - A 2 2(y + 6q) . ( 32
)
With the notations of Theorem 4, 5 and 6 we have for any A, y > 0

P (S A, i b 2 i 4y) exp - A 2 2y + 32q (33)
P (S A) exp - A 2 2(v + 2q) + 2Am/3 . ( 34
)
In the martingale case, (33) remains true if we allow a i and b i to be an F i-1 -measurable random variable.

Remark. Equation ( 33) is analogous to Corollary 3(a) of [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF].

Proof. Applying the bound (11) to the variables tX i for some t > 0, we get

log P (S A, X y) log E[exp{t(S -A) - t 2 X -t 2 y t 2 m 2 (e tm -tm -1)}] 3t 2 q + y m 2 (e tm -tm -1) -tA y + 6q m 2 (e tm -tm -1) -tA.
The optimization of this expression w.r.t. t 0 is classical in the theory of Bennett and Bernstein inequalities and delivers (30); see for instance the Appendix B of [START_REF] Pollard | Convergence of Stochastic Processes[END_REF]. The second inequality is deduced from (12) with the same method: for

V = [X + ] + X -or V = ([X] + 2 X )/3 one has log P (S A, V y) log E[e tS-tA-t 2 (V -y)/2 ] 3t 2 q + y t 2 2 -tA
and we take t = A/(y + 8q). Equations ( 33) and (34) are obtained similarly.

Deviation bounds for normalized sums. They are obtained through the following result (in the spirit of [START_REF] De La Peña | Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws[END_REF]):

Theorem 8. If S and D are two random variables, D 0, such that for any t > 0

E exp tS -1 2 t 2 D 1 (35)
then, for any p > 1 and x, y > 0

P S √ a + D > x e -x 2 2p (xy) -1/p , a = y 2 E[S 1/(p-1) + ] 2(p-1) . ( 36
)
Proof. Notice that for any variable Y ∼ N(0, 1/a), s ∈ R and d > 0

E e sY -1 2 dY 2 = exp - d + a 2 (y - s d + a ) 2 + s 2 2(d + a) √ a dy √ 2π = a d + a exp s 2 2(d + a)
.

Consequently, taking (s, d) = (S, D) independent of Y in this equation and using (35) we get

E a D + a exp S 2 2(D + a) 1 S>0 = E e Y S-1 2 Y 2 D 1 S>0 E e S|Y |-1 2 DY 2 1.
Hence

P S √ a + D > x E S √ D + a 1/p exp S 2 2p(D + a) 1 S>0 x -1/p e -x 2 2p E[S q/p + ] 1/q E a D + a exp S 2 2(D + a) 1 S>0 1/p a -1/2p x -1/p e -x 2 2p E[S 1/(p-1) + ] (p-1)/p a -1/2p x -1/p e -x 2 2p .
We get (36) because of the specific choice of a.

This theorem can be applied with equations (12), ( 13) , ( 21) , (23) but not (11) or (25) because of the constant m in these equations which make the scaling impossible. For instance, [START_REF] Georgii | Gibbs Measures and Phase Transitions[END_REF] implies that for t > 0

E exp tS - t 2 6 [X] - t 2 3 X -3t 2 q 1
and (36) holds with

D = 1 6 [X] + 1 3 X + 3q
where q is defined in Theorem 1.

Bounded difference inequalities

The above results lead straightforwardly to bounded difference inequalities by using a classical martingale argument of Maurey [START_REF] Maurey | Construction de suites symétriques[END_REF]. Equation ( 38) is the McDiarmid inequality [START_REF] Mcdiarmid | On the method of bounded differences[END_REF]. Equation ( 39) is a Bernstein inequality in the same context; an advantage of this inequality is that it may give results even if the function D k of (37) is not bounded (37)

Set S = f (Y ) -E[f (Y )] m = sup k ∆ k ∞ .
Then for any A > 0

P (S A) exp - 2A 2 k δ 2 k , δ k = D k ∞ (38) P (S A) exp - A 2 2 k δ ′ k 2 + 2Am/3 . δ ′ k = D k (Y k , Y ′ k ) 2 (39)
where Y ′ k is an independent copy of Y k . Remark. Let us mention that if f has the form f (Y ) = sup g∈Γ g(Y ) for some finite class of functions Γ then, with obvious notations,

D k (a, b) = sup Y sup g∈Γ g(Y 1 , . . . Y k-1 , a, Y k+1 . . . Y n ) -sup g∈Γ g(Y 1 , . . . Y k-1 , b, Y k+1 . . . Y n ) sup Y sup g∈Γ g(Y 1 , . . . Y k-1 , a, Y k+1 . . . Y n ) -g(Y 1 , . . . Y k-1 , b, Y k+1 . . . Y n ) = sup g∈Γ D g k (a, b)
in particular δ k sup g∈Γ δ g k . This is a classical argument in the theory of concentration inequalities. Proof. We shall utilize (33) and (30) with

X k = E[f (Y )|F k ] -E[f (Y )|F k-1 ] F k = σ(Y 1 , . . . Y k ).
We have already pointed out that q = 0 since X k is a martingale difference. Let us define the random variables

L k = inf y E[f (Y 1 , . . . Y k-1 , y, Y k+1 . . . Y n )|F k-1 ] U k = sup y E[f (Y 1 , . . . Y k-1 , y, Y k+1 . . . Y n )|F k-1 ].
The equation

L k E[f (Y )|F k ] U k implies L k -E[f (Y )|F k-1 ] X k U k -E[f (Y )|F k-1 ]
and since U k -L k = D k ∞ we can apply (33) with b k = D k ∞ and get (38).

On the other hand, if we set

∆ k = f (Y ) -f (Y 1 , . . . Y k-1 , Y ′ k , Y k+1 . . . Y n ),
clearly X k can be rewritten as

X k = E[∆ k |F k ] hence E[X 2 k |F k-1 ] E[∆ 2 k |F k-1 ] δ ′ k 2
, and (39) follows from (30).

Inequalities for suprema of U-statistics

For some problems of adaptive estimation and testing, it is very important to be able to control the supremum of U-statistics [12]. We give here a bound in this direction. Consider a sequence of i.i.d. random variables Y 1 , . . . Y n with values on some measurable space E and a finite family H of measurable symmetric functions on E d and set for h ∈ H

Y I = {Y i , i ∈ I}, I ⊂ {1, . . . n} Z h (Y ) = 1 n d I⊂{1,...n},|i|=d h(Y I ) S = sup h∈H Z h (Y ) -E[ sup h∈H Z h (Y )] (40)
where the sum is restricted to the subsets with cardinality d; since the kernel h is symmetric there is no ambiguity regarding the notation h(Y A ). We assume that h is centred:

E[h(Y 1 , . . . Y d )] = 0.
It is well known that if Z h is non degenerate, that is

E[h(Y 1 , . . . Y d )|Y 1 ] ≡ 0,
then the variance of Z h has order n -1 , cf [START_REF] Lee | [END_REF] p.12. We give in the following corollary a deviation bound for S which corresponds to a Gaussian approximation with variance of the same order of magnitude. In the case of degenerate U-statistics we do not get good bounds; this is apparent in the case H has only one element since an abundant literature exists concerning deviation of degenerate U-statistics [START_REF] Giné | Exponential and moment inequalities for U-statistics[END_REF][START_REF] Major | A multivariate version of Hoeffding's inequality[END_REF][START_REF] Bretagnolle | A new large deviation inequality for U-statistics of order 2[END_REF]. The function L below may be bounded by 2 h ∞ , and (41) should be generally good enough unless Y 1 takes a specific value with high probability in which case (42) may become significantly better: Corollary 10. If the symmetric function h satisfies for some function L(x, y)

|h(y 1 , . . . y d ) -h(y ′ 1 , y 2 , . . . y d )| L(y 1 , y ′ 1 ).
Then, for any A > 0

P (S A) exp - 2nA 2 d 2 L 2 ∞ , (41)
P (S A) exp - nA 2 d 2 E[L(Y 1 , Y ′ 1 ) 2 ] + 2Ad L ∞ /3 . ( 42
)
Proof. Fix k, a and b and set with y a = (y 1 , . . . y k-1 , a, y k+1 , . . . y n ), then sup

h,y Z h (y a ) -sup h Z h (y b ) sup h (Z h (y a ) -Z h (y b ))
thus, with the notation of Theorem 9,

|D k (a, b)| sup h |Z h (y a ) -Z h (y b )|. But |Z h (y a ) -Z h (y a )| 1 n d I∋k h(y a I ) -h(y b I ) 1 n d n -1 d -1 L(a, b) = d n L(a, b). Hence D k (a, b) d n L(a, b
) and the result is now just a consequence of Theorem 9.

Second order approach for time series

In this section we consider a sequence of centred random variables (X i ) 1 i n with the filtration defined by [START_REF] Catoni | Laplace transform estimates and deviation inequalities[END_REF]. We set

S k = k i=1 X i . ( 43
)
The idea is to use the following decomposition

e Sn = 1 - n j=1 e S k -e S k-1 ≃ 1 - n k=1 X k e S k
This is why we will need to control X k e S k , for each k. This will be done by using again a similar decomposition:

Lemma 11. Consider a sequence of centred random variables (X i ) 1 i n with the filtration by ( 5) and the partial sums (43). Then

E[X k e S k ] -E[X k S k ]E[e S k ] w k sup j≤k E[e Sj ]
with

w k = 1 2 j k E[X k |F j ] ∞ X j 2 ∞ + j k i j E[X k X j |F i ] -E[X k X j ] ∞ X i ∞ + j k |E[X k S j-1 ]| X j ∞ . ( 44
)
Proof.

X k e S k = X k + k j=1 X k (e Sj -e Sj-1 -X j e Sj ) + k j=1 X k X j e Sj = X k + k j=1 X k (e Sj -e Sj-1 -X j e Sj ) + k j=1 j i=1 X k X j (e Si -e Si-1 ) + k j=1 X k X j = X k + k j=1 X k (e Sj -e Sj-1 -X j e Sj ) + k j=1 j i=1 (X k X j -E[X k X j ])(e Si -e Si-1 ) - k j=1 k i=j+1 E[X k X j ](e Si -e Si-1 ) + k j=1 E[X k X j ](e S k -1) + k j=1 X k X j = X k + R 2 + R 3 + R 4 + E[X k S k ]e S k -E[X k S k ] + X S k .
Concerning R 2 , we notice that

|e y -1 -y| 1 3 y 2 ( 1 2 e y + 1)
(this is due to the fact that for ε = ±1, f ε (y) = 1 3 y2 ( 1 2 e y + 1) + ε(e y -1 -y) is a convex function which satisfies f ′ ε (0) = f ε (0) = 0, thus f ε 0). Replacing y by -y and multiplying by e y we get

|1 -e y + ye y | 1 3 y 2 ( 1 2 + e y )
hence, using this inequality in each term of R 2 with y = X j :

|E[R 2 ]| E j k |E[X k |F j ]| 1 3 X 2 j ( 1 2 e Sj-1 + e Sj ) 1 2 j k E[X k |F j ] ∞ X j 2 ∞ sup j k E[e Sj ].
Using now the identity e u -1 = (e u + 1) tanh(u/2), we have

|E[R 3 ]| = E j k i j (E[X k X j |F i ] -E[X k X j ]) tanh(X i /2)(e Si + e Si-1 )| j k i j E[X k X j |F i ] -E[X k X j ] ∞ X i ∞ sup j k E[e Sj ]
and similarly

|E[R 4 ]| = E k i=2 i-1 j=1 E[X k X j ] tanh(X i /2)(e Si-1 + e Si ) i k |E[X k S i-1 ]| X i ∞ sup j k E[e Sj ]
Theorem 12. Consider a sequence of centred random variables (X i ) 1 i n with the filtration by ( 5) and the partial sums (43). Then

E[e Sn ]e -1
where

δ 0 = 1 j<k n E[X k X j ] -(x -= -x1 x<0 ) (46) w = n k=1 w k (47)
and w k is given by (44). In particular, for any t > 0

E[e tSn ] e 1 2 t 2 E[S 2 n ]+t 2 δ0+t 3 w . ( 48
)
Remark. In the martingale case δ 0 = 0 and

w n = 1 2 X n 3 ∞ + i n-1 E[X 2 n |F i ] -E[X 2 n ] ∞ X i ∞ .
Proof. We consider the piecewise linear interpolation of the sequence S n

S(t) = S k + (t -k)X k+1 , t ∈ [k, k + 1] = S [t] + (t -[t])X [t]+1 . Consider t ∈ (n -1, n), i.e. t = n -1 + τ , τ ∈ (0, 1), then S(t) = S n-1+τ = S n-1 + τ X n
The previous lemma, applied where X n is replaced with τ X n , and with S(t) in place of S n , implies that s) ] with w(t) = w n .

τ E[S ′ (t)e S(t) ] -E[S ′ (t)S(t)]E[e S(t) ] τ w(t) sup s t E[e S(
We set

f (t) = E[e S(t) ] f * (t) = sup s t f (s) g(t) = 1 2 E[S(t) 2 ]. then f ′ (t) -g ′ (t)f (t) w(t)f * (t) (49)
In particular

(f e -g ) ′ = wf * e -g
for some function w(t) such that

| w(t)| w(t).
Hence

f (t)e -g(t) = 1 + t 0 w(s)f * (s)e -g(s) ds. ( 50
)
We need now a first estimate of f * . From (49) we get

f (t) 1 + t 0 (g ′ (s)f (s) + w(s)f * (s))ds implying, if t * is the index such that f * (t) = f (t * )
, and if we set g ′ (t) + = g ′ (t)1 g ′ (t)>0 ,:

f * (t) 1 + t * 0 (g ′ (s)f (s) + w(s)f * (s))ds 1 + t 0 (g ′ (s) + + w(s))f * (s)ds
and by the Gronwall Lemma

f * (t) ≤ exp t 0 (g ′ (s) + + w(s))ds
Inserting this back in (50):

|f (t)e -g(t) -1| t 0 w(s) exp s 0 (g ′ (u) + + w(u))du e -g(s) ds = t 0 w(s) exp s 0 (|g ′ (u)|1 g ′ (u)<0 + w(u))du ds exp t 0 |g ′ (u)|1 g ′ (u)<0 du t 0 w(s)e s 0 w(u)du ds e t 0 |g ′ (u)|1 g ′ (u)<0 du e t 0 w(s)ds -1 . If [u] = k -1 then g ′ (u) = E[X k S k-1 ] + (u -k + 1)E[X 2 k ] -E[X k S k-1 ] - hence k k-1 |g ′ (u)|1 g ′ (u)<0 du = k k-1 (-g ′ (u)) + du E[X k S k-1 ] -.
This implies (45). Equation ( 48) is obtained by noticing that (45) implies

E[e Sn ]e -1 2 E[S 2 n ] -1 e δ0 e w -1
and by an elementary scaling argument.

6 Second order approach for spatial processes

As mentioned in the introduction, in order to get better results, we shall have to control conditional expectations of products X k X j ; actually, our procedure will rather lead to products like X k X k j ; hence we are led to introduce for any pair (k, j) a sequence X k,j i corresponding to increasing dependence with (X k , X k j ). More precisely:

Second order setting (i) For any 1 k n is given a sequence X k j , j = 1 . . . k, which is a reordering of (X j , j = 1, . . . k) with X k k = X k . We attach to each k the σ-algebras

F k j ⊃ σ(X k i , i j), j k. (51)
(ii) For 1 j k n, the sequence (X k,j i ) i j is a reordering of (X k i ) i j and

H k,j i ⊃ σ(X k,j i , i j). (52)
In other words the σ-field F k j is made by taking off F k j+1 the "closest" variable to X k . The σ-field H k,j i is made by continuing this process after F k j (hence i < j) in a way which may depend on k and j.

This set-up is essentially, in a somewhat more general context, what is considered in [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF]. For time series, we have

X k i = X i and F k i = H k,j i = F i = σ(X l , l i).
This setting is adequate for dealing with mixing random fields in which case each index k corresponds to some point P k of the space; for each k, the sequence (X k j ) j will be obtained by sorting the original sequence (X j ) in decreasing order of the distance d(P j , P k ), and H k j will be the σ-field generated by the random variables setting on the j more distant points from P k , say P k 1 ,. . . P k j ; it is natural to define X k,j i as X l where P l is the i-th more distant point from {P k , P k j }, but the choice

X k,j i = X k i , H k,j i = F k i
, is typically suboptimal but good enough for random fields over the Euclidean space (see Section 8).

Theorem 13. Consider a sequence of centred random variables (X i ) 1 i n with the filtrations (51) and ( 52). Set

w = n k=1 w k w k = 1 2 j k E[X k |F k j ] ∞ X k j 2 ∞ + j k i j E[X k X k j |H k,j i ] -E[X k X k j ] ∞ X i ∞ + j k |E[X k S k j-1 | X k j ∞ S k j = j i=1 X k i .
Then ( 45) and (48) hold true.

Proof. We can work out Lemma 11 as before except that expressions like

k j=1 j i=1 X k X j (e Si -e Si-1 ) will become k j=1 j i=1 X k X k j (e S k,j i -e S k,j i-1 ), S k,j i = i l=1 X k,j l .
and since S k,j i is H k,j i -measurable, these σ-fields appear in the expression of w k . Since S k = S kk k and S k j = S kj j , we get as before

E[X k e S k ] -E[X k S k ]E[e S k ] w k sup i j k E e S kj i w k sup α∈[0,1] n E e k j=1 αj Xj (53)
and the proof goes as the proof of Theorem 12 with a slight complication due to α. We still define t) ]

S(t) = i t X i + (t -[t])X [t]+1 f (t) = E[e S(
g(t) = E[S(t) 2 ]
and, as we obtained ( 49) and (50), we get here

f ′ (t) -g ′ (t)f (t) w(t)f * (t) (54)
which implies

f (t)e -g(t) = 1 + t 0 w(s)f * (s)e -g(s) ds. ( 55
)
with | w(s)| ≤ w(s). In order to bound f * , we define for any α ∈ {0,

1} n S α (t) = i t α i X i + (t -[t])α [t]+1 X [t]+1 f α (t) = E[e Sα(t) ] g α (t) = E[S α (t) 2 ] f * (t) = sup α∈[0,1] n ,s t f α (s). = sup α∈[0,1] n f α (t)
Equation ( 53) can be applied with α k X k instead of X k and this leads to

|f ′ α (t) -g ′ α (t)f α (t)| w t f * (t).
As before we get for any α

f α (t) 1 + t 0 (g ′ α (s)f α (s) + w s f * (s))ds 1 + t 0 ((g ′ α (s)) + f α (s) + w s f * (s))ds
and this leads to

f * (t) 1 + t 0 (g ′ * (s)f * (s) + w s f * (s))ds with now g ′ * (s) = sup α g ′ α (s) + .
The Gronwall Lemma leads to

f * (t) ≤ exp t 0 (g ′ (s) * + w(s))ds .
We need now a bound on g ′ * :

g ′ * (s) = sup α α [s] E[X [s]+1 S α (s)] + i t E[X [s]+1 X i ] + + (t -[t])E[X 2 [s]+1 ] = g ′ (s) + i t E[X [s]+1 X i ] -.
Inserting this back in (55):

|f (t)e -g(t) -1| 7 Applications of second order bounds

Deviation inequalities

In this section we give the deviation inequalities that can be deduced from the preceding exponential inequalities. The bound (56) is analogous to the bound or Corollary 3 (b) in [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF] p.85, but in this paper the variance E[S 2 ] is amplified with an extra factor 2e 2 and w takes a slightly different value.

Theorem 14. With the notations of Theorem 12 and Theorem 13, we have for any A > 0

P (S A) exp - A 2 2E[S 2 ] + 4δ 0 + 2 2Aw/3 . ( 56
)
Remark. We recall that in the martingale case δ 0 = 0 and

w n = 1 2 X n 3 ∞ + i n E[X 2 n |F i ] -E[X 2 n ] ∞ X i ∞ .
Proof. Using (48) we get

log P (S A) log E[e t(S-A) ] ( 1 2 E[S 2 ] + δ 0 )t 2 + w t 3 3 -tA.
We choose t = A/(E[S 2 ] + 2δ 0 + 2Aw/3); in particular t 3A/2w hence log P (S A)

( 1 2 E[S 2 ] + δ 0 )t 2 + 2Aw/3 t 2 2 -tA = - tA 2 = - A 2 2E[S 2 ] + 4δ 0 + 2 2Aw/3 .
7.2 m-dependency processes and triangle counts

m-dependent processes

Let us consider the case of a (m, n)-dependent process in the following sense:

• for each k, there exist a set

I k of m k indices (k included) such that E[X k |X i , i / ∈ I k ] = 0 (57)
• for each pair (j, k), there exist a set J j,k of n k indices such that

E[X j X k |X i , i / ∈ J j,k ] = E[X j X k ]. (58)
One can start with an arbitrary initial ordering of the random variables. For any k, we can choose the sequence X k j in such a way that if k -j m k , X k j = X i for some i / ∈ I k , in order to get

E[X k |X k j , j k -m k ] = 0. ( 59
)
Similarly we can choose the sequence X k,j i in such a way that

E[X k j X k |X k,j i , i j -n k ] = E[X j X k ]. (60)
F k i and H k,j i are the corresponding σ-fields. In this case, for the calculation of w k from Theorem 13 we notice that

1 2 j k E[X k |F k j ] ∞ X k j 2 ∞ 1 2 m k ξ 2 X k ∞
and for the second term, if we set ξ = sup i X i ∞

j k i j E[X k X k j |H k,j i ] -E[X k X k j ] ∞ X i ∞ n 2 k ξ 2 X k ∞
and for the third one

j k |E[X k S k j ]| X k j-1 ∞ = k j=k-m k +1 j i=k-m k +1 |E[X k X k i ]| X k j-1 ∞ ξ 2 X k ∞ k j=k-m k +1 j i=k-n k +1 1 ξ 2 X k ∞ 1 2 m k (m k + 1) hence w k 1 2 (m k + 1) 2 ξ 2 X k ∞ + n 2 k ξ 2 X k ∞ .
Thus we can take

w = ξ 2 k X k ∞ 1 2 (m k + 1) 2 + n 2 k , ξ = sup i X i ∞ . (61)

Triangle counts

We shall show that the standard Gaussian approximation is asymptotically valid for triangle counts in the moderate deviation domain.

In the Erdös-Rényi model of an unoriented random graph with n vertices, edges are represented by n We set p = E[Y 12 ] and

X abc = Y ab Y bc Y ac -p 3 S = {a,b,c} Y ab Y bc Y ac -p 3 = {a,b,c} X abc = τ ∈T X τ ( 62
)
where T is the set of subsets of {1, . . . n} with three elements, |T | = n 3 . For any τ = {a, b, c}, define A τ the set elements of T such that at least two points are in common with τ (τ , {a, b, d}, {a, d, c}, . . . ); this makes 1 + 3(n -3) elements and (X σ ) σ / ∈Aτ is independent of X τ . Hence we can take m k = 1 + 3(n -3). Similarly, for any pair τ, τ ′ , define by B τ,τ ′ the set of σ which have not two points in common with τ or τ ′ . Then σ(X σ , σ ∈ B τ,τ ′ ) in independent of (X τ , X ′ τ ). Since the complement of B τ,τ ′ has at most 2m 1 variables, we can take

n k = 2m 1 . Finally, since X i ∞ 1 w 1 2 (m 1 + 1) 2 + 4m 2 1 |T | 9 2 (3n) 2 1 6 n 3 7n 5
and since δ 0 = 0 (covariates are positively correlated) Equation (56) implies

P (S A) exp - A 2 2V ar(S) + 2 14n 5 A/3 . (63)
Let us recall that (see [START_REF] Boucheron | Concentration inequalities using the entropy method[END_REF])

V ar(S) = n 3 (p 3 -p 6 ) + n 4 4 2 (p 5 -p 6 ).
This has order n 4 due to the covariance terms. Let us briefly compare with the bound of [START_REF] Boucheron | Concentration inequalities using the entropy method[END_REF]; this paper delivers a bound for P (S A) which is slightly larger than

exp - A 2 6nE[Z] + 16 E[Z]A , E[Z] = n(n -1)(n -2) 6 p 3 (64)
(the actual formula is much more complicated; we have used that min(a -1 , b -1 ) 2/(a + b) to obtain this from Theorem 18 of [START_REF] Boucheron | Concentration inequalities using the entropy method[END_REF]). One has 6nE[Z] 2 p 2 -p 3 2V ar(S). For p fixed and n large, the square root term in (63) is residual if A ≪ n 3 ; this is the moderate deviation case since the centring term in (62) has order n 3 (notice that S n 3 w.p.1), and we get the right variance. In (64), a change occurs when n 5/2 ≪ A, and if we set A = Bn 5/2 with B large, (64) leads to exp(-cnB) while (62) behaves like exp(-cnB 2 ).

Evaluation of constants under ϕ-mixing assumptions

We give here informally some arguments to convince the reader that under standard ϕ-mixing assumptions the constant q has the same order as the variance of the sum, and that w will be small.

For more details about mixing we refer to [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF], [START_REF] Doukhan | Mixing: Properties and Examples[END_REF] and [START_REF] Bradley | Basic properties of strong mixing conditions. A survey and some open questions. Update of, and a supplement[END_REF] (particularly Section 8 concerning random fields).

The ϕ-mixing constant between two σ-fields A and B is defined as

ϕ(A, B) = sup A∈A,B∈B |P (B|A) -P (B)|.
It is well known, see reference [START_REF] Rio | Théorie asymptotique des processus aléatoires faiblement dépendants[END_REF] p.27 or [START_REF] Hall | Martingale Limit Theory and its Applications[END_REF] p.278, that this implies that if Z is a zero-mean B-measurable random variable

E[Z|A] ∞ 2ϕ(A, B) Z ∞ .
Assume that X is a field over a part of Z d : each variable X k of the field sits on some P k ∈ Z d . F k j is the σ-field generated by the j more distant points from P k different from X 1 ,...X k-1 , and we take for simplicity H k,j i = F k i . Denote by P k j the the jth closest point to P k , when the points P 1 , . . . P k-1 have been excluded. Thus X k j sits on P k k-j+1 . The distance of P k to P k j , is at least cj1/d , for some constant c. This implies that standard ϕ-mixing assumptions between σ(X k ) and F k j can be rewritten as

ϕ(F k j , σ(X k )) ϕ ∞,1 ((k -j) 1/d ) (65)
for some decreasing function ϕ ∞,1 (for example exponential decay holds for finite range 1 shift-invariant Gibbs random fields [START_REF] Georgii | Gibbs Measures and Phase Transitions[END_REF] pp. 158-159; this contains a lot of examples). The subscripts ∞ and 1 on ϕ mean that there is no restriction on the number of random variables contained in the first σ-field, F k j , and there is only 1 variable in the second, σ(X k ); we use this traditional notation, in particular for compatibility with [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF].

On the other hand for i < j, j -i is smaller than the number of points in the annulus {x : P k j -P k x -P k P k i -P k }, in particular, for some c j -i c P k i -P k d-1 P k j -P k i .

Hence P k j -P k i is at least c(j -i)i -1+1/d for some c. This implies that standard ϕ-mixing assumptions between σ(X k , X k j ) and F k i can be rewritten as ϕ(F k i , σ(X k , X k j )) ϕ ∞,2 ((j -i)(k -i + 1) -1+1/d ), i j (66)

for some decreasing function ϕ ∞,2 . Equations ( 65) and (66) will imply, for i j k, and any measurable bounded functions f and g

E[f (X k )|F k j ] ∞ 2 f (X k ) ∞ ϕ ∞,1 ((k -j) 1/d ) E[g(X k , X k j )|F k i ] -E[g(X k , X k j )] ∞ 2 g(X k , X k j ) ∞ ϕ ∞,2 ((j -i)(k -i + 1) -1+1/d ).
The first equation leads to

E[X k |F k j ] ∞ 2 X k ∞ ϕ ∞,1 ((k -j) 1/d ) E[X k X k j |F k i ] -E[X k X k j ] ∞ 2m E[X k |F k j ] ∞ 4m X k ∞ ϕ ∞,1 ((k -j) 1/d )
with m = sup i X i ∞ , and the second

E[X k X k j |F k i ] -E[X k X k j ] ∞ 2m X k ∞ ϕ ∞,2 ((j -i)(k -i + 1) -1+1/d ).
For the first term, since j + 1 k -j and 1 2 (k + 1) k -j: The third term in w is bounded as

k j k |E[X k S k j-1 | X k j ∞ m 2 k k j=1 i<j E[X k |F k i ∞ = m 2 k i<k (k -i) E[X k |F k i ∞ 2m 2 k i<k (k -i) X k ∞ ϕ ∞,1 ((k -i) 1/d ) 2m 2 k j>0 j X k ∞ ϕ ∞,1 (j 1/d ) 2m 2 m 1 j>0 j j-1 (x + 1)ϕ ∞,1 (x 1/d )dx = 2dm 1 m 2 ∞ 0 (1 + y d )y d-1 ϕ ∞,1 (y)dy.
Putting everything together we finally get

w 1 2 m 3 + 11dm 2 m 1 ∞ 0 (1 + y d )y d-1 (ϕ ∞,1 (y) + ϕ ∞,2 (y))dy
The integral in the right hand side is essentially the D(φ) of [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF] page 86. If we refer to the independent case (X k of order 1/ √ n) the factor m 2 m 1 is of order 1/ √ n, what makes the factor of t 3 in (48) residual as far as t is smaller than √ n (moderate deviations). Proof. Everything will be more or less based on the inequality e x 1 + x. Equation ( 67) is obvious for the first pair of functions. In the second case we have only to check for x > 0; since in this case x -θ(x) = 1 -e -x this reduces to proving that:

A Technical inequalities

1 -e -x log(1 + x).

The function log(1 + x) + e -x -1 has a derivative (1 + x) -1 -e -x which is 0 since e x 1 + x; hence the inequality is satisfied. The third case is the non negativity of the function

f (x) = 1 + x + x 2 3 -e x-x 2 /6 .
This function satisfies

f ′ (x) = 1 + 2x 3 -1 - x 3 e x-

Proof.

  We start, as in the proof of the Hoeffding inequality, with the following inequality based on the upper-bound of the exponential function by the chord over the curve on [a, a + b]: e x (a + b)e a -ae a+b b + x e a+b -e a b , a x a + b.

Theorem 9 .

 9 Let Y = (Y 1 , . . . Y n ) be a zero-mean sequence of independent variables with values in some measured space E. Let f be a measurable function on E n with real values. We assume that for some functions D k (a, b) one has |f (y 1 , . . . y k-1 , a, y k+1 . . . y n ) -f (y 1 , . . . y k-1 , b, y k+1 . . . y n )| D k (a, b).

  (u) * + w(u))du e -g(s) )e w(u) duds.

2 i

 2 .i.d. Bernoulli variables Y ab , 1 a < b n, with the convention Y ab = Y ba and Y aa = 0. The number of triangles in such a model is Z = {a,b,c} Y ab Y bc Y ac .

T 1 0 2 ( 1 ( 1 j j- 1 (

 12111 j (k-1)/2 ϕ ∞,2 ((k -j) 1/d ) 2y d + 1)y d-1 ϕ ∞,2 (y)dyand for the second oneT 2 = 0 (k-1)/2<j k ϕ ∞,1 (j 1/d ) = j j + 1)ϕ ∞,1 (j 1/d ) j u + 2)ϕ ∞,1 (u 1/d )du = d ∞ 0 (y d + 2)y d-1 ϕ ∞,1 (y)dy

Proposition 15 . 1 θ 3 2

 1513 The three pairs of functionsθ(x) = 0, ψ(x) = e x -x -1 θ(x) = ζ(x + ), ψ(x) = ζ(x -), ζ(x) = e -x + x --θ(x) -log(1 + ψ(y))) m, |x|, |y| m.(68)

x 2 / 6 f 1 - 4 m

 614 ′′ (1 -x + x 2 /6)e x-x 2 /6 which is non negative since 1 -(1 -u)e u 0; f is convex. Since f ′ (0) = 0 and f (0) = 0, we conclude that f is non negative.For the last inequality, we start with an upper bound on ψ(y). In the first case ψ(y) ψ(|y|) ψ(m) e m -1.In the second case ψ(y) ψ(-m) e m -1 and in the third case ψ(y) m 2 /3 e m -1 (because of the expansion of the exponential); in any case we havelog(1 + ψ(y)) m. (69)On the one handtanh( 1 2 (x -θ(x) -log(1 + ψ(y)))) tanh( 12x) m/2 and on the other hand, thanks to (69), using that θ(x)x 2 /2 tanh( 1 2 (log(1 + ψ(y)) -x + θ(x))) tanh(m + m 2 /4) min(m + m 2 /4, 1)5 by considering separately the cases m < 1 and m > 1.

E[S 2 n ] -1 e δ0 (e w -1),(45)

This means the existence of a constant c such that if k, l ∈ Z d are such that d(k, l) > c then X k and X l are independent conditionally to (X j ) j / ∈{k,l} .

Hence

We get with m 1 = X i ∞ , and setting ϕ

The integral is essentially the quantity B(φ) of [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF], and Equations ( 33) and (34) may be seen as improvements over (b)(i) and (ii) of Corollary 4 of [START_REF] Dedecker | Exponential Inequalities and Functional central limit theorems for random fields[END_REF]. The constant w in Theorem 13 is the sum of three terms. The first one is

The second term contributing to w is


Hanbing Li
email: hanbing.li@inria.fr

Isabelle Puaut
email: isabelle.puaut@irisa.fr

Erven Rohou
email: erven.rohou@inria.fr

Traceability of Flow Information: Reconciling Compiler Optimizations and WCET Estimation

Keywords: WCET estimation, optimization, compilation, precise and safe, LLVM

Real-time systems have become ubiquitous. For this class of systems, correctness implies not only producing the correct result, but also doing so within specified timing constraints. Designers are required to obtain the worst-case execution time (WCET) of their systems to guarantee that all applications meet their time constraints. Many WCET estimation methods have been proposed. They operate through static code analysis, measurements, or a combination of both. Such methods give an upper bound of the time required to execute a given task on a given hardware platform. To be useful, WCET estimates have to be as tight as possible.

Information on possible flows of control (the so-called flow information) improves the tightness of WCET estimates. Flow information, should it be produced automatically or be inserted manually from annotations, is typically inserted at source code level. On the other hand, WCET analysis is performed at machine code level. Between these two levels, compiler optimizations may have a dramatic effect on the structure of the code, resulting in a loss of useful information. For this reason, many WCET tools for real-time systems turn off compiler optimizations when computing WCET. In this paper, we propose a framework to trace and maintain flow information from source code to machine code to benefit from optimizations, yet improving the WCET estimates. Our implementation in the LLVM compiler shows that we can improve the WCET of Mälardalen benchmarks by 60 % in average, and up to 86 %. We also provide new insight on the impact of existing optimizations on the WCET.

INTRODUCTION

In real-time systems, knowing the Worst-Case Execution Time (WCET) of pieces of software is required to demonstrate that the system meets its timing constraints, in all sit-uations, including the worst case. WCET calculation methods have to be safe and as tight as possible. Safety means that the estimate must be higher than or equal to the actual worst-case execution time. Tightness makes the estimate useful: to avoid over-provisioning processor resources, the estimated WCET has to be as close as possible to the actual WCET.

WCET estimation has to be computed at the machine code level, because the timing of processor operations can only be obtained at this level. Moreover, in processors with cache memories, the addresses of memory locations -necessary to analyze the contents of caches -are only known at binary code level.

Information on program control flow is required to calculate tight WCETs. The most basic flow information consists in loop bound information (the maximum number of times a loop iterates, regardless of the program input). More elaborate flow information help tighten WCETs, for example by expressing that a given path is infeasible, or that some program points are mutually exclusive during the same run.

Flow information may be obtained by using static analysis techniques or added manually by the application developer through annotations. In both situations, it is convenient to extract or express flow information at the source code level. When using manual annotations, the application developer can focus on the application semantics and behavior, ignoring the compiler and the binary code. When extracted automatically, more flow information can be gathered at source code level than at binary code level because of the higher level of the analyzed language.

Compilers translate high level languages written by programmers into binary code fit for microprocessors. Modern compilers also typically apply hundreds of optimizations to deliver more performance. Some of them are local (i.e. at the granularity of the basic block), they usually do not challenge the consistency of flow information. Other optimizations radically modify the program control flow. As a result, it is usually very difficult to match the structure of the binary code with the original source code, and hence to port flow information from high-level to low-level representations. Even when the structure of the binary and source code seem to match, there may be important changes of loop bound information, through optimizations such as loop unrolling or loop re-rolling.

Using optimizing compilers is key to deliver performance. From the point of view of the programmer, compilers are black boxes that take source code as input, and produce binary code. Some compilers can produce dumps of the transformations they applied, but these dumps are very limited. Yet, modern compilers apply hundreds of transformations, some very aggressive, that radically modify the structure of loops (consider unrolling, software pipelining, fusion, tiling, polyhedral transformations...) and even functions (inlining, specialization, processing OpenMP directives). 1 Using the flow information obtained at the source code level, or using best-effort methods for matching source code and binary code may be misleading. In the favorable case, the WCET is "simply" overestimated. Consider the example of Figure 1. The loop on the left has been annotated by the programmer. After optimization, in particular loop unrolling, the code will be similar to the right part of the figure (shown in C language for readability, although it will be expressed in compiler IR, or binary code). Both contain a single loop, and a tool could be tempted to match the CFGs and port the flow information to the binary representation. In this particular case, the result remains safe, but precision is lost since the new loop obviously iterates only 50 times at the maximum, whereas the original loop iterates 100 times. On the other hand, loop rerolling (implemented in some compilers -including LLVM -to reduce code size) results in a increase of the number of loop iterations. Using graph matching would result in underestimated WCETs, that jeopardize the system safety.

In this paper, we propose a framework to systematically transform flow information from source code level down to binary code level. The framework defines a set of formulas to transform flow information for standard compiler optimizations. What is crucial is that transforming the flow information is done within the compiler, in parallel with transforming the code (as illustrated in Figure 2). There is no guessing what flow information have become, it is transformed along with the code they describe. In case the transformation is too complex to update the information, we always have the option to drop it. The result is then safe, even though it will probably result in a loss of precision. However, we also notify the programmer (or the compiler developer) that this optimization causes problems in a real-time context, making it possible to disable it. Note that only problematic optimizations must be disabled, as opposed to all of them in most current real-time systems.

Our framework is designed to transform flow information as expressed by the most prevalent WCET calculation technique: Implicit Path Enumeration Technique (IPET) [START_REF] Li | Performance analysis of embedded software using implicit path enumeration[END_REF]. More precisely, flow constraints are expressed as linear relations between execution counts of basic blocks in the program control flow graph. As shown later in the paper, the framework is general enough to cover all linear flow constraints and all typical optimizations implemented in modern compilers. The proposed framework was integrated into the LLVM compiler infrastructure. For the scope of this paper, our experiments in LLVM will concentrate on loop 1 Debugging highly optimized programs gives a sense of such surprising transformations. The remainder of the paper is organized as follows. Related work is briefly surveyed in Section 2. Section 3 then details the context in which our work was developed: type of WCET calculation used, types and formats of flow information supported. Section 4 describes how flow information is transformed, independently of the compiler framework. Implementation within the LLVM compiler infrastructure is presented in Section 5. We provide experimental data in Section 6, before concluding with a summary of the paper contributions and plans for future work.

RELATED WORK

WCET calculation techniques can be classified into two categories: static and measurement-based methods [START_REF] Wilhelm | The worst-case execution-time problem-overview of methods and survey of tools[END_REF]. Static methods analyze the set of possible execution paths from the program structure. They derive upper bounds of the WCET from the program structure and a model of the hardware architecture. By design, static methods are guaranteed to identify the longest execution path, and therefore, are safe. On the other hand, measurement-based methods use endto-end measurements on the processor or a cycle-accurate simulator, with different inputs, in search for the input that exercises the longest execution path. This approach may miss the actual worst case. We do not address measurementbased techniques in this paper.

Information on the flow of control of applications improves the tightness of WCET estimates. Beyond loop bounds, which are mandatory for WCET calculation, examples of flow information include infeasible paths, or other properties constraining the relative execution counts of program points. Flow information can be obtained via two basic methods: static analysis or annotations added by the application developer. Among many other examples using static analysis, Healy and Whalley [START_REF] Healy | Automatic detection and exploitation of branch constraints for timing analysis[END_REF] concentrate on the detection and exploitation of branch constraints, and Lokuciejewski et al. [START_REF] Lokuciejewski | A fast and precise static loop analysis based on abstract interpretation, program slicing and polytope models[END_REF] extract loop bounds. Tools for WCET estimation also have support for expressing flow information, either using annotations in the source code or through flow expression languages. The former approach is used for example in the Heptane static analysis tool [START_REF] Colin | Worst case execution time analysis for a processor with branch prediction[END_REF], whereas the Otawa static WCET estimation tool2 defines a language dedicated to the expression of flow information. For the scope of this paper, we assume that flow information is known and the focus is on the traceability of flow information all along the compilation process.

WCC3 is a WCET-aware compiler that integrates optimizations for WCET minimization. Our work takes a different angle, by addressing general-purpose optimizations and compilers. Experimental results show that most optimizations designed for average-case performance are also beneficial in the worst-case.

Raymond et al. [START_REF] Raymond | Timing analysis enhancement for synchronous program[END_REF] focus on timing analysis enhancement through traceability of flow information for synchronous programs. Full traceability is guaranteed within the Lustre to C compiler, whereas error-prone graph matching is used so far for C to binary compilation. Our work is intended to complement theirs, with the overall objective of having full traceability of flow information from very high level languages to binary code.

An early approach was presented by Engblom et al. [START_REF] Engblom | Facilitating worst-case execution times analysis for optimized code[END_REF] to derive WCET when code optimizations are applied. According to the authors, there data structures were not powerful enough to support the most complex loop optimizations such as loop unrolling. In contrast, our mechanism can handle most LLVM optimizations, including loop unrolling.

The SATIrE system was introduced [START_REF] Schordan | Source-to-source analysis with SATIrEan example revisited[END_REF] as a source-tosource analysis that can map source code annotations to the intermediate representation. Barany et al. [9] use this system to build a WCET analysis tool which combines sourcelevel analysis, optimization and a back-end compiler performing WCET analysis. The connection to several other timing analysis tools is also implemented. Comparing with their source-to-source analysis, our method works on sourceto-binary transformation.

Huber et al. propose [START_REF] Huber | Combined WCET analysis of bitcode and machine code using control-flow relation graphs[END_REF] an approach to relate intermediate code and machine code when generating machine code in compiler back-ends. The approach is based on a novel representation, called control flow relation graph, that is constructed from partial mapping provided by the compiler. In contrast to them, we focus in this paper on optimizations performed at the intermediate code level.

The most related work is from Kirner et al. [START_REF] Kirner | Extending optimising compilation to support worst-case execution time analysis[END_REF][START_REF] Kirner | Transforming flow information during code optimization for timing analysis[END_REF], who present a method to maintain correct flow information from source code level to machine code level. It transforms flow information in parallel to the code transformations performed by the compiler. We differ in the following respects. Their first implementation goes back to GCC-2.7.2, a compiler released in 1995, lacking a modern higher-level intermediate representation (GIMPLE was introduced much later), and featuring only "a small number of code transformations that change the control flow of a program significantly". We rely on state-of-the-art technology, and we can handle most optimizations (see Table 1 for details). In a more recent implementation, Kirner et al. rely on source-to-source transformations, while we focus on traceability within the compiler, down to the code generator.

B 1 B 2 B 3 B 4 B 7 B 6 L: X min ,X max B 5
Objective function

X i∈CF G fi × Ti Structural constraints f1 =1 f12 + f62 =f23 = f2 f23 =f34 + f35 = f3 f34 =f46 = f4 f35 =f56 = f5 f46 + f56 =f62 + f67 = f6 Additional constraints f6 ≤ Xmax f4 ≤ 2 × f5

BACKGROUND: WCET CALCULATION AND EXPRESSION OF FLOW INFOR-MATION

WCET calculation using IPET

The static WCET calculation method used in this paper is the most common technique, named IPET for implicit path enumeration technique [START_REF] Li | Performance analysis of embedded software using implicit path enumeration[END_REF]. This method operates on control flow graphs (CFG), extracted from binary code. IPET models the WCET calculation problem as an Integer Linear Programming (ILP) formulation.

An example CFG is depicted in the left part of Figure 3. Branch free sequences of code (basic blocks) are depicted as circles, whereas arrows represent possible flows between basic blocks. The example program includes one loop, depicted by a rectangular box. Notation Xmin, Xmax states that the loop iterates at least Xmin times, and at most Xmax times.

The right part of Figure 3 depicts the ILP system used to calculate the WCET. Every basic block i has a worst-case execution time, denoted as Ti, and considered constant in the ILP system. Calculating the WCET is done by maximizing the objective function, in which fi represents the execution count of basic block i. The control flow is subject to structural flow constraints, that come directly from the structure of the CFG and are generated automatically. From top to bottom, the first one states that the entry point to be analyzed is executed exactly once. The next constraints state that the execution count of a basic block is equal to the sum the execution counts of its incoming edges, as well as outgoing edges, where fij represents the execution count of the edge from node i to j. Finally, additional constraints specify flow information that cannot be obtained directly from the control flow graph. The first kind of additional information is loop information (f6 ≤ Xmax in the example). It gives the maximum number of iterations for loops, and is mandatory for WCET estimation. Some other linear constraints such as f4 ≤ 2 × f5 may also be specified to constrain the relative numbers of executions of basic blocks in the CFG. Additional constraints may be inserted manually by the programmer, through annotations, or be obtained automatically using static analysis methods.

Notations and assumptions

Transformation of flow information operates on the program control flow graph (CFG) 4 . A CFG is a (possibly cyclic) directed graph made of a set of nodes N representing basic blocks, and a set of edges E representing control flow between basic blocks.

In the example program of Figure 3, we have:

CFG = {N , E} N = {B1, B2, B3, B3, B4, B5, B6, B7} E = {B1 → B2, B2 → B3, B3 → B4, B3 → B5, B4 → B6, B5 → B6, B6 → B2, B6 → B7}
The proposed framework for traceability of flow information assumes reducible and properly nested loops. Information on loop nesting is captured through the LoopScope data structure, made of a set of pairs Lo, Li with Lo and Li as loops. Li is the inner loop and is completely nested in the outer loop Lo. This data structure is useful because some compiler optimizations involve multiple loops (e.g. loop interchange), their maximum number of iterations have to be modified jointly. The LoopScope data structure for our running example depicted in Figure 4 contains: LoopScope = { , Lx , Lx, Ly } with " " denoting the absence of enclosing loop for the outermost loop.

Loop bounds are the maximum number of executions of any node in the loop body, regardless of the position of the node(s) testing the loop exit. Without loss of generality, local loop bounds are considered, representing the maximum number of iterations of a loop for each entry. Loop bounds are constant and context-independent.

A FRAMEWORK FOR THE TRACEABIL-ITY OF FLOW INFORMATION

In this section, we present a transformation framework that conveys flow information from source code level to machine code level. The transformations are expressed in an abstract way, independently of the compiler infrastructure in which they will be integrated.

The transformation framework, for each compiler optimization, defines a set of formulas, that rewrite available flow constraints into new constraints. As mentioned in Section 3, flow information is available in two forms:

• Loop bounds, for every program loop:

Loopbounds = { Lx, l bound , u bound }
with Lx the loop identifier and l bound and u bound denoting respectively the minimum and maximum number of iterations for loop Lx, and this for each entry in Lx.

• Additional flow constraints that are linear relations on execution counts of basic blocks (fi):

Constraints = {C 1 + X i∈CF G C 2 ×f i op C 3 + X j∈CF G C 4 ×f j }
with C 1/2/3/4 non-negative integer constants and op an operator in set {=, >, ≥, <, ≤}. These constraints, to be rewritten jointly with code optimizations, do not include the structural constraints presented in Section 3, but only additional flow information. Indeed, structural constraints can be derived automatically from the CFG at the end of the compilation process.

The transformation framework supports any linear constraint on executions counts of basic blocks. However, in the implementation presented in Section 5, we focus on tracing only the loop bounds.

Note that loop bounds, when finally used to calculate WCET using IPET, will eventually be encoded as linear constraints. However, as illustrated later in the paper, keeping the notion of loops is a richer information, and it integrates more naturally in a compiler.

Transformation rules

There are three basic rewriting rules for transforming flow information: change rule, removal rule and addition rule.

Change rule

This rule is used to express changes of the execution counts of basic blocks or changes of loop bounds, resulting from compiler optimizations. It is expressed as α → β, which means α is substituted by β in the constraints.

In case of a change in the execution count of a basic block, α is fi, with i one of the basic blocks in the original CFG. β is an expression

{C + P j∈newCF G M × fj}, with C a constant
and M a multiplicative coefficient, that can be either a nonnegative integer constant, an interval [a,b] or an interval [a,+∞) in which both a and b are non-negative constants. For example, given the constraint 3fA ≤ 7fD and the rule fA → 4fB, we transform the old constraint into the new constraint 3 × (4 × fB) ≤ 7 × fD.

In case of a change in loop bounds, α is a loop bound constraint Lx l bound , u bound , with Lx ⊂ original CFG, and

f o r ( i =0; i <10; i ++) f o r ( j =0; j <20; j ++) a [ i ] [ j ] = i + j ; f o r ( j =0; j <20; j ++) f o r ( i =0; i <10; i ++) a [ i ] [ j ] = i + j ;
(a) Original source code (b) Optimized code

Removal rule

This rule is used whenever a basic block or a loop is removed from the CFG due to some code optimization. We express it as α → ∅. α can be fi (i ∈ original CFG) or Lx l bound , u bound (Lx ⊂ original CFG) depending on the object (basic block, loop) that is removed. Through this transformation, α is deleted from the constraints. For example, with initial constraint 3 × fA ≤ 7 × fD, the rule fA → ∅ removes the constraint. With initial constraint 3 × fA + 2 × fB ≤ 7 × fD and rule fA → ∅, we get the new constraint 2 × fB ≤ 7 × fD.

Addition rule

This last rule is meant to be used by optimizations that add new objects (basic block/loop) in the CFG. When a new term is introduced into the CFG, the new constraint is added directly. The constraint should be linear, and should only involve objects (basic blocks, loops) from the new CFG.

For example, if a new constraint 3×fA ≤ 7×fD appears in the rules set, we just add this constraint into the constraints set.

Supported compiler optimizations

We defined transformation rules for LLVM optimizations at the -O1 level. Since the number of optimizations is relatively limited, we also considered other standard compiler optimizations. Table 1 lists the supported optimizations. Note that control flow preserving optimizations do not need specific traceability of flow information, and thus are not listed. Due to space constraints, the full list of rules will be published as a separate report, posted on the project's website 5 . The subsequent paragraphs illustrate our approach through two case studies: interchange, and unrolling.

Case studies

Loop Interchange

Loop interchange is a standard loop optimization exchanging the order of two iteration variables used by a loop nest. The variable used in the inner loop switches to the outer loop, and vice versa. Loop interchange is typically applied to ensure that elements of a multi-dimensional array are accessed in the order in which they are represented in memory, improving locality of reference and thus performance in architectures with data caches. An example of loop interchange performed at the source code level is given in Fig- ure 5.

The modifications of the CFG due to loop interchange are shown in Figure 6. In the figure, it is assumed that the structure of the CFG (structure of loops, basic blocks) is 5 http://wsept.inria.fr The transformation of flow information for the loop interchange optimization only requires the application of the change rule since there is no addition or removal of nodes and basic blocks. The set of rules describing the flow transformation is given below.

LX ˙Xmin , Xmax ¸→LX ˙Ymin , Ymax ĻY ˙Ymin , Ymax ¸→LY ˙Xmin , Xmax fB →[X min . . . Xmax]f B ′ fA →[ 1 Ymax . . . 1 Y min ]f A ′ fD →[X min . . . Xmax]f D ′ fE →[ 1 Ymax . . . 1 Y min ]f E ′ (1)
The first two lines show that the respective loop bounds of the two loops have been swapped. The following four lines update the constraints of the basic blocks to reflect the alteration of their execution count. For example, the execution count fB of node B changes from [X min . . . Xmax] × [Y min . . . Ymax] to [Y min . . . Ymax], so the original fB is replaced by the [X min . . . Xmax]fB. If Y min is 0, we should use +∞ instead of 1 Y min .

Loop Unrolling

Another example used to demonstrate constraint transformation is Loop Unrolling, illustrated in Figure 1. Loop unrolling replicates the loop body a number of times, called the unrolling factor. Unrolling reduces loop branching overhead and increase instruction level parallelism.

The modifications of the CFG are shown in Figure 7, in the general case where the number of iterations is not known to be a multiple of the unrolling factor. In the figure, the loop body B is replicated k times and the structure of the CFG is changed; a new loop is created to cope with number of iterations not multiple of k. The loop bound of these two The transformation of flow information for loop unrolling requires the application of the change rule and the addition rule because of the addition of the new loop. The set of rules describing the flow transformation is given below.

P A B C E L x : X min ,X max P A' B 1 C' L x : X min /k,X max /k A'' B'' C'' E L y : 0,k-1 B k
LX ˙Xmin , Xmax ¸→LX fi ⌊ X min k ⌋, ⌊ Xmax k ⌋ fl LY 0, k -1 fA →k × f A ′ + f A ′′ fC →k × f C ′ + f C ′′ fB →fB 1 + . . . + fB k + f B ′′ (2)
The first line (change rule) expresses that the loop bound of the first loop is derived from the loop bound of the original loop by dividing it by the unrolling factor k. The second line (addition rule) expresses the loop bound of the new loop. The following three lines (change rules) update the constraints on the basic blocks to reflect the alteration of their execution count. For example, the execution count fA of node A is replaced by k × f A ′ + f A ′′ .

IMPLEMENTATION IN THE LLVM COM-PILER INFRASTRUCTURE

The LLVM compiler infrastructure

We integrated the transformation rules described in Section 4 in the LLVM compiler infrastructure [START_REF] Lattner | LLVM: A compilation framework for lifelong program analysis and transformation[END_REF], version 3.4. LLVM is a collection of modular and reusable compiler and toolchain technologies. As shown in Figure 8, it consists in a three-phase compiler. The first phase is the compiler frontend, named clang, which parses, validates and diagnoses errors in the C/C++ code, and then translates the code into the LLVM Intermediate Representation (IR). Then, in a second phase, named opt (the LLVM optimizer), a series of analyses and optimizations are performed, with the objective of improving the code quality. Finally, the compiler backend, named codegen produces native machine code from IR. LLVM is built around the notion of passes. A pass performs an action on the program. They consist in Transform and Analysis passes (and a few Utility passes). Analysis passes compute various information relevant to subsequent transform passes, such as dominator trees, alias analysis, or loop forests. Each pass can specify its impact on already available information. It may specify that particular information is preserved (allowing further passes to reuse it without recomputing it), while others are invalided, hence destroyed, and must be recomputed.

Yellow boxes in Figure 8 represent external components we added for our WCET flow (oRange and Heptane -described in subsequent sections). Furthermore, we modified opt in three places: the parser, to read in annotations from an external file; the individual transformations to convey annotations all the way down; and the IR writer to dump the updated annotations to file.

Representation and transfer of flow information (WCETInfo)

We added to LLVM a new type of information, named WCETInfo, to be attached to the program. Its current purpose is to map loops (Loop objects in LLVM) to the corresponding estimate of loop bounds. Similarly to other information in LLVM, transformation passes may have one of the following behaviors with respect to WCETInfo:

Preserve WCETInfo. This is when the transformation does not modify loops, or when loops are modified, but we know that their bound remain unchanged. Constant propagation is an example of this case.

Update WCETInfo. This happens when loops are modified, but we are able to apply the corresponding transformation to the loop bound information, according to one of the rules of Section 4.

Delete WCETInfo. This occurs when the transformation is unknown, or is known to be too complex to propagate loop bounds correctly. These optimizations are WCET unfriendly, and may render the WCET impossible to compute. Thus, they should be disabled from a compiler targeting real-time systems.

The default for every pass is to delete the WCETInfo, as this is the safe behavior. The modification of opt to read loop bounds reads bounds generated by the oRange static analysis tool [START_REF] De Michiel | Partial Flow Analysis with oRange (short paper)[END_REF]. Loop bounds are expressed in the portable flow fact annotation language FFX [START_REF] Zwirchmayr | FFX: A Portable WCET Annotation Language[END_REF]. Code generation was also modified after all optimization passes to output the final loop bounds in the binary code in a specific section of the binary, for subsequent use in the WCET calculation.

As a side product of using automatically generated loop bounds, we were able to compare the loop bounds generated by oRange with those available inside LLVM using the scalar evolution analysis pass. All loop bounds calculated by scalar evolution were also computed by oRange and the bounds were identical.

EXPERIMENTAL RESULTS

The benefits of compiler optimizations cannot be assessed by enabling them one-at-a-time: optimizations depend on one-another, and many have an impact only when many others have been applied before to prepare the code. In the following, we first examine the impact on WCET of all LLVM optimizations of level (-O1). Then we evaluate the impact of an optimization by disabling it, and comparing its negative effect (we first disabled one optimization out of n, then two out of n).

Experimental Setup

We demonstrate the impact of our mechanism on program optimization and annotation transformation with the standardized set of WCET benchmarks from Mälardalen University 6 .

WCET are estimated using the Heptane timing analysis tool [START_REF] Colin | Worst case execution time analysis for a processor with branch prediction[END_REF], implementing the Implicit Path Enumeration Technique (IPET) for WCET calculation. The ILP solver is CPLEX. For the scope of this paper, to ease the understanding of results, a very simple hardware model is used by Heptane. A 32-MIPS processor is considered, with a 2-level hierarchy of caches and a perfect data cache. The L1 instruction cache is a 2-way 512-byte cache with 8-byte lines, and the L2 cache is a 8-way 16-Kbyte cache with 64-byte lines (the L1 cache size is voluntarily small to match the small size of Mälardalen benchmarks). The cache latency is set to 1 cycle for L1, 10 cycles for L2, and the memory latency to 50 cycles. Both cache levels implement LRU replacement. No instruction-level parallelism (pipeline) is assumed in the architecture.

Code is compiled to assembly using LLVM. The GNU assembler then compiles assembly code to binary that is used to feed Heptane. Optimized codes use the -O1 option of 6 http://www.mrtc.mdh.se/projects/wcet/benchmarks.html LLVM (with the exception of inlining and sparse conditional constant propagation which are not fully supported yet). Note that LLVM has most of its optimizations in -O1.

Higher levels only add global value numbering, vectorization, global dead code elimination, and constant merging for -O2, and argument promotion for -O3.

Impact of optimizations on WCET

Figure 9 shows the impact of compiler optimizations on the WCET computed by Heptane. Results are normalized with respect to the code compiled at -O0.

Firstly, we are able to transform all flow information from C code to binary without loss of information. This is shown by the fact that we can compute the WCET of all benchmarks (a single missing loop bound would make the computation impossible).

Secondly, we observe that option -O1 yields to an important reduction of estimated WCETs: 60 % in average, and up to 86 % (optimized WCET is 14 % of unoptimized) for benchmark ludcmp, which contains deeply-nested loops.

Individual impact of optimizations (1-off)

Disabling instcombine and loop-rotate causes problems to the compilation flow of LLVM. Further optimizations crash, and cause an abort of LLVM. Loop rotation transforms toptested loops into bottom-tested loops. While this transformation has a marginal impact on performance, it is an enabler for others. We hypothesize that further optimizations assume this transformation has been applied, hence crash when we disable it. Instcombine also applies some normalization, such as moving constant operand of a binary operator to the right hand side. Again, further optimizations probably assume the IR is in a normal form and fail when it is not the case. Thus, we kept both optimizations enabled.

Table 2 reports our results. For each benchmark (horizontally), we report in the first row the WCET (in cycles) when all optimizations are enabled. Following rows report the estimated WCET when disabling each optimization individually. For example, in the bottom left corner, we see that disabling simplifycfg causes an increase of 7 % of WCET of bs. In other words, simplifycfg improves the estimate. On the contrary, it has an adversary impact on ud (last column): the WCET estimate is better by 2 % when mem2reg is not run. A dash sign means no change.

General Comments.

Disabling some optimizations has no impact on the WCET. Some simply do not apply to our real-time benchmarks. For example: all loops compute useful values, hence loop deletion has nothing to do; prune-eh removes unused exception handlers, which do not exist in C code. Others, such as tail call elimination or memcopy optimization recognize specific patterns that do not occur in our benchmarks. Globalopt considers global variables whose addresses are never taken, and optimizes away constant and write-only variables.

Some optimizations, such as loop-simplify, do modify the code. It turns out that, in our configuration and for our benchmarks, the WCET remains unaltered.

Register promotion is implemented by mem2reg. This is a key optimization that replaces costly memory accesses by much faster register uses. It is a priori surprising that turning it off does not result in major degradation. The reason is that sroa achieves the same effect. This is further discussed in Section 6.2.2.

Common subexpression elimination (early-cse) and induction variable canonicalization (indvars) are basic optimizations of any compiler targeting Average Case Execution Time (ACET). Our results show that they also have a dramatic impact on WCET. These two classic optimizations alone can improve the tightness of WCET by valuable amounts.

Code Layout and I-Cache Effects.

Some transformations result in a minor improvement or degradation (±2 % or so) of the WCET. We suspected this could be a random effect due to a slightly different code layout, resulting in marginally different misses in the cache. To validate our hypothesis, we re-executed the entire experiments, disabling the I-cache (i.e. assuming a perfect cache). As expected we observed that these differences vanish.

Scalar Replacement of Aggregates.

Disabling sroa only impacts ndes, but the effect is significant: it results in more than 44 % increase in WCET. Visual inspection confirms that this benchmark makes intensive use of small structs (of two and three elements) that can easily be promoted.

As mentioned, sroa also captures the register promotion, but this effect is visible when both optimizations are turned off (see Section 6.2.2).

Loop Invariant Code Motion.

Disabling licm has a dramatic impact on ud, increasing the WCET estimate by 98 %. However, assuming a perfect instruction cache, the impact is reduced to less than 5 %. Ud consists in depth-3 loop nests (LU decomposition). The compiler is able to hoist a few instructions outside the loops, explaining the slight WCET improvement.

When the cache is analyzed, and licm is not run, many instructions in loops that iterate more than 100 times cannot be proved resident in the cache after the first access. They are thus classified as always miss. The effect is exacerbated by the fact that cache lines in our setup are small.

Loop Unrolling.

Loop unrolling produces mixed results: it improves matmult (2 %) and ndes (12 %), but degrades ludcmp (-4 %), cnt (-21 %) and ud (-7 %). With perfect I-cache, loop unrolling is always worthwhile, improving cnt, ludcmp, matmult, ndes and ud respectively by 22 %, 5 %, 3 %, 1 %, and 5 %.

Table 2: Change in WCET when one optimization is disabled (1-off ). Reference is -O1. Positive numbers denote a beneficial effect of the optimization (WCET degrades when it is disabled).

Loop unrolling is well known to compiler developers to be a double-edged sword. Average performance improves as long as the working set stays in the cache. The additional misses in the instruction cache cancel the benefits of the optimization. Our results show that the same holds for WCET. In the case of cnt, the reason is slightly different. The loop is unrolled ten times (fully unrolled). Its new size is about 400 bytes, which fits in the L1 I-cache. However, due to the structure of the application, there is no reuse of this code. The increased number of cycles comes from additional cold misses. Note, though, that in case of reuse, additional capacity misses are expected, because the unrolled loop size is close to the cache size (512 bytes), and most of its contents is evicted.

Combined impact of optimizations (2-off)

As a final experiment, we disabled pairs of optimizations out of -O1. We tried all pairs. Given the amount of data, we only report highlights in Table 3.

The most effective optimizations for our benchmarks are early-cse, indvars, and licm. We often observe additive effects, with up to 2.47× increase in WCET estimate when licm and indvars are both disabled. While not reported here, this observation is generally true for our set of optimizations and benchmarks. fdct without early-cse and indvars is an exception, resulting in a minor degradation (-1 % vs. -1 % -2 % ∼ -3 %). However, with a perfect cache, we observe the opposite behavior, confirming that slightly different code layout is at play.

As for ACET, optimizations are not always additive. This is also true for WCET. It can be illustrated by the pair simplifycfg + early-cse. Bs shows a sub-additive impact, while on ndes the effect is amplified.

As anticipated in the previous section, sroa and mem2reg have overlapping effects. As mentioned in the LLVM documentation, sroa also performs alloca promotion, which serves the purpose of SSA formation and results in an effect similar to register promotion. Disabling both optimizations results is a considerable degradation of the WCET estimate.

CONCLUSION

Designers of real-time systems are required to compute the WCET of the components of their systems. This is accomplished by combining information provided at high level by programmers (e.g. loop bound information) and generated at low level by compilers. This combination is possible if a mapping is maintained between high-and low-level representations. Optimizing compilers typically break this simple mapping, and developers turn all optimizations off. We propose a framework, built within the LLVM compiler, that traces information through compiler optimizations. We illustrate it on loop bounds, and we show that many optimizations can be turned on. Not only do we not lose any precision, the resulting WCET is much tighter, even in the presence of CFG restructuring transformations such as loop unrolling. We also provide insight about the advantage of running particular optimization of the well accepted Mälardalen benchmarks.

Our ongoing work regarding C to binary traceability consists in extending traceability beyond loop bound information (e.g. mutually exclusive branches, which are common in C-code generated by Lustre). Another ongoing work is to introduce contextual information (e.g. semantics information that depend on the execution context, such as call context, number of the iteration, etc). Besides, we need to consider global loop bounds because they can result in more precise WCET when triangular loops are analyzed.

Figure 1 :

 1 Figure 1: CFG matching and WCET overestimation

Figure 2 :

 2 Figure 2: Overall flow

Figure 3 :

 3 Figure 3: CFG and WCET calculation using IPET

  X min ,X max L y : Y min ,Y max

Figure 4 :

 4 Figure 4: Running example including nested loops

Figure 5 :

 5 Figure 5: Loop interchange optimization

  Y min ,Y max L y : X min ,X max

Figure 6 :

 6 Figure 6: Loop interchange example. The left part of the figure shows the original CFG, whereas the right part shows the optimized one.

Figure 7 :

 7 Figure 7: Loop unrolling example. The left part of the figure shows the original CFG, whereas the right part shows the optimized one.

Figure 8 :

 8 Figure 8: Implementation of traceability in LLVM

Figure 9 :

 9 Figure 9: Impact of optimizations (-O1) on WCET. The y-axis represents the WCET with optimizations, normalized with respect to the WCET without optimization (-O0)

Table 1 :

 1 Deletion of loops with non-infinite computable trip counts that have no side effects and do not contribute to the computation of the function's return value loop rotation Replacement of a loop with the exit test at the start of a loop with an equivalent one, with the test at the end of the loop. loop-unroll Replication of loop body by some unrolling factor to reduce branches and increase instruction-level parallelism Other supported optimizations not implemented in LLVM if simplification Removal of empty or not taken branches in conditional constructs. if conversion Replacement of flow of control by predicated instructions when applicable loop interchange Exchange the order of two loops in a perfect loop nest. In general, it switches the outer loop to the inner position and vice versa. loop fission Split a loop into multiple loops with the same iteration space as the original one and a subset of the original loop body. loop fusion Replace multiple loops with the same loop bound with a single one Supported optimizations. The optimizations included in LLVM appear on top.

	Optimization	Description
	name
	Redundancy elimination, control-flow and low-level optimizations of LLVM
	adce	Aggressive dead code elimination
	correl.-prop.	Correlated value propagation
	deadargelim	Deletes dead arguments from internal functions
	dse	Intra basic-block elimination of redundant stores
	early-cse	Early common subexpression elimination
	functionattrs	Interprocedural deduction of function attributes
	globalopt	Transforms simple global variables that never have their address taken
	ipsccp	Interprocedural conditional constant propagation
	jump-threading	Reduction of the number of branch instructions in case of chained branching.
	mem2reg	Promote memory reference to be register references
	memcpyopt	Transformations related to eliminating calls to memcpy
	prune-eh	Remove unused exception handling info
	reassociate	Reassociate expressions to promote better constant propagation
	simplifycfg	Dead code elimination and basic block merging
	sroa	Scalar replacement of aggregates
	tailcallelim	Elimination of tail recursion
	Loop Optimizations of LLVM
	loop-simplify	Canonicalize natural loops to make subsequent analyses and transformations simpler and more effective
	lcssa	Transform loops in closed SSA form
	licm	invariant code motion (move invariant code outside loop body)
	loop-unswitch	Transforms loops that contain branches on loop-invariant conditions to have multiple loops
	indvars	Canonicalize induction variables: analyzes and transforms the induction variables into simpler forms suitable
		for subsequent analysis and transformation
	loop-idiom	Loop idiom recognizer: transforms simple loops into a non-loop form
	loop-deletion

http://www.otawa.fr

http://ls12-www.cs.tu-dortmund.de/daes/en/ forschung/wcet-aware-compilation.html

For presentation clarity, we will concentrate in this paper on a single CFG, although the framework supports multiple functions and function calls.

Acknowledgments

The research was funded by W-SEPT 5 , a collaborative research project focusing on identification and traceability of semantic information for worst-case execution time estimation. W-SEPT is funded by ANR under grant ANR-12-INSE-0001, and supported by the competitiveness clusters

Aerospace Valley and Minalogic. The work was also partially funded by COST Action IC1202: Timing Analysis On Code-Level (TACLe). We express special thanks to Damien Hardy for his time solving tricky issues when using Heptane and his comments on earlier versions of this paper.