Index: lib/CodeGen/SelectionDAG/DAGCombiner.cpp =================================================================== --- lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -451,6 +451,11 @@ EVT LoadResultTy, EVT &ExtVT, EVT &LoadedVT, bool &NarrowLoad); + //// Helper function for MergeConsecutiveStores which merges the + //// component store chains. + SDValue getMergeStoreChains(SmallVectorImpl &StoreNodes, + unsigned NumStores); + /// This is a helper function for MergeConsecutiveStores. When the source /// elements of the consecutive stores are all constants or all extracted /// vector elements, try to merge them into one larger store. @@ -12101,6 +12106,26 @@ return false; } +SDValue DAGCombiner::getMergeStoreChains(SmallVectorImpl &StoreNodes, + unsigned NumStores) { + SmallVector Chains; + SmallPtrSet Visited; + SDLoc StoreDL(StoreNodes[0].MemNode); + + for (unsigned i = 0; i < NumStores; ++i) { + Visited.insert(StoreNodes[i].MemNode); + } + + // don't include nodes that are children + for (unsigned i = 0; i < NumStores; ++i) { + if (Visited.count(StoreNodes[i].MemNode->getChain().getNode()) == 0) + Chains.push_back(StoreNodes[i].MemNode->getChain()); + } + + assert(Chains.size() > 0 && "Chain should have generated a chain"); + return DAG.getNode(ISD::TokenFactor, StoreDL, MVT::Other, Chains); +} + bool DAGCombiner::MergeStoresOfConstantsOrVecElts( SmallVectorImpl &StoreNodes, EVT MemVT, unsigned NumStores, bool IsConstantSrc, bool UseVector) { @@ -12183,17 +12208,8 @@ StoredVal = DAG.getConstant(StoreInt, DL, StoreTy); } - SmallVector Chains; - - // Gather all Chains we're inheriting. As generally all chains are - // equal, do minor check to remove obvious redundancies. - Chains.push_back(StoreNodes[0].MemNode->getChain()); - for (unsigned i = 1; i < NumStores; ++i) - if (StoreNodes[0].MemNode->getChain() != StoreNodes[i].MemNode->getChain()) - Chains.push_back(StoreNodes[i].MemNode->getChain()); - LSBaseSDNode *FirstInChain = StoreNodes[0].MemNode; - SDValue NewChain = DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Chains); + SDValue NewChain = getMergeStoreChains(StoreNodes, NumStores); SDValue NewStore = DAG.getStore(NewChain, DL, StoredVal, FirstInChain->getBasePtr(), FirstInChain->getPointerInfo(), @@ -12222,6 +12238,52 @@ if (BasePtr.Base.isUndef()) return; + bool IsLoadSrc = isa(St->getValue()); + bool IsConstantSrc = isa(St->getValue()) || + isa(St->getValue()); + bool IsExtractVecSrc = + (St->getValue().getOpcode() == ISD::EXTRACT_VECTOR_ELT || + St->getValue().getOpcode() == ISD::EXTRACT_SUBVECTOR); + auto CandidateMatch = [&](StoreSDNode *Other, BaseIndexOffset &Ptr) -> bool { + if (Other->isVolatile() || Other->isIndexed()) + return false; + // We can merge constant floats to equivalent integers + if (Other->getMemoryVT() != MemVT) + if (!(MemVT.isInteger() && MemVT.bitsEq(Other->getMemoryVT()) && + isa(Other->getValue()))) + return false; + Ptr = BaseIndexOffset::match(Other->getBasePtr(), DAG); + if (!Ptr.equalBaseIndex(BasePtr)) + return false; + if (IsLoadSrc) + return isa(Other->getValue()); + if (IsConstantSrc) + return (isa(Other->getValue()) || + isa(Other->getValue())); + if (IsExtractVecSrc) + return (Other->getValue().getOpcode() == ISD::EXTRACT_VECTOR_ELT || + Other->getValue().getOpcode() == ISD::EXTRACT_SUBVECTOR); + return false; + }; + + // In the case FindBetterChain gives up we will find chains of + // consecutive stores. Do a preprocessing step to walk up the chain + // leaving the the head of the chain for the parallel search. + + StoreSDNode *STChain = St; + int64_t LastOffset = BasePtr.Offset; + while (StoreSDNode *Chain = dyn_cast(STChain->getChain())) { + BaseIndexOffset Ptr; + //Check Chain. + if (!CandidateMatch(Chain, Ptr) || Ptr.Offset > LastOffset) + break; + StoreNodes.push_back(MemOpLink(STChain, LastOffset)); + LastOffset = Ptr.Offset; + STChain = Chain; + } + + SDNode *RootNode = (STChain->getChain()).getNode(); + // We looking for a root node which is an ancestor to all mergable // stores. We search up through a load, to our root and then down // through all children. For instance we will find Store{1,2,3} if @@ -12233,13 +12295,11 @@ // |-------|-------| // Load Load Store3 // | | - // Store1 Store2 + // Store1 Store2 // // FIXME: We should be able to climb and // descend TokenFactors to find candidates as well. - SDNode *RootNode = (St->getChain()).getNode(); - // Set of Parents of Candidates std::set CandidateParents; @@ -12251,41 +12311,34 @@ } else CandidateParents.insert(RootNode); - bool IsLoadSrc = isa(St->getValue()); - bool IsConstantSrc = isa(St->getValue()) || - isa(St->getValue()); - bool IsExtractVecSrc = - (St->getValue().getOpcode() == ISD::EXTRACT_VECTOR_ELT || - St->getValue().getOpcode() == ISD::EXTRACT_SUBVECTOR); - auto CorrectValueKind = [&](StoreSDNode *Other) -> bool { - if (IsLoadSrc) - return isa(Other->getValue()); - if (IsConstantSrc) - return (isa(Other->getValue()) || - isa(Other->getValue())); - if (IsExtractVecSrc) - return (Other->getValue().getOpcode() == ISD::EXTRACT_VECTOR_ELT || - Other->getValue().getOpcode() == ISD::EXTRACT_SUBVECTOR); - return false; - }; - + // If we find a store, also traverse the parent to see if it's a store + // we can merge + std::vector WorklistNodes(CandidateParents.begin(), CandidateParents.end()); + unsigned Idx = 0; // check all parents of mergable children - for (auto P = CandidateParents.begin(); P != CandidateParents.end(); ++P) - for (auto I = (*P)->use_begin(), E = (*P)->use_end(); I != E; ++I) - if (I.getOperandNo() == 0) - if (StoreSDNode *OtherST = dyn_cast(*I)) { - if (OtherST->isVolatile() || OtherST->isIndexed()) - continue; - // We can merge constant floats to equivalent integers - if (OtherST->getMemoryVT() != MemVT) - if (!(MemVT.isInteger() && MemVT.bitsEq(OtherST->getMemoryVT()) && - isa(OtherST->getValue()))) - continue; - BaseIndexOffset Ptr = - BaseIndexOffset::match(OtherST->getBasePtr(), DAG); - if (Ptr.equalBaseIndex(BasePtr) && CorrectValueKind(OtherST)) - StoreNodes.push_back(MemOpLink(OtherST, Ptr.Offset)); - } + do { + auto *P = WorklistNodes[Idx]; + if (StoreSDNode *OSt = dyn_cast(P)) { + BaseIndexOffset Ptr; + if (CandidateMatch(OSt, Ptr)) { + StoreNodes.push_back(MemOpLink(OSt, Ptr.Offset)); + if (StoreSDNode *OtherSTChainST = dyn_cast(*OSt->use_begin())) + WorklistNodes.push_back(OtherSTChainST); + } + } else { + for (auto I = P->use_begin(), E = P->use_end(); I != E; ++I) + if (I.getOperandNo() == 0) + if (StoreSDNode *OtherST = dyn_cast(*I)) { + BaseIndexOffset Ptr; + if (CandidateMatch(OtherST, Ptr)) { + StoreNodes.push_back(MemOpLink(OtherST, Ptr.Offset)); + if (StoreSDNode *OtherSTChainST = dyn_cast(*OtherST->use_begin())) + WorklistNodes.push_back(OtherSTChainST); + } + } + } + ++Idx; + } while (Idx < WorklistNodes.size()); } // We need to check that merging these stores does not cause a loop @@ -12641,14 +12694,6 @@ if (NumElem < 2) return false; - // Collect the chains from all merged stores. Because the common case - // all chains are the same, check if we match the first Chain. - SmallVector MergeStoreChains; - MergeStoreChains.push_back(StoreNodes[0].MemNode->getChain()); - for (unsigned i = 1; i < NumElem; ++i) - if (StoreNodes[0].MemNode->getChain() != StoreNodes[i].MemNode->getChain()) - MergeStoreChains.push_back(StoreNodes[i].MemNode->getChain()); - // Find if it is better to use vectors or integers to load and store // to memory. EVT JointMemOpVT; @@ -12668,8 +12713,7 @@ FirstLoad->getBasePtr(), FirstLoad->getPointerInfo(), FirstLoadAlign); - SDValue NewStoreChain = - DAG.getNode(ISD::TokenFactor, StoreDL, MVT::Other, MergeStoreChains); + SDValue NewStoreChain = getMergeStoreChains(StoreNodes, NumElem); AddToWorklist(NewStoreChain.getNode());