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. */
mkHReg(Bool virtual,HRegClass rc,UInt enc,UInt ix)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
hregClass(HReg r)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
hregIndex(HReg r)158 static inline UInt hregIndex ( HReg r )
159 {
160 return r.u32 & 0xFFFFF;
161 }
162
hregEncoding(HReg r)163 static inline UInt hregEncoding ( HReg r )
164 {
165 return (r.u32 >> 20) & 0x7F;
166 }
167
hregIsVirtual(HReg r)168 static inline Bool hregIsVirtual ( HReg r )
169 {
170 return toBool((r.u32 >> 31) & 1);
171 }
172
sameHReg(HReg r1,HReg r2)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
hregIsInvalid(HReg r)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
initHRegUsage(HRegUsage * tab)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
initHRegRemap(HRegRemap * map)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
addHInstr(HInstrArray * ha,HInstr * instr)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
mk_RetLoc_simple(RetLocPrimary pri)443 static inline RetLoc mk_RetLoc_simple ( RetLocPrimary pri ) {
444 vassert(pri >= RLPri_INVALID && pri <= RLPri_2Int);
445 return (RetLoc){pri, 0};
446 }
447
mk_RetLoc_spRel(RetLocPrimary pri,Int off)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
is_sane_RetLoc(RetLoc rloc)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
mk_RetLoc_INVALID(void)464 static inline RetLoc mk_RetLoc_INVALID ( void ) {
465 return (RetLoc){RLPri_INVALID, 0};
466 }
467
is_RetLoc_INVALID(RetLoc rl)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 /*---------------------------------------------------------------*/
524