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