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