1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
//===--- ExpandLargeDivRem.cpp - Expand large div/rem ---------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This pass expands div/rem instructions with a bitwidth above a threshold
// into a call to auto-generated functions.
// This is useful for targets like x86_64 that cannot lower divisions
// with more than 128 bits or targets like x86_32 that cannot lower divisions
// with more than 64 bits.
//
//===----------------------------------------------------------------------===//
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Transforms/Utils/IntegerDivision.h"
using namespace llvm;
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 isConstantPowerOfTwo(llvm::Value *V, bool SignedOp) {
auto *C = dyn_cast<ConstantInt>(V);
if (!C)
return false;
APInt Val = C->getValue();
if (SignedOp && Val.isNegative())
Val = -Val;
return Val.isPowerOf2();
}
static bool isSigned(unsigned int Opcode) {
return Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
}
static bool runImpl(Function &F, const TargetLowering &TLI) {
SmallVector<BinaryOperator *, 4> Replace;
bool Modified = false;
unsigned MaxLegalDivRemBitWidth = TLI.getMaxDivRemBitWidthSupported();
if (ExpandDivRemBits != llvm::IntegerType::MAX_INT_BITS)
MaxLegalDivRemBitWidth = ExpandDivRemBits;
if (MaxLegalDivRemBitWidth >= llvm::IntegerType::MAX_INT_BITS)
return false;
for (auto &I : instructions(F)) {
switch (I.getOpcode()) {
case Instruction::UDiv:
case Instruction::SDiv:
case Instruction::URem:
case Instruction::SRem: {
// TODO: This doesn't handle vectors.
auto *IntTy = dyn_cast<IntegerType>(I.getType());
if (!IntTy || IntTy->getIntegerBitWidth() <= MaxLegalDivRemBitWidth)
continue;
// The backend has peephole optimizations for powers of two.
if (isConstantPowerOfTwo(I.getOperand(1), isSigned(I.getOpcode())))
continue;
Replace.push_back(&cast<BinaryOperator>(I));
Modified = true;
break;
}
default:
break;
}
}
if (Replace.empty())
return false;
while (!Replace.empty()) {
BinaryOperator *I = Replace.pop_back_val();
if (I->getOpcode() == Instruction::UDiv ||
I->getOpcode() == Instruction::SDiv) {
expandDivision(I);
} else {
expandRemainder(I);
}
}
return Modified;
}
namespace {
class ExpandLargeDivRemLegacyPass : public FunctionPass {
public:
static char ID;
ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
initializeExpandLargeDivRemLegacyPassPass(*PassRegistry::getPassRegistry());
}
bool runOnFunction(Function &F) override {
auto *TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
auto *TLI = TM->getSubtargetImpl(F)->getTargetLowering();
return runImpl(F, *TLI);
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<TargetPassConfig>();
AU.addPreserved<AAResultsWrapperPass>();
AU.addPreserved<GlobalsAAWrapperPass>();
}
};
} // namespace
char ExpandLargeDivRemLegacyPass::ID = 0;
INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
"Expand large div/rem", false, false)
INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
"Expand large div/rem", false, false)
FunctionPass *llvm::createExpandLargeDivRemPass() {
return new ExpandLargeDivRemLegacyPass();
}
|
