LLVM 17.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"
25#include "llvm/Pass.h"
29#include <optional>
30
31using namespace llvm;
32using namespace llvm::PatternMatch;
33
34#define DEBUG_TYPE "div-rem-pairs"
35STATISTIC(NumPairs, "Number of div/rem pairs");
36STATISTIC(NumRecomposed, "Number of instructions recomposed");
37STATISTIC(NumHoisted, "Number of instructions hoisted");
38STATISTIC(NumDecomposed, "Number of instructions decomposed");
39DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",
40 "Controls transformations in div-rem-pairs pass");
41
42namespace {
43struct ExpandedMatch {
44 DivRemMapKey Key;
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
53static 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
76namespace {
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.
79struct 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 if (RemBB->getSingleSuccessor() == DivBB) {
271 PredBB = RemBB->getUniquePredecessor();
272
273 // Look for something like this
274 // PredBB
275 // / \
276 // Div Rem
277 //
278 // If the Rem and Din blocks share a unique predecessor, and all
279 // paths from PredBB go to either RemBB or DivBB, and execution of RemBB
280 // and DivBB will always reach the Div/Rem, we can hoist Div to PredBB.
281 // If we have a DivRem operation we can also hoist Rem. By hoisting both
282 // ops to the same block, we reduce code size and allow the DivRem to
283 // issue sooner. Without a DivRem op, this transformation is
284 // unprofitable because we would end up performing an extra Mul+Sub on
285 // the Rem path.
286 } else if (BasicBlock *RemPredBB = RemBB->getUniquePredecessor()) {
287 // This hoist is only profitable when the target has a DivRem op.
288 if (HasDivRemOp && RemPredBB == DivBB->getUniquePredecessor())
289 PredBB = RemPredBB;
290 }
291 // FIXME: We could handle more hoisting cases.
292
293 if (PredBB && !isa<CatchSwitchInst>(PredBB->getTerminator()) &&
295 IsSafeToHoist(RemInst, RemBB) && IsSafeToHoist(DivInst, DivBB) &&
296 all_of(successors(PredBB),
297 [&](BasicBlock *BB) { return BB == DivBB || BB == RemBB; }) &&
298 all_of(predecessors(DivBB),
299 [&](BasicBlock *BB) { return BB == RemBB || BB == PredBB; })) {
300 DivDominates = true;
301 DivInst->moveBefore(PredBB->getTerminator());
302 Changed = true;
303 if (HasDivRemOp) {
304 RemInst->moveBefore(PredBB->getTerminator());
305 continue;
306 }
307 } else
308 continue;
309 }
310
311 // The target does not have a single div/rem operation,
312 // and the rem is already in expanded form. Nothing to do.
313 if (!HasDivRemOp && E.isRemExpanded())
314 continue;
315
316 if (HasDivRemOp) {
317 // The target has a single div/rem operation. Hoist the lower instruction
318 // to make the matched pair visible to the backend.
319 if (DivDominates)
320 RemInst->moveAfter(DivInst);
321 else
322 DivInst->moveAfter(RemInst);
323 NumHoisted++;
324 } else {
325 // The target does not have a single div/rem operation,
326 // and the rem is *not* in a already-expanded form.
327 // Decompose the remainder calculation as:
328 // X % Y --> X - ((X / Y) * Y).
329
330 assert(!RemOriginallyWasInExpandedForm &&
331 "We should not be expanding if the rem was in expanded form to "
332 "begin with.");
333
334 Value *X = E.getDividend();
335 Value *Y = E.getDivisor();
336 Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y);
337 Instruction *Sub = BinaryOperator::CreateSub(X, Mul);
338
339 // If the remainder dominates, then hoist the division up to that block:
340 //
341 // bb1:
342 // %rem = srem %x, %y
343 // bb2:
344 // %div = sdiv %x, %y
345 // -->
346 // bb1:
347 // %div = sdiv %x, %y
348 // %mul = mul %div, %y
349 // %rem = sub %x, %mul
350 //
351 // If the division dominates, it's already in the right place. The mul+sub
352 // will be in a different block because we don't assume that they are
353 // cheap to speculatively execute:
354 //
355 // bb1:
356 // %div = sdiv %x, %y
357 // bb2:
358 // %rem = srem %x, %y
359 // -->
360 // bb1:
361 // %div = sdiv %x, %y
362 // bb2:
363 // %mul = mul %div, %y
364 // %rem = sub %x, %mul
365 //
366 // If the div and rem are in the same block, we do the same transform,
367 // but any code movement would be within the same block.
368
369 if (!DivDominates)
370 DivInst->moveBefore(RemInst);
371 Mul->insertAfter(RemInst);
372 Sub->insertAfter(Mul);
373
374 // If DivInst has the exact flag, remove it. Otherwise this optimization
375 // may replace a well-defined value 'X % Y' with poison.
376 DivInst->dropPoisonGeneratingFlags();
377
378 // If X can be undef, X should be frozen first.
379 // For example, let's assume that Y = 1 & X = undef:
380 // %div = sdiv undef, 1 // %div = undef
381 // %rem = srem undef, 1 // %rem = 0
382 // =>
383 // %div = sdiv undef, 1 // %div = undef
384 // %mul = mul %div, 1 // %mul = undef
385 // %rem = sub %x, %mul // %rem = undef - undef = undef
386 // If X is not frozen, %rem becomes undef after transformation.
387 // TODO: We need a undef-specific checking function in ValueTracking
388 if (!isGuaranteedNotToBeUndefOrPoison(X, nullptr, DivInst, &DT)) {
389 auto *FrX = new FreezeInst(X, X->getName() + ".frozen", DivInst);
390 DivInst->setOperand(0, FrX);
391 Sub->setOperand(0, FrX);
392 }
393 // Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0,
394 // but %rem in tgt can be one of many integer values.
395 if (!isGuaranteedNotToBeUndefOrPoison(Y, nullptr, DivInst, &DT)) {
396 auto *FrY = new FreezeInst(Y, Y->getName() + ".frozen", DivInst);
397 DivInst->setOperand(1, FrY);
398 Mul->setOperand(1, FrY);
399 }
400
401 // Now kill the explicit remainder. We have replaced it with:
402 // (sub X, (mul (div X, Y), Y)
403 Sub->setName(RemInst->getName() + ".decomposed");
404 Instruction *OrigRemInst = RemInst;
405 // Update AssertingVH<> with new instruction so it doesn't assert.
406 RemInst = Sub;
407 // And replace the original instruction with the new one.
408 OrigRemInst->replaceAllUsesWith(Sub);
409 OrigRemInst->eraseFromParent();
410 NumDecomposed++;
411 }
412 Changed = true;
413 }
414
415 return Changed;
416}
417
418// Pass manager boilerplate below here.
419
424 if (!optimizeDivRem(F, TTI, DT))
425 return PreservedAnalyses::all();
426 // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
429 return PA;
430}
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
Definition: DebugCounter.h:182
This file defines the DenseMap class.
static DivRemWorklistTy getWorklist(Function &F)
Find matching pairs of integer div/rem ops (they have the same numerator, denominator,...
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,...
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
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This is the interface for a simple mod/ref and alias analysis over globals.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
FunctionAnalysisManager FAM
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
static SymbolRef::Type getType(const Symbol *Sym)
Definition: TapiFile.cpp:40
This pass exposes codegen information to IR-level passes.
BinaryOperator * Mul
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:264
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:301
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:323
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:127
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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
This class represents a freeze function that returns random concrete value if an operand is either a ...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:94
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool hasDivRemOp(Type *DataType, bool IsSigned) const
Return true if the target has a unified operation to calculate division and remainder.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
LLVM Value Representation.
Definition: Value.h:74
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
self_iterator getIterator()
Definition: ilist_node.h:82
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
BinOpPred_match< LHS, RHS, is_idiv_op > m_IDiv(const LHS &L, const RHS &R)
Matches integer division operations.
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:716
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:224
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
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
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.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:991
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1819
auto successors(const MachineBasicBlock *BB)
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.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto predecessors(const MachineBasicBlock *BB)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)