LLVM  16.0.0git
DivRemPairs.cpp
Go to the documentation of this file.
1 //===- DivRemPairs.cpp - Hoist/[dr]ecompose division and remainder --------===//
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 hoists and/or decomposes/recomposes integer division and remainder
10 // instructions to enable CFG improvements and better codegen.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/MapVector.h"
17 #include "llvm/ADT/Statistic.h"
21 #include "llvm/IR/Dominators.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/PatternMatch.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Pass.h"
27 #include "llvm/Transforms/Scalar.h"
29 #include <optional>
30 
31 using namespace llvm;
32 using namespace llvm::PatternMatch;
33 
34 #define DEBUG_TYPE "div-rem-pairs"
35 STATISTIC(NumPairs, "Number of div/rem pairs");
36 STATISTIC(NumRecomposed, "Number of instructions recomposed");
37 STATISTIC(NumHoisted, "Number of instructions hoisted");
38 STATISTIC(NumDecomposed, "Number of instructions decomposed");
39 DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",
40  "Controls transformations in div-rem-pairs pass");
41 
42 namespace {
43 struct ExpandedMatch {
46 };
47 } // namespace
48 
49 /// See if we can match: (which is the form we expand into)
50 /// X - ((X ?/ Y) * Y)
51 /// which is equivalent to:
52 /// X ?% Y
53 static std::optional<ExpandedMatch> matchExpandedRem(Instruction &I) {
54  Value *Dividend, *XroundedDownToMultipleOfY;
55  if (!match(&I, m_Sub(m_Value(Dividend), m_Value(XroundedDownToMultipleOfY))))
56  return std::nullopt;
57 
58  Value *Divisor;
59  Instruction *Div;
60  // Look for ((X / Y) * Y)
61  if (!match(
62  XroundedDownToMultipleOfY,
63  m_c_Mul(m_CombineAnd(m_IDiv(m_Specific(Dividend), m_Value(Divisor)),
64  m_Instruction(Div)),
65  m_Deferred(Divisor))))
66  return std::nullopt;
67 
68  ExpandedMatch M;
69  M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv;
70  M.Key.Dividend = Dividend;
71  M.Key.Divisor = Divisor;
72  M.Value = &I;
73  return M;
74 }
75 
76 namespace {
77 /// A thin wrapper to store two values that we matched as div-rem pair.
78 /// We want this extra indirection to avoid dealing with RAUW'ing the map keys.
79 struct DivRemPairWorklistEntry {
80  /// The actual udiv/sdiv instruction. Source of truth.
82 
83  /// The instruction that we have matched as a remainder instruction.
84  /// Should only be used as Value, don't introspect it.
86 
87  DivRemPairWorklistEntry(Instruction *DivInst_, Instruction *RemInst_)
88  : DivInst(DivInst_), RemInst(RemInst_) {
89  assert((DivInst->getOpcode() == Instruction::UDiv ||
90  DivInst->getOpcode() == Instruction::SDiv) &&
91  "Not a division.");
92  assert(DivInst->getType() == RemInst->getType() && "Types should match.");
93  // We can't check anything else about remainder instruction,
94  // it's not strictly required to be a urem/srem.
95  }
96 
97  /// The type for this pair, identical for both the div and rem.
98  Type *getType() const { return DivInst->getType(); }
99 
100  /// Is this pair signed or unsigned?
101  bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; }
102 
103  /// In this pair, what are the divident and divisor?
104  Value *getDividend() const { return DivInst->getOperand(0); }
105  Value *getDivisor() const { return DivInst->getOperand(1); }
106 
107  bool isRemExpanded() const {
108  switch (RemInst->getOpcode()) {
109  case Instruction::SRem:
110  case Instruction::URem:
111  return false; // single 'rem' instruction - unexpanded form.
112  default:
113  return true; // anything else means we have remainder in expanded form.
114  }
115  }
116 };
117 } // namespace
119 
120 /// Find matching pairs of integer div/rem ops (they have the same numerator,
121 /// denominator, and signedness). Place those pairs into a worklist for further
122 /// processing. This indirection is needed because we have to use TrackingVH<>
123 /// because we will be doing RAUW, and if one of the rem instructions we change
124 /// happens to be an input to another div/rem in the maps, we'd have problems.
126  // Insert all divide and remainder instructions into maps keyed by their
127  // operands and opcode (signed or unsigned).
129  // Use a MapVector for RemMap so that instructions are moved/inserted in a
130  // deterministic order.
132  for (auto &BB : F) {
133  for (auto &I : BB) {
134  if (I.getOpcode() == Instruction::SDiv)
135  DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
136  else if (I.getOpcode() == Instruction::UDiv)
137  DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
138  else if (I.getOpcode() == Instruction::SRem)
139  RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
140  else if (I.getOpcode() == Instruction::URem)
141  RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
142  else if (auto Match = matchExpandedRem(I))
143  RemMap[Match->Key] = Match->Value;
144  }
145  }
146 
147  // We'll accumulate the matching pairs of div-rem instructions here.
148  DivRemWorklistTy Worklist;
149 
150  // We can iterate over either map because we are only looking for matched
151  // pairs. Choose remainders for efficiency because they are usually even more
152  // rare than division.
153  for (auto &RemPair : RemMap) {
154  // Find the matching division instruction from the division map.
155  auto It = DivMap.find(RemPair.first);
156  if (It == DivMap.end())
157  continue;
158 
159  // We have a matching pair of div/rem instructions.
160  NumPairs++;
161  Instruction *RemInst = RemPair.second;
162 
163  // Place it in the worklist.
164  Worklist.emplace_back(It->second, RemInst);
165  }
166 
167  return Worklist;
168 }
169 
170 /// Find matching pairs of integer div/rem ops (they have the same numerator,
171 /// denominator, and signedness). If they exist in different basic blocks, bring
172 /// them together by hoisting or replace the common division operation that is
173 /// implicit in the remainder:
174 /// X % Y <--> X - ((X / Y) * Y).
175 ///
176 /// We can largely ignore the normal safety and cost constraints on speculation
177 /// of these ops when we find a matching pair. This is because we are already
178 /// guaranteed that any exceptions and most cost are already incurred by the
179 /// first member of the pair.
180 ///
181 /// Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or
182 /// SimplifyCFG, but it's split off on its own because it's different enough
183 /// that it doesn't quite match the stated objectives of those passes.
185  const DominatorTree &DT) {
186  bool Changed = false;
187 
188  // Get the matching pairs of div-rem instructions. We want this extra
189  // indirection to avoid dealing with having to RAUW the keys of the maps.
190  DivRemWorklistTy Worklist = getWorklist(F);
191 
192  // Process each entry in the worklist.
193  for (DivRemPairWorklistEntry &E : Worklist) {
194  if (!DebugCounter::shouldExecute(DRPCounter))
195  continue;
196 
197  bool HasDivRemOp = TTI.hasDivRemOp(E.getType(), E.isSigned());
198 
199  auto &DivInst = E.DivInst;
200  auto &RemInst = E.RemInst;
201 
202  const bool RemOriginallyWasInExpandedForm = E.isRemExpanded();
203  (void)RemOriginallyWasInExpandedForm; // suppress unused variable warning
204 
205  if (HasDivRemOp && E.isRemExpanded()) {
206  // The target supports div+rem but the rem is expanded.
207  // We should recompose it first.
208  Value *X = E.getDividend();
209  Value *Y = E.getDivisor();
210  Instruction *RealRem = E.isSigned() ? BinaryOperator::CreateSRem(X, Y)
211  : BinaryOperator::CreateURem(X, Y);
212  // Note that we place it right next to the original expanded instruction,
213  // and letting further handling to move it if needed.
214  RealRem->setName(RemInst->getName() + ".recomposed");
215  RealRem->insertAfter(RemInst);
216  Instruction *OrigRemInst = RemInst;
217  // Update AssertingVH<> with new instruction so it doesn't assert.
218  RemInst = RealRem;
219  // And replace the original instruction with the new one.
220  OrigRemInst->replaceAllUsesWith(RealRem);
221  OrigRemInst->eraseFromParent();
222  NumRecomposed++;
223  // Note that we have left ((X / Y) * Y) around.
224  // If it had other uses we could rewrite it as X - X % Y
225  Changed = true;
226  }
227 
228  assert((!E.isRemExpanded() || !HasDivRemOp) &&
229  "*If* the target supports div-rem, then by now the RemInst *is* "
230  "Instruction::[US]Rem.");
231 
232  // If the target supports div+rem and the instructions are in the same block
233  // already, there's nothing to do. The backend should handle this. If the
234  // target does not support div+rem, then we will decompose the rem.
235  if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())
236  continue;
237 
238  bool DivDominates = DT.dominates(DivInst, RemInst);
239  if (!DivDominates && !DT.dominates(RemInst, DivInst)) {
240  // We have matching div-rem pair, but they are in two different blocks,
241  // neither of which dominates one another.
242 
243  BasicBlock *PredBB = nullptr;
244  BasicBlock *DivBB = DivInst->getParent();
245  BasicBlock *RemBB = RemInst->getParent();
246 
247  // It's only safe to hoist if every instruction before the Div/Rem in the
248  // basic block is guaranteed to transfer execution.
249  auto IsSafeToHoist = [](Instruction *DivOrRem, BasicBlock *ParentBB) {
250  for (auto I = ParentBB->begin(), E = DivOrRem->getIterator(); I != E;
251  ++I)
253  return false;
254 
255  return true;
256  };
257 
258  // Look for something like this
259  // PredBB
260  // | \
261  // | Rem
262  // | /
263  // Div
264  //
265  // If the Rem block has a single predecessor and successor, and all paths
266  // from PredBB go to either RemBB or DivBB, and execution of RemBB and
267  // DivBB will always reach the Div/Rem, we can hoist Div to PredBB. If
268  // we have a DivRem operation we can also hoist Rem. Otherwise we'll leave
269  // Rem where it is and rewrite it to mul/sub.
270  // FIXME: We could handle more hoisting cases.
271  if (RemBB->getSingleSuccessor() == DivBB)
272  PredBB = RemBB->getUniquePredecessor();
273 
274  if (PredBB && IsSafeToHoist(RemInst, RemBB) &&
275  IsSafeToHoist(DivInst, DivBB) &&
276  all_of(successors(PredBB),
277  [&](BasicBlock *BB) { return BB == DivBB || BB == RemBB; }) &&
278  all_of(predecessors(DivBB),
279  [&](BasicBlock *BB) { return BB == RemBB || BB == PredBB; })) {
280  DivDominates = true;
281  DivInst->moveBefore(PredBB->getTerminator());
282  Changed = true;
283  if (HasDivRemOp) {
284  RemInst->moveBefore(PredBB->getTerminator());
285  continue;
286  }
287  } else
288  continue;
289  }
290 
291  // The target does not have a single div/rem operation,
292  // and the rem is already in expanded form. Nothing to do.
293  if (!HasDivRemOp && E.isRemExpanded())
294  continue;
295 
296  if (HasDivRemOp) {
297  // The target has a single div/rem operation. Hoist the lower instruction
298  // to make the matched pair visible to the backend.
299  if (DivDominates)
300  RemInst->moveAfter(DivInst);
301  else
302  DivInst->moveAfter(RemInst);
303  NumHoisted++;
304  } else {
305  // The target does not have a single div/rem operation,
306  // and the rem is *not* in a already-expanded form.
307  // Decompose the remainder calculation as:
308  // X % Y --> X - ((X / Y) * Y).
309 
310  assert(!RemOriginallyWasInExpandedForm &&
311  "We should not be expanding if the rem was in expanded form to "
312  "begin with.");
313 
314  Value *X = E.getDividend();
315  Value *Y = E.getDivisor();
317  Instruction *Sub = BinaryOperator::CreateSub(X, Mul);
318 
319  // If the remainder dominates, then hoist the division up to that block:
320  //
321  // bb1:
322  // %rem = srem %x, %y
323  // bb2:
324  // %div = sdiv %x, %y
325  // -->
326  // bb1:
327  // %div = sdiv %x, %y
328  // %mul = mul %div, %y
329  // %rem = sub %x, %mul
330  //
331  // If the division dominates, it's already in the right place. The mul+sub
332  // will be in a different block because we don't assume that they are
333  // cheap to speculatively execute:
334  //
335  // bb1:
336  // %div = sdiv %x, %y
337  // bb2:
338  // %rem = srem %x, %y
339  // -->
340  // bb1:
341  // %div = sdiv %x, %y
342  // bb2:
343  // %mul = mul %div, %y
344  // %rem = sub %x, %mul
345  //
346  // If the div and rem are in the same block, we do the same transform,
347  // but any code movement would be within the same block.
348 
349  if (!DivDominates)
350  DivInst->moveBefore(RemInst);
351  Mul->insertAfter(RemInst);
352  Sub->insertAfter(Mul);
353 
354  // If X can be undef, X should be frozen first.
355  // For example, let's assume that Y = 1 & X = undef:
356  // %div = sdiv undef, 1 // %div = undef
357  // %rem = srem undef, 1 // %rem = 0
358  // =>
359  // %div = sdiv undef, 1 // %div = undef
360  // %mul = mul %div, 1 // %mul = undef
361  // %rem = sub %x, %mul // %rem = undef - undef = undef
362  // If X is not frozen, %rem becomes undef after transformation.
363  // TODO: We need a undef-specific checking function in ValueTracking
364  if (!isGuaranteedNotToBeUndefOrPoison(X, nullptr, DivInst, &DT)) {
365  auto *FrX = new FreezeInst(X, X->getName() + ".frozen", DivInst);
366  DivInst->setOperand(0, FrX);
367  Sub->setOperand(0, FrX);
368  }
369  // Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0,
370  // but %rem in tgt can be one of many integer values.
371  if (!isGuaranteedNotToBeUndefOrPoison(Y, nullptr, DivInst, &DT)) {
372  auto *FrY = new FreezeInst(Y, Y->getName() + ".frozen", DivInst);
373  DivInst->setOperand(1, FrY);
374  Mul->setOperand(1, FrY);
375  }
376 
377  // Now kill the explicit remainder. We have replaced it with:
378  // (sub X, (mul (div X, Y), Y)
379  Sub->setName(RemInst->getName() + ".decomposed");
380  Instruction *OrigRemInst = RemInst;
381  // Update AssertingVH<> with new instruction so it doesn't assert.
382  RemInst = Sub;
383  // And replace the original instruction with the new one.
384  OrigRemInst->replaceAllUsesWith(Sub);
385  OrigRemInst->eraseFromParent();
386  NumDecomposed++;
387  }
388  Changed = true;
389  }
390 
391  return Changed;
392 }
393 
394 // Pass manager boilerplate below here.
395 
396 namespace {
397 struct DivRemPairsLegacyPass : public FunctionPass {
398  static char ID;
399  DivRemPairsLegacyPass() : FunctionPass(ID) {
401  }
402 
403  void getAnalysisUsage(AnalysisUsage &AU) const override {
406  AU.setPreservesCFG();
410  }
411 
412  bool runOnFunction(Function &F) override {
413  if (skipFunction(F))
414  return false;
415  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
416  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
417  return optimizeDivRem(F, TTI, DT);
418  }
419 };
420 } // namespace
421 
423 INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs",
424  "Hoist/decompose integer division and remainder", false,
425  false)
427 INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs",
428  "Hoist/decompose integer division and remainder", false,
429  false)
431  return new DivRemPairsLegacyPass();
432 }
433 
438  if (!optimizeDivRem(F, TTI, DT))
439  return PreservedAnalyses::all();
440  // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
442  PA.preserveSet<CFGAnalyses>();
443  return PA;
444 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2592
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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:774
Scalar.h
llvm::Function
Definition: Function.h:60
Pass.h
Hoist
TLS Variable Hoist
When an instruction is found to use only loop invariant operands that are safe to hoist,...
Definition: TLSVariableHoist.cpp:82
llvm::isGuaranteedNotToBeUndefOrPoison
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
Definition: ValueTracking.cpp:5440
optimizeDivRem
static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI, const DominatorTree &DT)
Find matching pairs of integer div/rem ops (they have the same numerator, denominator,...
Definition: DivRemPairs.cpp:184
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:173
MapVector.h
DivRemPairs.h
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
GlobalsModRef.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs", "Hoist/decompose integer division and remainder", false, false) INITIALIZE_PASS_END(DivRemPairsLegacyPass
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:315
matchExpandedRem
static std::optional< ExpandedMatch > matchExpandedRem(Instruction &I)
See if we can match: (which is the form we expand into) X - ((X ?/ Y) * Y) which is equivalent to: X ...
Definition: DivRemPairs.cpp:53
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::DiagnosticPredicateTy::Match
@ Match
and
We currently generate a but we really shouldn eax ecx xorl edx divl ecx eax divl ecx movl eax ret A similar code sequence works for division We currently compile i32 v2 eax eax jo LBB1_2 and
Definition: README.txt:1271
llvm::PatternMatch::m_Deferred
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
Definition: PatternMatch.h:790
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
remainder
div rem Hoist decompose integer division and remainder
Definition: DivRemPairs.cpp:428
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
llvm::createDivRemPairsPass
FunctionPass * createDivRemPairsPass()
Definition: DivRemPairs.cpp:430
llvm::Instruction::insertAfter
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:93
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:169
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1734
decompose
static Decomposition decompose(Value *V, SmallVectorImpl< PreconditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
Definition: ConstraintElimination.cpp:296
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:716
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
llvm::PatternMatch::m_IDiv
BinOpPred_match< LHS, RHS, is_idiv_op > m_IDiv(const LHS &L, const RHS &R)
Matches integer division operations.
Definition: PatternMatch.h:1324
pairs
div rem pairs
Definition: DivRemPairs.cpp:427
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:306
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
rem
expand large div rem
Definition: ExpandLargeDivRem.cpp:132
PatternMatch.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
BypassSlowDivision.h
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2648
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
getWorklist
static DivRemWorklistTy getWorklist(Function &F)
Find matching pairs of integer div/rem ops (they have the same numerator, denominator,...
Definition: DivRemPairs.cpp:125
llvm::Instruction::moveAfter
void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:111
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PatternMatch::m_Sub
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:991
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
getType
static M68kRelType getType(unsigned Kind, MCSymbolRefExpr::VariantKind &Modifier, bool &IsPCRel)
Definition: M68kELFObjectWriter.cpp:48
llvm::PatternMatch::m_CombineAnd
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:224
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:293
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::TargetTransformInfo::hasDivRemOp
bool hasDivRemOp(Type *DataType, bool IsSigned) const
Return true if the target has a unified operation to calculate division and remainder.
Definition: TargetTransformInfo.cpp:455
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::initializeDivRemPairsLegacyPassPass
void initializeDivRemPairsLegacyPassPass(PassRegistry &)
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::isGuaranteedToTransferExecutionToSuccessor
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Definition: ValueTracking.cpp:5471
Function.h
DebugCounter.h
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
DEBUG_COUNTER
DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform", "Controls transformations in div-rem-pairs pass")
llvm::PatternMatch::m_c_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
Definition: PatternMatch.h:2244
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:271
isSigned
static bool isSigned(unsigned int Opcode)
Definition: ExpandLargeDivRem.cpp:52
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
Dominators.h
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5435
CreateMul
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:253
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
llvm::DivRemMapKey
Definition: BypassSlowDivision.h:30
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:142
TargetTransformInfo.h
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.h:119
llvm::PatternMatch
Definition: PatternMatch.h:47
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:98
llvm::DivRemPairsPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Definition: DivRemPairs.cpp:434
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
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:107
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941