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
34using namespace llvm;
35
36static 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
42static 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
53static bool isSigned(unsigned int Opcode) {
54  return Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
55}
56
57static 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
109namespace {
110class ExpandLargeDivRemLegacyPass : public FunctionPass {
111public:
112  static char ID;
113
114  ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
115    initializeExpandLargeDivRemLegacyPassPass(*PassRegistry::getPassRegistry());
116  }
117
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
124  void getAnalysisUsage(AnalysisUsage &AU) const override {
125    AU.addRequired<TargetPassConfig>();
126    AU.addPreserved<AAResultsWrapperPass>();
127    AU.addPreserved<GlobalsAAWrapperPass>();
128  }
129};
130} // namespace
131
132PreservedAnalyses 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
139char ExpandLargeDivRemLegacyPass::ID = 0;
140INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
141                      "Expand large div/rem", false, false)
142INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
143                    "Expand large div/rem", false, false)
144
145FunctionPass *llvm::createExpandLargeDivRemPass() {
146  return new ExpandLargeDivRemLegacyPass();
147}
148