//
// The LLVM Compiler Infrastructure
//
-// This file was developed by Nate Begeman and is distributed under the
-// University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass combines dag nodes to form fewer, simpler DAG nodes. It can be run
// both before and after the DAG is legalized.
-//
-// FIXME: Missing folds
-// sdiv, udiv, srem, urem (X, const) where X is an integer can be expanded into
-// a sequence of multiplies, shifts, and adds. This should be controlled by
-// some kind of hint from the target that int div is expensive.
-// various folds of mulh[s,u] by constants such as -1, powers of 2, etc.
-//
-// FIXME: select C, pow2, pow2 -> something smart
-// FIXME: trunc(select X, Y, Z) -> select X, trunc(Y), trunc(Z)
-// FIXME: Dead stores -> nuke
-// FIXME: shr X, (and Y,31) -> shr X, Y (TRICKY!)
-// FIXME: mul (x, const) -> shifts + adds
-// FIXME: undef values
-// FIXME: divide by zero is currently left unfolded. do we want to turn this
-// into an undef?
-// FIXME: select ne (select cc, 1, 0), 0, true, false -> select cc, true, false
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "dagcombine"
-#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/SelectionDAG.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/MathExtras.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetOptions.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/CommandLine.h"
-#include <algorithm>
-#include <cmath>
-#include <iostream>
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/MathExtras.h"
#include <algorithm>
using namespace llvm;
+STATISTIC(NodesCombined , "Number of dag nodes combined");
+STATISTIC(PreIndexedNodes , "Number of pre-indexed nodes created");
+STATISTIC(PostIndexedNodes, "Number of post-indexed nodes created");
+
namespace {
- static Statistic<> NodesCombined ("dagcombiner",
- "Number of dag nodes combined");
-
+#ifndef NDEBUG
+ static cl::opt<bool>
+ ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
+ cl::desc("Pop up a window to show dags before the first "
+ "dag combine pass"));
+ static cl::opt<bool>
+ ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
+ cl::desc("Pop up a window to show dags before the second "
+ "dag combine pass"));
+#else
+ static const bool ViewDAGCombine1 = false;
+ static const bool ViewDAGCombine2 = false;
+#endif
+
+ static cl::opt<bool>
+ CombinerAA("combiner-alias-analysis", cl::Hidden,
+ cl::desc("Turn on alias analysis during testing"));
-static cl::opt<bool>
- CombinerAA("combiner-alias-analysis", cl::Hidden,
- cl::desc("Turn on alias analysis turning testing"));
-
-class VISIBILITY_HIDDEN DAGCombiner {
+ static cl::opt<bool>
+ CombinerGlobalAA("combiner-global-alias-analysis", cl::Hidden,
+ cl::desc("Include global information in alias analysis"));
+
+//------------------------------ DAGCombiner ---------------------------------//
+
+ class VISIBILITY_HIDDEN DAGCombiner {
SelectionDAG &DAG;
TargetLowering &TLI;
bool AfterLegalize;
// Worklist of all of the nodes that need to be simplified.
std::vector<SDNode*> WorkList;
+ // AA - Used for DAG load/store alias analysis.
+ AliasAnalysis &AA;
+
/// AddUsersToWorkList - When an instruction is simplified, add all users of
/// the instruction to the work lists because they might get more simplified
/// now.
void AddUsersToWorkList(SDNode *N) {
for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
UI != UE; ++UI)
- WorkList.push_back(*UI);
+ AddToWorkList(*UI);
}
/// removeFromWorkList - remove all instances of N from the worklist.
WorkList.end());
}
+ /// visit - call the node-specific routine that knows how to fold each
+ /// particular type of node.
+ SDOperand visit(SDNode *N);
+
public:
+ /// AddToWorkList - Add to the work list making sure it's instance is at the
+ /// the back (next to be processed.)
void AddToWorkList(SDNode *N) {
+ removeFromWorkList(N);
WorkList.push_back(N);
}
-
- SDOperand CombineTo(SDNode *N, const SDOperand *To, unsigned NumTo) {
+
+ SDOperand CombineTo(SDNode *N, const SDOperand *To, unsigned NumTo,
+ bool AddTo = true) {
assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
++NodesCombined;
- DEBUG(std::cerr << "\nReplacing "; N->dump();
- std::cerr << "\nWith: "; To[0].Val->dump(&DAG);
- std::cerr << " and " << NumTo-1 << " other values\n");
+ DOUT << "\nReplacing.1 "; DEBUG(N->dump(&DAG));
+ DOUT << "\nWith: "; DEBUG(To[0].Val->dump(&DAG));
+ DOUT << " and " << NumTo-1 << " other values\n";
std::vector<SDNode*> NowDead;
DAG.ReplaceAllUsesWith(N, To, &NowDead);
- // Push the new nodes and any users onto the worklist
- for (unsigned i = 0, e = NumTo; i != e; ++i) {
- WorkList.push_back(To[i].Val);
- AddUsersToWorkList(To[i].Val);
+ if (AddTo) {
+ // Push the new nodes and any users onto the worklist
+ for (unsigned i = 0, e = NumTo; i != e; ++i) {
+ AddToWorkList(To[i].Val);
+ AddUsersToWorkList(To[i].Val);
+ }
}
- // Nodes can end up on the worklist more than once. Make sure we do
- // not process a node that has been replaced.
+ // Nodes can be reintroduced into the worklist. Make sure we do not
+ // process a node that has been replaced.
removeFromWorkList(N);
for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
removeFromWorkList(NowDead[i]);
return SDOperand(N, 0);
}
- SDOperand CombineTo(SDNode *N, SDOperand Res) {
- return CombineTo(N, &Res, 1);
+ SDOperand CombineTo(SDNode *N, SDOperand Res, bool AddTo = true) {
+ return CombineTo(N, &Res, 1, AddTo);
}
- SDOperand CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) {
+ SDOperand CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1,
+ bool AddTo = true) {
SDOperand To[] = { Res0, Res1 };
- return CombineTo(N, To, 2);
+ return CombineTo(N, To, 2, AddTo);
}
private:
/// SimplifyDemandedBits - Check the specified integer node value to see if
/// it can be simplified or if things it uses can be simplified by bit
/// propagation. If so, return true.
- bool SimplifyDemandedBits(SDOperand Op) {
- TargetLowering::TargetLoweringOpt TLO(DAG);
+ bool SimplifyDemandedBits(SDOperand Op, uint64_t Demanded = ~0ULL) {
+ TargetLowering::TargetLoweringOpt TLO(DAG, AfterLegalize);
uint64_t KnownZero, KnownOne;
- uint64_t Demanded = MVT::getIntVTBitMask(Op.getValueType());
+ Demanded &= MVT::getIntVTBitMask(Op.getValueType());
if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO))
return false;
// Revisit the node.
- WorkList.push_back(Op.Val);
+ AddToWorkList(Op.Val);
// Replace the old value with the new one.
++NodesCombined;
- DEBUG(std::cerr << "\nReplacing "; TLO.Old.Val->dump();
- std::cerr << "\nWith: "; TLO.New.Val->dump(&DAG);
- std::cerr << '\n');
+ DOUT << "\nReplacing.2 "; DEBUG(TLO.Old.Val->dump(&DAG));
+ DOUT << "\nWith: "; DEBUG(TLO.New.Val->dump(&DAG));
+ DOUT << '\n';
std::vector<SDNode*> NowDead;
- DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, NowDead);
+ DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, &NowDead);
// Push the new node and any (possibly new) users onto the worklist.
- WorkList.push_back(TLO.New.Val);
+ AddToWorkList(TLO.New.Val);
AddUsersToWorkList(TLO.New.Val);
// Nodes can end up on the worklist more than once. Make sure we do
// something else needing this node.
if (TLO.Old.Val->use_empty()) {
removeFromWorkList(TLO.Old.Val);
+
+ // If the operands of this node are only used by the node, they will now
+ // be dead. Make sure to visit them first to delete dead nodes early.
+ for (unsigned i = 0, e = TLO.Old.Val->getNumOperands(); i != e; ++i)
+ if (TLO.Old.Val->getOperand(i).Val->hasOneUse())
+ AddToWorkList(TLO.Old.Val->getOperand(i).Val);
+
DAG.DeleteNode(TLO.Old.Val);
}
return true;
}
- /// visit - call the node-specific routine that knows how to fold each
- /// particular type of node.
- SDOperand visit(SDNode *N);
+ bool CombineToPreIndexedLoadStore(SDNode *N);
+ bool CombineToPostIndexedLoadStore(SDNode *N);
+
+
+ /// combine - call the node-specific routine that knows how to fold each
+ /// particular type of node. If that doesn't do anything, try the
+ /// target-specific DAG combines.
+ SDOperand combine(SDNode *N);
// Visitation implementation - Implement dag node combining for different
// node types. The semantics are as follows:
SDOperand visitTokenFactor(SDNode *N);
SDOperand visitADD(SDNode *N);
SDOperand visitSUB(SDNode *N);
+ SDOperand visitADDC(SDNode *N);
+ SDOperand visitADDE(SDNode *N);
SDOperand visitMUL(SDNode *N);
SDOperand visitSDIV(SDNode *N);
SDOperand visitUDIV(SDNode *N);
SDOperand visitUREM(SDNode *N);
SDOperand visitMULHU(SDNode *N);
SDOperand visitMULHS(SDNode *N);
+ SDOperand visitSMUL_LOHI(SDNode *N);
+ SDOperand visitUMUL_LOHI(SDNode *N);
+ SDOperand visitSDIVREM(SDNode *N);
+ SDOperand visitUDIVREM(SDNode *N);
SDOperand visitAND(SDNode *N);
SDOperand visitOR(SDNode *N);
SDOperand visitXOR(SDNode *N);
- SDOperand visitVBinOp(SDNode *N, ISD::NodeType IntOp, ISD::NodeType FPOp);
+ SDOperand SimplifyVBinOp(SDNode *N);
SDOperand visitSHL(SDNode *N);
SDOperand visitSRA(SDNode *N);
SDOperand visitSRL(SDNode *N);
SDOperand visitSIGN_EXTEND_INREG(SDNode *N);
SDOperand visitTRUNCATE(SDNode *N);
SDOperand visitBIT_CONVERT(SDNode *N);
- SDOperand visitVBIT_CONVERT(SDNode *N);
SDOperand visitFADD(SDNode *N);
SDOperand visitFSUB(SDNode *N);
SDOperand visitFMUL(SDNode *N);
SDOperand visitBRCOND(SDNode *N);
SDOperand visitBR_CC(SDNode *N);
SDOperand visitLOAD(SDNode *N);
- SDOperand visitXEXTLOAD(SDNode *N);
SDOperand visitSTORE(SDNode *N);
SDOperand visitINSERT_VECTOR_ELT(SDNode *N);
- SDOperand visitVINSERT_VECTOR_ELT(SDNode *N);
- SDOperand visitVBUILD_VECTOR(SDNode *N);
+ SDOperand visitEXTRACT_VECTOR_ELT(SDNode *N);
+ SDOperand visitBUILD_VECTOR(SDNode *N);
+ SDOperand visitCONCAT_VECTORS(SDNode *N);
SDOperand visitVECTOR_SHUFFLE(SDNode *N);
- SDOperand visitVVECTOR_SHUFFLE(SDNode *N);
SDOperand XformToShuffleWithZero(SDNode *N);
SDOperand ReassociateOps(unsigned Opc, SDOperand LHS, SDOperand RHS);
+ SDOperand visitShiftByConstant(SDNode *N, unsigned Amt);
+
bool SimplifySelectOps(SDNode *SELECT, SDOperand LHS, SDOperand RHS);
SDOperand SimplifyBinOpWithSameOpcodeHands(SDNode *N);
SDOperand SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2);
SDOperand SimplifySelectCC(SDOperand N0, SDOperand N1, SDOperand N2,
- SDOperand N3, ISD::CondCode CC);
+ SDOperand N3, ISD::CondCode CC,
+ bool NotExtCompare = false);
SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
ISD::CondCode Cond, bool foldBooleans = true);
- SDOperand ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *, MVT::ValueType);
+ bool SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp, unsigned HiOp);
+ SDOperand ConstantFoldBIT_CONVERTofBUILD_VECTOR(SDNode *, MVT::ValueType);
SDOperand BuildSDIV(SDNode *N);
SDOperand BuildUDIV(SDNode *N);
SDNode *MatchRotate(SDOperand LHS, SDOperand RHS);
+ SDOperand ReduceLoadWidth(SDNode *N);
- /// FindBaseOffset - Return true if we can determine base and offset
- /// information from a given pointer operand. Provides base and offset as a
- /// result.
- static bool FindBaseOffset(SDOperand Ptr,
- SDOperand &Object, int64_t &Offset);
+ SDOperand GetDemandedBits(SDOperand V, uint64_t Mask);
- /// isAlias - Return true if there is the possibility that the two addresses
+ /// GatherAllAliases - Walk up chain skipping non-aliasing memory nodes,
+ /// looking for aliasing nodes and adding them to the Aliases vector.
+ void GatherAllAliases(SDNode *N, SDOperand OriginalChain,
+ SmallVector<SDOperand, 8> &Aliases);
+
+ /// isAlias - Return true if there is any possibility that the two addresses
/// overlap.
- static bool isAlias(SDOperand Ptr1, int64_t Size1, SDOperand SrcValue1,
- SDOperand Ptr2, int64_t Size2, SDOperand SrcValue2);
-
+ bool isAlias(SDOperand Ptr1, int64_t Size1,
+ const Value *SrcValue1, int SrcValueOffset1,
+ SDOperand Ptr2, int64_t Size2,
+ const Value *SrcValue2, int SrcValueOffset2);
+
/// FindAliasInfo - Extracts the relevant alias information from the memory
- /// node.
- static void FindAliasInfo(SDNode *N,
- SDOperand &Ptr, int64_t &Size, SDOperand &SrcValue);
-
- /// hasChain - Return true if Op has a chain. Provides chain if present.
- ///
- static bool hasChain(SDOperand Op, SDOperand &Chain);
-
+ /// node. Returns true if the operand was a load.
+ bool FindAliasInfo(SDNode *N,
+ SDOperand &Ptr, int64_t &Size,
+ const Value *&SrcValue, int &SrcValueOffset);
+
/// FindBetterChain - Walk up chain skipping non-aliasing memory nodes,
- /// looking for a better chain.
+ /// looking for a better chain (aliasing node.)
SDOperand FindBetterChain(SDNode *N, SDOperand Chain);
public:
- DAGCombiner(SelectionDAG &D)
- : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {}
+ DAGCombiner(SelectionDAG &D, AliasAnalysis &A)
+ : DAG(D),
+ TLI(D.getTargetLoweringInfo()),
+ AfterLegalize(false),
+ AA(A) {}
/// Run - runs the dag combiner on all nodes in the work list
void Run(bool RunningAfterLegalize);
}
+//===----------------------------------------------------------------------===//
+// Helper Functions
+//===----------------------------------------------------------------------===//
+/// isNegatibleForFree - Return 1 if we can compute the negated form of the
+/// specified expression for the same cost as the expression itself, or 2 if we
+/// can compute the negated form more cheaply than the expression itself.
+static char isNegatibleForFree(SDOperand Op, unsigned Depth = 0) {
+ // No compile time optimizations on this type.
+ if (Op.getValueType() == MVT::ppcf128)
+ return 0;
-//===----------------------------------------------------------------------===//
+ // fneg is removable even if it has multiple uses.
+ if (Op.getOpcode() == ISD::FNEG) return 2;
+
+ // Don't allow anything with multiple uses.
+ if (!Op.hasOneUse()) return 0;
+
+ // Don't recurse exponentially.
+ if (Depth > 6) return 0;
+
+ switch (Op.getOpcode()) {
+ default: return false;
+ case ISD::ConstantFP:
+ return 1;
+ case ISD::FADD:
+ // FIXME: determine better conditions for this xform.
+ if (!UnsafeFPMath) return 0;
+
+ // -(A+B) -> -A - B
+ if (char V = isNegatibleForFree(Op.getOperand(0), Depth+1))
+ return V;
+ // -(A+B) -> -B - A
+ return isNegatibleForFree(Op.getOperand(1), Depth+1);
+ case ISD::FSUB:
+ // We can't turn -(A-B) into B-A when we honor signed zeros.
+ if (!UnsafeFPMath) return 0;
+
+ // -(A-B) -> B-A
+ return 1;
+
+ case ISD::FMUL:
+ case ISD::FDIV:
+ if (HonorSignDependentRoundingFPMath()) return 0;
+
+ // -(X*Y) -> (-X * Y) or (X*-Y)
+ if (char V = isNegatibleForFree(Op.getOperand(0), Depth+1))
+ return V;
+
+ return isNegatibleForFree(Op.getOperand(1), Depth+1);
+
+ case ISD::FP_EXTEND:
+ case ISD::FP_ROUND:
+ case ISD::FSIN:
+ return isNegatibleForFree(Op.getOperand(0), Depth+1);
+ }
+}
+
+/// GetNegatedExpression - If isNegatibleForFree returns true, this function
+/// returns the newly negated expression.
+static SDOperand GetNegatedExpression(SDOperand Op, SelectionDAG &DAG,
+ unsigned Depth = 0) {
+ // fneg is removable even if it has multiple uses.
+ if (Op.getOpcode() == ISD::FNEG) return Op.getOperand(0);
+
+ // Don't allow anything with multiple uses.
+ assert(Op.hasOneUse() && "Unknown reuse!");
+
+ assert(Depth <= 6 && "GetNegatedExpression doesn't match isNegatibleForFree");
+ switch (Op.getOpcode()) {
+ default: assert(0 && "Unknown code");
+ case ISD::ConstantFP: {
+ APFloat V = cast<ConstantFPSDNode>(Op)->getValueAPF();
+ V.changeSign();
+ return DAG.getConstantFP(V, Op.getValueType());
+ }
+ case ISD::FADD:
+ // FIXME: determine better conditions for this xform.
+ assert(UnsafeFPMath);
+
+ // -(A+B) -> -A - B
+ if (isNegatibleForFree(Op.getOperand(0), Depth+1))
+ return DAG.getNode(ISD::FSUB, Op.getValueType(),
+ GetNegatedExpression(Op.getOperand(0), DAG, Depth+1),
+ Op.getOperand(1));
+ // -(A+B) -> -B - A
+ return DAG.getNode(ISD::FSUB, Op.getValueType(),
+ GetNegatedExpression(Op.getOperand(1), DAG, Depth+1),
+ Op.getOperand(0));
+ case ISD::FSUB:
+ // We can't turn -(A-B) into B-A when we honor signed zeros.
+ assert(UnsafeFPMath);
+
+ // -(0-B) -> B
+ if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(Op.getOperand(0)))
+ if (N0CFP->getValueAPF().isZero())
+ return Op.getOperand(1);
+
+ // -(A-B) -> B-A
+ return DAG.getNode(ISD::FSUB, Op.getValueType(), Op.getOperand(1),
+ Op.getOperand(0));
+
+ case ISD::FMUL:
+ case ISD::FDIV:
+ assert(!HonorSignDependentRoundingFPMath());
+
+ // -(X*Y) -> -X * Y
+ if (isNegatibleForFree(Op.getOperand(0), Depth+1))
+ return DAG.getNode(Op.getOpcode(), Op.getValueType(),
+ GetNegatedExpression(Op.getOperand(0), DAG, Depth+1),
+ Op.getOperand(1));
+
+ // -(X*Y) -> X * -Y
+ return DAG.getNode(Op.getOpcode(), Op.getValueType(),
+ Op.getOperand(0),
+ GetNegatedExpression(Op.getOperand(1), DAG, Depth+1));
+
+ case ISD::FP_EXTEND:
+ case ISD::FP_ROUND:
+ case ISD::FSIN:
+ return DAG.getNode(Op.getOpcode(), Op.getValueType(),
+ GetNegatedExpression(Op.getOperand(0), DAG, Depth+1));
+ }
+}
// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc
return SDOperand();
}
+//===----------------------------------------------------------------------===//
+// Main DAG Combiner implementation
+//===----------------------------------------------------------------------===//
+
void DAGCombiner::Run(bool RunningAfterLegalize) {
// set the instance variable, so that the various visit routines may use it.
AfterLegalize = RunningAfterLegalize;
// changes of the root.
HandleSDNode Dummy(DAG.getRoot());
-
- /// DagCombineInfo - Expose the DAG combiner to the target combiner impls.
- TargetLowering::DAGCombinerInfo
- DagCombineInfo(DAG, !RunningAfterLegalize, this);
+ // The root of the dag may dangle to deleted nodes until the dag combiner is
+ // done. Set it to null to avoid confusion.
+ DAG.setRoot(SDOperand());
// while the worklist isn't empty, inspect the node on the end of it and
// try and combine it.
// reduced number of uses, allowing other xforms.
if (N->use_empty() && N != &Dummy) {
for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
- WorkList.push_back(N->getOperand(i).Val);
+ AddToWorkList(N->getOperand(i).Val);
- removeFromWorkList(N);
DAG.DeleteNode(N);
continue;
}
- SDOperand RV = visit(N);
-
- // If nothing happened, try a target-specific DAG combine.
- if (RV.Val == 0) {
- assert(N->getOpcode() != ISD::DELETED_NODE &&
- "Node was deleted but visit returned NULL!");
- if (N->getOpcode() >= ISD::BUILTIN_OP_END ||
- TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode()))
- RV = TLI.PerformDAGCombine(N, DagCombineInfo);
- }
+ SDOperand RV = combine(N);
if (RV.Val) {
++NodesCombined;
RV.Val->getOpcode() != ISD::DELETED_NODE &&
"Node was deleted but visit returned new node!");
- DEBUG(std::cerr << "\nReplacing "; N->dump();
- std::cerr << "\nWith: "; RV.Val->dump(&DAG);
- std::cerr << '\n');
+ DOUT << "\nReplacing.3 "; DEBUG(N->dump(&DAG));
+ DOUT << "\nWith: "; DEBUG(RV.Val->dump(&DAG));
+ DOUT << '\n';
std::vector<SDNode*> NowDead;
if (N->getNumValues() == RV.Val->getNumValues())
DAG.ReplaceAllUsesWith(N, RV.Val, &NowDead);
}
// Push the new node and any users onto the worklist
- WorkList.push_back(RV.Val);
+ AddToWorkList(RV.Val);
AddUsersToWorkList(RV.Val);
- // Nodes can end up on the worklist more than once. Make sure we do
- // not process a node that has been replaced.
+ // Nodes can be reintroduced into the worklist. Make sure we do not
+ // process a node that has been replaced.
removeFromWorkList(N);
for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
removeFromWorkList(NowDead[i]);
case ISD::TokenFactor: return visitTokenFactor(N);
case ISD::ADD: return visitADD(N);
case ISD::SUB: return visitSUB(N);
+ case ISD::ADDC: return visitADDC(N);
+ case ISD::ADDE: return visitADDE(N);
case ISD::MUL: return visitMUL(N);
case ISD::SDIV: return visitSDIV(N);
case ISD::UDIV: return visitUDIV(N);
case ISD::UREM: return visitUREM(N);
case ISD::MULHU: return visitMULHU(N);
case ISD::MULHS: return visitMULHS(N);
+ case ISD::SMUL_LOHI: return visitSMUL_LOHI(N);
+ case ISD::UMUL_LOHI: return visitUMUL_LOHI(N);
+ case ISD::SDIVREM: return visitSDIVREM(N);
+ case ISD::UDIVREM: return visitUDIVREM(N);
case ISD::AND: return visitAND(N);
case ISD::OR: return visitOR(N);
case ISD::XOR: return visitXOR(N);
case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N);
case ISD::TRUNCATE: return visitTRUNCATE(N);
case ISD::BIT_CONVERT: return visitBIT_CONVERT(N);
- case ISD::VBIT_CONVERT: return visitVBIT_CONVERT(N);
case ISD::FADD: return visitFADD(N);
case ISD::FSUB: return visitFSUB(N);
case ISD::FMUL: return visitFMUL(N);
case ISD::BRCOND: return visitBRCOND(N);
case ISD::BR_CC: return visitBR_CC(N);
case ISD::LOAD: return visitLOAD(N);
- case ISD::EXTLOAD:
- case ISD::SEXTLOAD:
- case ISD::ZEXTLOAD: return visitXEXTLOAD(N);
case ISD::STORE: return visitSTORE(N);
case ISD::INSERT_VECTOR_ELT: return visitINSERT_VECTOR_ELT(N);
- case ISD::VINSERT_VECTOR_ELT: return visitVINSERT_VECTOR_ELT(N);
- case ISD::VBUILD_VECTOR: return visitVBUILD_VECTOR(N);
+ case ISD::EXTRACT_VECTOR_ELT: return visitEXTRACT_VECTOR_ELT(N);
+ case ISD::BUILD_VECTOR: return visitBUILD_VECTOR(N);
+ case ISD::CONCAT_VECTORS: return visitCONCAT_VECTORS(N);
case ISD::VECTOR_SHUFFLE: return visitVECTOR_SHUFFLE(N);
- case ISD::VVECTOR_SHUFFLE: return visitVVECTOR_SHUFFLE(N);
- case ISD::VADD: return visitVBinOp(N, ISD::ADD , ISD::FADD);
- case ISD::VSUB: return visitVBinOp(N, ISD::SUB , ISD::FSUB);
- case ISD::VMUL: return visitVBinOp(N, ISD::MUL , ISD::FMUL);
- case ISD::VSDIV: return visitVBinOp(N, ISD::SDIV, ISD::FDIV);
- case ISD::VUDIV: return visitVBinOp(N, ISD::UDIV, ISD::UDIV);
- case ISD::VAND: return visitVBinOp(N, ISD::AND , ISD::AND);
- case ISD::VOR: return visitVBinOp(N, ISD::OR , ISD::OR);
- case ISD::VXOR: return visitVBinOp(N, ISD::XOR , ISD::XOR);
}
return SDOperand();
}
+SDOperand DAGCombiner::combine(SDNode *N) {
+
+ SDOperand RV = visit(N);
+
+ // If nothing happened, try a target-specific DAG combine.
+ if (RV.Val == 0) {
+ assert(N->getOpcode() != ISD::DELETED_NODE &&
+ "Node was deleted but visit returned NULL!");
+
+ if (N->getOpcode() >= ISD::BUILTIN_OP_END ||
+ TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode())) {
+
+ // Expose the DAG combiner to the target combiner impls.
+ TargetLowering::DAGCombinerInfo
+ DagCombineInfo(DAG, !AfterLegalize, false, this);
+
+ RV = TLI.PerformDAGCombine(N, DagCombineInfo);
+ }
+ }
+
+ return RV;
+}
+
+/// getInputChainForNode - Given a node, return its input chain if it has one,
+/// otherwise return a null sd operand.
+static SDOperand getInputChainForNode(SDNode *N) {
+ if (unsigned NumOps = N->getNumOperands()) {
+ if (N->getOperand(0).getValueType() == MVT::Other)
+ return N->getOperand(0);
+ else if (N->getOperand(NumOps-1).getValueType() == MVT::Other)
+ return N->getOperand(NumOps-1);
+ for (unsigned i = 1; i < NumOps-1; ++i)
+ if (N->getOperand(i).getValueType() == MVT::Other)
+ return N->getOperand(i);
+ }
+ return SDOperand(0, 0);
+}
+
SDOperand DAGCombiner::visitTokenFactor(SDNode *N) {
- // If the token factor has two operands and one is the entry token, replace
- // the token factor with the other operand.
+ // If N has two operands, where one has an input chain equal to the other,
+ // the 'other' chain is redundant.
if (N->getNumOperands() == 2) {
- if (N->getOperand(0).getOpcode() == ISD::EntryToken ||
- N->getOperand(0) == N->getOperand(1))
- return N->getOperand(1);
- if (N->getOperand(1).getOpcode() == ISD::EntryToken)
+ if (getInputChainForNode(N->getOperand(0).Val) == N->getOperand(1))
return N->getOperand(0);
+ if (getInputChainForNode(N->getOperand(1).Val) == N->getOperand(0))
+ return N->getOperand(1);
}
- SmallVector<SDNode *, 8> TFs; // Set of token factor nodes.
- SmallVector<SDOperand, 8> Ops; // Ops for replacing token factor.
-
- // Add this ndoe to the token factor set.
+ SmallVector<SDNode *, 8> TFs; // List of token factors to visit.
+ SmallVector<SDOperand, 8> Ops; // Ops for replacing token factor.
+ SmallPtrSet<SDNode*, 16> SeenOps;
+ bool Changed = false; // If we should replace this token factor.
+
+ // Start out with this token factor.
TFs.push_back(N);
-
- // Separate token factors from other operands.
- for (unsigned i = 0, ie = N->getNumOperands(); i != ie; ++i) {
- SDOperand Op = N->getOperand(i);
- if (Op.getOpcode() == ISD::TokenFactor)
- TFs.push_back(Op.Val);
- else if (Op.getOpcode() != ISD::EntryToken)
- Ops.push_back(Op);
- }
- // If there are token factor operands.
- if (TFs.size() > 1) {
- bool Changed = false; // If we should replace this token factor.
+ // Iterate through token factors. The TFs grows when new token factors are
+ // encountered.
+ for (unsigned i = 0; i < TFs.size(); ++i) {
+ SDNode *TF = TFs[i];
- // For each token factor.
- for (unsigned j = 1, je = TFs.size(); j != je; ++j) {
- SDNode *TF = TFs[j];
- bool CanMerge = true; // Can we merge this token factor.
-
- if (CombinerAA) {
- if (!TF->hasOneUse()) {
- // Check to see if all users point to members of the token factor set.
- for (SDNode::use_iterator UI = TF->use_begin(), UE = TF->use_end();
- CanMerge && UI != UE; ++UI) {
- SDNode *User = *UI;
- CanMerge = User->getOpcode() == ISD::TokenFactor &&
- std::find(TFs.begin(), TFs.end(), User) != TFs.end();
- }
- }
- } else {
- CanMerge = TF->hasOneUse();
- }
+ // Check each of the operands.
+ for (unsigned i = 0, ie = TF->getNumOperands(); i != ie; ++i) {
+ SDOperand Op = TF->getOperand(i);
- // If it's valid to merge.
- if (CanMerge) {
- // Remove dead token factor node.
- AddToWorkList(TF);
+ switch (Op.getOpcode()) {
+ case ISD::EntryToken:
+ // Entry tokens don't need to be added to the list. They are
+ // rededundant.
+ Changed = true;
+ break;
- // Make sure we don't duplicate operands.
- unsigned m = Ops.size(); // Number of prior operands.
- for (unsigned l = 0, le = TF->getNumOperands(); l != le; ++l) {
- SDOperand Op = TF->getOperand(l);
- if (std::find(Ops.begin(), Ops.end(), Op) == Ops.end())
- Ops.push_back(Op);
+ case ISD::TokenFactor:
+ if ((CombinerAA || Op.hasOneUse()) &&
+ std::find(TFs.begin(), TFs.end(), Op.Val) == TFs.end()) {
+ // Queue up for processing.
+ TFs.push_back(Op.Val);
+ // Clean up in case the token factor is removed.
+ AddToWorkList(Op.Val);
+ Changed = true;
+ break;
}
- Changed = true;
- } else {
- // Can't merge this token factor.
- Ops.push_back(SDOperand(TF, 0));
+ // Fall thru
+
+ default:
+ // Only add if it isn't already in the list.
+ if (SeenOps.insert(Op.Val))
+ Ops.push_back(Op);
+ else
+ Changed = true;
+ break;
}
}
-
- // If we've change things around then replace token factor.
- if (Changed) {
- return DAG.getNode(ISD::TokenFactor, MVT::Other, &Ops[0], Ops.size());
+ }
+
+ SDOperand Result;
+
+ // If we've change things around then replace token factor.
+ if (Changed) {
+ if (Ops.size() == 0) {
+ // The entry token is the only possible outcome.
+ Result = DAG.getEntryNode();
+ } else {
+ // New and improved token factor.
+ Result = DAG.getNode(ISD::TokenFactor, MVT::Other, &Ops[0], Ops.size());
}
+
+ // Don't add users to work list.
+ return CombineTo(N, Result, false);
}
+ return Result;
+}
+
+static
+SDOperand combineShlAddConstant(SDOperand N0, SDOperand N1, SelectionDAG &DAG) {
+ MVT::ValueType VT = N0.getValueType();
+ SDOperand N00 = N0.getOperand(0);
+ SDOperand N01 = N0.getOperand(1);
+ ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N01);
+ if (N01C && N00.getOpcode() == ISD::ADD && N00.Val->hasOneUse() &&
+ isa<ConstantSDNode>(N00.getOperand(1))) {
+ N0 = DAG.getNode(ISD::ADD, VT,
+ DAG.getNode(ISD::SHL, VT, N00.getOperand(0), N01),
+ DAG.getNode(ISD::SHL, VT, N00.getOperand(1), N01));
+ return DAG.getNode(ISD::ADD, VT, N0, N1);
+ }
+ return SDOperand();
+}
+
+static
+SDOperand combineSelectAndUse(SDNode *N, SDOperand Slct, SDOperand OtherOp,
+ SelectionDAG &DAG) {
+ MVT::ValueType VT = N->getValueType(0);
+ unsigned Opc = N->getOpcode();
+ bool isSlctCC = Slct.getOpcode() == ISD::SELECT_CC;
+ SDOperand LHS = isSlctCC ? Slct.getOperand(2) : Slct.getOperand(1);
+ SDOperand RHS = isSlctCC ? Slct.getOperand(3) : Slct.getOperand(2);
+ ISD::CondCode CC = ISD::SETCC_INVALID;
+ if (isSlctCC)
+ CC = cast<CondCodeSDNode>(Slct.getOperand(4))->get();
+ else {
+ SDOperand CCOp = Slct.getOperand(0);
+ if (CCOp.getOpcode() == ISD::SETCC)
+ CC = cast<CondCodeSDNode>(CCOp.getOperand(2))->get();
+ }
+
+ bool DoXform = false;
+ bool InvCC = false;
+ assert ((Opc == ISD::ADD || (Opc == ISD::SUB && Slct == N->getOperand(1))) &&
+ "Bad input!");
+ if (LHS.getOpcode() == ISD::Constant &&
+ cast<ConstantSDNode>(LHS)->isNullValue())
+ DoXform = true;
+ else if (CC != ISD::SETCC_INVALID &&
+ RHS.getOpcode() == ISD::Constant &&
+ cast<ConstantSDNode>(RHS)->isNullValue()) {
+ std::swap(LHS, RHS);
+ bool isInt = MVT::isInteger(isSlctCC ? Slct.getOperand(0).getValueType()
+ : Slct.getOperand(0).getOperand(0).getValueType());
+ CC = ISD::getSetCCInverse(CC, isInt);
+ DoXform = true;
+ InvCC = true;
+ }
+
+ if (DoXform) {
+ SDOperand Result = DAG.getNode(Opc, VT, OtherOp, RHS);
+ if (isSlctCC)
+ return DAG.getSelectCC(OtherOp, Result,
+ Slct.getOperand(0), Slct.getOperand(1), CC);
+ SDOperand CCOp = Slct.getOperand(0);
+ if (InvCC)
+ CCOp = DAG.getSetCC(CCOp.getValueType(), CCOp.getOperand(0),
+ CCOp.getOperand(1), CC);
+ return DAG.getNode(ISD::SELECT, VT, CCOp, OtherOp, Result);
+ }
return SDOperand();
}
ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
MVT::ValueType VT = N0.getValueType();
+
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+ // fold (add x, undef) -> undef
+ if (N0.getOpcode() == ISD::UNDEF)
+ return N0;
+ if (N1.getOpcode() == ISD::UNDEF)
+ return N1;
// fold (add c1, c2) -> c1+c2
if (N0C && N1C)
return DAG.getNode(ISD::ADD, VT, N0, N1);
uint64_t LHSZero, LHSOne;
uint64_t RHSZero, RHSOne;
uint64_t Mask = MVT::getIntVTBitMask(VT);
- TLI.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne);
+ DAG.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne);
if (LHSZero) {
- TLI.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne);
+ DAG.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne);
// If all possibly-set bits on the LHS are clear on the RHS, return an OR.
// If all possibly-set bits on the RHS are clear on the LHS, return an OR.
return DAG.getNode(ISD::OR, VT, N0, N1);
}
}
+
+ // fold (add (shl (add x, c1), c2), ) -> (add (add (shl x, c2), c1<<c2), )
+ if (N0.getOpcode() == ISD::SHL && N0.Val->hasOneUse()) {
+ SDOperand Result = combineShlAddConstant(N0, N1, DAG);
+ if (Result.Val) return Result;
+ }
+ if (N1.getOpcode() == ISD::SHL && N1.Val->hasOneUse()) {
+ SDOperand Result = combineShlAddConstant(N1, N0, DAG);
+ if (Result.Val) return Result;
+ }
+
+ // fold (add (select cc, 0, c), x) -> (select cc, x, (add, x, c))
+ if (N0.getOpcode() == ISD::SELECT && N0.Val->hasOneUse()) {
+ SDOperand Result = combineSelectAndUse(N, N0, N1, DAG);
+ if (Result.Val) return Result;
+ }
+ if (N1.getOpcode() == ISD::SELECT && N1.Val->hasOneUse()) {
+ SDOperand Result = combineSelectAndUse(N, N1, N0, DAG);
+ if (Result.Val) return Result;
+ }
+
+ return SDOperand();
+}
+
+SDOperand DAGCombiner::visitADDC(SDNode *N) {
+ SDOperand N0 = N->getOperand(0);
+ SDOperand N1 = N->getOperand(1);
+ ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
+ ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
+ MVT::ValueType VT = N0.getValueType();
+
+ // If the flag result is dead, turn this into an ADD.
+ if (N->hasNUsesOfValue(0, 1))
+ return CombineTo(N, DAG.getNode(ISD::ADD, VT, N1, N0),
+ DAG.getNode(ISD::CARRY_FALSE, MVT::Flag));
+
+ // canonicalize constant to RHS.
+ if (N0C && !N1C) {
+ SDOperand Ops[] = { N1, N0 };
+ return DAG.getNode(ISD::ADDC, N->getVTList(), Ops, 2);
+ }
+
+ // fold (addc x, 0) -> x + no carry out
+ if (N1C && N1C->isNullValue())
+ return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE, MVT::Flag));
+
+ // fold (addc a, b) -> (or a, b), CARRY_FALSE iff a and b share no bits.
+ uint64_t LHSZero, LHSOne;
+ uint64_t RHSZero, RHSOne;
+ uint64_t Mask = MVT::getIntVTBitMask(VT);
+ DAG.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne);
+ if (LHSZero) {
+ DAG.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne);
+
+ // If all possibly-set bits on the LHS are clear on the RHS, return an OR.
+ // If all possibly-set bits on the RHS are clear on the LHS, return an OR.
+ if ((RHSZero & (~LHSZero & Mask)) == (~LHSZero & Mask) ||
+ (LHSZero & (~RHSZero & Mask)) == (~RHSZero & Mask))
+ return CombineTo(N, DAG.getNode(ISD::OR, VT, N0, N1),
+ DAG.getNode(ISD::CARRY_FALSE, MVT::Flag));
+ }
+
+ return SDOperand();
+}
+
+SDOperand DAGCombiner::visitADDE(SDNode *N) {
+ SDOperand N0 = N->getOperand(0);
+ SDOperand N1 = N->getOperand(1);
+ SDOperand CarryIn = N->getOperand(2);
+ ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
+ ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
+ //MVT::ValueType VT = N0.getValueType();
+
+ // canonicalize constant to RHS
+ if (N0C && !N1C) {
+ SDOperand Ops[] = { N1, N0, CarryIn };
+ return DAG.getNode(ISD::ADDE, N->getVTList(), Ops, 3);
+ }
+
+ // fold (adde x, y, false) -> (addc x, y)
+ if (CarryIn.getOpcode() == ISD::CARRY_FALSE) {
+ SDOperand Ops[] = { N1, N0 };
+ return DAG.getNode(ISD::ADDC, N->getVTList(), Ops, 2);
+ }
return SDOperand();
}
+
+
SDOperand DAGCombiner::visitSUB(SDNode *N) {
SDOperand N0 = N->getOperand(0);
SDOperand N1 = N->getOperand(1);
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
MVT::ValueType VT = N0.getValueType();
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
// fold (sub x, x) -> 0
if (N0 == N1)
return DAG.getConstant(0, N->getValueType(0));
// fold (A+B)-B -> A
if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1)
return N0.getOperand(0);
+ // fold (sub x, (select cc, 0, c)) -> (select cc, x, (sub, x, c))
+ if (N1.getOpcode() == ISD::SELECT && N1.Val->hasOneUse()) {
+ SDOperand Result = combineSelectAndUse(N, N1, N0, DAG);
+ if (Result.Val) return Result;
+ }
+ // If either operand of a sub is undef, the result is undef
+ if (N0.getOpcode() == ISD::UNDEF)
+ return N0;
+ if (N1.getOpcode() == ISD::UNDEF)
+ return N1;
+
return SDOperand();
}
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
MVT::ValueType VT = N0.getValueType();
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
+ // fold (mul x, undef) -> 0
+ if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
+ return DAG.getConstant(0, VT);
// fold (mul c1, c2) -> c1*c2
if (N0C && N1C)
return DAG.getNode(ISD::MUL, VT, N0, N1);
SDOperand RMUL = ReassociateOps(ISD::MUL, N0, N1);
if (RMUL.Val != 0)
return RMUL;
+
return SDOperand();
}
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
MVT::ValueType VT = N->getValueType(0);
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
// fold (sdiv c1, c2) -> c1/c2
if (N0C && N1C && !N1C->isNullValue())
return DAG.getNode(ISD::SDIV, VT, N0, N1);
// If we know the sign bits of both operands are zero, strength reduce to a
// udiv instead. Handles (X&15) /s 4 -> X&15 >> 2
uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1);
- if (TLI.MaskedValueIsZero(N1, SignBit) &&
- TLI.MaskedValueIsZero(N0, SignBit))
+ if (DAG.MaskedValueIsZero(N1, SignBit) &&
+ DAG.MaskedValueIsZero(N0, SignBit))
return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1);
// fold (sdiv X, pow2) -> simple ops after legalize
if (N1C && N1C->getValue() && !TLI.isIntDivCheap() &&
SDOperand Op = BuildSDIV(N);
if (Op.Val) return Op;
}
+
+ // undef / X -> 0
+ if (N0.getOpcode() == ISD::UNDEF)
+ return DAG.getConstant(0, VT);
+ // X / undef -> undef
+ if (N1.getOpcode() == ISD::UNDEF)
+ return N1;
+
return SDOperand();
}
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
MVT::ValueType VT = N->getValueType(0);
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
// fold (udiv c1, c2) -> c1/c2
if (N0C && N1C && !N1C->isNullValue())
return DAG.getNode(ISD::UDIV, VT, N0, N1);
SDOperand Op = BuildUDIV(N);
if (Op.Val) return Op;
}
+
+ // undef / X -> 0
+ if (N0.getOpcode() == ISD::UNDEF)
+ return DAG.getConstant(0, VT);
+ // X / undef -> undef
+ if (N1.getOpcode() == ISD::UNDEF)
+ return N1;
+
return SDOperand();
}
// If we know the sign bits of both operands are zero, strength reduce to a
// urem instead. Handles (X & 0x0FFFFFFF) %s 16 -> X&15
uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1);
- if (TLI.MaskedValueIsZero(N1, SignBit) &&
- TLI.MaskedValueIsZero(N0, SignBit))
+ if (DAG.MaskedValueIsZero(N1, SignBit) &&
+ DAG.MaskedValueIsZero(N0, SignBit))
return DAG.getNode(ISD::UREM, VT, N0, N1);
+
+ // If X/C can be simplified by the division-by-constant logic, lower
+ // X%C to the equivalent of X-X/C*C.
+ if (N1C && !N1C->isNullValue()) {
+ SDOperand Div = DAG.getNode(ISD::SDIV, VT, N0, N1);
+ SDOperand OptimizedDiv = combine(Div.Val);
+ if (OptimizedDiv.Val && OptimizedDiv.Val != Div.Val) {
+ SDOperand Mul = DAG.getNode(ISD::MUL, VT, OptimizedDiv, N1);
+ SDOperand Sub = DAG.getNode(ISD::SUB, VT, N0, Mul);
+ AddToWorkList(Mul.Val);
+ return Sub;
+ }
+ }
+
+ // undef % X -> 0
+ if (N0.getOpcode() == ISD::UNDEF)
+ return DAG.getConstant(0, VT);
+ // X % undef -> undef
+ if (N1.getOpcode() == ISD::UNDEF)
+ return N1;
+
return SDOperand();
}
}
}
}
+
+ // If X/C can be simplified by the division-by-constant logic, lower
+ // X%C to the equivalent of X-X/C*C.
+ if (N1C && !N1C->isNullValue()) {
+ SDOperand Div = DAG.getNode(ISD::UDIV, VT, N0, N1);
+ SDOperand OptimizedDiv = combine(Div.Val);
+ if (OptimizedDiv.Val && OptimizedDiv.Val != Div.Val) {
+ SDOperand Mul = DAG.getNode(ISD::MUL, VT, OptimizedDiv, N1);
+ SDOperand Sub = DAG.getNode(ISD::SUB, VT, N0, Mul);
+ AddToWorkList(Mul.Val);
+ return Sub;
+ }
+ }
+
+ // undef % X -> 0
+ if (N0.getOpcode() == ISD::UNDEF)
+ return DAG.getConstant(0, VT);
+ // X % undef -> undef
+ if (N1.getOpcode() == ISD::UNDEF)
+ return N1;
+
return SDOperand();
}
SDOperand N0 = N->getOperand(0);
SDOperand N1 = N->getOperand(1);
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
+ MVT::ValueType VT = N->getValueType(0);
// fold (mulhs x, 0) -> 0
if (N1C && N1C->isNullValue())
return DAG.getNode(ISD::SRA, N0.getValueType(), N0,
DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1,
TLI.getShiftAmountTy()));
+ // fold (mulhs x, undef) -> 0
+ if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
+ return DAG.getConstant(0, VT);
+
return SDOperand();
}
SDOperand N0 = N->getOperand(0);
SDOperand N1 = N->getOperand(1);
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
+ MVT::ValueType VT = N->getValueType(0);
// fold (mulhu x, 0) -> 0
if (N1C && N1C->isNullValue())
// fold (mulhu x, 1) -> 0
if (N1C && N1C->getValue() == 1)
return DAG.getConstant(0, N0.getValueType());
+ // fold (mulhu x, undef) -> 0
+ if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
+ return DAG.getConstant(0, VT);
+
+ return SDOperand();
+}
+
+/// SimplifyNodeWithTwoResults - Perform optimizations common to nodes that
+/// compute two values. LoOp and HiOp give the opcodes for the two computations
+/// that are being performed. Return true if a simplification was made.
+///
+bool DAGCombiner::SimplifyNodeWithTwoResults(SDNode *N,
+ unsigned LoOp, unsigned HiOp) {
+ // If the high half is not needed, just compute the low half.
+ bool HiExists = N->hasAnyUseOfValue(1);
+ if (!HiExists &&
+ (!AfterLegalize ||
+ TLI.isOperationLegal(LoOp, N->getValueType(0)))) {
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0),
+ DAG.getNode(LoOp, N->getValueType(0),
+ N->op_begin(),
+ N->getNumOperands()));
+ return true;
+ }
+
+ // If the low half is not needed, just compute the high half.
+ bool LoExists = N->hasAnyUseOfValue(0);
+ if (!LoExists &&
+ (!AfterLegalize ||
+ TLI.isOperationLegal(HiOp, N->getValueType(1)))) {
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1),
+ DAG.getNode(HiOp, N->getValueType(1),
+ N->op_begin(),
+ N->getNumOperands()));
+ return true;
+ }
+
+ // If both halves are used, return as it is.
+ if (LoExists && HiExists)
+ return false;
+
+ // If the two computed results can be simplified separately, separate them.
+ bool RetVal = false;
+ if (LoExists) {
+ SDOperand Lo = DAG.getNode(LoOp, N->getValueType(0),
+ N->op_begin(), N->getNumOperands());
+ SDOperand LoOpt = combine(Lo.Val);
+ if (LoOpt.Val && LoOpt != Lo &&
+ TLI.isOperationLegal(LoOpt.getOpcode(), LoOpt.getValueType())) {
+ RetVal = true;
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), LoOpt);
+ } else
+ DAG.DeleteNode(Lo.Val);
+ }
+
+ if (HiExists) {
+ SDOperand Hi = DAG.getNode(HiOp, N->getValueType(1),
+ N->op_begin(), N->getNumOperands());
+ SDOperand HiOpt = combine(Hi.Val);
+ if (HiOpt.Val && HiOpt != Hi &&
+ TLI.isOperationLegal(HiOpt.getOpcode(), HiOpt.getValueType())) {
+ RetVal = true;
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), HiOpt);
+ } else
+ DAG.DeleteNode(Hi.Val);
+ }
+
+ return RetVal;
+}
+
+SDOperand DAGCombiner::visitSMUL_LOHI(SDNode *N) {
+
+ if (SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHS))
+ return SDOperand();
+
+ return SDOperand();
+}
+
+SDOperand DAGCombiner::visitUMUL_LOHI(SDNode *N) {
+
+ if (SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHU))
+ return SDOperand();
+
+ return SDOperand();
+}
+
+SDOperand DAGCombiner::visitSDIVREM(SDNode *N) {
+
+ if (SimplifyNodeWithTwoResults(N, ISD::SDIV, ISD::SREM))
+ return SDOperand();
+
+ return SDOperand();
+}
+
+SDOperand DAGCombiner::visitUDIVREM(SDNode *N) {
+
+ if (SimplifyNodeWithTwoResults(N, ISD::UDIV, ISD::UREM))
+ return SDOperand();
+
return SDOperand();
}
ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
MVT::ValueType VT = N1.getValueType();
- unsigned OpSizeInBits = MVT::getSizeInBits(VT);
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
+ // fold (and x, undef) -> 0
+ if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
+ return DAG.getConstant(0, VT);
// fold (and c1, c2) -> c1&c2
if (N0C && N1C)
return DAG.getNode(ISD::AND, VT, N0, N1);
if (N1C && N1C->isAllOnesValue())
return N0;
// if (and x, c) is known to be zero, return 0
- if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
+ if (N1C && DAG.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
return DAG.getConstant(0, VT);
// reassociate and
SDOperand RAND = ReassociateOps(ISD::AND, N0, N1);
// fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits.
if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) {
unsigned InMask = MVT::getIntVTBitMask(N0.getOperand(0).getValueType());
- if (TLI.MaskedValueIsZero(N0.getOperand(0),
+ if (DAG.MaskedValueIsZero(N0.getOperand(0),
~N1C->getValue() & InMask)) {
SDOperand Zext = DAG.getNode(ISD::ZERO_EXTEND, N0.getValueType(),
N0.getOperand(0));
SimplifyDemandedBits(SDOperand(N, 0)))
return SDOperand(N, 0);
// fold (zext_inreg (extload x)) -> (zextload x)
- if (N0.getOpcode() == ISD::EXTLOAD) {
- MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT();
+ if (ISD::isEXTLoad(N0.Val) && ISD::isUNINDEXEDLoad(N0.Val)) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ MVT::ValueType EVT = LN0->getLoadedVT();
// If we zero all the possible extended bits, then we can turn this into
// a zextload if we are running before legalize or the operation is legal.
- if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) &&
- (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) {
- SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- EVT);
+ if (DAG.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) &&
+ (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) {
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(),
+ LN0->getAlignment());
AddToWorkList(N);
CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
return SDOperand(N, 0); // Return N so it doesn't get rechecked!
}
}
// fold (zext_inreg (sextload x)) -> (zextload x) iff load has one use
- if (N0.getOpcode() == ISD::SEXTLOAD && N0.hasOneUse()) {
- MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT();
+ if (ISD::isSEXTLoad(N0.Val) && ISD::isUNINDEXEDLoad(N0.Val) &&
+ N0.hasOneUse()) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ MVT::ValueType EVT = LN0->getLoadedVT();
// If we zero all the possible extended bits, then we can turn this into
// a zextload if we are running before legalize or the operation is legal.
- if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) &&
- (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) {
- SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- EVT);
+ if (DAG.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) &&
+ (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) {
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(),
+ LN0->getAlignment());
AddToWorkList(N);
CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
return SDOperand(N, 0); // Return N so it doesn't get rechecked!
// fold (and (load x), 255) -> (zextload x, i8)
// fold (and (extload x, i16), 255) -> (zextload x, i8)
- if (N1C &&
- (N0.getOpcode() == ISD::LOAD || N0.getOpcode() == ISD::EXTLOAD ||
- N0.getOpcode() == ISD::ZEXTLOAD) &&
- N0.hasOneUse()) {
- MVT::ValueType EVT, LoadedVT;
- if (N1C->getValue() == 255)
- EVT = MVT::i8;
- else if (N1C->getValue() == 65535)
- EVT = MVT::i16;
- else if (N1C->getValue() == ~0U)
- EVT = MVT::i32;
- else
- EVT = MVT::Other;
+ if (N1C && N0.getOpcode() == ISD::LOAD) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ if (LN0->getExtensionType() != ISD::SEXTLOAD &&
+ LN0->getAddressingMode() == ISD::UNINDEXED &&
+ N0.hasOneUse()) {
+ MVT::ValueType EVT, LoadedVT;
+ if (N1C->getValue() == 255)
+ EVT = MVT::i8;
+ else if (N1C->getValue() == 65535)
+ EVT = MVT::i16;
+ else if (N1C->getValue() == ~0U)
+ EVT = MVT::i32;
+ else
+ EVT = MVT::Other;
- LoadedVT = N0.getOpcode() == ISD::LOAD ? VT :
- cast<VTSDNode>(N0.getOperand(3))->getVT();
- if (EVT != MVT::Other && LoadedVT > EVT &&
- (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) {
- MVT::ValueType PtrType = N0.getOperand(1).getValueType();
- // For big endian targets, we need to add an offset to the pointer to load
- // the correct bytes. For little endian systems, we merely need to read
- // fewer bytes from the same pointer.
- unsigned PtrOff =
- (MVT::getSizeInBits(LoadedVT) - MVT::getSizeInBits(EVT)) / 8;
- SDOperand NewPtr = N0.getOperand(1);
- if (!TLI.isLittleEndian())
- NewPtr = DAG.getNode(ISD::ADD, PtrType, NewPtr,
- DAG.getConstant(PtrOff, PtrType));
- AddToWorkList(NewPtr.Val);
- SDOperand Load =
- DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), NewPtr,
- N0.getOperand(2), EVT);
- AddToWorkList(N);
- CombineTo(N0.Val, Load, Load.getValue(1));
- return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ LoadedVT = LN0->getLoadedVT();
+ if (EVT != MVT::Other && LoadedVT > EVT &&
+ (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) {
+ MVT::ValueType PtrType = N0.getOperand(1).getValueType();
+ // For big endian targets, we need to add an offset to the pointer to
+ // load the correct bytes. For little endian systems, we merely need to
+ // read fewer bytes from the same pointer.
+ unsigned LVTStoreBytes = MVT::getStoreSizeInBits(LoadedVT)/8;
+ unsigned EVTStoreBytes = MVT::getStoreSizeInBits(EVT)/8;
+ unsigned PtrOff = LVTStoreBytes - EVTStoreBytes;
+ unsigned Alignment = LN0->getAlignment();
+ SDOperand NewPtr = LN0->getBasePtr();
+ if (!TLI.isLittleEndian()) {
+ NewPtr = DAG.getNode(ISD::ADD, PtrType, NewPtr,
+ DAG.getConstant(PtrOff, PtrType));
+ Alignment = MinAlign(Alignment, PtrOff);
+ }
+ AddToWorkList(NewPtr.Val);
+ SDOperand Load =
+ DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), NewPtr,
+ LN0->getSrcValue(), LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(), Alignment);
+ AddToWorkList(N);
+ CombineTo(N0.Val, Load, Load.getValue(1));
+ return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ }
}
}
MVT::ValueType VT = N1.getValueType();
unsigned OpSizeInBits = MVT::getSizeInBits(VT);
- // fold (or c1, c2) -> c1|c2
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
+ // fold (or x, undef) -> -1
+ if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
+ return DAG.getConstant(~0ULL, VT);
+ // fold (or c1, c2) -> c1|c2
if (N0C && N1C)
return DAG.getNode(ISD::OR, VT, N0, N1);
// canonicalize constant to RHS
return N1;
// fold (or x, c) -> c iff (x & ~c) == 0
if (N1C &&
- TLI.MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits))))
+ DAG.MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits))))
return N1;
// reassociate or
SDOperand ROR = ReassociateOps(ISD::OR, N0, N1);
uint64_t LHSMask = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
uint64_t RHSMask = cast<ConstantSDNode>(N1.getOperand(1))->getValue();
- if (TLI.MaskedValueIsZero(N0.getOperand(0), RHSMask&~LHSMask) &&
- TLI.MaskedValueIsZero(N1.getOperand(0), LHSMask&~RHSMask)) {
+ if (DAG.MaskedValueIsZero(N0.getOperand(0), RHSMask&~LHSMask) &&
+ DAG.MaskedValueIsZero(N1.getOperand(0), LHSMask&~RHSMask)) {
SDOperand X =DAG.getNode(ISD::OR, VT, N0.getOperand(0), N1.getOperand(0));
return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(LHSMask|RHSMask, VT));
}
/// MatchRotateHalf - Match "(X shl/srl V1) & V2" where V2 may not be present.
static bool MatchRotateHalf(SDOperand Op, SDOperand &Shift, SDOperand &Mask) {
if (Op.getOpcode() == ISD::AND) {
- if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
+ if (isa<ConstantSDNode>(Op.getOperand(1))) {
Mask = Op.getOperand(1);
Op = Op.getOperand(0);
} else {
}
unsigned OpSizeInBits = MVT::getSizeInBits(VT);
+ SDOperand LHSShiftArg = LHSShift.getOperand(0);
+ SDOperand LHSShiftAmt = LHSShift.getOperand(1);
+ SDOperand RHSShiftAmt = RHSShift.getOperand(1);
// fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1)
// fold (or (shl x, C1), (srl x, C2)) -> (rotr x, C2)
- if (LHSShift.getOperand(1).getOpcode() == ISD::Constant &&
- RHSShift.getOperand(1).getOpcode() == ISD::Constant) {
- uint64_t LShVal = cast<ConstantSDNode>(LHSShift.getOperand(1))->getValue();
- uint64_t RShVal = cast<ConstantSDNode>(RHSShift.getOperand(1))->getValue();
+ if (LHSShiftAmt.getOpcode() == ISD::Constant &&
+ RHSShiftAmt.getOpcode() == ISD::Constant) {
+ uint64_t LShVal = cast<ConstantSDNode>(LHSShiftAmt)->getValue();
+ uint64_t RShVal = cast<ConstantSDNode>(RHSShiftAmt)->getValue();
if ((LShVal + RShVal) != OpSizeInBits)
return 0;
SDOperand Rot;
if (HasROTL)
- Rot = DAG.getNode(ISD::ROTL, VT, LHSShift.getOperand(0),
- LHSShift.getOperand(1));
+ Rot = DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt);
else
- Rot = DAG.getNode(ISD::ROTR, VT, LHSShift.getOperand(0),
- RHSShift.getOperand(1));
+ Rot = DAG.getNode(ISD::ROTR, VT, LHSShiftArg, RHSShiftAmt);
// If there is an AND of either shifted operand, apply it to the result.
if (LHSMask.Val || RHSMask.Val) {
// fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotl x, y)
// fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotr x, (sub 32, y))
- if (RHSShift.getOperand(1).getOpcode() == ISD::SUB &&
- LHSShift.getOperand(1) == RHSShift.getOperand(1).getOperand(1)) {
+ if (RHSShiftAmt.getOpcode() == ISD::SUB &&
+ LHSShiftAmt == RHSShiftAmt.getOperand(1)) {
if (ConstantSDNode *SUBC =
- dyn_cast<ConstantSDNode>(RHSShift.getOperand(1).getOperand(0))) {
+ dyn_cast<ConstantSDNode>(RHSShiftAmt.getOperand(0))) {
if (SUBC->getValue() == OpSizeInBits)
if (HasROTL)
- return DAG.getNode(ISD::ROTL, VT, LHSShift.getOperand(0),
- LHSShift.getOperand(1)).Val;
+ return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).Val;
else
- return DAG.getNode(ISD::ROTR, VT, LHSShift.getOperand(0),
- LHSShift.getOperand(1)).Val;
+ return DAG.getNode(ISD::ROTR, VT, LHSShiftArg, RHSShiftAmt).Val;
}
}
// fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotr x, y)
// fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotl x, (sub 32, y))
- if (LHSShift.getOperand(1).getOpcode() == ISD::SUB &&
- RHSShift.getOperand(1) == LHSShift.getOperand(1).getOperand(1)) {
+ if (LHSShiftAmt.getOpcode() == ISD::SUB &&
+ RHSShiftAmt == LHSShiftAmt.getOperand(1)) {
if (ConstantSDNode *SUBC =
- dyn_cast<ConstantSDNode>(LHSShift.getOperand(1).getOperand(0))) {
+ dyn_cast<ConstantSDNode>(LHSShiftAmt.getOperand(0))) {
if (SUBC->getValue() == OpSizeInBits)
if (HasROTL)
- return DAG.getNode(ISD::ROTL, VT, LHSShift.getOperand(0),
- LHSShift.getOperand(1)).Val;
+ return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).Val;
else
- return DAG.getNode(ISD::ROTR, VT, LHSShift.getOperand(0),
- RHSShift.getOperand(1)).Val;
+ return DAG.getNode(ISD::ROTR, VT, LHSShiftArg, RHSShiftAmt).Val;
+ }
+ }
+
+ // Look for sign/zext/any-extended cases:
+ if ((LHSShiftAmt.getOpcode() == ISD::SIGN_EXTEND
+ || LHSShiftAmt.getOpcode() == ISD::ZERO_EXTEND
+ || LHSShiftAmt.getOpcode() == ISD::ANY_EXTEND) &&
+ (RHSShiftAmt.getOpcode() == ISD::SIGN_EXTEND
+ || RHSShiftAmt.getOpcode() == ISD::ZERO_EXTEND
+ || RHSShiftAmt.getOpcode() == ISD::ANY_EXTEND)) {
+ SDOperand LExtOp0 = LHSShiftAmt.getOperand(0);
+ SDOperand RExtOp0 = RHSShiftAmt.getOperand(0);
+ if (RExtOp0.getOpcode() == ISD::SUB &&
+ RExtOp0.getOperand(1) == LExtOp0) {
+ // fold (or (shl x, (*ext y)), (srl x, (*ext (sub 32, y)))) ->
+ // (rotr x, y)
+ // fold (or (shl x, (*ext y)), (srl x, (*ext (sub 32, y)))) ->
+ // (rotl x, (sub 32, y))
+ if (ConstantSDNode *SUBC = cast<ConstantSDNode>(RExtOp0.getOperand(0))) {
+ if (SUBC->getValue() == OpSizeInBits) {
+ if (HasROTL)
+ return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).Val;
+ else
+ return DAG.getNode(ISD::ROTR, VT, LHSShiftArg, RHSShiftAmt).Val;
+ }
+ }
+ } else if (LExtOp0.getOpcode() == ISD::SUB &&
+ RExtOp0 == LExtOp0.getOperand(1)) {
+ // fold (or (shl x, (*ext (sub 32, y))), (srl x, (*ext r))) ->
+ // (rotl x, y)
+ // fold (or (shl x, (*ext (sub 32, y))), (srl x, (*ext r))) ->
+ // (rotr x, (sub 32, y))
+ if (ConstantSDNode *SUBC = cast<ConstantSDNode>(LExtOp0.getOperand(0))) {
+ if (SUBC->getValue() == OpSizeInBits) {
+ if (HasROTL)
+ return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, RHSShiftAmt).Val;
+ else
+ return DAG.getNode(ISD::ROTL, VT, LHSShiftArg, LHSShiftAmt).Val;
+ }
+ }
}
}
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
MVT::ValueType VT = N0.getValueType();
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
+ // fold (xor x, undef) -> undef
+ if (N0.getOpcode() == ISD::UNDEF)
+ return N0;
+ if (N1.getOpcode() == ISD::UNDEF)
+ return N1;
// fold (xor c1, c2) -> c1^c2
if (N0C && N1C)
return DAG.getNode(ISD::XOR, VT, N0, N1);
assert(0 && "Unhandled SetCC Equivalent!");
abort();
}
+ // fold (not (zext (setcc x, y))) -> (zext (not (setcc x, y)))
+ if (N1C && N1C->getValue() == 1 && N0.getOpcode() == ISD::ZERO_EXTEND &&
+ N0.Val->hasOneUse() && isSetCCEquivalent(N0.getOperand(0), LHS, RHS, CC)){
+ SDOperand V = N0.getOperand(0);
+ V = DAG.getNode(ISD::XOR, V.getValueType(), V,
+ DAG.getConstant(1, V.getValueType()));
+ AddToWorkList(V.Val);
+ return DAG.getNode(ISD::ZERO_EXTEND, VT, V);
+ }
+
// fold !(x or y) -> (!x and !y) iff x or y are setcc
- if (N1C && N1C->getValue() == 1 &&
+ if (N1C && N1C->getValue() == 1 && VT == MVT::i1 &&
(N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) {
SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) {
return DAG.getConstant(0, VT);
} else if (!AfterLegalize || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT)) {
// Produce a vector of zeros.
- SDOperand El = DAG.getConstant(0, MVT::getVectorBaseType(VT));
+ SDOperand El = DAG.getConstant(0, MVT::getVectorElementType(VT));
std::vector<SDOperand> Ops(MVT::getVectorNumElements(VT), El);
return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
}
return SDOperand();
}
+/// visitShiftByConstant - Handle transforms common to the three shifts, when
+/// the shift amount is a constant.
+SDOperand DAGCombiner::visitShiftByConstant(SDNode *N, unsigned Amt) {
+ SDNode *LHS = N->getOperand(0).Val;
+ if (!LHS->hasOneUse()) return SDOperand();
+
+ // We want to pull some binops through shifts, so that we have (and (shift))
+ // instead of (shift (and)), likewise for add, or, xor, etc. This sort of
+ // thing happens with address calculations, so it's important to canonicalize
+ // it.
+ bool HighBitSet = false; // Can we transform this if the high bit is set?
+
+ switch (LHS->getOpcode()) {
+ default: return SDOperand();
+ case ISD::OR:
+ case ISD::XOR:
+ HighBitSet = false; // We can only transform sra if the high bit is clear.
+ break;
+ case ISD::AND:
+ HighBitSet = true; // We can only transform sra if the high bit is set.
+ break;
+ case ISD::ADD:
+ if (N->getOpcode() != ISD::SHL)
+ return SDOperand(); // only shl(add) not sr[al](add).
+ HighBitSet = false; // We can only transform sra if the high bit is clear.
+ break;
+ }
+
+ // We require the RHS of the binop to be a constant as well.
+ ConstantSDNode *BinOpCst = dyn_cast<ConstantSDNode>(LHS->getOperand(1));
+ if (!BinOpCst) return SDOperand();
+
+
+ // FIXME: disable this for unless the input to the binop is a shift by a
+ // constant. If it is not a shift, it pessimizes some common cases like:
+ //
+ //void foo(int *X, int i) { X[i & 1235] = 1; }
+ //int bar(int *X, int i) { return X[i & 255]; }
+ SDNode *BinOpLHSVal = LHS->getOperand(0).Val;
+ if ((BinOpLHSVal->getOpcode() != ISD::SHL &&
+ BinOpLHSVal->getOpcode() != ISD::SRA &&
+ BinOpLHSVal->getOpcode() != ISD::SRL) ||
+ !isa<ConstantSDNode>(BinOpLHSVal->getOperand(1)))
+ return SDOperand();
+
+ MVT::ValueType VT = N->getValueType(0);
+
+ // If this is a signed shift right, and the high bit is modified
+ // by the logical operation, do not perform the transformation.
+ // The highBitSet boolean indicates the value of the high bit of
+ // the constant which would cause it to be modified for this
+ // operation.
+ if (N->getOpcode() == ISD::SRA) {
+ uint64_t BinOpRHSSign = BinOpCst->getValue() >> MVT::getSizeInBits(VT)-1;
+ if ((bool)BinOpRHSSign != HighBitSet)
+ return SDOperand();
+ }
+
+ // Fold the constants, shifting the binop RHS by the shift amount.
+ SDOperand NewRHS = DAG.getNode(N->getOpcode(), N->getValueType(0),
+ LHS->getOperand(1), N->getOperand(1));
+
+ // Create the new shift.
+ SDOperand NewShift = DAG.getNode(N->getOpcode(), VT, LHS->getOperand(0),
+ N->getOperand(1));
+
+ // Create the new binop.
+ return DAG.getNode(LHS->getOpcode(), VT, NewShift, NewRHS);
+}
+
+
SDOperand DAGCombiner::visitSHL(SDNode *N) {
SDOperand N0 = N->getOperand(0);
SDOperand N1 = N->getOperand(1);
if (N1C && N1C->isNullValue())
return N0;
// if (shl x, c) is known to be zero, return 0
- if (TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
+ if (DAG.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
return DAG.getConstant(0, VT);
- if (SimplifyDemandedBits(SDOperand(N, 0)))
+ if (N1C && SimplifyDemandedBits(SDOperand(N, 0)))
return SDOperand(N, 0);
// fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2)
if (N1C && N0.getOpcode() == ISD::SHL &&
if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1))
return DAG.getNode(ISD::AND, VT, N0.getOperand(0),
DAG.getConstant(~0ULL << N1C->getValue(), VT));
- // fold (shl (add x, c1), c2) -> (add (shl x, c2), c1<<c2)
- if (N1C && N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse() &&
- isa<ConstantSDNode>(N0.getOperand(1))) {
- return DAG.getNode(ISD::ADD, VT,
- DAG.getNode(ISD::SHL, VT, N0.getOperand(0), N1),
- DAG.getNode(ISD::SHL, VT, N0.getOperand(1), N1));
- }
- return SDOperand();
+
+ return N1C ? visitShiftByConstant(N, N1C->getValue()) : SDOperand();
}
SDOperand DAGCombiner::visitSRA(SDNode *N) {
// If the sign bit is known to be zero, switch this to a SRL.
- if (TLI.MaskedValueIsZero(N0, MVT::getIntVTSignBit(VT)))
+ if (DAG.MaskedValueIsZero(N0, MVT::getIntVTSignBit(VT)))
return DAG.getNode(ISD::SRL, VT, N0, N1);
- return SDOperand();
+
+ return N1C ? visitShiftByConstant(N, N1C->getValue()) : SDOperand();
}
SDOperand DAGCombiner::visitSRL(SDNode *N) {
if (N1C && N1C->isNullValue())
return N0;
// if (srl x, c) is known to be zero, return 0
- if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits)))
+ if (N1C && DAG.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits)))
return DAG.getConstant(0, VT);
+
// fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2)
if (N1C && N0.getOpcode() == ISD::SRL &&
N0.getOperand(1).getOpcode() == ISD::Constant) {
return DAG.getNode(ISD::ANY_EXTEND, VT, SmallShift);
}
+ // fold (srl (sra X, Y), 31) -> (srl X, 31). This srl only looks at the sign
+ // bit, which is unmodified by sra.
+ if (N1C && N1C->getValue()+1 == MVT::getSizeInBits(VT)) {
+ if (N0.getOpcode() == ISD::SRA)
+ return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), N1);
+ }
+
// fold (srl (ctlz x), "5") -> x iff x has one bit set (the low bit).
if (N1C && N0.getOpcode() == ISD::CTLZ &&
N1C->getValue() == Log2_32(MVT::getSizeInBits(VT))) {
uint64_t KnownZero, KnownOne, Mask = MVT::getIntVTBitMask(VT);
- TLI.ComputeMaskedBits(N0.getOperand(0), Mask, KnownZero, KnownOne);
+ DAG.ComputeMaskedBits(N0.getOperand(0), Mask, KnownZero, KnownOne);
// If any of the input bits are KnownOne, then the input couldn't be all
// zeros, thus the result of the srl will always be zero.
}
}
- return SDOperand();
+ // fold operands of srl based on knowledge that the low bits are not
+ // demanded.
+ if (N1C && SimplifyDemandedBits(SDOperand(N, 0)))
+ return SDOperand(N, 0);
+
+ return N1C ? visitShiftByConstant(N, N1C->getValue()) : SDOperand();
}
SDOperand DAGCombiner::visitCTLZ(SDNode *N) {
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
MVT::ValueType VT = N->getValueType(0);
+ MVT::ValueType VT0 = N0.getValueType();
// fold select C, X, X -> X
if (N1 == N2)
// fold select C, 1, X -> C | X
if (MVT::i1 == VT && N1C && N1C->getValue() == 1)
return DAG.getNode(ISD::OR, VT, N0, N2);
+ // fold select C, 0, 1 -> ~C
+ if (MVT::isInteger(VT) && MVT::isInteger(VT0) &&
+ N1C && N2C && N1C->isNullValue() && N2C->getValue() == 1) {
+ SDOperand XORNode = DAG.getNode(ISD::XOR, VT0, N0, DAG.getConstant(1, VT0));
+ if (VT == VT0)
+ return XORNode;
+ AddToWorkList(XORNode.Val);
+ if (MVT::getSizeInBits(VT) > MVT::getSizeInBits(VT0))
+ return DAG.getNode(ISD::ZERO_EXTEND, VT, XORNode);
+ return DAG.getNode(ISD::TRUNCATE, VT, XORNode);
+ }
// fold select C, 0, X -> ~C & X
- // FIXME: this should check for C type == X type, not i1?
- if (MVT::i1 == VT && N1C && N1C->isNullValue()) {
+ if (VT == VT0 && VT == MVT::i1 && N1C && N1C->isNullValue()) {
SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
AddToWorkList(XORNode.Val);
return DAG.getNode(ISD::AND, VT, XORNode, N2);
}
// fold select C, X, 1 -> ~C | X
- if (MVT::i1 == VT && N2C && N2C->getValue() == 1) {
+ if (VT == VT0 && VT == MVT::i1 && N2C && N2C->getValue() == 1) {
SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
AddToWorkList(XORNode.Val);
return DAG.getNode(ISD::OR, VT, XORNode, N1);
SDOperand N2 = N->getOperand(2);
SDOperand N3 = N->getOperand(3);
SDOperand N4 = N->getOperand(4);
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
- ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
- ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get();
// fold select_cc lhs, rhs, x, x, cc -> x
// Determine if the condition we're dealing with is constant
SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
+ if (SCC.Val) AddToWorkList(SCC.Val);
if (ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val)) {
if (SCCC->getValue())
cast<CondCodeSDNode>(N->getOperand(2))->get());
}
+// ExtendUsesToFormExtLoad - Trying to extend uses of a load to enable this:
+// "fold ({s|z}ext (load x)) -> ({s|z}ext (truncate ({s|z}extload x)))"
+// transformation. Returns true if extension are possible and the above
+// mentioned transformation is profitable.
+static bool ExtendUsesToFormExtLoad(SDNode *N, SDOperand N0,
+ unsigned ExtOpc,
+ SmallVector<SDNode*, 4> &ExtendNodes,
+ TargetLowering &TLI) {
+ bool HasCopyToRegUses = false;
+ bool isTruncFree = TLI.isTruncateFree(N->getValueType(0), N0.getValueType());
+ for (SDNode::use_iterator UI = N0.Val->use_begin(), UE = N0.Val->use_end();
+ UI != UE; ++UI) {
+ SDNode *User = *UI;
+ if (User == N)
+ continue;
+ // FIXME: Only extend SETCC N, N and SETCC N, c for now.
+ if (User->getOpcode() == ISD::SETCC) {
+ ISD::CondCode CC = cast<CondCodeSDNode>(User->getOperand(2))->get();
+ if (ExtOpc == ISD::ZERO_EXTEND && ISD::isSignedIntSetCC(CC))
+ // Sign bits will be lost after a zext.
+ return false;
+ bool Add = false;
+ for (unsigned i = 0; i != 2; ++i) {
+ SDOperand UseOp = User->getOperand(i);
+ if (UseOp == N0)
+ continue;
+ if (!isa<ConstantSDNode>(UseOp))
+ return false;
+ Add = true;
+ }
+ if (Add)
+ ExtendNodes.push_back(User);
+ } else {
+ for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
+ SDOperand UseOp = User->getOperand(i);
+ if (UseOp == N0) {
+ // If truncate from extended type to original load type is free
+ // on this target, then it's ok to extend a CopyToReg.
+ if (isTruncFree && User->getOpcode() == ISD::CopyToReg)
+ HasCopyToRegUses = true;
+ else
+ return false;
+ }
+ }
+ }
+ }
+
+ if (HasCopyToRegUses) {
+ bool BothLiveOut = false;
+ for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
+ UI != UE; ++UI) {
+ SDNode *User = *UI;
+ for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
+ SDOperand UseOp = User->getOperand(i);
+ if (UseOp.Val == N && UseOp.ResNo == 0) {
+ BothLiveOut = true;
+ break;
+ }
+ }
+ }
+ if (BothLiveOut)
+ // Both unextended and extended values are live out. There had better be
+ // good a reason for the transformation.
+ return ExtendNodes.size();
+ }
+ return true;
+}
+
SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) {
SDOperand N0 = N->getOperand(0);
MVT::ValueType VT = N->getValueType(0);
// fold (sext c1) -> c1
- if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0))
+ if (isa<ConstantSDNode>(N0))
return DAG.getNode(ISD::SIGN_EXTEND, VT, N0);
// fold (sext (sext x)) -> (sext x)
if (N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND)
return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0));
- // fold (sext (truncate x)) -> (sextinreg x).
- if (N0.getOpcode() == ISD::TRUNCATE &&
- (!AfterLegalize || TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG,
- N0.getValueType()))) {
+ // fold (sext (truncate (load x))) -> (sext (smaller load x))
+ // fold (sext (truncate (srl (load x), c))) -> (sext (smaller load (x+c/n)))
+ if (N0.getOpcode() == ISD::TRUNCATE) {
+ SDOperand NarrowLoad = ReduceLoadWidth(N0.Val);
+ if (NarrowLoad.Val) {
+ if (NarrowLoad.Val != N0.Val)
+ CombineTo(N0.Val, NarrowLoad);
+ return DAG.getNode(ISD::SIGN_EXTEND, VT, NarrowLoad);
+ }
+ }
+
+ // See if the value being truncated is already sign extended. If so, just
+ // eliminate the trunc/sext pair.
+ if (N0.getOpcode() == ISD::TRUNCATE) {
SDOperand Op = N0.getOperand(0);
- if (Op.getValueType() < VT) {
- Op = DAG.getNode(ISD::ANY_EXTEND, VT, Op);
- } else if (Op.getValueType() > VT) {
- Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
+ unsigned OpBits = MVT::getSizeInBits(Op.getValueType());
+ unsigned MidBits = MVT::getSizeInBits(N0.getValueType());
+ unsigned DestBits = MVT::getSizeInBits(VT);
+ unsigned NumSignBits = DAG.ComputeNumSignBits(Op);
+
+ if (OpBits == DestBits) {
+ // Op is i32, Mid is i8, and Dest is i32. If Op has more than 24 sign
+ // bits, it is already ready.
+ if (NumSignBits > DestBits-MidBits)
+ return Op;
+ } else if (OpBits < DestBits) {
+ // Op is i32, Mid is i8, and Dest is i64. If Op has more than 24 sign
+ // bits, just sext from i32.
+ if (NumSignBits > OpBits-MidBits)
+ return DAG.getNode(ISD::SIGN_EXTEND, VT, Op);
+ } else {
+ // Op is i64, Mid is i8, and Dest is i32. If Op has more than 56 sign
+ // bits, just truncate to i32.
+ if (NumSignBits > OpBits-MidBits)
+ return DAG.getNode(ISD::TRUNCATE, VT, Op);
+ }
+
+ // fold (sext (truncate x)) -> (sextinreg x).
+ if (!AfterLegalize || TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG,
+ N0.getValueType())) {
+ if (Op.getValueType() < VT)
+ Op = DAG.getNode(ISD::ANY_EXTEND, VT, Op);
+ else if (Op.getValueType() > VT)
+ Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
+ return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, Op,
+ DAG.getValueType(N0.getValueType()));
}
- return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, Op,
- DAG.getValueType(N0.getValueType()));
}
// fold (sext (load x)) -> (sext (truncate (sextload x)))
- if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() &&
- (!AfterLegalize||TLI.isOperationLegal(ISD::SEXTLOAD, N0.getValueType()))){
- SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- N0.getValueType());
- CombineTo(N, ExtLoad);
- CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
- ExtLoad.getValue(1));
- return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ if (ISD::isNON_EXTLoad(N0.Val) &&
+ (!AfterLegalize||TLI.isLoadXLegal(ISD::SEXTLOAD, N0.getValueType()))){
+ bool DoXform = true;
+ SmallVector<SDNode*, 4> SetCCs;
+ if (!N0.hasOneUse())
+ DoXform = ExtendUsesToFormExtLoad(N, N0, ISD::SIGN_EXTEND, SetCCs, TLI);
+ if (DoXform) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(),
+ N0.getValueType(),
+ LN0->isVolatile(),
+ LN0->getAlignment());
+ CombineTo(N, ExtLoad);
+ SDOperand Trunc = DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad);
+ CombineTo(N0.Val, Trunc, ExtLoad.getValue(1));
+ // Extend SetCC uses if necessary.
+ for (unsigned i = 0, e = SetCCs.size(); i != e; ++i) {
+ SDNode *SetCC = SetCCs[i];
+ SmallVector<SDOperand, 4> Ops;
+ for (unsigned j = 0; j != 2; ++j) {
+ SDOperand SOp = SetCC->getOperand(j);
+ if (SOp == Trunc)
+ Ops.push_back(ExtLoad);
+ else
+ Ops.push_back(DAG.getNode(ISD::SIGN_EXTEND, VT, SOp));
+ }
+ Ops.push_back(SetCC->getOperand(2));
+ CombineTo(SetCC, DAG.getNode(ISD::SETCC, SetCC->getValueType(0),
+ &Ops[0], Ops.size()));
+ }
+ return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ }
}
// fold (sext (sextload x)) -> (sext (truncate (sextload x)))
// fold (sext ( extload x)) -> (sext (truncate (sextload x)))
- if ((N0.getOpcode() == ISD::SEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) &&
- N0.hasOneUse()) {
- MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT();
- SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2), EVT);
- CombineTo(N, ExtLoad);
- CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
- ExtLoad.getValue(1));
- return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ if ((ISD::isSEXTLoad(N0.Val) || ISD::isEXTLoad(N0.Val)) &&
+ ISD::isUNINDEXEDLoad(N0.Val) && N0.hasOneUse()) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ MVT::ValueType EVT = LN0->getLoadedVT();
+ if (!AfterLegalize || TLI.isLoadXLegal(ISD::SEXTLOAD, EVT)) {
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(),
+ LN0->getAlignment());
+ CombineTo(N, ExtLoad);
+ CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
+ ExtLoad.getValue(1));
+ return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ }
+ }
+
+ // sext(setcc x,y,cc) -> select_cc x, y, -1, 0, cc
+ if (N0.getOpcode() == ISD::SETCC) {
+ SDOperand SCC =
+ SimplifySelectCC(N0.getOperand(0), N0.getOperand(1),
+ DAG.getConstant(~0ULL, VT), DAG.getConstant(0, VT),
+ cast<CondCodeSDNode>(N0.getOperand(2))->get(), true);
+ if (SCC.Val) return SCC;
}
return SDOperand();
MVT::ValueType VT = N->getValueType(0);
// fold (zext c1) -> c1
- if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0))
+ if (isa<ConstantSDNode>(N0))
return DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
// fold (zext (zext x)) -> (zext x)
// fold (zext (aext x)) -> (zext x)
if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND)
return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0));
+ // fold (zext (truncate (load x))) -> (zext (smaller load x))
+ // fold (zext (truncate (srl (load x), c))) -> (zext (small load (x+c/n)))
+ if (N0.getOpcode() == ISD::TRUNCATE) {
+ SDOperand NarrowLoad = ReduceLoadWidth(N0.Val);
+ if (NarrowLoad.Val) {
+ if (NarrowLoad.Val != N0.Val)
+ CombineTo(N0.Val, NarrowLoad);
+ return DAG.getNode(ISD::ZERO_EXTEND, VT, NarrowLoad);
+ }
+ }
+
// fold (zext (truncate x)) -> (and x, mask)
if (N0.getOpcode() == ISD::TRUNCATE &&
(!AfterLegalize || TLI.isOperationLegal(ISD::AND, VT))) {
}
// fold (zext (load x)) -> (zext (truncate (zextload x)))
- if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() &&
- (!AfterLegalize||TLI.isOperationLegal(ISD::ZEXTLOAD, N0.getValueType()))){
- SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- N0.getValueType());
- CombineTo(N, ExtLoad);
- CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
- ExtLoad.getValue(1));
- return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ if (ISD::isNON_EXTLoad(N0.Val) &&
+ (!AfterLegalize||TLI.isLoadXLegal(ISD::ZEXTLOAD, N0.getValueType()))) {
+ bool DoXform = true;
+ SmallVector<SDNode*, 4> SetCCs;
+ if (!N0.hasOneUse())
+ DoXform = ExtendUsesToFormExtLoad(N, N0, ISD::ZERO_EXTEND, SetCCs, TLI);
+ if (DoXform) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(),
+ N0.getValueType(),
+ LN0->isVolatile(),
+ LN0->getAlignment());
+ CombineTo(N, ExtLoad);
+ SDOperand Trunc = DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad);
+ CombineTo(N0.Val, Trunc, ExtLoad.getValue(1));
+ // Extend SetCC uses if necessary.
+ for (unsigned i = 0, e = SetCCs.size(); i != e; ++i) {
+ SDNode *SetCC = SetCCs[i];
+ SmallVector<SDOperand, 4> Ops;
+ for (unsigned j = 0; j != 2; ++j) {
+ SDOperand SOp = SetCC->getOperand(j);
+ if (SOp == Trunc)
+ Ops.push_back(ExtLoad);
+ else
+ Ops.push_back(DAG.getNode(ISD::ZERO_EXTEND, VT, SOp));
+ }
+ Ops.push_back(SetCC->getOperand(2));
+ CombineTo(SetCC, DAG.getNode(ISD::SETCC, SetCC->getValueType(0),
+ &Ops[0], Ops.size()));
+ }
+ return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ }
}
// fold (zext (zextload x)) -> (zext (truncate (zextload x)))
// fold (zext ( extload x)) -> (zext (truncate (zextload x)))
- if ((N0.getOpcode() == ISD::ZEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) &&
- N0.hasOneUse()) {
- MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT();
- SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2), EVT);
+ if ((ISD::isZEXTLoad(N0.Val) || ISD::isEXTLoad(N0.Val)) &&
+ ISD::isUNINDEXEDLoad(N0.Val) && N0.hasOneUse()) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ MVT::ValueType EVT = LN0->getLoadedVT();
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(),
+ LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
return SDOperand(N, 0); // Return N so it doesn't get rechecked!
}
+
+ // zext(setcc x,y,cc) -> select_cc x, y, 1, 0, cc
+ if (N0.getOpcode() == ISD::SETCC) {
+ SDOperand SCC =
+ SimplifySelectCC(N0.getOperand(0), N0.getOperand(1),
+ DAG.getConstant(1, VT), DAG.getConstant(0, VT),
+ cast<CondCodeSDNode>(N0.getOperand(2))->get(), true);
+ if (SCC.Val) return SCC;
+ }
+
return SDOperand();
}
N0.getOpcode() == ISD::SIGN_EXTEND)
return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0));
+ // fold (aext (truncate (load x))) -> (aext (smaller load x))
+ // fold (aext (truncate (srl (load x), c))) -> (aext (small load (x+c/n)))
+ if (N0.getOpcode() == ISD::TRUNCATE) {
+ SDOperand NarrowLoad = ReduceLoadWidth(N0.Val);
+ if (NarrowLoad.Val) {
+ if (NarrowLoad.Val != N0.Val)
+ CombineTo(N0.Val, NarrowLoad);
+ return DAG.getNode(ISD::ANY_EXTEND, VT, NarrowLoad);
+ }
+ }
+
// fold (aext (truncate x))
if (N0.getOpcode() == ISD::TRUNCATE) {
SDOperand TruncOp = N0.getOperand(0);
}
// fold (aext (load x)) -> (aext (truncate (extload x)))
- if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() &&
- (!AfterLegalize||TLI.isOperationLegal(ISD::EXTLOAD, N0.getValueType()))) {
- SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- N0.getValueType());
+ if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() &&
+ (!AfterLegalize||TLI.isLoadXLegal(ISD::EXTLOAD, N0.getValueType()))) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(),
+ N0.getValueType(),
+ LN0->isVolatile(),
+ LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
// fold (aext (zextload x)) -> (aext (truncate (zextload x)))
// fold (aext (sextload x)) -> (aext (truncate (sextload x)))
// fold (aext ( extload x)) -> (aext (truncate (extload x)))
- if ((N0.getOpcode() == ISD::ZEXTLOAD || N0.getOpcode() == ISD::EXTLOAD ||
- N0.getOpcode() == ISD::SEXTLOAD) &&
+ if (N0.getOpcode() == ISD::LOAD &&
+ !ISD::isNON_EXTLoad(N0.Val) && ISD::isUNINDEXEDLoad(N0.Val) &&
N0.hasOneUse()) {
- MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT();
- SDOperand ExtLoad = DAG.getExtLoad(N0.getOpcode(), VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2), EVT);
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ MVT::ValueType EVT = LN0->getLoadedVT();
+ SDOperand ExtLoad = DAG.getExtLoad(LN0->getExtensionType(), VT,
+ LN0->getChain(), LN0->getBasePtr(),
+ LN0->getSrcValue(),
+ LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(),
+ LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
return SDOperand(N, 0); // Return N so it doesn't get rechecked!
}
+
+ // aext(setcc x,y,cc) -> select_cc x, y, 1, 0, cc
+ if (N0.getOpcode() == ISD::SETCC) {
+ SDOperand SCC =
+ SimplifySelectCC(N0.getOperand(0), N0.getOperand(1),
+ DAG.getConstant(1, VT), DAG.getConstant(0, VT),
+ cast<CondCodeSDNode>(N0.getOperand(2))->get(), true);
+ if (SCC.Val)
+ return SCC;
+ }
+
+ return SDOperand();
+}
+
+/// GetDemandedBits - See if the specified operand can be simplified with the
+/// knowledge that only the bits specified by Mask are used. If so, return the
+/// simpler operand, otherwise return a null SDOperand.
+SDOperand DAGCombiner::GetDemandedBits(SDOperand V, uint64_t Mask) {
+ switch (V.getOpcode()) {
+ default: break;
+ case ISD::OR:
+ case ISD::XOR:
+ // If the LHS or RHS don't contribute bits to the or, drop them.
+ if (DAG.MaskedValueIsZero(V.getOperand(0), Mask))
+ return V.getOperand(1);
+ if (DAG.MaskedValueIsZero(V.getOperand(1), Mask))
+ return V.getOperand(0);
+ break;
+ case ISD::SRL:
+ // Only look at single-use SRLs.
+ if (!V.Val->hasOneUse())
+ break;
+ if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(V.getOperand(1))) {
+ // See if we can recursively simplify the LHS.
+ unsigned Amt = RHSC->getValue();
+ Mask = (Mask << Amt) & MVT::getIntVTBitMask(V.getValueType());
+ SDOperand SimplifyLHS = GetDemandedBits(V.getOperand(0), Mask);
+ if (SimplifyLHS.Val) {
+ return DAG.getNode(ISD::SRL, V.getValueType(),
+ SimplifyLHS, V.getOperand(1));
+ }
+ }
+ }
+ return SDOperand();
+}
+
+/// ReduceLoadWidth - If the result of a wider load is shifted to right of N
+/// bits and then truncated to a narrower type and where N is a multiple
+/// of number of bits of the narrower type, transform it to a narrower load
+/// from address + N / num of bits of new type. If the result is to be
+/// extended, also fold the extension to form a extending load.
+SDOperand DAGCombiner::ReduceLoadWidth(SDNode *N) {
+ unsigned Opc = N->getOpcode();
+ ISD::LoadExtType ExtType = ISD::NON_EXTLOAD;
+ SDOperand N0 = N->getOperand(0);
+ MVT::ValueType VT = N->getValueType(0);
+ MVT::ValueType EVT = N->getValueType(0);
+
+ // Special case: SIGN_EXTEND_INREG is basically truncating to EVT then
+ // extended to VT.
+ if (Opc == ISD::SIGN_EXTEND_INREG) {
+ ExtType = ISD::SEXTLOAD;
+ EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
+ if (AfterLegalize && !TLI.isLoadXLegal(ISD::SEXTLOAD, EVT))
+ return SDOperand();
+ }
+
+ unsigned EVTBits = MVT::getSizeInBits(EVT);
+ unsigned ShAmt = 0;
+ bool CombineSRL = false;
+ if (N0.getOpcode() == ISD::SRL && N0.hasOneUse()) {
+ if (ConstantSDNode *N01 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
+ ShAmt = N01->getValue();
+ // Is the shift amount a multiple of size of VT?
+ if ((ShAmt & (EVTBits-1)) == 0) {
+ N0 = N0.getOperand(0);
+ if (MVT::getSizeInBits(N0.getValueType()) <= EVTBits)
+ return SDOperand();
+ CombineSRL = true;
+ }
+ }
+ }
+
+ if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() &&
+ // Do not allow folding to i1 here. i1 is implicitly stored in memory in
+ // zero extended form: by shrinking the load, we lose track of the fact
+ // that it is already zero extended.
+ // FIXME: This should be reevaluated.
+ VT != MVT::i1) {
+ assert(MVT::getSizeInBits(N0.getValueType()) > EVTBits &&
+ "Cannot truncate to larger type!");
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ MVT::ValueType PtrType = N0.getOperand(1).getValueType();
+ // For big endian targets, we need to adjust the offset to the pointer to
+ // load the correct bytes.
+ if (!TLI.isLittleEndian()) {
+ unsigned LVTStoreBits = MVT::getStoreSizeInBits(N0.getValueType());
+ unsigned EVTStoreBits = MVT::getStoreSizeInBits(EVT);
+ ShAmt = LVTStoreBits - EVTStoreBits - ShAmt;
+ }
+ uint64_t PtrOff = ShAmt / 8;
+ unsigned NewAlign = MinAlign(LN0->getAlignment(), PtrOff);
+ SDOperand NewPtr = DAG.getNode(ISD::ADD, PtrType, LN0->getBasePtr(),
+ DAG.getConstant(PtrOff, PtrType));
+ AddToWorkList(NewPtr.Val);
+ SDOperand Load = (ExtType == ISD::NON_EXTLOAD)
+ ? DAG.getLoad(VT, LN0->getChain(), NewPtr,
+ LN0->getSrcValue(), LN0->getSrcValueOffset(),
+ LN0->isVolatile(), NewAlign)
+ : DAG.getExtLoad(ExtType, VT, LN0->getChain(), NewPtr,
+ LN0->getSrcValue(), LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(), NewAlign);
+ AddToWorkList(N);
+ if (CombineSRL) {
+ DAG.ReplaceAllUsesOfValueWith(N0.getValue(1), Load.getValue(1));
+ CombineTo(N->getOperand(0).Val, Load);
+ } else
+ CombineTo(N0.Val, Load, Load.getValue(1));
+ if (ShAmt) {
+ if (Opc == ISD::SIGN_EXTEND_INREG)
+ return DAG.getNode(Opc, VT, Load, N->getOperand(1));
+ else
+ return DAG.getNode(Opc, VT, Load);
+ }
+ return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ }
+
return SDOperand();
}
return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0, N1);
// If the input is already sign extended, just drop the extension.
- if (TLI.ComputeNumSignBits(N0) >= MVT::getSizeInBits(VT)-EVTBits+1)
+ if (DAG.ComputeNumSignBits(N0) >= MVT::getSizeInBits(VT)-EVTBits+1)
return N0;
// fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2
return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1);
}
- // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is zero
- if (TLI.MaskedValueIsZero(N0, 1ULL << (EVTBits-1)))
+ // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is known zero.
+ if (DAG.MaskedValueIsZero(N0, 1ULL << (EVTBits-1)))
return DAG.getZeroExtendInReg(N0, EVT);
+ // fold operands of sext_in_reg based on knowledge that the top bits are not
+ // demanded.
+ if (SimplifyDemandedBits(SDOperand(N, 0)))
+ return SDOperand(N, 0);
+
+ // fold (sext_in_reg (load x)) -> (smaller sextload x)
+ // fold (sext_in_reg (srl (load x), c)) -> (smaller sextload (x+c/evtbits))
+ SDOperand NarrowLoad = ReduceLoadWidth(N);
+ if (NarrowLoad.Val)
+ return NarrowLoad;
+
// fold (sext_in_reg (srl X, 24), i8) -> sra X, 24
// fold (sext_in_reg (srl X, 23), i8) -> sra X, 23 iff possible.
// We already fold "(sext_in_reg (srl X, 25), i8) -> srl X, 25" above.
if (ShAmt->getValue()+EVTBits <= MVT::getSizeInBits(VT)) {
// We can turn this into an SRA iff the input to the SRL is already sign
// extended enough.
- unsigned InSignBits = TLI.ComputeNumSignBits(N0.getOperand(0));
+ unsigned InSignBits = DAG.ComputeNumSignBits(N0.getOperand(0));
if (MVT::getSizeInBits(VT)-(ShAmt->getValue()+EVTBits) < InSignBits)
return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), N0.getOperand(1));
}
}
-
+
// fold (sext_inreg (extload x)) -> (sextload x)
- if (N0.getOpcode() == ISD::EXTLOAD &&
- EVT == cast<VTSDNode>(N0.getOperand(3))->getVT() &&
- (!AfterLegalize || TLI.isOperationLegal(ISD::SEXTLOAD, EVT))) {
- SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- EVT);
+ if (ISD::isEXTLoad(N0.Val) &&
+ ISD::isUNINDEXEDLoad(N0.Val) &&
+ EVT == cast<LoadSDNode>(N0)->getLoadedVT() &&
+ (!AfterLegalize || TLI.isLoadXLegal(ISD::SEXTLOAD, EVT))) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(),
+ LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
return SDOperand(N, 0); // Return N so it doesn't get rechecked!
}
// fold (sext_inreg (zextload x)) -> (sextload x) iff load has one use
- if (N0.getOpcode() == ISD::ZEXTLOAD && N0.hasOneUse() &&
- EVT == cast<VTSDNode>(N0.getOperand(3))->getVT() &&
- (!AfterLegalize || TLI.isOperationLegal(ISD::SEXTLOAD, EVT))) {
- SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- EVT);
+ if (ISD::isZEXTLoad(N0.Val) && ISD::isUNINDEXEDLoad(N0.Val) &&
+ N0.hasOneUse() &&
+ EVT == cast<LoadSDNode>(N0)->getLoadedVT() &&
+ (!AfterLegalize || TLI.isLoadXLegal(ISD::SEXTLOAD, EVT))) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(),
+ LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
return SDOperand(N, 0); // Return N so it doesn't get rechecked!
// fold (truncate (ext x)) -> (ext x) or (truncate x) or x
if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND||
N0.getOpcode() == ISD::ANY_EXTEND) {
- if (N0.getValueType() < VT)
+ if (N0.getOperand(0).getValueType() < VT)
// if the source is smaller than the dest, we still need an extend
return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0));
- else if (N0.getValueType() > VT)
+ else if (N0.getOperand(0).getValueType() > VT)
// if the source is larger than the dest, than we just need the truncate
return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
else
// and the truncate
return N0.getOperand(0);
}
+
+ // See if we can simplify the input to this truncate through knowledge that
+ // only the low bits are being used. For example "trunc (or (shl x, 8), y)"
+ // -> trunc y
+ SDOperand Shorter = GetDemandedBits(N0, MVT::getIntVTBitMask(VT));
+ if (Shorter.Val)
+ return DAG.getNode(ISD::TRUNCATE, VT, Shorter);
+
// fold (truncate (load x)) -> (smaller load x)
- if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse()) {
- assert(MVT::getSizeInBits(N0.getValueType()) > MVT::getSizeInBits(VT) &&
- "Cannot truncate to larger type!");
- MVT::ValueType PtrType = N0.getOperand(1).getValueType();
- // For big endian targets, we need to add an offset to the pointer to load
- // the correct bytes. For little endian systems, we merely need to read
- // fewer bytes from the same pointer.
- uint64_t PtrOff =
- (MVT::getSizeInBits(N0.getValueType()) - MVT::getSizeInBits(VT)) / 8;
- SDOperand NewPtr = TLI.isLittleEndian() ? N0.getOperand(1) :
- DAG.getNode(ISD::ADD, PtrType, N0.getOperand(1),
- DAG.getConstant(PtrOff, PtrType));
- AddToWorkList(NewPtr.Val);
- SDOperand Load = DAG.getLoad(VT, N0.getOperand(0), NewPtr,N0.getOperand(2));
- AddToWorkList(N);
- CombineTo(N0.Val, Load, Load.getValue(1));
- return SDOperand(N, 0); // Return N so it doesn't get rechecked!
- }
- return SDOperand();
+ // fold (truncate (srl (load x), c)) -> (smaller load (x+c/evtbits))
+ return ReduceLoadWidth(N);
}
SDOperand DAGCombiner::visitBIT_CONVERT(SDNode *N) {
SDOperand N0 = N->getOperand(0);
MVT::ValueType VT = N->getValueType(0);
+ // If the input is a BUILD_VECTOR with all constant elements, fold this now.
+ // Only do this before legalize, since afterward the target may be depending
+ // on the bitconvert.
+ // First check to see if this is all constant.
+ if (!AfterLegalize &&
+ N0.getOpcode() == ISD::BUILD_VECTOR && N0.Val->hasOneUse() &&
+ MVT::isVector(VT)) {
+ bool isSimple = true;
+ for (unsigned i = 0, e = N0.getNumOperands(); i != e; ++i)
+ if (N0.getOperand(i).getOpcode() != ISD::UNDEF &&
+ N0.getOperand(i).getOpcode() != ISD::Constant &&
+ N0.getOperand(i).getOpcode() != ISD::ConstantFP) {
+ isSimple = false;
+ break;
+ }
+
+ MVT::ValueType DestEltVT = MVT::getVectorElementType(N->getValueType(0));
+ assert(!MVT::isVector(DestEltVT) &&
+ "Element type of vector ValueType must not be vector!");
+ if (isSimple) {
+ return ConstantFoldBIT_CONVERTofBUILD_VECTOR(N0.Val, DestEltVT);
+ }
+ }
+
// If the input is a constant, let getNode() fold it.
if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) {
SDOperand Res = DAG.getNode(ISD::BIT_CONVERT, VT, N0);
return DAG.getNode(ISD::BIT_CONVERT, VT, N0.getOperand(0));
// fold (conv (load x)) -> (load (conv*)x)
- // FIXME: These xforms need to know that the resultant load doesn't need a
- // higher alignment than the original!
- if (0 && N0.getOpcode() == ISD::LOAD && N0.hasOneUse()) {
- SDOperand Load = DAG.getLoad(VT, N0.getOperand(0), N0.getOperand(1),
- N0.getOperand(2));
- AddToWorkList(N);
- CombineTo(N0.Val, DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load),
- Load.getValue(1));
- return Load;
- }
-
- return SDOperand();
-}
-
-SDOperand DAGCombiner::visitVBIT_CONVERT(SDNode *N) {
- SDOperand N0 = N->getOperand(0);
- MVT::ValueType VT = N->getValueType(0);
-
- // If the input is a VBUILD_VECTOR with all constant elements, fold this now.
- // First check to see if this is all constant.
- if (N0.getOpcode() == ISD::VBUILD_VECTOR && N0.Val->hasOneUse() &&
- VT == MVT::Vector) {
- bool isSimple = true;
- for (unsigned i = 0, e = N0.getNumOperands()-2; i != e; ++i)
- if (N0.getOperand(i).getOpcode() != ISD::UNDEF &&
- N0.getOperand(i).getOpcode() != ISD::Constant &&
- N0.getOperand(i).getOpcode() != ISD::ConstantFP) {
- isSimple = false;
- break;
- }
-
- MVT::ValueType DestEltVT = cast<VTSDNode>(N->getOperand(2))->getVT();
- if (isSimple && !MVT::isVector(DestEltVT)) {
- return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(N0.Val, DestEltVT);
+ // If the resultant load doesn't need a higher alignment than the original!
+ if (ISD::isNormalLoad(N0.Val) && N0.hasOneUse() &&
+ TLI.isOperationLegal(ISD::LOAD, VT)) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ unsigned Align = TLI.getTargetMachine().getTargetData()->
+ getABITypeAlignment(MVT::getTypeForValueType(VT));
+ unsigned OrigAlign = LN0->getAlignment();
+ if (Align <= OrigAlign) {
+ SDOperand Load = DAG.getLoad(VT, LN0->getChain(), LN0->getBasePtr(),
+ LN0->getSrcValue(), LN0->getSrcValueOffset(),
+ LN0->isVolatile(), Align);
+ AddToWorkList(N);
+ CombineTo(N0.Val, DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load),
+ Load.getValue(1));
+ return Load;
}
}
return SDOperand();
}
-/// ConstantFoldVBIT_CONVERTofVBUILD_VECTOR - We know that BV is a vbuild_vector
+/// ConstantFoldBIT_CONVERTofBUILD_VECTOR - We know that BV is a build_vector
/// node with Constant, ConstantFP or Undef operands. DstEltVT indicates the
/// destination element value type.
SDOperand DAGCombiner::
-ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *BV, MVT::ValueType DstEltVT) {
+ConstantFoldBIT_CONVERTofBUILD_VECTOR(SDNode *BV, MVT::ValueType DstEltVT) {
MVT::ValueType SrcEltVT = BV->getOperand(0).getValueType();
// If this is already the right type, we're done.
// type, convert each element. This handles FP<->INT cases.
if (SrcBitSize == DstBitSize) {
SmallVector<SDOperand, 8> Ops;
- for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) {
+ for (unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) {
Ops.push_back(DAG.getNode(ISD::BIT_CONVERT, DstEltVT, BV->getOperand(i)));
AddToWorkList(Ops.back().Val);
}
- Ops.push_back(*(BV->op_end()-2)); // Add num elements.
- Ops.push_back(DAG.getValueType(DstEltVT));
- return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
+ MVT::ValueType VT =
+ MVT::getVectorType(DstEltVT,
+ MVT::getVectorNumElements(BV->getValueType(0)));
+ return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
}
// Otherwise, we're growing or shrinking the elements. To avoid having to
// same sizes.
assert((SrcEltVT == MVT::f32 || SrcEltVT == MVT::f64) && "Unknown FP VT!");
MVT::ValueType IntVT = SrcEltVT == MVT::f32 ? MVT::i32 : MVT::i64;
- BV = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, IntVT).Val;
+ BV = ConstantFoldBIT_CONVERTofBUILD_VECTOR(BV, IntVT).Val;
SrcEltVT = IntVT;
}
if (MVT::isFloatingPoint(DstEltVT)) {
assert((DstEltVT == MVT::f32 || DstEltVT == MVT::f64) && "Unknown FP VT!");
MVT::ValueType TmpVT = DstEltVT == MVT::f32 ? MVT::i32 : MVT::i64;
- SDNode *Tmp = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, TmpVT).Val;
+ SDNode *Tmp = ConstantFoldBIT_CONVERTofBUILD_VECTOR(BV, TmpVT).Val;
// Next, convert to FP elements of the same size.
- return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(Tmp, DstEltVT);
+ return ConstantFoldBIT_CONVERTofBUILD_VECTOR(Tmp, DstEltVT);
}
// Okay, we know the src/dst types are both integers of differing types.
unsigned NumInputsPerOutput = DstBitSize/SrcBitSize;
SmallVector<SDOperand, 8> Ops;
- for (unsigned i = 0, e = BV->getNumOperands()-2; i != e;
+ for (unsigned i = 0, e = BV->getNumOperands(); i != e;
i += NumInputsPerOutput) {
bool isLE = TLI.isLittleEndian();
uint64_t NewBits = 0;
Ops.push_back(DAG.getConstant(NewBits, DstEltVT));
}
- Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements.
- Ops.push_back(DAG.getValueType(DstEltVT)); // Add element size.
- return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
+ MVT::ValueType VT = MVT::getVectorType(DstEltVT,
+ Ops.size());
+ return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
}
// Finally, this must be the case where we are shrinking elements: each input
// turns into multiple outputs.
unsigned NumOutputsPerInput = SrcBitSize/DstBitSize;
SmallVector<SDOperand, 8> Ops;
- for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) {
+ for (unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) {
if (BV->getOperand(i).getOpcode() == ISD::UNDEF) {
for (unsigned j = 0; j != NumOutputsPerInput; ++j)
Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT));
if (!TLI.isLittleEndian())
std::reverse(Ops.end()-NumOutputsPerInput, Ops.end());
}
- Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements.
- Ops.push_back(DAG.getValueType(DstEltVT)); // Add element size.
- return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
+ MVT::ValueType VT = MVT::getVectorType(DstEltVT, Ops.size());
+ return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
}
ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
MVT::ValueType VT = N->getValueType(0);
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
// fold (fadd c1, c2) -> c1+c2
- if (N0CFP && N1CFP)
+ if (N0CFP && N1CFP && VT != MVT::ppcf128)
return DAG.getNode(ISD::FADD, VT, N0, N1);
// canonicalize constant to RHS
if (N0CFP && !N1CFP)
return DAG.getNode(ISD::FADD, VT, N1, N0);
// fold (A + (-B)) -> A-B
- if (N1.getOpcode() == ISD::FNEG)
- return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0));
+ if (isNegatibleForFree(N1) == 2)
+ return DAG.getNode(ISD::FSUB, VT, N0, GetNegatedExpression(N1, DAG));
// fold ((-A) + B) -> B-A
- if (N0.getOpcode() == ISD::FNEG)
- return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0));
+ if (isNegatibleForFree(N0) == 2)
+ return DAG.getNode(ISD::FSUB, VT, N1, GetNegatedExpression(N0, DAG));
+
+ // If allowed, fold (fadd (fadd x, c1), c2) -> (fadd x, (fadd c1, c2))
+ if (UnsafeFPMath && N1CFP && N0.getOpcode() == ISD::FADD &&
+ N0.Val->hasOneUse() && isa<ConstantFPSDNode>(N0.getOperand(1)))
+ return DAG.getNode(ISD::FADD, VT, N0.getOperand(0),
+ DAG.getNode(ISD::FADD, VT, N0.getOperand(1), N1));
+
return SDOperand();
}
ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
MVT::ValueType VT = N->getValueType(0);
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
// fold (fsub c1, c2) -> c1-c2
- if (N0CFP && N1CFP)
+ if (N0CFP && N1CFP && VT != MVT::ppcf128)
return DAG.getNode(ISD::FSUB, VT, N0, N1);
+ // fold (0-B) -> -B
+ if (UnsafeFPMath && N0CFP && N0CFP->getValueAPF().isZero()) {
+ if (isNegatibleForFree(N1))
+ return GetNegatedExpression(N1, DAG);
+ return DAG.getNode(ISD::FNEG, VT, N1);
+ }
// fold (A-(-B)) -> A+B
- if (N1.getOpcode() == ISD::FNEG)
- return DAG.getNode(ISD::FADD, VT, N0, N1.getOperand(0));
+ if (isNegatibleForFree(N1))
+ return DAG.getNode(ISD::FADD, VT, N0, GetNegatedExpression(N1, DAG));
+
return SDOperand();
}
ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
MVT::ValueType VT = N->getValueType(0);
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
// fold (fmul c1, c2) -> c1*c2
- if (N0CFP && N1CFP)
+ if (N0CFP && N1CFP && VT != MVT::ppcf128)
return DAG.getNode(ISD::FMUL, VT, N0, N1);
// canonicalize constant to RHS
if (N0CFP && !N1CFP)
// fold (fmul X, 2.0) -> (fadd X, X)
if (N1CFP && N1CFP->isExactlyValue(+2.0))
return DAG.getNode(ISD::FADD, VT, N0, N0);
+ // fold (fmul X, -1.0) -> (fneg X)
+ if (N1CFP && N1CFP->isExactlyValue(-1.0))
+ return DAG.getNode(ISD::FNEG, VT, N0);
+
+ // -X * -Y -> X*Y
+ if (char LHSNeg = isNegatibleForFree(N0)) {
+ if (char RHSNeg = isNegatibleForFree(N1)) {
+ // Both can be negated for free, check to see if at least one is cheaper
+ // negated.
+ if (LHSNeg == 2 || RHSNeg == 2)
+ return DAG.getNode(ISD::FMUL, VT, GetNegatedExpression(N0, DAG),
+ GetNegatedExpression(N1, DAG));
+ }
+ }
+
+ // If allowed, fold (fmul (fmul x, c1), c2) -> (fmul x, (fmul c1, c2))
+ if (UnsafeFPMath && N1CFP && N0.getOpcode() == ISD::FMUL &&
+ N0.Val->hasOneUse() && isa<ConstantFPSDNode>(N0.getOperand(1)))
+ return DAG.getNode(ISD::FMUL, VT, N0.getOperand(0),
+ DAG.getNode(ISD::FMUL, VT, N0.getOperand(1), N1));
+
return SDOperand();
}
ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
MVT::ValueType VT = N->getValueType(0);
+ // fold vector ops
+ if (MVT::isVector(VT)) {
+ SDOperand FoldedVOp = SimplifyVBinOp(N);
+ if (FoldedVOp.Val) return FoldedVOp;
+ }
+
// fold (fdiv c1, c2) -> c1/c2
- if (N0CFP && N1CFP)
+ if (N0CFP && N1CFP && VT != MVT::ppcf128)
return DAG.getNode(ISD::FDIV, VT, N0, N1);
+
+
+ // -X / -Y -> X*Y
+ if (char LHSNeg = isNegatibleForFree(N0)) {
+ if (char RHSNeg = isNegatibleForFree(N1)) {
+ // Both can be negated for free, check to see if at least one is cheaper
+ // negated.
+ if (LHSNeg == 2 || RHSNeg == 2)
+ return DAG.getNode(ISD::FDIV, VT, GetNegatedExpression(N0, DAG),
+ GetNegatedExpression(N1, DAG));
+ }
+ }
+
return SDOperand();
}
MVT::ValueType VT = N->getValueType(0);
// fold (frem c1, c2) -> fmod(c1,c2)
- if (N0CFP && N1CFP)
+ if (N0CFP && N1CFP && VT != MVT::ppcf128)
return DAG.getNode(ISD::FREM, VT, N0, N1);
+
return SDOperand();
}
ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
MVT::ValueType VT = N->getValueType(0);
- if (N0CFP && N1CFP) // Constant fold
+ if (N0CFP && N1CFP && VT != MVT::ppcf128) // Constant fold
return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1);
if (N1CFP) {
+ const APFloat& V = N1CFP->getValueAPF();
// copysign(x, c1) -> fabs(x) iff ispos(c1)
// copysign(x, c1) -> fneg(fabs(x)) iff isneg(c1)
- union {
- double d;
- int64_t i;
- } u;
- u.d = N1CFP->getValue();
- if (u.i >= 0)
+ if (!V.isNegative())
return DAG.getNode(ISD::FABS, VT, N0);
else
return DAG.getNode(ISD::FNEG, VT, DAG.getNode(ISD::FABS, VT, N0));
MVT::ValueType VT = N->getValueType(0);
// fold (sint_to_fp c1) -> c1fp
- if (N0C)
+ if (N0C && N0.getValueType() != MVT::ppcf128)
return DAG.getNode(ISD::SINT_TO_FP, VT, N0);
return SDOperand();
}
MVT::ValueType VT = N->getValueType(0);
// fold (uint_to_fp c1) -> c1fp
- if (N0C)
+ if (N0C && N0.getValueType() != MVT::ppcf128)
return DAG.getNode(ISD::UINT_TO_FP, VT, N0);
return SDOperand();
}
MVT::ValueType VT = N->getValueType(0);
// fold (fp_to_uint c1fp) -> c1
- if (N0CFP)
+ if (N0CFP && VT != MVT::ppcf128)
return DAG.getNode(ISD::FP_TO_UINT, VT, N0);
return SDOperand();
}
MVT::ValueType VT = N->getValueType(0);
// fold (fp_round c1fp) -> c1fp
- if (N0CFP)
+ if (N0CFP && N0.getValueType() != MVT::ppcf128)
return DAG.getNode(ISD::FP_ROUND, VT, N0);
// fold (fp_round (fp_extend x)) -> x
// fold (fp_round_inreg c1fp) -> c1fp
if (N0CFP) {
- SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT);
+ SDOperand Round = DAG.getConstantFP(N0CFP->getValueAPF(), EVT);
return DAG.getNode(ISD::FP_EXTEND, VT, Round);
}
return SDOperand();
ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
MVT::ValueType VT = N->getValueType(0);
+ // If this is fp_round(fpextend), don't fold it, allow ourselves to be folded.
+ if (N->hasOneUse() && (*N->use_begin())->getOpcode() == ISD::FP_ROUND)
+ return SDOperand();
+
// fold (fp_extend c1fp) -> c1fp
- if (N0CFP)
+ if (N0CFP && VT != MVT::ppcf128)
return DAG.getNode(ISD::FP_EXTEND, VT, N0);
// fold (fpext (load x)) -> (fpext (fpround (extload x)))
- if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() &&
- (!AfterLegalize||TLI.isOperationLegal(ISD::EXTLOAD, N0.getValueType()))) {
- SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- N0.getValueType());
+ if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() &&
+ (!AfterLegalize||TLI.isLoadXLegal(ISD::EXTLOAD, N0.getValueType()))) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(N0);
+ SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(),
+ LN0->getBasePtr(), LN0->getSrcValue(),
+ LN0->getSrcValueOffset(),
+ N0.getValueType(),
+ LN0->isVolatile(),
+ LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::FP_ROUND, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
SDOperand DAGCombiner::visitFNEG(SDNode *N) {
SDOperand N0 = N->getOperand(0);
- ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
- MVT::ValueType VT = N->getValueType(0);
- // fold (fneg c1) -> -c1
- if (N0CFP)
- return DAG.getNode(ISD::FNEG, VT, N0);
- // fold (fneg (sub x, y)) -> (sub y, x)
- if (N0.getOpcode() == ISD::SUB)
- return DAG.getNode(ISD::SUB, VT, N0.getOperand(1), N0.getOperand(0));
- // fold (fneg (fneg x)) -> x
- if (N0.getOpcode() == ISD::FNEG)
- return N0.getOperand(0);
+ if (isNegatibleForFree(N0))
+ return GetNegatedExpression(N0, DAG);
+
return SDOperand();
}
MVT::ValueType VT = N->getValueType(0);
// fold (fabs c1) -> fabs(c1)
- if (N0CFP)
+ if (N0CFP && VT != MVT::ppcf128)
return DAG.getNode(ISD::FABS, VT, N0);
// fold (fabs (fabs x)) -> (fabs x)
if (N0.getOpcode() == ISD::FABS)
// Use SimplifySetCC to simplify SETCC's.
SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false);
+ if (Simp.Val) AddToWorkList(Simp.Val);
+
ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val);
// fold br_cc true, dest -> br dest (unconditional branch)
// fold br_cc false, dest -> unconditional fall through
if (SCCC && SCCC->isNullValue())
return N->getOperand(0);
+
// fold to a simpler setcc
if (Simp.Val && Simp.getOpcode() == ISD::SETCC)
return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0),
return SDOperand();
}
-SDOperand DAGCombiner::visitLOAD(SDNode *N) {
- SDOperand Chain = N->getOperand(0);
- SDOperand Ptr = N->getOperand(1);
- SDOperand SrcValue = N->getOperand(2);
- // If there are no uses of the loaded value, change uses of the chain value
- // into uses of the chain input (i.e. delete the dead load).
- if (N->hasNUsesOfValue(0, 0))
- return CombineTo(N, DAG.getNode(ISD::UNDEF, N->getValueType(0)), Chain);
-
- // If this load is directly stored, replace the load value with the stored
- // value.
- // TODO: Handle store large -> read small portion.
- // TODO: Handle TRUNCSTORE/EXTLOAD
- if (Chain.getOpcode() == ISD::STORE && Chain.getOperand(2) == Ptr &&
- Chain.getOperand(1).getValueType() == N->getValueType(0))
- return CombineTo(N, Chain.getOperand(1), Chain);
-
- // We can only move the load if it has a user of it's chain result. Otherwise
- // there is no place to attach it's old chain.
- if (CombinerAA) {
- // Walk up chain skipping non-aliasing memory nodes.
- SDOperand BetterChain = FindBetterChain(N, Chain);
-
- // If the there is a better chain.
+/// CombineToPreIndexedLoadStore - Try turning a load / store and a
+/// pre-indexed load / store when the base pointer is a add or subtract
+/// and it has other uses besides the load / store. After the
+/// transformation, the new indexed load / store has effectively folded
+/// the add / subtract in and all of its other uses are redirected to the
+/// new load / store.
+bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) {
+ if (!AfterLegalize)
+ return false;
+
+ bool isLoad = true;
+ SDOperand Ptr;
+ MVT::ValueType VT;
+ if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
+ if (LD->getAddressingMode() != ISD::UNINDEXED)
+ return false;
+ VT = LD->getLoadedVT();
+ if (!TLI.isIndexedLoadLegal(ISD::PRE_INC, VT) &&
+ !TLI.isIndexedLoadLegal(ISD::PRE_DEC, VT))
+ return false;
+ Ptr = LD->getBasePtr();
+ } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
+ if (ST->getAddressingMode() != ISD::UNINDEXED)
+ return false;
+ VT = ST->getStoredVT();
+ if (!TLI.isIndexedStoreLegal(ISD::PRE_INC, VT) &&
+ !TLI.isIndexedStoreLegal(ISD::PRE_DEC, VT))
+ return false;
+ Ptr = ST->getBasePtr();
+ isLoad = false;
+ } else
+ return false;
+
+ // If the pointer is not an add/sub, or if it doesn't have multiple uses, bail
+ // out. There is no reason to make this a preinc/predec.
+ if ((Ptr.getOpcode() != ISD::ADD && Ptr.getOpcode() != ISD::SUB) ||
+ Ptr.Val->hasOneUse())
+ return false;
+
+ // Ask the target to do addressing mode selection.
+ SDOperand BasePtr;
+ SDOperand Offset;
+ ISD::MemIndexedMode AM = ISD::UNINDEXED;
+ if (!TLI.getPreIndexedAddressParts(N, BasePtr, Offset, AM, DAG))
+ return false;
+ // Don't create a indexed load / store with zero offset.
+ if (isa<ConstantSDNode>(Offset) &&
+ cast<ConstantSDNode>(Offset)->getValue() == 0)
+ return false;
+
+ // Try turning it into a pre-indexed load / store except when:
+ // 1) The new base ptr is a frame index.
+ // 2) If N is a store and the new base ptr is either the same as or is a
+ // predecessor of the value being stored.
+ // 3) Another use of old base ptr is a predecessor of N. If ptr is folded
+ // that would create a cycle.
+ // 4) All uses are load / store ops that use it as old base ptr.
+
+ // Check #1. Preinc'ing a frame index would require copying the stack pointer
+ // (plus the implicit offset) to a register to preinc anyway.
+ if (isa<FrameIndexSDNode>(BasePtr))
+ return false;
+
+ // Check #2.
+ if (!isLoad) {
+ SDOperand Val = cast<StoreSDNode>(N)->getValue();
+ if (Val == BasePtr || BasePtr.Val->isPredecessor(Val.Val))
+ return false;
+ }
+
+ // Now check for #3 and #4.
+ bool RealUse = false;
+ for (SDNode::use_iterator I = Ptr.Val->use_begin(),
+ E = Ptr.Val->use_end(); I != E; ++I) {
+ SDNode *Use = *I;
+ if (Use == N)
+ continue;
+ if (Use->isPredecessor(N))
+ return false;
+
+ if (!((Use->getOpcode() == ISD::LOAD &&
+ cast<LoadSDNode>(Use)->getBasePtr() == Ptr) ||
+ (Use->getOpcode() == ISD::STORE) &&
+ cast<StoreSDNode>(Use)->getBasePtr() == Ptr))
+ RealUse = true;
+ }
+ if (!RealUse)
+ return false;
+
+ SDOperand Result;
+ if (isLoad)
+ Result = DAG.getIndexedLoad(SDOperand(N,0), BasePtr, Offset, AM);
+ else
+ Result = DAG.getIndexedStore(SDOperand(N,0), BasePtr, Offset, AM);
+ ++PreIndexedNodes;
+ ++NodesCombined;
+ DOUT << "\nReplacing.4 "; DEBUG(N->dump(&DAG));
+ DOUT << "\nWith: "; DEBUG(Result.Val->dump(&DAG));
+ DOUT << '\n';
+ std::vector<SDNode*> NowDead;
+ if (isLoad) {
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0),
+ &NowDead);
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2),
+ &NowDead);
+ } else {
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1),
+ &NowDead);
+ }
+
+ // Nodes can end up on the worklist more than once. Make sure we do
+ // not process a node that has been replaced.
+ for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
+ removeFromWorkList(NowDead[i]);
+ // Finally, since the node is now dead, remove it from the graph.
+ DAG.DeleteNode(N);
+
+ // Replace the uses of Ptr with uses of the updated base value.
+ DAG.ReplaceAllUsesOfValueWith(Ptr, Result.getValue(isLoad ? 1 : 0),
+ &NowDead);
+ removeFromWorkList(Ptr.Val);
+ for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
+ removeFromWorkList(NowDead[i]);
+ DAG.DeleteNode(Ptr.Val);
+
+ return true;
+}
+
+/// CombineToPostIndexedLoadStore - Try combine a load / store with a
+/// add / sub of the base pointer node into a post-indexed load / store.
+/// The transformation folded the add / subtract into the new indexed
+/// load / store effectively and all of its uses are redirected to the
+/// new load / store.
+bool DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) {
+ if (!AfterLegalize)
+ return false;
+
+ bool isLoad = true;
+ SDOperand Ptr;
+ MVT::ValueType VT;
+ if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
+ if (LD->getAddressingMode() != ISD::UNINDEXED)
+ return false;
+ VT = LD->getLoadedVT();
+ if (!TLI.isIndexedLoadLegal(ISD::POST_INC, VT) &&
+ !TLI.isIndexedLoadLegal(ISD::POST_DEC, VT))
+ return false;
+ Ptr = LD->getBasePtr();
+ } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
+ if (ST->getAddressingMode() != ISD::UNINDEXED)
+ return false;
+ VT = ST->getStoredVT();
+ if (!TLI.isIndexedStoreLegal(ISD::POST_INC, VT) &&
+ !TLI.isIndexedStoreLegal(ISD::POST_DEC, VT))
+ return false;
+ Ptr = ST->getBasePtr();
+ isLoad = false;
+ } else
+ return false;
+
+ if (Ptr.Val->hasOneUse())
+ return false;
+
+ for (SDNode::use_iterator I = Ptr.Val->use_begin(),
+ E = Ptr.Val->use_end(); I != E; ++I) {
+ SDNode *Op = *I;
+ if (Op == N ||
+ (Op->getOpcode() != ISD::ADD && Op->getOpcode() != ISD::SUB))
+ continue;
+
+ SDOperand BasePtr;
+ SDOperand Offset;
+ ISD::MemIndexedMode AM = ISD::UNINDEXED;
+ if (TLI.getPostIndexedAddressParts(N, Op, BasePtr, Offset, AM, DAG)) {
+ if (Ptr == Offset)
+ std::swap(BasePtr, Offset);
+ if (Ptr != BasePtr)
+ continue;
+ // Don't create a indexed load / store with zero offset.
+ if (isa<ConstantSDNode>(Offset) &&
+ cast<ConstantSDNode>(Offset)->getValue() == 0)
+ continue;
+
+ // Try turning it into a post-indexed load / store except when
+ // 1) All uses are load / store ops that use it as base ptr.
+ // 2) Op must be independent of N, i.e. Op is neither a predecessor
+ // nor a successor of N. Otherwise, if Op is folded that would
+ // create a cycle.
+
+ // Check for #1.
+ bool TryNext = false;
+ for (SDNode::use_iterator II = BasePtr.Val->use_begin(),
+ EE = BasePtr.Val->use_end(); II != EE; ++II) {
+ SDNode *Use = *II;
+ if (Use == Ptr.Val)
+ continue;
+
+ // If all the uses are load / store addresses, then don't do the
+ // transformation.
+ if (Use->getOpcode() == ISD::ADD || Use->getOpcode() == ISD::SUB){
+ bool RealUse = false;
+ for (SDNode::use_iterator III = Use->use_begin(),
+ EEE = Use->use_end(); III != EEE; ++III) {
+ SDNode *UseUse = *III;
+ if (!((UseUse->getOpcode() == ISD::LOAD &&
+ cast<LoadSDNode>(UseUse)->getBasePtr().Val == Use) ||
+ (UseUse->getOpcode() == ISD::STORE) &&
+ cast<StoreSDNode>(UseUse)->getBasePtr().Val == Use))
+ RealUse = true;
+ }
+
+ if (!RealUse) {
+ TryNext = true;
+ break;
+ }
+ }
+ }
+ if (TryNext)
+ continue;
+
+ // Check for #2
+ if (!Op->isPredecessor(N) && !N->isPredecessor(Op)) {
+ SDOperand Result = isLoad
+ ? DAG.getIndexedLoad(SDOperand(N,0), BasePtr, Offset, AM)
+ : DAG.getIndexedStore(SDOperand(N,0), BasePtr, Offset, AM);
+ ++PostIndexedNodes;
+ ++NodesCombined;
+ DOUT << "\nReplacing.5 "; DEBUG(N->dump(&DAG));
+ DOUT << "\nWith: "; DEBUG(Result.Val->dump(&DAG));
+ DOUT << '\n';
+ std::vector<SDNode*> NowDead;
+ if (isLoad) {
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0),
+ &NowDead);
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2),
+ &NowDead);
+ } else {
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1),
+ &NowDead);
+ }
+
+ // Nodes can end up on the worklist more than once. Make sure we do
+ // not process a node that has been replaced.
+ for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
+ removeFromWorkList(NowDead[i]);
+ // Finally, since the node is now dead, remove it from the graph.
+ DAG.DeleteNode(N);
+
+ // Replace the uses of Use with uses of the updated base value.
+ DAG.ReplaceAllUsesOfValueWith(SDOperand(Op, 0),
+ Result.getValue(isLoad ? 1 : 0),
+ &NowDead);
+ removeFromWorkList(Op);
+ for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
+ removeFromWorkList(NowDead[i]);
+ DAG.DeleteNode(Op);
+
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+
+SDOperand DAGCombiner::visitLOAD(SDNode *N) {
+ LoadSDNode *LD = cast<LoadSDNode>(N);
+ SDOperand Chain = LD->getChain();
+ SDOperand Ptr = LD->getBasePtr();
+
+ // If load is not volatile and there are no uses of the loaded value (and
+ // the updated indexed value in case of indexed loads), change uses of the
+ // chain value into uses of the chain input (i.e. delete the dead load).
+ if (!LD->isVolatile()) {
+ if (N->getValueType(1) == MVT::Other) {
+ // Unindexed loads.
+ if (N->hasNUsesOfValue(0, 0))
+ return CombineTo(N, DAG.getNode(ISD::UNDEF, N->getValueType(0)), Chain);
+ } else {
+ // Indexed loads.
+ assert(N->getValueType(2) == MVT::Other && "Malformed indexed loads?");
+ if (N->hasNUsesOfValue(0, 0) && N->hasNUsesOfValue(0, 1)) {
+ SDOperand Undef0 = DAG.getNode(ISD::UNDEF, N->getValueType(0));
+ SDOperand Undef1 = DAG.getNode(ISD::UNDEF, N->getValueType(1));
+ SDOperand To[] = { Undef0, Undef1, Chain };
+ return CombineTo(N, To, 3);
+ }
+ }
+ }
+
+ // If this load is directly stored, replace the load value with the stored
+ // value.
+ // TODO: Handle store large -> read small portion.
+ // TODO: Handle TRUNCSTORE/LOADEXT
+ if (LD->getExtensionType() == ISD::NON_EXTLOAD) {
+ if (ISD::isNON_TRUNCStore(Chain.Val)) {
+ StoreSDNode *PrevST = cast<StoreSDNode>(Chain);
+ if (PrevST->getBasePtr() == Ptr &&
+ PrevST->getValue().getValueType() == N->getValueType(0))
+ return CombineTo(N, Chain.getOperand(1), Chain);
+ }
+ }
+
+ if (CombinerAA) {
+ // Walk up chain skipping non-aliasing memory nodes.
+ SDOperand BetterChain = FindBetterChain(N, Chain);
+
+ // If there is a better chain.
if (Chain != BetterChain) {
+ SDOperand ReplLoad;
+
// Replace the chain to void dependency.
- SDOperand ReplLoad = DAG.getLoad(N->getValueType(0), BetterChain, Ptr,
- SrcValue);
+ if (LD->getExtensionType() == ISD::NON_EXTLOAD) {
+ ReplLoad = DAG.getLoad(N->getValueType(0), BetterChain, Ptr,
+ LD->getSrcValue(), LD->getSrcValueOffset(),
+ LD->isVolatile(), LD->getAlignment());
+ } else {
+ ReplLoad = DAG.getExtLoad(LD->getExtensionType(),
+ LD->getValueType(0),
+ BetterChain, Ptr, LD->getSrcValue(),
+ LD->getSrcValueOffset(),
+ LD->getLoadedVT(),
+ LD->isVolatile(),
+ LD->getAlignment());
+ }
- // Create token factor to keep chain around.
+ // Create token factor to keep old chain connected.
SDOperand Token = DAG.getNode(ISD::TokenFactor, MVT::Other,
Chain, ReplLoad.getValue(1));
-
- // Replace uses with load and token factor.
- CombineTo(N, ReplLoad.getValue(0), Token);
-
- return SDOperand(N, 0);
+
+ // Replace uses with load result and token factor. Don't add users
+ // to work list.
+ return CombineTo(N, ReplLoad.getValue(0), Token, false);
}
}
- return SDOperand();
-}
+ // Try transforming N to an indexed load.
+ if (CombineToPreIndexedLoadStore(N) || CombineToPostIndexedLoadStore(N))
+ return SDOperand(N, 0);
-/// visitXEXTLOAD - Handle EXTLOAD/ZEXTLOAD/SEXTLOAD.
-SDOperand DAGCombiner::visitXEXTLOAD(SDNode *N) {
- SDOperand Chain = N->getOperand(0);
- SDOperand Ptr = N->getOperand(1);
- SDOperand SrcValue = N->getOperand(2);
- SDOperand EVT = N->getOperand(3);
-
- // If there are no uses of the loaded value, change uses of the chain value
- // into uses of the chain input (i.e. delete the dead load).
- if (N->hasNUsesOfValue(0, 0))
- return CombineTo(N, DAG.getNode(ISD::UNDEF, N->getValueType(0)), Chain);
-
return SDOperand();
}
SDOperand DAGCombiner::visitSTORE(SDNode *N) {
- SDOperand Chain = N->getOperand(0);
- SDOperand Value = N->getOperand(1);
- SDOperand Ptr = N->getOperand(2);
- SDOperand SrcValue = N->getOperand(3);
-
- // If this is a store that kills a previous store, remove the previous store.
- if (Chain.getOpcode() == ISD::STORE && Chain.getOperand(2) == Ptr &&
- Chain.Val->hasOneUse() /* Avoid introducing DAG cycles */ &&
- // Make sure that these stores are the same value type:
- // FIXME: we really care that the second store is >= size of the first.
- Value.getValueType() == Chain.getOperand(1).getValueType()) {
- // Create a new store of Value that replaces both stores.
- SDNode *PrevStore = Chain.Val;
- if (PrevStore->getOperand(1) == Value) // Same value multiply stored.
- return Chain;
- SDOperand NewStore = DAG.getNode(ISD::STORE, MVT::Other,
- PrevStore->getOperand(0), Value, Ptr,
- SrcValue);
- CombineTo(N, NewStore); // Nuke this store.
- CombineTo(PrevStore, NewStore); // Nuke the previous store.
- return SDOperand(N, 0);
- }
-
- // If this is a store of a bit convert, store the input value.
- // FIXME: This needs to know that the resultant store does not need a
- // higher alignment than the original.
- if (0 && Value.getOpcode() == ISD::BIT_CONVERT) {
- return DAG.getNode(ISD::STORE, MVT::Other, Chain, Value.getOperand(0),
- Ptr, SrcValue);
+ StoreSDNode *ST = cast<StoreSDNode>(N);
+ SDOperand Chain = ST->getChain();
+ SDOperand Value = ST->getValue();
+ SDOperand Ptr = ST->getBasePtr();
+
+ // If this is a store of a bit convert, store the input value if the
+ // resultant store does not need a higher alignment than the original.
+ if (Value.getOpcode() == ISD::BIT_CONVERT && !ST->isTruncatingStore() &&
+ ST->getAddressingMode() == ISD::UNINDEXED) {
+ unsigned Align = ST->getAlignment();
+ MVT::ValueType SVT = Value.getOperand(0).getValueType();
+ unsigned OrigAlign = TLI.getTargetMachine().getTargetData()->
+ getABITypeAlignment(MVT::getTypeForValueType(SVT));
+ if (Align <= OrigAlign && TLI.isOperationLegal(ISD::STORE, SVT))
+ return DAG.getStore(Chain, Value.getOperand(0), Ptr, ST->getSrcValue(),
+ ST->getSrcValueOffset(), ST->isVolatile(), Align);
}
- if (CombinerAA) {
- // If the store ptr is a frame index and the frame index has a use of one
- // and this is a return block, then the store is redundant.
- if (Ptr.hasOneUse() && isa<FrameIndexSDNode>(Ptr) &&
- DAG.getRoot().getOpcode() == ISD::RET) {
- return Chain;
+ // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
+ if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(Value)) {
+ if (Value.getOpcode() != ISD::TargetConstantFP) {
+ SDOperand Tmp;
+ switch (CFP->getValueType(0)) {
+ default: assert(0 && "Unknown FP type");
+ case MVT::f80: // We don't do this for these yet.
+ case MVT::f128:
+ case MVT::ppcf128:
+ break;
+ case MVT::f32:
+ if (!AfterLegalize || TLI.isTypeLegal(MVT::i32)) {
+ Tmp = DAG.getConstant((uint32_t)CFP->getValueAPF().
+ convertToAPInt().getZExtValue(), MVT::i32);
+ return DAG.getStore(Chain, Tmp, Ptr, ST->getSrcValue(),
+ ST->getSrcValueOffset(), ST->isVolatile(),
+ ST->getAlignment());
+ }
+ break;
+ case MVT::f64:
+ if (!AfterLegalize || TLI.isTypeLegal(MVT::i64)) {
+ Tmp = DAG.getConstant(CFP->getValueAPF().convertToAPInt().
+ getZExtValue(), MVT::i64);
+ return DAG.getStore(Chain, Tmp, Ptr, ST->getSrcValue(),
+ ST->getSrcValueOffset(), ST->isVolatile(),
+ ST->getAlignment());
+ } else if (TLI.isTypeLegal(MVT::i32)) {
+ // Many FP stores are not made apparent until after legalize, e.g. for
+ // argument passing. Since this is so common, custom legalize the
+ // 64-bit integer store into two 32-bit stores.
+ uint64_t Val = CFP->getValueAPF().convertToAPInt().getZExtValue();
+ SDOperand Lo = DAG.getConstant(Val & 0xFFFFFFFF, MVT::i32);
+ SDOperand Hi = DAG.getConstant(Val >> 32, MVT::i32);
+ if (!TLI.isLittleEndian()) std::swap(Lo, Hi);
+
+ int SVOffset = ST->getSrcValueOffset();
+ unsigned Alignment = ST->getAlignment();
+ bool isVolatile = ST->isVolatile();
+
+ SDOperand St0 = DAG.getStore(Chain, Lo, Ptr, ST->getSrcValue(),
+ ST->getSrcValueOffset(),
+ isVolatile, ST->getAlignment());
+ Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
+ DAG.getConstant(4, Ptr.getValueType()));
+ SVOffset += 4;
+ Alignment = MinAlign(Alignment, 4U);
+ SDOperand St1 = DAG.getStore(Chain, Hi, Ptr, ST->getSrcValue(),
+ SVOffset, isVolatile, Alignment);
+ return DAG.getNode(ISD::TokenFactor, MVT::Other, St0, St1);
+ }
+ break;
+ }
}
+ }
+ if (CombinerAA) {
// Walk up chain skipping non-aliasing memory nodes.
SDOperand BetterChain = FindBetterChain(N, Chain);
- // If the there is a better chain.
+ // If there is a better chain.
if (Chain != BetterChain) {
- // Replace the chain to void dependency.
- SDOperand ReplStore = DAG.getNode(ISD::STORE, MVT::Other,
- BetterChain, Value, Ptr,
- SrcValue);
+ // Replace the chain to avoid dependency.
+ SDOperand ReplStore;
+ if (ST->isTruncatingStore()) {
+ ReplStore = DAG.getTruncStore(BetterChain, Value, Ptr,
+ ST->getSrcValue(), ST->getSrcValueOffset(), ST->getStoredVT(),
+ ST->isVolatile(), ST->getAlignment());
+ } else {
+ ReplStore = DAG.getStore(BetterChain, Value, Ptr,
+ ST->getSrcValue(), ST->getSrcValueOffset(),
+ ST->isVolatile(), ST->getAlignment());
+ }
+
// Create token to keep both nodes around.
- SDOperand Token = DAG.getNode(ISD::TokenFactor, MVT::Other,
- Chain, ReplStore);
+ SDOperand Token =
+ DAG.getNode(ISD::TokenFactor, MVT::Other, Chain, ReplStore);
+
+ // Don't add users to work list.
+ return CombineTo(N, Token, false);
+ }
+ }
+
+ // Try transforming N to an indexed store.
+ if (CombineToPreIndexedLoadStore(N) || CombineToPostIndexedLoadStore(N))
+ return SDOperand(N, 0);
- // Make sure we merge token factors.
- AddUsersToWorkList(N);
-
- // Old chain needs to be cleaned up.
- AddToWorkList(Chain.Val);
-
- return Token;
+ // FIXME: is there such a thing as a truncating indexed store?
+ if (ST->isTruncatingStore() && ST->getAddressingMode() == ISD::UNINDEXED &&
+ MVT::isInteger(Value.getValueType())) {
+ // See if we can simplify the input to this truncstore with knowledge that
+ // only the low bits are being used. For example:
+ // "truncstore (or (shl x, 8), y), i8" -> "truncstore y, i8"
+ SDOperand Shorter =
+ GetDemandedBits(Value, MVT::getIntVTBitMask(ST->getStoredVT()));
+ AddToWorkList(Value.Val);
+ if (Shorter.Val)
+ return DAG.getTruncStore(Chain, Shorter, Ptr, ST->getSrcValue(),
+ ST->getSrcValueOffset(), ST->getStoredVT(),
+ ST->isVolatile(), ST->getAlignment());
+
+ // Otherwise, see if we can simplify the operation with
+ // SimplifyDemandedBits, which only works if the value has a single use.
+ if (SimplifyDemandedBits(Value, MVT::getIntVTBitMask(ST->getStoredVT())))
+ return SDOperand(N, 0);
+ }
+
+ // If this is a load followed by a store to the same location, then the store
+ // is dead/noop.
+ if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(Value)) {
+ if (Chain.Val == Ld && Ld->getBasePtr() == Ptr &&
+ ST->getAddressingMode() == ISD::UNINDEXED &&
+ ST->getStoredVT() == Ld->getLoadedVT() &&
+ !ST->isVolatile()) {
+ // The store is dead, remove it.
+ return Chain;
}
}
return SDOperand();
}
-SDOperand DAGCombiner::visitVINSERT_VECTOR_ELT(SDNode *N) {
+SDOperand DAGCombiner::visitEXTRACT_VECTOR_ELT(SDNode *N) {
SDOperand InVec = N->getOperand(0);
- SDOperand InVal = N->getOperand(1);
- SDOperand EltNo = N->getOperand(2);
- SDOperand NumElts = N->getOperand(3);
- SDOperand EltType = N->getOperand(4);
-
- // If the invec is a VBUILD_VECTOR and if EltNo is a constant, build a new
- // vector with the inserted element.
- if (InVec.getOpcode() == ISD::VBUILD_VECTOR && isa<ConstantSDNode>(EltNo)) {
+ SDOperand EltNo = N->getOperand(1);
+
+ // (vextract (v4f32 s2v (f32 load $addr)), 0) -> (f32 load $addr)
+ // (vextract (v4i32 bc (v4f32 s2v (f32 load $addr))), 0) -> (i32 load $addr)
+ if (isa<ConstantSDNode>(EltNo)) {
unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue();
- SmallVector<SDOperand, 8> Ops(InVec.Val->op_begin(), InVec.Val->op_end());
- if (Elt < Ops.size()-2)
- Ops[Elt] = InVal;
- return DAG.getNode(ISD::VBUILD_VECTOR, InVec.getValueType(),
- &Ops[0], Ops.size());
+ bool NewLoad = false;
+ if (Elt == 0) {
+ MVT::ValueType VT = InVec.getValueType();
+ MVT::ValueType EVT = MVT::getVectorElementType(VT);
+ MVT::ValueType LVT = EVT;
+ unsigned NumElts = MVT::getVectorNumElements(VT);
+ if (InVec.getOpcode() == ISD::BIT_CONVERT) {
+ MVT::ValueType BCVT = InVec.getOperand(0).getValueType();
+ if (!MVT::isVector(BCVT) ||
+ NumElts != MVT::getVectorNumElements(BCVT))
+ return SDOperand();
+ InVec = InVec.getOperand(0);
+ EVT = MVT::getVectorElementType(BCVT);
+ NewLoad = true;
+ }
+ if (InVec.getOpcode() == ISD::SCALAR_TO_VECTOR &&
+ InVec.getOperand(0).getValueType() == EVT &&
+ ISD::isNormalLoad(InVec.getOperand(0).Val) &&
+ InVec.getOperand(0).hasOneUse()) {
+ LoadSDNode *LN0 = cast<LoadSDNode>(InVec.getOperand(0));
+ unsigned Align = LN0->getAlignment();
+ if (NewLoad) {
+ // Check the resultant load doesn't need a higher alignment than the
+ // original load.
+ unsigned NewAlign = TLI.getTargetMachine().getTargetData()->
+ getABITypeAlignment(MVT::getTypeForValueType(LVT));
+ if (!TLI.isOperationLegal(ISD::LOAD, LVT) || NewAlign > Align)
+ return SDOperand();
+ Align = NewAlign;
+ }
+
+ return DAG.getLoad(LVT, LN0->getChain(), LN0->getBasePtr(),
+ LN0->getSrcValue(), LN0->getSrcValueOffset(),
+ LN0->isVolatile(), Align);
+ }
+ }
}
-
return SDOperand();
}
+
-SDOperand DAGCombiner::visitVBUILD_VECTOR(SDNode *N) {
- unsigned NumInScalars = N->getNumOperands()-2;
- SDOperand NumElts = N->getOperand(NumInScalars);
- SDOperand EltType = N->getOperand(NumInScalars+1);
+SDOperand DAGCombiner::visitBUILD_VECTOR(SDNode *N) {
+ unsigned NumInScalars = N->getNumOperands();
+ MVT::ValueType VT = N->getValueType(0);
+ unsigned NumElts = MVT::getVectorNumElements(VT);
+ MVT::ValueType EltType = MVT::getVectorElementType(VT);
- // Check to see if this is a VBUILD_VECTOR of a bunch of VEXTRACT_VECTOR_ELT
- // operations. If so, and if the EXTRACT_ELT vector inputs come from at most
- // two distinct vectors, turn this into a shuffle node.
+ // Check to see if this is a BUILD_VECTOR of a bunch of EXTRACT_VECTOR_ELT
+ // operations. If so, and if the EXTRACT_VECTOR_ELT vector inputs come from
+ // at most two distinct vectors, turn this into a shuffle node.
SDOperand VecIn1, VecIn2;
for (unsigned i = 0; i != NumInScalars; ++i) {
// Ignore undef inputs.
if (N->getOperand(i).getOpcode() == ISD::UNDEF) continue;
- // If this input is something other than a VEXTRACT_VECTOR_ELT with a
+ // If this input is something other than a EXTRACT_VECTOR_ELT with a
// constant index, bail out.
- if (N->getOperand(i).getOpcode() != ISD::VEXTRACT_VECTOR_ELT ||
+ if (N->getOperand(i).getOpcode() != ISD::EXTRACT_VECTOR_ELT ||
!isa<ConstantSDNode>(N->getOperand(i).getOperand(1))) {
VecIn1 = VecIn2 = SDOperand(0, 0);
break;
}
- // If the input vector type disagrees with the result of the vbuild_vector,
+ // If the input vector type disagrees with the result of the build_vector,
// we can't make a shuffle.
SDOperand ExtractedFromVec = N->getOperand(i).getOperand(0);
- if (*(ExtractedFromVec.Val->op_end()-2) != NumElts ||
- *(ExtractedFromVec.Val->op_end()-1) != EltType) {
+ if (ExtractedFromVec.getValueType() != VT) {
VecIn1 = VecIn2 = SDOperand(0, 0);
break;
}
SmallVector<SDOperand, 8> BuildVecIndices;
for (unsigned i = 0; i != NumInScalars; ++i) {
if (N->getOperand(i).getOpcode() == ISD::UNDEF) {
- BuildVecIndices.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
+ BuildVecIndices.push_back(DAG.getNode(ISD::UNDEF, TLI.getPointerTy()));
continue;
}
// Otherwise, use InIdx + VecSize
unsigned Idx = cast<ConstantSDNode>(Extract.getOperand(1))->getValue();
- BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars, MVT::i32));
+ BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars,
+ TLI.getPointerTy()));
}
// Add count and size info.
- BuildVecIndices.push_back(NumElts);
- BuildVecIndices.push_back(DAG.getValueType(MVT::i32));
+ MVT::ValueType BuildVecVT =
+ MVT::getVectorType(TLI.getPointerTy(), NumElts);
- // Return the new VVECTOR_SHUFFLE node.
+ // Return the new VECTOR_SHUFFLE node.
SDOperand Ops[5];
Ops[0] = VecIn1;
if (VecIn2.Val) {
Ops[1] = VecIn2;
} else {
- // Use an undef vbuild_vector as input for the second operand.
+ // Use an undef build_vector as input for the second operand.
std::vector<SDOperand> UnOps(NumInScalars,
DAG.getNode(ISD::UNDEF,
- cast<VTSDNode>(EltType)->getVT()));
- UnOps.push_back(NumElts);
- UnOps.push_back(EltType);
- Ops[1] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
+ EltType));
+ Ops[1] = DAG.getNode(ISD::BUILD_VECTOR, VT,
&UnOps[0], UnOps.size());
AddToWorkList(Ops[1].Val);
}
- Ops[2] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
+ Ops[2] = DAG.getNode(ISD::BUILD_VECTOR, BuildVecVT,
&BuildVecIndices[0], BuildVecIndices.size());
- Ops[3] = NumElts;
- Ops[4] = EltType;
- return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, Ops, 5);
+ return DAG.getNode(ISD::VECTOR_SHUFFLE, VT, Ops, 3);
}
return SDOperand();
}
+SDOperand DAGCombiner::visitCONCAT_VECTORS(SDNode *N) {
+ // TODO: Check to see if this is a CONCAT_VECTORS of a bunch of
+ // EXTRACT_SUBVECTOR operations. If so, and if the EXTRACT_SUBVECTOR vector
+ // inputs come from at most two distinct vectors, turn this into a shuffle
+ // node.
+
+ // If we only have one input vector, we don't need to do any concatenation.
+ if (N->getNumOperands() == 1) {
+ return N->getOperand(0);
+ }
+
+ return SDOperand();
+}
+
SDOperand DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) {
SDOperand ShufMask = N->getOperand(2);
unsigned NumElts = ShufMask.getNumOperands();
// all scalar elements the same.
if (isSplat) {
SDNode *V = N0.Val;
- if (V->getOpcode() == ISD::BIT_CONVERT)
- V = V->getOperand(0).Val;
+
+ // If this is a bit convert that changes the element type of the vector but
+ // not the number of vector elements, look through it. Be careful not to
+ // look though conversions that change things like v4f32 to v2f64.
+ if (V->getOpcode() == ISD::BIT_CONVERT) {
+ SDOperand ConvInput = V->getOperand(0);
+ if (MVT::getVectorNumElements(ConvInput.getValueType()) == NumElts)
+ V = ConvInput.Val;
+ }
+
if (V->getOpcode() == ISD::BUILD_VECTOR) {
- unsigned NumElems = V->getNumOperands()-2;
+ unsigned NumElems = V->getNumOperands();
if (NumElems > BaseIdx) {
SDOperand Base;
bool AllSame = true;
if (!Base.Val)
return N0;
for (unsigned i = 0; i != NumElems; ++i) {
- if (V->getOperand(i).getOpcode() != ISD::UNDEF &&
- V->getOperand(i) != Base) {
+ if (V->getOperand(i) != Base) {
AllSame = false;
break;
}
// If it is a unary or the LHS and the RHS are the same node, turn the RHS
// into an undef.
if (isUnary || N0 == N1) {
- if (N0.getOpcode() == ISD::UNDEF)
- return DAG.getNode(ISD::UNDEF, N->getValueType(0));
// Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the
// first operand.
SmallVector<SDOperand, 8> MappedOps;
- for (unsigned i = 0, e = ShufMask.getNumOperands(); i != e; ++i) {
+ for (unsigned i = 0; i != NumElts; ++i) {
if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF ||
cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) {
MappedOps.push_back(ShufMask.getOperand(i));
} else {
unsigned NewIdx =
- cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts;
+ cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts;
MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32));
}
}
&MappedOps[0], MappedOps.size());
AddToWorkList(ShufMask.Val);
return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getValueType(0),
- N0,
+ N0,
DAG.getNode(ISD::UNDEF, N->getValueType(0)),
ShufMask);
}
return SDOperand();
}
-SDOperand DAGCombiner::visitVVECTOR_SHUFFLE(SDNode *N) {
- SDOperand ShufMask = N->getOperand(2);
- unsigned NumElts = ShufMask.getNumOperands()-2;
-
- // If the shuffle mask is an identity operation on the LHS, return the LHS.
- bool isIdentity = true;
- for (unsigned i = 0; i != NumElts; ++i) {
- if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
- cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) {
- isIdentity = false;
- break;
- }
- }
- if (isIdentity) return N->getOperand(0);
-
- // If the shuffle mask is an identity operation on the RHS, return the RHS.
- isIdentity = true;
- for (unsigned i = 0; i != NumElts; ++i) {
- if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
- cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) {
- isIdentity = false;
- break;
- }
- }
- if (isIdentity) return N->getOperand(1);
-
- // Check if the shuffle is a unary shuffle, i.e. one of the vectors is not
- // needed at all.
- bool isUnary = true;
- bool isSplat = true;
- int VecNum = -1;
- unsigned BaseIdx = 0;
- for (unsigned i = 0; i != NumElts; ++i)
- if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF) {
- unsigned Idx = cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue();
- int V = (Idx < NumElts) ? 0 : 1;
- if (VecNum == -1) {
- VecNum = V;
- BaseIdx = Idx;
- } else {
- if (BaseIdx != Idx)
- isSplat = false;
- if (VecNum != V) {
- isUnary = false;
- break;
- }
- }
- }
-
- SDOperand N0 = N->getOperand(0);
- SDOperand N1 = N->getOperand(1);
- // Normalize unary shuffle so the RHS is undef.
- if (isUnary && VecNum == 1)
- std::swap(N0, N1);
-
- // If it is a splat, check if the argument vector is a build_vector with
- // all scalar elements the same.
- if (isSplat) {
- SDNode *V = N0.Val;
- if (V->getOpcode() == ISD::VBIT_CONVERT)
- V = V->getOperand(0).Val;
- if (V->getOpcode() == ISD::VBUILD_VECTOR) {
- unsigned NumElems = V->getNumOperands()-2;
- if (NumElems > BaseIdx) {
- SDOperand Base;
- bool AllSame = true;
- for (unsigned i = 0; i != NumElems; ++i) {
- if (V->getOperand(i).getOpcode() != ISD::UNDEF) {
- Base = V->getOperand(i);
- break;
- }
- }
- // Splat of <u, u, u, u>, return <u, u, u, u>
- if (!Base.Val)
- return N0;
- for (unsigned i = 0; i != NumElems; ++i) {
- if (V->getOperand(i).getOpcode() != ISD::UNDEF &&
- V->getOperand(i) != Base) {
- AllSame = false;
- break;
- }
- }
- // Splat of <x, x, x, x>, return <x, x, x, x>
- if (AllSame)
- return N0;
- }
- }
- }
-
- // If it is a unary or the LHS and the RHS are the same node, turn the RHS
- // into an undef.
- if (isUnary || N0 == N1) {
- // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the
- // first operand.
- SmallVector<SDOperand, 8> MappedOps;
- for (unsigned i = 0; i != NumElts; ++i) {
- if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF ||
- cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) {
- MappedOps.push_back(ShufMask.getOperand(i));
- } else {
- unsigned NewIdx =
- cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts;
- MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32));
- }
- }
- // Add the type/#elts values.
- MappedOps.push_back(ShufMask.getOperand(NumElts));
- MappedOps.push_back(ShufMask.getOperand(NumElts+1));
-
- ShufMask = DAG.getNode(ISD::VBUILD_VECTOR, ShufMask.getValueType(),
- &MappedOps[0], MappedOps.size());
- AddToWorkList(ShufMask.Val);
-
- // Build the undef vector.
- SDOperand UDVal = DAG.getNode(ISD::UNDEF, MappedOps[0].getValueType());
- for (unsigned i = 0; i != NumElts; ++i)
- MappedOps[i] = UDVal;
- MappedOps[NumElts ] = *(N0.Val->op_end()-2);
- MappedOps[NumElts+1] = *(N0.Val->op_end()-1);
- UDVal = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
- &MappedOps[0], MappedOps.size());
-
- return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
- N0, UDVal, ShufMask,
- MappedOps[NumElts], MappedOps[NumElts+1]);
- }
-
- return SDOperand();
-}
-
/// XformToShuffleWithZero - Returns a vector_shuffle if it able to transform
-/// a VAND to a vector_shuffle with the destination vector and a zero vector.
-/// e.g. VAND V, <0xffffffff, 0, 0xffffffff, 0>. ==>
+/// an AND to a vector_shuffle with the destination vector and a zero vector.
+/// e.g. AND V, <0xffffffff, 0, 0xffffffff, 0>. ==>
/// vector_shuffle V, Zero, <0, 4, 2, 4>
SDOperand DAGCombiner::XformToShuffleWithZero(SDNode *N) {
SDOperand LHS = N->getOperand(0);
SDOperand RHS = N->getOperand(1);
- if (N->getOpcode() == ISD::VAND) {
- SDOperand DstVecSize = *(LHS.Val->op_end()-2);
- SDOperand DstVecEVT = *(LHS.Val->op_end()-1);
- if (RHS.getOpcode() == ISD::VBIT_CONVERT)
+ if (N->getOpcode() == ISD::AND) {
+ if (RHS.getOpcode() == ISD::BIT_CONVERT)
RHS = RHS.getOperand(0);
- if (RHS.getOpcode() == ISD::VBUILD_VECTOR) {
+ if (RHS.getOpcode() == ISD::BUILD_VECTOR) {
std::vector<SDOperand> IdxOps;
unsigned NumOps = RHS.getNumOperands();
- unsigned NumElts = NumOps-2;
- MVT::ValueType EVT = cast<VTSDNode>(RHS.getOperand(NumOps-1))->getVT();
+ unsigned NumElts = NumOps;
+ MVT::ValueType EVT = MVT::getVectorElementType(RHS.getValueType());
for (unsigned i = 0; i != NumElts; ++i) {
SDOperand Elt = RHS.getOperand(i);
if (!isa<ConstantSDNode>(Elt))
if (!TLI.isVectorClearMaskLegal(IdxOps, EVT, DAG))
return SDOperand();
- // Return the new VVECTOR_SHUFFLE node.
- SDOperand NumEltsNode = DAG.getConstant(NumElts, MVT::i32);
- SDOperand EVTNode = DAG.getValueType(EVT);
+ // Return the new VECTOR_SHUFFLE node.
+ MVT::ValueType VT = MVT::getVectorType(EVT, NumElts);
std::vector<SDOperand> Ops;
- LHS = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, LHS, NumEltsNode,
- EVTNode);
+ LHS = DAG.getNode(ISD::BIT_CONVERT, VT, LHS);
Ops.push_back(LHS);
AddToWorkList(LHS.Val);
std::vector<SDOperand> ZeroOps(NumElts, DAG.getConstant(0, EVT));
- ZeroOps.push_back(NumEltsNode);
- ZeroOps.push_back(EVTNode);
- Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
+ Ops.push_back(DAG.getNode(ISD::BUILD_VECTOR, VT,
&ZeroOps[0], ZeroOps.size()));
- IdxOps.push_back(NumEltsNode);
- IdxOps.push_back(EVTNode);
- Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
+ Ops.push_back(DAG.getNode(ISD::BUILD_VECTOR, VT,
&IdxOps[0], IdxOps.size()));
- Ops.push_back(NumEltsNode);
- Ops.push_back(EVTNode);
- SDOperand Result = DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
+ SDOperand Result = DAG.getNode(ISD::VECTOR_SHUFFLE, VT,
&Ops[0], Ops.size());
- if (NumEltsNode != DstVecSize || EVTNode != DstVecEVT) {
- Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result,
- DstVecSize, DstVecEVT);
+ if (VT != LHS.getValueType()) {
+ Result = DAG.getNode(ISD::BIT_CONVERT, LHS.getValueType(), Result);
}
return Result;
}
return SDOperand();
}
-/// visitVBinOp - Visit a binary vector operation, like VADD. IntOp indicates
-/// the scalar operation of the vop if it is operating on an integer vector
-/// (e.g. ADD) and FPOp indicates the FP version (e.g. FADD).
-SDOperand DAGCombiner::visitVBinOp(SDNode *N, ISD::NodeType IntOp,
- ISD::NodeType FPOp) {
- MVT::ValueType EltType = cast<VTSDNode>(*(N->op_end()-1))->getVT();
- ISD::NodeType ScalarOp = MVT::isInteger(EltType) ? IntOp : FPOp;
+/// SimplifyVBinOp - Visit a binary vector operation, like ADD.
+SDOperand DAGCombiner::SimplifyVBinOp(SDNode *N) {
+ // After legalize, the target may be depending on adds and other
+ // binary ops to provide legal ways to construct constants or other
+ // things. Simplifying them may result in a loss of legality.
+ if (AfterLegalize) return SDOperand();
+
+ MVT::ValueType VT = N->getValueType(0);
+ assert(MVT::isVector(VT) && "SimplifyVBinOp only works on vectors!");
+
+ MVT::ValueType EltType = MVT::getVectorElementType(VT);
SDOperand LHS = N->getOperand(0);
SDOperand RHS = N->getOperand(1);
SDOperand Shuffle = XformToShuffleWithZero(N);
if (Shuffle.Val) return Shuffle;
- // If the LHS and RHS are VBUILD_VECTOR nodes, see if we can constant fold
+ // If the LHS and RHS are BUILD_VECTOR nodes, see if we can constant fold
// this operation.
- if (LHS.getOpcode() == ISD::VBUILD_VECTOR &&
- RHS.getOpcode() == ISD::VBUILD_VECTOR) {
+ if (LHS.getOpcode() == ISD::BUILD_VECTOR &&
+ RHS.getOpcode() == ISD::BUILD_VECTOR) {
SmallVector<SDOperand, 8> Ops;
- for (unsigned i = 0, e = LHS.getNumOperands()-2; i != e; ++i) {
+ for (unsigned i = 0, e = LHS.getNumOperands(); i != e; ++i) {
SDOperand LHSOp = LHS.getOperand(i);
SDOperand RHSOp = RHS.getOperand(i);
// If these two elements can't be folded, bail out.
RHSOp.getOpcode() != ISD::ConstantFP))
break;
// Can't fold divide by zero.
- if (N->getOpcode() == ISD::VSDIV || N->getOpcode() == ISD::VUDIV) {
+ if (N->getOpcode() == ISD::SDIV || N->getOpcode() == ISD::UDIV ||
+ N->getOpcode() == ISD::FDIV) {
if ((RHSOp.getOpcode() == ISD::Constant &&
cast<ConstantSDNode>(RHSOp.Val)->isNullValue()) ||
(RHSOp.getOpcode() == ISD::ConstantFP &&
- !cast<ConstantFPSDNode>(RHSOp.Val)->getValue()))
+ cast<ConstantFPSDNode>(RHSOp.Val)->getValueAPF().isZero()))
break;
}
- Ops.push_back(DAG.getNode(ScalarOp, EltType, LHSOp, RHSOp));
+ Ops.push_back(DAG.getNode(N->getOpcode(), EltType, LHSOp, RHSOp));
AddToWorkList(Ops.back().Val);
assert((Ops.back().getOpcode() == ISD::UNDEF ||
Ops.back().getOpcode() == ISD::Constant ||
"Scalar binop didn't fold!");
}
- if (Ops.size() == LHS.getNumOperands()-2) {
- Ops.push_back(*(LHS.Val->op_end()-2));
- Ops.push_back(*(LHS.Val->op_end()-1));
- return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
+ if (Ops.size() == LHS.getNumOperands()) {
+ MVT::ValueType VT = LHS.getValueType();
+ return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
}
}
// If this is a select from two identical things, try to pull the operation
// through the select.
if (LHS.getOpcode() == RHS.getOpcode() && LHS.hasOneUse() && RHS.hasOneUse()){
-#if 0
- std::cerr << "SELECT: ["; LHS.Val->dump();
- std::cerr << "] ["; RHS.Val->dump();
- std::cerr << "]\n";
-#endif
-
// If this is a load and the token chain is identical, replace the select
// of two loads with a load through a select of the address to load from.
// This triggers in things like "select bool X, 10.0, 123.0" after the FP
// constants have been dropped into the constant pool.
- if ((LHS.getOpcode() == ISD::LOAD ||
- LHS.getOpcode() == ISD::EXTLOAD ||
- LHS.getOpcode() == ISD::ZEXTLOAD ||
- LHS.getOpcode() == ISD::SEXTLOAD) &&
+ if (LHS.getOpcode() == ISD::LOAD &&
// Token chains must be identical.
- LHS.getOperand(0) == RHS.getOperand(0) &&
- // If this is an EXTLOAD, the VT's must match.
- (LHS.getOpcode() == ISD::LOAD ||
- LHS.getOperand(3) == RHS.getOperand(3))) {
- // FIXME: this conflates two src values, discarding one. This is not
- // the right thing to do, but nothing uses srcvalues now. When they do,
- // turn SrcValue into a list of locations.
- SDOperand Addr;
- if (TheSelect->getOpcode() == ISD::SELECT)
- Addr = DAG.getNode(ISD::SELECT, LHS.getOperand(1).getValueType(),
- TheSelect->getOperand(0), LHS.getOperand(1),
- RHS.getOperand(1));
- else
- Addr = DAG.getNode(ISD::SELECT_CC, LHS.getOperand(1).getValueType(),
- TheSelect->getOperand(0),
- TheSelect->getOperand(1),
- LHS.getOperand(1), RHS.getOperand(1),
- TheSelect->getOperand(4));
-
- SDOperand Load;
- if (LHS.getOpcode() == ISD::LOAD)
- Load = DAG.getLoad(TheSelect->getValueType(0), LHS.getOperand(0),
- Addr, LHS.getOperand(2));
- else
- Load = DAG.getExtLoad(LHS.getOpcode(), TheSelect->getValueType(0),
- LHS.getOperand(0), Addr, LHS.getOperand(2),
- cast<VTSDNode>(LHS.getOperand(3))->getVT());
- // Users of the select now use the result of the load.
- CombineTo(TheSelect, Load);
-
- // Users of the old loads now use the new load's chain. We know the
- // old-load value is dead now.
- CombineTo(LHS.Val, Load.getValue(0), Load.getValue(1));
- CombineTo(RHS.Val, Load.getValue(0), Load.getValue(1));
- return true;
+ LHS.getOperand(0) == RHS.getOperand(0)) {
+ LoadSDNode *LLD = cast<LoadSDNode>(LHS);
+ LoadSDNode *RLD = cast<LoadSDNode>(RHS);
+
+ // If this is an EXTLOAD, the VT's must match.
+ if (LLD->getLoadedVT() == RLD->getLoadedVT()) {
+ // FIXME: this conflates two src values, discarding one. This is not
+ // the right thing to do, but nothing uses srcvalues now. When they do,
+ // turn SrcValue into a list of locations.
+ SDOperand Addr;
+ if (TheSelect->getOpcode() == ISD::SELECT) {
+ // Check that the condition doesn't reach either load. If so, folding
+ // this will induce a cycle into the DAG.
+ if (!LLD->isPredecessor(TheSelect->getOperand(0).Val) &&
+ !RLD->isPredecessor(TheSelect->getOperand(0).Val)) {
+ Addr = DAG.getNode(ISD::SELECT, LLD->getBasePtr().getValueType(),
+ TheSelect->getOperand(0), LLD->getBasePtr(),
+ RLD->getBasePtr());
+ }
+ } else {
+ // Check that the condition doesn't reach either load. If so, folding
+ // this will induce a cycle into the DAG.
+ if (!LLD->isPredecessor(TheSelect->getOperand(0).Val) &&
+ !RLD->isPredecessor(TheSelect->getOperand(0).Val) &&
+ !LLD->isPredecessor(TheSelect->getOperand(1).Val) &&
+ !RLD->isPredecessor(TheSelect->getOperand(1).Val)) {
+ Addr = DAG.getNode(ISD::SELECT_CC, LLD->getBasePtr().getValueType(),
+ TheSelect->getOperand(0),
+ TheSelect->getOperand(1),
+ LLD->getBasePtr(), RLD->getBasePtr(),
+ TheSelect->getOperand(4));
+ }
+ }
+
+ if (Addr.Val) {
+ SDOperand Load;
+ if (LLD->getExtensionType() == ISD::NON_EXTLOAD)
+ Load = DAG.getLoad(TheSelect->getValueType(0), LLD->getChain(),
+ Addr,LLD->getSrcValue(),
+ LLD->getSrcValueOffset(),
+ LLD->isVolatile(),
+ LLD->getAlignment());
+ else {
+ Load = DAG.getExtLoad(LLD->getExtensionType(),
+ TheSelect->getValueType(0),
+ LLD->getChain(), Addr, LLD->getSrcValue(),
+ LLD->getSrcValueOffset(),
+ LLD->getLoadedVT(),
+ LLD->isVolatile(),
+ LLD->getAlignment());
+ }
+ // Users of the select now use the result of the load.
+ CombineTo(TheSelect, Load);
+
+ // Users of the old loads now use the new load's chain. We know the
+ // old-load value is dead now.
+ CombineTo(LHS.Val, Load.getValue(0), Load.getValue(1));
+ CombineTo(RHS.Val, Load.getValue(0), Load.getValue(1));
+ return true;
+ }
+ }
}
}
SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1,
SDOperand N2, SDOperand N3,
- ISD::CondCode CC) {
+ ISD::CondCode CC, bool NotExtCompare) {
MVT::ValueType VT = N2.getValueType();
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
// Determine if the condition we're dealing with is constant
SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
+ if (SCC.Val) AddToWorkList(SCC.Val);
ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
// fold select_cc true, x, y -> x
// Check to see if we can simplify the select into an fabs node
if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) {
// Allow either -0.0 or 0.0
- if (CFP->getValue() == 0.0) {
+ if (CFP->getValueAPF().isZero()) {
// select (setg[te] X, +/-0.0), X, fneg(X) -> fabs
if ((CC == ISD::SETGE || CC == ISD::SETGT) &&
N0 == N2 && N3.getOpcode() == ISD::FNEG &&
// fold select C, 16, 0 -> shl C, 4
if (N2C && N3C && N3C->isNullValue() && isPowerOf2_64(N2C->getValue()) &&
TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) {
+
+ // If the caller doesn't want us to simplify this into a zext of a compare,
+ // don't do it.
+ if (NotExtCompare && N2C->getValue() == 1)
+ return SDOperand();
+
// Get a SetCC of the condition
// FIXME: Should probably make sure that setcc is legal if we ever have a
// target where it isn't.
// cast from setcc result type to select result type
if (AfterLegalize) {
SCC = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC);
- Temp = DAG.getZeroExtendInReg(SCC, N2.getValueType());
+ if (N2.getValueType() < SCC.getValueType())
+ Temp = DAG.getZeroExtendInReg(SCC, N2.getValueType());
+ else
+ Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC);
} else {
SCC = DAG.getSetCC(MVT::i1, N0, N1, CC);
Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC);
}
AddToWorkList(SCC.Val);
AddToWorkList(Temp.Val);
+
+ if (N2C->getValue() == 1)
+ return Temp;
// shl setcc result by log2 n2c
return DAG.getNode(ISD::SHL, N2.getValueType(), Temp,
DAG.getConstant(Log2_64(N2C->getValue()),
// Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X ->
// Y = sra (X, size(X)-1); xor (add (X, Y), Y)
if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) &&
- N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) {
- if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) {
+ N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1) &&
+ N2.getOperand(0) == N1 && MVT::isInteger(N0.getValueType())) {
+ MVT::ValueType XType = N0.getValueType();
+ SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
+ DAG.getConstant(MVT::getSizeInBits(XType)-1,
+ TLI.getShiftAmountTy()));
+ SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift);
+ AddToWorkList(Shift.Val);
+ AddToWorkList(Add.Val);
+ return DAG.getNode(ISD::XOR, XType, Add, Shift);
+ }
+ // Check to see if this is an integer abs. select_cc setgt X, -1, X, -X ->
+ // Y = sra (X, size(X)-1); xor (add (X, Y), Y)
+ if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT &&
+ N0 == N2 && N3.getOpcode() == ISD::SUB && N0 == N3.getOperand(1)) {
+ if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N3.getOperand(0))) {
MVT::ValueType XType = N0.getValueType();
if (SubC->isNullValue() && MVT::isInteger(XType)) {
SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
DAG.getConstant(MVT::getSizeInBits(XType)-1,
- TLI.getShiftAmountTy()));
+ TLI.getShiftAmountTy()));
SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift);
AddToWorkList(Shift.Val);
AddToWorkList(Add.Val);
}
}
}
-
+
return SDOperand();
}
+/// SimplifySetCC - This is a stub for TargetLowering::SimplifySetCC.
SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0,
SDOperand N1, ISD::CondCode Cond,
bool foldBooleans) {
- // These setcc operations always fold.
- switch (Cond) {
- default: break;
- case ISD::SETFALSE:
- case ISD::SETFALSE2: return DAG.getConstant(0, VT);
- case ISD::SETTRUE:
- case ISD::SETTRUE2: return DAG.getConstant(1, VT);
- }
-
- if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
- uint64_t C1 = N1C->getValue();
- if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val)) {
- uint64_t C0 = N0C->getValue();
-
- // Sign extend the operands if required
- if (ISD::isSignedIntSetCC(Cond)) {
- C0 = N0C->getSignExtended();
- C1 = N1C->getSignExtended();
- }
-
- switch (Cond) {
- default: assert(0 && "Unknown integer setcc!");
- case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT);
- case ISD::SETNE: return DAG.getConstant(C0 != C1, VT);
- case ISD::SETULT: return DAG.getConstant(C0 < C1, VT);
- case ISD::SETUGT: return DAG.getConstant(C0 > C1, VT);
- case ISD::SETULE: return DAG.getConstant(C0 <= C1, VT);
- case ISD::SETUGE: return DAG.getConstant(C0 >= C1, VT);
- case ISD::SETLT: return DAG.getConstant((int64_t)C0 < (int64_t)C1, VT);
- case ISD::SETGT: return DAG.getConstant((int64_t)C0 > (int64_t)C1, VT);
- case ISD::SETLE: return DAG.getConstant((int64_t)C0 <= (int64_t)C1, VT);
- case ISD::SETGE: return DAG.getConstant((int64_t)C0 >= (int64_t)C1, VT);
- }
- } else {
- // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
- // equality comparison, then we're just comparing whether X itself is
- // zero.
- if (N0.getOpcode() == ISD::SRL && (C1 == 0 || C1 == 1) &&
- N0.getOperand(0).getOpcode() == ISD::CTLZ &&
- N0.getOperand(1).getOpcode() == ISD::Constant) {
- unsigned ShAmt = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
- if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
- ShAmt == Log2_32(MVT::getSizeInBits(N0.getValueType()))) {
- if ((C1 == 0) == (Cond == ISD::SETEQ)) {
- // (srl (ctlz x), 5) == 0 -> X != 0
- // (srl (ctlz x), 5) != 1 -> X != 0
- Cond = ISD::SETNE;
- } else {
- // (srl (ctlz x), 5) != 0 -> X == 0
- // (srl (ctlz x), 5) == 1 -> X == 0
- Cond = ISD::SETEQ;
- }
- SDOperand Zero = DAG.getConstant(0, N0.getValueType());
- return DAG.getSetCC(VT, N0.getOperand(0).getOperand(0),
- Zero, Cond);
- }
- }
-
- // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
- if (N0.getOpcode() == ISD::ZERO_EXTEND) {
- unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType());
-
- // If the comparison constant has bits in the upper part, the
- // zero-extended value could never match.
- if (C1 & (~0ULL << InSize)) {
- unsigned VSize = MVT::getSizeInBits(N0.getValueType());
- switch (Cond) {
- case ISD::SETUGT:
- case ISD::SETUGE:
- case ISD::SETEQ: return DAG.getConstant(0, VT);
- case ISD::SETULT:
- case ISD::SETULE:
- case ISD::SETNE: return DAG.getConstant(1, VT);
- case ISD::SETGT:
- case ISD::SETGE:
- // True if the sign bit of C1 is set.
- return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT);
- case ISD::SETLT:
- case ISD::SETLE:
- // True if the sign bit of C1 isn't set.
- return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT);
- default:
- break;
- }
- }
-
- // Otherwise, we can perform the comparison with the low bits.
- switch (Cond) {
- case ISD::SETEQ:
- case ISD::SETNE:
- case ISD::SETUGT:
- case ISD::SETUGE:
- case ISD::SETULT:
- case ISD::SETULE:
- return DAG.getSetCC(VT, N0.getOperand(0),
- DAG.getConstant(C1, N0.getOperand(0).getValueType()),
- Cond);
- default:
- break; // todo, be more careful with signed comparisons
- }
- } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
- (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
- MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
- unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
- MVT::ValueType ExtDstTy = N0.getValueType();
- unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
-
- // If the extended part has any inconsistent bits, it cannot ever
- // compare equal. In other words, they have to be all ones or all
- // zeros.
- uint64_t ExtBits =
- (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
- if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits)
- return DAG.getConstant(Cond == ISD::SETNE, VT);
-
- SDOperand ZextOp;
- MVT::ValueType Op0Ty = N0.getOperand(0).getValueType();
- if (Op0Ty == ExtSrcTy) {
- ZextOp = N0.getOperand(0);
- } else {
- int64_t Imm = ~0ULL >> (64-ExtSrcTyBits);
- ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0),
- DAG.getConstant(Imm, Op0Ty));
- }
- AddToWorkList(ZextOp.Val);
- // Otherwise, make this a use of a zext.
- return DAG.getSetCC(VT, ZextOp,
- DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)),
- ExtDstTy),
- Cond);
- } else if ((N1C->getValue() == 0 || N1C->getValue() == 1) &&
- (Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
- (N0.getOpcode() == ISD::XOR ||
- (N0.getOpcode() == ISD::AND &&
- N0.getOperand(0).getOpcode() == ISD::XOR &&
- N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
- isa<ConstantSDNode>(N0.getOperand(1)) &&
- cast<ConstantSDNode>(N0.getOperand(1))->getValue() == 1) {
- // If this is (X^1) == 0/1, swap the RHS and eliminate the xor. We can
- // only do this if the top bits are known zero.
- if (TLI.MaskedValueIsZero(N1,
- MVT::getIntVTBitMask(N0.getValueType())-1)) {
- // Okay, get the un-inverted input value.
- SDOperand Val;
- if (N0.getOpcode() == ISD::XOR)
- Val = N0.getOperand(0);
- else {
- assert(N0.getOpcode() == ISD::AND &&
- N0.getOperand(0).getOpcode() == ISD::XOR);
- // ((X^1)&1)^1 -> X & 1
- Val = DAG.getNode(ISD::AND, N0.getValueType(),
- N0.getOperand(0).getOperand(0), N0.getOperand(1));
- }
- return DAG.getSetCC(VT, Val, N1,
- Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
- }
- }
-
- uint64_t MinVal, MaxVal;
- unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0));
- if (ISD::isSignedIntSetCC(Cond)) {
- MinVal = 1ULL << (OperandBitSize-1);
- if (OperandBitSize != 1) // Avoid X >> 64, which is undefined.
- MaxVal = ~0ULL >> (65-OperandBitSize);
- else
- MaxVal = 0;
- } else {
- MinVal = 0;
- MaxVal = ~0ULL >> (64-OperandBitSize);
- }
-
- // Canonicalize GE/LE comparisons to use GT/LT comparisons.
- if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
- if (C1 == MinVal) return DAG.getConstant(1, VT); // X >= MIN --> true
- --C1; // X >= C0 --> X > (C0-1)
- return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
- (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
- }
-
- if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
- if (C1 == MaxVal) return DAG.getConstant(1, VT); // X <= MAX --> true
- ++C1; // X <= C0 --> X < (C0+1)
- return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
- (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
- }
-
- if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
- return DAG.getConstant(0, VT); // X < MIN --> false
-
- // Canonicalize setgt X, Min --> setne X, Min
- if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
- return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
- // Canonicalize setlt X, Max --> setne X, Max
- if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal)
- return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
-
- // If we have setult X, 1, turn it into seteq X, 0
- if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
- return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()),
- ISD::SETEQ);
- // If we have setugt X, Max-1, turn it into seteq X, Max
- else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
- return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()),
- ISD::SETEQ);
-
- // If we have "setcc X, C0", check to see if we can shrink the immediate
- // by changing cc.
-
- // SETUGT X, SINTMAX -> SETLT X, 0
- if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
- C1 == (~0ULL >> (65-OperandBitSize)))
- return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()),
- ISD::SETLT);
-
- // FIXME: Implement the rest of these.
-
- // Fold bit comparisons when we can.
- if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
- VT == N0.getValueType() && N0.getOpcode() == ISD::AND)
- if (ConstantSDNode *AndRHS =
- dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
- if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3
- // Perform the xform if the AND RHS is a single bit.
- if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
- return DAG.getNode(ISD::SRL, VT, N0,
- DAG.getConstant(Log2_64(AndRHS->getValue()),
- TLI.getShiftAmountTy()));
- }
- } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) {
- // (X & 8) == 8 --> (X & 8) >> 3
- // Perform the xform if C1 is a single bit.
- if ((C1 & (C1-1)) == 0) {
- return DAG.getNode(ISD::SRL, VT, N0,
- DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy()));
- }
- }
- }
- }
- } else if (isa<ConstantSDNode>(N0.Val)) {
- // Ensure that the constant occurs on the RHS.
- return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
- }
-
- if (ConstantFPSDNode *N0C = dyn_cast<ConstantFPSDNode>(N0.Val))
- if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) {
- double C0 = N0C->getValue(), C1 = N1C->getValue();
-
- switch (Cond) {
- default: break; // FIXME: Implement the rest of these!
- case ISD::SETEQ: return DAG.getConstant(C0 == C1, VT);
- case ISD::SETNE: return DAG.getConstant(C0 != C1, VT);
- case ISD::SETLT: return DAG.getConstant(C0 < C1, VT);
- case ISD::SETGT: return DAG.getConstant(C0 > C1, VT);
- case ISD::SETLE: return DAG.getConstant(C0 <= C1, VT);
- case ISD::SETGE: return DAG.getConstant(C0 >= C1, VT);
- }
- } else {
- // Ensure that the constant occurs on the RHS.
- return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
- }
-
- if (N0 == N1) {
- // We can always fold X == Y for integer setcc's.
- if (MVT::isInteger(N0.getValueType()))
- return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
- unsigned UOF = ISD::getUnorderedFlavor(Cond);
- if (UOF == 2) // FP operators that are undefined on NaNs.
- return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
- if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
- return DAG.getConstant(UOF, VT);
- // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO
- // if it is not already.
- ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
- if (NewCond != Cond)
- return DAG.getSetCC(VT, N0, N1, NewCond);
- }
-
- if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
- MVT::isInteger(N0.getValueType())) {
- if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
- N0.getOpcode() == ISD::XOR) {
- // Simplify (X+Y) == (X+Z) --> Y == Z
- if (N0.getOpcode() == N1.getOpcode()) {
- if (N0.getOperand(0) == N1.getOperand(0))
- return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond);
- if (N0.getOperand(1) == N1.getOperand(1))
- return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond);
- if (DAG.isCommutativeBinOp(N0.getOpcode())) {
- // If X op Y == Y op X, try other combinations.
- if (N0.getOperand(0) == N1.getOperand(1))
- return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond);
- if (N0.getOperand(1) == N1.getOperand(0))
- return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(1), Cond);
- }
- }
-
- if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) {
- if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
- // Turn (X+C1) == C2 --> X == C2-C1
- if (N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse()) {
- return DAG.getSetCC(VT, N0.getOperand(0),
- DAG.getConstant(RHSC->getValue()-LHSR->getValue(),
- N0.getValueType()), Cond);
- }
-
- // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
- if (N0.getOpcode() == ISD::XOR)
- // If we know that all of the inverted bits are zero, don't bother
- // performing the inversion.
- if (TLI.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getValue()))
- return DAG.getSetCC(VT, N0.getOperand(0),
- DAG.getConstant(LHSR->getValue()^RHSC->getValue(),
- N0.getValueType()), Cond);
- }
-
- // Turn (C1-X) == C2 --> X == C1-C2
- if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
- if (N0.getOpcode() == ISD::SUB && N0.Val->hasOneUse()) {
- return DAG.getSetCC(VT, N0.getOperand(1),
- DAG.getConstant(SUBC->getValue()-RHSC->getValue(),
- N0.getValueType()), Cond);
- }
- }
- }
-
- // Simplify (X+Z) == X --> Z == 0
- if (N0.getOperand(0) == N1)
- return DAG.getSetCC(VT, N0.getOperand(1),
- DAG.getConstant(0, N0.getValueType()), Cond);
- if (N0.getOperand(1) == N1) {
- if (DAG.isCommutativeBinOp(N0.getOpcode()))
- return DAG.getSetCC(VT, N0.getOperand(0),
- DAG.getConstant(0, N0.getValueType()), Cond);
- else {
- assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
- // (Z-X) == X --> Z == X<<1
- SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(),
- N1,
- DAG.getConstant(1,TLI.getShiftAmountTy()));
- AddToWorkList(SH.Val);
- return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond);
- }
- }
- }
-
- if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
- N1.getOpcode() == ISD::XOR) {
- // Simplify X == (X+Z) --> Z == 0
- if (N1.getOperand(0) == N0) {
- return DAG.getSetCC(VT, N1.getOperand(1),
- DAG.getConstant(0, N1.getValueType()), Cond);
- } else if (N1.getOperand(1) == N0) {
- if (DAG.isCommutativeBinOp(N1.getOpcode())) {
- return DAG.getSetCC(VT, N1.getOperand(0),
- DAG.getConstant(0, N1.getValueType()), Cond);
- } else {
- assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
- // X == (Z-X) --> X<<1 == Z
- SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0,
- DAG.getConstant(1,TLI.getShiftAmountTy()));
- AddToWorkList(SH.Val);
- return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond);
- }
- }
- }
- }
-
- // Fold away ALL boolean setcc's.
- SDOperand Temp;
- if (N0.getValueType() == MVT::i1 && foldBooleans) {
- switch (Cond) {
- default: assert(0 && "Unknown integer setcc!");
- case ISD::SETEQ: // X == Y -> (X^Y)^1
- Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
- N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1));
- AddToWorkList(Temp.Val);
- break;
- case ISD::SETNE: // X != Y --> (X^Y)
- N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
- break;
- case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> X^1 & Y
- case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> X^1 & Y
- Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
- N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp);
- AddToWorkList(Temp.Val);
- break;
- case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> Y^1 & X
- case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> Y^1 & X
- Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
- N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp);
- AddToWorkList(Temp.Val);
- break;
- case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> X^1 | Y
- case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> X^1 | Y
- Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
- N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp);
- AddToWorkList(Temp.Val);
- break;
- case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> Y^1 | X
- case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> Y^1 | X
- Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
- N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp);
- break;
- }
- if (VT != MVT::i1) {
- AddToWorkList(N0.Val);
- // FIXME: If running after legalize, we probably can't do this.
- N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
- }
- return N0;
- }
-
- // Could not fold it.
- return SDOperand();
+ TargetLowering::DAGCombinerInfo
+ DagCombineInfo(DAG, !AfterLegalize, false, this);
+ return TLI.SimplifySetCC(VT, N0, N1, Cond, foldBooleans, DagCombineInfo);
}
/// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
return S;
}
-/// FindBaseOffset - Return true if we can determine base and offset information
-/// from a given pointer operand. Provides base and offset as a result.
-bool DAGCombiner::FindBaseOffset(SDOperand Ptr,
- SDOperand &Object, int64_t &Offset) {
+/// FindBaseOffset - Return true if base is known not to alias with anything
+/// but itself. Provides base object and offset as results.
+static bool FindBaseOffset(SDOperand Ptr, SDOperand &Base, int64_t &Offset) {
+ // Assume it is a primitive operation.
+ Base = Ptr; Offset = 0;
- // Is it a frame variable, global or constant.
- if (isa<FrameIndexSDNode>(Ptr) ||
- isa<ConstantPoolSDNode>(Ptr) ||
- isa<GlobalAddressSDNode>(Ptr)) {
- Object = Ptr; Offset = 0;
- return true;
- } else if (Ptr.getOpcode() == ISD::ADD &&
- FindBaseOffset(Ptr.getOperand(0), Object, Offset)) {
- // If it's an add of an simple constant then include it in the offset.
- if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Ptr.getOperand(1))) {
+ // If it's an adding a simple constant then integrate the offset.
+ if (Base.getOpcode() == ISD::ADD) {
+ if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Base.getOperand(1))) {
+ Base = Base.getOperand(0);
Offset += C->getValue();
- return true;
}
}
-
- return false;
+
+ // If it's any of the following then it can't alias with anything but itself.
+ return isa<FrameIndexSDNode>(Base) ||
+ isa<ConstantPoolSDNode>(Base) ||
+ isa<GlobalAddressSDNode>(Base);
}
-/// isAlias - Return true if there is the possibility that the two addresses
+/// isAlias - Return true if there is any possibility that the two addresses
/// overlap.
bool DAGCombiner::isAlias(SDOperand Ptr1, int64_t Size1,
- SDOperand SrcValue1,
+ const Value *SrcValue1, int SrcValueOffset1,
SDOperand Ptr2, int64_t Size2,
- SDOperand SrcValue2) {
+ const Value *SrcValue2, int SrcValueOffset2)
+{
// If they are the same then they must be aliases.
if (Ptr1 == Ptr2) return true;
- // Gather base offset information. Objects can be frame variables, globals
- // or constants.
- SDOperand Object1, Object2;
+ // Gather base node and offset information.
+ SDOperand Base1, Base2;
int64_t Offset1, Offset2;
- if (FindBaseOffset(Ptr1, Object1, Offset1) &&
- FindBaseOffset(Ptr2, Object2, Offset2)) {
- // If they have a different base address, then they can't alias.
- if (Object1 != Object2) return false;
-
+ bool KnownBase1 = FindBaseOffset(Ptr1, Base1, Offset1);
+ bool KnownBase2 = FindBaseOffset(Ptr2, Base2, Offset2);
+
+ // If they have a same base address then...
+ if (Base1 == Base2) {
// Check to see if the addresses overlap.
- if ((Offset1 + Size1) <= Offset2 || (Offset2 + Size2) <= Offset1)
- return false;
+ return!((Offset1 + Size1) <= Offset2 || (Offset2 + Size2) <= Offset1);
}
- // Otherwise we don't know and have to play it safe.
+ // If we know both bases then they can't alias.
+ if (KnownBase1 && KnownBase2) return false;
+
+ if (CombinerGlobalAA) {
+ // Use alias analysis information.
+ int64_t MinOffset = std::min(SrcValueOffset1, SrcValueOffset2);
+ int64_t Overlap1 = Size1 + SrcValueOffset1 - MinOffset;
+ int64_t Overlap2 = Size2 + SrcValueOffset2 - MinOffset;
+ AliasAnalysis::AliasResult AAResult =
+ AA.alias(SrcValue1, Overlap1, SrcValue2, Overlap2);
+ if (AAResult == AliasAnalysis::NoAlias)
+ return false;
+ }
+
+ // Otherwise we have to assume they alias.
return true;
}
/// FindAliasInfo - Extracts the relevant alias information from the memory
-/// node.
-void DAGCombiner::FindAliasInfo(SDNode *N,
- SDOperand &Ptr, int64_t &Size, SDOperand &SrcValue) {
- switch (N->getOpcode()) {
- case ISD::LOAD:
- Ptr = N->getOperand(1);
- Size = MVT::getSizeInBits(N->getValueType(0)) >> 3;
- SrcValue = N->getOperand(2);
- break;
- case ISD::STORE:
- Ptr = N->getOperand(2);
- Size = MVT::getSizeInBits(N->getOperand(1).getValueType()) >> 3;
- SrcValue = N->getOperand(3);
- break;
- default:
- assert(0 && "getAliasInfo expected a memory op");
+/// node. Returns true if the operand was a load.
+bool DAGCombiner::FindAliasInfo(SDNode *N,
+ SDOperand &Ptr, int64_t &Size,
+ const Value *&SrcValue, int &SrcValueOffset) {
+ if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
+ Ptr = LD->getBasePtr();
+ Size = MVT::getSizeInBits(LD->getLoadedVT()) >> 3;
+ SrcValue = LD->getSrcValue();
+ SrcValueOffset = LD->getSrcValueOffset();
+ return true;
+ } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
+ Ptr = ST->getBasePtr();
+ Size = MVT::getSizeInBits(ST->getStoredVT()) >> 3;
+ SrcValue = ST->getSrcValue();
+ SrcValueOffset = ST->getSrcValueOffset();
+ } else {
+ assert(0 && "FindAliasInfo expected a memory operand");
}
+
+ return false;
}
-/// hasChain - Return true if Op has a chain. Provides chain if present.
-///
-bool DAGCombiner::hasChain(SDOperand Op, SDOperand &Chain) {
- if (Op.getNumOperands() == 0) return false;
- Chain = Op.getOperand(0);
- return Chain.getValueType() == MVT::Other;
-}
-
-/// FindBetterChain - Walk up chain skipping non-aliasing memory nodes, looking
-/// for a better chain.
-SDOperand DAGCombiner::FindBetterChain(SDNode *N, SDOperand Chain) {
+/// GatherAllAliases - Walk up chain skipping non-aliasing memory nodes,
+/// looking for aliasing nodes and adding them to the Aliases vector.
+void DAGCombiner::GatherAllAliases(SDNode *N, SDOperand OriginalChain,
+ SmallVector<SDOperand, 8> &Aliases) {
+ SmallVector<SDOperand, 8> Chains; // List of chains to visit.
+ std::set<SDNode *> Visited; // Visited node set.
+
// Get alias information for node.
SDOperand Ptr;
int64_t Size;
- SDOperand SrcValue;
- FindAliasInfo(N, Ptr, Size, SrcValue);
-
- // While we don't encounter any aliasing memory nodes walk up chain.
- while (true) {
+ const Value *SrcValue;
+ int SrcValueOffset;
+ bool IsLoad = FindAliasInfo(N, Ptr, Size, SrcValue, SrcValueOffset);
+
+ // Starting off.
+ Chains.push_back(OriginalChain);
+
+ // Look at each chain and determine if it is an alias. If so, add it to the
+ // aliases list. If not, then continue up the chain looking for the next
+ // candidate.
+ while (!Chains.empty()) {
+ SDOperand Chain = Chains.back();
+ Chains.pop_back();
+
+ // Don't bother if we've been before.
+ if (Visited.find(Chain.Val) != Visited.end()) continue;
+ Visited.insert(Chain.Val);
+
switch (Chain.getOpcode()) {
case ISD::EntryToken:
- // Entry token is ideal chain operand.
- return Chain;
+ // Entry token is ideal chain operand, but handled in FindBetterChain.
+ break;
+
case ISD::LOAD:
case ISD::STORE: {
- // Get alias information for chain.
- SDOperand ChainPtr;
- int64_t ChainSize;
- SDOperand ChainSrcValue;
- FindAliasInfo(Chain.Val, ChainPtr, ChainSize, ChainSrcValue);
-
- // If chain is alias then stop here, otherwise continue up chain.
- if (isAlias(Ptr, Size, SrcValue, ChainPtr, ChainSize, ChainSrcValue))
- return Chain;
- else
- Chain = Chain.getOperand(0);
+ // Get alias information for Chain.
+ SDOperand OpPtr;
+ int64_t OpSize;
+ const Value *OpSrcValue;
+ int OpSrcValueOffset;
+ bool IsOpLoad = FindAliasInfo(Chain.Val, OpPtr, OpSize,
+ OpSrcValue, OpSrcValueOffset);
+ // If chain is alias then stop here.
+ if (!(IsLoad && IsOpLoad) &&
+ isAlias(Ptr, Size, SrcValue, SrcValueOffset,
+ OpPtr, OpSize, OpSrcValue, OpSrcValueOffset)) {
+ Aliases.push_back(Chain);
+ } else {
+ // Look further up the chain.
+ Chains.push_back(Chain.getOperand(0));
+ // Clean up old chain.
+ AddToWorkList(Chain.Val);
+ }
break;
}
- case ISD::TokenFactor: {
- // Continue up each of token factor operand and accumulate results in
- // a new token factor. CSE will handle duplicate elimination.
- SmallVector<SDOperand, 8> Ops; // Ops for replacing token factor.
- bool Change = false;
-
- // For each token factor operand.
- for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i) {
- SDOperand Op = Chain.getOperand(i);
- SDOperand OpChain = FindBetterChain(N, Op);
-
- // Make sure we don't duplicate an operand.
- if (OpChain.getOpcode() != ISD::EntryToken &&
- std::find(Ops.begin(), Ops.end(), OpChain) == Ops.end()) {
- Ops.push_back(OpChain);
- }
-
- // If we added a new operand.
- Change = Change || Op != OpChain;
- }
-
- // If we have new operands.
- if (Change) {
- // Create a specialized token factor for this chain. getNode CSE will
- // handle duplicates. If it's a single operand, getNode will just
- // return the opernand instead of a new token factor.
- return DAG.getNode(ISD::TokenFactor, MVT::Other, &Ops[0], Ops.size());
- }
+
+ case ISD::TokenFactor:
+ // We have to check each of the operands of the token factor, so we queue
+ // then up. Adding the operands to the queue (stack) in reverse order
+ // maintains the original order and increases the likelihood that getNode
+ // will find a matching token factor (CSE.)
+ for (unsigned n = Chain.getNumOperands(); n;)
+ Chains.push_back(Chain.getOperand(--n));
+ // Eliminate the token factor if we can.
+ AddToWorkList(Chain.Val);
+ break;
- // Leave things alone.
- return Chain;
- }
- // For all other instructions we will just have to take what we can get.
- default: return Chain;
+ default:
+ // For all other instructions we will just have to take what we can get.
+ Aliases.push_back(Chain);
+ break;
}
}
+}
+
+/// FindBetterChain - Walk up chain skipping non-aliasing memory nodes, looking
+/// for a better chain (aliasing node.)
+SDOperand DAGCombiner::FindBetterChain(SDNode *N, SDOperand OldChain) {
+ SmallVector<SDOperand, 8> Aliases; // Ops for replacing token factor.
+
+ // Accumulate all the aliases to this node.
+ GatherAllAliases(N, OldChain, Aliases);
+
+ if (Aliases.size() == 0) {
+ // If no operands then chain to entry token.
+ return DAG.getEntryNode();
+ } else if (Aliases.size() == 1) {
+ // If a single operand then chain to it. We don't need to revisit it.
+ return Aliases[0];
+ }
+
+ // Construct a custom tailored token factor.
+ SDOperand NewChain = DAG.getNode(ISD::TokenFactor, MVT::Other,
+ &Aliases[0], Aliases.size());
+
+ // Make sure the old chain gets cleaned up.
+ if (NewChain != OldChain) AddToWorkList(OldChain.Val);
- return Chain;
+ return NewChain;
}
// SelectionDAG::Combine - This is the entry point for the file.
//
-void SelectionDAG::Combine(bool RunningAfterLegalize) {
+void SelectionDAG::Combine(bool RunningAfterLegalize, AliasAnalysis &AA) {
+ if (!RunningAfterLegalize && ViewDAGCombine1)
+ viewGraph();
+ if (RunningAfterLegalize && ViewDAGCombine2)
+ viewGraph();
/// run - This is the main entry point to this class.
///
- DAGCombiner(*this).Run(RunningAfterLegalize);
+ DAGCombiner(*this, AA).Run(RunningAfterLegalize);
}
projects / oota-llvm.git / blobdiff