src/vm/jit/loop/loop.h

   1 /* src/vm/jit/loop/loop.h - array bound removal header
   2
   3    Copyright (C) 1996-2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, 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., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    $Id: loop.h 7246 2007-01-29 18:49:05Z twisti $
  26
  27 */
  28
  29
  30 #ifndef _LOOP_H
  31 #define _LOOP_H
  32
  33 #include "config.h"
  34 #include "vm/types.h"
  35
  36 #include "vm/global.h"
  37
  38 #include "vm/jit/jit.h"
  39
  40 #include "vmcore/method.h"
  41
  42
  43 /*      Different types for struct Trace                                                                                */
  44 #define TRACE_UNKNOWN 0                 /* unknown                                                                      */
  45 #define TRACE_ICONST  1                 /* integer constant value                                       */
  46 #define TRACE_ALENGTH 2                 /* array length value                                           */
  47 #define TRACE_IVAR    3                 /* integer variable reference                           */
  48 #define TRACE_AVAR    4                 /* object (array) reference                                     */
  49
  50 /*      The ways a variable can be used in a loop                                                               */
  51 #define ARRAY_INDEX       0                     /* var used as array index                                      */
  52 #define VAR_MOD           1                     /* var changes its value                                        */
  53
  54 /*      The way, integer variables change their values                                                  */
  55 #define D_UP              0                     /* var is only increased                                        */
  56 #define D_DOWN            1                     /* var is only decreased                                        */
  57 #define D_UNKNOWN         2                     /* not known                                                            */
  58
  59 /*      The different types of operators in loop conditions                                             */
  60 #define OP_EQ             0                     /* operator:    ==                                                      */
  61 #define OP_LT         1                 /* operator:    <                                                       */
  62 #define OP_GE         2                 /* operator:    >=                                                      */
  63 #define OP_UNKNOWN        3                     /* operator:    unknown                                         */
  64
  65 /*      Possible types of static tests (constraints) in struct Constraint               */
  66
  67 #define TEST_ZERO                       0       /* check variable against const. lower bound*/
  68 #define TEST_ALENGTH            1       /* check variable against array length          */
  69 #define TEST_CONST_ZERO         2       /* check constant against const. lower bound*/
  70 #define TEST_CONST_ALENGTH      3       /* check variable against array length          */
  71 #define TEST_UNMOD_ZERO         4       /* check var. that is constant in loop against*/
  72                                                                 /* constant lower bound                                         */
  73 #define TEST_UNMOD_ALENGTH      5       /* check var. that is constant in loop against*/
  74                                                                 /* array length                                                         */
  75 #define TEST_RS_ZERO            6       /* check constant part of loop condition against*/
  76                                                                 /* constant lower bound                                                 */
  77 #define TEST_RS_ALENGTH         7       /* check constant part of loop condition against*/
  78                                                                 /* array length                                                                 */
  79
  80 /*      Possible types of bound check optimizations                                                                     */
  81 #define OPT_UNCHECKED   0               /* access not checked yet - first visit                 */
  82 #define OPT_NONE                1               /* no optimization                                                              */
  83 #define OPT_FULL                2               /* fully remove bound check                                             */
  84 #define OPT_LOWER               3               /* remove check againt zero                                             */
  85 #define OPT_UPPER               4               /* remove check against array length                    */
  86
  87 /*      The different ways, remove_boundcheck(.) can be called                                          */
  88 #define BOUNDCHECK_REGULAR      0       /* perform regular optimization                                 */
  89 #define BOUNDCHECK_SPECIAL      1       /* only optimize header node - and ignore               */
  90                                                                 /* information from loop condition                              */
  91
  92 #define LOOP_PART       0x1     /* a flag that marks a BB part of a loop        */
  93 #define HANDLER_PART    0x2     /* a flag that marks a BB part of ex-handler    */
  94 #define HANDLER_VISITED 0x4     /* flag to prevent loop if copying catch blocks */
  95
  96
  97 typedef struct LoopElement LoopElement;
  98 typedef struct LoopContainer LoopContainer;
  99 typedef struct loopdata loopdata;
 100
 101
 102 /*      This struct records information about interesting vars (vars that are modified
 103         or used as an array index in loops.
 104 */
 105 struct LoopVar {
 106         int value;                                      /* reference to array of local variables                */
 107         int modified;                           /* set if value of var is changed                               */
 108         int index;                                      /* set if var is used as array index                    */
 109         int static_l;                           /* var is never decremented -> static lower             */
 110                                                                 /* bound possible                                                               */
 111         int static_u;                           /* var is never incremented -> static upper             */
 112                                                                 /* bound possible                                                               */
 113         int dynamic_l;
 114         int dynamic_l_v;                        /* variable is left side of loop condition in   */
 115                                                                 /* variable + dynamic_l >= right side                   */
 116         int dynamic_u;
 117         int dynamic_u_v;                        /* variable is left side of loop condition in   */
 118                                                                 /* variable + dynamic_u < right side                    */
 119         struct LoopVar *next;           /* list pointer                                                                 */
 120 };
 121
 122
 123 /*      This struct records the needed static test of variables before loop entry.      */
 124 struct Constraint {
 125         int type;                                       /* type of test to perform                                              */
 126         int arrayRef;                           /* array reference involved in test (if any)    */
 127         int varRef;                                     /* which variable to test (if involved)                 */
 128         int constant;                           /* which constant to test (if involved)                 */
 129         struct Constraint *next;        /* list pointer                                                                 */
 130 };
 131
 132
 133 /* This structure is used to record variables that change their value in loops. */
 134 struct Changes {
 135         int var;                                        /* variable involved                                                    */
 136         int lower_bound;                        /* a minimum lower bound that is guaranteed             */
 137         int upper_bound;                        /* a maximum upper bound that is guaranteed             */
 138                                                                 /* IMPORTANT: if lower_bound > upper_bound              */
 139                                                                 /* there are no guarantees at all                               */
 140 };
 141
 142
 143 /*      This struct is used to build the control flow graph and stores the variable
 144         changes at the beginning of each basic block.
 145 */
 146 struct depthElement {
 147         int value;                                      /* number of successor of this block                    */
 148         struct depthElement *next;      /* list pointer                                                                 */
 149         struct Changes **changes;       /* pointer to array of variable changes                 */
 150 };
 151
 152
 153 /*      Used to build a list of all basicblock, the loop consists of              */
 154
 155 struct LoopElement {
 156         s4           node;
 157         basicblock  *block;
 158         LoopElement *next;
 159 };
 160
 161
 162 /*
 163    This structure stores informations about a single loop
 164 */
 165 struct LoopContainer {
 166         s4              toOpt;              /* does this loop need optimization   */
 167         LoopElement    *nodes;              /* list of BBs this loop consists of  */
 168         s4              loop_head;
 169         s4              in_degree;          /* needed to topological sort loops to*/
 170                                             /* get the order of optimizing them   */
 171         LoopContainer  *next;               /* list pointer                       */
 172         LoopContainer  *parent;             /* points to parent loop, if this BB  */
 173                                                                                 /* is head of a loop                  */
 174         LoopContainer  *tree_right;         /* used for tree hierarchie of loops  */
 175         LoopContainer  *tree_down;
 176         exception_entry *exceptions;        /* list of exception in that loop     */
 177 };
 178
 179
 180 struct loopdata {
 181         /* modified by graph.c                                                                                                                  */
 182
 183         int *c_defnum;                                  /* array that stores a number for each node     when*/
 184                                                                 /* control flow graph is traveres depth first   */
 185         int *c_parent;                                  /* for each node that array stores its parent   */
 186         int *c_reverse;                                 /* for each def number that array stores the    */
 187                                                                 /* corresponding node                                                   */
 188         int c_globalCount;                              /* counter for def numbering                                    */
 189         int *c_numPre;                                  /* array that stores for each node its number   */
 190                                                                 /* predecessors                                                                 */
 191         int **c_pre;                                    /* array of array that stores predecessors              */
 192         int c_last_jump;                                /* stores the source node of the last jsr instr */
 193         struct basicblock *c_last_target;      /* stores the source BB of the last jsr instr    */
 194
 195         struct depthElement **c_dTable; /* adjacency list for control flow graph                */
 196         struct depthElement **c_exceptionGraph; /* adjacency list for exception graph   */
 197
 198         struct LoopContainer *c_allLoops;               /* list of all loops                                    */
 199         struct LoopContainer *c_loop_root;              /* root of loop hierarchie tree                 */
 200
 201         int *c_exceptionVisit;                  /* array that stores a flag for each node part  */
 202                                                                 /* of the exception graph                                               */
 203
 204         /* modified by loop.c                                                                                                                   */
 205
 206         int *c_semi_dom;                                /* store for each node its semi dominator               */
 207         int *c_idom;                                    /* store for each node its dominator                    */
 208         int *c_same_dom;                                /* temp array to hold nodes with same dominator */
 209         int *c_ancestor;                                /* store for each node its ancestor with lowest */
 210                                                                 /* semi dominator                                                               */
 211         int *c_numBucket;
 212         int **c_bucket;
 213
 214         int *c_contains;                                /* store for each node whether it's part of loop*/
 215         int *c_stack;                                   /* a simple stack as array                                              */
 216         int c_stackPointer;                             /* stackpointer                                                                 */
 217
 218
 219         /* modified by analyze.c                                                                                                                */
 220
 221         struct LoopContainer *root;     /* the root pointer for the hierarchie tree of  */
 222                                     /* all loops in that procedure                  */
 223
 224         int c_needed_instr;                             /* number of instructions that have to be               */
 225                                                                 /* inserted before loop header to make sure             */
 226                                                                 /* array optimization is legal                                  */
 227         int c_rs_needed_instr;                  /* number of instructions needed to load the    */
 228                                                                 /* value ofthe right side of the loop condition */
 229         int *c_nestedLoops;                             /* store for each node the header node of the   */
 230                                                                 /* loop this node belongs to, -1 for none               */
 231         int *c_hierarchie;              /* store a loop hierarchie                      */
 232         int *c_toVisit;                                 /* set for each node that is part of the loop   */
 233
 234         int *c_current_loop;                    /* for each node:                               */
 235                                                                 /* store 0:     node is not part of loop                        */
 236                                                                 /* store 1:     node is loop header                                     */
 237                                                                 /* store 2:     node is in loop but not part of any     */
 238                                                                 /*                      nested loop                         */
 239                                                                 /* store 3:     node is part of nested loop                     */
 240
 241         int c_current_head;                             /* store number of node that is header of loop  */
 242         int *c_var_modified;                    /* store for each local variable whether its    */
 243                                                                 /* value is changed in the loop                                 */
 244
 245         struct Trace *c_rightside;              /* right side of loop condition                                 */
 246         struct Constraint **c_constraints;
 247                                                                 /* array that stores for each variable a list   */
 248                                                                 /* static tests (constraints) that have to be   */
 249                                                                 /* performed before loop entry                                  */
 250                                                                 /* IMPORTANT: c_constraints[maxlocals] stores   */
 251                                                                 /*                        the tests for constants and the       */
 252                                                                 /*                        right side of loop condition          */
 253
 254         struct LoopVar *c_loopvars;             /* a list of all intersting variables of the    */
 255                                                                 /* current loop (variables that are modified or */
 256                                                                 /* used as array index                                                  */
 257
 258         struct basicblock *c_first_block_copied; /* pointer to the first block, that is copied */
 259                                     /* during loop duplication                    */
 260
 261         struct basicblock *c_last_block_copied;  /* last block, that is copied during loop     */
 262                                     /* duplication                                */
 263
 264         int *c_null_check;              /* array to store for local vars, whether they  */
 265                                     /* need to be checked against the null reference*/
 266                                     /* in the loop head                             */
 267
 268         bool c_needs_redirection;       /* if a loop header is inserted as first block  */
 269                                     /* into the global BB list, this is set to true */
 270
 271         struct basicblock *c_newstart;         /* if a loop header is inserted as first block  */
 272                                     /* into the gloal BB list, this pointer is the  */
 273                                     /* new start                                    */
 274         int c_old_xtablelength;         /* used to store the original tablelength       */
 275
 276         /* set debug mode                                                                                                                               */
 277 #define C_DEBUG
 278
 279
 280         /* declare statistic variables                                                                                                  */
 281 #ifdef ENABLE_STATISTICS
 282
 283         int c_stat_num_loops;                   /* number of loops                                                              */
 284
 285         /* statistics per loop                                                                                                                  */
 286         int c_stat_array_accesses;              /* number of array accesses                                             */
 287
 288         int c_stat_full_opt;                    /* number of fully optimized accesses                   */
 289         int c_stat_no_opt;                              /* number of not optimized accesses                             */
 290         int c_stat_lower_opt;                   /* number of accesses where check against zero  */
 291                                                                 /* is removed                                                                   */
 292         int c_stat_upper_opt;                   /* number of accesses where check against array */
 293                                                                 /* lengh is removed                                                             */
 294         int c_stat_or;                                  /* set if optimization is cancelled because of  */
 295                                                                 /* or in loop condition                                                 */
 296         int c_stat_exception;                   /* set if optimization is cancelled because of  */
 297                                                                 /* index var modified in catch block                    */
 298
 299         /* statistics per procedure                                                                                                             */
 300         int c_stat_sum_accesses;                /* number of array accesses                                             */
 301
 302         int c_stat_sum_full;                    /* number of fully optimized accesses                   */
 303         int c_stat_sum_no;                              /* number of not optimized accesses                             */
 304         int c_stat_sum_lower;                   /* number of accesses where check against zero  */
 305                                                                 /* is removed                                                                   */
 306         int c_stat_sum_upper;                   /* number of accesses where check against array */
 307                                                                 /* lengh is removed                                                             */
 308         int c_stat_sum_or;                              /* set if optimization is cancelled because of  */
 309                                                                 /* or in loop condition                                                 */
 310         int c_stat_sum_exception;               /* set if optimization is cancelled because of  */
 311
 312 #endif
 313 };
 314
 315
 316 /* function prototypes ********************************************************/
 317
 318 void analyseGraph(jitdata *jd);
 319 void c_mem_error(void);
 320
 321 #endif /* _LOOP_H */
 322
 323
 324 /*
 325  * These are local overrides for various environment variables in Emacs.
 326  * Please do not remove this and leave it at the end of the file, where
 327  * Emacs will automagically detect them.
 328  * ---------------------------------------------------------------------
 329  * Local variables:
 330  * mode: c
 331  * indent-tabs-mode: t
 332  * c-basic-offset: 4
 333  * tab-width: 4
 334  * End:
 335  */