Prashant Singh

Aravind Sukumaran-Rajam
email: sukumaranrajam.1@osu.edu

Atanas Rountev
email: rountev.1@osu.edu

Fabrice Rastello
email: fabrice.rastello@inria.fr

Louis-Noël Pouchet
email: pouchet@colostate.edu

P Sadayappan
email: sadayappan.1@osu.edu

Associative Instruction Reordering to Alleviate Register Pressure

Keywords: Compilers, register pressure, associative reordering, domain-specific optimization

Register allocation is generally considered a practically solved problem. For most applications, the register allocation strategies in production compilers are very effective in controlling the number of loads/stores and register spills. However, existing register allocation strategies are not effective and result in excessive register spilling for computation patterns with a high degree of many-to-many data reuse, e.g., high-order stencils and tensor contractions. We develop a source-to-source instruction reordering strategy that exploits the flexibility of reordering associative operations to alleviate register pressure. The developed transformation module implements an adaptable strategy that can appropriately control the degree of instructionlevel parallelism, while relieving register pressure. The effectiveness of the approach is demonstrated through experimental results using multiple production compilers (GCC, Clang/LLVM) and target platforms (Intel Xeon Phi, and Intel x86 multi-core).

I. INTRODUCTION

As we approach the end of Moore's law scaling, there will be increasing emphasis on maximizing single-node efficiency, in addition to achieving good scalability across the nodes of a supercomputer. Compilers play a very critical role in enabling high performance and efficiency within a node. In this paper, we revisit a compiler problem that is generally considered to be solved for all practical purposes: register allocation. For most programs, the register allocation and instruction scheduling strategies in production compilers are very satisfactory, and the number of register spills is well controlled. However, this is not the case for many compute-intensive array-based applications in computational science and machine-learning/datascience that feature multiple inter-related reuses. With such computations, a number of variables in a basic block of instructions exhibit many coupled reuses, with different groups of instructions referencing different combinations of the set of reused variables. As clearly demonstrated with quantitative data later in the paper, existing register management strategies in production compilers are unable to effectively control the number of register spills for such computations. These manyto-many reuse patterns typically involve associative accumulation of multiple contributions into destination variables. In this paper, we develop an effective instruction reordering strategy that exploits the flexibility offered by associative operations. We demonstrate significant alleviation of register pressure and spilling, and corresponding enhancement of performance.

We use a high-order "box" stencil computation to elaborate on the addressed problem. First, let us consider a simple 2D 9-point Jacobi computation: for(i=1;i<N-1;i++) for(j=1;j<N-1;j++)

A[i][j] = c * (B[i-1][j-1] + B[i-1][j] + B[i-1][j+1] + B[i][j-1] + B[i][j] + B[i][j+1] + B[i+1][j-1] + B[i+1][j] + B[i+1][j+1]);
For computing each element A[i][j], the corresponding element B[i][j] and all 8 neighboring elements are read. For two adjacent result elements, A[i][j] and A[i][j + 1], six of the needed elements from B are common. By explicitly unrolling the inner j loop, these potential reuses are exposed in the resulting basic block of code in the unrolled loop. However, for a 4-way unrolled version of an 81-point convolution stencil, with GCC-7.2.0 as the base compiler on an Intel i7-6700K processor, we observe the number of memory accesses per iteration increases from 269 to 664 in the generated assembly code, and the performance drops from 72 GFLOPS to 70 GFLOPS when going from the original non-unrolled form to the unrolled version.

For such high-order stencils, the problem has been recognized in prior work and a solution provided: exploit associativity to reorder operations and create a different equivalent stencil pattern [START_REF] Stock | A framework for enhancing data reuse via associative reordering[END_REF]. With this changed access pattern, it has been shown [START_REF] Stock | A framework for enhancing data reuse via associative reordering[END_REF] that the maximum number of concurrently live registers reduces from O(k 2 ) to just O(k) for an orderk box stencil. Rearranging the contributions for the 81-point convolution stencil, such that the contribution from an input value is "scattered" to different output points, brings down the memory accesses per iteration in the unrolled code to 206, and the performance increases from 70 GFLOPS to 137 GFLOPS.

In this paper we develop a general solution for the associative reordering problem, without using any specialized abstractions such as stencil patterns as was used by Stock et al. [START_REF] Stock | A framework for enhancing data reuse via associative reordering[END_REF]. We devise an instruction reordering strategy that simul-taneously considers the flexibility with associative reordering of accumulations and the impact of instruction order on the maximum number of live values.

We develop a List-based Adaptive Register-reuse-driven Scheduler (LARS) that uses multiple criteria, including affinities of non-live variables to those live in registers, as well as potentials of variables to fire operations and to release registers. We chose to implement the instruction scheduler as a source-to-source pass outside the compiler, to be executed before the standard compiler passes. By doing so, we are able to evaluate its impact with two production compilers, LLVM and GCC. We present experimental results on a large collection of benchmarks that exhibit significant potential register-level reuse for array elements. We demonstrate significant benefits from the use of LARS.

The paper makes the following contributions:

• It develops a framework to reduce register pressure by exploiting the flexibility of associative reordering for computational kernels with multiple inter-related reuses. • It develops a flexible multi-criteria instruction reordering heuristic that can be adapted across architectures. • It demonstrates the effectiveness of the proposed framework for a number of scientific kernels when compiled with different compilers and on multiple architectures.

II. BACKGROUND AND MOTIVATION

Register Allocation and Instruction Scheduling: Register allocation assigns physical registers to the variables used in the intermediate representation (IR). All variables that are live at a given program point must be assigned to distinct registers if register spills are to be avoided. We denote as MAXLIVE the maximum number of variables that are simultaneously live at any program point through the execution of the program. A data reuse refers to multiple accesses to the same variable. Spill instructions are generated when the allocator runs out of physical registers: some registers are freed after their contents are stored into memory or simply discarded. The spilled contents must be reloaded into registers before their subsequent use. Since memory accesses have high latency, minimizing spills is important for performance.

Several techniques have been proposed to perform register allocation. Most compilers use versions of graph coloring [START_REF] Chaitin | Register allocation & spilling via graph coloring[END_REF] or linear scan [START_REF] Poletto | Linear scan register allocation[END_REF]. Both these techniques perform register allocation on a fixed instruction schedule that is obtained after performing instruction scheduling on the IR. The instruction scheduler orders the instructions to minimize the schedule length and simultaneously increase the instruction-level parallelism (ILP), so that the functional units and pipelines of the underlying processor are effectively utilized. Clearly, the objectives of instruction scheduling and register allocation can be antagonistic: instruction scheduling may prefer independent instructions scheduled in proximity to increase ILP, whereas register allocation may prefer data-dependent instructions to be scheduled in proximity to shorten the live ranges. This problem is more pronounced for applications that exhibit complex, many-to-many data reuse pattern: the instruction scheduler Listing 1: Unrolled input 1 for (int j=2; j<N-2; j++) 2 for (int i=2; i<N-2; i++) {

3 A[j][i] = a * B[j-2][i] + b * B[j-1][i] + c * B[j][i] + 4 d * B[j+1][i] + B[j][i] * B[j+2][i]; 5 A[j+1][i] = p * B[j-1][i] + q * B[j][i] + r * B[j+1][i] + 6 s * B[j+2][i] + B[j+1][i] * B[j+3][i]; 7 }
Listing 2: A reordering that leverages associativity of + 1 for (int j=2; j<N-2; j++)

2 for (int i=2; i<N-2; i++) { 3 A[j][i] = a * B[j-2][i]; 4 A[j][i] += c * B[j][i] + B[j][i] * B[j+2][i]; 5 A[j+1][i] = s * B[j+2][i] + q * B[j][i]; 6 A[j][i] += b * B[j-1][i] + d * B[j+1][i]; 7 A[j+1][i] += p * B[j-1][i] + r * B[j+1][i]; 8 A[j+1][i] += B[j+1][i] * B[j+3][i]; 9 }
does not consider the reuse pattern while generating the initial instruction ordering, resulting in increased live ranges for variables.

Associative Instruction Reordering: Sometimes, a better instruction reordering can be achieved if one leverages associativity of operations. Although floating-point additions are not strictly associative, it is generally acceptable to perform associative reordering of accumulations in most applications that do not rely on rounding behavior. In fact, many scientific computations are compiled using -ffast-math flag [START_REF]Semantics of Floating Point Math in GCC[END_REF], which allows a compiler to exploit associativity of floating-point operations to improve performance at the expense of IEEE compliance. Many recent efforts have leveraged operator associativity to drive code optimization strategies [START_REF] Stock | A framework for enhancing data reuse via associative reordering[END_REF], [START_REF] Basu | Compiler-directed transformation for higher-order stencils[END_REF], [START_REF] Suriana | Parallel associative reductions in halide[END_REF].

Consider the input program of Listing 1. The two statements read from four common input values. If the computation of the first statement entirely precedes the second statement, then these four values must be kept alive in registers. However, one can leverage the associativity of addition to reorder the computation as shown in Listing 2. In the reordered computation, the evaluation of the two output points is interleaved, so that all the uses of an input value are brought closer, and consequently, its live range is shortened. However, most production compilers perform instruction scheduling and register allocation on an IR like Register Transfer Language (RTL), which is low-level, and much closer to the machine mnemonics. Most compiler frontends operate on one or more high-level IRs. For example, GCC has two high-level IRs: GIMPLE and Static Single Assignment (SSA). GIMPLE is closer in spirit to the input, and captures operator associativity naturally. When GIMPLE is lowered to SSA, the accumulation operations are converted to a use-def chain of contributions. SSA is further lowered to RTL by applying a sequence of intra and interprocedural optimizations. Leveraging operator associativity at RTL would involve lifting the complex RTL to a higher GIMPLElike abstraction that naturally expresses operator associativity, which is difficult. Therefore, most compilers fail to fully utilize operator associativity to relieve register pressure.

Solution Approach: Many prior efforts have studied the implications of phase ordering between register allocation

[k][j][i] = a * (in[k+1][j][i]) + b * (in[k][j-1][i] + in[k][j][i-1] + in[k][j][i] + in[k][j][i+1] + in[k][j+1][i]) + c * (in[k-1][j][i]); 10 #pragma dsl end 11 } 12 }
and instruction scheduling on the generated code [START_REF] Pinter | Register allocation with instruction scheduling[END_REF], [START_REF] Norris | A scheduler-sensitive global register allocator[END_REF], [START_REF] Berson | Integrated instruction scheduling and register allocation techniques[END_REF]. These works proposed integrated register allocation and instruction scheduler for VLIW or in-order issue superscalar processors. However, none of these approaches leverage properties of the operators involved in the computations to improve the instruction reordering. We show in Section IV that for many scientific applications executed on out-of-order (OoO) processors, register spills are a performance bottleneck. To this end, we propose LARS (List-based, Adaptive, Register-reusedriven Scheduler)-a greedy instruction reordering framework for straight-line code, that a) operates at source level to fully exploit the associativity of operations, b) has a much better global perspective of the computational reuse pattern, and c) reorders the instructions minimize MAXLIVE.

III. INSTRUCTION REORDERING WITH LARS

A. Preprocessing Steps

LARS parses statements within a computational loop nest that are expressed in a subset of C with the following restrictions: (1) the loop iterators and the program parameters must be immutable in the statements; (2) the right-hand side expression of a statement must be side-effect free; and (3) the array index expressions in each statement must be an affine function of the loop iterators, program parameters, and literals. Listing 3 shows an example of preparing an input C code for reordering using LARS. LARS currently uses a pragma-based approach, where the straight-line code of interest is demarcated using dsl pragmas. All the auxiliary information is supplied as arguments to the dsl pragma. This makes it convenient to use LARS with domain-specific languages that are similar in flavor to C/C++ [START_REF] Rawat | Resource conscious reuse-driven tiling for GPUs[END_REF]. Lines 6 and 10 mark the beginning and end, respectively, of the optimization region. The arguments in line 6 indicate that i , j , and k are the loop iterators, and that the demarcated statements need to be unrolled by an unrolling factor of 2 along the dimensions corresponding to iterators k and j .

A preprocessing pass performs loop unrolling by the specified unrolling factors, and then lowers each statement in the optimization region into a sequence of instructions using operator associativity and/or distributivity. The instructions are somewhat similar in spirit to the three-address GIMPLE IR of GCC, where the right-hand side of an instruction has at most two operands, and the operator is either an assignment or an accumulation. In terms of assembly language, these instructions are synonymous with the register-register instructions (r 1 ← r 2 op r 3 where r 1 and r 2 /r 3 can be the same register).

Figure 1a shows an illustrative computation which is lowered into the instructions shown in Figure 1b using the associativity and distributivity of + and * . Note that even though all the operands in the illustrative example are scalars, in practice, the operands can be a mix of array accesses, scalars, and literals. An abstraction commonly used to represent such computations is a computational DAG (CDAG) [START_REF] Goodman | Code scheduling and register allocation in large basic blocks[END_REF], [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF], where the leaf nodes represent the storage locations read, the root represents the output, and the internal nodes represent the operators. For example, Figure 1c shows the CDAG corresponding to the computation of Figure 1b, whereas Figure 1d shows the CDAG corresponding to the instructions after converting the additive contributions in the original DAG to accumulations, represented in the figure by orange "accumulation +" nodes. Throughout the text, we will shift from an instruction sequence to its CDAG abstraction for ease of explanation.

In order to reduce register pressure, LARS must gauge the data reuse between the instructions in the original schedule. To recognize the common uses of a value, the accessed storage locations are assigned a label. All the accesses to the same storage location within a statement will have the same label. Across statements, the accesses to a storage location M will be identified by the same label if there is no write to M in between their execution.

B. Creating Multiple Initial Schedules

The time taken to reorder instructions is significantly lower with a greedy heuristic than with techniques like dynamic programming [START_REF] Gan | Scaling and analyzing the stencil performance on multi-core and many-core architectures[END_REF] or integer linear programming [START_REF] Chang | Using integer linear programming for instruction scheduling and register allocation in multiissue processors[END_REF]. We use this to our advantage, by reordering multiple versions of the input program instead of just one, and choosing the reordering with the best performance.

Figure 2 shows the expression tree of two statements, the register requirement for which can be computed by the classic Sethi-Ullman algorithm [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF]. The numbers next to each node in Figure 2 shows the number of registers required to evaluate that node. There can be two evaluation scenarios:

(1) evaluating S 1 before S 2 will require 4 registers, since the 3 registers released after evaluating S 1 can be used to entirely evaluate S 2 ; (2) evaluating S 2 before S 1 will require 5 registers, since one register will be engaged in holding the result of S 2 . This simple example demonstrates that if one rewrites the pragma-demarcated computation as different dependence-preserving permutations of input statements, each permutation can possibly produce a reordering schedule with a different register requirement. Determining the best statement permutations becomes more complicated with an increase in the number of statements, and inter-statement data reuse [START_REF] Aho | Code generation for expressions with common subexpressions[END_REF]. For example, each statement of Figure 3, in isolation, would require 3 registers for evaluation: 2 to store the operands, and one to store the result. A register assignment when evaluating the statements in the order shown in Figure 3

is {a → r 1 , b → r 2 , u → r 3 , e → r 4 , v → r 1 , g → r 4 , w → r 2 , c → r 4 , d → r 5 , x → r 6 }.
However, the permutations that evaluate S 4 first will yield more register-optimal schedules than other permutations. One possible register assignment when S 4 is evaluated first is

{c → r 1 , d → r 2 , x → r 3 , a → r 1 , b → r 2 , u → r 4 , e → r 5 , v → r 1 , g → r 5 , w → r 2 }, which uses 5 registers instead of 6.
In such situations, a brute-force approach to determine the best permutation will examine all dependence-preserving permutations of the input statements, and apply LARS to each permutation. However, for a program with n independent statements, this would imply exploring n! statement sequences, a formidable task as n increases [START_REF] Aho | Code generation for expressions with common subexpressions[END_REF]. Instead, we use the simple clustering algorithm from [START_REF] Rawat | Register optimizations for stencils on GPUs[END_REF] to generate a few different permutations that cluster the statements with reuses together, and then apply LARS to only these few statement permutations. Once we have the permutations, we choose one permutation at a time, apply the preprocessing step described in Section III-A to it, and then use LARS to reorder the version. The final reordered version is the one that is more efficient in execution. For the rest of the discussion, we will assume that the input to LARS is a valid permutation P .

C. Overview of the Reordering Strategy

Given the initial schedule P , the main objective of LARS is to compute a reordered schedule that preserves the dependences, and reduces register pressure while maintaining sufficient ILP. We use the initial schedule of Figure 1b as an example to give a brief overview of the reordering strategy implemented in LARS. Prior to reordering, we construct a dependence graph (DG) for the initial schedule. Since we allow the contributions to an accumulation node to be in arbitrary order, we do not include the true/output dependences on the accumulation node in DG. Figure 1e shows the dependence graph for the schedule of Figure 1b.

Next, we compute the labels occurring in the initial schedule. Figure 4a shows the mapping from the labels to the instructions in which they appear. We maintain a set L of labels that are currently live in pseudo registers, assuming a spill-free1 model of computation. An instruction I j in the schedule can fall in one of the following three categories: -Blocked: If I j has a true dependence on another instruction I k in the DG, and I k has not yet been fired -Unblocked: If I j is not blocked -Fireable: If I j is unblocked, and all the labels of I j are in L. Initially, only the instructions with no incoming dependence edges in DG are unblocked (i.e., instructions 1, 2, 3, 4, 6, 7, and 8 in the schedule of Figure 1b), and none of the labels are live. In a nutshell, the reordering algorithm can be summed up as two iterative steps: make the labels live in some order, so that instructions become fireable (Section III-E), and append the fired instructions into the final reordered schedule (Section III-D). The objective is to minimize the size of L at any given point, since the live range of labels simultaneously live in L are in interference. At the same time, there must be sufficient ILP to tolerate the access/execution latency. The order in which the labels are made live and the fired instructions are appended to the reordered schedule will affect the register pressure and ILP; the heuristic used to determine this order is explained in greater details in this section.

1) Reordering the computational DAG of Figure 1b: In order to determine the first seed label that becomes live, we compute an initial priority metric for each label; the computation is described in details in Section III-E1. Simply Fig. 4: Applying LARS reordering strategy to the input of Figure 1b. The digits next to a label are color-coded, and represent metrics that are explained in Section III-E2. green digit: number of non-live labels the label interacts with, red digit: cumulative primary affinity, orange digit: fire potential, blue digit: release potential.

put, the labels occurring in instructions that are closer to the source of the longest (critical) path in the CDAG are assigned a higher initial priority. This is done so that the source instructions in the critical paths are not unnecessarily delayed, resulting in longer schedule length. This also conforms to the priority assignment in the instruction scheduling phase of most production compilers, like GCC. For example, the critical path in the schedule of Figure 1b involves accumulations into a.

Since division operation has the highest latency, we assign high initial priority to labels {a,b,c,d,f }. Among these, LARS chooses b as the seed label, since it interacts with the least number of non-live labels (Figure 4b); the rationale behind this choice is discussed in Section III-E2. Once a label is made live, we check if any unblocked instruction becomes fireable. If so, the algorithm fires/executes it, and appends it to the final reordered schedule. Otherwise, a cost tuple t 1 , t 2 , . . . , t k is constructed for each non-live label, the elements of which represent the interaction of the label with the already-live labels, and the effect of making that label live on the current unblocked statements. Element t i has higher priority than t j if t i appears before t j in the tuple. t i (T ) denotes the value of element t i in the cost tuple T . Similarly, t i (l) denotes the value of element t i in the cost tuple of label l. Cost tuple comparison is based on the lexicographical ordering, i.e., for two tuples T a and T b ,

T a > T b ⇔ k ∃ i=1 ( i-1 ∀ j=1 (t j (T a ) = t j (T b )) ∧ t i (T a ) > t i (T b ))
Section III-E2 describes the cost tuple in detail. The labels with most profitable (i.e., greatest) cost tuple are assigned highest priority, and are iteratively made live till one or more of the unblocked instructions becomes fireable. In our example, none of the unblocked instructions become fireable when the seed label b is made live, and more labels need to be made live in order to fire any instruction. Figure 4b shows the interaction between the live label b, and the non-live labels {a,c,e} that appear with b in instructions {2,3}, i.e., their live range interferes with b. This interaction is captured by one of the elements, say t p , in the cost tuple: t p (a) = 2 since the live range of a interferes with b in two instructions, whereas t p (c) = t p (e) = 1, since the live ranges of c and e interfere with b in only one instruction. Other elements in all the cost tuples being equal, labels a,c,e will have higher priority over other non-live labels due to t p , and consequently one of these three labels will be added to the live set next; LARS picks a to be added to the live set, since t p (a) > t p (c,e).

Once a is live, instruction 2 can become fireable if c is made live next. When recomputing the cost tuple for the non-live labels, this firing potential of c is accounted for in its cost tuple by one of the elements, say t f . Element t f is positioned in the cost tuple so that it has higher priority than t p , giving c higher priority over other non-live labels. Therefore c is made live next, and instruction 2 is fired (Figure 4c). At this point, making either label d or e live will result in the firing of exactly one instruction. LARS prioritizes making e live, since it interacts with fewer non-live labels. Note that by doing so, LARS has separated the live range of b from that of d.

Once the computation reaches the state of Figure 4d, making label q live will enable firing of instruction 8. Instruction 8 has the last uses of labels f and e: once fired, the pseudoregister assigned to these two labels can be reused to store other labels. This release potential of q is accounted for by an element in its cost tuple, say, t r . Element t r is assigned higher priority than t f in the cost tuple. This results in q getting higher priority over other non-live labels, and becoming live in the next step (Figure 4e). When a label is released, its live range is separated from the non-live labels. LARS thus uses cost tuples to effectively manage the live set so that the live set size (and consequently the live range interference) is reduced.

After an instruction is fired, its dependence edges are removed from DG, which can possibly unblock some instructions. The cost tuple for each non-live label is recomputed with a change in the set of live labels, or the set of unblocked statements. The algorithm terminates when all instructions in the initial schedule have been fired. The final reordered schedule is then printed out using appropriate intrinsics for multi-core CPUs. Algorithm 1 sketches out the high-level reordering algorithm.

D. Adding Instructions to Reordered Schedule

We say that an instruction I a interlocks with a previously fired instruction I b , if there is a true dependence from I b to I a , or both I b and I a contribute to the same accumulator [START_REF] Goodman | Code scheduling and register allocation in large basic blocks[END_REF]. At any step, if there are several fireable instructions, priority is given to the one that has minimum interlocks with the recently scheduled instructions. For example, at the stage of Figure 4e, if t1 and g are made live, instructions 5 and 6 become fireable simultaneously. However, the previously fired instruction 4 interlocks with 5 on label a. Therefore, 6 is scheduled before 5 (Figure 5a). If all fireable instructions have the same degree of interlock, we fire them in their order in the original schedule. This provides the scheduling phase of the backend compiler with opportunities to exploit ILP [START_REF] Goodman | Code scheduling and register allocation in large basic blocks[END_REF].

If instructions I a and I b interlock due to the same accumulation output, we can resolve the interlock by register renaming [START_REF] Smith | Implementing precise interrupts in pipelined processors[END_REF], a technique often used by both compilers and the hardware to remove false dependences and improve ILP. When firing the instruction I a , we check if it interlocks due to the accumulation output with any of the k previously fired instructions, where k is a code generator parameter, which we term interlock window size. If it does, then we replace the accumulator in I a with its shadow, which will act as a partial accumulator. The shadow accumulator is appropriately initialized to the identity of the accumulation operator (e.g., 0 for addition/subtraction, 1 for multiplication), and its value will be added to the actual accumulator before the subsequent use of the accumulation output. There will be at most k shadows per accumulator, after which they will be cyclically reused. By register renaming, we remove the dependence between instructions that are less that k hops apart in the final schedule, thereby improving ILP. For example, in the reordered schedule of Figure 5a, the true dependences due to the accumulation output a in instructions 1-4 limits the achieved ILP. We can increase ILP by creating a shadow accumulator a1, and collecting partial accumulations from alternate instructions into it, as shown in Figure 5b. The partial contribution from the shadow a1 is added to a before its subsequent use in instruction 6.

E. Adding Labels to Live Set

1) Assigning initial priority to labels: No labels are initially live. To start the reordering, we have to choose the first nonlive seed label, and make it live. In order to determine the seed label, we assign an initial priority to all labels. This priority is based on the concept of earliest starting time. For each instruction n in the initial schedule, the earliest starting time, EST (n), can be computed based on the pipeline latencies of the underlying architecture [START_REF] Sarkar | Register-sensitive selection, duplication, and sequencing of instructions[END_REF]. where p i is the i th predecessor of n in DG, and latency(p i ) is the latency of the dependence edge from p i to n.

EST (n) = max i (EST (p i ) + latency(p i )) (1
A source in the DG is a node with no predecessors, and a sink is a node with no successors. For a path p in DG starting at source node n s and ending at sink node n t , we define the path execution time, PET (p) = EST (n t ). A critical path in DG corresponding to V is defined as the source-to-sink path with the highest PET . There can be more than one critical paths in the program. In most instruction scheduling algorithms, the first scheduled instruction (seed instruction) is the source instruction in the critical path [START_REF] Sarkar | Register-sensitive selection, duplication, and sequencing of instructions[END_REF], [START_REF] Goodman | Code scheduling and register allocation in large basic blocks[END_REF].

If an instruction n occurs in k source-to-sink paths {p 1 , p 2 , . . . , p k } in the DG, we can compute a cumulative cost for n, similar to the one defined in [START_REF] Goodman | Code scheduling and register allocation in large basic blocks[END_REF], as max 1≤r≤k (PET (p r )-EST (n)). Thus, the source in the critical path will have the highest cumulative cost, and the instructions closer to the source instruction in relatively longer paths in the DG will have higher cumulative costs than other instructions. The labels occurring in an instruction with higher cumulative cost must be assigned a higher priority, so that such instructions are scheduled with urgency. The initial priority P l of a label l is therefore set to max i {cumulative cost(n i )}, where n i represents all instructions in which label l appears.

2) Creating a cost tuple for each label: To model the profitability of making a non-live label l live, we capture its impact on the current set of unblocked instructions and its interaction with the live labels ∈ L using the following metrics: -Fire potential (F pot ): The fire potential of label l is the number of instructions that become fireable upon making l live. If there are k unblocked instructions that only need l to become live in order to become fireable, then the fire Algorithm 2: Create-Tuple (l, L, S ub )

Input : L: Set of live labels, l: a label ∈ L, S ub : Unblocked instructions Output: T : Cost tuple for l 1 Rpot ← 0; Fpot ← 0; N lk ← 0; 2 for each s ∈ S ub that becomes fireable when l ∈ L do 3 increment Fpot ; 4 for each t in L that has the last use in s do 5 increment Rpot ; 6 P l ← the label priority of l based on its initial priority, and the current leading statement; 7 N npaff ← number of labels ∈ L that have non-zero primary affinity with l; 8 P aff ← cumulative primary affinity of l to the labels ∈ L; 9 S aff ← cumulative secondary affinity of l to the labels ∈ L; 10 T ← Rpot , Fpot , P aff , S aff , -N npaff , P l ; 11 return T ; potential of l is k.

-Release potential (R pot ): The release potential of l refers to the number of labels that have their last uses in the instructions that become fireable when l is made live. -Cumulative Primary affinity (P aff ): Label l has primary affinity of strength p with an already live label t if both l and t occur simultaneously as the labels in exactly p instructions. The cumulative primary affinity of l is the sum of its primary affinity with all live labels. -Cumulative Secondary affinity (S aff ): Label l has secondary affinity of strength s with an already live label t if they both have a non-zero primary affinity with exactly s common labels. The cumulative secondary affinity of l is the sum of its secondary affinity with all live labels. Rationale: The release potential of a label reflects its ability to reduce register pressure directly. Therefore, the label with highest release potential must always be made live before others. Making a label with high fire potential live can provide the compiler with independent instructions to schedule. Also, even if the fired instructions do not release registers, they may still be a step in decreasing the remaining uses of their operands, and towards a consequent release of the registers occupied by their operands. If a label l has a non-zero primary affinity with an already-live label t, then the live range of l and t definitely interfere, and t cannot be released till l becomes live. Therefore, if label l has a high cumulative primary affinity with the already-live labels, then we eagerly make l live, so that we get a step closer to releasing l, and the labels it has primary affinity with. Similarly, if a label l has a non-zero secondary affinity with an already-live label t due to a label m, then the live ranges of both l and t will interfere with m. Making l live will shrink the live range of m and bring us one step closer to releasing m.

To help us determine the seed label, we had initialized the initial priority P l for each label based on the cumulative cost of the instructions. Multiple labels along disjoint critical paths could be initialized with the same priority if those paths have the same PET . However, when an instruction n is fired by LARS, the priority of the labels in the instructions dependent on n must be increased to favor depth-first traversal of the CDAG containing n. Otherwise, the instructions along different CDAGs may get unnecessarily interleaved, increasing the register pressure [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF]. Whenever an instruction is fired, the priority of each label is updated based on the current leading statement. A statement S i is currently leading if maximum number of the instructions that it was lowered down to have been fired. All the non-live labels occurring in the unblocked instructions corresponding to S i are assigned a higher P l than other non-live labels.

The primary affinity of a non-live label l to other non-live labels is also an important metric. Suppose the label l has a non-zero primary affinity with r non-live labels. Then, if l is made live at the current step, it needs to be live until all the r labels are live as well. For each label l, N npaff (l) denotes the number of non-live labels with which l has non-zero primary affinity. A label with higher N npaff must be penalized, as making it live may increase live-range interference in future.

The resultant combined metric for each label can be thought of as a 6-tuple: R pot , F pot , P aff , S aff , P l , -N npaff . The collection of tuples for all labels is then lexicographically sorted in descending order to rank-order the labels based on their profitability to be made live. The label that is deemed most profitable after the rank-ordering is chosen to be added to the set L. Algorithm 2 depicts the creation of the cost tuple.

F. Adaptivity in LARS

The relative order of the metrics in the tuple affects the reordering objective. For example, assigning the highest priority to R pot followed by P l would allow an interleaved execution of two statements only when the interleaving results in release of registers. This provides us the flexibility to define multiple sort functions, each acting as an objective function to determine the sequence in which the labels are added to set L. In the implementation, we choose the objective function based on the nature of the computation. For the computations where the intra-statement reuse is less than half the interstatement reuse (e.g., computation of Figure 6e), we order the metrics as R pot , F pot , P aff , S aff , -N npaff , P l . This facilitates interleaving across the statements to reduce register pressure. However, if the inter-statement reuse is less than onethird the intra-statement reuse, we order the metrics as R pot , P l , F pot , P aff , S aff , -N npaff , so that the interleaving across CDAGs is minimized.

G. Putting It All Together

Algorithm 3 recapitulates the broad steps applied by LARS to reorder an input program M . The unrolling factors are applied to M to obtain an unrolled version M . The dependence graph is then computed for M (line 4) using which, multiple permutations {V } of M are created (line 5). The reordering heuristic is then applied to each of these versions (line 7). The end goal is to find the fastest amongst all versions, which is then returned as the final reordered code (lines [START_REF] Norris | A scheduler-sensitive global register allocator[END_REF][START_REF] Berson | Integrated instruction scheduling and register allocation techniques[END_REF][START_REF] Rawat | Resource conscious reuse-driven tiling for GPUs[END_REF][START_REF] Goodman | Code scheduling and register allocation in large basic blocks[END_REF]. Appendix A gives a detailed example of using LARS to reorder the 2D 9-point stencil.

IV. EXPERIMENTAL EVALUATION Experimental Setup:

The experimental results presented here were obtained on an Intel Xeon Phi and a Skylake i7-6770K processor. The hardware details are shown in II.

Both GCC and LLVM provide some fine-grain control over the instruction scheduling passes via the compilation flags: GCC allows the user to enable or disable the prepass and postpass instruction scheduler, whereas LLVM provides multiple implementations for the prepass scheduler. With the fine-grain access to the compiler passes, we can control the effect of the scheduling passes on the LARS reordered schedule.

Benchmarks: We evaluate the efficacy of LARS on a wide variety of benchmarks, which can be grouped into five sets. The first set comprises generalized versions of computations typically used in iterative processes such as solving partial differential equations and convolutions [START_REF] Micikevicius | 3D finite difference computation on GPUs using CUDA[END_REF]. The second set contains smoothers used in HPGMG benchmark suite [START_REF]High-Performance Geometric Multigrid[END_REF]. The third set includes high-order stencil computations from the ExpCNS Compressible Navier-Stokes mini application from DoE [START_REF]ExaCT: Center for Exascale Simulation of Combustion in Turbulence: Proxy App Software[END_REF] and the Geodynamics Seismic Wave SW4 application code [START_REF]Seismic Wave Modelling (SW4) -Computational Infrastructure for Geodynamics[END_REF]. The fourth set comprises the kernels from Cloverleaf benchmark suite [START_REF] Mallinson | Cloverleaf: Preparing hydrodynamics codes for exascale[END_REF]. The final set contains the tensor contraction kernels CCSD(T) from the NWChem suite [START_REF]NWChem Download[END_REF]. These benchmarks are listed in Table III. All benchmarks are double-precision. Note that we evaluate all compute kernels from Cloverleaf benchmark suite, excluding the trivial kernels that copy data from one array to another.

Code Generation: The original version (Original) for each benchmark is as written by application developers, parallelized and vectorized by adding appropriate OpenMP pragma to the outermost parallel loop, and SIMD pragma to the innermost vectorizable loop, but without any explicit loop unrolling. We generate multiple unrolled versions (Unrolled) for each benchmark by explicitly unrolling all but the innermost loop by powers of 2, restricting the maximum unroll factor to 8. For each unrolled version, we generate an accumulation version with all the additive contributions converted to accumulations (Accumulation). Corresponding to each unrolled version, we create a LARS-optimized version (Reordered) as well. At present, LARS does not autotune for optimal unrolling factors. The user only needs to specify the unrolling factors in the pragma (line 6 of Listing 3), and appropriately modify the increment expression of the computational loop nest (lines 3-5 of Listing 3). The unrolling of the statements is done by the preprocessing stage described in Section III-A, usually in under less than a second. All benchmarks are control-flow-free and conform to the restrictions described in Section III-A, and hence LARS is able to parse them without any code modification. Whenever possible, we set the unrolling factor along the fastest-varying dimension to 1 to allow efficient vectorization by the underlying compiler. Except for the CCSD(T) kernels, LARS generates a reordered schedule with appropriate SIMD intrinsics for multi-core CPU and Xeon Phi. We do not generate accumulation version for CCSD(T) benchmarks, since their unrolled versions are already in accumulation form. No other optimization (e.g. tiling) is applied to the reordered code, in order to get a fair performance comparison with respect to the unrolled versions. For code generation, the interlock window size, k, is set to 2. For all benchmarks, the reordered versions were generated under 15 seconds by LARS. We check the correctness of each reordered code against the original version. For all benchmarks, we consider the theoretical floating-point operations performed by the original version to compute the GFLOPS for all versions.

Performance Results: Table IV plots the performance of the original, unrolled, accumulation, and reordered code for the different benchmark sets. For the convolution kernels, the reordered version significantly outperforms the original and unrolled versions over all compilers/architectures, especially when the order of the computation increases. The order here refers to the extent of elements read from the center. For IV: Performance of the benchmarks (in GFLOPS) on different architectures example, the 2d21pt kernel benefits the most from reordering, and it has the highest order, 5. This observation is consistent with that of Stock et al. [START_REF] Stock | A framework for enhancing data reuse via associative reordering[END_REF]. The volume of data read per point usually increases with an increase in the order for most of the dense computations, and this can exacerbate the spills in the unrolled code. LARS exploits associativity to judiciously reorder the instructions by interleaving computations across the unrolled statements, thereby reducing the spill volume. The reordered version also outperforms the accumulation version, indicating that reordering the instructions after rewriting the computation in accumulation form is crucial to performance. LARS outperforms both original and unrolled versions for the HPGMG smoothers as well, but the performance gains are lower when compared to the convolution kernels due to two reasons: (a) LARS leverages operator distributivity in order to exploit associativity for smoothers, thereby increasing the computation; (b) the increase in arithmetic intensity (defined as the FLOPs relative to the memory accesses) with unrolling is less significant for smoothers, which implies that they are more bandwidth-bound than convolutions.

For Cloverleaf 3D and 2D benchmarks, the performance of LARS-reordered code is almost the same (1.0× -1.13× for multi-core CPU), or slightly better (1.14× -1.7× with GCC on Xeon Phi). This can be mainly attributed to the nature of the computations in the Cloverleaf suite. As observed from Table III, each kernel in the Cloverleaf benchmarks reads from a multitude of arrays, but the computations in each kernel is scarce. Thus, there is very little reuse to be exploited via unrolling, and the computation is severely bandwidth-bound. Both these factors reduce the benefits of unrolling and reordering. However, the performance results serve to demonstrate that the reordering done by LARS does not degrade the performance for such benchmarks.

High-order stencils are becoming commonplace in scientific simulations, and optimizing them is the current focus of the HPC community. These high-order stencils can be thought of as a forest of CDAGs, with high data reuse across the CDAGs. This abstraction is particularly challenging for a traditional compiler to optimize, since most of the integrated instruction schedulers are designed to schedule a single CDAG. With LARS, we were able to reduce the total memory accesses per point even with the non-unrolled version, and achieve a 1.22× -3× speedup over the base version.

A similar performance trend is observed for CCSD(T) tensor contractions. Since each contraction has a loop nest of depth 7 and loop unrolling in tensor contractions is a research problem in itself [START_REF] Ma | Optimizing tensor contraction expressions for hybrid cpu-gpu execution[END_REF], we fix two loops as the unrolling candidates. Since the computation is an accumulation, the unrolling candidates are chosen to favor the reuse of the output element. Unrolling greatly improves the performance, and we get a 1.09× -2.26× speedup with simple reordering of the instructions to reduce the memory accesses.

Appendix B presents an analysis of the generated assembly code on Xeon Phi 7250, confirming that the LARS-reordered version incurs far fewer memory accesses than the unrolled version.

V. RELATED WORK

The interplay of register allocation and instruction scheduling has been studied by a body of prior research [START_REF] Motwani | Combining register allocation and instruction scheduling[END_REF], [START_REF] Pinter | Register allocation with instruction scheduling[END_REF], [START_REF] Norris | A scheduler-sensitive global register allocator[END_REF], [START_REF] Berson | Integrated instruction scheduling and register allocation techniques[END_REF], [START_REF] Krall | Optimistic integrated instruction scheduling and register allocation[END_REF], [START_REF] Goodman | Code scheduling and register allocation in large basic blocks[END_REF]. Sethi et al. [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF] propose an algorithm to translate an expression tree into machine code using optimal number of registers. The algorithm does not extend to CDAGs. Goodman and Hsu [START_REF] Goodman | Code scheduling and register allocation in large basic blocks[END_REF] present a prepass scheduler that is register-pressure sensitive. Motwani et al. [START_REF] Motwani | Combining register allocation and instruction scheduling[END_REF] show that integrated register allocation and instruction scheduling is NPhard, and propose a combined heuristic that provides relative weights for controlling register pressure and instruction parallelism. Other works attempt to combine the data dependence graph on which instruction scheduling is performed and interference graph on which register allocation is performed, and then perform instruction scheduling and register allocation on the unified graph. Berson et al. [START_REF] Berson | Integrated instruction scheduling and register allocation techniques[END_REF] use register reuse DAGs to identify instructions whose parallel scheduling will require more resources than available, and optimize them to reduce their resource demands. Pinter [START_REF] Pinter | Register allocation with instruction scheduling[END_REF] describes an algorithm that colors a parallel interference graph to obtain a register allocation that does not introduce false dependences, and therefore exploits maximal parallelism. Norris et al. [START_REF] Norris | A scheduler-sensitive global register allocator[END_REF] propose an algorithm that constructs an interference graph with all feasible schedules, and then remove interferences for schedules that are to be least likely followed. All these approaches are designed for in-order or VLIW processors, and an experimental evaluation by Valluri et al. [START_REF] Valluri | Evaluating register allocation and instruction scheduling techniques in out-of-order issue processors[END_REF] show that integrated efforts rarely benefit OoO processors.

In the context of OoO processors, Barany and Krall [START_REF] Krall | Optimistic integrated instruction scheduling and register allocation[END_REF] propose an optimistic integrated approach that performs prepass scheduling, and then rearranges instructions to mitigate register pressure during register allocation. However, the rescheduling is done from the local perspective of a single instruction, and tends to reduce ILP. Silvera et al. [START_REF] Silvera | A register pressure sensitive instruction scheduler for dynamic issue processors[END_REF] propose an instruction reordering framework for dynamic issue hardware that takes the output schedule after prepass scheduling, and reorders the instructions within the instruction window to reduce register pressure. With such constraints on reordering, their method will not be able to do aggressive reordering that reduces register pressure while maintaining ILP, as done by LARS (Appendix A). While Barany and Krall [START_REF] Krall | Optimistic integrated instruction scheduling and register allocation[END_REF] note that their rescheduling may not reduce register pressure as much as a register-pressure-driven scheduler, both they and Silvera et al. [START_REF] Silvera | A register pressure sensitive instruction scheduler for dynamic issue processors[END_REF] emphasize the importance of reducing register spills in OoO processors.

Stock et al. [START_REF] Stock | A framework for enhancing data reuse via associative reordering[END_REF] leverage retiming to convert a gathergather stencil into a scatter-gather stencil, thereby relieving register pressure. However, their approach is only applicable to regular stencils. In contrast, our work proposes a generalized reordering strategy that uses affinity between labels and unblocked instructions to reduce register pressure; it is not restricted to the cases that Stock et al. handle. Domagala et al. [START_REF] Domagala | Register allocation and promotion through combined instruction scheduling and loop unrolling[END_REF] present a register allocation strategy that is cognizant of loop unrolling and instruction scheduling. However, it does not consider associative reordering to improve register allocation/instruction scheduling. Veras et al. [START_REF] Veras | Compilers, hands-off my hands-on optimizations[END_REF] identify instances where manual instruction selection and scheduling can boost the performance of compute-bound numerical kernels like matrix-matrix multiplication, and propose a technique that uses custom macro intrinsics to generate efficient assembly for such numerical codelets. Even though their work, like ours, highlights the same performance issues with instruction scheduling of GCC, their approach is only suitable for numerical kernels that are tiled to expose repeated application of a compact codelet. Recently, Rawat et al. [START_REF] Rawat | Register optimizations for stencils on GPUs[END_REF] proposed an associative reordering strategy targeting stencil computations on GPU. They represent the stencil computation as a DAG of expression trees, and then generalize the Sethi-Ullman algorithm [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF] to schedule the DAG with the objective of minimizing register pressure. In contrast, we present a more generalized scheme that does not rely on any special abstraction of computation, and is adapted to generate efficient reordered code for multicore CPUs.

VI. CONCLUSION

Register spills and low performance are a problem when compiling scientific codes with high degree of many-tomany reuse. We present LARS, a list-based, adaptive, register pressure driven source-level scheduler, that leverages operator associativity to reorder instructions to reduce register pressure. The metrics used by LARS are powerful enough to exploit patterns in the computation, and general enough to benefit a variety of input applications. We demonstrate the usability of LARS, and the effectiveness of its reordering heuristics, over several benchmarks using multiple compilers and architectures.

C. Installation

First clone the artifact source to a local machine: $. git clone https://github.com/pssrawat/LARS Then compile the source code to create the executables: $. cd LARS $. make all To run the benchmarks: $. cd examples Edit run-benchmarks.sh in examples/ to select appropriate target architecture, and set up paths to the benchmarking compilers. The default has been set for the Skylake i7-6770K processor.

Execute the benchmarking script: $. ./run-benchmarks.sh

The computed GFLOPS for all the benchmarks will be redirected to the output file output.txt in the examples/ directory.

D. Evaluation and expected result

The performance for each stencil benchmark in GFLOPS will be in output.txt after the evaluation script successfully finishes.

E. Experiment customization

The unrolling factors can be changed in the input C/C++ file, and the reordered versions regenerated by using the reorder.sh script provided with each benchmark.

The documentation in docs/ folder provides additional details about adding new benchmarks, and optimizing them with LARS.

Fig. 1 :

 1 Fig. 1: Example: statements lowered down to sequence of instructions, and corresponding CDAG

Fig. 2 :Fig. 3 :

 23 Fig. 2: Expression tree of two statements

Fig. 5 :

 5 Fig. 5: Example: Using shadows to avoid interlocks

5 Fig. 6 :

 56 Fig. 6: Steps in instruction reordering with LARS for a 4-way unrolled 2D 9-point Jacobi stencil

  Interlock window size Output: R: Reordered schedule 1 DG ← dependence graph for P ; 2 L ← ∅; // set of live labels 3 S ub ← instructions that have no incoming dependences in DG; 4 S fire ← ∅; // set of fireable instructions 5 compute EST (ni) for each instruction ni using equation 1; 6 for each label l in P do 7 compute initial priority of l using EST of instructions (Sec. III-E1) 8 while not all instructions in P are fired do9 M ← ∅; // list of cost tuple for each non-live label 10 for each label l ∈ L such that l occurs in an instruction in S ub do 11 M ← M ∪ Create-Tuple (l, L, S ub ); (Algo. 2)

	12	Adaptive-Custom-Sort (M ) (Sec. III-F);
	13	add the most profitable label in sorted M to L;
	14	for each instruction s in S ub do
	15	if all the labels of s are in L then
	16	S fire ← S fire ∪ s;
	17	S ub ← S ub \ s;
	18	while S fire = ∅ do
	19	remove an instruction s ∈ S fire that has the least interlocks with the
		instructions in R;

) Algorithm 1: Reorder (P, k) Input : P : Initial schedule, k: 20 for each label l in s do 21 if this is the last use of l, remove l from L; 22 if s contributes to an accumulation node t then 23 create a shadow accumulation output if any of the last k instructions in R also contribute to t; 24 append s to R; 25 remove the dependence edges from s in DG, add instructions with no incoming dependences in DG to S ub ;

Table Algorithm 3

 Algorithm : End-to-end Algorithm Input : M : Input program, uf : Unrolling factors Output: R: Reordered output 1 Tm ← ∞; 2 k ← user-specified interlock window size; 3 M ← Unroll (M, uf ); 4 G ← Dependence-Graph (M ); 5 {V } ← Create-Permutations (M , G ); (Section III-B) 6 for P ∈ {V } do

	7	r ← Reorder (P, k);
	8	t ← execution time of r;
	9	Tm ← min (Tm, t);
	10	R ← faster version between r and the one corresponding to Tm;
	11 return R;
		Resource	Details
		Intel multi-core	Intel core i7-6700K (4 cores, 2 threads/core 4.00 GHz, 8192K
		CPU	L3 cache)
		Intel Xeon phi	Intel Xeon Phi 7250 (68 cores, 4 threads/core 1.40GHz,
			1024K L2 cache)

TABLE I :

 I Benchmarking hardware

	Compiler	Flags
	gcc	-Ofast/Os -fopenmp -ffast-math -fstrict-aliasing -march=core-
		avx2/{knl -mavx512f -mavx512er -mavx512cd -mavx512pf} -mfma
		-f(no)schedule-insns -fschedule-insns2 -fsched-pressure
		-ffp-contract=fast
	llvm	-Ofast/Os -fopenmp=libomp -mfma -ffast-math -fstrict-aliasing
		-march=core-avx2/knl -mllvm -ffp-contract=fast
		-pre-RA-sched="source/list-ilp/list-hybrid/list-burr"

TABLE II :

 II Compilation flags for multi-core and Xeon Phi

I. All benchmark codes are compiled with GCC-7.2.0, and the version of LLVM from the svn (llvm/trunk 311831). The compilation flags for both compilers are listed in Table

TABLE III :

 III Benchmark characteristics

TABLE

  [START_REF] Berson | Integrated instruction scheduling and register allocation techniques[END_REF]-point Jacobi stencil total memory accesses, UF : unrolling factor along loop dimensions {k,j,i}

	Bench.			GCC					LLVM
		Og	Unrolled		LARS	Og	Unrolled		LARS
		A	A	UF	A	UF	A	A	UF	A	UF
	2d25pt	55	77	{2,1}	58	{2,1}	67	207	{4,1}	70	{4,1}
	2d49pt	141 344	{4,1}	144	{4,1}	153 399	{4,1}	138	{4,1}
	2d64pt	201 494	{4,1}	174	{4,1}	213 519	{4,1}	165	{4,1}
	2d81pt	269 664	{4,1}	206	{4,1}	281 655	{4,1}	194	{4,1}
	2d121pt	429 1064	{4,1}	294	{4,1}	286 2056	{8,1}	763	{8,1}
	3d27pt	65	143	{8,1,1}	93	{8,1,1}	71	223	{4,1,1}	88	{4,1,1}
	3d125pt	468 1133 {2,2,1}	361	{2,2,1}	277 1019 {4,1,1}	497	{4,1,1}
	chebyshev	42	131	{2,2,1}	73	{2,2,1}	50	297	{4,2,1}	127	{4,2,1}
	7-point	15	67	{8,1,1}	62	{8,1,1}	26	34	{4,1,1}	32	{4,1,1}
	poisson	27	43	{2,1,1}	35	{2,1,1}	36	166	{8,1,1}	102	{8,1,1}
	helmholtz-v2	21	62	{4,1,1}	60	{4,1,1}	33	75	{4,1,1}	60	{4,1,1}
	helmholtz-v4	74	151	{2,1,1}	111	{2,1,1}	76	266	{4,1,1}	233	{4,1,1}
	27-point	36	228	{4,2,1}	99	{4,2,1}	48	131	{4,1,1}	67	{4,1,1}
	hypterm	317	-	-	268	{1,1,1}	307	-	-	214	{1,1,1}
	diffterm	345	-	-	328	{1,1,1}	440	-	-	386	{1,1,1}
	rhs4th3fort	632	-	-	426	{1,1,1}	327	-	-	287	{1,1,1}
	derivative	299	-	-	223	{1,1,1}	311	-	-	290	{1,1,1}
	cell-advec 3D	49	92	{2,1,1}	84	{2,1,1}	50	94	{2,1,1}	79	{2,1,1}
	mom-advec 3D	61	114	{2,1,1}	60	{1,1,1}	84	118	{2,1,1}	55	{1,1,1}
	accelerate 3D	76	150	{2,1,1}	75	{1,1,1}	75	156	{2,1,1}	51	{1,1,1}
	ideal-gas 3D	7	12	{2,1,1}	5	{1,1,1}	6	13	{2,1,1}	6	{1,1,1}
	PdV 3D	47	86	{2,1,1}	46	{1,1,1}	41	86	{2,1,1}	70	{2,1,1}
	calc-dt 3D	44	82	{2,1,1}	71	{2,1,1}	42	77	{2,1,1}	58	{2,1,1}
	fluxes 3D	33	120	{2,2,1}	95	{2,2,1}	32	120	{2,2,1}	92	{2,2,1}
	viscosity 3D	47	84	{2,1,1}	80	{2,1,1}	50	100	{2,1,1}	80	{2,1,1}
	cell-advec 2D	76	143	{2,1}	132	{2,1}	72	139	{2,1}	127	{2,1}
	mom-advec 2D	47	164	{4,1}	141	{4,1}	24	163	{4,1}	85	{4,1}
	accelerate 2D	42	162	{4,1}	99	{4,1}	40	170	{4,1}	97	{4,1}
	ideal-gas 2D	7	12	{2,1}	7	{1,1}	6	13	{2,1}	6	{1,1}
	PdV 2D	28	48	{2,1}	42	{2,1}	22	42	{2,1}	38	{2,1}
	calc-dt 2D	23	42	{2,1}	39	{2,1}	24	43	{2,1}	34	{2,1}
	fluxes 2D	16	50	{4,1}	44	{4,1}	14	50	{4,1}	43	{4,1}
	viscosity 2D	23	42	{2,1}	38	{2,1}	28	47	{2,1}	36	{2,1}
	sd-t-d1-1	13	76	{4,8}	48	{4,8}	13	76	{4,8}	50	{4,8}
	sd-t-d1-2	13	76	{4,8}	48	{4,8}	13	76	{4,8}	48	{4,8}
	sd-t-d1-3	15	76	{4,8}	50	{4,8}	16	69	{4,8}	57	{4,8}
	sd-t-d1-4	13	82	{4,8}	54	{4,8}	13	76	{4,8}	50	{4,8}
	sd-t-d1-5	13	126	{4,8}	93	{4,8}	13	104	{4,8}	62	{4,8}
	sd-t-d1-6	15	141	{4,8}	72	{4,8}	16	106	{4,8}	57	{4,8}
	sd-t-d1-7	13	82	{4,8}	60	{4,8}	13	76	{4,8}	48	{4,8}
	sd-t-d1-8	13	126	{4,8}	93	{4,8}	13	104	{4,8}	73	{4,8}
	sd-t-d1-9	12	121	{4,8}	97	{4,8}	18	126	{4,8}	71	{4,8}
	A:

TABLE V :

 V Assembly code analysis on Xeon Phi 7250

A value once loaded in a register will remain so for all its def/uses

ACKNOWLEDGMENTS

We thank the anonymous reviewers for their feedback and suggestions that helped improve the paper. This work was supported in part by the Exascale Computing Project (17-SC-20-SC), a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration, and by the U.S. National Science Foundation (NSF) through awards 1440749 and 1513120.

APPENDIX A EXAMPLE: LARS IN ACTION

We demonstrate the power of LARS by using it to reorder a Jacobi stencil computation [START_REF] Stock | A framework for enhancing data reuse via associative reordering[END_REF]. We assume that the interlock window size is 1. The computation has only inter-statement reuse, and the cost-tuple for labels are sorted as described in Section III-F.

Figure 6e shows a 4-way unrolled version of the 2D 9point Jacobi stencil. We assume that the coefficients in the stencil are literals, and all the input contributions to outputs are additive. There are 4 expression trees, each corresponding to the computation of a single output point, and there is significant reuse between these trees: two consecutive output points reuse 6 input values, and the output points two hops away reuse 3 input values. For the ease of description, let us assume that each input (output) point in Figure 6e is assigned an integer identifier which starts from 1, and is incremented during the lexicographical scan, going from left-to-right, topto-bottom. We identify an input or output label as i v or o v , respectively, where v is its identifier. All the labels have the same initial priority.

LARS starts by scheduling the solo contributions from the inputs i 1 , i 7 and i 13 that contribute to o 1 , since these labels can be immediately released (Figure 6a). Next, i 2 is made live, since it has firing potential of 1, and has the lowest primary affinity to other non-live labels. Now, making o 2 live will release i 2 (Figure 6b). i 14 is made live next, as it will be released after making its contributions to o 1 and o 2 . i 8 will be made live next, forcing o 3 to become live in the next step. At this point, we make i 3 live, and it contributes to three alreadylive output labels (Figure 6c).

LARS follows this pattern to progress to the schedule shown in Figure 6d, and ultimately that of 6e. At each step, we had at most three output points, that had high secondary affinity to each other, live consecutively. Also, we made exactly one input point live, which contributed to all the live output points, and was immediately released. Therefore, irrespective of the degree of unrolling, the maximum register pressure for the schedule by LARS will be 4.

Obtaining such a schedule is difficult with the existing instruction schedulers. The existing schedulers may interleave the computation across trees to increase ILP. However, among multiple interleavings with the same degree of ILP, there will be only a few that will simultaneously reduce the register pressure. Finding such interleavings requires more than just a greedy decision based on a local perspective of register pressure. LARS is able to find such an interleaving by having a broader perspective of register pressure based on release/fire potential, and cumulative primary/secondary affinities.

APPENDIX B ASSEMBLY CODE ANALYSIS

We perform an analysis of the generated assembly code for the various versions, and count the number memory accesses via loads into the ymm/zmm registers in the computational loop. The numbers for Xeon Phi 7250 are presented in Table V. One can observe from the data that the reordered version incurs far lesser memory accesses than the unrolled version, indicating that the reordering with LARS reduces the number of spills and reloads.

APPENDIX C ARTIFACT DESCRIPTION A. Abstract

The artifact comprises LARS, an automated framework to perform reordering optimization on straight-line codes; the algorithmic details of the framework are described in the SC '18 2) How software can be obtained (if available): The framework is open-source, and will be available for download from the git repository https://github.com/pssrawat/LARS. The downloaded package comprises the source code, the benchmarks, and the evaluation instructions and scripts. All the files in the repository are licensed to The Ohio State University.

3) Hardware dependencies: The framework has been tested on Ubuntu 16.04 and Red Hat Enterprise Linux Server release 6.7.

4) Software dependencies:

flex version ≥ 2.6.0 (2.