LLVM 19.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
21#include "llvm/CodeGen/Passes.h"
25#include "llvm/IR/IRBuilder.h"
27#include "llvm/IR/PassManager.h"
29#include "llvm/Pass.h"
33
34using namespace llvm;
35
37 ExpandDivRemBits("expand-div-rem-bits", cl::Hidden,
39 cl::desc("div and rem instructions on integers with "
40 "more than <N> bits are expanded."));
41
42static bool isConstantPowerOfTwo(llvm::Value *V, bool SignedOp) {
43 auto *C = dyn_cast<ConstantInt>(V);
44 if (!C)
45 return false;
46
47 APInt Val = C->getValue();
48 if (SignedOp && Val.isNegative())
49 Val = -Val;
50 return Val.isPowerOf2();
51}
52
53static bool isSigned(unsigned int Opcode) {
54 return Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
55}
56
57static bool runImpl(Function &F, const TargetLowering &TLI) {
59 bool Modified = false;
60
61 unsigned MaxLegalDivRemBitWidth = TLI.getMaxDivRemBitWidthSupported();
63 MaxLegalDivRemBitWidth = ExpandDivRemBits;
64
65 if (MaxLegalDivRemBitWidth >= llvm::IntegerType::MAX_INT_BITS)
66 return false;
67
68 for (auto &I : instructions(F)) {
69 switch (I.getOpcode()) {
70 case Instruction::UDiv:
71 case Instruction::SDiv:
72 case Instruction::URem:
73 case Instruction::SRem: {
74 // TODO: This doesn't handle vectors.
75 auto *IntTy = dyn_cast<IntegerType>(I.getType());
76 if (!IntTy || IntTy->getIntegerBitWidth() <= MaxLegalDivRemBitWidth)
77 continue;
78
79 // The backend has peephole optimizations for powers of two.
80 if (isConstantPowerOfTwo(I.getOperand(1), isSigned(I.getOpcode())))
81 continue;
82
83 Replace.push_back(&cast<BinaryOperator>(I));
84 Modified = true;
85 break;
86 }
87 default:
88 break;
89 }
90 }
91
92 if (Replace.empty())
93 return false;
94
95 while (!Replace.empty()) {
96 BinaryOperator *I = Replace.pop_back_val();
97
98 if (I->getOpcode() == Instruction::UDiv ||
99 I->getOpcode() == Instruction::SDiv) {
101 } else {
103 }
104 }
105
106 return Modified;
107}
108
109namespace {
110class ExpandLargeDivRemLegacyPass : public FunctionPass {
111public:
112 static char ID;
113
114 ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
116 }
117
118 bool runOnFunction(Function &F) override {
119 auto *TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
120 auto *TLI = TM->getSubtargetImpl(F)->getTargetLowering();
121 return runImpl(F, *TLI);
122 }
123
124 void getAnalysisUsage(AnalysisUsage &AU) const override {
128 }
129};
130} // namespace
131
134 const TargetSubtargetInfo *STI = TM->getSubtargetImpl(F);
137}
138
139char ExpandLargeDivRemLegacyPass::ID = 0;
140INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
141 "Expand large div/rem", false, false)
142INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
143 "Expand large div/rem", false, false)
144
146 return new ExpandLargeDivRemLegacyPass();
147}
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."))
static bool isSigned(unsigned int Opcode)
expand large div rem
static bool runImpl(Function &F, const TargetLowering &TLI)
static bool isConstantPowerOfTwo(llvm::Value *V, bool SignedOp)
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:21
This is the interface for a simple mod/ref and alias analysis over globals.
Select target instructions out of generic instructions
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
FunctionAnalysisManager FAM
const char LLVMTargetMachineRef TM
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file defines the SmallVector class.
This file contains some functions that are useful when dealing with strings.
This file describes how to lower LLVM code to machine code.
Target-Independent Code Generator Pass Configuration Options pass.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
Definition: APInt.h:76
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:307
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:418
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Legacy wrapper pass to provide the GlobalsAAResult object.
@ MAX_INT_BITS
Maximum number of bits that can be specified.
Definition: DerivedTypes.h:52
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
unsigned getMaxDivRemBitWidthSupported() const
Returns the size in bits of the maximum div/rem the backend supports.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:76
virtual const TargetSubtargetInfo * getSubtargetImpl(const Function &) const
Virtual method implemented by subclasses that returns a reference to that target's TargetSubtargetInf...
Target-Independent Code Generator Pass Configuration Options.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetLowering * getTargetLowering() const
LLVM Value Representation.
Definition: Value.h:74
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool expandDivision(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
void initializeExpandLargeDivRemLegacyPassPass(PassRegistry &)
FunctionPass * createExpandLargeDivRemPass()
bool expandRemainder(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.