src/jit/utils.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                                  Utils.cpp                                XX
   9 XX                                                                           XX
  10 XX   Has miscellaneous utility functions                                     XX
  11 XX                                                                           XX
  12 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  13 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  14 */
  15
  16 #include "jitpch.h"
  17 #ifdef _MSC_VER
  18 #pragma hdrstop
  19 #endif
  20
  21 #include "opcode.h"
  22
  23 /*****************************************************************************/
  24 // Define the string platform name based on compilation #ifdefs. This is the
  25 // same code for all platforms, hence it is here instead of in the targetXXX.cpp
  26 // files.
  27
  28 #ifdef _TARGET_UNIX_
  29 // Should we distinguish Mac? Can we?
  30 // Should we distinguish flavors of Unix? Can we?
  31 const char* Target::g_tgtPlatformName = "Unix";
  32 #else  // !_TARGET_UNIX_
  33 const char* Target::g_tgtPlatformName = "Windows";
  34 #endif // !_TARGET_UNIX_
  35
  36 /*****************************************************************************/
  37
  38 #define DECLARE_DATA
  39
  40 // clang-format off
  41 extern
  42 const signed char       opcodeSizes[] =
  43 {
  44     #define InlineNone_size           0
  45     #define ShortInlineVar_size       1
  46     #define InlineVar_size            2
  47     #define ShortInlineI_size         1
  48     #define InlineI_size              4
  49     #define InlineI8_size             8
  50     #define ShortInlineR_size         4
  51     #define InlineR_size              8
  52     #define ShortInlineBrTarget_size  1
  53     #define InlineBrTarget_size       4
  54     #define InlineMethod_size         4
  55     #define InlineField_size          4
  56     #define InlineType_size           4
  57     #define InlineString_size         4
  58     #define InlineSig_size            4
  59     #define InlineRVA_size            4
  60     #define InlineTok_size            4
  61     #define InlineSwitch_size         0       // for now
  62     #define InlinePhi_size            0       // for now
  63     #define InlineVarTok_size         0       // remove
  64
  65     #define OPDEF(name,string,pop,push,oprType,opcType,l,s1,s2,ctrl) oprType ## _size ,
  66     #include "opcode.def"
  67     #undef OPDEF
  68
  69     #undef InlineNone_size
  70     #undef ShortInlineVar_size
  71     #undef InlineVar_size
  72     #undef ShortInlineI_size
  73     #undef InlineI_size
  74     #undef InlineI8_size
  75     #undef ShortInlineR_size
  76     #undef InlineR_size
  77     #undef ShortInlineBrTarget_size
  78     #undef InlineBrTarget_size
  79     #undef InlineMethod_size
  80     #undef InlineField_size
  81     #undef InlineType_size
  82     #undef InlineString_size
  83     #undef InlineSig_size
  84     #undef InlineRVA_size
  85     #undef InlineTok_size
  86     #undef InlineSwitch_size
  87     #undef InlinePhi_size
  88 };
  89 // clang-format on
  90
  91 const BYTE varTypeClassification[] = {
  92 #define DEF_TP(tn, nm, jitType, verType, sz, sze, asze, st, al, tf, howUsed) tf,
  93 #include "typelist.h"
  94 #undef DEF_TP
  95 };
  96
  97 /*****************************************************************************/
  98 /*****************************************************************************/
  99 #ifdef DEBUG
 100 extern const char* const opcodeNames[] = {
 101 #define OPDEF(name, string, pop, push, oprType, opcType, l, s1, s2, ctrl) string,
 102 #include "opcode.def"
 103 #undef OPDEF
 104 };
 105
 106 extern const BYTE opcodeArgKinds[] = {
 107 #define OPDEF(name, string, pop, push, oprType, opcType, l, s1, s2, ctrl) (BYTE) oprType,
 108 #include "opcode.def"
 109 #undef OPDEF
 110 };
 111 #endif
 112
 113 /*****************************************************************************/
 114
 115 const char* varTypeName(var_types vt)
 116 {
 117     static const char* const varTypeNames[] = {
 118 #define DEF_TP(tn, nm, jitType, verType, sz, sze, asze, st, al, tf, howUsed) nm,
 119 #include "typelist.h"
 120 #undef DEF_TP
 121     };
 122
 123     assert((unsigned)vt < _countof(varTypeNames));
 124
 125     return varTypeNames[vt];
 126 }
 127
 128 #if defined(DEBUG) || defined(LATE_DISASM)
 129 /*****************************************************************************
 130  *
 131  *  Return the name of the given register.
 132  */
 133
 134 const char* getRegName(regNumber reg, bool isFloat)
 135 {
 136     // Special-case REG_NA; it's not in the regNames array, but we might want to print it.
 137     if (reg == REG_NA)
 138     {
 139         return "NA";
 140     }
 141 #if defined(_TARGET_X86_) && defined(LEGACY_BACKEND)
 142     static const char* const regNames[] = {
 143 #define REGDEF(name, rnum, mask, sname) sname,
 144 #include "register.h"
 145     };
 146
 147     static const char* const floatRegNames[] = {
 148 #define REGDEF(name, rnum, mask, sname) sname,
 149 #include "registerxmm.h"
 150     };
 151     if (isFloat)
 152     {
 153         assert(reg < ArrLen(floatRegNames));
 154         return floatRegNames[reg];
 155     }
 156     else
 157     {
 158         assert(reg < ArrLen(regNames));
 159         return regNames[reg];
 160     }
 161 #elif defined(_TARGET_ARM64_)
 162     static const char* const regNames[] = {
 163 #define REGDEF(name, rnum, mask, xname, wname) xname,
 164 #include "register.h"
 165     };
 166     assert(reg < ArrLen(regNames));
 167     return regNames[reg];
 168 #else
 169     static const char* const regNames[] = {
 170 #define REGDEF(name, rnum, mask, sname) sname,
 171 #include "register.h"
 172     };
 173     assert(reg < ArrLen(regNames));
 174     return regNames[reg];
 175 #endif
 176 }
 177
 178 const char* getRegName(unsigned reg,
 179                        bool     isFloat) // this is for gcencode.cpp and disasm.cpp that dont use the regNumber type
 180 {
 181     return getRegName((regNumber)reg, isFloat);
 182 }
 183 #endif // defined(DEBUG) || defined(LATE_DISASM)
 184
 185 #if defined(DEBUG)
 186
 187 const char* getRegNameFloat(regNumber reg, var_types type)
 188 {
 189 #ifdef _TARGET_ARM_
 190     assert(genIsValidFloatReg(reg));
 191     if (type == TYP_FLOAT)
 192         return getRegName(reg);
 193     else
 194     {
 195         const char* regName;
 196
 197         switch (reg)
 198         {
 199             default:
 200                 assert(!"Bad double register");
 201                 regName = "d??";
 202                 break;
 203             case REG_F0:
 204                 regName = "d0";
 205                 break;
 206             case REG_F2:
 207                 regName = "d2";
 208                 break;
 209             case REG_F4:
 210                 regName = "d4";
 211                 break;
 212             case REG_F6:
 213                 regName = "d6";
 214                 break;
 215             case REG_F8:
 216                 regName = "d8";
 217                 break;
 218             case REG_F10:
 219                 regName = "d10";
 220                 break;
 221             case REG_F12:
 222                 regName = "d12";
 223                 break;
 224             case REG_F14:
 225                 regName = "d14";
 226                 break;
 227             case REG_F16:
 228                 regName = "d16";
 229                 break;
 230             case REG_F18:
 231                 regName = "d18";
 232                 break;
 233             case REG_F20:
 234                 regName = "d20";
 235                 break;
 236             case REG_F22:
 237                 regName = "d22";
 238                 break;
 239             case REG_F24:
 240                 regName = "d24";
 241                 break;
 242             case REG_F26:
 243                 regName = "d26";
 244                 break;
 245             case REG_F28:
 246                 regName = "d28";
 247                 break;
 248             case REG_F30:
 249                 regName = "d30";
 250                 break;
 251         }
 252         return regName;
 253     }
 254
 255 #elif defined(_TARGET_X86_) && defined(LEGACY_BACKEND)
 256
 257     static const char* regNamesFloat[] = {
 258 #define REGDEF(name, rnum, mask, sname) sname,
 259 #include "registerxmm.h"
 260     };
 261     assert((unsigned)reg < ArrLen(regNamesFloat));
 262
 263     return regNamesFloat[reg];
 264
 265 #elif defined(_TARGET_ARM64_)
 266
 267     static const char* regNamesFloat[] = {
 268 #define REGDEF(name, rnum, mask, xname, wname) xname,
 269 #include "register.h"
 270     };
 271     assert((unsigned)reg < ArrLen(regNamesFloat));
 272
 273     return regNamesFloat[reg];
 274
 275 #else
 276     static const char* regNamesFloat[] = {
 277 #define REGDEF(name, rnum, mask, sname) "x" sname,
 278 #include "register.h"
 279     };
 280 #ifdef FEATURE_SIMD
 281     static const char* regNamesYMM[] = {
 282 #define REGDEF(name, rnum, mask, sname) "y" sname,
 283 #include "register.h"
 284     };
 285 #endif // FEATURE_SIMD
 286     assert((unsigned)reg < ArrLen(regNamesFloat));
 287
 288 #ifdef FEATURE_SIMD
 289     if (type == TYP_SIMD32)
 290     {
 291         return regNamesYMM[reg];
 292     }
 293 #endif // FEATURE_SIMD
 294
 295     return regNamesFloat[reg];
 296 #endif
 297 }
 298
 299 /*****************************************************************************
 300  *
 301  *  Displays a register set.
 302  *  TODO-ARM64-Cleanup: don't allow ip0, ip1 as part of a range.
 303  */
 304
 305 void dspRegMask(regMaskTP regMask, size_t minSiz)
 306 {
 307     const char* sep = "";
 308
 309     printf("[");
 310
 311     bool      inRegRange = false;
 312     regNumber regPrev    = REG_NA;
 313     regNumber regHead    = REG_NA; // When we start a range, remember the first register of the range, so we don't use
 314                                    // range notation if the range contains just a single register.
 315     for (regNumber regNum = REG_INT_FIRST; regNum <= REG_INT_LAST; regNum = REG_NEXT(regNum))
 316     {
 317         regMaskTP regBit = genRegMask(regNum);
 318
 319         if ((regMask & regBit) != 0)
 320         {
 321             // We have a register to display. It gets displayed now if:
 322             // 1. This is the first register to display of a new range of registers (possibly because
 323             //    no register has ever been displayed).
 324             // 2. This is the last register of an acceptable range (either the last integer register,
 325             //    or the last of a range that is displayed with range notation).
 326             if (!inRegRange)
 327             {
 328                 // It's the first register of a potential range.
 329                 const char* nam = getRegName(regNum);
 330                 printf("%s%s", sep, nam);
 331                 minSiz -= strlen(sep) + strlen(nam);
 332
 333                 // By default, we're not starting a potential register range.
 334                 sep = " ";
 335
 336                 // What kind of separator should we use for this range (if it is indeed going to be a range)?
 337                 CLANG_FORMAT_COMMENT_ANCHOR;
 338
 339 #if defined(_TARGET_AMD64_)
 340                 // For AMD64, create ranges for int registers R8 through R15, but not the "old" registers.
 341                 if (regNum >= REG_R8)
 342                 {
 343                     regHead    = regNum;
 344                     inRegRange = true;
 345                     sep        = "-";
 346                 }
 347 #elif defined(_TARGET_ARM64_)
 348                 // R17 and R28 can't be the start of a range, since the range would include TEB or FP
 349                 if ((regNum < REG_R17) || ((REG_R19 <= regNum) && (regNum < REG_R28)))
 350                 {
 351                     regHead    = regNum;
 352                     inRegRange = true;
 353                     sep        = "-";
 354                 }
 355 #elif defined(_TARGET_ARM_)
 356                 if (regNum < REG_R12)
 357                 {
 358                     regHead    = regNum;
 359                     inRegRange = true;
 360                     sep        = "-";
 361                 }
 362 #elif defined(_TARGET_X86_)
 363 // No register ranges
 364 #else // _TARGET_*
 365 #error Unsupported or unset target architecture
 366 #endif // _TARGET_*
 367             }
 368
 369 #if defined(_TARGET_ARM64_)
 370             // We've already printed a register. Is this the end of a range?
 371             else if ((regNum == REG_INT_LAST) || (regNum == REG_R17) // last register before TEB
 372                      || (regNum == REG_R28))                         // last register before FP
 373 #else                                                                // _TARGET_ARM64_
 374             // We've already printed a register. Is this the end of a range?
 375             else if (regNum == REG_INT_LAST)
 376 #endif                                                               // _TARGET_ARM64_
 377             {
 378                 const char* nam = getRegName(regNum);
 379                 printf("%s%s", sep, nam);
 380                 minSiz -= strlen(sep) + strlen(nam);
 381                 inRegRange = false; // No longer in the middle of a register range
 382                 regHead    = REG_NA;
 383                 sep        = " ";
 384             }
 385         }
 386         else // ((regMask & regBit) == 0)
 387         {
 388             if (inRegRange)
 389             {
 390                 assert(regHead != REG_NA);
 391                 if (regPrev != regHead)
 392                 {
 393                     // Close out the previous range, if it included more than one register.
 394                     const char* nam = getRegName(regPrev);
 395                     printf("%s%s", sep, nam);
 396                     minSiz -= strlen(sep) + strlen(nam);
 397                 }
 398                 sep        = " ";
 399                 inRegRange = false;
 400                 regHead    = REG_NA;
 401             }
 402         }
 403
 404         if (regBit > regMask)
 405         {
 406             break;
 407         }
 408
 409         regPrev = regNum;
 410     }
 411
 412 #if CPU_HAS_BYTE_REGS
 413     if (regMask & RBM_BYTE_REG_FLAG)
 414     {
 415         const char* nam = "BYTE";
 416         printf("%s%s", sep, nam);
 417         minSiz -= (strlen(sep) + strlen(nam));
 418     }
 419 #endif
 420
 421 #if !FEATURE_STACK_FP_X87
 422     if (strlen(sep) > 0)
 423     {
 424         // We've already printed something.
 425         sep = " ";
 426     }
 427     inRegRange = false;
 428     regPrev    = REG_NA;
 429     regHead    = REG_NA;
 430     for (regNumber regNum = REG_FP_FIRST; regNum <= REG_FP_LAST; regNum = REG_NEXT(regNum))
 431     {
 432         regMaskTP regBit = genRegMask(regNum);
 433
 434         if (regMask & regBit)
 435         {
 436             if (!inRegRange || (regNum == REG_FP_LAST))
 437             {
 438                 const char* nam = getRegName(regNum);
 439                 printf("%s%s", sep, nam);
 440                 minSiz -= strlen(sep) + strlen(nam);
 441                 sep     = "-";
 442                 regHead = regNum;
 443             }
 444             inRegRange = true;
 445         }
 446         else
 447         {
 448             if (inRegRange)
 449             {
 450                 if (regPrev != regHead)
 451                 {
 452                     const char* nam = getRegName(regPrev);
 453                     printf("%s%s", sep, nam);
 454                     minSiz -= (strlen(sep) + strlen(nam));
 455                 }
 456                 sep = " ";
 457             }
 458             inRegRange = false;
 459         }
 460
 461         if (regBit > regMask)
 462         {
 463             break;
 464         }
 465
 466         regPrev = regNum;
 467     }
 468 #endif
 469
 470     printf("]");
 471
 472     while ((int)minSiz > 0)
 473     {
 474         printf(" ");
 475         minSiz--;
 476     }
 477 }
 478
 479 //------------------------------------------------------------------------
 480 // dumpILBytes: Helper for dumpSingleInstr() to dump hex bytes of an IL stream,
 481 // aligning up to a minimum alignment width.
 482 //
 483 // Arguments:
 484 //    codeAddr  - Pointer to IL byte stream to display.
 485 //    codeSize  - Number of bytes of IL byte stream to display.
 486 //    alignSize - Pad out to this many characters, if fewer than this were written.
 487 //
 488 void dumpILBytes(const BYTE* const codeAddr,
 489                  unsigned          codeSize,
 490                  unsigned          alignSize) // number of characters to write, for alignment
 491 {
 492     for (IL_OFFSET offs = 0; offs < codeSize; ++offs)
 493     {
 494         printf(" %02x", *(codeAddr + offs));
 495     }
 496
 497     unsigned charsWritten = 3 * codeSize;
 498     for (unsigned i = charsWritten; i < alignSize; i++)
 499     {
 500         printf(" ");
 501     }
 502 }
 503
 504 //------------------------------------------------------------------------
 505 // dumpSingleInstr: Display a single IL instruction.
 506 //
 507 // Arguments:
 508 //    codeAddr  - Base pointer to a stream of IL instructions.
 509 //    offs      - Offset from codeAddr of the IL instruction to display.
 510 //    prefix    - Optional string to prefix the IL instruction with (if nullptr, no prefix is output).
 511 //
 512 // Return Value:
 513 //    Size of the displayed IL instruction in the instruction stream, in bytes. (Add this to 'offs' to
 514 //    get to the next instruction.)
 515 //
 516 unsigned dumpSingleInstr(const BYTE* const codeAddr, IL_OFFSET offs, const char* prefix)
 517 {
 518     const BYTE*    opcodePtr      = codeAddr + offs;
 519     const BYTE*    startOpcodePtr = opcodePtr;
 520     const unsigned ALIGN_WIDTH    = 3 * 6; // assume 3 characters * (1 byte opcode + 4 bytes data + 1 prefix byte) for
 521                                            // most things
 522
 523     if (prefix != nullptr)
 524     {
 525         printf("%s", prefix);
 526     }
 527
 528     OPCODE opcode = (OPCODE)getU1LittleEndian(opcodePtr);
 529     opcodePtr += sizeof(__int8);
 530
 531 DECODE_OPCODE:
 532
 533     if (opcode >= CEE_COUNT)
 534     {
 535         printf("\nIllegal opcode: %02X\n", (int)opcode);
 536         return (IL_OFFSET)(opcodePtr - startOpcodePtr);
 537     }
 538
 539     /* Get the size of additional parameters */
 540
 541     size_t   sz      = opcodeSizes[opcode];
 542     unsigned argKind = opcodeArgKinds[opcode];
 543
 544     /* See what kind of an opcode we have, then */
 545
 546     switch (opcode)
 547     {
 548         case CEE_PREFIX1:
 549             opcode = OPCODE(getU1LittleEndian(opcodePtr) + 256);
 550             opcodePtr += sizeof(__int8);
 551             goto DECODE_OPCODE;
 552
 553         default:
 554         {
 555             __int64 iOp;
 556             double  dOp;
 557             int     jOp;
 558             DWORD   jOp2;
 559
 560             switch (argKind)
 561             {
 562                 case InlineNone:
 563                     dumpILBytes(startOpcodePtr, (unsigned)(opcodePtr - startOpcodePtr), ALIGN_WIDTH);
 564                     printf(" %-12s", opcodeNames[opcode]);
 565                     break;
 566
 567                 case ShortInlineVar:
 568                     iOp = getU1LittleEndian(opcodePtr);
 569                     goto INT_OP;
 570                 case ShortInlineI:
 571                     iOp = getI1LittleEndian(opcodePtr);
 572                     goto INT_OP;
 573                 case InlineVar:
 574                     iOp = getU2LittleEndian(opcodePtr);
 575                     goto INT_OP;
 576                 case InlineTok:
 577                 case InlineMethod:
 578                 case InlineField:
 579                 case InlineType:
 580                 case InlineString:
 581                 case InlineSig:
 582                 case InlineI:
 583                     iOp = getI4LittleEndian(opcodePtr);
 584                     goto INT_OP;
 585                 case InlineI8:
 586                     iOp = getU4LittleEndian(opcodePtr);
 587                     iOp |= (__int64)getU4LittleEndian(opcodePtr + 4) << 32;
 588                     goto INT_OP;
 589
 590                 INT_OP:
 591                     dumpILBytes(startOpcodePtr, (unsigned)((opcodePtr - startOpcodePtr) + sz), ALIGN_WIDTH);
 592                     printf(" %-12s 0x%X", opcodeNames[opcode], iOp);
 593                     break;
 594
 595                 case ShortInlineR:
 596                     dOp = getR4LittleEndian(opcodePtr);
 597                     goto FLT_OP;
 598                 case InlineR:
 599                     dOp = getR8LittleEndian(opcodePtr);
 600                     goto FLT_OP;
 601
 602                 FLT_OP:
 603                     dumpILBytes(startOpcodePtr, (unsigned)((opcodePtr - startOpcodePtr) + sz), ALIGN_WIDTH);
 604                     printf(" %-12s %f", opcodeNames[opcode], dOp);
 605                     break;
 606
 607                 case ShortInlineBrTarget:
 608                     jOp = getI1LittleEndian(opcodePtr);
 609                     goto JMP_OP;
 610                 case InlineBrTarget:
 611                     jOp = getI4LittleEndian(opcodePtr);
 612                     goto JMP_OP;
 613
 614                 JMP_OP:
 615                     dumpILBytes(startOpcodePtr, (unsigned)((opcodePtr - startOpcodePtr) + sz), ALIGN_WIDTH);
 616                     printf(" %-12s %d (IL_%04x)", opcodeNames[opcode], jOp, (int)(opcodePtr + sz - codeAddr) + jOp);
 617                     break;
 618
 619                 case InlineSwitch:
 620                     jOp2 = getU4LittleEndian(opcodePtr);
 621                     opcodePtr += 4;
 622                     opcodePtr += jOp2 * 4; // Jump over the table
 623                     dumpILBytes(startOpcodePtr, (unsigned)(opcodePtr - startOpcodePtr), ALIGN_WIDTH);
 624                     printf(" %-12s", opcodeNames[opcode]);
 625                     break;
 626
 627                 case InlinePhi:
 628                     jOp2 = getU1LittleEndian(opcodePtr);
 629                     opcodePtr += 1;
 630                     opcodePtr += jOp2 * 2; // Jump over the table
 631                     dumpILBytes(startOpcodePtr, (unsigned)(opcodePtr - startOpcodePtr), ALIGN_WIDTH);
 632                     printf(" %-12s", opcodeNames[opcode]);
 633                     break;
 634
 635                 default:
 636                     assert(!"Bad argKind");
 637             }
 638
 639             opcodePtr += sz;
 640             break;
 641         }
 642     }
 643
 644     printf("\n");
 645     return (IL_OFFSET)(opcodePtr - startOpcodePtr);
 646 }
 647
 648 //------------------------------------------------------------------------
 649 // dumpILRange: Display a range of IL instructions from an IL instruction stream.
 650 //
 651 // Arguments:
 652 //    codeAddr  - Pointer to IL byte stream to display.
 653 //    codeSize  - Number of bytes of IL byte stream to display.
 654 //
 655 void dumpILRange(const BYTE* const codeAddr, unsigned codeSize) // in bytes
 656 {
 657     for (IL_OFFSET offs = 0; offs < codeSize;)
 658     {
 659         char prefix[100];
 660         sprintf_s(prefix, _countof(prefix), "IL_%04x ", offs);
 661         unsigned codeBytesDumped = dumpSingleInstr(codeAddr, offs, prefix);
 662         offs += codeBytesDumped;
 663     }
 664 }
 665
 666 /*****************************************************************************
 667  *
 668  *  Display a variable set.
 669  */
 670 const char* genES2str(BitVecTraits* traits, EXPSET_TP set)
 671 {
 672     const int   bufSize = 17;
 673     static char num1[bufSize];
 674
 675     static char num2[bufSize];
 676
 677     static char* nump = num1;
 678
 679     char* temp = nump;
 680
 681     nump = (nump == num1) ? num2 : num1;
 682
 683     sprintf_s(temp, bufSize, "%s", BitVecOps::ToString(traits, set));
 684
 685     return temp;
 686 }
 687
 688 const char* refCntWtd2str(unsigned refCntWtd)
 689 {
 690     const int   bufSize = 17;
 691     static char num1[bufSize];
 692
 693     static char num2[bufSize];
 694
 695     static char* nump = num1;
 696
 697     char* temp = nump;
 698
 699     nump = (nump == num1) ? num2 : num1;
 700
 701     if (refCntWtd == BB_MAX_WEIGHT)
 702     {
 703         sprintf_s(temp, bufSize, "MAX   ");
 704     }
 705     else
 706     {
 707         unsigned valueInt  = refCntWtd / BB_UNITY_WEIGHT;
 708         unsigned valueFrac = refCntWtd % BB_UNITY_WEIGHT;
 709
 710         if (valueFrac == 0)
 711         {
 712             sprintf_s(temp, bufSize, "%u   ", valueInt);
 713         }
 714         else
 715         {
 716             sprintf_s(temp, bufSize, "%u.%02u", valueInt, (valueFrac * 100 / BB_UNITY_WEIGHT));
 717         }
 718     }
 719     return temp;
 720 }
 721
 722 #endif // DEBUG
 723
 724 #if defined(DEBUG) || defined(INLINE_DATA)
 725
 726 //------------------------------------------------------------------------
 727 // Contains: check if the range includes a particular method
 728 //
 729 // Arguments:
 730 //    info   -- jit interface pointer
 731 //    method -- method handle for the method of interest
 732
 733 bool ConfigMethodRange::Contains(ICorJitInfo* info, CORINFO_METHOD_HANDLE method)
 734 {
 735     _ASSERT(m_inited == 1);
 736
 737     // No ranges specified means all methods included.
 738     if (m_lastRange == 0)
 739     {
 740         return true;
 741     }
 742
 743     // Check the hash. Note we can't use the cached hash here since
 744     // we may not be asking about the method currently being jitted.
 745     const unsigned hash = info->getMethodHash(method);
 746
 747     for (unsigned i = 0; i < m_lastRange; i++)
 748     {
 749         if ((m_ranges[i].m_low <= hash) && (hash <= m_ranges[i].m_high))
 750         {
 751             return true;
 752         }
 753     }
 754
 755     return false;
 756 }
 757
 758 //------------------------------------------------------------------------
 759 // InitRanges: parse the range string and set up the range info
 760 //
 761 // Arguments:
 762 //    rangeStr -- string to parse (may be nullptr)
 763 //    capacity -- number ranges to allocate in the range array
 764 //
 765 // Notes:
 766 //    Does some internal error checking; clients can use Error()
 767 //    to determine if the range string couldn't be fully parsed
 768 //    because of bad characters or too many entries, or had values
 769 //    that were too large to represent.
 770
 771 void ConfigMethodRange::InitRanges(const wchar_t* rangeStr, unsigned capacity)
 772 {
 773     // Make sure that the memory was zero initialized
 774     assert(m_inited == 0 || m_inited == 1);
 775     assert(m_entries == 0);
 776     assert(m_ranges == nullptr);
 777     assert(m_lastRange == 0);
 778
 779     // Flag any crazy-looking requests
 780     assert(capacity < 100000);
 781
 782     if (rangeStr == nullptr)
 783     {
 784         m_inited = 1;
 785         return;
 786     }
 787
 788     // Allocate some persistent memory
 789     ICorJitHost* jitHost = g_jitHost;
 790     m_ranges             = (Range*)jitHost->allocateMemory(capacity * sizeof(Range));
 791     m_entries            = capacity;
 792
 793     const wchar_t* p           = rangeStr;
 794     unsigned       lastRange   = 0;
 795     bool           setHighPart = false;
 796
 797     while ((*p != 0) && (lastRange < m_entries))
 798     {
 799         while (*p == L' ')
 800         {
 801             p++;
 802         }
 803
 804         int i = 0;
 805
 806         while (L'0' <= *p && *p <= L'9')
 807         {
 808             int j = 10 * i + ((*p++) - L'0');
 809
 810             // Check for overflow
 811             if ((m_badChar != 0) && (j <= i))
 812             {
 813                 m_badChar = (p - rangeStr) + 1;
 814             }
 815
 816             i = j;
 817         }
 818
 819         // Was this the high part of a low-high pair?
 820         if (setHighPart)
 821         {
 822             // Yep, set it and move to the next range
 823             m_ranges[lastRange].m_high = i;
 824
 825             // Sanity check that range is proper
 826             if ((m_badChar != 0) && (m_ranges[lastRange].m_high < m_ranges[lastRange].m_low))
 827             {
 828                 m_badChar = (p - rangeStr) + 1;
 829             }
 830
 831             lastRange++;
 832             setHighPart = false;
 833             continue;
 834         }
 835
 836         // Must have been looking for the low part of a range
 837         m_ranges[lastRange].m_low = i;
 838
 839         while (*p == L' ')
 840         {
 841             p++;
 842         }
 843
 844         // Was that the low part of a low-high pair?
 845         if (*p == L'-')
 846         {
 847             // Yep, skip the dash and set high part next time around.
 848             p++;
 849             setHighPart = true;
 850             continue;
 851         }
 852
 853         // Else we have a point range, so set high = low
 854         m_ranges[lastRange].m_high = i;
 855         lastRange++;
 856     }
 857
 858     // If we didn't parse the full range string, note index of the the
 859     // first bad char.
 860     if ((m_badChar != 0) && (*p != 0))
 861     {
 862         m_badChar = (p - rangeStr) + 1;
 863     }
 864
 865     // Finish off any remaining open range
 866     if (setHighPart)
 867     {
 868         m_ranges[lastRange].m_high = UINT_MAX;
 869         lastRange++;
 870     }
 871
 872     assert(lastRange <= m_entries);
 873     m_lastRange = lastRange;
 874     m_inited    = 1;
 875 }
 876
 877 #endif // defined(DEBUG) || defined(INLINE_DATA)
 878
 879 #if CALL_ARG_STATS || COUNT_BASIC_BLOCKS || COUNT_LOOPS || EMITTER_STATS || MEASURE_NODE_SIZE || MEASURE_MEM_ALLOC
 880
 881 /*****************************************************************************
 882  *  Histogram class.
 883  */
 884
 885 Histogram::Histogram(const unsigned* const sizeTable) : m_sizeTable(sizeTable)
 886 {
 887     unsigned sizeCount = 0;
 888     do
 889     {
 890         sizeCount++;
 891     } while ((sizeTable[sizeCount] != 0) && (sizeCount < 1000));
 892
 893     assert(sizeCount < HISTOGRAM_MAX_SIZE_COUNT - 1);
 894
 895     m_sizeCount = sizeCount;
 896
 897     memset(m_counts, 0, (m_sizeCount + 1) * sizeof(*m_counts));
 898 }
 899
 900 void Histogram::dump(FILE* output)
 901 {
 902     unsigned t = 0;
 903     for (unsigned i = 0; i < m_sizeCount; i++)
 904     {
 905         t += m_counts[i];
 906     }
 907
 908     for (unsigned c = 0, i = 0; i <= m_sizeCount; i++)
 909     {
 910         if (i == m_sizeCount)
 911         {
 912             if (m_counts[i] == 0)
 913             {
 914                 break;
 915             }
 916
 917             fprintf(output, "      >    %7u", m_sizeTable[i - 1]);
 918         }
 919         else
 920         {
 921             if (i == 0)
 922             {
 923                 fprintf(output, "     <=    ");
 924             }
 925             else
 926             {
 927                 fprintf(output, "%7u .. ", m_sizeTable[i - 1] + 1);
 928             }
 929
 930             fprintf(output, "%7u", m_sizeTable[i]);
 931         }
 932
 933         c += m_counts[i];
 934
 935         fprintf(output, " ===> %7u count (%3u%% of total)\n", m_counts[i], (int)(100.0 * c / t));
 936     }
 937 }
 938
 939 void Histogram::record(unsigned size)
 940 {
 941     unsigned i;
 942     for (i = 0; i < m_sizeCount; i++)
 943     {
 944         if (m_sizeTable[i] >= size)
 945         {
 946             break;
 947         }
 948     }
 949
 950     m_counts[i]++;
 951 }
 952
 953 #endif // CALL_ARG_STATS || COUNT_BASIC_BLOCKS || COUNT_LOOPS || EMITTER_STATS || MEASURE_NODE_SIZE
 954
 955 /*****************************************************************************
 956  * Fixed bit vector class
 957  */
 958
 959 // bitChunkSize() - Returns number of bits in a bitVect chunk
 960 inline UINT FixedBitVect::bitChunkSize()
 961 {
 962     return sizeof(UINT) * 8;
 963 }
 964
 965 // bitNumToBit() - Returns a bit mask of the given bit number
 966 inline UINT FixedBitVect::bitNumToBit(UINT bitNum)
 967 {
 968     assert(bitNum < bitChunkSize());
 969     assert(bitChunkSize() <= sizeof(int) * 8);
 970
 971     return 1 << bitNum;
 972 }
 973
 974 // bitVectInit() - Initializes a bit vector of a given size
 975 FixedBitVect* FixedBitVect::bitVectInit(UINT size, Compiler* comp)
 976 {
 977     UINT          bitVectMemSize, numberOfChunks;
 978     FixedBitVect* bv;
 979
 980     assert(size != 0);
 981
 982     numberOfChunks = (size - 1) / bitChunkSize() + 1;
 983     bitVectMemSize = numberOfChunks * (bitChunkSize() / 8); // size in bytes
 984
 985     assert(bitVectMemSize * bitChunkSize() >= size);
 986
 987     bv = (FixedBitVect*)comp->compGetMem(sizeof(FixedBitVect) + bitVectMemSize, CMK_FixedBitVect);
 988     memset(bv->bitVect, 0, bitVectMemSize);
 989
 990     bv->bitVectSize = size;
 991
 992     return bv;
 993 }
 994
 995 // bitVectSet() - Sets the given bit
 996 void FixedBitVect::bitVectSet(UINT bitNum)
 997 {
 998     UINT index;
 999
1000     assert(bitNum <= bitVectSize);
1001
1002     index = bitNum / bitChunkSize();
1003     bitNum -= index * bitChunkSize();
1004
1005     bitVect[index] |= bitNumToBit(bitNum);
1006 }
1007
1008 // bitVectTest() - Tests the given bit
1009 bool FixedBitVect::bitVectTest(UINT bitNum)
1010 {
1011     UINT index;
1012
1013     assert(bitNum <= bitVectSize);
1014
1015     index = bitNum / bitChunkSize();
1016     bitNum -= index * bitChunkSize();
1017
1018     return (bitVect[index] & bitNumToBit(bitNum)) != 0;
1019 }
1020
1021 // bitVectOr() - Or in the given bit vector
1022 void FixedBitVect::bitVectOr(FixedBitVect* bv)
1023 {
1024     UINT bitChunkCnt = (bitVectSize - 1) / bitChunkSize() + 1;
1025
1026     assert(bitVectSize == bv->bitVectSize);
1027
1028     // Or each chunks
1029     for (UINT i = 0; i < bitChunkCnt; i++)
1030     {
1031         bitVect[i] |= bv->bitVect[i];
1032     }
1033 }
1034
1035 // bitVectAnd() - And with passed in bit vector
1036 void FixedBitVect::bitVectAnd(FixedBitVect& bv)
1037 {
1038     UINT bitChunkCnt = (bitVectSize - 1) / bitChunkSize() + 1;
1039
1040     assert(bitVectSize == bv.bitVectSize);
1041
1042     // And each chunks
1043     for (UINT i = 0; i < bitChunkCnt; i++)
1044     {
1045         bitVect[i] &= bv.bitVect[i];
1046     }
1047 }
1048
1049 // bitVectGetFirst() - Find the first bit on and return bit num,
1050 //                    Return -1 if no bits found.
1051 UINT FixedBitVect::bitVectGetFirst()
1052 {
1053     return bitVectGetNext((UINT)-1);
1054 }
1055
1056 // bitVectGetNext() - Find the next bit on given previous position and return bit num.
1057 //                    Return -1 if no bits found.
1058 UINT FixedBitVect::bitVectGetNext(UINT bitNumPrev)
1059 {
1060     UINT bitNum = (UINT)-1;
1061     UINT index;
1062     UINT bitMask;
1063     UINT bitChunkCnt = (bitVectSize - 1) / bitChunkSize() + 1;
1064     UINT i;
1065
1066     if (bitNumPrev == (UINT)-1)
1067     {
1068         index   = 0;
1069         bitMask = (UINT)-1;
1070     }
1071     else
1072     {
1073         UINT bit;
1074
1075         index = bitNumPrev / bitChunkSize();
1076         bitNumPrev -= index * bitChunkSize();
1077         bit     = bitNumToBit(bitNumPrev);
1078         bitMask = ~(bit | (bit - 1));
1079     }
1080
1081     // Find first bit
1082     for (i = index; i < bitChunkCnt; i++)
1083     {
1084         UINT bitChunk = bitVect[i] & bitMask;
1085
1086         if (bitChunk != 0)
1087         {
1088             BitScanForward((ULONG*)&bitNum, bitChunk);
1089             break;
1090         }
1091
1092         bitMask = 0xFFFFFFFF;
1093     }
1094
1095     // Empty bit vector?
1096     if (bitNum == (UINT)-1)
1097     {
1098         return (UINT)-1;
1099     }
1100
1101     bitNum += i * bitChunkSize();
1102
1103     assert(bitNum <= bitVectSize);
1104
1105     return bitNum;
1106 }
1107
1108 // bitVectGetNextAndClear() - Find the first bit on, clear it and return it.
1109 //                            Return -1 if no bits found.
1110 UINT FixedBitVect::bitVectGetNextAndClear()
1111 {
1112     UINT bitNum      = (UINT)-1;
1113     UINT bitChunkCnt = (bitVectSize - 1) / bitChunkSize() + 1;
1114     UINT i;
1115
1116     // Find first bit
1117     for (i = 0; i < bitChunkCnt; i++)
1118     {
1119         if (bitVect[i] != 0)
1120         {
1121             BitScanForward((ULONG*)&bitNum, bitVect[i]);
1122             break;
1123         }
1124     }
1125
1126     // Empty bit vector?
1127     if (bitNum == (UINT)-1)
1128     {
1129         return (UINT)-1;
1130     }
1131
1132     // Clear the bit in the right chunk
1133     bitVect[i] &= ~bitNumToBit(bitNum);
1134
1135     bitNum += i * bitChunkSize();
1136
1137     assert(bitNum <= bitVectSize);
1138
1139     return bitNum;
1140 }
1141
1142 int SimpleSprintf_s(__in_ecount(cbBufSize - (pWriteStart - pBufStart)) char* pWriteStart,
1143                     __in_ecount(cbBufSize) char*                             pBufStart,
1144                     size_t                                                   cbBufSize,
1145                     __in_z const char*                                       fmt,
1146                     ...)
1147 {
1148     assert(fmt);
1149     assert(pBufStart);
1150     assert(pWriteStart);
1151     assert((size_t)pBufStart <= (size_t)pWriteStart);
1152     int ret;
1153
1154     // compute the space left in the buffer.
1155     if ((pBufStart + cbBufSize) < pWriteStart)
1156     {
1157         NO_WAY("pWriteStart is past end of buffer");
1158     }
1159     size_t  cbSpaceLeft = (size_t)((pBufStart + cbBufSize) - pWriteStart);
1160     va_list args;
1161     va_start(args, fmt);
1162     ret = vsprintf_s(pWriteStart, cbSpaceLeft, const_cast<char*>(fmt), args);
1163     va_end(args);
1164     if (ret < 0)
1165     {
1166         NO_WAY("vsprintf_s failed.");
1167     }
1168     return ret;
1169 }
1170
1171 #ifdef DEBUG
1172
1173 void hexDump(FILE* dmpf, const char* name, BYTE* addr, size_t size)
1174 {
1175     if (!size)
1176     {
1177         return;
1178     }
1179
1180     assert(addr);
1181
1182     fprintf(dmpf, "Hex dump of %s:\n", name);
1183
1184     for (unsigned i = 0; i < size; i++)
1185     {
1186         if ((i % 16) == 0)
1187         {
1188             fprintf(dmpf, "\n    %04X: ", i);
1189         }
1190
1191         fprintf(dmpf, "%02X ", *addr++);
1192     }
1193
1194     fprintf(dmpf, "\n\n");
1195 }
1196
1197 #endif // DEBUG
1198
1199 void HelperCallProperties::init()
1200 {
1201     for (CorInfoHelpFunc helper = CORINFO_HELP_UNDEF; // initialize helper
1202          (helper < CORINFO_HELP_COUNT);               // test helper for loop exit
1203          helper = CorInfoHelpFunc(int(helper) + 1))   // update helper to next
1204     {
1205         // Generally you want initialize these to their most typical/safest result
1206         //
1207         bool isPure        = false; // true if the result only depends upon input args and not any global state
1208         bool noThrow       = false; // true if the helper will never throw
1209         bool nonNullReturn = false; // true if the result will never be null or zero
1210         bool isAllocator   = false; // true if the result is usually a newly created heap item, or may throw OutOfMemory
1211         bool mutatesHeap   = false; // true if any previous heap objects [are|can be] modified
1212         bool mayRunCctor   = false; // true if the helper call may cause a static constructor to be run.
1213         bool mayFinalize   = false; // true if the helper call allocates an object that may need to run a finalizer
1214
1215         switch (helper)
1216         {
1217             // Arithmetic helpers that cannot throw
1218             case CORINFO_HELP_LLSH:
1219             case CORINFO_HELP_LRSH:
1220             case CORINFO_HELP_LRSZ:
1221             case CORINFO_HELP_LMUL:
1222             case CORINFO_HELP_LNG2DBL:
1223             case CORINFO_HELP_ULNG2DBL:
1224             case CORINFO_HELP_DBL2INT:
1225             case CORINFO_HELP_DBL2LNG:
1226             case CORINFO_HELP_DBL2UINT:
1227             case CORINFO_HELP_DBL2ULNG:
1228             case CORINFO_HELP_FLTREM:
1229             case CORINFO_HELP_DBLREM:
1230             case CORINFO_HELP_FLTROUND:
1231             case CORINFO_HELP_DBLROUND:
1232
1233                 isPure  = true;
1234                 noThrow = true;
1235                 break;
1236
1237             // Arithmetic helpers that *can* throw.
1238
1239             // This (or these) are not pure, in that they have "VM side effects"...but they don't mutate the heap.
1240             case CORINFO_HELP_ENDCATCH:
1241
1242                 noThrow = true;
1243                 break;
1244
1245             // Arithmetic helpers that may throw
1246             case CORINFO_HELP_LMOD: // Mods throw div-by zero, and signed mods have problems with the smallest integer
1247                                     // mod -1,
1248             case CORINFO_HELP_MOD:  // which is not representable as a positive integer.
1249             case CORINFO_HELP_UMOD:
1250             case CORINFO_HELP_ULMOD:
1251
1252             case CORINFO_HELP_UDIV: // Divs throw divide-by-zero.
1253             case CORINFO_HELP_DIV:
1254             case CORINFO_HELP_LDIV:
1255             case CORINFO_HELP_ULDIV:
1256
1257             case CORINFO_HELP_LMUL_OVF:
1258             case CORINFO_HELP_ULMUL_OVF:
1259             case CORINFO_HELP_DBL2INT_OVF:
1260             case CORINFO_HELP_DBL2LNG_OVF:
1261             case CORINFO_HELP_DBL2UINT_OVF:
1262             case CORINFO_HELP_DBL2ULNG_OVF:
1263
1264                 isPure = true;
1265                 break;
1266
1267             // Heap Allocation helpers, these all never return null
1268             case CORINFO_HELP_NEWSFAST:
1269             case CORINFO_HELP_NEWSFAST_ALIGN8:
1270
1271                 isAllocator   = true;
1272                 nonNullReturn = true;
1273                 noThrow       = true; // only can throw OutOfMemory
1274                 break;
1275
1276             case CORINFO_HELP_NEW_CROSSCONTEXT:
1277             case CORINFO_HELP_NEWFAST:
1278             case CORINFO_HELP_READYTORUN_NEW:
1279
1280                 mayFinalize   = true; // These may run a finalizer
1281                 isAllocator   = true;
1282                 nonNullReturn = true;
1283                 noThrow       = true; // only can throw OutOfMemory
1284                 break;
1285
1286             // These allocation helpers do some checks on the size (and lower bound) inputs,
1287             // and can throw exceptions other than OOM.
1288             case CORINFO_HELP_NEWARR_1_VC:
1289             case CORINFO_HELP_NEWARR_1_ALIGN8:
1290
1291                 isAllocator   = true;
1292                 nonNullReturn = true;
1293                 break;
1294
1295             // These allocation helpers do some checks on the size (and lower bound) inputs,
1296             // and can throw exceptions other than OOM.
1297             case CORINFO_HELP_NEW_MDARR:
1298             case CORINFO_HELP_NEWARR_1_DIRECT:
1299             case CORINFO_HELP_NEWARR_1_OBJ:
1300             case CORINFO_HELP_NEWARR_1_R2R_DIRECT:
1301             case CORINFO_HELP_READYTORUN_NEWARR_1:
1302
1303                 mayFinalize   = true; // These may run a finalizer
1304                 isAllocator   = true;
1305                 nonNullReturn = true;
1306                 break;
1307
1308             // Heap Allocation helpers that are also pure
1309             case CORINFO_HELP_STRCNS:
1310
1311                 isPure        = true;
1312                 isAllocator   = true;
1313                 nonNullReturn = true;
1314                 noThrow       = true; // only can throw OutOfMemory
1315                 break;
1316
1317             case CORINFO_HELP_BOX:
1318                 nonNullReturn = true;
1319                 isAllocator   = true;
1320                 noThrow       = true; // only can throw OutOfMemory
1321                 break;
1322
1323             case CORINFO_HELP_BOX_NULLABLE:
1324                 // Box Nullable is not a 'pure' function
1325                 // It has a Byref argument that it reads the contents of.
1326                 //
1327                 // So two calls to Box Nullable that pass the same address (with the same Value Number)
1328                 // will produce different results when the contents of the memory pointed to by the Byref changes
1329                 //
1330                 isAllocator = true;
1331                 noThrow     = true; // only can throw OutOfMemory
1332                 break;
1333
1334             case CORINFO_HELP_RUNTIMEHANDLE_METHOD:
1335             case CORINFO_HELP_RUNTIMEHANDLE_CLASS:
1336             case CORINFO_HELP_RUNTIMEHANDLE_METHOD_LOG:
1337             case CORINFO_HELP_RUNTIMEHANDLE_CLASS_LOG:
1338                 // logging helpers are not technically pure but can be optimized away
1339                 isPure        = true;
1340                 noThrow       = true;
1341                 nonNullReturn = true;
1342                 break;
1343
1344             // type casting helpers
1345             case CORINFO_HELP_ISINSTANCEOFINTERFACE:
1346             case CORINFO_HELP_ISINSTANCEOFARRAY:
1347             case CORINFO_HELP_ISINSTANCEOFCLASS:
1348             case CORINFO_HELP_ISINSTANCEOFANY:
1349             case CORINFO_HELP_READYTORUN_ISINSTANCEOF:
1350             case CORINFO_HELP_TYPEHANDLE_TO_RUNTIMETYPE:
1351
1352                 isPure  = true;
1353                 noThrow = true; // These return null for a failing cast
1354                 break;
1355
1356             // type casting helpers that throw
1357             case CORINFO_HELP_CHKCASTINTERFACE:
1358             case CORINFO_HELP_CHKCASTARRAY:
1359             case CORINFO_HELP_CHKCASTCLASS:
1360             case CORINFO_HELP_CHKCASTANY:
1361             case CORINFO_HELP_CHKCASTCLASS_SPECIAL:
1362             case CORINFO_HELP_READYTORUN_CHKCAST:
1363
1364                 // These throw for a failing cast
1365                 // But if given a null input arg will return null
1366                 isPure = true;
1367                 break;
1368
1369             // helpers returning addresses, these can also throw
1370             case CORINFO_HELP_UNBOX:
1371             case CORINFO_HELP_GETREFANY:
1372             case CORINFO_HELP_LDELEMA_REF:
1373
1374                 isPure = true;
1375                 break;
1376
1377             // helpers that return internal handle
1378             case CORINFO_HELP_GETCLASSFROMMETHODPARAM:
1379             case CORINFO_HELP_GETSYNCFROMCLASSHANDLE:
1380
1381                 isPure  = true;
1382                 noThrow = true;
1383                 break;
1384
1385             // Helpers that load the base address for static variables.
1386             // We divide these between those that may and may not invoke
1387             // static class constructors.
1388             case CORINFO_HELP_GETSHARED_GCSTATIC_BASE:
1389             case CORINFO_HELP_GETSHARED_NONGCSTATIC_BASE:
1390             case CORINFO_HELP_GETSHARED_GCSTATIC_BASE_DYNAMICCLASS:
1391             case CORINFO_HELP_GETSHARED_NONGCSTATIC_BASE_DYNAMICCLASS:
1392             case CORINFO_HELP_GETGENERICS_GCTHREADSTATIC_BASE:
1393             case CORINFO_HELP_GETGENERICS_NONGCTHREADSTATIC_BASE:
1394             case CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE:
1395             case CORINFO_HELP_GETSHARED_NONGCTHREADSTATIC_BASE:
1396             case CORINFO_HELP_CLASSINIT_SHARED_DYNAMICCLASS:
1397             case CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_DYNAMICCLASS:
1398             case CORINFO_HELP_GETSHARED_NONGCTHREADSTATIC_BASE_DYNAMICCLASS:
1399             case CORINFO_HELP_GETSTATICFIELDADDR_CONTEXT:
1400             case CORINFO_HELP_GETSTATICFIELDADDR_TLS:
1401             case CORINFO_HELP_GETGENERICS_GCSTATIC_BASE:
1402             case CORINFO_HELP_GETGENERICS_NONGCSTATIC_BASE:
1403             case CORINFO_HELP_READYTORUN_STATIC_BASE:
1404             case CORINFO_HELP_READYTORUN_GENERIC_STATIC_BASE:
1405
1406                 // These may invoke static class constructors
1407                 // These can throw InvalidProgram exception if the class can not be constructed
1408                 //
1409                 isPure        = true;
1410                 nonNullReturn = true;
1411                 mayRunCctor   = true;
1412                 break;
1413
1414             case CORINFO_HELP_GETSHARED_GCSTATIC_BASE_NOCTOR:
1415             case CORINFO_HELP_GETSHARED_NONGCSTATIC_BASE_NOCTOR:
1416             case CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_NOCTOR:
1417             case CORINFO_HELP_GETSHARED_NONGCTHREADSTATIC_BASE_NOCTOR:
1418
1419                 // These do not invoke static class constructors
1420                 //
1421                 isPure        = true;
1422                 noThrow       = true;
1423                 nonNullReturn = true;
1424                 break;
1425
1426             // GC Write barrier support
1427             // TODO-ARM64-Bug?: Can these throw or not?
1428             case CORINFO_HELP_ASSIGN_REF:
1429             case CORINFO_HELP_CHECKED_ASSIGN_REF:
1430             case CORINFO_HELP_ASSIGN_REF_ENSURE_NONHEAP:
1431             case CORINFO_HELP_ASSIGN_BYREF:
1432             case CORINFO_HELP_ASSIGN_STRUCT:
1433
1434                 mutatesHeap = true;
1435                 break;
1436
1437             // Accessing fields (write)
1438             case CORINFO_HELP_SETFIELD32:
1439             case CORINFO_HELP_SETFIELD64:
1440             case CORINFO_HELP_SETFIELDOBJ:
1441             case CORINFO_HELP_SETFIELDSTRUCT:
1442             case CORINFO_HELP_SETFIELDFLOAT:
1443             case CORINFO_HELP_SETFIELDDOUBLE:
1444             case CORINFO_HELP_ARRADDR_ST:
1445
1446                 mutatesHeap = true;
1447                 break;
1448
1449             // These helper calls always throw an exception
1450             case CORINFO_HELP_OVERFLOW:
1451             case CORINFO_HELP_VERIFICATION:
1452             case CORINFO_HELP_RNGCHKFAIL:
1453             case CORINFO_HELP_THROWDIVZERO:
1454             case CORINFO_HELP_THROWNULLREF:
1455             case CORINFO_HELP_THROW:
1456             case CORINFO_HELP_RETHROW:
1457             case CORINFO_HELP_THROW_ARGUMENTEXCEPTION:
1458             case CORINFO_HELP_THROW_ARGUMENTOUTOFRANGEEXCEPTION:
1459             case CORINFO_HELP_THROW_PLATFORM_NOT_SUPPORTED:
1460             case CORINFO_HELP_THROW_TYPE_NOT_SUPPORTED:
1461
1462                 break;
1463
1464             // These helper calls may throw an exception
1465             case CORINFO_HELP_METHOD_ACCESS_CHECK:
1466             case CORINFO_HELP_FIELD_ACCESS_CHECK:
1467             case CORINFO_HELP_CLASS_ACCESS_CHECK:
1468             case CORINFO_HELP_DELEGATE_SECURITY_CHECK:
1469             case CORINFO_HELP_MON_EXIT_STATIC:
1470
1471                 break;
1472
1473             // This is a debugging aid; it simply returns a constant address.
1474             case CORINFO_HELP_LOOP_CLONE_CHOICE_ADDR:
1475                 isPure  = true;
1476                 noThrow = true;
1477                 break;
1478
1479             case CORINFO_HELP_DBG_IS_JUST_MY_CODE:
1480             case CORINFO_HELP_BBT_FCN_ENTER:
1481             case CORINFO_HELP_POLL_GC:
1482             case CORINFO_HELP_MON_ENTER:
1483             case CORINFO_HELP_MON_EXIT:
1484             case CORINFO_HELP_MON_ENTER_STATIC:
1485             case CORINFO_HELP_JIT_REVERSE_PINVOKE_ENTER:
1486             case CORINFO_HELP_JIT_REVERSE_PINVOKE_EXIT:
1487             case CORINFO_HELP_SECURITY_PROLOG:
1488             case CORINFO_HELP_SECURITY_PROLOG_FRAMED:
1489             case CORINFO_HELP_VERIFICATION_RUNTIME_CHECK:
1490             case CORINFO_HELP_GETFIELDADDR:
1491             case CORINFO_HELP_INIT_PINVOKE_FRAME:
1492             case CORINFO_HELP_JIT_PINVOKE_BEGIN:
1493             case CORINFO_HELP_JIT_PINVOKE_END:
1494             case CORINFO_HELP_GETCURRENTMANAGEDTHREADID:
1495
1496                 noThrow = true;
1497                 break;
1498
1499             // Not sure how to handle optimization involving the rest of these  helpers
1500             default:
1501
1502                 // The most pessimistic results are returned for these helpers
1503                 mutatesHeap = true;
1504                 break;
1505         }
1506
1507         m_isPure[helper]        = isPure;
1508         m_noThrow[helper]       = noThrow;
1509         m_nonNullReturn[helper] = nonNullReturn;
1510         m_isAllocator[helper]   = isAllocator;
1511         m_mutatesHeap[helper]   = mutatesHeap;
1512         m_mayRunCctor[helper]   = mayRunCctor;
1513         m_mayFinalize[helper]   = mayFinalize;
1514     }
1515 }
1516
1517 //=============================================================================
1518 // AssemblyNamesList2
1519 //=============================================================================
1520 // The string should be of the form
1521 // MyAssembly
1522 // MyAssembly;mscorlib;System
1523 // MyAssembly;mscorlib System
1524
1525 AssemblyNamesList2::AssemblyNamesList2(const wchar_t* list, HostAllocator* alloc) : m_alloc(alloc)
1526 {
1527     assert(m_alloc != nullptr);
1528
1529     WCHAR          prevChar   = '?';     // dummy
1530     LPWSTR         nameStart  = nullptr; // start of the name currently being processed. nullptr if no current name
1531     AssemblyName** ppPrevLink = &m_pNames;
1532
1533     for (LPWSTR listWalk = const_cast<LPWSTR>(list); prevChar != '\0'; prevChar = *listWalk, listWalk++)
1534     {
1535         WCHAR curChar = *listWalk;
1536
1537         if (iswspace(curChar) || curChar == W(';') || curChar == W('\0'))
1538         {
1539             //
1540             // Found white-space
1541             //
1542
1543             if (nameStart)
1544             {
1545                 // Found the end of the current name; add a new assembly name to the list.
1546
1547                 AssemblyName* newName = new (m_alloc) AssemblyName();
1548
1549                 // Null out the current character so we can do zero-terminated string work; we'll restore it later.
1550                 *listWalk = W('\0');
1551
1552                 // How much space do we need?
1553                 int convertedNameLenBytes =
1554                     WszWideCharToMultiByte(CP_UTF8, 0, nameStart, -1, nullptr, 0, nullptr, nullptr);
1555                 newName->m_assemblyName = new (m_alloc) char[convertedNameLenBytes]; // convertedNameLenBytes includes
1556                                                                                      // the trailing null character
1557                 if (WszWideCharToMultiByte(CP_UTF8, 0, nameStart, -1, newName->m_assemblyName, convertedNameLenBytes,
1558                                            nullptr, nullptr) != 0)
1559                 {
1560                     *ppPrevLink = newName;
1561                     ppPrevLink  = &newName->m_next;
1562                 }
1563                 else
1564                 {
1565                     // Failed to convert the string. Ignore this string (and leak the memory).
1566                 }
1567
1568                 nameStart = nullptr;
1569
1570                 // Restore the current character.
1571                 *listWalk = curChar;
1572             }
1573         }
1574         else if (!nameStart)
1575         {
1576             //
1577             // Found the start of a new name
1578             //
1579
1580             nameStart = listWalk;
1581         }
1582     }
1583
1584     assert(nameStart == nullptr); // cannot be in the middle of a name
1585     *ppPrevLink = nullptr;        // Terminate the last element of the list.
1586 }
1587
1588 AssemblyNamesList2::~AssemblyNamesList2()
1589 {
1590     for (AssemblyName* pName = m_pNames; pName != nullptr; /**/)
1591     {
1592         AssemblyName* cur = pName;
1593         pName             = pName->m_next;
1594
1595         m_alloc->Free(cur->m_assemblyName);
1596         m_alloc->Free(cur);
1597     }
1598 }
1599
1600 bool AssemblyNamesList2::IsInList(const char* assemblyName)
1601 {
1602     for (AssemblyName* pName = m_pNames; pName != nullptr; pName = pName->m_next)
1603     {
1604         if (_stricmp(pName->m_assemblyName, assemblyName) == 0)
1605         {
1606             return true;
1607         }
1608     }
1609
1610     return false;
1611 }
1612
1613 #ifdef FEATURE_JIT_METHOD_PERF
1614 CycleCount::CycleCount() : cps(CycleTimer::CyclesPerSecond())
1615 {
1616 }
1617
1618 bool CycleCount::GetCycles(unsigned __int64* time)
1619 {
1620     return CycleTimer::GetThreadCyclesS(time);
1621 }
1622
1623 bool CycleCount::Start()
1624 {
1625     return GetCycles(&beginCycles);
1626 }
1627
1628 double CycleCount::ElapsedTime()
1629 {
1630     unsigned __int64 nowCycles;
1631     (void)GetCycles(&nowCycles);
1632     return ((double)(nowCycles - beginCycles) / cps) * 1000.0;
1633 }
1634
1635 bool PerfCounter::Start()
1636 {
1637     bool result = QueryPerformanceFrequency(&beg) != 0;
1638     if (!result)
1639     {
1640         return result;
1641     }
1642     freq = (double)beg.QuadPart / 1000.0;
1643     (void)QueryPerformanceCounter(&beg);
1644     return result;
1645 }
1646
1647 // Return elapsed time from Start() in millis.
1648 double PerfCounter::ElapsedTime()
1649 {
1650     LARGE_INTEGER li;
1651     (void)QueryPerformanceCounter(&li);
1652     return (double)(li.QuadPart - beg.QuadPart) / freq;
1653 }
1654
1655 #endif
1656
1657 #ifdef DEBUG
1658
1659 /*****************************************************************************
1660  * Return the number of digits in a number of the given base (default base 10).
1661  * Used when outputting strings.
1662  */
1663 unsigned CountDigits(unsigned num, unsigned base /* = 10 */)
1664 {
1665     assert(2 <= base && base <= 16); // sanity check
1666     unsigned count = 1;
1667     while (num >= base)
1668     {
1669         num /= base;
1670         ++count;
1671     }
1672     return count;
1673 }
1674
1675 #endif // DEBUG
1676
1677 double FloatingPointUtils::convertUInt64ToDouble(unsigned __int64 uIntVal)
1678 {
1679     __int64 s64 = uIntVal;
1680     double  d;
1681     if (s64 < 0)
1682     {
1683 #if defined(_TARGET_XARCH_)
1684         // RyuJIT codegen and clang (or gcc) may produce different results for casting uint64 to
1685         // double, and the clang result is more accurate. For example,
1686         //    1) (double)0x84595161401484A0UL --> 43e08b2a2c280290  (RyuJIT codegen or VC++)
1687         //    2) (double)0x84595161401484A0UL --> 43e08b2a2c280291  (clang or gcc)
1688         // If the folding optimization below is implemented by simple casting of (double)uint64_val
1689         // and it is compiled by clang, casting result can be inconsistent, depending on whether
1690         // the folding optimization is triggered or the codegen generates instructions for casting. //
1691         // The current solution is to force the same math as the codegen does, so that casting
1692         // result is always consistent.
1693
1694         // d = (double)(int64_t)uint64 + 0x1p64
1695         uint64_t adjHex = 0x43F0000000000000UL;
1696         d               = (double)s64 + *(double*)&adjHex;
1697 #else
1698         d                             = (double)uIntVal;
1699 #endif
1700     }
1701     else
1702     {
1703         d = (double)uIntVal;
1704     }
1705     return d;
1706 }
1707
1708 float FloatingPointUtils::convertUInt64ToFloat(unsigned __int64 u64)
1709 {
1710     double d = convertUInt64ToDouble(u64);
1711     return (float)d;
1712 }
1713
1714 unsigned __int64 FloatingPointUtils::convertDoubleToUInt64(double d)
1715 {
1716     unsigned __int64 u64;
1717     if (d >= 0.0)
1718     {
1719         // Work around a C++ issue where it doesn't properly convert large positive doubles
1720         const double two63 = 2147483648.0 * 4294967296.0;
1721         if (d < two63)
1722         {
1723             u64 = UINT64(d);
1724         }
1725         else
1726         {
1727             // subtract 0x8000000000000000, do the convert then add it back again
1728             u64 = INT64(d - two63) + I64(0x8000000000000000);
1729         }
1730         return u64;
1731     }
1732
1733 #ifdef _TARGET_XARCH_
1734
1735     // While the Ecma spec does not specifically call this out,
1736     // the case of conversion from negative double to unsigned integer is
1737     // effectively an overflow and therefore the result is unspecified.
1738     // With MSVC for x86/x64, such a conversion results in the bit-equivalent
1739     // unsigned value of the conversion to integer. Other compilers convert
1740     // negative doubles to zero when the target is unsigned.
1741     // To make the behavior consistent across OS's on TARGET_XARCH,
1742     // this double cast is needed to conform MSVC behavior.
1743
1744     u64 = UINT64(INT64(d));
1745 #else
1746     u64                               = UINT64(d);
1747 #endif // _TARGET_XARCH_
1748
1749     return u64;
1750 }
1751
1752 // Rounds a double-precision floating-point value to the nearest integer,
1753 // and rounds midpoint values to the nearest even number.
1754 double FloatingPointUtils::round(double x)
1755 {
1756     // ************************************************************************************
1757     // IMPORTANT: Do not change this implementation without also updating Math.Round(double),
1758     //            MathF.Round(float), and FloatingPointUtils::round(float)
1759     // ************************************************************************************
1760
1761     // If the number has no fractional part do nothing
1762     // This shortcut is necessary to workaround precision loss in borderline cases on some platforms
1763
1764     if (x == (double)((INT64)x))
1765     {
1766         return x;
1767     }
1768
1769     // We had a number that was equally close to 2 integers.
1770     // We need to return the even one.
1771
1772     double flrTempVal = floor(x + 0.5);
1773
1774     if ((x == (floor(x) + 0.5)) && (fmod(flrTempVal, 2.0) != 0))
1775     {
1776         flrTempVal -= 1.0;
1777     }
1778
1779     return _copysign(flrTempVal, x);
1780 }
1781
1782 // Windows x86 and Windows ARM/ARM64 may not define _copysignf() but they do define _copysign().
1783 // We will redirect the macro to this other functions if the macro is not defined for the platform.
1784 // This has the side effect of a possible implicit upcasting for arguments passed in and an explicit
1785 // downcasting for the _copysign() call.
1786 #if (defined(_TARGET_X86_) || defined(_TARGET_ARM_) || defined(_TARGET_ARM64_)) && !defined(FEATURE_PAL)
1787
1788 #if !defined(_copysignf)
1789 #define _copysignf (float)_copysign
1790 #endif
1791
1792 #endif
1793
1794 // Rounds a single-precision floating-point value to the nearest integer,
1795 // and rounds midpoint values to the nearest even number.
1796 float FloatingPointUtils::round(float x)
1797 {
1798     // ************************************************************************************
1799     // IMPORTANT: Do not change this implementation without also updating MathF.Round(float),
1800     //            Math.Round(double), and FloatingPointUtils::round(double)
1801     // ************************************************************************************
1802
1803     // If the number has no fractional part do nothing
1804     // This shortcut is necessary to workaround precision loss in borderline cases on some platforms
1805
1806     if (x == (float)((INT32)x))
1807     {
1808         return x;
1809     }
1810
1811     // We had a number that was equally close to 2 integers.
1812     // We need to return the even one.
1813
1814     float flrTempVal = floorf(x + 0.5f);
1815
1816     if ((x == (floorf(x) + 0.5f)) && (fmodf(flrTempVal, 2.0f) != 0))
1817     {
1818         flrTempVal -= 1.0f;
1819     }
1820
1821     return _copysignf(flrTempVal, x);
1822 }
1823
1824 namespace MagicDivide
1825 {
1826 template <int TableBase = 0, int TableSize, typename Magic>
1827 static const Magic* TryGetMagic(const Magic (&table)[TableSize], typename Magic::DivisorType index)
1828 {
1829     if ((index < TableBase) || (TableBase + TableSize <= index))
1830     {
1831         return nullptr;
1832     }
1833
1834     const Magic* p = &table[index - TableBase];
1835
1836     if (p->magic == 0)
1837     {
1838         return nullptr;
1839     }
1840
1841     return p;
1842 };
1843
1844 template <typename T>
1845 struct UnsignedMagic
1846 {
1847     typedef T DivisorType;
1848
1849     T    magic;
1850     bool add;
1851     int  shift;
1852 };
1853
1854 template <typename T>
1855 const UnsignedMagic<T>* TryGetUnsignedMagic(T divisor)
1856 {
1857     return nullptr;
1858 }
1859
1860 template <>
1861 const UnsignedMagic<uint32_t>* TryGetUnsignedMagic(uint32_t divisor)
1862 {
1863     static const UnsignedMagic<uint32_t> table[]{
1864         {0xaaaaaaab, false, 1}, // 3
1865         {},
1866         {0xcccccccd, false, 2}, // 5
1867         {0xaaaaaaab, false, 2}, // 6
1868         {0x24924925, true, 3},  // 7
1869         {},
1870         {0x38e38e39, false, 1}, // 9
1871         {0xcccccccd, false, 3}, // 10
1872         {0xba2e8ba3, false, 3}, // 11
1873         {0xaaaaaaab, false, 3}, // 12
1874     };
1875
1876     return TryGetMagic<3>(table, divisor);
1877 }
1878
1879 template <>
1880 const UnsignedMagic<uint64_t>* TryGetUnsignedMagic(uint64_t divisor)
1881 {
1882     static const UnsignedMagic<uint64_t> table[]{
1883         {0xaaaaaaaaaaaaaaab, false, 1}, // 3
1884         {},
1885         {0xcccccccccccccccd, false, 2}, // 5
1886         {0xaaaaaaaaaaaaaaab, false, 2}, // 6
1887         {0x2492492492492493, true, 3},  // 7
1888         {},
1889         {0xe38e38e38e38e38f, false, 3}, // 9
1890         {0xcccccccccccccccd, false, 3}, // 10
1891         {0x2e8ba2e8ba2e8ba3, false, 1}, // 11
1892         {0xaaaaaaaaaaaaaaab, false, 3}, // 12
1893     };
1894
1895     return TryGetMagic<3>(table, divisor);
1896 }
1897
1898 //------------------------------------------------------------------------
1899 // GetUnsignedMagic: Generates a magic number and shift amount for the magic
1900 // number unsigned division optimization.
1901 //
1902 // Arguments:
1903 //    d     - The divisor
1904 //    add   - Pointer to a flag indicating the kind of code to generate
1905 //    shift - Pointer to the shift value to be returned
1906 //
1907 // Returns:
1908 //    The magic number.
1909 //
1910 // Notes:
1911 //    This code is adapted from _The_PowerPC_Compiler_Writer's_Guide_, pages 57-58.
1912 //    The paper is based on "Division by invariant integers using multiplication"
1913 //    by Torbjorn Granlund and Peter L. Montgomery in PLDI 94
1914
1915 template <typename T>
1916 T GetUnsignedMagic(T d, bool* add /*out*/, int* shift /*out*/)
1917 {
1918     assert((d >= 3) && !isPow2(d));
1919
1920     const UnsignedMagic<T>* magic = TryGetUnsignedMagic(d);
1921
1922     if (magic != nullptr)
1923     {
1924         *shift = magic->shift;
1925         *add   = magic->add;
1926         return magic->magic;
1927     }
1928
1929     typedef typename jitstd::make_signed<T>::type ST;
1930
1931     const unsigned bits       = sizeof(T) * 8;
1932     const unsigned bitsMinus1 = bits - 1;
1933     const T        twoNMinus1 = T(1) << bitsMinus1;
1934
1935     *add        = false;
1936     const T  nc = -ST(1) - -ST(d) % ST(d);
1937     unsigned p  = bitsMinus1;
1938     T        q1 = twoNMinus1 / nc;
1939     T        r1 = twoNMinus1 - (q1 * nc);
1940     T        q2 = (twoNMinus1 - 1) / d;
1941     T        r2 = (twoNMinus1 - 1) - (q2 * d);
1942     T        delta;
1943
1944     do
1945     {
1946         p++;
1947
1948         if (r1 >= (nc - r1))
1949         {
1950             q1 = 2 * q1 + 1;
1951             r1 = 2 * r1 - nc;
1952         }
1953         else
1954         {
1955             q1 = 2 * q1;
1956             r1 = 2 * r1;
1957         }
1958
1959         if ((r2 + 1) >= (d - r2))
1960         {
1961             if (q2 >= (twoNMinus1 - 1))
1962             {
1963                 *add = true;
1964             }
1965
1966             q2 = 2 * q2 + 1;
1967             r2 = 2 * r2 + 1 - d;
1968         }
1969         else
1970         {
1971             if (q2 >= twoNMinus1)
1972             {
1973                 *add = true;
1974             }
1975
1976             q2 = 2 * q2;
1977             r2 = 2 * r2 + 1;
1978         }
1979
1980         delta = d - 1 - r2;
1981
1982     } while ((p < (bits * 2)) && ((q1 < delta) || ((q1 == delta) && (r1 == 0))));
1983
1984     *shift = p - bits; // resulting shift
1985     return q2 + 1;     // resulting magic number
1986 }
1987
1988 uint32_t GetUnsigned32Magic(uint32_t d, bool* add /*out*/, int* shift /*out*/)
1989 {
1990     return GetUnsignedMagic<uint32_t>(d, add, shift);
1991 }
1992
1993 #ifdef _TARGET_64BIT_
1994 uint64_t GetUnsigned64Magic(uint64_t d, bool* add /*out*/, int* shift /*out*/)
1995 {
1996     return GetUnsignedMagic<uint64_t>(d, add, shift);
1997 }
1998 #endif
1999
2000 template <typename T>
2001 struct SignedMagic
2002 {
2003     typedef T DivisorType;
2004
2005     T   magic;
2006     int shift;
2007 };
2008
2009 template <typename T>
2010 const SignedMagic<T>* TryGetSignedMagic(T divisor)
2011 {
2012     return nullptr;
2013 }
2014
2015 template <>
2016 const SignedMagic<int32_t>* TryGetSignedMagic(int32_t divisor)
2017 {
2018     static const SignedMagic<int32_t> table[]{
2019         {0x55555556, 0}, // 3
2020         {},
2021         {0x66666667, 1}, // 5
2022         {0x2aaaaaab, 0}, // 6
2023         {0x92492493, 2}, // 7
2024         {},
2025         {0x38e38e39, 1}, // 9
2026         {0x66666667, 2}, // 10
2027         {0x2e8ba2e9, 1}, // 11
2028         {0x2aaaaaab, 1}, // 12
2029     };
2030
2031     return TryGetMagic<3>(table, divisor);
2032 }
2033
2034 template <>
2035 const SignedMagic<int64_t>* TryGetSignedMagic(int64_t divisor)
2036 {
2037     static const SignedMagic<int64_t> table[]{
2038         {0x5555555555555556, 0}, // 3
2039         {},
2040         {0x6666666666666667, 1}, // 5
2041         {0x2aaaaaaaaaaaaaab, 0}, // 6
2042         {0x4924924924924925, 1}, // 7
2043         {},
2044         {0x1c71c71c71c71c72, 0}, // 9
2045         {0x6666666666666667, 2}, // 10
2046         {0x2e8ba2e8ba2e8ba3, 1}, // 11
2047         {0x2aaaaaaaaaaaaaab, 1}, // 12
2048     };
2049
2050     return TryGetMagic<3>(table, divisor);
2051 }
2052
2053 //------------------------------------------------------------------------
2054 // GetSignedMagic: Generates a magic number and shift amount for
2055 // the magic number division optimization.
2056 //
2057 // Arguments:
2058 //    denom - The denominator
2059 //    shift - Pointer to the shift value to be returned
2060 //
2061 // Returns:
2062 //    The magic number.
2063 //
2064 // Notes:
2065 //    This code is previously from UTC where it notes it was taken from
2066 //   _The_PowerPC_Compiler_Writer's_Guide_, pages 57-58. The paper is is based on
2067 //   is "Division by invariant integers using multiplication" by Torbjorn Granlund
2068 //   and Peter L. Montgomery in PLDI 94
2069
2070 template <typename T>
2071 T GetSignedMagic(T denom, int* shift /*out*/)
2072 {
2073     const SignedMagic<T>* magic = TryGetSignedMagic(denom);
2074
2075     if (magic != nullptr)
2076     {
2077         *shift = magic->shift;
2078         return magic->magic;
2079     }
2080
2081     const int bits         = sizeof(T) * 8;
2082     const int bits_minus_1 = bits - 1;
2083
2084     typedef typename jitstd::make_unsigned<T>::type UT;
2085
2086     const UT two_nminus1 = UT(1) << bits_minus_1;
2087
2088     int p;
2089     UT  absDenom;
2090     UT  absNc;
2091     UT  delta;
2092     UT  q1;
2093     UT  r1;
2094     UT  r2;
2095     UT  q2;
2096     UT  t;
2097     T   result_magic;
2098     int iters = 0;
2099
2100     absDenom = abs(denom);
2101     t        = two_nminus1 + ((unsigned int)denom >> 31);
2102     absNc    = t - 1 - (t % absDenom);        // absolute value of nc
2103     p        = bits_minus_1;                  // initialize p
2104     q1       = two_nminus1 / absNc;           // initialize q1 = 2^p / abs(nc)
2105     r1       = two_nminus1 - (q1 * absNc);    // initialize r1 = rem(2^p, abs(nc))
2106     q2       = two_nminus1 / absDenom;        // initialize q1 = 2^p / abs(denom)
2107     r2       = two_nminus1 - (q2 * absDenom); // initialize r1 = rem(2^p, abs(denom))
2108
2109     do
2110     {
2111         iters++;
2112         p++;
2113         q1 *= 2; // update q1 = 2^p / abs(nc)
2114         r1 *= 2; // update r1 = rem(2^p / abs(nc))
2115
2116         if (r1 >= absNc)
2117         { // must be unsigned comparison
2118             q1++;
2119             r1 -= absNc;
2120         }
2121
2122         q2 *= 2; // update q2 = 2^p / abs(denom)
2123         r2 *= 2; // update r2 = rem(2^p / abs(denom))
2124
2125         if (r2 >= absDenom)
2126         { // must be unsigned comparison
2127             q2++;
2128             r2 -= absDenom;
2129         }
2130
2131         delta = absDenom - r2;
2132     } while (q1 < delta || (q1 == delta && r1 == 0));
2133
2134     result_magic = q2 + 1; // resulting magic number
2135     if (denom < 0)
2136     {
2137         result_magic = -result_magic;
2138     }
2139     *shift = p - bits; // resulting shift
2140
2141     return result_magic;
2142 }
2143
2144 int32_t GetSigned32Magic(int32_t d, int* shift /*out*/)
2145 {
2146     return GetSignedMagic<int32_t>(d, shift);
2147 }
2148
2149 #ifdef _TARGET_64BIT_
2150 int64_t GetSigned64Magic(int64_t d, int* shift /*out*/)
2151 {
2152     return GetSignedMagic<int64_t>(d, shift);
2153 }
2154 #endif
2155 }