[InstCombine] sext(trunc(x)) should not be transformed to ashr(shl(trunc(x)))) when there is no chance to fold

[wenju-he]

Please check opt output in https://alive2.llvm.org/ce/z/faj-Rl
instcombine transforms

define void @src10(i64 %src1) {
entry:
  %1 = trunc i64 %src1 to i16
  %2 = sext i16 %1 to i32
  call void @use.i32(i32 %2)
  ret void
}

into

define void @tgt10(i64 %src1) {
entry:
  %1 = trunc i64 %src1 to i32
  %2 = shl i32 %1, 16
  %3 = ashr exact i32 %2, 16
  call void @use.i32(i32 %3)
  ret void
}

which should not be desired as the number of instructions increases.

[leewei05]

Hi, I'm curious about cases like these. Does InstCombine need to consider the case that increased instructions may produce more efficient machine code? Or is this the job for the backend? For instance, InstCombine generated more instructions than the original IR or this case, but the backend probably can generate a more efficient machine code than the original one.

Thinking again, I think it is the latter one. I assume that InstCombine just reduces the number of instructions and generate a canonical form for the backend. Is this correct?

[nikic]

@leewei05 Yes, your understanding is correct, and this transform does go against our usual policy. I'm somewhat surprised this exists.

For reference, this is the relevant code:

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

Lines 1494 to 1513 in 4e330fa

	// Try to extend the entire expression tree to the wide destination type.
	if (shouldChangeType(SrcTy, DestTy) && canEvaluateSExtd(Src, DestTy)) {
	// Okay, we can transform this! Insert the new expression now.
	LLVM_DEBUG(
	dbgs() << "ICE: EvaluateInDifferentType converting expression type"
	" to avoid sign extend: "
	<< Sext << '\n');
	Value *Res = EvaluateInDifferentType(Src, DestTy, true);
	assert(Res->getType() == DestTy);
	// If the high bits are already filled with sign bit, just replace this
	// cast with the result.
	if (ComputeNumSignBits(Res, 0, &Sext) > DestBitSize - SrcBitSize)
	return replaceInstUsesWith(Sext, Res);
	// We need to emit a shl + ashr to do the sign extend.
	Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize);
	return BinaryOperator::CreateAShr(Builder.CreateShl(Res, ShAmt, "sext"),
	ShAmt);
	}

Probably this is targeted at the case where evaluating in a different size actually reduces instructions.

[leewei05]

@nikic Thanks, good to know! Do you have a suggested solution for this particular issue? I am thinking if this issue is fixable for someone like me who has just started to get familiar with InstCombine.

[VedantParanjape]

@leewei05 Yes, your understanding is correct, and this transform does go against our usual policy. I'm somewhat surprised this exists.

For reference, this is the relevant code:

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

Lines 1494 to 1513 in 4e330fa

	// Try to extend the entire expression tree to the wide destination type.
	if (shouldChangeType(SrcTy, DestTy) && canEvaluateSExtd(Src, DestTy)) {
	// Okay, we can transform this! Insert the new expression now.
	LLVM_DEBUG(
	dbgs() << "ICE: EvaluateInDifferentType converting expression type"
	" to avoid sign extend: "
	<< Sext << '\n');
	Value *Res = EvaluateInDifferentType(Src, DestTy, true);
	assert(Res->getType() == DestTy);
	// If the high bits are already filled with sign bit, just replace this
	// cast with the result.
	if (ComputeNumSignBits(Res, 0, &Sext) > DestBitSize - SrcBitSize)
	return replaceInstUsesWith(Sext, Res);
	// We need to emit a shl + ashr to do the sign extend.
	Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize);
	return BinaryOperator::CreateAShr(Builder.CreateShl(Res, ShAmt, "sext"),
	ShAmt);
	}

Probably this is targeted at the case where evaluating in a different size actually reduces instructions.

isn't it something like instcombine does the optimization, and backend will revert it if it's not profitable for that backend?

[nikic]

@nikic Thanks, good to know! Do you have a suggested solution for this particular issue? I am thinking if this issue is fixable for someone like me who has just started to get familiar with InstCombine.

I'd start by deleting the code introducing the shift pair, look what regresses in the tests, and then try to figure out how to preserve those cases while forbidding this one.

[leewei05]

@nikic Thanks, good to know! Do you have a suggested solution for this particular issue? I am thinking if this issue is fixable for someone like me who has just started to get familiar with InstCombine.

I'd start by deleting the code introducing the shift pair, look what regresses in the tests, and then try to figure out how to preserve those cases while forbidding this one.

Thanks! I'll assign myself and try to work on this one.

[tianleliu]

I also meet the similar issue in https://discourse.llvm.org/t/rfc-spgo-passpipelines-adding-instcombinepass-and-simplifycfgpass-before-sampleprofileloaderpass-when-building-in-spgo-mode/83340. In my case, though this transition breaks following optimizations which lead to performance drop, "sext(trunc) to shl(ashr)" itself looks reasonable to me.
In my pattern, InstCombine transfers sext(trunc) to shl(ashr), and trunc is erased, because src type and dest type in sext and trunc are the same. https://alive2.llvm.org/ce/z/qmAN5c
If my understanding is right, InstCombine checks the dest and src types in

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

Line 237 in 4e330fa

X->getType() == Ty)

But it also permits the transition no matter if dest and src type are the same at

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

Line 1083 in 4e330fa

case Instruction::Trunc: // zext(trunc(x)) -> trunc(x) or zext(x)

When trunc could be erased, it seems transferring sext(trunc) to shl(ashr) makes sense, because backend might generate more efficient instructions at least in x86 SIMD mode: pslld and psrad are both ~1 cycle, but packssdw is ~3 cycles. In SIMD instructions, the same element size operations are recommended.