LLVM  14.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 // A BCE atom "Binary Compare Expression Atom" represents an integer load
70 // that is a constant offset from a base value, e.g. `a` or `o.c` in the example
71 // at the top.
72 struct BCEAtom {
73  BCEAtom() = default;
74  BCEAtom(GetElementPtrInst *GEP, LoadInst *LoadI, int BaseId, APInt Offset)
75  : GEP(GEP), LoadI(LoadI), BaseId(BaseId), Offset(Offset) {}
76 
77  BCEAtom(const BCEAtom &) = delete;
78  BCEAtom &operator=(const BCEAtom &) = delete;
79 
80  BCEAtom(BCEAtom &&that) = default;
81  BCEAtom &operator=(BCEAtom &&that) {
82  if (this == &that)
83  return *this;
84  GEP = that.GEP;
85  LoadI = that.LoadI;
86  BaseId = that.BaseId;
87  Offset = std::move(that.Offset);
88  return *this;
89  }
90 
91  // We want to order BCEAtoms by (Base, Offset). However we cannot use
92  // the pointer values for Base because these are non-deterministic.
93  // To make sure that the sort order is stable, we first assign to each atom
94  // base value an index based on its order of appearance in the chain of
95  // comparisons. We call this index `BaseOrdering`. For example, for:
96  // b[3] == c[2] && a[1] == d[1] && b[4] == c[3]
97  // | block 1 | | block 2 | | block 3 |
98  // b gets assigned index 0 and a index 1, because b appears as LHS in block 1,
99  // which is before block 2.
100  // We then sort by (BaseOrdering[LHS.Base()], LHS.Offset), which is stable.
101  bool operator<(const BCEAtom &O) const {
102  return BaseId != O.BaseId ? BaseId < O.BaseId : Offset.slt(O.Offset);
103  }
104 
105  GetElementPtrInst *GEP = nullptr;
106  LoadInst *LoadI = nullptr;
107  unsigned BaseId = 0;
108  APInt Offset;
109 };
110 
111 // A class that assigns increasing ids to values in the order in which they are
112 // seen. See comment in `BCEAtom::operator<()``.
113 class BaseIdentifier {
114 public:
115  // Returns the id for value `Base`, after assigning one if `Base` has not been
116  // seen before.
117  int getBaseId(const Value *Base) {
118  assert(Base && "invalid base");
119  const auto Insertion = BaseToIndex.try_emplace(Base, Order);
120  if (Insertion.second)
121  ++Order;
122  return Insertion.first->second;
123  }
124 
125 private:
126  unsigned Order = 1;
127  DenseMap<const Value*, int> BaseToIndex;
128 };
129 
130 // If this value is a load from a constant offset w.r.t. a base address, and
131 // there are no other users of the load or address, returns the base address and
132 // the offset.
133 BCEAtom visitICmpLoadOperand(Value *const Val, BaseIdentifier &BaseId) {
134  auto *const LoadI = dyn_cast<LoadInst>(Val);
135  if (!LoadI)
136  return {};
137  LLVM_DEBUG(dbgs() << "load\n");
138  if (LoadI->isUsedOutsideOfBlock(LoadI->getParent())) {
139  LLVM_DEBUG(dbgs() << "used outside of block\n");
140  return {};
141  }
142  // Do not optimize atomic loads to non-atomic memcmp
143  if (!LoadI->isSimple()) {
144  LLVM_DEBUG(dbgs() << "volatile or atomic\n");
145  return {};
146  }
147  Value *const Addr = LoadI->getOperand(0);
148  if (Addr->getType()->getPointerAddressSpace() != 0) {
149  LLVM_DEBUG(dbgs() << "from non-zero AddressSpace\n");
150  return {};
151  }
152  auto *const GEP = dyn_cast<GetElementPtrInst>(Addr);
153  if (!GEP)
154  return {};
155  LLVM_DEBUG(dbgs() << "GEP\n");
156  if (GEP->isUsedOutsideOfBlock(LoadI->getParent())) {
157  LLVM_DEBUG(dbgs() << "used outside of block\n");
158  return {};
159  }
160  const auto &DL = GEP->getModule()->getDataLayout();
161  if (!isDereferenceablePointer(GEP, LoadI->getType(), DL)) {
162  LLVM_DEBUG(dbgs() << "not dereferenceable\n");
163  // We need to make sure that we can do comparison in any order, so we
164  // require memory to be unconditionnally dereferencable.
165  return {};
166  }
167  APInt Offset = APInt(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
168  if (!GEP->accumulateConstantOffset(DL, Offset))
169  return {};
170  return BCEAtom(GEP, LoadI, BaseId.getBaseId(GEP->getPointerOperand()),
171  Offset);
172 }
173 
174 // A comparison between two BCE atoms, e.g. `a == o.a` in the example at the
175 // top.
176 // Note: the terminology is misleading: the comparison is symmetric, so there
177 // is no real {l/r}hs. What we want though is to have the same base on the
178 // left (resp. right), so that we can detect consecutive loads. To ensure this
179 // we put the smallest atom on the left.
180 struct BCECmp {
181  BCEAtom Lhs;
182  BCEAtom Rhs;
183  int SizeBits;
184  const ICmpInst *CmpI;
185 
186  BCECmp(BCEAtom L, BCEAtom R, int SizeBits, const ICmpInst *CmpI)
187  : Lhs(std::move(L)), Rhs(std::move(R)), SizeBits(SizeBits), CmpI(CmpI) {
188  if (Rhs < Lhs) std::swap(Rhs, Lhs);
189  }
190 };
191 
192 // A basic block with a comparison between two BCE atoms.
193 // The block might do extra work besides the atom comparison, in which case
194 // doesOtherWork() returns true. Under some conditions, the block can be
195 // split into the atom comparison part and the "other work" part
196 // (see canSplit()).
197 class BCECmpBlock {
198  public:
199  typedef SmallDenseSet<const Instruction *, 8> InstructionSet;
200 
201  BCECmpBlock(BCECmp Cmp, BasicBlock *BB, InstructionSet BlockInsts)
202  : BB(BB), BlockInsts(std::move(BlockInsts)), Cmp(std::move(Cmp)) {}
203 
204  const BCEAtom &Lhs() const { return Cmp.Lhs; }
205  const BCEAtom &Rhs() const { return Cmp.Rhs; }
206  int SizeBits() const { return Cmp.SizeBits; }
207 
208  // Returns true if the block does other works besides comparison.
209  bool doesOtherWork() const;
210 
211  // Returns true if the non-BCE-cmp instructions can be separated from BCE-cmp
212  // instructions in the block.
213  bool canSplit(AliasAnalysis &AA) const;
214 
215  // Return true if this all the relevant instructions in the BCE-cmp-block can
216  // be sunk below this instruction. By doing this, we know we can separate the
217  // BCE-cmp-block instructions from the non-BCE-cmp-block instructions in the
218  // block.
219  bool canSinkBCECmpInst(const Instruction *, AliasAnalysis &AA) const;
220 
221  // We can separate the BCE-cmp-block instructions and the non-BCE-cmp-block
222  // instructions. Split the old block and move all non-BCE-cmp-insts into the
223  // new parent block.
224  void split(BasicBlock *NewParent, AliasAnalysis &AA) const;
225 
226  // The basic block where this comparison happens.
227  BasicBlock *BB;
228  // Instructions relating to the BCECmp and branch.
229  InstructionSet BlockInsts;
230  // The block requires splitting.
231  bool RequireSplit = false;
232  // Original order of this block in the chain.
233  unsigned OrigOrder = 0;
234 
235 private:
236  BCECmp Cmp;
237 };
238 
239 bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst,
240  AliasAnalysis &AA) const {
241  // If this instruction may clobber the loads and is in middle of the BCE cmp
242  // block instructions, then bail for now.
243  if (Inst->mayWriteToMemory()) {
244  auto MayClobber = [&](LoadInst *LI) {
245  // If a potentially clobbering instruction comes before the load,
246  // we can still safely sink the load.
247  return !Inst->comesBefore(LI) &&
249  };
250  if (MayClobber(Cmp.Lhs.LoadI) || MayClobber(Cmp.Rhs.LoadI))
251  return false;
252  }
253  // Make sure this instruction does not use any of the BCE cmp block
254  // instructions as operand.
255  return llvm::none_of(Inst->operands(), [&](const Value *Op) {
256  const Instruction *OpI = dyn_cast<Instruction>(Op);
257  return OpI && BlockInsts.contains(OpI);
258  });
259 }
260 
261 void BCECmpBlock::split(BasicBlock *NewParent, AliasAnalysis &AA) const {
263  for (Instruction &Inst : *BB) {
264  if (BlockInsts.count(&Inst))
265  continue;
266  assert(canSinkBCECmpInst(&Inst, AA) && "Split unsplittable block");
267  // This is a non-BCE-cmp-block instruction. And it can be separated
268  // from the BCE-cmp-block instruction.
269  OtherInsts.push_back(&Inst);
270  }
271 
272  // Do the actual spliting.
273  for (Instruction *Inst : reverse(OtherInsts)) {
274  Inst->moveBefore(&*NewParent->begin());
275  }
276 }
277 
278 bool BCECmpBlock::canSplit(AliasAnalysis &AA) const {
279  for (Instruction &Inst : *BB) {
280  if (!BlockInsts.count(&Inst)) {
281  if (!canSinkBCECmpInst(&Inst, AA))
282  return false;
283  }
284  }
285  return true;
286 }
287 
288 bool BCECmpBlock::doesOtherWork() const {
289  // TODO(courbet): Can we allow some other things ? This is very conservative.
290  // We might be able to get away with anything does not have any side
291  // effects outside of the basic block.
292  // Note: The GEPs and/or loads are not necessarily in the same block.
293  for (const Instruction &Inst : *BB) {
294  if (!BlockInsts.count(&Inst))
295  return true;
296  }
297  return false;
298 }
299 
300 // Visit the given comparison. If this is a comparison between two valid
301 // BCE atoms, returns the comparison.
302 Optional<BCECmp> visitICmp(const ICmpInst *const CmpI,
303  const ICmpInst::Predicate ExpectedPredicate,
304  BaseIdentifier &BaseId) {
305  // The comparison can only be used once:
306  // - For intermediate blocks, as a branch condition.
307  // - For the final block, as an incoming value for the Phi.
308  // If there are any other uses of the comparison, we cannot merge it with
309  // other comparisons as we would create an orphan use of the value.
310  if (!CmpI->hasOneUse()) {
311  LLVM_DEBUG(dbgs() << "cmp has several uses\n");
312  return None;
313  }
314  if (CmpI->getPredicate() != ExpectedPredicate)
315  return None;
316  LLVM_DEBUG(dbgs() << "cmp "
317  << (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne")
318  << "\n");
319  auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0), BaseId);
320  if (!Lhs.BaseId)
321  return None;
322  auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1), BaseId);
323  if (!Rhs.BaseId)
324  return None;
325  const auto &DL = CmpI->getModule()->getDataLayout();
326  return BCECmp(std::move(Lhs), std::move(Rhs),
327  DL.getTypeSizeInBits(CmpI->getOperand(0)->getType()), CmpI);
328 }
329 
330 // Visit the given comparison block. If this is a comparison between two valid
331 // BCE atoms, returns the comparison.
332 Optional<BCECmpBlock> visitCmpBlock(Value *const Val, BasicBlock *const Block,
333  const BasicBlock *const PhiBlock,
334  BaseIdentifier &BaseId) {
335  if (Block->empty()) return None;
336  auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator());
337  if (!BranchI) return None;
338  LLVM_DEBUG(dbgs() << "branch\n");
339  Value *Cond;
340  ICmpInst::Predicate ExpectedPredicate;
341  if (BranchI->isUnconditional()) {
342  // In this case, we expect an incoming value which is the result of the
343  // comparison. This is the last link in the chain of comparisons (note
344  // that this does not mean that this is the last incoming value, blocks
345  // can be reordered).
346  Cond = Val;
347  ExpectedPredicate = ICmpInst::ICMP_EQ;
348  } else {
349  // In this case, we expect a constant incoming value (the comparison is
350  // chained).
351  const auto *const Const = cast<ConstantInt>(Val);
352  LLVM_DEBUG(dbgs() << "const\n");
353  if (!Const->isZero()) return None;
354  LLVM_DEBUG(dbgs() << "false\n");
355  assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch");
356  BasicBlock *const FalseBlock = BranchI->getSuccessor(1);
357  Cond = BranchI->getCondition();
358  ExpectedPredicate =
359  FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
360  }
361 
362  auto *CmpI = dyn_cast<ICmpInst>(Cond);
363  if (!CmpI) return None;
364  LLVM_DEBUG(dbgs() << "icmp\n");
365 
366  Optional<BCECmp> Result = visitICmp(CmpI, ExpectedPredicate, BaseId);
367  if (!Result)
368  return None;
369 
370  BCECmpBlock::InstructionSet BlockInsts(
371  {Result->Lhs.GEP, Result->Rhs.GEP, Result->Lhs.LoadI, Result->Rhs.LoadI,
372  Result->CmpI, BranchI});
373  return BCECmpBlock(std::move(*Result), Block, BlockInsts);
374 }
375 
376 static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons,
377  BCECmpBlock &&Comparison) {
378  LLVM_DEBUG(dbgs() << "Block '" << Comparison.BB->getName()
379  << "': Found cmp of " << Comparison.SizeBits()
380  << " bits between " << Comparison.Lhs().BaseId << " + "
381  << Comparison.Lhs().Offset << " and "
382  << Comparison.Rhs().BaseId << " + "
383  << Comparison.Rhs().Offset << "\n");
384  LLVM_DEBUG(dbgs() << "\n");
385  Comparison.OrigOrder = Comparisons.size();
386  Comparisons.push_back(std::move(Comparison));
387 }
388 
389 // A chain of comparisons.
390 class BCECmpChain {
391 public:
392  using ContiguousBlocks = std::vector<BCECmpBlock>;
393 
394  BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
395  AliasAnalysis &AA);
396 
397  bool simplify(const TargetLibraryInfo &TLI, AliasAnalysis &AA,
398  DomTreeUpdater &DTU);
399 
400  bool atLeastOneMerged() const {
401  return any_of(MergedBlocks_,
402  [](const auto &Blocks) { return Blocks.size() > 1; });
403  }
404 
405 private:
406  PHINode &Phi_;
407  // The list of all blocks in the chain, grouped by contiguity.
408  std::vector<ContiguousBlocks> MergedBlocks_;
409  // The original entry block (before sorting);
410  BasicBlock *EntryBlock_;
411 };
412 
413 static bool areContiguous(const BCECmpBlock &First, const BCECmpBlock &Second) {
414  return First.Lhs().BaseId == Second.Lhs().BaseId &&
415  First.Rhs().BaseId == Second.Rhs().BaseId &&
416  First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset &&
417  First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset;
418 }
419 
420 static unsigned getMinOrigOrder(const BCECmpChain::ContiguousBlocks &Blocks) {
421  unsigned MinOrigOrder = std::numeric_limits<unsigned>::max();
422  for (const BCECmpBlock &Block : Blocks)
423  MinOrigOrder = std::min(MinOrigOrder, Block.OrigOrder);
424  return MinOrigOrder;
425 }
426 
427 /// Given a chain of comparison blocks, groups the blocks into contiguous
428 /// ranges that can be merged together into a single comparison.
429 static std::vector<BCECmpChain::ContiguousBlocks>
430 mergeBlocks(std::vector<BCECmpBlock> &&Blocks) {
431  std::vector<BCECmpChain::ContiguousBlocks> MergedBlocks;
432 
433  // Sort to detect continuous offsets.
434  llvm::sort(Blocks,
435  [](const BCECmpBlock &LhsBlock, const BCECmpBlock &RhsBlock) {
436  return std::tie(LhsBlock.Lhs(), LhsBlock.Rhs()) <
437  std::tie(RhsBlock.Lhs(), RhsBlock.Rhs());
438  });
439 
440  BCECmpChain::ContiguousBlocks *LastMergedBlock = nullptr;
441  for (BCECmpBlock &Block : Blocks) {
442  if (!LastMergedBlock || !areContiguous(LastMergedBlock->back(), Block)) {
443  MergedBlocks.emplace_back();
444  LastMergedBlock = &MergedBlocks.back();
445  } else {
446  LLVM_DEBUG(dbgs() << "Merging block " << Block.BB->getName() << " into "
447  << LastMergedBlock->back().BB->getName() << "\n");
448  }
449  LastMergedBlock->push_back(std::move(Block));
450  }
451 
452  // While we allow reordering for merging, do not reorder unmerged comparisons.
453  // Doing so may introduce branch on poison.
454  llvm::sort(MergedBlocks, [](const BCECmpChain::ContiguousBlocks &LhsBlocks,
455  const BCECmpChain::ContiguousBlocks &RhsBlocks) {
456  return getMinOrigOrder(LhsBlocks) < getMinOrigOrder(RhsBlocks);
457  });
458 
459  return MergedBlocks;
460 }
461 
462 BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
463  AliasAnalysis &AA)
464  : Phi_(Phi) {
465  assert(!Blocks.empty() && "a chain should have at least one block");
466  // Now look inside blocks to check for BCE comparisons.
467  std::vector<BCECmpBlock> Comparisons;
468  BaseIdentifier BaseId;
469  for (BasicBlock *const Block : Blocks) {
470  assert(Block && "invalid block");
471  Optional<BCECmpBlock> Comparison = visitCmpBlock(
472  Phi.getIncomingValueForBlock(Block), Block, Phi.getParent(), BaseId);
473  if (!Comparison) {
474  LLVM_DEBUG(dbgs() << "chain with invalid BCECmpBlock, no merge.\n");
475  return;
476  }
477  if (Comparison->doesOtherWork()) {
478  LLVM_DEBUG(dbgs() << "block '" << Comparison->BB->getName()
479  << "' does extra work besides compare\n");
480  if (Comparisons.empty()) {
481  // This is the initial block in the chain, in case this block does other
482  // work, we can try to split the block and move the irrelevant
483  // instructions to the predecessor.
484  //
485  // If this is not the initial block in the chain, splitting it wont
486  // work.
487  //
488  // As once split, there will still be instructions before the BCE cmp
489  // instructions that do other work in program order, i.e. within the
490  // chain before sorting. Unless we can abort the chain at this point
491  // and start anew.
492  //
493  // NOTE: we only handle blocks a with single predecessor for now.
494  if (Comparison->canSplit(AA)) {
495  LLVM_DEBUG(dbgs()
496  << "Split initial block '" << Comparison->BB->getName()
497  << "' that does extra work besides compare\n");
498  Comparison->RequireSplit = true;
499  enqueueBlock(Comparisons, std::move(*Comparison));
500  } else {
501  LLVM_DEBUG(dbgs()
502  << "ignoring initial block '" << Comparison->BB->getName()
503  << "' that does extra work besides compare\n");
504  }
505  continue;
506  }
507  // TODO(courbet): Right now we abort the whole chain. We could be
508  // merging only the blocks that don't do other work and resume the
509  // chain from there. For example:
510  // if (a[0] == b[0]) { // bb1
511  // if (a[1] == b[1]) { // bb2
512  // some_value = 3; //bb3
513  // if (a[2] == b[2]) { //bb3
514  // do a ton of stuff //bb4
515  // }
516  // }
517  // }
518  //
519  // This is:
520  //
521  // bb1 --eq--> bb2 --eq--> bb3* -eq--> bb4 --+
522  // \ \ \ \
523  // ne ne ne \
524  // \ \ \ v
525  // +------------+-----------+----------> bb_phi
526  //
527  // We can only merge the first two comparisons, because bb3* does
528  // "other work" (setting some_value to 3).
529  // We could still merge bb1 and bb2 though.
530  return;
531  }
532  enqueueBlock(Comparisons, std::move(*Comparison));
533  }
534 
535  // It is possible we have no suitable comparison to merge.
536  if (Comparisons.empty()) {
537  LLVM_DEBUG(dbgs() << "chain with no BCE basic blocks, no merge\n");
538  return;
539  }
540  EntryBlock_ = Comparisons[0].BB;
541  MergedBlocks_ = mergeBlocks(std::move(Comparisons));
542 }
543 
544 namespace {
545 
546 // A class to compute the name of a set of merged basic blocks.
547 // This is optimized for the common case of no block names.
548 class MergedBlockName {
549  // Storage for the uncommon case of several named blocks.
550  SmallString<16> Scratch;
551 
552 public:
553  explicit MergedBlockName(ArrayRef<BCECmpBlock> Comparisons)
554  : Name(makeName(Comparisons)) {}
555  const StringRef Name;
556 
557 private:
558  StringRef makeName(ArrayRef<BCECmpBlock> Comparisons) {
559  assert(!Comparisons.empty() && "no basic block");
560  // Fast path: only one block, or no names at all.
561  if (Comparisons.size() == 1)
562  return Comparisons[0].BB->getName();
563  const int size = std::accumulate(Comparisons.begin(), Comparisons.end(), 0,
564  [](int i, const BCECmpBlock &Cmp) {
565  return i + Cmp.BB->getName().size();
566  });
567  if (size == 0)
568  return StringRef("", 0);
569 
570  // Slow path: at least two blocks, at least one block with a name.
571  Scratch.clear();
572  // We'll have `size` bytes for name and `Comparisons.size() - 1` bytes for
573  // separators.
574  Scratch.reserve(size + Comparisons.size() - 1);
575  const auto append = [this](StringRef str) {
576  Scratch.append(str.begin(), str.end());
577  };
578  append(Comparisons[0].BB->getName());
579  for (int I = 1, E = Comparisons.size(); I < E; ++I) {
580  const BasicBlock *const BB = Comparisons[I].BB;
581  if (!BB->getName().empty()) {
582  append("+");
583  append(BB->getName());
584  }
585  }
586  return Scratch.str();
587  }
588 };
589 } // namespace
590 
591 // Merges the given contiguous comparison blocks into one memcmp block.
592 static BasicBlock *mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
593  BasicBlock *const InsertBefore,
594  BasicBlock *const NextCmpBlock,
595  PHINode &Phi, const TargetLibraryInfo &TLI,
596  AliasAnalysis &AA, DomTreeUpdater &DTU) {
597  assert(!Comparisons.empty() && "merging zero comparisons");
598  LLVMContext &Context = NextCmpBlock->getContext();
599  const BCECmpBlock &FirstCmp = Comparisons[0];
600 
601  // Create a new cmp block before next cmp block.
602  BasicBlock *const BB =
603  BasicBlock::Create(Context, MergedBlockName(Comparisons).Name,
604  NextCmpBlock->getParent(), InsertBefore);
606  // Add the GEPs from the first BCECmpBlock.
607  Value *const Lhs = Builder.Insert(FirstCmp.Lhs().GEP->clone());
608  Value *const Rhs = Builder.Insert(FirstCmp.Rhs().GEP->clone());
609 
610  Value *IsEqual = nullptr;
611  LLVM_DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons -> "
612  << BB->getName() << "\n");
613 
614  // If there is one block that requires splitting, we do it now, i.e.
615  // just before we know we will collapse the chain. The instructions
616  // can be executed before any of the instructions in the chain.
617  const auto ToSplit = llvm::find_if(
618  Comparisons, [](const BCECmpBlock &B) { return B.RequireSplit; });
619  if (ToSplit != Comparisons.end()) {
620  LLVM_DEBUG(dbgs() << "Splitting non_BCE work to header\n");
621  ToSplit->split(BB, AA);
622  }
623 
624  if (Comparisons.size() == 1) {
625  LLVM_DEBUG(dbgs() << "Only one comparison, updating branches\n");
626  Value *const LhsLoad =
627  Builder.CreateLoad(FirstCmp.Lhs().LoadI->getType(), Lhs);
628  Value *const RhsLoad =
629  Builder.CreateLoad(FirstCmp.Rhs().LoadI->getType(), Rhs);
630  // There are no blocks to merge, just do the comparison.
631  IsEqual = Builder.CreateICmpEQ(LhsLoad, RhsLoad);
632  } else {
633  const unsigned TotalSizeBits = std::accumulate(
634  Comparisons.begin(), Comparisons.end(), 0u,
635  [](int Size, const BCECmpBlock &C) { return Size + C.SizeBits(); });
636 
637  // Create memcmp() == 0.
638  const auto &DL = Phi.getModule()->getDataLayout();
639  Value *const MemCmpCall = emitMemCmp(
640  Lhs, Rhs,
641  ConstantInt::get(DL.getIntPtrType(Context), TotalSizeBits / 8), Builder,
642  DL, &TLI);
643  IsEqual = Builder.CreateICmpEQ(
644  MemCmpCall, ConstantInt::get(Type::getInt32Ty(Context), 0));
645  }
646 
647  BasicBlock *const PhiBB = Phi.getParent();
648  // Add a branch to the next basic block in the chain.
649  if (NextCmpBlock == PhiBB) {
650  // Continue to phi, passing it the comparison result.
651  Builder.CreateBr(PhiBB);
652  Phi.addIncoming(IsEqual, BB);
653  DTU.applyUpdates({{DominatorTree::Insert, BB, PhiBB}});
654  } else {
655  // Continue to next block if equal, exit to phi else.
656  Builder.CreateCondBr(IsEqual, NextCmpBlock, PhiBB);
658  DTU.applyUpdates({{DominatorTree::Insert, BB, NextCmpBlock},
659  {DominatorTree::Insert, BB, PhiBB}});
660  }
661  return BB;
662 }
663 
665  DomTreeUpdater &DTU) {
666  assert(atLeastOneMerged() && "simplifying trivial BCECmpChain");
667  LLVM_DEBUG(dbgs() << "Simplifying comparison chain starting at block "
668  << EntryBlock_->getName() << "\n");
669 
670  // Effectively merge blocks. We go in the reverse direction from the phi block
671  // so that the next block is always available to branch to.
672  BasicBlock *InsertBefore = EntryBlock_;
673  BasicBlock *NextCmpBlock = Phi_.getParent();
674  for (const auto &Blocks : reverse(MergedBlocks_)) {
675  InsertBefore = NextCmpBlock = mergeComparisons(
676  Blocks, InsertBefore, NextCmpBlock, Phi_, TLI, AA, DTU);
677  }
678 
679  // Replace the original cmp chain with the new cmp chain by pointing all
680  // predecessors of EntryBlock_ to NextCmpBlock instead. This makes all cmp
681  // blocks in the old chain unreachable.
682  while (!pred_empty(EntryBlock_)) {
683  BasicBlock* const Pred = *pred_begin(EntryBlock_);
684  LLVM_DEBUG(dbgs() << "Updating jump into old chain from " << Pred->getName()
685  << "\n");
686  Pred->getTerminator()->replaceUsesOfWith(EntryBlock_, NextCmpBlock);
687  DTU.applyUpdates({{DominatorTree::Delete, Pred, EntryBlock_},
688  {DominatorTree::Insert, Pred, NextCmpBlock}});
689  }
690 
691  // If the old cmp chain was the function entry, we need to update the function
692  // entry.
693  const bool ChainEntryIsFnEntry = EntryBlock_->isEntryBlock();
694  if (ChainEntryIsFnEntry && DTU.hasDomTree()) {
695  LLVM_DEBUG(dbgs() << "Changing function entry from "
696  << EntryBlock_->getName() << " to "
697  << NextCmpBlock->getName() << "\n");
698  DTU.getDomTree().setNewRoot(NextCmpBlock);
699  DTU.applyUpdates({{DominatorTree::Delete, NextCmpBlock, EntryBlock_}});
700  }
701  EntryBlock_ = nullptr;
702 
703  // Delete merged blocks. This also removes incoming values in phi.
705  for (const auto &Blocks : MergedBlocks_) {
706  for (const BCECmpBlock &Block : Blocks) {
707  LLVM_DEBUG(dbgs() << "Deleting merged block " << Block.BB->getName()
708  << "\n");
709  DeadBlocks.push_back(Block.BB);
710  }
711  }
712  DeleteDeadBlocks(DeadBlocks, &DTU);
713 
714  MergedBlocks_.clear();
715  return true;
716 }
717 
718 std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
719  BasicBlock *const LastBlock,
720  int NumBlocks) {
721  // Walk up from the last block to find other blocks.
722  std::vector<BasicBlock *> Blocks(NumBlocks);
723  assert(LastBlock && "invalid last block");
724  BasicBlock *CurBlock = LastBlock;
725  for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) {
726  if (CurBlock->hasAddressTaken()) {
727  // Somebody is jumping to the block through an address, all bets are
728  // off.
729  LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
730  << " has its address taken\n");
731  return {};
732  }
733  Blocks[BlockIndex] = CurBlock;
734  auto *SinglePredecessor = CurBlock->getSinglePredecessor();
735  if (!SinglePredecessor) {
736  // The block has two or more predecessors.
737  LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
738  << " has two or more predecessors\n");
739  return {};
740  }
741  if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) {
742  // The block does not link back to the phi.
743  LLVM_DEBUG(dbgs() << "skip: block " << BlockIndex
744  << " does not link back to the phi\n");
745  return {};
746  }
747  CurBlock = SinglePredecessor;
748  }
749  Blocks[0] = CurBlock;
750  return Blocks;
751 }
752 
753 bool processPhi(PHINode &Phi, const TargetLibraryInfo &TLI, AliasAnalysis &AA,
754  DomTreeUpdater &DTU) {
755  LLVM_DEBUG(dbgs() << "processPhi()\n");
756  if (Phi.getNumIncomingValues() <= 1) {
757  LLVM_DEBUG(dbgs() << "skip: only one incoming value in phi\n");
758  return false;
759  }
760  // We are looking for something that has the following structure:
761  // bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+
762  // \ \ \ \
763  // ne ne ne \
764  // \ \ \ v
765  // +------------+-----------+----------> bb_phi
766  //
767  // - The last basic block (bb4 here) must branch unconditionally to bb_phi.
768  // It's the only block that contributes a non-constant value to the Phi.
769  // - All other blocks (b1, b2, b3) must have exactly two successors, one of
770  // them being the phi block.
771  // - All intermediate blocks (bb2, bb3) must have only one predecessor.
772  // - Blocks cannot do other work besides the comparison, see doesOtherWork()
773 
774  // The blocks are not necessarily ordered in the phi, so we start from the
775  // last block and reconstruct the order.
776  BasicBlock *LastBlock = nullptr;
777  for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) {
778  if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue;
779  if (LastBlock) {
780  // There are several non-constant values.
781  LLVM_DEBUG(dbgs() << "skip: several non-constant values\n");
782  return false;
783  }
784  if (!isa<ICmpInst>(Phi.getIncomingValue(I)) ||
785  cast<ICmpInst>(Phi.getIncomingValue(I))->getParent() !=
786  Phi.getIncomingBlock(I)) {
787  // Non-constant incoming value is not from a cmp instruction or not
788  // produced by the last block. We could end up processing the value
789  // producing block more than once.
790  //
791  // This is an uncommon case, so we bail.
792  LLVM_DEBUG(
793  dbgs()
794  << "skip: non-constant value not from cmp or not from last block.\n");
795  return false;
796  }
797  LastBlock = Phi.getIncomingBlock(I);
798  }
799  if (!LastBlock) {
800  // There is no non-constant block.
801  LLVM_DEBUG(dbgs() << "skip: no non-constant block\n");
802  return false;
803  }
804  if (LastBlock->getSingleSuccessor() != Phi.getParent()) {
805  LLVM_DEBUG(dbgs() << "skip: last block non-phi successor\n");
806  return false;
807  }
808 
809  const auto Blocks =
810  getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues());
811  if (Blocks.empty()) return false;
812  BCECmpChain CmpChain(Blocks, Phi, AA);
813 
814  if (!CmpChain.atLeastOneMerged()) {
815  LLVM_DEBUG(dbgs() << "skip: nothing merged\n");
816  return false;
817  }
818 
819  return CmpChain.simplify(TLI, AA, DTU);
820 }
821 
822 static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
824  DominatorTree *DT) {
825  LLVM_DEBUG(dbgs() << "MergeICmpsLegacyPass: " << F.getName() << "\n");
826 
827  // We only try merging comparisons if the target wants to expand memcmp later.
828  // The rationale is to avoid turning small chains into memcmp calls.
829  if (!TTI.enableMemCmpExpansion(F.hasOptSize(), true))
830  return false;
831 
832  // If we don't have memcmp avaiable we can't emit calls to it.
833  if (!TLI.has(LibFunc_memcmp))
834  return false;
835 
836  DomTreeUpdater DTU(DT, /*PostDominatorTree*/ nullptr,
837  DomTreeUpdater::UpdateStrategy::Eager);
838 
839  bool MadeChange = false;
840 
841  for (BasicBlock &BB : llvm::drop_begin(F)) {
842  // A Phi operation is always first in a basic block.
843  if (auto *const Phi = dyn_cast<PHINode>(&*BB.begin()))
844  MadeChange |= processPhi(*Phi, TLI, AA, DTU);
845  }
846 
847  return MadeChange;
848 }
849 
850 class MergeICmpsLegacyPass : public FunctionPass {
851 public:
852  static char ID;
853 
854  MergeICmpsLegacyPass() : FunctionPass(ID) {
855  initializeMergeICmpsLegacyPassPass(*PassRegistry::getPassRegistry());
856  }
857 
858  bool runOnFunction(Function &F) override {
859  if (skipFunction(F)) return false;
860  const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
861  const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
862  // MergeICmps does not need the DominatorTree, but we update it if it's
863  // already available.
864  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
865  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
866  return runImpl(F, TLI, TTI, AA, DTWP ? &DTWP->getDomTree() : nullptr);
867  }
868 
869  private:
870  void getAnalysisUsage(AnalysisUsage &AU) const override {
876  }
877 };
878 
879 } // namespace
880 
881 char MergeICmpsLegacyPass::ID = 0;
882 INITIALIZE_PASS_BEGIN(MergeICmpsLegacyPass, "mergeicmps",
883  "Merge contiguous icmps into a memcmp", false, false)
887 INITIALIZE_PASS_END(MergeICmpsLegacyPass, "mergeicmps",
888  "Merge contiguous icmps into a memcmp", false, false)
889 
890 Pass *llvm::createMergeICmpsLegacyPass() { return new MergeICmpsLegacyPass(); }
891 
892 PreservedAnalyses MergeICmpsPass::run(Function &F,
894  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
895  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
896  auto &AA = AM.getResult<AAManager>(F);
897  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
898  const bool MadeChanges = runImpl(F, TLI, TTI, AA, DT);
899  if (!MadeChanges)
900  return PreservedAnalyses::all();
903  return PA;
904 }
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:1288
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2331
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
---------------------— PointerInfo ------------------------------------—
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:741
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1565
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:266
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:720
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:779
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:1168
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:168
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
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:742
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:888
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:333
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:294
llvm::Instruction::comesBefore
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
Definition: Instruction.cpp:111
llvm::Optional
Definition: APInt.h:33
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
that
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local $pop6 WebAssembly registers are implicitly initialized to zero Explicit zeroing is therefore often redundant and could be optimized away Small indices may use smaller encodings than large indices WebAssemblyRegColoring and or WebAssemblyRegRenumbering should sort registers according to their usage frequency to maximize the usage of smaller encodings Many cases of irreducible control flow could be transformed more optimally than via the transform in WebAssemblyFixIrreducibleControlFlow cpp It may also be worthwhile to do transforms before register particularly when duplicating to allow register coloring to be aware of the duplication WebAssemblyRegStackify could use AliasAnalysis to reorder loads and stores more aggressively WebAssemblyRegStackify is currently a greedy algorithm This means that
Definition: README.txt:130
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:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:198
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:163
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2729
llvm::AAResults
Definition: AliasAnalysis.h:508
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:2818
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:287
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:584
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:197
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2725
llvm::None
const NoneType None
Definition: None.h:23
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::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:197
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1203
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:465
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2387
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:2783
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:338
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:928
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:2811
size
i< reg-> size
Definition: README.txt:166
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:1609
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:122
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:325
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::TargetTransformInfo::enableMemCmpExpansion
MemCmpExpansionOptions enableMemCmpExpansion(bool OptSize, bool IsZeroCmp) const
Definition: TargetTransformInfo.cpp:501
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1558
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
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:309
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
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:1578
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:2276
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::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
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:798
Function.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:221
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::SmallString::str
StringRef str() const
Explicit conversion to StringRef.
Definition: SmallString.h:259
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::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:887
Dominators.h
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1336
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:796
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:2749
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2633
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:401
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:172
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
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:440
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:218
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:154
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:37
llvm::createMergeICmpsLegacyPass
Pass * createMergeICmpsLegacyPass()
Definition: MergeICmps.cpp:890