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/IR/IRBuilder.h" 23 #include "llvm/IR/InstIterator.h" 24 #include "llvm/IR/PassManager.h" 25 #include "llvm/InitializePasses.h" 26 #include "llvm/Pass.h" 27 #include "llvm/Support/CommandLine.h" 28 #include "llvm/Transforms/Utils/IntegerDivision.h" 29 30 using namespace llvm; 31 32 static cl::opt<unsigned> 33 ExpandDivRemBits("expand-div-rem-bits", cl::Hidden, cl::init(128), 34 cl::desc("div and rem instructions on integers with " 35 "more than <N> bits are expanded.")); 36 37 static bool runImpl(Function &F) { 38 SmallVector<BinaryOperator *, 4> Replace; 39 bool Modified = false; 40 41 for (auto &I : instructions(F)) { 42 switch (I.getOpcode()) { 43 case Instruction::UDiv: 44 case Instruction::SDiv: 45 case Instruction::URem: 46 case Instruction::SRem: { 47 // TODO: This doesn't handle vectors. 48 auto *IntTy = dyn_cast<IntegerType>(I.getType()); 49 if (!IntTy || IntTy->getIntegerBitWidth() <= ExpandDivRemBits) 50 continue; 51 52 Replace.push_back(&cast<BinaryOperator>(I)); 53 Modified = true; 54 break; 55 } 56 default: 57 break; 58 } 59 } 60 61 if (Replace.empty()) 62 return false; 63 64 while (!Replace.empty()) { 65 BinaryOperator *I = Replace.pop_back_val(); 66 67 if (I->getOpcode() == Instruction::UDiv || 68 I->getOpcode() == Instruction::SDiv) { 69 expandDivision(I); 70 } else { 71 expandRemainder(I); 72 } 73 } 74 75 return Modified; 76 } 77 78 PreservedAnalyses ExpandLargeDivRemPass::run(Function &F, 79 FunctionAnalysisManager &AM) { 80 bool Changed = runImpl(F); 81 82 if (Changed) 83 return PreservedAnalyses::none(); 84 85 return PreservedAnalyses::all(); 86 } 87 88 class ExpandLargeDivRemLegacyPass : public FunctionPass { 89 public: 90 static char ID; 91 92 ExpandLargeDivRemLegacyPass() : FunctionPass(ID) { 93 initializeExpandLargeDivRemLegacyPassPass(*PassRegistry::getPassRegistry()); 94 } 95 96 bool runOnFunction(Function &F) override { return runImpl(F); } 97 98 void getAnalysisUsage(AnalysisUsage &AU) const override { 99 AU.addPreserved<AAResultsWrapperPass>(); 100 AU.addPreserved<GlobalsAAWrapperPass>(); 101 } 102 }; 103 104 char ExpandLargeDivRemLegacyPass::ID = 0; 105 INITIALIZE_PASS_BEGIN(ExpandLargeDivRemLegacyPass, "expand-large-div-rem", 106 "Expand large div/rem", false, false) 107 INITIALIZE_PASS_END(ExpandLargeDivRemLegacyPass, "expand-large-div-rem", 108 "Expand large div/rem", false, false) 109 110 FunctionPass *llvm::createExpandLargeDivRemPass() { 111 return new ExpandLargeDivRemLegacyPass(); 112 } 113