Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -112,6 +112,7 @@ void initializeDependenceAnalysisWrapperPassPass(PassRegistry&); void initializeDetectDeadLanesPass(PassRegistry&); void initializeDivergenceAnalysisPass(PassRegistry&); +void initializeDivRemHoistLegacyPassPass(PassRegistry&); void initializeDomOnlyPrinterPass(PassRegistry&); void initializeDomOnlyViewerPass(PassRegistry&); void initializeDomPrinterPass(PassRegistry&); Index: include/llvm/Transforms/Scalar.h =================================================================== --- include/llvm/Transforms/Scalar.h +++ include/llvm/Transforms/Scalar.h @@ -377,6 +377,12 @@ //===----------------------------------------------------------------------===// // +// DivRemHoist - Hoist integer division and remainder instructions. +// +FunctionPass *createDivRemHoistPass(); + +//===----------------------------------------------------------------------===// +// // MemCpyOpt - This pass performs optimizations related to eliminating memcpy // calls and/or combining multiple stores into memset's. // Index: include/llvm/Transforms/Scalar/DivRemHoist.h =================================================================== --- include/llvm/Transforms/Scalar/DivRemHoist.h +++ include/llvm/Transforms/Scalar/DivRemHoist.h @@ -0,0 +1,31 @@ +//===- DivRemHoist.h - Hoist integer division and remainder ---------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass hoists integer division and remainder instructions to enable CFG +// improvements and better codegen. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_DIVREMHOIST_H +#define LLVM_TRANSFORMS_SCALAR_DIVREMHOIST_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Hoist integer division and remainder instructions to enable CFG +/// improvements and better codegen. +struct DivRemHoistPass : public PassInfoMixin { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &); +}; + +} +#endif // LLVM_TRANSFORMS_SCALAR_DIVREMHOIST_H + Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -92,6 +92,7 @@ #include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h" #include "llvm/Transforms/Scalar/DCE.h" #include "llvm/Transforms/Scalar/DeadStoreElimination.h" +#include "llvm/Transforms/Scalar/DivRemHoist.h" #include "llvm/Transforms/Scalar/EarlyCSE.h" #include "llvm/Transforms/Scalar/Float2Int.h" #include "llvm/Transforms/Scalar/GVN.h" @@ -765,6 +766,11 @@ // And finally clean up LCSSA form before generating code. OptimizePM.addPass(InstSimplifierPass()); + // This is a special-case hoisting opportunity for div/rem ops. It should run + // after other sink/hoist passes to avoid re-sinking, but before SimplifyCFG + // because it can allow flattening of blocks. + OptimizePM.addPass(DivRemHoistPass()); + // LoopSink (and other loop passes since the last simplifyCFG) might have // resulted in single-entry-single-exit or empty blocks. Clean up the CFG. OptimizePM.addPass(SimplifyCFGPass()); Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -142,6 +142,7 @@ FUNCTION_PASS("consthoist", ConstantHoistingPass()) FUNCTION_PASS("correlated-propagation", CorrelatedValuePropagationPass()) FUNCTION_PASS("dce", DCEPass()) +FUNCTION_PASS("div-rem-hoist", DivRemHoistPass()) FUNCTION_PASS("dse", DSEPass()) FUNCTION_PASS("dot-cfg", CFGPrinterPass()) FUNCTION_PASS("dot-cfg-only", CFGOnlyPrinterPass()) Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -673,6 +673,11 @@ // Get rid of LCSSA nodes. MPM.add(createInstructionSimplifierPass()); + // This is a special-case hoisting opportunity for div/rem ops. It should run + // after other sink/hoist passes to avoid re-sinking, but before SimplifyCFG + // because it can allow flattening of blocks. + MPM.add(createDivRemHoistPass()); + // LoopSink (and other loop passes since the last simplifyCFG) might have // resulted in single-entry-single-exit or empty blocks. Clean up the CFG. MPM.add(createCFGSimplificationPass()); Index: lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- lib/Transforms/Scalar/CMakeLists.txt +++ lib/Transforms/Scalar/CMakeLists.txt @@ -7,6 +7,7 @@ CorrelatedValuePropagation.cpp DCE.cpp DeadStoreElimination.cpp + DivRemHoist.cpp EarlyCSE.cpp FlattenCFGPass.cpp Float2Int.cpp Index: lib/Transforms/Scalar/DivRemHoist.cpp =================================================================== --- lib/Transforms/Scalar/DivRemHoist.cpp +++ lib/Transforms/Scalar/DivRemHoist.cpp @@ -0,0 +1,151 @@ +//===- DivRemHoist.cpp - Hoist integer 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 integer division and remainder instructions to enable CFG +// improvements and better codegen. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/DivRemHoist.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/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/BypassSlowDivision.h" +using namespace llvm; + +#define DEBUG_TYPE "div-rem-hoist" +STATISTIC(NumPairs, "Number of div/rem pairs"); +STATISTIC(NumHoisted, "Number of instructions hoisted"); + +/// Find matching pairs of integer div/rem ops (they have the same numerator, +/// denominator, and signedness). If they exist in different basic blocks, try +/// to bring them together. This is profitable because division is a +/// subexpression of 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 hoistDivRem(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, 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.getFirst()]; + if (!DivInst) + continue; + + // We have a matching pair of div/rem instructions. If they are in different + // blocks and one dominates the other, hoist one. + NumPairs++; + Instruction *RemInst = RemPair.getSecond(); + BasicBlock *RemBB = RemInst->getParent(); + BasicBlock *DivBB = DivInst->getParent(); + if (RemBB == DivBB) + continue; + + if (DT.dominates(DivBB, RemBB)) { + // Hoist the rem into the div block if the implicit speculated + // multiplication is not too costly. + if (TTI.getArithmeticInstrCost(Instruction::Mul, RemInst->getType()) > 1) + continue; + RemInst->moveAfter(DivInst); + NumHoisted++; + Changed = true; + } else if (DT.dominates(RemBB, DivBB)) { + // Hoist the div into the rem block. No cost calculation needed here + // because division is an implicit component of remainder. + DivInst->moveAfter(RemInst); + NumHoisted++; + Changed = true; + } + } + + return Changed; +} + +// Pass manager boilerplate below here. + +namespace { +struct DivRemHoistLegacyPass : public FunctionPass { + static char ID; + DivRemHoistLegacyPass() : FunctionPass(ID) { + initializeDivRemHoistLegacyPassPass(*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 hoistDivRem(F, TTI, DT); + } +}; +} + +char DivRemHoistLegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(DivRemHoistLegacyPass, "div-rem-hoist", + "Hoist integer division and remainder", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_END(DivRemHoistLegacyPass, "div-rem-hoist", + "Hoist integer division and remainder", false, false) + +FunctionPass *llvm::createDivRemHoistPass() { + return new DivRemHoistLegacyPass(); +} + +PreservedAnalyses DivRemHoistPass::run(Function &F, + FunctionAnalysisManager &FAM) { + TargetTransformInfo &TTI = FAM.getResult(F); + DominatorTree &DT = FAM.getResult(F); + if (!hoistDivRem(F, TTI, DT)) + return PreservedAnalyses::all(); + // TODO: This pass just hoists math ops, so all analyses are preserved? + PreservedAnalyses PA; + PA.preserveSet(); + PA.preserve(); + return PA; +} Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -40,6 +40,7 @@ initializeCorrelatedValuePropagationPass(Registry); initializeDCELegacyPassPass(Registry); initializeDeadInstEliminationPass(Registry); + initializeDivRemHoistLegacyPassPass(Registry); initializeScalarizerPass(Registry); initializeDSELegacyPassPass(Registry); initializeGuardWideningLegacyPassPass(Registry); Index: test/Other/new-pm-defaults.ll =================================================================== --- test/Other/new-pm-defaults.ll +++ test/Other/new-pm-defaults.ll @@ -205,6 +205,7 @@ ; CHECK-O-NEXT: Running pass: AlignmentFromAssumptionsPass ; CHECK-O-NEXT: Running pass: LoopSinkPass ; CHECK-O-NEXT: Running pass: InstSimplifierPass +; CHECK-O-NEXT: Running pass: DivRemHoistPass ; CHECK-O-NEXT: Running pass: SimplifyCFGPass ; CHECK-O-NEXT: Finished llvm::Function pass manager run. ; CHECK-O-NEXT: Running pass: GlobalDCEPass Index: test/Other/new-pm-thinlto-defaults.ll =================================================================== --- test/Other/new-pm-thinlto-defaults.ll +++ test/Other/new-pm-thinlto-defaults.ll @@ -193,6 +193,7 @@ ; CHECK-POSTLINK-O-NEXT: Running pass: AlignmentFromAssumptionsPass ; CHECK-POSTLINK-O-NEXT: Running pass: LoopSinkPass ; CHECK-POSTLINK-O-NEXT: Running pass: InstSimplifierPass +; CHECK-POSTLINK-O-NEXT: Running pass: DivRemHoistPass ; CHECK-POSTLINK-O-NEXT: Running pass: SimplifyCFGPass ; CHECK-POSTLINK-O-NEXT: Finished llvm::Function pass manager run. ; CHECK-POSTLINK-O-NEXT: Running pass: GlobalDCEPass Index: test/Transforms/DivRemHoist/div-rem-pairs.ll =================================================================== --- test/Transforms/DivRemHoist/div-rem-pairs.ll +++ test/Transforms/DivRemHoist/div-rem-pairs.ll @@ -0,0 +1,271 @@ +; RUN: opt < %s -div-rem-hoist -S | FileCheck %s + +target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-unknown" + +; Hoist the sdiv because it's safe and free. +; PR31028 - https://bugs.llvm.org/show_bug.cgi?id=31028 + +define i32 @hoist_sdiv(i32 %a, i32 %b) { +; CHECK-LABEL: @hoist_sdiv( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[REM:%.*]] = srem i32 %a, %b +; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; 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 +} + +; Hoist the udiv because it's safe and free. + +define i64 @hoist_udiv(i64 %a, i64 %b) { +; CHECK-LABEL: @hoist_udiv( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[REM:%.*]] = urem i64 %a, %b +; CHECK-NEXT: [[DIV:%.*]] = udiv i64 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i64 [[REM]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; 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 +} + +; Hoist the srem because it's safe and the additional cost over div is not great. + +define i16 @hoist_srem(i16 %a, i16 %b) { +; CHECK-LABEL: @hoist_srem( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[DIV:%.*]] = sdiv i16 %a, %b +; CHECK-NEXT: [[REM:%.*]] = srem i16 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[DIV]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i16 [ [[REM]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i16 [[RET]] +; +entry: + %div = sdiv i16 %a, %b + %cmp = icmp eq i16 %div, 42 + br i1 %cmp, label %if, label %end + +if: + %rem = srem i16 %a, %b + br label %end + +end: + %ret = phi i16 [ %rem, %if ], [ 3, %entry ] + ret i16 %ret +} + +; Hoist the urem because it's safe and the additional cost over div is not great. + +define i8 @hoist_urem(i8 %a, i8 %b) { +; CHECK-LABEL: @hoist_urem( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[DIV:%.*]] = udiv i8 %a, %b +; CHECK-NEXT: [[REM:%.*]] = urem i8 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[DIV]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i8 [ [[REM]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i8 [[RET]] +; +entry: + %div = udiv i8 %a, %b + %cmp = icmp eq i8 %div, 42 + br i1 %cmp, label %if, label %end + +if: + %rem = urem i8 %a, %b + br label %end + +end: + %ret = phi i8 [ %rem, %if ], [ 3, %entry ] + ret i8 %ret +} + +; If the ops don't match, don't do anything: signedness. + +define i32 @dont_hoist_udiv(i32 %a, i32 %b) { +; CHECK-LABEL: @dont_hoist_udiv( +; 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:%.*]] = udiv 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 = udiv i32 %a, %b + br label %end + +end: + %ret = phi i32 [ %div, %if ], [ 3, %entry ] + ret i32 %ret +} + +; If the ops don't match, don't do anything: operation. + +define i32 @dont_hoist_srem(i32 %a, i32 %b) { +; CHECK-LABEL: @dont_hoist_srem( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[REM:%.*]] = urem i32 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[REM]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: [[REM2:%.*]] = srem i32 %a, %b +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[REM2]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i32 [[RET]] +; +entry: + %rem = urem i32 %a, %b + %cmp = icmp eq i32 %rem, 42 + br i1 %cmp, label %if, label %end + +if: + %rem2 = srem i32 %a, %b + br label %end + +end: + %ret = phi i32 [ %rem2, %if ], [ 3, %entry ] + ret i32 %ret +} + +; If the ops don't match, don't do anything: operands. + +define i32 @dont_hoist_sdiv(i32 %a, i32 %b, i32 %c) { +; CHECK-LABEL: @dont_hoist_sdiv( +; 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, %c +; 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, %c + br label %end + +end: + %ret = phi i32 [ %div, %if ], [ 3, %entry ] + ret i32 %ret +} + +; If the rem is much more expensive than div, don't do anything. + +define i128 @dont_hoist_urem(i128 %a, i128 %b) { +; CHECK-LABEL: @dont_hoist_urem( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[DIV:%.*]] = udiv i128 %a, %b +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i128 [[DIV]], 42 +; CHECK-NEXT: br i1 [[CMP]], label %if, label %end +; CHECK: if: +; CHECK-NEXT: [[REM:%.*]] = urem i128 %a, %b +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i128 [ [[REM]], %if ], [ 3, %entry ] +; CHECK-NEXT: ret i128 [[RET]] +; +entry: + %div = udiv i128 %a, %b + %cmp = icmp eq i128 %div, 42 + br i1 %cmp, label %if, label %end + +if: + %rem = urem i128 %a, %b + br label %end + +end: + %ret = phi i128 [ %rem, %if ], [ 3, %entry ] + ret i128 %ret +} + +; We don't hoist if one op does not dominate the other, +; but we could hoist both ops to the common predecessor block? + +define i32 @no_domination(i1 %cmp, i32 %a, i32 %b) { +; CHECK-LABEL: @no_domination( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cmp, label %if, label %else +; CHECK: if: +; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 %a, %b +; CHECK-NEXT: br label %end +; CHECK: else: +; CHECK-NEXT: [[REM:%.*]] = srem i32 %a, %b +; CHECK-NEXT: br label %end +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[DIV]], %if ], [ [[REM]], %else ] +; CHECK-NEXT: ret i32 [[RET]] +; +entry: + br i1 %cmp, label %if, label %else + +if: + %div = sdiv i32 %a, %b + br label %end + +else: + %rem = srem i32 %a, %b + br label %end + +end: + %ret = phi i32 [ %div, %if ], [ %rem, %else ] + ret i32 %ret +} +