#include "llvm/Target/TargetOptions.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Support/Compiler.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <set>
using namespace llvm;
//------------------------------ DAGCombiner ---------------------------------//
- class VISIBILITY_HIDDEN DAGCombiner {
+ class DAGCombiner {
SelectionDAG &DAG;
const TargetLowering &TLI;
CombineLevel Level;
/// overlap.
bool isAlias(SDValue Ptr1, int64_t Size1,
const Value *SrcValue1, int SrcValueOffset1,
+ unsigned SrcValueAlign1,
SDValue Ptr2, int64_t Size2,
- const Value *SrcValue2, int SrcValueOffset2) const;
+ const Value *SrcValue2, int SrcValueOffset2,
+ unsigned SrcValueAlign2) const;
/// FindAliasInfo - Extracts the relevant alias information from the memory
/// node. Returns true if the operand was a load.
bool FindAliasInfo(SDNode *N,
SDValue &Ptr, int64_t &Size,
- const Value *&SrcValue, int &SrcValueOffset) const;
+ const Value *&SrcValue, int &SrcValueOffset,
+ unsigned &SrcValueAlignment) const;
/// FindBetterChain - Walk up chain skipping non-aliasing memory nodes,
/// looking for a better chain (aliasing node.)
namespace {
/// WorkListRemover - This class is a DAGUpdateListener that removes any deleted
/// nodes from the worklist.
-class VISIBILITY_HIDDEN WorkListRemover :
- public SelectionDAG::DAGUpdateListener {
+class WorkListRemover : public SelectionDAG::DAGUpdateListener {
DAGCombiner &DC;
public:
explicit WorkListRemover(DAGCombiner &dc) : DC(dc) {}
bool AddTo) {
assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
++NodesCombined;
- DOUT << "\nReplacing.1 "; DEBUG(N->dump(&DAG));
- DOUT << "\nWith: "; DEBUG(To[0].getNode()->dump(&DAG));
- DOUT << " and " << NumTo-1 << " other values\n";
- DEBUG(for (unsigned i = 0, e = NumTo; i != e; ++i)
+ DEBUG(errs() << "\nReplacing.1 ";
+ N->dump(&DAG);
+ errs() << "\nWith: ";
+ To[0].getNode()->dump(&DAG);
+ errs() << " and " << NumTo-1 << " other values\n";
+ for (unsigned i = 0, e = NumTo; i != e; ++i)
assert(N->getValueType(i) == To[i].getValueType() &&
"Cannot combine value to value of different type!"));
WorkListRemover DeadNodes(*this);
// Replace the old value with the new one.
++NodesCombined;
- DOUT << "\nReplacing.2 "; DEBUG(TLO.Old.getNode()->dump(&DAG));
- DOUT << "\nWith: "; DEBUG(TLO.New.getNode()->dump(&DAG));
- DOUT << '\n';
+ DEBUG(errs() << "\nReplacing.2 ";
+ TLO.Old.getNode()->dump(&DAG);
+ errs() << "\nWith: ";
+ TLO.New.getNode()->dump(&DAG);
+ errs() << '\n');
CommitTargetLoweringOpt(TLO);
return true;
RV.getNode()->getOpcode() != ISD::DELETED_NODE &&
"Node was deleted but visit returned new node!");
- DOUT << "\nReplacing.3 "; DEBUG(N->dump(&DAG));
- DOUT << "\nWith: "; DEBUG(RV.getNode()->dump(&DAG));
- DOUT << '\n';
+ DEBUG(errs() << "\nReplacing.3 ";
+ N->dump(&DAG);
+ errs() << "\nWith: ";
+ RV.getNode()->dump(&DAG);
+ errs() << '\n');
WorkListRemover DeadNodes(*this);
if (N->getNumValues() == RV.getNode()->getNumValues())
DAG.ReplaceAllUsesWith(N, RV.getNode(), &DeadNodes);
break;
case ISD::TokenFactor:
- if ((CombinerAA || Op.hasOneUse()) &&
+ if (Op.hasOneUse() &&
std::find(TFs.begin(), TFs.end(), Op.getNode()) == TFs.end()) {
// Queue up for processing.
TFs.push_back(Op.getNode());
}
}
}
-
+
SDValue Result;
// If we've change things around then replace token factor.
// fold (zext_inreg (extload x)) -> (zextload x)
if (ISD::isEXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode())) {
LoadSDNode *LN0 = cast<LoadSDNode>(N0);
- EVT EVT = LN0->getMemoryVT();
+ EVT MemVT = LN0->getMemoryVT();
// If we zero all the possible extended bits, then we can turn this into
// a zextload if we are running before legalize or the operation is legal.
unsigned BitWidth = N1.getValueSizeInBits();
if (DAG.MaskedValueIsZero(N1, APInt::getHighBitsSet(BitWidth,
- BitWidth - EVT.getSizeInBits())) &&
+ BitWidth - MemVT.getSizeInBits())) &&
((!LegalOperations && !LN0->isVolatile()) ||
- TLI.isLoadExtLegal(ISD::ZEXTLOAD, EVT))) {
+ TLI.isLoadExtLegal(ISD::ZEXTLOAD, MemVT))) {
SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, N0.getDebugLoc(), VT,
LN0->getChain(), LN0->getBasePtr(),
LN0->getSrcValue(),
- LN0->getSrcValueOffset(), EVT,
+ LN0->getSrcValueOffset(), MemVT,
LN0->isVolatile(), LN0->getAlignment());
AddToWorkList(N);
CombineTo(N0.getNode(), ExtLoad, ExtLoad.getValue(1));
if (ISD::isSEXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode()) &&
N0.hasOneUse()) {
LoadSDNode *LN0 = cast<LoadSDNode>(N0);
- EVT EVT = LN0->getMemoryVT();
+ EVT MemVT = LN0->getMemoryVT();
// If we zero all the possible extended bits, then we can turn this into
// a zextload if we are running before legalize or the operation is legal.
unsigned BitWidth = N1.getValueSizeInBits();
if (DAG.MaskedValueIsZero(N1, APInt::getHighBitsSet(BitWidth,
- BitWidth - EVT.getSizeInBits())) &&
+ BitWidth - MemVT.getSizeInBits())) &&
((!LegalOperations && !LN0->isVolatile()) ||
- TLI.isLoadExtLegal(ISD::ZEXTLOAD, EVT))) {
+ TLI.isLoadExtLegal(ISD::ZEXTLOAD, MemVT))) {
SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, N0.getDebugLoc(), VT,
LN0->getChain(),
LN0->getBasePtr(), LN0->getSrcValue(),
- LN0->getSrcValueOffset(), EVT,
+ LN0->getSrcValueOffset(), MemVT,
LN0->isVolatile(), LN0->getAlignment());
AddToWorkList(N);
CombineTo(N0.getNode(), ExtLoad, ExtLoad.getValue(1));
EVT ExtVT = MVT::Other;
uint32_t ActiveBits = N1C->getAPIntValue().getActiveBits();
if (ActiveBits > 0 && APIntOps::isMask(ActiveBits, N1C->getAPIntValue()))
- ExtVT = EVT::getIntegerVT(ActiveBits);
+ ExtVT = EVT::getIntegerVT(*DAG.getContext(), ActiveBits);
EVT LoadedVT = LN0->getMemoryVT();
// For big endian targets, we need to add an offset to the pointer to
// load the correct bytes. For little endian systems, we merely need to
// read fewer bytes from the same pointer.
- unsigned LVTStoreBytes = LoadedVT.getStoreSizeInBits()/8;
- unsigned EVTStoreBytes = ExtVT.getStoreSizeInBits()/8;
+ unsigned LVTStoreBytes = LoadedVT.getStoreSize();
+ unsigned EVTStoreBytes = ExtVT.getStoreSize();
unsigned PtrOff = LVTStoreBytes - EVTStoreBytes;
unsigned Alignment = LN0->getAlignment();
SDValue NewPtr = LN0->getBasePtr();
// sext_inreg.
if (N1C && N0.getOpcode() == ISD::SHL && N1 == N0.getOperand(1)) {
unsigned LowBits = VT.getSizeInBits() - (unsigned)N1C->getZExtValue();
- EVT EVT = EVT::getIntegerVT(LowBits);
+ EVT EVT = EVT::getIntegerVT(*DAG.getContext(), LowBits);
if ((!LegalOperations || TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, EVT)))
return DAG.getNode(ISD::SIGN_EXTEND_INREG, N->getDebugLoc(), VT,
N0.getOperand(0), DAG.getValueType(EVT));
// Determine what the truncate's result bitsize and type would be.
unsigned VTValSize = VT.getSizeInBits();
EVT TruncVT =
- EVT::getIntegerVT(VTValSize - N1C->getZExtValue());
+ EVT::getIntegerVT(*DAG.getContext(), VTValSize - N1C->getZExtValue());
// Determine the residual right-shift amount.
signed ShiftAmt = N1C->getZExtValue() - N01C->getZExtValue();
if ((ISD::isSEXTLoad(N0.getNode()) || ISD::isEXTLoad(N0.getNode())) &&
ISD::isUNINDEXEDLoad(N0.getNode()) && N0.hasOneUse()) {
LoadSDNode *LN0 = cast<LoadSDNode>(N0);
- EVT EVT = LN0->getMemoryVT();
+ EVT MemVT = LN0->getMemoryVT();
if ((!LegalOperations && !LN0->isVolatile()) ||
- TLI.isLoadExtLegal(ISD::SEXTLOAD, EVT)) {
+ TLI.isLoadExtLegal(ISD::SEXTLOAD, MemVT)) {
SDValue ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, N->getDebugLoc(), VT,
LN0->getChain(),
LN0->getBasePtr(), LN0->getSrcValue(),
- LN0->getSrcValueOffset(), EVT,
+ LN0->getSrcValueOffset(), MemVT,
LN0->isVolatile(), LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.getNode(),
if ((ISD::isZEXTLoad(N0.getNode()) || ISD::isEXTLoad(N0.getNode())) &&
ISD::isUNINDEXEDLoad(N0.getNode()) && N0.hasOneUse()) {
LoadSDNode *LN0 = cast<LoadSDNode>(N0);
- EVT EVT = LN0->getMemoryVT();
+ EVT MemVT = LN0->getMemoryVT();
if ((!LegalOperations && !LN0->isVolatile()) ||
- TLI.isLoadExtLegal(ISD::ZEXTLOAD, EVT)) {
+ TLI.isLoadExtLegal(ISD::ZEXTLOAD, MemVT)) {
SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, N->getDebugLoc(), VT,
LN0->getChain(),
LN0->getBasePtr(), LN0->getSrcValue(),
- LN0->getSrcValueOffset(), EVT,
+ LN0->getSrcValueOffset(), MemVT,
LN0->isVolatile(), LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.getNode(),
!ISD::isNON_EXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode()) &&
N0.hasOneUse()) {
LoadSDNode *LN0 = cast<LoadSDNode>(N0);
- EVT EVT = LN0->getMemoryVT();
+ EVT MemVT = LN0->getMemoryVT();
SDValue ExtLoad = DAG.getExtLoad(LN0->getExtensionType(), N->getDebugLoc(),
VT, LN0->getChain(), LN0->getBasePtr(),
LN0->getSrcValue(),
- LN0->getSrcValueOffset(), EVT,
+ LN0->getSrcValueOffset(), MemVT,
LN0->isVolatile(), LN0->getAlignment());
CombineTo(N, ExtLoad);
CombineTo(N0.getNode(),
unsigned EVTBits = ExtVT.getSizeInBits();
unsigned ShAmt = 0;
- if (N0.getOpcode() == ISD::SRL && N0.hasOneUse()) {
+ if (N0.getOpcode() == ISD::SRL && N0.hasOneUse() && ExtVT.isRound()) {
if (ConstantSDNode *N01 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
ShAmt = N01->getZExtValue();
// Is the shift amount a multiple of size of VT?
if ((ShAmt & (EVTBits-1)) == 0) {
N0 = N0.getOperand(0);
- if (N0.getValueType().getSizeInBits() <= EVTBits)
+ // Is the load width a multiple of size of VT?
+ if ((N0.getValueType().getSizeInBits() & (EVTBits-1)) != 0)
return SDValue();
}
}
TLI.isConsecutiveLoad(LD2, LD1, LD1VT.getSizeInBits()/8, 1, MFI)) {
unsigned Align = LD1->getAlignment();
unsigned NewAlign = TLI.getTargetData()->
- getABITypeAlignment(VT.getTypeForEVT());
+ getABITypeAlignment(VT.getTypeForEVT(*DAG.getContext()));
if (NewAlign <= Align &&
(!LegalOperations || TLI.isOperationLegal(ISD::LOAD, VT)))
(!LegalOperations || TLI.isOperationLegal(ISD::LOAD, VT))) {
LoadSDNode *LN0 = cast<LoadSDNode>(N0);
unsigned Align = TLI.getTargetData()->
- getABITypeAlignment(VT.getTypeForEVT());
+ getABITypeAlignment(VT.getTypeForEVT(*DAG.getContext()));
unsigned OrigAlign = LN0->getAlignment();
if (Align <= OrigAlign) {
isa<ConstantFPSDNode>(N0.getOperand(0)) &&
VT.isInteger() && !VT.isVector()) {
unsigned OrigXWidth = N0.getOperand(1).getValueType().getSizeInBits();
- EVT IntXVT = EVT::getIntegerVT(OrigXWidth);
+ EVT IntXVT = EVT::getIntegerVT(*DAG.getContext(), OrigXWidth);
if (TLI.isTypeLegal(IntXVT) || !LegalTypes) {
SDValue X = DAG.getNode(ISD::BIT_CONVERT, N0.getDebugLoc(),
IntXVT, N0.getOperand(1));
DstEltVT, Op));
AddToWorkList(Ops.back().getNode());
}
- EVT VT = EVT::getVectorVT(DstEltVT,
+ EVT VT = EVT::getVectorVT(*DAG.getContext(), DstEltVT,
BV->getValueType(0).getVectorNumElements());
return DAG.getNode(ISD::BUILD_VECTOR, BV->getDebugLoc(), VT,
&Ops[0], Ops.size());
// Convert the input float vector to a int vector where the elements are the
// same sizes.
assert((SrcEltVT == MVT::f32 || SrcEltVT == MVT::f64) && "Unknown FP VT!");
- EVT IntVT = EVT::getIntegerVT(SrcEltVT.getSizeInBits());
+ EVT IntVT = EVT::getIntegerVT(*DAG.getContext(), SrcEltVT.getSizeInBits());
BV = ConstantFoldBIT_CONVERTofBUILD_VECTOR(BV, IntVT).getNode();
SrcEltVT = IntVT;
}
// convert to integer first, then to FP of the right size.
if (DstEltVT.isFloatingPoint()) {
assert((DstEltVT == MVT::f32 || DstEltVT == MVT::f64) && "Unknown FP VT!");
- EVT TmpVT = EVT::getIntegerVT(DstEltVT.getSizeInBits());
+ EVT TmpVT = EVT::getIntegerVT(*DAG.getContext(), DstEltVT.getSizeInBits());
SDNode *Tmp = ConstantFoldBIT_CONVERTofBUILD_VECTOR(BV, TmpVT).getNode();
// Next, convert to FP elements of the same size.
Ops.push_back(DAG.getConstant(NewBits, DstEltVT));
}
- EVT VT = EVT::getVectorVT(DstEltVT, Ops.size());
+ EVT VT = EVT::getVectorVT(*DAG.getContext(), DstEltVT, Ops.size());
return DAG.getNode(ISD::BUILD_VECTOR, BV->getDebugLoc(), VT,
&Ops[0], Ops.size());
}
// turns into multiple outputs.
bool isS2V = ISD::isScalarToVector(BV);
unsigned NumOutputsPerInput = SrcBitSize/DstBitSize;
- EVT VT = EVT::getVectorVT(DstEltVT, NumOutputsPerInput*BV->getNumOperands());
+ EVT VT = EVT::getVectorVT(*DAG.getContext(), DstEltVT,
+ NumOutputsPerInput*BV->getNumOperands());
SmallVector<SDValue, 8> Ops;
for (unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) {
SDValue DAGCombiner::visitFNEG(SDNode *N) {
SDValue N0 = N->getOperand(0);
+ EVT VT = N->getValueType(0);
if (isNegatibleForFree(N0, LegalOperations))
return GetNegatedExpression(N0, DAG, LegalOperations);
// Transform fneg(bitconvert(x)) -> bitconvert(x^sign) to avoid loading
// constant pool values.
- if (N0.getOpcode() == ISD::BIT_CONVERT && N0.getNode()->hasOneUse() &&
- N0.getOperand(0).getValueType().isInteger() &&
- !N0.getOperand(0).getValueType().isVector()) {
+ if (N0.getOpcode() == ISD::BIT_CONVERT &&
+ !VT.isVector() &&
+ N0.getNode()->hasOneUse() &&
+ N0.getOperand(0).getValueType().isInteger()) {
SDValue Int = N0.getOperand(0);
EVT IntVT = Int.getValueType();
if (IntVT.isInteger() && !IntVT.isVector()) {
DAG.getConstant(APInt::getSignBit(IntVT.getSizeInBits()), IntVT));
AddToWorkList(Int.getNode());
return DAG.getNode(ISD::BIT_CONVERT, N->getDebugLoc(),
- N->getValueType(0), Int);
+ VT, Int);
}
}
if (Op0.getOpcode() == ISD::AND &&
Op0.hasOneUse() &&
Op1.getOpcode() == ISD::Constant) {
- SDValue AndOp0 = Op0.getOperand(0);
SDValue AndOp1 = Op0.getOperand(1);
if (AndOp1.getOpcode() == ISD::Constant) {
BasePtr, Offset, AM);
++PreIndexedNodes;
++NodesCombined;
- DOUT << "\nReplacing.4 "; DEBUG(N->dump(&DAG));
- DOUT << "\nWith: "; DEBUG(Result.getNode()->dump(&DAG));
- DOUT << '\n';
+ DEBUG(errs() << "\nReplacing.4 ";
+ N->dump(&DAG);
+ errs() << "\nWith: ";
+ Result.getNode()->dump(&DAG);
+ errs() << '\n');
WorkListRemover DeadNodes(*this);
if (isLoad) {
DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result.getValue(0),
SDValue Offset;
ISD::MemIndexedMode AM = ISD::UNINDEXED;
if (TLI.getPostIndexedAddressParts(N, Op, BasePtr, Offset, AM, DAG)) {
- if (Ptr == Offset)
+ if (Ptr == Offset && Op->getOpcode() == ISD::ADD)
std::swap(BasePtr, Offset);
if (Ptr != BasePtr)
continue;
BasePtr, Offset, AM);
++PostIndexedNodes;
++NodesCombined;
- DOUT << "\nReplacing.5 "; DEBUG(N->dump(&DAG));
- DOUT << "\nWith: "; DEBUG(Result.getNode()->dump(&DAG));
- DOUT << '\n';
+ DEBUG(errs() << "\nReplacing.5 ";
+ N->dump(&DAG);
+ errs() << "\nWith: ";
+ Result.getNode()->dump(&DAG);
+ errs() << '\n');
WorkListRemover DeadNodes(*this);
if (isLoad) {
DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result.getValue(0),
// v3 = add v2, c
// 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.
- DOUT << "\nReplacing.6 "; DEBUG(N->dump(&DAG));
- DOUT << "\nWith chain: "; DEBUG(Chain.getNode()->dump(&DAG));
- DOUT << "\n";
+ DEBUG(errs() << "\nReplacing.6 ";
+ N->dump(&DAG);
+ errs() << "\nWith chain: ";
+ Chain.getNode()->dump(&DAG);
+ errs() << "\n");
WorkListRemover DeadNodes(*this);
DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), Chain, &DeadNodes);
assert(N->getValueType(2) == MVT::Other && "Malformed indexed loads?");
if (N->hasNUsesOfValue(0, 0) && N->hasNUsesOfValue(0, 1)) {
SDValue Undef = DAG.getUNDEF(N->getValueType(0));
- DOUT << "\nReplacing.6 "; DEBUG(N->dump(&DAG));
- DOUT << "\nWith: "; DEBUG(Undef.getNode()->dump(&DAG));
- DOUT << " and 2 other values\n";
+ DEBUG(errs() << "\nReplacing.6 ";
+ N->dump(&DAG);
+ errs() << "\nWith: ";
+ Undef.getNode()->dump(&DAG);
+ errs() << " and 2 other values\n");
WorkListRemover DeadNodes(*this);
DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Undef, &DeadNodes);
DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1),
// Create token factor to keep old chain connected.
SDValue Token = DAG.getNode(ISD::TokenFactor, N->getDebugLoc(),
MVT::Other, Chain, ReplLoad.getValue(1));
-
+
+ // Make sure the new and old chains are cleaned up.
+ AddToWorkList(Token.getNode());
+
// Replace uses with load result and token factor. Don't add users
// to work list.
return CombineTo(N, ReplLoad.getValue(0), Token, false);
unsigned ShAmt = Imm.countTrailingZeros();
unsigned MSB = BitWidth - Imm.countLeadingZeros() - 1;
unsigned NewBW = NextPowerOf2(MSB - ShAmt);
- EVT NewVT = EVT::getIntegerVT(NewBW);
+ EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), NewBW);
while (NewBW < BitWidth &&
!(TLI.isOperationLegalOrCustom(Opc, NewVT) &&
TLI.isNarrowingProfitable(VT, NewVT))) {
NewBW = NextPowerOf2(NewBW);
- NewVT = EVT::getIntegerVT(NewBW);
+ NewVT = EVT::getIntegerVT(*DAG.getContext(), NewBW);
}
if (NewBW >= BitWidth)
return SDValue();
unsigned NewAlign = MinAlign(LD->getAlignment(), PtrOff);
if (NewAlign <
- TLI.getTargetData()->getABITypeAlignment(NewVT.getTypeForEVT()))
+ TLI.getTargetData()->getABITypeAlignment(NewVT.getTypeForEVT(*DAG.getContext())))
return SDValue();
SDValue NewPtr = DAG.getNode(ISD::ADD, LD->getDebugLoc(),
unsigned OrigAlign = ST->getAlignment();
EVT SVT = Value.getOperand(0).getValueType();
unsigned Align = TLI.getTargetData()->
- getABITypeAlignment(SVT.getTypeForEVT());
+ getABITypeAlignment(SVT.getTypeForEVT(*DAG.getContext()));
if (Align <= OrigAlign &&
((!LegalOperations && !ST->isVolatile()) ||
TLI.isOperationLegalOrCustom(ISD::STORE, SVT)))
// If there is a better chain.
if (Chain != BetterChain) {
- // Replace the chain to avoid dependency.
SDValue ReplStore;
+
+ // Replace the chain to avoid dependency.
if (ST->isTruncatingStore()) {
ReplStore = DAG.getTruncStore(BetterChain, N->getDebugLoc(), Value, Ptr,
ST->getSrcValue(),ST->getSrcValueOffset(),
SDValue Token = DAG.getNode(ISD::TokenFactor, N->getDebugLoc(),
MVT::Other, Chain, ReplStore);
+ // Make sure the new and old chains are cleaned up.
+ AddToWorkList(Token.getNode());
+
// Don't add users to work list.
return CombineTo(N, Token, false);
}
if (!LegalOperations && InVec.getOpcode() == ISD::UNDEF &&
isa<ConstantSDNode>(EltNo)) {
EVT VT = InVec.getValueType();
- EVT EVT = VT.getVectorElementType();
+ EVT EltVT = VT.getVectorElementType();
unsigned NElts = VT.getVectorNumElements();
- SmallVector<SDValue, 8> Ops(NElts, DAG.getUNDEF(EVT));
+ SmallVector<SDValue, 8> Ops(NElts, DAG.getUNDEF(EltVT));
unsigned Elt = cast<ConstantSDNode>(EltNo)->getZExtValue();
if (Elt < Ops.size())
// Check the resultant load doesn't need a higher alignment than the
// original load.
unsigned NewAlign =
- TLI.getTargetData()->getABITypeAlignment(LVT.getTypeForEVT());
+ TLI.getTargetData()->getABITypeAlignment(LVT.getTypeForEVT(*DAG.getContext()));
if (NewAlign > Align || !TLI.isOperationLegalOrCustom(ISD::LOAD, LVT))
return SDValue();
SDValue DAGCombiner::visitBUILD_VECTOR(SDNode *N) {
unsigned NumInScalars = N->getNumOperands();
EVT VT = N->getValueType(0);
- EVT EltType = VT.getVectorElementType();
// Check to see if this is a BUILD_VECTOR of a bunch of EXTRACT_VECTOR_ELT
// operations. If so, and if the EXTRACT_VECTOR_ELT vector inputs come from
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");
return SDValue();
// Return the new VECTOR_SHUFFLE node.
- EVT EVT = RVT.getVectorElementType();
+ EVT EltVT = RVT.getVectorElementType();
SmallVector<SDValue,8> ZeroOps(RVT.getVectorNumElements(),
- DAG.getConstant(0, EVT));
+ DAG.getConstant(0, EltVT));
SDValue Zero = DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(),
RVT, &ZeroOps[0], ZeroOps.size());
LHS = DAG.getNode(ISD::BIT_CONVERT, dl, RVT, LHS);
return S;
}
-/// FindBaseOffset - Return true if base is known not to alias with anything
-/// but itself. Provides base object and offset as results.
-static bool FindBaseOffset(SDValue Ptr, SDValue &Base, int64_t &Offset) {
+/// FindBaseOffset - Return true if base is a frame index, which is known not
+// to alias with anything but itself. Provides base object and offset as results.
+static bool FindBaseOffset(SDValue Ptr, SDValue &Base, int64_t &Offset,
+ GlobalValue *&GV, void *&CV) {
// Assume it is a primitive operation.
- Base = Ptr; Offset = 0;
+ Base = Ptr; Offset = 0; GV = 0; CV = 0;
// If it's an adding a simple constant then integrate the offset.
if (Base.getOpcode() == ISD::ADD) {
Offset += C->getZExtValue();
}
}
+
+ // Return the underlying GlobalValue, and update the Offset. Return false
+ // for GlobalAddressSDNode since the same GlobalAddress may be represented
+ // by multiple nodes with different offsets.
+ if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(Base)) {
+ GV = G->getGlobal();
+ Offset += G->getOffset();
+ return false;
+ }
+ // Return the underlying Constant value, and update the Offset. Return false
+ // for ConstantSDNodes since the same constant pool entry may be represented
+ // by multiple nodes with different offsets.
+ if (ConstantPoolSDNode *C = dyn_cast<ConstantPoolSDNode>(Base)) {
+ CV = C->isMachineConstantPoolEntry() ? (void *)C->getMachineCPVal()
+ : (void *)C->getConstVal();
+ Offset += C->getOffset();
+ return false;
+ }
// If it's any of the following then it can't alias with anything but itself.
- return isa<FrameIndexSDNode>(Base) ||
- isa<ConstantPoolSDNode>(Base) ||
- isa<GlobalAddressSDNode>(Base);
+ return isa<FrameIndexSDNode>(Base);
}
/// isAlias - Return true if there is any possibility that the two addresses
/// overlap.
bool DAGCombiner::isAlias(SDValue Ptr1, int64_t Size1,
const Value *SrcValue1, int SrcValueOffset1,
+ unsigned SrcValueAlign1,
SDValue Ptr2, int64_t Size2,
- const Value *SrcValue2, int SrcValueOffset2) const {
+ const Value *SrcValue2, int SrcValueOffset2,
+ unsigned SrcValueAlign2) const {
// If they are the same then they must be aliases.
if (Ptr1 == Ptr2) return true;
// Gather base node and offset information.
SDValue Base1, Base2;
int64_t Offset1, Offset2;
- bool KnownBase1 = FindBaseOffset(Ptr1, Base1, Offset1);
- bool KnownBase2 = FindBaseOffset(Ptr2, Base2, Offset2);
+ GlobalValue *GV1, *GV2;
+ void *CV1, *CV2;
+ bool isFrameIndex1 = FindBaseOffset(Ptr1, Base1, Offset1, GV1, CV1);
+ bool isFrameIndex2 = FindBaseOffset(Ptr2, Base2, Offset2, GV2, CV2);
- // If they have a same base address then...
- if (Base1 == Base2)
- // Check to see if the addresses overlap.
+ // If they have a same base address then check to see if they overlap.
+ if (Base1 == Base2 || (GV1 && (GV1 == GV2)) || (CV1 && (CV1 == CV2)))
return !((Offset1 + Size1) <= Offset2 || (Offset2 + Size2) <= Offset1);
- // If we know both bases then they can't alias.
- if (KnownBase1 && KnownBase2) return false;
+ // If we know what the bases are, and they aren't identical, then we know they
+ // cannot alias.
+ if ((isFrameIndex1 || CV1 || GV1) && (isFrameIndex2 || CV2 || GV2))
+ return false;
+ // If we know required SrcValue1 and SrcValue2 have relatively large alignment
+ // compared to the size and offset of the access, we may be able to prove they
+ // do not alias. This check is conservative for now to catch cases created by
+ // splitting vector types.
+ if ((SrcValueAlign1 == SrcValueAlign2) &&
+ (SrcValueOffset1 != SrcValueOffset2) &&
+ (Size1 == Size2) && (SrcValueAlign1 > Size1)) {
+ int64_t OffAlign1 = SrcValueOffset1 % SrcValueAlign1;
+ int64_t OffAlign2 = SrcValueOffset2 % SrcValueAlign1;
+
+ // There is no overlap between these relatively aligned accesses of similar
+ // size, return no alias.
+ if ((OffAlign1 + Size1) <= OffAlign2 || (OffAlign2 + Size2) <= OffAlign1)
+ return false;
+ }
+
if (CombinerGlobalAA) {
// Use alias analysis information.
int64_t MinOffset = std::min(SrcValueOffset1, SrcValueOffset2);
/// node. Returns true if the operand was a load.
bool DAGCombiner::FindAliasInfo(SDNode *N,
SDValue &Ptr, int64_t &Size,
- const Value *&SrcValue, int &SrcValueOffset) const {
+ const Value *&SrcValue,
+ int &SrcValueOffset,
+ unsigned &SrcValueAlign) const {
if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
Ptr = LD->getBasePtr();
Size = LD->getMemoryVT().getSizeInBits() >> 3;
SrcValue = LD->getSrcValue();
SrcValueOffset = LD->getSrcValueOffset();
+ SrcValueAlign = LD->getOriginalAlignment();
return true;
} else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
Ptr = ST->getBasePtr();
Size = ST->getMemoryVT().getSizeInBits() >> 3;
SrcValue = ST->getSrcValue();
SrcValueOffset = ST->getSrcValueOffset();
+ SrcValueAlign = ST->getOriginalAlignment();
} else {
llvm_unreachable("FindAliasInfo expected a memory operand");
}
void DAGCombiner::GatherAllAliases(SDNode *N, SDValue OriginalChain,
SmallVector<SDValue, 8> &Aliases) {
SmallVector<SDValue, 8> Chains; // List of chains to visit.
- std::set<SDNode *> Visited; // Visited node set.
+ SmallPtrSet<SDNode *, 16> Visited; // Visited node set.
// Get alias information for node.
SDValue Ptr;
- int64_t Size = 0;
- const Value *SrcValue = 0;
- int SrcValueOffset = 0;
- bool IsLoad = FindAliasInfo(N, Ptr, Size, SrcValue, SrcValueOffset);
+ int64_t Size;
+ const Value *SrcValue;
+ int SrcValueOffset;
+ unsigned SrcValueAlign;
+ bool IsLoad = FindAliasInfo(N, Ptr, Size, SrcValue, SrcValueOffset,
+ SrcValueAlign);
// Starting off.
Chains.push_back(OriginalChain);
-
+ unsigned Depth = 0;
+
// Look at each chain and determine if it is an alias. If so, add it to the
// aliases list. If not, then continue up the chain looking for the next
// candidate.
while (!Chains.empty()) {
SDValue Chain = Chains.back();
Chains.pop_back();
+
+ // For TokenFactor nodes, look at each operand and only continue up the
+ // chain until we find two aliases. If we've seen two aliases, assume we'll
+ // find more and revert to original chain since the xform is unlikely to be
+ // profitable.
+ //
+ // FIXME: The depth check could be made to return the last non-aliasing
+ // chain we found before we hit a tokenfactor rather than the original
+ // chain.
+ if (Depth > 6 || Aliases.size() == 2) {
+ Aliases.clear();
+ Aliases.push_back(OriginalChain);
+ break;
+ }
- // Don't bother if we've been before.
- if (Visited.find(Chain.getNode()) != Visited.end()) continue;
- Visited.insert(Chain.getNode());
+ // Don't bother if we've been before.
+ if (!Visited.insert(Chain.getNode()))
+ continue;
switch (Chain.getOpcode()) {
case ISD::EntryToken:
case ISD::STORE: {
// Get alias information for Chain.
SDValue OpPtr;
- int64_t OpSize = 0;
- const Value *OpSrcValue = 0;
- int OpSrcValueOffset = 0;
+ int64_t OpSize;
+ const Value *OpSrcValue;
+ int OpSrcValueOffset;
+ unsigned OpSrcValueAlign;
bool IsOpLoad = FindAliasInfo(Chain.getNode(), OpPtr, OpSize,
- OpSrcValue, OpSrcValueOffset);
+ OpSrcValue, OpSrcValueOffset,
+ OpSrcValueAlign);
// If chain is alias then stop here.
if (!(IsLoad && IsOpLoad) &&
- isAlias(Ptr, Size, SrcValue, SrcValueOffset,
- OpPtr, OpSize, OpSrcValue, OpSrcValueOffset)) {
+ isAlias(Ptr, Size, SrcValue, SrcValueOffset, SrcValueAlign,
+ OpPtr, OpSize, OpSrcValue, OpSrcValueOffset,
+ OpSrcValueAlign)) {
Aliases.push_back(Chain);
} else {
// Look further up the chain.
Chains.push_back(Chain.getOperand(0));
- // Clean up old chain.
- AddToWorkList(Chain.getNode());
+ ++Depth;
}
break;
}
case ISD::TokenFactor:
- // We have to check each of the operands of the token factor, so we queue
- // then up. Adding the operands to the queue (stack) in reverse order
- // maintains the original order and increases the likelihood that getNode
- // will find a matching token factor (CSE.)
+ // We have to check each of the operands of the token factor for "small"
+ // token factors, so we queue them up. Adding the operands to the queue
+ // (stack) in reverse order maintains the original order and increases the
+ // likelihood that getNode will find a matching token factor (CSE.)
+ if (Chain.getNumOperands() > 16) {
+ Aliases.push_back(Chain);
+ break;
+ }
for (unsigned n = Chain.getNumOperands(); n;)
Chains.push_back(Chain.getOperand(--n));
- // Eliminate the token factor if we can.
- AddToWorkList(Chain.getNode());
+ ++Depth;
break;
default:
// If a single operand then chain to it. We don't need to revisit it.
return Aliases[0];
}
-
+
// Construct a custom tailored token factor.
- SDValue NewChain = DAG.getNode(ISD::TokenFactor, N->getDebugLoc(), MVT::Other,
- &Aliases[0], Aliases.size());
-
- // Make sure the old chain gets cleaned up.
- if (NewChain != OldChain) AddToWorkList(OldChain.getNode());
-
- return NewChain;
+ return DAG.getNode(ISD::TokenFactor, N->getDebugLoc(), MVT::Other,
+ &Aliases[0], Aliases.size());
}
// SelectionDAG::Combine - This is the entry point for the file.