This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] More aggressively try and fold irem/idiv/mul into selects.
Needs ReviewPublic

Authored by goldstein.w.n on Mar 17 2023, 7:05 PM.

Details

Summary

Don't only do constant cases, also try cases were we can't constant
fold both sides. In the same we can't constant fold both sides, only
do transform if the select is single use.

Diff Detail

Event Timeline

goldstein.w.n created this revision.Mar 17 2023, 7:05 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 17 2023, 7:05 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
goldstein.w.n requested review of this revision.Mar 17 2023, 7:05 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 17 2023, 7:05 PM
nikic requested changes to this revision.Mar 18 2023, 3:03 PM

This is not generally legal for div/rem, see https://alive2.llvm.org/ce/z/2iiR26 using one of your tests. This is only legal if the operation is speculatable.

This revision now requires changes to proceed.Mar 18 2023, 3:03 PM

This is not generally legal for div/rem, see https://alive2.llvm.org/ce/z/2iiR26 using one of your tests. This is only legal if the operation is speculatable.

Is there a flag for speculatable?

nikic added a comment.Mar 30 2023, 3:23 AM

This is not generally legal for div/rem, see https://alive2.llvm.org/ce/z/2iiR26 using one of your tests. This is only legal if the operation is speculatable.

Is there a flag for speculatable?

There is isSafeToSpeculativelyExecute().

nikic added a comment.Mar 30 2023, 3:25 AM

Err, I probably misunderstood the question: There are no div/rem variants that are always speculatable, we can only speculate them if we know that the divisor is non-zero (or the more complex conditions for the signed case are met).

Only do rem/div if denominator known non zero

Err, I probably misunderstood the question: There are no div/rem variants that are always speculatable, we can only speculate them if we know that the divisor is non-zero (or the more complex conditions for the signed case are met).

Done + test cases for it (*fail_no_speculation).

nikic added inline comments.Apr 26 2023, 12:57 AM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
191

Comment that it returns MultiUse.

193

Matching against all-wildcards is a bit silly :)

1020

Please use isSafeToSpeculativelyExecute() here. This check is not sufficient for sdiv (due to INT_MIN / -1), and we don't want to duplicate logic.

1847

Same here.

llvm/test/Transforms/InstCombine/binop-select.ll
548

Also test the straightforward case where the mul has a constant operand? Or is that already handled somewhere else (and if so, can we remove it)?

nikic requested changes to this revision.Apr 26 2023, 12:59 AM
This revision now requires changes to proceed.Apr 26 2023, 12:59 AM
goldstein.w.n marked 4 inline comments as done.Apr 30 2023, 10:01 PM
goldstein.w.n added inline comments.
llvm/test/Transforms/InstCombine/binop-select.ll
548

hmm? Not sure what you mean by this comment.

Use isSafeToSpeculate to check if allows on non-imm operands

nikic added inline comments.May 1 2023, 12:18 AM
llvm/test/Transforms/InstCombine/binop-select.ll
548

I mean something like (c ? x : C1) * C2, that isn't based on the select condition.

nikic added inline comments.May 1 2023, 12:44 AM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
206

Is this code in here so the case where the div is always folded away is always handled, as we're at worst going to relax to poison there and not introduce UB?

If so, I think it might be more elegant to sink this check into FoldOpIntoSelect and use the isSafeToSpeculativelyExecute variant that accepts operands, so we can check the operation that we're actually going to introduce (and thus also skip the check if we're not going to introduce one).

nikic added inline comments.May 1 2023, 12:46 AM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
206

and use the isSafeToSpeculativelyExecute variant that accepts operands

Well, it looks like I imagined that variant... So ignore that bit (or leave a TODO for possible future improvement) and just take the bit about only checking it if we're going to introduce an op.

xbolva00 added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1844

Updatr comment?

goldstein.w.n added inline comments.May 1 2023, 4:28 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
206

Without that variant we end up with regressions in:

LLVM :: Transforms/InstCombine/div.ll
LLVM :: Transforms/InstCombine/rem.ll

I'm happy to just add the variant and use that, but I'm not sure what to do with load/call instructions.
Maybe just return false in those cases as they aren't really needed here?

goldstein.w.n marked 3 inline comments as done.May 2 2023, 11:13 AM
goldstein.w.n added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
206

There are regressions either way. Would prefer to keep it this way if thats okay with you.

llvm/test/Transforms/InstCombine/binop-select.ll
548

done although unaffected by this patch.

goldstein.w.n marked an inline comment as done.May 2 2023, 11:13 AM

Update comments

We generally fail to call 'foldBinOpIntoSelectOrPhi' in commonIDivTransforms and commonIRemTransforms

How hard would be to add support for PHIs in your shouldFoldOp helper? (Can be followup).

We generally fail to call 'foldBinOpIntoSelectOrPhi' in commonIDivTransforms and commonIRemTransforms

How hard would be to add support for PHIs in your shouldFoldOp helper? (Can be followup).

Well we match explicitly against m_Select(...) to check the all constant case so that wouldn't apply.
The speculative execution check can be reused, however.

Personally to add PHI support I'd create a new function "shouldFoldOpIntoX(...)" then have a variant
for select/phi and base the imm match on what X is.

goldstein.w.n added inline comments.May 7 2023, 11:55 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
206

ping @nikic, okay with as is or okay with regressions or something else?

goldstein.w.n added inline comments.May 13 2023, 12:20 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
206

ping2 @nikic.

nikic added a comment.May 21 2023, 2:09 PM

I think this is basically okay if you drop the mul handling. As @xbolva00 pointed out (thanks, this is the bit I was missing here!) the mul case is already handled by foldBinOpIntoSelectOrPhi() and you're duplicating the transform for a special case now. If we want to extend handling to more cases, we should do so generically inside foldBinOpIntoSelectOrPhi(), not by repeating the transform with different arguments.

I think this is basically okay if you drop the mul handling. As @xbolva00 pointed out (thanks, this is the bit I was missing here!) the mul case is already handled by foldBinOpIntoSelectOrPhi() and you're duplicating the transform for a special case now. If we want to extend handling to more cases, we should do so generically inside foldBinOpIntoSelectOrPhi(), not by repeating the transform with different arguments.

Ah, I had misunderstood his comment. I can move all the logics for div/mul/rem/etc.. into foldBinOpInstoSelectOrPhi. We actually call it for udiv as well (with really weak speculative checks).

Move all new logic into foldBinOpIntoSelectOrPhi.

Rebase + remove issafetospeculativelyexecute patch dependency

Use bespoke speculation tracking for div/rem

(no rush) @nikic, I dropped the dependencies on the generic issafetospeculate... patch. Can take a look at this when you have the time.