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