Skip to content

Wrong canonicalization of add and bitwise logic operation #113301

Closed
@bongjunj

Description

@bongjunj

// Match
// (X + C2) | C
// (X + C2) ^ C
// (X + C2) & C
// and convert to do the bitwise logic first:
// (X | C) + C2
// (X ^ C) + C2
// (X & C) + C2
// iff bits affected by logic op are lower than last bit affected by math op
static Instruction *canonicalizeLogicFirst(BinaryOperator &I,
InstCombiner::BuilderTy &Builder) {
Type *Ty = I.getType();
Instruction::BinaryOps OpC = I.getOpcode();
Value *Op0 = I.getOperand(0);
Value *Op1 = I.getOperand(1);
Value *X;
const APInt *C, *C2;
if (!(match(Op0, m_OneUse(m_Add(m_Value(X), m_APInt(C2)))) &&
match(Op1, m_APInt(C))))
return nullptr;
unsigned Width = Ty->getScalarSizeInBits();
unsigned LastOneMath = Width - C2->countr_zero();
switch (OpC) {
case Instruction::And:
if (C->countl_one() < LastOneMath)
return nullptr;
break;
case Instruction::Xor:
case Instruction::Or:
if (C->countl_zero() < LastOneMath)
return nullptr;
break;
default:
llvm_unreachable("Unexpected BinaryOp!");
}
Value *NewBinOp = Builder.CreateBinOp(OpC, X, ConstantInt::get(Ty, *C));
return BinaryOperator::CreateWithCopiedFlags(Instruction::Add, NewBinOp,
ConstantInt::get(Ty, *C2), Op0);
}

Alive2 report: https://alive2.llvm.org/ce/z/n2TNxF

----------------------------------------
define <2 x i8> @t5_splat_undef_0b1000.2(<2 x i8> %x) {
#0:
  %#1 = xor <2 x i8> %x, { 15, undef }
  %x.lowbits.are.zero = icmp eq <2 x i8> %#1, { 0, 0 }
  %x.biased = add <2 x i8> %x, { 16, 16 }
  %x.biased.highbits = and <2 x i8> %x.biased, { 240, 240 }
  %x.roundedup = select <2 x i1> %x.lowbits.are.zero, <2 x i8> %x, <2 x i8> %x.biased.highbits
  ret <2 x i8> %x.roundedup
}
=>
define <2 x i8> @t5_splat_undef_0b1000.2(<2 x i8> %x) {
#0:
  %x.lowbits.are.zero = icmp eq <2 x i8> %x, { 15, undef }
  %#1 = and <2 x i8> %x, { 240, 240 }
  %x.biased.highbits = add <2 x i8> %#1, { 16, 16 }
  %x.roundedup = select <2 x i1> %x.lowbits.are.zero, <2 x i8> { 15, undef }, <2 x i8> %x.biased.highbits
  ret <2 x i8> %x.roundedup
}
Transformation doesn't verify!

ERROR: Value mismatch

Example:
<2 x i8> %x = < #x00 (0), #x00 (0) >

Source:
<2 x i8> %#1 = < #x0f (15), #x00 (0)	[based on undef value] >
<2 x i1> %x.lowbits.are.zero = < #x0 (0), #x1 (1) >
<2 x i8> %x.biased = < #x10 (16), #x10 (16) >
<2 x i8> %x.biased.highbits = < #x10 (16), #x10 (16) >
<2 x i8> %x.roundedup = < #x10 (16), #x00 (0) >

Target:
<2 x i1> %x.lowbits.are.zero = < #x0 (0), #x1 (1) >
<2 x i8> %#1 = < #x00 (0), #x00 (0) >
<2 x i8> %x.biased.highbits = < #x10 (16), #x10 (16) >
<2 x i8> %x.roundedup = < #x10 (16), #x02 (2) >
Source value: < #x10 (16), #x00 (0) >
Target value: < #x10 (16), #x02 (2) >


----------------------------------------
define i8 @t5_splat_undef_0b1000.3(i8 %x) {
#0:
  %#1 = xor i8 %x, undef
  %x.lowbits.are.zero = icmp eq i8 %#1, 0
  %x.biased = add i8 %x, 16
  %x.biased.highbits = and i8 %x.biased, 240
  %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
  ret i8 %x.roundedup
}
=>
define i8 @t5_splat_undef_0b1000.3(i8 %x) {
#0:
  ret i8 %x
}
Transformation seems to be correct!

Summary:
  1 correct transformations
  1 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions