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