Lune

PLDI2020Top-tier venue

OOElala: order-of-evaluation based alias analysis for compiler optimization

Ankush Phulia, Vaibhav Bhagee, Sorav Bansal

Abstract

In C, the order of evaluation of expressions is unspecified; further for expressions that do not involve function calls, C semantics ensure that there cannot be a data race between two evaluations that can proceed in either order (or concurrently). We explore the optimization opportunity enabled by these non-deterministic expression evaluation semantics in C, and provide a sound compile-time alias analysis to realize the same. Our algorithm is implemented as a part of the Clang/LLVM infrastructure, in a tool called OOElala. Our experimental results demonstrate that the untapped optimization opportunity is significant: code patterns that enable such optimizations are common; the enabled transformations can range from vectorization to improved instruction selection and register allocation; and the resulting speedups can be as high as 2.6x on already-optimized code.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Towards Removing Undef Values from LLVM IRPedro Lobo, John McIver, George Mitenkov, Juneyoung Lee et al.PLDI 2026

Related papers

  1. Relaxing Alias Analysis: Exploring the Unexplored SpaceMichel Weber, Theodoros Theodoridis, Zhendong SuPLDI 2025 · 1 citation
  2. The road not taken: exploring alias analysis based optimizations missed by the compilerKhushboo Chitre, Piyus Kedia, Rahul PurandareOOPSLA 2022 · 13 citations
  3. Visibility Algorithms for Dynamic Dependence Analysis and Distributed CoherenceMichael Bauer, Elliott Slaughter, Sean Treichler, Wonchan Lee et al.PPoPP 2023 · 6 citations
  4. Semiring optimizations: dynamic elision of expressions with identity and absorbing elementsGuilherme V. Leobas, Fernando Magno Quintão PereiraOOPSLA 2020 · 9 citations
  5. Accurate Static Data Race Detection for CEmerson Sales, Omar Inverso, Emilio TuostoFM 2024 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines