Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

Differential D140666 Diff 496325 llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Changeset View

Standalone View

View Options

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Show First 20 Lines • Show All 619 Lines • ▼ Show 20 Lines if (Mask & AMask_NotAllOnes) {
// the same as either B or D). // the same as either B or D).
APInt NewMask = *ConstB | *ConstD; APInt NewMask = *ConstB | *ConstD;
if (NewMask == *ConstB) if (NewMask == *ConstB)
return LHS; return LHS;
else if (NewMask == *ConstD) else if (NewMask == *ConstD)
return RHS; return RHS;
} }
if (Mask & BMask_Mixed) { if (Mask & (BMask_Mixed | BMask_NotMixed)) {
// Mixed:
bcl5980Unsubmitted
Done
ReplyInline Actions

Can we merge the code into here? It looks the logic is almost the same.

bcl5980: Can we merge the code into here? It looks the logic is almost the same.
bcl5980Unsubmitted
Done
ReplyInline Actions

Is Mask & (BMask_Mixed | BMask_NotMixed) better?

bcl5980: Is `Mask & (BMask_Mixed | BMask_NotMixed)` better?
// (icmp eq (A & B), C) & (icmp eq (A & D), E) // (icmp eq (A & B), C) & (icmp eq (A & D), E)
// We already know that B & C == C && D & E == E. // We already know that B & C == C && D & E == E.
// If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of
// C and E, which are shared by both the mask B and the mask D, don't // C and E, which are shared by both the mask B and the mask D, don't
// contradict, then we can transform to // contradict, then we can transform to
// -> (icmp eq (A & (B|D)), (C|E)) // -> (icmp eq (A & (B|D)), (C|E))
// Currently, we only handle the case of B, C, D, and E being constant. // Currently, we only handle the case of B, C, D, and E being constant.
// We can't simply use C and E because we might actually handle // We can't simply use C and E because we might actually handle
// (icmp ne (A & B), B) & (icmp eq (A & D), D) // (icmp ne (A & B), B) & (icmp eq (A & D), D)
// with B and D, having a single bit set. // with B and D, having a single bit set.
// NotMixed:
// (icmp ne (A & B), C) & (icmp ne (A & D), E)
// -> (icmp ne (A & (B & D)), (C & E))
// Check the intersection (B & D) for inequality.
// Assume that (B & D) == B || (B & D) == D, i.e B/D is a subset of D/B
// and (B & D) & (C ^ E) == 0, bits of C and E, which are shared by both the
// B and the D, don't contradict.
// Note that we can assume (~B & C) == 0 && (~D & E) == 0, previous
// operation should delete these icmps if it hadn't been met.
const APInt *OldConstC, *OldConstE; const APInt *OldConstC, *OldConstE;
if (!match(C, m_APInt(OldConstC)) || !match(E, m_APInt(OldConstE))) if (!match(C, m_APInt(OldConstC)) || !match(E, m_APInt(OldConstE)))
return nullptr; return nullptr;
const APInt ConstC = PredL != NewCC ? *ConstB ^ *OldConstC : *OldConstC; auto FoldBMixed = [&](ICmpInst::Predicate CC, bool IsNot) -> Value * {
const APInt ConstE = PredR != NewCC ? *ConstD ^ *OldConstE : *OldConstE; CC = IsNot ? CmpInst::getInversePredicate(CC) : CC;
const APInt ConstC = PredL != CC ? *ConstB ^ *OldConstC : *OldConstC;
const APInt ConstE = PredR != CC ? *ConstD ^ *OldConstE : *OldConstE;
// If there is a conflict, we should actually return a false for the
// whole construct.
if (((*ConstB & *ConstD) & (ConstC ^ ConstE)).getBoolValue()) if (((*ConstB & *ConstD) & (ConstC ^ ConstE)).getBoolValue())
bcl5980Unsubmitted
Done
ReplyInline Actions

Is this condition the same to line 660 ? Can we add some code like:

if (((*ConstB & *ConstD) & (ConstC ^ ConstE)).getBoolValue())
  return isMixed ? ConstantInt::get(LHS->getType(), !IsAnd) : nullptr
bcl5980: Is this condition the same to line 660 ? Can we add some code like: ``` if (((*ConstB &…
return ConstantInt::get(LHS->getType(), !IsAnd); return IsNot ? nullptr : ConstantInt::get(LHS->getType(), !IsAnd);
if (IsNot && !ConstB->isSubsetOf(*ConstD) && !ConstD->isSubsetOf(*ConstB))
bcl5980Unsubmitted
Done
ReplyInline Actions

This also can be shared by select like:

Value *ICmpLHS = Builder.CreateBinOp(isMixed ? Instruction::Or : Instruction::And);
Value * ICmpRHS = ConstantInt::get(A->getType(), isMixed ? (ConstC | ConstE) : (ConstC & ConstE));

Or you can check isMixed at first:

Instruction::BinaryOps ICmpLHSOpcode;
APInt ICmpRHSAP;
Value* ICmpAndConflictBailout;
if (isMixed) {
  ICmpLHSOpcode = Instruction::Or;
  ICmpRHSAP = ConstC | ConstE;
  ICmpAndConflictBailout = ConstantInt::get(LHS->getType(), !IsAnd);
} else {
  ICmpLHSOpcode = Instruction::And;
  ICmpRHSAP = ConstC & ConstE;
  ICmpAndConflictBailout = ConstantInt::get(LHS->getType(), !IsAnd);
}
bcl5980: This also can be shared by select like: ``` Value *ICmpLHS = Builder.CreateBinOp(isMixed ?
return nullptr;
spatelUnsubmitted
Not Done
ReplyInline Actions

Is there a negative test for this condition? Add a "negative test" comment if it is already here. Otherwise, can we add it?

spatel: Is there a negative test for this condition? Add a "negative test" comment if it is already…
inclycAuthorUnsubmitted
Done
ReplyInline Actions

Yes. See @masked_icmps_bmask_notmixed_not_subset_notoptimized in D142090. "not subset" refers to this condition

inclyc: Yes. See @masked_icmps_bmask_notmixed_not_subset_notoptimized in D142090. "not subset" refers…
Value *NewOr1 = Builder.CreateOr(B, D); APInt BD, CE;
Value *NewAnd = Builder.CreateAnd(A, NewOr1); if (IsNot) {
Constant *NewOr2 = ConstantInt::get(A->getType(), ConstC | ConstE); BD = *ConstB & *ConstD;
return Builder.CreateICmp(NewCC, NewAnd, NewOr2); CE = ConstC & ConstE;
} else {
BD = *ConstB | *ConstD;
CE = ConstC | ConstE;
} }
Value *NewAnd = Builder.CreateAnd(A, BD);
Value *CEVal = ConstantInt::get(A->getType(), CE);
return Builder.CreateICmp(CC, CEVal, NewAnd);
};
if (Mask & BMask_Mixed)
return FoldBMixed(NewCC, false);
if (Mask & BMask_NotMixed) // can be else also
return FoldBMixed(NewCC, true);
}
return nullptr; return nullptr;
} }
/// Try to fold a signed range checked with lower bound 0 to an unsigned icmp. /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
/// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
/// If \p Inverted is true then the check is for the inverted range, e.g. /// If \p Inverted is true then the check is for the inverted range, e.g.
/// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n /// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
Value *InstCombinerImpl::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, Value *InstCombinerImpl::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1,
spatelUnsubmitted
Done
ReplyInline Actions

Add a string message to each assert like "Expected impossible compares to be simplified".

But I'm skeptical that we can actually do that. Ie, how do we guarantee that the operands of this logic instruction were already visited before we got here? If we can't guarantee that, just bail out instead.

spatel: Add a string message to each assert like "Expected impossible compares to be simplified". But…
bcl5980Unsubmitted
Done
ReplyInline Actions

I think the assert should be OK. simplifyICmpInst will optimize the icmp to constant at very early time before the assert triggered.

bcl5980: I think the assert should be OK. simplifyICmpInst will optimize the icmp to constant at very…
spatelUnsubmitted
Done
ReplyInline Actions

No - this is a mistake I've made a few times in the past. :)

In simple examples (one basic block), you are correct - we will visit the icmp operands before the bitwise logic instruction.

But it is possible that we are visiting this bitwise logic instruction before visiting the icmp instructions. In that case, we can see unsimplified instructions.

Usually, it takes a long time before the bug is discovered in the wild, and/or we fuzz our way to a test that creates just the right sequence to trigger the problem.

I advise that we just 'return nullptr' here.

spatel: No - this is a mistake I've made a few times in the past. :) In simple examples (one basic…
bcl5980Unsubmitted
Done
ReplyInline Actions

Thanks for the explaination. Then maybe we should add bail out for if (Mask & BMask_Mixed) also.

bcl5980: Thanks for the explaination. Then maybe we should add bail out for `if (Mask & BMask_Mixed)`…
bcl5980Unsubmitted
Done
ReplyInline Actions

After read the code again I find in the function getMaskedICmpType: the mask BMask_Mixed and BMask_NotMixed already means B&C == C , D&E == E.
So I think early bail out is redundant.

bcl5980: After read the code again I find in the function `getMaskedICmpType`: the mask `BMask_Mixed`…
inclycAuthorUnsubmitted
Done
ReplyInline Actions

After read the code again I find in the function getMaskedICmpType: the mask BMask_Mixed and BMask_NotMixed already means B&C == C , D&E == E.
So I think early bail out is redundant.

This looks correct, and we've removed the relevant checks in the code. @spatel WDYT?

inclyc: > After read the code again I find in the function `getMaskedICmpType`: the mask `BMask_Mixed`…
bool Inverted) { bool Inverted) {
// Check the lower range comparison, e.g. x >= 0 // Check the lower range comparison, e.g. x >= 0
// InstCombine already ensured that if there is a constant it's on the RHS. // InstCombine already ensured that if there is a constant it's on the RHS.
ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1)); ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1));
bcl5980Unsubmitted
Done
ReplyInline Actions

I think this code can be shared by both BMask_Mixed and BMask_NotMixed also.

bcl5980: I think this code can be shared by both BMask_Mixed and BMask_NotMixed also.
if (!RangeStart) if (!RangeStart)
return nullptr; return nullptr;
spatelUnsubmitted
Done
ReplyInline Actions

Why does this use B and D rather than ConstB and ConstD?
In fact, why do we create this at all - can we use ConstT in the next line?

spatel: Why does this use B and D rather than ConstB and ConstD? In fact, why do we create this at all…
ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() : ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() :
Cmp0->getPredicate()); Cmp0->getPredicate());
// Accept x > -1 or x >= 0 (after potentially inverting the predicate). // Accept x > -1 or x >= 0 (after potentially inverting the predicate).
if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) || if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) ||
(Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero()))) (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero())))
return nullptr; return nullptr;
▲ Show 20 Lines • Show All 3,836 Lines • Show Last 20 Lines