src/vm/jit/loop/loop.h

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