?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
2009-01-07 Zoltan Varga <vargaz@gmail.com>
[mono-project.git] / mono / mini / ssapre.c
blobdc36bfb0f763644d1895a1f4b9811c2aec49d2ed
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 #include <string.h>
11 #include <stdio.h>
12 #include <math.h>
13
14 #include <mono/metadata/debug-helpers.h>
15 #include <mono/metadata/opcodes.h>
16
17 #include "config.h"
18
19 #include "inssel.h"
20
21 #include "ssapre.h"
22
23 /* Disable for now to save space since it is not yet ported to linear IR */
24 #if 0
25
26 #ifndef DISABLE_SSA
27
28 /* Logging conditions */
29 #define DUMP_LEVEL (4)
30 #define TRACE_LEVEL (3)
31 #define STATISTICS_LEVEL (2)
32 #define LOG_LEVEL (1)
33 #define DUMP_SSAPRE (area->cfg->verbose_level >= DUMP_LEVEL)
34 #define TRACE_SSAPRE (area->cfg->verbose_level >= TRACE_LEVEL)
35 #define STATISTICS_SSAPRE (area->cfg->verbose_level >= STATISTICS_LEVEL)
36 #define LOG_SSAPRE (area->cfg->verbose_level >= LOG_LEVEL)
37
38 /* "Bottom" symbol definition (see paper) */
39 #define BOTTOM_REDUNDANCY_CLASS (-1)
40
41 /* Various printing functions... */
42 static void
43 print_argument (MonoSsapreExpressionArgument *argument) {
44 switch (argument->type) {
45 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
46 printf ("ANY");
47 break;
48 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
49 printf ("NONE");
50 break;
51 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
52 printf ("ORIGINAL_VARIABLE %d", argument->argument.original_variable);
53 break;
54 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
55 printf ("SSA_VARIABLE %d", argument->argument.ssa_variable);
56 break;
57 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
58 printf ("INTEGER_CONSTANT %d", argument->argument.integer_constant);
59 break;
60 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
61 printf ("LONG_COSTANT %lld", (long long)*(argument->argument.long_constant));
62 break;
63 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
64 printf ("FLOAT_COSTANT %f", *(argument->argument.float_constant));
65 break;
66 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
67 printf ("DOUBLE_COSTANT %f", *(argument->argument.double_constant));
68 break;
69 default:
70 printf ("UNKNOWN: %d", argument->type);
71 }
72 }
73
74
75 static void
76 print_expression_description (MonoSsapreExpressionDescription *expression_description) {
77 if (expression_description->opcode != 0) {
78 printf ("%s ([", mono_inst_name (expression_description->opcode) );
79 print_argument (&(expression_description->left_argument));
80 printf ("],[");
81 print_argument (&(expression_description->right_argument));
82 printf ("])");
83 } else {
84 printf ("ANY");
85 }
86 }
87
88 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
89 static void
90 snprint_argument (GString *string, MonoSsapreExpressionArgument *argument) {
91 switch (argument->type) {
92 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
93 g_string_append_printf (string, "ANY");
94 break;
95 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
96 g_string_append_printf (string, "NONE");
97 break;
98 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
99 g_string_append_printf (string, "ORIGINAL_VARIABLE %d", argument->argument.original_variable);
100 break;
101 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
102 g_string_append_printf (string, "SSA_VARIABLE %d", argument->argument.ssa_variable);
103 break;
104 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
105 g_string_append_printf (string, "INTEGER_CONSTANT %d", argument->argument.integer_constant);
106 break;
107 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
108 g_string_append_printf (string, "LONG_COSTANT %lld", *(argument->argument.long_constant));
109 break;
110 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
111 g_string_append_printf (string, "FLOAT_COSTANT %f", *(argument->argument.float_constant));
112 break;
113 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
114 g_string_append_printf (string, "DOUBLE_COSTANT %f", *(argument->argument.double_constant));
115 break;
116 default:
117 g_string_append_printf (string, "UNKNOWN: %d", argument->type);
118 }
119 }
120
121 static void
122 snprint_expression_description (GString *string, MonoSsapreExpressionDescription *expression_description) {
123 if (expression_description->opcode != 0) {
124 g_string_append_printf (string, "%s ([", mono_inst_name (expression_description->opcode) );
125 snprint_argument (string, &(expression_description->left_argument));
126 g_string_append_printf (string, "],[");
127 snprint_argument (string, &(expression_description->right_argument));
128 g_string_append_printf (string, "])");
129 } else {
130 g_string_append_printf (string, "ANY");
131 }
132 }
133 #endif
134
135 #define GBOOLEAN_TO_STRING(b) ((b)?"TRUE":"FALSE")
136
137 static void
138 print_expression_occurrence (MonoSsapreExpressionOccurrence *occurrence, int number) {
139 printf (" ([%d][bb %d [ID %d]][class %d]: ", number, occurrence->bb_info->cfg_dfn, occurrence->bb_info->bb->block_num, occurrence->redundancy_class);
140 print_expression_description (&(occurrence->description));
141 if (occurrence->is_first_in_bb) {
142 printf (" [FIRST in BB]");
143 }
144 if (occurrence->is_last_in_bb) {
145 printf (" [LAST in BB]");
146 }
147 printf (" (save = %s)", GBOOLEAN_TO_STRING (occurrence->save));
148 printf (" (reload = %s)", GBOOLEAN_TO_STRING (occurrence->reload));
149 printf ("\n");
150 occurrence = occurrence->next;
151 }
152
153 static void
154 print_expression_occurrences (MonoSsapreExpressionOccurrence *occurrences) {
155 int i = 0;
156 while (occurrences != NULL) {
157 i++;
158 print_expression_occurrence (occurrences, i);
159 occurrences = occurrences->next;
160 }
161 }
162
163 static void
164 print_worklist (MonoSsapreExpression *expression) {
165 if (expression != NULL) {
166 print_worklist (expression->previous);
167
168 printf ("{%d}: ", expression->tree_size);
169 print_expression_description (&(expression->description));
170 printf ("\n");
171 print_expression_occurrences (expression->occurrences);
172
173 print_worklist (expression->next);
174 }
175 }
176
177 static void
178 print_bb_info (MonoSsapreBBInfo *bb_info, gboolean print_occurrences) {
179 int i;
180 MonoSsapreExpressionOccurrence *current_occurrence = bb_info->first_expression_in_bb;
181
182 printf ("bb %d [ID %d]: IN { ", bb_info->cfg_dfn, bb_info->bb->block_num);
183 for (i = 0; i < bb_info->in_count; i++) {
184 printf ("%d [ID %d] ", bb_info->in_bb [i]->cfg_dfn, bb_info->in_bb [i]->bb->block_num);
185 }
186 printf ("}, OUT {");
187 for (i = 0; i < bb_info->out_count; i++) {
188 printf ("%d [ID %d] ", bb_info->out_bb [i]->cfg_dfn, bb_info->out_bb [i]->bb->block_num);
189 }
190 printf ("}");
191 if (bb_info->next_interesting_bb != NULL) {
192 printf (", NEXT %d [ID %d]", bb_info->next_interesting_bb->cfg_dfn, bb_info->next_interesting_bb->bb->block_num);
193 }
194 if (bb_info->dt_covered_by_interesting_BBs) {
195 printf (" (COVERED)");
196 } else {
197 printf (" (NEVER DOWN SAFE)");
198 }
199 printf ("\n");
200 if (bb_info->has_phi) {
201 printf (" PHI, class %d [ ", bb_info->phi_redundancy_class);
202 for (i = 0; i < bb_info->in_count; i++) {
203 int argument_class = bb_info->phi_arguments_classes [i];
204 if (argument_class != BOTTOM_REDUNDANCY_CLASS) {
205 printf ("%d ", argument_class);
206 } else {
207 printf ("BOTTOM ");
208 }
209 }
210 printf ("]\n(phi_defines_a_real_occurrence:%s) (phi_is_down_safe:%s) (phi_can_be_available:%s) (phi_is_later:%s)\n",
211 GBOOLEAN_TO_STRING (bb_info->phi_defines_a_real_occurrence), GBOOLEAN_TO_STRING (bb_info->phi_is_down_safe),
212 GBOOLEAN_TO_STRING (bb_info->phi_can_be_available), GBOOLEAN_TO_STRING (bb_info->phi_is_later));
213 }
214 if (print_occurrences) {
215 i = 0;
216 while ((current_occurrence != NULL) && (current_occurrence->bb_info == bb_info)) {
217 print_expression_occurrence (current_occurrence, i);
218 current_occurrence = current_occurrence->next;
219 i++;
220 }
221 }
222 if (bb_info->has_phi_argument) {
223 printf (" PHI ARGUMENT, class ");
224 if (bb_info->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) {
225 printf ("%d ", bb_info->phi_argument_class);
226 } else {
227 printf ("BOTTOM ");
228 }
229 if (bb_info->phi_argument_defined_by_real_occurrence != NULL) {
230 printf ("(Defined by real occurrence %d)", bb_info->phi_argument_defined_by_real_occurrence->redundancy_class);
231 } else if (bb_info->phi_argument_defined_by_phi != NULL) {
232 printf ("(Defined by phi %d)", bb_info->phi_argument_defined_by_phi->phi_redundancy_class);
233 } else {
234 printf ("(Undefined)");
235 }
236 printf (" (real occurrence arguments: left ");
237 if (bb_info->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) {
238 printf ("%d ", bb_info->phi_argument_left_argument_version);
239 } else {
240 printf ("NONE ");
241 }
242 printf (", right ");
243 if (bb_info->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) {
244 printf ("%d ", bb_info->phi_argument_right_argument_version);
245 } else {
246 printf ("NONE ");
247 }
248 printf (")\n(phi_argument_has_real_use:%s) (phi_argument_needs_insert:%s) (phi_argument_has_been_processed:%s)\n",
249 GBOOLEAN_TO_STRING (bb_info->phi_argument_has_real_use), GBOOLEAN_TO_STRING (bb_info->phi_argument_needs_insert),
250 GBOOLEAN_TO_STRING (bb_info->phi_argument_has_been_processed));
251 }
252 }
253
254 static void
255 print_bb_infos (MonoSsapreWorkArea *area) {
256 int i;
257 for (i = 0; i < area->num_bblocks; i++) {
258 MonoSsapreBBInfo *bb_info = &(area->bb_infos [i]);
259 print_bb_info (bb_info, TRUE);
260 }
261 }
262
263 static void
264 print_interesting_bb_infos (MonoSsapreWorkArea *area) {
265 MonoSsapreBBInfo *current_bb;
266
267 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
268 print_bb_info (current_bb, FALSE);
269 }
270 }
271
272 static void dump_code (MonoSsapreWorkArea *area) {
273 int i;
274
275 for (i = 0; i < area->num_bblocks; i++) {
276 MonoSsapreBBInfo *current_bb = &(area->bb_infos [i]);
277 MonoInst *current_inst;
278
279 print_bb_info (current_bb, TRUE);
280 MONO_BB_FOR_EACH_INS (current_bb->bb, current_inst)
281 mono_print_tree_nl (current_inst);
282 }
283 }
284
285 /*
286 * Given a MonoInst, it tries to describe it as an expression argument.
287 * If this is not possible, the result will be of type
288 * MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY.
289 */
290 static void
291 analyze_argument (MonoInst *argument, MonoSsapreExpressionArgument *result) {
292 switch (argument->opcode) {
293 case CEE_LDIND_I1:
294 case CEE_LDIND_U1:
295 case CEE_LDIND_I2:
296 case CEE_LDIND_U2:
297 case CEE_LDIND_I4:
298 case CEE_LDIND_U4:
299 case CEE_LDIND_I8:
300 case CEE_LDIND_I:
301 case CEE_LDIND_R4:
302 case CEE_LDIND_R8:
303 case CEE_LDIND_REF:
304 if ((argument->inst_left->opcode == OP_LOCAL) || (argument->inst_left->opcode == OP_ARG)) {
305 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
306 result->argument.ssa_variable = argument->inst_left->inst_c0;
307 } else {
308 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
309 }
310 break;
311 case OP_ICONST:
312 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT;
313 result->argument.integer_constant = argument->inst_c0;
314 break;
315 case OP_I8CONST:
316 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT;
317 result->argument.long_constant = &(argument->inst_l);
318 break;
319 case OP_R4CONST:
320 if (! isnan (*((float*)argument->inst_p0))) {
321 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT;
322 result->argument.float_constant = (float*)argument->inst_p0;
323 } else {
324 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
325 }
326 break;
327 case OP_R8CONST:
328 if (! isnan (*((double*)argument->inst_p0))) {
329 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT;
330 result->argument.double_constant = (double*)argument->inst_p0;
331 } else {
332 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
333 }
334 break;
335 default:
336 result->type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
337 }
338 }
339
340
341 /*
342 * Given a MonoInst, it tries to describe it as an expression.
343 * If this is not possible, the result will have opcode 0.
344 */
345 static void
346 analyze_expression (MonoInst *expression, MonoSsapreExpressionDescription *result) {
347 switch (expression->opcode) {
348 #define SSAPRE_SPECIFIC_OPS 1
349 #define OPDEF(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) case a1:
350 #include "simple-cee-ops.h"
351 #undef OPDEF
352 #define MINI_OP(a1,a2) case a1:
353 #include "simple-mini-ops.h"
354 #undef MINI_OP
355 #undef SSAPRE_SPECIFIC_OPS
356 if ( (expression->type == STACK_I4) ||
357 (expression->type == STACK_PTR) ||
358 (expression->type == STACK_MP) ||
359 (expression->type == STACK_I8) ||
360 (expression->type == STACK_R8) ) {
361 if (mono_burg_arity [expression->opcode] > 0) {
362 result->opcode = expression->opcode;
363 analyze_argument (expression->inst_left, &(result->left_argument));
364 if (mono_burg_arity [expression->opcode] > 1) {
365 analyze_argument (expression->inst_right, &(result->right_argument));
366 } else {
367 result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT;
368 }
369 } else {
370 result->opcode = 0;
371 }
372 } else {
373 result->opcode = 0;
374 //~ if (expression->type != 0) {
375 //~ MonoType *type = mono_type_from_stack_type (expression);
376 //~ printf ("SSAPRE refuses opcode %s (%d) with type %s (%d)\n", mono_inst_name (expression->opcode), expression->opcode, mono_type_full_name (type), expression->type);
377 //~ } else {
378 //~ printf ("SSAPRE cannot really handle expression of opcode %s (%d)\n", mono_inst_name (expression->opcode), expression->opcode);
379 //~ }
380 }
381 break;
382 default:
383 result->opcode = 0;
384 result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
385 result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
386 }
387 //~ switch (expression->opcode) {
388 //~ case CEE_ADD:
389 //~ if ((result->left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT) &&
390 //~ (result->right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT)) {
391 //~ break;
392 //~ }
393 //~ case CEE_LDELEMA:
394 //~ case CEE_LDLEN:
395 //~ result->opcode = 0;
396 //~ result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
397 //~ result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY;
398 //~ }
399 }
400
401 /*
402 * Given an expression description, if any of its arguments has type
403 * MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE it transforms it to a
404 * MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE, converting the
405 * variable index to its "original" one.
406 * The resulting description is OK for a "MonoSsapreExpression" (the
407 * initial description came from a "MonoSsapreExpressionOccurrence").
408 */
409 static void
410 convert_ssa_variables_to_original_names (MonoSsapreExpressionDescription *result, MonoSsapreExpressionDescription *expression, MonoCompile *cfg) {
411 gssize original_variable;
412
413 result->opcode = expression->opcode;
414 if (expression->left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
415 result->left_argument = expression->left_argument;
416 } else {
417 result->left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE;
418 original_variable = MONO_VARINFO (cfg, expression->left_argument.argument.ssa_variable)->reg;
419 if (original_variable >= 0) {
420 result->left_argument.argument.original_variable = original_variable;
421 } else {
422 result->left_argument.argument.original_variable = expression->left_argument.argument.ssa_variable;
423 }
424 }
425 if (expression->right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
426 result->right_argument = expression->right_argument;
427 } else {
428 result->right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE;
429 original_variable = MONO_VARINFO (cfg, expression->right_argument.argument.ssa_variable)->reg;
430 if (original_variable >= 0) {
431 result->right_argument.argument.original_variable = original_variable;
432 } else {
433 result->right_argument.argument.original_variable = expression->right_argument.argument.ssa_variable;
434 }
435 }
436 }
437
438 /*
439 * Given a MonoInst, checks if it is a phi definition.
440 */
441 static gboolean
442 is_phi_definition (MonoInst *definition) {
443 if (definition != NULL) {
444 switch (definition->opcode) {
445 case CEE_STIND_REF:
446 case CEE_STIND_I:
447 case CEE_STIND_I4:
448 case CEE_STIND_I1:
449 case CEE_STIND_I2:
450 case CEE_STIND_I8:
451 case CEE_STIND_R4:
452 case CEE_STIND_R8:
453 if ((definition->inst_left->opcode == OP_LOCAL) &&
454 (definition->inst_right->opcode == OP_PHI)) {
455 return TRUE;
456 } else {
457 return FALSE;
458 }
459 default:
460 return FALSE;
461 }
462 } else {
463 return FALSE;
464 }
465 }
466
467 /*
468 * Given a variable index, checks if it is a phi definition
469 * (it assumes the "area" is visible).
470 */
471 #define IS_PHI_DEFINITION(v) is_phi_definition (MONO_VARINFO (area->cfg, v)->def)
472
473 /*
474 * Given a variable index, checks if it is a phi definition.
475 * If it is so, it returns the array of integers pointed to by the phi MonoInst
476 * (the one containing the length and the phi arguments), otherwise returns NULL.
477 */
478 static int*
479 get_phi_definition (MonoCompile *cfg, gssize variable) {
480 MonoInst *definition = MONO_VARINFO (cfg, variable)->def;
481 if (is_phi_definition (definition) && (definition->inst_left->inst_c0 == variable)) {
482 return definition->inst_right->inst_phi_args;
483 } else {
484 return NULL;
485 }
486 }
487
488 /*
489 * Given a variable index, returns the BB where the variable is defined.
490 * If the variable appears to have no definition, it returns the entry BB
491 * (the logic is that if it has no definition it is an argument, or a sort
492 * of constant, and in both cases it is defined in the entry BB).
493 */
494 static MonoSsapreBBInfo*
495 get_bb_info_of_definition (MonoSsapreWorkArea *area, gssize variable) {
496 MonoBasicBlock *def_bb = MONO_VARINFO (area->cfg, variable)->def_bb;
497 if (def_bb != NULL) {
498 return area->bb_infos_in_cfg_dfn_order [def_bb->dfn];
499 } else {
500 return area->bb_infos;
501 }
502 }
503
504 /*
505 * Given:
506 * - a variable index,
507 * - a BB (the "current" BB), and
508 * - a "phi argument index" (or index in the "in_bb" of the current BB),
509 * it checks if the variable is a phi.
510 * If it is so, it returns the variable index at the in_bb corresponding to
511 * the given index, otherwise it return the variable index unchanged.
512 * The logic is to return the variable version at the given predecessor BB.
513 */
514 static gssize
515 get_variable_version_at_predecessor_bb (MonoSsapreWorkArea *area, gssize variable, MonoSsapreBBInfo *current_bb, int phi_operand) {
516 MonoSsapreBBInfo *definition_bb = get_bb_info_of_definition (area, variable);
517 int *phi_definition = get_phi_definition (area->cfg, variable);
518 if ((definition_bb == current_bb) && (phi_definition != NULL)) {
519 return phi_definition [phi_operand + 1];
520 } else {
521 return variable;
522 }
523 }
524
525 /*
526 * Adds an expression to an autobalancing binary tree of expressions.
527 * Returns the new tree root (it can be different from "tree" because of the
528 * autobalancing).
529 */
530 static MonoSsapreExpression*
531 add_expression_to_tree (MonoSsapreExpression *tree, MonoSsapreExpression *expression) {
532 MonoSsapreExpression *subtree;
533 MonoSsapreExpression **subtree_reference;
534 int comparison;
535 gssize max_tree_depth, max_subtree_size;
536
537 if (tree == NULL) {
538 expression->previous = NULL;
539 expression->next = NULL;
540 expression->tree_size = 1;
541 return expression;
542 }
543
544 tree->tree_size++;
545
546 comparison = MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS (expression->description, tree->description);
547 if (comparison > 0) {
548 if (tree->next != NULL) {
549 subtree = tree->next;
550 subtree_reference = &(tree->next);
551 } else {
552 tree->next = expression;
553 expression->father = tree;
554 expression->previous = NULL;
555 expression->next = NULL;
556 expression->tree_size = 1;
557 return tree;
558 }
559 } else if (comparison < 0) {
560 if (tree->previous != NULL) {
561 subtree = tree->previous;
562 subtree_reference = &(tree->previous);
563 } else {
564 tree->previous = expression;
565 expression->father = tree;
566 expression->previous = NULL;
567 expression->next = NULL;
568 expression->tree_size = 1;
569 return tree;
570 }
571 } else {
572 g_assert_not_reached ();
573 return NULL;
574 }
575
576 MONO_SSAPRE_MAX_TREE_DEPTH (tree->tree_size, max_tree_depth);
577 max_subtree_size = (1 << max_tree_depth) -1;
578
579 if (subtree->tree_size < max_subtree_size) {
580 *subtree_reference = add_expression_to_tree (subtree, expression);
581 (*subtree_reference)->father = tree;
582 return tree;
583 } else {
584 MonoSsapreExpression *other_subtree;
585 MonoSsapreExpression *border_expression;
586 MonoSsapreExpression *border_expression_subtree;
587 MonoSsapreExpression **border_expression_reference_from_father;
588 int comparison_with_border;
589
590 border_expression = subtree;
591 if (comparison > 0) {
592 other_subtree = tree->previous;
593 MONO_SSAPRE_GOTO_FIRST_EXPRESSION (border_expression);
594 border_expression_subtree = border_expression->next;
595 border_expression_reference_from_father = &(border_expression->father->previous);
596 } else if (comparison < 0) {
597 other_subtree = tree->next;
598 MONO_SSAPRE_GOTO_LAST_EXPRESSION (border_expression);
599 border_expression_subtree = border_expression->previous;
600 border_expression_reference_from_father = &(border_expression->father->next);
601 } else {
602 g_assert_not_reached ();
603 return NULL;
604 }
605 comparison_with_border = MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS (expression->description, border_expression->description);
606
607 if ((comparison + comparison_with_border) != 0) {
608 MonoSsapreExpression *border_expression_iterator = border_expression->father;
609 while (border_expression_iterator != tree) {
610 border_expression_iterator->tree_size--;
611 border_expression_iterator = border_expression_iterator->father;
612 }
613
614 if (border_expression != subtree) {
615 *border_expression_reference_from_father = border_expression_subtree;
616 } else {
617 subtree = border_expression_subtree;
618 }
619 if (border_expression_subtree != NULL) {
620 border_expression_subtree->father = border_expression->father;
621 }
622
623 if (comparison > 0) {
624 border_expression->previous = add_expression_to_tree (other_subtree, tree);
625 border_expression->next = add_expression_to_tree (subtree, expression);
626 } else if (comparison < 0) {
627 border_expression->previous = add_expression_to_tree (subtree, expression);
628 border_expression->next = add_expression_to_tree (other_subtree, tree);
629 } else {
630 g_assert_not_reached ();
631 return NULL;
632 }
633 border_expression->tree_size = 1 + border_expression->previous->tree_size + border_expression->next->tree_size;
634 return border_expression;
635 } else {
636 if (comparison > 0) {
637 expression->previous = add_expression_to_tree (other_subtree, tree);
638 expression->next = subtree;
639 } else if (comparison < 0) {
640 expression->previous = subtree;
641 expression->next = add_expression_to_tree (other_subtree, tree);
642 } else {
643 g_assert_not_reached ();
644 return NULL;
645 }
646 expression->tree_size = 1 + expression->previous->tree_size + expression->next->tree_size;
647 return expression;
648 }
649 }
650 }
651
652 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
653 static char *mono_ssapre_expression_name = NULL;
654 static gboolean
655 check_ssapre_expression_name (MonoSsapreWorkArea *area, MonoSsapreExpressionDescription *expression_description) {
656 if (area->expression_is_handled_father) {
657 return TRUE;
658 }
659 if (mono_ssapre_expression_name == NULL) {
660 mono_ssapre_expression_name = getenv ("MONO_SSAPRE_EXPRESSION_NAME");
661 }
662 if (mono_ssapre_expression_name != NULL) {
663 GString *expression_name = g_string_new_len ("", 256);
664 gboolean return_value;
665 snprint_expression_description (expression_name, expression_description);
666 if (strstr (expression_name->str, mono_ssapre_expression_name) != NULL) {
667 return_value = TRUE;
668 } else {
669 return_value = FALSE;
670 }
671 g_string_free (expression_name, TRUE);
672 return return_value;
673 } else {
674 return TRUE;
675 }
676 }
677 #endif
678
679 /*
680 * Adds an expression to the worklist (putting the current occurrence as first
681 * occurrence of this expression).
682 */
683 static void
684 add_expression_to_worklist (MonoSsapreWorkArea *area) {
685 MonoSsapreExpressionOccurrence *occurrence = area->current_occurrence;
686 MonoSsapreExpression *expression = (MonoSsapreExpression*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpression));
687
688 convert_ssa_variables_to_original_names (&(expression->description), &(occurrence->description), area->cfg);
689
690 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
691 if (! check_ssapre_expression_name (area, &(expression->description))) return;
692 #endif
693
694 expression->type = mono_type_from_stack_type (occurrence->occurrence);
695 expression->occurrences = NULL;
696 expression->last_occurrence = NULL;
697 expression->next_in_queue = NULL;
698 if (area->last_in_queue != NULL) {
699 area->last_in_queue->next_in_queue = expression;
700 } else {
701 area->first_in_queue = expression;
702 }
703 area->last_in_queue = expression;
704 MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE (expression, occurrence);
705
706 area->worklist = add_expression_to_tree (area->worklist, expression);
707 area->worklist->father = NULL;
708 }
709
710 /*
711 * Adds the current expression occurrence to the worklist.
712 * If its expression is not yet in the worklist, it is created.
713 */
714 static void
715 add_occurrence_to_worklist (MonoSsapreWorkArea *area) {
716 MonoSsapreExpressionDescription description;
717 MonoSsapreExpression *current_expression;
718 int comparison;
719
720 convert_ssa_variables_to_original_names (&description, &(area->current_occurrence->description), area->cfg);
721 current_expression = area->worklist;
722
723 do {
724 if (current_expression != NULL) {
725 comparison = MONO_COMPARE_SSAPRE_EXPRESSION_DESCRIPTIONS (description, current_expression->description);
726
727 if (comparison > 0) {
728 current_expression = current_expression->next;
729 } else if (comparison < 0) {
730 current_expression = current_expression->previous;
731 } else {
732 MONO_SSAPRE_ADD_EXPRESSION_OCCURRANCE (current_expression, area->current_occurrence);
733 }
734 } else {
735 add_expression_to_worklist (area);
736 comparison = 0;
737 }
738 } while (comparison != 0);
739
740 area->current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreExpressionOccurrence));
741 }
742
743 /*
744 * Process a MonoInst, and of it is a valid expression add it to the worklist.
745 */
746 static void
747 process_inst (MonoSsapreWorkArea *area, MonoInst* inst, MonoInst* previous_inst, MonoSsapreFatherExpression*** father_in_tree, MonoSsapreBBInfo *bb_info) {
748 MonoSsapreFatherExpression** left_father_in_tree = NULL;
749 MonoSsapreFatherExpression** right_father_in_tree = NULL;
750
751 if (mono_burg_arity [inst->opcode] > 0) {
752 process_inst (area, inst->inst_left, previous_inst, &left_father_in_tree, bb_info);
753 if (mono_burg_arity [inst->opcode] > 1) {
754 process_inst (area, inst->inst_right, previous_inst, &right_father_in_tree, bb_info);
755 }
756 }
757
758 analyze_expression (inst, &(area->current_occurrence->description));
759 if (area->current_occurrence->description.opcode != 0) {
760 if ((left_father_in_tree != NULL) || (right_father_in_tree != NULL)) {
761 MonoSsapreFatherExpression *current_inst_as_father = (MonoSsapreFatherExpression*) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreFatherExpression));
762 current_inst_as_father->father_occurrence = inst;
763 current_inst_as_father->grand_father = NULL;
764 *father_in_tree = &(current_inst_as_father->grand_father);
765 if (left_father_in_tree != NULL) {
766 *left_father_in_tree = current_inst_as_father;
767 }
768 if (right_father_in_tree != NULL) {
769 *right_father_in_tree = current_inst_as_father;
770 }
771 if (DUMP_SSAPRE) {
772 printf ("Expression '");
773 mono_print_tree (inst);
774 printf ("' is a potential father ( ");
775 if (left_father_in_tree != NULL) {
776 printf ("LEFT ");
777 }
778 if (right_father_in_tree != NULL) {
779 printf ("RIGHT ");
780 }
781 printf (")\n");
782 }
783 } else if ((area->current_occurrence->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) &&
784 (area->current_occurrence->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY)) {
785 area->current_occurrence->occurrence = inst;
786 area->current_occurrence->previous_tree = previous_inst;
787 area->current_occurrence->bb_info = bb_info;
788 area->current_occurrence->is_first_in_bb = FALSE;
789 area->current_occurrence->is_last_in_bb = FALSE;
790
791 area->current_occurrence->father_in_tree = NULL;
792 *father_in_tree = &(area->current_occurrence->father_in_tree);
793
794 add_occurrence_to_worklist (area);
795 } else {
796 *father_in_tree = NULL;
797 }
798 } else {
799 *father_in_tree = NULL;
800 }
801 }
802
803 /*
804 * Process a BB, and (recursively) all its children in the dominator tree.
805 * The result is that all the expressions end up in the worklist, and the
806 * auxiliary MonoSsapreBBInfo fields (dt_dfn, dt_descendants) are initialized
807 * (with all the info that comes from the MonoBasicBlock).
808 */
809 static void
810 process_bb (MonoSsapreWorkArea *area, MonoBasicBlock *bb, int *dt_dfn, int *upper_descendants, int current_depth) {
811 MonoSsapreBBInfo *bb_info;
812 int descendants;
813 GSList *dominated_bb;
814 MonoInst* current_inst;
815 MonoInst* previous_inst;
816 MonoSsapreFatherExpression** dummy_father_in_tree;
817
818 bb_info = &(area->bb_infos [*dt_dfn]);
819 bb_info->dt_dfn = *dt_dfn;
820 (*dt_dfn)++;
821 bb_info->cfg_dfn = bb->dfn;
822 area->bb_infos_in_cfg_dfn_order [bb->dfn] = bb_info;
823 bb_info->in_count = bb->in_count;
824 bb_info->out_count = bb->out_count;
825 bb_info->dfrontier = bb->dfrontier;
826 bb_info->bb = bb;
827 bb_info->in_bb = (MonoSsapreBBInfo**) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreBBInfo*) * (bb->in_count));
828 bb_info->out_bb = (MonoSsapreBBInfo**) mono_mempool_alloc (area->mempool, sizeof (MonoSsapreBBInfo*) * (bb->out_count));
829 bb_info->phi_arguments_classes = (int*) mono_mempool_alloc (area->mempool, sizeof (int) * (bb->in_count));
830
831 bb_info->phi_insertion_point = NULL;
832
833 previous_inst = NULL;
834 MONO_BB_FOR_EACH_INS (bb, current_inst) {
835 /* Ugly hack to fix missing variable definitions */
836 /* (the SSA construction code should have done it already!) */
837 switch (current_inst->opcode) {
838 case CEE_STIND_REF:
839 case CEE_STIND_I:
840 case CEE_STIND_I4:
841 case CEE_STIND_I1:
842 case CEE_STIND_I2:
843 case CEE_STIND_I8:
844 case CEE_STIND_R4:
845 case CEE_STIND_R8:
846 if ((current_inst->inst_left->opcode == OP_LOCAL) || (current_inst->inst_left->opcode == OP_ARG)) {
847 int variable_index = current_inst->inst_left->inst_c0;
848
849 if (MONO_VARINFO (area->cfg, variable_index)->def_bb == NULL) {
850 if (area->cfg->verbose_level >= 4) {
851 printf ("SSAPRE WARNING: variable %d has no definition, fixing.\n", variable_index);
852 }
853 MONO_VARINFO (area->cfg, variable_index)->def_bb = bb_info->bb;
854 }
855 }
856 break;
857 default:
858 break;
859 }
860
861 if (is_phi_definition (current_inst)) {
862 bb_info->phi_insertion_point = current_inst;
863 }
864
865 if (mono_burg_arity [current_inst->opcode] > 0) {
866 process_inst (area, current_inst->inst_left, previous_inst, &dummy_father_in_tree, bb_info);
867 if (mono_burg_arity [current_inst->opcode] > 1) {
868 process_inst (area, current_inst->inst_right, previous_inst, &dummy_father_in_tree, bb_info);
869 }
870 }
871
872 previous_inst = current_inst;
873 }
874
875 if (current_depth > area->dt_depth) {
876 area->dt_depth = current_depth;
877 }
878 descendants = 0;
879 for (dominated_bb = bb->dominated; dominated_bb != NULL; dominated_bb = dominated_bb->next) {
880 process_bb (area, (MonoBasicBlock*) (dominated_bb->data), dt_dfn, &descendants, current_depth + 1);
881 }
882 bb_info->dt_descendants = descendants;
883 *upper_descendants += (descendants + 1);
884 }
885
886 /*
887 * Reset the MonoSsapreBBInfo fields that must be recomputed for each expression.
888 */
889 static void
890 clean_bb_infos (MonoSsapreWorkArea *area) {
891 int i;
892 for (i = 0; i < area->num_bblocks; i++) {
893 MonoSsapreBBInfo *bb_info = &(area->bb_infos [i]);
894 bb_info->dt_covered_by_interesting_BBs = FALSE;
895 bb_info->has_phi = FALSE;
896 bb_info->phi_defines_a_real_occurrence = FALSE;
897 bb_info->phi_is_down_safe = FALSE;
898 bb_info->phi_can_be_available = FALSE;
899 bb_info->phi_is_later = FALSE;
900 bb_info->phi_redundancy_class = BOTTOM_REDUNDANCY_CLASS;
901 bb_info->phi_variable_index = BOTTOM_REDUNDANCY_CLASS;
902 bb_info->has_phi_argument = FALSE;
903 bb_info->phi_argument_has_real_use = FALSE;
904 bb_info->phi_argument_needs_insert = FALSE;
905 bb_info->phi_argument_has_been_processed = FALSE;
906 bb_info->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
907 bb_info->phi_argument_variable_index = BOTTOM_REDUNDANCY_CLASS;
908 bb_info->phi_argument_defined_by_real_occurrence = NULL;
909 bb_info->phi_argument_defined_by_phi = NULL;
910 bb_info->phi_argument_left_argument_version = BOTTOM_REDUNDANCY_CLASS;
911 bb_info->phi_argument_right_argument_version = BOTTOM_REDUNDANCY_CLASS;
912 bb_info->first_expression_in_bb = NULL;
913 bb_info->next_interesting_bb = NULL;
914 bb_info->next_in_renaming_stack = NULL;
915 bb_info->top_of_local_renaming_stack = NULL;
916 }
917 }
918
919 /*
920 * Reset the MonoSsapreWorkArea fields that must be recomputed for each expression.
921 */
922 static void
923 clean_area_infos (MonoSsapreWorkArea *area) {
924 mono_bitset_clear_all (area->left_argument_bb_bitset);
925 mono_bitset_clear_all (area->right_argument_bb_bitset);
926 area->num_vars = area->cfg->num_varinfo;
927 area->top_of_renaming_stack = NULL;
928 area->bb_on_top_of_renaming_stack = NULL;
929 area->first_interesting_bb = NULL;
930 area->saved_occurrences = 0;
931 area->reloaded_occurrences = 0;
932 area->inserted_occurrences = 0;
933 area->unaltered_occurrences = 0;
934 area->added_phis = 0;
935 clean_bb_infos (area);
936 }
937
938 /*
939 * Utility function to combine the dominance frontiers of a set of BBs.
940 */
941 static void
942 compute_combined_dfrontier (MonoSsapreWorkArea *area, MonoBitSet* result, MonoBitSet *bblocks)
943 {
944 int i;
945 mono_bitset_clear_all (result);
946 mono_bitset_foreach_bit (bblocks, i, area->num_bblocks) {
947 mono_bitset_union (result, area->bb_infos_in_cfg_dfn_order [i]->dfrontier);
948 }
949 }
950
951 /*
952 * Utility function to compute the combined dominance frontier of a set of BBs.
953 */
954 static void
955 compute_combined_iterated_dfrontier (MonoSsapreWorkArea *area, MonoBitSet *result, MonoBitSet *bblocks, MonoBitSet *buffer)
956 {
957 gboolean change = TRUE;
958
959 compute_combined_dfrontier (area, result, bblocks);
960 do {
961 change = FALSE;
962 compute_combined_dfrontier (area, buffer, result);
963 mono_bitset_union (buffer, result);
964
965 if (!mono_bitset_equal (buffer, result)) {
966 mono_bitset_copyto (buffer, result);
967 change = TRUE;
968 }
969 } while (change);
970 }
971
972 /*
973 * See paper, section 5.1, definition of "Dominate"
974 */
975 static gboolean
976 dominates (MonoSsapreBBInfo *dominator, MonoSsapreBBInfo *dominated) {
977 if ((dominator->dt_dfn <= dominated->dt_dfn) && (dominated->dt_dfn <= (dominator->dt_dfn + dominator->dt_descendants))) {
978 return TRUE;
979 } else {
980 return FALSE;
981 }
982 }
983
984 /*
985 * See paper, figure 18, function Set_var_phis
986 */
987 static void process_phi_variable_in_phi_insertion (MonoSsapreWorkArea *area, gssize variable, MonoBitSet *phi_bbs) {
988 int* phi_definition = get_phi_definition (area->cfg, variable);
989
990 if (phi_definition != NULL) {
991 int definition_bb = MONO_VARINFO (area->cfg, variable)->def_bb->dfn;
992 if (! mono_bitset_test (phi_bbs, definition_bb)) {
993 int i;
994 mono_bitset_set (phi_bbs, definition_bb);
995 for (i = 0; i < *phi_definition; i++) {
996 process_phi_variable_in_phi_insertion (area, phi_definition [i+1], phi_bbs);
997 }
998 }
999 }
1000 }
1001
1002 /*
1003 * See paper, figure 18, function phi_insertion
1004 */
1005 static void
1006 phi_insertion (MonoSsapreWorkArea *area, MonoSsapreExpression *expression) {
1007 MonoSsapreExpressionOccurrence *current_expression = NULL;
1008 MonoSsapreExpressionOccurrence *previous_expression = NULL;
1009 MonoSsapreBBInfo *current_bb = NULL;
1010 MonoSsapreBBInfo *previous_interesting_bb = NULL;
1011 int i, j, current_bb_dt_dfn;
1012 int top;
1013 MonoSsapreBBInfo **stack;
1014 gboolean *interesting_stack;
1015
1016 mono_bitset_clear_all (area->expression_occurrences_buffer);
1017 for (current_expression = expression->occurrences; current_expression != NULL; current_expression = current_expression->next) {
1018 mono_bitset_set (area->expression_occurrences_buffer, current_expression->bb_info->cfg_dfn);
1019 if (current_expression->description.left_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
1020 process_phi_variable_in_phi_insertion (area, current_expression->description.left_argument.argument.ssa_variable, area->left_argument_bb_bitset);
1021 }
1022 if (current_expression->description.right_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) {
1023 process_phi_variable_in_phi_insertion (area, current_expression->description.right_argument.argument.ssa_variable, area->right_argument_bb_bitset);
1024 }
1025
1026 if (previous_expression != NULL) {
1027 if (previous_expression->bb_info != current_expression->bb_info) {
1028 previous_expression->is_last_in_bb = TRUE;
1029 current_expression->is_first_in_bb = TRUE;
1030 current_expression->bb_info->first_expression_in_bb = current_expression;
1031 }
1032 } else {
1033 current_expression->is_first_in_bb = TRUE;
1034 current_expression->bb_info->first_expression_in_bb = current_expression;
1035 }
1036
1037 previous_expression = current_expression;
1038 }
1039 previous_expression->is_last_in_bb = TRUE;
1040
1041 compute_combined_iterated_dfrontier (area, area->iterated_dfrontier_buffer, area->expression_occurrences_buffer, area->bb_iteration_buffer);
1042
1043 mono_bitset_union (area->iterated_dfrontier_buffer, area->left_argument_bb_bitset);
1044 mono_bitset_union (area->iterated_dfrontier_buffer, area->right_argument_bb_bitset);
1045
1046 mono_bitset_foreach_bit (area->iterated_dfrontier_buffer, i, area->num_bblocks) {
1047 area->bb_infos_in_cfg_dfn_order [i]->has_phi = TRUE;
1048 area->bb_infos_in_cfg_dfn_order [i]->phi_can_be_available = TRUE;
1049 for (j = 0; j < area->bb_infos_in_cfg_dfn_order [i]->in_count; j++) {
1050 area->bb_infos_in_cfg_dfn_order [i]->in_bb [j]->has_phi_argument = TRUE;
1051 }
1052 }
1053
1054 top = -1;
1055 stack = (MonoSsapreBBInfo **) alloca (sizeof (MonoSsapreBBInfo *) * (area->dt_depth));
1056 interesting_stack = (gboolean *) alloca (sizeof (gboolean) * (area->dt_depth));
1057
1058 /* Setup the list of interesting BBs, and their "DT coverage" */
1059 for (current_bb = area->bb_infos, current_bb_dt_dfn = 0; current_bb_dt_dfn < area->num_bblocks; current_bb++, current_bb_dt_dfn++) {
1060 gboolean current_bb_is_interesting;
1061
1062 if ((current_bb->first_expression_in_bb != NULL) || (current_bb->has_phi) || (current_bb->has_phi_argument)) {
1063 current_bb_is_interesting = TRUE;
1064
1065 if (previous_interesting_bb != NULL) {
1066 previous_interesting_bb->next_interesting_bb = current_bb;
1067 } else {
1068 area->first_interesting_bb = current_bb;
1069 }
1070 previous_interesting_bb = current_bb;
1071 } else {
1072 current_bb_is_interesting = FALSE;
1073 }
1074
1075 if (top >= 0) {
1076 while ((top >= 0) && (! dominates (stack [top], current_bb))) {
1077 gboolean top_covers_his_idominator = ((interesting_stack [top]) || (stack [top]->dt_covered_by_interesting_BBs));
1078
1079 if ((top > 0) && (! top_covers_his_idominator)) {
1080 stack [top - 1]->dt_covered_by_interesting_BBs = FALSE;
1081 }
1082
1083 top--;
1084 }
1085 } else {
1086 top = -1;
1087 }
1088
1089 top++;
1090
1091 interesting_stack [top] = current_bb_is_interesting;
1092 stack [top] = current_bb;
1093 if (stack [top]->dt_descendants == 0) {
1094 stack [top]->dt_covered_by_interesting_BBs = FALSE;
1095 } else {
1096 stack [top]->dt_covered_by_interesting_BBs = TRUE;
1097 }
1098 }
1099 while (top > 0) {
1100 gboolean top_covers_his_idominator = ((interesting_stack [top]) || (stack [top]->dt_covered_by_interesting_BBs));
1101
1102 if (! top_covers_his_idominator) {
1103 stack [top - 1]->dt_covered_by_interesting_BBs = FALSE;
1104 }
1105
1106 top--;
1107 }
1108 }
1109
1110 /*
1111 * Macro that pushes a real occurrence on the stack
1112 */
1113 #define PUSH_REAL_OCCURRENCE(o) do{\
1114 if (area->bb_on_top_of_renaming_stack != (o)->bb_info) { \
1115 (o)->bb_info->next_in_renaming_stack = area->bb_on_top_of_renaming_stack; \
1116 area->bb_on_top_of_renaming_stack =(o)->bb_info; \
1117 (o)->next_in_renaming_stack = NULL; \
1118 } else { \
1119 (o)->next_in_renaming_stack = area->top_of_renaming_stack; \
1120 } \
1121 (o)->bb_info->top_of_local_renaming_stack = (o); \
1122 area->top_of_renaming_stack = (o); \
1123 area->bb_on_top_of_renaming_stack->phi_argument_has_real_use = FALSE; \
1124 } while(0)
1125
1126 /*
1127 * Macro that pushes a PHI occurrence on the stack
1128 */
1129 #define PUSH_PHI_OCCURRENCE(b) do{\
1130 if (area->bb_on_top_of_renaming_stack != (b)) { \
1131 (b)->next_in_renaming_stack = area->bb_on_top_of_renaming_stack; \
1132 area->bb_on_top_of_renaming_stack = (b); \
1133 } \
1134 (b)->top_of_local_renaming_stack = NULL; \
1135 area->top_of_renaming_stack = NULL; \
1136 area->bb_on_top_of_renaming_stack->phi_argument_has_real_use = FALSE; \
1137 } while(0)
1138
1139 /*
1140 * See paper, section 5.4.
1141 * The two passes are coded sequentially (no separate "rename1" and "rename2" functions).
1142 */
1143 static void
1144 renaming_pass (MonoSsapreWorkArea *area) {
1145 MonoSsapreBBInfo *current_bb = NULL;
1146 MonoSsapreBBInfo *previous_bb = NULL;
1147 MonoSsapreExpressionOccurrence *current_expression = NULL;
1148 gssize current_class = 0;
1149
1150 /* This loop is "rename1" */
1151 for (current_bb = area->first_interesting_bb, previous_bb = NULL; current_bb != NULL; previous_bb = current_bb, current_bb = current_bb->next_interesting_bb) {
1152 if (previous_bb != NULL) {
1153 if (! dominates (previous_bb, current_bb)) {
1154 /* This means we are backtracking in the dominator tree */
1155 MonoSsapreBBInfo *first_interesting_dominator = current_bb->idominator;
1156 while ((first_interesting_dominator->next_interesting_bb == NULL) && (first_interesting_dominator->idominator != NULL)) {
1157 first_interesting_dominator = first_interesting_dominator->idominator;
1158 }
1159 current_bb->phi_argument_has_real_use = first_interesting_dominator->phi_argument_has_real_use;
1160
1161 if ((area->bb_on_top_of_renaming_stack != NULL) && (area->top_of_renaming_stack == NULL) && (previous_bb->phi_argument_has_real_use == FALSE)) {
1162 if (TRACE_SSAPRE) {
1163 printf ("Clearing down safe in PHI %d because of backtracking (current block is [bb %d [ID %d]], previous block is [bb %d [ID %d]])\n",
1164 area->bb_on_top_of_renaming_stack->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num, previous_bb->cfg_dfn, previous_bb->bb->block_num);
1165 }
1166 area->bb_on_top_of_renaming_stack->phi_is_down_safe = FALSE;
1167 }
1168 while ((area->bb_on_top_of_renaming_stack != NULL) && ! dominates (area->bb_on_top_of_renaming_stack, current_bb)) {
1169 MonoSsapreBBInfo *top_bb = area->bb_on_top_of_renaming_stack;
1170 if (top_bb->next_in_renaming_stack != NULL) {
1171 area->top_of_renaming_stack = top_bb->next_in_renaming_stack->top_of_local_renaming_stack;
1172 } else {
1173 area->top_of_renaming_stack = NULL;
1174 }
1175 area->bb_on_top_of_renaming_stack = top_bb->next_in_renaming_stack;
1176 }
1177 if (DUMP_SSAPRE) {
1178 printf ("Backtracked, getting real use flag from bb %d [ID %d], current top of the stack is class ",
1179 first_interesting_dominator->cfg_dfn, first_interesting_dominator->bb->block_num);
1180 if (area->top_of_renaming_stack != NULL) {
1181 printf ("%d\n", area->top_of_renaming_stack->redundancy_class);
1182 } else if (area->bb_on_top_of_renaming_stack != NULL) {
1183 printf ("%d\n", area->bb_on_top_of_renaming_stack->phi_redundancy_class);
1184 } else {
1185 printf ("BOTTOM\n");
1186 }
1187 }
1188 } else {
1189 /* With no backtracking we just propagate the flag */
1190 current_bb->phi_argument_has_real_use = previous_bb->phi_argument_has_real_use;
1191 }
1192 } else {
1193 /* Start condition */
1194 current_bb->phi_argument_has_real_use = FALSE;
1195 }
1196 if (DUMP_SSAPRE) {
1197 printf ("Real use flag is %s at the beginning of block [bb %d [ID %d]]\n",
1198 GBOOLEAN_TO_STRING (current_bb->phi_argument_has_real_use), current_bb->cfg_dfn, current_bb->bb->block_num);
1199 }
1200
1201 if (current_bb->has_phi) {
1202 if (current_bb->dt_covered_by_interesting_BBs) {
1203 current_bb->phi_is_down_safe = TRUE;
1204 } else {
1205 current_bb->phi_is_down_safe = FALSE;
1206 }
1207 current_bb->phi_redundancy_class = current_class;
1208 current_class++;
1209 PUSH_PHI_OCCURRENCE (current_bb);
1210 if (TRACE_SSAPRE) {
1211 printf ("Assigning class %d to PHI in bb %d [ID %d]\n",
1212 current_bb->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1213 }
1214 }
1215
1216 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1217 if (area->top_of_renaming_stack != NULL) {
1218 MonoSsapreExpressionOccurrence *top = area->top_of_renaming_stack;
1219
1220 if (((current_expression->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) ||
1221 (current_expression->description.left_argument.argument.ssa_variable == top->description.left_argument.argument.ssa_variable)) &&
1222 ((current_expression->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE) ||
1223 (current_expression->description.right_argument.argument.ssa_variable == top->description.right_argument.argument.ssa_variable))) {
1224 current_expression->redundancy_class = top->redundancy_class;
1225 current_expression->defined_by_real_occurrence = top;
1226 if (DUMP_SSAPRE) {
1227 printf ("Using class %d for occurrence '", current_expression->redundancy_class);
1228 print_expression_description (&(current_expression->description));
1229 printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1230 }
1231 } else {
1232 current_expression->redundancy_class = current_class;
1233 current_class++;
1234 current_expression->defined_by_real_occurrence = NULL;
1235 PUSH_REAL_OCCURRENCE (current_expression);
1236 if (TRACE_SSAPRE) {
1237 printf ("Assigning class %d to occurrence '", current_expression->redundancy_class);
1238 print_expression_description (&(current_expression->description));
1239 printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1240 }
1241 }
1242 current_expression->defined_by_phi = NULL;
1243 } else if (area->bb_on_top_of_renaming_stack != NULL) {
1244 MonoSsapreBBInfo *phi_bb = area->bb_on_top_of_renaming_stack;
1245 gssize left_argument_version = ((current_expression->description.left_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE)?
1246 (current_expression->description.left_argument.argument.ssa_variable):BOTTOM_REDUNDANCY_CLASS);
1247 gssize right_argument_version = ((current_expression->description.right_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE)?
1248 (current_expression->description.right_argument.argument.ssa_variable):BOTTOM_REDUNDANCY_CLASS);
1249
1250 /* See remark in section 5.4 about the dominance relation between PHI */
1251 /* occurrences and phi definitions */
1252 MonoSsapreBBInfo *left_argument_definition_bb = ((left_argument_version != BOTTOM_REDUNDANCY_CLASS)?
1253 (get_bb_info_of_definition (area, left_argument_version)):NULL);
1254 MonoSsapreBBInfo *right_argument_definition_bb = ((right_argument_version != BOTTOM_REDUNDANCY_CLASS)?
1255 (get_bb_info_of_definition (area, right_argument_version)):NULL);
1256
1257 gboolean left_same_class_condition = ((left_argument_definition_bb == NULL) || ((left_argument_definition_bb != phi_bb) ? dominates (left_argument_definition_bb, phi_bb) :
1258 (IS_PHI_DEFINITION (left_argument_version) ? TRUE : FALSE)));
1259 gboolean right_same_class_condition = ((right_argument_definition_bb == NULL) || ((right_argument_definition_bb != phi_bb) ? dominates (right_argument_definition_bb, phi_bb) :
1260 (IS_PHI_DEFINITION (right_argument_version) ? TRUE : FALSE)));
1261
1262 if (left_same_class_condition && right_same_class_condition) {
1263 int phi_argument;
1264
1265 phi_bb->phi_defines_a_real_occurrence = TRUE;
1266 current_bb->phi_argument_has_real_use = TRUE;
1267 current_expression->redundancy_class = phi_bb->phi_redundancy_class;
1268 current_expression->defined_by_phi = phi_bb;
1269
1270 /* If this PHI was not "covered", it is not down safe. */
1271 /* However, if the real occurrence is in the same BB, it */
1272 /* actually is down safe */
1273 if (phi_bb == current_bb) {
1274 if (DUMP_SSAPRE) {
1275 printf ("PHI in bb %d [ID %d] defined occurrence %d in the same BB, so it is down safe\n", phi_bb->cfg_dfn, phi_bb->bb->block_num, current_expression->redundancy_class);
1276 }
1277 phi_bb->phi_is_down_safe = TRUE;
1278 }
1279
1280 /*
1281 * Major difference from the paper here...
1282 * Instead of maintaining "set_for_rename2" (see figure 20), we just
1283 * compute "phi_argument_left_argument_version" (and right) here, and
1284 * use that in rename2, saving us the hassle of maintaining a set
1285 * data structure (and the related allocations).
1286 */
1287 for (phi_argument = 0; phi_argument < phi_bb->in_count; phi_argument++) {
1288 MonoSsapreBBInfo *previous_bb = phi_bb->in_bb [phi_argument];
1289 if (left_argument_version != BOTTOM_REDUNDANCY_CLASS) {
1290 previous_bb->phi_argument_left_argument_version = get_variable_version_at_predecessor_bb (area,
1291 left_argument_version, phi_bb, phi_argument);
1292 }
1293 if (right_argument_version != BOTTOM_REDUNDANCY_CLASS) {
1294 previous_bb->phi_argument_right_argument_version = get_variable_version_at_predecessor_bb (area,
1295 right_argument_version, phi_bb, phi_argument);
1296 }
1297 }
1298 if (DUMP_SSAPRE) {
1299 printf ("Using class %d for occurrence '", current_expression->redundancy_class);
1300 print_expression_description (&(current_expression->description));
1301 printf ("' in bb %d [ID %d] (Real use flag is now TRUE)\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1302 }
1303 } else {
1304 current_expression->redundancy_class = current_class;
1305 current_class++;
1306 current_expression->defined_by_phi = NULL;
1307 PUSH_REAL_OCCURRENCE (current_expression);
1308 phi_bb->phi_is_down_safe = FALSE;
1309 if (TRACE_SSAPRE) {
1310 printf ("Assigning class %d to occurrence '", current_expression->redundancy_class);
1311 print_expression_description (&(current_expression->description));
1312 printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1313 printf ("Clearing down safe in PHI %d because of real occurrence %d\n",
1314 phi_bb->phi_redundancy_class, current_expression->redundancy_class);
1315 }
1316 }
1317 current_expression->defined_by_real_occurrence = NULL;
1318 } else {
1319 current_expression->redundancy_class = current_class;
1320 current_class++;
1321 current_expression->defined_by_real_occurrence = NULL;
1322 current_expression->defined_by_phi = NULL;
1323 PUSH_REAL_OCCURRENCE (current_expression);
1324 if (TRACE_SSAPRE) {
1325 printf ("Assigning class %d to occurrence '", current_expression->redundancy_class);
1326 print_expression_description (&(current_expression->description));
1327 printf ("' in bb %d [ID %d]\n", current_bb->cfg_dfn, current_bb->bb->block_num);
1328 }
1329 }
1330 }
1331
1332 if (current_bb->has_phi_argument) {
1333 if (area->top_of_renaming_stack != NULL) {
1334 current_bb->phi_argument_defined_by_real_occurrence = area->top_of_renaming_stack;
1335 current_bb->phi_argument_class = area->top_of_renaming_stack->redundancy_class;
1336 } else if (area->bb_on_top_of_renaming_stack != NULL) {
1337 current_bb->phi_argument_defined_by_phi = area->bb_on_top_of_renaming_stack;
1338 current_bb->phi_argument_class = area->bb_on_top_of_renaming_stack->phi_redundancy_class;
1339 } else {
1340 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1341 }
1342 if ((DUMP_SSAPRE) && (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS)) {
1343 printf ("Temporarily using class %d for PHI argument in bb %d [ID %d]\n",
1344 current_bb->phi_argument_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1345 }
1346 }
1347 }
1348 if ((area->bb_on_top_of_renaming_stack != NULL) && (area->top_of_renaming_stack == NULL) && (previous_bb->phi_argument_has_real_use == FALSE)) {
1349 if (TRACE_SSAPRE) {
1350 printf ("Clearing down safe in PHI %d because of backtracking (previous block is [bb %d [ID %d]])\n",
1351 area->bb_on_top_of_renaming_stack->phi_redundancy_class, previous_bb->cfg_dfn, previous_bb->bb->block_num);
1352 }
1353 area->bb_on_top_of_renaming_stack->phi_is_down_safe = FALSE;
1354 }
1355 area->number_of_classes = current_class;
1356
1357 /* This loop is "rename2" */
1358 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1359 if (current_bb->has_phi_argument) {
1360 if ((current_bb->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) || (current_bb->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS)) {
1361 if (current_bb->phi_argument_defined_by_real_occurrence != NULL) {
1362 if (((current_bb->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) &&
1363 (current_bb->phi_argument_left_argument_version != current_bb->phi_argument_defined_by_real_occurrence->description.left_argument.argument.ssa_variable)) ||
1364 ((current_bb->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) &&
1365 (current_bb->phi_argument_right_argument_version != current_bb->phi_argument_defined_by_real_occurrence->description.right_argument.argument.ssa_variable))) {
1366 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1367 }
1368 } else if (current_bb->phi_argument_defined_by_phi != NULL) {
1369 MonoSsapreBBInfo *phi_bb = current_bb->phi_argument_defined_by_phi;
1370 MonoSsapreBBInfo *left_argument_definition_bb = (current_bb->phi_argument_left_argument_version != BOTTOM_REDUNDANCY_CLASS) ?
1371 get_bb_info_of_definition (area, current_bb->phi_argument_left_argument_version) : NULL;
1372 MonoSsapreBBInfo *right_argument_definition_bb = (current_bb->phi_argument_right_argument_version != BOTTOM_REDUNDANCY_CLASS) ?
1373 get_bb_info_of_definition (area, current_bb->phi_argument_right_argument_version) : NULL;
1374 /* See remark in section 5.4 about the dominance relation between PHI */
1375 /* occurrences and phi definitions */
1376 gboolean left_bottom_condition = ((left_argument_definition_bb != NULL) && ! ((left_argument_definition_bb != phi_bb) ? dominates (left_argument_definition_bb, phi_bb) :
1377 (IS_PHI_DEFINITION (current_bb->phi_argument_left_argument_version) ? TRUE : FALSE)));
1378 gboolean right_bottom_condition = ((right_argument_definition_bb != NULL) && ! ((right_argument_definition_bb != phi_bb) ? dominates (right_argument_definition_bb, phi_bb) :
1379 (IS_PHI_DEFINITION (current_bb->phi_argument_right_argument_version) ? TRUE : FALSE)));
1380
1381 if (left_bottom_condition || right_bottom_condition) {
1382 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1383 }
1384 } else {
1385 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1386 }
1387 } else {
1388 current_bb->phi_argument_class = BOTTOM_REDUNDANCY_CLASS;
1389 }
1390
1391 if (current_bb->phi_argument_class == BOTTOM_REDUNDANCY_CLASS) {
1392 if ((current_bb->phi_argument_defined_by_phi != NULL) && (! current_bb->phi_argument_has_real_use)) {
1393 if (TRACE_SSAPRE) {
1394 printf ("Clearing down safe in PHI %d because PHI argument in block [bb %d [ID %d]] is BOTTOM\n",
1395 current_bb->phi_argument_defined_by_phi->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1396 }
1397 current_bb->phi_argument_defined_by_phi->phi_is_down_safe = FALSE;
1398 }
1399 current_bb->phi_argument_has_real_use = FALSE;
1400
1401 if (DUMP_SSAPRE) {
1402 printf ("Cleared real use flag in block [bb %d [ID %d]] because phi argument class is now BOTTOM\n",
1403 current_bb->cfg_dfn, current_bb->bb->block_num);
1404 }
1405 }
1406 }
1407 }
1408
1409 /* Final quick pass to copy the result of "rename2" into PHI nodes */
1410 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1411 if (current_bb->has_phi) {
1412 int i;
1413 for (i = 0; i < current_bb->in_count; i++) {
1414 current_bb->phi_arguments_classes [i] = current_bb->in_bb [i]->phi_argument_class;
1415 }
1416 }
1417 }
1418 }
1419
1420 #undef PUSH_REAL_OCCURRENCE
1421 #undef PUSH_PHI_OCCURRENCE
1422
1423 /*
1424 * See paper, figure 8
1425 */
1426 static void
1427 reset_down_safe (MonoSsapreBBInfo *phi_argument) {
1428 if ((phi_argument->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) && (! phi_argument->phi_argument_has_real_use) && (phi_argument->phi_argument_defined_by_phi != NULL) && (phi_argument->phi_argument_defined_by_phi->phi_is_down_safe)) {
1429 int i;
1430 MonoSsapreBBInfo *phi = phi_argument->phi_argument_defined_by_phi;
1431 phi->phi_is_down_safe = FALSE;
1432 for (i = 0; i < phi->in_count; i++) {
1433 reset_down_safe (phi->in_bb [i]);
1434 }
1435 }
1436 }
1437
1438 /*
1439 * See paper, figure 8
1440 */
1441 static void
1442 down_safety (MonoSsapreWorkArea *area) {
1443 MonoSsapreBBInfo *current_bb = NULL;
1444
1445 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1446 if (current_bb->has_phi) {
1447 if (! current_bb->phi_is_down_safe) {
1448 int i;
1449 for (i = 0; i < current_bb->in_count; i++) {
1450 reset_down_safe (current_bb->in_bb [i]);
1451 }
1452 }
1453 }
1454 }
1455 }
1456
1457 /*
1458 * See paper, figure 10
1459 */
1460 static void
1461 reset_can_be_available (MonoSsapreWorkArea *area, MonoSsapreBBInfo *phi) {
1462 MonoSsapreBBInfo *current_bb = NULL;
1463
1464 if (DUMP_SSAPRE) {
1465 printf ("Resetting availability for PHI %d in block [bb %d [ID %d]]\n",
1466 phi->phi_redundancy_class, phi->cfg_dfn, phi->bb->block_num);
1467 }
1468
1469 phi->phi_can_be_available = FALSE;
1470 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1471 if (current_bb->has_phi) {
1472 gboolean phi_is_interesting = FALSE;
1473 int i;
1474
1475 for (i = 0; i < current_bb->in_count; i++) {
1476 MonoSsapreBBInfo *phi_argument = current_bb->in_bb [i];
1477 if ((phi_argument->phi_argument_class == current_bb->phi_redundancy_class) && (! phi_argument->phi_argument_has_real_use)) {
1478 phi_is_interesting = TRUE;
1479 break;
1480 }
1481 }
1482
1483 if (phi_is_interesting && (! current_bb->phi_is_down_safe) && (current_bb->phi_can_be_available)) {
1484 reset_can_be_available (area, current_bb);
1485 }
1486 }
1487 }
1488 }
1489
1490 /*
1491 * See paper, figure 10
1492 */
1493 static void
1494 compute_can_be_available (MonoSsapreWorkArea *area) {
1495 MonoSsapreBBInfo *current_bb = NULL;
1496
1497 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1498 if (current_bb->has_phi) {
1499 if ((! current_bb->phi_is_down_safe) && (current_bb->phi_can_be_available)) {
1500 gboolean phi_is_interesting = FALSE;
1501 int i;
1502
1503 for (i = 0; i < current_bb->in_count; i++) {
1504 if (current_bb->phi_arguments_classes [i] == BOTTOM_REDUNDANCY_CLASS) {
1505 phi_is_interesting = TRUE;
1506 break;
1507 }
1508 }
1509
1510 if (phi_is_interesting) {
1511 if (DUMP_SSAPRE) {
1512 printf ("Availability computation working on PHI %d in block [bb %d [ID %d]]\n",
1513 current_bb->phi_redundancy_class, current_bb->cfg_dfn, current_bb->bb->block_num);
1514 }
1515 reset_can_be_available (area, current_bb);
1516 }
1517 }
1518 }
1519 }
1520 }
1521
1522 /*
1523 * See paper, figure 10
1524 */
1525 static void
1526 reset_later (MonoSsapreWorkArea *area, MonoSsapreBBInfo *phi) {
1527 MonoSsapreBBInfo *current_bb = NULL;
1528
1529 if (phi->phi_is_later) {
1530 phi->phi_is_later = FALSE;
1531 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1532 if (current_bb->has_phi) {
1533 gboolean phi_is_interesting = FALSE;
1534 int i;
1535
1536 for (i = 0; i < current_bb->in_count; i++) {
1537 MonoSsapreBBInfo *phi_argument = current_bb->in_bb [i];
1538 if (phi_argument->phi_argument_class == current_bb->phi_redundancy_class) {
1539 phi_is_interesting = TRUE;
1540 break;
1541 }
1542 }
1543
1544 if (phi_is_interesting) {
1545 reset_later (area, current_bb);
1546 }
1547 }
1548 }
1549 }
1550 }
1551
1552 /*
1553 * See paper, figure 10
1554 */
1555 static void
1556 compute_later (MonoSsapreWorkArea *area) {
1557 MonoSsapreBBInfo *current_bb = NULL;
1558
1559 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1560 if (current_bb->has_phi) {
1561 current_bb->phi_is_later = current_bb->phi_can_be_available;
1562 }
1563 }
1564 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1565 if (current_bb->has_phi) {
1566 if (current_bb->phi_is_later) {
1567 gboolean phi_is_interesting = FALSE;
1568 int i;
1569
1570 for (i = 0; i < current_bb->in_count; i++) {
1571 MonoSsapreBBInfo *phi_argument = current_bb->in_bb [i];
1572 if ((phi_argument->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) && (phi_argument->phi_argument_has_real_use)) {
1573 phi_is_interesting = TRUE;
1574 break;
1575 }
1576 }
1577
1578 if (phi_is_interesting) {
1579 reset_later (area, current_bb);
1580 }
1581 }
1582 }
1583 }
1584 }
1585
1586 /*
1587 * See paper, figure 12, function Finalize_1
1588 */
1589 static void finalize_availability_and_reload (MonoSsapreWorkArea *area, MonoSsapreAvailabilityTableElement *availability_table) {
1590 MonoSsapreBBInfo *current_bb = NULL;
1591 MonoSsapreExpressionOccurrence *current_expression = NULL;
1592
1593 area->occurrences_scheduled_for_reloading = 0;
1594 area->arguments_scheduled_for_insertion = 0;
1595 area->dominating_arguments_scheduled_for_insertion = 0;
1596
1597 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1598 if (current_bb->has_phi) {
1599 if (current_bb->phi_can_be_available && ! current_bb->phi_is_later) {
1600 availability_table [current_bb->phi_redundancy_class].class_defined_by_phi = current_bb;
1601 }
1602 }
1603
1604 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1605 MonoSsapreBBInfo *defining_bb = availability_table [current_expression->redundancy_class].class_defined_by_phi;
1606 if (defining_bb == NULL && availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence != NULL) {
1607 defining_bb = availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence->bb_info;
1608 }
1609 if (defining_bb != NULL) {
1610 if (! dominates (defining_bb, current_bb)) {
1611 defining_bb = NULL;
1612 }
1613 }
1614
1615 if (defining_bb == NULL) {
1616 current_expression->reload = FALSE;
1617 availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence = current_expression;
1618 } else {
1619 current_expression->reload = TRUE;
1620
1621 area->occurrences_scheduled_for_reloading ++;
1622
1623 current_expression->defined_by_phi = availability_table [current_expression->redundancy_class].class_defined_by_phi;
1624 current_expression->defined_by_real_occurrence = availability_table [current_expression->redundancy_class].class_defined_by_real_occurrence;
1625 }
1626
1627 current_expression->save = FALSE;
1628 }
1629
1630 if (current_bb->has_phi_argument) {
1631 MonoSsapreBBInfo *phi_bb = current_bb->out_bb [0];
1632 if (((phi_bb->phi_can_be_available) && (! phi_bb->phi_is_later)) &&
1633 ((current_bb->phi_argument_class == BOTTOM_REDUNDANCY_CLASS) ||
1634 ((current_bb->phi_argument_has_real_use == FALSE) && (current_bb->phi_argument_defined_by_phi != NULL) &&
1635 (! ((current_bb->phi_argument_defined_by_phi->phi_can_be_available) && (! current_bb->phi_argument_defined_by_phi->phi_is_later)))
1636 ))) {
1637 current_bb->phi_argument_needs_insert = TRUE;
1638
1639 area->arguments_scheduled_for_insertion ++;
1640 if (dominates (current_bb, phi_bb)) {
1641 area->dominating_arguments_scheduled_for_insertion ++;
1642 }
1643
1644 current_bb->phi_argument_defined_by_real_occurrence = NULL;
1645 current_bb->phi_argument_defined_by_phi = NULL;
1646 } else {
1647 current_bb->phi_argument_needs_insert = FALSE;
1648 if (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) {
1649 current_bb->phi_argument_defined_by_real_occurrence = availability_table [current_bb->phi_argument_class].class_defined_by_real_occurrence;
1650 current_bb->phi_argument_defined_by_phi = availability_table [current_bb->phi_argument_class].class_defined_by_phi;
1651 }
1652 }
1653
1654 current_bb->phi_argument_has_been_processed = FALSE;
1655 }
1656 }
1657 }
1658
1659 /*
1660 * See paper, figure 13, function Set_save
1661 */
1662 static void set_save (MonoSsapreBBInfo *phi_occurrance, MonoSsapreExpressionOccurrence *real_occurrance) {
1663 if (real_occurrance != NULL) {
1664 real_occurrance->save = TRUE;
1665 } else if (phi_occurrance != NULL) {
1666 int i;
1667 for (i = 0; i < phi_occurrance->in_count; i++) {
1668 MonoSsapreBBInfo *phi_argument = phi_occurrance->in_bb [i];
1669 if (! phi_argument->phi_argument_has_been_processed) {
1670 phi_argument->phi_argument_has_been_processed = TRUE;
1671 set_save (phi_argument->phi_argument_defined_by_phi, phi_argument->phi_argument_defined_by_real_occurrence);
1672 }
1673 }
1674 }
1675 }
1676
1677 /*
1678 * See paper, figure 13, function Finalize_2 (note that we still don't do
1679 * extraneous PHI elimination, see function Set_replacement)
1680 */
1681 static void finalize_save (MonoSsapreWorkArea *area) {
1682 MonoSsapreBBInfo *current_bb = NULL;
1683 MonoSsapreExpressionOccurrence *current_expression = NULL;
1684
1685 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1686 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1687 if (current_expression->reload) {
1688 set_save (current_expression->defined_by_phi, current_expression->defined_by_real_occurrence);
1689 }
1690 }
1691
1692 if ((current_bb->has_phi_argument) &&
1693 (! current_bb->phi_argument_needs_insert) &&
1694 (current_bb->phi_argument_class != BOTTOM_REDUNDANCY_CLASS) &&
1695 (current_bb->phi_argument_defined_by_real_occurrence != NULL)) {
1696 current_bb->phi_argument_defined_by_real_occurrence->save = TRUE;
1697 }
1698 }
1699 }
1700
1701 #define OP_IS_CHEAP(op) (((op)==CEE_ADD)||((op)==CEE_SUB))
1702 #define EXPRESSION_HAS_ICONST(d) (((d).left_argument.type==MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT)||((d).right_argument.type==MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT))
1703 #define EXPRESSION_IS_CHEAP(d) ((OP_IS_CHEAP ((d).opcode))&&(EXPRESSION_HAS_ICONST ((d))))
1704 #define REDUNDANCY_IS_SMALL(a) (((a)->occurrences_scheduled_for_reloading < 2)&&((a)->dominating_arguments_scheduled_for_insertion < 1))
1705
1706 /*
1707 * Perform all "finalize" steps.
1708 * Return TRUE if we must go on with code_motion.
1709 */
1710 static gboolean finalize (MonoSsapreWorkArea *area) {
1711 MonoSsapreAvailabilityTableElement *availability_table = alloca (sizeof (MonoSsapreAvailabilityTableElement) * (area->number_of_classes));
1712 int i;
1713
1714 for (i = 0; i < area->number_of_classes; i++) {
1715 availability_table[i].class_defined_by_phi = NULL;
1716 availability_table[i].class_defined_by_real_occurrence = NULL;
1717 }
1718
1719 finalize_availability_and_reload (area, availability_table);
1720
1721 /* Tuning: if the redundancy is not worth handling, give up */
1722 if ((EXPRESSION_IS_CHEAP (area->current_expression->description)) && (REDUNDANCY_IS_SMALL (area))) {
1723 return FALSE;
1724 } else {
1725 finalize_save (area);
1726 return TRUE;
1727 }
1728 }
1729
1730 /*
1731 * Macros that help in creating constants
1732 */
1733 #define NEW_INST(dest,op) do { \
1734 (dest) = mono_mempool_alloc0 (area->cfg->mempool, sizeof (MonoInst)); \
1735 (dest)->opcode = (op); \
1736 } while (0)
1737
1738 #define NEW_I4(dest,val) do { \
1739 NEW_INST ((dest), OP_ICONST); \
1740 (dest)->inst_c0 = (val); \
1741 (dest)->type = STACK_I4; \
1742 } while (0)
1743
1744 #define NEW_I8(dest,val) do { \
1745 NEW_INST ((dest), OP_I8CONST); \
1746 (dest)->inst_l = (val); \
1747 (dest)->type = STACK_I8; \
1748 } while (0)
1749
1750 #define NEW_R4(dest,f) do { \
1751 NEW_INST ((dest), OP_R4CONST); \
1752 (dest)->inst_p0 = f; \
1753 (dest)->type = STACK_R8; \
1754 } while (0)
1755
1756 #define NEW_R8(dest,d) do { \
1757 NEW_INST ((dest), OP_R8CONST); \
1758 (dest)->inst_p0 = d; \
1759 (dest)->type = STACK_R8; \
1760 } while (0)
1761
1762 /*
1763 * Create a MonoInst that represents an expression argument
1764 */
1765 static MonoInst*
1766 create_expression_argument (MonoSsapreWorkArea *area, MonoSsapreExpressionArgument *argument) {
1767 MonoInst *result;
1768
1769 switch (argument->type) {
1770 case MONO_SSAPRE_EXPRESSION_ARGUMENT_NOT_PRESENT:
1771 return NULL;
1772 case MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE:
1773 return mono_compile_create_var_load (area->cfg, argument->argument.ssa_variable);
1774 case MONO_SSAPRE_EXPRESSION_ARGUMENT_INTEGER_CONSTANT:
1775 NEW_I4 (result, argument->argument.integer_constant);
1776 return result;
1777 case MONO_SSAPRE_EXPRESSION_ARGUMENT_LONG_COSTANT:
1778 NEW_I8 (result, *(argument->argument.long_constant));
1779 return result;
1780 case MONO_SSAPRE_EXPRESSION_ARGUMENT_FLOAT_COSTANT:
1781 NEW_R4 (result, argument->argument.float_constant);
1782 return result;
1783 case MONO_SSAPRE_EXPRESSION_ARGUMENT_DOUBLE_COSTANT:
1784 NEW_R8 (result, argument->argument.double_constant);
1785 return result;
1786 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE:
1787 case MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY:
1788 default:
1789 g_assert_not_reached ();
1790 return NULL;
1791 }
1792 }
1793
1794 /*
1795 * Create a MonoInst that represents an expression
1796 */
1797 static MonoInst*
1798 create_expression (MonoSsapreWorkArea *area, MonoSsapreExpressionDescription *expression, MonoInst *prototype_occurrence) {
1799 MonoInst *result;
1800 NEW_INST (result, expression->opcode);
1801 *result = *prototype_occurrence;
1802 result->inst_left = create_expression_argument (area, &(expression->left_argument));
1803 result->inst_right = create_expression_argument (area, &(expression->right_argument));
1804 return result;
1805 }
1806
1807 /*
1808 * Handles the father expression of a MonoInst that has been turned
1809 * into a load (eventually inserting it into the worklist).
1810 * Assumes "current_expression->father_in_tree != NULL".
1811 */
1812 static void
1813 handle_father_expression (MonoSsapreWorkArea *area, MonoSsapreExpressionOccurrence *current_expression, MonoInst *previous_tree) {
1814 if (DUMP_SSAPRE) {
1815 printf ("After reload, father expression becomes ");
1816 mono_print_tree_nl (current_expression->father_in_tree->father_occurrence);
1817 }
1818
1819 analyze_expression (current_expression->father_in_tree->father_occurrence, &(area->current_occurrence->description));
1820 if ((area->current_occurrence->description.opcode != 0) &&
1821 (area->current_occurrence->description.left_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY) &&
1822 (area->current_occurrence->description.right_argument.type != MONO_SSAPRE_EXPRESSION_ARGUMENT_ANY)) {
1823 area->current_occurrence->occurrence = current_expression->father_in_tree->father_occurrence;
1824 area->current_occurrence->previous_tree = previous_tree;
1825 area->current_occurrence->father_in_tree = current_expression->father_in_tree->grand_father;
1826 area->current_occurrence->bb_info = current_expression->bb_info;
1827 area->current_occurrence->is_first_in_bb = FALSE;
1828 area->current_occurrence->is_last_in_bb = FALSE;
1829 add_occurrence_to_worklist (area);
1830 }
1831 }
1832
1833 /*
1834 * See paper, section 3.6
1835 */
1836 static void code_motion (MonoSsapreWorkArea *area) {
1837 MonoSsapreBBInfo *current_bb = NULL;
1838 MonoSsapreExpressionOccurrence *current_expression = NULL;
1839 gssize original_variable_index = BOTTOM_REDUNDANCY_CLASS;
1840 MonoInst prototype_occurrence;
1841 prototype_occurrence.opcode = 0;
1842
1843 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1844 if ((current_bb->has_phi) && (current_bb->phi_can_be_available && ! current_bb->phi_is_later)) {
1845 MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL);
1846 current_bb->phi_variable_index = new_var->inst_c0;
1847 if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1848 original_variable_index = new_var->inst_c0;
1849 }
1850 MONO_VARINFO (area->cfg, new_var->inst_c0)->reg = original_variable_index;
1851 MONO_VARINFO (area->cfg, new_var->inst_c0)->def_bb = current_bb->bb;
1852 } else {
1853 current_bb->phi_variable_index = BOTTOM_REDUNDANCY_CLASS;
1854 }
1855
1856 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1857 if (prototype_occurrence.opcode == 0) {
1858 prototype_occurrence = *(current_expression->occurrence);
1859 }
1860 if (current_expression->save) {
1861 MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL);
1862 current_expression->variable_index = new_var->inst_c0;
1863 if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1864 original_variable_index = new_var->inst_c0;
1865 }
1866 MONO_VARINFO (area->cfg, new_var->inst_c0)->reg = original_variable_index;
1867 MONO_VARINFO (area->cfg, new_var->inst_c0)->def_bb = current_bb->bb;
1868 } else {
1869 current_expression->variable_index = BOTTOM_REDUNDANCY_CLASS;
1870 }
1871 }
1872
1873 if ((current_bb->has_phi_argument) && (current_bb->phi_argument_needs_insert)) {
1874 MonoInst *new_var = mono_compile_create_var (area->cfg, area->current_expression->type, OP_LOCAL);
1875 current_bb->phi_argument_variable_index = new_var->inst_c0;
1876 if (original_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1877 original_variable_index = new_var->inst_c0;
1878 }
1879 MONO_VARINFO (area->cfg, new_var->inst_c0)->reg = original_variable_index;
1880 MONO_VARINFO (area->cfg, new_var->inst_c0)->def_bb = current_bb->bb;
1881 } else {
1882 current_bb->phi_argument_variable_index = BOTTOM_REDUNDANCY_CLASS;
1883 }
1884 }
1885
1886 for (current_bb = area->first_interesting_bb; current_bb != NULL; current_bb = current_bb->next_interesting_bb) {
1887 if (current_bb->phi_variable_index != BOTTOM_REDUNDANCY_CLASS) {
1888 MonoInst *phi;
1889 MonoInst *store;
1890 int in_bb;
1891
1892 NEW_INST (phi, OP_PHI);
1893 phi->inst_c0 = MONO_VARINFO (area->cfg, current_bb->phi_variable_index)->reg;
1894 phi->inst_phi_args = mono_mempool_alloc (area->cfg->mempool, (sizeof (int) * ((current_bb->in_count) + 1)));
1895 phi->inst_phi_args [0] = current_bb->in_count;
1896 for (in_bb = 0; in_bb < current_bb->in_count; in_bb++) {
1897 gssize phi_argument_variable_index = current_bb->in_bb [in_bb]->phi_argument_variable_index;
1898 if (phi_argument_variable_index == BOTTOM_REDUNDANCY_CLASS) {
1899 MonoSsapreBBInfo *phi_argument_bb = current_bb->in_bb [in_bb];
1900 if (phi_argument_bb->phi_argument_defined_by_phi !=NULL) {
1901 phi_argument_variable_index = phi_argument_bb->phi_argument_defined_by_phi->phi_variable_index;
1902 } else if (phi_argument_bb->phi_argument_defined_by_real_occurrence !=NULL) {
1903 phi_argument_variable_index = phi_argument_bb->phi_argument_defined_by_real_occurrence->variable_index;
1904 } else {
1905 g_assert_not_reached ();
1906 }
1907 }
1908 phi->inst_phi_args [in_bb + 1] = phi_argument_variable_index;
1909 }
1910 store = mono_compile_create_var_store (area->cfg, current_bb->phi_variable_index, phi);
1911 if (current_bb->phi_insertion_point != NULL) {
1912 store->next = current_bb->phi_insertion_point->next;
1913 current_bb->phi_insertion_point->next = store;
1914 } else {
1915 store->next = current_bb->bb->code;
1916 current_bb->bb->code = store;
1917 }
1918 MONO_VARINFO (area->cfg, current_bb->phi_variable_index)->def = store;
1919 current_bb->phi_insertion_point = store;
1920
1921 area->added_phis ++;
1922 }
1923
1924 for (current_expression = current_bb->first_expression_in_bb; (current_expression != NULL) && (current_expression->bb_info == current_bb); current_expression = current_expression->next) {
1925 gboolean altered = FALSE;
1926 if (current_expression->save) {
1927 MonoInst *store;
1928 MonoInst *moved_expression = mono_mempool_alloc (area->cfg->mempool, sizeof (MonoInst));
1929 *moved_expression = *(current_expression->occurrence);
1930 store = mono_compile_create_var_store (area->cfg, current_expression->variable_index, moved_expression);
1931 if (current_expression->previous_tree != NULL) {
1932 store->next = current_expression->previous_tree->next;
1933 current_expression->previous_tree->next = store;
1934 } else {
1935 store->next = current_bb->bb->code;
1936 current_bb->bb->code = store;
1937 }
1938 MONO_VARINFO (area->cfg, current_expression->variable_index)->def = store;
1939 mono_compile_make_var_load (area->cfg, current_expression->occurrence, current_expression->variable_index);
1940 if (current_expression->father_in_tree != NULL) {
1941 handle_father_expression (area, current_expression, store);
1942 }
1943
1944 area->saved_occurrences ++;
1945 altered = TRUE;
1946 }
1947 if (current_expression->reload) {
1948 gssize variable_index;
1949 if (current_expression->defined_by_phi != NULL) {
1950 variable_index = current_expression->defined_by_phi->phi_variable_index;
1951 } else if (current_expression->defined_by_real_occurrence != NULL) {
1952 variable_index = current_expression->defined_by_real_occurrence->variable_index;
1953 } else {
1954 variable_index = BOTTOM_REDUNDANCY_CLASS;
1955 g_assert_not_reached ();
1956 }
1957 mono_compile_make_var_load (area->cfg, current_expression->occurrence, variable_index);
1958 if (current_expression->father_in_tree != NULL) {
1959 handle_father_expression (area, current_expression, current_expression->previous_tree);
1960 }
1961
1962 area->reloaded_occurrences ++;
1963 altered = TRUE;
1964 }
1965 if (! altered) {
1966 area->unaltered_occurrences ++;
1967 }
1968 }
1969
1970 if (current_bb->phi_argument_variable_index != BOTTOM_REDUNDANCY_CLASS) {
1971 MonoSsapreExpressionDescription expression_description;
1972 MonoInst *inserted_expression;
1973 MonoInst *store;
1974
1975 expression_description = area->current_expression->description;
1976 if (expression_description.left_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE) {
1977 expression_description.left_argument.argument.ssa_variable = current_bb->phi_argument_left_argument_version;
1978 expression_description.left_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
1979 }
1980 if (expression_description.right_argument.type == MONO_SSAPRE_EXPRESSION_ARGUMENT_ORIGINAL_VARIABLE) {
1981 expression_description.right_argument.argument.ssa_variable = current_bb->phi_argument_right_argument_version;
1982 expression_description.right_argument.type = MONO_SSAPRE_EXPRESSION_ARGUMENT_SSA_VARIABLE;
1983 }
1984
1985 inserted_expression = create_expression (area, &expression_description, &prototype_occurrence);
1986 store = mono_compile_create_var_store (area->cfg, current_bb->phi_argument_variable_index, inserted_expression);
1987 MONO_VARINFO (area->cfg, current_bb->phi_argument_variable_index)->def = store;
1988 store->next = NULL;
1989 mono_add_ins_to_end (current_bb->bb, store);
1990
1991 area->inserted_occurrences ++;
1992 }
1993 }
1994 }
1995
1996 /*
1997 * Perform all SSAPRE steps for the current expression
1998 */
1999 static void
2000 process_expression (MonoSsapreWorkArea *area) {
2001 MonoSsapreExpression *expression = area->current_expression;
2002
2003 if (area->cfg->verbose_level >= STATISTICS_LEVEL) {
2004 printf ("SSAPRE STARTS PROCESSING EXPRESSION ");
2005 print_expression_description (&(expression->description));
2006 printf ("\n");
2007 }
2008
2009 clean_area_infos (area);
2010
2011 area->current_expression = expression;
2012 phi_insertion (area, expression);
2013 renaming_pass (area);
2014
2015 if (area->cfg->verbose_level >= TRACE_LEVEL) {
2016 printf ("START SUMMARY OF BB INFOS\n");
2017 print_bb_infos (area);
2018 printf ("END SUMMARY OF BB INFOS\n");
2019 }
2020
2021 down_safety (area);
2022 compute_can_be_available (area);
2023 compute_later (area);
2024 if (finalize (area)) {
2025 code_motion (area);
2026 } else {
2027 if (area->cfg->verbose_level >= TRACE_LEVEL) {
2028 printf ("SSAPRE CODE MOTION SKIPPED\n");
2029 }
2030 }
2031
2032
2033 if (area->cfg->verbose_level >= DUMP_LEVEL) {
2034 printf ("START DUMP OF BB INFOS\n");
2035 dump_code (area);
2036 printf ("END DUMP OF BB INFOS\n");
2037 } else if (area->cfg->verbose_level >= TRACE_LEVEL) {
2038 printf ("START SUMMARY OF BB INFOS\n");
2039 print_interesting_bb_infos (area);
2040 printf ("END SUMMARY OF BB INFOS\n");
2041 }
2042
2043 if (area->cfg->verbose_level >= STATISTICS_LEVEL) {
2044 printf ("STATISTICS: saved_occurrences = %d, reloaded_occurrences = %d, inserted_occurrences = %d, unaltered_occurrences = %d, added_phis = %d\n",
2045 area->saved_occurrences, area->reloaded_occurrences, area->inserted_occurrences, area->unaltered_occurrences, area->added_phis);
2046 }
2047
2048 if (area->cfg->verbose_level >= TRACE_LEVEL) {
2049 printf ("SSAPRE ENDS PROCESSING EXPRESSION ");
2050 print_expression_description (&(expression->description));
2051 printf ("\n");
2052 }
2053 }
2054
2055 #if (MONO_APPLY_SSAPRE_TO_SINGLE_METHOD)
2056 static char*
2057 mono_ssapre_method_name = NULL;
2058 static gboolean check_ssapre_method_name (MonoCompile *cfg) {
2059 if (mono_ssapre_method_name == NULL) {
2060 mono_ssapre_method_name = getenv ("MONO_SSAPRE_METHOD_NAME");
2061 }
2062 if (mono_ssapre_method_name != NULL) {
2063 char *method_name = mono_method_full_name (cfg->method, TRUE);
2064 if (strstr (method_name, mono_ssapre_method_name) != NULL) {
2065 return TRUE;
2066 } else {
2067 return FALSE;
2068 }
2069 } else {
2070 return TRUE;
2071 }
2072 }
2073 #endif
2074
2075 /*
2076 * Apply SSAPRE to a MonoCompile
2077 */
2078 void
2079 mono_perform_ssapre (MonoCompile *cfg) {
2080 MonoSsapreWorkArea area;
2081 int dt_dfn, descendants, block, i;
2082
2083 #if (MONO_APPLY_SSAPRE_TO_SINGLE_METHOD)
2084 if (! check_ssapre_method_name (cfg)) return;
2085 #endif
2086 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
2087 area.expression_is_handled_father = FALSE;
2088 #endif
2089
2090 area.cfg = cfg;
2091 area.mempool = mono_mempool_new ();
2092
2093 area.num_bblocks = cfg->num_bblocks;
2094 area.bb_infos = (MonoSsapreBBInfo*) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreBBInfo) * (cfg->num_bblocks));
2095 area.bb_infos_in_cfg_dfn_order = (MonoSsapreBBInfo**) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreBBInfo*) * (cfg->num_bblocks));
2096
2097 area.sizeof_bb_bitset = mono_bitset_alloc_size (cfg->num_bblocks, 0);
2098 area.expression_occurrences_buffer = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2099 area.bb_iteration_buffer = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2100 area.iterated_dfrontier_buffer = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2101 area.left_argument_bb_bitset = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2102 area.right_argument_bb_bitset = mono_bitset_mem_new (mono_mempool_alloc (area.mempool, area.sizeof_bb_bitset), area.num_bblocks, 0);
2103
2104 area.worklist = NULL;
2105
2106 if (area.cfg->verbose_level >= LOG_LEVEL) {
2107 printf ("SSAPRE STARTS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE));
2108 }
2109 if (area.cfg->verbose_level >= DUMP_LEVEL) {
2110 mono_print_code (area.cfg, "BEFORE SSAPRE");
2111 }
2112
2113 area.first_in_queue = NULL;
2114 area.last_in_queue = NULL;
2115 area.current_occurrence = (MonoSsapreExpressionOccurrence*) mono_mempool_alloc (area.mempool, sizeof (MonoSsapreExpressionOccurrence));
2116 dt_dfn = 0;
2117 descendants = 0;
2118 area.dt_depth = 0;
2119 process_bb (&area, cfg->bblocks [0], &dt_dfn, &descendants, 1);
2120 for (block = 0; block < area.num_bblocks; block++) {
2121 MonoSsapreBBInfo *bb_info = &(area.bb_infos [block]);
2122 MonoBasicBlock *bb = bb_info->bb;
2123 if (bb->idom != NULL) {
2124 bb_info->idominator = area.bb_infos_in_cfg_dfn_order [bb->idom->dfn];
2125 } else {
2126 bb_info->idominator = NULL;
2127 }
2128 for (i = 0; i < bb->in_count; i++) {
2129 bb_info->in_bb [i] = area.bb_infos_in_cfg_dfn_order [bb->in_bb [i]->dfn];
2130 }
2131 for (i = 0; i < bb->out_count; i++) {
2132 bb_info->out_bb [i] = area.bb_infos_in_cfg_dfn_order [bb->out_bb [i]->dfn];
2133 }
2134 }
2135
2136 if (area.cfg->verbose_level >= TRACE_LEVEL) {
2137 printf ("SSAPRE START WORKLIST\n");
2138 print_worklist (area.worklist);
2139 printf ("SSAPRE END WORKLIST\n");
2140 }
2141
2142 #if (MONO_APPLY_SSAPRE_TO_SINGLE_EXPRESSION)
2143 area.expression_is_handled_father = TRUE;
2144 #endif
2145 for (area.current_expression = area.first_in_queue; area.current_expression != NULL; area.current_expression = area.current_expression->next_in_queue) {
2146 process_expression (&area);
2147 }
2148
2149 if (area.cfg->verbose_level >= DUMP_LEVEL) {
2150 mono_print_code (area.cfg, "AFTER SSAPRE");
2151 }
2152 if (area.cfg->verbose_level >= TRACE_LEVEL) {
2153 printf ("SSAPRE ENDS PROCESSING METHOD %s\n", mono_method_full_name (cfg->method, TRUE));
2154 }
2155
2156 mono_mempool_destroy (area.mempool);
2157 }
2158
2159 #endif /* DISABLE_SSA */
2160
2161 #else /* 0 */
2162
2163 void
2164 mono_perform_ssapre (MonoCompile *cfg)
2165 {
2166 }
2167
2168 #endif /* 0 */
Mirror of the official Mono project git repository