[LV] Apply sink-after & interleave-groups as VPlan transformations (NFC)

[gilr]

Summary

The sink-after and interleave-group vectorization decisions were so far applied to VPlan during initial VPlan construction, which complicates VPlan construction – also because of
their inter-dependence.
This patch refactors buildVPlanWithRecipes() to construct a simpler initial VPlan and later apply both these vectorization decisions, in order, as VPlan-to-VPlan
transformations.

[rengolin]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6472

Other try{something} functions return a recipe pointer, while this one returns a boolean.

If you rename this to "check" or "can" (instead of try), then you shouldn't clamp the range.

I'm not sure what's best here, but this way looks a bit odd.

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6472

Agreed. Will inline this code at call site instead.

[gilr]

• Applied review comment
• Simplified predicate lambda function

[rengolin]

So, IIUC, this is changing tryCreateRecipe to move the interleave recipe creation to the caller, buildVPlanWithVPRecipes. The dependencies with the sink values is recorded initially, then the plans are created, then the sinks are applied and, if any, the interleave groups.

The refactoring of VPRecipeBase make sense to me and the resulting code looks cleaner, but this doesn't look like an NFC change. Not that this is a bad thing, but I can't quite reach the conclusion that all the loops that would have been interleaved will continue to do so, because the order of the plans may change (for better or worse) the conditions in which the plan starts with.

Regardless, I think this is a positive change and goes in the direction we want the VPlan infrastructure to be. It also looks semantically equivalent (with the caveat above), so the change looks good to me.

It would be good to wait for further reviews on the next few days, just in case I missed something. I haven't looked at this code for a while, so that's very likely. :)

Thanks!

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6910

Update above comment: we no longer check for Interleave Groups widening recipe here, only Inductions and Phi nodes.

6911

This if (!Recipe) case and the next should be nested?

7048

Can retain the early-exiting "if (tryToCreateRecipe()) continue"?

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

53

receipes >> recipes

llvm/lib/Transforms/Vectorize/VPlan.cpp

117

Better place the implementation of removeFromParent() next to that of eraseFromParent() below.

284

Above comment suffices at header file only (and strictly speaking it's about Recipes rather than instructions).

Update Parent as done in insertBefore() above.

Should (existing) insertBefore() also assert !Parent before setting it?

llvm/lib/Transforms/Vectorize/VPlan.h

611

Better place removeFromParent() right before eraseFromParent() below, to emphasize that the latter (only) also deletes it.

[gilr]

In D68577#1701381, @rengolin wrote:

So, IIUC, this is changing tryCreateRecipe to move the interleave recipe creation to the caller, buildVPlanWithVPRecipes. The dependencies with the sink values is recorded initially, then the plans are created, then the sinks are applied and, if any, the interleave groups.

Correct. Motivation is to express these dependecies as VPlan transformation phase ordering. Ayal discussed this is more details in his 2017 VPlan talk.

... but this doesn't look like an NFC change. Not that this is a bad thing, but I can't quite reach the conclusion that all the loops that would have been interleaved will continue to do so, because the order of the plans may change (for better or worse) the conditions in which the plan starts with.
Regardless, I think this is a positive change and goes in the direction we want the VPlan infrastructure to be. It also looks semantically equivalent (with the caveat above), so the change looks good to me.
It would be good to wait for further reviews on the next few days, just in case I missed something.

Excellent. The intention is indeed to only change the way Planner executes these already-taken decisions (SA by Legal, IG by CostModel).
Thanks!

[gilr]

Applied review comments.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7071

Not sure how other feel, but I think it would be great if we could move this transform out of LoopVectorize.cpp , to group together VP2VP transforms. I think it would fit well into llvm/lib/Transforms/Vectorize/VPlanHCFGTransforms.h (although the name mentions HFCGTransforms, maybe it should be just VplanToVplanTransforms.h/cpp).

I could not spot anything that would prevent moving it to a different file on first glance.

[fhahn]

A while ago, I put up a patch to do sinking just on the VPInstruction/recipe level, but I never finished integrating it: D46826.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7079

This could just be Sink->moveAfter(RecipeBuilder.getRecipe(Entry.second)) . I've added it in D46825 and now finally have a reason to commit it ;)

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7071

This is currently still ingredient-based, i.e. not a pure VPlan2VPlan transformation, and as you mention the VPlan2VPlan part it's basically just a moveAfter(). A VPlan-based sinkAfter() should not be based on ingredients (as stated in D46826) and instead might take a Recipe2Recipe map., but that seems a bit of an overkill for this patch. Modelling VPlan-based transformations is definitely worth a larger discussion.

7079

Right. Will use it instead.
Seems it doesn't update Parent, though. Will rewrite as a composition of the more basic removeFromParent(), insertAfter() to avoid duplicating that and the assertions.

[gilr]

Applied review comments.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.cpp

288

nit: use Parent, as in insertBefore above.

[gilr]

Applied review comments.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7071

Sounds good to me, let's not overcomplicate things.

Yep, D46826 is still not really suitable here yet, which I only realised after accidentally submitting the comment here. Sorry for the confusion.

7079

Makes sense, thanks!

Originally I tried to mirror the implementation of Instruction::moveAfter, but it seems like it is only supposed to move instructions inside a basic block, although that's not really clear from the documentation.

llvm/lib/Transforms/Vectorize/VPlan.h

981

nit: it would be great to have a doc comment.

[gilr]

Applied review comments.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.h

981

While you're at it... worth adding that a full mask (potentially used by this recipe) is represented by nullptr, as well.

[gilr]

Applied review comments.
Reused VPWidenMemoryInstructionRecipe's new getMask() in its execute().

[gilr]

ping

[gilr]

Rebased.

[gilr]

Any other concern, guys?

[Ayal]

In D68577#1730054, @gilr wrote:

Any other concern, guys?

None from me.
@rengolin , @fhahn - ok to land?

[hsaito]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6909

I think the code here is easier to understand if written as

if ((Recipe = tryToWiden...())     ||
    (Recipe = tryToOptimize...()) ||
    (Recipe = tryToBlend())         ||
    (isa<PHINode()> && (Recipe = new VPWidenPHIRecipe())) {
    setRecipe(Instr, Recipe);
}

[rengolin]

In D68577#1730827, @Ayal wrote:

None from me.
@rengolin , @fhahn - ok to land?

None from me either. LGTM.

[fhahn]

LGTM, thanks for getting things started in that direction!

Just a few optional small nits.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6808

nit: could be changed to IsSingleton, to make it clearer we this is a boolean.

6979

nit: [r]ecipes?

6983

nit: [i]nstructions?

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

53

It may be worth mentioning the implicit contract: to mark a recipe for recording, the instruction needs to be added with a nullptr value.

57

maybe mention that we only record only if the instruction is already in the map.

[gilr]

Thanks everyone!

[gilr]

Addressed comments.

[bkramer]

This fails with asan: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/36343/steps/check-llvm%20asan/logs/stdio
Reverted in d3ec06d219788801380af1948c7f7ef9d3c6100b

==27731==ERROR: AddressSanitizer: heap-use-after-free on address 0x6060000300b0 at pc 0x000006bbd784 bp 0x7ffc45da9750 sp 0x7ffc45da9748
READ of size 8 at 0x6060000300b0 thread T0
    #0 0x6bbd783 in getInsertPos /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Analysis/VectorUtils.h:467:41
    #1 0x6bbd783 in operator() /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7082
    #2 0x6bbd783 in __invoke<(lambda at /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7080:20) &, unsigned int> /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/type_traits:3528
    #3 0x6bbd783 in __call<(lambda at /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7080:20) &, unsigned int> /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/__functional_base:317
    #4 0x6bbd783 in operator() /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/functional:1540
    #5 0x6bbd783 in std::__1::__function::__func<llvm::LoopVectorizationPlanner::buildVPlanWithVPRecipes(llvm::VFRange&, llvm::SmallPtrSetImpl<llvm::Value*>&, llvm::SmallPtrSetImpl<llvm::Instruction*>&)::$_31, std::__1::allocator<llvm::LoopVectorizationPlanner::buildVPlanWithVPRecipes(llvm::VFRange&, llvm::SmallPtrSetImpl<llvm::Value*>&, llvm::SmallPtrSetImpl<llvm::Instruction*>&)::$_31>, bool (unsigned int)>::operator()(unsigned int&&) /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/functional:1714
    #6 0x6b8232b in operator() /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/functional:1867:16
    #7 0x6b8232b in operator() /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/functional:2473
    #8 0x6b8232b in getDecisionAndClampRange /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:6617
    #9 0x6b8232b in llvm::LoopVectorizationPlanner::buildVPlanWithVPRecipes(llvm::VFRange&, llvm::SmallPtrSetImpl<llvm::Value*>&, llvm::SmallPtrSetImpl<llvm::Instruction*>&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7085
    #10 0x6b74387 in llvm::LoopVectorizationPlanner::buildVPlansWithVPRecipes(unsigned int, unsigned int) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7043:9
    #11 0x6b71f01 in llvm::LoopVectorizationPlanner::plan(unsigned int) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:6453:5
    #12 0x6b912b1 in llvm::LoopVectorizePass::processLoop(llvm::Loop*) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7623:47
    #13 0x6b9baa8 in llvm::LoopVectorizePass::runImpl(llvm::Function&, llvm::ScalarEvolution&, llvm::LoopInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::BlockFrequencyInfo&, llvm::TargetLibraryInfo*, llvm::DemandedBits&, llvm::AAResults&, llvm::AssumptionCache&, std::__1::function<llvm::LoopAccessInfo const& (llvm::Loop&)>&, llvm::OptimizationRemarkEmitter&, llvm::ProfileSummaryInfo*) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7843:16
    #14 0x6ba7c92 in (anonymous namespace)::LoopVectorize::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:1617:17
    #15 0x52d7953 in llvm::FPPassManager::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1481:27
    #16 0x52d8132 in llvm::FPPassManager::runOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1517:16
    #17 0x52d8fad in runOnModule /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1582:27
    #18 0x52d8fad in llvm::legacy::PassManagerImpl::run(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1694
    #19 0xafbff4 in main /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/opt/opt.cpp:890:12
    #20 0x7f5ecce0a2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #21 0x9e53e9 in _start (/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/opt+0x9e53e9)

0x6060000300b0 is located 48 bytes inside of 56-byte region [0x606000030080,0x6060000300b8)
freed by thread T0 here:
    #0 0xaa9bd8 in operator delete(void*) /b/sanitizer-x86_64-linux-fast/build/llvm-project/compiler-rt/lib/asan/asan_new_delete.cc:166
    #1 0x6b73274 in llvm::InterleavedAccessInfo::reset() /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Analysis/VectorUtils.h:550:7
    #2 0x6b7239b in llvm::LoopVectorizationPlanner::plan(unsigned int) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:6444:23
    #3 0x6b912b1 in llvm::LoopVectorizePass::processLoop(llvm::Loop*) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7623:47
    #4 0x6b9baa8 in llvm::LoopVectorizePass::runImpl(llvm::Function&, llvm::ScalarEvolution&, llvm::LoopInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::BlockFrequencyInfo&, llvm::TargetLibraryInfo*, llvm::DemandedBits&, llvm::AAResults&, llvm::AssumptionCache&, std::__1::function<llvm::LoopAccessInfo const& (llvm::Loop&)>&, llvm::OptimizationRemarkEmitter&, llvm::ProfileSummaryInfo*) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7843:16
    #5 0x6ba7c92 in (anonymous namespace)::LoopVectorize::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:1617:17
    #6 0x52d7953 in llvm::FPPassManager::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1481:27
    #7 0x52d8132 in llvm::FPPassManager::runOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1517:16
    #8 0x52d8fad in runOnModule /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1582:27
    #9 0x52d8fad in llvm::legacy::PassManagerImpl::run(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1694
    #10 0xafbff4 in main /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/opt/opt.cpp:890:12
    #11 0x7f5ecce0a2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)

previously allocated by thread T0 here:
    #0 0xaa9198 in operator new(unsigned long) /b/sanitizer-x86_64-linux-fast/build/llvm-project/compiler-rt/lib/asan/asan_new_delete.cc:105
    #1 0x434e673 in llvm::InterleavedAccessInfo::createInterleaveGroup(llvm::Instruction*, int, llvm::Align) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Analysis/VectorUtils.h:643:9
    #2 0x434b4d9 in llvm::InterleavedAccessInfo::analyzeInterleaving(bool) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Analysis/VectorUtils.cpp:930:17
    #3 0x6b90a71 in llvm::LoopVectorizePass::processLoop(llvm::Loop*) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7608:9
    #4 0x6b9baa8 in llvm::LoopVectorizePass::runImpl(llvm::Function&, llvm::ScalarEvolution&, llvm::LoopInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::BlockFrequencyInfo&, llvm::TargetLibraryInfo*, llvm::DemandedBits&, llvm::AAResults&, llvm::AssumptionCache&, std::__1::function<llvm::LoopAccessInfo const& (llvm::Loop&)>&, llvm::OptimizationRemarkEmitter&, llvm::ProfileSummaryInfo*) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7843:16
    #5 0x6ba7c92 in (anonymous namespace)::LoopVectorize::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:1617:17
    #6 0x52d7953 in llvm::FPPassManager::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1481:27
    #7 0x52d8132 in llvm::FPPassManager::runOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1517:16
    #8 0x52d8fad in runOnModule /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1582:27
    #9 0x52d8fad in llvm::legacy::PassManagerImpl::run(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1694
    #10 0xafbff4 in main /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/opt/opt.cpp:890:12
    #11 0x7f5ecce0a2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)

[gilr]

In D68577#1732352, @bkramer wrote:

This fails with asan: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/36343/steps/check-llvm%20asan/logs/stdio
Reverted in d3ec06d219788801380af1948c7f7ef9d3c6100b

Fail was due to a bug in IAI whose reset() method was not clearing the set holding pointers to the interleave groups being deleted, uncovered by this patch's use of the set. Patch recommited as 100e797adb433724a17c9b42b6533cd634cb796b with a fix to reset().
Thanks Benjamin!

[rtrieu]

The recommited patch is hitting an assert. See message and reduced test case below:

assertion failed at llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h:91 in llvm::VPRecipeBase *llvm::VPRecipeBuilder::getRecipe(llvm::Instruction *): Ingredient2Recipe[I] != nullptr && "Ingredient doesn't have a recipe"

"clang" \
"-cc1" \
"-triple" "x86_64-unknown-linux-gnu" \
"-emit-obj" \
"-O3" \
"-w" \
"-vectorize-loops" \
"-x" "c" "test.c"

int test(int I1, int *Arr1, int *Arr2) {
  int i = 0, j = 0;
  int I2 = 0;
  
  int ret = 0;
                          
  for (i = 0; i < 5; i++) {
    if ((Arr1[i] < 5)) {
      I2 = I1;
    }
  } 

  for (i = 0; i < I2; i++, j++) {
    Arr2[3] = (j < I1 ? Arr1[j] : 0);
  }         
  if (j < I1) {
    ret = 1;
  }
        
  return ret;
}

[tianqing]

In D68577#1736452, @rtrieu wrote:

The recommited patch is hitting an assert. See message and reduced test case below:

assertion failed at llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h:91 in llvm::VPRecipeBase *llvm::VPRecipeBuilder::getRecipe(llvm::Instruction *): Ingredient2Recipe[I] != nullptr && "Ingredient doesn't have a recipe"

I've got a similar crash. My case is a little bit simpler:

#include <stdio.h>

void find(int *data) {
    char t = 0; // changing char to int won't trigger the crash
    for (int i = 789; i > 0; i--)
        t = t || (data[i] == 42); // note the short circuit of OR
    if (t) // removing this conditional won't trigger the crash
      printf("some string");
}

This compiles to (under clang++ -O3):

define dso_local void @_Z4findPi(i32* nocapture readonly %0) local_unnamed_addr #0 {
  br label %4

2:                                                ; preds = %11
  %3 = phi i1 [ %12, %11 ]
  br i1 %3, label %16, label %18

4:                                                ; preds = %11, %1
  %5 = phi i64 [ 789, %1 ], [ %13, %11 ]
  %6 = phi i1 [ true, %1 ], [ %15, %11 ]
  br i1 %6, label %7, label %11

7:                                                ; preds = %4
  %8 = getelementptr inbounds i32, i32* %0, i64 %5
  %9 = load i32, i32* %8, align 4, !tbaa !2
  %10 = icmp eq i32 %9, 42
  br label %11

11:                                               ; preds = %4, %7
  %12 = phi i1 [ true, %4 ], [ %10, %7 ]
  %13 = add nsw i64 %5, -1
  %14 = icmp eq i64 %13, 0
  %15 = xor i1 %12, true
  br i1 %14, label %2, label %4

16:                                               ; preds = %2
  %17 = tail call i32 (i8*, ...) @printf(i8* nonnull dereferenceable(1) getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0))
  br label %18

18:                                               ; preds = %2, %16
  ret void
}

It identifies "br i1 %6, label %7, label %11" as sinkable and tries to sink it.

[tianqing]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7043

Previously we have this conditional guard against sinking of certain instructions so the problem got hidden. The real problem should be in IVDescriptors.cpp:RecurrenceDescriptor::isFirstOrderRecurrence(). Probably it's better to allow only a whitelist of arithmetic opcodes.

Please note there is another discussion https://reviews.llvm.org/D69228 going on with that function.

[fhahn]

Gil, I can put a patch up for not sinking past terminators in OVDescriptor, as I am already working on patches in that area.

I’d also suggest to land the removeFromParent & co changes separately from the other changes in the patch.

[gilr]

In D68577#1738622, @fhahn wrote:

Gil, I can put a patch up for not sinking past terminators in OVDescriptor, as I am already working on patches in that area.

I’d also suggest to land the removeFromParent & co changes separately from the other changes in the patch.

Ah, sorry, recommitted before noticing this comment :(
Also added a LIT based on @rtrieu's test case (thanks @rtrieu, @echristo, @tianqing!)

[efriedma]

I'm seeing a new failure with this patch: http://lab.llvm.org:8011/builders/aosp-O3-polly-before-vectorizer-unprofitable/builds/1128 . Crash log below. Please let me know if you need me to come up with a testcase.

`
FAILED: out/target/product/angler/obj/EXECUTABLES/tcpdump_intermediates/tcpdump.o 
/bin/bash -c "PWD=/proc/self/cwd ulimit -t 240; llvm.inst/bin/clang 	-I external/tcpdump -I out/target/product/angler/obj/EXECUTABLES/tcpdump_intermediates -I out/target/product/angler/gen/EXECUTABLES/tcpdump_intermediates -I libnativehelper/include/nativehelper \$(cat out/target/product/angler/obj/EXECUTABLES/tcpdump_intermediates/import_includes)  -I system/core/include -I system/media/audio/include -I hardware/libhardware/include -I hardware/libhardware_legacy/include -I hardware/ril/include -I libnativehelper/include -I frameworks/native/include -I frameworks/native/opengl/include -isystem frameworks/av/include -isystem out/target/product/angler/obj/include -isystem device/huawei/angler/kernel-headers -isystem hardware/qcom/msm8994/kernel-headers -isystem bionic/libc/arch-arm64/include -isystem bionic/libc/include -isystem bionic/libc/kernel/uapi -isystem bionic/libc/kernel/uapi/asm-arm64 -isystem bionic/libc/kernel/android/uapi -c  -fno-exceptions -Wno-multichar -fno-strict-aliasing -fstack-protector-strong -ffunction-sections -fdata-sections -funwind-tables -Wa,--noexecstack -Werror=format-security -D_FORTIFY_SOURCE=2 -fno-short-enums -no-canonical-prefixes -Werror=pointer-to-int-cast -Werror=int-to-pointer-cast -Werror=implicit-function-declaration -DNDEBUG -O2 -g -Wstrict-aliasing=2 -DANDROID -fmessage-length=0 -W -Wall -Wno-unused -Winit-self -Wpointer-arith -DNDEBUG -UDEBUG -fdebug-prefix-map=/proc/self/cwd= -D__compiler_offsetof=__builtin_offsetof -Werror=int-conversion -Wno-reserved-id-macro -Wno-format-pedantic -Wno-unused-command-line-argument -fcolor-diagnostics -Wno-expansion-to-defined -Werror=return-type -Werror=non-virtual-dtor -Werror=address -Werror=sequence-point -Werror=date-time -nostdlibinc -mcpu=cortex-a53 -target aarch64-linux-android -Bprebuilts/gcc/linux-x86/aarch64/aarch64-linux-android-4.9/aarch64-linux-android/bin   -std=gnu99    -D_BSD_SOURCE -DHAVE_CONFIG_H -D_U_=\"__attribute__((unused))\" -Werror -fpie -D_USING_LIBCXX   -Werror=int-to-pointer-cast -Werror=pointer-to-int-cast -Werror=address-of-temporary -Werror=return-type -Wno-error -O3 -mllvm -polly -mllvm -polly-position=before-vectorizer -mllvm -polly-process-unprofitable -MD -MF out/target/product/angler/obj/EXECUTABLES/tcpdump_intermediates/tcpdump.d -o out/target/product/angler/obj/EXECUTABLES/tcpdump_intermediates/tcpdump.o external/tcpdump/tcpdump.c"
clang: /var/lib/buildbot/slaves/hexagon-build-03/aosp/llvm.src/llvm/include/llvm/Support/Casting.h:264: typename cast_retty<X, Y *>::ret_type llvm::cast(Y *) [X = llvm::VPWidenMemoryInstructionRecipe, Y = llvm::VPRecipeBase]: Assertion `isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.
Stack dump:
0.	Program arguments: llvm.inst/bin/clang -cc1 -triple aarch64-unknown-linux-android -emit-obj -mnoexecstack -disable-free -main-file-name tcpdump.c -mrelocation-model pic -pic-level 1 -pic-is-pie -mthread-model posix -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu cortex-a53 -target-feature +fp-armv8 -target-feature +neon -target-feature +crc -target-feature +crypto -target-feature +sha2 -target-feature +aes -target-abi aapcs -mllvm -aarch64-fix-cortex-a53-835769=1 -fallow-half-arguments-and-returns -dwarf-column-info -debug-info-kind=limited -dwarf-version=4 -debugger-tuning=gdb -ffunction-sections -fdata-sections -nostdsysteminc -resource-dir llvm.inst/lib/clang/10.0.0 -dependency-file out/target/product/angler/obj/EXECUTABLES/tcpdump_intermediates/tcpdump.d -MT out/target/product/angler/obj/EXECUTABLES/tcpdump_intermediates/tcpdump.o -sys-header-deps -isystem frameworks/av/include -isystem out/target/product/angler/obj/include -isystem device/huawei/angler/kernel-headers -isystem hardware/qcom/msm8994/kernel-headers -isystem bionic/libc/arch-arm64/include -isystem bionic/libc/include -isystem bionic/libc/kernel/uapi -isystem bionic/libc/kernel/uapi/asm-arm64 -isystem bionic/libc/kernel/android/uapi -I external/tcpdump -I out/target/product/angler/obj/EXECUTABLES/tcpdump_intermediates -I out/target/product/angler/gen/EXECUTABLES/tcpdump_intermediates -I libnativehelper/include/nativehelper -I external/boringssl/src/include -I external/boringssl/src/include -I external/boringssl/src/include -I external/libpcap -I external/libcxx/include -I external/libcxxabi/include -I system/core/include -I system/media/audio/include -I hardware/libhardware/include -I hardware/libhardware_legacy/include -I hardware/ril/include -I libnativehelper/include -I frameworks/native/include -I frameworks/native/opengl/include -D _FORTIFY_SOURCE=2 -D NDEBUG -D ANDROID -D NDEBUG -U DEBUG -D __compiler_offsetof=__builtin_offsetof -D _BSD_SOURCE -D HAVE_CONFIG_H -D _U_=__attribute__((unused)) -D _USING_LIBCXX -internal-isystem llvm.inst/lib/clang/10.0.0/include -O3 -Wno-multichar -Werror=format-security -Werror=pointer-to-int-cast -Werror=int-to-pointer-cast -Werror=implicit-function-declaration -Wstrict-aliasing=2 -W -Wall -Wno-unused -Winit-self -Wpointer-arith -Werror=int-conversion -Wno-reserved-id-macro -Wno-format-pedantic -Wno-unused-command-line-argument -Wno-expansion-to-defined -Werror=return-type -Werror=non-virtual-dtor -Werror=address -Werror=sequence-point -Werror=date-time -Werror -Werror=int-to-pointer-cast -Werror=pointer-to-int-cast -Werror=address-of-temporary -Werror=return-type -Wno-error -std=gnu99 -fdebug-compilation-dir /var/lib/buildbot/slaves/hexagon-build-03/aosp -fdebug-prefix-map=/proc/self/cwd= -ferror-limit 19 -fmessage-length 0 -stack-protector 2 -fno-signed-char -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -fcolor-diagnostics -vectorize-loops -vectorize-slp -mllvm -polly -mllvm -polly-position=before-vectorizer -mllvm -polly-process-unprofitable -o out/target/product/angler/obj/EXECUTABLES/tcpdump_intermediates/tcpdump.o -x c external/tcpdump/tcpdump.c 
1.	<eof> parser at end of file
2.	Per-module optimization passes
3.	Running pass 'Function Pass Manager' on module 'external/tcpdump/tcpdump.c'.
4.	Running pass 'Loop Vectorization' on function '@lookup_ndo_printer'
 #0 0x00000000019a2684 PrintStackTraceSignalHandler(void*) (llvm.inst/bin/clang+0x19a2684)
 #1 0x00000000019a02de llvm::sys::RunSignalHandlers() (llvm.inst/bin/clang+0x19a02de)
 #2 0x00000000019a2aa8 SignalHandler(int) (llvm.inst/bin/clang+0x19a2aa8)
 #3 0x00007f370a6ccd10 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10d10)
 #4 0x00007f37095b9267 raise /build/buildd/glibc-2.21/signal/../sysdeps/unix/sysv/linux/raise.c:55:0
 #5 0x00007f37095baeca abort /build/buildd/glibc-2.21/stdlib/abort.c:91:0
 #6 0x00007f37095b203d __assert_fail_base /build/buildd/glibc-2.21/assert/assert.c:92:0
 #7 0x00007f37095b20f2 (/lib/x86_64-linux-gnu/libc.so.6+0x2e0f2)
 #8 0x0000000001adbe07 llvm::LoopVectorizationPlanner::buildVPlanWithVPRecipes(llvm::VFRange&, llvm::SmallPtrSetImpl<llvm::Value*>&, llvm::SmallPtrSetImpl<llvm::Instruction*>&) (llvm.inst/bin/clang+0x1adbe07)
 #9 0x0000000001ad5f5f llvm::LoopVectorizationPlanner::buildVPlansWithVPRecipes(unsigned int, unsigned int) (llvm.inst/bin/clang+0x1ad5f5f)
#10 0x0000000001ad57c2 llvm::LoopVectorizationPlanner::plan(unsigned int) (llvm.inst/bin/clang+0x1ad57c2)
#11 0x0000000001adfd4b llvm::LoopVectorizePass::processLoop(llvm::Loop*) (llvm.inst/bin/clang+0x1adfd4b)
#12 0x0000000001ae2ba4 llvm::LoopVectorizePass::runImpl(llvm::Function&, llvm::ScalarEvolution&, llvm::LoopInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::BlockFrequencyInfo&, llvm::TargetLibraryInfo*, llvm::DemandedBits&, llvm::AAResults&, llvm::AssumptionCache&, std::__1::function<llvm::LoopAccessInfo const& (llvm::Loop&)>&, llvm::OptimizationRemarkEmitter&, llvm::ProfileSummaryInfo*) (llvm.inst/bin/clang+0x1ae2ba4)
#13 0x0000000001ae6813 (anonymous namespace)::LoopVectorize::runOnFunction(llvm::Function&) (llvm.inst/bin/clang+0x1ae6813)
#14 0x0000000001402eb3 llvm::FPPassManager::runOnFunction(llvm::Function&) (llvm.inst/bin/clang+0x1402eb3)
#15 0x0000000001403198 llvm::FPPassManager::runOnModule(llvm::Module&) (llvm.inst/bin/clang+0x1403198)
#16 0x0000000001403696 llvm::legacy::PassManagerImpl::run(llvm::Module&) (llvm.inst/bin/clang+0x1403696)
#17 0x0000000001b7d310 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::__1::unique_ptr<llvm::raw_pwrite_stream, std::__1::default_delete<llvm::raw_pwrite_stream> >) (llvm.inst/bin/clang+0x1b7d310)
#18 0x00000000027a9c84 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (llvm.inst/bin/clang+0x27a9c84)
#19 0x0000000002e90cf3 clang::ParseAST(clang::Sema&, bool, bool) (llvm.inst/bin/clang+0x2e90cf3)
#20 0x00000000020c2480 clang::FrontendAction::Execute() (llvm.inst/bin/clang+0x20c2480)
#21 0x0000000002061698 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (llvm.inst/bin/clang+0x2061698)
#22 0x000000000216b03d clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (llvm.inst/bin/clang+0x216b03d)
#23 0x000000000094091f cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (llvm.inst/bin/clang+0x94091f)
#24 0x000000000093e3b1 main (llvm.inst/bin/clang+0x93e3b1)
#25 0x00007f37095a4a40 __libc_start_main /build/buildd/glibc-2.21/csu/libc-start.c:323:0
#26 0x000000000093b649 _start (llvm.inst/bin/clang+0x93b649)
clang: error: unable to execute command: Aborted (core dumped)
clang: error: clang frontend command failed due to signal (use -v to see invocation)
clang version 10.0.0 (/var/lib/buildbot/slaves/hexagon-build-03/aosp/llvm.src/clang e25bc5e0247141cb31093a370e22fe3249bdbb05)
Target: aarch64-unknown-linux-android
Thread model: posix
InstalledDir: llvm.inst/bin
clang: note: diagnostic msg: PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
clang: note: diagnostic msg: 
********************

`

[gilr]

In D68577#1739177, @efriedma wrote:

Please let me know if you need me to come up with a testcase.

That would be great. Thanks Eli!

[efriedma]

Testcase follows; reproduce with opt -loop-vectorize:

target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-unknown-linux-android"

%0 = type { i32 ()*, i32 }

@0 = internal unnamed_addr constant [59 x %0] [%0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 {i32 ()* null, i32 258}, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer, %0 zeroinitializer, %0 zeroinitializer,
%0 zeroinitializer], align 8

define dso_local void @lookup_ndo_printer(i32 %arg) {
bb1:
  br label %bb2

bb2:
  %tmp = phi %0* [ %tmp6, %bb2 ], [ getelementptr inbounds ([59 x %0], [59 x %0]* @0, i64 0, i64 0), %bb1 ]
  %tmp3 = getelementptr inbounds %0, %0* %tmp, i64 0, i32 1
  %tmp4 = load i32, i32* %tmp3, align 8
  %tmp5 = icmp eq i32 %tmp4, 258
  %tmp6 = getelementptr inbounds %0, %0* %tmp, i64 1
  br i1 %tmp5, label %bb65, label %bb2

bb65:
  unreachable
}

[Ayal]

In D68577#1739605, @efriedma wrote:

Testcase follows; reproduce with opt -loop-vectorize:

[snip]

This testcase is similar to PR40816, where a load from an array of constants feeds the compare of the loop's latch, allowing SCEV to determine the loop's trip count by looking at these constants. In this case there's a discrepancy between vectorizing such a load as an interleave group due to its strided access pattern, and scalarizing it due to being UniformAfterVectorization (see https://reviews.llvm.org/D68831#inline-627725). To be consistent with the previous behavior (of vectorizing), willWiden above should succeed if the Decision is CM_Interleave, even if the instruction isScalarAfterVectorization().

TODO notes for separate follow-up non-NFC patches:

1. It's probably better to (consistently) scalarize such cases, or even identify them as DeadInstructions, rather than vectorize them w/ or w/o an interleave group.
2. Such loops can and should be optimized to have a simple induction variable with constant trip count regardless of (and prior to) LV.

[gilr]

In D68577#1739605, @efriedma wrote:

Testcase follows; reproduce with opt -loop-vectorize:

Thanks Eli!
Patch recommitted with a fix and a lit based on this testcase.

[efriedma]

In D68577#1739971, @Ayal wrote:

1. Such loops can and should be optimized to have a simple induction variable with constant trip count regardless of (and prior to) LV.

indvars does this transform. That said, it only runs once; in some cases, we manage to simplify the loop after indvars runs. Maybe it makes sense to run indvars again? We'd want to measure how much it actually triggers in practice.

[Ayal]

In D68577#1741190, @efriedma wrote:

In D68577#1739971, @Ayal wrote:

1. Such loops can and should be optimized to have a simple induction variable with constant trip count regardless of (and prior to) LV.

indvars does this transform. That said, it only runs once; in some cases, we manage to simplify the loop after indvars runs. Maybe it makes sense to run indvars again? We'd want to measure how much it actually triggers in practice.

Indeed indvars takes care of the testcase provided in https://reviews.llvm.org/D68577#1739605, leaving nothing to be vectorized. It does not handle the testcase of PR40816, though, presumably because of the store inside its loop (which prevents IndVarSimplify::PredicateLoopExits() from succeeding). Perhaps indvars should be extented to convert any loop to use a simple canonical IV whenever SCEV can compute its trip count.
Running indvars before LV might also relieve the latter from having to take care of live outs that are IV's.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

class LoopVectorizationPlanner {
   const TargetTransformInfo *TTI;
 
   /// The legality analysis.
   LoopVectorizationLegality *Legal;
 
   /// The profitability analysis.
   LoopVectorizationCostModel &CM;
 
+  /// The interleaved access analysis.
+  InterleavedAccessInfo &IAI;
+
   SmallVector<VPlanPtr, 4> VPlans;
 
   /// This class is used to enable the VPlan to invoke a method of ILV. This is
   /// needed until the method is refactored out of ILV and becomes reusable.
   struct VPCallbackILV : public VPCallback {
     InnerLoopVectorizer &ILV;
 
     VPCallbackILV(InnerLoopVectorizer &ILV) : ILV(ILV) {}
 
     Value *getOrCreateVectorValues(Value *V, unsigned Part) override;
   };
 
   /// A builder used to construct the current plan.
   VPBuilder Builder;
 
   unsigned BestVF = 0;
   unsigned BestUF = 0;
 
 public:
   LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
                            const TargetTransformInfo *TTI,
                            LoopVectorizationLegality *Legal,
-                           LoopVectorizationCostModel &CM)
-      : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM) {}
+                           LoopVectorizationCostModel &CM,
+                           InterleavedAccessInfo &IAI)
+      : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM),
+        IAI(IAI) {}
 
   /// Plan how to best vectorize, return the best VF and its cost, or None if
   /// vectorization and interleaving should be avoided up front.
   Optional<VectorizationFactor> plan(unsigned UserVF);
 
   /// Use the VPlan-native path to plan how to best vectorize, return the best
   /// VF and its cost.
   VectorizationFactor planInVPlanNativePath(unsigned UserVF);

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

for (auto &Induction : *Legal->getInductionVars()) {
     // of the respective phi node. Any other casts in the induction def-use chain
     // have no other uses outside the phi update chain, and will be ignored.
     InductionDescriptor &IndDes = Induction.second;
     const SmallVectorImpl<Instruction *> &Casts = IndDes.getCastInsts();
     DeadInstructions.insert(Casts.begin(), Casts.end());
   }
 }
 
 Value *InnerLoopUnroller::reverseVector(Value *Vec) { return Vec; }
 
 Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) { return V; }
 
 Value *InnerLoopUnroller::getStepVector(Value *Val, int StartIdx, Value *Step,
                                         Instruction::BinaryOps BinOp) {
   // When unrolling and the VF is 1, we only need to add a simple scalar.
   Type *Ty = Val->getType();
   assert(!Ty->isVectorTy() && "Val must be a scalar");
for (auto *Predecessor : predecessors(BB)) {
     }
 
     BlockMask = Builder.createOr(BlockMask, EdgeMask);
   }
 
   return BlockMaskCache[BB] = BlockMask;
 }
 
-VPInterleaveRecipe *VPRecipeBuilder::tryToInterleaveMemory(Instruction *I,
-                                                           VFRange &Range,
-                                                           VPlanPtr &Plan) {
-  const InterleaveGroup<Instruction> *IG = CM.getInterleavedAccessGroup(I);
-  if (!IG)
-    return nullptr;
-
-  // Now check if IG is relevant for VF's in the given range.
-  auto isIGMember = [&](Instruction *I) -> std::function<bool(unsigned)> {
-    return [=](unsigned VF) -> bool {
-      return (VF >= 2 && // Query is illegal for VF == 1
-              CM.getWideningDecision(I, VF) ==
-                  LoopVectorizationCostModel::CM_Interleave);
-    };
-  };
-  if (!LoopVectorizationPlanner::getDecisionAndClampRange(isIGMember(I), Range))
-    return nullptr;
-
-  // I is a member of an InterleaveGroup for VF's in the (possibly trimmed)
-  // range. If it's the primary member of the IG construct a VPInterleaveRecipe.
-  // Otherwise, it's an adjunct member of the IG, do not construct any Recipe.
-  assert(I == IG->getInsertPos() &&
-         "Generating a recipe for an adjunct member of an interleave group");
-
-  VPValue *Mask = nullptr;
-  if (Legal->isMaskRequired(I))
-    Mask = createBlockInMask(I->getParent(), Plan);
-
-  return new VPInterleaveRecipe(IG, Mask);
-}
-
 VPWidenMemoryInstructionRecipe *
 VPRecipeBuilder::tryToWidenMemory(Instruction *I, VFRange &Range,
                                   VPlanPtr &Plan) {
   if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
     return nullptr;
 
   auto willWiden = [&](unsigned VF) -> bool {
     if (VF == 1)
       return false;
     if (CM.isScalarAfterVectorization(I, VF) ||
         CM.isProfitableToScalarize(I, VF))
       return false;
     LoopVectorizationCostModel::InstWidening Decision =
         CM.getWideningDecision(I, VF);
     assert(Decision != LoopVectorizationCostModel::CM_Unknown &&
            "CM decision should be taken at this point.");
-    assert(Decision != LoopVectorizationCostModel::CM_Interleave &&
-           "Interleave memory opportunity should be caught earlier.");
     return Decision != LoopVectorizationCostModel::CM_Scalarize;
   };
 
   if (!LoopVectorizationPlanner::getDecisionAndClampRange(willWiden, Range))
     return nullptr;
 
   VPValue *Mask = nullptr;
   if (Legal->isMaskRequired(I))
if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
       return false;
     }
     return true;
   };
 
   if (!LoopVectorizationPlanner::getDecisionAndClampRange(willWiden, Range))
     return false;
 
+  // If this ingredient's recipe is to be recorded, keep its recipe a singleton
+  // to avoid having to split recipes later.
+  bool Singleton = Ingredient2Recipe.count(I);
+
   // Success: widen this instruction. We optimize the common case where
   // consecutive instructions can be represented by a single recipe.
-  if (!VPBB->empty()) {
-    VPWidenRecipe *LastWidenRecipe = dyn_cast<VPWidenRecipe>(&VPBB->back());
-    if (LastWidenRecipe && LastWidenRecipe->appendInstruction(I))
-      return true;
-  }
+  if (!Singleton && !VPBB->empty() && LastExtensibleRecipe == &VPBB->back() &&
+      LastExtensibleRecipe->appendInstruction(I))
 
-  VPBB->appendRecipe(new VPWidenRecipe(I));
+  VPWidenRecipe *WidenRecipe = new VPWidenRecipe(I);
+  if (!Singleton)
+    LastExtensibleRecipe = WidenRecipe;
+  setRecipe(I, WidenRecipe);
+  VPBB->appendRecipe(WidenRecipe);
   return true;
 }
 
 VPBasicBlock *VPRecipeBuilder::handleReplication(
     Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
     DenseMap<Instruction *, VPReplicateRecipe *> &PredInst2Recipe,
     VPlanPtr &Plan) {
   bool IsUniform = LoopVectorizationPlanner::getDecisionAndClampRange(
       [&](unsigned VF) { return CM.isUniformAfterVectorization(I, VF); },
       Range);
 
   bool IsPredicated = LoopVectorizationPlanner::getDecisionAndClampRange(
       [&](unsigned VF) { return CM.isScalarWithPredication(I, VF); }, Range);
 
   auto *Recipe = new VPReplicateRecipe(I, IsUniform, IsPredicated);
+  setRecipe(I, Recipe);
 
   // Find if I uses a predicated instruction. If so, it will use its scalar
   // value. Avoid hoisting the insert-element which packs the scalar value into
   // a vector value, as that happens iff all users use the vector value.
   for (auto &Op : I->operands())
     if (auto *PredInst = dyn_cast<Instruction>(Op))
       if (PredInst2Recipe.find(PredInst) != PredInst2Recipe.end())
         PredInst2Recipe[PredInst]->setAlsoPack(false);
VPRegionBlock *VPRecipeBuilder::createReplicateRegion(Instruction *Instr,
   VPBlockUtils::connectBlocks(Pred, Exit);
 
   return Region;
 }
 
 bool VPRecipeBuilder::tryToCreateRecipe(Instruction *Instr, VFRange &Range,
                                         VPlanPtr &Plan, VPBasicBlock *VPBB) {
   VPRecipeBase *Recipe = nullptr;
-  // Check if Instr should belong to an interleave memory recipe, or already
-  // does. In the latter case Instr is irrelevant.
-  if ((Recipe = tryToInterleaveMemory(Instr, Range, Plan))) {
-    VPBB->appendRecipe(Recipe);
-    return true;
-  }
 
-  // Check if Instr is a memory operation that should be widened.
-  if ((Recipe = tryToWidenMemory(Instr, Range, Plan))) {
-    VPBB->appendRecipe(Recipe);
-    return true;
-  }
+  // First, check for specific widening recipes that deal with memory
+  // operations, inductions and Phi nodes.
+  if (!(Recipe = tryToWidenMemory(Instr, Range, Plan)) &&
+      !(Recipe = tryToOptimizeInduction(Instr, Range)) &&
+      !(Recipe = tryToBlend(Instr, Plan)) &&
+      isa<PHINode>(Instr))
+    Recipe = new VPWidenPHIRecipe(cast<PHINode>(Instr));
 
-  // Check if Instr should form some PHI recipe.
-  if ((Recipe = tryToOptimizeInduction(Instr, Range))) {
+  if (Recipe) {
+    setRecipe(Instr, Recipe);
     VPBB->appendRecipe(Recipe);
     return true;
   }
-  if ((Recipe = tryToBlend(Instr, Plan))) {
-    VPBB->appendRecipe(Recipe);
-    return true;
-  }
-  if (PHINode *Phi = dyn_cast<PHINode>(Instr)) {
-    VPBB->appendRecipe(new VPWidenPHIRecipe(Phi));
-    return true;
-  }
 
-  // Check if Instr is to be widened by a general VPWidenRecipe, after
-  // having first checked for specific widening recipes that deal with
-  // Interleave Groups, Inductions and Phi nodes.
+  // Check if Instr is to be widened by a general VPWidenRecipe.
   if (tryToWiden(Instr, VPBB, Range))
     return true;
 
   return false;
 }
 
 void LoopVectorizationPlanner::buildVPlansWithVPRecipes(unsigned MinVF,
                                                         unsigned MaxVF) {
   assert(OrigLoop->empty() && "Inner loop expected.");
VPlans.push_back(
         buildVPlanWithVPRecipes(SubRange, NeedDef, DeadInstructions));
     VF = SubRange.End;
   }
 }
 
 VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
     VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
     SmallPtrSetImpl<Instruction *> &DeadInstructions) {
+
   // Hold a mapping from predicated instructions to their recipes, in order to
   // fix their AlsoPack behavior if a user is determined to replicate and use a
   // scalar instead of vector value.
   DenseMap<Instruction *, VPReplicateRecipe *> PredInst2Recipe;
 
   DenseMap<Instruction *, Instruction *> &SinkAfter = Legal->getSinkAfter();
-  DenseMap<Instruction *, Instruction *> SinkAfterInverse;
+
+  SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
+
+  VPRecipeBuilder RecipeBuilder(OrigLoop, TLI, Legal, CM, Builder);
+
+  // ---------------------------------------------------------------------------
+  // Pre-construction: record ingredients whose Recipes we'll need to further
+  // process after constructing the initial VPlan.
+  // ---------------------------------------------------------------------------
+
+  // Mark Instructions we'll need to sink later and their targets as
+  // ingredients whose Recipe we'll need to record.
+  for (auto &Entry : SinkAfter) {
+    RecipeBuilder.recordRecipeOf(Entry.first);
+    RecipeBuilder.recordRecipeOf(Entry.second);
+  }
+
+  // For each interleave group which is relevant for this (possibly trimmed)
+  // Range, add it to the set of groups to be later applied to the VPlan and add
+  // placeholders for its members' Recipes which we'll be replacing with a
+  // single VPInterleaveRecipe.
+  for (InterleaveGroup<Instruction> *IG : IAI.getInterleaveGroups()) {
+    auto applyIG = [IG, this](unsigned VF) -> bool {
+      return (VF >= 2 && // Query is illegal for VF == 1
+              CM.getWideningDecision(IG->getInsertPos(), VF) ==
+                  LoopVectorizationCostModel::CM_Interleave);
+    };
+    if (!getDecisionAndClampRange(applyIG, Range))
+      continue;
+    InterleaveGroups.insert(IG);
+    for (unsigned i = 0; i < IG->getFactor(); i++)
+      if (Instruction *Member = IG->getMember(i))
+        RecipeBuilder.recordRecipeOf(Member);
+  };
+
+  // ---------------------------------------------------------------------------
+  // Build initial VPlan: Scan the body of the loop in a topological order to
+  // visit each basic block after having visited its predecessor basic blocks.
+  // ---------------------------------------------------------------------------
 
   // Create a dummy pre-entry VPBasicBlock to start building the VPlan.
   VPBasicBlock *VPBB = new VPBasicBlock("Pre-Entry");
   auto Plan = std::make_unique<VPlan>(VPBB);
 
-  VPRecipeBuilder RecipeBuilder(OrigLoop, TLI, Legal, CM, Builder);
   // Represent values that will have defs inside VPlan.
   for (Value *V : NeedDef)
     Plan->addVPValue(V);
 
   // Scan the body of the loop in a topological order to visit each basic block
   // after having visited its predecessor basic blocks.
   LoopBlocksDFS DFS(OrigLoop);
   DFS.perform(LI);
 
   for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO())) {
     // Relevant instructions from basic block BB will be grouped into VPRecipe
     // ingredients and fill a new VPBasicBlock.
     unsigned VPBBsForBB = 0;
     auto *FirstVPBBForBB = new VPBasicBlock(BB->getName());
     VPBlockUtils::insertBlockAfter(FirstVPBBForBB, VPBB);
     VPBB = FirstVPBBForBB;
     Builder.setInsertPoint(VPBB);
 
     std::vector<Instruction *> Ingredients;
 
-    // Organize the ingredients to vectorize from current basic block in the
-    // right order.
+    // Introduce each ingredient into VPlan.
     for (Instruction &I : BB->instructionsWithoutDebug()) {
       Instruction *Instr = &I;
 
       // First filter out irrelevant instructions, to ensure no recipes are
       // built for them.
       if (isa<BranchInst>(Instr) ||
           DeadInstructions.find(Instr) != DeadInstructions.end())
         continue;
 
-      // I is a member of an InterleaveGroup for Range.Start. If it's an adjunct
-      // member of the IG, do not construct any Recipe for it.
-      const InterleaveGroup<Instruction> *IG =
-          CM.getInterleavedAccessGroup(Instr);
-      if (IG && Instr != IG->getInsertPos() &&
-          Range.Start >= 2 && // Query is illegal for VF == 1
-          CM.getWideningDecision(Instr, Range.Start) ==
-              LoopVectorizationCostModel::CM_Interleave) {
-        auto SinkCandidate = SinkAfterInverse.find(Instr);
-        if (SinkCandidate != SinkAfterInverse.end())
-          Ingredients.push_back(SinkCandidate->second);
-        continue;
-      }
-
-      // Move instructions to handle first-order recurrences, step 1: avoid
-      // handling this instruction until after we've handled the instruction it
-      // should follow.
-      auto SAIt = SinkAfter.find(Instr);
-      if (SAIt != SinkAfter.end()) {
-        LLVM_DEBUG(dbgs() << "Sinking" << *SAIt->first << " after"
-                          << *SAIt->second
-                          << " to vectorize a 1st order recurrence.\n");
-        SinkAfterInverse[SAIt->second] = Instr;
-        continue;
-      }
-
-      Ingredients.push_back(Instr);
-
-      // Move instructions to handle first-order recurrences, step 2: push the
-      // instruction to be sunk at its insertion point.
-      auto SAInvIt = SinkAfterInverse.find(Instr);
-      if (SAInvIt != SinkAfterInverse.end())
-        Ingredients.push_back(SAInvIt->second);
-    }
-
-    // Introduce each ingredient into VPlan.
-    for (Instruction *Instr : Ingredients) {
       if (RecipeBuilder.tryToCreateRecipe(Instr, Range, Plan, VPBB))
         continue;
 
       // Otherwise, if all widening options failed, Instruction is to be
       // replicated. This may create a successor for VPBB.
       VPBasicBlock *NextVPBB = RecipeBuilder.handleReplication(
           Instr, Range, VPBB, PredInst2Recipe, Plan);
       if (NextVPBB != VPBB) {
         VPBB = NextVPBB;
         VPBB->setName(BB->hasName() ? BB->getName() + "." + Twine(VPBBsForBB++)
                                     : "");
       }
     }
   }
 
   // Discard empty dummy pre-entry VPBasicBlock. Note that other VPBasicBlocks
   // may also be empty, such as the last one VPBB, reflecting original
   // basic-blocks with no recipes.
   VPBasicBlock *PreEntry = cast<VPBasicBlock>(Plan->getEntry());
   assert(PreEntry->empty() && "Expecting empty pre-entry block.");
   VPBlockBase *Entry = Plan->setEntry(PreEntry->getSingleSuccessor());
   VPBlockUtils::disconnectBlocks(PreEntry, Entry);
   delete PreEntry;
 
+  // ---------------------------------------------------------------------------
+  // Transform initial VPlan: Apply previously taken decisions, in order, to
+  // bring the VPlan to its final state.
+  // ---------------------------------------------------------------------------
+
+  // Apply Sink-After legal constraints.
+  for (auto &Entry : SinkAfter) {
+    VPRecipeBase *Sink = RecipeBuilder.getRecipe(Entry.first);
+    Sink->removeFromParent();
+    Sink->insertAfter(RecipeBuilder.getRecipe(Entry.second));
+  }
+
+  // Interleave memory: for each Interleave Group we marked earlier as relevant
+  // for this VPlan, replace the Recipes widening its memory instructions with a
+  // single VPInterleaveRecipe at its insertion point.
+  for (auto IG : InterleaveGroups) {
+    auto *Recipe = cast<VPWidenMemoryInstructionRecipe>(
+        RecipeBuilder.getRecipe(IG->getInsertPos()));
+    (new VPInterleaveRecipe(IG, Recipe->getMask()))->insertBefore(Recipe);
+
+    for (unsigned i = 0; i < IG->getFactor(); ++i)
+      if (Instruction *Member = IG->getMember(i)) {
+        RecipeBuilder.getRecipe(Member)->eraseFromParent();
+      }
+  }
+
   // Finally, if tail is folded by masking, introduce selects between the phi
   // and the live-out instruction of each reduction, at the end of the latch.
   if (CM.foldTailByMasking()) {
     Builder.setInsertPoint(VPBB);
     auto *Cond = RecipeBuilder.createBlockInMask(OrigLoop->getHeader(), Plan);
     for (auto &Reduction : *Legal->getReductionVars()) {
       VPValue *Phi = Plan->getVPValue(Reduction.first);
       VPValue *Red = Plan->getVPValue(Reduction.second.getLoopExitInstr());
static bool processLoopInVPlanNativePath(
   InterleavedAccessInfo IAI(PSE, L, DT, LI, LVL->getLAI());
   ScalarEpilogueLowering SEL = getScalarEpilogueLowering(F, L, Hints, PSI, BFI);
 
   LoopVectorizationCostModel CM(SEL, L, PSE, LI, LVL, *TTI, TLI, DB, AC, ORE, F,
                                 &Hints, IAI);
   // Use the planner for outer loop vectorization.
   // TODO: CM is not used at this point inside the planner. Turn CM into an
   // optional argument if we don't need it in the future.
-  LoopVectorizationPlanner LVP(L, LI, TLI, TTI, LVL, CM);
+  LoopVectorizationPlanner LVP(L, LI, TLI, TTI, LVL, CM, IAI);
 
   // Get user vectorization factor.
   const unsigned UserVF = Hints.getWidth();
 
   // Plan how to best vectorize, return the best VF and its cost.
   const VectorizationFactor VF = LVP.planInVPlanNativePath(UserVF);
 
   // If we are stress testing VPlan builds, do not attempt to generate vector
#endif /* NDEBUG */
   }
 
   // Use the cost model.
   LoopVectorizationCostModel CM(SEL, L, PSE, LI, &LVL, *TTI, TLI, DB, AC, ORE,
                                 F, &Hints, IAI);
   CM.collectValuesToIgnore();
 
   // Use the planner for vectorization.
-  LoopVectorizationPlanner LVP(L, LI, TLI, TTI, &LVL, CM);
+  LoopVectorizationPlanner LVP(L, LI, TLI, TTI, &LVL, CM, IAI);
 
   // Get user vectorization factor.
   unsigned UserVF = Hints.getWidth();
 
   // Plan how to best vectorize, return the best VF and its cost.
   Optional<VectorizationFactor> MaybeVF = LVP.plan(UserVF);
 
   VectorizationFactor VF = VectorizationFactor::Disabled();

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

class VPRecipeBuilder {
   /// if-conversion currently takes place during VPlan-construction, so these
   /// caches are only used at that stage.
   using EdgeMaskCacheTy =
       DenseMap<std::pair<BasicBlock *, BasicBlock *>, VPValue *>;
   using BlockMaskCacheTy = DenseMap<BasicBlock *, VPValue *>;
   EdgeMaskCacheTy EdgeMaskCache;
   BlockMaskCacheTy BlockMaskCache;
 
+  // VPlan-VPlan transformations support: Hold a mapping from ingredients to
+  // their recipe. To save on memory, only do so for selected ingredients. If
+  // those ingredients get a VPWidenRecipe, also avoid compressing other
+  // ingredients into it to avoid having to split such recipes later.
+  DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
+  VPWidenRecipe *LastExtensibleRecipe = nullptr;
+
+  /// Set the recipe created for given ingredient.
+  void setRecipe(Instruction *I, VPRecipeBase *R) {
+    if (!Ingredient2Recipe.count(I))
+      return;
+    assert(Ingredient2Recipe[I] == nullptr &&
+           "Recipe already set for ingredient");
+    Ingredient2Recipe[I] = R;
+  }
+
 public:
   /// A helper function that computes the predicate of the block BB, assuming
   /// that the header block of the loop is set to True. It returns the *entry*
   /// mask for the block BB.
   VPValue *createBlockInMask(BasicBlock *BB, VPlanPtr &Plan);
 
   /// A helper function that computes the predicate of the edge between SRC
   /// and DST.
   VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlanPtr &Plan);
 
-  /// Check if \I belongs to an Interleave Group within the given VF \p Range,
-  /// \return true in the first returned value if so and false otherwise.
-  /// Build a new VPInterleaveGroup Recipe if \I is the primary member of an IG
-  /// for \p Range.Start, and provide it as the second returned value.
-  /// Note that if \I is an adjunct member of an IG for \p Range.Start, the
-  /// \return value is <true, nullptr>, as it is handled by another recipe.
-  /// \p Range.End may be decreased to ensure same decision from \p Range.Start
-  /// to \p Range.End.
-  VPInterleaveRecipe *tryToInterleaveMemory(Instruction *I, VFRange &Range,
-                                            VPlanPtr &Plan);
+  /// Mark given ingredient for recording its recipe once one is created for
+  /// it.
+  void recordRecipeOf(Instruction *I) {
+    assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
+           "Recipe already set for ingredient");
+    Ingredient2Recipe[I] = nullptr;
+  }
+
+  /// Return the recipe created for given ingredient.
+  VPRecipeBase *getRecipe(Instruction *I) {
+    assert(Ingredient2Recipe.count(I) &&
+           "Recording this ingredients recipe was not requested");
+    assert(Ingredient2Recipe[I] != nullptr &&
+           "Ingredient doesn't have a recipe");
+    return Ingredient2Recipe[I];
+  }
 
   /// Check if \I is a memory instruction to be widened for \p Range.Start and
   /// potentially masked. Such instructions are handled by a recipe that takes
   /// an additional VPInstruction for the mask.
   VPWidenMemoryInstructionRecipe *
   tryToWidenMemory(Instruction *I, VFRange &Range, VPlanPtr &Plan);
 
   /// Check if an induction recipe should be constructed for \I within the given

llvm/lib/Transforms/Vectorize/VPlan.h

bool isLegalToHoistInto() {
     return true;
   }
 };
 
 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
 /// instructions.
 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
   friend VPBasicBlock;
+  friend class VPBlockUtils;
 
 private:
   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
 
   /// Each VPRecipe belongs to a single VPBasicBlock.
   VPBasicBlock *Parent = nullptr;
 
 public:
public:
 
   /// \return the VPBasicBlock which this VPRecipe belongs to.
   VPBasicBlock *getParent() { return Parent; }
   const VPBasicBlock *getParent() const { return Parent; }
 
   /// The method which generates the output IR instructions that correspond to
   /// this VPRecipe, thereby "executing" the VPlan.
   virtual void execute(struct VPTransformState &State) = 0;
 
   /// Each recipe prints itself.
   virtual void print(raw_ostream &O, const Twine &Indent) const = 0;
 
   /// Insert an unlinked recipe into a basic block immediately before
   /// the specified recipe.
   void insertBefore(VPRecipeBase *InsertPos);
 
+  /// Insert an unlinked Recipe into a basic block immediately after
+  /// the specified Recipe.
+  void insertAfter(VPRecipeBase *InsertPos);
+
+  /// This method unlinks 'this' from the containing basic block, but does not
+  /// delete it.
+  void removeFromParent();
+
   /// This method unlinks 'this' from the containing basic block and deletes it.
   ///
   /// \returns an iterator pointing to the element after the erased one
   iplist<VPRecipeBase>::iterator eraseFromParent();
 };
 
 /// This is a concrete Recipe that models a single VPlan-level instruction.
 /// While as any Recipe it may generate a sequence of IR instructions when
if (Mask) // Create a VPInstruction to register as a user of the mask.
       User.reset(new VPUser({Mask}));
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
   }
 
+  VPValue *getMask() {
+    // Mask is the last operand.
+    return User ? User->getOperand(User->getNumOperands() - 1) : nullptr;
+  }
+
   /// Generate the wide load/store.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent) const override;
 };
 
 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
   for (VPBlockBase *Block : Blocks)
     delete Block;
 }
 
 BasicBlock *
 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
   // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
   // Pred stands for Predessor. Prev stands for Previous - last visited/created.
   BasicBlock *PrevBB = CFG.PrevBB;
   BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
                                          PrevBB->getParent(), CFG.LastBB);
   LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
 
   // Hook up the new basic block to its predecessors.
   for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
     VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
     auto &PredVPSuccessors = PredVPBB->getSuccessors();
for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
     }
   }
 
   // Exit replicating mode.
   State->Instance.reset();
 }
 
 void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
+  assert(!Parent && "Recipe already in some VPBasicBlock");
   Parent = InsertPos->getParent();
   Parent->getRecipeList().insert(InsertPos->getIterator(), this);
 }
 
+void VPRecipeBase::insertAfter(VPRecipeBase *InsertPos) {
+  assert(!Parent && "Recipe already in some VPBasicBlock");
+  Parent = InsertPos->getParent();
+  InsertPos->getParent()->getRecipeList().insertAfter(InsertPos->getIterator(),
+                                                      this);
+}
+
+void VPRecipeBase::removeFromParent() {
+  getParent()->getRecipeList().remove(getIterator());
+  Parent = nullptr;
+}
+
 iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
   return getParent()->getRecipeList().erase(getIterator());
 }
 
 void VPInstruction::generateInstruction(VPTransformState &State,
                                         unsigned Part) {
   IRBuilder<> &Builder = State.Builder;