From d45da457c03957ba8ffe1337d406b2cac73be839 Mon Sep 17 00:00:00 2001 From: Mike Danes Date: Sun, 13 Nov 2016 12:24:17 +0200 Subject: [PATCH] Remove magic division optimization from morph This is no longer needed, lowering does this now. --- src/jit/assertionprop.cpp | 5 +- src/jit/compiler.h | 3 - src/jit/morph.cpp | 269 ---------------------------------------------- src/jit/valuenum.cpp | 2 +- 4 files changed, 5 insertions(+), 274 deletions(-) diff --git a/src/jit/assertionprop.cpp b/src/jit/assertionprop.cpp index 159aa29..16f2a69 100644 --- a/src/jit/assertionprop.cpp +++ b/src/jit/assertionprop.cpp @@ -4763,7 +4763,6 @@ Compiler::fgWalkResult Compiler::optVNConstantPropCurStmt(BasicBlock* block, Gen case GT_MOD: case GT_UDIV: case GT_UMOD: - case GT_MULHI: case GT_EQ: case GT_NE: case GT_LT: @@ -4782,6 +4781,10 @@ Compiler::fgWalkResult Compiler::optVNConstantPropCurStmt(BasicBlock* block, Gen case GT_INTRINSIC: break; + case GT_MULHI: + assert(false && "Unexpected GT_MULHI node encountered before lowering"); + break; + case GT_JTRUE: break; diff --git a/src/jit/compiler.h b/src/jit/compiler.h index b52fafa..2b6cb1e 100644 --- a/src/jit/compiler.h +++ b/src/jit/compiler.h @@ -4574,12 +4574,9 @@ private: GenTreePtr fgMorphForRegisterFP(GenTreePtr tree); GenTreePtr fgMorphSmpOp(GenTreePtr tree, MorphAddrContext* mac = nullptr); GenTreePtr fgMorphSmpOpPre(GenTreePtr tree); - GenTreePtr fgMorphDivByConst(GenTreeOp* tree); - GenTreePtr fgMorphModByConst(GenTreeOp* tree); GenTreePtr fgMorphModToSubMulDiv(GenTreeOp* tree); GenTreePtr fgMorphSmpOpOptional(GenTreeOp* tree); GenTreePtr fgMorphRecognizeBoxNullable(GenTree* compare); - bool fgShouldUseMagicNumberDivide(GenTreeOp* tree); GenTreePtr fgMorphToEmulatedFP(GenTreePtr tree); GenTreePtr fgMorphConst(GenTreePtr tree); diff --git a/src/jit/morph.cpp b/src/jit/morph.cpp index 2f3d964..39aefbb 100644 --- a/src/jit/morph.cpp +++ b/src/jit/morph.cpp @@ -10714,13 +10714,6 @@ GenTreePtr Compiler::fgMorphSmpOp(GenTreePtr tree, MorphAddrContext* mac) { op2 = gtFoldExprConst(op2); } - - if (fgShouldUseMagicNumberDivide(tree->AsOp())) - { - tree = fgMorphDivByConst(tree->AsOp()); - op1 = tree->gtOp.gtOp1; - op2 = tree->gtOp.gtOp2; - } #endif // !LEGACY_BACKEND break; @@ -10879,16 +10872,6 @@ GenTreePtr Compiler::fgMorphSmpOp(GenTreePtr tree, MorphAddrContext* mac) tree = fgMorphModToSubMulDiv(tree->AsOp()); op1 = tree->gtOp.gtOp1; op2 = tree->gtOp.gtOp2; - -#else // !_TARGET_ARM64_ - - if (oper != GT_UMOD && fgShouldUseMagicNumberDivide(tree->AsOp())) - { - tree = fgMorphModByConst(tree->AsOp()); - op1 = tree->gtOp.gtOp1; - op2 = tree->gtOp.gtOp2; - } - #endif //_TARGET_ARM64_ #endif // !LEGACY_BACKEND break; @@ -13849,169 +13832,6 @@ GenTree* Compiler::fgMorphSmpOpOptional(GenTreeOp* tree) return tree; } -// code to generate a magic number and shift amount for the magic number division -// optimization. This code is previously from UTC where it notes it was taken from -// _The_PowerPC_Compiler_Writer's_Guide_, pages 57-58. -// The paper it is based on is "Division by invariant integers using multiplication" -// by Torbjorn Granlund and Peter L. Montgomery in PLDI 94 - -template -T GetSignedMagicNumberForDivide(T denom, int* shift /*out*/) -{ - // static SMAG smag; - const int bits = sizeof(T) * 8; - const int bits_minus_1 = bits - 1; - - typedef typename jitstd::make_unsigned::type UT; - - const UT two_nminus1 = UT(1) << bits_minus_1; - - int p; - UT absDenom; - UT absNc; - UT delta; - UT q1; - UT r1; - UT r2; - UT q2; - UT t; - T result_magic; - int result_shift; - int iters = 0; - - absDenom = abs(denom); - t = two_nminus1 + ((unsigned int)denom >> 31); - absNc = t - 1 - (t % absDenom); // absolute value of nc - p = bits_minus_1; // initialize p - q1 = two_nminus1 / absNc; // initialize q1 = 2^p / abs(nc) - r1 = two_nminus1 - (q1 * absNc); // initialize r1 = rem(2^p, abs(nc)) - q2 = two_nminus1 / absDenom; // initialize q1 = 2^p / abs(denom) - r2 = two_nminus1 - (q2 * absDenom); // initialize r1 = rem(2^p, abs(denom)) - - do - { - iters++; - p++; - q1 *= 2; // update q1 = 2^p / abs(nc) - r1 *= 2; // update r1 = rem(2^p / abs(nc)) - - if (r1 >= absNc) - { // must be unsigned comparison - q1++; - r1 -= absNc; - } - - q2 *= 2; // update q2 = 2^p / abs(denom) - r2 *= 2; // update r2 = rem(2^p / abs(denom)) - - if (r2 >= absDenom) - { // must be unsigned comparison - q2++; - r2 -= absDenom; - } - - delta = absDenom - r2; - } while (q1 < delta || (q1 == delta && r1 == 0)); - - result_magic = q2 + 1; // resulting magic number - if (denom < 0) - { - result_magic = -result_magic; - } - *shift = p - bits; // resulting shift - - return result_magic; -} - -bool Compiler::fgShouldUseMagicNumberDivide(GenTreeOp* tree) -{ -#ifdef _TARGET_ARM64_ - // TODO-ARM64-NYI: We don't have a 'mulHi' implementation yet for ARM64 - return false; -#else - - // During the optOptimizeValnumCSEs phase we can call fgMorph and when we do, - // if this method returns true we will introduce a new LclVar and - // a couple of new GenTree nodes, including an assignment to the new LclVar. - // None of these new GenTree nodes will have valid ValueNumbers. - // That is an invalid state for a GenTree node during the optOptimizeValnumCSEs phase. - // - // Also during optAssertionProp when extracting side effects we can assert - // during gtBuildCommaList if we have one tree that has Value Numbers - // and another one that does not. - // - if (!fgGlobalMorph) - { - // We only perform the Magic Number Divide optimization during - // the initial global morph phase - return false; - } - - if (tree->gtFlags & GTF_OVERFLOW) - { - return false; - } - - if (tree->gtOp2->gtOper != GT_CNS_INT && tree->gtOp2->gtOper != GT_CNS_LNG) - { - return false; - } - - ssize_t cons = tree->gtOp2->gtIntConCommon.IconValue(); - - if (cons == 0 || cons == -1 || cons == 1) - { - return false; - } - - // codegen will expand these - if (cons == SSIZE_T_MIN || isPow2(abs(cons))) - { - return false; - } - - // someone else will fold this away, so don't make it complicated for them - if (tree->gtOp1->IsCnsIntOrI()) - { - return false; - } - - // There is no technical barrier to handling unsigned, however it is quite rare - // and more work to support and test - if (tree->gtFlags & GTF_UNSIGNED) - { - return false; - } - - return true; -#endif -} - -// transform x%c -> x-((x/c)*c) - -GenTree* Compiler::fgMorphModByConst(GenTreeOp* tree) -{ - assert(fgShouldUseMagicNumberDivide(tree)); - - var_types type = tree->gtType; - - GenTree* cns = tree->gtOp2; - - GenTree* numerator = fgMakeMultiUse(&tree->gtOp1); - - tree->SetOper(GT_DIV); - - GenTree* mul = gtNewOperNode(GT_MUL, type, tree, gtCloneExpr(cns)); - - GenTree* sub = gtNewOperNode(GT_SUB, type, numerator, mul); - -#ifdef DEBUG - sub->gtDebugFlags |= GTF_DEBUG_NODE_MORPHED; -#endif - - return sub; -} - // For ARM64 we don't have a remainder instruction, // The architecture manual suggests the following transformation to // generate code for such operator: @@ -14066,95 +13886,6 @@ GenTree* Compiler::fgMorphModToSubMulDiv(GenTreeOp* tree) return sub; } -// Turn a division by a constant into a multiplication by constant + some adjustments -// see comments on GetSignedMagicNumberForDivide for source of this algorithm. -// returns: the transformed tree - -GenTree* Compiler::fgMorphDivByConst(GenTreeOp* tree) -{ - assert(fgShouldUseMagicNumberDivide(tree)); - - JITDUMP("doing magic number divide optimization\n"); - - int64_t denominator = tree->gtOp2->gtIntConCommon.IconValue(); - int64_t magic; - int shift; - var_types type = tree->gtType; - - if (tree->gtType == TYP_INT) - { - magic = GetSignedMagicNumberForDivide((int32_t)denominator, &shift); - } - else - { - magic = GetSignedMagicNumberForDivide((int64_t)denominator, &shift); - } - - GenTree* numerator = nullptr; - - // If signs of the denominator and magic number don't match, - // we will need to use the numerator again. - if (signum(denominator) != signum(magic)) - { - numerator = fgMakeMultiUse(&tree->gtOp1); - tree->gtFlags |= GTF_ASG; - } - - if (type == TYP_LONG) - { - tree->gtOp2->gtIntConCommon.SetLngValue(magic); - } - else - { - tree->gtOp2->gtIntConCommon.SetIconValue((ssize_t)magic); - } - - tree->SetOper(GT_MULHI); - - GenTree* t = tree; - GenTree* mulresult = tree; - - JITDUMP("Multiply Result:\n"); - DISPTREE(mulresult); - - GenTree* adjusted = mulresult; - - if (denominator > 0 && magic < 0) - { - // add the numerator back in - adjusted = gtNewOperNode(GT_ADD, type, mulresult, numerator); - } - else if (denominator < 0 && magic > 0) - { - // subtract the numerator off - adjusted = gtNewOperNode(GT_SUB, type, mulresult, numerator); - } - else - { - adjusted = mulresult; - } - - GenTree* result1 = adjusted; - if (shift != 0) - { - result1 = gtNewOperNode(GT_RSH, type, adjusted, gtNewIconNode(shift, TYP_INT)); - } - - GenTree* secondClone = fgMakeMultiUse(&result1); - - GenTree* result2 = gtNewOperNode(GT_RSZ, type, secondClone, gtNewIconNode(genTypeSize(type) * 8 - 1, type)); - - GenTree* result = gtNewOperNode(GT_ADD, type, result1, result2); - JITDUMP("Final Magic Number divide:\n"); - DISPTREE(result); - -#ifdef DEBUG - result->gtDebugFlags |= GTF_DEBUG_NODE_MORPHED; -#endif - - return result; -} - //------------------------------------------------------------------------------ // fgOperIsBitwiseRotationRoot : Check if the operation can be a root of a bitwise rotation tree. // diff --git a/src/jit/valuenum.cpp b/src/jit/valuenum.cpp index 51937da..4a2d925 100644 --- a/src/jit/valuenum.cpp +++ b/src/jit/valuenum.cpp @@ -2081,7 +2081,7 @@ bool ValueNumStore::CanEvalForConstantArgs(VNFunc vnf) case GT_ARR_LENGTH: return false; case GT_MULHI: - // should be rare, not worth the complexity and risk of getting it wrong + assert(false && "Unexpected GT_MULHI node encountered before lowering"); return false; default: return true; -- 2.7.4