jit/lsra.h

   1 /* jit/lsra.inc - linear scan register allocator header
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
   4    Institut f. Computersprachen, TU Wien
   5    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser, M. Probst,
   6    S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich,
   7    J. Wenninger, C. Ullrich
   8
   9    This file is part of CACAO.
  10
  11    This program is free software; you can redistribute it and/or
  12    modify it under the terms of the GNU General Public License as
  13    published by the Free Software Foundation; either version 2, or (at
  14    your option) any later version.
  15
  16    This program is distributed in the hope that it will be useful, but
  17    WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19    General Public License for more details.
  20
  21    You should have received a copy of the GNU General Public License
  22    along with this program; if not, write to the Free Software
  23    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  24    02111-1307, USA.
  25
  26    Contact: cacao@complang.tuwien.ac.at
  27
  28    Authors: Christian Ullrich
  29
  30    $Id: lsra.h 1590 2004-11-25 13:24:49Z christian $
  31
  32 */
  33
  34
  35 #ifndef _LSRA_H
  36 #define _LSRA_H
  37
  38 #include "loop/loop.h"
  39
  40 #define LSRA_STORE 1
  41 #define LSRA_LOAD 0
  42 #define LSRA_POP -1
  43
  44 struct lifetime {
  45         int   index; /* unique index, LOCALVAR varnum or negative*/
  46         int   b_start; /* bb of first use */
  47         int   b_end;   /* bb of last use */
  48         int i_start; /* instruction number of first use */
  49         int i_end; /* instruction number of last use */
  50         int length; /* lifetime in instructions */
  51         stackptr s; /* stackslot or NULL */
  52         int v_index; /* local variable index or -1 */
  53         int type;
  54         int usagecount; /* number of refernces*/
  55         int reg; /* regoffset durch lsra zugewiesen */
  56         int savedvar;
  57         struct stackslot *passthrough; /* List of Stackslots in Lifetime, which are passed through a Basic Block */
  58         struct stackslot *local_ss;
  59         struct _i_list *i_list; /* list of instructions with references to var */
  60         struct lifetime *next;
  61 };
  62
  63 /* struct int_list { */
  64 /*      int value; */
  65 /*      int_list *next; */
  66 /* }; */
  67
  68 struct active_lt {
  69         struct lifetime *lt;
  70         struct active_lt *next;
  71 };
  72
  73 struct l_loop {
  74         int b_first;
  75         int b_last;
  76         int nesting;
  77 };
  78
  79 struct b_loop {
  80         int loop;
  81         int instr;
  82 };
  83
  84 struct _i_list {
  85         int b_index;
  86         int instr;
  87         int store;
  88         struct _i_list *next;
  89 };
  90
  91 struct stackslot {
  92         stackptr s;
  93         int bb;
  94         struct stackslot *next;
  95 };
  96
  97 struct lsra_reg {
  98         int reg_index;
  99         int use;
 100 };
 101
 102 struct lsradata {
 103         struct lifetime **ss_lifetimes;
 104         struct lifetime **locals_lifetimes;
 105         struct lifetime *lifetimes;
 106         struct stackslot *stackslots;
 107         struct active_lt *active_tmp, *active_sav;
 108         int active_sav_count, active_tmp_count;
 109         int var_index;
 110         bool back_edge_panic;
 111 };
 112
 113 struct freemem {
 114         int off;
 115         int end;
 116         struct freemem *next;
 117 };
 118
 119 struct sss {
 120         int bb;
 121         bool out;
 122         struct sss *next;
 123 };
 124
 125 typedef struct lsradata lsradata;
 126
 127 /* function prototypes */
 128 void lsra(methodinfo *, codegendata *, registerdata *, loopdata *, t_inlining_globals *);
 129 void lsra_init(methodinfo *, codegendata *, t_inlining_globals *, lsradata *);
 130 void lsra_setup(methodinfo *, codegendata *, registerdata *, lsradata *, loopdata *);
 131 void lsra_clean_Graph( methodinfo *, codegendata *, lsradata *, loopdata *);
 132
 133 #ifdef LSRA_DEBUG
 134 void lsra_dump_Graph(methodinfo *, struct depthElement **);
 135 void lsra_dump_stack(stackptr );
 136 void print_lifetimes(registerdata *, struct lifetime *);
 137 #endif
 138
 139 int lsra_get_sbr_end(methodinfo *, loopdata *, int , int *);
 140 void lsra_scan_registers_canditates(methodinfo *, lsradata *);
 141 void lsra_join_lifetimes( methodinfo *, codegendata *, lsradata *, loopdata *);
 142 int lsra_getmaxblock(methodinfo *, loopdata *, int );
 143 void lsra_calc_lifetime_length(methodinfo *, lsradata *, codegendata *, loopdata *);
 144
 145 void lsra_merge_i_lists(struct lifetime *, struct lifetime *);
 146
 147 void _lsra_new_stack( lsradata *, stackptr , int , int , int);
 148 void _lsra_from_stack(lsradata *, stackptr , int , int, int);
 149 void lsra_add_ss(struct lifetime *, stackptr );
 150 void lsra_usage_local(lsradata *, s4 , int , int , int , int );
 151 void lsra_new_local(lsradata *, s4 , int );
 152 struct _i_list *lsra_add_i_list(struct _i_list *, int, int ,int );
 153
 154 void lsra_sort_lt(struct lifetime **);
 155 void lsra_main(methodinfo *, lsradata *, registerdata *);
 156 void _lsra_main( methodinfo *, lsradata *, struct lifetime *, struct lsra_reg *, int , int , int *, int *);
 157 void lsra_expire_old_intervalls(lsradata *, struct lifetime *, struct lsra_reg *);
 158 void _lsra_expire_old_intervalls(struct lifetime *, struct lsra_reg *, struct active_lt **, int *);
 159 void spill_at_intervall(lsradata *, struct lifetime *);
 160 void _spill_at_intervall(struct lifetime *, struct active_lt **, int *);
 161 void lsra_add_active(struct lifetime *, struct active_lt **, int *);
 162 void lsra_alloc(methodinfo *, registerdata *, struct lifetime *, int *);
 163 int lsra_getmem(struct lifetime *, struct freemem *, int *);
 164 struct freemem *lsra_getnewmem(int *);
 165 void lsra_align_stackslots(struct lsradata *, stackptr, stackptr);
 166 void lsra_setflags(int *, int);
 167 #endif /* _LSRA_H */
 168
 169
 170 /*
 171  * These are local overrides for various environment variables in Emacs.
 172  * Please do not remove this and leave it at the end of the file, where
 173  * Emacs will automagically detect them.
 174  * ---------------------------------------------------------------------
 175  * Local variables:
 176  * mode: c
 177  * indent-tabs-mode: t
 178  * c-basic-offset: 4
 179  * tab-width: 4
 180  * End:
 181  */