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