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