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