Maroua Maalej
email: maroua.maalej@ens-lyon.fr

Vitor Paisante
email: paisante@dcc.ufmg.br

Ramos Pedro
email: pedroramos@dcc.ufmg.br

Laure Gonnord
email: laure.gonnord@ens-lyon.fr

Fernando Pereira
email: fernando@dcc.ufmg.br

Pedro Ramos

Fernando Magno

Quintão Pereira

Pointer Disambiguation via Strict Inequalities

Keywords: Alias analysis, range analysis, speed, precision

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Pointer disambiguation consists in determining if two pointers, p 1 and p 2 , can refer to the same memory location. If overlapping happens, then p 1 and p 2 are said to alias. Pointer disambiguation has been focus of much research [START_REF] Andersen | Program Analysis and Specialization for the C Programming Language[END_REF][START_REF] Hardekopf | The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code[END_REF][START_REF] Hind | Pointer analysis: Haven't we solved this problem yet?[END_REF][START_REF] Steensgaard | Points-to analysis in almost linear time[END_REF], since the debut of the first alias analysis approaches [START_REF] Banning | An efficient way to find the side effects of procedure calls and the aliases of variables[END_REF][START_REF] Spillman | Exposing side-effects in a PL/I optimizing compiler[END_REF]. Today, state-of-the-art algorithms have acceptable speed [START_REF] Hardekopf | The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code[END_REF][START_REF] Pereira | Wave propagation and deep propagation for pointer analysis[END_REF], good precision [START_REF] Whaley | Cloning-based context-sensitive pointer alias analysis using binary decision diagrams[END_REF] or meet each other halfway [START_REF] Hardekopf | Flow-sensitive pointer analysis for millions of lines of code[END_REF][START_REF] Sui | Sparse flow-sensitive pointer analysis for multithreaded programs[END_REF]. However, understanding the relationships between memory references in programming languages that support pointer arithmetics remains challenging.

Pointer arithmetics come from the ability to associate pointers with offsets. Much of the work on automatic parallelization consists in the design of techniques to distinguish offsets from the same base pointer. Michael Wolfe [START_REF] Wolfe | High Performance Compilers for Parallel Computing[END_REF]Ch.7] and Aho et al. [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF]Ch.11] have entire chapters devoted to this issue. State-of-the-art approaches perform such distinction by solving diophantine equations, be it via the greatest common divisor test, be it via integer linear programming, as Rugina and Rinard do [START_REF] Rugina | Symbolic bounds analysis of pointers, array indices, and accessed memory regions[END_REF]. Other techniques try to associate intervals, numeric or symbolic, with pointers [START_REF] Balakrishnan | Analyzing memory accesses in x86 executables[END_REF][START_REF] Oh | Selective contextsensitivity guided by impact pre-analysis[END_REF][START_REF] Paisante | Symbolic range analysis of pointers[END_REF][START_REF] Yong | Pointer-range analysis[END_REF], presenting different ways to build Balakrishnan and Reps' notion of value sets. And yet, as expressive and powerful as such approaches are, they fail to disambiguate locations that are obviously different, as v[i] and v[j], in the loop:

for(i = 0, j = N; i < j; i++, j--) v[i] = v[j];

In this paper, we present a simple and efficient solution to this shortcoming. We say that v[i] and v[j] are obviously different locations because i < j. There are techniques to compute less-than relations between integer variables in programs [START_REF] Bodik | ABCD: eliminating array bounds checks on demand[END_REF][START_REF] Logozzo | Pentagons: a weakly relational abstract domain for the efficient validation of array accesses[END_REF][START_REF] Logozzo | Pentagons: A weakly relational abstract domain for the efficient validation of array accesses[END_REF][START_REF] Miné | The octagon abstract domain[END_REF]. Nevertheless, so far, they have not been used to disambiguate pointer locations. The insight that such techniques are effective and useful to such purpose is the key contribution of this paper. However, we go beyond: we rely on recent advances on the construction of sparse dataflow analyses [START_REF] Tavares | Parameterized construction of program representations for sparse dataflow analyses[END_REF] to design an efficient way to solve less-than inequalities. The sparse implementation lets us view this problem as an instance of the abstract interpretation framework; hence, we get correctness for free. The end result of our tool is a less-than analysis that can be augmented to handle different program representations, and that can increase in nontrivial ways the ability of compilers to distinguish pointers.

To demonstrate this last statement, we have implemented our static analysis in the LLVM compiler [START_REF] Lattner | LLVM: A compilation framework for lifelong program analysis & transformation[END_REF]. We show void ins_sort(int* v, int N) { int i, j; for (i = 0; i < N -1; i++) { for (j = i + 1; j < N; j++

) { if (v[i] > v[j]) { int tmp = v[i]; v[i] = v[j]; v[j] = tmp; } } } } void partition(int *v, int N) {
int i, j, p, tmp; p = v[N/2]; for (i = 0, j = N -1;; i++, j--) { while (v[i] < p) i++; while (p < v[j]) j--; empirically that industrial-quality alias analyses still leave unresolved pointers which our simple technique can disambiguate. As an example, we distinguish 11,881 pairs of pointers in SPEC's lbm, whereas LLVM's analyses distinguish 1,888. Furthermore, by combining our approach with basic heuristics, we obtain even more impressive results. For instance, our less-than check increases the success rate of LLVM's basic disambiguation heuristic from 48.12% (1,705,559 queries) to 64.19% [START_REF] Alves | Runtime pointer disambiguation[END_REF]274,936) in SPEC's gobmk.

if (i >= j) break; tmp = v[i]; v[i] = v[j]; v[j] = tmp; } } (a) (b)

Overview

To motivate the need for a new points-to analysis we show its application on the programs seen in Figure 1. The figure displays the C implementation of two sorting routines that make heavy use of pointers. In both cases, we know that memory positions v[i] and v[j] can never alias within the same loop iteration. However, traditional points-to analyses cannot prove this fact. Typical implementations of these analyses, built on top of the work of Andersen [START_REF] Andersen | Program Analysis and Specialization for the C Programming Language[END_REF] or Steensgaard [START_REF] Steensgaard | Points-to analysis in almost linear time[END_REF], can distinguish pointers that dereference different memory blocks; however, they do not say much about references ranging on the same array.

There are points-to analyses designed specifically to deal with pointer arithmetics [START_REF] Alves | Runtime pointer disambiguation[END_REF][START_REF] Balakrishnan | Analyzing memory accesses in x86 executables[END_REF][START_REF] Nazaré | Validation of memory accesses through symbolic analyses[END_REF][START_REF] Paisante | Symbolic range analysis of pointers[END_REF][START_REF] Rugina | Symbolic bounds analysis of pointers, array indices, and accessed memory regions[END_REF][START_REF] Rus | Hybrid analysis: Static and dynamic memory reference analysis[END_REF][START_REF] Sui | Loop-oriented array-and field-sensitive pointer analysis for automatic SIMD vectorization[END_REF][START_REF] Van Engelen | A unified framework for nonlinear dependence testing and symbolic analysis[END_REF][START_REF] Wilson | Efficient context-sensitive pointer analysis for c programs[END_REF]. Still, none of them works satisfactorily for the two examples seen in Figure 1. The reason for this ineffectiveness lays on the fact that these analyses use range intervals to disambiguate pointers. In our examples, the ranges of integer variables i and j overlap. Consequently, any conservative range analysis, à la Cousot [START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF], once applied on Figure 1 (a), will conclude that i exists on the interval [0, N -2], and that j exists on the interval [1, N -1]. Because these two intervals have non-empty intersection, points-to analyses based on the interval lattice will not be able to disambiguate the memory accesses at lines 6-8 of Figure 1 (a). The same holds true for the memory accesses in Figure 1 (b).

The technique that we introduce in this paper can disambiguate every use of v[i] and v[j] in both examples. The key to this success is the observation that i < j at every program point where we have an access to v. We conclude that i < j by means of a "less-than check". A less-than check is a relationship between two variables that is true whenever we can prove -statically -that one holds a value lesser than the value stored in the other. In Figure 1 (a), we know that i < j because of the way that j is initialized, within the for statement at line 4. In Figure 1 (b), we know that i < j due to the conditional check at line 7.

A more precise alias analysis brings many advantages to compilers. One of such benefits is optimizations: the extra precision gives compilers information to carry out more extensive transformations in programs. Notice that the pointer analysis that we propose in this paper provides weaker guarantees than more traditional approaches. Continuing with our example, the pointers v[i] and v[j] in Figure 1 (a &b) do, indeed, alias across the entire loop nest, albeit not at the same time. As we shall discuss in Section 3.5, if we say that two pointers do not alias, then they will never alias at any program point where they are simultaneously alive. This property is strong enough to support most of the classic compiler optimizations: constant propagation, value numbering, subexpression elimination, scheduling, etc. However, our technique cannot be used with optimizations that modify the iteration space of programs, such as loop fission and fusion.

The Less-Than Check

This section introduces a dataflow analysis whose goal is to construct a "less-than" set for each variable x (pointer or numeric, as we will discuss in Section 3.6). We denote such an object by LT(x). As we prove in Section 3.5, the important invariant that this static analysis guarantees is that if x ∈ LT(x), then x < x at every program point where both variables are alive. Our ultimate goal is to use this invariant to disambiguate pointers, as we explain in Section 3.6.

The Core Language

We use a core language to formalize the developments that we present in this paper. Figure 2 shows the syntax of this language. Our core language contains only those instructions that are essential to describe our static analysis. The Integer constants ::= {c 1 , c 2 , . . .}

Variables

::= {x 1 , x 2 , . . .}

Program (P)

::= { 1 : I 1 ; . . . , n : I n ; }

Instructions (I) ::= -Addition | x 0 = x 1 + x 2 -φ-function | x 0 = φ(x 1 : 1 , . . . , x n : n ) -Comparison | (x 1 < x 2 ) ? goto t : goto f Figure 2.
The syntax of our language. Variables have scalar type, e.g., either integer or pointer.

x 0 = [0, 1] x 1 = x 0 + 1 x 2 =ɸ (x 1 , x 3 ) x 3 = x 2 + 1 x 4 = x 2 -2 (x 4 < x 1 )?
x 6 =ɸ (x 4 , x 3 , x 4 ) true false reader can augment it with other assembly instructions, to make it as expressive as any industrial-strength program representation. As a testimony to this fact, the implementation that we describe in Section 4 comprises the entire LLVM intermediate representation. Figure 2 describe programs in Static Single Assignment form [START_REF] Cytron | Efficiently computing static single assignment form and the control dependence graph[END_REF]; therefore, it contains φ-functions. Additionally, it contains arithmetic instructions and conditional branches. These two kinds of instructions feed our static analysis with new information. EXAMPLE 3.1. Figure 3 describes a program in our core language. This is an artificial example, whose semantics is immaterial. Figure 3 illustrates a few key properties of the strict SSA representation: (i) the definition point of a variable dominates all its uses, and (ii) if two variables interfere, one of them is alive at the definition point of the other. Such properties will be useful in Section 3.5.

Program Representation

We want to implement a sparse dataflow analysis. Sparsity is good for: (i) time and space, as it reduces from cubic to quadratic (on the number of variables) the amount of information that needs to be stored; and (ii) correctness, as it simplifies all the proofs of theorems. A dataflow analysis is said to be sparse if it runs on a program representation that ensures the Static Single Information (SSI) Property [START_REF] Tavares | Parameterized construction of program representations for sparse dataflow analyses[END_REF]. To keep this paper self-contained, we quote Tavares et al.'s notion of single information property: DEFINITION 3.2 (Static Single Information Property). A dataflow analysis bears the static single information property if it always associates a variable with the same abstract state at every program point where that variable is alive.

Instructions (I) ::= -Addition | x 0 = x 1 + x 2 -Subtraction | x 0 = x 1 -n x 2 = x 1 -φ-function | x 0 = φ(x 1 : 1 , . . . , x n : n ) -Comparison | (x 1 < x 2 )? t : x 1t , x 2t f : x 1f , x 2f
Following Tavares et al. [START_REF] Tavares | Parameterized construction of program representations for sparse dataflow analyses[END_REF], to ensure the SSI property, we split the live range of every variable x at each program point where new information about x can appear. The live range of a variable v is the collection of program points where v is alive. To split the live range of x at a point , we create a copy x = x at , and rename uses of x at every program point dominated by . We shall write dom to indicate that dominates , meaning that any path from the beginning of the control flow graph to must cross . There are three situations that create new less-than information about a variable x:

1. x is defined. For instance, if x = x + 1, then we know that x < x;

2.
x is used in a subtraction, e.g,. x = x + n, n < 0. In this case, we know that x < x;

3.
x is used in a conditional, e.g., x < x . In this case, we know that x < x at the true branch, and x ≤ x at the false branch.

The Support of Range Analysis on Integer Intervals. The SSA representation ensures that a new name is created at each program point where a variable is defined. To meet the other two requirements, we split live ranges at subtractions and after conditionals. Going back to Figure 2, we see that our core language contains only syntax for arithmetic additions. However, we can use range analysis to know that one, or the two, terms of an addition are negative. Range analysis [START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF] is a static dataflow analysis that associates each variable x to an interval R(x) = [l, u], {l, u} ⊂ N, l ≤ u. The efficient and precise computation of range analysis has been researched extensively in the literature, and we shall not discuss it further. In our experiments, we have used the implementation of Rodrigues et al., which inserts guards in programs to track integer overflows [START_REF] Rodrigues | A fast and low overhead technique to secure programs against integer overflows[END_REF]. Given

x 1 = x 2 + x 3 , where R(x 2 ) = [l 2 , u 2 ] and R(x 3 ) = [l 3 , u 3 ],
we have a subtraction if u 3 < 0 or u 2 < 0. If both variables have positive ranges, then we have an addition. Otherwise, we have an unknown instruction, which shall not generate constraints.

(x 4 < x 1 )?

⟨x 4t = x 4 ⟩ ⟨x 1t = x 1 ⟩ ⟨x 4f = x 4 ⟩ ⟨x 1f = x 1 ⟩ (x 4 < x 1 )? l t l f l t l f ⟼ x 1 = x 2 + n ‖⟨x 3 = x 2 ⟩ x 1 = x 2 + n ⟼ l' l'
rename x 4 to x 4t and rename x 1 to x 1t at any block l if l t dom l ren. x 4 to x 4f and ren. Our live range splitting strategy leads to the creation of a different program representation. Figure 4 shows the instructions that constitute the new language. Figure 5 shows the two syntactic transformations that convert a program written in the syntax of Figure 2 into a program written in the syntax of Figure 4. We let x 0 = x 1 -n x 2 = x 1 denote a composition of two statements, x 0 = x 1 -n and x 2 = x 1 . The second instruction splits the live range of x 1 . Both statements happen in parallel. Thus, x 0 = x 1 -n x 2 = x 1 does not represent an actual assembly instruction; it is only used for notational convenience. Similarly, when transforming conditional tests, we let x 1t = x 1 , x 2t = x 2 denote two copies that happen in parallel: x 1t = x 1 , and x 2t = x 2 . Whenever there is no risk of ambiguity, we write simply x 1t , x 2t , as in Figure 4. Parallel copies and φ-functions are removed before code generation, after the analyses that require them have already run. This step is typically called SSA-Elimination phase. EXAMPLE 3.3. Figure 6 shows the result of applying the rules seen in Figure 5 onto the program in Figure 3.

x 1 to x 1f at l if l f dom l rename x 2 to x 3 at l if l' dom l (a) (b) R(n) = [l, u], u < 0

Constraint Generation

Once we have a suitable program representation, we use the rules in Figure 7 to generate constraints. These constraints determine the less-than set of variables. Constraint generation is O(|V|), where V is the set of variables in the target program. We have four kinds of constraints: init: Set the less-than set of a variable to empty: LT(x) = ∅.

x 0 = • x 1 = x 0 + 1 x 2 =ɸ (x 1 , x 3 ) x 3 = x 2 + 1 x 4 = x 2 -2 ‖⟨x 5 = x 2 ⟩ (x 4 < x 1 )? ⟨x 4t = x 4 ⟩ ⟨x 1t = x 1 ⟩ ⟨x 4f = x 4 ⟩ ⟨x 1f = x 1 ⟩
x 6 =ɸ (x 4 , x 3 , x 4t ) Figure 6. Figure 3 transformed by the rules in Figure 5.

x = • 1 LT(x) = ∅ x 1 = x 2 + n 2 LT(x 1 ) = {x 2 } ∪ LT(x 2 ) x 1 = x 2 -n x 3 = x 2 3 LT(x 3 ) = {x 1 } ∪ LT(x 2 ) LT(x 1 ) = ∅ x = φ(x 1 , . . . , x n ) 4 LT(x) = LT(x 1 ) ∩ . . . ∩ LT(x n ) (x 1 < x 2 )? t : x 1t , x 2t f : x 1f , x 2f 5                    LT(x 2t ) = {x 1t } ∪ LT(x 2 ) ∪ LT(x 1t ) LT(x 1t ) = LT(x 1 ) LT(x 2f ) = LT(x 2 ) LT(x 1f ) = LT(x 1 ) ∪ LT(x 2f )
> 0. If n is a variable, then R(n) = [l, u], l > 0.
union: Set the less-than set of a variable to be the union of another less-than set and a single element:

LT(x 3 ) = {x 1 } ∪ LT(x 2 ).
inter: Set the less-than set of a variable to be the intersection of multiple less-than sets:

LT(x) = LT(x 1 ) ∩ LT(x 2 ).
copy: Sets the less-than set of a variable to be the less-than set of another variable: LT(x) = LT(x ).

EXAMPLE 3.4. The rules in Figure 7 produce the following constraints for the program in Figure 6:

LT(x 0 ) = ∅, LT(x 1 ) = {x 0 } ∪ LT(x 0 ), LT(x 2 ) = LT(x 1 ) ∩ LT(x 3 ), LT(x 3 ) = {x 2 } ∪ LT(x 2 ), LT(x 4 ) = ∅, LT(x 5 ) = {x 4 } ∪ LT(x 2 ), LT(x 1t ) = {x 4t } ∪ LT(x 4t ) ∪ LT(x 1 ), LT(x 1f ) = LT(x 1 ), LT(x 4f ) = LT(x 1f ) ∩ LT(x 4 ), LT(x 4t ) = LT(x 4 ), LT(x 6 ) = LT(x 3 ) ∩ LT(x 4t ) ∩ LT(x 4 ).

Constraint Solving

Constraints are solved via a worklist algorithm. We initialize LT(x) to V, for every variable x. During the resolution process, elements are removed from each LT, until a fixed point is achieved. Theorem 3.7, in Section 3.5, guarantees that this process terminates. Constraint solving is equivalent to finding transitive closures; thus, it is O(|V| 3 ). In practice, we have observed an O(|V|) behavior, as we show in Section 4.

EXAMPLE 3.5. To solve the constraints in Example 3.4, we initialize every LT set to {x 0 , x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 1f , x 1t , x 4f , x 4t }, i.e., the set of program variables. The following sets are a fixed-point solution of this system:

LT(x 0 ) = LT(x 4 ) = LT(x 4t ) = LT(x 6 ) = ∅; LT(x 1 ) = LT(x 2 ) = LT(x 4f ) = LT(x 1f ) = {x 0 }; LT(x 3 ) = {x 0 , x 2 }; LT(x 5 ) = {x 0 , x 4 }; and LT(x 1t ) = {x 0 , x 4t }.

Properties

There are a number of properties that we can prove about our dataflow analysis. In this section we focus on two core properties: termination and adequacy. Termination ensures that the constraint solving approach of Section 3.4 always reaches a fixed point. Adequacy ensures that our analysis conforms to the semantics of programs. To show termination, we start by proving Lemma 3.6.

LEMMA 3.6 (Decreasing). If constraint resolution starts with LT(x) = V for every x, then LT(x) is monotonically decreasing or stationary.

Proof: The proof follows from a case analysis on each constraint produced in Figure 7, plus induction on the number of elements in LT. To prove Theorem 3.7, which states termination, we need to recall P V , the semi-lattice that underlines our less-than analysis. P V = {V, ∩, ⊥ = ∅, = V, ⊆} is the lattice formed by the partially ordered set of program variables. Ordering is given by subset inclusion ⊆. The meet operator (greatest lower bound) is set intersection ∩. The lowest element in this lattice is the empty set, and the highest is V. THEOREM 3.7 (Termination). The constraint resolution process terminates.

Proof: The proof of this theorem is the conjunction of two facts: (i) Constraint sets are monotonically decreasing; and (ii) they range on a finite lattice. Fact (i) follows from Lemma 3.6. Fact (ii) follows from the definition of P V .

We followed the framework of Tavares et al. [START_REF] Tavares | Parameterized construction of program representations for sparse dataflow analyses[END_REF] to build our intermediate program representation. Thus, we get correctness for free, as we are splitting live ranges at every program point where new information can appear. Lemma 3.8 formalizes this notion. LEMMA 3.8 (Sparcity). LT(x) is invariant along the live range of x.

Proof: The proof follows from case analysis on the constraint generation rules in Figure 7. By matching constraints with the syntax that produce them, we find that the abstract state of a variable can only change at its definition point. This property is ensured by the live range splitting strategy that produces the program representation that we use.

We close this section showing adequacy. In a nutshell, we want to show that if our constraint system determines that a variable x belongs into the less-than set of another variable x , then we know that x < x . This is a static notion: we consider the values of x and x that exist at the same moment during the execution of a program. Theorem 3.9 formalizes this observation. The proof of that theorem requires the semantics of the transformed language, whose syntax appears in Figure 4. However, for the sake of space, we omit this semantics. We assume the existence of a small-step transition rule →, which receives an instruction ι, plus a store environment Σ, and produces a new environment Σ . The store maps variables to integer values. Analogously, the constraints of Figure 7 show how instructions change the abstract state LT. We write ι LT LT to denote an abstract transition. We let |= model the following relation: if x ∈ LT(x), then Σ(x ) < Σ(x). If this relation is true for every element in the domain of Σ, then we write LT |= Σ. THEOREM 3.9 (Adequacy).

If LT 1 |= Σ 1 ∧ ι Σ 1 → Σ 2 ∧ ι LT 1 LT 2 , then LT 2 |= Σ 2 .
Proof: The proof happens by case analysis on the five instructions in Figure 7. For brevity, we show two cases: First case: ι is x1 = x2 + n. Notice that n > 0 because otherwise our range analysis would have led us to transform that instruction into a subtraction, or would have produced no constraint at all. Henceforth, we shall write "f \ a → b" to denote function update, i.e.: "λx COROLLARY 3.10 (Invariance). Let x i and x j be two variables simultaneously alive. If x i ∈ LT(x j ), then x i < x j .

.if x = a then b else f (x)" We have that x1 = x2 + n Σ1 → (Σ1 \ x1 → Σ1(x2) + n), and x1 = x2 + n LT1 (LT1 \ x1 → LT1(x2) ∪ {x2}). We look into possible vari- ables x ∈ LT1 \ x1 → LT1(x2) ∪ {x2}: • x = x2: the theorem is true because Σ1(x2) + n > Σ1 (
Proof: In a SSA-form program, if two variables interfere, then one is alive at the definition point of the other [START_REF] Budimlic | Fast copy coalescing and live-range identification[END_REF][START_REF] Hack | Register allocation for programs in SSA-form[END_REF][START_REF] Zhao | Formal verification of ssa-based optimizations for llvm[END_REF]. From Lemma 3.8, we know that LT(x) is constant along the live range of x. Theorem 3.9 gives us that this property holds at the definition point of the variables.

Pointer Disambiguation

Pointers The C standard refers to arithmetic types and pointer types collectively as scalar types [START_REF]The C programming language[END_REF]{ §6.2.5.21}. Notice that the less-than analysis that we have discussed thus far works seamlessly for scalars; thus, it also builds relations between pointers. For instance, the common idiom "for(int* pi = p; pi < pe; pi++);" gives us that pi < pe inside the loop. This fact justifies Definition 3.11 [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF]. Along similar lines, if p 1 = p + x 1 , we have that p ∈ LT(p 1 ); thus, Definition 3.11(2) lets us disambiguate a base pointer from its non-null offsets, e.g., p = p + n, if we know that n = 0. Definition 3.11 provides one, among several criteria, that can be used to disambiguate pointers. For instance, the C standard says that pointers of different types cannot alias. Aliasing is also impossible in well-defined programs between references derived from non-aliased base pointers. Additionally, derived pointers whose offsets have nonoverlapping ranges cannot alias, as discussed in previous work [START_REF] Balakrishnan | Analyzing memory accesses in x86 executables[END_REF][START_REF] Paisante | Symbolic range analysis of pointers[END_REF][START_REF] Rugina | Symbolic bounds analysis of pointers, array indices, and accessed memory regions[END_REF]. Thus, our analysis says nothing about p1 and p2 in scenarios as simple as: p1 = malloc(); p2 = malloc(), or p1 = p + 1; p2 = p + 2. Previous work is already able to disambiguate p1 and p2 in both cases. Our pointer disambiguation criterion does not compete against these other approaches. Rather, as we further explain in Section 5, it complements them.

Evaluation

To demonstrate that a "less-than" check can be effective and useful to disambiguate pointers, we have implemented an inter-procedural, context insensitive version of the analysis described in this paper in LLVM version 3.7. We achieve inter-procedurality by creating pseudo-instructions x f = φ(x 1 , . . . , x n ) for each formal parameter x f , and each actual parameter x i , 1 ≤ i ≤ n. Had we used an intra-procedural analysis, then we would have to assume that every formal parameter is bound to the range [-∞, +∞]. In this section we shall answer three research questions to evaluate the precision, the scalability and the applicability of our approach:

Precision: how effective are strict inequalities to disambiguate pairs of pointers?

Scalability: can the analysis described in this paper scale up to handle very large programs?

Applicability: can our pointer disambiguation method increase the effectiveness of existing program analyses?

In the rest of his section we provide answers to these questions. Our discussion starts with precision.

Precision

The precision of an alias analysis method is usually measured as the capacity of said method to indicate that two given pairs of pointers do not alias each other. To measure the precision of our method, we compare it against the techniques already in place in the LLVM compiler. Our metric is the percentage of pointer queries disambiguated. To generate queries, we resort to LLVM's aa-eval pass, which tries to disambiguate every pair of pointers in the program.

Our main competitor will be LLVM's basic disambiguation technique, the basic-aa algorithm. Henceforth, we shall refer to it as BA. This analysis uses several heuristics to disambiguate pointers, relying mostly on the fact that pointers derived from different allocation sites cannot alias in wellformed programs. In addition to the basic algorithm, LLVM 3.7 contains three other alias analyses, whose results we shall not use, because they have been able to resolve a very low number of queries in our experiments. Figure 8 shows the results of the three alias analyses when applied on the 100 largest benchmarks in the LLVM test suite. We have removed the benchmark TSVC from this lot, because its 36 programs were giving us the same numbers. This fact occurs because they use a common code base. Our method rarely disambiguates more pairs of pointers than BA. Such result is expected: most of the queries consist of pairs of pointers derived from different memory allocation sites, which BA disambiguates, and we do not analyze. The ISO C Standard prohibits comparisons between two references to separately allocated objects [START_REF]The C programming language[END_REF]{ §6.5.8p5}, even though they are used in practice [22, p.4].

Nevertheless, Figure 8 still lets us draw encouraging conclusions. There exist many queries that we can solve, but . "# Queries" is the total number of queries performed when testing a given benchmark. Percentages show the ratio of queries that yield"no-alias", given a certain alias analysis. The higher the percentage, the more precise is the pointer disambiguation method. We have highlighted the cases in which our less-than check has increased by 10% or higher the precision of LLVM's basic alias analysis.

BA cannot. For the entire LLVM test suite, our analysis (referred as LT), increases the precision of BA by 9.49% (56,192,064 vs 59,184,181 no-alias responses). Yet, in programs that make heavy use of pointer arithmetics, our results are even more impressive. For instance, in SPEC's lbm we disambiguate 11,881 pairs of pointers, whereas BA provides precise answers to only 1,888. And, even in situations where LT falls behind BA, the former can increase the precision of the latter non-trivially. As an example, in SPEC's gobmk, LT returns 852,368 "no-alias" answers and BA 1,705,559. Yet, these sets are mostly disjoint: the combination of both analyses solves 2,274,936 queries: an increase of 34% over BA. Figure 9 summarizes these results for SPEC 2006.

How do we compare against Andersen's analysis? Andersen's [START_REF] Andersen | Program Analysis and Specialization for the C Programming Language[END_REF] alias analysis is the quintessential pointer disambiguation technique. At the time of this writing, the most upto-date version of LLVM did not contain an implementation of such technique. However, there exist algorithms available for LLVM 4.0, which are not yet part of the official distribution, such as Sui's [START_REF] Sui | SVF: Interprocedural static value-flow analysis in llvm[END_REF] or Chen's [START_REF] Chen | CFL alias analysis[END_REF]. We have experimented with the latter. Henceforth, we shall call it CF, because it uses context free languages (CFL) to model the inclusionbased resolution of constraints, as proposed by Zheng and Rugina [START_REF] Zheng | Demand-driven alias analysis for c[END_REF], and by Zhang et al. [START_REF] Zhang | Fast algorithms for Dyck-CFL-reachability with applications to alias analysis[END_REF]. A detailed description of Chen's implementation is publicly available 1 . Figure 10 compares our analysis and Andersen's. Our numbers have been obtained in LLVM 3.7, whereas CF's has been produced via LLVM 4.0. We emphasize that both versions of this compiler produce exactly the same number of alias queries, and, more importantly, BA outputs exactly the same answers in both cases. This experiment reveals that there is no clear winner in this alias analysis context. BA+LT is more than 20% more precise than BA+CF in three benchmarks: lbm, milc and gobmk. BA+CF, in turn, is three times more precise in omnetpp. The main conclusions that we draw from this comparison are the following: (i) these analysis are complementary; and (ii) mainstream compilers still miss opportunities to disambiguate alias queries.

Scalability

We claim that the less-than analysis that we introduce in this paper presents -in practice -linear complexity on the size In this section we provide evidence that corroborates this claim. Figure 11 relates the number of constraints that we produce for a program, using the rules in Figure 7, with the number of instructions in that program. We show results for our 50 largest benchmarks, in number of instructions, taken from SPEC and the LLVM test suite. The strong linear relation between these two quantities is visually apparent in Figure 11. And, going beyond visual clues, the coefficient of determination (R 2 ) between constraints and instructions is 0.992. The closer to 1.0 is R 2 , the stronger the evidence of a linear behavior. Comparison between the number of instructions and the number of constraints that we produce (using rules in Figure 7) per benchmark. X-axis represents benchmarks, sorted by number of instructions. The coefficient of determination (R 2 ) between these two metrics is 0.992, indicating a strong linear correlation.

As Figure 11 shows, the number of constraints that we produce is linearly proportional to the number of instructions that these constraints represent. But, what about the time to solve such constraints -is it also linear on the number of instructions? To solve constraints, we compute the transitive closure of the "less-than" relation between program variables. We use a cubic algorithm to build the transitive closure [START_REF] Nuutila | Efficient transitive closure computation in large digraphs[END_REF]. When fed with our benchmarks, this algorithm is likely to show linear behavior: the coefficient of determination between the number of constraints for all our benchmarks, and the runtime of our analysis is 0.988. This linearity surfaces in practice because most of the constraints enter the worklist at most twice. For instance, SPEC CPU 2006, plus the 308 programs that are part of the LLVM test suite give us 8,392,822 constraints to solve. For this lot, we pop the worklist 17,800,102 times: a ratio that indicates that each constraint is visited 2.12 times until a fixed point is achieved.

We emphasize that our implementation still bears the status of a research prototype. Its runtime is far from being competitive, because, currently, it relies heavily on C++'s standard data-structures, instead of using data-types more customized to do static analyses. We use std::set to represent LT sets, std::map to bind LT sets to variables, and std::vector to implement the worklist. Therefore, our implementation still has much room to improve in terms of runtime. For instance, we took 340 seconds to solve all the lessthan relations between all the scalar variables found in the 16 programs of SPEC CPU that the LLVM's C frontend compiles on an 2.4GHz Intel Core i7. We have already observed that most of the LT sets end up empty, and that the vast majority of them, over 95%, contain only two or less elements. We intend to use such observations to improve the runtime of our analysis as future work.

Applicability

One way to measure the applicability of an alias analysis is to probe how it improves the quality of some compiler optimization, or the precision of other static analyses. In this work, we have opted to follow the second road, and show how our new alias analysis improves the construction of the Program Dependence Graph (PDG), a classic data structure introduced by Ferrante et al. [START_REF] Ferrante | The program dependence graph and its use in optimization[END_REF]. We use the implementation of PDGs available in the FlowTracker system [START_REF] Rodrigues | Sparse representation of implicit flows with applications to sidechannel detection[END_REF], which has a distribution for LLVM 3.7. The PDG is a graph whose vertices represent program variables and memory locations, and the edges represent dependences between these entities. An instruction such as a[i] = b creates a data dependence edge from b to the memory node a[i]. The more memory nodes the PDG contains, the more precise it is, because if two locations alias, they fall into the same node. In the absence of any alias information, the PDG contains at most one memory node; perfect alias information yields one memory node for each independent location in the program. It is not straightforward to compare LLVM's basic alias analysis against our less-than-based analysis, because the former is intra-procedural, whereas the latter is inter-procedural. Therefore, BA ends up creating at least one memory node per function that contains a load or store operation present in the target program. LT, on the contrary, joins nodes that exist in the scope of different functions if it cannot prove that they do not overlap. In order to circumvent this shortcoming, we decided to use Csmith [START_REF] Yang | Finding and understanding bugs in C compilers[END_REF]. Csmith produces random C programs that conform to the C99 standard, using an assortment of techniques, with the goal to find bugs in compilers. Csmith has one important advantage to us: we can tune it to produce programs with a single function, in addition to the ever present main routine. By varying the seed of its random number generator, we obtain programs of various sizes, and by varying the maximum nesting depth of pointers, we obtain a rich diversity of dependence graphs. Figure 12 shows the results that we got in this experiment.

Our alias analysis improves substantially the precision of LLVM's BA. We have produced 120 random programs, whose size vary from 50 to 4,030 lines. In total, the 120 PDGs produced with BA contain 1,299 memory nodes. When combined, BA and LT yield 8,114 nodes, an increase of 6.23x. We are much more precise than BA because the programs that Csmith produces do not read input values: they use constants instead. Because almost every memory indexing expression is formed by constants known at compilation time, LT can distinguish most of them. Although artificial, this experiment reveals a striking inability of LLVM's current alias analyses to deal with pointer arithmetics. None of the other alias analyses available in LLVM 3.7 are able to increase the precision of BA -not even marginally. Although we have not used CF in this experiment -it is not available for LLVM 3.7 -we speculate, from reading its source code, that it will not be able to change this scenario.

Notice that our results do not depend on the nesting depth of pointers. Our 120 benchmarks contain 6 categories of programs, which we produced by varying the nesting depth of pointers from 2 to 7 levels. Thus, we had 20 programs in each category. A pointer to int of nesting depth 3, for instance, is declared as int***. All these programs, regardless of their category, present an average of six static memory allocation sites. On average, BA produces PDGs with 11 memory nodes, independent on the bucket, and BA+LT produce PDGs with 68. The greater the number of static memory allocation sites, the better the results of both BA and LT. The largest PDG observed with BA only has 52 memory nodes (and 88 nodes if we augment BA with LT). The largest graph produced by the combination of BA and LT has 342 nodes (and only 15 nodes if we use BA without LT).

Related Work

The insight of using a less-than dataflow analysis to disambiguate pointers is an original contribution of this paper. However, such a static analysis is not new, having been used before to eliminate array bound checks. We know of two different approaches to build less-than relations: Logozzo's [START_REF] Logozzo | Pentagons: a weakly relational abstract domain for the efficient validation of array accesses[END_REF][START_REF] Logozzo | Pentagons: A weakly relational abstract domain for the efficient validation of array accesses[END_REF] and Bodik's [START_REF] Bodik | ABCD: eliminating array bounds checks on demand[END_REF]. Additionally, there exist non-relational analyses that produce enough information to solve less-than equations [START_REF] Cousot | Automatic discovery of linear restraints among variables of a program[END_REF][START_REF] Miné | The octagon abstract domain[END_REF]. In the rest of this section we discuss the differences between such work and ours.

The ABCD Algorithm. The work that most closely resembles ours is Bodik et al.'s ABCD (short for Array Bounds Checks on Demand) algorithm [START_REF] Bodik | ABCD: eliminating array bounds checks on demand[END_REF]. Similarities stem from the fact that Bodik et al. also build a new program representation to achieve a sparse less-than analysis. However, there are five key differences between that approach and ours. The first difference is a matter of presentation: Bodik et al. provide a geometric interpretation to the problem of building less-than relations, whereas we adopt an algebraic formalization. Bodik et al. keep track of such relations via a datastructure called the inequality graph. This graph is implicit in our approach: it appears if we create a vertex v i to represent each program variable x i , and add a weighted edge from v 1 to v 2 if, and only if, v 1 ∈ LT(v 2 ). The weight of an edge is the difference v 2 -v 1 , whenever known statically. The other four differences are more fundamental.

Bodik et al. use a different algorithm to prove that a variable is less than another. In the absence of cycles in the inequality graph, their approach works like ours: a positive path between v i to v j indicates that x i < x j . This path is implicit in the transitive closure that we produce after solving constraints. However, they use an extra step to handle cycles, which, in our opinion, makes their algorithm difficult to reason about. Upon finding a cycle in the inequality graph, Bodik et al. try to mark this cycle as increasing or decreasing. Cycles always exist due to φ-functions. Decreasing cycles cause φ-functions to be abstractly evaluated with the minimum operator applied on the weights of incoming edges; increasing cycles invoke maximum instead. Third, Bodik et al. do not use range analysis. This is understandable, because ABCD has been designed for just-in-time compilers, where runtime is an issue. Nevertheless, this limitation prevents ABCD from handling instructions such as x 1 = x 2 + x 3 if neither x 2 nor x 3 are constants. Fourth, Bodik et al.'s program representation does not split the live range of x 3 at an instruction such as x 1 = x 2 -x 3 , x 3 > 0. This implementation detail lets us know that x 2 > x 1 . Finally, we chose to compute a transitive closure of less-than relations, whereas ABCD works on demand.

The Pentagon Lattice. Logozzo and Fähndrich have proposed the Pentagon Lattice to eliminate array bound checks in type safe languages such as C#. This algebraic object is the combination of the lattice of integer intervals and the less-than lattice. Pentagons, like the ABCD algorithm, could be used to disambiguate pointers like we do. Nevertheless, there are differences between our algorithm and Logozzo's. First, the original work on Pentagons describe a dense analysis, whereas we use a different program representation to achieve sparsity. Contrary to ABCD, the Pentagon analysis infers that x 2 > x 1 given x 1 = x 2 -x 3 , x 3 > 0 like we do, albeit on a dense fashion. Second, Logozzo and Fähndrich build less-than and range relations together, whereas our analysis first builds range information, then uses it to compute less-than relations. We have not found thus far examples in which one approach yields better results than the other; however, we believe that, from an engineering point of view, decoupling both analyses leads to simpler implementations.

Fully-Relational Analyses. Our less-than analysis, ABCD and Pentagons are said to be semi-relational, meaning that they associate single program variables with sets of other variables. Fully-relational analysis, such as Octogons [START_REF] Miné | The octagon abstract domain[END_REF] or Polyhedrons [START_REF] Cousot | Automatic discovery of linear restraints among variables of a program[END_REF], associate tuples of variables with abstract information. For instance, Miné's Octogons build relations such as x 1 + x 2 ≤ 1, where x 1 and x 2 are variables in the target program. As an example, Polly-LLVM2 uses fully-relational techniques to analyze loops. Polly's dependence analysis is able to distinguish v[i] and v[j] in Figure 1 (a), given that ji ≥ 1; however, it cannot analyze v[i] and v[j] in Figure 1 (b). These analyses are very powerful; however, they face scalability problems when dealing with large programs. Whereas a semi-relational sparse analysis generates O(|V|) constraints, |V| being the number of program variables, a relational one might produce O(|V| k ), k being the number of variables used in relations.

Range-Based Alias Analyses

There exist several different pointer disambiguation strategies that associate ranges with pointers [START_REF] Alves | Runtime pointer disambiguation[END_REF][START_REF] Balakrishnan | Analyzing memory accesses in x86 executables[END_REF][START_REF] Balatsouras | Structure-sensitive points-to analysis for C and C++[END_REF][START_REF] Nazaré | Validation of memory accesses through symbolic analyses[END_REF][START_REF] Paisante | Symbolic range analysis of pointers[END_REF][START_REF] Rugina | Symbolic bounds analysis of pointers, array indices, and accessed memory regions[END_REF][START_REF] Rus | Hybrid analysis: Static and dynamic memory reference analysis[END_REF][START_REF] Sui | Loop-oriented array-and field-sensitive pointer analysis for automatic SIMD vectorization[END_REF][START_REF] Van Engelen | A unified framework for nonlinear dependence testing and symbolic analysis[END_REF][START_REF] Wilson | Efficient context-sensitive pointer analysis for c programs[END_REF]. They all share a common idea: two memory addresses p 1 + [l 1 , u 1 ] and p 2 + [l 2 , u 2 ] do not alias if the intervals [p 1 + l 1 , p 1 + u 1 ] and [p 2 + l 2 , p 2 + u 2 ] do not overlap. These analyses differ in the way they represent intervals, e.g., with holes [START_REF] Balakrishnan | Analyzing memory accesses in x86 executables[END_REF][START_REF] Sui | Loop-oriented array-and field-sensitive pointer analysis for automatic SIMD vectorization[END_REF] or contiguously [START_REF] Alves | Runtime pointer disambiguation[END_REF][START_REF] Rus | Hybrid analysis: Static and dynamic memory reference analysis[END_REF]; with symbolic bounds [START_REF] Nazaré | Validation of memory accesses through symbolic analyses[END_REF][START_REF] Paisante | Symbolic range analysis of pointers[END_REF][START_REF] Rugina | Symbolic bounds analysis of pointers, array indices, and accessed memory regions[END_REF] or with numeric bounds [START_REF] Balakrishnan | Analyzing memory accesses in x86 executables[END_REF][START_REF] Balatsouras | Structure-sensitive points-to analysis for C and C++[END_REF][START_REF] Sui | Loop-oriented array-and field-sensitive pointer analysis for automatic SIMD vectorization[END_REF], etc. None of these previous work is strictly better than ours. For instance, none of them can disambiguate v[i] and v[j] in Figure 1 (b), because these locations cover regions that overlap, albeit not at the same time. Nevertheless, range based disambiguation methods can solve queries that our less-than approach cannot. As an example, we are unable to disambiguate p 1 and p 2 , given these definitions: p 1 = p + 1 and p 2 = p + 2. We know that p < p 1 and p < p 2 , but we do not relate p 1 and p 2 .

Conclusion

This paper has introduced a new technique to disambiguate pointers, which relies on a less-than analysis. Our new alias analysis uses the observation that if p 1 and p 2 are two pointers, such that p 1 < p 2 , then they cannot alias. Even though this observation is obvious, it has not been used before as the cornerstone of an alias analysis. Testimony of this statement is the fact that our analysis has been able to improve the precision of LLVM's standard suite of pointer disambiguation techniques by a large factor in some benchmarks. There are several ways in which our idea can be further developed. One future avenue that is particularly appealing to us concerns speed. Currently, our research prototype can handle large programs, but its runtime is not practical: it takes several minutes to produce the transitive closure of the less-than relation for our largest benchmarks. We believe that better algorithms can improve this scenario substantially. The design of such algorithms is a problem that we leave open.

the .csv files in the folder. Warning: Bear in mind that the tests may take a while (up to 4 hours), mainly because they are running on a virtual machine.

In the folder memnodes you may find another script called run.sh that executes the third test in our paper, the test of Applicability. The test of Applicability runs a Dependence Graph pass that generates a PDG (Program Dependence Graph) and counts the number of memory nodes in it. Our aim is to show that our new alias analysis yields more memory nodes in these graphs, because it is more precise. We also run this test in the entire test-suite plus SPEC-Cpu2006. In order to do improve our evaluation, we used the tool Csmith to generate 120 random C programs and then we ran the Dependence Graph coupled with our Strict Relations Alias Analysis in all of them. We showed that the PDG generated without our analysis has less memory nodes than the PDG generated with our alias analysis. The random generated C programs are in the folder SingleSource, inside the LLVM's test-suite root, so this test already evaluates the entire test-suite and the random generated programs as well.

To use csmith to generate a random program, use the script random.sh in the folder ExecuteExamples.

A.5 The Output

The output for our analysis is very simple. We use the aa-eval pass to compare, within the same function, all possible pairs of pointers and then we return how many comparisons issued a NoAlias, MayAlias or a MustAlias response. Regarding the Dependence Graph, we basically count the number of Memory Nodes yielded. The output for this analysis is formatted in CSV files. When you run the tests with the script run.sh, the CSV files will be copied to your working directory.

Reviewing Methodology

This artifact has been reviewed according to the guidelines established by the Artifact Evaluation Committee of CGO and PPoPP. The reviewing methodology is described in http://cTuning.org/ae/submission-20161020. html.

Figure 1 .

 1 Figure 1. Two snippets of C code that challenge typical pointer disambiguation approaches.

Figure 3 .

 3 Figure 3. Program written in our core language.

Figure 4 .

 4 Figure 4. The syntax of our intermediate language.

Figure 5 .

 5 Figure 5. Transformation rules used to convert the syntax in Figure 2 into the syntax in Figure 4.

Figure 7 .

 7 Figure 7. Constraint generation rules. Numbers labelling each rule are used in the proofs of Section 3.5. If n is constant, then we assume n > 0. If n is a variable, then R(n) = [l, u], l > 0.

Figure 7

 7 reveals that we have only three kinds of constraints:• LT(x) = ∅: in this case, LT(x) is stationary;• LT(x) = {x } ∪ LT(x ): by induction, LT(x ) is decreasing or stationary, and LT(x) always contains {x }; • LT(x) = LT(x1) ∩ . . . ∩ LT(xn): we apply induction on each LT(xi), 1 ≤ i ≤ n.

  x2); • x ∈ LT(x2): From the hypothesis LT1 |= Σ1, we have that x < x2. We know that x2 < x1; thus, by transitivity, x < x1. Second case: ι is a φ-function. Then, x = φ(x1, . . . , xn) Σ1 → Σ1 \ x → Σ1(xi), for some i, 1 ≤ i ≤ n, depending on the program's dynamic control flow. From Figure 7, we have that LT2 = LT1 \ x → LT1(x1) ∩ . . . ∩ LT1(xn). Thus, any x ∈ LT2(x) is such that x ∈ LT1(xi). By the hypothesis, x < xi. By the semantics of φ-functions, x = xi; hence, x < x.

Figure 9 .

 9 Figure 9. Comparison between three alias analyses in SPEC 2006. "# Queries" is the total number of queries performed when testing a given benchmark. Percentages show the ratio of queries that yield"no-alias", given a certain alias analysis. The higher the percentage, the more precise is the pointer disambiguation method. We have highlighted the cases in which our less-than check has increased by 10% or higher the precision of LLVM's basic alias analysis.

Figure 10 .

 10 Figure 10. How two different alias analysis (LT and CF) increase the capacity of LLVM's basic alias analysis (BA) to disambiguate pointers. The Y-axis shows the percentage of no-alias responses. The higher the bar, the better.

Figure 11 .

 11 Figure 11. Comparison between the number of instructions and the number of constraints that we produce (using rules in Figure7) per benchmark. X-axis represents benchmarks, sorted by number of instructions. The coefficient of determination (R 2 ) between these two metrics is 0.992, indicating a strong linear correlation.

Figure 12 .

 12 Figure 12. Precision of dependence graph. The X-axis shows benchmarks, sorted by number of static memory references in the source code. Y-axis shows number of memory nodes in the Program Dependence Graph. The more memory nodes the PDG contains, the more precise it is.

  , in low-level languages, are used in conjunction with integer offsets to refer to specific memory locations. The combination of a base pointer plus an offset produces what we call a derived pointer. The less-than check that we have discussed in this paper lets us compare pointers directly, if they are bound to a less-than relation, or indirectly, if they are derived from a common base. This observation lets us state the disambiguation criteria below:

DEFINITION 3.11 (Pointer Disambiguation Criteria)

. Let p, p 1 and p 2 be variables of pointer type, and x 1 and x 2 be variables (not constants) of arithmetic type. We consider two disambiguation criteria:

1. Memory locations p 1 and p 2 will not alias if

p 1 ∈ LT(p 2 )

or p 2 ∈ LT(p 1 ). 2. Memory locations p 1 = p + x 1 and p 2 = p + x 2 will not alias if x 1 ∈ LT(x 2 ) or x 2 ∈ LT(x 1 ).

  Figure 8. Effectiveness of our alias analysis (LT), when compared to LLVM's basic alias analysis on the 100 largest benchmarks in the LLVM test suite. Each point in the X-axis represents one benchmark. The Y-axis represents total number of queries (one query per pair of pointers), and number of queries in which each algorithm got a "no-alias" response.

	1.E+09					MiBench's consumer-typeset
	1.E+08	Total	LT	BA	BA+LT	(Total: 295,875,797, LT: 1,708,678, BA: 9,901,270, LT+BA: 10,818,208)
	1.E+07
	1.E+06
		McCat's qbsort (Total: 3,351, LT: 73, BA: 713, LT+BA: 747)
	1.E+05
	1.E+04
	1.E+03
	1.E+02
	1.E+01
	1.E+00
	0	10	20		30	40	50	60	70	80	90	100
	Benchmark # Queries	BA		LT	BA + LT
	lbm	31,944	5.90%	10.15% 15.74%
	mcf	49,133	15.28% 8.95%	16.52%
	astar	95,098	45.54% 16.05% 47.66%
	libq	146,301	51.64% 3.45%	52.67%
	sjeng	428,082	70.64% 2.03%	71.64%
	milc	808,471	31.05% 23.90% 43.88%
	soplex	1,787,190	21.43% 12.48% 23.53%
	bzip2	2,472,234	21.48% 23.09% 26.70%
	hmmer	2,574,217	8.79%	4.48%	9.38%
	gobmk	3,492,577	48.49% 22.91% 63.33%
	namd	3,685,838	22.59% 0.93%	22.76%
	omnetpp	12,943,554	18.71% 0.46%	18.81%
	h264ref	20,068,605	12.86% 1.29%	13.16%
	perl	23,849,576	9.92%	3.87%	10.19%
	dealII	37,779,455	75.05% 20.21% 75.46%
	gcc	186,008,992 4.26%	1.47%	4.65%

Available at https://github.com/grievejia/andersen

Available at http://polly.llvm.org/

Acknowledgment

This project is supported by CNPq, Intel (The eCoSoC grant), FAPEMIG (The Prospiel project), and by the French National Research Agency -ANR (LABEX MILYON of Université de Lyon, within the program "Investissement d'Avenir" (ANR-11-IDEX-0007)). We thank the CGO referees for the very insightful comments and suggestions.

A. Artifact Evaluation

This artifact is in the form of a virtual machine and it is distributed through the link: http://cuda.dcc.ufmg. br/CGO17/strict-inequalities/. This virtual machine contains the code and execution scripts for the work presented in this paper. In the desktop folder, you will find ways to run our analysis on any source code you choose, or on the benchmarks used in this paper's evaluation.

A.1 The Code

The code from this work can be found inside LLVM's build directory inside the virtual machine. The LLVM source and build directory is at /llvm/, and the code for the analyses are in /llvm/lib/Transforms/. In total we have used 4 passes in this paper:

The main pointer alias analysis presented in this paper.

• /llvm/lib/Transforms/vSSA A pass that transforms the program to the e-SSA form, needed in order to use the Strict Relations Alias Analysis.

• /llvm/lib/Transforms/RangeAnalysis A symbolic Range Analysis also used in the Strict Relations Alias Analysis.

• /llvm/lib/Transforms/DepGraph A pass that builds the program dependence graph. This pass is used in one of our tests, to show the effectiveness of our new alias analysis when comparing the number of memory nodes yielded by the DepGraph when running it coupled with the Strict Relations Alias Analysis. We developed our work on LLVM 3.7.

A.2 Getting Started

The artifact is provided as a Virtual Machine image. To use the artifact, you need to download and install the Vir-tualBox VM player at https://www.virtualbox.org/ wiki/Downloads. After downloading and installing Virtu-alBox, to run the VM image, you must perform the following steps:

1. Download and decompress the VM image.

2. OpenVirtualBox.

3. Create a new virtual machine, by clicking in "Machine", "New...".

4. Give a name to the new VM, by filling the "Name" field.

5.

In "Type", select "Linux".

6.

In "Version", select "Ubuntu (64 bit)".

7.

Click "continue", select the desired amount of RAM memory, then click "continue" again.

8. In the hard drive selection screen, select the option "Use an existing virtual hard drive file", then select the .vdi file containing the VM image that you just downloaded.

Your Virtual Machine is ready to use! To start, simply double-click it in the VirtualBox VM list

If the VM prompts for a username and password, you may use the following combination:

• login: cgoartifact You may omit the file extension (.c) when passing the name of the program as a parameter. After the compilation, if you wish to run our Strict Relations Alias Analysis evaluation, you can run the script sraa.sh. The output will be the LLVM's default alias analysis evaluation, with a thorough list of alias information on the program.

$ bash sraa.sh test

If you wish to compare it with the LLVM's basic alias analysis alone, you can also run the script basicaa.sh on any program you wish. You may also use the script random.sh to generate a random C program with the tool Csmith: $ bash random.sh random The clean.sh script will remove all files created by the other scripts.

A.4 Running the Benchmarks

We have executed 3 main evaluation tests in our paper: Precision, Scalability and Applicability. These tests are described in Section 4 of this paper. In the folder Benchmarks you will find the scripts to run the benchmarks used in the paper. You will find two folders: aaeval and memnodes. In the folder aaeval there is a script called run.sh that runs two of the 3 evaluation tests we ran in our paper, the tests of Precision and Scalability. Both tests are executed on the LLVM's test-suite and on the SpecCPU2006. The test of Precision evaluates how better our alias analysis is compared to the Basic Alias Analysis provided by LLVM. So it runs the basicaa, the sraa and both together on the entire test-suite. The test of Scalability evaluates the growth of the number of constraints generated during the Strict Relations Alias Analysis compared to the size of the programs being analyzed. The script run.sh will basically run the tests on the entire test-suite and copy the .csv files containing the statistics to the folder aaeval. At the end of the execution you may find


Financer la recherche--développement des PME en Russie et dans le monde :

un problème, plusieurs solutions Julien Vercueil Maître de conférences habilité à

Le rôle moteur de l'État dans le financement de l'investissement en R&D est accepté de manière générale, y compris au sein d'institutions internationales comme l'OMC qui veillent à éviter que le soutien public ne perturbe de manière excessive la concurrence internationale. Les règles de l'OMC permettent en effet aux États membres d'accorder un montant significatif de ressources publiques aux entreprises privées qui s'engagent dans la R&D. L'objet de cet article est d'analyser les phases de l'activité de R&D pour identifier la nature des problèmes de financement qui y sont associés, tout en comparant plusieurs dispositifs nationaux de soutien aux jeunes entreprises innovantes. Ceci permettra de mettre en perspective, à la fois théoriquement et comparativement, la situation actuelle du financement de la R&D en Russie. La première section de l'article présente les principales ressources du financement de la R&D en Russie et dans une sélection de pays. La deuxième section s'intéresse aux problèmes particuliers rencontrés aux différentes étapes de développement d'une entreprise innovante. La troisième section compare plusieurs solutions de financement de l'investissement en R&D dans le monde. La quatrième section conclut.

1. Ressources et résultats de l'investissement en R&D en Russie Au début des années 2000, l'activité de R&D en Russie était sinistrée. Ses moyens s'étaient effondrés dans la décennie précédente, aussi bien du point de vue des ressources humaines que des investissements en équipement. A partir de l'année 2000 un effort particulier a été fourni dans cette direction par les entreprises et les pouvoirs publics (Graphique 1), effort soutenu par l'expansion économique qui s'est poursuivie durant une dizaine d'années. Source : élaboration de l'auteur à partir de Rosstat (2012) L'augmentation de la dépense intérieure par employé dans la R&D a été encore plus rapide, car dans le même temps, le nombre de salariés a continué de baisser, à un rythme moins rapide cependant que durant la décennie précédente (Graphique 2). (Gao et Liu, 2014, p. 170). Dans le cas russe, elle correspond plutôt à un rééquilibrage entre les ressources humaines et les ressources financières : le sous-équipement chronique des centres de recherche, par rapport au personnel employé, est un héritage de la période soviétique qui n'a commencé à être corrigé que durant la dernière décennie. En comparaisons internationales, la Russie affiche encore une faible intensité des dépenses en R&D relativement au personnel employé dans le secteur. Sur un échantillon de 36 pays pour lesquels les données ont été rassemblées par l'OCDE (la plupart d'entre eux étant membres de cette organisation), la Russie se classe 27 ème par le nombre de chercheurs rapportés à la population active, et 32 ème par l'intensité de la DIRD rapportée au PIB. Les dépenses par chercheur restent inférieures à la moyenne des pays comparés, c'est à dire sous la ligne pointillée du graphique 3. L'organisation des systèmes nationaux d'innovation (Freeman, 1993, Nelson, 1995[START_REF] Lundvall | National Systems of Innovation: Towards a Theory of Innovation and Interactive Learning[END_REF], fait aussi apparaître des différences significatives dans la distribution par destination des dépenses de R&D. Les pays industrialisés comme les États--Unis ou les pays de l'Union Européenne consacrent une part plus importante de leurs dépenses totales à la recherche fondamentale. La Chine et la Corée du Sud se distinguent par la proportion prépondérante des activités de développement, situées en aval du processus. La Russie, tout comme l'Inde, accorde une place importante à la recherche appliquée. Parmi les pays hors OCDE, seule l'Inde réalise une part importante de sa R&D dans le domaine fondamental, mais à des niveaux absolus et relatifs de dépenses globales plus faibles (Graphique 4). Source : OCDE, 2013, Pattelle, 2013, Deloitte, 2011 considérablement augmenté en Russie. Puis la grande dépression des années 1992--1998 a provoqué un ralentissement de l'activité de dépôt de brevets, en partie lié à l'assèchement des financements publics nationaux pour la R&D. Cet assèchement n'a été que partiellement compensé par des financements privés et internationaux [START_REF] Graham | Science in the New Russia. Crisis, Aid, Reform[END_REF]. Durant les années 2000, les financements ont repris et ont permis un rebond du flux de brevets déposés. Aujourd'hui, les entreprises souhaitant être protégées déposent à peu près le même nombre de brevets nationaux par habitant en Russie qu'en France ou en Chine. La dynamique est supérieure à celle des principaux pays industrialisés, mais plus lente qu'en Chine (Graphique 5). La situation est moins favorable à la Russie pour les brevets internationaux. Il s'agit dans ce cas de compter le nombre de brevets déposés par les entreprises établies en Russie et qui entendent protéger leurs innovations à l'international. Alors que le nombre total de brevets (dépôts de brevets comme brevets validés par l'office de protection de la propriété intellectuelle) place la Russie dans les dix premières nations du monde, la part des brevets déposés à l'étranger est inférieure à 10 % du total, contre plus de la moitié pour la France, la Grande--Bretagne, l'Allemagne ou l'Italie, et environ 50 % pour les États--Unis. De ce point de vue, l'activité de dépôt de brevets ressemble en Russie à celle de la Chine ou de la Corée du Sud, où l'essentiel des brevets déposés le sont dans le pays d'origine (WIPO, 2013, p. 59).

Source : World Development Indicators, élaboration de l'auteur.

Le deuxième niveau de mesure des effets des investissements en R&D est l'intensité technologique de la production intérieure. Si l'on mesure cette intensité par la part des exportations civiles de haute technologie (aéronautique et espace, informatique, produits pharmaceutiques, instruments scientifiques, équipements électriques) dans les exportations totales ou dans le PIB, la Russie se place en queue de peloton par rapport aux principales économies du monde (Graphiques 6 et 7). 2. La « vallée de la mort » : où est la sortie ? Les résultats macroéconomiques de la R&D ne se résument pas à ce qui vient d'être présenté. Les raisons qui explique la faible performance de l'économie russe en matière de commercialisation de ses innovations comparativement aux ressources qu'elle y consacre ont des explications multiples. Nous étudions dans le cadre de cet article un maillon de la chaîne de l'innovation : le financement des petites entreprises innovantes. La survie des projets d'innovation est conditionnée en grande partie par leur capacité à collecter des ressources financières suffisantes pour surmonter la période d'incertitude pendant laquelle le produit n'a pas encore trouvé sa demande solvable, alors qu'il faut continuer à investir dans son développement. Ce financement, qui pose déjà problème dans les grandes entreprises qui disposent de ressources financières ou d'un accès privilégié au marché financier et aux financements bancaires, devient critique pour les petites et moyennes entreprises. Dans l'environnement institutionnel et productif de la Russie, où les marchés sont souvent dominés par de grandes firmes, les conditions sont encore moins favorables à leur développement que dans des économies qui se caractérisent par une plus grande fluidité (entrante comme sortante) des jeunes entreprises. En Russie, les PME ne représentent qu'un peu plus de 20 % du PIB national, Les types de recherches conduites durant ces quatre phases sont différents. La recherche fondamentale a lieu en amont du projet, ce sont ses résultats qui sont utilisés par l'innovateur. Toutefois, dans certains cas l'innovateur a conduit lui--même une partie de la recherche fondamentale nécessaire au montage de son projet. Les premières phases du processus d'innovation correspondent largement à la recherche appliquée. Par la suite, à partir du moment où le prototype est transformé en produit, la recherche appliquée cède le pas au développement. Bien sûr, ces trois phases sont en interaction : le passage d'une forme à l'autre de recherche se fait via un développement en spirale, qui implique des retours en arrière pour résoudre des problèmes décelés en aval. Malgré tout, la majeure partie de ces activités de recherche doit être réalisée à un moment où le projet n'a pas encore dégagé de recettes commerciales. La question des conditions de sa viabilité financière se pose donc. Si l'on appelle 3F le montant de capital apporté à l'origine du projet (l'expression 3F, traduisant « family, friends and fools », fait référence au fait qu'au niveau d'incertitude prévalant lors de la conception du projet, la rationalité ne joue qu'un rôle très secondaire dans la décision d'investir : seuls « la famille, les amis et les fous » sont susceptibles d'y croire), ce montant doit être suffisant pour permettre au projet de supporter les pertes cumulées qu'il va encourir durant les trois premières phases du processus (figure 1), avant que la commercialisation ne lui donne les moyens de dégager des bénéfices nets. Si les premiers bénéfices apparaissent au bout de la n ième période, alors une condition du succès de la traversée de la « valée de la mort » (figure 1) s'écrit :

1 : 3𝐹 ≥ 𝑝𝑖 ! !!! où pi désigne la perte nette enregistrée à la i ème période (voir figure 1). Cette contrainte est largement virtuelle puisqu'elle ne peut être constatée qu'a posteriori. Au moment du premier financement, les fondateurs n'ont qu'une idée très vague de la nature de la courbe des flux nets de revenus qui attend leur projet. Ils n'en sont pas encore à réaliser un véritable « plan d'affaires (business plan) » qui doit attendre le stade de la finalisation du prototype pour être crédible. Enfin, l'expérience montre que ce premier financement, lorsque le projet obtient ses premiers succès techniques, s'avère presque toujours insuffisant du fait des ressources financières limitées que l'innovateur a réussi à collecter au tout premier stade. Autrement dit, la contrainte (1) n'est presque jamais respectée. Pour trouver son chemin vers la sortie de la vallée de la mort, l'innovation a besoin d'un apport financier extérieur. Lequel ? En phase de conception, lorsque l'incertitude est à son plus haut, il est rare que l'innovateur ait la possibilité d'obtenir autre chose que des prêts d'honneur (c'est--à--dire sans obligation juridique, mais avec une obligation morale si les conditions le permettent, de remboursement), des bourses ou des subventions. Au fur et à mesure que l'innovation progresse dans son processus de commercialisation, la pertinence de ces fonds s'amoindrit pour financer l'entreprise, à la fois parce que les montants en jeu augmentent -ce qui limite la possibilité de recourir à des dons ou quasi--dons -et parce que d'autres financements deviennent disponibles. A sa place, le financement par le biais du capital--risque augmente à partir de l'étape du lancement. Le capital risque s'avère particulièrement judicieux parce qu'il permet de pallier les limites techniques d'un financement bancaire (très peu de banques acceptent de prêter dans les conditions d'incertitude qui prévalent lors du lancement), tout en maintenant à un niveau raisonnable l'incertitude de l'investisseur puisque devenu actionnaire, il peut prendre connaissance du fonctionnement interne de l'entreprise et conseiller l'équipe de direction dans ses choix. Surtout, le financement par capital--risque est utile parce qu'il procède d'une ambiguïté constructive : en théorie, l'investissement est à horizon infini (puisque contrairement à un prêt il n'y a pas d'échéance de remboursement limitant l'horizon temporel de l'innovateur), ce qui atténue l'incertitude sur le devenir de l'entreprise dans son parcours au sein de la « vallée de la mort » ; mais en même temps, le capital--risqueur souhaite le plus souvent restreindre son engagement financier à un horizon de moyen terme (2--3 à 5 ans généralement), ce qui maintient de fortes incitations pour les dirigeants à faire en sorte de raccourcir le temps d'accès de l'innovation au marché. C'est cette ambivalence qui fait que le capital risque trouve son maximum de pertinence au stade du lancement. Au delà de cette phase, c'est à dire à partir du moment où l'intérêt commercial de l'innovation a été prouvé sur le terrain, l'attractivité du capital--risque décroit et la pertinence du financement bancaire ou par augmentation de capital augmente, tandis que décroît l'incertitude autour de la viabilité du projet.

3. Les formes de soutien à l'innovation dans les PME : une comparaison internationale L'implication des pouvoirs publics dans le soutien à l'innovation intervient à plusieurs niveaux. La comparaison des formes de soutien à l'innovation des jeunes entreprises dans plusieurs pays, dont la Russie, le montre aisément. Au niveau du canevas institutionnel, les lois sur la propriété intellectuelle, les conditions de leur application ont un rôle déterminant dans la propension des entreprises à prendre le risque de l'innovation. Bien sûr, il existe toujours la possibilité de recourir à la stratégie du secret (où l'entreprise devient son propre assureur) mais cette possibilité coûteuse et risquée est moins susceptible d'être retenue si les innovateurs sont plus efficacement protégés par l'environnement légal. De plus, le fait de publier l'innovation permet non seulement de la protéger mais aussi d'engranger les revenus éventuels de son utilisation par d'autres sous formes de droits d'usage. Du point de vue collectif, cette solution est plus bénéfique que le secret puisqu'elle permet de diffuser les connaissances intégrées à l'innovation et lui trouver de nouvelles applications. Au niveau des acteurs de la recherche scientifique, le canevas institutionnel joue aussi son rôle par le biais des incitations à l'essaimage (« spin off ») par les chercheurs de certaines applications de leurs recherches. Ces incitations se résument souvent à la simplification des procédures administratives nécessaires pour créer une entreprise tout en conservant une activité de recherche rémunérée, ou par des incitations fiscales. Le système fiscal joue également un rôle en dehors de l'essaimage. Le législateur introduit souvent la possibilité de défiscaliser les dépenses de R&D dans le but d'encourager ce type d'investissement en diminuant son coût. Au niveau des infrastructures, la création de zones spécialement dédiées à l'innovation (zones économiques spéciales d'innovation, incubateurs, technoparcs,…) est un outil largement répandu dans le monde. Le but de ces zones est d'offrir un environnement matériel plus favorable que sur le reste du territoire national, à la fois pour les services susceptibles d'y être rendus (services administratifs, comptables, de communication, etc.), pour les coûts auxquels ils sont réalisés (prix de la location des bureaux, par exemple), pour les incitations fiscales dont peuvent bénéficier les entreprises qui s'y implantent, et pour la possibilité de mettre en contact des entreprises dont les préoccupations et, parfois, les projets peuvent se compléter. Il s'agit là de provoquer, d'amplifier et surtout d'orienter sur une population particulière d'entreprises susceptibles d'en maximiser les effets, les externalités positives liées à la R&D, dont on a vu l'importance précédemment. Parmi les organisations qui peuvent servir de relai à la politique de soutien à la R&D, les agences de développement, qu'elles soient généralistes ou ciblées par secteur, interviennent plus particulièrement dans la détection, le financement et l'accompagnement des projets prometteurs. Leur soutien financier s'exerce le plus souvent par l'allocation d'un budget préétabli à diverses formes de programmes (prêts à taux bonifiés, à taux zéro, à remboursement différé, subventions et bourses) sur la base de d'appels à candidatures. Dans le secteur privé, ce rôle est joué par des fondations d'entreprises pour le soutien de la recherche et de l'innovation. Aux côtés de ces organismes, on trouve souvent des fonds de capital risque, publics ou privés, qui prennent des participations dans le capital des sociétés sélectionnées et s'en retirent lorsque le marché est devenu suffisamment mûr. La Russie se caractérise par une croissance rapide des financements par capital--risque à partir de la deuxième moitié des années 2000. Des entreprises publiques comme RVK, créée en 2006 pour fonctionner comme un fonds de fonds sectoriels, accompagnée de 19 fonds régionaux, ou Rosnano qui possède un fonds de capital risque, mais aussi des fonds privés sont intervenus de manière croissante et ont indubitablement réveillé cette activité, qui vivotait depuis les années 1990. De 40 millions de dollars en 2010, le montant total des financements par capital--risque est passé à 250 millions en 2012 (RVK, 2013). Pour autant, la décomposition des opérations suivant leur destinationgrande ou petite entreprise, stades initiaux ou stades avancés -n'étant pas disponible à cette échelle, il est difficile de savoir si ces opérations soutiennent réellement l'essor des PME innovantes. Leur répartition par secteur montre en revanche une forte concentration dans le domaine des technologies de l'information, qui s'est développé rapidement depuis le début de la transition et continue de constituer une source active d'innovations au sein l'économie russe. Par ailleurs, en dépit de la création d'un compartiment spécifique du marché financier moscovite, très peu d'opérations d'investissement en capital--risque se sont pour l'instant résolues en Russie par une sortie réussie par revente pour les investisseurs. Les bourses de fondations (les fondations Skolkovo et Bortnik principalement) ont atteint 133 millions de US$ en 2012 et ont financé 655 projets cette année (PricewaterhouseCoopers, 2012).

Source : OECD S&T Database, consultable sur http://stats.oecd.org/Index.aspx?QueryId=350# Dernier accès : janvier 2014. S'il est encore tôt pour porter un jugement sur l'efficacité de ces fonds, on peut mesurer le chemin parcouru en comparant l'activité russe en 2012 à celle des autres acteurs principaux du capital--risque (Graphique 8). Sans surprise, ce sont les fonds anglo--saxons qui montrent la plus grande activité relativement au PIB ainsi que les pays dans lesquels ces fonds sont actifs. L'Allemagne, par exemple, ne montre pas une intensité particulière dans la participation du capital--risque au financement de l'innovation, alors qu'elle se hisse aux premiers rangs de la R&D mondiale. Ceci indique que le capital--risque n'est pas une condition sine qua non pour assurer un financement efficace de la R&D, et que l'autofinancement ou le financement bancaire peuvent, à certaines conditions de taille de l'entreprise et de structure du système financier, prendre efficacement le relai, même aux stades initiaux. Nous avons vu que lors de la conception, le financement de l'innovation dans la jeune entreprise posait des problèmes que ne pouvait systématiquement résoudre le marché des capitaux, fût--il celui du capital--risque. Dans ce cas, c'est un soutien sous forme de bourse, de prêts d'honneur ou de financements analogues par le secteur public qui peut être adapté. Le tableau 1 présente une comparaison internationale des formes que prend en pratique ce soutien dans plusieurs pays, dont la Russie.

  Source : élaboration de l'auteur à partir de Rosstat (2012) Cette évolution qui tend à augmenter l'intensité capitalistique de l'activité de R&D n'est pas isolée. Elle se retrouve par exemple en Chine, où le nombre de chercheurs et d'employés dans les instituts de recherche et les bureaux d'études publics a chuté de plus de 50 % entre 1998 et 2007, alors que les capitaux investis augmentaient rapidement

  de l'auteur à partir de données de l'OCDE(2014)

  Les résultats de l'activité de R&D sont habituellement mesurés par deux types d'indicateurs : les indicateurs mesurant l'incidence directe de la R&D d'une part, comme le nombre de publications scientifiques ou dépôt de brevets et d'autres outils de protection de la propriété intellectuelle ; les indicateurs mesurant les effets indirects, à plus long terme, de cette activité, comme l'intensité de la production et des échanges en produits et services de haute technologie. De ces deux points de vue, l'évolution de la situation de la Russie comparativement à ses principaux partenaires est sensible depuis une dizaine d'année. Immédiatement après les débuts de la libéralisation de 1992, lorsqu'il est devenu possible pour les ingénieurs, scientifiques et les organisations qui les employaient de faire breveter les découvertes technologiques, le nombre de brevets déposés par an a

  contre 50 à 60 % dans les pays industrialisés occidentaux. La croissance des PME de haute technologie doit donc être réalisée dans un milieu concurrentiel particulièrement difficile, ce qui suppose de sécuriser encore davantage les financements pour assurer la solidité du projet. Pour comprendre le problème du financement de la PME innovante, il est utile de décomposer le processus d'innovation en plusieurs phases : la conception (la phase « seed » en anglais), le démarrage (« start--up »), l'accès au marché (« early growth »), l'expansion (« expansion »). Dans la phase de conception, l'innovateur a un concept, il travaille sur un prototype, mais n'a pas encore passé avec succès les étapes de validation technique de celui--ci. Dans la phase de démarrage, le prototype est validé, des améliorations continuent d'être apportées mais elles sont désormais moins critiques. Le travail essentiel porte sur le processus de fabrication et les études de faisabilité financière. Dans la phase d'accès au marché, le prototype a été transformé en produit, la demande est testée pour qualifier les éléments clés de la commercialisation. Les premières recettes commerciales peuvent commencer à affluer à ce stade. La phase d'expansion démarre quand les tests commerciaux ont été concluants. On investit alors dans les opérations commerciales (prospection et marketing) pour développer le courant d'affaires. Les recettes décollent véritablement lors de cette phase. and Myiazaki, 2006, élaboration de l'auteur Flux financiers nets temps 3F : mise de fonds initiale « family, friends & fools » « Vallée de la mort » pi

Dépôts de brevets des résidents et non--résidents pour 1 million d'habitants dans qelques pays, 1991--2011 (échelle logarithmique)

	10000,0	Graphique 5. Korea, Rep.
																							Japan
	1000,0																						United States
																							Germany
	100,0																						Russian
																							Federation
																							China
	10,0
																							France
	1,0	1991	1992	1993	1994	1995	1996	1997	1998	1999	2000	2001	2002	2003	2004	2005	2006	2007	2008	2009	2010	2011	Brazil India
							Graphique 6.
			30,00%
			25,00%
			20,00%
			15,00%
			10,00%
			5,00%
			0,00%
						2005 2006 2007 2008 2009 2010 2011

Part des exportations de haute technologie dans le total des exportations, 2005--2011

	China
	Korea, Rep.
	Japan
	France
	Germany
	United States
	India
	Brazil
	Russian
	Federation

Sources : World Development Indicators, élaboration de l'auteur. Dans le graphique 6, l'effet de distorsion exercé par le haut niveau des prix des hydrocarbures sur la valeur globale des exportations de la Russie pourrait masquer la croissance du volume des exportations de haute technologie. Pour cette raison, nous le complétons par le graphique 7, qui montre que même en proportion du PIB (qui n'est constitué qu'à hauteur de 20 % de la valeur ajoutée issue du secteur extractif), les exportations civiles de haute technologie de la Russie sont faibles en comparaison internationale et en déclin.

  Source : élaboration de l'auteur à partirde OECD, 2013, et des sites des programmes concernés : http://www.fasie.ru/programmy/start, http://www.exist.de/englische_version/, http://www.commercialisationaustralia.gov.au/Pages/Home.aspx, http://www.sbir.gov/. Dernier accès : janvier 2014.Les problèmes de financement rencontrés par les innovateurs sont similaires en Russie et ailleurs. Il est logique qu'une forme de convergence des méthodes de résolution de ces problèmes soit observable de part le monde, ainsi que le montrent les exemples donnés dans le tableau 1. En particulier, un consensus s'est dégagé pour reconaître que les premières étapes du processus d'innovation sont marquées par des défaillances de marché fondamentales, justifiant l'intervention publique pour éviter le sous-investissement dans les activités de R&D qui se traduirait à moyen terme par une perte de bien--être pour l'ensemble des agents économiques et une chute de la compétitivité internationale des entreprises du pays. Cette convergence ne doit pas cependant donner l'impression qu'il existe une « one best way » (une seule voie optimale) pour cofinancer les premières étapes du processus d'innovation dans les PME. Le dosage des dispositifs et leur ampleur doivent surtout

	Programme	Dotation et		Conditionnalité et
	et pays	durée	Étapes	sélectivité
		maximale
				Compétition ouverte.
	SBIR	2,5 années	Phase 1 : études de faisabilité	14 % des candidats sont
	(États--Unis)	> 1 milliard	Phase 2 : processus de	retenus pour la phase 1
		de US$	commercialisation	60 % des candidats de la
				phase 1 sont retenus pour
				la phase 2
			Phase 1. « Savoirs et Compétences » :
		2 à 3 ans	jusqu'à 450000 US$	Compétition ouverte.
		245 millions	Phase 2. « Cadres expérimentés » :	Phase 1 : Financement
	Commercia--	de US$ sur 5	jusqu'à 300000 US $.	80%/20%
	lisation	ans (2010--	Phase 3. « Test du concept » : 45 à	Phase 2 : 50/50
	Australia	2014) puis	220000 US $	Phase 3 : 50/50
	(Australie)	70 millions	Phase 4. « Premières phases de	Phase 4 : 50/50
		de US$ par	commercialisation » : 50000 à 1,7
		an	Millions d'US $
			Phase 1. Test de la faisabilité	Compétition ouverte.
	Exist	3 ans	technique : jusqu'à 60000 €	Phase 2 : couverture à
	(Allemagne)	32 millions	Phase 2. Réalisation du prototype :	hauteur de 75 % des coûts
		d'€ par an	jusqu'à 1,5 Millions d'€
				Compétition ouverte.
		3 ans	Année 1. Convaincre les	Année 1 : 26 % des
	Start	4 milliards	investisseurs : jusqu'à 40000 US$	candidats éligibles
	(Russie)	de RUR en	Année 2. Développement	Année 2 : 25 à 30 %
		2013,	technologique et industriel	éligibles (si financement
		objectif 20	Année 3. Développement commercial	privés >50 %)
		milliards en		Année 3 : 70 % éligibles (si
		2020		premières ventes)

être cohérents avec les spécificités nationales qui renvoient souvent au canevas institutionnel issu de l'histoire du pays. De manière générale, l'efficacité des programmes dépend tout de même d'un certain nombre de facteurs, dont les politiques d'innovation doivent tenir compte :

--Le montant des fonds alloués, car une masse critique de fonds est nécessaire pour que le processus ait un effet d'entraînement macroéconomique. --La qualité de la gouvernance des dispositifs, qui suppose l'intégrité déontologique des responsables des programmes, la mise en place de modes de sélection en « double aveugle » et la signature par les évaluateurs d'un engagement à signaler tout conflit d'intérêt pouvant fausser leur évaluation des projets. --La cohérence entre les dispositifs, notamment entre l'échelle nationale et l'échelle régionale, entre les aides génériques et les aides ciblées, entre les dispositifs d'aides par catégories et par tailles d'entreprises. --La faculté des financements publics à exercer un effet de levier sur les cofinancements, non seulement par l'augmentation de la notoriété de l'entreprise lauréate, mais également via le signal de qualité envoyé par la procédure de sélection aux financeurs privés, ainsi que grâce la garantie qui peut être donnée aux emprunts contractés par l'innovateur, qui permet de réduire considérablement l'incertitude associée au financement du projet. --Les services publics complémentaires associés aux financements, en premier lieu l'insertion dans un réseau d'entreprises innovantes et d'investisseurs qui décuple les opportunités pour la jeune entreprise. --La limitation autant que faire se peut, des effets indésirables que ces programmes peuvent provoquer. Par exemple, le risque existe que la procédure de sélection, en retenant les meilleurs projets, cible des entreprises qui auraient pu se développer sans aide, et manque, faute de financements supplémentaires, les entreprises qui ne pourraient trouver la sortie de la « vallée de la mort » sans soutien extérieur. Une étude de l'agence française pour le financement de l'innovation (OSEO, organisme public) a montré que les financements accordés permettaient de multiplier par trois le nombre de brevets déposés par les entreprises soutenues. Le coefficient multiplicateur est de deux pour les grandes entreprises contre 4 pour les PME, ce qui suggère qu'en France, la probabilité de provoquer un « effet d'aubaine » par le financement est supérieure lorsqu'il est dirigé vers les grandes entreprises que lorsqu'il cible les PME. --Les modes d'évaluation des dispositifs de soutien. Des études régulières sur l'efficacité des dépenses engagées doivent permettre de faire évoluer les programmes, tout en renouvelant leur crédibilité auprès des innovateurs et des autres partenaires.