mono/mini/ssapre.h

   1 /*
   2  * ssapre.h: SSA Partial Redundancy Elimination
   3  *
   4  * Author:
   5  *   Massimiliano Mantione (massi@ximian.com)
   6  *
   7  * (C) 2004 Novell, Inc.  http://www.novell.com
   8  */
   9
  10 #ifndef __MONO_SSAPRE_H__
  11 #define __MONO_SSAPRE_H__
  12
  13
  14 #include "mini.h"
  15 #include <mono/metadata/mempool.h>
  16
  17 /*
  18  * Hack to apply SSAPRE only to a given method (invaluable in debugging)
  19  */
  20 #define MONO_APPLY_SSAPRE_TO_SINGLE_METHOD 0
  21
  22 /*
  23  * Hack to apply SSAPRE only to a given expression (invaluable in debugging)
  24  */
  25 #define MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION 0
  26
  27 /*
  28  * All the different kind of arguments we can handle.
  29  * "ANY" means the argument is unknown or cannot be handled, and "NOT_PRESENT"
  30  * that the expression does not have this argument (has not "enough" arity).
  31  */
  32 typedef enum {
  33         MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY,
  34         MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT,
  35         MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE,
  36         MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE,
  37         MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT,
  38         MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT,
  39         MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT,
  40         MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT
  41 } MonoSsapreExpressionArgumentType;
  42
  43 /*
  44  * A struct representing an expression argument (the used branch in the
  45  * union depends on the value of the type field).
  46  */
  47 typedef struct MonoSsapreExpressionArgument {
  48         MonoSsapreExpressionArgumentType type;
  49         union {
  50                 int original_variable;
  51                 int ssa_variable;
  52                 int integer_constant;
  53                 gint64* long_constant;
  54                 float* float_constant;
  55                 double* double_constant;
  56         } argument;
  57 } MonoSsapreExpressionArgument;
  58
  59 /*
  60  * Macros used when comparing expression arguments, which return -1,0 or 1.
  61  */
  62 #define MONO_COMPARE_SSAPRE_DIRECT_VALUES(v1,v2) (((v2)>(v1)?(1):((v2)<(v1)?(-1):(0))))
  63 #define MONO_COMPARE_SSAPRE_POINTER_VALUES(p1,p2) (((*p2)>(*p1)?(1):((*p2)<(*p1)?(-1):(0))))
  64
  65 #define MONO_COMPARE_SSAPRE_EXPRESSION_ARGUMENT_VALUES(t,v1,v2) (\
  66                 (t)==MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE?\
  67                         MONO_COMPARE_SSAPRE_DIRECT_VALUES ((v1).original_variable,(v2).original_variable):(\
  68                 (t)==MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE?\
  69                         MONO_COMPARE_SSAPRE_DIRECT_VALUES ((v1).ssa_variable,(v2).ssa_variable):(\
  70                 (t)==MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT?\
  71                         MONO_COMPARE_SSAPRE_DIRECT_VALUES ((v1).integer_constant,(v2).integer_constant):(\
  72                 (t)==MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT?\
  73                         MONO_COMPARE_SSAPRE_POINTER_VALUES ((v1).long_constant,(v2).long_constant):(\
  74                 (t)==MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT?\
  75                         MONO_COMPARE_SSAPRE_POINTER_VALUES ((v1).float_constant,(v2).float_constant):(\
  76                 (t)==MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT?\
  77                         MONO_COMPARE_SSAPRE_POINTER_VALUES ((v1).double_constant,(v2).double_constant):(\
  78                 0)))))))
  79
  80 #define MONO_COMPARE_SSAPRE_EXPRESSION_ARGUMENTS(a1,a2) (\
  81                 MONO_COMPARE_SSAPRE_DIRECT_VALUES ((a1).type,(a2).type)!=0?\
  82                         MONO_COMPARE_SSAPRE_DIRECT_VALUES ((a1).type,(a2).type):\
  83                 MONO_COMPARE_SSAPRE_EXPRESSION_ARGUMENT_VALUES ((a1).type,(a1).argument,(a2).argument) )
  84
  85
  86 /*
  87  * A struct representing an expression, with its opcode and two arguments
  88  * (if the opcode has arity 1 right_argument is MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT).
  89  */
  90 typedef struct MonoSsapreExpressionDescription {
  91         guint16 opcode;
  92         MonoSsapreExpressionArgument left_argument;
  93         MonoSsapreExpressionArgument right_argument;
  94 } MonoSsapreExpressionDescription;
  95
  96 /*
  97  * Macro that compares two expression descriptions (returns -1, 0 or 1).
  98  */
  99 #define MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS(d1,d2) (\
 100                 MONO_COMPARE_SSAPRE_DIRECT_VALUES ((d1).opcode,(d2).opcode)!=0?\
 101                         MONO_COMPARE_SSAPRE_DIRECT_VALUES ((d1).opcode,(d2).opcode):(\
 102                 MONO_COMPARE_SSAPRE_EXPRESSION_ARGUMENTS ((d1).left_argument,(d2).left_argument)!=0?\
 103                         MONO_COMPARE_SSAPRE_EXPRESSION_ARGUMENTS ((d1).left_argument,(d2).left_argument):(\
 104                 MONO_COMPARE_SSAPRE_EXPRESSION_ARGUMENTS ((d1).right_argument,(d2).right_argument)!=0?\
 105                         MONO_COMPARE_SSAPRE_EXPRESSION_ARGUMENTS ((d1).right_argument,(d2).right_argument):(\
 106                 0))))
 107
 108 /*
 109  * Struct that contains all the information related to a BB.
 110  * Some of them are taken from the corresponding MonoBasicBlock, some are
 111  * constant during the compilation of the whole method, others must be
 112  * recomputed for each expression.
 113  */
 114 typedef struct MonoSsapreBBInfo {
 115         /* Information constant during the compilation of the whole method: */
 116
 117         /* Depth First Number relative to a traversal of the dominator tree */
 118         gint32 dt_dfn;
 119         /* Depth First Number relative to a traversal of the CFG */
 120         gint32 cfg_dfn;
 121         /* Number of descendants in the dominator tree (is equal to the number of strictly dominated BBs) */
 122         int dt_descendants;
 123         /* In and out count (taken from the corresponding MonoBasicBlock) */
 124         gint16 in_count, out_count;
 125         /* Idominator (taken from the corresponding MonoBasicBlock, but pointing */
 126         /* to the MonoSsapreBBInfo for convenience) */
 127         struct MonoSsapreBBInfo *idominator;
 128         /* In and out BBs (taken from the corresponding MonoBasicBlock, but pointing */
 129         /* to the MonoSsapreBBInfo for convenience) */
 130         struct MonoSsapreBBInfo **in_bb;
 131         struct MonoSsapreBBInfo **out_bb;
 132         /* Dominance frontier (taken from the corresponding MonoBasicBlock) */
 133         MonoBitSet *dfrontier;
 134
 135         /* MonoInst where new phi definitions must be added in the BB */
 136         /* (the last existing phi definition, or NULL if there is none) */
 137         MonoInst *phi_insertion_point;
 138
 139         /* Information reused during the analysis of each expression: */
 140
 141         /* True if this BB has a PHI occurrence */
 142         gboolean has_phi;
 143         /* True if this PHI defines a real occurrence */
 144         gboolean phi_defines_a_real_occurrence;
 145         /* True if this PHI is down safe */
 146         gboolean phi_is_down_safe;
 147         /* True if this PHI can be available */
 148         gboolean phi_can_be_available;
 149         /* True if this PHI is "later" */
 150         gboolean phi_is_later;
 151         /* The PHI class number */
 152         int phi_redundancy_class;
 153         /* The index of this PHI in the cfg->vars array */
 154         int phi_variable_index;
 155         /* Array of the class numbers of the PHI arguments (has "in_count" elements) */
 156         int *phi_arguments_classes;
 157
 158
 159         /* True if this BB has a PHI argument */
 160         gboolean has_phi_argument;
 161         /* True if this PHI argument "has real use" */
 162         gboolean phi_argument_has_real_use;
 163         /* True if this PHI argument needs the insertion of a new occurrence */
 164         gboolean phi_argument_needs_insert;
 165         /* True if this PHI argument has been processed (see "set_save") */
 166         gboolean phi_argument_has_been_processed;
 167         /* The PHI argument class number */
 168         int phi_argument_class;
 169         /* The index of this PHI argument in the cfg->vars array */
 170         int phi_argument_variable_index;
 171         /* Points to the real occurrence defining this PHI argument (NULL otherwise) */
 172         struct MonoSsapreExpressionOccurrence *phi_argument_defined_by_real_occurrence;
 173         /* Points to the BB containing the PHI defining this PHI argument (NULL otherwise) */
 174         struct MonoSsapreBBInfo *phi_argument_defined_by_phi;
 175         /* Variable version of the left argument og the PHI argument "expected" at */
 176         /* the PHI (or BOTTOM_REDUNDANCY_CLASS otherwise), see "renaming_pass" */
 177         int phi_argument_left_argument_version;
 178         /* As above, but for the right argument */
 179         int phi_argument_right_argument_version;
 180
 181         /* The first real occurrence in this BB (NULL if there is none) */
 182         struct MonoSsapreExpressionOccurrence *first_expression_in_bb;
 183         /* Next BB which has either a real occurrence, a PHI or a PHI argument */
 184         /* (NULL if there is none, BBs are in dominator tree depth first preorder) */
 185         struct MonoSsapreBBInfo *next_interesting_bb;
 186
 187         /* Used in maintaining the renaming stack */
 188         struct MonoSsapreBBInfo *next_in_renaming_stack;
 189         struct MonoSsapreExpressionOccurrence *top_of_local_renaming_stack;
 190
 191         /* MonoBasicBlock representing this BB in the CFG (this is obviously constant) */
 192         MonoBasicBlock *bb;
 193 } MonoSsapreBBInfo;
 194
 195
 196 /*
 197  * The father of an occurrence in the tree of MonoInst.
 198  * (needed just because a MonoInst cannot point to its father)
 199  */
 200 typedef struct MonoSsapreFatherExpression {
 201         /* The father occurrence */
 202         MonoInst *father_occurrence;
 203         /* The MonoSsapreFatherExpression node of the "grand father" */
 204         struct MonoSsapreFatherExpression *grand_father;
 205 } MonoSsapreFatherExpression;
 206
 207 /*
 208  * A "real" occurrence.
 209  */
 210 typedef struct MonoSsapreExpressionOccurrence {
 211         /* The occurrence in the CFG */
 212         MonoInst *occurrence;
 213         /* The "father" of this occurrence in the inst tree (if the occurrence is */
 214         /* part of a compound expression, otherwise it is NULL) */
 215         MonoSsapreFatherExpression *father_in_tree;
 216         /* The tree just before the occurrence in the CFG (if the occurrence must */
 217         /* saved into a temporary, the definition will be placed just after that tree) */
 218         MonoInst *previous_tree;
 219         /* The BB where this occurrence is found */
 220         MonoSsapreBBInfo *bb_info;
 221         /* The description of the occurrence */
 222         MonoSsapreExpressionDescription description;
 223         /* Next occurrence of this expression */
 224         struct MonoSsapreExpressionOccurrence *next;
 225         /* Previous occurrence of this expression */
 226         struct MonoSsapreExpressionOccurrence *previous;
 227         /* True if this occurrence is the first in its BB */
 228         gboolean is_first_in_bb;
 229         /* True if this occurrence is the last in its BB */
 230         gboolean is_last_in_bb;
 231         /* "reload" flag (see "finalize") */
 232         gboolean reload;
 233         /* "save" flag (see "finalize") */
 234         gboolean save;
 235
 236         /* Used in maintaining the renaming stack */
 237         struct MonoSsapreExpressionOccurrence *next_in_renaming_stack;
 238
 239         /* Class number of this occurrence */
 240         int redundancy_class;
 241         /* The index of the temporary of this occurrence in the cfg->vars array */
 242         int variable_index;
 243         /* Points to the real occurrence defining this occurrence (NULL otherwise) */
 244         struct MonoSsapreExpressionOccurrence *defined_by_real_occurrence;
 245         /* Points to the BB containing the PHI defining this occurrence (NULL otherwise) */
 246         struct MonoSsapreBBInfo *defined_by_phi;
 247 } MonoSsapreExpressionOccurrence;
 248
 249
 250 /*
 251  * An expression to be processed (in the worklist).
 252  */
 253 typedef struct MonoSsapreExpression {
 254         /* The description of the expression */
 255         MonoSsapreExpressionDescription description;
 256         /* The type to use when creating values of this expression */
 257         MonoType *type;
 258         /* The list of expression occurrences */
 259         MonoSsapreExpressionOccurrence *occurrences;
 260         /* The last expression occurrence in the list */
 261         MonoSsapreExpressionOccurrence *last_occurrence;
 262
 263         /* Used in maintaining the worklist (an autobalancing binary tree) */
 264         struct MonoSsapreExpression *father;
 265         struct MonoSsapreExpression *previous;
 266         struct MonoSsapreExpression *next;
 267         int tree_size;
 268
 269         /* Next expression to be processed in the worklist */
 270         struct MonoSsapreExpression *next_in_queue;
 271 } MonoSsapreExpression;
 272
 273 /*
 274  * Macros used to maintain the worklist
 275  */
 276 #define MONO_SSAPRE_GOTO_FIRST_EXPRESSION(e) do{\
 277                 while ((e)->previous != NULL) (e) = (e)->previous;\
 278         } while (0)
 279 #define MONO_SSAPRE_REMOVE_FIRST_EXPRESSION(e) do{\
 280                 if ((e)->father != NULL) {\
 281                         (e)->father->previous = (e)->next;\
 282                 }\
 283         } while (0)
 284 #define MONO_SSAPRE_GOTO_LAST_EXPRESSION(e) do{\
 285                 while ((e)->next != NULL) (e) = (e)->next;\
 286         } while (0)
 287 #define MONO_SSAPRE_REMOVE_LAST_EXPRESSION(e) do{\
 288                 if ((e)->father != NULL) {\
 289                         (e)->father->next = (e)->previous;\
 290                 }\
 291         } while (0)
 292
 293 #define MONO_SSAPRE_MAX_TREE_DEPTH(size,depth) do{\
 294                 unsigned __mask__ = ~1;\
 295                 (depth) = 1;\
 296                 while (((size)&__mask__)!=0) {\
 297                         __mask__ <<= 1;\
 298                         (depth)++;\
 299                 }\
 300         } while (0)
 301
 302 #define MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE(e,o) do{\
 303                 if ((e)->occurrences == NULL) {\
 304                         (e)->occurrences = (o);\
 305                 } else {\
 306                         (e)->last_occurrence->next = (o);\
 307                 }\
 308                 (o)->next = NULL;\
 309                 (o)->previous = (e)->last_occurrence;\
 310                 (e)->last_occurrence = (o);\
 311         } while (0)
 312 #define MONO_SSAPRE_REMOVE_EXPRESSION_OCCURRANCE(e,o) do{\
 313                 if ((e)->occurrences == (o)) {\
 314                         (e)->occurrences = (o)->next;\
 315                 }\
 316                 if ((e)->last_occurrence == (o)) {\
 317                         (e)->last_occurrence = (o)->previous;\
 318                 }\
 319                 if ((o)->previous != NULL) {\
 320                         (o)->previous->next = (o)->next;\
 321                 }\
 322                 if ((o)->next != NULL) {\
 323                         (o)->next->previous = (o)->previous;\
 324                 }\
 325                 (o)->next = NULL;\
 326                 (o)->previous = NULL;\
 327         } while (0)
 328
 329
 330 /*
 331  * Availability table element (see "finalize"), one for each redundancy class
 332  */
 333 typedef struct MonoSsapreAvailabilityTableElement {
 334         /* Points to the real occurrence defining this redundancy class (NULL otherwise) */
 335         struct MonoSsapreExpressionOccurrence *class_defined_by_real_occurrence;
 336         /* Points to the BB containing the PHI defining this redundancy class (NULL otherwise) */
 337         struct MonoSsapreBBInfo *class_defined_by_phi;
 338 } MonoSsapreAvailabilityTableElement;
 339
 340 /*
 341  * The "main" work area for the algorithm.
 342  */
 343 typedef struct MonoSsapreWorkArea {
 344         /* The CFG */
 345         MonoCompile *cfg;
 346         /* The SSAPRE specific mempool */
 347         MonoMemPool *mempool;
 348
 349         /* Number of BBs in the CFG (from cfg) */
 350         int num_bblocks;
 351         /* BB information, in dominator tree depth first preorder */
 352         MonoSsapreBBInfo *bb_infos;
 353         /* Pointers to BB information, in CFG depth first preorder */
 354         MonoSsapreBBInfo **bb_infos_in_cfg_dfn_order;
 355
 356         /* Number of variables in the CFG */
 357         int num_vars;
 358         /* Size of bitset for BBs */
 359         int sizeof_bb_bitset;
 360         /* Various bitsets used when working with iterated dfrontiers */
 361         MonoBitSet *expression_occurrences_buffer;
 362         MonoBitSet *bb_iteration_buffer;
 363         MonoBitSet *iterated_dfrontier_buffer;
 364         MonoBitSet *left_argument_bb_bitset;
 365         MonoBitSet *right_argument_bb_bitset;
 366
 367         /* The expression worklist */
 368         MonoSsapreExpression *worklist;
 369
 370         /* The expression queue head */
 371         MonoSsapreExpression *first_in_queue;
 372         /* The expression queue tail */
 373         MonoSsapreExpression *last_in_queue;
 374
 375         /* The expression being processed */
 376         MonoSsapreExpression *current_expression;
 377         /* The expression being allocated */
 378         MonoSsapreExpressionOccurrence *current_occurrence;
 379
 380         /* The BB on top of the renaming stack (if "top_of_renaming_stack" is NULL */
 381         /* but this is not, then the top of the stack is the PHI in this BB) */
 382         struct MonoSsapreBBInfo *bb_on_top_of_renaming_stack;
 383         /* The top of the renaming stack */
 384         struct MonoSsapreExpressionOccurrence *top_of_renaming_stack;
 385
 386         /* The head of the list of "interesting" BBs */
 387         struct MonoSsapreBBInfo *first_interesting_bb;
 388
 389         /* The number of generated class numbers */
 390         int number_of_classes;
 391
 392         /* Statistics fields (per expression)  */
 393         int saved_occurrences;
 394         int reloaded_occurrences;
 395         int inserted_occurrences;
 396         int unaltered_occurrences;
 397         int added_phis;
 398
 399 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
 400         gboolean expression_is_handled_father;
 401 #endif
 402 } MonoSsapreWorkArea;
 403
 404
 405 #endif /* __MONO_SSAPRE_H__ */