VEX/priv/host_generic_regs.h

   1
   2 /*---------------------------------------------------------------*/
   3 /*--- begin                               host_generic_regs.h ---*/
   4 /*---------------------------------------------------------------*/
   5
   6 /*
   7    This file is part of Valgrind, a dynamic binary instrumentation
   8    framework.
   9
  10    Copyright (C) 2004-2017 OpenWorks LLP
  11       info@open-works.net
  12
  13    This program is free software; you can redistribute it and/or
  14    modify it under the terms of the GNU General Public License as
  15    published by the Free Software Foundation; either version 2 of the
  16    License, or (at your option) any later version.
  17
  18    This program is distributed in the hope that it will be useful, but
  19    WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21    General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program; if not, see <http://www.gnu.org/licenses/>.
  25
  26    The GNU General Public License is contained in the file COPYING.
  27
  28    Neither the names of the U.S. Department of Energy nor the
  29    University of California nor the names of its contributors may be
  30    used to endorse or promote products derived from this software
  31    without prior written permission.
  32 */
  33
  34 #ifndef __VEX_HOST_GENERIC_REGS_H
  35 #define __VEX_HOST_GENERIC_REGS_H
  36
  37 #include "libvex_basictypes.h"
  38
  39
  40 /*---------------------------------------------------------*/
  41 /*--- Representing HOST REGISTERS                       ---*/
  42 /*---------------------------------------------------------*/
  43
  44 /* Host registers.  Stuff to represent:
  45
  46    - The register index.  This is a zero-based, sequential index that
  47      facilitates indexing into arrays or virtual or real registers.
  48      Virtual and real registers both have indices starting at zero.
  49      Interpreting a real register index requires having the host's
  50      RRegUniverse to hand.
  51
  52    - The register's hardware encoding.  This applies only for real
  53      registers and should be zero for virtual registers.  This is the
  54      number as used in a target architecture encoding.
  55
  56    - The register class
  57
  58    - Whether or not the register is a virtual reg.
  59
  60    Registers are sized so as to fit into 32 bits.
  61
  62    Note that since the class field is never 1111b, no valid register
  63    can have the value INVALID_HREG.
  64
  65    There are currently 6 register classes:
  66
  67      int32 int64 float32 float64 simd64 simd128
  68 */
  69
  70 /* Registers are represented as 32 bit integers, with the following layout:
  71
  72    31     30..27  26..20  19..0
  73    isV:1  rc:4    enc:7   ix:20
  74
  75    where
  76       UInt      ix:20;   // Zero based index
  77       UInt      enc:7;   // Hardware encoding number
  78       HRegClass rc:4;    // the register's HRegClass
  79       Bool      isV:1;   // is it a virtual register?
  80
  81    The obvious thing to do here would be to use bitfields.  But gcc
  82    seems to have problems constant folding calls to mkHReg() with all
  83    4 parameters constant to a 32 bit number, when using bitfields.
  84    Hence the use of the traditional shift-and-mask by-hand bitfields
  85    instead.
  86 */
  87 typedef  struct { UInt u32; }  HReg;
  88
  89 /* HRegClass describes host register classes which the instruction
  90    selectors can speak about.  We would not expect all of them to be
  91    available on any specific host.  For example on x86, the available
  92    classes are: Int32, Flt64, Vec128 only.
  93
  94    IMPORTANT NOTE: host_generic_reg_alloc*.c needs to know how much space is
  95    needed to spill each class of register.  It allocates the following
  96    amount of space:
  97
  98       HRcInt32     64 bits
  99       HRcInt64     64 bits
 100       HRcFlt32     64 bits
 101       HRcFlt64     128 bits (on x86 these are spilled by fstpt/fldt and
 102                              so won't fit in a 64-bit slot)
 103       HRcVec64     64 bits
 104       HRcVec128    128 bits
 105
 106    If you add another regclass, you must remember to update
 107    host_generic_reg_alloc*.c and RRegUniverse accordingly.
 108
 109    When adding entries to enum HRegClass, do not use any value > 14 or < 1.
 110 */
 111 typedef
 112    enum {
 113       HRcINVALID=1,   /* NOT A VALID REGISTER CLASS */
 114       HRcInt32=3,     /* 32-bit int */
 115       HRcInt64=4,     /* 64-bit int */
 116       HRcFlt32=5,     /* 32-bit float */
 117       HRcFlt64=6,     /* 64-bit float */
 118       HRcVec64=7,     /* 64-bit SIMD */
 119       HRcVec128=8,    /* 128-bit SIMD */
 120       HrcLAST=HRcVec128
 121    }
 122    HRegClass;
 123
 124 extern void ppHRegClass ( HRegClass );
 125
 126
 127 /* Print an HReg in a generic (non-target-specific) way.
 128    Returns number of HChar's written. */
 129 extern UInt ppHReg ( HReg );
 130
 131 /* Construct.  The goal here is that compiler can fold this down to a
 132    constant in the case where the four arguments are constants, which
 133    is often the case. */
 134 static inline HReg mkHReg ( Bool virtual, HRegClass rc, UInt enc, UInt ix )
 135 {
 136    vassert(ix <= 0xFFFFF);
 137    vassert(enc <= 0x7F);
 138    vassert(((UInt)rc) <= 0xF);
 139    vassert(((UInt)virtual) <= 1);
 140    if (virtual) vassert(enc == 0);
 141    HReg r;
 142    r.u32 = ((((UInt)virtual) & 1)       << 31)  |
 143            ((((UInt)rc)      & 0xF)     << 27)  |
 144            ((((UInt)enc)     & 0x7F)    << 20)  |
 145            ((((UInt)ix)      & 0xFFFFF) << 0);
 146    return r;
 147 }
 148
 149 static inline HRegClass hregClass ( HReg r )
 150 {
 151    HRegClass rc = (HRegClass)((r.u32 >> 27) & 0xF);
 152    vassert(rc >= HRcInt32 && rc <= HrcLAST);
 153    return rc;
 154 }
 155
 156 static inline UInt hregIndex ( HReg r )
 157 {
 158    return r.u32 & 0xFFFFF;
 159 }
 160
 161 static inline UInt hregEncoding ( HReg r )
 162 {
 163    return (r.u32 >> 20) & 0x7F;
 164 }
 165
 166 static inline Bool hregIsVirtual ( HReg r )
 167 {
 168    return toBool((r.u32 >> 31) & 1);
 169 }
 170
 171 static inline Bool sameHReg ( HReg r1, HReg r2 )
 172 {
 173    return toBool(r1.u32 == r2.u32);
 174 }
 175
 176 static const HReg INVALID_HREG = { .u32 = 0xFFFFFFFF };
 177
 178 static inline Bool hregIsInvalid ( HReg r )
 179 {
 180    return sameHReg(r, INVALID_HREG);
 181 }
 182
 183
 184 /*---------------------------------------------------------*/
 185 /*--- Real register Universes.                          ---*/
 186 /*---------------------------------------------------------*/
 187
 188 /* A "Real Register Universe" is a read-only structure that contains
 189    all information about real registers on a given host.  It serves
 190    several purposes:
 191
 192    * defines the mapping from real register indices to the registers
 193      themselves
 194
 195    * defines the size of the initial section of that mapping that is
 196      available to the register allocator for use, so that the register
 197      allocator can treat the registers under its control as a zero
 198      based, contiguous array.  This is important for its efficiency.
 199
 200    * gives meaning to RRegSets, which otherwise would merely be a
 201      bunch of bits.
 202
 203    This is a big structure, but it's readonly, and we expect to
 204    allocate only one instance for each run of Valgrind.  It is sized
 205    so as to be able to deal with up to 64 real registers.  AFAICS none
 206    of the back ends actually mention more than 64, despite the fact
 207    that many of the host architectures have more than 64 registers
 208    when all classes are taken into consideration.
 209 */
 210
 211 #define N_RREGUNIVERSE_REGS 64
 212
 213 typedef
 214    struct {
 215       /* Total number of registers in this universe .. */
 216       UInt size;
 217       /* .. of which the first |allocable| are available to regalloc. */
 218       UInt allocable;
 219       /* The registers themselves.  All must be real registers, and
 220          all must have their index number (.s.ix) equal to the array
 221          index here, since this is the only place where we map index
 222          numbers to actual registers. */
 223       HReg regs[N_RREGUNIVERSE_REGS];
 224
 225       /* Ranges for groups of allocable registers. Used to quickly address only
 226          a group of allocable registers belonging to the same register class.
 227          Indexes into |allocable_{start,end}| are HRcClass entries, such as
 228          HRcInt64. Values in |allocable_{start,end}| give a valid range into
 229          |regs| where registers corresponding to the given register class are
 230          found.
 231
 232          For example, let's say allocable_start[HRcInt64] == 10 and
 233          allocable_end[HRcInt64] == 14. Then regs[10], regs[11], regs[12],
 234          regs[13], and regs[14] give all registers of register class HRcInt64.
 235
 236          If a register class is not present, then values of the corresponding
 237          |allocable_{start,end}| elements are equal to N_RREGUNIVERSE_REGS.
 238
 239          Naturally registers in |regs| must form contiguous groups. This is
 240          checked by RRegUniverse__check_is_sane(). */
 241       UInt allocable_start[HrcLAST + 1];
 242       UInt allocable_end[HrcLAST + 1];
 243    }
 244    RRegUniverse;
 245
 246 /* Nominally initialise (zero out) an RRegUniverse. */
 247 void RRegUniverse__init ( /*OUT*/RRegUniverse* );
 248
 249 /* Check an RRegUniverse is valid, and assert if not.*/
 250 void RRegUniverse__check_is_sane ( const RRegUniverse* );
 251
 252 /* Print an RRegUniverse, for debugging. */
 253 void RRegUniverse__show ( const RRegUniverse* );
 254
 255
 256 /*---------------------------------------------------------*/
 257 /*--- Real register sets.                               ---*/
 258 /*---------------------------------------------------------*/
 259
 260 /* Represents sets of real registers.  |bitset| is interpreted in the
 261    context of |univ|.  That is, each bit index |i| in |bitset|
 262    corresponds to the register |univ->regs[i]|.  This relies
 263    entirely on the fact that N_RREGUNIVERSE_REGS <= 64. */
 264 typedef
 265    struct {
 266       ULong         bitset;
 267       RRegUniverse* univ;
 268    }
 269    RRegSet;
 270
 271
 272 /*---------------------------------------------------------*/
 273 /*--- Recording register usage (for reg-alloc)          ---*/
 274 /*---------------------------------------------------------*/
 275
 276 typedef
 277    enum { HRmRead, HRmWrite, HRmModify }
 278    HRegMode;
 279
 280
 281 /* This isn't entirely general, and is specialised towards being fast,
 282    for the reg-alloc.  It represents real registers using a bitmask
 283    and can also represent up to four virtual registers, in an
 284    unordered array.  This is based on the observation that no
 285    instruction that we generate can mention more than four registers
 286    at once.
 287 */
 288 #define N_HREGUSAGE_VREGS 5
 289
 290 typedef
 291    struct {
 292       /* The real registers.  The associated universe is not stored
 293          here -- callers will have to pass it around separately, as
 294          needed. */
 295       ULong    rRead;     /* real regs that are read */
 296       ULong    rWritten;  /* real regs that are written */
 297       /* The virtual registers. */
 298       HReg     vRegs[N_HREGUSAGE_VREGS];
 299       HRegMode vMode[N_HREGUSAGE_VREGS];
 300       UInt     n_vRegs;
 301
 302       /* Hint to the register allocator: this instruction is actually a move
 303          between two registers: regMoveSrc -> regMoveDst. */
 304       Bool     isRegRegMove;
 305       HReg     regMoveSrc;
 306       HReg     regMoveDst;
 307
 308       /* Used internally by the register allocator. The reg-reg move is
 309          actually a vreg-vreg move. */
 310       Bool     isVregVregMove;
 311    }
 312    HRegUsage;
 313
 314 extern void ppHRegUsage ( const RRegUniverse*, HRegUsage* );
 315
 316 static inline void initHRegUsage ( HRegUsage* tab )
 317 {
 318    tab->rRead        = 0;
 319    tab->rWritten     = 0;
 320    tab->n_vRegs      = 0;
 321    tab->isRegRegMove = False;
 322 }
 323
 324 /* Add a register to a usage table.  Combine incoming read uses with
 325    existing write uses into a modify use, and vice versa.  Do not
 326    create duplicate entries -- each reg should only be mentioned once.
 327 */
 328 extern void addHRegUse ( HRegUsage*, HRegMode, HReg );
 329
 330 extern Bool HRegUsage__contains ( const HRegUsage*, HReg );
 331
 332
 333 /*---------------------------------------------------------*/
 334 /*--- Indicating register remappings (for reg-alloc)    ---*/
 335 /*---------------------------------------------------------*/
 336
 337 /* Note that such maps can only map virtual regs to real regs.
 338    addToHRegRemap will barf if given a pair not of that form.  As a
 339    result, no valid HRegRemap will bind a real reg to anything, and so
 340    if lookupHRegMap is given a real reg, it returns it unchanged.
 341    This is precisely the behaviour that the register allocator needs
 342    to impose its decisions on the instructions it processes.  */
 343
 344 #define N_HREG_REMAP 6
 345
 346 typedef
 347    struct {
 348       HReg orig       [N_HREG_REMAP];
 349       HReg replacement[N_HREG_REMAP];
 350       Int  n_used;
 351    }
 352    HRegRemap;
 353
 354 extern void ppHRegRemap     ( HRegRemap* );
 355 extern void addToHRegRemap  ( HRegRemap*, HReg, HReg );
 356 extern HReg lookupHRegRemap ( HRegRemap*, HReg );
 357
 358 static inline void initHRegRemap ( HRegRemap* map )
 359 {
 360    map->n_used = 0;
 361 }
 362
 363
 364 /*---------------------------------------------------------*/
 365 /*--- Abstract instructions                             ---*/
 366 /*---------------------------------------------------------*/
 367
 368 /* A type is needed to refer to pointers to instructions of any
 369    target.  Defining it like this means that HInstr* can stand in for
 370    X86Instr*, ArmInstr*, etc. */
 371
 372 typedef  void  HInstr;
 373
 374
 375 /* An expandable array of HInstr*'s.  Handy for insn selection and
 376    register allocation.  n_vregs indicates the number of virtual
 377    registers mentioned in the code, something that reg-alloc needs to
 378    know.  These are required to be numbered 0 .. n_vregs-1.
 379 */
 380 typedef
 381    struct {
 382       HInstr** arr;
 383       Int      arr_size;
 384       Int      arr_used;
 385       Int      n_vregs;
 386    }
 387    HInstrArray;
 388
 389 extern HInstrArray* newHInstrArray ( void );
 390
 391 /* Never call this directly.  It's the slow and incomplete path for
 392    addHInstr. */
 393 __attribute__((noinline))
 394 extern void addHInstr_SLOW ( HInstrArray*, HInstr* );
 395
 396 static inline void addHInstr ( HInstrArray* ha, HInstr* instr )
 397 {
 398    if (LIKELY(ha->arr_used < ha->arr_size)) {
 399       ha->arr[ha->arr_used] = instr;
 400       ha->arr_used++;
 401    } else {
 402       addHInstr_SLOW(ha, instr);
 403    }
 404 }
 405
 406
 407 /*---------------------------------------------------------*/
 408 /*--- C-Call return-location descriptions               ---*/
 409 /*---------------------------------------------------------*/
 410
 411 /* This is common to all back ends.  It describes where the return
 412    value from a C call is located.  This is important in the case that
 413    the call is conditional, since the return locations will need to be
 414    set to 0x555..555 in the case that the call does not happen. */
 415
 416 typedef
 417    enum {
 418       RLPri_INVALID,   /* INVALID */
 419       RLPri_None,      /* no return value (a.k.a C "void") */
 420       RLPri_Int,       /* in the primary int return reg */
 421       RLPri_2Int,      /* in both primary and secondary int ret regs */
 422       RLPri_V128SpRel, /* 128-bit value, on the stack */
 423       RLPri_V256SpRel  /* 256-bit value, on the stack */
 424    }
 425    RetLocPrimary;
 426
 427 typedef
 428    struct {
 429       /* Primary description */
 430       RetLocPrimary pri;
 431       /* For .pri == RLPri_V128SpRel or RLPri_V256SpRel only, gives
 432          the offset of the lowest addressed byte of the value,
 433          relative to the stack pointer.  For all other .how values,
 434          has no meaning and should be zero. */
 435       Int spOff;
 436    }
 437    RetLoc;
 438
 439 extern void ppRetLoc ( RetLoc rloc );
 440
 441 static inline RetLoc mk_RetLoc_simple ( RetLocPrimary pri ) {
 442    vassert(pri >= RLPri_INVALID && pri <= RLPri_2Int);
 443    return (RetLoc){pri, 0};
 444 }
 445
 446 static inline RetLoc mk_RetLoc_spRel ( RetLocPrimary pri, Int off ) {
 447    vassert(pri >= RLPri_V128SpRel && pri <= RLPri_V256SpRel);
 448    return (RetLoc){pri, off};
 449 }
 450
 451 static inline Bool is_sane_RetLoc ( RetLoc rloc ) {
 452    switch (rloc.pri) {
 453       case RLPri_None: case RLPri_Int: case RLPri_2Int:
 454          return rloc.spOff == 0;
 455       case RLPri_V128SpRel: case RLPri_V256SpRel:
 456          return True;
 457       default:
 458          return False;
 459    }
 460 }
 461
 462 static inline RetLoc mk_RetLoc_INVALID ( void ) {
 463    return (RetLoc){RLPri_INVALID, 0};
 464 }
 465
 466 static inline Bool is_RetLoc_INVALID ( RetLoc rl ) {
 467    return rl.pri == RLPri_INVALID && rl.spOff == 0;
 468 }
 469
 470
 471 /*---------------------------------------------------------*/
 472 /*--- Reg alloc: TODO: move somewhere else              ---*/
 473 /*---------------------------------------------------------*/
 474
 475 /* Control of the VEX register allocator. */
 476 typedef
 477    struct {
 478       /* The real-register universe to use.  This contains facts about real
 479          registers, one of which is the set of registers available for
 480          allocation. */
 481       const RRegUniverse* univ;
 482
 483       /* Get info about register usage in this insn. */
 484       void (*getRegUsage)(HRegUsage*, const HInstr*, Bool);
 485
 486       /* Apply a reg-reg mapping to an insn. */
 487       void (*mapRegs)(HRegRemap*, HInstr*, Bool);
 488
 489       /* Return insn(s) to spill/restore a real register to a spill slot offset.
 490          Also a function to move between registers.
 491          And optionally a function to do direct reloads. */
 492       void    (*genSpill)(HInstr**, HInstr**, HReg, Int, Bool);
 493       void    (*genReload)(HInstr**, HInstr**, HReg, Int, Bool);
 494       HInstr* (*genMove)(HReg from, HReg to, Bool);
 495       HInstr* (*directReload)(HInstr*, HReg, Short);
 496       UInt    guest_sizeB;
 497
 498       /* For debug printing only. */
 499       void (*ppInstr)(const HInstr*, Bool);
 500       UInt (*ppReg)(HReg);
 501
 502       /* 32/64bit mode */
 503       Bool mode64;
 504    }
 505    RegAllocControl;
 506
 507 extern HInstrArray* doRegisterAllocation_v2(
 508    HInstrArray* instrs_in,
 509    const RegAllocControl* con
 510 );
 511 extern HInstrArray* doRegisterAllocation_v3(
 512    HInstrArray* instrs_in,
 513    const RegAllocControl* con
 514 );
 515
 516
 517 #endif /* ndef __VEX_HOST_GENERIC_REGS_H */
 518
 519 /*---------------------------------------------------------------*/
 520 /*---                                     host_generic_regs.h ---*/
 521 /*---------------------------------------------------------------*/