From e2d87487ff4432a974c8b0d09a06e35935e9eb83 Mon Sep 17 00:00:00 2001 From: Thomas Schwinge Date: Wed, 7 May 2014 12:31:26 +0200 Subject: [PATCH] Really delete gcc/loop-unswitch.c. gcc/ * loop-unswitch.c: Delete. From-SVN: r210150 --- gcc/ChangeLog | 5 +- gcc/loop-unswitch.c | 477 -------------------------------------------- 2 files changed, 4 insertions(+), 478 deletions(-) delete mode 100644 gcc/loop-unswitch.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d5e6a0a3150..e5033a04f26 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,7 @@ +2014-05-07 Thomas Schwinge + + * loop-unswitch.c: Delete. + 2014-05-07 Richard Biener * config.gcc: Always set need_64bit_hwint to yes. @@ -2294,7 +2298,6 @@ 2014-04-23 Richard Biener * Makefile.in (OBJS): Remove loop-unswitch.o. - * loop-unswitch.c: Delete. * tree-pass.h (make_pass_rtl_unswitch): Remove. * passes.def (pass_rtl_unswitch): Likewise. * loop-init.c (gate_rtl_unswitch): Likewise. diff --git a/gcc/loop-unswitch.c b/gcc/loop-unswitch.c deleted file mode 100644 index fff0fd16e52..00000000000 --- a/gcc/loop-unswitch.c +++ /dev/null @@ -1,477 +0,0 @@ -/* Loop unswitching for GNU compiler. - Copyright (C) 2002-2014 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 3, or (at your option) any later -version. - -GCC is distributed in the hope that it will be useful, but WITHOUT ANY -WARRANTY; without even the implied warranty of MERCHANTABILITY or -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 COPYING3. If not see -. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "tm.h" -#include "rtl.h" -#include "hard-reg-set.h" -#include "obstack.h" -#include "basic-block.h" -#include "cfgloop.h" -#include "params.h" -#include "expr.h" -#include "dumpfile.h" - -/* This pass moves constant conditions out of loops, duplicating the loop - in progress, i.e. this code: - - while (loop_cond) - { - A; - if (cond) - branch1; - else - branch2; - B; - if (cond) - branch3; - C; - } - where nothing inside the loop alters cond is transformed - into - - if (cond) - { - while (loop_cond) - { - A; - branch1; - B; - branch3; - C; - } - } - else - { - while (loop_cond) - { - A; - branch2; - B; - C; - } - } - - Duplicating the loop might lead to code growth exponential in number of - branches inside loop, so we limit the number of unswitchings performed - in a single loop to PARAM_MAX_UNSWITCH_LEVEL. We only perform the - transformation on innermost loops, as the benefit of doing it on loops - containing subloops would not be very large compared to complications - with handling this case. */ - -static struct loop *unswitch_loop (struct loop *, basic_block, rtx, rtx); -static bool 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 - true, with probability PROB. If CINSN is not NULL, it is the insn to copy - in order to create a jump. */ - -rtx -compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob, - rtx cinsn) -{ - rtx seq, jump, cond; - enum machine_mode mode; - - mode = GET_MODE (op0); - if (mode == VOIDmode) - mode = GET_MODE (op1); - - start_sequence (); - if (GET_MODE_CLASS (mode) == MODE_CC) - { - /* A hack -- there seems to be no easy generic way how to make a - conditional jump from a ccmode comparison. */ - gcc_assert (cinsn); - cond = XEXP (SET_SRC (pc_set (cinsn)), 0); - 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 - { - 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, -1); - jump = get_last_insn (); - gcc_assert (JUMP_P (jump)); - JUMP_LABEL (jump) = label; - LABEL_NUSES (label)++; - } - add_int_reg_note (jump, REG_BR_PROB, prob); - - seq = get_insns (); - end_sequence (); - - return seq; -} - -/* Main entry point. Perform loop unswitching on all suitable loops. */ -void -unswitch_loops (void) -{ - struct loop *loop; - bool changed = false; - - /* Go through inner loops (only original ones). */ - - FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) - changed |= unswitch_single_loop (loop, NULL_RTX, 0); - - iv_analysis_done (); - - /* If we unswitched any loop discover new loops that are eventually - exposed by making irreducible regions reducible. */ - if (changed) - { - calculate_dominance_info (CDI_DOMINATORS); - fix_loop_structure (NULL); - } -} - -/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its - basic blocks (for what it means see comments below). In case condition - compares loop invariant cc mode register, return the jump in CINSN. */ - -static rtx -may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn) -{ - 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 (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, 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 - are unable to update dominator/irreducible loop information correctly). */ - if (!just_once_each_iteration_p (loop, bb)) - return NULL_RTX; - - /* Condition must be invariant. */ - test = get_condition (BB_END (bb), &at, true, false); - if (!test) - return NULL_RTX; - - mode = VOIDmode; - for (i = 0; i < 2; i++) - { - op[i] = XEXP (test, i); - - if (CONSTANT_P (op[i])) - continue; - - if (!iv_analyze (at, op[i], &iv)) - return NULL_RTX; - if (iv.step != const0_rtx - || iv.first_special) - return NULL_RTX; - - op[i] = get_iv_value (&iv, const0_rtx); - if (iv.extend != IV_UNKNOWN_EXTEND - && iv.mode != iv.extend_mode) - op[i] = lowpart_subreg (iv.mode, op[i], iv.extend_mode); - if (mode == VOIDmode) - mode = iv.mode; - else - gcc_assert (mode == iv.mode); - } - - if (GET_MODE_CLASS (mode) == MODE_CC) - { - if (at != BB_END (bb)) - return NULL_RTX; - - 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])); -} - -/* Reverses CONDition; returns NULL if we cannot. */ -rtx -reversed_condition (rtx cond) -{ - enum rtx_code reversed; - reversed = reversed_comparison_code (cond, NULL); - if (reversed == UNKNOWN) - return NULL_RTX; - else - return gen_rtx_fmt_ee (reversed, - GET_MODE (cond), XEXP (cond, 0), - XEXP (cond, 1)); -} - -/* Unswitch single LOOP. COND_CHECKED holds list of conditions we already - unswitched on and are therefore known to be true in this LOOP. NUM is - 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. - Returns true LOOP was unswitched. */ -static bool -unswitch_single_loop (struct loop *loop, rtx cond_checked, int num) -{ - basic_block *bbs; - struct loop *nloop; - unsigned i; - rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn; - int repeat; - edge e; - HOST_WIDE_INT iterations; - - /* Do not unswitch too much. */ - if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) - { - if (dump_file) - fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); - return false; - } - - /* Only unswitch innermost loops. */ - if (loop->inner) - { - if (dump_file) - fprintf (dump_file, ";; Not unswitching, not innermost loop\n"); - return false; - } - - /* We must be able to duplicate loop body. */ - if (!can_duplicate_loop_p (loop)) - { - if (dump_file) - fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n"); - return false; - } - - /* The loop should not be too large, to limit code growth. */ - if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) - { - if (dump_file) - fprintf (dump_file, ";; Not unswitching, loop too big\n"); - return false; - } - - /* Do not unswitch in cold areas. */ - if (optimize_loop_for_size_p (loop)) - { - if (dump_file) - fprintf (dump_file, ";; Not unswitching, not hot area\n"); - return false; - } - - /* Nor if the loop usually does not roll. */ - iterations = get_estimated_loop_iterations_int (loop); - if (iterations >= 0 && iterations <= 1) - { - if (dump_file) - fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n"); - return false; - } - - do - { - repeat = 0; - cinsn = NULL_RTX; - - /* Find a bb to unswitch on. */ - bbs = get_loop_body (loop); - iv_analysis_loop_init (loop); - for (i = 0; i < loop->num_nodes; i++) - if ((cond = may_unswitch_on (bbs[i], loop, &cinsn))) - break; - - if (i == loop->num_nodes) - { - free (bbs); - return false; - } - - 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); - } - - if (cond == const_true_rtx) - { - /* Remove false path. */ - e = FALLTHRU_EDGE (bbs[i]); - remove_path (e); - free (bbs); - repeat = 1; - } - else if (cond == const0_rtx) - { - /* Remove true path. */ - e = BRANCH_EDGE (bbs[i]); - remove_path (e); - free (bbs); - repeat = 1; - } - } while (repeat); - - /* We found the condition we can unswitch on. */ - conds = alloc_EXPR_LIST (0, cond, cond_checked); - if (rcond) - rconds = alloc_EXPR_LIST (0, rcond, cond_checked); - else - rconds = cond_checked; - - if (dump_file) - fprintf (dump_file, ";; Unswitching loop\n"); - - /* Unswitch the loop on this condition. */ - nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn); - gcc_assert (nloop); - - /* Invoke itself on modified loops. */ - 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); - - return true; -} - -/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support - unswitching of innermost loops. UNSWITCH_ON must be executed in every - iteration, i.e. it must dominate LOOP latch. COND is the condition - determining which loop is entered. Returns NULL if impossible, new loop - otherwise. The new loop is entered if COND is true. If CINSN is not - NULL, it is the insn in that COND is compared. */ - -static struct loop * -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; - struct loop *nloop; - int irred_flag, prob; - rtx seq; - - /* Some sanity checking. */ - 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. */ - irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; - entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; - if (!duplicate_loop_to_header_edge (loop, entry, 1, - NULL, NULL, NULL, 0)) - return NULL; - entry->flags |= irred_flag; - - /* Record the block with condition we unswitch on. */ - unswitch_on_alt = get_bb_copy (unswitch_on); - true_edge = BRANCH_EDGE (unswitch_on_alt); - false_edge = FALLTHRU_EDGE (unswitch_on); - latch_edge = single_succ_edge (get_bb_copy (loop->latch)); - - /* Create a block with the condition. */ - prob = true_edge->probability; - switch_bb = create_empty_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb); - seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond), - block_label (true_edge->dest), - prob, cinsn); - emit_insn_after (seq, BB_END (switch_bb)); - e = make_edge (switch_bb, true_edge->dest, 0); - e->probability = prob; - e->count = apply_probability (latch_edge->count, prob); - e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU); - e->probability = false_edge->probability; - e->count = apply_probability (latch_edge->count, false_edge->probability); - - if (irred_flag) - { - switch_bb->flags |= BB_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; - 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 (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); - - copy_loop_info (loop, nloop); - /* Remove branches that are now unreachable in new loops. */ - remove_path (true_edge); - remove_path (false_edge); - - /* Preserve the simple loop preheaders. */ - split_edge (loop_preheader_edge (loop)); - split_edge (loop_preheader_edge (nloop)); - - return nloop; -} -- 2.30.2