Equality Saturation for Optimizing High-Level Julia IR

• URL: http://arxiv.org/abs/2502.17075v1
• Date: Mon, 24 Feb 2025 11:40:49 GMT
• Title: Equality Saturation for Optimizing High-Level Julia IR
• Authors: Jules Merckx, Tim Besard, Bjorn De Sutter,
• Abstract summary: We have developed a system that allows domain experts to express rewrite rules to optimize code in the Julia programming language.<n>We propose an ILP formulation for optimal e-graph extraction taking into account dominance properties for code reuse and introduce emphCFG skeleton relaxation to rewrite calls to pure functions.<n>Use cases demonstrate that our system can perform rewrites on high-level, domain-specific code, as well as on lower-level code such as Julia's broadcasting mechanism.
• Score: 3.4492141860812233
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Compilers are indispensable for transforming code written in high-level languages into performant machine code, but their general-purpose optimizations sometimes fall short. Domain experts might be aware of certain optimizations that the compiler is unable to apply or that are only valid in a particular domain. We have developed a system that allows domain experts to express rewrite rules to optimize code in the Julia programming language. Our system builds on e-graphs and equality saturation. It can apply optimizations in the presence of control flow and side effects. As Julia uses multiple dispatch, we allow users to constrain rewrite rules by argument types, and propagate type information through the e-graph representation. We propose an ILP formulation for optimal e-graph extraction taking into account dominance properties for code reuse and introduce \emph{CFG skeleton relaxation} to rewrite calls to pure functions as well as those with side effects. Use cases demonstrate that our system can perform rewrites on high-level, domain-specific code, as well as on lower-level code such as Julia's broadcasting mechanism. Finally, we analyze the required compilation time.

Related papers

• Trace is the Next AutoDiff: Generative Optimization with Rich Feedback, Execution Traces, and LLMs [19.89948665187903]
  We study a class of optimization problems motivated by automating the design and update of AI systems like coding assistants, robots, and copilots. We provide a Python, Trace, that efficiently converts a workflow optimization problem into an OPTO instance using PyTorch-like syntax.
  arXiv  Detail & Related papers  (2024-06-23T21:05:31Z)
• Should AI Optimize Your Code? A Comparative Study of Classical Optimizing Compilers Versus Current Large Language Models [0.0]
  Large Language Models (LLMs) raise intriguing questions about the potential of these AI approaches to revolutionize code optimization. This work aims to answer an essential question for the compiler community: "Can AI-driven models revolutionize the way we approach code optimization?" We present a comparative analysis between three classical optimizing compilers and two recent large language models.
  arXiv  Detail & Related papers  (2024-06-17T23:26:41Z)
• LLM as a Complementary Optimizer to Gradient Descent: A Case Study in Prompt Tuning [69.95292905263393]
  We show that gradient-based and high-level LLMs can effectively collaborate a combined optimization framework.<n>In this paper, we show that these complementary to each other and can effectively collaborate a combined optimization framework.
  arXiv  Detail & Related papers  (2024-05-30T06:24:14Z)
• CompilerDream: Learning a Compiler World Model for General Code Optimization [58.87557583347996]
  We introduce CompilerDream, a model-based reinforcement learning approach to general code optimization. It comprises a compiler world model that accurately simulates the intrinsic properties of optimization passes and an agent trained on this model to produce effective optimization strategies. It excels across diverse datasets, surpassing LLVM's built-in optimizations and other state-of-the-art methods in both settings of value prediction and end-to-end code optimization.
  arXiv  Detail & Related papers  (2024-04-24T09:20:33Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  We present Hierarchical cOntext MERging (HOMER), a new training-free scheme designed to overcome the limitations of large language models. HomeR uses a divide-and-conquer algorithm, dividing long inputs into manageable chunks. A token reduction technique precedes each merging, ensuring memory usage efficiency.
  arXiv  Detail & Related papers  (2024-04-16T06:34:08Z)
• ReGAL: Refactoring Programs to Discover Generalizable Abstractions [59.05769810380928]
  Generalizable Abstraction Learning (ReGAL) is a method for learning a library of reusable functions via codeization. We find that the shared function libraries discovered by ReGAL make programs easier to predict across diverse domains. For CodeLlama-13B, ReGAL results in absolute accuracy increases of 11.5% on LOGO, 26.1% on date understanding, and 8.1% on TextCraft, outperforming GPT-3.5 in two of three domains.
  arXiv  Detail & Related papers  (2024-01-29T18:45:30Z)
• LangProp: A code optimization framework using Large Language Models applied to driving [17.581983909703283]
  LangProp is a framework for iteratively optimizing code generated by large language models (LLMs) We show how LangProp can generate interpretable and transparent policies that can be verified and improved in a metric- and data-driven way.
  arXiv  Detail & Related papers  (2024-01-18T18:52:06Z)
• High-performance symbolic-numerics via multiple dispatch [52.77024349608834]
  Symbolics.jl is an extendable symbolic system which uses dynamic multiple dispatch to change behavior depending on the domain needs. We show that by formalizing a generic API on actions independent of implementation, we can retroactively add optimized data structures to our system. We demonstrate the ability to swap between classical term-rewriting simplifiers and e-graph-based term-rewriting simplifiers.
  arXiv  Detail & Related papers  (2021-05-09T14:22:43Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Flexible numerical optimization with ensmallen [15.78308411537254]
  This report provides an introduction to the ensmallen numerical optimization library. The library provides a fast and flexible C++ framework for mathematical optimization of arbitrary user-supplied functions.
  arXiv  Detail & Related papers  (2020-03-09T12:57:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.