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