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 _backedge {
  72         int start;
  73         int end;
  74         int nesting;
  75         struct _backedge *next;
  76 };
  77
  78 struct site {
  79         int b_index;
  80         int iindex;
  81         struct site *next;
  82 };
  83
  84 struct lifetime {
  85         int i_start;                /* instruction number of first use */
  86         int i_end;                  /* instruction number of last use */
  87         int v_index;           /* local variable index or negative for stackslots */
  88         int type;                   /* TYPE_XXX or -1 for unused lifetime */
  89         long usagecount;            /* number of references*/
  90         int regoff;                    /* regoffset allocated by lsra*/
  91         int savedvar;
  92         int flags;
  93         /* struct stackslot *local_ss; */ /* Stackslots for this Lifetime or NULL ( ==  */
  94                                 /* "pure" Local Var) */
  95         int bb_last_use;
  96         int i_last_use;
  97         int bb_first_def;
  98         int i_first_def;
  99
 100         struct site *def;
 101         struct site *use;
 102         struct site *last_use;
 103 };
 104
 105 struct l_loop {
 106         int b_first;
 107         int b_last;
 108         int nesting;
 109 };
 110
 111 /*
 112 struct stackslot {
 113         stackptr s;
 114         int bb;
 115         struct stackslot *next;
 116 };
 117 */
 118
 119 struct lsra_register {
 120         int *sav_reg;
 121         int *tmp_reg;
 122         int *nregdesc;
 123         int sav_top;
 124         int tmp_top;
 125 };
 126
 127 struct lsra_reg {
 128         int reg_index;
 129         int use;
 130 };
 131
 132 struct igraph_lookup {
 133         int var;
 134         int igraph;
 135 };
 136
 137 struct igraph_interference {
 138         int v1;
 139         int v2;
 140         struct igraph_interference *next;
 141 };
 142
 143 struct igraph_vars {
 144         int v;
 145         struct igraph_vars *next;
 146 };
 147
 148 struct igraph {
 149         struct igraph_interference *inter;
 150         struct igraph_vars *vars;
 151 };
 152
 153
 154 struct lsradata {
 155         /* int *var; */           /* unused entries are set to UNUSED    */
 156                             /* maps to jd->vars array */
 157         int varcount;       /* size of vars array */
 158         int ssavarcount;    /* ls->vars[0..ssavarcount[ are all locals and iovars */
 159                             /* they are regarded for ssa renaming */
 160                             /* the rest (ls->vars[ssavarcount..varcount[ are      */
 161                             /* TEMP or PREALLOC vars with just on definition and  */
 162                             /* use within one basicblock -> not of interest for   */
 163                             /* ssa renaming procedures */
 164         int vartop;         /* next free var */
 165         int varcount_with_indices;
 166         int *new_varindex;  /* new_varindex[0..jd->varcount[ points to the new    */
 167                             /* unique index of ls->vars(maps jd->vars to ls->vars)*/
 168
 169         int *var_0;        /* [0..ls->varcount]  */
 170                            /* var_0[a] with a in [0..ls->varcount[ holds the */
 171                            /* index of La,0 */
 172                            /* var_0[ls->varcount] holds the number of vars with */
 173                            /*indices */
 174
 175         int *sorted;         /* BB sorted in reverse post order */
 176         int *sorted_rev;     /* BB reverse lookup of sorted */
 177
 178         struct _backedge **backedge; /* backedge data structure */
 179         int backedge_count;          /* number of backedges */
 180
 181         long *nesting;    /* Nesting level of BB*/
 182
 183         struct lifetime *lifetime; /* array of lifetimes */
 184         int lifetimecount;         /* number of lifetimes */
 185         int *lt_used;              /* index to lifetimearray for used lifetimes   */
 186         int *lt_int;               /* index to lifetimearray for int lifetimes    */
 187         int lt_int_count;          /* number of int/[lng]/[adr] lifetimes */
 188         int *lt_flt;               /* index to lifetimearray for float lifetimes  */
 189         int lt_flt_count;          /* number of float/double lifetimes */
 190         int *lt_mem;               /* index to lifetimearray for all lifetimes    */
 191                                /* not to be allocated in registers */
 192         int lt_mem_count;          /* number of this other lifetimes */
 193
 194         struct lifetime **active_tmp, **active_sav;
 195         int active_tmp_top, active_sav_top;
 196
 197         struct lsra_exceptiontable *ex;
 198         int v_index;               /* next free index for stack slot lifetimes    */
 199                                    /* decrements from -1 */
 200
 201         /* SSA fields */
 202         bitvector *var_def; /* LocalVar Definition Bitvector [0..ls->bbcount]  */
 203                             /* Bitvector holds ls->max_vars Bits               */
 204         bitvector *use_sites; /* LocalVar Use Bitvector[0..ls->maxvars] */
 205         int **num_var_use; /* count of var_use[bb][var_index] */
 206         int **var; /* [0..cd->maxlocal+cd->maxstack[[0..4] */
 207         /* ssa_set_local_def and ssa_set_interface (called from analyse_stack)    */
 208         /* set var[local_index][local_type] and var[jd->maxlocals+stack_depth]    */
 209         /* [stack_type] to a unique type independend index [0..ls->max_vars[      */
 210         /* unused entries are set to -1                                           */
 211         int max_vars;
 212         int max_vars_with_indices;
 213         int *num_defs;    /* counts definitions of variables     */
 214                           /* [0..jd->maxlocals*5+cd->maxstack*5[ */
 215                           /* valid for [0..ls->max_vars[         */
 216
 217
 218         int *local_0;     /* [0..ls->max_locals]  */
 219                           /* local_0[a] with a in [0..ls->max_locals[ holds the */
 220                           /* index of La,0 */
 221                           /* local_0[ls->maxlocals] holds the number of local   */
 222                           /* vars with indices */
 223         int *interface_0; /* same here, just with interfaces */
 224
 225         int *var_to_index; /* var index to interface (<0) or local (>=0) index */
 226                            /* [0..jd->maxlocals*5+cd->maxstack*5[              */
 227                            /* valid for [0..ls->max_vars[                      */
 228                            /* holds var_index or the negative interface index  */
 229                            /* in ssa_Rename_init the indices are changed to the */
 230                        /* index of the corresponding first Var with index;) */
 231                            /* (== local_0[] or interface_0[] */
 232         int max_locals;
 233         int max_interfaces;
 234
 235         int uses;
 236         int basicblockcount;
 237         basicblock **basicblocks;
 238         /* [0..ls->basicblockcount[[0..ls->max_locals[[0..ls->num_pre[bb]] */
 239         /* 3rd index represents the the var involved in the phi function   */
 240         /* a0 = phi(a1,a2,...,a(ls->num_pre[bb]-1)) */
 241         int ***phi;  /* [0..ls->basicblockcount[[0..ls->max_vars[[0,1] */
 242                      /* if no phi function for a Basic Block and var exists */
 243                      /* phi[bb][a] == NULL */
 244         int *num_phi_moves;
 245         int ***phi_moves; /* phi_moves[block_index][0..num_phi_moves[bi][0..1] */
 246                           /* [][][0] target */
 247                           /* [][][1] source */
 248
 249         int *count;  /* Helpers for ssa_Rename */
 250         int **stack;
 251         int *stack_top;
 252
 253         /* structures for phi var interference graphs */
 254         struct igraph_lookup **igraph_lookup; /* var to igraph index */
 255         int igraph_lookup_top;   /* number of entries in above table */
 256         struct igraph *igraph;   /* interference graphs */
 257         int igraph_top;
 258 };
 259
 260
 261 struct freemem {
 262         int off;
 263         int end;
 264         struct freemem *next;
 265 };
 266
 267 typedef struct lsradata lsradata;
 268
 269 /* function prototypes */
 270 void lsra(jitdata *);
 271 #endif /* _LSRA_H */
 272
 273
 274 /*
 275  * These are local overrides for various environment variables in Emacs.
 276  * Please do not remove this and leave it at the end of the file, where
 277  * Emacs will automagically detect them.
 278  * ---------------------------------------------------------------------
 279  * Local variables:
 280  * mode: c
 281  * indent-tabs-mode: t
 282  * c-basic-offset: 4
 283  * tab-width: 4
 284  * End:
 285  */