src/vm/jit/loop/loop.h

   1 /* jit/loop/loop.h - array bound removal header
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   4    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
   5    M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
   6    P. Tomsich, J. Wenninger
   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    $Id: loop.h 665 2003-11-21 18:36:43Z jowenn $
  30
  31 */
  32
  33
  34 #ifndef _LOOP_H
  35 #define _LOOP_H
  36
  37 #include "global.h"
  38
  39 /*      Different types for struct Trace                                                                                */
  40 #define TRACE_UNKNOWN 0                 /* unknown                                                                      */
  41 #define TRACE_ICONST  1                 /* integer constant value                                       */
  42 #define TRACE_ALENGTH 2                 /* array length value                                           */
  43 #define TRACE_IVAR    3                 /* integer variable reference                           */
  44 #define TRACE_AVAR    4                 /* object (array) reference                                     */
  45
  46 /*      The ways a variable can be used in a loop                                                               */
  47 #define ARRAY_INDEX       0                     /* var used as array index                                      */
  48 #define VAR_MOD           1                     /* var changes its value                                        */
  49
  50 /*      The way, integer variables change their values                                                  */
  51 #define D_UP              0                     /* var is only increased                                        */
  52 #define D_DOWN            1                     /* var is only decreased                                        */
  53 #define D_UNKNOWN         2                     /* not known                                                            */
  54
  55 /*      The different types of operators in loop conditions                                             */
  56 #define OP_EQ             0                     /* operator:    ==                                                      */
  57 #define OP_LT         1                 /* operator:    <                                                       */
  58 #define OP_GE         2                 /* operator:    >=                                                      */
  59 #define OP_UNKNOWN        3                     /* operator:    unknown                                         */
  60
  61 /*      Possible types of static tests (constraints) in struct Constraint               */
  62
  63 #define TEST_ZERO                       0       /* check variable against const. lower bound*/
  64 #define TEST_ALENGTH            1       /* check variable against array length          */
  65 #define TEST_CONST_ZERO         2       /* check constant against const. lower bound*/
  66 #define TEST_CONST_ALENGTH      3       /* check variable against array length          */
  67 #define TEST_UNMOD_ZERO         4       /* check var. that is constant in loop against*/
  68                                                                 /* constant lower bound                                         */
  69 #define TEST_UNMOD_ALENGTH      5       /* check var. that is constant in loop against*/
  70                                                                 /* array length                                                         */
  71 #define TEST_RS_ZERO            6       /* check constant part of loop condition against*/
  72                                                                 /* constant lower bound                                                 */
  73 #define TEST_RS_ALENGTH         7       /* check constant part of loop condition against*/
  74                                                                 /* array length                                                                 */
  75
  76 /*      Possible types of bound check optimizations                                                                     */
  77 #define OPT_UNCHECKED   0               /* access not checked yet - first visit                 */
  78 #define OPT_NONE                1               /* no optimization                                                              */
  79 #define OPT_FULL                2               /* fully remove bound check                                             */
  80 #define OPT_LOWER               3               /* remove check againt zero                                             */
  81 #define OPT_UPPER               4               /* remove check against array length                    */
  82
  83 /*      The different ways, remove_boundcheck(.) can be called                                          */
  84 #define BOUNDCHECK_REGULAR      0       /* perform regular optimization                                 */
  85 #define BOUNDCHECK_SPECIAL      1       /* only optimize header node - and ignore               */
  86                                                                 /* information from loop condition                              */
  87
  88 #define LOOP_PART       0x1     /* a flag that marks a BB part of a loop        */
  89 #define HANDLER_PART    0x2     /* a flag that marks a BB part of ex-handler    */
  90 #define HANDLER_VISITED 0x4     /* flag to prevent loop if copying catch blocks */
  91
  92
  93
  94 /*      This struct records information about interesting vars (vars that are modified
  95         or used as an array index in loops.
  96 */
  97 struct LoopVar {
  98         int value;                                      /* reference to array of local variables                */
  99         int modified;                           /* set if value of var is changed                               */
 100         int index;                                      /* set if var is used as array index                    */
 101         int static_l;                           /* var is never decremented -> static lower             */
 102                                                                 /* bound possible                                                               */
 103         int static_u;                           /* var is never incremented -> static upper             */
 104                                                                 /* bound possible                                                               */
 105         int dynamic_l;
 106         int dynamic_l_v;                        /* variable is left side of loop condition in   */
 107                                                                 /* variable + dynamic_l >= right side                   */
 108         int dynamic_u;
 109         int dynamic_u_v;                        /* variable is left side of loop condition in   */
 110                                                                 /* variable + dynamic_u < right side                    */
 111         struct LoopVar *next;           /* list pointer                                                                 */
 112 };
 113
 114
 115 /*      This struct records the needed static test of variables before loop entry.      */
 116 struct Constraint {
 117         int type;                                       /* type of test to perform                                              */
 118         int arrayRef;                           /* array reference involved in test (if any)    */
 119         int varRef;                                     /* which variable to test (if involved)                 */
 120         int constant;                           /* which constant to test (if involved)                 */
 121         struct Constraint *next;        /* list pointer                                                                 */
 122 };
 123
 124
 125 /* This structure is used to record variables that change their value in loops. */
 126 struct Changes {
 127         int var;                                        /* variable involved                                                    */
 128         int lower_bound;                        /* a minimum lower bound that is guaranteed             */
 129         int upper_bound;                        /* a maximum upper bound that is guaranteed             */
 130                                                                 /* IMPORTANT: if lower_bound > upper_bound              */
 131                                                                 /* there are no guarantees at all                               */
 132 };
 133
 134
 135 /*      This struct is used to build the control flow graph and stores the variable
 136         changes at the beginning of each basic block.
 137 */
 138 struct depthElement {
 139         int value;                                      /* number of successor of this block                    */
 140         struct depthElement *next;      /* list pointer                                                                 */
 141         struct Changes **changes;       /* pointer to array of variable changes                 */
 142 };
 143
 144
 145 /*      Used to build a list of all basicblock, the loop consists of
 146 */
 147 struct LoopElement {
 148         int node;
 149         struct basicblock       *block;
 150         struct LoopElement *next;
 151 };
 152
 153
 154 /*
 155    This structure stores informations about a single loop
 156 */
 157 struct LoopContainer {
 158         int toOpt;                                                      /* does this loop need optimization             */
 159         struct LoopElement *nodes;          /* list of BBs this loop consists of    */
 160         int loop_head;
 161         int in_degree;                      /* needed to topological sort loops to  */
 162                                             /* get the order of optimizing them     */
 163         struct LoopContainer *next;                     /* list pointer                                                 */
 164         struct LoopContainer *parent;           /* points to parent loop, if this BB    */
 165                                                                                 /* is head of a loop                                    */
 166         struct LoopContainer *tree_right;   /* used for tree hierarchie of loops    */
 167         struct LoopContainer *tree_down;
 168         xtable *exceptions;                 /* list of exception in that loop       */
 169 };
 170
 171
 172 /* global variables */
 173 extern int c_debug_nr;
 174 extern int *c_defnum;
 175 extern int *c_parent;
 176 extern int *c_reverse;
 177 extern int c_globalCount;
 178 extern int *c_numPre;
 179 extern int **c_pre;
 180 extern int c_last_jump;
 181 extern struct basicblock *c_last_target;
 182 extern struct depthElement **c_dTable;
 183 extern struct depthElement **c_exceptionGraph;
 184 extern struct LoopContainer *c_allLoops;
 185 extern struct LoopContainer *c_loop_root;
 186 extern int *c_exceptionVisit;
 187
 188
 189 /* global loop variables */
 190 extern int *c_semi_dom;
 191 extern int *c_idom;
 192 extern int *c_same_dom;
 193 extern int *c_ancestor;
 194 extern int *c_numBucket;
 195 extern int **c_bucket;
 196 extern int *c_contains;
 197 extern int *c_stack;
 198 extern int c_stackPointer;
 199
 200
 201 /* global analyze variables     */
 202 extern struct LoopContainer *root;
 203 extern int c_needed_instr;
 204 extern int c_rs_needed_instr;
 205 extern int *c_nestedLoops;
 206 extern int *c_hierarchie;
 207 extern int *c_toVisit;
 208 extern int *c_current_loop;
 209 extern int c_current_head;
 210 extern int *c_var_modified;
 211 extern struct Trace *c_rightside;
 212 extern struct Constraint **c_constraints;
 213 extern struct LoopVar *c_loopvars;
 214 extern struct basicblock *c_first_block_copied;
 215 extern struct basicblock *c_last_block_copied;
 216 extern int *c_null_check;
 217 extern bool c_needs_redirection;
 218 extern struct basicblock *c_newstart;
 219 extern int c_old_xtablelength;
 220
 221
 222 /* global statistic variables */
 223 #ifdef STATISTICS
 224
 225 extern int c_stat_num_loops;
 226 extern int c_stat_array_accesses;
 227 extern int c_stat_full_opt;
 228 extern int c_stat_no_opt;
 229 extern int c_stat_lower_opt;
 230 extern int c_stat_upper_opt;
 231 extern int c_stat_or;
 232 extern int c_stat_exception;
 233 extern int c_stat_sum_accesses;
 234 extern int c_stat_sum_full;
 235 extern int c_stat_sum_no;
 236 extern int c_stat_sum_lower;
 237 extern int c_stat_sum_upper;
 238 extern int c_stat_sum_or;
 239 extern int c_stat_sum_exception;
 240
 241 #endif
 242
 243
 244 /* function prototypes */
 245 void analyseGraph();
 246 void c_mem_error();
 247
 248 #endif /* _LOOP_H */
 249
 250
 251 /*
 252  * These are local overrides for various environment variables in Emacs.
 253  * Please do not remove this and leave it at the end of the file, where
 254  * Emacs will automagically detect them.
 255  * ---------------------------------------------------------------------
 256  * Local variables:
 257  * mode: c
 258  * indent-tabs-mode: t
 259  * c-basic-offset: 4
 260  * tab-width: 4
 261  * End:
 262  */
 263