[VPlan] Unify Value2VPValue and VPExternalDefs maps (NFCI).

[fhahn]

Summary

Before this patch, a VPlan contained 2 mappings for Values -> VPValue:

1. Value2VPValue and 2) VPExternalDefs.

This duplication is unnecessary and there are already cases where
external defs are added to Value2VPValue. This patch replaces all uses
of VPExternalDefs with Value2VPValue.

It clarifies the naming of getOrAddVPValue (to getOrAddExternalVPValue)
and addVPValue (to addExternalVPValue).

At the moment, this is NFC, but will enable additional simplifications
in D147783.

Depends on D147891.

[Ayal]

This indeed deserves cleaning up!
Would it be correct and reasonable to rename "External[Def]" >> "LiveIn[VPValue]" throughout, as in !hasDefiningRecipe()?
Value2VPValueEnabled presumably applies to recipe'd VPValues only, i.e., excluding live-in VPValues? Better decrease allowed overriding cases, rather than increase them.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8150

nit (Independent of this patch): assert seems redundant - getOrAdd*() cannot return null?

8879

nit (Independent of this patch): should this case add a

// FIXME: Should not rely on getVPValue at this point.

referring to D108573?

10481

Explain why override is allowed? Add above FIXME?

llvm/lib/Transforms/Vectorize/VPlan.h

2252

Still only to remember whom to destroy? Worth retaining ToFree suffix?

2256

For live-ins/external-defs, the mapping is always intact?

Perhaps distinguish between getting a VPValue which may be a recipe, for which the mapping will become stale, and getting-or-adding a live-in VPValue?

2333

Note that addVPValue(Value*, VPValue*) remains intact, it is only addVPValue(Value*) which is renamed addExternalVPValue(Value*) below, as the former adds recipe VPValues whereas the latter adds live-in ones.

2343

Note that getVPValue() remains intact, used to retrieve both live-ins and recipe VPValues, although if used to retrieve live-ins it should disregard Value2VPValueEnabled - the obvious case being constants checked below.

2353

This adds a live-in, so indeed should be enabled always, regardless of Value2VPValueEnabled; although currently addVPValue(Value*) which adds a live-in does check Value2VPValueEnabled.

2364

getOrAddExternalVPValue() deals with live-in VPValues only, why should it consider Value2VPValueEnabled?

2365

Indeed, VPV must not have a defining recipe when expecting to get a live-in/external VPValue.

[fhahn]

In D147892#4265819, @Ayal wrote:

This indeed deserves cleaning up!
Would it be correct and reasonable to rename "External[Def]" >> "LiveIn[VPValue]" throughout, as in !hasDefiningRecipe()?

Update, thanks!

Value2VPValueEnabled presumably applies to recipe'd VPValues only, i.e., excluding live-in VPValues? Better decrease allowed overriding cases, rather than increase them.

I updated the exsting asserts to allow querying and adding live-ins regardless of Value2VPValueEnabled and consolidated the functions.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8150

Yeah, I can remove it separately.

8879

Update the code, the new getVPValueOrAddLiveIn only doesn't require the parameter, as live-ins can be added regardless.

10481

Update getOrAddLiveIn to be allowed generally.

llvm/lib/Transforms/Vectorize/VPlan.h

2252

Retained, thanks!

2256

Agreed, updated to always allow querying and adding live-ins.

2333

addExternalVPValue has been removed and addVPValue(Value*, VPValue*) has been updated to also handle the live-in case in the assert

2343

Updated to allow retrieving live-ins in the assert.

2353

This is gone now.

2364

Removed assert and renamed getVPValueOrAddLiveIn and updated the code to use existing addVPValue and getVPValue

[Ayal]

Looks good to me, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

2334–2335

nit: an isLiveIn() method may be clearer than these !getDefiningRecipe()'s.

2342

Retain documentation of \p OverrideAllowed?

[thurston]

(Repost from github)

This patch appears to cause a heap-use-after-free e.g., https://lab.llvm.org/buildbot/#/builders/239/builds/1843/steps/14/logs/stdio:

FAIL: LLVM :: Transforms/LoopVectorize/SystemZ/pr38110.ll (57359 of 71288)
******************** TEST 'LLVM :: Transforms/LoopVectorize/SystemZ/pr38110.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm_build_asan/bin/opt -passes='loop-vectorize' -mcpu=z13 -force-vector-width=2 -S < /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/test/Transforms/LoopVectorize/SystemZ/pr38110.ll | /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm_build_asan/bin/FileCheck /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/test/Transforms/LoopVectorize/SystemZ/pr38110.ll
--
Exit Code: 2
Command Output (stderr):
--
=================================================================
==932340==ERROR: AddressSanitizer: heap-use-after-free on address 0x50e000000b50 at pc 0xaaaacf039884 bp 0xffffca0e3220 sp 0xffffca0e3218
READ of size 8 at 0x50e000000b50 thread T0
    #0 0xaaaacf039880 in llvm::VPValue::getDefiningRecipe() /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/VPlan.cpp:117:37
    #1 0xaaaacef5cda4 in llvm::VPlan::getVPValue(llvm::Value*, bool) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/VPlan.h:2346:5
    #2 0xaaaacef5a7c4 in llvm::InnerLoopVectorizer::truncateToMinimalBitwidths(llvm::VPTransformState&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:3611:32
    #3 0xaaaacef5d648 in llvm::InnerLoopVectorizer::fixVectorizedLoop(llvm::VPTransformState&, llvm::VPlan&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:3739:5
    #4 0xaaaacefaf0e4 in llvm::LoopVectorizationPlanner::executePlan(llvm::ElementCount, unsigned int, llvm::VPlan&, llvm::InnerLoopVectorizer&, llvm::DominatorTree*, bool) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7802:7
    #5 0xaaaacefe67c8 in llvm::LoopVectorizePass::processLoop(llvm::Loop*) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:10496:13
    #6 0xaaaaceff4028 in llvm::LoopVectorizePass::runImpl(llvm::Function&, llvm::ScalarEvolution&, llvm::LoopInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::DemandedBits&, llvm::AssumptionCache&, llvm::LoopAccessInfoManager&, llvm::OptimizationRemarkEmitter&, llvm::ProfileSummaryInfo*) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:10593:30
    #7 0xaaaaceff5440 in llvm::LoopVectorizePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:10626:9
    #8 0xaaaacd88aaa8 in llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/include/llvm/IR/PassManager.h:517:40
    #9 0xaaaacd896838 in llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/IR/PassManager.cpp:124:38
    #10 0xaaaacd888284 in llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/include/llvm/IR/PassManager.h:517:40
    #11 0xaaaac851509c in llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/tools/opt/NewPMDriver.cpp:522:7
    #12 0xaaaac85446c4 in main /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/tools/opt/opt.cpp:701:12
    #13 0xffff92e373f8  (/lib/aarch64-linux-gnu/libc.so.6+0x273f8) (BuildId: f37f3aa07c797e333fd106472898d361f71798f5)
    #14 0xffff92e374c8 in __libc_start_main (/lib/aarch64-linux-gnu/libc.so.6+0x274c8) (BuildId: f37f3aa07c797e333fd106472898d361f71798f5)
    #15 0xaaaac842bb6c in _start (/b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm_build_asan/bin/opt+0x7f6bb6c)

[fhahn]

In D147892#4274496, @thurston wrote:

(Repost from github)

This patch appears to cause a heap-use-after-free e.g., https://lab.llvm.org/buildbot/#/builders/239/builds/1843/steps/14/logs/stdio:

FAIL: LLVM :: Transforms/LoopVectorize/SystemZ/pr38110.ll (57359 of 71288)
******************** TEST 'LLVM :: Transforms/LoopVectorize/SystemZ/pr38110.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm_build_asan/bin/opt -passes='loop-vectorize' -mcpu=z13 -force-vector-width=2 -S < /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/test/Transforms/LoopVectorize/SystemZ/pr38110.ll | /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm_build_asan/bin/FileCheck /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/test/Transforms/LoopVectorize/SystemZ/pr38110.ll
--
Exit Code: 2
Command Output (stderr):
--
=================================================================
==932340==ERROR: AddressSanitizer: heap-use-after-free on address 0x50e000000b50 at pc 0xaaaacf039884 bp 0xffffca0e3220 sp 0xffffca0e3218
READ of size 8 at 0x50e000000b50 thread T0
    #0 0xaaaacf039880 in llvm::VPValue::getDefiningRecipe() /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/VPlan.cpp:117:37
    #1 0xaaaacef5cda4 in llvm::VPlan::getVPValue(llvm::Value*, bool) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/VPlan.h:2346:5
    #2 0xaaaacef5a7c4 in llvm::InnerLoopVectorizer::truncateToMinimalBitwidths(llvm::VPTransformState&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:3611:32
    #3 0xaaaacef5d648 in llvm::InnerLoopVectorizer::fixVectorizedLoop(llvm::VPTransformState&, llvm::VPlan&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:3739:5
    #4 0xaaaacefaf0e4 in llvm::LoopVectorizationPlanner::executePlan(llvm::ElementCount, unsigned int, llvm::VPlan&, llvm::InnerLoopVectorizer&, llvm::DominatorTree*, bool) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:7802:7
    #5 0xaaaacefe67c8 in llvm::LoopVectorizePass::processLoop(llvm::Loop*) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:10496:13
    #6 0xaaaaceff4028 in llvm::LoopVectorizePass::runImpl(llvm::Function&, llvm::ScalarEvolution&, llvm::LoopInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::DemandedBits&, llvm::AssumptionCache&, llvm::LoopAccessInfoManager&, llvm::OptimizationRemarkEmitter&, llvm::ProfileSummaryInfo*) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:10593:30
    #7 0xaaaaceff5440 in llvm::LoopVectorizePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:10626:9
    #8 0xaaaacd88aaa8 in llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/include/llvm/IR/PassManager.h:517:40
    #9 0xaaaacd896838 in llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/lib/IR/PassManager.cpp:124:38
    #10 0xaaaacd888284 in llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/include/llvm/IR/PassManager.h:517:40
    #11 0xaaaac851509c in llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/tools/opt/NewPMDriver.cpp:522:7
    #12 0xaaaac85446c4 in main /b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm-project/llvm/tools/opt/opt.cpp:701:12
    #13 0xffff92e373f8  (/lib/aarch64-linux-gnu/libc.so.6+0x273f8) (BuildId: f37f3aa07c797e333fd106472898d361f71798f5)
    #14 0xffff92e374c8 in __libc_start_main (/lib/aarch64-linux-gnu/libc.so.6+0x274c8) (BuildId: f37f3aa07c797e333fd106472898d361f71798f5)
    #15 0xaaaac842bb6c in _start (/b/sanitizer-aarch64-linux-bootstrap-asan/build/llvm_build_asan/bin/opt+0x7f6bb6c)

Thanks for the revert, should be fixed by adjusting the order of the conditions in the assert in VPValue in the recommitted version.

[fhahn]

Recommitted as ff0ec4f42ea0

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

2334–2335

Done in 3157f03a349cfc852cdd994675eaa9652caa2e3a, thanks!

[thurston]

Thank you Florian! :-)

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (!BI->isConditional() || BI->getSuccessor(0) == BI->getSuccessor(1))
     return EdgeMaskCache[Edge] = SrcMask;
 
   // If source is an exiting block, we know the exit edge is dynamically dead
   // in the vector loop, and thus we don't need to restrict the mask.  Avoid
   // adding uses of an otherwise potentially dead instruction.
   if (OrigLoop->isLoopExiting(Src))
     return EdgeMaskCache[Edge] = SrcMask;
 
-  VPValue *EdgeMask = Plan.getOrAddVPValue(BI->getCondition());
+  VPValue *EdgeMask = Plan.getVPValueOrAddLiveIn(BI->getCondition());
   assert(EdgeMask && "No Edge Mask found for condition");
 
   if (BI->getSuccessor(0) != Dst)
     EdgeMask = Builder.createNot(EdgeMask, BI->getDebugLoc());
 
   if (SrcMask) { // Otherwise block in-mask is all-one, no need to AND.
     // The condition is 'SrcMask && EdgeMask', which is equivalent to
     // 'select i1 SrcMask, i1 EdgeMask, i1 false'.
     // The select version does not introduce new UB if SrcMask is false and
     // EdgeMask is poison. Using 'and' here introduces undefined behavior.
-    VPValue *False = Plan.getOrAddVPValue(
+    VPValue *False = Plan.getVPValueOrAddLiveIn(
         ConstantInt::getFalse(BI->getCondition()->getType()));
     EdgeMask =
         Builder.createSelect(SrcMask, EdgeMask, False, BI->getDebugLoc());
   }
 
   return EdgeMaskCache[Edge] = EdgeMask;
 }
 
auto isOptimizableIVTruncate =
     };
   };
 
   if (LoopVectorizationPlanner::getDecisionAndClampRange(
           isOptimizableIVTruncate(I), Range)) {
 
     auto *Phi = cast<PHINode>(I->getOperand(0));
     const InductionDescriptor &II = *Legal->getIntOrFpInductionDescriptor(Phi);
-    VPValue *Start = Plan.getOrAddVPValue(II.getStartValue());
+    VPValue *Start = Plan.getVPValueOrAddLiveIn(II.getStartValue());
     return createWidenInductionRecipes(Phi, I, Start, II, CM, Plan,
                                        *PSE.getSE(), *OrigLoop, Range);
   }
   return nullptr;
 }
 
 VPRecipeOrVPValueTy VPRecipeBuilder::tryToBlend(PHINode *Phi,
                                                 ArrayRef<VPValue *> Operands,
if (NeedsMask) {
       //      tail-folding, and we use the appropriate mask for the block.
       //   2) No mask is required for the block, but the only available
       //      vector variant at this VF requires a mask, so we synthesize an
       //      all-true mask.
       VPValue *Mask = nullptr;
       if (Legal->isMaskRequired(CI))
         Mask = createBlockInMask(CI->getParent(), *Plan);
       else
-        Mask = Plan->getOrAddVPValue(ConstantInt::getTrue(
+        Mask = Plan->getVPValueOrAddLiveIn(ConstantInt::getTrue(
             IntegerType::getInt1Ty(Variant->getFunctionType()->getContext())));
 
       VFShape Shape = VFShape::get(*CI, VariantVF, /*HasGlobalPred=*/true);
       unsigned MaskPos = 0;
 
       for (VFInfo Info : VFDatabase::getMappings(*CI))
         if (Info.Shape == Shape) {
           assert(Info.isMasked() && "Vector function info shape mismatch");
VPRecipeBase *VPRecipeBuilder::tryToWiden(Instruction *I,
   case Instruction::UDiv:
   case Instruction::SRem:
   case Instruction::URem: {
     // If not provably safe, use a select to form a safe divisor before widening the
     // div/rem operation itself.  Otherwise fall through to general handling below.
     if (CM.isPredicatedInst(I)) {
       SmallVector<VPValue *> Ops(Operands.begin(), Operands.end());
       VPValue *Mask = createBlockInMask(I->getParent(), *Plan);
-      VPValue *One =
-        Plan->getOrAddExternalDef(ConstantInt::get(I->getType(), 1u, false));
+      VPValue *One = Plan->getVPValueOrAddLiveIn(
+          ConstantInt::get(I->getType(), 1u, false));
       auto *SafeRHS =
          new VPInstruction(Instruction::Select, {Mask, Ops[1], One},
                            I->getDebugLoc());
       VPBB->appendRecipe(SafeRHS);
       Ops[1] = SafeRHS;
       return new VPWidenRecipe(*I, make_range(Ops.begin(), Ops.end()));
     }
     LLVM_FALLTHROUGH;
void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
   }
 }
 
 // Add the necessary canonical IV and branch recipes required to control the
 // loop.
 static void addCanonicalIVRecipes(VPlan &Plan, Type *IdxTy, DebugLoc DL,
                                   TailFoldingStyle Style) {
   Value *StartIdx = ConstantInt::get(IdxTy, 0);
-  auto *StartV = Plan.getOrAddVPValue(StartIdx);
+  auto *StartV = Plan.getVPValueOrAddLiveIn(StartIdx);
 
   // Add a VPCanonicalIVPHIRecipe starting at 0 to the header.
   auto *CanonicalIVPHI = new VPCanonicalIVPHIRecipe(StartV, DL);
   VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
   VPBasicBlock *Header = TopRegion->getEntryBasicBlock();
   Header->insert(CanonicalIVPHI, Header->begin());
 
   // Add a CanonicalIVIncrement{NUW} VPInstruction to increment the scalar
static void addUsersInExitBlock(VPBasicBlock *HeaderVPBB,
   // Only handle single-exit loops with unique exit blocks for now.
   if (!ExitBB || !ExitBB->getSinglePredecessor() || !ExitingBB)
     return;
 
   // Introduce VPUsers modeling the exit values.
   for (PHINode &ExitPhi : ExitBB->phis()) {
     Value *IncomingValue =
         ExitPhi.getIncomingValueForBlock(ExitingBB);
-    VPValue *V = Plan.getOrAddVPValue(IncomingValue, true);
+    VPValue *V = Plan.getVPValueOrAddLiveIn(IncomingValue);
     Plan.addLiveOut(&ExitPhi, V);
   }
 }
 
 std::optional<VPlanPtr> LoopVectorizationPlanner::tryToBuildVPlanWithVPRecipes(
     VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions) {
 
   SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
for (Instruction &I : BB->instructionsWithoutDebug(false)) {
       // First filter out irrelevant instructions, to ensure no recipes are
       // built for them.
       if (isa<BranchInst>(Instr) || DeadInstructions.count(Instr))
         continue;
 
       SmallVector<VPValue *, 4> Operands;
       auto *Phi = dyn_cast<PHINode>(Instr);
       if (Phi && Phi->getParent() == OrigLoop->getHeader()) {
-        Operands.push_back(Plan->getOrAddVPValue(
+        Operands.push_back(Plan->getVPValueOrAddLiveIn(
             Phi->getIncomingValueForBlock(OrigLoop->getLoopPreheader())));
       } else {
         auto OpRange = Plan->mapToVPValues(Instr->operands());
         Operands = {OpRange.begin(), OpRange.end()};
       }
 
       // Invariant stores inside loop will be deleted and a single store
       // with the final reduction value will be added to the exit block
if (!VectorizeLoop) {
               IndPhi = WidenInd->getPHINode();
               ID = &WidenInd->getInductionDescriptor();
             }
 
             ResumeV = MainILV.createInductionResumeValue(
                 IndPhi, *ID, {EPI.MainLoopIterationCountCheck});
           }
           assert(ResumeV && "Must have a resume value");
-          VPValue *StartVal = BestEpiPlan.getOrAddExternalDef(ResumeV);
+          VPValue *StartVal = BestEpiPlan.getVPValueOrAddLiveIn(ResumeV);
           cast<VPHeaderPHIRecipe>(&R)->setStartValue(StartVal);
         }
 
         LVP.executePlan(EPI.EpilogueVF, EPI.EpilogueUF, BestEpiPlan, EpilogILV,
                         DT, true);
         ++LoopsEpilogueVectorized;
 
         if (!MainILV.areSafetyChecksAdded())
           DisableRuntimeUnroll = true;

llvm/lib/Transforms/Vectorize/VPlan.h

class VPlan {
 
   /// Holds the UFs applicable to this VPlan. If empty, the VPlan is valid for
   /// any UF.
   SmallSetVector<unsigned, 2> UFs;
 
   /// Holds the name of the VPlan, for printing.
   std::string Name;
 
-  /// Holds all the external definitions created for this VPlan. External
-  /// definitions must be immutable and hold a pointer to their underlying IR.
-  DenseMap<Value *, VPValue *> VPExternalDefs;
-
   /// Represents the trip count of the original loop, for folding
   /// the tail.
   VPValue *TripCount = nullptr;
 
   /// Represents the backedge taken count of the original loop, for folding
   /// the tail. It equals TripCount - 1.
   VPValue *BackedgeTakenCount = nullptr;
 
   /// Represents the vector trip count.
   VPValue VectorTripCount;
 
   /// Holds a mapping between Values and their corresponding VPValue inside
   /// VPlan.
   Value2VPValueTy Value2VPValue;
 
-  /// Contains all VPValues that been allocated by addVPValue directly and need
-  /// to be free when the plan's destructor is called.
-  SmallVector<VPValue *, 16> VPValuesToFree;
+  /// Contains all the external definitions created for this VPlan. External
+  /// definitions are VPValues that hold a pointer to their underlying IR.
+  SmallVector<VPValue *, 16> VPLiveInsToFree;
 
   /// Indicates whether it is safe use the Value2VPValue mapping or if the
   /// mapping cannot be used any longer, because it is stale.
   bool Value2VPValueEnabled = true;
 
   /// Values used outside the plan.
   MapVector<PHINode *, VPLiveOut *> LiveOuts;
 
 public:
   VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {
     if (Entry)
void setUF(unsigned UF) {
     UFs.insert(UF);
   }
 
   /// Return a string with the name of the plan and the applicable VFs and UFs.
   std::string getName() const;
 
   void setName(const Twine &newName) { Name = newName.str(); }
 
-  /// Get the existing or add a new external definition for \p V.
-  VPValue *getOrAddExternalDef(Value *V) {
-    auto I = VPExternalDefs.insert({V, nullptr});
-    if (I.second)
-      I.first->second = new VPValue(V);
-    return I.first->second;
-  }
-
-  void addVPValue(Value *V) {
-    assert(Value2VPValueEnabled &&
-           "IR value to VPValue mapping may be out of date!");
-    assert(V && "Trying to add a null Value to VPlan");
-    assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
-    VPValue *VPV = new VPValue(V);
-    Value2VPValue[V] = VPV;
-    VPValuesToFree.push_back(VPV);
-  }
-
   void addVPValue(Value *V, VPValue *VPV) {
-    assert(Value2VPValueEnabled && "Value2VPValue mapping may be out of date!");
+    assert((Value2VPValueEnabled || !VPV->getDefiningRecipe()) &&
+           "Value2VPValue mapping may be out of date!");
     assert(V && "Trying to add a null Value to VPlan");
     assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
     Value2VPValue[V] = VPV;
   }
 
   /// Returns the VPValue for \p V. \p OverrideAllowed can be used to disable
-  /// checking whether it is safe to query VPValues using IR Values.
+  ///   /// checking whether it is safe to query VPValues using IR Values.
   VPValue *getVPValue(Value *V, bool OverrideAllowed = false) {
-    assert((OverrideAllowed || isa<Constant>(V) || Value2VPValueEnabled) &&
-           "Value2VPValue mapping may be out of date!");
     assert(V && "Trying to get the VPValue of a null Value");
     assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
+    assert((!Value2VPValue[V]->getDefiningRecipe() || Value2VPValueEnabled ||
+            OverrideAllowed) &&
+           "Value2VPValue mapping may be out of date!");
     return Value2VPValue[V];
   }
 
-  /// Gets the VPValue or adds a new one (if none exists yet) for \p V. \p
-  /// OverrideAllowed can be used to disable checking whether it is safe to
-  /// query VPValues using IR Values.
-  VPValue *getOrAddVPValue(Value *V, bool OverrideAllowed = false) {
-    assert((OverrideAllowed || isa<Constant>(V) || Value2VPValueEnabled) &&
-           "Value2VPValue mapping may be out of date!");
+  /// Gets the VPValue for \p V or adds a new live-in (if none exists yet) for
+  /// \p V.
+  VPValue *getVPValueOrAddLiveIn(Value *V) {
     assert(V && "Trying to get or add the VPValue of a null Value");
-    if (!Value2VPValue.count(V))
-      addVPValue(V);
+    if (!Value2VPValue.count(V)) {
+      VPValue *VPV = new VPValue(V);
+      VPLiveInsToFree.push_back(VPV);
+      addVPValue(V, VPV);
+    }
+
     return getVPValue(V);
   }
 
   void removeVPValueFor(Value *V) {
     assert(Value2VPValueEnabled &&
            "IR value to VPValue mapping may be out of date!");
     Value2VPValue.erase(V);
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print this VPlan to \p O.
   void print(raw_ostream &O) const;
 
   /// Print this VPlan in DOT format to \p O.
   void printDOT(raw_ostream &O) const;
 
   /// Dump the plan to stderr (for debugging).
   LLVM_DUMP_METHOD void dump() const;
 #endif
 
   /// Returns a range mapping the values the range \p Operands to their
   /// corresponding VPValues.
   iterator_range<mapped_iterator<Use *, std::function<VPValue *(Value *)>>>
   mapToVPValues(User::op_range Operands) {
     std::function<VPValue *(Value *)> Fn = [this](Value *Op) {
-      return getOrAddVPValue(Op);
+      return getVPValueOrAddLiveIn(Op);
     };
     return map_range(Operands, Fn);
   }
 
   /// Returns the VPRegionBlock of the vector loop.
   VPRegionBlock *getVectorLoopRegion() {
     return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
   }

llvm/lib/Transforms/Vectorize/VPlan.cpp

VPlan::~VPlan() {
 
   if (Entry) {
     VPValue DummyValue;
     for (VPBlockBase *Block : vp_depth_first_shallow(Entry))
       Block->dropAllReferences(&DummyValue);
 
     VPBlockBase::deleteCFG(Entry);
   }
-  for (VPValue *VPV : VPValuesToFree)
+  for (VPValue *VPV : VPLiveInsToFree)
     delete VPV;
   if (TripCount)
     delete TripCount;
   if (BackedgeTakenCount)
     delete BackedgeTakenCount;
-  for (auto &P : VPExternalDefs)
-    delete P.second;
 }
 
 VPActiveLaneMaskPHIRecipe *VPlan::getActiveLaneMaskPhi() {
   VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock();
   for (VPRecipeBase &R : Header->phis()) {
     if (isa<VPActiveLaneMaskPHIRecipe>(&R))
       return cast<VPActiveLaneMaskPHIRecipe>(&R);
   }
void VPlan::prepareToExecute(Value *TripCountV, Value *VectorTripCountV,
 
   for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part)
     State.set(&VectorTripCount, VectorTripCountV, Part);
 
   // When vectorizing the epilogue loop, the canonical induction start value
   // needs to be changed from zero to the value after the main vector loop.
   // FIXME: Improve modeling for canonical IV start values in the epilogue loop.
   if (CanonicalIVStartValue) {
-    VPValue *VPV = getOrAddExternalDef(CanonicalIVStartValue);
+    VPValue *VPV = getVPValueOrAddLiveIn(CanonicalIVStartValue);
     auto *IV = getCanonicalIV();
     assert(all_of(IV->users(),
                   [](const VPUser *U) {
                     if (isa<VPScalarIVStepsRecipe>(U) ||
                         isa<VPDerivedIVRecipe>(U))
                       return true;
                     auto *VPI = cast<VPInstruction>(U);
                     return VPI->getOpcode() ==

 bool vputils::onlyFirstLaneUsed(VPValue *Def) {
   return all_of(Def->users(),
                 [Def](VPUser *U) { return U->onlyFirstLaneUsed(Def); });
 }
 
 VPValue *vputils::getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr,
                                                 ScalarEvolution &SE) {
   if (auto *E = dyn_cast<SCEVConstant>(Expr))
-    return Plan.getOrAddExternalDef(E->getValue());
+    return Plan.getVPValueOrAddLiveIn(E->getValue());
   if (auto *E = dyn_cast<SCEVUnknown>(Expr))
-    return Plan.getOrAddExternalDef(E->getValue());
+    return Plan.getVPValueOrAddLiveIn(E->getValue());
 
   VPBasicBlock *Preheader = Plan.getEntry()->getEntryBasicBlock();
   VPExpandSCEVRecipe *Step = new VPExpandSCEVRecipe(Expr, SE);
   Preheader->appendRecipe(Step);
   return Step;
 }

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
   //   B) any other Value without specific representation in VPlan.
   // For now, we use VPValue to represent A and B and classify both as external
   // definitions. We may introduce specific VPValue subclasses for them in the
   // future.
   assert(isExternalDef(IRVal) && "Expected external definition as operand.");
 
   // A and B: Create VPValue and add it to the pool of external definitions and
   // to the Value->VPValue map.
-  VPValue *NewVPVal = Plan.getOrAddExternalDef(IRVal);
+  VPValue *NewVPVal = Plan.getVPValueOrAddLiveIn(IRVal);
   IRDef2VPValue[IRVal] = NewVPVal;
   return NewVPVal;
 }
 
 // Create new VPInstructions in a VPBasicBlock, given its BasicBlock
 // counterpart. This function must be invoked in RPO so that the operands of a
 // VPInstruction in \p BB have been visited before (except for Phi nodes).
 void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,
VPBasicBlock *PlainCFGBuilder::buildPlainCFG() {
   BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
   assert((ThePreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
          "Unexpected loop preheader");
   VPBasicBlock *ThePreheaderVPBB = getOrCreateVPBB(ThePreheaderBB);
   ThePreheaderVPBB->setName("vector.ph");
   for (auto &I : *ThePreheaderBB) {
     if (I.getType()->isVoidTy())
       continue;
-    IRDef2VPValue[&I] = Plan.getOrAddExternalDef(&I);
+    IRDef2VPValue[&I] = Plan.getVPValueOrAddLiveIn(&I);
   }
   // Create empty VPBB for Loop H so that we can link PH->H.
   VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
   HeaderVPBB->setName("vector.body");
   ThePreheaderVPBB->setOneSuccessor(HeaderVPBB);
 
   LoopBlocksRPO RPO(TheLoop);
   RPO.perform(LI);

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (VPRecipeBase &Ingredient :
         Ingredient.eraseFromParent();
         continue;
       }
 
       VPRecipeBase *NewRecipe = nullptr;
       if (auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
         auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
         if (const auto *II = GetIntOrFpInductionDescriptor(Phi)) {
-          VPValue *Start = Plan->getOrAddVPValue(II->getStartValue());
+          VPValue *Start = Plan->getVPValueOrAddLiveIn(II->getStartValue());
           VPValue *Step =
               vputils::getOrCreateVPValueForSCEVExpr(*Plan, II->getStep(), SE);
           NewRecipe =
               new VPWidenIntOrFpInductionRecipe(Phi, Start, Step, *II, true);
         } else {
           Plan->addVPValue(Phi, VPPhi);
           continue;
         }
       } else {
         assert(isa<VPInstruction>(&Ingredient) &&
                "only VPInstructions expected here");
         assert(!isa<PHINode>(Inst) && "phis should be handled above");
         // Create VPWidenMemoryInstructionRecipe for loads and stores.
         if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
           NewRecipe = new VPWidenMemoryInstructionRecipe(
-              *Load, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)),
+              *Load,
+              Plan->getVPValueOrAddLiveIn(getLoadStorePointerOperand(Inst)),
               nullptr /*Mask*/, false /*Consecutive*/, false /*Reverse*/);
         } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
           NewRecipe = new VPWidenMemoryInstructionRecipe(
-              *Store, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)),
-              Plan->getOrAddVPValue(Store->getValueOperand()), nullptr /*Mask*/,
-              false /*Consecutive*/, false /*Reverse*/);
+              *Store,
+              Plan->getVPValueOrAddLiveIn(getLoadStorePointerOperand(Inst)),
+              Plan->getVPValueOrAddLiveIn(Store->getValueOperand()),
+              nullptr /*Mask*/, false /*Consecutive*/, false /*Reverse*/);
         } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
           NewRecipe =
               new VPWidenGEPRecipe(GEP, Plan->mapToVPValues(GEP->operands()));
         } else if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
           NewRecipe =
               new VPWidenCallRecipe(*CI, Plan->mapToVPValues(CI->args()),
                                     getVectorIntrinsicIDForCall(CI, &TLI));
         } else if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
void VPlanTransforms::optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,
   ScalarEvolution &SE = *PSE.getSE();
   const SCEV *C =
       SE.getConstant(TripCount->getType(), BestVF.getKnownMinValue() * BestUF);
   if (TripCount->isZero() ||
       !SE.isKnownPredicate(CmpInst::ICMP_ULE, TripCount, C))
     return;
 
   LLVMContext &Ctx = SE.getContext();
-  auto *BOC =
-      new VPInstruction(VPInstruction::BranchOnCond,
-                        {Plan.getOrAddExternalDef(ConstantInt::getTrue(Ctx))});
+  auto *BOC = new VPInstruction(
+      VPInstruction::BranchOnCond,
+      {Plan.getVPValueOrAddLiveIn(ConstantInt::getTrue(Ctx))});
   Term->eraseFromParent();
   ExitingVPBB->appendRecipe(BOC);
   Plan.setVF(BestVF);
   Plan.setUF(BestUF);
   // TODO: Further simplifications are possible
   //      1. Replace inductions with constants.
   //      2. Replace vector loop region with VPBasicBlock.
 }

llvm/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

TEST_F(VPlanHCFGTest, testBuildHCFGInnerLoop) {
   VPInstruction *ICmp = dyn_cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::ICmp, ICmp->getOpcode());
   EXPECT_EQ(2u, ICmp->getNumOperands());
   EXPECT_EQ(IndvarAdd, ICmp->getOperand(0));
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   // Add an external value to check we do not print the list of external values,
   // as this is not required with the new printing.
-  Plan->addVPValue(&*F->arg_begin());
+  Plan->getVPValueOrAddLiveIn(&*F->arg_begin());
   std::string FullDump;
   raw_string_ostream OS(FullDump);
   Plan->printDOT(OS);
   const char *ExpectedStr = R"(digraph VPlan {
 graph [labelloc=t, fontsize=30; label="Vectorization Plan\n for UF\>=1"]
 node [shape=rect, fontname=Courier, fontsize=30]
 edge [fontname=Courier, fontsize=30]
 compound=true

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

TEST(VPRecipeTest, dump) {
 
   LLVMContext C;
 
   IntegerType *Int32 = IntegerType::get(C, 32);
   auto *AI =
       BinaryOperator::CreateAdd(UndefValue::get(Int32), UndefValue::get(Int32));
   AI->setName("a");
   SmallVector<VPValue *, 2> Args;
-  VPValue *ExtVPV1 = Plan.getOrAddExternalDef(ConstantInt::get(Int32, 1));
-  VPValue *ExtVPV2 = Plan.getOrAddExternalDef(ConstantInt::get(Int32, 2));
+  VPValue *ExtVPV1 = Plan.getVPValueOrAddLiveIn(ConstantInt::get(Int32, 1));
+  VPValue *ExtVPV2 = Plan.getVPValueOrAddLiveIn(ConstantInt::get(Int32, 2));
   Args.push_back(ExtVPV1);
   Args.push_back(ExtVPV2);
   VPWidenRecipe *WidenR =
       new VPWidenRecipe(*AI, make_range(Args.begin(), Args.end()));
   VPBB1->appendRecipe(WidenR);
 
   {
     // Use EXPECT_EXIT to capture stderr and compare against expected output.