[LLVMdev] [RFC] Scoped no-alias metadata (redux)

[Hal Finkel]

Hello everyone,

In December, I had started a thread on scoped no-alias metadata in order to represent C99 'restrict' pointer information at the IR level:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-December/056586.html

At this point, we also have another important use case: preserving the existing 'noalias' attributes on pointers after inlining. My original proposal was technically flawed, and based on the original feedback, and subsequent discussions with Arnold and Andy, a new scheme has emerged:

First, we'll add some metadata to define a hierarchy of scopes. For preserving noalias during function inlining, the inliner will fabricate a unique scope node for the inlined function (and then tag all memory accesses in the function). For use in representing C99 restrict pointers, a scope may represent the entire function, or some other statement block within the function (or a block within a block, etc.) created by the frontend.

As in my previous proposal, and similar to how TBAA is implemented, we define some scopes:
!scope0 = metadata !{ metadata !"scope of foo()" }
!scope1 = metadata !{ metadata !"scope 1", metadata !scope0 }
!scope2 = metadata !{ metadata !"scope 2", metadata !scope0 }
!scope3 = metadata !{ metadata !"scope 2.1", metadata !scope2 }
!scope4 = metadata !{ metadata !"scope 2.2", metadata !scope2 }

The language reference defines 'noalias' as indicating "that pointer values based on the argument or return value do not alias pointer values which are not based on it...", and so we need to tag all loads and stores in some scope with the scope metadata, and then additionally tag the 'noalias' loads and stores that don't alias with the various loads and stores in that scope (not just with the other noalias loads and stores).

  = load %ptr1, !alias.scope !scope1
  = load %ptr2, !alias.scope !scope1, !noalias !scope1

Generally, when BasicAA is evaluating an aliasing query, if one of the instructions is associated with an alias.scope id that is identical to the noalias scope associated with the other instruction, or is a descendant (in the scope hierarchy) of the noalias scope associated with the other instruction, then the two memory accesses are assumed not to alias. When merging two instructions with noalias metadata, if the transformation wants to maximally preserve the information, it can add both noalias metadata references to the new 'merged' instruction (likewise, all alias.scope references should be added).

This scheme should allow us to preserve noalias when inlining, and also adequately model C99 restrict semantics, in addition to being useful for other frontends.

If anyone has any feedback, please share.

Thanks again,
Hal

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory