[InstCombine] Make SimplifyDemandedUseBits handle PhiNode

[xur]

Summary

This patch enables SimplifyDemandedUseBits to handle PhiNode so that some redundant instructions across the PhiNode can be eliminated.

[craig.topper]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

473

This seems unrelated or at least unexplained.

476

DemandedMaskIn isn't used after this.

516

This as well?

[craig.topper]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

680

Use "KnownZero &= PhiOperandKnown.Zero" it will save an allocation if the width is more than 64-bits.

[xur]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

473

see the comments below.

476

I actually did not understand why DemandedMaskIn is reset here. So I moved it down (after processed the operand 0).

To me, since we are doing the do the shift right, ShiftAmt of the lowbits is not needed (whatever value it might be).
The original code seems to say these lowbits are needed.

If the lowbits in DemandMaskin are indeed needed, I would have to set the Known.zero and check Known.zero in AND instruction.

[craig.topper]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

476

If we dont' preserve the bits in the input to the shift, then the exact flag could become incorrect. I'm not sure why we would prefer to preserve the bits rather than clear the exact flag.

[• dberlin]

Interesting. NewGVN can already figure this out if it's important.
How often does stuff like this occur?

test/Transforms/InstCombine/simplify-demanded-bits-across-phi.ll

36

Remove the ss :)

[xur]

Updated the patch to integrate comments from ctopper and dberlin.

[xur]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

476

You are right! Thanks for the explanation. If the operand marked as exact, it's unsafe the remove the AND operation.
This exact in lshr seems to be insert by instcombine (with the presence of AND).
It won's apply to my original c++ programs.

Changed the test case as suggested by dberlin.

[xur]

ping.

[xur]

Ping.

[efriedma]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

679

This call is going to be expensive in the case where the PHI node refers to itself (either directly or indirectly). It's not an infinite loop due to the depth limit, but we might want to limit the recursion some other way.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask,
   case Instruction::LShr: {
     const APInt *SA;
     if (match(I->getOperand(1), m_APInt(SA))) {
       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
 
       // Unsigned shift right.
       APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
 
       // If the shift is exact, then it does demand the low bits (and knows that
       // they are zero).
       if (cast<LShrOperator>(I)->isExact())
         DemandedMaskIn.setLowBits(ShiftAmt);
 
       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
         return I;
       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
       Known.Zero.lshrInPlace(ShiftAmt);
       Known.One.lshrInPlace(ShiftAmt);
       if (ShiftAmt)
         Known.Zero.setHighBits(ShiftAmt);  // high bits known zero.
if (match(I->getOperand(1), m_APInt(SA))) {
 
       // Signed shift right.
       APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
       // If any of the high bits are demanded, we should set the sign bit as
       // demanded.
       if (DemandedMask.countLeadingZeros() <= ShiftAmt)
         DemandedMaskIn.setSignBit();
 
       // If the shift is exact, then it does demand the low bits (and knows that
       // they are zero).
       if (cast<AShrOperator>(I)->isExact())
         DemandedMaskIn.setLowBits(ShiftAmt);
 
       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
         return I;
 
       unsigned SignBits = ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI);
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
       }
       case Intrinsic::x86_sse42_crc32_64_64:
         Known.Zero.setBitsFrom(32);
         return nullptr;
       }
     }
     computeKnownBits(V, Known, Depth, CxtI);
     break;
+  case Instruction::PHI: {
+    APInt IKnownZero = APInt::getAllOnesValue(BitWidth);
+    APInt IKnownOne = APInt::getAllOnesValue(BitWidth);
+    for (unsigned i = 0; i != cast<PHINode>(I)->getNumIncomingValues(); ++i) {
+      KnownBits PhiOperandKnown(BitWidth);
+      SimplifyDemandedBits(I, i, DemandedMask, PhiOperandKnown, Depth + 1);
+      IKnownZero &= PhiOperandKnown.Zero;
+      IKnownOne &= PhiOperandKnown.One;
+    }
+    Known.Zero = std::move(IKnownZero);
+    Known.One = std::move(IKnownOne);
+    break;
+  }
   }
 
   // If the client is only demanding bits that we know, return the known
   // constant.
   if (DemandedMask.isSubsetOf(Known.Zero|Known.One))
     return Constant::getIntegerValue(VTy, Known.One);
   return nullptr;
 }

test/Transforms/InstCombine/simplify-demanded-bits-across-phi.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+@bar = local_unnamed_addr global i32 0, align 4
+
+define void @foo(i64, i32) {
+  switch i32 %1, label %10 [
+    i32 1, label %3
+    i32 2, label %6
+  ]
+
+; <label>:3:
+  %4 = mul i64 %0, -4132994306676758123
+  %5 = and i64 %4, -4294967296
+  br label %10
+; CHECK: ; <label>:[[L1:[0-9]+]]:
+; CHECK: %[[V1:[0-9]+]] = mul i64 %0, -4132994306676758123
+; CHECK-NOT: %{{[0-9]+}} = and i64
+
+
+; <label>:6:
+  %7 = mul i64 %0, -4132994306676758123
+  %8 = add i64 %7, -8265988613353516246
+  %9 = and i64 %8, -4294967296
+; CHECK: ; <label>:[[L2:[0-9]+]]:
+; CHECK: %[[V2:[0-9]+]] = mul i64 %0, -4132994306676758123
+; CHECK: %[[V3:[0-9]+]] = add i64 %[[V2]], 87027708318506
+; CHECK-NOT: %{{[0-9]+}} = and i64
+  br label %10
+
+; <label>:10:
+  %11 = phi i64 [ %9, %6 ], [ %5, %3 ], [ 0, %2 ]
+; CHECK: %{{[0-9]+}} = phi i64 [ %[[V3]], %[[L2]] ], [ %[[V1]], %[[L1]] ], [ 0, %{{[0-9]+}} ]
+; %12 = lshr exact i64 %11, 32
+  %12 = lshr i64 %11, 32
+  %13 = trunc i64 %12 to i32
+  %14 = and i32 %13, 65535
+  %15 = mul i32 %14, %1
+  %16 = lshr i32 %15, 16
+  store i32 %16, i32* @bar, align 4
+  ret void
+}