LLVM  12.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  Instruction *DivInst = DivMap[RemPair.first];
155  if (!DivInst)
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(DivInst, 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  // FIXME: We could hoist both ops to the common predecessor block?
242  continue;
243  }
244 
245  // The target does not have a single div/rem operation,
246  // and the rem is already in expanded form. Nothing to do.
247  if (!HasDivRemOp && E.isRemExpanded())
248  continue;
249 
250  if (HasDivRemOp) {
251  // The target has a single div/rem operation. Hoist the lower instruction
252  // to make the matched pair visible to the backend.
253  if (DivDominates)
254  RemInst->moveAfter(DivInst);
255  else
256  DivInst->moveAfter(RemInst);
257  NumHoisted++;
258  } else {
259  // The target does not have a single div/rem operation,
260  // and the rem is *not* in a already-expanded form.
261  // Decompose the remainder calculation as:
262  // X % Y --> X - ((X / Y) * Y).
263 
264  assert(!RemOriginallyWasInExpandedForm &&
265  "We should not be expanding if the rem was in expanded form to "
266  "begin with.");
267 
268  Value *X = E.getDividend();
269  Value *Y = E.getDivisor();
270  Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y);
271  Instruction *Sub = BinaryOperator::CreateSub(X, Mul);
272 
273  // If the remainder dominates, then hoist the division up to that block:
274  //
275  // bb1:
276  // %rem = srem %x, %y
277  // bb2:
278  // %div = sdiv %x, %y
279  // -->
280  // bb1:
281  // %div = sdiv %x, %y
282  // %mul = mul %div, %y
283  // %rem = sub %x, %mul
284  //
285  // If the division dominates, it's already in the right place. The mul+sub
286  // will be in a different block because we don't assume that they are
287  // cheap to speculatively execute:
288  //
289  // bb1:
290  // %div = sdiv %x, %y
291  // bb2:
292  // %rem = srem %x, %y
293  // -->
294  // bb1:
295  // %div = sdiv %x, %y
296  // bb2:
297  // %mul = mul %div, %y
298  // %rem = sub %x, %mul
299  //
300  // If the div and rem are in the same block, we do the same transform,
301  // but any code movement would be within the same block.
302 
303  if (!DivDominates)
304  DivInst->moveBefore(RemInst);
305  Mul->insertAfter(RemInst);
306  Sub->insertAfter(Mul);
307 
308  // If X can be undef, X should be frozen first.
309  // For example, let's assume that Y = 1 & X = undef:
310  // %div = sdiv undef, 1 // %div = undef
311  // %rem = srem undef, 1 // %rem = 0
312  // =>
313  // %div = sdiv undef, 1 // %div = undef
314  // %mul = mul %div, 1 // %mul = undef
315  // %rem = sub %x, %mul // %rem = undef - undef = undef
316  // If X is not frozen, %rem becomes undef after transformation.
317  // TODO: We need a undef-specific checking function in ValueTracking
318  if (!isGuaranteedNotToBeUndefOrPoison(X, DivInst, &DT)) {
319  auto *FrX = new FreezeInst(X, X->getName() + ".frozen", DivInst);
320  DivInst->setOperand(0, FrX);
321  Sub->setOperand(0, FrX);
322  }
323  // Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0,
324  // but %rem in tgt can be one of many integer values.
325  if (!isGuaranteedNotToBeUndefOrPoison(Y, DivInst, &DT)) {
326  auto *FrY = new FreezeInst(Y, Y->getName() + ".frozen", DivInst);
327  DivInst->setOperand(1, FrY);
328  Mul->setOperand(1, FrY);
329  }
330 
331  // Now kill the explicit remainder. We have replaced it with:
332  // (sub X, (mul (div X, Y), Y)
333  Sub->setName(RemInst->getName() + ".decomposed");
334  Instruction *OrigRemInst = RemInst;
335  // Update AssertingVH<> with new instruction so it doesn't assert.
336  RemInst = Sub;
337  // And replace the original instruction with the new one.
338  OrigRemInst->replaceAllUsesWith(Sub);
339  OrigRemInst->eraseFromParent();
340  NumDecomposed++;
341  }
342  Changed = true;
343  }
344 
345  return Changed;
346 }
347 
348 // Pass manager boilerplate below here.
349 
350 namespace {
351 struct DivRemPairsLegacyPass : public FunctionPass {
352  static char ID;
353  DivRemPairsLegacyPass() : FunctionPass(ID) {
355  }
356 
357  void getAnalysisUsage(AnalysisUsage &AU) const override {
360  AU.setPreservesCFG();
364  }
365 
366  bool runOnFunction(Function &F) override {
367  if (skipFunction(F))
368  return false;
369  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
370  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
371  return optimizeDivRem(F, TTI, DT);
372  }
373 };
374 } // namespace
375 
377 INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs",
378  "Hoist/decompose integer division and remainder", false,
379  false)
381 INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs",
382  "Hoist/decompose integer division and remainder", false,
383  false)
385  return new DivRemPairsLegacyPass();
386 }
387 
392  if (!optimizeDivRem(F, TTI, DT))
393  return PreservedAnalyses::all();
394  // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
396  PA.preserveSet<CFGAnalyses>();
397  PA.preserve<GlobalsAA>();
398  return PA;
399 }
Legacy wrapper pass to provide the GlobalsAAResult object.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:80
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:687
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:852
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, and signedness).
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
Analysis pass providing the TargetTransformInfo.
void initializeDivRemPairsLegacyPassPass(PassRegistry &)
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:37
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:233
F(f)
INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs", "Hoist/decompose integer division and remainder", false, false) INITIALIZE_PASS_END(DivRemPairsLegacyPass
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:342
This file provides an implementation of debug counters.
div rem Hoist decompose integer division and remainder
Key
PAL metadata keys.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
div rem pairs
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
bool hasDivRemOp(Type *DataType, bool IsSigned) const
Return true if the target has a unified operation to calculate division and remainder.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:486
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
static bool runOnFunction(Function &F, bool PostInlining)
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static DivRemWorklistTy getWorklist(Function &F)
Find matching pairs of integer div/rem ops (they have the same numerator, denominator, and signedness).
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:648
FunctionPass * createDivRemPairsPass()
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
BinOpPred_match< LHS, RHS, is_idiv_op > m_IDiv(const LHS &L, const RHS &R)
Matches integer division operations.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
static wasm::ValType getType(const TargetRegisterClass *RC)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
deferredval_ty< Value > m_Deferred(Value *const &V)
A commutative-friendly version of m_Specific().
Definition: PatternMatch.h:661
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:251
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
This class represents a freeze function that returns random concrete value if an operand is either a ...
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.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:115
DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform", "Controls transformations in div-rem-pairs pass")
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:270
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:92
#define I(x, y, z)
Definition: MD5.cpp:59
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V is never undef value or poison value.
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:74
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:159
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:262
This pass exposes codegen information to IR-level passes.
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:615
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)