?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[ci] Bump timeout in ms-test-suite
[mono-project.git] / mono / mini / branch-opts.c
blob1602b03d59aae4ef6d211d82ce75bf61f80b17b6
1 /*
2 * branch-opts.c: Branch optimizations support
3 *
4 * Authors:
5 * Patrik Torstensson (Patrik.Torstesson at gmail.com)
6 *
7 * (C) 2005 Ximian, Inc. http://www.ximian.com
8 * Copyright 2011 Xamarin Inc. http://www.xamarin.com
9 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
10 */
11
12 #include "config.h"
13 #include <mono/utils/mono-compiler.h>
14 #ifndef DISABLE_JIT
15
16 #include "mini.h"
17
18 /*
19 * Returns true if @bb is a basic block which falls through the next block.
20 * TODO verify if it helps to check if the bb last ins is a branch to its successor.
21 */
22 static gboolean
23 mono_bb_is_fall_through (MonoCompile *cfg, MonoBasicBlock *bb)
24 {
25 return bb->next_bb && bb->next_bb->region == bb->region && /*fall throught between regions is not really interesting or useful*/
26 (bb->last_ins == NULL || !MONO_IS_BRANCH_OP (bb->last_ins)); /*and the last op can't be a branch too*/
27 }
28
29 /*
30 * Used by the arch code to replace the exception handling
31 * with a direct branch. This is safe to do if the
32 * exception object isn't used, no rethrow statement and
33 * no filter statement (verify).
34 *
35 */
36 MonoInst *
37 mono_branch_optimize_exception_target (MonoCompile *cfg, MonoBasicBlock *bb, const char * exname)
38 {
39 MonoMethodHeader *header = cfg->header;
40 MonoExceptionClause *clause;
41 MonoClass *exclass;
42 int i;
43
44 if (!(cfg->opt & MONO_OPT_EXCEPTION))
45 return NULL;
46
47 if (bb->region == -1 || !MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY))
48 return NULL;
49
50 exclass = mono_class_load_from_name (mono_get_corlib (), "System", exname);
51 /* search for the handler */
52 for (i = 0; i < header->num_clauses; ++i) {
53 clause = &header->clauses [i];
54 if (MONO_OFFSET_IN_CLAUSE (clause, bb->real_offset)) {
55 if (clause->flags == MONO_EXCEPTION_CLAUSE_NONE && clause->data.catch_class && mono_class_is_assignable_from (clause->data.catch_class, exclass)) {
56 MonoBasicBlock *tbb;
57
58 /* get the basic block for the handler and
59 * check if the exception object is used.
60 * Flag is set during method_to_ir due to
61 * pop-op is optmized away in codegen (burg).
62 */
63 tbb = cfg->cil_offset_to_bb [clause->handler_offset];
64 if (tbb && tbb->flags & BB_EXCEPTION_DEAD_OBJ && !(tbb->flags & BB_EXCEPTION_UNSAFE)) {
65 MonoBasicBlock *targetbb = tbb;
66 gboolean unsafe = FALSE;
67
68 /* Check if this catch clause is ok to optimize by
69 * looking for the BB_EXCEPTION_UNSAFE in every BB that
70 * belongs to the same region.
71 *
72 * UNSAFE flag is set during method_to_ir (OP_RETHROW)
73 */
74 while (!unsafe && tbb->next_bb && tbb->region == tbb->next_bb->region) {
75 if (tbb->next_bb->flags & BB_EXCEPTION_UNSAFE) {
76 unsafe = TRUE;
77 break;
78 }
79 tbb = tbb->next_bb;
80 }
81
82 if (!unsafe) {
83 MonoInst *jump;
84
85 /* Create dummy inst to allow easier integration in
86 * arch dependent code (opcode ignored)
87 */
88 MONO_INST_NEW (cfg, jump, OP_BR);
89
90 /* Allocate memory for our branch target */
91 jump->inst_i1 = (MonoInst *)mono_mempool_alloc0 (cfg->mempool, sizeof (MonoInst));
92 jump->inst_true_bb = targetbb;
93
94 if (cfg->verbose_level > 2)
95 g_print ("found exception to optimize - returning branch to BB%d (%s) (instead of throw) for method %s:%s\n", targetbb->block_num, clause->data.catch_class->name, cfg->method->klass->name, cfg->method->name);
96
97 return jump;
98 }
99
100 return NULL;
101 } else {
102 /* Branching to an outer clause could skip inner clauses */
103 return NULL;
104 }
105 } else {
106 /* Branching to an outer clause could skip inner clauses */
107 return NULL;
108 }
109 }
110 }
111
112 return NULL;
113 }
114
115 static const int int_cmov_opcodes [] = {
116 OP_CMOV_IEQ,
117 OP_CMOV_INE_UN,
118 OP_CMOV_ILE,
119 OP_CMOV_IGE,
120 OP_CMOV_ILT,
121 OP_CMOV_IGT,
122 OP_CMOV_ILE_UN,
123 OP_CMOV_IGE_UN,
124 OP_CMOV_ILT_UN,
125 OP_CMOV_IGT_UN
126 };
127
128 static const int long_cmov_opcodes [] = {
129 OP_CMOV_LEQ,
130 OP_CMOV_LNE_UN,
131 OP_CMOV_LLE,
132 OP_CMOV_LGE,
133 OP_CMOV_LLT,
134 OP_CMOV_LGT,
135 OP_CMOV_LLE_UN,
136 OP_CMOV_LGE_UN,
137 OP_CMOV_LLT_UN,
138 OP_CMOV_LGT_UN
139 };
140
141 static G_GNUC_UNUSED int
142 br_to_br_un (int opcode)
143 {
144 switch (opcode) {
145 case OP_IBGT:
146 return OP_IBGT_UN;
147 break;
148 case OP_IBLE:
149 return OP_IBLE_UN;
150 break;
151 case OP_LBGT:
152 return OP_LBGT_UN;
153 break;
154 case OP_LBLE:
155 return OP_LBLE_UN;
156 break;
157 default:
158 g_assert_not_reached ();
159 return -1;
160 }
161 }
162
163 /**
164 * mono_replace_ins:
165 *
166 * Replace INS with its decomposition which is stored in a series of bblocks starting
167 * at FIRST_BB and ending at LAST_BB. On enter, PREV points to the predecessor of INS.
168 * On return, it will be set to the last ins of the decomposition.
169 */
170 void
171 mono_replace_ins (MonoCompile *cfg, MonoBasicBlock *bb, MonoInst *ins, MonoInst **prev, MonoBasicBlock *first_bb, MonoBasicBlock *last_bb)
172 {
173 MonoInst *next = ins->next;
174
175 if (next && next->opcode == OP_NOP) {
176 /* Avoid NOPs following branches */
177 ins->next = next->next;
178 next = next->next;
179 }
180
181 if (first_bb == last_bb) {
182 /*
183 * Only one replacement bb, merge the code into
184 * the current bb.
185 */
186
187 /* Delete links between the first_bb and its successors */
188 while (first_bb->out_count)
189 mono_unlink_bblock (cfg, first_bb, first_bb->out_bb [0]);
190
191 /* Head */
192 if (*prev) {
193 (*prev)->next = first_bb->code;
194 first_bb->code->prev = (*prev);
195 } else {
196 bb->code = first_bb->code;
197 }
198
199 /* Tail */
200 last_bb->last_ins->next = next;
201 if (next)
202 next->prev = last_bb->last_ins;
203 else
204 bb->last_ins = last_bb->last_ins;
205 *prev = last_bb->last_ins;
206 bb->has_array_access |= first_bb->has_array_access;
207 } else {
208 int i, count;
209 MonoBasicBlock **tmp_bblocks, *tmp;
210 MonoInst *last;
211
212 /* Multiple BBs */
213
214 /* Set region/real_offset */
215 for (tmp = first_bb; tmp; tmp = tmp->next_bb) {
216 tmp->region = bb->region;
217 tmp->real_offset = bb->real_offset;
218 }
219
220 /* Split the original bb */
221 if (ins->next)
222 ins->next->prev = NULL;
223 ins->next = NULL;
224 bb->last_ins = ins;
225
226 /* Merge the second part of the original bb into the last bb */
227 if (last_bb->last_ins) {
228 last_bb->last_ins->next = next;
229 if (next)
230 next->prev = last_bb->last_ins;
231 } else {
232 last_bb->code = next;
233 }
234 last_bb->has_array_access |= bb->has_array_access;
235
236 if (next) {
237 for (last = next; last->next != NULL; last = last->next)
238 ;
239 last_bb->last_ins = last;
240 }
241
242 for (i = 0; i < bb->out_count; ++i)
243 mono_link_bblock (cfg, last_bb, bb->out_bb [i]);
244
245 /* Merge the first (dummy) bb to the original bb */
246 if (*prev) {
247 (*prev)->next = first_bb->code;
248 first_bb->code->prev = (*prev);
249 } else {
250 bb->code = first_bb->code;
251 }
252 bb->last_ins = first_bb->last_ins;
253 bb->has_array_access |= first_bb->has_array_access;
254
255 /* Delete the links between the original bb and its successors */
256 tmp_bblocks = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoBasicBlock*) * bb->out_count);
257 memcpy (tmp_bblocks, bb->out_bb, sizeof (MonoBasicBlock*) * bb->out_count);
258 count = bb->out_count;
259 for (i = 0; i < count; ++i)
260 mono_unlink_bblock (cfg, bb, tmp_bblocks [i]);
261
262 /* Add links between the original bb and the first_bb's successors */
263 for (i = 0; i < first_bb->out_count; ++i) {
264 MonoBasicBlock *out_bb = first_bb->out_bb [i];
265
266 mono_link_bblock (cfg, bb, out_bb);
267 }
268 /* Delete links between the first_bb and its successors */
269 for (i = 0; i < bb->out_count; ++i) {
270 MonoBasicBlock *out_bb = bb->out_bb [i];
271
272 mono_unlink_bblock (cfg, first_bb, out_bb);
273 }
274 last_bb->next_bb = bb->next_bb;
275 bb->next_bb = first_bb->next_bb;
276
277 *prev = NULL;
278 }
279 }
280
281 void
282 mono_if_conversion (MonoCompile *cfg)
283 {
284 #ifdef MONO_ARCH_HAVE_CMOV_OPS
285 MonoBasicBlock *bb;
286 gboolean changed = FALSE;
287 int filter = FILTER_NOP | FILTER_IL_SEQ_POINT;
288
289 if (!(cfg->opt & MONO_OPT_CMOV))
290 return;
291
292 // FIXME: Make this work with extended bblocks
293
294 /*
295 * This pass requires somewhat optimized IR code so it should be run after
296 * local cprop/deadce. Also, it should be run before dominator computation, since
297 * it changes control flow.
298 */
299 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
300 MonoBasicBlock *bb1, *bb2;
301
302 restart:
303 /* Look for the IR code generated from cond ? a : b
304 * which is:
305 * BB:
306 * b<cond> [BB1BB2]
307 * BB1:
308 * <var> <- <a>
309 * br BB3
310 * BB2:
311 * <var> <- <b>
312 * br BB3
313 */
314 if (!(bb->out_count == 2 && !bb->extended))
315 continue;
316
317 bb1 = bb->out_bb [0];
318 bb2 = bb->out_bb [1];
319
320 if (bb1->in_count == 1 && bb2->in_count == 1 && bb1->out_count == 1 && bb2->out_count == 1 && bb1->out_bb [0] == bb2->out_bb [0]) {
321 MonoInst *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
322 MonoBasicBlock *true_bb, *false_bb;
323 gboolean simple, ret;
324 int dreg, tmp_reg;
325 CompType comp_type;
326
327 branch = mono_bb_last_inst (bb, filter);
328
329 if (!branch || branch->opcode == OP_BR_REG || branch->opcode == OP_BR)
330 continue;
331
332 /* Find the compare instruction */
333 compare = mono_inst_prev (branch, filter);
334 if (!compare)
335 continue;
336
337 if (!MONO_IS_COND_BRANCH_OP (branch))
338 /* This can happen if a cond branch is optimized away */
339 continue;
340
341 true_bb = branch->inst_true_bb;
342 false_bb = branch->inst_false_bb;
343
344 /*
345 * Check that bb1 and bb2 are 'simple' and both assign to the same
346 * variable.
347 */
348 /* FIXME: Get rid of the nops earlier */
349 ins1 = mono_bb_first_inst (true_bb, filter);
350 ins2 = mono_bb_first_inst (false_bb, filter);
351
352 if (!(ins1 && ins2 && ins1->dreg == ins2->dreg && ins1->dreg != -1))
353 continue;
354
355 simple = TRUE;
356 for (tmp = ins1->next; tmp; tmp = tmp->next)
357 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_IL_SEQ_POINT) || (tmp->opcode == OP_BR)))
358 simple = FALSE;
359
360 for (tmp = ins2->next; tmp; tmp = tmp->next)
361 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_IL_SEQ_POINT) || (tmp->opcode == OP_BR)))
362 simple = FALSE;
363
364 if (!simple)
365 continue;
366
367 /* We move ins1/ins2 before the compare so they should have no side effect */
368 if (!(MONO_INS_HAS_NO_SIDE_EFFECT (ins1) && MONO_INS_HAS_NO_SIDE_EFFECT (ins2)))
369 continue;
370
371 /* Moving ins1/ins2 could change the comparison */
372 /* FIXME: */
373 if (!((compare->sreg1 != ins1->dreg) && (compare->sreg2 != ins1->dreg)))
374 continue;
375
376 /* FIXME: */
377 comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
378 if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
379 continue;
380
381 /* FIXME: */
382 /* ins->type might not be set */
383 if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
384 continue;
385
386 if (cfg->verbose_level > 2) {
387 printf ("\tBranch -> CMove optimization in BB%d on\n", bb->block_num);
388 printf ("\t\t"); mono_print_ins (compare);
389 printf ("\t\t"); mono_print_ins (mono_inst_next (compare, filter));
390 printf ("\t\t"); mono_print_ins (ins1);
391 printf ("\t\t"); mono_print_ins (ins2);
392 }
393
394 changed = TRUE;
395
396 //printf ("HIT!\n");
397
398 /* Assignments to the return register must remain at the end of bbs */
399 if (cfg->ret)
400 ret = ins1->dreg == cfg->ret->dreg;
401 else
402 ret = FALSE;
403
404 tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
405 dreg = ins1->dreg;
406
407 /* Rewrite ins1 to emit to tmp_reg */
408 ins1->dreg = tmp_reg;
409
410 if (ret) {
411 dreg = mono_alloc_dreg (cfg, STACK_I4);
412 ins2->dreg = dreg;
413 }
414
415 /* Remove ins1/ins2 from bb1/bb2 */
416 MONO_REMOVE_INS (true_bb, ins1);
417 MONO_REMOVE_INS (false_bb, ins2);
418
419 /* Move ins1 and ins2 before the comparison */
420 /* ins1 comes first to avoid ins1 overwriting an argument of ins2 */
421 mono_bblock_insert_before_ins (bb, compare, ins2);
422 mono_bblock_insert_before_ins (bb, ins2, ins1);
423
424 /* Add cmov instruction */
425 MONO_INST_NEW (cfg, cmov, OP_NOP);
426 cmov->dreg = dreg;
427 cmov->sreg1 = dreg;
428 cmov->sreg2 = tmp_reg;
429 switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
430 case CMP_TYPE_I:
431 cmov->opcode = int_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
432 break;
433 case CMP_TYPE_L:
434 cmov->opcode = long_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
435 break;
436 default:
437 g_assert_not_reached ();
438 }
439 mono_bblock_insert_after_ins (bb, compare, cmov);
440
441 if (ret) {
442 /* Add an extra move */
443 MONO_INST_NEW (cfg, move, OP_MOVE);
444 move->dreg = cfg->ret->dreg;
445 move->sreg1 = dreg;
446 mono_bblock_insert_after_ins (bb, cmov, move);
447 }
448
449 /* Rewrite the branch */
450 branch->opcode = OP_BR;
451 branch->inst_target_bb = true_bb->out_bb [0];
452 mono_link_bblock (cfg, bb, branch->inst_target_bb);
453
454 /* Reorder bblocks */
455 mono_unlink_bblock (cfg, bb, true_bb);
456 mono_unlink_bblock (cfg, bb, false_bb);
457 mono_unlink_bblock (cfg, true_bb, true_bb->out_bb [0]);
458 mono_unlink_bblock (cfg, false_bb, false_bb->out_bb [0]);
459 mono_remove_bblock (cfg, true_bb);
460 mono_remove_bblock (cfg, false_bb);
461
462 /* Merge bb and its successor if possible */
463 if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
464 (bb->region == bb->out_bb [0]->region)) {
465 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
466 goto restart;
467 }
468 }
469
470 /* Look for the IR code generated from if (cond) <var> <- <a>
471 * which is:
472 * BB:
473 * b<cond> [BB1BB2]
474 * BB1:
475 * <var> <- <a>
476 * br BB2
477 */
478
479 if ((bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) ||
480 (bb1->in_count == 1 && bb1->out_count == 1 && bb1->out_bb [0] == bb2)) {
481 MonoInst *compare, *branch, *ins1, *cmov, *tmp;
482 gboolean simple;
483 int dreg, tmp_reg;
484 CompType comp_type;
485 CompRelation cond;
486 MonoBasicBlock *next_bb, *code_bb;
487
488 /* code_bb is the bblock containing code, next_bb is the successor bblock */
489 if (bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) {
490 code_bb = bb2;
491 next_bb = bb1;
492 } else {
493 code_bb = bb1;
494 next_bb = bb2;
495 }
496
497 ins1 = mono_bb_first_inst (code_bb, filter);
498
499 if (!ins1)
500 continue;
501
502 /* Check that code_bb is simple */
503 simple = TRUE;
504 for (tmp = ins1; tmp; tmp = tmp->next)
505 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_IL_SEQ_POINT) || (tmp->opcode == OP_BR)))
506 simple = FALSE;
507
508 if (!simple)
509 continue;
510
511 /* We move ins1 before the compare so it should have no side effect */
512 if (!MONO_INS_HAS_NO_SIDE_EFFECT (ins1))
513 continue;
514
515 branch = mono_bb_last_inst (bb, filter);
516
517 if (!branch || branch->opcode == OP_BR_REG)
518 continue;
519
520 /* Find the compare instruction */
521 compare = mono_inst_prev (branch, filter);
522 if (!compare)
523 continue;
524
525 if (!MONO_IS_COND_BRANCH_OP (branch))
526 /* This can happen if a cond branch is optimized away */
527 continue;
528
529 /* FIXME: */
530 comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
531 if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
532 continue;
533
534 /* FIXME: */
535 /* ins->type might not be set */
536 if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
537 continue;
538
539 /* FIXME: */
540 if (cfg->ret && ins1->dreg == cfg->ret->dreg)
541 continue;
542
543 if (!(cfg->opt & MONO_OPT_DEADCE))
544 /*
545 * It is possible that dreg is never set before, so we can't use
546 * it as an sreg of the cmov instruction (#582322).
547 */
548 continue;
549
550 if (cfg->verbose_level > 2) {
551 printf ("\tBranch -> CMove optimization (2) in BB%d on\n", bb->block_num);
552 printf ("\t\t"); mono_print_ins (compare);
553 printf ("\t\t"); mono_print_ins (mono_inst_next (compare, filter));
554 printf ("\t\t"); mono_print_ins (ins1);
555 }
556
557 changed = TRUE;
558
559 //printf ("HIT!\n");
560
561 tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
562 dreg = ins1->dreg;
563
564 /* Rewrite ins1 to emit to tmp_reg */
565 ins1->dreg = tmp_reg;
566
567 /* Remove ins1 from code_bb */
568 MONO_REMOVE_INS (code_bb, ins1);
569
570 /* Move ins1 before the comparison */
571 mono_bblock_insert_before_ins (bb, compare, ins1);
572
573 /* Add cmov instruction */
574 MONO_INST_NEW (cfg, cmov, OP_NOP);
575 cmov->dreg = dreg;
576 cmov->sreg1 = dreg;
577 cmov->sreg2 = tmp_reg;
578 cond = mono_opcode_to_cond (branch->opcode);
579 if (branch->inst_false_bb == code_bb)
580 cond = mono_negate_cond (cond);
581 switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
582 case CMP_TYPE_I:
583 cmov->opcode = int_cmov_opcodes [cond];
584 break;
585 case CMP_TYPE_L:
586 cmov->opcode = long_cmov_opcodes [cond];
587 break;
588 default:
589 g_assert_not_reached ();
590 }
591 mono_bblock_insert_after_ins (bb, compare, cmov);
592
593 /* Rewrite the branch */
594 branch->opcode = OP_BR;
595 branch->inst_target_bb = next_bb;
596 mono_link_bblock (cfg, bb, branch->inst_target_bb);
597
598 /* Nullify the branch at the end of code_bb */
599 if (code_bb->code) {
600 branch = code_bb->code;
601 MONO_DELETE_INS (code_bb, branch);
602 }
603
604 /* Reorder bblocks */
605 mono_unlink_bblock (cfg, bb, code_bb);
606 mono_unlink_bblock (cfg, code_bb, next_bb);
607
608 /* Merge bb and its successor if possible */
609 if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
610 (bb->region == bb->out_bb [0]->region)) {
611 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
612
613 /*
614 * bbn might have fallen through to the next bb without a branch,
615 * have to add one now (#474718).
616 * FIXME: Maybe need to do this more generally in
617 * merge_basic_blocks () ?
618 */
619 if (!(bb->last_ins && MONO_IS_BRANCH_OP (bb->last_ins)) && bb->out_count) {
620 MONO_INST_NEW (cfg, ins1, OP_BR);
621 ins1->inst_target_bb = bb->out_bb [0];
622 MONO_ADD_INS (bb, ins1);
623 }
624 goto restart;
625 }
626 }
627 }
628
629 /*
630 * Optimize checks like: if (v < 0 || v > limit) by changing then to unsigned
631 * compares. This isn't really if conversion, but it easier to do here than in
632 * optimize_branches () since the IR is already optimized.
633 */
634 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
635 MonoBasicBlock *bb1, *bb2, *next_bb;
636 MonoInst *branch1, *branch2, *compare1, *ins, *next;
637
638 /* Look for the IR code generated from if (<var> < 0 || v > <limit>)
639 * after branch opts which is:
640 * BB:
641 * icompare_imm R [0]
642 * int_blt [BB1BB2]
643 * BB2:
644 * icompare_imm R [<limit>]
645 * int_ble [BB3BB1]
646 */
647 if (!(bb->out_count == 2 && !bb->extended))
648 continue;
649
650 bb1 = bb->out_bb [0];
651 bb2 = bb->out_bb [1];
652
653 // FIXME: Add more cases
654
655 /* Check structure */
656 if (!(bb1->in_count == 2 && bb1->in_bb [0] == bb && bb1->in_bb [1] == bb2 && bb2->in_count == 1 && bb2->out_count == 2))
657 continue;
658
659 next_bb = bb2;
660
661 /* Check first branch */
662 branch1 = mono_bb_last_inst (bb, filter);
663 if (!(branch1 && ((branch1->opcode == OP_IBLT) || (branch1->opcode == OP_LBLT)) && (branch1->inst_false_bb == next_bb)))
664 continue;
665
666 /* Check second branch */
667 branch2 = mono_bb_last_inst (next_bb, filter);
668 if (!branch2)
669 continue;
670
671 /* mcs sometimes generates inverted branches */
672 if (((branch2->opcode == OP_IBGT) || (branch2->opcode == OP_LBGT)) && branch2->inst_true_bb == branch1->inst_true_bb)
673 ;
674 else if (((branch2->opcode == OP_IBLE) || (branch2->opcode == OP_LBLE)) && branch2->inst_false_bb == branch1->inst_true_bb)
675 ;
676 else
677 continue;
678
679 /* Check first compare */
680 compare1 = mono_inst_prev (mono_bb_last_inst (bb, filter), filter);
681 if (!(compare1 && ((compare1->opcode == OP_ICOMPARE_IMM) || (compare1->opcode == OP_LCOMPARE_IMM)) && compare1->inst_imm == 0))
682 continue;
683
684 /* Check second bblock */
685 ins = mono_bb_first_inst (next_bb, filter);
686 if (!ins)
687 continue;
688 next = mono_inst_next (ins, filter);
689 if (((ins->opcode == OP_ICOMPARE_IMM) || (ins->opcode == OP_LCOMPARE_IMM)) && ins->sreg1 == compare1->sreg1 && next == branch2) {
690 /* The second arg must be positive */
691 if (ins->inst_imm < 0)
692 continue;
693 } else if (((ins->opcode == OP_LDLEN) || (ins->opcode == OP_STRLEN)) && ins->dreg != compare1->sreg1 && next && next->opcode == OP_ICOMPARE && next->sreg1 == compare1->sreg1 && next->sreg2 == ins->dreg && mono_inst_next (next, filter) == branch2) {
694 /* Another common case: if (index < 0 || index > arr.Length) */
695 } else {
696 continue;
697 }
698
699 if (cfg->verbose_level > 2) {
700 printf ("\tSigned->unsigned compare optimization in BB%d on\n", bb->block_num);
701 printf ("\t\t"); mono_print_ins (compare1);
702 printf ("\t\t"); mono_print_ins (mono_inst_next (compare1, filter));
703 printf ("\t\t"); mono_print_ins (ins);
704 }
705
706 /* Rewrite the first compare+branch */
707 MONO_DELETE_INS (bb, compare1);
708 branch1->opcode = OP_BR;
709 mono_unlink_bblock (cfg, bb, branch1->inst_true_bb);
710 mono_unlink_bblock (cfg, bb, branch1->inst_false_bb);
711 branch1->inst_target_bb = next_bb;
712 mono_link_bblock (cfg, bb, next_bb);
713
714 /* Rewrite the second branch */
715 branch2->opcode = br_to_br_un (branch2->opcode);
716
717 mono_merge_basic_blocks (cfg, bb, next_bb);
718 }
719
720 #if 0
721 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
722 MonoBasicBlock *bb1, *bb2;
723 MonoInst *prev, *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
724 gboolean simple, ret;
725 int dreg, tmp_reg;
726 CompType comp_type;
727
728 /* Look for the IR code generated from if (cond) <var> <- <a>
729 * after branch opts which is:
730 * BB:
731 * compare
732 * b<cond> [BB1]
733 * <var> <- <a>
734 * BB1:
735 */
736 if (!(bb->out_count == 1 && bb->extended && bb->code && bb->code->next && bb->code->next->next))
737 continue;
738
739 mono_print_bb (bb, "");
740
741 /* Find the compare instruction */
742 prev = NULL;
743 compare = bb->code;
744 g_assert (compare);
745 while (compare->next->next && compare->next->next != bb->last_ins) {
746 prev = compare;
747 compare = compare->next;
748 }
749 branch = compare->next;
750 if (!MONO_IS_COND_BRANCH_OP (branch))
751 continue;
752 }
753 #endif
754
755 if (changed) {
756 if (cfg->opt & MONO_OPT_BRANCH)
757 mono_optimize_branches (cfg);
758 /* Merging bblocks could make some variables local */
759 mono_handle_global_vregs (cfg);
760 if (cfg->opt & (MONO_OPT_CONSPROP | MONO_OPT_COPYPROP))
761 mono_local_cprop (cfg);
762 if (cfg->opt & MONO_OPT_DEADCE)
763 mono_local_deadce (cfg);
764 }
765 #endif
766 }
767
768 void
769 mono_nullify_basic_block (MonoBasicBlock *bb)
770 {
771 bb->in_count = 0;
772 bb->out_count = 0;
773 bb->in_bb = NULL;
774 bb->out_bb = NULL;
775 bb->next_bb = NULL;
776 bb->code = bb->last_ins = NULL;
777 bb->cil_code = NULL;
778 }
779
780 static void
781 replace_out_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
782 {
783 int i;
784
785 for (i = 0; i < bb->out_count; i++) {
786 MonoBasicBlock *ob = bb->out_bb [i];
787 if (ob == orig) {
788 if (!repl) {
789 if (bb->out_count > 1) {
790 bb->out_bb [i] = bb->out_bb [bb->out_count - 1];
791 }
792 bb->out_count--;
793 } else {
794 bb->out_bb [i] = repl;
795 }
796 }
797 }
798 }
799
800 static void
801 replace_in_block (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl)
802 {
803 int i;
804
805 for (i = 0; i < bb->in_count; i++) {
806 MonoBasicBlock *ib = bb->in_bb [i];
807 if (ib == orig) {
808 if (!repl) {
809 if (bb->in_count > 1) {
810 bb->in_bb [i] = bb->in_bb [bb->in_count - 1];
811 }
812 bb->in_count--;
813 } else {
814 bb->in_bb [i] = repl;
815 }
816 }
817 }
818 }
819
820 static void
821 replace_out_block_in_code (MonoBasicBlock *bb, MonoBasicBlock *orig, MonoBasicBlock *repl) {
822 MonoInst *ins;
823
824 #if defined(__native_client_codegen__)
825 /* Need to maintain this flag for the new block because */
826 /* we can't jump indirectly to a non-aligned block. */
827 if (orig->flags & BB_INDIRECT_JUMP_TARGET)
828 {
829 repl->flags |= BB_INDIRECT_JUMP_TARGET;
830 }
831 #endif
832
833 for (ins = bb->code; ins != NULL; ins = ins->next) {
834 switch (ins->opcode) {
835 case OP_BR:
836 if (ins->inst_target_bb == orig)
837 ins->inst_target_bb = repl;
838 break;
839 case OP_CALL_HANDLER:
840 if (ins->inst_target_bb == orig)
841 ins->inst_target_bb = repl;
842 break;
843 case OP_SWITCH: {
844 int i;
845 int n = GPOINTER_TO_INT (ins->klass);
846 for (i = 0; i < n; i++ ) {
847 if (ins->inst_many_bb [i] == orig)
848 ins->inst_many_bb [i] = repl;
849 }
850 break;
851 }
852 default:
853 if (MONO_IS_COND_BRANCH_OP (ins)) {
854 if (ins->inst_true_bb == orig)
855 ins->inst_true_bb = repl;
856 if (ins->inst_false_bb == orig)
857 ins->inst_false_bb = repl;
858 } else if (MONO_IS_JUMP_TABLE (ins)) {
859 int i;
860 MonoJumpInfoBBTable *table = (MonoJumpInfoBBTable *)MONO_JUMP_TABLE_FROM_INS (ins);
861 for (i = 0; i < table->table_size; i++ ) {
862 if (table->table [i] == orig)
863 table->table [i] = repl;
864 }
865 }
866
867 break;
868 }
869 }
870 }
871
872 /**
873 * Check if a bb is useless (is just made of NOPs and ends with an
874 * unconditional branch, or nothing).
875 * If it is so, unlink it from the CFG and nullify it, and return TRUE.
876 * Otherwise, return FALSE;
877 */
878 static gboolean
879 remove_block_if_useless (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *previous_bb) {
880 MonoBasicBlock *target_bb = NULL;
881 MonoInst *inst;
882
883 /* Do not touch handlers */
884 if (bb->region != -1) {
885 bb->not_useless = TRUE;
886 return FALSE;
887 }
888
889 MONO_BB_FOR_EACH_INS (bb, inst) {
890 switch (inst->opcode) {
891 case OP_NOP:
892 case OP_IL_SEQ_POINT:
893 break;
894 case OP_BR:
895 target_bb = inst->inst_target_bb;
896 break;
897 default:
898 bb->not_useless = TRUE;
899 return FALSE;
900 }
901 }
902
903 if (target_bb == NULL) {
904 if ((bb->out_count == 1) && (bb->out_bb [0] == bb->next_bb)) {
905 target_bb = bb->next_bb;
906 } else {
907 /* Do not touch empty BBs that do not "fall through" to their next BB (like the exit BB) */
908 return FALSE;
909 }
910 }
911
912 /* Do not touch BBs following a switch (they are the "default" branch) */
913 if ((previous_bb->last_ins != NULL) && (previous_bb->last_ins->opcode == OP_SWITCH)) {
914 return FALSE;
915 }
916
917 /* Do not touch BBs following the entry BB and jumping to something that is not */
918 /* thiry "next" bb (the entry BB cannot contain the branch) */
919 if ((previous_bb == cfg->bb_entry) && (bb->next_bb != target_bb)) {
920 return FALSE;
921 }
922
923 /*
924 * Do not touch BBs following a try block as the code in
925 * mini_method_compile needs them to compute the length of the try block.
926 */
927 if (MONO_BBLOCK_IS_IN_REGION (previous_bb, MONO_REGION_TRY))
928 return FALSE;
929
930 /* Check that there is a target BB, and that bb is not an empty loop (Bug 75061) */
931 if ((target_bb != NULL) && (target_bb != bb)) {
932 int i;
933
934 if (cfg->verbose_level > 1) {
935 printf ("remove_block_if_useless, removed BB%d\n", bb->block_num);
936 }
937
938 /* unlink_bblock () modifies the bb->in_bb array so can't use a for loop here */
939 while (bb->in_count) {
940 MonoBasicBlock *in_bb = bb->in_bb [0];
941 mono_unlink_bblock (cfg, in_bb, bb);
942 mono_link_bblock (cfg, in_bb, target_bb);
943 replace_out_block_in_code (in_bb, bb, target_bb);
944 }
945
946 mono_unlink_bblock (cfg, bb, target_bb);
947 if (previous_bb != cfg->bb_entry && mono_bb_is_fall_through (cfg, previous_bb)) {
948 for (i = 0; i < previous_bb->out_count; i++) {
949 if (previous_bb->out_bb [i] == target_bb) {
950 MonoInst *jump;
951 MONO_INST_NEW (cfg, jump, OP_BR);
952 MONO_ADD_INS (previous_bb, jump);
953 jump->cil_code = previous_bb->cil_code;
954 jump->inst_target_bb = target_bb;
955 break;
956 }
957 }
958 }
959
960 previous_bb->next_bb = bb->next_bb;
961 mono_nullify_basic_block (bb);
962
963 return TRUE;
964 } else {
965 return FALSE;
966 }
967 }
968
969 void
970 mono_merge_basic_blocks (MonoCompile *cfg, MonoBasicBlock *bb, MonoBasicBlock *bbn)
971 {
972 MonoInst *inst;
973 MonoBasicBlock *prev_bb;
974 int i;
975
976 bb->has_array_access |= bbn->has_array_access;
977 bb->extended |= bbn->extended;
978
979 /* Compute prev_bb if possible to avoid the linear search below */
980 prev_bb = NULL;
981 for (i = 0; i < bbn->in_count; ++i)
982 if (bbn->in_bb [0]->next_bb == bbn)
983 prev_bb = bbn->in_bb [0];
984
985 mono_unlink_bblock (cfg, bb, bbn);
986 for (i = 0; i < bbn->out_count; ++i)
987 mono_link_bblock (cfg, bb, bbn->out_bb [i]);
988 while (bbn->out_count)
989 mono_unlink_bblock (cfg, bbn, bbn->out_bb [0]);
990
991 /* Handle the branch at the end of the bb */
992 if (bb->has_call_handler) {
993 for (inst = bb->code; inst != NULL; inst = inst->next) {
994 if (inst->opcode == OP_CALL_HANDLER) {
995 g_assert (inst->inst_target_bb == bbn);
996 NULLIFY_INS (inst);
997 }
998 }
999 }
1000 if (bb->has_jump_table) {
1001 for (inst = bb->code; inst != NULL; inst = inst->next) {
1002 if (MONO_IS_JUMP_TABLE (inst)) {
1003 int i;
1004 MonoJumpInfoBBTable *table = (MonoJumpInfoBBTable *)MONO_JUMP_TABLE_FROM_INS (inst);
1005 for (i = 0; i < table->table_size; i++ ) {
1006 /* Might be already NULL from a previous merge */
1007 if (table->table [i])
1008 g_assert (table->table [i] == bbn);
1009 table->table [i] = NULL;
1010 }
1011 /* Can't nullify this as later instructions depend on it */
1012 }
1013 }
1014 }
1015 if (bb->last_ins && MONO_IS_COND_BRANCH_OP (bb->last_ins)) {
1016 g_assert (bb->last_ins->inst_false_bb == bbn);
1017 bb->last_ins->inst_false_bb = NULL;
1018 bb->extended = TRUE;
1019 } else if (bb->last_ins && MONO_IS_BRANCH_OP (bb->last_ins)) {
1020 NULLIFY_INS (bb->last_ins);
1021 }
1022
1023 bb->has_call_handler |= bbn->has_call_handler;
1024 bb->has_jump_table |= bbn->has_jump_table;
1025
1026 if (bb->last_ins) {
1027 if (bbn->code) {
1028 bb->last_ins->next = bbn->code;
1029 bbn->code->prev = bb->last_ins;
1030 bb->last_ins = bbn->last_ins;
1031 }
1032 } else {
1033 bb->code = bbn->code;
1034 bb->last_ins = bbn->last_ins;
1035 }
1036
1037 if (!prev_bb) {
1038 for (prev_bb = cfg->bb_entry; prev_bb && prev_bb->next_bb != bbn; prev_bb = prev_bb->next_bb)
1039 ;
1040 }
1041 if (prev_bb) {
1042 prev_bb->next_bb = bbn->next_bb;
1043 } else {
1044 /* bbn might not be in the bb list yet */
1045 if (bb->next_bb == bbn)
1046 bb->next_bb = bbn->next_bb;
1047 }
1048 mono_nullify_basic_block (bbn);
1049
1050 /*
1051 * If bbn fell through to its next bblock, have to add a branch, since bb
1052 * will not fall though to the same bblock (#513931).
1053 */
1054 if (bb->last_ins && bb->out_count == 1 && bb->out_bb [0] != bb->next_bb && !MONO_IS_BRANCH_OP (bb->last_ins)) {
1055 MONO_INST_NEW (cfg, inst, OP_BR);
1056 inst->inst_target_bb = bb->out_bb [0];
1057 MONO_ADD_INS (bb, inst);
1058 }
1059 }
1060
1061 static void
1062 move_basic_block_to_end (MonoCompile *cfg, MonoBasicBlock *bb)
1063 {
1064 MonoBasicBlock *bbn, *next;
1065
1066 next = bb->next_bb;
1067
1068 /* Find the previous */
1069 for (bbn = cfg->bb_entry; bbn->next_bb && bbn->next_bb != bb; bbn = bbn->next_bb)
1070 ;
1071 if (bbn->next_bb) {
1072 bbn->next_bb = bb->next_bb;
1073 }
1074
1075 /* Find the last */
1076 for (bbn = cfg->bb_entry; bbn->next_bb; bbn = bbn->next_bb)
1077 ;
1078 bbn->next_bb = bb;
1079 bb->next_bb = NULL;
1080
1081 /* Add a branch */
1082 if (next && (!bb->last_ins || ((bb->last_ins->opcode != OP_NOT_REACHED) && (bb->last_ins->opcode != OP_BR) && (bb->last_ins->opcode != OP_BR_REG) && (!MONO_IS_COND_BRANCH_OP (bb->last_ins))))) {
1083 MonoInst *ins;
1084
1085 MONO_INST_NEW (cfg, ins, OP_BR);
1086 MONO_ADD_INS (bb, ins);
1087 mono_link_bblock (cfg, bb, next);
1088 ins->inst_target_bb = next;
1089 }
1090 }
1091
1092 /*
1093 * mono_remove_block:
1094 *
1095 * Remove BB from the control flow graph
1096 */
1097 void
1098 mono_remove_bblock (MonoCompile *cfg, MonoBasicBlock *bb)
1099 {
1100 MonoBasicBlock *tmp_bb;
1101
1102 for (tmp_bb = cfg->bb_entry; tmp_bb && tmp_bb->next_bb != bb; tmp_bb = tmp_bb->next_bb)
1103 ;
1104
1105 g_assert (tmp_bb);
1106 tmp_bb->next_bb = bb->next_bb;
1107 }
1108
1109 void
1110 mono_remove_critical_edges (MonoCompile *cfg)
1111 {
1112 MonoBasicBlock *bb;
1113 MonoBasicBlock *previous_bb;
1114
1115 if (cfg->verbose_level > 3) {
1116 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1117 int i;
1118 printf ("remove_critical_edges, BEFORE BB%d (in:", bb->block_num);
1119 for (i = 0; i < bb->in_count; i++) {
1120 printf (" %d", bb->in_bb [i]->block_num);
1121 }
1122 printf (") (out:");
1123 for (i = 0; i < bb->out_count; i++) {
1124 printf (" %d", bb->out_bb [i]->block_num);
1125 }
1126 printf (")");
1127 if (bb->last_ins != NULL) {
1128 printf (" ");
1129 mono_print_ins (bb->last_ins);
1130 }
1131 printf ("\n");
1132 }
1133 }
1134
1135 for (previous_bb = cfg->bb_entry, bb = previous_bb->next_bb; bb != NULL; previous_bb = previous_bb->next_bb, bb = bb->next_bb) {
1136 if (bb->in_count > 1) {
1137 int in_bb_index;
1138 for (in_bb_index = 0; in_bb_index < bb->in_count; in_bb_index++) {
1139 MonoBasicBlock *in_bb = bb->in_bb [in_bb_index];
1140 /*
1141 * Have to remove non-critical edges whose source ends with a BR_REG
1142 * ins too, since inserting a computation before the BR_REG could
1143 * overwrite the sreg1 of the ins.
1144 */
1145 if ((in_bb->out_count > 1) || (in_bb->out_count == 1 && in_bb->last_ins && in_bb->last_ins->opcode == OP_BR_REG)) {
1146 MonoBasicBlock *new_bb = (MonoBasicBlock *)mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoBasicBlock));
1147 new_bb->block_num = cfg->num_bblocks++;
1148 // new_bb->real_offset = bb->real_offset;
1149 new_bb->region = bb->region;
1150
1151 /* Do not alter the CFG while altering the BB list */
1152 if (mono_bb_is_fall_through (cfg, previous_bb)) {
1153 if (previous_bb != cfg->bb_entry) {
1154 int i;
1155 /* Make sure previous_bb really falls through bb */
1156 for (i = 0; i < previous_bb->out_count; i++) {
1157 if (previous_bb->out_bb [i] == bb) {
1158 MonoInst *jump;
1159 MONO_INST_NEW (cfg, jump, OP_BR);
1160 MONO_ADD_INS (previous_bb, jump);
1161 jump->cil_code = previous_bb->cil_code;
1162 jump->inst_target_bb = bb;
1163 break;
1164 }
1165 }
1166 } else {
1167 /* We cannot add any inst to the entry BB, so we must */
1168 /* put a new BB in the middle to hold the OP_BR */
1169 MonoInst *jump;
1170 MonoBasicBlock *new_bb_after_entry = (MonoBasicBlock *)mono_mempool_alloc0 ((cfg)->mempool, sizeof (MonoBasicBlock));
1171 new_bb_after_entry->block_num = cfg->num_bblocks++;
1172 // new_bb_after_entry->real_offset = bb->real_offset;
1173 new_bb_after_entry->region = bb->region;
1174
1175 MONO_INST_NEW (cfg, jump, OP_BR);
1176 MONO_ADD_INS (new_bb_after_entry, jump);
1177 jump->cil_code = bb->cil_code;
1178 jump->inst_target_bb = bb;
1179
1180 mono_unlink_bblock (cfg, previous_bb, bb);
1181 mono_link_bblock (cfg, new_bb_after_entry, bb);
1182 mono_link_bblock (cfg, previous_bb, new_bb_after_entry);
1183
1184 previous_bb->next_bb = new_bb_after_entry;
1185 previous_bb = new_bb_after_entry;
1186
1187 if (cfg->verbose_level > 2) {
1188 printf ("remove_critical_edges, added helper BB%d jumping to BB%d\n", new_bb_after_entry->block_num, bb->block_num);
1189 }
1190 }
1191 }
1192
1193 /* Insert new_bb in the BB list */
1194 previous_bb->next_bb = new_bb;
1195 new_bb->next_bb = bb;
1196 previous_bb = new_bb;
1197
1198 /* Setup in_bb and out_bb */
1199 new_bb->in_bb = (MonoBasicBlock **)mono_mempool_alloc ((cfg)->mempool, sizeof (MonoBasicBlock*));
1200 new_bb->in_bb [0] = in_bb;
1201 new_bb->in_count = 1;
1202 new_bb->out_bb = (MonoBasicBlock **)mono_mempool_alloc ((cfg)->mempool, sizeof (MonoBasicBlock*));
1203 new_bb->out_bb [0] = bb;
1204 new_bb->out_count = 1;
1205
1206 /* Relink in_bb and bb to (from) new_bb */
1207 replace_out_block (in_bb, bb, new_bb);
1208 replace_out_block_in_code (in_bb, bb, new_bb);
1209 replace_in_block (bb, in_bb, new_bb);
1210
1211 if (cfg->verbose_level > 2) {
1212 printf ("remove_critical_edges, removed critical edge from BB%d to BB%d (added BB%d)\n", in_bb->block_num, bb->block_num, new_bb->block_num);
1213 }
1214 }
1215 }
1216 }
1217 }
1218
1219 if (cfg->verbose_level > 3) {
1220 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
1221 int i;
1222 printf ("remove_critical_edges, AFTER BB%d (in:", bb->block_num);
1223 for (i = 0; i < bb->in_count; i++) {
1224 printf (" %d", bb->in_bb [i]->block_num);
1225 }
1226 printf (") (out:");
1227 for (i = 0; i < bb->out_count; i++) {
1228 printf (" %d", bb->out_bb [i]->block_num);
1229 }
1230 printf (")");
1231 if (bb->last_ins != NULL) {
1232 printf (" ");
1233 mono_print_ins (bb->last_ins);
1234 }
1235 printf ("\n");
1236 }
1237 }
1238 }
1239
1240 /*
1241 * Optimizes the branches on the Control Flow Graph
1242 *
1243 */
1244 void
1245 mono_optimize_branches (MonoCompile *cfg)
1246 {
1247 int i, count = 0, changed = FALSE;
1248 MonoBasicBlock *bb, *bbn;
1249 guint32 niterations;
1250 MonoInst *bbn_first_inst;
1251 int filter = FILTER_IL_SEQ_POINT;
1252
1253 /*
1254 * Some crazy loops could cause the code below to go into an infinite
1255 * loop, see bug #53003 for an example. To prevent this, we put an upper
1256 * bound on the number of iterations.
1257 */
1258 if (cfg->num_bblocks > 1000)
1259 niterations = cfg->num_bblocks * 2;
1260 else
1261 niterations = 1000;
1262
1263 do {
1264 MonoBasicBlock *previous_bb;
1265 changed = FALSE;
1266 niterations --;
1267
1268 /* we skip the entry block (exit is handled specially instead ) */
1269 for (previous_bb = cfg->bb_entry, bb = cfg->bb_entry->next_bb; bb; previous_bb = bb, bb = bb->next_bb) {
1270 count ++;
1271 if (count == 1000) {
1272 mono_threads_safepoint ();
1273 count = 0;
1274 }
1275 /* dont touch code inside exception clauses */
1276 if (bb->region != -1)
1277 continue;
1278
1279 if (!bb->not_useless && remove_block_if_useless (cfg, bb, previous_bb)) {
1280 changed = TRUE;
1281 continue;
1282 }
1283
1284 if ((bbn = bb->next_bb) && bbn->in_count == 0 && bbn != cfg->bb_exit && bb->region == bbn->region) {
1285 if (cfg->verbose_level > 2)
1286 g_print ("nullify block triggered %d\n", bbn->block_num);
1287
1288 bb->next_bb = bbn->next_bb;
1289
1290 for (i = 0; i < bbn->out_count; i++)
1291 replace_in_block (bbn->out_bb [i], bbn, NULL);
1292
1293 mono_nullify_basic_block (bbn);
1294 changed = TRUE;
1295 }
1296
1297 if (bb->out_count == 1) {
1298 bbn = bb->out_bb [0];
1299
1300 /* conditional branches where true and false targets are the same can be also replaced with OP_BR */
1301 if (bb->last_ins && (bb->last_ins->opcode != OP_BR) && MONO_IS_COND_BRANCH_OP (bb->last_ins)) {
1302 bb->last_ins->opcode = OP_BR;
1303 bb->last_ins->inst_target_bb = bb->last_ins->inst_true_bb;
1304 changed = TRUE;
1305 if (cfg->verbose_level > 2)
1306 g_print ("cond branch removal triggered in %d %d\n", bb->block_num, bb->out_count);
1307 }
1308
1309 if (bb->region == bbn->region && bb->next_bb == bbn) {
1310 /* the block are in sequence anyway ... */
1311
1312 /* branches to the following block can be removed */
1313 if (bb->last_ins && bb->last_ins->opcode == OP_BR && !bbn->out_of_line) {
1314 NULLIFY_INS (bb->last_ins);
1315 changed = TRUE;
1316 if (cfg->verbose_level > 2)
1317 g_print ("br removal triggered %d -> %d\n", bb->block_num, bbn->block_num);
1318 }
1319
1320 if (bbn->in_count == 1 && !bb->extended) {
1321 if (bbn != cfg->bb_exit) {
1322 if (cfg->verbose_level > 2)
1323 g_print ("block merge triggered %d -> %d\n", bb->block_num, bbn->block_num);
1324 mono_merge_basic_blocks (cfg, bb, bbn);
1325 changed = TRUE;
1326 continue;
1327 }
1328
1329 //mono_print_bb_code (bb);
1330 }
1331 }
1332 }
1333
1334 if ((bbn = bb->next_bb) && bbn->in_count == 0 && bbn != cfg->bb_exit && bb->region == bbn->region) {
1335 if (cfg->verbose_level > 2) {
1336 g_print ("nullify block triggered %d\n", bbn->block_num);
1337 }
1338 bb->next_bb = bbn->next_bb;
1339
1340 for (i = 0; i < bbn->out_count; i++)
1341 replace_in_block (bbn->out_bb [i], bbn, NULL);
1342
1343 mono_nullify_basic_block (bbn);
1344 changed = TRUE;
1345 continue;
1346 }
1347
1348 if (bb->out_count == 1) {
1349 bbn = bb->out_bb [0];
1350
1351 if (bb->last_ins && bb->last_ins->opcode == OP_BR) {
1352 bbn = bb->last_ins->inst_target_bb;
1353 bbn_first_inst = mono_bb_first_inst (bbn, filter);
1354 if (bb->region == bbn->region && bbn_first_inst && bbn_first_inst->opcode == OP_BR &&
1355 bbn_first_inst->inst_target_bb != bbn &&
1356 bbn_first_inst->inst_target_bb->region == bb->region) {
1357
1358 if (cfg->verbose_level > 2)
1359 g_print ("branch to branch triggered %d -> %d -> %d\n", bb->block_num, bbn->block_num, bbn_first_inst->inst_target_bb->block_num);
1360
1361 replace_in_block (bbn, bb, NULL);
1362 replace_out_block (bb, bbn, bbn_first_inst->inst_target_bb);
1363 mono_link_bblock (cfg, bb, bbn_first_inst->inst_target_bb);
1364 bb->last_ins->inst_target_bb = bbn_first_inst->inst_target_bb;
1365 changed = TRUE;
1366 continue;
1367 }
1368 }
1369 } else if (bb->out_count == 2) {
1370 if (bb->last_ins && MONO_IS_COND_BRANCH_NOFP (bb->last_ins)) {
1371 int branch_result;
1372 MonoBasicBlock *taken_branch_target = NULL, *untaken_branch_target = NULL;
1373
1374 if (bb->last_ins->flags & MONO_INST_CFOLD_TAKEN)
1375 branch_result = BRANCH_TAKEN;
1376 else if (bb->last_ins->flags & MONO_INST_CFOLD_NOT_TAKEN)
1377 branch_result = BRANCH_NOT_TAKEN;
1378 else
1379 branch_result = BRANCH_UNDEF;
1380
1381 if (branch_result == BRANCH_TAKEN) {
1382 taken_branch_target = bb->last_ins->inst_true_bb;
1383 untaken_branch_target = bb->last_ins->inst_false_bb;
1384 } else if (branch_result == BRANCH_NOT_TAKEN) {
1385 taken_branch_target = bb->last_ins->inst_false_bb;
1386 untaken_branch_target = bb->last_ins->inst_true_bb;
1387 }
1388 if (taken_branch_target) {
1389 /* if mono_eval_cond_branch () is ever taken to handle
1390 * non-constant values to compare, issue a pop here.
1391 */
1392 bb->last_ins->opcode = OP_BR;
1393 bb->last_ins->inst_target_bb = taken_branch_target;
1394 if (!bb->extended)
1395 mono_unlink_bblock (cfg, bb, untaken_branch_target);
1396 changed = TRUE;
1397 continue;
1398 }
1399 bbn = bb->last_ins->inst_true_bb;
1400 bbn_first_inst = mono_bb_first_inst (bbn, filter);
1401 if (bb->region == bbn->region && bbn_first_inst && bbn_first_inst->opcode == OP_BR &&
1402 bbn_first_inst->inst_target_bb->region == bb->region) {
1403 if (cfg->verbose_level > 2)
1404 g_print ("cbranch1 to branch triggered %d -> (%d) %d (0x%02x)\n",
1405 bb->block_num, bbn->block_num, bbn_first_inst->inst_target_bb->block_num,
1406 bbn_first_inst->opcode);
1407
1408 /*
1409 * Unlink, then relink bblocks to avoid various
1410 * tricky situations when the two targets of the branch
1411 * are equal, or will become equal after the change.
1412 */
1413 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1414 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1415
1416 bb->last_ins->inst_true_bb = bbn_first_inst->inst_target_bb;
1417
1418 mono_link_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1419 mono_link_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1420
1421 changed = TRUE;
1422 continue;
1423 }
1424
1425 bbn = bb->last_ins->inst_false_bb;
1426 bbn_first_inst = mono_bb_first_inst (bbn, filter);
1427 if (bbn && bb->region == bbn->region && bbn_first_inst && bbn_first_inst->opcode == OP_BR &&
1428 bbn_first_inst->inst_target_bb->region == bb->region) {
1429 if (cfg->verbose_level > 2)
1430 g_print ("cbranch2 to branch triggered %d -> (%d) %d (0x%02x)\n",
1431 bb->block_num, bbn->block_num, bbn_first_inst->inst_target_bb->block_num,
1432 bbn_first_inst->opcode);
1433
1434 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1435 mono_unlink_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1436
1437 bb->last_ins->inst_false_bb = bbn_first_inst->inst_target_bb;
1438
1439 mono_link_bblock (cfg, bb, bb->last_ins->inst_true_bb);
1440 mono_link_bblock (cfg, bb, bb->last_ins->inst_false_bb);
1441
1442 changed = TRUE;
1443 continue;
1444 }
1445
1446 bbn = bb->last_ins->inst_false_bb;
1447 /*
1448 * If bb is an extended bb, it could contain an inside branch to bbn.
1449 * FIXME: Enable the optimization if that is not true.
1450 * If bblocks_linked () is true, then merging bb and bbn
1451 * would require addition of an extra branch at the end of bbn
1452 * slowing down loops.
1453 */
1454 if (bbn && bb->region == bbn->region && bbn->in_count == 1 && cfg->enable_extended_bblocks && bbn != cfg->bb_exit && !bb->extended && !bbn->out_of_line && !mono_bblocks_linked (bbn, bb)) {
1455 g_assert (bbn->in_bb [0] == bb);
1456 if (cfg->verbose_level > 2)
1457 g_print ("merge false branch target triggered BB%d -> BB%d\n", bb->block_num, bbn->block_num);
1458 mono_merge_basic_blocks (cfg, bb, bbn);
1459 changed = TRUE;
1460 continue;
1461 }
1462 }
1463
1464 if (bb->last_ins && MONO_IS_COND_BRANCH_NOFP (bb->last_ins)) {
1465 if (bb->last_ins->inst_false_bb && bb->last_ins->inst_false_bb->out_of_line && (bb->region == bb->last_ins->inst_false_bb->region) && !cfg->disable_out_of_line_bblocks) {
1466 /* Reverse the branch */
1467 bb->last_ins->opcode = mono_reverse_branch_op (bb->last_ins->opcode);
1468 bbn = bb->last_ins->inst_false_bb;
1469 bb->last_ins->inst_false_bb = bb->last_ins->inst_true_bb;
1470 bb->last_ins->inst_true_bb = bbn;
1471
1472 move_basic_block_to_end (cfg, bb->last_ins->inst_true_bb);
1473 if (cfg->verbose_level > 2)
1474 g_print ("cbranch to throw block triggered %d.\n",
1475 bb->block_num);
1476 }
1477 }
1478 }
1479 }
1480 } while (changed && (niterations > 0));
1481 }
1482
1483 #else /* !DISABLE_JIT */
1484
1485 MONO_EMPTY_SOURCE_FILE (branch_opts);
1486
1487 #endif /* !DISABLE_JIT */
Mirror of the official Mono project git repository