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