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 
28 using namespace llvm;
29 using namespace llvm::PatternMatch;
30 
31 #define DEBUG_TYPE "div-rem-pairs"
32 STATISTIC(NumPairs, "Number of div/rem pairs");
33 STATISTIC(NumRecomposed, "Number of instructions recomposed");
34 STATISTIC(NumHoisted, "Number of instructions hoisted");
35 STATISTIC(NumDecomposed, "Number of instructions decomposed");
36 DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",
37               "Controls transformations in div-rem-pairs pass");
38 
39 namespace {
40 struct 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
50 static 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 
73 namespace {
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;
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(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
115 using 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.
122 static 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(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.
181 static 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(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)
249           if (!isGuaranteedToTransferExecutionToSuccessor(&*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()) &&
291           isGuaranteedToTransferExecutionToSuccessor(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 = new FreezeInst(X, X->getName() + ".frozen", DivInst);
387         DivInst->setOperand(0, FrX);
388         Sub->setOperand(0, FrX);
389       }
390       // Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0,
391       // but %rem in tgt can be one of many integer values.
392       if (!isGuaranteedNotToBeUndefOrPoison(Y, nullptr, DivInst, &DT)) {
393         auto *FrY = new FreezeInst(Y, Y->getName() + ".frozen", DivInst);
394         DivInst->setOperand(1, FrY);
395         Mul->setOperand(1, FrY);
396       }
397 
398       // Now kill the explicit remainder. We have replaced it with:
399       // (sub X, (mul (div X, Y), Y)
400       Sub->setName(RemInst->getName() + ".decomposed");
401       Instruction *OrigRemInst = RemInst;
402       // Update AssertingVH<> with new instruction so it doesn't assert.
403       RemInst = Sub;
404       // And replace the original instruction with the new one.
405       OrigRemInst->replaceAllUsesWith(Sub);
406       OrigRemInst->eraseFromParent();
407       NumDecomposed++;
408     }
409     Changed = true;
410   }
411 
412   return Changed;
413 }
414 
415 // Pass manager boilerplate below here.
416 
417 PreservedAnalyses DivRemPairsPass::run(Function &F,
418                                        FunctionAnalysisManager &FAM) {
419   TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F);
420   DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
421   if (!optimizeDivRem(F, TTI, DT))
422     return PreservedAnalyses::all();
423   // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
424   PreservedAnalyses PA;
425   PA.preserveSet<CFGAnalyses>();
426   return PA;
427 }
428