Index: llvm/trunk/include/llvm/Transforms/Utils/BypassSlowDivision.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/BypassSlowDivision.h +++ llvm/trunk/include/llvm/Transforms/Utils/BypassSlowDivision.h @@ -32,6 +32,8 @@ AssertingVH Dividend; AssertingVH Divisor; + DivRemMapKey() = default; + DivRemMapKey(bool InSignedOp, Value *InDividend, Value *InDivisor) : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {} }; Index: llvm/trunk/lib/Transforms/Scalar/DivRemPairs.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/DivRemPairs.cpp +++ llvm/trunk/lib/Transforms/Scalar/DivRemPairs.cpp @@ -1,4 +1,4 @@ -//===- DivRemPairs.cpp - Hoist/decompose division and remainder -*- C++ -*-===// +//===- DivRemPairs.cpp - Hoist/[dr]ecompose division and remainder --------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,7 +6,7 @@ // //===----------------------------------------------------------------------===// // -// This pass hoists and/or decomposes integer division and remainder +// This pass hoists and/or decomposes/recomposes integer division and remainder // instructions to enable CFG improvements and better codegen. // //===----------------------------------------------------------------------===// @@ -19,20 +19,57 @@ #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" +#include "llvm/IR/PatternMatch.h" #include "llvm/Pass.h" #include "llvm/Support/DebugCounter.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BypassSlowDivision.h" using namespace llvm; +using namespace llvm::PatternMatch; #define DEBUG_TYPE "div-rem-pairs" STATISTIC(NumPairs, "Number of div/rem pairs"); +STATISTIC(NumRecomposed, "Number of instructions recomposed"); 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"); +namespace { +struct ExpandedMatch { + DivRemMapKey Key; + Instruction *Value; +}; +} // namespace + +/// See if we can match: (which is the form we expand into) +/// X - ((X ?/ Y) * Y) +/// which is equivalent to: +/// X ?% Y +static llvm::Optional matchExpandedRem(Instruction &I) { + Value *Dividend, *XroundedDownToMultipleOfY; + if (!match(&I, m_Sub(m_Value(Dividend), m_Value(XroundedDownToMultipleOfY)))) + return llvm::None; + + Value *Divisor; + Instruction *Div; + // Look for ((X / Y) * Y) + if (!match( + XroundedDownToMultipleOfY, + m_c_Mul(m_CombineAnd(m_IDiv(m_Specific(Dividend), m_Value(Divisor)), + m_Instruction(Div)), + m_Deferred(Divisor)))) + return llvm::None; + + ExpandedMatch M; + M.Key.SignedOp = Div->getOpcode() == Instruction::SDiv; + M.Key.Dividend = Dividend; + M.Key.Divisor = Divisor; + M.Value = &I; + return M; +} + /// A thin wrapper to store two values that we matched as div-rem pair. /// We want this extra indirection to avoid dealing with RAUW'ing the map keys. struct DivRemPairWorklistEntry { @@ -62,6 +99,16 @@ /// In this pair, what are the divident and divisor? Value *getDividend() const { return DivInst->getOperand(0); } Value *getDivisor() const { return DivInst->getOperand(1); } + + bool isRemExpanded() const { + switch (RemInst->getOpcode()) { + case Instruction::SRem: + case Instruction::URem: + return false; // single 'rem' instruction - unexpanded form. + default: + return true; // anything else means we have remainder in expanded form. + } + } }; using DivRemWorklistTy = SmallVector; @@ -87,6 +134,8 @@ 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; + else if (auto Match = matchExpandedRem(I)) + RemMap[Match->Key] = Match->Value; } } @@ -137,11 +186,42 @@ // Process each entry in the worklist. for (DivRemPairWorklistEntry &E : Worklist) { + if (!DebugCounter::shouldExecute(DRPCounter)) + continue; + bool HasDivRemOp = TTI.hasDivRemOp(E.getType(), E.isSigned()); auto &DivInst = E.DivInst; auto &RemInst = E.RemInst; + const bool RemOriginallyWasInExpandedForm = E.isRemExpanded(); + + if (HasDivRemOp && E.isRemExpanded()) { + // The target supports div+rem but the rem is expanded. + // We should recompose it first. + Value *X = E.getDividend(); + Value *Y = E.getDivisor(); + Instruction *RealRem = E.isSigned() ? BinaryOperator::CreateSRem(X, Y) + : BinaryOperator::CreateURem(X, Y); + // Note that we place it right next to the original expanded instruction, + // and letting further handling to move it if needed. + RealRem->setName(RemInst->getName() + ".recomposed"); + RealRem->insertAfter(RemInst); + Instruction *OrigRemInst = RemInst; + // Update AssertingVH<> with new instruction so it doesn't assert. + RemInst = RealRem; + // And replace the original instruction with the new one. + OrigRemInst->replaceAllUsesWith(RealRem); + OrigRemInst->eraseFromParent(); + NumRecomposed++; + // Note that we have left ((X / Y) * Y) around. + // If it had other uses we could rewrite it as X - X % Y + } + + assert((!E.isRemExpanded() || !HasDivRemOp) && + "*If* the target supports div-rem, then by now the RemInst *is* " + "Instruction::[US]Rem."); + // 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. @@ -149,10 +229,18 @@ continue; bool DivDominates = DT.dominates(DivInst, RemInst); - if (!DivDominates && !DT.dominates(RemInst, DivInst)) + if (!DivDominates && !DT.dominates(RemInst, DivInst)) { + // We have matching div-rem pair, but they are in two different blocks, + // neither of which dominates one another. + assert(!RemOriginallyWasInExpandedForm && + "Won't happen for expanded-form rem."); + // FIXME: We could hoist both ops to the common predecessor block? continue; + } - if (!DebugCounter::shouldExecute(DRPCounter)) + // The target does not have a single div/rem operation, + // and the rem is already in expanded form. Nothing to do. + if (!HasDivRemOp && E.isRemExpanded()) continue; if (HasDivRemOp) { @@ -164,9 +252,15 @@ DivInst->moveAfter(RemInst); NumHoisted++; } else { - // The target does not have a single div/rem operation. Decompose the - // remainder calculation as: + // The target does not have a single div/rem operation, + // and the rem is *not* in a already-expanded form. + // Decompose the remainder calculation as: // X % Y --> X - ((X / Y) * Y). + + assert(!RemOriginallyWasInExpandedForm && + "We should not be expanding if the rem was in expanded form to " + "begin with."); + Value *X = E.getDividend(); Value *Y = E.getDivisor(); Instruction *Mul = BinaryOperator::CreateMul(DivInst, Y); Index: llvm/trunk/test/Transforms/DivRemPairs/X86/div-expanded-rem-pair.ll =================================================================== --- llvm/trunk/test/Transforms/DivRemPairs/X86/div-expanded-rem-pair.ll +++ llvm/trunk/test/Transforms/DivRemPairs/X86/div-expanded-rem-pair.ll @@ -7,8 +7,8 @@ ; CHECK-LABEL: @decompose_illegal_srem_same_block( ; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]] ; CHECK-NEXT: [[T0:%.*]] = mul i32 [[DIV]], [[B]] -; CHECK-NEXT: [[REM:%.*]] = sub i32 [[A]], [[T0]] -; CHECK-NEXT: call void @foo(i32 [[REM]], i32 [[DIV]]) +; CHECK-NEXT: [[REM_RECOMPOSED:%.*]] = srem i32 [[A]], [[B]] +; CHECK-NEXT: call void @foo(i32 [[REM_RECOMPOSED]], i32 [[DIV]]) ; CHECK-NEXT: ret void ; %div = sdiv i32 %a, %b @@ -22,8 +22,8 @@ ; CHECK-LABEL: @decompose_illegal_urem_same_block( ; CHECK-NEXT: [[DIV:%.*]] = udiv i32 [[A:%.*]], [[B:%.*]] ; CHECK-NEXT: [[T0:%.*]] = mul i32 [[DIV]], [[B]] -; CHECK-NEXT: [[REM:%.*]] = sub i32 [[A]], [[T0]] -; CHECK-NEXT: call void @foo(i32 [[REM]], i32 [[DIV]]) +; CHECK-NEXT: [[REM_RECOMPOSED:%.*]] = urem i32 [[A]], [[B]] +; CHECK-NEXT: call void @foo(i32 [[REM_RECOMPOSED]], i32 [[DIV]]) ; CHECK-NEXT: ret void ; %div = udiv i32 %a, %b @@ -39,14 +39,14 @@ ; CHECK-LABEL: @hoist_srem( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[DIV:%.*]] = sdiv i16 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[REM_RECOMPOSED:%.*]] = 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: [[T0:%.*]] = mul i16 [[DIV]], [[B]] -; CHECK-NEXT: [[REM:%.*]] = sub i16 [[A]], [[T0]] ; CHECK-NEXT: br label [[END]] ; CHECK: end: -; CHECK-NEXT: [[RET:%.*]] = phi i16 [ [[REM]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[RET:%.*]] = phi i16 [ [[REM_RECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] ; CHECK-NEXT: ret i16 [[RET]] ; entry: @@ -70,14 +70,14 @@ ; CHECK-LABEL: @hoist_urem( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[DIV:%.*]] = udiv i8 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[REM_RECOMPOSED:%.*]] = 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: [[T0:%.*]] = mul i8 [[DIV]], [[B]] -; CHECK-NEXT: [[REM:%.*]] = sub i8 [[A]], [[T0]] ; CHECK-NEXT: br label [[END]] ; CHECK: end: -; CHECK-NEXT: [[RET:%.*]] = phi i8 [ [[REM]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[RET:%.*]] = phi i8 [ [[REM_RECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ] ; CHECK-NEXT: ret i8 [[RET]] ; entry: @@ -122,11 +122,11 @@ ; CHECK-NEXT: [[T0:%.*]] = mul nsw i32 [[Z:%.*]], [[Y:%.*]] ; CHECK-NEXT: [[T1:%.*]] = sdiv i32 [[X:%.*]], [[T0]] ; CHECK-NEXT: [[T2:%.*]] = mul nsw i32 [[T0]], [[T1]] -; CHECK-NEXT: [[T3:%.*]] = sub nsw i32 [[X]], [[T2]] -; CHECK-NEXT: [[T4:%.*]] = sdiv i32 [[T3]], [[Y]] +; CHECK-NEXT: [[T3_RECOMPOSED:%.*]] = srem i32 [[X]], [[T0]] +; CHECK-NEXT: [[T4:%.*]] = sdiv i32 [[T3_RECOMPOSED]], [[Y]] ; CHECK-NEXT: [[T5:%.*]] = mul nsw i32 [[T4]], [[Y]] -; CHECK-NEXT: [[T6:%.*]] = sub nsw i32 [[T3]], [[T5]] -; CHECK-NEXT: ret i32 [[T6]] +; CHECK-NEXT: [[T6_RECOMPOSED:%.*]] = srem i32 [[T3_RECOMPOSED]], [[Y]] +; CHECK-NEXT: ret i32 [[T6_RECOMPOSED]] ; %t0 = mul nsw i32 %Z, %Y %t1 = sdiv i32 %X, %t0 Index: llvm/trunk/test/Transforms/DivRemPairs/X86/div-rem-pairs.ll =================================================================== --- llvm/trunk/test/Transforms/DivRemPairs/X86/div-rem-pairs.ll +++ llvm/trunk/test/Transforms/DivRemPairs/X86/div-rem-pairs.ll @@ -173,11 +173,11 @@ ; CHECK-NEXT: [[T0:%.*]] = mul nsw i32 [[Z:%.*]], [[Y:%.*]] ; CHECK-NEXT: [[T1:%.*]] = sdiv i32 [[X:%.*]], [[T0]] ; CHECK-NEXT: [[T2:%.*]] = mul nsw i32 [[T0]], [[T1]] -; CHECK-NEXT: [[T3:%.*]] = sub nsw i32 [[X]], [[T2]] -; CHECK-NEXT: [[T4:%.*]] = sdiv i32 [[T3]], [[Y]] +; CHECK-NEXT: [[T3_RECOMPOSED:%.*]] = srem i32 [[X]], [[T0]] +; CHECK-NEXT: [[T4:%.*]] = sdiv i32 [[T3_RECOMPOSED]], [[Y]] ; CHECK-NEXT: [[T5:%.*]] = mul nsw i32 [[T4]], [[Y]] -; CHECK-NEXT: [[T6:%.*]] = sub nsw i32 [[T3]], [[T5]] -; CHECK-NEXT: ret i32 [[T6]] +; CHECK-NEXT: [[T6_RECOMPOSED:%.*]] = srem i32 [[T3_RECOMPOSED]], [[Y]] +; CHECK-NEXT: ret i32 [[T6_RECOMPOSED]] ; %t0 = mul nsw i32 %Z, %Y %t1 = sdiv i32 %X, %t0