This is an archive of the discontinued LLVM Phabricator instance.

Differential D87555

[DivRemPairs] Add an initial case for hoisting to a common predecessor.
ClosedPublic

Authored by craig.topper on Sep 11 2020, 8:58 PM.

Details

Reviewers
spatel
lebedev.ri
RKSimon
efriedma
Commits
rGe38b7e894808: [DivRemPairs] Add an initial case for hoisting to a common predecessor.
Summary

This patch adds support for hoisting the division and maybe the
remainder for control flow graphs like this.

PredBB
  |  \
  |  Rem
  |  /
 Div

If we have DivRem we'll hoist both to PredBB. If not we'll just
hoist Div and expand Rem using the Div.

This improves our codegen for something like this

__uint128_t udivmodti4(__uint128_t dividend, __uint128_t divisor, __uint128_t *remainder) {
    if (remainder != 0)
        *remainder = dividend % divisor;
    return dividend / divisor;
}

Diff Detail

Event Timeline

craig.topper created this revision.Sep 11 2020, 8:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 11 2020, 8:58 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
craig.topper requested review of this revision.Sep 11 2020, 8:58 PM
Harbormaster completed remote builds in B71452: Diff 291372.Sep 11 2020, 9:31 PM
lebedev.ri added a comment.Sep 11 2020, 11:40 PM

Can we use DominatorTree::findNearestCommonDominator()?
If not, please add a negative test, where it's unsafe to do so.

llvm/lib/Transforms/Scalar/DivRemPairs.cpp
241

Remove FIXME?

craig.topper added a comment.Sep 12 2020, 12:35 AM
In D87555#2269355, @lebedev.ri wrote:

Can we use DominatorTree::findNearestCommonDominator()?
If not, please add a negative test, where it's unsafe to do so.

The nearest common dominator could put the division on a path that it wasn't going to execute on right? Isn't that not just possibly unsafe but also possibly unprofitable?

llvm/lib/Transforms/Scalar/DivRemPairs.cpp
241

I only handled one specific case. There are other cases that could be handled.

lebedev.ri added a comment.Sep 12 2020, 12:42 AM
In D87555#2269363, @craig.topper wrote:
In D87555#2269355, @lebedev.ri wrote:

Can we use DominatorTree::findNearestCommonDominator()?
If not, please add a negative test, where it's unsafe to do so.

The nearest common dominator could put the division on a path that it wasn't going to execute on right? Isn't that not just possibly unsafe but also possibly unprofitable?

Yep, that's why i'm asking for a negative test - we then could hoist it past the check for divisor being 0.

nikic added a subscriber: nikic.Sep 12 2020, 1:25 AM

Doesn't this need some guaranteed-to-transfer checks for all instructions we're moving across?

craig.topper added a comment.Sep 12 2020, 12:35 PM
In D87555#2269381, @nikic wrote:

Doesn't this need some guaranteed-to-transfer checks for all instructions we're moving across?

Good point. Maybe I'll just make sure they are the first instruction for now? That at least covers the case.

craig.topper planned changes to this revision.Sep 12 2020, 12:35 PM
craig.topper updated this revision to Diff 291448.Sep 13 2020, 1:10 AM

Ensure that the div/rem are the start of their basic blocks so they are guaranteed to execute.

Still need to add negative tests

lebedev.ri added inline comments.Sep 13 2020, 1:16 AM
llvm/lib/Transforms/Scalar/DivRemPairs.cpp
261–262

This is too fragile.
You want to check that every instruction between the place you hoist to,
and each div/rem instruction is isGuaranteedToTransferExecutionToSuccessor()

Harbormaster completed remote builds in B71502: Diff 291448.Sep 13 2020, 1:41 AM
craig.topper updated this revision to Diff 291451.Sep 13 2020, 2:41 AM

Use isGuaranteedToTransferExecutionToSuccessor. Need to be put together negative tests.

Harbormaster completed remote builds in B71505: Diff 291451.Sep 13 2020, 3:43 AM
spatel added a comment.Sep 13 2020, 5:58 AM

I'm not seeing why we need the guaranteed-to-execute checks with the proposed instruction movement. In general, div/rem are special because of their UB problems, but in this case we have:

/// 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.

In other words, this is similar to hoisting a normal math binop once we find the other member of the pair.

spatel added a comment.Sep 13 2020, 6:04 AM
In D87555#2270191, @spatel wrote:

I'm not seeing why we need the guaranteed-to-execute checks with the proposed instruction movement. In general, div/rem are special because of their UB problems, but in this case we have:

/// 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.

In other words, this is similar to hoisting a normal math binop once we find the other member of the pair.

Ah, never mind. I see it now. We are moving both div and rem.

craig.topper planned changes to this revision.Sep 14 2020, 2:38 PM
RKSimon added a comment.Jul 10 2021, 3:23 AM

@craig.topper Are you still intending to look at this?

craig.topper updated this revision to Diff 357761.Jul 10 2021, 3:47 PM

-Now with negative tests.
-Support the rem block having PredBB as a predecessor multiple times.

craig.topper edited the summary of this revision. (Show Details)Jul 10 2021, 3:48 PM
craig.topper edited the summary of this revision. (Show Details)
lebedev.ri added a comment.Jul 10 2021, 4:14 PM

Seems reasonable to me, but i don't quite recall what was the holdup back then..

llvm/lib/Transforms/Scalar/DivRemPairs.cpp
248

guaranteed

craig.topper updated this revision to Diff 357766.Jul 10 2021, 4:20 PM

Fix typo

lebedev.ri accepted this revision.Jul 10 2021, 4:25 PM

LG, thanks.
@spatel ?

llvm/test/Transforms/DivRemPairs/X86/div-expanded-rem-pair.ll
207

Please precommit the tests

This revision is now accepted and ready to land.Jul 10 2021, 4:25 PM
Harbormaster completed remote builds in B113386: Diff 357766.Jul 10 2021, 4:54 PM
craig.topper mentioned this in rGcbba7299f308: [DivRemPairs] Add test cases for D87555. NFC.Jul 10 2021, 6:37 PM
craig.topper updated this revision to Diff 357775.Jul 10 2021, 6:41 PM

Rebase after pre-committing tests

Harbormaster completed remote builds in B113392: Diff 357775.Jul 10 2021, 7:15 PM
spatel accepted this revision.Jul 11 2021, 4:23 AM

LGTM

Closed by commit rGe38b7e894808: [DivRemPairs] Add an initial case for hoisting to a common predecessor. (authored by craig.topper). · Explain WhyJul 11 2021, 10:08 AM
This revision was automatically updated to reflect the committed changes.
craig.topper added a commit: rGe38b7e894808: [DivRemPairs] Add an initial case for hoisting to a common predecessor..
RKSimon added a comment.Jul 11 2021, 1:09 PM

Thanks Craig!

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
31 lines
test/
Transforms/
DivRemPairs/
X86/
57 lines

Diff 291372

llvm/lib/Transforms/Scalar/DivRemPairs.cpp

//===- DivRemPairs.cpp - Hoist/[dr]ecompose division and remainder --------===// //===- DivRemPairs.cpp - Hoist/[dr]ecompose division and remainder --------===//
Lint: Lint
Inline Actions

clang-format not found in user's PATH; not linting file.

Lint: Lint: clang-format not found in user's PATH; not linting file.
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// //
▲ Show 20 Lines • Show All 224 Lines • ▼ Show 20 Lines for (DivRemPairWorklistEntry &E : Worklist) {
// target does not support div+rem, then we will decompose the rem. // target does not support div+rem, then we will decompose the rem.
if (HasDivRemOp && RemInst->getParent() == DivInst->getParent()) if (HasDivRemOp && RemInst->getParent() == DivInst->getParent())
continue; continue;
bool DivDominates = DT.dominates(DivInst, RemInst); 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, // We have matching div-rem pair, but they are in two different blocks,
// neither of which dominates one another. // neither of which dominates one another.
// FIXME: We could hoist both ops to the common predecessor block? // FIXME: We could hoist both ops to the common predecessor block?
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

Remove FIXME?

lebedev.ri: Remove FIXME?
craig.topperAuthorUnsubmitted
Done
ReplyInline Actions

I only handled one specific case. There are other cases that could be handled.

craig.topper: I only handled one specific case. There are other cases that could be handled.
BasicBlock *PredBB = nullptr;
// Look for something like this
// PredBB
// | \
// | Rem
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

guaranteed

lebedev.ri: guaranteed
// | /
// Div
//
// If the Rem block has a single predecessor and successor, and all paths
// from PredBB go to either Rem or Div, we can hoist Div to PredBB. If
// we have a DivRemOp we can also hoist Rem. Otherwise we'll leave
// Rem where it is and rewrite it to mul/sub.
if (RemInst->getParent()->getSingleSuccessor() == DivInst->getParent())
PredBB = RemInst->getParent()->getSinglePredecessor();
// Make sure all paths from PredBB go to either the RemBB or the DivBB.
if (PredBB && llvm::all_of(successors(PredBB), [&](BasicBlock *BB) {
return BB == DivInst->getParent() ||
Lint: Pre-merge checks
Inline Actions

clang-format: please reformat the code

-                         return BB == DivInst->getParent() ||
-                                BB == RemInst->getParent(); })) {
+            return BB == DivInst->getParent() || BB == RemInst->getParent();
+          })) {
Lint: Pre-merge checks: clang-format: please reformat the code ``` - return BB == DivInst…
BB == RemInst->getParent(); })) {
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

This is too fragile.
You want to check that every instruction between the place you hoist to,
and each div/rem instruction is isGuaranteedToTransferExecutionToSuccessor()

lebedev.ri: This is too fragile. You want to check that every instruction between the place you hoist to…
DivDominates = true;
DivInst->moveBefore(PredBB->getTerminator());
if (HasDivRemOp) {
RemInst->moveBefore(PredBB->getTerminator());
Changed = true;
continue;
}
} else
continue; continue;
} }
// The target does not have a single div/rem operation, // The target does not have a single div/rem operation,
// and the rem is already in expanded form. Nothing to do. // and the rem is already in expanded form. Nothing to do.
if (!HasDivRemOp && E.isRemExpanded()) if (!HasDivRemOp && E.isRemExpanded())
continue; continue;
if (HasDivRemOp) { if (HasDivRemOp) {
▲ Show 20 Lines • Show All 149 Lines • Show Last 20 Lines

llvm/test/Transforms/DivRemPairs/X86/div-expanded-rem-pair.ll

Show First 20 Lines • Show All 198 Lines • ▼ Show 20 Lines
if.else: if.else:
%t3 = udiv i32 %a, %b %t3 = udiv i32 %a, %b
br label %end br label %end
end: end:
%ret = phi i32 [ %t2, %if.then ], [ %t3, %if.else ] %ret = phi i32 [ %t2, %if.then ], [ %t3, %if.else ]
ret i32 %ret ret i32 %ret
} }
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

Please precommit the tests

lebedev.ri: Please precommit the tests
define i64 @remainder_triangle_i64(i64 %a, i64 %b, i64* %rp) {
; CHECK-LABEL: @remainder_triangle_i64(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64* [[RP:%.*]], null
; CHECK-NEXT: [[DIV:%.*]] = udiv i64 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT: [[REM:%.*]] = urem i64 [[A]], [[B]]
; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN:%.*]], label [[END:%.*]]
; CHECK: if.then:
; CHECK-NEXT: store i64 [[REM]], i64* [[RP]], align 4
; CHECK-NEXT: br label [[END]]
; CHECK: end:
; CHECK-NEXT: ret i64 [[DIV]]
;
entry:
%cmp = icmp ne i64* %rp, null
br i1 %cmp, label %if.then, label %end
if.then:
%rem = urem i64 %a, %b
store i64 %rem, i64* %rp
br label %end
end:
%div = udiv i64 %a, %b
ret i64 %div
}
define i128 @remainder_triangle_i128(i128 %a, i128 %b, i128* %rp) {
; CHECK-LABEL: @remainder_triangle_i128(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP:%.*]] = icmp ne i128* [[RP:%.*]], null
; CHECK-NEXT: [[A_FROZEN:%.*]] = freeze i128 [[A:%.*]]
; CHECK-NEXT: [[B_FROZEN:%.*]] = freeze i128 [[B:%.*]]
; CHECK-NEXT: [[DIV:%.*]] = udiv i128 [[A_FROZEN]], [[B_FROZEN]]
; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN:%.*]], label [[END:%.*]]
; CHECK: if.then:
; CHECK-NEXT: [[TMP0:%.*]] = mul i128 [[DIV]], [[B_FROZEN]]
; CHECK-NEXT: [[REM_DECOMPOSED:%.*]] = sub i128 [[A_FROZEN]], [[TMP0]]
; CHECK-NEXT: store i128 [[REM_DECOMPOSED]], i128* [[RP]], align 4
; CHECK-NEXT: br label [[END]]
; CHECK: end:
; CHECK-NEXT: ret i128 [[DIV]]
;
entry:
%cmp = icmp ne i128* %rp, null
br i1 %cmp, label %if.then, label %end
if.then:
%rem = urem i128 %a, %b
store i128 %rem, i128* %rp
br label %end
end:
%div = udiv i128 %a, %b
ret i128 %div
}