LLVM 18.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
20#include "llvm/CodeGen/Passes.h"
24#include "llvm/IR/IRBuilder.h"
26#include "llvm/IR/PassManager.h"
28#include "llvm/Pass.h"
32
33using namespace llvm;
34
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
41static 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
52static bool isSigned(unsigned int Opcode) {
53 return Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
54}
55
56static 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
108namespace {
109class ExpandLargeDivRemLegacyPass : public FunctionPass {
110public:
111 static char ID;
112
113 ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
115 }
116
117 bool runOnFunction(Function &F) override {
118 auto *TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
119 auto *TLI = TM->getSubtargetImpl(F)->getTargetLowering();
120 return runImpl(F, *TLI);
121 }
122
123 void getAnalysisUsage(AnalysisUsage &AU) const override {
127 }
128};
129} // namespace
130
131char ExpandLargeDivRemLegacyPass::ID = 0;
132INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
133 "Expand large div/rem", false, false)
134INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
135 "Expand large div/rem", false, false)
136
138 return new ExpandLargeDivRemLegacyPass();
139}
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
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
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.
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
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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:78
Target-Independent Code Generator Pass Configuration Options.
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:445
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.