LLVM 19.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"
26#include <optional>
27
28using namespace llvm;
29using namespace llvm::PatternMatch;
30
31#define DEBUG_TYPE "div-rem-pairs"
32STATISTIC(NumPairs, "Number of div/rem pairs");
33STATISTIC(NumRecomposed, "Number of instructions recomposed");
34STATISTIC(NumHoisted, "Number of instructions hoisted");
35STATISTIC(NumDecomposed, "Number of instructions decomposed");
36DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",
37 "Controls transformations in div-rem-pairs pass");
38
39namespace {
40struct ExpandedMatch {
41 DivRemMapKey Key;
43};
44} // namespace
45
46/// See if we can match: (which is the form we expand into)
47/// X - ((X ?/ Y) * Y)
48/// which is equivalent to:
49/// X ?% Y
50static std::optional<ExpandedMatch> matchExpandedRem(Instruction &I) {
51 Value *Dividend, *XroundedDownToMultipleOfY;
52 if (!match(&I, m_Sub(m_Value(Dividend), m_Value(XroundedDownToMultipleOfY))))
53 return std::nullopt;
54
55 Value *Divisor;
56 Instruction *Div;
57 // Look for ((X / Y) * Y)
58 if (!match(
59 XroundedDownToMultipleOfY,
60 m_c_Mul(m_CombineAnd(m_IDiv(m_Specific(Dividend), m_Value(Divisor)),
61 m_Instruction(Div)),
62 m_Deferred(Divisor))))
63 return std::nullopt;
64
65 ExpandedMatch M;
66 M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv;
67 M.Key.Dividend = Dividend;
68 M.Key.Divisor = Divisor;
69 M.Value = &I;
70 return M;
71}
72
73namespace {
74/// A thin wrapper to store two values that we matched as div-rem pair.
75/// We want this extra indirection to avoid dealing with RAUW'ing the map keys.
76struct DivRemPairWorklistEntry {
77 /// The actual udiv/sdiv instruction. Source of truth.
79
80 /// The instruction that we have matched as a remainder instruction.
81 /// Should only be used as Value, don't introspect it.
83
84 DivRemPairWorklistEntry(Instruction *DivInst_, Instruction *RemInst_)
85 : DivInst(DivInst_), RemInst(RemInst_) {
86 assert((DivInst->getOpcode() == Instruction::UDiv ||
87 DivInst->getOpcode() == Instruction::SDiv) &&
88 "Not a division.");
89 assert(DivInst->getType() == RemInst->getType() && "Types should match.");
90 // We can't check anything else about remainder instruction,
91 // it's not strictly required to be a urem/srem.
92 }
93
94 /// The type for this pair, identical for both the div and rem.
95 Type *getType() const { return DivInst->getType(); }
96
97 /// Is this pair signed or unsigned?
98 bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; }
99
100 /// In this pair, what are the divident and divisor?
101 Value *getDividend() const { return DivInst->getOperand(0); }
102 Value *getDivisor() const { return DivInst->getOperand(1); }
103
104 bool isRemExpanded() const {
105 switch (RemInst->getOpcode()) {
106 case Instruction::SRem:
107 case Instruction::URem:
108 return false; // single 'rem' instruction - unexpanded form.
109 default:
110 return true; // anything else means we have remainder in expanded form.
111 }
112 }
113};
114} // namespace
116
117/// Find matching pairs of integer div/rem ops (they have the same numerator,
118/// denominator, and signedness). Place those pairs into a worklist for further
119/// processing. This indirection is needed because we have to use TrackingVH<>
120/// because we will be doing RAUW, and if one of the rem instructions we change
121/// happens to be an input to another div/rem in the maps, we'd have problems.
123 // Insert all divide and remainder instructions into maps keyed by their
124 // operands and opcode (signed or unsigned).
126 // Use a MapVector for RemMap so that instructions are moved/inserted in a
127 // deterministic order.
129 for (auto &BB : F) {
130 for (auto &I : BB) {
131 if (I.getOpcode() == Instruction::SDiv)
132 DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
133 else if (I.getOpcode() == Instruction::UDiv)
134 DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
135 else if (I.getOpcode() == Instruction::SRem)
136 RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
137 else if (I.getOpcode() == Instruction::URem)
138 RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
139 else if (auto Match = matchExpandedRem(I))
140 RemMap[Match->Key] = Match->Value;
141 }
142 }
143
144 // We'll accumulate the matching pairs of div-rem instructions here.
145 DivRemWorklistTy Worklist;
146
147 // We can iterate over either map because we are only looking for matched
148 // pairs. Choose remainders for efficiency because they are usually even more
149 // rare than division.
150 for (auto &RemPair : RemMap) {
151 // Find the matching division instruction from the division map.
152 auto It = DivMap.find(RemPair.first);
153 if (It == DivMap.end())
154 continue;
155
156 // We have a matching pair of div/rem instructions.
157 NumPairs++;
158 Instruction *RemInst = RemPair.second;
159
160 // Place it in the worklist.
161 Worklist.emplace_back(It->second, RemInst);
162 }
163
164 return Worklist;
165}
166
167/// Find matching pairs of integer div/rem ops (they have the same numerator,
168/// denominator, and signedness). If they exist in different basic blocks, bring
169/// them together by hoisting or replace the common division operation that is
170/// implicit in the remainder:
171/// X % Y <--> X - ((X / Y) * Y).
172///
173/// We can largely ignore the normal safety and cost constraints on speculation
174/// of these ops when we find a matching pair. This is because we are already
175/// guaranteed that any exceptions and most cost are already incurred by the
176/// first member of the pair.
177///
178/// Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or
179/// SimplifyCFG, but it's split off on its own because it's different enough
180/// that it doesn't quite match the stated objectives of those passes.
182 const DominatorTree &DT) {
183 bool Changed = false;
184
185 // Get the matching pairs of div-rem instructions. We want this extra
186 // indirection to avoid dealing with having to RAUW the keys of the maps.
187 DivRemWorklistTy Worklist = getWorklist(F);
188
189 // Process each entry in the worklist.
190 for (DivRemPairWorklistEntry &E : Worklist) {
191 if (!DebugCounter::shouldExecute(DRPCounter))
192 continue;
193
194 bool HasDivRemOp = TTI.hasDivRemOp(E.getType(), E.isSigned());
195
196 auto &DivInst = E.DivInst;
197 auto &RemInst = E.RemInst;
198
199 const bool RemOriginallyWasInExpandedForm = E.isRemExpanded();
200 (void)RemOriginallyWasInExpandedForm; // suppress unused variable warning
201
202 if (HasDivRemOp && E.isRemExpanded()) {
203 // The target supports div+rem but the rem is expanded.
204 // We should recompose it first.
205 Value *X = E.getDividend();
206 Value *Y = E.getDivisor();
207 Instruction *RealRem = E.isSigned() ? BinaryOperator::CreateSRem(X, Y)
208 : BinaryOperator::CreateURem(X, Y);
209 // Note that we place it right next to the original expanded instruction,
210 // and letting further handling to move it if needed.
211 RealRem->setName(RemInst->getName() + ".recomposed");
212 RealRem->insertAfter(RemInst);
213 Instruction *OrigRemInst = RemInst;
214 // Update AssertingVH<> with new instruction so it doesn't assert.
215 RemInst = RealRem;
216 // And replace the original instruction with the new one.
217 OrigRemInst->replaceAllUsesWith(RealRem);
218 OrigRemInst->eraseFromParent();
219 NumRecomposed++;
220 // Note that we have left ((X / Y) * Y) around.
221 // If it had other uses we could rewrite it as X - X % Y
222 Changed = true;
223 }
224
225 assert((!E.isRemExpanded() || !HasDivRemOp) &&
226 "*If* the target supports div-rem, then by now the RemInst *is* "
227 "Instruction::[US]Rem.");
228
229 // If the target supports div+rem and the instructions are in the same block
230 // already, there's nothing to do. The backend should handle this. If the
231 // target does not support div+rem, then we will decompose the rem.
232 if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())
233 continue;
234
235 bool DivDominates = DT.dominates(DivInst, RemInst);
236 if (!DivDominates && !DT.dominates(RemInst, DivInst)) {
237 // We have matching div-rem pair, but they are in two different blocks,
238 // neither of which dominates one another.
239
240 BasicBlock *PredBB = nullptr;
241 BasicBlock *DivBB = DivInst->getParent();
242 BasicBlock *RemBB = RemInst->getParent();
243
244 // It's only safe to hoist if every instruction before the Div/Rem in the
245 // basic block is guaranteed to transfer execution.
246 auto IsSafeToHoist = [](Instruction *DivOrRem, BasicBlock *ParentBB) {
247 for (auto I = ParentBB->begin(), E = DivOrRem->getIterator(); I != E;
248 ++I)
250 return false;
251
252 return true;
253 };
254
255 // Look for something like this
256 // PredBB
257 // | \
258 // | Rem
259 // | /
260 // Div
261 //
262 // If the Rem block has a single predecessor and successor, and all paths
263 // from PredBB go to either RemBB or DivBB, and execution of RemBB and
264 // DivBB will always reach the Div/Rem, we can hoist Div to PredBB. If
265 // we have a DivRem operation we can also hoist Rem. Otherwise we'll leave
266 // Rem where it is and rewrite it to mul/sub.
267 if (RemBB->getSingleSuccessor() == DivBB) {
268 PredBB = RemBB->getUniquePredecessor();
269
270 // Look for something like this
271 // PredBB
272 // / \
273 // Div Rem
274 //
275 // If the Rem and Din blocks share a unique predecessor, and all
276 // paths from PredBB go to either RemBB or DivBB, and execution of RemBB
277 // and DivBB will always reach the Div/Rem, we can hoist Div to PredBB.
278 // If we have a DivRem operation we can also hoist Rem. By hoisting both
279 // ops to the same block, we reduce code size and allow the DivRem to
280 // issue sooner. Without a DivRem op, this transformation is
281 // unprofitable because we would end up performing an extra Mul+Sub on
282 // the Rem path.
283 } else if (BasicBlock *RemPredBB = RemBB->getUniquePredecessor()) {
284 // This hoist is only profitable when the target has a DivRem op.
285 if (HasDivRemOp && RemPredBB == DivBB->getUniquePredecessor())
286 PredBB = RemPredBB;
287 }
288 // FIXME: We could handle more hoisting cases.
289
290 if (PredBB && !isa<CatchSwitchInst>(PredBB->getTerminator()) &&
292 IsSafeToHoist(RemInst, RemBB) && IsSafeToHoist(DivInst, DivBB) &&
293 all_of(successors(PredBB),
294 [&](BasicBlock *BB) { return BB == DivBB || BB == RemBB; }) &&
295 all_of(predecessors(DivBB),
296 [&](BasicBlock *BB) { return BB == RemBB || BB == PredBB; })) {
297 DivDominates = true;
298 DivInst->moveBefore(PredBB->getTerminator());
299 Changed = true;
300 if (HasDivRemOp) {
301 RemInst->moveBefore(PredBB->getTerminator());
302 continue;
303 }
304 } else
305 continue;
306 }
307
308 // The target does not have a single div/rem operation,
309 // and the rem is already in expanded form. Nothing to do.
310 if (!HasDivRemOp && E.isRemExpanded())
311 continue;
312
313 if (HasDivRemOp) {
314 // The target has a single div/rem operation. Hoist the lower instruction
315 // to make the matched pair visible to the backend.
316 if (DivDominates)
317 RemInst->moveAfter(DivInst);
318 else
319 DivInst->moveAfter(RemInst);
320 NumHoisted++;
321 } else {
322 // The target does not have a single div/rem operation,
323 // and the rem is *not* in a already-expanded form.
324 // Decompose the remainder calculation as:
325 // X % Y --> X - ((X / Y) * Y).
326
327 assert(!RemOriginallyWasInExpandedForm &&
328 "We should not be expanding if the rem was in expanded form to "
329 "begin with.");
330
331 Value *X = E.getDividend();
332 Value *Y = E.getDivisor();
333 Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y);
334 Instruction *Sub = BinaryOperator::CreateSub(X, Mul);
335
336 // If the remainder dominates, then hoist the division up to that block:
337 //
338 // bb1:
339 // %rem = srem %x, %y
340 // bb2:
341 // %div = sdiv %x, %y
342 // -->
343 // bb1:
344 // %div = sdiv %x, %y
345 // %mul = mul %div, %y
346 // %rem = sub %x, %mul
347 //
348 // If the division dominates, it's already in the right place. The mul+sub
349 // will be in a different block because we don't assume that they are
350 // cheap to speculatively execute:
351 //
352 // bb1:
353 // %div = sdiv %x, %y
354 // bb2:
355 // %rem = srem %x, %y
356 // -->
357 // bb1:
358 // %div = sdiv %x, %y
359 // bb2:
360 // %mul = mul %div, %y
361 // %rem = sub %x, %mul
362 //
363 // If the div and rem are in the same block, we do the same transform,
364 // but any code movement would be within the same block.
365
366 if (!DivDominates)
367 DivInst->moveBefore(RemInst);
368 Mul->insertAfter(RemInst);
369 Sub->insertAfter(Mul);
370
371 // If DivInst has the exact flag, remove it. Otherwise this optimization
372 // may replace a well-defined value 'X % Y' with poison.
373 DivInst->dropPoisonGeneratingFlags();
374
375 // If X can be undef, X should be frozen first.
376 // For example, let's assume that Y = 1 & X = undef:
377 // %div = sdiv undef, 1 // %div = undef
378 // %rem = srem undef, 1 // %rem = 0
379 // =>
380 // %div = sdiv undef, 1 // %div = undef
381 // %mul = mul %div, 1 // %mul = undef
382 // %rem = sub %x, %mul // %rem = undef - undef = undef
383 // If X is not frozen, %rem becomes undef after transformation.
384 // TODO: We need a undef-specific checking function in ValueTracking
385 if (!isGuaranteedNotToBeUndefOrPoison(X, nullptr, DivInst, &DT)) {
386 auto *FrX =
387 new FreezeInst(X, X->getName() + ".frozen", DivInst->getIterator());
388 DivInst->setOperand(0, FrX);
389 Sub->setOperand(0, FrX);
390 }
391 // Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0,
392 // but %rem in tgt can be one of many integer values.
393 if (!isGuaranteedNotToBeUndefOrPoison(Y, nullptr, DivInst, &DT)) {
394 auto *FrY =
395 new FreezeInst(Y, Y->getName() + ".frozen", DivInst->getIterator());
396 DivInst->setOperand(1, FrY);
397 Mul->setOperand(1, FrY);
398 }
399
400 // Now kill the explicit remainder. We have replaced it with:
401 // (sub X, (mul (div X, Y), Y)
402 Sub->setName(RemInst->getName() + ".decomposed");
403 Instruction *OrigRemInst = RemInst;
404 // Update AssertingVH<> with new instruction so it doesn't assert.
405 RemInst = Sub;
406 // And replace the original instruction with the new one.
407 OrigRemInst->replaceAllUsesWith(Sub);
408 OrigRemInst->eraseFromParent();
409 NumDecomposed++;
410 }
411 Changed = true;
412 }
413
414 return Changed;
415}
416
417// Pass manager boilerplate below here.
418
423 if (!optimizeDivRem(F, TTI, DT))
424 return PreservedAnalyses::all();
425 // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
428 return PA;
429}
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:50
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:321
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:264
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:460
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:482
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:221
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
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:162
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 ...
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:252
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:377
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
self_iterator getIterator()
Definition: ilist_node.h:109
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:765
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:821
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:240
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:839
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:92
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)
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:1722
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 &)