LLVM  16.0.0git
ExpandLargeDivRem.cpp
Go to the documentation of this file.
1 //===--- ExpandLargeDivRem.cpp - Expand large div/rem ---------------------===//
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 expands div/rem instructions with a bitwidth above a threshold
10 // into a call to auto-generated functions.
11 // This is useful for targets like x86_64 that cannot lower divisions
12 // with more than 128 bits or targets like x86_32 that cannot lower divisions
13 // with more than 64 bits.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/StringExtras.h"
20 #include "llvm/CodeGen/Passes.h"
24 #include "llvm/IR/IRBuilder.h"
25 #include "llvm/IR/InstIterator.h"
26 #include "llvm/IR/PassManager.h"
27 #include "llvm/InitializePasses.h"
28 #include "llvm/Pass.h"
32 
33 using namespace llvm;
34 
35 static cl::opt<unsigned>
36  ExpandDivRemBits("expand-div-rem-bits", cl::Hidden,
38  cl::desc("div and rem instructions on integers with "
39  "more than <N> bits are expanded."));
40 
41 static bool isConstantPowerOfTwo(llvm::Value *V, bool SignedOp) {
42  auto *C = dyn_cast<ConstantInt>(V);
43  if (!C)
44  return false;
45 
46  APInt Val = C->getValue();
47  if (SignedOp && Val.isNegative())
48  Val = -Val;
49  return Val.isPowerOf2();
50 }
51 
52 static bool isSigned(unsigned int Opcode) {
53  return Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
54 }
55 
56 static bool runImpl(Function &F, const TargetLowering &TLI) {
58  bool Modified = false;
59 
60  unsigned MaxLegalDivRemBitWidth = TLI.getMaxDivRemBitWidthSupported();
62  MaxLegalDivRemBitWidth = ExpandDivRemBits;
63 
64  if (MaxLegalDivRemBitWidth >= llvm::IntegerType::MAX_INT_BITS)
65  return false;
66 
67  for (auto &I : instructions(F)) {
68  switch (I.getOpcode()) {
69  case Instruction::UDiv:
70  case Instruction::SDiv:
71  case Instruction::URem:
72  case Instruction::SRem: {
73  // TODO: This doesn't handle vectors.
74  auto *IntTy = dyn_cast<IntegerType>(I.getType());
75  if (!IntTy || IntTy->getIntegerBitWidth() <= MaxLegalDivRemBitWidth)
76  continue;
77 
78  // The backend has peephole optimizations for powers of two.
79  if (isConstantPowerOfTwo(I.getOperand(1), isSigned(I.getOpcode())))
80  continue;
81 
82  Replace.push_back(&cast<BinaryOperator>(I));
83  Modified = true;
84  break;
85  }
86  default:
87  break;
88  }
89  }
90 
91  if (Replace.empty())
92  return false;
93 
94  while (!Replace.empty()) {
95  BinaryOperator *I = Replace.pop_back_val();
96 
97  if (I->getOpcode() == Instruction::UDiv ||
98  I->getOpcode() == Instruction::SDiv) {
100  } else {
102  }
103  }
104 
105  return Modified;
106 }
107 
109 public:
110  static char ID;
111 
114  }
115 
116  bool runOnFunction(Function &F) override {
117  auto *TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
118  auto *TLI = TM->getSubtargetImpl(F)->getTargetLowering();
119  return runImpl(F, *TLI);
120  }
121 
122  void getAnalysisUsage(AnalysisUsage &AU) const override {
126  }
127 };
128 
130 INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
131  "Expand large div/rem", false, false)
133  "Expand large div/rem", false, false)
134 
136  return new ExpandLargeDivRemLegacyPass();
137 }
isConstantPowerOfTwo
static bool isConstantPowerOfTwo(llvm::Value *V, bool SignedOp)
Definition: ExpandLargeDivRem.cpp:41
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
InstIterator.h
llvm::Function
Definition: Function.h:60
Pass.h
llvm::APInt::isPowerOf2
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:425
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
ExpandLargeDivRemLegacyPass::ID
static char ID
Definition: ExpandLargeDivRem.cpp:110
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::TargetLoweringBase::getMaxDivRemBitWidthSupported
unsigned getMaxDivRemBitWidthSupported() const
Returns the size in bits of the maximum div/rem the backend supports.
Definition: TargetLowering.h:1956
F
#define F(x, y, z)
Definition: MD5.cpp:55
CommandLine.h
TargetLowering.h
llvm::APInt::isNegative
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:312
TargetMachine.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::TargetLowering
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Definition: TargetLowering.h:3486
llvm::expandDivision
bool expandDivision(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
Definition: IntegerDivision.cpp:407
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
LoopDeletionResult::Modified
@ Modified
rem
expand large div rem
Definition: ExpandLargeDivRem.cpp:132
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
ExpandLargeDivRemLegacyPass
Definition: ExpandLargeDivRem.cpp:108
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
Passes.h
ExpandLargeDivRemLegacyPass::ExpandLargeDivRemLegacyPass
ExpandLargeDivRemLegacyPass()
Definition: ExpandLargeDivRem.cpp:112
llvm::TargetPassConfig
Target-Independent Code Generator Pass Configuration Options.
Definition: TargetPassConfig.h:84
llvm::cl::opt
Definition: CommandLine.h:1412
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
expand
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:27
llvm::initializeExpandLargeDivRemLegacyPassPass
void initializeExpandLargeDivRemLegacyPassPass(PassRegistry &)
ExpandLargeDivRemLegacyPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: ExpandLargeDivRem.cpp:116
I
#define I(x, y, z)
Definition: MD5.cpp:58
StringExtras.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
TargetPassConfig.h
IRBuilder.h
llvm::TargetMachine
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:77
llvm::IntegerType::MAX_INT_BITS
@ MAX_INT_BITS
Maximum number of bits that can be specified.
Definition: DerivedTypes.h:52
llvm::expandRemainder
bool expandRemainder(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.
Definition: IntegerDivision.cpp:354
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::BinaryOperator
Definition: InstrTypes.h:188
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
TargetSubtargetInfo.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem", "Expand large div/rem", false, false) INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass
PassManager.h
runImpl
static bool runImpl(Function &F, const TargetLowering &TLI)
Definition: ExpandLargeDivRem.cpp:56
IntegerDivision.h
ExpandDivRemBits
static cl::opt< unsigned > ExpandDivRemBits("expand-div-rem-bits", cl::Hidden, cl::init(llvm::IntegerType::MAX_INT_BITS), cl::desc("div and rem instructions on integers with " "more than <N> bits are expanded."))
isSigned
static bool isSigned(unsigned int Opcode)
Definition: ExpandLargeDivRem.cpp:52
SmallVector.h
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:924
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:142
ExpandLargeDivRemLegacyPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: ExpandLargeDivRem.cpp:122
TM
const char LLVMTargetMachineRef TM
Definition: PassBuilderBindings.cpp:47
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::createExpandLargeDivRemPass
FunctionPass * createExpandLargeDivRemPass()
Definition: ExpandLargeDivRem.cpp:135
llvm::cl::desc
Definition: CommandLine.h:413
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74