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/Analysis/LoopInfo.h"
24#include "llvm/Analysis/LoopIterator.h"
25#include "llvm/Analysis/OptimizationRemarkEmitter.h"
26#include "llvm/Analysis/ScalarEvolution.h"
27#include "llvm/Analysis/ScalarEvolutionExpressions.h"
28#include "llvm/Analysis/TargetTransformInfo.h"
29#include "llvm/IR/InstrTypes.h"
30#include "llvm/IR/MDBuilder.h"
31#include "llvm/Transforms/Utils/LoopUtils.h"
32#include "llvm/Transforms/Utils/LoopVersioning.h"
33
34#define DEBUG_TYPE "vplan"
35
36using namespace llvm;
37using namespace VPlanPatternMatch;
38
39namespace {
40// Class that is used to build the plain CFG for the incoming IR.
41class PlainCFGBuilder {
42 // The outermost loop of the input loop nest considered for vectorization.
43 Loop *TheLoop;
44
45 // Loop Info analysis.
46 LoopInfo *LI;
47
48 // Loop versioning for alias metadata.
49 LoopVersioning *LVer;
50
51 // Vectorization plan that we are working on.
52 std::unique_ptr<VPlan> Plan;
53
54 // Builder of the VPlan instruction-level representation.
55 VPBuilder VPIRBuilder;
56
57 // NOTE: The following maps are intentionally destroyed after the plain CFG
58 // construction because subsequent VPlan-to-VPlan transformation may
59 // invalidate them.
60 // Map incoming BasicBlocks to their newly-created VPBasicBlocks.
61 DenseMap<BasicBlock *, VPBasicBlock *> BB2VPBB;
62 // Map incoming Value definitions to their newly-created VPValues.
63 DenseMap<Value *, VPValue *> IRDef2VPValue;
64
65 // Hold phi node's that need to be fixed once the plain CFG has been built.
66 SmallVector<PHINode *, 8> PhisToFix;
67
68 // Utility functions.
69 void setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB);
70 void fixHeaderPhis();
71 VPBasicBlock *getOrCreateVPBB(BasicBlock *BB);
72#ifndef NDEBUG
73 bool isExternalDef(Value *Val);
74#endif
75 VPValue *getOrCreateVPOperand(Value *IRVal);
76 void createVPInstructionsForVPBB(VPBasicBlock *VPBB, BasicBlock *BB);
77
78public:
79 PlainCFGBuilder(Loop *Lp, LoopInfo *LI, LoopVersioning *LVer)
80 : TheLoop(Lp), LI(LI), LVer(LVer), Plan(std::make_unique<VPlan>(args&: Lp)) {}
81
82 /// Build plain CFG for TheLoop and connect it to Plan's entry.
83 std::unique_ptr<VPlan> buildPlainCFG();
84};
85} // anonymous namespace
86
87// Set predecessors of \p VPBB in the same order as they are in \p BB. \p VPBB
88// must have no predecessors.
89void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) {
90 // Collect VPBB predecessors.
91 SmallVector<VPBlockBase *, 2> VPBBPreds;
92 for (BasicBlock *Pred : predecessors(BB))
93 VPBBPreds.push_back(Elt: getOrCreateVPBB(BB: Pred));
94 VPBB->setPredecessors(VPBBPreds);
95}
96
97static bool isHeaderBB(BasicBlock *BB, Loop *L) {
98 return L && BB == L->getHeader();
99}
100
101// Add operands to VPInstructions representing phi nodes from the input IR.
102void PlainCFGBuilder::fixHeaderPhis() {
103 for (auto *Phi : PhisToFix) {
104 assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
105 VPValue *VPVal = IRDef2VPValue[Phi];
106 assert(isa<VPPhi>(VPVal) && "Expected VPPhi for phi node.");
107 auto *PhiR = cast<VPPhi>(Val: VPVal);
108 assert(PhiR->getNumOperands() == 0 && "Expected VPPhi with no operands.");
109 assert(isHeaderBB(Phi->getParent(), LI->getLoopFor(Phi->getParent())) &&
110 "Expected Phi in header block.");
111 assert(Phi->getNumOperands() == 2 &&
112 "header phi must have exactly 2 operands");
113 for (BasicBlock *Pred : predecessors(BB: Phi->getParent()))
114 PhiR->addOperand(
115 Operand: getOrCreateVPOperand(IRVal: Phi->getIncomingValueForBlock(BB: Pred)));
116 }
117}
118
119// Create a new empty VPBasicBlock for an incoming BasicBlock or retrieve an
120// existing one if it was already created.
121VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {
122 if (auto *VPBB = BB2VPBB.lookup(Val: BB)) {
123 // Retrieve existing VPBB.
124 return VPBB;
125 }
126
127 // Create new VPBB.
128 StringRef Name = BB->getName();
129 LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << Name << "\n");
130 VPBasicBlock *VPBB = Plan->createVPBasicBlock(Name);
131 BB2VPBB[BB] = VPBB;
132 return VPBB;
133}
134
135#ifndef NDEBUG
136// Return true if \p Val is considered an external definition. An external
137// definition is either:
138// 1. A Value that is not an Instruction. This will be refined in the future.
139// 2. An Instruction that is outside of the IR region represented in VPlan,
140// i.e., is not part of the loop nest.
141bool PlainCFGBuilder::isExternalDef(Value *Val) {
142 // All the Values that are not Instructions are considered external
143 // definitions for now.
144 Instruction *Inst = dyn_cast<Instruction>(Val);
145 if (!Inst)
146 return true;
147
148 // Check whether Instruction definition is in loop body.
149 return !TheLoop->contains(Inst);
150}
151#endif
152
153// Create a new VPValue or retrieve an existing one for the Instruction's
154// operand \p IRVal. This function must only be used to create/retrieve VPValues
155// for *Instruction's operands* and not to create regular VPInstruction's. For
156// the latter, please, look at 'createVPInstructionsForVPBB'.
157VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
158 auto VPValIt = IRDef2VPValue.find(Val: IRVal);
159 if (VPValIt != IRDef2VPValue.end())
160 // Operand has an associated VPInstruction or VPValue that was previously
161 // created.
162 return VPValIt->second;
163
164 // Operand doesn't have a previously created VPInstruction/VPValue. This
165 // means that operand is:
166 // A) a definition external to VPlan,
167 // B) any other Value without specific representation in VPlan.
168 // For now, we use VPValue to represent A and B and classify both as external
169 // definitions. We may introduce specific VPValue subclasses for them in the
170 // future.
171 assert(isExternalDef(IRVal) && "Expected external definition as operand.");
172
173 // A and B: Create VPValue and add it to the pool of external definitions and
174 // to the Value->VPValue map.
175 VPValue *NewVPVal = Plan->getOrAddLiveIn(V: IRVal);
176 IRDef2VPValue[IRVal] = NewVPVal;
177 return NewVPVal;
178}
179
180// Create new VPInstructions in a VPBasicBlock, given its BasicBlock
181// counterpart. This function must be invoked in RPO so that the operands of a
182// VPInstruction in \p BB have been visited before (except for Phi nodes).
183void PlainCFGBuilder::createVPInstructionsForVPBB(VPBasicBlock *VPBB,
184 BasicBlock *BB) {
185 VPIRBuilder.setInsertPoint(VPBB);
186 // TODO: Model and preserve debug intrinsics in VPlan.
187 for (Instruction &InstRef : BB->instructionsWithoutDebug(SkipPseudoOp: false)) {
188 Instruction *Inst = &InstRef;
189
190 // There shouldn't be any VPValue for Inst at this point. Otherwise, we
191 // visited Inst when we shouldn't, breaking the RPO traversal order.
192 assert(!IRDef2VPValue.count(Inst) &&
193 "Instruction shouldn't have been visited.");
194
195 if (auto *Br = dyn_cast<BranchInst>(Val: Inst)) {
196 // Conditional branch instruction are represented using BranchOnCond
197 // recipes.
198 if (Br->isConditional()) {
199 VPValue *Cond = getOrCreateVPOperand(IRVal: Br->getCondition());
200 VPIRBuilder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cond}, Inst, Flags: {},
201 MD: VPIRMetadata(*Inst), DL: Inst->getDebugLoc());
202 }
203
204 // Skip the rest of the Instruction processing for Branch instructions.
205 continue;
206 }
207
208 if (auto *SI = dyn_cast<SwitchInst>(Val: Inst)) {
209 // Don't emit recipes for unconditional switch instructions.
210 if (SI->getNumCases() == 0)
211 continue;
212 SmallVector<VPValue *> Ops = {getOrCreateVPOperand(IRVal: SI->getCondition())};
213 for (auto Case : SI->cases())
214 Ops.push_back(Elt: getOrCreateVPOperand(IRVal: Case.getCaseValue()));
215 VPIRBuilder.createNaryOp(Opcode: Instruction::Switch, Operands: Ops, Inst, Flags: {},
216 MD: VPIRMetadata(*Inst), DL: Inst->getDebugLoc());
217 continue;
218 }
219
220 VPSingleDefRecipe *NewR;
221 if (auto *Phi = dyn_cast<PHINode>(Val: Inst)) {
222 // Phi node's operands may not have been visited at this point. We create
223 // an empty VPInstruction that we will fix once the whole plain CFG has
224 // been built.
225 NewR =
226 VPIRBuilder.createScalarPhi(IncomingValues: {}, DL: Phi->getDebugLoc(), Name: "vec.phi", Flags: *Phi);
227 NewR->setUnderlyingValue(Phi);
228 if (isHeaderBB(BB: Phi->getParent(), L: LI->getLoopFor(BB: Phi->getParent()))) {
229 // Header phis need to be fixed after the VPBB for the latch has been
230 // created.
231 PhisToFix.push_back(Elt: Phi);
232 } else {
233 // Add operands for VPPhi in the order matching its predecessors in
234 // VPlan.
235 DenseMap<const VPBasicBlock *, VPValue *> VPPredToIncomingValue;
236 for (unsigned I = 0; I != Phi->getNumOperands(); ++I) {
237 VPPredToIncomingValue[BB2VPBB[Phi->getIncomingBlock(i: I)]] =
238 getOrCreateVPOperand(IRVal: Phi->getIncomingValue(i: I));
239 }
240 for (VPBlockBase *Pred : VPBB->getPredecessors())
241 NewR->addOperand(
242 Operand: VPPredToIncomingValue.lookup(Val: Pred->getExitingBasicBlock()));
243 }
244 } else {
245 // Build VPIRMetadata from the instruction and add loop versioning
246 // metadata for loads and stores.
247 VPIRMetadata MD(*Inst);
248 if (isa<LoadInst, StoreInst>(Val: Inst) && LVer) {
249 const auto &[AliasScopeMD, NoAliasMD] =
250 LVer->getNoAliasMetadataFor(OrigInst: Inst);
251 if (AliasScopeMD)
252 MD.setMetadata(Kind: LLVMContext::MD_alias_scope, Node: AliasScopeMD);
253 if (NoAliasMD)
254 MD.setMetadata(Kind: LLVMContext::MD_noalias, Node: NoAliasMD);
255 }
256
257 // Translate LLVM-IR operands into VPValue operands and set them in the
258 // new VPInstruction.
259 SmallVector<VPValue *, 4> VPOperands;
260 for (Value *Op : Inst->operands())
261 VPOperands.push_back(Elt: getOrCreateVPOperand(IRVal: Op));
262
263 if (auto *CI = dyn_cast<CastInst>(Val: Inst)) {
264 NewR = VPIRBuilder.createScalarCast(Opcode: CI->getOpcode(), Op: VPOperands[0],
265 ResultTy: CI->getType(), DL: CI->getDebugLoc(),
266 Flags: VPIRFlags(*CI), Metadata: MD);
267 NewR->setUnderlyingValue(CI);
268 } else {
269 // Build VPInstruction for any arbitrary Instruction without specific
270 // representation in VPlan.
271 NewR =
272 VPIRBuilder.createNaryOp(Opcode: Inst->getOpcode(), Operands: VPOperands, Inst,
273 Flags: VPIRFlags(*Inst), MD, DL: Inst->getDebugLoc());
274 }
275 }
276
277 IRDef2VPValue[Inst] = NewR;
278 }
279}
280
281// Main interface to build the plain CFG.
282std::unique_ptr<VPlan> PlainCFGBuilder::buildPlainCFG() {
283 VPIRBasicBlock *Entry = cast<VPIRBasicBlock>(Val: Plan->getEntry());
284 BB2VPBB[Entry->getIRBasicBlock()] = Entry;
285 for (VPIRBasicBlock *ExitVPBB : Plan->getExitBlocks())
286 BB2VPBB[ExitVPBB->getIRBasicBlock()] = ExitVPBB;
287
288 // 1. Scan the body of the loop in a topological order to visit each basic
289 // block after having visited its predecessor basic blocks. Create a VPBB for
290 // each BB and link it to its successor and predecessor VPBBs. Note that
291 // predecessors must be set in the same order as they are in the incomming IR.
292 // Otherwise, there might be problems with existing phi nodes and algorithm
293 // based on predecessors traversal.
294
295 // Loop PH needs to be explicitly visited since it's not taken into account by
296 // LoopBlocksDFS.
297 BasicBlock *ThePreheaderBB = TheLoop->getLoopPreheader();
298 assert((ThePreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
299 "Unexpected loop preheader");
300 for (auto &I : *ThePreheaderBB) {
301 if (I.getType()->isVoidTy())
302 continue;
303 IRDef2VPValue[&I] = Plan->getOrAddLiveIn(V: &I);
304 }
305
306 LoopBlocksRPO RPO(TheLoop);
307 RPO.perform(LI);
308
309 for (BasicBlock *BB : RPO) {
310 // Create or retrieve the VPBasicBlock for this BB.
311 VPBasicBlock *VPBB = getOrCreateVPBB(BB);
312 // Set VPBB predecessors in the same order as they are in the incoming BB.
313 setVPBBPredsFromBB(VPBB, BB);
314
315 // Create VPInstructions for BB.
316 createVPInstructionsForVPBB(VPBB, BB);
317
318 // Set VPBB successors. We create empty VPBBs for successors if they don't
319 // exist already. Recipes will be created when the successor is visited
320 // during the RPO traversal.
321 if (auto *SI = dyn_cast<SwitchInst>(Val: BB->getTerminator())) {
322 SmallVector<VPBlockBase *> Succs = {
323 getOrCreateVPBB(BB: SI->getDefaultDest())};
324 for (auto Case : SI->cases())
325 Succs.push_back(Elt: getOrCreateVPBB(BB: Case.getCaseSuccessor()));
326 VPBB->setSuccessors(Succs);
327 continue;
328 }
329 auto *BI = cast<BranchInst>(Val: BB->getTerminator());
330 unsigned NumSuccs = succ_size(BB);
331 if (NumSuccs == 1) {
332 VPBB->setOneSuccessor(getOrCreateVPBB(BB: BB->getSingleSuccessor()));
333 continue;
334 }
335 assert(BI->isConditional() && NumSuccs == 2 && BI->isConditional() &&
336 "block must have conditional branch with 2 successors");
337
338 BasicBlock *IRSucc0 = BI->getSuccessor(i: 0);
339 BasicBlock *IRSucc1 = BI->getSuccessor(i: 1);
340 VPBasicBlock *Successor0 = getOrCreateVPBB(BB: IRSucc0);
341 VPBasicBlock *Successor1 = getOrCreateVPBB(BB: IRSucc1);
342 VPBB->setTwoSuccessors(IfTrue: Successor0, IfFalse: Successor1);
343 }
344
345 for (auto *EB : Plan->getExitBlocks())
346 setVPBBPredsFromBB(VPBB: EB, BB: EB->getIRBasicBlock());
347
348 // 2. The whole CFG has been built at this point so all the input Values must
349 // have a VPlan counterpart. Fix VPlan header phi by adding their
350 // corresponding VPlan operands.
351 fixHeaderPhis();
352
353 Plan->getEntry()->setOneSuccessor(getOrCreateVPBB(BB: TheLoop->getHeader()));
354 Plan->getEntry()->setPlan(&*Plan);
355
356 // Fix VPlan loop-closed-ssa exit phi's by adding incoming operands to the
357 // VPIRInstructions wrapping them.
358 // // Note that the operand order corresponds to IR predecessor order, and may
359 // need adjusting when VPlan predecessors are added, if an exit block has
360 // multiple predecessor.
361 for (auto *EB : Plan->getExitBlocks()) {
362 for (VPRecipeBase &R : EB->phis()) {
363 auto *PhiR = cast<VPIRPhi>(Val: &R);
364 PHINode &Phi = PhiR->getIRPhi();
365 assert(PhiR->getNumOperands() == 0 &&
366 "no phi operands should be added yet");
367 for (BasicBlock *Pred : predecessors(BB: EB->getIRBasicBlock()))
368 PhiR->addOperand(
369 Operand: getOrCreateVPOperand(IRVal: Phi.getIncomingValueForBlock(BB: Pred)));
370 }
371 }
372
373 LLVM_DEBUG(Plan->setName("Plain CFG\n"); dbgs() << *Plan);
374 return std::move(Plan);
375}
376
377/// Checks if \p HeaderVPB is a loop header block in the plain CFG; that is, it
378/// has exactly 2 predecessors (preheader and latch), where the block
379/// dominates the latch and the preheader dominates the block. If it is a
380/// header block return true and canonicalize the predecessors of the header
381/// (making sure the preheader appears first and the latch second) and the
382/// successors of the latch (making sure the loop exit comes first). Otherwise
383/// return false.
384static bool canonicalHeaderAndLatch(VPBlockBase *HeaderVPB,
385 const VPDominatorTree &VPDT) {
386 ArrayRef<VPBlockBase *> Preds = HeaderVPB->getPredecessors();
387 if (Preds.size() != 2)
388 return false;
389
390 auto *PreheaderVPBB = Preds[0];
391 auto *LatchVPBB = Preds[1];
392 if (!VPDT.dominates(A: PreheaderVPBB, B: HeaderVPB) ||
393 !VPDT.dominates(A: HeaderVPB, B: LatchVPBB)) {
394 std::swap(a&: PreheaderVPBB, b&: LatchVPBB);
395
396 if (!VPDT.dominates(A: PreheaderVPBB, B: HeaderVPB) ||
397 !VPDT.dominates(A: HeaderVPB, B: LatchVPBB))
398 return false;
399
400 // Canonicalize predecessors of header so that preheader is first and
401 // latch second.
402 HeaderVPB->swapPredecessors();
403 for (VPRecipeBase &R : cast<VPBasicBlock>(Val: HeaderVPB)->phis())
404 R.swapOperands();
405 }
406
407 // The two successors of conditional branch match the condition, with the
408 // first successor corresponding to true and the second to false. We
409 // canonicalize the successors of the latch when introducing the region, such
410 // that the latch exits the region when its condition is true; invert the
411 // original condition if the original CFG branches to the header on true.
412 // Note that the exit edge is not yet connected for top-level loops.
413 if (LatchVPBB->getSingleSuccessor() ||
414 LatchVPBB->getSuccessors()[0] != HeaderVPB)
415 return true;
416
417 assert(LatchVPBB->getNumSuccessors() == 2 && "Must have 2 successors");
418 auto *Term = cast<VPBasicBlock>(Val: LatchVPBB)->getTerminator();
419 assert(cast<VPInstruction>(Term)->getOpcode() ==
420 VPInstruction::BranchOnCond &&
421 "terminator must be a BranchOnCond");
422 auto *Not = new VPInstruction(VPInstruction::Not, {Term->getOperand(N: 0)});
423 Not->insertBefore(InsertPos: Term);
424 Term->setOperand(I: 0, New: Not);
425 LatchVPBB->swapSuccessors();
426
427 return true;
428}
429
430/// Create a new VPRegionBlock for the loop starting at \p HeaderVPB.
431static void createLoopRegion(VPlan &Plan, VPBlockBase *HeaderVPB) {
432 auto *PreheaderVPBB = HeaderVPB->getPredecessors()[0];
433 auto *LatchVPBB = HeaderVPB->getPredecessors()[1];
434
435 VPBlockUtils::disconnectBlocks(From: PreheaderVPBB, To: HeaderVPB);
436 VPBlockUtils::disconnectBlocks(From: LatchVPBB, To: HeaderVPB);
437
438 // Create an empty region first and insert it between PreheaderVPBB and
439 // the exit blocks, taking care to preserve the original predecessor &
440 // successor order of blocks. Set region entry and exiting after both
441 // HeaderVPB and LatchVPBB have been disconnected from their
442 // predecessors/successors.
443 auto *R = Plan.createLoopRegion();
444
445 // Transfer latch's successors to the region.
446 VPBlockUtils::transferSuccessors(Old: LatchVPBB, New: R);
447
448 VPBlockUtils::connectBlocks(From: PreheaderVPBB, To: R);
449 R->setEntry(HeaderVPB);
450 R->setExiting(LatchVPBB);
451
452 // All VPBB's reachable shallowly from HeaderVPB belong to the current region.
453 for (VPBlockBase *VPBB : vp_depth_first_shallow(G: HeaderVPB))
454 VPBB->setParent(R);
455}
456
457// Add the necessary canonical IV and branch recipes required to control the
458// loop.
459static void addCanonicalIVRecipes(VPlan &Plan, VPBasicBlock *HeaderVPBB,
460 VPBasicBlock *LatchVPBB, Type *IdxTy,
461 DebugLoc DL) {
462 auto *StartV = Plan.getConstantInt(Ty: IdxTy, Val: 0);
463
464 // Add a VPCanonicalIVPHIRecipe starting at 0 to the header.
465 auto *CanonicalIVPHI = new VPCanonicalIVPHIRecipe(StartV, DL);
466 HeaderVPBB->insert(Recipe: CanonicalIVPHI, InsertPt: HeaderVPBB->begin());
467
468 // We are about to replace the branch to exit the region. Remove the original
469 // BranchOnCond, if there is any.
470 DebugLoc LatchDL = DL;
471 if (!LatchVPBB->empty() && match(V: &LatchVPBB->back(), P: m_BranchOnCond())) {
472 LatchDL = LatchVPBB->getTerminator()->getDebugLoc();
473 LatchVPBB->getTerminator()->eraseFromParent();
474 }
475
476 VPBuilder Builder(LatchVPBB);
477 // Add a VPInstruction to increment the scalar canonical IV by VF * UF.
478 // Initially the induction increment is guaranteed to not wrap, but that may
479 // change later, e.g. when tail-folding, when the flags need to be dropped.
480 auto *CanonicalIVIncrement = Builder.createAdd(
481 LHS: CanonicalIVPHI, RHS: &Plan.getVFxUF(), DL, Name: "index.next", WrapFlags: {true, false});
482 CanonicalIVPHI->addOperand(Operand: CanonicalIVIncrement);
483
484 // Add the BranchOnCount VPInstruction to the latch.
485 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCount,
486 Operands: {CanonicalIVIncrement, &Plan.getVectorTripCount()},
487 DL: LatchDL);
488}
489
490/// Creates extracts for values in \p Plan defined in a loop region and used
491/// outside a loop region.
492static void createExtractsForLiveOuts(VPlan &Plan, VPBasicBlock *MiddleVPBB) {
493 VPBuilder B(MiddleVPBB, MiddleVPBB->getFirstNonPhi());
494 for (VPBasicBlock *EB : Plan.getExitBlocks()) {
495 if (!is_contained(Range: EB->predecessors(), Element: MiddleVPBB))
496 continue;
497
498 for (VPRecipeBase &R : EB->phis()) {
499 auto *ExitIRI = cast<VPIRPhi>(Val: &R);
500 VPValue *Exiting = ExitIRI->getIncomingValueForBlock(VPBB: MiddleVPBB);
501 if (isa<VPIRValue>(Val: Exiting))
502 continue;
503 Exiting = B.createNaryOp(Opcode: VPInstruction::ExtractLastPart, Operands: Exiting);
504 Exiting = B.createNaryOp(Opcode: VPInstruction::ExtractLastLane, Operands: Exiting);
505 ExitIRI->setIncomingValueForBlock(VPBB: MiddleVPBB, V: Exiting);
506 }
507 }
508}
509
510static void addInitialSkeleton(VPlan &Plan, Type *InductionTy, DebugLoc IVDL,
511 PredicatedScalarEvolution &PSE, Loop *TheLoop) {
512 VPDominatorTree VPDT(Plan);
513
514 auto *HeaderVPBB = cast<VPBasicBlock>(Val: Plan.getEntry()->getSingleSuccessor());
515 canonicalHeaderAndLatch(HeaderVPB: HeaderVPBB, VPDT);
516 auto *LatchVPBB = cast<VPBasicBlock>(Val: HeaderVPBB->getPredecessors()[1]);
517
518 VPBasicBlock *VecPreheader = Plan.createVPBasicBlock(Name: "vector.ph");
519 VPBlockUtils::insertBlockAfter(NewBlock: VecPreheader, BlockPtr: Plan.getEntry());
520
521 VPBasicBlock *MiddleVPBB = Plan.createVPBasicBlock(Name: "middle.block");
522 // The canonical LatchVPBB has the header block as last successor. If it has
523 // another successor, this successor is an exit block - insert middle block on
524 // its edge. Otherwise, add middle block as another successor retaining header
525 // as last.
526 if (LatchVPBB->getNumSuccessors() == 2) {
527 VPBlockBase *LatchExitVPB = LatchVPBB->getSuccessors()[0];
528 VPBlockUtils::insertOnEdge(From: LatchVPBB, To: LatchExitVPB, BlockPtr: MiddleVPBB);
529 } else {
530 VPBlockUtils::connectBlocks(From: LatchVPBB, To: MiddleVPBB);
531 LatchVPBB->swapSuccessors();
532 }
533
534 addCanonicalIVRecipes(Plan, HeaderVPBB, LatchVPBB, IdxTy: InductionTy, DL: IVDL);
535
536 // Create SCEV and VPValue for the trip count.
537 // We use the symbolic max backedge-taken-count, which works also when
538 // vectorizing loops with uncountable early exits.
539 const SCEV *BackedgeTakenCountSCEV = PSE.getSymbolicMaxBackedgeTakenCount();
540 assert(!isa<SCEVCouldNotCompute>(BackedgeTakenCountSCEV) &&
541 "Invalid backedge-taken count");
542 ScalarEvolution &SE = *PSE.getSE();
543 const SCEV *TripCount = SE.getTripCountFromExitCount(ExitCount: BackedgeTakenCountSCEV,
544 EvalTy: InductionTy, L: TheLoop);
545 Plan.setTripCount(vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: TripCount));
546
547 VPBasicBlock *ScalarPH = Plan.createVPBasicBlock(Name: "scalar.ph");
548 VPBlockUtils::connectBlocks(From: ScalarPH, To: Plan.getScalarHeader());
549
550 // The connection order corresponds to the operands of the conditional branch,
551 // with the middle block already connected to the exit block.
552 VPBlockUtils::connectBlocks(From: MiddleVPBB, To: ScalarPH);
553 // Also connect the entry block to the scalar preheader.
554 // TODO: Also introduce a branch recipe together with the minimum trip count
555 // check.
556 VPBlockUtils::connectBlocks(From: Plan.getEntry(), To: ScalarPH);
557 Plan.getEntry()->swapSuccessors();
558
559 createExtractsForLiveOuts(Plan, MiddleVPBB);
560
561 VPBuilder ScalarPHBuilder(ScalarPH);
562 for (const auto &[PhiR, ScalarPhiR] : zip_equal(
563 t: drop_begin(RangeOrContainer: HeaderVPBB->phis()), u: Plan.getScalarHeader()->phis())) {
564 auto *VectorPhiR = cast<VPPhi>(Val: &PhiR);
565 auto *ResumePhiR = ScalarPHBuilder.createScalarPhi(
566 IncomingValues: {VectorPhiR, VectorPhiR->getOperand(N: 0)}, DL: VectorPhiR->getDebugLoc());
567 cast<VPIRPhi>(Val: &ScalarPhiR)->addOperand(Operand: ResumePhiR);
568 }
569}
570
571/// Check \p Plan's live-in and replace them with constants, if they can be
572/// simplified via SCEV.
573static void simplifyLiveInsWithSCEV(VPlan &Plan,
574 PredicatedScalarEvolution &PSE) {
575 auto GetSimplifiedLiveInViaSCEV = [&](VPValue *VPV) -> VPValue * {
576 const SCEV *Expr = vputils::getSCEVExprForVPValue(V: VPV, PSE);
577 if (auto *C = dyn_cast<SCEVConstant>(Val: Expr))
578 return Plan.getOrAddLiveIn(V: C->getValue());
579 return nullptr;
580 };
581
582 for (VPValue *LiveIn : to_vector(Range: Plan.getLiveIns())) {
583 if (VPValue *SimplifiedLiveIn = GetSimplifiedLiveInViaSCEV(LiveIn))
584 LiveIn->replaceAllUsesWith(New: SimplifiedLiveIn);
585 }
586}
587
588/// To make RUN_VPLAN_PASS print initial VPlan.
589static void printAfterInitialConstruction(VPlan &) {}
590
591std::unique_ptr<VPlan>
592VPlanTransforms::buildVPlan0(Loop *TheLoop, LoopInfo &LI, Type *InductionTy,
593 DebugLoc IVDL, PredicatedScalarEvolution &PSE,
594 LoopVersioning *LVer) {
595 PlainCFGBuilder Builder(TheLoop, &LI, LVer);
596 std::unique_ptr<VPlan> VPlan0 = Builder.buildPlainCFG();
597 addInitialSkeleton(Plan&: *VPlan0, InductionTy, IVDL, PSE, TheLoop);
598 simplifyLiveInsWithSCEV(Plan&: *VPlan0, PSE);
599
600 RUN_VPLAN_PASS_NO_VERIFY(printAfterInitialConstruction, *VPlan0);
601 return VPlan0;
602}
603
604/// Creates a VPWidenIntOrFpInductionRecipe or VPWidenPointerInductionRecipe
605/// for \p Phi based on \p IndDesc.
606static VPHeaderPHIRecipe *
607createWidenInductionRecipe(PHINode *Phi, VPPhi *PhiR, VPIRValue *Start,
608 const InductionDescriptor &IndDesc, VPlan &Plan,
609 PredicatedScalarEvolution &PSE, Loop &OrigLoop,
610 DebugLoc DL) {
611 [[maybe_unused]] ScalarEvolution &SE = *PSE.getSE();
612 assert(SE.isLoopInvariant(IndDesc.getStep(), &OrigLoop) &&
613 "step must be loop invariant");
614 assert((Plan.getLiveIn(IndDesc.getStartValue()) == Start ||
615 (SE.isSCEVable(IndDesc.getStartValue()->getType()) &&
616 SE.getSCEV(IndDesc.getStartValue()) ==
617 vputils::getSCEVExprForVPValue(Start, PSE))) &&
618 "Start VPValue must match IndDesc's start value");
619
620 VPValue *Step =
621 vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: IndDesc.getStep());
622
623 VPValue *BackedgeVal = PhiR->getOperand(N: 1);
624 // Replace live-out extracts of WideIV's backedge value by ExitingIVValue
625 // recipes. optimizeInductionExitUsers will later compute the proper
626 // DerivedIV.
627 auto ReplaceExtractsWithExitingIVValue = [&](VPHeaderPHIRecipe *WideIV) {
628 for (VPUser *U : to_vector(Range: BackedgeVal->users())) {
629 if (!match(U, P: m_ExtractLastPart(Op0: m_VPValue())))
630 continue;
631 auto *ExtractLastPart = cast<VPInstruction>(Val: U);
632 VPUser *ExtractLastPartUser = ExtractLastPart->getSingleUser();
633 assert(ExtractLastPartUser && "must have a single user");
634 if (!match(U: ExtractLastPartUser, P: m_ExtractLastLane(Op0: m_VPValue())))
635 continue;
636 auto *ExtractLastLane = cast<VPInstruction>(Val: ExtractLastPartUser);
637 assert(is_contained(ExtractLastLane->getParent()->successors(),
638 Plan.getScalarPreheader()) &&
639 "last lane must be extracted in the middle block");
640 VPBuilder Builder(ExtractLastLane);
641 ExtractLastLane->replaceAllUsesWith(New: Builder.createNaryOp(
642 Opcode: VPInstruction::ExitingIVValue, Operands: {WideIV, BackedgeVal}));
643 ExtractLastLane->eraseFromParent();
644 ExtractLastPart->eraseFromParent();
645 }
646 };
647
648 if (IndDesc.getKind() == InductionDescriptor::IK_PtrInduction) {
649 auto *WideIV = new VPWidenPointerInductionRecipe(
650 Phi, Start, Step, &Plan.getVFxUF(), IndDesc, DL);
651 ReplaceExtractsWithExitingIVValue(WideIV);
652 return WideIV;
653 }
654
655 assert((IndDesc.getKind() == InductionDescriptor::IK_IntInduction ||
656 IndDesc.getKind() == InductionDescriptor::IK_FpInduction) &&
657 "must have an integer or float induction at this point");
658
659 // Update wide induction increments to use the same step as the corresponding
660 // wide induction. This enables detecting induction increments directly in
661 // VPlan and removes redundant splats.
662 if (match(V: BackedgeVal, P: m_Add(Op0: m_Specific(VPV: PhiR), Op1: m_VPValue())))
663 BackedgeVal->getDefiningRecipe()->setOperand(I: 1, New: Step);
664
665 // It is always safe to copy over the NoWrap and FastMath flags. In
666 // particular, when folding tail by masking, the masked-off lanes are never
667 // used, so it is safe.
668 VPIRFlags Flags = vputils::getFlagsFromIndDesc(ID: IndDesc);
669
670 auto *WideIV = new VPWidenIntOrFpInductionRecipe(
671 Phi, Start, Step, &Plan.getVF(), IndDesc, Flags, DL);
672
673 ReplaceExtractsWithExitingIVValue(WideIV);
674 return WideIV;
675}
676
677void VPlanTransforms::createHeaderPhiRecipes(
678 VPlan &Plan, PredicatedScalarEvolution &PSE, Loop &OrigLoop,
679 const MapVector<PHINode *, InductionDescriptor> &Inductions,
680 const MapVector<PHINode *, RecurrenceDescriptor> &Reductions,
681 const SmallPtrSetImpl<const PHINode *> &FixedOrderRecurrences,
682 const SmallPtrSetImpl<PHINode *> &InLoopReductions, bool AllowReordering) {
683 // Retrieve the header manually from the intial plain-CFG VPlan.
684 VPBasicBlock *HeaderVPBB = cast<VPBasicBlock>(
685 Val: Plan.getEntry()->getSuccessors()[1]->getSingleSuccessor());
686 assert(VPDominatorTree(Plan).dominates(HeaderVPBB,
687 HeaderVPBB->getPredecessors()[1]) &&
688 "header must dominate its latch");
689
690 auto CreateHeaderPhiRecipe = [&](VPPhi *PhiR) -> VPHeaderPHIRecipe * {
691 // TODO: Gradually replace uses of underlying instruction by analyses on
692 // VPlan.
693 auto *Phi = cast<PHINode>(Val: PhiR->getUnderlyingInstr());
694 assert(PhiR->getNumOperands() == 2 &&
695 "Must have 2 operands for header phis");
696
697 // Extract common values once.
698 VPIRValue *Start = cast<VPIRValue>(Val: PhiR->getOperand(N: 0));
699 VPValue *BackedgeValue = PhiR->getOperand(N: 1);
700
701 if (FixedOrderRecurrences.contains(Ptr: Phi)) {
702 // TODO: Currently fixed-order recurrences are modeled as chains of
703 // first-order recurrences. If there are no users of the intermediate
704 // recurrences in the chain, the fixed order recurrence should be
705 // modeled directly, enabling more efficient codegen.
706 return new VPFirstOrderRecurrencePHIRecipe(Phi, *Start, *BackedgeValue);
707 }
708
709 auto InductionIt = Inductions.find(Key: Phi);
710 if (InductionIt != Inductions.end())
711 return createWidenInductionRecipe(Phi, PhiR, Start, IndDesc: InductionIt->second,
712 Plan, PSE, OrigLoop,
713 DL: PhiR->getDebugLoc());
714
715 assert(Reductions.contains(Phi) && "only reductions are expected now");
716 const RecurrenceDescriptor &RdxDesc = Reductions.lookup(Key: Phi);
717 assert(RdxDesc.getRecurrenceStartValue() ==
718 Phi->getIncomingValueForBlock(OrigLoop.getLoopPreheader()) &&
719 "incoming value must match start value");
720 // Will be updated later to >1 if reduction is partial.
721 unsigned ScaleFactor = 1;
722 bool UseOrderedReductions = !AllowReordering && RdxDesc.isOrdered();
723 return new VPReductionPHIRecipe(
724 Phi, RdxDesc.getRecurrenceKind(), *Start, *BackedgeValue,
725 getReductionStyle(InLoop: InLoopReductions.contains(Ptr: Phi), Ordered: UseOrderedReductions,
726 ScaleFactor),
727 Phi->getType()->isFloatingPointTy() ? RdxDesc.getFastMathFlags()
728 : VPIRFlags(),
729 RdxDesc.hasUsesOutsideReductionChain());
730 };
731
732 for (VPRecipeBase &R : make_early_inc_range(Range: HeaderVPBB->phis())) {
733 if (isa<VPCanonicalIVPHIRecipe>(Val: &R))
734 continue;
735 auto *PhiR = cast<VPPhi>(Val: &R);
736 VPHeaderPHIRecipe *HeaderPhiR = CreateHeaderPhiRecipe(PhiR);
737 HeaderPhiR->insertBefore(InsertPos: PhiR);
738 PhiR->replaceAllUsesWith(New: HeaderPhiR);
739 PhiR->eraseFromParent();
740 }
741}
742
743void VPlanTransforms::createInLoopReductionRecipes(
744 VPlan &Plan, const DenseSet<BasicBlock *> &BlocksNeedingPredication,
745 ElementCount MinVF) {
746 VPTypeAnalysis TypeInfo(Plan);
747 VPBasicBlock *Header = Plan.getVectorLoopRegion()->getEntryBasicBlock();
748 SmallVector<VPRecipeBase *> ToDelete;
749
750 for (VPRecipeBase &R : Header->phis()) {
751 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(Val: &R);
752 if (!PhiR || !PhiR->isInLoop() || (MinVF.isScalar() && !PhiR->isOrdered()))
753 continue;
754
755 RecurKind Kind = PhiR->getRecurrenceKind();
756 assert(!RecurrenceDescriptor::isFindLastRecurrenceKind(Kind) &&
757 !RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) &&
758 !RecurrenceDescriptor::isFindIVRecurrenceKind(Kind) &&
759 "AnyOf and Find reductions are not allowed for in-loop reductions");
760
761 bool IsFPRecurrence =
762 RecurrenceDescriptor::isFloatingPointRecurrenceKind(Kind);
763 FastMathFlags FMFs =
764 IsFPRecurrence ? FastMathFlags::getFast() : FastMathFlags();
765
766 // Collect the chain of "link" recipes for the reduction starting at PhiR.
767 SetVector<VPSingleDefRecipe *> Worklist;
768 Worklist.insert(X: PhiR);
769 for (unsigned I = 0; I != Worklist.size(); ++I) {
770 VPSingleDefRecipe *Cur = Worklist[I];
771 for (VPUser *U : Cur->users()) {
772 auto *UserRecipe = cast<VPSingleDefRecipe>(Val: U);
773 if (!UserRecipe->getParent()->getEnclosingLoopRegion()) {
774 assert((UserRecipe->getParent() == Plan.getMiddleBlock() ||
775 UserRecipe->getParent() == Plan.getScalarPreheader()) &&
776 "U must be either in the loop region, the middle block or the "
777 "scalar preheader.");
778 continue;
779 }
780
781 // Stores using instructions will be sunk later.
782 if (match(R: UserRecipe, P: m_VPInstruction<Instruction::Store>()))
783 continue;
784 Worklist.insert(X: UserRecipe);
785 }
786 }
787
788 // Visit operation "Links" along the reduction chain top-down starting from
789 // the phi until LoopExitValue. We keep track of the previous item
790 // (PreviousLink) to tell which of the two operands of a Link will remain
791 // scalar and which will be reduced. For minmax by select(cmp), Link will be
792 // the select instructions. Blend recipes of in-loop reduction phi's will
793 // get folded to their non-phi operand, as the reduction recipe handles the
794 // condition directly.
795 VPSingleDefRecipe *PreviousLink = PhiR; // Aka Worklist[0].
796 for (VPSingleDefRecipe *CurrentLink : drop_begin(RangeOrContainer&: Worklist)) {
797 if (auto *Blend = dyn_cast<VPBlendRecipe>(Val: CurrentLink)) {
798 assert(Blend->getNumIncomingValues() == 2 &&
799 "Blend must have 2 incoming values");
800 unsigned PhiRIdx = Blend->getIncomingValue(Idx: 0) == PhiR ? 0 : 1;
801 assert(Blend->getIncomingValue(PhiRIdx) == PhiR &&
802 "PhiR must be an operand of the blend");
803 Blend->replaceAllUsesWith(New: Blend->getIncomingValue(Idx: 1 - PhiRIdx));
804 continue;
805 }
806
807 if (IsFPRecurrence) {
808 FastMathFlags CurFMF =
809 cast<VPRecipeWithIRFlags>(Val: CurrentLink)->getFastMathFlags();
810 if (match(R: CurrentLink, P: m_Select(Op0: m_VPValue(), Op1: m_VPValue(), Op2: m_VPValue())))
811 CurFMF |= cast<VPRecipeWithIRFlags>(Val: CurrentLink->getOperand(N: 0))
812 ->getFastMathFlags();
813 FMFs &= CurFMF;
814 }
815
816 Instruction *CurrentLinkI = CurrentLink->getUnderlyingInstr();
817
818 // Recognize a call to the llvm.fmuladd intrinsic.
819 bool IsFMulAdd = Kind == RecurKind::FMulAdd;
820 VPValue *VecOp;
821 VPBasicBlock *LinkVPBB = CurrentLink->getParent();
822 if (IsFMulAdd) {
823 assert(RecurrenceDescriptor::isFMulAddIntrinsic(CurrentLinkI) &&
824 "Expected current VPInstruction to be a call to the "
825 "llvm.fmuladd intrinsic");
826 assert(CurrentLink->getOperand(2) == PreviousLink &&
827 "expected a call where the previous link is the added operand");
828
829 // If the instruction is a call to the llvm.fmuladd intrinsic then we
830 // need to create an fmul recipe (multiplying the first two operands of
831 // the fmuladd together) to use as the vector operand for the fadd
832 // reduction.
833 auto *FMulRecipe = new VPInstruction(
834 Instruction::FMul,
835 {CurrentLink->getOperand(N: 0), CurrentLink->getOperand(N: 1)},
836 CurrentLinkI->getFastMathFlags());
837 LinkVPBB->insert(Recipe: FMulRecipe, InsertPt: CurrentLink->getIterator());
838 VecOp = FMulRecipe;
839 } else if (Kind == RecurKind::AddChainWithSubs &&
840 match(R: CurrentLink, P: m_Sub(Op0: m_VPValue(), Op1: m_VPValue()))) {
841 Type *PhiTy = TypeInfo.inferScalarType(V: PhiR);
842 auto *Zero = Plan.getConstantInt(Ty: PhiTy, Val: 0);
843 VPBuilder Builder(LinkVPBB, CurrentLink->getIterator());
844 auto *Sub = Builder.createSub(LHS: Zero, RHS: CurrentLink->getOperand(N: 1),
845 DL: CurrentLinkI->getDebugLoc());
846 Sub->setUnderlyingValue(CurrentLinkI);
847 VecOp = Sub;
848 } else {
849 // Index of the first operand which holds a non-mask vector operand.
850 unsigned IndexOfFirstOperand = 0;
851 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind)) {
852 if (match(R: CurrentLink, P: m_Cmp(Op0: m_VPValue(), Op1: m_VPValue())))
853 continue;
854 assert(match(CurrentLink,
855 m_Select(m_VPValue(), m_VPValue(), m_VPValue())) &&
856 "must be a select recipe");
857 IndexOfFirstOperand = 1;
858 }
859 // Note that for non-commutable operands (cmp-selects), the semantics of
860 // the cmp-select are captured in the recurrence kind.
861 unsigned VecOpId =
862 CurrentLink->getOperand(N: IndexOfFirstOperand) == PreviousLink
863 ? IndexOfFirstOperand + 1
864 : IndexOfFirstOperand;
865 VecOp = CurrentLink->getOperand(N: VecOpId);
866 assert(
867 VecOp != PreviousLink &&
868 CurrentLink->getOperand(
869 cast<VPInstruction>(CurrentLink)->getNumOperandsWithoutMask() -
870 1 - (VecOpId - IndexOfFirstOperand)) == PreviousLink &&
871 "PreviousLink must be the operand other than VecOp");
872 }
873
874 // Get block mask from CurrentLink, if it needs predication.
875 VPValue *CondOp = nullptr;
876 if (BlocksNeedingPredication.contains(V: CurrentLinkI->getParent()))
877 CondOp = cast<VPInstruction>(Val: CurrentLink)->getMask();
878
879 assert(PhiR->getVFScaleFactor() == 1 &&
880 "inloop reductions must be unscaled");
881 auto *RedRecipe = new VPReductionRecipe(
882 Kind, FMFs, CurrentLinkI, PreviousLink, VecOp, CondOp,
883 getReductionStyle(/*IsInLoop=*/InLoop: true, Ordered: PhiR->isOrdered(), ScaleFactor: 1),
884 CurrentLinkI->getDebugLoc());
885 // Append the recipe to the end of the VPBasicBlock because we need to
886 // ensure that it comes after all of it's inputs, including CondOp.
887 // Delete CurrentLink as it will be invalid if its operand is replaced
888 // with a reduction defined at the bottom of the block in the next link.
889 if (LinkVPBB->getNumSuccessors() == 0)
890 RedRecipe->insertBefore(InsertPos: &*std::prev(x: std::prev(x: LinkVPBB->end())));
891 else
892 LinkVPBB->appendRecipe(Recipe: RedRecipe);
893
894 CurrentLink->replaceAllUsesWith(New: RedRecipe);
895 ToDelete.push_back(Elt: CurrentLink);
896 PreviousLink = RedRecipe;
897 }
898 }
899
900 for (VPRecipeBase *R : ToDelete)
901 R->eraseFromParent();
902}
903
904void VPlanTransforms::handleEarlyExits(VPlan &Plan,
905 bool HasUncountableEarlyExit) {
906 auto *MiddleVPBB = cast<VPBasicBlock>(
907 Val: Plan.getScalarHeader()->getSinglePredecessor()->getPredecessors()[0]);
908 auto *LatchVPBB = cast<VPBasicBlock>(Val: MiddleVPBB->getSinglePredecessor());
909 VPBlockBase *HeaderVPB = cast<VPBasicBlock>(Val: LatchVPBB->getSuccessors()[1]);
910
911 if (HasUncountableEarlyExit) {
912 handleUncountableEarlyExits(Plan, HeaderVPBB: cast<VPBasicBlock>(Val: HeaderVPB), LatchVPBB,
913 MiddleVPBB);
914 return;
915 }
916
917 // Disconnect countable early exits from the loop, leaving it with a single
918 // exit from the latch. Countable early exits are left for a scalar epilog.
919 for (VPIRBasicBlock *EB : Plan.getExitBlocks()) {
920 for (VPBlockBase *Pred : to_vector(Range&: EB->getPredecessors())) {
921 if (Pred == MiddleVPBB)
922 continue;
923
924 // Remove phi operands for the early exiting block.
925 for (VPRecipeBase &R : EB->phis())
926 cast<VPIRPhi>(Val: &R)->removeIncomingValueFor(IncomingBlock: Pred);
927 auto *EarlyExitingVPBB = cast<VPBasicBlock>(Val: Pred);
928 EarlyExitingVPBB->getTerminator()->eraseFromParent();
929 VPBlockUtils::disconnectBlocks(From: Pred, To: EB);
930 }
931 }
932}
933
934void VPlanTransforms::addMiddleCheck(VPlan &Plan,
935 bool RequiresScalarEpilogueCheck,
936 bool TailFolded) {
937 auto *MiddleVPBB = cast<VPBasicBlock>(
938 Val: Plan.getScalarHeader()->getSinglePredecessor()->getPredecessors()[0]);
939 // If MiddleVPBB has a single successor then the original loop does not exit
940 // via the latch and the single successor must be the scalar preheader.
941 // There's no need to add a runtime check to MiddleVPBB.
942 if (MiddleVPBB->getNumSuccessors() == 1) {
943 assert(MiddleVPBB->getSingleSuccessor() == Plan.getScalarPreheader() &&
944 "must have ScalarPH as single successor");
945 return;
946 }
947
948 assert(MiddleVPBB->getNumSuccessors() == 2 && "must have 2 successors");
949
950 // Add a check in the middle block to see if we have completed all of the
951 // iterations in the first vector loop.
952 //
953 // Three cases:
954 // 1) If we require a scalar epilogue, the scalar ph must execute. Set the
955 // condition to false.
956 // 2) If (N - N%VF) == N, then we *don't* need to run the
957 // remainder. Thus if tail is to be folded, we know we don't need to run
958 // the remainder and we can set the condition to true.
959 // 3) Otherwise, construct a runtime check.
960
961 // We use the same DebugLoc as the scalar loop latch terminator instead of
962 // the corresponding compare because they may have ended up with different
963 // line numbers and we want to avoid awkward line stepping while debugging.
964 // E.g., if the compare has got a line number inside the loop.
965 auto *LatchVPBB = cast<VPBasicBlock>(Val: MiddleVPBB->getSinglePredecessor());
966 DebugLoc LatchDL = LatchVPBB->getTerminator()->getDebugLoc();
967 VPBuilder Builder(MiddleVPBB);
968 VPValue *Cmp;
969 if (!RequiresScalarEpilogueCheck)
970 Cmp = Plan.getFalse();
971 else if (TailFolded)
972 Cmp = Plan.getTrue();
973 else
974 Cmp = Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: Plan.getTripCount(),
975 B: &Plan.getVectorTripCount(), DL: LatchDL, Name: "cmp.n");
976 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cmp}, DL: LatchDL);
977}
978
979void VPlanTransforms::createLoopRegions(VPlan &Plan) {
980 VPDominatorTree VPDT(Plan);
981 for (VPBlockBase *HeaderVPB : vp_post_order_shallow(G: Plan.getEntry()))
982 if (canonicalHeaderAndLatch(HeaderVPB, VPDT))
983 createLoopRegion(Plan, HeaderVPB);
984
985 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
986 TopRegion->setName("vector loop");
987 TopRegion->getEntryBasicBlock()->setName("vector.body");
988}
989
990/// Insert \p CheckBlockVPBB on the edge leading to the vector preheader,
991/// connecting it to both vector and scalar preheaders. Updates scalar
992/// preheader phis to account for the new predecessor.
993static void insertCheckBlockBeforeVectorLoop(VPlan &Plan,
994 VPBasicBlock *CheckBlockVPBB) {
995 VPBlockBase *VectorPH = Plan.getVectorPreheader();
996 auto *ScalarPH = cast<VPBasicBlock>(Val: Plan.getScalarPreheader());
997 VPBlockBase *PreVectorPH = VectorPH->getSinglePredecessor();
998 VPBlockUtils::insertOnEdge(From: PreVectorPH, To: VectorPH, BlockPtr: CheckBlockVPBB);
999 VPBlockUtils::connectBlocks(From: CheckBlockVPBB, To: ScalarPH);
1000 CheckBlockVPBB->swapSuccessors();
1001 unsigned NumPreds = ScalarPH->getNumPredecessors();
1002 for (VPRecipeBase &R : ScalarPH->phis()) {
1003 auto *Phi = cast<VPPhi>(Val: &R);
1004 assert(Phi->getNumIncoming() == NumPreds - 1 &&
1005 "must have incoming values for all predecessors");
1006 Phi->addOperand(Operand: Phi->getOperand(N: NumPreds - 2));
1007 }
1008}
1009
1010// Likelyhood of bypassing the vectorized loop due to a runtime check block,
1011// including memory overlap checks block and wrapping/unit-stride checks block.
1012static constexpr uint32_t CheckBypassWeights[] = {1, 127};
1013
1014/// Create a BranchOnCond terminator in \p CheckBlockVPBB. Optionally adds
1015/// branch weights.
1016static void addBypassBranch(VPlan &Plan, VPBasicBlock *CheckBlockVPBB,
1017 VPValue *Cond, bool AddBranchWeights) {
1018 DebugLoc DL = Plan.getVectorLoopRegion()->getCanonicalIV()->getDebugLoc();
1019 auto *Term = VPBuilder(CheckBlockVPBB)
1020 .createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cond}, DL);
1021 if (AddBranchWeights) {
1022 MDBuilder MDB(Plan.getContext());
1023 MDNode *BranchWeights =
1024 MDB.createBranchWeights(Weights: CheckBypassWeights, /*IsExpected=*/false);
1025 Term->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1026 }
1027}
1028
1029void VPlanTransforms::attachCheckBlock(VPlan &Plan, Value *Cond,
1030 BasicBlock *CheckBlock,
1031 bool AddBranchWeights) {
1032 VPValue *CondVPV = Plan.getOrAddLiveIn(V: Cond);
1033 VPBasicBlock *CheckBlockVPBB = Plan.createVPIRBasicBlock(IRBB: CheckBlock);
1034 insertCheckBlockBeforeVectorLoop(Plan, CheckBlockVPBB);
1035 addBypassBranch(Plan, CheckBlockVPBB, Cond: CondVPV, AddBranchWeights);
1036}
1037
1038void VPlanTransforms::addMinimumIterationCheck(
1039 VPlan &Plan, ElementCount VF, unsigned UF,
1040 ElementCount MinProfitableTripCount, bool RequiresScalarEpilogue,
1041 bool TailFolded, bool CheckNeededWithTailFolding, Loop *OrigLoop,
1042 const uint32_t *MinItersBypassWeights, DebugLoc DL,
1043 PredicatedScalarEvolution &PSE) {
1044 // Generate code to check if the loop's trip count is less than VF * UF, or
1045 // equal to it in case a scalar epilogue is required; this implies that the
1046 // vector trip count is zero. This check also covers the case where adding one
1047 // to the backedge-taken count overflowed leading to an incorrect trip count
1048 // of zero. In this case we will also jump to the scalar loop.
1049 CmpInst::Predicate CmpPred =
1050 RequiresScalarEpilogue ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
1051 // If tail is to be folded, vector loop takes care of all iterations.
1052 VPValue *TripCountVPV = Plan.getTripCount();
1053 const SCEV *TripCount = vputils::getSCEVExprForVPValue(V: TripCountVPV, PSE);
1054 Type *TripCountTy = TripCount->getType();
1055 ScalarEvolution &SE = *PSE.getSE();
1056 auto GetMinTripCount = [&]() -> const SCEV * {
1057 // Compute max(MinProfitableTripCount, UF * VF) and return it.
1058 const SCEV *VFxUF =
1059 SE.getElementCount(Ty: TripCountTy, EC: (VF * UF), Flags: SCEV::FlagNUW);
1060 if (UF * VF.getKnownMinValue() >=
1061 MinProfitableTripCount.getKnownMinValue()) {
1062 // TODO: SCEV should be able to simplify test.
1063 return VFxUF;
1064 }
1065 const SCEV *MinProfitableTripCountSCEV =
1066 SE.getElementCount(Ty: TripCountTy, EC: MinProfitableTripCount, Flags: SCEV::FlagNUW);
1067 return SE.getUMaxExpr(LHS: MinProfitableTripCountSCEV, RHS: VFxUF);
1068 };
1069
1070 VPBasicBlock *EntryVPBB = Plan.getEntry();
1071 VPBuilder Builder(EntryVPBB);
1072 VPValue *TripCountCheck = Plan.getFalse();
1073 const SCEV *Step = GetMinTripCount();
1074 if (TailFolded) {
1075 if (CheckNeededWithTailFolding) {
1076 // vscale is not necessarily a power-of-2, which means we cannot guarantee
1077 // an overflow to zero when updating induction variables and so an
1078 // additional overflow check is required before entering the vector loop.
1079
1080 VPValue *StepVPV = Builder.createExpandSCEV(Expr: Step);
1081
1082 // Get the maximum unsigned value for the type.
1083 VPValue *MaxUIntTripCount =
1084 Plan.getConstantInt(Val: cast<IntegerType>(Val: TripCountTy)->getMask());
1085 VPValue *DistanceToMax =
1086 Builder.createSub(LHS: MaxUIntTripCount, RHS: TripCountVPV);
1087
1088 // Don't execute the vector loop if (UMax - n) < (VF * UF).
1089 // FIXME: Should only check VF * UF, but currently checks Step=max(VF*UF,
1090 // minProfitableTripCount).
1091 TripCountCheck =
1092 Builder.createICmp(Pred: ICmpInst::ICMP_ULT, A: DistanceToMax, B: StepVPV, DL);
1093 } else {
1094 // TripCountCheck = false, folding tail implies positive vector trip
1095 // count.
1096 }
1097 } else {
1098 // TODO: Emit unconditional branch to vector preheader instead of
1099 // conditional branch with known condition.
1100 TripCount = SE.applyLoopGuards(Expr: TripCount, L: OrigLoop);
1101 // Check if the trip count is < the step.
1102 if (SE.isKnownPredicate(Pred: CmpPred, LHS: TripCount, RHS: Step)) {
1103 // TODO: Ensure step is at most the trip count when determining max VF and
1104 // UF, w/o tail folding.
1105 TripCountCheck = Plan.getTrue();
1106 } else if (!SE.isKnownPredicate(Pred: CmpInst::getInversePredicate(pred: CmpPred),
1107 LHS: TripCount, RHS: Step)) {
1108 // Generate the minimum iteration check only if we cannot prove the
1109 // check is known to be true, or known to be false.
1110 VPValue *MinTripCountVPV = Builder.createExpandSCEV(Expr: Step);
1111 TripCountCheck = Builder.createICmp(
1112 Pred: CmpPred, A: TripCountVPV, B: MinTripCountVPV, DL, Name: "min.iters.check");
1113 } // else step known to be < trip count, use TripCountCheck preset to false.
1114 }
1115 VPInstruction *Term =
1116 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {TripCountCheck}, DL);
1117 if (MinItersBypassWeights) {
1118 MDBuilder MDB(Plan.getContext());
1119 MDNode *BranchWeights = MDB.createBranchWeights(
1120 Weights: ArrayRef(MinItersBypassWeights, 2), /*IsExpected=*/false);
1121 Term->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1122 }
1123}
1124
1125void VPlanTransforms::addMinimumVectorEpilogueIterationCheck(
1126 VPlan &Plan, Value *TripCount, Value *VectorTripCount,
1127 bool RequiresScalarEpilogue, ElementCount EpilogueVF, unsigned EpilogueUF,
1128 unsigned MainLoopStep, unsigned EpilogueLoopStep, ScalarEvolution &SE) {
1129 // Add the minimum iteration check for the epilogue vector loop.
1130 VPValue *TC = Plan.getOrAddLiveIn(V: TripCount);
1131 VPBuilder Builder(cast<VPBasicBlock>(Val: Plan.getEntry()));
1132 VPValue *VFxUF = Builder.createExpandSCEV(Expr: SE.getElementCount(
1133 Ty: TripCount->getType(), EC: (EpilogueVF * EpilogueUF), Flags: SCEV::FlagNUW));
1134 VPValue *Count = Builder.createSub(LHS: TC, RHS: Plan.getOrAddLiveIn(V: VectorTripCount),
1135 DL: DebugLoc::getUnknown(), Name: "n.vec.remaining");
1136
1137 // Generate code to check if the loop's trip count is less than VF * UF of
1138 // the vector epilogue loop.
1139 auto P = RequiresScalarEpilogue ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT;
1140 auto *CheckMinIters = Builder.createICmp(
1141 Pred: P, A: Count, B: VFxUF, DL: DebugLoc::getUnknown(), Name: "min.epilog.iters.check");
1142 VPInstruction *Branch =
1143 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: CheckMinIters);
1144
1145 // We assume the remaining `Count` is equally distributed in
1146 // [0, MainLoopStep)
1147 // So the probability for `Count < EpilogueLoopStep` should be
1148 // min(MainLoopStep, EpilogueLoopStep) / MainLoopStep
1149 // TODO: Improve the estimate by taking the estimated trip count into
1150 // consideration.
1151 unsigned EstimatedSkipCount = std::min(a: MainLoopStep, b: EpilogueLoopStep);
1152 const uint32_t Weights[] = {EstimatedSkipCount,
1153 MainLoopStep - EstimatedSkipCount};
1154 MDBuilder MDB(Plan.getContext());
1155 MDNode *BranchWeights =
1156 MDB.createBranchWeights(Weights, /*IsExpected=*/false);
1157 Branch->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1158}
1159
1160/// Find and return the final select instruction of the FindIV result pattern
1161/// for the given \p BackedgeVal:
1162/// select(icmp ne ComputeReductionResult(ReducedIV), Sentinel),
1163/// ComputeReductionResult(ReducedIV), Start.
1164static VPInstruction *findFindIVSelect(VPValue *BackedgeVal) {
1165 return cast<VPInstruction>(
1166 Val: vputils::findRecipe(Start: BackedgeVal, Pred: [BackedgeVal](VPRecipeBase *R) {
1167 auto *VPI = dyn_cast<VPInstruction>(Val: R);
1168 return VPI &&
1169 matchFindIVResult(VPI, ReducedIV: m_Specific(VPV: BackedgeVal), Start: m_VPValue());
1170 }));
1171}
1172
1173bool VPlanTransforms::handleMaxMinNumReductions(VPlan &Plan) {
1174 auto GetMinOrMaxCompareValue =
1175 [](VPReductionPHIRecipe *RedPhiR) -> VPValue * {
1176 auto *MinOrMaxR =
1177 dyn_cast_or_null<VPRecipeWithIRFlags>(Val: RedPhiR->getBackedgeValue());
1178 if (!MinOrMaxR)
1179 return nullptr;
1180
1181 // Check that MinOrMaxR is a VPWidenIntrinsicRecipe or VPReplicateRecipe
1182 // with an intrinsic that matches the reduction kind.
1183 Intrinsic::ID ExpectedIntrinsicID =
1184 getMinMaxReductionIntrinsicOp(RK: RedPhiR->getRecurrenceKind());
1185 if (!match(V: MinOrMaxR, P: m_Intrinsic(IntrID: ExpectedIntrinsicID)))
1186 return nullptr;
1187
1188 if (MinOrMaxR->getOperand(N: 0) == RedPhiR)
1189 return MinOrMaxR->getOperand(N: 1);
1190
1191 assert(MinOrMaxR->getOperand(1) == RedPhiR &&
1192 "Reduction phi operand expected");
1193 return MinOrMaxR->getOperand(N: 0);
1194 };
1195
1196 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
1197 SmallVector<std::pair<VPReductionPHIRecipe *, VPValue *>>
1198 MinOrMaxNumReductionsToHandle;
1199 bool HasUnsupportedPhi = false;
1200 for (auto &R : LoopRegion->getEntryBasicBlock()->phis()) {
1201 if (isa<VPCanonicalIVPHIRecipe, VPWidenIntOrFpInductionRecipe>(Val: &R))
1202 continue;
1203 auto *Cur = dyn_cast<VPReductionPHIRecipe>(Val: &R);
1204 if (!Cur) {
1205 // TODO: Also support fixed-order recurrence phis.
1206 HasUnsupportedPhi = true;
1207 continue;
1208 }
1209 if (!RecurrenceDescriptor::isFPMinMaxNumRecurrenceKind(
1210 Kind: Cur->getRecurrenceKind())) {
1211 HasUnsupportedPhi = true;
1212 continue;
1213 }
1214
1215 VPValue *MinOrMaxOp = GetMinOrMaxCompareValue(Cur);
1216 if (!MinOrMaxOp)
1217 return false;
1218
1219 MinOrMaxNumReductionsToHandle.emplace_back(Args&: Cur, Args&: MinOrMaxOp);
1220 }
1221
1222 if (MinOrMaxNumReductionsToHandle.empty())
1223 return true;
1224
1225 // We won't be able to resume execution in the scalar tail, if there are
1226 // unsupported header phis or there is no scalar tail at all, due to
1227 // tail-folding.
1228 if (HasUnsupportedPhi || !Plan.hasScalarTail())
1229 return false;
1230
1231 /// Check if the vector loop of \p Plan can early exit and restart
1232 /// execution of last vector iteration in the scalar loop. This requires all
1233 /// recipes up to early exit point be side-effect free as they are
1234 /// re-executed. Currently we check that the loop is free of any recipe that
1235 /// may write to memory. Expected to operate on an early VPlan w/o nested
1236 /// regions.
1237 for (VPBlockBase *VPB : vp_depth_first_shallow(
1238 G: Plan.getVectorLoopRegion()->getEntryBasicBlock())) {
1239 auto *VPBB = cast<VPBasicBlock>(Val: VPB);
1240 for (auto &R : *VPBB) {
1241 if (R.mayWriteToMemory() && !match(V: &R, P: m_BranchOnCount()))
1242 return false;
1243 }
1244 }
1245
1246 VPBasicBlock *LatchVPBB = LoopRegion->getExitingBasicBlock();
1247 VPBuilder LatchBuilder(LatchVPBB->getTerminator());
1248 VPValue *AllNaNLanes = nullptr;
1249 SmallPtrSet<VPValue *, 2> RdxResults;
1250 for (const auto &[_, MinOrMaxOp] : MinOrMaxNumReductionsToHandle) {
1251 VPValue *RedNaNLanes =
1252 LatchBuilder.createFCmp(Pred: CmpInst::FCMP_UNO, A: MinOrMaxOp, B: MinOrMaxOp);
1253 AllNaNLanes = AllNaNLanes ? LatchBuilder.createOr(LHS: AllNaNLanes, RHS: RedNaNLanes)
1254 : RedNaNLanes;
1255 }
1256
1257 VPValue *AnyNaNLane =
1258 LatchBuilder.createNaryOp(Opcode: VPInstruction::AnyOf, Operands: {AllNaNLanes});
1259 VPBasicBlock *MiddleVPBB = Plan.getMiddleBlock();
1260 VPBuilder MiddleBuilder(MiddleVPBB, MiddleVPBB->begin());
1261 for (const auto &[RedPhiR, _] : MinOrMaxNumReductionsToHandle) {
1262 assert(RecurrenceDescriptor::isFPMinMaxNumRecurrenceKind(
1263 RedPhiR->getRecurrenceKind()) &&
1264 "unsupported reduction");
1265
1266 // If we exit early due to NaNs, compute the final reduction result based on
1267 // the reduction phi at the beginning of the last vector iteration.
1268 auto *RdxResult = vputils::findComputeReductionResult(PhiR: RedPhiR);
1269 assert(RdxResult && "must find a ComputeReductionResult");
1270
1271 auto *NewSel = MiddleBuilder.createSelect(Cond: AnyNaNLane, TrueVal: RedPhiR,
1272 FalseVal: RdxResult->getOperand(N: 0));
1273 RdxResult->setOperand(I: 0, New: NewSel);
1274 assert(!RdxResults.contains(RdxResult) && "RdxResult already used");
1275 RdxResults.insert(Ptr: RdxResult);
1276 }
1277
1278 auto *LatchExitingBranch = LatchVPBB->getTerminator();
1279 assert(match(LatchExitingBranch, m_BranchOnCount(m_VPValue(), m_VPValue())) &&
1280 "Unexpected terminator");
1281 auto *IsLatchExitTaken = LatchBuilder.createICmp(
1282 Pred: CmpInst::ICMP_EQ, A: LatchExitingBranch->getOperand(N: 0),
1283 B: LatchExitingBranch->getOperand(N: 1));
1284 auto *AnyExitTaken = LatchBuilder.createOr(LHS: AnyNaNLane, RHS: IsLatchExitTaken);
1285 LatchBuilder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: AnyExitTaken);
1286 LatchExitingBranch->eraseFromParent();
1287
1288 // Update resume phis for inductions in the scalar preheader. If AnyNaNLane is
1289 // true, the resume from the start of the last vector iteration via the
1290 // canonical IV, otherwise from the original value.
1291 for (auto &R : Plan.getScalarPreheader()->phis()) {
1292 auto *ResumeR = cast<VPPhi>(Val: &R);
1293 VPValue *VecV = ResumeR->getOperand(N: 0);
1294 if (RdxResults.contains(Ptr: VecV))
1295 continue;
1296 if (auto *DerivedIV = dyn_cast<VPDerivedIVRecipe>(Val: VecV)) {
1297 if (DerivedIV->getNumUsers() == 1 &&
1298 DerivedIV->getOperand(N: 1) == &Plan.getVectorTripCount()) {
1299 auto *NewSel =
1300 MiddleBuilder.createSelect(Cond: AnyNaNLane, TrueVal: LoopRegion->getCanonicalIV(),
1301 FalseVal: &Plan.getVectorTripCount());
1302 DerivedIV->moveAfter(MovePos: &*MiddleBuilder.getInsertPoint());
1303 DerivedIV->setOperand(I: 1, New: NewSel);
1304 continue;
1305 }
1306 }
1307 // Bail out and abandon the current, partially modified, VPlan if we
1308 // encounter resume phi that cannot be updated yet.
1309 if (VecV != &Plan.getVectorTripCount()) {
1310 LLVM_DEBUG(dbgs() << "Found resume phi we cannot update for VPlan with "
1311 "FMaxNum/FMinNum reduction.\n");
1312 return false;
1313 }
1314 auto *NewSel = MiddleBuilder.createSelect(
1315 Cond: AnyNaNLane, TrueVal: LoopRegion->getCanonicalIV(), FalseVal: VecV);
1316 ResumeR->setOperand(I: 0, New: NewSel);
1317 }
1318
1319 auto *MiddleTerm = MiddleVPBB->getTerminator();
1320 MiddleBuilder.setInsertPoint(MiddleTerm);
1321 VPValue *MiddleCond = MiddleTerm->getOperand(N: 0);
1322 VPValue *NewCond =
1323 MiddleBuilder.createAnd(LHS: MiddleCond, RHS: MiddleBuilder.createNot(Operand: AnyNaNLane));
1324 MiddleTerm->setOperand(I: 0, New: NewCond);
1325 return true;
1326}
1327
1328bool VPlanTransforms::handleFindLastReductions(VPlan &Plan) {
1329 if (Plan.hasScalarVFOnly())
1330 return false;
1331
1332 // We want to create the following nodes:
1333 // vector.body:
1334 // ...new WidenPHI recipe introduced to keep the mask value for the latest
1335 // iteration where any lane was active.
1336 // mask.phi = phi [ ir<false>, vector.ph ], [ vp<new.mask>, vector.body ]
1337 // ...data.phi (a VPReductionPHIRecipe for a FindLast reduction) already
1338 // exists, but needs updating to use 'new.data' for the backedge value.
1339 // data.phi = phi ir<default.val>, vp<new.data>
1340 //
1341 // ...'data' and 'compare' created by existing nodes...
1342 //
1343 // ...new recipes introduced to determine whether to update the reduction
1344 // values or keep the current one.
1345 // any.active = i1 any-of ir<compare>
1346 // new.mask = select vp<any.active>, ir<compare>, vp<mask.phi>
1347 // new.data = select vp<any.active>, ir<data>, ir<data.phi>
1348 //
1349 // middle.block:
1350 // ...extract-last-active replaces compute-reduction-result.
1351 // result = extract-last-active vp<new.data>, vp<new.mask>, ir<default.val>
1352
1353 for (auto &Phi : Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
1354 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(Val: &Phi);
1355 if (!PhiR || !RecurrenceDescriptor::isFindLastRecurrenceKind(
1356 Kind: PhiR->getRecurrenceKind()))
1357 continue;
1358
1359 // Find the condition for the select/blend.
1360 auto *SelectR = cast<VPSingleDefRecipe>(Val: &PhiR->getBackedgeRecipe());
1361 VPValue *Cond = nullptr, *Op1 = nullptr, *Op2 = nullptr;
1362
1363 // If we're matching a blend rather than a select, there should be one
1364 // incoming value which is the data, then all other incoming values should
1365 // be the phi.
1366 auto MatchBlend = [&](VPRecipeBase *R) {
1367 auto *Blend = dyn_cast<VPBlendRecipe>(Val: R);
1368 if (!Blend)
1369 return false;
1370 assert(!Blend->isNormalized() && "must run before blend normalizaion");
1371 unsigned NumIncomingDataValues = 0;
1372 for (unsigned I = 0; I < Blend->getNumIncomingValues(); ++I) {
1373 VPValue *Incoming = Blend->getIncomingValue(Idx: I);
1374 if (Incoming != PhiR) {
1375 ++NumIncomingDataValues;
1376 Cond = Blend->getMask(Idx: I);
1377 Op1 = Incoming;
1378 Op2 = PhiR;
1379 }
1380 }
1381 return NumIncomingDataValues == 1;
1382 };
1383
1384 if (!match(R: SelectR,
1385 P: m_Select(Op0: m_VPValue(V&: Cond), Op1: m_VPValue(V&: Op1), Op2: m_VPValue(V&: Op2))) &&
1386 !MatchBlend(SelectR))
1387 return false;
1388
1389 // Add mask phi.
1390 VPBuilder Builder = VPBuilder::getToInsertAfter(R: PhiR);
1391 auto *MaskPHI = new VPWidenPHIRecipe(nullptr, /*Start=*/Plan.getFalse());
1392 Builder.insert(R: MaskPHI);
1393
1394 // Add select for mask.
1395 Builder.setInsertPoint(SelectR);
1396
1397 if (Op1 == PhiR) {
1398 // Normalize to selecting the data operand when the condition is true by
1399 // swapping operands and negating the condition.
1400 std::swap(a&: Op1, b&: Op2);
1401 Cond = Builder.createNot(Operand: Cond);
1402 }
1403 assert(Op2 == PhiR && "data value must be selected if Cond is true");
1404
1405 VPValue *AnyOf = Builder.createNaryOp(Opcode: VPInstruction::AnyOf, Operands: {Cond});
1406 VPValue *MaskSelect = Builder.createSelect(Cond: AnyOf, TrueVal: Cond, FalseVal: MaskPHI);
1407 MaskPHI->addOperand(Operand: MaskSelect);
1408
1409 // Replace select for data.
1410 VPValue *DataSelect =
1411 Builder.createSelect(Cond: AnyOf, TrueVal: Op1, FalseVal: Op2, DL: SelectR->getDebugLoc());
1412 SelectR->replaceAllUsesWith(New: DataSelect);
1413 SelectR->eraseFromParent();
1414
1415 // Find final reduction computation and replace it with an
1416 // extract.last.active intrinsic.
1417 auto *RdxResult =
1418 vputils::findUserOf<VPInstruction::ComputeReductionResult>(V: DataSelect);
1419 // TODO: Handle tail-folding.
1420 if (!RdxResult)
1421 return false;
1422 Builder.setInsertPoint(RdxResult);
1423 auto *ExtractLastActive =
1424 Builder.createNaryOp(Opcode: VPInstruction::ExtractLastActive,
1425 Operands: {DataSelect, MaskSelect, PhiR->getStartValue()},
1426 DL: RdxResult->getDebugLoc());
1427 RdxResult->replaceAllUsesWith(New: ExtractLastActive);
1428 RdxResult->eraseFromParent();
1429 }
1430
1431 return true;
1432}
1433
1434/// Given a first argmin/argmax pattern with strict predicate consisting of
1435/// 1) a MinOrMax reduction \p MinOrMaxPhiR producing \p MinOrMaxResult,
1436/// 2) a wide induction \p WideIV,
1437/// 3) a FindLastIV reduction \p FindLastIVPhiR using \p WideIV,
1438/// return the smallest index of the FindLastIV reduction result using UMin,
1439/// unless \p MinOrMaxResult equals the start value of its MinOrMax reduction.
1440/// In that case, return the start value of the FindLastIV reduction instead.
1441/// If \p WideIV is not canonical, a new canonical wide IV is added, and the
1442/// final result is scaled back to the non-canonical \p WideIV.
1443/// The final value of the FindLastIV reduction is originally computed using
1444/// \p FindIVSelect, \p FindIVCmp, and \p FindIVRdxResult, which are replaced
1445/// and removed.
1446/// Returns true if the pattern was handled successfully, false otherwise.
1447static bool handleFirstArgMinOrMax(
1448 VPlan &Plan, VPReductionPHIRecipe *MinOrMaxPhiR,
1449 VPReductionPHIRecipe *FindLastIVPhiR, VPWidenIntOrFpInductionRecipe *WideIV,
1450 VPInstruction *MinOrMaxResult, VPInstruction *FindIVSelect,
1451 VPRecipeBase *FindIVCmp, VPInstruction *FindIVRdxResult) {
1452 assert(!FindLastIVPhiR->isInLoop() && !FindLastIVPhiR->isOrdered() &&
1453 "inloop and ordered reductions not supported");
1454 assert(FindLastIVPhiR->getVFScaleFactor() == 1 &&
1455 "FindIV reduction must not be scaled");
1456
1457 Type *Ty = Plan.getVectorLoopRegion()->getCanonicalIVType();
1458 // TODO: Support non (i.e., narrower than) canonical IV types.
1459 // TODO: Emit remarks for failed transformations.
1460 if (Ty != VPTypeAnalysis(Plan).inferScalarType(V: WideIV))
1461 return false;
1462
1463 auto *FindIVSelectR = cast<VPSingleDefRecipe>(
1464 Val: FindLastIVPhiR->getBackedgeValue()->getDefiningRecipe());
1465 assert(
1466 match(FindIVSelectR, m_Select(m_VPValue(), m_VPValue(), m_VPValue())) &&
1467 "backedge value must be a select");
1468 if (FindIVSelectR->getOperand(N: 1) != WideIV &&
1469 FindIVSelectR->getOperand(N: 2) != WideIV)
1470 return false;
1471
1472 // If the original wide IV is not canonical, create a new one. The canonical
1473 // wide IV is guaranteed to not wrap for all lanes that are active in the
1474 // vector loop.
1475 if (!WideIV->isCanonical()) {
1476 VPIRValue *Zero = Plan.getConstantInt(Ty, Val: 0);
1477 VPIRValue *One = Plan.getConstantInt(Ty, Val: 1);
1478 auto *WidenCanIV = new VPWidenIntOrFpInductionRecipe(
1479 nullptr, Zero, One, WideIV->getVFValue(),
1480 WideIV->getInductionDescriptor(),
1481 VPIRFlags::WrapFlagsTy(/*HasNUW=*/true, /*HasNSW=*/false),
1482 WideIV->getDebugLoc());
1483 WidenCanIV->insertBefore(InsertPos: WideIV);
1484
1485 // Update the select to use the wide canonical IV.
1486 FindIVSelectR->setOperand(I: FindIVSelectR->getOperand(N: 1) == WideIV ? 1 : 2,
1487 New: WidenCanIV);
1488 }
1489 FindLastIVPhiR->setOperand(I: 0, New: Plan.getOrAddLiveIn(V: PoisonValue::get(T: Ty)));
1490
1491 // The reduction using MinOrMaxPhiR needs adjusting to compute the correct
1492 // result:
1493 // 1. Find the first canonical indices corresponding to partial min/max
1494 // values, using loop reductions.
1495 // 2. Find which of the partial min/max values are equal to the overall
1496 // min/max value.
1497 // 3. Select among the canonical indices those corresponding to the overall
1498 // min/max value.
1499 // 4. Find the first canonical index of overall min/max and scale it back to
1500 // the original IV using VPDerivedIVRecipe.
1501 // 5. If the overall min/max equals the starting min/max, the condition in
1502 // the loop was always false, due to being strict; return the start value
1503 // of FindLastIVPhiR in that case.
1504 //
1505 // For example, we transforms two independent reduction result computations
1506 // for
1507 //
1508 // <x1> vector loop: {
1509 // vector.body:
1510 // ...
1511 // ir<%iv> = WIDEN-INDUCTION nuw nsw ir<10>, ir<1>, vp<%0>
1512 // WIDEN-REDUCTION-PHI ir<%min.idx> = phi ir<sentinel.min.start>,
1513 // ir<%min.idx.next>
1514 // WIDEN-REDUCTION-PHI ir<%min.val> = phi ir<100>, ir<%min.val.next>
1515 // ....
1516 // WIDEN-INTRINSIC ir<%min.val.next> = call llvm.umin(ir<%min.val>, ir<%l>)
1517 // WIDEN ir<%min.idx.next> = select ir<%cmp>, ir<%iv>, ir<%min.idx>
1518 // ...
1519 // }
1520 // Successor(s): middle.block
1521 //
1522 // middle.block:
1523 // vp<%iv.rdx> = compute-reduction-result (smax) vp<%min.idx.next>
1524 // vp<%min.result> = compute-reduction-result (umin) ir<%min.val.next>
1525 // vp<%cmp> = icmp ne vp<%iv.rdx>, ir<sentinel.min.start>
1526 // vp<%find.iv.result> = select vp<%cmp>, vp<%iv.rdx>, ir<10>
1527 //
1528 //
1529 // Into:
1530 //
1531 // vp<%reduced.min> = compute-reduction-result (umin) ir<%min.val.next>
1532 // vp<%reduced.mins.mask> = icmp eq ir<%min.val.next>, vp<%reduced.min>
1533 // vp<%idxs2reduce> = select vp<%reduced.mins.mask>, ir<%min.idx.next>,
1534 // ir<MaxUInt>
1535 // vp<%reduced.idx> = compute-reduction-result (umin) vp<%idxs2reduce>
1536 // vp<%scaled.idx> = DERIVED-IV ir<20> + vp<%reduced.idx> * ir<1>
1537 // vp<%always.false> = icmp eq vp<%reduced.min>, ir<100>
1538 // vp<%final.idx> = select vp<%always.false>, ir<10>,
1539 // vp<%scaled.idx>
1540
1541 VPBuilder Builder(FindIVRdxResult);
1542 VPValue *MinOrMaxExiting = MinOrMaxResult->getOperand(N: 0);
1543 auto *FinalMinOrMaxCmp =
1544 Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: MinOrMaxExiting, B: MinOrMaxResult);
1545 VPValue *LastIVExiting = FindIVRdxResult->getOperand(N: 0);
1546 VPValue *MaxIV =
1547 Plan.getConstantInt(Val: APInt::getMaxValue(numBits: Ty->getIntegerBitWidth()));
1548 auto *FinalIVSelect =
1549 Builder.createSelect(Cond: FinalMinOrMaxCmp, TrueVal: LastIVExiting, FalseVal: MaxIV);
1550 VPIRFlags RdxFlags(RecurKind::UMin, false, false, FastMathFlags());
1551 VPSingleDefRecipe *FinalCanIV = Builder.createNaryOp(
1552 Opcode: VPInstruction::ComputeReductionResult, Operands: {FinalIVSelect}, Flags: RdxFlags,
1553 DL: FindIVRdxResult->getDebugLoc());
1554
1555 // If we used a new wide canonical IV convert the reduction result back to the
1556 // original IV scale before the final select.
1557 if (!WideIV->isCanonical()) {
1558 auto *DerivedIVRecipe =
1559 new VPDerivedIVRecipe(InductionDescriptor::IK_IntInduction,
1560 nullptr, // No FPBinOp for integer induction
1561 WideIV->getStartValue(), FinalCanIV,
1562 WideIV->getStepValue(), "derived.iv.result");
1563 DerivedIVRecipe->insertBefore(InsertPos: &*Builder.getInsertPoint());
1564 FinalCanIV = DerivedIVRecipe;
1565 }
1566
1567 // If the final min/max value matches its start value, the condition in the
1568 // loop was always false, i.e. no induction value has been selected. If that's
1569 // the case, set the result of the IV reduction to its start value.
1570 VPValue *AlwaysFalse = Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: MinOrMaxResult,
1571 B: MinOrMaxPhiR->getStartValue());
1572 VPValue *FinalIV = Builder.createSelect(
1573 Cond: AlwaysFalse, TrueVal: FindIVSelect->getOperand(N: 2), FalseVal: FinalCanIV);
1574 FindIVSelect->replaceAllUsesWith(New: FinalIV);
1575
1576 // Erase the old FindIV result pattern which is now dead.
1577 FindIVSelect->eraseFromParent();
1578 FindIVCmp->eraseFromParent();
1579 FindIVRdxResult->eraseFromParent();
1580 return true;
1581}
1582
1583bool VPlanTransforms::handleMultiUseReductions(VPlan &Plan,
1584 OptimizationRemarkEmitter *ORE,
1585 Loop *TheLoop) {
1586 for (auto &PhiR : make_early_inc_range(
1587 Range: Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis())) {
1588 auto *MinOrMaxPhiR = dyn_cast<VPReductionPHIRecipe>(Val: &PhiR);
1589 // TODO: check for multi-uses in VPlan directly.
1590 if (!MinOrMaxPhiR || !MinOrMaxPhiR->hasUsesOutsideReductionChain())
1591 continue;
1592
1593 // MinOrMaxPhiR has users outside the reduction cycle in the loop. Check if
1594 // the only other user is a FindLastIV reduction. MinOrMaxPhiR must have
1595 // exactly 2 users:
1596 // 1) the min/max operation of the reduction cycle, and
1597 // 2) the compare of a FindLastIV reduction cycle. This compare must match
1598 // the min/max operation - comparing MinOrMaxPhiR with the operand of the
1599 // min/max operation, and be used only by the select of the FindLastIV
1600 // reduction cycle.
1601 RecurKind RdxKind = MinOrMaxPhiR->getRecurrenceKind();
1602 assert(
1603 RecurrenceDescriptor::isIntMinMaxRecurrenceKind(RdxKind) &&
1604 "only min/max recurrences support users outside the reduction chain");
1605
1606 auto *MinOrMaxOp =
1607 dyn_cast<VPRecipeWithIRFlags>(Val: MinOrMaxPhiR->getBackedgeValue());
1608 if (!MinOrMaxOp)
1609 return false;
1610
1611 // Check that MinOrMaxOp is a VPWidenIntrinsicRecipe or VPReplicateRecipe
1612 // with an intrinsic that matches the reduction kind.
1613 Intrinsic::ID ExpectedIntrinsicID = getMinMaxReductionIntrinsicOp(RK: RdxKind);
1614 if (!match(V: MinOrMaxOp, P: m_Intrinsic(IntrID: ExpectedIntrinsicID)))
1615 return false;
1616
1617 // MinOrMaxOp must have 2 users: 1) MinOrMaxPhiR and 2)
1618 // ComputeReductionResult.
1619 assert(MinOrMaxOp->getNumUsers() == 2 &&
1620 "MinOrMaxOp must have exactly 2 users");
1621 VPValue *MinOrMaxOpValue = MinOrMaxOp->getOperand(N: 0);
1622 if (MinOrMaxOpValue == MinOrMaxPhiR)
1623 MinOrMaxOpValue = MinOrMaxOp->getOperand(N: 1);
1624
1625 VPValue *CmpOpA;
1626 VPValue *CmpOpB;
1627 CmpPredicate Pred;
1628 auto *Cmp = dyn_cast_or_null<VPRecipeWithIRFlags>(Val: vputils::findUserOf(
1629 V: MinOrMaxPhiR, P: m_Cmp(Pred, Op0: m_VPValue(V&: CmpOpA), Op1: m_VPValue(V&: CmpOpB))));
1630 if (!Cmp || Cmp->getNumUsers() != 1 ||
1631 (CmpOpA != MinOrMaxOpValue && CmpOpB != MinOrMaxOpValue))
1632 return false;
1633
1634 if (MinOrMaxOpValue != CmpOpB)
1635 Pred = CmpInst::getSwappedPredicate(pred: Pred);
1636
1637 // MinOrMaxPhiR must have exactly 2 users:
1638 // * MinOrMaxOp,
1639 // * Cmp (that's part of a FindLastIV chain).
1640 if (MinOrMaxPhiR->getNumUsers() != 2)
1641 return false;
1642
1643 VPInstruction *MinOrMaxResult =
1644 vputils::findUserOf<VPInstruction::ComputeReductionResult>(V: MinOrMaxOp);
1645 assert(is_contained(MinOrMaxPhiR->users(), MinOrMaxOp) &&
1646 "one user must be MinOrMaxOp");
1647 assert(MinOrMaxResult && "MinOrMaxResult must be a user of MinOrMaxOp");
1648
1649 // Cmp must be used by the select of a FindLastIV chain.
1650 VPValue *Sel = dyn_cast<VPSingleDefRecipe>(Val: Cmp->getSingleUser());
1651 VPValue *IVOp, *FindIV;
1652 if (!Sel || Sel->getNumUsers() != 2 ||
1653 !match(V: Sel,
1654 P: m_Select(Op0: m_Specific(VPV: Cmp), Op1: m_VPValue(V&: IVOp), Op2: m_VPValue(V&: FindIV))))
1655 return false;
1656
1657 if (!isa<VPReductionPHIRecipe>(Val: FindIV)) {
1658 std::swap(a&: FindIV, b&: IVOp);
1659 Pred = CmpInst::getInversePredicate(pred: Pred);
1660 }
1661
1662 auto *FindIVPhiR = dyn_cast<VPReductionPHIRecipe>(Val: FindIV);
1663 if (!FindIVPhiR || !RecurrenceDescriptor::isFindIVRecurrenceKind(
1664 Kind: FindIVPhiR->getRecurrenceKind()))
1665 return false;
1666
1667 assert(!FindIVPhiR->isInLoop() && !FindIVPhiR->isOrdered() &&
1668 "cannot handle inloop/ordered reductions yet");
1669
1670 // Check if FindIVPhiR is a FindLast pattern by checking the MinMaxKind
1671 // on its ComputeReductionResult. SMax/UMax indicates FindLast.
1672 VPInstruction *FindIVResult =
1673 vputils::findUserOf<VPInstruction::ComputeReductionResult>(
1674 V: FindIVPhiR->getBackedgeValue());
1675 assert(FindIVResult &&
1676 "must be able to retrieve the FindIVResult VPInstruction");
1677 RecurKind FindIVMinMaxKind = FindIVResult->getRecurKind();
1678 if (FindIVMinMaxKind != RecurKind::SMax &&
1679 FindIVMinMaxKind != RecurKind::UMax)
1680 return false;
1681
1682 // TODO: Support cases where IVOp is the IV increment.
1683 if (!match(V: IVOp, P: m_TruncOrSelf(Op0: m_VPValue(V&: IVOp))) ||
1684 !isa<VPWidenIntOrFpInductionRecipe>(Val: IVOp))
1685 return false;
1686
1687 // Check if the predicate is compatible with the reduction kind.
1688 bool IsValidKindPred = [RdxKind, Pred]() {
1689 switch (RdxKind) {
1690 case RecurKind::UMin:
1691 return Pred == CmpInst::ICMP_UGE || Pred == CmpInst::ICMP_UGT;
1692 case RecurKind::UMax:
1693 return Pred == CmpInst::ICMP_ULE || Pred == CmpInst::ICMP_ULT;
1694 case RecurKind::SMax:
1695 return Pred == CmpInst::ICMP_SLE || Pred == CmpInst::ICMP_SLT;
1696 case RecurKind::SMin:
1697 return Pred == CmpInst::ICMP_SGE || Pred == CmpInst::ICMP_SGT;
1698 default:
1699 llvm_unreachable("unhandled recurrence kind");
1700 }
1701 }();
1702 if (!IsValidKindPred) {
1703 ORE->emit(RemarkBuilder: [&]() {
1704 return OptimizationRemarkMissed(
1705 DEBUG_TYPE, "VectorizationMultiUseReductionPredicate",
1706 TheLoop->getStartLoc(), TheLoop->getHeader())
1707 << "Multi-use reduction with predicate "
1708 << CmpInst::getPredicateName(P: Pred)
1709 << " incompatible with reduction kind";
1710 });
1711 return false;
1712 }
1713
1714 auto *FindIVSelect = findFindIVSelect(BackedgeVal: FindIVPhiR->getBackedgeValue());
1715 auto *FindIVCmp = FindIVSelect->getOperand(N: 0)->getDefiningRecipe();
1716 auto *FindIVRdxResult = cast<VPInstruction>(Val: FindIVCmp->getOperand(N: 0));
1717 assert(FindIVSelect->getParent() == MinOrMaxResult->getParent() &&
1718 "both results must be computed in the same block");
1719 // Reducing to a scalar min or max value is placed right before reducing to
1720 // its scalar iteration, in order to generate instructions that use both
1721 // their operands.
1722 MinOrMaxResult->moveBefore(BB&: *FindIVRdxResult->getParent(),
1723 I: FindIVRdxResult->getIterator());
1724
1725 bool IsStrictPredicate = ICmpInst::isLT(P: Pred) || ICmpInst::isGT(P: Pred);
1726 if (IsStrictPredicate) {
1727 return handleFirstArgMinOrMax(Plan, MinOrMaxPhiR, FindLastIVPhiR: FindIVPhiR,
1728 WideIV: cast<VPWidenIntOrFpInductionRecipe>(Val: IVOp),
1729 MinOrMaxResult, FindIVSelect, FindIVCmp,
1730 FindIVRdxResult);
1731 }
1732
1733 // The reduction using MinOrMaxPhiR needs adjusting to compute the correct
1734 // result:
1735 // 1. We need to find the last IV for which the condition based on the
1736 // min/max recurrence is true,
1737 // 2. Compare the partial min/max reduction result to its final value and,
1738 // 3. Select the lanes of the partial FindLastIV reductions which
1739 // correspond to the lanes matching the min/max reduction result.
1740 //
1741 // For example, this transforms
1742 // vp<%min.result> = compute-reduction-result ir<%min.val.next>
1743 // vp<%iv.rdx> = compute-reduction-result (smax) vp<%min.idx.next>
1744 // vp<%cmp> = icmp ne vp<%iv.rdx>, SENTINEL
1745 // vp<%find.iv.result> = select vp<%cmp>, vp<%iv.rdx>, ir<0>
1746 //
1747 // into:
1748 //
1749 // vp<min.result> = compute-reduction-result ir<%min.val.next>
1750 // vp<%final.min.cmp> = icmp eq ir<%min.val.next>, vp<min.result>
1751 // vp<%final.iv> = select vp<%final.min.cmp>, vp<%min.idx.next>, SENTINEL
1752 // vp<%iv.rdx> = compute-reduction-result (smax) vp<%final.iv>
1753 // vp<%cmp> = icmp ne vp<%iv.rdx>, SENTINEL
1754 // vp<%find.iv.result> = select vp<%cmp>, vp<%iv.rdx>, ir<0>
1755 //
1756 VPBuilder B(FindIVRdxResult);
1757 VPValue *MinOrMaxExiting = MinOrMaxResult->getOperand(N: 0);
1758 auto *FinalMinOrMaxCmp =
1759 B.createICmp(Pred: CmpInst::ICMP_EQ, A: MinOrMaxExiting, B: MinOrMaxResult);
1760 VPValue *Sentinel = FindIVCmp->getOperand(N: 1);
1761 VPValue *LastIVExiting = FindIVRdxResult->getOperand(N: 0);
1762 auto *FinalIVSelect =
1763 B.createSelect(Cond: FinalMinOrMaxCmp, TrueVal: LastIVExiting, FalseVal: Sentinel);
1764 FindIVRdxResult->setOperand(I: 0, New: FinalIVSelect);
1765 }
1766 return true;
1767}
1768