The Deep Learning Compiler: A Comprehensive Survey <s> Graph Representation. <s> We show that reverse-mode AD (Automatic Differentiation)—a generalized gradient-calculation operator—can be incorporated as a first-class function in an augmented lambda calculus, and therefore into a functional-programming language. Closure is achieved, in that the new operator can be applied to any expression in the augmented language, yielding an expression in that language. This requires the resolution of two major technical issues: (a) how to transform nested lambda expressions, including those with free-variable references, and (b) how to support self application of the AD machinery. AD transformations preserve certain complexity properties, among them that the reverse phase of the reverse-mode AD transformation of a function have the same temporal complexity as the original untransformed function. First-class unrestricted AD operators increase the expressive power available to the numeric programmer, and may have significant practical implications for the construction of numeric software that is robust, modular, concise, correct, and efficient. <s> BIB001 </s> The Deep Learning Compiler: A Comprehensive Survey <s> Graph Representation. <s> Frameworks for writing, compiling, and optimizing deep learning (DL) models have recently enabled progress in areas like computer vision and natural language processing. Extending these frameworks to accommodate the rapidly diversifying landscape of DL models and hardware platforms presents challenging tradeoffs between expressivity, composability, and portability. We present Relay, a new compiler framework for DL. Relay's functional, statically typed intermediate representation (IR) unifies and generalizes existing DL IRs to express state-of-the-art models. The introduction of Relay's expressive IR requires careful design of domain-specific optimizations, addressed via Relay's extension mechanisms. Using these extension mechanisms, Relay supports a unified compiler that can target a variety of hardware platforms. Our evaluation demonstrates Relay's competitive performance for a broad class of models and devices (CPUs, GPUs, and emerging accelerators). Relay's design demonstrates how a unified IR can provide expressivity, composability, and portability without compromising performance. <s> BIB002
The graph representation in DL compilers adopts the approach of traditional computational graph, which is composed of data and operator. Data organization -DL compilers always establish their computational graph by multi-level node. Taking Relay as an example, Figure 4 (a) shows the data structure used to represent the computational graph. Relay divides its whole computational graph into smaller graphs called schedule nodes for the organization. A schedule node is composed of many stage nodes, and it forms a DAG graph. Each stage node has precisely one operator node to represent a computational operator, such as ComputeOp or TensorComputeOp. Operator node is also used to originate the relation between iterator variables. Besides, Relay combines the iterator variables in their graph data structure for bound inference. Relay organizes iterator variables hierarchically by its multi-level node mentioned above, and  shows the data structure of iterator variables kept by the related node at each level. In the schedule level, there will keep a bound map for necessary iterator variables, which can be obtained by every stage node. Each stage node manages its iterator variables. Iterator variables in one stage node can be classified into leaf variables and root variables. The former determines the ranges in specific operators and the latter figures out the loop dimension. Bound inference -The compiler needs to ensure the range of every iteration variable when performing optimizations. However, some computation representation does not intuitively point the scope of loop variables. Instead, those computation forms only offer information about the input and output. Thus, the bound inference process is needed to determine the variable ranges. The bound inference algorithm can be divided into two classes by the inference direction as follows: • From output to input: The inference of TVM is from output to input. It is related to its expression form, tensor expression, which needs the shape of output directly. Relay handles the inference process by a pass called InferBound pass, and Figure 5 shows the pseudo-code and the schematic diagram. The input is a schedule node, which contains a series of stage nodes. First, Relay will establish its dataflow graph whose nodes are stage nodes. Then, a reverse topological sort is performed to gain a list that guarantees the consumer nodes are before input nodes for it. That gives the inference process a primary hypothesis: when it comes to one stage, the shape of its output is already known. For each node, the inference pass will determine the range of root iterator variables first, using the shape of its output tensor. Then, Relay will figure out the leaf iterator variables by the relation of iterator variables and their relation recorded by stage node. The relation includes split, fuse,and rebase. The dependency of variables organized by that relation can be analyzed easily. Considering spilt node as an example. When facing a given factor, the ranges of a variable will be divided into (0, factor) and (factor, extend) if no cross-border. The bound results of root variables will be kept in the global map for other stage nodes to use. • From input to output: Einstein notation (used by TC IR) makes the programming more concise by inferring index ranges automatically, but it is based on the understandable rules of inference. Just as mentioned above, there are operators that the Einstein notation cannot deal with and needs the user to add where clause to guide the compiler. If one needs to take lots of time to consider which expression should use the where clause, he would prefer to write the loop explicitly and give up the TC IR. Trying to avoid that embarrassment, TC adopts a straightforward approach in the inference algorithm, which is inspired by Presburger arithmetic implemented in polyhedral libraries  . The problem solved by inference is seeking ranges of all undefined variables as large as possible under the constraint that indexes cannot get over the bounds of input. The process is iterative. First, the algorithm initializes a list for all unsolved variables which are not constrained by where clause. Then, the algorithm will find one expression that only has a single unresolved variable and use Halide function slove_for_inner_interval to find the maximum range under the existing conditions for this variable. Then the solved variable will be removed from the unsolved list. The algorithm repeats the second step until the list is empty. If the expression with a single unsolved variable does not exist and the unsolved list is not empty, the compiler will stop inference and request for where from the user. Another challenge for inference is the recurrent definition, which is not supported by the first release, making TC fails in implementing RNN. Data representation -The representation of data in DL compilers includes input, weights, and variables. Some compilers represent data directly by specific pointers, while others use Placeholder or other designs to point to data indirectly. The data representation contains not only specific values but also other related information. Due to the requirement of graph optimization, mainstream DL compilers prefer to add data layout information to the data representation. The data representations of different compilers are shown as follows. • Placeholder: Placeholder is widely used in symbolic programming. The compiler using placeholders has no information about the concrete tensor. Besides, it is convenient for the programmer to change the input and output shape by using placeholders instead of changing the whole semantics. During the compiling process, the placeholders can be replaced with different tensors without changes of semantic. TVM uses placeholders in its tensor expression language as a method to construct an empty tensor object. • Unknown shape representation: TVM uses Any to represent an unknown dimension in order to support the dynamic model. The Any can be used in tensor type definition as one of the dimensions of the tensor shape. Unlike placeholder, the shape contains Any is unknown at complication time, so the work on inference and checking dimension need to be relaxed, and additional shape function is necessary for guaranteeing memory validity. • Data layout: There are three perspectives on the data layout of compilers: from operator view (TVM, Glow, PlaidML), from backend view (XLA), and tensor view (Relay, MLIR). The former regards data layout as additional or necessary parameters of operators and requires such information for computation and optimization. Combining data layout information with operator rather than tensor enables intuitive implementation for certain operator, and compiler prefers to regard the data layout as a parameter rather than a field for operator in order to reduce dynamic consumption during compilation [4] . XLA regards data layout as constraints related to its backend device: CPU and GPU. For example, when a constant array is used by dot operator only in CPU backend, XLA will require the array to be column-major. Relay and MLIR are going to add layout information into the type system for tensor. Operators supported -The computational operators provided by DL compilers can be divided into three levels: basic calculation nodes, high-level calculation nodes, and fused calculation nodes. The basic nodes are the components of the whole operational space, such as exponent arithmetic. The high-level nodes include the units of the neural network models such as convolution and pooling. And the fused nodes represent the nodes fused by the graph optimizations. Besides, some compilers also support customized operators, which also belongs to computational operators. The support of customized operator is one of the most basic designs for extensibility, which allows users to define their operators for new backend instructions or just for technical needs. The support of the customized operators can be divided into two levels: node level and operator level. There are a large number of operators supported in DL compilers. Here we choose four operators that are representative and most frequently used across different DL compilers for illustration. • Broadcasting: Without broadcasting operators, the input shape of the operator would be stricter. For example, in an add operator, the input tensors are expected to be of the same shape. Some compilers like XLA and Relay relax the restrictions, which offer an operator called broadcasting. For example, XLA allows the element-wise addition to acts on a matrix and vector by replicating the vector until its shape is the same as the matrix. • Predication: Original prediction is a widely used method for deciding the code to execute by judging a condition before execution. The condition is always be pointed with a Boolean flag, and the false means related code should not be executed. Predication can also be used as a method in the control flow, such as avoiding the illegal division by non-zero determination. Compilers may redefine the semantic of predication due to different implementations. Glow regards predication as an optimization, and it means that the backend can ignore the content if the execution of predication does not accelerate the program [4] . The accelerating scene can be found in RNN implement by avoiding some computation brought by the different batch sizes. However, Glow hypothesizes that the prediction does not affect the main semantic of the program, which means that the prediction in Glow is not allowed in codes related to the control flow. TVM provides an assert statement that fits Halide IR as well as Python AST  . • Automatical differentiation: Glow differentiates its computational graph automatically by lowering the gradients and high-level differentiation operators like stochastic gradient descent (SGD) into low-level operators such as additive and multiplicative. By doing that, Glow can support the backends without the implementation of complex operations for training. Inspired by the reverse-mode BIB001 , Relay represents partial derivative by specific type, and the related gradient node is rewritten by transforming the inner AST. • Control flow: In graph IR, control flow is needed while representing complex and flexible models like RNN. Relay notices that arbitrary control flow can be implemented by recursion and pattern, which has demonstrated by the functional programming community BIB002 . Therefore, Relay provides if operator and recursive function for implementing control flow, which means one needs to implement while loop by judgment and jump manually. On the contrary, XLA represents control flow by special HLO operators, while and conditional.XLA has already implemented the control flow operators by a series of basic HLO operations.