The Deep Learning Compiler: A Comprehensive Survey <s> Low-level IR <s> In optimizing compilers, data structure choices directly influence the power and efficiency of practical program optimization. A poor choice of data structure can inhibit optimization or slow compilation to the point that advanced optimization features become undesirable. Recently, static single assignment form and the control dependence graph have been proposed to represent data flow and control flow properties of programs. Each of these previously unrelated techniques lends efficiency and power to a useful class of program optimizations. Although both of these structures are attractive, the difficulty of their construction and their potential size have discouraged their use. We present new algorithms that efficiently compute these data structures for arbitrary control flow graphs. The algorithms use {\em dominance frontiers}, a new concept that may have other applications. We also give analytical and experimental evidence that all of these data structures are usually linear in the size of the original program. This paper thus presents strong evidence that these structures can be of practical use in optimization. <s> BIB001 </s> The Deep Learning Compiler: A Comprehensive Survey <s> Low-level IR <s> Since its inception as a student project in 2001, initially just for the handling (as the name implies) of convex polyhedra, the Parma Polyhedra Library has been continuously improved and extended by joining scrupulous research on the theoretical foundations of (possibly non-convex) numerical abstractions to a total adherence to the best available practices in software development. Even though it is still not fully mature and functionally complete, the Parma Polyhedra Library already offers a combination of functionality, reliability, usability and performance that is not matched by similar, freely available libraries. In this paper, we present the main features of the current version of the library, emphasizing those that distinguish it from other similar libraries and those that are important for applications in the field of analysis and verification of hardware and software systems. <s> BIB002 </s> The Deep Learning Compiler: A Comprehensive Survey <s> Low-level IR <s> In compiler research, polytopes and related mathematical objects have been successfully used for several decades to represent and manipulate computer programs in an approach that has become known as the polyhedral model. The key insight is that the kernels of many compute-intensive applications are composed of loops with bounds that are affine combinations of symbolic constants and outer loop iterators. The iterations of a loop nest can then be represented as the integer points in a (parametric) polytope and manipulated as a whole, rather than as individual iterations. A similar reasoning holds for the elements of an array and for mappings between loop iterations and array elements. <s> BIB003
4.3.1 Implementation of Low-Level IR. Low-level IR describes the computation of a DL model in a more fine-grained representation than that in high-level IR, which enables the target-dependent optimizations by providing interfaces to tune the computation and memory access. It also allows the developer to make use of mature third-party tool-chains in compiler backend such as Halide  and polyhedral model [13] . In this section, we classify the low-level IRs into three categories: Halide based IRs, polyhedral model based IRs, and other unique IRs. Halide based IRs -Halide is firstly proposed to parallelize image processing, and it is proven to be extensible and efficient in DL compilers by TVM. The basic concept of Halide is the separation of computation and scheduling. Rather than giving a specific scheme directly, The compilers adopting Halide will try various possible scheduling and choose the best one. The original IR of the Halide needs to change on design and implementation when be used in DL compiling problem. For example, the shape of Halide's input is infinite, while the DL compilers need to know the exact shape of data in order to map the operator to hardware instructions. Some compilers, such as TC, need the fixed size of data, considering tensors in ML application have higher temporal locality than in general programs. TVM has isolated the Halide based IR from the original Halide program and improved it into an independent symbolic IR by following efforts [7] . First, TVM removes the dependency on LLVM of the original Halide IR. The structure of both project module and IR overall design of the Halide have been reorganized, pursuing better logical and publicly accessible from graph IR and frontend language such as python. The re-usability is also considered in order to add customized operators easily by introducing a runtime dispatching mechanism. TVM changes the variable definition from string matching to pointer matching, guaranteeing single define location for each variable as the static single-assignment (SSA) BIB001 , which is useful for further optimization. Polyhedral model based IRs -The polyhedral model is another important reference for DL compilers. It uses linear programming and other mathematical methods to optimize loopbased codes where the control flow of bounds and branches is static. The polyhedral model based IR undergoes multiple polyhedral transformations (e.g., fusion, tiling, sinking, and mapping), including both device-dependent and device-independent optimization. When targeting a specific architecture, polyhedral transformations involve changes in scheduling and mapping strategies. The main optimization space in the polyhedral model is loop lowering, such as iteration step and loop level. The polyhedral model always uses various specific nodes to present the semantics of the program, which will be introduced below. Further optimizations are also based on such nodes. There are many toolchain which can be borrowed by Polyhedral-based compilers, such as isl BIB003 , Omega  , PIP  , Polylib  , and PPL BIB002 . Because of the ability to deal with numerous deeply nested loops, many DL compilers, such as Tensor Comprehension (TC) and PlaidML, use the polyhedral model with or without modifications. TC has its unique design in low-level IR, which combines the Halide and polyhedral model. It uses Halide based IR to represent the computation, but it adopts the polyhedral model based IR to represent the loop structures. So the loop structures can be optimized using polyhedral techniques. TC presents detailed expressions by abstracted instances and introduces specific node types, and some of them are similar to the original polyhedral model. The node and their function can be described as Table 3 . In brief, TC uses the domain node to specify the ranges of index variables and uses context node to introduce new iterative variables that related to hardware, such as the size of block for GPU. A band node determines the order of iterations. A filter node represents an iterator combined with a statement instance. Set and sequence are keywords to specify the execution type for filters, set for parallelism, and sequence for serial execution. Besides, TC uses extension nodes to introduce other necessary instructions for code generation, such as the memory movement statement.