src/jit/regset.cpp

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 /*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   6 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   7 XX                                                                           XX
   8 XX                           RegSet                                          XX
   9 XX                                                                           XX
  10 XX  Represents the register set, and their states during code generation     XX
  11 XX  Can select an unused register, keeps track of the contents of the        XX
  12 XX  registers, and can spill registers                                       XX
  13 XX                                                                           XX
  14 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  15 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  16 */
  17
  18 #include "jitpch.h"
  19 #ifdef _MSC_VER
  20 #pragma hdrstop
  21 #endif
  22
  23 #include "emit.h"
  24
  25 /*****************************************************************************/
  26
  27 #ifdef _TARGET_ARM64_
  28 const regMaskSmall regMasks[] = {
  29 #define REGDEF(name, rnum, mask, xname, wname) mask,
  30 #include "register.h"
  31 };
  32 #else // !_TARGET_ARM64_
  33 const regMaskSmall regMasks[] = {
  34 #define REGDEF(name, rnum, mask, sname) mask,
  35 #include "register.h"
  36 };
  37 #endif
  38
  39 #ifdef _TARGET_X86_
  40 const regMaskSmall regFPMasks[] = {
  41 #define REGDEF(name, rnum, mask, sname) mask,
  42 #include "registerfp.h"
  43 };
  44 #endif // _TARGET_X86_
  45
  46 /*
  47 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  48 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  49 XX                          RegSet                                           XX
  50 XX                                                                           XX
  51 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  52 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  53 */
  54
  55 void RegSet::rsClearRegsModified()
  56 {
  57 #ifndef LEGACY_BACKEND
  58     assert(m_rsCompiler->lvaDoneFrameLayout < Compiler::FINAL_FRAME_LAYOUT);
  59 #endif // !LEGACY_BACKEND
  60
  61 #ifdef DEBUG
  62     if (m_rsCompiler->verbose)
  63     {
  64         printf("Clearing modified regs.\n");
  65     }
  66     rsModifiedRegsMaskInitialized = true;
  67 #endif // DEBUG
  68
  69     rsModifiedRegsMask = RBM_NONE;
  70 }
  71
  72 void RegSet::rsSetRegsModified(regMaskTP mask DEBUGARG(bool suppressDump))
  73 {
  74     assert(mask != RBM_NONE);
  75     assert(rsModifiedRegsMaskInitialized);
  76
  77 #ifndef LEGACY_BACKEND
  78     // We can't update the modified registers set after final frame layout (that is, during code
  79     // generation and after). Ignore prolog and epilog generation: they call register tracking to
  80     // modify rbp, for example, even in functions that use rbp as a frame pointer. Make sure normal
  81     // code generation isn't actually adding to set of modified registers.
  82     // Frame layout is only affected by callee-saved registers, so only ensure that callee-saved
  83     // registers aren't modified after final frame layout.
  84     assert((m_rsCompiler->lvaDoneFrameLayout < Compiler::FINAL_FRAME_LAYOUT) || m_rsCompiler->compGeneratingProlog ||
  85            m_rsCompiler->compGeneratingEpilog ||
  86            (((rsModifiedRegsMask | mask) & RBM_CALLEE_SAVED) == (rsModifiedRegsMask & RBM_CALLEE_SAVED)));
  87 #endif // !LEGACY_BACKEND
  88
  89 #ifdef DEBUG
  90     if (m_rsCompiler->verbose && !suppressDump)
  91     {
  92         if (rsModifiedRegsMask != (rsModifiedRegsMask | mask))
  93         {
  94             printf("Marking regs modified: ");
  95             dspRegMask(mask);
  96             printf(" (");
  97             dspRegMask(rsModifiedRegsMask);
  98             printf(" => ");
  99             dspRegMask(rsModifiedRegsMask | mask);
 100             printf(")\n");
 101         }
 102     }
 103 #endif // DEBUG
 104
 105     rsModifiedRegsMask |= mask;
 106 }
 107
 108 void RegSet::rsRemoveRegsModified(regMaskTP mask)
 109 {
 110     assert(mask != RBM_NONE);
 111     assert(rsModifiedRegsMaskInitialized);
 112
 113 #ifndef LEGACY_BACKEND
 114     // See comment in rsSetRegsModified().
 115     assert((m_rsCompiler->lvaDoneFrameLayout < Compiler::FINAL_FRAME_LAYOUT) || m_rsCompiler->compGeneratingProlog ||
 116            m_rsCompiler->compGeneratingEpilog ||
 117            (((rsModifiedRegsMask & ~mask) & RBM_CALLEE_SAVED) == (rsModifiedRegsMask & RBM_CALLEE_SAVED)));
 118 #endif // !LEGACY_BACKEND
 119
 120 #ifdef DEBUG
 121     if (m_rsCompiler->verbose)
 122     {
 123         printf("Removing modified regs: ");
 124         dspRegMask(mask);
 125         if (rsModifiedRegsMask == (rsModifiedRegsMask & ~mask))
 126         {
 127             printf(" (unchanged)");
 128         }
 129         else
 130         {
 131             printf(" (");
 132             dspRegMask(rsModifiedRegsMask);
 133             printf(" => ");
 134             dspRegMask(rsModifiedRegsMask & ~mask);
 135             printf(")");
 136         }
 137         printf("\n");
 138     }
 139 #endif // DEBUG
 140
 141     rsModifiedRegsMask &= ~mask;
 142 }
 143
 144 void RegSet::SetMaskVars(regMaskTP newMaskVars)
 145 {
 146 #ifdef DEBUG
 147     if (m_rsCompiler->verbose)
 148     {
 149         printf("\t\t\t\t\t\t\tLive regs: ");
 150         if (_rsMaskVars == newMaskVars)
 151         {
 152             printf("(unchanged) ");
 153         }
 154         else
 155         {
 156             printRegMaskInt(_rsMaskVars);
 157             m_rsCompiler->getEmitter()->emitDispRegSet(_rsMaskVars);
 158             printf(" => ");
 159         }
 160         printRegMaskInt(newMaskVars);
 161         m_rsCompiler->getEmitter()->emitDispRegSet(newMaskVars);
 162         printf("\n");
 163     }
 164 #endif // DEBUG
 165
 166     _rsMaskVars = newMaskVars;
 167 }
 168
 169 #ifdef DEBUG
 170
 171 RegSet::rsStressRegsType RegSet::rsStressRegs()
 172 {
 173 #ifndef LEGACY_BACKEND
 174     return RS_STRESS_NONE;
 175 #else  // LEGACY_BACKEND
 176     rsStressRegsType val = (rsStressRegsType)JitConfig.JitStressRegs();
 177     if (val == RS_STRESS_NONE && m_rsCompiler->compStressCompile(Compiler::STRESS_REGS, 15))
 178         val = RS_PICK_BAD_REG;
 179     return val;
 180 #endif // LEGACY_BACKEND
 181 }
 182 #endif // DEBUG
 183
 184 #ifdef LEGACY_BACKEND
 185 /*****************************************************************************
 186  *  Includes 'includeHint' if 'regs' is empty
 187  */
 188
 189 regMaskTP RegSet::rsUseIfZero(regMaskTP regs, regMaskTP includeHint)
 190 {
 191     return regs ? regs : includeHint;
 192 }
 193
 194 /*****************************************************************************
 195  *  Excludes 'excludeHint' if it results in a non-empty mask
 196  */
 197
 198 regMaskTP RegSet::rsExcludeHint(regMaskTP regs, regMaskTP excludeHint)
 199 {
 200     regMaskTP OKmask = regs & ~excludeHint;
 201     return OKmask ? OKmask : regs;
 202 }
 203
 204 /*****************************************************************************
 205  *  Narrows choice by 'narrowHint' if it results in a non-empty mask
 206  */
 207
 208 regMaskTP RegSet::rsNarrowHint(regMaskTP regs, regMaskTP narrowHint)
 209 {
 210     regMaskTP narrowed = regs & narrowHint;
 211     return narrowed ? narrowed : regs;
 212 }
 213
 214 /*****************************************************************************
 215  *  Excludes 'exclude' from regs if non-zero, or from RBM_ALLINT
 216  */
 217
 218 regMaskTP RegSet::rsMustExclude(regMaskTP regs, regMaskTP exclude)
 219 {
 220     // Try to exclude from current set
 221     regMaskTP OKmask = regs & ~exclude;
 222
 223     // If current set wont work, exclude from RBM_ALLINT
 224     if (OKmask == RBM_NONE)
 225         OKmask = (RBM_ALLINT & ~exclude);
 226
 227     assert(OKmask);
 228
 229     return OKmask;
 230 }
 231
 232 /*****************************************************************************
 233  *
 234  *  The following returns a mask that yields all free registers.
 235  */
 236
 237 // inline
 238 regMaskTP RegSet::rsRegMaskFree()
 239 {
 240     /* Any register that is locked must also be marked as 'used' */
 241
 242     assert((rsMaskUsed & rsMaskLock) == rsMaskLock);
 243
 244     /* Any register that isn't used and doesn't hold a variable is free */
 245
 246     return RBM_ALLINT & ~(rsMaskUsed | rsMaskVars | rsMaskResvd);
 247 }
 248
 249 /*****************************************************************************
 250  *
 251  *  The following returns a mask of registers that may be grabbed.
 252  */
 253
 254 // inline
 255 regMaskTP RegSet::rsRegMaskCanGrab()
 256 {
 257     /* Any register that is locked must also be marked as 'used' */
 258
 259     assert((rsMaskUsed & rsMaskLock) == rsMaskLock);
 260
 261     /* Any register that isn't locked and doesn't hold a var can be grabbed */
 262
 263     regMaskTP result = (RBM_ALLINT & ~(rsMaskLock | rsMaskVars));
 264
 265 #ifdef _TARGET_ARM_
 266
 267     // On the ARM when we pass structs in registers we set the rsUsedTree[]
 268     // to be the full TYP_STRUCT tree, which doesn't allow us to spill/unspill
 269     // these argument registers.  To fix JitStress issues that can occur
 270     // when rsPickReg tries to spill one of these registers we just remove them
 271     // from the set of registers that we can grab
 272     //
 273     regMaskTP structArgMask = RBM_NONE;
 274     // Load all the variable arguments in registers back to their registers.
 275     for (regNumber reg = REG_ARG_FIRST; reg <= REG_ARG_LAST; reg = REG_NEXT(reg))
 276     {
 277         GenTree* regHolds = rsUsedTree[reg];
 278         if ((regHolds != NULL) && (regHolds->TypeGet() == TYP_STRUCT))
 279         {
 280             structArgMask |= genRegMask(reg);
 281         }
 282     }
 283     result &= ~structArgMask;
 284 #endif
 285
 286     return result;
 287 }
 288
 289 /*****************************************************************************
 290  *
 291  *  Pick a free register. It is guaranteed that a register is available.
 292  *  Note that rsPickReg() can spill a register, whereas rsPickFreeReg() will not.
 293  */
 294
 295 // inline
 296 regNumber RegSet::rsPickFreeReg(regMaskTP regMaskHint)
 297 {
 298     regMaskTP freeRegs = rsRegMaskFree();
 299     assert(freeRegs != RBM_NONE);
 300
 301     regMaskTP regs = rsNarrowHint(freeRegs, regMaskHint);
 302
 303     return rsGrabReg(regs);
 304 }
 305
 306 /*****************************************************************************
 307  *
 308  *  Mark the given set of registers as used and locked.
 309  */
 310
 311 // inline
 312 void RegSet::rsLockReg(regMaskTP regMask)
 313 {
 314     /* Must not be already marked as either used or locked */
 315
 316     assert((rsMaskUsed & regMask) == 0);
 317     rsMaskUsed |= regMask;
 318     assert((rsMaskLock & regMask) == 0);
 319     rsMaskLock |= regMask;
 320 }
 321
 322 /*****************************************************************************
 323  *
 324  *  Mark an already used set of registers as locked.
 325  */
 326
 327 // inline
 328 void RegSet::rsLockUsedReg(regMaskTP regMask)
 329 {
 330     /* Must not be already marked as locked. Must be already marked as used. */
 331
 332     assert((rsMaskLock & regMask) == 0);
 333     assert((rsMaskUsed & regMask) == regMask);
 334
 335     rsMaskLock |= regMask;
 336 }
 337
 338 /*****************************************************************************
 339  *
 340  *  Mark the given set of registers as no longer used/locked.
 341  */
 342
 343 // inline
 344 void RegSet::rsUnlockReg(regMaskTP regMask)
 345 {
 346     /* Must be currently marked as both used and locked */
 347
 348     assert((rsMaskUsed & regMask) == regMask);
 349     rsMaskUsed -= regMask;
 350     assert((rsMaskLock & regMask) == regMask);
 351     rsMaskLock -= regMask;
 352 }
 353
 354 /*****************************************************************************
 355  *
 356  *  Mark the given set of registers as no longer locked.
 357  */
 358
 359 // inline
 360 void RegSet::rsUnlockUsedReg(regMaskTP regMask)
 361 {
 362     /* Must be currently marked as both used and locked */
 363
 364     assert((rsMaskUsed & regMask) == regMask);
 365     assert((rsMaskLock & regMask) == regMask);
 366     rsMaskLock -= regMask;
 367 }
 368
 369 /*****************************************************************************
 370  *
 371  *  Mark the given set of registers as used and locked. It may already have
 372  *  been marked as used.
 373  */
 374
 375 // inline
 376 void RegSet::rsLockReg(regMaskTP regMask, regMaskTP* usedMask)
 377 {
 378     /* Is it already marked as used? */
 379
 380     regMaskTP used   = (rsMaskUsed & regMask);
 381     regMaskTP unused = (regMask & ~used);
 382
 383     if (used)
 384         rsLockUsedReg(used);
 385
 386     if (unused)
 387         rsLockReg(unused);
 388
 389     *usedMask = used;
 390 }
 391
 392 /*****************************************************************************
 393  *
 394  *  Mark the given set of registers as no longer
 395  */
 396
 397 // inline
 398 void RegSet::rsUnlockReg(regMaskTP regMask, regMaskTP usedMask)
 399 {
 400     regMaskTP unused = (regMask & ~usedMask);
 401
 402     if (usedMask)
 403         rsUnlockUsedReg(usedMask);
 404
 405     if (unused)
 406         rsUnlockReg(unused);
 407 }
 408 #endif // LEGACY_BACKEND
 409
 410 #ifdef LEGACY_BACKEND
 411 /*****************************************************************************
 412  *
 413  *  Assume all registers contain garbage (called at start of codegen and when
 414  *  we encounter a code label).
 415  */
 416
 417 // inline
 418 void RegTracker::rsTrackRegClr()
 419 {
 420     assert(RV_TRASH == 0);
 421     memset(rsRegValues, 0, sizeof(rsRegValues));
 422 }
 423 #endif // LEGACY_BACKEND
 424
 425 /*****************************************************************************
 426  *
 427  *  Trash the rsRegValues associated with a register
 428  */
 429
 430 // inline
 431 void RegTracker::rsTrackRegTrash(regNumber reg)
 432 {
 433     /* Keep track of which registers we ever touch */
 434
 435     regSet->rsSetRegsModified(genRegMask(reg));
 436
 437 #ifdef LEGACY_BACKEND
 438     /* Record the new value for the register */
 439
 440     rsRegValues[reg].rvdKind = RV_TRASH;
 441 #endif // LEGACY_BACKEND
 442 }
 443
 444 #ifdef LEGACY_BACKEND
 445 /*****************************************************************************
 446  *
 447  *  calls rsTrackRegTrash on the set of registers in regmask
 448  */
 449
 450 // inline
 451 void RegTracker::rsTrackRegMaskTrash(regMaskTP regMask)
 452 {
 453     regMaskTP regBit = 1;
 454
 455     for (regNumber regNum = REG_FIRST; regNum < REG_COUNT; regNum = REG_NEXT(regNum), regBit <<= 1)
 456     {
 457         if (regBit > regMask)
 458         {
 459             break;
 460         }
 461
 462         if (regBit & regMask)
 463         {
 464             rsTrackRegTrash(regNum);
 465         }
 466     }
 467 }
 468 #endif // LEGACY_BACKEND
 469
 470 /*****************************************************************************/
 471
 472 // inline
 473 void RegTracker::rsTrackRegIntCns(regNumber reg, ssize_t val)
 474 {
 475     assert(genIsValidIntReg(reg));
 476
 477     /* Keep track of which registers we ever touch */
 478
 479     regSet->rsSetRegsModified(genRegMask(reg));
 480
 481 #ifdef LEGACY_BACKEND
 482     /* Record the new value for the register */
 483
 484     rsRegValues[reg].rvdKind      = RV_INT_CNS;
 485     rsRegValues[reg].rvdIntCnsVal = val;
 486 #endif
 487 }
 488
 489 #ifdef LEGACY_BACKEND
 490 /*****************************************************************************/
 491
 492 // inline
 493 void RegTracker::rsTrackRegLclVarLng(regNumber reg, unsigned var, bool low)
 494 {
 495     assert(genIsValidIntReg(reg));
 496
 497     if (compiler->lvaTable[var].lvAddrExposed)
 498     {
 499         return;
 500     }
 501
 502     /* Keep track of which registers we ever touch */
 503
 504     regSet->rsSetRegsModified(genRegMask(reg));
 505
 506     /* Record the new value for the register */
 507
 508     rsRegValues[reg].rvdKind      = (low ? RV_LCL_VAR_LNG_LO : RV_LCL_VAR_LNG_HI);
 509     rsRegValues[reg].rvdLclVarNum = var;
 510 }
 511
 512 /*****************************************************************************/
 513
 514 // inline
 515 bool RegTracker::rsTrackIsLclVarLng(regValKind rvKind)
 516 {
 517     if (compiler->opts.MinOpts() || compiler->opts.compDbgCode)
 518     {
 519         return false;
 520     }
 521
 522     if (rvKind == RV_LCL_VAR_LNG_LO || rvKind == RV_LCL_VAR_LNG_HI)
 523     {
 524         return true;
 525     }
 526     else
 527     {
 528         return false;
 529     }
 530 }
 531
 532 /*****************************************************************************/
 533
 534 // inline
 535 void RegTracker::rsTrackRegClsVar(regNumber reg, GenTree* clsVar)
 536 {
 537     rsTrackRegTrash(reg);
 538 }
 539
 540 /*****************************************************************************/
 541
 542 // inline
 543 void RegTracker::rsTrackRegAssign(GenTree* op1, GenTree* op2)
 544 {
 545     /* Constant/bitvalue has precedence over local */
 546     switch (rsRegValues[op2->gtRegNum].rvdKind)
 547     {
 548         case RV_INT_CNS:
 549             break;
 550
 551         default:
 552
 553             /* Mark RHS register as containing the value */
 554
 555             switch (op1->gtOper)
 556             {
 557                 case GT_LCL_VAR:
 558                     rsTrackRegLclVar(op2->gtRegNum, op1->gtLclVarCommon.gtLclNum);
 559                     break;
 560                 case GT_CLS_VAR:
 561                     rsTrackRegClsVar(op2->gtRegNum, op1);
 562                     break;
 563                 default:
 564                     break;
 565             }
 566     }
 567 }
 568
 569 /*****************************************************************************
 570  *
 571  *  Given a regmask, find the best regPairNo that can be formed
 572  *  or return REG_PAIR_NONE if no register pair can be formed
 573  */
 574
 575 regPairNo RegSet::rsFindRegPairNo(regMaskTP regAllowedMask)
 576 {
 577     regPairNo regPair;
 578
 579     // Remove any special purpose registers such as SP, EBP, etc...
 580     regMaskTP specialUseMask = (rsMaskResvd | RBM_SPBASE);
 581 #if ETW_EBP_FRAMED
 582     specialUseMask |= RBM_FPBASE;
 583 #else
 584     if (m_rsCompiler->codeGen->isFramePointerUsed())
 585         specialUseMask |= RBM_FPBASE;
 586 #endif
 587
 588     regAllowedMask &= ~specialUseMask;
 589
 590     /* Check if regAllowedMask has zero or one bits set */
 591     if ((regAllowedMask & (regAllowedMask - 1)) == 0)
 592     {
 593         /* If so we won't be able to find a reg pair */
 594         return REG_PAIR_NONE;
 595     }
 596
 597 #ifdef _TARGET_X86_
 598     if (regAllowedMask & RBM_EAX)
 599     {
 600         /* EAX is available, see if we can pair it with another reg */
 601
 602         if (regAllowedMask & RBM_EDX)
 603         {
 604             regPair = REG_PAIR_EAXEDX;
 605             goto RET;
 606         }
 607         if (regAllowedMask & RBM_ECX)
 608         {
 609             regPair = REG_PAIR_EAXECX;
 610             goto RET;
 611         }
 612         if (regAllowedMask & RBM_EBX)
 613         {
 614             regPair = REG_PAIR_EAXEBX;
 615             goto RET;
 616         }
 617         if (regAllowedMask & RBM_ESI)
 618         {
 619             regPair = REG_PAIR_EAXESI;
 620             goto RET;
 621         }
 622         if (regAllowedMask & RBM_EDI)
 623         {
 624             regPair = REG_PAIR_EAXEDI;
 625             goto RET;
 626         }
 627         if (regAllowedMask & RBM_EBP)
 628         {
 629             regPair = REG_PAIR_EAXEBP;
 630             goto RET;
 631         }
 632     }
 633
 634     if (regAllowedMask & RBM_ECX)
 635     {
 636         /* ECX is available, see if we can pair it with another reg */
 637
 638         if (regAllowedMask & RBM_EDX)
 639         {
 640             regPair = REG_PAIR_ECXEDX;
 641             goto RET;
 642         }
 643         if (regAllowedMask & RBM_EBX)
 644         {
 645             regPair = REG_PAIR_ECXEBX;
 646             goto RET;
 647         }
 648         if (regAllowedMask & RBM_ESI)
 649         {
 650             regPair = REG_PAIR_ECXESI;
 651             goto RET;
 652         }
 653         if (regAllowedMask & RBM_EDI)
 654         {
 655             regPair = REG_PAIR_ECXEDI;
 656             goto RET;
 657         }
 658         if (regAllowedMask & RBM_EBP)
 659         {
 660             regPair = REG_PAIR_ECXEBP;
 661             goto RET;
 662         }
 663     }
 664
 665     if (regAllowedMask & RBM_EDX)
 666     {
 667         /* EDX is available, see if we can pair it with another reg */
 668
 669         if (regAllowedMask & RBM_EBX)
 670         {
 671             regPair = REG_PAIR_EDXEBX;
 672             goto RET;
 673         }
 674         if (regAllowedMask & RBM_ESI)
 675         {
 676             regPair = REG_PAIR_EDXESI;
 677             goto RET;
 678         }
 679         if (regAllowedMask & RBM_EDI)
 680         {
 681             regPair = REG_PAIR_EDXEDI;
 682             goto RET;
 683         }
 684         if (regAllowedMask & RBM_EBP)
 685         {
 686             regPair = REG_PAIR_EDXEBP;
 687             goto RET;
 688         }
 689     }
 690
 691     if (regAllowedMask & RBM_EBX)
 692     {
 693         /* EBX is available, see if we can pair it with another reg */
 694
 695         if (regAllowedMask & RBM_ESI)
 696         {
 697             regPair = REG_PAIR_EBXESI;
 698             goto RET;
 699         }
 700         if (regAllowedMask & RBM_EDI)
 701         {
 702             regPair = REG_PAIR_EBXEDI;
 703             goto RET;
 704         }
 705         if (regAllowedMask & RBM_EBP)
 706         {
 707             regPair = REG_PAIR_EBXEBP;
 708             goto RET;
 709         }
 710     }
 711
 712     if (regAllowedMask & RBM_ESI)
 713     {
 714         /* ESI is available, see if we can pair it with another reg */
 715
 716         if (regAllowedMask & RBM_EDI)
 717         {
 718             regPair = REG_PAIR_ESIEDI;
 719             goto RET;
 720         }
 721         if (regAllowedMask & RBM_EBP)
 722         {
 723             regPair = REG_PAIR_EBPESI;
 724             goto RET;
 725         }
 726     }
 727
 728     if (regAllowedMask & RBM_EDI)
 729     {
 730         /* EDI is available, see if we can pair it with another reg */
 731
 732         if (regAllowedMask & RBM_EBP)
 733         {
 734             regPair = REG_PAIR_EBPEDI;
 735             goto RET;
 736         }
 737     }
 738 #endif
 739
 740 #ifdef _TARGET_ARM_
 741     // ARM is symmetric, so don't bother to prefer some pairs to others
 742     //
 743     // Iterate the registers in the order specified by rpRegTmpOrder/raRegTmpOrder
 744
 745     for (unsigned index1 = 0; index1 < REG_TMP_ORDER_COUNT; index1++)
 746     {
 747         regNumber reg1;
 748         if (m_rsCompiler->rpRegAllocDone)
 749             reg1 = raRegTmpOrder[index1];
 750         else
 751             reg1 = rpRegTmpOrder[index1];
 752
 753         regMaskTP reg1Mask = genRegMask(reg1);
 754
 755         if ((regAllowedMask & reg1Mask) == 0)
 756             continue;
 757
 758         for (unsigned index2 = index1 + 1; index2 < REG_TMP_ORDER_COUNT; index2++)
 759         {
 760             regNumber reg2;
 761             if (m_rsCompiler->rpRegAllocDone)
 762                 reg2 = raRegTmpOrder[index2];
 763             else
 764                 reg2 = rpRegTmpOrder[index2];
 765
 766             regMaskTP reg2Mask = genRegMask(reg2);
 767
 768             if ((regAllowedMask & reg2Mask) == 0)
 769                 continue;
 770
 771             regMaskTP pairMask = genRegMask(reg1) | genRegMask(reg2);
 772
 773             // if reg1 is larger than reg2 then swap the registers
 774             if (reg1 > reg2)
 775             {
 776                 regNumber regT = reg1;
 777                 reg1           = reg2;
 778                 reg2           = regT;
 779             }
 780
 781             regPair = gen2regs2pair(reg1, reg2);
 782             return regPair;
 783         }
 784     }
 785 #endif
 786
 787     assert(!"Unreachable code");
 788     regPair = REG_PAIR_NONE;
 789
 790 #ifdef _TARGET_X86_
 791 RET:
 792 #endif
 793
 794     return regPair;
 795 }
 796
 797 #endif // LEGACY_BACKEND
 798
 799 /*****************************************************************************/
 800
 801 RegSet::RegSet(Compiler* compiler, GCInfo& gcInfo) : m_rsCompiler(compiler), m_rsGCInfo(gcInfo)
 802 {
 803     /* Initialize the spill logic */
 804
 805     rsSpillInit();
 806
 807     /* Initialize the argument register count */
 808     // TODO-Cleanup: Consider moving intRegState and floatRegState to RegSet.  They used
 809     // to be initialized here, but are now initialized in the CodeGen constructor.
 810     // intRegState.rsCurRegArgNum   = 0;
 811     // loatRegState.rsCurRegArgNum = 0;
 812
 813     rsMaskResvd = RBM_NONE;
 814
 815 #ifdef LEGACY_BACKEND
 816     rsMaskMult = RBM_NONE;
 817     rsMaskUsed = RBM_NONE;
 818     rsMaskLock = RBM_NONE;
 819 #endif // LEGACY_BACKEND
 820
 821 #ifdef _TARGET_ARMARCH_
 822     rsMaskCalleeSaved = RBM_NONE;
 823 #endif // _TARGET_ARMARCH_
 824
 825 #ifdef _TARGET_ARM_
 826     rsMaskPreSpillRegArg = RBM_NONE;
 827     rsMaskPreSpillAlign  = RBM_NONE;
 828 #endif
 829
 830 #ifdef DEBUG
 831     rsModifiedRegsMaskInitialized = false;
 832 #endif // DEBUG
 833 }
 834
 835 #ifdef LEGACY_BACKEND
 836 /*****************************************************************************
 837  *
 838  *  Marks the register that holds the given operand value as 'used'. If 'addr'
 839  *  is non-zero, the register is part of a complex address mode that needs to
 840  *  be marked if the register is ever spilled.
 841  */
 842
 843 void RegSet::rsMarkRegUsed(GenTree* tree, GenTree* addr)
 844 {
 845     var_types type;
 846     regNumber regNum;
 847     regMaskTP regMask;
 848
 849     /* The value must be sitting in a register */
 850
 851     assert(tree);
 852     assert(tree->InReg());
 853
 854     type   = tree->TypeGet();
 855     regNum = tree->gtRegNum;
 856
 857     if (isFloatRegType(type))
 858         regMask = genRegMaskFloat(regNum, type);
 859     else
 860         regMask = genRegMask(regNum);
 861
 862 #ifdef DEBUG
 863     if (m_rsCompiler->verbose)
 864     {
 865         printf("\t\t\t\t\t\t\tThe register %s currently holds ", m_rsCompiler->compRegVarName(regNum));
 866         Compiler::printTreeID(tree);
 867         if (addr != NULL)
 868         {
 869             printf("/");
 870             Compiler::printTreeID(addr);
 871         }
 872         else if (tree->gtOper == GT_CNS_INT)
 873         {
 874             if (tree->IsIconHandle())
 875                 printf(" / Handle(0x%08p)", dspPtr(tree->gtIntCon.gtIconVal));
 876             else
 877                 printf(" / Constant(0x%X)", tree->gtIntCon.gtIconVal);
 878         }
 879         printf("\n");
 880     }
 881 #endif // DEBUG
 882
 883     /* Remember whether the register holds a pointer */
 884
 885     m_rsGCInfo.gcMarkRegPtrVal(regNum, type);
 886
 887     /* No locked register may ever be marked as free */
 888
 889     assert((rsMaskLock & rsRegMaskFree()) == 0);
 890
 891     /* Is the register used by two different values simultaneously? */
 892
 893     if (regMask & rsMaskUsed)
 894     {
 895         /* Save the preceding use information */
 896
 897         rsRecMultiReg(regNum, type);
 898     }
 899
 900     /* Set the register's bit in the 'used' bitset */
 901
 902     rsMaskUsed |= regMask;
 903
 904     /* Remember what values are in what registers, in case we have to spill */
 905     assert(regNum != REG_SPBASE);
 906     assert(rsUsedTree[regNum] == NULL);
 907     rsUsedTree[regNum] = tree;
 908     assert(rsUsedAddr[regNum] == NULL);
 909     rsUsedAddr[regNum] = addr;
 910 }
 911
 912 void RegSet::rsMarkArgRegUsedByPromotedFieldArg(GenTree* promotedStructArg, regNumber regNum, bool isGCRef)
 913 {
 914     regMaskTP regMask;
 915
 916     /* The value must be sitting in a register */
 917
 918     assert(promotedStructArg);
 919     assert(promotedStructArg->TypeGet() == TYP_STRUCT);
 920
 921     assert(regNum < MAX_REG_ARG);
 922     regMask = genRegMask(regNum);
 923     assert((regMask & RBM_ARG_REGS) != RBM_NONE);
 924
 925 #ifdef DEBUG
 926     if (m_rsCompiler->verbose)
 927     {
 928         printf("\t\t\t\t\t\t\tThe register %s currently holds ", m_rsCompiler->compRegVarName(regNum));
 929         Compiler::printTreeID(promotedStructArg);
 930         if (promotedStructArg->gtOper == GT_CNS_INT)
 931         {
 932             if (promotedStructArg->IsIconHandle())
 933                 printf(" / Handle(0x%08p)", dspPtr(promotedStructArg->gtIntCon.gtIconVal));
 934             else
 935                 printf(" / Constant(0x%X)", promotedStructArg->gtIntCon.gtIconVal);
 936         }
 937         printf("\n");
 938     }
 939 #endif
 940
 941     /* Remember whether the register holds a pointer */
 942
 943     m_rsGCInfo.gcMarkRegPtrVal(regNum, (isGCRef ? TYP_REF : TYP_INT));
 944
 945     /* No locked register may ever be marked as free */
 946
 947     assert((rsMaskLock & rsRegMaskFree()) == 0);
 948
 949     /* Is the register used by two different values simultaneously? */
 950
 951     if (regMask & rsMaskUsed)
 952     {
 953         /* Save the preceding use information */
 954
 955         assert(isValidIntArgReg(regNum)); // We are expecting only integer argument registers here
 956         rsRecMultiReg(regNum, TYP_I_IMPL);
 957     }
 958
 959     /* Set the register's bit in the 'used' bitset */
 960
 961     rsMaskUsed |= regMask;
 962
 963     /* Remember what values are in what registers, in case we have to spill */
 964     assert(regNum != REG_SPBASE);
 965     assert(rsUsedTree[regNum] == 0);
 966     rsUsedTree[regNum] = promotedStructArg;
 967 }
 968
 969 /*****************************************************************************
 970  *
 971  *  Marks the register pair that holds the given operand value as 'used'.
 972  */
 973
 974 void RegSet::rsMarkRegPairUsed(GenTree* tree)
 975 {
 976     regNumber regLo;
 977     regNumber regHi;
 978     regPairNo regPair;
 979     regMaskTP regMask;
 980
 981     /* The value must be sitting in a register */
 982
 983     assert(tree);
 984 #if CPU_HAS_FP_SUPPORT
 985     assert(tree->gtType == TYP_LONG);
 986 #else
 987     assert(tree->gtType == TYP_LONG || tree->gtType == TYP_DOUBLE);
 988 #endif
 989     assert(tree->InReg());
 990
 991     regPair = tree->gtRegPair;
 992     regMask = genRegPairMask(regPair);
 993
 994     regLo = genRegPairLo(regPair);
 995     regHi = genRegPairHi(regPair);
 996
 997 #ifdef DEBUG
 998     if (m_rsCompiler->verbose)
 999     {
1000         printf("\t\t\t\t\t\t\tThe register %s currently holds ", m_rsCompiler->compRegVarName(regLo));
1001         Compiler::printTreeID(tree);
1002         printf("/lo32\n");
1003         printf("\t\t\t\t\t\t\tThe register %s currently holds ", m_rsCompiler->compRegVarName(regHi));
1004         Compiler::printTreeID(tree);
1005         printf("/hi32\n");
1006     }
1007 #endif
1008
1009     /* Neither register obviously holds a pointer value */
1010
1011     m_rsGCInfo.gcMarkRegSetNpt(regMask);
1012
1013     /* No locked register may ever be marked as free */
1014
1015     assert((rsMaskLock & rsRegMaskFree()) == 0);
1016
1017     /* Are the registers used by two different values simultaneously? */
1018
1019     if (rsMaskUsed & genRegMask(regLo))
1020     {
1021         /* Save the preceding use information */
1022
1023         rsRecMultiReg(regLo, TYP_INT);
1024     }
1025
1026     if (rsMaskUsed & genRegMask(regHi))
1027     {
1028         /* Save the preceding use information */
1029
1030         rsRecMultiReg(regHi, TYP_INT);
1031     }
1032
1033     /* Can't mark a register pair more than once as used */
1034
1035     // assert((regMask & rsMaskUsed) == 0);
1036
1037     /* Mark the registers as 'used' */
1038
1039     rsMaskUsed |= regMask;
1040
1041     /* Remember what values are in what registers, in case we have to spill */
1042
1043     if (regLo != REG_STK)
1044     {
1045         assert(rsUsedTree[regLo] == 0);
1046         assert(regLo != REG_SPBASE);
1047         rsUsedTree[regLo] = tree;
1048     }
1049
1050     if (regHi != REG_STK)
1051     {
1052         assert(rsUsedTree[regHi] == 0);
1053         assert(regHi != REG_SPBASE);
1054         rsUsedTree[regHi] = tree;
1055     }
1056 }
1057
1058 /*****************************************************************************
1059  *
1060  *  Returns true if the given tree is currently held in reg.
1061  *  Note that reg may by used by multiple trees, in which case we have
1062  *  to search rsMultiDesc[reg].
1063  */
1064
1065 bool RegSet::rsIsTreeInReg(regNumber reg, GenTree* tree)
1066 {
1067     /* First do the trivial check */
1068
1069     if (rsUsedTree[reg] == tree)
1070         return true;
1071
1072     /* If the register is used by multiple trees, we have to search the list
1073        in rsMultiDesc[reg] */
1074
1075     if (genRegMask(reg) & rsMaskMult)
1076     {
1077         SpillDsc* multiDesc = rsMultiDesc[reg];
1078         assert(multiDesc);
1079
1080         for (/**/; multiDesc; multiDesc = multiDesc->spillNext)
1081         {
1082             if (multiDesc->spillTree == tree)
1083                 return true;
1084
1085             assert((!multiDesc->spillNext) == (!multiDesc->spillMoreMultis));
1086         }
1087     }
1088
1089     /* Not found. It must be spilled */
1090
1091     return false;
1092 }
1093 #endif // LEGACY_BACKEND
1094
1095 /*****************************************************************************
1096  *
1097  *  Finds the SpillDsc corresponding to 'tree' assuming it was spilled from 'reg'.
1098  */
1099
1100 RegSet::SpillDsc* RegSet::rsGetSpillInfo(GenTree*   tree,
1101                                          regNumber  reg,
1102                                          SpillDsc** pPrevDsc
1103 #ifdef LEGACY_BACKEND
1104                                          ,
1105                                          SpillDsc** pMultiDsc
1106 #endif // LEGACY_BACKEND
1107                                          )
1108 {
1109     /* Normally, trees are unspilled in the order of being spilled due to
1110        the post-order walking of trees during code-gen. However, this will
1111        not be true for something like a GT_ARR_ELEM node */
1112     CLANG_FORMAT_COMMENT_ANCHOR;
1113
1114 #ifdef LEGACY_BACKEND
1115     SpillDsc* multi = rsSpillDesc[reg];
1116 #endif // LEGACY_BACKEND
1117
1118     SpillDsc* prev;
1119     SpillDsc* dsc;
1120     for (prev = nullptr, dsc = rsSpillDesc[reg]; dsc != nullptr; prev = dsc, dsc = dsc->spillNext)
1121     {
1122 #ifdef LEGACY_BACKEND
1123         if (prev && !prev->spillMoreMultis)
1124             multi = dsc;
1125 #endif // LEGACY_BACKEND
1126
1127         if (dsc->spillTree == tree)
1128         {
1129             break;
1130         }
1131     }
1132
1133     if (pPrevDsc)
1134     {
1135         *pPrevDsc = prev;
1136     }
1137 #ifdef LEGACY_BACKEND
1138     if (pMultiDsc)
1139         *pMultiDsc = multi;
1140 #endif // LEGACY_BACKEND
1141
1142     return dsc;
1143 }
1144
1145 #ifdef LEGACY_BACKEND
1146 /*****************************************************************************
1147  *
1148  *  Mark the register set given by the register mask as not used.
1149  */
1150
1151 void RegSet::rsMarkRegFree(regMaskTP regMask)
1152 {
1153     /* Are we freeing any multi-use registers? */
1154
1155     if (regMask & rsMaskMult)
1156     {
1157         rsMultRegFree(regMask);
1158         return;
1159     }
1160
1161     m_rsGCInfo.gcMarkRegSetNpt(regMask);
1162
1163     regMaskTP regBit = 1;
1164
1165     for (regNumber regNum = REG_FIRST; regNum < REG_COUNT; regNum = REG_NEXT(regNum), regBit <<= 1)
1166     {
1167         if (regBit > regMask)
1168             break;
1169
1170         if (regBit & regMask)
1171         {
1172 #ifdef DEBUG
1173             if (m_rsCompiler->verbose)
1174             {
1175                 printf("\t\t\t\t\t\t\tThe register %s no longer holds ", m_rsCompiler->compRegVarName(regNum));
1176                 Compiler::printTreeID(rsUsedTree[regNum]);
1177                 if (rsUsedAddr[regNum] != nullptr)
1178                 {
1179                     Compiler::printTreeID(rsUsedAddr[regNum]);
1180                 }
1181
1182                 printf("\n");
1183             }
1184 #endif
1185             GenTree* usedTree = rsUsedTree[regNum];
1186             assert(usedTree != NULL);
1187             rsUsedTree[regNum] = NULL;
1188             rsUsedAddr[regNum] = NULL;
1189 #ifdef _TARGET_ARM_
1190             if (usedTree->TypeGet() == TYP_DOUBLE)
1191             {
1192                 regNum = REG_NEXT(regNum);
1193                 regBit <<= 1;
1194
1195                 assert(regBit & regMask);
1196                 assert(rsUsedTree[regNum] == NULL);
1197                 assert(rsUsedAddr[regNum] == NULL);
1198             }
1199 #endif
1200         }
1201     }
1202
1203     /* Remove the register set from the 'used' set */
1204
1205     assert((regMask & rsMaskUsed) == regMask);
1206     rsMaskUsed -= regMask;
1207
1208     /* No locked register may ever be marked as free */
1209
1210     assert((rsMaskLock & rsRegMaskFree()) == 0);
1211 }
1212
1213 /*****************************************************************************
1214  *
1215  *  Free the register from the given tree. If the register holds other tree,
1216  *  it will still be marked as used, else it will be completely free.
1217  */
1218
1219 void RegSet::rsMarkRegFree(regNumber reg, GenTree* tree)
1220 {
1221     assert(rsIsTreeInReg(reg, tree));
1222     regMaskTP regMask = genRegMask(reg);
1223
1224     /* If the register is not multi-used, it's easy. Just do the default work */
1225
1226     if (!(regMask & rsMaskMult))
1227     {
1228         rsMarkRegFree(regMask);
1229         return;
1230     }
1231
1232     /* The tree is multi-used. We just have to free it off the given tree but
1233        leave other trees which use the register as they are. The register may
1234        not be multi-used after freeing it from the given tree */
1235
1236     /* Is the tree in rsUsedTree[] or in rsMultiDesc[]?
1237        If it is in rsUsedTree[], update rsUsedTree[] */
1238
1239     if (rsUsedTree[reg] == tree)
1240     {
1241         rsRmvMultiReg(reg);
1242         return;
1243     }
1244
1245     /* The tree is in rsMultiDesc[] instead of in rsUsedTree[]. Find the desc
1246        corresponding to the tree and just remove it from there */
1247
1248     for (SpillDsc *multiDesc = rsMultiDesc[reg], *prevDesc = NULL; multiDesc;
1249          prevDesc = multiDesc, multiDesc = multiDesc->spillNext)
1250     {
1251         /* If we find the descriptor with the tree we are looking for,
1252            discard it */
1253
1254         if (multiDesc->spillTree != tree)
1255             continue;
1256
1257         if (prevDesc == NULL)
1258         {
1259             /* The very first desc in rsMultiDesc[] matched. If there are
1260                no further descs, then the register is no longer multi-used */
1261
1262             if (!multiDesc->spillMoreMultis)
1263                 rsMaskMult -= regMask;
1264
1265             rsMultiDesc[reg] = multiDesc->spillNext;
1266         }
1267         else
1268         {
1269             /* There are a couple of other descs before the match. So the
1270                register is still multi-used. However, we may have to
1271                update spillMoreMultis for the previous desc. */
1272
1273             if (!multiDesc->spillMoreMultis)
1274                 prevDesc->spillMoreMultis = false;
1275
1276             prevDesc->spillNext = multiDesc->spillNext;
1277         }
1278
1279         SpillDsc::freeDsc(this, multiDesc);
1280
1281 #ifdef DEBUG
1282         if (m_rsCompiler->verbose)
1283         {
1284             printf("\t\t\t\t\t\t\tRegister %s multi-use dec for ", m_rsCompiler->compRegVarName(reg));
1285             Compiler::printTreeID(tree);
1286             printf(" - now ");
1287             Compiler::printTreeID(rsUsedTree[reg]);
1288             printf(" multMask=" REG_MASK_ALL_FMT "\n", rsMaskMult);
1289         }
1290 #endif
1291
1292         return;
1293     }
1294
1295     assert(!"Didn't find the spilled tree in rsMultiDesc[]");
1296 }
1297
1298 /*****************************************************************************
1299  *
1300  *  Mark the register set given by the register mask as not used; there may
1301  *  be some 'multiple-use' registers in the set.
1302  */
1303
1304 void RegSet::rsMultRegFree(regMaskTP regMask)
1305 {
1306     /* Free any multiple-use registers first */
1307     regMaskTP nonMultMask = regMask & ~rsMaskMult;
1308     regMaskTP myMultMask  = regMask & rsMaskMult;
1309
1310     if (myMultMask)
1311     {
1312         regNumber regNum;
1313         regMaskTP regBit;
1314
1315         for (regNum = REG_FIRST, regBit = 1; regNum < REG_COUNT; regNum = REG_NEXT(regNum), regBit <<= 1)
1316         {
1317             if (regBit > myMultMask)
1318                 break;
1319
1320             if (regBit & myMultMask)
1321             {
1322                 /* Free the multi-use register 'regNum' */
1323                 var_types type = rsRmvMultiReg(regNum);
1324 #ifdef _TARGET_ARM_
1325                 if (genIsValidFloatReg(regNum) && (type == TYP_DOUBLE))
1326                 {
1327                     // On ARM32, We skip the second register for a TYP_DOUBLE
1328                     regNum = REG_NEXT(regNum);
1329                     regBit <<= 1;
1330                 }
1331 #endif // _TARGET_ARM_
1332             }
1333         }
1334     }
1335
1336     /* If there are any single-use registers, free them */
1337
1338     if (nonMultMask)
1339         rsMarkRegFree(nonMultMask);
1340 }
1341
1342 /*****************************************************************************
1343  *
1344  *  Returns the number of registers that are currently free which appear in needReg.
1345  */
1346
1347 unsigned RegSet::rsFreeNeededRegCount(regMaskTP needReg)
1348 {
1349     regMaskTP regNeededFree = rsRegMaskFree() & needReg;
1350     unsigned  cntFree       = 0;
1351
1352     /* While some registers are free ... */
1353
1354     while (regNeededFree)
1355     {
1356         /* Remove the next register bit and bump the count */
1357
1358         regNeededFree -= genFindLowestBit(regNeededFree);
1359         cntFree += 1;
1360     }
1361
1362     return cntFree;
1363 }
1364 #endif // LEGACY_BACKEND
1365
1366 /*****************************************************************************
1367  *
1368  *  Record the fact that the given register now contains the given local
1369  *  variable. Pointers are handled specially since reusing the register
1370  *  will extend the lifetime of a pointer register which is not a register
1371  *  variable.
1372  */
1373
1374 void RegTracker::rsTrackRegLclVar(regNumber reg, unsigned var)
1375 {
1376     LclVarDsc* varDsc = &compiler->lvaTable[var];
1377     assert(reg != REG_STK);
1378 #if CPU_HAS_FP_SUPPORT
1379     assert(varTypeIsFloating(varDsc->TypeGet()) == false);
1380 #endif
1381 #ifdef LEGACY_BACKEND
1382     // Kill the register before doing anything in case we take a
1383     // shortcut out of here
1384     rsRegValues[reg].rvdKind = RV_TRASH;
1385 #endif
1386
1387     if (compiler->lvaTable[var].lvAddrExposed)
1388     {
1389         return;
1390     }
1391
1392     /* Keep track of which registers we ever touch */
1393
1394     regSet->rsSetRegsModified(genRegMask(reg));
1395
1396 #ifdef LEGACY_BACKEND
1397
1398     /* Is the variable a pointer? */
1399
1400     if (varTypeIsGC(varDsc->TypeGet()))
1401     {
1402         /* Don't track pointer register vars */
1403
1404         if (varDsc->lvRegister)
1405         {
1406             return;
1407         }
1408
1409         /* Don't track when fully interruptible */
1410
1411         if (compiler->genInterruptible)
1412         {
1413             return;
1414         }
1415     }
1416     else if (varDsc->lvNormalizeOnLoad())
1417     {
1418         return;
1419     }
1420
1421 #ifdef DEBUG
1422     if (compiler->verbose)
1423     {
1424         printf("\t\t\t\t\t\t\tThe register %s now holds V%02u\n", compiler->compRegVarName(reg), var);
1425     }
1426 #endif
1427
1428     /* Record the new value for the register. ptr var needed for
1429      * lifetime extension
1430      */
1431
1432     rsRegValues[reg].rvdKind = RV_LCL_VAR;
1433
1434     // If this is a cast of a 64 bit int, then we must have the low 32 bits.
1435     if (genActualType(varDsc->TypeGet()) == TYP_LONG)
1436     {
1437         rsRegValues[reg].rvdKind = RV_LCL_VAR_LNG_LO;
1438     }
1439
1440     rsRegValues[reg].rvdLclVarNum = var;
1441 #endif // LEGACY_BACKEND
1442 }
1443
1444 /*****************************************************************************/
1445
1446 #ifdef LEGACY_BACKEND
1447 void RegTracker::rsTrackRegSwap(regNumber reg1, regNumber reg2)
1448 {
1449     RegValDsc tmp;
1450
1451     tmp               = rsRegValues[reg1];
1452     rsRegValues[reg1] = rsRegValues[reg2];
1453     rsRegValues[reg2] = tmp;
1454 }
1455 #endif // LEGACY_BACKEND
1456
1457 void RegTracker::rsTrackRegCopy(regNumber reg1, regNumber reg2)
1458 {
1459     /* Keep track of which registers we ever touch */
1460
1461     assert(reg1 < REG_COUNT);
1462     assert(reg2 < REG_COUNT);
1463
1464     regSet->rsSetRegsModified(genRegMask(reg1));
1465
1466 #ifdef LEGACY_BACKEND
1467     rsRegValues[reg1] = rsRegValues[reg2];
1468 #endif // LEGACY_BACKEND
1469 }
1470
1471 #ifdef LEGACY_BACKEND
1472
1473 /*****************************************************************************
1474  *  One of the operands of this complex address mode has been spilled
1475  */
1476
1477 void rsAddrSpillOper(GenTree* addr)
1478 {
1479     if (addr)
1480     {
1481         assert(addr->gtOper == GT_IND || addr->gtOper == GT_ARR_ELEM || addr->gtOper == GT_LEA ||
1482                addr->gtOper == GT_CMPXCHG);
1483
1484         // GTF_SPILLED_OP2 says "both operands have been spilled"
1485         assert((addr->gtFlags & GTF_SPILLED_OP2) == 0);
1486
1487         if ((addr->gtFlags & GTF_SPILLED_OPER) == 0)
1488             addr->gtFlags |= GTF_SPILLED_OPER;
1489         else
1490             addr->gtFlags |= GTF_SPILLED_OP2;
1491     }
1492 }
1493
1494 void rsAddrUnspillOper(GenTree* addr)
1495 {
1496     if (addr)
1497     {
1498         assert(addr->gtOper == GT_IND || addr->gtOper == GT_ARR_ELEM || addr->gtOper == GT_LEA ||
1499                addr->gtOper == GT_CMPXCHG);
1500
1501         assert((addr->gtFlags & GTF_SPILLED_OPER) != 0);
1502
1503         // Both operands spilled? */
1504         if ((addr->gtFlags & GTF_SPILLED_OP2) != 0)
1505             addr->gtFlags &= ~GTF_SPILLED_OP2;
1506         else
1507             addr->gtFlags &= ~GTF_SPILLED_OPER;
1508     }
1509 }
1510
1511 void RegSet::rsSpillRegIfUsed(regNumber reg)
1512 {
1513     if (rsMaskUsed & genRegMask(reg))
1514     {
1515         rsSpillReg(reg);
1516     }
1517 }
1518
1519 #endif // LEGACY_BACKEND
1520
1521 //------------------------------------------------------------
1522 // rsSpillTree: Spill the tree held in 'reg'.
1523 //
1524 // Arguments:
1525 //   reg     -   Register of tree node that is to be spilled
1526 //   tree    -   GenTree node that is being spilled
1527 //   regIdx  -   Register index identifying the specific result
1528 //               register of a multi-reg call node. For single-reg
1529 //               producing tree nodes its value is zero.
1530 //
1531 // Return Value:
1532 //   None.
1533 //
1534 // Assumption:
1535 //    RyuJIT backend specific: in case of multi-reg call nodes, GTF_SPILL
1536 //    flag associated with the reg that is being spilled is cleared.  The
1537 //    caller of this method is expected to clear GTF_SPILL flag on call
1538 //    node after all of its registers marked for spilling are spilled.
1539 //
1540 void RegSet::rsSpillTree(regNumber reg, GenTree* tree, unsigned regIdx /* =0 */)
1541 {
1542     assert(tree != nullptr);
1543
1544     GenTreeCall* call = nullptr;
1545     var_types    treeType;
1546 #if !defined(LEGACY_BACKEND) && defined(_TARGET_ARM_)
1547     GenTreePutArgSplit* splitArg = nullptr;
1548     GenTreeMultiRegOp*  multiReg = nullptr;
1549 #endif
1550
1551 #ifndef LEGACY_BACKEND
1552     if (tree->IsMultiRegCall())
1553     {
1554         call                        = tree->AsCall();
1555         ReturnTypeDesc* retTypeDesc = call->GetReturnTypeDesc();
1556         treeType                    = retTypeDesc->GetReturnRegType(regIdx);
1557     }
1558 #ifdef _TARGET_ARM_
1559     else if (tree->OperIsPutArgSplit())
1560     {
1561         splitArg = tree->AsPutArgSplit();
1562         treeType = splitArg->GetRegType(regIdx);
1563     }
1564     else if (tree->OperIsMultiRegOp())
1565     {
1566         multiReg = tree->AsMultiRegOp();
1567         treeType = multiReg->GetRegType(regIdx);
1568     }
1569 #endif // _TARGET_ARM_
1570     else
1571 #endif // !LEGACY_BACKEND
1572     {
1573         treeType = tree->TypeGet();
1574     }
1575
1576     var_types tempType = Compiler::tmpNormalizeType(treeType);
1577     regMaskTP mask;
1578     bool      floatSpill = false;
1579
1580     if (isFloatRegType(treeType))
1581     {
1582         floatSpill = true;
1583         mask       = genRegMaskFloat(reg, treeType);
1584     }
1585     else
1586     {
1587         mask = genRegMask(reg);
1588     }
1589
1590     rsNeededSpillReg = true;
1591
1592 #ifdef LEGACY_BACKEND
1593     // The register we're spilling must be used but not locked
1594     // or an enregistered variable.
1595
1596     assert((mask & rsMaskUsed) == mask);
1597     assert((mask & rsMaskLock) == 0);
1598     assert((mask & rsMaskVars) == 0);
1599 #endif // LEGACY_BACKEND
1600
1601 #ifndef LEGACY_BACKEND
1602     // We should only be spilling nodes marked for spill,
1603     // vars should be handled elsewhere, and to prevent
1604     // spilling twice clear GTF_SPILL flag on tree node.
1605     //
1606     // In case of multi-reg call nodes only the spill flag
1607     // associated with the reg is cleared. Spill flag on
1608     // call node should be cleared by the caller of this method.
1609     assert(tree->gtOper != GT_REG_VAR);
1610     assert((tree->gtFlags & GTF_SPILL) != 0);
1611
1612     unsigned regFlags = 0;
1613     if (call != nullptr)
1614     {
1615         regFlags = call->GetRegSpillFlagByIdx(regIdx);
1616         assert((regFlags & GTF_SPILL) != 0);
1617         regFlags &= ~GTF_SPILL;
1618     }
1619 #ifdef _TARGET_ARM_
1620     else if (splitArg != nullptr)
1621     {
1622         regFlags = splitArg->GetRegSpillFlagByIdx(regIdx);
1623         assert((regFlags & GTF_SPILL) != 0);
1624         regFlags &= ~GTF_SPILL;
1625     }
1626     else if (multiReg != nullptr)
1627     {
1628         regFlags = multiReg->GetRegSpillFlagByIdx(regIdx);
1629         assert((regFlags & GTF_SPILL) != 0);
1630         regFlags &= ~GTF_SPILL;
1631     }
1632 #endif // _TARGET_ARM_
1633     else
1634     {
1635         assert(!varTypeIsMultiReg(tree));
1636         tree->gtFlags &= ~GTF_SPILL;
1637     }
1638 #endif // !LEGACY_BACKEND
1639
1640 #if CPU_LONG_USES_REGPAIR
1641     // Are we spilling a part of a register pair?
1642     if (treeType == TYP_LONG)
1643     {
1644         tempType = TYP_I_IMPL;
1645         assert(genRegPairLo(tree->gtRegPair) == reg || genRegPairHi(tree->gtRegPair) == reg);
1646     }
1647     else
1648     {
1649         assert(tree->InReg());
1650         assert(tree->gtRegNum == reg);
1651     }
1652 #elif defined(_TARGET_ARM_)
1653     assert(tree->gtRegNum == reg || (call != nullptr && call->GetRegNumByIdx(regIdx) == reg) ||
1654            (splitArg != nullptr && splitArg->GetRegNumByIdx(regIdx) == reg) ||
1655            (multiReg != nullptr && multiReg->GetRegNumByIdx(regIdx) == reg));
1656 #else
1657     assert(tree->gtRegNum == reg || (call != nullptr && call->GetRegNumByIdx(regIdx) == reg));
1658 #endif // !CPU_LONG_USES_REGPAIR && !_TARGET_ARM_
1659
1660     // Are any registers free for spillage?
1661     SpillDsc* spill = SpillDsc::alloc(m_rsCompiler, this, tempType);
1662
1663     // Grab a temp to store the spilled value
1664     TempDsc* temp    = m_rsCompiler->tmpGetTemp(tempType);
1665     spill->spillTemp = temp;
1666     tempType         = temp->tdTempType();
1667
1668     // Remember what it is we have spilled
1669     spill->spillTree = tree;
1670 #ifdef LEGACY_BACKEND
1671     spill->spillAddr = rsUsedAddr[reg];
1672 #endif // LEGACY_BACKEND
1673
1674 #ifdef DEBUG
1675     if (m_rsCompiler->verbose)
1676     {
1677         printf("\t\t\t\t\t\t\tThe register %s spilled with    ", m_rsCompiler->compRegVarName(reg));
1678         Compiler::printTreeID(spill->spillTree);
1679 #ifdef LEGACY_BACKEND
1680         if (spill->spillAddr != nullptr)
1681         {
1682             Compiler::printTreeID(spill->spillAddr);
1683         }
1684 #endif // LEGACY_BACKEND
1685     }
1686 #endif
1687
1688 #ifdef LEGACY_BACKEND
1689     // Is the register part of a complex address mode?
1690     rsAddrSpillOper(rsUsedAddr[reg]);
1691 #endif // LEGACY_BACKEND
1692
1693     // 'lastDsc' is 'spill' for simple cases, and will point to the last
1694     // multi-use descriptor if 'reg' is being multi-used
1695     SpillDsc* lastDsc = spill;
1696
1697 #ifdef LEGACY_BACKEND
1698     if ((rsMaskMult & mask) == 0)
1699     {
1700         spill->spillMoreMultis = false;
1701     }
1702     else
1703     {
1704         // The register is being multi-used and will have entries in
1705         // rsMultiDesc[reg]. Spill all of them (ie. move them to
1706         // rsSpillDesc[reg]).
1707         // When we unspill the reg, they will all be moved back to
1708         // rsMultiDesc[].
1709
1710         spill->spillMoreMultis = true;
1711
1712         SpillDsc* nextDsc = rsMultiDesc[reg];
1713
1714         do
1715         {
1716             assert(nextDsc != nullptr);
1717
1718             // Is this multi-use part of a complex address mode?
1719             rsAddrSpillOper(nextDsc->spillAddr);
1720
1721             // Mark the tree node as having been spilled
1722             rsMarkSpill(nextDsc->spillTree, reg);
1723
1724             // lastDsc points to the last of the multi-spill descrs for 'reg'
1725             nextDsc->spillTemp = temp;
1726
1727 #ifdef DEBUG
1728             if (m_rsCompiler->verbose)
1729             {
1730                 printf(", ");
1731                 Compiler::printTreeID(nextDsc->spillTree);
1732                 printf("/");
1733                 Compiler::printTreeID(nextDsc->spillAddr);
1734             }
1735 #endif
1736
1737             lastDsc->spillNext = nextDsc;
1738             lastDsc            = nextDsc;
1739
1740             nextDsc = nextDsc->spillNext;
1741         } while (lastDsc->spillMoreMultis);
1742
1743         rsMultiDesc[reg] = nextDsc;
1744
1745         // 'reg' is no longer considered to be multi-used. We will set this
1746         // mask again when this value gets unspilled
1747         rsMaskMult &= ~mask;
1748     }
1749 #endif // LEGACY_BACKEND
1750
1751     // Insert the spill descriptor(s) in the list
1752     lastDsc->spillNext = rsSpillDesc[reg];
1753     rsSpillDesc[reg]   = spill;
1754
1755 #ifdef DEBUG
1756     if (m_rsCompiler->verbose)
1757     {
1758         printf("\n");
1759     }
1760 #endif
1761
1762     // Generate the code to spill the register
1763     var_types storeType = floatSpill ? treeType : tempType;
1764
1765     m_rsCompiler->codeGen->spillReg(storeType, temp, reg);
1766
1767     // Mark the tree node as having been spilled
1768     rsMarkSpill(tree, reg);
1769
1770 #ifdef LEGACY_BACKEND
1771     // The register is now free
1772     rsMarkRegFree(mask);
1773 #else
1774     // In case of multi-reg call node also mark the specific
1775     // result reg as spilled.
1776     if (call != nullptr)
1777     {
1778         regFlags |= GTF_SPILLED;
1779         call->SetRegSpillFlagByIdx(regFlags, regIdx);
1780     }
1781 #ifdef _TARGET_ARM_
1782     else if (splitArg != nullptr)
1783     {
1784         regFlags |= GTF_SPILLED;
1785         splitArg->SetRegSpillFlagByIdx(regFlags, regIdx);
1786     }
1787     else if (multiReg != nullptr)
1788     {
1789         regFlags |= GTF_SPILLED;
1790         multiReg->SetRegSpillFlagByIdx(regFlags, regIdx);
1791     }
1792 #endif // _TARGET_ARM_
1793 #endif //! LEGACY_BACKEND
1794 }
1795
1796 #if defined(_TARGET_X86_) && !FEATURE_STACK_FP_X87
1797 /*****************************************************************************
1798 *
1799 *  Spill the top of the FP x87 stack.
1800 */
1801 void RegSet::rsSpillFPStack(GenTreeCall* call)
1802 {
1803     SpillDsc* spill;
1804     TempDsc*  temp;
1805     var_types treeType = call->TypeGet();
1806
1807     spill = SpillDsc::alloc(m_rsCompiler, this, treeType);
1808
1809     /* Grab a temp to store the spilled value */
1810
1811     spill->spillTemp = temp = m_rsCompiler->tmpGetTemp(treeType);
1812
1813     /* Remember what it is we have spilled */
1814
1815     spill->spillTree  = call;
1816     SpillDsc* lastDsc = spill;
1817
1818     regNumber reg      = call->gtRegNum;
1819     lastDsc->spillNext = rsSpillDesc[reg];
1820     rsSpillDesc[reg]   = spill;
1821
1822 #ifdef DEBUG
1823     if (m_rsCompiler->verbose)
1824         printf("\n");
1825 #endif
1826     // m_rsCompiler->codeGen->inst_FS_ST(INS_fstp, emitActualTypeSize(treeType), temp, 0);
1827     m_rsCompiler->codeGen->getEmitter()->emitIns_S(INS_fstp, emitActualTypeSize(treeType), temp->tdTempNum(), 0);
1828
1829     /* Mark the tree node as having been spilled */
1830
1831     rsMarkSpill(call, reg);
1832 }
1833 #endif // defined(_TARGET_X86_) && !FEATURE_STACK_FP_X87
1834
1835 #ifdef LEGACY_BACKEND
1836
1837 /*****************************************************************************
1838  *
1839  *  Spill the given register (which we assume to be currently marked as used).
1840  */
1841
1842 void RegSet::rsSpillReg(regNumber reg)
1843 {
1844     /* We must know the value in the register that we are spilling */
1845     GenTree* tree = rsUsedTree[reg];
1846
1847 #ifdef _TARGET_ARM_
1848     if (tree == NULL && genIsValidFloatReg(reg) && !genIsValidDoubleReg(reg))
1849     {
1850         reg = REG_PREV(reg);
1851         assert(rsUsedTree[reg]);
1852         assert(rsUsedTree[reg]->TypeGet() == TYP_DOUBLE);
1853         tree = rsUsedTree[reg];
1854     }
1855 #endif
1856
1857     rsSpillTree(reg, tree);
1858
1859     /* The register no longer holds its original value */
1860
1861     rsUsedTree[reg] = NULL;
1862 }
1863
1864 /*****************************************************************************
1865  *
1866  *  Spill all registers in 'regMask' that are currently marked as used.
1867  */
1868
1869 void RegSet::rsSpillRegs(regMaskTP regMask)
1870 {
1871     /* The registers we're spilling must not be locked,
1872        or enregistered variables */
1873
1874     assert((regMask & rsMaskLock) == 0);
1875     assert((regMask & rsMaskVars) == 0);
1876
1877     /* Only spill what's currently marked as used */
1878
1879     regMask &= rsMaskUsed;
1880     assert(regMask);
1881
1882     regNumber regNum;
1883     regMaskTP regBit;
1884
1885     for (regNum = REG_FIRST, regBit = 1; regNum < REG_COUNT; regNum = REG_NEXT(regNum), regBit <<= 1)
1886     {
1887         if (regMask & regBit)
1888         {
1889             rsSpillReg(regNum);
1890
1891             regMask &= rsMaskUsed;
1892
1893             if (!regMask)
1894                 break;
1895         }
1896     }
1897 }
1898
1899 /*****************************************************************************
1900  *
1901  *  The following table determines the order in which registers are considered
1902  *  for internal tree temps to live in
1903  */
1904
1905 #ifdef LEGACY_BACKEND
1906 extern const regNumber raRegTmpOrder[] = {REG_TMP_ORDER};
1907 extern const regNumber rpRegTmpOrder[] = {REG_PREDICT_ORDER};
1908 #if FEATURE_FP_REGALLOC
1909 extern const regNumber raRegFltTmpOrder[] = {REG_FLT_TMP_ORDER};
1910 #endif
1911 #endif // LEGACY_BACKEND
1912
1913 /*****************************************************************************
1914  *
1915  *  Choose a register from the given set in the preferred order (see above);
1916  *  if no registers are in the set return REG_STK.
1917  */
1918
1919 regNumber RegSet::rsPickRegInTmpOrder(regMaskTP regMask)
1920 {
1921     if (regMask == RBM_NONE)
1922         return REG_STK;
1923
1924     bool      firstPass = true;
1925     regMaskTP avoidMask =
1926         ~rsGetModifiedRegsMask() & RBM_CALLEE_SAVED; // We want to avoid using any new callee saved register
1927
1928     while (true)
1929     {
1930         /* Iterate the registers in the order specified by raRegTmpOrder */
1931
1932         for (unsigned index = 0; index < REG_TMP_ORDER_COUNT; index++)
1933         {
1934             regNumber candidateReg  = raRegTmpOrder[index];
1935             regMaskTP candidateMask = genRegMask(candidateReg);
1936
1937             // For a FP base frame, don't use FP register.
1938             if (m_rsCompiler->codeGen->isFramePointerUsed() && (candidateMask == RBM_FPBASE))
1939                 continue;
1940
1941             // For the first pass avoid selecting a never used register when there are other registers available
1942             if (firstPass && ((candidateMask & avoidMask) != 0))
1943                 continue;
1944
1945             if (regMask & candidateMask)
1946                 return candidateReg;
1947         }
1948
1949         if (firstPass == true)
1950             firstPass = false; // OK, now we are willing to select a never used register
1951         else
1952             break;
1953     }
1954
1955     return REG_STK;
1956 }
1957
1958 /*****************************************************************************
1959  *  Choose a register from the 'regMask' set and return it. If no registers in
1960  *  the set are currently free, one of them will be spilled (even if other
1961  *  registers - not in the set - are currently free).
1962  *
1963  *  If you don't require a register from a particular set, you should use rsPickReg() instead.
1964  *
1965  *  rsModifiedRegsMask is modified to include the returned register.
1966  */
1967
1968 regNumber RegSet::rsGrabReg(regMaskTP regMask)
1969 {
1970     regMaskTP OKmask;
1971     regNumber regNum;
1972     regMaskTP regBit;
1973
1974     assert(regMask);
1975     regMask &= ~rsMaskLock;
1976     assert(regMask);
1977
1978     /* See if one of the desired registers happens to be free */
1979
1980     OKmask = regMask & rsRegMaskFree();
1981
1982     regNum = rsPickRegInTmpOrder(OKmask);
1983     if (REG_STK != regNum)
1984     {
1985         goto RET;
1986     }
1987
1988     /* We'll have to spill one of the registers in 'regMask' */
1989
1990     OKmask = regMask & rsRegMaskCanGrab();
1991     assert(OKmask);
1992
1993     for (regNum = REG_FIRST, regBit = 1; (regBit & OKmask) == 0; regNum = REG_NEXT(regNum), regBit <<= 1)
1994     {
1995         if (regNum >= REG_COUNT)
1996         {
1997             assert(!"no register to grab!");
1998             NO_WAY("Could not grab a register, Predictor should have prevented this!");
1999         }
2000     }
2001
2002     /* This will be the victim -- spill it */
2003     rsSpillReg(regNum);
2004
2005     /* Make sure we did find a register to spill */
2006     assert(genIsValidReg(regNum));
2007
2008 RET:
2009     /* Keep track of which registers we ever touch */
2010     rsSetRegsModified(genRegMask(regNum));
2011     return regNum;
2012 }
2013
2014 /*****************************************************************************
2015  *  Find a register to use and return it, spilling if necessary.
2016  *
2017  *  Look for a register in the following order: First, try and find a free register
2018  *  in 'regBest' (if 'regBest' is RBM_NONE, skip this step). Second, try to find a
2019  *  free register in 'regMask' (if 'regMask' is RBM_NONE, skip this step). Note that
2020  *  'regBest' doesn't need to be a subset of 'regMask'. Third, find any free
2021  *  register. Fourth, spill a register. The register to spill will be in 'regMask',
2022  *  if 'regMask' is not RBM_NONE.
2023  *
2024  *  Note that 'regMask' and 'regBest' are purely recommendations, and can be ignored;
2025  *  the caller can't expect that the returned register will be in those sets. In
2026  *  particular, under register stress, we specifically will pick registers not in
2027  *  these sets to ensure that callers don't require a register from those sets
2028  *  (and to ensure callers can handle the spilling that might ensue).
2029  *
2030  *  Calling rsPickReg() with the default arguments (which sets 'regMask' and 'regBest' to RBM_NONE)
2031  *  is equivalent to calling rsGrabReg(rsRegMaskFree()).
2032  *
2033  *  rsModifiedRegsMask is modified to include the returned register.
2034  */
2035
2036 regNumber RegSet::rsPickReg(regMaskTP regMask, regMaskTP regBest)
2037 {
2038     regNumber regNum;
2039     regMaskTP spillMask;
2040     regMaskTP canGrabMask;
2041
2042 #ifdef DEBUG
2043     if (rsStressRegs() >= 1)
2044     {
2045         /* 'regMask' is purely a recommendation, and callers should be
2046            able to handle the case where it is not satisfied.
2047            The logic here tries to return ~regMask to check that all callers
2048            are prepared to handle such a case */
2049
2050         regMaskTP badRegs = rsMaskMult & rsRegMaskCanGrab();
2051
2052         badRegs = rsUseIfZero(badRegs, rsMaskUsed & rsRegMaskCanGrab());
2053         badRegs = rsUseIfZero(badRegs, rsRegMaskCanGrab());
2054         badRegs = rsExcludeHint(badRegs, regMask);
2055
2056         assert(badRegs != RBM_NONE);
2057
2058         return rsGrabReg(badRegs);
2059     }
2060
2061 #endif
2062
2063     regMaskTP freeMask = rsRegMaskFree();
2064
2065 AGAIN:
2066
2067     /* By default we'd prefer to accept all available registers */
2068
2069     regMaskTP OKmask = freeMask;
2070
2071     // OKmask = rsNarrowHint(OKmask, rsUselessRegs());
2072
2073     /* Is there a 'best' register set? */
2074
2075     if (regBest)
2076     {
2077         OKmask &= regBest;
2078         if (OKmask)
2079             goto TRY_REG;
2080         else
2081             goto TRY_ALL;
2082     }
2083
2084     /* Was a register set recommended by the caller? */
2085
2086     if (regMask)
2087     {
2088         OKmask &= regMask;
2089         if (!OKmask)
2090             goto TRY_ALL;
2091     }
2092
2093 TRY_REG:
2094
2095     /* Iterate the registers in the order specified by raRegTmpOrder */
2096
2097     regNum = rsPickRegInTmpOrder(OKmask);
2098     if (REG_STK != regNum)
2099     {
2100         goto RET;
2101     }
2102
2103 TRY_ALL:
2104
2105     /* Were we considering 'regBest' ? */
2106
2107     if (regBest)
2108     {
2109         /* 'regBest' is no good -- ignore it and try 'regMask' instead */
2110
2111         regBest = RBM_NONE;
2112         goto AGAIN;
2113     }
2114
2115     /* Now let's consider all available registers */
2116
2117     /* Were we limited in our consideration? */
2118
2119     if (!regMask)
2120     {
2121         /* We need to spill one of the free registers */
2122
2123         spillMask = freeMask;
2124     }
2125     else
2126     {
2127         /* Did we not consider all free registers? */
2128
2129         if ((regMask & freeMask) != freeMask)
2130         {
2131             /* The recommended regset didn't work, so try all available regs */
2132
2133             regNum = rsPickRegInTmpOrder(freeMask);
2134             if (REG_STK != regNum)
2135                 goto RET;
2136         }
2137
2138         /* If we're going to spill, might as well go for the right one */
2139
2140         spillMask = regMask;
2141     }
2142
2143     /* Make sure we can spill some register. */
2144
2145     canGrabMask = rsRegMaskCanGrab();
2146     if ((spillMask & canGrabMask) == 0)
2147         spillMask = canGrabMask;
2148
2149     assert(spillMask);
2150
2151     /* We have no choice but to spill one of the regs */
2152
2153     return rsGrabReg(spillMask);
2154
2155 RET:
2156
2157     rsSetRegsModified(genRegMask(regNum));
2158     return regNum;
2159 }
2160
2161 #endif // LEGACY_BACKEND
2162
2163 /*****************************************************************************
2164  *
2165  *  Get the temp that was spilled from the given register (and free its
2166  *  spill descriptor while we're at it). Returns the temp (i.e. local var)
2167  */
2168
2169 TempDsc* RegSet::rsGetSpillTempWord(regNumber reg, SpillDsc* dsc, SpillDsc* prevDsc)
2170 {
2171     assert((prevDsc == nullptr) || (prevDsc->spillNext == dsc));
2172
2173 #ifdef LEGACY_BACKEND
2174     /* Is dsc the last of a set of multi-used values */
2175
2176     if (prevDsc && prevDsc->spillMoreMultis && !dsc->spillMoreMultis)
2177         prevDsc->spillMoreMultis = false;
2178 #endif // LEGACY_BACKEND
2179
2180     /* Remove this spill entry from the register's list */
2181
2182     (prevDsc ? prevDsc->spillNext : rsSpillDesc[reg]) = dsc->spillNext;
2183
2184     /* Remember which temp the value is in */
2185
2186     TempDsc* temp = dsc->spillTemp;
2187
2188     SpillDsc::freeDsc(this, dsc);
2189
2190     /* return the temp variable */
2191
2192     return temp;
2193 }
2194
2195 #ifdef LEGACY_BACKEND
2196 /*****************************************************************************
2197  *
2198  *  Reload the value that was spilled from the given register (and free its
2199  *  spill descriptor while we're at it). Returns the new register (which will
2200  *  be a member of 'needReg' if that value is non-zero).
2201  *
2202  *  'willKeepNewReg' indicates if the caller intends to mark newReg as used.
2203  *      If not, then we can't unspill the other multi-used descriptor (if any).
2204  *      Instead, we will just hold on to the temp and unspill them
2205  *      again as needed.
2206  */
2207
2208 regNumber RegSet::rsUnspillOneReg(GenTree* tree, regNumber oldReg, KeepReg willKeepNewReg, regMaskTP needReg)
2209 {
2210     /* Was oldReg multi-used when it was spilled? */
2211
2212     SpillDsc *prevDsc, *multiDsc;
2213     SpillDsc* spillDsc = rsGetSpillInfo(tree, oldReg, &prevDsc, &multiDsc);
2214     noway_assert((spillDsc != NULL) && (multiDsc != NULL));
2215
2216     bool multiUsed = multiDsc->spillMoreMultis;
2217
2218     /* We will use multiDsc to walk the rest of the spill list (if it's
2219        multiUsed). As we're going to remove spillDsc from the multiDsc
2220        list in the rsGetSpillTempWord() call we have to take care of the
2221        case where multiDsc==spillDsc. We will set multiDsc as spillDsc->spillNext */
2222     if (multiUsed && multiDsc == spillDsc)
2223     {
2224         assert(spillDsc->spillNext);
2225         multiDsc = spillDsc->spillNext;
2226     }
2227
2228     /* Get the temp and free the spill-descriptor */
2229
2230     TempDsc* temp = rsGetSpillTempWord(oldReg, spillDsc, prevDsc);
2231
2232     //  Pick a new home for the value:
2233     //    This must be a register matching the 'needReg' mask, if it is non-zero.
2234     //    Additionally, if 'oldReg' is in 'needMask' and it is free we will select oldReg.
2235     //    Also note that the rsGrabReg() call below may cause the chosen register to be spilled.
2236     //
2237     regMaskTP prefMask;
2238     regMaskTP freeMask;
2239     regNumber newReg;
2240     var_types regType;
2241     var_types loadType;
2242
2243     bool floatUnspill = false;
2244
2245 #if FEATURE_FP_REGALLOC
2246     floatUnspill = genIsValidFloatReg(oldReg);
2247 #endif
2248
2249     if (floatUnspill)
2250     {
2251         if (temp->tdTempType() == TYP_DOUBLE)
2252             regType = TYP_DOUBLE;
2253         else
2254             regType = TYP_FLOAT;
2255         loadType    = regType;
2256         prefMask    = genRegMaskFloat(oldReg, regType);
2257         freeMask    = RegFreeFloat();
2258     }
2259     else
2260     {
2261         regType  = TYP_I_IMPL;
2262         loadType = temp->tdTempType();
2263         prefMask = genRegMask(oldReg);
2264         freeMask = rsRegMaskFree();
2265     }
2266
2267     if ((((prefMask & needReg) != 0) || (needReg == 0)) && ((prefMask & freeMask) != 0))
2268     {
2269         needReg = prefMask;
2270     }
2271
2272     if (floatUnspill)
2273     {
2274         RegisterPreference pref(RBM_ALLFLOAT, needReg);
2275         newReg = PickRegFloat(regType, &pref, true);
2276     }
2277     else
2278     {
2279         newReg = rsGrabReg(rsUseIfZero(needReg, RBM_ALLINT));
2280     }
2281
2282     m_rsCompiler->codeGen->trashReg(newReg);
2283
2284     /* Reload the value from the saved location into the new register */
2285
2286     m_rsCompiler->codeGen->reloadReg(loadType, temp, newReg);
2287
2288     if (multiUsed && (willKeepNewReg == KEEP_REG))
2289     {
2290         /* We will unspill all the other multi-use trees if the register
2291            is going to be marked as used. If it is not going to be marked
2292            as used, we will have a problem if the new register gets spilled
2293            again.
2294          */
2295
2296         /* We don't do the extra unspilling for complex address modes,
2297            since someone up the call chain may have a different idea about
2298            what registers are used to form the complex address mode (the
2299            addrReg return value from genMakeAddressable).
2300
2301            Also, it is not safe to unspill all the multi-uses with a TYP_LONG.
2302
2303            Finally, it is not safe to unspill into a different register, because
2304            the caller of genMakeAddressable caches the addrReg return value
2305            (register mask), but when unspilling into a different register it's
2306            not possible to inform the caller that addrReg is now different.
2307            See bug #89946 for an example of this.  There is an assert for this
2308            in rsMarkRegFree via genDoneAddressable.
2309          */
2310
2311         for (SpillDsc* dsc = multiDsc; /**/; dsc = dsc->spillNext)
2312         {
2313             if ((oldReg != newReg) || (dsc->spillAddr != NULL) || (dsc->spillTree->gtType == TYP_LONG))
2314             {
2315                 return newReg;
2316             }
2317
2318             if (!dsc->spillMoreMultis)
2319             {
2320                 /* All the remaining multi-uses are fine. We will now
2321                    unspill them all */
2322                 break;
2323             }
2324         }
2325
2326         bool       bFound = false;
2327         SpillDsc*  pDsc;
2328         SpillDsc** ppPrev;
2329
2330         for (pDsc = rsSpillDesc[oldReg], ppPrev = &rsSpillDesc[oldReg];; pDsc = pDsc->spillNext)
2331         {
2332             if (pDsc == multiDsc)
2333             {
2334                 // We've found the sequence we were searching for
2335                 bFound = true;
2336             }
2337
2338             if (bFound)
2339             {
2340                 rsAddrUnspillOper(pDsc->spillAddr);
2341
2342                 // Mark the tree node as having been unspilled into newReg
2343                 rsMarkUnspill(pDsc->spillTree, newReg);
2344             }
2345
2346             if (!pDsc->spillMoreMultis)
2347             {
2348                 if (bFound)
2349                 {
2350                     // End of sequence
2351
2352                     // We link remaining sides of list
2353                     *ppPrev = pDsc->spillNext;
2354
2355                     // Exit walk
2356                     break;
2357                 }
2358                 else
2359                 {
2360                     ppPrev = &(pDsc->spillNext);
2361                 }
2362             }
2363         }
2364
2365         /* pDsc points to the last multi-used descriptor from the spill-list
2366            for the current value (pDsc->spillMoreMultis == false) */
2367
2368         pDsc->spillNext     = rsMultiDesc[newReg];
2369         rsMultiDesc[newReg] = multiDsc;
2370
2371         if (floatUnspill)
2372             rsMaskMult |= genRegMaskFloat(newReg, regType);
2373         else
2374             rsMaskMult |= genRegMask(newReg);
2375     }
2376
2377     if (!multiUsed || (willKeepNewReg == KEEP_REG))
2378     {
2379         // Free the temp, it's no longer used.
2380         // For multi-used regs that aren't (willKeepNewReg == KEEP_REG), we didn't unspill everything, so
2381         // we need to leave the temp for future unspilling.
2382         m_rsCompiler->tmpRlsTemp(temp);
2383     }
2384
2385     return newReg;
2386 }
2387 #endif // LEGACY_BACKEND
2388
2389 //---------------------------------------------------------------------
2390 //  rsUnspillInPlace: The given tree operand has been spilled; just mark
2391 //  it as unspilled so that we can use it as "normal" local.
2392 //
2393 //  Arguments:
2394 //     tree    -  GenTree that needs to be marked as unspilled.
2395 //     oldReg  -  reg of tree that was spilled.
2396 //
2397 //  Return Value:
2398 //     None.
2399 //
2400 //  Assumptions:
2401 //  1. It is the responsibility of the caller to free the spill temp.
2402 //  2. RyuJIT backend specific: In case of multi-reg call node
2403 //     GTF_SPILLED flag associated with reg is cleared.  It is the
2404 //     responsibility of caller to clear GTF_SPILLED flag on call node
2405 //     itself after ensuring there are no outstanding regs in GTF_SPILLED
2406 //     state.
2407 //
2408 TempDsc* RegSet::rsUnspillInPlace(GenTree* tree, regNumber oldReg, unsigned regIdx /* =0 */)
2409 {
2410     assert(!isRegPairType(tree->gtType));
2411
2412     // Get the tree's SpillDsc
2413     SpillDsc* prevDsc;
2414     SpillDsc* spillDsc = rsGetSpillInfo(tree, oldReg, &prevDsc);
2415     PREFIX_ASSUME(spillDsc != nullptr);
2416
2417     // Get the temp
2418     TempDsc* temp = rsGetSpillTempWord(oldReg, spillDsc, prevDsc);
2419
2420     // The value is now unspilled
2421     if (tree->IsMultiRegCall())
2422     {
2423         GenTreeCall* call  = tree->AsCall();
2424         unsigned     flags = call->GetRegSpillFlagByIdx(regIdx);
2425         flags &= ~GTF_SPILLED;
2426         call->SetRegSpillFlagByIdx(flags, regIdx);
2427     }
2428 #if !defined(LEGACY_BACKEND) && defined(_TARGET_ARM_)
2429     else if (tree->OperIsPutArgSplit())
2430     {
2431         GenTreePutArgSplit* splitArg = tree->AsPutArgSplit();
2432         unsigned            flags    = splitArg->GetRegSpillFlagByIdx(regIdx);
2433         flags &= ~GTF_SPILLED;
2434         splitArg->SetRegSpillFlagByIdx(flags, regIdx);
2435     }
2436     else if (tree->OperIsMultiRegOp())
2437     {
2438         GenTreeMultiRegOp* multiReg = tree->AsMultiRegOp();
2439         unsigned           flags    = multiReg->GetRegSpillFlagByIdx(regIdx);
2440         flags &= ~GTF_SPILLED;
2441         multiReg->SetRegSpillFlagByIdx(flags, regIdx);
2442     }
2443 #endif // !LEGACY_BACKEND && _TARGET_ARM_
2444     else
2445     {
2446         tree->gtFlags &= ~GTF_SPILLED;
2447     }
2448
2449 #ifdef DEBUG
2450     if (m_rsCompiler->verbose)
2451     {
2452         printf("\t\t\t\t\t\t\tTree-Node marked unspilled from  ");
2453         Compiler::printTreeID(tree);
2454         printf("\n");
2455     }
2456 #endif
2457
2458     return temp;
2459 }
2460
2461 #ifdef LEGACY_BACKEND
2462
2463 /*****************************************************************************
2464  *
2465  *  The given tree operand has been spilled; reload it into a register that
2466  *  is in 'needReg' (if 'needReg' is RBM_NONE, any register will do). If 'keepReg'
2467  *  is set to KEEP_REG, we'll mark the new register as used.
2468  */
2469
2470 void RegSet::rsUnspillReg(GenTree* tree, regMaskTP needReg, KeepReg keepReg)
2471 {
2472     assert(!isRegPairType(tree->gtType)); // use rsUnspillRegPair()
2473     regNumber oldReg = tree->gtRegNum;
2474
2475     /* Get the SpillDsc for the tree */
2476
2477     SpillDsc* spillDsc = rsGetSpillInfo(tree, oldReg);
2478     PREFIX_ASSUME(spillDsc != NULL);
2479
2480     /* Before spillDsc is stomped on by rsUnspillOneReg(), note whether
2481      * the reg was part of an address mode
2482      */
2483
2484     GenTree* unspillAddr = spillDsc->spillAddr;
2485
2486     /* Pick a new home for the value */
2487
2488     regNumber newReg = rsUnspillOneReg(tree, oldReg, keepReg, needReg);
2489
2490     /* Mark the tree node as having been unspilled into newReg */
2491
2492     rsMarkUnspill(tree, newReg);
2493
2494     // If this reg was part of a complex address mode, need to clear this flag which
2495     // tells address mode building that a component has been spilled
2496
2497     rsAddrUnspillOper(unspillAddr);
2498
2499 #ifdef DEBUG
2500     if (m_rsCompiler->verbose)
2501     {
2502         printf("\t\t\t\t\t\t\tThe register %s unspilled from  ", m_rsCompiler->compRegVarName(newReg));
2503         Compiler::printTreeID(tree);
2504         printf("\n");
2505     }
2506 #endif
2507
2508     /* Mark the new value as used, if the caller desires so */
2509
2510     if (keepReg == KEEP_REG)
2511         rsMarkRegUsed(tree, unspillAddr);
2512 }
2513 #endif // LEGACY_BACKEND
2514
2515 void RegSet::rsMarkSpill(GenTree* tree, regNumber reg)
2516 {
2517 #ifdef LEGACY_BACKEND
2518     tree->SetInReg(false);
2519 #endif
2520     tree->gtFlags |= GTF_SPILLED;
2521 }
2522
2523 #ifdef LEGACY_BACKEND
2524
2525 void RegSet::rsMarkUnspill(GenTree* tree, regNumber reg)
2526 {
2527 #ifndef _TARGET_AMD64_
2528     assert(tree->gtType != TYP_LONG);
2529 #endif // _TARGET_AMD64_
2530
2531     tree->gtFlags &= ~GTF_SPILLED;
2532     tree->gtRegNum = reg;
2533     tree->SetInReg();
2534 }
2535
2536 /*****************************************************************************
2537  *
2538  *  Choose a register pair from the given set (note: only registers in the
2539  *  given set will be considered).
2540  */
2541
2542 regPairNo RegSet::rsGrabRegPair(regMaskTP regMask)
2543 {
2544     regPairNo regPair;
2545     regMaskTP OKmask;
2546     regNumber reg1;
2547     regNumber reg2;
2548
2549     assert(regMask);
2550     regMask &= ~rsMaskLock;
2551     assert(regMask);
2552
2553     /* We'd prefer to choose a free register pair if possible */
2554
2555     OKmask = regMask & rsRegMaskFree();
2556
2557     /* Any takers in the recommended/free set? */
2558
2559     regPair = rsFindRegPairNo(OKmask);
2560
2561     if (regPair != REG_PAIR_NONE)
2562     {
2563         // The normal early exit
2564
2565         /* Keep track of which registers we ever touch */
2566         rsSetRegsModified(genRegPairMask(regPair));
2567
2568         return regPair;
2569     }
2570
2571     /* We have no choice but to spill one or two used regs */
2572
2573     if (OKmask)
2574     {
2575         /* One (and only one) register is free and acceptable - grab it */
2576
2577         assert(genMaxOneBit(OKmask));
2578
2579         for (reg1 = REG_INT_FIRST; reg1 <= REG_INT_LAST; reg1 = REG_NEXT(reg1))
2580         {
2581             if (OKmask & genRegMask(reg1))
2582                 break;
2583         }
2584         assert(OKmask & genRegMask(reg1));
2585     }
2586     else
2587     {
2588         /* No register is free and acceptable - we'll have to spill two */
2589
2590         reg1 = rsGrabReg(regMask);
2591     }
2592
2593     /* Temporarily lock the first register so it doesn't go away */
2594
2595     rsLockReg(genRegMask(reg1));
2596
2597     /* Now grab another register */
2598
2599     reg2 = rsGrabReg(regMask);
2600
2601     /* We can unlock the first register now */
2602
2603     rsUnlockReg(genRegMask(reg1));
2604
2605     /* Convert the two register numbers into a pair */
2606
2607     if (reg1 < reg2)
2608         regPair = gen2regs2pair(reg1, reg2);
2609     else
2610         regPair = gen2regs2pair(reg2, reg1);
2611
2612     return regPair;
2613 }
2614
2615 /*****************************************************************************
2616  *
2617  *  Choose a register pair from the given set (if non-zero) or from the set of
2618  *  currently available registers (if 'regMask' is zero).
2619  */
2620
2621 regPairNo RegSet::rsPickRegPair(regMaskTP regMask)
2622 {
2623     regMaskTP OKmask;
2624     regPairNo regPair;
2625
2626     int repeat = 0;
2627
2628     /* By default we'd prefer to accept all available registers */
2629
2630     OKmask = rsRegMaskFree();
2631
2632     if (regMask)
2633     {
2634         /* A register set was recommended by the caller */
2635
2636         OKmask &= regMask;
2637     }
2638
2639 AGAIN:
2640
2641     regPair = rsFindRegPairNo(OKmask);
2642
2643     if (regPair != REG_PAIR_NONE)
2644     {
2645         return regPair; // Normal early exit
2646     }
2647
2648     regMaskTP freeMask;
2649     regMaskTP spillMask;
2650
2651     /* Now let's consider all available registers */
2652
2653     freeMask = rsRegMaskFree();
2654
2655     /* Were we limited in our consideration? */
2656
2657     if (!regMask)
2658     {
2659         /* We need to spill two of the free registers */
2660
2661         spillMask = freeMask;
2662     }
2663     else
2664     {
2665         /* Did we not consider all free registers? */
2666
2667         if ((regMask & freeMask) != freeMask && repeat == 0)
2668         {
2669             /* The recommended regset didn't work, so try all available regs */
2670
2671             OKmask = freeMask;
2672             repeat++;
2673             goto AGAIN;
2674         }
2675
2676         /* If we're going to spill, might as well go for the right one */
2677
2678         spillMask = regMask;
2679     }
2680
2681     /* Make sure that we have at least two bits set */
2682
2683     if (genMaxOneBit(spillMask & rsRegMaskCanGrab()))
2684         spillMask = rsRegMaskCanGrab();
2685
2686     assert(!genMaxOneBit(spillMask));
2687
2688     /* We have no choice but to spill 1/2 of the regs */
2689
2690     return rsGrabRegPair(spillMask);
2691 }
2692
2693 /*****************************************************************************
2694  *
2695  *  The given tree operand has been spilled; reload it into a register pair
2696  *  that is in 'needReg' (if 'needReg' is RBM_NONE, any register pair will do). If
2697  *  'keepReg' is KEEP_REG, we'll mark the new register pair as used. It is
2698  *  assumed that the current register pair has been marked as used (modulo
2699  *  any spillage, of course).
2700  */
2701
2702 void RegSet::rsUnspillRegPair(GenTree* tree, regMaskTP needReg, KeepReg keepReg)
2703 {
2704     assert(isRegPairType(tree->gtType));
2705
2706     regPairNo regPair = tree->gtRegPair;
2707     regNumber regLo   = genRegPairLo(regPair);
2708     regNumber regHi   = genRegPairHi(regPair);
2709
2710     /* Has the register holding the lower half been spilled? */
2711
2712     if (!rsIsTreeInReg(regLo, tree))
2713     {
2714         /* Is the upper half already in the right place? */
2715
2716         if (rsIsTreeInReg(regHi, tree))
2717         {
2718             // Temporarily lock the high part if necessary. If this register is a multi-use register that is shared
2719             // with another tree, the register may already be locked.
2720             const regMaskTP regHiMask = genRegMask(regHi);
2721             const bool      lockReg   = (rsMaskLock & regHiMask) == 0;
2722             if (lockReg)
2723             {
2724                 rsLockUsedReg(regHiMask);
2725             }
2726
2727             /* Pick a new home for the lower half */
2728
2729             regLo = rsUnspillOneReg(tree, regLo, keepReg, needReg);
2730
2731             /* We can unlock the high part now */
2732             if (lockReg)
2733             {
2734                 rsUnlockUsedReg(regHiMask);
2735             }
2736         }
2737         else
2738         {
2739             /* Pick a new home for the lower half */
2740
2741             regLo = rsUnspillOneReg(tree, regLo, keepReg, needReg);
2742         }
2743     }
2744     else
2745     {
2746         /* Free the register holding the lower half */
2747
2748         rsMarkRegFree(genRegMask(regLo));
2749     }
2750
2751     if (regHi != REG_STK)
2752     {
2753         /* Has the register holding the upper half been spilled? */
2754
2755         if (!rsIsTreeInReg(regHi, tree))
2756         {
2757             regMaskTP regLoUsed = RBM_NONE;
2758
2759             // Temporarily lock the low part if necessary. If this register is a multi-use register that is shared
2760             // with another tree, the register may already be locked.
2761             const regMaskTP regLoMask = genRegMask(regLo);
2762             const bool      lockReg   = (rsMaskLock & regLoMask) == 0;
2763             if (lockReg)
2764             {
2765                 rsLockReg(regLoMask, &regLoUsed);
2766             }
2767
2768             /* Pick a new home for the upper half */
2769
2770             regHi = rsUnspillOneReg(tree, regHi, keepReg, needReg);
2771
2772             /* We can unlock the low register now */
2773             if (lockReg)
2774             {
2775                 rsUnlockReg(regLoMask, regLoUsed);
2776             }
2777         }
2778         else
2779         {
2780             /* Free the register holding the upper half */
2781
2782             rsMarkRegFree(genRegMask(regHi));
2783         }
2784     }
2785
2786     /* The value is now residing in the new register */
2787
2788     tree->SetInReg();
2789     tree->gtFlags &= ~GTF_SPILLED;
2790     tree->gtRegPair = gen2regs2pair(regLo, regHi);
2791
2792     /* Mark the new value as used, if the caller desires so */
2793
2794     if (keepReg == KEEP_REG)
2795         rsMarkRegPairUsed(tree);
2796 }
2797
2798 /*****************************************************************************
2799  *
2800  *  The given register is being used by multiple trees (all of which represent
2801  *  the same logical value). Happens mainly because of REDUNDANT_LOAD;
2802  *  We don't want to really spill the register as it actually holds the
2803  *  value we want. But the multiple trees may be part of different
2804  *  addressing modes.
2805  *  Save the previous 'use' info so that when we return the register will
2806  *  appear unused.
2807  */
2808
2809 void RegSet::rsRecMultiReg(regNumber reg, var_types type)
2810 {
2811     SpillDsc* spill;
2812     regMaskTP regMask;
2813
2814     if (genIsValidFloatReg(reg) && isFloatRegType(type))
2815         regMask = genRegMaskFloat(reg, type);
2816     else
2817         regMask = genRegMask(reg);
2818
2819 #ifdef DEBUG
2820     if (m_rsCompiler->verbose)
2821     {
2822         printf("\t\t\t\t\t\t\tRegister %s multi-use inc for   ", m_rsCompiler->compRegVarName(reg));
2823         Compiler::printTreeID(rsUsedTree[reg]);
2824         printf(" multMask=" REG_MASK_ALL_FMT "\n", rsMaskMult | regMask);
2825     }
2826 #endif
2827
2828     /* The register is supposed to be already used */
2829
2830     assert(regMask & rsMaskUsed);
2831
2832     assert(rsUsedTree[reg]);
2833
2834     /* Allocate/reuse a spill descriptor */
2835
2836     spill = SpillDsc::alloc(m_rsCompiler, this, rsUsedTree[reg]->TypeGet());
2837
2838     /* Record the current 'use' info in the spill descriptor */
2839
2840     spill->spillTree = rsUsedTree[reg];
2841     rsUsedTree[reg]  = 0;
2842     spill->spillAddr = rsUsedAddr[reg];
2843     rsUsedAddr[reg]  = 0;
2844
2845     /* Remember whether the register is already 'multi-use' */
2846
2847     spill->spillMoreMultis = ((rsMaskMult & regMask) != 0);
2848
2849     /* Insert the new multi-use record in the list for the register */
2850
2851     spill->spillNext = rsMultiDesc[reg];
2852     rsMultiDesc[reg] = spill;
2853
2854     /* This register is now 'multi-use' */
2855
2856     rsMaskMult |= regMask;
2857 }
2858
2859 /*****************************************************************************
2860  *
2861  *  Free the given register, which is known to have multiple uses.
2862  */
2863
2864 var_types RegSet::rsRmvMultiReg(regNumber reg)
2865 {
2866     SpillDsc* dsc;
2867
2868     assert(rsMaskMult & genRegMask(reg));
2869
2870 #ifdef DEBUG
2871     if (m_rsCompiler->verbose)
2872     {
2873         printf("\t\t\t\t\t\t\tRegister %s multi-use dec for   ", m_rsCompiler->compRegVarName(reg));
2874         Compiler::printTreeID(rsUsedTree[reg]);
2875         printf(" multMask=" REG_MASK_ALL_FMT "\n", rsMaskMult);
2876     }
2877 #endif
2878
2879     /* Get hold of the spill descriptor for the register */
2880
2881     dsc = rsMultiDesc[reg];
2882     assert(dsc);
2883     rsMultiDesc[reg] = dsc->spillNext;
2884
2885     /* Copy the previous 'use' info from the descriptor */
2886
2887     assert(reg != REG_SPBASE);
2888     rsUsedTree[reg] = dsc->spillTree;
2889     rsUsedAddr[reg] = dsc->spillAddr;
2890
2891     if (!(dsc->spillTree->gtFlags & GTF_SPILLED))
2892         m_rsGCInfo.gcMarkRegPtrVal(reg, dsc->spillTree->TypeGet());
2893
2894     var_types type = dsc->spillTree->TypeGet();
2895     regMaskTP regMask;
2896
2897     if (genIsValidFloatReg(reg) && isFloatRegType(type))
2898         regMask = genRegMaskFloat(reg, type);
2899     else
2900         regMask = genRegMask(reg);
2901
2902     /* Is only one use of the register left? */
2903
2904     if (!dsc->spillMoreMultis)
2905     {
2906         rsMaskMult -= regMask;
2907     }
2908
2909 #ifdef DEBUG
2910     if (m_rsCompiler->verbose)
2911     {
2912         printf("\t\t\t\t\t\t\tRegister %s multi-use dec - now ", m_rsCompiler->compRegVarName(reg));
2913         Compiler::printTreeID(rsUsedTree[reg]);
2914         printf(" multMask=" REG_MASK_ALL_FMT "\n", rsMaskMult);
2915     }
2916 #endif
2917
2918     SpillDsc::freeDsc(this, dsc);
2919     return type;
2920 }
2921 /*****************************************************************************/
2922 /*****************************************************************************
2923  *
2924  *  Search for a register which contains the given constant value.
2925  *  Return success/failure and set the register if success.
2926  *  If the closeDelta argument is non-NULL then look for a
2927  *  register that has a close constant value. For ARM, find
2928  *  the closest register value, independent of constant delta.
2929  *  For non-ARM, only consider values that are within -128..+127.
2930  *  If one is found, *closeDelta is set to the difference that needs
2931  *  to be added to the register returned. On x86/amd64, an lea instruction
2932  *  is used to set the target register using the register that
2933  *  contains the close integer constant.
2934  */
2935
2936 regNumber RegTracker::rsIconIsInReg(ssize_t val, ssize_t* closeDelta /* = NULL */)
2937 {
2938     regNumber closeReg = REG_NA;
2939
2940     if (compiler->opts.MinOpts() || compiler->opts.compDbgCode)
2941     {
2942         return REG_NA;
2943     }
2944
2945     for (regNumber reg = REG_INT_FIRST; reg <= REG_INT_LAST; reg = REG_NEXT(reg))
2946     {
2947         if (rsRegValues[reg].rvdKind == RV_INT_CNS)
2948         {
2949             ssize_t regCnsVal = rsRegValues[reg].rvdIntCnsVal;
2950             if (regCnsVal == val)
2951             {
2952                 if (closeDelta)
2953                 {
2954                     *closeDelta = 0;
2955                 }
2956                 return reg;
2957             }
2958             if (closeDelta)
2959             {
2960 #ifdef _TARGET_ARM_
2961                 // Find the smallest delta; the caller checks the size
2962                 // TODO-CQ: find the smallest delta from a low register?
2963                 //       That is, is it better to return a high register with a
2964                 //       small constant delta, or a low register with
2965                 //       a larger offset? It's better to have a low register with an offset within the low register
2966                 //       range, or a high register otherwise...
2967
2968                 ssize_t regCnsDelta = val - regCnsVal;
2969                 if ((closeReg == REG_NA) || (unsigned_abs(regCnsDelta) < unsigned_abs(*closeDelta)))
2970                 {
2971                     closeReg    = reg;
2972                     *closeDelta = regCnsDelta;
2973                 }
2974 #else
2975                 if (closeReg == REG_NA)
2976                 {
2977                     ssize_t regCnsDelta = val - regCnsVal;
2978                     /* Does delta fit inside a byte [-128..127] */
2979                     if (regCnsDelta == (signed char)regCnsDelta)
2980                     {
2981                         closeReg    = reg;
2982                         *closeDelta = (int)regCnsDelta;
2983                     }
2984                 }
2985 #endif
2986             }
2987         }
2988     }
2989
2990     /* There was not an exact match */
2991
2992     return closeReg; /* will always be REG_NA when closeDelta is NULL */
2993 }
2994
2995 /*****************************************************************************
2996  *
2997  *  Assume all non-integer registers contain garbage (this is called when
2998  *  we encounter a code label that isn't jumped by any block; we need to
2999  *  clear pointer values out of the table lest the GC pointer tables get
3000  *  out of date).
3001  */
3002
3003 void RegTracker::rsTrackRegClrPtr()
3004 {
3005     for (regNumber reg = REG_FIRST; reg < REG_COUNT; reg = REG_NEXT(reg))
3006     {
3007         /* Preserve constant values */
3008
3009         if (rsRegValues[reg].rvdKind == RV_INT_CNS)
3010         {
3011             /* Make sure we don't preserve NULL (it's a pointer) */
3012
3013             if (rsRegValues[reg].rvdIntCnsVal != NULL)
3014             {
3015                 continue;
3016             }
3017         }
3018
3019         /* Preserve variables known to not be pointers */
3020
3021         if (rsRegValues[reg].rvdKind == RV_LCL_VAR)
3022         {
3023             if (!varTypeIsGC(compiler->lvaTable[rsRegValues[reg].rvdLclVarNum].TypeGet()))
3024             {
3025                 continue;
3026             }
3027         }
3028
3029         rsRegValues[reg].rvdKind = RV_TRASH;
3030     }
3031 }
3032
3033 /*****************************************************************************
3034  *
3035  *  This routine trashes the registers that hold stack GCRef/ByRef variables. (VSW: 561129)
3036  *  It should be called at each gc-safe point.
3037  *
3038  *  It returns a mask of the registers that used to contain tracked stack variables that
3039  *  were trashed.
3040  *
3041  */
3042
3043 regMaskTP RegTracker::rsTrashRegsForGCInterruptability()
3044 {
3045     regMaskTP result = RBM_NONE;
3046     for (regNumber reg = REG_FIRST; reg < REG_COUNT; reg = REG_NEXT(reg))
3047     {
3048         if (rsRegValues[reg].rvdKind == RV_LCL_VAR)
3049         {
3050             LclVarDsc* varDsc = &compiler->lvaTable[rsRegValues[reg].rvdLclVarNum];
3051
3052             if (!varTypeIsGC(varDsc->TypeGet()))
3053             {
3054                 continue;
3055             }
3056
3057             // Only stack locals got tracked.
3058             assert(!varDsc->lvRegister);
3059
3060             rsRegValues[reg].rvdKind = RV_TRASH;
3061
3062             result |= genRegMask(reg);
3063         }
3064     }
3065
3066     return result;
3067 }
3068
3069 /*****************************************************************************
3070  *
3071  *  Search for a register which contains the given local var.
3072  *  Return success/failure and set the register if success.
3073  *  Return FALSE on register variables, because otherwise their lifetimes
3074  *  can get bungled with respect to pointer tracking.
3075  */
3076
3077 regNumber RegTracker::rsLclIsInReg(unsigned var)
3078 {
3079     assert(var < compiler->lvaCount);
3080
3081     if (compiler->opts.MinOpts() || compiler->opts.compDbgCode)
3082     {
3083         return REG_NA;
3084     }
3085
3086     /* return false if register var so genMarkLclVar can do its job */
3087
3088     if (compiler->lvaTable[var].lvRegister)
3089     {
3090         return REG_NA;
3091     }
3092
3093     for (regNumber reg = REG_FIRST; reg < REG_COUNT; reg = REG_NEXT(reg))
3094     {
3095         if (rsRegValues[reg].rvdLclVarNum == var && rsRegValues[reg].rvdKind == RV_LCL_VAR)
3096         {
3097             return reg;
3098         }
3099     }
3100
3101     return REG_NA;
3102 }
3103
3104 /*****************************************************************************/
3105
3106 regPairNo RegTracker::rsLclIsInRegPair(unsigned var)
3107 {
3108     assert(var < compiler->lvaCount);
3109
3110     if (compiler->opts.MinOpts() || compiler->opts.compDbgCode)
3111     {
3112         return REG_PAIR_NONE;
3113     }
3114
3115     regValKind rvKind = RV_TRASH;
3116     regNumber  regNo  = DUMMY_INIT(REG_NA);
3117
3118     for (regNumber reg = REG_FIRST; reg < REG_COUNT; reg = REG_NEXT(reg))
3119     {
3120         if (rvKind != rsRegValues[reg].rvdKind && rsTrackIsLclVarLng(rsRegValues[reg].rvdKind) &&
3121             rsRegValues[reg].rvdLclVarNum == var)
3122         {
3123             /* first occurrence of this variable ? */
3124
3125             if (rvKind == RV_TRASH)
3126             {
3127                 regNo  = reg;
3128                 rvKind = rsRegValues[reg].rvdKind;
3129             }
3130             else if (rvKind == RV_LCL_VAR_LNG_HI)
3131             {
3132                 /* We found the lower half of the long */
3133
3134                 return gen2regs2pair(reg, regNo);
3135             }
3136             else
3137             {
3138                 /* We found the upper half of the long */
3139
3140                 assert(rvKind == RV_LCL_VAR_LNG_LO);
3141                 return gen2regs2pair(regNo, reg);
3142             }
3143         }
3144     }
3145
3146     return REG_PAIR_NONE;
3147 }
3148
3149 /*****************************************************************************/
3150
3151 void RegTracker::rsTrashLclLong(unsigned var)
3152 {
3153     if (compiler->opts.MinOpts() || compiler->opts.compDbgCode)
3154     {
3155         return;
3156     }
3157
3158     for (regNumber reg = REG_FIRST; reg < REG_COUNT; reg = REG_NEXT(reg))
3159     {
3160         if (rsTrackIsLclVarLng(rsRegValues[reg].rvdKind) && rsRegValues[reg].rvdLclVarNum == var)
3161         {
3162             rsRegValues[reg].rvdKind = RV_TRASH;
3163         }
3164     }
3165 }
3166
3167 /*****************************************************************************
3168  *
3169  *  Local's value has changed, mark all regs which contained it as trash.
3170  */
3171
3172 void RegTracker::rsTrashLcl(unsigned var)
3173 {
3174     if (compiler->opts.MinOpts() || compiler->opts.compDbgCode)
3175     {
3176         return;
3177     }
3178
3179     for (regNumber reg = REG_FIRST; reg < REG_COUNT; reg = REG_NEXT(reg))
3180     {
3181         if (rsRegValues[reg].rvdKind == RV_LCL_VAR && rsRegValues[reg].rvdLclVarNum == var)
3182         {
3183             rsRegValues[reg].rvdKind = RV_TRASH;
3184         }
3185     }
3186 }
3187 #endif // LEGACY_BACKEND
3188
3189 /*****************************************************************************
3190  *
3191  *  A little helper to trash the given set of registers.
3192  *  Usually used after a call has been generated.
3193  */
3194
3195 void RegTracker::rsTrashRegSet(regMaskTP regMask)
3196 {
3197     if (compiler->opts.MinOpts() || compiler->opts.compDbgCode)
3198     {
3199         return;
3200     }
3201     regMaskTP regBit = 1;
3202     for (regNumber regNum = REG_FIRST; regMask != 0; regNum = REG_NEXT(regNum), regBit <<= 1)
3203     {
3204         if (regBit & regMask)
3205         {
3206             rsTrackRegTrash(regNum);
3207             regMask -= regBit;
3208         }
3209     }
3210 }
3211
3212 #ifdef LEGACY_BACKEND
3213 /*****************************************************************************
3214  *
3215  *  Return a mask of registers that hold no useful value.
3216  */
3217
3218 regMaskTP RegTracker::rsUselessRegs()
3219 {
3220     if (compiler->opts.MinOpts() || compiler->opts.compDbgCode)
3221     {
3222         return RBM_ALLINT;
3223     }
3224
3225     regMaskTP mask = RBM_NONE;
3226     for (regNumber reg = REG_FIRST; reg < REG_COUNT; reg = REG_NEXT(reg))
3227     {
3228         if (rsRegValues[reg].rvdKind == RV_TRASH)
3229         {
3230             mask |= genRegMask(reg);
3231         }
3232     }
3233
3234     return mask;
3235 }
3236
3237 /*****************************************************************************/
3238 #endif // LEGACY_BACKEND
3239 /*****************************************************************************/
3240
3241 /*
3242 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
3243 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
3244 XX                                                                           XX
3245 XX                           TempsInfo                                       XX
3246 XX                                                                           XX
3247 XX  The temporary lclVars allocated by the compiler for code generation      XX
3248 XX                                                                           XX
3249 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
3250 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
3251 */
3252
3253 void Compiler::tmpInit()
3254 {
3255 #ifdef LEGACY_BACKEND
3256     tmpDoubleSpillMax = 0;
3257     tmpIntSpillMax    = 0;
3258 #endif // LEGACY_BACKEND
3259
3260     tmpCount = 0;
3261     tmpSize  = 0;
3262 #ifdef DEBUG
3263     tmpGetCount = 0;
3264 #endif
3265
3266     memset(tmpFree, 0, sizeof(tmpFree));
3267     memset(tmpUsed, 0, sizeof(tmpUsed));
3268 }
3269
3270 /* static */
3271 var_types Compiler::tmpNormalizeType(var_types type)
3272 {
3273 #ifndef LEGACY_BACKEND
3274
3275     type = genActualType(type);
3276
3277 #if defined(FEATURE_SIMD) && !defined(_TARGET_64BIT_)
3278     // For SIMD on 32-bit platforms, we always spill SIMD12 to a 16-byte SIMD16 temp.
3279     // This is because we don't have a single instruction to store 12 bytes. We also
3280     // allocate non-argument locals as 16 bytes; see lvSize().
3281     if (type == TYP_SIMD12)
3282     {
3283         type = TYP_SIMD16;
3284     }
3285 #endif // defined(FEATURE_SIMD) && !defined(_TARGET_64BIT_)
3286
3287 #else  // LEGACY_BACKEND
3288     if (!varTypeIsGC(type))
3289     {
3290         switch (genTypeStSz(type))
3291         {
3292             case 1:
3293                 type = TYP_INT; // Maps all 4-byte non-GC types to TYP_INT temps
3294                 break;
3295             case 2:
3296                 type = TYP_DOUBLE; // Maps all 8-byte types to TYP_DOUBLE temps
3297                 break;
3298             default:
3299                 assert(!"unexpected type");
3300         }
3301     }
3302 #endif // LEGACY_BACKEND
3303
3304     return type;
3305 }
3306
3307 /*****************************************************************************
3308  *
3309  *  Allocate a temp of the given size (and type, if tracking pointers for
3310  *  the garbage collector).
3311  */
3312
3313 TempDsc* Compiler::tmpGetTemp(var_types type)
3314 {
3315     type          = tmpNormalizeType(type);
3316     unsigned size = genTypeSize(type);
3317
3318     // If TYP_STRUCT ever gets in here we do bad things (tmpSlot returns -1)
3319     noway_assert(size >= sizeof(int));
3320
3321     /* Find the slot to search for a free temp of the right size */
3322
3323     unsigned slot = tmpSlot(size);
3324
3325     /* Look for a temp with a matching type */
3326
3327     TempDsc** last = &tmpFree[slot];
3328     TempDsc*  temp;
3329
3330     for (temp = *last; temp; last = &temp->tdNext, temp = *last)
3331     {
3332         /* Does the type match? */
3333
3334         if (temp->tdTempType() == type)
3335         {
3336             /* We have a match -- remove it from the free list */
3337
3338             *last = temp->tdNext;
3339             break;
3340         }
3341     }
3342
3343 #ifdef DEBUG
3344     /* Do we need to allocate a new temp */
3345     bool isNewTemp = false;
3346 #endif // DEBUG
3347
3348 #ifndef LEGACY_BACKEND
3349
3350     noway_assert(temp != nullptr);
3351
3352 #else // LEGACY_BACKEND
3353
3354     if (temp == nullptr)
3355     {
3356 #ifdef DEBUG
3357         isNewTemp = true;
3358 #endif // DEBUG
3359         tmpCount++;
3360         tmpSize += (unsigned)size;
3361
3362 #ifdef _TARGET_ARM_
3363         if (type == TYP_DOUBLE)
3364         {
3365             // Adjust tmpSize in case it needs alignment
3366             tmpSize += TARGET_POINTER_SIZE;
3367         }
3368 #endif // _TARGET_ARM_
3369
3370         genEmitter->emitTmpSizeChanged(tmpSize);
3371
3372         temp = new (this, CMK_Unknown) TempDsc(-((int)tmpCount), size, type);
3373     }
3374
3375 #endif // LEGACY_BACKEND
3376
3377 #ifdef DEBUG
3378     if (verbose)
3379     {
3380         printf("%s temp #%u, slot %u, size = %u\n", isNewTemp ? "created" : "reused", -temp->tdTempNum(), slot,
3381                temp->tdTempSize());
3382     }
3383     tmpGetCount++;
3384 #endif // DEBUG
3385
3386     temp->tdNext  = tmpUsed[slot];
3387     tmpUsed[slot] = temp;
3388
3389     return temp;
3390 }
3391
3392 #ifndef LEGACY_BACKEND
3393
3394 /*****************************************************************************
3395  * Preallocate 'count' temps of type 'type'. This type must be a normalized
3396  * type (by the definition of tmpNormalizeType()).
3397  *
3398  * This is used at the end of LSRA, which knows precisely the maximum concurrent
3399  * number of each type of spill temp needed, before code generation. Code generation
3400  * then uses these preallocated temp. If code generation ever asks for more than
3401  * has been preallocated, it is a fatal error.
3402  */
3403
3404 void Compiler::tmpPreAllocateTemps(var_types type, unsigned count)
3405 {
3406     assert(type == tmpNormalizeType(type));
3407     unsigned size = genTypeSize(type);
3408
3409     // If TYP_STRUCT ever gets in here we do bad things (tmpSlot returns -1)
3410     noway_assert(size >= sizeof(int));
3411
3412     // Find the slot to search for a free temp of the right size.
3413     // Note that slots are shared by types of the identical size (e.g., TYP_REF and TYP_LONG on AMD64),
3414     // so we can't assert that the slot is empty when we get here.
3415
3416     unsigned slot = tmpSlot(size);
3417
3418     for (unsigned i = 0; i < count; i++)
3419     {
3420         tmpCount++;
3421         tmpSize += size;
3422
3423 #ifdef _TARGET_ARM_
3424         if (type == TYP_DOUBLE)
3425         {
3426             // Adjust tmpSize to accommodate possible alignment padding.
3427             // Note that at this point the offsets aren't yet finalized, so we don't yet know if it will be required.
3428             tmpSize += TARGET_POINTER_SIZE;
3429         }
3430 #endif // _TARGET_ARM_
3431
3432         TempDsc* temp = new (this, CMK_Unknown) TempDsc(-((int)tmpCount), size, type);
3433
3434 #ifdef DEBUG
3435         if (verbose)
3436         {
3437             printf("pre-allocated temp #%u, slot %u, size = %u\n", -temp->tdTempNum(), slot, temp->tdTempSize());
3438         }
3439 #endif // DEBUG
3440
3441         // Add it to the front of the appropriate slot list.
3442         temp->tdNext  = tmpFree[slot];
3443         tmpFree[slot] = temp;
3444     }
3445 }
3446
3447 #endif // !LEGACY_BACKEND
3448
3449 /*****************************************************************************
3450  *
3451  *  Release the given temp.
3452  */
3453
3454 void Compiler::tmpRlsTemp(TempDsc* temp)
3455 {
3456     assert(temp != nullptr);
3457
3458     unsigned slot;
3459
3460     /* Add the temp to the 'free' list */
3461
3462     slot = tmpSlot(temp->tdTempSize());
3463
3464 #ifdef DEBUG
3465     if (verbose)
3466     {
3467         printf("release temp #%u, slot %u, size = %u\n", -temp->tdTempNum(), slot, temp->tdTempSize());
3468     }
3469     assert(tmpGetCount);
3470     tmpGetCount--;
3471 #endif
3472
3473     // Remove it from the 'used' list.
3474
3475     TempDsc** last = &tmpUsed[slot];
3476     TempDsc*  t;
3477     for (t = *last; t != nullptr; last = &t->tdNext, t = *last)
3478     {
3479         if (t == temp)
3480         {
3481             /* Found it! -- remove it from the 'used' list */
3482
3483             *last = t->tdNext;
3484             break;
3485         }
3486     }
3487     assert(t != nullptr); // We better have found it!
3488
3489     // Add it to the free list.
3490
3491     temp->tdNext  = tmpFree[slot];
3492     tmpFree[slot] = temp;
3493 }
3494
3495 /*****************************************************************************
3496  *  Given a temp number, find the corresponding temp.
3497  *
3498  *  When looking for temps on the "free" list, this can only be used after code generation. (This is
3499  *  simply because we have an assert to that effect in tmpListBeg(); we could relax that, or hoist
3500  *  the assert to the appropriate callers.)
3501  *
3502  *  When looking for temps on the "used" list, this can be used any time.
3503  */
3504 TempDsc* Compiler::tmpFindNum(int tnum, TEMP_USAGE_TYPE usageType /* = TEMP_USAGE_FREE */) const
3505 {
3506     assert(tnum < 0); // temp numbers are negative
3507
3508     for (TempDsc* temp = tmpListBeg(usageType); temp != nullptr; temp = tmpListNxt(temp, usageType))
3509     {
3510         if (temp->tdTempNum() == tnum)
3511         {
3512             return temp;
3513         }
3514     }
3515
3516     return nullptr;
3517 }
3518
3519 /*****************************************************************************
3520  *
3521  *  A helper function is used to iterate over all the temps.
3522  */
3523
3524 TempDsc* Compiler::tmpListBeg(TEMP_USAGE_TYPE usageType /* = TEMP_USAGE_FREE */) const
3525 {
3526     TempDsc* const* tmpLists;
3527     if (usageType == TEMP_USAGE_FREE)
3528     {
3529         tmpLists = tmpFree;
3530     }
3531     else
3532     {
3533         tmpLists = tmpUsed;
3534     }
3535
3536     // Return the first temp in the slot for the smallest size
3537     unsigned slot = 0;
3538     while (slot < (TEMP_SLOT_COUNT - 1) && tmpLists[slot] == nullptr)
3539     {
3540         slot++;
3541     }
3542     TempDsc* temp = tmpLists[slot];
3543
3544     return temp;
3545 }
3546
3547 /*****************************************************************************
3548  * Used with tmpListBeg() to iterate over the list of temps.
3549  */
3550
3551 TempDsc* Compiler::tmpListNxt(TempDsc* curTemp, TEMP_USAGE_TYPE usageType /* = TEMP_USAGE_FREE */) const
3552 {
3553     assert(curTemp != nullptr);
3554
3555     TempDsc* temp = curTemp->tdNext;
3556     if (temp == nullptr)
3557     {
3558         unsigned size = curTemp->tdTempSize();
3559
3560         // If there are no more temps in the list, check if there are more
3561         // slots (for bigger sized temps) to walk.
3562
3563         TempDsc* const* tmpLists;
3564         if (usageType == TEMP_USAGE_FREE)
3565         {
3566             tmpLists = tmpFree;
3567         }
3568         else
3569         {
3570             tmpLists = tmpUsed;
3571         }
3572
3573         while (size < TEMP_MAX_SIZE && temp == nullptr)
3574         {
3575             size += sizeof(int);
3576             unsigned slot = tmpSlot(size);
3577             temp          = tmpLists[slot];
3578         }
3579
3580         assert((temp == nullptr) || (temp->tdTempSize() == size));
3581     }
3582
3583     return temp;
3584 }
3585
3586 #ifdef DEBUG
3587 /*****************************************************************************
3588  * Return 'true' if all allocated temps are free (not in use).
3589  */
3590 bool Compiler::tmpAllFree() const
3591 {
3592     // The 'tmpGetCount' should equal the number of things in the 'tmpUsed' lists. This is a convenient place
3593     // to assert that.
3594     unsigned usedCount = 0;
3595     for (TempDsc* temp = tmpListBeg(TEMP_USAGE_USED); temp != nullptr; temp = tmpListNxt(temp, TEMP_USAGE_USED))
3596     {
3597         ++usedCount;
3598     }
3599     assert(usedCount == tmpGetCount);
3600
3601     if (tmpGetCount != 0)
3602     {
3603         return false;
3604     }
3605
3606     for (unsigned i = 0; i < _countof(tmpUsed); i++)
3607     {
3608         if (tmpUsed[i] != nullptr)
3609         {
3610             return false;
3611         }
3612     }
3613
3614     return true;
3615 }
3616
3617 #endif // DEBUG
3618
3619 /*
3620 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
3621 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
3622 XX                                                                           XX
3623 XX  Register-related utility functions                                       XX
3624 XX                                                                           XX
3625 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
3626 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
3627 */
3628
3629 /*****************************************************************************
3630  *
3631  *  Returns whether regPair is a combination of two x86 registers or
3632  *  contains a pseudo register.
3633  *  In debug it also asserts that reg1 and reg2 are not the same.
3634  */
3635
3636 bool genIsProperRegPair(regPairNo regPair)
3637 {
3638     regNumber rlo = genRegPairLo(regPair);
3639     regNumber rhi = genRegPairHi(regPair);
3640
3641     assert(regPair >= REG_PAIR_FIRST && regPair <= REG_PAIR_LAST);
3642
3643     if (rlo == rhi)
3644     {
3645         return false;
3646     }
3647
3648     if (rlo == REG_L_STK || rhi == REG_L_STK)
3649     {
3650         return false;
3651     }
3652
3653     if (rlo >= REG_COUNT || rhi >= REG_COUNT)
3654     {
3655         return false;
3656     }
3657
3658     return (rlo != REG_STK && rhi != REG_STK);
3659 }
3660
3661 /*****************************************************************************
3662  *
3663  *  Given a register that is an argument register
3664  *   returns the next argument register
3665  *
3666  *  Note: that this method will return a non arg register
3667  *   when given REG_ARG_LAST
3668  *
3669  */
3670
3671 regNumber genRegArgNext(regNumber argReg)
3672 {
3673     assert(isValidIntArgReg(argReg) || isValidFloatArgReg(argReg));
3674
3675     switch (argReg)
3676     {
3677
3678 #ifdef _TARGET_AMD64_
3679 #ifdef UNIX_AMD64_ABI
3680
3681         // Linux x64 ABI: REG_RDI, REG_RSI, REG_RDX, REG_RCX, REG_R8, REG_R9
3682         case REG_ARG_0:       // REG_RDI
3683             return REG_ARG_1; // REG_RSI
3684         case REG_ARG_1:       // REG_RSI
3685             return REG_ARG_2; // REG_RDX
3686         case REG_ARG_2:       // REG_RDX
3687             return REG_ARG_3; // REG_RCX
3688         case REG_ARG_3:       // REG_RCX
3689             return REG_ARG_4; // REG_R8
3690
3691 #else // !UNIX_AMD64_ABI
3692
3693         // Windows x64 ABI: REG_RCX, REG_RDX, REG_R8, REG_R9
3694         case REG_ARG_1:       // REG_RDX
3695             return REG_ARG_2; // REG_R8
3696
3697 #endif // !UNIX_AMD64_ABI
3698 #endif // _TARGET_AMD64_
3699
3700         default:
3701             return REG_NEXT(argReg);
3702     }
3703 }
3704
3705 /*****************************************************************************
3706  *
3707  *  The following table determines the order in which callee-saved registers
3708  *  are encoded in GC information at call sites (perhaps among other things).
3709  *  In any case, they establish a mapping from ordinal callee-save reg "indices" to
3710  *  register numbers and corresponding bitmaps.
3711  */
3712
3713 const regNumber raRegCalleeSaveOrder[] = {REG_CALLEE_SAVED_ORDER};
3714 const regMaskTP raRbmCalleeSaveOrder[] = {RBM_CALLEE_SAVED_ORDER};
3715
3716 regMaskSmall genRegMaskFromCalleeSavedMask(unsigned short calleeSaveMask)
3717 {
3718     regMaskSmall res = 0;
3719     for (int i = 0; i < CNT_CALLEE_SAVED; i++)
3720     {
3721         if ((calleeSaveMask & ((regMaskTP)1 << i)) != 0)
3722         {
3723             res |= raRbmCalleeSaveOrder[i];
3724         }
3725     }
3726     return res;
3727 }
3728
3729 /*****************************************************************************
3730  *
3731  *  Initializes the spill code. Should be called once per function compiled.
3732  */
3733
3734 // inline
3735 void RegSet::rsSpillInit()
3736 {
3737     /* Clear out the spill and multi-use tables */
3738
3739     memset(rsSpillDesc, 0, sizeof(rsSpillDesc));
3740
3741 #ifdef LEGACY_BACKEND
3742     memset(rsUsedTree, 0, sizeof(rsUsedTree));
3743     memset(rsUsedAddr, 0, sizeof(rsUsedAddr));
3744     memset(rsMultiDesc, 0, sizeof(rsMultiDesc));
3745     rsSpillFloat = nullptr;
3746 #endif // LEGACY_BACKEND
3747
3748     rsNeededSpillReg = false;
3749
3750     /* We don't have any descriptors allocated */
3751
3752     rsSpillFree = nullptr;
3753 }
3754
3755 /*****************************************************************************
3756  *
3757  *  Shuts down the spill code. Should be called once per function compiled.
3758  */
3759
3760 // inline
3761 void RegSet::rsSpillDone()
3762 {
3763     rsSpillChk();
3764 }
3765
3766 /*****************************************************************************
3767  *
3768  *  Begin tracking spills - should be called each time before a pass is made
3769  *  over a function body.
3770  */
3771
3772 // inline
3773 void RegSet::rsSpillBeg()
3774 {
3775     rsSpillChk();
3776 }
3777
3778 /*****************************************************************************
3779  *
3780  *  Finish tracking spills - should be called each time after a pass is made
3781  *  over a function body.
3782  */
3783
3784 // inline
3785 void RegSet::rsSpillEnd()
3786 {
3787     rsSpillChk();
3788 }
3789
3790 //****************************************************************************
3791 //  Create a new SpillDsc or get one off the free list
3792 //
3793
3794 // inline
3795 RegSet::SpillDsc* RegSet::SpillDsc::alloc(Compiler* pComp, RegSet* regSet, var_types type)
3796 {
3797     RegSet::SpillDsc*  spill;
3798     RegSet::SpillDsc** pSpill;
3799
3800     pSpill = &(regSet->rsSpillFree);
3801
3802     // Allocate spill structure
3803     if (*pSpill)
3804     {
3805         spill   = *pSpill;
3806         *pSpill = spill->spillNext;
3807     }
3808     else
3809     {
3810         spill = (RegSet::SpillDsc*)pComp->compGetMem(sizeof(SpillDsc));
3811     }
3812     return spill;
3813 }
3814
3815 //****************************************************************************
3816 //  Free a SpillDsc and return it to the rsSpillFree list
3817 //
3818
3819 // inline
3820 void RegSet::SpillDsc::freeDsc(RegSet* regSet, RegSet::SpillDsc* spillDsc)
3821 {
3822     spillDsc->spillNext = regSet->rsSpillFree;
3823     regSet->rsSpillFree = spillDsc;
3824 }
3825
3826 /*****************************************************************************
3827  *
3828  *  Make sure no spills are currently active - used for debugging of the code
3829  *  generator.
3830  */
3831
3832 #ifdef DEBUG
3833
3834 // inline
3835 void RegSet::rsSpillChk()
3836 {
3837     // All grabbed temps should have been released
3838     assert(m_rsCompiler->tmpGetCount == 0);
3839
3840     for (regNumber reg = REG_FIRST; reg < REG_COUNT; reg = REG_NEXT(reg))
3841     {
3842         assert(rsSpillDesc[reg] == nullptr);
3843
3844 #ifdef LEGACY_BACKEND
3845         assert(rsUsedTree[reg] == NULL);
3846         assert(rsMultiDesc[reg] == NULL);
3847 #endif // LEGACY_BACKEND
3848     }
3849 }
3850
3851 #else
3852
3853 // inline
3854 void RegSet::rsSpillChk()
3855 {
3856 }
3857
3858 #endif
3859
3860 /*****************************************************************************/
3861 #ifdef LEGACY_BACKEND
3862
3863 // inline
3864 bool RegTracker::rsIconIsInReg(ssize_t val, regNumber reg)
3865 {
3866     if (compiler->opts.MinOpts() || compiler->opts.compDbgCode)
3867     {
3868         return false;
3869     }
3870
3871     if (rsRegValues[reg].rvdKind == RV_INT_CNS && rsRegValues[reg].rvdIntCnsVal == val)
3872     {
3873         return true;
3874     }
3875     return false;
3876 }
3877
3878 #endif // LEGACY_BACKEND
3879 /*****************************************************************************/