summaryrefslogtreecommitdiff
path: root/src/jit/earlyprop.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/jit/earlyprop.cpp')
-rw-r--r--src/jit/earlyprop.cpp433
1 files changed, 433 insertions, 0 deletions
diff --git a/src/jit/earlyprop.cpp b/src/jit/earlyprop.cpp
new file mode 100644
index 0000000000..0d760513f8
--- /dev/null
+++ b/src/jit/earlyprop.cpp
@@ -0,0 +1,433 @@
+//
+// Copyright (c) Microsoft. All rights reserved.
+// Licensed under the MIT license. See LICENSE file in the project root for full license information.
+//
+//
+// Early Value Propagation
+//
+// This phase performs an SSA-based value propagation optimization, currently only applies to array
+// lengths and runtime type handles. An SSA-based backwards tracking of local variables is performed
+// at each point of interest, e.g., an array length reference site or a method table reference site.
+// The tracking continues until an interesting value is encountered. The value is then used to rewrite
+// the source site.
+//
+///////////////////////////////////////////////////////////////////////////////////////
+
+#include "jitpch.h"
+#include "ssabuilder.h"
+
+
+bool Compiler::optDoEarlyPropForFunc()
+{
+ bool propArrayLen = (optMethodFlags & OMF_HAS_NEWARRAY) && (optMethodFlags & OMF_HAS_ARRAYREF);
+ bool propGetType = (optMethodFlags & OMF_HAS_NEWOBJ) && (optMethodFlags & OMF_HAS_VTABLEREF);
+ return propArrayLen || propGetType;
+}
+
+bool Compiler::optDoEarlyPropForBlock(BasicBlock* block)
+{
+ bool bbHasArrayRef = (block->bbFlags & BBF_HAS_INDX) != 0;
+ bool bbHasVtableRef = (block->bbFlags & BBF_HAS_VTABREF) != 0;
+ return bbHasArrayRef || bbHasVtableRef;
+}
+
+//--------------------------------------------------------------------
+// gtIsVtableRef: Return true if the tree is a method table reference.
+//
+// Arguments:
+// tree - The input tree.
+//
+// Return Value:
+// Return true if the tree is a method table reference.
+
+bool Compiler::gtIsVtableRef(GenTreePtr tree)
+{
+ if (tree->OperGet() == GT_IND)
+ {
+ GenTreeIndir* indir = tree->AsIndir();
+
+ if (!indir->HasIndex())
+ {
+ // Check if the base is an reference pointer.
+ if (indir->Base()->TypeGet() == TYP_REF)
+ {
+ return true;
+ }
+ }
+ }
+
+ return false;
+}
+
+//------------------------------------------------------------------------------
+// getArrayLengthFromAllocation: Return the array length for an array allocation
+// helper call.
+//
+// Arguments:
+// tree - The array allocation helper call.
+//
+// Return Value:
+// Return the array length node.
+
+GenTreePtr Compiler::getArrayLengthFromAllocation(GenTreePtr tree)
+{
+ assert(tree != nullptr);
+
+ if (tree->OperGet() == GT_CALL)
+ {
+ GenTreeCall* call = tree->AsCall();
+
+ if (call->gtCallType == CT_HELPER)
+ {
+ CorInfoHelpFunc helpFunc = eeGetHelperNum(call->gtCallMethHnd);
+
+ if (call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWARR_1_DIRECT) ||
+ call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWARR_1_OBJ) ||
+ call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWARR_1_VC) ||
+ call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWARR_1_ALIGN8))
+ {
+ // This is an array allocation site. Grab the array length node.
+ return gtArgEntryByArgNum(call, 1)->node;
+ }
+ }
+ }
+
+ return nullptr;
+}
+
+//-----------------------------------------------------------------------------
+// getObjectHandleNodeFromAllocation: Return the type handle for an object allocation
+// helper call.
+//
+// Arguments:
+// tree - The object allocation helper call.
+//
+// Return Value:
+// Return the object type handle node.
+
+GenTreePtr Compiler::getObjectHandleNodeFromAllocation(GenTreePtr tree)
+{
+ assert(tree != nullptr);
+
+ if (tree->OperGet() == GT_CALL)
+ {
+ GenTreeCall* call = tree->AsCall();
+
+ if (call->gtCallType == CT_HELPER)
+ {
+ CorInfoHelpFunc helpFunc = eeGetHelperNum(call->gtCallMethHnd);
+
+ if (call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWFAST) ||
+ call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWSFAST) ||
+ call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWSFAST_ALIGN8) ||
+ call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWARR_1_DIRECT) ||
+ call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWARR_1_OBJ) ||
+ call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWARR_1_VC) ||
+ call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_NEWARR_1_ALIGN8))
+ {
+ // This is an object allocation site. Return the runtime type handle node.
+ fgArgTabEntryPtr argTabEntry = gtArgEntryByArgNum(call, 0);
+ return argTabEntry->node;
+ }
+ }
+ }
+
+ return nullptr;
+}
+
+//------------------------------------------------------------------------------------------
+// optEarlyProp: The entry point of the early value propagation.
+//
+// Notes:
+// This phase performs an SSA-based value propagation, including
+// 1. Array length propagation.
+// 2. Runtime type handle propagation.
+//
+// For array length propagation, a demand-driven SSA-based backwards tracking of constant
+// array lengths is performed at each array length reference site which is in form of a
+// GT_ARR_LENGTH node. When a GT_ARR_LENGTH node is seen, the array ref pointer which is
+// the only child node of the GT_ARR_LENGTH is tracked. This is only done for array ref
+// pointers that have valid SSA forms.The tracking is along SSA use-def chain and stops
+// at the original array allocation site where we can grab the array length. The
+// GT_ARR_LENGTH node will then be rewritten to a GT_CNS_INT node if the array length is
+// constant.
+//
+// Similarly, the same algorithm also applies to rewriting a method table (also known as
+// vtable) reference site which is in form of GT_INDIR node. The base pointer, which is
+// an object reference pointer, is treated in the same way as an array reference pointer.
+
+void Compiler::optEarlyProp()
+{
+#ifdef DEBUG
+ if (verbose)
+ {
+ printf("*************** In optEarlyProp()\n");
+ }
+#endif
+
+ assert(fgSsaPassesCompleted == 1);
+
+ if (!optDoEarlyPropForFunc())
+ {
+ return;
+ }
+
+ for (BasicBlock* block = fgFirstBB; block != nullptr; block = block->bbNext)
+ {
+ if (!optDoEarlyPropForBlock(block))
+ continue;
+
+ compCurBB = block;
+
+ for (GenTreeStmt* stmt = block->firstStmt(); stmt != nullptr; )
+ {
+ // Preserve the next link before the propagation and morph.
+ GenTreeStmt* next = stmt->gtNextStmt;
+
+ compCurStmt = stmt;
+
+ // Walk the stmt tree in linear order to rewrite any array length reference with a
+ // constant array length.
+ bool isRewritten = false;
+ for (GenTreePtr tree = stmt->gtStmt.gtStmtList; tree != nullptr; tree = tree->gtNext)
+ {
+ if (optEarlyPropRewriteTree(tree))
+ {
+ isRewritten = true;
+ }
+ }
+
+ // Morph the stmt and update the evaluation order if the stmt has been rewritten.
+ if (isRewritten)
+ {
+ gtSetStmtInfo(stmt);
+ fgSetStmtSeq(stmt);
+ }
+
+ stmt = next;
+ }
+ }
+
+#ifdef DEBUG
+ if (verbose)
+ {
+ JITDUMP("\nAfter optEarlyProp:\n");
+ fgDispBasicBlocks(/*dumpTrees*/true);
+ }
+#endif
+}
+
+//----------------------------------------------------------------
+// optEarlyPropRewriteValue: Rewrite a tree to the actual value.
+//
+// Arguments:
+// tree - The input tree node to be rewritten.
+//
+// Return Value:
+// Return true iff "tree" is successfully rewritten.
+
+bool Compiler::optEarlyPropRewriteTree(GenTreePtr tree)
+{
+ GenTreePtr objectRefPtr = nullptr;
+ optPropKind propKind = optPropKind::OPK_INVALID;
+
+ if (tree->OperGet() == GT_ARR_LENGTH)
+ {
+ objectRefPtr = tree->gtOp.gtOp1;
+ propKind = optPropKind::OPK_ARRAYLEN;
+ }
+ else if (gtIsVtableRef(tree))
+ {
+ objectRefPtr = tree->gtOp.gtOp1;
+ propKind = optPropKind::OPK_OBJ_GETTYPE;
+ }
+ else
+ {
+ return false;
+ }
+
+ if (!objectRefPtr->OperIsScalarLocal() ||
+ fgExcludeFromSsa(objectRefPtr->AsLclVarCommon()->GetLclNum()))
+
+ {
+ return false;
+ }
+
+ bool isRewritten = false;
+ GenTreePtr root = compCurStmt;
+ unsigned lclNum = objectRefPtr->AsLclVarCommon()->GetLclNum();
+ unsigned ssaNum = objectRefPtr->AsLclVarCommon()->GetSsaNum();
+
+ GenTreePtr actualVal = optPropGetValue(lclNum, ssaNum, propKind);
+
+ if (actualVal != nullptr)
+ {
+ if (propKind == optPropKind::OPK_ARRAYLEN)
+ {
+ assert(actualVal->IsCnsIntOrI());
+
+ if (actualVal->gtIntCon.gtIconVal > INT32_MAX)
+ {
+ // Don't propagate array lengths that are beyond the maximum value of a GT_ARR_LENGTH.
+ // node. CORINFO_HELP_NEWARR_1_OBJ helper call allows to take a long integer as the
+ // array length argument, but the type of GT_ARR_LENGTH is always INT32.
+ return false;
+ }
+ }
+ else if (propKind == optPropKind::OPK_OBJ_GETTYPE)
+ {
+ assert(actualVal->IsCnsIntOrI());
+ }
+
+#ifdef DEBUG
+ if (verbose)
+ {
+ printf("optEarlyProp Rewriting BB%02u\n", compCurBB->bbNum);
+ gtDispTree(root);
+ printf("\n");
+ }
+#endif
+ // Rewrite the tree using a copy of "actualVal"
+ GenTreePtr actualValCopy;
+ var_types origType = tree->gtType;
+
+ if (actualVal->GetNodeSize() <= tree->GetNodeSize())
+ {
+ actualValCopy = tree;
+ }
+ else
+ {
+ actualValCopy = gtNewLargeOperNode(GT_ADD, TYP_INT);
+ }
+
+ fgWalkTreePre(&tree, Compiler::lvaDecRefCntsCB, (void*)this, true);
+
+ actualValCopy->CopyFrom(actualVal, this);
+ actualValCopy->gtType = origType;
+
+ fgWalkTreePre(&actualValCopy, Compiler::lvaIncRefCntsCB, (void*)this, true);
+
+ if (actualValCopy != tree)
+ {
+ gtReplaceTree(root, tree, actualValCopy);
+ }
+
+ isRewritten = true;
+
+#ifdef DEBUG
+ if (verbose)
+ {
+ printf("to\n");
+ gtDispTree(compCurStmt);
+ printf("\n");
+ }
+#endif
+ }
+
+ return isRewritten;
+}
+
+//-------------------------------------------------------------------------------------------
+// optPropGetValue: Given an SSA object ref pointer, get the value needed based on valueKind.
+//
+// Arguments:
+// lclNum - The local var number of the ref pointer.
+// ssaNum - The SSA var number of the ref pointer.
+// valueKind - The kind of value of interest.
+//
+// Return Value:
+// Return the corresponding value based on valueKind.
+
+GenTreePtr Compiler::optPropGetValue(unsigned lclNum, unsigned ssaNum, optPropKind valueKind)
+{
+ return optPropGetValueRec(lclNum, ssaNum, valueKind, 0);
+}
+
+//-----------------------------------------------------------------------------------
+// optPropGetValueRec: Given an SSA object ref pointer, get the value needed based on valueKind
+// within a recursion bound.
+//
+// Arguments:
+// lclNum - The local var number of the array pointer.
+// ssaNum - The SSA var number of the array pointer.
+// valueKind - The kind of value of interest.
+// walkDepth - Current recursive walking depth.
+//
+// Return Value:
+// Return the corresponding value based on valueKind.
+
+GenTreePtr Compiler::optPropGetValueRec(unsigned lclNum, unsigned ssaNum, optPropKind valueKind, int walkDepth)
+{
+ if (ssaNum == SsaConfig::RESERVED_SSA_NUM)
+ {
+ return nullptr;
+ }
+
+ SSAName ssaName(lclNum, ssaNum);
+ GenTreePtr value = nullptr;
+
+ // Bound the recursion with a hard limit.
+ if (walkDepth > optEarlyPropRecurBound)
+ {
+ return nullptr;
+ }
+
+ // Track along the use-def chain to get the array length
+ GenTreePtr treelhs = lvaTable[lclNum].GetPerSsaData(ssaNum)->m_defLoc.m_tree;
+
+ if (treelhs == nullptr)
+ {
+ // Incoming parameters or live-in variables don't have actual definition tree node
+ // for their FIRST_SSA_NUM. See SsaBuilder::RenameVariables.
+ assert(ssaNum == SsaConfig::FIRST_SSA_NUM);
+ }
+ else
+ {
+ GenTreePtr *lhsPtr;
+ GenTreePtr treeDefParent = treelhs->gtGetParent(&lhsPtr);
+
+ if (treeDefParent->OperGet() == GT_ASG)
+ {
+ assert(treelhs == treeDefParent->gtGetOp1());
+ GenTreePtr treeRhs = treeDefParent->gtGetOp2();
+
+ if (treeRhs->OperIsScalarLocal() && !fgExcludeFromSsa(treeRhs->AsLclVarCommon()->GetLclNum()))
+ {
+ // Recursively track the Rhs
+ unsigned rhsLclNum = treeRhs->AsLclVarCommon()->GetLclNum();
+ unsigned rhsSsaNum = treeRhs->AsLclVarCommon()->GetSsaNum();
+
+ value = optPropGetValueRec(rhsLclNum, rhsSsaNum, valueKind, walkDepth + 1);
+ }
+ else
+ {
+ if (valueKind == optPropKind::OPK_ARRAYLEN)
+ {
+ value = getArrayLengthFromAllocation(treeRhs);
+ if (value != nullptr)
+ {
+ if (!value->IsCnsIntOrI())
+ {
+ // Leave out non-constant-sized array
+ value = nullptr;
+ }
+ }
+ }
+ else if(valueKind == optPropKind::OPK_OBJ_GETTYPE)
+ {
+ value = getObjectHandleNodeFromAllocation(treeRhs);
+ if (value != nullptr)
+ {
+ if (!value->IsCnsIntOrI())
+ {
+ // Leave out non-constant-sized array
+ value = nullptr;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ return value;
+}