narray/loop.h

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