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/ADT/StringExtras.h"
20 #include "llvm/Analysis/GlobalsModRef.h"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/CodeGen/TargetLowering.h"
23 #include "llvm/CodeGen/TargetPassConfig.h"
24 #include "llvm/CodeGen/TargetSubtargetInfo.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/InstIterator.h"
27 #include "llvm/IR/PassManager.h"
28 #include "llvm/InitializePasses.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Target/TargetMachine.h"
32 #include "llvm/Transforms/Utils/IntegerDivision.h"
33
34 using namespace llvm;
35
36 static cl::opt<unsigned>
37 ExpandDivRemBits("expand-div-rem-bits", cl::Hidden,
38 cl::init(llvm::IntegerType::MAX_INT_BITS),
39 cl::desc("div and rem instructions on integers with "
40 "more than <N> bits are expanded."));
41
isConstantPowerOfTwo(llvm::Value * V,bool SignedOp)42 static 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
isSigned(unsigned int Opcode)53 static bool isSigned(unsigned int Opcode) {
54 return Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
55 }
56
runImpl(Function & F,const TargetLowering & TLI)57 static bool runImpl(Function &F, const TargetLowering &TLI) {
58 SmallVector<BinaryOperator *, 4> Replace;
59 bool Modified = false;
60
61 unsigned MaxLegalDivRemBitWidth = TLI.getMaxDivRemBitWidthSupported();
62 if (ExpandDivRemBits != llvm::IntegerType::MAX_INT_BITS)
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) {
100 expandDivision(I);
101 } else {
102 expandRemainder(I);
103 }
104 }
105
106 return Modified;
107 }
108
109 namespace {
110 class ExpandLargeDivRemLegacyPass : public FunctionPass {
111 public:
112 static char ID;
113
ExpandLargeDivRemLegacyPass()114 ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
115 initializeExpandLargeDivRemLegacyPassPass(*PassRegistry::getPassRegistry());
116 }
117
runOnFunction(Function & F)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
getAnalysisUsage(AnalysisUsage & AU) const124 void getAnalysisUsage(AnalysisUsage &AU) const override {
125 AU.addRequired<TargetPassConfig>();
126 AU.addPreserved<AAResultsWrapperPass>();
127 AU.addPreserved<GlobalsAAWrapperPass>();
128 }
129 };
130 } // namespace
131
run(Function & F,FunctionAnalysisManager & FAM)132 PreservedAnalyses ExpandLargeDivRemPass::run(Function &F,
133 FunctionAnalysisManager &FAM) {
134 const TargetSubtargetInfo *STI = TM->getSubtargetImpl(F);
135 return runImpl(F, *STI->getTargetLowering()) ? PreservedAnalyses::none()
136 : PreservedAnalyses::all();
137 }
138
139 char ExpandLargeDivRemLegacyPass::ID = 0;
140 INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
141 "Expand large div/rem", false, false)
142 INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
143 "Expand large div/rem", false, false)
144
createExpandLargeDivRemPass()145 FunctionPass *llvm::createExpandLargeDivRemPass() {
146 return new ExpandLargeDivRemLegacyPass();
147 }
148