974 lines · cpp
1//===- MergeICmps.cpp - Optimize chains of integer comparisons ------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// This pass turns chains of integer comparisons into memcmp (the memcmp is10// later typically inlined as a chain of efficient hardware comparisons). This11// typically benefits c++ member or nonmember operator==().12//13// The basic idea is to replace a longer chain of integer comparisons loaded14// from contiguous memory locations into a shorter chain of larger integer15// comparisons. Benefits are double:16// - There are less jumps, and therefore less opportunities for mispredictions17// and I-cache misses.18// - Code size is smaller, both because jumps are removed and because the19// encoding of a 2*n byte compare is smaller than that of two n-byte20// compares.21//22// Example:23//24// struct S {25// int a;26// char b;27// char c;28// uint16_t d;29// bool operator==(const S& o) const {30// return a == o.a && b == o.b && c == o.c && d == o.d;31// }32// };33//34// Is optimized as :35//36// bool S::operator==(const S& o) const {37// return memcmp(this, &o, 8) == 0;38// }39//40// Which will later be expanded (ExpandMemCmp) as a single 8-bytes icmp.41//42//===----------------------------------------------------------------------===//43 44#include "llvm/Transforms/Scalar/MergeICmps.h"45#include "llvm/ADT/SmallString.h"46#include "llvm/Analysis/DomTreeUpdater.h"47#include "llvm/Analysis/GlobalsModRef.h"48#include "llvm/Analysis/Loads.h"49#include "llvm/Analysis/TargetLibraryInfo.h"50#include "llvm/Analysis/TargetTransformInfo.h"51#include "llvm/IR/Dominators.h"52#include "llvm/IR/Function.h"53#include "llvm/IR/IRBuilder.h"54#include "llvm/IR/Instruction.h"55#include "llvm/IR/ProfDataUtils.h"56#include "llvm/InitializePasses.h"57#include "llvm/Pass.h"58#include "llvm/Transforms/Scalar.h"59#include "llvm/Transforms/Utils/BasicBlockUtils.h"60#include "llvm/Transforms/Utils/BuildLibCalls.h"61#include <algorithm>62#include <numeric>63#include <utility>64#include <vector>65 66using namespace llvm;67 68#define DEBUG_TYPE "mergeicmps"69 70namespace llvm {71extern cl::opt<bool> ProfcheckDisableMetadataFixes;72} // namespace llvm73namespace {74 75// A BCE atom "Binary Compare Expression Atom" represents an integer load76// that is a constant offset from a base value, e.g. `a` or `o.c` in the example77// at the top.78struct BCEAtom {79 BCEAtom() = default;80 BCEAtom(GetElementPtrInst *GEP, LoadInst *LoadI, int BaseId, APInt Offset)81 : GEP(GEP), LoadI(LoadI), BaseId(BaseId), Offset(std::move(Offset)) {}82 83 BCEAtom(const BCEAtom &) = delete;84 BCEAtom &operator=(const BCEAtom &) = delete;85 86 BCEAtom(BCEAtom &&that) = default;87 BCEAtom &operator=(BCEAtom &&that) {88 if (this == &that)89 return *this;90 GEP = that.GEP;91 LoadI = that.LoadI;92 BaseId = that.BaseId;93 Offset = std::move(that.Offset);94 return *this;95 }96 97 // We want to order BCEAtoms by (Base, Offset). However we cannot use98 // the pointer values for Base because these are non-deterministic.99 // To make sure that the sort order is stable, we first assign to each atom100 // base value an index based on its order of appearance in the chain of101 // comparisons. We call this index `BaseOrdering`. For example, for:102 // b[3] == c[2] && a[1] == d[1] && b[4] == c[3]103 // | block 1 | | block 2 | | block 3 |104 // b gets assigned index 0 and a index 1, because b appears as LHS in block 1,105 // which is before block 2.106 // We then sort by (BaseOrdering[LHS.Base()], LHS.Offset), which is stable.107 bool operator<(const BCEAtom &O) const {108 return BaseId != O.BaseId ? BaseId < O.BaseId : Offset.slt(O.Offset);109 }110 111 GetElementPtrInst *GEP = nullptr;112 LoadInst *LoadI = nullptr;113 unsigned BaseId = 0;114 APInt Offset;115};116 117// A class that assigns increasing ids to values in the order in which they are118// seen. See comment in `BCEAtom::operator<()``.119class BaseIdentifier {120public:121 // Returns the id for value `Base`, after assigning one if `Base` has not been122 // seen before.123 int getBaseId(const Value *Base) {124 assert(Base && "invalid base");125 const auto Insertion = BaseToIndex.try_emplace(Base, Order);126 if (Insertion.second)127 ++Order;128 return Insertion.first->second;129 }130 131private:132 unsigned Order = 1;133 DenseMap<const Value*, int> BaseToIndex;134};135} // namespace136 137// If this value is a load from a constant offset w.r.t. a base address, and138// there are no other users of the load or address, returns the base address and139// the offset.140static BCEAtom visitICmpLoadOperand(Value *const Val, BaseIdentifier &BaseId) {141 auto *const LoadI = dyn_cast<LoadInst>(Val);142 if (!LoadI)143 return {};144 LLVM_DEBUG(dbgs() << "load\n");145 if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {146 LLVM_DEBUG(dbgs() << "used outside of block\n");147 return {};148 }149 // Do not optimize atomic loads to non-atomic memcmp150 if (!LoadI->isSimple()) {151 LLVM_DEBUG(dbgs() << "volatile or atomic\n");152 return {};153 }154 Value *Addr = LoadI->getOperand(0);155 if (Addr->getType()->getPointerAddressSpace() != 0) {156 LLVM_DEBUG(dbgs() << "from non-zero AddressSpace\n");157 return {};158 }159 const auto &DL = LoadI->getDataLayout();160 if (!isDereferenceablePointer(Addr, LoadI->getType(), DL)) {161 LLVM_DEBUG(dbgs() << "not dereferenceable\n");162 // We need to make sure that we can do comparison in any order, so we163 // require memory to be unconditionally dereferenceable.164 return {};165 }166 167 APInt Offset = APInt(DL.getIndexTypeSizeInBits(Addr->getType()), 0);168 Value *Base = Addr;169 auto *GEP = dyn_cast<GetElementPtrInst>(Addr);170 if (GEP) {171 LLVM_DEBUG(dbgs() << "GEP\n");172 if (GEP->isUsedOutsideOfBlock(LoadI->getParent())) {173 LLVM_DEBUG(dbgs() << "used outside of block\n");174 return {};175 }176 if (!GEP->accumulateConstantOffset(DL, Offset))177 return {};178 Base = GEP->getPointerOperand();179 }180 return BCEAtom(GEP, LoadI, BaseId.getBaseId(Base), Offset);181}182 183namespace {184// A comparison between two BCE atoms, e.g. `a == o.a` in the example at the185// top.186// Note: the terminology is misleading: the comparison is symmetric, so there187// is no real {l/r}hs. What we want though is to have the same base on the188// left (resp. right), so that we can detect consecutive loads. To ensure this189// we put the smallest atom on the left.190struct BCECmp {191 BCEAtom Lhs;192 BCEAtom Rhs;193 int SizeBits;194 const ICmpInst *CmpI;195 196 BCECmp(BCEAtom L, BCEAtom R, int SizeBits, const ICmpInst *CmpI)197 : Lhs(std::move(L)), Rhs(std::move(R)), SizeBits(SizeBits), CmpI(CmpI) {198 if (Rhs < Lhs) std::swap(Rhs, Lhs);199 }200};201 202// A basic block with a comparison between two BCE atoms.203// The block might do extra work besides the atom comparison, in which case204// doesOtherWork() returns true. Under some conditions, the block can be205// split into the atom comparison part and the "other work" part206// (see canSplit()).207class BCECmpBlock {208 public:209 typedef SmallDenseSet<const Instruction *, 8> InstructionSet;210 211 BCECmpBlock(BCECmp Cmp, BasicBlock *BB, InstructionSet BlockInsts)212 : BB(BB), BlockInsts(std::move(BlockInsts)), Cmp(std::move(Cmp)) {}213 214 const BCEAtom &Lhs() const { return Cmp.Lhs; }215 const BCEAtom &Rhs() const { return Cmp.Rhs; }216 int SizeBits() const { return Cmp.SizeBits; }217 218 // Returns true if the block does other works besides comparison.219 bool doesOtherWork() const;220 221 // Returns true if the non-BCE-cmp instructions can be separated from BCE-cmp222 // instructions in the block.223 bool canSplit(AliasAnalysis &AA) const;224 225 // Return true if this all the relevant instructions in the BCE-cmp-block can226 // be sunk below this instruction. By doing this, we know we can separate the227 // BCE-cmp-block instructions from the non-BCE-cmp-block instructions in the228 // block.229 bool canSinkBCECmpInst(const Instruction *, AliasAnalysis &AA) const;230 231 // We can separate the BCE-cmp-block instructions and the non-BCE-cmp-block232 // instructions. Split the old block and move all non-BCE-cmp-insts into the233 // new parent block.234 void split(BasicBlock *NewParent, AliasAnalysis &AA) const;235 236 // The basic block where this comparison happens.237 BasicBlock *BB;238 // Instructions relating to the BCECmp and branch.239 InstructionSet BlockInsts;240 // The block requires splitting.241 bool RequireSplit = false;242 // Original order of this block in the chain.243 unsigned OrigOrder = 0;244 245private:246 BCECmp Cmp;247};248} // namespace249 250bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst,251 AliasAnalysis &AA) const {252 // If this instruction may clobber the loads and is in middle of the BCE cmp253 // block instructions, then bail for now.254 if (Inst->mayWriteToMemory()) {255 auto MayClobber = [&](LoadInst *LI) {256 // If a potentially clobbering instruction comes before the load,257 // we can still safely sink the load.258 return (Inst->getParent() != LI->getParent() || !Inst->comesBefore(LI)) &&259 isModSet(AA.getModRefInfo(Inst, MemoryLocation::get(LI)));260 };261 if (MayClobber(Cmp.Lhs.LoadI) || MayClobber(Cmp.Rhs.LoadI))262 return false;263 }264 // Make sure this instruction does not use any of the BCE cmp block265 // instructions as operand.266 return llvm::none_of(Inst->operands(), [&](const Value *Op) {267 const Instruction *OpI = dyn_cast<Instruction>(Op);268 return OpI && BlockInsts.contains(OpI);269 });270}271 272void BCECmpBlock::split(BasicBlock *NewParent, AliasAnalysis &AA) const {273 llvm::SmallVector<Instruction *, 4> OtherInsts;274 for (Instruction &Inst : *BB) {275 if (BlockInsts.count(&Inst))276 continue;277 assert(canSinkBCECmpInst(&Inst, AA) && "Split unsplittable block");278 // This is a non-BCE-cmp-block instruction. And it can be separated279 // from the BCE-cmp-block instruction.280 OtherInsts.push_back(&Inst);281 }282 283 // Do the actual spliting.284 for (Instruction *Inst : reverse(OtherInsts))285 Inst->moveBeforePreserving(*NewParent, NewParent->begin());286}287 288bool BCECmpBlock::canSplit(AliasAnalysis &AA) const {289 for (Instruction &Inst : *BB) {290 if (!BlockInsts.count(&Inst)) {291 if (!canSinkBCECmpInst(&Inst, AA))292 return false;293 }294 }295 return true;296}297 298bool BCECmpBlock::doesOtherWork() const {299 // TODO(courbet): Can we allow some other things ? This is very conservative.300 // We might be able to get away with anything does not have any side301 // effects outside of the basic block.302 // Note: The GEPs and/or loads are not necessarily in the same block.303 for (const Instruction &Inst : *BB) {304 if (!BlockInsts.count(&Inst))305 return true;306 }307 return false;308}309 310// Visit the given comparison. If this is a comparison between two valid311// BCE atoms, returns the comparison.312static std::optional<BCECmp>313visitICmp(const ICmpInst *const CmpI,314 const ICmpInst::Predicate ExpectedPredicate, BaseIdentifier &BaseId) {315 // The comparison can only be used once:316 // - For intermediate blocks, as a branch condition.317 // - For the final block, as an incoming value for the Phi.318 // If there are any other uses of the comparison, we cannot merge it with319 // other comparisons as we would create an orphan use of the value.320 if (!CmpI->hasOneUse()) {321 LLVM_DEBUG(dbgs() << "cmp has several uses\n");322 return std::nullopt;323 }324 if (CmpI->getPredicate() != ExpectedPredicate)325 return std::nullopt;326 LLVM_DEBUG(dbgs() << "cmp "327 << (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne")328 << "\n");329 auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0), BaseId);330 if (!Lhs.BaseId)331 return std::nullopt;332 auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1), BaseId);333 if (!Rhs.BaseId)334 return std::nullopt;335 const auto &DL = CmpI->getDataLayout();336 return BCECmp(std::move(Lhs), std::move(Rhs),337 DL.getTypeSizeInBits(CmpI->getOperand(0)->getType()), CmpI);338}339 340// Visit the given comparison block. If this is a comparison between two valid341// BCE atoms, returns the comparison.342static std::optional<BCECmpBlock>343visitCmpBlock(Value *const Val, BasicBlock *const Block,344 const BasicBlock *const PhiBlock, BaseIdentifier &BaseId) {345 if (Block->empty())346 return std::nullopt;347 auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator());348 if (!BranchI)349 return std::nullopt;350 LLVM_DEBUG(dbgs() << "branch\n");351 Value *Cond;352 ICmpInst::Predicate ExpectedPredicate;353 if (BranchI->isUnconditional()) {354 // In this case, we expect an incoming value which is the result of the355 // comparison. This is the last link in the chain of comparisons (note356 // that this does not mean that this is the last incoming value, blocks357 // can be reordered).358 Cond = Val;359 ExpectedPredicate = ICmpInst::ICMP_EQ;360 } else {361 // In this case, we expect a constant incoming value (the comparison is362 // chained).363 const auto *const Const = cast<ConstantInt>(Val);364 LLVM_DEBUG(dbgs() << "const\n");365 if (!Const->isZero())366 return std::nullopt;367 LLVM_DEBUG(dbgs() << "false\n");368 assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch");369 BasicBlock *const FalseBlock = BranchI->getSuccessor(1);370 Cond = BranchI->getCondition();371 ExpectedPredicate =372 FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;373 }374 375 auto *CmpI = dyn_cast<ICmpInst>(Cond);376 if (!CmpI)377 return std::nullopt;378 LLVM_DEBUG(dbgs() << "icmp\n");379 380 std::optional<BCECmp> Result = visitICmp(CmpI, ExpectedPredicate, BaseId);381 if (!Result)382 return std::nullopt;383 384 BCECmpBlock::InstructionSet BlockInsts(385 {Result->Lhs.LoadI, Result->Rhs.LoadI, Result->CmpI, BranchI});386 if (Result->Lhs.GEP)387 BlockInsts.insert(Result->Lhs.GEP);388 if (Result->Rhs.GEP)389 BlockInsts.insert(Result->Rhs.GEP);390 return BCECmpBlock(std::move(*Result), Block, BlockInsts);391}392 393static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons,394 BCECmpBlock &&Comparison) {395 LLVM_DEBUG(dbgs() << "Block '" << Comparison.BB->getName()396 << "': Found cmp of " << Comparison.SizeBits()397 << " bits between " << Comparison.Lhs().BaseId << " + "398 << Comparison.Lhs().Offset << " and "399 << Comparison.Rhs().BaseId << " + "400 << Comparison.Rhs().Offset << "\n");401 LLVM_DEBUG(dbgs() << "\n");402 Comparison.OrigOrder = Comparisons.size();403 Comparisons.push_back(std::move(Comparison));404}405 406namespace {407// A chain of comparisons.408class BCECmpChain {409public:410 using ContiguousBlocks = std::vector<BCECmpBlock>;411 412 BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,413 AliasAnalysis &AA);414 415 bool simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA,416 DomTreeUpdater &DTU);417 418 bool atLeastOneMerged() const {419 return any_of(MergedBlocks_,420 [](const auto &Blocks) { return Blocks.size() > 1; });421 }422 423private:424 PHINode &Phi_;425 // The list of all blocks in the chain, grouped by contiguity.426 std::vector<ContiguousBlocks> MergedBlocks_;427 // The original entry block (before sorting);428 BasicBlock *EntryBlock_;429};430} // namespace431 432static bool areContiguous(const BCECmpBlock &First, const BCECmpBlock &Second) {433 return First.Lhs().BaseId == Second.Lhs().BaseId &&434 First.Rhs().BaseId == Second.Rhs().BaseId &&435 First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset &&436 First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset;437}438 439static unsigned getMinOrigOrder(const BCECmpChain::ContiguousBlocks &Blocks) {440 unsigned MinOrigOrder = std::numeric_limits<unsigned>::max();441 for (const BCECmpBlock &Block : Blocks)442 MinOrigOrder = std::min(MinOrigOrder, Block.OrigOrder);443 return MinOrigOrder;444}445 446/// Given a chain of comparison blocks, groups the blocks into contiguous447/// ranges that can be merged together into a single comparison.448static std::vector<BCECmpChain::ContiguousBlocks>449mergeBlocks(std::vector<BCECmpBlock> &&Blocks) {450 std::vector<BCECmpChain::ContiguousBlocks> MergedBlocks;451 452 // Sort to detect continuous offsets.453 llvm::sort(Blocks,454 [](const BCECmpBlock &LhsBlock, const BCECmpBlock &RhsBlock) {455 return std::tie(LhsBlock.Lhs(), LhsBlock.Rhs()) <456 std::tie(RhsBlock.Lhs(), RhsBlock.Rhs());457 });458 459 BCECmpChain::ContiguousBlocks *LastMergedBlock = nullptr;460 for (BCECmpBlock &Block : Blocks) {461 if (!LastMergedBlock || !areContiguous(LastMergedBlock->back(), Block)) {462 MergedBlocks.emplace_back();463 LastMergedBlock = &MergedBlocks.back();464 } else {465 LLVM_DEBUG(dbgs() << "Merging block " << Block.BB->getName() << " into "466 << LastMergedBlock->back().BB->getName() << "\n");467 }468 LastMergedBlock->push_back(std::move(Block));469 }470 471 // While we allow reordering for merging, do not reorder unmerged comparisons.472 // Doing so may introduce branch on poison.473 llvm::sort(MergedBlocks, [](const BCECmpChain::ContiguousBlocks &LhsBlocks,474 const BCECmpChain::ContiguousBlocks &RhsBlocks) {475 return getMinOrigOrder(LhsBlocks) < getMinOrigOrder(RhsBlocks);476 });477 478 return MergedBlocks;479}480 481BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,482 AliasAnalysis &AA)483 : Phi_(Phi) {484 assert(!Blocks.empty() && "a chain should have at least one block");485 // Now look inside blocks to check for BCE comparisons.486 std::vector<BCECmpBlock> Comparisons;487 BaseIdentifier BaseId;488 for (BasicBlock *const Block : Blocks) {489 assert(Block && "invalid block");490 if (Block->hasAddressTaken()) {491 LLVM_DEBUG(dbgs() << "cannot merge blocks with blockaddress\n");492 return;493 }494 std::optional<BCECmpBlock> Comparison = visitCmpBlock(495 Phi.getIncomingValueForBlock(Block), Block, Phi.getParent(), BaseId);496 if (!Comparison) {497 LLVM_DEBUG(dbgs() << "chain with invalid BCECmpBlock, no merge.\n");498 return;499 }500 if (Comparison->doesOtherWork()) {501 LLVM_DEBUG(dbgs() << "block '" << Comparison->BB->getName()502 << "' does extra work besides compare\n");503 if (Comparisons.empty()) {504 // This is the initial block in the chain, in case this block does other505 // work, we can try to split the block and move the irrelevant506 // instructions to the predecessor.507 //508 // If this is not the initial block in the chain, splitting it wont509 // work.510 //511 // As once split, there will still be instructions before the BCE cmp512 // instructions that do other work in program order, i.e. within the513 // chain before sorting. Unless we can abort the chain at this point514 // and start anew.515 //516 // NOTE: we only handle blocks a with single predecessor for now.517 if (Comparison->canSplit(AA)) {518 LLVM_DEBUG(dbgs()519 << "Split initial block '" << Comparison->BB->getName()520 << "' that does extra work besides compare\n");521 Comparison->RequireSplit = true;522 enqueueBlock(Comparisons, std::move(*Comparison));523 } else {524 LLVM_DEBUG(dbgs()525 << "ignoring initial block '" << Comparison->BB->getName()526 << "' that does extra work besides compare\n");527 }528 continue;529 }530 // TODO(courbet): Right now we abort the whole chain. We could be531 // merging only the blocks that don't do other work and resume the532 // chain from there. For example:533 // if (a[0] == b[0]) { // bb1534 // if (a[1] == b[1]) { // bb2535 // some_value = 3; //bb3536 // if (a[2] == b[2]) { //bb3537 // do a ton of stuff //bb4538 // }539 // }540 // }541 //542 // This is:543 //544 // bb1 --eq--> bb2 --eq--> bb3* -eq--> bb4 --+545 // \ \ \ \546 // ne ne ne \547 // \ \ \ v548 // +------------+-----------+----------> bb_phi549 //550 // We can only merge the first two comparisons, because bb3* does551 // "other work" (setting some_value to 3).552 // We could still merge bb1 and bb2 though.553 return;554 }555 enqueueBlock(Comparisons, std::move(*Comparison));556 }557 558 // It is possible we have no suitable comparison to merge.559 if (Comparisons.empty()) {560 LLVM_DEBUG(dbgs() << "chain with no BCE basic blocks, no merge\n");561 return;562 }563 EntryBlock_ = Comparisons[0].BB;564 MergedBlocks_ = mergeBlocks(std::move(Comparisons));565}566 567namespace {568 569// A class to compute the name of a set of merged basic blocks.570// This is optimized for the common case of no block names.571class MergedBlockName {572 // Storage for the uncommon case of several named blocks.573 SmallString<16> Scratch;574 575public:576 explicit MergedBlockName(ArrayRef<BCECmpBlock> Comparisons)577 : Name(makeName(Comparisons)) {}578 const StringRef Name;579 580private:581 StringRef makeName(ArrayRef<BCECmpBlock> Comparisons) {582 assert(!Comparisons.empty() && "no basic block");583 // Fast path: only one block, or no names at all.584 if (Comparisons.size() == 1)585 return Comparisons[0].BB->getName();586 const int size = std::accumulate(Comparisons.begin(), Comparisons.end(), 0,587 [](int i, const BCECmpBlock &Cmp) {588 return i + Cmp.BB->getName().size();589 });590 if (size == 0)591 return StringRef("", 0);592 593 // Slow path: at least two blocks, at least one block with a name.594 Scratch.clear();595 // We'll have `size` bytes for name and `Comparisons.size() - 1` bytes for596 // separators.597 Scratch.reserve(size + Comparisons.size() - 1);598 const auto append = [this](StringRef str) {599 Scratch.append(str.begin(), str.end());600 };601 append(Comparisons[0].BB->getName());602 for (int I = 1, E = Comparisons.size(); I < E; ++I) {603 const BasicBlock *const BB = Comparisons[I].BB;604 if (!BB->getName().empty()) {605 append("+");606 append(BB->getName());607 }608 }609 return Scratch.str();610 }611};612} // namespace613 614/// Determine the branch weights for the resulting conditional branch, resulting615/// after merging \p Comparisons.616static std::optional<SmallVector<uint32_t, 2>>617computeMergedBranchWeights(ArrayRef<BCECmpBlock> Comparisons) {618 assert(!Comparisons.empty());619 if (ProfcheckDisableMetadataFixes)620 return std::nullopt;621 if (Comparisons.size() == 1) {622 SmallVector<uint32_t, 2> Weights;623 if (!extractBranchWeights(*Comparisons[0].BB->getTerminator(), Weights))624 return std::nullopt;625 return Weights;626 }627 // The probability to go to the phi block is the disjunction of the628 // probability to go to the phi block from the individual Comparisons. We'll629 // swap the weights because `getDisjunctionWeights` computes the disjunction630 // for the "true" branch, then swap back.631 SmallVector<uint64_t, 2> Weights{0, 1};632 // At this point, Weights encodes "0-probability" for the "true" side.633 for (const auto &C : Comparisons) {634 SmallVector<uint32_t, 2> W;635 if (!extractBranchWeights(*C.BB->getTerminator(), W))636 return std::nullopt;637 638 std::swap(W[0], W[1]);639 Weights = getDisjunctionWeights(Weights, W);640 }641 std::swap(Weights[0], Weights[1]);642 return fitWeights(Weights);643}644 645// Merges the given contiguous comparison blocks into one memcmp block.646static BasicBlock *mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,647 BasicBlock *const InsertBefore,648 BasicBlock *const NextCmpBlock,649 PHINode &Phi, const TargetLibraryInfo &TLI,650 AliasAnalysis &AA, DomTreeUpdater &DTU) {651 assert(!Comparisons.empty() && "merging zero comparisons");652 LLVMContext &Context = NextCmpBlock->getContext();653 const BCECmpBlock &FirstCmp = Comparisons[0];654 655 // Create a new cmp block before next cmp block.656 BasicBlock *const BB =657 BasicBlock::Create(Context, MergedBlockName(Comparisons).Name,658 NextCmpBlock->getParent(), InsertBefore);659 IRBuilder<> Builder(BB);660 // Add the GEPs from the first BCECmpBlock.661 Value *Lhs, *Rhs;662 if (FirstCmp.Lhs().GEP)663 Lhs = Builder.Insert(FirstCmp.Lhs().GEP->clone());664 else665 Lhs = FirstCmp.Lhs().LoadI->getPointerOperand();666 if (FirstCmp.Rhs().GEP)667 Rhs = Builder.Insert(FirstCmp.Rhs().GEP->clone());668 else669 Rhs = FirstCmp.Rhs().LoadI->getPointerOperand();670 671 Value *IsEqual = nullptr;672 LLVM_DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons -> "673 << BB->getName() << "\n");674 675 // If there is one block that requires splitting, we do it now, i.e.676 // just before we know we will collapse the chain. The instructions677 // can be executed before any of the instructions in the chain.678 const auto *ToSplit = llvm::find_if(679 Comparisons, [](const BCECmpBlock &B) { return B.RequireSplit; });680 if (ToSplit != Comparisons.end()) {681 LLVM_DEBUG(dbgs() << "Splitting non_BCE work to header\n");682 ToSplit->split(BB, AA);683 }684 685 if (Comparisons.size() == 1) {686 LLVM_DEBUG(dbgs() << "Only one comparison, updating branches\n");687 // Use clone to keep the metadata688 Instruction *const LhsLoad = Builder.Insert(FirstCmp.Lhs().LoadI->clone());689 Instruction *const RhsLoad = Builder.Insert(FirstCmp.Rhs().LoadI->clone());690 LhsLoad->replaceUsesOfWith(LhsLoad->getOperand(0), Lhs);691 RhsLoad->replaceUsesOfWith(RhsLoad->getOperand(0), Rhs);692 // There are no blocks to merge, just do the comparison.693 // If we condition on this IsEqual, we already have its probabilities.694 IsEqual = Builder.CreateICmpEQ(LhsLoad, RhsLoad);695 } else {696 const unsigned TotalSizeBits = std::accumulate(697 Comparisons.begin(), Comparisons.end(), 0u,698 [](int Size, const BCECmpBlock &C) { return Size + C.SizeBits(); });699 700 // memcmp expects a 'size_t' argument and returns 'int'.701 unsigned SizeTBits = TLI.getSizeTSize(*Phi.getModule());702 unsigned IntBits = TLI.getIntSize();703 704 // Create memcmp() == 0.705 const auto &DL = Phi.getDataLayout();706 Value *const MemCmpCall = emitMemCmp(707 Lhs, Rhs,708 ConstantInt::get(Builder.getIntNTy(SizeTBits), TotalSizeBits / 8),709 Builder, DL, &TLI);710 IsEqual = Builder.CreateICmpEQ(711 MemCmpCall, ConstantInt::get(Builder.getIntNTy(IntBits), 0));712 }713 714 BasicBlock *const PhiBB = Phi.getParent();715 // Add a branch to the next basic block in the chain.716 if (NextCmpBlock == PhiBB) {717 // Continue to phi, passing it the comparison result.718 Builder.CreateBr(PhiBB);719 Phi.addIncoming(IsEqual, BB);720 DTU.applyUpdates({{DominatorTree::Insert, BB, PhiBB}});721 } else {722 // Continue to next block if equal, exit to phi else.723 auto *BI = Builder.CreateCondBr(IsEqual, NextCmpBlock, PhiBB);724 if (auto BranchWeights = computeMergedBranchWeights(Comparisons))725 setBranchWeights(*BI, BranchWeights.value(), /*IsExpected=*/false);726 Phi.addIncoming(ConstantInt::getFalse(Context), BB);727 DTU.applyUpdates({{DominatorTree::Insert, BB, NextCmpBlock},728 {DominatorTree::Insert, BB, PhiBB}});729 }730 return BB;731}732 733bool BCECmpChain::simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA,734 DomTreeUpdater &DTU) {735 assert(atLeastOneMerged() && "simplifying trivial BCECmpChain");736 LLVM_DEBUG(dbgs() << "Simplifying comparison chain starting at block "737 << EntryBlock_->getName() << "\n");738 739 // Effectively merge blocks. We go in the reverse direction from the phi block740 // so that the next block is always available to branch to.741 BasicBlock *InsertBefore = EntryBlock_;742 BasicBlock *NextCmpBlock = Phi_.getParent();743 for (const auto &Blocks : reverse(MergedBlocks_)) {744 InsertBefore = NextCmpBlock = mergeComparisons(745 Blocks, InsertBefore, NextCmpBlock, Phi_, TLI, AA, DTU);746 }747 748 // Replace the original cmp chain with the new cmp chain by pointing all749 // predecessors of EntryBlock_ to NextCmpBlock instead. This makes all cmp750 // blocks in the old chain unreachable.751 while (!pred_empty(EntryBlock_)) {752 BasicBlock* const Pred = *pred_begin(EntryBlock_);753 LLVM_DEBUG(dbgs() << "Updating jump into old chain from " << Pred->getName()754 << "\n");755 Pred->getTerminator()->replaceUsesOfWith(EntryBlock_, NextCmpBlock);756 DTU.applyUpdates({{DominatorTree::Delete, Pred, EntryBlock_},757 {DominatorTree::Insert, Pred, NextCmpBlock}});758 }759 760 // If the old cmp chain was the function entry, we need to update the function761 // entry.762 const bool ChainEntryIsFnEntry = EntryBlock_->isEntryBlock();763 if (ChainEntryIsFnEntry && DTU.hasDomTree()) {764 LLVM_DEBUG(dbgs() << "Changing function entry from "765 << EntryBlock_->getName() << " to "766 << NextCmpBlock->getName() << "\n");767 DTU.getDomTree().setNewRoot(NextCmpBlock);768 DTU.applyUpdates({{DominatorTree::Delete, NextCmpBlock, EntryBlock_}});769 }770 EntryBlock_ = nullptr;771 772 // Delete merged blocks. This also removes incoming values in phi.773 SmallVector<BasicBlock *, 16> DeadBlocks;774 for (const auto &Blocks : MergedBlocks_) {775 for (const BCECmpBlock &Block : Blocks) {776 LLVM_DEBUG(dbgs() << "Deleting merged block " << Block.BB->getName()777 << "\n");778 DeadBlocks.push_back(Block.BB);779 }780 }781 DeleteDeadBlocks(DeadBlocks, &DTU);782 783 MergedBlocks_.clear();784 return true;785}786 787static std::vector<BasicBlock *>788getOrderedBlocks(PHINode &Phi, BasicBlock *const LastBlock, int NumBlocks) {789 // Walk up from the last block to find other blocks.790 std::vector<BasicBlock *> Blocks(NumBlocks);791 assert(LastBlock && "invalid last block");792 BasicBlock *CurBlock = LastBlock;793 for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) {794 if (CurBlock->hasAddressTaken()) {795 // Somebody is jumping to the block through an address, all bets are796 // off.797 LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex798 << " has its address taken\n");799 return {};800 }801 Blocks[BlockIndex] = CurBlock;802 auto *SinglePredecessor = CurBlock->getSinglePredecessor();803 if (!SinglePredecessor) {804 // The block has two or more predecessors.805 LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex806 << " has two or more predecessors\n");807 return {};808 }809 if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) {810 // The block does not link back to the phi.811 LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex812 << " does not link back to the phi\n");813 return {};814 }815 CurBlock = SinglePredecessor;816 }817 Blocks[0] = CurBlock;818 return Blocks;819}820 821static bool processPhi(PHINode &Phi, const TargetLibraryInfo &TLI,822 AliasAnalysis &AA, DomTreeUpdater &DTU) {823 LLVM_DEBUG(dbgs() << "processPhi()\n");824 if (Phi.getNumIncomingValues() <= 1) {825 LLVM_DEBUG(dbgs() << "skip: only one incoming value in phi\n");826 return false;827 }828 // We are looking for something that has the following structure:829 // bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+830 // \ \ \ \831 // ne ne ne \832 // \ \ \ v833 // +------------+-----------+----------> bb_phi834 //835 // - The last basic block (bb4 here) must branch unconditionally to bb_phi.836 // It's the only block that contributes a non-constant value to the Phi.837 // - All other blocks (b1, b2, b3) must have exactly two successors, one of838 // them being the phi block.839 // - All intermediate blocks (bb2, bb3) must have only one predecessor.840 // - Blocks cannot do other work besides the comparison, see doesOtherWork()841 842 // The blocks are not necessarily ordered in the phi, so we start from the843 // last block and reconstruct the order.844 BasicBlock *LastBlock = nullptr;845 for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) {846 if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue;847 if (LastBlock) {848 // There are several non-constant values.849 LLVM_DEBUG(dbgs() << "skip: several non-constant values\n");850 return false;851 }852 if (!isa<ICmpInst>(Phi.getIncomingValue(I)) ||853 cast<ICmpInst>(Phi.getIncomingValue(I))->getParent() !=854 Phi.getIncomingBlock(I)) {855 // Non-constant incoming value is not from a cmp instruction or not856 // produced by the last block. We could end up processing the value857 // producing block more than once.858 //859 // This is an uncommon case, so we bail.860 LLVM_DEBUG(861 dbgs()862 << "skip: non-constant value not from cmp or not from last block.\n");863 return false;864 }865 LastBlock = Phi.getIncomingBlock(I);866 }867 if (!LastBlock) {868 // There is no non-constant block.869 LLVM_DEBUG(dbgs() << "skip: no non-constant block\n");870 return false;871 }872 if (LastBlock->getSingleSuccessor() != Phi.getParent()) {873 LLVM_DEBUG(dbgs() << "skip: last block non-phi successor\n");874 return false;875 }876 877 const auto Blocks =878 getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues());879 if (Blocks.empty()) return false;880 BCECmpChain CmpChain(Blocks, Phi, AA);881 882 if (!CmpChain.atLeastOneMerged()) {883 LLVM_DEBUG(dbgs() << "skip: nothing merged\n");884 return false;885 }886 887 return CmpChain.simplify(TLI, AA, DTU);888}889 890static bool runImpl(Function &F, const TargetLibraryInfo &TLI,891 const TargetTransformInfo &TTI, AliasAnalysis &AA,892 DominatorTree *DT) {893 LLVM_DEBUG(dbgs() << "MergeICmpsLegacyPass: " << F.getName() << "\n");894 895 // We only try merging comparisons if the target wants to expand memcmp later.896 // The rationale is to avoid turning small chains into memcmp calls.897 if (!TTI.enableMemCmpExpansion(F.hasOptSize(), true))898 return false;899 900 // If we don't have memcmp avaiable we can't emit calls to it.901 if (!TLI.has(LibFunc_memcmp))902 return false;903 904 DomTreeUpdater DTU(DT, /*PostDominatorTree*/ nullptr,905 DomTreeUpdater::UpdateStrategy::Eager);906 907 bool MadeChange = false;908 909 for (BasicBlock &BB : llvm::drop_begin(F)) {910 // A Phi operation is always first in a basic block.911 if (auto *const Phi = dyn_cast<PHINode>(&*BB.begin()))912 MadeChange |= processPhi(*Phi, TLI, AA, DTU);913 }914 915 return MadeChange;916}917 918namespace {919class MergeICmpsLegacyPass : public FunctionPass {920public:921 static char ID;922 923 MergeICmpsLegacyPass() : FunctionPass(ID) {924 initializeMergeICmpsLegacyPassPass(*PassRegistry::getPassRegistry());925 }926 927 bool runOnFunction(Function &F) override {928 if (skipFunction(F)) return false;929 const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);930 const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);931 // MergeICmps does not need the DominatorTree, but we update it if it's932 // already available.933 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();934 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();935 return runImpl(F, TLI, TTI, AA, DTWP ? &DTWP->getDomTree() : nullptr);936 }937 938 private:939 void getAnalysisUsage(AnalysisUsage &AU) const override {940 AU.addRequired<TargetLibraryInfoWrapperPass>();941 AU.addRequired<TargetTransformInfoWrapperPass>();942 AU.addRequired<AAResultsWrapperPass>();943 AU.addPreserved<GlobalsAAWrapperPass>();944 AU.addPreserved<DominatorTreeWrapperPass>();945 }946};947 948} // namespace949 950char MergeICmpsLegacyPass::ID = 0;951INITIALIZE_PASS_BEGIN(MergeICmpsLegacyPass, "mergeicmps",952 "Merge contiguous icmps into a memcmp", false, false)953INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)954INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)955INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)956INITIALIZE_PASS_END(MergeICmpsLegacyPass, "mergeicmps",957 "Merge contiguous icmps into a memcmp", false, false)958 959Pass *llvm::createMergeICmpsLegacyPass() { return new MergeICmpsLegacyPass(); }960 961PreservedAnalyses MergeICmpsPass::run(Function &F,962 FunctionAnalysisManager &AM) {963 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);964 auto &TTI = AM.getResult<TargetIRAnalysis>(F);965 auto &AA = AM.getResult<AAManager>(F);966 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);967 const bool MadeChanges = runImpl(F, TLI, TTI, AA, DT);968 if (!MadeChanges)969 return PreservedAnalyses::all();970 PreservedAnalyses PA;971 PA.preserve<DominatorTreeAnalysis>();972 return PA;973}974