LLVM 22.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 void scalarize(BinaryOperator *BO,
59
60 IRBuilder<> Builder(BO);
61
62 unsigned NumElements = VTy->getElementCount().getFixedValue();
63 Value *Result = PoisonValue::get(VTy);
64 for (unsigned Idx = 0; Idx < NumElements; ++Idx) {
65 Value *LHS = Builder.CreateExtractElement(BO->getOperand(0), Idx);
66 Value *RHS = Builder.CreateExtractElement(BO->getOperand(1), Idx);
67 Value *Op = Builder.CreateBinOp(BO->getOpcode(), LHS, RHS);
68 Result = Builder.CreateInsertElement(Result, Op, Idx);
69 if (auto *NewBO = dyn_cast<BinaryOperator>(Op)) {
70 NewBO->copyIRFlags(Op, true);
71 Replace.push_back(NewBO);
72 }
73 }
74 BO->replaceAllUsesWith(Result);
76 BO->eraseFromParent();
77}
78
79static bool runImpl(Function &F, const TargetLowering &TLI) {
82 bool Modified = false;
83
84 unsigned MaxLegalDivRemBitWidth = TLI.getMaxDivRemBitWidthSupported();
86 MaxLegalDivRemBitWidth = ExpandDivRemBits;
87
88 if (MaxLegalDivRemBitWidth >= llvm::IntegerType::MAX_INT_BITS)
89 return false;
90
91 for (auto &I : instructions(F)) {
92 switch (I.getOpcode()) {
93 case Instruction::UDiv:
94 case Instruction::SDiv:
95 case Instruction::URem:
96 case Instruction::SRem: {
97 // TODO: This pass doesn't handle scalable vectors.
98 if (I.getOperand(0)->getType()->isScalableTy())
99 continue;
100
101 auto *IntTy = dyn_cast<IntegerType>(I.getType()->getScalarType());
102 if (!IntTy || IntTy->getIntegerBitWidth() <= MaxLegalDivRemBitWidth)
103 continue;
104
105 // The backend has peephole optimizations for powers of two.
106 // TODO: We don't consider vectors here.
107 if (isConstantPowerOfTwo(I.getOperand(1), isSigned(I.getOpcode())))
108 continue;
109
110 if (I.getOperand(0)->getType()->isVectorTy())
111 ReplaceVector.push_back(&cast<BinaryOperator>(I));
112 else
114 Modified = true;
115 break;
116 }
117 default:
118 break;
119 }
120 }
121
122 while (!ReplaceVector.empty()) {
123 BinaryOperator *BO = ReplaceVector.pop_back_val();
124 scalarize(BO, Replace);
125 }
126
127 if (Replace.empty())
128 return false;
129
130 while (!Replace.empty()) {
131 BinaryOperator *I = Replace.pop_back_val();
132
133 if (I->getOpcode() == Instruction::UDiv ||
134 I->getOpcode() == Instruction::SDiv) {
136 } else {
138 }
139 }
140
141 return Modified;
142}
143
144namespace {
145class ExpandLargeDivRemLegacyPass : public FunctionPass {
146public:
147 static char ID;
148
149 ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
151 }
152
153 bool runOnFunction(Function &F) override {
154 auto *TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
155 auto *TLI = TM->getSubtargetImpl(F)->getTargetLowering();
156 return runImpl(F, *TLI);
157 }
158
159 void getAnalysisUsage(AnalysisUsage &AU) const override {
160 AU.addRequired<TargetPassConfig>();
161 AU.addPreserved<AAResultsWrapperPass>();
162 AU.addPreserved<GlobalsAAWrapperPass>();
163 }
164};
165} // namespace
166
173
174char ExpandLargeDivRemLegacyPass::ID = 0;
175INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
176 "Expand large div/rem", false, false)
177INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
178 "Expand large div/rem", false, false)
179
181 return new ExpandLargeDivRemLegacyPass();
182}
Expand Atomic instructions
static bool runOnFunction(Function &F, bool PostInlining)
static bool runImpl(Function &F, const TargetLowering &TLI, AssumptionCache *AC)
Definition ExpandFp.cpp:992
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)
static bool runImpl(Function &F, const TargetLowering &TLI)
static bool isConstantPowerOfTwo(llvm::Value *V, bool SignedOp)
This is the interface for a simple mod/ref and alias analysis over globals.
This header defines various interfaces for pass management in LLVM.
#define F(x, y, z)
Definition MD5.cpp:55
#define I(x, y, z)
Definition MD5.cpp:58
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
This file defines the SmallVector class.
This file describes how to lower LLVM code to machine code.
Target-Independent Code Generator Pass Configuration Options pass.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition APInt.h:78
bool isNegative() const
Determine sign of this APInt.
Definition APInt.h:329
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition APInt.h:440
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
BinaryOps getOpcode() const
Definition InstrTypes.h:374
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:314
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2780
LLVM_ABI 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.
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition Analysis.h:115
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetLowering * getTargetLowering() const
void dropAllReferences()
Drop all references to operands.
Definition User.h:349
Value * getOperand(unsigned i) const
Definition User.h:232
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:256
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:546
@ C
The default llvm calling convention, compatible with C.
Definition CallingConv.h:34
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI bool expandDivision(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:649
LLVM_ABI FunctionPass * createExpandLargeDivRemPass()
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:565
LLVM_ABI bool expandRemainder(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.
LLVM_ABI void initializeExpandLargeDivRemLegacyPassPass(PassRegistry &)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.