Master's Thesis

Optimistic Global Value Numbering for Compilers with Undefined Behavior

Manuel José Gomes Brito2024

Key information

Authors:

Manuel José Gomes Brito (Manuel Brito)

Supervisors:

Nuno Claudino Pereira Lopes (Nuno P. Lopes); Alina Sbîrlea

Published in

11/11/2024

Abstract

Compilers play a vital role in modern software systems by bridging the gap between high-level programming languages and the underlying hardware. With the rise of highly specialized languages and diverse hardware platforms, the complexity of compilation has increased. This complexity is managed using intermediate representations (IR), which enable machine-independent optimizations such as Global Value Numbering (GVN). GVN identifies and eliminates redundant computations by assigning value numbers to equivalent expressions. However, traditional GVN faces challenges in detecting more complex redundancies, particularly in loops and partially redundant computations. This thesis introduces a GVN algorithm tailored for SSA-based intermediate representations, enhancing the precision and efficiency of GVN through techniques like algebraic simplification, partial redundancy elimination (PRE), unreachable code elimination (UCE), and the optimistic assumption. By leveraging extensions like Static Single Information (SSI) and Memory SSA (MSSA), our approach improves value numbering for memory operations and predicates, allowing for the detection of complex redundancies in both scalar and memory-based computations. Our solution, implemented within the LLVM compiler, demonstrates performance improvements of up to 30\% over existing implementations in LLVM. Additionally, the combination of optimizations enables unique transformations, such as loop-invariant code motion. However, the study also highlights cases where value numbering can degrade performance, underscoring the importance of careful optimization pipeline design.

Publication details

Authors in the community:

Supervisors of this institution:

Fields of Science and Technology (FOS)

electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering

Publication language (ISO code)

eng - English

Rights type:

Embargoed access

Date available:

09/04/2025

Institution name

Instituto Superior Técnico