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