#define DEBUG_TYPE "dagcombine"
#include "llvm/CodeGen/SelectionDAG.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Target/TargetData.h"
+#include "llvm/Target/TargetFrameInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
bool NotExtCompare = false);
SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
ISD::CondCode Cond, bool foldBooleans = true);
- bool SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp, unsigned HiOp);
+ SDOperand SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp,
+ unsigned HiOp);
SDOperand ConstantFoldBIT_CONVERTofBUILD_VECTOR(SDNode *, MVT::ValueType);
SDOperand BuildSDIV(SDNode *N);
SDOperand BuildUDIV(SDNode *N);
SDOperand RV = combine(N);
- if (RV.Val) {
- ++NodesCombined;
- // If we get back the same node we passed in, rather than a new node or
- // zero, we know that the node must have defined multiple values and
- // 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!");
-
- 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);
- else {
- assert(N->getValueType(0) == RV.getValueType() && "Type mismatch");
- SDOperand OpV = RV;
- DAG.ReplaceAllUsesWith(N, &OpV, &NowDead);
- }
-
- // Push the new node and any users onto the worklist
- AddToWorkList(RV.Val);
- AddUsersToWorkList(RV.Val);
-
- // 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]);
-
- // Finally, since the node is now dead, remove it from the graph.
- DAG.DeleteNode(N);
- }
+ if (RV.Val == 0)
+ continue;
+
+ ++NodesCombined;
+
+ // If we get back the same node we passed in, rather than a new node or
+ // zero, we know that the node must have defined multiple values and
+ // 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)
+ continue;
+
+ assert(N->getOpcode() != ISD::DELETED_NODE &&
+ RV.Val->getOpcode() != ISD::DELETED_NODE &&
+ "Node was deleted but visit returned new node!");
+
+ 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);
+ else {
+ assert(N->getValueType(0) == RV.getValueType() &&
+ N->getNumValues() == 1 && "Type mismatch");
+ SDOperand OpV = RV;
+ DAG.ReplaceAllUsesWith(N, &OpV, &NowDead);
}
+
+ // Push the new node and any users onto the worklist
+ AddToWorkList(RV.Val);
+ AddUsersToWorkList(RV.Val);
+
+ // Add any uses of the old node to the worklist in case this node is the
+ // last one that uses them. They may become dead after this node is
+ // deleted.
+ for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
+ AddToWorkList(N->getOperand(i).Val);
+
+ // 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]);
+
+ // Finally, since the node is now dead, remove it from the graph.
+ DAG.DeleteNode(N);
}
// If the root changed (e.g. it was a dead load, update the root).
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());
+ SDOperand Op0 = Slct.getOperand(0);
+ bool isInt = MVT::isInteger(isSlctCC ? Op0.getValueType()
+ : Op0.getOperand(0).getValueType());
CC = ISD::getSetCCInverse(CC, isInt);
DoXform = true;
InvCC = true;
// X%C to the equivalent of X-X/C*C.
if (N1C && !N1C->isNullValue()) {
SDOperand Div = DAG.getNode(ISD::SDIV, VT, N0, N1);
+ AddToWorkList(Div.Val);
SDOperand OptimizedDiv = combine(Div.Val);
if (OptimizedDiv.Val && OptimizedDiv.Val != Div.Val) {
SDOperand Mul = DAG.getNode(ISD::MUL, VT, OptimizedDiv, N1);
/// 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) {
+SDOperand 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;
+ SDOperand Res = DAG.getNode(LoOp, N->getValueType(0), N->op_begin(),
+ N->getNumOperands());
+ return CombineTo(N, Res, Res);
}
// If the low half is not needed, just compute the high half.
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;
+ SDOperand Res = DAG.getNode(HiOp, N->getValueType(1), N->op_begin(),
+ N->getNumOperands());
+ return CombineTo(N, Res, Res);
}
// If both halves are used, return as it is.
if (LoExists && HiExists)
- return false;
+ return SDOperand();
// 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());
+ AddToWorkList(Lo.Val);
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 (LoOpt.Val && LoOpt.Val != Lo.Val &&
+ TLI.isOperationLegal(LoOpt.getOpcode(), LoOpt.getValueType()))
+ return CombineTo(N, LoOpt, LoOpt);
}
if (HiExists) {
SDOperand Hi = DAG.getNode(HiOp, N->getValueType(1),
N->op_begin(), N->getNumOperands());
+ AddToWorkList(Hi.Val);
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);
+ TLI.isOperationLegal(HiOpt.getOpcode(), HiOpt.getValueType()))
+ return CombineTo(N, HiOpt, HiOpt);
}
-
- return RetVal;
+ return SDOperand();
}
SDOperand DAGCombiner::visitSMUL_LOHI(SDNode *N) {
-
- if (SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHS))
- return SDOperand();
+ SDOperand Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHS);
+ if (Res.Val) return Res;
return SDOperand();
}
SDOperand DAGCombiner::visitUMUL_LOHI(SDNode *N) {
-
- if (SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHU))
- return SDOperand();
+ SDOperand Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHU);
+ if (Res.Val) return Res;
return SDOperand();
}
SDOperand DAGCombiner::visitSDIVREM(SDNode *N) {
-
- if (SimplifyNodeWithTwoResults(N, ISD::SDIV, ISD::SREM))
- return SDOperand();
+ SDOperand Res = SimplifyNodeWithTwoResults(N, ISD::SDIV, ISD::SREM);
+ if (Res.Val) return Res;
return SDOperand();
}
SDOperand DAGCombiner::visitUDIVREM(SDNode *N) {
-
- if (SimplifyNodeWithTwoResults(N, ISD::UDIV, ISD::UREM))
- return SDOperand();
+ SDOperand Res = SimplifyNodeWithTwoResults(N, ISD::UDIV, ISD::UREM);
+ if (Res.Val) return Res;
return SDOperand();
}
if (N1C && N0.getOpcode() == ISD::LOAD) {
LoadSDNode *LN0 = cast<LoadSDNode>(N0);
if (LN0->getExtensionType() != ISD::SEXTLOAD &&
- LN0->getAddressingMode() == ISD::UNINDEXED &&
- N0.hasOneUse()) {
+ LN0->isUnindexed() && N0.hasOneUse()) {
MVT::ValueType EVT, LoadedVT;
if (N1C->getValue() == 255)
EVT = MVT::i8;
if (N0.getOpcode() == ISD::FP_EXTEND && VT == N0.getOperand(0).getValueType())
return N0.getOperand(0);
+ // fold (fp_round (fp_round x)) -> (fp_round x)
+ if (N0.getOpcode() == ISD::FP_ROUND) {
+ // This is a value preserving truncation if both round's are.
+ bool IsTrunc = N->getConstantOperandVal(1) == 1 &&
+ N0.Val->getConstantOperandVal(1) == 1;
+ return DAG.getNode(ISD::FP_ROUND, VT, N0.getOperand(0),
+ DAG.getIntPtrConstant(IsTrunc));
+ }
+
// fold (fp_round (copysign X, Y)) -> (copysign (fp_round X), Y)
if (N0.getOpcode() == ISD::FCOPYSIGN && N0.Val->hasOneUse()) {
SDOperand Tmp = DAG.getNode(ISD::FP_ROUND, VT, N0.getOperand(0), N1);
SDOperand Ptr;
MVT::ValueType VT;
if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
- if (LD->getAddressingMode() != ISD::UNINDEXED)
+ if (LD->isIndexed())
return false;
VT = LD->getLoadedVT();
if (!TLI.isIndexedLoadLegal(ISD::PRE_INC, VT) &&
return false;
Ptr = LD->getBasePtr();
} else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
- if (ST->getAddressingMode() != ISD::UNINDEXED)
+ if (ST->isIndexed())
return false;
VT = ST->getStoredVT();
if (!TLI.isIndexedStoreLegal(ISD::PRE_INC, VT) &&
SDOperand Ptr;
MVT::ValueType VT;
if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
- if (LD->getAddressingMode() != ISD::UNINDEXED)
+ if (LD->isIndexed())
return false;
VT = LD->getLoadedVT();
if (!TLI.isIndexedLoadLegal(ISD::POST_INC, VT) &&
return false;
Ptr = LD->getBasePtr();
} else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
- if (ST->getAddressingMode() != ISD::UNINDEXED)
+ if (ST->isIndexed())
return false;
VT = ST->getStoredVT();
if (!TLI.isIndexedStoreLegal(ISD::POST_INC, VT) &&
return false;
}
+/// InferAlignment - If we can infer some alignment information from this
+/// pointer, return it.
+static unsigned InferAlignment(SDOperand Ptr, SelectionDAG &DAG) {
+ // If this is a direct reference to a stack slot, use information about the
+ // stack slot's alignment.
+ int FrameIdx = 1 << 31;
+ int64_t FrameOffset = 0;
+ if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
+ FrameIdx = FI->getIndex();
+ } else if (Ptr.getOpcode() == ISD::ADD &&
+ isa<ConstantSDNode>(Ptr.getOperand(1)) &&
+ isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
+ FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
+ FrameOffset = Ptr.getConstantOperandVal(1);
+ }
+
+ if (FrameIdx != (1 << 31)) {
+ // FIXME: Handle FI+CST.
+ const MachineFrameInfo &MFI = *DAG.getMachineFunction().getFrameInfo();
+ if (MFI.isFixedObjectIndex(FrameIdx)) {
+ int64_t ObjectOffset = MFI.getObjectOffset(FrameIdx);
+
+ // The alignment of the frame index can be determined from its offset from
+ // the incoming frame position. If the frame object is at offset 32 and
+ // the stack is guaranteed to be 16-byte aligned, then we know that the
+ // object is 16-byte aligned.
+ unsigned StackAlign = DAG.getTarget().getFrameInfo()->getStackAlignment();
+ unsigned Align = MinAlign(ObjectOffset, StackAlign);
+
+ // Finally, the frame object itself may have a known alignment. Factor
+ // the alignment + offset into a new alignment. For example, if we know
+ // the FI is 8 byte aligned, but the pointer is 4 off, we really have a
+ // 4-byte alignment of the resultant pointer. Likewise align 4 + 4-byte
+ // offset = 4-byte alignment, align 4 + 1-byte offset = align 1, etc.
+ unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
+ FrameOffset);
+ return std::max(Align, FIInfoAlign);
+ }
+ }
+
+ return 0;
+}
SDOperand DAGCombiner::visitLOAD(SDNode *N) {
LoadSDNode *LD = cast<LoadSDNode>(N);
SDOperand Chain = LD->getChain();
SDOperand Ptr = LD->getBasePtr();
+
+ // Try to infer better alignment information than the load already has.
+ if (LD->isUnindexed()) {
+ if (unsigned Align = InferAlignment(Ptr, DAG)) {
+ if (Align > LD->getAlignment())
+ return DAG.getExtLoad(LD->getExtensionType(), LD->getValueType(0),
+ Chain, Ptr, LD->getSrcValue(),
+ LD->getSrcValueOffset(), LD->getLoadedVT(),
+ LD->isVolatile(), Align);
+ }
+ }
+
// 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
// v1, chain2 = load chain1, loc
// v2, chain3 = load chain2, loc
// v3 = add v2, c
- // Now we replace use of v1 with undef, use of chain2 with chain1.
- // ReplaceAllUsesWith() will iterate through uses of the first load and
- // update operands:
- // v1, chain2 = load chain1, loc
- // v2, chain3 = load chain1, loc
- // v3 = add v2, c
- // Now the second load is the same as the first load, SelectionDAG cse
- // will ensure the use of second load is replaced with the first load.
- // v1, chain2 = load chain1, loc
- // v3 = add v1, c
- // Then v1 is replaced with undef and bad things happen.
+ // Now we replace use of chain2 with chain1. This makes the second load
+ // isomorphic to the one we are deleting, and thus makes this load live.
std::vector<SDNode*> NowDead;
- SDOperand Undef = DAG.getNode(ISD::UNDEF, N->getValueType(0));
DOUT << "\nReplacing.6 "; DEBUG(N->dump(&DAG));
- DOUT << "\nWith: "; DEBUG(Undef.Val->dump(&DAG));
- DOUT << " and 1 other value\n";
- DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Undef, &NowDead);
+ DOUT << "\nWith chain: "; DEBUG(Chain.Val->dump(&DAG));
+ DOUT << "\n";
DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Chain, &NowDead);
- removeFromWorkList(N);
for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
removeFromWorkList(NowDead[i]);
- DAG.DeleteNode(N);
+ if (N->use_empty()) {
+ removeFromWorkList(N);
+ DAG.DeleteNode(N);
+ }
return SDOperand(N, 0); // Return N so it doesn't get rechecked!
}
} else {
DOUT << " and 2 other values\n";
DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Undef, &NowDead);
DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1),
- DAG.getNode(ISD::UNDEF, N->getValueType(1)),
+ DAG.getNode(ISD::UNDEF, N->getValueType(1)),
&NowDead);
DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 2), Chain, &NowDead);
removeFromWorkList(N);
SDOperand Value = ST->getValue();
SDOperand Ptr = ST->getBasePtr();
+ // Try to infer better alignment information than the store already has.
+ if (ST->isUnindexed()) {
+ if (unsigned Align = InferAlignment(Ptr, DAG)) {
+ if (Align > ST->getAlignment())
+ return DAG.getTruncStore(Chain, Value, Ptr, ST->getSrcValue(),
+ ST->getSrcValueOffset(), ST->getStoredVT(),
+ ST->isVolatile(), Align);
+ }
+ }
+
// 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) {
+ ST->isUnindexed()) {
unsigned Align = ST->getAlignment();
MVT::ValueType SVT = Value.getOperand(0).getValueType();
unsigned OrigAlign = TLI.getTargetMachine().getTargetData()->
SDOperand ReplStore;
if (ST->isTruncatingStore()) {
ReplStore = DAG.getTruncStore(BetterChain, Value, Ptr,
- ST->getSrcValue(), ST->getSrcValueOffset(), ST->getStoredVT(),
- ST->isVolatile(), ST->getAlignment());
+ 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());
+ ST->getSrcValue(), ST->getSrcValueOffset(),
+ ST->isVolatile(), ST->getAlignment());
}
// Create token to keep both nodes around.
return SDOperand(N, 0);
// FIXME: is there such a thing as a truncating indexed store?
- if (ST->isTruncatingStore() && ST->getAddressingMode() == ISD::UNINDEXED &&
+ if (ST->isTruncatingStore() && ST->isUnindexed() &&
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:
// is dead/noop.
if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(Value)) {
if (Ld->getBasePtr() == Ptr && ST->getStoredVT() == Ld->getLoadedVT() &&
- ST->getAddressingMode() == ISD::UNINDEXED &&
- !ST->isVolatile() &&
+ ST->isUnindexed() && !ST->isVolatile() &&
// There can't be any side effects between the load and store, such as
// a call or store.
Chain.reachesChainWithoutSideEffects(SDOperand(Ld, 1))) {
}
}
+ // If this is an FP_ROUND or TRUNC followed by a store, fold this into a
+ // truncating store. We can do this even if this is already a truncstore.
+ if ((Value.getOpcode() == ISD::FP_ROUND || Value.getOpcode() == ISD::TRUNCATE)
+ && TLI.isTypeLegal(Value.getOperand(0).getValueType()) &&
+ Value.Val->hasOneUse() && ST->isUnindexed() &&
+ TLI.isTruncStoreLegal(Value.getOperand(0).getValueType(),
+ ST->getStoredVT())) {
+ return DAG.getTruncStore(Chain, Value.getOperand(0), Ptr, ST->getSrcValue(),
+ ST->getSrcValueOffset(), ST->getStoredVT(),
+ ST->isVolatile(), ST->getAlignment());
+ }
+
return SDOperand();
}