Using program synthesis to select instructions for and optimize input programs is receiving increasing attention. However, existing synthesis-based compilers are faced by two major challenges that prohibit the deployment of program synthesis in production compilers: exorbitantly long synthesis times spanning several minutes and hours; and scalability issues that prevent synthesis of complex modern compute and data swizzle instructions, which have been found to maximize performance of modern tensor and stencil workloads. This paper proposes MISAAL, a synthesis-based compiler that employs a novel strategy to use formal semantics of hardware instructions to automatically prune a large search space of rewrite rules for modern complex instructions in an offline stage. MISAAL also proposes a novel methodology to make term-rewriting process in the online stage (at compile-time) extremely lightweight so as to enable programs to compile in seconds. Our results show that MISAAL reduces compilation times by up to a geomean of 16x compared to the state-of-the-art synthesis-based compiler, HYDRIDE. MISAAL also delivers competitive runtime performance against the production compiler for image processing and deep learning workloads, Halide, as well as HYDRIDE across x86, Hexagon and ARM.
Machine learning (ML) compilers rely on graph-level transformations to enhance the runtime performance of ML models, typically by applying a series of unverified, complex rewrite rules. The rewrite rules must account for the fact that tensor shapes, layouts and ranks may not be known at compile-time (i.e., tensor properties are determined at runtime – for instance, the sequence length of input texts fed into Large Language models is only available at runtime) which makes verifying them challenging. Moreover, compilers must apply rewrites so that they are conditionally applied only when certain constraints on symbolic tensor shapes, layouts, ranks, etc. are satisfied. We propose TensorEgg that enables formal verification of rewrites operating on tensors with polymorphic shapes, ranks and layouts, and uses a tensor rewrite system that applies these rules to ML computational graphs to enable compilation of dynamically-shaped tensors.