2 * branch-opts.c: Branch optimizations support
5 * Patrik Torstensson (Patrik.Torstesson at gmail.com)
7 * (C) 2005 Ximian, Inc. http://www.ximian.com
12 * Used by the arch code to replace the exception handling
13 * with a direct branch. This is safe to do if the
14 * exception object isn't used, no rethrow statement and
15 * no filter statement (verify).
19 mono_branch_optimize_exception_target (MonoCompile *cfg, MonoBasicBlock *bb, const char * exname)
21 MonoMethod *method = cfg->method;
22 MonoMethodHeader *header = mono_method_get_header (method);
23 MonoExceptionClause *clause;
27 if (!(cfg->opt & MONO_OPT_EXCEPTION))
30 if (bb->region == -1 || !MONO_BBLOCK_IS_IN_REGION (bb, MONO_REGION_TRY))
33 exclass = mono_class_from_name (mono_get_corlib (), "System", exname);
34 /* search for the handler */
35 for (i = 0; i < header->num_clauses; ++i) {
36 clause = &header->clauses [i];
37 if (MONO_OFFSET_IN_CLAUSE (clause, bb->real_offset)) {
38 if (clause->flags == MONO_EXCEPTION_CLAUSE_NONE && clause->data.catch_class && mono_class_is_assignable_from (clause->data.catch_class, exclass)) {
41 /* get the basic block for the handler and
42 * check if the exception object is used.
43 * Flag is set during method_to_ir due to
44 * pop-op is optmized away in codegen (burg).
46 tbb = cfg->cil_offset_to_bb [clause->handler_offset];
47 if (tbb && tbb->flags & BB_EXCEPTION_DEAD_OBJ && !(tbb->flags & BB_EXCEPTION_UNSAFE)) {
48 MonoBasicBlock *targetbb = tbb;
49 gboolean unsafe = FALSE;
51 /* Check if this catch clause is ok to optimize by
52 * looking for the BB_EXCEPTION_UNSAFE in every BB that
53 * belongs to the same region.
55 * UNSAFE flag is set during method_to_ir (OP_RETHROW)
57 while (!unsafe && tbb->next_bb && tbb->region == tbb->next_bb->region) {
58 if (tbb->next_bb->flags & BB_EXCEPTION_UNSAFE) {
68 /* Create dummy inst to allow easier integration in
69 * arch dependent code (opcode ignored)
71 MONO_INST_NEW (cfg, jump, OP_BR);
73 /* Allocate memory for our branch target */
74 jump->inst_i1 = mono_mempool_alloc0 (cfg->mempool, sizeof (MonoInst));
75 jump->inst_true_bb = targetbb;
77 if (cfg->verbose_level > 2)
78 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);
86 /* Branching to an outer clause could skip inner clauses */
95 static const int int_cmov_opcodes [] = {
108 static const int long_cmov_opcodes [] = {
122 mono_if_conversion (MonoCompile *cfg)
124 #ifdef MONO_ARCH_HAVE_CMOV_OPS
126 gboolean changed = FALSE;
128 if (!(cfg->opt & MONO_OPT_CMOV))
131 // FIXME: Make this work with extended bblocks
134 * This pass requires somewhat optimized IR code so it should be run after
135 * local cprop/deadce. Also, it should be run before dominator computation, since
136 * it changes control flow.
138 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
139 MonoBasicBlock *bb1, *bb2;
142 /* Look for the IR code generated from cond ? a : b
153 if (!(bb->out_count == 2 && !bb->extended))
156 bb1 = bb->out_bb [0];
157 bb2 = bb->out_bb [1];
159 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]) {
160 MonoInst *prev, *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
161 gboolean simple, ret;
166 * Check that bb1 and bb2 are 'simple' and both assign to the same
169 /* FIXME: Get rid of the nops earlier */
171 while (ins1 && ins1->opcode == OP_NOP)
174 while (ins2 && ins2->opcode == OP_NOP)
176 if (!(ins1 && ins2 && ins1->dreg == ins2->dreg && ins1->dreg != -1))
180 for (tmp = ins1->next; tmp; tmp = tmp->next)
181 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
184 for (tmp = ins2->next; tmp; tmp = tmp->next)
185 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
191 /* We move ins1/ins2 before the compare so they should have no side effect */
192 if (!(MONO_INS_HAS_NO_SIDE_EFFECT (ins1) && MONO_INS_HAS_NO_SIDE_EFFECT (ins2)))
195 if (bb->last_ins && (bb->last_ins->opcode == OP_BR_REG || bb->last_ins->opcode == OP_BR))
198 /* Find the compare instruction */
199 /* FIXME: Optimize this using prev */
203 while (compare->next && !MONO_IS_COND_BRANCH_OP (compare->next)) {
205 compare = compare->next;
207 g_assert (compare->next && MONO_IS_COND_BRANCH_OP (compare->next));
208 branch = compare->next;
210 /* Moving ins1/ins2 could change the comparison */
212 if (!((compare->sreg1 != ins1->dreg) && (compare->sreg2 != ins1->dreg)))
216 comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
217 if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
221 /* ins->type might not be set */
222 if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
225 if (cfg->verbose_level > 2) {
226 printf ("\tBranch -> CMove optimization in BB%d on\n", bb->block_num);
227 printf ("\t\t"); mono_print_ins (compare);
228 printf ("\t\t"); mono_print_ins (compare->next);
229 printf ("\t\t"); mono_print_ins (ins1);
230 printf ("\t\t"); mono_print_ins (ins2);
237 /* Assignments to the return register must remain at the end of bbs */
239 ret = ins1->dreg == cfg->ret->dreg;
243 tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
246 /* Rewrite ins1 to emit to tmp_reg */
247 ins1->dreg = tmp_reg;
250 dreg = mono_alloc_dreg (cfg, STACK_I4);
254 /* Remove ins1/ins2 from bb1/bb2 */
255 MONO_REMOVE_INS (bb1, ins1);
256 MONO_REMOVE_INS (bb2, ins2);
258 /* Move ins1 and ins2 before the comparison */
259 /* ins1 comes first to avoid ins1 overwriting an argument of ins2 */
260 mono_bblock_insert_before_ins (bb, compare, ins2);
261 mono_bblock_insert_before_ins (bb, ins2, ins1);
263 /* Add cmov instruction */
264 MONO_INST_NEW (cfg, cmov, OP_NOP);
267 cmov->sreg2 = tmp_reg;
268 switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
270 cmov->opcode = int_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
273 cmov->opcode = long_cmov_opcodes [mono_opcode_to_cond (branch->opcode)];
276 g_assert_not_reached ();
278 mono_bblock_insert_after_ins (bb, compare, cmov);
281 /* Add an extra move */
282 MONO_INST_NEW (cfg, move, OP_MOVE);
283 move->dreg = cfg->ret->dreg;
285 mono_bblock_insert_after_ins (bb, cmov, move);
288 /* Rewrite the branch */
289 branch->opcode = OP_BR;
290 branch->inst_target_bb = bb1->out_bb [0];
291 mono_link_bblock (cfg, bb, branch->inst_target_bb);
293 /* Reorder bblocks */
294 mono_unlink_bblock (cfg, bb, bb1);
295 mono_unlink_bblock (cfg, bb, bb2);
296 mono_unlink_bblock (cfg, bb1, bb1->out_bb [0]);
297 mono_unlink_bblock (cfg, bb2, bb2->out_bb [0]);
298 mono_remove_bblock (cfg, bb1);
299 mono_remove_bblock (cfg, bb2);
301 /* Merge bb and its successor if possible */
302 if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
303 (bb->region == bb->out_bb [0]->region)) {
304 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
309 /* Look for the IR code generated from if (cond) <var> <- <a>
318 if ((bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) ||
319 (bb1->in_count == 1 && bb1->out_count == 1 && bb1->out_bb [0] == bb2)) {
320 MonoInst *prev, *compare, *branch, *ins1, *cmov, *tmp;
325 MonoBasicBlock *next_bb, *code_bb;
327 /* code_bb is the bblock containing code, next_bb is the successor bblock */
328 if (bb2->in_count == 1 && bb2->out_count == 1 && bb2->out_bb [0] == bb1) {
336 ins1 = code_bb->code;
341 /* Check that code_bb is simple */
343 for (tmp = ins1->next; tmp; tmp = tmp->next)
344 if (!((tmp->opcode == OP_NOP) || (tmp->opcode == OP_BR)))
350 /* We move ins1 before the compare so it should have no side effect */
351 if (!MONO_INS_HAS_NO_SIDE_EFFECT (ins1))
354 if (bb->last_ins && bb->last_ins->opcode == OP_BR_REG)
357 /* Find the compare instruction */
358 /* FIXME: Optimize this using prev */
362 while (compare->next && !MONO_IS_COND_BRANCH_OP (compare->next)) {
364 compare = compare->next;
366 g_assert (compare->next && MONO_IS_COND_BRANCH_OP (compare->next));
367 branch = compare->next;
370 comp_type = mono_opcode_to_type (branch->opcode, compare->opcode);
371 if (!((comp_type == CMP_TYPE_I) || (comp_type == CMP_TYPE_L)))
375 /* ins->type might not be set */
376 if (INS_INFO (ins1->opcode) [MONO_INST_DEST] != 'i')
380 if (cfg->ret && ins1->dreg == cfg->ret->dreg)
383 if (cfg->verbose_level > 2) {
384 printf ("\tBranch -> CMove optimization (2) in BB%d on\n", bb->block_num);
385 printf ("\t\t"); mono_print_ins (compare);
386 printf ("\t\t"); mono_print_ins (compare->next);
387 printf ("\t\t"); mono_print_ins (ins1);
394 tmp_reg = mono_alloc_dreg (cfg, STACK_I4);
397 /* Rewrite ins1 to emit to tmp_reg */
398 ins1->dreg = tmp_reg;
400 /* Remove ins1 from code_bb */
401 MONO_REMOVE_INS (code_bb, ins1);
403 /* Move ins1 before the comparison */
404 mono_bblock_insert_before_ins (bb, compare, ins1);
406 /* Add cmov instruction */
407 MONO_INST_NEW (cfg, cmov, OP_NOP);
410 cmov->sreg2 = tmp_reg;
411 cond = mono_opcode_to_cond (branch->opcode);
412 if (branch->inst_false_bb == code_bb)
413 cond = mono_negate_cond (cond);
414 switch (mono_opcode_to_type (branch->opcode, compare->opcode)) {
416 cmov->opcode = int_cmov_opcodes [cond];
419 cmov->opcode = long_cmov_opcodes [cond];
422 g_assert_not_reached ();
424 mono_bblock_insert_after_ins (bb, compare, cmov);
426 /* Rewrite the branch */
427 branch->opcode = OP_BR;
428 branch->inst_target_bb = next_bb;
429 mono_link_bblock (cfg, bb, branch->inst_target_bb);
431 /* Nullify the branch at the end of code_bb */
433 branch = code_bb->code;
434 MONO_DELETE_INS (code_bb, branch);
437 /* Reorder bblocks */
438 mono_unlink_bblock (cfg, bb, code_bb);
439 mono_unlink_bblock (cfg, code_bb, next_bb);
441 /* Merge bb and its successor if possible */
442 if ((bb->out_bb [0]->in_count == 1) && (bb->out_bb [0] != cfg->bb_exit) &&
443 (bb->region == bb->out_bb [0]->region)) {
444 mono_merge_basic_blocks (cfg, bb, bb->out_bb [0]);
451 for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
452 MonoBasicBlock *bb1, *bb2;
453 MonoInst *prev, *compare, *branch, *ins1, *ins2, *cmov, *move, *tmp;
454 gboolean simple, ret;
458 /* Look for the IR code generated from if (cond) <var> <- <a>
459 * after branch opts which is:
466 if (!(bb->out_count == 1 && bb->extended && bb->code && bb->code->next && bb->code->next->next))
469 mono_print_bb (bb, "");
471 /* Find the compare instruction */
475 while (compare->next->next && compare->next->next != bb->last_ins) {
477 compare = compare->next;
479 branch = compare->next;
480 if (!MONO_IS_COND_BRANCH_OP (branch))
486 if (cfg->opt & MONO_OPT_BRANCH)
487 mono_optimize_branches (cfg);
488 /* Merging bblocks could make some variables local */
489 mono_handle_global_vregs (cfg);
490 if (cfg->opt & (MONO_OPT_CONSPROP | MONO_OPT_COPYPROP))
491 mono_local_cprop2 (cfg);
492 mono_local_deadce (cfg);