This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Irreducible loops self checking
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: gcc-patches at gcc dot gnu dot org, rth at redhat dot com
- Date: Fri, 21 Nov 2003 16:38:30 +0100
- Subject: [tree-ssa] Irreducible loops self checking
Hi,
this patch adds code to ensure that we don't introduce new irreducible
region during optimization. I don't want to use loop code for it as it
unshares loop regions and checking code should not clobber the CFG so I
used structural analysis code I wrote earlier.
While this is quite violent sollution for such a small problem, I think
the code will become more usefull in the future as it serves interesting
alternative to the loop discovery code (in some way it is easier to keep
up to date and it does not suffer quadratic behaviour) and it can be
used to make pretty printer dumps output structured programs again.
(Zdenek did some work on this independently so I want to check first his
work before making some more work.)
Regtested/bootstrapped i386 together with SSA patch. OK?
Honza
2003-11-21 Jan Hubicka <jh@suse.cz>
* tree-optimize.c: Include sa.h.
(optimize-function_tree): Check amount of improper regions.
* sa.c: New file.
* sa.h: New file.
* Makefile.in (sa.o): New.
(tree-optimize.o): Depend on sa.h
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.78
diff -c -3 -p -r1.1.4.78 tree-optimize.c
*** tree-optimize.c 20 Nov 2003 21:21:44 -0000 1.1.4.78
--- tree-optimize.c 21 Nov 2003 15:18:39 -0000
*************** Boston, MA 02111-1307, USA. */
*** 44,49 ****
--- 44,51 ----
#include "tree-inline.h"
#include "tree-mudflap.h"
#include "ggc.h"
+ #include "sa.h"
/* Rewrite a function tree to the SSA form and perform the SSA-based
optimizations on it. */
*************** optimize_function_tree (tree fndecl, tre
*** 71,76 ****
--- 73,82 ----
if (n_basic_blocks > 0)
{
sbitmap vars_to_rename;
+ #ifdef ENABLE_CHECKING
+ int nimproper;
+ struct flow_structure *structure;
+ #endif
/* Initialize common SSA structures. */
init_tree_ssa ();
*************** optimize_function_tree (tree fndecl, tre
*** 82,87 ****
--- 88,99 ----
the function. */
compute_may_aliases (fndecl);
+ #ifdef ENABLE_CHECKING
+ structure = build_flow_structure ();
+ nimproper = structure->nimproper;
+ free (structure);
+ #endif
+
/* BEGIN SSA PASSES
IMPORTANT: If you change the order in which these passes are
*************** optimize_function_tree (tree fndecl, tre
*** 175,188 ****
if (flag_tree_dce)
tree_ssa_dce (fndecl, TDI_dce_2);
- #if 0
- /* Eliminate tail recursion calls and discover sibling calls. */
- tree_optimize_tail_calls (true, TDI_tail2);
- #endif
#ifdef ENABLE_CHECKING
! verify_flow_info ();
#endif
/* Rewrite the function out of SSA form. */
rewrite_out_of_ssa (fndecl, TDI_optimized);
--- 230,245 ----
if (flag_tree_dce)
tree_ssa_dce (fndecl, TDI_dce_2);
#ifdef ENABLE_CHECKING
! structure = build_flow_structure ();
! /* We shall never introduce new improper regions
! before loop optimization is performed. */
! if (structure->nimproper > nimproper)
! abort ();
! free (structure);
#endif
+
/* Rewrite the function out of SSA form. */
rewrite_out_of_ssa (fndecl, TDI_optimized);
Index: sa.c
===================================================================
RCS file: sa.c
diff -N sa.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- sa.c 21 Nov 2003 15:18:39 -0000
***************
*** 0 ****
--- 1,1135 ----
+ /* The structural control flow graph analysis.
+ Contributed by Jan Hubicka, SuSE Labs.
+ Copyright (C) 2003 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+ License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ /* This pass performs the structural analysis and produces the reduced
+ flowgraph containing single entry-multiple exit nodes.
+ It is almost identical to the algorithm described by Muchnick's
+ Advanced Compiler Design and Implementation book, 202-214. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "alloc-pool.h"
+ #include "basic-block.h"
+ #include "sa.h"
+ #include "toplev.h"
+ #include "rtl.h" /* We need abort() macro. */
+
+ /* Pool used to allocate lists of improper regions. */
+ alloc_pool list_pool;
+ /* Dominance info is used to minimize improper regions
+ and is computed lazilly when such a region appears. */
+ static dominance_info dom;
+
+ /* Create structural node. */
+ static struct struct_node *
+ create_node (struct flow_structure *st, enum node_type type)
+ {
+ struct struct_node *n = pool_alloc (st->node_pool);
+ memset (n, 0, sizeof (*n));
+ n->index = st->nnodes++;
+ if (type == STRUCT_IMPROPER)
+ st->nimproper++;
+ n->type = type;
+ n->improper_head = NULL;
+ n->improper_nodes = NULL;
+ return n;
+ }
+
+ /* Create edge and avoid duplicates. */
+
+ static struct struct_edge *
+ struct_create_edge (struct flow_structure *st, struct struct_node *n1,
+ struct struct_node *n2)
+ {
+ struct struct_edge *e = n1->succ;
+ /* Look if the edge does already exist. */
+ while (e)
+ {
+ if (e->src == n1 && e->dest == n2)
+ return e;
+ e = e->succ_next;
+ }
+ e = pool_alloc (st->edge_pool);
+
+ e->src = n1;
+ e->dest = n2;
+ e->pred_prev = NULL;
+ e->succ_prev = NULL;
+ e->pred_next = e->dest->pred;
+ e->succ_next = e->src->succ;
+
+ if (n1->succ)
+ n1->succ->succ_prev = e;
+ if (n2->pred)
+ n2->pred->pred_prev = e;
+
+ n1->succ = e;
+ n2->pred = e;
+
+ return e;
+ }
+
+ /* Remove edge. */
+ static void
+ struct_remove_edge (struct flow_structure *st,
+ struct struct_edge *e)
+ {
+ if (e->pred_prev)
+ e->pred_prev->pred_next = e->pred_next;
+ else if (e->dest->pred != e)
+ abort ();
+ else
+ e->dest->pred = e->pred_next;
+
+ if (e->succ_prev)
+ e->succ_prev->succ_next = e->succ_next;
+ else if (e->src->succ != e)
+ abort ();
+ else
+ e->src->succ = e->succ_next;
+
+ if (e->pred_next)
+ e->pred_next->pred_prev = e->pred_prev;
+ if (e->succ_next)
+ e->succ_next->succ_prev = e->succ_prev;
+ pool_free (st->edge_pool, e);
+ }
+
+ /* Create structural node representing basic block B.
+ b->aux filed is set to point back to the node to simplify manipulation. */
+ static struct struct_node *
+ create_basic_block_node (struct flow_structure *st, basic_block b)
+ {
+ struct struct_node *n = create_node (st, STRUCT_BASIC_BLOCK);
+ n->data.basic_block.basic_block = b;
+ b->aux = n;
+ return n;
+ }
+
+ /* Create structural node representing exit block. */
+ static struct struct_node *
+ create_exit_node (struct flow_structure *st)
+ {
+ struct struct_node *n = create_node (st, STRUCT_EXIT);
+ n->data.basic_block.basic_block = EXIT_BLOCK_PTR;
+ EXIT_BLOCK_PTR->aux = n;
+ return n;
+ }
+
+ /* Create structural node representing entry block. */
+ static struct struct_node *
+ create_entry_node (struct flow_structure *st)
+ {
+ struct struct_node *n = create_node (st, STRUCT_ENTRY);
+ n->data.basic_block.basic_block = ENTRY_BLOCK_PTR;
+ ENTRY_BLOCK_PTR->aux = n;
+ return n;
+ }
+
+ /* Print INDENT spaces. */
+ static void
+ print_indent (FILE *out, int indent)
+ {
+ int i;
+
+ for (i = 0; i < indent; i++)
+ fputc (' ', out);
+ }
+
+ /* Print goto used by proper, improper and reduced_loop blocks. */
+ static void
+ struct_pretty_print_goto (FILE *out, struct struct_node *node, int indent,
+ bool indented)
+ {
+ bool first = true;
+ struct struct_edge *e = node->succ;
+
+ if (!node->succ)
+ return;
+ if (!indented)
+ print_indent (out, indent);
+ else
+ fputc (' ', out);
+ fputs ("goto ", out);
+ for (e = node->succ; e; e = e->succ_next)
+ {
+ struct struct_node *n = e->dest;
+
+ while (n->son)
+ n = n->son;
+ if (!first)
+ fputs (" or ", out);
+ if (n->type == STRUCT_EXIT)
+ fputs ("return", out);
+ else if (n->type == STRUCT_BASIC_BLOCK)
+ fprintf (out, "bb%i", n->data.basic_block.basic_block->index);
+ first = false;
+ }
+ if (node->exits)
+ {
+ if (!first)
+ fputs (" or ", out);
+ fputs ("upper", out);
+ }
+ fputc ('\n', out);
+ }
+
+ /* Pretty print node indented by INDENT spaces. If INDENTED is true,
+ expect the current line being already partly output and use it only
+ if the whole thing fits into single line. */
+ static void
+ struct_pretty_print_node (FILE *out, struct struct_node *node, int indent,
+ bool indented)
+ {
+ struct struct_node *n = node->son;
+ switch (node->type)
+ {
+ case STRUCT_NONE:
+ abort ();
+ case STRUCT_ENTRY:
+ break;
+ case STRUCT_EXIT:
+ if (!indented)
+ print_indent (out, indent);
+ else
+ fputc (' ', out);
+ fputs ("return\n", out);
+ break;
+ case STRUCT_BLOCK:
+ if (indented)
+ fputc ('\n', out);
+ print_indent (out, indent);
+ fputs ("{\n", out);
+ while (n)
+ {
+ struct_pretty_print_node (out, n, indent + 2, false);
+ if (n->son_next && (!n->succ || n->succ->succ_next
+ || n->succ->dest != n->son_next))
+ abort ();
+
+ n = n->son_next;
+ }
+ print_indent (out, indent);
+ fputs ("}\n", out);
+ break;
+ case STRUCT_IF_THEN_ELSE:
+ if (indented)
+ fputc ('\n', out);
+ print_indent (out, indent);
+ fputs ("if", out);
+ again:
+ struct_pretty_print_node (out, n, indent + 2, true);
+ n = n->son_next;
+ struct_pretty_print_node (out, n, indent + 2, false);
+ n = n->son_next;
+ print_indent (out, indent);
+ if (n->type == STRUCT_IF_THEN_ELSE)
+ {
+ fputs ("else if", out);
+ node = n;
+ n = n->son;
+ goto again;
+ }
+ if (n->type == STRUCT_IF_THEN)
+ {
+ fputs ("else if", out);
+ node = n;
+ n = n->son;
+ goto again2;
+ }
+ fputs ("else\n", out);
+ struct_pretty_print_node (out, n, indent + 2, false);
+ n = n->son_next;
+ if (n)
+ abort ();
+ break;
+ case STRUCT_IF_THEN:
+ if (indented)
+ fputc ('\n', out);
+ print_indent (out, indent);
+ fputs ("if", out);
+ again2:
+ struct_pretty_print_node (out, n, indent + 2, true);
+ n = n->son_next;
+ struct_pretty_print_node (out, n, indent + 2, false);
+ n = n->son_next;
+ if (n)
+ abort ();
+ break;
+ case STRUCT_BASIC_BLOCK:
+ if (!indented)
+ print_indent (out, indent);
+ else
+ fputc (' ', out);
+ {
+ basic_block bb = node->data.basic_block.basic_block;
+
+ fprintf (out, "BB #%i", bb->index);
+ if (bb->frequency)
+ fprintf (out, " freq:%i", bb->frequency);
+ if (bb->count)
+ fprintf (out, " count:" HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) bb->count);
+ fputc ('\n', out);
+ }
+ if (n)
+ abort ();
+ break;
+ case STRUCT_LOOP:
+ if (indented)
+ fputc ('\n', out);
+ print_indent (out, indent);
+ fputs ("loop", out);
+ struct_pretty_print_node (out, n, indent + 2, true);
+ if (n->son_next)
+ abort ();
+ break;
+ case STRUCT_REPEAT:
+ if (indented)
+ fputc ('\n', out);
+ print_indent (out, indent);
+ fputs ("do\n", out);
+ struct_pretty_print_node (out, n, indent + 2, false);
+ n = n->son_next;
+ print_indent (out, indent);
+ fputs ("while", out);
+ struct_pretty_print_node (out, n, indent + 2, true);
+ if (n->son_next)
+ abort ();
+ break;
+ case STRUCT_WHILE:
+ if (indented)
+ fputc ('\n', out);
+ print_indent (out, indent);
+ fputs ("while", out);
+ struct_pretty_print_node (out, n, indent + 2, true);
+ n = n->son_next;
+ print_indent (out, indent);
+ fputs ("do\n", out);
+ struct_pretty_print_node (out, n, indent + 2, false);
+ if (n->son_next)
+ abort ();
+ break;
+ case STRUCT_REDUCED_LOOP:
+ if (indented)
+ fputc ('\n', out);
+ print_indent (out, indent);
+ fputs ("while forever\n", out);
+ print_indent (out, indent + 2);
+ fputs ("{\n", out);
+ while (n)
+ {
+ struct struct_node *next = n->son_next;
+
+ if (!next)
+ next = node->son;
+ if (!n->succ->succ_next && n->succ->dest == next && !n->exits)
+ {
+ struct_pretty_print_node (out, n, indent + 4, false);
+ }
+ else if (!n->succ->succ_next && n->succ->dest == next && n->exits)
+ {
+ print_indent (out, indent + 4);
+ fputs ("if", out);
+ struct_pretty_print_node (out, n, indent + 6, true);
+ print_indent (out, indent + 6);
+ fputs ("break\n", out);
+ }
+ else
+ {
+ struct_pretty_print_node (out, n, indent + 4, false);
+ struct_pretty_print_goto (out, n, indent + 4, false);
+ }
+ n = n->son_next;
+ }
+ print_indent (out, indent + 2);
+ fputs ("}\n", out);
+ break;
+ case STRUCT_PROPER:
+ case STRUCT_IMPROPER:
+ if (indented)
+ fputc ('\n', out);
+ if (node->type == STRUCT_IMPROPER)
+ {
+ print_indent (out, indent);
+ fputs ("improper:\n", out);
+ }
+ print_indent (out, indent);
+ fputs ("{\n", out);
+ while (n)
+ {
+ struct struct_node *next = n->son_next;
+
+ if (n->succ && !n->succ->succ_next && n->succ->dest == next
+ && !n->exits)
+ {
+ struct_pretty_print_node (out, n, indent + 2, false);
+ }
+ else if (n->succ && !n->succ->succ_next && n->succ->dest == next
+ && n->exits)
+ {
+ print_indent (out, indent + 2);
+ fputs ("if", out);
+ struct_pretty_print_node (out, n, indent + 4, true);
+ print_indent (out, indent + 4);
+ fputs ("break\n", out);
+ }
+ else
+ {
+ struct_pretty_print_node (out, n, indent + 2, false);
+ struct_pretty_print_goto (out, n, indent + 2, false);
+ }
+ n = n->son_next;
+ }
+ print_indent (out, indent);
+ fputs ("}\n", out);
+ break;
+ default:
+ abort ();
+ }
+ }
+
+ /* Print node in verbose way. Useful for debugging structural analysis itself.
+ analysis themselves. */
+ static void
+ struct_print_node (FILE *out, struct struct_node *node, int indent)
+ {
+ static const char *const node_names[] = {
+ "none",
+ "basic_block",
+ "entry",
+ "exit",
+ "block",
+ "if_then",
+ "if_then_else",
+ "proper",
+ "loop",
+ "repeat",
+ "while",
+ "reduced_loop",
+ "improper"
+ };
+ struct struct_node *n = node->son;
+
+ print_indent (out, indent);
+ fprintf (out, "%s #%i pre: %i post: %i", node_names[node->type], node->index,
+ node->pre_dfs_index, node->post_dfs_index);
+ if (node->type == STRUCT_BASIC_BLOCK)
+ fprintf (out, " %i", node->data.basic_block.basic_block->index);
+ if (node->succ)
+ {
+ struct struct_edge *e = node->succ;
+ fprintf (out, " succ [");
+ while (e)
+ {
+ if (e->src != node)
+ abort ();
+ fprintf (out, " %i", e->dest->index);
+ e = e->succ_next;
+ }
+ fprintf (out, " ]");
+ }
+ if (node->pred)
+ {
+ struct struct_edge *e = node->pred;
+ fprintf (out, " pred [");
+ while (e)
+ {
+ if (e->dest != node)
+ abort ();
+ fprintf (out, " %i", e->src->index);
+ e = e->pred_next;
+ }
+ fprintf (out, " ]");
+ }
+ fprintf (out, "\n");
+ while (n)
+ {
+ struct_print_node (out, n, indent + 2);
+ n = n->son_next;
+ }
+ }
+
+ /* We need to mirror the CFG into our own representation.
+ Return entry node. */
+ static struct struct_node *
+ mirror_cfg (struct flow_structure *st)
+ {
+ basic_block bb;
+ edge edge;
+
+ FOR_EACH_BB (bb)
+ create_basic_block_node (st, bb);
+ FOR_EACH_BB (bb)
+ {
+ edge = bb->succ;
+ while (edge)
+ {
+ struct_create_edge (st, edge->src->aux, edge->dest->aux);
+ edge = edge->succ_next;
+ }
+ /* Structural analysis produces ugly results in presence of a
+ basic block with no outgoing edges. Alternatively we can
+ accept a noreturn block for STRUCT_IF_THEN/STRUCT_IF_THEN_ELSE
+ or invent new names for conditionals terminating the program. */
+ if (!bb->succ)
+ struct_create_edge (st, bb->aux, st->exit);
+ }
+ edge = ENTRY_BLOCK_PTR->succ;
+ while (edge)
+ {
+ struct_create_edge (st, st->entry, edge->dest->aux);
+ edge = edge->succ_next;
+ }
+ return (st->entry);
+ }
+
+ /* Perform depth first search, intialize dfs_order structure
+ and set pre_dfs_index and post_dfs_index. */
+ static int
+ struct_DFS (struct struct_node **dfs_order, struct struct_node *n)
+ {
+ struct struct_edge **stack;
+ int sp;
+ int prenum = 1;
+ int postnum = 0;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack =
+ (struct struct_edge **) xmalloc ((n_basic_blocks + 2) *
+ sizeof (struct struct_edge *));
+ sp = 0;
+ n->visit = 1;
+ n->pre_dfs_index = 0;
+
+ /* Push the first edge on to the stack. */
+ stack[sp++] = n->succ;
+
+ while (sp)
+ {
+ struct struct_edge *e;
+ struct struct_node *src;
+ struct struct_node *dest;
+
+ /* Look at the edge on the top of the stack. */
+ e = stack[sp - 1];
+ src = e->src;
+ dest = e->dest;
+
+ /* Check if the edge destination has been visited yet. */
+ if (!dest->visit)
+ {
+ /* Mark that we have visited the destination. */
+ dest->visit = 1;
+
+ dest->pre_dfs_index = prenum++;
+ if (dest->succ)
+ {
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = dest->succ;
+ }
+ else
+ {
+ dfs_order[postnum] = dest;
+ dest->post_dfs_index = postnum++;
+ }
+ }
+ else
+ {
+ if (!e->succ_next)
+ {
+ dfs_order[postnum] = src;
+ src->post_dfs_index = postnum++;
+ }
+
+ if (e->succ_next)
+ stack[sp - 1] = e->succ_next;
+ else
+ sp--;
+ }
+ }
+
+ free (stack);
+ return postnum;
+ }
+
+ /* Reduce chain of nodes starting at SON into region of TYPE.
+ Update DFS_ORDER and set new entry type in case it has changed. */
+ static struct struct_node *
+ reduce (struct flow_structure *st, struct struct_node *son,
+ enum node_type type, struct struct_node **dfs_order,
+ struct struct_node **entry)
+ {
+ struct struct_node *node;
+ struct struct_node *n;
+ int maxorder = son->post_dfs_index;
+ int minorder = son->pre_dfs_index;
+
+ /* Compute new DFS indexes. */
+ #ifdef ENABLE_CHECKING
+ n = son;
+ while (n)
+ {
+ if (n->parent)
+ abort ();
+ n = n->son_next;
+ }
+ #endif
+
+ /* We are recogninzing blocks in pairs. It looks prettier when we
+ concatenate them into single blocks containing multiple sons. */
+ if (type == STRUCT_BLOCK
+ && son->son_next->type == STRUCT_BLOCK && !son->son_next->son_next)
+ {
+ node = son->son_next;
+
+ /* Create internal edge. */
+ struct_remove_edge (st, son->succ);
+ if (son->succ)
+ abort ();
+ struct_create_edge (st, son, node->son);
+
+ /* Merge sons. */
+ son->parent = node;
+ son->son_next = node->son;
+ node->son = son;
+ node->visit = 0;
+
+ /* Redirect incomming edges. */
+ if (node->pred)
+ abort ();
+ while (son->pred)
+ {
+ struct_create_edge (st, son->pred->src, node);
+ struct_remove_edge (st, son->pred);
+ }
+ }
+ else
+ {
+
+ node = create_node (st, type);
+ node->son = son;
+
+ n = son;
+ while (n)
+ {
+ n->parent = node;
+ n = n->son_next;
+ }
+ if (!son)
+ abort ();
+ n = son;
+ while (n)
+ {
+ struct struct_edge *e;
+ e = n->succ;
+ while (e)
+ {
+ struct struct_edge *next = e->succ_next;
+ struct struct_node *d = e->dest;
+ if (d == son && !LOOPING_NODE (type))
+ abort ();
+ else if (d->parent != node)
+ {
+ struct_remove_edge (st, e);
+ struct_create_edge (st, node, d);
+ n->exits = true;
+ }
+ e = next;
+ }
+ e = n->pred;
+ while (e)
+ {
+ struct struct_edge *next = e->pred_next;
+ struct struct_node *s = e->src;
+ if (s->parent != node)
+ {
+ if (n != node->son)
+ abort ();
+ struct_remove_edge (st, e);
+ struct_create_edge (st, s, node);
+ }
+ e = next;
+ }
+ if (n == *entry)
+ *entry = node;
+ n = n->son_next;
+ }
+ }
+ dfs_order[maxorder] = node;
+ node->pre_dfs_index = minorder;
+ node->post_dfs_index = maxorder;
+ return node;
+ }
+
+ /* Return true if N is a succesor of N2. */
+ static bool
+ succ_of_p (struct struct_node *n, struct struct_node *n2)
+ {
+ struct struct_edge *e;
+
+ for (e = n2->succ; e; e = e->succ_next)
+ if (e->dest == n)
+ return true;
+ return false;
+ }
+
+ /* Proper region is maximal acyclic subgraph with only single entry point N.
+ We discover it by doing topological sort as long as we are able to. */
+ static struct struct_node *
+ find_proper_region (struct struct_node *n)
+ {
+ struct struct_node *lastson = n;
+ struct struct_node *current = n;
+
+ while (current)
+ {
+ struct struct_edge *e = current->succ;
+ while (e)
+ {
+ /* We ought to have an counter here, but I am lazy to do it for now
+ so I just look for unknown predecessors by hand. This makes
+ algorithm potentially quadratic in number of nodes. */
+ struct struct_edge *e1 = e->dest->pred;
+
+ if (!e->dest->son_next && e->dest != lastson)
+ {
+ while (e1)
+ {
+ if (!e1->src->son_next && e1->src != lastson)
+ break;
+ e1 = e1->pred_next;
+ }
+ if (!e1 && !succ_of_p (n, e->dest))
+ {
+ lastson->son_next = e->dest;
+ lastson = e->dest;
+ }
+ }
+ e = e->succ_next;
+ }
+ current = current->son_next;
+ }
+ return n;
+ }
+
+ /* Return true when A is ancestor of B in DFS search. */
+ static bool
+ is_ancestor_p (struct struct_node *a, struct struct_node *b)
+ {
+ return (a->pre_dfs_index <= b->pre_dfs_index
+ && a->post_dfs_index > b->post_dfs_index);
+ }
+
+ /* Reverse linked list representing structural node. */
+ static struct struct_node *
+ reverse_son_list (struct struct_node *n)
+ {
+ struct struct_node *prev = 0, *next;
+ for (; n; n = next)
+ {
+ next = n->son_next;
+ n->son_next = prev;
+ prev = n;
+ }
+ return prev;
+ }
+
+ /* Add node NODE into list pointed to by WHERE. */
+ static void
+ add_to_node_list (struct struct_node_list **where, struct struct_node *node)
+ {
+ struct struct_node_list *list = pool_alloc (list_pool);
+ list->node = node;
+ list->next = *where;
+ *where = list;
+ }
+
+ /* Identify the cyclic region in the graph entered by node n. */
+
+ static struct struct_node *
+ find_cyclic_region (struct struct_node *n)
+ {
+ struct struct_edge *e = n->pred;
+ struct struct_node *lastson = n;
+ bool improper = false;
+
+ while (e)
+ {
+ /* Identify the back edges. */
+ if (is_ancestor_p (n, e->src)
+ && (!e->src->son_next && e->src != lastson))
+ {
+ struct struct_node *n1 = e->src;
+ struct struct_node *torev = lastson;
+
+ lastson->son_next = n1;
+ lastson = n1;
+ /* When we are not looking at loopback edge, discover loop body
+ by looking at predesecors of the basic block. */
+ while (n1)
+ {
+ struct struct_edge *e1 = n1->pred;
+ while (e1)
+ {
+ /* Look for blocks we didn't visited yet and link them
+ into region. */
+ if (e1->src->parent)
+ abort ();
+ if (!e1->src->son_next && e1->src != lastson)
+ {
+ if (is_ancestor_p (n, e1->src))
+ {
+ lastson->son_next = e1->src;
+ lastson = e1->src;
+ }
+ else
+ improper = true;
+ }
+ e1 = e1->pred_next;
+ }
+ n1 = n1->son_next;
+ }
+
+ /* Make ordering prettier - we discover the loop in reverse order.
+ */
+ lastson = torev->son_next;
+ torev->son_next = reverse_son_list (torev->son_next);
+ }
+ e = e->pred_next;
+ }
+ /* Do we have improper region? If so, we have to perform minimization. */
+ if (n->son_next && improper)
+ {
+ struct struct_node *l, *head, *next;
+ basic_block ancestor = NULL;
+
+ if (!dom)
+ dom = calculate_dominance_info (CDI_DOMINATORS);
+
+ for (l = n; l; l = l->son_next)
+ {
+ struct struct_node *l2 = l;
+ basic_block b;
+
+ while (l2->parent)
+ l2 = l2->parent;
+ b = l2->data.basic_block.basic_block;
+ if (!ancestor)
+ ancestor = b;
+ else
+ ancestor = nearest_common_dominator (dom, b, ancestor);
+ }
+ head = ancestor->aux;
+ while (head->parent)
+ head = head->parent;
+ for (l = n; l; l = next)
+ {
+ next = l->son_next;
+ l->son_next = NULL;
+ if (l->improper_head != head)
+ {
+ add_to_node_list (&head->improper_nodes, l);
+ l->improper_head = head;
+ }
+ }
+ }
+ return n;
+ }
+
+ /* Return type of the acyclic region, STRUCT_NODE otherwise. */
+ static enum node_type
+ acyclic_region_type (struct struct_node *n, struct struct_node **first)
+ {
+ struct struct_node *n1 = n;
+ struct struct_node *n2 = n;
+
+ /* Rule out self loops early. */
+ if (succ_of_p (n, n))
+ return STRUCT_NONE;
+
+ /* Block. */
+ if (n->succ && !n->succ->succ_next)
+ {
+ n2 = n->succ->dest;
+ if (n2->pred && !n2->pred->pred_next && !succ_of_p (n1, n2))
+ {
+ n1->son_next = n2;
+ n2->son_next = NULL;
+ *first = n1;
+ return STRUCT_BLOCK;
+ }
+ }
+
+ /* Nonlooping conditional jump... */
+ if (n->succ && n->succ->succ_next && !n->succ->succ_next->succ_next
+ && n->succ->dest != n && n->succ->succ_next->dest != n)
+ {
+ n1 = n->succ->dest;
+ n2 = n->succ->succ_next->dest;
+ if (n1 == n2)
+ abort ();
+
+ /* If then else */
+ if (n1->succ && n2->succ && n1->succ->dest == n2->succ->dest
+ && !n1->succ->succ_next && !n2->succ->succ_next
+ && !n1->pred->pred_next && !n2->pred->pred_next
+ /* Prohibit loops */
+ && n1->succ->dest != n1 && n1->succ->dest != n
+ && n1->succ->dest != n2)
+ {
+ n->son_next = n2;
+ n2->son_next = n1;
+ n1->son_next = NULL;
+ *first = n;
+ return STRUCT_IF_THEN_ELSE;
+ }
+
+ /* if then */
+ if (n1->succ && n1->succ->dest == n2
+ && !n1->succ->succ_next && n1->pred && !n1->pred->pred_next)
+ {
+ n->son_next = n1;
+ n1->son_next = NULL;
+ *first = n;
+ return STRUCT_IF_THEN;
+ }
+ /* The symetric case. */
+ if (n2->succ && n2->succ->dest == n1
+ && !n2->succ->succ_next && n2->pred && !n2->pred->pred_next)
+ {
+ n->son_next = n2;
+ n2->son_next = NULL;
+ *first = n;
+ return STRUCT_IF_THEN;
+ }
+ }
+
+ /* Handling of the switch statements is suggested too, but I don't see any
+ point to do that right now. */
+ return STRUCT_NONE;
+ }
+
+ /* Return the type of cyclic region, STRUCT_NONE otherwise.
+ Also initialize improper_nodes lists in the case current node is
+ found to be in the improper region. */
+ static enum node_type
+ cyclic_region_type (struct struct_node *n, struct struct_node **first)
+ {
+ /* The fast path - self loops and repeat loops are the most common
+ looping constructs. */
+ if (succ_of_p (n, n))
+ {
+ *first = n;
+ return STRUCT_LOOP;
+ }
+ if (n->succ && !n->succ->succ_next
+ && !n->succ->dest->pred->pred_next && succ_of_p (n, n->succ->dest))
+ {
+ *first = n;
+ n->son_next = n->succ->dest;
+ return STRUCT_REPEAT;
+ }
+ *first = find_cyclic_region (n);
+
+ if ((*first)->son_next && !(*first)->son_next->son_next
+ && (*first)->son_next->succ && !(*first)->son_next->succ->succ_next)
+ return STRUCT_WHILE;
+
+ /* The existence of loops with multiple entry points is very unfortunate.
+ For now deal by converting whole graph to single improper region.
+ We will need to find more smart way how to discover them later. */
+ if ((*first)->son_next)
+ return STRUCT_REDUCED_LOOP;
+ return STRUCT_NONE;
+ }
+
+ /* Look for closest header of improper region. */
+ static void
+ minimize_improper_regions (struct struct_node *n)
+ {
+ struct struct_node *head = n->improper_head;
+ struct struct_edge *e;
+ int min_post_ord_seen = INT_MAX;
+
+ if (head)
+ min_post_ord_seen = head->post_dfs_index;
+ for (e = n->succ; e; e = e->succ_next)
+ if (e->dest->improper_head
+ && min_post_ord_seen > e->dest->improper_head->post_dfs_index)
+ {
+ min_post_ord_seen = e->dest->improper_head->post_dfs_index;
+ head = e->dest->improper_head;
+ }
+ if (min_post_ord_seen != INT_MAX && n->improper_head != head)
+ {
+ n->improper_head = head;
+ add_to_node_list (&head->improper_nodes, n);
+ }
+ }
+
+ /* Build list of all nodes inside improper regions.
+ We may enocounter nested improper regions so we need to traverse
+ these recursivly. */
+ static struct struct_node *
+ build_improper_region (struct struct_node *n)
+ {
+ struct struct_node_list *l;
+ struct struct_node *first = n;
+ struct struct_node *last = n;
+
+ for (l = n->improper_nodes; l; l = l->next)
+ {
+ struct struct_node *nn = l->node;
+ while (nn->parent)
+ nn = nn->parent;
+ if (nn != last && !nn->son_next)
+ {
+ last->son_next = nn;
+ last = nn;
+ }
+ }
+ return first;
+ }
+
+ /* Main entry point - build flow structure and return the pointer. */
+ struct flow_structure *
+ build_flow_structure (void)
+ {
+ struct flow_structure *st;
+ struct struct_node *entry;
+ struct struct_node **dfs_order;
+ int npost;
+ int nnodes = n_basic_blocks + 2;
+ int index = 0;
+ struct struct_node *first;
+
+ st = xcalloc (sizeof (*st), 1);
+ st->edge_pool =
+ create_alloc_pool ("structural edges", sizeof (struct struct_edge),
+ n_edges + 1);
+ st->node_pool =
+ create_alloc_pool ("structural nodes", sizeof (struct struct_node),
+ n_basic_blocks + 4);
+ list_pool =
+ create_alloc_pool ("structural nodes lists",
+ sizeof (struct struct_node_list), 1);
+ st->root = NULL;
+ st->nnodes = -2;
+ st->exit = create_exit_node (st);
+ st->entry = create_entry_node (st);
+
+ dfs_order =
+ (struct struct_node **) xmalloc ((n_basic_blocks + 2) *
+ sizeof (struct struct_node *));
+ entry = mirror_cfg (st);
+
+
+ npost = struct_DFS (dfs_order, entry);
+ for (index = 0; index < npost; index++)
+ {
+ dfs_order[index]->post_dfs_index = index;
+ dfs_order[index]->visit = 0;
+ }
+ index = 0;
+ while (nnodes > 1 && index < npost)
+ {
+ struct struct_node *n = dfs_order[index];
+ enum node_type type;
+ bool noreduce;
+
+ do
+ {
+ noreduce = false;
+ if (n->improper_nodes)
+ n = st->root =
+ reduce (st, build_improper_region (n), STRUCT_IMPROPER,
+ dfs_order, &entry);
+ if (n->parent)
+ {
+ minimize_improper_regions (n);
+ break;
+ }
+ /* Locate acyclic region if present. */
+ type = acyclic_region_type (n, &first);
+ if (!type)
+ {
+ /* Locate the cyclict region if present. */
+ type = cyclic_region_type (n, &first);
+ }
+ if (type)
+ n = st->root = reduce (st, first, type, dfs_order, &entry);
+ else
+ noreduce = true;
+ minimize_improper_regions (n);
+ }
+ while (!noreduce);
+ index++;
+ }
+
+ while (entry->parent)
+ entry = entry->parent;
+
+ /* Pack possible remaining irreducible acyclic nodes into single PROPER
+ basic block. */
+ first = find_proper_region (entry);
+ if (first->son_next)
+ st->root = reduce (st, first, STRUCT_PROPER, dfs_order, &entry);
+
+ /* Verify that we reduced whole CFG. */
+ while (entry->parent)
+ entry = entry->parent;
+ if (entry->succ || entry->pred)
+ abort ();
+
+ if (dom)
+ free_dominance_info (dom);
+ clear_aux_for_blocks ();
+ free_alloc_pool (list_pool);
+ dom = NULL;
+ return st;
+ }
+
+ /* Release data used by flow structure. */
+ void
+ free_flow_structure (struct flow_structure *st)
+ {
+ free_alloc_pool (st->edge_pool);
+ free_alloc_pool (st->node_pool);
+ free (st);
+ }
+
+ /* Dump whole flow structure in verbose way. */
+ void
+ dump_flow_structure (struct flow_structure *st, FILE *out)
+ {
+ struct_print_node (out, st->root, 0);
+ }
+
+ /* Dump whole flow structure in pretty way. */
+ void
+ pretty_dump_flow_structure (struct flow_structure *st, FILE *out)
+ {
+ struct_pretty_print_node (out, st->root, 0, false);
+ }
Index: sa.h
===================================================================
RCS file: sa.h
diff -N sa.h
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- sa.h 21 Nov 2003 15:18:39 -0000
***************
*** 0 ****
--- 1,139 ----
+ /* The structural control flow graph analysis.
+ Contributed by Jan Hubicka, SuSE Labs.
+ Copyright (C) 2003 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+ License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ #ifndef SA_H
+ #define SA_H
+ /* Basic constructions we know of.
+ Allow bit operations to represent classes of the struct constructions. */
+ enum node_type
+ {
+ STRUCT_NONE,
+ STRUCT_BASIC_BLOCK,
+ STRUCT_ENTRY,
+ STRUCT_EXIT,
+ /* son0->son1->son2.... */
+ STRUCT_BLOCK,
+ /* Son0
+ / |
+ son1 |
+ \ |
+ XXX */
+ STRUCT_IF_THEN,
+ /* Son0
+ / \
+ son1 son2
+ \ /
+ XXX */
+ STRUCT_IF_THEN_ELSE,
+ /* Arbitary acyclic region. */
+ STRUCT_PROPER,
+ /* Self loop. */
+ STRUCT_LOOP,
+ /* Son1
+ | ^
+ V |
+ Son2
+ |
+ V
+ XXXX */
+ STRUCT_REPEAT,
+ /* Son1---> XXX
+ | ^
+ V |
+ Son2 */
+ STRUCT_WHILE,
+ /* Arbitrary loop with single entry edge. */
+ STRUCT_REDUCED_LOOP,
+ /* Improper region - may contain everything. */
+ STRUCT_IMPROPER
+ };
+
+ #define LOOPING_NODE(type) (type >= STRUCT_LOOP)
+ struct struct_edge;
+
+ /* Structure used to represent each node. */
+ struct struct_node
+ {
+ enum node_type type;
+
+ /* Unique index used by dumping function. */
+ int index;
+
+ /* We represent tree of nodes. */
+ struct struct_node *parent;
+ struct struct_node *son;
+ struct struct_node *son_next;
+
+ struct struct_node_list
+ {
+ struct struct_node *node;
+ struct struct_node_list *next;
+ } *improper_nodes;
+ struct struct_node *improper_head;
+
+ /* As well as predecesor/succesor information. */
+ struct struct_edge *pred, *succ;
+
+ /* Data that does depend on the type of node. */
+ union
+ {
+ struct
+ {
+ struct basic_block_def *basic_block;
+ }
+ basic_block;
+ }
+ data;
+
+ /* Used temporary by DFS searching routines. Set to 0 otherwise. */
+ int visit:1;
+ /* Whether control flow can leave the parent node here. */
+ int exits:1;
+ int pre_dfs_index;
+ int post_dfs_index;
+ };
+
+ /* Structure used to represent edge. */
+ struct struct_edge
+ {
+ struct struct_node *src, *dest;
+ struct struct_edge *succ_next, *pred_next;
+ struct struct_edge *succ_prev, *pred_prev;
+ };
+
+ /* Overall Central Flow Structure object. */
+ struct flow_structure
+ {
+ /* Pool used to allocate all the data structures. */
+ struct alloc_pool_def *node_pool, *edge_pool;
+ struct struct_node *root;
+ struct struct_node *entry;
+ struct struct_node *exit;
+ int nnodes;
+ int nimproper;
+ };
+
+ struct flow_structure *build_flow_structure (void);
+ void free_flow_structure (struct flow_structure *);
+ void dump_flow_structure (struct flow_structure *, FILE *);
+ void pretty_dump_flow_structure (struct flow_structure *, FILE *);
+ void debug_flow_structure (void);
+ #endif
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.137
diff -c -3 -p -r1.903.2.137 Makefile.in
*** Makefile.in 21 Nov 2003 07:26:08 -0000 1.903.2.137
--- Makefile.in 21 Nov 2003 15:21:02 -0000
*************** OBJS-common = \
*** 895,901 ****
profile.o ra.o ra-build.o ra-colorize.o ra-debug.o ra-rewrite.o \
real.o recog.o reg-stack.o regclass.o regmove.o regrename.o \
reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o \
! sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o \
sibcall.o simplify-rtx.o sreal.o ssa.o ssa-ccp.o ssa-dce.o stmt.o \
stor-layout.o stringpool.o targhooks.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
--- 895,901 ----
profile.o ra.o ra-build.o ra-colorize.o ra-debug.o ra-rewrite.o \
real.o recog.o reg-stack.o regclass.o regmove.o regrename.o \
reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o \
! sa.o sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o \
sibcall.o simplify-rtx.o sreal.o ssa.o ssa-ccp.o ssa-dce.o stmt.o \
stor-layout.o stringpool.o targhooks.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
*************** tree-optimize.o : tree-optimize.c $(TREE
*** 1587,1593 ****
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
$(GGC_H) output.h diagnostic.h ssa.h errors.h flags.h tree-alias-common.h \
$(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) toplev.h function.h \
! langhooks.h flags.h cgraph.h tree-inline.h tree-mudflap.h $(GGC_H)
c-simplify.o : c-simplify.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) errors.h \
$(C_TREE_H) $(C_COMMON_H) diagnostic.h $(TREE_SIMPLE_H) varray.h flags.h \
langhooks.h toplev.h rtl.h $(TREE_FLOW_H) langhooks-def.h \
--- 1587,1593 ----
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
$(GGC_H) output.h diagnostic.h ssa.h errors.h flags.h tree-alias-common.h \
$(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) toplev.h function.h \
! langhooks.h flags.h cgraph.h tree-inline.h tree-mudflap.h $(GGC_H) sa.h
c-simplify.o : c-simplify.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) errors.h \
$(C_TREE_H) $(C_COMMON_H) diagnostic.h $(TREE_SIMPLE_H) varray.h flags.h \
langhooks.h toplev.h rtl.h $(TREE_FLOW_H) langhooks-def.h \
*************** regmove.o : regmove.c $(CONFIG_H) $(SYST
*** 1924,1929 ****
--- 1924,1931 ----
haifa-sched.o : haifa-sched.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
sched-int.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h flags.h insn-config.h function.h \
$(INSN_ATTR_H) toplev.h $(RECOG_H) except.h $(TM_P_H) $(TARGET_H)
+ sa.o : sa.c sa.h $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
+ $(BASIC_BLOCK_H) hard-reg-set.h coretypes.h $(TM_H)
sched-deps.o : sched-deps.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
sched-int.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h flags.h insn-config.h function.h \
$(INSN_ATTR_H) toplev.h $(RECOG_H) except.h cselib.h $(PARAMS_H) $(TM_P_H)