X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Floop-unswitch.c;h=77524d8bfe39ca299ec3be230665438fc28484b3;hp=6febbed966b0f0eceb6a93daf72931d0f76e9728;hb=ccd3dcb6fb0fb5c9e11e56556c0e6b2233ee8391;hpb=f08e8669bcacdba24546faf4638aa6be5cc0c693 diff --git a/gcc/loop-unswitch.c b/gcc/loop-unswitch.c index 6febbed966b..77524d8bfe3 100644 --- a/gcc/loop-unswitch.c +++ b/gcc/loop-unswitch.c @@ -1,11 +1,12 @@ /* Loop unswitching for GNU compiler. - Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010 + Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -14,9 +15,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -24,6 +24,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tm.h" #include "rtl.h" #include "hard-reg-set.h" +#include "obstack.h" #include "basic-block.h" #include "cfgloop.h" #include "cfglayout.h" @@ -78,9 +79,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA containing subloops would not be very large compared to complications with handling this case. */ -static struct loop *unswitch_loop (struct loops *, struct loop *, - basic_block, rtx, rtx); -static void unswitch_single_loop (struct loops *, struct loop *, rtx, int); +static struct loop *unswitch_loop (struct loop *, basic_block, rtx, rtx); +static void unswitch_single_loop (struct loop *, rtx, int); static rtx may_unswitch_on (basic_block, struct loop *, rtx *); /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if @@ -103,64 +103,54 @@ compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob, { /* A hack -- there seems to be no easy generic way how to make a conditional jump from a ccmode comparison. */ - if (!cinsn) - abort (); + gcc_assert (cinsn); cond = XEXP (SET_SRC (pc_set (cinsn)), 0); - if (GET_CODE (cond) != comp - || !rtx_equal_p (op0, XEXP (cond, 0)) - || !rtx_equal_p (op1, XEXP (cond, 1))) - abort (); + gcc_assert (GET_CODE (cond) == comp); + gcc_assert (rtx_equal_p (op0, XEXP (cond, 0))); + gcc_assert (rtx_equal_p (op1, XEXP (cond, 1))); emit_jump_insn (copy_insn (PATTERN (cinsn))); jump = get_last_insn (); + gcc_assert (JUMP_P (jump)); JUMP_LABEL (jump) = JUMP_LABEL (cinsn); LABEL_NUSES (JUMP_LABEL (jump))++; redirect_jump (jump, label, 0); } else { - if (cinsn) - abort (); + gcc_assert (!cinsn); op0 = force_operand (op0, NULL_RTX); op1 = force_operand (op1, NULL_RTX); do_compare_rtx_and_jump (op0, op1, comp, 0, - mode, NULL_RTX, NULL_RTX, label); + mode, NULL_RTX, NULL_RTX, label, -1); jump = get_last_insn (); + gcc_assert (JUMP_P (jump)); JUMP_LABEL (jump) = label; LABEL_NUSES (label)++; } - REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob), - REG_NOTES (jump)); + add_reg_note (jump, REG_BR_PROB, GEN_INT (prob)); + seq = get_insns (); end_sequence (); return seq; } -/* Main entry point. Perform loop unswitching on all suitable LOOPS. */ +/* Main entry point. Perform loop unswitching on all suitable loops. */ void -unswitch_loops (struct loops *loops) +unswitch_loops (void) { - int i, num; + loop_iterator li; struct loop *loop; /* Go through inner loops (only original ones). */ - num = loops->num; - for (i = 1; i < num; i++) + FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) { - /* Removed loop? */ - loop = loops->parray[i]; - if (!loop) - continue; - - if (loop->inner) - continue; - - unswitch_single_loop (loops, loop, NULL_RTX, 0); + unswitch_single_loop (loop, NULL_RTX, 0); #ifdef ENABLE_CHECKING verify_dominators (CDI_DOMINATORS); - verify_loop_structure (loops); + verify_loop_structure (); #endif } @@ -174,20 +164,20 @@ unswitch_loops (struct loops *loops) static rtx may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn) { - rtx test, at, insn, op[2]; + rtx test, at, op[2], stest; struct rtx_iv iv; unsigned i; enum machine_mode mode; /* BB must end in a simple conditional jump. */ - if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next) + if (EDGE_COUNT (bb->succs) != 2) return NULL_RTX; if (!any_condjump_p (BB_END (bb))) return NULL_RTX; /* With branches inside loop. */ - if (!flow_bb_inside_loop_p (loop, bb->succ->dest) - || !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest)) + if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest) + || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest)) return NULL_RTX; /* It must be executed just once each iteration (because otherwise we @@ -196,7 +186,7 @@ may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn) return NULL_RTX; /* Condition must be invariant. */ - test = get_condition (BB_END (bb), &at, true); + test = get_condition (BB_END (bb), &at, true, false); if (!test) return NULL_RTX; @@ -207,8 +197,7 @@ may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn) if (CONSTANT_P (op[i])) continue; - insn = iv_get_reaching_def (at, op[i]); - if (!iv_analyze (insn, op[i], &iv)) + if (!iv_analyze (at, op[i], &iv)) return NULL_RTX; if (iv.step != const0_rtx || iv.first_special) @@ -225,14 +214,20 @@ may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn) if (at != BB_END (bb)) return NULL_RTX; - *cinsn = BB_END (bb); if (!rtx_equal_p (op[0], XEXP (test, 0)) || !rtx_equal_p (op[1], XEXP (test, 1))) return NULL_RTX; + *cinsn = BB_END (bb); return test; } + stest = simplify_gen_relational (GET_CODE (test), SImode, + mode, op[0], op[1]); + if (stest == const0_rtx + || stest == const_true_rtx) + return stest; + return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode, op[0], op[1])); } @@ -256,67 +251,67 @@ reversed_condition (rtx cond) number of unswitchings done; do not allow it to grow too much, it is too easy to create example on that the code would grow exponentially. */ static void -unswitch_single_loop (struct loops *loops, struct loop *loop, - rtx cond_checked, int num) +unswitch_single_loop (struct loop *loop, rtx cond_checked, int num) { basic_block *bbs; struct loop *nloop; unsigned i; - rtx cond, rcond, conds, rconds, acond, cinsn = NULL_RTX; + rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn; int repeat; edge e; /* Do not unswitch too much. */ if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) { - if (rtl_dump_file) - fprintf (rtl_dump_file, ";; Not unswitching anymore, hit max level\n"); + if (dump_file) + fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); return; } /* Only unswitch innermost loops. */ if (loop->inner) { - if (rtl_dump_file) - fprintf (rtl_dump_file, ";; Not unswitching, not innermost loop\n"); + if (dump_file) + fprintf (dump_file, ";; Not unswitching, not innermost loop\n"); return; } /* We must be able to duplicate loop body. */ if (!can_duplicate_loop_p (loop)) { - if (rtl_dump_file) - fprintf (rtl_dump_file, ";; Not unswitching, can't duplicate loop\n"); + if (dump_file) + fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n"); return; } /* The loop should not be too large, to limit code growth. */ if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) { - if (rtl_dump_file) - fprintf (rtl_dump_file, ";; Not unswitching, loop too big\n"); + if (dump_file) + fprintf (dump_file, ";; Not unswitching, loop too big\n"); return; } /* Do not unswitch in cold areas. */ - if (!maybe_hot_bb_p (loop->header)) + if (optimize_loop_for_size_p (loop)) { - if (rtl_dump_file) - fprintf (rtl_dump_file, ";; Not unswitching, not hot area\n"); + if (dump_file) + fprintf (dump_file, ";; Not unswitching, not hot area\n"); return; } /* Nor if the loop usually does not roll. */ if (expected_loop_iterations (loop) < 1) { - if (rtl_dump_file) - fprintf (rtl_dump_file, ";; Not unswitching, loop iterations < 1\n"); + if (dump_file) + fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n"); return; } do { repeat = 0; + cinsn = NULL_RTX; /* Find a bb to unswitch on. */ bbs = get_loop_body (loop); @@ -331,19 +326,23 @@ unswitch_single_loop (struct loops *loops, struct loop *loop, return; } - rcond = reversed_condition (cond); - if (rcond) - rcond = canon_condition (rcond); + if (cond != const0_rtx + && cond != const_true_rtx) + { + rcond = reversed_condition (cond); + if (rcond) + rcond = canon_condition (rcond); - /* Check whether the result can be predicted. */ - for (acond = cond_checked; acond; acond = XEXP (acond, 1)) - simplify_using_condition (XEXP (acond, 0), &cond, NULL); + /* Check whether the result can be predicted. */ + for (acond = cond_checked; acond; acond = XEXP (acond, 1)) + simplify_using_condition (XEXP (acond, 0), &cond, NULL); + } if (cond == const_true_rtx) { /* Remove false path. */ e = FALLTHRU_EDGE (bbs[i]); - remove_path (loops, e); + remove_path (e); free (bbs); repeat = 1; } @@ -351,7 +350,7 @@ unswitch_single_loop (struct loops *loops, struct loop *loop, { /* Remove true path. */ e = BRANCH_EDGE (bbs[i]); - remove_path (loops, e); + remove_path (e); free (bbs); repeat = 1; } @@ -364,21 +363,22 @@ unswitch_single_loop (struct loops *loops, struct loop *loop, else rconds = cond_checked; - if (rtl_dump_file) - fprintf (rtl_dump_file, ";; Unswitching loop\n"); + if (dump_file) + fprintf (dump_file, ";; Unswitching loop\n"); /* Unswitch the loop on this condition. */ - nloop = unswitch_loop (loops, loop, bbs[i], cond, cinsn); - if (!nloop) - abort (); + nloop = unswitch_loop (loop, bbs[i], cond, cinsn); + gcc_assert (nloop); /* Invoke itself on modified loops. */ - unswitch_single_loop (loops, nloop, rconds, num + 1); - unswitch_single_loop (loops, loop, conds, num + 1); + unswitch_single_loop (nloop, rconds, num + 1); + unswitch_single_loop (loop, conds, num + 1); free_EXPR_LIST_node (conds); if (rcond) free_EXPR_LIST_node (rconds); + + free (bbs); } /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support @@ -389,50 +389,37 @@ unswitch_single_loop (struct loops *loops, struct loop *loop, NULL, it is the insn in that COND is compared. */ static struct loop * -unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on, - rtx cond, rtx cinsn) +unswitch_loop (struct loop *loop, basic_block unswitch_on, rtx cond, rtx cinsn) { edge entry, latch_edge, true_edge, false_edge, e; - basic_block switch_bb, unswitch_on_alt, src; + basic_block switch_bb, unswitch_on_alt; struct loop *nloop; - sbitmap zero_bitmap; int irred_flag, prob; rtx seq; /* Some sanity checking. */ - if (!flow_bb_inside_loop_p (loop, unswitch_on)) - abort (); - if (!unswitch_on->succ || !unswitch_on->succ->succ_next || - unswitch_on->succ->succ_next->succ_next) - abort (); - if (!just_once_each_iteration_p (loop, unswitch_on)) - abort (); - if (loop->inner) - abort (); - if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->dest)) - abort (); - if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->succ_next->dest)) - abort (); + gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); + gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); + gcc_assert (just_once_each_iteration_p (loop, unswitch_on)); + gcc_assert (!loop->inner); + gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest)); + gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest)); entry = loop_preheader_edge (loop); /* Make a copy. */ - src = entry->src; irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; - zero_bitmap = sbitmap_alloc (2); - sbitmap_zero (zero_bitmap); - if (!duplicate_loop_to_header_edge (loop, entry, loops, 1, - zero_bitmap, NULL, NULL, NULL, 0)) + if (!duplicate_loop_to_header_edge (loop, entry, 1, + NULL, NULL, NULL, 0)) return NULL; - free (zero_bitmap); entry->flags |= irred_flag; /* Record the block with condition we unswitch on. */ - unswitch_on_alt = unswitch_on->rbi->copy; + unswitch_on_alt = get_bb_copy (unswitch_on); true_edge = BRANCH_EDGE (unswitch_on_alt); false_edge = FALLTHRU_EDGE (unswitch_on); - latch_edge = loop->latch->rbi->copy->succ; + latch_edge = single_succ_edge (get_bb_copy (loop->latch)); /* Create a block with the condition. */ prob = true_edge->probability; @@ -451,32 +438,29 @@ unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on, if (irred_flag) { switch_bb->flags |= BB_IRREDUCIBLE_LOOP; - switch_bb->succ->flags |= EDGE_IRREDUCIBLE_LOOP; - switch_bb->succ->succ_next->flags |= EDGE_IRREDUCIBLE_LOOP; + EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP; + EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP; } else { switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP; - switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP; - switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP; + EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP; + EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP; } /* Loopify from the copy of LOOP body, constructing the new loop. */ - nloop = loopify (loops, latch_edge, - loop->header->rbi->copy->pred, switch_bb); + nloop = loopify (latch_edge, + single_pred_edge (get_bb_copy (loop->header)), switch_bb, + BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true, + prob, REG_BR_PROB_BASE - prob); /* Remove branches that are now unreachable in new loops. */ - remove_path (loops, true_edge); - remove_path (loops, false_edge); - - /* One of created loops do not have to be subloop of the outer loop now, - so fix its placement in loop data structure. */ - fix_loop_placement (loop); - fix_loop_placement (nloop); + remove_path (true_edge); + remove_path (false_edge); /* Preserve the simple loop preheaders. */ - loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX); - loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX); + split_edge (loop_preheader_edge (loop)); + split_edge (loop_preheader_edge (nloop)); return nloop; }