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