[InstSimplify] fold extracting from std::pair (2/2)

[inouehrs]

Summary

This is the second patch in a series of patches to enable jump threading with a method whose return type is std::pair<int, bool> or std::pair<bool, int>. Originally, this patch is included in D48828, but re-submitted as a separate patch.

This second patch in the series handles code sequences that merges two values using shl and or, then extracts one value using and.

[lebedev.ri]

Tentative LG as with D48828, but the questions raised in D48828 need to be resolved first.

[inouehrs]

@spatel @lebedev.ri Do you have any further comments before committing this?

[lebedev.ri]

Just one: test/Transforms/NewGVN/pair_jumpthread.ll can now be un-XFAIL'ed i think?

I wonder if this still can be merged into 7.0, given that it is the second half of D48828/rL338485, which made it into the 7.0.
@hans ?

[hans]

In D49981#1185396, @lebedev.ri wrote:

Just one: test/Transforms/NewGVN/pair_jumpthread.ll can now be un-XFAIL'ed i think?

I wonder if this still can be merged into 7.0, given that it is the second half of D48828/rL338485, which made it into the 7.0.
@hans ?

Sounds good to me.

[spatel]

LGTM - see inline for some typo fixes.

lib/Analysis/InstructionSimplify.cpp

1874–1875 ↗

(On Diff #158706)

optimization -> optimize the
optimizers -> passes

test/Transforms/InstSimplify/AndOrXor.ll

995 ↗

(On Diff #158706)

Here and below: concatinate -> concatenate

[inouehrs]

In D49981#1185399, @hans wrote:

In D49981#1185396, @lebedev.ri wrote:

Just one: test/Transforms/NewGVN/pair_jumpthread.ll can now be un-XFAIL'ed i think?

I wonder if this still can be merged into 7.0, given that it is the second half of D48828/rL338485, which made it into the 7.0.
@hans ?

Sounds good to me.

@hans , I appreciate if you can merge this patch to 7.0. Thanks!

[hans]

In D49981#1187670, @inouehrs wrote:

In D49981#1185399, @hans wrote:

In D49981#1185396, @lebedev.ri wrote:

Just one: test/Transforms/NewGVN/pair_jumpthread.ll can now be un-XFAIL'ed i think?

I wonder if this still can be merged into 7.0, given that it is the second half of D48828/rL338485, which made it into the 7.0.
@hans ?

Sounds good to me.

@hans , I appreciate if you can merge this patch to 7.0. Thanks!

Merged in r339097.

Cheers,
Hans

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
 
   // If the operation is with the result of a phi instruction, check whether
   // operating on all incoming values of the phi always yields the same value.
   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q,
                                       MaxRecurse))
       return V;
 
+  // Assuming the effective width of Y is not larger than A, i.e. all bits
+  // from X and Y are disjoint in (X << A) | Y,
+  // if the mask of this AND op covers all bits of X or Y, while it covers
+  // no bits from the other, we can bypass this AND op. E.g.,
+  // ((X << A) | Y) & Mask -> Y,
+  //     if Mask = ((1 << effective_width_of(Y)) - 1)
+  // ((X << A) | Y) & Mask -> X << A,
+  //     if Mask = ((1 << effective_width_of(X)) - 1) << A
+  // SimplifyDemandedBits in InstCombine can optimize the general case.
+  // This pattern aims to help other passes for a common case.
+  Value *Y, *XShifted;
+  if (match(Op1, m_APInt(Mask)) &&
+      match(Op0, m_c_Or(m_CombineAnd(m_NUWShl(m_Value(X), m_APInt(ShAmt)),
+                                     m_Value(XShifted)),
+                        m_Value(Y)))) {
+    const unsigned ShftCnt = ShAmt->getZExtValue();
+    const KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+    const unsigned Width = Op0->getType()->getScalarSizeInBits();
+    const unsigned EffWidthY = Width - YKnown.countMinLeadingZeros();
+    if (EffWidthY <= ShftCnt) {
+      const KnownBits XKnown = computeKnownBits(X, Q.DL, 0, Q.AC, Q.CxtI,
+                                                Q.DT);
+      const unsigned EffWidthX = Width - XKnown.countMinLeadingZeros();
+      const APInt EffBitsY = APInt::getLowBitsSet(Width, EffWidthY);
+      const APInt EffBitsX = APInt::getLowBitsSet(Width, EffWidthX) << ShftCnt;
+      // If the mask is extracting all bits from X or Y as is, we can skip
+      // this AND op.
+      if (EffBitsY.isSubsetOf(*Mask) && !EffBitsX.intersects(*Mask))
+        return Y;
+      if (EffBitsX.isSubsetOf(*Mask) && !EffBitsY.intersects(*Mask))
+        return XShifted;
+    }
+  }
+
   return nullptr;
 }
 
 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::SimplifyAndInst(Op0, Op1, Q, RecursionLimit);
 }
 
 /// Given operands for an Or, see if we can fold the result.

llvm/trunk/test/Transforms/InstSimplify/AndOrXor.ll

 ;
   %nega = xor i32 -1, %a
   %or = or i32 %a, %nega
   ret i32 %or
 }
 
 define i64 @shl_or_and1(i32 %a, i1 %b) {
 ; CHECK-LABEL: @shl_or_and1(
-; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[A:%.*]] to i64
 ; CHECK-NEXT:    [[TMP2:%.*]] = zext i1 [[B:%.*]] to i64
-; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw i64 [[TMP1]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = or i64 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = and i64 [[TMP4]], 1
-; CHECK-NEXT:    ret i64 [[TMP5]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %tmp1 = zext i32 %a to i64
   %tmp2 = zext i1 %b to i64
   %tmp3 = shl nuw i64 %tmp1, 32
   %tmp4 = or i64 %tmp2, %tmp3
   %tmp5 = and i64 %tmp4, 1
   ret i64 %tmp5
 }
 
 define i64 @shl_or_and2(i32 %a, i1 %b) {
 ; CHECK-LABEL: @shl_or_and2(
 ; CHECK-NEXT:    [[TMP1:%.*]] = zext i1 [[B:%.*]] to i64
-; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[A:%.*]] to i64
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw i64 [[TMP1]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = or i64 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = and i64 [[TMP4]], 4294967296
-; CHECK-NEXT:    ret i64 [[TMP5]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %tmp1 = zext i1 %b to i64
   %tmp2 = zext i32 %a to i64
   %tmp3 = shl nuw i64 %tmp1, 32
   %tmp4 = or i64 %tmp2, %tmp3
   %tmp5 = and i64 %tmp4, 4294967296
   ret i64 %tmp5
 }
 
-; concatinate two 32-bit integers and extract lower 32-bit
+; concatenate two 32-bit integers and extract lower 32-bit
 define i64 @shl_or_and3(i32 %a, i32 %b) {
 ; CHECK-LABEL: @shl_or_and3(
-; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[A:%.*]] to i64
 ; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[B:%.*]] to i64
-; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw i64 [[TMP1]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = or i64 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = and i64 [[TMP4]], 4294967295
-; CHECK-NEXT:    ret i64 [[TMP5]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %tmp1 = zext i32 %a to i64
   %tmp2 = zext i32 %b to i64
   %tmp3 = shl nuw i64 %tmp1, 32
   %tmp4 = or i64 %tmp2, %tmp3
   %tmp5 = and i64 %tmp4, 4294967295
   ret i64 %tmp5
 }
 
-; concatinate two 16-bit integers and extract higher 16-bit
+; concatenate two 16-bit integers and extract higher 16-bit
 define i32 @shl_or_and4(i16 %a, i16 %b) {
 ; CHECK-LABEL: @shl_or_and4(
 ; CHECK-NEXT:    [[TMP1:%.*]] = zext i16 [[A:%.*]] to i32
-; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[B:%.*]] to i32
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw i32 [[TMP1]], 16
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], -65536
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %tmp1 = zext i16 %a to i32
   %tmp2 = zext i16 %b to i32
   %tmp3 = shl nuw i32 %tmp1, 16
   %tmp4 = or i32 %tmp2, %tmp3
   %tmp5 = and i32 %tmp4, 4294901760 ; mask with 0xFFFF0000
   ret i32 %tmp5
 }
 
 define i128 @shl_or_and5(i64 %a, i1 %b) {
 ; CHECK-LABEL: @shl_or_and5(
-; CHECK-NEXT:    [[TMP1:%.*]] = zext i64 [[A:%.*]] to i128
 ; CHECK-NEXT:    [[TMP2:%.*]] = zext i1 [[B:%.*]] to i128
-; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw i128 [[TMP1]], 64
-; CHECK-NEXT:    [[TMP4:%.*]] = or i128 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = and i128 [[TMP4]], 1
-; CHECK-NEXT:    ret i128 [[TMP5]]
+; CHECK-NEXT:    ret i128 [[TMP2]]
 ;
   %tmp1 = zext i64 %a to i128
   %tmp2 = zext i1 %b to i128
   %tmp3 = shl nuw i128 %tmp1, 64
   %tmp4 = or i128 %tmp2, %tmp3
   %tmp5 = and i128 %tmp4, 1
   ret i128 %tmp5
 }
;
   %tmp3 = shl nuw i32 %tmp1, 16
   %tmp4 = or i32 %tmp2, %tmp3
   %tmp5 = and i32 %tmp4, 131071 ; mask with 0x1FFFF
   ret i32 %tmp5
 }
 
 define <2 x i64> @shl_or_and1v(<2 x i32> %a, <2 x i1> %b) {
 ; CHECK-LABEL: @shl_or_and1v(
-; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i32> [[A:%.*]] to <2 x i64>
 ; CHECK-NEXT:    [[TMP2:%.*]] = zext <2 x i1> [[B:%.*]] to <2 x i64>
-; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw <2 x i64> [[TMP1]], <i64 32, i64 32>
-; CHECK-NEXT:    [[TMP4:%.*]] = or <2 x i64> [[TMP3]], [[TMP2]]
-; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i64> [[TMP4]], <i64 1, i64 1>
-; CHECK-NEXT:    ret <2 x i64> [[TMP5]]
+; CHECK-NEXT:    ret <2 x i64> [[TMP2]]
 ;
   %tmp1 = zext <2 x i32> %a to <2 x i64>
   %tmp2 = zext <2 x i1> %b to <2 x i64>
   %tmp3 = shl nuw <2 x i64> %tmp1, <i64 32, i64 32>
   %tmp4 = or <2 x i64> %tmp3, %tmp2
   %tmp5 = and <2 x i64> %tmp4, <i64 1, i64 1>
   ret <2 x i64> %tmp5
 }
 
 define <2 x i64> @shl_or_and2v(<2 x i32> %a, <2 x i1> %b) {
 ; CHECK-LABEL: @shl_or_and2v(
 ; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i1> [[B:%.*]] to <2 x i64>
-; CHECK-NEXT:    [[TMP2:%.*]] = zext <2 x i32> [[A:%.*]] to <2 x i64>
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw <2 x i64> [[TMP1]], <i64 32, i64 32>
-; CHECK-NEXT:    [[TMP4:%.*]] = or <2 x i64> [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i64> [[TMP4]], <i64 4294967296, i64 4294967296>
-; CHECK-NEXT:    ret <2 x i64> [[TMP5]]
+; CHECK-NEXT:    ret <2 x i64> [[TMP3]]
 ;
   %tmp1 = zext <2 x i1> %b to <2 x i64>
   %tmp2 = zext <2 x i32> %a to <2 x i64>
   %tmp3 = shl nuw <2 x i64> %tmp1, <i64 32, i64 32>
   %tmp4 = or <2 x i64> %tmp2, %tmp3
   %tmp5 = and <2 x i64> %tmp4, <i64 4294967296, i64 4294967296>
   ret <2 x i64> %tmp5
 }

llvm/trunk/test/Transforms/NewGVN/pair_jumpthread.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -newgvn -S | FileCheck %s
 ; RUN: opt < %s -newgvn -jump-threading -S | FileCheck --check-prefix=CHECK-JT %s
-; This test is expected to fail until the transformation is committed.
-; XFAIL: *
 
 define signext i32 @testBI(i32 signext %v) {
 ; Test with std::pair<bool, int>
 ; based on the following C++ code
 ; std::pair<bool, int> callee(int v) {
 ;   int a = dummy(v);
 ;   if (a) return std::make_pair(true, dummy(a));
 ;   else return std::make_pair(v < 0, v);