// This pass combines dag nodes to form fewer, simpler DAG nodes. It can be run
// both before and after the DAG is legalized.
//
+// This pass is not a substitute for the LLVM IR instcombine pass. This pass is
+// primarily intended to handle simplification opportunities that are implicit
+// in the LLVM IR and exposed by the various codegen lowering phases.
+//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "dagcombine"
SelectionDAG &DAG;
const TargetLowering &TLI;
CombineLevel Level;
+ CodeGenOpt::Level OptLevel;
bool LegalOperations;
bool LegalTypes;
- bool Fast;
// Worklist of all of the nodes that need to be simplified.
std::vector<SDNode*> WorkList;
}
public:
- DAGCombiner(SelectionDAG &D, AliasAnalysis &A, bool fast)
+ DAGCombiner(SelectionDAG &D, AliasAnalysis &A, CodeGenOpt::Level OL)
: DAG(D),
TLI(D.getTargetLoweringInfo()),
Level(Unrestricted),
+ OptLevel(OL),
LegalOperations(false),
LegalTypes(false),
- Fast(fast),
AA(A) {}
/// Run - runs the dag combiner on all nodes in the work list
MVT TruncVT =
MVT::getIntegerVT(VTValSize - N1C->getZExtValue());
// Determine the residual right-shift amount.
- unsigned ShiftAmt = N1C->getZExtValue() - N01C->getZExtValue();
+ signed ShiftAmt = N1C->getZExtValue() - N01C->getZExtValue();
// If the shift is not a no-op (in which case this should be just a sign
// extend already), the truncated to type is legal, sign_extend is legal
// on that type, and the the truncate to that type is both legal and free,
// perform the transform.
- if (ShiftAmt &&
+ if ((ShiftAmt > 0) &&
TLI.isOperationLegalOrCustom(ISD::SIGN_EXTEND, TruncVT) &&
TLI.isOperationLegalOrCustom(ISD::TRUNCATE, VT) &&
TLI.isTruncateFree(VT, TruncVT)) {
if (NarrowLoad.getNode()) {
if (NarrowLoad.getNode() != N0.getNode())
CombineTo(N0.getNode(), NarrowLoad);
- return DAG.getNode(ISD::SIGN_EXTEND, N->getDebugLoc(), VT, NarrowLoad);
+ return SDValue(N, 0); // Return N so it doesn't get rechecked!
}
// See if the value being truncated is already sign extended. If so, just
// 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))
+ if (isa<FrameIndexSDNode>(BasePtr) || isa<RegisterSDNode>(BasePtr))
return false;
// Check #2.
// nor a successor of N. Otherwise, if Op is folded that would
// create a cycle.
+ if (isa<FrameIndexSDNode>(BasePtr) || isa<RegisterSDNode>(BasePtr))
+ continue;
+
// Check for #1.
bool TryNext = false;
for (SDNode::use_iterator II = BasePtr.getNode()->use_begin(),
SDValue Ptr = LD->getBasePtr();
// Try to infer better alignment information than the load already has.
- if (!Fast && LD->isUnindexed()) {
+ if (OptLevel != CodeGenOpt::None && LD->isUnindexed()) {
if (unsigned Align = InferAlignment(Ptr, DAG)) {
if (Align > LD->getAlignment())
return DAG.getExtLoad(LD->getExtensionType(), N->getDebugLoc(),
SDValue Ptr = ST->getBasePtr();
// Try to infer better alignment information than the store already has.
- if (!Fast && ST->isUnindexed()) {
+ if (OptLevel != CodeGenOpt::None && ST->isUnindexed()) {
if (unsigned Align = InferAlignment(Ptr, DAG)) {
if (Align > ST->getAlignment())
return DAG.getTruncStore(Chain, N->getDebugLoc(), Value,
return DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(),
InVec.getValueType(), &Ops[0], Ops.size());
}
+ // If the invec is an UNDEF and if EltNo is a constant, create a new
+ // BUILD_VECTOR with undef elements and the inserted element.
+ if (!LegalOperations && InVec.getOpcode() == ISD::UNDEF &&
+ isa<ConstantSDNode>(EltNo)) {
+ MVT VT = InVec.getValueType();
+ MVT EVT = VT.getVectorElementType();
+ unsigned NElts = VT.getVectorNumElements();
+ SmallVector<SDValue, 8> Ops(NElts, DAG.getUNDEF(EVT));
+ unsigned Elt = cast<ConstantSDNode>(EltNo)->getZExtValue();
+ if (Elt < Ops.size())
+ Ops[Elt] = InVal;
+ return DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(),
+ InVec.getValueType(), &Ops[0], Ops.size());
+ }
return SDValue();
}
}
LoadSDNode *LN0 = NULL;
+ const ShuffleVectorSDNode *SVN = NULL;
if (ISD::isNormalLoad(InVec.getNode())) {
LN0 = cast<LoadSDNode>(InVec);
} else if (InVec.getOpcode() == ISD::SCALAR_TO_VECTOR &&
InVec.getOperand(0).getValueType() == EVT &&
ISD::isNormalLoad(InVec.getOperand(0).getNode())) {
LN0 = cast<LoadSDNode>(InVec.getOperand(0));
- } else if (InVec.getOpcode() == ISD::VECTOR_SHUFFLE) {
+ } else if ((SVN = dyn_cast<ShuffleVectorSDNode>(InVec))) {
// (vextract (vector_shuffle (load $addr), v2, <1, u, u, u>), 1)
// =>
// (load $addr+1*size)
// to examine the mask.
if (BCNumEltsChanged)
return SDValue();
- unsigned Idx = cast<ConstantSDNode>(InVec.getOperand(2).
- getOperand(Elt))->getZExtValue();
- unsigned NumElems = InVec.getOperand(2).getNumOperands();
- InVec = (Idx < NumElems) ? InVec.getOperand(0) : InVec.getOperand(1);
+
+ // Select the input vector, guarding against out of range extract vector.
+ unsigned NumElems = VT.getVectorNumElements();
+ int Idx = (Elt > NumElems) ? -1 : SVN->getMaskElt(Elt);
+ InVec = (Idx < (int)NumElems) ? InVec.getOperand(0) : InVec.getOperand(1);
+
if (InVec.getOpcode() == ISD::BIT_CONVERT)
InVec = InVec.getOperand(0);
if (ISD::isNormalLoad(InVec.getNode())) {
LN0 = cast<LoadSDNode>(InVec);
- Elt = (Idx < NumElems) ? Idx : Idx - NumElems;
+ Elt = (Idx < (int)NumElems) ? Idx : Idx - NumElems;
}
}
SDValue DAGCombiner::visitBUILD_VECTOR(SDNode *N) {
unsigned NumInScalars = N->getNumOperands();
MVT VT = N->getValueType(0);
- unsigned NumElts = VT.getVectorNumElements();
MVT EltType = VT.getVectorElementType();
// Check to see if this is a BUILD_VECTOR of a bunch of EXTRACT_VECTOR_ELT
}
// If everything is good, we can make a shuffle operation.
- MVT IndexVT = MVT::i32;
if (VecIn1.getNode()) {
- SmallVector<SDValue, 8> BuildVecIndices;
+ SmallVector<int, 8> Mask;
for (unsigned i = 0; i != NumInScalars; ++i) {
if (N->getOperand(i).getOpcode() == ISD::UNDEF) {
- BuildVecIndices.push_back(DAG.getUNDEF(IndexVT));
+ Mask.push_back(-1);
continue;
}
- SDValue Extract = N->getOperand(i);
-
// If extracting from the first vector, just use the index directly.
+ SDValue Extract = N->getOperand(i);
SDValue ExtVal = Extract.getOperand(1);
if (Extract.getOperand(0) == VecIn1) {
- if (ExtVal.getValueType() == IndexVT)
- BuildVecIndices.push_back(ExtVal);
- else {
- unsigned Idx = cast<ConstantSDNode>(ExtVal)->getZExtValue();
- BuildVecIndices.push_back(DAG.getConstant(Idx, IndexVT));
- }
+ unsigned ExtIndex = cast<ConstantSDNode>(ExtVal)->getZExtValue();
+ if (ExtIndex > VT.getVectorNumElements())
+ return SDValue();
+
+ Mask.push_back(ExtIndex);
continue;
}
// Otherwise, use InIdx + VecSize
unsigned Idx = cast<ConstantSDNode>(ExtVal)->getZExtValue();
- BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars, IndexVT));
+ Mask.push_back(Idx+NumInScalars);
}
// Add count and size info.
- MVT BuildVecVT = MVT::getVectorVT(IndexVT, NumElts);
- if (!TLI.isTypeLegal(BuildVecVT) && LegalTypes)
+ if (!TLI.isTypeLegal(VT) && LegalTypes)
return SDValue();
// Return the new VECTOR_SHUFFLE node.
- SDValue Ops[5];
+ SDValue Ops[2];
Ops[0] = VecIn1;
- if (VecIn2.getNode()) {
- Ops[1] = VecIn2;
- } else {
- // Use an undef build_vector as input for the second operand.
- std::vector<SDValue> UnOps(NumInScalars,
- DAG.getUNDEF(EltType));
- Ops[1] = DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), VT,
- &UnOps[0], UnOps.size());
- AddToWorkList(Ops[1].getNode());
- }
-
- Ops[2] = DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), BuildVecVT,
- &BuildVecIndices[0], BuildVecIndices.size());
- return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getDebugLoc(), VT, Ops, 3);
+ Ops[1] = VecIn2.getNode() ? VecIn2 : DAG.getUNDEF(VT);
+ return DAG.getVectorShuffle(VT, N->getDebugLoc(), Ops[0], Ops[1], &Mask[0]);
}
return SDValue();
}
SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) {
- SDValue ShufMask = N->getOperand(2);
- unsigned NumElts = ShufMask.getNumOperands();
+ return SDValue();
+
+ MVT VT = N->getValueType(0);
+ unsigned NumElts = VT.getVectorNumElements();
SDValue N0 = N->getOperand(0);
SDValue N1 = N->getOperand(1);
assert(N0.getValueType().getVectorNumElements() == NumElts &&
"Vector shuffle must be normalized in DAG");
- // 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))->getZExtValue() != 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))->getZExtValue() !=
- 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))->getZExtValue();
- 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;
- }
- }
- }
-
- // Normalize unary shuffle so the RHS is undef.
- if (isUnary && VecNum == 1)
- std::swap(N0, N1);
+ // FIXME: implement canonicalizations from DAG.getVectorShuffle()
// If it is a splat, check if the argument vector is a build_vector with
// all scalar elements the same.
- if (isSplat) {
+ if (cast<ShuffleVectorSDNode>(N)->isSplat()) {
SDNode *V = N0.getNode();
+
// 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
if (V->getOpcode() == ISD::BUILD_VECTOR) {
unsigned NumElems = V->getNumOperands();
+ unsigned BaseIdx = cast<ShuffleVectorSDNode>(N)->getSplatIndex();
if (NumElems > BaseIdx) {
SDValue Base;
bool AllSame = true;
}
}
}
-
- // 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<SDValue, 8> MappedOps;
-
- for (unsigned i = 0; i != NumElts; ++i) {
- if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF ||
- cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() <
- NumElts) {
- MappedOps.push_back(ShufMask.getOperand(i));
- } else {
- unsigned NewIdx =
- cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() -
- NumElts;
- MappedOps.push_back(DAG.getConstant(NewIdx,
- ShufMask.getOperand(i).getValueType()));
- }
- }
-
- ShufMask = DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(),
- ShufMask.getValueType(),
- &MappedOps[0], MappedOps.size());
- AddToWorkList(ShufMask.getNode());
- return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getDebugLoc(),
- N->getValueType(0), N0,
- DAG.getUNDEF(N->getValueType(0)),
- ShufMask);
- }
-
return SDValue();
}
/// e.g. AND V, <0xffffffff, 0, 0xffffffff, 0>. ==>
/// vector_shuffle V, Zero, <0, 4, 2, 4>
SDValue DAGCombiner::XformToShuffleWithZero(SDNode *N) {
+ MVT VT = N->getValueType(0);
+ DebugLoc dl = N->getDebugLoc();
SDValue LHS = N->getOperand(0);
SDValue RHS = N->getOperand(1);
if (N->getOpcode() == ISD::AND) {
if (RHS.getOpcode() == ISD::BIT_CONVERT)
RHS = RHS.getOperand(0);
if (RHS.getOpcode() == ISD::BUILD_VECTOR) {
- std::vector<SDValue> IdxOps;
- unsigned NumOps = RHS.getNumOperands();
- unsigned NumElts = NumOps;
+ SmallVector<int, 8> Indices;
+ unsigned NumElts = RHS.getNumOperands();
for (unsigned i = 0; i != NumElts; ++i) {
SDValue Elt = RHS.getOperand(i);
if (!isa<ConstantSDNode>(Elt))
return SDValue();
else if (cast<ConstantSDNode>(Elt)->isAllOnesValue())
- IdxOps.push_back(DAG.getIntPtrConstant(i));
+ Indices.push_back(i);
else if (cast<ConstantSDNode>(Elt)->isNullValue())
- IdxOps.push_back(DAG.getIntPtrConstant(NumElts));
+ Indices.push_back(NumElts);
else
return SDValue();
}
// Let's see if the target supports this vector_shuffle.
- if (!TLI.isVectorClearMaskLegal(IdxOps, TLI.getPointerTy(), DAG))
+ MVT RVT = RHS.getValueType();
+ if (!TLI.isVectorClearMaskLegal(Indices, RVT))
return SDValue();
// Return the new VECTOR_SHUFFLE node.
- MVT EVT = RHS.getValueType().getVectorElementType();
- MVT VT = MVT::getVectorVT(EVT, NumElts);
- MVT MaskVT = MVT::getVectorVT(TLI.getPointerTy(), NumElts);
- std::vector<SDValue> Ops;
- LHS = DAG.getNode(ISD::BIT_CONVERT, LHS.getDebugLoc(), VT, LHS);
- Ops.push_back(LHS);
- AddToWorkList(LHS.getNode());
- std::vector<SDValue> ZeroOps(NumElts, DAG.getConstant(0, EVT));
- Ops.push_back(DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(),
- VT, &ZeroOps[0], ZeroOps.size()));
- Ops.push_back(DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(),
- MaskVT, &IdxOps[0], IdxOps.size()));
- SDValue Result = DAG.getNode(ISD::VECTOR_SHUFFLE, N->getDebugLoc(),
- VT, &Ops[0], Ops.size());
-
- if (VT != N->getValueType(0))
- Result = DAG.getNode(ISD::BIT_CONVERT, N->getDebugLoc(),
- N->getValueType(0), Result);
-
- return Result;
+ MVT EVT = RVT.getVectorElementType();
+ SmallVector<SDValue,8> ZeroOps(RVT.getVectorNumElements(),
+ DAG.getConstant(0, EVT));
+ SDValue Zero = DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(),
+ RVT, &ZeroOps[0], ZeroOps.size());
+ LHS = DAG.getNode(ISD::BIT_CONVERT, dl, RVT, LHS);
+ SDValue Shuf = DAG.getVectorShuffle(RVT, dl, LHS, Zero, &Indices[0]);
+ return DAG.getNode(ISD::BIT_CONVERT, dl, VT, Shuf);
}
}
// Get the offsets to the 0 and 1 element of the array so that we can
// select between them.
SDValue Zero = DAG.getIntPtrConstant(0);
- unsigned EltSize = (unsigned)TD.getTypePaddedSize(Elts[0]->getType());
+ unsigned EltSize = (unsigned)TD.getTypeAllocSize(Elts[0]->getType());
SDValue One = DAG.getIntPtrConstant(EltSize);
SDValue Cond = DAG.getSetCC(DL,
// Get alias information for node.
SDValue Ptr;
- int64_t Size;
- const Value *SrcValue;
- int SrcValueOffset;
+ int64_t Size = 0;
+ const Value *SrcValue = 0;
+ int SrcValueOffset = 0;
bool IsLoad = FindAliasInfo(N, Ptr, Size, SrcValue, SrcValueOffset);
// Starting off.
case ISD::STORE: {
// Get alias information for Chain.
SDValue OpPtr;
- int64_t OpSize;
- const Value *OpSrcValue;
- int OpSrcValueOffset;
+ int64_t OpSize = 0;
+ const Value *OpSrcValue = 0;
+ int OpSrcValueOffset = 0;
bool IsOpLoad = FindAliasInfo(Chain.getNode(), OpPtr, OpSize,
OpSrcValue, OpSrcValueOffset);
// SelectionDAG::Combine - This is the entry point for the file.
//
-void SelectionDAG::Combine(CombineLevel Level, AliasAnalysis &AA, bool Fast) {
+void SelectionDAG::Combine(CombineLevel Level, AliasAnalysis &AA,
+ CodeGenOpt::Level OptLevel) {
/// run - This is the main entry point to this class.
///
- DAGCombiner(*this, AA, Fast).Run(Level);
+ DAGCombiner(*this, AA, OptLevel).Run(Level);
}
projects / oota-llvm.git / blobdiff