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/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
  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
  53 static bool isSigned(unsigned int Opcode) {
  54   return Opcode == Instruction::SDiv || Opcode == Instruction::SRem;
  55 }
  56
  57 static void scalarize(BinaryOperator *BO,
  58                       SmallVectorImpl<BinaryOperator *> &Replace) {
  59   VectorType *VTy = cast<FixedVectorType>(BO->getType());
  60
  61   IRBuilder<> Builder(BO);
  62
  63   unsigned NumElements = VTy->getElementCount().getFixedValue();
  64   Value *Result = PoisonValue::get(VTy);
  65   for (unsigned Idx = 0; Idx < NumElements; ++Idx) {
  66     Value *LHS = Builder.CreateExtractElement(BO->getOperand(0), Idx);
  67     Value *RHS = Builder.CreateExtractElement(BO->getOperand(1), Idx);
  68     Value *Op = Builder.CreateBinOp(BO->getOpcode(), LHS, RHS);
  69     Result = Builder.CreateInsertElement(Result, Op, Idx);
  70     if (auto *NewBO = dyn_cast<BinaryOperator>(Op)) {
  71       NewBO->copyIRFlags(Op, true);
  72       Replace.push_back(NewBO);
  73     }
  74   }
  75   BO->replaceAllUsesWith(Result);
  76   BO->dropAllReferences();
  77   BO->eraseFromParent();
  78 }
  79
  80 static bool runImpl(Function &F, const TargetLowering &TLI) {
  81   SmallVector<BinaryOperator *, 4> Replace;
  82   SmallVector<BinaryOperator *, 4> ReplaceVector;
  83   bool Modified = false;
  84
  85   unsigned MaxLegalDivRemBitWidth = TLI.getMaxDivRemBitWidthSupported();
  86   if (ExpandDivRemBits != llvm::IntegerType::MAX_INT_BITS)
  87     MaxLegalDivRemBitWidth = ExpandDivRemBits;
  88
  89   if (MaxLegalDivRemBitWidth >= llvm::IntegerType::MAX_INT_BITS)
  90     return false;
  91
  92   for (auto &I : instructions(F)) {
  93     switch (I.getOpcode()) {
  94     case Instruction::UDiv:
  95     case Instruction::SDiv:
  96     case Instruction::URem:
  97     case Instruction::SRem: {
  98       // TODO: This pass doesn't handle scalable vectors.
  99       if (I.getOperand(0)->getType()->isScalableTy())
 100         continue;
 101
 102       auto *IntTy = dyn_cast<IntegerType>(I.getType()->getScalarType());
 103       if (!IntTy || IntTy->getIntegerBitWidth() <= MaxLegalDivRemBitWidth)
 104         continue;
 105
 106       // The backend has peephole optimizations for powers of two.
 107       // TODO: We don't consider vectors here.
 108       if (isConstantPowerOfTwo(I.getOperand(1), isSigned(I.getOpcode())))
 109         continue;
 110
 111       if (I.getOperand(0)->getType()->isVectorTy())
 112         ReplaceVector.push_back(&cast<BinaryOperator>(I));
 113       else
 114         Replace.push_back(&cast<BinaryOperator>(I));
 115       Modified = true;
 116       break;
 117     }
 118     default:
 119       break;
 120     }
 121   }
 122
 123   while (!ReplaceVector.empty()) {
 124     BinaryOperator *BO = ReplaceVector.pop_back_val();
 125     scalarize(BO, Replace);
 126   }
 127
 128   if (Replace.empty())
 129     return false;
 130
 131   while (!Replace.empty()) {
 132     BinaryOperator *I = Replace.pop_back_val();
 133
 134     if (I->getOpcode() == Instruction::UDiv ||
 135         I->getOpcode() == Instruction::SDiv) {
 136       expandDivision(I);
 137     } else {
 138       expandRemainder(I);
 139     }
 140   }
 141
 142   return Modified;
 143 }
 144
 145 namespace {
 146 class ExpandLargeDivRemLegacyPass : public FunctionPass {
 147 public:
 148   static char ID;
 149
 150   ExpandLargeDivRemLegacyPass() : FunctionPass(ID) {
 151     initializeExpandLargeDivRemLegacyPassPass(*PassRegistry::getPassRegistry());
 152   }
 153
 154   bool runOnFunction(Function &F) override {
 155     auto *TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
 156     auto *TLI = TM->getSubtargetImpl(F)->getTargetLowering();
 157     return runImpl(F, *TLI);
 158   }
 159
 160   void getAnalysisUsage(AnalysisUsage &AU) const override {
 161     AU.addRequired<TargetPassConfig>();
 162     AU.addPreserved<AAResultsWrapperPass>();
 163     AU.addPreserved<GlobalsAAWrapperPass>();
 164   }
 165 };
 166 } // namespace
 167
 168 PreservedAnalyses ExpandLargeDivRemPass::run(Function &F,
 169                                              FunctionAnalysisManager &FAM) {
 170   const TargetSubtargetInfo *STI = TM->getSubtargetImpl(F);
 171   return runImpl(F, *STI->getTargetLowering()) ? PreservedAnalyses::none()
 172                                                : PreservedAnalyses::all();
 173 }
 174
 175 char ExpandLargeDivRemLegacyPass::ID = 0;
 176 INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
 177                       "Expand large div/rem", false, false)
 178 INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem",
 179                     "Expand large div/rem", false, false)
 180
 181 FunctionPass *llvm::createExpandLargeDivRemPass() {
 182   return new ExpandLargeDivRemLegacyPass();
 183 }