src/vm/jit/optimizing/lsra.h

   1 /* src/vm/jit/optimizing/lsra.h - linear scan register allocator header
   2
   3    Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    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., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christian Ullrich
  28
  29    $Id: lsra.h,v 1.17 2005/11/22 14:36:16 christian Exp $
  30
  31 */
  32
  33
  34 #ifndef _LSRA_H
  35 #define _LSRA_H
  36
  37 #include "toolbox/bitvector.h"
  38
  39
  40 #if !defined(NDEBUG)
  41 # include <assert.h>
  42 # define LSRA_DEBUG_CHECK
  43 # define LSRA_DEBUG_VERBOSE
  44 #endif
  45
  46 #ifdef LSRA_DEBUG_CHECK
  47 # define _LSRA_CHECK_BOUNDS(i,l,h) assert( ((i) >= (l)) && ((i) < (h)));
  48 # define _LSRA_ASSERT(a) assert((a));
  49 #else
  50 # define _LSRA_CHECK_BOUNDS(i,l,h)
  51 # define _LSRA_ASSERT(a)
  52 #endif
  53
  54 /* let LSRA allocate reserved registers (REG_ITMP[1|2|3]) */
  55 #if defined(__I386__)
  56 /* #define LSRA_USES_REG_RES */
  57 /* # include "vm/jit/i386/icmd_uses_reg_res.inc.h" */
  58 #endif
  59
  60 /* #define LSRA_SAVEDVAR */
  61 /* #define LSRA_MEMORY */
  62
  63 #define USAGE_COUNT        /* influence LSRA with usagecount */
  64 /* #define USAGE_PER_INSTR */    /* divide usagecount by lifetimelength */
  65
  66
  67
  68 #define min(a,b) ((a)<(b)?(a):(b))
  69 #define max(a,b) ((a)<(b)?(b):(a))
  70
  71 struct site {
  72         int b_index;
  73         int iindex;
  74         struct site *next;
  75 };
  76
  77 struct lifetime {
  78         int i_start;                /* instruction number of first use */
  79         int i_end;                  /* instruction number of last use */
  80         int v_index;           /* local variable index or negative for stackslots */
  81         int type;                   /* TYPE_XXX or -1 for unused lifetime */
  82         long usagecount;            /* number of references*/
  83         int regoff;                    /* regoffset allocated by lsra*/
  84         int savedvar;
  85         int flags;
  86         /* struct stackslot *local_ss; */ /* Stackslots for this Lifetime or NULL ( ==  */
  87                                 /* "pure" Local Var) */
  88         int bb_last_use;
  89         int i_last_use;
  90         int bb_first_def;
  91         int i_first_def;
  92
  93         struct site *def;
  94         struct site *use;
  95         struct site *last_use;
  96 };
  97
  98 struct l_loop {
  99         int b_first;
 100         int b_last;
 101         int nesting;
 102 };
 103
 104 struct lsra_register {
 105         int *sav_reg;
 106         int *tmp_reg;
 107         int *nregdesc;
 108         int sav_top;
 109         int tmp_top;
 110 };
 111
 112 struct lsra_reg {
 113         int reg_index;
 114         int use;
 115 };
 116
 117 struct lsradata {
 118         int varcount;       /* size of vars array */
 119         int ssavarcount;    /* ls->vars[0..ssavarcount[ are all locals and iovars */
 120                             /* they are regarded for ssa renaming */
 121                             /* the rest (ls->vars[ssavarcount..varcount[ are      */
 122                             /* TEMP or PREALLOC vars with just on definition and  */
 123                             /* use within one basicblock -> not of interest for   */
 124                             /* ssa renaming procedures */
 125         int vartop;         /* next free var */
 126         int varcount_with_indices;
 127         int *new_varindex;  /* new_varindex[0..jd->varcount[ points to the new    */
 128                             /* unique index of ls->vars(maps jd->vars to ls->vars)*/
 129
 130         int *var_0;        /* [0..ls->varcount]  */
 131                            /* var_0[a] with a in [0..ls->varcount[ holds the */
 132                            /* index of La,0 */
 133                            /* var_0[ls->varcount] holds the number of vars with */
 134                            /*indices */
 135
 136         int *sorted;         /* BB sorted in reverse post order */
 137         int *sorted_rev;     /* BB reverse lookup of sorted */
 138
 139         long *nesting;    /* Nesting level of BB*/
 140
 141         struct lifetime *lifetime; /* array of lifetimes */
 142         int lifetimecount;         /* number of lifetimes */
 143         int *lt_used;              /* index to lifetimearray for used lifetimes   */
 144         int *lt_int;               /* index to lifetimearray for int lifetimes    */
 145         int lt_int_count;          /* number of int/[lng]/[adr] lifetimes */
 146         int *lt_flt;               /* index to lifetimearray for float lifetimes  */
 147         int lt_flt_count;          /* number of float/double lifetimes */
 148         int *lt_mem;               /* index to lifetimearray for all lifetimes    */
 149                                /* not to be allocated in registers */
 150         int lt_mem_count;          /* number of this other lifetimes */
 151
 152         struct lifetime **active_tmp, **active_sav;
 153         int active_tmp_top, active_sav_top;
 154
 155         struct lsra_exceptiontable *ex;
 156
 157         /* SSA fields */
 158         bitvector *var_def; /* LocalVar Definition Bitvector [0..ls->bbcount]  */
 159                             /* Bitvector holds ls->max_vars Bits               */
 160         bitvector *use_sites; /* LocalVar Use Bitvector[0..ls->maxvars] */
 161         int **num_var_use; /* count of var_use[bb][var_index] */
 162         int **var; /* [0..cd->maxlocal+cd->maxstack[[0..4] */
 163         /* ssa_set_local_def and ssa_set_interface (called from analyse_stack)    */
 164         /* set var[local_index][local_type] and var[jd->maxlocals+stack_depth]    */
 165         /* [stack_type] to a unique type independend index [0..ls->max_vars[      */
 166         /* unused entries are set to -1                                           */
 167         int max_vars;
 168         int max_vars_with_indices;
 169         int *num_defs;    /* counts definitions of variables     */
 170                           /* [0..jd->maxlocals*5+cd->maxstack*5[ */
 171                           /* valid for [0..ls->max_vars[         */
 172
 173
 174         int *local_0;     /* [0..ls->max_locals]  */
 175                           /* local_0[a] with a in [0..ls->max_locals[ holds the */
 176                           /* index of La,0 */
 177                           /* local_0[ls->maxlocals] holds the number of local   */
 178                           /* vars with indices */
 179         int *interface_0; /* same here, just with interfaces */
 180
 181         int *var_to_index; /* var index to interface (<0) or local (>=0) index */
 182                            /* [0..jd->maxlocals*5+cd->maxstack*5[              */
 183                            /* valid for [0..ls->max_vars[                      */
 184                            /* holds var_index or the negative interface index  */
 185                            /* in ssa_Rename_init the indices are changed to the */
 186                        /* index of the corresponding first Var with index;) */
 187                            /* (== local_0[] or interface_0[] */
 188         int max_locals;
 189         int max_interfaces;
 190
 191         int uses;
 192         int basicblockcount;
 193         basicblock **basicblocks;
 194         /* [0..ls->basicblockcount[[0..ls->max_locals[[0..ls->num_pre[bb]] */
 195         /* 3rd index represents the the var involved in the phi function   */
 196         /* a0 = phi(a1,a2,...,a(ls->num_pre[bb]-1)) */
 197         int ***phi;  /* [0..ls->basicblockcount[[0..ls->max_vars[[0,1] */
 198                      /* if no phi function for a Basic Block and var exists */
 199                      /* phi[bb][a] == NULL */
 200         int *num_phi_moves;
 201         int ***phi_moves; /* phi_moves[block_index][0..num_phi_moves[bi][0..1] */
 202                           /* [][][0] target */
 203                           /* [][][1] source */
 204
 205         int *count;  /* Helpers for ssa_Rename */
 206         int **stack;
 207         int *stack_top;
 208
 209 };
 210
 211
 212 struct freemem {
 213         int off;
 214         int end;
 215         struct freemem *next;
 216 };
 217
 218 typedef struct lsradata lsradata;
 219
 220 /* function prototypes */
 221 void lsra(jitdata *);
 222 #endif /* _LSRA_H */
 223
 224
 225 /*
 226  * These are local overrides for various environment variables in Emacs.
 227  * Please do not remove this and leave it at the end of the file, where
 228  * Emacs will automagically detect them.
 229  * ---------------------------------------------------------------------
 230  * Local variables:
 231  * mode: c
 232  * indent-tabs-mode: t
 233  * c-basic-offset: 4
 234  * tab-width: 4
 235  * End:
 236  */