diff --git a/llvm/lib/Transforms/Scalar/DivRemPairs.cpp b/llvm/lib/Transforms/Scalar/DivRemPairs.cpp index e1bc590c5c9a..ffcf34f1cf7a 100644 --- a/llvm/lib/Transforms/Scalar/DivRemPairs.cpp +++ b/llvm/lib/Transforms/Scalar/DivRemPairs.cpp @@ -1,211 +1,217 @@ //===- DivRemPairs.cpp - Hoist/decompose division and remainder -*- C++ -*-===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This pass hoists and/or decomposes integer division and remainder // instructions to enable CFG improvements and better codegen. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/DivRemPairs.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/Pass.h" +#include "llvm/Support/DebugCounter.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BypassSlowDivision.h" using namespace llvm; #define DEBUG_TYPE "div-rem-pairs" STATISTIC(NumPairs, "Number of div/rem pairs"); STATISTIC(NumHoisted, "Number of instructions hoisted"); STATISTIC(NumDecomposed, "Number of instructions decomposed"); +DEBUG_COUNTER(DRPCounter, "div-rem-pairs-transform", + "Controls transformations in div-rem-pairs pass"); /// Find matching pairs of integer div/rem ops (they have the same numerator, /// denominator, and signedness). If they exist in different basic blocks, bring /// them together by hoisting or replace the common division operation that is /// implicit in the remainder: /// X % Y <--> X - ((X / Y) * Y). /// /// We can largely ignore the normal safety and cost constraints on speculation /// of these ops when we find a matching pair. This is because we are already /// guaranteed that any exceptions and most cost are already incurred by the /// first member of the pair. /// /// Note: This transform could be an oddball enhancement to EarlyCSE, GVN, or /// SimplifyCFG, but it's split off on its own because it's different enough /// that it doesn't quite match the stated objectives of those passes. static bool optimizeDivRem(Function &F, const TargetTransformInfo &TTI, const DominatorTree &DT) { bool Changed = false; // Insert all divide and remainder instructions into maps keyed by their // operands and opcode (signed or unsigned). DenseMap DivMap; // Use a MapVector for RemMap so that instructions are moved/inserted in a // deterministic order. MapVector RemMap; for (auto &BB : F) { for (auto &I : BB) { if (I.getOpcode() == Instruction::SDiv) DivMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I; else if (I.getOpcode() == Instruction::UDiv) DivMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I; else if (I.getOpcode() == Instruction::SRem) RemMap[DivRemMapKey(true, I.getOperand(0), I.getOperand(1))] = &I; else if (I.getOpcode() == Instruction::URem) RemMap[DivRemMapKey(false, I.getOperand(0), I.getOperand(1))] = &I; } } // We can iterate over either map because we are only looking for matched // pairs. Choose remainders for efficiency because they are usually even more // rare than division. for (auto &RemPair : RemMap) { // Find the matching division instruction from the division map. Instruction *DivInst = DivMap[RemPair.first]; if (!DivInst) continue; // We have a matching pair of div/rem instructions. If one dominates the // other, hoist and/or replace one. NumPairs++; Instruction *RemInst = RemPair.second; bool IsSigned = DivInst->getOpcode() == Instruction::SDiv; bool HasDivRemOp = TTI.hasDivRemOp(DivInst->getType(), IsSigned); // If the target supports div+rem and the instructions are in the same block // already, there's nothing to do. The backend should handle this. If the // target does not support div+rem, then we will decompose the rem. if (HasDivRemOp && RemInst->getParent() == DivInst->getParent()) continue; bool DivDominates = DT.dominates(DivInst, RemInst); if (!DivDominates && !DT.dominates(RemInst, DivInst)) continue; + if (!DebugCounter::shouldExecute(DRPCounter)) + continue; + if (HasDivRemOp) { // The target has a single div/rem operation. Hoist the lower instruction // to make the matched pair visible to the backend. if (DivDominates) RemInst->moveAfter(DivInst); else DivInst->moveAfter(RemInst); NumHoisted++; } else { // The target does not have a single div/rem operation. Decompose the // remainder calculation as: // X % Y --> X - ((X / Y) * Y). Value *X = RemInst->getOperand(0); Value *Y = RemInst->getOperand(1); Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y); Instruction *Sub = BinaryOperator::CreateSub(X, Mul); // If the remainder dominates, then hoist the division up to that block: // // bb1: // %rem = srem %x, %y // bb2: // %div = sdiv %x, %y // --> // bb1: // %div = sdiv %x, %y // %mul = mul %div, %y // %rem = sub %x, %mul // // If the division dominates, it's already in the right place. The mul+sub // will be in a different block because we don't assume that they are // cheap to speculatively execute: // // bb1: // %div = sdiv %x, %y // bb2: // %rem = srem %x, %y // --> // bb1: // %div = sdiv %x, %y // bb2: // %mul = mul %div, %y // %rem = sub %x, %mul // // If the div and rem are in the same block, we do the same transform, // but any code movement would be within the same block. if (!DivDominates) DivInst->moveBefore(RemInst); Mul->insertAfter(RemInst); Sub->insertAfter(Mul); // Now kill the explicit remainder. We have replaced it with: // (sub X, (mul (div X, Y), Y) RemInst->replaceAllUsesWith(Sub); RemInst->eraseFromParent(); NumDecomposed++; } Changed = true; } return Changed; } // Pass manager boilerplate below here. namespace { struct DivRemPairsLegacyPass : public FunctionPass { static char ID; DivRemPairsLegacyPass() : FunctionPass(ID) { initializeDivRemPairsLegacyPassPass(*PassRegistry::getPassRegistry()); } void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.addRequired(); AU.setPreservesCFG(); AU.addPreserved(); AU.addPreserved(); FunctionPass::getAnalysisUsage(AU); } bool runOnFunction(Function &F) override { if (skipFunction(F)) return false; auto &TTI = getAnalysis().getTTI(F); auto &DT = getAnalysis().getDomTree(); return optimizeDivRem(F, TTI, DT); } }; } char DivRemPairsLegacyPass::ID = 0; INITIALIZE_PASS_BEGIN(DivRemPairsLegacyPass, "div-rem-pairs", "Hoist/decompose integer division and remainder", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_END(DivRemPairsLegacyPass, "div-rem-pairs", "Hoist/decompose integer division and remainder", false, false) FunctionPass *llvm::createDivRemPairsPass() { return new DivRemPairsLegacyPass(); } PreservedAnalyses DivRemPairsPass::run(Function &F, FunctionAnalysisManager &FAM) { TargetTransformInfo &TTI = FAM.getResult(F); DominatorTree &DT = FAM.getResult(F); if (!optimizeDivRem(F, TTI, DT)) return PreservedAnalyses::all(); // TODO: This pass just hoists/replaces math ops - all analyses are preserved? PreservedAnalyses PA; PA.preserveSet(); PA.preserve(); return PA; } diff --git a/llvm/test/Other/debugcounter-divrempairs.ll b/llvm/test/Other/debugcounter-divrempairs.ll new file mode 100644 index 000000000000..8da10091274d --- /dev/null +++ b/llvm/test/Other/debugcounter-divrempairs.ll @@ -0,0 +1,90 @@ +; RUN: opt < %s -div-rem-pairs -debug-counter=div-rem-pairs-transform-skip=1,div-rem-pairs-transform-count=1 \ +; RUN: -S -mtriple=x86_64-unknown-unknown | FileCheck %s +;; Test that, with debug counters on, we only skip the first div-rem-pairs opportunity, optimize one after it, +;; and then ignore all the others. There is 1 optimization opportunity in f1, 2 in f2, and another 1 in f3, +;; only the first one in f2 will be performed. + +define i64 @f1(i64 %a, i64 %b) { +; CHECK-LABEL: @f1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[REM:%.*]] = urem i64 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i64 [[REM]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: [[DIV:%.*]] = udiv i64 %a, %b +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i64 [ [[DIV]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i64 [[RET]] +; +entry: + %rem = urem i64 %a, %b + %cmp = icmp eq i64 %rem, 42 + br i1 %cmp, label %if, label %end + +if: + %div = udiv i64 %a, %b + br label %end + +end: + %ret = phi i64 [ %div, %if ], [ 3, %entry ] + ret i64 %ret +} + +define i16 @f2(i16 %a, i16 %b) { +; CHECK-LABEL: @f2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[DIV1:%.*]] = sdiv i16 %a, %b +; CHECK-NEXT: [[REM1:%.*]] = srem i16 %a, %b +; CHECK-NEXT: [[DIV2:%.*]] = udiv i16 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[DIV1]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: [[REM2:%.*]] = urem i16 %a, %b +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i16 [ [[REM1]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i16 [[RET]] +; +entry: + %div1 = sdiv i16 %a, %b + %div2 = udiv i16 %a, %b + %cmp = icmp eq i16 %div1, 42 + br i1 %cmp, label %if, label %end + +if: + %rem1 = srem i16 %a, %b + %rem2 = urem i16 %a, %b + br label %end + +end: + %ret = phi i16 [ %rem1, %if ], [ 3, %entry ] + ret i16 %ret +} + +define i32 @f3(i32 %a, i32 %b) { +; CHECK-LABEL: @f3( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[REM:%.*]] = srem i32 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 %a, %b +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[DIV]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i32 [[RET]] +; +entry: + %rem = srem i32 %a, %b + %cmp = icmp eq i32 %rem, 42 + br i1 %cmp, label %if, label %end + +if: + %div = sdiv i32 %a, %b + br label %end + +end: + %ret = phi i32 [ %div, %if ], [ 3, %entry ] + ret i32 %ret +} \ No newline at end of file