src/vm/jit/allocator/lsra.h

   1 /* src/vm/jit/allocator/lsra.h - linear scan register allocator header
   2
   3    Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Christian Ullrich
  28
  29    Changes: Edwin Steiner
  30
  31    $Id: lsra.h 5240 2006-08-16 11:31:02Z christian $
  32
  33 */
  34
  35
  36 #ifndef _LSRA_H
  37 #define _LSRA_H
  38
  39 #include "config.h"
  40
  41 #if !defined(NDEBUG)
  42 # include <assert.h>
  43 # define LSRA_DEBUG_CHECK
  44 # define LSRA_DEBUG_VERBOSE
  45 #endif
  46
  47 #ifdef SSA_DEBUG_CHECK
  48 # define _LSRA_CHECK_BOUNDS(i,l,h) assert( ((i) >= (l)) && ((i) < (h)));
  49 # define _LSRA_ASSERT(a) assert((a));
  50 #else
  51 # define _LSRA_CHECK_BOUNDS(i,l,h)
  52 # define _LSRA_ASSERT(a)
  53 #endif
  54
  55 /* #define LSRA_DEBUG  */ /* lsra debug messages */
  56 /* #define LSRA_SAVEDVAR */
  57 /* #define LSRA_MEMORY */
  58 #if defined(__I386__) || defined(__X86_64__)
  59 #define JOIN_DEST_STACK           /* The destination stackslot gets the same  */
  60         /* register as one of the src stackslots. Important for i386 & X86_64 */
  61         /* since they do not have "3 operand" arithmetic instructions to      */
  62         /* prevent usage of a reserved register (REG_ITMPX)                   */
  63 #endif
  64 #define JOIN_DUP_STACK         /* join "identical" stackslots created by dup* */
  65
  66 #define USAGE_COUNT        /* influence LSRA with usagecount */
  67 #define USEAGE_COUNT_EXACT /* search all active lifetimes and regard */
  68                            /* usage_count */
  69 #define USAGE_PER_INSTR    /* divide usagecount by lifetimelength */
  70
  71 #define LSRA_BB_IN 3
  72 #define LSRA_BB_OUT 2
  73 #define LSRA_STORE 1
  74 #define LSRA_LOAD 0
  75 #define LSRA_POP -1
  76
  77 /* join types and flags*/
  78 #define JOIN     0 /* joins that are not in any way dangerous                 */
  79 #define JOIN_BB  1 /* join Stackslots over Basic Block Boundaries             */
  80 #define JOIN_DUP 2 /* join of two possibly concurring lifeteimes through DUP* */
  81 #define JOIN_OP  4 /* join of src operand with dst operand on i386 and x86_64 */
  82                    /* architecture                                            */
  83                    /* JOIN_DUP and JOIN_OP is mutually exclusive as JOIN_OP   */
  84                    /* and JOIN_BB                                             */
  85 #define JOINING  8 /* set while joining for DUP or OP to prevent assignement  */
  86                    /* to a REG_RES before all involved lifetimes have been    */
  87                    /* seen completely */
  88
  89 #define min(a,b) ((a)<(b)?(a):(b))
  90 #define max(a,b) ((a)<(b)?(b):(a))
  91
  92 struct _list {
  93         int value;
  94         struct _list *next;
  95 };
  96
  97 struct _backedge {
  98         int start;
  99         int end;
 100         int nesting;
 101         struct _backedge *next;
 102 };
 103
 104 struct lifetime {
 105         int i_start;                /* instruction number of first use */
 106         int i_end;                  /* instruction number of last use */
 107         int v_index;           /* local variable index or negative for stackslots */
 108         int type;                   /* TYPE_* or -1 for unused lifetime */
 109         long usagecount;            /* number of references*/
 110         int reg;                    /* regoffset allocated by lsra*/
 111         int savedvar;
 112         int flags;
 113         struct stackslot *local_ss; /* Stackslots for this Lifetime or NULL ( ==  */
 114                                 /* "pure" Local Var) */
 115         int bb_last_use;
 116         int bb_first_def;
 117         int i_last_use;
 118         int i_first_def;
 119 };
 120
 121 struct l_loop {
 122         int b_first;
 123         int b_last;
 124         int nesting;
 125 };
 126
 127 struct b_loop {
 128         int loop;
 129         int instr;
 130 };
 131
 132
 133 struct stackslot {
 134         stackptr s;
 135         int bb;
 136         struct stackslot *next;
 137 };
 138
 139 struct lsra_register {
 140         int *sav_reg;
 141         int *tmp_reg;
 142         int *nregdesc;
 143         int sav_top;
 144         int tmp_top;
 145 };
 146
 147 struct lsra_reg {
 148         int reg_index;
 149         int use;
 150 };
 151
 152 struct _sbr {
 153         int header;          /* BB Index of subroutine start (SBR_HEADER) */
 154         struct _list *ret;   /* List of possible return BB indizes */
 155         struct _sbr *next;
 156 };
 157
 158 struct lsradata {
 159 #if defined(LSRA_USES_REG_RES)
 160         int reg_res_free[REG_RES_CNT];
 161 #endif
 162         struct _list **succ; /* CFG successors*/
 163         struct _list **pred; /* CFG predecessors */
 164         int *num_pred;       /* CFG number of predecessors */
 165         int *sorted;         /* BB sorted in reverse post order */
 166         int *sorted_rev;     /* BB reverse lookup of sorted */
 167
 168         struct _backedge **backedge; /* backedge data structure */
 169         int backedge_count;          /* number of backedges */
 170
 171         struct _sbr sbr;     /* list of subroutines, sorted by header */
 172
 173         long *nesting;    /* Nesting level of BB*/
 174
 175         int maxlifetimes; /* copy from methodinfo to prevent passing methodinfo   */
 176                       /* as parameter */
 177
 178         struct lifetime *lifetime; /* array of lifetimes */
 179         int lifetimecount;         /* number of lifetimes */
 180         int *lt_used;              /* index to lifetimearray for used lifetimes   */
 181         int *lt_int;               /* index to lifetimearray for int lifetimes    */
 182         int lt_int_count;          /* number of int/[lng]/[adr] lifetimes */
 183         int *lt_flt;               /* index to lifetimearray for float lifetimes  */
 184         int lt_flt_count;          /* number of float/double lifetimes */
 185         int *lt_mem;               /* index to lifetimearray for all lifetimes    */
 186                                /* not to be allocated in registers */
 187         int lt_mem_count;          /* number of this other lifetimes */
 188
 189         struct lifetime **active_tmp, **active_sav;
 190         int active_tmp_top, active_sav_top;
 191
 192         struct lsra_exceptiontable *ex;
 193         int v_index;               /* next free index for stack slot lifetimes    */
 194                                    /* decrements from -1 */
 195         int *icount_block;
 196 };
 197
 198 struct freemem {
 199         int off;
 200         int end;
 201         struct freemem *next;
 202 };
 203
 204 typedef struct lsradata lsradata;
 205
 206
 207 /* function prototypes ********************************************************/
 208
 209 bool lsra(jitdata *jd);
 210
 211 #endif /* _LSRA_H */
 212
 213
 214 /*
 215  * These are local overrides for various environment variables in Emacs.
 216  * Please do not remove this and leave it at the end of the file, where
 217  * Emacs will automagically detect them.
 218  * ---------------------------------------------------------------------
 219  * Local variables:
 220  * mode: c
 221  * indent-tabs-mode: t
 222  * c-basic-offset: 4
 223  * tab-width: 4
 224  * End:
 225  * vim:noexpandtab:sw=4:ts=4:
 226  */