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/ADT/SmallVector.h"
18 #include "llvm/ADT/StringExtras.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 
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 
52 static bool isSigned(unsigned int Opcode) {
53   return Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
54 }
55 
56 static bool runImpl(Function &F, const TargetLowering &TLI) {
57   SmallVector<BinaryOperator *, 4> Replace;
58   bool Modified = false;
59 
60   unsigned MaxLegalDivRemBitWidth = TLI.getMaxDivRemBitWidthSupported();
61   if (ExpandDivRemBits != llvm::IntegerType::MAX_INT_BITS)
62     MaxLegalDivRemBitWidth = ExpandDivRemBits;
63 
64   if (MaxLegalDivRemBitWidth >= llvm::IntegerType::MAX_INT_BITS)
65     return false;
66 
67   for (auto &I : instructions(F)) {
68     switch (I.getOpcode()) {
69     case Instruction::UDiv:
70     case Instruction::SDiv:
71     case Instruction::URem:
72     case Instruction::SRem: {
73       // TODO: This doesn't handle vectors.
74       auto *IntTy = dyn_cast<IntegerType>(I.getType());
75       if (!IntTy || IntTy->getIntegerBitWidth() <= MaxLegalDivRemBitWidth)
76         continue;
77 
78       // The backend has peephole optimizations for powers of two.
79       if (isConstantPowerOfTwo(I.getOperand(1), isSigned(I.getOpcode())))
80         continue;
81 
82       Replace.push_back(&cast<BinaryOperator>(I));
83       Modified = true;
84       break;
85     }
86     default:
87       break;
88     }
89   }
90 
91   if (Replace.empty())
92     return false;
93 
94   while (!Replace.empty()) {
95     BinaryOperator *I = Replace.pop_back_val();
96 
97     if (I->getOpcode() == Instruction::UDiv ||
98         I->getOpcode() == Instruction::SDiv) {
99       expandDivision(I);
100     } else {
101       expandRemainder(I);
102     }
103   }
104 
105   return Modified;
106 }
107 
108 namespace {
109 class ExpandLargeDivRemLegacyPass : public FunctionPass {
110 public:
111   static char ID;
112 
113   ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
114     initializeExpandLargeDivRemLegacyPassPass(*PassRegistry::getPassRegistry());
115   }
116 
117   bool runOnFunction(Function &F) override {
118     auto *TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
119     auto *TLI = TM->getSubtargetImpl(F)->getTargetLowering();
120     return runImpl(F, *TLI);
121   }
122 
123   void getAnalysisUsage(AnalysisUsage &AU) const override {
124     AU.addRequired<TargetPassConfig>();
125     AU.addPreserved<AAResultsWrapperPass>();
126     AU.addPreserved<GlobalsAAWrapperPass>();
127   }
128 };
129 } // namespace
130 
131 char ExpandLargeDivRemLegacyPass::ID = 0;
132 INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
133                       "Expand large div/rem", false, false)
134 INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
135                     "Expand large div/rem", false, false)
136 
137 FunctionPass *llvm::createExpandLargeDivRemPass() {
138   return new ExpandLargeDivRemLegacyPass();
139 }
140