A Language for Describing Optimization Strategies

Optimizing programs to run efficiently on modern parallel hardware is hard but crucial for many applications. The predominantly used imperative languages - like C or OpenCL - force the programmer to intertwine the code describing functionality and optimizations. This results in a nightmare for portability which is particularly problematic given the accelerating trend towards specialized hardware devices to further increase efficiency. Many emerging DSLs used in performance demanding domains such as deep learning, automatic differentiation, or image processing attempt to simplify or even fully automate the optimization process. Using a high-level - often functional - language, programmers focus on describing functionality in a declarative way. In some systems such as Halide or TVM, a separate schedule specifies how the program should be optimized. Unfortunately, these schedules are not written in well-defined programming languages. Instead, they are implemented as a set of ad-hoc predefined APIs that the compiler writers have exposed. In this paper, we present Elevate: a functional language for describing optimization strategies. Elevate follows a tradition of prior systems used in different contexts that express optimization strategies as composition of rewrites. In contrast to systems with scheduling APIs, in Elevate programmers are not restricted to a set of built-in optimizations but define their own optimization strategies freely in a composable way. We show how user-defined optimization strategies in Elevate enable the effective optimization of programs expressed in a functional data-parallel language demonstrating competitive performance with Halide and TVM.


Introduction
The tremendous gains in performance and efficiency that computer hardware continues to make are a key driving force for innovation in computing. This enables entire new areas of computing such as deep learning to deliver applications unthinkable even just a few years ago. With the end of Moore's law and Denard's scaling [23], these gains no longer come for free for software writers. Programs have to be optimized for an increasing diverse set of hardware devices by exploiting many subtle details of the computer architecture. Performance portability has emerged as a crucial concern as software naturally outlives the faster cycle of hardware generations. In addition, specialized hardware has proven to offer extreme benefits for performance and energy efficiency -if the specially optimized software exploits it.
The predominant imperative and low-level programming approaches such as C, CUDA, or OpenCL force programmers to intertwine the code describing the functional behavior of the program with optimization decisions. This makes them -by design -non performance portable. As an alternative, higher level domain-specific approaches have emerged that allow programmers to declaratively describe the functional behavior without committing to a specific implementation. Popular examples of this approach are virtually all machine learning systems such as TensorFlow [1] or PyTorch [27]. For these approaches, the compilers and runtime systems are responsible to optimize the computations that are expressed as data-flow graphs. Programmers have limited control about the optimization process. Instead large teams of engineers at Google and Facebook provide fast implementations for the most common hardware platforms, for TensorFlow including Google's specialized TPU hardware. This labour intensive support of new hardware devices is currently only sustainable for the biggest companies in the market -and even they struggle [5]. To overcome this innovation obstacle and to achieve automated performance portability we will need to rethink how we separate, describe, and apply optimizations in a more principled way.
Encoding program transformations as rewrite rules has been a long established idea. Bird and de Moor [6] studied an algebraic programming approach where functional programs are rewritten by exploiting algebraic properties. The Glasgow Haskell Compiler allows the specification of rewrite rules for program optimizations [28]. More recently, Lift [33] encodes optimization and implementation choices as rewrite rules for optimizing a high-level pattern-based data-parallel functional language using an automated stochastic search method applying the rewrites. Rewrite based approaches, such as Lift, have the advantage of being easily extensible towards new application domains (such as stencils [21]) as well as supporting new hardware features (such as specialized vector instructions which are encoded as new low-level patterns and introduced by a rewrite rule [34]). Unfortunately, these rewrite approaches are limited in their practicality to deliver the high performance required in many real-world applications. They lack control over the rewriting process and the automated rewriting using stochastic search processes takes a long time to find a high performance implementation. In this paper, we are going to address these practical limitations of rewrite-based approaches for optimizing high-performance real-world applications by defining a strategy language that allows the definition of optimization strategies that precisely controls the rewrite process.
Halide [30,31] has introduced the concept of separating programs into functional descriptions and schedules in the area of high-performance domain-specific code generators. A schedule describes the optimizations to be applied to the Halide algorithm that defines the functional behavior of the computation. Halide's schedules -as well similar schedules in TVM [12] -are implemented using a set of predefined APIs that expose a fixed set of optimization options. Halide's authors describe these APIs as a scheduling language but it lacks many desirable properties of a programming language. Most crucially, programmers are not able to define their own abstractions. Even the composition of existing optimization primitives is in some cases unintuitive due to the lack of a clear semantics and Halide's compiler has default and implicit behavior limiting experts' control. All of these reasons make writing schedules in Halide significantly harder than writing algorithms. Furthermore, for some desirable optimizations it is not sufficient to change the schedule but the algorithm itself has to be redefined -violating the promise of separating algorithm and schedule. In this paper, we build upon Halide's general idea but provide a proper functional strategy language, called Elevate, with clear semantics of individual primitives and how they compose. It enables programmers to define their own abstractions for building optimization strategies in a composable and reusable way.
The design of Elevate is heavily inspired by research on strategy languages for rewrite systems used in other contexts -and largely unknown to the high-performance code generation community -such as Stratego [37]. Kirchner [24] provides a recent overview of the research of the rewriting community. We claim no novelty in the design foundations of strategy languages but instead in the strategies we present and their usage to facilitate the generation of highly efficient code on modern hardware.
Our paper makes the following key contributions: • Description of the design of Elevate, a functional language for describing optimization strategies for highperformance code generation (Section 3); • demonstration of Elevate using three case studies: automatic differentiation (section 4), image processing (section 5) and deep learning (section 6). They show the flexibility and extensibility of Elevate and experimentally evaluate the practicality of a rewrite based approach for achieving competitive high performance.

Motivation and Background
We motivate the need for a strategy language with a closer look at Halide. We then argue for a more principled language approach for describing optimizations strategies.
the dot product for each coordinate pair (x, y). The dot product is expressed as pairwise multiplications and reducing over the reduction domain r using the += operator (line 3). The other lines in the listing define the schedule specifying the optimizations to be performed. The Halide compiler takes this C++ program and produces efficient GPU code coming close to highly optimized low-level library code.
By looking at the code it is immediately clear that writing a schedule is significantly more challenging than writing the algorithm describing matrix-matrix multiplication. Schedules are written using a sequence of API calls on the C++ objects that represent the input (A, B) and output (out) data. prod represents the reduction operation in Halide's internal representation. While the algorithm and schedule are separated they still share the same C++ identifiers and must, therefore, be written in the same C++ scope limiting the reuse of schedules across algorithms.
Some of these optimizations are specific for the hardware (like vectorize or gpu threads), others are generally useful algorithmic optimizations for many applications (like tiling to increase data locality), and others are low-level optimizations (like unroll and reorder that transform loop nests). Halide is not easily extensible. Adding a new optimization primitive to the schedule API requires extending the Halide compiler. Even a primitive like tile that can be implemented with split and reorder 1 is represented as a composition but provided as a built-in abstraction. Halide's schedules lack the ability for user-defined abstractions.
The behavior of some primitives is not intuitive and the documentation provides only informal descriptions, e.g., for update: "Get a handle on an update step for the purposes of scheduling it". The lack of clear descriptions of the optimization primitives makes reasoning about the schedule difficult. For example, is it unclear to us why lines 21-23 are repeated at lines 25-27 with calls to unroll and update in between. img |> pad2D(1) |> slide2D(3)(1) |> map2D(fun(nbh => 3 dot(join(weights2d))(join(nbh)) )))) 1 val sbf = (topDown(separateDot) ';' lowerToC)(bf) Figure 2. 2D binomial filter in a Lift-like language (top) and the separating optimization strategy in Elevate (bottom). Figure 1 shows the implementation of a two-dimensional binomial filter in Halide. The listing on top shows the basic Halide algorithm implementation by computing every output pixel as a weighted sum of the 3 × 3 surrounding pixels. A more efficient way is shown below where the computation is separated into a vertical and horizontal filter operating on 3 pixels each. Separability is a well known domain-specific optimization in image processing and only valid for appropriate weights. Halide does not offer this optimization as a scheduling primitive and, therefore, programmers are forced to change the algorithm for this optimization -clearly violating the promise of separating algorithm and schedule.
If no schedules are provided (as in fig. 1), the Halide compiler employs a set of implicit default optimizations that are out of reach of the control of the user. This sometimes leads to the surprising behavior that algorithms without a schedule perform better (e.g., due to auto-vectorization) than ones where a schedule is provided.

Towards an Optimization Strategy Language
Out of the shortcoming of the API approach we identify the following desirable features for a strategy language: 1. Optimization strategies should be defined clearly separated from the computational program facilitating reusablility of strategies across programs; 2. Strategies should be written as compositions of user-defined strategies (possibly domain-specific ones); the language should facilitate the creation of higher-level abstractions; 3. All strategies should have a clear semantics allowing reasoning about their application and implicit default behavior should be avoided to empower users to be in control. Essentially we argue that a strategy language should be build with the same standards as a language describing computation. In this paper we present such a language: Elevate. Figure 2 shows an example of an Elevate strategy (bottom) that optimizes a program (top) written in a completely separate pattern-based language similar to Lift [21] called Rise. The optimization strategy is a sequential composition (';') of user defined strategies providing a higher level of abstraction. Strategies are build as compositions of rewrite rules with a clear semantics and no implicit behavior.
In the remainder of the paper, we will explain the language for writing such strategies and defining custom abstractions.

Elevate: A Language for Describing Optimization Strategies
In this section, we describe our language for describing optimization strategies: Elevate. It is heavily inspired by earlier works on strategy languages for term rewriting systems, particularly Stratego [41]. Our key contribution is not the design of Elevate itself but rather its application to define optimization for high-performance code generators. In this section, we focus on introducing Elevate as a practical programming language. For a more formal treatment of strategy languages see [39].

Language Features and Types
Elevate is a functional language with a standard feature set including function recursion, algebraic data types and pattern matching. Besides the standard scalar data types such as int, types of interests are function types, tuple types and list types. Our current implementation is an embedded DSL in Scala and we use Scala-like notation in the paper.

Strategies
A strategy is the fundamental building block of Elevate. Strategies encode program transformations and are modeled as functions with the following type:

type Strategy[P] = P => RewriteResult[P]
Here P is the type of the program that is rewritten. P could for example be Rise for programs written in the Rise language from fig. 2

. A RewriteResult[P]
is an algebraic datatype encoding the success or failure of applying a strategy to a program:

RewriteResult[P] = Success[P](p: P) | Failure[P](s: Strategy[P])
In case of a successful application, Success contains the transformed program, in case of a failure, Failure contains the strategy that has been unsuccessful. The simplest example of a strategy is the id strategy which always succeeds and returns its input program:

Rewrite Rules as Strategies
In Elevate, rewrite rules are also strategies, i.e., functions satisfying the same type given above. Let's look at a concrete type of programs, such as Rise which is a pattern-based functional programming language where we want to apply well-known rewrite rules such as the fusion of two map calls: In Rise, the left-hand side of the rule is expressed as: val p: Rise = fun(xs => map(f)(map(g)(xs))) map(f)(map(g)(xs)) map(fun(x �� f(g(x))))(xs) Figure 3. Rise's map-fusion rule as an AST transformation.
The AST representation of the body of this is shown in fig. 3 on the left, with function applications explicit as app nodes. This is the implementation of the fusion rule in Elevate: Note that we are mixing expressions of the Rise language (i.e., map(f)) and Elevate. The expression nested inside Success is the rewritten expression shown in fig. 3 on the right.

Strategy Combinators
A key idea that Elevate inherits from Stratego [39] is to describe strategies as compositions of other strategies. Therefore, we introduce strategy combinators.
The seq combinator is given two strategies fs and ss and applies the first strategy to the input program p. Afterwards, the second strategy is applied to the result.
In the implementation of seq, we make use of the monadic interface of strategies: the RewriteResult ADT provides two versions of map/flatMap to compose strategies -one in case of a successful strategy application and one in case of failure.
The lChoice combinator is given two strategies and applies the second strategy only if the first strategy failed.

def lChoice[P]: Strategy[P] => Strategy[P] => Strategy[P]
We use <+ as notation for lChoice and ';' for seq and define two more combinators: The try combinator applies a strategy and in case of failure applies the identity strategy. Therefore, try never fails.

Traversal Strategies
The mapFusion strategy we saw in the previous subsection is implemented as a function in Elevate. Therefore, its match statement will try to pattern match its argument -the entire program. This means that a strategy on its own is very hard to reuse in different circumstances. In addition, a strategy is often applicable at multiple places within the same program or only applicable at a specific location. For example, the mapFusion strategy is applicable twice in the following Rise program:
In Elevate, we use traversal strategies to describe at which exact location a strategy is applied. Luttik et al. [25] proposed three basic traversal strategies: all applies a given strategy to all sub-expressions of the current expression and fails if the strategy is not applicable to all sub-expressions. one applies a given strategy to exactly one sub-expression and fails it the strategy is not applicable to any sub-expression. some applies a given strategy to at least one sub-expression but potentially more if possible. one and some are allowed to non-deterministically choose sub-expressions.
In Elevate, we see these three basic traversal strategies as a type class: an interface that has to be implemented for each program type P. The implementation for Rise is straightforward. Rise programs are represented by ASTs such as the one in fig. 4, therefore, all, one, and some correspond to the obvious implementations on the tree-based representation.
To fuse the first two maps in fig. 4 we use the one traversal strategy: one(mapFusion)(threemaps). This will apply the mapFusion strategy not at the root of the AST, but instead one level down first trying to apply the strategy (unsuccsessfully) to the function parameter and then (successfully) to the function body highlighted in the upper-right blue box.
To fuse the last two maps we use the one traversal strategy twice to apply mapFusion two levels down in the AST: one(one (mapFusion))(threemaps). This sucessfully applies the fusion strategy to the expression highlighed in the lower-left purple box in fig. 4.

Language-Specific Traversal Strategies
The traversals we have discussed so far are not specific to a particular language, such as Rise. These traversals are flexible, but offer only limited control as for one and some the selection of sub-expressions is either non-deterministic, or implementation-dependent (as for Rise) and in our context it makes rarely sense to apply a strategy to all sub-expressions.
In Elevate, one can easily specify program language specific traversal primitives. Rise is a functional language using λ-calculus as its representation. Therefore, it makes sense to introduce traversals that navigate the two core concepts of λ-calculus: function abstraction and application.
To apply a strategy to the body of a function abstraction we define the following traversal strategy: For the Rise program shown in fig. 4, we are now able to precisely describe a traversal path in the AST. To fuse the first two maps we may write body(mapFusion)(threemaps), and to fuse the others body(argument(mapFusion))(threemaps).
The traversals defined here are specific to Rise but similar traversals are obviously possible for any functional language. If the program is not a functional language, say e.g., a computational graph as used by Tensorflow, different languagespecific traversals (e.g., leftOperand and rightOperand) could be defined to describe language-specific traversals.

Complete Expression Traversal Strategies
All of the traversal primitives introduced so far apply their given strategies only to immediate sub-expressions.
Using strategy combinators and traversals, we are able to define recursive strategies which traverse entire expressions: topDown and bottomUp are useful strategies traversing an expression either from the top or from the bottom, trying to apply a given strategy at every sub-expression and stopping at the first successful application. If the strategy is not applicable at any sub-expression, topDown and bottomUp fail.
allTopDown and allBottomUp do not use lChoice insisting on applying the given strategy to every sub-expression.
The tryAll strategy is often more useful as it wraps its given strategy in a try and thus never fails but applies the strategy wherever possible. Also note that the tryAll strategy traverses the AST bottom-up instead of top-down.
These traversals have also been proposed by Visser [39] and we use them here with slightly different names more fitting for our use cases.

Normalization, Confluence and Termination
When implementing rewrite rules, such as the mapFusion rule, as strategies, the match statement expects the program expression to be in a particular syntactic form. For a functional language like Rise, we might for example expect that expressions are fully β-reduced. To ensure that expressions satisfy a normal form we define: The normalize strategy applies a given strategy repeatedly at every possible sub-expression until it can not be applied any more. Therefore, after normalize successfully finishes it is not possible to apply the given strategy to any sub-expression any more. By defining a strategy for β-reduction and using it together with normalize we ensure that expressions are in β-normal-form.
Confluence (multiple non-deterministic rewrite paths eventually produce the same result) and termination are desirable properties for normal forms in term rewriting systems [39]. In Elevate, confluence only becomes a factor when the implementation of one and some are non-deterministic. This can often be avoided such as for the use cases we consider with Rise and F that we will discuss in section 4.
Termination of normal forms critically depends on the chosen set of strategies. Therefore, reasoning about terminating normal forms must be done on a case by case basis. For example, it is trivial to build a non-terminating normal form using the id strategy that is always applicable. We currently, do not prevent the creation of non-terminating strategies similar as almost all general purpose computational languages do not prevent writing non-terminating programs. In the future, we are interested to introduce a richer type system for Elevate to better assist the user in writing well behaved strategies.

Summary
We have introduced Elevate, a language for describing optimization strategies. In the next three sections we discuss three case studies of using Elevate in the domains of automatic differentiation, image processing, and deep learning.

Case Study 1: Automatic Differentiation
So far we have seen Rise as the only example of a language that we transform with Elevate, but Elevate is flexible and not restricted to a single language. In this first case study, we will look at the F language that has been introduced in [32].
F is a small functional language capable of automatically computing the derivative of arbitrary F functions. Implementing automatic differentiation is not too difficult but making it efficient is non-trivial. F achieves efficiency by rewriting the differentiated code. In the paper, rewrite rules are specified alongside examples. Example 5 in the paper shows that a F program transposing a matrix twice can be rewritten into a program without transposition, see fig. 5.
The paper does not provide an explanation how the rewriting between these programs happens or is specified. The authors only state "by applying the loop fusion rules and performing further partial evaluation the expression is derived".
We are interested in exploring the flexibility of Elevate and if we can specify the rewrite rule applications programmatically. We implemented the F language representing expressions using an algebraic data type FSmooth. We implemented the rewrite rules from the paper, such as fusion rules:   ,(e0,e1)),e2)) => Success (app(e1,e2) Using these rewrite rules encoded as Elevate strategies, we use normalize and lChoice to specify multiple strategies that should be applied repeatedly at every sub-expression: This Elevate program successfully rewrites the doublytransposed F program into the non-transposed form. By tracing the execution of the Elevate program we get a sequence of 12 basic rewrite rule applications explaining the program transformation step-by-step. A full version of the trace is shown in the supplementary material.
We also implemented the other examples in the paper which contain rewriting in Elevate-and identifying a minor bug in the description of example 6.
This case study shows Elevate's flexibility to implement an existing rewrite system. It also demonstrates Elevate's ease of use: we did not have to think about where to apply the individual rewrite rules thanks to the abstraction provided by normalize. It is important to stress, that this is not a built-in abstraction but defined itself in terms of the smaller building blocks repeat and topDown. In the next case-study, we discuss how the ability to leverage these abstractions and build custom ones enables the definition of optimization strategies for image processing.

Case Study 2: Image Processing
In this case study, we are interested to see how our extensible strategy language Elevate compares directly to Halide. We will look at the binomial filter example which we already briefly showed in fig. 1 and 2. We will use Rise as our computational language. Rise is a Lift [33]-like language that is compiled by rewriting high-level pattern-based programs into a low-level representation encoding implementation and optimization choices. It then uses a compilation process similar to [3] to compile the low-level pattern-based code into parallel imperative code.

Halide Schedules for the Binomial Filter
For Halide, we saw two algorithms describing the computation of the binominal filter in fig. 1. The naive version on the top is a straightforward implementation as a twodimensional stencil. The separated version on the bottom specifies the computation as a composition of vertical and horizontal one-dimensional stencils. In Halide, it is not possible to take the naive algorithm and use a schedule to specify the separability optimization. When we do not specify a schedule in Halide, a default schedule is chosen that inlines computations as much as possible. Therefore, the naive and the separated version with the default schedule result in code executing two nested loops and accessing 9 elements of the input image. We can instruct Halide not to fully inline the vertical filter by writing: b_y.compute_at(out, y); This schedule uses the variable names from the Halide algorithm implementing the separated version of binomial filter. The compute_at schedule instruction tells the compiler to perform the computation of the vertical filter (b_y) inside the for loop iterating over the y dimension of the out image. This computation will be stored in a temporary that is consumed in the nested loop iterating over the x dimension of out. We call this version scanline as the temporary stores an entire line of the image.
For all versions, it is possible to parallelize the outermost loop with: out.parallel(y);

Elevate Strategies Optimizing Binomial Filter
To compare with Halide, we express the binomial filter with Rise as shown at the top of fig. 2. This formulation is the naive way to describe a two-dimensional filter in Rise. The filter is expressed using two-dimensional variations of the pad, slide, and map high-level patterns in the style of [21]. pad models the boundary handling, the sliding window pattern slide describes a neighborhood of values each of which is then processed by the map pattern. The 2D versions of these pattens are just macros defined as compositions of the onedimensional versions and a few additional basic patterns. The dot product computation is also defined as a composition:

dot(x)(y) = reduce(add)(0)(map(mult)(zip(x)(y)))
To express the separability as an Elevate strategy we introduce an image-processing specific rewrite rule that describes how the dot product of the weights and the neighborhood inside the binomial filter is separated:  , app(join, w)), app(join, nbh)))) if w==w2d => Success(nbh |> map(dot(wh)) |> dot(wv)) case _ => Failure(sepDot) } The underlined values in the pattern matching indicate that these must match for the pattern matching to succeed. The strategy takes three parameters that are all expressions in the computational language Rise. w2d represents the two-dimensional weights and wh and wv are the separated horizontal and vertical weights. Elevate does not automatically attempt to separate the weights nor does it attempt to prove that the horizontal and vertical weights are a valid separation of the two-dimensional weights. These considerations are left to the user. We aim to empower users to extend Elevate which such domain-specific strategies.
To rewrite the naive binominal filter into the separated one, we apply separateDot with topDown as shown earlier as an Elevate strategy at the bottom of fig. 2

resulting in: 1 img |> pad2D(1) |> slide2D(3)(1) |> map2D(fun(nbh => 2 nbh |> map(dot(weightsH)) |> map(dot(weightsV)) ))
We express the lowering of high-level Rise expressions with Elevate strategies that encode low-level implementation choices such as whether we would like to parallelize or not. In Halide, the built-in compute_at primitive is used for the scanline version. In Elevate a user-defined strategy encodes the same transformation. We will investigate more complex optimization and low-level implementation strategies in more detail in the third case study in section 6.

Performance Evaluation
Even though this paper discusses Elevate and not Rise we want to evaluate whether a rewrite-based approach by combining them is capable of achieving competitive performance compared to the industry-strength Halide compiler that uses more traditional compiler techniques. We have seen that Elevate allows the definition of optimization strategies in an extensible way and that this allows to express optimizations as strategies that are not expressible as Halide schedules (such as separability). We are now interested to see if these strategies encoding the same optimization decisions lead to competitive performance when compiled with Rise and compared to Halide. Figure 6 shows the performance of the Halide and Rise generated code measured on a ARM Cortex A7 quad-core 2 . We can see -not surprisingly -that the non-parallel versions on the left are significantly slower than the parallel versions. The Halide generated code is 10-15% faster than the Rise generated code. Improvements to the Rise compiler might close this gap in the future. Crucially, we observe the same trend for performance improvements due to optimizations. This demonstrates that our extensible and rewrite based approach is capable of achieving competitive performance.

Case Study 3: Deep Learning
In our first two case studies, we looked at fairly simple strategies. In our final case study, we are interested to explore the practicability and scalability of Elevate. We are looking at the domain of deep learning where performance optimizations are particularly important. In this section, we explore the implementation of a scheduling language with Elevate using the ability to define custom abstractions. We use TVM [12] as an example for a state-of-the-art optimizing deep learning compiler with a scheduling API implemented in Python, similar to Halide. We use Rise again as the target language for the strategies we develop.
We start by looking at how TVM represents schedules and how we implement simple scheduling primitives such as parallel and vectorize in Elevate. Then we show how to implement more complex scheduling primitives like tile using composition in Elevate whereas it is built-in in TVM. We follow a tutorial from the TVM authors 3 that discusses seven differently optimized versions of matrix multiplication. For each one, we show an equivalent strategy implemented with Elevate and evaluate the performance achieved.

TVM Schedules for Matrix Multiply
In TVM, computations are expressed similar to TensorFlow: ((M, N), lambda x, y: 2

tvm.sum(A[x,k] * B[k,y], axis=k), name='C')
The "How to optimize GEMM on CPU" 3 tutorial discusses seven versions applying different optimizations. The baseline version uses a default schedule with no instructions. The blocking version tiles the two outermost loops computing matrix C and then splits the reduction loop before reordering the loop nest: With this rewritten computation we can now also describe the schedule affecting the computation of the temporary packedB matrix. Contrary to Halide, this computation is not inlined by default in TVM and results in a separate loop nest. In the rest of the case study, we attempt to implement a similar looking scheduling language in Elevate for rewriting Rise programs. We define abstractions ourselves similar to the built-in scheduling primitives provided by TVM.

Basic Scheduling Primitives as Elevate Strategies
The TVM scheduling primitives parallel, split, vectorize, and unroll can be implemented as rewrite rules for Rise.

Success( split(n) >> reduce(fun(a => fun(y =>
op(a, reduce(op)(init)(y)) )))(init) ) case _ => Failure( split(n) ) } TVM's split scheduling primitive implements loop-blocking (also known as strip-mining). In Rise, this is achieved by transforming the computation over an array expressed by map(f): first the input is split into an 2D array using split(n), then f is mapped twice to apply the function to all elements of the now nested array, and finally the resulting array is flattened into the original one-dimensional form using join. We write f >> g to indicate reverse function composition, i.e.,: fun(x => g(f(x))). It is important to note, that Rise does not materialize the intermediate two-dimensional array in memory, but only uses this representation inside the compiler for code generation. There is a second case for splitting reduce resulting in two nested reductions. The unroll strategy rewrites the high-level map and reduce patterns into Rise low-level patterns that will be unrolled by the Rise compiler.
Identifying Locations In TVM, named identifiers describe the location at which the optimization should be applied. For example, TVM's parallel is invoked with an argument specifying the loop to parallelize. Using named identifiers allows writing invalid schedules, e.g., trying to vectorize a reduction axis failing at runtime when TVM detects the error. Elevate does not use names to identify locations, but instead uses the traversals we defined in section 3. The vectorize strategy is -by construction -only applicable at valid locations within the AST.
By using Elevate's traversal strategies, we can apply the basic scheduling strategies in a much more flexible way: e.g., topDown(parallel) traverses the AST from top to bottom and will thus always parallelize the outermost map, corresponding to the outermost for loop. tryAll(parallel) traverses the whole AST instead and all possible maps are parallelized. Depending on the desired use case users are free to combine different traversals with the basic scheduling strategies.

Tiling as an Elevate Strategy
Tiling is an important optimization improving the cache hit rate by exploiting locality within a small neighborhood of elements. TVM's tile is a more complicated scheduling primitive to implement because it is essentially a combination of two traditional loop transformations: loop-blocking and loopinterchange. In fact, tile in TVM is a built-in combination of split for loop-blocking and reorder for loop-interchange. We already saw how to implement split using Elevate and we will now discuss how to implement tile using a combination of rules, normal-forms and domain-specific traversals.
We use matrix-matrix multiplication as the illustrative example to explain the optimization steps. Since we use Rise as the target language for the tiling strategy, we need to consider how matrix multiplication is expressed there: Essentially, the dot product is computed for each combination of rows and columns of matrix A and B.
In the following, we show how to use Elevate to systematically construct a strategy out of simple building blocks that has the same effect as TVM's tile scheduling primitive. Specifically, we construct a generalized strategy that is able to tile an arbitrary number of dimensions whereas TVM's tile only tiles in two-dimensions. This strategy expects a list of tile sizes, one per tiled dimension. The two-dimensional tiling, that is equivalent to TVM's built-in tile scheduling primitives, is expressed as tileND( List(x,y))(mm) for this 2D case we also write tile(x,y)(mm).
The intuition for our tileND implementation is simple: First, we ensure that the required rules are applicable to the input expression by normalizing the expression using the DFNF normal form. Then, we apply the previously introduced split strategy to every map to be blocked, recursively going from innermost to outermost. Finally, we interchange dimensions accordingly. In the following, we first introduce the required normalforms (e.g., DFNF), then explain how we recursively traverse (fmap) to apply loop-blocking and finally briefly explain how we interchange dimensions in Rise (interchange).
Normal forms In Elevate, we introduced normalize to ensure that expressions are in a particular form expected by the implementation of rewrite rules. λ-calculus (and Rise) allows for semantically equivalent but syntactically different expressions. For example, fun(x => f(x)) is equivalent to f iff x does not appear free in f. Transforming between these representations is called η-reduction and η-abstraction.
The simplest normal-form we use is the βη-normal-form (BENF) which exhaustively applies βand η-reduction: As not every function abstraction is η-reducible, the function arguments of Rise's higher-order patterns map and reduce might have different forms. Therefore, we introduce a normal form making the data flow explicit by ensuring a function abstraction is present in every higher order pattern: The definition shows the normalization for map. A similar case exists for reduce. Using the not and isFun predicates, that are themselves Elevate strategies, we describe the desired form in a natural and elegant way.
Recursively Applying Loop-Blocking In order to recursively apply the loop blocking strategy to nested maps, we make use of the Rise-specific traversal fmap: def fmap(s:Strategy[Rise])=function(argOf(map,body(s))) fmap essentially traverses to the function argument of a map primitive and applies the given strategy s. For example, fmap(fmap(split(n)))(DFNF(map(map(map(f))))) skips two maps applying loop-blocking to the innermost map.
Interchange in tile After recursively blocking all map s, we use interchange to rearrange the dimensions in the correct order. For simplicity, we describe the two dimensional case: after loop-blocking the data is four-dimensional and we must swap the two inner dimensions. To achieve this we introduce two transpose patterns and then move one of the transpose into the right position. Doing it this way every strategy is a semantics-preserving transformation ensuring the correctness of the overall optimization.

Reordering as an Elevate Strategy
Due to the loopless nature of Rise, implementing TVM's reorder primitive as a strategy is more complicated. Instead of simply interchanging perfectly nested loops, the same is achieved in Rise by interchanging the nesting of map and reduce patterns. Therefore, there are multiple possible combinations to consider and the implementation of each rewrite rule requires reasoning about why exchanging the specific patterns is possible in the first place.
We implemented a reorder strategy in Elevate but its implementation is non-trivial and, therefore, it is not discussed here. While it is possible to implement TVM's reorder primitive, this particular loop transformation is just not a good fit for the pattern-based abstractions in the Rise language.

Matrix Multiply Schedules as Elevate Strategies
Using the TVM-like scheduling abstractions implemented as Elevate strategies, we are now able to discuss how we combine them together to describe entire schedules in Elevate.
For baseline, TVM does not provide a schedule, but we describe the implicit behaviour of the compiler explicitly: The TVM algorithm computes the dot product in a single statement. The Rise program describes the dot product with separate patterns which are fused using fuseReduceMap. The lowerToC strategy lowers every high-level pattern into its low-level sequential version: map is rewritten into mapSeq and reduce into reduceSeq.

(loopPerm ';' lowerToC)(mm)
For the array packing version, we are not required to change the Rise program manually, but can apply the array packing of matrix B as a rewrite step. Afterwards, we can reuse the loopPerm strategy before the packed representation of B is vectorized and then copied in parallel.  For the parallel version, we reuse the prior array packing strategy only changing the way we lower the high-level code. We parallelize the outermost loop with topDown(parallel) and unroll the innermost reduction using bottomUp(isReduce ';'unroll) before lowering the remaining high-level patterns to sequential code as before. We have demonstrated that it is feasible to implement a TVM-like scheduling language in Elevate by expressing schedules as compositions of reusable strategies.

Experimental Evaluation
In order to evaluate the practicability and the scalability of Elevate, we performed two experiments.

Number of Rewrite Steps
In the first experiment, we are interested in the scalability of our approach by counting the number of successfully applied rewrites steps performed when applying a strategy to the Rise matrix multiplication expression. Figure 7 shows this number for every strategy shown in the previous subsection. Since no major optimization strategies are applied to the baseline version, only 211 rewrite steps are performed. However, as soon as interesting optimizations are applied, we easily reach about 100,000 steps for the next three versions and about 150,000 for the most complicated optimizations. The loop-permutation case slightly drops in numbers of applied rewrite rules because the specific nesting prescribed in TVM's schedule required fewer loop-interchanges.
These high numbers clearly show that abstractions are required to control this many rewrite steps. It also shows the scalability of our compositional approach in which complex optimizations are composed out of a small set of fundamental building blocks. The high-level strategies encode practical optimizations and hide massive numbers of individual rewrite steps that are actually performed. Overall, applying the strategies to the Rise expression took less than 50 seconds per version on a commodity notebook. Performance Comparison In the second experiment, we are interested in the performance achieved when optimizing Rise programs with Elevate compared to TVM. Ideally, the code optimized with Elevate should be similar to the TVM-generated code and achieve competitive performance. We generated LLVM code with TVM (version 0.6.dev) and C code for Rise annotated with OpenMP pragmas for the version which include parallelization or vectorization. The Rise generated C code was compiled with clang (v.9.0.0) using -Ofast -ffast-math -fopenmp which echoes the settings used by TVM and Halide 4 . The measurements were performed on an Intel core i5-4670K CPU (frequency locked to 3.4GHz) running Arch Linux (kernel 5.3.11-arch1-1). We measured wall-time for Rise-generated code and used TVM's built-in measurement API. We measured 100 iterations per version reporting the median runtimes in milliseconds. Figure 8 shows the performance of Rise and TVM generated code using a logarithmic scale. The code generated by Rise controlled by the Elevate optimization strategies performs competitive to TVM. Similar to the results of the Halide case study, our experiment shows a matching trend when comparing to TVM's versions with equivalent optimizations. The most optimized parallel Rise generated version improves the performance over the baseline by a factor of about 110x. This means that the strategies we developed using Elevate, that are defined in an extensible style by composing individual rewrite steps, scale to a level where they actually encode practically useable and relevant optimizations.

Related Work
Term Rewriting and Strategy Languages Elevate is inspired by existing strategy languages, especially ELAN [7,8] and Stratego [39,41], which introduce combinators to support user-defined strategies in the context of term rewriting systems. Similar rewriting systems include [2,9,14,17,20,29,36]. Program transformations using rewrite rules and strategy languages have since been used in many different domains including reverse engineering [13], refactoring [18], and obfuscation [15]. Visser [38,40] and Kirchner [24] provide surveys covering term rewriting, strategy languages and their application domains.
To the best of our knowledge, Elevate is the first strategy language that has been used to specify state-of-the-art compiler optimizations such as tiling focusing on high performance code generation.

Rewriting in Compilers
Rewrite rules and rewriting strategies have also been used when building compilers. The Glasgow Haskell Compiler [28] uses rewrite rules as a practical way to optimize Haskell programs and Visser et. al. [41] describe how to build program optimizers using rewriting strategies. Other areas include building interpreters [16], instruction selection [10] or constant propagation [26]. More recently, Lift [21,33,35] showed how to use rewrite rules to generate high-performance code targeting accelerators.
Controlling the application of rewrite rules in compilers still largely is built-in in a fixed way based on heurisitcs. In this work, we showed how to use Elevate instead, allowing a more flexible and practical approach towards using rewrite rules for describing optimizations in compilers.
These existing scheduling APIs are not designed as principled programming languages. Instead, a fixed set of ad-hoc built-in primitives is exposed allowing users to specify which optimizations to apply. In this work, we showed how to use Elevate to implement scheduling languages from first principles as composition of rewrite rules.

Conclusion
In this paper, we presented Elevate: a language for describing optimization strategies. Elevate follows a tradition of prior systems used in different contexts that express optimization strategies as composition of rewrites. We showed that, in contrast to existing systems with scheduling APIs such as Halide and TVM, programmers are not restricted to a set of built-in optimizations but define their own optimization strategies. Using three case studies, we demonstrated Elevate's flexiblity to rewrite different languages ( F and Rise), its extensibility to add custom abstractions inlcuding domain-specific optimizations, and its practicality to scale to complex optimization strategies requiring 150k rewrite steps used in deep learning. We showed that Elevate successfully optimizes programs in the Rise language achieving competitive performance compared to Halide and TVM.