Charles Guyon

Thierry Bouwmans

El-Hadi Zahzah
email: ezahzah@univ-lr.fr

Foreground Detection via Robust Low Rank Matrix Factorization including Spatial Constraint with Iterative Reweighted Regression

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

The detection of moving objects is the basic lowlevel operations in video analysis. This detection is usually done using foreground detection. This basic operation consists of separating the moving objects called "foreground" from the static information called "background". Recent reseach on robust PCA shows qualitative visual results with the background variations appromatively lying in a low dimension subspace, and the sparse part being the moving objects. First, Candes et al. [START_REF] Candes | Robust principal component analysis[END_REF] proposed a convex optimization problem to address the robust PCA problem. The observation matrix is assumed represented as:

A = L + S ( 1
)
where L is a low-rank matrix and S must be sparse matrix with a small fraction of nonzero entries. This research seeks to solve for L with the following optimization problem: min

L,S ||L|| * + λ||S|| 1 subj A = L + S (2)
where ||.|| * and ||.|| 1 are the nuclear norm (which is the L 1 norm of singular values) and l 1 norm, respectively, and λ > 0 is an arbitrary balanced parameter. Under these minimal assumptions, this approach called Principal Component Pursuit (PCP) solution perfectly recovers the low-rank and the sparse matrices. Candes et al. [START_REF] Candes | Robust principal component analysis[END_REF] showed results on face images and background modeling that demonstrated encouraging performance. Several algorithms have been proposed for solving PCP such as Augmented Lagrangian Method [START_REF] Candes | Robust principal component analysis[END_REF], Low-Rank Representation [START_REF] Lin | Linearized alternating direction method with adaptive penalty for low-rank representation[END_REF] and SADAL [START_REF] Ma | Algorithms for sparse and low-rank optimization: Convergence, complexity and applications[END_REF]. However, PCP presents the following limitations: 1) The low-rank component are assumed to be exactly low-rank and the sparse component to be exactly sparse but the observations in real applications are often corrupted by noise affecting every entry of the data matrix; 2) The spatial connexity of the pixels are not addressed as the images are stacked in columns; 3) PCP is a batch algorithm.

For the first limitation, Zhou et al. [START_REF] Wright | Robust principal component analysis: Exact recovery of corrupted low-rank matrices by convex optimization[END_REF] proposed a stable PCP that guarantee stable and accurate recovery in the presence of entry-wise noise. Recently, Tang and Nehorai [START_REF] Tang | Robust principal component analysis based on low-rank and block-sparse matrix decomposition[END_REF] proposed a PCP method via a decomposition that enforces the block sparsity of S and then address the second limitation. For the third limitation, He et al. [START_REF] He | Incremental gradient on the grassmannian for online foreground and background separation in subsampled video[END_REF] proposed an incremental Grasmannian RPCA method to update L and S when a new frame arrives.

In this paper, we propose a robust low-matrix factorization with IRLS scheme to adress the second limitation. For a data matrix A containing the sequence, we assume that a part is approximatively low-rank and product of two matrices, and a small part of this matrix is corrupted by the outliers. Furthermore, we directly introduced a spatial term in the l 1 minimization to address the spatial connexity of the pixels. So, our contributions can be summarized as follows: 1) Addition of spatial constraint to minimization process, 2) IRLS alternating scheme for weighted the 2-parameters ||.|| α,β for matrix low-rank decomposition. The rest of this paper is organized as follows. The Section 2 focus on IRLS method apply on vector regression problems. In Section 3, we present a robust low-rank matrix factorization which allows us to detect foreground objects in dynamic backgrounds. In Section 4, we present comparison and evaluation versus the state-of-the-art methods and the Section 5 provides the conclusion.

L p Minimization with spatial constraint

In most applications, video surveillance data is assumed to be compose of background, foreground and noise. Regression task is a crucial part of the proposed decomposition algorithm and illustrate the main keys through a simple 1-D example shown in Fig. 1. We consider the following minimization problem (3), where A is a dictionary matrix (row order) and b is a row vector, the second term forces the error E to be a connexe shape, through the TV (Total Variation) of the error must be small, where the matrix ∇ s is a spatial gradient. The left part of the problem (3) is convexe for α > 1 and the usual IRLS (Iteratively reweighted least squares) scheme for solve argmin x ||Ax -b|| α is given by

argmin x ||Ax -b|| α + λ||∇ s E|| 1 , E = |b -Ax| (3)
D (i) = diag((ε + |b -Ax (i) |) α-2 ) x (i+1) = (A t D (i) A) -1 A t D (i) b (4)
It was proven that a suitable IRLS method is convergent for 1 ≤ α < 3 (cf. [START_REF] Daubechies | Iteratively reweighted least squares minimization for sparse recovery[END_REF] and [START_REF] Osborne | Finite algorithms in optimization and data analysis[END_REF]). Since if the process is express with a residual formulation, we gain more numericaly stability and let us to choose freely α ∈ [1, ∞[ with an adapted step size λ opt on every iteration.

r (i) = b -Ax (i) D = diag((ε + |r (i) |) α-2 ) y (i) = (A DA) -1 A Dr (i) x (i+1) = x (i) + (1 + λ opt )y (i) (5)
With a fixed λ opt , we should choose λ opt = Λ(α).

Λ(α) =      5/6 if α ≤ 1 -2 3 α + 3 2 if 1 < α < 1 + 3 4 1 α-1 -1 if α ≥ 1 + 3 4 (6)
Otherwise, the algorithm is twice iterative, where we try to get an optimal x and an optimal λ at each step.

c (i) = Ay (i) d (i) = b -A(x (i) + y (i) ) argmin λ opt ||c (i) λ -d (i) ||α λ (0) = Λ(α) s (k) = d -λ (k) c E = diag((ε + |s (k) |) α-2 ) z (k) = c t Es (k) c t Ec λ (k+1) = λ (k) + (1 + Λ(α))z (k) (7)
Only few iterations (≈ 10) is enough for acceptable approximation of λ opt of the λ (k) sequence. Moreover, the convergence is usually improved by a Aitken process or an other acceleration technique. Note for case α > 2, convergence is achieved when 0 < 1 + λ < 2 α-1 . Additionally, TV is particular case of the following problem:

argmin x ||Ax -b|| α + λ||Cx -d|| β (8)
By derivation, the associated IRLS scheme is,

r 1 = b -Ax (i) , r 2 = d -Cx (i) , e 1 = ε + |r 1 |, e 2 = ε + |r 2 | D 1 = ( e α 1 ) 1 α -1 diag(e α-2 1
), D 2 = λ( e β 2 )

1 β -1 diag(e β-2 2 ) y (i) = (A D 1 A + C D 2 C) -1 (A D 1 r 1 + A D 2 r 2 ) x (i+1) = x (i) + (1 + λopt)y (i) (9)
The penalty term of (3) used for to increase connexity of the error requires to solve this minimization problem,

argmin x ||C|Ax -b| α -d|| β (10)
With • denotes the Hadamard product, the IRLS follow:

r 1 = b -Ax (i) , r 2 = d -C|Ax (i) -b| D = diag((C (|r 2 | β-2 • r 2 )) • |r 1 | α-2 ) y (i) = (A DA) -1 (A Dr 1 ) , x (i+1) = x (i) + (1 + λopt)y (i) (11)
More generally, we consider the following matrix regression problem min

With ||M ij || α,β W = ( n i=1 ( m j=1 W ij |M ij | β ) α β ) 1 α ( 12
)
The problem is solved in the same manner on matrices with a reweighted regression strategy,

Until X is stable, repeat on each k-columns R ← B -AX S ← ε + |R| D k ← diag(S β-2 ik • ( j (S β ij • W ij )) α β -1 • W ik ) k X ik ← X ik +(1+Λ(max(α, β)))(A t D k A) -1 A t D k R ik (13)

Foreground Detection via Robust Low-Rank Matrix Factorization

The training video sequence A ∈ R n×m is store as a matrix with a particular structure. Columns are spatial frames and rows are values of a fixed pixel over time.

For A = I 1 , . . . , I m , I j denotes a vectorized frame of n pixels at j-time with m is the number of frames.

A y+hx,t implies the pixel intensity at coordinate x, y, t.

Then, the decomposition involves the following model:

A = L + S = BC + S ( 14
)
where B is a low-rank matrix corresponding to the background model plus noise and C allows to approximate L by linear combination. S is a sparse matrix which corresponds to the foreground component obtained by subtraction. The model involves the error reconstruction determined by the following constraints:

min B∈R n×p ,C∈R p×m ||(A-BC)•W || α,β +µ||BC|| * (15)
where ||.|| * denote the nuclear norm. The decomposition is fragmented into two parts. Firstly, we track 1-Rank decomposition since the first eigen-vector is strongly dominant in video surveillance. . Finally, we find a local minimum of ||.|| 2,0 and hope that is near of the global minimum of this problem. In the case where α = β = 2, the decomposition is usually solved by a SVD (Singular Value Decomposition). Thus, our SVD algorithm can be seen as an iterative regression. The proposed scheme determines alternatively the optimal coefficients, it means searching C for B fixed and searching B for C fixed.

R 1 = A -B 1 C 1 min B1,C1 ||R 1 || 1,1 R = A -B 1 C 1 -B r C r min Br,Cr ||R • φ(R 1 )|| 2,1→0 (16)
C (k+1) = (A t A) -1 A t B (k) C(k+1) = C (k+1) √ C t(k+1) C (k+1) -1 B (k+1) = (A t A) -1 A t C(k+1) (17)
Additionnaly, this alternating regression framework allows to associate a weigthed matrix W which is entrywise multiplied to the error. min

B,C ||(A -BC) • W || α,β
The W mask is iteratively computed and aims to enforce the fit exclusively on guessed background region.

We define a function φ that have two goals, smooth the error (like spatial median filtering) and transform the error for obtain a suitable weighted mask for regression.

W = φ(|A -BC|) , φ(E) = e -γT V (E)
(18) By including local penalty as a constraint in RPCA, this explicitly increases local coherence of the sparse component as filled/plain shapes (therefore moving object).

Experimental Results

We have compared the proposed approach with recent RPCA approaches: LBD [START_REF] Tang | Robust principal component analysis based on low-rank and block-sparse matrix decomposition[END_REF], LRR [START_REF] Lin | Linearized alternating direction method with adaptive penalty for low-rank representation[END_REF], SADAL [START_REF] Ma | Algorithms for sparse and low-rank optimization: Convergence, complexity and applications[END_REF] and GRASTA [START_REF] He | Incremental gradient on the grassmannian for online foreground and background separation in subsampled video[END_REF] algorithms. The experiments were conducted qualitatively and quantitatively on the Wallflower dataset [START_REF] Toyama | Wallflower: Principles and practice of background maintenance[END_REF] I2R dataset [START_REF] Li | Statistical modeling of complex backgrounds for foreground object detection[END_REF]. The algorithms are implemented with Matlab.

Wallflower and I2R dataset

The Wallflower dataset provided by Toyama et al. [START_REF] Toyama | Wallflower: Principles and practice of background maintenance[END_REF] consists of seven video sequences, with each sequence presenting one of the difficulties a practical task is likely to encounter. The images are 160 × 120 pixels. The Fig. 3 and Fig. 4 show the qualitative results. For the quantitative evaluation, we used metrics based on the detection rate, the precision and the F-measure [START_REF] Maddalena | A fuzzy spatial coherence-based approach to background foreground separation for moving object detection[END_REF] computed between algorithm result and hand-segmented ground truth. our method (direct one-to-one correspondence with Fig. 4).

The I2R dataset provided by [START_REF] Li | Statistical modeling of complex backgrounds for foreground object detection[END_REF] consists of nine video sequences, which each sequence presenting dynamic backgrounds or illumination changes. The size of the images is 176 × 144 pixels. For each sequence, the ground truth is provided for 20 images. Among this dataset, we have chosen to show results on seven sequences (see Fig. 3 and Fig. 4).

Discussion

The proposed approach outperforms the other algorithms on five sequences over the Wallflower and I2R datasets and it is followed by SADAL. For the other sequences, the algorithm is in the second place or the results are still acceptable.

Conclusion

In this paper, we have presented a robust matrix factorization for foreground detection. This method is conceptually simple, easy to implement and efficient. Furthermore, experiments on video surveillance datasets show that this approach is more robust than recent RPCA approaches in the presence of dynamic backgrounds and illumination changes. Further research consists in developping an incremental version to update the model at every frame and to achieve real-time requirements.

Figure 1 .

 1 Figure 1. Schematic example for the 1-D case: We illustrate different fitting strategies of random dictionary basis (cosine function, wavelets, ...) on a composite signal S = S1 + S2 + S3.

Figure 2 .

 2 Figure 2. Overview of our background modeling strategy for the 1-D case with L1 minimization and spatial constrain in order to split Foreground and Background+Noises components.

X||AX-

  B|| α,β W with two parameters norm (α, β) and a weighted matrix (W ),

  We use ||.|| 2,1→0 instead of usual ||.|| 1,1 because it forces spatial homogeneous fitting. Besides β = (1 → 0) means the β parameter decreases during iteration. First, we search a solution of the convex problem ||.|| 2,1 , then use the solution as an initial guess for non-convex problem ||.|| 2,(1-ε)

Figure 3 .

 3 Figure 3. From top to bottom: Wallflower and I2R datasets. From left to right (split in two columns): The original image, the background model and their difference.

Figure 4 .

 4 Figure 4. Foreground detection masks on the Wallflower and I2R datasets. From left to right: Ground Truth, LBD, LRR, SADAL, GRASTA, our method.

Table 1

 1 shows the results obtained for each algorithms.

	Sequence	Frame	LBD LRR SADAL GRASTA Our method
	bootstrap	00299 70.18 69.40	67.02	55.37	58.78
	campus	01650 59.93 59.99	68.14	61.84	75.07
	curtain	22772 91.08 88.34	91.01	89.88	90.73
	escalator	02424 65.28 63.41	59.81	68.31	63.68
	hall	02926 73.58 69.75	77.57	78.25	79.26
	shoppingmall	01862 80.15 77.88	82.80	79.54	81.94
	watersurface	01499 90.37 83.57	92.01	90.97	91.02
	camouflage	00251 70.58 70.49	76.00	70.34	82.27
	fore. aperture	00489 60.69 50.10	71.55	75.14	75.19
	light switch	01865 57.74 36.76	69.33	28.35	58.49
	moved objects 00985	0	0	0	0	0
	time of day	01850 71.43 54.41	80.84	79.80	80.43
	waving trees	00247 62.65 50.74	81.67	84.16	84.70

Table . 1 F-measure for LBD [9], LRR[5], SADAL[6], GRASTA[3],

 .


Maroua Maalej

Laure Gonnord

Do we still need new Alias Analyses?

Keywords: Static Analysis, Alias Analysis, Optimization, Compilers Analyses statiques, Analyses d'alias, Optimisation, Compilateurs

Alias analysis is one of the most used techniques that aim to optimize languages with pointers. It is no surprise that this topic has received much attention in many fields including compilation and program verification. However, despite all this attention, a deep study of its state-of-the art shows that it is not handled satisfactorily, by far. In this paper we demonstrate that, although many approaches have been proposed, we still cannot rely on alias analysis inside compilers. We illustrate our statement with an overview of the capabilities of state-of-the-art compilers.

Introduction

Low-level languages like C are widely used to write embedded software and manage hardware in order to make smaller or more efficient programs. They enable the programmer to finely adapt their code to their hardware, so that it runs faster with minimum memory usage. Today variants of the C language are still used to program on multicore or GPU machines. However, since these languages lack abstractions and give the programmer ability to manipulate memory, they are hard to program and are vulnerable to errors. To overcome this problem and to help the user produce correct and optimized code, analysis techniques have been widely investigated in both verification [START_REF] Martena | Alias analysis by means of a model checker[END_REF] and compilation fields [START_REF] Ghiya | On the importance of points-to analysis and other memory disambiguation methods for C programs[END_REF].

In this paper we will mainly discuss the field of static alias analyses also known as pointer analyses or points-to analyses that have been shown to be undecidable [START_REF] Ramalingam | The undecidability of aliasing[END_REF]. This kind of analysis attempts to discover, statically (at compile-time), the possible values of a pointer at runtime. Typically, this information is used to optimize programs or prove their correctness, which can be done by eliminating dead code and null pointers, parallelizing, rescheduling, etc.

Many approaches that trade precision for speed, speed for precision, or even attempt to balance between both, have been proposed and improved in time and space. However, we shall demonstrate that despite all the attention this topic has received, today's compilers still rely on rudimentary and imprecise alias analyses, which provide conservative information insufficient to generate efficient code.

The contributions of this paper are the following:

• an extensive study of the state-of-the-art approaches for alias analyses (Section 2) and their use for compiler optimizations (Section 3); • an experimental evaluation of strengths and weaknesses of current production C compilers (Section 4); • a discussion of the kind of information that would be useful for designing new pointer analyses for compilers (Section 5).

Alias analysis: context and related work

In this section, we introduce the problem of alias analyses and make an overview of existing approaches. We show that the trade-off between precision and scalability is difficult to find, especially when it comes to compiler optimization.

Problem statement

Alias analysis (or "pointer analysis") is a technique widely used to perform, on languages with pointers, transformations and optimizations such as parallelization [START_REF] Larsen | Parallelizing more loops with compiler guided refactoring[END_REF] and code motion. It is also useful for program verification such as detecting bugs due to array out of bounds accesses [START_REF] Nazaré | Validation of memory accesses through symbolic analyses[END_REF][START_REF] Ströder | Proving termination and memory safety for programs with pointer arithmetic[END_REF] and integer overflow [START_REF] Kuznetsov | Code-pointer integrity[END_REF][START_REF] Wagner | Intrusion detection via static analysis[END_REF]. Some of alias analyses are performed for security and performance enforcement [START_REF] Chang | Efficient and extensible security enforcement using dynamic data flow analysis[END_REF][START_REF] Olivo | Static detection of asymptotic performance bugs in collection traversals[END_REF], deadlock or race detection [START_REF] Rugina | Symbolic bounds analysis of pointers, array indices, and accessed memory regions[END_REF][START_REF] Vineet Kahlon | Fast and accurate static data-race detection for concurrent programs[END_REF], memory errors detection [START_REF] Dor | Checking cleanness in linked lists[END_REF], etc. Such an analysis aims to disambiguate memory locations pointed by pointer variables to find out whether they dereference overlapping regions or not.

At runtime, a pair of pointers may have the following behaviors, depicted in Figure 1: • No Alias: p 1 and p 2 are disjoint. They do not reference overlapping memory regions. This is the favorable case toward optimizations such as rescheduling and code motion, as we will see in Section 3. • Alias : p 1 and p 2 reference regions that overlap. In this case, we can distinguish between partial alias where p 1 and p 2 overlap in some way but do not start at the same address and must alias where p 1 and p 2 alias and start at the same address. The literature of alias analysis is abundant and much work have been done in the last few decades. For a quite exhaustive bibliography, see for instance [START_REF] Hind | Pointer analysis: haven't we solved this problem yet[END_REF] and [START_REF] Mensi | Analyse des pointeurs pour le langage C[END_REF]. In this paper, we shall be limited to related work that are the most relevant for our study of interest.

Static analyses of pointers

Historically, starting from Andersen's work [START_REF] Ole | Program Analysis and Specialization for the C Programming Language[END_REF], static analysis for pointers has received much attention [START_REF] Hind | Pointer analysis: haven't we solved this problem yet[END_REF][START_REF] Ghiya | On the importance of points-to analysis and other memory disambiguation methods for C programs[END_REF][START_REF] Magno | Wave propagation and deep propagation for pointer analysis[END_REF][START_REF] Ströder | Proving termination and memory safety for programs with pointer arithmetic[END_REF]. The current state-of-the-art shows numerous analysis approaches.

Constraint-based pointer analyses. Andersen [START_REF] Ole | Program Analysis and Specialization for the C Programming Language[END_REF] and Steensgaard [START_REF] Steensgaard | Points-to analysis in almost linear time[END_REF] propose to compute points-to sets (the set of variables that a given pointer can reference) by means of solving constraint systems. In these two algorithms, a set of constraints is derived from program statements involving assignments, loads and stores. For instance, for any assignment a=b, the points-to set of b is included in the points-to set of a (for Andersen), or the two points-to sets are equal (for Steensgaard). Solving this set of constraints is done with efficient graph algorithms. The output of these algorithms is not a comparison between pointers but a points-to set for each pointer which would enable further use by means of alias queries. The main drawback of these Inria algorithms is that they are not precise enough to properly handle pointer arithmetic: after the assignment py=px+4, px and py are inside the same points-to set.

Pointer analyses by Model Checking. In [START_REF] Martena | Alias analysis by means of a model checker[END_REF], alias analysis information is collected by means of model checking techniques. To do so, the relevant features of the C code is represented as a finite state automaton and the alias query is translated into a property verified as a reachability problem. Although the performance in terms of verification time and in scalability seems promising, we believe that such kinds of program transformation cannot be embedded in compilers, in particular because tracking back information from results obtained after transformation is tedious and error prone.

Shape Analyses. Shape analysis [START_REF] Sagiv | Solving shape-analysis problems in languages with destructive updating[END_REF][START_REF] Calcagno | Beyond reachability: Shape abstraction in the presence of pointer arithmetic[END_REF], also known as storage analysis, is a kind of static alias analysis mostly used to verify programs that perform destructive updating on dynamically allocated storage. Its goal is to give, for each program point, a finite and conservative characterization of the possible shapes of program data structures allocated in the heap. A Static Shape Graph (SSG), which is a finite, directed and labeled graph, is computed at each program point to approximate stores done during execution until this point. The SSG, where nodes are structures and edges are pointers, is used to check memory safety (looks for memory leaks), and to find out of bounds accesses and discover properties of linked data structures dynamically allocated. Graphs are used to model program stores. Much attention has been paid to this technique in the last decade. However, the effort has mainly been done on precision issues. The state-of-the-art [START_REF] Li | Shape analysis for unstructured sharing[END_REF] is able to express complex properties about graph structures, but the current version of the analyzer only deals with tiny programs (20 to 30 lines of code). However, this kind of analyses are too greedy in terms of memory resources to be embedded in state-of-the-art compilers.

An example of application to verification: array out-of-bounds check. A violation of memory safety in C leads to undefined behavior that may lead to incorrect program or even a non-termination. One form of memory violation is array out of bounds access. To avoid this bug, many alias analyses [START_REF] Nazaré | Validation of memory accesses through symbolic analyses[END_REF][START_REF] Ströder | Proving termination and memory safety for programs with pointer arithmetic[END_REF] have been proposed. In [START_REF] Nazaré | Validation of memory accesses through symbolic analyses[END_REF] the analysis tracks valid references from array base pointers to avoid out-of-bounds accesses. Example 1 illustrates this approach.

Example 1 Consider the program shown in Figure 2. After renaming variables, we let p i = p + i at line 5 and p j = p + j at line 6. W designs the function that maps a pointer to its addressable offsets. The static analysis detailed in [START_REF] Nazaré | Validation of memory accesses through symbolic analyses[END_REF], proves that

W (p) = [0, N -1], W (p i ) = [0, 1] and W (p j ) = [-1, 0].
In other words, this analysis tells us that p i for instance can safely dereference addresses from 0 to 1 and that the largest addressable offset from p is N-1. Therefore, we no more need to add runtime checks [START_REF] Milewicz | Runtime checking C programs[END_REF] to guarantee the safety of memory accesses.

Complexity and scalability of pointer analyses

As in other fields of static analyses, the different pointer analyses that have been proposed can be classified depending on the kind of information they track and the type of abstraction they do.

Historically, the two success stories of pointer analyses, namely Andersen's and Steensgaard's algorithms [START_REF] Ole | Program Analysis and Specialization for the C Programming Language[END_REF][START_REF] Steensgaard | Points-to analysis in almost linear time[END_REF], are flow-insensitive. Information concerning pointer aliases are gathered and merged at join nodes. Clearly, these kinds of analyses are cheaper than analyses that take the control flow into account, such as [START_REF] Ye | Region-based selective flow-sensitive pointer analysis[END_REF][START_REF] Nagaraj | Approximating flow-sensitive pointer analysis using frequent itemset mining[END_REF][START_REF] Hardekopf | Flow-sensitive pointer analysis for millions of lines of code[END_REF]. However, in programs with arbitrary pointer dereferencing, precise flow-sensitive as well as flow-insensitive analyses algorithms have been shown to be NP-hard [START_REF] Landi | Pointer-induced aliasing: A problem classification[END_REF][START_REF] Horwitz | Precise flow-insensitive may-alias analysis is np-hard[END_REF].

1: unsigned N = read() 2: int * p = malloc(N) 3: int i = 0 ; int m = 0 ; int j = N-1 4: while i < j do As far as precision is concerned, the analyses may also consider the different calling contexts of a given procedure. This again has a cost [START_REF] Oh | Selective context-sensitivity guided by impact pre-analysis[END_REF], depending on the length of the calling chain taken into account.

When a pair of pointers is within an alias set but pointers are disjoint and don't dereference overlapping memory regions, the algorithm is said to be imprecise. Therefore, many optimizations might be disabled while they are possible and beneficial. However, the cost of a given analysis is growing with its precision.

The efficiency of alias approaches do not generally refer to the quality of their output but with to speed and to the number of instructions and lines of code that they can handle. Depending on which criterion is privileged, different algorithms have been proposed to be precise or scalable, or claim to handle this trade-off [START_REF] Hardekopf | Flow-sensitive pointer analysis for millions of lines of code[END_REF].

As far as we know, apart from the classic Andersen and Steensgaard Algorithms for points-to sets, none of the algorithms we cited before has been implemented in production compilers. The recent advances in static analyses for compilation [START_REF] Nazaré | Validation of memory accesses through symbolic analyses[END_REF][START_REF] Boissinot | SSI Properties Revisited[END_REF] have shown that sparse analyses, which assign information only on variables, scale better [START_REF] Choi | Automatic construction of sparse data flow evaluation graphs[END_REF] than dense analyses. These later also assign information on variables in addition to program points, hence the complexity is higher.

Static analyses with runtime checks

Hybrid analysis [START_REF] Rus | Hybrid analysis: static & dynamic memory reference analysis[END_REF] gathers information during compile time and use them at runtime to decide whether an optimized version can be used. The goal is to reduce time and memory overheads. An example of a hybrid analysis is given by Example 2.

Example 2 Recall that the information needed to optimize the program in Figure 3a is that there is no aliasing between pointers at lines 5 and 6. Given this information, we can parallelize the code, which gives the program in Figure 3b. Since in this case, the value of N cannot be known at compile time, a decision could not be made based on only static analysis which would conservatively answer "may alias". The hybrid analysis technique given by [START_REF] Rus | Hybrid analysis: static & dynamic memory reference analysis[END_REF] applied to the original program generates the test N < 84 at compile time and asserts it at runtime.

Dynamic analyses

Incomplete control-flow and input information or high complexity of the analysis decreases the efficiency and accuracy of static analyses. Consequently, compilers are less able to perform optimizations. To improve the quality of the results of alias analysis and to increase its efficiency while avoiding memory overheads, dynamic analysis [START_REF] Mock | Dynamic analysis from the bottom up[END_REF][START_REF] Guo | Selective runtime memory disambiguation in a dynamic binary translator[END_REF] techniques have been proposed. These techniques attempt to gather pointer values at run time and check their aliasing during

Inria 1: int i = 0 2: int N = atoi (argv[1]) 3: int * p = malloc (N/2 + 42) 4: for i = 0; i < N/2; i + + do 5: p[i] = i 6: p[i + 42] = N -i 7: end for (a)
Example that illustrates the need to hybrid analysis.

1: int i = 0 2: int N = atoi (argv[1]) 3: int * p = malloc (N/2 + 42) 4: if N < 84 then 5:
for all i < N/2 do 6:

p[i] = i 7: p[i + 42] = N -i 8:
end for 9: else 10:

for i = 0; i < N/2; i + + do 11: p[i] = i 12: p[i + 42] = N -i 13:
end for 14: end if (b) Optimizing with hybrid analysis. the program execution. The information gathered during executions, namely, the taken paths and the memory actually accessed, contributes to make the analysis more precise on the tested inputs.

Comparing two pointer addresses takes only one cycle and thus, for one execution, dynamic alias analyses should be faster than static ones. However, results of dynamic analyses are specific to that execution since it is input-dependent. It can not be generalized to other inputs and analyses and optimizations should be done for each input.

Compared to static analysis, which is done once (at compile time), the overall overhead of dynamic analyses can be more significant. The reader may refer to [START_REF] Michael | Invited talk static and dynamic analysis: synergy and duality[END_REF][START_REF] Mock | Dynamic points-to sets: a comparison with static analyses and potential applications in program understanding and optimization[END_REF] for further comparison between static and dynamic analyses.

Our setting: scalable correct static analyses

Since we are interested in safety analysis and code optimization, we are interested in conservative analyses: a positive answer "no, they do not alias" will guarantee that the two pointers never overlap during execution. On the contrary, these analyses may fail to disambiguate some pairs of pointers (returning a "may alias" answer), even if there is no execution where the two pointers actually access the same block. Transformations and optimizations will not be enabled with "may alias" to stay safe.

Generally static analysis algorithms provide an imprecise analysis compared to the dynamic ones since they aim to be conservative thus give a safe estimation of pointed locations. In this study, we will only focus on static analyses.

Correctness is also considered as a mandatory condition. Correct alias algorithms are those without false negative answers, which means two pointers are said "no alias" when they do. As demonstrated by [START_REF] Wu | Effective dynamic detection of alias analysis errors[END_REF], this condition is often compromised but not usually detected.

We are also concerned by scalability issues. As we are dealing with compilation optimizations, we cannot pay too much for an alias analysis. Some of the previous approaches, designed for several verification contexts, have been shown not to be scalable. We expect that the algorithmic behind alias analyses for compilers should not be too costly in order to scale well. Memory is also an issue.

Applications of alias analyses inside compilers

As we have seen in Section 2, alias analyses are proposed and used for verification and optimization. Inside compilers, they are mostly used to perform transformations on source code, leading to many optimizations. In this section, we make an assessment of some optimizations that are clients of alias analyses. We provide examples in which we illustrate the need for alias analysis for more efficient program optimizations.

An application domain: program optimization.

Alias analysis for loop code motion Code motion consists in interchanging some statements or moving others. This optimization is beneficial especially in loops where loop invariant code motion (Licm) allows removing unchanged statements from the loop by hoisting or sinking them and therefore to avoid useless executions. Code motion is also used to improve data locality and optimize memory and cache accesses. Program snippet in Figure 4a shows a loop with a read from p and a write in p 2 . Clearly * p is never changed inside the loop since we don't write in p, and p and p 2 access disjoint pieces of memory. Thus, an analysis that provides these information would enable optimizing the loop by hoisting the load from the loop. Such an optimization (Figure 4b) saves a variable write and a store at each loop iteration.

Alias analysis for automatic parallelization Parallelization can be done within loops or between procedures using threads but in both cases we need alias analysis information to detect data race freedom.

Figure 5a shows a procedure Parallel that fills, in each loop iteration, two values in p, an integer array. Let p i = p + i and p N = p + Ni denote the array accesses at lines 4 and 5 respectively. Since i < N 2 , writes in p i and p N are always independent and can be done in parallel. Provided this "no alias" information, one can optimize this code to parallelize the loop which would give program in 5b. In some cases, for instance for the program depicted in Figure 7, an inter-procedural alias analysis is required to detect the absence of data-races between the two Fill_table calls at line 12 and 13. An automatic parallelization is then possible.

Instruction rescheduling.

Rescheduling code means interchanging some of its statements. This option can be profitable to improve data locality, or to enable further optimizations.

for i = 0; i < N/2; i + + do 4: p[i] = i 5: p[N -i] = N -i 6:
end for 7: end procedure . . . . . . Figure 6 shows a procedure Reschedule that fills data in two tables A and B, then copy B into table C. Since B is written in the first loop and then read in the third loop, interchanging the first and second loop would improve data locality. Such an optimization is only valid if A and B are disjoint tables and values of B are never rewritten by those of A, which is implied by a non-alias property between A and B. If this is the case, the program can be rescheduled into 6b and even further optimized by a loop fusion in 6c. for i = n 1 ; i < n 2 ; i + + do int * q = p + atoi(argv [START_REF] Ole | Program Analysis and Specialization for the C Programming Language[END_REF]) 12: spawn FILL TABLE (p, atoi(argv [START_REF] Ole | Program Analysis and Specialization for the C Programming Language[END_REF]), atoi(argv [START_REF] Bodík | ABCD: eliminating array bounds checks on demand[END_REF])) 13: spawn FILL TABLE (q, atoi(argv [2]), 2 × atoi(argv [2])) 14: end procedure while i < j do

5: if v[i] > v[ j] then 6: int tmp = v[i] 7: v[i] = v[ j] 8: v[ j] = tmp 9:
end if

10: i ++ 11: j -- 12:
end while 13: end procedure Dead code elimination. Dead code elimination optimization consists in removing useless statements (generally assignments) such as overwritten variables or writes that are never read.

Let us consider again the program of Figure 6a. We now suppose that B and C must "alias". Recall that must alias pointers start at the same location. Hence, these is no need to fill in table C in the third loop at line 9 because it is already done in loop at line 3 which fills table B. Loop at line 9 could be removed (the number of iterations is the same in both loops so the same fields are filled in).

Conclusion: a need for specialized information about pointers

As we have seen, alias analysis could be used to perform numerous optimizations on C code such as code motion and parallelization. Inside compilers, roles are divided into optimization passes that transform the program, and analyzing passes that perform analyses, including alias analysis.

However, optimizing passes are just clients of analysis passes that should provide them with the necessary information. Otherwise, transformations could not be done even though the analysis is correct and precise. In other words, analysis and transformation passes should speak the same language. In addition to the four types (at most) of alias response (may, must, partial alias, and alias), the compiler might need extra facts such as relations between variables and variable offsets (lower and upper bound).

As an example, in Figure 8, an analysis which do not track relationships between i and j may fail to infer that all v[i] and v[j] never refer to the same array accesses inside the loop.

Pentagons [START_REF] Logozzo | Pentagons: A weakly relational abstract domain for the efficient validation of array accesses[END_REF] is an abstract interpretation based algorithm that tracks "less than" relations between numerical variables (here, i and j, in addition to their value ranges). We think that such "semi-relational" analyses designed to fit particular optimization needs are promising and deserve to be further studied.

Inria 4 Experimental evaluation of pointer analyses inside stateof-the art compilers

Alias analysis output does not depend on whether its results would concretely be used for verification or optimization. However, what matters most is the efficiency and scalability of the approach. In this section, we evaluate the precision of the current analyses inside production compilers, and show that there is a huge gap between theory and practice.

C compilers: GCC, LLVM, ICC

Compilers are responsible for transforming abstracted programming languages into machine code.

A compiler includes three main components that process the input source file. These components are: the front-end, the middle-end, and the back-end. The front end parses the source code and generates an Intermediate Representation (IR), which will be analyzed and optimized in the middle-end. Depending on the machine architecture, the back-end generates the machine code based on the optimized representation.

In this section, we will study some of the production C compilers (CGG, LLVM, and ICC) to show that the alias analyses inside compilers are far from being satisfactory. We show how these three compilers handle the simple example of Figure 4a with the maximum level of optimization (O3).

GCC

The GNU Compiler Collection (GCC) is a collection of front-ends of C, C++, Java among others and their libraries. We are particularly interested in GCC, the C compiler.

In this section, we study assembly code generated by GCC 4.9.2 (gcc -S) when applied to code snippet in Figure 4a with O3 optimizations. Simplified results are depicted in Figure 9.

The C compiler GCC at this level of optimization is able to know that the loop will be executed at least once. Thus, it removes the assignment that associates 10 to a and instead assigns to a variable stored in p, which is 8 at this stage of program. It then executes the loop and, at each iteration, loads value of p and assigns it to a. As a conclusion GCC, even with -O3, fails to disambiguate pointers p and p 2 and does not hoist or sink the instruction a = * p outside the loop. Optimization level O3 relies on the default alias analysis, which is type-based, that just marks all variables of compatible types as aliasing.

LLVM

LLVM is the name of a research project at the University of Illinois. This project has contributed to a collection of modular and reusable compiler and tool-chain technologies. LLVM has clang as a front end which is a native C/C++/Objective-C compiler.

We now try to optimize the loop in program of Figure 4a using "opt" to activate LLVM optimizer (version 3.8). A simplified Intermediate Representation (IR) of optimized byte code is depicted in Figure 10. Similarly to GCC, LLVM which relies on the default optimization basicaa (for basic alias analysis) fails to disambiguate pointers p and p 2 and to provide the non-aliasing information to the Loop Invariant Code Motion (Licm) pass to optimize the code and remove the load from p 2 from the while loop.

ICC

ICC is the Intel C Compiler. The main purpose of ICC is to make C programs run faster on Intel architectures. We have tested code in Figure 4a using ICC 15 released in 2014. Simplified assembly generated with -O3 optimizations is depicted in Figure 11. Highlighted code shows the load from p which is kept inside the while loop. We conclude that Intel compiler is unable to disambiguate pointers p and p 2 and to hoist the load.

Restrict keyword

The restrict keyword is a C99 standard keyword that can be specified by the programmer to give the compiler information about aliasing. In fact, it is applied to a pointer p to say that only p or a pointer derived from it can access that memory region during its lifetime. Hence, if p is a restricted pointer then, any access to p's block must occur through p while p is alive. Otherwise, we have an undefined behavior. Let p and q be two pointers arguments of procedure f in Figure 12a. If f is not inlined, the compiler is not able to optimize it even using an interprocedural context-sensitive analysis. In fact, since linking is done after optimizations, optimizing a standalone function without keeping The loop has been unrolled by a factor of two. Another loop is also generated by ICC where the load is removed but replaced by a = 8. The flow gets into this loop as soon as p > p 2 (which implies that p and p 2 will never alias any more, since p 2 is decreasing).

a trace of its unoptimized version would be incorrect in some other call contexts. Adding the restrict keyword to procedure f is a declaration that programmers intent p and q to never alias.

No further alias analysis will be done by the compiler. Example 3 illustrates the benefit of using the restrict keyword by showing simplified assembly codes of f and f_res using LLVM and -O3. 1: procedure F RES(int * restrict p, int * restrict q, int a, int b) Example 3 Figure 13 gives a simplified assembly code generated after LLVM O3 optimizations applied to f and f_res in Figure 12. The compiler here associates %rdi to pointer p and %rsi to pointer q. The main difference between 13a and 13b is two extra memory accesses (a load and a store) done in 13a. In fact, with the restrict keyword, p and q are supposed not to alias. Addresses (p + a) and (q + b) are then disjoint and any write in p[a] does not affect any read from q[b]. Therefore, the compiler can optimize this code by loading only once the value stored in q[b] and not storing the first sum (p[a] + q[b]) in q[a] since we have a write-write dependence. Extra store and load are depicted respectively line 5 and line 6 in Figure 13a. Without such aliasing information, the compiler is unable to perform this optimization. For the readability of Figure 13, the reader may note that lines 2, 4 and 7 in Figure 13a are equivalent to lines 2, 5 and 7 in Figure 13b and correspond respectively to p[a].

1: procedure F(int * p, int * q, int a, int b) 2: p[a] = p[a] + q[b] 3: p[a] = p[a] + q[b] 4: end procedure
2: p[a] = p[a] + q[b] 3: p[a] = p[a] + q[b]
Experimental evaluation of pointer analyses inside state-of-the art compilers GCC, LLVM and ICC shows that these compilers fails in carrying out optimizations based on pointer analyses for simple benchmarks. Some published techniques have probably tried to improve these results and might theoretically succeed in optimizing them, but the fact that they are not added to compilers and not available in the distributed version of compilers still shows a certain amount of inefficiency.

restrict.

(b) Procedure with restrict keyword.

Figure 13: Impact of using the restrict keyword on f. The highlighted code on the left is unnecessary if we know that p and q alias.

Discussion

Toward new pointer analyses in compilers. As we saw, mainstream compilers still struggle to distinguish intervals within the same array. Our study confirms that pointer analyses often fail to disambiguate regions addressed from a common base pointer via different offsets, as stated by Yong and Horwitz [START_REF] Hsi | Pointer-range analysis[END_REF]. Field-sensitive pointer analysis could provide a partial solution to this problem. These analyses can distinguish different fields within a record, such as a struct in C [START_REF] Pearce | Efficient field-sensitive pointer analysis for C[END_REF], or a class in Java [START_REF] Yan | Demand-driven context-sensitive alias analysis for java[END_REF]. However, they rely on syntax that is usually absent in the low level program representations adopted by compilers. We believe that actually implementing such analyses inside production compilers is still a challenge.

A proposition for alias analyses with offsets. Recently, we proposed an analysis that combines range analysis and pointer analysis [START_REF] Vitor Paisante | Symbolic range analysis of pointers[END_REF]. The main idea is to disambiguate pointers by comparing their base pointers and possible addressable memory offsets. We use an abstract interpretation based algorithm where we compute offsets from abstract program locations. Our analysis strongly relies on a preprocessing that computes parametric ranges of numerical variables. The solution that we have proposed is sparse and relies on Extended Static Single Assignment E-SSA form [START_REF] Bodík | ABCD: eliminating array bounds checks on demand[END_REF] to achieve efficiency. Indeed, pointers are disambiguated within two steps: the first step is a global analysis that allows disambiguating pointers in the whole program by iterating and solving an abstract constraint system until achieving a fix point. A widening operator is used to ensure convergence. The second step is a local refinement that permits to disambiguate pointers inside loops.

Experimental results show that this solution implemented on the top of LLVM compiler is fast, scalable (quasi-linear in the number of lines of code) and succeeds in disambiguating more pairs Inria of pointers compared to basic alias analysis of LLVM. It was for instance able to disambiguate pointers p + a and q + b in procedure F (Figure 12) without using the restrict keyword and to remove the extra load and store as detailed in Example 3. However, our experiments show that the new alias analysis enables less optimizations than what was expected. We therefore suppose that a dysfunction between analysis passes and optimization ones is occurring and conclude that what matters most is not the efficiency of the analysis and its scalability but information shape provided to optimizing passes.

Conclusion

In this paper we have presented an overview of state-of-the art techniques for pointer analyses. Although this topic has received much attention in the last decades, we believe that new analyses remain to be defined to fit the special needs of optimization in state-of-the-art compilers. The designers of such analyses should pay a particular attention to the actual implementation of the compilers to design simple but efficient analyses. We also strongly believe that there remains work to be done on client analyses that intensively use the results of alias analyses.

Figure 1 :

 1 Figure 1: Concrete representation of memory regions in case of no, partial and must aliasing. Each represents a memory slot.

Figure 2 :

 2 Figure 2: Example for out-of-bounds memory analysis.

Figure 3 :

 3 Figure 3: Hybrid Analysis.

8 : * p 2

 82 1: int * p = malloc (2*N*sizeof(int)) 2: int * p 1 , * p 2 , * a 3: * p = 8; * a = 10 4: p 1 = p + N 5: p 2 = p + 2 × N 6: while p 2 > p 1 do end while(a) Example for possible loop invariant code motion.1: int * p = malloc (2*N*sizeof(int)) 2: int * p 1 , * p 2 , * a 3: * p = 8; * a = 10 4: p 1 = p + N 5: p 2 = p + 2 × N 6: a = * p 7: while p 2 > p 1 do

Figure 4 :

 4 Figure 4: Optimizing a program with code motion given a no-alias information.

Inria 1 :

 1 procedure PARALLEL(int * p, int N)

  (a) Example for possible parallelization.

1 :

 1 procedure PARALLEL THREAD(int * p, int N) Parallel procedure parallelized after no alias analysis results.

Figure 5 :

 5 Figure 5: Use of no alias result for parallelization.

1 :

 1 procedure RESCHEDULE(int * A, int * B, int * C, int L, . . . ) 2:int i; int j; int k 3:for i = 0; i < L; i++ do 4:for j = 0; j < 2L; j++ do 7:A[ j] = ...

  13: end procedure (a) Initial Reschedule procedure.

1 :

 1 procedure RESCHEDULE(int * A, int * B, int * C, int L, . . . ) 2:int i; int j; int k 3:for j = 0; j < 2L; j++ do 4:A[ j] = ...

  for i = 0; i < L; i++ do

  13: end procedure (b) Procedure Reschedule after rescheduling.

1 : 3 :

 13 procedure RESCHEDULE(int * A, int * B, int * C, int L, . . . ) 2: int i; int j; int k for j = 0; j < 2L; j++ do 4: A[ j] = ...

6 :

 6 for i = 0; i < L; i++ do end procedure (c) Optimized Reschedule procedure.

Figure 6 :

 6 Figure 6: Using alias analysis for rescheduling.

8 :

 8 procedure MAIN(int argc, int * * argv) 9:assert atoi(argv[START_REF] Ole | Program Analysis and Specialization for the C Programming Language[END_REF])<atoi(argv[START_REF] Bodík | ABCD: eliminating array bounds checks on demand[END_REF]) 10:int * p = malloc (2 × atoi(argv[START_REF] Bodík | ABCD: eliminating array bounds checks on demand[END_REF]))11:

Figure 7 :

 7 Figure 7: Example for data race freedom detection

Figure 8 :

 8 Figure 8: Pentagons analysis for parallelization.

  -> a ; %r c x -> p2 , %rax ->

Figure 9 :

 9 Figure 9: Simplified assembly code given by gcc -O3 applied to code_motion.c.The boxed instruction stays inside the L6 loop.

Figure 10 :

 10 Figure 10: Simplified IR given by clang -O3 applied to code_motion.c. %1 designs pointer p and %3 variable a in the while body. Here again, the boxed instruction is not hoisted out of the loop.

Inria

2 Figure 11 :

 211 Figure11: Simplified assembly code given by icc -O3 applied to code_motion.c. The loop has been unrolled by a factor of two. Another loop is also generated by ICC where the load is removed but replaced by a = 8. The flow gets into this loop as soon as p > p 2 (which implies that p and p 2 will never alias any more, since p 2 is decreasing).

  (a) Procedure without restrict keyword.

4 :

 4 end procedure (b) Procedure with restrict keyword.

Figure 12 :

 12 Figure 12: Syntax of restrict keyword.

2 2 . 1 2 . 2 2 . 3 2 . 4 2 . 5 2 . 6 7 3 3 . 1 10 4

 21222324252673110 Alias analysis: context and related work 4 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Static analyses of pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Complexity and scalability of pointer analyses . . . . . . . . . . . . . . . . . . . . 5 Static analyses with runtime checks . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Dynamic analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Our setting: scalable correct static analyses . . . . . . . . . . . . . . . . . . . . . Applications of alias analyses inside compilers 8 An application domain: program optimization. . . . . . . . . . . . . . . . . . . . 8 3.2 Conclusion: a need for specialized information about pointers . . . . . . . . . . . Experimental evaluation of pointer analyses inside state-of-the art compilers 11 4.1 C compilers: GCC, LLVM, ICC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 GCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 LLVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.4 ICC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.5 Restrict keyword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 :

 1 procedure FILL TABLE(int * p, int n 1 , int n 2 )

	2:	int i; int * p 1
	3:

RR n°8812

* This work was supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).