This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] add more SPFofSPF folding
ClosedPublic

Authored by shchenz on Jul 12 2018, 8:00 AM.

Details

Summary

This is from D48754.

Make matchSelectPattern() can recognize more abs pattern now. foldSPFofSPF() can also fold more SPF of SPF(abs/nabs) patterns.

Testcases are added at rL336902.

Diff Detail

Repository
rL LLVM

Event Timeline

shchenz created this revision.Jul 12 2018, 8:00 AM

Some explanation for this patch:
1, for TODO in InstCombineSelect.cpp: because matchSelectPattern() can recognize more abs pattern, including abs(-x), then the assert in canonicalizeAbsNabs() will be hit. But we decide to canonicalize pattern abs(-x) in a separated patch, I just keep canonicalizeAbsNabs() recognize the patterns which trunk recognizes. When canonicalization patch is committed, we should solve TODO.

2, Reply the comment in D48754 in file ValueTracking.cpp at line 4671. I think matchselectpattern can only return a SelectPatternResult struct. RHS stores negated operand, LHS stores the other operand. ABS(-X) and NABS(-x) is just for good understanding?

3, testcase abs_abs_x17/abs_nabs_x17/nabs_abs_x17/nabs_nabs_x17 already be folded in trunk is because (%sub = sub nsw i32 0, %x
, %cmp = icmp sgt i32 %sub, -1) can be folded to (%sub = sub nsw i32 0, %x, %cmp = icmp slt i32 %x, 0) by visiticmp(). After this folding, the left IRs is a standard abs pattern(abx(x)), so it can be recognized. But after this patch, abs(-x) is also recognized, so visiticmp() can not fold %cmp = icmp sgt i32 %sub, -1 any more. So we get different result with trunk. But after canonicalize patch, I assume, we should also get abs(x)

RKSimon added a subscriber: RKSimon.
RKSimon added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4658 ↗(On Diff #155177)

Is this better?

  if (match(TrueVal, MaybeSExtLHS)) {
      LHS = TrueVal;
      RHS = FalseVal;
  } else {
      LHS = FalseVal;
      RHS = TrueVal;
  }
if (CmpUsesNegatedOp)
  std::swap(LHS, RHS);
shchenz updated this revision to Diff 155292.Jul 12 2018, 3:52 PM

fix Simon's comments.

@RKSimon Hi Simon, thanks very much for your comment. I have updated accordingly.

spatel added inline comments.Jul 12 2018, 5:05 PM
llvm/lib/Analysis/ValueTracking.cpp
4640–4641 ↗(On Diff #155292)

What happens if the cmp uses a negated and sign-extended op? I'm not sure if this is possible because of other transforms. Do we have test(s) that include that possibility?

llvm/test/Transforms/InstCombine/abs_abs.ll
333–336 ↗(On Diff #155292)

Do you know why the scalar version above folded, but the vector version did not? Something is falsely excluding vector types.

shchenz marked 2 inline comments as done.Jul 12 2018, 6:25 PM
shchenz added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4640–4641 ↗(On Diff #155292)

new patch can recognize:
1:
%ext = sext i16 %tmp to i32
%b = sub i32 0, %ext
%cond = icmp sgt i32 %b, -1
%ret = select i1 %cond %b, %ext

%ext can be any operator's result including sext. So I

2:
%ext = sext i16 %tmp to i32
%b = sub i32 0, %ext
%cond = icmp sgt i32 %ext, -1
%ret = select i1 %cond %b, %ext

in this case, it is the same logic with trunk, so I think there should be already test for it. (abs_canonical_5/nabs_canonical_5 in abs-1.ll)

3:
%b = sub i16 0, %tmp
%ext = sext i16 %b to i32
%cond = icmp sgt i32 %ext, -1
%ret = select i1 %cond %tmp, %X

for this case:
if %X is %b, in trunk and new patch, this is not a abs pattern.
if %X is %ext, in trunk and new patch, this is also not a abs pattern.

@spatel Sanjay, Do you have any other pattern I have not considered about?

But there should be some thing we can do for sign-extended to enlarge abs pattern scope. for example We should recognize (%tmp, %ext) as negation pair in isKnownNegation(). Maybe I will do this after I finish current work for abs.

llvm/test/Transforms/InstCombine/abs_abs.ll
333–336 ↗(On Diff #155292)

Yes, it is also confuse me. I will look into it. Maybe there is a bug in trunk.

spatel added inline comments.Jul 12 2018, 6:35 PM
llvm/lib/Analysis/ValueTracking.cpp
4640–4641 ↗(On Diff #155292)

The sext pattern is my only concern with this patch.

Also, I think we might be able to simplify the logic a bit more. I'll send an idea.

shchenz marked 2 inline comments as done.Jul 13 2018, 1:38 AM

@spatel, much appriciate for your help, Sanjay. Anything wrong, please let me know. And for icmp not folded for vector type issue, I created new patch D49283 to fix it. Thanks.

I think the logic is correct, but it would be easier to read if we re-organized it like this:

Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp	(revision 336964)
+++ lib/Analysis/ValueTracking.cpp	(working copy)
@@ -4627,34 +4627,49 @@
     }
   }
 
-  // Sign-extending LHS does not change its sign, so TrueVal/FalseVal can
-  // match against either LHS or sext(LHS).
-  auto MaybeSExtLHS = m_CombineOr(m_Specific(CmpLHS),
-                                  m_SExt(m_Specific(CmpLHS)));
-  if ((match(TrueVal, MaybeSExtLHS) &&
-       match(FalseVal, m_Neg(m_Specific(TrueVal)))) ||
-      (match(FalseVal, MaybeSExtLHS) &&
-       match(TrueVal, m_Neg(m_Specific(FalseVal))))) {
-    // Set LHS and RHS so that RHS is the negated operand of the select
-    if (match(TrueVal, MaybeSExtLHS)) {
+  if (isKnownNegation(TrueVal, FalseVal)) {
+    // Sign-extending LHS does not change its sign, so TrueVal/FalseVal can
+    // match against either LHS or sext(LHS).
+    auto MaybeSExtCmpLHS = m_CombineOr(m_Specific(CmpLHS),
+                                       m_SExt(m_Specific(CmpLHS)));
+    auto ZeroOrAllOnes = m_CombineOr(m_ZeroInt(), m_AllOnes());
+    auto ZeroOrOne = m_CombineOr(m_ZeroInt(), m_One());
+    if (match(TrueVal, MaybeSExtCmpLHS)) {
+      // Set the return values. If the compare uses the negated value (-X >s 0),
+      // swap the return values because the negated value is always 'RHS'.
       LHS = TrueVal;
       RHS = FalseVal;
-    } else {
+      if (match(CmpLHS, m_Neg(m_Specific(FalseVal))))
+        std::swap(LHS, RHS);
+
+      // (X >s 0) ? X : -X or (X >s -1) ? X : -X --> ABS(X)
+      // (-X >s 0) ? -X : X or (-X >s -1) ? -X : X --> ABS(X)
+      if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, ZeroOrAllOnes))
+        return {SPF_ABS, SPNB_NA, false};
+
+      // (X <s 0) ? X : -X or (X <s 1) ? X : -X --> NABS(X)
+      // (-X <s 0) ? -X : X or (-X <s 1) ? -X : X --> NABS(X)
+      if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, ZeroOrOne))
+        return {SPF_NABS, SPNB_NA, false};
+    }
+    if (match(FalseVal, MaybeSExtCmpLHS)) {
+      // Set the return values. If the compare uses the negated value (-X >s 0),
+      // swap the return values because the negated value is always 'RHS'.
       LHS = FalseVal;
       RHS = TrueVal;
-    }
+      if (match(CmpLHS, m_Neg(m_Specific(TrueVal))))
+        std::swap(LHS, RHS);
 
-    // (X >s 0) ? X : -X or (X >s -1) ? X : -X --> ABS(X)
-    // (X >s 0) ? -X : X or (X >s -1) ? -X : X --> NABS(X)
-    if (Pred == ICmpInst::ICMP_SGT &&
-        match(CmpRHS, m_CombineOr(m_ZeroInt(), m_AllOnes())))
-      return {(LHS == TrueVal) ? SPF_ABS : SPF_NABS, SPNB_NA, false};
+      // (X >s 0) ? -X : X or (X >s -1) ? -X : X --> NABS(X)
+      // (-X >s 0) ? X : -X or (-X >s -1) ? X : -X --> NABS(X)
+      if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, ZeroOrAllOnes))
+        return {SPF_NABS, SPNB_NA, false};
 
-    // (X <s 0) ? -X : X or (X <s 1) ? -X : X --> ABS(X)
-    // (X <s 0) ? X : -X or (X <s 1) ? X : -X --> NABS(X)
-    if (Pred == ICmpInst::ICMP_SLT &&
-        match(CmpRHS, m_CombineOr(m_ZeroInt(), m_One())))
-      return {(LHS == FalseVal) ? SPF_ABS : SPF_NABS, SPNB_NA, false};
+      // (X <s 0) ? -X : X or (X <s 1) ? -X : X --> ABS(X)
+      // (-X <s 0) ? X : -X or (-X <s 1) ? X : -X --> ABS(X)
+      if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, ZeroOrOne))
+        return {SPF_ABS, SPNB_NA, false};
+    }
   }
 
   if (CmpInst::isIntPredicate(Pred))
shchenz updated this revision to Diff 155608.Jul 15 2018, 6:57 PM

fix Sanjay comments.

@spatel Hi Sanjay, thanks for your such detailed comments. I have updated accordingly.

spatel accepted this revision.Jul 15 2018, 7:12 PM

LGTM

This revision is now accepted and ready to land.Jul 15 2018, 7:12 PM
This revision was automatically updated to reflect the committed changes.