diff options
Diffstat (limited to 'src/jit/optcse.cpp')
-rw-r--r-- | src/jit/optcse.cpp | 200 |
1 files changed, 173 insertions, 27 deletions
diff --git a/src/jit/optcse.cpp b/src/jit/optcse.cpp index 5ee6d84920..41aad403d9 100644 --- a/src/jit/optcse.cpp +++ b/src/jit/optcse.cpp @@ -321,8 +321,8 @@ Compiler::fgWalkResult Compiler::optCSE_MaskHelper(GenTreePtr* pTree, fgWalkData // void Compiler::optCSE_GetMaskData(GenTreePtr tree, optCSE_MaskData* pMaskData) { - pMaskData->CSE_defMask = BitVecOps::MakeCopy(cseTraits, cseEmpty); - pMaskData->CSE_useMask = BitVecOps::MakeCopy(cseTraits, cseEmpty); + pMaskData->CSE_defMask = BitVecOps::MakeEmpty(cseTraits); + pMaskData->CSE_useMask = BitVecOps::MakeEmpty(cseTraits); fgWalkTreePre(&tree, optCSE_MaskHelper, (void*)pMaskData); } @@ -498,10 +498,7 @@ void Compiler::optValnumCSE_Init() // Init traits and full/empty bitvectors. This will be used to track the // individual cse indexes. cseTraits = new (getAllocator()) BitVecTraits(EXPSET_SZ, this); - cseFull = BitVecOps::UninitVal(); - cseEmpty = BitVecOps::UninitVal(); - BitVecOps::AssignNoCopy(cseTraits, cseFull, BitVecOps::MakeFull(cseTraits)); - BitVecOps::AssignNoCopy(cseTraits, cseEmpty, BitVecOps::MakeEmpty(cseTraits)); + cseFull = BitVecOps::MakeFull(cseTraits); /* Allocate and clear the hash bucket table */ @@ -509,6 +506,9 @@ void Compiler::optValnumCSE_Init() optCSECandidateCount = 0; optDoCSE = false; // Stays false until we find duplicate CSE tree + + // optCseArrLenMap is unused in most functions, allocated only when used + optCseArrLenMap = nullptr; } /***************************************************************************** @@ -700,8 +700,17 @@ unsigned Compiler::optValnumCSE_Locate() noway_assert(stmt->gtOper == GT_STMT); /* We walk the tree in the forwards direction (bottom up) */ + bool stmtHasArrLenCandidate = false; for (tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext) { + if (tree->OperIsCompare() && stmtHasArrLenCandidate) + { + // Check if this compare is a function of (one of) the arrary + // length candidate(s); we may want to update its value number + // if the array length gets CSEd + optCseUpdateArrLenMap(tree); + } + if (!optIsCSEcandidate(tree)) { continue; @@ -730,6 +739,11 @@ unsigned Compiler::optValnumCSE_Locate() { noway_assert(((unsigned)tree->gtCSEnum) == CSEindex); } + + if (IS_CSE_INDEX(CSEindex) && (tree->OperGet() == GT_ARR_LENGTH)) + { + stmtHasArrLenCandidate = true; + } } } } @@ -748,6 +762,102 @@ unsigned Compiler::optValnumCSE_Locate() return 1; } +//------------------------------------------------------------------------ +// optCseUpdateArrLenMap: Check if this compare is a tractable function of +// an array length that is a CSE candidate, and insert +// an entry in the optCseArrLenMap if so. This facilitates +// subsequently updating the compare's value number if +// the array length gets CSEd. +// +// Arguments: +// compare - The compare node to check + +void Compiler::optCseUpdateArrLenMap(GenTreePtr compare) +{ + assert(compare->OperIsCompare()); + + ValueNum compareVN = compare->gtVNPair.GetConservative(); + VNFuncApp cmpVNFuncApp; + + if (!vnStore->GetVNFunc(compareVN, &cmpVNFuncApp) || + (cmpVNFuncApp.m_func != GetVNFuncForOper(compare->OperGet(), compare->IsUnsigned()))) + { + // Value numbering inferred this compare as something other + // than its own operator; leave its value number alone. + return; + } + + // Now look for an array length feeding the compare + ValueNumStore::ArrLenArithBoundInfo info; + GenTreePtr arrLenParent = nullptr; + + if (vnStore->IsVNArrLenBound(compareVN)) + { + // Simple compare of an array legnth against something else. + + vnStore->GetArrLenBoundInfo(compareVN, &info); + arrLenParent = compare; + } + else if (vnStore->IsVNArrLenArithBound(compareVN)) + { + // Compare of an array length +/- some offset to something else. + + GenTreePtr op1 = compare->gtGetOp1(); + GenTreePtr op2 = compare->gtGetOp2(); + + vnStore->GetArrLenArithBoundInfo(compareVN, &info); + if (GetVNFuncForOper(op1->OperGet(), op1->IsUnsigned()) == (VNFunc)info.arrOper) + { + // The arithmetic node is the array length's parent. + arrLenParent = op1; + } + else if (GetVNFuncForOper(op2->OperGet(), op2->IsUnsigned()) == (VNFunc)info.arrOper) + { + // The arithmetic node is the array length's parent. + arrLenParent = op2; + } + } + + if (arrLenParent != nullptr) + { + GenTreePtr arrLen = nullptr; + + // Find which child of arrLenParent is the array length. Abort if its + // conservative value number doesn't match the one from the compare VN. + + GenTreePtr child1 = arrLenParent->gtGetOp1(); + if ((child1->OperGet() == GT_ARR_LENGTH) && IS_CSE_INDEX(child1->gtCSEnum) && + (info.vnArray == child1->AsArrLen()->ArrRef()->gtVNPair.GetConservative())) + { + arrLen = child1; + } + else + { + GenTreePtr child2 = arrLenParent->gtGetOp2(); + if ((child2->OperGet() == GT_ARR_LENGTH) && IS_CSE_INDEX(child2->gtCSEnum) && + (info.vnArray == child2->AsArrLen()->ArrRef()->gtVNPair.GetConservative())) + { + arrLen = child2; + } + } + + if (arrLen != nullptr) + { + // Found an arrayLen feeding a compare that is a tracatable function of it; + // record this in the map so we can update the compare VN if the array length + // node gets CSEd. + + if (optCseArrLenMap == nullptr) + { + // Allocate map on first use. + optCseArrLenMap = new (getAllocator()) NodeToNodeMap(getAllocator()); + } + + optCseArrLenMap->Set(arrLen, compare); + } + } +} + /***************************************************************************** * * Compute each blocks bbCseGen @@ -782,7 +892,7 @@ void Compiler::optValnumCSE_InitDataFlow() if (init_to_zero) { /* Initialize to {ZERO} prior to dataflow */ - block->bbCseIn = BitVecOps::MakeCopy(cseTraits, cseEmpty); + block->bbCseIn = BitVecOps::MakeEmpty(cseTraits); } else { @@ -793,7 +903,7 @@ void Compiler::optValnumCSE_InitDataFlow() block->bbCseOut = BitVecOps::MakeCopy(cseTraits, cseFull); /* Initialize to {ZERO} prior to locating the CSE candidates */ - block->bbCseGen = BitVecOps::MakeCopy(cseTraits, cseEmpty); + block->bbCseGen = BitVecOps::MakeEmpty(cseTraits); } // We walk the set of CSE candidates and set the bit corresponsing to the CSEindex @@ -847,42 +957,31 @@ void Compiler::optValnumCSE_InitDataFlow() */ class CSE_DataFlow { -private: - EXPSET_TP m_preMergeOut; - - Compiler* m_pCompiler; + BitVecTraits* m_pBitVecTraits; + EXPSET_TP m_preMergeOut; public: - CSE_DataFlow(Compiler* pCompiler) : m_pCompiler(pCompiler) + CSE_DataFlow(Compiler* pCompiler) : m_pBitVecTraits(pCompiler->cseTraits), m_preMergeOut(BitVecOps::UninitVal()) { } - Compiler* getCompiler() - { - return m_pCompiler; - } - // At the start of the merge function of the dataflow equations, initialize premerge state (to detect changes.) void StartMerge(BasicBlock* block) { - m_preMergeOut = BitVecOps::MakeCopy(m_pCompiler->cseTraits, block->bbCseOut); + BitVecOps::Assign(m_pBitVecTraits, m_preMergeOut, block->bbCseOut); } // During merge, perform the actual merging of the predecessor's (since this is a forward analysis) dataflow flags. void Merge(BasicBlock* block, BasicBlock* predBlock, flowList* preds) { - BitVecOps::IntersectionD(m_pCompiler->cseTraits, block->bbCseIn, predBlock->bbCseOut); + BitVecOps::IntersectionD(m_pBitVecTraits, block->bbCseIn, predBlock->bbCseOut); } // At the end of the merge store results of the dataflow equations, in a postmerge state. bool EndMerge(BasicBlock* block) { - BitVecTraits* traits = m_pCompiler->cseTraits; - EXPSET_TP mergeOut = BitVecOps::MakeCopy(traits, block->bbCseIn); - BitVecOps::UnionD(traits, mergeOut, block->bbCseGen); - BitVecOps::IntersectionD(traits, mergeOut, block->bbCseOut); - BitVecOps::Assign(traits, block->bbCseOut, mergeOut); - return (!BitVecOps::Equal(traits, mergeOut, m_preMergeOut)); + BitVecOps::DataFlowD(m_pBitVecTraits, block->bbCseOut, block->bbCseGen, block->bbCseIn); + return !BitVecOps::Equal(m_pBitVecTraits, block->bbCseOut, m_preMergeOut); } }; @@ -948,6 +1047,8 @@ void Compiler::optValnumCSE_Availablity() printf("Labeling the CSEs with Use/Def information\n"); } #endif + EXPSET_TP available_cses = BitVecOps::MakeEmpty(cseTraits); + for (BasicBlock* block = fgFirstBB; block; block = block->bbNext) { GenTreePtr stmt; @@ -957,7 +1058,7 @@ void Compiler::optValnumCSE_Availablity() compCurBB = block; - EXPSET_TP available_cses = BitVecOps::MakeCopy(cseTraits, block->bbCseIn); + BitVecOps::Assign(cseTraits, available_cses, block->bbCseIn); optCSEweight = block->getBBWeight(this); @@ -1103,6 +1204,18 @@ public: continue; } +#if FEATURE_FIXED_OUT_ARGS + // Skip the OutgoingArgArea in computing frame size, since + // its size is not yet known and it doesn't affect local + // offsets from the frame pointer (though it may affect + // them from the stack pointer). + noway_assert(m_pCompiler->lvaOutgoingArgSpaceVar != BAD_VAR_NUM); + if (lclNum == m_pCompiler->lvaOutgoingArgSpaceVar) + { + continue; + } +#endif // FEATURE_FIXED_OUT_ARGS + bool onStack = (regAvailEstimate == 0); // true when it is likely that this LclVar will have a stack home // Some LclVars always have stack homes @@ -1909,6 +2022,39 @@ public: // use to fetch the same value with no reload, so we can safely propagate that // conservative VN to this use. This can help range check elimination later on. cse->gtVNPair.SetConservative(defConservativeVN); + + GenTreePtr cmp; + if ((exp->OperGet() == GT_ARR_LENGTH) && (m_pCompiler->optCseArrLenMap != nullptr) && + (m_pCompiler->optCseArrLenMap->Lookup(exp, &cmp))) + { + // Propagate the new value number to this compare node as well, since + // subsequent range check elimination will try to correlate it with + // the other appearances that are getting CSEd. + + ValueNumStore* vnStore = m_pCompiler->vnStore; + ValueNum oldCmpVN = cmp->gtVNPair.GetConservative(); + ValueNumStore::ArrLenArithBoundInfo info; + ValueNum newCmpArgVN; + if (vnStore->IsVNArrLenBound(oldCmpVN)) + { + // Comparison is against the array length directly. + + newCmpArgVN = defConservativeVN; + vnStore->GetArrLenBoundInfo(oldCmpVN, &info); + } + else + { + // Comparison is against the array length +/- some offset. + + assert(vnStore->IsVNArrLenArithBound(oldCmpVN)); + vnStore->GetArrLenArithBoundInfo(oldCmpVN, &info); + newCmpArgVN = vnStore->VNForFunc(vnStore->TypeOfVN(info.arrOp), (VNFunc)info.arrOper, + info.arrOp, defConservativeVN); + } + ValueNum newCmpVN = vnStore->VNForFunc(vnStore->TypeOfVN(oldCmpVN), (VNFunc)info.cmpOper, + info.cmpOp, newCmpArgVN); + cmp->gtVNPair.SetConservative(newCmpVN); + } } #ifdef DEBUG cse->gtDebugFlags |= GTF_DEBUG_VAR_CSE_REF; |