src/vm/jit/allocator/lsra.h

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