This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Canonicalize uadd.with.overflow to uadd.sat
ClosedPublic

Authored by dmgreen on Oct 21 2019, 2:35 AM.

Details

Summary

This adds some patterns to transform uadd.with.overflow to uadd.sat (with usub.with.overflow to usub.sat too). The patterns selects from UINTMAX (or 0 for subs) depending on whether the operation overflowed.

Signed patterns are a little more involved (they can wrap in two directions), but can be added here in a followup patch too.

Diff Detail

Event Timeline

dmgreen created this revision.Oct 21 2019, 2:35 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 21 2019, 2:35 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
nikic added inline comments.Oct 21 2019, 11:45 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1743

We might want to add an m_ExtractValue<0>(Matcher) matcher...

dmgreen marked an inline comment as done.Oct 22 2019, 7:01 AM
dmgreen added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1743

Righteo.

I've only made it single index, as opposed to try and get fancy with some recursive templates. That is likely the most common case. I've also added a m_BinOpIntrinsic to more easily grab the BinaryOpIntrinsic.

dmgreen updated this revision to Diff 226042.Oct 22 2019, 7:01 AM

Added a m_ExtractValue matcher.

nikic added inline comments.Oct 22 2019, 1:25 PM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1743

I think it would make more sense to make this a matcher for WithOverflowInst intrinsics -- that's what's needed here, and matching both saturating and with.overflow in one matcher doesn't seem super useful in general.

dmgreen marked an inline comment as done.Oct 23 2019, 3:02 AM
dmgreen added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1743

Oh yeah. That sounds like what I need. I could also add a generic "match one of these things" operator. Something like

diff --git a/llvm/include/llvm/IR/PatternMatch.h b/llvm/include/llvm/IR/PatternMatch.h
index 0cf8e62..649b047 100644
--- a/llvm/include/llvm/IR/PatternMatch.h
+++ b/llvm/include/llvm/IR/PatternMatch.h
@@ -559,8 +559,9 @@ inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
 inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
 /// Match a binary operator, capturing it if we match.
 inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
-/// Match a binary operator intrinsic, capturing it if we match.
-inline bind_ty<BinaryOpIntrinsic> m_BinOpIntrinsic(BinaryOpIntrinsic *&I) { return I; }
+/// Match a class of type T, capturing it if we match.
+template <typename T>
+inline bind_ty<T> m_Instruction(T *&I) { return I; }
 
 /// Match a ConstantInt, capturing the value if we match.
 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstC
index f3b0ac5..46bfb81 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
@@ -1743,8 +1743,8 @@ foldOverflowingAddSubSelect(SelectInst &SI, InstCombiner::BuilderTy &Bui
   Value *TrueVal = SI.getTrueValue();
   Value *FalseVal = SI.getFalseValue();
 
-  BinaryOpIntrinsic *II;
-  if (!match(CondVal, m_ExtractValue<1>(m_BinOpIntrinsic(II))) ||
+  WithOverflowInst *II;
+  if (!match(CondVal, m_ExtractValue<1>(m_Instruction(II))) ||
       !match(FalseVal, m_ExtractValue<0>(m_Specific(II))))
     return nullptr;

What do you think? Is there a better name than m_Instruction? (It's better than my original m_OneOfTheseThings. I kind of feel like there should be some way of doing this already that I might be missing).

dmgreen updated this revision to Diff 226110.Oct 23 2019, 3:07 AM

Update to m_WithOverflowInst for now

nikic added inline comments.Oct 24 2019, 11:57 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1743

I like the idea. Overloading m_Instruction() for this purpose is probably not good though. Generally I'd prefer something that mentions the type on the matcher itself, i.e. m_Instruction<WithOverflowInst>(II), though I guess that's more of usage style question, as it probably can't be enforced in the implementation.

Some ideas...

m_a<WithOverflowInst>(II)
m_isa<WithOverflowInst>(II)
m_InstanceOf<WithOverflowInst>(II)
m_OfType<WithOverflowInst>(II)
dmgreen updated this revision to Diff 226592.Oct 27 2019, 2:48 PM

I've gone with m_isa, which I think with the explicit WithOverflowInst looks OK.

nikic accepted this revision.Oct 27 2019, 3:32 PM

LGTM, though I'd like a second opinion on the PatternMatch additions from @lebedev.ri or @spatel.

This revision is now accepted and ready to land.Oct 27 2019, 3:32 PM
lebedev.ri requested changes to this revision.Oct 27 2019, 11:13 PM

Looks good in general but i have reservations about matchers.

llvm/include/llvm/IR/PatternMatch.h
562–564

I don't like this one.
Can we change it to be a two-step process - just make m_isa<>() a predicate,
if isa<>() matches, then it should apply inner matcher, if any.
And said inner matcher can be m_Value().

This revision now requires changes to proceed.Oct 27 2019, 11:13 PM
nikic added inline comments.Oct 28 2019, 1:10 AM
llvm/include/llvm/IR/PatternMatch.h
562–564

I'm not sure I understand how that would be used. If you use something like m_isa<WithOverflowInst>(m_Value(V)), wouldn't V have to be Value * rather than WithOverflowInst *? That seems less useful to me. It's also not clear what things apart from m_Value() you would use as the inner matcher.

lebedev.ri added inline comments.
llvm/include/llvm/IR/PatternMatch.h
562–564

Good point. I'm mainly unhappy about the name.
m_isa<>() really looks similar to normal isa<>(), from looking at it i would not
have guessed it takes reference to the pointer of that type and binds to it if matched.

dmgreen marked an inline comment as done.Oct 28 2019, 2:24 AM
dmgreen added inline comments.
llvm/include/llvm/IR/PatternMatch.h
562–564

Right. I did think of that but is seemed OK as it was in the middle of a match statement.

Got a better suggestion, or a preference out of these?

m_a<WithOverflowInst>(II)
m_InstanceOf<WithOverflowInst>(II)
m_OfType<WithOverflowInst>(II)
m_OneOfTheseThings<WithOverflowInst>(II)
lebedev.ri added inline comments.Oct 28 2019, 4:56 AM
llvm/include/llvm/IR/PatternMatch.h
562–564

To be honest, none of those tell me that they capture..
Would m_CaptureIf_isa<>() be too ugly?
@RKSimon @spatel thoughts?

spatel added inline comments.Oct 28 2019, 8:26 AM
llvm/include/llvm/IR/PatternMatch.h
562–564

Catching up after travel...I might have missed something in the earlier inline comments, but we just need a WithOverflowInst sibling to:

inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }

...for this patch, right?

It's not clear to me that a more templated generic binder is needed. Either way, it would be good to split the matcher changes from the instcombine changes, so there's less risk of losing improvements if some part of this needs to be reverted.

dmgreen marked an inline comment as done.Oct 29 2019, 2:49 AM
dmgreen added inline comments.
llvm/include/llvm/IR/PatternMatch.h
562–564

Do you mean like this version: https://reviews.llvm.org/D69245?id=226110 :)

We can go back to that. I quite like the ability to capture a thing of type T, but you are correct that it is simpler to just add the m_WithOverflowInst case.

dmgreen updated this revision to Diff 226861.Oct 29 2019, 2:53 AM

Back to m_WithOverflowInst

lebedev.ri accepted this revision.Oct 29 2019, 3:04 AM

LGTM, thank you.

This revision is now accepted and ready to land.Oct 29 2019, 3:04 AM
spatel added inline comments.Oct 29 2019, 4:33 AM
llvm/include/llvm/IR/PatternMatch.h
562–564

Yes, that's the simpler solution since we don't have a clear winner for the more generic matcher.
I'd still split this when committing (adding a couple of dedicated tests to unittests/IR/PatternMatch.cpp is even better), but either way, LGTM.

dmgreen marked an inline comment as done.Oct 31 2019, 5:28 AM
dmgreen added inline comments.
llvm/include/llvm/IR/PatternMatch.h
562–564

Part1: https://reviews.llvm.org/rG6cfbefbc4a7e. Let me know if that test looks dodgy.

This revision was automatically updated to reflect the committed changes.
spatel added inline comments.Oct 31 2019, 6:39 AM
llvm/include/llvm/IR/PatternMatch.h
562–564

Thanks! Unit tests LGTM.