This is an archive of the discontinued LLVM Phabricator instance.

Improve lookThroughCast function.
ClosedPublic

Authored by ArturGainullin on Oct 4 2017, 3:21 AM.

Details

Summary

When we have the following case:

%c = cmp iN %x, a
%t = trunc iN %y to iK
%sel = select i1 %c, iK %t, iK b

We could possibly match only min/max pattern after looking through cast.
So it is more profitable if widened b constant will be equal a. That is
why extend b using upper bits from a.

Also description for lookTroughCast function was added.

Event Timeline

ArturGainullin created this revision.Oct 4 2017, 3:21 AM
spatel edited edge metadata.

This reminds me that I haven't revisited D26556...in ~6 months.

If we implement what Eli suggested there (matching the size of a select to a cmp of its condition operand), then we won't need to do this?

I have checked that patch from D26556 doesn't work for the case described in this review.
D26556 is about folding extension instruction into select.
I.e. in case of the following pattern:

s = select Cond, C1, C2 
sext s

sext operation is eliminated and C1, C2 constants are widened.

Also it perfroms the following folding when we have trunc before select and zext after select:

zext (select Cond, C, (trunc X)) --> select Cond, C', (and X, Mask)
zext (select Cond, (trunc X), C) --> select Cond, (and X, Mask), C'

While patch from this review is intended to cover more cases when we can match min/max pattern and as a result of canonicalization move cast operation out of min/max.
So I think that we still need this.

I have read more carefully your comment. As far as I understood in D26556 you want to change the process of decision making for function that folds cast operation into select.
According to suggestion from Eli you should try to match the size of a select to a cmp of its condition operand as a final result.
Necessary to mention that this function doesn't make cast folding when select is min/max and it is called only when select is an operand of cast operation.

Current differential revision try to solve this case:

p = cmp i32 x, a
x' = trunc i32 x to i8
select i1 p, i8 x', i8 a'

where select is not an operand of the cast and where we have min/max operation as a result.
So here we try to match min/max pattern with further canonicalization (sinking of trunc). Reverse hoisting will not be performed because foldCastIntoSelect doesn't touch min/max idioms.

spatel added a comment.EditedOct 16 2017, 1:09 PM

I have read more carefully your comment. As far as I understood in D26556 you want to change the process of decision making for function that folds cast operation into select.
According to suggestion from Eli you should try to match the size of a select to a cmp of its condition operand as a final result.

That's right. The patch I was imagining would be something like this:

Index: lib/Transforms/InstCombine/InstCombineSelect.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineSelect.cpp	(revision 315902)
+++ lib/Transforms/InstCombine/InstCombineSelect.cpp	(working copy)
@@ -748,6 +748,22 @@
     }
   }
 
+  // If the select uses a truncated operand of the compare, try to select using the
+  // same value as the compare. This may then be matched as a canonical min/max
+  // op, and it usually produces better codegen for vector types because the
+  // compare result is often used as a mask value for the select.
+  Constant *CmpC, *SelC;
+  if (match(CmpRHS, m_Constant(CmpC)) && match(FalseVal, m_Constant(SelC)) &&
+      match(TrueVal, m_Trunc(m_Specific(CmpLHS)))) {
+    Type *NarrowType = SelC->getType();
+    if (ConstantExpr::getTrunc(CmpC, NarrowType) == SelC) {
+       // select (icmp Pred X, CmpC), (trunc X), SelC -->
+       // trunc (select (icmp Pred X, CmpC), X, CmpC
+      Value *WideSel = Builder.CreateSelect(ICI, CmpLHS, CmpC);
+      return new TruncInst(WideSel, NarrowType);
+    }
+  }
+

...but I suppose treating this as another special-case min/max is fine too. However, the tests you have are both not minimized (we don't need a clamp pattern) and not complete. Please try this case too:

define <2 x i8> @min_through_cast_vec(<2 x i32> %x) {
  %cmp = icmp slt <2 x i32> %x, <i32 510, i32 511>
  %max_trunc = trunc <2 x i32> %x to <2 x i8>
  %res = select <2 x i1> %cmp, <2 x i8> %max_trunc, <2 x i8> <i8 254, i8 255>
  ret <2 x i8> %res
}

Once you determine that the compare is against a constant, I don't think you need to recreate that constant - just use that constant:

if (match(CmpI->getOperand(1), m_Constant(CmpConst)))
  CastedTo = CmpConst;

Minimized test cases and added new ones.

For using constant from cmp instruction (instead of recreation) we will need to check that truncated constant is equal to lower bits of cmp constant.
That is why I decided just to recreate constant which looks like more general solution.

For using constant from cmp instruction (instead of recreation) we will need to check that truncated constant is equal to lower bits of cmp constant.
That is why I decided just to recreate constant which looks like more general solution.

That is already done?

// Make sure the cast doesn't lose any information.
  Constant *CastedBack =
      ConstantExpr::getCast(*CastOp, CastedTo, C->getType(), true);
  if (CastedBack != C)
    return nullptr;

That's why I suggested the non-splat vector test - it should be transformed too, right?

Fixed according to comments.

Oh, yes, it is clear for me now. Thanks! I have fixed according to your recommendation.

Improved comment.

spatel accepted this revision.Oct 17 2017, 8:35 AM

LGTM - see inline notes for a couple of changes to the code comments.

lib/Analysis/ValueTracking.cpp
4312

typo: initial - you could just remove that word, and the comment would be better.

4350–4355

It's more typical to use 'C' for constant values in code and comments in LLVM, so I'd change this comment text and formula to match the code:

%cond = cmp iN %x, CmpConst
%tr = trunc iN %x to iK
%narrowsel = select i1 %cond, iK %t, iK C
-->
%cond = cmp iN %x, CmpConst
%widesel = select i1 %cond, iN %x, iN CmpConst
%tr = trunc iN %widesel to iK
This revision is now accepted and ready to land.Oct 17 2017, 8:35 AM
This revision was automatically updated to reflect the committed changes.