diff options
Diffstat (limited to 'llvm/lib/Transforms/Scalar/MergeICmps.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Scalar/MergeICmps.cpp | 945 |
1 files changed, 945 insertions, 0 deletions
diff --git a/llvm/lib/Transforms/Scalar/MergeICmps.cpp b/llvm/lib/Transforms/Scalar/MergeICmps.cpp new file mode 100644 index 000000000000..98a45b391319 --- /dev/null +++ b/llvm/lib/Transforms/Scalar/MergeICmps.cpp @@ -0,0 +1,945 @@ +//===- MergeICmps.cpp - Optimize chains of integer comparisons ------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This pass turns chains of integer comparisons into memcmp (the memcmp is +// later typically inlined as a chain of efficient hardware comparisons). This +// typically benefits c++ member or nonmember operator==(). +// +// The basic idea is to replace a longer chain of integer comparisons loaded +// from contiguous memory locations into a shorter chain of larger integer +// comparisons. Benefits are double: +// - There are less jumps, and therefore less opportunities for mispredictions +// and I-cache misses. +// - Code size is smaller, both because jumps are removed and because the +// encoding of a 2*n byte compare is smaller than that of two n-byte +// compares. +// +// Example: +// +// struct S { +// int a; +// char b; +// char c; +// uint16_t d; +// bool operator==(const S& o) const { +// return a == o.a && b == o.b && c == o.c && d == o.d; +// } +// }; +// +// Is optimized as : +// +// bool S::operator==(const S& o) const { +// return memcmp(this, &o, 8) == 0; +// } +// +// Which will later be expanded (ExpandMemCmp) as a single 8-bytes icmp. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/MergeICmps.h" +#include "llvm/Analysis/DomTreeUpdater.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/Loads.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/Pass.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/BuildLibCalls.h" +#include <algorithm> +#include <numeric> +#include <utility> +#include <vector> + +using namespace llvm; + +namespace { + +#define DEBUG_TYPE "mergeicmps" + +// Returns true if the instruction is a simple load or a simple store +static bool isSimpleLoadOrStore(const Instruction *I) { + if (const LoadInst *LI = dyn_cast<LoadInst>(I)) + return LI->isSimple(); + if (const StoreInst *SI = dyn_cast<StoreInst>(I)) + return SI->isSimple(); + return false; +} + +// A BCE atom "Binary Compare Expression Atom" represents an integer load +// that is a constant offset from a base value, e.g. `a` or `o.c` in the example +// at the top. +struct BCEAtom { + BCEAtom() = default; + BCEAtom(GetElementPtrInst *GEP, LoadInst *LoadI, int BaseId, APInt Offset) + : GEP(GEP), LoadI(LoadI), BaseId(BaseId), Offset(Offset) {} + + BCEAtom(const BCEAtom &) = delete; + BCEAtom &operator=(const BCEAtom &) = delete; + + BCEAtom(BCEAtom &&that) = default; + BCEAtom &operator=(BCEAtom &&that) { + if (this == &that) + return *this; + GEP = that.GEP; + LoadI = that.LoadI; + BaseId = that.BaseId; + Offset = std::move(that.Offset); + return *this; + } + + // We want to order BCEAtoms by (Base, Offset). However we cannot use + // the pointer values for Base because these are non-deterministic. + // To make sure that the sort order is stable, we first assign to each atom + // base value an index based on its order of appearance in the chain of + // comparisons. We call this index `BaseOrdering`. For example, for: + // b[3] == c[2] && a[1] == d[1] && b[4] == c[3] + // | block 1 | | block 2 | | block 3 | + // b gets assigned index 0 and a index 1, because b appears as LHS in block 1, + // which is before block 2. + // We then sort by (BaseOrdering[LHS.Base()], LHS.Offset), which is stable. + bool operator<(const BCEAtom &O) const { + return BaseId != O.BaseId ? BaseId < O.BaseId : Offset.slt(O.Offset); + } + + GetElementPtrInst *GEP = nullptr; + LoadInst *LoadI = nullptr; + unsigned BaseId = 0; + APInt Offset; +}; + +// A class that assigns increasing ids to values in the order in which they are +// seen. See comment in `BCEAtom::operator<()``. +class BaseIdentifier { +public: + // Returns the id for value `Base`, after assigning one if `Base` has not been + // seen before. + int getBaseId(const Value *Base) { + assert(Base && "invalid base"); + const auto Insertion = BaseToIndex.try_emplace(Base, Order); + if (Insertion.second) + ++Order; + return Insertion.first->second; + } + +private: + unsigned Order = 1; + DenseMap<const Value*, int> BaseToIndex; +}; + +// If this value is a load from a constant offset w.r.t. a base address, and +// there are no other users of the load or address, returns the base address and +// the offset. +BCEAtom visitICmpLoadOperand(Value *const Val, BaseIdentifier &BaseId) { + auto *const LoadI = dyn_cast<LoadInst>(Val); + if (!LoadI) + return {}; + LLVM_DEBUG(dbgs() << "load\n"); + if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) { + LLVM_DEBUG(dbgs() << "used outside of block\n"); + return {}; + } + // Do not optimize atomic loads to non-atomic memcmp + if (!LoadI->isSimple()) { + LLVM_DEBUG(dbgs() << "volatile or atomic\n"); + return {}; + } + Value *const Addr = LoadI->getOperand(0); + auto *const GEP = dyn_cast<GetElementPtrInst>(Addr); + if (!GEP) + return {}; + LLVM_DEBUG(dbgs() << "GEP\n"); + if (GEP->isUsedOutsideOfBlock(LoadI->getParent())) { + LLVM_DEBUG(dbgs() << "used outside of block\n"); + return {}; + } + const auto &DL = GEP->getModule()->getDataLayout(); + if (!isDereferenceablePointer(GEP, LoadI->getType(), DL)) { + LLVM_DEBUG(dbgs() << "not dereferenceable\n"); + // We need to make sure that we can do comparison in any order, so we + // require memory to be unconditionnally dereferencable. + return {}; + } + APInt Offset = APInt(DL.getPointerTypeSizeInBits(GEP->getType()), 0); + if (!GEP->accumulateConstantOffset(DL, Offset)) + return {}; + return BCEAtom(GEP, LoadI, BaseId.getBaseId(GEP->getPointerOperand()), + Offset); +} + +// A basic block with a comparison between two BCE atoms, e.g. `a == o.a` in the +// example at the top. +// The block might do extra work besides the atom comparison, in which case +// doesOtherWork() returns true. Under some conditions, the block can be +// split into the atom comparison part and the "other work" part +// (see canSplit()). +// Note: the terminology is misleading: the comparison is symmetric, so there +// is no real {l/r}hs. What we want though is to have the same base on the +// left (resp. right), so that we can detect consecutive loads. To ensure this +// we put the smallest atom on the left. +class BCECmpBlock { + public: + BCECmpBlock() {} + + BCECmpBlock(BCEAtom L, BCEAtom R, int SizeBits) + : Lhs_(std::move(L)), Rhs_(std::move(R)), SizeBits_(SizeBits) { + if (Rhs_ < Lhs_) std::swap(Rhs_, Lhs_); + } + + bool IsValid() const { return Lhs_.BaseId != 0 && Rhs_.BaseId != 0; } + + // Assert the block is consistent: If valid, it should also have + // non-null members besides Lhs_ and Rhs_. + void AssertConsistent() const { + if (IsValid()) { + assert(BB); + assert(CmpI); + assert(BranchI); + } + } + + const BCEAtom &Lhs() const { return Lhs_; } + const BCEAtom &Rhs() const { return Rhs_; } + int SizeBits() const { return SizeBits_; } + + // Returns true if the block does other works besides comparison. + bool doesOtherWork() const; + + // Returns true if the non-BCE-cmp instructions can be separated from BCE-cmp + // instructions in the block. + bool canSplit(AliasAnalysis &AA) const; + + // Return true if this all the relevant instructions in the BCE-cmp-block can + // be sunk below this instruction. By doing this, we know we can separate the + // BCE-cmp-block instructions from the non-BCE-cmp-block instructions in the + // block. + bool canSinkBCECmpInst(const Instruction *, DenseSet<Instruction *> &, + AliasAnalysis &AA) const; + + // We can separate the BCE-cmp-block instructions and the non-BCE-cmp-block + // instructions. Split the old block and move all non-BCE-cmp-insts into the + // new parent block. + void split(BasicBlock *NewParent, AliasAnalysis &AA) const; + + // The basic block where this comparison happens. + BasicBlock *BB = nullptr; + // The ICMP for this comparison. + ICmpInst *CmpI = nullptr; + // The terminating branch. + BranchInst *BranchI = nullptr; + // The block requires splitting. + bool RequireSplit = false; + +private: + BCEAtom Lhs_; + BCEAtom Rhs_; + int SizeBits_ = 0; +}; + +bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst, + DenseSet<Instruction *> &BlockInsts, + AliasAnalysis &AA) const { + // If this instruction has side effects and its in middle of the BCE cmp block + // instructions, then bail for now. + if (Inst->mayHaveSideEffects()) { + // Bail if this is not a simple load or store + if (!isSimpleLoadOrStore(Inst)) + return false; + // Disallow stores that might alias the BCE operands + MemoryLocation LLoc = MemoryLocation::get(Lhs_.LoadI); + MemoryLocation RLoc = MemoryLocation::get(Rhs_.LoadI); + if (isModSet(AA.getModRefInfo(Inst, LLoc)) || + isModSet(AA.getModRefInfo(Inst, RLoc))) + return false; + } + // Make sure this instruction does not use any of the BCE cmp block + // instructions as operand. + for (auto BI : BlockInsts) { + if (is_contained(Inst->operands(), BI)) + return false; + } + return true; +} + +void BCECmpBlock::split(BasicBlock *NewParent, AliasAnalysis &AA) const { + DenseSet<Instruction *> BlockInsts( + {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI}); + llvm::SmallVector<Instruction *, 4> OtherInsts; + for (Instruction &Inst : *BB) { + if (BlockInsts.count(&Inst)) + continue; + assert(canSinkBCECmpInst(&Inst, BlockInsts, AA) && + "Split unsplittable block"); + // This is a non-BCE-cmp-block instruction. And it can be separated + // from the BCE-cmp-block instruction. + OtherInsts.push_back(&Inst); + } + + // Do the actual spliting. + for (Instruction *Inst : reverse(OtherInsts)) { + Inst->moveBefore(&*NewParent->begin()); + } +} + +bool BCECmpBlock::canSplit(AliasAnalysis &AA) const { + DenseSet<Instruction *> BlockInsts( + {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI}); + for (Instruction &Inst : *BB) { + if (!BlockInsts.count(&Inst)) { + if (!canSinkBCECmpInst(&Inst, BlockInsts, AA)) + return false; + } + } + return true; +} + +bool BCECmpBlock::doesOtherWork() const { + AssertConsistent(); + // All the instructions we care about in the BCE cmp block. + DenseSet<Instruction *> BlockInsts( + {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI}); + // TODO(courbet): Can we allow some other things ? This is very conservative. + // We might be able to get away with anything does not have any side + // effects outside of the basic block. + // Note: The GEPs and/or loads are not necessarily in the same block. + for (const Instruction &Inst : *BB) { + if (!BlockInsts.count(&Inst)) + return true; + } + return false; +} + +// Visit the given comparison. If this is a comparison between two valid +// BCE atoms, returns the comparison. +BCECmpBlock visitICmp(const ICmpInst *const CmpI, + const ICmpInst::Predicate ExpectedPredicate, + BaseIdentifier &BaseId) { + // The comparison can only be used once: + // - For intermediate blocks, as a branch condition. + // - For the final block, as an incoming value for the Phi. + // If there are any other uses of the comparison, we cannot merge it with + // other comparisons as we would create an orphan use of the value. + if (!CmpI->hasOneUse()) { + LLVM_DEBUG(dbgs() << "cmp has several uses\n"); + return {}; + } + if (CmpI->getPredicate() != ExpectedPredicate) + return {}; + LLVM_DEBUG(dbgs() << "cmp " + << (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne") + << "\n"); + auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0), BaseId); + if (!Lhs.BaseId) + return {}; + auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1), BaseId); + if (!Rhs.BaseId) + return {}; + const auto &DL = CmpI->getModule()->getDataLayout(); + return BCECmpBlock(std::move(Lhs), std::move(Rhs), + DL.getTypeSizeInBits(CmpI->getOperand(0)->getType())); +} + +// Visit the given comparison block. If this is a comparison between two valid +// BCE atoms, returns the comparison. +BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block, + const BasicBlock *const PhiBlock, + BaseIdentifier &BaseId) { + if (Block->empty()) return {}; + auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator()); + if (!BranchI) return {}; + LLVM_DEBUG(dbgs() << "branch\n"); + if (BranchI->isUnconditional()) { + // In this case, we expect an incoming value which is the result of the + // comparison. This is the last link in the chain of comparisons (note + // that this does not mean that this is the last incoming value, blocks + // can be reordered). + auto *const CmpI = dyn_cast<ICmpInst>(Val); + if (!CmpI) return {}; + LLVM_DEBUG(dbgs() << "icmp\n"); + auto Result = visitICmp(CmpI, ICmpInst::ICMP_EQ, BaseId); + Result.CmpI = CmpI; + Result.BranchI = BranchI; + return Result; + } else { + // In this case, we expect a constant incoming value (the comparison is + // chained). + const auto *const Const = dyn_cast<ConstantInt>(Val); + LLVM_DEBUG(dbgs() << "const\n"); + if (!Const->isZero()) return {}; + LLVM_DEBUG(dbgs() << "false\n"); + auto *const CmpI = dyn_cast<ICmpInst>(BranchI->getCondition()); + if (!CmpI) return {}; + LLVM_DEBUG(dbgs() << "icmp\n"); + assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch"); + BasicBlock *const FalseBlock = BranchI->getSuccessor(1); + auto Result = visitICmp( + CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, + BaseId); + Result.CmpI = CmpI; + Result.BranchI = BranchI; + return Result; + } + return {}; +} + +static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons, + BCECmpBlock &&Comparison) { + LLVM_DEBUG(dbgs() << "Block '" << Comparison.BB->getName() + << "': Found cmp of " << Comparison.SizeBits() + << " bits between " << Comparison.Lhs().BaseId << " + " + << Comparison.Lhs().Offset << " and " + << Comparison.Rhs().BaseId << " + " + << Comparison.Rhs().Offset << "\n"); + LLVM_DEBUG(dbgs() << "\n"); + Comparisons.push_back(std::move(Comparison)); +} + +// A chain of comparisons. +class BCECmpChain { + public: + BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi, + AliasAnalysis &AA); + + int size() const { return Comparisons_.size(); } + +#ifdef MERGEICMPS_DOT_ON + void dump() const; +#endif // MERGEICMPS_DOT_ON + + bool simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA, + DomTreeUpdater &DTU); + +private: + static bool IsContiguous(const BCECmpBlock &First, + const BCECmpBlock &Second) { + return First.Lhs().BaseId == Second.Lhs().BaseId && + First.Rhs().BaseId == Second.Rhs().BaseId && + First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset && + First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset; + } + + PHINode &Phi_; + std::vector<BCECmpBlock> Comparisons_; + // The original entry block (before sorting); + BasicBlock *EntryBlock_; +}; + +BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi, + AliasAnalysis &AA) + : Phi_(Phi) { + assert(!Blocks.empty() && "a chain should have at least one block"); + // Now look inside blocks to check for BCE comparisons. + std::vector<BCECmpBlock> Comparisons; + BaseIdentifier BaseId; + for (size_t BlockIdx = 0; BlockIdx < Blocks.size(); ++BlockIdx) { + BasicBlock *const Block = Blocks[BlockIdx]; + assert(Block && "invalid block"); + BCECmpBlock Comparison = visitCmpBlock(Phi.getIncomingValueForBlock(Block), + Block, Phi.getParent(), BaseId); + Comparison.BB = Block; + if (!Comparison.IsValid()) { + LLVM_DEBUG(dbgs() << "chain with invalid BCECmpBlock, no merge.\n"); + return; + } + if (Comparison.doesOtherWork()) { + LLVM_DEBUG(dbgs() << "block '" << Comparison.BB->getName() + << "' does extra work besides compare\n"); + if (Comparisons.empty()) { + // This is the initial block in the chain, in case this block does other + // work, we can try to split the block and move the irrelevant + // instructions to the predecessor. + // + // If this is not the initial block in the chain, splitting it wont + // work. + // + // As once split, there will still be instructions before the BCE cmp + // instructions that do other work in program order, i.e. within the + // chain before sorting. Unless we can abort the chain at this point + // and start anew. + // + // NOTE: we only handle blocks a with single predecessor for now. + if (Comparison.canSplit(AA)) { + LLVM_DEBUG(dbgs() + << "Split initial block '" << Comparison.BB->getName() + << "' that does extra work besides compare\n"); + Comparison.RequireSplit = true; + enqueueBlock(Comparisons, std::move(Comparison)); + } else { + LLVM_DEBUG(dbgs() + << "ignoring initial block '" << Comparison.BB->getName() + << "' that does extra work besides compare\n"); + } + continue; + } + // TODO(courbet): Right now we abort the whole chain. We could be + // merging only the blocks that don't do other work and resume the + // chain from there. For example: + // if (a[0] == b[0]) { // bb1 + // if (a[1] == b[1]) { // bb2 + // some_value = 3; //bb3 + // if (a[2] == b[2]) { //bb3 + // do a ton of stuff //bb4 + // } + // } + // } + // + // This is: + // + // bb1 --eq--> bb2 --eq--> bb3* -eq--> bb4 --+ + // \ \ \ \ + // ne ne ne \ + // \ \ \ v + // +------------+-----------+----------> bb_phi + // + // We can only merge the first two comparisons, because bb3* does + // "other work" (setting some_value to 3). + // We could still merge bb1 and bb2 though. + return; + } + enqueueBlock(Comparisons, std::move(Comparison)); + } + + // It is possible we have no suitable comparison to merge. + if (Comparisons.empty()) { + LLVM_DEBUG(dbgs() << "chain with no BCE basic blocks, no merge\n"); + return; + } + EntryBlock_ = Comparisons[0].BB; + Comparisons_ = std::move(Comparisons); +#ifdef MERGEICMPS_DOT_ON + errs() << "BEFORE REORDERING:\n\n"; + dump(); +#endif // MERGEICMPS_DOT_ON + // Reorder blocks by LHS. We can do that without changing the + // semantics because we are only accessing dereferencable memory. + llvm::sort(Comparisons_, + [](const BCECmpBlock &LhsBlock, const BCECmpBlock &RhsBlock) { + return std::tie(LhsBlock.Lhs(), LhsBlock.Rhs()) < + std::tie(RhsBlock.Lhs(), RhsBlock.Rhs()); + }); +#ifdef MERGEICMPS_DOT_ON + errs() << "AFTER REORDERING:\n\n"; + dump(); +#endif // MERGEICMPS_DOT_ON +} + +#ifdef MERGEICMPS_DOT_ON +void BCECmpChain::dump() const { + errs() << "digraph dag {\n"; + errs() << " graph [bgcolor=transparent];\n"; + errs() << " node [color=black,style=filled,fillcolor=lightyellow];\n"; + errs() << " edge [color=black];\n"; + for (size_t I = 0; I < Comparisons_.size(); ++I) { + const auto &Comparison = Comparisons_[I]; + errs() << " \"" << I << "\" [label=\"%" + << Comparison.Lhs().Base()->getName() << " + " + << Comparison.Lhs().Offset << " == %" + << Comparison.Rhs().Base()->getName() << " + " + << Comparison.Rhs().Offset << " (" << (Comparison.SizeBits() / 8) + << " bytes)\"];\n"; + const Value *const Val = Phi_.getIncomingValueForBlock(Comparison.BB); + if (I > 0) errs() << " \"" << (I - 1) << "\" -> \"" << I << "\";\n"; + errs() << " \"" << I << "\" -> \"Phi\" [label=\"" << *Val << "\"];\n"; + } + errs() << " \"Phi\" [label=\"Phi\"];\n"; + errs() << "}\n\n"; +} +#endif // MERGEICMPS_DOT_ON + +namespace { + +// A class to compute the name of a set of merged basic blocks. +// This is optimized for the common case of no block names. +class MergedBlockName { + // Storage for the uncommon case of several named blocks. + SmallString<16> Scratch; + +public: + explicit MergedBlockName(ArrayRef<BCECmpBlock> Comparisons) + : Name(makeName(Comparisons)) {} + const StringRef Name; + +private: + StringRef makeName(ArrayRef<BCECmpBlock> Comparisons) { + assert(!Comparisons.empty() && "no basic block"); + // Fast path: only one block, or no names at all. + if (Comparisons.size() == 1) + return Comparisons[0].BB->getName(); + const int size = std::accumulate(Comparisons.begin(), Comparisons.end(), 0, + [](int i, const BCECmpBlock &Cmp) { + return i + Cmp.BB->getName().size(); + }); + if (size == 0) + return StringRef("", 0); + + // Slow path: at least two blocks, at least one block with a name. + Scratch.clear(); + // We'll have `size` bytes for name and `Comparisons.size() - 1` bytes for + // separators. + Scratch.reserve(size + Comparisons.size() - 1); + const auto append = [this](StringRef str) { + Scratch.append(str.begin(), str.end()); + }; + append(Comparisons[0].BB->getName()); + for (int I = 1, E = Comparisons.size(); I < E; ++I) { + const BasicBlock *const BB = Comparisons[I].BB; + if (!BB->getName().empty()) { + append("+"); + append(BB->getName()); + } + } + return StringRef(Scratch); + } +}; +} // namespace + +// Merges the given contiguous comparison blocks into one memcmp block. +static BasicBlock *mergeComparisons(ArrayRef<BCECmpBlock> Comparisons, + BasicBlock *const InsertBefore, + BasicBlock *const NextCmpBlock, + PHINode &Phi, const TargetLibraryInfo &TLI, + AliasAnalysis &AA, DomTreeUpdater &DTU) { + assert(!Comparisons.empty() && "merging zero comparisons"); + LLVMContext &Context = NextCmpBlock->getContext(); + const BCECmpBlock &FirstCmp = Comparisons[0]; + + // Create a new cmp block before next cmp block. + BasicBlock *const BB = + BasicBlock::Create(Context, MergedBlockName(Comparisons).Name, + NextCmpBlock->getParent(), InsertBefore); + IRBuilder<> Builder(BB); + // Add the GEPs from the first BCECmpBlock. + Value *const Lhs = Builder.Insert(FirstCmp.Lhs().GEP->clone()); + Value *const Rhs = Builder.Insert(FirstCmp.Rhs().GEP->clone()); + + Value *IsEqual = nullptr; + LLVM_DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons -> " + << BB->getName() << "\n"); + if (Comparisons.size() == 1) { + LLVM_DEBUG(dbgs() << "Only one comparison, updating branches\n"); + Value *const LhsLoad = + Builder.CreateLoad(FirstCmp.Lhs().LoadI->getType(), Lhs); + Value *const RhsLoad = + Builder.CreateLoad(FirstCmp.Rhs().LoadI->getType(), Rhs); + // There are no blocks to merge, just do the comparison. + IsEqual = Builder.CreateICmpEQ(LhsLoad, RhsLoad); + } else { + // If there is one block that requires splitting, we do it now, i.e. + // just before we know we will collapse the chain. The instructions + // can be executed before any of the instructions in the chain. + const auto ToSplit = + std::find_if(Comparisons.begin(), Comparisons.end(), + [](const BCECmpBlock &B) { return B.RequireSplit; }); + if (ToSplit != Comparisons.end()) { + LLVM_DEBUG(dbgs() << "Splitting non_BCE work to header\n"); + ToSplit->split(BB, AA); + } + + const unsigned TotalSizeBits = std::accumulate( + Comparisons.begin(), Comparisons.end(), 0u, + [](int Size, const BCECmpBlock &C) { return Size + C.SizeBits(); }); + + // Create memcmp() == 0. + const auto &DL = Phi.getModule()->getDataLayout(); + Value *const MemCmpCall = emitMemCmp( + Lhs, Rhs, + ConstantInt::get(DL.getIntPtrType(Context), TotalSizeBits / 8), Builder, + DL, &TLI); + IsEqual = Builder.CreateICmpEQ( + MemCmpCall, ConstantInt::get(Type::getInt32Ty(Context), 0)); + } + + BasicBlock *const PhiBB = Phi.getParent(); + // Add a branch to the next basic block in the chain. + if (NextCmpBlock == PhiBB) { + // Continue to phi, passing it the comparison result. + Builder.CreateBr(PhiBB); + Phi.addIncoming(IsEqual, BB); + DTU.applyUpdates({{DominatorTree::Insert, BB, PhiBB}}); + } else { + // Continue to next block if equal, exit to phi else. + Builder.CreateCondBr(IsEqual, NextCmpBlock, PhiBB); + Phi.addIncoming(ConstantInt::getFalse(Context), BB); + DTU.applyUpdates({{DominatorTree::Insert, BB, NextCmpBlock}, + {DominatorTree::Insert, BB, PhiBB}}); + } + return BB; +} + +bool BCECmpChain::simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA, + DomTreeUpdater &DTU) { + assert(Comparisons_.size() >= 2 && "simplifying trivial BCECmpChain"); + // First pass to check if there is at least one merge. If not, we don't do + // anything and we keep analysis passes intact. + const auto AtLeastOneMerged = [this]() { + for (size_t I = 1; I < Comparisons_.size(); ++I) { + if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) + return true; + } + return false; + }; + if (!AtLeastOneMerged()) + return false; + + LLVM_DEBUG(dbgs() << "Simplifying comparison chain starting at block " + << EntryBlock_->getName() << "\n"); + + // Effectively merge blocks. We go in the reverse direction from the phi block + // so that the next block is always available to branch to. + const auto mergeRange = [this, &TLI, &AA, &DTU](int I, int Num, + BasicBlock *InsertBefore, + BasicBlock *Next) { + return mergeComparisons(makeArrayRef(Comparisons_).slice(I, Num), + InsertBefore, Next, Phi_, TLI, AA, DTU); + }; + int NumMerged = 1; + BasicBlock *NextCmpBlock = Phi_.getParent(); + for (int I = static_cast<int>(Comparisons_.size()) - 2; I >= 0; --I) { + if (IsContiguous(Comparisons_[I], Comparisons_[I + 1])) { + LLVM_DEBUG(dbgs() << "Merging block " << Comparisons_[I].BB->getName() + << " into " << Comparisons_[I + 1].BB->getName() + << "\n"); + ++NumMerged; + } else { + NextCmpBlock = mergeRange(I + 1, NumMerged, NextCmpBlock, NextCmpBlock); + NumMerged = 1; + } + } + // Insert the entry block for the new chain before the old entry block. + // If the old entry block was the function entry, this ensures that the new + // entry can become the function entry. + NextCmpBlock = mergeRange(0, NumMerged, EntryBlock_, NextCmpBlock); + + // Replace the original cmp chain with the new cmp chain by pointing all + // predecessors of EntryBlock_ to NextCmpBlock instead. This makes all cmp + // blocks in the old chain unreachable. + while (!pred_empty(EntryBlock_)) { + BasicBlock* const Pred = *pred_begin(EntryBlock_); + LLVM_DEBUG(dbgs() << "Updating jump into old chain from " << Pred->getName() + << "\n"); + Pred->getTerminator()->replaceUsesOfWith(EntryBlock_, NextCmpBlock); + DTU.applyUpdates({{DominatorTree::Delete, Pred, EntryBlock_}, + {DominatorTree::Insert, Pred, NextCmpBlock}}); + } + + // If the old cmp chain was the function entry, we need to update the function + // entry. + const bool ChainEntryIsFnEntry = + (EntryBlock_ == &EntryBlock_->getParent()->getEntryBlock()); + if (ChainEntryIsFnEntry && DTU.hasDomTree()) { + LLVM_DEBUG(dbgs() << "Changing function entry from " + << EntryBlock_->getName() << " to " + << NextCmpBlock->getName() << "\n"); + DTU.getDomTree().setNewRoot(NextCmpBlock); + DTU.applyUpdates({{DominatorTree::Delete, NextCmpBlock, EntryBlock_}}); + } + EntryBlock_ = nullptr; + + // Delete merged blocks. This also removes incoming values in phi. + SmallVector<BasicBlock *, 16> DeadBlocks; + for (auto &Cmp : Comparisons_) { + LLVM_DEBUG(dbgs() << "Deleting merged block " << Cmp.BB->getName() << "\n"); + DeadBlocks.push_back(Cmp.BB); + } + DeleteDeadBlocks(DeadBlocks, &DTU); + + Comparisons_.clear(); + return true; +} + +std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi, + BasicBlock *const LastBlock, + int NumBlocks) { + // Walk up from the last block to find other blocks. + std::vector<BasicBlock *> Blocks(NumBlocks); + assert(LastBlock && "invalid last block"); + BasicBlock *CurBlock = LastBlock; + for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) { + if (CurBlock->hasAddressTaken()) { + // Somebody is jumping to the block through an address, all bets are + // off. + LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex + << " has its address taken\n"); + return {}; + } + Blocks[BlockIndex] = CurBlock; + auto *SinglePredecessor = CurBlock->getSinglePredecessor(); + if (!SinglePredecessor) { + // The block has two or more predecessors. + LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex + << " has two or more predecessors\n"); + return {}; + } + if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) { + // The block does not link back to the phi. + LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex + << " does not link back to the phi\n"); + return {}; + } + CurBlock = SinglePredecessor; + } + Blocks[0] = CurBlock; + return Blocks; +} + +bool processPhi(PHINode &Phi, const TargetLibraryInfo &TLI, AliasAnalysis &AA, + DomTreeUpdater &DTU) { + LLVM_DEBUG(dbgs() << "processPhi()\n"); + if (Phi.getNumIncomingValues() <= 1) { + LLVM_DEBUG(dbgs() << "skip: only one incoming value in phi\n"); + return false; + } + // We are looking for something that has the following structure: + // bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+ + // \ \ \ \ + // ne ne ne \ + // \ \ \ v + // +------------+-----------+----------> bb_phi + // + // - The last basic block (bb4 here) must branch unconditionally to bb_phi. + // It's the only block that contributes a non-constant value to the Phi. + // - All other blocks (b1, b2, b3) must have exactly two successors, one of + // them being the phi block. + // - All intermediate blocks (bb2, bb3) must have only one predecessor. + // - Blocks cannot do other work besides the comparison, see doesOtherWork() + + // The blocks are not necessarily ordered in the phi, so we start from the + // last block and reconstruct the order. + BasicBlock *LastBlock = nullptr; + for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) { + if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue; + if (LastBlock) { + // There are several non-constant values. + LLVM_DEBUG(dbgs() << "skip: several non-constant values\n"); + return false; + } + if (!isa<ICmpInst>(Phi.getIncomingValue(I)) || + cast<ICmpInst>(Phi.getIncomingValue(I))->getParent() != + Phi.getIncomingBlock(I)) { + // Non-constant incoming value is not from a cmp instruction or not + // produced by the last block. We could end up processing the value + // producing block more than once. + // + // This is an uncommon case, so we bail. + LLVM_DEBUG( + dbgs() + << "skip: non-constant value not from cmp or not from last block.\n"); + return false; + } + LastBlock = Phi.getIncomingBlock(I); + } + if (!LastBlock) { + // There is no non-constant block. + LLVM_DEBUG(dbgs() << "skip: no non-constant block\n"); + return false; + } + if (LastBlock->getSingleSuccessor() != Phi.getParent()) { + LLVM_DEBUG(dbgs() << "skip: last block non-phi successor\n"); + return false; + } + + const auto Blocks = + getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues()); + if (Blocks.empty()) return false; + BCECmpChain CmpChain(Blocks, Phi, AA); + + if (CmpChain.size() < 2) { + LLVM_DEBUG(dbgs() << "skip: only one compare block\n"); + return false; + } + + return CmpChain.simplify(TLI, AA, DTU); +} + +static bool runImpl(Function &F, const TargetLibraryInfo &TLI, + const TargetTransformInfo &TTI, AliasAnalysis &AA, + DominatorTree *DT) { + LLVM_DEBUG(dbgs() << "MergeICmpsLegacyPass: " << F.getName() << "\n"); + + // We only try merging comparisons if the target wants to expand memcmp later. + // The rationale is to avoid turning small chains into memcmp calls. + if (!TTI.enableMemCmpExpansion(F.hasOptSize(), true)) + return false; + + // If we don't have memcmp avaiable we can't emit calls to it. + if (!TLI.has(LibFunc_memcmp)) + return false; + + DomTreeUpdater DTU(DT, /*PostDominatorTree*/ nullptr, + DomTreeUpdater::UpdateStrategy::Eager); + + bool MadeChange = false; + + for (auto BBIt = ++F.begin(); BBIt != F.end(); ++BBIt) { + // A Phi operation is always first in a basic block. + if (auto *const Phi = dyn_cast<PHINode>(&*BBIt->begin())) + MadeChange |= processPhi(*Phi, TLI, AA, DTU); + } + + return MadeChange; +} + +class MergeICmpsLegacyPass : public FunctionPass { +public: + static char ID; + + MergeICmpsLegacyPass() : FunctionPass(ID) { + initializeMergeICmpsLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override { + if (skipFunction(F)) return false; + const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); + const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); + // MergeICmps does not need the DominatorTree, but we update it if it's + // already available. + auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); + auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); + return runImpl(F, TLI, TTI, AA, DTWP ? &DTWP->getDomTree() : nullptr); + } + + private: + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired<TargetLibraryInfoWrapperPass>(); + AU.addRequired<TargetTransformInfoWrapperPass>(); + AU.addRequired<AAResultsWrapperPass>(); + AU.addPreserved<GlobalsAAWrapperPass>(); + AU.addPreserved<DominatorTreeWrapperPass>(); + } +}; + +} // namespace + +char MergeICmpsLegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(MergeICmpsLegacyPass, "mergeicmps", + "Merge contiguous icmps into a memcmp", false, false) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_END(MergeICmpsLegacyPass, "mergeicmps", + "Merge contiguous icmps into a memcmp", false, false) + +Pass *llvm::createMergeICmpsLegacyPass() { return new MergeICmpsLegacyPass(); } + +PreservedAnalyses MergeICmpsPass::run(Function &F, + FunctionAnalysisManager &AM) { + auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); + auto &TTI = AM.getResult<TargetIRAnalysis>(F); + auto &AA = AM.getResult<AAManager>(F); + auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F); + const bool MadeChanges = runImpl(F, TLI, TTI, AA, DT); + if (!MadeChanges) + return PreservedAnalyses::all(); + PreservedAnalyses PA; + PA.preserve<GlobalsAA>(); + PA.preserve<DominatorTreeAnalysis>(); + return PA; +} |