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/CodeGen/ExpandLargeDivRem.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Analysis/GlobalsModRef.h"
20 #include "llvm/CodeGen/Passes.h"
21 #include "llvm/CodeGen/TargetLowering.h"
22 #include "llvm/CodeGen/TargetPassConfig.h"
23 #include "llvm/CodeGen/TargetSubtargetInfo.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"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Target/TargetMachine.h"
31 #include "llvm/Transforms/Utils/IntegerDivision.h"
32
33 using namespace llvm;
34
35 static cl::opt<unsigned>
36 ExpandDivRemBits("expand-div-rem-bits", cl::Hidden,
37 cl::init(llvm::IntegerType::MAX_INT_BITS),
38 cl::desc("div and rem instructions on integers with "
39 "more than <N> bits are expanded."));
40
isConstantPowerOfTwo(llvm::Value * V,bool SignedOp)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
isSigned(unsigned int Opcode)52 static bool isSigned(unsigned int Opcode) {
53 return Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
54 }
55
scalarize(BinaryOperator * BO,SmallVectorImpl<BinaryOperator * > & Replace)56 static void scalarize(BinaryOperator *BO,
57 SmallVectorImpl<BinaryOperator *> &Replace) {
58 VectorType *VTy = cast<FixedVectorType>(BO->getType());
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);
75 BO->dropAllReferences();
76 BO->eraseFromParent();
77 }
78
runImpl(Function & F,const TargetLowering & TLI)79 static bool runImpl(Function &F, const TargetLowering &TLI) {
80 SmallVector<BinaryOperator *, 4> Replace;
81 SmallVector<BinaryOperator *, 4> ReplaceVector;
82 bool Modified = false;
83
84 unsigned MaxLegalDivRemBitWidth = TLI.getMaxDivRemBitWidthSupported();
85 if (ExpandDivRemBits != llvm::IntegerType::MAX_INT_BITS)
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
113 Replace.push_back(&cast<BinaryOperator>(I));
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) {
135 expandDivision(I);
136 } else {
137 expandRemainder(I);
138 }
139 }
140
141 return Modified;
142 }
143
144 namespace {
145 class ExpandLargeDivRemLegacyPass : public FunctionPass {
146 public:
147 static char ID;
148
ExpandLargeDivRemLegacyPass()149 ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
150 initializeExpandLargeDivRemLegacyPassPass(*PassRegistry::getPassRegistry());
151 }
152
runOnFunction(Function & F)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
getAnalysisUsage(AnalysisUsage & AU) const159 void getAnalysisUsage(AnalysisUsage &AU) const override {
160 AU.addRequired<TargetPassConfig>();
161 AU.addPreserved<AAResultsWrapperPass>();
162 AU.addPreserved<GlobalsAAWrapperPass>();
163 }
164 };
165 } // namespace
166
run(Function & F,FunctionAnalysisManager & FAM)167 PreservedAnalyses ExpandLargeDivRemPass::run(Function &F,
168 FunctionAnalysisManager &FAM) {
169 const TargetSubtargetInfo *STI = TM->getSubtargetImpl(F);
170 return runImpl(F, *STI->getTargetLowering()) ? PreservedAnalyses::none()
171 : PreservedAnalyses::all();
172 }
173
174 char ExpandLargeDivRemLegacyPass::ID = 0;
175 INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
176 "Expand large div/rem", false, false)
177 INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
178 "Expand large div/rem", false, false)
179
createExpandLargeDivRemPass()180 FunctionPass *llvm::createExpandLargeDivRemPass() {
181 return new ExpandLargeDivRemLegacyPass();
182 }
183