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