[ValueTracking] ComputeNumSignBitsImpl - add basic handling of BITCAST nodes

[RKSimon]

At the very least ComputeNumSignBitsImpl should be able to report that if we bitcast from a wider scalar/vector type to a narrow vector element type, and the original wide type was all sign bits then the destination narrow type elements will be all sign bits as well.

SelectionDAG already does this (and quite a bit more, but the "fast case" would be enough):

llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

Lines 4425 to 4469 in 5ad320a

	case ISD::BITCAST: {
	if (VT.isScalableVector())
	break;
	SDValue N0 = Op.getOperand(0);
	EVT SrcVT = N0.getValueType();
	unsigned SrcBits = SrcVT.getScalarSizeInBits();
	// Ignore bitcasts from unsupported types..
	if (!(SrcVT.isInteger() || SrcVT.isFloatingPoint()))
	break;
	// Fast handling of 'identity' bitcasts.
	if (VTBits == SrcBits)
	return ComputeNumSignBits(N0, DemandedElts, Depth + 1);
	bool IsLE = getDataLayout().isLittleEndian();
	// Bitcast 'large element' scalar/vector to 'small element' vector.
	if ((SrcBits % VTBits) == 0) {
	assert(VT.isVector() && "Expected bitcast to vector");
	unsigned Scale = SrcBits / VTBits;
	APInt SrcDemandedElts =
	APIntOps::ScaleBitMask(DemandedElts, NumElts / Scale);
	// Fast case - sign splat can be simply split across the small elements.
	Tmp = ComputeNumSignBits(N0, SrcDemandedElts, Depth + 1);
	if (Tmp == SrcBits)
	return VTBits;
	// Slow case - determine how far the sign extends into each sub-element.
	Tmp2 = VTBits;
	for (unsigned i = 0; i != NumElts; ++i)
	if (DemandedElts[i]) {
	unsigned SubOffset = i % Scale;
	SubOffset = (IsLE ? ((Scale - 1) - SubOffset) : SubOffset);
	SubOffset = SubOffset * VTBits;
	if (Tmp <= SubOffset)
	return 1;
	Tmp2 = std::min(Tmp2, Tmp - SubOffset);
	}
	return Tmp2;
	}
	break;
	}

Encountered while fighting bitcasts between SSE intrinsics.

https://alive2.llvm.org/ce/z/NvZpPa

----------------------------------------
define <4 x i2> @src(<1 x i8> %a0, <1 x i8> %a1) {
#0:
  %cmp = icmp sgt <1 x i8> %a0, %a1
  %ext = sext <1 x i1> %cmp to <1 x i8>
  %sub = bitcast <1 x i8> %ext to <4 x i2>
  %sra = ashr <4 x i2> %sub, { 1, 1, 1, 1 }
  ret <4 x i2> %sra
}
=>
define <4 x i2> @tgt(<1 x i8> %a0, <1 x i8> %a1) {
#0:
  %cmp = icmp sgt <1 x i8> %a0, %a1
  %ext = sext <1 x i1> %cmp to <1 x i8>
  %sub = bitcast <1 x i8> %ext to <4 x i2>
  ret <4 x i2> %sub
}
Transformation seems to be correct!

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Simon Pilgrim (RKSimon)

At the very least ComputeNumSignBitsImpl should be able to report that if we bitcast from a wider scalar/vector type to a narrow vector element type, and the original wide type was all sign bits then the destination narrow type elements will be all sign bits as well.

SelectionDAG already does this (and quite a bit more, but for the "fast case" would be enough):

llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

Lines 4425 to 4469 in 5ad320a

	case ISD::BITCAST: {
	if (VT.isScalableVector())
	break;
	SDValue N0 = Op.getOperand(0);
	EVT SrcVT = N0.getValueType();
	unsigned SrcBits = SrcVT.getScalarSizeInBits();
	// Ignore bitcasts from unsupported types..
	if (!(SrcVT.isInteger() || SrcVT.isFloatingPoint()))
	break;
	// Fast handling of 'identity' bitcasts.
	if (VTBits == SrcBits)
	return ComputeNumSignBits(N0, DemandedElts, Depth + 1);
	bool IsLE = getDataLayout().isLittleEndian();
	// Bitcast 'large element' scalar/vector to 'small element' vector.
	if ((SrcBits % VTBits) == 0) {
	assert(VT.isVector() && "Expected bitcast to vector");
	unsigned Scale = SrcBits / VTBits;
	APInt SrcDemandedElts =
	APIntOps::ScaleBitMask(DemandedElts, NumElts / Scale);
	// Fast case - sign splat can be simply split across the small elements.
	Tmp = ComputeNumSignBits(N0, SrcDemandedElts, Depth + 1);
	if (Tmp == SrcBits)
	return VTBits;
	// Slow case - determine how far the sign extends into each sub-element.
	Tmp2 = VTBits;
	for (unsigned i = 0; i != NumElts; ++i)
	if (DemandedElts[i]) {
	unsigned SubOffset = i % Scale;
	SubOffset = (IsLE ? ((Scale - 1) - SubOffset) : SubOffset);
	SubOffset = SubOffset * VTBits;
	if (Tmp <= SubOffset)
	return 1;
	Tmp2 = std::min(Tmp2, Tmp - SubOffset);
	}
	return Tmp2;
	}
	break;
	}

Encountered while fighting bitcasts between SSE intrinsics.

https://alive2.llvm.org/ce/z/NvZpPa

----------------------------------------
define &lt;4 x i2&gt; @<!-- -->src(&lt;1 x i8&gt; %a0, &lt;1 x i8&gt; %a1) {
#<!-- -->0:
  %cmp = icmp sgt &lt;1 x i8&gt; %a0, %a1
  %ext = sext &lt;1 x i1&gt; %cmp to &lt;1 x i8&gt;
  %sub = bitcast &lt;1 x i8&gt; %ext to &lt;4 x i2&gt;
  %sra = ashr &lt;4 x i2&gt; %sub, { 1, 1, 1, 1 }
  ret &lt;4 x i2&gt; %sra
}
=&gt;
define &lt;4 x i2&gt; @<!-- -->tgt(&lt;1 x i8&gt; %a0, &lt;1 x i8&gt; %a1) {
#<!-- -->0:
  %cmp = icmp sgt &lt;1 x i8&gt; %a0, %a1
  %ext = sext &lt;1 x i1&gt; %cmp to &lt;1 x i8&gt;
  %sub = bitcast &lt;1 x i8&gt; %ext to &lt;4 x i2&gt;
  ret &lt;4 x i2&gt; %sub
}
Transformation seems to be correct!

[changkhothuychung]

I will take this issue if its available, thanks!

[changkhothuychung]

@RKSimon Rk
Thanks for assigning this to me! I have a quick question, I see you attached a link from alive2.llvm

Can you explain to me what the syntax is? Is that some part of llvm? and is there resource I can utilize to gain some understandings of it? Thanks.

[RKSimon]

alive2 takes standard llvm IR to compare the src vs dst codegen.

The test I created was based off the issue I hit where ashr of an all-signbits value can be discarded:

llvm-project/llvm/lib/Analysis/InstructionSimplify.cpp

Lines 1525 to 1528 in a612524

	// Arithmetic shifting an all-sign-bit value is a no-op.
	unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
	if (NumSignBits == Op0->getType()->getScalarSizeInBits())
	return Op0;

[RKSimon]

@changkhothuychung Do you have enough information to understand the issue?

[RKSimon]

@changkhothuychung reverse-ping

[changkhothuychung]

@changkhothuychung reverse-ping

I am sorry for the late response, now I can get started on this one. If possible, can you provide me some instructions of what action items I need to do? from the description it looks like I need to enhance function ComputeNumSignBitsImpl to report if we are casting from wider range to narrower range?

[RKSimon]

The basic implementation will be something like:

    case Instruction::BitCast: {
      Value *Src = U->getOperand(0);
      unsigned NumSrcEltBits = Src->getType()->getScalarSizeInBits();
      if ((NumSrcEltBits % TyBits) != 0)
        break;
      unsigned NumSrcSignBits = ComputeNumSignBits(Src, Depth + 1, Q);
      if (NumSrcSignBits == NumSrcSignBits)
        return TyBits;
      break;
    }

Plus comments, handling of weird types etc.

[changkhothuychung]

The basic implementation will be something like:

    case Instruction::BitCast: {
      Value *Src = U->getOperand(0);
      unsigned NumSrcEltBits = Src->getType()->getScalarSizeInBits();
      if ((NumSrcEltBits % TyBits) != 0)
        break;
      unsigned NumSrcSignBits = ComputeNumSignBits(Src, Depth + 1, Q);
      if (NumSrcSignBits == NumSrcSignBits)
        return TyBits;
      break;
    }

Plus comments, handling of weird types etc.

I am actively looking into this now, looks like the change you are suggesting should be done in the file llvm/lib/Analysis/ValueTracking.cpp, right?

[RKSimon]

Yes, the issue subject/description explains this.