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 void scalarize(BinaryOperator *BO,
59 VectorType *VTy = cast<FixedVectorType>(BO->getType());
60
61 IRBuilder<> Builder(BO);
62
63 unsigned NumElements = VTy->getElementCount().getFixedValue();
64 Value *Result = PoisonValue::get(VTy);
65 for (unsigned Idx = 0; Idx < NumElements; ++Idx) {
66 Value *LHS = Builder.CreateExtractElement(BO->getOperand(0), Idx);
67 Value *RHS = Builder.CreateExtractElement(BO->getOperand(1), Idx);
68 Value *Op = Builder.CreateBinOp(BO->getOpcode(), LHS, RHS);
69 Result = Builder.CreateInsertElement(Result, Op, Idx);
70 if (auto *NewBO = dyn_cast<BinaryOperator>(Op)) {
71 NewBO->copyIRFlags(Op, true);
72 Replace.push_back(NewBO);
73 }
74 }
75 BO->replaceAllUsesWith(Result);
77 BO->eraseFromParent();
78}
79
80static bool runImpl(Function &F, const TargetLowering &TLI) {
83 bool Modified = false;
84
85 unsigned MaxLegalDivRemBitWidth = TLI.getMaxDivRemBitWidthSupported();
87 MaxLegalDivRemBitWidth = ExpandDivRemBits;
88
89 if (MaxLegalDivRemBitWidth >= llvm::IntegerType::MAX_INT_BITS)
90 return false;
91
92 for (auto &I : instructions(F)) {
93 switch (I.getOpcode()) {
94 case Instruction::UDiv:
95 case Instruction::SDiv:
96 case Instruction::URem:
97 case Instruction::SRem: {
98 // TODO: This pass doesn't handle scalable vectors.
99 if (I.getOperand(0)->getType()->isScalableTy())
100 continue;
101
102 auto *IntTy = dyn_cast<IntegerType>(I.getType()->getScalarType());
103 if (!IntTy || IntTy->getIntegerBitWidth() <= MaxLegalDivRemBitWidth)
104 continue;
105
106 // The backend has peephole optimizations for powers of two.
107 // TODO: We don't consider vectors here.
108 if (isConstantPowerOfTwo(I.getOperand(1), isSigned(I.getOpcode())))
109 continue;
110
111 if (I.getOperand(0)->getType()->isVectorTy())
112 ReplaceVector.push_back(&cast<BinaryOperator>(I));
113 else
114 Replace.push_back(&cast<BinaryOperator>(I));
115 Modified = true;
116 break;
117 }
118 default:
119 break;
120 }
121 }
122
123 while (!ReplaceVector.empty()) {
124 BinaryOperator *BO = ReplaceVector.pop_back_val();
125 scalarize(BO, Replace);
126 }
127
128 if (Replace.empty())
129 return false;
130
131 while (!Replace.empty()) {
132 BinaryOperator *I = Replace.pop_back_val();
133
134 if (I->getOpcode() == Instruction::UDiv ||
135 I->getOpcode() == Instruction::SDiv) {
137 } else {
139 }
140 }
141
142 return Modified;
143}
144
145namespace {
146class ExpandLargeDivRemLegacyPass : public FunctionPass {
147public:
148 static char ID;
149
150 ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
152 }
153
154 bool runOnFunction(Function &F) override {
155 auto *TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
156 auto *TLI = TM->getSubtargetImpl(F)->getTargetLowering();
157 return runImpl(F, *TLI);
158 }
159
160 void getAnalysisUsage(AnalysisUsage &AU) const override {
164 }
165};
166} // namespace
167
170 const TargetSubtargetInfo *STI = TM->getSubtargetImpl(F);
173}
174
175char ExpandLargeDivRemLegacyPass::ID = 0;
176INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
177 "Expand large div/rem", false, false)
178INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
179 "Expand large div/rem", false, false)
180
182 return new ExpandLargeDivRemLegacyPass();
183}
Expand Atomic instructions
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
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)
static void scalarize(BinaryOperator *BO, SmallVectorImpl< BinaryOperator * > &Replace)
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.
#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.
Value * RHS
Value * LHS
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
Definition: APInt.h:77
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:308
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:419
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
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.
BinaryOps getOpcode() const
Definition: InstrTypes.h:513
This class represents an Operation in the Expression.
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.
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2472
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2460
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1666
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2666
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
@ 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
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1814
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
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
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
void dropAllReferences()
Drop all references to operands.
Definition: User.h:299
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
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.