From a67f5698705dab8cb58bd07c733ac492e81ad28f Mon Sep 17 00:00:00 2001 From: Eugene Rozenfeld Date: Tue, 6 Sep 2016 16:51:23 -0700 Subject: [PATCH] Make GT_LIST processing non-recursive to avoid StackOverflow. We had some internal cases where crossgen failed with StackOverflow exception when compiling huge methods. In particular, the methods had GT_PHI nodes with huge number of arguments. StackOverflow was happening in multiple places. Recent LIR changes eliminated two of those places, these changes eliminate two more: gtSetEvalOrder and fgDebugCheckFlags (debug only). We already had gtSetListOrder but it was only used for call arg lists. I made gtSetListOrder non-recursive and also generalized to handle other GT_LIST nodes. With that with these changes the huge repros can now be crossgen'd. I verified no assembly diffs in SuperPMI. I'm verifying overall throughput effect. --- src/jit/compiler.h | 3 +- src/jit/flowgraph.cpp | 269 ++++++++++++++++++++++++++++++-------------------- src/jit/gentree.cpp | 167 ++++++++++++++++++++++--------- 3 files changed, 282 insertions(+), 157 deletions(-) diff --git a/src/jit/compiler.h b/src/jit/compiler.h index fd1f19e..c5dca50 100644 --- a/src/jit/compiler.h +++ b/src/jit/compiler.h @@ -1994,7 +1994,7 @@ public: unsigned gtHashValue(GenTree* tree); - unsigned gtSetListOrder(GenTree* list, bool regs); + unsigned gtSetListOrder(GenTree* list, bool regs, bool isListCallArgs); void gtWalkOp(GenTree** op1, GenTree** op2, GenTree* adr, bool constOnly); @@ -4201,6 +4201,7 @@ public: void fgDebugCheckLinks(bool morphTrees = false); void fgDebugCheckNodeLinks(BasicBlock* block, GenTreePtr stmt); void fgDebugCheckFlags(GenTreePtr tree); + void fgDebugCheckFlagsHelper(GenTreePtr tree, unsigned treeFlags, unsigned chkFlags); #endif #ifdef LEGACY_BACKEND diff --git a/src/jit/flowgraph.cpp b/src/jit/flowgraph.cpp index e894525..1c47073 100644 --- a/src/jit/flowgraph.cpp +++ b/src/jit/flowgraph.cpp @@ -20239,21 +20239,55 @@ void Compiler::fgDebugCheckFlags(GenTreePtr tree) } break; + case GT_LIST: + if ((op2 != nullptr) && op2->IsList()) + { + ArrayStack stack(this); + while ((tree->gtGetOp2() != nullptr) && tree->gtGetOp2()->IsList()) + { + stack.Push(tree); + tree = tree->gtGetOp2(); + } + + fgDebugCheckFlags(tree); + + while (stack.Height() > 0) + { + tree = stack.Pop(); + assert((tree->gtFlags & GTF_REVERSE_OPS) == 0); + fgDebugCheckFlags(tree->gtOp.gtOp1); + chkFlags |= (tree->gtOp.gtOp1->gtFlags & GTF_ALL_EFFECT); + chkFlags |= (tree->gtGetOp2()->gtFlags & GTF_ALL_EFFECT); + fgDebugCheckFlagsHelper(tree, (tree->gtFlags & GTF_ALL_EFFECT), chkFlags); + } + + return; + } + break; + default: break; } /* Recursively check the subtrees */ - if (op1) { fgDebugCheckFlags(op1); -} - if (op2) { fgDebugCheckFlags(op2); -} + if (op1) + { + fgDebugCheckFlags(op1); + } + if (op2) + { + fgDebugCheckFlags(op2); + } - if (op1) { chkFlags |= (op1->gtFlags & GTF_ALL_EFFECT); -} - if (op2) { chkFlags |= (op2->gtFlags & GTF_ALL_EFFECT); -} + if (op1) + { + chkFlags |= (op1->gtFlags & GTF_ALL_EFFECT); + } + if (op2) + { + chkFlags |= (op2->gtFlags & GTF_ALL_EFFECT); + } // We reuse the value of GTF_REVERSE_OPS for a GT_IND-specific flag, // so exempt that (unary) operator. @@ -20315,131 +20349,150 @@ void Compiler::fgDebugCheckFlags(GenTreePtr tree) /* See what kind of a special operator we have here */ - else { switch (tree->OperGet()) - { - case GT_CALL: + else + { + switch (tree->OperGet()) + { + case GT_CALL: - GenTreePtr args; - GenTreePtr argx; - GenTreeCall* call; + GenTreePtr args; + GenTreePtr argx; + GenTreeCall* call; - call = tree->AsCall(); + call = tree->AsCall(); - chkFlags |= GTF_CALL; + chkFlags |= GTF_CALL; - if ((treeFlags & GTF_EXCEPT) && !(chkFlags & GTF_EXCEPT)) - { - switch (eeGetHelperNum(tree->gtCall.gtCallMethHnd)) + if ((treeFlags & GTF_EXCEPT) && !(chkFlags & GTF_EXCEPT)) { - // Is this a helper call that can throw an exception ? - case CORINFO_HELP_LDIV: - case CORINFO_HELP_LMOD: - case CORINFO_HELP_METHOD_ACCESS_CHECK: - case CORINFO_HELP_FIELD_ACCESS_CHECK: - case CORINFO_HELP_CLASS_ACCESS_CHECK: - case CORINFO_HELP_DELEGATE_SECURITY_CHECK: - chkFlags |= GTF_EXCEPT; - break; - default: - break; + switch (eeGetHelperNum(tree->gtCall.gtCallMethHnd)) + { + // Is this a helper call that can throw an exception ? + case CORINFO_HELP_LDIV: + case CORINFO_HELP_LMOD: + case CORINFO_HELP_METHOD_ACCESS_CHECK: + case CORINFO_HELP_FIELD_ACCESS_CHECK: + case CORINFO_HELP_CLASS_ACCESS_CHECK: + case CORINFO_HELP_DELEGATE_SECURITY_CHECK: + chkFlags |= GTF_EXCEPT; + break; + default: + break; + } } - } - - if (call->gtCallObjp) - { - fgDebugCheckFlags(call->gtCallObjp); - chkFlags |= (call->gtCallObjp->gtFlags & GTF_SIDE_EFFECT); - if (call->gtCallObjp->gtFlags & GTF_ASG) + if (call->gtCallObjp) { - treeFlags |= GTF_ASG; + fgDebugCheckFlags(call->gtCallObjp); + chkFlags |= (call->gtCallObjp->gtFlags & GTF_SIDE_EFFECT); + + if (call->gtCallObjp->gtFlags & GTF_ASG) + { + treeFlags |= GTF_ASG; + } } - } - for (args = call->gtCallArgs; args; args = args->gtOp.gtOp2) - { - argx = args->gtOp.gtOp1; - fgDebugCheckFlags(argx); + for (args = call->gtCallArgs; args; args = args->gtOp.gtOp2) + { + argx = args->gtOp.gtOp1; + fgDebugCheckFlags(argx); - chkFlags |= (argx->gtFlags & GTF_SIDE_EFFECT); + chkFlags |= (argx->gtFlags & GTF_SIDE_EFFECT); - if (argx->gtFlags & GTF_ASG) - { - treeFlags |= GTF_ASG; + if (argx->gtFlags & GTF_ASG) + { + treeFlags |= GTF_ASG; + } } - } - for (args = call->gtCallLateArgs; args; args = args->gtOp.gtOp2) - { - argx = args->gtOp.gtOp1; - fgDebugCheckFlags(argx); + for (args = call->gtCallLateArgs; args; args = args->gtOp.gtOp2) + { + argx = args->gtOp.gtOp1; + fgDebugCheckFlags(argx); - chkFlags |= (argx->gtFlags & GTF_SIDE_EFFECT); + chkFlags |= (argx->gtFlags & GTF_SIDE_EFFECT); - if (argx->gtFlags & GTF_ASG) - { - treeFlags |= GTF_ASG; + if (argx->gtFlags & GTF_ASG) + { + treeFlags |= GTF_ASG; + } } - } - if ((call->gtCallType == CT_INDIRECT) && (call->gtCallCookie != nullptr)) - { - fgDebugCheckFlags(call->gtCallCookie); - chkFlags |= (call->gtCallCookie->gtFlags & GTF_SIDE_EFFECT); - } - - if (call->gtCallType == CT_INDIRECT) - { - fgDebugCheckFlags(call->gtCallAddr); - chkFlags |= (call->gtCallAddr->gtFlags & GTF_SIDE_EFFECT); - } + if ((call->gtCallType == CT_INDIRECT) && (call->gtCallCookie != nullptr)) + { + fgDebugCheckFlags(call->gtCallCookie); + chkFlags |= (call->gtCallCookie->gtFlags & GTF_SIDE_EFFECT); + } - if (call->IsUnmanaged() && - (call->gtCallMoreFlags & GTF_CALL_M_UNMGD_THISCALL)) - { - if (call->gtCallArgs->gtOp.gtOp1->OperGet() == GT_NOP) + if (call->gtCallType == CT_INDIRECT) { - noway_assert(call->gtCallLateArgs->gtOp.gtOp1->TypeGet() == TYP_I_IMPL || - call->gtCallLateArgs->gtOp.gtOp1->TypeGet() == TYP_BYREF); + fgDebugCheckFlags(call->gtCallAddr); + chkFlags |= (call->gtCallAddr->gtFlags & GTF_SIDE_EFFECT); } - else + + if (call->IsUnmanaged() && + (call->gtCallMoreFlags & GTF_CALL_M_UNMGD_THISCALL)) { - noway_assert(call->gtCallArgs->gtOp.gtOp1->TypeGet() == TYP_I_IMPL || - call->gtCallArgs->gtOp.gtOp1->TypeGet() == TYP_BYREF); + if (call->gtCallArgs->gtOp.gtOp1->OperGet() == GT_NOP) + { + noway_assert(call->gtCallLateArgs->gtOp.gtOp1->TypeGet() == TYP_I_IMPL || + call->gtCallLateArgs->gtOp.gtOp1->TypeGet() == TYP_BYREF); + } + else + { + noway_assert(call->gtCallArgs->gtOp.gtOp1->TypeGet() == TYP_I_IMPL || + call->gtCallArgs->gtOp.gtOp1->TypeGet() == TYP_BYREF); + } } - } - break; + break; - case GT_ARR_ELEM: + case GT_ARR_ELEM: - GenTreePtr arrObj; - unsigned dim; + GenTreePtr arrObj; + unsigned dim; - arrObj = tree->gtArrElem.gtArrObj; - fgDebugCheckFlags(arrObj); - chkFlags |= (arrObj->gtFlags & GTF_ALL_EFFECT); + arrObj = tree->gtArrElem.gtArrObj; + fgDebugCheckFlags(arrObj); + chkFlags |= (arrObj->gtFlags & GTF_ALL_EFFECT); - for (dim = 0; dim < tree->gtArrElem.gtArrRank; dim++) - { - fgDebugCheckFlags(tree->gtArrElem.gtArrInds[dim]); - chkFlags |= tree->gtArrElem.gtArrInds[dim]->gtFlags & GTF_ALL_EFFECT; - } - break; + for (dim = 0; dim < tree->gtArrElem.gtArrRank; dim++) + { + fgDebugCheckFlags(tree->gtArrElem.gtArrInds[dim]); + chkFlags |= tree->gtArrElem.gtArrInds[dim]->gtFlags & GTF_ALL_EFFECT; + } + break; - case GT_ARR_OFFSET: - fgDebugCheckFlags(tree->gtArrOffs.gtOffset); - chkFlags |= (tree->gtArrOffs.gtOffset->gtFlags & GTF_ALL_EFFECT); - fgDebugCheckFlags(tree->gtArrOffs.gtIndex); - chkFlags |= (tree->gtArrOffs.gtIndex->gtFlags & GTF_ALL_EFFECT); - fgDebugCheckFlags(tree->gtArrOffs.gtArrObj); - chkFlags |= (tree->gtArrOffs.gtArrObj->gtFlags & GTF_ALL_EFFECT); - break; + case GT_ARR_OFFSET: + fgDebugCheckFlags(tree->gtArrOffs.gtOffset); + chkFlags |= (tree->gtArrOffs.gtOffset->gtFlags & GTF_ALL_EFFECT); + fgDebugCheckFlags(tree->gtArrOffs.gtIndex); + chkFlags |= (tree->gtArrOffs.gtIndex->gtFlags & GTF_ALL_EFFECT); + fgDebugCheckFlags(tree->gtArrOffs.gtArrObj); + chkFlags |= (tree->gtArrOffs.gtArrObj->gtFlags & GTF_ALL_EFFECT); + break; - default: - break; + default: + break; + } } + + fgDebugCheckFlagsHelper(tree, treeFlags, chkFlags); } +//------------------------------------------------------------------------------ +// fgDebugCheckFlagsHelper : Check if all bits that are set in chkFlags are also set in treeFlags. +// +// +// Arguments: +// tree - Tree whose flags are being checked +// treeFlags - Actual flags on the tree +// chkFlags - Expected flags +// +// Note: +// Checking that all bits that are set in treeFlags are also set in chkFlags is currently disabled. + +void Compiler::fgDebugCheckFlagsHelper(GenTreePtr tree, unsigned treeFlags, unsigned chkFlags) +{ if (chkFlags & ~treeFlags) { // Print the tree so we can see it in the log. @@ -20461,12 +20514,12 @@ void Compiler::fgDebugCheckFlags(GenTreePtr tree) #if 0 // TODO-Cleanup: /* The tree has extra flags set. However, this will happen if we - replace a subtree with something, but don't clear the flags up - the tree. Can't flag this unless we start clearing flags above. + replace a subtree with something, but don't clear the flags up + the tree. Can't flag this unless we start clearing flags above. - Note: we need this working for GTF_CALL and CSEs, so I'm enabling - it for calls. - */ + Note: we need this working for GTF_CALL and CSEs, so I'm enabling + it for calls. + */ if (tree->OperGet() != GT_CALL && (treeFlags & GTF_CALL) && !(chkFlags & GTF_CALL)) { // Print the tree so we can see it in the log. @@ -20482,9 +20535,9 @@ void Compiler::fgDebugCheckFlags(GenTreePtr tree) GenTree::gtDispFlags(treeFlags & ~chkFlags, GTF_DEBUG_NONE); printf("\n"); gtDispTree(tree); - } -#endif // 0 } +#endif // 0 +} } // DEBUG routine to check correctness of the internal gtNext, gtPrev threading of a statement. diff --git a/src/jit/gentree.cpp b/src/jit/gentree.cpp index 7a76dfa..503e99d 100644 --- a/src/jit/gentree.cpp +++ b/src/jit/gentree.cpp @@ -3132,77 +3132,136 @@ bool GenTree::gtIsValid64RsltMul() #endif // DEBUG -/***************************************************************************** - * - * Figure out the evaluation order for a list of values. - */ + //------------------------------------------------------------------------------ + // gtSetListOrder : Figure out the evaluation order for a list of values. + // + // + // Arguments: + // list - List to figure out the evaluation order for + // isListCallArgs - True iff the list is a list of call arguments + // callArgsInRegs - True iff the list is a list of call arguments and they are passed in registers + // + // Return Value: + // True if the operation can be a root of a bitwise rotation tree; false otherwise. -unsigned Compiler::gtSetListOrder(GenTree* list, bool regs) +unsigned Compiler::gtSetListOrder(GenTree *list, bool isListCallArgs, bool callArgsInRegs) { - assert(list && list->IsList()); + assert((list != nullptr) && list->IsList()); + assert(!callArgsInRegs || isListCallArgs); - unsigned level = 0; - unsigned ftreg = 0; - unsigned costSz = 0; - unsigned costEx = 0; + ArrayStack listNodes(this); + do + { + listNodes.Push(list); + list = list->gtOp.gtOp2; + } while ((list != nullptr) && (list->IsList())); + + unsigned nxtlvl = (list == nullptr) ? 0 : gtSetEvalOrder(list); + while (listNodes.Height() > 0) + { #if FEATURE_STACK_FP_X87 - /* Save the current FP stack level since an argument list - * will implicitly pop the FP stack when pushing the argument */ - unsigned FPlvlSave = codeGen->genGetFPstkLevel(); + /* Save the current FP stack level since an argument list + * will implicitly pop the FP stack when pushing the argument */ + unsigned FPlvlSave = codeGen->genGetFPstkLevel(); #endif // FEATURE_STACK_FP_X87 - GenTreePtr next = list->gtOp.gtOp2; + list = listNodes.Pop(); + assert(list && list->IsList()); + GenTreePtr next = list->gtOp.gtOp2; - if (next) - { - unsigned nxtlvl = gtSetListOrder(next, regs); + unsigned level = 0; + unsigned ftreg = 0; - ftreg |= next->gtRsvdRegs; + // TODO: Do we have to compute costs differently for argument lists and + // all other lists? + // https://github.com/dotnet/coreclr/issues/7095 + unsigned costSz = (isListCallArgs || (next == nullptr)) ? 0 : 1; + unsigned costEx = (isListCallArgs || (next == nullptr)) ? 0 : 1; - if (level < nxtlvl) + if (next != nullptr) { - level = nxtlvl; + ftreg |= next->gtRsvdRegs; + if (isListCallArgs) + { + if (level < nxtlvl) + { + level = nxtlvl; + } + } + costEx += next->gtCostEx; + costSz += next->gtCostSz; } - costEx += next->gtCostEx; - costSz += next->gtCostSz; - } - GenTreePtr op1 = list->gtOp.gtOp1; - unsigned lvl = gtSetEvalOrder(op1); + GenTreePtr op1 = list->gtOp.gtOp1; + unsigned lvl = gtSetEvalOrder(op1); #if FEATURE_STACK_FP_X87 - /* restore the FP level */ - codeGen->genResetFPstkLevel(FPlvlSave); + // restore the FP level + codeGen->genResetFPstkLevel(FPlvlSave); #endif // FEATURE_STACK_FP_X87 - list->gtRsvdRegs = (regMaskSmall)(ftreg | op1->gtRsvdRegs); + list->gtRsvdRegs = (regMaskSmall)(ftreg | op1->gtRsvdRegs); - if (level < lvl) - { - level = lvl; - } + // Swap the level counts + if (list->gtFlags & GTF_REVERSE_OPS) + { + unsigned tmpl; - if (op1->gtCostEx != 0) - { - costEx += op1->gtCostEx; - costEx += regs ? 0 : IND_COST_EX; - } + tmpl = lvl; + lvl = nxtlvl; + nxtlvl = tmpl; + } - if (op1->gtCostSz != 0) - { - costSz += op1->gtCostSz; + // TODO: Do we have to compute levels differently for argument lists and + // all other lists? + // https://github.com/dotnet/coreclr/issues/7095 + if (isListCallArgs) + { + if (level < lvl) + { + level = lvl; + } + } + else + { + if (lvl < 1) + { + level = nxtlvl; + } + else if (lvl == nxtlvl) + { + level = lvl + 1; + } + else + { + level = lvl; + } + } + + if (op1->gtCostEx != 0) + { + costEx += op1->gtCostEx; + costEx += (callArgsInRegs || !isListCallArgs) ? 0 : IND_COST_EX; + } + + if (op1->gtCostSz != 0) + { + costSz += op1->gtCostSz; #ifdef _TARGET_XARCH_ - if (regs) // push is smaller than mov to reg + if (callArgsInRegs) // push is smaller than mov to reg #endif - { - costSz += 1; + { + costSz += 1; + } } - } - list->SetCosts(costEx, costSz); + list->SetCosts(costEx, costSz); - return level; + nxtlvl = level; + } + + return nxtlvl; } /***************************************************************************** @@ -4515,6 +4574,14 @@ unsigned Compiler::gtSetEvalOrder(GenTree* tree) goto DONE; + case GT_LIST: + + { + const bool isListCallArgs = false; + const bool callArgsInRegs = false; + return gtSetListOrder(tree, isListCallArgs, callArgsInRegs); + } + default: break; } @@ -4957,7 +5024,9 @@ unsigned Compiler::gtSetEvalOrder(GenTree* tree) #if FEATURE_STACK_FP_X87 FPlvlSave = codeGen->genGetFPstkLevel(); #endif // FEATURE_STACK_FP_X87 - lvl2 = gtSetListOrder(tree->gtCall.gtCallArgs, false); + const bool isListCallArgs = true; + const bool callArgsInRegs = false; + lvl2 = gtSetListOrder(tree->gtCall.gtCallArgs, isListCallArgs, callArgsInRegs); if (level < lvl2) { level = lvl2; @@ -4979,7 +5048,9 @@ unsigned Compiler::gtSetEvalOrder(GenTree* tree) #if FEATURE_STACK_FP_X87 FPlvlSave = codeGen->genGetFPstkLevel(); #endif // FEATURE_STACK_FP_X87 - lvl2 = gtSetListOrder(tree->gtCall.gtCallLateArgs, true); + const bool isListCallArgs = true; + const bool callArgsInRegs = true; + lvl2 = gtSetListOrder(tree->gtCall.gtCallLateArgs, isListCallArgs, callArgsInRegs); if (level < lvl2) { level = lvl2; -- 2.7.4