contrib/llvm-project/llvm/lib/Transforms/Scalar/MergeICmps.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This pass turns chains of integer comparisons into memcmp (the memcmp is
  10 // later typically inlined as a chain of efficient hardware comparisons). This
  11 // typically benefits c++ member or nonmember operator==().
  12 //
  13 // The basic idea is to replace a longer chain of integer comparisons loaded
  14 // from contiguous memory locations into a shorter chain of larger integer
  15 // comparisons. Benefits are double:
  16 //  - There are less jumps, and therefore less opportunities for mispredictions
  17 //    and I-cache misses.
  18 //  - Code size is smaller, both because jumps are removed and because the
  19 //    encoding of a 2*n byte compare is smaller than that of two n-byte
  20 //    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/Analysis/DomTreeUpdater.h"
  46 #include "llvm/Analysis/GlobalsModRef.h"
  47 #include "llvm/Analysis/Loads.h"
  48 #include "llvm/Analysis/TargetLibraryInfo.h"
  49 #include "llvm/Analysis/TargetTransformInfo.h"
  50 #include "llvm/IR/Dominators.h"
  51 #include "llvm/IR/Function.h"
  52 #include "llvm/IR/IRBuilder.h"
  53 #include "llvm/InitializePasses.h"
  54 #include "llvm/Pass.h"
  55 #include "llvm/Transforms/Scalar.h"
  56 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  57 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  58 #include <algorithm>
  59 #include <numeric>
  60 #include <utility>
  61 #include <vector>
  62
  63 using namespace llvm;
  64
  65 namespace {
  66
  67 #define DEBUG_TYPE "mergeicmps"
  68
  69 // Returns true if the instruction is a simple load or a simple store
  70 static bool isSimpleLoadOrStore(const Instruction *I) {
  71   if (const LoadInst *LI = dyn_cast<LoadInst>(I))
  72     return LI->isSimple();
  73   if (const StoreInst *SI = dyn_cast<StoreInst>(I))
  74     return SI->isSimple();
  75   return false;
  76 }
  77
  78 // A BCE atom "Binary Compare Expression Atom" represents an integer load
  79 // that is a constant offset from a base value, e.g. `a` or `o.c` in the example
  80 // at the top.
  81 struct BCEAtom {
  82   BCEAtom() = default;
  83   BCEAtom(GetElementPtrInst *GEP, LoadInst *LoadI, int BaseId, APInt Offset)
  84       : GEP(GEP), LoadI(LoadI), BaseId(BaseId), Offset(Offset) {}
  85
  86   BCEAtom(const BCEAtom &) = delete;
  87   BCEAtom &operator=(const BCEAtom &) = delete;
  88
  89   BCEAtom(BCEAtom &&that) = default;
  90   BCEAtom &operator=(BCEAtom &&that) {
  91     if (this == &that)
  92       return *this;
  93     GEP = that.GEP;
  94     LoadI = that.LoadI;
  95     BaseId = that.BaseId;
  96     Offset = std::move(that.Offset);
  97     return *this;
  98   }
  99
 100   // We want to order BCEAtoms by (Base, Offset). However we cannot use
 101   // the pointer values for Base because these are non-deterministic.
 102   // To make sure that the sort order is stable, we first assign to each atom
 103   // base value an index based on its order of appearance in the chain of
 104   // comparisons. We call this index `BaseOrdering`. For example, for:
 105   //    b[3] == c[2] && a[1] == d[1] && b[4] == c[3]
 106   //    |  block 1 |    |  block 2 |    |  block 3 |
 107   // b gets assigned index 0 and a index 1, because b appears as LHS in block 1,
 108   // which is before block 2.
 109   // We then sort by (BaseOrdering[LHS.Base()], LHS.Offset), which is stable.
 110   bool operator<(const BCEAtom &O) const {
 111     return BaseId != O.BaseId ? BaseId < O.BaseId : Offset.slt(O.Offset);
 112   }
 113
 114   GetElementPtrInst *GEP = nullptr;
 115   LoadInst *LoadI = nullptr;
 116   unsigned BaseId = 0;
 117   APInt Offset;
 118 };
 119
 120 // A class that assigns increasing ids to values in the order in which they are
 121 // seen. See comment in `BCEAtom::operator<()``.
 122 class BaseIdentifier {
 123 public:
 124   // Returns the id for value `Base`, after assigning one if `Base` has not been
 125   // seen before.
 126   int getBaseId(const Value *Base) {
 127     assert(Base && "invalid base");
 128     const auto Insertion = BaseToIndex.try_emplace(Base, Order);
 129     if (Insertion.second)
 130       ++Order;
 131     return Insertion.first->second;
 132   }
 133
 134 private:
 135   unsigned Order = 1;
 136   DenseMap<const Value*, int> BaseToIndex;
 137 };
 138
 139 // If this value is a load from a constant offset w.r.t. a base address, and
 140 // there are no other users of the load or address, returns the base address and
 141 // the offset.
 142 BCEAtom visitICmpLoadOperand(Value *const Val, BaseIdentifier &BaseId) {
 143   auto *const LoadI = dyn_cast<LoadInst>(Val);
 144   if (!LoadI)
 145     return {};
 146   LLVM_DEBUG(dbgs() << "load\n");
 147   if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {
 148     LLVM_DEBUG(dbgs() << "used outside of block\n");
 149     return {};
 150   }
 151   // Do not optimize atomic loads to non-atomic memcmp
 152   if (!LoadI->isSimple()) {
 153     LLVM_DEBUG(dbgs() << "volatile or atomic\n");
 154     return {};
 155   }
 156   Value *const Addr = LoadI->getOperand(0);
 157   auto *const GEP = dyn_cast<GetElementPtrInst>(Addr);
 158   if (!GEP)
 159     return {};
 160   LLVM_DEBUG(dbgs() << "GEP\n");
 161   if (GEP->isUsedOutsideOfBlock(LoadI->getParent())) {
 162     LLVM_DEBUG(dbgs() << "used outside of block\n");
 163     return {};
 164   }
 165   const auto &DL = GEP->getModule()->getDataLayout();
 166   if (!isDereferenceablePointer(GEP, LoadI->getType(), DL)) {
 167     LLVM_DEBUG(dbgs() << "not dereferenceable\n");
 168     // We need to make sure that we can do comparison in any order, so we
 169     // require memory to be unconditionnally dereferencable.
 170     return {};
 171   }
 172   APInt Offset = APInt(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
 173   if (!GEP->accumulateConstantOffset(DL, Offset))
 174     return {};
 175   return BCEAtom(GEP, LoadI, BaseId.getBaseId(GEP->getPointerOperand()),
 176                  Offset);
 177 }
 178
 179 // A basic block with a comparison between two BCE atoms, e.g. `a == o.a` in the
 180 // example at the top.
 181 // The block might do extra work besides the atom comparison, in which case
 182 // doesOtherWork() returns true. Under some conditions, the block can be
 183 // split into the atom comparison part and the "other work" part
 184 // (see canSplit()).
 185 // Note: the terminology is misleading: the comparison is symmetric, so there
 186 // is no real {l/r}hs. What we want though is to have the same base on the
 187 // left (resp. right), so that we can detect consecutive loads. To ensure this
 188 // we put the smallest atom on the left.
 189 class BCECmpBlock {
 190  public:
 191   BCECmpBlock() {}
 192
 193   BCECmpBlock(BCEAtom L, BCEAtom R, int SizeBits)
 194       : Lhs_(std::move(L)), Rhs_(std::move(R)), SizeBits_(SizeBits) {
 195     if (Rhs_ < Lhs_) std::swap(Rhs_, Lhs_);
 196   }
 197
 198   bool IsValid() const { return Lhs_.BaseId != 0 && Rhs_.BaseId != 0; }
 199
 200   // Assert the block is consistent: If valid, it should also have
 201   // non-null members besides Lhs_ and Rhs_.
 202   void AssertConsistent() const {
 203     if (IsValid()) {
 204       assert(BB);
 205       assert(CmpI);
 206       assert(BranchI);
 207     }
 208   }
 209
 210   const BCEAtom &Lhs() const { return Lhs_; }
 211   const BCEAtom &Rhs() const { return Rhs_; }
 212   int SizeBits() const { return SizeBits_; }
 213
 214   // Returns true if the block does other works besides comparison.
 215   bool doesOtherWork() const;
 216
 217   // Returns true if the non-BCE-cmp instructions can be separated from BCE-cmp
 218   // instructions in the block.
 219   bool canSplit(AliasAnalysis &AA) const;
 220
 221   // Return true if this all the relevant instructions in the BCE-cmp-block can
 222   // be sunk below this instruction. By doing this, we know we can separate the
 223   // BCE-cmp-block instructions from the non-BCE-cmp-block instructions in the
 224   // block.
 225   bool canSinkBCECmpInst(const Instruction *, DenseSet<Instruction *> &,
 226                          AliasAnalysis &AA) const;
 227
 228   // We can separate the BCE-cmp-block instructions and the non-BCE-cmp-block
 229   // instructions. Split the old block and move all non-BCE-cmp-insts into the
 230   // new parent block.
 231   void split(BasicBlock *NewParent, AliasAnalysis &AA) const;
 232
 233   // The basic block where this comparison happens.
 234   BasicBlock *BB = nullptr;
 235   // The ICMP for this comparison.
 236   ICmpInst *CmpI = nullptr;
 237   // The terminating branch.
 238   BranchInst *BranchI = nullptr;
 239   // The block requires splitting.
 240   bool RequireSplit = false;
 241
 242 private:
 243   BCEAtom Lhs_;
 244   BCEAtom Rhs_;
 245   int SizeBits_ = 0;
 246 };
 247
 248 bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst,
 249                                     DenseSet<Instruction *> &BlockInsts,
 250                                     AliasAnalysis &AA) const {
 251   // If this instruction has side effects and its in middle of the BCE cmp block
 252   // instructions, then bail for now.
 253   if (Inst->mayHaveSideEffects()) {
 254     // Bail if this is not a simple load or store
 255     if (!isSimpleLoadOrStore(Inst))
 256       return false;
 257     // Disallow stores that might alias the BCE operands
 258     MemoryLocation LLoc = MemoryLocation::get(Lhs_.LoadI);
 259     MemoryLocation RLoc = MemoryLocation::get(Rhs_.LoadI);
 260     if (isModSet(AA.getModRefInfo(Inst, LLoc)) ||
 261         isModSet(AA.getModRefInfo(Inst, RLoc)))
 262       return false;
 263   }
 264   // Make sure this instruction does not use any of the BCE cmp block
 265   // instructions as operand.
 266   for (auto BI : BlockInsts) {
 267     if (is_contained(Inst->operands(), BI))
 268       return false;
 269   }
 270   return true;
 271 }
 272
 273 void BCECmpBlock::split(BasicBlock *NewParent, AliasAnalysis &AA) const {
 274   DenseSet<Instruction *> BlockInsts(
 275       {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
 276   llvm::SmallVector<Instruction *, 4> OtherInsts;
 277   for (Instruction &Inst : *BB) {
 278     if (BlockInsts.count(&Inst))
 279       continue;
 280       assert(canSinkBCECmpInst(&Inst, BlockInsts, AA) &&
 281              "Split unsplittable block");
 282     // This is a non-BCE-cmp-block instruction. And it can be separated
 283     // from the BCE-cmp-block instruction.
 284     OtherInsts.push_back(&Inst);
 285   }
 286
 287   // Do the actual spliting.
 288   for (Instruction *Inst : reverse(OtherInsts)) {
 289     Inst->moveBefore(&*NewParent->begin());
 290   }
 291 }
 292
 293 bool BCECmpBlock::canSplit(AliasAnalysis &AA) const {
 294   DenseSet<Instruction *> BlockInsts(
 295       {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
 296   for (Instruction &Inst : *BB) {
 297     if (!BlockInsts.count(&Inst)) {
 298       if (!canSinkBCECmpInst(&Inst, BlockInsts, AA))
 299         return false;
 300     }
 301   }
 302   return true;
 303 }
 304
 305 bool BCECmpBlock::doesOtherWork() const {
 306   AssertConsistent();
 307   // All the instructions we care about in the BCE cmp block.
 308   DenseSet<Instruction *> BlockInsts(
 309       {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
 310   // TODO(courbet): Can we allow some other things ? This is very conservative.
 311   // We might be able to get away with anything does not have any side
 312   // effects outside of the basic block.
 313   // Note: The GEPs and/or loads are not necessarily in the same block.
 314   for (const Instruction &Inst : *BB) {
 315     if (!BlockInsts.count(&Inst))
 316       return true;
 317   }
 318   return false;
 319 }
 320
 321 // Visit the given comparison. If this is a comparison between two valid
 322 // BCE atoms, returns the comparison.
 323 BCECmpBlock visitICmp(const ICmpInst *const CmpI,
 324                       const ICmpInst::Predicate ExpectedPredicate,
 325                       BaseIdentifier &BaseId) {
 326   // The comparison can only be used once:
 327   //  - For intermediate blocks, as a branch condition.
 328   //  - For the final block, as an incoming value for the Phi.
 329   // If there are any other uses of the comparison, we cannot merge it with
 330   // other comparisons as we would create an orphan use of the value.
 331   if (!CmpI->hasOneUse()) {
 332     LLVM_DEBUG(dbgs() << "cmp has several uses\n");
 333     return {};
 334   }
 335   if (CmpI->getPredicate() != ExpectedPredicate)
 336     return {};
 337   LLVM_DEBUG(dbgs() << "cmp "
 338                     << (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne")
 339                     << "\n");
 340   auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0), BaseId);
 341   if (!Lhs.BaseId)
 342     return {};
 343   auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1), BaseId);
 344   if (!Rhs.BaseId)
 345     return {};
 346   const auto &DL = CmpI->getModule()->getDataLayout();
 347   return BCECmpBlock(std::move(Lhs), std::move(Rhs),
 348                      DL.getTypeSizeInBits(CmpI->getOperand(0)->getType()));
 349 }
 350
 351 // Visit the given comparison block. If this is a comparison between two valid
 352 // BCE atoms, returns the comparison.
 353 BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block,
 354                           const BasicBlock *const PhiBlock,
 355                           BaseIdentifier &BaseId) {
 356   if (Block->empty()) return {};
 357   auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator());
 358   if (!BranchI) return {};
 359   LLVM_DEBUG(dbgs() << "branch\n");
 360   if (BranchI->isUnconditional()) {
 361     // In this case, we expect an incoming value which is the result of the
 362     // comparison. This is the last link in the chain of comparisons (note
 363     // that this does not mean that this is the last incoming value, blocks
 364     // can be reordered).
 365     auto *const CmpI = dyn_cast<ICmpInst>(Val);
 366     if (!CmpI) return {};
 367     LLVM_DEBUG(dbgs() << "icmp\n");
 368     auto Result = visitICmp(CmpI, ICmpInst::ICMP_EQ, BaseId);
 369     Result.CmpI = CmpI;
 370     Result.BranchI = BranchI;
 371     return Result;
 372   } else {
 373     // In this case, we expect a constant incoming value (the comparison is
 374     // chained).
 375     const auto *const Const = dyn_cast<ConstantInt>(Val);
 376     LLVM_DEBUG(dbgs() << "const\n");
 377     if (!Const->isZero()) return {};
 378     LLVM_DEBUG(dbgs() << "false\n");
 379     auto *const CmpI = dyn_cast<ICmpInst>(BranchI->getCondition());
 380     if (!CmpI) return {};
 381     LLVM_DEBUG(dbgs() << "icmp\n");
 382     assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch");
 383     BasicBlock *const FalseBlock = BranchI->getSuccessor(1);
 384     auto Result = visitICmp(
 385         CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
 386         BaseId);
 387     Result.CmpI = CmpI;
 388     Result.BranchI = BranchI;
 389     return Result;
 390   }
 391   return {};
 392 }
 393
 394 static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons,
 395                                 BCECmpBlock &&Comparison) {
 396   LLVM_DEBUG(dbgs() << "Block '" << Comparison.BB->getName()
 397                     << "': Found cmp of " << Comparison.SizeBits()
 398                     << " bits between " << Comparison.Lhs().BaseId << " + "
 399                     << Comparison.Lhs().Offset << " and "
 400                     << Comparison.Rhs().BaseId << " + "
 401                     << Comparison.Rhs().Offset << "\n");
 402   LLVM_DEBUG(dbgs() << "\n");
 403   Comparisons.push_back(std::move(Comparison));
 404 }
 405
 406 // A chain of comparisons.
 407 class BCECmpChain {
 408  public:
 409    BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
 410                AliasAnalysis &AA);
 411
 412    int size() const { return Comparisons_.size(); }
 413
 414 #ifdef MERGEICMPS_DOT_ON
 415   void dump() const;
 416 #endif  // MERGEICMPS_DOT_ON
 417
 418   bool simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA,
 419                 DomTreeUpdater &DTU);
 420
 421 private:
 422   static bool IsContiguous(const BCECmpBlock &First,
 423                            const BCECmpBlock &Second) {
 424     return First.Lhs().BaseId == Second.Lhs().BaseId &&
 425            First.Rhs().BaseId == Second.Rhs().BaseId &&
 426            First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset &&
 427            First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset;
 428   }
 429
 430   PHINode &Phi_;
 431   std::vector<BCECmpBlock> Comparisons_;
 432   // The original entry block (before sorting);
 433   BasicBlock *EntryBlock_;
 434 };
 435
 436 BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
 437                          AliasAnalysis &AA)
 438     : Phi_(Phi) {
 439   assert(!Blocks.empty() && "a chain should have at least one block");
 440   // Now look inside blocks to check for BCE comparisons.
 441   std::vector<BCECmpBlock> Comparisons;
 442   BaseIdentifier BaseId;
 443   for (size_t BlockIdx = 0; BlockIdx < Blocks.size(); ++BlockIdx) {
 444     BasicBlock *const Block = Blocks[BlockIdx];
 445     assert(Block && "invalid block");
 446     BCECmpBlock Comparison = visitCmpBlock(Phi.getIncomingValueForBlock(Block),
 447                                            Block, Phi.getParent(), BaseId);
 448     Comparison.BB = Block;
 449     if (!Comparison.IsValid()) {
 450       LLVM_DEBUG(dbgs() << "chain with invalid BCECmpBlock, no merge.\n");
 451       return;
 452     }
 453     if (Comparison.doesOtherWork()) {
 454       LLVM_DEBUG(dbgs() << "block '" << Comparison.BB->getName()
 455                         << "' does extra work besides compare\n");
 456       if (Comparisons.empty()) {
 457         // This is the initial block in the chain, in case this block does other
 458         // work, we can try to split the block and move the irrelevant
 459         // instructions to the predecessor.
 460         //
 461         // If this is not the initial block in the chain, splitting it wont
 462         // work.
 463         //
 464         // As once split, there will still be instructions before the BCE cmp
 465         // instructions that do other work in program order, i.e. within the
 466         // chain before sorting. Unless we can abort the chain at this point
 467         // and start anew.
 468         //
 469         // NOTE: we only handle blocks a with single predecessor for now.
 470         if (Comparison.canSplit(AA)) {
 471           LLVM_DEBUG(dbgs()
 472                      << "Split initial block '" << Comparison.BB->getName()
 473                      << "' that does extra work besides compare\n");
 474           Comparison.RequireSplit = true;
 475           enqueueBlock(Comparisons, std::move(Comparison));
 476         } else {
 477           LLVM_DEBUG(dbgs()
 478                      << "ignoring initial block '" << Comparison.BB->getName()
 479                      << "' that does extra work besides compare\n");
 480         }
 481         continue;
 482       }
 483       // TODO(courbet): Right now we abort the whole chain. We could be
 484       // merging only the blocks that don't do other work and resume the
 485       // chain from there. For example:
 486       //  if (a[0] == b[0]) {  // bb1
 487       //    if (a[1] == b[1]) {  // bb2
 488       //      some_value = 3; //bb3
 489       //      if (a[2] == b[2]) { //bb3
 490       //        do a ton of stuff  //bb4
 491       //      }
 492       //    }
 493       //  }
 494       //
 495       // This is:
 496       //
 497       // bb1 --eq--> bb2 --eq--> bb3* -eq--> bb4 --+
 498       //  \            \           \               \
 499       //   ne           ne          ne              \
 500       //    \            \           \               v
 501       //     +------------+-----------+----------> bb_phi
 502       //
 503       // We can only merge the first two comparisons, because bb3* does
 504       // "other work" (setting some_value to 3).
 505       // We could still merge bb1 and bb2 though.
 506       return;
 507     }
 508     enqueueBlock(Comparisons, std::move(Comparison));
 509   }
 510
 511   // It is possible we have no suitable comparison to merge.
 512   if (Comparisons.empty()) {
 513     LLVM_DEBUG(dbgs() << "chain with no BCE basic blocks, no merge\n");
 514     return;
 515   }
 516   EntryBlock_ = Comparisons[0].BB;
 517   Comparisons_ = std::move(Comparisons);
 518 #ifdef MERGEICMPS_DOT_ON
 519   errs() << "BEFORE REORDERING:\n\n";
 520   dump();
 521 #endif  // MERGEICMPS_DOT_ON
 522   // Reorder blocks by LHS. We can do that without changing the
 523   // semantics because we are only accessing dereferencable memory.
 524   llvm::sort(Comparisons_,
 525              [](const BCECmpBlock &LhsBlock, const BCECmpBlock &RhsBlock) {
 526                return std::tie(LhsBlock.Lhs(), LhsBlock.Rhs()) <
 527                       std::tie(RhsBlock.Lhs(), RhsBlock.Rhs());
 528              });
 529 #ifdef MERGEICMPS_DOT_ON
 530   errs() << "AFTER REORDERING:\n\n";
 531   dump();
 532 #endif  // MERGEICMPS_DOT_ON
 533 }
 534
 535 #ifdef MERGEICMPS_DOT_ON
 536 void BCECmpChain::dump() const {
 537   errs() << "digraph dag {\n";
 538   errs() << " graph [bgcolor=transparent];\n";
 539   errs() << " node [color=black,style=filled,fillcolor=lightyellow];\n";
 540   errs() << " edge [color=black];\n";
 541   for (size_t I = 0; I < Comparisons_.size(); ++I) {
 542     const auto &Comparison = Comparisons_[I];
 543     errs() << " \"" << I << "\" [label=\"%"
 544            << Comparison.Lhs().Base()->getName() << " + "
 545            << Comparison.Lhs().Offset << " == %"
 546            << Comparison.Rhs().Base()->getName() << " + "
 547            << Comparison.Rhs().Offset << " (" << (Comparison.SizeBits() / 8)
 548            << " bytes)\"];\n";
 549     const Value *const Val = Phi_.getIncomingValueForBlock(Comparison.BB);
 550     if (I > 0) errs() << " \"" << (I - 1) << "\" -> \"" << I << "\";\n";
 551     errs() << " \"" << I << "\" -> \"Phi\" [label=\"" << *Val << "\"];\n";
 552   }
 553   errs() << " \"Phi\" [label=\"Phi\"];\n";
 554   errs() << "}\n\n";
 555 }
 556 #endif  // MERGEICMPS_DOT_ON
 557
 558 namespace {
 559
 560 // A class to compute the name of a set of merged basic blocks.
 561 // This is optimized for the common case of no block names.
 562 class MergedBlockName {
 563   // Storage for the uncommon case of several named blocks.
 564   SmallString<16> Scratch;
 565
 566 public:
 567   explicit MergedBlockName(ArrayRef<BCECmpBlock> Comparisons)
 568       : Name(makeName(Comparisons)) {}
 569   const StringRef Name;
 570
 571 private:
 572   StringRef makeName(ArrayRef<BCECmpBlock> Comparisons) {
 573     assert(!Comparisons.empty() && "no basic block");
 574     // Fast path: only one block, or no names at all.
 575     if (Comparisons.size() == 1)
 576       return Comparisons[0].BB->getName();
 577     const int size = std::accumulate(Comparisons.begin(), Comparisons.end(), 0,
 578                                      [](int i, const BCECmpBlock &Cmp) {
 579                                        return i + Cmp.BB->getName().size();
 580                                      });
 581     if (size == 0)
 582       return StringRef("", 0);
 583
 584     // Slow path: at least two blocks, at least one block with a name.
 585     Scratch.clear();
 586     // We'll have `size` bytes for name and `Comparisons.size() - 1` bytes for
 587     // separators.
 588     Scratch.reserve(size + Comparisons.size() - 1);
 589     const auto append = [this](StringRef str) {
 590       Scratch.append(str.begin(), str.end());
 591     };
 592     append(Comparisons[0].BB->getName());
 593     for (int I = 1, E = Comparisons.size(); I < E; ++I) {
 594       const BasicBlock *const BB = Comparisons[I].BB;
 595       if (!BB->getName().empty()) {
 596         append("+");
 597         append(BB->getName());
 598       }
 599     }
 600     return StringRef(Scratch);
 601   }
 602 };
 603 } // namespace
 604
 605 // Merges the given contiguous comparison blocks into one memcmp block.
 606 static BasicBlock *mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
 607                                     BasicBlock *const InsertBefore,
 608                                     BasicBlock *const NextCmpBlock,
 609                                     PHINode &Phi, const TargetLibraryInfo &TLI,
 610                                     AliasAnalysis &AA, DomTreeUpdater &DTU) {
 611   assert(!Comparisons.empty() && "merging zero comparisons");
 612   LLVMContext &Context = NextCmpBlock->getContext();
 613   const BCECmpBlock &FirstCmp = Comparisons[0];
 614
 615   // Create a new cmp block before next cmp block.
 616   BasicBlock *const BB =
 617       BasicBlock::Create(Context, MergedBlockName(Comparisons).Name,
 618                          NextCmpBlock->getParent(), InsertBefore);
 619   IRBuilder<> Builder(BB);
 620   // Add the GEPs from the first BCECmpBlock.
 621   Value *const Lhs = Builder.Insert(FirstCmp.Lhs().GEP->clone());
 622   Value *const Rhs = Builder.Insert(FirstCmp.Rhs().GEP->clone());
 623
 624   Value *IsEqual = nullptr;
 625   LLVM_DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons -> "
 626                     << BB->getName() << "\n");
 627   if (Comparisons.size() == 1) {
 628     LLVM_DEBUG(dbgs() << "Only one comparison, updating branches\n");
 629     Value *const LhsLoad =
 630         Builder.CreateLoad(FirstCmp.Lhs().LoadI->getType(), Lhs);
 631     Value *const RhsLoad =
 632         Builder.CreateLoad(FirstCmp.Rhs().LoadI->getType(), Rhs);
 633     // There are no blocks to merge, just do the comparison.
 634     IsEqual = Builder.CreateICmpEQ(LhsLoad, RhsLoad);
 635   } else {
 636     // If there is one block that requires splitting, we do it now, i.e.
 637     // just before we know we will collapse the chain. The instructions
 638     // can be executed before any of the instructions in the chain.
 639     const auto ToSplit =
 640         std::find_if(Comparisons.begin(), Comparisons.end(),
 641                      [](const BCECmpBlock &B) { return B.RequireSplit; });
 642     if (ToSplit != Comparisons.end()) {
 643       LLVM_DEBUG(dbgs() << "Splitting non_BCE work to header\n");
 644       ToSplit->split(BB, AA);
 645     }
 646
 647     const unsigned TotalSizeBits = std::accumulate(
 648         Comparisons.begin(), Comparisons.end(), 0u,
 649         [](int Size, const BCECmpBlock &C) { return Size + C.SizeBits(); });
 650
 651     // Create memcmp() == 0.
 652     const auto &DL = Phi.getModule()->getDataLayout();
 653     Value *const MemCmpCall = emitMemCmp(
 654         Lhs, Rhs,
 655         ConstantInt::get(DL.getIntPtrType(Context), TotalSizeBits / 8), Builder,
 656         DL, &TLI);
 657     IsEqual = Builder.CreateICmpEQ(
 658         MemCmpCall, ConstantInt::get(Type::getInt32Ty(Context), 0));
 659   }
 660
 661   BasicBlock *const PhiBB = Phi.getParent();
 662   // Add a branch to the next basic block in the chain.
 663   if (NextCmpBlock == PhiBB) {
 664     // Continue to phi, passing it the comparison result.
 665     Builder.CreateBr(PhiBB);
 666     Phi.addIncoming(IsEqual, BB);
 667     DTU.applyUpdates({{DominatorTree::Insert, BB, PhiBB}});
 668   } else {
 669     // Continue to next block if equal, exit to phi else.
 670     Builder.CreateCondBr(IsEqual, NextCmpBlock, PhiBB);
 671     Phi.addIncoming(ConstantInt::getFalse(Context), BB);
 672     DTU.applyUpdates({{DominatorTree::Insert, BB, NextCmpBlock},
 673                       {DominatorTree::Insert, BB, PhiBB}});
 674   }
 675   return BB;
 676 }
 677
 678 bool BCECmpChain::simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA,
 679                            DomTreeUpdater &DTU) {
 680   assert(Comparisons_.size() >= 2 && "simplifying trivial BCECmpChain");
 681   // First pass to check if there is at least one merge. If not, we don't do
 682   // anything and we keep analysis passes intact.
 683   const auto AtLeastOneMerged = [this]() {
 684     for (size_t I = 1; I < Comparisons_.size(); ++I) {
 685       if (IsContiguous(Comparisons_[I - 1], Comparisons_[I]))
 686         return true;
 687     }
 688     return false;
 689   };
 690   if (!AtLeastOneMerged())
 691     return false;
 692
 693   LLVM_DEBUG(dbgs() << "Simplifying comparison chain starting at block "
 694                     << EntryBlock_->getName() << "\n");
 695
 696   // Effectively merge blocks. We go in the reverse direction from the phi block
 697   // so that the next block is always available to branch to.
 698   const auto mergeRange = [this, &TLI, &AA, &DTU](int I, int Num,
 699                                                   BasicBlock *InsertBefore,
 700                                                   BasicBlock *Next) {
 701     return mergeComparisons(makeArrayRef(Comparisons_).slice(I, Num),
 702                             InsertBefore, Next, Phi_, TLI, AA, DTU);
 703   };
 704   int NumMerged = 1;
 705   BasicBlock *NextCmpBlock = Phi_.getParent();
 706   for (int I = static_cast<int>(Comparisons_.size()) - 2; I >= 0; --I) {
 707     if (IsContiguous(Comparisons_[I], Comparisons_[I + 1])) {
 708       LLVM_DEBUG(dbgs() << "Merging block " << Comparisons_[I].BB->getName()
 709                         << " into " << Comparisons_[I + 1].BB->getName()
 710                         << "\n");
 711       ++NumMerged;
 712     } else {
 713       NextCmpBlock = mergeRange(I + 1, NumMerged, NextCmpBlock, NextCmpBlock);
 714       NumMerged = 1;
 715     }
 716   }
 717   // Insert the entry block for the new chain before the old entry block.
 718   // If the old entry block was the function entry, this ensures that the new
 719   // entry can become the function entry.
 720   NextCmpBlock = mergeRange(0, NumMerged, EntryBlock_, NextCmpBlock);
 721
 722   // Replace the original cmp chain with the new cmp chain by pointing all
 723   // predecessors of EntryBlock_ to NextCmpBlock instead. This makes all cmp
 724   // blocks in the old chain unreachable.
 725   while (!pred_empty(EntryBlock_)) {
 726     BasicBlock* const Pred = *pred_begin(EntryBlock_);
 727     LLVM_DEBUG(dbgs() << "Updating jump into old chain from " << Pred->getName()
 728                       << "\n");
 729     Pred->getTerminator()->replaceUsesOfWith(EntryBlock_, NextCmpBlock);
 730     DTU.applyUpdates({{DominatorTree::Delete, Pred, EntryBlock_},
 731                       {DominatorTree::Insert, Pred, NextCmpBlock}});
 732   }
 733
 734   // If the old cmp chain was the function entry, we need to update the function
 735   // entry.
 736   const bool ChainEntryIsFnEntry =
 737       (EntryBlock_ == &EntryBlock_->getParent()->getEntryBlock());
 738   if (ChainEntryIsFnEntry && DTU.hasDomTree()) {
 739     LLVM_DEBUG(dbgs() << "Changing function entry from "
 740                       << EntryBlock_->getName() << " to "
 741                       << NextCmpBlock->getName() << "\n");
 742     DTU.getDomTree().setNewRoot(NextCmpBlock);
 743     DTU.applyUpdates({{DominatorTree::Delete, NextCmpBlock, EntryBlock_}});
 744   }
 745   EntryBlock_ = nullptr;
 746
 747   // Delete merged blocks. This also removes incoming values in phi.
 748   SmallVector<BasicBlock *, 16> DeadBlocks;
 749   for (auto &Cmp : Comparisons_) {
 750     LLVM_DEBUG(dbgs() << "Deleting merged block " << Cmp.BB->getName() << "\n");
 751     DeadBlocks.push_back(Cmp.BB);
 752   }
 753   DeleteDeadBlocks(DeadBlocks, &DTU);
 754
 755   Comparisons_.clear();
 756   return true;
 757 }
 758
 759 std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
 760                                            BasicBlock *const LastBlock,
 761                                            int NumBlocks) {
 762   // Walk up from the last block to find other blocks.
 763   std::vector<BasicBlock *> Blocks(NumBlocks);
 764   assert(LastBlock && "invalid last block");
 765   BasicBlock *CurBlock = LastBlock;
 766   for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) {
 767     if (CurBlock->hasAddressTaken()) {
 768       // Somebody is jumping to the block through an address, all bets are
 769       // off.
 770       LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
 771                         << " has its address taken\n");
 772       return {};
 773     }
 774     Blocks[BlockIndex] = CurBlock;
 775     auto *SinglePredecessor = CurBlock->getSinglePredecessor();
 776     if (!SinglePredecessor) {
 777       // The block has two or more predecessors.
 778       LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
 779                         << " has two or more predecessors\n");
 780       return {};
 781     }
 782     if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) {
 783       // The block does not link back to the phi.
 784       LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
 785                         << " does not link back to the phi\n");
 786       return {};
 787     }
 788     CurBlock = SinglePredecessor;
 789   }
 790   Blocks[0] = CurBlock;
 791   return Blocks;
 792 }
 793
 794 bool processPhi(PHINode &Phi, const TargetLibraryInfo &TLI, AliasAnalysis &AA,
 795                 DomTreeUpdater &DTU) {
 796   LLVM_DEBUG(dbgs() << "processPhi()\n");
 797   if (Phi.getNumIncomingValues() <= 1) {
 798     LLVM_DEBUG(dbgs() << "skip: only one incoming value in phi\n");
 799     return false;
 800   }
 801   // We are looking for something that has the following structure:
 802   //   bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+
 803   //     \            \           \               \
 804   //      ne           ne          ne              \
 805   //       \            \           \               v
 806   //        +------------+-----------+----------> bb_phi
 807   //
 808   //  - The last basic block (bb4 here) must branch unconditionally to bb_phi.
 809   //    It's the only block that contributes a non-constant value to the Phi.
 810   //  - All other blocks (b1, b2, b3) must have exactly two successors, one of
 811   //    them being the phi block.
 812   //  - All intermediate blocks (bb2, bb3) must have only one predecessor.
 813   //  - Blocks cannot do other work besides the comparison, see doesOtherWork()
 814
 815   // The blocks are not necessarily ordered in the phi, so we start from the
 816   // last block and reconstruct the order.
 817   BasicBlock *LastBlock = nullptr;
 818   for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) {
 819     if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue;
 820     if (LastBlock) {
 821       // There are several non-constant values.
 822       LLVM_DEBUG(dbgs() << "skip: several non-constant values\n");
 823       return false;
 824     }
 825     if (!isa<ICmpInst>(Phi.getIncomingValue(I)) ||
 826         cast<ICmpInst>(Phi.getIncomingValue(I))->getParent() !=
 827             Phi.getIncomingBlock(I)) {
 828       // Non-constant incoming value is not from a cmp instruction or not
 829       // produced by the last block. We could end up processing the value
 830       // producing block more than once.
 831       //
 832       // This is an uncommon case, so we bail.
 833       LLVM_DEBUG(
 834           dbgs()
 835           << "skip: non-constant value not from cmp or not from last block.\n");
 836       return false;
 837     }
 838     LastBlock = Phi.getIncomingBlock(I);
 839   }
 840   if (!LastBlock) {
 841     // There is no non-constant block.
 842     LLVM_DEBUG(dbgs() << "skip: no non-constant block\n");
 843     return false;
 844   }
 845   if (LastBlock->getSingleSuccessor() != Phi.getParent()) {
 846     LLVM_DEBUG(dbgs() << "skip: last block non-phi successor\n");
 847     return false;
 848   }
 849
 850   const auto Blocks =
 851       getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues());
 852   if (Blocks.empty()) return false;
 853   BCECmpChain CmpChain(Blocks, Phi, AA);
 854
 855   if (CmpChain.size() < 2) {
 856     LLVM_DEBUG(dbgs() << "skip: only one compare block\n");
 857     return false;
 858   }
 859
 860   return CmpChain.simplify(TLI, AA, DTU);
 861 }
 862
 863 static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
 864                     const TargetTransformInfo &TTI, AliasAnalysis &AA,
 865                     DominatorTree *DT) {
 866   LLVM_DEBUG(dbgs() << "MergeICmpsLegacyPass: " << F.getName() << "\n");
 867
 868   // We only try merging comparisons if the target wants to expand memcmp later.
 869   // The rationale is to avoid turning small chains into memcmp calls.
 870   if (!TTI.enableMemCmpExpansion(F.hasOptSize(), true))
 871     return false;
 872
 873   // If we don't have memcmp avaiable we can't emit calls to it.
 874   if (!TLI.has(LibFunc_memcmp))
 875     return false;
 876
 877   DomTreeUpdater DTU(DT, /*PostDominatorTree*/ nullptr,
 878                      DomTreeUpdater::UpdateStrategy::Eager);
 879
 880   bool MadeChange = false;
 881
 882   for (auto BBIt = ++F.begin(); BBIt != F.end(); ++BBIt) {
 883     // A Phi operation is always first in a basic block.
 884     if (auto *const Phi = dyn_cast<PHINode>(&*BBIt->begin()))
 885       MadeChange |= processPhi(*Phi, TLI, AA, DTU);
 886   }
 887
 888   return MadeChange;
 889 }
 890
 891 class MergeICmpsLegacyPass : public FunctionPass {
 892 public:
 893   static char ID;
 894
 895   MergeICmpsLegacyPass() : FunctionPass(ID) {
 896     initializeMergeICmpsLegacyPassPass(*PassRegistry::getPassRegistry());
 897   }
 898
 899   bool runOnFunction(Function &F) override {
 900     if (skipFunction(F)) return false;
 901     const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
 902     const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 903     // MergeICmps does not need the DominatorTree, but we update it if it's
 904     // already available.
 905     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
 906     auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
 907     return runImpl(F, TLI, TTI, AA, DTWP ? &DTWP->getDomTree() : nullptr);
 908   }
 909
 910  private:
 911   void getAnalysisUsage(AnalysisUsage &AU) const override {
 912     AU.addRequired<TargetLibraryInfoWrapperPass>();
 913     AU.addRequired<TargetTransformInfoWrapperPass>();
 914     AU.addRequired<AAResultsWrapperPass>();
 915     AU.addPreserved<GlobalsAAWrapperPass>();
 916     AU.addPreserved<DominatorTreeWrapperPass>();
 917   }
 918 };
 919
 920 } // namespace
 921
 922 char MergeICmpsLegacyPass::ID = 0;
 923 INITIALIZE_PASS_BEGIN(MergeICmpsLegacyPass, "mergeicmps",
 924                       "Merge contiguous icmps into a memcmp", false, false)
 925 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 926 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 927 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 928 INITIALIZE_PASS_END(MergeICmpsLegacyPass, "mergeicmps",
 929                     "Merge contiguous icmps into a memcmp", false, false)
 930
 931 Pass *llvm::createMergeICmpsLegacyPass() { return new MergeICmpsLegacyPass(); }
 932
 933 PreservedAnalyses MergeICmpsPass::run(Function &F,
 934                                       FunctionAnalysisManager &AM) {
 935   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
 936   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
 937   auto &AA = AM.getResult<AAManager>(F);
 938   auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
 939   const bool MadeChanges = runImpl(F, TLI, TTI, AA, DT);
 940   if (!MadeChanges)
 941     return PreservedAnalyses::all();
 942   PreservedAnalyses PA;
 943   PA.preserve<GlobalsAA>();
 944   PA.preserve<DominatorTreeAnalysis>();
 945   return PA;
 946 }