Use load/store metadata to improve LLVM alias analysis

The idea here is to use metadata to tell LLVM that memory operations targeting (a) the heap, (b) the A stack, and (c) global variables cannot alias each other. This improves dead store elimination.

The following discussion from !16 (merged) should be addressed:

• @camilstaps started a discussion: (+6 comments)

  This answers my question about the description of the assert above. I was assuming that hp and asp would not be used when using globals, only hp_global and asp_global. But you use hp and asp locally and only write them out when needed.

  I would expect LLVM to combine multiple writes to the same global in dead store elimination. In

  @g = external global i32
  
  declare void @ext()
  
  define void @f(i1 %c) {
    store i32 1, ptr @g             ; eliminated
    br i1 %c, label %a, label %b
  
  a:
    store i32 2, ptr @g             ; not eliminated
    call void @ext()
    store i32 5, ptr @g             ; not eliminated
    ret void
  
  b:
    store i32 3, ptr @g             ; not eliminated
    ret void
  }

  The first store is eliminated by the pass, but the second is not because ext() may use g. I think this is the behavior you need here as well.

  For this to work across loads/stores to pointers, we need to tell LLVM that those pointers cannot alias the globals, using alias metadata:

  @g = external unnamed_addr global i32
  
  !0 = !{!0} ; the globals domain
  !1 = !{!1} ; the heap domain
  !2 = !{!2} ; the asp domain
  
  !3 = !{!3, !0} ; the globals scope
  !4 = !{!4, !1} ; the heap scope
  !5 = !{!5, !2} ; the asp scope
  
  !6 = !{!3} ; the globals scope list
  !7 = !{!4} ; the heap scope list
  !8 = !{!5} ; the asp scope list
  
  !9  = !{!4, !5} ; everything except the globals scope list
  !10 = !{!3, !5} ; everything except the heap scope list
  !11 = !{!3, !4} ; everything except the asp scope list
  
  declare void @ext()
  
  define i1 @f(ptr %p) {
    store i32 1, ptr @g, !alias.scope !6, !noalias !9    ; eliminated, because LLVM knows that %p cannot alias @g and therefore %c will not depend on this store
    %c = load i1, ptr %p, !alias.scope !7, !noalias !10
    store i32 5, ptr @g, !alias.scope !6, !noalias !9
    ret i1 %c
  }

  This looks complicated, but !0 through !11 is boilerplate, so it really comes down to adding alias.scope and noalias metadata to all memory instructions. Here I have defined three mutually disjoint scopes, for globals, heap, and A stack. If using this method for the A stack, the latter is not needed. But if the A stack is implemented as it is now, it may be independently useful to use alias metadata to inform LLVM that heap and stack pointers cannot alias each other.