llvm/lib/CodeGen/ExpandLargeDivRem.cpp

   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 }