Introduce llvm.noalias.decl intrinsic

[jeroen.dobbelaere]

Summary

The `llvm.experimental.noalias.scope.decl` intrinsic identifies where a noalias
scope is declared. When the intrinsic is duplicated, a decision must
also be made about the scope: depending on the reason of the duplication,
the scope might need to be duplicated as well.

[nikic]

llvm/docs/LangRef.rst

19619

The p.alloca and p.objId arguments don't make a lot of sense without the remainder of the full restrict patch. The objId refers to a notion that doesn't exist in current LLVM.

I think it would be better to make the intrinsics just

declare void @llvm.noalias.decl(metadata !p.scope)

to start with. Adding additional arguments via AutoUpgrade should be straightfoward down the line.

19628

We should probably avoid using "restrict" terminology on the LLVM IR level, as restrict is a C/C++ specific concept. Rather than "restrict scope" I would call this a "noalias scope".

On that note, I wonder whether calling this intrinsic @llvm.noalias.scope.start rather than @llvm.noalias.decl might make sense. (The name mirrors llvm.lifetime.start and llvm.invariant.start -- but then again, those also have an "end", so maybe the parallel does not make sense.)

19651

If only a single scope can be listed, might it make sense to directly point to the scope, rather than a list with a single scope? Or is the idea here that this might be extended to declare multiple scopes at the same time in the future?

19659

I think adding an example for this intrinsic would be helpful. I'm thinking something along these lines:

; This examples shows two possible positions for noalias.decl:
; If it is outside the loop (version 1), then %a and %b are noalias across *all* iterations.
; If it is inside the loop (version 2), then %a and %b are noalias only within *one* iteration.
declare void @decl_in_loop(i8* %a.base, i8* %b.base) {
entry:
  ; call void @llvm.noalias.decl(metadata !2) ; Version 1: noalias.decl outside loop
  br label %loop

loop:
  %a = phi i8* [ %a.base, %entry ], [ %a.inc, %loop ]
  %b = phi i8* [ %b.base, %entry ], [ %b.inc, %loop ]
  ; call void @llvm.noalias.decl(metadata !2) ; Version 2: noalias.decl inside loop
  %val = load i8, i8* %a, !alias.scope !2
  store i8 %val, i8* %b, !noalias !2
  %a.inc = getelementptr inbounds i8, i8* %a, i64 1
  %b.inc = getelementptr inbounds i8, i8* %a, i64 1
  %cond = call i1 @cond()
  br i1 %cond, label %loop, label %exit

exit:
  ret void
}

!0 = !{!0} ; domain
!1 = !{!1, !0} ; scope
!2 = !{!1} ; scope list

llvm/include/llvm/IR/Intrinsics.td

558

The ArgMemOnly here seems a bit dubious. This means it can read/write the p.alloca argument, which I assume is not intended (even if it's unused now).

I guess we can't make this NoMem, because then it could simply be DCEd right? Maybe it should be InaccessibleMemOnly?

[nikic]

While the concept of the intrinsic is intuitive, I think we're missing something here in terms of how it is formalized. I have a bit of a hard time formulating the rules.

Let's consider this code:

call @llvm.noalias.decl(!metadata !2)
load i8, i8* %a, !alias.scope !2
call @llvm.noalias.decl(!metadata !2)
store i8 0, i8* %a, !noalias !2

Something along the lines you could get from a naive unrolling. Now, clean semantics would be to say that noalias.decl acts as a barrier, and !2 before noalias.decl and !2 after it refer to separate scopes. But we can't do that from a technical perspective.

So I guess instead, we say that the above code invoked undefined behavior.

However, is this undefined behavior as well?

  br i1 %c, label %if, label %else

if:
  call @llvm.noalias.decl(!metadata !2)
  load i8, i8* %a, !alias.scope !2
  br label %end

else:
  call @llvm.noalias.decl(!metadata !2)
  store i8 0, i8* %a, !noalias !2
  br label %end

end:
  ret void
}

I would say "no", this code is fine. So the rule would be:

If an @llvm.noalias.decl intrinsic for a certain scope is dominated by another @llvm.noalias.decl intrinsic for the same scope, the behavior is undefined.

Loop unrolling etc then need to perform the renaming to avoid that UB.

Next, what about this code?

load i8, i8* %a, !alias.scope !2 ; before noalias.decl
call @llvm.noalias.decl(!metadata !2)
store i8 0, i8* %a, !noalias !2

// and this
if:
  call @llvm.noalias.decl(!metadata !2)
  br label %end

else:
  br label %end

end:
  store i8 0, i8* %a, !noalias !2 ; after noalias.decl, but not dominated
  ret void

I would assume this is also UB:

Any usage of a certain scope must be dominated by a @llvm.noalias.decl intrinsic for that scope, otherwise the behavior is undefined. As an exception, if there is no @llvm.noalias.decl call for a certain scope contained in the function, the behavior is as if such a call were located at the start of the function.

The exception here is a bit ugly. Without it existing IR would have to be auto-upgraded by inserting @llvm.noalias.decl for any scopes that are used.

[jeroen.dobbelaere]

llvm/docs/LangRef.rst

19619

The initial recommendation during the AA tech call was to already add all the arguments even if they are not needed yet. I guess that omitting them for now could work. Do you know the exact policy for backwards compatibility ? (released vs unreleased)

19628

At this level, we can indeed omit references to restrict. For the larger explanation (full restrict), imho, it makes sense to use restrict as an example for explaining all the logic.

For the intrinsic: it is not a 'start of a scope'. The intrinsic indicates the location (in the code) where the scope was declared. Instructions metadata are allowed to refer to that scope, even if the intrinsic is not dominating that instruction. Optimizations are allowed to move instructions that refer to this scope over the intrinsic.

[jeroen.dobbelaere]

llvm/docs/LangRef.rst

19651

Yes (to the second): one of the ideas is that a future optimization might combine llvm.noalias.decl into a single instruction, referring to the union of the scopes.

llvm/include/llvm/IR/Intrinsics.td

558

That might also work.

[jeroen.dobbelaere]

In D93039#2446719, @nikic wrote:

While the concept of the intrinsic is intuitive, I think we're missing something here in terms of how it is formalized. I have a bit of a hard time formulating the rules.

The rules that I have in mind have more freedom. They are more like:

• @llvm.noalias.decl is something like a barrier that indicates where a noalias scope originates
• It should normally not be moved across block boundaries. (This is to avoid a declaration crossing a loop boundary)
• Moving it inside a block should pose no problems.
• When it is duplicated, care must be taken to see what to do with the noalias scope.
  • cases like loop unrolling and loop rotation: scope must be duplicated
  • cases like loop unswitching: no need to duplicate the scope
  • it should also not block optimizing away an 'almost empty loop' (in that case, the empty loop should be replaced by the @llvm.noalias.decl)
• instructions that have !alias.scope or !noalias metadata referring to the declared scope can be moved freely across the intrinsic.
• A @llvm.noalias.decl can be omitted if there is no !alias.scope metadata referring to the scope.
  • An !alias.scope usage, corresponds to a @llvm.noalias/@llvm.ptr_provenance.noalias usage in the full restrict version. When there are no more dependencies, the @llvm.noalias.decl intrinsic can be omitted.
• A missing @llvm.noalias.decl inside a function can lead to undefined behavior after inlining (and loop unrolling).
• Multiple @llvm.noalias.decl intrinsics in the same block, referring to the same scope can be merged.
• Multiple @llvm.noalias.decl intrinsics in the same block, referring to a different scopes can also be merged (but I would not yet do this).

if there is no @llvm.noalias.decl` call for a certain scope contained in the function, the behavior is as if such a call were located at the start of the function.`

Not sure if we need to enforce this. For backwards compatibility it might be convenient (and expensive to check) to do this during inlining. But I would rather not do it there.

[nikic]

In D93039#2448573, @jeroen.dobbelaere wrote:

In D93039#2446719, @nikic wrote:

While the concept of the intrinsic is intuitive, I think we're missing something here in terms of how it is formalized. I have a bit of a hard time formulating the rules.

The rules that I have in mind have more freedom. They are more like:

• @llvm.noalias.decl is something like a barrier that indicates where a noalias scope originates
• It should normally not be moved across block boundaries. (This is to avoid a declaration crossing a loop boundary)
• Moving it inside a block should pose no problems.
• When it is duplicated, care must be taken to see what to do with the noalias scope.
  • cases like loop unrolling and loop rotation: scope must be duplicated
  • cases like loop unswitching: no need to duplicate the scope
  • it should also not block optimizing away an 'almost empty loop' (in that case, the empty loop should be replaced by the @llvm.noalias.decl)
• instructions that have !alias.scope or !noalias metadata referring to the declared scope can be moved freely across the intrinsic.
• A @llvm.noalias.decl can be omitted if there is no !alias.scope metadata referring to the scope.
  • An !alias.scope usage, corresponds to a @llvm.noalias/@llvm.ptr_provenance.noalias usage in the full restrict version. When there are no more dependencies, the @llvm.noalias.decl intrinsic can be omitted.
• A missing @llvm.noalias.decl inside a function can lead to undefined behavior after inlining (and loop unrolling).
• Multiple @llvm.noalias.decl intrinsics in the same block, referring to the same scope can be merged.
• Multiple @llvm.noalias.decl intrinsics in the same block, referring to a different scopes can also be merged (but I would not yet do this).

I think it is generally beneficial to make the rules stricter rather than laxer. The reason is that we can implement checks in the IR Verifier and then automatically find optimizations that break the invariants. For example, if we have a rule that says:

If a noalias.decl for !scope is dominated by another noalias.decl for !scope, then the IR is malformed.

Then, performing loop unrolling without proper handling of alias scopes, will automatically result in a verifier error. Without the rule the IR remains valid, just incorrect. Similarly, a rule that says:

If a noalias.decl for !scope exists in the function, then all uses of !scope must be dominated by the noalias.decl.

Then this will also automatically detect certain incorrect code motion optimizations. (I'm less sure about this one, but I think we generally already drop noalias metadata when moving loads upwards.)

Does this make some sense?

llvm/docs/LangRef.rst

19619

Not sure on policy for unreleased versions, but it should be simple enough to autoupgrade it in either case.

[jdoerfert]

llvm/docs/LangRef.rst

19659

Maybe:
_ exact location
+ scope

---

I don't like the loop sentence. Isn't the real problem that we need to duplicate + uniquify whenever we "duplicate" a noalias decl? So for inlining it is the same as for loop unrolling, isn't it? Loop unrolling can be mentioned afterwards as an example.

llvm/include/llvm/IR/Intrinsics.td

558

I don't think it should be DCEd if used. NoMem seems logical to me.

[jeroen.dobbelaere]

As discussed during the LLVM AA Tech Call of 2021/1/5:

• switched to the minimal version with '@llvm.experimental.noalias.scope.decl', only using a single argument.

Note: verifier changes are not yet included. I first wanted to provide an update with the other changes before trying to formalize the rule checking in the verifier.

[jeroen.dobbelaere]

llvm/include/llvm/IR/Intrinsics.td

558

NoMem would allow to optimize it away. IntrInaccessibleMemOnly seems the closest fit today.

[nikic]

Just some minor notes.

llvm/docs/LangRef.rst

19617

Maybe name it !id.scope.list to make it clear that it's not a single scope?

19640

", also a decision must be made about the scope" -> ", a decision must also be made about the scope"

19644

associate -> associated

19665

The %a here should be %b.

llvm/include/llvm/IR/Intrinsics.td

550

At the technical call @jdoerfert also mentioned the possibility of marking it noduplicate, but after looking at some of the usages of cannotDuplicate() I'm pretty sure this will cause more issues than it will solve.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

6429

Spurious change.

llvm/lib/IR/IRBuilder.cpp

461

I believe you can just pass {Scope} here and drop the SmallVector.

[jeroen.dobbelaere]

• Minor changes as suggested by Nikita
• Added verifier part.

NOTE: this will now show that there is an issue with looprotate (which was in fact expected, as it has a similar issue as loopunroll). I'll see if I can backport that fix from the Full Restrict version as wel.

[jeroen.dobbelaere]

I added D94306 for supporting loop rotation. The test-suite still triggers some verifier crashes due to one declaration dominating another one. It seems that the SLP Vectorizer is the culprit.

[jeroen.dobbelaere]

Another observation/question I have is about possible optimizations for omitting the @llvm.experimental.noalias.scope.decl: In the full restrict patches, the declarations are thrown away when there are no users any more. The equivalent with the implementation here, is that we can throw away the declaration if the scope it declares is not used in any !alias.scope metadata. Would this be something that is easy (and fast) to check ?

[nikic]

In D93039#2486994, @jeroen.dobbelaere wrote:

Another observation/question I have is about possible optimizations for omitting the @llvm.experimental.noalias.scope.decl: In the full restrict patches, the declarations are thrown away when there are no users any more. The equivalent with the implementation here, is that we can throw away the declaration if the scope it declares is not used in any !alias.scope metadata. Would this be something that is easy (and fast) to check ?

As far as I can tell metadata does not have use lists, so I don't think this can be done without a full scan of the function to collect used scopes.

llvm/docs/LangRef.rst

19624

Same as below "also a decision must be made" -> "a decision must also be made"

19636

The domination rule enforced by the verifier should be mentioned here as well.

llvm/lib/IR/Verifier.cpp

5540

const auto *?

5553

It might make sense to temporarily put the domination check behind a default disabled cl::opt. Unless we want to land everything at the same time (which I wouldn't recommend) there will be an intermediate time where the verifier check will not succeed.

5557

auto *

5566

llvm::sort(NoAliasScopeDecls, Compare)

5593

Can you please also add a test for this in llvm/test/Verifier?

[jeroen.dobbelaere]

In D93039#2487142, @nikic wrote:

In D93039#2486994, @jeroen.dobbelaere wrote:

Another observation/question I have is about possible optimizations for omitting the @llvm.experimental.noalias.scope.decl: In the full restrict patches, the declarations are thrown away when there are no users any more. The equivalent with the implementation here, is that we can throw away the declaration if the scope it declares is not used in any !alias.scope metadata. Would this be something that is easy (and fast) to check ?

As far as I can tell metadata does not have use lists, so I don't think this can be done without a full scan of the function to collect used scopes.

Any optimization pass where we could piggy back on to do this ? Or should something like this be a separate pass ? We would need to trace all !noalias/!alias.scope usages in a function and combine this data with the llvm.experimental.noalias.scope.decl calls.

[jeroen.dobbelaere]

• Added verifier testcase
• put domination check behind an option

[jeroen.dobbelaere]

Thanks for the reviews @nikic. I hope I didn't miss anything.

[nikic]

LGTM, but please wait for @jdoerfert to check this as well.

llvm/docs/LangRef.rst

19624

nit: reason of -> reason for

[nikic]

@jdoerfert It would be great if you could look over this as well.

[jdoerfert]

A few minor wording suggestions and comments, nothing that would require another round of review. Adopt my suggestions as you see fit, add TODOs where it makes sense and something should be investigated in the future. LGTM

llvm/docs/LangRef.rst

19624–19625

19641

Same wording as above.

19643–19646

19650

19678–19680

19681

Nit: Version or version, not both.

llvm/include/llvm/IR/Intrinsics.td

550

Interesting, at some point I'd like to hear more. Let's go with IntrInaccessibleMemOnly for now but we should be on the lookout for better solutions here. This is not the only intrinsic and the less restrictive our annotations are the better.

llvm/lib/IR/Verifier.cpp

5571

If this sorts based on pointer values it is non-deterministic. While potentially OK in the verifier, I'd recommend a TODO. We should sort by "metadata ids" (!0, !1, ...) or something that is deterministic.

5597

FWIW, I would set this up the other way around, maybe worth considering but not strictly necessary:

1. Collect all scopes from the intrinsics in a map<Scope, SmallVector<Instruction>>
2. For each scope, take the last and all other instructions in the vector and check dominance.
3. If there is more than one, drop the last instruction and go to 2.

[jeroen.dobbelaere]

In D93039#2491603, @jdoerfert wrote:

A few minor wording suggestions and comments, nothing that would require another round of review. Adopt my suggestions as you see fit, add TODOs where it makes sense and something should be investigated in the future. LGTM

Thanks for the feedback. I plan to do the small updates today and commit it so that we have a view on possible (unexpected) fallout.
@jdoerfert, @nikic, can you also spend some time on the other open reviews on the stack ?

llvm/lib/IR/Verifier.cpp

5571

Yes that's true. In the 'good' case, this will not make a difference of course. I'll add the TODO.

5597

My initial idea was to use a map of vectors as you suggest, but I settled on doing a sort and avoiding a bunch of allocations. I am going to keep this for now. Having a nested for-loop does not make a big difference wrt complexity as we need to check the dominance for A vs B and for B vs A.

[jeroen.dobbelaere]

Adapted to comments.

[asbirlea]

Forgot to send this nits, feel free to add in a follow up.

llvm/lib/IR/Verifier.cpp

5571

+1, please let's avoid non-deterministic behavior, follow-up works.

Potentially also store and reuse the list of scopes from the above for loop.

5586

s/[/]

[jeroen.dobbelaere]

llvm/lib/IR/Verifier.cpp

5586

ItCurrent inclusive, ItNext exclusive.
Or [ ItCurrent, ItNext-1 ].

[asbirlea]

llvm/lib/IR/Verifier.cpp

5586

Thank you for the clarification, I realized the interval from the code, but then didn't connect it to the comment notation.
This format is new to me. I was taught the mathematical notation is [ItCurrent, ItNext) in this case, or, as you said, [ItCurrent, ItNext-1].

[nikic]

llvm/lib/IR/Verifier.cpp

121

Can we flip this flag now, or are you aware of any further issues?

[jeroen.dobbelaere]

Will you do the flip or shall I do it ?

llvm/lib/IR/Verifier.cpp

121

I just did a test-suite run and a stage2 release build using an assertion build with the flag flipped, and both went fine. IMHO it makes sense to try it out...

[fhahn]

llvm/lib/IR/Verifier.cpp

121

What's the impact on compile-time? If it is potentially expensive, it should probably be true for EXPENSIVE_CHECKS builds.

[nikic]

llvm/lib/IR/Verifier.cpp

121

I see no reason for it to be expensive at least.

[jeroen.dobbelaere]

llvm/lib/IR/Verifier.cpp

5586

@asbirlea Both are valid it seems https://en.wikipedia.org/wiki/Interval_(mathematics)#Including_or_excluding_endpoints
and https://en.wikipedia.org/wiki/ISO_31-11
I (and my children) learned the notation using only '[' and ']' ;)

[xbolva00]

llvm/lib/IR/Verifier.cpp

5586

I would prefer more common notation too. It may look like a typo, and somebody in the future may “fix” it to ].

[jeroen.dobbelaere]

llvm/lib/IR/Verifier.cpp

121

@fhahn, @nikic, It's O(N log(N)) (sorting of N = number of scope declarations)
Next to that, it is roughly k * O((M-1)^2) * O(dominance checking) with M the the number of identical scope declarations, and k the number if different scopes.
In practice M should be pretty low (mostly 1) and O(N log(N)) should be the main part.

Is that considered to be too expensive ?

5586

@xbolva00 That probably depends on what you learned and might go in both directions. Do we have an llvm guidance on what notation to use ? I have no problem with using the '[' ')' style, but it might make sense that it is documented as the preferred style for llvm ?

[fhahn]

llvm/lib/IR/Verifier.cpp

121

IIUC we need to potentially check whether any llvm.experimental.noalias.scope.decl dominates any other llvm.experimental.noalias.scope.decl?

Is it possible to have a function with N basic blocks which do not dominate each other, each with N llvm.experimental.noalias.scope.decl for the same scope?

[jeroen.dobbelaere]

llvm/lib/IR/Verifier.cpp

121

Is it possible to have a function with N basic blocks which do not dominate each other, each with N llvm.experimental.noalias.scope.decl for the same scope?

It is allowed to construct such llvm-ir manually.
I am not aware on how to trigger this by an optimization pass, just based on declarations introduced by inlining.
My understanding is that most optimizations will not duplicate the intrinsic. The extra check is there to catch those optimizations that do and do it wrongly.

[fhahn]

llvm/lib/IR/Verifier.cpp

121

In practice M should be pretty low (mostly 1) and O(N log(N)) should be the main part.

I am not worried really worried about about the 'common' case here, it is unlikely to be noticeable in common C/C++ programs. But if there isn't anything preventing the worst case, (~M in the above being roughly the number of instructions in a function, excluding branches), then I think it would be better to have this as expensive check.

This might be overly cautious for 'sane' code, but unfortunately there are plenty of code-generators that like to generate highly unusual IR. For example, we surprisingly often get reports of builds taking 24+ hours, because someone tries to compile a file with 500k stores in a single basic block without running any IR store optimizations, which one could argue is not 'common'.

It is allowed to construct such llvm-ir manually.
I am not aware on how to trigger this by an optimization pass, just based on declarations introduced by inlining.

Unfortunately LLVM IR & the verifier is used in many contexts, frontends are free to generate whatever IR they want and also are free to use whatever combination of optimizations (or no optimizations at all). Personally I am weary when it comes to assuming IR passed to LLVM is 'reasonable'.

[jeroen.dobbelaere]

llvm/lib/IR/Verifier.cpp

121

@fhahn Would D95335 be acceptable ?

llvm/docs/LangRef.rst

 The second argument specifies the exception behavior as described above.
 
 Semantics:
 """"""""""
 
 This function returns the same values as the libm ``trunc`` functions
 would and handles error conditions in the same way.
 
+.. _int_experimental_noalias_scope_decl:
+
+'``llvm.experimental.noalias.scope.decl``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+
+::
+
+      declare void @llvm.experimental.noalias.scope.decl(metadata !id.scope.list)
+
+Overview:
+"""""""""
+
+The ``llvm.experimental.noalias.scope.decl`` intrinsic identifies where a
+noalias scope is declared. When the intrinsic is duplicated, a decision must
+also be made about the scope: depending on the reason of the duplication,
+the scope might need to be duplicated as well.
+
+
+Arguments:
+""""""""""
+
+The ``!id.scope.list`` argument is metadata that is a list of ``noalias``
+metadata references. The format is identical to that required for ``noalias``
+metadata. This list must have exactly one element.
+
+Semantics:
+""""""""""
+
+The ``llvm.experimental.noalias.scope.decl`` intrinsic identifies where a
+noalias scope is declared. When the intrinsic is duplicated, a decision must
+also be made about the scope: depending on the reason of the duplication,
+the scope might need to be duplicated as well.
+
+For example, when the intrinsic is used inside a loop body, and that loop is
+unrolled, the associated noalias scope must also be duplicated. Otherwise, the
+noalias property it signifies would spill across loop iterations, whereas it
+was only valid within a single iteration.
+
+.. code-block:: llvm
+
+  ; This examples shows two possible positions for noalias.decl and how they impact the semantics:
+  ; If it is outside the loop (Version 1), then %a and %b are noalias across *all* iterations.
+  ; If it is inside the loop (Version 2), then %a and %b are noalias only within *one* iteration.
+  declare void @decl_in_loop(i8* %a.base, i8* %b.base) {
+  entry:
+    ; call void @llvm.experimental.noalias.scope.decl(metadata !2) ; Version 1: noalias decl outside loop
+    br label %loop
+  
+  loop:
+    %a = phi i8* [ %a.base, %entry ], [ %a.inc, %loop ]
+    %b = phi i8* [ %b.base, %entry ], [ %b.inc, %loop ]
+    ; call void @llvm.experimental.noalias.scope.decl(metadata !2) ; Version 2: noalias decl inside loop
+    %val = load i8, i8* %a, !alias.scope !2
+    store i8 %val, i8* %b, !noalias !2
+    %a.inc = getelementptr inbounds i8, i8* %a, i64 1
+    %b.inc = getelementptr inbounds i8, i8* %b, i64 1
+    %cond = call i1 @cond()
+    br i1 %cond, label %loop, label %exit
+  
+  exit:
+    ret void
+  }
+  
+  !0 = !{!0} ; domain
+  !1 = !{!1, !0} ; scope
+  !2 = !{!1} ; scope list
+
+Multiple calls to `@llvm.experimental.noalias.scope.decl` for the same scope
+are possible, but one should never dominate another. Violations are pointed out
+by the verifier as they indicate a problem in either a transformation pass or
+the input.
+
 
 Floating Point Environment Manipulation intrinsics
 --------------------------------------------------
 
 These functions read or write floating point environment, such as rounding
 mode or state of floating point exceptions. Altering the floating point
 environment requires special care. See :ref:`Floating Point Environment <floatenv>`.
 

llvm/include/llvm/IR/IRBuilder.h

#endif
   /// Create an assume intrinsic call that allows the optimizer to
   /// assume that the provided condition will be true.
   ///
   /// The optional argument \p OpBundles specifies operand bundles that are
   /// added to the call instruction.
   CallInst *CreateAssumption(Value *Cond,
                              ArrayRef<OperandBundleDef> OpBundles = llvm::None);
 
+  /// Create a llvm.experimental.noalias.scope.decl intrinsic call.
+  Instruction *CreateNoAliasScopeDeclaration(Value *Scope);
+  Instruction *CreateNoAliasScopeDeclaration(MDNode *ScopeTag) {
+    return CreateNoAliasScopeDeclaration(
+        MetadataAsValue::get(Context, ScopeTag));
+  }
+
   /// Create a call to the experimental.gc.statepoint intrinsic to
   /// start a new statepoint sequence.
   CallInst *CreateGCStatepointCall(uint64_t ID, uint32_t NumPatchBytes,
                                    Value *ActualCallee,
                                    ArrayRef<Value *> CallArgs,
                                    Optional<ArrayRef<Value *>> DeoptArgs,
                                    ArrayRef<Value *> GCArgs,
                                    const Twine &Name = "");

llvm/include/llvm/IR/Intrinsics.h

 class LLVMContext;
 class Module;
 class AttributeList;
 
 /// This namespace contains an enum with a value for every intrinsic/builtin
 /// function known by LLVM. The enum values are returned by
 /// Function::getIntrinsicID().
 namespace Intrinsic {
+  // Abstraction for the arguments of the noalias intrinsics
+  static const int NoAliasScopeDeclScopeArg = 0;
+
   // Intrinsic ID type. This is an opaque typedef to facilitate splitting up
   // the enum into target-specific enums.
   typedef unsigned ID;
 
   enum IndependentIntrinsics : unsigned {
     not_intrinsic = 0, // Must be zero
 
   // Get the intrinsic enums generated from Intrinsics.td

llvm/include/llvm/IR/Intrinsics.td

 
 def int_readcyclecounter : DefaultAttrsIntrinsic<[llvm_i64_ty]>;
 
 // The assume intrinsic is marked as arbitrarily writing so that proper
 // control dependencies will be maintained.
 def int_assume        : DefaultAttrsIntrinsic<[], [llvm_i1_ty], [IntrWillReturn,
                                                      NoUndef<ArgIndex<0>>]>;
 
+// 'llvm.experimental.noalias.scope.decl' intrinsic: Inserted at the location of
+// noalias scope declaration. Makes it possible to identify that a noalias scope
+// is only valid inside the body of a loop.
+//
+// Purpose of the different arguments:
+// - arg0: id.scope: metadata representing the scope declaration.
+def int_experimental_noalias_scope_decl
+    : DefaultAttrsIntrinsic<[], [llvm_metadata_ty],
+        [IntrInaccessibleMemOnly]>; // blocks LICM and some more
+
 // Stack Protector Intrinsic - The stackprotector intrinsic writes the stack
 // guard to the correct place on the stack frame.
 def int_stackprotector : DefaultAttrsIntrinsic<[], [llvm_ptr_ty, llvm_ptrptr_ty], []>;
 def int_stackguard : DefaultAttrsIntrinsic<[llvm_ptr_ty], [], []>;
 
 // A counter increment for instrumentation based profiling.
 def int_instrprof_increment : Intrinsic<[],
                                         [llvm_ptr_ty, llvm_i64_ty,
                                          llvm_i32_ty, llvm_i32_ty]>;
 
 // A counter increment with step for instrumentation based profiling.
 def int_instrprof_increment_step : Intrinsic<[],
                                         [llvm_ptr_ty, llvm_i64_ty,
                                          llvm_i32_ty, llvm_i32_ty, llvm_i64_ty]>;
 

llvm/lib/CodeGen/IntrinsicLowering.cpp

void IntrinsicLowering::LowerIntrinsicCall(CallInst *CI) {
 
   case Intrinsic::annotation:
   case Intrinsic::ptr_annotation:
     // Just drop the annotation, but forward the value
     CI->replaceAllUsesWith(CI->getOperand(0));
     break;
 
   case Intrinsic::assume:
+  case Intrinsic::experimental_noalias_scope_decl:
   case Intrinsic::var_annotation:
     break;   // Strip out these intrinsics
 
   case Intrinsic::memcpy: {
     Type *IntPtr = DL.getIntPtrType(Context);
     Value *Size = Builder.CreateIntCast(CI->getArgOperand(2), IntPtr,
                                         /* isSigned */ false);
     Value *Ops[3];

llvm/lib/CodeGen/SelectionDAG/FastISel.cpp

bool FastISel::selectIntrinsicCall(const IntrinsicInst *II) {
   case Intrinsic::lifetime_start:
   case Intrinsic::lifetime_end:
   // The donothing intrinsic does, well, nothing.
   case Intrinsic::donothing:
   // Neither does the sideeffect intrinsic.
   case Intrinsic::sideeffect:
   // Neither does the assume intrinsic; it's also OK not to codegen its operand.
   case Intrinsic::assume:
+  // Neither does the llvm.experimental.noalias.scope.decl intrinsic
+  case Intrinsic::experimental_noalias_scope_decl:
     return true;
   case Intrinsic::dbg_declare: {
     const DbgDeclareInst *DI = cast<DbgDeclareInst>(II);
     assert(DI->getVariable() && "Missing variable");
     if (!FuncInfo.MF->getMMI().hasDebugInfo()) {
       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI
                         << " (!hasDebugInfo)\n");
       return true;

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::stackguard: {
     }
     if (TLI.useStackGuardXorFP())
       Res = TLI.emitStackGuardXorFP(DAG, Res, sdl);
     DAG.setRoot(Chain);
     setValue(&I, Res);
     return;
   }
   case Intrinsic::stackprotector: {
     // Emit code into the DAG to store the stack guard onto the stack.
     MachineFunction &MF = DAG.getMachineFunction();
     MachineFrameInfo &MFI = MF.getFrameInfo();
     SDValue Src, Chain = getRoot();
 
     if (TLI.useLoadStackGuardNode())
       Src = getLoadStackGuard(DAG, sdl, Chain);
     else
       Src = getValue(I.getArgOperand(0));   // The guard's value.
#include "llvm/IR/VPIntrinsics.def"
 
   case Intrinsic::annotation:
   case Intrinsic::ptr_annotation:
   case Intrinsic::launder_invariant_group:
   case Intrinsic::strip_invariant_group:
     // Drop the intrinsic, but forward the value
     setValue(&I, getValue(I.getOperand(0)));
     return;
+
   case Intrinsic::assume:
+  case Intrinsic::experimental_noalias_scope_decl:
   case Intrinsic::var_annotation:
   case Intrinsic::sideeffect:
-    // Discard annotate attributes, assumptions, and artificial side-effects.
+    // Discard annotate attributes, noalias scope declarations, assumptions, and
+    // artificial side-effects.
     return;
 
   case Intrinsic::codeview_annotation: {
     // Emit a label associated with this metadata.
     MachineFunction &MF = DAG.getMachineFunction();
     MCSymbol *Label =
         MF.getMMI().getContext().createTempSymbol("annotation", true);
     Metadata *MD = cast<MetadataAsValue>(I.getArgOperand(0))->getMetadata();

llvm/lib/IR/IRBuilder.cpp

assert(Cond->getType() == getInt1Ty() &&
          "an assumption condition must be of type i1");
 
   Value *Ops[] = { Cond };
   Module *M = BB->getParent()->getParent();
   Function *FnAssume = Intrinsic::getDeclaration(M, Intrinsic::assume);
   return createCallHelper(FnAssume, Ops, this, "", nullptr, OpBundles);
 }
 
+Instruction *IRBuilderBase::CreateNoAliasScopeDeclaration(Value *Scope) {
+  Module *M = BB->getModule();
+  auto *FnIntrinsic = Intrinsic::getDeclaration(
+      M, Intrinsic::experimental_noalias_scope_decl, {});
+  return createCallHelper(FnIntrinsic, {Scope}, this);
+}
+
 /// Create a call to a Masked Load intrinsic.
 /// \p Ptr       - base pointer for the load
 /// \p Alignment - alignment of the source location
 /// \p Mask      - vector of booleans which indicates what vector lanes should
 ///                be accessed in memory
 /// \p PassThru  - pass-through value that is used to fill the masked-off lanes
 ///                of the result
 /// \p Name      - name of the result variable

llvm/lib/IR/Verifier.cpp

 #include <cassert>
 #include <cstdint>
 #include <memory>
 #include <string>
 #include <utility>
 
 using namespace llvm;
 
+static cl::opt<bool> VerifyNoAliasScopeDomination(
+    "verify-noalias-scope-decl-dom", cl::Hidden, cl::init(false),
+    cl::desc("Ensure that llvm.experimental.noalias.scope.decl for identical "
+             "scopes are not dominating"));
+
 namespace llvm {
 
 struct VerifierSupport {
   raw_ostream *OS;
   const Module &M;
   ModuleSlotTracker MST;
   Triple TT;
   const DataLayout &DL;
class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   // constant expressions, we can arrive at a particular user many times.
   SmallPtrSet<const Value *, 32> GlobalValueVisited;
 
   // Keeps track of duplicate function argument debug info.
   SmallVector<const DILocalVariable *, 16> DebugFnArgs;
 
   TBAAVerifier TBAAVerifyHelper;
 
+  SmallVector<IntrinsicInst *, 4> NoAliasScopeDecls;
+
   void checkAtomicMemAccessSize(Type *Ty, const Instruction *I);
 
 public:
   explicit Verifier(raw_ostream *OS, bool ShouldTreatBrokenDebugInfoAsError,
                     const Module &M)
       : VerifierSupport(OS, M), LandingPadResultTy(nullptr),
         SawFrameEscape(false), TBAAVerifyHelper(this) {
     TreatBrokenDebugInfoAsError = ShouldTreatBrokenDebugInfoAsError;
bool verify(const Function &F) {
     // FIXME: We strip const here because the inst visitor strips const.
     visit(const_cast<Function &>(F));
     verifySiblingFuncletUnwinds();
     InstsInThisBlock.clear();
     DebugFnArgs.clear();
     LandingPadResultTy = nullptr;
     SawFrameEscape = false;
     SiblingFuncletInfo.clear();
+    verifyNoAliasScopeDecl();
+    NoAliasScopeDecls.clear();
 
     return !Broken;
   }
 
   /// Verify the module that this instance of \c Verifier was initialized with.
   bool verify() {
     Broken = false;
 
#include "llvm/IR/Metadata.def"
   void verifyCompileUnits();
 
   /// Module-level verification that all @llvm.experimental.deoptimize
   /// declarations share the same calling convention.
   void verifyDeoptimizeCallingConvs();
 
   /// Verify all-or-nothing property of DIFile source attribute within a CU.
   void verifySourceDebugInfo(const DICompileUnit &U, const DIFile &F);
+
+  /// Verify the llvm.experimental.noalias.scope.decl declarations
+  void verifyNoAliasScopeDecl();
 };
 
 } // end anonymous namespace
 
 /// We know that cond should be true, if not print an error message.
 #define Assert(C, ...) \
   do { if (!(C)) { CheckFailed(__VA_ARGS__); return; } } while (false)
 
case Intrinsic::experimental_vector_extract: {
     VectorType *VecTy = cast<VectorType>(Call.getArgOperand(0)->getType());
 
     Assert(ResultTy->getElementType() == VecTy->getElementType(),
            "experimental_vector_extract result must have the same element "
            "type as the input vector.",
            &Call);
     break;
   }
+  case Intrinsic::experimental_noalias_scope_decl: {
+    NoAliasScopeDecls.push_back(cast<IntrinsicInst>(&Call));
+    break;
+  }
   };
 }
 
 /// Carefully grab the subprogram from a local scope.
 ///
 /// This carefully grabs the subprogram from a local scope, avoiding the
 /// built-in assertions that would typically fire.
 static DISubprogram *getSubprogram(Metadata *LocalScope) {

 void Verifier::verifySourceDebugInfo(const DICompileUnit &U, const DIFile &F) {
   bool HasSource = F.getSource().hasValue();
   if (!HasSourceDebugInfo.count(&U))
     HasSourceDebugInfo[&U] = HasSource;
   AssertDI(HasSource == HasSourceDebugInfo[&U],
            "inconsistent use of embedded source");
 }
 
+void Verifier::verifyNoAliasScopeDecl() {
+  if (NoAliasScopeDecls.empty())
+    return;
+
+  // only a single scope must be declared at a time.
+  for (auto *II : NoAliasScopeDecls) {
+    assert(II->getIntrinsicID() == Intrinsic::experimental_noalias_scope_decl &&
+           "Not a llvm.experimental.noalias.scope.decl ?");
+    const auto *ScopeListMV = dyn_cast<MetadataAsValue>(
+        II->getOperand(Intrinsic::NoAliasScopeDeclScopeArg));
+    Assert(ScopeListMV != nullptr,
+           "llvm.experimental.noalias.scope.decl must have a MetadataAsValue "
+           "argument",
+           II);
+
+    const auto *ScopeListMD = dyn_cast<MDNode>(ScopeListMV->getMetadata());
+    Assert(ScopeListMD != nullptr, "!id.scope.list must point to an MDNode",
+           II);
+    Assert(ScopeListMD->getNumOperands() == 1,
+           "!id.scope.list must point to a list with a single scope", II);
+  }
+
+  // Only check the domination rule when requested. Once all passes have been
+  // adapted this option can go away.
+  if (!VerifyNoAliasScopeDomination)
+    return;
+
+  // Now sort the intrinsics based on the scope MDNode so that declarations of
+  // the same scopes are next to each other.
+  auto GetScope = [](IntrinsicInst *II) {
+    const auto *ScopeListMV = cast<MetadataAsValue>(
+        II->getOperand(Intrinsic::NoAliasScopeDeclScopeArg));
+    return &cast<MDNode>(ScopeListMV->getMetadata())->getOperand(0);
+  };
+
+  // We are sorting on MDNode pointers here. For valid input IR this is ok.
+  // TODO: Sort on Metadata ID to avoid non-deterministic error messages.
+  auto Compare = [GetScope](IntrinsicInst *Lhs, IntrinsicInst *Rhs) {
+    return GetScope(Lhs) < GetScope(Rhs);
+  };
+
+  llvm::sort(NoAliasScopeDecls, Compare);
+
+  // Go over the intrinsics and check that for the same scope, they are not
+  // dominating each other.
+  auto ItCurrent = NoAliasScopeDecls.begin();
+  while (ItCurrent != NoAliasScopeDecls.end()) {
+    auto CurScope = GetScope(*ItCurrent);
+    auto ItNext = ItCurrent;
+    do {
+      ++ItNext;
+    } while (ItNext != NoAliasScopeDecls.end() &&
+             GetScope(*ItNext) == CurScope);
+
+    // [ItCurrent, ItNext[ represents the declarations for the same scope.
+    // Ensure they are not dominating each other
+    for (auto *I : llvm::make_range(ItCurrent, ItNext)) {
+      for (auto *J : llvm::make_range(ItCurrent, ItNext)) {
+        if (I != J) {
+          Assert(!DT.dominates(I, J),
+                 "llvm.experimental.noalias.scope.decl dominates another one "
+                 "with the same scope",
+                 I);
+        }
+      }
+    }
+    ItCurrent = ItNext;
+  }
+}
+
 //===----------------------------------------------------------------------===//
 //  Implement the public interfaces to this file...
 //===----------------------------------------------------------------------===//
 
 bool llvm::verifyFunction(const Function &f, raw_ostream *OS) {
   Function &F = const_cast<Function &>(f);
 
   // Don't use a raw_null_ostream.  Printing IR is expensive.

llvm/test/Verifier/noalias_scope_decl.ll

+; RUN: not llvm-as -disable-output --verify-noalias-scope-decl-dom < %s 2>&1 | FileCheck %s
+
+define void @test_single_scope01() nounwind ssp {
+  tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
+  ret void
+}
+
+define void @test_single_scope02() nounwind ssp {
+  tail call void @llvm.experimental.noalias.scope.decl(metadata !5)
+  ret void
+}
+; CHECK: !id.scope.list must point to a list with a single scope
+; CHECK-NEXT:   tail call void @llvm.experimental.noalias.scope.decl(metadata !5)
+
+define void @test_single_scope03() nounwind ssp {
+  tail call void @llvm.experimental.noalias.scope.decl(metadata !"test")
+  ret void
+}
+; CHECK-NEXT: !id.scope.list must point to an MDNode
+; CHECK-NEXT:   tail call void @llvm.experimental.noalias.scope.decl(metadata !"test")
+
+define void @test_dom01() nounwind ssp {
+  tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
+  tail call void @llvm.experimental.noalias.scope.decl(metadata !8)
+  ret void
+}
+
+define void @test_dom02() nounwind ssp {
+  tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
+  tail call void @llvm.experimental.noalias.scope.decl(metadata !6)
+  ret void
+}
+; CHECK-NEXT: llvm.experimental.noalias.scope.decl dominates another one with the same scope
+; CHECK-NEXT:   tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
+
+define void @test_dom03() nounwind ssp {
+  tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
+  tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
+  ret void
+}
+; CHECK-NEXT: llvm.experimental.noalias.scope.decl dominates another one with the same scope
+; CHECK-NEXT:   tail call void @llvm.experimental.noalias.scope.decl(metadata !2)
+
+; CHECK-NOT: llvm.experimental.noalias.scope.decl
+
+; Function Attrs: inaccessiblememonly nounwind
+declare void @llvm.experimental.noalias.scope.decl(metadata) #1
+
+attributes #1 = { inaccessiblememonly nounwind }
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang"}
+!2 = !{!3}
+!3 = distinct !{!3, !4, !"test: pA"}
+!4 = distinct !{!4, !"test"}
+!5 = !{!3, !3}
+!6 = !{!3}
+!7 = distinct !{!7, !4, !"test: pB"}
+!8 = !{!7}