Optimistic Global Value Numbering for Compilers with Undefined Behavior

11/11/2024

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.

Authors in the community:

• 

  M

  Manuel Brito

  ist195623

Supervisors of this institution:

• 

  N

  Nuno P. Lopes

  ist155393

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

eng - English

Instituto Superior Técnico