Michael Kruse
email: michael.kruse@inria.fr

Tobias Grosser
email: tobias.grosser@inf.ethz.ch

DeLICM: Scalar Dependence Removal at Zero Memory Cost

Keywords: CCS Concepts, Software and its engineering → Compilers; Polyhedral Framework, Scalar Dependence, LLVM, Polly

Increasing data movement costs motivate the integration of polyhedral loop optimizers in the standard flow (-O3) of production compilers. While polyhedral optimizers have been shown to be effective when applied as source-to-source transformation, the single static assignment form used in modern compiler mid-ends makes such optimizers less effective. Scalar dependencies (dependencies carried over a single memory location) are the main obstacle preventing effective optimization. We present DeLICM, a set of transformations which, backed by a polyhedral value analysis, eliminate problematic scalar dependences by 1) relocating scalar memory references to unused array locations and by 2) forwarding computations that otherwise cause scalar dependences. Our experiments show that DeLICM effectively eliminates dependencies introduced by compiler-internal canonicalization passes, human programmers, optimizing code generators, or inlining -without the need for any additional memory allocation. As a result, polyhedral loop optimizations can be better integrated into compiler pass pipelines which is essential for metaprogramming optimization.

Introduction

Advanced high-level loop optimizations, often using polyhedral program models [START_REF] Verdoolaege | Presburger Formulas and Polyhedral Compilation[END_REF], have been shown to effectively improve data locality for image processing [START_REF] Teja Mullapudi | Polymage: Automatic Optimization for Image Processing Pipelines[END_REF], iterated stencils [START_REF] Bandishti | Tiling Stencil Computations to Maximize Parallelism[END_REF], Lattice-Boltzmann computations [START_REF] Pananilath | An Optimizing Code Generator for a Class of Lattice-Boltzmann Computations[END_REF], sparsematrices [START_REF] Venkat | Loop and Data Transformations for Sparse Matrix Code[END_REF] and even provide some of the leading automatic GPU code generation approaches [START_REF] Baskaran | Automatic C-to-CUDA code generation for affine programs[END_REF][START_REF] Verdoolaege | Polyhedral Parallel Code Generation for CUDA[END_REF].

While polyhedral optimizers have been shown to be effective in research, but are rarely used in production, at least partly because they are disabled in the most common optimization levels. because none of the established frameworks is enabled by default in a standard optimization setting (e.g. -O3). With GCC/graphite [START_REF] Trifunovic | Graphite Two Years After: First Lessons learned from Real-World Polyhedral Compilation[END_REF], IBM XL-C [START_REF] Bondhugula | A Model for Fusion and Code Motion in an Automatic Parallelizing Compiler[END_REF], and LLVM/Polly [START_REF] Grosser | Polly -Performing Polyhedral Optimizations on a Low-Level Intermediate Representation[END_REF] there are three polyhedral optimizers that work directly in production C/C++/FORTRAN compilers and are shipped to millions of users. While all provide good performance on various benchmarks, one of the last roadblocks that prevents enabling polyhedral optimizers by default is that they generally run as pre-processing pass before the standard -O3 pass pipeline.

Most compilers require canonicalization passes for their detection of single-entry-single-exit regions, loops and iteration count to work properly. For instance, natural loops need recognizable headers, pre-headers, backedges and latches. Since a polyhedral optimizer also makes use of these structures, running the compiler's canonicalization passes is necessary before the polyhedral analyzer. This introduces changes in the intermediate representation that appear as runtime performance noise when enabling polyhedral optimization. At the same time, applying loop optimizations -which often increase code size -early means that no inlining has yet been performed and consequently only smaller loop regions are exposed or future inlining opportunities are prevented.

Therefore, the better position for a polyhedral optimizer is later in the pass pipeline, after all inlining and canonicalization has taken place. At this position the IR can be analyzed without having to modify it and heuristic inlining decisions are not influenced. However, when running late in the pass pipeline, various earlier passes introduce IR changes that polyhedral optimizers do not handle well.

For instance, Listing 1 works entirely on arrays and is easier to optimize than Listings 2 to 4. This is because of the temporaries a and c, which baked-in the assumption that for (int i = 0; i < N; i += 1) { T: C[i] = 0; for (int k = 0; k < K; k += 1) S:

C the i-loop is the outer loop. Although the data-flow dependencies are the same, new false dependencies are introduced that prevent the scalars a or c from being overwritten before all statements using that value have been executed. For Listing 3, this means that the dynamic statement instance T (i), statement T at loop iteration i, cannot execute before the previous iteration i -1 has finished. In this case, statement instance U (i -1) must execute before T (i), represented by the (anti-)dependencies

∀i ∈ { 1, . . . , N -1 } : U (i -1) → T (i) .
We call dependencies that are induced by a single memory location such as a or c, scalar dependencies. Such false dependencies effectively serialize the code into the order it is written, inhibiting or at least complicating most advanced loop optimizations including tiling, strip-mining, and parallelization. Certain specific optimizations can cope well with scalar dependencies. A vectorizer can, for example, introduce multiple independent instances of the scalars, one for each SIMD lane. An automatic parallelizer can privatize the temporaries per thread. However, general purpose loop scheduling algorithms such as Feautrier [START_REF] Feautrier | Some Efficient Solutions to the Affine Scheduling Problem -Part I. One-dimensional Time[END_REF][START_REF] Feautrier | Some Efficient Solutions to the Affine Scheduling Problem -Part II. Multidimensional Time[END_REF] or Pluto [START_REF] Bondhugula | A Practical Automatic Polyhedral Parallelizer and Locality Optimizer[END_REF] do not take privatization opportunities into account. These are fundamentally split into an analysis and a scheduling part. Analysis extracts dependences to determine which execution orders are possible, and the scheduler uses this information to find a new ordering that does not violate any dependence. The analysis result must be correct even for transformations such as loop distribution and -reversal which are not enabled by these transformation-specific techniques. Hence, to allow maximal scheduling freedom, it is desirable to model programs with a minimal number of scalar dependencies. As the semantics of Listings 1 to 4 are identical, a good compiler should be able to compile them to the same optimized program, after all loop optimizations have been applied.

In this article we present a novel memory dependence removal approach that reduces a polyhedral's compiler sensitivity on the shape and style of the input code and enables effective high-level loop optimizations as part of a standard optimization pipeline. Our contributions are:

• A polyhedral value analysis that provides, at statement instance granularity, information about the liveness and the source statement of individual data values.

c = 0 c + = A [ 0 ] [ 0 ] c + = A [ 0 ] [ 1 ] c + = A [ 0 ] [ 2 ] c = 0 c + = A [ 1 ] [ 0 ] c + = A [ 1 ] [ 1 ] c + = A [ 1 ] [ 2 ] c = 0 c + = A [ 2 ] [ 0 ] c + = A [ 2 ] [ 1 ] c + = A [ 2 ] [ 2 ] 0 S (0, 0) S (0, 1) S (0, 2) S (0, 2) 0 S (1, 0) S (1, 1) S (1, 2) S (1, 2) 0 S (2, 0) S (2, 1) S (2, 2)
Figure 1. Reaching definition and known content of c.

Θ :

T (0) S (0, 0) S (0, 1) S (0, 2)

U (0) T (1) S (1, 0) S (1, 1) S (1, 2) U (1) T (2) S (2, 0) S (2, 1) S (2, 2) U (2)
Figure 2. Lifetime of variable c. C++ abstraction layers allow higher-level concepts to be represented as objects where components are distributed over different functions. For instance, a class can implement a matrix subscript operation by overloading the call operator, as uBLAS does [START_REF] Koch | Boost uBLAS[END_REF]. When invoked the operator will return the content at the indexed matrix location as a scalar. To optimize across such abstraction layers, it is essential for inlining to have taken place. Manual source optimizations applied by users to not rely on the compiler to do the optimization. For instance, possible aliasing between array C and A in Listing 1 may prevent LICM to be performed by the compiler. Even C++17 does not yet provide annotations (e.g., restrict) to declare the absence of aliasing, so programmers may just write Listing 3, or just consider it to be the more natural formulation. Code generators which are not meant to generate output read by humans, might be inclined to generate pre-optimized code. TensorFlow XLA, for instance, passes code to LLVM with pre-promoted variables in its matrix multiplication kernels [START_REF] Agarwal | Enable Polyhedral Optimizations in XLA through LLVM/Polly[END_REF].

U (0) U (1) U (2
C [ 0 ] = c C [ 1 ] = c C [ 2 ] = c

Value Coalescing

In this section we present the idea of reusing an array element to store a scalar. We first present the idea on an example (next section) and the general algorithm in Section 2.2.

Value Coalescing by Example

To illustrate how the coalescing algorithm will work, we apply it on Listing 3 with N = K = 3. Figures 1 to 6 visualize the execution of each statement. Assuming that the execution of each statement takes one time unit, each statement instance has a timepoint that marks the time passed since the execution of the first statement. Let a zone be a set of one or more intervals between (integer) timepoints. For instance, the zone [START_REF] Baghdadi | Improved Loop Tiling Based on the Removal of Spurious False Dependences[END_REF][START_REF] Baskaran | Automatic C-to-CUDA code generation for affine programs[END_REF] is the duration between timepoint 3 and 5, excluding 3 itself.

The reaching definition of a memory location is the last write to a variable at some timepoint. Figure 1 shows the reaching definition of the variable c. The reaching definition in the zone ]3, 5] is S(0, 2) because S(0, 2) writes the value that we would read from c in that zone. If, like it is the case for S(0, 2), a statement reads from and writes to the same location, we assume that the read is effective in the preceding reaching definition. For this reason the definition zones are always left-open and right-closed. Zones can also be unbounded, like the reaching definition zone of the last write S(2, 2) in the example.

Using these reaching definitions, we also know which value a location contains in the definition zone. In case of T (0), this is the constant 0. For cases where there is no direct representation, we use the statement instance itself to represent the value it writes. Timepoints before the first write use the value the variable had before timepoint zero.

The same rules also applies to the array C as shown in Figure 3. The difference is that each array element has its own reaching definition. In this example, each element is written exactly once.

The zone from the definition to its last use is the definition's lifetime. If there is no use, then the lifetime is empty. A variable's lifetime is the union of all its definition's lifetimes. Figure 2 shows the lifetime of c. The lifetime for the for

(int i = 0; i < N; i += 1) { T: C[i] = 0; for (int k = 0; k < K; k += 1) S: C[i] += A[i] * B[k]; U: C[i] = C[i]; } Listing 5.
Sum-of-products (Listing 3) after mapping of the scalar c to the array elements

C[i].
array C is shown in Figure 4, separately for each of the three elements. A location's zone is unused if there is no lifetime using it. Unused zone intervals usually extend from the last read of a reaching definition to the write of the next definition zone.

It is easy to see that the lifetime of c fits into the unused zone of array C. Hence, there is no need to reserve memory for both of them; we can save memory by coalescing both variable's memory to the same space.

One possibility is to store all of c into the memory of C [START_REF] Allen | Automatic Translation of FORTRAN Programs to Vector Form[END_REF], as shown in Figure 5. The alternative is to map each lifetime to a different array element, shown in Figure 6. The latter results in the code shown in Listing 5.

For our purpose, this latter variant is preferable. The first reason is that when U (i) reads c to store it to C[i], it has to load c's value from C[i]. That is, statement U (i) is not required anymore. Secondly, and more importantly, the perdefinition lifetimes of c are stored at different locations such that there are no false dependencies between them.

The observation that statements can be removed if two adjacent lifetimes use the same storage motivates a simple heuristic: at a statement that starts a lifetime (that is, an array element is written), find another lifetime that ends which can be mapped to the same element. A lifetime can be mapped if the array element's unused zone is large enough for the entire lifetime.

The new lifetime of C[i] is the union of the lifetimes of the scalar and the previous lifetime. If there were other unmapped scalars in the program, we could now proceed to map these scalars as well. If two lifetimes overlap it might still be possible to coalesce them. In Figure 2 we annotated the known content at each timepoint. If the lifetimes overlap, but are known to contain the same value, they can still be mapped to the same memory location. This is important for cases such as Listing 4. Here, the writeback of c to C[i] in every instance of statement S(i, j) does not end its lifetime, but overlaps with the lifetime of C[i].

The Greedy Scalar Mapping Algorithm

We have seen the outline of how to coalesce scalars and array elements to avoid dependencies. In this section, we describe a general algorithm that selects the memory to be coalesced. The algorithm's pseudocode is shown in Listing 6. It maps the first variable it sees without backtracking after a possible mapping is found, i.e., a greedy algorithm. In the following paragraphs we explain the algorithm in detail.

The algorithm begins by collection data about the loop nest, which we call Knowledge (line 1). It includes information about each memory location referenced in this system, scalars as well as array elements:

• All writes to a location.

-The reaching definition derived from the writes.

-The written value is the known content for the reaching definition's zone. • All reads from a location.

-The lifetime zones derived from the reads and the reaching definitions.

• All memory location's unused zones, which is the complement of all lifetimes occupying that location. Alternatively to using the complement, one can compute the zones from each reaching definition's last read to the next write.

All of these can be represented as polyhedra with dimensions tagged as belonging to an array element, timepoint, statement or value. Every write potentially terminates an unused zone right before it. Some mapping target locations might be unsuitable, for instance because the store is not in a loop or the span of elements written to is only a single element (like in Figure 6). Such targets are skipped (lines 3-4).

For a given write, we collect two properties: first, the target array element for each statement instance that is overwritten and therefore causes an unused zone before it (Target on line 5); second, the list of possible scalars that might be mapped to it (getInputScalars at line 6). The best candidate for mapping is the value that is stored by the write because it would effectively move the write to an earlier point where the value is written (like U (i) in Listing 5). These candidates are used to initialize a queue, with the best candidate coming out first. Prioritized candidates are those that lead to a load from the target.

Let s be the next candidate scalar (line 8). Similar to checking the eligibility of w being a mapping target, we check whether s is eligible to be mapped to t (Lines 9-10). Reasons for not being a viable scalar include being larger than the target location, being defined before the modeled code or used after it (because these accesses cannot be changed). The exact requirements depends on the intermediate representation used by the implementation. Once s passes the basic checks, we compute the additional knowledge for it in case it is mapped to t. It consists of the lifetime for the previously unused array elements of t and the known content of s, which then becomes the known content of t. We call this supplemental knowledge the Proposal (line 11).

The proposal is then compared with the existing knowledge to see whether there are conflicts (line 13). For two knowledges A and B to be compatible (non-conflicting), they must meet the following conditions for every memory location:

• The lifetime zones of A and B must be disjoint, except when they share the same known content. • Writes in A cannot write into B's lifetime zone, except if the written value is already B's known content. • Writes in B cannot write into A's lifetime zone, except if the written value is already A's known content.

A conflict is a violation against one of these rules. They ensure that the semantics of the program remain the same after carrying out the mapping of the proposal. If a conflict is found, the proposal is rejected and the next scalar from the queue is tried.

for (int i = ...) { c = ... T: use(c); U: A

[i] = g(c); } for (int i = ...) { A[i] = ... T: use(A[i]); U: A[i] = g(A[i]); } Listing 7.
Example when coalescing restricts scheduling possibilities. On the left statements T and U can be executed in exchanged order; after mapping c to A[i] (right) this is not possible anymore.

Note that a write to A or B does not induce a lifetime if that value is never read. Still, such a write to, say A, would overwrite the content of B if coalesced together. Therefore both directions need to be checked.

If there is no conflict, then the proposal is applied. All uses of s are changed to uses of t (line 17). The proposal is used to update the knowledge (line 18) by uniting the lifetimes and known content. Since writes to s have become writes to t, a new unused zone ends at each write, to which variables can be mapped to. As with the original write (line 6), we add possible mapping candidates to the work queue (line 20). Because after mapping there are no more writes to the location of s, we use the writing statements from before the transformation (line 15).

The algorithm runs until no more variable can be mapped to t and then continues with the next write, until all writes have been processed (line 2). As Listing 7 shows, coalescing can also add additional false dependencies. However, loopcarried dependencies block more optimizations that loopinternal ones.

Operand Tree Forwarding

The mapping algorithm is only able to remove scalar dependencies if there is an unused array element, or one that stores the same value anyway. For a in Listing 2 this does not apply. Fortunately, we can just repeat the computation of a in every statement it is used in. The result of such a forwarding is shown in Listing 8. Thereafter the variable a becomes dead code.

Operand forwarding is the replication of instruction operands defined by operations in other statements. This is possible when the operation's arguments are still available, which can in turn be made available by forwarding them as well such that transitively we get an operand tree.

Besides pure instructions whose result only depend on their arguments, replicating a load requires that the location loaded from contains the same value. Instead of determining whether the memory location is unchanged, we can reuse the knowledge we already need to obtain for greedy mapping. Given the known content information at the timepoint of the target of the forwarding, any value required by the target statement can be reloaded. The two advantages are that the reload does not need to happen from the same location as the original load, and the reloaded value does not even need to be a result of a load.

Listing 9 shows the pseudocode that determines whether an operand tree rooted in s whose result is used in another statement, can be forwarded to that target statement. If canForwardTree returns a positive result, the procedure doForwardTree in Listing 10 can be called to carry-out the forwarding.

Both procedures are recursive functions on the operand tree's children. They are correct on DAGs as well, but lead to duplicated subtrees. doForwardTree repeats the traversal of canForwardTree, but can assume that every operation can be forwarded. A tree that contains a non-forwardable subtree would require the introduction of a scalar dependency for its value, hence such trees are not forwarded at all.

The method findSameContent (line 2) looks for an array element for each statement instance of the target that contains the result of operation s. If it finds such locations, the operand tree does not need to be copied but its result can be reloaded from these locations. The new load is added to the list of operations executed by the target statement (line 4 of doForwardTree).

If the operation is speculatable (line 4 in canForwardTree), i.e., its result depends only on its arguments, we also need to check whether its operands are forwardable (line 7) since copying the operation to the target will require its operands to be available as well. In doForwardTree, the speculatable operation is added to the target's operations (line 7) and a recursive call on its operands ensures that the operands values are as well available in the target statement (line 9).

Implementation

Both transformations, value mapping and operand tree forwarding, have been implemented in Polly [START_REF] Grosser | Polly -Performing Polyhedral Optimizations on a Low-Level Intermediate Representation[END_REF]. Polly inserts itself into the LLVM pass pipeline depending on the -polly-position option, as shown in Figure 7, which in the following we shorten to early and late.

LLVM's early mid-end is (also) meant to canonicalize the input IR: to find a common representation for inputs that have the same semantics. Transformations should never make a follow-up analyses worse, e.g., not introduce irreducible loops or remove pointer aliasing information. Loop-Invariant Code Motion and Partial Redundancy Elimination is part of the IR's canonicalized form. Low-level and most target-specific transformations take place later in the pipeline.

Because scalar dependencies are destructive to polyhedral optimization, Polly's default configuration used to be early. Polly depends on LLVM's loop detection and its ScalarEvolution analysis, such that a selected set of passes are added before Polly.

In the late position, Polly is added after LLVM's own canonicalization. It first runs the operand tree forwarding followed by the greedy mapping algorithm. A simplification pass cleans up accesses and statements that have become unnecessary. The vectorizer expects canonicalized IR, so the mid-end passes are run again if Polly generated any code in that function. The pipeline is tuned for the current pass order (e.g. the inliner's heuristics) and used in production, therefore adjusting LLVM's canonicalization passes for the needs of Polly is not an option.

IR-Specific Algorithm Details

Because LLVM-IR is an SSA-based language, a value can be uniquely identified by the operation and the statement instance it is computed in. We use this for known content analysis. For instance, the value a produced by statement T (i) in Listing 2 is represented by [T (i) → a]. Because a is loaded from the array A, the content of A[i] at the time of the execution of T (i) can also be identified as [T (i) → a].

In addition to the SSA-value for result of the φ-node, Polly models a φ with an additional memory location as shown in Listing 11. Handling of φ-nodes is analogous to SSA-values, but with multiple writes and a single read to/from a virtual %v.phiops variable.

Listing 11. Listing 6 does not assume a single write per scalar, hence is also applicable. The fact that there is only one read from the additional locations helps computing the lifetime. The φ's known content can be replaced by the incoming value in simple cases.

Evaluation

The evaluation consists of two parts. In Section 5.1 we analyze the transformations applied by DeLICM itself and which polyhedral optimizations are enabled by it. The measurements are done statically by the compiler without executing the code. The second part in Section 5.2 evaluates the speedup gained through the enabled transformations. The code is optimized for and run on an Intel Xeon E5-2667 v3 (Haswell architecture) running at 3.20 GHz. Its cache sizes are 32 KB (L1i), 32 KB (L1d), 256 KB (L2) and 20 MB (L3). The machine has 8 physical and 16 logical cores, but we only evaluate single-thread performance. The hardware details are mostly relevant for the performance tests, but some mid-end passes make use of target-specific information as well. Hence, hardware details can influence which transformations are carried out. DeLICM itself does not make use of hardware architecture information. The compiler used for all evaluations is based on clang 6.0.0 (SVN revision 317808) using the optimization level -O3 -march=native -ffast-math for all tests. All evaluation is done on Polybench/C 4.2.1 beta [START_REF] Pouchet | Polybench 4.2.1 beta[END_REF].

Polybench is a collection of 30 benchmarks with kernels typical in scientific computing. Polybench/C benchmarks are written with polyhedral source-to-source compilers in mind with the consequence that it avoids scalar variables since they are known to not work well in the polyhedral model. Instead, we let the LLVM scalar optimizers (mostly LICM and GVN) introduce the scalar dependencies by running Polly late in LLVM's pass pipeline. This allows us to compare the DeLICM result to a reference source without scalar dependences.

Unfortunately, we hit a problem where the combination of the LLVM passes LoopRotate and JumpThreading causes ScalarEvolution to being unable to analyze a loop when an inner loop has no iterations. We modified the Polybench source to avoid this problem (by peeling off the first outer loop), because this is a shortcoming of LLVM's canonicalization, unrelated to Polly. We are in contact with the LLVM community to resolve this in the future.

In order to allow LLVM's scalar optimizers to work better, we enable Polybench's use of the C99 restrict keyword (-DPOLYBENCH_USE_RESTRICT). This tells the compiler that arrays do not alias each other which allows more code movement. For all tests, we use Polybench's -DEXTRALARGE_DATASET, which sets the problem size such that the computation requires about 120MB of memory.

To show the effect of C++ and inlining, we translated four of the benchmarks to C++ using uBLAS [START_REF] Koch | Boost uBLAS[END_REF]: covariance, correlation, gemm and 2mm. The former two use the original algorithm but instead of an array, they use uBLAS's vector and matrix types. The latter two use uBLAS own implementation of the matrix-matrix product. uBLAS is a header-only library with extensive use of expression templates and has no target-specific optimizations.

Table 1. Number of applied DeLICM transformations at early and late positions in the LLVM pass pipeline. "Forwards" is the number of copied instructions (line 7 of Listing 10), plus the number of reloads from arrays (line 4). "Mappings" is the number of SSA values (plus φ nodes) mapped to array locations (number of scalars that pass the conflict test at line 13 of Listing 6).

early late Benchmark Forwards Mappings Forwards Mappings O3) using median execution times. Each experiment ran 5 times, with all median absolute deviations being less than %2 of the median. DeLICM is able to recover the original performance at late position in most cases.

Data Mining correlation 0 0 1+1 3+3 covariance 0 0 2+0 2+2 Linear Algebra gemm 0 0 1+1 0 gemver 0 0 0+2 2+2 gesummv 0 0 0 2+2 symm 0 0 1+4 0 syr2k 0 0 0+2 0 syrk 0 0 1+1 0 trmm 0 0 0+1 0 2mm 0 0 0 2+2 3mm 0 0 0 3+3 atax 0 0 0 1+1 bicg 0 0 0+1 1+1 doitgen 0 0 0 0 mvt 0 0 0 2+2 Solvers cholesky 0 0 0 0 durbin 3+3 2+1 0 0 gramschmidt 0 0+3 0 2+2 lu 0 0 0+1 0 ludcmp 0+3 0+11 0+3 1+7 trisolv 0 0 1+1 0 Dynamic Programming deriche 8+0 0+4 4+0 0+4 nussinov - - - - Shortest Path floyd-warshall 0 0 0 0 Stencils adi 74+0 0 0+4 0+2 fdtd-2d 0 0 0+3 0 heat-3d 0 0 0+2 0 jacobi-1d 0 0 0+4 0 jacobi-2d 0 0 0+2 0 seidel-2d 0 0 0+6 0 uBLAS C++ correlation - - 1+3 3+0 covariance - - 2+2 2+0 gemm - - 0+1 1+1 2mm - - 0+1 2+2
Data Mining correlation 0 0 0 4+6 0 +5 covariance 1+0 1+0 0 3+4 1+0 +3 Linear Algebra gemm 0 0 0 1+0 0 0 (+1) gemver 0 0 0 4+4 0 +3 gesummv 0 0 0 2+4 0 +1 symm 0+5 0+5 0 5+2 1+2 0 syr2k 0 0 0 2+0 0 +1 syrk 0 0 0 1+0 0 +1 trmm 0 0 0 1+2 0 +2 2mm 0 0 0 2+4 0 +2 (+2) 3mm 0 0 0 3+6 0 +3 (+3) atax 0 0 0 1+2 0 +2 bicg 0 0 0 2+2 0 0 doitgen 0 0 0 1+2 1+2 0 mvt 0 0 0 2+4 0 +2 Solvers cholesky 0 0 0 0 0 0 durbin 4+5 1+3 0 5+4 5+4 0 gramschmidt 1+5 1+0 0 3+4 1+0 +3 lu 0 0 0 0+2 0 +1 ludcmp 3+18 0 0 4+14 0 0 trisolv 0 0 0 1+4 0+4 0 Dynamic Programming deriche 0+28 0+20 0 0+28 0+20 0 nussinov - - - - - - Shortest Path floyd-warshall 0 0 0 0 0 0 Stencils adi 0 0 0 0+12 0 +4 fdtd-2d 0 0 0 1+4 0 0 heat-3d 0 0 0 0+4 0 +1 jacobi-1d 0 0 0 0+8 0 +1 jacobi-2d 0 0 0 0+4 0 +1 seidel-2d 0 0 0 0+12 0 0 uBLAS C++ correlation - - 0 3+6 0 +4 covariance - - 0 2+4 0 +4 gemm - - 0 2+2 0 +2 (+1) 2mm - - 0 3+4 0 +4 (+2)

Static Evaluation

Table 1 shows how many transformations the DeLICM algorithms applies on the benchmarks. To show how effective they were, Table 2 shows the number of scalar writes in loops. We use this measure as a proxy for scalar dependencies. Not every scalar dependency inhibits loops transformations (for instance, using a constant defined before the loop), but every scalar write in a loop causes a false dependency itself in the next iteration, and every dependency involves a write access.

When Polly is at the early position, only few scalar dependencies are present and consequently DeLICM does mostly nothing. At the late position, DeLICM successfully removed all scalar dependencies in 24 (of 31 that had at least one) programs.

One of the trickier cases is atax in which the scalar temporary, called tmp, was manually expanded into an array. The LLVM passes almost entirely recovered the scalar nature of the temporary so it is not obvious to find a mapping location. The GVN partial redundancy elimination introduces φ nodes into stencil iterations to reuse an already loaded value in the next stencil. This effectively serializes the inner loop. To make it parallel again, the φ-nodes have either to be forwarded or traversed to find the original location. Our implementation does the latter.

In the following, we discuss cases where not all scalar dependencies could be removed and explore the reasons for it. The programs symm, durbin and deriche use more scalars in their loops than there are unused array elements. DeLICM does not help in these cases. In covariance, the dependence is caused by a division that cannot be forwarded because LLVM cannot prove that the divisor is non-zero. The LLVM framework provides no property for instructions that can be executed multiple times, if they are executed at least once. We had to fall back to the stricter speculatable property which also allows instructions to be executed if they were not executed at all in the original program. Anyway, Polly is able to extract the performance-critical code and optimize it. The remaining scalar write in gramschmidt is due to a call to the sqrt function whose result is used in an inner loop. LLVM does not consider sqrt speculatable such that the operand tree forwarder does not copy a call to it. LLVM's LoopIdiom pass introduces a memset memory intrinsic into doitgen's code. Although Polly handles memsets, it causes each array element to be split into byte-sized subelements. Our implementation of content analysis does not yet support mixed-size array elements. Similarly, trisolv has some confusion about an array's type. Uses of the same array as 64-bit integer and double-precision floating-point occur in the same function .

Polly failed to recover the array subscripts of an access in nussinov (at early and as well as at late position) and because of it, gives up optimizing it. Polly's access analysis is not invoked. LLVM does not move code out of loops in floyd-warshall, hence DeLICM has nothing to do. The function calls to the overloaded operators in the C++ codes also causes Polly to bail out. After inlining, they are similar to the original Polybench implementation.

Performance Evaluation

The runtime speed-ups are shown in Figure 8 on a logarithmic scale. The speedups are relative to the execution time of the benchmark compiled with clang -O3 without Polly. Each execution time is the median of 5 runs. A run of all benchmarks takes in the range of 1 hour to complete.

With Polly executed early in the pipeline ("Early" bars), we gain the highest speed-ups with the matrix-multiplication family (gemm, 2mm, 3mm) due to a special optimization path for it. The benchmarks using uBLAS cannot be optimized because they contain not-yet inlined function calls. The benchmarks gemver, symm, mvt, cholesky, durbin, gramschmidt, lu, ludcmp, deriche, floyd-warshall, nussinov, heat-3d and jacobi-2d are not shown in the figure because neither the pipeline position nor DeLICM have a significant effect on their execution speeds, in other cases Polly's transformations even cause slowdowns. Our contribution is to enable transformations, not about which one to select. Therefore any change in performance relative to Polly switched off is a sign that some transformation has been performed and therefore is a success for DeLICM. We continue working on the heuristics that improve performance, or at least do not regress performance.

Executing Polly at the late position causes the performance to fall back to the performance without Polly ("Late"). Generally, this is because Polly does not generate any code because of new scalar dependencies. Enabling DeLICM ("Late DeLICM") almost always restores the original performance. For some benchmarks, we even got a (higher) speed-up where there was none before: trmm and fdtd-2d. Thanks to the inlining having happened at the late position, the C++ benchmarks using uBLAS can now be optimized as well. The uBLAS matrix-multiplication benchmarks are not vectorized by clang without Polly , which leads to an even higher speedup when it is vectorized by Polly. The only benchmark where the performance could not be recovered are doitgen and trisolv, caused by scalar dependencies that could not be removed.

Applying DeLICM at the beginning of the LLVM pipeline ("Early DeLICM"), without LICM and GVN, has little effect as the Polybench benchmarks avoid scalar dependencies in the source.

Related Work

We can categorize most work on avoiding false dependencies into two categories: memory duplication and ignoring nonflow dependencies.

The first category provides additional memory such that there are fewer false dependencies between unrelated computations. Techniques such as renaming, scalar expansion and node splitting [START_REF] Allen | Automatic Translation of FORTRAN Programs to Vector Form[END_REF][START_REF] Kuck | Dependence Graphs and Compiler Optimizations[END_REF] have been proposed even before the appearance of the polyhedral model. Taken to the extreme, every statement instance writes to its own dedicated memory [START_REF] Feautrier | Array Expansion[END_REF]. Like in SSA, every element is only written once and therefore this mode is also called Dynamic Single Assignment (DSA) [START_REF] Vanbroekhoven | Transformation to Dynamic Single Assignment Using a Simple Data Flow Analysis[END_REF] or Array SSA [START_REF] Knobe | Array SSA Form and Its Use in Parallelization[END_REF]. This eliminates all false dependencies at the cost of potentially greatly increasing memory usage. Refinements of this technique only duplicate a private copy per thread [START_REF] Li | Array Privatization: A Loop Transformation for Parallel Execution[END_REF]. This can solve the problem for parallelism but does not enable inner-thread scheduling such as tiling. [START_REF] Trifunovic | Elimination of Memory-Based Dependences for Loop-Nest Optimization and Parallelization[END_REF][START_REF] Vasilache | Trading Off Memory For Parallelism Quality[END_REF] propose privatization on demand, when an optimization finds restricting dependencies.

There is the possibility to contract array space after scheduling [START_REF] Somashekaracharya | Automatic Storage Optimization for Arrays[END_REF][START_REF] Somashekaracharya | SMO: An Integrated Approach to Intra-Array and Inter-Array Storage Optimization[END_REF][START_REF] Darte | Extended Lattice-Based Memory Allocation[END_REF][START_REF] Lefebvre | Automatic storage management for parallel programs[END_REF][START_REF] Quilleré | Optimizing Memory Usage in the Polyhedral Model[END_REF][START_REF] Doran | Allocating Memory Arrays for Polyhedra[END_REF]. However, the re-scheduled program may inherently require more memory than the source program, especially if the scheduler is unaware that its decisions may increase the memory footprint.

The second strategy is to remove non-flow dependencies when it can be shown they are not important to the correctness of the transformed program. Which dependencies can be removed depends on the scheduling transformation to be performed. A technique called variable liberalization [START_REF] Mehta | Variable Liberalization[END_REF] allows loop-fusion. Tiling and parallelism can be recovered using live-range reordering [START_REF] Baghdadi | Improved Loop Tiling Based on the Removal of Spurious False Dependences[END_REF][START_REF] Verdoolaege | Live Range Reordering[END_REF].

Both come with the disadvantage that they are only enable specific optimizations. In case of live-range reordering, the Pluto algorithm is still used with the scalar dependencies to determine bands (sets of perfectly nested loops). Live-ranges are then used to determine whether these bands are tileable or even parallel. They are if the life ranges are restricted to the band's body. This means that with this algorithm Listing 1 has a tileable band of two loops while for Listings 2 to 4 the two loops that cannot be combined into a band.

A conflict set as presented in [START_REF] Somashekaracharya | SMO: An Integrated Approach to Intra-Array and Inter-Array Storage Optimization[END_REF][START_REF] Darte | Extended Lattice-Based Memory Allocation[END_REF] can be useful to determine whether a scalar is conflicting with an array (Listing 6 line 13). For the purpose of DeLICM we additionally need to analyze the stored content. One participant of the conflict set is always a scalar such that a full-array conflict set is not needed.

Conclusion

This paper presented two algorithms to reduce the number of scalar dependencies that are typically the result of scalar mid-end optimizations such as Loop-Invariant Code Motion, but also appear in hand-written source code. We use DeLICM as an umbrella name for two algorithms. The first algorithm handles the more complicated case of register promotion, where an array element is represented as scalars during a loop execution. The approach is to map the scalar to unused memory locations. This problem is akin to register allocation, with mapping targets being array elements instead of processor registers -an NP-complete problem [START_REF] Chaitin | Register Allocation via Coloring[END_REF]. We employ a greedy strategy which works well in practice. The second algorithm implements operand tree forwarding. It copies side-effect-free operations to the statements where their result is needed or reloads values from array elements that are known to contain the same value.

We implemented both algorithms in Polly, a polyhedral optimizer for the LLVM intermediate representation. The experiments have shown that DeLICM can remove almost all avoidable scalar dependencies. Thanks to this effort, it also becomes worthwhile to execute Polly after LLVM's IR normalization and inlining, allowing, for instance, polyhedral optimization of C++ code with templates. The experiment of the currently checked-out branch is executed using: $ python3 ./gittool.py execjob This will execute the command in the Exec: line, then commit the result to a new branch that is prefixed with the host machine's hostname.

To extract measurements, the script execcmp.py can read the results from a result branch. For instance, the command $ ./execcmp.py leone_A10_nopolly prints the execution time of each benchmark of experiment "A10_nopolly" executed on the machine "leone" (The machine used for our evaluations, http://www.cscs.ch/computers/monte_leone/index.html). The command $ ./execcmp.py leone_A10_nopolly vs leone_A20_polly compares the execution times of the benchmarks with and woutput Polly.

More details about the experiment execution system can be found in the README.md in the master branch of the cgo18 repository. The system also includes a command to create new experiments from scratch and a buildbot component that queues and executes jobs but are not necessary to reproduce the results.

A.8 Notes

The git sha1 hashes allow to uniquely identify each experiment and benchmark result. The data for this paper were taken from experiments with the hashes shown in Table 4.

Listing 1 .

 1 [i] += A[i] * B[k];} Running example: sums-of-products.

Listing 3 .

 3 double a; for (int i = 0; i < N; i += 1) { T: C[i] = 0; a = A[i]; for (int k = 0; k < K; k += 1) S: C[i] += a * B[k]; } Listing 2. Sum-of-products after hoisting the load of A[i]. double c; for (int i = 0; i < N; i += 1) { T: c = 0; for (int k = 0; k < K; k += 1) S: c += A[i] * B[k]; U: C[i] = c; } Sum-of-products after promotion of C[i] to a scalar. double c; for (int i = 0; i < N; i += 1) { T: c = 0; for (int k = 0; k < K; k += 1) S: C[i] = (c += A[i] * B[k]); } Listing 4. Sum-of-products after partial promotion of C[i].

Figure 3 .

 3 Figure 3. Reaching definition and known contents of C.

Figure 4 .

 4 Figure 4. Lifetimes and unused zone of array elements C[0], C[1] and C[2].

Figure 5 .Figure 6 .

 56 Figure 5. Coalesced memory of c and C[2].

1 Knowledge

 1 (s); 12 Proposal = mapKnowledge(Candidate, t); 13 if (isConflicting(Knowledge, Proposal)) 14 continue; 15 WriteStmts = { w.Parent | w ∈ WritesTo(s) }; 16 for (a : ReadsTo(s) ∪ WritesTo(s))

22 } 6 .

 226 Listing Greedy scalar mapping algorithm.

Listing 8 . 4 if (s is not speculatable) 5 return false; 6 for 10 } 9 . 1 void 10 } 10 .

 845610911010 double a, a_S; for (int i = 0; i < N; i += 1) { T: C[i] = 0; a = A[i]; for (int k = 0; k < K; k += 1) { S: a_S = A[i]; C[i] += a_S * B[k]; } } Operand tree forwarding applied on sum-ofproducts (Listing 2). 1 bool canForwardTree(Target, s, Knowledge) { 2 e = Knowledge.findSameContent(s, Target); 3 if (e) return true; (op : operands(s)) 7 if (!canForwardTree(Target, op, Knowledge)) Listing Determine whether an operand tree is forwardable. doForwardTree(Target, s, Knowledge) { 2 e = Knowledge.findSameContent(s, Target);Listing Replicate an operand tree to TargetStmt.

Figure 7 .

 7 Figure 7. Position of the Polly polyhedral optimizer in the LLVM pass pipeline.

  pred1: br label %basicblock ; write 0.0 to %v.phiops pred2: br label %basicblock ; write 1.0 to %v.phiops basic_block: ; read from %v.phiops %v = phi float [0.0, %pred1], [1.0, %pred2]

c o r r e l a t i o n c o v a r i a n cFigure 8 .

 8 Figure 8. Speedups relative to clang without Polly (-O3) using median execution times. Each experiment ran 5 times, with all median absolute deviations being less than %2 of the median. DeLICM is able to recover the original performance at late position in most cases.

Table 2 .

 2 Number of scalar writes in loops before and after DeLICM. Each cell shows the number of SSA-scalar plus the number of φ write accesses. "Post-Opts" are additional postscheduling optimizations that can be applied with DeLICM compared to without it. The first is the number of additional tiled loops and the number in parentheses the number of additional optimized matrix-multiplications.

			early			late
	Benchmark	before	DeLICM	Post-Opts	before	DeLICM	Post-Opts

Table 4 .

 4 Hashes (first 6 digits) to the commits describing an experiment and the hashes resulting from the execution on Monte Leone.

	Branch	Experiment "leone"
	A10_nopolly	88faaff	98fafc2
	A20_polly	905f739	895c01f
	A30_polly_early	9274722	a7d8e2d
	A40_polly_late	27c0354	3cd76a7
	A50_polly_early_delicm	fbf19b5	1830678
	master	87eb3a

Acknowledgments

The authors would like to thank Johannes Doerfert for his suggestions, ARM for support in the context of Polly Labs, and the LLVM community for providing a research environment.

A Artifact Appendix A.1 Abstract

The artifact consists of a Github repository where each branch represents an experiment. The branches contain the Polly source code (unmodified, since all required changes have been upstreamed), and a script that compiles LLVM with Polly and runs the experiments.

In addition, we provide the experimental results used for evaluation (Section 5) and a script to extract and compare results.

A.2 Artifact Check-List (Meta-Information) The precompiled experiments were compiled for/on Red Hat Enterprise Linux Server 6.7 x86_64 (Intel Haswell) and may or may not work on different platforms. For optimal results, we recommend recompiling for each platform.

A.3.3 Software Dependencies

All requirements needed to compile LLVM, see llvm.org/docs/GettingStarted.html#software. In addition, the

A.4 Installation

No installation required.

A.5 Experiment Workflow

The script cgo.py provided in the master branch of the cgo18 repository performs the check-out of LLVM, compilation, benchmark execution and evaluation of the measurements. To run, execute: $ cd cgo18 $ python3 ./cgo.py 2>&1 | tee log.txt This process may take around 21 hours to execute and consumes about 7 GB of disk space. The script prints results in-between other output, so the log.txt might be helpful.

A.6 Evaluation and Expected Result

The cgo.py script will print the following information to the console:

• Comparison of the obtained results to our results ("leone").

• Number of transformations as in Table 1.

• Number of scalar dependencies and post-scheduling transformations as in Table 2. • Speed-ups as in Figure 8.

A.7 Experiment Customization

The cgo.py script calls two other scripts to compile and run the benchmarks (gittool.py) and extract the results (execcmp.py). These commands can also be invoked manually.

Each experiment is described by a branch in the repository with a line starting with Exec: describing the experiment to execute. The predefined experiments are shown in Table 3.

An experiment can be modified by changing the Exec: in the commit message of the branches latest commit. We recommend creating a new branch for each new experiment. The available options can be seen using: $ python3 ./gittool.py runtest --help The source code of Polly, and the script being executed (run-test-suite.py) are as well part of the commit, such that these can be modified as well., e.g. to test modifications to the compiler that are not exposed via a command-line switch.


Mohamed Khemakhem
email: mohamed.khemakhem@inria.frcarmen.brando@ehess.fr

Carmen Brando

Laurent Romary
email: laurent.romary@inria.frfrederique.melanie@ens.fr

Frédérique Mélanie-Becquet

Jean-Luc Pinol
email: jean-luc.pinol@ens-lyon.fr

Fueling Time Machine: Information Extraction from Retro-Digitised Address Directories

Whereas mapping systems, such as Google Maps or Bing, have become nowadays the common tools to geocode addresses or to browse neighborhoods on modern maps, browsing a legacy map representing a geographical snapshot of historical cities is far from being accomplished. The issue is related in the first place to the lack of data allowing a system to map a given address to a throwback location. Such information are abundantly available in dedicated paper resources, such as legacy address directories 1 . But even digitised, mining the content of these resources remains limited due to the adhoc employed information extraction techniques. Time machine2 is a major large scale project aiming to bridge this gap, among many others, by analysing and valorising the content of legacy documents for the ultimate purpose of redrawing the historical, social and economical heritage of Europe. In this context, we present our approach and first results of a state-of-the-art technique for extracting information from digitised address directories.

Our labour has been motivated by two emerging factors. First, the public release of several digitised versions in high-definition from the legacy address directories "Annuaires-almanach" of Paris, made available by the French National Library3 . The directory series, which had been edited since the 18th century, carry a joint description of the commercial activities and postal information of the french capital. Second, a recently implemented approach by [START_REF] Khemakhem | Automatic Extraction of TEI Structures in Digitized Lexical Resources using Conditional Random Fields[END_REF][START_REF] Khemakhem | Enhancing Usability for Automatically Structuring Digitised Dictionaries[END_REF] has given an information extraction system, GROBID-Dictionaries, which has been designed to structure digitised dictionaric resources by using machine learning models. We have been struck by the similarities in the structures of dictionaries and address directories, where both resources share a semasiological representation. In fact, the latters could be perceived as encyclopedic resource where locations are described as unique concepts.

We have used Text Encoding Initiative (TEI) as a common modeling standard and proposed a first encoding of entries in an address directory. We distinguish between two categories of entries (see table 1). The first is reserved for each entry describing a single occupant in a unique or a shared address. In other terms, to each number in a street, one or many occupants could be assigned and for each one of them corresponds an entry. The second category of entries gathers the description blocs of a common street. An entry in this case encapsulates information like the name of the street, length, neighbouring street, etc. St-Germain-des-Prés). <-rue de l'Echaudé, 18.-►rue St-Beno!t, 11</sense> </entry> The current architecture of GROBID-Dictionaries, based on cascading machine learning models, has been to a large extent able to support the presented encoding of the textual information and extract the macro structures. In fact, first level of segmentation has the mission to differentiate between the different parts of a digitised page. The second level relies on a model for segmenting a page body to entries which will be further segmented in the third level to main semantic blocks. Despite sometimes the noisy OCRised data (see table 1), till the third level, the only required adaptation of the system has been the implementation of a new label to mark the numbering of entries <num>. After this minor adaptation, a first experimentation of the system has shown interesting results for the first 3 segmentation levels, which we report in table 2. Although the models had given better results with dictionaries in previous experimentations, the current results are still considered impressive given the different nature of the address directories and the noise in the OCRs, especially for the first model. The outcome should be improved as soon as we annotate more data and further strengthen the selected features, if needed. To reach the complete encoding presented in table 1, we are investigating the creation of new models to be integrated in the existing architecture for processing the clusters of texts labels. Before considering building new models trained from scratch, the integration of models used for the same purpose in the GROBID 5 family projects is likely to be the most efficient solution, such for the parsing of addresses and person names. We are considering also to improve the OCRs for known entries such as the majority of street names, which could be checked against existing defined lists.

Model

In conclusion, a Time machine with structured information extracted from legacy address directories seems not to be an issue anymore thanks to the availability of the target digitised material and the advanced extraction techniques embedded in GROBID-Dictionaries. The existing architecture of the tool could be further improved by annotating more data, plugging in existing models or creating new ones to be applied in larger scale or on similar documents in other languages. Finally, our aim is to further retrodigitise releases of the Annuaires-almanach and geocode historical postal addresses listed there thereby to analyse commercial activity in old Paris taken from large amounts of historical sources as introduced by Kaplan et al. 2017.

  <pc>,</pc> <lbl>et</lbl> <address>pl. Péreire, 1.</address> </sense> </entry> <entry> <form>ABBAYE (rue de V)</form> <sense>(230" de longueur) (Ancienne abbaye de St-Germain-des-Prés) 6* Arr. (Luxembodrg).

Table 1 :

 1 Both images in lines 2 and 3 correspond respectively to excerpts of pages 3500 and 2882 of the 1901 release 4 of the annuaires-almanach

Historical maps are evidently an important source of geolocalised information, our proposed approach aims to be complementary to well-known methods for georeferencing old maps and thus deals with a new kind of historical source.

http://timemachineproject.eu

http://gallica.bnf.fr/ark:/12148/cb32695639f/date

http://gallica.bnf.fr/ark:/12148/bpt6k9763088f

https://github.com/kermitt2