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