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