[LAA] Analyze pointers forked by a select

[huntergr]

Summary

Given a function like the following:

void forked_ptrs_different_base_same_offset(float *Base1, float *Base2, float *Dest, int *Preds) {
  for (int i=0; i<100; i++) {
    if (Pred[i] != 0) {
      Dest[i] = Base1[i];
    } else {
      Dest[i] = Base2[i];
    }
  }
}

LLVM will optimize the IR to a single load using a pointer determined by a select instruction:

%spec.select = select i1 %cmp1.not, float* %Base2, float* %Base1
%.sink.in = getelementptr inbounds float, float* %spec.select, i64 %indvars.iv 
%.sink = load float, float* %.sink.in, align 4

LAA is currently unable to analyze such IR, since ScalarEvolution will return a SCEVUnknown for the pointer operand for the load.

This patch adds initial optional support for analyzing both possibilities for the pointer and allowing LAA to generate runtime checks for the bounds if required.

[huntergr]

Rebased, ran clang-format over the patch.

[david-arm]

Hi @huntergr, apologies for delay reviewing this patch! I've not finished reviewing it, but I've left some comments that I have so far. Thanks!

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

363

If we're only ever going to support two forks couldn't we make this simpler by just having:

unsigned Members[2];

instead or is this a real pain to implement? Or is the idea that we may want to extend the fork to allow more than 2 in future?

388

Again, does this need to be a SmallVector and can it just be const SCEV *Starts[2];?

llvm/include/llvm/Analysis/ScalarEvolution.h

444 ↗

(On Diff #370905)

Hi Graham, it feels slightly awkward having to essentially redefine a ForkedPointer as a pair in the same way as ForkedPtrs in llvm/include/llvm/Analysis/LoopAccessAnalysis.h. Maybe we could define something like:

using ForkedPointer = std::pair<const SCEV *, const SCEV *>;

in llvm/include/llvm/Analysis/ScalarEvolution.h that can be used in LoopAccessAnalysis too?

llvm/lib/Analysis/LoopAccessAnalysis.cpp

346

nit: Perhaps you can just write assert(Fork <= 1 && ...) since it's unsigned anyway?

469

nit: Perhaps you can just write assert(Fork <= 1 && ...) since it's unsigned anyway?

620

Have you rewritten the logic here as a performance improvement, i.e. to avoid calling Group.addPointer() after it's already been merged?

865

nit: This is just a suggestion, but you could restructure this a little to remove the extra indentation I think here:

if (!AR) {
  if (!RtCheck.AllowForkedPtrs)
    return false;
  ...

Not sure if this is better?

881

Is it better to just make a recursive call to hasComputableBounds instead of calling isAffine here? We're potentially missing out on future improvements to hasComputableBounds here, and also we're ignoring the possibility of a forked pointer being loop invariant I think.

llvm/test/Transforms/LoopVectorize/forked-pointers.ll

1

Can we also have a test where at least one of the forked pointers is loop-invariant?

[huntergr]

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

363

So this is for a RuntimeCheckingPtrGroup, which may have more than two members already; I've only changed it from a SmallVector to a SmallSetVector here in order to avoid duplicate members, since both sides of a forked pointer can be added to the same group.

388

I'll look into it, but it'll make other parts messier since I can't just iterate over the members of the SmallVectors and would need to perform null checks for all those places for the second element.

One solution I thought of (but didn't implement, since I wanted some community feedback on the overall work first) was to create a new SCEVForkedExpr so that we wouldn't need to store two SCEVs here and could just note which fork(s) was represented. It'll take a while to implement that, but might be cleaner. Thoughts?

llvm/lib/Analysis/LoopAccessAnalysis.cpp

620

Not intentionally, no -- I just replicated the behaviour of the original (break out of the loop if the pointer merged into a group) but considered both potential forks.

llvm/test/Transforms/LoopVectorize/forked-pointers.ll

1

We already do; see forked_ptrs_uniform_and_contiguous_forks

We could properly analyze and vectorize that case as well, but I haven't implemented that yet so I'm just testing that it gets rejected for now.

[david-arm]

llvm/test/Transforms/LoopVectorize/forked-pointers.ll

1

Ah ok, sorry I missed that. I guess what I meant was that this should be trivial to implement, particularly if we can find a way of making calls to hasComputableBounds recursive and re-use the existing code that checks for loop-invariants and affine pointers.

[huntergr]

Rebased, updated based on review comments.

[huntergr]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

865

We still needed to bail out if AR was false and forked pointers weren't allowed... so I rewrote it to check for the positive case for AR first and then proceed with the forked pointers check and default false afterwards.

881

We can't do that right now -- hasComputableBounds takes a Value* rather than a SCEV* so it can (potentially) be added to the stride map in replaceSymbolicStrideSCEV. We'd just end up looking at the same Value and splitting again.

This is something the SCEVForkedExpr would make cleaner, since we would only need to evaluate a single SCEV. But it'll take a bit of refactoring to do that, which is why I wanted some feedback on the whole idea first.

We could also separate out parts of these functions to make it recursive, but I'll need to be careful since replaceSymbolicStrideSCEV has other users.

llvm/test/Transforms/LoopVectorize/forked-pointers.ll

1

Sadly, it'll require a bit more work to support invariant addresses. My original downstream code allowed them, but we ran into a bug with it and disabled them.

My plan is to get the base functionality committed, then go back and add an interface so that LoopVectorize (or other LAA consumers) can query the type of the forks in order to generate correct (and hopefully more optimal) IR for various cases -- the current contiguous-only SCEVs, strides of >1, loop-invariant but unknown strides, uniform/invariant addresses, indexed gather/scatter, etc.

If both forks have a stride of 1, or are invariant, then we could potentially plant two masked load instructions (or load + broadcast) instead of a gather, for instance. But that's future work until this part is completed.

[huntergr]

Ping.

[david-arm]

Thanks for making the changes @huntergr! I've got a few mostly minor comments so far, but still have to review findForkedSCEVs. :)

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

411

Hi @huntergr, thanks for making the changes to Exprs. I just wonder if we should have an assert here that ScExprs.size() <= 2?

llvm/lib/Analysis/LoopAccessAnalysis.cpp

554

nit: Is it worth calling CheckingGroups.emplace_back(I, *this, /*Fork=0*/0) for clarity here?

877

nit: This is just a minor comment, but you could remove indentation further here by bailing out early, i.e.

if (!FPtr)
  return false;

const SCEV *A =

881

nit: Instead of writing:

LLVM_DEBUG(dbgs() << "LAA: SCEV1: " << *(FPtr->first) << "\n");

I think you can just write

LLVM_DEBUG(dbgs() << "LAA: SCEV1: " << *A << "\n");

and same for the second one.

[david-arm]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

883

Is there any danger in setting this before we return true?

930

You're introducing a new implicit TypeSize -> uint64_t cast here. Could you rewrite this as:

int64_t Size = DL.getTypeAllocSize(PtrTy->getElementType()).getFixedSize();

[huntergr]

Rebased, minor fixes from review comments.

[david-arm]

Thanks for dealing with all the review comments @huntergr! I think the patch looks sensible to me, although I'm not as familiar with the SCEV code as others might be. I'm adding @lebedev.ri as a potential reviewer if that's ok?

llvm/test/Transforms/LoopVectorize/forked-pointers.ll

33

It would be good to show some distinction here between Check 1 and Check 2. I assume it's actually checking each of the forked pointers, but the output doesn't make that clear.

[huntergr]

Rebased, and changed the membership of a checking group to be a pair of PointerInfo index and fork so that printing can show which forks are present in a group.

[huntergr]

Rebased, disabled by default, added a couple of different instructions into the tests to ensure those paths are at least covered even if they aren't in a positive case right now; I'm still planning to leave those cases (known strides, g/s, uniform) for a followup patch; I suppose I could start a patch series if people want to see those earlier.

I've run the LNT nightly suite with this enabled, along with a few HPC benchmarks I have access to and they all pass.

[david-arm]

LGTM! Thanks for making all the changes @huntergr and adding the tests. This patch is low risk at the moment with the flag being disabled currently. At some point once there have been performance investigations to prove there are no regressions we can then enable this by default.

[fhahn]

In D108699#3148674, @david-arm wrote:

LGTM! Thanks for making all the changes @huntergr and adding the tests. This patch is low risk at the moment with the flag being disabled currently. At some point once there have been performance investigations to prove there are no regressions we can then enable this by default.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

19

Is this needed? Other SCEV types are forward-declared below, so ScalarEvolution.h doesn't need to be included.

332

Could we use a bool for Fork if it only has 2 possible values?

llvm/include/llvm/Analysis/ScalarEvolution.h

769 ↗

(On Diff #388889)

This is only used by LAA. Is there a reason this needs to be part of ScalarEvolution?

llvm/test/Transforms/LoopVectorize/forked-pointers.ll

1

the tests running -loop-accesses should be in llvm/test/Analysis/LoopAccessAnalysis.

Also, could you pre-commit the tests and update the diff here to show only the difference? That way it is a bit easier to see the impact in the diff.

[fhahn]

I just realized how this may be a bit similar to how we handle pointers that are phi nodes. Currently those are handled by adding accesses for both incoming values (see D109381). Unfortunately the same approach cannot be directly used for selects, because we need to create 2 pointers that do not exist in the IR.

But if MemAccessInfo/ would also carry the pointer SCEV directly, I think it would be possible to avoid adding another dimension to RuntimePointerChecking::PointerInfo. Instead we would add 2 PointerInfo entries with separate translated pointer SCEVs. I put up a rough sketch of what this may look like in D114480, D114479 to see how this may look like

[fhahn]

In D108699#3150041, @fhahn wrote:

I just realized how this may be a bit similar to how we handle pointers that are phi nodes. Currently those are handled by adding accesses for both incoming values (see D109381). Unfortunately the same approach cannot be directly used for selects, because we need to create 2 pointers that do not exist in the IR.

But if MemAccessInfo/ would also carry the pointer SCEV directly, I think it would be possible to avoid adding another dimension to RuntimePointerChecking::PointerInfo. Instead we would add 2 PointerInfo entries with separate translated pointer SCEVs. I put up a rough sketch of what this may look like in D114480, D114479 to see how this may look like

I also put up a sketch of a stripped down variant that only supports runtime check generation by adding multiple PointerInfos with different associated pointer SCEVs: D114487.

The variant that also extends MemAccessInfo should also be able to determine that certain loops are safe without runtime checks, e.g. like the one below I think:

%s1 = type { [32000 x float], [32000 x float], [32000 x float] }
define dso_local void @foo(%s1 * nocapture readonly %Base, i32* nocapture readonly %Preds) {
entry:
  br label %for.body

for.cond.cleanup:
  ret void

for.body:
  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
  %arrayidx = getelementptr inbounds i32, i32* %Preds, i64 %indvars.iv
  %0 = load i32, i32* %arrayidx, align 4
  %cmp1.not = icmp eq i32 %0, 0
  %gep.1 = getelementptr inbounds %s1, %s1* %Base, i64 0, i32 1, i32 0
  %gep.2 = getelementptr inbounds %s1, %s1* %Base, i64 0, i32 2, i32 0
  %spec.select = select i1 %cmp1.not, float* %gep.1, float* %gep.2
  %.sink.in = getelementptr inbounds float, float* %spec.select, i64 %indvars.iv
  %.sink = load float, float* %.sink.in, align 4
  %1= getelementptr inbounds %s1, %s1 * %Base, i64 0, i32 0, i64 %indvars.iv
  store float %.sink, float* %1, align 4
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, 100
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

[huntergr]

Revised based on @fhahn 's initial suggestions, rebased.

I'll look into the MemAccessInfo approach.

[huntergr]

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

19

It was there to include the 'using ForkedPointer =' definition, but moving it out of ScalarEvolution means we can just define it here.

I had hoped that we could maybe integrate it further into ScalarEvolution as a new type of SCEV, but maybe this isn't the right time -- you're correct, this will be the only user for now, so we can just keep it here until we find a case where it would be useful to have it more widely available.

[david-arm]

LGTM!

Hi @huntergr, thanks for making all the changes. I think the patch looks good to
go for now. It's still worth looking into the MemAccessInfo approach as a follow-up,
but the patch has been sat in review for long enough (3 months) without any
fundamental objections so I'd prefer we got something merged now to get the
functionality defended and unblock future work. This is currently only enabled
under an option, so any refactoring for the MemAccessInfo approach can be
done safely under another patch.

[fhahn]

In D108699#3158014, @david-arm wrote:

LGTM!

Hi @huntergr, thanks for making all the changes. I think the patch looks good to
go for now. It's still worth looking into the MemAccessInfo approach as a follow-up,
but the patch has been sat in review for long enough (3 months) without any
fundamental objections so I'd prefer we got something merged now to get the
functionality defended and unblock future work.

I agree it is not ideal that there's been not much feedback so far, but now that there is some additional feedback/suggestion, I think it would be good to hear additional opinions on the preferred direction here or at least discuss concrete potential alternatives; D114487 in particular which should have similar effects, but with less invasive changes, i.e. there's no need to adjust isNoWrap, hasComputableBounds, RuntimePointerChecking::insert or add additional state.

You mention future work blocked by this as a reason for landing this now, however I cannot find any references to patches depending on this work.

This is currently only enabled
under an option, so any refactoring for the MemAccessInfo approach can be
done safely under another patch.

While it is true that it is off by default, it adds substantial complexity to LAA which is already quite complex and the changes are quite spread out. One concern is that it adds an additional way to model 'forked pointers'; we already handle 'forked pointers' via phi nodes (by adding multiple PointerInfos). I am also not sure it should be off by default, once it lands. IMO better analysis should be the right thing to do and should be quite safe from a performance regression perspective. I don't see a strong reason for not enabling this by default and having wide testing surface potential issues early.

[huntergr]

Rebased and changed to use @fhahn 's lighter-weight approach from D114487 combined with my recursive function to find the SCEVs. Although the simplified tests are handled with a couple levels of checking, the real applications I was working on had additional operations between the ptr value for the load or store and a select.

It might be best to introduce a limit to recursion though, any thoughts?

[huntergr]

Rebased, added a recursion limit to the SCEV building function.

[huntergr]

Rebased. Ping?

[fhahn]

Thanks for the update!

I think it would be good to split this up to have a first patch that just adds very limited support in findForkedSCEVs and then gradually add support for more cases separately. This also makes it easier to make sure all code paths in findForkedSCEVs are covered by the unit tests.

I went ahead and rebased D114487 and stripped the fork analysis to the bare minimum. I'd be happy to land the scaffolding in D114487 separately and this patch and following could add the sophisticated fork analysis.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

133

It would be good to add a test for the option, e.g. a case that requires 2 or 3 recursions and set test with max-forked-scev-depth=2/3

568

This scheme would need documenting, i.e. why we can have multiple expressions for a pointer.

573

should be removed?

855

should be removed?

1023

Needs resolving.

It should be needed, because the above code may have added assumptions, which make Ptr an AddRec, See comment in D114487.

1037

missing test for this?

1055

It looks like tests for those conditions are missing?

1068

I don't think we can use the inbounds info here, unless we prove that the program is undefined if GEP is poison.

Consider something like below. If %c is always false, the GEP index could be out-of-bounds (and the GEP poison). Adding a runtime check based on the SCEV expression may introduce a branch on poison unconditionally.

define dso_local void @forked_ptrs_different_base_same_offset(float* nocapture readonly %Base1, float* nocapture readonly %Base2, float* nocapture %Dest, i32* nocapture readonly %Preds, i1 %c) {
entry:
  br label %for.body

for.cond.cleanup:
  ret void

for.body:
  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %latch ]
  %arrayidx = getelementptr inbounds i32, i32* %Preds, i64 %indvars.iv
  %0 = load i32, i32* %arrayidx, align 4
  %cmp1.not = icmp eq i32 %0, 0
  %spec.select = select i1 %cmp1.not, float* %Base2, float* %Base1
  %.sink.in = getelementptr inbounds float, float* %spec.select, i64 %indvars.iv
  %.sink = load float, float* %.sink.in, align 4
  %1 = getelementptr inbounds float, float* %Dest, i64 %indvars.iv
  br i1 %c, label %then, label %latch

then:
  store float %.sink, float* %1, align 4
  br label %latch

latch:
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, 100
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

1075

It might be a bit simpler to just add a duplicate to BaseScevs/OffsetScevs and have one common code path to compute the SCEVs to add

[huntergr]

In D108699#3441724, @fhahn wrote:

Thanks for the update!

I think it would be good to split this up to have a first patch that just adds very limited support in findForkedSCEVs and then gradually add support for more cases separately. This also makes it easier to make sure all code paths in findForkedSCEVs are covered by the unit tests.

I went ahead and rebased D114487 and stripped the fork analysis to the bare minimum. I'd be happy to land the scaffolding in D114487 separately and this patch and following could add the sophisticated fork analysis.

Sure, that sounds like a good plan. I'll try and review your patch this week.

[fhahn]

In D108699#3445309, @huntergr wrote:

In D108699#3441724, @fhahn wrote:

Thanks for the update!

I think it would be good to split this up to have a first patch that just adds very limited support in findForkedSCEVs and then gradually add support for more cases separately. This also makes it easier to make sure all code paths in findForkedSCEVs are covered by the unit tests.

I went ahead and rebased D114487 and stripped the fork analysis to the bare minimum. I'd be happy to land the scaffolding in D114487 separately and this patch and following could add the sophisticated fork analysis.

Sure, that sounds like a good plan. I'll try and review your patch this week.

Sounds great, thanks!

[huntergr]

Rebased on top of Florian's patch from https://reviews.llvm.org/D114487

That patch has been reverted for now so builds will fail, but this should be pretty close to what we want once the base feature is back in.

I've cut the walker function down to only handle GEPs and selects for now; we can add more cases (and more tests) later.

I've added tests to exercise the checks that exclude a given select or GEP from processing, as well as one for the recursion limit.

I'll precommit the new tests before the next update on this patch.

[fhahn]

In D108699#3591443, @huntergr wrote:

Rebased on top of Florian's patch from https://reviews.llvm.org/D114487

That patch has been reverted for now so builds will fail, but this should be pretty close to what we want once the base feature is back in.

Thanks, the patch has been relanded a while ago.

I've cut the walker function down to only handle GEPs and selects for now; we can add more cases (and more tests) later.

I've added tests to exercise the checks that exclude a given select or GEP from processing, as well as one for the recursion limit.

I'll precommit the new tests before the next update on this patch.

Sounds good! I skimmed the current version and it looks like most comments should be addressed in the latest update. It might be good to mark them as done. One thing I couldn't spot in the latest version is a test for the potential inbounds issue mentioned inline.

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

0–2

It would be probably be good to convert the IR to use opaque pointers in a pre-commit, so -opaque-pointers is not needed.

[huntergr]

Rebased on top of @fhahn 's fixed patch, including changes to detect possible undef/poison.

New tests were precommitted in rGa19cf47da095.

[huntergr]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1068

I removed the code to add no-wrap flags to the SCEV based on 'inbounds', then added your test.

[fhahn]

LGTM, thanks!

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1117

nit: unnecessary move?

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

74

nit: it would probably be good to also have a few tests that access different sizes, including odd ones like i23 or something like that, to ensure the right size expressions are used.

[ro]

This patch broke the Solaris/amd64 and Solaris/sparcv9 builds:

/vol/llvm/src/llvm-project/dist/llvm/lib/Analysis/LoopAccessAnalysis.cpp: In function ‘llvm::SmallVector<std::pair<const llvm::SCEV*, bool> > findForkedPointer(llvm::PredicatedScalarEvolution&, const ValueToValueMap&, llvm::Value*, const llvm::Loop*)’:
/vol/llvm/src/llvm-project/dist/llvm/lib/Analysis/LoopAccessAnalysis.cpp:916:12: error: could not convert ‘Scevs’ from ‘SmallVector<[...],2>’ to ‘SmallVector<[...],3>’
  916 |     return Scevs;
      |            ^~~~~
      |            |
      |            SmallVector<[...],2>

[huntergr]

In D108699#3659633, @ro wrote:

This patch broke the Solaris/amd64 and Solaris/sparcv9 builds:

/vol/llvm/src/llvm-project/dist/llvm/lib/Analysis/LoopAccessAnalysis.cpp: In function ‘llvm::SmallVector<std::pair<const llvm::SCEV*, bool> > findForkedPointer(llvm::PredicatedScalarEvolution&, const ValueToValueMap&, llvm::Value*, const llvm::Loop*)’:
/vol/llvm/src/llvm-project/dist/llvm/lib/Analysis/LoopAccessAnalysis.cpp:916:12: error: could not convert ‘Scevs’ from ‘SmallVector<[...],2>’ to ‘SmallVector<[...],3>’
  916 |     return Scevs;
      |            ^~~~~
      |            |
      |            SmallVector<[...],2>

Does rG4bd072c56b87 fix this for you?

[ro]

In D108699#3659641, @huntergr wrote:

In D108699#3659633, @ro wrote:

This patch broke the Solaris/amd64 and Solaris/sparcv9 builds:

[...]

Does rG4bd072c56b87 fix this for you?

It does indeed, thanks. FWIW, this is with g++ 11.3.0.

[efriedma]

https://github.com/llvm/llvm-project/issues/57368 is an open bug report describing a regression from this patch.

[huntergr]

In D108699#3756189, @efriedma wrote:

https://github.com/llvm/llvm-project/issues/57368 is an open bug report describing a regression from this patch.

Thanks for the report and reproducer, I'll look into it.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
 #define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
 
 #include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
 
 class AAResults;
 class DataLayout;
 class Loop;
private:
   void mergeInStatus(VectorizationSafetyStatus S);
 };
 
 class RuntimePointerChecking;
 /// A grouping of pointers. A single memcheck is required between
 /// two groups.
 struct RuntimeCheckingPtrGroup {
   /// Create a new pointer checking group containing a single
-  /// pointer, with index \p Index in RtCheck.
-  RuntimeCheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck);
+  /// pointer, with index \p Index in RtCheck and using \p Fork (0 or 1) if
+  /// this represents a forked pointer.
+  RuntimeCheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck,
+                          bool IsFork = false);
 
   RuntimeCheckingPtrGroup(unsigned Index, const SCEV *Start, const SCEV *End,
-                          unsigned AS)
+                          unsigned AS, bool IsFork = false)
       : High(End), Low(Start), AddressSpace(AS) {
-    Members.push_back(Index);
+    Members.push_back(std::make_pair(Index, IsFork ? 1 : 0));
   }
 
   /// Tries to add the pointer recorded in RtCheck at index
   /// \p Index to this pointer checking group. We can only add a pointer
   /// to a checking group if we will still be able to get
   /// the upper and lower bounds of the check. Returns true in case
   /// of success, false otherwise.
-  bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck);
+  /// For forked pointers this will only add one fork at a time, determined
+  /// by \p Fork (0 or 1).
+  bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck,
+                  bool IsFork = false);
   bool addPointer(unsigned Index, const SCEV *Start, const SCEV *End,
-                  unsigned AS, ScalarEvolution &SE);
+                  unsigned AS, ScalarEvolution &SE, bool IsFork = false);
 
   /// The SCEV expression which represents the upper bound of all the
   /// pointers in this group.
   const SCEV *High;
   /// The SCEV expression which represents the lower bound of all the
   /// pointers in this group.
   const SCEV *Low;
-  /// Indices of all the pointers that constitute this grouping.
-  SmallVector<unsigned, 2> Members;
+  /// Indices of all the pointers that constitute this grouping, including
+  /// which fork if the pointer is forked.
+  SmallVector<std::pair<unsigned, unsigned>, 2> Members;
   /// Address space of the involved pointers.
   unsigned AddressSpace;
 };
 
 /// A memcheck which made up of a pair of grouped pointers.
 typedef std::pair<const RuntimeCheckingPtrGroup *,
                   const RuntimeCheckingPtrGroup *>
     RuntimePointerCheck;
 
+/// Type for a possible forked pointer, where a single pointer could be
+/// one of two different pointers determined conditionally via a select
+/// instruction.
+using ForkedPointer = std::pair<const SCEV *, const SCEV *>;
+
 /// Holds information about the memory runtime legality checks to verify
 /// that a group of pointers do not overlap.
 class RuntimePointerChecking {
   friend struct RuntimeCheckingPtrGroup;
 
 public:
   struct PointerInfo {
     /// Holds the pointer value that we need to check.
     TrackingVH<Value> PointerValue;
-    /// Holds the smallest byte address accessed by the pointer throughout all
-    /// iterations of the loop.
-    const SCEV *Start;
-    /// Holds the largest byte address accessed by the pointer throughout all
-    /// iterations of the loop, plus 1.
-    const SCEV *End;
+    /// Holds the smallest byte address(es) accessed by the pointer throughout
+    /// all iterations of the loop.
+    const SCEV *Starts[2];
+    /// Holds the largest byte address(es) accessed by the pointer throughout
+    /// all iterations of the loop, plus 1.
+    const SCEV *Ends[2];
     /// Holds the information if this pointer is used for writing to memory.
     bool IsWritePtr;
     /// Holds the id of the set of pointers that could be dependent because of a
     /// shared underlying object.
     unsigned DependencySetId;
     /// Holds the id of the disjoint alias set to which this pointer belongs.
     unsigned AliasSetId;
-    /// SCEV for the access.
-    const SCEV *Expr;
-
-    PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End,
-                bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
-                const SCEV *Expr)
-        : PointerValue(PointerValue), Start(Start), End(End),
-          IsWritePtr(IsWritePtr), DependencySetId(DependencySetId),
-          AliasSetId(AliasSetId), Expr(Expr) {}
+    /// SCEV(s) for the access.
+    const SCEV *Exprs[2];
+    /// Determines whether this represents a forked pointer, which will have
+    /// two SCEV expressions to consider for runtime checking instead of one.
+    bool HasFork = false;
+
+    PointerInfo(Value *PointerValue, SmallVectorImpl<const SCEV *> &ScStarts,
+                SmallVectorImpl<const SCEV *> &ScEnds, bool IsWritePtr,
+                unsigned DependencySetId, unsigned AliasSetId,
+                SmallVectorImpl<const SCEV *> &ScExprs)
+        : PointerValue(PointerValue), IsWritePtr(IsWritePtr),
+          DependencySetId(DependencySetId), AliasSetId(AliasSetId) {
+      assert(ScExprs.size() <= 2 && "Too many SCEV expressions for pointer");
+      for (size_t i = 0; i < ScExprs.size(); ++i) {
+        Exprs[i] = ScExprs[i];
+        Starts[i] = ScStarts[i];
+        Ends[i] = ScEnds[i];
+      }
+
+      // If there are two SCEV expressions associated with this pointer,
+      // then we have a fork.
+      HasFork = (ScExprs.size() == 2);
+    }
   };
 
-  RuntimePointerChecking(ScalarEvolution *SE) : Need(false), SE(SE) {}
+  RuntimePointerChecking(ScalarEvolution *SE, bool AllowForkedPtrs)
+      : Need(false), AllowForkedPtrs(AllowForkedPtrs), SE(SE) {}
 
   /// Reset the state of the pointer runtime information.
   void reset() {
     Need = false;
     Pointers.clear();
+    ForkedPtrs.clear();
     Checks.clear();
   }
 
   /// Insert a pointer and calculate the start and end SCEVs.
   /// We need \p PSE in order to compute the SCEV expression of the pointer
   /// according to the assumptions that we've made during the analysis.
   /// The method might also version the pointer stride according to \p Strides,
   /// and add new predicates to \p PSE.
public:
   /// Print the list run-time memory checks necessary.
   void print(raw_ostream &OS, unsigned Depth = 0) const;
 
   /// Print \p Checks.
   void printChecks(raw_ostream &OS,
                    const SmallVectorImpl<RuntimePointerCheck> &Checks,
                    unsigned Depth = 0) const;
 
+  /// Returns true if the pointer can decompose into two separate pointers
+  /// through a select.
+  bool isForkedPtr(const Value *Ptr) const {
+    return ForkedPtrs.count(Ptr) != 0;
+  }
+
   /// This flag indicates if we need to add the runtime check.
   bool Need;
 
+  /// This flags indicates we allow diverging pointers over a select
+  bool AllowForkedPtrs;
+
   /// Information about the pointers that may require checking.
   SmallVector<PointerInfo, 2> Pointers;
 
+  /// Mapping between a pointer Value used by memory operations and a pair
+  /// of SCEV expressions. This is used in cases where a 'select' instruction
+  /// is used to form part of an address, and we could form a single
+  /// SCEVAddRecExpr with either side but not with both, so we just calculate
+  /// and store the two expressions to determine whether checks are required.
+  DenseMap<const Value *, ForkedPointer> ForkedPtrs;
+
   /// Holds a partitioning of pointers into "check groups".
   SmallVector<RuntimeCheckingPtrGroup, 2> CheckingGroups;
 
   /// Check if pointers are in the same partition
   ///
   /// \p PtrToPartition contains the partition number for pointers (-1 if the
   /// pointer belongs to multiple partitions).
   static bool

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 
 /// Enable store-to-load forwarding conflict detection. This option can
 /// be disabled for correctness testing.
 static cl::opt<bool> EnableForwardingConflictDetection(
     "store-to-load-forwarding-conflict-detection", cl::Hidden,
     cl::desc("Enable conflict detection in loop-access analysis"),
     cl::init(true));
 
+/// Enables the detection of forked pointers when analyzing loops; these
+/// pointers could have two possible values at runtime based on a conditional
+/// select instruction, and we can analyze both possibilities to determine
+/// bounds.
+static cl::opt<bool> EnableForkedPointers(
+    "enable-forked-pointer-detection", cl::Hidden,
+    cl::desc("Enable detection of pointers forked by a select instruction"),
+    cl::init(false));
+
 bool VectorizerParams::isInterleaveForced() {
   return ::VectorizationInterleave.getNumOccurrences() > 0;
 }
 
 Value *llvm::stripIntegerCast(Value *V) {
   if (auto *CI = dyn_cast<CastInst>(V))
     if (CI->getOperand(0)->getType()->isIntegerTy())
       return CI->getOperand(0);
const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
   PSE.addPredicate(*SE->getEqualPredicate(U, CT));
   auto *Expr = PSE.getSCEV(Ptr);
 
   LLVM_DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV
        << " by: " << *Expr << "\n");
   return Expr;
 }
 
+// Walk back through the IR for a pointer, looking for a select like the
+// following:
+//
+//  %offset = select i1 %cmp, i64 %a, i64 %b
+//  %addr = getelementptr double, double* %base, i64 %offset
+//  %ld = load double, double* %addr, align 8
+//
+// We won't be able to form a single SCEVAddRecExpr from this since the
+// address for each loop iteration depends on %cmp. We could potentially
+// produce multiple valid SCEVAddRecExprs, though, and check all of them for
+// memory safety/aliasing if needed.
+//
+// If we encounter some IR we don't yet handle, or something obviously fine
+// like a constant, then we just add the SCEV for that term to the list passed
+// in by the caller. If we have a node that may potentially yield a valid
+// SCEVAddRecExpr then we decompose it into parts and build the SCEV terms
+// ourselves before adding to the list.
+static void findForkedSCEVs(ScalarEvolution *SE, const Loop *L, Value *Ptr,
+                            SmallVectorImpl<const SCEV *> &ScevList) {
+  const SCEV *Scev = SE->getSCEV(Ptr);
+  if (SE->isLoopInvariant(Scev, L) || isa<SCEVAddRecExpr>(Scev) ||
+      !isa<Instruction>(Ptr)) {
+    ScevList.push_back(Scev);
+    return;
+  }
+
+  auto GetBinOpExpr = [&SE](unsigned Opcode, const SCEV *L, const SCEV *R) {
+    switch (Opcode) {
+    case Instruction::Add:
+      return SE->getAddExpr(L, R);
+    case Instruction::Sub:
+      return SE->getMinusSCEV(L, R);
+    case Instruction::Mul:
+      return SE->getMulExpr(L, R);
+    default:
+      llvm_unreachable("Unexpected binary operator when walking ForkedPtrs");
+    }
+  };
+
+  Instruction *I = cast<Instruction>(Ptr);
+  unsigned Opcode = I->getOpcode();
+  switch (Opcode) {
+  case Instruction::BitCast:
+    findForkedSCEVs(SE, L, I->getOperand(0), ScevList);
+    break;
+  case Instruction::SExt:
+  case Instruction::ZExt: {
+    SmallVector<const SCEV *, 2> ExtScevs;
+    findForkedSCEVs(SE, L, I->getOperand(0), ExtScevs);
+    for (const SCEV *Scev : ExtScevs)
+      if (Opcode == Instruction::SExt)
+        ScevList.push_back(SE->getSignExtendExpr(Scev, I->getType()));
+      else
+        ScevList.push_back(SE->getZeroExtendExpr(Scev, I->getType()));
+    break;
+  }
+  case Instruction::GetElementPtr: {
+    GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
+    Type *SourceTy = GEP->getSourceElementType();
+    // We only handle base + single offset GEPs here for now.
+    // Not dealing with preexisting gathers yet, so no vectors.
+    if (I->getNumOperands() != 2 || SourceTy->isVectorTy()) {
+      ScevList.push_back(Scev);
+      break;
+    }
+    SmallVector<const SCEV *, 2> BaseScevs;
+    SmallVector<const SCEV *, 2> OffsetScevs;
+    findForkedSCEVs(SE, L, I->getOperand(0), BaseScevs);
+    findForkedSCEVs(SE, L, I->getOperand(1), OffsetScevs);
+
+    // Make sure we get the correct pointer type to extend to, including the
+    // address space.
+    const SCEV *BaseExpr = SE->getSCEV(GEP->getPointerOperand());
+    Type *IntPtrTy = SE->getEffectiveSCEVType(BaseExpr->getType());
+    SCEV::NoWrapFlags Wrap =
+        GEP->isInBounds() ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
+    // Find the size of the type being pointed to. We only have a single
+    // index term (guarded above) so we don't need to index into arrays or
+    // structures, just get the size of the scalar value.
+    const SCEV *Size = SE->getSizeOfExpr(IntPtrTy, SourceTy);
+
+    if (OffsetScevs.size() == 2 && BaseScevs.size() == 1) {
+      const SCEV *Off1 = SE->getTruncateOrSignExtend(OffsetScevs[0], IntPtrTy);
+      const SCEV *Off2 = SE->getTruncateOrSignExtend(OffsetScevs[1], IntPtrTy);
+      const SCEV *Mul1 = SE->getMulExpr(Size, Off1, Wrap);
+      const SCEV *Mul2 = SE->getMulExpr(Size, Off2, Wrap);
+      const SCEV *Add1 = SE->getAddExpr(BaseScevs[0], Mul1, Wrap);
+      const SCEV *Add2 = SE->getAddExpr(BaseScevs[0], Mul2, Wrap);
+      ScevList.push_back(Add1);
+      ScevList.push_back(Add2);
+    } else if (BaseScevs.size() == 2 && OffsetScevs.size() == 1) {
+      const SCEV *Off = SE->getTruncateOrSignExtend(OffsetScevs[0], IntPtrTy);
+      const SCEV *Mul = SE->getMulExpr(Size, Off, Wrap);
+      const SCEV *Add1 = SE->getAddExpr(BaseScevs[0], Mul, Wrap);
+      const SCEV *Add2 = SE->getAddExpr(BaseScevs[1], Mul, Wrap);
+      ScevList.push_back(Add1);
+      ScevList.push_back(Add2);
+    } else
+      ScevList.push_back(Scev);
+    break;
+  }
+  case Instruction::Select: {
+    SmallVector<const SCEV *, 2> ChildScevs;
+    // A select means we've found a forked pointer, but we currently only
+    // support a single select per pointer so if there's another behind this
+    // then we just bail out and return the generic SCEV.
+    findForkedSCEVs(SE, L, I->getOperand(1), ChildScevs);
+    findForkedSCEVs(SE, L, I->getOperand(2), ChildScevs);
+    if (ChildScevs.size() == 2) {
+      ScevList.push_back(ChildScevs[0]);
+      ScevList.push_back(ChildScevs[1]);
+    } else
+      ScevList.push_back(Scev);
+    break;
+  }
+  // If adding another binop to this list, update GetBinOpExpr above
+  case Instruction::Add:
+  case Instruction::Sub:
+  case Instruction::Mul: {
+    SmallVector<const SCEV *, 2> LScevs;
+    SmallVector<const SCEV *, 2> RScevs;
+    findForkedSCEVs(SE, L, I->getOperand(0), LScevs);
+    findForkedSCEVs(SE, L, I->getOperand(1), RScevs);
+    if (LScevs.size() == 2 && RScevs.size() == 1) {
+      const SCEV *Op1 = GetBinOpExpr(Opcode, LScevs[0], RScevs[0]);
+      const SCEV *Op2 = GetBinOpExpr(Opcode, LScevs[1], RScevs[0]);
+      ScevList.push_back(Op1);
+      ScevList.push_back(Op2);
+    } else if (LScevs.size() == 1 && RScevs.size() == 2) {
+      const SCEV *Op1 = GetBinOpExpr(Opcode, LScevs[0], RScevs[0]);
+      const SCEV *Op2 = GetBinOpExpr(Opcode, LScevs[0], RScevs[1]);
+      ScevList.push_back(Op1);
+      ScevList.push_back(Op2);
+    } else
+      ScevList.push_back(Scev);
+    break;
+  }
+  default:
+    // Just return the current SCEV if we haven't handled the instruction yet.
+    LLVM_DEBUG(dbgs() << "ForkedPtr unhandled instruction: " << *I << "\n");
+    ScevList.push_back(Scev);
+    break;
+  }
+
+  return;
+}
+
+static Optional<ForkedPointer> findForkedPointer(ScalarEvolution *SE, Value *V,
+                                                 const Loop *L) {
+  assert(SE->isSCEVable(V->getType()) && "Value is not SCEVable!");
+  SmallVector<const SCEV *, 2> Scevs;
+  findForkedSCEVs(SE, L, V, Scevs);
+
+  // For now, we will only accept a forked pointer with two options.
+  if (Scevs.size() == 2)
+    return std::make_pair(Scevs[0], Scevs[1]);
+
+  return None;
+}
+
 RuntimeCheckingPtrGroup::RuntimeCheckingPtrGroup(
-    unsigned Index, RuntimePointerChecking &RtCheck)
-    : High(RtCheck.Pointers[Index].End), Low(RtCheck.Pointers[Index].Start),
+    unsigned Index, RuntimePointerChecking &RtCheck, bool IsFork)
+    : High(RtCheck.Pointers[Index].Ends[IsFork ? 1 : 0]),
+      Low(RtCheck.Pointers[Index].Starts[IsFork ? 1 : 0]),
       AddressSpace(RtCheck.Pointers[Index]
                        .PointerValue->getType()
                        ->getPointerAddressSpace()) {
-  Members.push_back(Index);
+  Members.push_back(std::make_pair(Index, IsFork ? 1 : 0));
 }
 
 /// Calculate Start and End points of memory access.
 /// Let's assume A is the first access and B is a memory access on N-th loop
 /// iteration. Then B is calculated as:
 ///   B = A + Step*N .
 /// Step value may be positive or negative.
 /// N is a calculated back-edge taken count:
void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, bool WritePtr,
                                     PredicatedScalarEvolution &PSE) {
   // Get the stride replaced scev.
   const SCEV *Sc = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
   ScalarEvolution *SE = PSE.getSE();
 
   const SCEV *ScStart;
   const SCEV *ScEnd;
 
+  // See if this was a ForkedPtr. If so, we want to add checks for both sides.
+  SmallVector<const SCEV *, 2> Scevs;
+  SmallVector<const SCEV *, 2> Starts;
+  SmallVector<const SCEV *, 2> Ends;
+  if (ForkedPtrs.count(Ptr)) {
+    Scevs.push_back(ForkedPtrs[Ptr].first);
+    Scevs.push_back(ForkedPtrs[Ptr].second);
+  } else
+    Scevs.push_back(Sc);
+
+  for (const SCEV *Sc : Scevs) {
     if (SE->isLoopInvariant(Sc, Lp)) {
       ScStart = ScEnd = Sc;
     } else {
       const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
       assert(AR && "Invalid addrec expression");
       const SCEV *Ex = PSE.getBackedgeTakenCount();
 
       ScStart = AR->getStart();
       ScEnd = AR->evaluateAtIteration(Ex, *SE);
       const SCEV *Step = AR->getStepRecurrence(*SE);
 
       // For expressions with negative step, the upper bound is ScStart and the
       // lower bound is ScEnd.
       if (const auto *CStep = dyn_cast<SCEVConstant>(Step)) {
         if (CStep->getValue()->isNegative())
           std::swap(ScStart, ScEnd);
       } else {
         // Fallback case: the step is not constant, but we can still
         // get the upper and lower bounds of the interval by using min/max
         // expressions.
         ScStart = SE->getUMinExpr(ScStart, ScEnd);
         ScEnd = SE->getUMaxExpr(AR->getStart(), ScEnd);
       }
     }
     // Add the size of the pointed element to ScEnd.
     auto &DL = Lp->getHeader()->getModule()->getDataLayout();
     Type *IdxTy = DL.getIndexType(Ptr->getType());
     const SCEV *EltSizeSCEV =
         SE->getStoreSizeOfExpr(IdxTy, Ptr->getType()->getPointerElementType());
     ScEnd = SE->getAddExpr(ScEnd, EltSizeSCEV);
-
-  Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, Sc);
+    Starts.push_back(ScStart);
+    Ends.push_back(ScEnd);
+  }
+  Pointers.emplace_back(Ptr, Starts, Ends, WritePtr, DepSetId, ASId, Scevs);
 }
 
 SmallVector<RuntimePointerCheck, 4>
 RuntimePointerChecking::generateChecks() const {
   SmallVector<RuntimePointerCheck, 4> Checks;
 
   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
     for (unsigned J = I + 1; J < CheckingGroups.size(); ++J) {
void RuntimePointerChecking::generateChecks(
   groupChecks(DepCands, UseDependencies);
   Checks = generateChecks();
 }
 
 bool RuntimePointerChecking::needsChecking(
     const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) const {
   for (unsigned I = 0, EI = M.Members.size(); EI != I; ++I)
     for (unsigned J = 0, EJ = N.Members.size(); EJ != J; ++J)
-      if (needsChecking(M.Members[I], N.Members[J]))
+      if (needsChecking(M.Members[I].first, N.Members[J].first))
         return true;
   return false;
 }
 
 /// Compare \p I and \p J and return the minimum.
 /// Return nullptr in case we couldn't find an answer.
 static const SCEV *getMinFromExprs(const SCEV *I, const SCEV *J,
                                    ScalarEvolution *SE) {
   const SCEV *Diff = SE->getMinusSCEV(J, I);
   const SCEVConstant *C = dyn_cast<const SCEVConstant>(Diff);
 
   if (!C)
     return nullptr;
   if (C->getValue()->isNegative())
     return J;
   return I;
 }
 
 bool RuntimeCheckingPtrGroup::addPointer(unsigned Index,
-                                         RuntimePointerChecking &RtCheck) {
+                                         RuntimePointerChecking &RtCheck,
+                                         bool IsFork) {
+  unsigned Fork = IsFork ? 1 : 0;
   return addPointer(
-      Index, RtCheck.Pointers[Index].Start, RtCheck.Pointers[Index].End,
+      Index, RtCheck.Pointers[Index].Starts[Fork],
+      RtCheck.Pointers[Index].Ends[Fork],
       RtCheck.Pointers[Index].PointerValue->getType()->getPointerAddressSpace(),
-      *RtCheck.SE);
+      *RtCheck.SE, Fork);
 }
 
 bool RuntimeCheckingPtrGroup::addPointer(unsigned Index, const SCEV *Start,
                                          const SCEV *End, unsigned AS,
-                                         ScalarEvolution &SE) {
+                                         ScalarEvolution &SE, bool IsFork) {
   assert(AddressSpace == AS &&
          "all pointers in a checking group must be in the same address space");
 
   // Compare the starts and ends with the known minimum and maximum
   // of this set. We need to know how we compare against the min/max
   // of the set in order to be able to emit memchecks.
   const SCEV *Min0 = getMinFromExprs(Start, Low, &SE);
   if (!Min0)
     return false;
 
   const SCEV *Min1 = getMinFromExprs(End, High, &SE);
   if (!Min1)
     return false;
 
   // Update the low bound  expression if we've found a new min value.
   if (Min0 == Start)
     Low = Start;
 
   // Update the high bound expression if we've found a new max value.
   if (Min1 != End)
     High = End;
 
-  Members.push_back(Index);
+  Members.push_back(std::make_pair(Index, IsFork ? 1 : 0));
   return true;
 }
 
 void RuntimePointerChecking::groupChecks(
     MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies) {
   // We build the groups from dependency candidates equivalence classes
   // because:
   //    - We know that pointers in the same equivalence class share
void RuntimePointerChecking::groupChecks(
   // is also false. In this case we will use the fallback path and create
   // separate checking groups for all pointers.
 
   // If we don't have the dependency partitions, construct a new
   // checking pointer group for each pointer. This is also required
   // for correctness, because in this case we can have checking between
   // pointers to the same underlying object.
   if (!UseDependencies) {
-    for (unsigned I = 0; I < Pointers.size(); ++I)
-      CheckingGroups.push_back(RuntimeCheckingPtrGroup(I, *this));
+    for (unsigned I = 0; I < Pointers.size(); ++I) {
+      auto Group = CheckingGroups.emplace_back(I, *this, /*Fork=*/0);
+      // Try to add a fork to the same group first, otherwise establish
+      // a new one.
+      if (Pointers[I].HasFork)
+        if (!Group.addPointer(I, *this, /*Fork=*/1))
+          CheckingGroups.emplace_back(I, *this, /*Fork=*/1);
+    }
     return;
   }
 
   unsigned TotalComparisons = 0;
 
   DenseMap<Value *, unsigned> PositionMap;
   for (unsigned Index = 0; Index < Pointers.size(); ++Index)
     PositionMap[Pointers[Index].PointerValue] = Index;
 
   // We need to keep track of what pointers we've already seen so we
   // don't process them twice.
   SmallSet<unsigned, 2> Seen;
 
   // Go through all equivalence classes, get the "pointer check groups"
   // and add them to the overall solution. We use the order in which accesses
   // appear in 'Pointers' to enforce determinism.
   for (unsigned I = 0; I < Pointers.size(); ++I) {
     // We've seen this pointer before, and therefore already processed
     // its equivalence class.
     if (Seen.count(I))
       continue;
for (unsigned I = 0; I < Pointers.size(); ++I) {
     // the order in which unions and insertions are performed on the
     // equivalence class, the iteration order is deterministic.
     for (auto MI = DepCands.member_begin(LeaderI), ME = DepCands.member_end();
          MI != ME; ++MI) {
       auto PointerI = PositionMap.find(MI->getPointer());
       assert(PointerI != PositionMap.end() &&
              "pointer in equivalence class not found in PositionMap");
       unsigned Pointer = PointerI->second;
-      bool Merged = false;
+      bool Merged[2] = {false, false};
+      // Two expressions to evaluate for forked pointers.
+      const unsigned NumExprs = Pointers[Pointer].HasFork ? 2 : 1;
       // Mark this pointer as seen.
       Seen.insert(Pointer);
 
       // Go through all the existing sets and see if we can find one
       // which can include this pointer.
       for (RuntimeCheckingPtrGroup &Group : Groups) {
         // Don't perform more than a certain amount of comparisons.
         // This should limit the cost of grouping the pointers to something
         // reasonable.  If we do end up hitting this threshold, the algorithm
         // will create separate groups for all remaining pointers.
         if (TotalComparisons > MemoryCheckMergeThreshold)
           break;
 
         TotalComparisons++;
 
-        if (Group.addPointer(Pointer, *this)) {
-          Merged = true;
+        // Try to add both forks, if applicable.
+        for (unsigned J = 0; J < NumExprs; ++J)
+          if (!Merged[J])
+            Merged[J] = Group.addPointer(Pointer, *this, J);
+
+        if (Merged[0] && (Merged[1] || NumExprs == 1))
           break;
-        }
-      }
 
-      if (!Merged)
-        // We couldn't add this pointer to any existing set or the threshold
-        // for the number of comparisons has been reached. Create a new group
-        // to hold the current pointer.
-        Groups.push_back(RuntimeCheckingPtrGroup(Pointer, *this));
+      // If we couldn't add the pointer expression(s) to any existing set or
+      // the threshold for the number of comparisons has been reached, create a
+      // new group to hold the current pointer expression(s).
+      RuntimeCheckingPtrGroup *Group = nullptr;
+      if (!Merged[0])
+        Group = &Groups.emplace_back(Pointer, *this);
+      if (!Merged[1] && NumExprs == 2) {
+        // Try merging forks first, as they may have the same base address
+        // but different offsets.
+        if (!Group || !Group->addPointer(Pointer, *this, /*Fork=*/1))
+          Groups.emplace_back(Pointer, *this, /*Fork=*/1);
+      }
     }
 
     // We've computed the grouped checks for this partition.
     // Save the results and continue with the next one.
     llvm::copy(Groups, std::back_inserter(CheckingGroups));
   }
 }
 
void RuntimePointerChecking::printChecks(
     unsigned Depth) const {
   unsigned N = 0;
   for (const auto &Check : Checks) {
     const auto &First = Check.first->Members, &Second = Check.second->Members;
 
     OS.indent(Depth) << "Check " << N++ << ":\n";
 
     OS.indent(Depth + 2) << "Comparing group (" << Check.first << "):\n";
-    for (unsigned K = 0; K < First.size(); ++K)
-      OS.indent(Depth + 2) << *Pointers[First[K]].PointerValue << "\n";
+    for (unsigned K = 0; K < First.size(); ++K) {
+      const PointerInfo &Info = Pointers[First[K].first];
+      OS.indent(Depth + 2) << *Info.PointerValue << "\n";
+      if (Info.HasFork)
+        OS.indent(Depth + 6)
+            << "Fork: " << *Info.Exprs[First[K].second] << "\n";
+    }
 
     OS.indent(Depth + 2) << "Against group (" << Check.second << "):\n";
-    for (unsigned K = 0; K < Second.size(); ++K)
-      OS.indent(Depth + 2) << *Pointers[Second[K]].PointerValue << "\n";
+    for (unsigned K = 0; K < Second.size(); ++K) {
+      const PointerInfo &Info = Pointers[Second[K].first];
+      OS.indent(Depth + 2) << *Info.PointerValue << "\n";
+      if (Info.HasFork)
+        OS.indent(Depth + 6)
+            << "Fork: " << *Info.Exprs[Second[K].second] << "\n";
+    }
   }
 }
 
 void RuntimePointerChecking::print(raw_ostream &OS, unsigned Depth) const {
 
   OS.indent(Depth) << "Run-time memory checks:\n";
   printChecks(OS, Checks, Depth);
 
   OS.indent(Depth) << "Grouped accesses:\n";
   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
     const auto &CG = CheckingGroups[I];
 
     OS.indent(Depth + 2) << "Group " << &CG << ":\n";
     OS.indent(Depth + 4) << "(Low: " << *CG.Low << " High: " << *CG.High
                          << ")\n";
     for (unsigned J = 0; J < CG.Members.size(); ++J) {
-      OS.indent(Depth + 6) << "Member: " << *Pointers[CG.Members[J]].Expr
+      const PointerInfo &Info = Pointers[CG.Members[J].first];
+      OS.indent(Depth + 6) << "Member: " << *(Info.Exprs[CG.Members[J].second])
                            << "\n";
     }
   }
 }
 
 namespace {
 
 /// Analyses memory accesses in a loop.

 
 } // end anonymous namespace
 
 /// Check whether a pointer can participate in a runtime bounds check.
 /// If \p Assume, try harder to prove that we can compute the bounds of \p Ptr
 /// by adding run-time checks (overflow checks) if necessary.
 static bool hasComputableBounds(PredicatedScalarEvolution &PSE,
                                 const ValueToValueMap &Strides, Value *Ptr,
-                                Loop *L, bool Assume) {
+                                Loop *L, bool Assume,
+                                RuntimePointerChecking &RtCheck) {
   const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
 
+  ScalarEvolution *SE = PSE.getSE();
   // The bounds for loop-invariant pointer is trivial.
-  if (PSE.getSE()->isLoopInvariant(PtrScev, L))
+  if (SE->isLoopInvariant(PtrScev, L))
     return true;
 
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
 
   if (!AR && Assume)
     AR = PSE.getAsAddRec(Ptr);
 
-  if (!AR)
-    return false;
-
+  if (AR)
     return AR->isAffine();
+
+  // If we can't find a single SCEVAddRecExpr, then maybe we can find two.
+  // The findForkedPointer function tries walking backwards through IR until
+  // it finds operands that are either loop invariant or for which a
+  // SCEVAddRecExpr can be formed. If a select instruction is encountered
+  // during this walk then we split the walk and try to generate two valid
+  // SCEVAddRecExprs. Both of those SCEVs can then be considered when
+  // deciding whether runtime checks are required.
+  if (RtCheck.AllowForkedPtrs) {
+    Optional<ForkedPointer> FPtr = findForkedPointer(SE, Ptr, L);
+    if (!FPtr)
+      return false;
+
+    const SCEV *A = FPtr->first;
+    const SCEV *B = FPtr->second;
+    LLVM_DEBUG(dbgs() << "LAA: ForkedPtr found: " << *Ptr << "\n");
+    LLVM_DEBUG(dbgs() << "LAA: SCEV1: " << *A << "\n");
+    LLVM_DEBUG(dbgs() << "LAA: SCEV2: " << *B << "\n");
+    if (isa<SCEVAddRecExpr>(A) && cast<SCEVAddRecExpr>(A)->isAffine() &&
+        isa<SCEVAddRecExpr>(B) && cast<SCEVAddRecExpr>(B)->isAffine()) {
+      RtCheck.ForkedPtrs[Ptr] = *FPtr;
+      return true;
+    }
+
+    LLVM_DEBUG(
+        dbgs() << "LAA: Could not determine bounds for forked pointer\n");
+  }
+
+  return false;
 }
 
 /// Check whether a pointer address cannot wrap.
 static bool isNoWrap(PredicatedScalarEvolution &PSE,
-                     const ValueToValueMap &Strides, Value *Ptr, Loop *L) {
+                     const ValueToValueMap &Strides, Value *Ptr, Loop *L,
+                     RuntimePointerChecking &RtCheck) {
   const SCEV *PtrScev = PSE.getSCEV(Ptr);
   if (PSE.getSE()->isLoopInvariant(PtrScev, L))
     return true;
 
+  // The SCEV generated directly from a forked pointer is not an AddRecExpr,
+  // but an unknown SCEV. The PSE.hasNoOverflow method currently assumes
+  // that it must be an AddRecExpr and just casts. So we just bail out at
+  // this point, since we can't pass in the SCEVs one at a time --
+  // hasNoOverflow takes a Value* as a param instead of a SCEV*.
+  // TODO: Support overflow checking for ForkedPointers.
+  //
+  // We can, however, calculate an effective stride for each side of the fork
+  // and check if the stride is 1 for both; this is the other way we can
+  // assume a pointer doesn't wrap.
+  if (RtCheck.isForkedPtr(Ptr)) {
+    auto SCEVs = RtCheck.ForkedPtrs[Ptr];
+    const SCEVAddRecExpr *LSAR = cast<SCEVAddRecExpr>(SCEVs.first);
+    const SCEVAddRecExpr *RSAR = cast<SCEVAddRecExpr>(SCEVs.second);
+    const SCEV *LStep = LSAR->getStepRecurrence(*PSE.getSE());
+    const SCEV *RStep = RSAR->getStepRecurrence(*PSE.getSE());
+
+    if (LStep != RStep) {
+      LLVM_DEBUG(dbgs() << "LAA: Forkedptr with mismatched steps\n");
+      return false;
+    }
+
+    auto *PtrTy = dyn_cast<PointerType>(Ptr->getType());
+    auto &DL = L->getHeader()->getModule()->getDataLayout();
+    int64_t Size = DL.getTypeAllocSize(PtrTy->getElementType()).getFixedSize();
+
+    const SCEVConstant *C = dyn_cast<SCEVConstant>(LStep);
+    if (!C) {
+      LLVM_DEBUG(dbgs() << "LAA: Forkedptr with non-constant steps\n");
+      return false;
+    }
+    const APInt &APStepVal = C->getAPInt();
+    if (APStepVal.getBitWidth() > 64) {
+      LLVM_DEBUG(dbgs() << "LAA: Forkedptr step is too large\n");
+      return false;
+    }
+
+    int64_t StepVal = APStepVal.getSExtValue();
+
+    // Strided access.
+    int64_t Stride = StepVal / Size;
+    int64_t Rem = StepVal % Size;
+    if (Rem) {
+      LLVM_DEBUG(dbgs() << "LAA: Forkedptr step not multiple of elt size\n");
+      return false;
+    }
+
+    return Stride == 1;
+  }
+
   Type *AccessTy = Ptr->getType()->getPointerElementType();
   int64_t Stride = getPtrStride(PSE, AccessTy, Ptr, L, Strides);
   if (Stride == 1 || PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW))
     return true;
 
   return false;
 }
 
bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
                                           MemAccessInfo Access,
                                           const ValueToValueMap &StridesMap,
                                           DenseMap<Value *, unsigned> &DepSetId,
                                           Loop *TheLoop, unsigned &RunningDepId,
                                           unsigned ASId, bool ShouldCheckWrap,
                                           bool Assume) {
   Value *Ptr = Access.getPointer();
 
-  if (!hasComputableBounds(PSE, StridesMap, Ptr, TheLoop, Assume))
+  if (!hasComputableBounds(PSE, StridesMap, Ptr, TheLoop, Assume, RtCheck))
     return false;
 
   // When we run after a failing dependency check we have to make sure
   // we don't have wrapping pointers.
-  if (ShouldCheckWrap && !isNoWrap(PSE, StridesMap, Ptr, TheLoop)) {
+  if (ShouldCheckWrap && !isNoWrap(PSE, StridesMap, Ptr, TheLoop, RtCheck)) {
     auto *Expr = PSE.getSCEV(Ptr);
     if (!Assume || !isa<SCEVAddRecExpr>(Expr))
       return false;
     PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
   }
 
   // The id of the dependence set.
   unsigned DepId;
 
   if (isDependencyCheckNeeded()) {
     Value *Leader = DepCands.getLeaderValue(Access).getPointer();
     unsigned &LeaderId = DepSetId[Leader];
     if (!LeaderId)
       LeaderId = RunningDepId++;
     DepId = LeaderId;
   } else
     // Each access has its own dependence set.
     DepId = RunningDepId++;
 
   bool IsWrite = Access.getInt();
   RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap, PSE);
   LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
 
   return true;
  }
 
 bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
                                      ScalarEvolution *SE, Loop *TheLoop,
                                      const ValueToValueMap &StridesMap,
                                      bool ShouldCheckWrap) {
   // Find pointers with computable bounds. We are going to use this information
   // to place a runtime bound check.
   bool CanDoRT = true;
 
   bool MayNeedRTCheck = false;
   if (!IsRTCheckAnalysisNeeded) return true;
 
   bool IsDepCheckNeeded = isDependencyCheckNeeded();
 
   // We assign a consecutive id to access from different alias sets.
   // Accesses between different groups doesn't need to be checked.
   unsigned ASId = 0;
   for (auto &AS : AST) {
     int NumReadPtrChecks = 0;
     int NumWritePtrChecks = 0;
     bool CanDoAliasSetRT = true;
     ++ASId;
 
     // We assign consecutive id to access from different dependence sets.
     // Accesses within the same set don't need a runtime check.
     unsigned RunningDepId = 1;
     DenseMap<Value *, unsigned> DepSetId;
 
     SmallVector<MemAccessInfo, 4> Retries;
 
     // First, count how many write and read accesses are in the alias set. Also
     // collect MemAccessInfos for later.
     SmallVector<MemAccessInfo, 4> AccessInfos;
     for (const auto &A : AS) {
       Value *Ptr = A.getValue();
       bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
 
       if (IsWrite)
         ++NumWritePtrChecks;
       else
         ++NumReadPtrChecks;
       AccessInfos.emplace_back(Ptr, IsWrite);
     }
 
     // We do not need runtime checks for this alias set, if there are no writes
     // or a single write and no reads.
     if (NumWritePtrChecks == 0 ||
         (NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
       assert((AS.size() <= 1 ||
               all_of(AS,
                      [this](auto AC) {
                        MemAccessInfo AccessWrite(AC.getValue(), true);
                        return DepCands.findValue(AccessWrite) == DepCands.end();
                      })) &&
              "Can only skip updating CanDoRT below, if all entries in AS "
              "are reads or there is at most 1 entry");
       continue;
for (auto &AS : AST) {
     if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
       // Reset the CanDoSetRt flag and retry all accesses that have failed.
       // We know that we need these checks, so we can now be more aggressive
       // and add further checks if required (overflow checks).
       CanDoAliasSetRT = true;
       for (auto Access : Retries)
         if (!createCheckForAccess(RtCheck, Access, StridesMap, DepSetId,
                                   TheLoop, RunningDepId, ASId,
                                   ShouldCheckWrap, /*Assume=*/true)) {
           CanDoAliasSetRT = false;
           break;
         }
     }
 
     CanDoRT &= CanDoAliasSetRT;
     MayNeedRTCheck |= NeedsAliasSetRTCheck;
     ++ASId;
void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
 
   bool HasComplexMemInst = false;
 
   // A runtime check is only legal to insert if there are no convergent calls.
   HasConvergentOp = false;
 
   PtrRtChecking->Pointers.clear();
   PtrRtChecking->Need = false;
+  PtrRtChecking->ForkedPtrs.clear();
 
   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
 
   const bool EnableMemAccessVersioningOfLoop =
       EnableMemAccessVersioning &&
       !TheLoop->getHeader()->getParent()->hasOptSize();
 
   // For each block.
void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
   SymbolicStrides[Ptr] = Stride;
   StrideSet.insert(Stride);
 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const TargetLibraryInfo *TLI, AAResults *AA,
                                DominatorTree *DT, LoopInfo *LI)
     : PSE(std::make_unique<PredicatedScalarEvolution>(*SE, *L)),
-      PtrRtChecking(std::make_unique<RuntimePointerChecking>(SE)),
+      PtrRtChecking(
+          std::make_unique<RuntimePointerChecking>(SE, EnableForkedPointers)),
       DepChecker(std::make_unique<MemoryDepChecker>(*PSE, L)), TheLoop(L),
       NumLoads(0), NumStores(0), MaxSafeDepDistBytes(-1), CanVecMem(false),
       HasConvergentOp(false),
       HasDependenceInvolvingLoopInvariantAddress(false) {
   if (canAnalyzeLoop())
     analyzeLoop(AA, LI, TLI, DT);
 }
 

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

private:
   /// number -1 means that the pointer is used in multiple partitions.  In this
   /// case we can't safely omit the check.
   SmallVector<RuntimePointerCheck, 4> includeOnlyCrossPartitionChecks(
       const SmallVectorImpl<RuntimePointerCheck> &AllChecks,
       const SmallVectorImpl<int> &PtrToPartition,
       const RuntimePointerChecking *RtPtrChecking) {
     SmallVector<RuntimePointerCheck, 4> Checks;
 
-    copy_if(AllChecks, std::back_inserter(Checks),
-            [&](const RuntimePointerCheck &Check) {
-              for (unsigned PtrIdx1 : Check.first->Members)
-                for (unsigned PtrIdx2 : Check.second->Members)
-                  // Only include this check if there is a pair of pointers
-                  // that require checking and the pointers fall into
-                  // separate partitions.
-                  //
-                  // (Note that we already know at this point that the two
-                  // pointer groups need checking but it doesn't follow
-                  // that each pair of pointers within the two groups need
-                  // checking as well.
-                  //
-                  // In other words we don't want to include a check just
-                  // because there is a pair of pointers between the two
-                  // pointer groups that require checks and a different
-                  // pair whose pointers fall into different partitions.)
-                  if (RtPtrChecking->needsChecking(PtrIdx1, PtrIdx2) &&
-                      !RuntimePointerChecking::arePointersInSamePartition(
-                          PtrToPartition, PtrIdx1, PtrIdx2))
-                    return true;
-              return false;
-            });
+    copy_if(
+        AllChecks, std::back_inserter(Checks),
+          for (auto PtrIdx1 : Check.first->Members)
+            for (auto PtrIdx2 : Check.second->Members)
+              if (RtPtrChecking->needsChecking(PtrIdx1.first, PtrIdx2.first) &&
+                      PtrToPartition, PtrIdx1.first, PtrIdx2.first))
 
     return Checks;
   }
 
   /// Check whether the loop metadata is forcing distribution to be
   /// enabled/disabled.
   void setForced() {
     Optional<const MDOperand *> Value =

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

SmallVector<RuntimePointerCheck, 4> collectMemchecks(
 
     const auto &AllChecks = LAI.getRuntimePointerChecking()->getChecks();
     SmallVector<RuntimePointerCheck, 4> Checks;
 
     copy_if(AllChecks, std::back_inserter(Checks),
             [&](const RuntimePointerCheck &Check) {
               for (auto PtrIdx1 : Check.first->Members)
                 for (auto PtrIdx2 : Check.second->Members)
-                  if (needsChecking(PtrIdx1, PtrIdx2, PtrsWrittenOnFwdingPath,
-                                    CandLoadPtrs))
+                  if (needsChecking(PtrIdx1.first, PtrIdx2.first,
+                                    PtrsWrittenOnFwdingPath, CandLoadPtrs))
                     return true;
               return false;
             });
 
     LLVM_DEBUG(dbgs() << "\nPointer Checks (count: " << Checks.size()
                       << "):\n");
     LLVM_DEBUG(LAI.getRuntimePointerChecking()->printChecks(dbgs(), Checks));
 

llvm/lib/Transforms/Utils/LoopVersioning.cpp

void LoopVersioning::prepareNoAliasMetadata() {
   // reverse map from pointers to the pointer checking group they were assigned
   // to.
   MDBuilder MDB(Context);
   MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
 
   for (const auto &Group : RtPtrChecking->CheckingGroups) {
     GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
 
-    for (unsigned PtrIdx : Group.Members)
-      PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
+    for (auto PtrIdx : Group.Members)
+      PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx.first).PointerValue] =
+          &Group;
   }
 
   // Go through the checks and for each pointer group, collect the scopes for
   // each non-aliasing pointer group.
   DenseMap<const RuntimeCheckingPtrGroup *, SmallVector<Metadata *, 4>>
       GroupToNonAliasingScopes;
 
   for (const auto &Check : AliasChecks)

llvm/test/Analysis/LoopAccessAnalysis/forked-pointers.ll

-; RUN: opt -loop-accesses -analyze -enable-new-pm=0 %s 2>&1 | FileCheck %s
-; RUN: opt -disable-output -passes='require<scalar-evolution>,require<aa>,loop(print-access-info)' %s 2>&1 | FileCheck %s
+; RUN: opt -enable-forked-pointer-detection -loop-accesses -analyze -enable-new-pm=0 %s 2>&1 | FileCheck %s
+; RUN: opt -enable-forked-pointer-detection -disable-output -passes='require<scalar-evolution>,require<aa>,loop(print-access-info)' %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 ; CHECK-LABEL: function 'forked_ptrs_different_base_same_offset':
-; CHECK-NEXT:  for.body:
-; CHECK-NEXT:    Report: cannot identify array bounds
-; CHECK-NEXT:    Dependences:
-; CHECK-NEXT:    Run-time memory checks:
-; CHECK-NEXT:    Grouped accesses:
+; CHECK-NEXT: for.body:
+; CHECK-NEXT:   Memory dependences are safe with run-time checks
+; CHECK-NEXT:   Dependences:
+; CHECK-NEXT:   Run-time memory checks:
+; CHECK-NEXT:   Check 0:
+; CHECK-NEXT:     Comparing group
+; CHECK-NEXT:       %1 = getelementptr inbounds float, float* %Dest, i64 %indvars.iv
+; CHECK-NEXT:     Against group
+; CHECK-NEXT:       %arrayidx = getelementptr inbounds i32, i32* %Preds, i64 %indvars.iv
+; CHECK-NEXT:   Check 1:
+; CHECK-NEXT:     Comparing group
+; CHECK-NEXT:       %1 = getelementptr inbounds float, float* %Dest, i64 %indvars.iv
+; CHECK-NEXT:     Against group
+; CHECK-NEXT:       %.sink.in = getelementptr inbounds float, float* %spec.select, i64 %indvars.iv
+; CHECK-NEXT:         Fork: {%Base2,+,4}<nsw><%for.body>
+; CHECK-NEXT:   Check 2:
+; CHECK-NEXT:     Comparing group
+; CHECK-NEXT:       %1 = getelementptr inbounds float, float* %Dest, i64 %indvars.iv
+; CHECK-NEXT:     Against group
+; CHECK-NEXT:       %.sink.in = getelementptr inbounds float, float* %spec.select, i64 %indvars.iv
+; CHECK-NEXT:         Fork: {%Base1,+,4}<nsw><%for.body>
+; CHECK-NEXT:   Grouped accesses:
+; CHECK-NEXT:     Group
+; CHECK-NEXT:       (Low: %Dest High: (400 + %Dest))
+; CHECK-NEXT:         Member: {%Dest,+,4}<nuw><%for.body>
+; CHECK-NEXT:     Group
+; CHECK-NEXT:       (Low: %Preds High: (400 + %Preds))
+; CHECK-NEXT:         Member: {%Preds,+,4}<nuw><%for.body>
+; CHECK-NEXT:     Group
+; CHECK-NEXT:       (Low: %Base2 High: (400 + %Base2))
+; CHECK-NEXT:         Member: {%Base2,+,4}<nsw><%for.body>
+; CHECK-NEXT:     Group
+; CHECK-NEXT:       (Low: %Base1 High: (400 + %Base1))
+; CHECK-NEXT:         Member: {%Base1,+,4}<nsw><%for.body>
 ; CHECK-EMPTY:
-; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
-; CHECK-NEXT:    SCEV assumptions:
+; CHECK-NEXT:   Non vectorizable stores to invariant address were not found in loop.
+; CHECK-NEXT:   SCEV assumptions:
 ; CHECK-EMPTY:
-; CHECK-NEXT:    Expressions re-written:
+; CHECK-NEXT:   Expressions re-written:
 
 ;;;; Derived from the following C code
 ;; void forked_ptrs_different_base_same_offset(float *A, float *B, float *C, int *D) {
 ;;   for (int i=0; i<100; i++) {
 ;;     if (D[i] != 0) {
 ;;       C[i] = A[i];
 ;;     } else {
 ;;       C[i] = B[i];
for.body:
   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
   %arrayidx = getelementptr inbounds i32, i32* %Preds, i64 %indvars.iv
   %0 = load i32, i32* %arrayidx, align 4
   %cmp1.not = icmp eq i32 %0, 0
   %spec.select = select i1 %cmp1.not, float* %Base2, float* %Base1
   %.sink.in = getelementptr inbounds float, float* %spec.select, i64 %indvars.iv
   %.sink = load float, float* %.sink.in, align 4
   %1 = getelementptr inbounds float, float* %Dest, i64 %indvars.iv
   store float %.sink, float* %1, align 4
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %exitcond.not = icmp eq i64 %indvars.iv.next, 100
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: function 'forked_ptrs_same_base_different_offset':
-; CHECK-NEXT:   for.body:
-; CHECK-NEXT:     Report: cannot identify array bounds
-; CHECK-NEXT:     Dependences:
-; CHECK-NEXT:     Run-time memory checks:
-; CHECK-NEXT:     Grouped accesses:
+; CHECK-NEXT: for.body:
+; CHECK-NEXT:   Memory dependences are safe with run-time checks
+; CHECK-NEXT:   Dependences:
+; CHECK-NEXT:   Run-time memory checks:
+; CHECK-NEXT:   Check 0:
+; CHECK-NEXT:     Comparing group
+; CHECK-NEXT:       %arrayidx5 = getelementptr inbounds float, float* %Dest, i64 %indvars.iv
+; CHECK-NEXT:     Against group
+; CHECK-NEXT:       %arrayidx = getelementptr inbounds i32, i32* %Preds, i64 %indvars.iv
+; CHECK-NEXT:   Check 1:
+; CHECK-NEXT:     Comparing group
+; CHECK-NEXT:       %arrayidx5 = getelementptr inbounds float, float* %Dest, i64 %indvars.iv
+; CHECK-NEXT:     Against group
+; CHECK-NEXT:       %arrayidx3 = getelementptr inbounds float, float* %Base, i64 %idxprom213
+; CHECK-NEXT:         Fork: {(4 + %Base)<nsw>,+,4}<nsw><%for.body>
+; CHECK-NEXT:       %arrayidx3 = getelementptr inbounds float, float* %Base, i64 %idxprom213
+; CHECK-NEXT:         Fork: {%Base,+,4}<nsw><%for.body>
+; CHECK-NEXT:   Grouped accesses:
+; CHECK-NEXT:     Group
+; CHECK-NEXT:       (Low: %Dest High: (400 + %Dest))
+; CHECK-NEXT:         Member: {%Dest,+,4}<nuw><%for.body>
+; CHECK-NEXT:     Group
+; CHECK-NEXT:       (Low: %Preds High: (400 + %Preds))
+; CHECK-NEXT:         Member: {%Preds,+,4}<nuw><%for.body>
+; CHECK-NEXT:     Group
+; CHECK-NEXT:       (Low: %Base High: (404 + %Base))
+; CHECK-NEXT:         Member: {(4 + %Base)<nsw>,+,4}<nsw><%for.body>
+; CHECK-NEXT:         Member: {%Base,+,4}<nsw><%for.body>
 ; CHECK-EMPTY:
-; CHECK-NEXT:     Non vectorizable stores to invariant address were not found in loop.
-; CHECK-NEXT:     SCEV assumptions:
+; CHECK-NEXT:   Non vectorizable stores to invariant address were not found in loop.
+; CHECK-NEXT:   SCEV assumptions:
 ; CHECK-EMPTY:
-; CHECK-NEXT:     Expressions re-written:
+; CHECK-NEXT:   Expressions re-written:
 
 ;;;; Derived from the following C code
 ;; void forked_ptrs_same_base_different_offset(float *A, float *B, int *C) {
 ;;   int offset;
 ;;   for (int i = 0; i < 100; i++) {
 ;;     if (C[i] != 0)
 ;;       offset = i;
 ;;     else

llvm/test/Transforms/LoopVectorize/forked-pointers.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -loop-vectorize -instcombine -force-vector-width=4 -S < %s 2>&1 | FileCheck %s
+; RUN: opt -enable-forked-pointer-detection -loop-vectorize -instcombine -force-vector-width=4 -S < %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 ;;;; Derived from the following C code
 ;; void forked_ptrs_different_base_same_offset(float *A, float *B, float *C, int *D) {
 ;;   for (int i=0; i<100; i++) {
 ;;     if (D[i] != 0) {
 ;;       C[i] = A[i];
 ;;     } else {
 ;;       C[i] = B[i];
 ;;     }
 ;;   }
 ;; }
 
 define dso_local void @forked_ptrs_different_base_same_offset(float* nocapture readonly %Base1, float* nocapture readonly %Base2, float* nocapture %Dest, i32* nocapture readonly %Preds) {
 ; CHECK-LABEL: @forked_ptrs_different_base_same_offset(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]
+; CHECK:       vector.memcheck:
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr float, float* [[DEST:%.*]], i64 100
+; CHECK-NEXT:    [[SCEVGEP4:%.*]] = getelementptr i32, i32* [[PREDS:%.*]], i64 100
+; CHECK-NEXT:    [[SCEVGEP7:%.*]] = getelementptr float, float* [[BASE2:%.*]], i64 100
+; CHECK-NEXT:    [[SCEVGEP10:%.*]] = getelementptr float, float* [[BASE1:%.*]], i64 100
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[SCEVGEP4]] to float*
+; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ugt float* [[TMP0]], [[DEST]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast float* [[SCEVGEP]] to i32*
+; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ugt i32* [[TMP1]], [[PREDS]]
+; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
+; CHECK-NEXT:    [[BOUND012:%.*]] = icmp ugt float* [[SCEVGEP7]], [[DEST]]
+; CHECK-NEXT:    [[BOUND113:%.*]] = icmp ugt float* [[SCEVGEP]], [[BASE2]]
+; CHECK-NEXT:    [[FOUND_CONFLICT14:%.*]] = and i1 [[BOUND012]], [[BOUND113]]
+; CHECK-NEXT:    [[CONFLICT_RDX:%.*]] = or i1 [[FOUND_CONFLICT]], [[FOUND_CONFLICT14]]
+; CHECK-NEXT:    [[BOUND015:%.*]] = icmp ugt float* [[SCEVGEP10]], [[DEST]]
+; CHECK-NEXT:    [[BOUND116:%.*]] = icmp ugt float* [[SCEVGEP]], [[BASE1]]
+; CHECK-NEXT:    [[FOUND_CONFLICT17:%.*]] = and i1 [[BOUND015]], [[BOUND116]]
+; CHECK-NEXT:    [[CONFLICT_RDX18:%.*]] = or i1 [[CONFLICT_RDX]], [[FOUND_CONFLICT17]]
+; CHECK-NEXT:    br i1 [[CONFLICT_RDX18]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x float*> poison, float* [[BASE2]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x float*> [[BROADCAST_SPLATINSERT]], <4 x float*> poison, <4 x i32> zeroinitializer
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT19:%.*]] = insertelement <4 x float*> poison, float* [[BASE1]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT20:%.*]] = shufflevector <4 x float*> [[BROADCAST_SPLATINSERT19]], <4 x float*> poison, <4 x i32> zeroinitializer
+; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i64 [[INDEX]], 1
+; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[INDEX]], 2
+; CHECK-NEXT:    [[TMP4:%.*]] = or i64 [[INDEX]], 3
+; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i32, i32* [[PREDS]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP6:%.*]] = bitcast i32* [[TMP5]] to <4 x i32>*
+; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP6]], align 4, !alias.scope !0
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq <4 x i32> [[WIDE_LOAD]], zeroinitializer
+; CHECK-NEXT:    [[TMP8:%.*]] = select <4 x i1> [[TMP7]], <4 x float*> [[BROADCAST_SPLAT]], <4 x float*> [[BROADCAST_SPLAT20]]
+; CHECK-NEXT:    [[TMP9:%.*]] = extractelement <4 x float*> [[TMP8]], i32 0
+; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds float, float* [[TMP9]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP11:%.*]] = extractelement <4 x float*> [[TMP8]], i32 1
+; CHECK-NEXT:    [[TMP12:%.*]] = getelementptr inbounds float, float* [[TMP11]], i64 [[TMP2]]
+; CHECK-NEXT:    [[TMP13:%.*]] = extractelement <4 x float*> [[TMP8]], i32 2
+; CHECK-NEXT:    [[TMP14:%.*]] = getelementptr inbounds float, float* [[TMP13]], i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <4 x float*> [[TMP8]], i32 3
+; CHECK-NEXT:    [[TMP16:%.*]] = getelementptr inbounds float, float* [[TMP15]], i64 [[TMP4]]
+; CHECK-NEXT:    [[TMP17:%.*]] = load float, float* [[TMP10]], align 4, !alias.scope !3
+; CHECK-NEXT:    [[TMP18:%.*]] = load float, float* [[TMP12]], align 4, !alias.scope !3
+; CHECK-NEXT:    [[TMP19:%.*]] = load float, float* [[TMP14]], align 4, !alias.scope !3
+; CHECK-NEXT:    [[TMP20:%.*]] = load float, float* [[TMP16]], align 4, !alias.scope !3
+; CHECK-NEXT:    [[TMP21:%.*]] = insertelement <4 x float> poison, float [[TMP17]], i32 0
+; CHECK-NEXT:    [[TMP22:%.*]] = insertelement <4 x float> [[TMP21]], float [[TMP18]], i32 1
+; CHECK-NEXT:    [[TMP23:%.*]] = insertelement <4 x float> [[TMP22]], float [[TMP19]], i32 2
+; CHECK-NEXT:    [[TMP24:%.*]] = insertelement <4 x float> [[TMP23]], float [[TMP20]], i32 3
+; CHECK-NEXT:    [[TMP25:%.*]] = getelementptr inbounds float, float* [[DEST]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP26:%.*]] = bitcast float* [[TMP25]] to <4 x float>*
+; CHECK-NEXT:    store <4 x float> [[TMP24]], <4 x float>* [[TMP26]], align 4, !alias.scope !5, !noalias !7
+; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
+; CHECK-NEXT:    [[TMP27:%.*]] = icmp eq i64 [[INDEX_NEXT]], 100
+; CHECK-NEXT:    br i1 [[TMP27]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP9:![0-9]+]]
+; CHECK:       middle.block:
+; CHECK-NEXT:    br i1 true, label [[FOR_COND_CLEANUP:%.*]], label [[SCALAR_PH]]
+; CHECK:       scalar.ph:
+; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 100, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[VECTOR_MEMCHECK]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.cond.cleanup:
 ; CHECK-NEXT:    ret void
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[PREDS:%.*]], i64 [[INDVARS_IV]]
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
-; CHECK-NEXT:    [[CMP1_NOT:%.*]] = icmp eq i32 [[TMP0]], 0
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[CMP1_NOT]], float* [[BASE2:%.*]], float* [[BASE1:%.*]]
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[PREDS]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    [[TMP28:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[CMP1_NOT:%.*]] = icmp eq i32 [[TMP28]], 0
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[CMP1_NOT]], float* [[BASE2]], float* [[BASE1]]
 ; CHECK-NEXT:    [[DOTSINK_IN:%.*]] = getelementptr inbounds float, float* [[SPEC_SELECT]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    [[DOTSINK:%.*]] = load float, float* [[DOTSINK_IN]], align 4
-; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds float, float* [[DEST:%.*]], i64 [[INDVARS_IV]]
-; CHECK-NEXT:    store float [[DOTSINK]], float* [[TMP1]], align 4
+; CHECK-NEXT:    [[TMP29:%.*]] = getelementptr inbounds float, float* [[DEST]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store float [[DOTSINK]], float* [[TMP29]], align 4
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 100
-; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
+; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY]], !llvm.loop [[LOOP11:![0-9]+]]
 ;
 entry:
   br label %for.body
 
 for.cond.cleanup:
   ret void
 
 for.body:

 ;;       offset = i+1;
 ;;     B[i] = A[offset];
 ;;   }
 ;; }
 
 define dso_local void @forked_ptrs_same_base_different_offset(float* nocapture readonly %Base, float* nocapture %Dest, i32* nocapture readonly %Preds) {
 ; CHECK-LABEL: @forked_ptrs_same_base_different_offset(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]
+; CHECK:       vector.memcheck:
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr float, float* [[DEST:%.*]], i64 100
+; CHECK-NEXT:    [[SCEVGEP4:%.*]] = getelementptr i32, i32* [[PREDS:%.*]], i64 100
+; CHECK-NEXT:    [[SCEVGEP7:%.*]] = getelementptr float, float* [[BASE:%.*]], i64 101
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[SCEVGEP4]] to float*
+; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ugt float* [[TMP0]], [[DEST]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast float* [[SCEVGEP]] to i32*
+; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ugt i32* [[TMP1]], [[PREDS]]
+; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
+; CHECK-NEXT:    [[BOUND09:%.*]] = icmp ugt float* [[SCEVGEP7]], [[DEST]]
+; CHECK-NEXT:    [[BOUND110:%.*]] = icmp ugt float* [[SCEVGEP]], [[BASE]]
+; CHECK-NEXT:    [[FOUND_CONFLICT11:%.*]] = and i1 [[BOUND09]], [[BOUND110]]
+; CHECK-NEXT:    [[CONFLICT_RDX:%.*]] = or i1 [[FOUND_CONFLICT]], [[FOUND_CONFLICT11]]
+; CHECK-NEXT:    br i1 [[CONFLICT_RDX]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[VEC_IND13:%.*]] = phi <4 x i32> [ <i32 0, i32 1, i32 2, i32 3>, [[VECTOR_PH]] ], [ [[VEC_IND_NEXT14:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[VEC_IND15:%.*]] = phi <4 x i32> [ <i32 0, i32 1, i32 2, i32 3>, [[VECTOR_PH]] ], [ [[VEC_IND_NEXT16:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[PREDS]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP2]] to <4 x i32>*
+; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP3]], align 4, !alias.scope !12
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <4 x i32> [[WIDE_LOAD]], zeroinitializer
+; CHECK-NEXT:    [[TMP5:%.*]] = add nuw nsw <4 x i32> [[VEC_IND13]], <i32 1, i32 1, i32 1, i32 1>
+; CHECK-NEXT:    [[TMP6:%.*]] = select <4 x i1> [[TMP4]], <4 x i32> [[TMP5]], <4 x i32> [[VEC_IND15]]
+; CHECK-NEXT:    [[TMP7:%.*]] = zext <4 x i32> [[TMP6]] to <4 x i64>
+; CHECK-NEXT:    [[TMP8:%.*]] = extractelement <4 x i64> [[TMP7]], i32 0
+; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds float, float* [[BASE]], i64 [[TMP8]]
+; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <4 x i64> [[TMP7]], i32 1
+; CHECK-NEXT:    [[TMP11:%.*]] = getelementptr inbounds float, float* [[BASE]], i64 [[TMP10]]
+; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <4 x i64> [[TMP7]], i32 2
+; CHECK-NEXT:    [[TMP13:%.*]] = getelementptr inbounds float, float* [[BASE]], i64 [[TMP12]]
+; CHECK-NEXT:    [[TMP14:%.*]] = extractelement <4 x i64> [[TMP7]], i32 3
+; CHECK-NEXT:    [[TMP15:%.*]] = getelementptr inbounds float, float* [[BASE]], i64 [[TMP14]]
+; CHECK-NEXT:    [[TMP16:%.*]] = load float, float* [[TMP9]], align 4, !alias.scope !15
+; CHECK-NEXT:    [[TMP17:%.*]] = load float, float* [[TMP11]], align 4, !alias.scope !15
+; CHECK-NEXT:    [[TMP18:%.*]] = load float, float* [[TMP13]], align 4, !alias.scope !15
+; CHECK-NEXT:    [[TMP19:%.*]] = load float, float* [[TMP15]], align 4, !alias.scope !15
+; CHECK-NEXT:    [[TMP20:%.*]] = insertelement <4 x float> poison, float [[TMP16]], i32 0
+; CHECK-NEXT:    [[TMP21:%.*]] = insertelement <4 x float> [[TMP20]], float [[TMP17]], i32 1
+; CHECK-NEXT:    [[TMP22:%.*]] = insertelement <4 x float> [[TMP21]], float [[TMP18]], i32 2
+; CHECK-NEXT:    [[TMP23:%.*]] = insertelement <4 x float> [[TMP22]], float [[TMP19]], i32 3
+; CHECK-NEXT:    [[TMP24:%.*]] = getelementptr inbounds float, float* [[DEST]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP25:%.*]] = bitcast float* [[TMP24]] to <4 x float>*
+; CHECK-NEXT:    store <4 x float> [[TMP23]], <4 x float>* [[TMP25]], align 4, !alias.scope !17, !noalias !19
+; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
+; CHECK-NEXT:    [[VEC_IND_NEXT14]] = add <4 x i32> [[VEC_IND13]], <i32 4, i32 4, i32 4, i32 4>
+; CHECK-NEXT:    [[VEC_IND_NEXT16]] = add <4 x i32> [[VEC_IND15]], <i32 4, i32 4, i32 4, i32 4>
+; CHECK-NEXT:    [[TMP26:%.*]] = icmp eq i64 [[INDEX_NEXT]], 100
+; CHECK-NEXT:    br i1 [[TMP26]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP20:![0-9]+]]
+; CHECK:       middle.block:
+; CHECK-NEXT:    br i1 true, label [[FOR_COND_CLEANUP:%.*]], label [[SCALAR_PH]]
+; CHECK:       scalar.ph:
+; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 100, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[VECTOR_MEMCHECK]] ]
+; CHECK-NEXT:    [[BC_RESUME_VAL12:%.*]] = phi i32 [ 100, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY]] ], [ 0, [[VECTOR_MEMCHECK]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.cond.cleanup:
 ; CHECK-NEXT:    ret void
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[I_014:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[PREDS:%.*]], i64 [[INDVARS_IV]]
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
-; CHECK-NEXT:    [[CMP1_NOT:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[I_014:%.*]] = phi i32 [ [[BC_RESUME_VAL12]], [[SCALAR_PH]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[PREDS]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    [[TMP27:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[CMP1_NOT:%.*]] = icmp eq i32 [[TMP27]], 0
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[ADD]] = add nuw nsw i32 [[I_014]], 1
-; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32
-; CHECK-NEXT:    [[OFFSET_0:%.*]] = select i1 [[CMP1_NOT]], i32 [[ADD]], i32 [[TMP1]]
+; CHECK-NEXT:    [[TMP28:%.*]] = trunc i64 [[INDVARS_IV]] to i32
+; CHECK-NEXT:    [[OFFSET_0:%.*]] = select i1 [[CMP1_NOT]], i32 [[ADD]], i32 [[TMP28]]
 ; CHECK-NEXT:    [[IDXPROM213:%.*]] = zext i32 [[OFFSET_0]] to i64
-; CHECK-NEXT:    [[ARRAYIDX3:%.*]] = getelementptr inbounds float, float* [[BASE:%.*]], i64 [[IDXPROM213]]
-; CHECK-NEXT:    [[TMP2:%.*]] = load float, float* [[ARRAYIDX3]], align 4
-; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds float, float* [[DEST:%.*]], i64 [[INDVARS_IV]]
-; CHECK-NEXT:    store float [[TMP2]], float* [[ARRAYIDX5]], align 4
+; CHECK-NEXT:    [[ARRAYIDX3:%.*]] = getelementptr inbounds float, float* [[BASE]], i64 [[IDXPROM213]]
+; CHECK-NEXT:    [[TMP29:%.*]] = load float, float* [[ARRAYIDX3]], align 4
+; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds float, float* [[DEST]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store float [[TMP29]], float* [[ARRAYIDX5]], align 4
 ; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 100
-; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
+; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY]], !llvm.loop [[LOOP21:![0-9]+]]
 ;
 entry:
   br label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.body
   ret void
 
 for.body:                                         ; preds = %entry, %for.body