X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gcc%2Fcfgloopanal.c;h=95ec929c7bde1ba4ce563a9717f3426dcc55db86;hb=b7c41230322051912d979e132c52100158745b73;hp=6ca4cb454c106e773e1cc2d6b27b66cd6f1df8b6;hpb=c263766cf3464e48e71481bf46ba6f5886d64433;p=gcc.git
diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c
index 6ca4cb454c1..95ec929c7bd 100644
--- a/gcc/cfgloopanal.c
+++ b/gcc/cfgloopanal.c
@@ -1,11 +1,11 @@
/* Natural loop analysis code for GNU compiler.
- Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2002-2019 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,65 +14,36 @@ 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"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
#include "rtl.h"
-#include "hard-reg-set.h"
-#include "basic-block.h"
+#include "tree.h"
+#include "predict.h"
+#include "memmodel.h"
+#include "emit-rtl.h"
#include "cfgloop.h"
+#include "explow.h"
#include "expr.h"
-#include "output.h"
-
-struct unmark_altered_insn_data;
-static void unmark_altered (rtx, rtx, regset);
-static void blocks_invariant_registers (basic_block *, int, regset);
-static void unmark_altered_insn (rtx, rtx, struct unmark_altered_insn_data *);
-static void blocks_single_set_registers (basic_block *, int, rtx *);
-static int invariant_rtx_wrto_regs_p_helper (rtx *, regset);
-static bool invariant_rtx_wrto_regs_p (rtx, regset);
-static rtx test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT);
-static bool constant_iterations (struct loop_desc *, unsigned HOST_WIDE_INT *,
- bool *);
-static bool simple_loop_exit_p (struct loop *, edge, regset,
- rtx *, struct loop_desc *);
-static rtx variable_initial_value (rtx, regset, rtx, rtx *, enum machine_mode);
-static rtx variable_initial_values (edge, rtx, enum machine_mode);
-static bool simple_condition_p (struct loop *, rtx, regset,
- struct loop_desc *);
-static basic_block simple_increment (struct loop *, rtx *, struct loop_desc *);
-static rtx count_strange_loop_iterations (rtx, rtx, enum rtx_code,
- int, rtx, enum machine_mode,
- enum machine_mode);
-static unsigned HOST_WIDEST_INT inverse (unsigned HOST_WIDEST_INT, int);
-static bool fits_in_mode_p (enum machine_mode mode, rtx expr);
-
-/* Computes inverse to X modulo (1 << MOD). */
-static unsigned HOST_WIDEST_INT
-inverse (unsigned HOST_WIDEST_INT x, int mod)
-{
- unsigned HOST_WIDEST_INT mask =
- ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
- unsigned HOST_WIDEST_INT rslt = 1;
- int i;
+#include "graphds.h"
+#include "params.h"
+#include "sreal.h"
+#include "regs.h"
+#include "function-abi.h"
- for (i = 0; i < mod - 1; i++)
- {
- rslt = (rslt * x) & mask;
- x = (x * x) & mask;
- }
-
- return rslt;
-}
+struct target_cfgloop default_target_cfgloop;
+#if SWITCHABLE_TARGET
+struct target_cfgloop *this_target_cfgloop = &default_target_cfgloop;
+#endif
/* Checks whether BB is executed exactly once in each LOOP iteration. */
+
bool
-just_once_each_iteration_p (struct loop *loop, basic_block bb)
+just_once_each_iteration_p (const class loop *loop, const_basic_block bb)
{
/* It must be executed at least once each iteration. */
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
@@ -89,1433 +60,474 @@ just_once_each_iteration_p (struct loop *loop, basic_block bb)
return true;
}
+/* Marks blocks and edges that are part of non-recognized loops; i.e. we
+ throw away all latch edges and mark blocks inside any remaining cycle.
+ Everything is a bit complicated due to fact we do not want to do this
+ for parts of cycles that only "pass" through some loop -- i.e. for
+ each cycle, we want to mark blocks that belong directly to innermost
+ loop containing the whole cycle.
-/* Unmarks modified registers; helper to blocks_invariant_registers. */
-static void
-unmark_altered (rtx what, rtx by ATTRIBUTE_UNUSED, regset regs)
-{
- if (GET_CODE (what) == SUBREG)
- what = SUBREG_REG (what);
- if (!REG_P (what))
- return;
- CLEAR_REGNO_REG_SET (regs, REGNO (what));
-}
-
-/* Marks registers that are invariant inside blocks BBS. */
-static void
-blocks_invariant_registers (basic_block *bbs, int nbbs, regset regs)
-{
- rtx insn;
- int i;
-
- for (i = 0; i < max_reg_num (); i++)
- SET_REGNO_REG_SET (regs, i);
- for (i = 0; i < nbbs; i++)
- for (insn = BB_HEAD (bbs[i]);
- insn != NEXT_INSN (BB_END (bbs[i]));
- insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- note_stores (PATTERN (insn),
- (void (*) (rtx, rtx, void *)) unmark_altered,
- regs);
-}
-
-/* Unmarks modified registers; helper to blocks_single_set_registers. */
-struct unmark_altered_insn_data
-{
- rtx *regs;
- rtx insn;
-};
-
-static void
-unmark_altered_insn (rtx what, rtx by ATTRIBUTE_UNUSED,
- struct unmark_altered_insn_data *data)
-{
- int rn;
+ LOOPS is the loop tree. */
- if (GET_CODE (what) == SUBREG)
- what = SUBREG_REG (what);
- if (!REG_P (what))
- return;
- rn = REGNO (what);
- if (data->regs[rn] == data->insn)
- return;
- data->regs[rn] = NULL;
-}
+#define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun))
+#define BB_REPR(BB) ((BB)->index + 1)
-/* Marks registers that have just single simple set in BBS; the relevant
- insn is returned in REGS. */
-static void
-blocks_single_set_registers (basic_block *bbs, int nbbs, rtx *regs)
+bool
+mark_irreducible_loops (void)
{
- rtx insn;
+ basic_block act;
+ struct graph_edge *ge;
+ edge e;
+ edge_iterator ei;
+ int src, dest;
+ unsigned depth;
+ struct graph *g;
+ int num = number_of_loops (cfun);
+ class loop *cloop;
+ bool irred_loop_found = false;
int i;
- struct unmark_altered_insn_data data;
-
- for (i = 0; i < max_reg_num (); i++)
- regs[i] = NULL;
-
- for (i = 0; i < nbbs; i++)
- for (insn = BB_HEAD (bbs[i]);
- insn != NEXT_INSN (BB_END (bbs[i]));
- insn = NEXT_INSN (insn))
- {
- rtx set = single_set (insn);
- if (!set)
- continue;
- if (!REG_P (SET_DEST (set)))
- continue;
- regs[REGNO (SET_DEST (set))] = insn;
- }
-
- data.regs = regs;
- for (i = 0; i < nbbs; i++)
- for (insn = BB_HEAD (bbs[i]);
- insn != NEXT_INSN (BB_END (bbs[i]));
- insn = NEXT_INSN (insn))
- {
- if (!INSN_P (insn))
- continue;
- data.insn = insn;
- note_stores (PATTERN (insn),
- (void (*) (rtx, rtx, void *)) unmark_altered_insn,
- &data);
- }
-}
-
-/* Helper for invariant_rtx_wrto_regs_p. */
-static int
-invariant_rtx_wrto_regs_p_helper (rtx *expr, regset invariant_regs)
-{
- switch (GET_CODE (*expr))
- {
- case CC0:
- case PC:
- case UNSPEC_VOLATILE:
- return 1;
-
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST:
- case SYMBOL_REF:
- case LABEL_REF:
- return 0;
-
- case ASM_OPERANDS:
- return MEM_VOLATILE_P (*expr);
-
- case MEM:
- /* If the memory is not constant, assume it is modified. If it is
- constant, we still have to check the address. */
- return !RTX_UNCHANGING_P (*expr);
-
- case REG:
- return !REGNO_REG_SET_P (invariant_regs, REGNO (*expr));
-
- default:
- return 0;
- }
-}
-
-/* Checks that EXPR is invariant provided that INVARIANT_REGS are invariant. */
-static bool
-invariant_rtx_wrto_regs_p (rtx expr, regset invariant_regs)
-{
- return !for_each_rtx (&expr, (rtx_function) invariant_rtx_wrto_regs_p_helper,
- invariant_regs);
-}
-
-/* Checks whether CONDITION is a simple comparison in that one of operands
- is register and the other one is invariant in the LOOP. Fills var, lim
- and cond fields in DESC. */
-static bool
-simple_condition_p (struct loop *loop ATTRIBUTE_UNUSED, rtx condition,
- regset invariant_regs, struct loop_desc *desc)
-{
- rtx op0, op1;
-
- /* Check condition. */
- switch (GET_CODE (condition))
- {
- case EQ:
- case NE:
- case LE:
- case LT:
- case GE:
- case GT:
- case GEU:
- case GTU:
- case LEU:
- case LTU:
- break;
- default:
- return false;
- }
-
- /* Of integers or pointers. */
- if (GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_INT
- && GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_PARTIAL_INT)
- return false;
- /* One of operands must be a simple register. */
- op0 = XEXP (condition, 0);
- op1 = XEXP (condition, 1);
+ gcc_assert (current_loops != NULL);
- /* One of operands must be invariant. */
- if (invariant_rtx_wrto_regs_p (op0, invariant_regs))
+ /* Reset the flags. */
+ FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
{
- /* And the other one must be a register. */
- if (!REG_P (op1))
- return false;
- desc->var = op1;
- desc->lim = op0;
-
- desc->cond = swap_condition (GET_CODE (condition));
- if (desc->cond == UNKNOWN)
- return false;
- return true;
+ act->flags &= ~BB_IRREDUCIBLE_LOOP;
+ FOR_EACH_EDGE (e, ei, act->succs)
+ e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
- /* Check the other operand. */
- if (!invariant_rtx_wrto_regs_p (op1, invariant_regs))
- return false;
- if (!REG_P (op0))
- return false;
-
- desc->var = op0;
- desc->lim = op1;
-
- desc->cond = GET_CODE (condition);
-
- return true;
-}
-
-/* Checks whether DESC->var is incremented/decremented exactly once each
- iteration. Fills in DESC->stride and returns block in that DESC->var is
- modified. */
-static basic_block
-simple_increment (struct loop *loop, rtx *simple_increment_regs,
- struct loop_desc *desc)
-{
- rtx mod_insn, mod_insn1, set, set_src, set_add;
- basic_block mod_bb, mod_bb1;
-
- /* Find insn that modifies var. */
- mod_insn = simple_increment_regs[REGNO (desc->var)];
- if (!mod_insn)
- return NULL;
- mod_bb = BLOCK_FOR_INSN (mod_insn);
-
- /* Check that it is executed exactly once each iteration. */
- if (!just_once_each_iteration_p (loop, mod_bb))
- return NULL;
-
- /* mod_insn must be a simple increment/decrement. */
- set = single_set (mod_insn);
- if (!set)
- abort ();
- if (!rtx_equal_p (SET_DEST (set), desc->var))
- abort ();
-
- set_src = find_reg_equal_equiv_note (mod_insn);
- if (!set_src)
- set_src = SET_SRC (set);
-
- /* Check for variables that iterate in narrower mode. */
- if (GET_CODE (set_src) == SIGN_EXTEND
- || GET_CODE (set_src) == ZERO_EXTEND)
- {
- /* If we are sign extending variable that is then compared unsigned
- or vice versa, there is something weird happening. */
- if (desc->cond != EQ
- && desc->cond != NE
- && ((desc->cond == LEU
- || desc->cond == LTU
- || desc->cond == GEU
- || desc->cond == GTU)
- ^ (GET_CODE (set_src) == ZERO_EXTEND)))
- return NULL;
-
- if (GET_CODE (XEXP (set_src, 0)) != SUBREG
- || SUBREG_BYTE (XEXP (set_src, 0)) != 0
- || GET_MODE (SUBREG_REG (XEXP (set_src, 0))) != GET_MODE (desc->var))
- return NULL;
-
- desc->inner_mode = GET_MODE (XEXP (set_src, 0));
- desc->extend = GET_CODE (set_src);
- set_src = SUBREG_REG (XEXP (set_src, 0));
-
- if (GET_CODE (set_src) != REG)
- return NULL;
-
- /* Find where the reg is set. */
- mod_insn1 = simple_increment_regs[REGNO (set_src)];
- if (!mod_insn1)
- return NULL;
-
- mod_bb1 = BLOCK_FOR_INSN (mod_insn1);
- if (!dominated_by_p (CDI_DOMINATORS, mod_bb, mod_bb1))
- return NULL;
- if (mod_bb1 == mod_bb)
- {
- for (;
- mod_insn != PREV_INSN (BB_HEAD (mod_bb));
- mod_insn = PREV_INSN (mod_insn))
- if (mod_insn == mod_insn1)
- break;
-
- if (mod_insn == PREV_INSN (BB_HEAD (mod_bb)))
- return NULL;
- }
-
- /* Replace the source with the possible place of increment. */
- set = single_set (mod_insn1);
- if (!set)
- abort ();
- if (!rtx_equal_p (SET_DEST (set), set_src))
- abort ();
-
- set_src = find_reg_equal_equiv_note (mod_insn1);
- if (!set_src)
- set_src = SET_SRC (set);
- }
- else
- {
- desc->inner_mode = GET_MODE (desc->var);
- desc->extend = NIL;
- }
+ /* Create the edge lists. */
+ g = new_graph (last_basic_block_for_fn (cfun) + num);
- if (GET_CODE (set_src) != PLUS)
- return NULL;
- if (!rtx_equal_p (XEXP (set_src, 0), desc->var))
- return NULL;
+ FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
+ FOR_EACH_EDGE (e, ei, act->succs)
+ {
+ /* Ignore edges to exit. */
+ if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
+ continue;
- /* Set desc->stride. */
- set_add = XEXP (set_src, 1);
- if (CONSTANT_P (set_add))
- desc->stride = set_add;
- else
- return NULL;
+ src = BB_REPR (act);
+ dest = BB_REPR (e->dest);
- return mod_bb;
-}
+ /* Ignore latch edges. */
+ if (e->dest->loop_father->header == e->dest
+ && e->dest->loop_father->latch == act)
+ continue;
-/* Tries to find initial value of VAR in INSN. This value must be invariant
- wrto INVARIANT_REGS. If SET_INSN is not NULL, insn in that var is set is
- placed here. INNER_MODE is mode in that induction variable VAR iterates. */
-static rtx
-variable_initial_value (rtx insn, regset invariant_regs,
- rtx var, rtx *set_insn, enum machine_mode inner_mode)
-{
- basic_block bb;
- rtx set;
- rtx ret = NULL;
+ /* Edges inside a single loop should be left where they are. Edges
+ to subloop headers should lead to representative of the subloop,
+ but from the same place.
- /* Go back through cfg. */
- bb = BLOCK_FOR_INSN (insn);
- while (1)
- {
- for (; insn != BB_HEAD (bb); insn = PREV_INSN (insn))
- {
- if (INSN_P (insn))
- note_stores (PATTERN (insn),
- (void (*) (rtx, rtx, void *)) unmark_altered,
- invariant_regs);
- if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
- break;
- }
+ Edges exiting loops should lead from representative
+ of the son of nearest common ancestor of the loops in that
+ act lays. */
- if (insn != BB_HEAD (bb))
- {
- /* We found place where var is set. */
- rtx set_dest;
- rtx val;
- rtx note;
-
- set = single_set (insn);
- if (!set)
- return NULL;
- set_dest = SET_DEST (set);
- if (!rtx_equal_p (set_dest, var))
- return NULL;
-
- note = find_reg_equal_equiv_note (insn);
- if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
- val = XEXP (note, 0);
- else
- val = SET_SRC (set);
-
- /* If we know that the initial value is indeed in range of
- the inner mode, record the fact even in case the value itself
- is useless. */
- if ((GET_CODE (val) == SIGN_EXTEND
- || GET_CODE (val) == ZERO_EXTEND)
- && GET_MODE (XEXP (val, 0)) == inner_mode)
- ret = gen_rtx_fmt_e (GET_CODE (val),
- GET_MODE (var),
- gen_rtx_fmt_ei (SUBREG,
- inner_mode,
- var, 0));
-
- if (!invariant_rtx_wrto_regs_p (val, invariant_regs))
- return ret;
-
- if (set_insn)
- *set_insn = insn;
- return val;
- }
+ if (e->dest->loop_father->header == e->dest)
+ dest = LOOP_REPR (e->dest->loop_father);
+ if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
+ {
+ depth = 1 + loop_depth (find_common_loop (act->loop_father,
+ e->dest->loop_father));
+ if (depth == loop_depth (act->loop_father))
+ cloop = act->loop_father;
+ else
+ cloop = (*act->loop_father->superloops)[depth];
- if (bb->pred->pred_next || bb->pred->src == ENTRY_BLOCK_PTR)
- return NULL;
+ src = LOOP_REPR (cloop);
+ }
- bb = bb->pred->src;
- insn = BB_END (bb);
- }
+ add_edge (g, src, dest)->data = e;
+ }
- return NULL;
-}
+ /* Find the strongly connected components. */
+ graphds_scc (g, NULL);
-/* Returns list of definitions of initial value of VAR at edge E. INNER_MODE
- is mode in that induction variable VAR really iterates. */
-static rtx
-variable_initial_values (edge e, rtx var, enum machine_mode inner_mode)
-{
- rtx set_insn, list;
- regset invariant_regs;
- regset_head invariant_regs_head;
- int i;
+ /* Mark the irreducible loops. */
+ for (i = 0; i < g->n_vertices; i++)
+ for (ge = g->vertices[i].succ; ge; ge = ge->succ_next)
+ {
+ edge real = (edge) ge->data;
+ /* edge E in graph G is irreducible if it connects two vertices in the
+ same scc. */
- invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
- for (i = 0; i < max_reg_num (); i++)
- SET_REGNO_REG_SET (invariant_regs, i);
+ /* All edges should lead from a component with higher number to the
+ one with lower one. */
+ gcc_assert (g->vertices[ge->src].component >= g->vertices[ge->dest].component);
- list = alloc_EXPR_LIST (0, copy_rtx (var), NULL);
+ if (g->vertices[ge->src].component != g->vertices[ge->dest].component)
+ continue;
- if (e->src == ENTRY_BLOCK_PTR)
- return list;
+ real->flags |= EDGE_IRREDUCIBLE_LOOP;
+ irred_loop_found = true;
+ if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
+ real->src->flags |= BB_IRREDUCIBLE_LOOP;
+ }
- set_insn = BB_END (e->src);
- while (REG_P (var)
- && (var = variable_initial_value (set_insn, invariant_regs, var,
- &set_insn, inner_mode)))
- list = alloc_EXPR_LIST (0, copy_rtx (var), list);
+ free_graph (g);
- FREE_REG_SET (invariant_regs);
- return list;
+ loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
+ return irred_loop_found;
}
-/* Counts constant number of iterations of the loop described by DESC;
- returns false if impossible. */
-static bool
-constant_iterations (struct loop_desc *desc, unsigned HOST_WIDE_INT *niter,
- bool *may_be_zero)
+/* Counts number of insns inside LOOP. */
+int
+num_loop_insns (const class loop *loop)
{
- rtx test, expr;
- rtx ainit, alim;
+ basic_block *bbs, bb;
+ unsigned i, ninsns = 0;
+ rtx_insn *insn;
- test = test_for_iteration (desc, 0);
- if (test == const0_rtx)
+ bbs = get_loop_body (loop);
+ for (i = 0; i < loop->num_nodes; i++)
{
- *niter = 0;
- *may_be_zero = false;
- return true;
+ bb = bbs[i];
+ FOR_BB_INSNS (bb, insn)
+ if (NONDEBUG_INSN_P (insn))
+ ninsns++;
}
+ free (bbs);
- *may_be_zero = (test != const_true_rtx);
-
- /* It would make a little sense to check every with every when we
- know that all but the first alternative are simply registers. */
- for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
- {
- alim = XEXP (desc->lim_alts, 0);
- if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim)))
- continue;
- if (GET_CODE (expr) == CONST_INT)
- {
- *niter = INTVAL (expr);
- return true;
- }
- }
- for (alim = XEXP (desc->lim_alts, 1); alim; alim = XEXP (alim, 1))
- {
- ainit = XEXP (desc->var_alts, 0);
- if (!(expr = count_loop_iterations (desc, ainit, XEXP (alim, 0))))
- continue;
- if (GET_CODE (expr) == CONST_INT)
- {
- *niter = INTVAL (expr);
- return true;
- }
- }
+ if (!ninsns)
+ ninsns = 1; /* To avoid division by zero. */
- return false;
+ return ninsns;
}
-/* Attempts to determine a number of iterations of a "strange" loop.
- Its induction variable starts with value INIT, is compared by COND
- with LIM. If POSTINCR, it is incremented after the test. It is incremented
- by STRIDE each iteration, has mode MODE but iterates in INNER_MODE.
-
- By "strange" we mean loops where induction variable increases in the wrong
- direction wrto comparison, i.e. for (i = 6; i > 5; i++). */
-static rtx
-count_strange_loop_iterations (rtx init, rtx lim, enum rtx_code cond,
- int postincr, rtx stride, enum machine_mode mode,
- enum machine_mode inner_mode)
+/* Counts number of insns executed on average per iteration LOOP. */
+int
+average_num_loop_insns (const class loop *loop)
{
- rtx rqmt, n_to_wrap, before_wrap, after_wrap;
- rtx mode_min, mode_max;
- int size;
-
- /* This could be handled, but it is not important enough to lose time with
- it just now. */
- if (mode != inner_mode)
- return NULL_RTX;
-
- if (!postincr)
- init = simplify_gen_binary (PLUS, mode, init, stride);
-
- /* If we are able to prove that we don't pass the first test, we are
- done. */
- rqmt = simplify_relational_operation (cond, mode, init, lim);
- if (rqmt == const0_rtx)
- return const0_rtx;
-
- /* And if we don't know we pass it, the things are too complicated for us. */
- if (rqmt != const_true_rtx)
- return NULL_RTX;
-
- switch (cond)
- {
- case GE:
- case GT:
- case LE:
- case LT:
- size = GET_MODE_BITSIZE (mode);
- mode_min = GEN_INT (-((unsigned HOST_WIDEST_INT) 1 << (size - 1)));
- mode_max = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1)) - 1);
-
- break;
-
- case GEU:
- case GTU:
- case LEU:
- case LTU:
- case EQ:
- mode_min = const0_rtx;
- mode_max = simplify_gen_binary (MINUS, mode, const0_rtx, const1_rtx);
- break;
-
- default:
- abort ();
- }
+ basic_block *bbs, bb;
+ unsigned i, binsns;
+ sreal ninsns;
+ rtx_insn *insn;
- switch (cond)
+ ninsns = 0;
+ bbs = get_loop_body (loop);
+ for (i = 0; i < loop->num_nodes; i++)
{
- case EQ:
- /* This iterates once, as init == lim. */
- return const1_rtx;
-
- /* The behavior is undefined in signed cases. Never mind, we still
- try to behave sanely. */
- case GE:
- case GT:
- case GEU:
- case GTU:
- if (INTVAL (stride) <= 0)
- abort ();
- n_to_wrap = simplify_gen_binary (MINUS, mode, mode_max, copy_rtx (init));
- n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
- before_wrap = simplify_gen_binary (MULT, mode,
- copy_rtx (n_to_wrap), stride);
- before_wrap = simplify_gen_binary (PLUS, mode,
- before_wrap, copy_rtx (init));
- after_wrap = simplify_gen_binary (PLUS, mode,
- before_wrap, stride);
- if (GET_CODE (after_wrap) != CONST_INT)
- {
- after_wrap = simplify_gen_binary (PLUS, mode, mode_min, stride);
- after_wrap = simplify_gen_binary (MINUS, mode, after_wrap, const1_rtx);
- }
- break;
-
- case LE:
- case LT:
- case LEU:
- case LTU:
- if (INTVAL (stride) >= 0)
- abort ();
- stride = simplify_gen_unary (NEG, mode, stride, mode);
- n_to_wrap = simplify_gen_binary (MINUS, mode, copy_rtx (init), mode_min);
- n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
- before_wrap = simplify_gen_binary (MULT, mode,
- copy_rtx (n_to_wrap), stride);
- before_wrap = simplify_gen_binary (MINUS, mode,
- copy_rtx (init), before_wrap);
- after_wrap = simplify_gen_binary (MINUS, mode,
- before_wrap, stride);
- if (GET_CODE (after_wrap) != CONST_INT)
- {
- after_wrap = simplify_gen_binary (MINUS, mode, mode_max, stride);
- after_wrap = simplify_gen_binary (PLUS, mode, after_wrap, const1_rtx);
- }
- break;
- default:
- abort ();
- }
-
- /* If this is const_true_rtx and we did not take a conservative approximation
- of after_wrap above, we might iterate the calculation (but of course we
- would have to take care about infinite cases). Ignore this for now. */
- rqmt = simplify_relational_operation (cond, mode, after_wrap, lim);
- if (rqmt != const0_rtx)
- return NULL_RTX;
-
- return simplify_gen_binary (PLUS, mode, n_to_wrap, const1_rtx);
-}
-
-/* Checks whether value of EXPR fits into range of MODE. */
-static bool
-fits_in_mode_p (enum machine_mode mode, rtx expr)
-{
- unsigned HOST_WIDEST_INT val;
- int n_bits = 0;
+ bb = bbs[i];
- if (GET_CODE (expr) == CONST_INT)
- {
- for (val = INTVAL (expr); val; val >>= 1)
- n_bits++;
+ binsns = 0;
+ FOR_BB_INSNS (bb, insn)
+ if (NONDEBUG_INSN_P (insn))
+ binsns++;
- return n_bits <= GET_MODE_BITSIZE (mode);
+ ninsns += (sreal)binsns * bb->count.to_sreal_scale (loop->header->count);
+ /* Avoid overflows. */
+ if (ninsns > 1000000)
+ return 100000;
}
+ free (bbs);
- if (GET_CODE (expr) == SIGN_EXTEND
- || GET_CODE (expr) == ZERO_EXTEND)
- return GET_MODE (XEXP (expr, 0)) == mode;
+ int64_t ret = ninsns.to_int ();
+ if (!ret)
+ ret = 1; /* To avoid division by zero. */
- return false;
+ return ret;
}
-/* Return RTX expression representing number of iterations of loop as bounded
- by test described by DESC (in the case loop really has multiple exit
- edges, fewer iterations may happen in the practice).
-
- Return NULL if it is unknown. Additionally the value may be invalid for
- paradoxical loop (lets define paradoxical loops as loops whose test is
- failing at -1th iteration, for instance "for (i=5;i<1;i++);").
+/* Returns expected number of iterations of LOOP, according to
+ measured or guessed profile.
- These cases needs to be either cared by copying the loop test in the front
- of loop or keeping the test in first iteration of loop.
+ This functions attempts to return "sane" value even if profile
+ information is not good enough to derive osmething.
+ If BY_PROFILE_ONLY is set, this logic is bypassed and function
+ return -1 in those scenarios. */
- When INIT/LIM are set, they are used instead of var/lim of DESC. */
-rtx
-count_loop_iterations (struct loop_desc *desc, rtx init, rtx lim)
+gcov_type
+expected_loop_iterations_unbounded (const class loop *loop,
+ bool *read_profile_p,
+ bool by_profile_only)
{
- enum rtx_code cond = desc->cond;
- rtx stride = desc->stride;
- rtx mod, exp, ainit, bound;
- rtx overflow_check, mx, mxp;
- enum machine_mode mode = GET_MODE (desc->var);
- unsigned HOST_WIDEST_INT s, size, d;
-
- /* Give up on floating point modes and friends. It can be possible to do
- the job for constant loop bounds, but it is probably not worthwhile. */
- if (!INTEGRAL_MODE_P (mode))
- return NULL;
-
- init = copy_rtx (init ? init : desc->var);
- lim = copy_rtx (lim ? lim : desc->lim);
-
- /* Ensure that we always handle the condition to stay inside loop. */
- if (desc->neg)
- cond = reverse_condition (cond);
-
- if (desc->inner_mode != mode)
- {
- /* We have a case when the variable in fact iterates in the narrower
- mode. This has following consequences:
-
- For induction variable itself, if !desc->postincr, it does not mean
- anything too special, since we know the variable is already in range
- of the inner mode when we compare it (so it is just needed to shorten
- it into the mode before calculations are done, so that we don't risk
- wrong results). More complicated case is when desc->postincr; then
- the first two iterations are special (the first one because the value
- may be out of range, the second one because after shortening it to the
- range it may have absolutely any value), and we do not handle this in
- unrolling. So if we aren't able to prove that the initial value is in
- the range, we fail in this case.
-
- Step is just moduled to fit into inner mode.
-
- If lim is out of range, then either the loop is infinite (and then
- we may unroll however we like to), or exits in the first iteration
- (this is also ok, since we handle it specially for this case anyway).
- So we may safely assume that it fits into the inner mode. */
-
- for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
- if (fits_in_mode_p (desc->inner_mode, XEXP (ainit, 0)))
- break;
-
- if (!ainit)
- {
- if (desc->postincr)
- return NULL_RTX;
-
- init = simplify_gen_unary (desc->extend,
- mode,
- simplify_gen_subreg (desc->inner_mode,
- init,
- mode,
- 0),
- desc->inner_mode);
- }
-
- stride = simplify_gen_subreg (desc->inner_mode, stride, mode, 0);
- if (stride == const0_rtx)
- return NULL_RTX;
- }
+ edge e;
+ edge_iterator ei;
+ gcov_type expected = -1;
+
+ if (read_profile_p)
+ *read_profile_p = false;
- /* Prepare condition to verify that we do not risk overflow. */
- if (stride == const1_rtx
- || stride == constm1_rtx
- || cond == NE
- || cond == EQ)
+ /* If we have no profile at all, use AVG_LOOP_NITER. */
+ if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
{
- /* Overflow at NE conditions does not occur. EQ condition
- is weird and is handled in count_strange_loop_iterations.
- If stride is 1, overflow may occur only for <= and >= conditions,
- and then they are infinite, so it does not bother us. */
- overflow_check = const0_rtx;
+ if (by_profile_only)
+ return -1;
+ expected = PARAM_VALUE (PARAM_AVG_LOOP_NITER);
}
- else
+ else if (loop->latch && (loop->latch->count.initialized_p ()
+ || loop->header->count.initialized_p ()))
{
- if (cond == LT || cond == LTU)
- mx = simplify_gen_binary (MINUS, mode, lim, const1_rtx);
- else if (cond == GT || cond == GTU)
- mx = simplify_gen_binary (PLUS, mode, lim, const1_rtx);
- else
- mx = lim;
- if (mode != desc->inner_mode)
- mxp = simplify_gen_subreg (desc->inner_mode, mx, mode, 0);
- else
- mxp = mx;
- mxp = simplify_gen_binary (PLUS, desc->inner_mode, mxp, stride);
- if (mode != desc->inner_mode)
- mxp = simplify_gen_unary (desc->extend, mode, mxp, desc->inner_mode);
- overflow_check = simplify_gen_relational (cond, SImode, mode, mx, mxp);
- }
-
- /* Compute absolute value of the difference of initial and final value. */
- if (INTVAL (stride) > 0)
- {
- /* Handle strange tests specially. */
- if (cond == EQ || cond == GE || cond == GT || cond == GEU
- || cond == GTU)
- return count_strange_loop_iterations (init, lim, cond, desc->postincr,
- stride, mode, desc->inner_mode);
- exp = simplify_gen_binary (MINUS, mode, lim, init);
- }
- else
- {
- if (cond == EQ || cond == LE || cond == LT || cond == LEU
- || cond == LTU)
- return count_strange_loop_iterations (init, lim, cond, desc->postincr,
- stride, mode, desc->inner_mode);
- exp = simplify_gen_binary (MINUS, mode, init, lim);
- stride = simplify_gen_unary (NEG, mode, stride, mode);
- }
-
- /* If there is a risk of overflow (i.e. when we increment value satisfying
- a condition, we may again obtain a value satisfying the condition),
- fail. */
- if (overflow_check != const0_rtx)
- return NULL_RTX;
+ profile_count count_in = profile_count::zero (),
+ count_latch = profile_count::zero ();
- /* Normalize difference so the value is always first examined
- and later incremented. */
- if (!desc->postincr)
- exp = simplify_gen_binary (MINUS, mode, exp, stride);
+ FOR_EACH_EDGE (e, ei, loop->header->preds)
+ if (e->src == loop->latch)
+ count_latch = e->count ();
+ else
+ count_in += e->count ();
- /* Determine delta caused by exit condition. */
- switch (cond)
- {
- case NE:
- /* NE tests are easy to handle, because we just perform simple
- arithmetics modulo power of 2. Let's use the fact to compute the
- number of iterations exactly. We are now in situation when we want to
- solve an equation stride * i = c (mod size of inner_mode).
- Let nsd (stride, size of mode) = d. If d does not divide c, the
- loop is infinite. Otherwise, the number of iterations is
- (inverse(s/d) * (c/d)) mod (size of mode/d). */
- size = GET_MODE_BITSIZE (desc->inner_mode);
- s = INTVAL (stride);
- d = 1;
- while (s % 2 != 1)
+ if (!count_latch.initialized_p ())
{
- s /= 2;
- d *= 2;
- size--;
+ if (by_profile_only)
+ return -1;
+ expected = PARAM_VALUE (PARAM_AVG_LOOP_NITER);
}
- bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
- exp = simplify_gen_binary (UDIV, mode, exp, GEN_INT (d));
- exp = simplify_gen_binary (MULT, mode,
- exp, GEN_INT (inverse (s, size)));
- exp = simplify_gen_binary (AND, mode, exp, bound);
- break;
-
- case LT:
- case GT:
- case LTU:
- case GTU:
- break;
- case LE:
- case GE:
- case LEU:
- case GEU:
- exp = simplify_gen_binary (PLUS, mode, exp, const1_rtx);
- break;
- default:
- abort ();
- }
-
- if (cond != NE && stride != const1_rtx)
- {
- /* Number of iterations is now (EXP + STRIDE - 1 / STRIDE),
- but we need to take care for overflows. */
-
- mod = simplify_gen_binary (UMOD, mode, exp, stride);
-
- /* This is dirty trick. When we can't compute number of iterations
- to be constant, we simply ignore the possible overflow, as
- runtime unroller always use power of 2 amounts and does not
- care about possible lost bits. */
-
- if (GET_CODE (mod) != CONST_INT)
+ else if (!count_in.nonzero_p ())
{
- rtx stridem1 = simplify_gen_binary (PLUS, mode, stride, constm1_rtx);
- exp = simplify_gen_binary (PLUS, mode, exp, stridem1);
- exp = simplify_gen_binary (UDIV, mode, exp, stride);
+ if (by_profile_only)
+ return -1;
+ expected = count_latch.to_gcov_type () * 2;
}
else
{
- exp = simplify_gen_binary (UDIV, mode, exp, stride);
- if (mod != const0_rtx)
- exp = simplify_gen_binary (PLUS, mode, exp, const1_rtx);
+ expected = (count_latch.to_gcov_type () + count_in.to_gcov_type ()
+ - 1) / count_in.to_gcov_type ();
+ if (read_profile_p
+ && count_latch.reliable_p () && count_in.reliable_p ())
+ *read_profile_p = true;
}
}
-
- if (dump_file)
+ else
{
- fprintf (dump_file, "; Number of iterations: ");
- print_simple_rtl (dump_file, exp);
- fprintf (dump_file, "\n");
+ if (by_profile_only)
+ return -1;
+ expected = PARAM_VALUE (PARAM_AVG_LOOP_NITER);
}
- return exp;
-}
-
-/* Return simplified RTX expression representing the value of test
- described of DESC at given iteration of loop. */
-
-static rtx
-test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT iter)
-{
- enum rtx_code cond = desc->cond;
- rtx exp = XEXP (desc->var_alts, 0);
- rtx addval;
-
- /* Give up on floating point modes and friends. It can be possible to do
- the job for constant loop bounds, but it is probably not worthwhile. */
- if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
- return NULL;
-
- /* Ensure that we always handle the condition to stay inside loop. */
- if (desc->neg)
- cond = reverse_condition (cond);
-
- /* Compute the value of induction variable. */
- addval = simplify_gen_binary (MULT, GET_MODE (desc->var),
- desc->stride,
- gen_int_mode (desc->postincr
- ? iter : iter + 1,
- GET_MODE (desc->var)));
- exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), exp, addval);
- /* Test at given condition. */
- exp = simplify_gen_relational (cond, SImode,
- GET_MODE (desc->var), exp, desc->lim);
-
- if (dump_file)
+ if (!by_profile_only)
{
- fprintf (dump_file, "; Conditional to continue loop at "
- HOST_WIDE_INT_PRINT_UNSIGNED "th iteration: ", iter);
- print_simple_rtl (dump_file, exp);
- fprintf (dump_file, "\n");
+ HOST_WIDE_INT max = get_max_loop_iterations_int (loop);
+ if (max != -1 && max < expected)
+ return max;
}
- return exp;
+
+ return expected;
}
+/* Returns expected number of LOOP iterations. The returned value is bounded
+ by REG_BR_PROB_BASE. */
-/* Tests whether exit at EXIT_EDGE from LOOP is simple. Returns simple loop
- description joined to it in in DESC. INVARIANT_REGS and SINGLE_SET_REGS
- are results of blocks_{invariant,single_set}_regs over BODY. */
-static bool
-simple_loop_exit_p (struct loop *loop, edge exit_edge,
- regset invariant_regs, rtx *single_set_regs,
- struct loop_desc *desc)
-{
- basic_block mod_bb, exit_bb;
- int fallthru_out;
- rtx condition;
- edge ei, e;
-
- exit_bb = exit_edge->src;
-
- fallthru_out = (exit_edge->flags & EDGE_FALLTHRU);
-
- if (!exit_bb)
- return false;
-
- /* It must be tested (at least) once during any iteration. */
- if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
- return false;
-
- /* It must end in a simple conditional jump. */
- if (!any_condjump_p (BB_END (exit_bb)))
- return false;
-
- ei = exit_bb->succ;
- if (ei == exit_edge)
- ei = ei->succ_next;
-
- desc->out_edge = exit_edge;
- desc->in_edge = ei;
-
- /* Condition must be a simple comparison in that one of operands
- is register and the other one is invariant. */
- if (!(condition = get_condition (BB_END (exit_bb), NULL, false)))
- return false;
-
- if (!simple_condition_p (loop, condition, invariant_regs, desc))
- return false;
-
- /* Var must be simply incremented or decremented in exactly one insn that
- is executed just once every iteration. */
- if (!(mod_bb = simple_increment (loop, single_set_regs, desc)))
- return false;
-
- /* OK, it is simple loop. Now just fill in remaining info. */
- desc->postincr = !dominated_by_p (CDI_DOMINATORS, exit_bb, mod_bb);
- desc->neg = !fallthru_out;
-
- /* Find initial value of var and alternative values for lim. */
- e = loop_preheader_edge (loop);
- desc->var_alts = variable_initial_values (e, desc->var, desc->inner_mode);
- desc->lim_alts = variable_initial_values (e, desc->lim, desc->inner_mode);
-
- /* Number of iterations. */
- desc->const_iter =
- constant_iterations (desc, &desc->niter, &desc->may_be_zero);
- if (!desc->const_iter && !count_loop_iterations (desc, NULL, NULL))
- return false;
- return true;
-}
-
-/* Tests whether LOOP is simple for loop. Returns simple loop description
- in DESC. */
-bool
-simple_loop_p (struct loop *loop, struct loop_desc *desc)
+unsigned
+expected_loop_iterations (class loop *loop)
{
- unsigned i;
- basic_block *body;
- edge e;
- struct loop_desc act;
- bool any = false;
- regset invariant_regs;
- regset_head invariant_regs_head;
- rtx *single_set_regs;
- int n_branches;
-
- body = get_loop_body (loop);
-
- invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
- single_set_regs = xmalloc (max_reg_num () * sizeof (rtx));
-
- blocks_invariant_registers (body, loop->num_nodes, invariant_regs);
- blocks_single_set_registers (body, loop->num_nodes, single_set_regs);
-
- n_branches = 0;
- for (i = 0; i < loop->num_nodes; i++)
- {
- for (e = body[i]->succ; e; e = e->succ_next)
- if (!flow_bb_inside_loop_p (loop, e->dest)
- && simple_loop_exit_p (loop, e,
- invariant_regs, single_set_regs, &act))
- {
- /* Prefer constant iterations; the less the better. */
- if (!any)
- any = true;
- else if (!act.const_iter
- || (desc->const_iter && act.niter >= desc->niter))
- continue;
- *desc = act;
- }
-
- if (body[i]->succ && body[i]->succ->succ_next)
- n_branches++;
- }
- desc->n_branches = n_branches;
-
- if (dump_file && any)
- {
- fprintf (dump_file, "; Simple loop %i\n", loop->num);
- if (desc->postincr)
- fprintf (dump_file,
- "; does postincrement after loop exit condition\n");
-
- fprintf (dump_file, "; Induction variable:");
- print_simple_rtl (dump_file, desc->var);
- fputc ('\n', dump_file);
-
- fprintf (dump_file, "; Initial values:");
- print_simple_rtl (dump_file, desc->var_alts);
- fputc ('\n', dump_file);
-
- fprintf (dump_file, "; Stride:");
- print_simple_rtl (dump_file, desc->stride);
- fputc ('\n', dump_file);
-
- fprintf (dump_file, "; Compared with:");
- print_simple_rtl (dump_file, desc->lim);
- fputc ('\n', dump_file);
-
- fprintf (dump_file, "; Alternative values:");
- print_simple_rtl (dump_file, desc->lim_alts);
- fputc ('\n', dump_file);
-
- fprintf (dump_file, "; Exit condition:");
- if (desc->neg)
- fprintf (dump_file, "(negated)");
- fprintf (dump_file, "%s\n", GET_RTX_NAME (desc->cond));
-
- fprintf (dump_file, "; Number of branches:");
- fprintf (dump_file, "%d\n", desc->n_branches);
-
- fputc ('\n', dump_file);
- }
-
- free (body);
- FREE_REG_SET (invariant_regs);
- free (single_set_regs);
- return any;
+ gcov_type expected = expected_loop_iterations_unbounded (loop);
+ return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
}
-/* Structure representing edge of a graph. */
-
-struct edge
-{
- int src, dest; /* Source and destination. */
- struct edge *pred_next, *succ_next;
- /* Next edge in predecessor and successor lists. */
- void *data; /* Data attached to the edge. */
-};
-
-/* Structure representing vertex of a graph. */
+/* Returns the maximum level of nesting of subloops of LOOP. */
-struct vertex
-{
- struct edge *pred, *succ;
- /* Lists of predecessors and successors. */
- int component; /* Number of dfs restarts before reaching the
- vertex. */
- int post; /* Postorder number. */
-};
-
-/* Structure representing a graph. */
-
-struct graph
+unsigned
+get_loop_level (const class loop *loop)
{
- int n_vertices; /* Number of vertices. */
- struct vertex *vertices;
- /* The vertices. */
-};
+ const class loop *ploop;
+ unsigned mx = 0, l;
-/* Dumps graph G into F. */
-
-extern void dump_graph (FILE *, struct graph *);
-void dump_graph (FILE *f, struct graph *g)
-{
- int i;
- struct edge *e;
-
- for (i = 0; i < g->n_vertices; i++)
+ for (ploop = loop->inner; ploop; ploop = ploop->next)
{
- if (!g->vertices[i].pred
- && !g->vertices[i].succ)
- continue;
-
- fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
- for (e = g->vertices[i].pred; e; e = e->pred_next)
- fprintf (f, " %d", e->src);
- fprintf (f, "\n");
-
- fprintf (f, "\t->");
- for (e = g->vertices[i].succ; e; e = e->succ_next)
- fprintf (f, " %d", e->dest);
- fprintf (f, "\n");
+ l = get_loop_level (ploop);
+ if (l >= mx)
+ mx = l + 1;
}
+ return mx;
}
-/* Creates a new graph with N_VERTICES vertices. */
+/* Initialize the constants for computing set costs. */
-static struct graph *
-new_graph (int n_vertices)
-{
- struct graph *g = xmalloc (sizeof (struct graph));
+void
+init_set_costs (void)
+{
+ int speed;
+ rtx_insn *seq;
+ rtx reg1 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 1);
+ rtx reg2 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 2);
+ rtx addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 3);
+ rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
+ unsigned i;
- g->n_vertices = n_vertices;
- g->vertices = xcalloc (n_vertices, sizeof (struct vertex));
+ target_avail_regs = 0;
+ target_clobbered_regs = 0;
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
+ && !fixed_regs[i])
+ {
+ target_avail_regs++;
+ /* ??? This is only a rough heuristic. It doesn't cope well
+ with alternative ABIs, but that's an optimization rather than
+ correctness issue. */
+ if (default_function_abi.clobbers_full_reg_p (i))
+ target_clobbered_regs++;
+ }
- return g;
+ target_res_regs = 3;
+
+ for (speed = 0; speed < 2; speed++)
+ {
+ crtl->maybe_hot_insn_p = speed;
+ /* Set up the costs for using extra registers:
+
+ 1) If not many free registers remain, we should prefer having an
+ additional move to decreasing the number of available registers.
+ (TARGET_REG_COST).
+ 2) If no registers are available, we need to spill, which may require
+ storing the old value to memory and loading it back
+ (TARGET_SPILL_COST). */
+
+ start_sequence ();
+ emit_move_insn (reg1, reg2);
+ seq = get_insns ();
+ end_sequence ();
+ target_reg_cost [speed] = seq_cost (seq, speed);
+
+ start_sequence ();
+ emit_move_insn (mem, reg1);
+ emit_move_insn (reg2, mem);
+ seq = get_insns ();
+ end_sequence ();
+ target_spill_cost [speed] = seq_cost (seq, speed);
+ }
+ default_rtl_profile ();
}
-/* Adds an edge from F to T to graph G, with DATA attached. */
-
-static void
-add_edge (struct graph *g, int f, int t, void *data)
-{
- struct edge *e = xmalloc (sizeof (struct edge));
-
- e->src = f;
- e->dest = t;
- e->data = data;
+/* Estimates cost of increased register pressure caused by making N_NEW new
+ registers live around the loop. N_OLD is the number of registers live
+ around the loop. If CALL_P is true, also take into account that
+ call-used registers may be clobbered in the loop body, reducing the
+ number of available registers before we spill. */
- e->pred_next = g->vertices[t].pred;
- g->vertices[t].pred = e;
-
- e->succ_next = g->vertices[f].succ;
- g->vertices[f].succ = e;
+unsigned
+estimate_reg_pressure_cost (unsigned n_new, unsigned n_old, bool speed,
+ bool call_p)
+{
+ unsigned cost;
+ unsigned regs_needed = n_new + n_old;
+ unsigned available_regs = target_avail_regs;
+
+ /* If there is a call in the loop body, the call-clobbered registers
+ are not available for loop invariants. */
+ if (call_p)
+ available_regs = available_regs - target_clobbered_regs;
+
+ /* If we have enough registers, we should use them and not restrict
+ the transformations unnecessarily. */
+ if (regs_needed + target_res_regs <= available_regs)
+ return 0;
+
+ if (regs_needed <= available_regs)
+ /* If we are close to running out of registers, try to preserve
+ them. */
+ cost = target_reg_cost [speed] * n_new;
+ else
+ /* If we run out of registers, it is very expensive to add another
+ one. */
+ cost = target_spill_cost [speed] * n_new;
+
+ if (optimize && (flag_ira_region == IRA_REGION_ALL
+ || flag_ira_region == IRA_REGION_MIXED)
+ && number_of_loops (cfun) <= (unsigned) IRA_MAX_LOOPS_NUM)
+ /* IRA regional allocation deals with high register pressure
+ better. So decrease the cost (to do more accurate the cost
+ calculation for IRA, we need to know how many registers lives
+ through the loop transparently). */
+ cost /= 2;
+
+ return cost;
}
-/* Runs dfs search over vertices of G, from NQ vertices in queue QS.
- The vertices in postorder are stored into QT. If FORWARD is false,
- backward dfs is run. */
+/* Sets EDGE_LOOP_EXIT flag for all loop exits. */
-static void
-dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
+void
+mark_loop_exit_edges (void)
{
- int i, tick = 0, v, comp = 0, top;
- struct edge *e;
- struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices);
-
- for (i = 0; i < g->n_vertices; i++)
- {
- g->vertices[i].component = -1;
- g->vertices[i].post = -1;
- }
+ basic_block bb;
+ edge e;
-#define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
-#define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
-#define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
-#define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
+ if (number_of_loops (cfun) <= 1)
+ return;
- for (i = 0; i < nq; i++)
+ FOR_EACH_BB_FN (bb, cfun)
{
- v = qs[i];
- if (g->vertices[v].post != -1)
- continue;
-
- g->vertices[v].component = comp++;
- e = FST_EDGE (v);
- top = 0;
+ edge_iterator ei;
- while (1)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
- while (e && g->vertices[EDGE_DEST (e)].component != -1)
- e = NEXT_EDGE (e);
-
- if (!e)
- {
- if (qt)
- qt[tick] = v;
- g->vertices[v].post = tick++;
-
- if (!top)
- break;
-
- e = stack[--top];
- v = EDGE_SRC (e);
- e = NEXT_EDGE (e);
- continue;
- }
-
- stack[top++] = e;
- v = EDGE_DEST (e);
- e = FST_EDGE (v);
- g->vertices[v].component = comp - 1;
+ if (loop_outer (bb->loop_father)
+ && loop_exit_edge_p (bb->loop_father, e))
+ e->flags |= EDGE_LOOP_EXIT;
+ else
+ e->flags &= ~EDGE_LOOP_EXIT;
}
}
-
- free (stack);
-}
-
-/* Marks the edge E in graph G irreducible if it connects two vertices in the
- same scc. */
-
-static void
-check_irred (struct graph *g, struct edge *e)
-{
- edge real = e->data;
-
- /* All edges should lead from a component with higher number to the
- one with lower one. */
- if (g->vertices[e->src].component < g->vertices[e->dest].component)
- abort ();
-
- if (g->vertices[e->src].component != g->vertices[e->dest].component)
- return;
-
- real->flags |= EDGE_IRREDUCIBLE_LOOP;
- if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
- real->src->flags |= BB_IRREDUCIBLE_LOOP;
-}
-
-/* Runs CALLBACK for all edges in G. */
-
-static void
-for_each_edge (struct graph *g,
- void (callback) (struct graph *, struct edge *))
-{
- struct edge *e;
- int i;
-
- for (i = 0; i < g->n_vertices; i++)
- for (e = g->vertices[i].succ; e; e = e->succ_next)
- callback (g, e);
}
-/* Releases the memory occupied by G. */
-
-static void
-free_graph (struct graph *g)
-{
- struct edge *e, *n;
- int i;
-
- for (i = 0; i < g->n_vertices; i++)
- for (e = g->vertices[i].succ; e; e = n)
- {
- n = e->succ_next;
- free (e);
- }
- free (g->vertices);
- free (g);
-}
-
-/* Marks blocks and edges that are part of non-recognized loops; i.e. we
- throw away all latch edges and mark blocks inside any remaining cycle.
- Everything is a bit complicated due to fact we do not want to do this
- for parts of cycles that only "pass" through some loop -- i.e. for
- each cycle, we want to mark blocks that belong directly to innermost
- loop containing the whole cycle.
-
- LOOPS is the loop tree. */
-
-#define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
-#define BB_REPR(BB) ((BB)->index + 1)
-
-void
-mark_irreducible_loops (struct loops *loops)
-{
- basic_block act;
- edge e;
- int i, src, dest;
- struct graph *g;
- int *queue1 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- int *queue2 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
- int nq, depth;
- struct loop *cloop;
-
- /* Reset the flags. */
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- {
- act->flags &= ~BB_IRREDUCIBLE_LOOP;
- for (e = act->succ; e; e = e->succ_next)
- e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
- }
-
- /* Create the edge lists. */
- g = new_graph (last_basic_block + loops->num);
-
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- for (e = act->succ; e; e = e->succ_next)
- {
- /* Ignore edges to exit. */
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
-
- /* And latch edges. */
- if (e->dest->loop_father->header == e->dest
- && e->dest->loop_father->latch == act)
- continue;
-
- /* Edges inside a single loop should be left where they are. Edges
- to subloop headers should lead to representative of the subloop,
- but from the same place.
-
- Edges exiting loops should lead from representative
- of the son of nearest common ancestor of the loops in that
- act lays. */
-
- src = BB_REPR (act);
- dest = BB_REPR (e->dest);
-
- if (e->dest->loop_father->header == e->dest)
- dest = LOOP_REPR (e->dest->loop_father);
-
- if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
- {
- depth = find_common_loop (act->loop_father,
- e->dest->loop_father)->depth + 1;
- if (depth == act->loop_father->depth)
- cloop = act->loop_father;
- else
- cloop = act->loop_father->pred[depth];
-
- src = LOOP_REPR (cloop);
- }
-
- add_edge (g, src, dest, e);
- }
-
- /* Find the strongly connected components. Use the algorithm of Tarjan --
- first determine the postorder dfs numbering in reversed graph, then
- run the dfs on the original graph in the order given by decreasing
- numbers assigned by the previous pass. */
- nq = 0;
- FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- {
- queue1[nq++] = BB_REPR (act);
- }
- for (i = 1; i < (int) loops->num; i++)
- if (loops->parray[i])
- queue1[nq++] = LOOP_REPR (loops->parray[i]);
- dfs (g, queue1, nq, queue2, false);
- for (i = 0; i < nq; i++)
- queue1[i] = queue2[nq - i - 1];
- dfs (g, queue1, nq, NULL, true);
-
- /* Mark the irreducible loops. */
- for_each_edge (g, check_irred);
-
- free_graph (g);
- free (queue1);
- free (queue2);
-
- loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
-}
+/* Return exit edge if loop has only one exit that is likely
+ to be executed on runtime (i.e. it is not EH or leading
+ to noreturn call. */
-/* Counts number of insns inside LOOP. */
-int
-num_loop_insns (struct loop *loop)
+edge
+single_likely_exit (class loop *loop)
{
- basic_block *bbs, bb;
- unsigned i, ninsns = 0;
- rtx insn;
-
- bbs = get_loop_body (loop);
- for (i = 0; i < loop->num_nodes; i++)
- {
- bb = bbs[i];
- ninsns++;
- for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- ninsns++;
+ edge found = single_exit (loop);
+ vec exits;
+ unsigned i;
+ edge ex;
+
+ if (found)
+ return found;
+ exits = get_loop_exit_edges (loop);
+ FOR_EACH_VEC_ELT (exits, i, ex)
+ {
+ if (probably_never_executed_edge_p (cfun, ex)
+ /* We want to rule out paths to noreturns but not low probabilities
+ resulting from adjustments or combining.
+ FIXME: once we have better quality tracking, make this more
+ robust. */
+ || ex->probability <= profile_probability::very_unlikely ())
+ continue;
+ if (!found)
+ found = ex;
+ else
+ {
+ exits.release ();
+ return NULL;
+ }
}
- free(bbs);
-
- return ninsns;
+ exits.release ();
+ return found;
}
-/* Counts number of insns executed on average per iteration LOOP. */
-int
-average_num_loop_insns (struct loop *loop)
-{
- basic_block *bbs, bb;
- unsigned i, binsns, ninsns, ratio;
- rtx insn;
-
- ninsns = 0;
- bbs = get_loop_body (loop);
- for (i = 0; i < loop->num_nodes; i++)
- {
- bb = bbs[i];
-
- binsns = 1;
- for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- binsns++;
-
- ratio = loop->header->frequency == 0
- ? BB_FREQ_MAX
- : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
- ninsns += binsns * ratio;
- }
- free(bbs);
-
- ninsns /= BB_FREQ_MAX;
- if (!ninsns)
- ninsns = 1; /* To avoid division by zero. */
- return ninsns;
-}
+/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
+ order against direction of edges from latch. Specially, if
+ header != latch, latch is the 1-st block. */
-/* Returns expected number of LOOP iterations.
- Compute upper bound on number of iterations in case they do not fit integer
- to help loop peeling heuristics. Use exact counts if at all possible. */
-unsigned
-expected_loop_iterations (const struct loop *loop)
+vec
+get_loop_hot_path (const class loop *loop)
{
- edge e;
+ basic_block bb = loop->header;
+ vec path = vNULL;
+ bitmap visited = BITMAP_ALLOC (NULL);
- if (loop->header->count)
+ while (true)
{
- gcov_type count_in, count_latch, expected;
+ edge_iterator ei;
+ edge e;
+ edge best = NULL;
- count_in = 0;
- count_latch = 0;
-
- for (e = loop->header->pred; e; e = e->pred_next)
- if (e->src == loop->latch)
- count_latch = e->count;
- else
- count_in += e->count;
-
- if (count_in == 0)
- return 0;
-
- expected = (count_latch + count_in - 1) / count_in;
-
- /* Avoid overflows. */
- return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
- }
- else
- {
- int freq_in, freq_latch;
-
- freq_in = 0;
- freq_latch = 0;
-
- for (e = loop->header->pred; e; e = e->pred_next)
- if (e->src == loop->latch)
- freq_latch = EDGE_FREQUENCY (e);
- else
- freq_in += EDGE_FREQUENCY (e);
-
- if (freq_in == 0)
- return 0;
-
- return (freq_latch + freq_in - 1) / freq_in;
+ path.safe_push (bb);
+ bitmap_set_bit (visited, bb->index);
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if ((!best || e->probability > best->probability)
+ && !loop_exit_edge_p (loop, e)
+ && !bitmap_bit_p (visited, e->dest->index))
+ best = e;
+ if (!best || best->dest == loop->header)
+ break;
+ bb = best->dest;
}
+ BITMAP_FREE (visited);
+ return path;
}