summaryrefslogtreecommitdiff
path: root/src/jit/optcse.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/jit/optcse.cpp')
-rw-r--r--src/jit/optcse.cpp200
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;