Page MenuHomePhabricator

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

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

Details

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

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
240–241

Remove FIXME?

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
240–241

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

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?

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

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
260–261

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

Use isGuaranteedToTransferExecutionToSuccessor. Need to be put together negative tests.

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.

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