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