mono/mini/abcremoval.h

   1 /**
   2  * \file
   3  * Array bounds check removal
   4  *
   5  * Author:
   6  *   Massimiliano Mantione (massi@ximian.com)
   7  *
   8  * (C) 2004 Ximian, Inc.  http://www.ximian.com
   9  */
  10
  11 #ifndef __MONO_ABCREMOVAL_H__
  12 #define __MONO_ABCREMOVAL_H__
  13
  14 #include <limits.h>
  15
  16 #include "mini.h"
  17
  18
  19 /**
  20  * All handled value types (expressions) in variable definitions and branch
  21  * contitions:
  22  * ANY: not handled
  23  * CONSTANT: an integer constant
  24  * VARIABLE: a reference to a variable, with an optional delta (can be zero)
  25  * PHI: a PHI definition of the SSA representation
  26  */
  27 typedef enum {
  28         MONO_ANY_SUMMARIZED_VALUE,
  29         MONO_CONSTANT_SUMMARIZED_VALUE,
  30         MONO_VARIABLE_SUMMARIZED_VALUE,
  31         MONO_PHI_SUMMARIZED_VALUE
  32 } MonoSummarizedValueType;
  33
  34 /**
  35  * A MONO_CONSTANT_SUMMARIZED_VALUE value.
  36  * value: the value
  37  */
  38 typedef struct MonoSummarizedConstantValue {
  39         int value;
  40 } MonoSummarizedConstantValue;
  41
  42 /**
  43  * A MONO_VARIABLE_SUMMARIZED_VALUE value
  44  * variable: the variable index in the cfg
  45  * delta: the delta (can be zero)
  46  */
  47 typedef struct MonoSummarizedVariableValue {
  48         int variable;
  49         int delta;
  50 } MonoSummarizedVariableValue;
  51
  52 /**
  53  * A MONO_PHI_SUMMARIZED_VALUE value.
  54  * number_of_alternatives: the number of alternatives in the PHI definition
  55  * phi_alternatives: an array of integers with the indexes of the variables
  56  *                   which are the alternatives in this PHI definition
  57  */
  58 typedef struct MonoSummarizedPhiValue {
  59         int number_of_alternatives;
  60         int *phi_alternatives;
  61 } MonoSummarizedPhiValue;
  62
  63 /**
  64  * A summarized value.
  65  * In practice it is a "tagged union".
  66  */
  67 typedef struct MonoSummarizedValue {
  68         MonoSummarizedValueType type;
  69         union {
  70                 MonoSummarizedConstantValue constant;
  71                 MonoSummarizedVariableValue variable;
  72                 MonoSummarizedPhiValue phi;
  73         } value;
  74 } MonoSummarizedValue;
  75
  76 /**
  77  * A "relation" between two values.
  78  * The enumeration is used as a bit field, with three significant bits.
  79  * The degenerated cases are meaningful:
  80  * MONO_ANY_RELATION: we know nothing of this relation
  81  * MONO_NO_RELATION: no relation is possible (this code is unreachable)
  82  */
  83 typedef enum {
  84         MONO_EQ_RELATION = 1,
  85         MONO_LT_RELATION = 2,
  86         MONO_GT_RELATION = 4,
  87         MONO_NE_RELATION = (MONO_LT_RELATION|MONO_GT_RELATION),
  88         MONO_LE_RELATION = (MONO_LT_RELATION|MONO_EQ_RELATION),
  89         MONO_GE_RELATION = (MONO_GT_RELATION|MONO_EQ_RELATION),
  90         MONO_ANY_RELATION = (MONO_EQ_RELATION|MONO_LT_RELATION|MONO_GT_RELATION),
  91         MONO_NO_RELATION = 0
  92 } MonoValueRelation;
  93
  94 /**
  95  * A "kind" of integer value.
  96  * The enumeration is used as a bit field, with two fields.
  97  * The first, four bits wide, is the "sizeof" in bytes.
  98  * The second is a flag that is true if the value is unsigned.
  99  */
 100 typedef enum {
 101         MONO_INTEGER_VALUE_SIZE_1 = 1,
 102         MONO_INTEGER_VALUE_SIZE_2 = 2,
 103         MONO_INTEGER_VALUE_SIZE_4 = 4,
 104         MONO_INTEGER_VALUE_SIZE_8 = 8,
 105         MONO_INTEGER_VALUE_SIZE_BITMASK = 15,
 106         MONO_UNSIGNED_VALUE_FLAG = 16,
 107         MONO_UNSIGNED_INTEGER_VALUE_SIZE_1 = MONO_UNSIGNED_VALUE_FLAG|MONO_INTEGER_VALUE_SIZE_1,
 108         MONO_UNSIGNED_INTEGER_VALUE_SIZE_2 = MONO_UNSIGNED_VALUE_FLAG|MONO_INTEGER_VALUE_SIZE_2,
 109         MONO_UNSIGNED_INTEGER_VALUE_SIZE_4 = MONO_UNSIGNED_VALUE_FLAG|MONO_INTEGER_VALUE_SIZE_4,
 110         MONO_UNSIGNED_INTEGER_VALUE_SIZE_8 = MONO_UNSIGNED_VALUE_FLAG|MONO_INTEGER_VALUE_SIZE_8,
 111         MONO_UNKNOWN_INTEGER_VALUE = 0
 112 } MonoIntegerValueKind;
 113
 114 /**
 115  * A relation between variables (or a variable and a constant).
 116  * The first variable (the one "on the left of the expression") is implicit.
 117  * relation: the relation between the variable and the value
 118  * related_value: the related value
 119  * relation_is_static_definition: TRUE if the relation comes from a veriable
 120  *                                definition, FALSE if it comes from a branch
 121  *                                condition
 122  * next: pointer to the next relation of this variable in the evaluation area
 123  *       (relations are always kept in the evaluation area, one list for each
 124  *       variable)
 125  */
 126 typedef struct MonoSummarizedValueRelation {
 127         MonoValueRelation relation;
 128         MonoSummarizedValue related_value;
 129         gboolean relation_is_static_definition;
 130         struct MonoSummarizedValueRelation *next;
 131 } MonoSummarizedValueRelation;
 132
 133 /**
 134  * The evaluation status for one variable.
 135  * The enumeration is used as a bit field, because the status has two
 136  * distinct sections.
 137  * The first is the "main" one (bits 0, 1 and 2), which is actually a proper
 138  * enumeration (the bits are mutually exclusive, and their meaning is obvious).
 139  * The other section (the bits in the MONO_RELATIONS_EVALUATION_IS_RECURSIVE
 140  * set) is used to mark an evaluation as recursive (while backtracking through
 141  * the evaluation contexts), to state if the graph loop gives a value that is
 142  * ascending, descending or indefinite.
 143  * The bits are handled separately because the same evaluation context could
 144  * belong to more than one loop, so that each loop would set its bits.
 145  * After the backtracking, the bits are examined and a decision is taken.
 146  *
 147  */
 148 typedef enum {
 149         MONO_RELATIONS_EVALUATION_NOT_STARTED = 0,
 150         MONO_RELATIONS_EVALUATION_IN_PROGRESS = 1,
 151         MONO_RELATIONS_EVALUATION_COMPLETED = 2,
 152         MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING = 4,
 153         MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING = 8,
 154         MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE = 16,
 155         MONO_RELATIONS_EVALUATION_IS_RECURSIVE = (MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_ASCENDING|MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_DESCENDING|MONO_RELATIONS_EVALUATION_IS_RECURSIVELY_INDEFINITE)
 156 } MonoRelationsEvaluationStatus;
 157
 158 /**
 159  * A range of values (ranges include their limits).
 160  * A range from MIN_INT to MAX_INT is "indefinite" (any value).
 161  * A range where upper < lower means unreachable code (some of the relations
 162  * that generated the range is incompatible, like x = 0 and x > 0).
 163  * lower: the lower limit
 164  * upper: the upper limit
 165  */
 166 typedef struct MonoRelationsEvaluationRange {
 167         int lower;
 168         int upper;
 169 } MonoRelationsEvaluationRange;
 170
 171 /**
 172  * The two ranges that contain the result of a variable evaluation.
 173  * zero: the range with respect to zero
 174  * variable: the range with respect to the target variable in this evaluation
 175  */
 176 typedef struct MonoRelationsEvaluationRanges {
 177         MonoRelationsEvaluationRange zero;
 178         MonoRelationsEvaluationRange variable;
 179 } MonoRelationsEvaluationRanges;
 180
 181 /**
 182  * The context of a variable evaluation.
 183  * current_relation: the relation that is currently evaluated.
 184  * ranges: the result of the evaluation.
 185  * father: the context of the evaluation that invoked this one (used to
 186  *         perform the backtracking when loops are detected.
 187  */
 188 typedef struct MonoRelationsEvaluationContext {
 189         MonoSummarizedValueRelation *current_relation;
 190         MonoRelationsEvaluationRanges ranges;
 191         struct MonoRelationsEvaluationContext *father;
 192 } MonoRelationsEvaluationContext;
 193
 194 /*
 195  * Basic macros to initialize and check ranges.
 196  */
 197 #define MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK(r) do{\
 198                 (r).lower = INT_MIN;\
 199                 (r).upper = INT_MAX;\
 200         } while (0)
 201 #define MONO_MAKE_RELATIONS_EVALUATION_RANGES_WEAK(rs) do{\
 202                 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK ((rs).zero); \
 203                 MONO_MAKE_RELATIONS_EVALUATION_RANGE_WEAK ((rs).variable); \
 204         } while (0)
 205 #define MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE(r) do{\
 206                 (r).lower = INT_MAX;\
 207                 (r).upper = INT_MIN;\
 208         } while (0)
 209 #define MONO_MAKE_RELATIONS_EVALUATION_RANGES_IMPOSSIBLE(rs) do{\
 210                 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE ((rs).zero); \
 211                 MONO_MAKE_RELATIONS_EVALUATION_RANGE_IMPOSSIBLE ((rs).variable); \
 212         } while (0)
 213 #define MONO_RELATIONS_EVALUATION_RANGE_IS_WEAK(r) (((r).lower==INT_MIN)&&((r).upper==INT_MAX))
 214 #define MONO_RELATIONS_EVALUATION_RANGES_ARE_WEAK(rs) \
 215         (MONO_RELATIONS_EVALUATION_RANGE_IS_WEAK((rs).zero) && \
 216         MONO_RELATIONS_EVALUATION_RANGE_IS_WEAK((rs).variable))
 217 #define MONO_RELATIONS_EVALUATION_RANGE_IS_IMPOSSIBLE(r) (((r).lower)>((r).upper))
 218 #define MONO_RELATIONS_EVALUATION_RANGES_ARE_IMPOSSIBLE(rs) \
 219         (MONO_RELATIONS_EVALUATION_RANGE_IS_IMPOSSIBLE((rs).zero) || \
 220         MONO_RELATIONS_EVALUATION_RANGE_IS_IMPOSSIBLE((rs).variable))
 221
 222 /*
 223  * The following macros are needed because ranges include theit limits, but
 224  * some relations explicitly exclude them (GT and LT).
 225  */
 226 #define MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL(ur) ((((ur)==INT_MIN)||((ur)==INT_MAX))?(ur):((ur)-1))
 227 #define MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL(lr) ((((lr)==INT_MIN)||((lr)==INT_MAX))?(lr):((lr)+1))
 228 #define MONO_APPLY_INEQUALITY_TO_EVALUATION_RANGE(r) do{\
 229                 (r).lower = MONO_LOWER_EVALUATION_RANGE_NOT_EQUAL ((r).lower);\
 230                 (r).upper = MONO_UPPER_EVALUATION_RANGE_NOT_EQUAL ((r).upper);\
 231         } while (0)
 232 #define MONO_APPLY_INEQUALITY_TO_EVALUATION_RANGES(rs) do{\
 233                 MONO_APPLY_INEQUALITY_TO_EVALUATION_RANGE ((rs).zero); \
 234                 MONO_APPLY_INEQUALITY_TO_EVALUATION_RANGE ((rs).variable); \
 235         } while (0)
 236
 237 /*
 238  * The following macros perform union and intersection operations on ranges.
 239  */
 240 #define MONO_LOWER_EVALUATION_RANGE_UNION(lr,other_lr) ((lr)=MIN(lr,other_lr))
 241 #define MONO_UPPER_EVALUATION_RANGE_UNION(ur,other_ur) ((ur)=MAX(ur,other_ur))
 242 #define MONO_LOWER_EVALUATION_RANGE_INTERSECTION(lr,other_lr) ((lr)=MAX(lr,other_lr))
 243 #define MONO_UPPER_EVALUATION_RANGE_INTERSECTION(ur,other_ur) ((ur)=MIN(ur,other_ur))
 244 #define MONO_RELATIONS_EVALUATION_RANGE_UNION(r,other_r) do{\
 245                 MONO_LOWER_EVALUATION_RANGE_UNION((r).lower,(other_r).lower);\
 246                 MONO_UPPER_EVALUATION_RANGE_UNION((r).upper,(other_r).upper);\
 247         } while (0)
 248 #define MONO_RELATIONS_EVALUATION_RANGE_INTERSECTION(r,other_r) do{\
 249                 MONO_LOWER_EVALUATION_RANGE_INTERSECTION((r).lower,(other_r).lower);\
 250                 MONO_UPPER_EVALUATION_RANGE_INTERSECTION((r).upper,(other_r).upper);\
 251         } while (0)
 252 #define MONO_RELATIONS_EVALUATION_RANGES_UNION(rs,other_rs) do{\
 253                 MONO_RELATIONS_EVALUATION_RANGE_UNION ((rs).zero,(other_rs).zero); \
 254                 MONO_RELATIONS_EVALUATION_RANGE_UNION ((rs).variable,(other_rs).variable); \
 255         } while (0)
 256 #define MONO_RELATIONS_EVALUATION_RANGES_INTERSECTION(rs,other_rs) do{\
 257                 MONO_RELATIONS_EVALUATION_RANGE_INTERSECTION ((rs).zero,(other_rs).zero); \
 258                 MONO_RELATIONS_EVALUATION_RANGE_INTERSECTION ((rs).variable,(other_rs).variable); \
 259         } while (0)
 260
 261 /*
 262  * The following macros add or subtract "safely" (without over/under-flow) a
 263  * delta (constant) value to a range.
 264  */
 265 #define MONO_ADD_DELTA_SAFELY(v,d) do{\
 266                 if (((d) > 0) && ((v) != INT_MIN)) {\
 267                         (v) = (((v)+(d))>(v))?((v)+(d)):INT_MAX;\
 268                 } else if (((d) < 0) && ((v) != INT_MAX)) {\
 269                         (v) = (((v)+(d))<(v))?((v)+(d)):INT_MIN;\
 270                 }\
 271         } while (0)
 272 #define MONO_SUB_DELTA_SAFELY(v,d) do{\
 273                 if (((d) < 0) && ((v) != INT_MIN)) {\
 274                         (v) = (((v)-(d))>(v))?((v)-(d)):INT_MAX;\
 275                 } else if (((d) > 0) && ((v) != INT_MAX)) {\
 276                         (v) = (((v)-(d))<(v))?((v)-(d)):INT_MIN;\
 277                 }\
 278         } while (0)
 279 #define MONO_ADD_DELTA_SAFELY_TO_RANGE(r,d) do{\
 280                 MONO_ADD_DELTA_SAFELY((r).lower,(d));\
 281                 MONO_ADD_DELTA_SAFELY((r).upper,(d));\
 282         } while (0)
 283 #define MONO_SUB_DELTA_SAFELY_FROM_RANGE(r,d) do{\
 284                 MONO_SUB_DELTA_SAFELY((r).lower,(d));\
 285                 MONO_SUB_DELTA_SAFELY((r).upper,(d));\
 286         } while (0)
 287 #define MONO_ADD_DELTA_SAFELY_TO_RANGES(rs,d) do{\
 288                 MONO_ADD_DELTA_SAFELY_TO_RANGE((rs).zero,(d));\
 289                 MONO_ADD_DELTA_SAFELY_TO_RANGE((rs).variable,(d));\
 290         } while (0)
 291 #define MONO_SUB_DELTA_SAFELY_FROM_RANGES(rs,d) do{\
 292                 MONO_SUB_DELTA_SAFELY_FROM_RANGE((rs).zero,(d));\
 293                 MONO_SUB_DELTA_SAFELY_FROM_RANGE((rs).variable,(d));\
 294         } while (0)
 295
 296
 297 /**
 298  * The main evaluation area.
 299  * cfg: the cfg of the method that is being examined.
 300  * relations: and array of relations, one for each method variable (each
 301  *            relation is the head of a list); this is the evaluation graph
 302  * contexts: an array of evaluation contexts (one for each method variable)
 303  * variable_value_kind: an array of MonoIntegerValueKind, one for each local
 304  *                      variable (or argument)
 305  * defs: maps vregs to the instruction which defines it.
 306  */
 307 typedef struct MonoVariableRelationsEvaluationArea {
 308         MonoCompile *cfg;
 309         MonoSummarizedValueRelation *relations;
 310
 311 /**
 312  * statuses and contexts are parallel arrays. A given index into each refers to
 313  * the same context. This is a performance optimization. Clean_context was
 314  * coming to dominate the running time of abcremoval. By
 315  * storing the statuses together, we can memset the entire
 316  * region.
 317  */
 318         MonoRelationsEvaluationStatus *statuses;
 319         MonoRelationsEvaluationContext *contexts;
 320
 321         MonoIntegerValueKind *variable_value_kind;
 322         MonoInst **defs;
 323 } MonoVariableRelationsEvaluationArea;
 324
 325 /**
 326  * Convenience structure to define an "additional" relation for the main
 327  * evaluation graph.
 328  * variable: the variable to which the relation is applied
 329  * relation: the relation
 330  * insertion_point: the point in the graph where the relation is inserted
 331  *                  (useful for removing it from the list when backtracking
 332  *                  in the traversal of the dominator tree)
 333  */
 334 typedef struct MonoAdditionalVariableRelation {
 335         int variable;
 336         MonoSummarizedValueRelation relation;
 337         MonoSummarizedValueRelation *insertion_point;
 338 } MonoAdditionalVariableRelation;
 339
 340 /**
 341  * Convenience structure that stores two additional relations.
 342  * In the current code, each BB can add at most two relations to the main
 343  * evaluation graph, so one of these structures is enough to hold all the
 344  * modifications to the graph made examining one BB.
 345  */
 346 typedef struct MonoAdditionalVariableRelationsForBB {
 347         MonoAdditionalVariableRelation relation1;
 348         MonoAdditionalVariableRelation relation2;
 349 } MonoAdditionalVariableRelationsForBB;
 350
 351
 352 #endif /* __MONO_ABCREMOVAL_H__ */