Page MenuHomePhabricator
Differential D54137 Diff 176310 lib/Target/AArch64/AArch64ISelLowering.cpp

Changeset View

Standalone View

View Options

lib/Target/AArch64/AArch64ISelLowering.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 1,540 Lines • ▼ Show 20 Lines
/// a comparison. They set the NZCV flags to a predefined value if their /// a comparison. They set the NZCV flags to a predefined value if their
/// predicate is false. This allows to express arbitrary conjunctions, for /// predicate is false. This allows to express arbitrary conjunctions, for
/// example "cmp 0 (and (setCA (cmp A)) (setCB (cmp B)))" /// example "cmp 0 (and (setCA (cmp A)) (setCB (cmp B)))"
/// expressed as: /// expressed as:
/// cmp A /// cmp A
/// ccmp B, inv(CB), CA /// ccmp B, inv(CB), CA
/// check for CB flags /// check for CB flags
/// ///
/// In general we can create code for arbitrary "... (and (and A B) C)" /// This naturally lets us implement chains of AND operations with SETCC
/// sequences. We can also implement some "or" expressions, because "(or A B)" /// operands. And we can even implement some other situations by transforming
/// is equivalent to "not (and (not A) (not B))" and we can implement some /// them:
/// negation operations: /// - We can implement (NEG SETCC) i.e. negating a single comparison by
/// We can negate the results of a single comparison by inverting the flags /// negating the flags used in a CCMP/FCCMP operations.
/// used when the predicate fails and inverting the flags tested in the next /// - We can negate the result of a whole chain of CMP/CCMP/FCCMP operations
/// instruction; We can also negate the results of the whole previous /// by negating the flags we test for afterwards. i.e.
/// conditional compare sequence by inverting the flags tested in the next /// NEG (CMP CCMP CCCMP ...) can be implemented.
/// instruction. However there is no way to negate the result of a partial /// - Note that we can only ever negate all previously processed results.
/// sequence. /// What we can not implement by flipping the flags to test is a negation
/// of two sub-trees (because the negation affects all sub-trees emitted so
/// far, so the 2nd sub-tree we emit would also affect the first).
/// With those tools we can implement some OR operations:
/// - (OR (SETCC A) (SETCC B)) can be implemented via:
/// NEG (AND (NEG (SETCC A)) (NEG (SETCC B)))
/// - After transforming OR to NEG/AND combinations we may be able to use NEG
/// elimination rules from earlier to implement the whole thing as a
/// CCMP/FCCMP chain.
/// ///
/// Therefore on encountering an "or" expression we can negate the subtree on /// As complete example:
efriedmaUnsubmitted
Done
ReplyInline Actions

Maybe include a second step here, which explicitly reassociates this expression?

efriedma: Maybe include a second step here, which explicitly reassociates this expression?
/// one side and have to be able to push the negate to the leafs of the subtree /// or (or (setCA (cmp A)) (setCB (cmp B)))
/// on the other side (see also the comments in code). As complete example:
/// "or (or (setCA (cmp A)) (setCB (cmp B)))
/// (and (setCC (cmp C)) (setCD (cmp D)))" /// (and (setCC (cmp C)) (setCD (cmp D)))"
/// is transformed to /// can be reassociated to:
/// "not (and (not (and (setCC (cmp C)) (setCC (cmp D)))) /// or (and (setCC (cmp C)) setCD (cmp D))
// (or (setCA (cmp A)) (setCB (cmp B)))
/// can be transformed to:
/// not (and (not (and (setCC (cmp C)) (setCD (cmp D))))
/// (and (not (setCA (cmp A)) (not (setCB (cmp B))))))" /// (and (not (setCA (cmp A)) (not (setCB (cmp B))))))"
/// and implemented as: /// which can be implemented as:
/// cmp C /// cmp C
/// ccmp D, inv(CD), CC /// ccmp D, inv(CD), CC
/// ccmp A, CA, inv(CD) /// ccmp A, CA, inv(CD)
/// ccmp B, CB, inv(CA) /// ccmp B, CB, inv(CA)
/// check for CB flags /// check for CB flags
/// A counterexample is "or (and A B) (and C D)" which cannot be implemented ///
/// by conditional compare sequences. /// A counterexample is "or (and A B) (and C D)" which translates to
/// not (and (not (and (not A) (not B))) (not (and (not C) (not D)))), we
/// can only implement 1 of the inner (not) operations, but not both!
efriedmaUnsubmitted
Done
ReplyInline Actions

Would it be possible to use an extra CCMP to "negate" a condition, using something like "ccmp xzr, xzr"? I'm not sure it's actually a good idea, but it seems feasible.

efriedma: Would it be possible to use an extra CCMP to "negate" a condition, using something like "ccmp…
/// @{ /// @{
/// Create a conditional comparison; Use CCMP, CCMN or FCCMP as appropriate. /// Create a conditional comparison; Use CCMP, CCMN or FCCMP as appropriate.
static SDValue emitConditionalComparison(SDValue LHS, SDValue RHS, static SDValue emitConditionalComparison(SDValue LHS, SDValue RHS,
ISD::CondCode CC, SDValue CCOp, ISD::CondCode CC, SDValue CCOp,
AArch64CC::CondCode Predicate, AArch64CC::CondCode Predicate,
AArch64CC::CondCode OutCC, AArch64CC::CondCode OutCC,
const SDLoc &DL, SelectionDAG &DAG) { const SDLoc &DL, SelectionDAG &DAG) {
Show All 23 Linesstatic SDValue emitConditionalComparison(SDValue LHS, SDValue RHS,
AArch64CC::CondCode InvOutCC = AArch64CC::getInvertedCondCode(OutCC); AArch64CC::CondCode InvOutCC = AArch64CC::getInvertedCondCode(OutCC);
unsigned NZCV = AArch64CC::getNZCVToSatisfyCondCode(InvOutCC); unsigned NZCV = AArch64CC::getNZCVToSatisfyCondCode(InvOutCC);
SDValue NZCVOp = DAG.getConstant(NZCV, DL, MVT::i32); SDValue NZCVOp = DAG.getConstant(NZCV, DL, MVT::i32);
return DAG.getNode(Opcode, DL, MVT_CC, LHS, RHS, NZCVOp, Condition, CCOp); return DAG.getNode(Opcode, DL, MVT_CC, LHS, RHS, NZCVOp, Condition, CCOp);
} }
/// Returns true if @p Val is a tree of AND/OR/SETCC operations that can be /// Returns true if @p Val is a tree of AND/OR/SETCC operations that can be
/// expressed as a conjunction. See \ref AArch64CCMP. /// expressed as a conjunction. See \ref AArch64CCMP.
/// \param CanNegate Set to true if we can also emit the negation of the /// \param CanNegate Set to true if we can negate the whole sub-tree just by
/// tree as a conjunction. /// changing the conditions on the SETCC tests.
/// (this means we can call emitConjunctionRec() with
/// Negate==true on this sub-tree)
/// \param MustBeFirst Set to true if this subtree needs to be negated and we
/// cannot do the negation naturally. We are required to
efriedmaUnsubmitted
Done
ReplyInline Actions

In other words, MustBeFirst is true when the outermost expression of the transformed tree is a "not", as opposed to an "and" or a "setcc"?

efriedma: In other words, MustBeFirst is true when the outermost expression of the transformed tree is a…
/// emit the subtree first in this case.
/// \param WillNegate Is true if are called when the result of this
/// subexpression must be negated. This happens when the
/// outer expression is an OR. We can use this fact to know
/// that we have a double negation (or (or ...) ...) that
/// can be implemented for free.
static bool canEmitConjunction(const SDValue Val, bool &CanNegate, static bool canEmitConjunction(const SDValue Val, bool &CanNegate,
bool &MustBeFirst, bool WillNegate,
efriedmaUnsubmitted
Done
ReplyInline Actions

Missing documentation for WillNegate?

efriedma: Missing documentation for WillNegate?
unsigned Depth = 0) { unsigned Depth = 0) {
if (!Val.hasOneUse()) if (!Val.hasOneUse())
return false; return false;
unsigned Opcode = Val->getOpcode(); unsigned Opcode = Val->getOpcode();
if (Opcode == ISD::SETCC) { if (Opcode == ISD::SETCC) {
if (Val->getOperand(0).getValueType() == MVT::f128) if (Val->getOperand(0).getValueType() == MVT::f128)
return false; return false;
CanNegate = true; CanNegate = true;
MustBeFirst = false;
return true; return true;
} }
// Protect against exponential runtime and stack overflow. // Protect against exponential runtime and stack overflow.
if (Depth > 6) if (Depth > 6)
return false; return false;
if (Opcode == ISD::AND || Opcode == ISD::OR) { if (Opcode == ISD::AND || Opcode == ISD::OR) {
bool IsOR = Opcode == ISD::OR;
SDValue O0 = Val->getOperand(0); SDValue O0 = Val->getOperand(0);
SDValue O1 = Val->getOperand(1); SDValue O1 = Val->getOperand(1);
bool CanNegateL; bool CanNegateL;
if (!canEmitConjunction(O0, CanNegateL, Depth+1)) bool MustBeFirstL;
if (!canEmitConjunction(O0, CanNegateL, MustBeFirstL, IsOR, Depth+1))
return false; return false;
bool CanNegateR; bool CanNegateR;
if (!canEmitConjunction(O1, CanNegateR, Depth+1)) bool MustBeFirstR;
if (!canEmitConjunction(O1, CanNegateR, MustBeFirstR, IsOR, Depth+1))
return false; return false;
if (Opcode == ISD::OR) { if (MustBeFirstL && MustBeFirstR)
// For an OR expression we need to be able to negate at least one side or return false;
// we cannot do the transformation at all.
if (IsOR) {
efriedmaUnsubmitted
Done
ReplyInline Actions

IsOR?

efriedma: IsOR?
// For an OR expression we need to be able to naturally negate at least
// one side or we cannot do the transformation at all.
if (!CanNegateL && !CanNegateR) if (!CanNegateL && !CanNegateR)
return false; return false;
// However if we can negate x and y, then we can change // If we the result of the OR will be negated and we can naturally negate
// (not (or x y)) // the leafs, then this sub-tree as a whole negates naturally.
// into CanNegate = WillNegate && CanNegateL && CanNegateR;
// (and (not x) (not y)) // If we cannot naturally negate the whole sub-tree, then this must be
// to eliminate the outer negation. // emitted first.
CanNegate = CanNegateL && CanNegateR; MustBeFirst = !CanNegate;
} else { } else {
// If the operands are OR expressions then we finally need to negate their assert(Opcode == ISD::AND && "Must be OR or AND");
// outputs, we can only do that for the operand with emitted last by // We cannot naturally negate an AND operation.
// negating OutCC, not for both operands.
bool NeedsNegOutL = O0->getOpcode() == ISD::OR;
bool NeedsNegOutR = O1->getOpcode() == ISD::OR;
if (NeedsNegOutL && NeedsNegOutR)
return false;
// We cannot negate an AND operation.
CanNegate = false; CanNegate = false;
MustBeFirst = MustBeFirstL || MustBeFirstR;
} }
return true; return true;
} }
return false; return false;
} }
/// Emit conjunction or disjunction tree with the CMP/FCMP followed by a chain /// Emit conjunction or disjunction tree with the CMP/FCMP followed by a chain
/// of CCMP/CFCMP ops. See @ref AArch64CCMP. /// of CCMP/CFCMP ops. See @ref AArch64CCMP.
/// Tries to transform the given i1 producing node @p Val to a series compare /// Tries to transform the given i1 producing node @p Val to a series compare
/// and conditional compare operations. @returns an NZCV flags producing node /// and conditional compare operations. @returns an NZCV flags producing node
/// and sets @p OutCC to the flags that should be tested or returns SDValue() if /// and sets @p OutCC to the flags that should be tested or returns SDValue() if
/// transformation was not possible. /// transformation was not possible.
/// On recursive invocations @p PushNegate may be set to true to have negation /// \p Negate is true if we want this sub-tree being negated just by changing
/// effects pushed to the tree leafs; @p Predicate is an NZCV flag predicate /// SETCC conditions.
/// for the comparisons in the current subtree; @p Depth limits the search
/// depth to avoid stack overflow.
static SDValue emitConjunctionRec(SelectionDAG &DAG, SDValue Val, static SDValue emitConjunctionRec(SelectionDAG &DAG, SDValue Val,
AArch64CC::CondCode &OutCC, bool Negate, SDValue CCOp, AArch64CC::CondCode &OutCC, bool Negate, SDValue CCOp,
AArch64CC::CondCode Predicate) { AArch64CC::CondCode Predicate) {
// We're at a tree leaf, produce a conditional comparison operation. // We're at a tree leaf, produce a conditional comparison operation.
unsigned Opcode = Val->getOpcode(); unsigned Opcode = Val->getOpcode();
if (Opcode == ISD::SETCC) { if (Opcode == ISD::SETCC) {
SDValue LHS = Val->getOperand(0); SDValue LHS = Val->getOperand(0);
SDValue RHS = Val->getOperand(1); SDValue RHS = Val->getOperand(1);
Show All 25 Lines if (Opcode == ISD::SETCC) {
// Produce a normal comparison if we are first in the chain // Produce a normal comparison if we are first in the chain
if (!CCOp) if (!CCOp)
return emitComparison(LHS, RHS, CC, DL, DAG); return emitComparison(LHS, RHS, CC, DL, DAG);
// Otherwise produce a ccmp. // Otherwise produce a ccmp.
return emitConditionalComparison(LHS, RHS, CC, CCOp, Predicate, OutCC, DL, return emitConditionalComparison(LHS, RHS, CC, CCOp, Predicate, OutCC, DL,
DAG); DAG);
} }
assert((Opcode == ISD::AND || (Opcode == ISD::OR && Val->hasOneUse())) && assert(Val->hasOneUse() && "Valid conjunction/disjunction tree");
"Valid conjunction/disjunction tree");
// Check if both sides can be transformed. bool IsOR = Opcode == ISD::OR;
SDValue LHS = Val->getOperand(0);
SDValue RHS = Val->getOperand(1);
// In case of an OR we need to negate our operands and the result. SDValue LHS = Val->getOperand(0);
// (A v B) <=> not(not(A) ^ not(B))
bool NegateOpsAndResult = Opcode == ISD::OR;
// We can negate the results of all previous operations by inverting the
// predicate flags giving us a free negation for one side. The other side
// must be negatable by itself.
if (NegateOpsAndResult) {
// See which side we can negate.
bool CanNegateL; bool CanNegateL;
bool isValidL = canEmitConjunction(LHS, CanNegateL); bool MustBeFirstL;
assert(isValidL && "Valid conjunction/disjunction tree"); bool ValidL = canEmitConjunction(LHS, CanNegateL, MustBeFirstL, IsOR);
(void)isValidL; assert(ValidL && "Valid conjunction/disjunction tree");
(void)ValidL;
#ifndef NDEBUG SDValue RHS = Val->getOperand(1);
bool CanNegateR; bool CanNegateR;
bool isValidR = canEmitConjunction(RHS, CanNegateR); bool MustBeFirstR;
assert(isValidR && "Valid conjunction/disjunction tree"); bool ValidR = canEmitConjunction(RHS, CanNegateR, MustBeFirstR, IsOR);
assert((CanNegateL || CanNegateR) && "Valid conjunction/disjunction tree"); assert(ValidR && "Valid conjunction/disjunction tree");
#endif (void)ValidR;
// Swap sub-tree that must come first to the right side.
if (MustBeFirstL) {
assert(!MustBeFirstR && "Valid conjunction/disjunction tree");
std::swap(LHS, RHS);
std::swap(CanNegateL, CanNegateR);
std::swap(MustBeFirstL, MustBeFirstR);
}
// Order the side which we cannot negate to RHS so we can emit it first. bool NegateR;
if (!CanNegateL) bool NegateAfterR;
bool NegateL;
bool NegateAfterAll;
if (Opcode == ISD::OR) {
// Swap the sub-tree that we can negate naturally to the left.
if (!CanNegateL) {
assert(CanNegateR && "at least one side must be negatable");
assert(!MustBeFirstR && "invalid conjunction/disjunction tree");
assert(!Negate);
std::swap(LHS, RHS); std::swap(LHS, RHS);
NegateR = false;
NegateAfterR = true;
} else { } else {
bool NeedsNegOutL = LHS->getOpcode() == ISD::OR; // Negate the left sub-tree if possible, otherwise negate the result.
assert((!NeedsNegOutL || RHS->getOpcode() != ISD::OR) && NegateR = CanNegateR;
"Valid conjunction/disjunction tree"); NegateAfterR = !CanNegateR;
// Order the side where we need to negate the output flags to RHS so it }
// gets emitted first. NegateL = true;
if (NeedsNegOutL) NegateAfterAll = !Negate;
std::swap(LHS, RHS); } else {
assert(Opcode == ISD::AND && "Valid conjunction/disjunction tree");
assert(!Negate && "Valid conjunction/disjunction tree");
NegateL = false;
NegateR = false;
NegateAfterR = false;
NegateAfterAll = false;
} }
// Emit RHS. If we want to negate the tree we only need to push a negate // Emit sub-trees.
// through if we are already in a PushNegate case, otherwise we can negate
// the "flags to test" afterwards.
AArch64CC::CondCode RHSCC; AArch64CC::CondCode RHSCC;
SDValue CmpR = emitConjunctionRec(DAG, RHS, RHSCC, Negate, SDValue CmpR = emitConjunctionRec(DAG, RHS, RHSCC, NegateR, CCOp, Predicate);
CCOp, Predicate); if (NegateAfterR)
if (NegateOpsAndResult && !Negate)
RHSCC = AArch64CC::getInvertedCondCode(RHSCC); RHSCC = AArch64CC::getInvertedCondCode(RHSCC);
// Emit LHS. We may need to negate it. SDValue CmpL = emitConjunctionRec(DAG, LHS, OutCC, NegateL, CmpR, RHSCC);
SDValue CmpL = emitConjunctionRec(DAG, LHS, OutCC, if (NegateAfterAll)
NegateOpsAndResult, CmpR,
RHSCC);
// If we transformed an OR to and AND then we have to negate the result
// (or absorb the Negate parameter).
if (NegateOpsAndResult && !Negate)
OutCC = AArch64CC::getInvertedCondCode(OutCC); OutCC = AArch64CC::getInvertedCondCode(OutCC);
return CmpL; return CmpL;
} }
/// Emit expression as a conjunction (a series of CCMP/CFCMP ops). /// Emit expression as a conjunction (a series of CCMP/CFCMP ops).
/// In some cases this is even possible with OR operations in the expression. /// In some cases this is even possible with OR operations in the expression.
/// See \ref AArch64CCMP. /// See \ref AArch64CCMP.
/// \see emitConjunctionRec(). /// \see emitConjunctionRec().
static SDValue emitConjunction(SelectionDAG &DAG, SDValue Val, static SDValue emitConjunction(SelectionDAG &DAG, SDValue Val,
AArch64CC::CondCode &OutCC) { AArch64CC::CondCode &OutCC) {
bool DummyCanNegate; bool DummyCanNegate;
if (!canEmitConjunction(Val, DummyCanNegate)) bool DummyMustBeFirst;
if (!canEmitConjunction(Val, DummyCanNegate, DummyMustBeFirst, false))
return SDValue(); return SDValue();
return emitConjunctionRec(DAG, Val, OutCC, false, SDValue(), AArch64CC::AL); return emitConjunctionRec(DAG, Val, OutCC, false, SDValue(), AArch64CC::AL);
} }
/// @} /// @}
/// Returns how profitable it is to fold a comparison's operand's shift and/or /// Returns how profitable it is to fold a comparison's operand's shift and/or
▲ Show 20 Lines • Show All 9,982 Lines • Show Last 20 Lines