Index: lib/CodeGen/SelectionDAG/DAGCombiner.cpp =================================================================== --- lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -449,6 +449,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. @@ -12071,6 +12076,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) { @@ -12153,17 +12178,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(), @@ -12192,6 +12208,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 @@ -12203,13 +12265,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; @@ -12221,39 +12281,13 @@ } 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; - }; - // 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)) + BaseIndexOffset Ptr; + if (CandidateMatch(OtherST, Ptr)) StoreNodes.push_back(MemOpLink(OtherST, Ptr.Offset)); } } @@ -12611,14 +12645,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; @@ -12638,8 +12664,7 @@ FirstLoad->getBasePtr(), FirstLoad->getPointerInfo(), FirstLoadAlign); - SDValue NewStoreChain = - DAG.getNode(ISD::TokenFactor, StoreDL, MVT::Other, MergeStoreChains); + SDValue NewStoreChain = getMergeStoreChains(StoreNodes, NumElem); AddToWorklist(NewStoreChain.getNode()); Index: test/CodeGen/X86/stores-merging2.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/stores-merging2.ll @@ -0,0 +1,44 @@ +; RUN: llc %s -o - | FileCheck %s + +target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128" +target triple = "i386-unknown-linux-gnu" + + + +@ptr = global [32 x i32] zeroinitializer, align 4 +@strptr = global [4 x i8] zeroinitializer, align 1 + +; FindBetterChains in SelectionDAG should give up and the 4 1-byte +; stores will remain in a chain. We should still be able to merge them +; into a 32-bit store. + +; CHECK-LABEL: @foo +; CHECK: movl $1684234849, strpt + +define i32 @foo() { + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 0) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 1) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 2) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 3) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 4) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 5) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 6) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 7) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 8) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 9) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 10) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 11) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 12) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 13) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 14) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 15) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 16) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 17) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 18) + store i32 0, i32* getelementptr inbounds ([32 x i32], [32 x i32]* @ptr, i32 0, i32 19) + store i8 97, i8* getelementptr inbounds ([4 x i8], [4 x i8]* @strptr, i32 0, i32 0) + store i8 98, i8* getelementptr inbounds ([4 x i8], [4 x i8]* @strptr, i32 0, i32 1) + store i8 99, i8* getelementptr inbounds ([4 x i8], [4 x i8]* @strptr, i32 0, i32 2) + store i8 100, i8* getelementptr inbounds ([4 x i8], [4 x i8]* @strptr, i32 0, i32 3) + ret i32 0 +}