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-2015 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_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. */
mkHReg(Bool virtual,HRegClass rc,UInt enc,UInt ix)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
hregClass(HReg r)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
hregIndex(HReg r)156 static inline UInt hregIndex ( HReg r )
157 {
158 return r.u32 & 0xFFFFF;
159 }
160
hregEncoding(HReg r)161 static inline UInt hregEncoding ( HReg r )
162 {
163 return (r.u32 >> 20) & 0x7F;
164 }
165
hregIsVirtual(HReg r)166 static inline Bool hregIsVirtual ( HReg r )
167 {
168 return toBool((r.u32 >> 31) & 1);
169 }
170
sameHReg(HReg r1,HReg r2)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
hregIsInvalid(HReg r)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
initHRegUsage(HRegUsage * tab)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
initHRegRemap(HRegRemap * map)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
addHInstr(HInstrArray * ha,HInstr * instr)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
mk_RetLoc_simple(RetLocPrimary pri)411 static inline RetLoc mk_RetLoc_simple ( RetLocPrimary pri ) {
412 vassert(pri >= RLPri_INVALID && pri <= RLPri_2Int);
413 return (RetLoc){pri, 0};
414 }
415
mk_RetLoc_spRel(RetLocPrimary pri,Int off)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
is_sane_RetLoc(RetLoc rloc)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
mk_RetLoc_INVALID(void)432 static inline RetLoc mk_RetLoc_INVALID ( void ) {
433 return (RetLoc){RLPri_INVALID, 0};
434 }
435
is_RetLoc_INVALID(RetLoc rl)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