X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcfgloopanal.c;h=5a9189787eae1727a0eac86b7e49dc5a23cdeda0;hb=99f2248e961ae8770af13ccd04282b83758500e5;hp=1c2a57d182c6e3c9c95c0c5baa17bd176c7ce33c;hpb=862be7479682d06ddaaef2a0439cff0783f0c32e;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cfgloopanal.c b/gcc/cfgloopanal.c index 1c2a57d182c..5a9189787ea 100644 --- a/gcc/cfgloopanal.c +++ b/gcc/cfgloopanal.c @@ -1,5 +1,5 @@ /* Natural loop analysis code for GNU compiler. - Copyright (C) 2002 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. This file is part of GCC. @@ -15,8 +15,8 @@ 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. */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ #include "config.h" #include "system.h" @@ -24,42 +24,19 @@ 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 "expr.h" #include "output.h" -struct unmark_altered_insn_data; -static void unmark_altered PARAMS ((rtx, rtx, regset)); -static void blocks_invariant_registers PARAMS ((basic_block *, int, regset)); -static void unmark_altered_insn PARAMS ((rtx, rtx, struct unmark_altered_insn_data *)); -static void blocks_single_set_registers PARAMS ((basic_block *, int, rtx *)); -static int invariant_rtx_wrto_regs_p_helper PARAMS ((rtx *, regset)); -static bool invariant_rtx_wrto_regs_p PARAMS ((rtx, regset)); -static rtx test_for_iteration PARAMS ((struct loop_desc *desc, - unsigned HOST_WIDE_INT)); -static bool constant_iterations PARAMS ((struct loop_desc *, - unsigned HOST_WIDE_INT *, - bool *)); -static bool simple_loop_exit_p PARAMS ((struct loops *, struct loop *, - edge, regset, rtx *, - struct loop_desc *)); -static rtx variable_initial_value PARAMS ((rtx, regset, rtx, rtx *)); -static rtx variable_initial_values PARAMS ((edge, rtx)); -static bool simple_condition_p PARAMS ((struct loop *, rtx, - regset, struct loop_desc *)); -static basic_block simple_increment PARAMS ((struct loops *, struct loop *, - rtx *, struct loop_desc *)); - /* Checks whether BB is executed exactly once in each LOOP iteration. */ + bool -just_once_each_iteration_p (loops, loop, bb) - struct loops *loops; - struct loop *loop; - basic_block bb; +just_once_each_iteration_p (const struct loop *loop, basic_block bb) { /* It must be executed at least once each iteration. */ - if (!dominated_by_p (loops->cfg.dom, loop->latch, bb)) + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) return false; /* And just once. */ @@ -73,928 +50,327 @@ just_once_each_iteration_p (loops, loop, bb) return true; } +/* Structure representing edge of a graph. */ -/* Unmarks modified registers; helper to blocks_invariant_registers. */ -static void -unmark_altered (what, by, regs) - rtx what; - rtx by ATTRIBUTE_UNUSED; - regset regs; +struct edge { - if (GET_CODE (what) == SUBREG) - what = SUBREG_REG (what); - if (!REG_P (what)) - return; - CLEAR_REGNO_REG_SET (regs, REGNO (what)); -} + 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. */ +}; -/* Marks registers that are invariant inside blocks BBS. */ -static void -blocks_invariant_registers (bbs, nbbs, regs) - basic_block *bbs; - int nbbs; - regset regs; +/* Structure representing vertex of a graph. */ + +struct vertex { - rtx insn; - int i; + struct edge *pred, *succ; + /* Lists of predecessors and successors. */ + int component; /* Number of dfs restarts before reaching the + vertex. */ + int post; /* Postorder number. */ +}; - for (i = 0; i < max_reg_num (); i++) - SET_REGNO_REG_SET (regs, i); - for (i = 0; i < nbbs; i++) - for (insn = bbs[i]->head; - insn != NEXT_INSN (bbs[i]->end); - insn = NEXT_INSN (insn)) - if (INSN_P (insn)) - note_stores (PATTERN (insn), - (void (*) PARAMS ((rtx, rtx, void *))) unmark_altered, - regs); -} +/* Structure representing a graph. */ -/* Unmarks modified registers; helper to blocks_single_set_registers. */ -struct unmark_altered_insn_data +struct graph { - rtx *regs; - rtx insn; + int n_vertices; /* Number of vertices. */ + struct vertex *vertices; + /* The vertices. */ }; -static void -unmark_altered_insn (what, by, data) - rtx what; - rtx by ATTRIBUTE_UNUSED; - struct unmark_altered_insn_data *data; -{ - int rn; +/* Dumps graph G into F. */ - 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; -} +extern void dump_graph (FILE *, struct graph *); -/* Marks registers that have just single simple set in BBS; the relevant - insn is returned in REGS. */ -static void -blocks_single_set_registers (bbs, nbbs, regs) - basic_block *bbs; - int nbbs; - rtx *regs; +void +dump_graph (FILE *f, struct graph *g) { - rtx insn; 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 = bbs[i]->head; - insn != NEXT_INSN (bbs[i]->end); - 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 = bbs[i]->head; - insn != NEXT_INSN (bbs[i]->end); - insn = NEXT_INSN (insn)) - { - if (!INSN_P (insn)) - continue; - data.insn = insn; - note_stores (PATTERN (insn), - (void (*) PARAMS ((rtx, rtx, void *))) unmark_altered_insn, - &data); - } -} + struct edge *e; -/* Helper for invariant_rtx_wrto_regs_p. */ -static int -invariant_rtx_wrto_regs_p_helper (expr, invariant_regs) - rtx *expr; - regset invariant_regs; -{ - switch (GET_CODE (*expr)) + for (i = 0; i < g->n_vertices; i++) { - 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; + 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"); } } -/* Checks that EXPR is invariant provided that INVARIANT_REGS are invariant. */ -static bool -invariant_rtx_wrto_regs_p (expr, invariant_regs) - rtx expr; - regset invariant_regs; -{ - return !for_each_rtx (&expr, (rtx_function) invariant_rtx_wrto_regs_p_helper, - invariant_regs); -} +/* Creates a new graph with N_VERTICES vertices. */ -/* 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 (loop, condition, invariant_regs, desc) - struct loop *loop ATTRIBUTE_UNUSED; - rtx condition; - regset invariant_regs; - struct loop_desc *desc; +static struct graph * +new_graph (int n_vertices) { - 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; - } + struct graph *g = XNEW (struct graph); - /* 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); - - /* One of operands must be invariant. */ - if (invariant_rtx_wrto_regs_p (op0, invariant_regs)) - { - /* 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; - } + g->n_vertices = n_vertices; + g->vertices = XCNEWVEC (struct vertex, n_vertices); - /* 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; + return g; } -/* 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 (loops, loop, simple_increment_regs, desc) - struct loops *loops; - struct loop *loop; - rtx *simple_increment_regs; - struct loop_desc *desc; -{ - rtx mod_insn, set, set_src, set_add; - basic_block mod_bb; - - /* 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 (loops, 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); - if (GET_CODE (set_src) != PLUS) - return NULL; - if (!rtx_equal_p (XEXP (set_src, 0), desc->var)) - return NULL; - - /* Set desc->stride. */ - set_add = XEXP (set_src, 1); - if (CONSTANT_P (set_add)) - desc->stride = set_add; - else - return NULL; +/* Adds an edge from F to T to graph G, with DATA attached. */ - return mod_bb; -} - -/* 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. */ -static rtx -variable_initial_value (insn, invariant_regs, var, set_insn) - rtx insn; - regset invariant_regs; - rtx var; - rtx *set_insn; +static void +add_edge (struct graph *g, int f, int t, void *data) { - basic_block bb; - rtx set; - - /* Go back through cfg. */ - bb = BLOCK_FOR_INSN (insn); - while (1) - { - for (; insn != bb->head; insn = PREV_INSN (insn)) - { - if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn))) - break; - if (INSN_P (insn)) - note_stores (PATTERN (insn), - (void (*) PARAMS ((rtx, rtx, void *))) unmark_altered, - invariant_regs); - } - - if (insn != bb->head) - { - /* 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 (!invariant_rtx_wrto_regs_p (val, invariant_regs)) - return NULL; - - if (set_insn) - *set_insn = insn; - return val; - } + struct edge *e = xmalloc (sizeof (struct edge)); + e->src = f; + e->dest = t; + e->data = data; - if (bb->pred->pred_next || bb->pred->src == ENTRY_BLOCK_PTR) - return NULL; - - bb = bb->pred->src; - insn = bb->end; - } + e->pred_next = g->vertices[t].pred; + g->vertices[t].pred = e; - return NULL; + e->succ_next = g->vertices[f].succ; + g->vertices[f].succ = e; } -/* Returns list of definitions of initial value of VAR at Edge. */ -static rtx -variable_initial_values (e, var) - edge e; - rtx var; -{ - rtx set_insn, list; - regset invariant_regs; - regset_head invariant_regs_head; - int i; - - invariant_regs = INITIALIZE_REG_SET (invariant_regs_head); - for (i = 0; i < max_reg_num (); i++) - SET_REGNO_REG_SET (invariant_regs, i); - - list = alloc_EXPR_LIST (0, copy_rtx (var), NULL); - - if (e->src == ENTRY_BLOCK_PTR) - return list; +/* 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. */ - set_insn = e->src->end; - while (REG_P (var) - && (var = variable_initial_value (set_insn, invariant_regs, var, &set_insn))) - list = alloc_EXPR_LIST (0, copy_rtx (var), list); - - FREE_REG_SET (invariant_regs); - return list; -} - -/* Counts constant number of iterations of the loop described by DESC; - returns false if impossible. */ -static bool -constant_iterations (desc, niter, may_be_zero) - struct loop_desc *desc; - unsigned HOST_WIDE_INT *niter; - bool *may_be_zero; +static void +dfs (struct graph *g, int *qs, int nq, int *qt, bool forward) { - rtx test, expr; - rtx ainit, alim; + int i, tick = 0, v, comp = 0, top; + struct edge *e; + struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices); - test = test_for_iteration (desc, 0); - if (test == const0_rtx) + for (i = 0; i < g->n_vertices; i++) { - *niter = 0; - *may_be_zero = false; - return true; + g->vertices[i].component = -1; + g->vertices[i].post = -1; } - *may_be_zero = (test != const_true_rtx); +#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) - /* 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)) + for (i = 0; i < nq; i++) { - alim = XEXP (desc->lim_alts, 0); - if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim))) - abort (); - 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)))) - abort (); - if (GET_CODE (expr) == CONST_INT) - { - *niter = INTVAL (expr); - return true; - } - } + v = qs[i]; + if (g->vertices[v].post != -1) + continue; - return false; -} + g->vertices[v].component = comp++; + e = FST_EDGE (v); + top = 0; -/* 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++);"). - - 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. - - When INIT/LIM are set, they are used instead of var/lim of DESC. */ -rtx -count_loop_iterations (desc, init, lim) - struct loop_desc *desc; - rtx init; - rtx lim; -{ - enum rtx_code cond = desc->cond; - rtx stride = desc->stride; - rtx mod, exp; - - /* 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; - - 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); - - /* Compute absolute value of the difference of initial and final value. */ - if (INTVAL (stride) > 0) - { - /* Bypass nonsensical tests. */ - if (cond == EQ || cond == GE || cond == GT || cond == GEU - || cond == GTU) - return NULL; - exp = simplify_gen_binary (MINUS, GET_MODE (desc->var), - lim, init); - } - else - { - /* Bypass nonsensical tests. */ - if (cond == EQ || cond == LE || cond == LT || cond == LEU - || cond == LTU) - return NULL; - exp = simplify_gen_binary (MINUS, GET_MODE (desc->var), - init, lim); - stride = simplify_gen_unary (NEG, GET_MODE (desc->var), - stride, GET_MODE (desc->var)); - } - - /* Normalize difference so the value is always first examined - and later incremented. */ - - if (!desc->postincr) - exp = simplify_gen_binary (MINUS, GET_MODE (desc->var), - exp, stride); - - /* Determine delta caused by exit condition. */ - switch (cond) - { - case NE: - /* For NE tests, make sure that the iteration variable won't miss - the final value. If EXP mod STRIDE is not zero, then the - iteration variable will overflow before the loop exits, and we - can not calculate the number of iterations easily. */ - if (stride != const1_rtx - && (simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride) - != const0_rtx)) - return NULL; - break; - case LT: - case GT: - case LTU: - case GTU: - break; - case LE: - case GE: - case LEU: - case GEU: - exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), - exp, const1_rtx); - break; - default: - abort (); - } + while (1) + { + while (e && g->vertices[EDGE_DEST (e)].component != -1) + e = NEXT_EDGE (e); - if (stride != const1_rtx) - { - /* Number of iterations is now (EXP + STRIDE - 1 / STRIDE), - but we need to take care for overflows. */ + if (!e) + { + if (qt) + qt[tick] = v; + g->vertices[v].post = tick++; - mod = simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride); + if (!top) + break; - /* 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. */ + e = stack[--top]; + v = EDGE_SRC (e); + e = NEXT_EDGE (e); + continue; + } - if (GET_CODE (mod) != CONST_INT) - { - rtx stridem1 = simplify_gen_binary (PLUS, GET_MODE (desc->var), - stride, constm1_rtx); - exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), - exp, stridem1); - exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride); - } - else - { - exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride); - if (mod != const0_rtx) - exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), - exp, const1_rtx); + stack[top++] = e; + v = EDGE_DEST (e); + e = FST_EDGE (v); + g->vertices[v].component = comp - 1; } } - if (rtl_dump_file) - { - fprintf (rtl_dump_file, "; Number of iterations: "); - print_simple_rtl (rtl_dump_file, exp); - fprintf (rtl_dump_file, "\n"); - } - - return exp; -} - -/* Return simplified RTX expression representing the value of test - described of DESC at given iteration of loop. */ - -static rtx -test_for_iteration (desc, iter) - 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 (rtl_dump_file) - { - fprintf (rtl_dump_file, "; Conditional to continue loop at "); - fprintf (rtl_dump_file, HOST_WIDE_INT_PRINT_UNSIGNED, iter); - fprintf (rtl_dump_file, "th iteration: "); - print_simple_rtl (rtl_dump_file, exp); - fprintf (rtl_dump_file, "\n"); - } - return exp; + free (stack); } +/* Marks the edge E in graph G irreducible if it connects two vertices in the + same scc. */ -/* 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 (loops, loop, exit_edge, invariant_regs, single_set_regs, desc) - struct loops *loops; - struct loop *loop; - edge exit_edge; - struct loop_desc *desc; - regset invariant_regs; - rtx *single_set_regs; +static void +check_irred (struct graph *g, struct edge *e) { - basic_block mod_bb, exit_bb; - int fallthru_out; - rtx condition; - edge ei, e; + edge real = e->data; - exit_bb = exit_edge->src; + /* All edges should lead from a component with higher number to the + one with lower one. */ + gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component); - fallthru_out = (exit_edge->flags & EDGE_FALLTHRU); - - if (!exit_bb) - return false; + if (g->vertices[e->src].component != g->vertices[e->dest].component) + return; - /* It must be tested (at least) once during any iteration. */ - if (!dominated_by_p (loops->cfg.dom, loop->latch, exit_bb)) - return false; + real->flags |= EDGE_IRREDUCIBLE_LOOP; + if (flow_bb_inside_loop_p (real->src->loop_father, real->dest)) + real->src->flags |= BB_IRREDUCIBLE_LOOP; +} - /* It must end in a simple conditional jump. */ - if (!any_condjump_p (exit_bb->end)) - return false; +/* Runs CALLBACK for all edges in G. */ - ei = exit_bb->succ; - if (ei == exit_edge) - ei = ei->succ_next; +static void +for_each_edge (struct graph *g, + void (callback) (struct graph *, struct edge *)) +{ + struct edge *e; + int i; - desc->out_edge = exit_edge; - desc->in_edge = ei; + for (i = 0; i < g->n_vertices; i++) + for (e = g->vertices[i].succ; e; e = e->succ_next) + callback (g, e); +} - /* Condition must be a simple comparison in that one of operands - is register and the other one is invariant. */ - if (!(condition = get_condition (exit_bb->end, NULL))) - return false; +/* Releases the memory occupied by G. */ - if (!simple_condition_p (loop, condition, invariant_regs, desc)) - return false; +static void +free_graph (struct graph *g) +{ + struct edge *e, *n; + int i; - /* Var must be simply incremented or decremented in exactly one insn that - is executed just once every iteration. */ - if (!(mod_bb = simple_increment (loops, loop, single_set_regs, desc))) - return false; + 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); +} - /* OK, it is simple loop. Now just fill in remaining info. */ - desc->postincr = !dominated_by_p (loops->cfg.dom, exit_bb, mod_bb); - desc->neg = !fallthru_out; +/* 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. - /* 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->lim_alts = variable_initial_values (e, desc->lim); + LOOPS is the loop tree. */ - /* Number of iterations. */ - if (!count_loop_iterations (desc, NULL, NULL)) - return false; - desc->const_iter = - constant_iterations (desc, &desc->niter, &desc->may_be_zero); - return true; -} +#define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block) +#define BB_REPR(BB) ((BB)->index + 1) -/* Tests whether LOOP is simple for loop. Returns simple loop description - in DESC. */ -bool -simple_loop_p (loops, loop, desc) - struct loops *loops; - struct loop *loop; - struct loop_desc *desc; +void +mark_irreducible_loops (void) { - unsigned i; - basic_block *body; + basic_block act; 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++) + edge_iterator ei; + int i, src, dest; + struct graph *g; + int num = current_loops ? number_of_loops () : 1; + int *queue1 = XNEWVEC (int, last_basic_block + num); + int *queue2 = XNEWVEC (int, last_basic_block + num); + int nq, depth; + struct loop *cloop, *loop; + loop_iterator li; + + /* Reset the flags. */ + FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) { - for (e = body[i]->succ; e; e = e->succ_next) - if (!flow_bb_inside_loop_p (loop, e->dest) - && simple_loop_exit_p (loops, 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++; + act->flags &= ~BB_IRREDUCIBLE_LOOP; + FOR_EACH_EDGE (e, ei, act->succs) + e->flags &= ~EDGE_IRREDUCIBLE_LOOP; } - desc->n_branches = n_branches; - - if (rtl_dump_file && any) - { - fprintf (rtl_dump_file, "; Simple loop %i\n", loop->num); - if (desc->postincr) - fprintf (rtl_dump_file, - "; does postincrement after loop exit condition\n"); - - fprintf (rtl_dump_file, "; Induction variable:"); - print_simple_rtl (rtl_dump_file, desc->var); - fputc ('\n', rtl_dump_file); - fprintf (rtl_dump_file, "; Initial values:"); - print_simple_rtl (rtl_dump_file, desc->var_alts); - fputc ('\n', rtl_dump_file); - - fprintf (rtl_dump_file, "; Stride:"); - print_simple_rtl (rtl_dump_file, desc->stride); - fputc ('\n', rtl_dump_file); + /* Create the edge lists. */ + g = new_graph (last_basic_block + num); - fprintf (rtl_dump_file, "; Compared with:"); - print_simple_rtl (rtl_dump_file, desc->lim); - fputc ('\n', rtl_dump_file); + FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) + FOR_EACH_EDGE (e, ei, act->succs) + { + /* Ignore edges to exit. */ + if (e->dest == EXIT_BLOCK_PTR) + continue; - fprintf (rtl_dump_file, "; Alternative values:"); - print_simple_rtl (rtl_dump_file, desc->lim_alts); - fputc ('\n', rtl_dump_file); + src = BB_REPR (act); + dest = BB_REPR (e->dest); - fprintf (rtl_dump_file, "; Exit condition:"); - if (desc->neg) - fprintf (rtl_dump_file, "(negated)"); - fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond)); + if (current_loops) + { + /* Ignore latch edges. */ + if (e->dest->loop_father->header == e->dest + && e->dest->loop_father->latch == act) + continue; - fprintf (rtl_dump_file, "; Number of branches:"); - fprintf (rtl_dump_file, "%d\n", desc->n_branches); + /* 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. - fputc ('\n', rtl_dump_file); - } + Edges exiting loops should lead from representative + of the son of nearest common ancestor of the loops in that + act lays. */ - free (body); - FREE_REG_SET (invariant_regs); - free (single_set_regs); - return any; -} + if (e->dest->loop_father->header == e->dest) + dest = LOOP_REPR (e->dest->loop_father); -/* Marks blocks 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. */ -void -mark_irreducible_loops (loops) - struct loops *loops; -{ - int *dfs_in, *closed, *mr, *mri, *n_edges, *stack; - unsigned i; - edge **edges, e; - basic_block act; - int stack_top, tick, depth; - struct loop *cloop; - - /* The first last_basic_block + 1 entries are for real blocks (including - entry); then we have loops->num - 1 fake blocks for loops to that we - assign edges leading from loops (fake loop 0 is not interesting). */ - dfs_in = xmalloc ((last_basic_block + loops->num) * sizeof (int)); - closed = xmalloc ((last_basic_block + loops->num) * sizeof (int)); - mr = xmalloc ((last_basic_block + loops->num) * sizeof (int)); - mri = xmalloc ((last_basic_block + loops->num) * sizeof (int)); - n_edges = xmalloc ((last_basic_block + loops->num) * sizeof (int)); - edges = xmalloc ((last_basic_block + loops->num) * sizeof (edge *)); - stack = xmalloc ((n_basic_blocks + loops->num) * sizeof (int)); + 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]; - /* Create the edge lists. */ - for (i = 0; i < last_basic_block + loops->num; i++) - n_edges[i] = 0; - 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. */ - if (act->loop_father == e->dest->loop_father - || act->loop_father == e->dest->loop_father->outer) - { - n_edges[act->index + 1]++; - continue; + src = LOOP_REPR (cloop); + } } - /* Edges exiting loops remain. They should lead from representative - of the son of nearest common ancestor of the loops in that - act lays. */ - 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]; - n_edges[cloop->num + last_basic_block]++; - } - for (i = 0; i < last_basic_block + loops->num; i++) - { - edges[i] = xmalloc (n_edges[i] * sizeof (edge)); - n_edges[i] = 0; - } - - FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) - for (e = act->succ; e; e = e->succ_next) - { - if (e->dest == EXIT_BLOCK_PTR) - continue; - if (e->dest->loop_father->header == e->dest - && e->dest->loop_father->latch == act) - continue; - if (act->loop_father == e->dest->loop_father - || act->loop_father == e->dest->loop_father->outer) - { - edges[act->index + 1][n_edges[act->index + 1]++] = e; - continue; - } - 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]; - i = cloop->num + last_basic_block; - edges[i][n_edges[i]++] = e; + add_edge (g, src, dest, e); } - /* Compute dfs numbering, starting from loop headers, and mark found - loops.*/ - tick = 0; - for (i = 0; i < last_basic_block + loops->num; i++) + /* 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) { - dfs_in[i] = -1; - closed[i] = 0; - mr[i] = last_basic_block + loops->num; - mri[i] = -1; + queue1[nq++] = BB_REPR (act); } - stack_top = 0; - for (i = 0; i < loops->num; i++) - if (loops->parray[i]) - stack[stack_top++] = loops->parray[i]->header->index + 1; - - while (stack_top) + if (current_loops) { - int idx, sidx; - - idx = stack[stack_top - 1]; - if (dfs_in[idx] < 0) - dfs_in[idx] = tick++; - - while (n_edges[idx]) + FOR_EACH_LOOP (li, loop, 0) { - e = edges[idx][--n_edges[idx]]; - sidx = e->dest->loop_father->header == e->dest - ? e->dest->loop_father->num + last_basic_block - : e->dest->index + 1; - if (closed[sidx]) - { - if (mr[sidx] < mr[idx] && !closed[mri[sidx]]) - { - mr[idx] = mr[sidx]; - mri[idx] = mri[sidx]; - } - continue; - } - if (dfs_in[sidx] < 0) - { - stack[stack_top++] = sidx; - goto next; - } - if (dfs_in[sidx] < mr[idx]) - { - mr[idx] = dfs_in[sidx]; - mri[idx] = sidx; - } - } - - /* Return back. */ - closed[idx] = 1; - stack_top--; - if (stack_top && dfs_in[stack[stack_top - 1]] >= 0) - { - /* Propagate information back. */ - sidx = stack[stack_top - 1]; - if (mr[sidx] > mr[idx]) - { - mr[sidx] = mr[idx]; - mri[sidx] = mri[idx]; - } + queue1[nq++] = LOOP_REPR (loop); } - /* Mark the block if relevant. */ - if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx]) - BASIC_BLOCK (idx - 1)->flags |= BB_IRREDUCIBLE_LOOP; -next:; } + dfs (g, queue1, nq, queue2, false); + for (i = 0; i < nq; i++) + queue1[i] = queue2[nq - i - 1]; + dfs (g, queue1, nq, NULL, true); - free (stack); - free (dfs_in); - free (closed); - free (mr); - free (mri); - for (i = 0; i < last_basic_block + loops->num; i++) - free (edges[i]); - free (edges); - free (n_edges); - loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS; + /* Mark the irreducible loops. */ + for_each_edge (g, check_irred); + + free_graph (g); + free (queue1); + free (queue2); + + if (current_loops) + current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS; } /* Counts number of insns inside LOOP. */ int -num_loop_insns (loop) - struct loop *loop; +num_loop_insns (struct loop *loop) { basic_block *bbs, bb; unsigned i, ninsns = 0; @@ -1005,18 +381,18 @@ num_loop_insns (loop) { bb = bbs[i]; ninsns++; - for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn)) - ninsns++; + for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) + if (INSN_P (insn)) + ninsns++; } free(bbs); - + return ninsns; } /* Counts number of insns executed on average per iteration LOOP. */ int -average_num_loop_insns (loop) - struct loop *loop; +average_num_loop_insns (struct loop *loop) { basic_block *bbs, bb; unsigned i, binsns, ninsns, ratio; @@ -1029,8 +405,9 @@ average_num_loop_insns (loop) bb = bbs[i]; binsns = 1; - for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn)) - binsns++; + 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 @@ -1038,7 +415,7 @@ average_num_loop_insns (loop) ninsns += binsns * ratio; } free(bbs); - + ninsns /= BB_FREQ_MAX; if (!ninsns) ninsns = 1; /* To avoid division by zero. */ @@ -1050,28 +427,28 @@ average_num_loop_insns (loop) 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 (loop) - const struct loop *loop; +expected_loop_iterations (const struct loop *loop) { edge e; + edge_iterator ei; - if (loop->header->count) + if (loop->latch->count || loop->header->count) { gcov_type count_in, count_latch, expected; count_in = 0; count_latch = 0; - for (e = loop->header->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, loop->header->preds) 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; + expected = count_latch * 2; + else + expected = (count_latch + count_in - 1) / count_in; /* Avoid overflows. */ return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); @@ -1083,15 +460,147 @@ expected_loop_iterations (loop) freq_in = 0; freq_latch = 0; - for (e = loop->header->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, loop->header->preds) 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 * 2; return (freq_latch + freq_in - 1) / freq_in; } } + +/* Returns the maximum level of nesting of subloops of LOOP. */ + +unsigned +get_loop_level (const struct loop *loop) +{ + const struct loop *ploop; + unsigned mx = 0, l; + + for (ploop = loop->inner; ploop; ploop = ploop->next) + { + l = get_loop_level (ploop); + if (l >= mx) + mx = l + 1; + } + return mx; +} + +/* Returns estimate on cost of computing SEQ. */ + +static unsigned +seq_cost (rtx seq) +{ + unsigned cost = 0; + rtx set; + + for (; seq; seq = NEXT_INSN (seq)) + { + set = single_set (seq); + if (set) + cost += rtx_cost (set, SET); + else + cost++; + } + + return cost; +} + +/* The properties of the target. */ + +unsigned target_avail_regs; /* Number of available registers. */ +unsigned target_res_regs; /* Number of reserved registers. */ +unsigned target_small_cost; /* The cost for register when there is a free one. */ +unsigned target_pres_cost; /* The cost for register when there are not too many + free ones. */ +unsigned target_spill_cost; /* The cost for register when we need to spill. */ + +/* Initialize the constants for computing set costs. */ + +void +init_set_costs (void) +{ + rtx seq; + rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER); + rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1); + rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2); + rtx mem = validize_mem (gen_rtx_MEM (SImode, addr)); + unsigned i; + + 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++; + + target_res_regs = 3; + + /* These are really just heuristic values. */ + + start_sequence (); + emit_move_insn (reg1, reg2); + seq = get_insns (); + end_sequence (); + target_small_cost = seq_cost (seq); + target_pres_cost = 2 * target_small_cost; + + start_sequence (); + emit_move_insn (mem, reg1); + emit_move_insn (reg2, mem); + seq = get_insns (); + end_sequence (); + target_spill_cost = seq_cost (seq); +} + +/* Calculates cost for having SIZE new loop global variables. REGS_USED is the + number of global registers used in loop. N_USES is the number of relevant + variable uses. */ + +unsigned +global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses) +{ + unsigned regs_needed = regs_used + size; + unsigned cost = 0; + + if (regs_needed + target_res_regs <= target_avail_regs) + cost += target_small_cost * size; + else if (regs_needed <= target_avail_regs) + cost += target_pres_cost * size; + else + { + cost += target_pres_cost * size; + cost += target_spill_cost * n_uses * (regs_needed - target_avail_regs) / regs_needed; + } + + return cost; +} + +/* Sets EDGE_LOOP_EXIT flag for all loop exits. */ + +void +mark_loop_exit_edges (void) +{ + basic_block bb; + edge e; + + if (!current_loops) + return; + + FOR_EACH_BB (bb) + { + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (bb->loop_father->outer + && loop_exit_edge_p (bb->loop_father, e)) + e->flags |= EDGE_LOOP_EXIT; + else + e->flags &= ~EDGE_LOOP_EXIT; + } + } +} +