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@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*/
89typedef  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*/
113typedef
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
125extern void ppHRegClass ( HRegClass );
126
127
128/* Print an HReg in a generic (non-target-specific) way. */
129extern 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. */
134static 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
149static 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
156static inline UInt hregIndex ( HReg r )
157{
158   return r.u32 & 0xFFFFF;
159}
160
161static inline UInt hregEncoding ( HReg r )
162{
163   return (r.u32 >> 20) & 0x7F;
164}
165
166static inline Bool hregIsVirtual ( HReg r )
167{
168   return toBool((r.u32 >> 31) & 1);
169}
170
171static inline Bool sameHReg ( HReg r1, HReg r2 )
172{
173   return toBool(r1.u32 == r2.u32);
174}
175
176static const HReg INVALID_HREG = { .u32 = 0xFFFFFFFF };
177
178static 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
213typedef
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. */
228void RRegUniverse__init ( /*OUT*/RRegUniverse* );
229
230/* Check an RRegUniverse is valid, and assert if not.*/
231void RRegUniverse__check_is_sane ( const RRegUniverse* );
232
233/* Print an RRegUniverse, for debugging. */
234void 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. */
245typedef
246   struct {
247      ULong         bitset;
248      RRegUniverse* univ;
249   }
250   RRegSet;
251
252
253/*---------------------------------------------------------*/
254/*--- Recording register usage (for reg-alloc)          ---*/
255/*---------------------------------------------------------*/
256
257typedef
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
271typedef
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
285extern void ppHRegUsage ( const RRegUniverse*, HRegUsage* );
286
287static 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*/
298extern void addHRegUse ( HRegUsage*, HRegMode, HReg );
299
300extern 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
316typedef
317   struct {
318      HReg orig       [N_HREG_REMAP];
319      HReg replacement[N_HREG_REMAP];
320      Int  n_used;
321   }
322   HRegRemap;
323
324extern void ppHRegRemap     ( HRegRemap* );
325extern void addToHRegRemap  ( HRegRemap*, HReg, HReg );
326extern HReg lookupHRegRemap ( HRegRemap*, HReg );
327
328static 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
342typedef  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*/
350typedef
351   struct {
352      HInstr** arr;
353      Int      arr_size;
354      Int      arr_used;
355      Int      n_vregs;
356   }
357   HInstrArray;
358
359extern HInstrArray* newHInstrArray ( void );
360
361/* Never call this directly.  It's the slow and incomplete path for
362   addHInstr. */
363__attribute__((noinline))
364extern void addHInstr_SLOW ( HInstrArray*, HInstr* );
365
366static 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
386typedef
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
397typedef
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
409extern void ppRetLoc ( RetLoc rloc );
410
411static inline RetLoc mk_RetLoc_simple ( RetLocPrimary pri ) {
412   vassert(pri >= RLPri_INVALID && pri <= RLPri_2Int);
413   return (RetLoc){pri, 0};
414}
415
416static inline RetLoc mk_RetLoc_spRel ( RetLocPrimary pri, Int off ) {
417   vassert(pri >= RLPri_V128SpRel && pri <= RLPri_V256SpRel);
418   return (RetLoc){pri, off};
419}
420
421static 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
432static inline RetLoc mk_RetLoc_INVALID ( void ) {
433   return (RetLoc){RLPri_INVALID, 0};
434}
435
436static 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
445extern
446HInstrArray* 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