diff options
Diffstat (limited to 'src/jit/copyprop.cpp')
-rw-r--r-- | src/jit/copyprop.cpp | 463 |
1 files changed, 463 insertions, 0 deletions
diff --git a/src/jit/copyprop.cpp b/src/jit/copyprop.cpp new file mode 100644 index 0000000000..bf714f0963 --- /dev/null +++ b/src/jit/copyprop.cpp @@ -0,0 +1,463 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +// +// +// CopyProp +// +// This stage performs value numbering based copy propagation. Since copy propagation +// is about data flow, we cannot find them in assertion prop phase. In assertion prop +// we can identify copies, like so: if (a == b) else, i.e., control flow assertions. +// +// To identify data flow copies, we'll follow a similar approach to SSA renaming. +// We would walk each path in the graph keeping track of every live definition. Thus +// when we see a variable that shares the VN with a live definition, we'd replace this +// variable with the variable in the live definition, if suitable. +// +/////////////////////////////////////////////////////////////////////////////////////// + +#include "jitpch.h" +#include "ssabuilder.h" + +template <typename T> +inline static T* allocate_any(jitstd::allocator<void>& alloc, size_t count = 1) +{ + return jitstd::allocator<T>(alloc).allocate(count); +} + +/************************************************************************************** + * + * Corresponding to the live definition pushes, pop the stack as we finish a sub-paths + * of the graph originating from the block. Refer SSA renaming for any additional info. + * "curSsaName" tracks the currently live definitions. + */ +void Compiler::optBlockCopyPropPopStacks(BasicBlock* block, LclNumToGenTreePtrStack* curSsaName) +{ + for (GenTreePtr stmt = block->bbTreeList; stmt; stmt = stmt->gtNext) + { + for (GenTreePtr tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext) + { + if (!tree->IsLocal()) + { + continue; + } + unsigned lclNum = tree->gtLclVarCommon.gtLclNum; + if (fgExcludeFromSsa(lclNum)) + { + continue; + } + if (tree->gtFlags & GTF_VAR_DEF) + { + GenTreePtrStack* stack = nullptr; + curSsaName->Lookup(lclNum, &stack); + stack->Pop(); + if (stack->Height() == 0) + { + curSsaName->Remove(lclNum); + } + } + } + } +} + +/******************************************************************************************************* + * + * Given the "lclVar" and "copyVar" compute if the copy prop will be beneficial. + * + */ +int Compiler::optCopyProp_LclVarScore(LclVarDsc* lclVarDsc, LclVarDsc* copyVarDsc, bool preferOp2) +{ + int score = 0; + + if (lclVarDsc->lvVolatileHint) + { + score += 4; + } + + if (copyVarDsc->lvVolatileHint) + { + score -= 4; + } + + if (lclVarDsc->lvDoNotEnregister) + { + score += 4; + } + + if (copyVarDsc->lvDoNotEnregister) + { + score -= 4; + } + +#ifdef _TARGET_X86_ + // For doubles we also prefer to change parameters into non-parameter local variables + if (lclVarDsc->lvType == TYP_DOUBLE) + { + if (lclVarDsc->lvIsParam) + { + score += 2; + } + + if (copyVarDsc->lvIsParam) + { + score -= 2; + } + } +#endif + + // Otherwise we prefer to use the op2LclNum + return score + ((preferOp2) ? 1 : -1); +} + +/************************************************************************************** + * + * Perform copy propagation on a given tree as we walk the graph and if it is a local + * variable, then look up all currently live definitions and check if any of those + * definitions share the same value number. If so, then we can make the replacement. + * + */ +void Compiler::optCopyProp(BasicBlock* block, GenTreePtr stmt, GenTreePtr tree, LclNumToGenTreePtrStack* curSsaName) +{ + // TODO-Review: EH successor/predecessor iteration seems broken. + if (block->bbCatchTyp == BBCT_FINALLY || block->bbCatchTyp == BBCT_FAULT) + { + return; + } + + // If not local nothing to do. + if (!tree->IsLocal()) + { + return; + } + if (tree->OperGet() == GT_PHI_ARG || tree->OperGet() == GT_LCL_FLD) + { + return; + } + + // Propagate only on uses. + if (tree->gtFlags & GTF_VAR_DEF || tree->gtFlags & GTF_VAR_USEDEF) + { + return; + } + unsigned lclNum = tree->AsLclVarCommon()->GetLclNum(); + + // Skip address exposed variables. + if (fgExcludeFromSsa(lclNum)) + { + return; + } + + assert(tree->gtVNPair.GetConservative() != ValueNumStore::NoVN); + + for (LclNumToGenTreePtrStack::KeyIterator iter = curSsaName->Begin(); !iter.Equal(curSsaName->End()); ++iter) + { + unsigned newLclNum = iter.Get(); + + GenTreePtr op = iter.GetValue()->Index(0); + + // Nothing to do if same. + if (lclNum == newLclNum) + { + continue; + } + + // Skip variables with assignments embedded in the statement (i.e., with a comma). Because we + // are not currently updating their SSA names as live in the copy-prop pass of the stmt. + if (VarSetOps::IsMember(this, optCopyPropKillSet, lvaTable[newLclNum].lvVarIndex)) + { + continue; + } + + if (op->gtFlags & GTF_VAR_CAST) + { + continue; + } + if (gsShadowVarInfo != nullptr && lvaTable[newLclNum].lvIsParam && + gsShadowVarInfo[newLclNum].shadowCopy == lclNum) + { + continue; + } + ValueNum opVN = GetUseAsgDefVNOrTreeVN(op); + if (opVN == ValueNumStore::NoVN) + { + continue; + } + if (op->TypeGet() != tree->TypeGet()) + { + continue; + } + if (opVN != tree->gtVNPair.GetConservative()) + { + continue; + } + if (optCopyProp_LclVarScore(&lvaTable[lclNum], &lvaTable[newLclNum], true) <= 0) + { + continue; + } + // Check whether the newLclNum is live before being substituted. Otherwise, we could end + // up in a situation where there must've been a phi node that got pruned because the variable + // is not live anymore. For example, + // if + // x0 = 1 + // else + // x1 = 2 + // print(c) <-- x is not live here. Let's say 'c' shares the value number with "x0." + // + // If we simply substituted 'c' with "x0", we would be wrong. Ideally, there would be a phi + // node x2 = phi(x0, x1) which can then be used to substitute 'c' with. But because of pruning + // there would be no such phi node. To solve this we'll check if 'x' is live, before replacing + // 'c' with 'x.' + if (!lvaTable[newLclNum].lvVerTypeInfo.IsThisPtr()) + { + if (lvaTable[newLclNum].lvAddrExposed) + { + continue; + } + + // We compute liveness only on tracked variables. So skip untracked locals. + if (!lvaTable[newLclNum].lvTracked) + { + continue; + } + + // Because of this dependence on live variable analysis, CopyProp phase is immediately + // after Liveness, SSA and VN. + if (!VarSetOps::IsMember(this, compCurLife, lvaTable[newLclNum].lvVarIndex)) + { + continue; + } + } + unsigned newSsaNum = SsaConfig::RESERVED_SSA_NUM; + if (op->gtFlags & (GTF_VAR_DEF | GTF_VAR_USEDEF)) + { + newSsaNum = GetSsaNumForLocalVarDef(op); + } + else // parameters, this pointer etc. + { + newSsaNum = op->AsLclVarCommon()->GetSsaNum(); + } + + if (newSsaNum == SsaConfig::RESERVED_SSA_NUM) + { + continue; + } + +#ifdef DEBUG + if (verbose) + { + JITDUMP("VN based copy assertion for "); + printTreeID(tree); + printf(" V%02d @%08X by ", lclNum, tree->GetVN(VNK_Conservative)); + printTreeID(op); + printf(" V%02d @%08X.\n", newLclNum, op->GetVN(VNK_Conservative)); + gtDispTree(tree, nullptr, nullptr, true); + } +#endif + + lvaTable[lclNum].decRefCnts(block->getBBWeight(this), this); + lvaTable[newLclNum].incRefCnts(block->getBBWeight(this), this); + tree->gtLclVarCommon.SetLclNum(newLclNum); + tree->AsLclVarCommon()->SetSsaNum(newSsaNum); +#ifdef DEBUG + if (verbose) + { + printf("copy propagated to:\n"); + gtDispTree(tree, nullptr, nullptr, true); + } +#endif + break; + } + return; +} + +/************************************************************************************** + * + * Helper to check if tree is a local that participates in SSA numbering. + */ +bool Compiler::optIsSsaLocal(GenTreePtr tree) +{ + return tree->IsLocal() && !fgExcludeFromSsa(tree->AsLclVarCommon()->GetLclNum()); +} + +/************************************************************************************** + * + * Perform copy propagation using currently live definitions on the current block's + * variables. Also as new definitions are encountered update the "curSsaName" which + * tracks the currently live definitions. + * + */ +void Compiler::optBlockCopyProp(BasicBlock* block, LclNumToGenTreePtrStack* curSsaName) +{ + JITDUMP("Copy Assertion for BB%02u\n", block->bbNum); + + // There are no definitions at the start of the block. So clear it. + compCurLifeTree = nullptr; + VarSetOps::Assign(this, compCurLife, block->bbLiveIn); + for (GenTreePtr stmt = block->bbTreeList; stmt; stmt = stmt->gtNext) + { + VarSetOps::ClearD(this, optCopyPropKillSet); + + // Walk the tree to find if any local variable can be replaced with current live definitions. + for (GenTreePtr tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext) + { + compUpdateLife</*ForCodeGen*/ false>(tree); + optCopyProp(block, stmt, tree, curSsaName); + + // TODO-Review: Merge this loop with the following loop to correctly update the + // live SSA num while also propagating copies. + // + // 1. This loop performs copy prop with currently live (on-top-of-stack) SSA num. + // 2. The subsequent loop maintains a stack for each lclNum with + // currently active SSA numbers when definitions are encountered. + // + // If there is an embedded definition using a "comma" in a stmt, then the currently + // live SSA number will get updated only in the next loop (2). However, this new + // definition is now supposed to be live (on tos). If we did not update the stacks + // using (2), copy prop (1) will use a SSA num defined outside the stmt ignoring the + // embedded update. Killing the variable is a simplification to produce 0 ASM diffs + // for an update release. + // + if (optIsSsaLocal(tree) && (tree->gtFlags & GTF_VAR_DEF)) + { + VarSetOps::AddElemD(this, optCopyPropKillSet, lvaTable[tree->gtLclVarCommon.gtLclNum].lvVarIndex); + } + } + + // This logic must be in sync with SSA renaming process. + for (GenTreePtr tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext) + { + if (!optIsSsaLocal(tree)) + { + continue; + } + + unsigned lclNum = tree->gtLclVarCommon.gtLclNum; + + // As we encounter a definition add it to the stack as a live definition. + if (tree->gtFlags & GTF_VAR_DEF) + { + GenTreePtrStack* stack; + if (!curSsaName->Lookup(lclNum, &stack)) + { + stack = new (getAllocator()) GenTreePtrStack(this); + } + stack->Push(tree); + curSsaName->Set(lclNum, stack); + } + // If we encounter first use of a param or this pointer add it as a live definition. + // Since they are always live, do it only once. + else if ((tree->gtOper == GT_LCL_VAR) && !(tree->gtFlags & (GTF_VAR_USEASG | GTF_VAR_USEDEF)) && + (lvaTable[lclNum].lvIsParam || lvaTable[lclNum].lvVerTypeInfo.IsThisPtr())) + { + GenTreePtrStack* stack; + if (!curSsaName->Lookup(lclNum, &stack)) + { + stack = new (getAllocator()) GenTreePtrStack(this); + stack->Push(tree); + curSsaName->Set(lclNum, stack); + } + } + } + } +} + +/************************************************************************************** + * + * This stage performs value numbering based copy propagation. Since copy propagation + * is about data flow, we cannot find them in assertion prop phase. In assertion prop + * we can identify copies that like so: if (a == b) else, i.e., control flow assertions. + * + * To identify data flow copies, we follow a similar approach to SSA renaming. We walk + * each path in the graph keeping track of every live definition. Thus when we see a + * variable that shares the VN with a live definition, we'd replace this variable with + * the variable in the live definition. + * + * We do this to be in conventional SSA form. This can very well be changed later. + * + * For example, on some path in the graph: + * a0 = x0 + * : <- other blocks + * : + * a1 = y0 + * : + * : <- other blocks + * b0 = x0, we cannot substitute x0 with a0, because currently our backend doesn't + * treat lclNum and ssaNum together as a variable, but just looks at lclNum. If we + * substituted x0 with a0, then we'd be in general SSA form. + * + */ +void Compiler::optVnCopyProp() +{ +#ifdef DEBUG + if (verbose) + { + printf("*************** In optVnCopyProp()\n"); + } +#endif + + if (fgSsaPassesCompleted == 0) + { + return; + } + jitstd::allocator<void> allocator(getAllocator()); + + // Compute the domTree to use. + BlkToBlkSetMap* domTree = new (getAllocator()) BlkToBlkSetMap(getAllocator()); + domTree->Reallocate(fgBBcount * 3 / 2); // Prime the allocation + SsaBuilder::ComputeDominators(this, domTree); + + struct BlockWork + { + BasicBlock* m_blk; + bool m_processed; + + BlockWork(BasicBlock* blk, bool processed = false) : m_blk(blk), m_processed(processed) + { + } + }; + typedef jitstd::vector<BlockWork> BlockWorkStack; + + VarSetOps::AssignNoCopy(this, compCurLife, VarSetOps::MakeEmpty(this)); + VarSetOps::AssignNoCopy(this, optCopyPropKillSet, VarSetOps::MakeEmpty(this)); + + // The map from lclNum to its recently live definitions as a stack. + LclNumToGenTreePtrStack curSsaName(getAllocator()); + + BlockWorkStack* worklist = + new (allocate_any<BlockWorkStack>(allocator), jitstd::placement_t()) BlockWorkStack(allocator); + + worklist->push_back(BlockWork(fgFirstBB)); + while (!worklist->empty()) + { + BlockWork work = worklist->back(); + worklist->pop_back(); + + BasicBlock* block = work.m_blk; + if (work.m_processed) + { + // Pop all the live definitions for this block. + optBlockCopyPropPopStacks(block, &curSsaName); + continue; + } + + // Generate copy assertions in this block, and keeping curSsaName variable up to date. + worklist->push_back(BlockWork(block, true)); + + optBlockCopyProp(block, &curSsaName); + + // Add dom children to work on. + BlkSet* pBlkSet; + if (domTree->Lookup(block, &pBlkSet)) + { + for (BlkSet::KeyIterator child = pBlkSet->Begin(); !child.Equal(pBlkSet->End()); ++child) + { + worklist->push_back(BlockWork(child.Get())); + } + } + } + + // Tracked variable count increases after CopyProp, so don't keep a shorter array around. + // Destroy (release) the varset. + VarSetOps::AssignNoCopy(this, compCurLife, VarSetOps::UninitVal()); +} |