Page MenuHomePhabricator

[InstCombine] try to pull 'not' of select into compare operands
ClosedPublic

Authored by spatel on Dec 30 2019, 9:37 AM.

Details

Summary

not (select Cond, (cmp TPred, ?, ?), FVal --> select Cond, (cmp TPred', ?, ?), (not FVal)

(If both sides of the select are cmps, we can remove an instruction.)

We have a more general 'isFreeToInvert' analysis, but I'm not seeing a way to use that more widely without inducing infinite looping (opposing transforms).
Here, we flip the compare predicate directly, so we should not have any danger by creating extra intermediate 'not' ops.

Alive proofs:
https://rise4fun.com/Alive/jKa

Name: both select values are compares - invert predicates
  %tcmp = icmp sle i32 %x, %y  
  %fcmp = icmp ugt i32 %z, %w
  %sel = select i1 %cond, i1 %tcmp, i1 %fcmp
  %not = xor i1 %sel, true
=>
  %tcmp_not = icmp sgt i32 %x, %y  
  %fcmp_not = icmp ule i32 %z, %w
  %not = select i1 %cond, i1 %tcmp_not, i1 %fcmp_not
  
Name: false val is compare - invert/not 
  %fcmp = icmp ugt i32 %z, %w
  %sel = select i1 %cond, i1 %tcmp, i1 %fcmp
  %not = xor i1 %sel, true
=>
  %tcmp_not = xor i1 %tcmp, -1  
  %fcmp_not = icmp ule i32 %z, %w
  %not = select i1 %cond, i1 %tcmp_not, i1 %fcmp_not

Diff Detail

Event Timeline

spatel created this revision.Dec 30 2019, 9:37 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 30 2019, 9:37 AM

Looks good

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
3287

InvertedTPred?

I almost missed the “ ‘ “.

3304

Maybe small lambda would help here to improve this almost same code?

Looks good to me in principle, the case where we get rid of not is good,
but i'm not sure about the case where we only manage to sink it into one of the hands.
To me that seems to be the opposite of the current general canonicalizaion we do.
(Do we need Inverter logic, that handles sinking of inversions as far as possible?)

I agree that it is a throughput improvement for final assembly, but not sure about IR.
Is there some bigger pattern (of which this pattern is part of)
which shows why this is the correct IR canonicalization?

spatel added a comment.Jan 4 2020, 6:17 AM

Looks good to me in principle, the case where we get rid of not is good,
but i'm not sure about the case where we only manage to sink it into one of the hands.
To me that seems to be the opposite of the current general canonicalizaion we do.

The general 'not cmp' canonicalization is the same as this? See around line 3090:

// not (cmp A, B) = !cmp A, B
CmpInst::Predicate Pred;
if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
  return replaceInstUsesWith(I, Op0);
}

(Do we need Inverter logic, that handles sinking of inversions as far as possible?)

That would be similar to D68408 (did negator hit a roadblock?), so it could be an enhancement there.

I agree that it is a throughput improvement for final assembly, but not sure about IR.
Is there some bigger pattern (of which this pattern is part of)
which shows why this is the correct IR canonicalization?

The app where I noticed this allowed eliminating the 'not' (the select had 2 cmps), but I've lost track of that larger example. So that case seems uncontroversial - we are able to remove an instruction.

I can reduce the scope of this patch to only handle that case, but then we will have a missing canonicalization for the more general case (1 cmp). Pulling the 'not' ahead of the select seems more likely to allow follow-on folding, so that's why I chose that as canonical. I can propose that separately or drop it if that's not a convincing argument.

Looks good to me in principle, the case where we get rid of not is good,
but i'm not sure about the case where we only manage to sink it into one of the hands.
To me that seems to be the opposite of the current general canonicalizaion we do.

The general 'not cmp' canonicalization is the same as this? See around line 3090:

// not (cmp A, B) = !cmp A, B
CmpInst::Predicate Pred;
if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
  return replaceInstUsesWith(I, Op0);
}

No, i'm not talking about clear-win cases where that allows to eliminate not/neg,
but about the cases where there is no change in instruction count.

(Do we need Inverter logic, that handles sinking of inversions as far as possible?)

That would be similar to D68408, so it could be an enhancement there.

I would personally say that *if* we have an Inverter, then generally, outside of it,
in the cases where there is no decrease in instruction count,
we should be consistently *hoisting* not/neg.
But clearly we are not there (yet?), so the solution is not as obvious.

(did negator hit a roadblock?)

Yeah, it got too powerful and hit/exposed another conflicting canonicalization,
so i've stopped for now. I think it will need some kind of pattern blacklisting :/

I agree that it is a throughput improvement for final assembly, but not sure about IR.
Is there some bigger pattern (of which this pattern is part of)
which shows why this is the correct IR canonicalization?

The app where I noticed this allowed eliminating the 'not' (the select had 2 cmps), but I've lost track of that larger example. So that case seems uncontroversial - we are able to remove an instruction.

I can reduce the scope of this patch to only handle that case, but then we will have a missing canonicalization for the more general case (1 cmp). Pulling the 'not' ahead of the select seems more likely to allow follow-on folding, so that's why I chose that as canonical. I can propose that separately or drop it if that's not a convincing argument.

The clear-win case LG; the other case where we only sink it, but not *necessarily* eliminate it,
while it doesn't look obviously-bad to me, it isn't immediately obvious to me that it is the correct direction.

spatel updated this revision to Diff 236252.Jan 5 2020, 9:16 AM
spatel marked 2 inline comments as done.

Patch updated:
Only do the transform if both arms of the select are cmps. Defer canonicalization of single cmp pattern (see TODO comments).

lebedev.ri accepted this revision.Jan 6 2020, 2:24 PM

LG
I wonder if this will expose some inverse canonicalization (i hope instcombine will still endlessly loop/assert), but i can't think of any right now.

This revision is now accepted and ready to land.Jan 6 2020, 2:24 PM
This revision was automatically updated to reflect the committed changes.