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 } 140