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 recomputed during the analysis of each expression: */
 140
 141         /* True if the whole BB subtree in the dominator tree is "covered" with */
 142         /* BBs marked "interesting" (a BB where this is false cannot be down */
 143         /* safe, since there would be a path to exit with no occurrence at all). */
 144         /* A more formal way of stating this is that on the DT there is no path */
 145         /* from this BB to any leaf that does not meet an interesting BB */
 146         gboolean dt_covered_by_interesting_BBs;
 147
 148         /* True if this BB has a PHI occurrence */
 149         gboolean has_phi;
 150         /* True if this PHI defines a real occurrence */
 151         gboolean phi_defines_a_real_occurrence;
 152         /* True if this PHI is down safe */
 153         gboolean phi_is_down_safe;
 154         /* True if this PHI can be available */
 155         gboolean phi_can_be_available;
 156         /* True if this PHI is "later" */
 157         gboolean phi_is_later;
 158         /* The PHI class number */
 159         int phi_redundancy_class;
 160         /* The index of this PHI in the cfg->vars array */
 161         int phi_variable_index;
 162         /* Array of the class numbers of the PHI arguments (has "in_count" elements) */
 163         int *phi_arguments_classes;
 164
 165         /* True if this BB has a PHI argument */
 166         gboolean has_phi_argument;
 167         /* True if this PHI argument "has real use" */
 168         gboolean phi_argument_has_real_use;
 169         /* True if this PHI argument needs the insertion of a new occurrence */
 170         gboolean phi_argument_needs_insert;
 171         /* True if this PHI argument has been processed (see "set_save") */
 172         gboolean phi_argument_has_been_processed;
 173         /* The PHI argument class number */
 174         int phi_argument_class;
 175         /* The index of this PHI argument in the cfg->vars array */
 176         int phi_argument_variable_index;
 177         /* Points to the real occurrence defining this PHI argument (NULL otherwise) */
 178         struct MonoSsapreExpressionOccurrence *phi_argument_defined_by_real_occurrence;
 179         /* Points to the BB containing the PHI defining this PHI argument (NULL otherwise) */
 180         struct MonoSsapreBBInfo *phi_argument_defined_by_phi;
 181         /* Variable version of the left argument og the PHI argument "expected" at */
 182         /* the PHI (or BOTTOM_REDUNDANCY_CLASS otherwise), see "renaming_pass" */
 183         int phi_argument_left_argument_version;
 184         /* As above, but for the right argument */
 185         int phi_argument_right_argument_version;
 186
 187         /* The first real occurrence in this BB (NULL if there is none) */
 188         struct MonoSsapreExpressionOccurrence *first_expression_in_bb;
 189         /* Next BB which has either a real occurrence, a PHI or a PHI argument */
 190         /* (NULL if there is none, BBs are in dominator tree depth first preorder) */
 191         struct MonoSsapreBBInfo *next_interesting_bb;
 192
 193         /* Used in maintaining the renaming stack */
 194         struct MonoSsapreBBInfo *next_in_renaming_stack;
 195         struct MonoSsapreExpressionOccurrence *top_of_local_renaming_stack;
 196
 197         /* MonoBasicBlock representing this BB in the CFG (this is obviously constant) */
 198         MonoBasicBlock *bb;
 199 } MonoSsapreBBInfo;
 200
 201
 202 /*
 203  * The father of an occurrence in the tree of MonoInst.
 204  * (needed just because a MonoInst cannot point to its father)
 205  */
 206 typedef struct MonoSsapreFatherExpression {
 207         /* The father occurrence */
 208         MonoInst *father_occurrence;
 209         /* The MonoSsapreFatherExpression node of the "grand father" */
 210         struct MonoSsapreFatherExpression *grand_father;
 211 } MonoSsapreFatherExpression;
 212
 213 /*
 214  * A "real" occurrence.
 215  */
 216 typedef struct MonoSsapreExpressionOccurrence {
 217         /* The occurrence in the CFG */
 218         MonoInst *occurrence;
 219         /* The "father" of this occurrence in the inst tree (if the occurrence is */
 220         /* part of a compound expression, otherwise it is NULL) */
 221         MonoSsapreFatherExpression *father_in_tree;
 222         /* The tree just before the occurrence in the CFG (if the occurrence must */
 223         /* saved into a temporary, the definition will be placed just after that tree) */
 224         MonoInst *previous_tree;
 225         /* The BB where this occurrence is found */
 226         MonoSsapreBBInfo *bb_info;
 227         /* The description of the occurrence */
 228         MonoSsapreExpressionDescription description;
 229         /* Next occurrence of this expression */
 230         struct MonoSsapreExpressionOccurrence *next;
 231         /* Previous occurrence of this expression */
 232         struct MonoSsapreExpressionOccurrence *previous;
 233         /* True if this occurrence is the first in its BB */
 234         gboolean is_first_in_bb;
 235         /* True if this occurrence is the last in its BB */
 236         gboolean is_last_in_bb;
 237         /* "reload" flag (see "finalize") */
 238         gboolean reload;
 239         /* "save" flag (see "finalize") */
 240         gboolean save;
 241
 242         /* Used in maintaining the renaming stack */
 243         struct MonoSsapreExpressionOccurrence *next_in_renaming_stack;
 244
 245         /* Class number of this occurrence */
 246         int redundancy_class;
 247         /* The index of the temporary of this occurrence in the cfg->vars array */
 248         int variable_index;
 249         /* Points to the real occurrence defining this occurrence (NULL otherwise) */
 250         struct MonoSsapreExpressionOccurrence *defined_by_real_occurrence;
 251         /* Points to the BB containing the PHI defining this occurrence (NULL otherwise) */
 252         struct MonoSsapreBBInfo *defined_by_phi;
 253 } MonoSsapreExpressionOccurrence;
 254
 255
 256 /*
 257  * An expression to be processed (in the worklist).
 258  */
 259 typedef struct MonoSsapreExpression {
 260         /* The description of the expression */
 261         MonoSsapreExpressionDescription description;
 262         /* The type to use when creating values of this expression */
 263         MonoType *type;
 264         /* The list of expression occurrences */
 265         MonoSsapreExpressionOccurrence *occurrences;
 266         /* The last expression occurrence in the list */
 267         MonoSsapreExpressionOccurrence *last_occurrence;
 268
 269         /* Used in maintaining the worklist (an autobalancing binary tree) */
 270         struct MonoSsapreExpression *father;
 271         struct MonoSsapreExpression *previous;
 272         struct MonoSsapreExpression *next;
 273         int tree_size;
 274
 275         /* Next expression to be processed in the worklist */
 276         struct MonoSsapreExpression *next_in_queue;
 277 } MonoSsapreExpression;
 278
 279 /*
 280  * Macros used to maintain the worklist
 281  */
 282 #define MONO_SSAPRE_GOTO_FIRST_EXPRESSION(e) do{\
 283                 while ((e)->previous != NULL) (e) = (e)->previous;\
 284         } while (0)
 285 #define MONO_SSAPRE_REMOVE_FIRST_EXPRESSION(e) do{\
 286                 if ((e)->father != NULL) {\
 287                         (e)->father->previous = (e)->next;\
 288                 }\
 289         } while (0)
 290 #define MONO_SSAPRE_GOTO_LAST_EXPRESSION(e) do{\
 291                 while ((e)->next != NULL) (e) = (e)->next;\
 292         } while (0)
 293 #define MONO_SSAPRE_REMOVE_LAST_EXPRESSION(e) do{\
 294                 if ((e)->father != NULL) {\
 295                         (e)->father->next = (e)->previous;\
 296                 }\
 297         } while (0)
 298
 299 #define MONO_SSAPRE_MAX_TREE_DEPTH(size,depth) do{\
 300                 unsigned __mask__ = ~1;\
 301                 (depth) = 1;\
 302                 while (((size)&__mask__)!=0) {\
 303                         __mask__ <<= 1;\
 304                         (depth)++;\
 305                 }\
 306         } while (0)
 307
 308 #define MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE(e,o) do{\
 309                 if ((e)->occurrences == NULL) {\
 310                         (e)->occurrences = (o);\
 311                 } else {\
 312                         (e)->last_occurrence->next = (o);\
 313                 }\
 314                 (o)->next = NULL;\
 315                 (o)->previous = (e)->last_occurrence;\
 316                 (e)->last_occurrence = (o);\
 317         } while (0)
 318 #define MONO_SSAPRE_REMOVE_EXPRESSION_OCCURRANCE(e,o) do{\
 319                 if ((e)->occurrences == (o)) {\
 320                         (e)->occurrences = (o)->next;\
 321                 }\
 322                 if ((e)->last_occurrence == (o)) {\
 323                         (e)->last_occurrence = (o)->previous;\
 324                 }\
 325                 if ((o)->previous != NULL) {\
 326                         (o)->previous->next = (o)->next;\
 327                 }\
 328                 if ((o)->next != NULL) {\
 329                         (o)->next->previous = (o)->previous;\
 330                 }\
 331                 (o)->next = NULL;\
 332                 (o)->previous = NULL;\
 333         } while (0)
 334
 335
 336 /*
 337  * Availability table element (see "finalize"), one for each redundancy class
 338  */
 339 typedef struct MonoSsapreAvailabilityTableElement {
 340         /* Points to the real occurrence defining this redundancy class (NULL otherwise) */
 341         struct MonoSsapreExpressionOccurrence *class_defined_by_real_occurrence;
 342         /* Points to the BB containing the PHI defining this redundancy class (NULL otherwise) */
 343         struct MonoSsapreBBInfo *class_defined_by_phi;
 344 } MonoSsapreAvailabilityTableElement;
 345
 346 /*
 347  * The "main" work area for the algorithm.
 348  */
 349 typedef struct MonoSsapreWorkArea {
 350         /* The CFG */
 351         MonoCompile *cfg;
 352         /* The SSAPRE specific mempool */
 353         MonoMemPool *mempool;
 354
 355         /* Number of BBs in the CFG (from cfg) */
 356         int num_bblocks;
 357         /* BB information, in dominator tree depth first preorder */
 358         MonoSsapreBBInfo *bb_infos;
 359         /* Pointers to BB information, in CFG depth first preorder */
 360         MonoSsapreBBInfo **bb_infos_in_cfg_dfn_order;
 361
 362         /* Number of variables in the CFG */
 363         int num_vars;
 364         /* Size of bitset for BBs */
 365         int sizeof_bb_bitset;
 366         /* Various bitsets used when working with iterated dfrontiers */
 367         MonoBitSet *expression_occurrences_buffer;
 368         MonoBitSet *bb_iteration_buffer;
 369         MonoBitSet *iterated_dfrontier_buffer;
 370         MonoBitSet *left_argument_bb_bitset;
 371         MonoBitSet *right_argument_bb_bitset;
 372
 373         /* The depth of the dominator tree */
 374         int dt_depth;
 375
 376         /* The expression worklist */
 377         MonoSsapreExpression *worklist;
 378
 379         /* The expression queue head */
 380         MonoSsapreExpression *first_in_queue;
 381         /* The expression queue tail */
 382         MonoSsapreExpression *last_in_queue;
 383
 384         /* The expression being processed */
 385         MonoSsapreExpression *current_expression;
 386         /* The expression being allocated */
 387         MonoSsapreExpressionOccurrence *current_occurrence;
 388
 389         /* The BB on top of the renaming stack (if "top_of_renaming_stack" is NULL */
 390         /* but this is not, then the top of the stack is the PHI in this BB) */
 391         struct MonoSsapreBBInfo *bb_on_top_of_renaming_stack;
 392         /* The top of the renaming stack */
 393         struct MonoSsapreExpressionOccurrence *top_of_renaming_stack;
 394
 395         /* The head of the list of "interesting" BBs */
 396         struct MonoSsapreBBInfo *first_interesting_bb;
 397
 398         /* The number of generated class numbers */
 399         int number_of_classes;
 400
 401         /* The number of occurrences scheduled for reloading/insertion */
 402         /* (used to decide if the redundancy is worth eliminating) */
 403         int occurrences_scheduled_for_reloading;
 404         int arguments_scheduled_for_insertion;
 405         int dominating_arguments_scheduled_for_insertion;
 406
 407         /* Statistics fields (per expression)  */
 408         int saved_occurrences;
 409         int reloaded_occurrences;
 410         int inserted_occurrences;
 411         int unaltered_occurrences;
 412         int added_phis;
 413
 414 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
 415         gboolean expression_is_handled_father;
 416 #endif
 417 } MonoSsapreWorkArea;
 418
 419
 420 #endif /* __MONO_SSAPRE_H__ */