src/vm/jit/allocator/lsra.h

   1 /* src/vm/jit/allocator/lsra.h - linear scan register allocator header
   2
   3    Copyright (C) 1996-2005 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 4055 2006-01-02 12:59:54Z christian $
  30
  31 */
  32
  33
  34 #ifndef _LSRA_H
  35 #define _LSRA_H
  36
  37 #include "config.h"
  38
  39 /* #define LSRA_DEBUG */  /* lsra debug messages */
  40 /* #define LSRA_SAVEDVAR */
  41 /* #define LSRA_MEMORY */
  42 /* #define LSRA_PRINTLIFETIMES */
  43 /* #define LSRA_USES_REG_RES */ /* is now in i386/codegen.h */
  44 /*  #define LSRA_TESTLT */
  45 /* #define LSRA_LEAF */
  46 #if defined(__I386__) || defined(__X86_64__)
  47 #define JOIN_DEST_STACK           /* The destination stackslot gets the same  */
  48         /* register as one of the src stackslots. Important for i386 & X86_64 */
  49         /* since they do not have "3 operand" arithmetic instructions to      */
  50         /* prevent usage of a reserved register (REG_ITMPX)                   */
  51 #endif
  52 #define JOIN_DUP_STACK         /* join "identical" stackslots created by dup* */
  53
  54 #define USAGE_COUNT        /* influence LSRA with usagecount */
  55 #define USAGE_PER_INSTR    /* divide usagecount by lifetimelength */
  56
  57 #ifdef LSRA_DEBUG
  58 #undef LSRA_LEAF
  59 #endif
  60
  61 #ifdef LSRA_TESTLT
  62 #define VS 999999
  63 #endif
  64
  65
  66 #ifdef LSRA_DEBUG
  67 #define LSRA_PRINTLIFETIMES
  68 #endif
  69
  70 #define LSRA_BB_IN 3
  71 #define LSRA_BB_OUT 2
  72 #define LSRA_STORE 1
  73 #define LSRA_LOAD 0
  74 #define LSRA_POP -1
  75
  76 /* join types and flags*/
  77 #define JOIN     0 /* joins that are not in any way dangerous                 */
  78 #define JOIN_BB  1 /* join Stackslots over Basic Block Boundaries             */
  79 #define JOIN_DUP 2 /* join of two possibly concurring lifeteimes through DUP* */
  80 #define JOIN_OP  4 /* join of src operand with dst operand on i386 and x86_64 */
  81                    /* architecture                                            */
  82                    /* JOIN_DUP and JOIN_OP is mutually exclusive as JOIN_OP   */
  83                    /* and JOIN_BB                                             */
  84 #define JOINING  8 /* set while joining for DUP or OP to prevent assignement  */
  85                    /* to a REG_RES before all involved lifetimes have been    */
  86                    /* seen completely */
  87
  88 #define min(a,b) ((a)<(b)?(a):(b))
  89 #define max(a,b) ((a)<(b)?(b):(a))
  90
  91 struct _list {
  92         int value;
  93         struct _list *next;
  94 };
  95
  96 struct _backedge {
  97         int start;
  98         int end;
  99         int nesting;
 100         struct _backedge *next;
 101 };
 102
 103 struct lifetime {
 104         int i_start;                /* instruction number of first use */
 105         int i_end;                  /* instruction number of last use */
 106         int v_index;           /* local variable index or negative for stackslots */
 107         int type;                   /* TYPE_XXX or -1 for unused lifetime */
 108         long usagecount;            /* number of references*/
 109         int reg;                    /* regoffset allocated by lsra*/
 110         int savedvar;
 111         int flags;
 112         struct stackslot *local_ss; /* Stackslots for this Lifetime or NULL ( ==  */
 113                                 /* "pure" Local Var) */
 114         int bb_last_use;
 115         int i_last_use;
 116         int bb_first_def;
 117         int i_first_def;
 118 };
 119
 120 struct l_loop {
 121         int b_first;
 122         int b_last;
 123         int nesting;
 124 };
 125
 126 struct b_loop {
 127         int loop;
 128         int instr;
 129 };
 130
 131
 132 struct stackslot {
 133         stackptr s;
 134         int bb;
 135         struct stackslot *next;
 136 };
 137
 138 struct lsra_register {
 139         int *sav_reg;
 140         int *tmp_reg;
 141         int *nregdesc;
 142         int sav_top;
 143         int tmp_top;
 144 };
 145
 146 struct lsra_reg {
 147         int reg_index;
 148         int use;
 149 };
 150
 151 struct _sbr {
 152         int header;          /* BB Index of subroutine start (SBR_HEADER) */
 153         struct _list *ret;   /* List of possible return BB indizes */
 154         struct _sbr *next;
 155 };
 156
 157 struct lsradata {
 158 #if defined(LSRA_USES_REG_RES)
 159         int reg_res_free[REG_RES_CNT];
 160 #endif
 161         struct _list **succ; /* CFG successors*/
 162         struct _list **pred; /* CFG predecessors */
 163         int *num_pred;       /* CFG number of predecessors */
 164         int *sorted;         /* BB sorted in reverse post order */
 165         int *sorted_rev;     /* BB reverse lookup of sorted */
 166
 167         struct _backedge **backedge; /* backedge data structure */
 168         int backedge_count;          /* number of backedges */
 169
 170         struct _sbr sbr;     /* list of subroutines, sorted by header */
 171
 172         long *nesting;    /* Nesting level of BB*/
 173
 174         int maxlifetimes; /* copy from methodinfo to prevent passing methodinfo   */
 175                       /* as parameter */
 176
 177         struct lifetime *lifetime; /* array of lifetimes */
 178         int lifetimecount;         /* number of lifetimes */
 179         int *lt_used;              /* index to lifetimearray for used lifetimes   */
 180         int *lt_int;               /* index to lifetimearray for int lifetimes    */
 181         int lt_int_count;          /* number of int/[lng]/[adr] lifetimes */
 182         int *lt_flt;               /* index to lifetimearray for float lifetimes  */
 183         int lt_flt_count;          /* number of float/double lifetimes */
 184         int *lt_mem;               /* index to lifetimearray for all lifetimes    */
 185                                /* not to be allocated in registers */
 186         int lt_mem_count;          /* number of this other lifetimes */
 187
 188         struct lifetime **active_tmp, **active_sav;
 189         int active_tmp_top, active_sav_top;
 190
 191         struct lsra_exceptiontable *ex;
 192         int v_index;               /* next free index for stack slot lifetimes    */
 193                                    /* decrements from -1 */
 194 };
 195
 196 struct freemem {
 197         int off;
 198         int end;
 199         struct freemem *next;
 200 };
 201
 202 typedef struct lsradata lsradata;
 203
 204 /* function prototypes */
 205 void lsra(methodinfo *, codegendata *, registerdata *,t_inlining_globals *);
 206
 207 #endif /* _LSRA_H */
 208
 209
 210 /*
 211  * These are local overrides for various environment variables in Emacs.
 212  * Please do not remove this and leave it at the end of the file, where
 213  * Emacs will automagically detect them.
 214  * ---------------------------------------------------------------------
 215  * Local variables:
 216  * mode: c
 217  * indent-tabs-mode: t
 218  * c-basic-offset: 4
 219  * tab-width: 4
 220  * End:
 221  */