LLVM  13.0.0git
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/InitializePasses.h"
54 #include "llvm/Pass.h"
55 #include "llvm/Transforms/Scalar.h"
58 #include <algorithm>
59 #include <numeric>
60 #include <utility>
61 #include <vector>
62 
63 using namespace llvm;
64 
65 namespace {
66 
67 #define DEBUG_TYPE "mergeicmps"
68 
69 // Returns true if the instruction is a simple load or a simple store
70 static bool isSimpleLoadOrStore(const Instruction *I) {
71  if (const LoadInst *LI = dyn_cast<LoadInst>(I))
72  return LI->isSimple();
73  if (const StoreInst *SI = dyn_cast<StoreInst>(I))
74  return SI->isSimple();
75  return false;
76 }
77 
78 // A BCE atom "Binary Compare Expression Atom" represents an integer load
79 // that is a constant offset from a base value, e.g. `a` or `o.c` in the example
80 // at the top.
81 struct BCEAtom {
82  BCEAtom() = default;
83  BCEAtom(GetElementPtrInst *GEP, LoadInst *LoadI, int BaseId, APInt Offset)
84  : GEP(GEP), LoadI(LoadI), BaseId(BaseId), Offset(Offset) {}
85 
86  BCEAtom(const BCEAtom &) = delete;
87  BCEAtom &operator=(const BCEAtom &) = delete;
88 
89  BCEAtom(BCEAtom &&that) = default;
90  BCEAtom &operator=(BCEAtom &&that) {
91  if (this == &that)
92  return *this;
93  GEP = that.GEP;
94  LoadI = that.LoadI;
95  BaseId = that.BaseId;
96  Offset = std::move(that.Offset);
97  return *this;
98  }
99 
100  // We want to order BCEAtoms by (Base, Offset). However we cannot use
101  // the pointer values for Base because these are non-deterministic.
102  // To make sure that the sort order is stable, we first assign to each atom
103  // base value an index based on its order of appearance in the chain of
104  // comparisons. We call this index `BaseOrdering`. For example, for:
105  // b[3] == c[2] && a[1] == d[1] && b[4] == c[3]
106  // | block 1 | | block 2 | | block 3 |
107  // b gets assigned index 0 and a index 1, because b appears as LHS in block 1,
108  // which is before block 2.
109  // We then sort by (BaseOrdering[LHS.Base()], LHS.Offset), which is stable.
110  bool operator<(const BCEAtom &O) const {
111  return BaseId != O.BaseId ? BaseId < O.BaseId : Offset.slt(O.Offset);
112  }
113 
114  GetElementPtrInst *GEP = nullptr;
115  LoadInst *LoadI = nullptr;
116  unsigned BaseId = 0;
117  APInt Offset;
118 };
119 
120 // A class that assigns increasing ids to values in the order in which they are
121 // seen. See comment in `BCEAtom::operator<()``.
122 class BaseIdentifier {
123 public:
124  // Returns the id for value `Base`, after assigning one if `Base` has not been
125  // seen before.
126  int getBaseId(const Value *Base) {
127  assert(Base && "invalid base");
128  const auto Insertion = BaseToIndex.try_emplace(Base, Order);
129  if (Insertion.second)
130  ++Order;
131  return Insertion.first->second;
132  }
133 
134 private:
135  unsigned Order = 1;
136  DenseMap<const Value*, int> BaseToIndex;
137 };
138 
139 // If this value is a load from a constant offset w.r.t. a base address, and
140 // there are no other users of the load or address, returns the base address and
141 // the offset.
142 BCEAtom visitICmpLoadOperand(Value *const Val, BaseIdentifier &BaseId) {
143  auto *const LoadI = dyn_cast<LoadInst>(Val);
144  if (!LoadI)
145  return {};
146  LLVM_DEBUG(dbgs() << "load\n");
147  if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {
148  LLVM_DEBUG(dbgs() << "used outside of block\n");
149  return {};
150  }
151  // Do not optimize atomic loads to non-atomic memcmp
152  if (!LoadI->isSimple()) {
153  LLVM_DEBUG(dbgs() << "volatile or atomic\n");
154  return {};
155  }
156  Value *const Addr = LoadI->getOperand(0);
157  auto *const GEP = dyn_cast<GetElementPtrInst>(Addr);
158  if (!GEP)
159  return {};
160  LLVM_DEBUG(dbgs() << "GEP\n");
161  if (GEP->isUsedOutsideOfBlock(LoadI->getParent())) {
162  LLVM_DEBUG(dbgs() << "used outside of block\n");
163  return {};
164  }
165  const auto &DL = GEP->getModule()->getDataLayout();
166  if (!isDereferenceablePointer(GEP, LoadI->getType(), DL)) {
167  LLVM_DEBUG(dbgs() << "not dereferenceable\n");
168  // We need to make sure that we can do comparison in any order, so we
169  // require memory to be unconditionnally dereferencable.
170  return {};
171  }
172  APInt Offset = APInt(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
173  if (!GEP->accumulateConstantOffset(DL, Offset))
174  return {};
175  return BCEAtom(GEP, LoadI, BaseId.getBaseId(GEP->getPointerOperand()),
176  Offset);
177 }
178 
179 // A basic block with a comparison between two BCE atoms, e.g. `a == o.a` in the
180 // example at the top.
181 // The block might do extra work besides the atom comparison, in which case
182 // doesOtherWork() returns true. Under some conditions, the block can be
183 // split into the atom comparison part and the "other work" part
184 // (see canSplit()).
185 // Note: the terminology is misleading: the comparison is symmetric, so there
186 // is no real {l/r}hs. What we want though is to have the same base on the
187 // left (resp. right), so that we can detect consecutive loads. To ensure this
188 // we put the smallest atom on the left.
189 class BCECmpBlock {
190  public:
191  BCECmpBlock() {}
192 
193  BCECmpBlock(BCEAtom L, BCEAtom R, int SizeBits)
194  : Lhs_(std::move(L)), Rhs_(std::move(R)), SizeBits_(SizeBits) {
195  if (Rhs_ < Lhs_) std::swap(Rhs_, Lhs_);
196  }
197 
198  bool IsValid() const { return Lhs_.BaseId != 0 && Rhs_.BaseId != 0; }
199 
200  // Assert the block is consistent: If valid, it should also have
201  // non-null members besides Lhs_ and Rhs_.
202  void AssertConsistent() const {
203  if (IsValid()) {
204  assert(BB);
205  assert(CmpI);
206  assert(BranchI);
207  }
208  }
209 
210  const BCEAtom &Lhs() const { return Lhs_; }
211  const BCEAtom &Rhs() const { return Rhs_; }
212  int SizeBits() const { return SizeBits_; }
213 
214  // Returns true if the block does other works besides comparison.
215  bool doesOtherWork() const;
216 
217  // Returns true if the non-BCE-cmp instructions can be separated from BCE-cmp
218  // instructions in the block.
219  bool canSplit(AliasAnalysis &AA) const;
220 
221  // Return true if this all the relevant instructions in the BCE-cmp-block can
222  // be sunk below this instruction. By doing this, we know we can separate the
223  // BCE-cmp-block instructions from the non-BCE-cmp-block instructions in the
224  // block.
225  bool canSinkBCECmpInst(const Instruction *, DenseSet<Instruction *> &,
226  AliasAnalysis &AA) const;
227 
228  // We can separate the BCE-cmp-block instructions and the non-BCE-cmp-block
229  // instructions. Split the old block and move all non-BCE-cmp-insts into the
230  // new parent block.
231  void split(BasicBlock *NewParent, AliasAnalysis &AA) const;
232 
233  // The basic block where this comparison happens.
234  BasicBlock *BB = nullptr;
235  // The ICMP for this comparison.
236  ICmpInst *CmpI = nullptr;
237  // The terminating branch.
238  BranchInst *BranchI = nullptr;
239  // The block requires splitting.
240  bool RequireSplit = false;
241 
242 private:
243  BCEAtom Lhs_;
244  BCEAtom Rhs_;
245  int SizeBits_ = 0;
246 };
247 
248 bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst,
249  DenseSet<Instruction *> &BlockInsts,
250  AliasAnalysis &AA) const {
251  // If this instruction has side effects and its in middle of the BCE cmp block
252  // instructions, then bail for now.
253  if (Inst->mayHaveSideEffects()) {
254  // Bail if this is not a simple load or store
255  if (!isSimpleLoadOrStore(Inst))
256  return false;
257  // Disallow stores that might alias the BCE operands
258  MemoryLocation LLoc = MemoryLocation::get(Lhs_.LoadI);
259  MemoryLocation RLoc = MemoryLocation::get(Rhs_.LoadI);
260  if (isModSet(AA.getModRefInfo(Inst, LLoc)) ||
261  isModSet(AA.getModRefInfo(Inst, RLoc)))
262  return false;
263  }
264  // Make sure this instruction does not use any of the BCE cmp block
265  // instructions as operand.
266  for (auto BI : BlockInsts) {
267  if (is_contained(Inst->operands(), BI))
268  return false;
269  }
270  return true;
271 }
272 
273 void BCECmpBlock::split(BasicBlock *NewParent, AliasAnalysis &AA) const {
274  DenseSet<Instruction *> BlockInsts(
275  {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
277  for (Instruction &Inst : *BB) {
278  if (BlockInsts.count(&Inst))
279  continue;
280  assert(canSinkBCECmpInst(&Inst, BlockInsts, AA) &&
281  "Split unsplittable block");
282  // This is a non-BCE-cmp-block instruction. And it can be separated
283  // from the BCE-cmp-block instruction.
284  OtherInsts.push_back(&Inst);
285  }
286 
287  // Do the actual spliting.
288  for (Instruction *Inst : reverse(OtherInsts)) {
289  Inst->moveBefore(&*NewParent->begin());
290  }
291 }
292 
293 bool BCECmpBlock::canSplit(AliasAnalysis &AA) const {
294  DenseSet<Instruction *> BlockInsts(
295  {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
296  for (Instruction &Inst : *BB) {
297  if (!BlockInsts.count(&Inst)) {
298  if (!canSinkBCECmpInst(&Inst, BlockInsts, AA))
299  return false;
300  }
301  }
302  return true;
303 }
304 
305 bool BCECmpBlock::doesOtherWork() const {
306  AssertConsistent();
307  // All the instructions we care about in the BCE cmp block.
308  DenseSet<Instruction *> BlockInsts(
309  {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
310  // TODO(courbet): Can we allow some other things ? This is very conservative.
311  // We might be able to get away with anything does not have any side
312  // effects outside of the basic block.
313  // Note: The GEPs and/or loads are not necessarily in the same block.
314  for (const Instruction &Inst : *BB) {
315  if (!BlockInsts.count(&Inst))
316  return true;
317  }
318  return false;
319 }
320 
321 // Visit the given comparison. If this is a comparison between two valid
322 // BCE atoms, returns the comparison.
323 BCECmpBlock visitICmp(const ICmpInst *const CmpI,
324  const ICmpInst::Predicate ExpectedPredicate,
325  BaseIdentifier &BaseId) {
326  // The comparison can only be used once:
327  // - For intermediate blocks, as a branch condition.
328  // - For the final block, as an incoming value for the Phi.
329  // If there are any other uses of the comparison, we cannot merge it with
330  // other comparisons as we would create an orphan use of the value.
331  if (!CmpI->hasOneUse()) {
332  LLVM_DEBUG(dbgs() << "cmp has several uses\n");
333  return {};
334  }
335  if (CmpI->getPredicate() != ExpectedPredicate)
336  return {};
337  LLVM_DEBUG(dbgs() << "cmp "
338  << (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne")
339  << "\n");
340  auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0), BaseId);
341  if (!Lhs.BaseId)
342  return {};
343  auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1), BaseId);
344  if (!Rhs.BaseId)
345  return {};
346  const auto &DL = CmpI->getModule()->getDataLayout();
347  return BCECmpBlock(std::move(Lhs), std::move(Rhs),
348  DL.getTypeSizeInBits(CmpI->getOperand(0)->getType()));
349 }
350 
351 // Visit the given comparison block. If this is a comparison between two valid
352 // BCE atoms, returns the comparison.
353 BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block,
354  const BasicBlock *const PhiBlock,
355  BaseIdentifier &BaseId) {
356  if (Block->empty()) return {};
357  auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator());
358  if (!BranchI) return {};
359  LLVM_DEBUG(dbgs() << "branch\n");
360  if (BranchI->isUnconditional()) {
361  // In this case, we expect an incoming value which is the result of the
362  // comparison. This is the last link in the chain of comparisons (note
363  // that this does not mean that this is the last incoming value, blocks
364  // can be reordered).
365  auto *const CmpI = dyn_cast<ICmpInst>(Val);
366  if (!CmpI) return {};
367  LLVM_DEBUG(dbgs() << "icmp\n");
368  auto Result = visitICmp(CmpI, ICmpInst::ICMP_EQ, BaseId);
369  Result.CmpI = CmpI;
370  Result.BranchI = BranchI;
371  return Result;
372  } else {
373  // In this case, we expect a constant incoming value (the comparison is
374  // chained).
375  const auto *const Const = cast<ConstantInt>(Val);
376  LLVM_DEBUG(dbgs() << "const\n");
377  if (!Const->isZero()) return {};
378  LLVM_DEBUG(dbgs() << "false\n");
379  auto *const CmpI = dyn_cast<ICmpInst>(BranchI->getCondition());
380  if (!CmpI) return {};
381  LLVM_DEBUG(dbgs() << "icmp\n");
382  assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch");
383  BasicBlock *const FalseBlock = BranchI->getSuccessor(1);
384  auto Result = visitICmp(
385  CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
386  BaseId);
387  Result.CmpI = CmpI;
388  Result.BranchI = BranchI;
389  return Result;
390  }
391  return {};
392 }
393 
394 static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons,
395  BCECmpBlock &&Comparison) {
396  LLVM_DEBUG(dbgs() << "Block '" << Comparison.BB->getName()
397  << "': Found cmp of " << Comparison.SizeBits()
398  << " bits between " << Comparison.Lhs().BaseId << " + "
399  << Comparison.Lhs().Offset << " and "
400  << Comparison.Rhs().BaseId << " + "
401  << Comparison.Rhs().Offset << "\n");
402  LLVM_DEBUG(dbgs() << "\n");
403  Comparisons.push_back(std::move(Comparison));
404 }
405 
406 // A chain of comparisons.
407 class BCECmpChain {
408  public:
409  BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
410  AliasAnalysis &AA);
411 
412  int size() const { return Comparisons_.size(); }
413 
414 #ifdef MERGEICMPS_DOT_ON
415  void dump() const;
416 #endif // MERGEICMPS_DOT_ON
417 
418  bool simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA,
419  DomTreeUpdater &DTU);
420 
421 private:
422  static bool IsContiguous(const BCECmpBlock &First,
423  const BCECmpBlock &Second) {
424  return First.Lhs().BaseId == Second.Lhs().BaseId &&
425  First.Rhs().BaseId == Second.Rhs().BaseId &&
426  First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset &&
427  First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset;
428  }
429 
430  PHINode &Phi_;
431  std::vector<BCECmpBlock> Comparisons_;
432  // The original entry block (before sorting);
433  BasicBlock *EntryBlock_;
434 };
435 
436 BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
437  AliasAnalysis &AA)
438  : Phi_(Phi) {
439  assert(!Blocks.empty() && "a chain should have at least one block");
440  // Now look inside blocks to check for BCE comparisons.
441  std::vector<BCECmpBlock> Comparisons;
442  BaseIdentifier BaseId;
443  for (BasicBlock *const Block : Blocks) {
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);
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 
627  // If there is one block that requires splitting, we do it now, i.e.
628  // just before we know we will collapse the chain. The instructions
629  // can be executed before any of the instructions in the chain.
630  const auto ToSplit = llvm::find_if(
631  Comparisons, [](const BCECmpBlock &B) { return B.RequireSplit; });
632  if (ToSplit != Comparisons.end()) {
633  LLVM_DEBUG(dbgs() << "Splitting non_BCE work to header\n");
634  ToSplit->split(BB, AA);
635  }
636 
637  if (Comparisons.size() == 1) {
638  LLVM_DEBUG(dbgs() << "Only one comparison, updating branches\n");
639  Value *const LhsLoad =
640  Builder.CreateLoad(FirstCmp.Lhs().LoadI->getType(), Lhs);
641  Value *const RhsLoad =
642  Builder.CreateLoad(FirstCmp.Rhs().LoadI->getType(), Rhs);
643  // There are no blocks to merge, just do the comparison.
644  IsEqual = Builder.CreateICmpEQ(LhsLoad, RhsLoad);
645  } else {
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);
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 = EntryBlock_->isEntryBlock();
736  if (ChainEntryIsFnEntry && DTU.hasDomTree()) {
737  LLVM_DEBUG(dbgs() << "Changing function entry from "
738  << EntryBlock_->getName() << " to "
739  << NextCmpBlock->getName() << "\n");
740  DTU.getDomTree().setNewRoot(NextCmpBlock);
741  DTU.applyUpdates({{DominatorTree::Delete, NextCmpBlock, EntryBlock_}});
742  }
743  EntryBlock_ = nullptr;
744 
745  // Delete merged blocks. This also removes incoming values in phi.
747  for (auto &Cmp : Comparisons_) {
748  LLVM_DEBUG(dbgs() << "Deleting merged block " << Cmp.BB->getName() << "\n");
749  DeadBlocks.push_back(Cmp.BB);
750  }
751  DeleteDeadBlocks(DeadBlocks, &DTU);
752 
753  Comparisons_.clear();
754  return true;
755 }
756 
757 std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
758  BasicBlock *const LastBlock,
759  int NumBlocks) {
760  // Walk up from the last block to find other blocks.
761  std::vector<BasicBlock *> Blocks(NumBlocks);
762  assert(LastBlock && "invalid last block");
763  BasicBlock *CurBlock = LastBlock;
764  for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) {
765  if (CurBlock->hasAddressTaken()) {
766  // Somebody is jumping to the block through an address, all bets are
767  // off.
768  LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
769  << " has its address taken\n");
770  return {};
771  }
772  Blocks[BlockIndex] = CurBlock;
773  auto *SinglePredecessor = CurBlock->getSinglePredecessor();
774  if (!SinglePredecessor) {
775  // The block has two or more predecessors.
776  LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
777  << " has two or more predecessors\n");
778  return {};
779  }
780  if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) {
781  // The block does not link back to the phi.
782  LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
783  << " does not link back to the phi\n");
784  return {};
785  }
786  CurBlock = SinglePredecessor;
787  }
788  Blocks[0] = CurBlock;
789  return Blocks;
790 }
791 
792 bool processPhi(PHINode &Phi, const TargetLibraryInfo &TLI, AliasAnalysis &AA,
793  DomTreeUpdater &DTU) {
794  LLVM_DEBUG(dbgs() << "processPhi()\n");
795  if (Phi.getNumIncomingValues() <= 1) {
796  LLVM_DEBUG(dbgs() << "skip: only one incoming value in phi\n");
797  return false;
798  }
799  // We are looking for something that has the following structure:
800  // bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+
801  // \ \ \ \
802  // ne ne ne \
803  // \ \ \ v
804  // +------------+-----------+----------> bb_phi
805  //
806  // - The last basic block (bb4 here) must branch unconditionally to bb_phi.
807  // It's the only block that contributes a non-constant value to the Phi.
808  // - All other blocks (b1, b2, b3) must have exactly two successors, one of
809  // them being the phi block.
810  // - All intermediate blocks (bb2, bb3) must have only one predecessor.
811  // - Blocks cannot do other work besides the comparison, see doesOtherWork()
812 
813  // The blocks are not necessarily ordered in the phi, so we start from the
814  // last block and reconstruct the order.
815  BasicBlock *LastBlock = nullptr;
816  for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) {
817  if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue;
818  if (LastBlock) {
819  // There are several non-constant values.
820  LLVM_DEBUG(dbgs() << "skip: several non-constant values\n");
821  return false;
822  }
823  if (!isa<ICmpInst>(Phi.getIncomingValue(I)) ||
824  cast<ICmpInst>(Phi.getIncomingValue(I))->getParent() !=
825  Phi.getIncomingBlock(I)) {
826  // Non-constant incoming value is not from a cmp instruction or not
827  // produced by the last block. We could end up processing the value
828  // producing block more than once.
829  //
830  // This is an uncommon case, so we bail.
831  LLVM_DEBUG(
832  dbgs()
833  << "skip: non-constant value not from cmp or not from last block.\n");
834  return false;
835  }
836  LastBlock = Phi.getIncomingBlock(I);
837  }
838  if (!LastBlock) {
839  // There is no non-constant block.
840  LLVM_DEBUG(dbgs() << "skip: no non-constant block\n");
841  return false;
842  }
843  if (LastBlock->getSingleSuccessor() != Phi.getParent()) {
844  LLVM_DEBUG(dbgs() << "skip: last block non-phi successor\n");
845  return false;
846  }
847 
848  const auto Blocks =
849  getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues());
850  if (Blocks.empty()) return false;
851  BCECmpChain CmpChain(Blocks, Phi, AA);
852 
853  if (CmpChain.size() < 2) {
854  LLVM_DEBUG(dbgs() << "skip: only one compare block\n");
855  return false;
856  }
857 
858  return CmpChain.simplify(TLI, AA, DTU);
859 }
860 
861 static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
863  DominatorTree *DT) {
864  LLVM_DEBUG(dbgs() << "MergeICmpsLegacyPass: " << F.getName() << "\n");
865 
866  // We only try merging comparisons if the target wants to expand memcmp later.
867  // The rationale is to avoid turning small chains into memcmp calls.
868  if (!TTI.enableMemCmpExpansion(F.hasOptSize(), true))
869  return false;
870 
871  // If we don't have memcmp avaiable we can't emit calls to it.
872  if (!TLI.has(LibFunc_memcmp))
873  return false;
874 
875  DomTreeUpdater DTU(DT, /*PostDominatorTree*/ nullptr,
876  DomTreeUpdater::UpdateStrategy::Eager);
877 
878  bool MadeChange = false;
879 
880  for (auto BBIt = ++F.begin(); BBIt != F.end(); ++BBIt) {
881  // A Phi operation is always first in a basic block.
882  if (auto *const Phi = dyn_cast<PHINode>(&*BBIt->begin()))
883  MadeChange |= processPhi(*Phi, TLI, AA, DTU);
884  }
885 
886  return MadeChange;
887 }
888 
889 class MergeICmpsLegacyPass : public FunctionPass {
890 public:
891  static char ID;
892 
893  MergeICmpsLegacyPass() : FunctionPass(ID) {
894  initializeMergeICmpsLegacyPassPass(*PassRegistry::getPassRegistry());
895  }
896 
897  bool runOnFunction(Function &F) override {
898  if (skipFunction(F)) return false;
899  const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
900  const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
901  // MergeICmps does not need the DominatorTree, but we update it if it's
902  // already available.
903  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
904  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
905  return runImpl(F, TLI, TTI, AA, DTWP ? &DTWP->getDomTree() : nullptr);
906  }
907 
908  private:
909  void getAnalysisUsage(AnalysisUsage &AU) const override {
915  }
916 };
917 
918 } // namespace
919 
920 char MergeICmpsLegacyPass::ID = 0;
921 INITIALIZE_PASS_BEGIN(MergeICmpsLegacyPass, "mergeicmps",
922  "Merge contiguous icmps into a memcmp", false, false)
926 INITIALIZE_PASS_END(MergeICmpsLegacyPass, "mergeicmps",
927  "Merge contiguous icmps into a memcmp", false, false)
928 
929 Pass *llvm::createMergeICmpsLegacyPass() { return new MergeICmpsLegacyPass(); }
930 
931 PreservedAnalyses MergeICmpsPass::run(Function &F,
933  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
934  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
935  auto &AA = AM.getResult<AAManager>(F);
936  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
937  const bool MadeChanges = runImpl(F, TLI, TTI, AA, DT);
938  if (!MadeChanges)
939  return PreservedAnalyses::all();
942  return PA;
943 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1233
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2320
Merge
R600 Clause Merge
Definition: R600ClauseMergePass.cpp:69
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:37
llvm
Definition: AllocatorList.h:23
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:66
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:743
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:435
Insert
Vector Rotate Left Mask Mask Insert
Definition: README_P9.txt:112
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
simplify
hexagon bit simplify
Definition: HexagonBitSimplify.cpp:261
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
Scalar.h
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:230
Loads.h
llvm::Function
Definition: Function.h:61
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::emitMemCmp
Value * emitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilderBase &B, const DataLayout &DL, const TargetLibraryInfo *TLI)
Emit a call to the memcmp function.
Definition: BuildLibCalls.cpp:1339
llvm::FunctionPass::skipFunction
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:163
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
llvm::IRBuilder<>
DomTreeUpdater.h
llvm::DominatorTreeBase::setNewRoot
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
Definition: GenericDomTree.h:632
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:744
llvm::DeleteDeadBlocks
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
Definition: BasicBlockUtils.cpp:94
memcmp
Merge contiguous icmps into a memcmp
Definition: MergeICmps.cpp:927
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
GlobalsModRef.h
llvm::FunctionPass::runOnFunction
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:329
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:294
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:892
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:180
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::sys::path::append
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
Definition: Path.cpp:454
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2696
llvm::AAResults
Definition: AliasAnalysis.h:456
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
runImpl
static bool runImpl(const TargetLibraryInfo &TLI, Function &F)
Definition: ReplaceWithVeclib.cpp:177
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
TargetLibraryInfo.h
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2785
llvm::Instruction
Definition: Instruction.h:45
llvm::isDereferenceablePointer
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
Definition: Loads.cpp:234
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
that
Reference model for inliner Oz decision policy Note that
Definition: README.txt:2
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2692
llvm::DomTreeUpdater::hasDomTree
bool hasDomTree() const
Returns true if it holds a DominatorTree.
Definition: DomTreeUpdater.h:57
llvm::SmallString< 16 >
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
into
Clang compiles this into
Definition: README.txt:504
llvm::SmallString::append
void append(StringRef RHS)
Append from a StringRef.
Definition: SmallString.h:67
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::BasicBlock::hasAddressTaken
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:448
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:179
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:303
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1206
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:463
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2376
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:80
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2750
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:303
llvm::DenseMap
Definition: DenseMap.h:714
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:931
llvm::PHINode::getBasicBlockIndex
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: Instructions.h:2778
size
i< reg-> size
Definition: README.txt:166
llvm::is_contained
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:1547
llvm::Instruction::mayHaveSideEffects
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:634
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1540
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
getFalse
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
Definition: InstructionSimplify.cpp:119
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::User::replaceUsesOfWith
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
llvm::TargetLibraryInfo::has
bool has(LibFunc F) const
Tests whether a library function is available.
Definition: TargetLibraryInfo.h:323
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1463
llvm::TargetTransformInfo::enableMemCmpExpansion
MemCmpExpansionOptions enableMemCmpExpansion(bool OptSize, bool IsZeroCmp) const
Definition: TargetTransformInfo.cpp:495
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:119
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:294
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::BasicBlock::getTerminator
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:148
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1509
MergeICmps.h
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
split
coro split
Definition: CoroSplit.cpp:2267
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
std
Definition: BitVector.h:838
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:153
llvm::X86::FirstMacroFusionInstKind::Cmp
@ Cmp
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:788
Function.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1423
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:584
llvm::codeview::ModifierOptions::Const
@ Const
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(MergeICmpsLegacyPass, "mergeicmps", "Merge contiguous icmps into a memcmp", false, false) INITIALIZE_PASS_END(MergeICmpsLegacyPass
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
llvm::initializeMergeICmpsLegacyPassPass
void initializeMergeICmpsLegacyPassPass(PassRegistry &)
llvm::pred_begin
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:109
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
mergeicmps
mergeicmps
Definition: MergeICmps.cpp:926
Dominators.h
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1281
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:799
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2716
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2600
llvm::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:397
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3035
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:623
BasicBlockUtils.h
llvm::pdb::PDB_SymType::Block
@ Block
InitializePasses.h
BuildLibCalls.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:438
llvm::AAResults::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
Definition: AliasAnalysis.cpp:219
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:154
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::Instruction::moveBefore
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:97
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::createMergeICmpsLegacyPass
Pass * createMergeICmpsLegacyPass()
Definition: MergeICmps.cpp:929