Full Restrict Support - single patch

[jeroen.dobbelaere]

Summary

This is a convenience patch that covers all 27 patches starting from D68484 through D68523. It implements the support for full C99 restrict in clang/llvm.

Any feedback about how it behaves on your benchmarks and testcases is welcome !

Any help with code review is also welcome. That should happen on the separate patches.
(The part that is currently up for review is on D111159, introducing unknown_provenance and ptr_provenance)

The base version is dd2e681612f1f09d92abc9e16f5f65293e3fe725 (May 27, 2023)

NOTE: (January 9, 2023) - added xfail clang/test/CodeGen/restrict/capture_checks_01.c testcase to track missing pointer escape analysis.

NOTE: (June 21, 2021) - full restrict is now again enabled by default - this update also contains a number of bugfixes (triggered by csmith) - llvm.noalias.copy.guard now uses a representation based on offsets for knowing where in memory noalias pointers are stored (documentation is not yet updated) - the separate patches are not yet in sync with this version

Note: (November 17,2021)

• Moved NoAliasProvenance out of AAMetadata. Added PtrProvenance to MemoryLocation
• Introduced UnknownProvenance constant
• Added support for (some) atomic instructions.

Note: (July 29, 2022)

• Track ptr_provenance again during selectiondag lowering

[jrmuizel]

What revision is the base for this change?

[jeroen.dobbelaere]

In D69542#1727793, @jrmuizel wrote:

What revision is the base for this change?

The is a rebase based on 82d3ba87d06f9e2abc6e27d8799587d433c56630

[jrmuizel]

Is this work stalled?

[jeroen.dobbelaere]

In D69542#1836340, @jrmuizel wrote:

Is this work stalled?

Partly:

• I still need to do the documentation work, creating a separate document for restrict/noalias.
• Johannes wondered if we need to use operand bundles: http://lists.llvm.org/pipermail/llvm-dev/2019-November/136705.html
  • There is no resolution for this yet. If we decide that this is the way to go, I can migrate the full restrict support patch, once the load/store instructions support operand bundles.

[jeroen.dobbelaere]

Rebased to c06b7e2ab5167ad031745a706204abed1aefd823 (July 14, 2020)

[jeroen.dobbelaere]

Rebased to 9fb46a452d4e5666828c95610ceac8dcd9e4ce16 (September 7, 2020)

[jeroen.dobbelaere]

D68509: Updated to correctly handle inlining when callee == caller. (Triggered by doing a stage2 compile)
D68515: Fixed build warning and testcase failure in Release mode.

[jeroen.dobbelaere]

Following changes were done:

• use 'variant 1' approach for ptr_provenance argument, getting rid of 'NumUserOperandsDelta' (See D68488)
• fix issue with new pass manager (See D68507)
• fix testcase issue (See D68512)

[barannikov88]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1770–1771

Suppose we have V2 with valid noalias provenance, and V1 without it.
V1 is a long chain of GEPs (longer than MaxLookupSearchDepth), finished with noalias.arg.guard.

When aliasCheck is called the first time, we get into the "then" branch of the "if", strip nothing, and getUnderlyingObject finds some base for V1 at the depth MaxLookupSearchDepth. This object will be passed to a recursive call of aliasCheck later as O1.

After that, aliasCheck is called recursively from aliasGEP, this time with O1 != nullptr and empty V2AAInfo. We get into the else branch of the if and strip out noalias.arg.guard from V1 chain. This effectively decreases depth of the expression, and DecomposeGEP called later from aliasGEP will return _different_ base object from O1.

This leads to failed assertion in aliasGEP which checks that DecomposeGEP found the same base as getUnderlyingObject.

[jeroen.dobbelaere]

Thanks for the detailed analysis !

[barannikov88]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

494

@jeroen.dobbelaere
In case the instruction is Load or Store, its provenance operand is set UndefValue upon cloning. Is this behavior appropriate here?

[jeroen.dobbelaere]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

494

@barannikov88
Good question. The restrict patches have had already a number of iterations. In the earlier versions, ptr_provenance information was dropped when cloning. The main reason was for safety: In a restrict world, you need to think what to do when cloning an instruction wrt the restrict validity: do we need to keep the same scopes/restrict variable or do we need to work on a copy. Dropping the info was a safety guard. But, we needed to keep the same number of arguments, so I used UndefValue to indicate a dropped ptr_provenance.

At that time, a missing ptr_provenance would result in 'safe analysis', as, both a ptr_provenance and a !noalias metadata were required to perform ScopeNoAliasAA. Later on, it became clear that we should also do analysis if no ptr_provenance was explicitly present (which meant the same as ptr == ptr_provenance) and the rules changed.

This probably means that just dropping the ptr_provenance when cloning is probably not the right thing to do any more.
And passes that use clone() on a load/store instruction should become aware of the potential extra dependency introduced by the ptr_provenance. Dropping it (in a restrict) world should only be done if also the !noalias metadata is removed. In a world where ptr_provenance is also used for tracking actual ptr_provenance, this might also not be true.

So no, this behavior is probably not appropriate here. Do you happen to have a testcase that confirms this ?

[barannikov88]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

494

Thank you for the quick and detailed answer!
I have a testcase, but right now it contains some bits of proprietary information. I'll strip them off and post the test here later.

[barannikov88]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

494

Here you go:

test.ll3 KBDownload

$ opt test.ll -loop-rotate -S -o -

You should be able to find the following line in the output:
%x.01 = load i8, i8* %src_ptr, ptr_provenance i8* undef, align 1, !tbaa !10, !noalias !9

The patch was aplied to the same base, the project is configured as:

-DBUILD_SHARED_LIBS=ON
-DLLVM_CCACHE_BUILD=ON
-DLLVM_TARGETS_TO_BUILD="X86"
-DLLVM_ENABLE_PROJECTS="clang"
-DLLVM_USE_LINKER=lld

PS
I believe I've seen similar behavior of the SimplifyCFG pass, I'll try to prepare a test for that, too.

[barannikov88]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

494

I believe I've seen similar behavior of the SimplifyCFG pass, I'll try to prepare a test for that, too.

It appeared to be the same pass (LoopRotate). The dump just did not show the change with -print-after-all.

[jeroen.dobbelaere]

@barannikov88
Thanks ! I have vacation the next two weeks, so things will be slow. But I'll take it into account for the next revision on which I am working.
If you have time you can always join the LLVM Alias Analysis Technical Call. The next one should be on January 5,2021; 12pm central time.

[jeroen.dobbelaere]

Rebased to f8dbd61074176bae92ec360a093ac7bc498c9321.

[jeroen.dobbelaere]

NOTE: the latest update missed two mandatory changes: - in clang/include/clang/Driver/Options.td : the DefaultFalse should become a DefaultTrue in order to enable the full restrict by default. - in clang/lib/Driver/ToolChains/Clang.cpp, '"-use-noalias-intrinsic-during-inlining=0"' must become '"-use-noalias-intrinsic-during-inlining=scopes"'

[jeroen.dobbelaere]

NOTE: (June 21, 2021) - full restrict is now again enabled by default - this update also contains a number of bugfixes (triggered by csmith) - llvm.noalias.copy.guard now uses a representation based on offsets for knowing where in memory noalias pointers are stored - the separate patches are not yet in sync with this version

[jeroen.dobbelaere]

Rebased to 3c4fad6a69887311f4e9feeca28126a89f314d45 (August 17, 2021)

[jeroen.dobbelaere]

Compile time impact: https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&branch=dobbelaj-snps%2Fperf%2Ffull_restrict-20210817-01

[gyiu]

llvm/lib/Transforms/Scalar/SROA.cpp

3954

Missing this line to make sure NoAlias Instruction doesn't self-reference.

NoAlias->setOperand(0, Load);

[jeroen.dobbelaere]

Rebased to 8924ba3bf8c6b0e8d14dff455e4e449a426a2700 (November 17, 2021)

Note: (November 17,2021)

• Moved NoAliasProvenance out of AAMetadata. Added PtrProvenance to MemoryLocation
• Introduced UnknownProvenance constant
• Added support for (some) atomic instructions.

[hkao13]

llvm/lib/IR/IRBuilder.cpp

579

This is a case when clang codegen creates a bitcast for NoAliasLoad, causing the TBAA issue mentioned above.

Is it possible to remove this code entirely? Looking into getMangledTypeStr(), it seems like literal structs will be prefixed with "sl_".

Thank you.

[hkao13]

clang/lib/CodeGen/CGExpr.cpp

1759

Metadata copied over from Load to NoAliasLoad may include TBAA. NoAliasLoad may be a bitcast instruction which will cause IR verifier to assert if TBAA metadata is attached.

[jeroen.dobbelaere]

Hi @hkao13 You happen to have some reduced testcases that show the problem ? Thanks !

[hkao13]

Hi @jeroen.dobbelaere, the above two comments of mine are in the wrong order, sorry.

I have attached a C test case, and the problem I'm seeing related to the above comments can be replicated using:

clang -flegacy-pass-manager -ffull-restrict -fstrict-aliasing -O1 test-verify.c

test-verify.c122 BDownload

The output error I see is on a bitcast instruction:
This instruction shall not have a TBAA access tag!

Thanks.

[D.Kharlamov]

Hi. I tried to use your patch for my project. My main concern is AA in MachineScheduler.
I noticed what ptr_provenance info is not passed to CodeGen.
It could be fixed by adding it to MemoryMachineOperand constructor in SelectionDAGBuilder::visitLoad and SelectionDAGBuilder::visitStore.
Also invocation of AAResults::alias in Codegen lacks of PtrProvenance argument in MemoryLocation constructors.
After this fixes AA in MachineScheduler is working fine.

[jeroen.dobbelaere]

In D69542#3465162, @D.Kharlamov wrote:

Hi. I tried to use your patch for my project. My main concern is AA in MachineScheduler.
I noticed what ptr_provenance info is not passed to CodeGen.
It could be fixed by adding it to MemoryMachineOperand constructor in SelectionDAGBuilder::visitLoad and SelectionDAGBuilder::visitStore.

Hi @D.Kharlamov, thanks for notifying this. Originally, the ptr_provenance was part of the AAMDNodes, so it would be automatically part of those places.
When extracting the ptr_provenance support, I moved it out of AAMDNodes, as that was not the logical place for it to reside. This explicit passing should indeed be
added in the SelectionDAGBuilder::visitLoad/visitStore. (Note that MachinePointerInfo already supports the optional ptr_provenance argument).

Any help with reviewing the ptr_provenance patches (See D107354 and related) is appreciated. Getting these reviewed and accepted is the next step in adding full restrict support.

Also invocation of AAResults::alias in Codegen lacks of PtrProvenance argument in MemoryLocation constructors.
After this fixes AA in MachineScheduler is working fine.

Also here, we will need to pass the ptr_provenance explicitely. Could you point me to a file and location for this case ?

Thanks,

Jeroen Dobbelaere

[jeroen.dobbelaere]

• Rebased
• Track ptr_provenance also during lowering (this was not working any more when ptr_provenance got moved outside of AAMetaData)

[vzakhari]

Hi @jeroen.dobbelaere, can you please rebase the patch? I would like to try @llvm.noalias for Flang generated IR, but the patch would not apply cleanly. Thank you!

[jeroen.dobbelaere]

In D69542#3932775, @vzakhari wrote:

Hi @jeroen.dobbelaere, can you please rebase the patch? I would like to try @llvm.noalias for Flang generated IR, but the patch would not apply cleanly. Thank you!

Hi @vzakhari , I'll give it another respin, but it will likely take a week or 2-3.

[vzakhari]

In D69542#3933523, @jeroen.dobbelaere wrote:

In D69542#3932775, @vzakhari wrote:

Hi @jeroen.dobbelaere, can you please rebase the patch? I would like to try @llvm.noalias for Flang generated IR, but the patch would not apply cleanly. Thank you!

Hi @vzakhari , I'll give it another respin, but it will likely take a week or 2-3.

I see. It will still be great to try it with the latest Flang, but I can try the patch on top of ffe262a198a9f9030991df6d3ddd812e74fa3523 in the meantime. Thank you!

[RalfJung]

llvm/docs/LangRef.rst

9966–9971

Rust and C also have a notion of "pointer provenance", but it is subtly difference: provenance in those languages is something that flows with pointer values. IOW, a value of pointer type consists of some address in memory, plus some "provenance" metadata. LLVM also has that kind of provenance, it is needed e.g. to explain some of the behavior of getelementptr. (A pointer returned by getelementptr without inbounds can go out-of-bounds but must not be used to access memory outside the bounds of the allocation it started with. In other words, the pointer "remembers" the allocation it is associated with in some way that is separate from the integer address it points to.)

Is it a good idea to use the same term for this slightly different concept? A load operation already receives provenance from its pointer argument, and now with this patchset it *also* receives something else, but also called provenance, via a separate argument.

23372

From what I was able to see (but maybe I missed something), the docs do not say what exactly happens when these aliasing requirements are violated. I would expect that this results in immediate UB. During some recent discussion, it was suggested that noalias-violating loads might return poison instead of causing UB, but I think that proposal has problems. Either way though the docs should clearly state what the behavior is in that case.

23401

should probably be: how "they" work

[jeroen.dobbelaere]

Hi Ralf, thanks for your feedback !

This convenience patch is made available to show what the total picture looks like. The current set of extracted patches (ptr_provenance and unknown_provenance) that is available for review can be found here: D104268 (and in the 'stack')

Any help in reviewing and feedback is appreciated !

Thanks,

Jeroen Dobbelaere

llvm/docs/LangRef.rst

9966–9971

This is rather an extension of this concept than a different concept: the patches extend the notion of a pointer that represents a value + provenance. For the load/store instructions, when no ptr_provenance is present, the single pointer represents both the value and provenance (and getPtrProvenance() will return this value). When the ptr_provenance` argument has been set it means that for these instructions, the getPointerOperand now only points to the value. The getPtrPtrProvenance() and getOptionalPtrProvenance() will now return the separate ptr_provenance.

It is still assumed that a single pointer contains both value and provenance.

23372

This explanation is indeed missing. In practice, noalias-violating loads must be kept as ok. noalias-violating loads in combination with a noalias-violating store results in undefined behavior. The background for this is that: reorderings of a noalias-violating load/load should not harm. Reorderings of a noalias-violating store/store, load/store or store/load might result in unwanted results.

23401

Indeed

[RalfJung]

Okay I will try to post the same comments there.

[RalfJung]

Hm I cannot find the diff that the 2nd and 3rd comment refer to in https://reviews.llvm.org/D104268? Am I looking at the wrong thing? It refers to the new "Scoped NoAlias Related Intrinsics" section of the LangRef.
Sorry for the noise. This patchset stuff is really confusing, I have no clue how to navigate them.

[jeroen.dobbelaere]

In D69542#4010990, @RalfJung wrote:

Hm I cannot find the diff that the 2nd and 3rd comment refer to in https://reviews.llvm.org/D104268? Am I looking at the wrong thing? It refers to the new "Scoped NoAlias Related Intrinsics" section of the LangRef.

Hi Ralf, the ptr_provenance patches do not contain the description of the various noalias intrinsics. I will create separate patches for this once the ptr_provenance set of changes have been reviewed and committed.

Sorry for the noise. This patchset stuff is really confusing, I have no clue how to navigate them.

I tried to provide the real dependencies in the 'stack'. Maybe it is better to just go for a fake linear dependency chain.

[RalfJung]

I see, thanks. I guess this summary patch is then the best place for those comments still.

[nikic]

In D69542#3933523, @jeroen.dobbelaere wrote:

In D69542#3932775, @vzakhari wrote:

Hi @jeroen.dobbelaere, can you please rebase the patch? I would like to try @llvm.noalias for Flang generated IR, but the patch would not apply cleanly. Thank you!

Hi @vzakhari , I'll give it another respin, but it will likely take a week or 2-3.

If there's a version of the patch that applies to either release/15.x or current main, I'd like to test this against Rust. The last time I tried this I didn't get far due to the type mangling issues, but those have been fixed, so I think it would be worthwhile to try again, both from a correctness and compile-time perspective.

Especially the ptr_provenance change seems like it could have many silent failure points. I know we have a lot of code that assumes that a pointer used by a load is the loaded pointer, which is true right now, but does not hold with ptr_provenance.

[nikic]

Thanks for the rebase!

I tested the updated patch with rustc, but unfortunately didn't get very far again. The proc_macro build fails with verifier errors:

llvm.provenance.noalias scope arg must match with llvm.noalias.decl
  %22 = call ptr @llvm.provenance.noalias.p0.p0.p0.p0.i64(ptr nonnull %8, ptr %19, ptr null, ptr undef, i64 0, metadata !4794), !noalias !4796
llvm.provenance.noalias scope arg must match with llvm.noalias.decl
  %23 = tail call ptr @llvm.provenance.noalias.p0.p0.p0.p0.i64(ptr nonnull %11, ptr %20, ptr null, ptr undef, i64 0, metadata !4798), !noalias !4796
llvm.provenance.noalias scope arg must match with llvm.noalias.decl
  %44 = call ptr @llvm.provenance.noalias.p0.p0.p0.p0.i64(ptr nonnull %8, ptr %42, ptr null, ptr undef, i64 0, metadata !4808), !noalias !4810
llvm.provenance.noalias scope arg must match with llvm.noalias.decl
  %45 = tail call ptr @llvm.provenance.noalias.p0.p0.p0.p0.i64(ptr nonnull %11, ptr %41, ptr null, ptr undef, i64 0, metadata !4812), !noalias !4810
LLVM ERROR: Broken module found, compilation aborted!

Here is the input IR (run under e.g. opt -O2): https://gist.github.com/nikic/fb9701235151e199fff0a23530808539

[jeroen.dobbelaere]

In D69542#4046725, @nikic wrote:

Thanks for the rebase!

I tested the updated patch with rustc, but unfortunately didn't get very far again. The proc_macro build fails with verifier errors:
...
Here is the input IR (run under e.g. opt -O2): https://gist.github.com/nikic/fb9701235151e199fff0a23530808539

Hi @nikic, thanks for trying it out. I am able to reproduce the problem and was also able to produce a reduced version. I'll provide an update once I have a fix.

[ram-NK]

llvm/lib/Transforms/Scalar/LICM.cpp

2097

Rodinia/backprop benchmark of llvm-test-suite is failed, When I test with this patch.
My analysis points to a restrict argument ( %hidden_units in bpnn_train_kernel()), Which is promoted by LICM.

[jeroen.dobbelaere]

llvm/lib/Transforms/Scalar/LICM.cpp

2097

Thanks for the report. I am currently working on a rebase. Once that is available (and published) I'll be working on this and some other issues that were reported.

[jeroen.dobbelaere]

This is a rebase, based on dd2e681612f1f09d92abc9e16f5f65293e3fe725 (May 27, 2023). It fully incorporates the ptr_provenance patches (D111159)

There are a number of known issues that have not yet been resolved. Those are available in testcases and have been marked with XFAIL
(a grep for XFAIL in this patch should show them) :

• wrong (too optimistic) assumption when mixing restrict and non-restrict based pointers:
  • with a global variable as restrict pointer
  • escape analysis misses cases where a noalias pointer (restrict annotated pointer) escapes through a double (or more) indirection
• LICM introduces inconsistencies in noalias.scope metadata (through phi nodes).
• LICM exposes an issue with AliasSet where ptr_provenance data is missed.

In the most recent rebase (between May 13 and may 27), I also noticed a change in behavior for an OpenMP testcase. That testcase has also been changed to XFAIL.

During June, I should be able to come up with an update that fixes those known issues.

As usual, any feedback is welcome. If you want to help out or discuss, you can always join the 4-weekly LLVM AA Technical calls.

[nikic]

For the record, I tested the new rebase and the "llvm.provenance.noalias scope arg must match with llvm.noalias.decl" issue still exists. I wasn't sure whether it was supposed to be fixed or not.

[jeroen.dobbelaere]

In D69542#4380832, @nikic wrote:

For the record, I tested the new rebase and the "llvm.provenance.noalias scope arg must match with llvm.noalias.decl" issue still exists. I wasn't sure whether it was supposed to be fixed or not.

That problem is indeed not fixed. It is also related to a new check with PHI nodes that already triggers in the .ll file that you provided earlier.

Thanks for testing !

[ram-NK]

Hi @jeroen.dobbelaere,
Following issue is identified during my testing.
GVN Pass is not copying ptr_provenance to new Load. due to this test-suite/MicroBenchmarks/LCALS/SubsetCRawLoops benchmark is giving noalias to same pointer( one is with provenance details and other without).
But unfortunately benchmark is not failing.

Always there is possibility of wrong AA analysis result, if ptr_provenance propagation is not done in any of the passes/new passes.
Adding an assertion to prevent these cases will be helpful.

[aaron.ballman]

Hello! I'm wondering what the plan is for this work given the ongoing switch to GitHub PRs and the closing of Phabricator? I believe this is work the community is still very interested in seeing landed (I certainly am!), but I'm skeptical of our ability to do that by the deadline and figure we should start talking about how to handle this sooner rather than later. Thanks!

CC @rnk for awareness on outstanding Phab reviews

[jeroen.dobbelaere]

In D69542#4654537, @aaron.ballman wrote:

Hello! I'm wondering what the plan is for this work given the ongoing switch to GitHub PRs and the closing of Phabricator? I believe this is work the community is still very interested in seeing landed (I certainly am!), but I'm skeptical of our ability to do that by the deadline and figure we should start talking about how to handle this sooner rather than later. Thanks!

CC @rnk for awareness on outstanding Phab reviews

Hi Aaron, I has some discussion about this in the last US LLVM conference. Consensus is to keep using phabricator for now (github does not work well with stacked reviews), but also to speed up the committing of changes that have already been accepted and preparation of remaining changes.
I am currently working on a rebase.

Thanks,

Jeroen Dobbelaere

[aaron.ballman]

In D69542#4654612, @jeroen.dobbelaere wrote:

In D69542#4654537, @aaron.ballman wrote:

Hello! I'm wondering what the plan is for this work given the ongoing switch to GitHub PRs and the closing of Phabricator? I believe this is work the community is still very interested in seeing landed (I certainly am!), but I'm skeptical of our ability to do that by the deadline and figure we should start talking about how to handle this sooner rather than later. Thanks!

CC @rnk for awareness on outstanding Phab reviews

Hi Aaron, I has some discussion about this in the last US LLVM conference. Consensus is to keep using phabricator for now (github does not work well with stacked reviews), but also to speed up the committing of changes that have already been accepted and preparation of remaining changes.
I am currently working on a rebase.

Excellent, that sounds like a great path forward. Thank you!

clang/lib/CodeGen/CGExpr.cpp

 #include "clang/AST/Attr.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/NSAPI.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/CodeGenOptions.h"
 #include "clang/Basic/SourceManager.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/Metadata.h"
 #include "llvm/Support/ConvertUTF.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/SaveAndRestore.h"
 #include "llvm/Transforms/Utils/SanitizerStats.h"
 
 #include <string>
 

     Load->setMetadata(CGM.getModule().getMDKindID("nontemporal"), Node);
   }
 
   CGM.DecorateInstructionWithTBAA(Load, TBAAInfo);
 
   if (EmitScalarRangeCheck(Load, Ty, Loc)) {
     // In order to prevent the optimizer from throwing away the check, don't
     // attach range metadata to the load.
   } else if (CGM.getCodeGenOpts().OptimizationLevel > 0)
     if (llvm::MDNode *RangeInfo = getRangeForLoadFromType(Ty))
       Load->setMetadata(llvm::LLVMContext::MD_range, RangeInfo);
 
+  // If this is a load from a restrict-qualified variable, then we have pointer
+  // aliasing assumptions that can be applied to the pointer value being loaded.
+  if (Ty.isRestrictQualified() && CGM.getCodeGenOpts().FullRestrict) {
+    auto NoAliasScopeMD = getExistingOrUnknownNoAliasScope(Addr.getPointer());
+    auto NoAliasDecl = getExistingNoAliasDeclOrNullptr(NoAliasScopeMD);
+    auto *NoAliasLoad = Builder.CreateNoAliasPointer(
+        Load, NoAliasDecl, Addr.getPointer(), NoAliasScopeMD);
+
+    // The llvm.noalias intrinsic can make use of the available alias info
+    llvm::AAMDNodes AAMetadata;
+    Load->getAAMetadata(AAMetadata);
+    NoAliasLoad->setAAMetadata(AAMetadata);
+
+    // ..as wel as the local restrict scope
+    // In both cases, this is about the 'P.addr'(getOperand(2) of llvm.noalias)
+    recordMemoryInstruction(NoAliasLoad);
+    return EmitFromMemory(NoAliasLoad, Ty);
+  }
   return EmitFromMemory(Load, Ty);
 }
 
 llvm::Value *CodeGenFunction::EmitToMemory(llvm::Value *Value, QualType Ty) {
   // Bool has a different representation in memory than in registers.
   if (hasBooleanRepresentation(Ty)) {
     // This should really always be an i1, but sometimes it's already
     // an i8, and it's awkward to track those cases down.

llvm/docs/LangRef.rst

 This describes a struct with two fields. The first is at offset 0 bytes
 with size 4 bytes, and has tbaa tag !1. The second is at offset 8 bytes
 and has size 4 bytes and has tbaa tag !2.
 
 Note that the fields need not be contiguous. In this example, there is a
 4 byte gap between the two fields. This gap represents padding which
 does not carry useful data and need not be preserved.
 
+.. _noalias_and_aliasscope:
+
 '``noalias``' and '``alias.scope``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 ``noalias`` and ``alias.scope`` metadata provide the ability to specify generic
 noalias memory-access sets. This means that some collection of memory access
 instructions (loads, stores, memory-accessing calls, etc.) that carry
 ``noalias`` metadata can specifically be specified not to alias with some other
 collection of memory access instructions that carry ``alias.scope`` metadata.

 '``load``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      <result> = load [volatile] <ty>, <ty>* <pointer>[, align <alignment>][, !nontemporal !<nontemp_node>][, !invariant.load !<empty_node>][, !invariant.group !<empty_node>][, !nonnull !<empty_node>][, !dereferenceable !<deref_bytes_node>][, !dereferenceable_or_null !<deref_bytes_node>][, !align !<align_node>][, !noundef !<empty_node>]
-      <result> = load atomic [volatile] <ty>, <ty>* <pointer> [syncscope("<target-scope>")] <ordering>, align <alignment> [, !invariant.group !<empty_node>]
+      <result> = load [volatile] <ty>, <ty>* <pointer>[, ptr_provenance <ty>* <channel>][,align <alignment>][, !nontemporal !<nontemp_node>][, !invariant.load !<empty_node>][, !invariant.group !<empty_node>][, !nonnull !<empty_node>][, !dereferenceable !<deref_bytes_node>][, !dereferenceable_or_null !<deref_bytes_node>][, !align !<align_node>][, !noundef !<empty_node>]
+      <result> = load atomic [volatile] <ty>, <ty>* <pointer>[, ptr_provenance <ty>* <channel>] [syncscope("<target-scope>")] <ordering>, align <alignment> [, !invariant.group !<empty_node>]
       !<nontemp_node> = !{ i32 1 }
       !<empty_node> = !{}
       !<deref_bytes_node> = !{ i64 <dereferenceable_bytes> }
       !<align_node> = !{ i64 <value_alignment> }
 
 Overview:
 """""""""
 

 Atomic loads produce :ref:`defined <memmodel>` results when they may see
 multiple atomic stores. The type of the pointee must be an integer, pointer, or
 floating-point type whose bit width is a power of two greater than or equal to
 eight and less than or equal to a target-specific size limit.  ``align`` must be
 explicitly specified on atomic loads, and the load has undefined behavior if the
 alignment is not set to a value which is at least the size in bytes of the
 pointee. ``!nontemporal`` does not have any defined semantics for atomic loads.
 
+The optional ``ptr_provenance`` argument specifies the noalias chain of the
+pointer operand. It has the same type as the pointer operand. Together with the
+``!noalias`` metadata on the instruction, and the ``llvm.provenance.noalias``,
+``llvm.noalias.arg.guard`` intrinsics in the chain, this is used to deduce if
+two load/store instructions may or may not alias. (See `Scoped NoAlias Related
+Intrinsics`_)
+
 The optional constant ``align`` argument specifies the alignment of the
 operation (that is, the alignment of the memory address). A value of 0
 or an omitted ``align`` argument means that the operation has the ABI
 alignment for the target. It is the responsibility of the code emitter
 to ensure that the alignment information is correct. Overestimating the
 alignment results in undefined behavior. Underestimating the alignment
 may produce less efficient code. An alignment of 1 is always safe. The
 maximum possible alignment is ``1 << 29``. An alignment value higher

 '``store``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      store [volatile] <ty> <value>, <ty>* <pointer>[, align <alignment>][, !nontemporal !<nontemp_node>][, !invariant.group !<empty_node>]        ; yields void
-      store atomic [volatile] <ty> <value>, <ty>* <pointer> [syncscope("<target-scope>")] <ordering>, align <alignment> [, !invariant.group !<empty_node>] ; yields void
+      store [volatile] <ty> <value>, <ty>* <pointer>[, ptr_provenance <ty>* <channel>][, align <alignment>][, !nontemporal !<nontemp_node>][, !invariant.group !<empty_node>]        ; yields void
+      store atomic [volatile] <ty> <value>, <ty>* <pointer>[, ptr_provenance <ty>* <channel>] [syncscope("<target-scope>")] <ordering>, align <alignment> [, !invariant.group !<empty_node>] ; yields void
       !<nontemp_node> = !{ i32 1 }
       !<empty_node> = !{}
 
 Overview:
 """""""""
 
 The '``store``' instruction is used to write to memory.
 

 Atomic loads produce :ref:`defined <memmodel>` results when they may see
 multiple atomic stores. The type of the pointee must be an integer, pointer, or
 floating-point type whose bit width is a power of two greater than or equal to
 eight and less than or equal to a target-specific size limit.  ``align`` must be
 explicitly specified on atomic stores, and the store has undefined behavior if
 the alignment is not set to a value which is at least the size in bytes of the
 pointee. ``!nontemporal`` does not have any defined semantics for atomic stores.
 
+The optional ``ptr_provenance`` argument specifies the noalias chain of the
+pointer operand. It has the same type as the pointer operand. Together with the
+``!noalias`` metadata on the instruction, and the ``llvm.provenance.noalias``,
+``llvm.noalias.arg.guard`` intrinsics in the chain, this is used to deduce if
+two load/store instructions may or may not alias. (See `Scoped NoAlias Related
+Intrinsics`_)
+
 The optional constant ``align`` argument specifies the alignment of the
 operation (that is, the alignment of the memory address). A value of 0
 or an omitted ``align`` argument means that the operation has the ABI
 alignment for the target. It is the responsibility of the code emitter
 to ensure that the alignment information is correct. Overestimating the
 alignment results in undefined behavior. Underestimating the
 alignment may produce less efficient code. An alignment of 1 is always
 safe. The maximum possible alignment is ``1 << 29``. An alignment

 
 Example:
 """"""""
 
 .. code-block:: llvm
 
       %ptr = alloca i32                               ; yields i32*:ptr
       store i32 3, i32* %ptr                          ; yields void
       %val = load i32, i32* %ptr                      ; yields i32:val = i32 3

   !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.
 
+Scoped NoAlias Related Intrinsics
+---------------------------------
+
+This set of intrinsics provide the basis for full C99 '``restrict``' support
+(See: iso-C99-n1256, 6.7.3.1 'Formal definition of restrict').
+
+In C99 restrict, accesses using a pointer based on a restrict pointer ``p``
+are assumed to not alias with other accesses that are not based on ``p``, as
+long as both accesses are within the scope of the declaration of  ``p``.
+
+The intrinsics work together with the '``!noalias``'
+:ref:`metadata <noalias_and_aliasscope>` annotations on memory instructions and
+the ``ptr_provenance`` of ``load`` and ``store`` instructions.
+
+The full set of intrinsics is:
+
+.. code-block:: llvm
+
+      %p.decl       = i8* @llvm.noalias.decl.XXX(i8** %p.alloc, i32 <p.objId>, metadata !p.scope)
+      %p.noalias    = i8* @llvm.noalias.XXX(i8* %p, i8* %p.decl, i8** %p.addr,
+                                            i32 <p.objId>, metadata !p.scope) !noalias !VisibleScopes
+      %prov.p       = i8* @llvm.provenance.noalias.XXX(i8* %prov.p, i8* %p.decl,
+                                            i8** p.addr, i8** %prov.p.addr,
+                                            i32 <p.objId>, metadata !p.scope) !noalias !VisibleScopes
+      %p.guard      = i8* @llvm.noalias.arg.guard.XXX(i8* %p, i8* %prov.p)
+      %p.copy.guard = %struct.FOO* @llvm.noalias.copy.guard.XXX(%struct.FOO* %p.block, i8* %p.decl,
+                                                              metadata !p.indices, metadata !p.scope)
+
+
+A detailed description of these intrinsics and how the work is explained in
+::doc::`Restrict and NoAlias Information in LLVM <NoAliasInfo>`
+
+.. _int_noalias_decl:
+
+'``llvm.noalias.decl``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. The return type and argument types are encoded
+in ``XXX``.
+
+::
+
+      declare i8* @llvm.noalias.decl.XXX(<type>* %p.alloca, i32 <p.objId>, metadata !p.scope)
+
+Overview:
+"""""""""
+
+``llvm.noalias.decl`` is inserted at the location of a restrict pointer
+declaration. It makes it possible to identify that a restrict scope is only
+valid inside the body of a loop. It also makes it possible to identify that a
+certain ``alloca`` is associated to an object that contains one or more
+restrict pointers.
+
+The handle it returns is always of type ``i8*`` and does
+not really represent a value. It is merely used to track a dependency on the
+declaration.
+
+Arguments:
+""""""""""
+
+The first argument ``%p.alloca`` points to the ``alloca`` that contains one
+or more restrict pointers. It can also be ``null`` if the ``alloca`` has been
+optimized away.
+
+The second argument ``p.objId`` is an integer representing an object id.
+
+The third argument ``!p.scope`` 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.noalias.decl`` intrinsic is used to identify the exact location of
+a *restrict pointer declaration*. When this is done inside the loop body,
+care must be taken to duplicate and uniquify the scopes and intrinsics when
+the loop is unrolled. Otherwise the restrict scope could spill across
+iterations.
+
+It also associates specific restrict properties to an ``alloca`` and is used
+to propagate those properties to ``llvm.noalias``, ``llvm.provenance.noalias`` and
+``llvm.noalias.copy.guard`` intrinsics when inlining and optimizations make
+the relationship between those intrinsics and the actual variable declaration
+visible.
+
+A detailed description of these intrinsics and how the work is explained in
+::doc::`Restrict and NoAlias Information in LLVM <NoAliasInfo>`
+
+.. _int_noalias:
+
+'``llvm.noalias``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. The return type and argument types are encoded
+in ``XXX``.
+
+::
+
+      declare <type>* @llvm.noalias.XXX(<type>* %p, i8* %p.decl, <type>** %p.addr,
+                                        i32 <p.objId>, metadata !p.scope)
+
+Overview:
+"""""""""
+
+``llvm.noalias`` is inserted at the moment that restrict properties are
+introduced. This is typically done after loading a restrict pointer from
+memory. Its return value can be seen as *the pointer value with restrict
+properties*
+
+Arguments:
+""""""""""
+
+The first argument ``%p`` is the pointer on which the aliasing assumption is
+being placed.
+
+The second argument ``%p.decl`` refers to the ``llvm.noalias.decl`` that is
+associated with the pointer declaration.
+
+The third argument ``%p.addr`` is the address in memory of this pointer.
+
+The fourth argument ``p.objId`` is an integer representing an object id.
+
+The fifth argument ``!p.scope`` 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.noalias`` intrinsic adds alias assumptions to the pointer
+computation path. It also blocks optimizations on this computation path.
+
+It will be transformed into a ``llvm.provenance.noalias`` intrinsic and moved onto
+the ``ptr_provenance`` path, so that pointer optimizations can still be
+done and the restrict information is not lost.
+
+A detailed description of these intrinsics and how the work is explained in
+::doc::`Restrict and NoAlias Information in LLVM <NoAliasInfo>`
+
+.. _int_provenance_noalias:
+
+'``llvm.provenance.noalias``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. The return type and argument types are encoded
+in ``XXX``.
+
+::
+
+      declare <type>* @llvm.provenance.noalias.XXX(<type>* %p, i8* %p.decl,
+                                             <type>** %p.addr, <type>** %prov.p.addr,
+                                             i32 <p.objId>, metadata !p.scope)
+
+Overview:
+"""""""""
+
+``llvm.provenance.noalias`` is inserted at the moment that restrict properties are
+introduced on the ``ptr_provenance``. This is typically done when a
+``llvm.noalias`` is converted into the ``llvm.provenance.noalias``
+
+The value it returns (``%prov.p``) is representing the pointer ``%p`` on the
+``ptr_provenance``.
+
+Arguments:
+""""""""""
+
+The first argument ``%p`` is the pointer (or its ``ptr_provenance``) on
+which the aliasing assumption is being placed.
+
+The second argument ``%p.decl`` refers to the ``llvm.noalias.decl`` that is
+associated with the pointer declaration.
+
+The third argument ``%p.addr`` is the address in memory of this pointer.
+
+The fourth argument ``%prov.p.addr`` represents ``%p.addr`` on the
+``ptr_provenance``.
+
+The fifth argument ``p.objId`` is an integer representing an object id.
+
+The sixth argument ``!p.scope`` 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.provenance.noalias`` intrinsic adds alias assumptions to the
+``ptr_provenance`` of the memory instructions that depends on it.
+
+For this purpose, the ``llvm.provenance.noalias`` itself is also considered to be
+a memory instruction and has its own ``ptr_provenance`` for the ``%p.addr``
+argument.
+
+A detailed description of these intrinsics and how the work is explained in
+::doc::`Restrict and NoAlias Information in LLVM <NoAliasInfo>`
+
+
+.. _int_noalias_arg_guard:
+
+'``llvm.noalias.arg.guard``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. The return type and argument types are encoded
+in ``XXX``.
+
+::
+
+      declare <type>* @llvm.noalias.arg.guard.XXX(<type>* %p, <type>* %prov.p)
+
+Overview:
+"""""""""
+
+The ``llvm.noalias.arg.guard`` intrinsic brings alias assumption properties that
+are on the ``ptr_provenance`` path of a pointer back into the
+computation path of that pointer.
+
+Arguments:
+""""""""""
+
+The first argument ``%p`` represents the computation path of the pointer.
+
+The second argument ``%prov.p`` represents the ``ptr_provenance`` path
+of that pointer.
+
+Semantics:
+""""""""""
+
+The ``llvm.noalias.arg.guard`` is typically generated when a ``llvm.noalias``
+intrinsic is converted to a ``llvm.provenance.noalias``, but the pointer escapes
+because it is used as an argument to a function or it is returned.
+
+It can typically be optimized away after inlining:
+* When it is encountered on the computation path, it is assumed to return the
+first argument ``%p``.
+
+When it is encountered on a ``ptr_provenance`` path, it is assumed to
+return the second argument ``%prov.p``.
+
+A detailed description of these intrinsics and how the work is explained in
+::doc::`Restrict and NoAlias Information in LLVM <NoAliasInfo>`
+
+
+.. _int_noalias_copy_guard:
+
+'``llvm.noalias.copy.guard``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+This is an overloaded intrinsic. The return type and argument types are encoded
+in ``XXX``.
+
+::
+
+      declare <type>* @llvm.noalias.copy.guard.XXX(<type>* %p.block, i8* %p.decl,
+                                                   metadata !p.indices, metadata !p.scope)
+
+Overview:
+"""""""""
+
+``llvm.noalias.copy.guard`` is inserted in the source pointer argument when a
+block of memory that will be copied (either using ``llvm.memcpy`` or a
+combination of ``load``/``store`` instructions) is associated to a variable
+that contains at least one restrict pointer. This could be a ``struct`` that
+contains one or more restrict member pointers, or an array of restrict pointers.
+
+The intrinsic returns the first argument.
+
+Arguments:
+""""""""""
+
+The first argument ``%p.block`` represents the block that will be copied.
+
+The second argument ``%p.decl`` refers to the ``llvm.noalias.decl`` that is
+associated with the block.
+
+The third argument ``!p.indices`` refers to a metadata list of metadata. Each
+entry refers to another metadata list of integers, describing the GEP path
+that contains a restrict pointer. A -1 value indicates that any index value
+is a match. See above for an example.
+
+Semantics:
+""""""""""
+
+The ``llvm.noalias.copy.guard`` provides extra restrict information about a
+block of memory that is copied over. When the memory copy is optimized away,
+they will still be able to match the pointer access to the correct restrict
+information.
+
+A detailed description of these intrinsics and how the work is explained in
+::doc::`Restrict and NoAlias Information in LLVM <NoAliasInfo>`
+
 
 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.set.rounding``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 }
 #endif
 
 AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
                                  const MemoryLocation &LocB,
                                  AAQueryInfo &AAQI) {
   assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
          "BasicAliasAnalysis doesn't support interprocedural queries.");
-  return aliasCheck(LocA.Ptr, LocA.Size, LocB.Ptr, LocB.Size, AAQI);
+  auto hasValidNoAliasProvenance = [](const AAMDNodes &AA) {
+    return AA.NoAliasProvenance && !isa<UndefValue>(AA.NoAliasProvenance);
+  };
+  return aliasCheck(LocA.Ptr, LocA.Size, LocB.Ptr, LocB.Size, AAQI,
+                    !(hasValidNoAliasProvenance(LocA.AATags) ||
+                      hasValidNoAliasProvenance(LocB.AATags)));
 }
 
 /// Checks to see if the specified callsite can clobber the specified memory
 /// object.
 ///
 /// Since we only look at local properties of this function, we really can't
 /// say much about this query.  We do, however, use simple "address taken"
 /// analysis on local objects.

 
   return Alias;
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
 /// array references.
 AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
                                       const Value *V2, LocationSize V2Size,
-                                      AAQueryInfo &AAQI) {
+                                      AAQueryInfo &AAQI, bool StripNoAlias) {
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are.
   if (V1Size.isZero() || V2Size.isZero())
     return AliasResult::NoAlias;
 
+  // FIXME: problem with MaxLookupSearch and aliasGEP.. is this still present?
   // Strip off any casts if they exist.
-  V1 = V1->stripPointerCastsForAliasAnalysis();
-  V2 = V2->stripPointerCastsForAliasAnalysis();
+  if (StripNoAlias) {
+    // No ptr_provenance - look through noalias intrinsics in a safe way
+    V1 = V1->stripPointerCastsAndInvariantGroupsAndNoAliasIntr();
+    V2 = V2->stripPointerCastsAndInvariantGroupsAndNoAliasIntr();
+  } else {
+    V1 = V1->stripPointerCastsForAliasAnalysis();
+    V2 = V2->stripPointerCastsForAliasAnalysis();
+  }
 
   // If V1 or V2 is undef, the result is NoAlias because we can always pick a
   // value for undef that aliases nothing in the program.
   if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
     return AliasResult::NoAlias;
 
   // Are we checking for alias of the same value?
   // Because we look 'through' phi nodes, we could look at "Value" pointers from

     // Function arguments can't alias with things that are known to be
     // unambigously identified at the function level.
     if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
         (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
       return AliasResult::NoAlias;
 
     // If one pointer is the result of a call/invoke or load and the other is a
     // non-escaping local object within the same function, then we know the
     // object couldn't escape to a point where the call could return it.

llvm/lib/IR/IRBuilder.cpp

 
 Instruction *IRBuilderBase::CreateNoAliasScopeDeclaration(Value *Scope) {
   Module *M = BB->getModule();
   auto *FnIntrinsic = Intrinsic::getDeclaration(
       M, Intrinsic::experimental_noalias_scope_decl, {});
   return createCallHelper(FnIntrinsic, {Scope}, this);
 }
 
+Instruction *IRBuilderBase::CreateNoAliasDeclaration(Value *AllocaPtr,
+                                                     Value *ObjId,
+                                                     Value *Scope) {
+  assert(AllocaPtr);
+
+  SmallVector<Type *, 1> Types = {Type::getInt8PtrTy(getContext()),
+                                  AllocaPtr->getType(), ObjId->getType()};
+  SmallVector<Value *, 1> Ops = {AllocaPtr, ObjId, Scope};
+
+  Module *M = BB->getModule();
+  auto *FnIntrinsic =
+      Intrinsic::getDeclaration(M, Intrinsic::noalias_decl, Types);
+  return createCallHelper(FnIntrinsic, Ops, this);
+}
+
+Instruction *IRBuilderBase::CreateNoAliasPointer(Value *Ptr, Value *NoAliasDecl,
+                                                 Value *AddrP, Value *ScopeTag,
+                                                 const Twine &Name,
+                                                 uint64_t ObjectId) {
+  assert(Ptr && AddrP);
+  Value *I64_0 =
+      ConstantInt::get(IntegerType::getInt64Ty(getContext()), ObjectId);
+  return CreateGenericNoAliasIntrinsic(Intrinsic::noalias, Ptr,
+                                       {NoAliasDecl, AddrP, I64_0}, {},
+                                       {ScopeTag}, Name);
+}
+
+Instruction *IRBuilderBase::CreateProvenanceNoAliasPlain(
+    Value *Ptr, Value *NoAliasDecl, Value *AddrP, Value *AddrP_Provenance,
+    Value *ObjId, MDNode *ScopeTag, const Twine &Name) {
+  assert(Ptr && AddrP && AddrP_Provenance);
+  return CreateGenericNoAliasIntrinsic(
+      Intrinsic::provenance_noalias, Ptr,
+      {NoAliasDecl, AddrP, AddrP_Provenance, ObjId}, {ScopeTag}, {}, Name);
+}
+
+Instruction *IRBuilderBase::CreateProvenanceNoAliasPlain(
+    Value *Ptr, Value *NoAliasDecl, Value *AddrP, Value *AddrP_Provenance,
+    Value *ObjId, Value *ScopeValue, const Twine &Name) {
+  assert(Ptr && AddrP && AddrP_Provenance);
+  return CreateGenericNoAliasIntrinsic(
+      Intrinsic::provenance_noalias, Ptr,
+      {NoAliasDecl, AddrP, AddrP_Provenance, ObjId}, {}, {ScopeValue}, Name);
+}
+
+Instruction *IRBuilderBase::CreateNoAliasArgGuard(Value *Ptr, Value *Provenance,
+                                                  const Twine &Name) {
+  return CreateGenericNoAliasIntrinsic(Intrinsic::noalias_arg_guard, Ptr,
+                                       {Provenance}, {}, {}, Name);
+}
+
+Value *IRBuilderBase::CreateNoAliasCopyGuard(Value *BasePtr, Value *NoAliasDecl,
+                                             MDNode *Offsets, MDNode *ScopeTag,
+                                             const Twine &Name) {
+  if (!Offsets)
+    return BasePtr;
+
+  assert(ScopeTag && "No scope metadata ?");
+  return CreateGenericNoAliasIntrinsic(Intrinsic::noalias_copy_guard, BasePtr,
+                                       {NoAliasDecl}, {Offsets, ScopeTag}, {},
+                                       Name);
+}
+
+Instruction *IRBuilderBase::CreateGenericNoAliasIntrinsic(
+    Intrinsic::ID ID, Value *Ptr, ArrayRef<Value *> args_opt,
+    ArrayRef<MDNode *> MDNodes, ArrayRef<Value *> MDValues, const Twine &Name) {
+  // FIXME: We can currently mangle just about everything, but not literal
+  // structs (for those, bitcast to i8*).
+  // FIXME: as far as I see in 'getMangledTypeStr', this should be ok now.
+  Value *CPtr = Ptr;
+  if (auto *STyp =
+          dyn_cast<StructType>(CPtr->getType()->getPointerElementType())) {
+    if (STyp->isLiteral())
+      CPtr = getCastedInt8PtrValue(CPtr);
+  }
+
+  SmallVector<Type *, 7> Types = {CPtr->getType()};
+  SmallVector<Value *, 7> Ops = {CPtr};
+  for (auto *A : args_opt) {
+    Types.push_back(A->getType());
+    Ops.push_back(A);
+  }
+  // For the metadata info, types must not be added:
+  for (auto *MD : MDNodes) {
+    Ops.push_back(MetadataAsValue::get(Context, MD));
+  }
+  Ops.insert(Ops.end(), MDValues.begin(), MDValues.end());
+  Module *M = BB->getModule();
+  auto *FnIntrinsic = Intrinsic::getDeclaration(M, ID, Types);
+  Instruction *Ret = createCallHelper(FnIntrinsic, Ops, this, Name);
+
+  if (Ret->getType() != Ptr->getType()) {
+    BitCastInst *BCI = new BitCastInst(Ret, Ptr->getType(), Name + ".cast");
+    BB->getInstList().insert(InsertPt, BCI);
+    SetInstDebugLocation(BCI);
+    Ret = BCI;
+  }
+
+  return Ret;
+}
+
 /// 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/Transforms/Scalar/LICM.cpp

         OpBundles.emplace_back("funclet", EHPad);
     }
 
     New = CallInst::Create(CI, OpBundles);
   } else {
     New = I.clone();
   }
 
+  AAMDNodes AAMetadata;
+  I.getAAMetadata(AAMetadata);
+  //@ FIXME: The other metadata should already be cloned ?
+  New->setAAMetadata(AAMetadata);
+  New->setAAMetadataNoAliasProvenance(AAMetadata);
+
   ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
   if (!I.getName().empty())
     New->setName(I.getName() + ".le");
 
   if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
     // Create a new MemoryAccess and let MemorySSA set its defining access.
     MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
         New, nullptr, New->getParent(), MemorySSA::Beginning);

       Instruction *InsertPos = LoopInsertPts[i];
       StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
       if (UnorderedAtomic)
         NewSI->setOrdering(AtomicOrdering::Unordered);
       NewSI->setAlignment(Align(Alignment));
       NewSI->setDebugLoc(DL);
       if (AATags)
         NewSI->setAAMetadata(AATags);
+      // Note: ptr_provenance propagation is not done here. A dependend
+      // provenance should be migrated first !
 
       if (MSSAU) {
         MemoryAccess *MSSAInsertPoint = MSSAInsertPts[i];
         MemoryAccess *NewMemAcc;
         if (!MSSAInsertPoint) {
           NewMemAcc = MSSAU->createMemoryAccessInBB(
               NewSI, nullptr, NewSI->getParent(), MemorySSA::Beginning);
         } else {

   // different sizes.  While we are at it, collect alignment and AA info.
   for (Value *ASIV : PointerMustAliases) {
     // Check that all of the pointers in the alias set have the same type.  We
     // cannot (yet) promote a memory location that is loaded and stored in
     // different sizes.
     if (SomePtr->getType() != ASIV->getType())
       return false;
 
-    for (User *U : ASIV->users()) {
+    for (auto U_it = ASIV->user_begin(), U_it_end = ASIV->user_end();
+         U_it != U_it_end; ++U_it) {
+      User *U = *U_it;
       // Ignore instructions that are outside the loop.
       Instruction *UI = dyn_cast<Instruction>(U);
       if (!UI || !CurLoop->contains(UI))
         continue;
 
       // If there is an non-load/store instruction in the loop, we can't promote
       // it.
       if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
+        if (U_it.getUse().getOperandNo() ==
+            Load->getNoaliasProvenanceOperandIndex())
+          continue;
         if (!Load->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Load->isAtomic();
         SawNotAtomic |= !Load->isAtomic();
 
         Align InstAlignment = Load->getAlign();
 
         // Note that proving a load safe to speculate requires proving
         // sufficient alignment at the target location.  Proving it guaranteed
         // to execute does as well.  Thus we can increase our guaranteed
         // alignment as well.
         if (!DereferenceableInPH || (InstAlignment > Alignment))
           if (isSafeToExecuteUnconditionally(*Load, DT, TLI, CurLoop,
                                              SafetyInfo, ORE,
                                              Preheader->getTerminator())) {
             DereferenceableInPH = true;
             Alignment = std::max(Alignment, InstAlignment);
           }
       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
+        if (U_it.getUse().getOperandNo() ==
+            Store->getNoaliasProvenanceOperandIndex())
+          continue;
+
         // Stores *of* the pointer are not interesting, only stores *to* the
         // pointer.
         if (UI->getOperand(1) != ASIV)
           continue;
         if (!Store->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Store->isAtomic();

 
         // If the store is not guaranteed to execute, we may still get
         // deref info through it.
         if (!DereferenceableInPH) {
           DereferenceableInPH = isDereferenceableAndAlignedPointer(
               Store->getPointerOperand(), Store->getValueOperand()->getType(),
               Store->getAlign(), MDL, Preheader->getTerminator(), DT, TLI);
         }
-      } else
-        return false; // Not a load or store.
+      } else {
+        // Not a load or store.
+        if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(UI)) {
+          if (II->getIntrinsicID() == Intrinsic::provenance_noalias ||
+              II->getIntrinsicID() == Intrinsic::noalias_arg_guard ||
+              II->getIntrinsicID() == Intrinsic::noalias_copy_guard) {
+            // those must not block promotion.
+            continue;
+          }
+        }
+        return false;
+      }
 
       // Merge the AA tags.
       if (LoopUses.empty()) {
         // On the first load/store, just take its AA tags.
         UI->getAAMetadata(AATags);
       } else if (AATags) {
         UI->getAAMetadata(AATags, /* Merge = */ true);
       }

   // value from the preheader that uses in the loop will use.
   LoadInst *PreheaderLoad = new LoadInst(
       SomePtr->getType()->getPointerElementType(), SomePtr,
       SomePtr->getName() + ".promoted", Preheader->getTerminator());
   if (SawUnorderedAtomic)
     PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
   PreheaderLoad->setAlignment(Alignment);
   PreheaderLoad->setDebugLoc(DebugLoc());
-  if (AATags)
+  if (AATags) {
     PreheaderLoad->setAAMetadata(AATags);
+    // Note: ptr_provenance propagation is not done here. A dependend provenance
+    // should be migrated first !
+  }
   SSA.AddAvailableValue(Preheader, PreheaderLoad);
 
   if (MSSAU) {
     MemoryAccess *PreheaderLoadMemoryAccess = MSSAU->createMemoryAccessInBB(
         PreheaderLoad, nullptr, PreheaderLoad->getParent(), MemorySSA::End);
     MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
     MSSAU->insertUse(NewMemUse, /*RenameUses=*/true);
   }

llvm/lib/Transforms/Scalar/SROA.cpp

 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"

 
 /// Hidden option to experiment with completely strict handling of inbounds
 /// GEPs.
 static cl::opt<bool> SROAStrictInbounds("sroa-strict-inbounds", cl::init(false),
                                         cl::Hidden);
 
 namespace {
 
+static llvm::IntrinsicInst *getBaseAsCopyGuardOrNull(llvm::Value *V) {
+  llvm::IntrinsicInst *II = dyn_cast<IntrinsicInst>(V->stripInBoundsOffsets());
+  if (II && (II->getIntrinsicID() == Intrinsic::noalias_copy_guard))
+    return II;
+
+  return nullptr;
+}
+
 /// A custom IRBuilder inserter which prefixes all names, but only in
 /// Assert builds.
 class IRBuilderPrefixedInserter final : public IRBuilderDefaultInserter {
   std::string Prefix;
 
   const Twine getNameWithPrefix(const Twine &Name) const {
     return Name.isTriviallyEmpty() ? Name : Prefix + Name;
   }

 static Value *foldPHINodeOrSelectInst(Instruction &I) {
   if (PHINode *PN = dyn_cast<PHINode>(&I)) {
     // If PN merges together the same value, return that value.
     return PN->hasConstantValue();
   }
   return foldSelectInst(cast<SelectInst>(I));
 }
 
+class MatchOffset {
+  uint64_t TargetOffset;
+  bool WasMatched = false;
+
+public:
+  MatchOffset(uint64_t TargetOffset) : TargetOffset(TargetOffset) {}
+
+  bool isOffsetTooLarge(uint64_t Offset) const {
+    return WasMatched || (Offset > TargetOffset);
+  }
+
+  void track(uint64_t Offset, uint64_t /*Size*/) {
+    if (TargetOffset == Offset)
+      WasMatched = true;
+  }
+
+public:
+  bool wasMatched() const { return WasMatched; }
+};
+
+class GatherRestrictPointers {
+  uint64_t SliceStart;
+  uint64_t SliceEnd;
+  SmallVectorImpl<std::pair<uint64_t, uint64_t>> &PtrOffsetSizes;
+
+public:
+  GatherRestrictPointers(uint64_t SliceStart, uint64_t SliceEnd,
+                         SmallVectorImpl<std::pair<uint64_t, uint64_t>> &C)
+      : SliceStart(SliceStart), SliceEnd(SliceEnd), PtrOffsetSizes(C) {}
+
+  bool isOffsetTooLarge(uint64_t Offset) const { return (Offset >= SliceEnd); }
+
+  void track(uint64_t Offset, uint64_t Size) {
+    if ((SliceStart <= Offset) && (Offset + Size) <= SliceEnd)
+      PtrOffsetSizes.push_back(std::make_pair(Offset - SliceStart, Size));
+  }
+};
+
+// Returns the 'GlobalSize' of the item under investigation
+template <typename T>
+uint64_t gatherValidNoAliasPointerOffsets(T &Handler,
+                                          const MDNode *NoAliasOffsets,
+                                          uint64_t BaseOffset = 0) {
+  MDBuilder::NoAliasOffsetsNode NAO(NoAliasOffsets);
+  // Input: { GlobalSize, [offset, (ptrsize | !struct), count]+ }
+
+  uint64_t GlobalSize = NAO.getGlobalSize();
+
+  unsigned NumFields = NAO.getNumEntries();
+  for (unsigned Index = 0; Index < NumFields; ++Index) {
+    if (Handler.isOffsetTooLarge(BaseOffset))
+      break;
+
+    auto F = NAO.getField(Index);
+    uint64_t LocalOffset = BaseOffset + F.Offset;
+    uint64_t LocalCount = F.Count;
+    // Note: a LocalCount of 0 will be bounded by the AllocSize
+    if (!F.Record) {
+      uint64_t LocalSize = F.Size;
+      assert(LocalSize > 0 && "We cannot handle a pointer size of 0");
+
+      uint64_t I = 0;
+      do {
+        if (Handler.isOffsetTooLarge(LocalOffset))
+          break;
+
+        Handler.track(LocalOffset, LocalSize);
+
+        I++;
+        LocalOffset += LocalSize;
+      } while (LocalCount != I);
+    } else {
+      uint64_t I = 0;
+      do {
+        if (Handler.isOffsetTooLarge(LocalOffset))
+          break;
+
+        uint64_t LocalSize =
+            gatherValidNoAliasPointerOffsets(Handler, F.Record, LocalOffset);
+        assert(((LocalCount != 0) || (LocalSize > 0)) &&
+               "We cannot handle a struct with empty size");
+        if (LocalSize == 0)
+          break;
+        LocalOffset += LocalSize;
+        I++;
+      } while (LocalCount != I);
+    }
+  }
+
+  return GlobalSize;
+}
+
 /// Builder for the alloca slices.
 ///
 /// This class builds a set of alloca slices by recursively visiting the uses
 /// of an alloca and making a slice for each load and store at each offset.
 class AllocaSlices::SliceBuilder : public PtrUseVisitor<SliceBuilder> {
   friend class PtrUseVisitor<SliceBuilder>;
   friend class InstVisitor<SliceBuilder>;
 
   using Base = PtrUseVisitor<SliceBuilder>;
 
   const uint64_t AllocSize;
   AllocaSlices &AS;
 
   SmallDenseMap<Instruction *, unsigned> MemTransferSliceMap;
   SmallDenseMap<Instruction *, uint64_t> PHIOrSelectSizes;
 
   /// Set to de-duplicate dead instructions found in the use walk.
   SmallPtrSet<Instruction *, 4> VisitedDeadInsts;
 
+  // llvm.noalias.copy.guard, offset
+  SmallVector<std::pair<IntrinsicInst *, uint64_t>, 4> PendingNoAliasCopyGuards;
+
 public:
   SliceBuilder(const DataLayout &DL, AllocaInst &AI, AllocaSlices &AS)
       : PtrUseVisitor<SliceBuilder>(DL),
         AllocSize(DL.getTypeAllocSize(AI.getAllocatedType()).getFixedSize()),
         AS(AS) {}
 
+  PtrInfo visitPtrAndNoAliasCopyGuards(Instruction &I) {
+    PtrInfo PI = visitPtr(I);
+    if (!PI.isAborted()) {
+      for (auto &CGAndOffset : PendingNoAliasCopyGuards)
+        visitPendingNoAliasCopyGuard(*CGAndOffset.first, CGAndOffset.second);
+    }
+
+    return PI;
+  }
+
 private:
   void markAsDead(Instruction &I) {
     if (VisitedDeadInsts.insert(&I).second)
       AS.DeadUsers.push_back(&I);
   }
 
   void insertUse(Instruction &I, const APInt &Offset, uint64_t Size,
                  bool IsSplittable = false) {

 
     insertUse(I, Offset, Size, IsSplittable);
   }
 
   void visitLoadInst(LoadInst &LI) {
     assert((!LI.isSimple() || LI.getType()->isSingleValueType()) &&
            "All simple FCA loads should have been pre-split");
 
+    if (U->getOperandNo() == LI.getNoaliasProvenanceOperandIndex()) {
+      // Skip provenance
+      assert(LI.hasNoaliasProvenanceOperand() &&
+             LI.getNoaliasProvenanceOperand() == *U);
+      return;
+    }
+
     if (!IsOffsetKnown)
       return PI.setAborted(&LI);
 
     if (LI.isVolatile() &&
         LI.getPointerAddressSpace() != DL.getAllocaAddrSpace())
       return PI.setAborted(&LI);
 
     if (isa<ScalableVectorType>(LI.getType()))
       return PI.setAborted(&LI);
 
     uint64_t Size = DL.getTypeStoreSize(LI.getType()).getFixedSize();
     return handleLoadOrStore(LI.getType(), LI, Offset, Size, LI.isVolatile());
   }
 
   void visitStoreInst(StoreInst &SI) {
+    if (U->getOperandNo() == SI.getNoaliasProvenanceOperandIndex()) {
+      // Skip provenance
+      assert(SI.hasNoaliasProvenanceOperand() &&
+             SI.getNoaliasProvenanceOperand() == *U);
+      return;
+    }
+
     Value *ValOp = SI.getValueOperand();
     if (ValOp == *U)
       return PI.setEscapedAndAborted(&SI);
     if (!IsOffsetKnown)
       return PI.setAborted(&SI);
 
     if (SI.isVolatile() &&
         SI.getPointerAddressSpace() != DL.getAllocaAddrSpace())

                         << "    alloca: " << AS.AI << "\n"
                         << "       use: " << SI << "\n");
       return markAsDead(SI);
     }
 
     assert((!SI.isSimple() || ValOp->getType()->isSingleValueType()) &&
            "All simple FCA stores should have been pre-split");
     handleLoadOrStore(ValOp->getType(), SI, Offset, Size, SI.isVolatile());
+
+    if (auto *LI = dyn_cast<LoadInst>(SI.getValueOperand())) {
+      // When we get here, the Store is based on an AllocaInst.
+      // Make sure to track any source dependencies on a llvm.noalias.copy.guard
+      // when the source was not based on the AllocaInst.
+      rememberIfBasedOnNoAliasCopyGuard(LI->getPointerOperand(),
+                                        Offset.getZExtValue());
+    }
   }
 
   void visitMemSetInst(MemSetInst &II) {
     assert(II.getRawDest() == *U && "Pointer use is not the destination?");
     ConstantInt *Length = dyn_cast<ConstantInt>(II.getLength());
     if ((Length && Length->getValue() == 0) ||
         (IsOffsetKnown && Offset.uge(AllocSize)))
       // Zero-length mem transfer intrinsics can be ignored entirely.

     }
 
     // Insert the use now that we've fixed up the splittable nature.
     insertUse(II, Offset, Size, /*IsSplittable=*/Inserted && Length);
 
     // Check that we ended up with a valid index in the map.
     assert(AS.Slices[PrevIdx].getUse()->getUser() == &II &&
            "Map index doesn't point back to a slice with this user.");
+
+    // When we get here, one of the operands is based on an AllocaInst.
+    // Make sure to track any source dependencies on a llvm.noalias.copy.guard
+    // when the source was not based on the AllocaInst.
+    rememberIfBasedOnNoAliasCopyGuard(II.getSource(), Offset.getZExtValue());
+  }
+
+  void rememberIfBasedOnNoAliasCopyGuard(Value *V, uint64_t TheOffset) {
+    if (auto II = getBaseAsCopyGuardOrNull(V)) {
+      for (auto CGOff : PendingNoAliasCopyGuards) {
+        if (CGOff.first == II && CGOff.second == TheOffset)
+          return;
+      }
+
+      PendingNoAliasCopyGuards.emplace_back(II, TheOffset);
+    }
+  }
+
+  void visitNoAliasCopyGuard(IntrinsicInst &II) {
+    assert(II.getIntrinsicID() == Intrinsic::noalias_copy_guard &&
+           "We need a llvm.noalias.copy.guard here");
+    rememberIfBasedOnNoAliasCopyGuard(&II, Offset.getZExtValue());
+    enqueueUsers(II);
+  }
+
+  void visitPendingNoAliasCopyGuard(IntrinsicInst &II, uint64_t BaseOffset) {
+    LLVM_DEBUG(
+        llvm::dbgs()
+        << "AllocaSlices::SliceBuilder: handling llvm.noalias.copy.guard:" << II
+        << ":@" << BaseOffset << ":" << AllocSize << "\n");
+    // Identify the usage, so that it can be split
+    if (II.use_empty())
+      return markAsDead(II);
+
+    SmallVector<std::pair<uint64_t, uint64_t>, 4> PtrOffsetSizes;
+
+    // Provide as many slices as we have restrict pointers
+    MDNode *CopyGuardIndices =
+        cast<MDNode>(cast<MetadataAsValue>(
+                         II.getOperand(Intrinsic::NoAliasCopyGuardIndicesArg))
+                         ->getMetadata());
+    auto Tracker =
+        GatherRestrictPointers(BaseOffset, AllocSize, PtrOffsetSizes);
+    gatherValidNoAliasPointerOffsets(Tracker, CopyGuardIndices);
+    LLVM_DEBUG(llvm::dbgs() << "noalias pointers are at:\n";
+               for (auto &P
+                    : PtrOffsetSizes) {
+                 llvm::dbgs()
+                     << " - [" << P.first << "," << P.first + P.second << ")\n";
+               });
+
+    U = &II.getOperandUse(0);
+    unsigned AS = II.getOperand(0)->getType()->getPointerAddressSpace();
+    APInt TheBaseOffset(DL.getIndexSizeInBits(AS), BaseOffset);
+    for (auto &P : PtrOffsetSizes) {
+      APInt TheOffset = TheBaseOffset + P.first;
+      insertUse(II, TheOffset, P.second, false);
+    }
   }
 
   // Disable SRoA for any intrinsics except for lifetime invariants and
   // invariant group.
   // FIXME: What about debug intrinsics? This matches old behavior, but
   // doesn't make sense.
   void visitIntrinsicInst(IntrinsicInst &II) {
     if (II.isDroppable()) {
       AS.DeadUseIfPromotable.push_back(U);
       return;
     }
 
     if (!IsOffsetKnown)
       return PI.setAborted(&II);
 
     if (II.isLifetimeStartOrEnd()) {
       ConstantInt *Length = cast<ConstantInt>(II.getArgOperand(0));
       uint64_t Size = std::min(AllocSize - Offset.getLimitedValue(),
                                Length->getLimitedValue());
       insertUse(II, Offset, Size, true);
       return;
     }
+    // look through noalias intrinsics
+    if (II.getIntrinsicID() == Intrinsic::noalias_decl) {
+      insertUse(II, Offset, AllocSize, true);
+      // do not enqueue direct users (?) They should be handled through a
+      // dependency on the original alloca
+      return;
+    }
+    if (II.getIntrinsicID() == Intrinsic::noalias) {
+      if (U->getOperandNo() == Intrinsic::NoAliasIdentifyPArg) {
+        insertUse(II, Offset,
+                  DL.getTypeStoreSize(
+                      II.getOperand(Intrinsic::NoAliasIdentifyPArg)->getType()),
+                  false);
+        return;
+      }
+      if (U->getOperandNo() == 0) {
+        assert(II.getOperand(0) == *U);
+        // _only_ look through the first argument
+        enqueueUsers(II);
+      }
+      return;
+    }
+    if (II.getIntrinsicID() == Intrinsic::provenance_noalias) {
+      if (U->getOperandNo() == Intrinsic::ProvenanceNoAliasIdentifyPArg) {
+        insertUse(II, Offset,
+                  DL.getTypeStoreSize(
+                      II.getOperand(Intrinsic::ProvenanceNoAliasIdentifyPArg)
+                          ->getType()),
+                  false);
+        return;
+      }
+      // hmmm - do not look through the first argument for a
+      // llvm.provenance.noalias
+      return;
+    }
+    if (II.getIntrinsicID() == Intrinsic::noalias_arg_guard) {
+      if (U->getOperandNo() == 0) {
+        // _only_ look through the first argument
+        enqueueUsers(II);
+      }
+      return;
+    }
+    if (II.getIntrinsicID() == Intrinsic::noalias_copy_guard) {
+      visitNoAliasCopyGuard(II);
+      return;
+    }
 
     if (II.isLaunderOrStripInvariantGroup()) {
       enqueueUsers(II);
       return;
     }
 
     Base::visitIntrinsicInst(II);
   }

 
 AllocaSlices::AllocaSlices(const DataLayout &DL, AllocaInst &AI)
     :
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
       AI(AI),
 #endif
       PointerEscapingInstr(nullptr) {
   SliceBuilder PB(DL, AI, *this);
-  SliceBuilder::PtrInfo PtrI = PB.visitPtr(AI);
+  SliceBuilder::PtrInfo PtrI = PB.visitPtrAndNoAliasCopyGuards(AI);
   if (PtrI.isEscaped() || PtrI.isAborted()) {
     // FIXME: We should sink the escape vs. abort info into the caller nicely,
     // possibly by just storing the PtrInfo in the AllocaSlices.
     PointerEscapingInstr = PtrI.getEscapingInst() ? PtrI.getEscapingInst()
                                                   : PtrI.getAbortingInst();
     assert(PointerEscapingInstr && "Did not track a bad instruction");
     return;
   }

 
 LLVM_DUMP_METHOD void AllocaSlices::dump(const_iterator I) const {
   print(dbgs(), I);
 }
 LLVM_DUMP_METHOD void AllocaSlices::dump() const { print(dbgs()); }
 
 #endif // !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 
+static IntrinsicInst *partitionRepresentsNoAliasPointer(Partition &P) {
+  // A partition that has a 'llvm.noalias.copy.guard' use, represents a
+  // noalias pointer
+  for (auto &I : P) {
+    Use *U = I.getUse();
+    if (auto *II = dyn_cast<IntrinsicInst>(U->getUser()))
+      if (II->getIntrinsicID() == Intrinsic::noalias_copy_guard)
+        return II;
+  }
+  return nullptr;
+}
+
 /// Walk the range of a partitioning looking for a common type to cover this
 /// sequence of slices.
 static std::pair<Type *, IntegerType *>
 findCommonType(AllocaSlices::const_iterator B, AllocaSlices::const_iterator E,
                uint64_t EndOffset) {
   Type *Ty = nullptr;
   bool TyIsCommon = true;
   IntegerType *ITy = nullptr;

 
   return true;
 }
 
 static void speculatePHINodeLoads(PHINode &PN) {
   LLVM_DEBUG(dbgs() << "    original: " << PN << "\n");
 
   LoadInst *SomeLoad = cast<LoadInst>(PN.user_back());
-  Type *LoadTy = SomeLoad->getType();
+  if (SomeLoad->getPointerOperand() != &PN) {
+    // this must be the provenance -> ignore the speculation for now
+    LLVM_DEBUG(llvm::dbgs() << "    not speculating dependency on provenance: "
+                            << *SomeLoad << "\n");
+    return;
+  }
+
+  Type *LoadTy = cast<PointerType>(PN.getType())->getElementType();
   IRBuilderTy PHIBuilder(&PN);
   PHINode *NewPN = PHIBuilder.CreatePHI(LoadTy, PN.getNumIncomingValues(),
                                         PN.getName() + ".sroa.speculated");
 
   // Get the AA tags and alignment to use from one of the loads. It does not
   // matter which one we get and if any differ.
   AAMDNodes AATags;
   SomeLoad->getAAMetadata(AATags);

 
   const DataLayout &DL;
   AllocaSlices &AS;
   SROA &Pass;
   AllocaInst &OldAI, &NewAI;
   const uint64_t NewAllocaBeginOffset, NewAllocaEndOffset;
   Type *NewAllocaTy;
 
+  IntrinsicInst *OldNoAliasDecl = nullptr;
+  IntrinsicInst *NewNoAliasDecl = nullptr;
+
   // This is a convenience and flag variable that will be null unless the new
   // alloca's integer operations should be widened to this integer type due to
   // passing isIntegerWideningViable above. If it is non-null, the desired
   // integer type will be stored here for easy access during rewriting.
   IntegerType *IntTy;
 
   // If we are rewriting an alloca partition which can be written as pure
   // vector operations, we stash extra information here. When VecTy is

 
   // The new offsets of the slice currently being rewritten relative to the
   // original alloca.
   uint64_t NewBeginOffset = 0, NewEndOffset = 0;
 
   uint64_t SliceSize = 0;
   bool IsSplittable = false;
   bool IsSplit = false;
+  bool RepresentsNoAlias = false;
   Use *OldUse = nullptr;
   Instruction *OldPtr = nullptr;
 
   // Track post-rewrite users which are PHI nodes and Selects.
   SmallSetVector<PHINode *, 8> &PHIUsers;
   SmallSetVector<SelectInst *, 8> &SelectUsers;
 
   // Utility IR builder, whose name prefix is setup for each visited use, and
   // the insertion point is set to point to the user.
   IRBuilderTy IRB;
 
 public:
   AllocaSliceRewriter(const DataLayout &DL, AllocaSlices &AS, SROA &Pass,
                       AllocaInst &OldAI, AllocaInst &NewAI,
                       uint64_t NewAllocaBeginOffset,
                       uint64_t NewAllocaEndOffset, bool IsIntegerPromotable,
                       VectorType *PromotableVecTy,
                       SmallSetVector<PHINode *, 8> &PHIUsers,
-                      SmallSetVector<SelectInst *, 8> &SelectUsers)
+                      SmallSetVector<SelectInst *, 8> &SelectUsers,
+                      bool ReprNoAlias)
       : DL(DL), AS(AS), Pass(Pass), OldAI(OldAI), NewAI(NewAI),
         NewAllocaBeginOffset(NewAllocaBeginOffset),
         NewAllocaEndOffset(NewAllocaEndOffset),
         NewAllocaTy(NewAI.getAllocatedType()),
         IntTy(
             IsIntegerPromotable
                 ? Type::getIntNTy(NewAI.getContext(),
                                   DL.getTypeSizeInBits(NewAI.getAllocatedType())
                                       .getFixedSize())
                 : nullptr),
         VecTy(PromotableVecTy),
         ElementTy(VecTy ? VecTy->getElementType() : nullptr),
         ElementSize(VecTy ? DL.getTypeSizeInBits(ElementTy).getFixedSize() / 8
                           : 0),
-        PHIUsers(PHIUsers), SelectUsers(SelectUsers),
-        IRB(NewAI.getContext(), ConstantFolder()) {
+        RepresentsNoAlias(ReprNoAlias), PHIUsers(PHIUsers),
+        SelectUsers(SelectUsers), IRB(NewAI.getContext(), ConstantFolder()) {
     if (VecTy) {
       assert((DL.getTypeSizeInBits(ElementTy).getFixedSize() % 8) == 0 &&
              "Only multiple-of-8 sized vector elements are viable");
       ++NumVectorized;
     }
     assert((!IntTy && !VecTy) || (IntTy && !VecTy) || (!IntTy && VecTy));
+    prepareNoAliasDecl();
   }
 
   bool visit(AllocaSlices::const_iterator I) {
     bool CanSROA = true;
     BeginOffset = I->beginOffset();
     EndOffset = I->endOffset();
     IsSplittable = I->isSplittable();
     IsSplit =
         BeginOffset < NewAllocaBeginOffset || EndOffset > NewAllocaEndOffset;
     LLVM_DEBUG(dbgs() << "  rewriting " << (IsSplit ? "split " : ""));
     LLVM_DEBUG(AS.printSlice(dbgs(), I, ""));
     LLVM_DEBUG(dbgs() << "\n");
 
     // Compute the intersecting offset range.
     assert(BeginOffset < NewAllocaEndOffset);
     assert(EndOffset > NewAllocaBeginOffset);
     NewBeginOffset = std::max(BeginOffset, NewAllocaBeginOffset);
     NewEndOffset = std::min(EndOffset, NewAllocaEndOffset);
 
     SliceSize = NewEndOffset - NewBeginOffset;
 
     OldUse = I->getUse();
-    OldPtr = cast<Instruction>(OldUse->get());
+    OldPtr = dyn_cast<Instruction>(OldUse->get());
 
     Instruction *OldUserI = cast<Instruction>(OldUse->getUser());
     IRB.SetInsertPoint(OldUserI);
     IRB.SetCurrentDebugLocation(OldUserI->getDebugLoc());
     IRB.getInserter().SetNamePrefix(
         Twine(NewAI.getName()) + "." + Twine(BeginOffset) + ".");
 
     CanSROA &= visit(cast<Instruction>(OldUse->getUser()));

     New->copyMetadata(II, {LLVMContext::MD_mem_parallel_loop_access,
                            LLVMContext::MD_access_group});
     if (AATags)
       New->setAAMetadata(AATags.shift(NewBeginOffset - BeginOffset));
     LLVM_DEBUG(dbgs() << "          to: " << *New << "\n");
     return !II.isVolatile();
   }
 
+  Instruction *detachFromNoAliasCopyGuard(Instruction *DepPtr,
+                                          Instruction *NACG) {
+    assert(getBaseAsCopyGuardOrNull(DepPtr) == NACG &&
+           "DepPtr must depend on NACG");
+
+    // Follow first arg until we hit the llvm.noalias.copy.guard
+    Instruction *Ptr = cast<Instruction>(DepPtr);
+    while (true) {
+      if (Ptr->getNumUses() != 1)
+        break;
+      Instruction *ParentPtr = cast<Instruction>(Ptr->getOperand(0));
+      if (ParentPtr == NACG) {
+        // we got here with only single uses - just remove the dependency
+        Ptr->setOperand(0, NACG->getOperand(0));
+        return DepPtr;
+      }
+      Ptr = ParentPtr;
+    }
+
+    assert(false && "Multiple use found - we should duplicate the chain");
+    return DepPtr;
+  }
+
+  Instruction *maybeIntroduceNoAlias(LoadInst *Load, Value *PtrOperand) {
+    if (!RepresentsNoAlias)
+      return Load;
+
+    auto NACG = getBaseAsCopyGuardOrNull(PtrOperand);
+    if (NACG == nullptr) {
+      // strange, but could happen
+      LLVM_DEBUG(llvm::dbgs()
+                 << "maybeIntroduceNoAlias: RepresentsNoAlias is true,"
+                    "but no copy.guard seen\n");
+      return Load;
+    }
+
+    Value *NoAliasDecl =
+        NACG->getOperand(Intrinsic::NoAliasCopyGuardNoAliasDeclArg);
+
+    auto ScopeArg = NACG->getOperand(Intrinsic::NoAliasCopyGuardScopeArg);
+
+    auto NewDepPtr = Load->getPointerOperand();
+    if (auto NACG2 = getBaseAsCopyGuardOrNull(NewDepPtr)) {
+      assert(NACG2 == NACG && "llvm.noalias.copy.guard dep must be identical");
+      (void)NACG2;
+      NewDepPtr = detachFromNoAliasCopyGuard(
+          cast<Instruction>(Load->getPointerOperand()), NACG);
+      Load->setOperand(Load->getPointerOperandIndex(), NewDepPtr);
+    }
+
+    if (Load->getType()->isPointerTy()) {
+      auto *NoAlias = IRB.CreateNoAliasPointer(
+          Load, NoAliasDecl, NewDepPtr, ScopeArg, Load->getName() + ".noalias");
+      auto *NoAliasInstr = isa<BitCastInst>(NoAlias)
+                               ? cast<Instruction>(NoAlias->getOperand(0))
+                               : NoAlias;
+      if (NoAliasDecl == OldNoAliasDecl) {
+        assert(NewNoAliasDecl->getOperand(Intrinsic::NoAliasDeclScopeArg) ==
+                   ScopeArg &&
+               "New llvm.noalias.decl must have same scope");
+        NoAliasInstr->setOperand(Intrinsic::NoAliasNoAliasDeclArg,
+                                 NewNoAliasDecl);
+        NoAliasInstr->setOperand(
+            Intrinsic::NoAliasIdentifyPObjIdArg,
+            NewNoAliasDecl->getOperand(Intrinsic::NoAliasDeclObjIdArg));
+      }
+
+      LLVM_DEBUG(llvm::dbgs() << "   introduce: " << *NoAliasInstr << "\n");
+      if (NoAlias != NoAliasInstr)
+        LLVM_DEBUG(llvm::dbgs() << "   introduce: " << *NoAlias << "\n");
+
+      return NoAlias;
+    }
+
+    assert(false && "Need PtrToInt ?");
+    return Load;
+  }
+
   bool visitMemTransferInst(MemTransferInst &II) {
     // Rewriting of memory transfer instructions can be a bit tricky. We break
     // them into two categories: split intrinsics and unsplit intrinsics.
 
     LLVM_DEBUG(dbgs() << "    original: " << II << "\n");
 
     AAMDNodes AATags;
     II.getAAMetadata(AATags);

     MaybeAlign DstAlign = SliceAlign;
     if (!IsDest) {
       std::swap(SrcPtr, DstPtr);
       std::swap(SrcAlign, DstAlign);
     }
 
     Value *Src;
     if (VecTy && !IsWholeAlloca && !IsDest) {
+      // FIXME: should we handle noalias annotations here ?
       Src = IRB.CreateAlignedLoad(NewAI.getAllocatedType(), &NewAI,
                                   NewAI.getAlign(), "load");
       Src = extractVector(IRB, Src, BeginIndex, EndIndex, "vec");
     } else if (IntTy && !IsWholeAlloca && !IsDest) {
-      Src = IRB.CreateAlignedLoad(NewAI.getAllocatedType(), &NewAI,
+      LoadInst *Load = IRB.CreateAlignedLoad(NewAI.getAllocatedType(), &NewAI,
                                              NewAI.getAlign(), "load");
+      Src = maybeIntroduceNoAlias(Load, II.getSource());
       Src = convertValue(DL, IRB, Src, IntTy);
       uint64_t Offset = NewBeginOffset - NewAllocaBeginOffset;
       Src = extractInteger(DL, IRB, Src, SubIntTy, Offset, "extract");
     } else {
       LoadInst *Load = IRB.CreateAlignedLoad(OtherTy, SrcPtr, SrcAlign,
                                              II.isVolatile(), "copyload");
       Load->copyMetadata(II, {LLVMContext::MD_mem_parallel_loop_access,
                               LLVMContext::MD_access_group});
       if (AATags)
         Load->setAAMetadata(AATags.shift(NewBeginOffset - BeginOffset));
-      Src = Load;
+      Src = maybeIntroduceNoAlias(Load, II.getSource());
     }
 
     if (VecTy && !IsWholeAlloca && IsDest) {
       Value *Old = IRB.CreateAlignedLoad(NewAI.getAllocatedType(), &NewAI,
                                          NewAI.getAlign(), "oldload");
       Src = insertVector(IRB, Old, Src, BeginIndex, "vec");
     } else if (IntTy && !IsWholeAlloca && IsDest) {
       Value *Old = IRB.CreateAlignedLoad(NewAI.getAllocatedType(), &NewAI,
                                          NewAI.getAlign(), "oldload");
       Old = convertValue(DL, IRB, Old, IntTy);
       uint64_t Offset = NewBeginOffset - NewAllocaBeginOffset;
       Src = insertInteger(DL, IRB, Old, Src, Offset, "insert");
       Src = convertValue(DL, IRB, Src, NewAllocaTy);
     }
 
     StoreInst *Store = cast<StoreInst>(
         IRB.CreateAlignedStore(Src, DstPtr, DstAlign, II.isVolatile()));
     Store->copyMetadata(II, {LLVMContext::MD_mem_parallel_loop_access,
                              LLVMContext::MD_access_group});
     if (AATags)
       Store->setAAMetadata(AATags.shift(NewBeginOffset - BeginOffset));
-    LLVM_DEBUG(dbgs() << "          to: " << *Store << "\n");
+    LLVM_DEBUG(dbgs() << "(3)       to: " << *Store << "\n");
     return !II.isVolatile();
   }
 
-  bool visitIntrinsicInst(IntrinsicInst &II) {
-    assert((II.isLifetimeStartOrEnd() || II.isDroppable()) &&
-           "Unexpected intrinsic!");
+  void prepareNoAliasDecl() {
+    OldNoAliasDecl = nullptr;
+    NewNoAliasDecl = nullptr;
+    for (auto U : OldAI.users()) {
+      IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
+      if (II && II->getIntrinsicID() == Intrinsic::noalias_decl) {
+        if (OldNoAliasDecl) {
+          // We alreay found a llvm.noalias.decl - leave it up to the visiter to
+          // propagate
+          OldNoAliasDecl = nullptr;
+          NewNoAliasDecl = nullptr;
+          break;
+        }
+        IRB.SetInsertPoint(II);
+        IRB.SetCurrentDebugLocation(II->getDebugLoc());
+        IRB.getInserter().SetNamePrefix(Twine(NewAI.getName()) +
+                                        ".noalias.decl.");
+
+        OldNoAliasDecl = II;
+        LLVM_DEBUG(dbgs() << "Found llvm.noalias.decl: " << *II << "\n");
+        ConstantInt *OldId = cast<ConstantInt>(
+            II->getArgOperand(Intrinsic::NoAliasDeclObjIdArg));
+        NewNoAliasDecl = cast<IntrinsicInst>(IRB.CreateNoAliasDeclaration(
+            &NewAI, NewAllocaBeginOffset + OldId->getZExtValue(),
+            II->getArgOperand(2)));
+        LLVM_DEBUG(dbgs() << "New   llvm.noalias.decl: " << *NewNoAliasDecl
+                          << "\n");
+        // continue - it is possible we see multiple llvm.noalias.decl!
+      }
+    }
+  }
+
+  bool visitNoAliasDeclIntrinsicInst(IntrinsicInst &II) {
+    assert(II.getIntrinsicID() == Intrinsic::noalias_decl);
+    LLVM_DEBUG(dbgs() << "    original: " << II << "\n");
+    Value *New;
+    if (OldNoAliasDecl) {
+      assert(OldNoAliasDecl == &II);
+      assert(NewNoAliasDecl != nullptr);
+      New = NewNoAliasDecl;
+    } else {
+      assert(NewNoAliasDecl == nullptr);
+      ConstantInt *OldId =
+          cast<ConstantInt>(II.getArgOperand(Intrinsic::NoAliasDeclObjIdArg));
+      New = cast<IntrinsicInst>(IRB.CreateNoAliasDeclaration(
+          &NewAI, NewAllocaBeginOffset + OldId->getZExtValue(),
+          II.getArgOperand(2)));
+    }
+    (void)New;
+    LLVM_DEBUG(dbgs() << "          to: " << *New << "\n");
+
+    // Record this instruction for deletion.
+    Pass.DeadInsts.push_back(&II);
+
+    // nothing else to do - preparation was already done
+    return true;
+  }
+
+  bool visitProvenanceNoAliasIntrinsicInst(IntrinsicInst &II) {
+    assert(II.getIntrinsicID() == Intrinsic::provenance_noalias);
+    assert(II.getArgOperand(Intrinsic::ProvenanceNoAliasIdentifyPArg) ==
+           OldPtr);
+    LLVM_DEBUG(dbgs() << "    original: " << II << "\n");
+    if (II.getArgOperand(Intrinsic::ProvenanceNoAliasNoAliasDeclArg) ==
+        OldNoAliasDecl) {
+      assert(OldNoAliasDecl && NewNoAliasDecl &&
+             "If we get here, we must have an old and a new llvm.noalias.decl");
+      II.setArgOperand(Intrinsic::ProvenanceNoAliasNoAliasDeclArg,
+                       NewNoAliasDecl);
+    }
+    II.setArgOperand(
+        Intrinsic::ProvenanceNoAliasIdentifyPArg,
+        getNewAllocaSlicePtr(
+            IRB, II.getArgOperand(Intrinsic::ProvenanceNoAliasIdentifyPArg)
+                     ->getType()));
+    if (NewAllocaBeginOffset > 0) {
+      Value *OldObjIdV =
+          II.getArgOperand(Intrinsic::ProvenanceNoAliasIdentifyPObjIdArg);
+      auto NewObjId = ConstantInt::get(
+          OldObjIdV->getType(),
+          cast<ConstantInt>(OldObjIdV)->getZExtValue() + NewAllocaBeginOffset);
+      II.setArgOperand(Intrinsic::ProvenanceNoAliasIdentifyPObjIdArg, NewObjId);
+    }
+    LLVM_DEBUG(dbgs() << "          to: " << II << "\n");
+    deleteIfTriviallyDead(OldPtr);
+    return true;
+  }
+
+  bool visitNoAliasIntrinsicInst(IntrinsicInst &II) {
+    assert(II.getIntrinsicID() == Intrinsic::noalias);
+    assert(II.getArgOperand(Intrinsic::NoAliasIdentifyPArg) == OldPtr);
+    LLVM_DEBUG(dbgs() << "    original: " << II << "\n");
+    if (II.getArgOperand(Intrinsic::NoAliasNoAliasDeclArg) == OldNoAliasDecl) {
+      assert(OldNoAliasDecl && NewNoAliasDecl &&
+             "If we get here, we must have an old and a new llvm.noalias.decl");
+      II.setArgOperand(Intrinsic::NoAliasNoAliasDeclArg, NewNoAliasDecl);
+    }
+    II.setArgOperand(
+        Intrinsic::NoAliasIdentifyPArg,
+        getNewAllocaSlicePtr(
+            IRB, II.getArgOperand(Intrinsic::NoAliasIdentifyPArg)->getType()));
+    if (NewAllocaBeginOffset > 0) {
+      Value *OldObjIdV = II.getArgOperand(Intrinsic::NoAliasIdentifyPObjIdArg);
+      auto NewObjId = ConstantInt::get(
+          OldObjIdV->getType(),
+          cast<ConstantInt>(OldObjIdV)->getZExtValue() + NewAllocaBeginOffset);
+      II.setArgOperand(Intrinsic::NoAliasIdentifyPObjIdArg, NewObjId);
+    }
+    LLVM_DEBUG(dbgs() << "          to: " << II << "\n");
+    deleteIfTriviallyDead(OldPtr);
+    return true;
+  }
+
+  bool visitNoAliasCopyGuardIntrinsicInst(IntrinsicInst &II) {
+    assert(II.getIntrinsicID() == Intrinsic::noalias_copy_guard);
+    return true;
+  }
+
+  bool visitLifetimeIntrinsicInst(IntrinsicInst &II) {
+    assert(II.isLifetimeStartOrEnd());
     LLVM_DEBUG(dbgs() << "    original: " << II << "\n");
 
     // Record this instruction for deletion.
     Pass.DeadInsts.push_back(&II);
 
     if (II.isDroppable()) {
       assert(II.getIntrinsicID() == Intrinsic::assume && "Expected assume");
       // TODO For now we forget assumed information, this can be improved.

       New = IRB.CreateLifetimeEnd(Ptr, Size);
 
     (void)New;
     LLVM_DEBUG(dbgs() << "          to: " << *New << "\n");
 
     return true;
   }
 
+  bool visitIntrinsicInst(IntrinsicInst &II) {
+    switch (II.getIntrinsicID()) {
+    case Intrinsic::lifetime_start:
+    case Intrinsic::lifetime_end:
+      return visitLifetimeIntrinsicInst(II);
+    case Intrinsic::noalias_decl:
+      return visitNoAliasDeclIntrinsicInst(II);
+    case Intrinsic::noalias:
+      return visitNoAliasIntrinsicInst(II);
+    case Intrinsic::provenance_noalias:
+      return visitProvenanceNoAliasIntrinsicInst(II);
+    case Intrinsic::noalias_copy_guard:
+      return visitNoAliasCopyGuardIntrinsicInst(II);
+    default:
+      assert(false && "SROA: SliceRewriter: unhandled intrinsic");
+      return false;
+    }
+  }
+
   void fixLoadStoreAlign(Instruction &Root) {
     // This algorithm implements the same visitor loop as
     // hasUnsafePHIOrSelectUse, and fixes the alignment of each load
     // or store found.
     SmallPtrSet<Instruction *, 4> Visited;
     SmallVector<Instruction *, 4> Uses;
     Visited.insert(&Root);
     Uses.push_back(&Root);

     // fully-rewritten alloca.
     SelectUsers.insert(&SI);
     return true;
   }
 };
 
 namespace {
 
+// Returns true if the indicices of the provided GEP are compatible with
+// the indices in the llvm.noalias.copy.guard.
+// - treatMissingIndicesAsZero: if the number of indices from the GEP
+// is smaller, treat the missing indices as zero
+// Note: A nullptr GEP can be combined with treatMissingIndicesAsZero=true
+static bool areGepIndicesCompatibleWithCopyGuard(
+    const DataLayout &DL, GetElementPtrInst *GEP,
+    llvm::Instruction *CopyGuardII, bool treatMissingIndicesAsZero = false) {
+  assert(CopyGuardII && "We need a llvm.noalias.copy.guard");
+
+  MDNode *CopyGuardIndices = cast<MDNode>(
+      cast<MetadataAsValue>(
+          CopyGuardII->getOperand(Intrinsic::NoAliasCopyGuardIndicesArg))
+          ->getMetadata());
+  APInt GEPOffset(DL.getPointerSizeInBits(), 0);
+  if (GEP) {
+    if (!GEP->accumulateConstantOffset(DL, GEPOffset))
+      return false;
+  } else if (!treatMissingIndicesAsZero)
+    return false;
+
+  // Either we could compute the offset, or we use 0
+  MatchOffset MO(GEPOffset.getZExtValue());
+  gatherValidNoAliasPointerOffsets(MO, CopyGuardIndices);
+  return MO.wasMatched();
+}
+
+static Type *GetZeroIndexLeafType(Type *TypeToLoad) {
+  while (true) {
+    if (StructType *ST = dyn_cast<StructType>(TypeToLoad)) {
+      TypeToLoad = ST->getElementType(0);
+      continue;
+    }
+    if (ArrayType *AT = dyn_cast<ArrayType>(TypeToLoad)) {
+      TypeToLoad = AT->getElementType();
+      continue;
+    }
+    if (VectorType *VT = dyn_cast<VectorType>(TypeToLoad)) {
+      TypeToLoad = VT->getElementType();
+      continue;
+    }
+    break;
+  }
+  assert(TypeToLoad->isPointerTy() && "Only pointers can have noalias info");
+
+  return TypeToLoad;
+}
+
+static void detachIfSingleUse(Value *What, Instruction *NACG) {
+  // Be on the safe side
+  Instruction *I = dyn_cast<Instruction>(What);
+  if (I && I->getNumUses() == 1 && I->getOperand(0) == NACG) {
+    I->setOperand(0, NACG->getOperand(0));
+  }
+}
+
+// Check if the load corresponds to a restrict pointer, as specified in the
+// CopyGuard information.
+// If so, add and return 'llvm.noalias' before the load. If the original load
+// needs to be replaced, due to bitcasts, it is returned through the 'Load'
+// argument.
+static llvm::Instruction *introduceNoAliasWhenCopyGuardIndicesAreCompatible(
+    llvm::LoadInst *Load, llvm::Instruction *CopyGuardII, const DataLayout &DL,
+    SmallVector<Use *, 2> *TrackSliceUses = nullptr) {
+  Value *PtrOp = Load->getPointerOperand();
+
+  if (TrackSliceUses)
+    TrackSliceUses->push_back(
+        &Load->getOperandUse(Load->getPointerOperandIndex()));
+
+  if (CopyGuardII == nullptr)
+    return Load;
+
+  // Possible cases:
+  // 1)  load ( gep ( CopyGuard) )
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(PtrOp)) {
+    if (areGepIndicesCompatibleWithCopyGuard(DL, GEP, CopyGuardII)) {
+      if (!Load->getType()->isPointerTy()) {
+        //@ FIXME:  Not a pointer type ? avoid introducing the noalias
+        // This is like the load of union (which is part of a struct).
+        // The correct solution for this should be to keep the
+        // llvm.noalias.copy.guard but this shift the offset with the gepoffset
+        // (But a negative shift is not yet supported in the NoAliasOffsets
+        // representation).
+        return Load;
+      }
+
+      IRBuilderTy IRB(Load->getNextNode());
+
+      detachIfSingleUse(GEP, CopyGuardII);
+
+      // A compatible set of indices was found - introduce a noalias intrinsic
+      // FIXME: what AAMetadata should we put on the llvm.noalias ?
+      auto NoAlias = IRB.CreateNoAliasPointer(
+          Load,
+          CopyGuardII->getOperand(Intrinsic::NoAliasCopyGuardNoAliasDeclArg),
+          GEP, CopyGuardII->getOperand(Intrinsic::NoAliasCopyGuardScopeArg),
+          Load->getName() + ".noalias");
+      // juggle around
+      Load->replaceAllUsesWith(NoAlias);
+      NoAlias->setOperand(0, Load);
+      LLVM_DEBUG(llvm::dbgs()
+                 << " - compatible, introduced:" << *NoAlias << "\n");
+
+      if (TrackSliceUses)
+        TrackSliceUses->push_back(
+            &NoAlias->getOperandUse(Intrinsic::NoAliasIdentifyPArg));
+
+      return NoAlias;
+    }
+
+    return Load;
+  }
+
+  if (BitCastInst *BCI = dyn_cast<BitCastInst>(PtrOp)) {
+    // We want to pass it as an integer type or pointer
+    if (!(Load->getType()->isIntegerTy() || Load->getType()->isPointerTy())) {
+      LLVM_DEBUG(llvm::dbgs()
+                 << " ** copy.guard: ignoring non integer or pointer:" << *Load
+                 << "\n");
+      return Load;
+    }
+
+    bool IsLoadOfInteger = Load->getType()->isIntegerTy();
+
+    // 2) load iXX (bitcast (gep (CopyGuard)))
+    //    load pXX (bitcast (gep (CopyGuard)))
+    // 3) load iXX (bitcast (CopyGuard))
+    //    load pXX (bitcast (CopyGuard))
+    Value *BCIOp = BCI->getOperand(0);
+    GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(BCI->getOperand(0));
+    if (GEP || (BCIOp == CopyGuardII)) {
+      Type *TypeToLoad = BCIOp->getType()->getPointerElementType();
+
+      // Also handles a null GEP
+      if (!areGepIndicesCompatibleWithCopyGuard(DL, GEP, CopyGuardII, true)) {
+        return Load;
+      }
+
+      TypeToLoad = GetZeroIndexLeafType(TypeToLoad);
+
+      // Sizes must be identical
+      if (DL.getTypeStoreSizeInBits(TypeToLoad) !=
+          DL.getTypeStoreSizeInBits(Load->getType())) {
+        LLVM_DEBUG(llvm::dbgs() << " ** copy.guard: type sizes do not match\n");
+        return Load;
+      }
+
+      IRBuilderTy IRB(Load->getNextNode());
+
+      if (GEP) {
+        detachIfSingleUse(GEP, CopyGuardII);
+      } else {
+        // Look through BCIop == CopyGuardII
+        BCIOp = CopyGuardII->getOperand(0);
+      }
+
+      LLVM_DEBUG(
+          llvm::dbgs()
+          << (GEP ? " - compatible bitcast(gep(copy.guard)), introduced:\n"
+                  : " - compatible bitcast(copy.guard), introduced:\n"));
+
+      LoadInst *NewLoad = Load;
+      Value *NewPtr = BCIOp;
+      if (IsLoadOfInteger) {
+        NewPtr = IRB.CreatePointerBitCastOrAddrSpaceCast(
+            BCIOp, TypeToLoad->getPointerTo());
+
+        if (NewPtr != BCIOp) {
+          LLVM_DEBUG(llvm::dbgs() << " -- " << *NewPtr << "\n");
+        }
+
+        NewLoad = IRB.CreateAlignedLoad(TypeToLoad, NewPtr, Load->getAlign(),
+                                        Load->getName() + ".sroa_as_ptr");
+        AAMDNodes AATags;
+        Load->getAAMetadata(AATags);
+        NewLoad->setAAMetadata(AATags);
+        LLVM_DEBUG(llvm::dbgs() << " -- " << *NewLoad << "\n");
+      }
+
+      // A compatible set of indices was found - introduce a noalias intrinsic
+      // FIXME: what AAMetadata should we put on the llvm.noalias ?
+      auto NoAlias = IRB.CreateNoAliasPointer(
+          NewLoad,
+          CopyGuardII->getOperand(Intrinsic::NoAliasCopyGuardNoAliasDeclArg),
+          NewPtr, CopyGuardII->getOperand(Intrinsic::NoAliasCopyGuardScopeArg),
+          NewLoad->getName() + ".noalias");
+
+      LLVM_DEBUG(llvm::dbgs() << " -- " << *NoAlias << "\n");
+      Value *RetVal;
+      if (IsLoadOfInteger) {
+        auto PtrCast = IRB.CreatePtrToInt(NoAlias, Load->getType(),
+                                          Load->getName() + ".sroa_as_int");
+
+        LLVM_DEBUG(llvm::dbgs() << " -- " << *PtrCast << "\n");
+
+        // juggle around
+        Load->replaceAllUsesWith(PtrCast);
+        Load->eraseFromParent();
+
+        RetVal = PtrCast;
+      } else {
+        Load->replaceAllUsesWith(NoAlias);
+
+        RetVal = NoAlias;
+      }
+
+      if (BCI->use_empty())
+        BCI->eraseFromParent();
+
+      if (TrackSliceUses) {
+        TrackSliceUses->back() =
+            &NewLoad->getOperandUse(NewLoad->getPointerOperandIndex());
+        TrackSliceUses->push_back(
+            &NoAlias->getOperandUse(Intrinsic::NoAliasIdentifyPArg));
+      }
+
+      return cast<Instruction>(RetVal);
+    }
+
+    LLVM_DEBUG(llvm::dbgs()
+               << " ** copy.guard: unhandled bitcast:" << BCI << "\n");
+    return Load;
+  }
+
+  LLVM_DEBUG(llvm::dbgs() << "copy.guard: unhandled:" << Load << "\n");
+  // unhandled other situation
+  return Load;
+}
+
 /// Visitor to rewrite aggregate loads and stores as scalar.
 ///
 /// This pass aggressively rewrites all aggregate loads and stores on
 /// a particular pointer (or any pointer derived from it which we can identify)
 /// with scalar loads and stores.
 class AggLoadStoreRewriter : public InstVisitor<AggLoadStoreRewriter, bool> {
   // Befriend the base class so it can delegate to private visit methods.
   friend class InstVisitor<AggLoadStoreRewriter, bool>;
+  typedef InstVisitor<AggLoadStoreRewriter, bool> Base;
 
   /// Queue of pointer uses to analyze and potentially rewrite.
   SmallVector<Use *, 8> Queue;
 
   /// Set to prevent us from cycling with phi nodes and loops.
   SmallPtrSet<User *, 8> Visited;
 
   /// The current pointer use being rewritten. This is used to dig up the used

       }
 
       llvm_unreachable("Only arrays and structs are aggregate loadable types");
     }
   };
 
   struct LoadOpSplitter : public OpSplitter<LoadOpSplitter> {
     AAMDNodes AATags;
+    Instruction *CopyGuardII = nullptr;
+    unsigned CGIIndex = 0;
 
     LoadOpSplitter(Instruction *InsertionPoint, Value *Ptr, Type *BaseTy,
-                   AAMDNodes AATags, Align BaseAlign, const DataLayout &DL)
+                   AAMDNodes AATags, Align BaseAlign, const DataLayout &DL,
+                   Instruction *CopyGuardII_)
         : OpSplitter<LoadOpSplitter>(InsertionPoint, Ptr, BaseTy, BaseAlign,
                                      DL),
-          AATags(AATags) {}
+          AATags(AATags), CopyGuardII(CopyGuardII_) {}
 
     /// Emit a leaf load of a single value. This is called at the leaves of the
     /// recursive emission to actually load values.
     void emitFunc(Type *Ty, Value *&Agg, Align Alignment, const Twine &Name) {
       assert(Ty->isSingleValueType());
       // Load the single value and insert it using the indices.
+      auto Ptr = this->Ptr; // Make sure _NOT_ to overwrite the Ptr member
+      if (CopyGuardII) {
+        assert(CopyGuardII == Ptr && "Ptr != CopyGuardII ???");
+        Ptr = CopyGuardII->getOperand(0); // look through noalias.copy.guard
+      }
       Value *GEP =
           IRB.CreateInBoundsGEP(BaseTy, Ptr, GEPIndices, Name + ".gep");
-      LoadInst *Load =
+      Instruction *PValue;
+      LoadInst *PLoad =
           IRB.CreateAlignedLoad(Ty, GEP, Alignment, Name + ".load");
 
       APInt Offset(
           DL.getIndexSizeInBits(Ptr->getType()->getPointerAddressSpace()), 0);
       if (AATags &&
           GEPOperator::accumulateConstantOffset(BaseTy, GEPIndices, DL, Offset))
-        Load->setAAMetadata(AATags.shift(Offset.getZExtValue()));
+        PLoad->setAAMetadata(AATags.shift(Offset.getZExtValue()));
+      PValue = introduceNoAliasWhenCopyGuardIndicesAreCompatible(
+          PLoad, CopyGuardII, DL);
 
-      Agg = IRB.CreateInsertValue(Agg, Load, Indices, Name + ".insert");
-      LLVM_DEBUG(dbgs() << "          to: " << *Load << "\n");
+      Agg = IRB.CreateInsertValue(Agg, PValue, Indices, Name + ".insert");
+      LLVM_DEBUG(dbgs() << "          to: " << *PValue << "\n");
     }
   };
 
   bool visitLoadInst(LoadInst &LI) {
-    assert(LI.getPointerOperand() == *U);
-    if (!LI.isSimple() || LI.getType()->isSingleValueType())
+    if (U->getOperandNo() == LI.getNoaliasProvenanceOperandIndex()) {
+      // Skip provenance
+      assert(LI.hasNoaliasProvenanceOperand() &&
+             LI.getNoaliasProvenanceOperand() == *U);
       return false;
+    }
+    assert(LI.getPointerOperand() == *U);
+    Instruction *CopyGuardII = getBaseAsCopyGuardOrNull(LI.getPointerOperand());
+    if (CopyGuardII) {
+      LLVM_DEBUG(llvm::dbgs() << " Replacing Load:" << LI
+                              << "\n"
+                                 " Depends on:"
+                              << *CopyGuardII << "\n");
+    }
+    if (!LI.isSimple() || LI.getType()->isSingleValueType()) {
+      LoadInst *PLI = &LI;
+      auto Load = introduceNoAliasWhenCopyGuardIndicesAreCompatible(
+          PLI, CopyGuardII, DL);
+      return (Load != PLI);
+    }
 
     // We have an aggregate being loaded, split it apart.
     LLVM_DEBUG(dbgs() << "    original: " << LI << "\n");
     AAMDNodes AATags;
     LI.getAAMetadata(AATags);
     LoadOpSplitter Splitter(&LI, *U, LI.getType(), AATags,
-                            getAdjustedAlignment(&LI, 0), DL);
+                            getAdjustedAlignment(&LI, 0), DL, CopyGuardII);
     Value *V = UndefValue::get(LI.getType());
     Splitter.emitSplitOps(LI.getType(), V, LI.getName() + ".fca");
     Visited.erase(&LI);
     LI.replaceAllUsesWith(V);
     LI.eraseFromParent();
     return true;
   }
 

     if (!SI.isSimple() || SI.getPointerOperand() != *U)
       return false;
     Value *V = SI.getValueOperand();
     if (V->getType()->isSingleValueType())
       return false;
 
     // We have an aggregate being stored, split it apart.
     LLVM_DEBUG(dbgs() << "    original: " << SI << "\n");
+
+    if (auto *LI = dyn_cast<LoadInst>(SI.getValueOperand())) {
+      // Try to split up the depending load, helpful for tracking noalias info
+      if (Visited.insert(LI).second) {
+        LLVM_DEBUG(llvm::dbgs()
+                   << "       - Forcing split of of StoreInst value operand\n");
+        Queue.push_back(&LI->getOperandUse(LI->getPointerOperandIndex()));
+      }
+    }
+
     AAMDNodes AATags;
     SI.getAAMetadata(AATags);
     StoreOpSplitter Splitter(&SI, *U, V->getType(), AATags,
                              getAdjustedAlignment(&SI, 0), DL);
     Splitter.emitSplitOps(V->getType(), V, V->getName() + ".fca");
     Visited.erase(&SI);
     SI.eraseFromParent();
     return true;
   }
 
   bool visitBitCastInst(BitCastInst &BC) {
     enqueueUsers(BC);
     return false;
   }
 
+  // Look through noalias intrinsics
+  bool visitIntrinsicInst(IntrinsicInst &II) {
+    if (II.getIntrinsicID() == Intrinsic::noalias) {
+      if (II.getOperand(0) == *U) {
+        enqueueUsers(II);
+      }
+      return false;
+    }
+    if (II.getIntrinsicID() == Intrinsic::provenance_noalias ||
+        II.getIntrinsicID() == Intrinsic::noalias_decl) {
+      return false;
+    }
+    if (II.getIntrinsicID() == Intrinsic::noalias_copy_guard) {
+      LLVM_DEBUG(llvm::dbgs()
+                 << "AggLoadStoreRewriter: handling llvm.noalias.copy.guard:"
+                 << (II.getOperand(0) == *U) << ":" << II << "\n");
+      if (II.getOperand(0) == *U)
+        enqueueUsers(II);
+      return false;
+    }
+
+    return Base::visitIntrinsicInst(II);
+  }
+
   bool visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) {
     enqueueUsers(ASC);
     return false;
   }
 
   // Fold gep (select cond, ptr1, ptr2) => select cond, gep(ptr1), gep(ptr2)
   bool foldGEPSelect(GetElementPtrInst &GEPI) {
     if (!GEPI.hasAllConstantIndices())

   // At this point, we have collected all of the loads and stores we can
   // pre-split, and the specific splits needed for them. We actually do the
   // splitting in a specific order in order to handle when one of the loads in
   // the value operand to one of the stores.
   //
   // First, we rewrite all of the split loads, and just accumulate each split
   // load in a parallel structure. We also build the slices for them and append
   // them to the alloca slices.
-  SmallDenseMap<LoadInst *, std::vector<LoadInst *>, 1> SplitLoadsMap;
-  std::vector<LoadInst *> SplitLoads;
+  SmallDenseMap<LoadInst *, std::vector<Instruction *>, 1> SplitLoadsMap;
+  std::vector<Instruction *> SplitLoads;
   const DataLayout &DL = AI.getModule()->getDataLayout();
   for (LoadInst *LI : Loads) {
     SplitLoads.clear();
 
     IntegerType *Ty = cast<IntegerType>(LI->getType());
     assert(Ty->getBitWidth() % 8 == 0);
     uint64_t LoadSize = Ty->getBitWidth() / 8;
     assert(LoadSize > 0 && "Cannot have a zero-sized integer load!");
 
     auto &Offsets = SplitOffsetsMap[LI];
     assert(LoadSize == Offsets.S->endOffset() - Offsets.S->beginOffset() &&
            "Slice size should always match load size exactly!");
     uint64_t BaseOffset = Offsets.S->beginOffset();
     assert(BaseOffset + LoadSize > BaseOffset &&
            "Cannot represent alloca access size using 64-bit integers!");
 
     Instruction *BasePtr = cast<Instruction>(LI->getPointerOperand());
     IRB.SetInsertPoint(LI);
 
+    Instruction *CopyGuardII = getBaseAsCopyGuardOrNull(BasePtr);
+
     LLVM_DEBUG(dbgs() << "  Splitting load: " << *LI << "\n");
 
     uint64_t PartOffset = 0, PartSize = Offsets.Splits.front();
     int Idx = 0, Size = Offsets.Splits.size();
     for (;;) {
       auto *PartTy = Type::getIntNTy(Ty->getContext(), PartSize * 8);
       auto AS = LI->getPointerAddressSpace();
       auto *PartPtrTy = PartTy->getPointerTo(AS);
       LoadInst *PLoad = IRB.CreateAlignedLoad(
           PartTy,
           getAdjustedPtr(IRB, DL, BasePtr,
                          APInt(DL.getIndexSizeInBits(AS), PartOffset),
                          PartPtrTy, BasePtr->getName() + "."),
           getAdjustedAlignment(LI, PartOffset),
           /*IsVolatile*/ false, LI->getName());
       PLoad->copyMetadata(*LI, {LLVMContext::MD_mem_parallel_loop_access,
                                 LLVMContext::MD_access_group});
 
+      SmallVector<Use *, 2> UsesToTrack;
+      auto *PValue = introduceNoAliasWhenCopyGuardIndicesAreCompatible(
+          PLoad, CopyGuardII, DL, &UsesToTrack);
+
       // Append this load onto the list of split loads so we can find it later
       // to rewrite the stores.
-      SplitLoads.push_back(PLoad);
+      SplitLoads.push_back(PValue);
 
       // Now build a new slice for the alloca.
-      NewSlices.push_back(
-          Slice(BaseOffset + PartOffset, BaseOffset + PartOffset + PartSize,
-                &PLoad->getOperandUse(PLoad->getPointerOperandIndex()),
+      for (Use *PUse : UsesToTrack) {
+        NewSlices.push_back(Slice(BaseOffset + PartOffset,
+                                  BaseOffset + PartOffset + PartSize, PUse,
                                   /*IsSplittable*/ false));
         LLVM_DEBUG(dbgs() << "    new slice [" << NewSlices.back().beginOffset()
                           << ", " << NewSlices.back().endOffset()
-                        << "): " << *PLoad << "\n");
+                          << "): " << *PUse->getUser() << "\n");
+      }
 
       // See if we've handled all the splits.
       if (Idx >= Size)
         break;
 
       // Setup the next partition.
       PartOffset = Offsets.Splits[Idx];
       ++Idx;

       }
 
       Value *StoreBasePtr = SI->getPointerOperand();
       IRB.SetInsertPoint(SI);
 
       LLVM_DEBUG(dbgs() << "    Splitting store of load: " << *SI << "\n");
 
       for (int Idx = 0, Size = SplitLoads.size(); Idx < Size; ++Idx) {
-        LoadInst *PLoad = SplitLoads[Idx];
+        auto *PLoad = SplitLoads[Idx];
         uint64_t PartOffset = Idx == 0 ? 0 : Offsets.Splits[Idx - 1];
         auto *PartPtrTy =
             PLoad->getType()->getPointerTo(SI->getPointerAddressSpace());
 
         auto AS = SI->getPointerAddressSpace();
         StoreInst *PStore = IRB.CreateAlignedStore(
             PLoad,
             getAdjustedPtr(IRB, DL, StoreBasePtr,

     auto &Offsets = SplitOffsetsMap[SI];
     assert(StoreSize == Offsets.S->endOffset() - Offsets.S->beginOffset() &&
            "Slice size should always match load size exactly!");
     uint64_t BaseOffset = Offsets.S->beginOffset();
     assert(BaseOffset + StoreSize > BaseOffset &&
            "Cannot represent alloca access size using 64-bit integers!");
 
     Value *LoadBasePtr = LI->getPointerOperand();
+    Instruction *CopyGuardII = getBaseAsCopyGuardOrNull(LoadBasePtr);
     Instruction *StoreBasePtr = cast<Instruction>(SI->getPointerOperand());
 
     LLVM_DEBUG(dbgs() << "  Splitting store: " << *SI << "\n");
 
     // Check whether we have an already split load.
     auto SplitLoadsMapI = SplitLoadsMap.find(LI);
-    std::vector<LoadInst *> *SplitLoads = nullptr;
+    std::vector<Instruction *> *SplitLoads = nullptr;
     if (SplitLoadsMapI != SplitLoadsMap.end()) {
       SplitLoads = &SplitLoadsMapI->second;
       assert(SplitLoads->size() == Offsets.Splits.size() + 1 &&
              "Too few split loads for the number of splits in the store!");
     } else {
       LLVM_DEBUG(dbgs() << "          of load: " << *LI << "\n");
     }
 
     uint64_t PartOffset = 0, PartSize = Offsets.Splits.front();
     int Idx = 0, Size = Offsets.Splits.size();
     for (;;) {
       auto *PartTy = Type::getIntNTy(Ty->getContext(), PartSize * 8);
       auto *LoadPartPtrTy = PartTy->getPointerTo(LI->getPointerAddressSpace());
       auto *StorePartPtrTy = PartTy->getPointerTo(SI->getPointerAddressSpace());
 
       // Either lookup a split load or create one.
-      LoadInst *PLoad;
+      Instruction *PLoad;
       if (SplitLoads) {
         PLoad = (*SplitLoads)[Idx];
       } else {
         IRB.SetInsertPoint(LI);
         auto AS = LI->getPointerAddressSpace();
-        PLoad = IRB.CreateAlignedLoad(
+        LoadInst *NewPLoad = IRB.CreateAlignedLoad(
             PartTy,
             getAdjustedPtr(IRB, DL, LoadBasePtr,
                            APInt(DL.getIndexSizeInBits(AS), PartOffset),
                            LoadPartPtrTy, LoadBasePtr->getName() + "."),
             getAdjustedAlignment(LI, PartOffset),
             /*IsVolatile*/ false, LI->getName());
-        PLoad->copyMetadata(*LI, {LLVMContext::MD_mem_parallel_loop_access,
+        NewPLoad->copyMetadata(*LI, {LLVMContext::MD_mem_parallel_loop_access,
                                   LLVMContext::MD_access_group});
+        PLoad = introduceNoAliasWhenCopyGuardIndicesAreCompatible(
+            NewPLoad, CopyGuardII, DL);
       }
 
       // And store this partition.
       IRB.SetInsertPoint(SI);
       auto AS = SI->getPointerAddressSpace();
       StoreInst *PStore = IRB.CreateAlignedStore(
           PLoad,
           getAdjustedPtr(IRB, DL, StoreBasePtr,

 /// promoted.
 AllocaInst *SROA::rewritePartition(AllocaInst &AI, AllocaSlices &AS,
                                    Partition &P) {
   // Try to compute a friendly type for this partition of the alloca. This
   // won't always succeed, in which case we fall back to a legal integer type
   // or an i8 array of an appropriate size.
   Type *SliceTy = nullptr;
   const DataLayout &DL = AI.getModule()->getDataLayout();
+  auto RepresentsNoAlias = (partitionRepresentsNoAliasPointer(P) != nullptr);
   std::pair<Type *, IntegerType *> CommonUseTy =
       findCommonType(P.begin(), P.end(), P.endOffset());
   // Do all uses operate on the same type?
   if (CommonUseTy.first)
     if (DL.getTypeAllocSize(CommonUseTy.first).getFixedSize() >= P.size())
       SliceTy = CommonUseTy.first;
   // If not, can we find an appropriate subtype in the original allocated type?
   if (!SliceTy)

 
   bool IsIntegerPromotable = isIntegerWideningViable(P, SliceTy, DL);
 
   VectorType *VecTy =
       IsIntegerPromotable ? nullptr : isVectorPromotionViable(P, DL);
   if (VecTy)
     SliceTy = VecTy;
 
+  if (RepresentsNoAlias && !SliceTy->isPointerTy()) {
+    if (DL.getTypeStoreSizeInBits(SliceTy) ==
+        DL.getTypeStoreSizeInBits(SliceTy->getPointerTo())) {
+      // a restrict pointer must be a pointer
+      SliceTy = SliceTy->getPointerTo();
+    }
+  }
+
   // Check for the case where we're going to rewrite to a new alloca of the
   // exact same type as the original, and with the same access offsets. In that
   // case, re-use the existing alloca, but still run through the rewriter to
   // perform phi and select speculation.
   // P.beginOffset() can be non-zero even with the same type in a case with
   // out-of-bounds access (e.g. @PR35657 function in SROA/basictest.ll).
   AllocaInst *NewAI;
   if (SliceTy == AI.getAllocatedType() && P.beginOffset() == 0) {

   // fact scheduled for promotion.
   unsigned PPWOldSize = PostPromotionWorklist.size();
   unsigned NumUses = 0;
   SmallSetVector<PHINode *, 8> PHIUsers;
   SmallSetVector<SelectInst *, 8> SelectUsers;
 
   AllocaSliceRewriter Rewriter(DL, AS, *this, AI, *NewAI, P.beginOffset(),
                                P.endOffset(), IsIntegerPromotable, VecTy,
-                               PHIUsers, SelectUsers);
+                               PHIUsers, SelectUsers, RepresentsNoAlias);
   bool Promotable = true;
   for (Slice *S : P.splitSliceTails()) {
     Promotable &= Rewriter.visit(S);
     ++NumUses;
   }
   for (Slice &S : P) {
     Promotable &= Rewriter.visit(&S);
     ++NumUses;

 
 /// Analyze an alloca for SROA.
 ///
 /// This analyzes the alloca to ensure we can reason about it, builds
 /// the slices of the alloca, and then hands it off to be split and
 /// rewritten as needed.
 bool SROA::runOnAlloca(AllocaInst &AI) {
   LLVM_DEBUG(dbgs() << "SROA alloca: " << AI << "\n");
+  LLVM_DEBUG(AI.getParent()->getParent()->dump());
   ++NumAllocasAnalyzed;
 
   // Special case dead allocas, as they're trivial.
   if (AI.use_empty()) {
     AI.eraseFromParent();
     return true;
   }
   const DataLayout &DL = AI.getModule()->getDataLayout();

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

 #include "llvm/IR/Module.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
+#include "llvm/Transforms/Utils/NoAliasUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-rotate"
 
 STATISTIC(NumNotRotatedDueToHeaderSize,
           "Number of loops not rotated due to the header size");

     for (auto I = std::next(OrigPreheader->rbegin()), E = OrigPreheader->rend();
          I != E; ++I) {
       if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&*I))
         DbgIntrinsics.insert(makeHash(DII));
       else
         break;
     }
 
-    // Remember the local noalias scope declarations in the header. After the
-    // rotation, they must be duplicated and the scope must be cloned. This
-    // avoids unwanted interaction across iterations.
-    SmallVector<NoAliasScopeDeclInst *, 6> NoAliasDeclInstructions;
-    for (Instruction &I : *OrigHeader)
-      if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I))
-        NoAliasDeclInstructions.push_back(Decl);
+    // check if there are local restrict declarations and how they are used.
+    // - avoid breaking up mixed usage:
+    // -- either all usages must be in the OrigHeader, or no usages must be in
+    //    the OrigHeader.
+    // -- when usages are outside the function, and we decide to continue, break
+    //    the connection with the llvm.noalias.decl, as it will have no impact
+    //    any more.
+    SmallVector<NoAliasScopeDeclInst *, 6> NoAliasScopeDeclInstructions;
+    SmallVector<Instruction *, 6> NoAliasDeclInstructions;
+    {
+      SmallVector<Instruction *, 6> ProvenanceNoAliasOrNoAliasToDisconnect;
+      for (Instruction &I : *OrigHeader) {
+        if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I)) {
+          NoAliasScopeDeclInstructions.push_back(Decl);
+        } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I)) {
+          if (II->getIntrinsicID() == Intrinsic::noalias_decl) {
+            // Check usage validity:
+            bool UsedInsideHeader = false;
+            bool UsedOutsideHeaderInsideLoop = false;
+            for (User *U : II->users()) {
+              Instruction *UI = cast<Instruction>(U);
+              if (UI->getParent() == OrigHeader) {
+                UsedInsideHeader = true;
+              } else if (L->contains(UI)) {
+                UsedOutsideHeaderInsideLoop = true;
+              } else {
+                if (PHINode *PUI = dyn_cast<PHINode>(UI)) {
+                  if (PUI->getNumIncomingValues() > 1) {
+                    LLVM_DEBUG(
+                        llvm::dbgs()
+                        << "LoopRotation: NOT rotating - " << *II
+                        << "\n    used in PHI node " << *PUI
+                        << ",\n   in exit block with multiple entries.\n");
+                    return false;
+                  }
+                }
+                ProvenanceNoAliasOrNoAliasToDisconnect.push_back(UI);
+              }
+            }
+
+            if (UsedInsideHeader && UsedOutsideHeaderInsideLoop) {
+              LLVM_DEBUG(llvm::dbgs()
+                         << "LoopRotation: NOT rotating - " << *II
+                         << " used in header and other parts of the loop.\n"
+                            "  Rotation would reduced the llvm.noalias quality "
+                            "too much.\n");
+              return false;
+            }
+
+            NoAliasDeclInstructions.push_back(II);
+          }
+        }
+      }
+
+      // If we get here, we will do the rotate.
+      // First break the link between any llvm.noalias.decl and its outside-loop
+      // usage
+      for (Instruction *I : ProvenanceNoAliasOrNoAliasToDisconnect) {
+        unsigned OpN;
+        if (PHINode *PI = dyn_cast<PHINode>(I)) {
+          // can only happen when in the exit block -> single predecessor !
+          assert(PI->getNumIncomingValues() == 1 &&
+                 "PHI node should have a single value");
+          (void)PI; // Silence not-used warning in Release builds
+          OpN = 0;
+        } else {
+          IntrinsicInst *II = cast<IntrinsicInst>(I);
+          if (II->getIntrinsicID() == Intrinsic::provenance_noalias) {
+            OpN = Intrinsic::ProvenanceNoAliasNoAliasDeclArg;
+          } else if (II->getIntrinsicID() == Intrinsic::noalias) {
+            OpN = Intrinsic::NoAliasNoAliasDeclArg;
+          } else {
+            assert(II->getIntrinsicID() == Intrinsic::noalias_copy_guard);
+            OpN = Intrinsic::NoAliasCopyGuardNoAliasDeclArg;
+          }
+        }
+
+        auto *PT = cast<PointerType>(I->getOperand(OpN)->getType());
+        I->setOperand(OpN, ConstantPointerNull::get(PT));
+      }
+    }
 
     while (I != E) {
       Instruction *Inst = &*I++;
 
       // If the instruction's operands are invariant and it doesn't read or write
       // memory, then it is safe to hoist.  Doing this doesn't change the order of
       // execution in the preheader, but does prevent the instruction from
       // executing in each iteration of the loop.  This means it is safe to hoist
       // something that might trap, but isn't safe to hoist something that reads
       // memory (without proving that the loop doesn't write).
       if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&

           AC->registerAssumption(II);
         // MemorySSA cares whether the cloned instruction was inserted or not, and
         // not whether it can be remapped to a simplified value.
         if (MSSAU)
           InsertNewValueIntoMap(ValueMapMSSA, Inst, C);
       }
     }
 
-    if (!NoAliasDeclInstructions.empty()) {
+    if (!NoAliasDeclInstructions.empty() ||
+        !NoAliasScopeDeclInstructions.empty()) {
+
       // There are noalias scope declarations:
       // (general):
       // Original:    OrigPre              { OrigHeader NewHeader ... Latch }
       // after:      (OrigPre+OrigHeader') { NewHeader ... Latch OrigHeader }
       //
       // with D: llvm.experimental.noalias.scope.decl,
       //      U: !noalias or !alias.scope depending on D
+      // or with D: llvm.noalias.decl,
+      //         U: llvm.provenance.noalias depending on D
       //       ... { D U1 U2 }   can transform into:
       // (0) : ... { D U1 U2 }        // no relevant rotation for this part
       // (1) : ... D' { U1 U2 D }     // D is part of OrigHeader
       // (2) : ... D' U1' { U2 D U1 } // D, U1 are part of OrigHeader
       //
       // We now want to transform:
       // (1) -> : ... D' { D U1 U2 D'' }
       // (2) -> : ... D' U1' { D U2 D'' U1'' }
-      // D: original llvm.experimental.noalias.scope.decl
+      // D: original llvm.experimental.noalias.scope.decl/llvm.noalias.decl
       // D', U1': duplicate with replaced scopes
       // D'', U1'': different duplicate with replaced scopes
       // This ensures a safe fallback to 'may_alias' introduced by the rotate,
       // as U1'' and U1' scopes will not be compatible wrt to the local restrict
 
-      // Clone the llvm.experimental.noalias.decl again for the NewHeader.
+      // Clone the llvm.experimental.noalias.decl/llvm.noalias.decl again for
+      // the NewHeader.
+
       Instruction *NewHeaderInsertionPoint = &(*NewHeader->getFirstNonPHI());
-      for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions) {
+      for (NoAliasScopeDeclInst *NAD : NoAliasScopeDeclInstructions) {
         LLVM_DEBUG(dbgs() << "  Cloning llvm.experimental.noalias.scope.decl:"
                           << *NAD << "\n");
         Instruction *NewNAD = NAD->clone();
         NewNAD->insertBefore(NewHeaderInsertionPoint);
       }
+      for (Instruction *NAD : NoAliasDeclInstructions) {
+        LLVM_DEBUG(llvm::dbgs()
+                   << "  Cloning llvm.noalias.decl:" << *NAD << "\n");
+        Instruction *NewNAD = NAD->clone();
+        //@ FIXME: NewNAD->insertBefore(NewHeaderInsertionPoint);
+        NewNAD->insertBefore(NAD);
+
+        // remap dependencies in the OrigHeader block to NewNAD
+        NAD->replaceUsesInsideBlock(NewNAD, OrigHeader);
+
+        // And move the original NAD to the NewHeader
+        NAD->moveBefore(NewHeaderInsertionPoint);
+
+        // Now forget about the original NAD mapping
+        auto tmp =
+            ValueMap[NAD];      // use a local copy to avoid undefined behavior
+        ValueMap[NewNAD] = tmp; // this could trigger a reallocation.
+        ValueMap.erase(NAD);
+      }
 
       // Scopes must now be duplicated, once for OrigHeader and once for
       // OrigPreHeader'.
       {
         auto &Context = NewHeader->getContext();
 
         SmallVector<MDNode *, 8> NoAliasDeclScopes;
-        for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions)
+        for (auto *NAD : NoAliasScopeDeclInstructions)
           NoAliasDeclScopes.push_back(NAD->getScopeList());
+        for (auto *NAD : NoAliasDeclInstructions)
+          NoAliasDeclScopes.push_back(
+              cast<MDNode>(cast<MetadataAsValue>(
+                               NAD->getOperand(Intrinsic::NoAliasDeclScopeArg))
+                               ->getMetadata()));
 
         LLVM_DEBUG(dbgs() << "  Updating OrigHeader scopes\n");
         cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, {OrigHeader}, Context,
                                    "h.rot");
         LLVM_DEBUG(OrigHeader->dump());
 
+        // FIXME: originally we were updating only a part of the OrigPreHeader
+        // FIXME: for now, for easyness, we update the complete OrigPreHeader.
+        // FIXME: the comment below is not true any more !
         // Keep the compile time impact low by only adapting the inserted block
         // of instructions in the OrigPreHeader. This might result in slightly
         // more aliasing between these instructions and those that were already
         // present, but it will be much faster when the original PreHeader is
         // large.
-        LLVM_DEBUG(dbgs() << "  Updating part of OrigPreheader scopes\n");
-        auto *FirstDecl =
-            cast<Instruction>(ValueMap[*NoAliasDeclInstructions.begin()]);
-        auto *LastInst = &OrigPreheader->back();
-        cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, FirstDecl, LastInst,
-                                   Context, "pre.rot");
+        LLVM_DEBUG(dbgs() << "  Updating OrigPreheader scopes\n");
+        cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, {OrigPreheader}, Context,
+                                   "pre.rot");
         LLVM_DEBUG(OrigPreheader->dump());
 
         LLVM_DEBUG(dbgs() << "  Updated NewHeader:\n");
         LLVM_DEBUG(NewHeader->dump());
       }
     }
 
     // Along with all the other instructions, we just cloned OrigHeader's