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