1//===-------- LoopIdiomVectorize.cpp - Loop idiom vectorization -----------===//
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// This pass implements a pass that recognizes certain loop idioms and
10// transforms them into more optimized versions of the same loop. In cases
11// where this happens, it can be a significant performance win.
12//
13// We currently support two loops:
14//
15// 1. A loop that finds the first mismatched byte in an array and returns the
16// index, i.e. something like:
17//
18// while (++i != n) {
19// if (a[i] != b[i])
20// break;
21// }
22//
23// In this example we can actually vectorize the loop despite the early exit,
24// although the loop vectorizer does not support it. It requires some extra
25// checks to deal with the possibility of faulting loads when crossing page
26// boundaries. However, even with these checks it is still profitable to do the
27// transformation.
28//
29// TODO List:
30//
31// * Add support for the inverse case where we scan for a matching element.
32// * Permit 64-bit induction variable types.
33// * Recognize loops that increment the IV *after* comparing bytes.
34// * Allow 32-bit sign-extends of the IV used by the GEP.
35//
36// 2. A loop that finds the first matching character in an array among a set of
37// possible matches, e.g.:
38//
39// for (; first != last; ++first)
40// for (s_it = s_first; s_it != s_last; ++s_it)
41// if (*first == *s_it)
42// return first;
43// return last;
44//
45// This corresponds to std::find_first_of (for arrays of bytes) from the C++
46// standard library. This function can be implemented efficiently for targets
47// that support @llvm.experimental.vector.match. For example, on AArch64 targets
48// that implement SVE2, this lower to a MATCH instruction, which enables us to
49// perform up to 16x16=256 comparisons in one go. This can lead to very
50// significant speedups.
51//
52// TODO:
53//
54// * Add support for `find_first_not_of' loops (i.e. with not-equal comparison).
55// * Make VF a configurable parameter (right now we assume 128-bit vectors).
56// * Potentially adjust the cost model to let the transformation kick-in even if
57// @llvm.experimental.vector.match doesn't have direct support in hardware.
58//
59//===----------------------------------------------------------------------===//
60//
61// NOTE: This Pass matches really specific loop patterns because it's only
62// supposed to be a temporary solution until our LoopVectorizer is powerful
63// enough to vectorize them automatically.
64//
65//===----------------------------------------------------------------------===//
66
67#include "llvm/Transforms/Vectorize/LoopIdiomVectorize.h"
68#include "VectorizeOptions.h"
69#include "llvm/Analysis/DomTreeUpdater.h"
70#include "llvm/Analysis/LoopPass.h"
71#include "llvm/Analysis/OptimizationRemarkEmitter.h"
72#include "llvm/Analysis/TargetTransformInfo.h"
73#include "llvm/IR/Dominators.h"
74#include "llvm/IR/IRBuilder.h"
75#include "llvm/IR/Intrinsics.h"
76#include "llvm/IR/MDBuilder.h"
77#include "llvm/IR/PatternMatch.h"
78#include "llvm/Transforms/Utils/BasicBlockUtils.h"
79#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
80
81using namespace llvm;
82using namespace PatternMatch;
83
84#define DEBUG_TYPE "loop-idiom-vectorize"
85
86namespace {
87class LoopIdiomVectorize {
88 const VectorizeOptions &Opts;
89 LoopIdiomVectorizeStyle VectorizeStyle;
90 unsigned ByteCompareVF;
91 Loop *CurLoop = nullptr;
92 DominatorTree *DT;
93 LoopInfo *LI;
94 const TargetTransformInfo *TTI;
95
96 /// Interface to emit optimization remarks.
97 OptimizationRemarkEmitter &ORE;
98
99 // Blocks that will be used for inserting vectorized code.
100 BasicBlock *EndBlock = nullptr;
101 BasicBlock *VectorLoopPreheaderBlock = nullptr;
102 BasicBlock *VectorLoopStartBlock = nullptr;
103 BasicBlock *VectorLoopMismatchBlock = nullptr;
104 BasicBlock *VectorLoopIncBlock = nullptr;
105
106public:
107 LoopIdiomVectorize(const VectorizeOptions &Opts, LoopIdiomVectorizeStyle S,
108 unsigned VF, DominatorTree *DT, LoopInfo *LI,
109 const TargetTransformInfo *TTI,
110 OptimizationRemarkEmitter &ORE)
111 : Opts(Opts), VectorizeStyle(S), ByteCompareVF(VF), DT(DT), LI(LI),
112 TTI(TTI), ORE(ORE) {}
113
114 bool run(Loop *L);
115
116private:
117 /// \name Countable Loop Idiom Handling
118 /// @{
119
120 bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
121 SmallVectorImpl<BasicBlock *> &ExitBlocks);
122
123 bool recognizeByteCompare();
124
125 Value *expandFindMismatch(IRBuilder<> &Builder, DomTreeUpdater &DTU,
126 GetElementPtrInst *GEPA, GetElementPtrInst *GEPB,
127 Instruction *Index, Value *Start, Value *MaxLen);
128
129 Value *createMaskedFindMismatch(IRBuilder<> &Builder, DomTreeUpdater &DTU,
130 GetElementPtrInst *GEPA,
131 GetElementPtrInst *GEPB, Value *ExtStart,
132 Value *ExtEnd);
133 Value *createPredicatedFindMismatch(IRBuilder<> &Builder, DomTreeUpdater &DTU,
134 GetElementPtrInst *GEPA,
135 GetElementPtrInst *GEPB, Value *ExtStart,
136 Value *ExtEnd);
137
138 void transformByteCompare(GetElementPtrInst *GEPA, GetElementPtrInst *GEPB,
139 PHINode *IndPhi, Value *MaxLen, Instruction *Index,
140 Value *Start, bool IncIdx, BasicBlock *FoundBB,
141 BasicBlock *EndBB);
142
143 bool recognizeFindFirstByte();
144
145 Value *expandFindFirstByte(IRBuilder<> &Builder, DomTreeUpdater &DTU,
146 unsigned VF, Type *CharTy, Value *IndPhi,
147 BasicBlock *ExitSucc, BasicBlock *ExitFail,
148 Value *SearchStart, Value *SearchEnd,
149 Value *NeedleStart, Value *NeedleEnd);
150
151 void transformFindFirstByte(PHINode *IndPhi, unsigned VF, Type *CharTy,
152 BasicBlock *ExitSucc, BasicBlock *ExitFail,
153 Value *SearchStart, Value *SearchEnd,
154 Value *NeedleStart, Value *NeedleEnd);
155 /// @}
156};
157} // anonymous namespace
158
159PreservedAnalyses LoopIdiomVectorizePass::run(Loop &L, LoopAnalysisManager &AM,
160 LoopStandardAnalysisResults &AR,
161 LPMUpdater &) {
162 const VectorizeOptions &Opts = getVectorizeOptions(L);
163 if (Opts.disable_loop_idiom_vectorize_all)
164 return PreservedAnalyses::all();
165
166 LoopIdiomVectorizeStyle VecStyle =
167 Opts.loop_idiom_vectorize_style.value_or(u&: VectorizeStyle);
168 unsigned BCVF = Opts.loop_idiom_vectorize_bytecmp_vf.value_or(u&: ByteCompareVF);
169
170 Function &F = *L.getHeader()->getParent();
171 auto &FAMP = AM.getResult<FunctionAnalysisManagerLoopProxy>(IR&: L, ExtraArgs&: AR);
172 auto *ORE = FAMP.getCachedResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
173
174 std::optional<OptimizationRemarkEmitter> ORELocal;
175 if (!ORE) {
176 ORELocal.emplace(args: &F);
177 ORE = &*ORELocal;
178 }
179
180 LoopIdiomVectorize LIV(Opts, VecStyle, BCVF, &AR.DT, &AR.LI, &AR.TTI, *ORE);
181 if (!LIV.run(L: &L))
182 return PreservedAnalyses::all();
183
184 return PreservedAnalyses::none();
185}
186
187//===----------------------------------------------------------------------===//
188//
189// Implementation of LoopIdiomVectorize
190//
191//===----------------------------------------------------------------------===//
192
193bool LoopIdiomVectorize::run(Loop *L) {
194 CurLoop = L;
195
196 Function &F = *L->getHeader()->getParent();
197 if (Opts.disable_loop_idiom_vectorize_all || F.hasOptSize())
198 return false;
199
200 // Bail if vectorization is disabled on loop.
201 LoopVectorizeHints Hints(Opts, L, /*InterleaveOnlyWhenForced=*/true, ORE);
202 if (!Hints.allowVectorization(L, /*VectorizeOnlyWhenForced=*/false)) {
203 LLVM_DEBUG(dbgs() << DEBUG_TYPE << " is disabled on " << L->getName()
204 << " due to vectorization hints\n");
205 return false;
206 }
207
208 if (F.hasFnAttribute(Kind: Attribute::NoImplicitFloat)) {
209 LLVM_DEBUG(dbgs() << DEBUG_TYPE << " is disabled on " << F.getName()
210 << " due to its NoImplicitFloat attribute");
211 return false;
212 }
213
214 // If the loop could not be converted to canonical form, it must have an
215 // indirectbr in it, just give up.
216 if (!L->getLoopPreheader())
217 return false;
218
219 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F[" << F.getName() << "] Loop %"
220 << CurLoop->getHeader()->getName() << "\n");
221
222 if (recognizeByteCompare())
223 return true;
224
225 if (recognizeFindFirstByte())
226 return true;
227
228 return false;
229}
230
231static void fixSuccessorPhis(Loop *L, Value *ScalarRes, Value *VectorRes,
232 BasicBlock *SuccBB, BasicBlock *IncBB) {
233 for (PHINode &PN : SuccBB->phis()) {
234 // Look through the incoming values to find ScalarRes, meaning this is a
235 // PHI collecting the results of the transformation.
236 bool ResPhi = false;
237 for (Value *Op : PN.incoming_values())
238 if (Op == ScalarRes) {
239 ResPhi = true;
240 break;
241 }
242
243 // Any PHI that depended upon the result of the transformation needs a new
244 // incoming value from IncBB.
245 if (ResPhi)
246 PN.addIncoming(V: VectorRes, BB: IncBB);
247 else {
248 // There should be no other outside uses of other values in the
249 // original loop. Any incoming values should either:
250 // 1. Be for blocks outside the loop, which aren't interesting. Or ..
251 // 2. These are from blocks in the loop with values defined outside
252 // the loop. We should a similar incoming value from CmpBB.
253 for (BasicBlock *BB : PN.blocks())
254 if (L->contains(BB)) {
255 PN.addIncoming(V: PN.getIncomingValueForBlock(BB), BB: IncBB);
256 break;
257 }
258 }
259 }
260}
261
262bool LoopIdiomVectorize::recognizeByteCompare() {
263 // Currently the transformation only works on scalable vector types, although
264 // there is no fundamental reason why it cannot be made to work for fixed
265 // width too.
266
267 // We also need to know the minimum page size for the target in order to
268 // generate runtime memory checks to ensure the vector version won't fault.
269 if (!TTI->supportsScalableVectors() || !TTI->getMinPageSize().has_value() ||
270 Opts.disable_loop_idiom_vectorize_bytecmp)
271 return false;
272
273 BasicBlock *Header = CurLoop->getHeader();
274
275 // In LoopIdiomVectorize::run we have already checked that the loop
276 // has a preheader so we can assume it's in a canonical form.
277 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 2)
278 return false;
279
280 PHINode *PN = dyn_cast<PHINode>(Val: &Header->front());
281 if (!PN || PN->getNumIncomingValues() != 2)
282 return false;
283
284 auto LoopBlocks = CurLoop->getBlocks();
285 // The first block in the loop should contain only 4 instructions, e.g.
286 //
287 // while.cond:
288 // %res.phi = phi i32 [ %start, %ph ], [ %inc, %while.body ]
289 // %inc = add i32 %res.phi, 1
290 // %cmp.not = icmp eq i32 %inc, %n
291 // br i1 %cmp.not, label %while.end, label %while.body
292 //
293 if (LoopBlocks[0]->size() > 4)
294 return false;
295
296 // The second block should contain 7 instructions, e.g.
297 //
298 // while.body:
299 // %idx = zext i32 %inc to i64
300 // %idx.a = getelementptr inbounds i8, ptr %a, i64 %idx
301 // %load.a = load i8, ptr %idx.a
302 // %idx.b = getelementptr inbounds i8, ptr %b, i64 %idx
303 // %load.b = load i8, ptr %idx.b
304 // %cmp.not.ld = icmp eq i8 %load.a, %load.b
305 // br i1 %cmp.not.ld, label %while.cond, label %while.end
306 //
307 if (LoopBlocks[1]->size() > 7)
308 return false;
309
310 // The incoming value to the PHI node from the loop should be an add of 1.
311 Value *StartIdx = nullptr;
312 Instruction *Index = nullptr;
313 if (!CurLoop->contains(BB: PN->getIncomingBlock(i: 0))) {
314 StartIdx = PN->getIncomingValue(i: 0);
315 Index = dyn_cast<Instruction>(Val: PN->getIncomingValue(i: 1));
316 } else {
317 StartIdx = PN->getIncomingValue(i: 1);
318 Index = dyn_cast<Instruction>(Val: PN->getIncomingValue(i: 0));
319 }
320
321 // Limit to 32-bit types for now
322 if (!Index || !Index->getType()->isIntegerTy(BitWidth: 32) ||
323 !match(V: Index, P: m_c_Add(L: m_Specific(V: PN), R: m_One())))
324 return false;
325
326 // If we match the pattern, PN and Index will be replaced with the result of
327 // the cttz.elts intrinsic. If any other instructions are used outside of
328 // the loop, we cannot replace it.
329 for (BasicBlock *BB : LoopBlocks)
330 for (Instruction &I : *BB)
331 if (&I != PN && &I != Index)
332 for (User *U : I.users())
333 if (!CurLoop->contains(Inst: cast<Instruction>(Val: U)))
334 return false;
335
336 // Match the branch instruction for the header
337 Value *MaxLen;
338 BasicBlock *EndBB, *WhileBB;
339 if (!match(V: Header->getTerminator(),
340 P: m_Br(C: m_SpecificICmp(MatchPred: ICmpInst::ICMP_EQ, L: m_Specific(V: Index),
341 R: m_Value(V&: MaxLen)),
342 T: m_BasicBlock(V&: EndBB), F: m_BasicBlock(V&: WhileBB))) ||
343 !CurLoop->contains(BB: WhileBB))
344 return false;
345
346 // WhileBB should contain the pattern of load & compare instructions. Match
347 // the pattern and find the GEP instructions used by the loads.
348 BasicBlock *FoundBB;
349 BasicBlock *TrueBB;
350 Value *LoadA, *LoadB;
351 if (!match(V: WhileBB->getTerminator(),
352 P: m_Br(C: m_SpecificICmp(MatchPred: ICmpInst::ICMP_EQ, L: m_Value(V&: LoadA),
353 R: m_Value(V&: LoadB)),
354 T: m_BasicBlock(V&: TrueBB), F: m_BasicBlock(V&: FoundBB))) ||
355 !CurLoop->contains(BB: TrueBB))
356 return false;
357
358 Value *A, *B;
359 if (!match(V: LoadA, P: m_Load(Op: m_Value(V&: A))) || !match(V: LoadB, P: m_Load(Op: m_Value(V&: B))))
360 return false;
361
362 LoadInst *LoadAI = cast<LoadInst>(Val: LoadA);
363 LoadInst *LoadBI = cast<LoadInst>(Val: LoadB);
364 if (!LoadAI->isSimple() || !LoadBI->isSimple())
365 return false;
366
367 GetElementPtrInst *GEPA = dyn_cast<GetElementPtrInst>(Val: A);
368 GetElementPtrInst *GEPB = dyn_cast<GetElementPtrInst>(Val: B);
369
370 if (!GEPA || !GEPB)
371 return false;
372
373 Value *PtrA = GEPA->getPointerOperand();
374 Value *PtrB = GEPB->getPointerOperand();
375
376 // Check we are loading i8 values from two loop invariant pointers
377 if (!CurLoop->isLoopInvariant(V: PtrA) || !CurLoop->isLoopInvariant(V: PtrB) ||
378 !GEPA->getResultElementType()->isIntegerTy(BitWidth: 8) ||
379 !GEPB->getResultElementType()->isIntegerTy(BitWidth: 8) ||
380 !LoadAI->getType()->isIntegerTy(BitWidth: 8) ||
381 !LoadBI->getType()->isIntegerTy(BitWidth: 8) || PtrA == PtrB)
382 return false;
383
384 // Check that the index to the GEPs is the index we found earlier
385 if (GEPA->getNumIndices() > 1 || GEPB->getNumIndices() > 1)
386 return false;
387
388 Value *IdxA = GEPA->getOperand(i_nocapture: GEPA->getNumIndices());
389 Value *IdxB = GEPB->getOperand(i_nocapture: GEPB->getNumIndices());
390 if (IdxA != IdxB || !match(V: IdxA, P: m_ZExt(Op: m_Specific(V: Index))))
391 return false;
392
393 // We only ever expect the pre-incremented index value to be used inside the
394 // loop.
395 if (!PN->hasOneUse())
396 return false;
397
398 // Ensure that when the Found and End blocks are identical the PHIs have the
399 // supported format. We don't currently allow cases like this:
400 // while.cond:
401 // ...
402 // br i1 %cmp.not, label %while.end, label %while.body
403 //
404 // while.body:
405 // ...
406 // br i1 %cmp.not2, label %while.cond, label %while.end
407 //
408 // while.end:
409 // %final_ptr = phi ptr [ %c, %while.body ], [ %d, %while.cond ]
410 //
411 // Where the incoming values for %final_ptr are unique and from each of the
412 // loop blocks, but not actually defined in the loop. This requires extra
413 // work setting up the byte.compare block, i.e. by introducing a select to
414 // choose the correct value.
415 // TODO: We could add support for this in future.
416 if (FoundBB == EndBB) {
417 for (PHINode &EndPN : EndBB->phis()) {
418 Value *WhileCondVal = EndPN.getIncomingValueForBlock(BB: Header);
419 Value *WhileBodyVal = EndPN.getIncomingValueForBlock(BB: WhileBB);
420
421 // The value of the index when leaving the while.cond block is always the
422 // same as the end value (MaxLen) so we permit either. The value when
423 // leaving the while.body block should only be the index. Otherwise for
424 // any other values we only allow ones that are same for both blocks.
425 if (WhileCondVal != WhileBodyVal &&
426 ((WhileCondVal != Index && WhileCondVal != MaxLen) ||
427 (WhileBodyVal != Index)))
428 return false;
429 }
430 }
431
432 LLVM_DEBUG(dbgs() << "FOUND IDIOM IN LOOP: \n"
433 << *(EndBB->getParent()) << "\n\n");
434
435 // The index is incremented before the GEP/Load pair so we need to
436 // add 1 to the start value.
437 transformByteCompare(GEPA, GEPB, IndPhi: PN, MaxLen, Index, Start: StartIdx, /*IncIdx=*/true,
438 FoundBB, EndBB);
439 return true;
440}
441
442Value *LoopIdiomVectorize::createMaskedFindMismatch(
443 IRBuilder<> &Builder, DomTreeUpdater &DTU, GetElementPtrInst *GEPA,
444 GetElementPtrInst *GEPB, Value *ExtStart, Value *ExtEnd) {
445 Type *I64Type = Builder.getInt64Ty();
446 Type *ResType = Builder.getInt32Ty();
447 Type *LoadType = Builder.getInt8Ty();
448 Value *PtrA = GEPA->getPointerOperand();
449 Value *PtrB = GEPB->getPointerOperand();
450
451 ScalableVectorType *PredVTy =
452 ScalableVectorType::get(ElementType: Builder.getInt1Ty(), MinNumElts: ByteCompareVF);
453
454 Value *InitialPred = Builder.CreateIntrinsic(
455 ID: Intrinsic::get_active_lane_mask, OverloadTypes: {PredVTy, I64Type}, Args: {ExtStart, ExtEnd});
456
457 Value *VecLen = Builder.CreateVScale(Ty: I64Type);
458 VecLen =
459 Builder.CreateMul(LHS: VecLen, RHS: ConstantInt::get(Ty: I64Type, V: ByteCompareVF), Name: "",
460 /*HasNUW=*/true, /*HasNSW=*/true);
461
462 Value *PFalse = Builder.CreateVectorSplat(EC: PredVTy->getElementCount(),
463 V: Builder.getInt1(V: false));
464
465 Builder.CreateBr(Dest: VectorLoopStartBlock);
466
467 DTU.applyUpdates(Updates: {{DominatorTree::Insert, VectorLoopPreheaderBlock,
468 VectorLoopStartBlock}});
469
470 // Set up the first vector loop block by creating the PHIs, doing the vector
471 // loads and comparing the vectors.
472 Builder.SetInsertPoint(VectorLoopStartBlock);
473 PHINode *LoopPred = Builder.CreatePHI(Ty: PredVTy, NumReservedValues: 2, Name: "mismatch_vec_loop_pred");
474 LoopPred->addIncoming(V: InitialPred, BB: VectorLoopPreheaderBlock);
475 PHINode *VectorIndexPhi = Builder.CreatePHI(Ty: I64Type, NumReservedValues: 2, Name: "mismatch_vec_index");
476 VectorIndexPhi->addIncoming(V: ExtStart, BB: VectorLoopPreheaderBlock);
477 Type *VectorLoadType =
478 ScalableVectorType::get(ElementType: Builder.getInt8Ty(), MinNumElts: ByteCompareVF);
479 Value *Passthru = ConstantInt::getNullValue(Ty: VectorLoadType);
480
481 Value *VectorLhsGep =
482 Builder.CreateGEP(Ty: LoadType, Ptr: PtrA, IdxList: VectorIndexPhi, Name: "", NW: GEPA->isInBounds());
483 Value *VectorLhsLoad = Builder.CreateMaskedLoad(Ty: VectorLoadType, Ptr: VectorLhsGep,
484 Alignment: Align(1), Mask: LoopPred, PassThru: Passthru);
485
486 Value *VectorRhsGep =
487 Builder.CreateGEP(Ty: LoadType, Ptr: PtrB, IdxList: VectorIndexPhi, Name: "", NW: GEPB->isInBounds());
488 Value *VectorRhsLoad = Builder.CreateMaskedLoad(Ty: VectorLoadType, Ptr: VectorRhsGep,
489 Alignment: Align(1), Mask: LoopPred, PassThru: Passthru);
490
491 Value *VectorMatchCmp = Builder.CreateICmpNE(LHS: VectorLhsLoad, RHS: VectorRhsLoad);
492 VectorMatchCmp = Builder.CreateSelect(C: LoopPred, True: VectorMatchCmp, False: PFalse);
493 Value *VectorMatchHasActiveLanes = Builder.CreateOrReduce(Src: VectorMatchCmp);
494 Builder.CreateCondBr(Cond: VectorMatchHasActiveLanes, True: VectorLoopMismatchBlock,
495 False: VectorLoopIncBlock);
496
497 DTU.applyUpdates(
498 Updates: {{DominatorTree::Insert, VectorLoopStartBlock, VectorLoopMismatchBlock},
499 {DominatorTree::Insert, VectorLoopStartBlock, VectorLoopIncBlock}});
500
501 // Increment the index counter and calculate the predicate for the next
502 // iteration of the loop. We branch back to the start of the loop if there
503 // is at least one active lane.
504 Builder.SetInsertPoint(VectorLoopIncBlock);
505 Value *NewVectorIndexPhi =
506 Builder.CreateAdd(LHS: VectorIndexPhi, RHS: VecLen, Name: "",
507 /*HasNUW=*/true, /*HasNSW=*/true);
508 VectorIndexPhi->addIncoming(V: NewVectorIndexPhi, BB: VectorLoopIncBlock);
509 Value *NewPred =
510 Builder.CreateIntrinsic(ID: Intrinsic::get_active_lane_mask,
511 OverloadTypes: {PredVTy, I64Type}, Args: {NewVectorIndexPhi, ExtEnd});
512 LoopPred->addIncoming(V: NewPred, BB: VectorLoopIncBlock);
513
514 Value *PredHasActiveLanes =
515 Builder.CreateExtractElement(Vec: NewPred, Idx: uint64_t(0));
516 Builder.CreateCondBr(Cond: PredHasActiveLanes, True: VectorLoopStartBlock, False: EndBlock);
517
518 DTU.applyUpdates(
519 Updates: {{DominatorTree::Insert, VectorLoopIncBlock, VectorLoopStartBlock},
520 {DominatorTree::Insert, VectorLoopIncBlock, EndBlock}});
521
522 // If we found a mismatch then we need to calculate which lane in the vector
523 // had a mismatch and add that on to the current loop index.
524 Builder.SetInsertPoint(VectorLoopMismatchBlock);
525 PHINode *FoundPred = Builder.CreatePHI(Ty: PredVTy, NumReservedValues: 1, Name: "mismatch_vec_found_pred");
526 FoundPred->addIncoming(V: VectorMatchCmp, BB: VectorLoopStartBlock);
527 PHINode *LastLoopPred =
528 Builder.CreatePHI(Ty: PredVTy, NumReservedValues: 1, Name: "mismatch_vec_last_loop_pred");
529 LastLoopPred->addIncoming(V: LoopPred, BB: VectorLoopStartBlock);
530 PHINode *VectorFoundIndex =
531 Builder.CreatePHI(Ty: I64Type, NumReservedValues: 1, Name: "mismatch_vec_found_index");
532 VectorFoundIndex->addIncoming(V: VectorIndexPhi, BB: VectorLoopStartBlock);
533
534 Value *PredMatchCmp = Builder.CreateAnd(LHS: LastLoopPred, RHS: FoundPred);
535 Value *Ctz = Builder.CreateCountTrailingZeroElems(ResTy: ResType, Mask: PredMatchCmp);
536 Ctz = Builder.CreateZExt(V: Ctz, DestTy: I64Type);
537 Value *VectorLoopRes64 = Builder.CreateAdd(LHS: VectorFoundIndex, RHS: Ctz, Name: "",
538 /*HasNUW=*/true, /*HasNSW=*/true);
539 return Builder.CreateTrunc(V: VectorLoopRes64, DestTy: ResType);
540}
541
542Value *LoopIdiomVectorize::createPredicatedFindMismatch(
543 IRBuilder<> &Builder, DomTreeUpdater &DTU, GetElementPtrInst *GEPA,
544 GetElementPtrInst *GEPB, Value *ExtStart, Value *ExtEnd) {
545 Type *I64Type = Builder.getInt64Ty();
546 Type *I32Type = Builder.getInt32Ty();
547 Type *ResType = I32Type;
548 Type *LoadType = Builder.getInt8Ty();
549 Value *PtrA = GEPA->getPointerOperand();
550 Value *PtrB = GEPB->getPointerOperand();
551
552 auto *JumpToVectorLoop = UncondBrInst::Create(Target: VectorLoopStartBlock);
553 Builder.Insert(I: JumpToVectorLoop);
554
555 DTU.applyUpdates(Updates: {{DominatorTree::Insert, VectorLoopPreheaderBlock,
556 VectorLoopStartBlock}});
557
558 // Set up the first Vector loop block by creating the PHIs, doing the vector
559 // loads and comparing the vectors.
560 Builder.SetInsertPoint(VectorLoopStartBlock);
561 auto *VectorIndexPhi = Builder.CreatePHI(Ty: I64Type, NumReservedValues: 2, Name: "mismatch_vector_index");
562 VectorIndexPhi->addIncoming(V: ExtStart, BB: VectorLoopPreheaderBlock);
563
564 // Calculate AVL by subtracting the vector loop index from the trip count
565 Value *AVL = Builder.CreateSub(LHS: ExtEnd, RHS: VectorIndexPhi, Name: "avl", /*HasNUW=*/true,
566 /*HasNSW=*/true);
567
568 auto *VectorLoadType = ScalableVectorType::get(ElementType: LoadType, MinNumElts: ByteCompareVF);
569 auto *VF = ConstantInt::get(Ty: I32Type, V: ByteCompareVF);
570
571 Value *VL = Builder.CreateIntrinsic(ID: Intrinsic::experimental_get_vector_length,
572 OverloadTypes: {I64Type}, Args: {AVL, VF, Builder.getTrue()});
573 Value *GepOffset = VectorIndexPhi;
574
575 Value *VectorLhsGep =
576 Builder.CreateGEP(Ty: LoadType, Ptr: PtrA, IdxList: GepOffset, Name: "", NW: GEPA->isInBounds());
577 VectorType *TrueMaskTy =
578 VectorType::get(ElementType: Builder.getInt1Ty(), EC: VectorLoadType->getElementCount());
579 Value *AllTrueMask = Constant::getAllOnesValue(Ty: TrueMaskTy);
580 Value *VectorLhsLoad = Builder.CreateIntrinsic(
581 ID: Intrinsic::vp_load, OverloadTypes: {VectorLoadType, VectorLhsGep->getType()},
582 Args: {VectorLhsGep, AllTrueMask, VL}, FMFSource: nullptr, Name: "lhs.load");
583
584 Value *VectorRhsGep =
585 Builder.CreateGEP(Ty: LoadType, Ptr: PtrB, IdxList: GepOffset, Name: "", NW: GEPB->isInBounds());
586 Value *VectorRhsLoad = Builder.CreateIntrinsic(
587 ID: Intrinsic::vp_load, OverloadTypes: {VectorLoadType, VectorLhsGep->getType()},
588 Args: {VectorRhsGep, AllTrueMask, VL}, FMFSource: nullptr, Name: "rhs.load");
589
590 Value *VectorMatchCmp =
591 Builder.CreateICmpNE(LHS: VectorLhsLoad, RHS: VectorRhsLoad, Name: "mismatch.cmp");
592 Value *CTZ = Builder.CreateIntrinsic(
593 ID: Intrinsic::vp_cttz_elts, OverloadTypes: {ResType, VectorMatchCmp->getType()},
594 Args: {VectorMatchCmp, /*ZeroIsPoison=*/Builder.getInt1(V: false), AllTrueMask,
595 VL});
596 Value *MismatchFound = Builder.CreateICmpNE(LHS: CTZ, RHS: VL);
597 auto *VectorEarlyExit = CondBrInst::Create(
598 Cond: MismatchFound, IfTrue: VectorLoopMismatchBlock, IfFalse: VectorLoopIncBlock);
599 Builder.Insert(I: VectorEarlyExit);
600
601 DTU.applyUpdates(
602 Updates: {{DominatorTree::Insert, VectorLoopStartBlock, VectorLoopMismatchBlock},
603 {DominatorTree::Insert, VectorLoopStartBlock, VectorLoopIncBlock}});
604
605 // Increment the index counter and calculate the predicate for the next
606 // iteration of the loop. We branch back to the start of the loop if there
607 // is at least one active lane.
608 Builder.SetInsertPoint(VectorLoopIncBlock);
609 Value *VL64 = Builder.CreateZExt(V: VL, DestTy: I64Type);
610 Value *NewVectorIndexPhi =
611 Builder.CreateAdd(LHS: VectorIndexPhi, RHS: VL64, Name: "",
612 /*HasNUW=*/true, /*HasNSW=*/true);
613 VectorIndexPhi->addIncoming(V: NewVectorIndexPhi, BB: VectorLoopIncBlock);
614 Value *ExitCond = Builder.CreateICmpNE(LHS: NewVectorIndexPhi, RHS: ExtEnd);
615 auto *VectorLoopBranchBack =
616 CondBrInst::Create(Cond: ExitCond, IfTrue: VectorLoopStartBlock, IfFalse: EndBlock);
617 Builder.Insert(I: VectorLoopBranchBack);
618
619 DTU.applyUpdates(
620 Updates: {{DominatorTree::Insert, VectorLoopIncBlock, VectorLoopStartBlock},
621 {DominatorTree::Insert, VectorLoopIncBlock, EndBlock}});
622
623 // If we found a mismatch then we need to calculate which lane in the vector
624 // had a mismatch and add that on to the current loop index.
625 Builder.SetInsertPoint(VectorLoopMismatchBlock);
626
627 // Add LCSSA phis for CTZ and VectorIndexPhi.
628 auto *CTZLCSSAPhi = Builder.CreatePHI(Ty: CTZ->getType(), NumReservedValues: 1, Name: "ctz");
629 CTZLCSSAPhi->addIncoming(V: CTZ, BB: VectorLoopStartBlock);
630 auto *VectorIndexLCSSAPhi =
631 Builder.CreatePHI(Ty: VectorIndexPhi->getType(), NumReservedValues: 1, Name: "mismatch_vector_index");
632 VectorIndexLCSSAPhi->addIncoming(V: VectorIndexPhi, BB: VectorLoopStartBlock);
633
634 Value *CTZI64 = Builder.CreateZExt(V: CTZLCSSAPhi, DestTy: I64Type);
635 Value *VectorLoopRes64 = Builder.CreateAdd(LHS: VectorIndexLCSSAPhi, RHS: CTZI64, Name: "",
636 /*HasNUW=*/true, /*HasNSW=*/true);
637 return Builder.CreateTrunc(V: VectorLoopRes64, DestTy: ResType);
638}
639
640Value *LoopIdiomVectorize::expandFindMismatch(
641 IRBuilder<> &Builder, DomTreeUpdater &DTU, GetElementPtrInst *GEPA,
642 GetElementPtrInst *GEPB, Instruction *Index, Value *Start, Value *MaxLen) {
643 Value *PtrA = GEPA->getPointerOperand();
644 Value *PtrB = GEPB->getPointerOperand();
645
646 // Get the arguments and types for the intrinsic.
647 BasicBlock *Preheader = CurLoop->getLoopPreheader();
648 Instruction *PHBranch = Preheader->getTerminator();
649 LLVMContext &Ctx = PHBranch->getContext();
650 Type *LoadType = Type::getInt8Ty(C&: Ctx);
651 Type *ResType = Builder.getInt32Ty();
652
653 // Split block in the original loop preheader.
654 EndBlock = SplitBlock(Old: Preheader, SplitPt: PHBranch, DT, LI, MSSAU: nullptr, BBName: "mismatch_end");
655
656 // Create the blocks that we're going to need:
657 // 1. A block for checking the zero-extended length exceeds 0
658 // 2. A block to check that the start and end addresses of a given array
659 // lie on the same page.
660 // 3. The vector loop preheader.
661 // 4. The first vector loop block.
662 // 5. The vector loop increment block.
663 // 6. A block we can jump to from the vector loop when a mismatch is found.
664 // 7. The first block of the scalar loop itself, containing PHIs , loads
665 // and cmp.
666 // 8. A scalar loop increment block to increment the PHIs and go back
667 // around the loop.
668
669 BasicBlock *MinItCheckBlock = BasicBlock::Create(
670 Context&: Ctx, Name: "mismatch_min_it_check", Parent: EndBlock->getParent(), InsertBefore: EndBlock);
671
672 // Update the terminator added by SplitBlock to branch to the first block
673 Preheader->getTerminator()->setSuccessor(Idx: 0, BB: MinItCheckBlock);
674
675 BasicBlock *MemCheckBlock = BasicBlock::Create(
676 Context&: Ctx, Name: "mismatch_mem_check", Parent: EndBlock->getParent(), InsertBefore: EndBlock);
677
678 VectorLoopPreheaderBlock = BasicBlock::Create(
679 Context&: Ctx, Name: "mismatch_vec_loop_preheader", Parent: EndBlock->getParent(), InsertBefore: EndBlock);
680
681 VectorLoopStartBlock = BasicBlock::Create(Context&: Ctx, Name: "mismatch_vec_loop",
682 Parent: EndBlock->getParent(), InsertBefore: EndBlock);
683
684 VectorLoopIncBlock = BasicBlock::Create(Context&: Ctx, Name: "mismatch_vec_loop_inc",
685 Parent: EndBlock->getParent(), InsertBefore: EndBlock);
686
687 VectorLoopMismatchBlock = BasicBlock::Create(Context&: Ctx, Name: "mismatch_vec_loop_found",
688 Parent: EndBlock->getParent(), InsertBefore: EndBlock);
689
690 BasicBlock *LoopPreHeaderBlock = BasicBlock::Create(
691 Context&: Ctx, Name: "mismatch_loop_pre", Parent: EndBlock->getParent(), InsertBefore: EndBlock);
692
693 BasicBlock *LoopStartBlock =
694 BasicBlock::Create(Context&: Ctx, Name: "mismatch_loop", Parent: EndBlock->getParent(), InsertBefore: EndBlock);
695
696 BasicBlock *LoopIncBlock = BasicBlock::Create(
697 Context&: Ctx, Name: "mismatch_loop_inc", Parent: EndBlock->getParent(), InsertBefore: EndBlock);
698
699 DTU.applyUpdates(Updates: {{DominatorTree::Insert, Preheader, MinItCheckBlock},
700 {DominatorTree::Delete, Preheader, EndBlock}});
701
702 // Update LoopInfo with the new vector & scalar loops.
703 auto VectorLoop = LI->AllocateLoop();
704 auto ScalarLoop = LI->AllocateLoop();
705
706 if (CurLoop->getParentLoop()) {
707 CurLoop->getParentLoop()->addBasicBlockToLoop(NewBB: MinItCheckBlock, LI&: *LI);
708 CurLoop->getParentLoop()->addBasicBlockToLoop(NewBB: MemCheckBlock, LI&: *LI);
709 CurLoop->getParentLoop()->addBasicBlockToLoop(NewBB: VectorLoopPreheaderBlock,
710 LI&: *LI);
711 CurLoop->getParentLoop()->addChildLoop(NewChild: VectorLoop);
712 CurLoop->getParentLoop()->addBasicBlockToLoop(NewBB: VectorLoopMismatchBlock, LI&: *LI);
713 CurLoop->getParentLoop()->addBasicBlockToLoop(NewBB: LoopPreHeaderBlock, LI&: *LI);
714 CurLoop->getParentLoop()->addChildLoop(NewChild: ScalarLoop);
715 } else {
716 LI->addTopLevelLoop(New: VectorLoop);
717 LI->addTopLevelLoop(New: ScalarLoop);
718 }
719
720 // Add the new basic blocks to their associated loops.
721 VectorLoop->addBasicBlockToLoop(NewBB: VectorLoopStartBlock, LI&: *LI);
722 VectorLoop->addBasicBlockToLoop(NewBB: VectorLoopIncBlock, LI&: *LI);
723
724 ScalarLoop->addBasicBlockToLoop(NewBB: LoopStartBlock, LI&: *LI);
725 ScalarLoop->addBasicBlockToLoop(NewBB: LoopIncBlock, LI&: *LI);
726
727 // Set up some types and constants that we intend to reuse.
728 Type *I64Type = Builder.getInt64Ty();
729
730 // Check the zero-extended iteration count > 0
731 Builder.SetInsertPoint(MinItCheckBlock);
732 Value *ExtStart = Builder.CreateZExt(V: Start, DestTy: I64Type);
733 Value *ExtEnd = Builder.CreateZExt(V: MaxLen, DestTy: I64Type);
734 // This check doesn't really cost us very much.
735
736 Value *LimitCheck = Builder.CreateICmpULE(LHS: Start, RHS: MaxLen);
737 CondBrInst *MinItCheckBr =
738 CondBrInst::Create(Cond: LimitCheck, IfTrue: MemCheckBlock, IfFalse: LoopPreHeaderBlock);
739 MinItCheckBr->setMetadata(
740 KindID: LLVMContext::MD_prof,
741 Node: MDBuilder(MinItCheckBr->getContext()).createBranchWeights(TrueWeight: 99, FalseWeight: 1));
742 Builder.Insert(I: MinItCheckBr);
743
744 DTU.applyUpdates(
745 Updates: {{DominatorTree::Insert, MinItCheckBlock, MemCheckBlock},
746 {DominatorTree::Insert, MinItCheckBlock, LoopPreHeaderBlock}});
747
748 // For each of the arrays, check the start/end addresses are on the same
749 // page.
750 Builder.SetInsertPoint(MemCheckBlock);
751
752 // The early exit in the original loop means that when performing vector
753 // loads we are potentially reading ahead of the early exit. So we could
754 // fault if crossing a page boundary. Therefore, we create runtime memory
755 // checks based on the minimum page size as follows:
756 // 1. Calculate the addresses of the first memory accesses in the loop,
757 // i.e. LhsStart and RhsStart.
758 // 2. Get the last accessed addresses in the loop, i.e. LhsEnd and RhsEnd.
759 // 3. Determine which pages correspond to all the memory accesses, i.e
760 // LhsStartPage, LhsEndPage, RhsStartPage, RhsEndPage.
761 // 4. If LhsStartPage == LhsEndPage and RhsStartPage == RhsEndPage, then
762 // we know we won't cross any page boundaries in the loop so we can
763 // enter the vector loop! Otherwise we fall back on the scalar loop.
764 Value *LhsStartGEP = Builder.CreateGEP(Ty: LoadType, Ptr: PtrA, IdxList: ExtStart);
765 Value *RhsStartGEP = Builder.CreateGEP(Ty: LoadType, Ptr: PtrB, IdxList: ExtStart);
766 Value *RhsStart = Builder.CreatePtrToInt(V: RhsStartGEP, DestTy: I64Type);
767 Value *LhsStart = Builder.CreatePtrToInt(V: LhsStartGEP, DestTy: I64Type);
768 Value *LhsEndGEP = Builder.CreateGEP(Ty: LoadType, Ptr: PtrA, IdxList: ExtEnd);
769 Value *RhsEndGEP = Builder.CreateGEP(Ty: LoadType, Ptr: PtrB, IdxList: ExtEnd);
770 Value *LhsEnd = Builder.CreatePtrToInt(V: LhsEndGEP, DestTy: I64Type);
771 Value *RhsEnd = Builder.CreatePtrToInt(V: RhsEndGEP, DestTy: I64Type);
772
773 const uint64_t MinPageSize = TTI->getMinPageSize().value();
774 const uint64_t AddrShiftAmt = llvm::Log2_64(Value: MinPageSize);
775 Value *LhsStartPage = Builder.CreateLShr(LHS: LhsStart, RHS: AddrShiftAmt);
776 Value *LhsEndPage = Builder.CreateLShr(LHS: LhsEnd, RHS: AddrShiftAmt);
777 Value *RhsStartPage = Builder.CreateLShr(LHS: RhsStart, RHS: AddrShiftAmt);
778 Value *RhsEndPage = Builder.CreateLShr(LHS: RhsEnd, RHS: AddrShiftAmt);
779 Value *LhsPageCmp = Builder.CreateICmpNE(LHS: LhsStartPage, RHS: LhsEndPage);
780 Value *RhsPageCmp = Builder.CreateICmpNE(LHS: RhsStartPage, RHS: RhsEndPage);
781
782 Value *CombinedPageCmp = Builder.CreateOr(LHS: LhsPageCmp, RHS: RhsPageCmp);
783 CondBrInst *CombinedPageCmpCmpBr = CondBrInst::Create(
784 Cond: CombinedPageCmp, IfTrue: LoopPreHeaderBlock, IfFalse: VectorLoopPreheaderBlock);
785 CombinedPageCmpCmpBr->setMetadata(
786 KindID: LLVMContext::MD_prof, Node: MDBuilder(CombinedPageCmpCmpBr->getContext())
787 .createBranchWeights(TrueWeight: 10, FalseWeight: 90));
788 Builder.Insert(I: CombinedPageCmpCmpBr);
789
790 DTU.applyUpdates(
791 Updates: {{DominatorTree::Insert, MemCheckBlock, LoopPreHeaderBlock},
792 {DominatorTree::Insert, MemCheckBlock, VectorLoopPreheaderBlock}});
793
794 // Set up the vector loop preheader, i.e. calculate initial loop predicate,
795 // zero-extend MaxLen to 64-bits, determine the number of vector elements
796 // processed in each iteration, etc.
797 Builder.SetInsertPoint(VectorLoopPreheaderBlock);
798
799 // At this point we know two things must be true:
800 // 1. Start <= End
801 // 2. ExtMaxLen <= MinPageSize due to the page checks.
802 // Therefore, we know that we can use a 64-bit induction variable that
803 // starts from 0 -> ExtMaxLen and it will not overflow.
804 Value *VectorLoopRes = nullptr;
805 switch (VectorizeStyle) {
806 case LoopIdiomVectorizeStyle::Masked:
807 VectorLoopRes =
808 createMaskedFindMismatch(Builder, DTU, GEPA, GEPB, ExtStart, ExtEnd);
809 break;
810 case LoopIdiomVectorizeStyle::Predicated:
811 VectorLoopRes = createPredicatedFindMismatch(Builder, DTU, GEPA, GEPB,
812 ExtStart, ExtEnd);
813 break;
814 }
815
816 Builder.CreateBr(Dest: EndBlock);
817
818 DTU.applyUpdates(
819 Updates: {{DominatorTree::Insert, VectorLoopMismatchBlock, EndBlock}});
820
821 // Generate code for scalar loop.
822 Builder.SetInsertPoint(LoopPreHeaderBlock);
823 Builder.CreateBr(Dest: LoopStartBlock);
824
825 DTU.applyUpdates(
826 Updates: {{DominatorTree::Insert, LoopPreHeaderBlock, LoopStartBlock}});
827
828 Builder.SetInsertPoint(LoopStartBlock);
829 PHINode *IndexPhi = Builder.CreatePHI(Ty: ResType, NumReservedValues: 2, Name: "mismatch_index");
830 IndexPhi->addIncoming(V: Start, BB: LoopPreHeaderBlock);
831
832 // Otherwise compare the values
833 // Load bytes from each array and compare them.
834 Value *GepOffset = Builder.CreateZExt(V: IndexPhi, DestTy: I64Type);
835
836 Value *LhsGep =
837 Builder.CreateGEP(Ty: LoadType, Ptr: PtrA, IdxList: GepOffset, Name: "", NW: GEPA->isInBounds());
838 Value *LhsLoad = Builder.CreateLoad(Ty: LoadType, Ptr: LhsGep);
839
840 Value *RhsGep =
841 Builder.CreateGEP(Ty: LoadType, Ptr: PtrB, IdxList: GepOffset, Name: "", NW: GEPB->isInBounds());
842 Value *RhsLoad = Builder.CreateLoad(Ty: LoadType, Ptr: RhsGep);
843
844 Value *MatchCmp = Builder.CreateICmpEQ(LHS: LhsLoad, RHS: RhsLoad);
845 // If we have a mismatch then exit the loop ...
846 Builder.CreateCondBr(Cond: MatchCmp, True: LoopIncBlock, False: EndBlock);
847
848 DTU.applyUpdates(Updates: {{DominatorTree::Insert, LoopStartBlock, LoopIncBlock},
849 {DominatorTree::Insert, LoopStartBlock, EndBlock}});
850
851 // Have we reached the maximum permitted length for the loop?
852 Builder.SetInsertPoint(LoopIncBlock);
853 Value *PhiInc = Builder.CreateAdd(LHS: IndexPhi, RHS: ConstantInt::get(Ty: ResType, V: 1), Name: "",
854 /*HasNUW=*/Index->hasNoUnsignedWrap(),
855 /*HasNSW=*/Index->hasNoSignedWrap());
856 IndexPhi->addIncoming(V: PhiInc, BB: LoopIncBlock);
857 Value *IVCmp = Builder.CreateICmpEQ(LHS: PhiInc, RHS: MaxLen);
858 Builder.CreateCondBr(Cond: IVCmp, True: EndBlock, False: LoopStartBlock);
859
860 DTU.applyUpdates(Updates: {{DominatorTree::Insert, LoopIncBlock, EndBlock},
861 {DominatorTree::Insert, LoopIncBlock, LoopStartBlock}});
862
863 // In the end block we need to insert a PHI node to deal with three cases:
864 // 1. We didn't find a mismatch in the scalar loop, so we return MaxLen.
865 // 2. We exitted the scalar loop early due to a mismatch and need to return
866 // the index that we found.
867 // 3. We didn't find a mismatch in the vector loop, so we return MaxLen.
868 // 4. We exitted the vector loop early due to a mismatch and need to return
869 // the index that we found.
870 Builder.SetInsertPoint(EndBlock->getFirstInsertionPt());
871 PHINode *ResPhi = Builder.CreatePHI(Ty: ResType, NumReservedValues: 4, Name: "mismatch_result");
872 ResPhi->addIncoming(V: MaxLen, BB: LoopIncBlock);
873 ResPhi->addIncoming(V: IndexPhi, BB: LoopStartBlock);
874 ResPhi->addIncoming(V: MaxLen, BB: VectorLoopIncBlock);
875 ResPhi->addIncoming(V: VectorLoopRes, BB: VectorLoopMismatchBlock);
876
877 Value *FinalRes = Builder.CreateTrunc(V: ResPhi, DestTy: ResType);
878
879 if (Opts.loop_idiom_vectorize_verify) {
880 ScalarLoop->verifyLoop();
881 VectorLoop->verifyLoop();
882 if (!VectorLoop->isRecursivelyLCSSAForm(DT: *DT, LI: *LI))
883 report_fatal_error(reason: "Loops must remain in LCSSA form!");
884 if (!ScalarLoop->isRecursivelyLCSSAForm(DT: *DT, LI: *LI))
885 report_fatal_error(reason: "Loops must remain in LCSSA form!");
886 }
887
888 return FinalRes;
889}
890
891void LoopIdiomVectorize::transformByteCompare(GetElementPtrInst *GEPA,
892 GetElementPtrInst *GEPB,
893 PHINode *IndPhi, Value *MaxLen,
894 Instruction *Index, Value *Start,
895 bool IncIdx, BasicBlock *FoundBB,
896 BasicBlock *EndBB) {
897
898 // Insert the byte compare code at the end of the preheader block
899 BasicBlock *Preheader = CurLoop->getLoopPreheader();
900 BasicBlock *Header = CurLoop->getHeader();
901 UncondBrInst *PHBranch = cast<UncondBrInst>(Val: Preheader->getTerminator());
902 IRBuilder<> Builder(PHBranch);
903 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
904 Builder.SetCurrentDebugLocation(PHBranch->getDebugLoc());
905
906 // Increment the pointer if this was done before the loads in the loop.
907 if (IncIdx)
908 Start = Builder.CreateAdd(LHS: Start, RHS: ConstantInt::get(Ty: Start->getType(), V: 1));
909
910 Value *ByteCmpRes =
911 expandFindMismatch(Builder, DTU, GEPA, GEPB, Index, Start, MaxLen);
912
913 // Replaces uses of index & induction Phi with intrinsic (we already
914 // checked that the the first instruction of Header is the Phi above).
915 assert(IndPhi->hasOneUse() && "Index phi node has more than one use!");
916 Index->replaceAllUsesWith(V: ByteCmpRes);
917
918 // If no mismatch was found, we can jump to the end block. Create a
919 // new basic block for the compare instruction.
920 auto *CmpBB = BasicBlock::Create(Context&: Preheader->getContext(), Name: "byte.compare",
921 Parent: Preheader->getParent());
922 CmpBB->moveBefore(MovePos: EndBB);
923
924 // Replace the branch in the preheader with an always-true conditional branch.
925 // This ensures there is still a reference to the original loop.
926 Builder.CreateCondBr(Cond: Builder.getTrue(), True: CmpBB, False: Header);
927 PHBranch->eraseFromParent();
928
929 BasicBlock *MismatchEnd = cast<Instruction>(Val: ByteCmpRes)->getParent();
930 DTU.applyUpdates(Updates: {{DominatorTree::Insert, MismatchEnd, CmpBB}});
931
932 // Create the branch to either the end or found block depending on the value
933 // returned by the intrinsic.
934 Builder.SetInsertPoint(CmpBB);
935 if (FoundBB != EndBB) {
936 Value *FoundCmp = Builder.CreateICmpEQ(LHS: ByteCmpRes, RHS: MaxLen);
937 Builder.CreateCondBr(Cond: FoundCmp, True: EndBB, False: FoundBB);
938 DTU.applyUpdates(Updates: {{DominatorTree::Insert, CmpBB, FoundBB},
939 {DominatorTree::Insert, CmpBB, EndBB}});
940
941 } else {
942 Builder.CreateBr(Dest: FoundBB);
943 DTU.applyUpdates(Updates: {{DominatorTree::Insert, CmpBB, FoundBB}});
944 }
945
946 // Ensure all Phis in the successors of CmpBB have an incoming value from it.
947 fixSuccessorPhis(L: CurLoop, ScalarRes: ByteCmpRes, VectorRes: ByteCmpRes, SuccBB: EndBB, IncBB: CmpBB);
948 if (EndBB != FoundBB)
949 fixSuccessorPhis(L: CurLoop, ScalarRes: ByteCmpRes, VectorRes: ByteCmpRes, SuccBB: FoundBB, IncBB: CmpBB);
950
951 // The new CmpBB block isn't part of the loop, but will need to be added to
952 // the outer loop if there is one.
953 if (!CurLoop->isOutermost())
954 CurLoop->getParentLoop()->addBasicBlockToLoop(NewBB: CmpBB, LI&: *LI);
955
956 if (Opts.loop_idiom_vectorize_verify && CurLoop->getParentLoop()) {
957 CurLoop->getParentLoop()->verifyLoop();
958 if (!CurLoop->getParentLoop()->isRecursivelyLCSSAForm(DT: *DT, LI: *LI))
959 report_fatal_error(reason: "Loops must remain in LCSSA form!");
960 }
961}
962
963bool LoopIdiomVectorize::recognizeFindFirstByte() {
964 // Currently the transformation only works on scalable vector types, although
965 // there is no fundamental reason why it cannot be made to work for fixed
966 // vectors. We also need to know the target's minimum page size in order to
967 // generate runtime memory checks to ensure the vector version won't fault.
968 if (!TTI->supportsScalableVectors() || !TTI->getMinPageSize().has_value() ||
969 Opts.disable_loop_idiom_vectorize_find_first_byte)
970 return false;
971
972 // We exclude loops with trip counts > minimum page size via runtime checks,
973 // so make sure that the minimum page size is something sensible such that
974 // induction variables cannot overflow.
975 if (uint64_t(*TTI->getMinPageSize()) >
976 (std::numeric_limits<uint64_t>::max() / 2))
977 return false;
978
979 // Define some constants we need throughout.
980 BasicBlock *Header = CurLoop->getHeader();
981 LLVMContext &Ctx = Header->getContext();
982
983 // We are expecting the four blocks defined below: Header, MatchBB, InnerBB,
984 // and OuterBB. For now, we will bail our for almost anything else. The Four
985 // blocks contain one nested loop.
986 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 4 ||
987 CurLoop->getSubLoops().size() != 1)
988 return false;
989
990 auto *InnerLoop = CurLoop->getSubLoops().front();
991
992 // Bail if vectorization is disabled on inner loop.
993 LoopVectorizeHints Hints(Opts, InnerLoop, /*InterleaveOnlyWhenForced=*/true,
994 ORE);
995 if (!Hints.allowVectorization(L: InnerLoop, /*VectorizeOnlyWhenForced=*/false)) {
996 LLVM_DEBUG(dbgs() << DEBUG_TYPE << " is disabled on inner loop "
997 << InnerLoop->getName()
998 << " due to vectorization hints\n");
999 return false;
1000 }
1001
1002 PHINode *IndPhi = dyn_cast<PHINode>(Val: &Header->front());
1003 if (!IndPhi || IndPhi->getNumIncomingValues() != 2)
1004 return false;
1005
1006 // Check instruction counts.
1007 auto LoopBlocks = CurLoop->getBlocks();
1008 if (LoopBlocks[0]->size() > 3 || LoopBlocks[1]->size() > 4 ||
1009 LoopBlocks[2]->size() > 3 || LoopBlocks[3]->size() > 3)
1010 return false;
1011
1012 // Check that no instruction other than IndPhi has outside uses.
1013 for (BasicBlock *BB : LoopBlocks)
1014 for (Instruction &I : *BB)
1015 if (&I != IndPhi)
1016 for (User *U : I.users())
1017 if (!CurLoop->contains(Inst: cast<Instruction>(Val: U)))
1018 return false;
1019
1020 // Match the branch instruction in the header. We are expecting an
1021 // unconditional branch to the inner loop.
1022 //
1023 // Header:
1024 // %14 = phi ptr [ %24, %OuterBB ], [ %3, %Header.preheader ]
1025 // %15 = load i8, ptr %14, align 1
1026 // br label %MatchBB
1027 BasicBlock *MatchBB;
1028 if (!match(V: Header->getTerminator(), P: m_UnconditionalBr(Succ&: MatchBB)) ||
1029 !InnerLoop->contains(BB: MatchBB))
1030 return false;
1031
1032 // MatchBB should be the entrypoint into the inner loop containing the
1033 // comparison between a search element and a needle.
1034 //
1035 // MatchBB:
1036 // %20 = phi ptr [ %7, %Header ], [ %17, %InnerBB ]
1037 // %21 = load i8, ptr %20, align 1
1038 // %22 = icmp eq i8 %15, %21
1039 // br i1 %22, label %ExitSucc, label %InnerBB
1040 BasicBlock *ExitSucc, *InnerBB;
1041 Value *LoadSearch, *LoadNeedle;
1042 CmpPredicate MatchPred;
1043 if (!match(V: MatchBB->getTerminator(),
1044 P: m_Br(C: m_ICmp(Pred&: MatchPred, L: m_Value(V&: LoadSearch), R: m_Value(V&: LoadNeedle)),
1045 T: m_BasicBlock(V&: ExitSucc), F: m_BasicBlock(V&: InnerBB))) ||
1046 MatchPred != ICmpInst::ICMP_EQ || !InnerLoop->contains(BB: InnerBB))
1047 return false;
1048
1049 // We expect outside uses of `IndPhi' in ExitSucc (and only there).
1050 for (User *U : IndPhi->users())
1051 if (!CurLoop->contains(Inst: cast<Instruction>(Val: U))) {
1052 auto *PN = dyn_cast<PHINode>(Val: U);
1053 if (!PN || PN->getParent() != ExitSucc)
1054 return false;
1055 }
1056
1057 // Match the loads and check they are simple. The loads come from two PHIs,
1058 // each with two incoming values.
1059 PHINode *PSearch, *PNeedle;
1060 if (!match(V: LoadSearch, P: m_Load(Op: m_Phi(PN&: PSearch))) ||
1061 !match(V: LoadNeedle, P: m_Load(Op: m_Phi(PN&: PNeedle))) ||
1062 !cast<LoadInst>(Val: LoadSearch)->isSimple() ||
1063 !cast<LoadInst>(Val: LoadNeedle)->isSimple())
1064 return false;
1065
1066 // Check we are loading valid characters.
1067 Type *CharTy = LoadSearch->getType();
1068 if (!CharTy->isIntegerTy() || LoadNeedle->getType() != CharTy)
1069 return false;
1070
1071 // Pick the vectorisation factor based on CharTy, work out the cost of the
1072 // match intrinsic and decide if we should use it.
1073 // Note: For the time being we assume 128-bit vectors.
1074 unsigned VF = 128 / CharTy->getIntegerBitWidth();
1075 SmallVector<Type *> Args = {
1076 ScalableVectorType::get(ElementType: CharTy, MinNumElts: VF), FixedVectorType::get(ElementType: CharTy, NumElts: VF),
1077 ScalableVectorType::get(ElementType: Type::getInt1Ty(C&: Ctx), MinNumElts: VF)};
1078 IntrinsicCostAttributes Attrs(Intrinsic::experimental_vector_match, Args[2],
1079 Args);
1080 if (TTI->getIntrinsicInstrCost(ICA: Attrs, CostKind: TTI::TCK_SizeAndLatency) > 4)
1081 return false;
1082
1083 if (PSearch->getNumIncomingValues() != 2 ||
1084 PNeedle->getNumIncomingValues() != 2)
1085 return false;
1086
1087 // One PHI comes from the outer loop (PSearch), the other one from the inner
1088 // loop (PNeedle). PSearch effectively corresponds to IndPhi.
1089 if (InnerLoop->contains(Inst: PSearch))
1090 std::swap(a&: PSearch, b&: PNeedle);
1091 if (PSearch != &Header->front() || PNeedle != &MatchBB->front())
1092 return false;
1093
1094 // The incoming values of both PHI nodes should be a gep of 1.
1095 Value *SearchStart = PSearch->getIncomingValue(i: 0);
1096 Value *SearchIndex = PSearch->getIncomingValue(i: 1);
1097 if (CurLoop->contains(BB: PSearch->getIncomingBlock(i: 0)))
1098 std::swap(a&: SearchStart, b&: SearchIndex);
1099
1100 Value *NeedleStart = PNeedle->getIncomingValue(i: 0);
1101 Value *NeedleIndex = PNeedle->getIncomingValue(i: 1);
1102 if (InnerLoop->contains(BB: PNeedle->getIncomingBlock(i: 0)))
1103 std::swap(a&: NeedleStart, b&: NeedleIndex);
1104
1105 // Match the GEPs.
1106 if (!match(V: SearchIndex, P: m_GEP(Ops: m_Specific(V: PSearch), Ops: m_One())) ||
1107 !match(V: NeedleIndex, P: m_GEP(Ops: m_Specific(V: PNeedle), Ops: m_One())))
1108 return false;
1109
1110 // Check the GEPs result type matches `CharTy'.
1111 GetElementPtrInst *GEPSearch = cast<GetElementPtrInst>(Val: SearchIndex);
1112 GetElementPtrInst *GEPNeedle = cast<GetElementPtrInst>(Val: NeedleIndex);
1113 if (GEPSearch->getResultElementType() != CharTy ||
1114 GEPNeedle->getResultElementType() != CharTy)
1115 return false;
1116
1117 // InnerBB should increment the address of the needle pointer.
1118 //
1119 // InnerBB:
1120 // %17 = getelementptr inbounds i8, ptr %20, i64 1
1121 // %18 = icmp eq ptr %17, %10
1122 // br i1 %18, label %OuterBB, label %MatchBB
1123 BasicBlock *OuterBB;
1124 Value *NeedleEnd;
1125 if (!match(V: InnerBB->getTerminator(),
1126 P: m_Br(C: m_SpecificICmp(MatchPred: ICmpInst::ICMP_EQ, L: m_Specific(V: GEPNeedle),
1127 R: m_Value(V&: NeedleEnd)),
1128 T: m_BasicBlock(V&: OuterBB), F: m_Specific(V: MatchBB))) ||
1129 !CurLoop->contains(BB: OuterBB))
1130 return false;
1131
1132 // OuterBB should increment the address of the search element pointer.
1133 //
1134 // OuterBB:
1135 // %24 = getelementptr inbounds i8, ptr %14, i64 1
1136 // %25 = icmp eq ptr %24, %6
1137 // br i1 %25, label %ExitFail, label %Header
1138 BasicBlock *ExitFail;
1139 Value *SearchEnd;
1140 if (!match(V: OuterBB->getTerminator(),
1141 P: m_Br(C: m_SpecificICmp(MatchPred: ICmpInst::ICMP_EQ, L: m_Specific(V: GEPSearch),
1142 R: m_Value(V&: SearchEnd)),
1143 T: m_BasicBlock(V&: ExitFail), F: m_Specific(V: Header))))
1144 return false;
1145
1146 if (!CurLoop->isLoopInvariant(V: SearchStart) ||
1147 !CurLoop->isLoopInvariant(V: SearchEnd) ||
1148 !CurLoop->isLoopInvariant(V: NeedleStart) ||
1149 !CurLoop->isLoopInvariant(V: NeedleEnd))
1150 return false;
1151
1152 LLVM_DEBUG(dbgs() << "Found idiom in loop: \n" << *CurLoop << "\n\n");
1153
1154 transformFindFirstByte(IndPhi, VF, CharTy, ExitSucc, ExitFail, SearchStart,
1155 SearchEnd, NeedleStart, NeedleEnd);
1156 return true;
1157}
1158
1159Value *LoopIdiomVectorize::expandFindFirstByte(
1160 IRBuilder<> &Builder, DomTreeUpdater &DTU, unsigned VF, Type *CharTy,
1161 Value *IndPhi, BasicBlock *ExitSucc, BasicBlock *ExitFail,
1162 Value *SearchStart, Value *SearchEnd, Value *NeedleStart,
1163 Value *NeedleEnd) {
1164 // Set up some types and constants that we intend to reuse.
1165 auto *I64Ty = Builder.getInt64Ty();
1166 auto *PredVTy = ScalableVectorType::get(ElementType: Builder.getInt1Ty(), MinNumElts: VF);
1167 auto *CharVTy = ScalableVectorType::get(ElementType: CharTy, MinNumElts: VF);
1168 auto *ConstVF = ConstantInt::get(Ty: I64Ty, V: VF);
1169
1170 // Other common arguments.
1171 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1172 LLVMContext &Ctx = Preheader->getContext();
1173 Value *Passthru = ConstantInt::getNullValue(Ty: CharVTy);
1174
1175 // Split block in the original loop preheader.
1176 // SPH is the new preheader to the old scalar loop.
1177 BasicBlock *SPH = SplitBlock(Old: Preheader, SplitPt: Preheader->getTerminator(), DT, LI,
1178 MSSAU: nullptr, BBName: "scalar_preheader");
1179
1180 // Create the blocks that we're going to use.
1181 //
1182 // We will have the following loops:
1183 // (O) Outer loop where we iterate over the elements of the search array.
1184 // (I) Inner loop where we iterate over the elements of the needle array.
1185 //
1186 // Overall, the blocks do the following:
1187 // (0) Check if the arrays can't cross page boundaries. If so go to (1),
1188 // otherwise fall back to the original scalar loop.
1189 // (1) Load the search array. Go to (2).
1190 // (2) (a) Load the needle array.
1191 // (b) Splat the first element to the inactive lanes.
1192 // (c) Accumulate any matches found. If we haven't reached the end of the
1193 // needle array loop back to (2), otherwise go to (3).
1194 // (3) Test if we found any match. If so go to (4), otherwise go to (5).
1195 // (4) Compute the index of the first match and exit.
1196 // (5) Check if we've reached the end of the search array. If not loop back to
1197 // (1), otherwise exit.
1198 // Blocks (0,4) are not part of any loop. Blocks (1,3,5) and (2) belong to the
1199 // outer and inner loops, respectively.
1200 BasicBlock *BB0 = BasicBlock::Create(Context&: Ctx, Name: "mem_check", Parent: SPH->getParent(), InsertBefore: SPH);
1201 BasicBlock *BB1 =
1202 BasicBlock::Create(Context&: Ctx, Name: "find_first_vec_header", Parent: SPH->getParent(), InsertBefore: SPH);
1203 BasicBlock *BB2 =
1204 BasicBlock::Create(Context&: Ctx, Name: "needle_check_vec", Parent: SPH->getParent(), InsertBefore: SPH);
1205 BasicBlock *BB3 =
1206 BasicBlock::Create(Context&: Ctx, Name: "match_check_vec", Parent: SPH->getParent(), InsertBefore: SPH);
1207 BasicBlock *BB4 =
1208 BasicBlock::Create(Context&: Ctx, Name: "calculate_match", Parent: SPH->getParent(), InsertBefore: SPH);
1209 BasicBlock *BB5 =
1210 BasicBlock::Create(Context&: Ctx, Name: "search_check_vec", Parent: SPH->getParent(), InsertBefore: SPH);
1211
1212 // Update LoopInfo with the new loops.
1213 auto OuterLoop = LI->AllocateLoop();
1214 auto InnerLoop = LI->AllocateLoop();
1215
1216 if (auto ParentLoop = CurLoop->getParentLoop()) {
1217 ParentLoop->addBasicBlockToLoop(NewBB: BB0, LI&: *LI);
1218 ParentLoop->addChildLoop(NewChild: OuterLoop);
1219 } else {
1220 LI->addTopLevelLoop(New: OuterLoop);
1221 }
1222
1223 // BB4 branches only to ExitSucc, so it belongs to the innermost enclosing
1224 // loop that contains ExitSucc. That is not necessarily CurLoop's parent: a
1225 // match can exit several levels out, or out of every loop.
1226 Loop *ExitLoop = CurLoop->getParentLoop();
1227 while (ExitLoop && !ExitLoop->contains(BB: ExitSucc))
1228 ExitLoop = ExitLoop->getParentLoop();
1229 if (ExitLoop)
1230 ExitLoop->addBasicBlockToLoop(NewBB: BB4, LI&: *LI);
1231
1232 // Add the inner loop to the outer.
1233 OuterLoop->addChildLoop(NewChild: InnerLoop);
1234
1235 // Add the new basic blocks to the corresponding loops.
1236 OuterLoop->addBasicBlockToLoop(NewBB: BB1, LI&: *LI);
1237 OuterLoop->addBasicBlockToLoop(NewBB: BB3, LI&: *LI);
1238 OuterLoop->addBasicBlockToLoop(NewBB: BB5, LI&: *LI);
1239 InnerLoop->addBasicBlockToLoop(NewBB: BB2, LI&: *LI);
1240
1241 // Update the terminator added by SplitBlock to branch to the first block.
1242 Preheader->getTerminator()->setSuccessor(Idx: 0, BB: BB0);
1243 DTU.applyUpdates(Updates: {{DominatorTree::Delete, Preheader, SPH},
1244 {DominatorTree::Insert, Preheader, BB0}});
1245
1246 // (0) Check if we could be crossing a page boundary; if so, fallback to the
1247 // old scalar loops. Also create a predicate of VF elements to be used in the
1248 // vector loops.
1249 Builder.SetInsertPoint(BB0);
1250 Value *ISearchStart =
1251 Builder.CreatePtrToInt(V: SearchStart, DestTy: I64Ty, Name: "search_start_int");
1252 Value *ISearchEnd =
1253 Builder.CreatePtrToInt(V: SearchEnd, DestTy: I64Ty, Name: "search_end_int");
1254 Value *SearchIdxInit = Constant::getNullValue(Ty: I64Ty);
1255 Value *SearchTripCount =
1256 Builder.CreateZExt(V: Builder.CreatePtrDiff(ElemTy: CharTy, LHS: SearchEnd, RHS: SearchStart,
1257 Name: "search_trip_count"),
1258 DestTy: I64Ty);
1259 Value *INeedleStart =
1260 Builder.CreatePtrToInt(V: NeedleStart, DestTy: I64Ty, Name: "needle_start_int");
1261 Value *INeedleEnd =
1262 Builder.CreatePtrToInt(V: NeedleEnd, DestTy: I64Ty, Name: "needle_end_int");
1263 Value *NeedleIdxInit = Constant::getNullValue(Ty: I64Ty);
1264 Value *NeedleTripCount =
1265 Builder.CreateZExt(V: Builder.CreatePtrDiff(ElemTy: CharTy, LHS: NeedleEnd, RHS: NeedleStart,
1266 Name: "needle_trip_count"),
1267 DestTy: I64Ty);
1268 Value *PredVF =
1269 Builder.CreateIntrinsic(ID: Intrinsic::get_active_lane_mask, OverloadTypes: {PredVTy, I64Ty},
1270 Args: {ConstantInt::get(Ty: I64Ty, V: 0), ConstVF});
1271
1272 const uint64_t MinPageSize = TTI->getMinPageSize().value();
1273 const uint64_t AddrShiftAmt = llvm::Log2_64(Value: MinPageSize);
1274 Value *SearchStartPage =
1275 Builder.CreateLShr(LHS: ISearchStart, RHS: AddrShiftAmt, Name: "search_start_page");
1276 Value *SearchEndPage =
1277 Builder.CreateLShr(LHS: ISearchEnd, RHS: AddrShiftAmt, Name: "search_end_page");
1278 Value *NeedleStartPage =
1279 Builder.CreateLShr(LHS: INeedleStart, RHS: AddrShiftAmt, Name: "needle_start_page");
1280 Value *NeedleEndPage =
1281 Builder.CreateLShr(LHS: INeedleEnd, RHS: AddrShiftAmt, Name: "needle_end_page");
1282 Value *SearchPageCmp =
1283 Builder.CreateICmpNE(LHS: SearchStartPage, RHS: SearchEndPage, Name: "search_page_cmp");
1284 Value *NeedlePageCmp =
1285 Builder.CreateICmpNE(LHS: NeedleStartPage, RHS: NeedleEndPage, Name: "needle_page_cmp");
1286
1287 Value *CombinedPageCmp =
1288 Builder.CreateOr(LHS: SearchPageCmp, RHS: NeedlePageCmp, Name: "combined_page_cmp");
1289 CondBrInst *CombinedPageBr = Builder.CreateCondBr(Cond: CombinedPageCmp, True: SPH, False: BB1);
1290 CombinedPageBr->setMetadata(KindID: LLVMContext::MD_prof,
1291 Node: MDBuilder(Ctx).createBranchWeights(TrueWeight: 10, FalseWeight: 90));
1292 DTU.applyUpdates(
1293 Updates: {{DominatorTree::Insert, BB0, SPH}, {DominatorTree::Insert, BB0, BB1}});
1294
1295 // (1) Load the search array and branch to the inner loop.
1296 Builder.SetInsertPoint(BB1);
1297 PHINode *SearchIdx = Builder.CreatePHI(Ty: I64Ty, NumReservedValues: 2, Name: "search_idx");
1298 Value *PredSearch = Builder.CreateIntrinsic(
1299 ID: Intrinsic::get_active_lane_mask, OverloadTypes: {PredVTy, I64Ty},
1300 Args: {SearchIdx, SearchTripCount}, FMFSource: nullptr, Name: "search_pred");
1301 PredSearch = Builder.CreateAnd(LHS: PredVF, RHS: PredSearch, Name: "search_masked");
1302 Value *Search = Builder.CreateGEP(Ty: CharTy, Ptr: SearchStart, IdxList: SearchIdx, Name: "psearch");
1303 Value *LoadSearch = Builder.CreateMaskedLoad(
1304 Ty: CharVTy, Ptr: Search, Alignment: Align(1), Mask: PredSearch, PassThru: Passthru, Name: "search_load_vec");
1305 Value *MatchInit = Constant::getNullValue(Ty: PredVTy);
1306 Builder.CreateBr(Dest: BB2);
1307 DTU.applyUpdates(Updates: {{DominatorTree::Insert, BB1, BB2}});
1308
1309 // (2) Inner loop.
1310 Builder.SetInsertPoint(BB2);
1311 PHINode *NeedleIdx = Builder.CreatePHI(Ty: I64Ty, NumReservedValues: 2, Name: "needle_idx");
1312 PHINode *Match = Builder.CreatePHI(Ty: PredVTy, NumReservedValues: 2, Name: "pmatch");
1313
1314 // (2.a) Load the needle array.
1315 Value *PredNeedle = Builder.CreateIntrinsic(
1316 ID: Intrinsic::get_active_lane_mask, OverloadTypes: {PredVTy, I64Ty},
1317 Args: {NeedleIdx, NeedleTripCount}, FMFSource: nullptr, Name: "needle_pred");
1318 PredNeedle = Builder.CreateAnd(LHS: PredVF, RHS: PredNeedle, Name: "needle_masked");
1319 Value *Needle = Builder.CreateGEP(Ty: CharTy, Ptr: NeedleStart, IdxList: NeedleIdx, Name: "pneedle");
1320 Value *LoadNeedle = Builder.CreateMaskedLoad(
1321 Ty: CharVTy, Ptr: Needle, Alignment: Align(1), Mask: PredNeedle, PassThru: Passthru, Name: "needle_load_vec");
1322
1323 // (2.b) Splat the first element to the inactive lanes.
1324 Value *Needle0 =
1325 Builder.CreateExtractElement(Vec: LoadNeedle, Idx: uint64_t(0), Name: "needle0");
1326 Value *Needle0Splat = Builder.CreateVectorSplat(EC: ElementCount::getScalable(MinVal: VF),
1327 V: Needle0, Name: "needle0");
1328 LoadNeedle = Builder.CreateSelect(C: PredNeedle, True: LoadNeedle, False: Needle0Splat,
1329 Name: "needle_splat");
1330 LoadNeedle = Builder.CreateExtractVector(
1331 DstType: FixedVectorType::get(ElementType: CharTy, NumElts: VF), SrcVec: LoadNeedle, Idx: uint64_t(0), Name: "needle_vec");
1332
1333 // (2.c) Accumulate matches.
1334 Value *MatchSeg = Builder.CreateIntrinsic(
1335 ID: Intrinsic::experimental_vector_match, OverloadTypes: {CharVTy, LoadNeedle->getType()},
1336 Args: {LoadSearch, LoadNeedle, PredSearch}, FMFSource: nullptr, Name: "match_segment");
1337 Value *MatchAcc = Builder.CreateOr(LHS: Match, RHS: MatchSeg, Name: "match_accumulator");
1338 Value *NextNeedleIdx =
1339 Builder.CreateAdd(LHS: NeedleIdx, RHS: ConstVF, Name: "needle_idx_next");
1340 Builder.CreateCondBr(Cond: Builder.CreateICmpULT(LHS: NextNeedleIdx, RHS: NeedleTripCount),
1341 True: BB2, False: BB3);
1342 DTU.applyUpdates(
1343 Updates: {{DominatorTree::Insert, BB2, BB2}, {DominatorTree::Insert, BB2, BB3}});
1344
1345 // (3) Check if we found a match.
1346 Builder.SetInsertPoint(BB3);
1347 PHINode *MatchPredAccLCSSA = Builder.CreatePHI(Ty: PredVTy, NumReservedValues: 1, Name: "match_pred");
1348 Value *IfAnyMatch = Builder.CreateOrReduce(Src: MatchPredAccLCSSA);
1349 Builder.CreateCondBr(Cond: IfAnyMatch, True: BB4, False: BB5);
1350 DTU.applyUpdates(
1351 Updates: {{DominatorTree::Insert, BB3, BB4}, {DominatorTree::Insert, BB3, BB5}});
1352
1353 // (4) We found a match. Compute the index of its location and exit.
1354 Builder.SetInsertPoint(BB4);
1355 PHINode *MatchLCSSA =
1356 Builder.CreatePHI(Ty: SearchStart->getType(), NumReservedValues: 1, Name: "match_start");
1357 PHINode *MatchPredLCSSA = Builder.CreatePHI(Ty: PredVTy, NumReservedValues: 1, Name: "match_vec");
1358 Value *MatchCnt = Builder.CreateIntrinsic(
1359 ID: Intrinsic::experimental_cttz_elts, OverloadTypes: {I64Ty, PredVTy},
1360 Args: {MatchPredLCSSA, /*ZeroIsPoison=*/Builder.getInt1(V: true)}, FMFSource: nullptr,
1361 Name: "match_idx");
1362 Value *MatchVal =
1363 Builder.CreateGEP(Ty: CharTy, Ptr: MatchLCSSA, IdxList: MatchCnt, Name: "match_res");
1364 Builder.CreateBr(Dest: ExitSucc);
1365 DTU.applyUpdates(Updates: {{DominatorTree::Insert, BB4, ExitSucc}});
1366
1367 // (5) Check if we've reached the end of the search array.
1368 Builder.SetInsertPoint(BB5);
1369 Value *NextSearchIdx =
1370 Builder.CreateAdd(LHS: SearchIdx, RHS: ConstVF, Name: "search_idx_next");
1371 Builder.CreateCondBr(Cond: Builder.CreateICmpULT(LHS: NextSearchIdx, RHS: SearchTripCount),
1372 True: BB1, False: ExitFail);
1373 DTU.applyUpdates(Updates: {{DominatorTree::Insert, BB5, BB1},
1374 {DominatorTree::Insert, BB5, ExitFail}});
1375
1376 // Set up the PHI nodes.
1377 SearchIdx->addIncoming(V: SearchIdxInit, BB: BB0);
1378 SearchIdx->addIncoming(V: NextSearchIdx, BB: BB5);
1379 NeedleIdx->addIncoming(V: NeedleIdxInit, BB: BB1);
1380 NeedleIdx->addIncoming(V: NextNeedleIdx, BB: BB2);
1381 Match->addIncoming(V: MatchInit, BB: BB1);
1382 Match->addIncoming(V: MatchAcc, BB: BB2);
1383 // These are needed to retain LCSSA form.
1384 MatchPredAccLCSSA->addIncoming(V: MatchAcc, BB: BB2);
1385 MatchLCSSA->addIncoming(V: Search, BB: BB3);
1386 MatchPredLCSSA->addIncoming(V: MatchPredAccLCSSA, BB: BB3);
1387
1388 // Ensure all Phis in the successors of BB4/BB5 have an incoming value from
1389 // them.
1390 fixSuccessorPhis(L: CurLoop, ScalarRes: IndPhi, VectorRes: MatchVal, SuccBB: ExitSucc, IncBB: BB4);
1391 if (ExitSucc != ExitFail)
1392 fixSuccessorPhis(L: CurLoop, ScalarRes: IndPhi, VectorRes: MatchVal, SuccBB: ExitFail, IncBB: BB5);
1393
1394 if (Opts.loop_idiom_vectorize_verify) {
1395 OuterLoop->verifyLoop();
1396 InnerLoop->verifyLoop();
1397 if (!OuterLoop->isRecursivelyLCSSAForm(DT: *DT, LI: *LI))
1398 report_fatal_error(reason: "Loops must remain in LCSSA form!");
1399 }
1400
1401 return MatchVal;
1402}
1403
1404void LoopIdiomVectorize::transformFindFirstByte(
1405 PHINode *IndPhi, unsigned VF, Type *CharTy, BasicBlock *ExitSucc,
1406 BasicBlock *ExitFail, Value *SearchStart, Value *SearchEnd,
1407 Value *NeedleStart, Value *NeedleEnd) {
1408 // Insert the find first byte code at the end of the preheader block.
1409 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1410 UncondBrInst *PHBranch = cast<UncondBrInst>(Val: Preheader->getTerminator());
1411 IRBuilder<> Builder(PHBranch);
1412 Builder.disableGEPCanonicalization();
1413 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1414 Builder.SetCurrentDebugLocation(PHBranch->getDebugLoc());
1415
1416 expandFindFirstByte(Builder, DTU, VF, CharTy, IndPhi, ExitSucc, ExitFail,
1417 SearchStart, SearchEnd, NeedleStart, NeedleEnd);
1418
1419 if (Opts.loop_idiom_vectorize_verify && CurLoop->getParentLoop()) {
1420 CurLoop->getParentLoop()->verifyLoop();
1421 if (!CurLoop->getParentLoop()->isRecursivelyLCSSAForm(DT: *DT, LI: *LI))
1422 report_fatal_error(reason: "Loops must remain in LCSSA form!");
1423 }
1424}
1425