src/jit/liveness.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 // =================================================================================
   6 //  Code that works with liveness and related concepts (interference, debug scope)
   7 // =================================================================================
   8
   9 #include "jitpch.h"
  10 #ifdef _MSC_VER
  11 #pragma hdrstop
  12 #endif
  13
  14 #if !defined(_TARGET_64BIT_)
  15 #include "decomposelongs.h"
  16 #endif
  17 #include "lower.h" // for LowerRange()
  18
  19 /*****************************************************************************
  20  *
  21  *  Helper for Compiler::fgPerBlockLocalVarLiveness().
  22  *  The goal is to compute the USE and DEF sets for a basic block.
  23  */
  24 void Compiler::fgMarkUseDef(GenTreeLclVarCommon* tree)
  25 {
  26     assert((tree->OperIsLocal() && (tree->OperGet() != GT_PHI_ARG)) || tree->OperIsLocalAddr());
  27
  28     const unsigned lclNum = tree->gtLclNum;
  29     assert(lclNum < lvaCount);
  30
  31     LclVarDsc* const varDsc = &lvaTable[lclNum];
  32
  33     // We should never encounter a reference to a lclVar that has a zero refCnt.
  34     if (varDsc->lvRefCnt() == 0 && (!varTypeIsPromotable(varDsc) || !varDsc->lvPromoted))
  35     {
  36         JITDUMP("Found reference to V%02u with zero refCnt.\n", lclNum);
  37         assert(!"We should never encounter a reference to a lclVar that has a zero refCnt.");
  38         varDsc->setLvRefCnt(1);
  39     }
  40
  41     const bool isDef = (tree->gtFlags & GTF_VAR_DEF) != 0;
  42     const bool isUse = !isDef || ((tree->gtFlags & GTF_VAR_USEASG) != 0);
  43
  44     if (varDsc->lvTracked)
  45     {
  46         assert(varDsc->lvVarIndex < lvaTrackedCount);
  47
  48         // We don't treat stores to tracked locals as modifications of ByrefExposed memory;
  49         // Make sure no tracked local is addr-exposed, to make sure we don't incorrectly CSE byref
  50         // loads aliasing it across a store to it.
  51         assert(!varDsc->lvAddrExposed);
  52
  53         if (isUse && !VarSetOps::IsMember(this, fgCurDefSet, varDsc->lvVarIndex))
  54         {
  55             // This is an exposed use; add it to the set of uses.
  56             VarSetOps::AddElemD(this, fgCurUseSet, varDsc->lvVarIndex);
  57         }
  58
  59         if (isDef)
  60         {
  61             // This is a def, add it to the set of defs.
  62             VarSetOps::AddElemD(this, fgCurDefSet, varDsc->lvVarIndex);
  63         }
  64     }
  65     else
  66     {
  67         if (varDsc->lvAddrExposed)
  68         {
  69             // Reflect the effect on ByrefExposed memory
  70
  71             if (isUse)
  72             {
  73                 fgCurMemoryUse |= memoryKindSet(ByrefExposed);
  74             }
  75             if (isDef)
  76             {
  77                 fgCurMemoryDef |= memoryKindSet(ByrefExposed);
  78
  79                 // We've found a store that modifies ByrefExposed
  80                 // memory but not GcHeap memory, so track their
  81                 // states separately.
  82                 byrefStatesMatchGcHeapStates = false;
  83             }
  84         }
  85
  86         if (varTypeIsStruct(varDsc))
  87         {
  88             lvaPromotionType promotionType = lvaGetPromotionType(varDsc);
  89
  90             if (promotionType != PROMOTION_TYPE_NONE)
  91             {
  92                 VARSET_TP bitMask(VarSetOps::MakeEmpty(this));
  93
  94                 for (unsigned i = varDsc->lvFieldLclStart; i < varDsc->lvFieldLclStart + varDsc->lvFieldCnt; ++i)
  95                 {
  96                     noway_assert(lvaTable[i].lvIsStructField);
  97                     if (lvaTable[i].lvTracked)
  98                     {
  99                         noway_assert(lvaTable[i].lvVarIndex < lvaTrackedCount);
 100                         VarSetOps::AddElemD(this, bitMask, lvaTable[i].lvVarIndex);
 101                     }
 102                 }
 103
 104                 // For pure defs (i.e. not an "update" def which is also a use), add to the (all) def set.
 105                 if (!isUse)
 106                 {
 107                     assert(isDef);
 108                     VarSetOps::UnionD(this, fgCurDefSet, bitMask);
 109                 }
 110                 else if (!VarSetOps::IsSubset(this, bitMask, fgCurDefSet))
 111                 {
 112                     // Mark as used any struct fields that are not yet defined.
 113                     VarSetOps::UnionD(this, fgCurUseSet, bitMask);
 114                 }
 115             }
 116         }
 117     }
 118 }
 119
 120 /*****************************************************************************/
 121 void Compiler::fgLocalVarLiveness()
 122 {
 123 #ifdef DEBUG
 124     if (verbose)
 125     {
 126         printf("*************** In fgLocalVarLiveness()\n");
 127
 128         if (compRationalIRForm)
 129         {
 130             lvaTableDump();
 131         }
 132     }
 133 #endif // DEBUG
 134
 135     // Init liveness data structures.
 136     fgLocalVarLivenessInit();
 137
 138     EndPhase(PHASE_LCLVARLIVENESS_INIT);
 139
 140     // Make sure we haven't noted any partial last uses of promoted structs.
 141     ClearPromotedStructDeathVars();
 142
 143     // Initialize the per-block var sets.
 144     fgInitBlockVarSets();
 145
 146     fgLocalVarLivenessChanged = false;
 147     do
 148     {
 149         /* Figure out use/def info for all basic blocks */
 150         fgPerBlockLocalVarLiveness();
 151         EndPhase(PHASE_LCLVARLIVENESS_PERBLOCK);
 152
 153         /* Live variable analysis. */
 154
 155         fgStmtRemoved = false;
 156         fgInterBlockLocalVarLiveness();
 157     } while (fgStmtRemoved && fgLocalVarLivenessChanged);
 158
 159     EndPhase(PHASE_LCLVARLIVENESS_INTERBLOCK);
 160 }
 161
 162 /*****************************************************************************/
 163 void Compiler::fgLocalVarLivenessInit()
 164 {
 165     JITDUMP("In fgLocalVarLivenessInit\n");
 166
 167     // Sort locals first, if we're optimizing
 168     if (opts.OptimizationEnabled())
 169     {
 170         lvaSortByRefCount();
 171     }
 172
 173     // We mark a lcl as must-init in a first pass of local variable
 174     // liveness (Liveness1), then assertion prop eliminates the
 175     // uninit-use of a variable Vk, asserting it will be init'ed to
 176     // null.  Then, in a second local-var liveness (Liveness2), the
 177     // variable Vk is no longer live on entry to the method, since its
 178     // uses have been replaced via constant propagation.
 179     //
 180     // This leads to a bug: since Vk is no longer live on entry, the
 181     // register allocator sees Vk and an argument Vj as having
 182     // disjoint lifetimes, and allocates them to the same register.
 183     // But Vk is still marked "must-init", and this initialization (of
 184     // the register) trashes the value in Vj.
 185     //
 186     // Therefore, initialize must-init to false for all variables in
 187     // each liveness phase.
 188     for (unsigned lclNum = 0; lclNum < lvaCount; ++lclNum)
 189     {
 190         lvaTable[lclNum].lvMustInit = false;
 191     }
 192 }
 193
 194 //------------------------------------------------------------------------
 195 // fgPerNodeLocalVarLiveness:
 196 //   Set fgCurMemoryUse and fgCurMemoryDef when memory is read or updated
 197 //   Call fgMarkUseDef for any Local variables encountered
 198 //
 199 // Arguments:
 200 //    tree       - The current node.
 201 //
 202 void Compiler::fgPerNodeLocalVarLiveness(GenTree* tree)
 203 {
 204     assert(tree != nullptr);
 205
 206     switch (tree->gtOper)
 207     {
 208         case GT_QMARK:
 209         case GT_COLON:
 210             // We never should encounter a GT_QMARK or GT_COLON node
 211             noway_assert(!"unexpected GT_QMARK/GT_COLON");
 212             break;
 213
 214         case GT_LCL_VAR:
 215         case GT_LCL_FLD:
 216         case GT_LCL_VAR_ADDR:
 217         case GT_LCL_FLD_ADDR:
 218         case GT_STORE_LCL_VAR:
 219         case GT_STORE_LCL_FLD:
 220             fgMarkUseDef(tree->AsLclVarCommon());
 221             break;
 222
 223         case GT_CLS_VAR:
 224             // For Volatile indirection, first mutate GcHeap/ByrefExposed.
 225             // See comments in ValueNum.cpp (under case GT_CLS_VAR)
 226             // This models Volatile reads as def-then-use of memory
 227             // and allows for a CSE of a subsequent non-volatile read.
 228             if ((tree->gtFlags & GTF_FLD_VOLATILE) != 0)
 229             {
 230                 // For any Volatile indirection, we must handle it as a
 231                 // definition of GcHeap/ByrefExposed
 232                 fgCurMemoryDef |= memoryKindSet(GcHeap, ByrefExposed);
 233             }
 234             // If the GT_CLS_VAR is the lhs of an assignment, we'll handle it as a GcHeap/ByrefExposed def, when we get
 235             // to the assignment.
 236             // Otherwise, we treat it as a use here.
 237             if ((tree->gtFlags & GTF_CLS_VAR_ASG_LHS) == 0)
 238             {
 239                 fgCurMemoryUse |= memoryKindSet(GcHeap, ByrefExposed);
 240             }
 241             break;
 242
 243         case GT_IND:
 244             // For Volatile indirection, first mutate GcHeap/ByrefExposed
 245             // see comments in ValueNum.cpp (under case GT_CLS_VAR)
 246             // This models Volatile reads as def-then-use of memory.
 247             // and allows for a CSE of a subsequent non-volatile read
 248             if ((tree->gtFlags & GTF_IND_VOLATILE) != 0)
 249             {
 250                 // For any Volatile indirection, we must handle it as a
 251                 // definition of the GcHeap/ByrefExposed
 252                 fgCurMemoryDef |= memoryKindSet(GcHeap, ByrefExposed);
 253             }
 254
 255             // If the GT_IND is the lhs of an assignment, we'll handle it
 256             // as a memory def, when we get to assignment.
 257             // Otherwise, we treat it as a use here.
 258             if ((tree->gtFlags & GTF_IND_ASG_LHS) == 0)
 259             {
 260                 GenTreeLclVarCommon* dummyLclVarTree = nullptr;
 261                 bool                 dummyIsEntire   = false;
 262                 GenTree*             addrArg         = tree->gtOp.gtOp1->gtEffectiveVal(/*commaOnly*/ true);
 263                 if (!addrArg->DefinesLocalAddr(this, /*width doesn't matter*/ 0, &dummyLclVarTree, &dummyIsEntire))
 264                 {
 265                     fgCurMemoryUse |= memoryKindSet(GcHeap, ByrefExposed);
 266                 }
 267                 else
 268                 {
 269                     // Defines a local addr
 270                     assert(dummyLclVarTree != nullptr);
 271                     fgMarkUseDef(dummyLclVarTree->AsLclVarCommon());
 272                 }
 273             }
 274             break;
 275
 276         // These should have been morphed away to become GT_INDs:
 277         case GT_FIELD:
 278         case GT_INDEX:
 279             unreached();
 280             break;
 281
 282         // We'll assume these are use-then-defs of memory.
 283         case GT_LOCKADD:
 284         case GT_XADD:
 285         case GT_XCHG:
 286         case GT_CMPXCHG:
 287             fgCurMemoryUse |= memoryKindSet(GcHeap, ByrefExposed);
 288             fgCurMemoryDef |= memoryKindSet(GcHeap, ByrefExposed);
 289             fgCurMemoryHavoc |= memoryKindSet(GcHeap, ByrefExposed);
 290             break;
 291
 292         case GT_MEMORYBARRIER:
 293             // Simliar to any Volatile indirection, we must handle this as a definition of GcHeap/ByrefExposed
 294             fgCurMemoryDef |= memoryKindSet(GcHeap, ByrefExposed);
 295             break;
 296
 297 #ifdef FEATURE_HW_INTRINSICS
 298         case GT_HWIntrinsic:
 299         {
 300             GenTreeHWIntrinsic* hwIntrinsicNode = tree->AsHWIntrinsic();
 301
 302             // We can't call fgMutateGcHeap unless the block has recorded a MemoryDef
 303             //
 304             if (hwIntrinsicNode->OperIsMemoryStore())
 305             {
 306                 // We currently handle this like a Volatile store, so it counts as a definition of GcHeap/ByrefExposed
 307                 fgCurMemoryDef |= memoryKindSet(GcHeap, ByrefExposed);
 308             }
 309             if (hwIntrinsicNode->OperIsMemoryLoad())
 310             {
 311                 // This instruction loads from memory and we need to record this information
 312                 fgCurMemoryUse |= memoryKindSet(GcHeap, ByrefExposed);
 313             }
 314             break;
 315         }
 316 #endif
 317
 318         // For now, all calls read/write GcHeap/ByrefExposed, writes in their entirety.  Might tighten this case later.
 319         case GT_CALL:
 320         {
 321             GenTreeCall* call    = tree->AsCall();
 322             bool         modHeap = true;
 323             if (call->gtCallType == CT_HELPER)
 324             {
 325                 CorInfoHelpFunc helpFunc = eeGetHelperNum(call->gtCallMethHnd);
 326
 327                 if (!s_helperCallProperties.MutatesHeap(helpFunc) && !s_helperCallProperties.MayRunCctor(helpFunc))
 328                 {
 329                     modHeap = false;
 330                 }
 331             }
 332             if (modHeap)
 333             {
 334                 fgCurMemoryUse |= memoryKindSet(GcHeap, ByrefExposed);
 335                 fgCurMemoryDef |= memoryKindSet(GcHeap, ByrefExposed);
 336                 fgCurMemoryHavoc |= memoryKindSet(GcHeap, ByrefExposed);
 337             }
 338         }
 339
 340             // If this is a p/invoke unmanaged call or if this is a tail-call
 341             // and we have an unmanaged p/invoke call in the method,
 342             // then we're going to run the p/invoke epilog.
 343             // So we mark the FrameRoot as used by this instruction.
 344             // This ensures that the block->bbVarUse will contain
 345             // the FrameRoot local var if is it a tracked variable.
 346
 347             if ((tree->gtCall.IsUnmanaged() || (tree->gtCall.IsTailCall() && info.compCallUnmanaged)))
 348             {
 349                 assert((!opts.ShouldUsePInvokeHelpers()) || (info.compLvFrameListRoot == BAD_VAR_NUM));
 350                 if (!opts.ShouldUsePInvokeHelpers())
 351                 {
 352                     /* Get the TCB local and mark it as used */
 353
 354                     noway_assert(info.compLvFrameListRoot < lvaCount);
 355
 356                     LclVarDsc* varDsc = &lvaTable[info.compLvFrameListRoot];
 357
 358                     if (varDsc->lvTracked)
 359                     {
 360                         if (!VarSetOps::IsMember(this, fgCurDefSet, varDsc->lvVarIndex))
 361                         {
 362                             VarSetOps::AddElemD(this, fgCurUseSet, varDsc->lvVarIndex);
 363                         }
 364                     }
 365                 }
 366             }
 367
 368             break;
 369
 370         default:
 371
 372             // Determine what memory locations it defines.
 373             if (tree->OperIs(GT_ASG) || tree->OperIsBlkOp())
 374             {
 375                 GenTreeLclVarCommon* dummyLclVarTree = nullptr;
 376                 if (tree->DefinesLocal(this, &dummyLclVarTree))
 377                 {
 378                     if (lvaVarAddrExposed(dummyLclVarTree->gtLclNum))
 379                     {
 380                         fgCurMemoryDef |= memoryKindSet(ByrefExposed);
 381
 382                         // We've found a store that modifies ByrefExposed
 383                         // memory but not GcHeap memory, so track their
 384                         // states separately.
 385                         byrefStatesMatchGcHeapStates = false;
 386                     }
 387                 }
 388                 else
 389                 {
 390                     // If it doesn't define a local, then it might update GcHeap/ByrefExposed.
 391                     fgCurMemoryDef |= memoryKindSet(GcHeap, ByrefExposed);
 392                 }
 393             }
 394             break;
 395     }
 396 }
 397
 398 /*****************************************************************************/
 399 void Compiler::fgPerBlockLocalVarLiveness()
 400 {
 401 #ifdef DEBUG
 402     if (verbose)
 403     {
 404         printf("*************** In fgPerBlockLocalVarLiveness()\n");
 405     }
 406 #endif // DEBUG
 407
 408     unsigned livenessVarEpoch = GetCurLVEpoch();
 409
 410     BasicBlock* block;
 411
 412     // If we don't require accurate local var lifetimes, things are simple.
 413     if (!backendRequiresLocalVarLifetimes())
 414     {
 415         unsigned   lclNum;
 416         LclVarDsc* varDsc;
 417
 418         VARSET_TP liveAll(VarSetOps::MakeEmpty(this));
 419
 420         /* We simply make everything live everywhere */
 421
 422         for (lclNum = 0, varDsc = lvaTable; lclNum < lvaCount; lclNum++, varDsc++)
 423         {
 424             if (varDsc->lvTracked)
 425             {
 426                 VarSetOps::AddElemD(this, liveAll, varDsc->lvVarIndex);
 427             }
 428         }
 429
 430         for (block = fgFirstBB; block; block = block->bbNext)
 431         {
 432             // Strictly speaking, the assignments for the "Def" cases aren't necessary here.
 433             // The empty set would do as well.  Use means "use-before-def", so as long as that's
 434             // "all", this has the right effect.
 435             VarSetOps::Assign(this, block->bbVarUse, liveAll);
 436             VarSetOps::Assign(this, block->bbVarDef, liveAll);
 437             VarSetOps::Assign(this, block->bbLiveIn, liveAll);
 438             block->bbMemoryUse     = fullMemoryKindSet;
 439             block->bbMemoryDef     = fullMemoryKindSet;
 440             block->bbMemoryLiveIn  = fullMemoryKindSet;
 441             block->bbMemoryLiveOut = fullMemoryKindSet;
 442
 443             switch (block->bbJumpKind)
 444             {
 445                 case BBJ_EHFINALLYRET:
 446                 case BBJ_THROW:
 447                 case BBJ_RETURN:
 448                     VarSetOps::AssignNoCopy(this, block->bbLiveOut, VarSetOps::MakeEmpty(this));
 449                     break;
 450                 default:
 451                     VarSetOps::Assign(this, block->bbLiveOut, liveAll);
 452                     break;
 453             }
 454         }
 455
 456         // In minopts, we don't explicitly build SSA or value-number; GcHeap and
 457         // ByrefExposed implicitly (conservatively) change state at each instr.
 458         byrefStatesMatchGcHeapStates = true;
 459
 460         return;
 461     }
 462
 463     // Avoid allocations in the long case.
 464     VarSetOps::AssignNoCopy(this, fgCurUseSet, VarSetOps::MakeEmpty(this));
 465     VarSetOps::AssignNoCopy(this, fgCurDefSet, VarSetOps::MakeEmpty(this));
 466
 467     // GC Heap and ByrefExposed can share states unless we see a def of byref-exposed
 468     // memory that is not a GC Heap def.
 469     byrefStatesMatchGcHeapStates = true;
 470
 471     for (block = fgFirstBB; block; block = block->bbNext)
 472     {
 473         VarSetOps::ClearD(this, fgCurUseSet);
 474         VarSetOps::ClearD(this, fgCurDefSet);
 475
 476         fgCurMemoryUse   = emptyMemoryKindSet;
 477         fgCurMemoryDef   = emptyMemoryKindSet;
 478         fgCurMemoryHavoc = emptyMemoryKindSet;
 479
 480         compCurBB = block;
 481         if (block->IsLIR())
 482         {
 483             for (GenTree* node : LIR::AsRange(block).NonPhiNodes())
 484             {
 485                 fgPerNodeLocalVarLiveness(node);
 486             }
 487         }
 488         else
 489         {
 490             for (GenTreeStmt* stmt = block->FirstNonPhiDef(); stmt; stmt = stmt->gtNextStmt)
 491             {
 492                 compCurStmt = stmt;
 493                 for (GenTree* node = stmt->gtStmtList; node != nullptr; node = node->gtNext)
 494                 {
 495                     fgPerNodeLocalVarLiveness(node);
 496                 }
 497             }
 498         }
 499
 500         /* Get the TCB local and mark it as used */
 501
 502         if (block->bbJumpKind == BBJ_RETURN && info.compCallUnmanaged)
 503         {
 504             assert((!opts.ShouldUsePInvokeHelpers()) || (info.compLvFrameListRoot == BAD_VAR_NUM));
 505             if (!opts.ShouldUsePInvokeHelpers())
 506             {
 507                 noway_assert(info.compLvFrameListRoot < lvaCount);
 508
 509                 LclVarDsc* varDsc = &lvaTable[info.compLvFrameListRoot];
 510
 511                 if (varDsc->lvTracked)
 512                 {
 513                     if (!VarSetOps::IsMember(this, fgCurDefSet, varDsc->lvVarIndex))
 514                     {
 515                         VarSetOps::AddElemD(this, fgCurUseSet, varDsc->lvVarIndex);
 516                     }
 517                 }
 518             }
 519         }
 520
 521 #ifdef DEBUG
 522         if (verbose)
 523         {
 524             VARSET_TP allVars(VarSetOps::Union(this, fgCurUseSet, fgCurDefSet));
 525             printf(FMT_BB, block->bbNum);
 526             printf(" USE(%d)=", VarSetOps::Count(this, fgCurUseSet));
 527             lvaDispVarSet(fgCurUseSet, allVars);
 528             for (MemoryKind memoryKind : allMemoryKinds())
 529             {
 530                 if ((fgCurMemoryUse & memoryKindSet(memoryKind)) != 0)
 531                 {
 532                     printf(" + %s", memoryKindNames[memoryKind]);
 533                 }
 534             }
 535             printf("\n     DEF(%d)=", VarSetOps::Count(this, fgCurDefSet));
 536             lvaDispVarSet(fgCurDefSet, allVars);
 537             for (MemoryKind memoryKind : allMemoryKinds())
 538             {
 539                 if ((fgCurMemoryDef & memoryKindSet(memoryKind)) != 0)
 540                 {
 541                     printf(" + %s", memoryKindNames[memoryKind]);
 542                 }
 543                 if ((fgCurMemoryHavoc & memoryKindSet(memoryKind)) != 0)
 544                 {
 545                     printf("*");
 546                 }
 547             }
 548             printf("\n\n");
 549         }
 550 #endif // DEBUG
 551
 552         VarSetOps::Assign(this, block->bbVarUse, fgCurUseSet);
 553         VarSetOps::Assign(this, block->bbVarDef, fgCurDefSet);
 554         block->bbMemoryUse   = fgCurMemoryUse;
 555         block->bbMemoryDef   = fgCurMemoryDef;
 556         block->bbMemoryHavoc = fgCurMemoryHavoc;
 557
 558         /* also initialize the IN set, just in case we will do multiple DFAs */
 559
 560         VarSetOps::AssignNoCopy(this, block->bbLiveIn, VarSetOps::MakeEmpty(this));
 561         block->bbMemoryLiveIn = emptyMemoryKindSet;
 562     }
 563
 564     noway_assert(livenessVarEpoch == GetCurLVEpoch());
 565 #ifdef DEBUG
 566     if (verbose)
 567     {
 568         printf("** Memory liveness computed, GcHeap states and ByrefExposed states %s\n",
 569                (byrefStatesMatchGcHeapStates ? "match" : "diverge"));
 570     }
 571 #endif // DEBUG
 572 }
 573
 574 // Helper functions to mark variables live over their entire scope
 575
 576 void Compiler::fgBeginScopeLife(VARSET_TP* inScope, VarScopeDsc* var)
 577 {
 578     assert(var);
 579
 580     LclVarDsc* lclVarDsc1 = &lvaTable[var->vsdVarNum];
 581
 582     if (lclVarDsc1->lvTracked)
 583     {
 584         VarSetOps::AddElemD(this, *inScope, lclVarDsc1->lvVarIndex);
 585     }
 586 }
 587
 588 void Compiler::fgEndScopeLife(VARSET_TP* inScope, VarScopeDsc* var)
 589 {
 590     assert(var);
 591
 592     LclVarDsc* lclVarDsc1 = &lvaTable[var->vsdVarNum];
 593
 594     if (lclVarDsc1->lvTracked)
 595     {
 596         VarSetOps::RemoveElemD(this, *inScope, lclVarDsc1->lvVarIndex);
 597     }
 598 }
 599
 600 /*****************************************************************************/
 601
 602 void Compiler::fgMarkInScope(BasicBlock* block, VARSET_VALARG_TP inScope)
 603 {
 604 #ifdef DEBUG
 605     if (verbose)
 606     {
 607         printf("Scope info: block " FMT_BB " marking in scope: ", block->bbNum);
 608         dumpConvertedVarSet(this, inScope);
 609         printf("\n");
 610     }
 611 #endif // DEBUG
 612
 613     /* Record which vars are artifically kept alive for debugging */
 614
 615     VarSetOps::Assign(this, block->bbScope, inScope);
 616
 617     /* Being in scope implies a use of the variable. Add the var to bbVarUse
 618        so that redoing fgLiveVarAnalysis() will work correctly */
 619
 620     VarSetOps::UnionD(this, block->bbVarUse, inScope);
 621
 622     /* Artifically mark all vars in scope as alive */
 623
 624     VarSetOps::UnionD(this, block->bbLiveIn, inScope);
 625     VarSetOps::UnionD(this, block->bbLiveOut, inScope);
 626 }
 627
 628 void Compiler::fgUnmarkInScope(BasicBlock* block, VARSET_VALARG_TP unmarkScope)
 629 {
 630 #ifdef DEBUG
 631     if (verbose)
 632     {
 633         printf("Scope info: block " FMT_BB " UNmarking in scope: ", block->bbNum);
 634         dumpConvertedVarSet(this, unmarkScope);
 635         printf("\n");
 636     }
 637 #endif // DEBUG
 638
 639     assert(VarSetOps::IsSubset(this, unmarkScope, block->bbScope));
 640
 641     VarSetOps::DiffD(this, block->bbScope, unmarkScope);
 642     VarSetOps::DiffD(this, block->bbVarUse, unmarkScope);
 643     VarSetOps::DiffD(this, block->bbLiveIn, unmarkScope);
 644     VarSetOps::DiffD(this, block->bbLiveOut, unmarkScope);
 645 }
 646
 647 #ifdef DEBUG
 648
 649 void Compiler::fgDispDebugScopes()
 650 {
 651     printf("\nDebug scopes:\n");
 652
 653     BasicBlock* block;
 654     for (block = fgFirstBB; block; block = block->bbNext)
 655     {
 656         printf(FMT_BB ": ", block->bbNum);
 657         dumpConvertedVarSet(this, block->bbScope);
 658         printf("\n");
 659     }
 660 }
 661
 662 #endif // DEBUG
 663
 664 /*****************************************************************************
 665  *
 666  * Mark variables live across their entire scope.
 667  */
 668
 669 #if FEATURE_EH_FUNCLETS
 670
 671 void Compiler::fgExtendDbgScopes()
 672 {
 673     compResetScopeLists();
 674
 675 #ifdef DEBUG
 676     if (verbose)
 677     {
 678         printf("\nMarking vars alive over their entire scope :\n\n");
 679     }
 680
 681     if (verbose)
 682     {
 683         compDispScopeLists();
 684     }
 685 #endif // DEBUG
 686
 687     VARSET_TP inScope(VarSetOps::MakeEmpty(this));
 688
 689     // Mark all tracked LocalVars live over their scope - walk the blocks
 690     // keeping track of the current life, and assign it to the blocks.
 691
 692     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
 693     {
 694         // If we get to a funclet, reset the scope lists and start again, since the block
 695         // offsets will be out of order compared to the previous block.
 696
 697         if (block->bbFlags & BBF_FUNCLET_BEG)
 698         {
 699             compResetScopeLists();
 700             VarSetOps::ClearD(this, inScope);
 701         }
 702
 703         // Process all scopes up to the current offset
 704
 705         if (block->bbCodeOffs != BAD_IL_OFFSET)
 706         {
 707             compProcessScopesUntil(block->bbCodeOffs, &inScope, &Compiler::fgBeginScopeLife, &Compiler::fgEndScopeLife);
 708         }
 709
 710         // Assign the current set of variables that are in scope to the block variables tracking this.
 711
 712         fgMarkInScope(block, inScope);
 713     }
 714
 715 #ifdef DEBUG
 716     if (verbose)
 717     {
 718         fgDispDebugScopes();
 719     }
 720 #endif // DEBUG
 721 }
 722
 723 #else // !FEATURE_EH_FUNCLETS
 724
 725 void Compiler::fgExtendDbgScopes()
 726 {
 727     compResetScopeLists();
 728
 729 #ifdef DEBUG
 730     if (verbose)
 731     {
 732         printf("\nMarking vars alive over their entire scope :\n\n");
 733         compDispScopeLists();
 734     }
 735 #endif // DEBUG
 736
 737     VARSET_TP inScope(VarSetOps::MakeEmpty(this));
 738     compProcessScopesUntil(0, &inScope, &Compiler::fgBeginScopeLife, &Compiler::fgEndScopeLife);
 739
 740     IL_OFFSET lastEndOffs = 0;
 741
 742     // Mark all tracked LocalVars live over their scope - walk the blocks
 743     // keeping track of the current life, and assign it to the blocks.
 744
 745     BasicBlock* block;
 746     for (block = fgFirstBB; block; block = block->bbNext)
 747     {
 748         // Find scopes becoming alive. If there is a gap in the instr
 749         // sequence, we need to process any scopes on those missing offsets.
 750
 751         if (block->bbCodeOffs != BAD_IL_OFFSET)
 752         {
 753             if (lastEndOffs != block->bbCodeOffs)
 754             {
 755                 noway_assert(lastEndOffs < block->bbCodeOffs);
 756
 757                 compProcessScopesUntil(block->bbCodeOffs, &inScope, &Compiler::fgBeginScopeLife,
 758                                        &Compiler::fgEndScopeLife);
 759             }
 760             else
 761             {
 762                 while (VarScopeDsc* varScope = compGetNextEnterScope(block->bbCodeOffs))
 763                 {
 764                     fgBeginScopeLife(&inScope, varScope);
 765                 }
 766             }
 767         }
 768
 769         // Assign the current set of variables that are in scope to the block variables tracking this.
 770
 771         fgMarkInScope(block, inScope);
 772
 773         // Find scopes going dead.
 774
 775         if (block->bbCodeOffsEnd != BAD_IL_OFFSET)
 776         {
 777             VarScopeDsc* varScope;
 778             while ((varScope = compGetNextExitScope(block->bbCodeOffsEnd)) != nullptr)
 779             {
 780                 fgEndScopeLife(&inScope, varScope);
 781             }
 782
 783             lastEndOffs = block->bbCodeOffsEnd;
 784         }
 785     }
 786
 787     /* Everything should be out of scope by the end of the method. But if the
 788        last BB got removed, then inScope may not be empty. */
 789
 790     noway_assert(VarSetOps::IsEmpty(this, inScope) || lastEndOffs < info.compILCodeSize);
 791 }
 792
 793 #endif // !FEATURE_EH_FUNCLETS
 794
 795 /*****************************************************************************
 796  *
 797  * For debuggable code, we allow redundant assignments to vars
 798  * by marking them live over their entire scope.
 799  */
 800
 801 void Compiler::fgExtendDbgLifetimes()
 802 {
 803 #ifdef DEBUG
 804     if (verbose)
 805     {
 806         printf("*************** In fgExtendDbgLifetimes()\n");
 807     }
 808 #endif // DEBUG
 809
 810     noway_assert(opts.compDbgCode && (info.compVarScopesCount > 0));
 811
 812     /*-------------------------------------------------------------------------
 813      *   Extend the lifetimes over the entire reported scope of the variable.
 814      */
 815
 816     fgExtendDbgScopes();
 817
 818 /*-------------------------------------------------------------------------
 819  * Partly update liveness info so that we handle any funky BBF_INTERNAL
 820  * blocks inserted out of sequence.
 821  */
 822
 823 #ifdef DEBUG
 824     if (verbose && 0)
 825     {
 826         fgDispBBLiveness();
 827     }
 828 #endif
 829
 830     fgLiveVarAnalysis(true);
 831
 832     /* For compDbgCode, we prepend an empty BB which will hold the
 833        initializations of variables which are in scope at IL offset 0 (but
 834        not initialized by the IL code). Since they will currently be
 835        marked as live on entry to fgFirstBB, unmark the liveness so that
 836        the following code will know to add the initializations. */
 837
 838     assert(fgFirstBBisScratch());
 839
 840     VARSET_TP trackedArgs(VarSetOps::MakeEmpty(this));
 841
 842     for (unsigned argNum = 0; argNum < info.compArgsCount; argNum++)
 843     {
 844         LclVarDsc* argDsc = lvaTable + argNum;
 845         if (argDsc->lvPromoted)
 846         {
 847             lvaPromotionType promotionType = lvaGetPromotionType(argDsc);
 848
 849             if (promotionType == PROMOTION_TYPE_INDEPENDENT)
 850             {
 851                 noway_assert(argDsc->lvFieldCnt == 1); // We only handle one field here
 852
 853                 unsigned fieldVarNum = argDsc->lvFieldLclStart;
 854                 argDsc               = lvaTable + fieldVarNum;
 855             }
 856         }
 857         noway_assert(argDsc->lvIsParam);
 858         if (argDsc->lvTracked)
 859         {
 860             noway_assert(!VarSetOps::IsMember(this, trackedArgs, argDsc->lvVarIndex)); // Each arg should define a
 861                                                                                        // different bit.
 862             VarSetOps::AddElemD(this, trackedArgs, argDsc->lvVarIndex);
 863         }
 864     }
 865
 866     // Don't unmark struct locals, either.
 867     VARSET_TP noUnmarkVars(trackedArgs);
 868
 869     for (unsigned i = 0; i < lvaCount; i++)
 870     {
 871         LclVarDsc* varDsc = &lvaTable[i];
 872         if (varTypeIsStruct(varDsc) && varDsc->lvTracked)
 873         {
 874             VarSetOps::AddElemD(this, noUnmarkVars, varDsc->lvVarIndex);
 875         }
 876     }
 877     fgUnmarkInScope(fgFirstBB, VarSetOps::Diff(this, fgFirstBB->bbScope, noUnmarkVars));
 878
 879     /*-------------------------------------------------------------------------
 880      * As we keep variables artifically alive over their entire scope,
 881      * we need to also artificially initialize them if the scope does
 882      * not exactly match the real lifetimes, or they will contain
 883      * garbage until they are initialized by the IL code.
 884      */
 885
 886     VARSET_TP initVars(VarSetOps::MakeEmpty(this)); // Vars which are artificially made alive
 887
 888     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
 889     {
 890         VarSetOps::ClearD(this, initVars);
 891
 892         switch (block->bbJumpKind)
 893         {
 894             case BBJ_NONE:
 895                 PREFIX_ASSUME(block->bbNext != nullptr);
 896                 VarSetOps::UnionD(this, initVars, block->bbNext->bbScope);
 897                 break;
 898
 899             case BBJ_ALWAYS:
 900             case BBJ_EHCATCHRET:
 901             case BBJ_EHFILTERRET:
 902                 VarSetOps::UnionD(this, initVars, block->bbJumpDest->bbScope);
 903                 break;
 904
 905             case BBJ_CALLFINALLY:
 906                 if (!(block->bbFlags & BBF_RETLESS_CALL))
 907                 {
 908                     assert(block->isBBCallAlwaysPair());
 909                     PREFIX_ASSUME(block->bbNext != nullptr);
 910                     VarSetOps::UnionD(this, initVars, block->bbNext->bbScope);
 911                 }
 912                 VarSetOps::UnionD(this, initVars, block->bbJumpDest->bbScope);
 913                 break;
 914
 915             case BBJ_COND:
 916                 PREFIX_ASSUME(block->bbNext != nullptr);
 917                 VarSetOps::UnionD(this, initVars, block->bbNext->bbScope);
 918                 VarSetOps::UnionD(this, initVars, block->bbJumpDest->bbScope);
 919                 break;
 920
 921             case BBJ_SWITCH:
 922             {
 923                 BasicBlock** jmpTab;
 924                 unsigned     jmpCnt;
 925
 926                 jmpCnt = block->bbJumpSwt->bbsCount;
 927                 jmpTab = block->bbJumpSwt->bbsDstTab;
 928
 929                 do
 930                 {
 931                     VarSetOps::UnionD(this, initVars, (*jmpTab)->bbScope);
 932                 } while (++jmpTab, --jmpCnt);
 933             }
 934             break;
 935
 936             case BBJ_EHFINALLYRET:
 937             case BBJ_RETURN:
 938                 break;
 939
 940             case BBJ_THROW:
 941                 /* We don't have to do anything as we mark
 942                  * all vars live on entry to a catch handler as
 943                  * volatile anyway
 944                  */
 945                 break;
 946
 947             default:
 948                 noway_assert(!"Unexpected bbJumpKind");
 949                 break;
 950         }
 951
 952         /* If the var is already live on entry to the current BB,
 953            we would have already initialized it. So ignore bbLiveIn */
 954
 955         VarSetOps::DiffD(this, initVars, block->bbLiveIn);
 956
 957         /* Add statements initializing the vars, if there are any to initialize */
 958         unsigned blockWeight = block->getBBWeight(this);
 959
 960         VarSetOps::Iter iter(this, initVars);
 961         unsigned        varIndex = 0;
 962         while (iter.NextElem(&varIndex))
 963         {
 964             /* Create initialization tree */
 965
 966             unsigned   varNum = lvaTrackedToVarNum[varIndex];
 967             LclVarDsc* varDsc = &lvaTable[varNum];
 968             var_types  type   = varDsc->TypeGet();
 969
 970             // Don't extend struct lifetimes -- they aren't enregistered, anyway.
 971             if (type == TYP_STRUCT)
 972             {
 973                 continue;
 974             }
 975
 976             // If we haven't already done this ...
 977             if (!fgLocalVarLivenessDone)
 978             {
 979                 // Create a "zero" node
 980                 GenTree* zero = gtNewZeroConNode(genActualType(type));
 981
 982                 // Create initialization node
 983                 if (!block->IsLIR())
 984                 {
 985                     GenTree* varNode  = gtNewLclvNode(varNum, type);
 986                     GenTree* initNode = gtNewAssignNode(varNode, zero);
 987
 988                     // Create a statement for the initializer, sequence it, and append it to the current BB.
 989                     GenTree* initStmt = gtNewStmt(initNode);
 990                     gtSetStmtInfo(initStmt);
 991                     fgSetStmtSeq(initStmt);
 992                     fgInsertStmtNearEnd(block, initStmt);
 993                 }
 994                 else
 995                 {
 996                     GenTree* store    = new (this, GT_STORE_LCL_VAR) GenTreeLclVar(GT_STORE_LCL_VAR, type, varNum);
 997                     store->gtOp.gtOp1 = zero;
 998                     store->gtFlags |= (GTF_VAR_DEF | GTF_ASG);
 999
1000                     LIR::Range initRange = LIR::EmptyRange();
1001                     initRange.InsertBefore(nullptr, zero, store);
1002
1003 #if !defined(_TARGET_64BIT_)
1004                     DecomposeLongs::DecomposeRange(this, blockWeight, initRange);
1005 #endif // !defined(_TARGET_64BIT_)
1006                     m_pLowering->LowerRange(block, initRange);
1007
1008                     // Naively inserting the initializer at the end of the block may add code after the block's
1009                     // terminator, in which case the inserted code will never be executed (and the IR for the
1010                     // block will be invalid). Use `LIR::InsertBeforeTerminator` to avoid this problem.
1011                     LIR::InsertBeforeTerminator(block, std::move(initRange));
1012                 }
1013
1014 #ifdef DEBUG
1015                 if (verbose)
1016                 {
1017                     printf("Created zero-init of V%02u in " FMT_BB "\n", varNum, block->bbNum);
1018                 }
1019 #endif                                         // DEBUG
1020                 block->bbFlags |= BBF_CHANGED; // indicates that the contents of the block have changed.
1021             }
1022
1023             /* Update liveness information so that redoing fgLiveVarAnalysis()
1024                will work correctly if needed */
1025
1026             VarSetOps::AddElemD(this, block->bbVarDef, varIndex);
1027             VarSetOps::AddElemD(this, block->bbLiveOut, varIndex);
1028         }
1029     }
1030
1031     // raMarkStkVars() reserves stack space for unused variables (which
1032     //   needs to be initialized). However, arguments don't need to be initialized.
1033     //   So just ensure that they don't have a 0 ref cnt
1034
1035     unsigned lclNum = 0;
1036     for (LclVarDsc *varDsc = lvaTable; lclNum < lvaCount; lclNum++, varDsc++)
1037     {
1038         if (lclNum >= info.compArgsCount)
1039         {
1040             break; // early exit for loop
1041         }
1042
1043         if (varDsc->lvIsRegArg)
1044         {
1045             varDsc->lvImplicitlyReferenced = true;
1046         }
1047     }
1048
1049 #ifdef DEBUG
1050     if (verbose)
1051     {
1052         printf("\nBB liveness after fgExtendDbgLifetimes():\n\n");
1053         fgDispBBLiveness();
1054         printf("\n");
1055     }
1056 #endif // DEBUG
1057 }
1058
1059 //------------------------------------------------------------------------
1060 // fgGetHandlerLiveVars: determine set of locals live because of implicit
1061 //   exception flow from a block.
1062 //
1063 // Arguments:
1064 //    block - the block in question
1065 //
1066 // Returns:
1067 //    Additional set of locals to be considered live throughout the block.
1068 //
1069 // Notes:
1070 //    Assumes caller has screened candidate blocks to only those with
1071 //    exception flow, via `ehBlockHasExnFlowDsc`.
1072 //
1073 //    Exception flow can arise because of a newly raised exception (for
1074 //    blocks within try regions) or because of an actively propagating exception
1075 //    (for filter blocks). This flow effectively creates additional successor
1076 //    edges in the flow graph that the jit does not model. This method computes
1077 //    the net contribution from all the missing successor edges.
1078 //
1079 //    For example, with the following C# source, during EH processing of the throw,
1080 //    the outer filter will execute in pass1, before the inner handler executes
1081 //    in pass2, and so the filter blocks should show the inner handler's local is live.
1082 //
1083 //    try
1084 //    {
1085 //        using (AllocateObject())   // ==> try-finally; handler calls Dispose
1086 //        {
1087 //            throw new Exception();
1088 //        }
1089 //    }
1090 //    catch (Exception e1) when (IsExpectedException(e1))
1091 //    {
1092 //        Console.WriteLine("In catch 1");
1093 //    }
1094
1095 VARSET_VALRET_TP Compiler::fgGetHandlerLiveVars(BasicBlock* block)
1096 {
1097     noway_assert(block);
1098     noway_assert(ehBlockHasExnFlowDsc(block));
1099
1100     VARSET_TP liveVars(VarSetOps::MakeEmpty(this));
1101     EHblkDsc* HBtab = ehGetBlockExnFlowDsc(block);
1102
1103     do
1104     {
1105         /* Either we enter the filter first or the catch/finally */
1106         if (HBtab->HasFilter())
1107         {
1108             VarSetOps::UnionD(this, liveVars, HBtab->ebdFilter->bbLiveIn);
1109 #if FEATURE_EH_FUNCLETS
1110             // The EH subsystem can trigger a stack walk after the filter
1111             // has returned, but before invoking the handler, and the only
1112             // IP address reported from this method will be the original
1113             // faulting instruction, thus everything in the try body
1114             // must report as live any variables live-out of the filter
1115             // (which is the same as those live-in to the handler)
1116             VarSetOps::UnionD(this, liveVars, HBtab->ebdHndBeg->bbLiveIn);
1117 #endif // FEATURE_EH_FUNCLETS
1118         }
1119         else
1120         {
1121             VarSetOps::UnionD(this, liveVars, HBtab->ebdHndBeg->bbLiveIn);
1122         }
1123
1124         /* If we have nested try's edbEnclosing will provide them */
1125         noway_assert((HBtab->ebdEnclosingTryIndex == EHblkDsc::NO_ENCLOSING_INDEX) ||
1126                      (HBtab->ebdEnclosingTryIndex > ehGetIndex(HBtab)));
1127
1128         unsigned outerIndex = HBtab->ebdEnclosingTryIndex;
1129         if (outerIndex == EHblkDsc::NO_ENCLOSING_INDEX)
1130         {
1131             break;
1132         }
1133         HBtab = ehGetDsc(outerIndex);
1134
1135     } while (true);
1136
1137     // If this block is within a filter, we also need to report as live
1138     // any vars live into enclosed finally or fault handlers, since the
1139     // filter will run during the first EH pass, and enclosed or enclosing
1140     // handlers will run during the second EH pass. So all these handlers
1141     // are "exception flow" successors of the filter.
1142     //
1143     // Note we are relying on ehBlockHasExnFlowDsc to return true
1144     // for any filter block that we should examine here.
1145     if (block->hasHndIndex())
1146     {
1147         const unsigned thisHndIndex   = block->getHndIndex();
1148         EHblkDsc*      enclosingHBtab = ehGetDsc(thisHndIndex);
1149
1150         if (enclosingHBtab->InFilterRegionBBRange(block))
1151         {
1152             assert(enclosingHBtab->HasFilter());
1153
1154             // Search the EH table for enclosed regions.
1155             //
1156             // All the enclosed regions will be lower numbered and
1157             // immediately prior to and contiguous with the enclosing
1158             // region in the EH tab.
1159             unsigned index = thisHndIndex;
1160
1161             while (index > 0)
1162             {
1163                 index--;
1164                 unsigned enclosingIndex = ehGetEnclosingTryIndex(index);
1165                 bool     isEnclosed     = false;
1166
1167                 // To verify this is an enclosed region, search up
1168                 // through the enclosing regions until we find the
1169                 // region associated with the filter.
1170                 while (enclosingIndex != EHblkDsc::NO_ENCLOSING_INDEX)
1171                 {
1172                     if (enclosingIndex == thisHndIndex)
1173                     {
1174                         isEnclosed = true;
1175                         break;
1176                     }
1177
1178                     enclosingIndex = ehGetEnclosingTryIndex(enclosingIndex);
1179                 }
1180
1181                 // If we found an enclosed region, check if the region
1182                 // is a try fault or try finally, and if so, add any
1183                 // locals live into the enclosed region's handler into this
1184                 // block's live-in set.
1185                 if (isEnclosed)
1186                 {
1187                     EHblkDsc* enclosedHBtab = ehGetDsc(index);
1188
1189                     if (enclosedHBtab->HasFinallyOrFaultHandler())
1190                     {
1191                         VarSetOps::UnionD(this, liveVars, enclosedHBtab->ebdHndBeg->bbLiveIn);
1192                     }
1193                 }
1194                 // Once we run across a non-enclosed region, we can stop searching.
1195                 else
1196                 {
1197                     break;
1198                 }
1199             }
1200         }
1201     }
1202
1203     return liveVars;
1204 }
1205
1206 class LiveVarAnalysis
1207 {
1208     Compiler* m_compiler;
1209
1210     bool m_hasPossibleBackEdge;
1211
1212     unsigned  m_memoryLiveIn;
1213     unsigned  m_memoryLiveOut;
1214     VARSET_TP m_liveIn;
1215     VARSET_TP m_liveOut;
1216
1217     LiveVarAnalysis(Compiler* compiler)
1218         : m_compiler(compiler)
1219         , m_hasPossibleBackEdge(false)
1220         , m_memoryLiveIn(emptyMemoryKindSet)
1221         , m_memoryLiveOut(emptyMemoryKindSet)
1222         , m_liveIn(VarSetOps::MakeEmpty(compiler))
1223         , m_liveOut(VarSetOps::MakeEmpty(compiler))
1224     {
1225     }
1226
1227     bool PerBlockAnalysis(BasicBlock* block, bool updateInternalOnly, bool keepAliveThis)
1228     {
1229         /* Compute the 'liveOut' set */
1230         VarSetOps::ClearD(m_compiler, m_liveOut);
1231         m_memoryLiveOut = emptyMemoryKindSet;
1232         if (block->endsWithJmpMethod(m_compiler))
1233         {
1234             // A JMP uses all the arguments, so mark them all
1235             // as live at the JMP instruction
1236             //
1237             const LclVarDsc* varDscEndParams = m_compiler->lvaTable + m_compiler->info.compArgsCount;
1238             for (LclVarDsc* varDsc = m_compiler->lvaTable; varDsc < varDscEndParams; varDsc++)
1239             {
1240                 noway_assert(!varDsc->lvPromoted);
1241                 if (varDsc->lvTracked)
1242                 {
1243                     VarSetOps::AddElemD(m_compiler, m_liveOut, varDsc->lvVarIndex);
1244                 }
1245             }
1246         }
1247
1248         // Additionally, union in all the live-in tracked vars of successors.
1249         for (BasicBlock* succ : block->GetAllSuccs(m_compiler))
1250         {
1251             VarSetOps::UnionD(m_compiler, m_liveOut, succ->bbLiveIn);
1252             m_memoryLiveOut |= succ->bbMemoryLiveIn;
1253             if (succ->bbNum <= block->bbNum)
1254             {
1255                 m_hasPossibleBackEdge = true;
1256             }
1257         }
1258
1259         /* For lvaKeepAliveAndReportThis methods, "this" has to be kept alive everywhere
1260            Note that a function may end in a throw on an infinite loop (as opposed to a return).
1261            "this" has to be alive everywhere even in such methods. */
1262
1263         if (keepAliveThis)
1264         {
1265             VarSetOps::AddElemD(m_compiler, m_liveOut, m_compiler->lvaTable[m_compiler->info.compThisArg].lvVarIndex);
1266         }
1267
1268         /* Compute the 'm_liveIn'  set */
1269         VarSetOps::LivenessD(m_compiler, m_liveIn, block->bbVarDef, block->bbVarUse, m_liveOut);
1270
1271         // Even if block->bbMemoryDef is set, we must assume that it doesn't kill memory liveness from m_memoryLiveOut,
1272         // since (without proof otherwise) the use and def may touch different memory at run-time.
1273         m_memoryLiveIn = m_memoryLiveOut | block->bbMemoryUse;
1274
1275         // Does this block have implicit exception flow to a filter or handler?
1276         // If so, include the effects of that flow.
1277         if (m_compiler->ehBlockHasExnFlowDsc(block))
1278         {
1279             const VARSET_TP& liveVars(m_compiler->fgGetHandlerLiveVars(block));
1280             VarSetOps::UnionD(m_compiler, m_liveIn, liveVars);
1281             VarSetOps::UnionD(m_compiler, m_liveOut, liveVars);
1282
1283             // Implicit eh edges can induce loop-like behavior,
1284             // so make sure we iterate to closure.
1285             m_hasPossibleBackEdge = true;
1286         }
1287
1288         /* Has there been any change in either live set? */
1289
1290         bool liveInChanged = !VarSetOps::Equal(m_compiler, block->bbLiveIn, m_liveIn);
1291         if (liveInChanged || !VarSetOps::Equal(m_compiler, block->bbLiveOut, m_liveOut))
1292         {
1293             if (updateInternalOnly)
1294             {
1295                 // Only "extend" liveness over BBF_INTERNAL blocks
1296
1297                 noway_assert(block->bbFlags & BBF_INTERNAL);
1298
1299                 liveInChanged = !VarSetOps::IsSubset(m_compiler, m_liveIn, block->bbLiveIn);
1300                 if (liveInChanged || !VarSetOps::IsSubset(m_compiler, m_liveOut, block->bbLiveOut))
1301                 {
1302 #ifdef DEBUG
1303                     if (m_compiler->verbose)
1304                     {
1305                         printf("Scope info: block " FMT_BB " LiveIn+ ", block->bbNum);
1306                         dumpConvertedVarSet(m_compiler, VarSetOps::Diff(m_compiler, m_liveIn, block->bbLiveIn));
1307                         printf(", LiveOut+ ");
1308                         dumpConvertedVarSet(m_compiler, VarSetOps::Diff(m_compiler, m_liveOut, block->bbLiveOut));
1309                         printf("\n");
1310                     }
1311 #endif // DEBUG
1312
1313                     VarSetOps::UnionD(m_compiler, block->bbLiveIn, m_liveIn);
1314                     VarSetOps::UnionD(m_compiler, block->bbLiveOut, m_liveOut);
1315                 }
1316             }
1317             else
1318             {
1319                 VarSetOps::Assign(m_compiler, block->bbLiveIn, m_liveIn);
1320                 VarSetOps::Assign(m_compiler, block->bbLiveOut, m_liveOut);
1321             }
1322         }
1323
1324         const bool memoryLiveInChanged = (block->bbMemoryLiveIn != m_memoryLiveIn);
1325         if (memoryLiveInChanged || (block->bbMemoryLiveOut != m_memoryLiveOut))
1326         {
1327             block->bbMemoryLiveIn  = m_memoryLiveIn;
1328             block->bbMemoryLiveOut = m_memoryLiveOut;
1329         }
1330
1331         return liveInChanged || memoryLiveInChanged;
1332     }
1333
1334     void Run(bool updateInternalOnly)
1335     {
1336         const bool keepAliveThis =
1337             m_compiler->lvaKeepAliveAndReportThis() && m_compiler->lvaTable[m_compiler->info.compThisArg].lvTracked;
1338
1339         /* Live Variable Analysis - Backward dataflow */
1340         bool changed;
1341         do
1342         {
1343             changed = false;
1344
1345             /* Visit all blocks and compute new data flow values */
1346
1347             VarSetOps::ClearD(m_compiler, m_liveIn);
1348             VarSetOps::ClearD(m_compiler, m_liveOut);
1349
1350             m_memoryLiveIn  = emptyMemoryKindSet;
1351             m_memoryLiveOut = emptyMemoryKindSet;
1352
1353             for (BasicBlock* block = m_compiler->fgLastBB; block; block = block->bbPrev)
1354             {
1355                 // sometimes block numbers are not monotonically increasing which
1356                 // would cause us not to identify backedges
1357                 if (block->bbNext && block->bbNext->bbNum <= block->bbNum)
1358                 {
1359                     m_hasPossibleBackEdge = true;
1360                 }
1361
1362                 if (updateInternalOnly)
1363                 {
1364                     /* Only update BBF_INTERNAL blocks as they may be
1365                        syntactically out of sequence. */
1366
1367                     noway_assert(m_compiler->opts.compDbgCode && (m_compiler->info.compVarScopesCount > 0));
1368
1369                     if (!(block->bbFlags & BBF_INTERNAL))
1370                     {
1371                         continue;
1372                     }
1373                 }
1374
1375                 if (PerBlockAnalysis(block, updateInternalOnly, keepAliveThis))
1376                 {
1377                     changed = true;
1378                 }
1379             }
1380             // if there is no way we could have processed a block without seeing all of its predecessors
1381             // then there is no need to iterate
1382             if (!m_hasPossibleBackEdge)
1383             {
1384                 break;
1385             }
1386         } while (changed);
1387     }
1388
1389 public:
1390     static void Run(Compiler* compiler, bool updateInternalOnly)
1391     {
1392         LiveVarAnalysis analysis(compiler);
1393         analysis.Run(updateInternalOnly);
1394     }
1395 };
1396
1397 /*****************************************************************************
1398  *
1399  *  This is the classic algorithm for Live Variable Analysis.
1400  *  If updateInternalOnly==true, only update BBF_INTERNAL blocks.
1401  */
1402
1403 void Compiler::fgLiveVarAnalysis(bool updateInternalOnly)
1404 {
1405     if (!backendRequiresLocalVarLifetimes())
1406     {
1407         return;
1408     }
1409
1410     LiveVarAnalysis::Run(this, updateInternalOnly);
1411
1412 #ifdef DEBUG
1413     if (verbose && !updateInternalOnly)
1414     {
1415         printf("\nBB liveness after fgLiveVarAnalysis():\n\n");
1416         fgDispBBLiveness();
1417     }
1418 #endif // DEBUG
1419 }
1420
1421 /*****************************************************************************
1422  * For updating liveset during traversal AFTER fgComputeLife has completed
1423  */
1424
1425 VARSET_VALRET_TP Compiler::fgUpdateLiveSet(VARSET_VALARG_TP liveSet, GenTree* tree)
1426 {
1427     VARSET_TP newLiveSet(VarSetOps::MakeCopy(this, liveSet));
1428     assert(fgLocalVarLivenessDone == true);
1429     GenTree* lclVarTree = tree; // After the tests below, "lclVarTree" will be the local variable.
1430     if (tree->gtOper == GT_LCL_VAR || tree->gtOper == GT_LCL_FLD ||
1431         (lclVarTree = fgIsIndirOfAddrOfLocal(tree)) != nullptr)
1432     {
1433         const VARSET_TP& varBits(fgGetVarBits(lclVarTree));
1434
1435         if (!VarSetOps::IsEmpty(this, varBits))
1436         {
1437             if (tree->gtFlags & GTF_VAR_DEATH)
1438             {
1439                 // We'd like to be able to assert the following, however if we are walking
1440                 // through a qmark/colon tree, we may encounter multiple last-use nodes.
1441                 // assert (VarSetOps::IsSubset(this, varBits, newLiveSet));
1442
1443                 // We maintain the invariant that if the lclVarTree is a promoted struct, but the
1444                 // the lookup fails, then all the field vars (i.e., "varBits") are dying.
1445                 VARSET_TP* deadVarBits = nullptr;
1446                 if (varTypeIsStruct(lclVarTree) && LookupPromotedStructDeathVars(lclVarTree, &deadVarBits))
1447                 {
1448                     VarSetOps::DiffD(this, newLiveSet, *deadVarBits);
1449                 }
1450                 else
1451                 {
1452                     VarSetOps::DiffD(this, newLiveSet, varBits);
1453                 }
1454             }
1455             else if ((tree->gtFlags & GTF_VAR_DEF) != 0 && (tree->gtFlags & GTF_VAR_USEASG) == 0)
1456             {
1457                 assert(tree == lclVarTree); // LDOBJ case should only be a use.
1458
1459                 // This shouldn't be in newLiveSet, unless this is debug code, in which
1460                 // case we keep vars live everywhere, OR it is address-exposed, OR this block
1461                 // is part of a try block, in which case it may be live at the handler
1462                 // Could add a check that, if it's in the newLiveSet, that it's also in
1463                 // fgGetHandlerLiveVars(compCurBB), but seems excessive
1464                 //
1465                 assert(VarSetOps::IsEmptyIntersection(this, newLiveSet, varBits) || opts.compDbgCode ||
1466                        lvaTable[tree->gtLclVarCommon.gtLclNum].lvAddrExposed ||
1467                        (compCurBB != nullptr && ehBlockHasExnFlowDsc(compCurBB)));
1468                 VarSetOps::UnionD(this, newLiveSet, varBits);
1469             }
1470         }
1471     }
1472     return newLiveSet;
1473 }
1474
1475 //------------------------------------------------------------------------
1476 // Compiler::fgComputeLifeCall: compute the changes to local var liveness
1477 //                              due to a GT_CALL node.
1478 //
1479 // Arguments:
1480 //    life - The live set that is being computed.
1481 //    call - The call node in question.
1482 //
1483 void Compiler::fgComputeLifeCall(VARSET_TP& life, GenTreeCall* call)
1484 {
1485     assert(call != nullptr);
1486
1487     // If this is a tail-call and we have any unmanaged p/invoke calls in
1488     // the method then we're going to run the p/invoke epilog
1489     // So we mark the FrameRoot as used by this instruction.
1490     // This ensure that this variable is kept alive at the tail-call
1491     if (call->IsTailCall() && info.compCallUnmanaged)
1492     {
1493         assert((!opts.ShouldUsePInvokeHelpers()) || (info.compLvFrameListRoot == BAD_VAR_NUM));
1494         if (!opts.ShouldUsePInvokeHelpers())
1495         {
1496             /* Get the TCB local and make it live */
1497
1498             noway_assert(info.compLvFrameListRoot < lvaCount);
1499
1500             LclVarDsc* frameVarDsc = &lvaTable[info.compLvFrameListRoot];
1501
1502             if (frameVarDsc->lvTracked)
1503             {
1504                 VarSetOps::AddElemD(this, life, frameVarDsc->lvVarIndex);
1505             }
1506         }
1507     }
1508
1509     // TODO: we should generate the code for saving to/restoring
1510     //       from the inlined N/Direct frame instead.
1511
1512     /* Is this call to unmanaged code? */
1513     if (call->IsUnmanaged())
1514     {
1515         /* Get the TCB local and make it live */
1516         assert((!opts.ShouldUsePInvokeHelpers()) || (info.compLvFrameListRoot == BAD_VAR_NUM));
1517         if (!opts.ShouldUsePInvokeHelpers())
1518         {
1519             noway_assert(info.compLvFrameListRoot < lvaCount);
1520
1521             LclVarDsc* frameVarDsc = &lvaTable[info.compLvFrameListRoot];
1522
1523             if (frameVarDsc->lvTracked)
1524             {
1525                 unsigned varIndex = frameVarDsc->lvVarIndex;
1526                 noway_assert(varIndex < lvaTrackedCount);
1527
1528                 // Is the variable already known to be alive?
1529                 //
1530                 if (VarSetOps::IsMember(this, life, varIndex))
1531                 {
1532                     // Since we may call this multiple times, clear the GTF_CALL_M_FRAME_VAR_DEATH if set.
1533                     //
1534                     call->gtCallMoreFlags &= ~GTF_CALL_M_FRAME_VAR_DEATH;
1535                 }
1536                 else
1537                 {
1538                     // The variable is just coming to life
1539                     // Since this is a backwards walk of the trees
1540                     // that makes this change in liveness a 'last-use'
1541                     //
1542                     VarSetOps::AddElemD(this, life, varIndex);
1543                     call->gtCallMoreFlags |= GTF_CALL_M_FRAME_VAR_DEATH;
1544                 }
1545             }
1546         }
1547     }
1548 }
1549
1550 //------------------------------------------------------------------------
1551 // Compiler::fgComputeLifeTrackedLocalUse:
1552 //    Compute the changes to local var liveness due to a use of a tracked local var.
1553 //
1554 // Arguments:
1555 //    life          - The live set that is being computed.
1556 //    varDsc        - The LclVar descriptor for the variable being used or defined.
1557 //    node          - The node that is defining the lclVar.
1558 void Compiler::fgComputeLifeTrackedLocalUse(VARSET_TP& life, LclVarDsc& varDsc, GenTreeLclVarCommon* node)
1559 {
1560     assert(node != nullptr);
1561     assert((node->gtFlags & GTF_VAR_DEF) == 0);
1562     assert(varDsc.lvTracked);
1563
1564     const unsigned varIndex = varDsc.lvVarIndex;
1565
1566     // Is the variable already known to be alive?
1567     if (VarSetOps::IsMember(this, life, varIndex))
1568     {
1569         // Since we may do liveness analysis multiple times, clear the GTF_VAR_DEATH if set.
1570         node->gtFlags &= ~GTF_VAR_DEATH;
1571         return;
1572     }
1573
1574 #ifdef DEBUG
1575     if (verbose && 0)
1576     {
1577         printf("Ref V%02u,T%02u] at ", node->gtLclNum, varIndex);
1578         printTreeID(node);
1579         printf(" life %s -> %s\n", VarSetOps::ToString(this, life),
1580                VarSetOps::ToString(this, VarSetOps::AddElem(this, life, varIndex)));
1581     }
1582 #endif // DEBUG
1583
1584     // The variable is being used, and it is not currently live.
1585     // So the variable is just coming to life
1586     node->gtFlags |= GTF_VAR_DEATH;
1587     VarSetOps::AddElemD(this, life, varIndex);
1588 }
1589
1590 //------------------------------------------------------------------------
1591 // Compiler::fgComputeLifeTrackedLocalDef:
1592 //    Compute the changes to local var liveness due to a def of a tracked local var and return `true` if the def is a
1593 //    dead store.
1594 //
1595 // Arguments:
1596 //    life          - The live set that is being computed.
1597 //    keepAliveVars - The current set of variables to keep alive regardless of their actual lifetime.
1598 //    varDsc        - The LclVar descriptor for the variable being used or defined.
1599 //    node          - The node that is defining the lclVar.
1600 //
1601 // Returns:
1602 //    `true` if the def is a dead store; `false` otherwise.
1603 bool Compiler::fgComputeLifeTrackedLocalDef(VARSET_TP&           life,
1604                                             VARSET_VALARG_TP     keepAliveVars,
1605                                             LclVarDsc&           varDsc,
1606                                             GenTreeLclVarCommon* node)
1607 {
1608     assert(node != nullptr);
1609     assert((node->gtFlags & GTF_VAR_DEF) != 0);
1610     assert(varDsc.lvTracked);
1611
1612     const unsigned varIndex = varDsc.lvVarIndex;
1613     if (VarSetOps::IsMember(this, life, varIndex))
1614     {
1615         // The variable is live
1616         if ((node->gtFlags & GTF_VAR_USEASG) == 0)
1617         {
1618             // Remove the variable from the live set if it is not in the keepalive set.
1619             if (!VarSetOps::IsMember(this, keepAliveVars, varIndex))
1620             {
1621                 VarSetOps::RemoveElemD(this, life, varIndex);
1622             }
1623 #ifdef DEBUG
1624             if (verbose && 0)
1625             {
1626                 printf("Def V%02u,T%02u at ", node->gtLclNum, varIndex);
1627                 printTreeID(node);
1628                 printf(" life %s -> %s\n",
1629                        VarSetOps::ToString(this,
1630                                            VarSetOps::Union(this, life, VarSetOps::MakeSingleton(this, varIndex))),
1631                        VarSetOps::ToString(this, life));
1632             }
1633 #endif // DEBUG
1634         }
1635     }
1636     else
1637     {
1638         // Dead store
1639         node->gtFlags |= GTF_VAR_DEATH;
1640
1641         if (!opts.MinOpts())
1642         {
1643             // keepAliveVars always stay alive
1644             noway_assert(!VarSetOps::IsMember(this, keepAliveVars, varIndex));
1645
1646             // Do not consider this store dead if the target local variable represents
1647             // a promoted struct field of an address exposed local or if the address
1648             // of the variable has been exposed. Improved alias analysis could allow
1649             // stores to these sorts of variables to be removed at the cost of compile
1650             // time.
1651             return !varDsc.lvAddrExposed && !(varDsc.lvIsStructField && lvaTable[varDsc.lvParentLcl].lvAddrExposed);
1652         }
1653     }
1654
1655     return false;
1656 }
1657
1658 //------------------------------------------------------------------------
1659 // Compiler::fgComputeLifeUntrackedLocal:
1660 //    Compute the changes to local var liveness due to a use or a def of an untracked local var.
1661 //
1662 // Note:
1663 //    It may seem a bit counter-intuitive that a change to an untracked lclVar could affect the liveness of tracked
1664 //    lclVars. In theory, this could happen with promoted (especially dependently-promoted) structs: in these cases,
1665 //    a use or def of the untracked struct var is treated as a use or def of any of its component fields that are
1666 //    tracked.
1667 //
1668 // Arguments:
1669 //    life          - The live set that is being computed.
1670 //    keepAliveVars - The current set of variables to keep alive regardless of their actual lifetime.
1671 //    varDsc        - The LclVar descriptor for the variable being used or defined.
1672 //    lclVarNode    - The node that corresponds to the local var def or use.
1673 void Compiler::fgComputeLifeUntrackedLocal(VARSET_TP&           life,
1674                                            VARSET_VALARG_TP     keepAliveVars,
1675                                            LclVarDsc&           varDsc,
1676                                            GenTreeLclVarCommon* lclVarNode)
1677 {
1678     assert(lclVarNode != nullptr);
1679
1680     if (!varTypeIsStruct(varDsc.lvType) || (lvaGetPromotionType(&varDsc) == PROMOTION_TYPE_NONE))
1681     {
1682         return;
1683     }
1684
1685     VARSET_TP varBit(VarSetOps::MakeEmpty(this));
1686
1687     for (unsigned i = varDsc.lvFieldLclStart; i < varDsc.lvFieldLclStart + varDsc.lvFieldCnt; ++i)
1688     {
1689 #if !defined(_TARGET_64BIT_)
1690         if (!varTypeIsLong(lvaTable[i].lvType) || !lvaTable[i].lvPromoted)
1691 #endif // !defined(_TARGET_64BIT_)
1692         {
1693             noway_assert(lvaTable[i].lvIsStructField);
1694         }
1695         if (lvaTable[i].lvTracked)
1696         {
1697             const unsigned varIndex = lvaTable[i].lvVarIndex;
1698             noway_assert(varIndex < lvaTrackedCount);
1699             VarSetOps::AddElemD(this, varBit, varIndex);
1700         }
1701     }
1702     if (lclVarNode->gtFlags & GTF_VAR_DEF)
1703     {
1704         VarSetOps::DiffD(this, varBit, keepAliveVars);
1705         VarSetOps::DiffD(this, life, varBit);
1706         return;
1707     }
1708     // This is a use.
1709
1710     // Are the variables already known to be alive?
1711     if (VarSetOps::IsSubset(this, varBit, life))
1712     {
1713         lclVarNode->gtFlags &= ~GTF_VAR_DEATH; // Since we may now call this multiple times, reset if live.
1714         return;
1715     }
1716
1717     // Some variables are being used, and they are not currently live.
1718     // So they are just coming to life, in the backwards traversal; in a forwards
1719     // traversal, one or more are dying.  Mark this.
1720
1721     lclVarNode->gtFlags |= GTF_VAR_DEATH;
1722
1723     // Are all the variables becoming alive (in the backwards traversal), or just a subset?
1724     if (!VarSetOps::IsEmptyIntersection(this, varBit, life))
1725     {
1726         // Only a subset of the variables are become live; we must record that subset.
1727         // (Lack of an entry for "lclVarNode" will be considered to imply all become dead in the
1728         // forward traversal.)
1729         VARSET_TP* deadVarSet = new (this, CMK_bitset) VARSET_TP;
1730         VarSetOps::AssignNoCopy(this, *deadVarSet, VarSetOps::Diff(this, varBit, life));
1731         GetPromotedStructDeathVars()->Set(lclVarNode, deadVarSet);
1732     }
1733
1734     // In any case, all the field vars are now live (in the backwards traversal).
1735     VarSetOps::UnionD(this, life, varBit);
1736 }
1737
1738 //------------------------------------------------------------------------
1739 // Compiler::fgComputeLifeLocal:
1740 //    Compute the changes to local var liveness due to a use or a def of a local var and indicates whether the use/def
1741 //    is a dead store.
1742 //
1743 // Arguments:
1744 //    life          - The live set that is being computed.
1745 //    keepAliveVars - The current set of variables to keep alive regardless of their actual lifetime.
1746 //    lclVarNode    - The node that corresponds to the local var def or use.
1747 //
1748 // Returns:
1749 //    `true` if the local var node corresponds to a dead store; `false` otherwise.
1750 bool Compiler::fgComputeLifeLocal(VARSET_TP& life, VARSET_VALARG_TP keepAliveVars, GenTree* lclVarNode)
1751 {
1752     unsigned lclNum = lclVarNode->gtLclVarCommon.gtLclNum;
1753
1754     assert(lclNum < lvaCount);
1755     LclVarDsc& varDsc = lvaTable[lclNum];
1756
1757     // Is this a tracked variable?
1758     if (varDsc.lvTracked)
1759     {
1760         /* Is this a definition or use? */
1761         if (lclVarNode->gtFlags & GTF_VAR_DEF)
1762         {
1763             return fgComputeLifeTrackedLocalDef(life, keepAliveVars, varDsc, lclVarNode->AsLclVarCommon());
1764         }
1765         else
1766         {
1767             fgComputeLifeTrackedLocalUse(life, varDsc, lclVarNode->AsLclVarCommon());
1768         }
1769     }
1770     else
1771     {
1772         fgComputeLifeUntrackedLocal(life, keepAliveVars, varDsc, lclVarNode->AsLclVarCommon());
1773     }
1774     return false;
1775 }
1776
1777 /*****************************************************************************
1778  *
1779  * Compute the set of live variables at each node in a given statement
1780  * or subtree of a statement moving backward from startNode to endNode
1781  */
1782
1783 void Compiler::fgComputeLife(VARSET_TP&       life,
1784                              GenTree*         startNode,
1785                              GenTree*         endNode,
1786                              VARSET_VALARG_TP volatileVars,
1787                              bool* pStmtInfoDirty DEBUGARG(bool* treeModf))
1788 {
1789     GenTree* tree;
1790
1791     // Don't kill vars in scope
1792     VARSET_TP keepAliveVars(VarSetOps::Union(this, volatileVars, compCurBB->bbScope));
1793
1794     noway_assert(VarSetOps::IsSubset(this, keepAliveVars, life));
1795     noway_assert(compCurStmt->gtOper == GT_STMT);
1796     noway_assert(endNode || (startNode == compCurStmt->gtStmt.gtStmtExpr));
1797
1798     // NOTE: Live variable analysis will not work if you try
1799     // to use the result of an assignment node directly!
1800     for (tree = startNode; tree != endNode; tree = tree->gtPrev)
1801     {
1802     AGAIN:
1803         assert(tree->OperGet() != GT_QMARK);
1804
1805         if (tree->gtOper == GT_CALL)
1806         {
1807             fgComputeLifeCall(life, tree->AsCall());
1808         }
1809         else if (tree->OperIsNonPhiLocal() || tree->OperIsLocalAddr())
1810         {
1811             bool isDeadStore = fgComputeLifeLocal(life, keepAliveVars, tree);
1812             if (isDeadStore)
1813             {
1814                 LclVarDsc* varDsc = &lvaTable[tree->gtLclVarCommon.gtLclNum];
1815
1816                 bool doAgain = false;
1817                 if (fgRemoveDeadStore(&tree, varDsc, life, &doAgain, pStmtInfoDirty DEBUGARG(treeModf)))
1818                 {
1819                     assert(!doAgain);
1820                     break;
1821                 }
1822
1823                 if (doAgain)
1824                 {
1825                     goto AGAIN;
1826                 }
1827             }
1828         }
1829     }
1830 }
1831
1832 void Compiler::fgComputeLifeLIR(VARSET_TP& life, BasicBlock* block, VARSET_VALARG_TP volatileVars)
1833 {
1834     // Don't kill volatile vars and vars in scope.
1835     VARSET_TP keepAliveVars(VarSetOps::Union(this, volatileVars, block->bbScope));
1836
1837     noway_assert(VarSetOps::IsSubset(this, keepAliveVars, life));
1838
1839     LIR::Range& blockRange      = LIR::AsRange(block);
1840     GenTree*    firstNonPhiNode = blockRange.FirstNonPhiNode();
1841     if (firstNonPhiNode == nullptr)
1842     {
1843         return;
1844     }
1845     for (GenTree *node = blockRange.LastNode(), *next = nullptr, *end = firstNonPhiNode->gtPrev; node != end;
1846          node = next)
1847     {
1848         next = node->gtPrev;
1849
1850         bool isDeadStore;
1851         switch (node->OperGet())
1852         {
1853             case GT_CALL:
1854             {
1855                 GenTreeCall* const call = node->AsCall();
1856                 if (((call->TypeGet() == TYP_VOID) || call->IsUnusedValue()) && !call->HasSideEffects(this))
1857                 {
1858                     JITDUMP("Removing dead call:\n");
1859                     DISPNODE(call);
1860
1861                     node->VisitOperands([](GenTree* operand) -> GenTree::VisitResult {
1862                         if (operand->IsValue())
1863                         {
1864                             operand->SetUnusedValue();
1865                         }
1866
1867                         // Special-case PUTARG_STK: since this operator is not considered a value, DCE will not remove
1868                         // these nodes.
1869                         if (operand->OperIs(GT_PUTARG_STK))
1870                         {
1871                             operand->AsPutArgStk()->gtOp1->SetUnusedValue();
1872                             operand->gtBashToNOP();
1873                         }
1874
1875                         return GenTree::VisitResult::Continue;
1876                     });
1877
1878                     blockRange.Remove(node);
1879
1880                     // Removing a call does not affect liveness unless it is a tail call in a nethod with P/Invokes or
1881                     // is itself a P/Invoke, in which case it may affect the liveness of the frame root variable.
1882                     if (!opts.MinOpts() && !opts.ShouldUsePInvokeHelpers() &&
1883                         ((call->IsTailCall() && info.compCallUnmanaged) || call->IsUnmanaged()) &&
1884                         lvaTable[info.compLvFrameListRoot].lvTracked)
1885                     {
1886                         fgStmtRemoved = true;
1887                     }
1888                 }
1889                 else
1890                 {
1891                     fgComputeLifeCall(life, call);
1892                 }
1893                 break;
1894             }
1895
1896             case GT_LCL_VAR:
1897             case GT_LCL_FLD:
1898             {
1899                 GenTreeLclVarCommon* const lclVarNode = node->AsLclVarCommon();
1900                 LclVarDsc&                 varDsc     = lvaTable[lclVarNode->gtLclNum];
1901
1902                 if (node->IsUnusedValue())
1903                 {
1904                     JITDUMP("Removing dead LclVar use:\n");
1905                     DISPNODE(lclVarNode);
1906
1907                     blockRange.Delete(this, block, node);
1908                     if (varDsc.lvTracked && !opts.MinOpts())
1909                     {
1910                         fgStmtRemoved = true;
1911                     }
1912                 }
1913                 else if (varDsc.lvTracked)
1914                 {
1915                     fgComputeLifeTrackedLocalUse(life, varDsc, lclVarNode);
1916                 }
1917                 else
1918                 {
1919                     fgComputeLifeUntrackedLocal(life, keepAliveVars, varDsc, lclVarNode);
1920                 }
1921                 break;
1922             }
1923
1924             case GT_LCL_VAR_ADDR:
1925             case GT_LCL_FLD_ADDR:
1926                 if (node->IsUnusedValue())
1927                 {
1928                     JITDUMP("Removing dead LclVar address:\n");
1929                     DISPNODE(node);
1930
1931                     const bool isTracked = lvaTable[node->AsLclVarCommon()->gtLclNum].lvTracked;
1932                     blockRange.Delete(this, block, node);
1933                     if (isTracked && !opts.MinOpts())
1934                     {
1935                         fgStmtRemoved = true;
1936                     }
1937                 }
1938                 else
1939                 {
1940                     isDeadStore = fgComputeLifeLocal(life, keepAliveVars, node);
1941                     if (isDeadStore)
1942                     {
1943                         LIR::Use addrUse;
1944                         if (blockRange.TryGetUse(node, &addrUse) && (addrUse.User()->OperGet() == GT_STOREIND))
1945                         {
1946                             // Remove the store. DCE will iteratively clean up any ununsed operands.
1947                             GenTreeStoreInd* const store = addrUse.User()->AsStoreInd();
1948
1949                             JITDUMP("Removing dead indirect store:\n");
1950                             DISPNODE(store);
1951
1952                             assert(store->Addr() == node);
1953                             blockRange.Delete(this, block, node);
1954
1955                             store->Data()->SetUnusedValue();
1956
1957                             blockRange.Remove(store);
1958
1959                             assert(!opts.MinOpts());
1960                             fgStmtRemoved = true;
1961                         }
1962                     }
1963                 }
1964                 break;
1965
1966             case GT_STORE_LCL_VAR:
1967             case GT_STORE_LCL_FLD:
1968             {
1969                 GenTreeLclVarCommon* const lclVarNode = node->AsLclVarCommon();
1970
1971                 LclVarDsc& varDsc = lvaTable[lclVarNode->gtLclNum];
1972                 if (varDsc.lvTracked)
1973                 {
1974                     isDeadStore = fgComputeLifeTrackedLocalDef(life, keepAliveVars, varDsc, lclVarNode);
1975                     if (isDeadStore)
1976                     {
1977                         JITDUMP("Removing dead store:\n");
1978                         DISPNODE(lclVarNode);
1979
1980                         // Remove the store. DCE will iteratively clean up any ununsed operands.
1981                         lclVarNode->gtOp1->SetUnusedValue();
1982
1983                         // If the store is marked as a late argument, it is referenced by a call. Instead of removing
1984                         // it, bash it to a NOP.
1985                         if ((node->gtFlags & GTF_LATE_ARG) != 0)
1986                         {
1987                             JITDUMP("node is a late arg; replacing with NOP\n");
1988                             node->gtBashToNOP();
1989
1990                             // NOTE: this is a bit of a hack. We need to keep these nodes around as they are
1991                             // referenced by the call, but they're considered side-effect-free non-value-producing
1992                             // nodes, so they will be removed if we don't do this.
1993                             node->gtFlags |= GTF_ORDER_SIDEEFF;
1994                         }
1995                         else
1996                         {
1997                             blockRange.Remove(node);
1998                         }
1999
2000                         assert(!opts.MinOpts());
2001                         fgStmtRemoved = true;
2002                     }
2003                 }
2004                 else
2005                 {
2006                     fgComputeLifeUntrackedLocal(life, keepAliveVars, varDsc, lclVarNode);
2007                 }
2008                 break;
2009             }
2010
2011             case GT_LABEL:
2012             case GT_FTN_ADDR:
2013             case GT_CNS_INT:
2014             case GT_CNS_LNG:
2015             case GT_CNS_DBL:
2016             case GT_CNS_STR:
2017             case GT_CLS_VAR_ADDR:
2018             case GT_PHYSREG:
2019                 // These are all side-effect-free leaf nodes.
2020                 if (node->IsUnusedValue())
2021                 {
2022                     JITDUMP("Removing dead node:\n");
2023                     DISPNODE(node);
2024
2025                     blockRange.Remove(node);
2026                 }
2027                 break;
2028
2029             case GT_LOCKADD:
2030             case GT_XADD:
2031             case GT_XCHG:
2032             case GT_CMPXCHG:
2033             case GT_MEMORYBARRIER:
2034             case GT_JMP:
2035             case GT_STOREIND:
2036             case GT_ARR_BOUNDS_CHECK:
2037             case GT_STORE_OBJ:
2038             case GT_STORE_BLK:
2039             case GT_STORE_DYN_BLK:
2040 #if defined(FEATURE_SIMD)
2041             case GT_SIMD_CHK:
2042 #endif // FEATURE_SIMD
2043 #ifdef FEATURE_HW_INTRINSICS
2044             case GT_HW_INTRINSIC_CHK:
2045 #endif // FEATURE_HW_INTRINSICS
2046             case GT_JCMP:
2047             case GT_CMP:
2048             case GT_JCC:
2049             case GT_JTRUE:
2050             case GT_RETURN:
2051             case GT_SWITCH:
2052             case GT_RETFILT:
2053             case GT_START_NONGC:
2054             case GT_START_PREEMPTGC:
2055             case GT_PROF_HOOK:
2056 #if !FEATURE_EH_FUNCLETS
2057             case GT_END_LFIN:
2058 #endif // !FEATURE_EH_FUNCLETS
2059             case GT_SWITCH_TABLE:
2060             case GT_PINVOKE_PROLOG:
2061             case GT_PINVOKE_EPILOG:
2062             case GT_RETURNTRAP:
2063             case GT_PUTARG_STK:
2064             case GT_IL_OFFSET:
2065 #ifdef FEATURE_HW_INTRINSICS
2066             case GT_HWIntrinsic:
2067 #endif // FEATURE_HW_INTRINSICS
2068                 // Never remove these nodes, as they are always side-effecting.
2069                 //
2070                 // NOTE: the only side-effect of some of these nodes (GT_CMP, GT_SUB_HI) is a write to the flags
2071                 // register.
2072                 // Properly modeling this would allow these nodes to be removed.
2073                 break;
2074
2075             case GT_NOP:
2076                 // NOTE: we need to keep some NOPs around because they are referenced by calls. See the dead store
2077                 // removal code above (case GT_STORE_LCL_VAR) for more explanation.
2078                 if ((node->gtFlags & GTF_ORDER_SIDEEFF) != 0)
2079                 {
2080                     break;
2081                 }
2082                 __fallthrough;
2083
2084             default:
2085                 assert(!node->OperIsLocal());
2086                 if (!node->IsValue() || node->IsUnusedValue())
2087                 {
2088                     // We are only interested in avoiding the removal of nodes with direct side-effects
2089                     // (as opposed to side effects of their children).
2090                     // This default case should never include calls or assignments.
2091                     assert(!node->OperRequiresAsgFlag() && !node->OperIs(GT_CALL));
2092                     if (!node->gtSetFlags() && !node->OperMayThrow(this))
2093                     {
2094                         JITDUMP("Removing dead node:\n");
2095                         DISPNODE(node);
2096
2097                         node->VisitOperands([](GenTree* operand) -> GenTree::VisitResult {
2098                             operand->SetUnusedValue();
2099                             return GenTree::VisitResult::Continue;
2100                         });
2101
2102                         blockRange.Remove(node);
2103                     }
2104                 }
2105                 break;
2106         }
2107     }
2108 }
2109
2110 // fgRemoveDeadStore - remove a store to a local which has no exposed uses.
2111 //
2112 //   pTree          - GenTree** to local, including store-form local or local addr (post-rationalize)
2113 //   varDsc         - var that is being stored to
2114 //   life           - current live tracked vars (maintained as we walk backwards)
2115 //   doAgain        - out parameter, true if we should restart the statement
2116 //   pStmtInfoDirty - should defer the cost computation to the point after the reverse walk is completed?
2117 //
2118 // Returns: true if we should skip the rest of the statement, false if we should continue
2119
2120 bool Compiler::fgRemoveDeadStore(GenTree**        pTree,
2121                                  LclVarDsc*       varDsc,
2122                                  VARSET_VALARG_TP life,
2123                                  bool*            doAgain,
2124                                  bool* pStmtInfoDirty DEBUGARG(bool* treeModf))
2125 {
2126     assert(!compRationalIRForm);
2127
2128     // Vars should have already been checked for address exposure by this point.
2129     assert(!varDsc->lvIsStructField || !lvaTable[varDsc->lvParentLcl].lvAddrExposed);
2130     assert(!varDsc->lvAddrExposed);
2131
2132     GenTree*       asgNode  = nullptr;
2133     GenTree*       rhsNode  = nullptr;
2134     GenTree*       addrNode = nullptr;
2135     GenTree* const tree     = *pTree;
2136
2137     GenTree* nextNode = tree->gtNext;
2138
2139     // First, characterize the lclVarTree and see if we are taking its address.
2140     if (tree->OperIsLocalStore())
2141     {
2142         rhsNode = tree->gtOp.gtOp1;
2143         asgNode = tree;
2144     }
2145     else if (tree->OperIsLocal())
2146     {
2147         if (nextNode == nullptr)
2148         {
2149             return false;
2150         }
2151         if (nextNode->OperGet() == GT_ADDR)
2152         {
2153             addrNode = nextNode;
2154             nextNode = nextNode->gtNext;
2155         }
2156     }
2157     else
2158     {
2159         assert(tree->OperIsLocalAddr());
2160         addrNode = tree;
2161     }
2162
2163     // Next, find the assignment.
2164     if (asgNode == nullptr)
2165     {
2166         if (addrNode == nullptr)
2167         {
2168             asgNode = nextNode;
2169         }
2170         else if (asgNode == nullptr)
2171         {
2172             // This may be followed by GT_IND/assign or GT_STOREIND.
2173             if (nextNode == nullptr)
2174             {
2175                 return false;
2176             }
2177             if (nextNode->OperIsIndir())
2178             {
2179                 // This must be a non-nullcheck form of indir, or it would not be a def.
2180                 assert(nextNode->OperGet() != GT_NULLCHECK);
2181                 if (nextNode->OperIsStore())
2182                 {
2183                     asgNode = nextNode;
2184                     if (asgNode->OperIsBlk())
2185                     {
2186                         rhsNode = asgNode->AsBlk()->Data();
2187                     }
2188                     // TODO-1stClassStructs: There should be an else clause here to handle
2189                     // the non-block forms of store ops (GT_STORE_LCL_VAR, etc.) for which
2190                     // rhsNode is op1. (This isn't really a 1stClassStructs item, but the
2191                     // above was added to catch what used to be dead block ops, and that
2192                     // made this omission apparent.)
2193                 }
2194                 else
2195                 {
2196                     asgNode = nextNode->gtNext;
2197                 }
2198             }
2199         }
2200     }
2201
2202     if (asgNode == nullptr)
2203     {
2204         return false;
2205     }
2206
2207     if (asgNode->OperIs(GT_ASG))
2208     {
2209         rhsNode = asgNode->gtGetOp2();
2210     }
2211     else if (rhsNode == nullptr)
2212     {
2213         return false;
2214     }
2215
2216     if (asgNode && (asgNode->gtFlags & GTF_ASG))
2217     {
2218         noway_assert(rhsNode);
2219         noway_assert(tree->gtFlags & GTF_VAR_DEF);
2220
2221         assert(asgNode->OperIs(GT_ASG));
2222
2223         // Do not remove if this local variable represents
2224         // a promoted struct field of an address exposed local.
2225         if (varDsc->lvIsStructField && lvaTable[varDsc->lvParentLcl].lvAddrExposed)
2226         {
2227             return false;
2228         }
2229
2230         // Do not remove if the address of the variable has been exposed.
2231         if (varDsc->lvAddrExposed)
2232         {
2233             return false;
2234         }
2235
2236         /* Test for interior statement */
2237
2238         if (asgNode->gtNext == nullptr)
2239         {
2240             /* This is a "NORMAL" statement with the
2241              * assignment node hanging from the GT_STMT node */
2242
2243             noway_assert(compCurStmt->gtStmt.gtStmtExpr == asgNode);
2244             JITDUMP("top level assign\n");
2245
2246             /* Check for side effects */
2247
2248             if (rhsNode->gtFlags & GTF_SIDE_EFFECT)
2249             {
2250             EXTRACT_SIDE_EFFECTS:
2251                 /* Extract the side effects */
2252
2253                 GenTree* sideEffList = nullptr;
2254 #ifdef DEBUG
2255                 if (verbose)
2256                 {
2257                     printf(FMT_BB " - Dead assignment has side effects...\n", compCurBB->bbNum);
2258                     gtDispTree(asgNode);
2259                     printf("\n");
2260                 }
2261 #endif // DEBUG
2262                 if (rhsNode->TypeGet() == TYP_STRUCT)
2263                 {
2264                     // This is a block assignment. An indirection of the rhs is not considered to
2265                     // happen until the assignment, so we will extract the side effects from only
2266                     // the address.
2267                     if (rhsNode->OperIsIndir())
2268                     {
2269                         assert(rhsNode->OperGet() != GT_NULLCHECK);
2270                         rhsNode = rhsNode->AsIndir()->Addr();
2271                     }
2272                 }
2273                 gtExtractSideEffList(rhsNode, &sideEffList);
2274
2275                 if (sideEffList)
2276                 {
2277                     noway_assert(sideEffList->gtFlags & GTF_SIDE_EFFECT);
2278 #ifdef DEBUG
2279                     if (verbose)
2280                     {
2281                         printf("Extracted side effects list...\n");
2282                         gtDispTree(sideEffList);
2283                         printf("\n");
2284                     }
2285 #endif // DEBUG
2286
2287                     /* Replace the assignment statement with the list of side effects */
2288                     noway_assert(sideEffList->gtOper != GT_STMT);
2289
2290                     *pTree = compCurStmt->gtStmt.gtStmtExpr = sideEffList;
2291 #ifdef DEBUG
2292                     *treeModf = true;
2293 #endif // DEBUG
2294                     /* Update ordering, costs, FP levels, etc. */
2295                     gtSetStmtInfo(compCurStmt);
2296
2297                     /* Re-link the nodes for this statement */
2298                     fgSetStmtSeq(compCurStmt);
2299
2300                     // Since the whole statement gets replaced it is safe to
2301                     // re-thread and update order. No need to compute costs again.
2302                     *pStmtInfoDirty = false;
2303
2304                     /* Compute the live set for the new statement */
2305                     *doAgain = true;
2306                     return false;
2307                 }
2308                 else
2309                 {
2310                     /* No side effects, most likely we forgot to reset some flags */
2311                     fgRemoveStmt(compCurBB, compCurStmt);
2312
2313                     return true;
2314                 }
2315             }
2316             else
2317             {
2318                 /* If this is GT_CATCH_ARG saved to a local var don't bother */
2319
2320                 JITDUMP("removing stmt with no side effects\n");
2321
2322                 if (asgNode->gtFlags & GTF_ORDER_SIDEEFF)
2323                 {
2324                     if (rhsNode->gtOper == GT_CATCH_ARG)
2325                     {
2326                         goto EXTRACT_SIDE_EFFECTS;
2327                     }
2328                 }
2329
2330                 /* No side effects - remove the whole statement from the block->bbTreeList */
2331
2332                 fgRemoveStmt(compCurBB, compCurStmt);
2333
2334                 /* Since we removed it do not process the rest (i.e. RHS) of the statement
2335                  * variables in the RHS will not be marked as live, so we get the benefit of
2336                  * propagating dead variables up the chain */
2337
2338                 return true;
2339             }
2340         }
2341         else
2342         {
2343             /* This is an INTERIOR STATEMENT with a dead assignment - remove it */
2344
2345             noway_assert(!VarSetOps::IsMember(this, life, varDsc->lvVarIndex));
2346
2347             if (rhsNode->gtFlags & GTF_SIDE_EFFECT)
2348             {
2349                 /* :-( we have side effects */
2350
2351                 GenTree* sideEffList = nullptr;
2352 #ifdef DEBUG
2353                 if (verbose)
2354                 {
2355                     printf(FMT_BB " - INTERIOR dead assignment has side effects...\n", compCurBB->bbNum);
2356                     gtDispTree(asgNode);
2357                     printf("\n");
2358                 }
2359 #endif // DEBUG
2360                 gtExtractSideEffList(rhsNode, &sideEffList);
2361
2362                 if (!sideEffList)
2363                 {
2364                     goto NO_SIDE_EFFECTS;
2365                 }
2366
2367                 noway_assert(sideEffList->gtFlags & GTF_SIDE_EFFECT);
2368 #ifdef DEBUG
2369                 if (verbose)
2370                 {
2371                     printf("Extracted side effects list from condition...\n");
2372                     gtDispTree(sideEffList);
2373                     printf("\n");
2374                 }
2375 #endif // DEBUG
2376                 if (sideEffList->gtOper == asgNode->gtOper)
2377                 {
2378 #ifdef DEBUG
2379                     *treeModf = true;
2380 #endif // DEBUG
2381                     asgNode->gtOp.gtOp1 = sideEffList->gtOp.gtOp1;
2382                     asgNode->gtOp.gtOp2 = sideEffList->gtOp.gtOp2;
2383                     asgNode->gtType     = sideEffList->gtType;
2384                 }
2385                 else
2386                 {
2387 #ifdef DEBUG
2388                     *treeModf = true;
2389 #endif // DEBUG
2390                     /* Change the node to a GT_COMMA holding the side effect list */
2391                     asgNode->gtBashToNOP();
2392
2393                     asgNode->ChangeOper(GT_COMMA);
2394                     asgNode->gtFlags |= sideEffList->gtFlags & GTF_ALL_EFFECT;
2395
2396                     if (sideEffList->gtOper == GT_COMMA)
2397                     {
2398                         asgNode->gtOp.gtOp1 = sideEffList->gtOp.gtOp1;
2399                         asgNode->gtOp.gtOp2 = sideEffList->gtOp.gtOp2;
2400                     }
2401                     else
2402                     {
2403                         asgNode->gtOp.gtOp1 = sideEffList;
2404                         asgNode->gtOp.gtOp2 = gtNewNothingNode();
2405                     }
2406                 }
2407             }
2408             else
2409             {
2410             NO_SIDE_EFFECTS:
2411 #ifdef DEBUG
2412                 if (verbose)
2413                 {
2414                     printf("\nRemoving tree ");
2415                     printTreeID(asgNode);
2416                     printf(" in " FMT_BB " as useless\n", compCurBB->bbNum);
2417                     gtDispTree(asgNode);
2418                     printf("\n");
2419                 }
2420 #endif // DEBUG
2421                 /* No side effects - Change the assignment to a GT_NOP node */
2422                 asgNode->gtBashToNOP();
2423
2424 #ifdef DEBUG
2425                 *treeModf = true;
2426 #endif // DEBUG
2427             }
2428
2429             /* Re-link the nodes for this statement - Do not update ordering! */
2430
2431             // Do not update costs by calling gtSetStmtInfo. fgSetStmtSeq modifies
2432             // the tree threading based on the new costs. Removing nodes could
2433             // cause a subtree to get evaluated first (earlier second) during the
2434             // liveness walk. Instead just set a flag that costs are dirty and
2435             // caller has to call gtSetStmtInfo.
2436             *pStmtInfoDirty = true;
2437
2438             fgSetStmtSeq(compCurStmt);
2439
2440             /* Continue analysis from this node */
2441
2442             *pTree = asgNode;
2443
2444             return false;
2445         }
2446     }
2447     return false;
2448 }
2449
2450 /*****************************************************************************
2451  *
2452  *  Iterative data flow for live variable info and availability of range
2453  *  check index expressions.
2454  */
2455 void Compiler::fgInterBlockLocalVarLiveness()
2456 {
2457 #ifdef DEBUG
2458     if (verbose)
2459     {
2460         printf("*************** In fgInterBlockLocalVarLiveness()\n");
2461     }
2462 #endif
2463
2464     /* This global flag is set whenever we remove a statement */
2465
2466     fgStmtRemoved = false;
2467
2468     // keep track if a bbLiveIn changed due to dead store removal
2469     fgLocalVarLivenessChanged = false;
2470
2471     /* Compute the IN and OUT sets for tracked variables */
2472
2473     fgLiveVarAnalysis();
2474
2475     /* For debuggable code, we mark vars as live over their entire
2476      * reported scope, so that it will be visible over the entire scope
2477      */
2478
2479     if (opts.compDbgCode && (info.compVarScopesCount > 0))
2480     {
2481         fgExtendDbgLifetimes();
2482     }
2483
2484     // Nothing more to be done if the backend does not require accurate local var lifetimes.
2485     if (!backendRequiresLocalVarLifetimes())
2486     {
2487         fgLocalVarLivenessDone = true;
2488         return;
2489     }
2490
2491     /*-------------------------------------------------------------------------
2492      * Variables involved in exception-handlers and finally blocks need
2493      * to be specially marked
2494      */
2495     BasicBlock* block;
2496
2497     VARSET_TP exceptVars(VarSetOps::MakeEmpty(this));  // vars live on entry to a handler
2498     VARSET_TP finallyVars(VarSetOps::MakeEmpty(this)); // vars live on exit of a 'finally' block
2499     VARSET_TP filterVars(VarSetOps::MakeEmpty(this));  // vars live on exit from a 'filter'
2500
2501     for (block = fgFirstBB; block; block = block->bbNext)
2502     {
2503         if (block->bbCatchTyp != BBCT_NONE)
2504         {
2505             /* Note the set of variables live on entry to exception handler */
2506             VarSetOps::UnionD(this, exceptVars, block->bbLiveIn);
2507         }
2508
2509         if (block->bbJumpKind == BBJ_EHFILTERRET)
2510         {
2511             /* Get the set of live variables on exit from a 'filter' */
2512             VarSetOps::UnionD(this, filterVars, block->bbLiveOut);
2513         }
2514         else if (block->bbJumpKind == BBJ_EHFINALLYRET)
2515         {
2516             /* Get the set of live variables on exit from a 'finally' block */
2517
2518             VarSetOps::UnionD(this, finallyVars, block->bbLiveOut);
2519         }
2520 #if FEATURE_EH_FUNCLETS
2521         // Funclets are called and returned from, as such we can only count on the frame
2522         // pointer being restored, and thus everything live in or live out must be on the
2523         // stack
2524         if (block->bbFlags & BBF_FUNCLET_BEG)
2525         {
2526             VarSetOps::UnionD(this, exceptVars, block->bbLiveIn);
2527         }
2528         if ((block->bbJumpKind == BBJ_EHFINALLYRET) || (block->bbJumpKind == BBJ_EHFILTERRET) ||
2529             (block->bbJumpKind == BBJ_EHCATCHRET))
2530         {
2531             VarSetOps::UnionD(this, exceptVars, block->bbLiveOut);
2532         }
2533 #endif // FEATURE_EH_FUNCLETS
2534     }
2535
2536     LclVarDsc* varDsc;
2537     unsigned   varNum;
2538
2539     for (varNum = 0, varDsc = lvaTable; varNum < lvaCount; varNum++, varDsc++)
2540     {
2541         /* Ignore the variable if it's not tracked */
2542
2543         if (!varDsc->lvTracked)
2544         {
2545             continue;
2546         }
2547
2548         if (lvaIsFieldOfDependentlyPromotedStruct(varDsc))
2549         {
2550             continue;
2551         }
2552
2553         /* Un-init locals may need auto-initialization. Note that the
2554            liveness of such locals will bubble to the top (fgFirstBB)
2555            in fgInterBlockLocalVarLiveness() */
2556
2557         if (!varDsc->lvIsParam && VarSetOps::IsMember(this, fgFirstBB->bbLiveIn, varDsc->lvVarIndex) &&
2558             (info.compInitMem || varTypeIsGC(varDsc->TypeGet())))
2559         {
2560             varDsc->lvMustInit = true;
2561         }
2562
2563         // Mark all variables that are live on entry to an exception handler
2564         // or on exit from a filter handler or finally as DoNotEnregister */
2565
2566         if (VarSetOps::IsMember(this, exceptVars, varDsc->lvVarIndex) ||
2567             VarSetOps::IsMember(this, filterVars, varDsc->lvVarIndex))
2568         {
2569             /* Mark the variable appropriately */
2570             lvaSetVarDoNotEnregister(varNum DEBUGARG(DNER_LiveInOutOfHandler));
2571         }
2572
2573         /* Mark all pointer variables live on exit from a 'finally'
2574            block as either volatile for non-GC ref types or as
2575            'explicitly initialized' (volatile and must-init) for GC-ref types */
2576
2577         if (VarSetOps::IsMember(this, finallyVars, varDsc->lvVarIndex))
2578         {
2579             lvaSetVarDoNotEnregister(varNum DEBUGARG(DNER_LiveInOutOfHandler));
2580
2581             /* Don't set lvMustInit unless we have a non-arg, GC pointer */
2582
2583             if (varDsc->lvIsParam)
2584             {
2585                 continue;
2586             }
2587
2588             if (!varTypeIsGC(varDsc->TypeGet()))
2589             {
2590                 continue;
2591             }
2592
2593             /* Mark it */
2594             varDsc->lvMustInit = true;
2595         }
2596     }
2597
2598     /*-------------------------------------------------------------------------
2599      * Now fill in liveness info within each basic block - Backward DataFlow
2600      */
2601
2602     for (block = fgFirstBB; block; block = block->bbNext)
2603     {
2604         /* Tell everyone what block we're working on */
2605
2606         compCurBB = block;
2607
2608         /* Remember those vars live on entry to exception handlers */
2609         /* if we are part of a try block */
2610
2611         VARSET_TP volatileVars(VarSetOps::MakeEmpty(this));
2612
2613         if (ehBlockHasExnFlowDsc(block))
2614         {
2615             VarSetOps::Assign(this, volatileVars, fgGetHandlerLiveVars(block));
2616
2617             // volatileVars is a subset of exceptVars
2618             noway_assert(VarSetOps::IsSubset(this, volatileVars, exceptVars));
2619         }
2620
2621         /* Start with the variables live on exit from the block */
2622
2623         VARSET_TP life(VarSetOps::MakeCopy(this, block->bbLiveOut));
2624
2625         /* Mark any interference we might have at the end of the block */
2626
2627         if (block->IsLIR())
2628         {
2629             fgComputeLifeLIR(life, block, volatileVars);
2630         }
2631         else
2632         {
2633             /* Get the first statement in the block */
2634
2635             GenTree* firstStmt = block->FirstNonPhiDef();
2636
2637             if (firstStmt == nullptr)
2638             {
2639                 continue;
2640             }
2641
2642             /* Walk all the statements of the block backwards - Get the LAST stmt */
2643
2644             GenTree* nextStmt = block->bbTreeList->gtPrev;
2645
2646             do
2647             {
2648 #ifdef DEBUG
2649                 bool treeModf = false;
2650 #endif // DEBUG
2651                 noway_assert(nextStmt);
2652                 noway_assert(nextStmt->gtOper == GT_STMT);
2653
2654                 compCurStmt = nextStmt;
2655                 nextStmt    = nextStmt->gtPrev;
2656
2657                 /* Compute the liveness for each tree node in the statement */
2658                 bool stmtInfoDirty = false;
2659
2660                 fgComputeLife(life, compCurStmt->gtStmt.gtStmtExpr, nullptr, volatileVars,
2661                               &stmtInfoDirty DEBUGARG(&treeModf));
2662
2663                 if (stmtInfoDirty)
2664                 {
2665                     gtSetStmtInfo(compCurStmt);
2666                     fgSetStmtSeq(compCurStmt);
2667                     gtUpdateStmtSideEffects(compCurStmt);
2668                 }
2669
2670 #ifdef DEBUG
2671                 if (verbose && treeModf)
2672                 {
2673                     printf("\nfgComputeLife modified tree:\n");
2674                     gtDispTree(compCurStmt->gtStmt.gtStmtExpr);
2675                     printf("\n");
2676                 }
2677 #endif // DEBUG
2678             } while (compCurStmt != firstStmt);
2679         }
2680
2681         /* Done with the current block - if we removed any statements, some
2682          * variables may have become dead at the beginning of the block
2683          * -> have to update bbLiveIn */
2684
2685         if (!VarSetOps::Equal(this, life, block->bbLiveIn))
2686         {
2687             /* some variables have become dead all across the block
2688                So life should be a subset of block->bbLiveIn */
2689
2690             // We changed the liveIn of the block, which may affect liveOut of others,
2691             // which may expose more dead stores.
2692             fgLocalVarLivenessChanged = true;
2693
2694             noway_assert(VarSetOps::IsSubset(this, life, block->bbLiveIn));
2695
2696             /* set the new bbLiveIn */
2697
2698             VarSetOps::Assign(this, block->bbLiveIn, life);
2699
2700             /* compute the new bbLiveOut for all the predecessors of this block */
2701         }
2702
2703         noway_assert(compCurBB == block);
2704 #ifdef DEBUG
2705         compCurBB = nullptr;
2706 #endif
2707     }
2708
2709     fgLocalVarLivenessDone = true;
2710 }
2711
2712 #ifdef DEBUG
2713
2714 /*****************************************************************************/
2715
2716 void Compiler::fgDispBBLiveness(BasicBlock* block)
2717 {
2718     VARSET_TP allVars(VarSetOps::Union(this, block->bbLiveIn, block->bbLiveOut));
2719     printf(FMT_BB, block->bbNum);
2720     printf(" IN (%d)=", VarSetOps::Count(this, block->bbLiveIn));
2721     lvaDispVarSet(block->bbLiveIn, allVars);
2722     for (MemoryKind memoryKind : allMemoryKinds())
2723     {
2724         if ((block->bbMemoryLiveIn & memoryKindSet(memoryKind)) != 0)
2725         {
2726             printf(" + %s", memoryKindNames[memoryKind]);
2727         }
2728     }
2729     printf("\n     OUT(%d)=", VarSetOps::Count(this, block->bbLiveOut));
2730     lvaDispVarSet(block->bbLiveOut, allVars);
2731     for (MemoryKind memoryKind : allMemoryKinds())
2732     {
2733         if ((block->bbMemoryLiveOut & memoryKindSet(memoryKind)) != 0)
2734         {
2735             printf(" + %s", memoryKindNames[memoryKind]);
2736         }
2737     }
2738     printf("\n\n");
2739 }
2740
2741 void Compiler::fgDispBBLiveness()
2742 {
2743     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
2744     {
2745         fgDispBBLiveness(block);
2746     }
2747 }
2748
2749 #endif // DEBUG