contrib/llvm/lib/Transforms/Scalar/MergeICmps.cpp

   1 //===- MergeICmps.cpp - Optimize chains of integer comparisons ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass turns chains of integer comparisons into memcmp (the memcmp is
  11 // later typically inlined as a chain of efficient hardware comparisons). This
  12 // typically benefits c++ member or nonmember operator==().
  13 //
  14 // The basic idea is to replace a larger chain of integer comparisons loaded
  15 // from contiguous memory locations into a smaller chain of such integer
  16 // comparisons. Benefits are double:
  17 //  - There are less jumps, and therefore less opportunities for mispredictions
  18 //    and I-cache misses.
  19 //  - Code size is smaller, both because jumps are removed and because the
  20 //    encoding of a 2*n byte compare is smaller than that of two n-byte
  21 //    compares.
  22
  23 //===----------------------------------------------------------------------===//
  24
  25 #include <algorithm>
  26 #include <numeric>
  27 #include <utility>
  28 #include <vector>
  29 #include "llvm/Analysis/Loads.h"
  30 #include "llvm/Analysis/TargetLibraryInfo.h"
  31 #include "llvm/Analysis/TargetTransformInfo.h"
  32 #include "llvm/IR/Function.h"
  33 #include "llvm/IR/IRBuilder.h"
  34 #include "llvm/Pass.h"
  35 #include "llvm/Transforms/Scalar.h"
  36 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  37
  38 using namespace llvm;
  39
  40 namespace {
  41
  42 #define DEBUG_TYPE "mergeicmps"
  43
  44 // A BCE atom.
  45 struct BCEAtom {
  46   BCEAtom() : GEP(nullptr), LoadI(nullptr), Offset() {}
  47
  48   const Value *Base() const { return GEP ? GEP->getPointerOperand() : nullptr; }
  49
  50   bool operator<(const BCEAtom &O) const {
  51     assert(Base() && "invalid atom");
  52     assert(O.Base() && "invalid atom");
  53     // Just ordering by (Base(), Offset) is sufficient. However because this
  54     // means that the ordering will depend on the addresses of the base
  55     // values, which are not reproducible from run to run. To guarantee
  56     // stability, we use the names of the values if they exist; we sort by:
  57     // (Base.getName(), Base(), Offset).
  58     const int NameCmp = Base()->getName().compare(O.Base()->getName());
  59     if (NameCmp == 0) {
  60       if (Base() == O.Base()) {
  61         return Offset.slt(O.Offset);
  62       }
  63       return Base() < O.Base();
  64     }
  65     return NameCmp < 0;
  66   }
  67
  68   GetElementPtrInst *GEP;
  69   LoadInst *LoadI;
  70   APInt Offset;
  71 };
  72
  73 // If this value is a load from a constant offset w.r.t. a base address, and
  74 // there are no othe rusers of the load or address, returns the base address and
  75 // the offset.
  76 BCEAtom visitICmpLoadOperand(Value *const Val) {
  77   BCEAtom Result;
  78   if (auto *const LoadI = dyn_cast<LoadInst>(Val)) {
  79     DEBUG(dbgs() << "load\n");
  80     if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {
  81       DEBUG(dbgs() << "used outside of block\n");
  82       return {};
  83     }
  84     if (LoadI->isVolatile()) {
  85       DEBUG(dbgs() << "volatile\n");
  86       return {};
  87     }
  88     Value *const Addr = LoadI->getOperand(0);
  89     if (auto *const GEP = dyn_cast<GetElementPtrInst>(Addr)) {
  90       DEBUG(dbgs() << "GEP\n");
  91       if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {
  92         DEBUG(dbgs() << "used outside of block\n");
  93         return {};
  94       }
  95       const auto &DL = GEP->getModule()->getDataLayout();
  96       if (!isDereferenceablePointer(GEP, DL)) {
  97         DEBUG(dbgs() << "not dereferenceable\n");
  98         // We need to make sure that we can do comparison in any order, so we
  99         // require memory to be unconditionnally dereferencable.
 100         return {};
 101       }
 102       Result.Offset = APInt(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
 103       if (GEP->accumulateConstantOffset(DL, Result.Offset)) {
 104         Result.GEP = GEP;
 105         Result.LoadI = LoadI;
 106       }
 107     }
 108   }
 109   return Result;
 110 }
 111
 112 // A basic block with a comparison between two BCE atoms.
 113 // Note: the terminology is misleading: the comparison is symmetric, so there
 114 // is no real {l/r}hs. What we want though is to have the same base on the
 115 // left (resp. right), so that we can detect consecutive loads. To ensure this
 116 // we put the smallest atom on the left.
 117 class BCECmpBlock {
 118  public:
 119   BCECmpBlock() {}
 120
 121   BCECmpBlock(BCEAtom L, BCEAtom R, int SizeBits)
 122       : Lhs_(L), Rhs_(R), SizeBits_(SizeBits) {
 123     if (Rhs_ < Lhs_) std::swap(Rhs_, Lhs_);
 124   }
 125
 126   bool IsValid() const {
 127     return Lhs_.Base() != nullptr && Rhs_.Base() != nullptr;
 128   }
 129
 130   // Assert the the block is consistent: If valid, it should also have
 131   // non-null members besides Lhs_ and Rhs_.
 132   void AssertConsistent() const {
 133     if (IsValid()) {
 134       assert(BB);
 135       assert(CmpI);
 136       assert(BranchI);
 137     }
 138   }
 139
 140   const BCEAtom &Lhs() const { return Lhs_; }
 141   const BCEAtom &Rhs() const { return Rhs_; }
 142   int SizeBits() const { return SizeBits_; }
 143
 144   // Returns true if the block does other works besides comparison.
 145   bool doesOtherWork() const;
 146
 147   // The basic block where this comparison happens.
 148   BasicBlock *BB = nullptr;
 149   // The ICMP for this comparison.
 150   ICmpInst *CmpI = nullptr;
 151   // The terminating branch.
 152   BranchInst *BranchI = nullptr;
 153
 154  private:
 155   BCEAtom Lhs_;
 156   BCEAtom Rhs_;
 157   int SizeBits_ = 0;
 158 };
 159
 160 bool BCECmpBlock::doesOtherWork() const {
 161   AssertConsistent();
 162   // TODO(courbet): Can we allow some other things ? This is very conservative.
 163   // We might be able to get away with anything does does not have any side
 164   // effects outside of the basic block.
 165   // Note: The GEPs and/or loads are not necessarily in the same block.
 166   for (const Instruction &Inst : *BB) {
 167     if (const auto *const GEP = dyn_cast<GetElementPtrInst>(&Inst)) {
 168       if (!(Lhs_.GEP == GEP || Rhs_.GEP == GEP)) return true;
 169     } else if (const auto *const L = dyn_cast<LoadInst>(&Inst)) {
 170       if (!(Lhs_.LoadI == L || Rhs_.LoadI == L)) return true;
 171     } else if (const auto *const C = dyn_cast<ICmpInst>(&Inst)) {
 172       if (C != CmpI) return true;
 173     } else if (const auto *const Br = dyn_cast<BranchInst>(&Inst)) {
 174       if (Br != BranchI) return true;
 175     } else {
 176       return true;
 177     }
 178   }
 179   return false;
 180 }
 181
 182 // Visit the given comparison. If this is a comparison between two valid
 183 // BCE atoms, returns the comparison.
 184 BCECmpBlock visitICmp(const ICmpInst *const CmpI,
 185                       const ICmpInst::Predicate ExpectedPredicate) {
 186   if (CmpI->getPredicate() == ExpectedPredicate) {
 187     DEBUG(dbgs() << "cmp "
 188                  << (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne")
 189                  << "\n");
 190     auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0));
 191     if (!Lhs.Base()) return {};
 192     auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1));
 193     if (!Rhs.Base()) return {};
 194     return BCECmpBlock(std::move(Lhs), std::move(Rhs),
 195                        CmpI->getOperand(0)->getType()->getScalarSizeInBits());
 196   }
 197   return {};
 198 }
 199
 200 // Visit the given comparison block. If this is a comparison between two valid
 201 // BCE atoms, returns the comparison.
 202 BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block,
 203                           const BasicBlock *const PhiBlock) {
 204   if (Block->empty()) return {};
 205   auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator());
 206   if (!BranchI) return {};
 207   DEBUG(dbgs() << "branch\n");
 208   if (BranchI->isUnconditional()) {
 209     // In this case, we expect an incoming value which is the result of the
 210     // comparison. This is the last link in the chain of comparisons (note
 211     // that this does not mean that this is the last incoming value, blocks
 212     // can be reordered).
 213     auto *const CmpI = dyn_cast<ICmpInst>(Val);
 214     if (!CmpI) return {};
 215     DEBUG(dbgs() << "icmp\n");
 216     auto Result = visitICmp(CmpI, ICmpInst::ICMP_EQ);
 217     Result.CmpI = CmpI;
 218     Result.BranchI = BranchI;
 219     return Result;
 220   } else {
 221     // In this case, we expect a constant incoming value (the comparison is
 222     // chained).
 223     const auto *const Const = dyn_cast<ConstantInt>(Val);
 224     DEBUG(dbgs() << "const\n");
 225     if (!Const->isZero()) return {};
 226     DEBUG(dbgs() << "false\n");
 227     auto *const CmpI = dyn_cast<ICmpInst>(BranchI->getCondition());
 228     if (!CmpI) return {};
 229     DEBUG(dbgs() << "icmp\n");
 230     assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch");
 231     BasicBlock *const FalseBlock = BranchI->getSuccessor(1);
 232     auto Result = visitICmp(
 233         CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE);
 234     Result.CmpI = CmpI;
 235     Result.BranchI = BranchI;
 236     return Result;
 237   }
 238   return {};
 239 }
 240
 241 // A chain of comparisons.
 242 class BCECmpChain {
 243  public:
 244   BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi);
 245
 246   int size() const { return Comparisons_.size(); }
 247
 248 #ifdef MERGEICMPS_DOT_ON
 249   void dump() const;
 250 #endif  // MERGEICMPS_DOT_ON
 251
 252   bool simplify(const TargetLibraryInfo *const TLI);
 253
 254  private:
 255   static bool IsContiguous(const BCECmpBlock &First,
 256                            const BCECmpBlock &Second) {
 257     return First.Lhs().Base() == Second.Lhs().Base() &&
 258            First.Rhs().Base() == Second.Rhs().Base() &&
 259            First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset &&
 260            First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset;
 261   }
 262
 263   // Merges the given comparison blocks into one memcmp block and update
 264   // branches. Comparisons are assumed to be continguous. If NextBBInChain is
 265   // null, the merged block will link to the phi block.
 266   static void mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
 267                                BasicBlock *const NextBBInChain, PHINode &Phi,
 268                                const TargetLibraryInfo *const TLI);
 269
 270   PHINode &Phi_;
 271   std::vector<BCECmpBlock> Comparisons_;
 272   // The original entry block (before sorting);
 273   BasicBlock *EntryBlock_;
 274 };
 275
 276 BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi)
 277     : Phi_(Phi) {
 278   // Now look inside blocks to check for BCE comparisons.
 279   std::vector<BCECmpBlock> Comparisons;
 280   for (BasicBlock *Block : Blocks) {
 281     BCECmpBlock Comparison = visitCmpBlock(Phi.getIncomingValueForBlock(Block),
 282                                            Block, Phi.getParent());
 283     Comparison.BB = Block;
 284     if (!Comparison.IsValid()) {
 285       DEBUG(dbgs() << "skip: not a valid BCECmpBlock\n");
 286       return;
 287     }
 288     if (Comparison.doesOtherWork()) {
 289       DEBUG(dbgs() << "block does extra work besides compare\n");
 290       if (Comparisons.empty()) {  // First block.
 291         // TODO(courbet): The first block can do other things, and we should
 292         // split them apart in a separate block before the comparison chain.
 293         // Right now we just discard it and make the chain shorter.
 294         DEBUG(dbgs()
 295               << "ignoring first block that does extra work besides compare\n");
 296         continue;
 297       }
 298       // TODO(courbet): Right now we abort the whole chain. We could be
 299       // merging only the blocks that don't do other work and resume the
 300       // chain from there. For example:
 301       //  if (a[0] == b[0]) {  // bb1
 302       //    if (a[1] == b[1]) {  // bb2
 303       //      some_value = 3; //bb3
 304       //      if (a[2] == b[2]) { //bb3
 305       //        do a ton of stuff  //bb4
 306       //      }
 307       //    }
 308       //  }
 309       //
 310       // This is:
 311       //
 312       // bb1 --eq--> bb2 --eq--> bb3* -eq--> bb4 --+
 313       //  \            \           \               \
 314       //   ne           ne          ne              \
 315       //    \            \           \               v
 316       //     +------------+-----------+----------> bb_phi
 317       //
 318       // We can only merge the first two comparisons, because bb3* does
 319       // "other work" (setting some_value to 3).
 320       // We could still merge bb1 and bb2 though.
 321       return;
 322     }
 323     DEBUG(dbgs() << "*Found cmp of " << Comparison.SizeBits()
 324                  << " bits between " << Comparison.Lhs().Base() << " + "
 325                  << Comparison.Lhs().Offset << " and "
 326                  << Comparison.Rhs().Base() << " + " << Comparison.Rhs().Offset
 327                  << "\n");
 328     DEBUG(dbgs() << "\n");
 329     Comparisons.push_back(Comparison);
 330   }
 331   EntryBlock_ = Comparisons[0].BB;
 332   Comparisons_ = std::move(Comparisons);
 333 #ifdef MERGEICMPS_DOT_ON
 334   errs() << "BEFORE REORDERING:\n\n";
 335   dump();
 336 #endif  // MERGEICMPS_DOT_ON
 337   // Reorder blocks by LHS. We can do that without changing the
 338   // semantics because we are only accessing dereferencable memory.
 339   std::sort(Comparisons_.begin(), Comparisons_.end(),
 340             [](const BCECmpBlock &a, const BCECmpBlock &b) {
 341               return a.Lhs() < b.Lhs();
 342             });
 343 #ifdef MERGEICMPS_DOT_ON
 344   errs() << "AFTER REORDERING:\n\n";
 345   dump();
 346 #endif  // MERGEICMPS_DOT_ON
 347 }
 348
 349 #ifdef MERGEICMPS_DOT_ON
 350 void BCECmpChain::dump() const {
 351   errs() << "digraph dag {\n";
 352   errs() << " graph [bgcolor=transparent];\n";
 353   errs() << " node [color=black,style=filled,fillcolor=lightyellow];\n";
 354   errs() << " edge [color=black];\n";
 355   for (size_t I = 0; I < Comparisons_.size(); ++I) {
 356     const auto &Comparison = Comparisons_[I];
 357     errs() << " \"" << I << "\" [label=\"%"
 358            << Comparison.Lhs().Base()->getName() << " + "
 359            << Comparison.Lhs().Offset << " == %"
 360            << Comparison.Rhs().Base()->getName() << " + "
 361            << Comparison.Rhs().Offset << " (" << (Comparison.SizeBits() / 8)
 362            << " bytes)\"];\n";
 363     const Value *const Val = Phi_.getIncomingValueForBlock(Comparison.BB);
 364     if (I > 0) errs() << " \"" << (I - 1) << "\" -> \"" << I << "\";\n";
 365     errs() << " \"" << I << "\" -> \"Phi\" [label=\"" << *Val << "\"];\n";
 366   }
 367   errs() << " \"Phi\" [label=\"Phi\"];\n";
 368   errs() << "}\n\n";
 369 }
 370 #endif  // MERGEICMPS_DOT_ON
 371
 372 bool BCECmpChain::simplify(const TargetLibraryInfo *const TLI) {
 373   // First pass to check if there is at least one merge. If not, we don't do
 374   // anything and we keep analysis passes intact.
 375   {
 376     bool AtLeastOneMerged = false;
 377     for (size_t I = 1; I < Comparisons_.size(); ++I) {
 378       if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) {
 379         AtLeastOneMerged = true;
 380         break;
 381       }
 382     }
 383     if (!AtLeastOneMerged) return false;
 384   }
 385
 386   // Remove phi references to comparison blocks, they will be rebuilt as we
 387   // merge the blocks.
 388   for (const auto &Comparison : Comparisons_) {
 389     Phi_.removeIncomingValue(Comparison.BB, false);
 390   }
 391
 392   // Point the predecessors of the chain to the first comparison block (which is
 393   // the new entry point).
 394   if (EntryBlock_ != Comparisons_[0].BB)
 395     EntryBlock_->replaceAllUsesWith(Comparisons_[0].BB);
 396
 397   // Effectively merge blocks.
 398   int NumMerged = 1;
 399   for (size_t I = 1; I < Comparisons_.size(); ++I) {
 400     if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) {
 401       ++NumMerged;
 402     } else {
 403       // Merge all previous comparisons and start a new merge block.
 404       mergeComparisons(
 405           makeArrayRef(Comparisons_).slice(I - NumMerged, NumMerged),
 406           Comparisons_[I].BB, Phi_, TLI);
 407       NumMerged = 1;
 408     }
 409   }
 410   mergeComparisons(makeArrayRef(Comparisons_)
 411                        .slice(Comparisons_.size() - NumMerged, NumMerged),
 412                    nullptr, Phi_, TLI);
 413
 414   return true;
 415 }
 416
 417 void BCECmpChain::mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
 418                                    BasicBlock *const NextBBInChain,
 419                                    PHINode &Phi,
 420                                    const TargetLibraryInfo *const TLI) {
 421   assert(!Comparisons.empty());
 422   const auto &FirstComparison = *Comparisons.begin();
 423   BasicBlock *const BB = FirstComparison.BB;
 424   LLVMContext &Context = BB->getContext();
 425
 426   if (Comparisons.size() >= 2) {
 427     DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons\n");
 428     const auto TotalSize =
 429         std::accumulate(Comparisons.begin(), Comparisons.end(), 0,
 430                         [](int Size, const BCECmpBlock &C) {
 431                           return Size + C.SizeBits();
 432                         }) /
 433         8;
 434
 435     // Incoming edges do not need to be updated, and both GEPs are already
 436     // computing the right address, we just need to:
 437     //   - replace the two loads and the icmp with the memcmp
 438     //   - update the branch
 439     //   - update the incoming values in the phi.
 440     FirstComparison.BranchI->eraseFromParent();
 441     FirstComparison.CmpI->eraseFromParent();
 442     FirstComparison.Lhs().LoadI->eraseFromParent();
 443     FirstComparison.Rhs().LoadI->eraseFromParent();
 444
 445     IRBuilder<> Builder(BB);
 446     const auto &DL = Phi.getModule()->getDataLayout();
 447     Value *const MemCmpCall = emitMemCmp(
 448         FirstComparison.Lhs().GEP, FirstComparison.Rhs().GEP, ConstantInt::get(DL.getIntPtrType(Context), TotalSize),
 449         Builder, DL, TLI);
 450     Value *const MemCmpIsZero = Builder.CreateICmpEQ(
 451         MemCmpCall, ConstantInt::get(Type::getInt32Ty(Context), 0));
 452
 453     // Add a branch to the next basic block in the chain.
 454     if (NextBBInChain) {
 455       Builder.CreateCondBr(MemCmpIsZero, NextBBInChain, Phi.getParent());
 456       Phi.addIncoming(ConstantInt::getFalse(Context), BB);
 457     } else {
 458       Builder.CreateBr(Phi.getParent());
 459       Phi.addIncoming(MemCmpIsZero, BB);
 460     }
 461
 462     // Delete merged blocks.
 463     for (size_t I = 1; I < Comparisons.size(); ++I) {
 464       BasicBlock *CBB = Comparisons[I].BB;
 465       CBB->replaceAllUsesWith(BB);
 466       CBB->eraseFromParent();
 467     }
 468   } else {
 469     assert(Comparisons.size() == 1);
 470     // There are no blocks to merge, but we still need to update the branches.
 471     DEBUG(dbgs() << "Only one comparison, updating branches\n");
 472     if (NextBBInChain) {
 473       if (FirstComparison.BranchI->isConditional()) {
 474         DEBUG(dbgs() << "conditional -> conditional\n");
 475         // Just update the "true" target, the "false" target should already be
 476         // the phi block.
 477         assert(FirstComparison.BranchI->getSuccessor(1) == Phi.getParent());
 478         FirstComparison.BranchI->setSuccessor(0, NextBBInChain);
 479         Phi.addIncoming(ConstantInt::getFalse(Context), BB);
 480       } else {
 481         DEBUG(dbgs() << "unconditional -> conditional\n");
 482         // Replace the unconditional branch by a conditional one.
 483         FirstComparison.BranchI->eraseFromParent();
 484         IRBuilder<> Builder(BB);
 485         Builder.CreateCondBr(FirstComparison.CmpI, NextBBInChain,
 486                              Phi.getParent());
 487         Phi.addIncoming(FirstComparison.CmpI, BB);
 488       }
 489     } else {
 490       if (FirstComparison.BranchI->isConditional()) {
 491         DEBUG(dbgs() << "conditional -> unconditional\n");
 492         // Replace the conditional branch by an unconditional one.
 493         FirstComparison.BranchI->eraseFromParent();
 494         IRBuilder<> Builder(BB);
 495         Builder.CreateBr(Phi.getParent());
 496         Phi.addIncoming(FirstComparison.CmpI, BB);
 497       } else {
 498         DEBUG(dbgs() << "unconditional -> unconditional\n");
 499         Phi.addIncoming(FirstComparison.CmpI, BB);
 500       }
 501     }
 502   }
 503 }
 504
 505 std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
 506                                            BasicBlock *const LastBlock,
 507                                            int NumBlocks) {
 508   // Walk up from the last block to find other blocks.
 509   std::vector<BasicBlock *> Blocks(NumBlocks);
 510   BasicBlock *CurBlock = LastBlock;
 511   for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) {
 512     if (CurBlock->hasAddressTaken()) {
 513       // Somebody is jumping to the block through an address, all bets are
 514       // off.
 515       DEBUG(dbgs() << "skip: block " << BlockIndex
 516                    << " has its address taken\n");
 517       return {};
 518     }
 519     Blocks[BlockIndex] = CurBlock;
 520     auto *SinglePredecessor = CurBlock->getSinglePredecessor();
 521     if (!SinglePredecessor) {
 522       // The block has two or more predecessors.
 523       DEBUG(dbgs() << "skip: block " << BlockIndex
 524                    << " has two or more predecessors\n");
 525       return {};
 526     }
 527     if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) {
 528       // The block does not link back to the phi.
 529       DEBUG(dbgs() << "skip: block " << BlockIndex
 530                    << " does not link back to the phi\n");
 531       return {};
 532     }
 533     CurBlock = SinglePredecessor;
 534   }
 535   Blocks[0] = CurBlock;
 536   return Blocks;
 537 }
 538
 539 bool processPhi(PHINode &Phi, const TargetLibraryInfo *const TLI) {
 540   DEBUG(dbgs() << "processPhi()\n");
 541   if (Phi.getNumIncomingValues() <= 1) {
 542     DEBUG(dbgs() << "skip: only one incoming value in phi\n");
 543     return false;
 544   }
 545   // We are looking for something that has the following structure:
 546   //   bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+
 547   //     \            \           \               \
 548   //      ne           ne          ne              \
 549   //       \            \           \               v
 550   //        +------------+-----------+----------> bb_phi
 551   //
 552   //  - The last basic block (bb4 here) must branch unconditionally to bb_phi.
 553   //    It's the only block that contributes a non-constant value to the Phi.
 554   //  - All other blocks (b1, b2, b3) must have exactly two successors, one of
 555   //    them being the the phi block.
 556   //  - All intermediate blocks (bb2, bb3) must have only one predecessor.
 557   //  - Blocks cannot do other work besides the comparison, see doesOtherWork()
 558
 559   // The blocks are not necessarily ordered in the phi, so we start from the
 560   // last block and reconstruct the order.
 561   BasicBlock *LastBlock = nullptr;
 562   for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) {
 563     if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue;
 564     if (LastBlock) {
 565       // There are several non-constant values.
 566       DEBUG(dbgs() << "skip: several non-constant values\n");
 567       return false;
 568     }
 569     LastBlock = Phi.getIncomingBlock(I);
 570   }
 571   if (!LastBlock) {
 572     // There is no non-constant block.
 573     DEBUG(dbgs() << "skip: no non-constant block\n");
 574     return false;
 575   }
 576   if (LastBlock->getSingleSuccessor() != Phi.getParent()) {
 577     DEBUG(dbgs() << "skip: last block non-phi successor\n");
 578     return false;
 579   }
 580
 581   const auto Blocks =
 582       getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues());
 583   if (Blocks.empty()) return false;
 584   BCECmpChain CmpChain(Blocks, Phi);
 585
 586   if (CmpChain.size() < 2) {
 587     DEBUG(dbgs() << "skip: only one compare block\n");
 588     return false;
 589   }
 590
 591   return CmpChain.simplify(TLI);
 592 }
 593
 594 class MergeICmps : public FunctionPass {
 595  public:
 596   static char ID;
 597
 598   MergeICmps() : FunctionPass(ID) {
 599     initializeMergeICmpsPass(*PassRegistry::getPassRegistry());
 600   }
 601
 602   bool runOnFunction(Function &F) override {
 603     if (skipFunction(F)) return false;
 604     const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 605     const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 606     auto PA = runImpl(F, &TLI, &TTI);
 607     return !PA.areAllPreserved();
 608   }
 609
 610  private:
 611   void getAnalysisUsage(AnalysisUsage &AU) const override {
 612     AU.addRequired<TargetLibraryInfoWrapperPass>();
 613     AU.addRequired<TargetTransformInfoWrapperPass>();
 614   }
 615
 616   PreservedAnalyses runImpl(Function &F, const TargetLibraryInfo *TLI,
 617                             const TargetTransformInfo *TTI);
 618 };
 619
 620 PreservedAnalyses MergeICmps::runImpl(Function &F, const TargetLibraryInfo *TLI,
 621                                       const TargetTransformInfo *TTI) {
 622   DEBUG(dbgs() << "MergeICmpsPass: " << F.getName() << "\n");
 623
 624   // We only try merging comparisons if the target wants to expand memcmp later.
 625   // The rationale is to avoid turning small chains into memcmp calls.
 626   if (!TTI->enableMemCmpExpansion(true)) return PreservedAnalyses::all();
 627
 628   bool MadeChange = false;
 629
 630   for (auto BBIt = ++F.begin(); BBIt != F.end(); ++BBIt) {
 631     // A Phi operation is always first in a basic block.
 632     if (auto *const Phi = dyn_cast<PHINode>(&*BBIt->begin()))
 633       MadeChange |= processPhi(*Phi, TLI);
 634   }
 635
 636   if (MadeChange) return PreservedAnalyses::none();
 637   return PreservedAnalyses::all();
 638 }
 639
 640 }  // namespace
 641
 642 char MergeICmps::ID = 0;
 643 INITIALIZE_PASS_BEGIN(MergeICmps, "mergeicmps",
 644                       "Merge contiguous icmps into a memcmp", false, false)
 645 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 646 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 647 INITIALIZE_PASS_END(MergeICmps, "mergeicmps",
 648                     "Merge contiguous icmps into a memcmp", false, false)
 649
 650 Pass *llvm::createMergeICmpsPass() { return new MergeICmps(); }