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