1//===-- VPlanConstruction.cpp - Transforms for initial VPlan construction -===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements transforms for initial VPlan construction.
11///
12//===----------------------------------------------------------------------===//
13
14#include "LoopVectorizationPlanner.h"
15#include "VPlan.h"
16#include "VPlanAnalysis.h"
17#include "VPlanCFG.h"
18#include "VPlanDominatorTree.h"
19#include "VPlanHelpers.h"
20#include "VPlanPatternMatch.h"
21#include "VPlanTransforms.h"
22#include "VPlanUtils.h"
23#include "llvm/ADT/SmallVectorExtras.h"
24#include "llvm/Analysis/Loads.h"
25#include "llvm/Analysis/LoopInfo.h"
26#include "llvm/Analysis/LoopIterator.h"
27#include "llvm/Analysis/OptimizationRemarkEmitter.h"
28#include "llvm/Analysis/ScalarEvolution.h"
29#include "llvm/Analysis/ScalarEvolutionExpressions.h"
30#include "llvm/Analysis/TargetTransformInfo.h"
31#include "llvm/IR/InstrTypes.h"
32#include "llvm/IR/MDBuilder.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Transforms/Utils/LoopUtils.h"
35#include "llvm/Transforms/Utils/LoopVersioning.h"
36#include "llvm/Transforms/Vectorize/LoopVectorize.h"
37
38#define DEBUG_TYPE "vplan"
39
40using namespace llvm;
41using namespace LoopVectorizationUtils;
42using namespace VPlanPatternMatch;
43
44namespace {
45// Class that is used to build the plain CFG for the incoming IR.
46class PlainCFGBuilder {
47 // The outermost loop of the input loop nest considered for vectorization.
48 Loop *TheLoop;
49
50 // Loop Info analysis.
51 LoopInfo *LI;
52
53 // Loop versioning for alias metadata.
54 LoopVersioning *LVer;
55
56 // Vectorization plan that we are working on.
57 std::unique_ptr<VPlan> Plan;
58
59 // Builder of the VPlan instruction-level representation.
60 VPBuilder VPIRBuilder;
61
62 // NOTE: The following maps are intentionally destroyed after the plain CFG
63 // construction because subsequent VPlan-to-VPlan transformation may
64 // invalidate them.
65 // Map incoming BasicBlocks to their newly-created VPBasicBlocks.
66 DenseMap<BasicBlock *, VPBasicBlock *> BB2VPBB;
67 // Map incoming Value definitions to their newly-created VPValues.
68 DenseMap<Value *, VPValue *> IRDef2VPValue;
69
70 // Hold phi node's that need to be fixed once the plain CFG has been built.
71 SmallVector<PHINode *, 8> PhisToFix;
72
73 // Utility functions.
74 void setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB);
75 void fixHeaderPhis();
76 VPBasicBlock *getOrCreateVPBB(BasicBlock *BB);
77#ifndef NDEBUG
78 bool isExternalDef(Value *Val);
79#endif
80 VPValue *getOrCreateVPOperand(Value *IRVal);
81 void createVPInstructionsForVPBB(VPBasicBlock *VPBB, BasicBlock *BB);
82
83public:
84 PlainCFGBuilder(Loop *Lp, LoopInfo *LI, LoopVersioning *LVer, Type *IdxTy)
85 : TheLoop(Lp), LI(LI), LVer(LVer),
86 Plan(std::make_unique<VPlan>(args&: Lp, args&: IdxTy)) {}
87
88 /// Build plain CFG for TheLoop and connect it to Plan's entry.
89 std::unique_ptr<VPlan> buildPlainCFG();
90};
91} // anonymous namespace
92
93// Set predecessors of \p VPBB in the same order as they are in \p BB. \p VPBB
94// must have no predecessors.
95void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) {
96 // Collect VPBB predecessors.
97 SmallVector<VPBlockBase *, 2> VPBBPreds;
98 for (BasicBlock *Pred : predecessors(BB))
99 VPBBPreds.push_back(Elt: getOrCreateVPBB(BB: Pred));
100 VPBB->setPredecessors(VPBBPreds);
101}
102
103static bool isHeaderBB(BasicBlock *BB, Loop *L) {
104 return L && BB == L->getHeader();
105}
106
107// Add operands to VPInstructions representing phi nodes from the input IR.
108void PlainCFGBuilder::fixHeaderPhis() {
109 for (auto *Phi : PhisToFix) {
110 assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
111 VPValue *VPVal = IRDef2VPValue[Phi];
112 assert(isa<VPPhi>(VPVal) && "Expected VPPhi for phi node.");
113 auto *PhiR = cast<VPPhi>(Val: VPVal);
114 assert(PhiR->getNumOperands() == 0 && "Expected VPPhi with no operands.");
115 assert(isHeaderBB(Phi->getParent(), LI->getLoopFor(Phi->getParent())) &&
116 "Expected Phi in header block.");
117 assert(Phi->getNumOperands() == 2 &&
118 "header phi must have exactly 2 operands");
119 for (BasicBlock *Pred : predecessors(BB: Phi->getParent()))
120 PhiR->addIncoming(
121 IncomingV: getOrCreateVPOperand(IRVal: Phi->getIncomingValueForBlock(BB: Pred)));
122 }
123}
124
125// Create a new empty VPBasicBlock for an incoming BasicBlock or retrieve an
126// existing one if it was already created.
127VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {
128 if (auto *VPBB = BB2VPBB.lookup(Val: BB)) {
129 // Retrieve existing VPBB.
130 return VPBB;
131 }
132
133 // Create new VPBB.
134 StringRef Name = BB->getName();
135 LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << Name << "\n");
136 VPBasicBlock *VPBB = Plan->createVPBasicBlock(Name);
137 BB2VPBB[BB] = VPBB;
138 return VPBB;
139}
140
141#ifndef NDEBUG
142// Return true if \p Val is considered an external definition. An external
143// definition is either:
144// 1. A Value that is not an Instruction. This will be refined in the future.
145// 2. An Instruction that is outside of the IR region represented in VPlan,
146// i.e., is not part of the loop nest.
147bool PlainCFGBuilder::isExternalDef(Value *Val) {
148 // All the Values that are not Instructions are considered external
149 // definitions for now.
150 Instruction *Inst = dyn_cast<Instruction>(Val);
151 if (!Inst)
152 return true;
153
154 // Check whether Instruction definition is in loop body.
155 return !TheLoop->contains(Inst);
156}
157#endif
158
159// Create a new VPValue or retrieve an existing one for the Instruction's
160// operand \p IRVal. This function must only be used to create/retrieve VPValues
161// for *Instruction's operands* and not to create regular VPInstruction's. For
162// the latter, please, look at 'createVPInstructionsForVPBB'.
163VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
164 auto VPValIt = IRDef2VPValue.find(Val: IRVal);
165 if (VPValIt != IRDef2VPValue.end())
166 // Operand has an associated VPInstruction or VPValue that was previously
167 // created.
168 return VPValIt->second;
169
170 // Operand doesn't have a previously created VPInstruction/VPValue. This
171 // means that operand is:
172 // A) a definition external to VPlan,
173 // B) any other Value without specific representation in VPlan.
174 // For now, we use VPValue to represent A and B and classify both as external
175 // definitions. We may introduce specific VPValue subclasses for them in the
176 // future.
177 assert(isExternalDef(IRVal) && "Expected external definition as operand.");
178
179 // A and B: Create VPValue and add it to the pool of external definitions and
180 // to the Value->VPValue map.
181 VPValue *NewVPVal = Plan->getOrAddLiveIn(V: IRVal);
182 IRDef2VPValue[IRVal] = NewVPVal;
183 return NewVPVal;
184}
185
186// Create new VPInstructions in a VPBasicBlock, given its BasicBlock
187// counterpart. This function must be invoked in RPO so that the operands of a
188// VPInstruction in \p BB have been visited before (except for Phi nodes).
189void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,
190 BasicBlock *BB) {
191 VPIRBuilder.setInsertPoint(VPBB);
192 // TODO: Model and preserve debug intrinsics in VPlan.
193 for (Instruction &InstRef : *BB) {
194 Instruction *Inst = &InstRef;
195
196 // There shouldn't be any VPValue for Inst at this point. Otherwise, we
197 // visited Inst when we shouldn't, breaking the RPO traversal order.
198 assert(!IRDef2VPValue.count(Inst) &&
199 "Instruction shouldn't have been visited.");
200
201 if (isa<UncondBrInst>(Val: Inst))
202 // Skip the rest of the Instruction processing for Branch instructions.
203 continue;
204
205 if (auto *Br = dyn_cast<CondBrInst>(Val: Inst)) {
206 // Conditional branch instruction are represented using BranchOnCond
207 // recipes.
208 VPValue *Cond = getOrCreateVPOperand(IRVal: Br->getCondition());
209 VPIRBuilder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cond}, Inst, Flags: {},
210 MD: VPIRMetadata(*Inst), DL: Inst->getDebugLoc());
211 continue;
212 }
213
214 if (auto *SI = dyn_cast<SwitchInst>(Val: Inst)) {
215 // Don't emit recipes for unconditional switch instructions.
216 if (SI->getNumCases() == 0)
217 continue;
218 SmallVector<VPValue *> Ops = {getOrCreateVPOperand(IRVal: SI->getCondition())};
219 for (auto Case : SI->cases())
220 Ops.push_back(Elt: getOrCreateVPOperand(IRVal: Case.getCaseValue()));
221 VPIRBuilder.createNaryOp(Opcode: Instruction::Switch, Operands: Ops, Inst, Flags: {},
222 MD: VPIRMetadata(*Inst), DL: Inst->getDebugLoc());
223 continue;
224 }
225
226 VPSingleDefRecipe *NewR;
227 if (auto *Phi = dyn_cast<PHINode>(Val: Inst)) {
228 // Phi node's operands may not have been visited at this point. We create
229 // an empty VPInstruction that we will fix once the whole plain CFG has
230 // been built.
231 NewR = VPIRBuilder.createScalarPhi(IncomingValues: {}, DL: Phi->getDebugLoc(), Name: "vec.phi",
232 Flags: *Phi, ResultTy: Phi->getType());
233 NewR->setUnderlyingValue(Phi);
234 if (isHeaderBB(BB: Phi->getParent(), L: LI->getLoopFor(BB: Phi->getParent()))) {
235 // Header phis need to be fixed after the VPBB for the latch has been
236 // created.
237 PhisToFix.push_back(Elt: Phi);
238 } else {
239 // Add operands for VPPhi in the order matching its predecessors in
240 // VPlan.
241 DenseMap<const VPBasicBlock *, VPValue *> VPPredToIncomingValue;
242 for (unsigned I = 0; I != Phi->getNumOperands(); ++I) {
243 VPPredToIncomingValue[BB2VPBB[Phi->getIncomingBlock(i: I)]] =
244 getOrCreateVPOperand(IRVal: Phi->getIncomingValue(i: I));
245 }
246 for (VPBlockBase *Pred : VPBB->getPredecessors())
247 cast<VPPhi>(Val: NewR)->addIncoming(
248 IncomingV: VPPredToIncomingValue.lookup(Val: Pred->getExitingBasicBlock()));
249 }
250 } else {
251 // Build VPIRMetadata from the instruction and add loop versioning
252 // metadata for loads and stores.
253 VPIRMetadata MD(*Inst);
254 if (isa<LoadInst, StoreInst>(Val: Inst) && LVer) {
255 const auto &[AliasScopeMD, NoAliasMD] =
256 LVer->getNoAliasMetadataFor(OrigInst: Inst);
257 if (AliasScopeMD)
258 MD.setMetadata(Kind: LLVMContext::MD_alias_scope, Node: AliasScopeMD);
259 if (NoAliasMD)
260 MD.setMetadata(Kind: LLVMContext::MD_noalias, Node: NoAliasMD);
261 }
262
263 // Translate LLVM-IR operands into VPValue operands and set them in the
264 // new VPInstruction.
265 SmallVector<VPValue *, 4> VPOperands;
266 for (Value *Op : Inst->operands())
267 VPOperands.push_back(Elt: getOrCreateVPOperand(IRVal: Op));
268
269 if (auto *CI = dyn_cast<CastInst>(Val: Inst)) {
270 NewR = VPIRBuilder.createScalarCast(Opcode: CI->getOpcode(), Op: VPOperands[0],
271 ResultTy: CI->getType(), DL: CI->getDebugLoc(),
272 Flags: VPIRFlags(*CI), Metadata: MD);
273 NewR->setUnderlyingValue(CI);
274 } else if (auto *LI = dyn_cast<LoadInst>(Val: Inst)) {
275 NewR = VPIRBuilder.createScalarLoad(ResultTy: LI->getType(), Addr: VPOperands[0],
276 DL: LI->getDebugLoc(), Metadata: MD);
277 NewR->setUnderlyingValue(LI);
278 } else {
279 // Build VPInstruction for any arbitrary Instruction without specific
280 // representation in VPlan.
281 NewR = VPIRBuilder.createNaryOp(
282 Opcode: Inst->getOpcode(), Operands: VPOperands, Inst, Flags: VPIRFlags(*Inst), MD,
283 DL: Inst->getDebugLoc(), Name: "", ResultTy: Inst->getType());
284 }
285 }
286
287 IRDef2VPValue[Inst] = NewR;
288 }
289}
290
291// Main interface to build the plain CFG.
292std::unique_ptr<VPlan> PlainCFGBuilder::buildPlainCFG() {
293 VPIRBasicBlock *Entry = cast<VPIRBasicBlock>(Val: Plan->getEntry());
294 BB2VPBB[Entry->getIRBasicBlock()] = Entry;
295 for (VPIRBasicBlock *ExitVPBB : Plan->getExitBlocks())
296 BB2VPBB[ExitVPBB->getIRBasicBlock()] = ExitVPBB;
297
298 // 1. Scan the body of the loop in a topological order to visit each basic
299 // block after having visited its predecessor basic blocks. Create a VPBB for
300 // each BB and link it to its successor and predecessor VPBBs. Note that
301 // predecessors must be set in the same order as they are in the incomming IR.
302 // Otherwise, there might be problems with existing phi nodes and algorithm
303 // based on predecessors traversal.
304
305 // Loop PH needs to be explicitly visited since it's not taken into account by
306 // LoopBlocksDFS.
307 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
308 assert((ThePreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
309 "Unexpected loop preheader");
310 for (auto &I : *ThePreheaderBB) {
311 if (I.getType()->isVoidTy())
312 continue;
313 IRDef2VPValue[&I] = Plan->getOrAddLiveIn(V: &I);
314 }
315
316 LoopBlocksRPO RPO(TheLoop);
317 RPO.perform(LI);
318
319 for (BasicBlock *BB : RPO) {
320 // Create or retrieve the VPBasicBlock for this BB.
321 VPBasicBlock *VPBB = getOrCreateVPBB(BB);
322 // Set VPBB predecessors in the same order as they are in the incoming BB.
323 setVPBBPredsFromBB(VPBB, BB);
324
325 // Create VPInstructions for BB.
326 createVPInstructionsForVPBB(VPBB, BB);
327
328 // Set VPBB successors. We create empty VPBBs for successors if they don't
329 // exist already. Recipes will be created when the successor is visited
330 // during the RPO traversal.
331 if (auto *SI = dyn_cast<SwitchInst>(Val: BB->getTerminator())) {
332 SmallVector<VPBlockBase *> Succs = {
333 getOrCreateVPBB(BB: SI->getDefaultDest())};
334 for (auto Case : SI->cases())
335 Succs.push_back(Elt: getOrCreateVPBB(BB: Case.getCaseSuccessor()));
336 VPBB->setSuccessors(Succs);
337 continue;
338 }
339 if (auto *BI = dyn_cast<UncondBrInst>(Val: BB->getTerminator())) {
340 VPBB->setOneSuccessor(getOrCreateVPBB(BB: BI->getSuccessor()));
341 continue;
342 }
343 auto *BI = cast<CondBrInst>(Val: BB->getTerminator());
344 BasicBlock *IRSucc0 = BI->getSuccessor(i: 0);
345 BasicBlock *IRSucc1 = BI->getSuccessor(i: 1);
346 VPBasicBlock *Successor0 = getOrCreateVPBB(BB: IRSucc0);
347 VPBasicBlock *Successor1 = getOrCreateVPBB(BB: IRSucc1);
348 VPBB->setTwoSuccessors(IfTrue: Successor0, IfFalse: Successor1);
349 }
350
351 for (auto *EB : Plan->getExitBlocks())
352 setVPBBPredsFromBB(VPBB: EB, BB: EB->getIRBasicBlock());
353
354 // 2. The whole CFG has been built at this point so all the input Values must
355 // have a VPlan counterpart. Fix VPlan header phi by adding their
356 // corresponding VPlan operands.
357 fixHeaderPhis();
358
359 Plan->getEntry()->setOneSuccessor(getOrCreateVPBB(BB: TheLoop->getHeader()));
360 Plan->getEntry()->setPlan(&*Plan);
361
362 // Fix VPlan loop-closed-ssa exit phi's by adding incoming operands to the
363 // VPIRInstructions wrapping them.
364 // // Note that the operand order corresponds to IR predecessor order, and may
365 // need adjusting when VPlan predecessors are added, if an exit block has
366 // multiple predecessor.
367 for (auto *EB : Plan->getExitBlocks()) {
368 for (VPRecipeBase &R : EB->phis()) {
369 auto *PhiR = cast<VPIRPhi>(Val: &R);
370 PHINode &Phi = PhiR->getIRPhi();
371 assert(PhiR->getNumOperands() == 0 &&
372 "no phi operands should be added yet");
373 for (BasicBlock *Pred : predecessors(BB: EB->getIRBasicBlock()))
374 PhiR->addIncoming(
375 IncomingV: getOrCreateVPOperand(IRVal: Phi.getIncomingValueForBlock(BB: Pred)));
376 }
377 }
378
379 LLVM_DEBUG(Plan->setName("Plain CFG\n"); dbgs() << *Plan);
380 return std::move(Plan);
381}
382
383/// Checks if \p HeaderVPB is a loop header block in the plain CFG; that is, it
384/// has exactly 2 predecessors (preheader and latch), where the block
385/// dominates the latch and the preheader dominates the block. If it is a
386/// header block return true and canonicalize the predecessors of the header
387/// (making sure the preheader appears first and the latch second) and the
388/// successors of the latch (making sure the loop exit comes first). Otherwise
389/// return false.
390static bool canonicalHeaderAndLatch(VPBlockBase *HeaderVPB,
391 const VPDominatorTree &VPDT) {
392 ArrayRef<VPBlockBase *> Preds = HeaderVPB->getPredecessors();
393 if (Preds.size() != 2)
394 return false;
395
396 auto *PreheaderVPBB = Preds[0];
397 auto *LatchVPBB = Preds[1];
398 if (!VPDT.dominates(A: PreheaderVPBB, B: HeaderVPB) ||
399 !VPDT.dominates(A: HeaderVPB, B: LatchVPBB)) {
400 std::swap(a&: PreheaderVPBB, b&: LatchVPBB);
401
402 if (!VPDT.dominates(A: PreheaderVPBB, B: HeaderVPB) ||
403 !VPDT.dominates(A: HeaderVPB, B: LatchVPBB))
404 return false;
405
406 // Canonicalize predecessors of header so that preheader is first and
407 // latch second.
408 HeaderVPB->swapPredecessors();
409 for (VPRecipeBase &R : cast<VPBasicBlock>(Val: HeaderVPB)->phis())
410 R.swapOperands();
411 }
412
413 // The two successors of conditional branch match the condition, with the
414 // first successor corresponding to true and the second to false. We
415 // canonicalize the successors of the latch when introducing the region, such
416 // that the latch exits the region when its condition is true; invert the
417 // original condition if the original CFG branches to the header on true.
418 // Note that the exit edge is not yet connected for top-level loops.
419 if (LatchVPBB->getSingleSuccessor() ||
420 LatchVPBB->getSuccessors()[0] != HeaderVPB)
421 return true;
422
423 assert(LatchVPBB->getNumSuccessors() == 2 && "Must have 2 successors");
424 auto *Term = cast<VPBasicBlock>(Val: LatchVPBB)->getTerminator();
425 assert(cast<VPInstruction>(Term)->getOpcode() ==
426 VPInstruction::BranchOnCond &&
427 "terminator must be a BranchOnCond");
428 auto *Not = new VPInstruction(VPInstruction::Not, {Term->getOperand(N: 0)});
429 Not->insertBefore(InsertPos: Term);
430 Term->setOperand(I: 0, New: Not);
431 LatchVPBB->swapSuccessors();
432
433 return true;
434}
435
436/// Create a new VPRegionBlock for the loop starting at \p HeaderVPB. For the
437/// outermost loop adjust the regions exiting terminator to be based on the
438/// canonical IV.
439static void createLoopRegion(VPlan &Plan, VPBlockBase *HeaderVPB, DebugLoc DL) {
440 auto *PreheaderVPBB = HeaderVPB->getPredecessors()[0];
441 auto *LatchVPBB = cast<VPBasicBlock>(Val: HeaderVPB->getPredecessors()[1]);
442 auto *OutermostHeaderVPBB =
443 VPBlockUtils::getPlainCFGHeaderAndLatch(Plan).first;
444
445 VPBlockUtils::disconnectBlocks(From: PreheaderVPBB, To: HeaderVPB);
446 VPBlockUtils::disconnectBlocks(From: LatchVPBB, To: HeaderVPB);
447
448 // Create an empty region first and insert it between PreheaderVPBB and
449 // the exit blocks, taking care to preserve the original predecessor &
450 // successor order of blocks. Set region entry and exiting after both
451 // HeaderVPB and LatchVPBB have been disconnected from their
452 // predecessors/successors. Only the outermost loop has a canonical IV. Nested
453 // loops are assigned a canonical IV of null type and unknown debug location.
454 bool IsOutermost = HeaderVPB == OutermostHeaderVPBB;
455 Type *CanIVTy = nullptr;
456 if (IsOutermost)
457 CanIVTy = Plan.getVectorTripCount().getType();
458 else
459 DL = DebugLoc::getUnknown();
460 auto *R = Plan.createLoopRegion(CanIVTy, DL);
461
462 // Transfer latch's successors to the region.
463 VPBlockUtils::transferSuccessors(Old: LatchVPBB, New: R);
464
465 VPBlockUtils::connectBlocks(From: PreheaderVPBB, To: R);
466 R->setEntry(HeaderVPB);
467 R->setExiting(LatchVPBB);
468
469 // All VPBB's reachable shallowly from HeaderVPB belong to the current region.
470 for (VPBlockBase *VPBB : vp_depth_first_shallow(G: HeaderVPB))
471 VPBB->setParent(R);
472
473 if (!IsOutermost)
474 return;
475
476 auto *LatchTerm = LatchVPBB->getTerminator();
477 VPBuilder Builder(LatchTerm);
478 // Add a VPInstruction to increment the scalar canonical IV by VF * UF.
479 // Initially the induction increment is guaranteed to not wrap, but that may
480 // change later, e.g. when tail-folding, when the flags need to be dropped.
481 auto *CanonicalIVIncrement = Builder.createAdd(
482 LHS: R->getCanonicalIV(), RHS: &Plan.getVFxUF(), DL, Name: "index.next", WrapFlags: {true, false});
483
484 if (match(V: LatchTerm, P: m_BranchOnTwoConds())) {
485 auto *IsLatchExitTaken = Builder.createICmp(
486 Pred: CmpInst::ICMP_EQ, A: CanonicalIVIncrement, B: &Plan.getVectorTripCount());
487 LatchTerm->setOperand(I: 1, New: IsLatchExitTaken);
488 } else {
489 // We are replacing the branch to exit the region. Remove the original
490 // BranchOnCond.
491 assert(match(LatchTerm, m_BranchOnCond()) && "Unexpected terminator");
492 DebugLoc LatchDL = LatchTerm->getDebugLoc();
493 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCount,
494 Operands: {CanonicalIVIncrement, &Plan.getVectorTripCount()},
495 DL: LatchDL);
496 LatchTerm->eraseFromParent();
497 }
498}
499
500/// Creates extracts for values in \p Plan defined in a loop region and used
501/// outside a loop region.
502static void createExtractsForLiveOuts(VPlan &Plan, VPBasicBlock *MiddleVPBB) {
503 VPBuilder B(MiddleVPBB, MiddleVPBB->getFirstNonPhi());
504 for (VPBasicBlock *EB : Plan.getExitBlocks()) {
505 if (!is_contained(Range: EB->predecessors(), Element: MiddleVPBB))
506 continue;
507
508 for (VPRecipeBase &R : EB->phis()) {
509 auto *ExitIRI = cast<VPIRPhi>(Val: &R);
510 VPValue *Exiting = ExitIRI->getIncomingValueForBlock(VPBB: MiddleVPBB);
511 if (isa<VPIRValue>(Val: Exiting))
512 continue;
513 Exiting = B.createNaryOp(Opcode: VPInstruction::ExtractLastPart, Operands: Exiting);
514 Exiting = B.createNaryOp(Opcode: VPInstruction::ExtractLastLane, Operands: Exiting);
515 ExitIRI->setIncomingValueForBlock(VPBB: MiddleVPBB, V: Exiting);
516 }
517 }
518}
519
520static void addInitialSkeleton(VPlan &Plan, Type *InductionTy,
521 PredicatedScalarEvolution &PSE, Loop *TheLoop) {
522 VPDominatorTree VPDT(Plan);
523
524 auto *HeaderVPBB = cast<VPBasicBlock>(Val: Plan.getEntry()->getSingleSuccessor());
525 canonicalHeaderAndLatch(HeaderVPB: HeaderVPBB, VPDT);
526 auto *LatchVPBB = cast<VPBasicBlock>(Val: HeaderVPBB->getPredecessors()[1]);
527
528 VPBasicBlock *VecPreheader = Plan.createVPBasicBlock(Name: "vector.ph");
529 VPBlockUtils::insertBlockAfter(NewBlock: VecPreheader, BlockPtr: Plan.getEntry());
530
531 VPBasicBlock *MiddleVPBB = Plan.createVPBasicBlock(Name: "middle.block");
532 // The canonical LatchVPBB has the header block as last successor. If it has
533 // another successor, this successor is an exit block - insert middle block on
534 // its edge. Otherwise, add middle block as another successor retaining header
535 // as last. In the latter case, the latch has no conditional terminator yet,
536 // so insert a placeholder BranchOnCond that always continues to the header.
537 // It will be canonicalized to a BranchOnCount later
538 if (LatchVPBB->getNumSuccessors() == 2) {
539 VPBlockBase *LatchExitVPB = LatchVPBB->getSuccessors()[0];
540 VPBlockUtils::insertOnEdge(From: LatchVPBB, To: LatchExitVPB, BlockPtr: MiddleVPBB);
541 } else {
542 VPBlockUtils::connectBlocks(From: LatchVPBB, To: MiddleVPBB);
543 LatchVPBB->swapSuccessors();
544 VPBuilder(LatchVPBB).createNaryOp(Opcode: VPInstruction::BranchOnCond,
545 Operands: {Plan.getFalse()});
546 }
547
548 // Create SCEV and VPValue for the trip count.
549 // We use the symbolic max backedge-taken-count, which works also when
550 // vectorizing loops with uncountable early exits.
551 const SCEV *BackedgeTakenCountSCEV = PSE.getSymbolicMaxBackedgeTakenCount();
552 assert(!isa<SCEVCouldNotCompute>(BackedgeTakenCountSCEV) &&
553 "Invalid backedge-taken count");
554 ScalarEvolution &SE = *PSE.getSE();
555 const SCEV *TripCount = SE.getTripCountFromExitCount(ExitCount: BackedgeTakenCountSCEV,
556 EvalTy: InductionTy, L: TheLoop);
557 Plan.setTripCount(vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: TripCount));
558
559 VPBasicBlock *ScalarPH = Plan.createVPBasicBlock(Name: "scalar.ph");
560 VPBlockUtils::connectBlocks(From: ScalarPH, To: Plan.getScalarHeader());
561
562 // The connection order corresponds to the operands of the conditional branch,
563 // with the middle block already connected to the exit block.
564 VPBlockUtils::connectBlocks(From: MiddleVPBB, To: ScalarPH);
565 // Also connect the entry block to the scalar preheader.
566 // TODO: Also introduce a branch recipe together with the minimum trip count
567 // check.
568 VPBlockUtils::connectBlocks(From: Plan.getEntry(), To: ScalarPH);
569 Plan.getEntry()->swapSuccessors();
570
571 createExtractsForLiveOuts(Plan, MiddleVPBB);
572
573 // Create resume phis in the scalar preheader for each phi in the scalar loop.
574 // Their incoming value from the vector loop will be the last lane of the
575 // corresponding vector loop header phi.
576 VPBuilder MiddleBuilder(MiddleVPBB, MiddleVPBB->getFirstNonPhi());
577 VPBuilder ScalarPHBuilder(ScalarPH);
578 assert(equal(ScalarPH->getPredecessors(),
579 ArrayRef<VPBlockBase *>({MiddleVPBB, Plan.getEntry()})) &&
580 "unexpected predecessor order of scalar ph");
581 for (const auto &[PhiR, ScalarPhiR] :
582 zip_equal(t: HeaderVPBB->phis(), u: Plan.getScalarHeader()->phis())) {
583 auto *VectorPhiR = cast<VPPhi>(Val: &PhiR);
584 VPValue *BackedgeVal = VectorPhiR->getOperand(N: 1);
585 VPValue *ResumeFromVectorLoop =
586 MiddleBuilder.createNaryOp(Opcode: VPInstruction::ExtractLastPart, Operands: BackedgeVal);
587 ResumeFromVectorLoop = MiddleBuilder.createNaryOp(
588 Opcode: VPInstruction::ExtractLastLane, Operands: ResumeFromVectorLoop);
589 // Create scalar resume phi, with the first operand being the incoming value
590 // from the middle block and the second operand coming from the entry block.
591 auto *ResumePhiR = ScalarPHBuilder.createScalarPhi(
592 IncomingValues: {ResumeFromVectorLoop, VectorPhiR->getOperand(N: 0)},
593 DL: VectorPhiR->getDebugLoc());
594 cast<VPIRPhi>(Val: &ScalarPhiR)->addIncoming(IncomingV: ResumePhiR);
595 }
596}
597
598/// Check \p Plan's live-in and replace them with constants, if they can be
599/// simplified via SCEV.
600static void simplifyLiveInsWithSCEV(VPlan &Plan,
601 PredicatedScalarEvolution &PSE) {
602 auto GetSimplifiedLiveInViaSCEV = [&](VPValue *VPV) -> VPValue * {
603 const SCEV *Expr = vputils::getSCEVExprForVPValue(V: VPV, PSE);
604 if (auto *C = dyn_cast<SCEVConstant>(Val: Expr))
605 return Plan.getOrAddLiveIn(V: C->getValue());
606 return nullptr;
607 };
608
609 for (VPValue *LiveIn : to_vector(Range: Plan.getLiveIns())) {
610 if (VPValue *SimplifiedLiveIn = GetSimplifiedLiveInViaSCEV(LiveIn))
611 LiveIn->replaceAllUsesWith(New: SimplifiedLiveIn);
612 }
613}
614
615/// To make RUN_VPLAN_PASS print initial VPlan.
616static void printAfterInitialConstruction(VPlan &) {}
617
618std::unique_ptr<VPlan>
619VPlanTransforms::buildVPlan0(Loop *TheLoop, LoopInfo &LI, Type *InductionTy,
620 PredicatedScalarEvolution &PSE,
621 LoopVersioning *LVer) {
622 PlainCFGBuilder Builder(TheLoop, &LI, LVer, InductionTy);
623 std::unique_ptr<VPlan> VPlan0 = Builder.buildPlainCFG();
624 addInitialSkeleton(Plan&: *VPlan0, InductionTy, PSE, TheLoop);
625 simplifyLiveInsWithSCEV(Plan&: *VPlan0, PSE);
626
627 RUN_VPLAN_PASS_NO_VERIFY(printAfterInitialConstruction, *VPlan0);
628 return VPlan0;
629}
630
631/// Creates a VPWidenIntOrFpInductionRecipe or VPWidenPointerInductionRecipe
632/// for \p Phi based on \p IndDesc.
633static VPHeaderPHIRecipe *
634createWidenInductionRecipe(PHINode *Phi, VPPhi *PhiR, VPIRValue *Start,
635 const InductionDescriptor &IndDesc, VPlan &Plan,
636 PredicatedScalarEvolution &PSE, Loop &OrigLoop,
637 DebugLoc DL) {
638 [[maybe_unused]] ScalarEvolution &SE = *PSE.getSE();
639 assert(SE.isLoopInvariant(IndDesc.getStep(), &OrigLoop) &&
640 "step must be loop invariant");
641 assert((Plan.getLiveIn(IndDesc.getStartValue()) == Start ||
642 (SE.isSCEVable(IndDesc.getStartValue()->getType()) &&
643 PSE.getSCEV(IndDesc.getStartValue()) ==
644 vputils::getSCEVExprForVPValue(Start, PSE))) &&
645 "Start VPValue must match IndDesc's start value");
646
647 VPValue *Step =
648 vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: IndDesc.getStep());
649
650 VPValue *BackedgeVal = PhiR->getOperand(N: 1);
651 // Replace live-out extracts of WideIV's backedge value by ExitingIVValue
652 // recipes. optimizeInductionLiveOutUsers will later compute the proper
653 // DerivedIV.
654 //
655 // For an IV that requires SCEV predicate, keep extracting the exit values
656 // from the loop directly, as the pre-computed exit value as-is would be
657 // incorrect outside the loop.
658 auto ReplaceExtractsWithExitingIVValueIfPossible = [&](VPWidenInductionRecipe
659 *WideIV) {
660 bool IsPredicated = !WideIV->getNoWrapPredicates().empty();
661 for (VPUser *U : to_vector(Range: BackedgeVal->users())) {
662 if (!match(U, P: m_ExtractLastPart(Op0: m_VPValue())))
663 continue;
664 auto *ExtractLastPart = cast<VPInstruction>(Val: U);
665 VPUser *ExtractLastPartUser = ExtractLastPart->getSingleUser();
666 assert(ExtractLastPartUser && "must have a single user");
667 if (!match(U: ExtractLastPartUser, P: m_ExtractLastLane(Op0: m_VPValue())))
668 continue;
669 auto *ExtractLastLane = cast<VPInstruction>(Val: ExtractLastPartUser);
670 assert(is_contained(ExtractLastLane->getParent()->successors(),
671 Plan.getScalarPreheader()) &&
672 "last lane must be extracted in the middle block");
673 // Keep the vector extract for exit-block live-out uses of a predicated
674 // IV.
675 if (IsPredicated &&
676 any_of(Range: ExtractLastLane->users(), P: [&](VPUser *LaneUser) {
677 auto *R = cast<VPRecipeBase>(Val: LaneUser);
678 return Plan.isExitBlock(VPBB: R->getParent());
679 }))
680 continue;
681 VPBuilder Builder(ExtractLastLane);
682 ExtractLastLane->replaceAllUsesWith(
683 New: Builder.createNaryOp(Opcode: VPInstruction::ExitingIVValue, Operands: {WideIV}));
684 ExtractLastLane->eraseFromParent();
685 ExtractLastPart->eraseFromParent();
686 }
687 };
688
689 if (IndDesc.getKind() == InductionDescriptor::IK_PtrInduction) {
690 auto *WideIV = new VPWidenPointerInductionRecipe(
691 Phi, Start, Step, &Plan.getVFxUF(), IndDesc, DL);
692 ReplaceExtractsWithExitingIVValueIfPossible(WideIV);
693 return WideIV;
694 }
695
696 assert((IndDesc.getKind() == InductionDescriptor::IK_IntInduction ||
697 IndDesc.getKind() == InductionDescriptor::IK_FpInduction) &&
698 "must have an integer or float induction at this point");
699
700 // Update wide induction increments to use the same step as the corresponding
701 // wide induction. This enables detecting induction increments directly in
702 // VPlan and removes redundant splats.
703 if (match(V: BackedgeVal, P: m_Add(Op0: m_Specific(VPV: PhiR), Op1: m_VPValue())))
704 BackedgeVal->getDefiningRecipe()->setOperand(I: 1, New: Step);
705
706 // It is always safe to copy over the NoWrap and FastMath flags. In
707 // particular, when folding tail by masking, the masked-off lanes are never
708 // used, so it is safe.
709 VPIRFlags Flags = vputils::getFlagsFromIndDesc(ID: IndDesc);
710
711 auto *WideIV = new VPWidenIntOrFpInductionRecipe(
712 Phi, Start, Step, &Plan.getVF(), IndDesc, Flags, DL);
713
714 ReplaceExtractsWithExitingIVValueIfPossible(WideIV);
715 return WideIV;
716}
717
718/// Try to sink users of \p FOR after \p Previous. \returns true if sinking
719/// succeeded or was not necessary, and false otherwise.
720static bool
721sinkRecurrenceUsersAfterPrevious(VPFirstOrderRecurrencePHIRecipe *FOR,
722 VPRecipeBase *Previous,
723 const VPDominatorTree &VPDT) {
724 // Collect recipes that need sinking.
725 SmallVector<VPRecipeBase *> WorkList;
726 SmallPtrSet<VPRecipeBase *, 8> Seen;
727 Seen.insert(Ptr: Previous);
728 auto TryToPushSinkCandidate = [&](VPRecipeBase *SinkCandidate) {
729 // The previous value must not depend on the users of the recurrence phi.
730 // In that case, FOR is not a fixed order recurrence.
731 if (SinkCandidate == Previous)
732 return false;
733
734 if (isa<VPHeaderPHIRecipe>(Val: SinkCandidate) ||
735 !Seen.insert(Ptr: SinkCandidate).second ||
736 VPDT.properlyDominates(A: Previous, B: SinkCandidate))
737 return true;
738
739 if (vputils::cannotHoistOrSinkRecipe(R: *SinkCandidate, /*Sinking=*/true))
740 return false;
741
742 WorkList.push_back(Elt: SinkCandidate);
743 return true;
744 };
745
746 // Recursively sink users of FOR after Previous.
747 WorkList.push_back(Elt: FOR);
748 for (unsigned I = 0; I != WorkList.size(); ++I) {
749 VPRecipeBase *Current = WorkList[I];
750 assert(Current->getNumDefinedValues() == 1 &&
751 "only recipes with a single defined value expected");
752
753 for (VPUser *User : Current->getVPSingleValue()->users()) {
754 if (!TryToPushSinkCandidate(cast<VPRecipeBase>(Val: User)))
755 return false;
756 }
757 }
758
759 // Keep recipes to sink ordered by dominance so earlier instructions are
760 // processed first.
761 sort(C&: WorkList, Comp: [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {
762 return VPDT.properlyDominates(A, B);
763 });
764
765 for (VPRecipeBase *SinkCandidate : WorkList) {
766 if (SinkCandidate == FOR)
767 continue;
768
769 SinkCandidate->moveAfter(MovePos: Previous);
770 Previous = SinkCandidate;
771 }
772 return true;
773}
774
775/// Try to hoist \p Previous and its operands before all users of \p FOR.
776/// \returns true if hoisting succeeded or was not necessary, and false
777/// otherwise.
778static bool hoistPreviousBeforeFORUsers(VPFirstOrderRecurrencePHIRecipe *FOR,
779 VPRecipeBase *Previous,
780 const VPDominatorTree &VPDT) {
781 if (vputils::cannotHoistOrSinkRecipe(R: *Previous))
782 return false;
783
784 // Collect recipes that need hoisting.
785 SmallVector<VPRecipeBase *> HoistCandidates;
786 SmallPtrSet<VPRecipeBase *, 8> Visited;
787 // Find the closest hoist point by looking at all users of FOR and selecting
788 // the recipe dominating all other users.
789 VPRecipeBase *HoistPoint = nullptr;
790 for (VPUser *U : FOR->users()) {
791 auto *R = cast<VPRecipeBase>(Val: U);
792 if (!HoistPoint || VPDT.properlyDominates(A: R, B: HoistPoint))
793 HoistPoint = R;
794 }
795 assert(all_of(FOR->users(),
796 [&VPDT, HoistPoint](VPUser *U) {
797 auto *R = cast<VPRecipeBase>(U);
798 return HoistPoint == R ||
799 VPDT.properlyDominates(HoistPoint, R);
800 }) &&
801 "HoistPoint must dominate all users of FOR");
802
803 auto NeedsHoisting = [HoistPoint, &VPDT,
804 &Visited](VPValue *HoistCandidateV) -> VPRecipeBase * {
805 VPRecipeBase *HoistCandidate = HoistCandidateV->getDefiningRecipe();
806 if (!HoistCandidate)
807 return nullptr;
808 // Hoist candidate was already visited, no need to hoist.
809 if (!Visited.insert(Ptr: HoistCandidate).second)
810 return nullptr;
811 // If we reached a recipe that dominates HoistPoint, we don't need to
812 // hoist the recipe.
813 if (VPDT.properlyDominates(A: HoistCandidate, B: HoistPoint))
814 return nullptr;
815 return HoistCandidate;
816 };
817
818 if (!NeedsHoisting(Previous->getVPSingleValue()))
819 return true;
820
821 // Recursively try to hoist Previous and its operands before all users of
822 // FOR.
823 HoistCandidates.push_back(Elt: Previous);
824
825 for (unsigned I = 0; I != HoistCandidates.size(); ++I) {
826 VPRecipeBase *Current = HoistCandidates[I];
827 assert(Current->getNumDefinedValues() == 1 &&
828 "only recipes with a single defined value expected");
829 if (vputils::cannotHoistOrSinkRecipe(R: *Current))
830 return false;
831
832 for (VPValue *Op : Current->operands()) {
833 // If we reach FOR, it means the original Previous depends on some other
834 // recurrence that in turn depends on FOR. If that is the case, we would
835 // also need to hoist recipes involving the other FOR, which may break
836 // dependencies.
837 if (Op == FOR)
838 return false;
839
840 if (auto *R = NeedsHoisting(Op)) {
841 // Bail out if the recipe defines multiple values.
842 // TODO: Hoisting such recipes requires additional handling.
843 if (R->getNumDefinedValues() != 1)
844 return false;
845 HoistCandidates.push_back(Elt: R);
846 }
847 }
848 }
849
850 // Order recipes to hoist by dominance so earlier instructions are processed
851 // first.
852 sort(C&: HoistCandidates, Comp: [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {
853 return VPDT.properlyDominates(A, B);
854 });
855
856 for (VPRecipeBase *HoistCandidate : HoistCandidates) {
857 HoistCandidate->moveBefore(BB&: *HoistPoint->getParent(),
858 I: HoistPoint->getIterator());
859 }
860
861 return true;
862}
863
864/// Sink users of fixed-order recurrences past or hoist before the recipe
865/// defining the previous value, introduce FirstOrderRecurrenceSplice
866/// VPInstructions, and replace FOR uses. Returns false if hoisting or sinking
867/// fails.
868static bool tryToSinkOrHoistRecurrenceUsers(VPBasicBlock *HeaderVPBB,
869 const VPDominatorTree &VPDT) {
870 auto FORs =
871 map_to_vector(C: make_filter_range(Range: HeaderVPBB->phis(),
872 Pred: IsaPred<VPFirstOrderRecurrencePHIRecipe>),
873 F: [](VPRecipeBase &R) {
874 return cast<VPFirstOrderRecurrencePHIRecipe>(Val: &R);
875 });
876 for (VPFirstOrderRecurrencePHIRecipe *FOR : FORs) {
877 // Follow through FOR phi chains to find the actual Previous recipe.
878 // Fixed-order recurrences do not contain cycles, so this loop is
879 // guaranteed to terminate.
880 SmallPtrSet<VPFirstOrderRecurrencePHIRecipe *, 4> SeenPhis;
881 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();
882 while (auto *PrevPhi =
883 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Val: Previous)) {
884 assert(PrevPhi->getParent() == FOR->getParent() &&
885 "PrevPhi must be in same block as FOR");
886 assert(SeenPhis.insert(PrevPhi).second &&
887 "PrevPhi must not be visited multiple times");
888 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();
889 }
890
891 VPBasicBlock *InsertBlock = FOR->getParent();
892 VPBasicBlock::iterator InsertPt = InsertBlock->getFirstNonPhi();
893 if (Previous) {
894 // Sink FOR users after Previous or hoist Previous before FOR users.
895 if (!sinkRecurrenceUsersAfterPrevious(FOR, Previous, VPDT) &&
896 !hoistPreviousBeforeFORUsers(FOR, Previous, VPDT))
897 return false;
898 InsertBlock = Previous->getParent();
899 InsertPt = isa<VPHeaderPHIRecipe>(Val: Previous)
900 ? InsertBlock->getFirstNonPhi()
901 : std::next(x: Previous->getIterator());
902 }
903
904 // Create FirstOrderRecurrenceSplice and replace FOR uses.
905 VPBuilder LoopBuilder(InsertBlock, InsertPt);
906 auto *RecurSplice =
907 LoopBuilder.createNaryOp(Opcode: VPInstruction::FirstOrderRecurrenceSplice,
908 Operands: {FOR, FOR->getBackedgeValue()});
909 FOR->replaceUsesWithIf(New: RecurSplice, ShouldReplace: [RecurSplice](VPUser &U, unsigned) {
910 return &U != RecurSplice;
911 });
912 }
913
914 return true;
915}
916
917bool VPlanTransforms::createHeaderPhiRecipes(
918 VPlan &Plan, PredicatedScalarEvolution &PSE, Loop &OrigLoop,
919 const VPDominatorTree &VPDT,
920 const MapVector<PHINode *, InductionDescriptor> &Inductions,
921 const MapVector<PHINode *, RecurrenceDescriptor> &Reductions,
922 const SmallPtrSetImpl<const PHINode *> &FixedOrderRecurrences,
923 const SmallPtrSetImpl<PHINode *> &InLoopReductions, bool AllowReordering) {
924 // Retrieve the header manually from the intial plain-CFG VPlan.
925 auto [HeaderVPBB, LatchVPBB] = VPBlockUtils::getPlainCFGHeaderAndLatch(Plan);
926 assert(VPDT.dominates(HeaderVPBB, LatchVPBB) &&
927 "header must dominate its latch");
928
929 auto CreateHeaderPhiRecipe = [&](VPPhi *PhiR) -> VPHeaderPHIRecipe * {
930 // TODO: Gradually replace uses of underlying instruction by analyses on
931 // VPlan.
932 auto *Phi = cast<PHINode>(Val: PhiR->getUnderlyingInstr());
933 assert(PhiR->getNumOperands() == 2 &&
934 "Must have 2 operands for header phis");
935
936 // Extract common values once.
937 VPIRValue *Start = cast<VPIRValue>(Val: PhiR->getOperand(N: 0));
938 VPValue *BackedgeValue = PhiR->getOperand(N: 1);
939
940 if (FixedOrderRecurrences.contains(Ptr: Phi)) {
941 // TODO: Currently fixed-order recurrences are modeled as chains of
942 // first-order recurrences. If there are no users of the intermediate
943 // recurrences in the chain, the fixed order recurrence should be
944 // modeled directly, enabling more efficient codegen.
945 return new VPFirstOrderRecurrencePHIRecipe(Phi, *Start, *BackedgeValue);
946 }
947
948 auto InductionIt = Inductions.find(Key: Phi);
949 if (InductionIt != Inductions.end())
950 return createWidenInductionRecipe(Phi, PhiR, Start, IndDesc: InductionIt->second,
951 Plan, PSE, OrigLoop,
952 DL: PhiR->getDebugLoc());
953
954 assert(Reductions.contains(Phi) && "only reductions are expected now");
955 const RecurrenceDescriptor &RdxDesc = Reductions.lookup(Key: Phi);
956 assert(RdxDesc.getRecurrenceStartValue() ==
957 Phi->getIncomingValueForBlock(OrigLoop.getLoopPreheader()) &&
958 "incoming value must match start value");
959 // Will be updated later to >1 if reduction is partial.
960 unsigned ScaleFactor = 1;
961 bool UseOrderedReductions = !AllowReordering && RdxDesc.isOrdered();
962 return new VPReductionPHIRecipe(
963 Phi, RdxDesc.getRecurrenceKind(), *Start, *BackedgeValue,
964 getReductionStyle(InLoop: InLoopReductions.contains(Ptr: Phi), Ordered: UseOrderedReductions,
965 ScaleFactor),
966 Phi->getType()->isFloatingPointTy() ? RdxDesc.getFastMathFlags()
967 : VPIRFlags(),
968 RdxDesc.hasUsesOutsideReductionChain());
969 };
970
971 for (VPRecipeBase &R : make_early_inc_range(Range: HeaderVPBB->phis())) {
972 auto *PhiR = cast<VPPhi>(Val: &R);
973 VPHeaderPHIRecipe *HeaderPhiR = CreateHeaderPhiRecipe(PhiR);
974 HeaderPhiR->insertBefore(InsertPos: PhiR);
975 PhiR->replaceAllUsesWith(New: HeaderPhiR);
976 PhiR->eraseFromParent();
977 }
978
979 if (!tryToSinkOrHoistRecurrenceUsers(HeaderVPBB, VPDT))
980 return false;
981
982 // Skip renaming resume phi recipes, if any header phi has been removed.
983 if (range_size(Range: HeaderVPBB->phis()) !=
984 range_size(Range: Plan.getScalarPreheader()->phis()))
985 return true;
986 for (const auto &[HeaderPhiR, ScalarPhiR] :
987 zip_equal(t: HeaderVPBB->phis(), u: Plan.getScalarPreheader()->phis())) {
988 auto *ResumePhiR = cast<VPPhi>(Val: &ScalarPhiR);
989 if (isa<VPFirstOrderRecurrencePHIRecipe>(Val: &HeaderPhiR)) {
990 ResumePhiR->setName("scalar.recur.init");
991 auto *ExtractLastLane = cast<VPInstruction>(Val: ResumePhiR->getOperand(N: 0));
992 ExtractLastLane->setName("vector.recur.extract");
993 continue;
994 }
995 ResumePhiR->setName(isa<VPWidenInductionRecipe>(Val: HeaderPhiR)
996 ? "bc.resume.val"
997 : "bc.merge.rdx");
998 }
999 return true;
1000}
1001
1002bool VPlanTransforms::finalizeSCEVPredicates(VPlan &Plan,
1003 PredicatedScalarEvolution &PSE,
1004 bool OptForSize,
1005 unsigned SCEVCheckThreshold,
1006 OptimizationRemarkEmitter *ORE,
1007 Loop *TheLoop) {
1008 // Collect which wide IVs have predicates and add them to PSE.
1009 auto [HeaderVPBB, _] = VPBlockUtils::getPlainCFGHeaderAndLatch(Plan);
1010 SmallPtrSet<VPWidenInductionRecipe *, 4> PredicatedIVs;
1011 for (auto &R : HeaderVPBB->phis()) {
1012 auto *WideIV = dyn_cast<VPWidenInductionRecipe>(Val: &R);
1013 if (!WideIV || WideIV->getNoWrapPredicates().empty())
1014 continue;
1015 PredicatedIVs.insert(Ptr: WideIV);
1016 for (const auto *P : WideIV->getNoWrapPredicates())
1017 PSE.addPredicate(Pred: *P);
1018 }
1019
1020 unsigned TotalComplexity = PSE.getPredicate().getComplexity();
1021 if (TotalComplexity && OptForSize) {
1022 LLVM_DEBUG(
1023 dbgs() << "LV: Not vectorizing: SCEV predicates needed for induction "
1024 "but optimizing for size\n");
1025 reportVectorizationFailure(
1026 DebugMsg: "Runtime SCEV check is required with -Os/-Oz",
1027 OREMsg: "runtime SCEV checks needed but optimizing for size",
1028 ORETag: "CantVersionLoopWithOptForSize", ORE, TheLoop);
1029 return false;
1030 }
1031
1032 if (TotalComplexity > SCEVCheckThreshold) {
1033 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Too many SCEV checks needed ("
1034 << TotalComplexity << " > " << SCEVCheckThreshold
1035 << ")\n");
1036 reportVectorizationFailure(
1037 DebugMsg: "Too many SCEV checks needed",
1038 OREMsg: "Too many SCEV assumptions need to be made and checked at runtime",
1039 ORETag: "TooManySCEVRunTimeChecks", ORE, TheLoop);
1040 return false;
1041 }
1042
1043 return true;
1044}
1045
1046void VPlanTransforms::createInLoopReductionRecipes(VPlan &Plan,
1047 ElementCount MinVF) {
1048 VPBasicBlock *Header = Plan.getVectorLoopRegion()->getEntryBasicBlock();
1049 SmallVector<VPRecipeBase *> ToDelete;
1050
1051 for (VPRecipeBase &R : Header->phis()) {
1052 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(Val: &R);
1053 if (!PhiR || !PhiR->isInLoop() || (MinVF.isScalar() && !PhiR->isOrdered()))
1054 continue;
1055
1056 RecurKind Kind = PhiR->getRecurrenceKind();
1057 assert(!RecurrenceDescriptor::isFindLastRecurrenceKind(Kind) &&
1058 !RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) &&
1059 !RecurrenceDescriptor::isFindIVRecurrenceKind(Kind) &&
1060 "AnyOf and Find reductions are not allowed for in-loop reductions");
1061
1062 bool IsFPRecurrence =
1063 RecurrenceDescriptor::isFloatingPointRecurrenceKind(Kind);
1064 FastMathFlags FMFs =
1065 IsFPRecurrence ? FastMathFlags::getFast() : FastMathFlags();
1066
1067 // Collect the chain of "link" recipes for the reduction starting at PhiR.
1068 SetVector<VPSingleDefRecipe *> Worklist;
1069 Worklist.insert(X: PhiR);
1070 for (unsigned I = 0; I != Worklist.size(); ++I) {
1071 VPSingleDefRecipe *Cur = Worklist[I];
1072 for (VPUser *U : Cur->users()) {
1073 auto *UserRecipe = cast<VPSingleDefRecipe>(Val: U);
1074 if (!UserRecipe->getParent()->getEnclosingLoopRegion()) {
1075 assert((UserRecipe->getParent() == Plan.getMiddleBlock() ||
1076 UserRecipe->getParent() == Plan.getScalarPreheader()) &&
1077 "U must be either in the loop region, the middle block or the "
1078 "scalar preheader.");
1079 continue;
1080 }
1081
1082 // Stores using instructions will be sunk later.
1083 if (match(R: UserRecipe, P: m_VPInstruction<Instruction::Store>()))
1084 continue;
1085 Worklist.insert(X: UserRecipe);
1086 }
1087 }
1088
1089 // Visit operation "Links" along the reduction chain top-down starting from
1090 // the phi until LoopExitValue. We keep track of the previous item
1091 // (PreviousLink) to tell which of the two operands of a Link will remain
1092 // scalar and which will be reduced. For minmax by select(cmp), Link will be
1093 // the select instructions. Blend recipes of in-loop reduction phi's will
1094 // get folded to their non-phi operand, as the reduction recipe handles the
1095 // condition directly.
1096 VPSingleDefRecipe *PreviousLink = PhiR; // Aka Worklist[0].
1097 for (VPSingleDefRecipe *CurrentLink : drop_begin(RangeOrContainer&: Worklist)) {
1098 if (auto *Blend = dyn_cast<VPBlendRecipe>(Val: CurrentLink)) {
1099 assert(Blend->getNumIncomingValues() == 2 &&
1100 "Blend must have 2 incoming values");
1101 unsigned PhiRIdx = Blend->getIncomingValue(Idx: 0) == PhiR ? 0 : 1;
1102 assert(Blend->getIncomingValue(PhiRIdx) == PhiR &&
1103 "PhiR must be an operand of the blend");
1104 Blend->replaceAllUsesWith(New: Blend->getIncomingValue(Idx: 1 - PhiRIdx));
1105 continue;
1106 }
1107
1108 if (IsFPRecurrence) {
1109 FastMathFlags CurFMF =
1110 cast<VPRecipeWithIRFlags>(Val: CurrentLink)->getFastMathFlagsOrNone();
1111 if (match(R: CurrentLink, P: m_Select(Op0: m_VPValue(), Op1: m_VPValue(), Op2: m_VPValue())))
1112 CurFMF |= cast<VPRecipeWithIRFlags>(Val: CurrentLink->getOperand(N: 0))
1113 ->getFastMathFlagsOrNone();
1114 FMFs &= CurFMF;
1115 }
1116
1117 Instruction *CurrentLinkI = CurrentLink->getUnderlyingInstr();
1118
1119 // Recognize a call to the llvm.fmuladd intrinsic.
1120 bool IsFMulAdd = Kind == RecurKind::FMulAdd;
1121 VPValue *VecOp;
1122 VPBasicBlock *LinkVPBB = CurrentLink->getParent();
1123 if (IsFMulAdd) {
1124 assert(RecurrenceDescriptor::isFMulAddIntrinsic(CurrentLinkI) &&
1125 "Expected current VPInstruction to be a call to the "
1126 "llvm.fmuladd intrinsic");
1127 assert(CurrentLink->getOperand(2) == PreviousLink &&
1128 "expected a call where the previous link is the added operand");
1129
1130 // If the instruction is a call to the llvm.fmuladd intrinsic then we
1131 // need to create an fmul recipe (multiplying the first two operands of
1132 // the fmuladd together) to use as the vector operand for the fadd
1133 // reduction.
1134 auto *FMulRecipe = new VPInstruction(
1135 Instruction::FMul,
1136 {CurrentLink->getOperand(N: 0), CurrentLink->getOperand(N: 1)},
1137 CurrentLinkI->getFastMathFlags());
1138 LinkVPBB->insert(Recipe: FMulRecipe, InsertPt: CurrentLink->getIterator());
1139 VecOp = FMulRecipe;
1140 } else if (Kind == RecurKind::AddChainWithSubs &&
1141 match(R: CurrentLink, P: m_Sub(Op0: m_VPValue(), Op1: m_VPValue()))) {
1142 Type *PhiTy = PhiR->getScalarType();
1143 auto *Zero = Plan.getConstantInt(Ty: PhiTy, Val: 0);
1144 VPBuilder Builder(LinkVPBB, CurrentLink->getIterator());
1145 auto *Sub = Builder.createSub(LHS: Zero, RHS: CurrentLink->getOperand(N: 1),
1146 DL: CurrentLinkI->getDebugLoc());
1147 Sub->setUnderlyingValue(CurrentLinkI);
1148 VecOp = Sub;
1149 } else {
1150 // Index of the first operand which holds a non-mask vector operand.
1151 unsigned IndexOfFirstOperand = 0;
1152 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind)) {
1153 if (match(R: CurrentLink, P: m_Cmp(Op0: m_VPValue(), Op1: m_VPValue())))
1154 continue;
1155 assert(match(CurrentLink,
1156 m_Select(m_VPValue(), m_VPValue(), m_VPValue())) &&
1157 "must be a select recipe");
1158 IndexOfFirstOperand = 1;
1159 }
1160 // Note that for non-commutable operands (cmp-selects), the semantics of
1161 // the cmp-select are captured in the recurrence kind.
1162 unsigned VecOpId =
1163 CurrentLink->getOperand(N: IndexOfFirstOperand) == PreviousLink
1164 ? IndexOfFirstOperand + 1
1165 : IndexOfFirstOperand;
1166 VecOp = CurrentLink->getOperand(N: VecOpId);
1167 assert(
1168 VecOp != PreviousLink &&
1169 CurrentLink->getOperand(
1170 cast<VPInstruction>(CurrentLink)->getNumOperandsWithoutMask() -
1171 1 - (VecOpId - IndexOfFirstOperand)) == PreviousLink &&
1172 "PreviousLink must be the operand other than VecOp");
1173 }
1174
1175 assert(PhiR->getVFScaleFactor() == 1 &&
1176 "inloop reductions must be unscaled");
1177 VPValue *CondOp = cast<VPInstruction>(Val: CurrentLink)->getMask();
1178 auto *RedRecipe = new VPReductionRecipe(
1179 Kind, FMFs, CurrentLinkI, PreviousLink, VecOp, CondOp,
1180 getReductionStyle(/*IsInLoop=*/InLoop: true, Ordered: PhiR->isOrdered(), ScaleFactor: 1),
1181 CurrentLinkI->getDebugLoc());
1182 // Append the recipe to the end of the VPBasicBlock because we need to
1183 // ensure that it comes after all of it's inputs, including CondOp.
1184 // Delete CurrentLink as it will be invalid if its operand is replaced
1185 // with a reduction defined at the bottom of the block in the next link.
1186 if (LinkVPBB->getNumSuccessors() == 0)
1187 RedRecipe->insertBefore(InsertPos: &*std::prev(x: std::prev(x: LinkVPBB->end())));
1188 else
1189 LinkVPBB->appendRecipe(Recipe: RedRecipe);
1190
1191 CurrentLink->replaceAllUsesWith(New: RedRecipe);
1192 // Move any store recipes using the RedRecipe that appear before it in the
1193 // same block to just after the RedRecipe.
1194 for (VPUser *U : make_early_inc_range(Range: RedRecipe->users())) {
1195 auto *UserR = dyn_cast<VPRecipeBase>(Val: U);
1196 if (!UserR || UserR->getParent() != LinkVPBB)
1197 continue;
1198 if (!match(V: UserR, P: m_VPInstruction<Instruction::Store>()))
1199 continue;
1200 UserR->moveAfter(MovePos: RedRecipe);
1201 }
1202 ToDelete.push_back(Elt: CurrentLink);
1203 PreviousLink = RedRecipe;
1204 }
1205 }
1206
1207 for (VPRecipeBase *R : ToDelete)
1208 R->eraseFromParent();
1209}
1210
1211/// Check if all loads in the loop are dereferenceable. Iterates over the
1212/// loop body blocks reachable from \p HeaderVPBB. Returns false if any
1213/// non-dereferenceable load is found.
1214static bool areAllLoadsDereferenceable(VPBasicBlock *HeaderVPBB, Loop *TheLoop,
1215 PredicatedScalarEvolution &PSE,
1216 DominatorTree &DT, AssumptionCache *AC) {
1217 ScalarEvolution &SE = *PSE.getSE();
1218 const DataLayout &DL = TheLoop->getHeader()->getDataLayout();
1219 for (VPBasicBlock *VPBB : vp_rpo_plain_cfg_loop_body(Header: HeaderVPBB)) {
1220 for (VPRecipeBase &R : *VPBB) {
1221 auto *VPI = dyn_cast<VPInstructionWithType>(Val: &R);
1222 if (!VPI || VPI->getOpcode() != Instruction::Load) {
1223 assert(!R.mayReadFromMemory() && "unexpected recipe reading memory");
1224 continue;
1225 }
1226
1227 // Get the pointer SCEV for dereferenceability checking.
1228 VPValue *Ptr = VPI->getOperand(N: 0);
1229 const SCEV *PtrSCEV = vputils::getSCEVExprForVPValue(V: Ptr, PSE, L: TheLoop);
1230 if (isa<SCEVCouldNotCompute>(Val: PtrSCEV)) {
1231 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Found non-dereferenceable "
1232 "load with SCEVCouldNotCompute pointer\n");
1233 return false;
1234 }
1235
1236 // Check dereferenceability using the SCEV-based version.
1237 Type *LoadTy = VPI->getScalarType();
1238 const SCEV *SizeSCEV =
1239 SE.getStoreSizeOfExpr(IntTy: DL.getIndexType(PtrTy: PtrSCEV->getType()), StoreTy: LoadTy);
1240 auto *Load = cast<LoadInst>(Val: VPI->getUnderlyingValue());
1241 SmallVector<const SCEVPredicate *> Preds;
1242 if (isDereferenceableAndAlignedInLoop(PtrSCEV, Alignment: Load->getAlign(), EltSizeSCEV: SizeSCEV,
1243 L: TheLoop, SE, DT, AC, Predicates: &Preds))
1244 continue;
1245
1246 LLVM_DEBUG(
1247 dbgs() << "LV: Not vectorizing: Auto-vectorization of loops with "
1248 "potentially faulting load is not supported.\n");
1249 return false;
1250 }
1251 }
1252 return true;
1253}
1254
1255bool VPlanTransforms::handleEarlyExits(VPlan &Plan, UncountableExitStyle Style,
1256 Loop *TheLoop,
1257 PredicatedScalarEvolution &PSE,
1258 DominatorTree &DT, AssumptionCache *AC) {
1259 auto *MiddleVPBB = VPBlockUtils::getPlainCFGMiddleBlock(Plan);
1260 auto [HeaderVPBB, LatchVPBB] = VPBlockUtils::getPlainCFGHeaderAndLatch(Plan);
1261
1262 // TODO: We would like to detect uncountable exits and stores within loops
1263 // with such exits from the VPlan alone. Exit detection can be moved
1264 // here from handleUncountableEarlyExits, but we need to improve
1265 // detection of recipes which may write to memory.
1266 if (Style != UncountableExitStyle::NoUncountableExit) {
1267 // Dereferenceability is checked separately for uncountable exit loops with
1268 // stores, as only the loads contributing to the exit condition need to
1269 // be checked.
1270 if (Style == UncountableExitStyle::ReadOnly &&
1271 !areAllLoadsDereferenceable(HeaderVPBB, TheLoop, PSE, DT, AC))
1272 return false;
1273 // TODO: Check target preference for style.
1274 return handleUncountableEarlyExits(Plan, HeaderVPBB, LatchVPBB, MiddleVPBB,
1275 TheLoop, PSE, DT, AC, Style);
1276 }
1277
1278 // Disconnect countable early exits from the loop, leaving it with a single
1279 // exit from the latch. Countable early exits are left for a scalar epilog.
1280 for (VPIRBasicBlock *EB : Plan.getExitBlocks()) {
1281 for (VPBlockBase *Pred : to_vector(Range&: EB->getPredecessors())) {
1282 if (Pred == MiddleVPBB)
1283 continue;
1284
1285 // Remove phi operands for the early exiting block.
1286 for (VPRecipeBase &R : EB->phis())
1287 cast<VPIRPhi>(Val: &R)->removeIncomingValueFor(IncomingBlock: Pred);
1288 auto *EarlyExitingVPBB = cast<VPBasicBlock>(Val: Pred);
1289 EarlyExitingVPBB->getTerminator()->eraseFromParent();
1290 VPBlockUtils::disconnectBlocks(From: Pred, To: EB);
1291 }
1292 }
1293 return true;
1294}
1295
1296void VPlanTransforms::addMiddleCheck(VPlan &Plan) {
1297 auto *MiddleVPBB = VPBlockUtils::getPlainCFGMiddleBlock(Plan);
1298 // If MiddleVPBB has a single successor then the original loop does not exit
1299 // via the latch and the single successor must be the scalar preheader.
1300 // There's no need to add a runtime check to MiddleVPBB.
1301 if (MiddleVPBB->getNumSuccessors() == 1) {
1302 assert(MiddleVPBB->getSingleSuccessor() == Plan.getScalarPreheader() &&
1303 "must have ScalarPH as single successor");
1304 return;
1305 }
1306
1307 assert(MiddleVPBB->getNumSuccessors() == 2 && "must have 2 successors");
1308
1309 // Add a check in the middle block to see if we have completed all of the
1310 // iterations in the first vector loop.
1311 //
1312 // Three cases:
1313 // 1) If we require a scalar epilogue, the scalar ph must execute. Set the
1314 // condition to false.
1315 // 2) If (N - N%VF) == N, then we *don't* need to run the
1316 // remainder. Thus if tail is to be folded, we know we don't need to run
1317 // the remainder and we can set the condition to true.
1318 // 3) Otherwise, construct a runtime check.
1319
1320 // We use the same DebugLoc as the scalar loop latch terminator instead of
1321 // the corresponding compare because they may have ended up with different
1322 // line numbers and we want to avoid awkward line stepping while debugging.
1323 // E.g., if the compare has got a line number inside the loop.
1324 auto *LatchVPBB = cast<VPBasicBlock>(Val: MiddleVPBB->getSinglePredecessor());
1325 DebugLoc LatchDL = LatchVPBB->getTerminator()->getDebugLoc();
1326 VPBuilder Builder(MiddleVPBB);
1327 VPValue *Cmp =
1328 Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: Plan.getTripCount(),
1329 B: &Plan.getVectorTripCount(), DL: LatchDL, Name: "cmp.n");
1330 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cmp}, DL: LatchDL);
1331}
1332
1333void VPlanTransforms::createLoopRegions(VPlan &Plan, DebugLoc DL) {
1334 VPDominatorTree VPDT(Plan);
1335 PostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> POT(
1336 Plan.getEntry());
1337 for (VPBlockBase *HeaderVPB : POT)
1338 if (canonicalHeaderAndLatch(HeaderVPB, VPDT))
1339 createLoopRegion(Plan, HeaderVPB, DL);
1340
1341 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
1342 TopRegion->setName("vector loop");
1343 TopRegion->getEntryBasicBlock()->setName("vector.body");
1344}
1345
1346void VPlanTransforms::foldTailByMasking(VPlan &Plan) {
1347 assert(Plan.getExitBlocks().size() == 1 &&
1348 "only a single-exit block is supported currently");
1349 assert(Plan.getExitBlocks().front()->getSinglePredecessor() ==
1350 Plan.getMiddleBlock() &&
1351 "the exit block must have middle block as single predecessor");
1352
1353 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
1354 assert(LoopRegion->getSingleSuccessor() == Plan.getMiddleBlock() &&
1355 "The vector loop region must have the middle block as its single "
1356 "successor for now");
1357 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
1358
1359 Header->splitAt(SplitAt: Header->getFirstNonPhi());
1360
1361 // Abstract header mask, materialized into concrete recipes later.
1362 VPValue *HeaderMask = LoopRegion->createHeaderMask();
1363 VPBuilder Builder(Header, Header->getFirstNonPhi());
1364 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: HeaderMask);
1365
1366 VPBasicBlock *OrigLatch = LoopRegion->getExitingBasicBlock();
1367 VPValue *IVInc;
1368 [[maybe_unused]] bool TermBranchOnCount =
1369 match(V: OrigLatch->getTerminator(),
1370 P: m_BranchOnCount(Op0: m_VPValue(V&: IVInc),
1371 Op1: m_Specific(VPV: &Plan.getVectorTripCount())));
1372 assert(TermBranchOnCount &&
1373 match(IVInc, m_Add(m_Specific(LoopRegion->getCanonicalIV()),
1374 m_Specific(&Plan.getVFxUF()))) &&
1375 std::next(IVInc->getDefiningRecipe()->getIterator()) ==
1376 OrigLatch->getTerminator()->getIterator() &&
1377 "Unexpected canonical iv increment");
1378
1379 // Split the latch at the IV update, and branch to it from the header mask.
1380 VPBasicBlock *Latch =
1381 OrigLatch->splitAt(SplitAt: IVInc->getDefiningRecipe()->getIterator());
1382 Latch->setName("vector.latch");
1383 VPBlockUtils::connectBlocks(From: Header, To: Latch);
1384
1385 // Collect any values defined in the loop that need a phi. Currently this
1386 // includes header phi backedges and live-outs extracted in the middle block.
1387 // TODO: Handle early exits via Plan.getExitBlocks()
1388 MapVector<VPValue *, SmallVector<VPUser *>> NeedsPhi;
1389 for (VPRecipeBase &R : Header->phis())
1390 if (!isa<VPWidenInductionRecipe>(Val: R))
1391 NeedsPhi[cast<VPHeaderPHIRecipe>(Val&: R).getBackedgeValue()].push_back(Elt: &R);
1392
1393 VPValue *V;
1394 for (VPRecipeBase &R : *Plan.getMiddleBlock())
1395 if (match(V: &R, P: m_ExtractLastPart(Op0: m_VPValue(V))))
1396 NeedsPhi[V].push_back(Elt: &R);
1397
1398 // Insert phis for values coming past the end of the tail.
1399 Builder.setInsertPoint(TheBB: Latch, IP: Latch->begin());
1400 for (const auto &[V, Users] : NeedsPhi) {
1401 if (isa<VPIRValue>(Val: V))
1402 continue;
1403 VPValue *TailVal = Plan.getPoison(Ty: V->getScalarType());
1404 VPIRFlags Flags;
1405 assert(llvm::count_if(Users, IsaPred<VPReductionPHIRecipe>) <= 1 &&
1406 "Value used by more than two reduction phis?");
1407 auto *RedIt = find_if(Range: Users, P: IsaPred<VPReductionPHIRecipe>);
1408 auto *RdxPhi =
1409 RedIt != Users.end() ? cast<VPReductionPHIRecipe>(Val: *RedIt) : nullptr;
1410 if (RdxPhi && !RdxPhi->isInLoop()) {
1411 TailVal = RdxPhi;
1412 Flags = *RdxPhi;
1413 }
1414
1415 VPInstruction *Phi = Builder.createScalarPhi(IncomingValues: {V, TailVal}, DL: {}, Name: "", Flags);
1416 for (VPUser *U : Users)
1417 U->replaceUsesOfWith(From: V, To: Phi);
1418 }
1419
1420 // Any extract of the last element must be updated to extract from the last
1421 // active lane of the header mask instead (i.e., the lane corresponding to the
1422 // last active iteration).
1423 Builder.setInsertPoint(Plan.getMiddleBlock()->getTerminator());
1424 for (VPRecipeBase &R : *Plan.getMiddleBlock()) {
1425 VPValue *Op;
1426 if (!match(V: &R, P: m_ExtractLastLaneOfLastPart(Op0: m_VPValue(V&: Op))))
1427 continue;
1428
1429 // Compute the index of the last active lane.
1430 VPValue *LastActiveLane = Builder.createLastActiveLane(Masks: HeaderMask);
1431 auto *Ext =
1432 Builder.createNaryOp(Opcode: VPInstruction::ExtractLane, Operands: {LastActiveLane, Op});
1433 R.getVPSingleValue()->replaceAllUsesWith(New: Ext);
1434 }
1435
1436 // VectorTripCount now equals TripCount so simplify the MiddleVPBB branch.
1437 assert(match(Plan.getMiddleBlock()->getTerminator(),
1438 m_BranchOnCond(m_SpecificICmp(
1439 CmpInst::ICMP_EQ, m_Specific(Plan.getTripCount()),
1440 m_Specific(&Plan.getVectorTripCount())))) &&
1441 "Unexpected MiddleVPBB branch");
1442 Plan.getMiddleBlock()->getTerminator()->setOperand(I: 0, New: Plan.getTrue());
1443}
1444
1445/// Insert \p CheckBlockVPBB on the edge leading to the vector preheader,
1446/// connecting it to both vector and scalar preheaders. Updates scalar
1447/// preheader phis to account for the new predecessor.
1448static void insertCheckBlockBeforeVectorLoop(VPlan &Plan,
1449 VPBasicBlock *CheckBlockVPBB) {
1450 VPBlockBase *VectorPH = Plan.getVectorPreheader();
1451 auto *ScalarPH = cast<VPBasicBlock>(Val: Plan.getScalarPreheader());
1452 VPBlockBase *PreVectorPH = VectorPH->getSinglePredecessor();
1453 VPBlockUtils::insertOnEdge(From: PreVectorPH, To: VectorPH, BlockPtr: CheckBlockVPBB);
1454 VPBlockUtils::connectBlocks(From: CheckBlockVPBB, To: ScalarPH);
1455 CheckBlockVPBB->swapSuccessors();
1456 unsigned NumPreds = ScalarPH->getNumPredecessors();
1457 for (VPRecipeBase &R : ScalarPH->phis()) {
1458 auto *Phi = cast<VPPhi>(Val: &R);
1459 assert(Phi->getNumIncoming() == NumPreds - 1 &&
1460 "must have incoming values for all predecessors");
1461 Phi->addIncoming(IncomingV: Phi->getOperand(N: NumPreds - 2));
1462 }
1463}
1464
1465// Likelyhood of bypassing the vectorized loop due to a runtime check block,
1466// including memory overlap checks block and wrapping/unit-stride checks block.
1467static constexpr uint32_t CheckBypassWeights[] = {1, 127};
1468
1469/// Create a BranchOnCond terminator in \p CheckBlockVPBB. Optionally adds
1470/// branch weights.
1471static void addBypassBranch(VPlan &Plan, VPBasicBlock *CheckBlockVPBB,
1472 VPValue *Cond, bool AddBranchWeights) {
1473 DebugLoc DL = Plan.getVectorLoopRegion()->getCanonicalIV()->getDebugLoc();
1474 auto *Term = VPBuilder(CheckBlockVPBB)
1475 .createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cond}, DL);
1476 if (AddBranchWeights) {
1477 MDBuilder MDB(Plan.getContext());
1478 MDNode *BranchWeights =
1479 MDB.createBranchWeights(Weights: CheckBypassWeights, /*IsExpected=*/false);
1480 Term->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1481 }
1482}
1483
1484void VPlanTransforms::attachVPCheckBlock(VPlan &Plan, VPValue *Cond,
1485 VPBasicBlock *CheckBlock,
1486 bool AddBranchWeights) {
1487 insertCheckBlockBeforeVectorLoop(Plan, CheckBlockVPBB: CheckBlock);
1488 addBypassBranch(Plan, CheckBlockVPBB: CheckBlock, Cond, AddBranchWeights);
1489}
1490
1491void VPlanTransforms::attachCheckBlock(VPlan &Plan, Value *Cond,
1492 BasicBlock *CheckBlock,
1493 bool AddBranchWeights) {
1494 VPValue *CondVPV = Plan.getOrAddLiveIn(V: Cond);
1495 VPBasicBlock *CheckBlockVPBB = Plan.createVPIRBasicBlock(IRBB: CheckBlock);
1496 attachVPCheckBlock(Plan, Cond: CondVPV, CheckBlock: CheckBlockVPBB, AddBranchWeights);
1497}
1498
1499void VPlanTransforms::addMinimumIterationCheck(
1500 VPlan &Plan, ElementCount VF, unsigned UF,
1501 ElementCount MinProfitableTripCount, bool RequiresScalarEpilogue,
1502 bool TailFolded, Loop *OrigLoop, const uint32_t *MinItersBypassWeights,
1503 DebugLoc DL, PredicatedScalarEvolution &PSE, VPBasicBlock *CheckBlock) {
1504 // Generate code to check if the loop's trip count is less than VF * UF, or
1505 // equal to it in case a scalar epilogue is required; this implies that the
1506 // vector trip count is zero. This check also covers the case where adding one
1507 // to the backedge-taken count overflowed leading to an incorrect trip count
1508 // of zero. In this case we will also jump to the scalar loop.
1509 CmpInst::Predicate CmpPred =
1510 RequiresScalarEpilogue ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
1511 // If tail is to be folded, vector loop takes care of all iterations.
1512 VPValue *TripCountVPV = Plan.getTripCount();
1513 const SCEV *TripCount = vputils::getSCEVExprForVPValue(V: TripCountVPV, PSE);
1514 Type *TripCountTy = TripCount->getType();
1515 ScalarEvolution &SE = *PSE.getSE();
1516 auto GetMinTripCount = [&]() -> const SCEV * {
1517 // Compute max(MinProfitableTripCount, UF * VF) and return it.
1518 const SCEV *VFxUF =
1519 SE.getElementCount(Ty: TripCountTy, EC: (VF * UF), Flags: SCEV::FlagNUW);
1520 if (UF * VF.getKnownMinValue() >=
1521 MinProfitableTripCount.getKnownMinValue()) {
1522 // TODO: SCEV should be able to simplify test.
1523 return VFxUF;
1524 }
1525 const SCEV *MinProfitableTripCountSCEV =
1526 SE.getElementCount(Ty: TripCountTy, EC: MinProfitableTripCount, Flags: SCEV::FlagNUW);
1527 return SE.getUMaxExpr(LHS: MinProfitableTripCountSCEV, RHS: VFxUF);
1528 };
1529
1530 VPBuilder Builder(CheckBlock);
1531 VPValue *TripCountCheck = Plan.getFalse();
1532 const SCEV *Step = GetMinTripCount();
1533 // TripCountCheck = false, folding tail implies positive vector trip
1534 // count.
1535 if (!TailFolded) {
1536 // TODO: Emit unconditional branch to vector preheader instead of
1537 // conditional branch with known condition.
1538 TripCount = SE.applyLoopGuards(Expr: TripCount, L: OrigLoop);
1539 // Check if the trip count is < the step.
1540 if (SE.isKnownPredicate(Pred: CmpPred, LHS: TripCount, RHS: Step)) {
1541 // TODO: Ensure step is at most the trip count when determining max VF and
1542 // UF, w/o tail folding.
1543 TripCountCheck = Plan.getTrue();
1544 } else if (!SE.isKnownPredicate(Pred: CmpInst::getInversePredicate(pred: CmpPred),
1545 LHS: TripCount, RHS: Step)) {
1546 // Generate the minimum iteration check only if we cannot prove the
1547 // check is known to be true, or known to be false.
1548 // Try to expand Step into VPInstructions in CheckBlock; otherwise fall
1549 // back to a VPExpandSCEV recipe in the plan's entry block.
1550 VPValue *MinTripCountVPV =
1551 VPSCEVExpander(Builder, *PSE.getSE(), DL).tryToExpand(S: Step);
1552 if (!MinTripCountVPV)
1553 MinTripCountVPV = VPBuilder(Plan.getEntry()).createExpandSCEV(Expr: Step);
1554 TripCountCheck = Builder.createICmp(
1555 Pred: CmpPred, A: TripCountVPV, B: MinTripCountVPV, DL, Name: "min.iters.check");
1556 } // else step known to be < trip count, use TripCountCheck preset to false.
1557 }
1558 VPInstruction *Term =
1559 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {TripCountCheck}, DL);
1560 if (MinItersBypassWeights) {
1561 MDBuilder MDB(Plan.getContext());
1562 MDNode *BranchWeights = MDB.createBranchWeights(
1563 Weights: ArrayRef(MinItersBypassWeights, 2), /*IsExpected=*/false);
1564 Term->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1565 }
1566}
1567
1568void VPlanTransforms::addIterationCountCheckBlock(
1569 VPlan &Plan, ElementCount VF, unsigned UF, bool RequiresScalarEpilogue,
1570 Loop *OrigLoop, const uint32_t *MinItersBypassWeights, DebugLoc DL,
1571 PredicatedScalarEvolution &PSE) {
1572 auto *CheckBlock = Plan.createVPBasicBlock(Name: "vector.main.loop.iter.check");
1573 insertCheckBlockBeforeVectorLoop(Plan, CheckBlockVPBB: CheckBlock);
1574 addMinimumIterationCheck(Plan, VF, UF, MinProfitableTripCount: ElementCount::getFixed(MinVal: 0),
1575 RequiresScalarEpilogue, /*TailFolded=*/false,
1576 OrigLoop, MinItersBypassWeights, DL, PSE,
1577 CheckBlock);
1578}
1579
1580void VPlanTransforms::addMinimumVectorEpilogueIterationCheck(
1581 VPlan &Plan, Value *VectorTripCount, bool RequiresScalarEpilogue,
1582 ElementCount EpilogueVF, unsigned EpilogueUF, unsigned MainLoopStep,
1583 unsigned EpilogueLoopStep, ScalarEvolution &SE) {
1584 // Add the minimum iteration check for the epilogue vector loop.
1585 VPValue *TC = Plan.getTripCount();
1586 Value *TripCount = TC->getLiveInIRValue();
1587 VPBuilder Builder(cast<VPBasicBlock>(Val: Plan.getEntry()));
1588 VPValue *VFxUF = Builder.createExpandSCEV(Expr: SE.getElementCount(
1589 Ty: TripCount->getType(), EC: (EpilogueVF * EpilogueUF), Flags: SCEV::FlagNUW));
1590 VPValue *Count = Builder.createSub(LHS: TC, RHS: Plan.getOrAddLiveIn(V: VectorTripCount),
1591 DL: DebugLoc::getUnknown(), Name: "n.vec.remaining");
1592
1593 // Generate code to check if the loop's trip count is less than VF * UF of
1594 // the vector epilogue loop.
1595 auto P = RequiresScalarEpilogue ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
1596 auto *CheckMinIters = Builder.createICmp(
1597 Pred: P, A: Count, B: VFxUF, DL: DebugLoc::getUnknown(), Name: "min.epilog.iters.check");
1598 VPInstruction *Branch =
1599 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: CheckMinIters);
1600
1601 // We assume the remaining `Count` is equally distributed in
1602 // [0, MainLoopStep)
1603 // So the probability for `Count < EpilogueLoopStep` should be
1604 // min(MainLoopStep, EpilogueLoopStep) / MainLoopStep
1605 // TODO: Improve the estimate by taking the estimated trip count into
1606 // consideration.
1607 unsigned EstimatedSkipCount = std::min(a: MainLoopStep, b: EpilogueLoopStep);
1608 const uint32_t Weights[] = {EstimatedSkipCount,
1609 MainLoopStep - EstimatedSkipCount};
1610 MDBuilder MDB(Plan.getContext());
1611 MDNode *BranchWeights =
1612 MDB.createBranchWeights(Weights, /*IsExpected=*/false);
1613 Branch->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1614}
1615
1616/// Find and return the final select instruction of the FindIV result pattern
1617/// for the given \p BackedgeVal:
1618/// select(icmp ne ComputeReductionResult(ReducedIV), Sentinel),
1619/// ComputeReductionResult(ReducedIV), Start.
1620static VPInstruction *findFindIVSelect(VPValue *BackedgeVal) {
1621 return cast<VPInstruction>(
1622 Val: vputils::findRecipe(Start: BackedgeVal, Pred: [BackedgeVal](VPRecipeBase *R) {
1623 auto *VPI = dyn_cast<VPInstruction>(Val: R);
1624 return VPI &&
1625 matchFindIVResult(VPI, ReducedIV: m_Specific(VPV: BackedgeVal), Start: m_VPValue());
1626 }));
1627}
1628
1629bool VPlanTransforms::handleMaxMinNumReductions(VPlan &Plan) {
1630 auto GetMinOrMaxCompareValue =
1631 [](VPReductionPHIRecipe *RedPhiR) -> VPValue * {
1632 auto *MinOrMaxR =
1633 dyn_cast_or_null<VPRecipeWithIRFlags>(Val: RedPhiR->getBackedgeValue());
1634 if (!MinOrMaxR)
1635 return nullptr;
1636
1637 // Check that MinOrMaxR is a VPWidenIntrinsicRecipe or VPReplicateRecipe
1638 // with an intrinsic that matches the reduction kind.
1639 Intrinsic::ID ExpectedIntrinsicID =
1640 getMinMaxReductionIntrinsicOp(RK: RedPhiR->getRecurrenceKind());
1641 if (!match(V: MinOrMaxR, P: m_Intrinsic(IntrID: ExpectedIntrinsicID)))
1642 return nullptr;
1643
1644 if (MinOrMaxR->getOperand(N: 0) == RedPhiR)
1645 return MinOrMaxR->getOperand(N: 1);
1646
1647 assert(MinOrMaxR->getOperand(1) == RedPhiR &&
1648 "Reduction phi operand expected");
1649 return MinOrMaxR->getOperand(N: 0);
1650 };
1651
1652 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
1653 SmallVector<std::pair<VPReductionPHIRecipe *, VPValue *>>
1654 MinOrMaxNumReductionsToHandle;
1655 bool HasUnsupportedPhi = false;
1656 for (auto &R : LoopRegion->getEntryBasicBlock()->phis()) {
1657 if (isa<VPWidenIntOrFpInductionRecipe>(Val: &R))
1658 continue;
1659 auto *Cur = dyn_cast<VPReductionPHIRecipe>(Val: &R);
1660 if (!Cur) {
1661 // TODO: Also support fixed-order recurrence phis.
1662 HasUnsupportedPhi = true;
1663 continue;
1664 }
1665 if (!RecurrenceDescriptor::isFPMinMaxNumRecurrenceKind(
1666 Kind: Cur->getRecurrenceKind())) {
1667 HasUnsupportedPhi = true;
1668 continue;
1669 }
1670
1671 VPValue *MinOrMaxOp = GetMinOrMaxCompareValue(Cur);
1672 if (!MinOrMaxOp)
1673 return false;
1674
1675 MinOrMaxNumReductionsToHandle.emplace_back(Args&: Cur, Args&: MinOrMaxOp);
1676 }
1677
1678 if (MinOrMaxNumReductionsToHandle.empty())
1679 return true;
1680
1681 // We won't be able to resume execution in the scalar tail, if there are
1682 // unsupported header phis or there is no scalar tail at all, due to
1683 // tail-folding.
1684 if (HasUnsupportedPhi || !Plan.hasScalarTail())
1685 return false;
1686
1687 /// Check if the vector loop of \p Plan can early exit and restart
1688 /// execution of last vector iteration in the scalar loop. This requires all
1689 /// recipes up to early exit point be side-effect free as they are
1690 /// re-executed. Currently we check that the loop is free of any recipe that
1691 /// may write to memory. Expected to operate on an early VPlan w/o nested
1692 /// regions.
1693 for (VPBlockBase *VPB : vp_depth_first_shallow(
1694 G: Plan.getVectorLoopRegion()->getEntryBasicBlock())) {
1695 auto *VPBB = cast<VPBasicBlock>(Val: VPB);
1696 for (auto &R : *VPBB) {
1697 if (R.mayWriteToMemory() && !match(V: &R, P: m_BranchOnCount()))
1698 return false;
1699 }
1700 }
1701
1702 VPBasicBlock *LatchVPBB = LoopRegion->getExitingBasicBlock();
1703 VPBuilder LatchBuilder(LatchVPBB->getTerminator());
1704 VPValue *AllNaNLanes = nullptr;
1705 SmallPtrSet<VPValue *, 2> RdxResults;
1706 for (const auto &[_, MinOrMaxOp] : MinOrMaxNumReductionsToHandle) {
1707 VPValue *RedNaNLanes =
1708 LatchBuilder.createFCmp(Pred: CmpInst::FCMP_UNO, A: MinOrMaxOp, B: MinOrMaxOp);
1709 AllNaNLanes = AllNaNLanes ? LatchBuilder.createOr(LHS: AllNaNLanes, RHS: RedNaNLanes)
1710 : RedNaNLanes;
1711 }
1712
1713 VPValue *AnyNaNLane =
1714 LatchBuilder.createNaryOp(Opcode: VPInstruction::AnyOf, Operands: {AllNaNLanes});
1715 VPBasicBlock *MiddleVPBB = Plan.getMiddleBlock();
1716 VPBuilder MiddleBuilder(MiddleVPBB, MiddleVPBB->begin());
1717 for (const auto &[RedPhiR, _] : MinOrMaxNumReductionsToHandle) {
1718 assert(RecurrenceDescriptor::isFPMinMaxNumRecurrenceKind(
1719 RedPhiR->getRecurrenceKind()) &&
1720 "unsupported reduction");
1721
1722 // If we exit early due to NaNs, compute the final reduction result based on
1723 // the reduction phi at the beginning of the last vector iteration.
1724 auto *RdxResult = vputils::findComputeReductionResult(PhiR: RedPhiR);
1725 assert(RdxResult && "must find a ComputeReductionResult");
1726
1727 auto *NewSel = MiddleBuilder.createSelect(Cond: AnyNaNLane, TrueVal: RedPhiR,
1728 FalseVal: RdxResult->getOperand(N: 0));
1729 RdxResult->setOperand(I: 0, New: NewSel);
1730 assert(!RdxResults.contains(RdxResult) && "RdxResult already used");
1731 RdxResults.insert(Ptr: RdxResult);
1732 }
1733
1734 auto *LatchExitingBranch = LatchVPBB->getTerminator();
1735 assert(match(LatchExitingBranch, m_BranchOnCount(m_VPValue(), m_VPValue())) &&
1736 "Unexpected terminator");
1737 auto *IsLatchExitTaken = LatchBuilder.createICmp(
1738 Pred: CmpInst::ICMP_EQ, A: LatchExitingBranch->getOperand(N: 0),
1739 B: LatchExitingBranch->getOperand(N: 1));
1740 auto *AnyExitTaken = LatchBuilder.createOr(LHS: AnyNaNLane, RHS: IsLatchExitTaken);
1741 LatchBuilder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: AnyExitTaken);
1742 LatchExitingBranch->eraseFromParent();
1743
1744 // Update resume phis for inductions in the scalar preheader. If AnyNaNLane is
1745 // true, the resume from the start of the last vector iteration via the
1746 // canonical IV, otherwise from the original value.
1747 auto IsTC = [&Plan](VPValue *V) {
1748 return V == &Plan.getVectorTripCount() || V == Plan.getTripCount();
1749 };
1750 for (auto &R : Plan.getScalarPreheader()->phis()) {
1751 auto *ResumeR = cast<VPPhi>(Val: &R);
1752 VPValue *VecV = ResumeR->getOperand(N: 0);
1753 if (RdxResults.contains(Ptr: VecV))
1754 continue;
1755 if (auto *DerivedIV = dyn_cast<VPDerivedIVRecipe>(Val: VecV)) {
1756 VPValue *DIVTC = DerivedIV->getOperand(N: 1);
1757 if (DerivedIV->hasOneUse() && IsTC(DIVTC)) {
1758 auto *NewSel = MiddleBuilder.createSelect(
1759 Cond: AnyNaNLane, TrueVal: LoopRegion->getCanonicalIV(), FalseVal: DIVTC);
1760 DerivedIV->moveAfter(MovePos: &*MiddleBuilder.getInsertPoint());
1761 DerivedIV->setOperand(I: 1, New: NewSel);
1762 continue;
1763 }
1764 }
1765 // Bail out and abandon the current, partially modified, VPlan if we
1766 // encounter resume phi that cannot be updated yet.
1767 if (!IsTC(VecV)) {
1768 LLVM_DEBUG(dbgs() << "Found resume phi we cannot update for VPlan with "
1769 "FMaxNum/FMinNum reduction.\n");
1770 return false;
1771 }
1772 auto *NewSel = MiddleBuilder.createSelect(
1773 Cond: AnyNaNLane, TrueVal: LoopRegion->getCanonicalIV(), FalseVal: VecV);
1774 ResumeR->setOperand(I: 0, New: NewSel);
1775 }
1776
1777 auto *MiddleTerm = MiddleVPBB->getTerminator();
1778 MiddleBuilder.setInsertPoint(MiddleTerm);
1779 VPValue *MiddleCond = MiddleTerm->getOperand(N: 0);
1780 VPValue *NewCond =
1781 MiddleBuilder.createAnd(LHS: MiddleCond, RHS: MiddleBuilder.createNot(Operand: AnyNaNLane));
1782 MiddleTerm->setOperand(I: 0, New: NewCond);
1783 return true;
1784}
1785
1786bool VPlanTransforms::handleFindLastReductions(VPlan &Plan) {
1787 if (Plan.hasScalarVFOnly())
1788 return false;
1789
1790 // We want to create the following nodes:
1791 // vector.body:
1792 // ...new WidenPHI recipe introduced to keep the mask value for the latest
1793 // iteration where any lane was active.
1794 // mask.phi = phi [ ir<false>, vector.ph ], [ vp<new.mask>, vector.body ]
1795 // ...data.phi (a VPReductionPHIRecipe for a FindLast reduction) already
1796 // exists, but needs updating to use 'new.data' for the backedge value.
1797 // data.phi = phi ir<default.val>, vp<new.data>
1798 //
1799 // ...'data' and 'compare' created by existing nodes...
1800 //
1801 // ...new recipes introduced to determine whether to update the reduction
1802 // values or keep the current one.
1803 // any.active = i1 any-of ir<compare>
1804 // new.mask = select vp<any.active>, ir<compare>, vp<mask.phi>
1805 // new.data = select vp<any.active>, ir<data>, ir<data.phi>
1806 //
1807 // middle.block:
1808 // ...extract-last-active replaces compute-reduction-result.
1809 // result = extract-last-active vp<new.data>, vp<new.mask>, ir<default.val>
1810
1811 SmallVector<VPReductionPHIRecipe *, 4> Phis;
1812 for (VPRecipeBase &Phi :
1813 Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
1814 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(Val: &Phi);
1815 if (PhiR && RecurrenceDescriptor::isFindLastRecurrenceKind(
1816 Kind: PhiR->getRecurrenceKind()))
1817 Phis.push_back(Elt: PhiR);
1818 }
1819
1820 if (Phis.empty())
1821 return true;
1822
1823 VPValue *HeaderMask = Plan.getVectorLoopRegion()->getHeaderMask();
1824 for (VPReductionPHIRecipe *PhiR : Phis) {
1825 // Find the condition for the select/blend.
1826 VPValue *BackedgeSelect = PhiR->getBackedgeValue();
1827 VPValue *CondSelect = BackedgeSelect;
1828
1829 // If there's a header mask, the backedge select will not be the find-last
1830 // select.
1831 if (HeaderMask &&
1832 !match(V: BackedgeSelect,
1833 P: m_SelectLike(Op0: m_Specific(VPV: HeaderMask), Op1: m_VPValue(V&: CondSelect),
1834 Op2: m_Specific(VPV: PhiR))))
1835 return false;
1836
1837 VPValue *Cond = nullptr, *Op1 = nullptr, *Op2 = nullptr;
1838
1839 // If we're matching a blend rather than a select, there should be one
1840 // incoming value which is the data, then all other incoming values should
1841 // be the phi.
1842 auto MatchBlend = [&](VPRecipeBase *R) {
1843 auto *Blend = dyn_cast<VPBlendRecipe>(Val: R);
1844 if (!Blend)
1845 return false;
1846 assert(!Blend->isNormalized() && "must run before blend normalizaion");
1847 unsigned NumIncomingDataValues = 0;
1848 for (unsigned I = 0; I < Blend->getNumIncomingValues(); ++I) {
1849 VPValue *Incoming = Blend->getIncomingValue(Idx: I);
1850 if (Incoming != PhiR) {
1851 ++NumIncomingDataValues;
1852 Cond = Blend->getMask(Idx: I);
1853 Op1 = Incoming;
1854 Op2 = PhiR;
1855 }
1856 }
1857 return NumIncomingDataValues == 1;
1858 };
1859
1860 VPSingleDefRecipe *SelectR =
1861 cast<VPSingleDefRecipe>(Val: CondSelect->getDefiningRecipe());
1862 if (!match(R: SelectR,
1863 P: m_Select(Op0: m_VPValue(V&: Cond), Op1: m_VPValue(V&: Op1), Op2: m_VPValue(V&: Op2))) &&
1864 !MatchBlend(SelectR))
1865 return false;
1866
1867 assert(Cond != HeaderMask && "Cond must not be HeaderMask");
1868
1869 // Find final reduction computation and replace it with an
1870 // extract.last.active intrinsic.
1871 auto *RdxResult =
1872 findUserOf<VPInstruction::ComputeReductionResult>(V: BackedgeSelect);
1873 assert(RdxResult && "Could not find reduction result");
1874
1875 // Add mask phi.
1876 VPBuilder Builder = VPBuilder::getToInsertAfter(R: PhiR);
1877 auto *MaskPHI = Builder.createWidenPhi(IncomingValues: Plan.getFalse());
1878
1879 // Add select for mask.
1880 Builder.setInsertPoint(SelectR);
1881
1882 if (Op1 == PhiR) {
1883 // Normalize to selecting the data operand when the condition is true by
1884 // swapping operands and negating the condition.
1885 std::swap(a&: Op1, b&: Op2);
1886 Cond = Builder.createNot(Operand: Cond);
1887 }
1888 assert(Op2 == PhiR && "data value must be selected if Cond is true");
1889
1890 if (HeaderMask)
1891 Cond = Builder.createLogicalAnd(LHS: HeaderMask, RHS: Cond);
1892
1893 VPValue *AnyOf = Builder.createNaryOp(Opcode: VPInstruction::AnyOf, Operands: {Cond});
1894 VPValue *MaskSelect = Builder.createSelect(Cond: AnyOf, TrueVal: Cond, FalseVal: MaskPHI);
1895 MaskPHI->addIncoming(IncomingV: MaskSelect);
1896
1897 // Replace select for data.
1898 VPValue *DataSelect =
1899 Builder.createSelect(Cond: AnyOf, TrueVal: Op1, FalseVal: Op2, DL: SelectR->getDebugLoc());
1900 SelectR->replaceAllUsesWith(New: DataSelect);
1901 PhiR->setBackedgeValue(DataSelect);
1902 SelectR->eraseFromParent();
1903
1904 Builder.setInsertPoint(RdxResult);
1905 auto *ExtractLastActive =
1906 Builder.createNaryOp(Opcode: VPInstruction::ExtractLastActive,
1907 Operands: {PhiR->getStartValue(), DataSelect, MaskSelect},
1908 DL: RdxResult->getDebugLoc());
1909 RdxResult->replaceAllUsesWith(New: ExtractLastActive);
1910 RdxResult->eraseFromParent();
1911 }
1912
1913 return true;
1914}
1915
1916/// Given a first argmin/argmax pattern with strict predicate consisting of
1917/// 1) a MinOrMax reduction \p MinOrMaxPhiR producing \p MinOrMaxResult,
1918/// 2) a wide induction \p WideIV,
1919/// 3) a FindLastIV reduction \p FindLastIVPhiR using \p WideIV,
1920/// return the smallest index of the FindLastIV reduction result using UMin,
1921/// unless \p MinOrMaxResult equals the start value of its MinOrMax reduction.
1922/// In that case, return the start value of the FindLastIV reduction instead.
1923/// If \p WideIV is not canonical, a new canonical wide IV is added, and the
1924/// final result is scaled back to the non-canonical \p WideIV.
1925/// The final value of the FindLastIV reduction is originally computed using
1926/// \p FindIVSelect, \p FindIVCmp, and \p FindIVRdxResult, which are replaced
1927/// and removed.
1928/// Returns true if the pattern was handled successfully, false otherwise.
1929static bool handleFirstArgMinOrMax(
1930 VPlan &Plan, VPReductionPHIRecipe *MinOrMaxPhiR,
1931 VPReductionPHIRecipe *FindLastIVPhiR, VPWidenIntOrFpInductionRecipe *WideIV,
1932 VPInstruction *MinOrMaxResult, VPInstruction *FindIVSelect,
1933 VPRecipeBase *FindIVCmp, VPInstruction *FindIVRdxResult) {
1934 assert(!FindLastIVPhiR->isInLoop() && !FindLastIVPhiR->isOrdered() &&
1935 "inloop and ordered reductions not supported");
1936 assert(FindLastIVPhiR->getVFScaleFactor() == 1 &&
1937 "FindIV reduction must not be scaled");
1938
1939 Type *Ty = Plan.getVectorLoopRegion()->getCanonicalIVType();
1940 // TODO: Support non (i.e., narrower than) canonical IV types.
1941 // TODO: Emit remarks for failed transformations.
1942 if (Ty != WideIV->getScalarType())
1943 return false;
1944
1945 auto *FindIVSelectR = cast<VPSingleDefRecipe>(
1946 Val: FindLastIVPhiR->getBackedgeValue()->getDefiningRecipe());
1947 assert(
1948 match(FindIVSelectR, m_Select(m_VPValue(), m_VPValue(), m_VPValue())) &&
1949 "backedge value must be a select");
1950 if (FindIVSelectR->getOperand(N: 1) != WideIV &&
1951 FindIVSelectR->getOperand(N: 2) != WideIV)
1952 return false;
1953
1954 // If the original wide IV is not canonical, create a new one. The canonical
1955 // wide IV is guaranteed to not wrap for all lanes that are active in the
1956 // vector loop.
1957 if (!WideIV->isCanonical()) {
1958 VPIRValue *Zero = Plan.getConstantInt(Ty, Val: 0);
1959 VPIRValue *One = Plan.getConstantInt(Ty, Val: 1);
1960 auto *WidenCanIV = new VPWidenIntOrFpInductionRecipe(
1961 nullptr, Zero, One, WideIV->getVFValue(),
1962 WideIV->getInductionDescriptor(),
1963 VPIRFlags::WrapFlagsTy(/*HasNUW=*/true, /*HasNSW=*/false),
1964 WideIV->getDebugLoc());
1965 WidenCanIV->insertBefore(InsertPos: WideIV);
1966
1967 // Update the select to use the wide canonical IV.
1968 FindIVSelectR->setOperand(I: FindIVSelectR->getOperand(N: 1) == WideIV ? 1 : 2,
1969 New: WidenCanIV);
1970 }
1971 FindLastIVPhiR->setOperand(I: 0, New: Plan.getPoison(Ty));
1972
1973 // The reduction using MinOrMaxPhiR needs adjusting to compute the correct
1974 // result:
1975 // 1. Find the first canonical indices corresponding to partial min/max
1976 // values, using loop reductions.
1977 // 2. Find which of the partial min/max values are equal to the overall
1978 // min/max value.
1979 // 3. Select among the canonical indices those corresponding to the overall
1980 // min/max value.
1981 // 4. Find the first canonical index of overall min/max and scale it back to
1982 // the original IV using VPDerivedIVRecipe.
1983 // 5. If the overall min/max equals the starting min/max, the condition in
1984 // the loop was always false, due to being strict; return the start value
1985 // of FindLastIVPhiR in that case.
1986 //
1987 // For example, we transforms two independent reduction result computations
1988 // for
1989 //
1990 // <x1> vector loop: {
1991 // vector.body:
1992 // ...
1993 // ir<%iv> = WIDEN-INDUCTION nuw nsw ir<10>, ir<1>, vp<%0>
1994 // WIDEN-REDUCTION-PHI ir<%min.idx> = phi ir<sentinel.min.start>,
1995 // ir<%min.idx.next>
1996 // WIDEN-REDUCTION-PHI ir<%min.val> = phi ir<100>, ir<%min.val.next>
1997 // ....
1998 // WIDEN-INTRINSIC ir<%min.val.next> = call llvm.umin(ir<%min.val>, ir<%l>)
1999 // WIDEN ir<%min.idx.next> = select ir<%cmp>, ir<%iv>, ir<%min.idx>
2000 // ...
2001 // }
2002 // Successor(s): middle.block
2003 //
2004 // middle.block:
2005 // vp<%iv.rdx> = compute-reduction-result (smax) vp<%min.idx.next>
2006 // vp<%min.result> = compute-reduction-result (umin) ir<%min.val.next>
2007 // vp<%cmp> = icmp ne vp<%iv.rdx>, ir<sentinel.min.start>
2008 // vp<%find.iv.result> = select vp<%cmp>, vp<%iv.rdx>, ir<10>
2009 //
2010 //
2011 // Into:
2012 //
2013 // vp<%reduced.min> = compute-reduction-result (umin) ir<%min.val.next>
2014 // vp<%reduced.mins.mask> = icmp eq ir<%min.val.next>, vp<%reduced.min>
2015 // vp<%idxs2reduce> = select vp<%reduced.mins.mask>, ir<%min.idx.next>,
2016 // ir<MaxUInt>
2017 // vp<%reduced.idx> = compute-reduction-result (umin) vp<%idxs2reduce>
2018 // vp<%scaled.idx> = DERIVED-IV ir<20> + vp<%reduced.idx> * ir<1>
2019 // vp<%always.false> = icmp eq vp<%reduced.min>, ir<100>
2020 // vp<%final.idx> = select vp<%always.false>, ir<10>,
2021 // vp<%scaled.idx>
2022
2023 VPBuilder Builder(FindIVRdxResult);
2024 VPValue *MinOrMaxExiting = MinOrMaxResult->getOperand(N: 0);
2025 auto *FinalMinOrMaxCmp =
2026 Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: MinOrMaxExiting, B: MinOrMaxResult);
2027 VPValue *LastIVExiting = FindIVRdxResult->getOperand(N: 0);
2028 VPValue *MaxIV =
2029 Plan.getConstantInt(Val: APInt::getMaxValue(numBits: Ty->getIntegerBitWidth()));
2030 auto *FinalIVSelect =
2031 Builder.createSelect(Cond: FinalMinOrMaxCmp, TrueVal: LastIVExiting, FalseVal: MaxIV);
2032 VPIRFlags RdxFlags(RecurKind::UMin, false, false, FastMathFlags());
2033 VPSingleDefRecipe *FinalCanIV = Builder.createNaryOp(
2034 Opcode: VPInstruction::ComputeReductionResult, Operands: {FinalIVSelect}, Flags: RdxFlags,
2035 DL: FindIVRdxResult->getDebugLoc());
2036
2037 // If we used a new wide canonical IV convert the reduction result back to the
2038 // original IV scale before the final select.
2039 if (!WideIV->isCanonical()) {
2040 auto *DerivedIVRecipe = new VPDerivedIVRecipe(
2041 InductionDescriptor::IK_IntInduction,
2042 nullptr, // No FPBinOp for integer induction
2043 WideIV->getStartValue(), FinalCanIV, WideIV->getStepValue());
2044 DerivedIVRecipe->insertBefore(InsertPos: &*Builder.getInsertPoint());
2045 FinalCanIV = DerivedIVRecipe;
2046 }
2047
2048 // If the final min/max value matches its start value, the condition in the
2049 // loop was always false, i.e. no induction value has been selected. If that's
2050 // the case, set the result of the IV reduction to its start value.
2051 VPValue *AlwaysFalse = Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: MinOrMaxResult,
2052 B: MinOrMaxPhiR->getStartValue());
2053 VPValue *FinalIV = Builder.createSelect(
2054 Cond: AlwaysFalse, TrueVal: FindIVSelect->getOperand(N: 2), FalseVal: FinalCanIV);
2055 FindIVSelect->replaceAllUsesWith(New: FinalIV);
2056
2057 // Erase the old FindIV result pattern which is now dead.
2058 FindIVSelect->eraseFromParent();
2059 FindIVCmp->eraseFromParent();
2060 FindIVRdxResult->eraseFromParent();
2061 return true;
2062}
2063
2064bool VPlanTransforms::handleMultiUseReductions(VPlan &Plan,
2065 OptimizationRemarkEmitter *ORE,
2066 Loop *TheLoop) {
2067 for (auto &PhiR : make_early_inc_range(
2068 Range: Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis())) {
2069 auto *MinOrMaxPhiR = dyn_cast<VPReductionPHIRecipe>(Val: &PhiR);
2070 // TODO: check for multi-uses in VPlan directly.
2071 if (!MinOrMaxPhiR || !MinOrMaxPhiR->hasUsesOutsideReductionChain())
2072 continue;
2073
2074 // MinOrMaxPhiR has users outside the reduction cycle in the loop. Check if
2075 // the only other user is a FindLastIV reduction. MinOrMaxPhiR must have
2076 // exactly 2 users:
2077 // 1) the min/max operation of the reduction cycle, and
2078 // 2) the compare of a FindLastIV reduction cycle. This compare must match
2079 // the min/max operation - comparing MinOrMaxPhiR with the operand of the
2080 // min/max operation, and be used only by the select of the FindLastIV
2081 // reduction cycle.
2082 RecurKind RdxKind = MinOrMaxPhiR->getRecurrenceKind();
2083 assert(
2084 RecurrenceDescriptor::isIntMinMaxRecurrenceKind(RdxKind) &&
2085 "only min/max recurrences support users outside the reduction chain");
2086
2087 auto *MinOrMaxOp =
2088 dyn_cast<VPRecipeWithIRFlags>(Val: MinOrMaxPhiR->getBackedgeValue());
2089 if (!MinOrMaxOp)
2090 return false;
2091
2092 // Check that MinOrMaxOp is a VPWidenIntrinsicRecipe or VPReplicateRecipe
2093 // with an intrinsic that matches the reduction kind.
2094 Intrinsic::ID ExpectedIntrinsicID = getMinMaxReductionIntrinsicOp(RK: RdxKind);
2095 if (!match(V: MinOrMaxOp, P: m_Intrinsic(IntrID: ExpectedIntrinsicID)))
2096 return false;
2097
2098 // MinOrMaxOp must have 2 users: 1) MinOrMaxPhiR and 2)
2099 // ComputeReductionResult.
2100 assert(MinOrMaxOp->getNumUsers() == 2 &&
2101 "MinOrMaxOp must have exactly 2 users");
2102 VPValue *MinOrMaxOpValue = MinOrMaxOp->getOperand(N: 0);
2103 if (MinOrMaxOpValue == MinOrMaxPhiR)
2104 MinOrMaxOpValue = MinOrMaxOp->getOperand(N: 1);
2105
2106 VPValue *CmpOpA;
2107 VPValue *CmpOpB;
2108 CmpPredicate Pred;
2109 auto *Cmp = dyn_cast_or_null<VPRecipeWithIRFlags>(Val: findUserOf(
2110 V: MinOrMaxPhiR, P: m_Cmp(Pred, Op0: m_VPValue(V&: CmpOpA), Op1: m_VPValue(V&: CmpOpB))));
2111 if (!Cmp || Cmp->getNumUsers() != 1 ||
2112 (CmpOpA != MinOrMaxOpValue && CmpOpB != MinOrMaxOpValue))
2113 return false;
2114
2115 if (MinOrMaxOpValue != CmpOpB)
2116 Pred = CmpInst::getSwappedPredicate(pred: Pred);
2117
2118 // MinOrMaxPhiR must have exactly 2 users:
2119 // * MinOrMaxOp,
2120 // * Cmp (that's part of a FindLastIV chain).
2121 if (MinOrMaxPhiR->getNumUsers() != 2)
2122 return false;
2123
2124 VPInstruction *MinOrMaxResult =
2125 findUserOf<VPInstruction::ComputeReductionResult>(V: MinOrMaxOp);
2126 assert(is_contained(MinOrMaxPhiR->users(), MinOrMaxOp) &&
2127 "one user must be MinOrMaxOp");
2128 assert(MinOrMaxResult && "MinOrMaxResult must be a user of MinOrMaxOp");
2129
2130 // Cmp must be used by the select of a FindLastIV chain.
2131 VPValue *Sel = dyn_cast<VPSingleDefRecipe>(Val: Cmp->getSingleUser());
2132 VPValue *IVOp, *FindIV;
2133 if (!Sel || Sel->getNumUsers() != 2 ||
2134 !match(V: Sel,
2135 P: m_Select(Op0: m_Specific(VPV: Cmp), Op1: m_VPValue(V&: IVOp), Op2: m_VPValue(V&: FindIV))))
2136 return false;
2137
2138 if (!isa<VPReductionPHIRecipe>(Val: FindIV)) {
2139 std::swap(a&: FindIV, b&: IVOp);
2140 Pred = CmpInst::getInversePredicate(pred: Pred);
2141 }
2142
2143 auto *FindIVPhiR = dyn_cast<VPReductionPHIRecipe>(Val: FindIV);
2144 if (!FindIVPhiR || !RecurrenceDescriptor::isFindIVRecurrenceKind(
2145 Kind: FindIVPhiR->getRecurrenceKind()))
2146 return false;
2147
2148 assert(!FindIVPhiR->isInLoop() && !FindIVPhiR->isOrdered() &&
2149 "cannot handle inloop/ordered reductions yet");
2150
2151 // Check if FindIVPhiR is a FindLast pattern by checking the MinMaxKind
2152 // on its ComputeReductionResult. SMax/UMax indicates FindLast.
2153 VPInstruction *FindIVResult =
2154 findUserOf<VPInstruction::ComputeReductionResult>(
2155 V: FindIVPhiR->getBackedgeValue());
2156 assert(FindIVResult &&
2157 "must be able to retrieve the FindIVResult VPInstruction");
2158 RecurKind FindIVMinMaxKind = FindIVResult->getRecurKind();
2159 if (FindIVMinMaxKind != RecurKind::SMax &&
2160 FindIVMinMaxKind != RecurKind::UMax)
2161 return false;
2162
2163 // TODO: Support cases where IVOp is the IV increment.
2164 if (!match(V: IVOp, P: m_TruncOrSelf(Op0: m_VPValue(V&: IVOp))) ||
2165 !isa<VPWidenIntOrFpInductionRecipe>(Val: IVOp))
2166 return false;
2167
2168 // Check if the predicate is compatible with the reduction kind.
2169 bool IsValidKindPred = [RdxKind, Pred]() {
2170 switch (RdxKind) {
2171 case RecurKind::UMin:
2172 return Pred == CmpInst::ICMP_UGE || Pred == CmpInst::ICMP_UGT;
2173 case RecurKind::UMax:
2174 return Pred == CmpInst::ICMP_ULE || Pred == CmpInst::ICMP_ULT;
2175 case RecurKind::SMax:
2176 return Pred == CmpInst::ICMP_SLE || Pred == CmpInst::ICMP_SLT;
2177 case RecurKind::SMin:
2178 return Pred == CmpInst::ICMP_SGE || Pred == CmpInst::ICMP_SGT;
2179 default:
2180 llvm_unreachable("unhandled recurrence kind");
2181 }
2182 }();
2183 if (!IsValidKindPred) {
2184 ORE->emit(RemarkBuilder: [&]() {
2185 return OptimizationRemarkMissed(
2186 DEBUG_TYPE, "VectorizationMultiUseReductionPredicate",
2187 TheLoop->getStartLoc(), TheLoop->getHeader())
2188 << "Multi-use reduction with predicate "
2189 << CmpInst::getPredicateName(P: Pred)
2190 << " incompatible with reduction kind";
2191 });
2192 return false;
2193 }
2194
2195 auto *FindIVSelect = findFindIVSelect(BackedgeVal: FindIVPhiR->getBackedgeValue());
2196 auto *FindIVCmp = FindIVSelect->getOperand(N: 0)->getDefiningRecipe();
2197 auto *FindIVRdxResult = cast<VPInstruction>(Val: FindIVCmp->getOperand(N: 0));
2198 assert(FindIVSelect->getParent() == MinOrMaxResult->getParent() &&
2199 "both results must be computed in the same block");
2200 // Reducing to a scalar min or max value is placed right before reducing to
2201 // its scalar iteration, in order to generate instructions that use both
2202 // their operands.
2203 MinOrMaxResult->moveBefore(BB&: *FindIVRdxResult->getParent(),
2204 I: FindIVRdxResult->getIterator());
2205
2206 bool IsStrictPredicate = ICmpInst::isLT(P: Pred) || ICmpInst::isGT(P: Pred);
2207 if (IsStrictPredicate) {
2208 if (!handleFirstArgMinOrMax(Plan, MinOrMaxPhiR, FindLastIVPhiR: FindIVPhiR,
2209 WideIV: cast<VPWidenIntOrFpInductionRecipe>(Val: IVOp),
2210 MinOrMaxResult, FindIVSelect, FindIVCmp,
2211 FindIVRdxResult))
2212 return false;
2213 continue;
2214 }
2215
2216 // The reduction using MinOrMaxPhiR needs adjusting to compute the correct
2217 // result:
2218 // 1. We need to find the last IV for which the condition based on the
2219 // min/max recurrence is true,
2220 // 2. Compare the partial min/max reduction result to its final value and,
2221 // 3. Select the lanes of the partial FindLastIV reductions which
2222 // correspond to the lanes matching the min/max reduction result.
2223 //
2224 // For example, this transforms
2225 // vp<%min.result> = compute-reduction-result ir<%min.val.next>
2226 // vp<%iv.rdx> = compute-reduction-result (smax) vp<%min.idx.next>
2227 // vp<%cmp> = icmp ne vp<%iv.rdx>, SENTINEL
2228 // vp<%find.iv.result> = select vp<%cmp>, vp<%iv.rdx>, ir<0>
2229 //
2230 // into:
2231 //
2232 // vp<min.result> = compute-reduction-result ir<%min.val.next>
2233 // vp<%final.min.cmp> = icmp eq ir<%min.val.next>, vp<min.result>
2234 // vp<%final.iv> = select vp<%final.min.cmp>, vp<%min.idx.next>, SENTINEL
2235 // vp<%iv.rdx> = compute-reduction-result (smax) vp<%final.iv>
2236 // vp<%cmp> = icmp ne vp<%iv.rdx>, SENTINEL
2237 // vp<%find.iv.result> = select vp<%cmp>, vp<%iv.rdx>, ir<0>
2238 //
2239 VPBuilder B(FindIVRdxResult);
2240 VPValue *MinOrMaxExiting = MinOrMaxResult->getOperand(N: 0);
2241 auto *FinalMinOrMaxCmp =
2242 B.createICmp(Pred: CmpInst::ICMP_EQ, A: MinOrMaxExiting, B: MinOrMaxResult);
2243 VPValue *Sentinel = FindIVCmp->getOperand(N: 1);
2244 VPValue *LastIVExiting = FindIVRdxResult->getOperand(N: 0);
2245 auto *FinalIVSelect =
2246 B.createSelect(Cond: FinalMinOrMaxCmp, TrueVal: LastIVExiting, FalseVal: Sentinel);
2247 FindIVRdxResult->setOperand(I: 0, New: FinalIVSelect);
2248 }
2249 return true;
2250}
2251