# Changeset View

Changeset View

# Standalone View

Standalone View

# 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: | ||||

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! | |||||

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 Lines | static 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 | |||||

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, | |||||

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) { | |||||

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 |

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