#include "mini.h"
#include <mono/metadata/mempool.h>
+/*
+ * Hack to apply SSAPRE only to a given method (invaluable in debugging)
+ */
+#define MONO_APPLY_SSAPRE_TO_SINGLE_METHOD 0
+
+/*
+ * Hack to apply SSAPRE only to a given expression (invaluable in debugging)
+ */
+#define MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION 0
+
/*
* All the different kind of arguments we can handle.
* "ANY" means the argument is unknown or cannot be handled, and "NOT_PRESENT"
typedef struct MonoSsapreExpressionArgument {
MonoSsapreExpressionArgumentType type;
union {
- gssize original_variable;
- gssize ssa_variable;
- gssize integer_constant;
+ int original_variable;
+ int ssa_variable;
+ int integer_constant;
gint64* long_constant;
float* float_constant;
double* double_constant;
/* (the last existing phi definition, or NULL if there is none) */
MonoInst *phi_insertion_point;
- /* Information reused during the analysis of each expression: */
+ /* Information recomputed during the analysis of each expression: */
+
+ /* True if the whole BB subtree in the dominator tree is "covered" with */
+ /* BBs marked "interesting" (a BB where this is false cannot be down */
+ /* safe, since there would be a path to exit with no occurrence at all). */
+ /* A more formal way of stating this is that on the DT there is no path */
+ /* from this BB to any leaf that does not meet an interesting BB */
+ gboolean dt_covered_by_interesting_BBs;
/* True if this BB has a PHI occurrence */
gboolean has_phi;
/* True if this PHI is "later" */
gboolean phi_is_later;
/* The PHI class number */
- gssize phi_redundancy_class;
+ int phi_redundancy_class;
/* The index of this PHI in the cfg->vars array */
- gssize phi_variable_index;
+ int phi_variable_index;
/* Array of the class numbers of the PHI arguments (has "in_count" elements) */
- gssize *phi_arguments_classes;
-
+ int *phi_arguments_classes;
/* True if this BB has a PHI argument */
gboolean has_phi_argument;
/* True if this PHI argument has been processed (see "set_save") */
gboolean phi_argument_has_been_processed;
/* The PHI argument class number */
- gssize phi_argument_class;
+ int phi_argument_class;
/* The index of this PHI argument in the cfg->vars array */
- gssize phi_argument_variable_index;
+ int phi_argument_variable_index;
/* Points to the real occurrence defining this PHI argument (NULL otherwise) */
struct MonoSsapreExpressionOccurrence *phi_argument_defined_by_real_occurrence;
/* Points to the BB containing the PHI defining this PHI argument (NULL otherwise) */
struct MonoSsapreBBInfo *phi_argument_defined_by_phi;
/* Variable version of the left argument og the PHI argument "expected" at */
/* the PHI (or BOTTOM_REDUNDANCY_CLASS otherwise), see "renaming_pass" */
- gssize phi_argument_left_argument_version;
+ int phi_argument_left_argument_version;
/* As above, but for the right argument */
- gssize phi_argument_right_argument_version;
+ int phi_argument_right_argument_version;
/* The first real occurrence in this BB (NULL if there is none) */
struct MonoSsapreExpressionOccurrence *first_expression_in_bb;
} MonoSsapreBBInfo;
+/*
+ * The father of an occurrence in the tree of MonoInst.
+ * (needed just because a MonoInst cannot point to its father)
+ */
+typedef struct MonoSsapreFatherExpression {
+ /* The father occurrence */
+ MonoInst *father_occurrence;
+ /* The MonoSsapreFatherExpression node of the "grand father" */
+ struct MonoSsapreFatherExpression *grand_father;
+} MonoSsapreFatherExpression;
+
/*
* A "real" occurrence.
*/
typedef struct MonoSsapreExpressionOccurrence {
/* The occurrence in the CFG */
MonoInst *occurrence;
+ /* The "father" of this occurrence in the inst tree (if the occurrence is */
+ /* part of a compound expression, otherwise it is NULL) */
+ MonoSsapreFatherExpression *father_in_tree;
/* The tree just before the occurrence in the CFG (if the occurrence must */
/* saved into a temporary, the definition will be placed just after that tree) */
MonoInst *previous_tree;
MonoSsapreExpressionDescription description;
/* Next occurrence of this expression */
struct MonoSsapreExpressionOccurrence *next;
- /* Previois occurrence of this expression */
+ /* Previous occurrence of this expression */
struct MonoSsapreExpressionOccurrence *previous;
/* True if this occurrence is the first in its BB */
gboolean is_first_in_bb;
struct MonoSsapreExpressionOccurrence *next_in_renaming_stack;
/* Class number of this occurrence */
- gssize redundancy_class;
+ int redundancy_class;
/* The index of the temporary of this occurrence in the cfg->vars array */
- gssize variable_index;
+ int variable_index;
/* Points to the real occurrence defining this occurrence (NULL otherwise) */
struct MonoSsapreExpressionOccurrence *defined_by_real_occurrence;
/* Points to the BB containing the PHI defining this occurrence (NULL otherwise) */
struct MonoSsapreExpression *father;
struct MonoSsapreExpression *previous;
struct MonoSsapreExpression *next;
- gssize tree_size;
+ int tree_size;
+
+ /* Next expression to be processed in the worklist */
+ struct MonoSsapreExpression *next_in_queue;
} MonoSsapreExpression;
/*
MonoBitSet *left_argument_bb_bitset;
MonoBitSet *right_argument_bb_bitset;
+ /* The depth of the dominator tree */
+ int dt_depth;
+
/* The expression worklist */
MonoSsapreExpression *worklist;
+ /* The expression queue head */
+ MonoSsapreExpression *first_in_queue;
+ /* The expression queue tail */
+ MonoSsapreExpression *last_in_queue;
+
/* The expression being processed */
MonoSsapreExpression *current_expression;
+ /* The expression being allocated */
+ MonoSsapreExpressionOccurrence *current_occurrence;
/* The BB on top of the renaming stack (if "top_of_renaming_stack" is NULL */
/* but this is not, then the top of the stack is the PHI in this BB) */
/* The number of generated class numbers */
int number_of_classes;
+ /* The number of occurrences scheduled for reloading/insertion */
+ /* (used to decide if the redundancy is worth eliminating) */
+ int occurrences_scheduled_for_reloading;
+ int arguments_scheduled_for_insertion;
+ int dominating_arguments_scheduled_for_insertion;
+
/* Statistics fields (per expression) */
int saved_occurrences;
int reloaded_occurrences;
int inserted_occurrences;
int unaltered_occurrences;
int added_phis;
+
+#if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
+ gboolean expression_is_handled_father;
+#endif
} MonoSsapreWorkArea;