Andrew J Muir

Fred F Poordad

John G Mchutchison

Mitchell L Shiffman

Thomas Berg

Peter Ferenci

Jenny Heathcote

Jean-Michel Pawlotsky

Stefan Zeuzem

Henk W Reesink

Retreatment with telaprevir combination therapy in hepatitis C

à 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.

Table 3. Adverse Events Leading to Discontinuation and Most Common Adverse Events Reported According to Treatment Group

*Unassigned patients discontinued treatment prior to week 12 assignment of treatment duration. **Adverse events leading to discontinuation in >2 patients. ‡This category includes all patients experiencing rash events as assessed with the use of a group of related terms to identify all dermatologic events. All treatment discontinuations due to rash happened during telaprevir phase.

†Using a variety of descriptive terms to identify all dermatologic events, rash events occurred in 44%, 53%, 100%, and 48% of T12PR24, T12PR48, Unassigned, and Total patients, respectively.


AMD Dibyendu Das
email: dibyendu.das@amd.com

India Pvt

Ltd Beno

Î T Dupont

D E Dinechin

Kalray Ltd

INRIA Ramakrishna Upadrasta
email: ramakrishna.upadrasta@inria.fr.

A Efficient Liveness Computation Using Merge Sets and DJ-Graphs

Keywords: D.3.4 [Programming Languages]: Processors-Compilers; D.3.3 [Programming Languages]: Language Constructs and Features-Control structures Liveness, Algorithms, Compilers Liveness, SSA, Merge Set, Dominator Tree, DJ-graph, Optimizing Compilers

In this work we devise an efficient algorithm that computes the liveness information of program variables. The algorithm employs SSA form and DJ-graphs as representation to build M erge sets. The M erge set of node n, M (n) is based on the structure of the Control Flow Graph(CFG) and consists of all nodes where a φ-function needs to be placed, if a definition of a variable appears in n. The merge sets of a CFG can be computed using DJ-graphs without prior knowledge of how the variables are used and defined. Later, we can answer the liveness query (as a part of other optimization or analysis phase) by utilizing the knowledge of the use/def of variables, the dominator tree and the pre-computed merge sets. On average, merge sets have been shown to be of size comparable to the Dominance Frontier(DF) set of a CFG and can be computed efficiently for all kinds of applications consisting of both reducible and irreducible loops. This is an advantage over existing algorithms which require additional complexities while handling applications using irreducible loops. For cases where the merge sets have already been created during the SSA construction step, the cost of our algorithm reduces even further when we use these merge sets for liveness computation. We have compared our new algorithm with a recent algorithm for computing liveness based on SSA form, and show how it performs better in practice, though being simpler to understand and implement.

INTRODUCTION

Live variable analysis (or simply liveness analysis) is a classic data flow analysis [START_REF] Morgan | Building an Optimizing Compiler[END_REF][START_REF] Cooper | Efficiently computing Static Single Assignment Form and the Control Dependence Graph[END_REF] performed by compilers to calculate for each program point the variables that may be potentially read before their next write. Thus, liveness information is an important aspect for various optimization phases. Some of the well-known optimization passes that require liveness analysis are register allocation [START_REF] Chaitin | Register Allocation Via Coloring[END_REF][START_REF] Briggs | Improvements to Graph Coloring Register Allocation[END_REF]] and global instruction scheduling (software pipelining, trace scheduling) [START_REF] Srikant | The Compiler Design Handbook: Optimizations and Machine Code Generation[END_REF], assuming these techniques work directly from the SSA form [START_REF] Hack | Register Allocation for Programs in SSA form[END_REF]]. Classical dataflow-based iterative liveness analysis uses bitsets to represent live-in/live-out status of a variable at a program point. Given the use/def points of variables, it uses a set of dataflow equations to update the bitsets. Once the bitsets are computed for all program points, the question of whether a variable is live-in/live-out can be easily found using set membership tests on the bitsets. Though such iterative solutions may not be very expensive in practice, optimization phases may add new variables or modify the CFG. This invalidates the liveness information resulting in the entire iterative process to be repeated making the overall process costly.

In a recent work published by [START_REF] Boissinot | Fast Liveness Checking for SSA-Form Programs[END_REF], an efficient algorithm is presented for fast liveness checking of programs in SSA form using a pre-computation step followed by the actual liveness computation step. The precomputation step enables part of the liveness computation that is dependent on the topological structure of the CFG, to be stored early. Once, a variable, its use and define points and the point where the liveness question is being asked, are known, the precomputed information can be combined with these to arrive at the answer quickly. One of the advantages of this method is that the liveness information survives all program transformations except for changes in the CFG.

The idea of a pre-computation step followed by the actual computation step for program analysis has previously been used to efficiently insert φ-functions for converting programs to SSA forms by [START_REF] Das | A Practical and Fast Iterative Algorithm for φ-function Computation Using DJ-Graphs[END_REF]. In that paper the authors pre-compute the merge sets of the nodes of the CFG in a top-down iterative manner utilizing a DJ-graph [START_REF] Sreedhar | A Linear Time Algorithm for Placing φ-nodes[END_REF]]. This step is followed by the actual φ-function insertion step when the variable and its define points are known. The authors also show how such an iterative top-down algorithm is quite efficient in practice outperforming such standard algorithms as [Cytron et al. 1991]. In an earlier work on control dependence computation, Pingali and Bilardi [START_REF] Pingali | APT: A Data Structure for Optimal Control Dependence Computation[END_REF] introduced the idea of pre-computing a data structure that is queried repeatedly during the analysis phase.

In the present work we show how the merge sets can also be effectively utilized to carry out liveness analysis in a fast and efficient manner for programs in SSA form. The merge set of a node n (belonging to the CFG) denoted as M (n) can be derived solely from the CFG structure. Loosely, M (n) encodes the set of nodes where multiple paths merge or join. Using this information added with the knowledge of how variables are used and defined, we can compute the liveness information using a two-step method. The first step involves the computation of M (n) for all nodes n of the CFG while the second step involves using these M (n) sets and the use/def of variables to compute liveness.

Our algorithm can handle arbitrary control flow graphs that may include irreducible loops [START_REF] Havlak | Nesting of Reducible and Irreducible Loops[END_REF][START_REF] Ramalingam | On Loops, Dominators and Dominance Frontiers[END_REF]]. In addition, if merge sets have already been used to compute the φ-function placement, while converting the program into SSA form, then, our algorithm has a very low-cost pre-computation step, as the merge sets are readily available without any need to re-compute them.

For a detailed introduction and discussion on merge sets one can refer to the work by Pingali and Bilardi [START_REF] Bilardi | Algorithms for Computing the Static Single Assignment Form[END_REF]. For a description of how these sets can be computed efficiently in a compiler, one can refer to the work [START_REF] Das | A Practical and Fast Iterative Algorithm for φ-function Computation Using DJ-Graphs[END_REF]. Nevertheless, in this paper we will introduce the merge sets briefly.

Our Contributions

The contributions of this paper are the following:

-Given a program in SSA form we show how liveness information can be computed simply and efficiently using merge sets. This is the first known instance of merge sets being used for computing SSA-based liveness information. -Our work provides insight into how merge sets can be visualized as a unifying concept for computing liveness in SSA-form programs with both reducible and irreducible loops, without resorting to additional data structure (like loop nesting forests [START_REF] Ramalingam | On Loops, Dominators and Dominance Frontiers[END_REF]) for handling irreducible loops. -This work also shows how merge sets provide a scalable mechanism for liveness computation in SSA form due to linear memory requirements (in the size of the CFG) for storing merge sets as opposed to other forms of supporting data-structures which may not scale well with the size of the CFG. -Finally we present experimental results showing how the new mechanism fares better than the existing mechanisms.

Paper Organization

The paper is organized as follows. Section 2 provides the preliminary definitions, a motivating example including an overview of merge sets and Boissinot's algorithm. In Section 3 we discuss our new algorithms for computing live-in and live-out for liveness queries at entry/exit of basic blocks. Section 4 contains the correctness proofs. Section 5 deals with experimental results. In Section 6 we provide related work. We end with conclusion and future work in Section 7.

PRELIMINARIES

In this section we briefly define the following :

CFG. CF G = V, E is a tuple consisting of a set of nodes V and a set of directed edges E ⊆ V × V , with a special node EN T RY (root) ∈ V , from which, there exists a path to every node and a special node EXIT ∈ V to which every node has a path. The x + → y notation will represent a path from node x to node y in the CFG which is non-empty. Possibly empty paths will be denoted as x * → y.1 Back-Edge. A back-edge in a CFG is defined to be an edge of the form u → v, when v is an ancestor of u in the DFS tree of the CFG. A back-edge free path p + → q is a path which does not contain any back-edges. Havlak [START_REF] Havlak | Nesting of Reducible and Irreducible Loops[END_REF]] and Ramalingam [START_REF] Ramalingam | On Loops, Dominators and Dominance Frontiers[END_REF]] have posited on various interpretations of a back-edge -especially for irreducible graphs. In this work, we will use the definition stated above.

Dominance.

A transitive, antisymmetric, reflexive relation on V such that, a node v is said to dominate node w, v dom w if every path from EN T RY to w has v. It can be represented as a tree with EN T RY as root. If v = w, then v is said to strictly dominate w. Dominator Tree. A dominator tree DT = V, E DomT ree is a tree whose root node is the EN T RY node of the CFG, the nodes are the nodes of the CFG and the edges (denoted as D-edges) are idom(v) → v where idom(v) is the immediate dominator of v. The immediate dominator of v is the closest strict dominator on any path from EN T RY to v. Though idom(v) → v is a directed edge, the reverse edge v → idom(v) is also maintained. This allows us to visualize DT as a undirected tree.2

Level. Level of a node v is the distance of the node from the EN T RY node in the dominator tree. EN T RY has level 0, its children have level 1 and so on.

J-edges.

If e = (s, t) ∈ E but s does not strictly dominate t, then e is called a J-edge and s is the source and t the target nodes [START_REF] Sreedhar | A Linear Time Algorithm for Placing φ-nodes[END_REF]. We will denote a J-edge as s J → t. A J-edge has the property that idom(t) strictly dominates s and is an ancestor of s in the dominator tree. This follows from Lemma 3.1 in [START_REF] Sreedhar | Efficient Program Analysis Using DJ Graphs[END_REF].

Tree-Path. Let V, T be a undirected tree. For v, w ∈ V , the notation [v, w] represents the set of vertices on the simple path joining v and w. Similarly, the notation [v, w) represents the set of vertices on the simple path joining v and w, not including w. For example, in the dominator tree of Figure 1(b) (ignoring the J-edges), [9, 3] denotes the set {9, 8, 3}, while [6, 2) denotes the set of nodes {6, 3}. This definition can be found in Pingali and Bilardi [START_REF] Pingali | APT: A Data Structure for Optimal Control Dependence Computation[END_REF]. Throughout this paper, the tree in question will be the dominator tree DT .

Shadow(e).

Given an edge e = s J → t, where idom(t) is known to strictly dominate s, Shadow(s J → t) is defined as the set of nodes in the dominator tree from node s to node idom(t), excluding node idom(t). In tree-path notation, Shadow(s

J → t) = [s, idom(t)).
For example, Shadow(10

J → 8) = [10, 3) = {10, 9, 8} in Figure 1(b). Also, Shadow(5 J → 6) = [5, 3) = {5}.
DJ-graph. [START_REF] Sreedhar | A Linear Time Algorithm for Placing φ-nodes[END_REF] define a DJ-graph as a dominator tree with the J-edges added. The DJ-graph is a directed graph and both the D-edges and J-edges are directed edges. Though a D-edge idom(v) → v is a directed edge, the reverse edge v → idom(v) is also maintained. This helps in traversing up and down the DJ-graph using these bi-directional edges. Though subsequent diagrams will show D-edges as directed in one direction, in reality these are bi-directional edges and will be assumed as such.

S(tatic) S(ingle) A(ssignment) Form.

In compiler design, static single assignment form is an intermediate representation (IR) in which every variable is assigned exactly once. Existing variables in the original IR are split into versions, new variables typically indicated by the name with a subscript, so that every definition gets its own version. In SSA form, use-def chains are factored such that every use has a single definition.

I(mmediate) DOM(inator) P(ath).

The immediate dominator path of a node n, denoted as IDOM P (n), is the set of nodes lying on the dominator tree from the node n, all the way up to the root node of the dominator tree. Thus IDOM P (n) is the tree-path [n, root] in the dominator tree DT . For example IDOM P (8) = [8, root] = {8, 3, 2, 1, root} in Figure 1(b). IDOM P (X) where X is a set of nodes is defined as IDOM P (X) = n∈X IDOM P (n). φ-function. When a program is being put in SSA form multiple definitions of the same variable converge at control-flow join points. In order to disambiguate which of the new variables to use, the SSA form introduces the abstract concept of φ-functions that select the correct one depending on control flow.

D(ominance) F(rontier).

A node v is said to be in DF (w), if a predecessor of v is dominated by w but v is not strictly dominated by w. The transitive closure of DF is referred to as DF + . This relation can be represented by a graph called the DF-graph. I(terated) D(ominance) F(rontier). Cytron et al. [Cytron et al. 1991] introduced this method for placing φ-functions. Finding the φpoints for a set N α for a variable v is done by seeding the output set with N α , and adding the DF of each element of the set to it, till no new nodes can be added. Thus, IDF (x) = DF + (x).

Here, N α is the set of nodes where variable v is defined.

IsLiveIn(n,a).

A variable a is live-in at a node n of a CFG, if there exists a path from node n to a node u where a is used and that path does not contain any definition of a.

IsLiveOut(n,a).

A variable a is live-out at a node n if it is live-in at a successor of n.

Throughout the paper we will use def (a) to denote the node containing the single dominating definition of a variable a, while uses(a) will denote the set of nodes which contain the uses of variable a, each such node being dominated by def (a) as the program is in SSA form.

A Motivating Example

In the CFG shown in Figure 1(a) derived from [START_REF] Boissinot | Fast Liveness Checking for SSA-Form Programs[END_REF], three variables w, x, y are defined in node 3 while x is used at node 9, y at node 5 and w at node 4. The corresponding DJ-graph and its merge sets are shown in Figure 1(b). The DJ-graph consists of the dominator tree of the CFG with the J-edges superimposed on it. An easy way to visualize the construction of the DJ-graph is to first create the dominator tree of a CFG. Consider E DomT ree to be the set of edges in the dominator tree. Find the set E -E DomT ree i.e. all the edges in the original CFG which are not edges in the dominator tree. This constitutes the set of J-edges. For example, the back edge from node 7 to node 2 in the CFG transforms to a J-edge in the DJ-graph as it does not figure as an edge in the dominator tree. The entire set of J-edges comprises of the edges

{7 J → 2, 5 J → 6, 6 J → 5, 4 J → 5, 9 J → 6, 10 J → 8}.
If we use Figure 1(a) for the query IsLiveIn(10, w) (i.e. whether the variable w is live at node 10), the answer we should get is a f alse value. This follows from the fact that the only way to reach a use of w in node 4 from node 10 is via the following path 10 → 8 → 9 → 6 → 7 → 2 → 3 → 4 in the CFG. But due to variable w being defined in node 3, w is not live at node 10. On the other hand, for the query IsLiveIn(8, y) we see that the path from node 8 that can reach a use of variable y in node 5 in the CFG is 8 → 9 → 6 → 5 with no def (y) lying in the path. Hence the query should return a true value.

Merge Set and Merge Relation

Let us define first the notion of a join set J(S) for a given set of nodes S in a control flow graph. The merge relation is defined as a relation v = M (u) that holds between two nodes u and v whenever v ∈ J({root, u}) [START_REF] Bilardi | Algorithms for Computing the Static Single Assignment Form[END_REF]]. We insert a φ-function at v for a variable that is assigned at u. For any node u ∈ V , v ∈ M (u) if and only if there is a path u + → v that does not contain idom(v). The merge sets for the nodes of the CFG in Figure 1 are provided. For example, node 2 ∈ M (7) where the paths root + → 2 and 7 + → 2 meet.

(1) = { } M(2) = { 2 } M(3) = { 2 } M(4) = { 2,5,6 } M(5) = { 2,5,6 } M(6) = { 2,5,6 } M(7) = { 2 } M(8) = { 2,5,6,8 } M(9) = { 2,5,6,8 } M(10) = { 2,5,6,8 } M(11) = { } CFG: DJ-Graph: (a) (b) J-edge D-edge

Merge Sets: Computation and Advantages

M (n) of a node n can be efficiently computed using a top-down iterative pass over the DJ-graph. A simple and efficient algorithm for construcing merge sets, that handles in a unified manner, both the cases of CFGs with reducible and irreducible loops by a topdown iterative construction algorithm has been given by [START_REF] Das | A Practical and Fast Iterative Algorithm for φ-function Computation Using DJ-Graphs[END_REF]. In the later sections, we will show that these advantages of merge sets, along with simplicity of construction and storing of DJ-graph could reflect well on the liveness computation.

2.3.1. Size of merge sets. One of the important observations on the sizes of merge sets is that for a node n, the average size of |M (n)| is usually a small constant number irrespective of the size of the CFG. Hence, the total storage requirement for the merge sets of a CFG having V nodes is O(|V |). In Table II for the experiments conducted on a set of benchmarks the total merge set storage requirement for a CFG varies from 1.5x to 2.3x of the total size of |V | on an average.

Handling irreducible loops in CFGs.

The other observation is that using merge sets removes the need for special cases that are needed for programs with irreducible loops. [START_REF] Havlak | Nesting of Reducible and Irreducible Loops[END_REF][START_REF] Ramalingam | On Loops, Dominators and Dominance Frontiers[END_REF]] use special and non-trivial constructions for handling the back edges in these programs with these kinds of loops.

Irreducible loops create issues as back edges are not well-defined in CFGs as shown in [START_REF] Havlak | Nesting of Reducible and Irreducible Loops[END_REF][START_REF] Ramalingam | On Loops, Dominators and Dominance Frontiers[END_REF]. Identifying back-edge targets for irreducible loops usually requires pre-processing of the CFG. The pre-computation steps in Boissinot's algorithm [START_REF] Boissinot | Fast Liveness Checking for SSA-Form Programs[END_REF]] is dependent on the formation of a set called the T q set which contains all back-edge targets relevant for a liveness query at node q. When irreducible loops appear, this algorithm suffers from increased complexity due to additional pre-processing.

A merge set based pre-computation mechanism does not suffer from these drawbacks as CFGs with reducible and irreducible loops are handled in a unified manner by the top-down iterative merge set construction algorithms. Irreducible loops may lead to multiple top-down passes during merge set construction phase, depending on the number of nodes that make up such irreducible loops [START_REF] Das | A Practical and Fast Iterative Algorithm for φ-function Computation Using DJ-Graphs[END_REF]. Since the number of nodes which make up an irreducible loop is small in practice, the number of passes are usually constrained to a small number. Also, our liveness query algorithms do not depend on finding back edges of loops.

Boissinot's Algorithm

In this part we will briefly describe Boissinot's approach to answer the IsLiveIn/IsLiveOut queries for SSA-form programs. As stated in the introduction, the algorithm is divided into two phases. The first phase computes certain path-specific information of the CFG, which is subsequently used in the second phase to answer the liveness queries. For a variable a, assume that the dominating definition is at node d, a use is at node u ∈ uses(a), and the liveness query is being asked at node q via IsLiveIn(q, a).

Boissinot's algorithm relies on two observations. The first is that a is live-in at q if a back-edge-free path q + → u, exists (assuming q = u). Also, d should not be part of this path. Using this observation, Boissinot define a reduced graph G from G such that it contains all the nodes and edges of G, excepting the back edges. If x + → y is a valid path in G, it is said that y is reduced reachable from x. For each node x, the nodes that are reduced-reachable from x are stored in the set R x . It can be seen that when u ∈ R q , a is live-in at q.

The second observation derives from paths that contain back-edges. Even if there exists no reduced-reachable path from q + → u, one may still reach u from q by following a mix of reduced-reachable paths and back-edges. There may be multiple such paths which may reach u from q, but the existence of one where d does not appear suffices to make a live at q. To take care of the presence of back-edges, the relevant back-edge target nodes that may affect the answer of a liveness query at q are stored in the set T q . A set of recursive data-flow equations are defined to compute T q as shown below.

T q = ∞ i=0 T i q T i q = t∈T i-1 q T ↑ t , T 0 q = {q} T ↑ t = {t ′ ∈ V \R t |∃s ′ ∈ R t ∧ (s ′ , t ′ ) ∈ E ↑ },
where, E ↑ is the set of back-edges.

Boissinot's algorithm now proceeds to the second phase where it answers a query about the live-in status of a variable a at node q. For this, it includes only nodes that belong to T q which are additionally dominated by d, calling it the T (q,a) set. For every node in T (q,a) , if a u is reachable in G, the algorithm returns a true value. If none of the u ∈ uses(a) is reachable it returns a f alse value. The live-out status of a variable can be computed similarly.

For the example in Figure 1(a) let us try to evaluate T 9 = ∞ i=0 T i 9 = T 0 9 ∪ T 1 9 . . . which is required in order to answer the IsLiveIn(9, w) query. From the equations, T ↑ 9 can now be computed as {2, 5, 8} as these are the nodes in E ↑ whose sources are in R 9 but targets are in V \R 9 . T 9 will eventually be {2, 5, 8}. Nodes 5 and 8 are two nodes which are part of T 9 and are dominated by def (w). But from none of these nodes can we reach the use(w) at node 4 using the reduced reachability graph. Hence IsLiveIn(9, w) query returns a f alse value. The primary disadvantage of Boissinot's approach is that it is an involved algorithm and can theoretically perform sub-optimally in the presence of irreducible loops. In the next section, we present an algorithm that is theoretically much simpler and performs well practically.

T 0 9 = {9}. T 1 9 = t∈T 0 9 T ↑ t . As T 0 9 = {9}, T 1 9 = T ↑ 9 . R 9 = {6, 7, 10}. We now need to find {t ′ ∈ V \R 9 |∃s ′ ∈ R 9 ∧(s ′ , t ′ ) ∈ E ↑ }. E ↑ = {10 → 8, 7 → 2, 6 → 5}

NEW ALGORITHM FOR COMPUTING LIVENESS OF VARIABLES

We will now outline new algorithms called the IsLiveInU singM ergeSet and IsLiveOutU singM ergeSet for computing the liveness information of variables at the entry and exit of basic blocks. These can also be used for computing liveness information at arbitrary points inside basic blocks. The algorithms are designed along the lines of the IsLiveIn and IsLiveOut query algorithms as outlined in Boissinot et al. [START_REF] Boissinot | Fast Liveness Checking for SSA-Form Programs[END_REF], the main difference being that our algorithms provide for liveness information using the pre-computed merge sets and dominator tree. Our algorithms assume that the merge sets of the nodes of a CFG have been pre-computed and ∀n ∈ V , the set M (n) is available. As stated earlier, if a merge set based φ-function placement algorithm is used for SSA construction, these sets may be readily available. In optimizers, where conversion to SSA form happens through more conventional algorithms as [Cytron et al. 1991], merge sets will need to be pre-computed, preferably via the top-down iterative process mentioned earlier.

Informal reasoning of Using Merge Sets

To clarify the role of merge sets in liveness analysis, assume that we are trying to answer the IsLiveIn(n, a) query. In Figure 2 we show two general cases where the variable a is defined at node X and used at node u and X dominates u (where u ∈ uses(a)). In the case in Figure 2 IsLiveIn, the path n + → m + → u does not have a definition of a and hence a is live-in at n. In this case, too, m ∈ M (n) and m dom u hold true when IsLiveIn(n, a) is true. Thus, for both of these cases we see that for a use u, there exists a node m that dominates u and node m belongs to M (n).

For the cases above, n does not dominate u. If there is a single path from n to u, then, n should dominate u. If def (a) does not appear in n + → u, then IsLiveIn(n, a) is also true. Hence, for liveness queries we need to check whether ∃s ∈ {M (n) ∪ {n}} and s dom u. This observation is the basis of our algorithms that follow. Similar observation can be made when IsLiveIn(n, a) is f alse. In such cases, we encounter def (a) before encountering any node in {M (n) ∪ {n}} when we climb up from u using the tree-path [u, root]. Note that node n may belong to the set M (n).

We will use the notation M r (n) to denote {M (n) ∪ {n}}. IsLiveIn(n, a) can now be defined as:

IsLiveIn(n, a) = ∃u ∈ uses(a)|M r (n) ∩ [u, def (a)) = φ
where [u, def (a)) = (IDOM P (u) -IDOM P (def (a))).

Algorithm IsLiveInU singM ergeSet

As the firststep of computing IsLiveInU singM ergeSet(n, a), we create the M r (n) set by adding the node n to the M (n) set as shown in Line 1 of Algorithm 1. In the next step shown in Line 3, we loop over all the nodes in uses(a). For each node t ∈ uses(a), we climb up the dominator tree if we do not encounter one of the nodes in M r (n) before encountering the def (a) node. In brief, we check the nodes in the tree-path [u, def (a)), where u ∈ uses(a), to see whether we encounter a node m ∈ M r (n). This is depicted in the while loop from Lines 4 to 10. When [u, def (a)) ∩ M r (n) is not an empty set, the variable a is designated live-in at node n and the algorithm returns a true value. After traversing through all the nodes in uses(a) if we do not encounter M r (n) in any [u, def (a)), then a is not regarded as live-in at n and the algorithm returns a f alse value. The pre-computed (or available) merge sets are preserved and used during this liveness query step.

Let us use the new IsLiveInU singM ergeSet to answer the liveness queries as in Section 2. For the query IsLiveInU singM ergeSet(10, w) we first compute M r (10). Using the merge sets given in Figure 1 we see that M r (10) = {2, 5, 6, 8, 10}. Also, def (w) = {3}, uses(w) = {4} and [u, def (a)) = [4, 3] = {4}. If we climb up the dominator tree starting at node 4, the first node we reach is node 3 before we encounter any of the nodes in M r (10). This implies that the while loop at Line 4 exits and a f alse value is returned. Hence, node w is not live-in at node 10 as [4, 3) ∩ M r (10) is empty. For the query IsLiveInU singM ergeSet(8, y), M r (8) = {2, 5, 6, 8}. def (y) = {3}, uses(y) = {5} and [u, def (a)) = [5, 3) = {5}. Node 5 in the DJ-graph also belongs to M r (8). Hence [5, 3) ∩ M r (8) is non-empty and a true value is returned by the algorithm implying that y is live-in at node 8.

In Figure 3(a) we show the case for IsLiveInU singM ergeSet(10, w). The working of IsLiveInU singM ergeSet(8, y) is depicted in Figure 3(b). The Start and End markers specify the start and end nodes of the upward walks of the dominator tree.

The while loop in Line 4 of the algorithm climbs up the dominator tree traversing the IDOM P (x) = [x, root] where u ∈ uses(a). The size of IDOM P (u) is controlled by the height of the node u in the dominator tree. Assume that the average height of a node in the dominator tree is given by h DomT ree avg and given that the intersection operation in Line 5 takes a small constant time, the complexity of the algorithm is given by O(|uses ) under the assumption of small constant size of |uses(a)| avg . Rigorous complexity computation of our algorithms along the lines of [START_REF] Blieberger | Average Case Analysis of DJ-Graphs[END_REF]] has not been attempted in this paper.

CORRECTNESS PROOFS

The following lemmas demonstrate how liveness analysis can be correctly computed using merge sets and DJ-graphs. We will provide the proof of correctness of IsLiveInU singM ergeSet(n, a). The correctness of live-out can be derived along similar lines. For the proofs we will only discuss the general case when there exists a path from node n to u, u ∈ uses(a) and n, M (n) and u are distinct. For other cases, proofs can be worked out on similar lines.

The basic step used in IsLiveInU singM ergeSet(n, a) is a bottom-up traversal of the DJ-graph from each use u ∈ uses(a), till an element m ∈ M r (n) is found. If found, the algorithm returns a true value. If, instead, a def (a) is encountered, ∀u ∈ uses(a), then, a f alse value is returned. Thus, the correctness of the algorithm is dependent on proving whether IsLiveIn(n, a) = ∃u ∈ uses(a)|M r (n) ∩ [u, def (a)) = φ. We will assume absence of any un-initialized variables. Also we will use the terms root and EN T RY interchangeably. → u such that w dom u. This implies w ∈ M (n). Hence w ∈ M r (n). w is assumed to be distinct from u.

For the lemmas that follow, if multiple nodes m 1 , . . . , m k dominate u, then we will use that node m such that ∀m i , level(m) > level(m i ). Thus, ∀m i , m i dom m and assume m to be distinct from u. But we know that m ∈ M r (n). This means that, there must exist another path from the start node EN T RY to m that bypasses n, otherwise m would not have been in the merge set of n. This implies the existence of a path of the form EN T RY

+ → m + → u.
In such a case, def (a) can no longer dominate u, as we can reach u without passing through def (a). This is a contradiction as we assumed def (a) to dominate uses(a). Hence, IsLiveIn(n, a) has to be true (by contradiction).

(⇒) : Assume now that IsLiveIn(n, a) is true. This implies that ∃u ∈ uses(a), such that the path n + → u does not have def (a) on that path. We will consider two cases:

Case 1: Assume that node n dominates u. This implies that n ∈ IDOM P (u). As n ∈ M r (n), hence, M r (n) ∩ IDOM P (u) = φ. As def (a) does not appear on at least one path n + → u by definition of IsLiveIn being true, def (a) cannot be dominated by n. On the other hand, if def (a) does not dominate n we can construct an alternate path EN T RY + → n + → u where def (a) does not appear. This will violate the assumption that def (a) dom u. So, def (a) dom n holds. def (a) can now be encountered only after n in the reverse walk of the dominator tree upward from u. This implies that n ∈ [u, def (a)). Hence, ∃u ∈ uses(a), where,

M r (n) ∩ [u, def (a)) = φ.
Case 2: Assume that node n does not dominate u. But def (a) ∈ IDOM P (u). Refer to possible scenarios as shown in Figure 2. In general, as Lemma 1 holds, ∃m ∈ M r (n) and m dom u. By virtue of node m being the first node in the reverse walk of the dominator tree from u, m cannot dominate def (a) as otherwise IsLiveIn will be f alse. This is because all paths from n + → u will be of the form n

+ → m + → def (a) + → u.
Since this is not allowed, def (a) must dominate m as def (a) dom u. Thus, def (a) appears in IDOM P (u) but only after m is encountered in a reverse walk of the dominator tree upward from u. Hence, ∃u ∈ uses(a), where, M r (n) ∩ [u, def (a)) = φ.

LEMMA 4.3. In an SSA-form program, for node n and variable a, IsLiveIn(n, a) is

f alse ⇐⇒ ∀u ∈ uses(a)|M r (n) ∩ [u, def (a)) = φ. PROOF. (⇐) : If ∀u ∈ uses(a)|M r (n) ∩ [u, def (a)) = φ,
it implies that def (a) appears before any of the nodes in M r (n) is encountered in a tree-path [u, root] from all u in uses(a). Going by Lemma 1, for each u ∈ uses(a), there is a node m ∈ M r (n) that dominates u. For this m, when m ∩ [u, def (a)) = φ, then m ∈ IDOM P (u) and m ∈ IDOM P (def (a)). This implies that both the conditions m dom u and m dom def (a) are valid. Hence, all paths from n to u ∈ uses(a) should be of the form n PROOF. Follows from Lemma 2 and Lemma 3.

+ → m + → def (a) + → u as m ∈ M (n)

EXPERIMENTS

Experimental Setup

Liveness checking of the SSA variables is especially useful for dismantling the SSA form, that is, converting back to a non-SSA program representation. This conversion is expensive when it includes coalescing of the copies inserted to replace the φ-functions, and such coalescing is required in order to obtain high-quality code. As observed by Sreedhar et al. [START_REF] Sreedhar | Translating Out of Static Single Assignment Form[END_REF], SSA based coalescing removes copies that cannot be removed by traditional coalescing such as Chaitin's algorithm. The need for fast and effective copy coalescing while dismantling the SSA form motivates work by [START_REF] Budimlic | Fast Copy Coalescing and Live-Range Identification[END_REF], and more recently, work by [START_REF] Boissinot | Revisiting Out-of-SSA Translation for Correctness, Code quality and Efficiency[END_REF]] that generalizes work by Sreedhar et al.

For our experiments, we adapted the Sreedhar et al. [START_REF] Sreedhar | Translating Out of Static Single Assignment Form[END_REF]] Method III algorithm, and also his SSA based coalescing algorithm, in order to use liveness checking of variables instead of the classic live-in and live-out sets. We selected the methods of Sreedhar as they are currently the most advanced for copy coalescing and dismantling the SSA form that are also correct, tolerant to non-split critical edges, and described with enough details to be implemented faithfully. The main changes to the Sreedhar Method III for using liveness checking are in the interference breaking phase (step 4) and the actual copy insertion phase (step 6). As in other SSA form dismantling and coalescing techniques [START_REF] Budimlic | Fast Copy Coalescing and Live-Range Identification[END_REF], it is only necessary to consider the variables that are operands of the φ-functions or operands of the copy operations.

Besides our liveness checking technique and the modifications to the Sreedhar methods, we implemented the Boissinot et al. [START_REF] Boissinot | Fast Liveness Checking for SSA-Form Programs[END_REF]] method, using the same basic data-structures (dominance tree, bitsets, memory allocators, etc.) as in the implementations of our algorithms. So we provide an unbiased comparison with this technique. As our implementation choice, we represented as bitsets all the sets that contain control-flow nodes, including the dominance frontiers, the merge sets and M s sets, and the Boissinot T q (which consists of all back-edge targets relevant for a liveness query at node q) and R v (which consists of the set of nodes that are reachable from node v for a back-edge free directed graph) sets.

All these implementations were conducted in the STMicroelectronics production compiler for ST200 VLIW family, which is based on the GCC front-ends, the Open64 optimizers, and the LAO code generator [START_REF] Dupont De Dinechin | Code Generator Optimizations for the ST120 DSP-MCU Core[END_REF]]. Execution times are provided in milliseconds.

Compilation Times

We measure compilation time for the following compilation steps: For each series of measures, we compute two ratios:

RatioA (RatA) is (Setup0 + LiveIn0 + LiveOut0) divided by (MergeSets + Setup1 + LiveIn1 + LiveOut1). This gives the speedup of our method in a pessimistic setting, as we include the cost of computing the merge sets. RatioB (RatB) is (Setup0 + LiveIn0 + LiveOut0) divided by (Setup1 + LiveIn1 + LiveOut1). This gives the speedup of our method in a realistic setting, since the cost of computing the merge sets disappears if merge sets are already computed. The results for several benchmarks are displayed in Table I. The upper part of the table contains codes from the compiler regression base. The lower part of the table are Mediabench [START_REF] Lee | Mediabench: A Tool for Evaluating and Synthesizing Multimedia and Communicatons Systems[END_REF]] benchmarks. Our algorithm fares better on an average when compared to the algorithm presented by Boissinot et al. due to much lesser precomputation time. The query times are comparable for both the methods. For some benchmarks the query times for Boissinot are faster than our method -mostly for livein queries. Our method is almost always faster on live-out queries. For the benchmarks evaluated, we are faster by about 1.3x even when the merge set computation time is taken into account (RatioA). Without the merge set computation time, our algorithm performs around 1.5x-2x times faster (RatioB).

It may be noted that due to the low number of functions(variables) in some of the benchmarks, the compile times are low when compared to bigger ones like mipmap, osdemo and texgen. The compilation times reported by Boissinot et al. is also of the order of microseconds to milliseconds.

Though we have not measured it explicitly, we speculate that the compilation time spent in liveness computation in SSA form programs may not exceed 5-10% of the total compilation time of the program [Puzović 2007]. It may be higher in programs where high optimization levels and very aggressive inlining are employed that may create very large functions. Similarly, the memory requirement of the SSA-based liveness computation may not exceed 5-10% of the total memory requirement of the entire compilation.

Benchmark Parameters

Using instrumentation inserted in the compiler, we measured various parameters for each benchmark considered in the previous section:

#F

The cumulative number of functions contained in the benchmark. #V

The As a general comment, the method of Boissinot et al. computes three auxiliary sets of control-flow nodes per basic block, whereas our method computes only the M s sets beyond the merge sets. The M r (n) sets in our method need not be explicitly computed, as testing membership of t is same as t == n or t ∈ M (n). We can observe from Table II that the average storage requirement in our algorithm is considerably lesser -of the order of 15x.

RELATED WORK

Liveness analysis is a classical backward data-flow based analysis technique [START_REF] Cooper | Efficiently computing Static Single Assignment Form and the Control Dependence Graph[END_REF][START_REF] Morgan | Building an Optimizing Compiler[END_REF]]. One of the first attempts at solving the liveness problem using SSA is by Choi et al [START_REF] Choi | Automatic Construction of Sparse Data Flow Evaluation Graphs[END_REF]. They use Sparse Data Flow Evaluation Graphs (SEG) to solve the liveness problem by first noting that φ-functions obscure liveness properties of variables and then using SEGs to compute liveness. The idea behind sparse evaluation graphs is to construct a smaller graph from the original graph G, from whose solution the solution of the original graph can be recovered [START_REF] Ramalingam | On Sparse Evaluation Representations[END_REF]. [START_REF] Gerlek | A Reference Chain Approach for Live Variables[END_REF]] chain the φ-functions and create a graph representation from which strongly connected components are extracted to get the liveness information.

In a recent work Boissinot et al. derive an efficient mechanism to compute liveness information for variables. In this work they extract liveness information for SSA-form programs. They employ precomputation and dominator tree in their work in order to speed up liveness queries. However, in this algorithm the handling of CFGs with irreducible loops is not straightforward. And the space requirement of this algorithm is high which subsequently reduce the scalabilty of the algorithm. Our work is very closely related to this work. We also compute liveness information for SSA-form programs. However, we use merge sets which allow us to handle CFG with irreducible loops using a single unified algorithm. It also allows our algorithm to be scalable, simple to understand and implement. This is also the first instance of the application of merge sets for liveness computation.

CONCLUSION AND FUTURE WORK

In this paper we have presented a novel approach to liveness analysis for SSA-form programs using merge sets. This is the first application of merge sets for liveness analysis. Merge sets have been used earlier for computing the φ-functions of programs as part of the SSA transformation. The advantages of our method compared to previous approaches lie in using the merge sets to handle CFGs consisting of reducible or irreducible loops in a unified and consistent manner. This makes our approach much cleaner and simpler. In addition, storage of merge sets in CFGs take up much lesser space compared to existing methods.

One of the future works is to study whether such merge-set based techniques can be adaped for computing liveness for programs not in SSA form. Also, in the liveness queries, time is spent to account for the fact that φ-function arguments are in fact used at the end of the corresponding predecessor basic blocks, instead of the beginning of the basic block where the φ-function textually appears. This is a classic rule for the liveness of φ-function arguments. Future work will also aim at reducing this overhead if possible. In addition, we may need to evaluate the compile-time and memory overheads of the SSA-based liveness computation phase when compared to the entire compilation flow.

  3 Consider two nodes u and v and distinct paths from u + → w and v + → w, where w is some node in the CFG (x + → y denotes a non-empty path). If the two paths

Fig. 1 .

 1 Fig.1. An example (a) CFG and its corresponding (b) DJgraph and Merge Sets meet only at w then w is in the join set of the nodes {u, v}. For instance, consider nodes 1 and 9 in Figure1(a). The paths 1 → 2 → 3 → 8 and 9 → 10 → 8 meet at 8 for the first time and so {8} ∈ J({1, 9}).The merge relation is defined as a relation v = M (u) that holds between two nodes u and v whenever v ∈ J({root, u})[START_REF] Bilardi | Algorithms for Computing the Static Single Assignment Form[END_REF]]. We insert a φ-function at v for a variable that is assigned at u. For any node u ∈ V , v ∈ M (u) if and only if there is a path u

Fig. 2 .

 2 Fig. 2. The intuition behind using Merge Sets for Liveness

  (a), for paths without loops, since n does not dominate u, there are paths n + → m and p + → m where p = m. Also m dom u holds as given in the figure. Thus, m becomes a merge point for n and m ∈ M (n). According to IsLiveIn, a is live-in at n because the path n + → m + → u via which u is reachable from n does not have a define of variable a. Thus, m ∈ M (n) and m dom u hold true when IsLiveIn(n, a) is true. For the case in Figure 2(b), which involves a back-edge, there are paths, n Also m dom u holds according to the figure and m ∈ M (n). According to ALGORITHM 1: Algorithm for IsLiveInU singM ergeSet Input: Node n, Variable a. Output: bool. 1 M r (n) = M (n) ∪ {n}; // Create a new set from the merge set 2 // Iterate over all the uses of a 3 for t ∈ uses(a) -parent(t); // Climb up from node t in the DJ-Graph 9 // dom-parent returns the parent node in DT

Fig. 3 .

 3 Fig. 3. Working of IsLiveInU singM ergeSet

  (a)| avg * h DomT ree avg ). Boissinot et al. show that for a large suite of benchmarks |uses(a)| avg is usually a small constant. Hence the complexity of IsLiveInU singM ergeSet query is O(h DomT ree avg ) for all practical purposes. IsLiveOutU singM ergeSet has an added complexity in computing M s sets whose complexity is O(|V succAvg |), where |V succAvg | is the average number of successor nodes of a node. Thus, the total complexity is O(|V succAvg | + (|uses(a)| avg * h DomT ree avg )) where the second part of the complexity expression is due to Line 5-11 of Algorithm 4. The entire expression simplifies to O(|V succAvg | + h DomT ree avg

  LEMMA 4.1. In a CFG, for nodes n and u, if there is a path n+ → u then ∃m ∈ M r (n) such that m dom u.PROOF. If all paths from root + → u is of the form root + → n + → u then n dom u holds. Also, by definition, n ∈ M r (n). Else, if n does not dominate u there are paths root +

LEMMA 4. 2 .

 2 In an SSA-form program, for node n and variable a, IsLiveIn(n, a) returns true ⇐⇒ ∃u ∈ uses(a)|M r (n) ∩ [u, def (a)) = φ PROOF. (⇐) : Assume for some m ∈ M r (n) there ∃u ∈ uses(a) such that m ∩ [u, def (a)) = φ. Hence m dominates u and def (a) dominates m. This is due to two reasons. Firstly, all uses(a) should be dominated by def (a). Secondly, def (a) should dominate m otherwise in the IDOM P (u) tree-path def (a) will appear prior to m. Now if we assume that IsLiveIn(n, a) is f alse, then, def (a) should appear in each and every path from n to u, denoted as n + → u. Hence any such path should follow the pattern n + → def (a) + → u (assume n, def (a) and u are distinct). Also, since def (a) dominates m and m dominates u, the path should follow the pattern, m and def (a) are distinct).

  by definition of a merge set. This means that IsLiveIn(n, a) returns f alse as all paths from n to u contain def (a). (⇒) : As IsLiveIn(n, a) returns f alse, for every path n + → u, where u ∈ uses(a), the node def (a) appears in the path i.e. n + → def (a) + → u holds. As m ∈ M r (n), there are paths EN T RY + → m and n + → m which join at m by definition of merge. Now if the path m + → u does not have def (a), then the path n + → m + → u can be constructed that does not have def (a) leading to IsLiveIn(n, a) being true. This is a contradiction. So m + → u must contain def (a) (n + → m cannot contain def (a) else def (a) will not dominate u). This leads to all paths from m to u taking the form m + → def (a) + → u. As m dom u holds, m ∈ IDOM P (u), then, m ∈ IDOM P (def (a)) also. This results in [u, def (a)) = φ. So, M r (n) ∩ [u, def (a)) = φ for all u ∈ uses(a).LEMMA 4.4. IsLiveIn(n, a) = ∃u ∈ uses(a)|M r (n) ∩ [u, def (a)) = φ.

  MergeSets (MSets) Construction of the Merge Sets using the TDMSC-II algorithm of Das et al. [Das and Ramakrishna 2005], assuming the dominators are already computed. Setup0 (St0) The setup time of the Boissinot et al. liveness check computation, which includes computation of the T q and R v sets. LiveIn0 (LIn0) The total time spent in live-in checking of Boissinot et al. LiveOut0 (LOut0) The total time spent in live-out checking of Boissinot et al. Setup1 (St1) The setup time of our liveness check computation, which includes computation of the M s sets. LiveIn1 (LIn1) The total time spent in our live-in checking. LiveOut1 (LOut1) The total time spent in our live-out checking including computation of M s sets.

Table I .

 I Performance Data for Merge Set based Liveness Computation

	Benchmark	MSets	St0	LIn0	LOut0	St1	LIn1	LOut1	RatA	RatB
	autcorr.240	0.044	0.171	0.003	0.162	0.054	0.002	0.083	1.83	2.41
	bassmgt	0.111	0.430	0.020	0.765	0.141	0.028	0.641	1.32	1.50
	compress.2	0.349	1.008	0.124	0.121	0.326	0.092	0.076	1.49	2.54
	c-lex	4.674	15.456	0.514	2.480	5.820	0.592	3.266	1.29	1.91
	dbuffer	1.697	5.550	0.554	1.933	1.842	0.455	1.459	1.47	2.14
	fft32x32s	0.060	0.186	0.090	0.137	0.060	0.094	0.127	1.22	1.48
	transfo	0.104	0.401	0.010	0.143	0.136	0.024	0.116	1.45	2.00
	TOTAL	7.039	23.202	1.315	5.741	8.379	1.287	5.768	1.35	1.96
	g721dec	0.441	1.412	0.008	0.259	0.461	0.011	0.173	1.55	2.60
	g721enc	0.431	1.337	0.008	0.259	0.437	0.011	0.173	1.53	2.58
	gsm	1.887	7.184	6.730	8.016	2.363	5.816	5.170	1.44	1.64
	mipmap	72.569	292.075	9.777	640.193	105.433 14.151	523.023	1.32	1.47
	osdemo	73.747	297.928 10.756	643.717	107.519 15.239	526.036	1.32	1.47
	pegwit	2.272	9.680	1.039	5.306	3.160	0.861	3.603	1.62	2.10
	rasta	5.244	24.183	0.528	42.224	8.383	0.480	35.258	1.36	1.52
	texgen	72.808	293.244	9.790	642.496	105.828 14.163	524.562	1.32	1.47
	TOTAL	229.399	927.043 38.636 1982.470	333.584 50.732 1617.998	1.32	1.47

  The total number of elements in the M s sets. HqSizes (HqSz) The total number of elements in the T ↑ t sets of Boissinot et al. liveness checking. This set is a subset of T q with some additional properties of reachability. TqSizes (TqSz) The total number of elements in the T q sets of Boissinot et al. liveness checking. RvSizes (RvSz) The total number of elements in the R v sets of Boissinot et al. liveness checking.

		cumulative number of SSA variables considered by the Sreedhar III
		algorithms.
	#B	The cumulative number of basic blocks seen by the Sreedhar III algo-
		rithms.
	MergeSizes (MgSz) The total number of elements in the merge sets.
	MsaSizes	(MsaSz)

Ratio is (HqSizes + TqSizes + RvSizes) divided by MsaSizes.

Table II .

 II Parameters and sizes of various sets used in our experiments

	Benchmark	#F	#V	#B	MgSz	MsaSz	HqSz	TqSz	RvSz	Ratio
	autcorr.240	1	82	28	56	84	18	46	392	5.43
	bassmgt	1	127	63	199	262	42	105	1966	8.06
	compress.2	7	231	160	319	485	67	242	1710	4.16
	c-lex	7	710	984	2416	3450	272	1257	82604	24.39
	dbuffer	14	1144	744	1603	2363	238	983	16740	7.60
	fft32x32s	1	100	30	68	98	14	44	418	4.86
	transfo	3	125	64	80	144	18	82	596	4.83
	TOTAL	34	2519	2073	4741	6886	669	2759	104426	15.66
	g721dec	17	1344	221	306	542	68	289	3587	7.28
	g721enc	13	1148	209	309	528	62	271	3658	7.56
	gsm	57	7961	1143	1369	2564	284	1428	22337	9.38
	mipmap	638 247728	27547	40598	70903	9765	37313 1062017	15.64
	osdemo	650 253690	28170	41652	72605	10419	38590 1087342	15.65
	pegwit	90	11392	1596	1921	3575	489	2086	22684	7.07
	rasta	64	25373	2980	9327	12579	3033	6014	118711	10.16
	texgen	654 249686	27745	40780	71299	9863	37609 1063953	15.59
	TOTAL	2183 798322	89611	136262 234595	33983 123600 3384289	15.10

ACM Transactions on Architecture and Code Optimization, Vol. V, No. N, Article A, Publication date: January YYYY.

In subsequent diagrams we will omit EN T RY and EXIT nodes for simplicity.

In subsequent diagrams we will omit the root node for simplicity.ACM Transactions on Architecture and Code Optimization, Vol. V, No. N, Article A, Publication date: January YYYY.

In English 'join' and 'merge' are synonyms, and in the literature, these two synonyms are used to mean distinct but very-similar and related concepts.ACM Transactions on Architecture and Code Optimization, Vol. V, No. N, Article A, Publication date: January YYYY.

ACKNOWLEDGMENTS

The authors would like to thank Albert Cohen of INRIA and Vugranam Sreedhar of IBM Research for various kinds of support and the anonymous referees for useful suggestions that improved the quality of the work.

Algorithm IsLiveOutU singM ergeSet

In this section we outline how the liveout sets can be computed for variables without computing the live-in sets for all the successor nodes of a basic block where live-out sets are being computed. First, we need to compute the M s sets using the merge sets of the successor nodes of node n. This is shown in Line 4-8 of Algorithm 2. The algorithm then proceeds to use the same logic as IsLiveInU singM ergeSet i.e. traversing up the dominator tree from the uses(a) set, the only difference being the use of M s set instead of M r (n). The details are provided in Algorithm 2. The special case of live-out being computed for the def (a) node can be found in Lines 1-3.

IsLiveOutU singM ergeSet may be invoked for the same node multiple times. Hence, we can optimize Algorithm 2 further by carrying out an initial top-down pass over the DJ-graph to pre-compute the M s sets as shown in Algorithm 4. This is done using a separate function called ComputeSuccM ergeSetsInDJGraph shown in Algorithm 3. The M s sets can now be used without the need of computing them during each invocation of IsLiveOutU singM ergeSet.

Average Case Complexity of the Liveness Algorithms

The complexity of computing the merge sets is linear on an average as shown in [START_REF] Das | A Practical and Fast Iterative Algorithm for φ-function Computation Using DJ-Graphs[END_REF]. The complexity of IsLiveInU singM ergeSet is controlled by the outer loop of Line 3 in Algorithm 1, which depends on the size of the use sets of variables. Let |uses(a)| denote the size of the use set for variable a, and |uses(a)| avg is the average number of nodes that need to be traversed in Line 3 of the for loop.


A Falchi

Clement Turbelin

Laurent Andreoletti

Christophe Arena

Thierry Blanchon

Isabelle Bonmarin

Thomas Hanslik

Marianne Leruez

Xavier De Lamballerie

Nationwide surveillance of 18 respiratory viruses in patients with influenza like illnesses: a pilot feasibility study in the French Sentinel Network

Keywords: respiratory viruses respiratory viruses, influenza-like illness, surveillance system, general practitioners 68

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Alessandra Falchi, 1,2* Clément Turbelin, 1,2 Laurent Andreoletti, 3,4 Christophe Arena, 1,2 Thierry 7 Blanchon, 1,2 Isabelle Bonmarin, 5 Thomas Hanslik, 1,6,7 Marianne Leruez-Ville, 8 Xavier De 8 Lamballerie, 9,10 Fabrice Carrat The spread of the new variant A/(H1N1) 2009 influenza virus in the Northern hemisphere at 73 an earlier time than usual for seasonal influenza in previous years has highlighted the limited 74 knowledge concerning the aetiology of acute respiratory illnesses outside of influenza outbreaks. 75

In early September 2009, while reports of influenza-like illness were increasing in medical practice-76 based surveillance in France and other European countries, the detection of pandemic influenza 77 virus remained sporadic [START_REF] Linde | Does viral 341 interference affect spread of influenza?[END_REF]. This finding was attributed to the circulation of other 78 respiratory viruses and, to a lesser extent, may have been associated with the increased propensity 79 of patients with influenza-like illness to seek medical advice due to increased anxiety in the 80 pandemic context. 81 This finding was also observed for influenza-like illness incidence rates reported by the 82 French Sentinel Network [START_REF] Turbelin | Early 361 estimates of 2009 pandemic influenza A(H1N1) virus activity in general practice in France: 362 incidence of influenza-like illness and age distribution of reported cases[END_REF]. The Sentinel network is a continuous 83 epidemiological surveillance system based on General Practitioners (GPs) and has been operating 84 since 1984 in France. It consists of a sample of 1,319 GPs throughout France, of which 200 to 400 85 participate each week in continuous surveillance [START_REF] Valleron | A computer 364 network for the surveillance of communicable diseases: the French experiment[END_REF]. The GPs participating in 86 the Sentinel Network are representative of the whole French GP population as regards to age, 87 location, type (rural/urban) and kind of practice (alone/pluridisciplinary) [START_REF] Chauvin | Attitude of French general practitioners to the public health 314 surveillance of communicable diseases[END_REF]. 88

The main objective of the French Sentinel Network is to provide the national health 89 authorities with near to real-time information on several health-related events occurring in the 90 community, including influenza-like illness (for the full list of events, see http://www.sentiweb.fr). 91

These events are reported by Sentinel GPs through a dedicated website, aggregated at different 92 spatial and temporal levels and used to inform health authorities. In the Sentinel network, influenza-93 like illness cases are defined on the basis of clinical signs, but no virological collection is carried 94 out routinely. 95

Given the need for improving virological surveillance after the first A/(H1N1)2009 96 6 an e-mail survey in GPs who did not include any patients to describe the reasons for the lack of 147 sample collection was performed, and another survey was performed to evaluate the GPs' 148 satisfaction with the pilot study in those who included patients. 149

Statistical Analysis 150

Patients with at least one virus detected (positive patients) were compared to patients 151 with no virus detected (negative patients). Factors and signs associated with positivity for the 152 viruses that were most frequently isolated or with co-infections were studied. The Fisher exact test 153 was used to compare independent categorical variables and the Mann-Whitney test was used to 154 compare continuous variables. A logistic regression model was used for binomial outcomes, and 155 odds ratios (OR) and their 95% confidence intervals were estimated. 156

157

RESULTS

158

Number of samples collected by GPs 159

Sixty-three (42%) GPs collected 103 nasopharyngeal samples. Based on clinical data 160 reported by the GPs, all samples were collected in patients with influenza-like illness as defined by 161 the surveillance network. The maximum number of samples collected was during week 04 (from 162 January, 25 to January 29, 2010) (n=36). Thirty-nine (62%) GPs provided one sample, eleven 163 (17%) provided two samples, ten (16%) GPs provided three samples and three (11%) GPs provided 164 four samples. 165

Comparison of GPs who collected samples and GPs who did not 166

GPs who collected samples (n=63) did not differ from those who did not (n=87) with respect 167 to their age (51.8±7.4 years vs. 51.7±8.8 years; P=0.93), gender (male) (78% vs. 80%; P=0. Thirty-four (82.5%) GPs were satisfied with the feedback on the results. 175

Survey in GPs who did not collect samples 176

Eighty-seven GPs did not collect nasopharyngeal samples. Four items have been proposed 177 to explain the reasons for not participating (lack of any influenza-like illness cases during the study 178 period; lack of time; the study was too complex; declined to participate). Ninety-five percent 179 (83/87) of GPs declared that they did not collect any samples because of the lack of any influenza-180 like illness case during the study period, but they reported themselves to be very interested in 181 participating in the study. Four GPs did not participate because of a lack of time and they declined 182 to participate in the following phase of the study. 183

Characteristics of patients 184

The median age of the 103 patients with influenza-like illness patients was 18 years , 185 of whom 58 (56%) were males. These patients did not differ from cases of influenza-like illness 186 reported by the Sentinel network during the study period (n=380) as regards age (P=0.49) or 187 influenza vaccination status (P=0.46). However, the proportion of men was higher in this sample 188 (56%) than in cases of influenza-like illness reported in the network (45% men) (P=0.02). 189

Of note, 50% of the included patients were children under the age of 18 which, compared to 190 the proportion of children in the general French population (22%), indicated that children were 3.5 191 times more likely than adults to be included in the sample of patients with an influenza-like illness. 192

Virological findings 193

Seven samples were excluded since the virological results were not interpretable by the 194 FluaVir (n=4) microarray or the PneumoVir microarray (n=3) because of undetectable internal 195 controls. Among the remaining 96 influenza-like illness cases, 61 viruses were detected in 196 8 nasopharyngeal samples from 56 (58%) patients: RSV in 24 (25%), hMPV in 13 (13.5%), hCoV 197 229E in nine (9.4%), Influenza A/H1N1 2009 in five (5.2%), RV in three (3.1%), hBoV and AV in 198 two (2.1%) and Influenza B, Influenza A/H3N2 and PIV 2 in one (1.0%) (Table I). More than one 199 virus was detected in four patients (Table I). 200

The age distribution (0-5; 6-18; 19-25; 26-44; 45-87 years) differed significantly between 201 positive and negative patients, with positive patients being younger than negative patients 202 (OR=0.98, IC 0.95-0.99; P=0.0226). All patients aged 0-5 years (n=12) were positive for one or 203 more respiratory viruses, among whom eight had a positive diagnosis for RSVb infection (Fig. 1). 204

The most common clinical findings in patients infected with hMPV (n=13) and RSV (n=24) were 205 cough (n=11 and n=24), rhinorrea (n=11 and n=22), fatigue (n=11 and n=21) and myalgia (n=10 206 and n=16). Co-infected patients (Table I) had a median age of 15 years and did not differ clinically 207 from mono-infected patients. 208 209 DISCUSSION 210 Despite the small number of samples included, the present pilot study showed that it was 211 feasible to combine microarray detection of 18 respiratory virus infections with clinical surveillance 212 of influenza-like illness in order to provide a more complete understanding of the epidemiology of 213 these viruses in the community. 214

Combined community virological and clinical surveillance for influenza or RSV have been 215

implemented in several countries. Notably, in France, the Groupes Régionaux d'Observation de la 216 Grippe (GROGs) is an influenza-devoted surveillance system which has been operating for more 217 than 25 years in which GPs or paediatricians perform virological diagnosis of influenza in patients 218 with acute respiratory illness [START_REF] Quénel | Influenza A and B epidemic criteria based on time-series analysis of health 346 services surveillance data[END_REF] [START_REF] Townsend | Experimental evaluation of the FluChip diagnostic microarray 359 for influenza virus surveillance[END_REF], even if technical training is necessary to avoid false positive results 247 because of insufficient washing or overexposure of the arrays [START_REF] Frobert | Respiratory viruses in children admitted to hospital intensive care 331 units: evaluating the CLART® PneumoVir DNA array[END_REF]. Excluding 248 these samples, 58% were positive for at least one virus. This proportion of positive diagnosis is 249 comparable to findings from other studies using qRT-PCR or a combination of qRT-PCR and 250 classical cell culture techniques, in which 41-61.8% of the samples were positive [Follin et al., 251 2009;[START_REF] Heikkinen | Human metapneumoVirus 335 infections in children[END_REF][START_REF] Va | Influenza-like illness 339 sentinel surveillance in Peru[END_REF][START_REF] Nougairède | Novel virus influenza A (H1N1sw) in South-Eastern France[END_REF]. 252

It is noteworthy that the clinical criteria used for sample collection in those studies included 253 a broad spectrum of respiratory symptoms, while the criteria for influenza-like illness were rather 254 narrow/specific. Therefore, the number of positive specimens was not altered by the selection of 255 patients with a strict case definition. On the other hand, false-negative results may have occurred in 256 the adult population and could have been the consequence of insufficient quality of the sample 257 collected or of a lack of sensitivity of the laboratory techniques. Nevertheless, a recent study 258 validated the performance of the commercial kits used in the present study [START_REF] Renois | 355 Rapid detection of respiratory tract viral infections and co-infections in patients with ILI by use of 356 RT-PCR DNA microarray systems[END_REF]. 259

Negative results can also be due to other unknown or known respiratory pathogens (e.g. 260 Parechovirus, Polyomavirus KI and WU, Human coronavirus OC43, NL63 and KU1 or M. 261 pneumoniae and C. pneumoniae). This proportion of undiagnosed cases is in line with those found 262 in other surveys [START_REF] Hasman | Aetiology of 333 influenza-like illness in adults includes parainfluenzavirus type 4[END_REF][START_REF] Va | Influenza-like illness 339 sentinel surveillance in Peru[END_REF] and appeal for complementary 263 virological investigations using, for example, high throughput methods (e.g. pyrosequencing 264 methods [START_REF] Deyde | Pyrosequencing as a tool to detect molecular markers of resistance to neuraminidase 320 inhibitors in seasonal influenza A viruses[END_REF], mass spectrometry [START_REF] Chen | Rapid identification viruses from nasal pharyngeal aspirates in acute viral respiratory 317 infections by RT-PCR and electrospray ionization mass spectrometry[END_REF], high resolution melting 265 (HRM) techniques [START_REF] Varillas | A new method for detection of pandemic influenza virus using High Resolution 368 Melting analysis of the neuraminidase gene[END_REF] and Padlock Probes [START_REF] Wu | Emerging molecular assays for detection and characterization of respiratory 376 viruses[END_REF]). 266

In this investigation, it was found that age was associated with the chance of being positive, 267 with a rate of positivity of 100% in younger patients (0-5 years), in which RSV and hMPV were the 268 most frequently detected viruses. Similar findings were obtained in other settings and were 269 attributed to the developing immune status of young children and their vulnerability to infections 270 [START_REF] Raboni | Pandemic influenza A and 349 community respiratory viral infections in southern Brazil -laboratory diagnosis, epidemiology and 350 clinical outcome[END_REF]. 271

  which spanned fromSeptember 6, 2009 to December 26, 2009 in France, the 97 feasibility of integrating the diagnosis of respiratory viruses into clinical surveillance of influenza-98 like illness in the French Sentinel Network was tested. As a secondary objective, participated in the study. A subset of 150 volunteer GPs, 104 located in mainland France were recruited, on the basis of their participation in continuous 105 surveillance in the Sentinel Network. 106The 150 GPs were distributed over all the departments (administrative units) of France. The 107 GPs participating to the present study did not differ from other GPs of the Sentinel Network with 108 respect to age (51.7±8.1 years vs. 52.1±7.8 years; P=0.93), gender (male) (79% vs. 83%; P=0.60) 109 urban/rural distribution (urban 75% vs. 74%; rural 25% vs. 26%; P=0.68) and years of inscription 110 in the Sentinel Network (10.4±7.6 years vs. 11.1±7.7 years; P=0.27). 111The pilot study was carried out over five weeks between January 25, 2010 and February 27, 112 2010, after the end of the French A/(H1N1)2009 epidemic. The 150 enrolled volunteer GPs 113 received swabs and other study materials to include every first patient of the week having a medical 114 visit for influenza-like illness (Sentinel network case-definition: a sudden fever of 39ºC or above, 115 respiratory symptoms and myalgia), with the additional criteria of the time between symptom onset 116 and the visit of less than 48 hours. 117Sample and patient data collection 118Sample collection was performed with ∑-Virocult® swabs (ELItech, France). The 119 nasopharyngeal swabs were sent by mail in 2 ml of viral transport medium within two days to one 120 of the three virological laboratories participating in the study. Detailed demographic and clinical 121 of the onset of symptoms, reported symptoms, physical findings and influenza 122 vaccination status) were obtained from patients during the medical visit. 123Nucleic Acid Extraction and Microarray Detection 124Following RNA and DNA extraction from clinical specimens using either an automated 125 MagNA Pure LC with the Total Nucleic Acid High Performance kit (Roche Diagnostic, Meylan, 126France) or an EZ1 Biorobot with the virus mini kit (Qiagen, Courtaboeuf, France), all samples were 127 tested for the simultaneous detection of a panel of 18 respiratory viral pathogens using a PCR-DNA 128 microarray detection assay (CLART® PneumoVir and FluaVir Version 3.0, Genomica, Madrid, 129 Spain). The CLART® PneumoVir allows the detection of 17 respiratory viruses distinguishing 130 between the seasonal influenza A subtypes A/H1N1 and A/H3N2. The CLART® FluaVir kit was 131 able to type and to distinguish the influenza virus A/H1N12009 from the A/H1N1 and A/H3N2 132 subtypes of the seasonal influenza A virus. All respiratory samples were tested simultaneously using 133 these two kits. 134The combination of these two systems allows for the simultaneous detection of Adenovirus 135 (AV), Bocavirus (hBov), Coronavirus 229E (hCoV), Enterovirus (Echovirus) (EV), Influenza A 136 ((H1N1) 2009, H3N2, H1N1), Influenza B, Influenza C, MetaPneumoVirus (hMPVa and hMPVb), 137 Parainfluenza (PIV) (1, 2, 3 and 4), Respiratory Syncytial Virus (RSVa and RSVb) and Rhinovirus 138 (RV). The technique includes an internal control that tests the efficiency of the amplification 139 process and to detect the presence of inhibition products. The sensitivity and specificity of the 140 multiplex RT-PCR assay for the simultaneous detection of this panel of respiratory viral pathogens 141 have been previously reported.[START_REF] Renois | 355 Rapid detection of respiratory tract viral infections and co-infections in patients with ILI by use of 356 RT-PCR DNA microarray systems[END_REF]. 142 Surveillance virological results (number of samples, positive samples, type and subtype of 143 viruses isolated weekly) were available on the website the week following sample collection. Each 144 week, the GPs also received the virological results of her/his patients on a secure study website. The 145 interval between specimen collection and availability of the results for GPs was 10-14 days. Finally, 146

  68) and 168years of inscription in the Sentinel Network (10.8±7.2 years vs. 10.7±7.4 years; P=0.68). percent (40/63) of GPs responded to the satisfaction survey. Thirty-five out of 40 172 (87.5%) GPs were satisfied with the swab collection instructions and 38 (95%) found the dedicated 173 study website useful for following the development of the study and for consulting instructions. 174

Table I :

 I Viral aetiology of the ILI patients.

	Viral aetiology (co-infections included)	Number	% of patients
	Adenovirus	2	2.1
	Bocavirus	2	2.1
	Enterovirus	0	0
	Human Coronavirus type 229E	9	9.4
	Influenza virus type A subtype H1N1	0	0
	Influenza virus type A subtype H1N1 2009	5	5.2
	Influenza virus type A subtype H3N2	1	1
	Influenza virus type B	1	1
	Influenza virus type C	0	0
	Metapneumovirus type A Metapneumovirus type B Parainfluenza virus type 1 Parainfluenza virus type 2 Parainfluenza virus type 3 Parainfluenza virus type 4 F o r	11 2 0 1 0 0	13.5 1
	Respiratory Syncytial Virus type A Respiratory Syncytial Virus type B Rhinovirus P Total number of detected virus e	10 14 3 61	25 3.1
	Details of detected Co-infections Metapneumovirus A + Respiratory Syncytial Virus A+Respiratory Syncytial Virus B e r	1	1
	Influenza B + Metapneumovirus A Adenovirus + Human Coronavirus 229E Bocavirus + Respiratory Syncytial Virus A R Number of positive patients e 1 1 1 56 Total patients 96 v i e 58.3 % 1 1 1
		w
	1

Nationwide surveillance of 18 respiratory viruses in patients with influenza-like illnesses: a 1 pilot feasibility study in the French Sentinel Network

	2
	3
	4
	5	Running title: Nationwide Surveillance of 18 Respiratory Viruses
	6

  Hôpitaux de Paris, Hôpital Saint Antoine, Unité de Santé Publique, F-75012 Paris, France.

	72	INTRODUCTION
	9	1,2,11
	10 11 12 13 14 15 16 17 18 19 20 11.Assistance Publique-21 1.INSERM, UMR-S 707, F-75012, Paris, France; 2.UPMC Université Paris 06, UMR-S U707, F-75012, Paris, France; 3.Unité de Virologie Médicale et Moléculaire, Centre Hospitalier Universitaire, Reims, France; 4.IFR 53/EA-4303 (DAT/PPCIDH), Faculté de Médecine, Reims, France; 5.Institut de Veille Sanitaire, St Maurice, Paris, France; 6.Université Versailles Saint Quentin en Yvelines, F-78000, Versailles, France; 7.Assistance Publique Hôpitaux de Paris, Service de Médecine Interne, Hôpital Ambroise Paré, F-92100, Boulogne Billancourt, France ; 8.Unité de Virologie, Hôpital Necker-Enfants Malades, Université Paris Descartes, EA 36-20, Paris, France; 9.Université de la Méditerranée, Unité des Virus Emergents UMR190, Marseille, France; 10.Institut de Recherche pour le Développement, Marseille, France; 22
	23
	24
	25
	26	Correspondence: Alessandra Falchi, réseau Sentinelles, UMR-S 707, Laboratory of Virology,
	27	University of Corsica, 20250 Corte, France
	28	Tel: + 33 0 495 45 06 77
	29	Fax: + 33 1 44 73 84 54
	30	E-mail: falchi@u707.jussieu.fr (A. Falchi)
	31
	32
	33
	34
	35
	36
	37
	38
	39
	40
	41
	42
	43
	44
	45

  . Similar networks have been launched in other 219European countries, e.g. the UK, Switzerland, Italy and Spain (www.ecdc.europe.eu). But, to our 220 knowledge, no surveillance system combines the simultaneous diagnosis of a large number of 221

	[
	F o r F o r
	P P
	e e
	e r e r
	R R
	e e
	v i e v i e
	w w
	10

Journal of Medical Virology


G Strömqvist

V Pasiskevicius

C Canalias

C Montes

Coherent Phase Modulation Transfer in Counter-Propagating Parametric Down-Conversion

Keywords: numbers: 42.65.Lm, 42.65.Yj, 78.67.Pt, 42.70.Mp

Distributed positive feedback established by a counter-propagating three-wave mixing process in a sub-micrometer structured second-order nonlinear medium leads to mirrorless parametric oscillation with unusual spectral properties. In this work, we demonstrate experimentally and theoretically that the phase modulation of the pump is coherently transferred to the co-propagating parametric wave, while the counter-propagating wave retains a narrow bandwidth and high coherence.

The main mechanisms responsible for these properties are the maximized convective separation between the counter-propagating waves, as well as the associated phase-locking between the pump and the co-propagating parametric wave. This suggests that mirrorless optical parametric oscillators can be pumped with incoherent light and still generate highly coherent backward-propagating radiation.

1

The lowest-order nonlinear interactions, collectively called three-wave mixing (TWM), are important in many different physical contexts, e.g. interactions in plasma [1,2], hydrodynamics and internal gravity waves [3], planetary Rossby waves which are related to the global climate [4], interactions of bulk and surface acoustic waves [START_REF] Shiren | Proc. IEEE[END_REF][START_REF] Svaasand | [END_REF], matter waves [START_REF] Ling | Coherence and quantum optics VIII[END_REF] and, indeed, in nonlinear optics [START_REF] Armstrong | [END_REF]. Optical parametric amplification (OPA) of lower frequency waves in a TWM process where photons ω p of the wave of the highest frequency, the pump, are split into two photons of lower energy, the signal ω s and the idler ω i , such that the energy conservation, ω p = ω s + ω i , and the momentum conservation, k p = k s + k i , conditions are satisfied, has large practical importance for the generation of high-energy ultrashort pulses in attosecond systems [9], as well as in quantum optics experiments for entangled photon-pair generation [10] and generation of squeezed vacuum states [11].

The coherence properties of the waves generated in the TWM down-conversion process have been subject of investigation from the very beginning of nonlinear optics [12,[START_REF] Glauber | Quantum theory of optical coherence[END_REF]. For instance, from simple quantum optical considerations it was shown [12] that OPA behaves like a perfect phase-sensitive amplifier, where the output photon number and phase variances of the amplified signal wave faithfully represent the input variances within the uncertainty principle. It is a general property of TWM that the total interaction phase is fixed. In the case of a down-conversion process, the phases φ j (where j = p, s, i) satisfy the relation:

φ p -φ s -φ i = π/2.
(

) 1
This feature has been utilized in passive all-optical carrier-envelope phase stabilization schemes [START_REF] Baltuska | [END_REF]. In an optical parametric generation (OPG) process, which, by definition, is seeded by zero-point fluctuations and thermal background radiation, the phases of the individual signal or idler waves remain to a large extent random, although the pairwise correlation between the signal and idler waves does exist [15]. As a consequence, the signal and the idler waves generated in background-noise seeded singly-resonant optical parametric oscillators (OPOs) can, in general, be considered incoherent and their spectral widths are much larger than that of the pump wave, unless phase-sensitive filtering is artificially imposed [16]. The spectral width of the parametric gain is determined primarily by the dispersion of the nonlinear medium and it is maximized when the group velocity dispersion is zero, ∂ 2 k ∂ω 2 = 0, at the degeneracy point (ω s ω i ). Away from degeneracy, the convection operators in the coupled wave equations, v g,j • ∇, where v g,j are the respective group velocities, determine the spectral widths of the signal and the idler waves. Several scenarios leading to increased coherence of the generated parametric waves by exploiting convective wave separation have been theoretically investigated [17,18].

In this work, we demonstrate experimentally and numerically that in a mirrorless optical parametric oscillator (MOPO), the device which relies on counter-propagating TWM for establishing a distributed positive feedback for sustained oscillation above threshold [19],

the convective wave separation is maximized and responsible for the unusual spectral and coherence properties of the generated signal and idler waves. Specifically, this physical mechanism ensures that the frequency bandwidth of the backward-propagating idler will be narrow compared to that of the signal when a broadband pump is used. Moreover, as a consequence of the phase relation in Eq. ( 1), the phase modulation of the pump is then effectively transferred to the co-propagating parametric wave.

Proposed in 1966 [20], the first experimental demonstration of a MOPO was reported in 2007 [21]. The major difficulty in achieving mirrorless parametric oscillation is associated with satisfying the momentum conservation condition, which in scalar form reads k p = k s -k i .

In homogeneous dielectrics, the phase matching condition can possibly be satisfied only for large signal-idler detunings, with the signal frequency close to that of the pump and the idler frequency in the THz region. However, due to the very different diffraction properties of the near-infrared signal and the far-infrared idler, achieving oscillation in homogeneous dielectrics is problematic. By employing ferroelectric nonlinear crystals structured with sub-micrometer periodicity, Λ, quasi-phase matching (QPM) [START_REF] Armstrong | [END_REF]

∆k = k p -k s + k i = 2π/Λ, (2)
can be utilized to achieve MOPO with counter-propagating idler k i in the mid-infrared spectral range. In the experimental investigation of the spectral properties of a MOPO, we here employ a 6.5 mm-long periodically-poled KTiOPO 4 (PPKTP) crystal with a QPM period of Λ = 800 nm to convert the pump around 813.5 nm into a co-propagating signal at 1123.0 nm and a counter-propagating idler at 2952.2 nm. The crystal fabrication details have been reported elsewhere [21,22].

From the momentum conservation condition in the TWM with counter-propagating idler (Eq. 2), one can derive and estimate the frequency variation in the counter-propagating wave, ∆ω i , as function the frequency variation in the pump, ∆ω p :

∆ω i = ∆ω p v g,i (v g,p -v g,s ) v g,p (v g,i + v g,s ) . (3)
The sum of the group velocities in the denominator of Eq. 3, which is the result of the counter-propagating geometry, ensures that the frequency of the back-propagating wave is not sensitive to changes in the pump frequency. This also means that the bandwidth of the counter-propagating wave is much smaller than that of the pump and it should reach minimum in a special case when the group velocities of the pump and the co-propagating signal wave are equal. In this limit when ∆ω i /∆ω p → 0, the temporal phase of the counterpropagating idler wave is φ i const. Then from Eq. 1, it follows that the partial derivatives of the co-propagating signal and pump phases with respect to time are approximately equal,

∂ t φ s (t) ∂ t φ p (t)
. These are indeed very unusual properties for parametric oscillation. In a process which is seeded by random noise, the interaction establishes a counter-propagating wave with a coherence time much longer than both the seeding noise and the coherence time of the pump. At the same time, the phase of this counter-propagating wave acts as a stable phase reference, thereby forcing the phases of the pump and the co-propagating signal wave to lock and vary in synchronism. It should be stressed that Eq. 3 is only an estimate, because the actual spectra of the generated waves also depend on the details of the TWM dynamics. A numerical solution of the coupled wave equations will show that the above reasoning regarding the phases of the waves is qualitatively correct.

For the experimental verification of the convective phase locking in MOPOs, the abovementioned PPKTP crystal was pumped with pulses centered at 814. linear chirp provides a direct frequency-to-time mapping, implying that the spectral measurements also contain temporal information about the MOPO dynamics. By comparing the spectra in Fig. 1(a), we can see that, at this pump intensity, the MOPO starts oscillating after a delay of about 260 ps, corresponding to the difference in time between the beginning of the pulse (816.1 nm) and where the pump starts being depleted (814.7 nm). After the start of the MOPO oscillation, the pump is rapidly depleted and the depletion level of about 60% remains approximately constant until the end of the pump pulse. This shows that the counter-propagating TWM process indeed is very efficient. The measured spectrum of the MOPO signal had a central wavelength of 1123.0 nm and a FWMH spectral width of 410

GHz, as illustrated in Fig. 1(b). Cross-correlation measurements revealed that the pulse had a FWHM length of 160 ps, containing a positive linear frequency chirp of 16.0 mrad/ps 2 .

This value is close to the chirp of the pump, as expected if the picture of convective phaselocking and phase modulation transfer between pump and signal is correct. The measured idler spectrum (spectrometer Jobin Yvon iHR550, 0.55 nm resolution) shown in Fig. 1(c) reveals that the FWHM bandwidth is 23 GHz. Taking into account that the resolution of the spectrometer is limited to 19 GHz at 2.952 µm and assuming a Gaussian spectral shape, the deconvoluted idler frequency bandwidth is then about 13 GHz. Within the resolution of our measurements, the idler bandwidth did not depend on the amount or sign of chirp imposed on the pump wave. This was checked by passing the pump pulse through a delay line with anomalous group-delay dispersion so that the pump pulse with the same spectrum as in Fig. 1(a) had an opposite frequency chirp and a different pulse length.

As a final experiment, we investigated the compressibility of the signal pulse. If the linear frequency chirp is transferred from the pump to the co-propagating signal, the MOPO signal pulse should be compressible. To test this, we built a compressor with anomalous groupdelay dispersion involving 4 bounces off a 1200 l/mm diffraction grating. The MOPO was pumped with positively chirped pulses of similar spectral and temporal widths as in the previous experiment. The signal pulse before and after the compressor was characterized using cross-correlation with the 1 ps-long reference pulse at the pump wavelength. The crosscorrelation traces measured by employing noncollinear sum-frequency mixing in a 200 µmlong BBO crystal are shown in Fig. 2 for different compressor lengths. The compressibility of the MOPO signal proves that the phase modulation which is imposed on the pump pulse is transferred to the signal. This is a unique feature of the MOPO, enabled by the counter-propagating TWM process.

The transfer of modulation from the pump to the signal can also be shown theoretically. In order to elucidate the unusual coherence properties in the MOPO and also to model the experimental situation, we numerically solved the coupled wave equations using the slowly varying envelope and plane wave approximations for parametric down-conversion in counter-propagating geometry:

(∂ t + v g,p ∂ z + γ p + iβ p ∂ tt ) A p = -σ p A s A i , (4a)
(∂ t + v g,s ∂ z + γ s + iβ s ∂ tt ) A s = σ s A p A * i , (4b)
(∂ t -v g,i ∂ z + γ i + iβ i ∂ tt ) A i = σ i A p A * s . (4c)
Here A j , β j , γ j , σ j = 2πd ef f v g,j /(λ j n j ) are the field amplitude, the group-velocity dispersion, the loss and the nonlinear coupling coefficients for the j = p, s, i wave, respectively. A model PPKTP crystal with a length of 6.5 mm and an effective nonlinearity of d ef f = 9 pm/V was excited with an asymmetric super-Gaussian pump pulse with amplitude

A p (t) = A p0 [1 -t/(2∆t 0 )] exp[iφ p (t) -((t -t 0 )/∆t 1 ) 8 /2].
The pulse was centered at t 0 = 441 ps and the temporal widths ∆t 0 = 1766 ps and ∆t 1 = 220 ps were chosen in order to fit the experimental intensity pump shape and to get a FWHM pulse length of ∆t p = 400 ps. The theoretical pump pulse contained a linear frequency chirp, given by the quadratic phase modulation φ p (t) = α 2 ((tt 0 )/τ 0 ) 2 , where τ 0 = 2/(σ p A p0 ) is the characteristic nonlinear interaction time, defining the characteristic nonlinear interaction length, L nl = v g,p τ 0 . For the pump intensity of 1.1 GW/cm 2 , which is a pump intensity close to the experimental input, the characteristic parameter values are τ 0 = 6.9 ps and L nl = 1 mm. The pump chirp parameter α 2 = 0.46 was chosen to give a positive chirp and a spectral width of 1.27

THz. The dispersion parameters for the KTP crystal were calculated using the Sellmeier expansion from Ref. [23] and the quasi-phase matched interaction generated signal and idler waves around around 1125 nm and 2952 nm, respectively, for a pump wavelength of 814.5

nm. For these central wavelengths, the spectral compression in the idler, as estimated from Eq. 3, is ∆ω i /∆ω p 1/92.

Simulations of the MOPO at the pump intensity of 1.1 GW/cm 2 reveal that the oscillation develops after an initial delay of 300 ps and TWM starts depleting the trailing end of the pump pulse where the high-frequency components are located due to the chirp. This can be seen in the comparison between the input and output pump spectra in Fig. 3(a). Fig. 3(b) Fig. 3(c) show that the generated signal obtains a FWHM spectral width of 440 GHz, whereas that of the idler is only 6.5 GHz, i.e. about 200-times narrower than the initial pump spectrum and 70-times narrower than the signal. The strong asymmetry in the spectral widths of the signal and idler is related to the amount of phase modulation in the waves. This is illustrated in Fig. 4, where the phase of the idler wave shows very little variation along the crystal, while the phases of the signal and pump remain locked. Qualitatively one can understand this by realizing that the initial pulse front of the backward-propagating idler wave is rapidly separated from the signal and the pump, akin to fast convection, and seeds the parametric amplification process upstream, while maintaining its initial phase and enforcing the phase of the signal, owing to the phase relation in Eq. 1. Simulations of the MOPO pumped with a wave containing random phase modulation give qualitatively similar results, i.e. the convective phase locking mechanism ensures the generation of a narrowband coherent counter-propagating idler wave, while the signal inherits the random phase modulation from the pump.

In conclusion, we have employed a mirrorless OPO realized in a sub-micrometer periodically-poled KTP crystal for experimental demonstration that the phase of the pump wave is coherently transferred to the co-propagating OPO signal, as a result of the maximized convective separation of the pump and idler pulse fronts. This convective mechanism, as was elucidated by the numerical modeling, gives rise to a narrowband counter-propagating idler wave, regardless of the details of the pump phase. The corresponding FWHM widths are 1.27 THz, 440 GHz and 6.5 GHz.

  5 nm with a frequency bandwidth of 1.21 THz. The pulse was stretched in a normal-dispersion stretcher and amplified in a Ti:Sapphire regenerative amplifier. The FWHM length of the amplified pulse was 480 ps and it was used for MOPO pumping. A small portion of the pump pulse was recompressed to close to transform-limited duration of 1 ps and was used as a reference for cross-correlation measurements. The MOPO reached threshold at the pump intensity of 0.8 GW/cm 2 . The measured pump spectra (spectrometer Ando AQ-6315A, resolution 0.05 nm) at 1.3-times the threshold intensity are shown in Fig.1(a), where the undepleted pump spectrum was measured when the pump beam propagated outside the structured area of the PPKTP and the MOPO was not operational. The linear frequency chirp of the pump, measured using cross-correlation with the reference pulse, was dω p /dt = 15.7 mrad/ps 2 .

FIG. 1 :FIG. 2 :FIG. 3 :

 123 FIG. 1: Experimental spectra: Undepleted (solid line) and depleted (dashed line) pump (a). Copropagating signal (b). Counter-propagating idler (c). The graphs show that the FWHM widths of the pump and signal are 1.21 THz and 410 GHz, respectively. The deconvoluted idler FWHM is 13 GHz.

FIG. 4: Phase distribution inside the for the pump, the signal (locked to the pump) and the backward idler (invariant). The x-axis is in units of L nl = v g,p τ 0 = 1 mm.