Improving LLVM Alias Analysis

This page tracks the information and progress relevant to improving the alias analysis pass for the LLVM backend of GHC.

LLVM Alias Analysis Infrastructure

Some links to the various documentation on LLVM's AA support:

•  LLVM Alias Analysis Infrastructure
•  LLVM's Analysis and Transform Passes
•  The Often Misunderstood GEP Instruction
•  LLVM Language Reference
•  LLVM Dev List: Comparison of Alias Analysis in LLVM

Max's Work

Max had a crack at writing a custom alias analysis pass for LLVM, relevant links are:

•  Email to LLVM dev
•  Blog post about results

TBAA

LLVM as of version 2.9 includes Type Based Alias Analysis. This mean using metadata you can specify a type hierarchy (with alias properties between types) and annotate your code with these types to improve the alias information. This should allow us to improve the alias analysis without any changes to LLVM itself like Max made.

•  LLVM TBBA Doc

STG / Cmm Alias Properties

Question (David Terei): What alias properties does the codegen obey? Sp and Hp never alias? R<n> registers never alias? ....

Answer (Simon Marlow): Sp[] and Hp[] never alias, R[] never aliases with Sp[], and that's about it.

LLVM type system

The above aliasing information can be encoded as follows:

!0 = metadata !{ metadata !"top" }
!1 = metadata !{ metadata !"heap", metadata !0 }
!2 = metadata !{ metadata !"stack", metadata !0 }
!3 = metadata !{ metadata !"rx", metadata !1 }

The fact that R[] never aliases with Sp[] is never used as the one way relation isn't expressible in LLVM.

Stores/loads needs to be annotated with !tbaa and one of the above four types e.g.

%ln1NH1 = load i64* %Sp_Arg, align 8, !tbaa !2

Progress

David and Johan plan to have a crack at this at the start of 2012.