Home | History | Annotate | Download | only in priv
      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-2013 OpenWorks LLP
     11       info (at) 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_alloc2.c needs 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_alloc2.c 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    }
    123    HRegClass;
    124 
    125 extern void ppHRegClass ( HRegClass );
    126 
    127 
    128 /* Print an HReg in a generic (non-target-specific) way. */
    129 extern void 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 <= HRcVec128);
    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    RRegUniverse;
    226 
    227 /* Nominally initialise (zero out) an RRegUniverse. */
    228 void RRegUniverse__init ( /*OUT*/RRegUniverse* );
    229 
    230 /* Check an RRegUniverse is valid, and assert if not.*/
    231 void RRegUniverse__check_is_sane ( const RRegUniverse* );
    232 
    233 /* Print an RRegUniverse, for debugging. */
    234 void RRegUniverse__show ( const RRegUniverse* );
    235 
    236 
    237 /*---------------------------------------------------------*/
    238 /*--- Real register sets.                               ---*/
    239 /*---------------------------------------------------------*/
    240 
    241 /* Represents sets of real registers.  |bitset| is interpreted in the
    242    context of |univ|.  That is, each bit index |i| in |bitset|
    243    corresponds to the register |univ->regs[i]|.  This relies
    244    entirely on the fact that N_RREGUNIVERSE_REGS <= 64. */
    245 typedef
    246    struct {
    247       ULong         bitset;
    248       RRegUniverse* univ;
    249    }
    250    RRegSet;
    251 
    252 
    253 /*---------------------------------------------------------*/
    254 /*--- Recording register usage (for reg-alloc)          ---*/
    255 /*---------------------------------------------------------*/
    256 
    257 typedef
    258    enum { HRmRead, HRmWrite, HRmModify }
    259    HRegMode;
    260 
    261 
    262 /* This isn't entirely general, and is specialised towards being fast,
    263    for the reg-alloc.  It represents real registers using a bitmask
    264    and can also represent up to four virtual registers, in an
    265    unordered array.  This is based on the observation that no
    266    instruction that we generate can mention more than four registers
    267    at once.
    268 */
    269 #define N_HREGUSAGE_VREGS 5
    270 
    271 typedef
    272    struct {
    273       /* The real registers.  The associated universe is not stored
    274          here -- callers will have to pass it around separately, as
    275          needed. */
    276       ULong    rRead;     /* real regs that are read */
    277       ULong    rWritten;  /* real regs that are written */
    278       /* The virtual registers. */
    279       HReg     vRegs[N_HREGUSAGE_VREGS];
    280       HRegMode vMode[N_HREGUSAGE_VREGS];
    281       UInt     n_vRegs;
    282    }
    283    HRegUsage;
    284 
    285 extern void ppHRegUsage ( const RRegUniverse*, HRegUsage* );
    286 
    287 static inline void initHRegUsage ( HRegUsage* tab )
    288 {
    289    tab->rRead    = 0;
    290    tab->rWritten = 0;
    291    tab->n_vRegs  = 0;
    292 }
    293 
    294 /* Add a register to a usage table.  Combine incoming read uses with
    295    existing write uses into a modify use, and vice versa.  Do not
    296    create duplicate entries -- each reg should only be mentioned once.
    297 */
    298 extern void addHRegUse ( HRegUsage*, HRegMode, HReg );
    299 
    300 extern Bool HRegUsage__contains ( const HRegUsage*, HReg );
    301 
    302 
    303 /*---------------------------------------------------------*/
    304 /*--- Indicating register remappings (for reg-alloc)    ---*/
    305 /*---------------------------------------------------------*/
    306 
    307 /* Note that such maps can only map virtual regs to real regs.
    308    addToHRegRenap will barf if given a pair not of that form.  As a
    309    result, no valid HRegRemap will bind a real reg to anything, and so
    310    if lookupHRegMap is given a real reg, it returns it unchanged.
    311    This is precisely the behaviour that the register allocator needs
    312    to impose its decisions on the instructions it processes.  */
    313 
    314 #define N_HREG_REMAP 6
    315 
    316 typedef
    317    struct {
    318       HReg orig       [N_HREG_REMAP];
    319       HReg replacement[N_HREG_REMAP];
    320       Int  n_used;
    321    }
    322    HRegRemap;
    323 
    324 extern void ppHRegRemap     ( HRegRemap* );
    325 extern void addToHRegRemap  ( HRegRemap*, HReg, HReg );
    326 extern HReg lookupHRegRemap ( HRegRemap*, HReg );
    327 
    328 static inline void initHRegRemap ( HRegRemap* map )
    329 {
    330    map->n_used = 0;
    331 }
    332 
    333 
    334 /*---------------------------------------------------------*/
    335 /*--- Abstract instructions                             ---*/
    336 /*---------------------------------------------------------*/
    337 
    338 /* A type is needed to refer to pointers to instructions of any
    339    target.  Defining it like this means that HInstr* can stand in for
    340    X86Instr*, ArmInstr*, etc. */
    341 
    342 typedef  void  HInstr;
    343 
    344 
    345 /* An expandable array of HInstr*'s.  Handy for insn selection and
    346    register allocation.  n_vregs indicates the number of virtual
    347    registers mentioned in the code, something that reg-alloc needs to
    348    know.  These are required to be numbered 0 .. n_vregs-1.
    349 */
    350 typedef
    351    struct {
    352       HInstr** arr;
    353       Int      arr_size;
    354       Int      arr_used;
    355       Int      n_vregs;
    356    }
    357    HInstrArray;
    358 
    359 extern HInstrArray* newHInstrArray ( void );
    360 
    361 /* Never call this directly.  It's the slow and incomplete path for
    362    addHInstr. */
    363 __attribute__((noinline))
    364 extern void addHInstr_SLOW ( HInstrArray*, HInstr* );
    365 
    366 static inline void addHInstr ( HInstrArray* ha, HInstr* instr )
    367 {
    368    if (LIKELY(ha->arr_used < ha->arr_size)) {
    369       ha->arr[ha->arr_used] = instr;
    370       ha->arr_used++;
    371    } else {
    372       addHInstr_SLOW(ha, instr);
    373    }
    374 }
    375 
    376 
    377 /*---------------------------------------------------------*/
    378 /*--- C-Call return-location descriptions               ---*/
    379 /*---------------------------------------------------------*/
    380 
    381 /* This is common to all back ends.  It describes where the return
    382    value from a C call is located.  This is important in the case that
    383    the call is conditional, since the return locations will need to be
    384    set to 0x555..555 in the case that the call does not happen. */
    385 
    386 typedef
    387    enum {
    388       RLPri_INVALID,   /* INVALID */
    389       RLPri_None,      /* no return value (a.k.a C "void") */
    390       RLPri_Int,       /* in the primary int return reg */
    391       RLPri_2Int,      /* in both primary and secondary int ret regs */
    392       RLPri_V128SpRel, /* 128-bit value, on the stack */
    393       RLPri_V256SpRel  /* 256-bit value, on the stack */
    394    }
    395    RetLocPrimary;
    396 
    397 typedef
    398    struct {
    399       /* Primary description */
    400       RetLocPrimary pri;
    401       /* For .pri == RLPri_V128SpRel or RLPri_V256SpRel only, gives
    402          the offset of the lowest addressed byte of the value,
    403          relative to the stack pointer.  For all other .how values,
    404          has no meaning and should be zero. */
    405       Int spOff;
    406    }
    407    RetLoc;
    408 
    409 extern void ppRetLoc ( RetLoc rloc );
    410 
    411 static inline RetLoc mk_RetLoc_simple ( RetLocPrimary pri ) {
    412    vassert(pri >= RLPri_INVALID && pri <= RLPri_2Int);
    413    return (RetLoc){pri, 0};
    414 }
    415 
    416 static inline RetLoc mk_RetLoc_spRel ( RetLocPrimary pri, Int off ) {
    417    vassert(pri >= RLPri_V128SpRel && pri <= RLPri_V256SpRel);
    418    return (RetLoc){pri, off};
    419 }
    420 
    421 static inline Bool is_sane_RetLoc ( RetLoc rloc ) {
    422    switch (rloc.pri) {
    423       case RLPri_None: case RLPri_Int: case RLPri_2Int:
    424          return rloc.spOff == 0;
    425       case RLPri_V128SpRel: case RLPri_V256SpRel:
    426          return True;
    427       default:
    428          return False;
    429    }
    430 }
    431 
    432 static inline RetLoc mk_RetLoc_INVALID ( void ) {
    433    return (RetLoc){RLPri_INVALID, 0};
    434 }
    435 
    436 static inline Bool is_RetLoc_INVALID ( RetLoc rl ) {
    437    return rl.pri == RLPri_INVALID && rl.spOff == 0;
    438 }
    439 
    440 
    441 /*---------------------------------------------------------*/
    442 /*--- Reg alloc: TODO: move somewhere else              ---*/
    443 /*---------------------------------------------------------*/
    444 
    445 extern
    446 HInstrArray* doRegisterAllocation (
    447 
    448    /* Incoming virtual-registerised code. */
    449    HInstrArray* instrs_in,
    450 
    451    /* The real-register universe to use.  This contains facts about
    452       real registers, one of which is the set of registers available
    453       for allocation. */
    454    const RRegUniverse* univ,
    455 
    456    /* Return True iff the given insn is a reg-reg move, in which
    457       case also return the src and dst regs. */
    458    Bool (*isMove) (const HInstr*, HReg*, HReg*),
    459 
    460    /* Get info about register usage in this insn. */
    461    void (*getRegUsage) (HRegUsage*, const HInstr*, Bool),
    462 
    463    /* Apply a reg-reg mapping to an insn. */
    464    void (*mapRegs) (HRegRemap*, HInstr*, Bool),
    465 
    466    /* Return insn(s) to spill/restore a real reg to a spill slot
    467       offset.  And optionally a function to do direct reloads. */
    468    void    (*genSpill) (  HInstr**, HInstr**, HReg, Int, Bool ),
    469    void    (*genReload) ( HInstr**, HInstr**, HReg, Int, Bool ),
    470    HInstr* (*directReload) ( HInstr*, HReg, Short ),
    471    Int     guest_sizeB,
    472 
    473    /* For debug printing only. */
    474    void (*ppInstr) ( const HInstr*, Bool ),
    475    void (*ppReg) ( HReg ),
    476 
    477    /* 32/64bit mode */
    478    Bool mode64
    479 );
    480 
    481 
    482 #endif /* ndef __VEX_HOST_GENERIC_REGS_H */
    483 
    484 /*---------------------------------------------------------------*/
    485 /*---                                     host_generic_regs.h ---*/
    486 /*---------------------------------------------------------------*/
    487