1 //===- DivRemPairs.cpp - Hoist/[dr]ecompose division and remainder --------===//
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
7 //===----------------------------------------------------------------------===//
9 // This pass hoists and/or decomposes/recomposes integer division and remainder
10 // instructions to enable CFG improvements and better codegen.
12 //===----------------------------------------------------------------------===//
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"
31 using namespace llvm::PatternMatch;
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");
42 struct ExpandedMatch {
48 /// See if we can match: (which is the form we expand into)
49 /// X - ((X ?/ Y) * Y)
50 /// which is equivalent to:
52 static llvm::Optional<ExpandedMatch> matchExpandedRem(Instruction &I) {
53 Value *Dividend, *XroundedDownToMultipleOfY;
54 if (!match(&I, m_Sub(m_Value(Dividend), m_Value(XroundedDownToMultipleOfY))))
59 // Look for ((X / Y) * Y)
61 XroundedDownToMultipleOfY,
62 m_c_Mul(m_CombineAnd(m_IDiv(m_Specific(Dividend), m_Value(Divisor)),
64 m_Deferred(Divisor))))
68 M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv;
69 M.Key.Dividend = Dividend;
70 M.Key.Divisor = Divisor;
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.
80 AssertingVH<Instruction> DivInst;
82 /// The instruction that we have matched as a remainder instruction.
83 /// Should only be used as Value, don't introspect it.
84 AssertingVH<Instruction> RemInst;
86 DivRemPairWorklistEntry(Instruction *DivInst_, Instruction *RemInst_)
87 : DivInst(DivInst_), RemInst(RemInst_) {
88 assert((DivInst->getOpcode() == Instruction::UDiv ||
89 DivInst->getOpcode() == Instruction::SDiv) &&
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.
96 /// The type for this pair, identical for both the div and rem.
97 Type *getType() const { return DivInst->getType(); }
99 /// Is this pair signed or unsigned?
100 bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; }
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); }
106 bool isRemExpanded() const {
107 switch (RemInst->getOpcode()) {
108 case Instruction::SRem:
109 case Instruction::URem:
110 return false; // single 'rem' instruction - unexpanded form.
112 return true; // anything else means we have remainder in expanded form.
117 using DivRemWorklistTy = SmallVector<DivRemPairWorklistEntry, 4>;
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.
124 static DivRemWorklistTy getWorklist(Function &F) {
125 // Insert all divide and remainder instructions into maps keyed by their
126 // operands and opcode (signed or unsigned).
127 DenseMap<DivRemMapKey, Instruction *> DivMap;
128 // Use a MapVector for RemMap so that instructions are moved/inserted in a
129 // deterministic order.
130 MapVector<DivRemMapKey, Instruction *> RemMap;
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;
146 // We'll accumulate the matching pairs of div-rem instructions here.
147 DivRemWorklistTy Worklist;
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 Instruction *DivInst = DivMap[RemPair.first];
158 // We have a matching pair of div/rem instructions.
160 Instruction *RemInst = RemPair.second;
162 // Place it in the worklist.
163 Worklist.emplace_back(DivInst, RemInst);
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).
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.
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.
183 static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI,
184 const DominatorTree &DT) {
185 bool Changed = false;
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);
191 // Process each entry in the worklist.
192 for (DivRemPairWorklistEntry &E : Worklist) {
193 if (!DebugCounter::shouldExecute(DRPCounter))
196 bool HasDivRemOp = TTI.hasDivRemOp(E.getType(), E.isSigned());
198 auto &DivInst = E.DivInst;
199 auto &RemInst = E.RemInst;
201 const bool RemOriginallyWasInExpandedForm = E.isRemExpanded();
202 (void)RemOriginallyWasInExpandedForm; // suppress unused variable warning
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.
218 // And replace the original instruction with the new one.
219 OrigRemInst->replaceAllUsesWith(RealRem);
220 OrigRemInst->eraseFromParent();
222 // Note that we have left ((X / Y) * Y) around.
223 // If it had other uses we could rewrite it as X - X % Y
227 assert((!E.isRemExpanded() || !HasDivRemOp) &&
228 "*If* the target supports div-rem, then by now the RemInst *is* "
229 "Instruction::[US]Rem.");
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())
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?
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())
251 // The target has a single div/rem operation. Hoist the lower instruction
252 // to make the matched pair visible to the backend.
254 RemInst->moveAfter(DivInst);
256 DivInst->moveAfter(RemInst);
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).
264 assert(!RemOriginallyWasInExpandedForm &&
265 "We should not be expanding if the rem was in expanded form to "
268 Value *X = E.getDividend();
269 Value *Y = E.getDivisor();
270 Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y);
271 Instruction *Sub = BinaryOperator::CreateSub(X, Mul);
273 // If the remainder dominates, then hoist the division up to that block:
276 // %rem = srem %x, %y
278 // %div = sdiv %x, %y
281 // %div = sdiv %x, %y
282 // %mul = mul %div, %y
283 // %rem = sub %x, %mul
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:
290 // %div = sdiv %x, %y
292 // %rem = srem %x, %y
295 // %div = sdiv %x, %y
297 // %mul = mul %div, %y
298 // %rem = sub %x, %mul
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.
304 DivInst->moveBefore(RemInst);
305 Mul->insertAfter(RemInst);
306 Sub->insertAfter(Mul);
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
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, DivInst, &DT)) {
319 auto *FrX = new FreezeInst(X, X->getName() + ".frozen", DivInst);
320 DivInst->setOperand(0, FrX);
321 Sub->setOperand(0, FrX);
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, DivInst, &DT)) {
326 auto *FrY = new FreezeInst(Y, Y->getName() + ".frozen", DivInst);
327 DivInst->setOperand(1, FrY);
328 Mul->setOperand(1, FrY);
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.
337 // And replace the original instruction with the new one.
338 OrigRemInst->replaceAllUsesWith(Sub);
339 OrigRemInst->eraseFromParent();
348 // Pass manager boilerplate below here.
351 struct DivRemPairsLegacyPass : public FunctionPass {
353 DivRemPairsLegacyPass() : FunctionPass(ID) {
354 initializeDivRemPairsLegacyPassPass(*PassRegistry::getPassRegistry());
357 void getAnalysisUsage(AnalysisUsage &AU) const override {
358 AU.addRequired<DominatorTreeWrapperPass>();
359 AU.addRequired<TargetTransformInfoWrapperPass>();
360 AU.setPreservesCFG();
361 AU.addPreserved<DominatorTreeWrapperPass>();
362 AU.addPreserved<GlobalsAAWrapperPass>();
363 FunctionPass::getAnalysisUsage(AU);
366 bool runOnFunction(Function &F) override {
369 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
370 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
371 return optimizeDivRem(F, TTI, DT);
376 char DivRemPairsLegacyPass::ID = 0;
377 INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs",
378 "Hoist/decompose integer division and remainder", false,
380 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
381 INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs",
382 "Hoist/decompose integer division and remainder", false,
384 FunctionPass *llvm::createDivRemPairsPass() {
385 return new DivRemPairsLegacyPass();
388 PreservedAnalyses DivRemPairsPass::run(Function &F,
389 FunctionAnalysisManager &FAM) {
390 TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F);
391 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
392 if (!optimizeDivRem(F, TTI, DT))
393 return PreservedAnalyses::all();
394 // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
395 PreservedAnalyses PA;
396 PA.preserveSet<CFGAnalyses>();
397 PA.preserve<GlobalsAA>();