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