LLVM  14.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 
30 using namespace llvm;
31 using namespace llvm::PatternMatch;
32 
33 #define DEBUG_TYPE "div-rem-pairs"
34 STATISTIC(NumPairs, "Number of div/rem pairs");
35 STATISTIC(NumRecomposed, "Number of instructions recomposed");
36 STATISTIC(NumHoisted, "Number of instructions hoisted");
37 STATISTIC(NumDecomposed, "Number of instructions decomposed");
38 DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",
39  "Controls transformations in div-rem-pairs pass");
40 
41 namespace {
42 struct ExpandedMatch {
45 };
46 } // namespace
47 
48 /// See if we can match: (which is the form we expand into)
49 /// X - ((X ?/ Y) * Y)
50 /// which is equivalent to:
51 /// X ?% Y
53  Value *Dividend, *XroundedDownToMultipleOfY;
54  if (!match(&I, m_Sub(m_Value(Dividend), m_Value(XroundedDownToMultipleOfY))))
55  return llvm::None;
56 
57  Value *Divisor;
58  Instruction *Div;
59  // Look for ((X / Y) * Y)
60  if (!match(
61  XroundedDownToMultipleOfY,
62  m_c_Mul(m_CombineAnd(m_IDiv(m_Specific(Dividend), m_Value(Divisor)),
63  m_Instruction(Div)),
64  m_Deferred(Divisor))))
65  return llvm::None;
66 
67  ExpandedMatch M;
68  M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv;
69  M.Key.Dividend = Dividend;
70  M.Key.Divisor = Divisor;
71  M.Value = &I;
72  return M;
73 }
74 
75 namespace {
76 /// A thin wrapper to store two values that we matched as div-rem pair.
77 /// We want this extra indirection to avoid dealing with RAUW'ing the map keys.
78 struct DivRemPairWorklistEntry {
79  /// The actual udiv/sdiv instruction. Source of truth.
81 
82  /// The instruction that we have matched as a remainder instruction.
83  /// Should only be used as Value, don't introspect it.
85 
86  DivRemPairWorklistEntry(Instruction *DivInst_, Instruction *RemInst_)
87  : DivInst(DivInst_), RemInst(RemInst_) {
88  assert((DivInst->getOpcode() == Instruction::UDiv ||
89  DivInst->getOpcode() == Instruction::SDiv) &&
90  "Not a division.");
91  assert(DivInst->getType() == RemInst->getType() && "Types should match.");
92  // We can't check anything else about remainder instruction,
93  // it's not strictly required to be a urem/srem.
94  }
95 
96  /// The type for this pair, identical for both the div and rem.
97  Type *getType() const { return DivInst->getType(); }
98 
99  /// Is this pair signed or unsigned?
100  bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; }
101 
102  /// In this pair, what are the divident and divisor?
103  Value *getDividend() const { return DivInst->getOperand(0); }
104  Value *getDivisor() const { return DivInst->getOperand(1); }
105 
106  bool isRemExpanded() const {
107  switch (RemInst->getOpcode()) {
108  case Instruction::SRem:
109  case Instruction::URem:
110  return false; // single 'rem' instruction - unexpanded form.
111  default:
112  return true; // anything else means we have remainder in expanded form.
113  }
114  }
115 };
116 } // namespace
118 
119 /// Find matching pairs of integer div/rem ops (they have the same numerator,
120 /// denominator, and signedness). Place those pairs into a worklist for further
121 /// processing. This indirection is needed because we have to use TrackingVH<>
122 /// because we will be doing RAUW, and if one of the rem instructions we change
123 /// happens to be an input to another div/rem in the maps, we'd have problems.
125  // Insert all divide and remainder instructions into maps keyed by their
126  // operands and opcode (signed or unsigned).
128  // Use a MapVector for RemMap so that instructions are moved/inserted in a
129  // deterministic order.
131  for (auto &BB : F) {
132  for (auto &I : BB) {
133  if (I.getOpcode() == Instruction::SDiv)
134  DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
135  else if (I.getOpcode() == Instruction::UDiv)
136  DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
137  else if (I.getOpcode() == Instruction::SRem)
138  RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
139  else if (I.getOpcode() == Instruction::URem)
140  RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
141  else if (auto Match = matchExpandedRem(I))
142  RemMap[Match->Key] = Match->Value;
143  }
144  }
145 
146  // We'll accumulate the matching pairs of div-rem instructions here.
147  DivRemWorklistTy Worklist;
148 
149  // We can iterate over either map because we are only looking for matched
150  // pairs. Choose remainders for efficiency because they are usually even more
151  // rare than division.
152  for (auto &RemPair : RemMap) {
153  // Find the matching division instruction from the division map.
154  auto It = DivMap.find(RemPair.first);
155  if (It == DivMap.end())
156  continue;
157 
158  // We have a matching pair of div/rem instructions.
159  NumPairs++;
160  Instruction *RemInst = RemPair.second;
161 
162  // Place it in the worklist.
163  Worklist.emplace_back(It->second, RemInst);
164  }
165 
166  return Worklist;
167 }
168 
169 /// Find matching pairs of integer div/rem ops (they have the same numerator,
170 /// denominator, and signedness). If they exist in different basic blocks, bring
171 /// them together by hoisting or replace the common division operation that is
172 /// implicit in the remainder:
173 /// X % Y <--> X - ((X / Y) * Y).
174 ///
175 /// We can largely ignore the normal safety and cost constraints on speculation
176 /// of these ops when we find a matching pair. This is because we are already
177 /// guaranteed that any exceptions and most cost are already incurred by the
178 /// first member of the pair.
179 ///
180 /// Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or
181 /// SimplifyCFG, but it's split off on its own because it's different enough
182 /// that it doesn't quite match the stated objectives of those passes.
184  const DominatorTree &DT) {
185  bool Changed = false;
186 
187  // Get the matching pairs of div-rem instructions. We want this extra
188  // indirection to avoid dealing with having to RAUW the keys of the maps.
189  DivRemWorklistTy Worklist = getWorklist(F);
190 
191  // Process each entry in the worklist.
192  for (DivRemPairWorklistEntry &E : Worklist) {
193  if (!DebugCounter::shouldExecute(DRPCounter))
194  continue;
195 
196  bool HasDivRemOp = TTI.hasDivRemOp(E.getType(), E.isSigned());
197 
198  auto &DivInst = E.DivInst;
199  auto &RemInst = E.RemInst;
200 
201  const bool RemOriginallyWasInExpandedForm = E.isRemExpanded();
202  (void)RemOriginallyWasInExpandedForm; // suppress unused variable warning
203 
204  if (HasDivRemOp && E.isRemExpanded()) {
205  // The target supports div+rem but the rem is expanded.
206  // We should recompose it first.
207  Value *X = E.getDividend();
208  Value *Y = E.getDivisor();
209  Instruction *RealRem = E.isSigned() ? BinaryOperator::CreateSRem(X, Y)
210  : BinaryOperator::CreateURem(X, Y);
211  // Note that we place it right next to the original expanded instruction,
212  // and letting further handling to move it if needed.
213  RealRem->setName(RemInst->getName() + ".recomposed");
214  RealRem->insertAfter(RemInst);
215  Instruction *OrigRemInst = RemInst;
216  // Update AssertingVH<> with new instruction so it doesn't assert.
217  RemInst = RealRem;
218  // And replace the original instruction with the new one.
219  OrigRemInst->replaceAllUsesWith(RealRem);
220  OrigRemInst->eraseFromParent();
221  NumRecomposed++;
222  // Note that we have left ((X / Y) * Y) around.
223  // If it had other uses we could rewrite it as X - X % Y
224  Changed = true;
225  }
226 
227  assert((!E.isRemExpanded() || !HasDivRemOp) &&
228  "*If* the target supports div-rem, then by now the RemInst *is* "
229  "Instruction::[US]Rem.");
230 
231  // If the target supports div+rem and the instructions are in the same block
232  // already, there's nothing to do. The backend should handle this. If the
233  // target does not support div+rem, then we will decompose the rem.
234  if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())
235  continue;
236 
237  bool DivDominates = DT.dominates(DivInst, RemInst);
238  if (!DivDominates && !DT.dominates(RemInst, DivInst)) {
239  // We have matching div-rem pair, but they are in two different blocks,
240  // neither of which dominates one another.
241 
242  BasicBlock *PredBB = nullptr;
243  BasicBlock *DivBB = DivInst->getParent();
244  BasicBlock *RemBB = RemInst->getParent();
245 
246  // It's only safe to hoist if every instruction before the Div/Rem in the
247  // basic block is guaranteed to transfer execution.
248  auto IsSafeToHoist = [](Instruction *DivOrRem, BasicBlock *ParentBB) {
249  for (auto I = ParentBB->begin(), E = DivOrRem->getIterator(); I != E;
250  ++I)
252  return false;
253 
254  return true;
255  };
256 
257  // Look for something like this
258  // PredBB
259  // | \
260  // | Rem
261  // | /
262  // Div
263  //
264  // If the Rem block has a single predecessor and successor, and all paths
265  // from PredBB go to either RemBB or DivBB, and execution of RemBB and
266  // DivBB will always reach the Div/Rem, we can hoist Div to PredBB. If
267  // we have a DivRem operation we can also hoist Rem. Otherwise we'll leave
268  // Rem where it is and rewrite it to mul/sub.
269  // FIXME: We could handle more hoisting cases.
270  if (RemBB->getSingleSuccessor() == DivBB)
271  PredBB = RemBB->getUniquePredecessor();
272 
273  if (PredBB && IsSafeToHoist(RemInst, RemBB) &&
274  IsSafeToHoist(DivInst, DivBB) &&
275  all_of(successors(PredBB),
276  [&](BasicBlock *BB) { return BB == DivBB || BB == RemBB; }) &&
277  all_of(predecessors(DivBB),
278  [&](BasicBlock *BB) { return BB == RemBB || BB == PredBB; })) {
279  DivDominates = true;
280  DivInst->moveBefore(PredBB->getTerminator());
281  Changed = true;
282  if (HasDivRemOp) {
283  RemInst->moveBefore(PredBB->getTerminator());
284  continue;
285  }
286  } else
287  continue;
288  }
289 
290  // The target does not have a single div/rem operation,
291  // and the rem is already in expanded form. Nothing to do.
292  if (!HasDivRemOp && E.isRemExpanded())
293  continue;
294 
295  if (HasDivRemOp) {
296  // The target has a single div/rem operation. Hoist the lower instruction
297  // to make the matched pair visible to the backend.
298  if (DivDominates)
299  RemInst->moveAfter(DivInst);
300  else
301  DivInst->moveAfter(RemInst);
302  NumHoisted++;
303  } else {
304  // The target does not have a single div/rem operation,
305  // and the rem is *not* in a already-expanded form.
306  // Decompose the remainder calculation as:
307  // X % Y --> X - ((X / Y) * Y).
308 
309  assert(!RemOriginallyWasInExpandedForm &&
310  "We should not be expanding if the rem was in expanded form to "
311  "begin with.");
312 
313  Value *X = E.getDividend();
314  Value *Y = E.getDivisor();
316  Instruction *Sub = BinaryOperator::CreateSub(X, Mul);
317 
318  // If the remainder dominates, then hoist the division up to that block:
319  //
320  // bb1:
321  // %rem = srem %x, %y
322  // bb2:
323  // %div = sdiv %x, %y
324  // -->
325  // bb1:
326  // %div = sdiv %x, %y
327  // %mul = mul %div, %y
328  // %rem = sub %x, %mul
329  //
330  // If the division dominates, it's already in the right place. The mul+sub
331  // will be in a different block because we don't assume that they are
332  // cheap to speculatively execute:
333  //
334  // bb1:
335  // %div = sdiv %x, %y
336  // bb2:
337  // %rem = srem %x, %y
338  // -->
339  // bb1:
340  // %div = sdiv %x, %y
341  // bb2:
342  // %mul = mul %div, %y
343  // %rem = sub %x, %mul
344  //
345  // If the div and rem are in the same block, we do the same transform,
346  // but any code movement would be within the same block.
347 
348  if (!DivDominates)
349  DivInst->moveBefore(RemInst);
350  Mul->insertAfter(RemInst);
351  Sub->insertAfter(Mul);
352 
353  // If X can be undef, X should be frozen first.
354  // For example, let's assume that Y = 1 & X = undef:
355  // %div = sdiv undef, 1 // %div = undef
356  // %rem = srem undef, 1 // %rem = 0
357  // =>
358  // %div = sdiv undef, 1 // %div = undef
359  // %mul = mul %div, 1 // %mul = undef
360  // %rem = sub %x, %mul // %rem = undef - undef = undef
361  // If X is not frozen, %rem becomes undef after transformation.
362  // TODO: We need a undef-specific checking function in ValueTracking
363  if (!isGuaranteedNotToBeUndefOrPoison(X, nullptr, DivInst, &DT)) {
364  auto *FrX = new FreezeInst(X, X->getName() + ".frozen", DivInst);
365  DivInst->setOperand(0, FrX);
366  Sub->setOperand(0, FrX);
367  }
368  // Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0,
369  // but %rem in tgt can be one of many integer values.
370  if (!isGuaranteedNotToBeUndefOrPoison(Y, nullptr, DivInst, &DT)) {
371  auto *FrY = new FreezeInst(Y, Y->getName() + ".frozen", DivInst);
372  DivInst->setOperand(1, FrY);
373  Mul->setOperand(1, FrY);
374  }
375 
376  // Now kill the explicit remainder. We have replaced it with:
377  // (sub X, (mul (div X, Y), Y)
378  Sub->setName(RemInst->getName() + ".decomposed");
379  Instruction *OrigRemInst = RemInst;
380  // Update AssertingVH<> with new instruction so it doesn't assert.
381  RemInst = Sub;
382  // And replace the original instruction with the new one.
383  OrigRemInst->replaceAllUsesWith(Sub);
384  OrigRemInst->eraseFromParent();
385  NumDecomposed++;
386  }
387  Changed = true;
388  }
389 
390  return Changed;
391 }
392 
393 // Pass manager boilerplate below here.
394 
395 namespace {
396 struct DivRemPairsLegacyPass : public FunctionPass {
397  static char ID;
398  DivRemPairsLegacyPass() : FunctionPass(ID) {
400  }
401 
402  void getAnalysisUsage(AnalysisUsage &AU) const override {
405  AU.setPreservesCFG();
409  }
410 
411  bool runOnFunction(Function &F) override {
412  if (skipFunction(F))
413  return false;
414  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
415  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
416  return optimizeDivRem(F, TTI, DT);
417  }
418 };
419 } // namespace
420 
422 INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs",
423  "Hoist/decompose integer division and remainder", false,
424  false)
426 INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs",
427  "Hoist/decompose integer division and remainder", false,
428  false)
430  return new DivRemPairsLegacyPass();
431 }
432 
437  if (!optimizeDivRem(F, TTI, DT))
438  return PreservedAnalyses::all();
439  // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
441  PA.preserveSet<CFGAnalyses>();
442  return PA;
443 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2331
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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::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::Function
Definition: Function.h:61
Pass.h
decompose
static SmallVector< std::pair< int64_t, Value * >, 4 > decompose(Value *V)
Definition: ConstraintElimination.cpp:50
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:5262
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:183
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
MapVector.h
DivRemPairs.h
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:294
llvm::Optional
Definition: APInt.h:33
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::DiagnosticPredicateTy::Match
@ Match
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
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:820
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
remainder
div rem Hoist decompose integer division and remainder
Definition: DivRemPairs.cpp:427
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:115
llvm::createDivRemPairsPass
FunctionPass * createDivRemPairsPass()
Definition: DivRemPairs.cpp:429
llvm::Intrinsic::getType
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
Definition: Function.cpp:1335
llvm::Instruction::insertAfter
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:90
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
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:1551
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
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:481
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:748
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
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:1334
pairs
div rem pairs
Definition: DivRemPairs.cpp:426
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:376
PatternMatch.h
llvm::None
const NoneType None
Definition: None.h:23
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:78
BypassSlowDivision.h
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2387
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:124
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:101
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:1020
matchExpandedRem
static llvm::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:52
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
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:216
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:272
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:81
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:418
llvm::RecurKind::Mul
@ Mul
Product of integers.
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
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::initializeDivRemPairsLegacyPassPass
void initializeDivRemPairsLegacyPassPass(PassRegistry &)
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
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:83
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
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:5293
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:2235
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:802
Dominators.h
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5360
CreateMul
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:246
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:94
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
TargetTransformInfo.h
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:93
llvm::DivRemPairsPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Definition: DivRemPairs.cpp:433
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
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:75
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::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37