#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
+#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/CommandLine.h"
// 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;
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 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);
SDOperand BuildSDIV(SDNode *N);
SDOperand BuildUDIV(SDNode *N);
SDNode *MatchRotate(SDOperand LHS, SDOperand RHS);
+ SDOperand ReduceLoadWidth(SDNode *N);
/// GatherAllAliases - Walk up chain skipping non-aliasing memory nodes,
/// looking for aliasing nodes and adding them to the Aliases vector.
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);
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);
+ TLI.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne);
+ if (LHSZero) {
+ TLI.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);
SimplifyDemandedBits(SDOperand(N, 0)))
return SDOperand(N, 0);
// fold (zext_inreg (extload x)) -> (zextload x)
- if (ISD::isEXTLoad(N0.Val)) {
+ 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
(!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) {
SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
LN0->getBasePtr(), LN0->getSrcValue(),
- LN0->getSrcValueOffset(), EVT);
+ 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 (ISD::isSEXTLoad(N0.Val) && N0.hasOneUse()) {
+ 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
(!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) {
SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
LN0->getBasePtr(), LN0->getSrcValue(),
- LN0->getSrcValueOffset(), EVT);
+ 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!
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)
AddToWorkList(NewPtr.Val);
SDOperand Load =
DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), NewPtr,
- LN0->getSrcValue(), LN0->getSrcValueOffset(), EVT);
+ LN0->getSrcValue(), LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(), LN0->getAlignment());
AddToWorkList(N);
CombineTo(N0.Val, Load, Load.getValue(1));
return SDOperand(N, 0); // Return N so it doesn't get rechecked!
}
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;
+ }
+ }
}
}
// if (shl x, c) is known to be zero, return 0
if (TLI.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 (srl x, c) is known to be zero, return 0
if (N1C && TLI.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) {
}
}
+ // 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 SDOperand();
}
if (N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND)
return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0));
+ // 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) {
- // See if the value being truncated is already sign extended. If so, just
- // eliminate the trunc/sext pair.
SDOperand Op = N0.getOperand(0);
unsigned OpBits = MVT::getSizeInBits(Op.getValueType());
unsigned MidBits = MVT::getSizeInBits(N0.getValueType());
SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(),
LN0->getBasePtr(), LN0->getSrcValue(),
LN0->getSrcValueOffset(),
- N0.getValueType());
+ N0.getValueType(),
+ LN0->isVolatile());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
// fold (sext (sextload x)) -> (sext (truncate (sextload x)))
// fold (sext ( extload x)) -> (sext (truncate (sextload x)))
- if ((ISD::isSEXTLoad(N0.Val) || ISD::isEXTLoad(N0.Val)) && N0.hasOneUse()) {
+ 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->getSrcValueOffset(), EVT,
+ LN0->isVolatile(),
+ LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
}
}
+ // 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();
}
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))) {
SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
LN0->getBasePtr(), LN0->getSrcValue(),
LN0->getSrcValueOffset(),
- N0.getValueType());
+ N0.getValueType(),
+ LN0->isVolatile(),
+ LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
// fold (zext (zextload x)) -> (zext (truncate (zextload x)))
// fold (zext ( extload x)) -> (zext (truncate (zextload x)))
- if ((ISD::isZEXTLoad(N0.Val) || ISD::isEXTLoad(N0.Val)) && N0.hasOneUse()) {
+ 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->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);
SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(),
LN0->getBasePtr(), LN0->getSrcValue(),
LN0->getSrcValueOffset(),
- N0.getValueType());
+ 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::LOAD && !ISD::isNON_EXTLoad(N0.Val) &&
+ if (N0.getOpcode() == ISD::LOAD &&
+ !ISD::isNON_EXTLoad(N0.Val) && ISD::isUNINDEXEDLoad(N0.Val) &&
N0.hasOneUse()) {
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->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();
+}
+
+/// 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())
+ ShAmt = MVT::getSizeInBits(N0.getValueType()) - ShAmt - EVTBits;
+ uint64_t PtrOff = ShAmt / 8;
+ 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(), LN0->getAlignment())
+ : DAG.getExtLoad(ExtType, VT, LN0->getChain(), NewPtr,
+ LN0->getSrcValue(), LN0->getSrcValueOffset(), EVT,
+ LN0->isVolatile(), LN0->getAlignment());
+ AddToWorkList(N);
+ if (CombineSRL) {
+ std::vector<SDNode*> NowDead;
+ DAG.ReplaceAllUsesOfValueWith(N0.getValue(1), Load.getValue(1), NowDead);
+ 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.getOperand(0), N1);
}
- // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is zero
+ // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is known zero.
if (TLI.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.
return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), N0.getOperand(1));
}
}
-
+
// fold (sext_inreg (extload x)) -> (sextload x)
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->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 (ISD::isZEXTLoad(N0.Val) && N0.hasOneUse() &&
+ 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->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!
// and the truncate
return N0.getOperand(0);
}
+
// fold (truncate (load x)) -> (smaller load x)
- 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()) > MVT::getSizeInBits(VT) &&
- "Cannot truncate to larger type!");
- LoadSDNode *LN0 = cast<LoadSDNode>(N0);
- 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() ? LN0->getBasePtr() :
- DAG.getNode(ISD::ADD, PtrType, LN0->getBasePtr(),
- DAG.getConstant(PtrOff, PtrType));
- AddToWorkList(NewPtr.Val);
- SDOperand Load = DAG.getLoad(VT, LN0->getChain(), NewPtr,
- LN0->getSrcValue(), LN0->getSrcValueOffset());
- 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) {
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 && ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse()) {
+ // If the resultant load doesn't need a higher alignment than the original!
+ if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() &&
+ TLI.isOperationLegal(ISD::LOAD, VT)) {
LoadSDNode *LN0 = cast<LoadSDNode>(N0);
- SDOperand Load = DAG.getLoad(VT, LN0->getChain(), LN0->getBasePtr(),
- LN0->getSrcValue(), LN0->getSrcValueOffset());
- AddToWorkList(N);
- CombineTo(N0.Val, DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load),
- Load.getValue(1));
- return Load;
+ unsigned Align = TLI.getTargetMachine().getTargetData()->
+ getPrefTypeAlignment(getTypeForValueType(VT));
+ unsigned OrigAlign = LN0->getAlignment();
+ if (Align <= OrigAlign) {
+ SDOperand Load = DAG.getLoad(VT, LN0->getChain(), LN0->getBasePtr(),
+ LN0->getSrcValue(), LN0->getSrcValueOffset(),
+ LN0->isVolatile(), LN0->getAlignment());
+ AddToWorkList(N);
+ CombineTo(N0.Val, DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load),
+ Load.getValue(1));
+ return Load;
+ }
}
return SDOperand();
SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(),
LN0->getBasePtr(), LN0->getSrcValue(),
LN0->getSrcValueOffset(),
- N0.getValueType());
+ N0.getValueType(),
+ LN0->isVolatile(),
+ LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.Val, DAG.getNode(ISD::FP_ROUND, N0.getValueType(), ExtLoad),
ExtLoad.getValue(1));
if (LD->getAddressingMode() != ISD::UNINDEXED)
return false;
VT = LD->getLoadedVT();
- if (LD->getAddressingMode() != ISD::UNINDEXED &&
- !TLI.isIndexedLoadLegal(ISD::PRE_INC, VT) &&
+ if (!TLI.isIndexedLoadLegal(ISD::PRE_INC, VT) &&
!TLI.isIndexedLoadLegal(ISD::PRE_DEC, VT))
return false;
Ptr = LD->getBasePtr();
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 base is a frame index.
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.
LoadSDNode *LD = cast<LoadSDNode>(N);
SDOperand Chain = LD->getChain();
SDOperand Ptr = LD->getBasePtr();
-
- // 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 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.
// Replace the chain to void dependency.
if (LD->getExtensionType() == ISD::NON_EXTLOAD) {
ReplLoad = DAG.getLoad(N->getValueType(0), BetterChain, Ptr,
- LD->getSrcValue(), LD->getSrcValueOffset());
+ 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->getLoadedVT(),
+ LD->isVolatile(),
+ LD->getAlignment());
}
// Create token factor to keep old chain connected.
SDOperand Value = ST->getValue();
SDOperand Ptr = ST->getBasePtr();
- // 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.getStore(Chain, Value.getOperand(0), Ptr, ST->getSrcValue(),
- ST->getSrcValueOffset());
+ // 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()) {
+ unsigned Align = ST->getAlignment();
+ MVT::ValueType SVT = Value.getOperand(0).getValueType();
+ unsigned OrigAlign = TLI.getTargetMachine().getTargetData()->
+ getPrefTypeAlignment(getTypeForValueType(SVT));
+ if (Align <= OrigAlign && TLI.isOperationLegal(ISD::STORE, SVT))
+ return DAG.getStore(Chain, Value.getOperand(0), Ptr, ST->getSrcValue(),
+ ST->getSrcValueOffset());
}
// Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
if (LLD->getExtensionType() == ISD::NON_EXTLOAD)
Load = DAG.getLoad(TheSelect->getValueType(0), LLD->getChain(),
Addr,LLD->getSrcValue(),
- LLD->getSrcValueOffset());
+ 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->getLoadedVT(),
+ LLD->isVolatile(),
+ LLD->getAlignment());
}
// Users of the select now use the result of the load.
CombineTo(TheSelect, Load);
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);
// 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.
}
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();
}