#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Target/TargetLowering.h"
+#include "llvm/Support/Visibility.h"
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace llvm;
namespace {
- Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined");
+ static Statistic<> NodesCombined ("dagcombiner",
+ "Number of dag nodes combined");
- class DAGCombiner {
+ class VISIBILITY_HIDDEN DAGCombiner {
SelectionDAG &DAG;
TargetLowering &TLI;
bool AfterLegalize;
SDOperand CombineTo(SDNode *N, const std::vector<SDOperand> &To) {
++NodesCombined;
DEBUG(std::cerr << "\nReplacing "; N->dump();
- std::cerr << "\nWith: "; To[0].Val->dump();
+ std::cerr << "\nWith: "; To[0].Val->dump(&DAG);
std::cerr << " and " << To.size()-1 << " other values\n");
std::vector<SDNode*> NowDead;
DAG.ReplaceAllUsesWith(N, To, &NowDead);
// Replace the old value with the new one.
++NodesCombined;
DEBUG(std::cerr << "\nReplacing "; TLO.Old.Val->dump();
- std::cerr << "\nWith: "; TLO.New.Val->dump());
+ std::cerr << "\nWith: "; TLO.New.Val->dump(&DAG));
std::vector<SDNode*> NowDead;
DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, NowDead);
//===----------------------------------------------------------------------===//
-struct ms {
- int64_t m; // magic number
- int64_t s; // shift amount
-};
-
-struct mu {
- uint64_t m; // magic number
- int64_t a; // add indicator
- int64_t s; // shift amount
-};
-
-/// magic - calculate the magic numbers required to codegen an integer sdiv as
-/// a sequence of multiply and shifts. Requires that the divisor not be 0, 1,
-/// or -1.
-static ms magic32(int32_t d) {
- int32_t p;
- uint32_t ad, anc, delta, q1, r1, q2, r2, t;
- const uint32_t two31 = 0x80000000U;
- struct ms mag;
-
- ad = abs(d);
- t = two31 + ((uint32_t)d >> 31);
- anc = t - 1 - t%ad; // absolute value of nc
- p = 31; // initialize p
- q1 = two31/anc; // initialize q1 = 2p/abs(nc)
- r1 = two31 - q1*anc; // initialize r1 = rem(2p,abs(nc))
- q2 = two31/ad; // initialize q2 = 2p/abs(d)
- r2 = two31 - q2*ad; // initialize r2 = rem(2p,abs(d))
- do {
- p = p + 1;
- q1 = 2*q1; // update q1 = 2p/abs(nc)
- r1 = 2*r1; // update r1 = rem(2p/abs(nc))
- if (r1 >= anc) { // must be unsigned comparison
- q1 = q1 + 1;
- r1 = r1 - anc;
- }
- q2 = 2*q2; // update q2 = 2p/abs(d)
- r2 = 2*r2; // update r2 = rem(2p/abs(d))
- if (r2 >= ad) { // must be unsigned comparison
- q2 = q2 + 1;
- r2 = r2 - ad;
- }
- delta = ad - r2;
- } while (q1 < delta || (q1 == delta && r1 == 0));
-
- mag.m = (int32_t)(q2 + 1); // make sure to sign extend
- if (d < 0) mag.m = -mag.m; // resulting magic number
- mag.s = p - 32; // resulting shift
- return mag;
-}
-
-/// magicu - calculate the magic numbers required to codegen an integer udiv as
-/// a sequence of multiply, add and shifts. Requires that the divisor not be 0.
-static mu magicu32(uint32_t d) {
- int32_t p;
- uint32_t nc, delta, q1, r1, q2, r2;
- struct mu magu;
- magu.a = 0; // initialize "add" indicator
- nc = - 1 - (-d)%d;
- p = 31; // initialize p
- q1 = 0x80000000/nc; // initialize q1 = 2p/nc
- r1 = 0x80000000 - q1*nc; // initialize r1 = rem(2p,nc)
- q2 = 0x7FFFFFFF/d; // initialize q2 = (2p-1)/d
- r2 = 0x7FFFFFFF - q2*d; // initialize r2 = rem((2p-1),d)
- do {
- p = p + 1;
- if (r1 >= nc - r1 ) {
- q1 = 2*q1 + 1; // update q1
- r1 = 2*r1 - nc; // update r1
- }
- else {
- q1 = 2*q1; // update q1
- r1 = 2*r1; // update r1
- }
- if (r2 + 1 >= d - r2) {
- if (q2 >= 0x7FFFFFFF) magu.a = 1;
- q2 = 2*q2 + 1; // update q2
- r2 = 2*r2 + 1 - d; // update r2
- }
- else {
- if (q2 >= 0x80000000) magu.a = 1;
- q2 = 2*q2; // update q2
- r2 = 2*r2 + 1; // update r2
- }
- delta = d - 1 - r2;
- } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
- magu.m = q2 + 1; // resulting magic number
- magu.s = p - 32; // resulting shift
- return magu;
-}
-
-/// magic - calculate the magic numbers required to codegen an integer sdiv as
-/// a sequence of multiply and shifts. Requires that the divisor not be 0, 1,
-/// or -1.
-static ms magic64(int64_t d) {
- int64_t p;
- uint64_t ad, anc, delta, q1, r1, q2, r2, t;
- const uint64_t two63 = 9223372036854775808ULL; // 2^63
- struct ms mag;
-
- ad = d >= 0 ? d : -d;
- t = two63 + ((uint64_t)d >> 63);
- anc = t - 1 - t%ad; // absolute value of nc
- p = 63; // initialize p
- q1 = two63/anc; // initialize q1 = 2p/abs(nc)
- r1 = two63 - q1*anc; // initialize r1 = rem(2p,abs(nc))
- q2 = two63/ad; // initialize q2 = 2p/abs(d)
- r2 = two63 - q2*ad; // initialize r2 = rem(2p,abs(d))
- do {
- p = p + 1;
- q1 = 2*q1; // update q1 = 2p/abs(nc)
- r1 = 2*r1; // update r1 = rem(2p/abs(nc))
- if (r1 >= anc) { // must be unsigned comparison
- q1 = q1 + 1;
- r1 = r1 - anc;
- }
- q2 = 2*q2; // update q2 = 2p/abs(d)
- r2 = 2*r2; // update r2 = rem(2p/abs(d))
- if (r2 >= ad) { // must be unsigned comparison
- q2 = q2 + 1;
- r2 = r2 - ad;
- }
- delta = ad - r2;
- } while (q1 < delta || (q1 == delta && r1 == 0));
-
- mag.m = q2 + 1;
- if (d < 0) mag.m = -mag.m; // resulting magic number
- mag.s = p - 64; // resulting shift
- return mag;
-}
-
-/// magicu - calculate the magic numbers required to codegen an integer udiv as
-/// a sequence of multiply, add and shifts. Requires that the divisor not be 0.
-static mu magicu64(uint64_t d)
-{
- int64_t p;
- uint64_t nc, delta, q1, r1, q2, r2;
- struct mu magu;
- magu.a = 0; // initialize "add" indicator
- nc = - 1 - (-d)%d;
- p = 63; // initialize p
- q1 = 0x8000000000000000ull/nc; // initialize q1 = 2p/nc
- r1 = 0x8000000000000000ull - q1*nc; // initialize r1 = rem(2p,nc)
- q2 = 0x7FFFFFFFFFFFFFFFull/d; // initialize q2 = (2p-1)/d
- r2 = 0x7FFFFFFFFFFFFFFFull - q2*d; // initialize r2 = rem((2p-1),d)
- do {
- p = p + 1;
- if (r1 >= nc - r1 ) {
- q1 = 2*q1 + 1; // update q1
- r1 = 2*r1 - nc; // update r1
- }
- else {
- q1 = 2*q1; // update q1
- r1 = 2*r1; // update r1
- }
- if (r2 + 1 >= d - r2) {
- if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1;
- q2 = 2*q2 + 1; // update q2
- r2 = 2*r2 + 1 - d; // update r2
- }
- else {
- if (q2 >= 0x8000000000000000ull) magu.a = 1;
- q2 = 2*q2; // update q2
- r2 = 2*r2 + 1; // update r2
- }
- delta = d - 1 - r2;
- } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
- magu.m = q2 + 1; // resulting magic number
- magu.s = p - 64; // resulting shift
- return magu;
-}
-
// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc
// that selects between the values 1 and 0, making it equivalent to a setcc.
// Also, set the incoming LHS, RHS, and CC references to the appropriate
// 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);
// CombineTo was used. Since CombineTo takes care of the worklist
// mechanics for us, we have no work to do in this case.
if (RV.Val != N) {
+ assert(N->getOpcode() != ISD::DELETED_NODE &&
+ 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();
+ std::cerr << "\nWith: "; RV.Val->dump(&DAG);
std::cerr << '\n');
std::vector<SDNode*> NowDead;
DAG.ReplaceAllUsesWith(N, std::vector<SDOperand>(1, RV), &NowDead);
// If the token factor has two operands and one is the entry token, replace
// the token factor with the other operand.
if (N->getNumOperands() == 2) {
- if (N->getOperand(0).getOpcode() == ISD::EntryToken)
+ if (N->getOperand(0).getOpcode() == ISD::EntryToken ||
+ N->getOperand(0) == N->getOperand(1))
return N->getOperand(1);
if (N->getOperand(1).getOpcode() == ISD::EntryToken)
return N->getOperand(0);
Changed = true;
for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j)
Ops.push_back(Op.getOperand(j));
- } else {
+ } else if (i == 0 || N->getOperand(i) != N->getOperand(i-1)) {
Ops.push_back(Op);
+ } else {
+ // Deleted an operand that was the same as the last one.
+ Changed = true;
}
}
if (Changed)
// fold (OP (zext x), (zext y)) -> (zext (OP x, y))
// fold (OP (sext x), (sext y)) -> (sext (OP x, y))
// fold (OP (aext x), (aext y)) -> (aext (OP x, y))
+ // fold (OP (trunc x), (trunc y)) -> (trunc (OP x, y))
if ((N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND||
- N0.getOpcode() == ISD::SIGN_EXTEND) &&
+ N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::TRUNCATE) &&
N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
SDOperand ORNode = DAG.getNode(N->getOpcode(),
N0.getOperand(0).getValueType(),
return DAG.getNode(N0.getOpcode(), VT, ORNode);
}
- // fold (and (trunc x), (trunc y)) -> (trunc (and x, y))
- // fold (or (trunc x), (trunc y)) -> (trunc (or x, y))
- // fold (xor (trunc x), (trunc y)) -> (trunc (xor x, y))
- if (N0.getOpcode() == ISD::TRUNCATE &&
- N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
- SDOperand ORNode = DAG.getNode(N->getOpcode(),
- N0.getOperand(0).getValueType(),
- N0.getOperand(0), N1.getOperand(0));
- AddToWorkList(ORNode.Val);
- return DAG.getNode(ISD::TRUNCATE, VT, ORNode);
- }
-
-
// For each of OP in SHL/SRL/SRA/AND...
// fold (and (OP x, z), (OP y, z)) -> (OP (and x, y), z)
// fold (or (OP x, z), (OP y, z)) -> (OP (or x, y), z)
}
}
+ // Simplify, based on bits shifted out of the LHS.
+ if (N1C && SimplifyDemandedBits(SDOperand(N, 0)))
+ return SDOperand(N, 0);
+
+
// If the sign bit is known to be zero, switch this to a SRL.
if (TLI.MaskedValueIsZero(N0, MVT::getIntVTSignBit(VT)))
return DAG.getNode(ISD::SRL, VT, N0, N1);
DAG.getConstant(c1 + c2, N1.getValueType()));
}
+ // fold (srl (anyextend x), c) -> (anyextend (srl x, c))
+ if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) {
+ // Shifting in all undef bits?
+ MVT::ValueType SmallVT = N0.getOperand(0).getValueType();
+ if (N1C->getValue() >= MVT::getSizeInBits(SmallVT))
+ return DAG.getNode(ISD::UNDEF, VT);
+
+ SDOperand SmallShift = DAG.getNode(ISD::SRL, SmallVT, N0.getOperand(0), N1);
+ AddToWorkList(SmallShift.Val);
+ return DAG.getNode(ISD::ANY_EXTEND, VT, SmallShift);
+ }
+
// 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))) {
SDOperand DAGCombiner::visitCTLZ(SDNode *N) {
SDOperand N0 = N->getOperand(0);
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
MVT::ValueType VT = N->getValueType(0);
// fold (ctlz c1) -> c2
- if (N0C)
+ if (isa<ConstantSDNode>(N0))
return DAG.getNode(ISD::CTLZ, VT, N0);
return SDOperand();
}
SDOperand DAGCombiner::visitCTTZ(SDNode *N) {
SDOperand N0 = N->getOperand(0);
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
MVT::ValueType VT = N->getValueType(0);
// fold (cttz c1) -> c2
- if (N0C)
+ if (isa<ConstantSDNode>(N0))
return DAG.getNode(ISD::CTTZ, VT, N0);
return SDOperand();
}
SDOperand DAGCombiner::visitCTPOP(SDNode *N) {
SDOperand N0 = N->getOperand(0);
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
MVT::ValueType VT = N->getValueType(0);
// fold (ctpop c1) -> c2
- if (N0C)
+ if (isa<ConstantSDNode>(N0))
return DAG.getNode(ISD::CTPOP, VT, N0);
return SDOperand();
}
// fold X ? Y : X --> X ? Y : 0 --> X & Y
if (MVT::i1 == VT && N0 == N2)
return DAG.getNode(ISD::AND, VT, N0, N1);
+
// If we can fold this based on the true/false value, do so.
if (SimplifySelectOps(N, N1, N2))
- return SDOperand();
+ return SDOperand(N, 0); // Don't revisit N.
+
// fold selects based on a setcc into other things, such as min/max/abs
if (N0.getOpcode() == ISD::SETCC)
// FIXME:
// Determine if the condition we're dealing with is constant
SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
- ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
+ //ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
// fold select_cc lhs, rhs, x, x, cc -> x
if (N2 == N3)
// If we can fold this based on the true/false value, do so.
if (SimplifySelectOps(N, N2, N3))
- return SDOperand();
+ return SDOperand(N, 0); // Don't revisit N.
// fold select_cc into other things, such as min/max/abs
return SimplifySelectCC(N0, N1, N2, N3, CC);
SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) {
SDOperand N0 = N->getOperand(0);
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
MVT::ValueType VT = N->getValueType(0);
// fold (sext c1) -> c1
- if (N0C)
+ if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0))
return DAG.getNode(ISD::SIGN_EXTEND, VT, N0);
+
// fold (sext (sext x)) -> (sext x)
- if (N0.getOpcode() == ISD::SIGN_EXTEND)
+ // fold (sext (aext 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) iff x size == sext size.
if (N0.getOpcode() == ISD::TRUNCATE && N0.getOperand(0).getValueType() == VT&&
(!AfterLegalize ||
TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, N0.getValueType())))
return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0),
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()))){
// fold (sext ( extload x)) -> (sext (truncate (sextload x)))
if ((N0.getOpcode() == ISD::SEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) &&
N0.hasOneUse()) {
- SDOperand ExtLoad = DAG.getNode(ISD::SEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- N0.getOperand(3));
+ 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));
SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) {
SDOperand N0 = N->getOperand(0);
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
MVT::ValueType VT = N->getValueType(0);
// fold (zext c1) -> c1
- if (N0C)
+ if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0))
return DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
// fold (zext (zext x)) -> (zext x)
- if (N0.getOpcode() == ISD::ZERO_EXTEND)
+ // 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 x)) -> (zextinreg x) iff x size == zext size.
if (N0.getOpcode() == ISD::TRUNCATE && N0.getOperand(0).getValueType() == VT&&
// fold (zext ( extload x)) -> (zext (truncate (zextload x)))
if ((N0.getOpcode() == ISD::ZEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) &&
N0.hasOneUse()) {
- SDOperand ExtLoad = DAG.getNode(ISD::ZEXTLOAD, VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- N0.getOperand(3));
+ 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);
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
SDOperand DAGCombiner::visitANY_EXTEND(SDNode *N) {
SDOperand N0 = N->getOperand(0);
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
MVT::ValueType VT = N->getValueType(0);
// fold (aext c1) -> c1
- if (N0C)
+ if (isa<ConstantSDNode>(N0))
return DAG.getNode(ISD::ANY_EXTEND, VT, N0);
// fold (aext (aext x)) -> (aext x)
// fold (aext (zext x)) -> (zext x)
if ((N0.getOpcode() == ISD::ZEXTLOAD || N0.getOpcode() == ISD::EXTLOAD ||
N0.getOpcode() == ISD::SEXTLOAD) &&
N0.hasOneUse()) {
- SDOperand ExtLoad = DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0),
- N0.getOperand(1), N0.getOperand(2),
- N0.getOperand(3));
+ 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);
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) {
SDOperand N0 = N->getOperand(0);
SDOperand N1 = N->getOperand(1);
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
MVT::ValueType VT = N->getValueType(0);
MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT();
unsigned EVTBits = MVT::getSizeInBits(EVT);
// fold (sext_in_reg c1) -> c1
- if (N0C) {
- SDOperand Truncate = DAG.getConstant(N0C->getValue(), EVT);
- return DAG.getNode(ISD::SIGN_EXTEND, VT, Truncate);
- }
- // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt1
- if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
- cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) {
+ if (isa<ConstantSDNode>(N0) || N0.getOpcode() == ISD::UNDEF)
+ 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)
return N0;
- }
+
// fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2
if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) {
return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1);
}
- // fold (sext_in_reg (assert_sext x)) -> (assert_sext x)
- if (N0.getOpcode() == ISD::AssertSext &&
- cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) {
- return N0;
- }
- // fold (sext_in_reg (sextload x)) -> (sextload x)
- if (N0.getOpcode() == ISD::SEXTLOAD &&
- cast<VTSDNode>(N0.getOperand(3))->getVT() <= EVT) {
- return N0;
- }
- // fold (sext_in_reg (setcc x)) -> setcc x iff (setcc x) == 0 or -1
- if (N0.getOpcode() == ISD::SETCC &&
- TLI.getSetCCResultContents() ==
- TargetLowering::ZeroOrNegativeOneSetCCResult)
- return N0;
+
// fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is zero
if (TLI.MaskedValueIsZero(N0, 1ULL << (EVTBits-1)))
return DAG.getZeroExtendInReg(N0, EVT);
+
+ // 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 (N0.getOpcode() == ISD::SRL) {
+ if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
+ 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));
+ 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() &&
SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) {
SDOperand N0 = N->getOperand(0);
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
MVT::ValueType VT = N->getValueType(0);
// noop truncate
if (N0.getValueType() == N->getValueType(0))
return N0;
// fold (truncate c1) -> c1
- if (N0C)
+ if (isa<ConstantSDNode>(N0))
return DAG.getNode(ISD::TRUNCATE, VT, N0);
// fold (truncate (truncate x)) -> (truncate x)
if (N0.getOpcode() == ISD::TRUNCATE)
return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
// fold (truncate (ext x)) -> (ext x) or (truncate x) or x
- if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND){
+ if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND||
+ N0.getOpcode() == ISD::ANY_EXTEND) {
if (N0.getValueType() < VT)
// if the source is smaller than the dest, we still need an extend
return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0));
// fold (fp_extend c1fp) -> c1fp
if (N0CFP)
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());
+ CombineTo(N, ExtLoad);
+ CombineTo(N0.Val, DAG.getNode(ISD::FP_ROUND, N0.getValueType(), ExtLoad),
+ ExtLoad.getValue(1));
+ return SDOperand(N, 0); // Return N so it doesn't get rechecked!
+ }
+
+
return SDOperand();
}
}
}
if (isIdentity) return N->getOperand(1);
-
- // If the LHS and the RHS are the same node, turn the RHS into an undef.
- if (N->getOperand(0) == N->getOperand(1)) {
- if (N->getOperand(0).getOpcode() == ISD::UNDEF)
+
+ // 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::BIT_CONVERT)
+ V = V->getOperand(0).Val;
+ if (V->getOpcode() == ISD::BUILD_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) {
+ 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.
MappedOps);
AddToWorkList(ShufMask.Val);
return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getValueType(0),
- N->getOperand(0),
+ N0,
DAG.getNode(ISD::UNDEF, N->getValueType(0)),
ShufMask);
}
}
if (isIdentity) return N->getOperand(1);
- // If the LHS and the RHS are the same node, turn the RHS into an undef.
- if (N->getOperand(0) == 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.
std::vector<SDOperand> MappedOps;
SDOperand UDVal = DAG.getNode(ISD::UNDEF, MappedOps[0].getValueType());
for (unsigned i = 0; i != NumElts; ++i)
MappedOps[i] = UDVal;
- MappedOps[NumElts ] = *(N->getOperand(0).Val->op_end()-2);
- MappedOps[NumElts+1] = *(N->getOperand(0).Val->op_end()-1);
+ MappedOps[NumElts ] = *(N0.Val->op_end()-2);
+ MappedOps[NumElts+1] = *(N0.Val->op_end()-1);
UDVal = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, MappedOps);
return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
- N->getOperand(0), UDVal, ShufMask,
+ N0, UDVal, ShufMask,
MappedOps[NumElts], MappedOps[NumElts+1]);
}
RHSOp.getOpcode() != ISD::Constant &&
RHSOp.getOpcode() != ISD::ConstantFP))
break;
+ // Can't fold divide by zero.
+ if (N->getOpcode() == ISD::VSDIV || N->getOpcode() == ISD::VUDIV) {
+ if ((RHSOp.getOpcode() == ISD::Constant &&
+ cast<ConstantSDNode>(RHSOp.Val)->isNullValue()) ||
+ (RHSOp.getOpcode() == ISD::ConstantFP &&
+ !cast<ConstantFPSDNode>(RHSOp.Val)->getValue()))
+ break;
+ }
Ops.push_back(DAG.getNode(ScalarOp, EltType, LHSOp, RHSOp));
AddToWorkList(Ops.back().Val);
assert((Ops.back().getOpcode() == ISD::UNDEF ||
/// SimplifySelectOps - Given a SELECT or a SELECT_CC node, where LHS and RHS
/// are the two values being selected between, see if we can simplify the
-/// select.
+/// select. Callers of this should assume that TheSelect is deleted if this
+/// returns true. As such, they should return the appropriate thing (e.g. the
+/// node) back to the top-level of the DAG combiner loop to avoid it being
+/// looked at.
///
bool DAGCombiner::SimplifySelectOps(SDNode *TheSelect, SDOperand LHS,
SDOperand RHS) {
ISD::CondCode CC) {
MVT::ValueType VT = N2.getValueType();
- ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
+ //ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
// 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()));
+ DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy()));
}
}
}
/// multiplying by a magic number. See:
/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
SDOperand DAGCombiner::BuildSDIV(SDNode *N) {
- MVT::ValueType VT = N->getValueType(0);
-
- // Check to see if we can do this.
- if (!TLI.isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
- return SDOperand(); // BuildSDIV only operates on i32 or i64
- if (!TLI.isOperationLegal(ISD::MULHS, VT))
- return SDOperand(); // Make sure the target supports MULHS.
-
- int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended();
- ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d);
-
- // Multiply the numerator (operand 0) by the magic value
- SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0),
- DAG.getConstant(magics.m, VT));
- // If d > 0 and m < 0, add the numerator
- if (d > 0 && magics.m < 0) {
- Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0));
- AddToWorkList(Q.Val);
- }
- // If d < 0 and m > 0, subtract the numerator.
- if (d < 0 && magics.m > 0) {
- Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0));
- AddToWorkList(Q.Val);
- }
- // Shift right algebraic if shift value is nonzero
- if (magics.s > 0) {
- Q = DAG.getNode(ISD::SRA, VT, Q,
- DAG.getConstant(magics.s, TLI.getShiftAmountTy()));
- AddToWorkList(Q.Val);
- }
- // Extract the sign bit and add it to the quotient
- SDOperand T =
- DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1,
- TLI.getShiftAmountTy()));
- AddToWorkList(T.Val);
- return DAG.getNode(ISD::ADD, VT, Q, T);
+ std::vector<SDNode*> Built;
+ SDOperand S = TLI.BuildSDIV(N, DAG, &Built);
+
+ for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end();
+ ii != ee; ++ii)
+ AddToWorkList(*ii);
+ return S;
}
/// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
/// multiplying by a magic number. See:
/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
SDOperand DAGCombiner::BuildUDIV(SDNode *N) {
- MVT::ValueType VT = N->getValueType(0);
-
- // Check to see if we can do this.
- if (!TLI.isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
- return SDOperand(); // BuildUDIV only operates on i32 or i64
- if (!TLI.isOperationLegal(ISD::MULHU, VT))
- return SDOperand(); // Make sure the target supports MULHU.
-
- uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue();
- mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d);
-
- // Multiply the numerator (operand 0) by the magic value
- SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0),
- DAG.getConstant(magics.m, VT));
- AddToWorkList(Q.Val);
-
- if (magics.a == 0) {
- return DAG.getNode(ISD::SRL, VT, Q,
- DAG.getConstant(magics.s, TLI.getShiftAmountTy()));
- } else {
- SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q);
- AddToWorkList(NPQ.Val);
- NPQ = DAG.getNode(ISD::SRL, VT, NPQ,
- DAG.getConstant(1, TLI.getShiftAmountTy()));
- AddToWorkList(NPQ.Val);
- NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q);
- AddToWorkList(NPQ.Val);
- return DAG.getNode(ISD::SRL, VT, NPQ,
- DAG.getConstant(magics.s-1, TLI.getShiftAmountTy()));
- }
+ std::vector<SDNode*> Built;
+ SDOperand S = TLI.BuildUDIV(N, DAG, &Built);
+
+ for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end();
+ ii != ee; ++ii)
+ AddToWorkList(*ii);
+ return S;
}
// SelectionDAG::Combine - This is the entry point for the file.
projects / oota-llvm.git / blobdiff