LLVM  8.0.0svn
MergeICmps.cpp
Go to the documentation of this file.
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"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/IRBuilder.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Transforms/Scalar.h"
37 
38 using namespace llvm;
39 
40 namespace {
41 
42 #define DEBUG_TYPE "mergeicmps"
43 
44 // Returns true if the instruction is a simple load or a simple store
45 static bool isSimpleLoadOrStore(const Instruction *I) {
46  if (const LoadInst *LI = dyn_cast<LoadInst>(I))
47  return LI->isSimple();
48  if (const StoreInst *SI = dyn_cast<StoreInst>(I))
49  return SI->isSimple();
50  return false;
51 }
52 
53 // A BCE atom.
54 struct BCEAtom {
55  BCEAtom() : GEP(nullptr), LoadI(nullptr), Offset() {}
56 
57  const Value *Base() const { return GEP ? GEP->getPointerOperand() : nullptr; }
58 
59  bool operator<(const BCEAtom &O) const {
60  assert(Base() && "invalid atom");
61  assert(O.Base() && "invalid atom");
62  // Just ordering by (Base(), Offset) is sufficient. However because this
63  // means that the ordering will depend on the addresses of the base
64  // values, which are not reproducible from run to run. To guarantee
65  // stability, we use the names of the values if they exist; we sort by:
66  // (Base.getName(), Base(), Offset).
67  const int NameCmp = Base()->getName().compare(O.Base()->getName());
68  if (NameCmp == 0) {
69  if (Base() == O.Base()) {
70  return Offset.slt(O.Offset);
71  }
72  return Base() < O.Base();
73  }
74  return NameCmp < 0;
75  }
76 
78  LoadInst *LoadI;
79  APInt Offset;
80 };
81 
82 // If this value is a load from a constant offset w.r.t. a base address, and
83 // there are no other users of the load or address, returns the base address and
84 // the offset.
85 BCEAtom visitICmpLoadOperand(Value *const Val) {
86  BCEAtom Result;
87  if (auto *const LoadI = dyn_cast<LoadInst>(Val)) {
88  LLVM_DEBUG(dbgs() << "load\n");
89  if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {
90  LLVM_DEBUG(dbgs() << "used outside of block\n");
91  return {};
92  }
93  // Do not optimize atomic loads to non-atomic memcmp
94  if (!LoadI->isSimple()) {
95  LLVM_DEBUG(dbgs() << "volatile or atomic\n");
96  return {};
97  }
98  Value *const Addr = LoadI->getOperand(0);
99  if (auto *const GEP = dyn_cast<GetElementPtrInst>(Addr)) {
100  LLVM_DEBUG(dbgs() << "GEP\n");
101  if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {
102  LLVM_DEBUG(dbgs() << "used outside of block\n");
103  return {};
104  }
105  const auto &DL = GEP->getModule()->getDataLayout();
106  if (!isDereferenceablePointer(GEP, DL)) {
107  LLVM_DEBUG(dbgs() << "not dereferenceable\n");
108  // We need to make sure that we can do comparison in any order, so we
109  // require memory to be unconditionnally dereferencable.
110  return {};
111  }
112  Result.Offset = APInt(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
113  if (GEP->accumulateConstantOffset(DL, Result.Offset)) {
114  Result.GEP = GEP;
115  Result.LoadI = LoadI;
116  }
117  }
118  }
119  return Result;
120 }
121 
122 // A basic block with a comparison between two BCE atoms.
123 // The block might do extra work besides the atom comparison, in which case
124 // doesOtherWork() returns true. Under some conditions, the block can be
125 // split into the atom comparison part and the "other work" part
126 // (see canSplit()).
127 // Note: the terminology is misleading: the comparison is symmetric, so there
128 // is no real {l/r}hs. What we want though is to have the same base on the
129 // left (resp. right), so that we can detect consecutive loads. To ensure this
130 // we put the smallest atom on the left.
131 class BCECmpBlock {
132  public:
133  BCECmpBlock() {}
134 
135  BCECmpBlock(BCEAtom L, BCEAtom R, int SizeBits)
136  : Lhs_(L), Rhs_(R), SizeBits_(SizeBits) {
137  if (Rhs_ < Lhs_) std::swap(Rhs_, Lhs_);
138  }
139 
140  bool IsValid() const {
141  return Lhs_.Base() != nullptr && Rhs_.Base() != nullptr;
142  }
143 
144  // Assert the block is consistent: If valid, it should also have
145  // non-null members besides Lhs_ and Rhs_.
146  void AssertConsistent() const {
147  if (IsValid()) {
148  assert(BB);
149  assert(CmpI);
150  assert(BranchI);
151  }
152  }
153 
154  const BCEAtom &Lhs() const { return Lhs_; }
155  const BCEAtom &Rhs() const { return Rhs_; }
156  int SizeBits() const { return SizeBits_; }
157 
158  // Returns true if the block does other works besides comparison.
159  bool doesOtherWork() const;
160 
161  // Returns true if the non-BCE-cmp instructions can be separated from BCE-cmp
162  // instructions in the block.
163  bool canSplit(AliasAnalysis *AA) const;
164 
165  // Return true if this all the relevant instructions in the BCE-cmp-block can
166  // be sunk below this instruction. By doing this, we know we can separate the
167  // BCE-cmp-block instructions from the non-BCE-cmp-block instructions in the
168  // block.
169  bool canSinkBCECmpInst(const Instruction *, DenseSet<Instruction *> &,
170  AliasAnalysis *AA) const;
171 
172  // We can separate the BCE-cmp-block instructions and the non-BCE-cmp-block
173  // instructions. Split the old block and move all non-BCE-cmp-insts into the
174  // new parent block.
175  void split(BasicBlock *NewParent, AliasAnalysis *AA) const;
176 
177  // The basic block where this comparison happens.
178  BasicBlock *BB = nullptr;
179  // The ICMP for this comparison.
180  ICmpInst *CmpI = nullptr;
181  // The terminating branch.
182  BranchInst *BranchI = nullptr;
183  // The block requires splitting.
184  bool RequireSplit = false;
185 
186 private:
187  BCEAtom Lhs_;
188  BCEAtom Rhs_;
189  int SizeBits_ = 0;
190 };
191 
192 bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst,
193  DenseSet<Instruction *> &BlockInsts,
194  AliasAnalysis *AA) const {
195  // If this instruction has side effects and its in middle of the BCE cmp block
196  // instructions, then bail for now.
197  if (Inst->mayHaveSideEffects()) {
198  // Bail if this is not a simple load or store
199  if (!isSimpleLoadOrStore(Inst))
200  return false;
201  // Disallow stores that might alias the BCE operands
202  MemoryLocation LLoc = MemoryLocation::get(Lhs_.LoadI);
203  MemoryLocation RLoc = MemoryLocation::get(Rhs_.LoadI);
204  if (isModSet(AA->getModRefInfo(Inst, LLoc)) ||
205  isModSet(AA->getModRefInfo(Inst, RLoc)))
206  return false;
207  }
208  // Make sure this instruction does not use any of the BCE cmp block
209  // instructions as operand.
210  for (auto BI : BlockInsts) {
211  if (is_contained(Inst->operands(), BI))
212  return false;
213  }
214  return true;
215 }
216 
217 void BCECmpBlock::split(BasicBlock *NewParent, AliasAnalysis *AA) const {
218  DenseSet<Instruction *> BlockInsts(
219  {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
221  for (Instruction &Inst : *BB) {
222  if (BlockInsts.count(&Inst))
223  continue;
224  assert(canSinkBCECmpInst(&Inst, BlockInsts, AA) &&
225  "Split unsplittable block");
226  // This is a non-BCE-cmp-block instruction. And it can be separated
227  // from the BCE-cmp-block instruction.
228  OtherInsts.push_back(&Inst);
229  }
230 
231  // Do the actual spliting.
232  for (Instruction *Inst : reverse(OtherInsts)) {
233  Inst->moveBefore(&*NewParent->begin());
234  }
235 }
236 
237 bool BCECmpBlock::canSplit(AliasAnalysis *AA) const {
238  DenseSet<Instruction *> BlockInsts(
239  {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
240  for (Instruction &Inst : *BB) {
241  if (!BlockInsts.count(&Inst)) {
242  if (!canSinkBCECmpInst(&Inst, BlockInsts, AA))
243  return false;
244  }
245  }
246  return true;
247 }
248 
249 bool BCECmpBlock::doesOtherWork() const {
250  AssertConsistent();
251  // All the instructions we care about in the BCE cmp block.
252  DenseSet<Instruction *> BlockInsts(
253  {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
254  // TODO(courbet): Can we allow some other things ? This is very conservative.
255  // We might be able to get away with anything does not have any side
256  // effects outside of the basic block.
257  // Note: The GEPs and/or loads are not necessarily in the same block.
258  for (const Instruction &Inst : *BB) {
259  if (!BlockInsts.count(&Inst))
260  return true;
261  }
262  return false;
263 }
264 
265 // Visit the given comparison. If this is a comparison between two valid
266 // BCE atoms, returns the comparison.
267 BCECmpBlock visitICmp(const ICmpInst *const CmpI,
268  const ICmpInst::Predicate ExpectedPredicate) {
269  // The comparison can only be used once:
270  // - For intermediate blocks, as a branch condition.
271  // - For the final block, as an incoming value for the Phi.
272  // If there are any other uses of the comparison, we cannot merge it with
273  // other comparisons as we would create an orphan use of the value.
274  if (!CmpI->hasOneUse()) {
275  LLVM_DEBUG(dbgs() << "cmp has several uses\n");
276  return {};
277  }
278  if (CmpI->getPredicate() == ExpectedPredicate) {
279  LLVM_DEBUG(dbgs() << "cmp "
280  << (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne")
281  << "\n");
282  auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0));
283  if (!Lhs.Base()) return {};
284  auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1));
285  if (!Rhs.Base()) return {};
286  return BCECmpBlock(std::move(Lhs), std::move(Rhs),
287  CmpI->getOperand(0)->getType()->getScalarSizeInBits());
288  }
289  return {};
290 }
291 
292 // Visit the given comparison block. If this is a comparison between two valid
293 // BCE atoms, returns the comparison.
294 BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block,
295  const BasicBlock *const PhiBlock) {
296  if (Block->empty()) return {};
297  auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator());
298  if (!BranchI) return {};
299  LLVM_DEBUG(dbgs() << "branch\n");
300  if (BranchI->isUnconditional()) {
301  // In this case, we expect an incoming value which is the result of the
302  // comparison. This is the last link in the chain of comparisons (note
303  // that this does not mean that this is the last incoming value, blocks
304  // can be reordered).
305  auto *const CmpI = dyn_cast<ICmpInst>(Val);
306  if (!CmpI) return {};
307  LLVM_DEBUG(dbgs() << "icmp\n");
308  auto Result = visitICmp(CmpI, ICmpInst::ICMP_EQ);
309  Result.CmpI = CmpI;
310  Result.BranchI = BranchI;
311  return Result;
312  } else {
313  // In this case, we expect a constant incoming value (the comparison is
314  // chained).
315  const auto *const Const = dyn_cast<ConstantInt>(Val);
316  LLVM_DEBUG(dbgs() << "const\n");
317  if (!Const->isZero()) return {};
318  LLVM_DEBUG(dbgs() << "false\n");
319  auto *const CmpI = dyn_cast<ICmpInst>(BranchI->getCondition());
320  if (!CmpI) return {};
321  LLVM_DEBUG(dbgs() << "icmp\n");
322  assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch");
323  BasicBlock *const FalseBlock = BranchI->getSuccessor(1);
324  auto Result = visitICmp(
325  CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE);
326  Result.CmpI = CmpI;
327  Result.BranchI = BranchI;
328  return Result;
329  }
330  return {};
331 }
332 
333 static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons,
334  BCECmpBlock &Comparison) {
335  LLVM_DEBUG(dbgs() << "Block '" << Comparison.BB->getName()
336  << "': Found cmp of " << Comparison.SizeBits()
337  << " bits between " << Comparison.Lhs().Base() << " + "
338  << Comparison.Lhs().Offset << " and "
339  << Comparison.Rhs().Base() << " + "
340  << Comparison.Rhs().Offset << "\n");
341  LLVM_DEBUG(dbgs() << "\n");
342  Comparisons.push_back(Comparison);
343 }
344 
345 // A chain of comparisons.
346 class BCECmpChain {
347  public:
348  BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
349  AliasAnalysis *AA);
350 
351  int size() const { return Comparisons_.size(); }
352 
353 #ifdef MERGEICMPS_DOT_ON
354  void dump() const;
355 #endif // MERGEICMPS_DOT_ON
356 
357  bool simplify(const TargetLibraryInfo *const TLI, AliasAnalysis *AA);
358 
359  private:
360  static bool IsContiguous(const BCECmpBlock &First,
361  const BCECmpBlock &Second) {
362  return First.Lhs().Base() == Second.Lhs().Base() &&
363  First.Rhs().Base() == Second.Rhs().Base() &&
364  First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset &&
365  First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset;
366  }
367 
368  // Merges the given comparison blocks into one memcmp block and update
369  // branches. Comparisons are assumed to be continguous. If NextBBInChain is
370  // null, the merged block will link to the phi block.
371  void mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
372  BasicBlock *const NextBBInChain, PHINode &Phi,
373  const TargetLibraryInfo *const TLI, AliasAnalysis *AA);
374 
375  PHINode &Phi_;
376  std::vector<BCECmpBlock> Comparisons_;
377  // The original entry block (before sorting);
378  BasicBlock *EntryBlock_;
379 };
380 
381 BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
382  AliasAnalysis *AA)
383  : Phi_(Phi) {
384  assert(!Blocks.empty() && "a chain should have at least one block");
385  // Now look inside blocks to check for BCE comparisons.
386  std::vector<BCECmpBlock> Comparisons;
387  for (size_t BlockIdx = 0; BlockIdx < Blocks.size(); ++BlockIdx) {
388  BasicBlock *const Block = Blocks[BlockIdx];
389  assert(Block && "invalid block");
390  BCECmpBlock Comparison = visitCmpBlock(Phi.getIncomingValueForBlock(Block),
391  Block, Phi.getParent());
392  Comparison.BB = Block;
393  if (!Comparison.IsValid()) {
394  LLVM_DEBUG(dbgs() << "chain with invalid BCECmpBlock, no merge.\n");
395  return;
396  }
397  if (Comparison.doesOtherWork()) {
398  LLVM_DEBUG(dbgs() << "block '" << Comparison.BB->getName()
399  << "' does extra work besides compare\n");
400  if (Comparisons.empty()) {
401  // This is the initial block in the chain, in case this block does other
402  // work, we can try to split the block and move the irrelevant
403  // instructions to the predecessor.
404  //
405  // If this is not the initial block in the chain, splitting it wont
406  // work.
407  //
408  // As once split, there will still be instructions before the BCE cmp
409  // instructions that do other work in program order, i.e. within the
410  // chain before sorting. Unless we can abort the chain at this point
411  // and start anew.
412  //
413  // NOTE: we only handle block with single predecessor for now.
414  if (Comparison.canSplit(AA)) {
415  LLVM_DEBUG(dbgs()
416  << "Split initial block '" << Comparison.BB->getName()
417  << "' that does extra work besides compare\n");
418  Comparison.RequireSplit = true;
419  enqueueBlock(Comparisons, Comparison);
420  } else {
421  LLVM_DEBUG(dbgs()
422  << "ignoring initial block '" << Comparison.BB->getName()
423  << "' that does extra work besides compare\n");
424  }
425  continue;
426  }
427  // TODO(courbet): Right now we abort the whole chain. We could be
428  // merging only the blocks that don't do other work and resume the
429  // chain from there. For example:
430  // if (a[0] == b[0]) { // bb1
431  // if (a[1] == b[1]) { // bb2
432  // some_value = 3; //bb3
433  // if (a[2] == b[2]) { //bb3
434  // do a ton of stuff //bb4
435  // }
436  // }
437  // }
438  //
439  // This is:
440  //
441  // bb1 --eq--> bb2 --eq--> bb3* -eq--> bb4 --+
442  // \ \ \ \
443  // ne ne ne \
444  // \ \ \ v
445  // +------------+-----------+----------> bb_phi
446  //
447  // We can only merge the first two comparisons, because bb3* does
448  // "other work" (setting some_value to 3).
449  // We could still merge bb1 and bb2 though.
450  return;
451  }
452  enqueueBlock(Comparisons, Comparison);
453  }
454 
455  // It is possible we have no suitable comparison to merge.
456  if (Comparisons.empty()) {
457  LLVM_DEBUG(dbgs() << "chain with no BCE basic blocks, no merge\n");
458  return;
459  }
460  EntryBlock_ = Comparisons[0].BB;
461  Comparisons_ = std::move(Comparisons);
462 #ifdef MERGEICMPS_DOT_ON
463  errs() << "BEFORE REORDERING:\n\n";
464  dump();
465 #endif // MERGEICMPS_DOT_ON
466  // Reorder blocks by LHS. We can do that without changing the
467  // semantics because we are only accessing dereferencable memory.
468  llvm::sort(Comparisons_, [](const BCECmpBlock &a, const BCECmpBlock &b) {
469  return a.Lhs() < b.Lhs();
470  });
471 #ifdef MERGEICMPS_DOT_ON
472  errs() << "AFTER REORDERING:\n\n";
473  dump();
474 #endif // MERGEICMPS_DOT_ON
475 }
476 
477 #ifdef MERGEICMPS_DOT_ON
478 void BCECmpChain::dump() const {
479  errs() << "digraph dag {\n";
480  errs() << " graph [bgcolor=transparent];\n";
481  errs() << " node [color=black,style=filled,fillcolor=lightyellow];\n";
482  errs() << " edge [color=black];\n";
483  for (size_t I = 0; I < Comparisons_.size(); ++I) {
484  const auto &Comparison = Comparisons_[I];
485  errs() << " \"" << I << "\" [label=\"%"
486  << Comparison.Lhs().Base()->getName() << " + "
487  << Comparison.Lhs().Offset << " == %"
488  << Comparison.Rhs().Base()->getName() << " + "
489  << Comparison.Rhs().Offset << " (" << (Comparison.SizeBits() / 8)
490  << " bytes)\"];\n";
491  const Value *const Val = Phi_.getIncomingValueForBlock(Comparison.BB);
492  if (I > 0) errs() << " \"" << (I - 1) << "\" -> \"" << I << "\";\n";
493  errs() << " \"" << I << "\" -> \"Phi\" [label=\"" << *Val << "\"];\n";
494  }
495  errs() << " \"Phi\" [label=\"Phi\"];\n";
496  errs() << "}\n\n";
497 }
498 #endif // MERGEICMPS_DOT_ON
499 
500 bool BCECmpChain::simplify(const TargetLibraryInfo *const TLI,
501  AliasAnalysis *AA) {
502  // First pass to check if there is at least one merge. If not, we don't do
503  // anything and we keep analysis passes intact.
504  {
505  bool AtLeastOneMerged = false;
506  for (size_t I = 1; I < Comparisons_.size(); ++I) {
507  if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) {
508  AtLeastOneMerged = true;
509  break;
510  }
511  }
512  if (!AtLeastOneMerged) return false;
513  }
514 
515  // Remove phi references to comparison blocks, they will be rebuilt as we
516  // merge the blocks.
517  for (const auto &Comparison : Comparisons_) {
518  Phi_.removeIncomingValue(Comparison.BB, false);
519  }
520 
521  // If entry block is part of the chain, we need to make the first block
522  // of the chain the new entry block of the function.
523  BasicBlock *Entry = &Comparisons_[0].BB->getParent()->getEntryBlock();
524  for (size_t I = 1; I < Comparisons_.size(); ++I) {
525  if (Entry == Comparisons_[I].BB) {
526  BasicBlock *NEntryBB = BasicBlock::Create(Entry->getContext(), "",
527  Entry->getParent(), Entry);
528  BranchInst::Create(Entry, NEntryBB);
529  break;
530  }
531  }
532 
533  // Point the predecessors of the chain to the first comparison block (which is
534  // the new entry point) and update the entry block of the chain.
535  if (EntryBlock_ != Comparisons_[0].BB) {
536  EntryBlock_->replaceAllUsesWith(Comparisons_[0].BB);
537  EntryBlock_ = Comparisons_[0].BB;
538  }
539 
540  // Effectively merge blocks.
541  int NumMerged = 1;
542  for (size_t I = 1; I < Comparisons_.size(); ++I) {
543  if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) {
544  ++NumMerged;
545  } else {
546  // Merge all previous comparisons and start a new merge block.
547  mergeComparisons(
548  makeArrayRef(Comparisons_).slice(I - NumMerged, NumMerged),
549  Comparisons_[I].BB, Phi_, TLI, AA);
550  NumMerged = 1;
551  }
552  }
553  mergeComparisons(makeArrayRef(Comparisons_)
554  .slice(Comparisons_.size() - NumMerged, NumMerged),
555  nullptr, Phi_, TLI, AA);
556 
557  return true;
558 }
559 
560 void BCECmpChain::mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
561  BasicBlock *const NextBBInChain,
562  PHINode &Phi,
563  const TargetLibraryInfo *const TLI,
564  AliasAnalysis *AA) {
565  assert(!Comparisons.empty());
566  const auto &FirstComparison = *Comparisons.begin();
567  BasicBlock *const BB = FirstComparison.BB;
568  LLVMContext &Context = BB->getContext();
569 
570  if (Comparisons.size() >= 2) {
571  // If there is one block that requires splitting, we do it now, i.e.
572  // just before we know we will collapse the chain. The instructions
573  // can be executed before any of the instructions in the chain.
574  auto C = std::find_if(Comparisons.begin(), Comparisons.end(),
575  [](const BCECmpBlock &B) { return B.RequireSplit; });
576  if (C != Comparisons.end())
577  C->split(EntryBlock_, AA);
578 
579  LLVM_DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons\n");
580  const auto TotalSize =
581  std::accumulate(Comparisons.begin(), Comparisons.end(), 0,
582  [](int Size, const BCECmpBlock &C) {
583  return Size + C.SizeBits();
584  }) /
585  8;
586 
587  // Incoming edges do not need to be updated, and both GEPs are already
588  // computing the right address, we just need to:
589  // - replace the two loads and the icmp with the memcmp
590  // - update the branch
591  // - update the incoming values in the phi.
592  FirstComparison.BranchI->eraseFromParent();
593  FirstComparison.CmpI->eraseFromParent();
594  FirstComparison.Lhs().LoadI->eraseFromParent();
595  FirstComparison.Rhs().LoadI->eraseFromParent();
596 
597  IRBuilder<> Builder(BB);
598  const auto &DL = Phi.getModule()->getDataLayout();
599  Value *const MemCmpCall = emitMemCmp(
600  FirstComparison.Lhs().GEP, FirstComparison.Rhs().GEP,
601  ConstantInt::get(DL.getIntPtrType(Context), TotalSize),
602  Builder, DL, TLI);
603  Value *const MemCmpIsZero = Builder.CreateICmpEQ(
604  MemCmpCall, ConstantInt::get(Type::getInt32Ty(Context), 0));
605 
606  // Add a branch to the next basic block in the chain.
607  if (NextBBInChain) {
608  Builder.CreateCondBr(MemCmpIsZero, NextBBInChain, Phi.getParent());
609  Phi.addIncoming(ConstantInt::getFalse(Context), BB);
610  } else {
611  Builder.CreateBr(Phi.getParent());
612  Phi.addIncoming(MemCmpIsZero, BB);
613  }
614 
615  // Delete merged blocks.
616  for (size_t I = 1; I < Comparisons.size(); ++I) {
617  BasicBlock *CBB = Comparisons[I].BB;
618  CBB->replaceAllUsesWith(BB);
619  CBB->eraseFromParent();
620  }
621  } else {
622  assert(Comparisons.size() == 1);
623  // There are no blocks to merge, but we still need to update the branches.
624  LLVM_DEBUG(dbgs() << "Only one comparison, updating branches\n");
625  if (NextBBInChain) {
626  if (FirstComparison.BranchI->isConditional()) {
627  LLVM_DEBUG(dbgs() << "conditional -> conditional\n");
628  // Just update the "true" target, the "false" target should already be
629  // the phi block.
630  assert(FirstComparison.BranchI->getSuccessor(1) == Phi.getParent());
631  FirstComparison.BranchI->setSuccessor(0, NextBBInChain);
632  Phi.addIncoming(ConstantInt::getFalse(Context), BB);
633  } else {
634  LLVM_DEBUG(dbgs() << "unconditional -> conditional\n");
635  // Replace the unconditional branch by a conditional one.
636  FirstComparison.BranchI->eraseFromParent();
637  IRBuilder<> Builder(BB);
638  Builder.CreateCondBr(FirstComparison.CmpI, NextBBInChain,
639  Phi.getParent());
640  Phi.addIncoming(FirstComparison.CmpI, BB);
641  }
642  } else {
643  if (FirstComparison.BranchI->isConditional()) {
644  LLVM_DEBUG(dbgs() << "conditional -> unconditional\n");
645  // Replace the conditional branch by an unconditional one.
646  FirstComparison.BranchI->eraseFromParent();
647  IRBuilder<> Builder(BB);
648  Builder.CreateBr(Phi.getParent());
649  Phi.addIncoming(FirstComparison.CmpI, BB);
650  } else {
651  LLVM_DEBUG(dbgs() << "unconditional -> unconditional\n");
652  Phi.addIncoming(FirstComparison.CmpI, BB);
653  }
654  }
655  }
656 }
657 
658 std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
659  BasicBlock *const LastBlock,
660  int NumBlocks) {
661  // Walk up from the last block to find other blocks.
662  std::vector<BasicBlock *> Blocks(NumBlocks);
663  assert(LastBlock && "invalid last block");
664  BasicBlock *CurBlock = LastBlock;
665  for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) {
666  if (CurBlock->hasAddressTaken()) {
667  // Somebody is jumping to the block through an address, all bets are
668  // off.
669  LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
670  << " has its address taken\n");
671  return {};
672  }
673  Blocks[BlockIndex] = CurBlock;
674  auto *SinglePredecessor = CurBlock->getSinglePredecessor();
675  if (!SinglePredecessor) {
676  // The block has two or more predecessors.
677  LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
678  << " has two or more predecessors\n");
679  return {};
680  }
681  if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) {
682  // The block does not link back to the phi.
683  LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
684  << " does not link back to the phi\n");
685  return {};
686  }
687  CurBlock = SinglePredecessor;
688  }
689  Blocks[0] = CurBlock;
690  return Blocks;
691 }
692 
693 bool processPhi(PHINode &Phi, const TargetLibraryInfo *const TLI,
694  AliasAnalysis *AA) {
695  LLVM_DEBUG(dbgs() << "processPhi()\n");
696  if (Phi.getNumIncomingValues() <= 1) {
697  LLVM_DEBUG(dbgs() << "skip: only one incoming value in phi\n");
698  return false;
699  }
700  // We are looking for something that has the following structure:
701  // bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+
702  // \ \ \ \
703  // ne ne ne \
704  // \ \ \ v
705  // +------------+-----------+----------> bb_phi
706  //
707  // - The last basic block (bb4 here) must branch unconditionally to bb_phi.
708  // It's the only block that contributes a non-constant value to the Phi.
709  // - All other blocks (b1, b2, b3) must have exactly two successors, one of
710  // them being the phi block.
711  // - All intermediate blocks (bb2, bb3) must have only one predecessor.
712  // - Blocks cannot do other work besides the comparison, see doesOtherWork()
713 
714  // The blocks are not necessarily ordered in the phi, so we start from the
715  // last block and reconstruct the order.
716  BasicBlock *LastBlock = nullptr;
717  for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) {
718  if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue;
719  if (LastBlock) {
720  // There are several non-constant values.
721  LLVM_DEBUG(dbgs() << "skip: several non-constant values\n");
722  return false;
723  }
724  if (!isa<ICmpInst>(Phi.getIncomingValue(I)) ||
725  cast<ICmpInst>(Phi.getIncomingValue(I))->getParent() !=
726  Phi.getIncomingBlock(I)) {
727  // Non-constant incoming value is not from a cmp instruction or not
728  // produced by the last block. We could end up processing the value
729  // producing block more than once.
730  //
731  // This is an uncommon case, so we bail.
732  LLVM_DEBUG(
733  dbgs()
734  << "skip: non-constant value not from cmp or not from last block.\n");
735  return false;
736  }
737  LastBlock = Phi.getIncomingBlock(I);
738  }
739  if (!LastBlock) {
740  // There is no non-constant block.
741  LLVM_DEBUG(dbgs() << "skip: no non-constant block\n");
742  return false;
743  }
744  if (LastBlock->getSingleSuccessor() != Phi.getParent()) {
745  LLVM_DEBUG(dbgs() << "skip: last block non-phi successor\n");
746  return false;
747  }
748 
749  const auto Blocks =
750  getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues());
751  if (Blocks.empty()) return false;
752  BCECmpChain CmpChain(Blocks, Phi, AA);
753 
754  if (CmpChain.size() < 2) {
755  LLVM_DEBUG(dbgs() << "skip: only one compare block\n");
756  return false;
757  }
758 
759  return CmpChain.simplify(TLI, AA);
760 }
761 
762 class MergeICmps : public FunctionPass {
763  public:
764  static char ID;
765 
766  MergeICmps() : FunctionPass(ID) {
768  }
769 
770  bool runOnFunction(Function &F) override {
771  if (skipFunction(F)) return false;
772  const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
773  const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
774  AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
775  auto PA = runImpl(F, &TLI, &TTI, AA);
776  return !PA.areAllPreserved();
777  }
778 
779  private:
780  void getAnalysisUsage(AnalysisUsage &AU) const override {
784  }
785 
787  const TargetTransformInfo *TTI, AliasAnalysis *AA);
788 };
789 
791  const TargetTransformInfo *TTI,
792  AliasAnalysis *AA) {
793  LLVM_DEBUG(dbgs() << "MergeICmpsPass: " << F.getName() << "\n");
794 
795  // We only try merging comparisons if the target wants to expand memcmp later.
796  // The rationale is to avoid turning small chains into memcmp calls.
797  if (!TTI->enableMemCmpExpansion(true)) return PreservedAnalyses::all();
798 
799  // If we don't have memcmp avaiable we can't emit calls to it.
800  if (!TLI->has(LibFunc_memcmp))
801  return PreservedAnalyses::all();
802 
803  bool MadeChange = false;
804 
805  for (auto BBIt = ++F.begin(); BBIt != F.end(); ++BBIt) {
806  // A Phi operation is always first in a basic block.
807  if (auto *const Phi = dyn_cast<PHINode>(&*BBIt->begin()))
808  MadeChange |= processPhi(*Phi, TLI, AA);
809  }
810 
811  if (MadeChange) return PreservedAnalyses::none();
812  return PreservedAnalyses::all();
813 }
814 
815 } // namespace
816 
817 char MergeICmps::ID = 0;
818 INITIALIZE_PASS_BEGIN(MergeICmps, "mergeicmps",
819  "Merge contiguous icmps into a memcmp", false, false)
824  "Merge contiguous icmps into a memcmp", false, false)
825 
826 Pass *llvm::createMergeICmpsPass() { return new MergeICmps(); }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
uint64_t CallInst * C
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:584
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional &#39;br Cond, TrueDest, FalseDest&#39; instruction.
Definition: IRBuilder.h:854
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
LLVMContext & Context
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
iterator begin() const
Definition: ArrayRef.h:137
iterator end()
Definition: Function.h:658
Implements a dense probed hash-table based set.
Definition: DenseSet.h:250
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:299
static std::pair< StringRef, StringRef > split(StringRef Str, char Separator)
Checked version of split, to ensure mandatory subparts.
Definition: DataLayout.cpp:202
F(f)
An instruction for reading from memory.
Definition: Instructions.h:168
Hexagon Common GEP
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:263
mergeicmps
Definition: MergeICmps.cpp:823
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:364
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:743
Pass * createMergeICmpsPass()
Definition: MergeICmps.cpp:826
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:251
bool empty() const
Definition: BasicBlock.h:274
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool has(LibFunc F) const
Tests whether a library function is available.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:263
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
An instruction for storing to memory.
Definition: Instructions.h:310
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
iterator begin()
Definition: Function.h:656
Value * getOperand(unsigned i) const
Definition: User.h:170
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:157
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:843
static bool runOnFunction(Function &F, bool PostInlining)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:236
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
Conditional or Unconditional Branch instruction.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
Value * getIncomingValueForBlock(const BasicBlock *BB) const
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:558
Represent the analysis usage information of a pass.
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:685
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
op_range operands()
Definition: User.h:238
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1748
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1070
R600 Clause Merge
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:972
Representation for a specific memory location.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:386
hexagon bit simplify
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1023
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:130
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Provides information about what library functions are available for the current target.
iterator end() const
Definition: ArrayRef.h:138
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
Class for arbitrary precision integers.
Definition: APInt.h:70
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
bool isDereferenceablePointer(const Value *V, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if this is always a dereferenceable pointer.
Definition: Loads.cpp:153
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:759
Merge contiguous icmps into a memcmp
Definition: MergeICmps.cpp:823
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:115
#define I(x, y, z)
Definition: MD5.cpp:58
const MemCmpExpansionOptions * enableMemCmpExpansion(bool IsZeroCmp) const
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
uint32_t Size
Definition: Profile.cpp:47
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:92
Value * emitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B, const DataLayout &DL, const TargetLibraryInfo *TLI)
Emit a call to the memcmp function.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
LLVM Value Representation.
Definition: Value.h:73
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional &#39;br label X&#39; instruction.
Definition: IRBuilder.h:848
static const Function * getParent(const Value *V)
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:87
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:413
INITIALIZE_PASS_BEGIN(MergeICmps, "mergeicmps", "Merge contiguous icmps into a memcmp", false, false) INITIALIZE_PASS_END(MergeICmps
This pass exposes codegen information to IR-level passes.
void initializeMergeICmpsPass(PassRegistry &)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
#define LLVM_DEBUG(X)
Definition: Debug.h:123
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144
const BasicBlock * getParent() const
Definition: Instruction.h:67
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1101