From 617b465c7f1fa399d376f89a1b255fbb39e4e738 Mon Sep 17 00:00:00 2001 From: Zdenek Dvorak Date: Sat, 8 Feb 2003 15:29:00 +0100 Subject: cfgloop.h (fix_loop_placement, [...]): Declare. * cfgloop.h (fix_loop_placement, can_duplicate_loop_p, duplicate_loop_to_header_edge, loopify, remove_path, split_loop_bb): Declare. (DLTHE_FLAG_UPDATE_FREQ): New. * cfgloopmanip.c (duplicate_loop, duplicate_subloops, copy_loops_to, loop_redirect_edge, loop_delete_branch_edge, copy_bbs, remove_bbs, rpe_enum_p, find_branch, alp_enum_p, add_loop, fix_loop_placements, fix_bb_placement, fix_bb_placements, place_new_loop, scale_loop_frequencies, scale_bbs_frequencies, record_exit_edges): New static functions. (fix_loop_placement, can_duplicate_loop_p, duplicate_loop_to_header_edge, loopify, remove_path, split_loop_bb): New functions. * cfgloop.h (loop_optimizer_init, loop_optimizer_finalize, unswitch_loops): Declare. * loop-init.c: New file. * loop-unswitch.c: New file. * Makefile.in (loop-init.o, loop-unswitch.o): New. * params.def (PARAM_MAX_UNSWITCH_INSNS, PARAM_MAX_UNSWITCH_LEVEL): New. * toplev.c (DFI_loop2): New dump. (flag_unswitch_loops): New. (lang_independent_options): Add it. (rest_of_compilation): Call new loop optimizer. (parse_options_and_default_flags): Turn flag_unswitch_loops on with -O3. From-SVN: r62578 --- gcc/loop-unswitch.c | 412 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 412 insertions(+) create mode 100644 gcc/loop-unswitch.c (limited to 'gcc/loop-unswitch.c') diff --git a/gcc/loop-unswitch.c b/gcc/loop-unswitch.c new file mode 100644 index 00000000000..8d6654c520e --- /dev/null +++ b/gcc/loop-unswitch.c @@ -0,0 +1,412 @@ +/* Loop unswitching for GNU compiler. + Copyright (C) 2002 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 +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 COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "rtl.h" +#include "hard-reg-set.h" +#include "basic-block.h" +#include "cfgloop.h" +#include "cfglayout.h" +#include "params.h" +#include "output.h" +#include "expr.h" + +/* This pass moves constant conditions out of loops, duplicating the loop + in progres, 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 PARAMS ((struct loops *, + struct loop *, basic_block)); +static void unswitch_single_loop PARAMS ((struct loops *, struct loop *, + rtx, int)); +static bool may_unswitch_on_p PARAMS ((struct loops *, basic_block, + struct loop *, basic_block *)); +static rtx reversed_condition PARAMS ((rtx)); + +/* Main entry point. Perform loop unswitching on all suitable LOOPS. */ +void +unswitch_loops (loops) + struct loops *loops; +{ + int i, num; + struct loop *loop; + + /* Go through inner loops (only original ones). */ + num = loops->num; + + for (i = 1; i < num; i++) + { + /* Removed loop? */ + loop = loops->parray[i]; + if (!loop) + continue; + + if (loop->inner) + continue; + + unswitch_single_loop (loops, loop, NULL_RTX, 0); +#ifdef ENABLE_CHECKING + verify_dominators (loops->cfg.dom); + verify_loop_structure (loops); +#endif + } +} + +/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its + basic blocks (for what it means see comments below). List of basic blocks + inside LOOP is provided in BODY to save time. */ +static bool +may_unswitch_on_p (loops, bb, loop, body) + struct loops *loops; + basic_block bb; + struct loop *loop; + basic_block *body; +{ + rtx test; + unsigned i; + + /* BB must end in a simple conditional jump. */ + if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next) + return false; + if (!any_condjump_p (bb->end)) + return false; + + /* 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)) + return false; + + /* 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 (loops, loop, bb)) + return false; + + /* Condition must be invariant. We use just a stupid test of invariantness + of the condition: all used regs must not be modified inside loop body. */ + test = get_condition (bb->end, NULL); + if (!test) + return false; + + for (i = 0; i < loop->num_nodes; i++) + if (modified_between_p (test, body[i]->head, NEXT_INSN (body[i]->end))) + return false; + + return true; +} + +/* Reverses CONDition; returns NULL if we cannot. */ +static rtx +reversed_condition (cond) + 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. */ +static void +unswitch_single_loop (loops, loop, cond_checked, num) + struct loops *loops; + struct loop *loop; + rtx cond_checked; + int num; +{ + basic_block *bbs, bb; + struct loop *nloop; + unsigned i; + int true_first; + rtx cond, rcond, conds, rconds, acond, split_before; + int always_true; + int always_false; + 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"); + return; + } + + /* Only unswitch innermost loops. */ + if (loop->inner) + { + if (rtl_dump_file) + fprintf (rtl_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"); + 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"); + return; + } + + /* Do not unswitch in cold areas. */ + if (!maybe_hot_bb_p (loop->header)) + { + if (rtl_dump_file) + fprintf (rtl_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"); + return; + } + + do + { + repeat = 0; + + /* Find a bb to unswitch on. */ + bbs = get_loop_body (loop); + for (i = 0; i < loop->num_nodes; i++) + if (may_unswitch_on_p (loops, bbs[i], loop, bbs)) + break; + + if (i == loop->num_nodes) + { + free (bbs); + return; + } + + if (!(cond = get_condition (bbs[i]->end, &split_before))) + abort (); + rcond = reversed_condition (cond); + + /* Check whether the result can be predicted. */ + always_true = 0; + always_false = 0; + for (acond = cond_checked; acond; acond = XEXP (acond, 1)) + { + if (rtx_equal_p (cond, XEXP (acond, 0))) + { + always_true = 1; + break; + } + if (rtx_equal_p (rcond, XEXP (acond, 0))) + { + always_false = 1; + break; + } + } + + if (always_true) + { + /* Remove false path. */ + for (e = bbs[i]->succ; !(e->flags & EDGE_FALLTHRU); e = e->succ_next); + remove_path (loops, e); + free (bbs); + repeat = 1; + } + else if (always_false) + { + /* Remove true path. */ + for (e = bbs[i]->succ; e->flags & EDGE_FALLTHRU; e = e->succ_next); + remove_path (loops, 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; + + /* Separate condition in a single basic block. */ + bb = split_loop_bb (loops, bbs[i], PREV_INSN (split_before))->dest; + free (bbs); + true_first = !(bb->succ->flags & EDGE_FALLTHRU); + if (rtl_dump_file) + fprintf (rtl_dump_file, ";; Unswitching loop\n"); + + /* Unswitch the loop on this condition. */ + nloop = unswitch_loop (loops, loop, bb); + if (!nloop) + abort (); + + /* Invoke itself on modified loops. */ + unswitch_single_loop (loops, nloop, true_first ? conds : rconds, num + 1); + unswitch_single_loop (loops, loop, true_first ? rconds : conds, num + 1); + + free_EXPR_LIST_node (conds); + if (rcond) + free_EXPR_LIST_node (rconds); +} + +/* 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, and should only contain code + for the condition we unswitch on. Returns NULL if impossible, new + loop otherwise. */ +static struct loop * +unswitch_loop (loops, loop, unswitch_on) + struct loops *loops; + struct loop *loop; + basic_block unswitch_on; +{ + edge entry, e, latch_edge; + basic_block switch_bb, unswitch_on_alt, src; + struct loop *nloop; + sbitmap zero_bitmap; + int irred_flag; + + /* 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 (loops, 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 (); + + /* Will we be able to perform redirection? */ + if (!any_condjump_p (unswitch_on->end)) + return NULL; + if (!cfg_layout_can_duplicate_bb_p (unswitch_on)) + return NULL; + + entry = loop_preheader_edge (loop); + + /* Make a copy. */ + src = entry->src; + irred_flag = src->flags & BB_IRREDUCIBLE_LOOP; + src->flags &= ~BB_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)) + return NULL; + free (zero_bitmap); + src->flags |= irred_flag; + + /* Record the block with condition we unswitch on. */ + unswitch_on_alt = RBI (unswitch_on)->copy; + + /* Make a copy of the block containing the condition; we will use + it as switch to decide which loop we want to use. */ + switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL); + switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP; + switch_bb->flags |= irred_flag; + add_to_dominance_info (loops->cfg.dom, switch_bb); + RBI (unswitch_on)->copy = unswitch_on_alt; + + /* Loopify from the copy of LOOP body, constructing the new loop. */ + for (latch_edge = RBI (loop->latch)->copy->succ; + latch_edge->dest != loop->header; + latch_edge = latch_edge->succ_next); + nloop = loopify (loops, latch_edge, + RBI (loop->header)->copy->pred, switch_bb); + + /* Remove branches that are now unreachable in new loops. We rely on the + fact that cfg_layout_duplicate_bb reverses list of edges. */ + for (e = unswitch_on->succ->succ_next->dest->pred; e; e = e->pred_next) + if (e->src != unswitch_on && + !dominated_by_p (loops->cfg.dom, e->src, e->dest)) + break; + remove_path (loops, unswitch_on->succ); + remove_path (loops, unswitch_on_alt->succ); + + /* One of created loops do not have to be subloop of the outer loop now, + so fix its placement in loop datastructure. */ + fix_loop_placement (loop); + fix_loop_placement (nloop); + + return nloop; +} -- cgit v1.2.1