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 #if !defined(NDEBUG)
  40 # include <assert.h>
  41 # define LSRA_DEBUG_CHECK
  42 # define LSRA_DEBUG_VERBOSE
  43 #endif
  44
  45 #ifdef LSRA_DEBUG_CHECK
  46 # define _LSRA_CHECK_BOUNDS(i,l,h) assert( ((i) >= (l)) && ((i) < (h)));
  47 # define _LSRA_ASSERT(a) assert((a));
  48 #else
  49 # define _LSRA_CHECK_BOUNDS(i,l,h)
  50 # define _LSRA_ASSERT(a)
  51 #endif
  52
  53 /* let LSRA allocate reserved registers (REG_ITMP[1|2|3]) */
  54 #if defined(__I386__)
  55 /* #define LSRA_USES_REG_RES */
  56 /* # include "vm/jit/i386/icmd_uses_reg_res.inc.h" */
  57 #endif
  58
  59 /* #define LSRA_SAVEDVAR */
  60 /* #define LSRA_MEMORY */
  61
  62 #define USAGE_COUNT        /* influence LSRA with usagecount */
  63 /* #define USAGE_PER_INSTR */    /* divide usagecount by lifetimelength */
  64
  65
  66
  67 #define min(a,b) ((a)<(b)?(a):(b))
  68 #define max(a,b) ((a)<(b)?(b):(a))
  69
  70 struct _backedge {
  71         int start;
  72         int end;
  73         int nesting;
  74         struct _backedge *next;
  75 };
  76
  77 struct site {
  78         int b_index;
  79         int iindex;
  80         struct site *next;
  81 };
  82
  83 struct lifetime {
  84         int i_start;                /* instruction number of first use */
  85         int i_end;                  /* instruction number of last use */
  86         int v_index;           /* local variable index or negative for stackslots */
  87         int type;                   /* TYPE_XXX or -1 for unused lifetime */
  88         long usagecount;            /* number of references*/
  89         int reg;                    /* regoffset allocated by lsra*/
  90         int savedvar;
  91         int flags;
  92         struct stackslot *local_ss; /* Stackslots for this Lifetime or NULL ( ==  */
  93                                 /* "pure" Local Var) */
  94         int bb_last_use;
  95         int i_last_use;
  96         int bb_first_def;
  97         int i_first_def;
  98
  99         struct site *def;
 100         struct site *use;
 101         struct site *last_use;
 102 };
 103
 104 struct l_loop {
 105         int b_first;
 106         int b_last;
 107         int nesting;
 108 };
 109
 110 struct stackslot {
 111         stackptr s;
 112         int bb;
 113         struct stackslot *next;
 114 };
 115
 116 struct lsra_register {
 117         int *sav_reg;
 118         int *tmp_reg;
 119         int *nregdesc;
 120         int sav_top;
 121         int tmp_top;
 122 };
 123
 124 struct lsra_reg {
 125         int reg_index;
 126         int use;
 127 };
 128
 129 struct igraph_lookup {
 130         int var;
 131         int igraph;
 132 };
 133
 134 struct igraph_interference {
 135         int v1;
 136         int v2;
 137         struct igraph_interference *next;
 138 };
 139
 140 struct igraph_vars {
 141         int v;
 142         struct igraph_vars *next;
 143 };
 144
 145 struct igraph {
 146         struct igraph_interference *inter;
 147         struct igraph_vars *vars;
 148 };
 149
 150
 151 struct lsradata {
 152         int *sorted;         /* BB sorted in reverse post order */
 153         int *sorted_rev;     /* BB reverse lookup of sorted */
 154
 155         struct _backedge **backedge; /* backedge data structure */
 156         int backedge_count;          /* number of backedges */
 157
 158         long *nesting;    /* Nesting level of BB*/
 159
 160         int maxlifetimes; /* copy from methodinfo to prevent passing methodinfo   */
 161                       /* as parameter */
 162
 163         struct lifetime *lifetime; /* array of lifetimes */
 164         int lifetimecount;         /* number of lifetimes */
 165         int *lt_used;              /* index to lifetimearray for used lifetimes   */
 166         int *lt_int;               /* index to lifetimearray for int lifetimes    */
 167         int lt_int_count;          /* number of int/[lng]/[adr] lifetimes */
 168         int *lt_flt;               /* index to lifetimearray for float lifetimes  */
 169         int lt_flt_count;          /* number of float/double lifetimes */
 170         int *lt_mem;               /* index to lifetimearray for all lifetimes    */
 171                                /* not to be allocated in registers */
 172         int lt_mem_count;          /* number of this other lifetimes */
 173
 174         struct lifetime **active_tmp, **active_sav;
 175         int active_tmp_top, active_sav_top;
 176
 177         struct lsra_exceptiontable *ex;
 178         int v_index;               /* next free index for stack slot lifetimes    */
 179                                    /* decrements from -1 */
 180
 181         /* SSA fields */
 182         bitvector *var_def; /* LocalVar Definition Bitvector [0..ls->bbcount]  */
 183                        /* Bitvector holds ls->max_vars Bits              */
 184         bitvector *use_sites; /* LocalVar Use Bitvector[0..ls->maxvars] */
 185         int **num_var_use; /* count of var_use[bb][var_index] */
 186         int **var; /* [0..cd->maxlocal+cd->maxstack[[0..4] */
 187         /* ssa_set_local_def and ssa_set_interface (called from analyse_stack)    */
 188         /* set var[local_index][local_type] and var[cd->maxlocals+stack_depth]    */
 189         /* [stack_type] to a unique type independend index [0..ls->max_vars[      */
 190         /* unused entries are set to -1                                           */
 191         int max_vars;
 192         int max_vars_with_indices;
 193         int *num_defs;    /* counts definitions of variables     */
 194                           /* [0..cd->maxlocals*5+cd->maxstack*5[ */
 195                           /* valid for [0..ls->max_vars[         */
 196
 197
 198         int *local_0;     /* [0..ls->max_locals]  */
 199                           /* local_0[a] with a in [0..ls->max_locals[ holds the */
 200                           /* index of La,0 */
 201                           /* local_0[ls->maxlocals] holds the number of local   */
 202                           /* vars with indices */
 203         int *interface_0; /* same here, just with interfaces */
 204
 205         int *var_to_index; /* var index to interface (<0) or local (>=0) index */
 206                            /* [0..cd->maxlocals*5+cd->maxstack*5[              */
 207                            /* valid for [0..ls->max_vars[                      */
 208                            /* holds var_index or the negative interface index  */
 209                            /* in ssa_Rename_init the indices are changed to the */
 210                        /* index of the corresponding first Var with index;) */
 211                            /* (== local_0[] or interface_0[] */
 212         int max_locals;
 213         int max_interfaces;
 214
 215         int uses;
 216         int basicblockcount;
 217         basicblock **basicblocks;
 218         /* [0..ls->basicblockcount[[0..ls->max_locals[[0..ls->num_pre[bb]] */
 219         /* 3rd index represents the the var involved in the phi function   */
 220         /* a0 = phi(a1,a2,...,a(ls->num_pre[bb]-1)) */
 221         int ***phi;  /* [0..ls->basicblockcount[[0..ls->max_vars[[0,1] */
 222                      /* if no phi function for a Basic Block and var exists */
 223                      /* phi[bb][a] == NULL */
 224         int *num_phi_moves;
 225         int ***phi_moves; /* phi_moves[block_index][0..num_phi_moves[bi][0..1] */
 226                           /* [][][0] target */
 227                           /* [][][1] source */
 228
 229         int *count;  /* Helpers for ssa_Rename */
 230         int **stack;
 231         int *stack_top;
 232
 233         /* structures for phi var interference graphs */
 234         struct igraph_lookup **igraph_lookup; /* var to igraph index */
 235         int igraph_lookup_top;   /* number of entries in above table */
 236         struct igraph *igraph;   /* interference graphs */
 237         int igraph_top;
 238 };
 239
 240
 241 struct freemem {
 242         int off;
 243         int end;
 244         struct freemem *next;
 245 };
 246
 247 typedef struct lsradata lsradata;
 248
 249 /* function prototypes */
 250 void lsra(jitdata *);
 251 #endif /* _LSRA_H */
 252
 253
 254 /*
 255  * These are local overrides for various environment variables in Emacs.
 256  * Please do not remove this and leave it at the end of the file, where
 257  * Emacs will automagically detect them.
 258  * ---------------------------------------------------------------------
 259  * Local variables:
 260  * mode: c
 261  * indent-tabs-mode: t
 262  * c-basic-offset: 4
 263  * tab-width: 4
 264  * End:
 265  */