LLVM  9.0.0svn
DivRemPairs.cpp
Go to the documentation of this file.
1 //===- DivRemPairs.cpp - Hoist/decompose division and remainder -*- C++ -*-===//
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 integer division and remainder
10 // instructions to enable CFG improvements and better codegen.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/MapVector.h"
17 #include "llvm/ADT/Statistic.h"
20 #include "llvm/IR/Dominators.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/Pass.h"
24 #include "llvm/Transforms/Scalar.h"
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "div-rem-pairs"
29 STATISTIC(NumPairs, "Number of div/rem pairs");
30 STATISTIC(NumHoisted, "Number of instructions hoisted");
31 STATISTIC(NumDecomposed, "Number of instructions decomposed");
32 DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform",
33  "Controls transformations in div-rem-pairs pass");
34 
35 /// Find matching pairs of integer div/rem ops (they have the same numerator,
36 /// denominator, and signedness). If they exist in different basic blocks, bring
37 /// them together by hoisting or replace the common division operation that is
38 /// implicit in the remainder:
39 /// X % Y <--> X - ((X / Y) * Y).
40 ///
41 /// We can largely ignore the normal safety and cost constraints on speculation
42 /// of these ops when we find a matching pair. This is because we are already
43 /// guaranteed that any exceptions and most cost are already incurred by the
44 /// first member of the pair.
45 ///
46 /// Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or
47 /// SimplifyCFG, but it's split off on its own because it's different enough
48 /// that it doesn't quite match the stated objectives of those passes.
49 static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI,
50  const DominatorTree &DT) {
51  bool Changed = false;
52 
53  // Insert all divide and remainder instructions into maps keyed by their
54  // operands and opcode (signed or unsigned).
56  // Use a MapVector for RemMap so that instructions are moved/inserted in a
57  // deterministic order.
59  for (auto &BB : F) {
60  for (auto &I : BB) {
61  if (I.getOpcode() == Instruction::SDiv)
62  DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
63  else if (I.getOpcode() == Instruction::UDiv)
64  DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
65  else if (I.getOpcode() == Instruction::SRem)
66  RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I;
67  else if (I.getOpcode() == Instruction::URem)
68  RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I;
69  }
70  }
71 
72  // We can iterate over either map because we are only looking for matched
73  // pairs. Choose remainders for efficiency because they are usually even more
74  // rare than division.
75  for (auto &RemPair : RemMap) {
76  // Find the matching division instruction from the division map.
77  Instruction *DivInst = DivMap[RemPair.first];
78  if (!DivInst)
79  continue;
80 
81  // We have a matching pair of div/rem instructions. If one dominates the
82  // other, hoist and/or replace one.
83  NumPairs++;
84  Instruction *RemInst = RemPair.second;
85  bool IsSigned = DivInst->getOpcode() == Instruction::SDiv;
86  bool HasDivRemOp = TTI.hasDivRemOp(DivInst->getType(), IsSigned);
87 
88  // If the target supports div+rem and the instructions are in the same block
89  // already, there's nothing to do. The backend should handle this. If the
90  // target does not support div+rem, then we will decompose the rem.
91  if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())
92  continue;
93 
94  bool DivDominates = DT.dominates(DivInst, RemInst);
95  if (!DivDominates && !DT.dominates(RemInst, DivInst))
96  continue;
97 
98  if (!DebugCounter::shouldExecute(DRPCounter))
99  continue;
100 
101  if (HasDivRemOp) {
102  // The target has a single div/rem operation. Hoist the lower instruction
103  // to make the matched pair visible to the backend.
104  if (DivDominates)
105  RemInst->moveAfter(DivInst);
106  else
107  DivInst->moveAfter(RemInst);
108  NumHoisted++;
109  } else {
110  // The target does not have a single div/rem operation. Decompose the
111  // remainder calculation as:
112  // X % Y --> X - ((X / Y) * Y).
113  Value *X = RemInst->getOperand(0);
114  Value *Y = RemInst->getOperand(1);
115  Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y);
116  Instruction *Sub = BinaryOperator::CreateSub(X, Mul);
117 
118  // If the remainder dominates, then hoist the division up to that block:
119  //
120  // bb1:
121  // %rem = srem %x, %y
122  // bb2:
123  // %div = sdiv %x, %y
124  // -->
125  // bb1:
126  // %div = sdiv %x, %y
127  // %mul = mul %div, %y
128  // %rem = sub %x, %mul
129  //
130  // If the division dominates, it's already in the right place. The mul+sub
131  // will be in a different block because we don't assume that they are
132  // cheap to speculatively execute:
133  //
134  // bb1:
135  // %div = sdiv %x, %y
136  // bb2:
137  // %rem = srem %x, %y
138  // -->
139  // bb1:
140  // %div = sdiv %x, %y
141  // bb2:
142  // %mul = mul %div, %y
143  // %rem = sub %x, %mul
144  //
145  // If the div and rem are in the same block, we do the same transform,
146  // but any code movement would be within the same block.
147 
148  if (!DivDominates)
149  DivInst->moveBefore(RemInst);
150  Mul->insertAfter(RemInst);
151  Sub->insertAfter(Mul);
152 
153  // Now kill the explicit remainder. We have replaced it with:
154  // (sub X, (mul (div X, Y), Y)
155  RemInst->replaceAllUsesWith(Sub);
156  RemInst->eraseFromParent();
157  NumDecomposed++;
158  }
159  Changed = true;
160  }
161 
162  return Changed;
163 }
164 
165 // Pass manager boilerplate below here.
166 
167 namespace {
168 struct DivRemPairsLegacyPass : public FunctionPass {
169  static char ID;
170  DivRemPairsLegacyPass() : FunctionPass(ID) {
172  }
173 
174  void getAnalysisUsage(AnalysisUsage &AU) const override {
177  AU.setPreservesCFG();
181  }
182 
183  bool runOnFunction(Function &F) override {
184  if (skipFunction(F))
185  return false;
186  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
187  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
188  return optimizeDivRem(F, TTI, DT);
189  }
190 };
191 }
192 
194 INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs",
195  "Hoist/decompose integer division and remainder", false,
196  false)
198 INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs",
199  "Hoist/decompose integer division and remainder", false,
200  false)
202  return new DivRemPairsLegacyPass();
203 }
204 
209  if (!optimizeDivRem(F, TTI, DT))
210  return PreservedAnalyses::all();
211  // TODO: This pass just hoists/replaces math ops - all analyses are preserved?
213  PA.preserveSet<CFGAnalyses>();
214  PA.preserve<GlobalsAA>();
215  return PA;
216 }
Legacy wrapper pass to provide the GlobalsAAResult object.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI, const DominatorTree &DT)
Find matching pairs of integer div/rem ops (they have the same numerator, denominator, and signedness).
Definition: DivRemPairs.cpp:49
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
Analysis pass providing the TargetTransformInfo.
void initializeDivRemPairsLegacyPassPass(PassRegistry &)
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:37
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs", "Hoist/decompose integer division and remainder", false, false) INITIALIZE_PASS_END(DivRemPairsLegacyPass
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
This file provides an implementation of debug counters.
div rem Hoist decompose integer division and remainder
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:91
div rem pairs
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
bool hasDivRemOp(Type *DataType, bool IsSigned) const
Return true if the target has a unified operation to calculate division and remainder.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
static bool runOnFunction(Function &F, bool PostInlining)
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
FunctionPass * createDivRemPairsPass()
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:73
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform", "Controls transformations in div-rem-pairs pass")
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:79
#define I(x, y, z)
Definition: MD5.cpp:58
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:90
LLVM Value Representation.
Definition: Value.h:72
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:86
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
This pass exposes codegen information to IR-level passes.
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
const BasicBlock * getParent() const
Definition: Instruction.h:66