src/jit/optcse.cpp

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 /*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   6 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   7 XX                                                                           XX
   8 XX                              OptCSE                                       XX
   9 XX                                                                           XX
  10 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  11 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  12 */
  13
  14 #include "jitpch.h"
  15 #ifdef _MSC_VER
  16 #pragma hdrstop
  17 #endif
  18
  19 /*****************************************************************************/
  20 #if FEATURE_ANYCSE
  21 /*****************************************************************************/
  22
  23 /* static */
  24 const size_t Compiler::s_optCSEhashSize = EXPSET_SZ * 2;
  25
  26 /*****************************************************************************
  27  *
  28  *  We've found all the candidates, build the index for easy access.
  29  */
  30
  31 void Compiler::optCSEstop()
  32 {
  33     if (optCSECandidateCount == 0)
  34     {
  35         return;
  36     }
  37
  38     CSEdsc*  dsc;
  39     CSEdsc** ptr;
  40     unsigned cnt;
  41
  42     optCSEtab = new (this, CMK_CSE) CSEdsc*[optCSECandidateCount]();
  43
  44     for (cnt = s_optCSEhashSize, ptr = optCSEhash; cnt; cnt--, ptr++)
  45     {
  46         for (dsc = *ptr; dsc; dsc = dsc->csdNextInBucket)
  47         {
  48             if (dsc->csdIndex)
  49             {
  50                 noway_assert((unsigned)dsc->csdIndex <= optCSECandidateCount);
  51                 if (optCSEtab[dsc->csdIndex - 1] == nullptr)
  52                 {
  53                     optCSEtab[dsc->csdIndex - 1] = dsc;
  54                 }
  55             }
  56         }
  57     }
  58
  59 #ifdef DEBUG
  60     for (cnt = 0; cnt < optCSECandidateCount; cnt++)
  61     {
  62         noway_assert(optCSEtab[cnt] != nullptr);
  63     }
  64 #endif
  65 }
  66
  67 /*****************************************************************************
  68  *
  69  *  Return the descriptor for the CSE with the given index.
  70  */
  71
  72 inline Compiler::CSEdsc* Compiler::optCSEfindDsc(unsigned index)
  73 {
  74     noway_assert(index);
  75     noway_assert(index <= optCSECandidateCount);
  76     noway_assert(optCSEtab[index - 1]);
  77
  78     return optCSEtab[index - 1];
  79 }
  80
  81 /*****************************************************************************
  82  *
  83  *  For a previously marked CSE, decrement the use counts and unmark it
  84  */
  85
  86 void Compiler::optUnmarkCSE(GenTreePtr tree)
  87 {
  88     if (!IS_CSE_INDEX(tree->gtCSEnum))
  89     {
  90         // This tree is not a CSE candidate, so there is nothing
  91         // to do.
  92         return;
  93     }
  94
  95     unsigned CSEnum = GET_CSE_INDEX(tree->gtCSEnum);
  96     CSEdsc*  desc;
  97
  98     // make sure it's been initialized
  99     noway_assert(optCSEweight <= BB_MAX_WEIGHT);
 100
 101     /* Is this a CSE use? */
 102     if (IS_CSE_USE(tree->gtCSEnum))
 103     {
 104         desc = optCSEfindDsc(CSEnum);
 105
 106 #ifdef DEBUG
 107         if (verbose)
 108         {
 109             printf("Unmark CSE use #%02d at ", CSEnum);
 110             printTreeID(tree);
 111             printf(": %3d -> %3d\n", desc->csdUseCount, desc->csdUseCount - 1);
 112         }
 113 #endif
 114
 115         /* Reduce the nested CSE's 'use' count */
 116
 117         noway_assert(desc->csdUseCount > 0);
 118
 119         if (desc->csdUseCount > 0)
 120         {
 121             desc->csdUseCount -= 1;
 122
 123             if (desc->csdUseWtCnt < optCSEweight)
 124             {
 125                 desc->csdUseWtCnt = 0;
 126             }
 127             else
 128             {
 129                 desc->csdUseWtCnt -= optCSEweight;
 130             }
 131         }
 132     }
 133     else
 134     {
 135         desc = optCSEfindDsc(CSEnum);
 136
 137 #ifdef DEBUG
 138         if (verbose)
 139         {
 140             printf("Unmark CSE def #%02d at ", CSEnum);
 141             printTreeID(tree);
 142             printf(": %3d -> %3d\n", desc->csdDefCount, desc->csdDefCount - 1);
 143         }
 144 #endif
 145
 146         /* Reduce the nested CSE's 'def' count */
 147
 148         noway_assert(desc->csdDefCount > 0);
 149
 150         if (desc->csdDefCount > 0)
 151         {
 152             desc->csdDefCount -= 1;
 153
 154             if (desc->csdDefWtCnt < optCSEweight)
 155             {
 156                 desc->csdDefWtCnt = 0;
 157             }
 158             else
 159             {
 160                 desc->csdDefWtCnt -= optCSEweight;
 161             }
 162         }
 163     }
 164
 165     tree->gtCSEnum = NO_CSE;
 166 }
 167
 168 Compiler::fgWalkResult Compiler::optHasNonCSEChild(GenTreePtr* pTree, fgWalkData* data)
 169 {
 170     if (*pTree == data->pCallbackData)
 171     {
 172         return WALK_CONTINUE;
 173     }
 174
 175     if ((*pTree)->gtFlags & GTF_DONT_CSE)
 176     {
 177
 178         // Fix 392756 WP7 Crossgen
 179         // Don't propagate the GTF_DONT_CSE flag up from a GT_CNS_INT
 180         //
 181         // During codegen optGetArrayRefScaleAndIndex() makes the assumption that op2 of a GT_MUL node
 182         // is a constant and is not capable of handling CSE'ing the elemSize constant into a lclvar.
 183         // Hence to prevent the constant from becoming a CSE we have marked it as NO_CSE, but this
 184         // should not prevent tree's above the constant from becoming CSE's.
 185         //
 186         if ((*pTree)->gtOper == GT_CNS_INT)
 187         {
 188             return WALK_SKIP_SUBTREES;
 189         }
 190
 191         return WALK_ABORT;
 192     }
 193
 194     return WALK_SKIP_SUBTREES;
 195 }
 196
 197 Compiler::fgWalkResult Compiler::optPropagateNonCSE(GenTreePtr* pTree, fgWalkData* data)
 198 {
 199     GenTree*  tree = *pTree;
 200     Compiler* comp = data->compiler;
 201
 202     /* Calls get DONT_CSE implicitly */
 203     if (tree->OperGet() == GT_CALL)
 204     {
 205         if (!IsSharedStaticHelper(tree))
 206         {
 207             tree->gtFlags |= GTF_DONT_CSE;
 208         }
 209     }
 210
 211     if ((tree->gtFlags & GTF_DONT_CSE) == 0)
 212     {
 213         /* Propagate the DONT_CSE flag from child to parent */
 214         if (comp->fgWalkTreePre(&tree, optHasNonCSEChild, tree) == WALK_ABORT)
 215         {
 216             tree->gtFlags |= GTF_DONT_CSE;
 217         }
 218     }
 219
 220     return WALK_CONTINUE;
 221 }
 222
 223 /*****************************************************************************
 224  *
 225  *  Helper passed to Compiler::fgWalkAllTreesPre() to unmark nested CSE's.
 226  */
 227
 228 /* static */
 229 Compiler::fgWalkResult Compiler::optUnmarkCSEs(GenTreePtr* pTree, fgWalkData* data)
 230 {
 231     GenTreePtr tree     = *pTree;
 232     Compiler*  comp     = data->compiler;
 233     GenTreePtr keepList = (GenTreePtr)(data->pCallbackData);
 234
 235     // We may have a non-NULL side effect list that is being kept
 236     //
 237     if (keepList)
 238     {
 239         GenTreePtr keptTree = keepList;
 240         while (keptTree->OperGet() == GT_COMMA)
 241         {
 242             assert(keptTree->OperKind() & GTK_SMPOP);
 243             GenTreePtr op1 = keptTree->gtOp.gtOp1;
 244             GenTreePtr op2 = keptTree->gtGetOp2();
 245
 246             // For the GT_COMMA case the op1 is part of the orginal CSE tree
 247             // that is being kept because it contains some side-effect
 248             //
 249             if (tree == op1)
 250             {
 251                 // This tree and all of its sub trees are being kept
 252                 return WALK_SKIP_SUBTREES;
 253             }
 254
 255             // For the GT_COMMA case the op2 are the remaining side-effects of the orginal CSE tree
 256             // which can again be another GT_COMMA or the final side-effect part
 257             //
 258             keptTree = op2;
 259         }
 260         if (tree == keptTree)
 261         {
 262             // This tree and all of its sub trees are being kept
 263             return WALK_SKIP_SUBTREES;
 264         }
 265     }
 266
 267     // This node is being removed from the graph of GenTreePtr
 268     // Call optUnmarkCSE and  decrement the LclVar ref counts.
 269     comp->optUnmarkCSE(tree);
 270     assert(!IS_CSE_INDEX(tree->gtCSEnum));
 271
 272     /* Look for any local variable references */
 273
 274     if (tree->gtOper == GT_LCL_VAR)
 275     {
 276         unsigned   lclNum;
 277         LclVarDsc* varDsc;
 278
 279         /* This variable ref is going away, decrease its ref counts */
 280
 281         lclNum = tree->gtLclVarCommon.gtLclNum;
 282         assert(lclNum < comp->lvaCount);
 283         varDsc = comp->lvaTable + lclNum;
 284
 285         // make sure it's been initialized
 286         assert(comp->optCSEweight <= BB_MAX_WEIGHT);
 287
 288         /* Decrement its lvRefCnt and lvRefCntWtd */
 289
 290         varDsc->decRefCnts(comp->optCSEweight, comp);
 291     }
 292
 293     return WALK_CONTINUE;
 294 }
 295
 296 Compiler::fgWalkResult Compiler::optCSE_MaskHelper(GenTreePtr* pTree, fgWalkData* walkData)
 297 {
 298     GenTree*         tree      = *pTree;
 299     Compiler*        comp      = walkData->compiler;
 300     optCSE_MaskData* pUserData = (optCSE_MaskData*)(walkData->pCallbackData);
 301
 302     if (IS_CSE_INDEX(tree->gtCSEnum))
 303     {
 304         unsigned cseIndex = GET_CSE_INDEX(tree->gtCSEnum);
 305         unsigned cseBit   = genCSEnum2bit(cseIndex);
 306         if (IS_CSE_DEF(tree->gtCSEnum))
 307         {
 308             BitVecOps::AddElemD(comp->cseTraits, pUserData->CSE_defMask, cseBit);
 309         }
 310         else
 311         {
 312             BitVecOps::AddElemD(comp->cseTraits, pUserData->CSE_useMask, cseBit);
 313         }
 314     }
 315
 316     return WALK_CONTINUE;
 317 }
 318
 319 // This functions walks all the node for an given tree
 320 // and return the mask of CSE defs and uses for the tree
 321 //
 322 void Compiler::optCSE_GetMaskData(GenTreePtr tree, optCSE_MaskData* pMaskData)
 323 {
 324     pMaskData->CSE_defMask = BitVecOps::MakeCopy(cseTraits, cseEmpty);
 325     pMaskData->CSE_useMask = BitVecOps::MakeCopy(cseTraits, cseEmpty);
 326     fgWalkTreePre(&tree, optCSE_MaskHelper, (void*)pMaskData);
 327 }
 328
 329 //------------------------------------------------------------------------
 330 // optCSE_canSwap: Determine if the execution order of two nodes can be swapped.
 331 //
 332 // Arguments:
 333 //    op1 - The first node
 334 //    op2 - The second node
 335 //
 336 // Return Value:
 337 //    Return true iff it safe to swap the execution order of 'op1' and 'op2',
 338 //    considering only the locations of the CSE defs and uses.
 339 //
 340 // Assumptions:
 341 //    'op1' currently occurse before 'op2' in the execution order.
 342 //
 343 bool Compiler::optCSE_canSwap(GenTree* op1, GenTree* op2)
 344 {
 345     // op1 and op2 must be non-null.
 346     assert(op1 != nullptr);
 347     assert(op2 != nullptr);
 348
 349     bool canSwap = true; // the default result unless proven otherwise.
 350
 351     optCSE_MaskData op1MaskData;
 352     optCSE_MaskData op2MaskData;
 353
 354     optCSE_GetMaskData(op1, &op1MaskData);
 355     optCSE_GetMaskData(op2, &op2MaskData);
 356
 357     // We cannot swap if op1 contains a CSE def that is used by op2
 358     if (!BitVecOps::IsEmptyIntersection(cseTraits, op1MaskData.CSE_defMask, op2MaskData.CSE_useMask))
 359     {
 360         canSwap = false;
 361     }
 362     else
 363     {
 364         // We also cannot swap if op2 contains a CSE def that is used by op1.
 365         if (!BitVecOps::IsEmptyIntersection(cseTraits, op2MaskData.CSE_defMask, op1MaskData.CSE_useMask))
 366         {
 367             canSwap = false;
 368         }
 369     }
 370
 371     return canSwap;
 372 }
 373
 374 //------------------------------------------------------------------------
 375 // optCSE_canSwap: Determine if the execution order of a node's operands can be swapped.
 376 //
 377 // Arguments:
 378 //    tree - The node of interest
 379 //
 380 // Return Value:
 381 //    Return true iff it safe to swap the execution order of the operands of 'tree',
 382 //    considering only the locations of the CSE defs and uses.
 383 //
 384 bool Compiler::optCSE_canSwap(GenTreePtr tree)
 385 {
 386     // We must have a binary treenode with non-null op1 and op2
 387     assert((tree->OperKind() & GTK_SMPOP) != 0);
 388
 389     GenTreePtr op1 = tree->gtOp.gtOp1;
 390     GenTreePtr op2 = tree->gtGetOp2();
 391
 392     return optCSE_canSwap(op1, op2);
 393 }
 394
 395 /*****************************************************************************
 396  *
 397  *  Compare function passed to qsort() by CSE_Heuristic::SortCandidates
 398  *  when (CodeOptKind() != Compiler::SMALL_CODE)
 399  */
 400
 401 /* static */
 402 int __cdecl Compiler::optCSEcostCmpEx(const void* op1, const void* op2)
 403 {
 404     CSEdsc* dsc1 = *(CSEdsc**)op1;
 405     CSEdsc* dsc2 = *(CSEdsc**)op2;
 406
 407     GenTreePtr exp1 = dsc1->csdTree;
 408     GenTreePtr exp2 = dsc2->csdTree;
 409
 410     int diff;
 411
 412     diff = (int)(exp2->gtCostEx - exp1->gtCostEx);
 413
 414     if (diff != 0)
 415     {
 416         return diff;
 417     }
 418
 419     // Sort the higher Use Counts toward the top
 420     diff = (int)(dsc2->csdUseWtCnt - dsc1->csdUseWtCnt);
 421
 422     if (diff != 0)
 423     {
 424         return diff;
 425     }
 426
 427     // With the same use count, Sort the lower Def Counts toward the top
 428     diff = (int)(dsc1->csdDefWtCnt - dsc2->csdDefWtCnt);
 429
 430     if (diff != 0)
 431     {
 432         return diff;
 433     }
 434
 435     // In order to ensure that we have a stable sort, we break ties using the csdIndex
 436     return (int)(dsc1->csdIndex - dsc2->csdIndex);
 437 }
 438
 439 /*****************************************************************************
 440  *
 441  *  Compare function passed to qsort() by CSE_Heuristic::SortCandidates
 442  *  when (CodeOptKind() == Compiler::SMALL_CODE)
 443  */
 444
 445 /* static */
 446 int __cdecl Compiler::optCSEcostCmpSz(const void* op1, const void* op2)
 447 {
 448     CSEdsc* dsc1 = *(CSEdsc**)op1;
 449     CSEdsc* dsc2 = *(CSEdsc**)op2;
 450
 451     GenTreePtr exp1 = dsc1->csdTree;
 452     GenTreePtr exp2 = dsc2->csdTree;
 453
 454     int diff;
 455
 456     diff = (int)(exp2->gtCostSz - exp1->gtCostSz);
 457
 458     if (diff != 0)
 459     {
 460         return diff;
 461     }
 462
 463     // Sort the higher Use Counts toward the top
 464     diff = (int)(dsc2->csdUseCount - dsc1->csdUseCount);
 465
 466     if (diff != 0)
 467     {
 468         return diff;
 469     }
 470
 471     // With the same use count, Sort the lower Def Counts toward the top
 472     diff = (int)(dsc1->csdDefCount - dsc2->csdDefCount);
 473
 474     if (diff != 0)
 475     {
 476         return diff;
 477     }
 478
 479     // In order to ensure that we have a stable sort, we break ties using the csdIndex
 480     return (int)(dsc1->csdIndex - dsc2->csdIndex);
 481 }
 482
 483 /*****************************************************************************/
 484 #if FEATURE_VALNUM_CSE
 485 /*****************************************************************************/
 486
 487 /*****************************************************************************
 488  *
 489  *  Initialize the Value Number CSE tracking logic.
 490  */
 491
 492 void Compiler::optValnumCSE_Init()
 493 {
 494 #ifdef DEBUG
 495     optCSEtab = nullptr;
 496 #endif
 497
 498     // Init traits and full/empty bitvectors.  This will be used to track the
 499     // individual cse indexes.
 500     cseTraits = new (getAllocator()) BitVecTraits(EXPSET_SZ, this);
 501     cseFull   = BitVecOps::UninitVal();
 502     cseEmpty  = BitVecOps::UninitVal();
 503     BitVecOps::AssignNoCopy(cseTraits, cseFull, BitVecOps::MakeFull(cseTraits));
 504     BitVecOps::AssignNoCopy(cseTraits, cseEmpty, BitVecOps::MakeEmpty(cseTraits));
 505
 506     /* Allocate and clear the hash bucket table */
 507
 508     optCSEhash = new (this, CMK_CSE) CSEdsc*[s_optCSEhashSize]();
 509
 510     optCSECandidateCount = 0;
 511     optDoCSE             = false; // Stays false until we find duplicate CSE tree
 512
 513     // cseArrLenMap is unused in most functions, allocated only when used
 514     cseArrLenMap = nullptr;
 515 }
 516
 517 /*****************************************************************************
 518  *
 519  *  Assign an index to the given expression (adding it to the lookup table,
 520  *  if necessary). Returns the index or 0 if the expression can not be a CSE.
 521  */
 522
 523 unsigned Compiler::optValnumCSE_Index(GenTreePtr tree, GenTreePtr stmt)
 524 {
 525     unsigned key;
 526     unsigned hash;
 527     unsigned hval;
 528     CSEdsc*  hashDsc;
 529
 530     ValueNum vnlib = tree->GetVN(VNK_Liberal);
 531
 532     /* Compute the hash value for the expression */
 533
 534     key = (unsigned)vnlib;
 535
 536     hash = key;
 537     hash *= (unsigned)(s_optCSEhashSize + 1);
 538     hash >>= 7;
 539
 540     hval = hash % s_optCSEhashSize;
 541
 542     /* Look for a matching index in the hash table */
 543
 544     bool newCSE = false;
 545
 546     for (hashDsc = optCSEhash[hval]; hashDsc; hashDsc = hashDsc->csdNextInBucket)
 547     {
 548         if (hashDsc->csdHashValue == key)
 549         {
 550             treeStmtLstPtr newElem;
 551
 552             /* Have we started the list of matching nodes? */
 553
 554             if (hashDsc->csdTreeList == nullptr)
 555             {
 556                 // Create the new element based upon the matching hashDsc element.
 557
 558                 newElem = new (this, CMK_TreeStatementList) treeStmtLst;
 559
 560                 newElem->tslTree  = hashDsc->csdTree;
 561                 newElem->tslStmt  = hashDsc->csdStmt;
 562                 newElem->tslBlock = hashDsc->csdBlock;
 563                 newElem->tslNext  = nullptr;
 564
 565                 /* Start the list with the first CSE candidate recorded */
 566
 567                 hashDsc->csdTreeList = newElem;
 568                 hashDsc->csdTreeLast = newElem;
 569             }
 570
 571             noway_assert(hashDsc->csdTreeList);
 572
 573             /* Append this expression to the end of the list */
 574
 575             newElem = new (this, CMK_TreeStatementList) treeStmtLst;
 576
 577             newElem->tslTree  = tree;
 578             newElem->tslStmt  = stmt;
 579             newElem->tslBlock = compCurBB;
 580             newElem->tslNext  = nullptr;
 581
 582             hashDsc->csdTreeLast->tslNext = newElem;
 583             hashDsc->csdTreeLast          = newElem;
 584
 585             optDoCSE = true; // Found a duplicate CSE tree
 586
 587             /* Have we assigned a CSE index? */
 588             if (hashDsc->csdIndex == 0)
 589             {
 590                 newCSE = true;
 591                 break;
 592             }
 593 #if 0
 594             // Use this to see if this Value Number base CSE is also a lexical CSE
 595             bool treeMatch = GenTree::Compare(hashDsc->csdTree, tree, true);
 596 #endif
 597
 598             assert(FitsIn<signed char>(hashDsc->csdIndex));
 599             tree->gtCSEnum = ((signed char)hashDsc->csdIndex);
 600             return hashDsc->csdIndex;
 601         }
 602     }
 603
 604     if (!newCSE)
 605     {
 606         /* Not found, create a new entry (unless we have too many already) */
 607
 608         if (optCSECandidateCount < MAX_CSE_CNT)
 609         {
 610             hashDsc = new (this, CMK_CSE) CSEdsc;
 611
 612             hashDsc->csdHashValue      = key;
 613             hashDsc->csdIndex          = 0;
 614             hashDsc->csdLiveAcrossCall = 0;
 615             hashDsc->csdDefCount       = 0;
 616             hashDsc->csdUseCount       = 0;
 617             hashDsc->csdDefWtCnt       = 0;
 618             hashDsc->csdUseWtCnt       = 0;
 619
 620             hashDsc->csdTree     = tree;
 621             hashDsc->csdStmt     = stmt;
 622             hashDsc->csdBlock    = compCurBB;
 623             hashDsc->csdTreeList = nullptr;
 624
 625             /* Append the entry to the hash bucket */
 626
 627             hashDsc->csdNextInBucket = optCSEhash[hval];
 628             optCSEhash[hval]         = hashDsc;
 629         }
 630         return 0;
 631     }
 632     else // newCSE is true
 633     {
 634         /* We get here only after finding a matching CSE */
 635
 636         /* Create a new CSE (unless we have the maximum already) */
 637
 638         if (optCSECandidateCount == MAX_CSE_CNT)
 639         {
 640             return 0;
 641         }
 642
 643         C_ASSERT((signed char)MAX_CSE_CNT == MAX_CSE_CNT);
 644
 645         unsigned CSEindex = ++optCSECandidateCount;
 646         // EXPSET_TP  CSEmask  = genCSEnum2bit(CSEindex);
 647
 648         /* Record the new CSE index in the hashDsc */
 649         hashDsc->csdIndex = CSEindex;
 650
 651         /* Update the gtCSEnum field in the original tree */
 652         noway_assert(hashDsc->csdTreeList->tslTree->gtCSEnum == 0);
 653         assert(FitsIn<signed char>(CSEindex));
 654
 655         hashDsc->csdTreeList->tslTree->gtCSEnum = ((signed char)CSEindex);
 656         noway_assert(((unsigned)hashDsc->csdTreeList->tslTree->gtCSEnum) == CSEindex);
 657
 658         tree->gtCSEnum = ((signed char)CSEindex);
 659
 660 #ifdef DEBUG
 661         if (verbose)
 662         {
 663             EXPSET_TP tempMask = BitVecOps::MakeSingleton(cseTraits, genCSEnum2bit(CSEindex));
 664             printf("\nCSE candidate #%02u, vn=", CSEindex);
 665             vnPrint(vnlib, 0);
 666             printf(" cseMask=%s in BB%02u, [cost=%2u, size=%2u]: \n", genES2str(cseTraits, tempMask), compCurBB->bbNum,
 667                    tree->gtCostEx, tree->gtCostSz);
 668             gtDispTree(tree);
 669         }
 670 #endif // DEBUG
 671
 672         return CSEindex;
 673     }
 674 }
 675
 676 /*****************************************************************************
 677  *
 678  *  Locate CSE candidates and assign indices to them
 679  *  return 0 if no CSE candidates were found
 680  *  Also initialize bbCseIn, bbCseout and bbCseGen sets for all blocks
 681  */
 682
 683 unsigned Compiler::optValnumCSE_Locate()
 684 {
 685     // Locate CSE candidates and assign them indices
 686
 687     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
 688     {
 689         GenTreePtr stmt;
 690         GenTreePtr tree;
 691
 692         /* Make the block publicly available */
 693
 694         compCurBB = block;
 695
 696         /* Ensure that the BBF_VISITED and BBF_MARKED flag are clear */
 697         /* Everyone who uses these flags are required to clear afterwards */
 698         noway_assert((block->bbFlags & (BBF_VISITED | BBF_MARKED)) == 0);
 699
 700         /* Walk the statement trees in this basic block */
 701         for (stmt = block->FirstNonPhiDef(); stmt; stmt = stmt->gtNext)
 702         {
 703             noway_assert(stmt->gtOper == GT_STMT);
 704
 705             /* We walk the tree in the forwards direction (bottom up) */
 706             bool stmtHasArrLenCandidate = false;
 707             for (tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
 708             {
 709                 if (tree->OperIsCompare() && stmtHasArrLenCandidate)
 710                 {
 711                     // Check if this compare is a function of (one of) the arrary
 712                     // length candidate(s); we may want to update its value number
 713                     // if the array length gets CSEd
 714                     updateCseArrLenMap(tree);
 715                 }
 716
 717                 if (!optIsCSEcandidate(tree))
 718                 {
 719                     continue;
 720                 }
 721
 722                 ValueNum vnlib = tree->GetVN(VNK_Liberal);
 723
 724                 if (ValueNumStore::isReservedVN(vnlib))
 725                 {
 726                     continue;
 727                 }
 728
 729                 // Don't CSE constant values, instead let the Value Number
 730                 // based Assertion Prop phase handle them.
 731                 //
 732                 if (vnStore->IsVNConstant(vnlib))
 733                 {
 734                     continue;
 735                 }
 736
 737                 /* Assign an index to this expression */
 738
 739                 unsigned CSEindex = optValnumCSE_Index(tree, stmt);
 740
 741                 if (CSEindex != 0)
 742                 {
 743                     noway_assert(((unsigned)tree->gtCSEnum) == CSEindex);
 744                 }
 745
 746                 if (IS_CSE_INDEX(CSEindex) && (tree->OperGet() == GT_ARR_LENGTH))
 747                 {
 748                     stmtHasArrLenCandidate = true;
 749                 }
 750             }
 751         }
 752     }
 753
 754     /* We're done if there were no interesting expressions */
 755
 756     if (!optDoCSE)
 757     {
 758         return 0;
 759     }
 760
 761     /* We're finished building the expression lookup table */
 762
 763     optCSEstop();
 764
 765     return 1;
 766 }
 767
 768 //------------------------------------------------------------------------
 769 // updateCseArrLenMap: Check if this compare is a tractable function of
 770 //                     an array length that is a CSE candidate, and insert
 771 //                     an entry in the cseArrLenMap if so.  This facilitates
 772 //                     subsequently updating the compare's value number if
 773 //                     the array length gets CSEd.
 774 //
 775 // Arguments:
 776 //    compare - The compare node to check
 777
 778 void Compiler::updateCseArrLenMap(GenTreePtr compare)
 779 {
 780     assert(compare->OperIsCompare());
 781
 782     ValueNum  compareVN = compare->gtVNPair.GetConservative();
 783     VNFuncApp cmpVNFuncApp;
 784
 785     if (!vnStore->GetVNFunc(compareVN, &cmpVNFuncApp) ||
 786         (cmpVNFuncApp.m_func != GetVNFuncForOper(compare->OperGet(), (compare->gtFlags & GTF_UNSIGNED) != 0)))
 787     {
 788         // Value numbering inferred this compare as something other
 789         // than its own operator; leave its value number alone.
 790         return;
 791     }
 792
 793     // Now look for an array length feeding the compare
 794     ValueNumStore::ArrLenArithBoundInfo info;
 795     GenTreePtr                          arrLenParent = nullptr;
 796
 797     if (vnStore->IsVNArrLenBound(compareVN))
 798     {
 799         // Simple compare of an array legnth against something else.
 800
 801         vnStore->GetArrLenBoundInfo(compareVN, &info);
 802         arrLenParent = compare;
 803     }
 804     else if (vnStore->IsVNArrLenArithBound(compareVN))
 805     {
 806         // Compare of an array length +/- some offset to something else.
 807
 808         GenTreePtr op1 = compare->gtGetOp1();
 809         GenTreePtr op2 = compare->gtGetOp2();
 810
 811         vnStore->GetArrLenArithBoundInfo(compareVN, &info);
 812         if (GetVNFuncForOper(op1->OperGet(), (op1->gtFlags & GTF_UNSIGNED) != 0) == info.arrOper)
 813         {
 814             // The arithmetic node is the array length's parent.
 815             arrLenParent = op1;
 816         }
 817         else if (GetVNFuncForOper(op2->OperGet(), (op2->gtFlags & GTF_UNSIGNED) != 0) == info.arrOper)
 818         {
 819             // The arithmetic node is the array length's parent.
 820             arrLenParent = op2;
 821         }
 822     }
 823
 824     if (arrLenParent != nullptr)
 825     {
 826         GenTreePtr arrLen = nullptr;
 827
 828         // Find which child of arrLenParent is the array length.  Abort if its
 829         // conservative value number doesn't match the one from the compare VN.
 830
 831         GenTreePtr child1 = arrLenParent->gtGetOp1();
 832         if ((child1->OperGet() == GT_ARR_LENGTH) && IS_CSE_INDEX(child1->gtCSEnum) &&
 833             (info.vnArray == child1->AsArrLen()->ArrRef()->gtVNPair.GetConservative()))
 834         {
 835             arrLen = child1;
 836         }
 837         else
 838         {
 839             GenTreePtr child2 = arrLenParent->gtGetOp2();
 840             if ((child2->OperGet() == GT_ARR_LENGTH) && IS_CSE_INDEX(child2->gtCSEnum) &&
 841                 (info.vnArray == child2->AsArrLen()->ArrRef()->gtVNPair.GetConservative()))
 842             {
 843                 arrLen = child2;
 844             }
 845         }
 846
 847         if (arrLen != nullptr)
 848         {
 849             // Found an arrayLen feeding a compare that is a tracatable function of it;
 850             // record this in the map so we can update the compare VN if the array length
 851             // node gets CSEd.
 852
 853             if (cseArrLenMap == nullptr)
 854             {
 855                 // Allocate map on first use.
 856                 cseArrLenMap = new (getAllocator()) NodeToNodeMap(getAllocator());
 857             }
 858
 859             cseArrLenMap->Set(arrLen, compare);
 860         }
 861     }
 862 }
 863
 864 /*****************************************************************************
 865  *
 866  *  Compute each blocks bbCseGen
 867  *  This is the bitset that represents the CSEs that are generated within the block
 868  */
 869 void Compiler::optValnumCSE_InitDataFlow()
 870 {
 871     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
 872     {
 873         GenTreePtr stmt;
 874         GenTreePtr tree;
 875
 876         /* Initialize the blocks's bbCseIn set */
 877
 878         bool init_to_zero = false;
 879
 880         if (block == fgFirstBB)
 881         {
 882             /* Clear bbCseIn for the entry block */
 883             init_to_zero = true;
 884         }
 885 #if !CSE_INTO_HANDLERS
 886         else
 887         {
 888             if (bbIsHandlerBeg(block))
 889             {
 890                 /* Clear everything on entry to filters or handlers */
 891                 init_to_zero = true;
 892             }
 893         }
 894 #endif
 895         if (init_to_zero)
 896         {
 897             /* Initialize to {ZERO} prior to dataflow */
 898             block->bbCseIn = BitVecOps::MakeCopy(cseTraits, cseEmpty);
 899         }
 900         else
 901         {
 902             /* Initialize to {ALL} prior to dataflow */
 903             block->bbCseIn = BitVecOps::MakeCopy(cseTraits, cseFull);
 904         }
 905
 906         block->bbCseOut = BitVecOps::MakeCopy(cseTraits, cseFull);
 907
 908         /* Initialize to {ZERO} prior to locating the CSE candidates */
 909         block->bbCseGen = BitVecOps::MakeCopy(cseTraits, cseEmpty);
 910     }
 911
 912     // We walk the set of CSE candidates and set the bit corresponsing to the CSEindex
 913     // in the block's bbCseGen bitset
 914     //
 915     for (unsigned cnt = 0; cnt < optCSECandidateCount; cnt++)
 916     {
 917         CSEdsc*        dsc      = optCSEtab[cnt];
 918         unsigned       CSEindex = dsc->csdIndex;
 919         treeStmtLstPtr lst      = dsc->csdTreeList;
 920         noway_assert(lst);
 921
 922         while (lst != nullptr)
 923         {
 924             BasicBlock* block = lst->tslBlock;
 925             BitVecOps::AddElemD(cseTraits, block->bbCseGen, genCSEnum2bit(CSEindex));
 926             lst = lst->tslNext;
 927         }
 928     }
 929
 930 #ifdef DEBUG
 931     // Dump out the bbCseGen information that we just created
 932     //
 933     if (verbose)
 934     {
 935         bool headerPrinted = false;
 936         for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
 937         {
 938             if (block->bbCseGen != nullptr)
 939             {
 940                 if (!headerPrinted)
 941                 {
 942                     printf("\nBlocks that generate CSE def/uses\n");
 943                     headerPrinted = true;
 944                 }
 945                 printf("BB%02u", block->bbNum);
 946                 printf(" cseGen = %s\n", genES2str(cseTraits, block->bbCseGen));
 947             }
 948         }
 949     }
 950
 951     fgDebugCheckLinks();
 952
 953 #endif // DEBUG
 954 }
 955
 956 /*****************************************************************************
 957  *
 958  * CSE Dataflow, so that all helper methods for dataflow are in a single place
 959  *
 960  */
 961 class CSE_DataFlow
 962 {
 963 private:
 964     EXPSET_TP m_preMergeOut;
 965
 966     Compiler* m_pCompiler;
 967
 968 public:
 969     CSE_DataFlow(Compiler* pCompiler) : m_pCompiler(pCompiler)
 970     {
 971     }
 972
 973     Compiler* getCompiler()
 974     {
 975         return m_pCompiler;
 976     }
 977
 978     // At the start of the merge function of the dataflow equations, initialize premerge state (to detect changes.)
 979     void StartMerge(BasicBlock* block)
 980     {
 981         m_preMergeOut = BitVecOps::MakeCopy(m_pCompiler->cseTraits, block->bbCseOut);
 982     }
 983
 984     // During merge, perform the actual merging of the predecessor's (since this is a forward analysis) dataflow flags.
 985     void Merge(BasicBlock* block, BasicBlock* predBlock, flowList* preds)
 986     {
 987         BitVecOps::IntersectionD(m_pCompiler->cseTraits, block->bbCseIn, predBlock->bbCseOut);
 988     }
 989
 990     // At the end of the merge store results of the dataflow equations, in a postmerge state.
 991     bool EndMerge(BasicBlock* block)
 992     {
 993         BitVecTraits* traits   = m_pCompiler->cseTraits;
 994         EXPSET_TP     mergeOut = BitVecOps::MakeCopy(traits, block->bbCseIn);
 995         BitVecOps::UnionD(traits, mergeOut, block->bbCseGen);
 996         BitVecOps::IntersectionD(traits, mergeOut, block->bbCseOut);
 997         BitVecOps::Assign(traits, block->bbCseOut, mergeOut);
 998         return (!BitVecOps::Equal(traits, mergeOut, m_preMergeOut));
 999     }
1000 };
1001
1002 /*****************************************************************************
1003  *
1004  *  Perform a DataFlow forward analysis using the block CSE bitsets:
1005  *    Inputs:
1006  *      bbCseGen  - Exact CSEs that are become available within the block
1007  *      bbCseIn   - Maximal estimate of CSEs that are/could be available at input to the block
1008  *      bbCseOut  - Maximal estimate of CSEs that are/could be available at exit to the block
1009  *
1010  *    Outputs:
1011  *      bbCseIn   - Computed CSEs that are available at input to the block
1012  *      bbCseOut  - Computed CSEs that are available at exit to the block
1013  */
1014
1015 void Compiler::optValnumCSE_DataFlow()
1016 {
1017     CSE_DataFlow cse(this);
1018
1019     // Modified dataflow algorithm for available expressions.
1020     DataFlow cse_flow(this);
1021
1022     cse_flow.ForwardAnalysis(cse);
1023
1024 #ifdef DEBUG
1025     if (verbose)
1026     {
1027         printf("\nAfter performing DataFlow for ValnumCSE's\n");
1028
1029         for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
1030         {
1031             printf("BB%02u", block->bbNum);
1032             printf(" cseIn  = %s", genES2str(cseTraits, block->bbCseIn));
1033             printf(" cseOut = %s", genES2str(cseTraits, block->bbCseOut));
1034             printf("\n");
1035         }
1036
1037         printf("\n");
1038     }
1039 #endif // DEBUG
1040 }
1041
1042 /*****************************************************************************
1043  *
1044  *   Using the information computed by CSE_DataFlow determine for each
1045  *   CSE whether the CSE is a definition (if the CSE was not available)
1046  *   or if the CSE is a use (if the CSE was previously made available)
1047  *   The implementation iterates of all blocks setting 'available_cses'
1048  *   to the CSEs that are available at input to the block.
1049  *   When a CSE expression is encountered it is classified as either
1050  *   as a definition (if the CSE is not in the 'available_cses' set) or
1051  *   as a use (if the CSE is  in the 'available_cses' set).  If the CSE
1052  *   is a definition then it is added to the 'available_cses' set.
1053  *   In the Value Number based CSEs we do not need to have kill sets
1054  */
1055
1056 void Compiler::optValnumCSE_Availablity()
1057 {
1058 #ifdef DEBUG
1059     if (verbose)
1060     {
1061         printf("Labeling the CSEs with Use/Def information\n");
1062     }
1063 #endif
1064     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
1065     {
1066         GenTreePtr stmt;
1067         GenTreePtr tree;
1068
1069         /* Make the block publicly available */
1070
1071         compCurBB = block;
1072
1073         EXPSET_TP available_cses = BitVecOps::MakeCopy(cseTraits, block->bbCseIn);
1074
1075         optCSEweight = block->getBBWeight(this);
1076
1077         /* Walk the statement trees in this basic block */
1078
1079         for (stmt = block->FirstNonPhiDef(); stmt; stmt = stmt->gtNext)
1080         {
1081             noway_assert(stmt->gtOper == GT_STMT);
1082
1083             /* We walk the tree in the forwards direction (bottom up) */
1084             for (tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
1085             {
1086                 if (IS_CSE_INDEX(tree->gtCSEnum))
1087                 {
1088                     unsigned int cseBit = genCSEnum2bit(tree->gtCSEnum);
1089                     CSEdsc*      desc   = optCSEfindDsc(tree->gtCSEnum);
1090                     unsigned     stmw   = block->getBBWeight(this);
1091
1092                     /* Is this expression available here? */
1093
1094                     if (BitVecOps::IsMember(cseTraits, available_cses, cseBit))
1095                     {
1096                         /* This is a CSE use */
1097
1098                         desc->csdUseCount += 1;
1099                         desc->csdUseWtCnt += stmw;
1100                     }
1101                     else
1102                     {
1103                         if (tree->gtFlags & GTF_COLON_COND)
1104                         {
1105                             // We can't create CSE definitions inside QMARK-COLON trees
1106                             tree->gtCSEnum = NO_CSE;
1107                             continue;
1108                         }
1109
1110                         /* This is a CSE def */
1111
1112                         if (desc->csdDefCount == 0)
1113                         {
1114                             // This is the first def visited, so copy its conservative VN
1115                             desc->defConservativeVN = tree->gtVNPair.GetConservative();
1116                         }
1117                         else if (tree->gtVNPair.GetConservative() != desc->defConservativeVN)
1118                         {
1119                             // This candidate has defs with differing conservative VNs
1120                             desc->defConservativeVN = ValueNumStore::NoVN;
1121                         }
1122
1123                         desc->csdDefCount += 1;
1124                         desc->csdDefWtCnt += stmw;
1125
1126                         /* Mark the node as a CSE definition */
1127
1128                         tree->gtCSEnum = TO_CSE_DEF(tree->gtCSEnum);
1129
1130                         /* This CSE will be available after this def */
1131                         BitVecOps::AddElemD(cseTraits, available_cses, cseBit);
1132                     }
1133 #ifdef DEBUG
1134                     if (verbose && IS_CSE_INDEX(tree->gtCSEnum))
1135                     {
1136                         printf("BB%02u ", block->bbNum);
1137                         printTreeID(tree);
1138                         printf(" %s of CSE #%02u [weight=%s]\n", IS_CSE_USE(tree->gtCSEnum) ? "Use" : "Def",
1139                                GET_CSE_INDEX(tree->gtCSEnum), refCntWtd2str(stmw));
1140                     }
1141 #endif
1142                 }
1143             }
1144         }
1145     }
1146 }
1147
1148 //  The following class handles the CSE heuristics
1149 //  we use a complex set of heuristic rules
1150 //  to determine if it is likely to be profitable to perform this CSE
1151 //
1152 class CSE_Heuristic
1153 {
1154     Compiler* m_pCompiler;
1155     unsigned  m_addCSEcount;
1156
1157     unsigned               aggressiveRefCnt;
1158     unsigned               moderateRefCnt;
1159     unsigned               enregCount; // count of the number of enregisterable variables
1160     bool                   largeFrame;
1161     bool                   hugeFrame;
1162     Compiler::codeOptimize codeOptKind;
1163     Compiler::CSEdsc**     sortTab;
1164     size_t                 sortSiz;
1165 #ifdef DEBUG
1166     CLRRandom m_cseRNG;
1167     unsigned  m_bias;
1168 #endif
1169
1170 public:
1171     CSE_Heuristic(Compiler* pCompiler) : m_pCompiler(pCompiler)
1172     {
1173         codeOptKind = m_pCompiler->compCodeOpt();
1174     }
1175
1176     Compiler::codeOptimize CodeOptKind()
1177     {
1178         return codeOptKind;
1179     }
1180
1181     // Perform the Initialization step for our CSE Heuristics
1182     // determine the various cut off values to use for
1183     // the aggressive, moderate and conservative CSE promotions
1184     // count the number of enregisterable variables
1185     // determine if the method has a large or huge stack frame.
1186     //
1187     void Initialize()
1188     {
1189         m_addCSEcount = 0; /* Count of the number of LclVars for CSEs that we added */
1190
1191         // Record the weighted ref count of the last "for sure" callee saved LclVar
1192         aggressiveRefCnt = 0;
1193         moderateRefCnt   = 0;
1194         enregCount       = 0;
1195         largeFrame       = false;
1196         hugeFrame        = false;
1197         sortTab          = nullptr;
1198         sortSiz          = 0;
1199
1200 #ifdef _TARGET_XARCH_
1201         if (m_pCompiler->compLongUsed)
1202         {
1203             enregCount++;
1204         }
1205 #endif
1206
1207         unsigned   frameSize        = 0;
1208         unsigned   regAvailEstimate = ((CNT_CALLEE_ENREG * 3) + (CNT_CALLEE_TRASH * 2) + 1);
1209         unsigned   lclNum;
1210         LclVarDsc* varDsc;
1211
1212         for (lclNum = 0, varDsc = m_pCompiler->lvaTable; lclNum < m_pCompiler->lvaCount; lclNum++, varDsc++)
1213         {
1214             if (varDsc->lvRefCnt == 0)
1215             {
1216                 continue;
1217             }
1218
1219             bool onStack = (regAvailEstimate == 0); // true when it is likely that this LclVar will have a stack home
1220
1221             // Some LclVars always have stack homes
1222             if ((varDsc->lvDoNotEnregister) || (varDsc->lvType == TYP_LCLBLK))
1223             {
1224                 onStack = true;
1225             }
1226
1227 #ifdef _TARGET_X86_
1228             // Treat floating point and 64 bit integers as always on the stack
1229             if (varTypeIsFloating(varDsc->TypeGet()) || varTypeIsLong(varDsc->TypeGet()))
1230                 onStack = true;
1231 #endif
1232
1233             if (onStack)
1234             {
1235                 frameSize += m_pCompiler->lvaLclSize(lclNum);
1236             }
1237             else
1238             {
1239                 // For the purposes of estimating the frameSize we
1240                 // will consider this LclVar as being enregistered.
1241                 // Now we reduce the remaining regAvailEstimate by
1242                 // an appropriate amount.
1243                 if (varDsc->lvRefCnt <= 2)
1244                 {
1245                     // a single use single def LclVar only uses 1
1246                     regAvailEstimate -= 1;
1247                 }
1248                 else
1249                 {
1250                     // a LclVar with multiple uses and defs uses 2
1251                     if (regAvailEstimate >= 2)
1252                     {
1253                         regAvailEstimate -= 2;
1254                     }
1255                     else
1256                     {
1257                         // Don't try to subtract when regAvailEstimate is 1
1258                         regAvailEstimate = 0;
1259                     }
1260                 }
1261             }
1262 #ifdef _TARGET_XARCH_
1263             if (frameSize > 0x080)
1264             {
1265                 // We likely have a large stack frame.
1266                 // Thus we might need to use large displacements when loading or storing
1267                 // to CSE LclVars that are not enregistered
1268                 largeFrame = true;
1269                 break; // early out,  we don't need to keep increasing frameSize
1270             }
1271 #else // _TARGET_ARM_
1272             if (frameSize > 0x0400)
1273             {
1274                 largeFrame = true;
1275             }
1276             if (frameSize > 0x10000)
1277             {
1278                 hugeFrame = true;
1279                 break;
1280             }
1281 #endif
1282         }
1283
1284         unsigned sortNum = 0;
1285         while (sortNum < m_pCompiler->lvaTrackedCount)
1286         {
1287             LclVarDsc* varDsc = m_pCompiler->lvaRefSorted[sortNum++];
1288             var_types  varTyp = varDsc->TypeGet();
1289
1290             if (varDsc->lvDoNotEnregister)
1291             {
1292                 continue;
1293             }
1294
1295             if (!varTypeIsFloating(varTyp))
1296             {
1297                 // TODO-1stClassStructs: Remove this; it is here to duplicate previous behavior.
1298                 // Note that this makes genTypeStSz return 1.
1299                 if (varTypeIsStruct(varTyp))
1300                 {
1301                     varTyp = TYP_STRUCT;
1302                 }
1303                 enregCount += genTypeStSz(varTyp);
1304             }
1305
1306             if ((aggressiveRefCnt == 0) && (enregCount > (CNT_CALLEE_ENREG * 3 / 2)))
1307             {
1308                 if (CodeOptKind() == Compiler::SMALL_CODE)
1309                 {
1310                     aggressiveRefCnt = varDsc->lvRefCnt + BB_UNITY_WEIGHT;
1311                 }
1312                 else
1313                 {
1314                     aggressiveRefCnt = varDsc->lvRefCntWtd + BB_UNITY_WEIGHT;
1315                 }
1316             }
1317             if ((moderateRefCnt == 0) && (enregCount > ((CNT_CALLEE_ENREG * 3) + (CNT_CALLEE_TRASH * 2))))
1318             {
1319                 if (CodeOptKind() == Compiler::SMALL_CODE)
1320                 {
1321                     moderateRefCnt = varDsc->lvRefCnt;
1322                 }
1323                 else
1324                 {
1325                     moderateRefCnt = varDsc->lvRefCntWtd;
1326                 }
1327             }
1328         }
1329         unsigned mult = 3;
1330         // use smaller value for mult when enregCount is in [0..4]
1331         if (enregCount <= 4)
1332         {
1333             mult = (enregCount <= 2) ? 1 : 2;
1334         }
1335
1336         aggressiveRefCnt = max(BB_UNITY_WEIGHT * mult, aggressiveRefCnt);
1337         moderateRefCnt   = max((BB_UNITY_WEIGHT * mult) / 2, moderateRefCnt);
1338
1339 #ifdef DEBUG
1340         if (m_pCompiler->verbose)
1341         {
1342             printf("\n");
1343             printf("Aggressive CSE Promotion cutoff is %u\n", aggressiveRefCnt);
1344             printf("Moderate CSE Promotion cutoff is %u\n", moderateRefCnt);
1345             printf("Framesize estimate is 0x%04X\n", frameSize);
1346             printf("We have a %s frame\n", hugeFrame ? "huge" : (largeFrame ? "large" : "small"));
1347         }
1348 #endif
1349     }
1350
1351     void SortCandidates()
1352     {
1353         /* Create an expression table sorted by decreasing cost */
1354         sortTab = new (m_pCompiler, CMK_CSE) Compiler::CSEdsc*[m_pCompiler->optCSECandidateCount];
1355
1356         sortSiz = m_pCompiler->optCSECandidateCount * sizeof(*sortTab);
1357         memcpy(sortTab, m_pCompiler->optCSEtab, sortSiz);
1358
1359         if (CodeOptKind() == Compiler::SMALL_CODE)
1360         {
1361             qsort(sortTab, m_pCompiler->optCSECandidateCount, sizeof(*sortTab), m_pCompiler->optCSEcostCmpSz);
1362         }
1363         else
1364         {
1365             qsort(sortTab, m_pCompiler->optCSECandidateCount, sizeof(*sortTab), m_pCompiler->optCSEcostCmpEx);
1366         }
1367
1368 #ifdef DEBUG
1369         if (m_pCompiler->verbose)
1370         {
1371             printf("\nSorted CSE candidates:\n");
1372             /* Print out the CSE candidates */
1373             EXPSET_TP tempMask;
1374             for (unsigned cnt = 0; cnt < m_pCompiler->optCSECandidateCount; cnt++)
1375             {
1376                 Compiler::CSEdsc* dsc  = sortTab[cnt];
1377                 GenTreePtr        expr = dsc->csdTree;
1378
1379                 unsigned def;
1380                 unsigned use;
1381
1382                 if (CodeOptKind() == Compiler::SMALL_CODE)
1383                 {
1384                     def = dsc->csdDefCount; // def count
1385                     use = dsc->csdUseCount; // use count (excluding the implicit uses at defs)
1386                 }
1387                 else
1388                 {
1389                     def = dsc->csdDefWtCnt; // weighted def count
1390                     use = dsc->csdUseWtCnt; // weighted use count (excluding the implicit uses at defs)
1391                 }
1392
1393                 tempMask = BitVecOps::MakeSingleton(m_pCompiler->cseTraits, genCSEnum2bit(dsc->csdIndex));
1394                 printf("CSE #%02u,cseMask=%s,useCnt=%d: [def=%3u, use=%3u", dsc->csdIndex,
1395                        genES2str(m_pCompiler->cseTraits, tempMask), dsc->csdUseCount, def, use);
1396                 printf("] :: ");
1397                 m_pCompiler->gtDispTree(expr, nullptr, nullptr, true);
1398             }
1399             printf("\n");
1400         }
1401 #endif // DEBUG
1402     }
1403
1404     //  The following class nested within CSE_Heuristic encapsulates the information
1405     //  about the current CSE candidate that is under consideration
1406     //
1407     //  TODO-Cleanup: This is still very much based upon the old Lexical CSE implementation
1408     //  and needs to be reworked for the Value Number based implementation
1409     //
1410     class CSE_Candidate
1411     {
1412         CSE_Heuristic*    m_context;
1413         Compiler::CSEdsc* m_CseDsc;
1414
1415         unsigned m_cseIndex;
1416
1417         unsigned m_defCount;
1418         unsigned m_useCount;
1419
1420         unsigned m_Cost;
1421         unsigned m_Size;
1422
1423     public:
1424         CSE_Candidate(CSE_Heuristic* context, Compiler::CSEdsc* cseDsc) : m_context(context), m_CseDsc(cseDsc)
1425         {
1426             m_cseIndex = m_CseDsc->csdIndex;
1427         }
1428
1429         Compiler::CSEdsc* CseDsc()
1430         {
1431             return m_CseDsc;
1432         }
1433         unsigned CseIndex()
1434         {
1435             return m_cseIndex;
1436         }
1437         unsigned DefCount()
1438         {
1439             return m_defCount;
1440         }
1441         unsigned UseCount()
1442         {
1443             return m_useCount;
1444         }
1445         // TODO-CQ: With ValNum CSE's the Expr and its cost can vary.
1446         GenTreePtr Expr()
1447         {
1448             return m_CseDsc->csdTree;
1449         }
1450         unsigned Cost()
1451         {
1452             return m_Cost;
1453         }
1454         unsigned Size()
1455         {
1456             return m_Size;
1457         }
1458
1459         bool LiveAcrossCall()
1460         {
1461             return (m_CseDsc->csdLiveAcrossCall != 0);
1462         }
1463
1464         void InitializeCounts()
1465         {
1466             if (m_context->CodeOptKind() == Compiler::SMALL_CODE)
1467             {
1468                 m_Cost     = Expr()->gtCostSz;      // the estimated code size
1469                 m_Size     = Expr()->gtCostSz;      // always the gtCostSz
1470                 m_defCount = m_CseDsc->csdDefCount; // def count
1471                 m_useCount = m_CseDsc->csdUseCount; // use count (excluding the implicit uses at defs)
1472             }
1473             else
1474             {
1475                 m_Cost     = Expr()->gtCostEx;      // the estimated execution cost
1476                 m_Size     = Expr()->gtCostSz;      // always the gtCostSz
1477                 m_defCount = m_CseDsc->csdDefWtCnt; // weighted def count
1478                 m_useCount = m_CseDsc->csdUseWtCnt; // weighted use count (excluding the implicit uses at defs)
1479             }
1480         }
1481     };
1482
1483 #ifdef DEBUG
1484     //------------------------------------------------------------------------
1485     // optConfigBiasedCSE:
1486     //     Stress mode to shuffle the decision to CSE or not using environment
1487     //     variable COMPlus_JitStressBiasedCSE (= 0 to 100%). When the bias value
1488     //     is not specified but COMPlus_JitStress is ON, generate a random bias.
1489     //
1490     // Return Value:
1491     //      0 -- This method is indifferent about this CSE (no bias specified and no stress)
1492     //      1 -- This CSE must be performed to maintain specified/generated bias.
1493     //     -1 -- This CSE mustn't be performed to maintain specified/generated bias.
1494     //
1495     // Operation:
1496     //     A debug stress only method that returns "1" with probability (P)
1497     //     defined by:
1498     //
1499     //         P = (COMPlus_JitStressBiasedCSE / 100) (or)
1500     //         P = (random(100) / 100) when COMPlus_JitStress is specified and
1501     //                                 COMPlus_JitStressBiasedCSE is unspecified.
1502     //
1503     //     When specified, the bias is reinterpreted as a decimal number between 0
1504     //     to 100.
1505     //     When bias is not specified, a bias is randomly generated if COMPlus_JitStress
1506     //     is non-zero.
1507     //
1508     //     Callers are supposed to call this method for each CSE promotion decision
1509     //     and ignore the call if return value is 0 and honor the 1 with a CSE and
1510     //     -1 with a no-CSE to maintain the specified/generated bias.
1511     //
1512     int optConfigBiasedCSE()
1513     {
1514         // Seed the PRNG, if never done before.
1515         if (!m_cseRNG.IsInitialized())
1516         {
1517             m_cseRNG.Init(m_pCompiler->info.compMethodHash());
1518             m_bias = m_cseRNG.Next(100);
1519         }
1520
1521         // Obtain the bias value and reinterpret as decimal.
1522         unsigned bias = ReinterpretHexAsDecimal(JitConfig.JitStressBiasedCSE());
1523
1524         // Invalid value, check if JitStress is ON.
1525         if (bias > 100)
1526         {
1527             if (!m_pCompiler->compStressCompile(Compiler::STRESS_MAKE_CSE, MAX_STRESS_WEIGHT))
1528             {
1529                 // JitStress is OFF for CSE, nothing to do.
1530                 return 0;
1531             }
1532             bias = m_bias;
1533             JITDUMP("JitStressBiasedCSE is OFF, but JitStress is ON: generated bias=%d.\n", bias);
1534         }
1535
1536         // Generate a number between (0, 99) and if the generated
1537         // number is smaller than bias, then perform CSE.
1538         unsigned gen = m_cseRNG.Next(100);
1539         int      ret = (gen < bias) ? 1 : -1;
1540
1541         if (m_pCompiler->verbose)
1542         {
1543             if (ret < 0)
1544             {
1545                 printf("No CSE because gen=%d >= bias=%d\n", gen, bias);
1546             }
1547             else
1548             {
1549                 printf("Promoting CSE because gen=%d < bias=%d\n", gen, bias);
1550             }
1551         }
1552
1553         // Indicate whether to perform CSE or not.
1554         return ret;
1555     }
1556 #endif
1557
1558     // Given a CSE candidate decide whether it passes or fails the profitablity heuristic
1559     // return true if we believe that it is profitable to promote this candidate to a CSE
1560     //
1561     bool PromotionCheck(CSE_Candidate* candidate)
1562     {
1563         bool result = false;
1564
1565 #ifdef DEBUG
1566         int stressResult = optConfigBiasedCSE();
1567         if (stressResult != 0)
1568         {
1569             // Stress is enabled. Check whether to perform CSE or not.
1570             return (stressResult > 0);
1571         }
1572
1573         if (m_pCompiler->optConfigDisableCSE2())
1574         {
1575             return false; // skip this CSE
1576         }
1577 #endif
1578
1579         /*
1580             Our calculation is based on the following cost estimate formula
1581
1582             Existing costs are:
1583
1584             (def + use) * cost
1585
1586             If we introduce a CSE temp are each definition and
1587             replace the use with a CSE temp then our cost is:
1588
1589             (def * (cost + cse-def-cost)) + (use * cse-use-cost)
1590
1591             We must estimate the values to use for cse-def-cost and cse-use-cost
1592
1593             If we are able to enregister the CSE then the cse-use-cost is one
1594             and cse-def-cost is either zero or one.  Zero in the case where
1595             we needed to evaluate the def into a register and we can use that
1596             register as the CSE temp as well.
1597
1598             If we are unable to enregister the CSE then the cse-use-cost is IND_COST
1599             and the cse-def-cost is also IND_COST.
1600
1601             If we want to be conservative we use IND_COST as the the value
1602             for both cse-def-cost and cse-use-cost and then we never introduce
1603             a CSE that could pessimize the execution time of the method.
1604
1605             If we want to be more moderate we use (IND_COST_EX + 1) / 2 as the
1606             values for both cse-def-cost and cse-use-cost.
1607
1608             If we want to be aggressive we use 1 as the values for both
1609             cse-def-cost and cse-use-cost.
1610
1611             If we believe that the CSE very valuable in terms of weighted ref counts
1612             such that it would always be enregistered by the register allocator we choose
1613             the aggressive use def costs.
1614
1615             If we believe that the CSE is somewhat valuable in terms of weighted ref counts
1616             such that it could be likely be enregistered by the register allocator we choose
1617             the moderate use def costs.
1618
1619             otherwise we choose the conservative use def costs.
1620
1621         */
1622
1623         unsigned cse_def_cost;
1624         unsigned cse_use_cost;
1625
1626         unsigned no_cse_cost    = 0;
1627         unsigned yes_cse_cost   = 0;
1628         unsigned extra_yes_cost = 0;
1629         unsigned extra_no_cost  = 0;
1630
1631         // The 'cseRefCnt' is the RefCnt that we will have if we promote this CSE into a new LclVar
1632         // Each CSE Def will contain two Refs and each CSE Use wil have one Ref of this new LclVar
1633         unsigned cseRefCnt = (candidate->DefCount() * 2) + candidate->UseCount();
1634
1635         if (CodeOptKind() == Compiler::SMALL_CODE)
1636         {
1637             if (cseRefCnt >= aggressiveRefCnt)
1638             {
1639 #ifdef DEBUG
1640                 if (m_pCompiler->verbose)
1641                 {
1642                     printf("Aggressive CSE Promotion (%u >= %u)\n", cseRefCnt, aggressiveRefCnt);
1643                 }
1644 #endif
1645                 cse_def_cost = 1;
1646                 cse_use_cost = 1;
1647
1648                 if (candidate->LiveAcrossCall() != 0)
1649                 {
1650                     if (largeFrame)
1651                     {
1652                         cse_def_cost++;
1653                         cse_use_cost++;
1654                     }
1655                     if (hugeFrame)
1656                     {
1657                         cse_def_cost++;
1658                         cse_use_cost++;
1659                     }
1660                 }
1661             }
1662             else if (largeFrame)
1663             {
1664 #ifdef DEBUG
1665                 if (m_pCompiler->verbose)
1666                 {
1667                     printf("Codesize CSE Promotion (large frame)\n");
1668                 }
1669 #endif
1670 #ifdef _TARGET_XARCH_
1671                 /* The following formula is good choice when optimizing CSE for SMALL_CODE */
1672                 cse_def_cost = 6; // mov [EBP-0x00001FC],reg
1673                 cse_use_cost = 5; //     [EBP-0x00001FC]
1674 #else                             // _TARGET_ARM_
1675                 if (hugeFrame)
1676                 {
1677                     cse_def_cost = 12; // movw/movt r10 and str reg,[sp+r10]
1678                     cse_use_cost = 12;
1679                 }
1680                 else
1681                 {
1682                     cse_def_cost = 8; // movw r10 and str reg,[sp+r10]
1683                     cse_use_cost = 8;
1684                 }
1685 #endif
1686             }
1687             else // small frame
1688             {
1689 #ifdef DEBUG
1690                 if (m_pCompiler->verbose)
1691                 {
1692                     printf("Codesize CSE Promotion (small frame)\n");
1693                 }
1694 #endif
1695 #ifdef _TARGET_XARCH_
1696                 /* The following formula is good choice when optimizing CSE for SMALL_CODE */
1697                 cse_def_cost = 3; // mov [EBP-1C],reg
1698                 cse_use_cost = 2; //     [EBP-1C]
1699 #else                             // _TARGET_ARM_
1700                 cse_def_cost = 2; // str reg,[sp+0x9c]
1701                 cse_use_cost = 2; // ldr reg,[sp+0x9c]
1702 #endif
1703             }
1704         }
1705         else // not SMALL_CODE ...
1706         {
1707             if (cseRefCnt >= aggressiveRefCnt)
1708             {
1709 #ifdef DEBUG
1710                 if (m_pCompiler->verbose)
1711                 {
1712                     printf("Aggressive CSE Promotion (%u >= %u)\n", cseRefCnt, aggressiveRefCnt);
1713                 }
1714 #endif
1715                 cse_def_cost = 1;
1716                 cse_use_cost = 1;
1717             }
1718             else if (cseRefCnt >= moderateRefCnt)
1719             {
1720
1721                 if (candidate->LiveAcrossCall() == 0)
1722                 {
1723 #ifdef DEBUG
1724                     if (m_pCompiler->verbose)
1725                     {
1726                         printf("Moderate CSE Promotion (CSE never live at call) (%u >= %u)\n", cseRefCnt,
1727                                moderateRefCnt);
1728                     }
1729 #endif
1730                     cse_def_cost = 2;
1731                     cse_use_cost = 1;
1732                 }
1733                 else // candidate is live across call
1734                 {
1735 #ifdef DEBUG
1736                     if (m_pCompiler->verbose)
1737                     {
1738                         printf("Moderate CSE Promotion (%u >= %u)\n", cseRefCnt, moderateRefCnt);
1739                     }
1740 #endif
1741                     cse_def_cost   = 2;
1742                     cse_use_cost   = 2;
1743                     extra_yes_cost = BB_UNITY_WEIGHT * 2; // Extra cost in case we have to spill/restore a caller
1744                                                           // saved register
1745                 }
1746             }
1747             else // Conservative CSE promotion
1748             {
1749                 if (candidate->LiveAcrossCall() == 0)
1750                 {
1751 #ifdef DEBUG
1752                     if (m_pCompiler->verbose)
1753                     {
1754                         printf("Conservative CSE Promotion (CSE never live at call) (%u < %u)\n", cseRefCnt,
1755                                moderateRefCnt);
1756                     }
1757 #endif
1758                     cse_def_cost = 2;
1759                     cse_use_cost = 2;
1760                 }
1761                 else // candidate is live across call
1762                 {
1763 #ifdef DEBUG
1764                     if (m_pCompiler->verbose)
1765                     {
1766                         printf("Conservative CSE Promotion (%u < %u)\n", cseRefCnt, moderateRefCnt);
1767                     }
1768 #endif
1769                     cse_def_cost   = 3;
1770                     cse_use_cost   = 3;
1771                     extra_yes_cost = BB_UNITY_WEIGHT * 4; // Extra cost in case we have to spill/restore a caller
1772                                                           // saved register
1773                 }
1774
1775                 // If we have maxed out lvaTrackedCount then this CSE may end up as an untracked variable
1776                 if (m_pCompiler->lvaTrackedCount == lclMAX_TRACKED)
1777                 {
1778                     cse_def_cost++;
1779                     cse_use_cost++;
1780                 }
1781             }
1782
1783             if (largeFrame)
1784             {
1785                 cse_def_cost++;
1786                 cse_use_cost++;
1787             }
1788             if (hugeFrame)
1789             {
1790                 cse_def_cost++;
1791                 cse_use_cost++;
1792             }
1793         }
1794
1795         // estimate the cost from lost codesize reduction if we do not perform the CSE
1796         if (candidate->Size() > cse_use_cost)
1797         {
1798             Compiler::CSEdsc* dsc = candidate->CseDsc(); // We need to retrieve the actual use count, not the
1799                                                          // weighted count
1800             extra_no_cost = candidate->Size() - cse_use_cost;
1801             extra_no_cost = extra_no_cost * dsc->csdUseCount * 2;
1802         }
1803
1804         /* no_cse_cost  is the cost estimate when we decide not to make a CSE */
1805         /* yes_cse_cost is the cost estimate when we decide to make a CSE     */
1806
1807         no_cse_cost  = candidate->UseCount() * candidate->Cost();
1808         yes_cse_cost = (candidate->DefCount() * cse_def_cost) + (candidate->UseCount() * cse_use_cost);
1809
1810 #if CPU_LONG_USES_REGPAIR
1811         if (candidate->Expr()->TypeGet() == TYP_LONG)
1812         {
1813             yes_cse_cost *= 2;
1814         }
1815 #endif
1816         no_cse_cost += extra_no_cost;
1817         yes_cse_cost += extra_yes_cost;
1818
1819 #ifdef DEBUG
1820         if (m_pCompiler->verbose)
1821         {
1822             printf("cseRefCnt=%d, aggressiveRefCnt=%d, moderateRefCnt=%d\n", cseRefCnt, aggressiveRefCnt,
1823                    moderateRefCnt);
1824             printf("defCnt=%d, useCnt=%d, cost=%d, size=%d\n", candidate->DefCount(), candidate->UseCount(),
1825                    candidate->Cost(), candidate->Size());
1826             printf("def_cost=%d, use_cost=%d, extra_no_cost=%d, extra_yes_cost=%d\n", cse_def_cost, cse_use_cost,
1827                    extra_no_cost, extra_yes_cost);
1828
1829             printf("CSE cost savings check (%u >= %u) %s\n", no_cse_cost, yes_cse_cost,
1830                    (no_cse_cost >= yes_cse_cost) ? "passes" : "fails");
1831         }
1832 #endif
1833
1834         // Should we make this candidate into a CSE?
1835         // Is the yes cost less than the no cost
1836         //
1837         if (yes_cse_cost <= no_cse_cost)
1838         {
1839             result = true; // Yes make this a CSE
1840         }
1841         else
1842         {
1843             /* In stress mode we will make some extra CSEs */
1844             if (no_cse_cost > 0)
1845             {
1846                 int percentage = (no_cse_cost * 100) / yes_cse_cost;
1847
1848                 if (m_pCompiler->compStressCompile(Compiler::STRESS_MAKE_CSE, percentage))
1849                 {
1850                     result = true; // Yes make this a CSE
1851                 }
1852             }
1853         }
1854
1855         return result;
1856     }
1857
1858     // PerformCSE() takes a successful candidate and performs  the appropriate replacements:
1859     //
1860     // It will replace all of the CSE defs with assignments to a new "cse0" LclVar
1861     // and will replace all of the CSE uses with reads of the "cse0" LclVar
1862     //
1863     void PerformCSE(CSE_Candidate* successfulCandidate)
1864     {
1865         unsigned cseRefCnt = (successfulCandidate->DefCount() * 2) + successfulCandidate->UseCount();
1866
1867         if (successfulCandidate->LiveAcrossCall() != 0)
1868         {
1869             // As we introduce new LclVars for these CSE we slightly
1870             // increase the cutoffs for aggressive and moderate CSE's
1871             //
1872             int incr = BB_UNITY_WEIGHT;
1873
1874 #if CPU_LONG_USES_REGPAIR
1875             if (successfulCandidate->Expr()->TypeGet() == TYP_LONG)
1876                 incr *= 2;
1877 #endif
1878
1879             if (cseRefCnt > aggressiveRefCnt)
1880             {
1881                 aggressiveRefCnt += incr;
1882             }
1883
1884             if (cseRefCnt > moderateRefCnt)
1885             {
1886                 moderateRefCnt += (incr / 2);
1887             }
1888         }
1889
1890         /* Introduce a new temp for the CSE */
1891
1892         // we will create a  long lifetime temp for the new cse LclVar
1893         unsigned  cseLclVarNum = m_pCompiler->lvaGrabTemp(false DEBUGARG("ValNumCSE"));
1894         var_types cseLclVarTyp = genActualType(successfulCandidate->Expr()->TypeGet());
1895         if (varTypeIsStruct(cseLclVarTyp))
1896         {
1897             m_pCompiler->lvaSetStruct(cseLclVarNum, m_pCompiler->gtGetStructHandle(successfulCandidate->Expr()), false);
1898         }
1899         m_pCompiler->lvaTable[cseLclVarNum].lvType  = cseLclVarTyp;
1900         m_pCompiler->lvaTable[cseLclVarNum].lvIsCSE = true;
1901
1902         m_addCSEcount++; // Record that we created a new LclVar for use as a CSE temp
1903         m_pCompiler->optCSEcount++;
1904
1905         ValueNum defConservativeVN = successfulCandidate->CseDsc()->defConservativeVN;
1906
1907         /*  Walk all references to this CSE, adding an assignment
1908             to the CSE temp to all defs and changing all refs to
1909             a simple use of the CSE temp.
1910
1911             We also unmark nested CSE's for all uses.
1912         */
1913
1914         Compiler::treeStmtLstPtr lst;
1915         lst = successfulCandidate->CseDsc()->csdTreeList;
1916         noway_assert(lst);
1917
1918 #define QQQ_CHECK_CSE_VNS 0
1919 #if QQQ_CHECK_CSE_VNS
1920         assert(lst != NULL);
1921         ValueNum firstVN = lst->tslTree->gtVN;
1922         lst              = lst->tslNext;
1923         bool allSame     = true;
1924         while (lst != NULL)
1925         {
1926             if (IS_CSE_INDEX(lst->tslTree->gtCSEnum))
1927             {
1928                 if (lst->tslTree->gtVN != firstVN)
1929                 {
1930                     allSame = false;
1931                     break;
1932                 }
1933             }
1934             lst = lst->tslNext;
1935         }
1936         if (!allSame)
1937         {
1938             lst                  = dsc->csdTreeList;
1939             GenTreePtr firstTree = lst->tslTree;
1940             printf("In %s, CSE (oper = %s, type = %s) has differing VNs: ", info.compFullName,
1941                    GenTree::NodeName(firstTree->OperGet()), varTypeName(firstTree->TypeGet()));
1942             while (lst != NULL)
1943             {
1944                 if (IS_CSE_INDEX(lst->tslTree->gtCSEnum))
1945                 {
1946                     printf("0x%x(%s,%d)    ", lst->tslTree, IS_CSE_USE(lst->tslTree->gtCSEnum) ? "u" : "d",
1947                            lst->tslTree->gtVN);
1948                 }
1949                 lst = lst->tslNext;
1950             }
1951             printf("\n");
1952         }
1953         lst = dsc->csdTreeList;
1954 #endif
1955
1956         do
1957         {
1958             /* Process the next node in the list */
1959             GenTreePtr exp = lst->tslTree;
1960             GenTreePtr stm = lst->tslStmt;
1961             noway_assert(stm->gtOper == GT_STMT);
1962             BasicBlock* blk = lst->tslBlock;
1963
1964             /* Advance to the next node in the list */
1965             lst = lst->tslNext;
1966
1967             // Assert if we used DEBUG_DESTROY_NODE on this CSE exp
1968             assert(exp->gtOper != GT_COUNT);
1969
1970             /* Ignore the node if it's not been marked as a CSE */
1971             if (!IS_CSE_INDEX(exp->gtCSEnum))
1972             {
1973                 continue;
1974             }
1975
1976             /* Make sure we update the weighted ref count correctly */
1977             m_pCompiler->optCSEweight = blk->getBBWeight(m_pCompiler);
1978
1979             /* Figure out the actual type of the value */
1980             var_types expTyp = genActualType(exp->TypeGet());
1981             noway_assert(expTyp == cseLclVarTyp);
1982
1983             // This will contain the replacement tree for exp
1984             // It will either be the CSE def or CSE ref
1985             //
1986             GenTreePtr    cse = nullptr;
1987             bool          isDef;
1988             FieldSeqNode* fldSeq               = nullptr;
1989             bool          hasZeroMapAnnotation = m_pCompiler->GetZeroOffsetFieldMap()->Lookup(exp, &fldSeq);
1990
1991             if (IS_CSE_USE(exp->gtCSEnum))
1992             {
1993                 /* This is a use of the CSE */
1994                 isDef = false;
1995 #ifdef DEBUG
1996                 if (m_pCompiler->verbose)
1997                 {
1998                     printf("\nCSE #%02u use at ", exp->gtCSEnum);
1999                     Compiler::printTreeID(exp);
2000                     printf(" replaced in BB%02u with temp use.\n", blk->bbNum);
2001                 }
2002 #endif // DEBUG
2003
2004                 /* check for and collect any SIDE_EFFECTS */
2005                 GenTreePtr sideEffList = nullptr;
2006
2007                 if (exp->gtFlags & GTF_PERSISTENT_SIDE_EFFECTS)
2008                 {
2009                     // Extract any side effects from exp
2010                     //
2011                     m_pCompiler->gtExtractSideEffList(exp, &sideEffList, GTF_PERSISTENT_SIDE_EFFECTS_IN_CSE);
2012                 }
2013
2014                 // We will replace the CSE ref with a new tree
2015                 // this is typically just a simple use of the new CSE LclVar
2016                 //
2017                 cse           = m_pCompiler->gtNewLclvNode(cseLclVarNum, cseLclVarTyp);
2018                 cse->gtVNPair = exp->gtVNPair; // assign the proper Value Numbers
2019                 if (defConservativeVN != ValueNumStore::NoVN)
2020                 {
2021                     // All defs of this CSE share the same conservative VN, and we are rewriting this
2022                     // use to fetch the same value with no reload, so we can safely propagate that
2023                     // conservative VN to this use.  This can help range check elimination later on.
2024                     cse->gtVNPair.SetConservative(defConservativeVN);
2025
2026                     GenTreePtr cmp;
2027                     if ((exp->OperGet() == GT_ARR_LENGTH) && (m_pCompiler->cseArrLenMap != nullptr) &&
2028                         (m_pCompiler->cseArrLenMap->Lookup(exp, &cmp)))
2029                     {
2030                         // Propagate the new value number to this compare node as well, since
2031                         // subsequent range check elimination will try to correlate it with
2032                         // the other appearances that are getting CSEd.
2033
2034                         ValueNumStore*                      vnStore  = m_pCompiler->vnStore;
2035                         ValueNum                            oldCmpVN = cmp->gtVNPair.GetConservative();
2036                         ValueNumStore::ArrLenArithBoundInfo info;
2037                         ValueNum                            newCmpArgVN;
2038                         if (vnStore->IsVNArrLenBound(oldCmpVN))
2039                         {
2040                             // Comparison is against the array length directly.
2041
2042                             newCmpArgVN = defConservativeVN;
2043                             vnStore->GetArrLenBoundInfo(oldCmpVN, &info);
2044                         }
2045                         else
2046                         {
2047                             // Comparison is against the array length +/- some offset.
2048
2049                             assert(vnStore->IsVNArrLenArithBound(oldCmpVN));
2050                             vnStore->GetArrLenArithBoundInfo(oldCmpVN, &info);
2051                             newCmpArgVN = vnStore->VNForFunc(vnStore->TypeOfVN(info.arrOp), (VNFunc)info.arrOper,
2052                                                              info.arrOp, defConservativeVN);
2053                         }
2054                         ValueNum newCmpVN = vnStore->VNForFunc(vnStore->TypeOfVN(oldCmpVN), (VNFunc)info.cmpOper,
2055                                                                info.cmpOp, newCmpArgVN);
2056                         cmp->gtVNPair.SetConservative(newCmpVN);
2057                     }
2058                 }
2059 #ifdef DEBUG
2060                 cse->gtDebugFlags |= GTF_DEBUG_VAR_CSE_REF;
2061 #endif // DEBUG
2062
2063                 // If we have side effects then we need to create a GT_COMMA tree instead
2064                 //
2065                 if (sideEffList)
2066                 {
2067                     noway_assert(sideEffList->gtFlags & GTF_SIDE_EFFECT);
2068 #ifdef DEBUG
2069                     if (m_pCompiler->verbose)
2070                     {
2071                         printf("\nThe CSE has side effects! Extracting side effects...\n");
2072                         m_pCompiler->gtDispTree(sideEffList);
2073                         printf("\n");
2074                     }
2075 #endif
2076
2077                     GenTreePtr     cseVal         = cse;
2078                     GenTreePtr     curSideEff     = sideEffList;
2079                     ValueNumStore* vnStore        = m_pCompiler->vnStore;
2080                     ValueNumPair   exceptions_vnp = ValueNumStore::VNPForEmptyExcSet();
2081
2082                     while ((curSideEff->OperGet() == GT_COMMA) || (curSideEff->OperGet() == GT_ASG))
2083                     {
2084                         GenTreePtr op1 = curSideEff->gtOp.gtOp1;
2085                         GenTreePtr op2 = curSideEff->gtOp.gtOp2;
2086
2087                         ValueNumPair op1vnp;
2088                         ValueNumPair op1Xvnp = ValueNumStore::VNPForEmptyExcSet();
2089                         vnStore->VNPUnpackExc(op1->gtVNPair, &op1vnp, &op1Xvnp);
2090
2091                         exceptions_vnp = vnStore->VNPExcSetUnion(exceptions_vnp, op1Xvnp);
2092                         curSideEff     = op2;
2093                     }
2094
2095                     // We may have inserted a narrowing cast during a previous remorph
2096                     // and it will not have a value number.
2097                     if ((curSideEff->OperGet() == GT_CAST) && !curSideEff->gtVNPair.BothDefined())
2098                     {
2099                         // The inserted cast will have no exceptional effects
2100                         assert(curSideEff->gtOverflow() == false);
2101                         // Process the exception effects from the cast's operand.
2102                         curSideEff = curSideEff->gtOp.gtOp1;
2103                     }
2104
2105                     ValueNumPair op2vnp;
2106                     ValueNumPair op2Xvnp = ValueNumStore::VNPForEmptyExcSet();
2107                     vnStore->VNPUnpackExc(curSideEff->gtVNPair, &op2vnp, &op2Xvnp);
2108                     exceptions_vnp = vnStore->VNPExcSetUnion(exceptions_vnp, op2Xvnp);
2109
2110                     op2Xvnp = ValueNumStore::VNPForEmptyExcSet();
2111                     vnStore->VNPUnpackExc(cseVal->gtVNPair, &op2vnp, &op2Xvnp);
2112                     exceptions_vnp = vnStore->VNPExcSetUnion(exceptions_vnp, op2Xvnp);
2113
2114                     /* Create a comma node with the sideEffList as op1 */
2115                     cse           = m_pCompiler->gtNewOperNode(GT_COMMA, expTyp, sideEffList, cseVal);
2116                     cse->gtVNPair = vnStore->VNPWithExc(op2vnp, exceptions_vnp);
2117                 }
2118
2119                 exp->gtCSEnum = NO_CSE; // clear the gtCSEnum field
2120
2121                 /* Unmark any nested CSE's in the sub-operands */
2122
2123                 // But we do need to communicate the side effect list to optUnmarkCSEs
2124                 // as any part of the 'exp' tree that is in the sideEffList is preserved
2125                 // and is not deleted and does not have its ref counts decremented
2126                 //
2127                 m_pCompiler->optValnumCSE_UnmarkCSEs(exp, sideEffList);
2128             }
2129             else
2130             {
2131                 /* This is a def of the CSE */
2132                 isDef = true;
2133 #ifdef DEBUG
2134                 if (m_pCompiler->verbose)
2135                 {
2136                     printf("\nCSE #%02u def at ", GET_CSE_INDEX(exp->gtCSEnum));
2137                     Compiler::printTreeID(exp);
2138                     printf(" replaced in BB%02u with def of V%02u\n", blk->bbNum, cseLclVarNum);
2139                 }
2140 #endif // DEBUG
2141
2142                 exp->gtCSEnum = NO_CSE; // clear the gtCSEnum field
2143
2144                 GenTreePtr val = exp;
2145
2146                 /* Create an assignment of the value to the temp */
2147                 GenTreePtr asg = m_pCompiler->gtNewTempAssign(cseLclVarNum, val);
2148
2149                 // assign the proper Value Numbers
2150                 asg->gtVNPair.SetBoth(ValueNumStore::VNForVoid()); // The GT_ASG node itself is $VN.Void
2151                 asg->gtOp.gtOp1->gtVNPair = val->gtVNPair;         // The dest op is the same as 'val'
2152
2153                 noway_assert(asg->gtOp.gtOp1->gtOper == GT_LCL_VAR);
2154                 noway_assert(asg->gtOp.gtOp2 == val);
2155
2156                 /* Create a reference to the CSE temp */
2157                 GenTreePtr ref = m_pCompiler->gtNewLclvNode(cseLclVarNum, cseLclVarTyp);
2158                 ref->gtVNPair  = val->gtVNPair; // The new 'ref' is the same as 'val'
2159
2160                 // If it has a zero-offset field seq, copy annotation to the ref
2161                 if (hasZeroMapAnnotation)
2162                 {
2163                     m_pCompiler->GetZeroOffsetFieldMap()->Set(ref, fldSeq);
2164                 }
2165
2166                 /* Create a comma node for the CSE assignment */
2167                 cse           = m_pCompiler->gtNewOperNode(GT_COMMA, expTyp, asg, ref);
2168                 cse->gtVNPair = ref->gtVNPair; // The comma's value is the same as 'val'
2169                                                // as the assignment to the CSE LclVar
2170                                                // cannot add any new exceptions
2171             }
2172
2173             // Increment ref count for the CSE ref
2174             m_pCompiler->lvaTable[cseLclVarNum].incRefCnts(blk->getBBWeight(m_pCompiler), m_pCompiler);
2175
2176             if (isDef)
2177             {
2178                 // Also increment ref count for the CSE assignment
2179                 m_pCompiler->lvaTable[cseLclVarNum].incRefCnts(blk->getBBWeight(m_pCompiler), m_pCompiler);
2180             }
2181
2182             // Walk the statement 'stm' and find the pointer
2183             // in the tree is pointing to 'exp'
2184             //
2185             GenTreePtr* link = m_pCompiler->gtFindLink(stm, exp);
2186
2187 #ifdef DEBUG
2188             if (link == nullptr)
2189             {
2190                 printf("\ngtFindLink failed: stm=");
2191                 Compiler::printTreeID(stm);
2192                 printf(", exp=");
2193                 Compiler::printTreeID(exp);
2194                 printf("\n");
2195                 printf("stm =");
2196                 m_pCompiler->gtDispTree(stm);
2197                 printf("\n");
2198                 printf("exp =");
2199                 m_pCompiler->gtDispTree(exp);
2200                 printf("\n");
2201             }
2202 #endif // DEBUG
2203
2204             noway_assert(link);
2205
2206             // Mutate this link, thus replacing the old exp with the new cse representation
2207             //
2208             *link = cse;
2209
2210             // If it has a zero-offset field seq, copy annotation.
2211             if (hasZeroMapAnnotation)
2212             {
2213                 m_pCompiler->GetZeroOffsetFieldMap()->Set(cse, fldSeq);
2214             }
2215
2216             assert(m_pCompiler->fgRemoveRestOfBlock == false);
2217
2218             /* re-morph the statement */
2219             m_pCompiler->fgMorphBlockStmt(blk, stm->AsStmt() DEBUGARG("optValnumCSE"));
2220
2221         } while (lst != nullptr);
2222     }
2223
2224     // Consider each of the CSE candidates and if the CSE passes
2225     // the PromotionCheck then transform the CSE by calling PerformCSE
2226     //
2227     void ConsiderCandidates()
2228     {
2229         /* Consider each CSE candidate, in order of decreasing cost */
2230         unsigned           cnt = m_pCompiler->optCSECandidateCount;
2231         Compiler::CSEdsc** ptr = sortTab;
2232         for (; (cnt > 0); cnt--, ptr++)
2233         {
2234             Compiler::CSEdsc* dsc = *ptr;
2235             CSE_Candidate     candidate(this, dsc);
2236
2237             candidate.InitializeCounts();
2238
2239             if (candidate.UseCount() == 0)
2240             {
2241 #ifdef DEBUG
2242                 if (m_pCompiler->verbose)
2243                 {
2244                     printf("Skipped CSE #%02u because use count is 0\n", candidate.CseIndex());
2245                 }
2246 #endif
2247                 continue;
2248             }
2249
2250 #ifdef DEBUG
2251             if (m_pCompiler->verbose)
2252             {
2253                 printf("\nConsidering CSE #%02u [def=%2u, use=%2u, cost=%2u] CSE Expression:\n", candidate.CseIndex(),
2254                        candidate.DefCount(), candidate.UseCount(), candidate.Cost());
2255                 m_pCompiler->gtDispTree(candidate.Expr());
2256                 printf("\n");
2257             }
2258 #endif
2259
2260             if ((dsc->csdDefCount <= 0) || (dsc->csdUseCount == 0))
2261             {
2262                 // If we reach this point, then the CSE def was incorrectly marked or the
2263                 // block with this use is unreachable. So skip and go to the next CSE.
2264                 // Without the "continue", we'd generate bad code in retail.
2265                 // Commented out a noway_assert(false) here due to bug: 3290124.
2266                 // The problem is if there is sub-graph that is not reachable from the
2267                 // entry point, the CSE flags propagated, would be incorrect for it.
2268                 continue;
2269             }
2270
2271             bool doCSE = PromotionCheck(&candidate);
2272
2273 #ifdef DEBUG
2274             if (m_pCompiler->verbose)
2275             {
2276                 if (doCSE)
2277                 {
2278                     printf("\nPromoting CSE:\n");
2279                 }
2280                 else
2281                 {
2282                     printf("Did Not promote this CSE\n");
2283                 }
2284             }
2285 #endif // DEBUG
2286
2287             if (doCSE)
2288             {
2289                 PerformCSE(&candidate);
2290             }
2291         }
2292     }
2293
2294     // Perform the necessary cleanup after our CSE heuristics have run
2295     //
2296     void Cleanup()
2297     {
2298         if (m_addCSEcount > 0)
2299         {
2300             /* We've added new local variables to the lvaTable so note that we need to recreate the sorted table */
2301             m_pCompiler->lvaSortAgain = true;
2302         }
2303     }
2304 };
2305
2306 /*****************************************************************************
2307  *
2308  *  Routine for performing the Value Number based CSE using our heuristics
2309  */
2310
2311 void Compiler::optValnumCSE_Heuristic()
2312 {
2313 #ifdef DEBUG
2314     if (verbose)
2315     {
2316         printf("\n************ Trees at start of optValnumCSE_Heuristic()\n");
2317         fgDumpTrees(fgFirstBB, nullptr);
2318         printf("\n");
2319     }
2320 #endif // DEBUG
2321
2322     CSE_Heuristic cse_heuristic(this);
2323
2324     cse_heuristic.Initialize();
2325     cse_heuristic.SortCandidates();
2326     cse_heuristic.ConsiderCandidates();
2327     cse_heuristic.Cleanup();
2328 }
2329
2330 /*****************************************************************************
2331  *
2332  *  Routine to unmark any CSEs contained within a tree
2333  *   - optionally a 'keepList' vcan be provided to specify a list of trees that will be kept
2334  *
2335  */
2336
2337 void Compiler::optValnumCSE_UnmarkCSEs(GenTreePtr deadTree, GenTreePtr keepList)
2338 {
2339     assert(optValnumCSE_phase);
2340
2341     // We need to communicate the 'keepList' to optUnmarkCSEs
2342     // as any part of the 'deadTree' tree that is in the keepList is preserved
2343     // and is not deleted and does not have its ref counts decremented
2344     // We communicate this value using the walkData.pCallbackData field
2345     //
2346
2347     fgWalkTreePre(&deadTree, optUnmarkCSEs, (void*)keepList);
2348 }
2349
2350 /*****************************************************************************
2351  *
2352  *  Perform common sub-expression elimination.
2353  */
2354
2355 void Compiler::optOptimizeValnumCSEs()
2356 {
2357 #ifdef DEBUG
2358     if (verbose)
2359     {
2360         printf("\n*************** In optOptimizeValnumCSEs()\n");
2361     }
2362
2363     if (optConfigDisableCSE())
2364     {
2365         return; // Disabled by JitNoCSE
2366     }
2367 #endif
2368
2369     optValnumCSE_phase = true;
2370
2371     /* Initialize the expression tracking logic */
2372
2373     optValnumCSE_Init();
2374
2375     /* Locate interesting expressions and assign indices to them */
2376
2377     if (optValnumCSE_Locate() > 0)
2378     {
2379         optCSECandidateTotal += optCSECandidateCount;
2380
2381         optValnumCSE_InitDataFlow();
2382
2383         optValnumCSE_DataFlow();
2384
2385         optValnumCSE_Availablity();
2386
2387         optValnumCSE_Heuristic();
2388     }
2389
2390     optValnumCSE_phase = false;
2391 }
2392
2393 #endif // FEATURE_VALNUM_CSE
2394
2395 /*****************************************************************************
2396  *
2397  *  The following determines whether the given expression is a worthy CSE
2398  *  candidate.
2399  */
2400 bool Compiler::optIsCSEcandidate(GenTreePtr tree)
2401 {
2402     /* No good if the expression contains side effects or if it was marked as DONT CSE */
2403
2404     if (tree->gtFlags & (GTF_ASG | GTF_DONT_CSE))
2405     {
2406         return false;
2407     }
2408
2409     /* The only reason a TYP_STRUCT tree might occur is as an argument to
2410        GT_ADDR. It will never be actually materialized. So ignore them.
2411        Also TYP_VOIDs */
2412
2413     var_types  type = tree->TypeGet();
2414     genTreeOps oper = tree->OperGet();
2415
2416     // TODO-1stClassStructs: Enable CSE for struct types (depends on either transforming
2417     // to use regular assignments, or handling copyObj.
2418     if (varTypeIsStruct(type) || type == TYP_VOID)
2419     {
2420         return false;
2421     }
2422
2423 #ifdef _TARGET_X86_
2424     if (type == TYP_FLOAT)
2425     {
2426         // TODO-X86-CQ: Revisit this
2427         // Don't CSE a TYP_FLOAT on x86 as we currently can only enregister doubles
2428         return false;
2429     }
2430 #else
2431     if (oper == GT_CNS_DBL)
2432     {
2433         // TODO-CQ: Revisit this
2434         // Don't try to CSE a GT_CNS_DBL as they can represent both float and doubles
2435         return false;
2436     }
2437 #endif
2438
2439     unsigned cost;
2440     if (compCodeOpt() == SMALL_CODE)
2441     {
2442         cost = tree->gtCostSz;
2443     }
2444     else
2445     {
2446         cost = tree->gtCostEx;
2447     }
2448
2449     /* Don't bother if the potential savings are very low */
2450     if (cost < MIN_CSE_COST)
2451     {
2452         return false;
2453     }
2454
2455 #if !CSE_CONSTS
2456     /* Don't bother with constants */
2457     if (tree->OperKind() & GTK_CONST)
2458         return false;
2459 #endif
2460
2461     /* Check for some special cases */
2462
2463     switch (oper)
2464     {
2465         case GT_CALL:
2466             // If we have a simple helper call with no other persistent side-effects
2467             // then we allow this tree to be a CSE candidate
2468             //
2469             if (gtTreeHasSideEffects(tree, GTF_PERSISTENT_SIDE_EFFECTS_IN_CSE) == false)
2470             {
2471                 return true;
2472             }
2473             else
2474             {
2475                 // Calls generally cannot be CSE-ed
2476                 return false;
2477             }
2478
2479         case GT_IND:
2480             // TODO-CQ: Review this...
2481             /* We try to cse GT_ARR_ELEM nodes instead of GT_IND(GT_ARR_ELEM).
2482                 Doing the first allows cse to also kick in for code like
2483                 "GT_IND(GT_ARR_ELEM) = GT_IND(GT_ARR_ELEM) + xyz", whereas doing
2484                 the second would not allow it */
2485
2486             return (tree->gtOp.gtOp1->gtOper != GT_ARR_ELEM);
2487
2488         case GT_CNS_INT:
2489         case GT_CNS_LNG:
2490         case GT_CNS_DBL:
2491         case GT_CNS_STR:
2492             return true; // We reach here only when CSE_CONSTS is enabled
2493
2494         case GT_ARR_ELEM:
2495         case GT_ARR_LENGTH:
2496         case GT_CLS_VAR:
2497         case GT_LCL_FLD:
2498             return true;
2499
2500         case GT_LCL_VAR:
2501             return false; // Can't CSE a volatile LCL_VAR
2502
2503         case GT_NEG:
2504         case GT_NOT:
2505         case GT_CAST:
2506             return true; // CSE these Unary Operators
2507
2508         case GT_SUB:
2509         case GT_DIV:
2510         case GT_MOD:
2511         case GT_UDIV:
2512         case GT_UMOD:
2513         case GT_OR:
2514         case GT_AND:
2515         case GT_XOR:
2516         case GT_RSH:
2517         case GT_RSZ:
2518         case GT_ROL:
2519         case GT_ROR:
2520             return true; // CSE these Binary Operators
2521
2522         case GT_ADD: // Check for ADDRMODE flag on these Binary Operators
2523         case GT_MUL:
2524         case GT_LSH:
2525             if ((tree->gtFlags & GTF_ADDRMODE_NO_CSE) != 0)
2526             {
2527                 return false;
2528             }
2529
2530         case GT_EQ:
2531         case GT_NE:
2532         case GT_LT:
2533         case GT_LE:
2534         case GT_GE:
2535         case GT_GT:
2536             return true; // Also CSE these Comparison Operators
2537
2538         case GT_INTRINSIC:
2539             return true; // Intrinsics
2540
2541         case GT_COMMA:
2542             return true; // Allow GT_COMMA nodes to be CSE-ed.
2543
2544         case GT_COLON:
2545         case GT_QMARK:
2546         case GT_NOP:
2547         case GT_RETURN:
2548             return false; // Currently the only special nodes that we hit
2549                           // that we know that we don't want to CSE
2550
2551         default:
2552             break; // Any new nodes that we might add later...
2553     }
2554
2555     return false;
2556 }
2557
2558 #ifdef DEBUG
2559 //
2560 // A Debug only method that allows you to control whether the CSE logic is enabled for this method.
2561 //
2562 // If this method returns false then the CSE phase should be performed.
2563 // If the method returns true then the CSE phase should be skipped.
2564 //
2565 bool Compiler::optConfigDisableCSE()
2566 {
2567     // Next check if COMPlus_JitNoCSE is set and applies to this method
2568     //
2569     unsigned jitNoCSE = JitConfig.JitNoCSE();
2570
2571     if (jitNoCSE > 0)
2572     {
2573         unsigned methodCount = Compiler::jitTotalMethodCompiled;
2574         if ((jitNoCSE & 0xF000000) == 0xF000000)
2575         {
2576             unsigned methodCountMask = methodCount & 0xFFF;
2577             unsigned bitsZero        = (jitNoCSE >> 12) & 0xFFF;
2578             unsigned bitsOne         = (jitNoCSE >> 0) & 0xFFF;
2579
2580             if (((methodCountMask & bitsOne) == bitsOne) && ((~methodCountMask & bitsZero) == bitsZero))
2581             {
2582                 if (verbose)
2583                 {
2584                     printf(" Disabled by JitNoCSE methodCountMask\n");
2585                 }
2586
2587                 return true; // The CSE phase for this method is disabled
2588             }
2589         }
2590         else if (jitNoCSE <= (methodCount + 1))
2591         {
2592             if (verbose)
2593             {
2594                 printf(" Disabled by JitNoCSE > methodCount\n");
2595             }
2596
2597             return true; // The CSE phase for this method is disabled
2598         }
2599     }
2600
2601     return false;
2602 }
2603
2604 //
2605 // A Debug only method that allows you to control whether the CSE logic is enabled for
2606 // a particular CSE in a method
2607 //
2608 // If this method returns false then the CSE should be performed.
2609 // If the method returns true then the CSE should be skipped.
2610 //
2611 bool Compiler::optConfigDisableCSE2()
2612 {
2613     static unsigned totalCSEcount = 0;
2614
2615     unsigned jitNoCSE2 = JitConfig.JitNoCSE2();
2616
2617     totalCSEcount++;
2618
2619     if (jitNoCSE2 > 0)
2620     {
2621         if ((jitNoCSE2 & 0xF000000) == 0xF000000)
2622         {
2623             unsigned totalCSEMask = totalCSEcount & 0xFFF;
2624             unsigned bitsZero     = (jitNoCSE2 >> 12) & 0xFFF;
2625             unsigned bitsOne      = (jitNoCSE2 >> 0) & 0xFFF;
2626
2627             if (((totalCSEMask & bitsOne) == bitsOne) && ((~totalCSEMask & bitsZero) == bitsZero))
2628             {
2629                 if (verbose)
2630                 {
2631                     printf(" Disabled by jitNoCSE2 Ones/Zeros mask\n");
2632                 }
2633                 return true;
2634             }
2635         }
2636         else if ((jitNoCSE2 & 0xF000000) == 0xE000000)
2637         {
2638             unsigned totalCSEMask = totalCSEcount & 0xFFF;
2639             unsigned disableMask  = jitNoCSE2 & 0xFFF;
2640
2641             disableMask >>= (totalCSEMask % 12);
2642
2643             if (disableMask & 1)
2644             {
2645                 if (verbose)
2646                 {
2647                     printf(" Disabled by jitNoCSE2 rotating disable mask\n");
2648                 }
2649                 return true;
2650             }
2651         }
2652         else if (jitNoCSE2 <= totalCSEcount)
2653         {
2654             if (verbose)
2655             {
2656                 printf(" Disabled by jitNoCSE2 > totalCSEcount\n");
2657             }
2658             return true;
2659         }
2660     }
2661     return false;
2662 }
2663 #endif
2664
2665 void Compiler::optOptimizeCSEs()
2666 {
2667 #ifdef DEBUG
2668     if (verbose)
2669     {
2670         printf("\n*************** In optOptimizeCSEs()\n");
2671         printf("Blocks/Trees at start of optOptimizeCSE phase\n");
2672         fgDispBasicBlocks(true);
2673     }
2674 #endif // DEBUG
2675
2676     optCSECandidateCount = 0;
2677     optCSEstart          = lvaCount;
2678
2679 #if FEATURE_VALNUM_CSE
2680     INDEBUG(optEnsureClearCSEInfo());
2681     optOptimizeValnumCSEs();
2682     EndPhase(PHASE_OPTIMIZE_VALNUM_CSES);
2683 #endif // FEATURE_VALNUM_CSE
2684 }
2685
2686 /*****************************************************************************
2687  *
2688  *  Cleanup after CSE to allow us to run more than once.
2689  */
2690
2691 void Compiler::optCleanupCSEs()
2692 {
2693     // We must clear the BBF_VISITED and BBF_MARKED flags
2694     //
2695     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
2696     {
2697         // And clear all the "visited" bits on the block
2698         //
2699         block->bbFlags &= ~(BBF_VISITED | BBF_MARKED);
2700
2701         /* Walk the statement trees in this basic block */
2702
2703         GenTreePtr stmt;
2704
2705         // Initialize 'stmt' to the first non-Phi statement
2706         stmt = block->FirstNonPhiDef();
2707
2708         for (; stmt; stmt = stmt->gtNext)
2709         {
2710             noway_assert(stmt->gtOper == GT_STMT);
2711
2712             /* We must clear the gtCSEnum field */
2713             for (GenTreePtr tree = stmt->gtStmt.gtStmtExpr; tree; tree = tree->gtPrev)
2714             {
2715                 tree->gtCSEnum = NO_CSE;
2716             }
2717         }
2718     }
2719 }
2720
2721 #ifdef DEBUG
2722
2723 /*****************************************************************************
2724  *
2725  *  Ensure that all the CSE information in the IR is initialized the way we expect it,
2726  *  before running a CSE phase. This is basically an assert that optCleanupCSEs() is not needed.
2727  */
2728
2729 void Compiler::optEnsureClearCSEInfo()
2730 {
2731     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
2732     {
2733         assert((block->bbFlags & (BBF_VISITED | BBF_MARKED)) == 0);
2734
2735         /* Walk the statement trees in this basic block */
2736
2737         GenTreePtr stmt;
2738
2739         // Initialize 'stmt' to the first non-Phi statement
2740         stmt = block->FirstNonPhiDef();
2741
2742         for (; stmt; stmt = stmt->gtNext)
2743         {
2744             assert(stmt->gtOper == GT_STMT);
2745
2746             for (GenTreePtr tree = stmt->gtStmt.gtStmtExpr; tree; tree = tree->gtPrev)
2747             {
2748                 assert(tree->gtCSEnum == NO_CSE);
2749             }
2750         }
2751     }
2752 }
2753
2754 #endif // DEBUG
2755
2756 /*****************************************************************************/
2757 #endif // FEATURE_ANYCSE
2758 /*****************************************************************************/