This is the first in a series of patches to extend the scoped-noalias metadata implementation by providing an intrinsic for implicit alias scope assignment (in contrast to the alias.scope metadata which provides explicit scope assignment).
The general design for this was discussed at the end of last year (http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-November/078786.html), and while there will need to be further extensions (to support dynamic predicates, at least), this should address two core motivations:
- Provide a way to retain dominance information which is necessary to answer loop-sensitive queries
- Make it practical to use scoped-noalias metadata to model block-level restrict-qualified pointers from Clang.
To summarize from the llvmdev e-mail, the problem underlying (1) is that, when using the existing metadata scheme, we cannot differentiate between these two after inlining:
void foo(float * restrict a, float * restrict b) {
for (int i = 0; i < 1600; ++i)
a[i] = b[i] + 1;
}and:
void inner(float * restrict a, float * restrict b) {
*a = *b + 1;
}
void foo(float * a, float * b) {
for (int i = 0; i < 1600; ++i)
inner(a+i, b+i);
}and we currently cheat and assume the former to enable vectorization. This is not correct, however, and the underlying issue is that the current scheme cannot differentiate directly between:
- Does access A alias with access B, both in loop L, within a loop iteration
- Does access A alias with the memory accessed by B is any loop iteration
the existing metadata really only can answer (a) but the vectorizer needs (b). The existing noalias attribute (like the restrict-qualifier on which it is based) does provide the necessary information (because it applies to all derived pointers, and thus those used in every loop iteration), but we loose it when converting to the existing metadata scheme.
Regarding problem (2), while in theory block-level restrict-qualified pointers can be modeled using the existing metadata scheme, it suffers from a lack of dominance information (from problem (1)), and is also difficult to apply in practice. The core issue is that to determine whether or not a variable is derived from some particular restrict-qualified pointer, you need to determine which accesses might be derived from that pointer via some capture. This is much easier to do after optimization (mem2reg, funcattrs to add nocapture attributes, etc.) than in the frontend directly. In practice, we really want to delay this determination until later in the pipeline (and not try to do it in the frontend).
To address these concerns, we'll add a new intrinsic for implicit scope assignment. The scope, in the sense of modeling restrict-qualified pointers, represents the set of restrict-qualified pointers from which some access might derive. This can be explicitly represented with alias.scope metadata. Then the noalias metadata specified with which scopes the tagged access does not alias. To use the new intrinsic, llvm.noalias, you tag all potentially relevant accesses with noalias metadata and derive all pointers in a particular scope from the return value of the llvm.noalias intrinsic with that scope as an argument. The reason that all relevant accesses need to have noalias metadata, including those using pointers derived from the noalias intrinsic, is a compile-time optimization: we don't need to search for noalias intrinsics, a potentially expensive operation, if there is no noalias metadata tag, and thus, there should be no significant cost to the feature if you're not using it.
One issue (directly relevant in a later patch providing the implementation), is that the scope list provided as the metadata argument can have only one item. This is because we need the ability to search for other intrinsics with the same scope argument, and because metadata no longer have use lists, we can do this only by searching the use list of the MetadataAsValue wrapper (and, as a result, can only find complete matches, so we need to have trivial lists). This may be something we wish to address is some different way, because as it stands, we cannot combine adjacent noalias intrinsics.
To bring up a naming issue: I named the intrinsic llvm.noalias because it is like the noalias function argument. However, conceptually, is serves the same purpose as the alias.scope metadata (and works along with the noalias metadata, which is still needed), so maybe it should be named llvm.alias.scope?
Also, on the data dependence, while poses obvious difficulties on the optimizer (and may of the patches are to address this), a strict control dependence is not sufficient (so we can't make it more like the lifetime intrinsics which take a pointer argument). Specifically, we need to be able to represent this kind of construct:
void foo(T * restrict x, T * restrict y) {
for (int i = 0; i < 1600; ++i)
x[2*i+1] = y[2*i] + 1;
}when inlined from the call foo(q, q).
This wording is a little odd.
I realize you are trying to say something about other pointers, but this intrinsic is really saying something about the accesses with the right metadata, not about their pointers.
(unless there's something i missed, and the fact that a pointer has the right noalias data in one access also implies something about that pointer when used in an access *not* in the right scope)
So i would say "llvm.noalias allows the assume that accesses using pointers derived from the return value don't alias with those accesses tagged with associated noalias scopes"
or something
You also need to very carefully define "derived".
Derived could mean a lot of things (IE if i ptrtoint it, add 6, and intoptr it, is it still derived?)