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  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  // 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, nullptr, 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, nullptr, 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:77
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:763
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:937
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:785
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:249
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:367
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:246
bool hasDivRemOp(Type *DataType, bool IsSigned) const
Return true if the target has a unified operation to calculate division and remainder.
static SmallVector< std::pair< int64_t, Value * >, 4 > decompose(Value *V)
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:511
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:151
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:155
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:724
FunctionPass * createDivRemPairsPass()
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
bool dominates(const Value *Def, const Use &U) const
Return true if value Def dominates use U, in the sense that Def is available at U, and could be substituted as the used value without violating the SSA dominance requirement.
Definition: Dominators.cpp:260
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:161
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:737
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:960
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:116
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:191
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:295
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:89
#define I(x, y, z)
Definition: MD5.cpp:59
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:75
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:278
This pass exposes codegen information to IR-level passes.
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
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...
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:691
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)