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 assert(!isa<InsertValueInst>(Inst) &&
296 "legality must reject aggregate-producing insertvalue");
297 // Translate LLVM-IR operands into VPValue operands and set them in the
298 // new VPInstruction.
299 SmallVector<VPValue *, 4> VPOperands;
300 for (Value *Op : Inst->operands())
301 VPOperands.push_back(Elt: getOrCreateVPOperand(IRVal: Op));
302 if (auto *EVI = dyn_cast<ExtractValueInst>(Val: Inst))
303 for (unsigned Idx : EVI->indices())
304 VPOperands.push_back(Elt: Plan->getConstantInt(BitWidth: 32, Val: Idx));
305 VPIRAttributes Attrs;
306 if (auto *CI = dyn_cast<CallInst>(Val: Inst))
307 Attrs = VPIRAttributes(CI->getAttributes());
308 NewR = VPIRBuilder.createNaryOp(Opcode: Inst->getOpcode(), Operands: VPOperands, Inst,
309 Flags: VPIRFlags(*Inst), MD, DL: Inst->getDebugLoc(),
310 Name: "", ResultTy: Inst->getType(), Attrs);
311 }
312
313 IRDef2VPValue[Inst] = NewR;
314 }
315}
316
317// Main interface to build the plain CFG.
318std::unique_ptr<VPlan> PlainCFGBuilder::buildPlainCFG() {
319 VPIRBasicBlock *Entry = cast<VPIRBasicBlock>(Val: Plan->getEntry());
320 BB2VPBB[Entry->getIRBasicBlock()] = Entry;
321 for (VPIRBasicBlock *ExitVPBB : Plan->getExitBlocks())
322 BB2VPBB[ExitVPBB->getIRBasicBlock()] = ExitVPBB;
323
324 // 1. Scan the body of the loop in a topological order to visit each basic
325 // block after having visited its predecessor basic blocks. Create a VPBB for
326 // each BB and link it to its successor and predecessor VPBBs. Note that
327 // predecessors must be set in the same order as they are in the incomming IR.
328 // Otherwise, there might be problems with existing phi nodes and algorithm
329 // based on predecessors traversal.
330
331 // Loop PH needs to be explicitly visited since it's not taken into account by
332 // LoopBlocksDFS.
333 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
334 assert((ThePreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
335 "Unexpected loop preheader");
336 for (auto &I : *ThePreheaderBB) {
337 if (I.getType()->isVoidTy())
338 continue;
339 IRDef2VPValue[&I] = Plan->getOrAddLiveIn(V: &I);
340 }
341
342 LoopBlocksRPO RPO(TheLoop);
343 RPO.perform(LI);
344
345 for (BasicBlock *BB : RPO) {
346 // Create or retrieve the VPBasicBlock for this BB.
347 VPBasicBlock *VPBB = getOrCreateVPBB(BB);
348 // Set VPBB predecessors in the same order as they are in the incoming BB.
349 setVPBBPredsFromBB(VPBB, BB);
350
351 // Create VPInstructions for BB.
352 createVPInstructionsForVPBB(VPBB, BB);
353
354 // Set VPBB successors. We create empty VPBBs for successors if they don't
355 // exist already. Recipes will be created when the successor is visited
356 // during the RPO traversal.
357 if (auto *SI = dyn_cast<SwitchInst>(Val: BB->getTerminator())) {
358 SmallVector<VPBlockBase *> Succs = {
359 getOrCreateVPBB(BB: SI->getDefaultDest())};
360 for (auto Case : SI->cases())
361 Succs.push_back(Elt: getOrCreateVPBB(BB: Case.getCaseSuccessor()));
362 VPBB->setSuccessors(Succs);
363 continue;
364 }
365 if (auto *BI = dyn_cast<UncondBrInst>(Val: BB->getTerminator())) {
366 VPBB->setOneSuccessor(getOrCreateVPBB(BB: BI->getSuccessor()));
367 continue;
368 }
369 auto *BI = cast<CondBrInst>(Val: BB->getTerminator());
370 BasicBlock *IRSucc0 = BI->getSuccessor(i: 0);
371 BasicBlock *IRSucc1 = BI->getSuccessor(i: 1);
372 VPBasicBlock *Successor0 = getOrCreateVPBB(BB: IRSucc0);
373 VPBasicBlock *Successor1 = getOrCreateVPBB(BB: IRSucc1);
374 VPBB->setTwoSuccessors(IfTrue: Successor0, IfFalse: Successor1);
375 }
376
377 for (auto *EB : Plan->getExitBlocks())
378 setVPBBPredsFromBB(VPBB: EB, BB: EB->getIRBasicBlock());
379
380 // 2. The whole CFG has been built at this point so all the input Values must
381 // have a VPlan counterpart. Fix VPlan header phi by adding their
382 // corresponding VPlan operands.
383 fixHeaderPhis();
384
385 Plan->getEntry()->setOneSuccessor(getOrCreateVPBB(BB: TheLoop->getHeader()));
386 Plan->getEntry()->setPlan(&*Plan);
387
388 // Fix VPlan loop-closed-ssa exit phi's by adding incoming operands to the
389 // VPIRInstructions wrapping them.
390 // // Note that the operand order corresponds to IR predecessor order, and may
391 // need adjusting when VPlan predecessors are added, if an exit block has
392 // multiple predecessor.
393 for (auto *EB : Plan->getExitBlocks()) {
394 for (VPRecipeBase &R : EB->phis()) {
395 auto *PhiR = cast<VPIRPhi>(Val: &R);
396 PHINode &Phi = PhiR->getIRPhi();
397 assert(PhiR->getNumOperands() == 0 &&
398 "no phi operands should be added yet");
399 for (BasicBlock *Pred : predecessors(BB: EB->getIRBasicBlock()))
400 PhiR->addIncoming(
401 IncomingV: getOrCreateVPOperand(IRVal: Phi.getIncomingValueForBlock(BB: Pred)));
402 }
403 }
404
405 LLVM_DEBUG(Plan->setName("Plain CFG\n"); dbgs() << *Plan);
406 return std::move(Plan);
407}
408
409/// Checks if \p HeaderVPB is a loop header block in the plain CFG; that is, it
410/// has exactly 2 predecessors (preheader and latch), where the block
411/// dominates the latch and the preheader dominates the block. If it is a
412/// header block return true and canonicalize the predecessors of the header
413/// (making sure the preheader appears first and the latch second) and the
414/// successors of the latch (making sure the loop exit comes first). Otherwise
415/// return false.
416static bool canonicalHeaderAndLatch(VPBlockBase *HeaderVPB,
417 const VPDominatorTree &VPDT) {
418 ArrayRef<VPBlockBase *> Preds = HeaderVPB->getPredecessors();
419 if (Preds.size() != 2)
420 return false;
421
422 auto *PreheaderVPBB = Preds[0];
423 auto *LatchVPBB = Preds[1];
424 if (!VPDT.dominates(A: PreheaderVPBB, B: HeaderVPB) ||
425 !VPDT.dominates(A: HeaderVPB, B: LatchVPBB)) {
426 std::swap(a&: PreheaderVPBB, b&: LatchVPBB);
427
428 if (!VPDT.dominates(A: PreheaderVPBB, B: HeaderVPB) ||
429 !VPDT.dominates(A: HeaderVPB, B: LatchVPBB))
430 return false;
431
432 // Canonicalize predecessors of header so that preheader is first and
433 // latch second.
434 HeaderVPB->swapPredecessors();
435 for (VPRecipeBase &R : cast<VPBasicBlock>(Val: HeaderVPB)->phis())
436 R.swapOperands();
437 }
438
439 // The two successors of conditional branch match the condition, with the
440 // first successor corresponding to true and the second to false. We
441 // canonicalize the successors of the latch when introducing the region, such
442 // that the latch exits the region when its condition is true; invert the
443 // original condition if the original CFG branches to the header on true.
444 // Note that the exit edge is not yet connected for top-level loops.
445 if (LatchVPBB->getSingleSuccessor() ||
446 LatchVPBB->getSuccessors()[0] != HeaderVPB)
447 return true;
448
449 assert(LatchVPBB->getNumSuccessors() == 2 && "Must have 2 successors");
450 auto *Term = cast<VPBasicBlock>(Val: LatchVPBB)->getTerminator();
451 assert(cast<VPInstruction>(Term)->getOpcode() ==
452 VPInstruction::BranchOnCond &&
453 "terminator must be a BranchOnCond");
454 auto *Not = new VPInstruction(VPInstruction::Not, {Term->getOperand(N: 0)});
455 Not->insertBefore(InsertPos: Term);
456 Term->setOperand(I: 0, New: Not);
457 LatchVPBB->swapSuccessors();
458
459 return true;
460}
461
462/// Create a new VPRegionBlock for the loop starting at \p HeaderVPB. For the
463/// outermost loop adjust the regions exiting terminator to be based on the
464/// canonical IV.
465static void createLoopRegion(VPlan &Plan, VPBlockBase *HeaderVPB, DebugLoc DL) {
466 auto *PreheaderVPBB = HeaderVPB->getPredecessors()[0];
467 auto *LatchVPBB = cast<VPBasicBlock>(Val: HeaderVPB->getPredecessors()[1]);
468 auto *OutermostHeaderVPBB =
469 VPBlockUtils::getPlainCFGHeaderAndLatch(Plan).first;
470
471 VPBlockUtils::disconnectBlocks(From: PreheaderVPBB, To: HeaderVPB);
472 VPBlockUtils::disconnectBlocks(From: LatchVPBB, To: HeaderVPB);
473
474 // Create an empty region first and insert it between PreheaderVPBB and
475 // the exit blocks, taking care to preserve the original predecessor &
476 // successor order of blocks. Set region entry and exiting after both
477 // HeaderVPB and LatchVPBB have been disconnected from their
478 // predecessors/successors. Only the outermost loop has a canonical IV. Nested
479 // loops are assigned a canonical IV of null type and unknown debug location.
480 bool IsOutermost = HeaderVPB == OutermostHeaderVPBB;
481 Type *CanIVTy = nullptr;
482 if (IsOutermost)
483 CanIVTy = Plan.getVectorTripCount().getType();
484 else
485 DL = DebugLoc::getUnknown();
486 auto *R = Plan.createLoopRegion(CanIVTy, DL);
487
488 // Transfer latch's successors to the region.
489 VPBlockUtils::transferSuccessors(Old: LatchVPBB, New: R);
490
491 VPBlockUtils::connectBlocks(From: PreheaderVPBB, To: R);
492 R->setEntry(HeaderVPB);
493 R->setExiting(LatchVPBB);
494
495 // All VPBB's reachable shallowly from HeaderVPB belong to the current region.
496 for (VPBlockBase *VPBB : vp_depth_first_shallow(G: HeaderVPB))
497 VPBB->setParent(R);
498
499 if (!IsOutermost)
500 return;
501
502 auto *LatchTerm = LatchVPBB->getTerminator();
503 VPBuilder Builder(LatchTerm);
504 // Add a VPInstruction to increment the scalar canonical IV by VF * UF.
505 // Initially the induction increment is guaranteed to not wrap, but that may
506 // change later, e.g. when tail-folding, when the flags need to be dropped.
507 auto *CanonicalIVIncrement = Builder.createAdd(
508 LHS: R->getCanonicalIV(), RHS: &Plan.getVFxUF(), DL, Name: "index.next", WrapFlags: {true, false});
509
510 if (match(V: LatchTerm, P: m_BranchOnTwoConds())) {
511 auto *IsLatchExitTaken = Builder.createICmp(
512 Pred: CmpInst::ICMP_EQ, A: CanonicalIVIncrement, B: &Plan.getVectorTripCount());
513 LatchTerm->setOperand(I: 1, New: IsLatchExitTaken);
514 } else {
515 // We are replacing the branch to exit the region. Remove the original
516 // BranchOnCond.
517 assert(match(LatchTerm, m_BranchOnCond()) && "Unexpected terminator");
518 DebugLoc LatchDL = LatchTerm->getDebugLoc();
519 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCount,
520 Operands: {CanonicalIVIncrement, &Plan.getVectorTripCount()},
521 DL: LatchDL);
522 LatchTerm->eraseFromParent();
523 }
524}
525
526/// Creates extracts for values in \p Plan defined in a loop region and used
527/// outside a loop region.
528static void createExtractsForLiveOuts(VPlan &Plan, VPBasicBlock *MiddleVPBB) {
529 VPBuilder B(MiddleVPBB->getFirstNonPhi());
530 for (VPBasicBlock *EB : Plan.getExitBlocks()) {
531 if (!is_contained(Range: EB->predecessors(), Element: MiddleVPBB))
532 continue;
533
534 for (VPRecipeBase &R : EB->phis()) {
535 auto *ExitIRI = cast<VPIRPhi>(Val: &R);
536 VPValue *Exiting = ExitIRI->getIncomingValueForBlock(VPBB: MiddleVPBB);
537 if (isa<VPIRValue>(Val: Exiting))
538 continue;
539 Exiting = B.createNaryOp(Opcode: VPInstruction::ExtractLastPart, Operands: Exiting);
540 Exiting = B.createNaryOp(Opcode: VPInstruction::ExtractLastLane, Operands: Exiting);
541 ExitIRI->setIncomingValueForBlock(VPBB: MiddleVPBB, V: Exiting);
542 }
543 }
544}
545
546static void addInitialSkeleton(VPlan &Plan, Type *InductionTy,
547 PredicatedScalarEvolution &PSE, Loop *TheLoop) {
548 VPDominatorTree VPDT(Plan);
549
550 auto *HeaderVPBB = cast<VPBasicBlock>(Val: Plan.getEntry()->getSingleSuccessor());
551 if (TheLoop->isInnermost()) {
552 canonicalHeaderAndLatch(HeaderVPB: HeaderVPBB, VPDT);
553 } else {
554 // When vectorizing outer loops, canonicalize all loops up front.
555 SmallVector<VPBlockBase *> Blocks(vp_depth_first_shallow(G: Plan.getEntry()));
556 for (VPBlockBase *VPB : Blocks)
557 canonicalHeaderAndLatch(HeaderVPB: VPB, VPDT);
558 }
559 auto *LatchVPBB = cast<VPBasicBlock>(Val: HeaderVPBB->getPredecessors()[1]);
560
561 VPBasicBlock *VecPreheader = Plan.createVPBasicBlock(Name: "vector.ph");
562 VPBlockUtils::insertBlockAfter(NewBlock: VecPreheader, BlockPtr: Plan.getEntry());
563
564 VPBasicBlock *MiddleVPBB = Plan.createVPBasicBlock(Name: "middle.block");
565 // The canonical LatchVPBB has the header block as last successor. If it has
566 // another successor, this successor is an exit block - insert middle block on
567 // its edge. Otherwise, add middle block as another successor retaining header
568 // as last. In the latter case, the latch has no conditional terminator yet,
569 // so insert a placeholder BranchOnCond that always continues to the header.
570 // It will be canonicalized to a BranchOnCount later
571 if (LatchVPBB->getNumSuccessors() == 2) {
572 VPBlockBase *LatchExitVPB = LatchVPBB->getSuccessors()[0];
573 VPBlockUtils::insertOnEdge(From: LatchVPBB, To: LatchExitVPB, BlockPtr: MiddleVPBB);
574 } else {
575 VPBlockUtils::connectBlocks(From: LatchVPBB, To: MiddleVPBB);
576 LatchVPBB->swapSuccessors();
577 VPBuilder(LatchVPBB).createNaryOp(Opcode: VPInstruction::BranchOnCond,
578 Operands: {Plan.getFalse()});
579 }
580
581 // Create SCEV and VPValue for the trip count.
582 // We use the symbolic max backedge-taken-count, which works also when
583 // vectorizing loops with uncountable early exits.
584 const SCEV *BackedgeTakenCountSCEV = PSE.getSymbolicMaxBackedgeTakenCount();
585 assert(!isa<SCEVCouldNotCompute>(BackedgeTakenCountSCEV) &&
586 "Invalid backedge-taken count");
587 ScalarEvolution &SE = *PSE.getSE();
588 const SCEV *TripCount = SE.getTripCountFromExitCount(ExitCount: BackedgeTakenCountSCEV,
589 EvalTy: InductionTy, L: TheLoop);
590 Plan.setTripCount(vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: TripCount));
591
592 VPBasicBlock *ScalarPH = Plan.createVPBasicBlock(Name: "scalar.ph");
593 VPBlockUtils::connectBlocks(From: ScalarPH, To: Plan.getScalarHeader());
594
595 // The connection order corresponds to the operands of the conditional branch,
596 // with the middle block already connected to the exit block.
597 VPBlockUtils::connectBlocks(From: MiddleVPBB, To: ScalarPH);
598 // Also connect the entry block to the scalar preheader.
599 // TODO: Also introduce a branch recipe together with the minimum trip count
600 // check.
601 VPBlockUtils::connectBlocks(From: Plan.getEntry(), To: ScalarPH);
602 Plan.getEntry()->swapSuccessors();
603
604 createExtractsForLiveOuts(Plan, MiddleVPBB);
605
606 // Create resume phis in the scalar preheader for each phi in the scalar loop.
607 // Their incoming value from the vector loop will be the last lane of the
608 // corresponding vector loop header phi.
609 VPBuilder MiddleBuilder(MiddleVPBB->getFirstNonPhi());
610 VPBuilder ScalarPHBuilder(ScalarPH);
611 assert(equal(ScalarPH->getPredecessors(),
612 ArrayRef<VPBlockBase *>({MiddleVPBB, Plan.getEntry()})) &&
613 "unexpected predecessor order of scalar ph");
614 for (const auto &[PhiR, ScalarPhiR] :
615 zip_equal(t: HeaderVPBB->phis(), u: Plan.getScalarHeader()->phis())) {
616 auto *VectorPhiR = cast<VPPhi>(Val: &PhiR);
617 VPValue *BackedgeVal = VectorPhiR->getOperand(N: 1);
618 VPValue *ResumeFromVectorLoop =
619 MiddleBuilder.createNaryOp(Opcode: VPInstruction::ExtractLastPart, Operands: BackedgeVal);
620 ResumeFromVectorLoop = MiddleBuilder.createNaryOp(
621 Opcode: VPInstruction::ExtractLastLane, Operands: ResumeFromVectorLoop);
622 // Create scalar resume phi, with the first operand being the incoming value
623 // from the middle block and the second operand coming from the entry block.
624 auto *ResumePhiR = ScalarPHBuilder.createScalarPhi(
625 IncomingValues: {ResumeFromVectorLoop, VectorPhiR->getOperand(N: 0)},
626 DL: VectorPhiR->getDebugLoc());
627 cast<VPIRPhi>(Val: &ScalarPhiR)->addIncoming(IncomingV: ResumePhiR);
628 }
629}
630
631/// To make RUN_VPLAN_PASS print initial VPlan.
632static void printAfterInitialConstruction(VPlan &) {}
633
634std::unique_ptr<VPlan> VPlanTransforms::buildVPlan0(
635 Loop *TheLoop, LoopInfo &LI, Type *InductionTy,
636 PredicatedScalarEvolution &PSE, LoopVersioning *LVer,
637 function_ref<const BranchProbabilityInfo &()> GetBPI) {
638 PlainCFGBuilder Builder(TheLoop, &LI, LVer, InductionTy, GetBPI);
639 std::unique_ptr<VPlan> VPlan0 = Builder.buildPlainCFG();
640 addInitialSkeleton(Plan&: *VPlan0, InductionTy, PSE, TheLoop);
641 simplifyLiveInsWithSCEV(Plan&: *VPlan0, PSE);
642
643 RUN_VPLAN_PASS_NO_VERIFY(printAfterInitialConstruction, *VPlan0);
644 return VPlan0;
645}
646
647void VPlanTransforms::recordExecutionFrequencies(VPlan &Plan) {
648 VPBasicBlock *Header = VPBlockUtils::getPlainCFGHeaderAndLatch(Plan).first;
649 SmallVector<VPBasicBlock *> Blocks = vp_rpo_plain_cfg_loop_body(Header);
650 auto Frequencies = vputils::computeExecutionFrequencies(Blocks);
651 LLVMContext &Ctx = Plan.getContext();
652 for (VPBasicBlock *VPBB : Blocks) {
653 std::optional<VPExecutionFrequency> Freq = Frequencies.lookup(Val: VPBB);
654 for (VPInstruction &VPI : make_isa_range<VPInstruction>(Range&: *VPBB))
655 VPI.setExecutionFrequency(Freq, Ctx);
656 }
657}
658
659/// Creates a VPWidenIntOrFpInductionRecipe or VPWidenPointerInductionRecipe
660/// for \p Phi based on \p IndDesc.
661static VPHeaderPHIRecipe *
662createWidenInductionRecipe(PHINode *Phi, VPPhi *PhiR, VPIRValue *Start,
663 const InductionDescriptor &IndDesc, VPlan &Plan,
664 PredicatedScalarEvolution &PSE, Loop &OrigLoop,
665 DebugLoc DL) {
666 [[maybe_unused]] ScalarEvolution &SE = *PSE.getSE();
667 assert(SE.isLoopInvariant(IndDesc.getStep(), &OrigLoop) &&
668 "step must be loop invariant");
669 assert((Plan.getLiveIn(IndDesc.getStartValue()) == Start ||
670 (SE.isSCEVable(IndDesc.getStartValue()->getType()) &&
671 PSE.getSCEV(IndDesc.getStartValue()) ==
672 vputils::getSCEVExprForVPValue(Start, PSE))) &&
673 "Start VPValue must match IndDesc's start value");
674
675 VPValue *Step =
676 vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: IndDesc.getStep());
677
678 VPValue *BackedgeVal = PhiR->getOperand(N: 1);
679 // Replace live-out extracts of WideIV's backedge value by ExitingIVValue
680 // recipes. optimizeInductionLiveOutUsers will later compute the proper
681 // DerivedIV.
682 //
683 // For an IV that requires SCEV predicate, keep extracting the exit values
684 // from the loop directly, as the pre-computed exit value as-is would be
685 // incorrect outside the loop.
686 auto ReplaceExtractsWithExitingIVValueIfPossible = [&](VPWidenInductionRecipe
687 *WideIV) {
688 bool IsPredicated = !WideIV->getNoWrapPredicates().empty();
689 for (VPUser *U : to_vector(Range: BackedgeVal->users())) {
690 if (!match(U, P: m_ExtractLastPart(Op0: m_VPValue())))
691 continue;
692 auto *ExtractLastPart = cast<VPInstruction>(Val: U);
693 VPUser *ExtractLastPartUser = ExtractLastPart->getSingleUser();
694 assert(ExtractLastPartUser && "must have a single user");
695 if (!match(U: ExtractLastPartUser, P: m_ExtractLastLane(Op0: m_VPValue())))
696 continue;
697 auto *ExtractLastLane = cast<VPInstruction>(Val: ExtractLastPartUser);
698 assert(is_contained(ExtractLastLane->getParent()->successors(),
699 Plan.getScalarPreheader()) &&
700 "last lane must be extracted in the middle block");
701 // Keep the vector extract for exit-block live-out uses of a predicated
702 // IV.
703 if (IsPredicated &&
704 any_of(Range: ExtractLastLane->users(), P: [&](VPUser *LaneUser) {
705 auto *R = cast<VPRecipeBase>(Val: LaneUser);
706 return Plan.isExitBlock(VPBB: R->getParent());
707 }))
708 continue;
709 VPBuilder Builder(ExtractLastLane);
710 ExtractLastLane->replaceAllUsesWith(
711 New: Builder.createNaryOp(Opcode: VPInstruction::ExitingIVValue, Operands: {WideIV}));
712 ExtractLastLane->eraseFromParent();
713 ExtractLastPart->eraseFromParent();
714 }
715 };
716
717 if (IndDesc.getKind() == InductionDescriptor::IK_PtrInduction) {
718 auto *WideIV = new VPWidenPointerInductionRecipe(
719 Phi, Start, Step, &Plan.getVFxUF(), IndDesc, DL);
720 ReplaceExtractsWithExitingIVValueIfPossible(WideIV);
721 return WideIV;
722 }
723
724 assert((IndDesc.getKind() == InductionDescriptor::IK_IntInduction ||
725 IndDesc.getKind() == InductionDescriptor::IK_FpInduction) &&
726 "must have an integer or float induction at this point");
727
728 // Update wide induction increments to use the same step as the corresponding
729 // wide induction. This enables detecting induction increments directly in
730 // VPlan and removes redundant splats.
731 if (match(V: BackedgeVal, P: m_Add(Op0: m_Specific(VPV: PhiR), Op1: m_VPValue())))
732 BackedgeVal->getDefiningRecipe()->setOperand(I: 1, New: Step);
733
734 // It is always safe to copy over the NoWrap and FastMath flags. In
735 // particular, when folding tail by masking, the masked-off lanes are never
736 // used, so it is safe.
737 VPIRFlags Flags = vputils::getFlagsForInduction(ID: IndDesc, PhiR);
738
739 auto *WideIV = new VPWidenIntOrFpInductionRecipe(
740 Phi, Start, Step, &Plan.getVF(), IndDesc, Flags, DL);
741
742 ReplaceExtractsWithExitingIVValueIfPossible(WideIV);
743 return WideIV;
744}
745
746/// Try to sink users of \p FOR after \p Previous. \returns true if sinking
747/// succeeded or was not necessary, and false otherwise.
748static bool
749sinkRecurrenceUsersAfterPrevious(VPFirstOrderRecurrencePHIRecipe *FOR,
750 VPRecipeBase *Previous,
751 const VPDominatorTree &VPDT) {
752 // Collect recipes that need sinking.
753 SmallVector<VPRecipeBase *> WorkList;
754 SmallPtrSet<VPRecipeBase *, 8> Seen;
755 Seen.insert(Ptr: Previous);
756 auto TryToPushSinkCandidate = [&](VPRecipeBase *SinkCandidate) {
757 // The previous value must not depend on the users of the recurrence phi.
758 // In that case, FOR is not a fixed order recurrence.
759 if (SinkCandidate == Previous)
760 return false;
761
762 if (isa<VPHeaderPHIRecipe>(Val: SinkCandidate) ||
763 !Seen.insert(Ptr: SinkCandidate).second ||
764 VPDT.properlyDominates(A: Previous, B: SinkCandidate))
765 return true;
766
767 if (vputils::cannotHoistOrSinkRecipe(R: *SinkCandidate, /*Sinking=*/true))
768 return false;
769
770 WorkList.push_back(Elt: SinkCandidate);
771 return true;
772 };
773
774 // Recursively sink users of FOR after Previous.
775 WorkList.push_back(Elt: FOR);
776 for (unsigned I = 0; I != WorkList.size(); ++I) {
777 VPRecipeBase *Current = WorkList[I];
778 assert(Current->getNumDefinedValues() == 1 &&
779 "only recipes with a single defined value expected");
780
781 for (VPUser *User : Current->getVPSingleValue()->users()) {
782 if (!TryToPushSinkCandidate(cast<VPRecipeBase>(Val: User)))
783 return false;
784 }
785 }
786
787 // Keep recipes to sink ordered by dominance so earlier instructions are
788 // processed first.
789 sort(C&: WorkList, Comp: [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {
790 return VPDT.properlyDominates(A, B);
791 });
792
793 for (VPRecipeBase *SinkCandidate : WorkList) {
794 if (SinkCandidate == FOR)
795 continue;
796
797 SinkCandidate->moveAfter(MovePos: Previous);
798 Previous = SinkCandidate;
799 }
800 return true;
801}
802
803/// Try to hoist \p Previous and its operands before all users of \p FOR.
804/// \returns true if hoisting succeeded or was not necessary, and false
805/// otherwise.
806static bool hoistPreviousBeforeFORUsers(VPFirstOrderRecurrencePHIRecipe *FOR,
807 VPRecipeBase *Previous,
808 const VPDominatorTree &VPDT) {
809 if (vputils::cannotHoistOrSinkRecipe(R: *Previous))
810 return false;
811
812 // Collect recipes that need hoisting.
813 SmallVector<VPRecipeBase *> HoistCandidates;
814 SmallPtrSet<VPRecipeBase *, 8> Visited;
815 // Find the closest hoist point by looking at all users of FOR and selecting
816 // the recipe dominating all other users.
817 VPRecipeBase *HoistPoint = nullptr;
818 for (VPUser *U : FOR->users()) {
819 auto *R = cast<VPRecipeBase>(Val: U);
820 if (!HoistPoint || VPDT.properlyDominates(A: R, B: HoistPoint))
821 HoistPoint = R;
822 }
823 // Dominance is only a partial order, so the users of FOR may not have a
824 // single user dominating all others. Bail out in that case.
825 if (!HoistPoint || HoistPoint->isPhi() ||
826 any_of(Range: FOR->users(), P: [&VPDT, HoistPoint](VPUser *U) {
827 auto *R = cast<VPRecipeBase>(Val: U);
828 return HoistPoint != R && !VPDT.properlyDominates(A: HoistPoint, B: R);
829 }))
830 return false;
831
832 auto NeedsHoisting = [HoistPoint, &VPDT,
833 &Visited](VPValue *HoistCandidateV) -> VPRecipeBase * {
834 VPRecipeBase *HoistCandidate = HoistCandidateV->getDefiningRecipe();
835 if (!HoistCandidate)
836 return nullptr;
837 // Hoist candidate was already visited, no need to hoist.
838 if (!Visited.insert(Ptr: HoistCandidate).second)
839 return nullptr;
840 // If we reached a recipe that dominates HoistPoint, we don't need to
841 // hoist the recipe.
842 if (VPDT.properlyDominates(A: HoistCandidate, B: HoistPoint))
843 return nullptr;
844 return HoistCandidate;
845 };
846
847 if (!NeedsHoisting(Previous->getVPSingleValue()))
848 return true;
849
850 // Recursively try to hoist Previous and its operands before all users of
851 // FOR.
852 HoistCandidates.push_back(Elt: Previous);
853
854 for (unsigned I = 0; I != HoistCandidates.size(); ++I) {
855 VPRecipeBase *Current = HoistCandidates[I];
856 assert(Current->getNumDefinedValues() == 1 &&
857 "only recipes with a single defined value expected");
858 if (vputils::cannotHoistOrSinkRecipe(R: *Current))
859 return false;
860
861 for (VPValue *Op : Current->operands()) {
862 // If we reach FOR, it means the original Previous depends on some other
863 // recurrence that in turn depends on FOR. If that is the case, we would
864 // also need to hoist recipes involving the other FOR, which may break
865 // dependencies.
866 if (Op == FOR)
867 return false;
868
869 if (auto *R = NeedsHoisting(Op)) {
870 // Bail out if the recipe defines multiple values.
871 // TODO: Hoisting such recipes requires additional handling.
872 if (R->getNumDefinedValues() != 1)
873 return false;
874 HoistCandidates.push_back(Elt: R);
875 }
876 }
877 }
878
879 // Moving a candidate to HoistPoint keeps it dominating its other users only
880 // if HoistPoint dominates the candidate's current position.
881 if (any_of(Range&: HoistCandidates, P: [&VPDT, HoistPoint](VPRecipeBase *R) {
882 return !VPDT.properlyDominates(A: HoistPoint, B: R);
883 }))
884 return false;
885
886 // Order recipes to hoist by dominance so earlier instructions are processed
887 // first.
888 sort(C&: HoistCandidates, Comp: [&VPDT](const VPRecipeBase *A, const VPRecipeBase *B) {
889 return VPDT.properlyDominates(A, B);
890 });
891
892 for (VPRecipeBase *HoistCandidate : HoistCandidates) {
893 HoistCandidate->moveBefore(I: HoistPoint->getIterator());
894 }
895
896 return true;
897}
898
899/// Sink users of fixed-order recurrences past or hoist before the recipe
900/// defining the previous value, introduce FirstOrderRecurrenceSplice
901/// VPInstructions, and replace FOR uses. Returns false if hoisting or sinking
902/// fails.
903static bool tryToSinkOrHoistRecurrenceUsers(VPBasicBlock *HeaderVPBB,
904 const VPDominatorTree &VPDT) {
905 auto FORs =
906 map_to_vector(C: make_filter_range(Range: HeaderVPBB->phis(),
907 Pred: IsaPred<VPFirstOrderRecurrencePHIRecipe>),
908 F: [](VPRecipeBase &R) {
909 return cast<VPFirstOrderRecurrencePHIRecipe>(Val: &R);
910 });
911 for (VPFirstOrderRecurrencePHIRecipe *FOR : FORs) {
912 // Follow through FOR phi chains to find the actual Previous recipe.
913 // Fixed-order recurrences do not contain cycles, so this loop is
914 // guaranteed to terminate.
915#ifndef NDEBUG
916 SmallPtrSet<VPFirstOrderRecurrencePHIRecipe *, 4> SeenPhis;
917#endif
918 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();
919 while (auto *PrevPhi =
920 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Val: Previous)) {
921 assert(PrevPhi->getParent() == FOR->getParent() &&
922 "PrevPhi must be in same block as FOR");
923 assert(SeenPhis.insert(PrevPhi).second &&
924 "PrevPhi must not be visited multiple times");
925 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();
926 }
927
928 VPBasicBlock::iterator InsertPt = FOR->getParent()->getFirstNonPhi();
929 if (Previous) {
930 // Sink FOR users after Previous or hoist Previous before FOR users.
931 if (!sinkRecurrenceUsersAfterPrevious(FOR, Previous, VPDT) &&
932 !hoistPreviousBeforeFORUsers(FOR, Previous, VPDT))
933 return false;
934 InsertPt = isa<VPHeaderPHIRecipe>(Val: Previous)
935 ? Previous->getParent()->getFirstNonPhi()
936 : std::next(x: Previous->getIterator());
937 }
938
939 // Create FirstOrderRecurrenceSplice and replace FOR uses.
940 VPBuilder LoopBuilder(InsertPt);
941 auto *RecurSplice =
942 LoopBuilder.createNaryOp(Opcode: VPInstruction::FirstOrderRecurrenceSplice,
943 Operands: {FOR, FOR->getBackedgeValue()});
944 FOR->replaceUsesWithIf(New: RecurSplice, ShouldReplace: not_equal_to(Arg&: RecurSplice));
945 }
946
947 return true;
948}
949
950bool VPlanTransforms::createHeaderPhiRecipes(
951 VPlan &Plan, PredicatedScalarEvolution &PSE, Loop &OrigLoop,
952 OptimizationRemarkEmitter *ORE, const VPDominatorTree &VPDT,
953 const MapVector<PHINode *, InductionDescriptor> &Inductions,
954 const MapVector<PHINode *, RecurrenceDescriptor> &Reductions,
955 const MapVector<PHINode *, ConditionalInductionDescriptor>
956 &ConditionalInductions,
957 const SmallPtrSetImpl<const PHINode *> &FixedOrderRecurrences,
958 const SmallPtrSetImpl<PHINode *> &InLoopReductions, bool AllowReordering) {
959 // Retrieve the header manually from the intial plain-CFG VPlan.
960 auto [HeaderVPBB, LatchVPBB] = VPBlockUtils::getPlainCFGHeaderAndLatch(Plan);
961 assert(VPDT.dominates(HeaderVPBB, LatchVPBB) &&
962 "header must dominate its latch");
963
964 auto CreateHeaderPhiRecipe = [&](VPPhi *PhiR) -> VPHeaderPHIRecipe * {
965 // TODO: Gradually replace uses of underlying instruction by analyses on
966 // VPlan.
967 auto *Phi = cast<PHINode>(Val: PhiR->getUnderlyingInstr());
968 assert(PhiR->getNumOperands() == 2 &&
969 "Must have 2 operands for header phis");
970
971 // Extract common values once.
972 VPIRValue *Start = cast<VPIRValue>(Val: PhiR->getOperand(N: 0));
973 VPValue *BackedgeValue = PhiR->getOperand(N: 1);
974
975 if (FixedOrderRecurrences.contains(Ptr: Phi)) {
976 // TODO: Currently fixed-order recurrences are modeled as chains of
977 // first-order recurrences. If there are no users of the intermediate
978 // recurrences in the chain, the fixed order recurrence should be
979 // modeled directly, enabling more efficient codegen.
980 return new VPFirstOrderRecurrencePHIRecipe(Phi, *Start, *BackedgeValue);
981 }
982
983 auto InductionIt = Inductions.find(Key: Phi);
984 if (InductionIt != Inductions.end())
985 return createWidenInductionRecipe(Phi, PhiR, Start, IndDesc: InductionIt->second,
986 Plan, PSE, OrigLoop,
987 DL: PhiR->getDebugLoc());
988
989 auto ConditionalInductionIt = ConditionalInductions.find(Key: Phi);
990 if (ConditionalInductionIt != ConditionalInductions.end()) {
991 const ConditionalInductionDescriptor &CondID =
992 ConditionalInductionIt->second;
993 return new VPConditionalInductionPHIRecipe(*Phi, *Start, *BackedgeValue,
994 CondID.getStepSCEV());
995 }
996
997 assert(Reductions.contains(Phi) && "only reductions are expected now");
998 const RecurrenceDescriptor &RdxDesc = Reductions.lookup(Key: Phi);
999 assert(RdxDesc.getRecurrenceStartValue() ==
1000 Phi->getIncomingValueForBlock(OrigLoop.getLoopPreheader()) &&
1001 "incoming value must match start value");
1002 // Will be updated later to >1 if reduction is partial.
1003 unsigned ScaleFactor = 1;
1004 bool UseOrderedReductions = !AllowReordering && RdxDesc.isOrdered();
1005 return new VPReductionPHIRecipe(
1006 Phi, RdxDesc.getRecurrenceKind(), *Start, *BackedgeValue,
1007 getReductionStyle(InLoop: InLoopReductions.contains(Ptr: Phi), Ordered: UseOrderedReductions,
1008 ScaleFactor),
1009 Phi->getType()->isFloatingPointTy() ? RdxDesc.getFastMathFlags()
1010 : VPIRFlags(),
1011 RdxDesc.hasUsesOutsideReductionChain());
1012 };
1013
1014 for (VPRecipeBase &R : make_early_inc_range(Range: HeaderVPBB->phis())) {
1015 auto *PhiR = cast<VPPhi>(Val: &R);
1016 VPHeaderPHIRecipe *HeaderPhiR = CreateHeaderPhiRecipe(PhiR);
1017 HeaderPhiR->insertBefore(InsertPos: PhiR);
1018 PhiR->replaceAllUsesWith(New: HeaderPhiR);
1019 PhiR->eraseFromParent();
1020 }
1021
1022 if (!tryToSinkOrHoistRecurrenceUsers(HeaderVPBB, VPDT)) {
1023 reportVectorizationFailure(
1024 DebugMsg: "Failed to sink or hoist user of first-order recurrence",
1025 ORETag: "CannotSinkHoistFORUser", ORE, TheLoop: &OrigLoop);
1026 return false;
1027 }
1028
1029 // Skip renaming resume phi recipes, if any header phi has been removed.
1030 if (range_size(Range: HeaderVPBB->phis()) !=
1031 range_size(Range: Plan.getScalarPreheader()->phis()))
1032 return true;
1033 for (const auto &[HeaderPhiR, ScalarPhiR] :
1034 zip_equal(t: HeaderVPBB->phis(), u: Plan.getScalarPreheader()->phis())) {
1035 auto *ResumePhiR = cast<VPPhi>(Val: &ScalarPhiR);
1036 if (isa<VPFirstOrderRecurrencePHIRecipe>(Val: &HeaderPhiR)) {
1037 ResumePhiR->setName("scalar.recur.init");
1038 auto *ExtractLastLane = cast<VPInstruction>(Val: ResumePhiR->getOperand(N: 0));
1039 ExtractLastLane->setName("vector.recur.extract");
1040 continue;
1041 }
1042 ResumePhiR->setName(isa<VPWidenInductionRecipe>(Val: HeaderPhiR)
1043 ? "bc.resume.val"
1044 : "bc.merge.rdx");
1045 }
1046 return true;
1047}
1048
1049bool VPlanTransforms::finalizeSCEVPredicates(VPlan &Plan,
1050 PredicatedScalarEvolution &PSE,
1051 bool OptForSize,
1052 unsigned SCEVCheckThreshold,
1053 OptimizationRemarkEmitter *ORE,
1054 Loop *TheLoop) {
1055 // Collect which wide IVs have predicates and add them to PSE.
1056 auto [HeaderVPBB, _] = VPBlockUtils::getPlainCFGHeaderAndLatch(Plan);
1057 SmallPtrSet<VPWidenInductionRecipe *, 4> PredicatedIVs;
1058 for (VPWidenInductionRecipe &WideIV :
1059 make_isa_range<VPWidenInductionRecipe>(Range: HeaderVPBB->phis())) {
1060 if (WideIV.getNoWrapPredicates().empty())
1061 continue;
1062 PredicatedIVs.insert(Ptr: &WideIV);
1063 for (const auto *P : WideIV.getNoWrapPredicates())
1064 PSE.addPredicate(Pred: *P);
1065 }
1066
1067 unsigned TotalComplexity = PSE.getPredicate().getComplexity();
1068 if (TotalComplexity && OptForSize) {
1069 LLVM_DEBUG(
1070 dbgs() << "LV: Not vectorizing: SCEV predicates needed for induction "
1071 "but optimizing for size\n");
1072 reportVectorizationFailure(
1073 DebugMsg: "Runtime SCEV check is required with -Os/-Oz",
1074 OREMsg: "runtime SCEV checks needed but optimizing for size",
1075 ORETag: "CantVersionLoopWithOptForSize", ORE, TheLoop);
1076 return false;
1077 }
1078
1079 if (TotalComplexity > SCEVCheckThreshold) {
1080 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Too many SCEV checks needed ("
1081 << TotalComplexity << " > " << SCEVCheckThreshold
1082 << ")\n");
1083 reportVectorizationFailure(
1084 DebugMsg: "Too many SCEV checks needed",
1085 OREMsg: "Too many SCEV assumptions need to be made and checked at runtime",
1086 ORETag: "TooManySCEVRunTimeChecks", ORE, TheLoop);
1087 return false;
1088 }
1089
1090 return true;
1091}
1092
1093void VPlanTransforms::createInLoopReductionRecipes(VPlan &Plan,
1094 ElementCount MinVF) {
1095 VPBasicBlock *Header = Plan.getVectorLoopRegion()->getEntryBasicBlock();
1096 SmallVector<VPRecipeBase *> ToDelete;
1097
1098 for (VPRecipeBase &R : Header->phis()) {
1099 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(Val: &R);
1100 if (!PhiR || !PhiR->isInLoop() || (MinVF.isScalar() && !PhiR->isOrdered()))
1101 continue;
1102
1103 RecurKind Kind = PhiR->getRecurrenceKind();
1104 assert(!RecurrenceDescriptor::isFindLastRecurrenceKind(Kind) &&
1105 !RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) &&
1106 !RecurrenceDescriptor::isFindIVRecurrenceKind(Kind) &&
1107 "AnyOf and Find reductions are not allowed for in-loop reductions");
1108
1109 bool IsFPRecurrence =
1110 RecurrenceDescriptor::isFloatingPointRecurrenceKind(Kind);
1111 FastMathFlags FMFs =
1112 IsFPRecurrence ? FastMathFlags::getFast() : FastMathFlags();
1113
1114 // Collect the chain of "link" recipes for the reduction starting at PhiR.
1115 SetVector<VPSingleDefRecipe *> Worklist;
1116 Worklist.insert(X: PhiR);
1117 for (unsigned I = 0; I != Worklist.size(); ++I) {
1118 VPSingleDefRecipe *Cur = Worklist[I];
1119 for (VPUser *U : Cur->users()) {
1120 auto *UserRecipe = cast<VPSingleDefRecipe>(Val: U);
1121 if (!UserRecipe->getParent()->getEnclosingLoopRegion()) {
1122 assert((UserRecipe->getParent() == Plan.getMiddleBlock() ||
1123 UserRecipe->getParent() == Plan.getScalarPreheader()) &&
1124 "U must be either in the loop region, the middle block or the "
1125 "scalar preheader.");
1126 continue;
1127 }
1128
1129 // Stores using instructions will be sunk later.
1130 if (match(R: UserRecipe, P: m_VPInstruction<Instruction::Store>()))
1131 continue;
1132 Worklist.insert(X: UserRecipe);
1133 }
1134 }
1135
1136 // Visit operation "Links" along the reduction chain top-down starting from
1137 // the phi until LoopExitValue. We keep track of the previous item
1138 // (PreviousLink) to tell which of the two operands of a Link will remain
1139 // scalar and which will be reduced. For minmax by select(cmp), Link will be
1140 // the select instructions. A blend of the in-loop reduction phi is folded
1141 // to its non-phi operand; all links are masked by the blend's mask for that
1142 // operand instead, as the chain only contributes on that edge.
1143 VPValue *BlendMask = nullptr;
1144 VPBasicBlock *BlendVPBB = nullptr;
1145 auto BlendIt = find_if(Range&: Worklist, P: IsaPred<VPBlendRecipe>);
1146 if (BlendIt != Worklist.end()) {
1147 auto *Blend = cast<VPBlendRecipe>(Val: *BlendIt);
1148 assert(Blend->getNumIncomingValues() == 2 &&
1149 "Blend must have 2 incoming values");
1150 unsigned ChainIdx = Blend->getIncomingValue(Idx: 0) == PhiR ? 1 : 0;
1151 assert(Blend->getIncomingValue(1 - ChainIdx) == PhiR &&
1152 "PhiR must be an operand of the blend");
1153 BlendMask = Blend->getMask(Idx: ChainIdx);
1154 BlendVPBB = Blend->getParent();
1155 Blend->replaceAllUsesWith(New: Blend->getIncomingValue(Idx: ChainIdx));
1156 ToDelete.push_back(Elt: Blend);
1157 Worklist.erase(I: BlendIt);
1158 }
1159
1160 VPSingleDefRecipe *PreviousLink = PhiR; // Aka Worklist[0].
1161 for (VPSingleDefRecipe *CurrentLink : drop_begin(RangeOrContainer&: Worklist)) {
1162 if (IsFPRecurrence) {
1163 FastMathFlags CurFMF =
1164 cast<VPRecipeWithIRFlags>(Val: CurrentLink)->getFastMathFlagsOrNone();
1165 if (match(R: CurrentLink, P: m_Select(Op0: m_VPValue(), Op1: m_VPValue(), Op2: m_VPValue())))
1166 CurFMF |= cast<VPRecipeWithIRFlags>(Val: CurrentLink->getOperand(N: 0))
1167 ->getFastMathFlagsOrNone();
1168 FMFs &= CurFMF;
1169 }
1170
1171 Instruction *CurrentLinkI = CurrentLink->getUnderlyingInstr();
1172
1173 // Recognize a call to the llvm.fmuladd intrinsic.
1174 bool IsFMulAdd = Kind == RecurKind::FMulAdd;
1175 VPValue *VecOp;
1176 VPBasicBlock *LinkVPBB = BlendVPBB ? BlendVPBB : CurrentLink->getParent();
1177 if (IsFMulAdd) {
1178 assert(RecurrenceDescriptor::isFMulAddIntrinsic(CurrentLinkI) &&
1179 "Expected current VPInstruction to be a call to the "
1180 "llvm.fmuladd intrinsic");
1181 assert(CurrentLink->getOperand(2) == PreviousLink &&
1182 "expected a call where the previous link is the added operand");
1183
1184 // If the instruction is a call to the llvm.fmuladd intrinsic then we
1185 // need to create an fmul recipe (multiplying the first two operands of
1186 // the fmuladd together) to use as the vector operand for the fadd
1187 // reduction.
1188 auto *FMulRecipe = new VPInstruction(
1189 Instruction::FMul,
1190 {CurrentLink->getOperand(N: 0), CurrentLink->getOperand(N: 1)},
1191 CurrentLinkI->getFastMathFlags());
1192 FMulRecipe->insertBefore(InsertPos: CurrentLink);
1193 VecOp = FMulRecipe;
1194 } else if (Kind == RecurKind::AddChainWithSubs &&
1195 match(R: CurrentLink, P: m_Sub(Op0: m_VPValue(), Op1: m_VPValue()))) {
1196 Type *PhiTy = PhiR->getScalarType();
1197 auto *Zero = Plan.getConstantInt(Ty: PhiTy, Val: 0);
1198 VPBuilder Builder(CurrentLink);
1199 auto *Sub = Builder.createSub(LHS: Zero, RHS: CurrentLink->getOperand(N: 1),
1200 DL: CurrentLinkI->getDebugLoc());
1201 Sub->setUnderlyingValue(CurrentLinkI);
1202 VecOp = Sub;
1203 } else {
1204 // Index of the first operand which holds a non-mask vector operand.
1205 unsigned IndexOfFirstOperand = 0;
1206 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind)) {
1207 if (match(R: CurrentLink, P: m_Cmp(Op0: m_VPValue(), Op1: m_VPValue())))
1208 continue;
1209 assert(match(CurrentLink,
1210 m_Select(m_VPValue(), m_VPValue(), m_VPValue())) &&
1211 "must be a select recipe");
1212 IndexOfFirstOperand = 1;
1213 }
1214 // Note that for non-commutable operands (cmp-selects), the semantics of
1215 // the cmp-select are captured in the recurrence kind.
1216 unsigned VecOpId =
1217 CurrentLink->getOperand(N: IndexOfFirstOperand) == PreviousLink
1218 ? IndexOfFirstOperand + 1
1219 : IndexOfFirstOperand;
1220 VecOp = CurrentLink->getOperand(N: VecOpId);
1221 assert(
1222 VecOp != PreviousLink &&
1223 CurrentLink->getOperand(
1224 cast<VPInstruction>(CurrentLink)->getNumOperandsWithoutMask() -
1225 1 - (VecOpId - IndexOfFirstOperand)) == PreviousLink &&
1226 "PreviousLink must be the operand other than VecOp");
1227 }
1228
1229 assert(PhiR->getVFScaleFactor() == 1 &&
1230 "inloop reductions must be unscaled");
1231 VPValue *CondOp =
1232 BlendMask ? BlendMask : cast<VPInstruction>(Val: CurrentLink)->getMask();
1233 auto *RedRecipe = new VPReductionRecipe(
1234 Kind, FMFs, CurrentLinkI, PreviousLink, VecOp, CondOp,
1235 getReductionStyle(/*IsInLoop=*/InLoop: true, Ordered: PhiR->isOrdered(), ScaleFactor: 1),
1236 CurrentLinkI->getDebugLoc());
1237 // Append the recipe to the end of the VPBasicBlock because we need to
1238 // ensure that it comes after all of it's inputs, including CondOp.
1239 // Delete CurrentLink as it will be invalid if its operand is replaced
1240 // with a reduction defined at the bottom of the block in the next link.
1241 if (LinkVPBB->getNumSuccessors() == 0)
1242 RedRecipe->insertBefore(InsertPos: &*std::prev(x: std::prev(x: LinkVPBB->end())));
1243 else
1244 LinkVPBB->appendRecipe(Recipe: RedRecipe);
1245
1246 CurrentLink->replaceAllUsesWith(New: RedRecipe);
1247 // Move any store recipes using the RedRecipe that appear before it in the
1248 // same block to just after the RedRecipe. With a blend, the RedRecipe is
1249 // placed in the blend's block, after stores in earlier blocks, so move
1250 // all of them.
1251 for (VPRecipeBase *UserR : make_early_inc_range(
1252 Range: make_isa_range<VPRecipeBase>(Range: RedRecipe->users()))) {
1253 if (!BlendVPBB && UserR->getParent() != LinkVPBB)
1254 continue;
1255 if (!match(V: UserR, P: m_VPInstruction<Instruction::Store>()))
1256 continue;
1257 assert(UserR->getOperand(0) == RedRecipe &&
1258 UserR->getOperand(1)->isDefinedOutsideLoopRegions() &&
1259 "only invariant stores of the reduction can be moved");
1260 UserR->moveAfter(MovePos: RedRecipe);
1261 }
1262 ToDelete.push_back(Elt: CurrentLink);
1263 // The compare of a min/max select is dead once the select is replaced,
1264 // and may use RedRecipe before its definition.
1265 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind)) {
1266 VPValue *Cmp = CurrentLink->getOperand(N: 0);
1267 assert(Cmp->hasOneUse() && "compare must only be used by the select");
1268 ToDelete.push_back(Elt: Cmp->getDefiningRecipe());
1269 }
1270 PreviousLink = RedRecipe;
1271 }
1272 }
1273
1274 for (VPRecipeBase *R : ToDelete)
1275 R->eraseFromParent();
1276}
1277
1278bool VPlanTransforms::areAllLoadsDereferenceable(VPBasicBlock *HeaderVPBB,
1279 Loop *TheLoop,
1280 PredicatedScalarEvolution &PSE,
1281 DominatorTree &DT,
1282 AssumptionCache *AC) {
1283 ScalarEvolution &SE = *PSE.getSE();
1284 const DataLayout &DL = TheLoop->getHeader()->getDataLayout();
1285 for (VPBasicBlock *VPBB : vp_rpo_plain_cfg_loop_body(Header: HeaderVPBB)) {
1286 for (VPRecipeBase &R : *VPBB) {
1287 // Pseudo-probes are profiling placeholders with side effects but no real
1288 // memory access. They are modeled as reading inaccessible memory, so skip
1289 // them here to stay consistent with isReadOnlyLoop(), which classifies
1290 // such loops as read-only.
1291 if (match(V: &R, P: m_Intrinsic<Intrinsic::pseudoprobe>()))
1292 continue;
1293 auto *VPI = dyn_cast<VPInstruction>(Val: &R);
1294 if (!VPI || VPI->getOpcode() != Instruction::Load) {
1295 assert(!R.mayReadFromMemory() && "unexpected recipe reading memory");
1296 continue;
1297 }
1298
1299 // Get the pointer SCEV for dereferenceability checking.
1300 VPValue *Ptr = VPI->getOperand(N: 0);
1301 const SCEV *PtrSCEV = vputils::getSCEVExprForVPValue(V: Ptr, PSE, L: TheLoop);
1302 if (isa<SCEVCouldNotCompute>(Val: PtrSCEV)) {
1303 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Found non-dereferenceable "
1304 "load with SCEVCouldNotCompute pointer\n");
1305 return false;
1306 }
1307
1308 // Check dereferenceability using the SCEV-based version.
1309 Type *LoadTy = VPI->getScalarType();
1310 const SCEV *SizeSCEV =
1311 SE.getStoreSizeOfExpr(IntTy: DL.getIndexType(PtrTy: PtrSCEV->getType()), StoreTy: LoadTy);
1312 auto *Load = cast<LoadInst>(Val: VPI->getUnderlyingValue());
1313 SmallVector<const SCEVPredicate *> Preds;
1314 if (isDereferenceableAndAlignedInLoop(PtrSCEV, Alignment: Load->getAlign(), EltSizeSCEV: SizeSCEV,
1315 L: TheLoop, SE, DT, AC, Predicates: &Preds))
1316 continue;
1317
1318 return false;
1319 }
1320 }
1321 return true;
1322}
1323
1324void VPlanTransforms::handleCountableEarlyExits(VPlan &Plan) {
1325 auto *MiddleVPBB = VPBlockUtils::getPlainCFGMiddleBlock(Plan);
1326 // Disconnect countable early exits from the loop, leaving it with a single
1327 // exit from the latch. Countable early exits are left for a scalar epilog.
1328 for (auto [EarlyExitingVPBB, EB] : vputils::getEarlyExits(Plan, MiddleVPBB)) {
1329 // Remove phi operands for the early exiting block.
1330 for (VPRecipeBase &R : EB->phis())
1331 cast<VPIRPhi>(Val: &R)->removeIncomingValueFor(IncomingBlock: EarlyExitingVPBB);
1332 EarlyExitingVPBB->getTerminator()->eraseFromParent();
1333 VPBlockUtils::disconnectBlocks(From: EarlyExitingVPBB, To: EB);
1334 }
1335}
1336
1337void VPlanTransforms::addMiddleCheck(VPlan &Plan) {
1338 auto *MiddleVPBB = VPBlockUtils::getPlainCFGMiddleBlock(Plan);
1339 // If MiddleVPBB has a single successor then the original loop does not exit
1340 // via the latch and the single successor must be the scalar preheader.
1341 // There's no need to add a runtime check to MiddleVPBB.
1342 if (MiddleVPBB->getNumSuccessors() == 1) {
1343 assert(MiddleVPBB->getSingleSuccessor() == Plan.getScalarPreheader() &&
1344 "must have ScalarPH as single successor");
1345 return;
1346 }
1347
1348 assert(MiddleVPBB->getNumSuccessors() == 2 && "must have 2 successors");
1349
1350 // Add a check in the middle block to see if we have completed all of the
1351 // iterations in the first vector loop.
1352 //
1353 // Three cases:
1354 // 1) If we require a scalar epilogue, the scalar ph must execute. Set the
1355 // condition to false.
1356 // 2) If (N - N%VF) == N, then we *don't* need to run the
1357 // remainder. Thus if tail is to be folded, we know we don't need to run
1358 // the remainder and we can set the condition to true.
1359 // 3) Otherwise, construct a runtime check.
1360
1361 // We use the same DebugLoc as the scalar loop latch terminator instead of
1362 // the corresponding compare because they may have ended up with different
1363 // line numbers and we want to avoid awkward line stepping while debugging.
1364 // E.g., if the compare has got a line number inside the loop.
1365 auto *LatchVPBB = cast<VPBasicBlock>(Val: MiddleVPBB->getSinglePredecessor());
1366 DebugLoc LatchDL = LatchVPBB->getTerminator()->getDebugLoc();
1367 VPBuilder Builder(MiddleVPBB);
1368 VPValue *Cmp =
1369 Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: Plan.getTripCount(),
1370 B: &Plan.getVectorTripCount(), DL: LatchDL, Name: "cmp.n");
1371 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cmp}, DL: LatchDL);
1372}
1373
1374void VPlanTransforms::createLoopRegions(VPlan &Plan, DebugLoc DL) {
1375 VPDominatorTree VPDT(Plan);
1376 PostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> POT(
1377 Plan.getEntry());
1378 // Headers and latches have been canonicalized by addInitialSkeleton.
1379 for (VPBlockBase *HeaderVPB : POT) {
1380 if (!VPBlockUtils::isHeader(VPB: HeaderVPB, VPDT))
1381 continue;
1382 assert(HeaderVPB->getPredecessors()[1]->getSuccessors().back() ==
1383 HeaderVPB &&
1384 "latch must have the header as last successor");
1385 createLoopRegion(Plan, HeaderVPB, DL);
1386 }
1387
1388 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
1389 TopRegion->setName("vector loop");
1390 TopRegion->getEntryBasicBlock()->setName("vector.body");
1391}
1392
1393void VPlanTransforms::foldTailByMasking(VPlan &Plan) {
1394 assert(Plan.getExitBlocks().size() == 1 &&
1395 "only a single-exit block is supported currently");
1396 assert(Plan.getExitBlocks().front()->getSinglePredecessor() ==
1397 Plan.getMiddleBlock() &&
1398 "the exit block must have middle block as single predecessor");
1399
1400 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
1401 assert(LoopRegion->getSingleSuccessor() == Plan.getMiddleBlock() &&
1402 "The vector loop region must have the middle block as its single "
1403 "successor for now");
1404 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
1405
1406 Header->splitAt(SplitAt: Header->getFirstNonPhi());
1407
1408 // Abstract header mask, materialized into concrete recipes later.
1409 VPValue *HeaderMask = LoopRegion->createHeaderMask();
1410 VPBuilder Builder(Header->getFirstNonPhi());
1411 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: HeaderMask);
1412
1413 VPBasicBlock *OrigLatch = LoopRegion->getExitingBasicBlock();
1414 VPValue *IVInc;
1415 [[maybe_unused]] bool TermBranchOnCount =
1416 match(V: OrigLatch->getTerminator(),
1417 P: m_BranchOnCount(Op0: m_VPValue(V&: IVInc),
1418 Op1: m_Specific(VPV: &Plan.getVectorTripCount())));
1419 assert(TermBranchOnCount &&
1420 match(IVInc, m_Add(m_Specific(LoopRegion->getCanonicalIV()),
1421 m_Specific(&Plan.getVFxUF()))) &&
1422 std::next(IVInc->getDefiningRecipe()->getIterator()) ==
1423 OrigLatch->getTerminator()->getIterator() &&
1424 "Unexpected canonical iv increment");
1425
1426 // Split the latch at the IV update, and branch to it from the header mask.
1427 VPBasicBlock *Latch =
1428 OrigLatch->splitAt(SplitAt: IVInc->getDefiningRecipe()->getIterator());
1429 Latch->setName("vector.latch");
1430 VPBlockUtils::connectBlocks(From: Header, To: Latch);
1431
1432 // Collect any values defined in the loop that need a phi, that is header phis
1433 // and any value defined n the loop and used in the middle block.
1434 // TODO: Handle early exits via Plan.getExitBlocks()
1435 MapVector<VPValue *, SmallVector<VPUser *>> NeedsPhi;
1436 auto CollectBypassedOperands = [&](VPRecipeBase &R) {
1437 for (VPValue *Op : R.operands()) {
1438 auto *DefR = Op->getDefiningRecipe();
1439 if (DefR && DefR->getParent()->getEnclosingLoopRegion() == LoopRegion &&
1440 !is_contained(Set: {Header, Latch}, Element: DefR->getParent()))
1441 NeedsPhi[Op].push_back(Elt: &R);
1442 }
1443 };
1444 for (VPRecipeBase &R : Header->phis())
1445 CollectBypassedOperands(R);
1446 for (VPRecipeBase &R : *Plan.getMiddleBlock())
1447 CollectBypassedOperands(R);
1448
1449 // Insert phis for values coming past the end of the tail.
1450 Builder.setInsertPoint(Latch->begin());
1451 for (const auto &[V, Users] : NeedsPhi) {
1452 VPValue *TailVal = Plan.getPoison(Ty: V->getScalarType());
1453 std::optional<VPIRFlags> Flags;
1454 assert(llvm::count_if(Users, IsaPred<VPReductionPHIRecipe>) <= 1 &&
1455 "Value used by more than two reduction phis?");
1456 auto *RedIt = find_if(Range: Users, P: IsaPred<VPReductionPHIRecipe>);
1457 auto *RdxPhi =
1458 RedIt != Users.end() ? cast<VPReductionPHIRecipe>(Val: *RedIt) : nullptr;
1459 if (RdxPhi && !RdxPhi->isInLoop()) {
1460 TailVal = RdxPhi;
1461 Flags = *RdxPhi;
1462 }
1463
1464 VPInstruction *Phi = Builder.createScalarPhi(IncomingValues: {V, TailVal}, DL: {}, Name: "", Flags);
1465 for (VPUser *U : Users)
1466 U->replaceUsesOfWith(From: V, To: Phi);
1467 }
1468
1469 // Any extract of the last element must be updated to extract from the last
1470 // active lane of the header mask instead (i.e., the lane corresponding to the
1471 // last active iteration).
1472 Builder.setInsertPoint(Plan.getMiddleBlock()->getTerminator());
1473 for (VPRecipeBase &R : *Plan.getMiddleBlock()) {
1474 VPValue *Op;
1475 if (!match(V: &R, P: m_ExtractLastLaneOfLastPart(Op0: m_VPValue(V&: Op))))
1476 continue;
1477
1478 // Compute the index of the last active lane.
1479 VPValue *LastActiveLane = Builder.createLastActiveLane(Masks: HeaderMask);
1480 auto *Ext =
1481 Builder.createNaryOp(Opcode: VPInstruction::ExtractLane, Operands: {LastActiveLane, Op});
1482 R.getVPSingleValue()->replaceAllUsesWith(New: Ext);
1483 }
1484
1485 // VectorTripCount now equals TripCount so simplify the MiddleVPBB branch.
1486 assert(match(Plan.getMiddleBlock()->getTerminator(),
1487 m_BranchOnCond(m_SpecificICmp(
1488 CmpInst::ICMP_EQ, m_Specific(Plan.getTripCount()),
1489 m_Specific(&Plan.getVectorTripCount())))) &&
1490 "Unexpected MiddleVPBB branch");
1491 Plan.getMiddleBlock()->getTerminator()->setOperand(I: 0, New: Plan.getTrue());
1492}
1493
1494/// Add an incoming value to all phis in \p VPBB for its just-added last
1495/// predecessor, re-using the value of the previously last one.
1496static void addIncomingForLastPredecessor(VPBasicBlock *VPBB) {
1497 for (VPRecipeBase &R : VPBB->phis()) {
1498 auto *Phi = cast<VPPhi>(Val: &R);
1499 assert(Phi->getNumIncoming() == VPBB->getNumPredecessors() - 1 &&
1500 "must have incoming values for all predecessors but the new one");
1501 Phi->addIncoming(IncomingV: Phi->getIncomingValue(Idx: Phi->getNumIncoming() - 1));
1502 }
1503}
1504
1505/// Insert \p CheckBlockVPBB on the edge leading to the vector preheader,
1506/// connecting it to both vector and scalar preheaders. Updates scalar
1507/// preheader phis to account for the new predecessor.
1508static void insertCheckBlockBeforeVectorLoop(VPlan &Plan,
1509 VPBasicBlock *CheckBlockVPBB) {
1510 VPBlockBase *VectorPH = Plan.getVectorPreheader();
1511 auto *ScalarPH = cast<VPBasicBlock>(Val: Plan.getScalarPreheader());
1512 VPBlockBase *PreVectorPH = VectorPH->getSinglePredecessor();
1513 VPBlockUtils::insertOnEdge(From: PreVectorPH, To: VectorPH, BlockPtr: CheckBlockVPBB);
1514 VPBlockUtils::connectBlocks(From: CheckBlockVPBB, To: ScalarPH);
1515 CheckBlockVPBB->swapSuccessors();
1516 addIncomingForLastPredecessor(VPBB: ScalarPH);
1517}
1518
1519VPIRBasicBlock *
1520VPlanTransforms::modelGeneratedMainLoopBlocks(VPlan &EpiPlan, VPlan &MainPlan,
1521 VPBasicBlock *MainCheck) {
1522 VPBasicBlock *VectorPH = EpiPlan.getVectorPreheader();
1523 assert(VectorPH && VectorPH->phis().empty() &&
1524 "vector preheader must exist and have no phis to update");
1525 auto *MainScalarPH = cast<VPIRBasicBlock>(Val: MainPlan.getScalarPreheader());
1526 assert(MainScalarPH->getIRBasicBlock()->phis().empty() &&
1527 "MainPlan must not have generated phis in its scalar preheader");
1528 auto *EpilogueCheck =
1529 EpiPlan.createEmptyVPIRBasicBlock(IRBB: MainScalarPH->getIRBasicBlock());
1530 VPBlockUtils::reassociateBlocks(Old: EpiPlan.getEntry(), New: EpilogueCheck);
1531
1532 // Map blocks from MainPlan to new, empty VPIRBasicBlocks in EpiPlan, so the
1533 // skeleton CFG can be modeled explicitly. MainPlan's entry maps to EpiPlan's
1534 // now-disconnected entry and its scalar PH to EpilogueCheck.
1535 VPBlockBase *MainEntry = MainPlan.getEntry();
1536 SmallMapVector<VPBlockBase *, VPBlockBase *, 8> MainToEpiVPBB;
1537 MainToEpiVPBB[MainEntry] = EpiPlan.getEntry();
1538 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT(
1539 MainEntry);
1540 for (VPIRBasicBlock *VPBB : VPBlockUtils::blocksAs<VPIRBasicBlock>(Range&: RPOT))
1541 // Skip entry block and exit blocks/scalar loop header; they are already
1542 // modeled in the epilogue plan.
1543 if (VPBB != MainEntry && VPBB != MainScalarPH && VPBB->hasSuccessors())
1544 MainToEpiVPBB[VPBB] =
1545 EpiPlan.createEmptyVPIRBasicBlock(IRBB: VPBB->getIRBasicBlock());
1546 MainToEpiVPBB[MainScalarPH] = EpilogueCheck;
1547
1548 // First, connect the edges from the bypass blocks (minimum iteration checks,
1549 // runtime checks) to the scalar preheader, in reverse order, to preserve the
1550 // predecessor order of the generated IR. The middle block is the first
1551 // predecessor. MainCheck only bypasses the main vector loop; connect it to
1552 // the epilogue vector preheader instead.
1553 VPBasicBlock *EpiScalarPH = EpiPlan.getScalarPreheader();
1554 for (VPBlockBase *MainVPBB :
1555 reverse(C: drop_begin(RangeOrContainer: MainScalarPH->predecessors()))) {
1556 VPBlockBase *EpiVPBB = MainToEpiVPBB.lookup(Key: MainVPBB);
1557 if (MainVPBB == MainCheck) {
1558 VPBlockUtils::connectBlocks(From: EpiVPBB, To: VectorPH);
1559 continue;
1560 }
1561 VPBlockUtils::connectBlocks(From: EpiVPBB, To: EpiScalarPH);
1562 addIncomingForLastPredecessor(VPBB: EpiScalarPH);
1563 }
1564
1565 // Mirror MainPlan's CFG, skipping the bypass edges connected above, which
1566 // come first, edges to blocks not modeled in EpiPlan and the main vector
1567 // loop's back-edge (to a block earlier in RPO), so EpiPlan contains no loop
1568 // it does not own.
1569 SmallPtrSet<VPBlockBase *, 8> Visited;
1570 for (auto &[MainVPBB, EpiVPBB] : drop_end(RangeOrContainer&: MainToEpiVPBB)) {
1571 Visited.insert(Ptr: MainVPBB);
1572 for (VPBlockBase *Succ :
1573 drop_begin(RangeOrContainer&: MainVPBB->getSuccessors(), N: EpiVPBB->getNumSuccessors()))
1574 if (auto *SuccVPBB = MainToEpiVPBB.lookup(Key: Succ);
1575 SuccVPBB && !Visited.contains(Ptr: Succ))
1576 VPBlockUtils::connectBlocks(From: EpiVPBB, To: SuccVPBB);
1577 }
1578 return EpilogueCheck;
1579}
1580
1581// Likelyhood of bypassing the vectorized loop due to a runtime check block,
1582// including memory overlap checks block and wrapping/unit-stride checks block.
1583static constexpr uint32_t CheckBypassWeights[] = {1, 127};
1584
1585/// Create a BranchOnCond terminator in \p CheckBlockVPBB. Optionally adds
1586/// branch weights.
1587static void addBypassBranch(VPlan &Plan, VPBasicBlock *CheckBlockVPBB,
1588 VPValue *Cond, bool AddBranchWeights) {
1589 DebugLoc DL = Plan.getVectorLoopRegion()->getCanonicalIV()->getDebugLoc();
1590 auto *Term = VPBuilder(CheckBlockVPBB)
1591 .createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cond}, DL);
1592 if (AddBranchWeights) {
1593 MDBuilder MDB(Plan.getContext());
1594 MDNode *BranchWeights =
1595 MDB.createBranchWeights(Weights: CheckBypassWeights, /*IsExpected=*/false);
1596 Term->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1597 }
1598}
1599
1600void VPlanTransforms::attachVPCheckBlock(VPlan &Plan, VPValue *Cond,
1601 VPBasicBlock *CheckBlock,
1602 bool AddBranchWeights) {
1603 insertCheckBlockBeforeVectorLoop(Plan, CheckBlockVPBB: CheckBlock);
1604 addBypassBranch(Plan, CheckBlockVPBB: CheckBlock, Cond, AddBranchWeights);
1605}
1606
1607void VPlanTransforms::attachCheckBlock(VPlan &Plan, Value *Cond,
1608 BasicBlock *CheckBlock,
1609 bool AddBranchWeights) {
1610 VPValue *CondVPV = Plan.getOrAddLiveIn(V: Cond);
1611 VPBasicBlock *CheckBlockVPBB = Plan.createVPIRBasicBlock(IRBB: CheckBlock);
1612 attachVPCheckBlock(Plan, Cond: CondVPV, CheckBlock: CheckBlockVPBB, AddBranchWeights);
1613}
1614
1615/// Generate recipes for the memory runtime checks \p Checks of \p TheLoop
1616/// using \p Builder and return the condition that is true if any check fails.
1617static VPValue *createRuntimeChecks(VPlan &Plan, VPBuilder &Builder,
1618 VPSCEVExpander &Expander,
1619 ArrayRef<RuntimePointerCheck> Checks,
1620 const Loop *TheLoop, ScalarEvolution &SE,
1621 DebugLoc DL) {
1622 // Expand each group's bounds once so all checks reuse the same frozen values.
1623 SmallDenseMap<const RuntimeCheckingPtrGroup *,
1624 std::tuple<VPValue *, VPValue *, const SCEV *>, 8>
1625 GroupToBounds;
1626 for (const auto &[A, B] : Checks) {
1627 for (const RuntimeCheckingPtrGroup *CG : {A, B}) {
1628 if (GroupToBounds.contains(Val: CG))
1629 continue;
1630 auto [Low, High, Stride] = getRuntimeCheckBounds(
1631 CG, TheLoop, SE, HoistRuntimeChecks: VectorizerParams::HoistRuntimeChecks);
1632 VPValue *Start = Expander.expand(S: Low);
1633 VPValue *End = Expander.expand(S: High);
1634 if (CG->NeedsFreeze) {
1635 Start = Builder.createFreeze(Op: Start, DL);
1636 End = Builder.createFreeze(Op: End, DL);
1637 }
1638 GroupToBounds[CG] = {Start, End, Stride};
1639 }
1640 }
1641
1642 VPValue *Cond = Plan.getFalse();
1643 SmallPtrSet<const SCEV *, 4> CheckedStrides;
1644 for (const auto &[A, B] : Checks) {
1645 auto [AStart, AEnd, AStride] = GroupToBounds[A];
1646 auto [BStart, BEnd, BStride] = GroupToBounds[B];
1647 // Compare B's bounds in A's address space, see addRuntimeChecks.
1648 Type *PtrTy = AStart->getScalarType();
1649 if (BStart->getScalarType() != PtrTy) {
1650 BStart = Builder.createScalarCast(Opcode: Instruction::AddrSpaceCast, Op: BStart,
1651 ResultTy: PtrTy, DL);
1652 BEnd =
1653 Builder.createScalarCast(Opcode: Instruction::AddrSpaceCast, Op: BEnd, ResultTy: PtrTy, DL);
1654 }
1655 VPValue *Bound0 =
1656 Builder.createICmp(Pred: CmpInst::ICMP_ULT, A: AStart, B: BEnd, DL, Name: "bound0");
1657 VPValue *Bound1 =
1658 Builder.createICmp(Pred: CmpInst::ICMP_ULT, A: BStart, B: AEnd, DL, Name: "bound1");
1659 VPValue *IsConflict =
1660 Builder.createAnd(LHS: Bound0, RHS: Bound1, DL, Name: "found.conflict");
1661 for (const SCEV *Stride : {AStride, BStride}) {
1662 if (!Stride || !CheckedStrides.insert(Ptr: Stride).second)
1663 continue;
1664 VPValue *StrideV = Expander.expand(S: Stride);
1665 VPValue *IsNegative = Builder.createICmp(
1666 Pred: CmpInst::ICMP_SLT, A: StrideV, B: Plan.getZero(Ty: StrideV->getScalarType()),
1667 DL, Name: "stride.check");
1668 IsConflict = Builder.createOr(LHS: IsConflict, RHS: IsNegative, DL);
1669 }
1670 Cond = Builder.createOr(LHS: Cond, RHS: IsConflict, DL, Name: "conflict.rdx");
1671 }
1672 return Cond;
1673}
1674
1675/// Generate recipes for the memory runtime difference checks \p Checks using
1676/// \p Builder and return the condition that is true if any check fails. Each
1677/// difference is compared against a threshold derived from \p VF and \p UF.
1678static VPValue *createDiffRuntimeChecks(VPlan &Plan, VPBuilder &Builder,
1679 VPSCEVExpander &Expander,
1680 ArrayRef<PointerDiffInfo> Checks,
1681 ScalarEvolution &SE, ElementCount VF,
1682 unsigned UF, DebugLoc DL) {
1683 // Set of operand pairs of already created compares, to allow detecting and
1684 // re-using redundant compares.
1685 SmallDenseSet<std::pair<const SCEV *, const SCEV *>, 8> SeenCompares;
1686 VPValue *Cond = Plan.getFalse();
1687 for (const auto &[SrcStart, SinkStart, AccessSize, NeedsFreeze] : Checks) {
1688 assert(UF * AccessSize > 0 &&
1689 "Threshold must be non-zero to use diff-check");
1690 Type *Ty = SinkStart->getType();
1691 const SCEV *TotalAccessSize = SE.getElementCount(Ty, EC: VF * UF * AccessSize);
1692 const SCEV *ThresholdMinusOneSCEV =
1693 SE.getMinusSCEV(LHS: TotalAccessSize, RHS: SE.getOne(Ty));
1694 const SCEV *DiffSCEV = SE.getMinusSCEV(LHS: SinkStart, RHS: SrcStart);
1695
1696 // If the same compare has already been created earlier, there is no need to
1697 // check it again.
1698 if (!SeenCompares.insert(V: {DiffSCEV, ThresholdMinusOneSCEV}).second)
1699 continue;
1700
1701 VPValue *ThresholdMinusOne = Expander.expand(S: ThresholdMinusOneSCEV);
1702 VPValue *Diff = Expander.expand(S: DiffSCEV);
1703 // Use (Diff - 1) <u (Threshold - 1), equivalent to 0 <u Diff <u Threshold,
1704 // to exclude Diff == 0 (equal pointers are safe).
1705 VPValue *DiffMinusOne =
1706 Builder.createSub(LHS: Diff, RHS: Plan.getConstantInt(Ty, Val: 1), DL);
1707 VPValue *IsConflict = Builder.createICmp(
1708 Pred: CmpInst::ICMP_ULT, A: DiffMinusOne, B: ThresholdMinusOne, DL, Name: "diff.check");
1709 if (NeedsFreeze)
1710 IsConflict = Builder.createFreeze(Op: IsConflict, DL, Name: "diff.check.fr");
1711 Cond = Builder.createOr(LHS: Cond, RHS: IsConflict, DL, Name: "conflict.rdx");
1712 }
1713 return Cond;
1714}
1715
1716void VPlanTransforms::attachMemoryChecks(
1717 VPlan &Plan, const RuntimePointerChecking &RtPtrChecking,
1718 const Loop *TheLoop, ScalarEvolution &SE, ElementCount VF, unsigned UF,
1719 bool AddBranchWeights) {
1720 assert(!RtPtrChecking.getChecks().empty() && "No checks to generate");
1721
1722 DebugLoc DL = TheLoop->getStartLoc();
1723 auto *MemCheckVPBB = Plan.createVPBasicBlock(Name: "vector.memcheck");
1724 VPBuilder Builder(MemCheckVPBB);
1725 VPSCEVExpander Expander(Builder, SE, DL, TheLoop->getParentLoop());
1726 auto DiffChecks = RtPtrChecking.getDiffChecks();
1727 VPValue *Cond =
1728 DiffChecks
1729 ? createDiffRuntimeChecks(Plan, Builder, Expander, Checks: *DiffChecks, SE,
1730 VF, UF, DL)
1731 : createRuntimeChecks(Plan, Builder, Expander,
1732 Checks: RtPtrChecking.getChecks(), TheLoop, SE, DL);
1733 attachVPCheckBlock(Plan, Cond, CheckBlock: MemCheckVPBB, AddBranchWeights);
1734}
1735
1736void VPlanTransforms::addMinimumIterationCheck(
1737 VPlan &Plan, ElementCount VF, unsigned UF,
1738 ElementCount MinProfitableTripCount, bool RequiresScalarEpilogue,
1739 bool TailFolded, Loop *OrigLoop, const uint32_t *MinItersBypassWeights,
1740 DebugLoc DL, PredicatedScalarEvolution &PSE, VPBasicBlock *CheckBlock) {
1741 // Generate code to check if the loop's trip count is less than VF * UF, or
1742 // equal to it in case a scalar epilogue is required; this implies that the
1743 // vector trip count is zero. This check also covers the case where adding one
1744 // to the backedge-taken count overflowed leading to an incorrect trip count
1745 // of zero. In this case we will also jump to the scalar loop.
1746 CmpInst::Predicate CmpPred =
1747 RequiresScalarEpilogue ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
1748 // If tail is to be folded, vector loop takes care of all iterations.
1749 VPValue *TripCountVPV = Plan.getTripCount();
1750 const SCEV *TripCount = vputils::getSCEVExprForVPValue(V: TripCountVPV, PSE);
1751 Type *TripCountTy = TripCount->getType();
1752 ScalarEvolution &SE = *PSE.getSE();
1753 auto GetMinTripCount = [&]() -> const SCEV * {
1754 // Compute max(MinProfitableTripCount, UF * VF) and return it.
1755 const SCEV *VFxUF =
1756 SE.getElementCount(Ty: TripCountTy, EC: (VF * UF), Flags: SCEV::FlagNUW);
1757 if (UF * VF.getKnownMinValue() >=
1758 MinProfitableTripCount.getKnownMinValue()) {
1759 // TODO: SCEV should be able to simplify test.
1760 return VFxUF;
1761 }
1762 const SCEV *MinProfitableTripCountSCEV =
1763 SE.getElementCount(Ty: TripCountTy, EC: MinProfitableTripCount, Flags: SCEV::FlagNUW);
1764 return SE.getUMaxExpr(LHS: MinProfitableTripCountSCEV, RHS: VFxUF);
1765 };
1766
1767 VPBuilder Builder(CheckBlock);
1768 VPValue *TripCountCheck = Plan.getFalse();
1769 const SCEV *Step = GetMinTripCount();
1770 // TripCountCheck = false, folding tail implies positive vector trip
1771 // count.
1772 if (!TailFolded) {
1773 // TODO: Emit unconditional branch to vector preheader instead of
1774 // conditional branch with known condition.
1775 TripCount = SE.applyLoopGuards(Expr: TripCount, L: OrigLoop);
1776 // Check if the trip count is < the step.
1777 if (SE.isKnownPredicate(Pred: CmpPred, LHS: TripCount, RHS: Step)) {
1778 // TODO: Ensure step is at most the trip count when determining max VF and
1779 // UF, w/o tail folding.
1780 TripCountCheck = Plan.getTrue();
1781 } else if (!SE.isKnownPredicate(Pred: CmpInst::getInversePredicate(pred: CmpPred),
1782 LHS: TripCount, RHS: Step)) {
1783 // Generate the minimum iteration check only if we cannot prove the
1784 // check is known to be true, or known to be false.
1785 VPValue *MinTripCountVPV =
1786 VPSCEVExpander(Builder, *PSE.getSE(), DL).expand(S: Step);
1787 TripCountCheck = Builder.createICmp(
1788 Pred: CmpPred, A: TripCountVPV, B: MinTripCountVPV, DL, Name: "min.iters.check");
1789 } // else step known to be < trip count, use TripCountCheck preset to false.
1790 }
1791 VPInstruction *Term =
1792 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {TripCountCheck}, DL);
1793 if (MinItersBypassWeights) {
1794 MDBuilder MDB(Plan.getContext());
1795 MDNode *BranchWeights = MDB.createBranchWeights(
1796 Weights: ArrayRef(MinItersBypassWeights, 2), /*IsExpected=*/false);
1797 Term->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1798 }
1799}
1800
1801void VPlanTransforms::addIterationCountCheckBlock(
1802 VPlan &Plan, ElementCount VF, unsigned UF, bool RequiresScalarEpilogue,
1803 Loop *OrigLoop, const uint32_t *MinItersBypassWeights, DebugLoc DL,
1804 PredicatedScalarEvolution &PSE) {
1805 auto *CheckBlock = Plan.createVPBasicBlock(Name: "vector.main.loop.iter.check");
1806 insertCheckBlockBeforeVectorLoop(Plan, CheckBlockVPBB: CheckBlock);
1807 addMinimumIterationCheck(Plan, VF, UF, MinProfitableTripCount: ElementCount::getFixed(MinVal: 0),
1808 RequiresScalarEpilogue, /*TailFolded=*/false,
1809 OrigLoop, MinItersBypassWeights, DL, PSE,
1810 CheckBlock);
1811}
1812
1813void VPlanTransforms::addMinimumVectorEpilogueIterationCheck(
1814 VPlan &Plan, VPValue *MainVectorTripCount, bool RequiresScalarEpilogue,
1815 ElementCount EpilogueVF, unsigned MainLoopStep, unsigned EpilogueLoopStep,
1816 ScalarEvolution &SE) {
1817 // Add the minimum iteration check for the epilogue vector loop.
1818 auto *EpilogueCheck =
1819 cast<VPBasicBlock>(Val: Plan.getVectorPreheader()->getPredecessors().front());
1820
1821 // A tail-folded epilogue handles any number of remaining iterations, so the
1822 // epilogue check never branches to the scalar preheader.
1823 if (Plan.hasTailFolded()) {
1824 assert(!RequiresScalarEpilogue &&
1825 "Expected no scalar epilogue for tail-folded plan");
1826 VPBuilder(EpilogueCheck)
1827 .createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: Plan.getFalse());
1828 return;
1829 }
1830
1831 VPBuilder Builder(cast<VPBasicBlock>(Val: Plan.getEntry()));
1832 VPValue *TC = Plan.getTripCount();
1833 VPValue *VFxUF = Builder.createExpandSCEV(
1834 Expr: SE.getElementCount(Ty: TC->getScalarType(), EC: EpilogueVF, Flags: SCEV::FlagNUW));
1835 Builder.setInsertPoint(EpilogueCheck);
1836 VPValue *Count = Builder.createSub(LHS: TC, RHS: MainVectorTripCount,
1837 DL: DebugLoc::getUnknown(), Name: "n.vec.remaining");
1838
1839 // Generate code to check if the loop's trip count is less than VF * UF of
1840 // the vector epilogue loop.
1841 auto P = RequiresScalarEpilogue ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
1842 auto *CheckMinIters = Builder.createICmp(
1843 Pred: P, A: Count, B: VFxUF, DL: DebugLoc::getUnknown(), Name: "min.epilog.iters.check");
1844 VPInstruction *Branch =
1845 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: CheckMinIters);
1846
1847 // We assume the remaining `Count` is equally distributed in
1848 // [0, MainLoopStep)
1849 // So the probability for `Count < EpilogueLoopStep` should be
1850 // min(MainLoopStep, EpilogueLoopStep) / MainLoopStep
1851 // TODO: Improve the estimate by taking the estimated trip count into
1852 // consideration.
1853 unsigned EstimatedSkipCount = std::min(a: MainLoopStep, b: EpilogueLoopStep);
1854 const uint32_t Weights[] = {EstimatedSkipCount,
1855 MainLoopStep - EstimatedSkipCount};
1856 MDBuilder MDB(Plan.getContext());
1857 MDNode *BranchWeights =
1858 MDB.createBranchWeights(Weights, /*IsExpected=*/false);
1859 Branch->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1860}
1861
1862/// Find and return the final select instruction of the FindIV result pattern
1863/// for the given \p BackedgeVal:
1864/// select(icmp ne ComputeReductionResult(ReducedIV), Sentinel),
1865/// ComputeReductionResult(ReducedIV), Start.
1866static VPInstruction *findFindIVSelect(VPValue *BackedgeVal) {
1867 return cast<VPInstruction>(
1868 Val: vputils::findRecipe(Start: BackedgeVal, Pred: [BackedgeVal](VPRecipeBase *R) {
1869 auto *VPI = dyn_cast<VPInstruction>(Val: R);
1870 return VPI &&
1871 matchFindIVResult(VPI, ReducedIV: m_Specific(VPV: BackedgeVal), Start: m_VPValue());
1872 }));
1873}
1874
1875bool VPlanTransforms::handleMaxMinNumReductions(VPlan &Plan) {
1876 auto GetMinOrMaxCompareValue =
1877 [](VPReductionPHIRecipe *RedPhiR) -> VPValue * {
1878 auto *MinOrMaxR =
1879 dyn_cast_or_null<VPRecipeWithIRFlags>(Val: RedPhiR->getBackedgeValue());
1880 if (!MinOrMaxR)
1881 return nullptr;
1882
1883 // Check that MinOrMaxR is a VPWidenIntrinsicRecipe or VPReplicateRecipe
1884 // with an intrinsic that matches the reduction kind.
1885 Intrinsic::ID ExpectedIntrinsicID =
1886 getMinMaxReductionIntrinsicOp(RK: RedPhiR->getRecurrenceKind());
1887 if (!match(V: MinOrMaxR, P: m_Intrinsic(IntrID: ExpectedIntrinsicID)))
1888 return nullptr;
1889
1890 // MinOrMaxR must combine RedPhiR directly with the new element, as the NaN
1891 // check added below only covers the other operand.
1892 // TODO: Support multi-step min/max chains (e.g. maxnum(l, maxnum(k, phi)))
1893 // by checking all operands feeding the chain for NaNs.
1894 if (MinOrMaxR->getOperand(N: 0) == RedPhiR)
1895 return MinOrMaxR->getOperand(N: 1);
1896 if (MinOrMaxR->getOperand(N: 1) == RedPhiR)
1897 return MinOrMaxR->getOperand(N: 0);
1898 return nullptr;
1899 };
1900
1901 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
1902 SmallVector<std::pair<VPReductionPHIRecipe *, VPValue *>>
1903 MinOrMaxNumReductionsToHandle;
1904 bool HasUnsupportedPhi = false;
1905 for (auto &R : LoopRegion->getEntryBasicBlock()->phis()) {
1906 if (isa<VPWidenIntOrFpInductionRecipe>(Val: &R))
1907 continue;
1908 auto *Cur = dyn_cast<VPReductionPHIRecipe>(Val: &R);
1909 if (!Cur) {
1910 // TODO: Also support fixed-order recurrence phis.
1911 HasUnsupportedPhi = true;
1912 continue;
1913 }
1914 if (!RecurrenceDescriptor::isFPMinMaxNumRecurrenceKind(
1915 Kind: Cur->getRecurrenceKind())) {
1916 HasUnsupportedPhi = true;
1917 continue;
1918 }
1919
1920 VPValue *MinOrMaxOp = GetMinOrMaxCompareValue(Cur);
1921 if (!MinOrMaxOp)
1922 return false;
1923
1924 MinOrMaxNumReductionsToHandle.emplace_back(Args&: Cur, Args&: MinOrMaxOp);
1925 }
1926
1927 if (MinOrMaxNumReductionsToHandle.empty())
1928 return true;
1929
1930 // We won't be able to resume execution in the scalar tail, if there are
1931 // unsupported header phis or there is no scalar tail at all, due to
1932 // tail-folding.
1933 if (HasUnsupportedPhi || !Plan.hasScalarTail())
1934 return false;
1935
1936 // TODO: Support loops with uncountable early exits; their latch is not
1937 // terminated by BranchOnCount.
1938 VPBasicBlock *LatchVPBB = LoopRegion->getExitingBasicBlock();
1939 if (!match(V: LatchVPBB->getTerminator(), P: m_BranchOnCount()))
1940 return false;
1941
1942 /// Check if the vector loop of \p Plan can early exit and restart
1943 /// execution of last vector iteration in the scalar loop. This requires all
1944 /// recipes up to early exit point be side-effect free as they are
1945 /// re-executed. Currently we check that the loop is free of any recipe that
1946 /// may write to memory. Expected to operate on an early VPlan w/o nested
1947 /// regions.
1948 for (VPBlockBase *VPB : vp_depth_first_shallow(
1949 G: Plan.getVectorLoopRegion()->getEntryBasicBlock())) {
1950 auto *VPBB = cast<VPBasicBlock>(Val: VPB);
1951 for (auto &R : *VPBB) {
1952 if (R.mayWriteToMemory() && !match(V: &R, P: m_BranchOnCount()))
1953 return false;
1954 }
1955 }
1956
1957 // Freeze MinOrMaxOps since:
1958 // * multiple uses are introduced and the value may be undef
1959 // * they feed into a branch condition, so block poison propagation to
1960 // prevent immediate UB
1961 for (auto &[Phi, MinOrMaxOp] : MinOrMaxNumReductionsToHandle) {
1962 VPRecipeBase *MinOrMaxR = Phi->getBackedgeValue()->getDefiningRecipe();
1963 VPInstruction *Freeze = VPBuilder(MinOrMaxR).createFreeze(Op: MinOrMaxOp);
1964 MinOrMaxR->replaceUsesOfWith(From: MinOrMaxOp, To: Freeze);
1965 MinOrMaxOp = Freeze;
1966 }
1967
1968 VPBuilder LatchBuilder(LatchVPBB->getTerminator());
1969 VPValue *AllNaNLanes = nullptr;
1970 SmallPtrSet<VPValue *, 2> RdxResults;
1971 for (const auto &[_, MinOrMaxOp] : MinOrMaxNumReductionsToHandle) {
1972 VPValue *RedNaNLanes =
1973 LatchBuilder.createFCmp(Pred: CmpInst::FCMP_UNO, A: MinOrMaxOp, B: MinOrMaxOp);
1974 AllNaNLanes = AllNaNLanes ? LatchBuilder.createOr(LHS: AllNaNLanes, RHS: RedNaNLanes)
1975 : RedNaNLanes;
1976 }
1977
1978 VPValue *AnyNaNLane =
1979 LatchBuilder.createNaryOp(Opcode: VPInstruction::AnyOf, Operands: {AllNaNLanes});
1980 VPBasicBlock *MiddleVPBB = Plan.getMiddleBlock();
1981 VPBuilder MiddleBuilder(MiddleVPBB->begin());
1982 for (const auto &[RedPhiR, _] : MinOrMaxNumReductionsToHandle) {
1983 assert(RecurrenceDescriptor::isFPMinMaxNumRecurrenceKind(
1984 RedPhiR->getRecurrenceKind()) &&
1985 "unsupported reduction");
1986
1987 // If we exit early due to NaNs, compute the final reduction result based on
1988 // the reduction phi at the beginning of the last vector iteration.
1989 auto *RdxResult = vputils::findComputeReductionResult(PhiR: RedPhiR);
1990 assert(RdxResult && "must find a ComputeReductionResult");
1991
1992 auto *NewSel = MiddleBuilder.createSelect(Cond: AnyNaNLane, TrueVal: RedPhiR,
1993 FalseVal: RdxResult->getOperand(N: 0));
1994 RdxResult->setOperand(I: 0, New: NewSel);
1995 assert(!RdxResults.contains(RdxResult) && "RdxResult already used");
1996 RdxResults.insert(Ptr: RdxResult);
1997 }
1998
1999 auto *LatchExitingBranch = LatchVPBB->getTerminator();
2000 assert(match(LatchExitingBranch, m_BranchOnCount(m_VPValue(), m_VPValue())) &&
2001 "Unexpected terminator");
2002 auto *IsLatchExitTaken = LatchBuilder.createICmp(
2003 Pred: CmpInst::ICMP_EQ, A: LatchExitingBranch->getOperand(N: 0),
2004 B: LatchExitingBranch->getOperand(N: 1));
2005 auto *AnyExitTaken = LatchBuilder.createOr(LHS: AnyNaNLane, RHS: IsLatchExitTaken);
2006 LatchBuilder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: AnyExitTaken);
2007 LatchExitingBranch->eraseFromParent();
2008
2009 // Update resume phis for inductions in the scalar preheader. If AnyNaNLane is
2010 // true, the resume from the start of the last vector iteration via the
2011 // canonical IV, otherwise from the original value.
2012 auto IsTC = [&Plan](VPValue *V) {
2013 return V == &Plan.getVectorTripCount() || V == Plan.getTripCount();
2014 };
2015 for (auto &R : Plan.getScalarPreheader()->phis()) {
2016 auto *ResumeR = cast<VPPhi>(Val: &R);
2017 VPValue *VecV = ResumeR->getOperand(N: 0);
2018 if (RdxResults.contains(Ptr: VecV))
2019 continue;
2020 if (auto *DerivedIV = dyn_cast<VPDerivedIVRecipe>(Val: VecV)) {
2021 VPValue *DIVTC = DerivedIV->getOperand(N: 1);
2022 if (DerivedIV->hasOneUse() && IsTC(DIVTC)) {
2023 auto *NewSel = MiddleBuilder.createSelect(
2024 Cond: AnyNaNLane, TrueVal: LoopRegion->getCanonicalIV(), FalseVal: DIVTC);
2025 DerivedIV->moveAfter(MovePos: MiddleBuilder.getRecipeAtInsertPoint());
2026 DerivedIV->setOperand(I: 1, New: NewSel);
2027 continue;
2028 }
2029 }
2030 // Bail out and abandon the current, partially modified, VPlan if we
2031 // encounter resume phi that cannot be updated yet.
2032 if (!IsTC(VecV)) {
2033 LLVM_DEBUG(dbgs() << "Found resume phi we cannot update for VPlan with "
2034 "FMaxNum/FMinNum reduction.\n");
2035 return false;
2036 }
2037 auto *NewSel = MiddleBuilder.createSelect(
2038 Cond: AnyNaNLane, TrueVal: LoopRegion->getCanonicalIV(), FalseVal: VecV);
2039 ResumeR->setOperand(I: 0, New: NewSel);
2040 }
2041
2042 auto *MiddleTerm = MiddleVPBB->getTerminator();
2043 MiddleBuilder.setInsertPoint(MiddleTerm);
2044 VPValue *MiddleCond = MiddleTerm->getOperand(N: 0);
2045 VPValue *NewCond =
2046 MiddleBuilder.createAnd(LHS: MiddleCond, RHS: MiddleBuilder.createNot(Operand: AnyNaNLane));
2047 MiddleTerm->setOperand(I: 0, New: NewCond);
2048 return true;
2049}
2050
2051bool VPlanTransforms::handleFindLastReductions(VPlan &Plan) {
2052 // We want to create the following nodes:
2053 // vector.body:
2054 // ...new WidenPHI recipe introduced to keep the mask value for the latest
2055 // iteration where any lane was active.
2056 // mask.phi = phi [ ir<false>, vector.ph ], [ vp<new.mask>, vector.body ]
2057 // ...data.phi (a VPReductionPHIRecipe for a FindLast reduction) already
2058 // exists, but needs updating to use 'new.data' for the backedge value.
2059 // data.phi = phi ir<default.val>, vp<new.data>
2060 //
2061 // ...'data' and 'compare' created by existing nodes...
2062 //
2063 // ...new recipes introduced to determine whether to update the reduction
2064 // values or keep the current one.
2065 // any.active = i1 any-of ir<compare>
2066 // new.mask = select vp<any.active>, ir<compare>, vp<mask.phi>
2067 // new.data = select vp<any.active>, ir<data>, ir<data.phi>
2068 //
2069 // middle.block:
2070 // ...extract-last-active replaces compute-reduction-result.
2071 // result = extract-last-active vp<new.data>, vp<new.mask>, ir<default.val>
2072
2073 SmallVector<VPReductionPHIRecipe *, 4> Phis;
2074 for (VPReductionPHIRecipe &PhiR : make_isa_range<VPReductionPHIRecipe>(
2075 Range: Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis())) {
2076 if (RecurrenceDescriptor::isFindLastRecurrenceKind(
2077 Kind: PhiR.getRecurrenceKind()))
2078 Phis.push_back(Elt: &PhiR);
2079 }
2080
2081 if (Phis.empty())
2082 return true;
2083
2084 VPValue *HeaderMask = Plan.getVectorLoopRegion()->getHeaderMask();
2085 for (VPReductionPHIRecipe *PhiR : Phis) {
2086 // Find the condition for the select/blend.
2087 VPValue *BackedgeSelect = PhiR->getBackedgeValue();
2088 VPValue *CondSelect = BackedgeSelect;
2089
2090 // If there's a header mask, the backedge select will not be the find-last
2091 // select.
2092 if (HeaderMask &&
2093 !match(V: BackedgeSelect,
2094 P: m_SelectLike(Op0: m_Specific(VPV: HeaderMask), Op1: m_VPValue(V&: CondSelect),
2095 Op2: m_Specific(VPV: PhiR))))
2096 return false;
2097
2098 VPValue *Cond = nullptr, *Op1 = nullptr, *Op2 = nullptr;
2099
2100 // If we're matching a blend rather than a select, there should be one
2101 // incoming value which is the data, then all other incoming values should
2102 // be the phi.
2103 auto MatchBlend = [&](VPRecipeBase *R) {
2104 auto *Blend = dyn_cast<VPBlendRecipe>(Val: R);
2105 if (!Blend)
2106 return false;
2107 assert(!Blend->isNormalized() && "must run before blend normalizaion");
2108 unsigned NumIncomingDataValues = 0;
2109 for (unsigned I = 0; I < Blend->getNumIncomingValues(); ++I) {
2110 VPValue *Incoming = Blend->getIncomingValue(Idx: I);
2111 if (Incoming != PhiR) {
2112 ++NumIncomingDataValues;
2113 Cond = Blend->getMask(Idx: I);
2114 Op1 = Incoming;
2115 Op2 = PhiR;
2116 }
2117 }
2118 return NumIncomingDataValues == 1;
2119 };
2120
2121 VPSingleDefRecipe *SelectR =
2122 cast<VPSingleDefRecipe>(Val: CondSelect->getDefiningRecipe());
2123 if (!match(R: SelectR,
2124 P: m_Select(Op0: m_VPValue(V&: Cond), Op1: m_VPValue(V&: Op1), Op2: m_VPValue(V&: Op2))) &&
2125 !MatchBlend(SelectR))
2126 return false;
2127
2128 // Bail out if PhiR has users other than the find-last select/blend and the
2129 // header mask select, e.g. nested blends. Then the data operand may be PhiR
2130 // on some paths and Cond does not determine the lanes to update.
2131 if (any_of(Range: PhiR->users(), P: [&](VPUser *U) {
2132 return U != SelectR && U != BackedgeSelect->getDefiningRecipe();
2133 }))
2134 return false;
2135
2136 assert(Cond != HeaderMask && "Cond must not be HeaderMask");
2137
2138 // Find final reduction computation and replace it with an
2139 // extract.last.active intrinsic.
2140 auto *RdxResult =
2141 findSingleUser<VPInstruction::ComputeReductionResult>(V: BackedgeSelect);
2142 assert(RdxResult && "Could not find reduction result");
2143
2144 // Add mask phi.
2145 VPBuilder Builder = VPBuilder::getToInsertAfter(R: PhiR);
2146 auto *MaskPHI = Builder.createWidenPhi(IncomingValues: Plan.getFalse());
2147
2148 // Add select for mask.
2149 Builder.setInsertPoint(SelectR);
2150
2151 if (Op1 == PhiR) {
2152 // Normalize to selecting the data operand when the condition is true by
2153 // swapping operands and negating the condition.
2154 std::swap(a&: Op1, b&: Op2);
2155 Cond = Builder.createNot(Operand: Cond);
2156 }
2157 assert(Op2 == PhiR && "data value must be selected if Cond is true");
2158
2159 if (HeaderMask)
2160 Cond = Builder.createLogicalAnd(LHS: HeaderMask, RHS: Cond);
2161
2162 Cond = Builder.createFreeze(Op: Cond);
2163 VPValue *AnyOf = Builder.createNaryOp(Opcode: VPInstruction::AnyOf, Operands: Cond);
2164 VPValue *MaskSelect = Builder.createSelect(Cond: AnyOf, TrueVal: Cond, FalseVal: MaskPHI);
2165 MaskPHI->addIncoming(IncomingV: MaskSelect);
2166
2167 // Replace select for data.
2168 VPValue *DataSelect =
2169 Builder.createSelect(Cond: AnyOf, TrueVal: Op1, FalseVal: Op2, DL: SelectR->getDebugLoc());
2170 SelectR->replaceAllUsesWith(New: DataSelect);
2171 PhiR->setBackedgeValue(DataSelect);
2172 SelectR->eraseFromParent();
2173
2174 Builder.setInsertPoint(RdxResult);
2175 auto *ExtractLastActive =
2176 Builder.createNaryOp(Opcode: VPInstruction::ExtractLastActive,
2177 Operands: {PhiR->getStartValue(), DataSelect, MaskSelect},
2178 DL: RdxResult->getDebugLoc());
2179 RdxResult->replaceAllUsesWith(New: ExtractLastActive);
2180 RdxResult->eraseFromParent();
2181 }
2182
2183 return true;
2184}
2185
2186/// Given a first argmin/argmax pattern with strict predicate consisting of
2187/// 1) a MinOrMax reduction \p MinOrMaxPhiR producing \p MinOrMaxResult,
2188/// 2) a wide induction \p WideIV,
2189/// 3) a FindLastIV reduction \p FindLastIVPhiR using \p WideIV,
2190/// return the smallest index of the FindLastIV reduction result using UMin,
2191/// unless \p MinOrMaxResult equals the start value of its MinOrMax reduction.
2192/// In that case, return the start value of the FindLastIV reduction instead.
2193/// If \p WideIV is not canonical, a new canonical wide IV is added, and the
2194/// final result is scaled back to the non-canonical \p WideIV.
2195/// The final value of the FindLastIV reduction is originally computed using
2196/// \p FindIVSelect, \p FindIVCmp, and \p FindIVRdxResult, which are replaced
2197/// and removed.
2198/// Returns true if the pattern was handled successfully, false otherwise.
2199static bool handleFirstArgMinOrMax(
2200 VPlan &Plan, VPReductionPHIRecipe *MinOrMaxPhiR,
2201 VPReductionPHIRecipe *FindLastIVPhiR, VPWidenIntOrFpInductionRecipe *WideIV,
2202 VPInstruction *MinOrMaxResult, VPInstruction *FindIVSelect,
2203 VPRecipeBase *FindIVCmp, VPInstruction *FindIVRdxResult) {
2204 assert(!FindLastIVPhiR->isInLoop() && !FindLastIVPhiR->isOrdered() &&
2205 "inloop and ordered reductions not supported");
2206 assert(FindLastIVPhiR->getVFScaleFactor() == 1 &&
2207 "FindIV reduction must not be scaled");
2208
2209 // TODO: support for FP in handleFirstArgMinOrMax
2210 if (RecurrenceDescriptor::isFloatingPointRecurrenceKind(
2211 Kind: MinOrMaxPhiR->getRecurrenceKind()))
2212 return false;
2213
2214 Type *Ty = Plan.getVectorLoopRegion()->getCanonicalIVType();
2215 // TODO: Support non (i.e., narrower than) canonical IV types.
2216 // TODO: Emit remarks for failed transformations.
2217 if (Ty != WideIV->getScalarType())
2218 return false;
2219
2220 VPValue *HeaderMask = Plan.getVectorLoopRegion()->getHeaderMask();
2221 auto *BackedgeVal = FindLastIVPhiR->getBackedgeValue();
2222 auto *FindIVSelectVal = BackedgeVal;
2223 if (HeaderMask && !match(V: BackedgeVal, P: m_Select(Op0: m_Specific(VPV: HeaderMask),
2224 Op1: m_VPValue(V&: FindIVSelectVal),
2225 Op2: m_Specific(VPV: FindLastIVPhiR))))
2226 return false;
2227 auto *FindIVSelectR =
2228 cast<VPSingleDefRecipe>(Val: FindIVSelectVal->getDefiningRecipe());
2229
2230 assert(
2231 match(FindIVSelectR, m_Select(m_VPValue(), m_VPValue(), m_VPValue())) &&
2232 "backedge value must be a select");
2233 if (FindIVSelectR->getOperand(N: 1) != WideIV &&
2234 FindIVSelectR->getOperand(N: 2) != WideIV)
2235 return false;
2236
2237 // If the original wide IV is not canonical, create a new one. The canonical
2238 // wide IV is guaranteed to not wrap for all lanes that are active in the
2239 // vector loop.
2240 if (!WideIV->isCanonical()) {
2241 VPIRValue *Zero = Plan.getConstantInt(Ty, Val: 0);
2242 VPIRValue *One = Plan.getConstantInt(Ty, Val: 1);
2243 auto *WidenCanIV = new VPWidenIntOrFpInductionRecipe(
2244 nullptr, Zero, One, WideIV->getVFValue(),
2245 WideIV->getInductionDescriptor(),
2246 VPIRFlags::WrapFlagsTy(/*HasNUW=*/true, /*HasNSW=*/false),
2247 WideIV->getDebugLoc());
2248 WidenCanIV->insertBefore(InsertPos: WideIV);
2249
2250 // Update the select to use the wide canonical IV.
2251 FindIVSelectR->setOperand(I: FindIVSelectR->getOperand(N: 1) == WideIV ? 1 : 2,
2252 New: WidenCanIV);
2253 }
2254 FindLastIVPhiR->setOperand(I: 0, New: Plan.getPoison(Ty));
2255
2256 // The reduction using MinOrMaxPhiR needs adjusting to compute the correct
2257 // result:
2258 // 1. Find the first canonical indices corresponding to partial min/max
2259 // values, using loop reductions.
2260 // 2. Find which of the partial min/max values are equal to the overall
2261 // min/max value.
2262 // 3. Select among the canonical indices those corresponding to the overall
2263 // min/max value.
2264 // 4. Find the first canonical index of overall min/max and scale it back to
2265 // the original IV using VPDerivedIVRecipe.
2266 // 5. If the overall min/max equals the starting min/max, the condition in
2267 // the loop was always false, due to being strict; return the start value
2268 // of FindLastIVPhiR in that case.
2269 //
2270 // For example, we transforms two independent reduction result computations
2271 // for
2272 //
2273 // <x1> vector loop: {
2274 // vector.body:
2275 // ...
2276 // ir<%iv> = WIDEN-INDUCTION nuw nsw ir<10>, ir<1>, vp<%0>
2277 // WIDEN-REDUCTION-PHI ir<%min.idx> = phi ir<sentinel.min.start>,
2278 // ir<%min.idx.next>
2279 // WIDEN-REDUCTION-PHI ir<%min.val> = phi ir<100>, ir<%min.val.next>
2280 // ....
2281 // WIDEN-INTRINSIC ir<%min.val.next> = call llvm.umin(ir<%min.val>, ir<%l>)
2282 // WIDEN ir<%min.idx.next> = select ir<%cmp>, ir<%iv>, ir<%min.idx>
2283 // ...
2284 // }
2285 // Successor(s): middle.block
2286 //
2287 // middle.block:
2288 // vp<%iv.rdx> = compute-reduction-result (smax) vp<%min.idx.next>
2289 // vp<%min.result> = compute-reduction-result (umin) ir<%min.val.next>
2290 // vp<%cmp> = icmp ne vp<%iv.rdx>, ir<sentinel.min.start>
2291 // vp<%find.iv.result> = select vp<%cmp>, vp<%iv.rdx>, ir<10>
2292 //
2293 //
2294 // Into:
2295 //
2296 // vp<%reduced.min> = compute-reduction-result (umin) ir<%min.val.next>
2297 // vp<%reduced.mins.mask> = icmp eq ir<%min.val.next>, vp<%reduced.min>
2298 // vp<%idxs2reduce> = select vp<%reduced.mins.mask>, ir<%min.idx.next>,
2299 // ir<MaxUInt>
2300 // vp<%reduced.idx> = compute-reduction-result (umin) vp<%idxs2reduce>
2301 // vp<%scaled.idx> = DERIVED-IV ir<20> + vp<%reduced.idx> * ir<1>
2302 // vp<%always.false> = icmp eq vp<%reduced.min>, ir<100>
2303 // vp<%final.idx> = select vp<%always.false>, ir<10>,
2304 // vp<%scaled.idx>
2305
2306 VPBuilder Builder(FindIVRdxResult);
2307 VPValue *MinOrMaxExiting = MinOrMaxResult->getOperand(N: 0);
2308 auto *FinalMinOrMaxCmp =
2309 Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: MinOrMaxExiting, B: MinOrMaxResult);
2310 VPValue *LastIVExiting = FindIVRdxResult->getOperand(N: 0);
2311 VPValue *MaxIV =
2312 Plan.getConstantInt(Val: APInt::getMaxValue(numBits: Ty->getIntegerBitWidth()));
2313 auto *FinalIVSelect =
2314 Builder.createSelect(Cond: FinalMinOrMaxCmp, TrueVal: LastIVExiting, FalseVal: MaxIV);
2315 VPIRFlags RdxFlags(RecurKind::UMin, false, false, FastMathFlags());
2316 VPSingleDefRecipe *FinalCanIV = Builder.createNaryOp(
2317 Opcode: VPInstruction::ComputeReductionResult, Operands: {FinalIVSelect}, Flags: RdxFlags,
2318 DL: FindIVRdxResult->getDebugLoc());
2319
2320 // If we used a new wide canonical IV convert the reduction result back to the
2321 // original IV scale before the final select.
2322 if (!WideIV->isCanonical()) {
2323 auto *DerivedIVRecipe = new VPDerivedIVRecipe(
2324 InductionDescriptor::IK_IntInduction,
2325 nullptr, // No FPBinOp for integer induction
2326 WideIV->getStartValue(), FinalCanIV, WideIV->getStepValue());
2327 DerivedIVRecipe->insertBefore(InsertPos: Builder.getRecipeAtInsertPoint());
2328 FinalCanIV = DerivedIVRecipe;
2329 }
2330
2331 // If the final min/max value matches its start value, the condition in the
2332 // loop was always false, i.e. no induction value has been selected. If that's
2333 // the case, set the result of the IV reduction to its start value.
2334 VPValue *AlwaysFalse = Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: MinOrMaxResult,
2335 B: MinOrMaxPhiR->getStartValue());
2336 VPValue *FinalIV = Builder.createSelect(
2337 Cond: AlwaysFalse, TrueVal: FindIVSelect->getOperand(N: 2), FalseVal: FinalCanIV);
2338 FindIVSelect->replaceAllUsesWith(New: FinalIV);
2339
2340 // Erase the old FindIV result pattern which is now dead.
2341 FindIVSelect->eraseFromParent();
2342 FindIVCmp->eraseFromParent();
2343 FindIVRdxResult->eraseFromParent();
2344 return true;
2345}
2346
2347bool VPlanTransforms::handleMultiUseReductions(VPlan &Plan,
2348 OptimizationRemarkEmitter *ORE,
2349 Loop *TheLoop) {
2350 for (auto &PhiR : make_early_inc_range(
2351 Range: Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis())) {
2352 auto *MinOrMaxPhiR = dyn_cast<VPReductionPHIRecipe>(Val: &PhiR);
2353 // TODO: check for multi-uses in VPlan directly.
2354 if (!MinOrMaxPhiR || !MinOrMaxPhiR->hasUsesOutsideReductionChain())
2355 continue;
2356
2357 // MinOrMaxPhiR has users outside the reduction cycle in the loop. Check if
2358 // the only other user is a FindLastIV reduction. MinOrMaxPhiR must have
2359 // exactly 2 users if not tailfolded:
2360 // 1) the min/max operation of the reduction cycle, and
2361 // 2) the compare of a FindLastIV reduction cycle. This compare must match
2362 // the min/max operation - comparing MinOrMaxPhiR with the operand of the
2363 // min/max operation, and be used only by the select of the FindLastIV
2364 // reduction cycle.
2365 // There is an additional user if the tail was folded:
2366 // 3) the select operation of the vector.latch block. This select uses the
2367 // original MinOrMaxPhiR if the mask is zero.
2368 RecurKind RdxKind = MinOrMaxPhiR->getRecurrenceKind();
2369 assert(
2370 RecurrenceDescriptor::isMinMaxRecurrenceKind(RdxKind) &&
2371 "only min/max recurrences support users outside the reduction chain");
2372
2373 auto *MinOrMaxBackedgeR =
2374 dyn_cast<VPRecipeWithIRFlags>(Val: MinOrMaxPhiR->getBackedgeValue());
2375 if (!MinOrMaxBackedgeR)
2376 return false;
2377
2378 // If the tail was folded then the backedge won't be the
2379 // reduction-intrinsic but the select in the vector.latch block that wraps
2380 // the reduction-intrinsic.
2381 auto *MinOrMaxOp = MinOrMaxBackedgeR;
2382 VPValue *HeaderMask = Plan.getVectorLoopRegion()->getHeaderMask();
2383 VPValue *MinOrMaxTailfold;
2384 if (HeaderMask) {
2385 if (!match(V: MinOrMaxBackedgeR, P: m_SelectLike(Op0: m_Specific(VPV: HeaderMask),
2386 Op1: m_VPValue(V&: MinOrMaxTailfold),
2387 Op2: m_Specific(VPV: MinOrMaxPhiR))))
2388 return false;
2389
2390 MinOrMaxOp = dyn_cast<VPRecipeWithIRFlags>(Val: MinOrMaxTailfold);
2391 if (!MinOrMaxOp)
2392 return false;
2393 }
2394
2395 // Check that MinOrMaxOp is a VPWidenIntrinsicRecipe or
2396 // VPReplicateRecipe with an intrinsic that matches the reduction kind.
2397 Intrinsic::ID ExpectedIntrinsicID = getMinMaxReductionIntrinsicOp(RK: RdxKind);
2398 if (!match(V: MinOrMaxOp, P: m_Intrinsic(IntrID: ExpectedIntrinsicID)))
2399 return false;
2400
2401 // Tailfolded MinOrMaxOp should only feed into the predicated
2402 // select MinOrMaxBackedgeR.
2403 assert((!HeaderMask || MinOrMaxOp->getNumUsers() == 1) &&
2404 "Tailfolded MinOrMaxOp must have exactly 1 user");
2405 // MinOrMaxBackedgeR must have 2 users: 1) MinOrMaxPhiR and 2)
2406 // ComputeReductionResult.
2407 assert(MinOrMaxBackedgeR->getNumUsers() == 2 &&
2408 "MinOrMaxBackedgeR must have exactly 2 users");
2409 // MinOrMaxOp must combine MinOrMaxPhiR directly with the new element;
2410 // reject multi-step min/max chains (e.g. max(l, max(k, phi))), which
2411 // this transform does not handle.
2412 VPValue *MinOrMaxOpValue;
2413 if (MinOrMaxOp->getOperand(N: 0) == MinOrMaxPhiR)
2414 MinOrMaxOpValue = MinOrMaxOp->getOperand(N: 1);
2415 else if (MinOrMaxOp->getOperand(N: 1) == MinOrMaxPhiR)
2416 MinOrMaxOpValue = MinOrMaxOp->getOperand(N: 0);
2417 else
2418 return false;
2419
2420 VPValue *CmpOpA;
2421 VPValue *CmpOpB;
2422 CmpPredicate Pred;
2423 auto *Cmp = findSingleUser<VPRecipeWithIRFlags>(
2424 V: MinOrMaxPhiR, P: m_Cmp(Pred, Op0: m_VPValue(V&: CmpOpA), Op1: m_VPValue(V&: CmpOpB)));
2425 if (!Cmp || Cmp->getNumUsers() != 1 ||
2426 (CmpOpA != MinOrMaxOpValue && CmpOpB != MinOrMaxOpValue))
2427 return false;
2428
2429 if (MinOrMaxOpValue != CmpOpB)
2430 Pred = CmpInst::getSwappedPredicate(pred: Pred);
2431
2432 // MinOrMaxPhiR must have exactly 2 users if not tailfolded:
2433 // * MinOrMaxOp,
2434 // * Cmp (that's part of a FindLastIV chain).
2435 // Also an additional third user if it is tailfolded:
2436 // * Predicated HEADER-MASK select in the vector.latch block.
2437 if (MinOrMaxPhiR->getNumUsers() != (HeaderMask ? 3 : 2))
2438 return false;
2439
2440 VPInstruction *MinOrMaxResult =
2441 findSingleUser<VPInstruction::ComputeReductionResult>(
2442 V: MinOrMaxBackedgeR);
2443 assert(MinOrMaxResult &&
2444 "MinOrMaxResult must be a user of MinOrMaxBackedgeR");
2445
2446 // Cmp must be used by the select of a FindLastIV chain.
2447 VPValue *Sel = dyn_cast<VPSingleDefRecipe>(Val: Cmp->getSingleUser());
2448 VPValue *IVOp, *FindIV;
2449 if (!Sel || (Sel->getNumUsers() != (HeaderMask ? 1 : 2)) ||
2450 !match(V: Sel,
2451 P: m_Select(Op0: m_Specific(VPV: Cmp), Op1: m_VPValue(V&: IVOp), Op2: m_VPValue(V&: FindIV))))
2452 return false;
2453
2454 if (!isa<VPReductionPHIRecipe>(Val: FindIV)) {
2455 std::swap(a&: FindIV, b&: IVOp);
2456 Pred = CmpInst::getInversePredicate(pred: Pred);
2457 }
2458
2459 auto *FindIVPhiR = dyn_cast<VPReductionPHIRecipe>(Val: FindIV);
2460 if (!FindIVPhiR || !RecurrenceDescriptor::isFindIVRecurrenceKind(
2461 Kind: FindIVPhiR->getRecurrenceKind()))
2462 return false;
2463
2464 assert(!FindIVPhiR->isInLoop() && !FindIVPhiR->isOrdered() &&
2465 "cannot handle inloop/ordered reductions yet");
2466
2467 // Check if FindIVPhiR is a FindLast pattern by checking the MinMaxKind
2468 // on its ComputeReductionResult. SMax/UMax indicates FindLast.
2469 VPInstruction *FindIVResult =
2470 findSingleUser<VPInstruction::ComputeReductionResult>(
2471 V: FindIVPhiR->getBackedgeValue());
2472 assert(FindIVResult &&
2473 "must be able to retrieve the FindIVResult VPInstruction");
2474 RecurKind FindIVMinMaxKind = FindIVResult->getRecurKind();
2475 if (FindIVMinMaxKind != RecurKind::SMax &&
2476 FindIVMinMaxKind != RecurKind::UMax)
2477 return false;
2478
2479 // TODO: Support cases where IVOp is the IV increment.
2480 if (!match(V: IVOp, P: m_TruncOrSelf(Op0: m_VPValue(V&: IVOp))) ||
2481 !isa<VPWidenIntOrFpInductionRecipe>(Val: IVOp))
2482 return false;
2483
2484 // Check if the predicate is compatible with the reduction kind.
2485 bool IsValidKindPred = [RdxKind, Pred]() {
2486 switch (RdxKind) {
2487 case RecurKind::UMin:
2488 return Pred == CmpInst::ICMP_UGE || Pred == CmpInst::ICMP_UGT;
2489 case RecurKind::UMax:
2490 return Pred == CmpInst::ICMP_ULE || Pred == CmpInst::ICMP_ULT;
2491 case RecurKind::SMax:
2492 return Pred == CmpInst::ICMP_SLE || Pred == CmpInst::ICMP_SLT;
2493 case RecurKind::SMin:
2494 return Pred == CmpInst::ICMP_SGE || Pred == CmpInst::ICMP_SGT;
2495 case RecurKind::FMax:
2496 case RecurKind::FMaximumNum:
2497 return Pred == CmpInst::FCMP_OLE || Pred == CmpInst::FCMP_OLT;
2498 case RecurKind::FMin:
2499 case RecurKind::FMinimumNum:
2500 return Pred == CmpInst::FCMP_OGE || Pred == CmpInst::FCMP_OGT;
2501 // minnum and maxnum need special handling due to expected sNaN behaviour
2502 // minimum and maximum return NaN if either input is a NAN
2503 case RecurKind::FMinNum:
2504 case RecurKind::FMaxNum:
2505 case RecurKind::FMinimum:
2506 case RecurKind::FMaximum:
2507 return false;
2508 default:
2509 llvm_unreachable("unhandled recurrence kind");
2510 }
2511 }();
2512 if (!IsValidKindPred) {
2513 ORE->emit(RemarkBuilder: [&]() {
2514 return OptimizationRemarkMissed(
2515 DEBUG_TYPE, "VectorizationMultiUseReductionPredicate",
2516 TheLoop->getStartLoc(), TheLoop->getHeader())
2517 << "Multi-use reduction with predicate "
2518 << CmpInst::getPredicateName(P: Pred)
2519 << " incompatible with reduction kind";
2520 });
2521 return false;
2522 }
2523
2524 if (RdxKind == RecurKind::FMaximumNum ||
2525 RdxKind == RecurKind::FMinimumNum) {
2526 auto *StartC = dyn_cast<VPConstant>(Val: MinOrMaxPhiR->getStartValue());
2527 if (!StartC || StartC->getConstant()->isNaN())
2528 return false;
2529 }
2530
2531 auto *FindIVSelect = findFindIVSelect(BackedgeVal: FindIVPhiR->getBackedgeValue());
2532 auto *FindIVCmp = FindIVSelect->getOperand(N: 0)->getDefiningRecipe();
2533 auto *FindIVRdxResult = cast<VPInstruction>(Val: FindIVCmp->getOperand(N: 0));
2534 assert(FindIVSelect->getParent() == MinOrMaxResult->getParent() &&
2535 "both results must be computed in the same block");
2536 // Reducing to a scalar min or max value is placed right before reducing to
2537 // its scalar iteration, in order to generate instructions that use both
2538 // their operands.
2539 MinOrMaxResult->moveBefore(I: FindIVRdxResult->getIterator());
2540
2541 bool IsStrictPredicate = CmpInst::isStrictPredicate(predicate: Pred);
2542 if (IsStrictPredicate) {
2543 if (!handleFirstArgMinOrMax(Plan, MinOrMaxPhiR, FindLastIVPhiR: FindIVPhiR,
2544 WideIV: cast<VPWidenIntOrFpInductionRecipe>(Val: IVOp),
2545 MinOrMaxResult, FindIVSelect, FindIVCmp,
2546 FindIVRdxResult))
2547 return false;
2548 continue;
2549 }
2550
2551 // The reduction using MinOrMaxPhiR needs adjusting to compute the correct
2552 // result:
2553 // 1. We need to find the last IV for which the condition based on the
2554 // min/max recurrence is true,
2555 // 2. Compare the partial min/max reduction result to its final value and,
2556 // 3. Select the lanes of the partial FindLastIV reductions which
2557 // correspond to the lanes matching the min/max reduction result.
2558 //
2559 // For example, this transforms
2560 // vp<%min.result> = compute-reduction-result ir<%min.val.next>
2561 // vp<%iv.rdx> = compute-reduction-result (smax) vp<%min.idx.next>
2562 // vp<%cmp> = icmp ne vp<%iv.rdx>, SENTINEL
2563 // vp<%find.iv.result> = select vp<%cmp>, vp<%iv.rdx>, ir<0>
2564 //
2565 // into:
2566 //
2567 // vp<min.result> = compute-reduction-result ir<%min.val.next>
2568 // vp<%final.min.cmp> = icmp eq ir<%min.val.next>, vp<min.result>
2569 // vp<%final.iv> = select vp<%final.min.cmp>, vp<%min.idx.next>, SENTINEL
2570 // vp<%iv.rdx> = compute-reduction-result (smax) vp<%final.iv>
2571 // vp<%cmp> = icmp ne vp<%iv.rdx>, SENTINEL
2572 // vp<%find.iv.result> = select vp<%cmp>, vp<%iv.rdx>, ir<0>
2573 //
2574 VPBuilder B(FindIVRdxResult);
2575 VPValue *MinOrMaxExiting = MinOrMaxResult->getOperand(N: 0);
2576 auto *FinalMinOrMaxCmp =
2577 (RecurrenceDescriptor::isIntegerRecurrenceKind(Kind: RdxKind))
2578 ? B.createICmp(Pred: CmpInst::ICMP_EQ, A: MinOrMaxExiting, B: MinOrMaxResult)
2579 : B.createFCmp(Pred: CmpInst::FCMP_OEQ, A: MinOrMaxExiting, B: MinOrMaxResult);
2580 VPValue *Sentinel = FindIVCmp->getOperand(N: 1);
2581 VPValue *LastIVExiting = FindIVRdxResult->getOperand(N: 0);
2582 auto *FinalIVSelect =
2583 B.createSelect(Cond: FinalMinOrMaxCmp, TrueVal: LastIVExiting, FalseVal: Sentinel);
2584 FindIVRdxResult->setOperand(I: 0, New: FinalIVSelect);
2585 }
2586 return true;
2587}
2588
2589void VPlanTransforms::attachAliasMaskToHeaderMask(VPlan &Plan) {
2590 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
2591 VPValue *HeaderMask = LoopRegion->getHeaderMask();
2592 Type *I1Ty = IntegerType::getInt1Ty(C&: Plan.getContext());
2593
2594 VPBuilder Builder(Plan.getVectorPreheader());
2595 auto *AliasMask = Builder.createNaryOp(
2596 Opcode: VPInstruction::IncomingAliasMask, Operands: {}, Inst: nullptr, Flags: {}, MD: {},
2597 DL: DebugLoc::getUnknown(), Name: "incoming.alias.mask", ResultTy: I1Ty);
2598
2599 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
2600 Builder = VPBuilder(Header->getFirstNonPhi());
2601
2602 // Update all existing users of the header mask to "HeaderMask & AliasMask".
2603 auto *ClampedHeaderMask = Builder.createAnd(LHS: HeaderMask, RHS: AliasMask);
2604 HeaderMask->replaceUsesWithIf(New: ClampedHeaderMask,
2605 ShouldReplace: not_equal_to(Arg&: ClampedHeaderMask));
2606}
2607