Repository: llvm/llvm-project
File: llvm/lib/Transforms/Vectorize/LoopIdiomVectorize.cpp (C++)

Code before:

  // The new CmpBB block isn't part of the loop, but will need to be added to
  // the outer loop if there is one.
  if (!CurLoop->isOutermost())
    CurLoop->getParentLoop()->addBasicBlockToLoop(CmpBB, *LI);

  if (VerifyLoops && CurLoop->getParentLoop()) {
    CurLoop->getParentLoop()->verifyLoop();
    if (!CurLoop->getParentLoop()->isRecursivelyLCSSAForm(*DT, *LI))
      report_fatal_error("Loops must remain in LCSSA form!");
  }
}

bool LoopIdiomVectorize::recognizeFindFirstByte() {
  // Currently the transformation only works on scalable vector types, although
  // there is no fundamental reason why it cannot be made to work for fixed
  // vectors. We also need to know the target's minimum page size in order to
  // generate runtime memory checks to ensure the vector version won't fault.
  if (!TTI->supportsScalableVectors() || !TTI->getMinPageSize().has_value() ||
      DisableFindFirstByte)
    return false;

  // We exclude loops with trip counts > minimum page size via runtime checks,
  // so make sure that the minimum page size is something sensible such that
  // induction variables cannot overflow.
  if (sizeof(*TTI->getMinPageSize()) >= sizeof(uint64_t))
    return false;

  // Define some constants we need throughout.
  BasicBlock *Header = CurLoop->getHeader();
  LLVMContext &Ctx = Header->getContext();

  // We are expecting the four blocks defined below: Header, MatchBB, InnerBB,
  // and OuterBB. For now, we will bail our for almost anything else. The Four
  // blocks contain one nested loop.
  if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 4 ||
      CurLoop->getSubLoops().size() != 1)
    return false;

  auto *InnerLoop = CurLoop->getSubLoops().front();
  PHINode *IndPhi = dyn_cast<PHINode>(&Header->front());
  if (!IndPhi || IndPhi->getNumIncomingValues() != 2)
    return false;

  // Check instruction counts.
  auto LoopBlocks = CurLoop->getBlocks();
  if (LoopBlocks[0]->sizeWithoutDebug() > 3 ||
      LoopBlocks[1]->sizeWithoutDebug() > 4 ||
      LoopBlocks[2]->sizeWithoutDebug() > 3 ||
      LoopBlocks[3]->sizeWithoutDebug() > 3)
    return false;

Review comment (suggestion):
Hmm, I think this works, but it's not as clear as just doing

```
  if (*TTI->getMinPageSize() > (std::numeric_limits<uint64_t>::max() / 2))
    return false;
```

which would be optimised away by the compiler anyway. Alternatively, if you want to leave the original check can you add a comment explaining why you're checking the size of the type and not the actual page size value?

I'll leave it up to you!

Code after:
  PHBranch->eraseFromParent();

  BasicBlock *MismatchEnd = cast<Instruction>(ByteCmpRes)->getParent();
  DTU.applyUpdates({{DominatorTree::Insert, MismatchEnd, CmpBB}});

  // Create the branch to either the end or found block depending on the value
  // returned by the intrinsic.
  Builder.SetInsertPoint(CmpBB);
  if (FoundBB != EndBB) {
    Value *FoundCmp = Builder.CreateICmpEQ(ByteCmpRes, MaxLen);
    Builder.CreateCondBr(FoundCmp, EndBB, FoundBB);
    DTU.applyUpdates({{DominatorTree::Insert, CmpBB, FoundBB},
                      {DominatorTree::Insert, CmpBB, EndBB}});

  } else {
    Builder.CreateBr(FoundBB);
    DTU.applyUpdates({{DominatorTree::Insert, CmpBB, FoundBB}});
  }

  // Ensure all Phis in the successors of CmpBB have an incoming value from it.
  fixSuccessorPhis(CurLoop, ByteCmpRes, ByteCmpRes, EndBB, CmpBB);
  if (EndBB != FoundBB)
    fixSuccessorPhis(CurLoop, ByteCmpRes, ByteCmpRes, FoundBB, CmpBB);

  // The new CmpBB block isn't part of the loop, but will need to be added to
  // the outer loop if there is one.
  if (!CurLoop->isOutermost())
    CurLoop->getParentLoop()->addBasicBlockToLoop(CmpBB, *LI);

  if (VerifyLoops && CurLoop->getParentLoop()) {
    CurLoop->getParentLoop()->verifyLoop();
    if (!CurLoop->getParentLoop()->isRecursivelyLCSSAForm(*DT, *LI))
      report_fatal_error("Loops must remain in LCSSA form!");
  }
}

bool LoopIdiomVectorize::recognizeFindFirstByte() {
  // Currently the transformation only works on scalable vector types, although
  // there is no fundamental reason why it cannot be made to work for fixed
  // vectors. We also need to know the target's minimum page size in order to
  // generate runtime memory checks to ensure the vector version won't fault.
  if (!TTI->supportsScalableVectors() || !TTI->getMinPageSize().has_value() ||
      DisableFindFirstByte)
    return false;

  // We exclude loops with trip counts > minimum page size via runtime checks,
  // so make sure that the minimum page size is something sensible such that
  // induction variables cannot overflow.
  if (uint64_t(*TTI->getMinPageSize()) >
      (std::numeric_limits<uint64_t>::max() / 2))
    return false;