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/InitializePasses.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Support/DebugCounter.h"
27 #include "llvm/Transforms/Scalar.h"
28 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
29 #include <optional>
30
31 using namespace llvm;
32 using namespace llvm::PatternMatch;
33
34 #define DEBUG_TYPE "div-rem-pairs"
35 STATISTIC(NumPairs, "Number of div/rem pairs");
36 STATISTIC(NumRecomposed, "Number of instructions recomposed");
37 STATISTIC(NumHoisted, "Number of instructions hoisted");
38 STATISTIC(NumDecomposed, "Number of instructions decomposed");
39 DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",
40 "Controls transformations in div-rem-pairs pass");
41
42 namespace {
43 struct ExpandedMatch {
44 DivRemMapKey Key;
45 Instruction *Value;
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
matchExpandedRem(Instruction & I)53 static 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
76 namespace {
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.
79 struct DivRemPairWorklistEntry {
80 /// The actual udiv/sdiv instruction. Source of truth.
81 AssertingVH<Instruction> DivInst;
82
83 /// The instruction that we have matched as a remainder instruction.
84 /// Should only be used as Value, don't introspect it.
85 AssertingVH<Instruction> RemInst;
86
DivRemPairWorklistEntry__anone6bce0700211::DivRemPairWorklistEntry87 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.
getType__anone6bce0700211::DivRemPairWorklistEntry98 Type *getType() const { return DivInst->getType(); }
99
100 /// Is this pair signed or unsigned?
isSigned__anone6bce0700211::DivRemPairWorklistEntry101 bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; }
102
103 /// In this pair, what are the divident and divisor?
getDividend__anone6bce0700211::DivRemPairWorklistEntry104 Value *getDividend() const { return DivInst->getOperand(0); }
getDivisor__anone6bce0700211::DivRemPairWorklistEntry105 Value *getDivisor() const { return DivInst->getOperand(1); }
106
isRemExpanded__anone6bce0700211::DivRemPairWorklistEntry107 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
118 using DivRemWorklistTy = SmallVector<DivRemPairWorklistEntry, 4>;
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.
getWorklist(Function & F)125 static DivRemWorklistTy getWorklist(Function &F) {
126 // Insert all divide and remainder instructions into maps keyed by their
127 // operands and opcode (signed or unsigned).
128 DenseMap<DivRemMapKey, Instruction *> DivMap;
129 // Use a MapVector for RemMap so that instructions are moved/inserted in a
130 // deterministic order.
131 MapVector<DivRemMapKey, Instruction *> RemMap;
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.
optimizeDivRem(Function & F,const TargetTransformInfo & TTI,const DominatorTree & DT)184 static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI,
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)
252 if (!isGuaranteedToTransferExecutionToSuccessor(&*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()) &&
294 isGuaranteedToTransferExecutionToSuccessor(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 X can be undef, X should be frozen first.
375 // For example, let's assume that Y = 1 & X = undef:
376 // %div = sdiv undef, 1 // %div = undef
377 // %rem = srem undef, 1 // %rem = 0
378 // =>
379 // %div = sdiv undef, 1 // %div = undef
380 // %mul = mul %div, 1 // %mul = undef
381 // %rem = sub %x, %mul // %rem = undef - undef = undef
382 // If X is not frozen, %rem becomes undef after transformation.
383 // TODO: We need a undef-specific checking function in ValueTracking
384 if (!isGuaranteedNotToBeUndefOrPoison(X, nullptr, DivInst, &DT)) {
385 auto *FrX = new FreezeInst(X, X->getName() + ".frozen", DivInst);
386 DivInst->setOperand(0, FrX);
387 Sub->setOperand(0, FrX);
388 }
389 // Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0,
390 // but %rem in tgt can be one of many integer values.
391 if (!isGuaranteedNotToBeUndefOrPoison(Y, nullptr, DivInst, &DT)) {
392 auto *FrY = new FreezeInst(Y, Y->getName() + ".frozen", DivInst);
393 DivInst->setOperand(1, FrY);
394 Mul->setOperand(1, FrY);
395 }
396
397 // Now kill the explicit remainder. We have replaced it with:
398 // (sub X, (mul (div X, Y), Y)
399 Sub->setName(RemInst->getName() + ".decomposed");
400 Instruction *OrigRemInst = RemInst;
401 // Update AssertingVH<> with new instruction so it doesn't assert.
402 RemInst = Sub;
403 // And replace the original instruction with the new one.
404 OrigRemInst->replaceAllUsesWith(Sub);
405 OrigRemInst->eraseFromParent();
406 NumDecomposed++;
407 }
408 Changed = true;
409 }
410
411 return Changed;
412 }
413
414 // Pass manager boilerplate below here.
415
416 namespace {
417 struct DivRemPairsLegacyPass : public FunctionPass {
418 static char ID;
DivRemPairsLegacyPass__anone6bce0700611::DivRemPairsLegacyPass419 DivRemPairsLegacyPass() : FunctionPass(ID) {
420 initializeDivRemPairsLegacyPassPass(*PassRegistry::getPassRegistry());
421 }
422
getAnalysisUsage__anone6bce0700611::DivRemPairsLegacyPass423 void getAnalysisUsage(AnalysisUsage &AU) const override {
424 AU.addRequired<DominatorTreeWrapperPass>();
425 AU.addRequired<TargetTransformInfoWrapperPass>();
426 AU.setPreservesCFG();
427 AU.addPreserved<DominatorTreeWrapperPass>();
428 AU.addPreserved<GlobalsAAWrapperPass>();
429 FunctionPass::getAnalysisUsage(AU);
430 }
431
runOnFunction__anone6bce0700611::DivRemPairsLegacyPass432 bool runOnFunction(Function &F) override {
433 if (skipFunction(F))
434 return false;
435 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
436 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
437 return optimizeDivRem(F, TTI, DT);
438 }
439 };
440 } // namespace
441
442 char DivRemPairsLegacyPass::ID = 0;
443 INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs",
444 "Hoist/decompose integer division and remainder", false,
445 false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)446 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
447 INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs",
448 "Hoist/decompose integer division and remainder", false,
449 false)
450 FunctionPass *llvm::createDivRemPairsPass() {
451 return new DivRemPairsLegacyPass();
452 }
453
run(Function & F,FunctionAnalysisManager & FAM)454 PreservedAnalyses DivRemPairsPass::run(Function &F,
455 FunctionAnalysisManager &FAM) {
456 TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F);
457 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
458 if (!optimizeDivRem(F, TTI, DT))
459 return PreservedAnalyses::all();
460 // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
461 PreservedAnalyses PA;
462 PA.preserveSet<CFGAnalyses>();
463 return PA;
464 }
465