From 3745f0675ab507814af923afc22739a976488782 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Mon, 4 Dec 2017 19:21:58 +0000 Subject: [PATCH] [BypassSlowDivision] Improve our handling of divisions by constants (This reapplies r314253. r314253 was reverted on r314482 because of a correctness regression on P100, but that regression was identified to be something else.) Summary: Don't bail out on constant divisors for divisions that can be narrowed without introducing control flow . This gives us a 32 bit multiply instead of an emulated 64 bit multiply in the generated PTX assembly. Reviewers: jlebar Subscribers: jholewinski, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38265 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@319677 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/BypassSlowDivision.cpp | 20 ++++-- .../CodeGenPrepare/NVPTX/bypass-slow-div.ll | 77 ++++++++++++++++++++++ 2 files changed, 90 insertions(+), 7 deletions(-) diff --git a/lib/Transforms/Utils/BypassSlowDivision.cpp b/lib/Transforms/Utils/BypassSlowDivision.cpp index e9c14c93a9a..f711b192f60 100644 --- a/lib/Transforms/Utils/BypassSlowDivision.cpp +++ b/lib/Transforms/Utils/BypassSlowDivision.cpp @@ -352,11 +352,6 @@ Optional FastDivInsertionTask::insertFastDivAndRem() { Value *Dividend = SlowDivOrRem->getOperand(0); Value *Divisor = SlowDivOrRem->getOperand(1); - if (isa(Divisor)) { - // Keep division by a constant for DAGCombiner. - return None; - } - VisitedSetTy SetL; ValueRange DividendRange = getValueRange(Dividend, SetL); if (DividendRange == VALRNG_LIKELY_LONG) @@ -372,7 +367,9 @@ Optional FastDivInsertionTask::insertFastDivAndRem() { if (DividendShort && DivisorShort) { // If both operands are known to be short then just replace the long - // division with a short one in-place. + // division with a short one in-place. Since we're not introducing control + // flow in this case, narrowing the division is always a win, even if the + // divisor is a constant (and will later get replaced by a multiplication). IRBuilder<> Builder(SlowDivOrRem); Value *TruncDividend = Builder.CreateTrunc(Dividend, BypassType); @@ -382,7 +379,16 @@ Optional FastDivInsertionTask::insertFastDivAndRem() { Value *ExtDiv = Builder.CreateZExt(TruncDiv, getSlowType()); Value *ExtRem = Builder.CreateZExt(TruncRem, getSlowType()); return QuotRemPair(ExtDiv, ExtRem); - } else if (DividendShort && !isSignedOp()) { + } + + if (isa(Divisor)) { + // If the divisor is not a constant, DAGCombiner will convert it to a + // multiplication by a magic constant. It isn't clear if it is worth + // introducing control flow to get a narrower multiply. + return None; + } + + if (DividendShort && !isSignedOp()) { // If the division is unsigned and Dividend is known to be short, then // either // 1) Divisor is less or equal to Dividend, and the result can be computed diff --git a/test/Transforms/CodeGenPrepare/NVPTX/bypass-slow-div.ll b/test/Transforms/CodeGenPrepare/NVPTX/bypass-slow-div.ll index 4846d52f4d2..4d824e450ff 100644 --- a/test/Transforms/CodeGenPrepare/NVPTX/bypass-slow-div.ll +++ b/test/Transforms/CodeGenPrepare/NVPTX/bypass-slow-div.ll @@ -27,3 +27,80 @@ define void @rem_only(i64 %a, i64 %b, i64* %retptr) { store i64 %d, i64* %retptr ret void } + +; CHECK-LABEL: @udiv_by_constant( +define i64 @udiv_by_constant(i32 %a) { +; CHECK-NEXT: [[A_ZEXT:%.*]] = zext i32 [[A:%.*]] to i64 +; CHECK-NEXT: [[TMP1:%.*]] = trunc i64 [[A_ZEXT]] to i32 +; CHECK-NEXT: [[TMP2:%.*]] = udiv i32 [[TMP1]], 50 +; CHECK-NEXT: [[TMP3:%.*]] = zext i32 [[TMP2]] to i64 +; CHECK-NEXT: ret i64 [[TMP3]] + + %a.zext = zext i32 %a to i64 + %wide.div = udiv i64 %a.zext, 50 + ret i64 %wide.div +} + +; CHECK-LABEL: @urem_by_constant( +define i64 @urem_by_constant(i32 %a) { +; CHECK-NEXT: [[A_ZEXT:%.*]] = zext i32 [[A:%.*]] to i64 +; CHECK-NEXT: [[TMP1:%.*]] = trunc i64 [[A_ZEXT]] to i32 +; CHECK-NEXT: [[TMP2:%.*]] = urem i32 [[TMP1]], 50 +; CHECK-NEXT: [[TMP3:%.*]] = zext i32 [[TMP2]] to i64 +; CHECK-NEXT: ret i64 [[TMP3]] + + %a.zext = zext i32 %a to i64 + %wide.div = urem i64 %a.zext, 50 + ret i64 %wide.div +} + +; Negative test: instead of emitting a runtime check on %a, we prefer to let the +; DAGCombiner transform this division by constant into a multiplication (with a +; "magic constant"). +; +; CHECK-LABEL: @udiv_by_constant_negative_0( +define i64 @udiv_by_constant_negative_0(i64 %a) { +; CHECK-NEXT: [[WIDE_DIV:%.*]] = udiv i64 [[A:%.*]], 50 +; CHECK-NEXT: ret i64 [[WIDE_DIV]] + + %wide.div = udiv i64 %a, 50 + ret i64 %wide.div +} + +; Negative test: while we know the dividend is short, the divisor isn't. This +; test is here for completeness, but instcombine will optimize this to return 0. +; +; CHECK-LABEL: @udiv_by_constant_negative_1( +define i64 @udiv_by_constant_negative_1(i32 %a) { +; CHECK-NEXT: [[A_ZEXT:%.*]] = zext i32 [[A:%.*]] to i64 +; CHECK-NEXT: [[WIDE_DIV:%.*]] = udiv i64 [[A_ZEXT]], 8589934592 +; CHECK-NEXT: ret i64 [[WIDE_DIV]] + + %a.zext = zext i32 %a to i64 + %wide.div = udiv i64 %a.zext, 8589934592 ;; == 1 << 33 + ret i64 %wide.div +} + +; URem version of udiv_by_constant_negative_0 +; +; CHECK-LABEL: @urem_by_constant_negative_0( +define i64 @urem_by_constant_negative_0(i64 %a) { +; CHECK-NEXT: [[WIDE_DIV:%.*]] = urem i64 [[A:%.*]], 50 +; CHECK-NEXT: ret i64 [[WIDE_DIV]] + + %wide.div = urem i64 %a, 50 + ret i64 %wide.div +} + +; URem version of udiv_by_constant_negative_1 +; +; CHECK-LABEL: @urem_by_constant_negative_1( +define i64 @urem_by_constant_negative_1(i32 %a) { +; CHECK-NEXT: [[A_ZEXT:%.*]] = zext i32 [[A:%.*]] to i64 +; CHECK-NEXT: [[WIDE_DIV:%.*]] = urem i64 [[A_ZEXT]], 8589934592 +; CHECK-NEXT: ret i64 [[WIDE_DIV]] + + %a.zext = zext i32 %a to i64 + %wide.div = urem i64 %a.zext, 8589934592 ;; == 1 << 33 + ret i64 %wide.div +} -- 2.11.0