/* Natural loop discovery code for GNU compiler.
|
/* Natural loop discovery code for GNU compiler.
|
Copyright (C) 2000, 2001, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2000, 2001, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
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
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "obstack.h"
|
#include "obstack.h"
|
#include "function.h"
|
#include "function.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
|
|
/* Ratio of frequencies of edges so that one of more latch edges is
|
/* Ratio of frequencies of edges so that one of more latch edges is
|
considered to belong to inner loop with same header. */
|
considered to belong to inner loop with same header. */
|
#define HEAVY_EDGE_RATIO 8
|
#define HEAVY_EDGE_RATIO 8
|
|
|
#define HEADER_BLOCK(B) (* (int *) (B)->aux)
|
#define HEADER_BLOCK(B) (* (int *) (B)->aux)
|
#define LATCH_EDGE(E) (*(int *) (E)->aux)
|
#define LATCH_EDGE(E) (*(int *) (E)->aux)
|
|
|
static void flow_loops_cfg_dump (const struct loops *, FILE *);
|
static void flow_loops_cfg_dump (const struct loops *, FILE *);
|
static int flow_loop_level_compute (struct loop *);
|
static int flow_loop_level_compute (struct loop *);
|
static void flow_loops_level_compute (struct loops *);
|
static void flow_loops_level_compute (struct loops *);
|
static void establish_preds (struct loop *);
|
static void establish_preds (struct loop *);
|
static void canonicalize_loop_headers (void);
|
static void canonicalize_loop_headers (void);
|
static bool glb_enum_p (basic_block, void *);
|
static bool glb_enum_p (basic_block, void *);
|
|
|
/* Dump loop related CFG information. */
|
/* Dump loop related CFG information. */
|
|
|
static void
|
static void
|
flow_loops_cfg_dump (const struct loops *loops, FILE *file)
|
flow_loops_cfg_dump (const struct loops *loops, FILE *file)
|
{
|
{
|
int i;
|
int i;
|
basic_block bb;
|
basic_block bb;
|
|
|
if (! loops->num || ! file)
|
if (! loops->num || ! file)
|
return;
|
return;
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
edge succ;
|
edge succ;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
fprintf (file, ";; %d succs { ", bb->index);
|
fprintf (file, ";; %d succs { ", bb->index);
|
FOR_EACH_EDGE (succ, ei, bb->succs)
|
FOR_EACH_EDGE (succ, ei, bb->succs)
|
fprintf (file, "%d ", succ->dest->index);
|
fprintf (file, "%d ", succ->dest->index);
|
fprintf (file, "}\n");
|
fprintf (file, "}\n");
|
}
|
}
|
|
|
/* Dump the DFS node order. */
|
/* Dump the DFS node order. */
|
if (loops->cfg.dfs_order)
|
if (loops->cfg.dfs_order)
|
{
|
{
|
fputs (";; DFS order: ", file);
|
fputs (";; DFS order: ", file);
|
for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
fprintf (file, "%d ", loops->cfg.dfs_order[i]);
|
fprintf (file, "%d ", loops->cfg.dfs_order[i]);
|
|
|
fputs ("\n", file);
|
fputs ("\n", file);
|
}
|
}
|
|
|
/* Dump the reverse completion node order. */
|
/* Dump the reverse completion node order. */
|
if (loops->cfg.rc_order)
|
if (loops->cfg.rc_order)
|
{
|
{
|
fputs (";; RC order: ", file);
|
fputs (";; RC order: ", file);
|
for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
fprintf (file, "%d ", loops->cfg.rc_order[i]);
|
fprintf (file, "%d ", loops->cfg.rc_order[i]);
|
|
|
fputs ("\n", file);
|
fputs ("\n", file);
|
}
|
}
|
}
|
}
|
|
|
/* Return nonzero if the nodes of LOOP are a subset of OUTER. */
|
/* Return nonzero if the nodes of LOOP are a subset of OUTER. */
|
|
|
bool
|
bool
|
flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
|
flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
|
{
|
{
|
return (loop->depth > outer->depth
|
return (loop->depth > outer->depth
|
&& loop->pred[outer->depth] == outer);
|
&& loop->pred[outer->depth] == outer);
|
}
|
}
|
|
|
/* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
|
/* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
|
loops within LOOP. */
|
loops within LOOP. */
|
|
|
struct loop *
|
struct loop *
|
superloop_at_depth (struct loop *loop, unsigned depth)
|
superloop_at_depth (struct loop *loop, unsigned depth)
|
{
|
{
|
gcc_assert (depth <= (unsigned) loop->depth);
|
gcc_assert (depth <= (unsigned) loop->depth);
|
|
|
if (depth == (unsigned) loop->depth)
|
if (depth == (unsigned) loop->depth)
|
return loop;
|
return loop;
|
|
|
return loop->pred[depth];
|
return loop->pred[depth];
|
}
|
}
|
|
|
/* Dump the loop information specified by LOOP to the stream FILE
|
/* Dump the loop information specified by LOOP to the stream FILE
|
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
|
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
|
|
|
void
|
void
|
flow_loop_dump (const struct loop *loop, FILE *file,
|
flow_loop_dump (const struct loop *loop, FILE *file,
|
void (*loop_dump_aux) (const struct loop *, FILE *, int),
|
void (*loop_dump_aux) (const struct loop *, FILE *, int),
|
int verbose)
|
int verbose)
|
{
|
{
|
basic_block *bbs;
|
basic_block *bbs;
|
unsigned i;
|
unsigned i;
|
|
|
if (! loop || ! loop->header)
|
if (! loop || ! loop->header)
|
return;
|
return;
|
|
|
fprintf (file, ";;\n;; Loop %d\n", loop->num);
|
fprintf (file, ";;\n;; Loop %d\n", loop->num);
|
|
|
fprintf (file, ";; header %d, latch %d\n",
|
fprintf (file, ";; header %d, latch %d\n",
|
loop->header->index, loop->latch->index);
|
loop->header->index, loop->latch->index);
|
fprintf (file, ";; depth %d, level %d, outer %ld\n",
|
fprintf (file, ";; depth %d, level %d, outer %ld\n",
|
loop->depth, loop->level,
|
loop->depth, loop->level,
|
(long) (loop->outer ? loop->outer->num : -1));
|
(long) (loop->outer ? loop->outer->num : -1));
|
|
|
fprintf (file, ";; nodes:");
|
fprintf (file, ";; nodes:");
|
bbs = get_loop_body (loop);
|
bbs = get_loop_body (loop);
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
fprintf (file, " %d", bbs[i]->index);
|
fprintf (file, " %d", bbs[i]->index);
|
free (bbs);
|
free (bbs);
|
fprintf (file, "\n");
|
fprintf (file, "\n");
|
|
|
if (loop_dump_aux)
|
if (loop_dump_aux)
|
loop_dump_aux (loop, file, verbose);
|
loop_dump_aux (loop, file, verbose);
|
}
|
}
|
|
|
/* Dump the loop information specified by LOOPS to the stream FILE,
|
/* Dump the loop information specified by LOOPS to the stream FILE,
|
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
|
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
|
|
|
void
|
void
|
flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
|
flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
|
{
|
{
|
int i;
|
int i;
|
int num_loops;
|
int num_loops;
|
|
|
num_loops = loops->num;
|
num_loops = loops->num;
|
if (! num_loops || ! file)
|
if (! num_loops || ! file)
|
return;
|
return;
|
|
|
fprintf (file, ";; %d loops found\n", num_loops);
|
fprintf (file, ";; %d loops found\n", num_loops);
|
|
|
for (i = 0; i < num_loops; i++)
|
for (i = 0; i < num_loops; i++)
|
{
|
{
|
struct loop *loop = loops->parray[i];
|
struct loop *loop = loops->parray[i];
|
|
|
if (!loop)
|
if (!loop)
|
continue;
|
continue;
|
|
|
flow_loop_dump (loop, file, loop_dump_aux, verbose);
|
flow_loop_dump (loop, file, loop_dump_aux, verbose);
|
}
|
}
|
|
|
if (verbose)
|
if (verbose)
|
flow_loops_cfg_dump (loops, file);
|
flow_loops_cfg_dump (loops, file);
|
}
|
}
|
|
|
/* Free data allocated for LOOP. */
|
/* Free data allocated for LOOP. */
|
void
|
void
|
flow_loop_free (struct loop *loop)
|
flow_loop_free (struct loop *loop)
|
{
|
{
|
if (loop->pred)
|
if (loop->pred)
|
free (loop->pred);
|
free (loop->pred);
|
free (loop);
|
free (loop);
|
}
|
}
|
|
|
/* Free all the memory allocated for LOOPS. */
|
/* Free all the memory allocated for LOOPS. */
|
|
|
void
|
void
|
flow_loops_free (struct loops *loops)
|
flow_loops_free (struct loops *loops)
|
{
|
{
|
if (loops->parray)
|
if (loops->parray)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
|
|
gcc_assert (loops->num);
|
gcc_assert (loops->num);
|
|
|
/* Free the loop descriptors. */
|
/* Free the loop descriptors. */
|
for (i = 0; i < loops->num; i++)
|
for (i = 0; i < loops->num; i++)
|
{
|
{
|
struct loop *loop = loops->parray[i];
|
struct loop *loop = loops->parray[i];
|
|
|
if (!loop)
|
if (!loop)
|
continue;
|
continue;
|
|
|
flow_loop_free (loop);
|
flow_loop_free (loop);
|
}
|
}
|
|
|
free (loops->parray);
|
free (loops->parray);
|
loops->parray = NULL;
|
loops->parray = NULL;
|
|
|
if (loops->cfg.dfs_order)
|
if (loops->cfg.dfs_order)
|
free (loops->cfg.dfs_order);
|
free (loops->cfg.dfs_order);
|
if (loops->cfg.rc_order)
|
if (loops->cfg.rc_order)
|
free (loops->cfg.rc_order);
|
free (loops->cfg.rc_order);
|
|
|
}
|
}
|
}
|
}
|
|
|
/* Find the nodes contained within the LOOP with header HEADER.
|
/* Find the nodes contained within the LOOP with header HEADER.
|
Return the number of nodes within the loop. */
|
Return the number of nodes within the loop. */
|
|
|
int
|
int
|
flow_loop_nodes_find (basic_block header, struct loop *loop)
|
flow_loop_nodes_find (basic_block header, struct loop *loop)
|
{
|
{
|
basic_block *stack;
|
basic_block *stack;
|
int sp;
|
int sp;
|
int num_nodes = 1;
|
int num_nodes = 1;
|
|
|
header->loop_father = loop;
|
header->loop_father = loop;
|
header->loop_depth = loop->depth;
|
header->loop_depth = loop->depth;
|
|
|
if (loop->latch->loop_father != loop)
|
if (loop->latch->loop_father != loop)
|
{
|
{
|
stack = XNEWVEC (basic_block, n_basic_blocks);
|
stack = XNEWVEC (basic_block, n_basic_blocks);
|
sp = 0;
|
sp = 0;
|
num_nodes++;
|
num_nodes++;
|
stack[sp++] = loop->latch;
|
stack[sp++] = loop->latch;
|
loop->latch->loop_father = loop;
|
loop->latch->loop_father = loop;
|
loop->latch->loop_depth = loop->depth;
|
loop->latch->loop_depth = loop->depth;
|
|
|
while (sp)
|
while (sp)
|
{
|
{
|
basic_block node;
|
basic_block node;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
node = stack[--sp];
|
node = stack[--sp];
|
|
|
FOR_EACH_EDGE (e, ei, node->preds)
|
FOR_EACH_EDGE (e, ei, node->preds)
|
{
|
{
|
basic_block ancestor = e->src;
|
basic_block ancestor = e->src;
|
|
|
if (ancestor != ENTRY_BLOCK_PTR
|
if (ancestor != ENTRY_BLOCK_PTR
|
&& ancestor->loop_father != loop)
|
&& ancestor->loop_father != loop)
|
{
|
{
|
ancestor->loop_father = loop;
|
ancestor->loop_father = loop;
|
ancestor->loop_depth = loop->depth;
|
ancestor->loop_depth = loop->depth;
|
num_nodes++;
|
num_nodes++;
|
stack[sp++] = ancestor;
|
stack[sp++] = ancestor;
|
}
|
}
|
}
|
}
|
}
|
}
|
free (stack);
|
free (stack);
|
}
|
}
|
return num_nodes;
|
return num_nodes;
|
}
|
}
|
|
|
/* For each loop in the lOOPS tree that has just a single exit
|
/* For each loop in the lOOPS tree that has just a single exit
|
record the exit edge. */
|
record the exit edge. */
|
|
|
void
|
void
|
mark_single_exit_loops (struct loops *loops)
|
mark_single_exit_loops (struct loops *loops)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
edge e;
|
edge e;
|
struct loop *loop;
|
struct loop *loop;
|
unsigned i;
|
unsigned i;
|
|
|
for (i = 1; i < loops->num; i++)
|
for (i = 1; i < loops->num; i++)
|
{
|
{
|
loop = loops->parray[i];
|
loop = loops->parray[i];
|
if (loop)
|
if (loop)
|
loop->single_exit = NULL;
|
loop->single_exit = NULL;
|
}
|
}
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
edge_iterator ei;
|
edge_iterator ei;
|
if (bb->loop_father == loops->tree_root)
|
if (bb->loop_father == loops->tree_root)
|
continue;
|
continue;
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
{
|
{
|
if (e->dest == EXIT_BLOCK_PTR)
|
if (e->dest == EXIT_BLOCK_PTR)
|
continue;
|
continue;
|
|
|
if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
|
if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
|
continue;
|
continue;
|
|
|
for (loop = bb->loop_father;
|
for (loop = bb->loop_father;
|
loop != e->dest->loop_father;
|
loop != e->dest->loop_father;
|
loop = loop->outer)
|
loop = loop->outer)
|
{
|
{
|
/* If we have already seen an exit, mark this by the edge that
|
/* If we have already seen an exit, mark this by the edge that
|
surely does not occur as any exit. */
|
surely does not occur as any exit. */
|
if (loop->single_exit)
|
if (loop->single_exit)
|
loop->single_exit = single_succ_edge (ENTRY_BLOCK_PTR);
|
loop->single_exit = single_succ_edge (ENTRY_BLOCK_PTR);
|
else
|
else
|
loop->single_exit = e;
|
loop->single_exit = e;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
for (i = 1; i < loops->num; i++)
|
for (i = 1; i < loops->num; i++)
|
{
|
{
|
loop = loops->parray[i];
|
loop = loops->parray[i];
|
if (!loop)
|
if (!loop)
|
continue;
|
continue;
|
|
|
if (loop->single_exit == single_succ_edge (ENTRY_BLOCK_PTR))
|
if (loop->single_exit == single_succ_edge (ENTRY_BLOCK_PTR))
|
loop->single_exit = NULL;
|
loop->single_exit = NULL;
|
}
|
}
|
|
|
loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
|
loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
|
}
|
}
|
|
|
static void
|
static void
|
establish_preds (struct loop *loop)
|
establish_preds (struct loop *loop)
|
{
|
{
|
struct loop *ploop, *father = loop->outer;
|
struct loop *ploop, *father = loop->outer;
|
|
|
loop->depth = father->depth + 1;
|
loop->depth = father->depth + 1;
|
|
|
/* Remember the current loop depth if it is the largest seen so far. */
|
/* Remember the current loop depth if it is the largest seen so far. */
|
cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
|
cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
|
|
|
if (loop->pred)
|
if (loop->pred)
|
free (loop->pred);
|
free (loop->pred);
|
loop->pred = XNEWVEC (struct loop *, loop->depth);
|
loop->pred = XNEWVEC (struct loop *, loop->depth);
|
memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
|
memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
|
loop->pred[father->depth] = father;
|
loop->pred[father->depth] = father;
|
|
|
for (ploop = loop->inner; ploop; ploop = ploop->next)
|
for (ploop = loop->inner; ploop; ploop = ploop->next)
|
establish_preds (ploop);
|
establish_preds (ploop);
|
}
|
}
|
|
|
/* Add LOOP to the loop hierarchy tree where FATHER is father of the
|
/* Add LOOP to the loop hierarchy tree where FATHER is father of the
|
added loop. If LOOP has some children, take care of that their
|
added loop. If LOOP has some children, take care of that their
|
pred field will be initialized correctly. */
|
pred field will be initialized correctly. */
|
|
|
void
|
void
|
flow_loop_tree_node_add (struct loop *father, struct loop *loop)
|
flow_loop_tree_node_add (struct loop *father, struct loop *loop)
|
{
|
{
|
loop->next = father->inner;
|
loop->next = father->inner;
|
father->inner = loop;
|
father->inner = loop;
|
loop->outer = father;
|
loop->outer = father;
|
|
|
establish_preds (loop);
|
establish_preds (loop);
|
}
|
}
|
|
|
/* Remove LOOP from the loop hierarchy tree. */
|
/* Remove LOOP from the loop hierarchy tree. */
|
|
|
void
|
void
|
flow_loop_tree_node_remove (struct loop *loop)
|
flow_loop_tree_node_remove (struct loop *loop)
|
{
|
{
|
struct loop *prev, *father;
|
struct loop *prev, *father;
|
|
|
father = loop->outer;
|
father = loop->outer;
|
loop->outer = NULL;
|
loop->outer = NULL;
|
|
|
/* Remove loop from the list of sons. */
|
/* Remove loop from the list of sons. */
|
if (father->inner == loop)
|
if (father->inner == loop)
|
father->inner = loop->next;
|
father->inner = loop->next;
|
else
|
else
|
{
|
{
|
for (prev = father->inner; prev->next != loop; prev = prev->next);
|
for (prev = father->inner; prev->next != loop; prev = prev->next);
|
prev->next = loop->next;
|
prev->next = loop->next;
|
}
|
}
|
|
|
loop->depth = -1;
|
loop->depth = -1;
|
free (loop->pred);
|
free (loop->pred);
|
loop->pred = NULL;
|
loop->pred = NULL;
|
}
|
}
|
|
|
/* Helper function to compute loop nesting depth and enclosed loop level
|
/* Helper function to compute loop nesting depth and enclosed loop level
|
for the natural loop specified by LOOP. Returns the loop level. */
|
for the natural loop specified by LOOP. Returns the loop level. */
|
|
|
static int
|
static int
|
flow_loop_level_compute (struct loop *loop)
|
flow_loop_level_compute (struct loop *loop)
|
{
|
{
|
struct loop *inner;
|
struct loop *inner;
|
int level = 1;
|
int level = 1;
|
|
|
if (! loop)
|
if (! loop)
|
return 0;
|
return 0;
|
|
|
/* Traverse loop tree assigning depth and computing level as the
|
/* Traverse loop tree assigning depth and computing level as the
|
maximum level of all the inner loops of this loop. The loop
|
maximum level of all the inner loops of this loop. The loop
|
level is equivalent to the height of the loop in the loop tree
|
level is equivalent to the height of the loop in the loop tree
|
and corresponds to the number of enclosed loop levels (including
|
and corresponds to the number of enclosed loop levels (including
|
itself). */
|
itself). */
|
for (inner = loop->inner; inner; inner = inner->next)
|
for (inner = loop->inner; inner; inner = inner->next)
|
{
|
{
|
int ilevel = flow_loop_level_compute (inner) + 1;
|
int ilevel = flow_loop_level_compute (inner) + 1;
|
|
|
if (ilevel > level)
|
if (ilevel > level)
|
level = ilevel;
|
level = ilevel;
|
}
|
}
|
|
|
loop->level = level;
|
loop->level = level;
|
return level;
|
return level;
|
}
|
}
|
|
|
/* Compute the loop nesting depth and enclosed loop level for the loop
|
/* Compute the loop nesting depth and enclosed loop level for the loop
|
hierarchy tree specified by LOOPS. Return the maximum enclosed loop
|
hierarchy tree specified by LOOPS. Return the maximum enclosed loop
|
level. */
|
level. */
|
|
|
static void
|
static void
|
flow_loops_level_compute (struct loops *loops)
|
flow_loops_level_compute (struct loops *loops)
|
{
|
{
|
flow_loop_level_compute (loops->tree_root);
|
flow_loop_level_compute (loops->tree_root);
|
}
|
}
|
|
|
/* A callback to update latch and header info for basic block JUMP created
|
/* A callback to update latch and header info for basic block JUMP created
|
by redirecting an edge. */
|
by redirecting an edge. */
|
|
|
static void
|
static void
|
update_latch_info (basic_block jump)
|
update_latch_info (basic_block jump)
|
{
|
{
|
alloc_aux_for_block (jump, sizeof (int));
|
alloc_aux_for_block (jump, sizeof (int));
|
HEADER_BLOCK (jump) = 0;
|
HEADER_BLOCK (jump) = 0;
|
alloc_aux_for_edge (single_pred_edge (jump), sizeof (int));
|
alloc_aux_for_edge (single_pred_edge (jump), sizeof (int));
|
LATCH_EDGE (single_pred_edge (jump)) = 0;
|
LATCH_EDGE (single_pred_edge (jump)) = 0;
|
set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump));
|
set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump));
|
}
|
}
|
|
|
/* A callback for make_forwarder block, to redirect all edges except for
|
/* A callback for make_forwarder block, to redirect all edges except for
|
MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
|
MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
|
whether to redirect it. */
|
whether to redirect it. */
|
|
|
static edge mfb_kj_edge;
|
static edge mfb_kj_edge;
|
static bool
|
static bool
|
mfb_keep_just (edge e)
|
mfb_keep_just (edge e)
|
{
|
{
|
return e != mfb_kj_edge;
|
return e != mfb_kj_edge;
|
}
|
}
|
|
|
/* A callback for make_forwarder block, to redirect the latch edges into an
|
/* A callback for make_forwarder block, to redirect the latch edges into an
|
entry part. E is the edge for that we should decide whether to redirect
|
entry part. E is the edge for that we should decide whether to redirect
|
it. */
|
it. */
|
|
|
static bool
|
static bool
|
mfb_keep_nonlatch (edge e)
|
mfb_keep_nonlatch (edge e)
|
{
|
{
|
return LATCH_EDGE (e);
|
return LATCH_EDGE (e);
|
}
|
}
|
|
|
/* Takes care of merging natural loops with shared headers. */
|
/* Takes care of merging natural loops with shared headers. */
|
|
|
static void
|
static void
|
canonicalize_loop_headers (void)
|
canonicalize_loop_headers (void)
|
{
|
{
|
basic_block header;
|
basic_block header;
|
edge e;
|
edge e;
|
|
|
alloc_aux_for_blocks (sizeof (int));
|
alloc_aux_for_blocks (sizeof (int));
|
alloc_aux_for_edges (sizeof (int));
|
alloc_aux_for_edges (sizeof (int));
|
|
|
/* Split blocks so that each loop has only single latch. */
|
/* Split blocks so that each loop has only single latch. */
|
FOR_EACH_BB (header)
|
FOR_EACH_BB (header)
|
{
|
{
|
edge_iterator ei;
|
edge_iterator ei;
|
int num_latches = 0;
|
int num_latches = 0;
|
int have_abnormal_edge = 0;
|
int have_abnormal_edge = 0;
|
|
|
FOR_EACH_EDGE (e, ei, header->preds)
|
FOR_EACH_EDGE (e, ei, header->preds)
|
{
|
{
|
basic_block latch = e->src;
|
basic_block latch = e->src;
|
|
|
if (e->flags & EDGE_ABNORMAL)
|
if (e->flags & EDGE_ABNORMAL)
|
have_abnormal_edge = 1;
|
have_abnormal_edge = 1;
|
|
|
if (latch != ENTRY_BLOCK_PTR
|
if (latch != ENTRY_BLOCK_PTR
|
&& dominated_by_p (CDI_DOMINATORS, latch, header))
|
&& dominated_by_p (CDI_DOMINATORS, latch, header))
|
{
|
{
|
num_latches++;
|
num_latches++;
|
LATCH_EDGE (e) = 1;
|
LATCH_EDGE (e) = 1;
|
}
|
}
|
}
|
}
|
if (have_abnormal_edge)
|
if (have_abnormal_edge)
|
HEADER_BLOCK (header) = 0;
|
HEADER_BLOCK (header) = 0;
|
else
|
else
|
HEADER_BLOCK (header) = num_latches;
|
HEADER_BLOCK (header) = num_latches;
|
}
|
}
|
|
|
if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR)))
|
if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR)))
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
|
|
/* We could not redirect edges freely here. On the other hand,
|
/* We could not redirect edges freely here. On the other hand,
|
we can simply split the edge from entry block. */
|
we can simply split the edge from entry block. */
|
bb = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
|
bb = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
|
|
|
alloc_aux_for_edge (single_succ_edge (bb), sizeof (int));
|
alloc_aux_for_edge (single_succ_edge (bb), sizeof (int));
|
LATCH_EDGE (single_succ_edge (bb)) = 0;
|
LATCH_EDGE (single_succ_edge (bb)) = 0;
|
alloc_aux_for_block (bb, sizeof (int));
|
alloc_aux_for_block (bb, sizeof (int));
|
HEADER_BLOCK (bb) = 0;
|
HEADER_BLOCK (bb) = 0;
|
}
|
}
|
|
|
FOR_EACH_BB (header)
|
FOR_EACH_BB (header)
|
{
|
{
|
int max_freq, is_heavy;
|
int max_freq, is_heavy;
|
edge heavy, tmp_edge;
|
edge heavy, tmp_edge;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
if (HEADER_BLOCK (header) <= 1)
|
if (HEADER_BLOCK (header) <= 1)
|
continue;
|
continue;
|
|
|
/* Find a heavy edge. */
|
/* Find a heavy edge. */
|
is_heavy = 1;
|
is_heavy = 1;
|
heavy = NULL;
|
heavy = NULL;
|
max_freq = 0;
|
max_freq = 0;
|
FOR_EACH_EDGE (e, ei, header->preds)
|
FOR_EACH_EDGE (e, ei, header->preds)
|
if (LATCH_EDGE (e) &&
|
if (LATCH_EDGE (e) &&
|
EDGE_FREQUENCY (e) > max_freq)
|
EDGE_FREQUENCY (e) > max_freq)
|
max_freq = EDGE_FREQUENCY (e);
|
max_freq = EDGE_FREQUENCY (e);
|
FOR_EACH_EDGE (e, ei, header->preds)
|
FOR_EACH_EDGE (e, ei, header->preds)
|
if (LATCH_EDGE (e) &&
|
if (LATCH_EDGE (e) &&
|
EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
|
EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
|
{
|
{
|
if (heavy)
|
if (heavy)
|
{
|
{
|
is_heavy = 0;
|
is_heavy = 0;
|
break;
|
break;
|
}
|
}
|
else
|
else
|
heavy = e;
|
heavy = e;
|
}
|
}
|
|
|
if (is_heavy)
|
if (is_heavy)
|
{
|
{
|
/* Split out the heavy edge, and create inner loop for it. */
|
/* Split out the heavy edge, and create inner loop for it. */
|
mfb_kj_edge = heavy;
|
mfb_kj_edge = heavy;
|
tmp_edge = make_forwarder_block (header, mfb_keep_just,
|
tmp_edge = make_forwarder_block (header, mfb_keep_just,
|
update_latch_info);
|
update_latch_info);
|
alloc_aux_for_block (tmp_edge->dest, sizeof (int));
|
alloc_aux_for_block (tmp_edge->dest, sizeof (int));
|
HEADER_BLOCK (tmp_edge->dest) = 1;
|
HEADER_BLOCK (tmp_edge->dest) = 1;
|
alloc_aux_for_edge (tmp_edge, sizeof (int));
|
alloc_aux_for_edge (tmp_edge, sizeof (int));
|
LATCH_EDGE (tmp_edge) = 0;
|
LATCH_EDGE (tmp_edge) = 0;
|
HEADER_BLOCK (header)--;
|
HEADER_BLOCK (header)--;
|
}
|
}
|
|
|
if (HEADER_BLOCK (header) > 1)
|
if (HEADER_BLOCK (header) > 1)
|
{
|
{
|
/* Create a new latch block. */
|
/* Create a new latch block. */
|
tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
|
tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
|
update_latch_info);
|
update_latch_info);
|
alloc_aux_for_block (tmp_edge->dest, sizeof (int));
|
alloc_aux_for_block (tmp_edge->dest, sizeof (int));
|
HEADER_BLOCK (tmp_edge->src) = 0;
|
HEADER_BLOCK (tmp_edge->src) = 0;
|
HEADER_BLOCK (tmp_edge->dest) = 1;
|
HEADER_BLOCK (tmp_edge->dest) = 1;
|
alloc_aux_for_edge (tmp_edge, sizeof (int));
|
alloc_aux_for_edge (tmp_edge, sizeof (int));
|
LATCH_EDGE (tmp_edge) = 1;
|
LATCH_EDGE (tmp_edge) = 1;
|
}
|
}
|
}
|
}
|
|
|
free_aux_for_blocks ();
|
free_aux_for_blocks ();
|
free_aux_for_edges ();
|
free_aux_for_edges ();
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_dominators (CDI_DOMINATORS);
|
verify_dominators (CDI_DOMINATORS);
|
#endif
|
#endif
|
}
|
}
|
|
|
/* Initialize all the parallel_p fields of the loops structure to true. */
|
/* Initialize all the parallel_p fields of the loops structure to true. */
|
|
|
static void
|
static void
|
initialize_loops_parallel_p (struct loops *loops)
|
initialize_loops_parallel_p (struct loops *loops)
|
{
|
{
|
unsigned int i;
|
unsigned int i;
|
|
|
for (i = 0; i < loops->num; i++)
|
for (i = 0; i < loops->num; i++)
|
{
|
{
|
struct loop *loop = loops->parray[i];
|
struct loop *loop = loops->parray[i];
|
loop->parallel_p = true;
|
loop->parallel_p = true;
|
}
|
}
|
}
|
}
|
|
|
/* Find all the natural loops in the function and save in LOOPS structure and
|
/* Find all the natural loops in the function and save in LOOPS structure and
|
recalculate loop_depth information in basic block structures.
|
recalculate loop_depth information in basic block structures.
|
Return the number of natural loops found. */
|
Return the number of natural loops found. */
|
|
|
int
|
int
|
flow_loops_find (struct loops *loops)
|
flow_loops_find (struct loops *loops)
|
{
|
{
|
int b;
|
int b;
|
int num_loops;
|
int num_loops;
|
edge e;
|
edge e;
|
sbitmap headers;
|
sbitmap headers;
|
int *dfs_order;
|
int *dfs_order;
|
int *rc_order;
|
int *rc_order;
|
basic_block header;
|
basic_block header;
|
basic_block bb;
|
basic_block bb;
|
|
|
memset (loops, 0, sizeof *loops);
|
memset (loops, 0, sizeof *loops);
|
|
|
/* We are going to recount the maximum loop depth,
|
/* We are going to recount the maximum loop depth,
|
so throw away the last count. */
|
so throw away the last count. */
|
cfun->max_loop_depth = 0;
|
cfun->max_loop_depth = 0;
|
|
|
/* Taking care of this degenerate case makes the rest of
|
/* Taking care of this degenerate case makes the rest of
|
this code simpler. */
|
this code simpler. */
|
if (n_basic_blocks == NUM_FIXED_BLOCKS)
|
if (n_basic_blocks == NUM_FIXED_BLOCKS)
|
return 0;
|
return 0;
|
|
|
dfs_order = NULL;
|
dfs_order = NULL;
|
rc_order = NULL;
|
rc_order = NULL;
|
|
|
/* Ensure that the dominators are computed. */
|
/* Ensure that the dominators are computed. */
|
calculate_dominance_info (CDI_DOMINATORS);
|
calculate_dominance_info (CDI_DOMINATORS);
|
|
|
/* Join loops with shared headers. */
|
/* Join loops with shared headers. */
|
canonicalize_loop_headers ();
|
canonicalize_loop_headers ();
|
|
|
/* Count the number of loop headers. This should be the
|
/* Count the number of loop headers. This should be the
|
same as the number of natural loops. */
|
same as the number of natural loops. */
|
headers = sbitmap_alloc (last_basic_block);
|
headers = sbitmap_alloc (last_basic_block);
|
sbitmap_zero (headers);
|
sbitmap_zero (headers);
|
|
|
num_loops = 0;
|
num_loops = 0;
|
FOR_EACH_BB (header)
|
FOR_EACH_BB (header)
|
{
|
{
|
edge_iterator ei;
|
edge_iterator ei;
|
int more_latches = 0;
|
int more_latches = 0;
|
|
|
header->loop_depth = 0;
|
header->loop_depth = 0;
|
|
|
/* If we have an abnormal predecessor, do not consider the
|
/* If we have an abnormal predecessor, do not consider the
|
loop (not worth the problems). */
|
loop (not worth the problems). */
|
FOR_EACH_EDGE (e, ei, header->preds)
|
FOR_EACH_EDGE (e, ei, header->preds)
|
if (e->flags & EDGE_ABNORMAL)
|
if (e->flags & EDGE_ABNORMAL)
|
break;
|
break;
|
if (e)
|
if (e)
|
continue;
|
continue;
|
|
|
FOR_EACH_EDGE (e, ei, header->preds)
|
FOR_EACH_EDGE (e, ei, header->preds)
|
{
|
{
|
basic_block latch = e->src;
|
basic_block latch = e->src;
|
|
|
gcc_assert (!(e->flags & EDGE_ABNORMAL));
|
gcc_assert (!(e->flags & EDGE_ABNORMAL));
|
|
|
/* Look for back edges where a predecessor is dominated
|
/* Look for back edges where a predecessor is dominated
|
by this block. A natural loop has a single entry
|
by this block. A natural loop has a single entry
|
node (header) that dominates all the nodes in the
|
node (header) that dominates all the nodes in the
|
loop. It also has single back edge to the header
|
loop. It also has single back edge to the header
|
from a latch node. */
|
from a latch node. */
|
if (latch != ENTRY_BLOCK_PTR
|
if (latch != ENTRY_BLOCK_PTR
|
&& dominated_by_p (CDI_DOMINATORS, latch, header))
|
&& dominated_by_p (CDI_DOMINATORS, latch, header))
|
{
|
{
|
/* Shared headers should be eliminated by now. */
|
/* Shared headers should be eliminated by now. */
|
gcc_assert (!more_latches);
|
gcc_assert (!more_latches);
|
more_latches = 1;
|
more_latches = 1;
|
SET_BIT (headers, header->index);
|
SET_BIT (headers, header->index);
|
num_loops++;
|
num_loops++;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Allocate loop structures. */
|
/* Allocate loop structures. */
|
loops->parray = XCNEWVEC (struct loop *, num_loops + 1);
|
loops->parray = XCNEWVEC (struct loop *, num_loops + 1);
|
|
|
/* Dummy loop containing whole function. */
|
/* Dummy loop containing whole function. */
|
loops->parray[0] = XCNEW (struct loop);
|
loops->parray[0] = XCNEW (struct loop);
|
loops->parray[0]->next = NULL;
|
loops->parray[0]->next = NULL;
|
loops->parray[0]->inner = NULL;
|
loops->parray[0]->inner = NULL;
|
loops->parray[0]->outer = NULL;
|
loops->parray[0]->outer = NULL;
|
loops->parray[0]->depth = 0;
|
loops->parray[0]->depth = 0;
|
loops->parray[0]->pred = NULL;
|
loops->parray[0]->pred = NULL;
|
loops->parray[0]->num_nodes = n_basic_blocks;
|
loops->parray[0]->num_nodes = n_basic_blocks;
|
loops->parray[0]->latch = EXIT_BLOCK_PTR;
|
loops->parray[0]->latch = EXIT_BLOCK_PTR;
|
loops->parray[0]->header = ENTRY_BLOCK_PTR;
|
loops->parray[0]->header = ENTRY_BLOCK_PTR;
|
ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
|
ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
|
EXIT_BLOCK_PTR->loop_father = loops->parray[0];
|
EXIT_BLOCK_PTR->loop_father = loops->parray[0];
|
|
|
loops->tree_root = loops->parray[0];
|
loops->tree_root = loops->parray[0];
|
|
|
/* Find and record information about all the natural loops
|
/* Find and record information about all the natural loops
|
in the CFG. */
|
in the CFG. */
|
loops->num = 1;
|
loops->num = 1;
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
bb->loop_father = loops->tree_root;
|
bb->loop_father = loops->tree_root;
|
|
|
if (num_loops)
|
if (num_loops)
|
{
|
{
|
/* Compute depth first search order of the CFG so that outer
|
/* Compute depth first search order of the CFG so that outer
|
natural loops will be found before inner natural loops. */
|
natural loops will be found before inner natural loops. */
|
dfs_order = XNEWVEC (int, n_basic_blocks);
|
dfs_order = XNEWVEC (int, n_basic_blocks);
|
rc_order = XNEWVEC (int, n_basic_blocks);
|
rc_order = XNEWVEC (int, n_basic_blocks);
|
pre_and_rev_post_order_compute (dfs_order, rc_order, false);
|
pre_and_rev_post_order_compute (dfs_order, rc_order, false);
|
|
|
/* Save CFG derived information to avoid recomputing it. */
|
/* Save CFG derived information to avoid recomputing it. */
|
loops->cfg.dfs_order = dfs_order;
|
loops->cfg.dfs_order = dfs_order;
|
loops->cfg.rc_order = rc_order;
|
loops->cfg.rc_order = rc_order;
|
|
|
num_loops = 1;
|
num_loops = 1;
|
|
|
for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
|
for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
|
{
|
{
|
struct loop *loop;
|
struct loop *loop;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
/* Search the nodes of the CFG in reverse completion order
|
/* Search the nodes of the CFG in reverse completion order
|
so that we can find outer loops first. */
|
so that we can find outer loops first. */
|
if (!TEST_BIT (headers, rc_order[b]))
|
if (!TEST_BIT (headers, rc_order[b]))
|
continue;
|
continue;
|
|
|
header = BASIC_BLOCK (rc_order[b]);
|
header = BASIC_BLOCK (rc_order[b]);
|
|
|
loop = loops->parray[num_loops] = XCNEW (struct loop);
|
loop = loops->parray[num_loops] = XCNEW (struct loop);
|
|
|
loop->header = header;
|
loop->header = header;
|
loop->num = num_loops;
|
loop->num = num_loops;
|
num_loops++;
|
num_loops++;
|
|
|
/* Look for the latch for this header block. */
|
/* Look for the latch for this header block. */
|
FOR_EACH_EDGE (e, ei, header->preds)
|
FOR_EACH_EDGE (e, ei, header->preds)
|
{
|
{
|
basic_block latch = e->src;
|
basic_block latch = e->src;
|
|
|
if (latch != ENTRY_BLOCK_PTR
|
if (latch != ENTRY_BLOCK_PTR
|
&& dominated_by_p (CDI_DOMINATORS, latch, header))
|
&& dominated_by_p (CDI_DOMINATORS, latch, header))
|
{
|
{
|
loop->latch = latch;
|
loop->latch = latch;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
flow_loop_tree_node_add (header->loop_father, loop);
|
flow_loop_tree_node_add (header->loop_father, loop);
|
loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
|
loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
|
}
|
}
|
|
|
/* Assign the loop nesting depth and enclosed loop level for each
|
/* Assign the loop nesting depth and enclosed loop level for each
|
loop. */
|
loop. */
|
flow_loops_level_compute (loops);
|
flow_loops_level_compute (loops);
|
|
|
loops->num = num_loops;
|
loops->num = num_loops;
|
initialize_loops_parallel_p (loops);
|
initialize_loops_parallel_p (loops);
|
}
|
}
|
|
|
sbitmap_free (headers);
|
sbitmap_free (headers);
|
|
|
loops->state = 0;
|
loops->state = 0;
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_flow_info ();
|
verify_flow_info ();
|
verify_loop_structure (loops);
|
verify_loop_structure (loops);
|
#endif
|
#endif
|
|
|
return loops->num;
|
return loops->num;
|
}
|
}
|
|
|
/* Return nonzero if basic block BB belongs to LOOP. */
|
/* Return nonzero if basic block BB belongs to LOOP. */
|
bool
|
bool
|
flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
|
flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
|
{
|
{
|
struct loop *source_loop;
|
struct loop *source_loop;
|
|
|
if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
|
if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
|
return 0;
|
return 0;
|
|
|
source_loop = bb->loop_father;
|
source_loop = bb->loop_father;
|
return loop == source_loop || flow_loop_nested_p (loop, source_loop);
|
return loop == source_loop || flow_loop_nested_p (loop, source_loop);
|
}
|
}
|
|
|
/* Enumeration predicate for get_loop_body. */
|
/* Enumeration predicate for get_loop_body. */
|
static bool
|
static bool
|
glb_enum_p (basic_block bb, void *glb_header)
|
glb_enum_p (basic_block bb, void *glb_header)
|
{
|
{
|
return bb != (basic_block) glb_header;
|
return bb != (basic_block) glb_header;
|
}
|
}
|
|
|
/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
|
/* 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
|
order against direction of edges from latch. Specially, if
|
header != latch, latch is the 1-st block. */
|
header != latch, latch is the 1-st block. */
|
basic_block *
|
basic_block *
|
get_loop_body (const struct loop *loop)
|
get_loop_body (const struct loop *loop)
|
{
|
{
|
basic_block *tovisit, bb;
|
basic_block *tovisit, bb;
|
unsigned tv = 0;
|
unsigned tv = 0;
|
|
|
gcc_assert (loop->num_nodes);
|
gcc_assert (loop->num_nodes);
|
|
|
tovisit = XCNEWVEC (basic_block, loop->num_nodes);
|
tovisit = XCNEWVEC (basic_block, loop->num_nodes);
|
tovisit[tv++] = loop->header;
|
tovisit[tv++] = loop->header;
|
|
|
if (loop->latch == EXIT_BLOCK_PTR)
|
if (loop->latch == EXIT_BLOCK_PTR)
|
{
|
{
|
/* There may be blocks unreachable from EXIT_BLOCK. */
|
/* There may be blocks unreachable from EXIT_BLOCK. */
|
gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
|
gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
tovisit[tv++] = bb;
|
tovisit[tv++] = bb;
|
tovisit[tv++] = EXIT_BLOCK_PTR;
|
tovisit[tv++] = EXIT_BLOCK_PTR;
|
}
|
}
|
else if (loop->latch != loop->header)
|
else if (loop->latch != loop->header)
|
{
|
{
|
tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
|
tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
|
tovisit + 1, loop->num_nodes - 1,
|
tovisit + 1, loop->num_nodes - 1,
|
loop->header) + 1;
|
loop->header) + 1;
|
}
|
}
|
|
|
gcc_assert (tv == loop->num_nodes);
|
gcc_assert (tv == loop->num_nodes);
|
return tovisit;
|
return tovisit;
|
}
|
}
|
|
|
/* Fills dominance descendants inside LOOP of the basic block BB into
|
/* Fills dominance descendants inside LOOP of the basic block BB into
|
array TOVISIT from index *TV. */
|
array TOVISIT from index *TV. */
|
|
|
static void
|
static void
|
fill_sons_in_loop (const struct loop *loop, basic_block bb,
|
fill_sons_in_loop (const struct loop *loop, basic_block bb,
|
basic_block *tovisit, int *tv)
|
basic_block *tovisit, int *tv)
|
{
|
{
|
basic_block son, postpone = NULL;
|
basic_block son, postpone = NULL;
|
|
|
tovisit[(*tv)++] = bb;
|
tovisit[(*tv)++] = bb;
|
for (son = first_dom_son (CDI_DOMINATORS, bb);
|
for (son = first_dom_son (CDI_DOMINATORS, bb);
|
son;
|
son;
|
son = next_dom_son (CDI_DOMINATORS, son))
|
son = next_dom_son (CDI_DOMINATORS, son))
|
{
|
{
|
if (!flow_bb_inside_loop_p (loop, son))
|
if (!flow_bb_inside_loop_p (loop, son))
|
continue;
|
continue;
|
|
|
if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
|
if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
|
{
|
{
|
postpone = son;
|
postpone = son;
|
continue;
|
continue;
|
}
|
}
|
fill_sons_in_loop (loop, son, tovisit, tv);
|
fill_sons_in_loop (loop, son, tovisit, tv);
|
}
|
}
|
|
|
if (postpone)
|
if (postpone)
|
fill_sons_in_loop (loop, postpone, tovisit, tv);
|
fill_sons_in_loop (loop, postpone, tovisit, tv);
|
}
|
}
|
|
|
/* Gets body of a LOOP (that must be different from the outermost loop)
|
/* Gets body of a LOOP (that must be different from the outermost loop)
|
sorted by dominance relation. Additionally, if a basic block s dominates
|
sorted by dominance relation. Additionally, if a basic block s dominates
|
the latch, then only blocks dominated by s are be after it. */
|
the latch, then only blocks dominated by s are be after it. */
|
|
|
basic_block *
|
basic_block *
|
get_loop_body_in_dom_order (const struct loop *loop)
|
get_loop_body_in_dom_order (const struct loop *loop)
|
{
|
{
|
basic_block *tovisit;
|
basic_block *tovisit;
|
int tv;
|
int tv;
|
|
|
gcc_assert (loop->num_nodes);
|
gcc_assert (loop->num_nodes);
|
|
|
tovisit = XCNEWVEC (basic_block, loop->num_nodes);
|
tovisit = XCNEWVEC (basic_block, loop->num_nodes);
|
|
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
|
|
tv = 0;
|
tv = 0;
|
fill_sons_in_loop (loop, loop->header, tovisit, &tv);
|
fill_sons_in_loop (loop, loop->header, tovisit, &tv);
|
|
|
gcc_assert (tv == (int) loop->num_nodes);
|
gcc_assert (tv == (int) loop->num_nodes);
|
|
|
return tovisit;
|
return tovisit;
|
}
|
}
|
|
|
/* Get body of a LOOP in breadth first sort order. */
|
/* Get body of a LOOP in breadth first sort order. */
|
|
|
basic_block *
|
basic_block *
|
get_loop_body_in_bfs_order (const struct loop *loop)
|
get_loop_body_in_bfs_order (const struct loop *loop)
|
{
|
{
|
basic_block *blocks;
|
basic_block *blocks;
|
basic_block bb;
|
basic_block bb;
|
bitmap visited;
|
bitmap visited;
|
unsigned int i = 0;
|
unsigned int i = 0;
|
unsigned int vc = 1;
|
unsigned int vc = 1;
|
|
|
gcc_assert (loop->num_nodes);
|
gcc_assert (loop->num_nodes);
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
|
|
blocks = XCNEWVEC (basic_block, loop->num_nodes);
|
blocks = XCNEWVEC (basic_block, loop->num_nodes);
|
visited = BITMAP_ALLOC (NULL);
|
visited = BITMAP_ALLOC (NULL);
|
|
|
bb = loop->header;
|
bb = loop->header;
|
while (i < loop->num_nodes)
|
while (i < loop->num_nodes)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
if (!bitmap_bit_p (visited, bb->index))
|
if (!bitmap_bit_p (visited, bb->index))
|
{
|
{
|
/* This basic block is now visited */
|
/* This basic block is now visited */
|
bitmap_set_bit (visited, bb->index);
|
bitmap_set_bit (visited, bb->index);
|
blocks[i++] = bb;
|
blocks[i++] = bb;
|
}
|
}
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
{
|
{
|
if (flow_bb_inside_loop_p (loop, e->dest))
|
if (flow_bb_inside_loop_p (loop, e->dest))
|
{
|
{
|
if (!bitmap_bit_p (visited, e->dest->index))
|
if (!bitmap_bit_p (visited, e->dest->index))
|
{
|
{
|
bitmap_set_bit (visited, e->dest->index);
|
bitmap_set_bit (visited, e->dest->index);
|
blocks[i++] = e->dest;
|
blocks[i++] = e->dest;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
gcc_assert (i >= vc);
|
gcc_assert (i >= vc);
|
|
|
bb = blocks[vc++];
|
bb = blocks[vc++];
|
}
|
}
|
|
|
BITMAP_FREE (visited);
|
BITMAP_FREE (visited);
|
return blocks;
|
return blocks;
|
}
|
}
|
|
|
/* Gets exit edges of a LOOP, returning their number in N_EDGES. */
|
/* Gets exit edges of a LOOP, returning their number in N_EDGES. */
|
edge *
|
edge *
|
get_loop_exit_edges (const struct loop *loop, unsigned int *num_edges)
|
get_loop_exit_edges (const struct loop *loop, unsigned int *num_edges)
|
{
|
{
|
edge *edges, e;
|
edge *edges, e;
|
unsigned i, n;
|
unsigned i, n;
|
basic_block * body;
|
basic_block * body;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
|
|
body = get_loop_body (loop);
|
body = get_loop_body (loop);
|
n = 0;
|
n = 0;
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
FOR_EACH_EDGE (e, ei, body[i]->succs)
|
FOR_EACH_EDGE (e, ei, body[i]->succs)
|
if (!flow_bb_inside_loop_p (loop, e->dest))
|
if (!flow_bb_inside_loop_p (loop, e->dest))
|
n++;
|
n++;
|
edges = XNEWVEC (edge, n);
|
edges = XNEWVEC (edge, n);
|
*num_edges = n;
|
*num_edges = n;
|
n = 0;
|
n = 0;
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
FOR_EACH_EDGE (e, ei, body[i]->succs)
|
FOR_EACH_EDGE (e, ei, body[i]->succs)
|
if (!flow_bb_inside_loop_p (loop, e->dest))
|
if (!flow_bb_inside_loop_p (loop, e->dest))
|
edges[n++] = e;
|
edges[n++] = e;
|
free (body);
|
free (body);
|
|
|
return edges;
|
return edges;
|
}
|
}
|
|
|
/* Counts the number of conditional branches inside LOOP. */
|
/* Counts the number of conditional branches inside LOOP. */
|
|
|
unsigned
|
unsigned
|
num_loop_branches (const struct loop *loop)
|
num_loop_branches (const struct loop *loop)
|
{
|
{
|
unsigned i, n;
|
unsigned i, n;
|
basic_block * body;
|
basic_block * body;
|
|
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
|
|
body = get_loop_body (loop);
|
body = get_loop_body (loop);
|
n = 0;
|
n = 0;
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
if (EDGE_COUNT (body[i]->succs) >= 2)
|
if (EDGE_COUNT (body[i]->succs) >= 2)
|
n++;
|
n++;
|
free (body);
|
free (body);
|
|
|
return n;
|
return n;
|
}
|
}
|
|
|
/* Adds basic block BB to LOOP. */
|
/* Adds basic block BB to LOOP. */
|
void
|
void
|
add_bb_to_loop (basic_block bb, struct loop *loop)
|
add_bb_to_loop (basic_block bb, struct loop *loop)
|
{
|
{
|
int i;
|
int i;
|
|
|
bb->loop_father = loop;
|
bb->loop_father = loop;
|
bb->loop_depth = loop->depth;
|
bb->loop_depth = loop->depth;
|
loop->num_nodes++;
|
loop->num_nodes++;
|
for (i = 0; i < loop->depth; i++)
|
for (i = 0; i < loop->depth; i++)
|
loop->pred[i]->num_nodes++;
|
loop->pred[i]->num_nodes++;
|
}
|
}
|
|
|
/* Remove basic block BB from loops. */
|
/* Remove basic block BB from loops. */
|
void
|
void
|
remove_bb_from_loops (basic_block bb)
|
remove_bb_from_loops (basic_block bb)
|
{
|
{
|
int i;
|
int i;
|
struct loop *loop = bb->loop_father;
|
struct loop *loop = bb->loop_father;
|
|
|
loop->num_nodes--;
|
loop->num_nodes--;
|
for (i = 0; i < loop->depth; i++)
|
for (i = 0; i < loop->depth; i++)
|
loop->pred[i]->num_nodes--;
|
loop->pred[i]->num_nodes--;
|
bb->loop_father = NULL;
|
bb->loop_father = NULL;
|
bb->loop_depth = 0;
|
bb->loop_depth = 0;
|
}
|
}
|
|
|
/* Finds nearest common ancestor in loop tree for given loops. */
|
/* Finds nearest common ancestor in loop tree for given loops. */
|
struct loop *
|
struct loop *
|
find_common_loop (struct loop *loop_s, struct loop *loop_d)
|
find_common_loop (struct loop *loop_s, struct loop *loop_d)
|
{
|
{
|
if (!loop_s) return loop_d;
|
if (!loop_s) return loop_d;
|
if (!loop_d) return loop_s;
|
if (!loop_d) return loop_s;
|
|
|
if (loop_s->depth < loop_d->depth)
|
if (loop_s->depth < loop_d->depth)
|
loop_d = loop_d->pred[loop_s->depth];
|
loop_d = loop_d->pred[loop_s->depth];
|
else if (loop_s->depth > loop_d->depth)
|
else if (loop_s->depth > loop_d->depth)
|
loop_s = loop_s->pred[loop_d->depth];
|
loop_s = loop_s->pred[loop_d->depth];
|
|
|
while (loop_s != loop_d)
|
while (loop_s != loop_d)
|
{
|
{
|
loop_s = loop_s->outer;
|
loop_s = loop_s->outer;
|
loop_d = loop_d->outer;
|
loop_d = loop_d->outer;
|
}
|
}
|
return loop_s;
|
return loop_s;
|
}
|
}
|
|
|
/* Cancels the LOOP; it must be innermost one. */
|
/* Cancels the LOOP; it must be innermost one. */
|
|
|
static void
|
static void
|
cancel_loop (struct loops *loops, struct loop *loop)
|
cancel_loop (struct loops *loops, struct loop *loop)
|
{
|
{
|
basic_block *bbs;
|
basic_block *bbs;
|
unsigned i;
|
unsigned i;
|
|
|
gcc_assert (!loop->inner);
|
gcc_assert (!loop->inner);
|
|
|
/* Move blocks up one level (they should be removed as soon as possible). */
|
/* Move blocks up one level (they should be removed as soon as possible). */
|
bbs = get_loop_body (loop);
|
bbs = get_loop_body (loop);
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
bbs[i]->loop_father = loop->outer;
|
bbs[i]->loop_father = loop->outer;
|
|
|
/* Remove the loop from structure. */
|
/* Remove the loop from structure. */
|
flow_loop_tree_node_remove (loop);
|
flow_loop_tree_node_remove (loop);
|
|
|
/* Remove loop from loops array. */
|
/* Remove loop from loops array. */
|
loops->parray[loop->num] = NULL;
|
loops->parray[loop->num] = NULL;
|
|
|
/* Free loop data. */
|
/* Free loop data. */
|
flow_loop_free (loop);
|
flow_loop_free (loop);
|
}
|
}
|
|
|
/* Cancels LOOP and all its subloops. */
|
/* Cancels LOOP and all its subloops. */
|
void
|
void
|
cancel_loop_tree (struct loops *loops, struct loop *loop)
|
cancel_loop_tree (struct loops *loops, struct loop *loop)
|
{
|
{
|
while (loop->inner)
|
while (loop->inner)
|
cancel_loop_tree (loops, loop->inner);
|
cancel_loop_tree (loops, loop->inner);
|
cancel_loop (loops, loop);
|
cancel_loop (loops, loop);
|
}
|
}
|
|
|
/* Checks that LOOPS are all right:
|
/* Checks that LOOPS are all right:
|
-- sizes of loops are all right
|
-- sizes of loops are all right
|
-- results of get_loop_body really belong to the loop
|
-- results of get_loop_body really belong to the loop
|
-- loop header have just single entry edge and single latch edge
|
-- loop header have just single entry edge and single latch edge
|
-- loop latches have only single successor that is header of their loop
|
-- loop latches have only single successor that is header of their loop
|
-- irreducible loops are correctly marked
|
-- irreducible loops are correctly marked
|
*/
|
*/
|
void
|
void
|
verify_loop_structure (struct loops *loops)
|
verify_loop_structure (struct loops *loops)
|
{
|
{
|
unsigned *sizes, i, j;
|
unsigned *sizes, i, j;
|
sbitmap irreds;
|
sbitmap irreds;
|
basic_block *bbs, bb;
|
basic_block *bbs, bb;
|
struct loop *loop;
|
struct loop *loop;
|
int err = 0;
|
int err = 0;
|
edge e;
|
edge e;
|
|
|
/* Check sizes. */
|
/* Check sizes. */
|
sizes = XCNEWVEC (unsigned, loops->num);
|
sizes = XCNEWVEC (unsigned, loops->num);
|
sizes[0] = 2;
|
sizes[0] = 2;
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
for (loop = bb->loop_father; loop; loop = loop->outer)
|
for (loop = bb->loop_father; loop; loop = loop->outer)
|
sizes[loop->num]++;
|
sizes[loop->num]++;
|
|
|
for (i = 0; i < loops->num; i++)
|
for (i = 0; i < loops->num; i++)
|
{
|
{
|
if (!loops->parray[i])
|
if (!loops->parray[i])
|
continue;
|
continue;
|
|
|
if (loops->parray[i]->num_nodes != sizes[i])
|
if (loops->parray[i]->num_nodes != sizes[i])
|
{
|
{
|
error ("size of loop %d should be %d, not %d",
|
error ("size of loop %d should be %d, not %d",
|
i, sizes[i], loops->parray[i]->num_nodes);
|
i, sizes[i], loops->parray[i]->num_nodes);
|
err = 1;
|
err = 1;
|
}
|
}
|
}
|
}
|
|
|
/* Check get_loop_body. */
|
/* Check get_loop_body. */
|
for (i = 1; i < loops->num; i++)
|
for (i = 1; i < loops->num; i++)
|
{
|
{
|
loop = loops->parray[i];
|
loop = loops->parray[i];
|
if (!loop)
|
if (!loop)
|
continue;
|
continue;
|
bbs = get_loop_body (loop);
|
bbs = get_loop_body (loop);
|
|
|
for (j = 0; j < loop->num_nodes; j++)
|
for (j = 0; j < loop->num_nodes; j++)
|
if (!flow_bb_inside_loop_p (loop, bbs[j]))
|
if (!flow_bb_inside_loop_p (loop, bbs[j]))
|
{
|
{
|
error ("bb %d do not belong to loop %d",
|
error ("bb %d do not belong to loop %d",
|
bbs[j]->index, i);
|
bbs[j]->index, i);
|
err = 1;
|
err = 1;
|
}
|
}
|
free (bbs);
|
free (bbs);
|
}
|
}
|
|
|
/* Check headers and latches. */
|
/* Check headers and latches. */
|
for (i = 1; i < loops->num; i++)
|
for (i = 1; i < loops->num; i++)
|
{
|
{
|
loop = loops->parray[i];
|
loop = loops->parray[i];
|
if (!loop)
|
if (!loop)
|
continue;
|
continue;
|
|
|
if ((loops->state & LOOPS_HAVE_PREHEADERS)
|
if ((loops->state & LOOPS_HAVE_PREHEADERS)
|
&& EDGE_COUNT (loop->header->preds) != 2)
|
&& EDGE_COUNT (loop->header->preds) != 2)
|
{
|
{
|
error ("loop %d's header does not have exactly 2 entries", i);
|
error ("loop %d's header does not have exactly 2 entries", i);
|
err = 1;
|
err = 1;
|
}
|
}
|
if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
|
if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
|
{
|
{
|
if (!single_succ_p (loop->latch))
|
if (!single_succ_p (loop->latch))
|
{
|
{
|
error ("loop %d's latch does not have exactly 1 successor", i);
|
error ("loop %d's latch does not have exactly 1 successor", i);
|
err = 1;
|
err = 1;
|
}
|
}
|
if (single_succ (loop->latch) != loop->header)
|
if (single_succ (loop->latch) != loop->header)
|
{
|
{
|
error ("loop %d's latch does not have header as successor", i);
|
error ("loop %d's latch does not have header as successor", i);
|
err = 1;
|
err = 1;
|
}
|
}
|
if (loop->latch->loop_father != loop)
|
if (loop->latch->loop_father != loop)
|
{
|
{
|
error ("loop %d's latch does not belong directly to it", i);
|
error ("loop %d's latch does not belong directly to it", i);
|
err = 1;
|
err = 1;
|
}
|
}
|
}
|
}
|
if (loop->header->loop_father != loop)
|
if (loop->header->loop_father != loop)
|
{
|
{
|
error ("loop %d's header does not belong directly to it", i);
|
error ("loop %d's header does not belong directly to it", i);
|
err = 1;
|
err = 1;
|
}
|
}
|
if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
|
if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
|
&& (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
|
&& (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
|
{
|
{
|
error ("loop %d's latch is marked as part of irreducible region", i);
|
error ("loop %d's latch is marked as part of irreducible region", i);
|
err = 1;
|
err = 1;
|
}
|
}
|
}
|
}
|
|
|
/* Check irreducible loops. */
|
/* Check irreducible loops. */
|
if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
|
if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
|
{
|
{
|
/* Record old info. */
|
/* Record old info. */
|
irreds = sbitmap_alloc (last_basic_block);
|
irreds = sbitmap_alloc (last_basic_block);
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
edge_iterator ei;
|
edge_iterator ei;
|
if (bb->flags & BB_IRREDUCIBLE_LOOP)
|
if (bb->flags & BB_IRREDUCIBLE_LOOP)
|
SET_BIT (irreds, bb->index);
|
SET_BIT (irreds, bb->index);
|
else
|
else
|
RESET_BIT (irreds, bb->index);
|
RESET_BIT (irreds, bb->index);
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
if (e->flags & EDGE_IRREDUCIBLE_LOOP)
|
if (e->flags & EDGE_IRREDUCIBLE_LOOP)
|
e->flags |= EDGE_ALL_FLAGS + 1;
|
e->flags |= EDGE_ALL_FLAGS + 1;
|
}
|
}
|
|
|
/* Recount it. */
|
/* Recount it. */
|
mark_irreducible_loops (loops);
|
mark_irreducible_loops (loops);
|
|
|
/* Compare. */
|
/* Compare. */
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
if ((bb->flags & BB_IRREDUCIBLE_LOOP)
|
if ((bb->flags & BB_IRREDUCIBLE_LOOP)
|
&& !TEST_BIT (irreds, bb->index))
|
&& !TEST_BIT (irreds, bb->index))
|
{
|
{
|
error ("basic block %d should be marked irreducible", bb->index);
|
error ("basic block %d should be marked irreducible", bb->index);
|
err = 1;
|
err = 1;
|
}
|
}
|
else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
|
else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
|
&& TEST_BIT (irreds, bb->index))
|
&& TEST_BIT (irreds, bb->index))
|
{
|
{
|
error ("basic block %d should not be marked irreducible", bb->index);
|
error ("basic block %d should not be marked irreducible", bb->index);
|
err = 1;
|
err = 1;
|
}
|
}
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
{
|
{
|
if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
|
if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
|
&& !(e->flags & (EDGE_ALL_FLAGS + 1)))
|
&& !(e->flags & (EDGE_ALL_FLAGS + 1)))
|
{
|
{
|
error ("edge from %d to %d should be marked irreducible",
|
error ("edge from %d to %d should be marked irreducible",
|
e->src->index, e->dest->index);
|
e->src->index, e->dest->index);
|
err = 1;
|
err = 1;
|
}
|
}
|
else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
|
else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
|
&& (e->flags & (EDGE_ALL_FLAGS + 1)))
|
&& (e->flags & (EDGE_ALL_FLAGS + 1)))
|
{
|
{
|
error ("edge from %d to %d should not be marked irreducible",
|
error ("edge from %d to %d should not be marked irreducible",
|
e->src->index, e->dest->index);
|
e->src->index, e->dest->index);
|
err = 1;
|
err = 1;
|
}
|
}
|
e->flags &= ~(EDGE_ALL_FLAGS + 1);
|
e->flags &= ~(EDGE_ALL_FLAGS + 1);
|
}
|
}
|
}
|
}
|
free (irreds);
|
free (irreds);
|
}
|
}
|
|
|
/* Check the single_exit. */
|
/* Check the single_exit. */
|
if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
|
if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
|
{
|
{
|
memset (sizes, 0, sizeof (unsigned) * loops->num);
|
memset (sizes, 0, sizeof (unsigned) * loops->num);
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
edge_iterator ei;
|
edge_iterator ei;
|
if (bb->loop_father == loops->tree_root)
|
if (bb->loop_father == loops->tree_root)
|
continue;
|
continue;
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
{
|
{
|
if (e->dest == EXIT_BLOCK_PTR)
|
if (e->dest == EXIT_BLOCK_PTR)
|
continue;
|
continue;
|
|
|
if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
|
if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
|
continue;
|
continue;
|
|
|
for (loop = bb->loop_father;
|
for (loop = bb->loop_father;
|
loop != e->dest->loop_father;
|
loop != e->dest->loop_father;
|
loop = loop->outer)
|
loop = loop->outer)
|
{
|
{
|
sizes[loop->num]++;
|
sizes[loop->num]++;
|
if (loop->single_exit
|
if (loop->single_exit
|
&& loop->single_exit != e)
|
&& loop->single_exit != e)
|
{
|
{
|
error ("wrong single exit %d->%d recorded for loop %d",
|
error ("wrong single exit %d->%d recorded for loop %d",
|
loop->single_exit->src->index,
|
loop->single_exit->src->index,
|
loop->single_exit->dest->index,
|
loop->single_exit->dest->index,
|
loop->num);
|
loop->num);
|
error ("right exit is %d->%d",
|
error ("right exit is %d->%d",
|
e->src->index, e->dest->index);
|
e->src->index, e->dest->index);
|
err = 1;
|
err = 1;
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
for (i = 1; i < loops->num; i++)
|
for (i = 1; i < loops->num; i++)
|
{
|
{
|
loop = loops->parray[i];
|
loop = loops->parray[i];
|
if (!loop)
|
if (!loop)
|
continue;
|
continue;
|
|
|
if (sizes[i] == 1
|
if (sizes[i] == 1
|
&& !loop->single_exit)
|
&& !loop->single_exit)
|
{
|
{
|
error ("single exit not recorded for loop %d", loop->num);
|
error ("single exit not recorded for loop %d", loop->num);
|
err = 1;
|
err = 1;
|
}
|
}
|
|
|
if (sizes[i] != 1
|
if (sizes[i] != 1
|
&& loop->single_exit)
|
&& loop->single_exit)
|
{
|
{
|
error ("loop %d should not have single exit (%d -> %d)",
|
error ("loop %d should not have single exit (%d -> %d)",
|
loop->num,
|
loop->num,
|
loop->single_exit->src->index,
|
loop->single_exit->src->index,
|
loop->single_exit->dest->index);
|
loop->single_exit->dest->index);
|
err = 1;
|
err = 1;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
gcc_assert (!err);
|
gcc_assert (!err);
|
|
|
free (sizes);
|
free (sizes);
|
}
|
}
|
|
|
/* Returns latch edge of LOOP. */
|
/* Returns latch edge of LOOP. */
|
edge
|
edge
|
loop_latch_edge (const struct loop *loop)
|
loop_latch_edge (const struct loop *loop)
|
{
|
{
|
return find_edge (loop->latch, loop->header);
|
return find_edge (loop->latch, loop->header);
|
}
|
}
|
|
|
/* Returns preheader edge of LOOP. */
|
/* Returns preheader edge of LOOP. */
|
edge
|
edge
|
loop_preheader_edge (const struct loop *loop)
|
loop_preheader_edge (const struct loop *loop)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
FOR_EACH_EDGE (e, ei, loop->header->preds)
|
FOR_EACH_EDGE (e, ei, loop->header->preds)
|
if (e->src != loop->latch)
|
if (e->src != loop->latch)
|
break;
|
break;
|
|
|
return e;
|
return e;
|
}
|
}
|
|
|
/* Returns true if E is an exit of LOOP. */
|
/* Returns true if E is an exit of LOOP. */
|
|
|
bool
|
bool
|
loop_exit_edge_p (const struct loop *loop, edge e)
|
loop_exit_edge_p (const struct loop *loop, edge e)
|
{
|
{
|
return (flow_bb_inside_loop_p (loop, e->src)
|
return (flow_bb_inside_loop_p (loop, e->src)
|
&& !flow_bb_inside_loop_p (loop, e->dest));
|
&& !flow_bb_inside_loop_p (loop, e->dest));
|
}
|
}
|
|
|
