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/IR/Dominators.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/PatternMatch.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Pass.h"
25 #include "llvm/Support/DebugCounter.h"
26 #include "llvm/Transforms/Scalar.h"
27 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
30 using namespace llvm::PatternMatch;
32 #define DEBUG_TYPE "div-rem-pairs"
33 STATISTIC(NumPairs, "Number of div/rem pairs");
34 STATISTIC(NumRecomposed, "Number of instructions recomposed");
35 STATISTIC(NumHoisted, "Number of instructions hoisted");
36 STATISTIC(NumDecomposed, "Number of instructions decomposed");
37 DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",
38 "Controls transformations in div-rem-pairs pass");
41 struct ExpandedMatch {
47 /// See if we can match: (which is the form we expand into)
48 /// X - ((X ?/ Y) * Y)
49 /// which is equivalent to:
51 static llvm::Optional<ExpandedMatch> matchExpandedRem(Instruction &I) {
52 Value *Dividend, *XroundedDownToMultipleOfY;
53 if (!match(&I, m_Sub(m_Value(Dividend), m_Value(XroundedDownToMultipleOfY))))
58 // Look for ((X / Y) * Y)
60 XroundedDownToMultipleOfY,
61 m_c_Mul(m_CombineAnd(m_IDiv(m_Specific(Dividend), m_Value(Divisor)),
63 m_Deferred(Divisor))))
67 M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv;
68 M.Key.Dividend = Dividend;
69 M.Key.Divisor = Divisor;
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.
76 struct DivRemPairWorklistEntry {
77 /// The actual udiv/sdiv instruction. Source of truth.
78 AssertingVH<Instruction> DivInst;
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;
84 DivRemPairWorklistEntry(Instruction *DivInst_, Instruction *RemInst_)
85 : DivInst(DivInst_), RemInst(RemInst_) {
86 assert((DivInst->getOpcode() == Instruction::UDiv ||
87 DivInst->getOpcode() == Instruction::SDiv) &&
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.
94 /// The type for this pair, identical for both the div and rem.
95 Type *getType() const { return DivInst->getType(); }
97 /// Is this pair signed or unsigned?
98 bool isSigned() const { return DivInst->getOpcode() == Instruction::SDiv; }
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); }
104 bool isRemExpanded() const {
105 switch (RemInst->getOpcode()) {
106 case Instruction::SRem:
107 case Instruction::URem:
108 return false; // single 'rem' instruction - unexpanded form.
110 return true; // anything else means we have remainder in expanded form.
114 using DivRemWorklistTy = SmallVector<DivRemPairWorklistEntry, 4>;
116 /// Find matching pairs of integer div/rem ops (they have the same numerator,
117 /// denominator, and signedness). Place those pairs into a worklist for further
118 /// processing. This indirection is needed because we have to use TrackingVH<>
119 /// because we will be doing RAUW, and if one of the rem instructions we change
120 /// happens to be an input to another div/rem in the maps, we'd have problems.
121 static DivRemWorklistTy getWorklist(Function &F) {
122 // Insert all divide and remainder instructions into maps keyed by their
123 // operands and opcode (signed or unsigned).
124 DenseMap<DivRemMapKey, Instruction *> DivMap;
125 // Use a MapVector for RemMap so that instructions are moved/inserted in a
126 // deterministic order.
127 MapVector<DivRemMapKey, Instruction *> RemMap;
130 if (I.getOpcode() == Instruction::SDiv)
131 DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
132 else if (I.getOpcode() == Instruction::UDiv)
133 DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
134 else if (I.getOpcode() == Instruction::SRem)
135 RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
136 else if (I.getOpcode() == Instruction::URem)
137 RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
138 else if (auto Match = matchExpandedRem(I))
139 RemMap[Match->Key] = Match->Value;
143 // We'll accumulate the matching pairs of div-rem instructions here.
144 DivRemWorklistTy Worklist;
146 // We can iterate over either map because we are only looking for matched
147 // pairs. Choose remainders for efficiency because they are usually even more
148 // rare than division.
149 for (auto &RemPair : RemMap) {
150 // Find the matching division instruction from the division map.
151 Instruction *DivInst = DivMap[RemPair.first];
155 // We have a matching pair of div/rem instructions.
157 Instruction *RemInst = RemPair.second;
159 // Place it in the worklist.
160 Worklist.emplace_back(DivInst, RemInst);
166 /// Find matching pairs of integer div/rem ops (they have the same numerator,
167 /// denominator, and signedness). If they exist in different basic blocks, bring
168 /// them together by hoisting or replace the common division operation that is
169 /// implicit in the remainder:
170 /// X % Y <--> X - ((X / Y) * Y).
172 /// We can largely ignore the normal safety and cost constraints on speculation
173 /// of these ops when we find a matching pair. This is because we are already
174 /// guaranteed that any exceptions and most cost are already incurred by the
175 /// first member of the pair.
177 /// Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or
178 /// SimplifyCFG, but it's split off on its own because it's different enough
179 /// that it doesn't quite match the stated objectives of those passes.
180 static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI,
181 const DominatorTree &DT) {
182 bool Changed = false;
184 // Get the matching pairs of div-rem instructions. We want this extra
185 // indirection to avoid dealing with having to RAUW the keys of the maps.
186 DivRemWorklistTy Worklist = getWorklist(F);
188 // Process each entry in the worklist.
189 for (DivRemPairWorklistEntry &E : Worklist) {
190 if (!DebugCounter::shouldExecute(DRPCounter))
193 bool HasDivRemOp = TTI.hasDivRemOp(E.getType(), E.isSigned());
195 auto &DivInst = E.DivInst;
196 auto &RemInst = E.RemInst;
198 const bool RemOriginallyWasInExpandedForm = E.isRemExpanded();
199 (void)RemOriginallyWasInExpandedForm; // suppress unused variable warning
201 if (HasDivRemOp && E.isRemExpanded()) {
202 // The target supports div+rem but the rem is expanded.
203 // We should recompose it first.
204 Value *X = E.getDividend();
205 Value *Y = E.getDivisor();
206 Instruction *RealRem = E.isSigned() ? BinaryOperator::CreateSRem(X, Y)
207 : BinaryOperator::CreateURem(X, Y);
208 // Note that we place it right next to the original expanded instruction,
209 // and letting further handling to move it if needed.
210 RealRem->setName(RemInst->getName() + ".recomposed");
211 RealRem->insertAfter(RemInst);
212 Instruction *OrigRemInst = RemInst;
213 // Update AssertingVH<> with new instruction so it doesn't assert.
215 // And replace the original instruction with the new one.
216 OrigRemInst->replaceAllUsesWith(RealRem);
217 OrigRemInst->eraseFromParent();
219 // Note that we have left ((X / Y) * Y) around.
220 // If it had other uses we could rewrite it as X - X % Y
223 assert((!E.isRemExpanded() || !HasDivRemOp) &&
224 "*If* the target supports div-rem, then by now the RemInst *is* "
225 "Instruction::[US]Rem.");
227 // If the target supports div+rem and the instructions are in the same block
228 // already, there's nothing to do. The backend should handle this. If the
229 // target does not support div+rem, then we will decompose the rem.
230 if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())
233 bool DivDominates = DT.dominates(DivInst, RemInst);
234 if (!DivDominates && !DT.dominates(RemInst, DivInst)) {
235 // We have matching div-rem pair, but they are in two different blocks,
236 // neither of which dominates one another.
237 // FIXME: We could hoist both ops to the common predecessor block?
241 // The target does not have a single div/rem operation,
242 // and the rem is already in expanded form. Nothing to do.
243 if (!HasDivRemOp && E.isRemExpanded())
247 // The target has a single div/rem operation. Hoist the lower instruction
248 // to make the matched pair visible to the backend.
250 RemInst->moveAfter(DivInst);
252 DivInst->moveAfter(RemInst);
255 // The target does not have a single div/rem operation,
256 // and the rem is *not* in a already-expanded form.
257 // Decompose the remainder calculation as:
258 // X % Y --> X - ((X / Y) * Y).
260 assert(!RemOriginallyWasInExpandedForm &&
261 "We should not be expanding if the rem was in expanded form to "
264 Value *X = E.getDividend();
265 Value *Y = E.getDivisor();
266 Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y);
267 Instruction *Sub = BinaryOperator::CreateSub(X, Mul);
269 // If the remainder dominates, then hoist the division up to that block:
272 // %rem = srem %x, %y
274 // %div = sdiv %x, %y
277 // %div = sdiv %x, %y
278 // %mul = mul %div, %y
279 // %rem = sub %x, %mul
281 // If the division dominates, it's already in the right place. The mul+sub
282 // will be in a different block because we don't assume that they are
283 // cheap to speculatively execute:
286 // %div = sdiv %x, %y
288 // %rem = srem %x, %y
291 // %div = sdiv %x, %y
293 // %mul = mul %div, %y
294 // %rem = sub %x, %mul
296 // If the div and rem are in the same block, we do the same transform,
297 // but any code movement would be within the same block.
300 DivInst->moveBefore(RemInst);
301 Mul->insertAfter(RemInst);
302 Sub->insertAfter(Mul);
304 // Now kill the explicit remainder. We have replaced it with:
305 // (sub X, (mul (div X, Y), Y)
306 Sub->setName(RemInst->getName() + ".decomposed");
307 Instruction *OrigRemInst = RemInst;
308 // Update AssertingVH<> with new instruction so it doesn't assert.
310 // And replace the original instruction with the new one.
311 OrigRemInst->replaceAllUsesWith(Sub);
312 OrigRemInst->eraseFromParent();
321 // Pass manager boilerplate below here.
324 struct DivRemPairsLegacyPass : public FunctionPass {
326 DivRemPairsLegacyPass() : FunctionPass(ID) {
327 initializeDivRemPairsLegacyPassPass(*PassRegistry::getPassRegistry());
330 void getAnalysisUsage(AnalysisUsage &AU) const override {
331 AU.addRequired<DominatorTreeWrapperPass>();
332 AU.addRequired<TargetTransformInfoWrapperPass>();
333 AU.setPreservesCFG();
334 AU.addPreserved<DominatorTreeWrapperPass>();
335 AU.addPreserved<GlobalsAAWrapperPass>();
336 FunctionPass::getAnalysisUsage(AU);
339 bool runOnFunction(Function &F) override {
342 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
343 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
344 return optimizeDivRem(F, TTI, DT);
349 char DivRemPairsLegacyPass::ID = 0;
350 INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs",
351 "Hoist/decompose integer division and remainder", false,
353 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
354 INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs",
355 "Hoist/decompose integer division and remainder", false,
357 FunctionPass *llvm::createDivRemPairsPass() {
358 return new DivRemPairsLegacyPass();
361 PreservedAnalyses DivRemPairsPass::run(Function &F,
362 FunctionAnalysisManager &FAM) {
363 TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F);
364 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
365 if (!optimizeDivRem(F, TTI, DT))
366 return PreservedAnalyses::all();
367 // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
368 PreservedAnalyses PA;
369 PA.preserveSet<CFGAnalyses>();
370 PA.preserve<GlobalsAA>();