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
14#include "llvm/Transforms/Scalar/DivRemPairs.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/MapVector.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/Analysis/GlobalsModRef.h"
19#include "llvm/Analysis/TargetTransformInfo.h"
20#include "llvm/Analysis/ValueTracking.h"
21#include "llvm/IR/Dominators.h"
22#include "llvm/IR/Function.h"
23#include "llvm/IR/PatternMatch.h"
24#include "llvm/Support/DebugCounter.h"
25#include "llvm/Transforms/Utils/BypassSlowDivision.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;
42 Instruction *Value;
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(V: &I, P: m_Sub(L: m_Value(V&: Dividend), R: m_Value(V&: XroundedDownToMultipleOfY))))
53 return std::nullopt;
54
55 Value *Divisor;
56 Instruction *Div;
57 // Look for ((X / Y) * Y)
58 if (!match(
59 V: XroundedDownToMultipleOfY,
60 P: m_c_Mul(L: m_CombineAnd(L: m_IDiv(L: m_Specific(V: Dividend), R: m_Value(V&: Divisor)),
61 R: m_Instruction(I&: Div)),
62 R: m_Deferred(V: 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.
78 AssertingVH<Instruction> DivInst;
79
80 /// The instruction that we have matched as a remainder instruction.
81 /// Should only be used as Value, don't introspect it.
82 AssertingVH<Instruction> RemInst;
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(i: 0); }
102 Value *getDivisor() const { return DivInst->getOperand(i: 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
115using DivRemWorklistTy = SmallVector<DivRemPairWorklistEntry, 4>;
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.
122static DivRemWorklistTy getWorklist(Function &F) {
123 // Insert all divide and remainder instructions into maps keyed by their
124 // operands and opcode (signed or unsigned).
125 DenseMap<DivRemMapKey, Instruction *> DivMap;
126 // Use a MapVector for RemMap so that instructions are moved/inserted in a
127 // deterministic order.
128 MapVector<DivRemMapKey, Instruction *> RemMap;
129 for (auto &BB : F) {
130 for (auto &I : BB) {
131 if (I.getOpcode() == Instruction::SDiv)
132 DivMap[DivRemMapKey(true, I.getOperand(i: 0), I.getOperand(i: 1))] = &I;
133 else if (I.getOpcode() == Instruction::UDiv)
134 DivMap[DivRemMapKey(false, I.getOperand(i: 0), I.getOperand(i: 1))] = &I;
135 else if (I.getOpcode() == Instruction::SRem)
136 RemMap[DivRemMapKey(true, I.getOperand(i: 0), I.getOperand(i: 1))] = &I;
137 else if (I.getOpcode() == Instruction::URem)
138 RemMap[DivRemMapKey(false, I.getOperand(i: 0), I.getOperand(i: 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(Val: 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(Args&: It->second, Args&: 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.
181static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI,
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(CounterName: DRPCounter))
192 continue;
193
194 bool HasDivRemOp = TTI.hasDivRemOp(DataType: E.getType(), IsSigned: 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(V1: X, V2: Y)
208 : BinaryOperator::CreateURem(V1: X, V2: 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(InsertPos: 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(V: 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(Def: DivInst, User: RemInst);
236 if (!DivDominates && !DT.dominates(Def: RemInst, User: 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)
249 if (!isGuaranteedToTransferExecutionToSuccessor(I: &*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>(Val: PredBB->getTerminator()) &&
291 isGuaranteedToTransferExecutionToSuccessor(I: PredBB->getTerminator()) &&
292 IsSafeToHoist(RemInst, RemBB) && IsSafeToHoist(DivInst, DivBB) &&
293 all_of(Range: successors(BB: PredBB),
294 P: [&](BasicBlock *BB) { return BB == DivBB || BB == RemBB; }) &&
295 all_of(Range: predecessors(BB: DivBB),
296 P: [&](BasicBlock *BB) { return BB == RemBB || BB == PredBB; })) {
297 DivDominates = true;
298 DivInst->moveBefore(MovePos: PredBB->getTerminator());
299 Changed = true;
300 if (HasDivRemOp) {
301 RemInst->moveBefore(MovePos: 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(MovePos: DivInst);
318 else
319 DivInst->moveAfter(MovePos: 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(V1: DivInst, V2: Y);
334 Instruction *Sub = BinaryOperator::CreateSub(V1: X, V2: 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(MovePos: RemInst);
368 Mul->insertAfter(InsertPos: RemInst);
369 Sub->insertAfter(InsertPos: 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(V: X, AC: nullptr, CtxI: DivInst, DT: &DT)) {
386 auto *FrX =
387 new FreezeInst(X, X->getName() + ".frozen", DivInst->getIterator());
388 DivInst->setOperand(i: 0, Val: FrX);
389 Sub->setOperand(i: 0, Val: 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(V: Y, AC: nullptr, CtxI: DivInst, DT: &DT)) {
394 auto *FrY =
395 new FreezeInst(Y, Y->getName() + ".frozen", DivInst->getIterator());
396 DivInst->setOperand(i: 1, Val: FrY);
397 Mul->setOperand(i: 1, Val: 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(V: Sub);
408 OrigRemInst->eraseFromParent();
409 NumDecomposed++;
410 }
411 Changed = true;
412 }
413
414 return Changed;
415}
416
417// Pass manager boilerplate below here.
418
419PreservedAnalyses DivRemPairsPass::run(Function &F,
420 FunctionAnalysisManager &FAM) {
421 TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(IR&: F);
422 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: F);
423 if (!optimizeDivRem(F, TTI, DT))
424 return PreservedAnalyses::all();
425 // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
426 PreservedAnalyses PA;
427 PA.preserveSet<CFGAnalyses>();
428 return PA;
429}
430

source code of llvm/lib/Transforms/Scalar/DivRemPairs.cpp