[patch] SSA for trees. Initial implementation.
Diego Novillo
dnovillo@redhat.com
Fri Mar 9 14:54:00 GMT 2001
This patch implements initial support for doing SSA analysis on
trees. This is part of the infrastructure work I had mentioned
back in January ( http://gcc.gnu.org/ml/gcc/2001-01/msg01864.html )
Essentially, the patch adds a new flag to GCC (-ftree-optimizer)
which makes c_expand_body() call tree_opt() right before
converting the function tree into RTL. The goal is for tree_opt()
to transform the function tree and feed that modified tree into
the rest of the compiler.
The pass is supposed to be completely transparent to the rest of
the optimizer. Currently, the patch builds a flowgraph for the
tree representation, finds all variable references in the
function and builds an SSA representation for it. The SSA data is
orthogonal to the function tree (ie, the function is not
modified).
Not surprisingly, the code is very much work in progress. It
works on mickey mouse programs, most of the time. And it still
doesn't do any transformations. It just builds the SSA form which
you can see by turning on one of the DEBUG_ environment variables
that the code recognizes.
I have done this mainly to learn how the tree representation
works in GCC. I wanted to release what I have to get some advice
w.r.t. implementation and design. I'm probably doing things that
are naive or "against the grain". Also, if anybody is at all
interested in helping me out with this, please let me know! There
is a huge number of things to be done yet.
This is a summary of the current implementation:
- In tree-cfg.c we build the flowgraph for the function tree. I
wanted to re-use the existing basic_block and edge data
structures as much as possible.
Unfortunately, this led me to make one truly horrid hack that I
am not sure how to circumvent (without revamping a bunch of
files or duplicating tons of code). The problem is that both
basic_block, edge and all the functions that use them assume
that they deal with `rtx' instructions.
What I did is #define a new symbol 'ilx' which gets defined to
'rtx' or 'tree' at compile time. This is gross, of course. But
we can get away with it because rtx basic_block objects
and tree basic_block objects are manipulated in completely
separate modules.
Functions that only deal with basic_blocks from a flowgraph
perspective can be shared (all the dominance information
functions). Ideally, I'd like GCC to have a true concept of
different ILs and make generic data structures like
basic_blocks and edges able to deal with them. But, this is a
much pervasive change. What other options could I try?
The flowgraph is built in a top-down manner. We walk all the
statements in the function, looking for basic_block
terminators. At control flow statements, we recurse and build
sub-graphs for the body (or bodies) of the statement. Edges are
built in a similar way.
- In tree-dfa.c we find all the variable references in the
function. Each def and use is added to a list of references
made in the corresponding basic block and also the symbol
representing the variable collects a list of references made to
it.
To support this I needed to add an 'aux' field to the
tree_common structure. I somehow remember that this was not
allowed before, but I'm not sure if that's the case anymore.
The patch doesn't break anything, so I guess it's OK?
The aux field is akin to the aux field in basic_block. One can
add pass-specific annotations to it. We have two types of
annotations one for trees (tree_ann) and the other for basic
blocks (basic_block_ann).
- In tree-ssa.c we build the SSA form for the flowgraph. All the
SSA information is annotated in the graph. I used the algorithm
in Wolfe's book "High Performance Compilers for Parallel
Computing", which is essentially the same one in Cytron's
original paper. The only reason for using it is that it's
simple to implement. I might try to implement a linear time phi
placing algorithm in the future.
To compute SSA information I used the existing dominance
functions and modified the current SSA pass to make the
dominance frontier function extern instead of static (I had to
do that on a couple other functions in flow.c)
- In tree-opt.c we just get the ball rolling by calling the
flowgraph builder, the reference finder and SSA builder.
To avoid hauling big diffs files around (it's already ~80Kb), I
would like to have this checked in either the mainline or a new
branch. I would prefer to work out of the mainline to avoid all
the merge activities. Since none of the code is activated unless
you use -ftree-optimizer, I think it's safe to work out of the
mainline but I don't mind working on a branch.
The patch bootstraps on i686-pc-linux-gnu. Well, it doesn't
today. I'm getting the same failures reported in
http://gcc.gnu.org/ml/gcc-bugs/2001-03/msg00022.html , but it did
before I updated my tree today. It also doesn't introduce any
regressions in the testsuite.
Thanks.
2001-03-09 Diego Novillo <dnovillo@redhat.com>
* Makefile.in (C_AND_OBJC_OBJS): Add tree-cfg.o, tree-dfa.o,
tree-ssa.o and tree-opt.o
(c-decl.o): Add tree-opt.h to list of dependencies.
(tree-ssa.o): Add.
(tree-cfg.o): Add.
(tree-dfa.o): Add.
(tree-opt.o): Add.
* basic-block.h (ilx): Define.
(struct edge_def): Replace 'rtx' with 'ilx'.
(struct basic_block_def): Ditto.
(struct loop): Ditto.
(dump_edge_info): Add extern definition.
(clear_edges): Ditto.
(mark_critical_edges): Ditto.
* c-decl.c (c_expand_body): Invoke tree optimizer when
-ftree-optimizer is set.
* flags.h (flag_tree_optimizer): New flag.
* flow.c (dump_edge_info): Change from static to extern.
(clear_edges): Ditto.
(mark_critical_edges): Ditto.
* ssa.c (compute_dominance_frontiers): Change from static to
extern.
* ssa.h (compute_dominance_frontiers): Add extern definition.
* toplev.c (flag_tree_optimizer): New flag.
(f_options): Add -ftree-optimizer.
* tree-cfg.c: New file.
* tree-dfa.c: New file.
* tree-flow.h: New file.
* tree-opt.c: New file.
* tree-opt.h: New file.
* tree-ssa.c: New file.
* tree.h (struct tree_common): Add new field 'aux'.
* cp/Make-lang.in (CXX_C_OBJS): Add tree-cfg.o, tree-dfa.o,
tree-opt.o and tree-ssa.o.
Index: gcc/Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.618
diff -d -c -p -r1.618 Makefile.in
*** Makefile.in 2001/03/07 19:05:24 1.618
--- Makefile.in 2001/03/09 21:15:41
*************** CXX_TARGET_OBJS=@cxx_target_objs@
*** 713,719 ****
# Language-specific object files for C and Objective C.
C_AND_OBJC_OBJS = c-errors.o c-lex.o c-pragma.o c-decl.o c-typeck.o \
c-convert.o c-aux-info.o c-common.o c-format.o c-semantics.o c-dump.o \
! libcpp.a $(C_TARGET_OBJS)
# Language-specific object files for C.
C_OBJS = c-parse.o c-lang.o $(C_AND_OBJC_OBJS)
--- 713,720 ----
# Language-specific object files for C and Objective C.
C_AND_OBJC_OBJS = c-errors.o c-lex.o c-pragma.o c-decl.o c-typeck.o \
c-convert.o c-aux-info.o c-common.o c-format.o c-semantics.o c-dump.o \
! libcpp.a $(C_TARGET_OBJS) \
! tree-cfg.o tree-dfa.o tree-ssa.o tree-opt.o
# Language-specific object files for C.
C_OBJS = c-parse.o c-lang.o $(C_AND_OBJC_OBJS)
*************** $(srcdir)/c-parse.y: c-parse.in
*** 1155,1161 ****
c-decl.o : c-decl.c $(CONFIG_H) system.h $(TREE_H) $(RTL_H) $(C_TREE_H) \
$(GGC_H) c-lex.h flags.h function.h output.h $(EXPR_H) \
! toplev.h intl.h
c-typeck.o : c-typeck.c $(CONFIG_H) system.h $(TREE_H) $(C_TREE_H) \
flags.h intl.h output.h $(EXPR_H) $(RTL_H) toplev.h
c-lang.o : c-lang.c $(CONFIG_H) system.h $(TREE_H) $(C_TREE_H) \
--- 1156,1162 ----
c-decl.o : c-decl.c $(CONFIG_H) system.h $(TREE_H) $(RTL_H) $(C_TREE_H) \
$(GGC_H) c-lex.h flags.h function.h output.h $(EXPR_H) \
! toplev.h intl.h tree-opt.h
c-typeck.o : c-typeck.c $(CONFIG_H) system.h $(TREE_H) $(C_TREE_H) \
flags.h intl.h output.h $(EXPR_H) $(RTL_H) toplev.h
c-lang.o : c-lang.c $(CONFIG_H) system.h $(TREE_H) $(C_TREE_H) \
*************** convert.o: convert.c $(CONFIG_H) system.
*** 1318,1323 ****
--- 1319,1332 ----
tree.o : tree.c $(CONFIG_H) system.h $(TREE_H) flags.h function.h toplev.h \
$(GGC_H) $(HASHTAB_H) output.h
+ tree-ssa.o : tree-ssa.c tree-opt.h tree-flow.h $(CONFIG_H) system.h $(RTL_H) \
+ $(TREE_H) output.h
+ tree-cfg.o : tree-cfg.c tree-opt.h tree-flow.h $(CONFIG_H) system.h $(RTL_H) \
+ $(TREE_H) output.h
+ tree-dfa.o : tree-dfa.c tree-opt.h tree-flow.h $(CONFIG_H) system.h $(RTL_H) \
+ $(TREE_H) output.h
+ tree-opt.o : tree-opt.c tree-opt.h tree-flow.h $(CONFIG_H) system.h \
+ $(RTL_H) $(TREE_H) output.h
print-tree.o : print-tree.c $(CONFIG_H) system.h $(TREE_H) $(GGC_H)
stor-layout.o : stor-layout.c $(CONFIG_H) system.h $(TREE_H) flags.h \
function.h $(EXPR_H) $(RTL_H) toplev.h $(GGC_H)
Index: gcc/basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.87
diff -d -c -p -r1.87 basic-block.h
*** basic-block.h 2001/01/11 17:02:44 1.87
--- basic-block.h 2001/03/09 21:15:41
*************** Boston, MA 02111-1307, USA. */
*** 26,31 ****
--- 26,48 ----
#include "varray.h"
#include "partition.h"
+ /* Generic IL instructions. By default, we use RTL, but modules dealing
+ with the tree optimizer will use trees.
+
+ ??? This is actually very gross. But making ilx a first class
+ structure recognized everyhwere in the compiler involves changing
+ tons of things.
+
+ Since the tree and the rtl optimizer do not share data, and both
+ tree and rtx have the same size, this should not introduce
+ any problems. */
+
+ #ifdef USE_TREE_IL
+ #define ilx tree
+ #else
+ #define ilx rtx
+ #endif
+
/* Head of register set linked list. */
typedef bitmap_head regset_head;
/* A pointer to a regset_head. */
*************** typedef struct edge_def {
*** 120,126 ****
struct basic_block_def *src, *dest;
/* Instructions queued on the edge. */
! rtx insns;
/* Auxiliary info specific to a pass. */
void *aux;
--- 137,143 ----
struct basic_block_def *src, *dest;
/* Instructions queued on the edge. */
! ilx insns;
/* Auxiliary info specific to a pass. */
void *aux;
*************** typedef struct edge_def {
*** 156,162 ****
/* Basic block information indexed by block number. */
typedef struct basic_block_def {
/* The first and last insns of the block. */
! rtx head, end;
/* The edges into and out of the block. */
edge pred, succ;
--- 173,179 ----
/* Basic block information indexed by block number. */
typedef struct basic_block_def {
/* The first and last insns of the block. */
! ilx head, end;
/* The edges into and out of the block. */
edge pred, succ;
*************** extern int flow_delete_block PARAMS ((b
*** 262,267 ****
--- 279,287 ----
extern void merge_blocks_nomove PARAMS ((basic_block, basic_block));
extern void tidy_fallthru_edge PARAMS ((edge, basic_block,
basic_block));
+ extern void dump_edge_info PARAMS ((FILE *, edge, int));
+ extern void clear_edges PARAMS ((void));
+ extern void mark_critical_edges PARAMS ((void));
/* Structure to hold information for each natural loop. */
struct loop
*************** struct loop
*** 344,373 ****
disappear as loop.c is converted to use the CFG. */
/* Non-zero if the loop has a NOTE_INSN_LOOP_VTOP. */
! rtx vtop;
/* Non-zero if the loop has a NOTE_INSN_LOOP_CONT.
A continue statement will generate a branch to NEXT_INSN (cont). */
! rtx cont;
/* The dominator of cont. */
! rtx cont_dominator;
/* The NOTE_INSN_LOOP_BEG. */
! rtx start;
/* The NOTE_INSN_LOOP_END. */
! rtx end;
/* For a rotated loop that is entered near the bottom,
this is the label at the top. Otherwise it is zero. */
! rtx top;
/* Place in the loop where control enters. */
! rtx scan_start;
/* The position where to sink insns out of the loop. */
! rtx sink;
/* List of all LABEL_REFs which refer to code labels outside the
loop. Used by routines that need to know all loop exits, such as
--- 364,393 ----
disappear as loop.c is converted to use the CFG. */
/* Non-zero if the loop has a NOTE_INSN_LOOP_VTOP. */
! ilx vtop;
/* Non-zero if the loop has a NOTE_INSN_LOOP_CONT.
A continue statement will generate a branch to NEXT_INSN (cont). */
! ilx cont;
/* The dominator of cont. */
! ilx cont_dominator;
/* The NOTE_INSN_LOOP_BEG. */
! ilx start;
/* The NOTE_INSN_LOOP_END. */
! ilx end;
/* For a rotated loop that is entered near the bottom,
this is the label at the top. Otherwise it is zero. */
! ilx top;
/* Place in the loop where control enters. */
! ilx scan_start;
/* The position where to sink insns out of the loop. */
! ilx sink;
/* List of all LABEL_REFs which refer to code labels outside the
loop. Used by routines that need to know all loop exits, such as
*************** struct loop
*** 378,384 ****
dead after a return, so the presense of a return does not affect
any of the optimizations that use this info. It is simpler to
just not include return instructions on this list. */
! rtx exit_labels;
/* The number of LABEL_REFs on exit_labels for this loop and all
loops nested inside it. */
--- 398,404 ----
dead after a return, so the presense of a return does not affect
any of the optimizations that use this info. It is simpler to
just not include return instructions on this list. */
! ilx exit_labels;
/* The number of LABEL_REFs on exit_labels for this loop and all
loops nested inside it. */
Index: gcc/c-decl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-decl.c,v
retrieving revision 1.213
diff -d -c -p -r1.213 c-decl.c
*** c-decl.c 2001/03/02 21:41:35 1.213
--- c-decl.c 2001/03/09 21:15:41
*************** Boston, MA 02111-1307, USA. */
*** 41,46 ****
--- 41,47 ----
#include "ggc.h"
#include "tm_p.h"
#include "cpplib.h"
+ #include "tree-opt.h"
/* In grokdeclarator, distinguish syntactic contexts of declarators. */
enum decl_context
*************** c_expand_body (fndecl, nested_p)
*** 6692,6697 ****
--- 6693,6705 ----
semantic analysis; this code just generates RTL. */
if (flag_syntax_only)
return;
+
+ /* Invoke the high-level tree optimizer. */
+ if (flag_tree_optimizer)
+ {
+ init_tree_opt ();
+ optimize_tree (DECL_SAVED_TREE (fndecl));
+ }
/* Squirrel away our current state. */
if (nested_p)
Index: gcc/flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.59
diff -d -c -p -r1.59 flags.h
*** flags.h 2001/03/07 19:29:35 1.59
--- flags.h 2001/03/09 21:15:42
*************** extern int flag_eliminate_dwarf2_dups;
*** 624,627 ****
--- 624,629 ----
and to print them when we are done. */
extern int flag_detailed_statistics;
+ /* Enable tree-based optimizer. */
+ extern int flag_tree_optimizer;
#endif /* GCC_FLAGS_H */
Index: gcc/flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.381
diff -d -c -p -r1.381 flow.c
*** flow.c 2001/02/24 02:32:33 1.381
--- flow.c 2001/03/09 21:15:43
*************** typedef struct depth_first_search_dsS *d
*** 359,371 ****
static int count_basic_blocks PARAMS ((rtx));
static void find_basic_blocks_1 PARAMS ((rtx));
static rtx find_label_refs PARAMS ((rtx, rtx));
- static void clear_edges PARAMS ((void));
static void make_edges PARAMS ((rtx));
static void make_label_edge PARAMS ((sbitmap *, basic_block,
rtx, int));
static void make_eh_edge PARAMS ((sbitmap *, eh_nesting_info *,
basic_block, rtx, int));
- static void mark_critical_edges PARAMS ((void));
static void move_stray_eh_region_notes PARAMS ((void));
static void record_active_eh_regions PARAMS ((rtx));
--- 359,369 ----
*************** static void mark_used_regs PARAMS ((str
*** 434,440 ****
rtx, rtx, rtx));
void dump_flow_info PARAMS ((FILE *));
void debug_flow_info PARAMS ((void));
- static void dump_edge_info PARAMS ((FILE *, edge, int));
static void print_rtl_and_abort_fcn PARAMS ((const char *, int,
const char *))
ATTRIBUTE_NORETURN;
--- 432,437 ----
*************** compute_bb_for_insn (max)
*** 1152,1158 ****
/* Free the memory associated with the edge structures. */
! static void
clear_edges ()
{
int i;
--- 1149,1155 ----
/* Free the memory associated with the edge structures. */
! void
clear_edges ()
{
int i;
*************** record_active_eh_regions (f)
*** 1588,1594 ****
/* Identify critical edges and set the bits appropriately. */
! static void
mark_critical_edges ()
{
int i, n = n_basic_blocks;
--- 1585,1591 ----
/* Identify critical edges and set the bits appropriately. */
! void
mark_critical_edges ()
{
int i, n = n_basic_blocks;
*************** debug_flow_info ()
*** 6525,6531 ****
dump_flow_info (stderr);
}
! static void
dump_edge_info (file, e, do_succ)
FILE *file;
edge e;
--- 6522,6528 ----
dump_flow_info (stderr);
}
! void
dump_edge_info (file, e, do_succ)
FILE *file;
edge e;
Index: gcc/ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ssa.c,v
retrieving revision 1.25
diff -d -c -p -r1.25 ssa.c
*** ssa.c 2000/11/19 13:15:50 1.25
--- ssa.c 2001/03/09 21:15:43
*************** static int remove_phi_alternative
*** 170,177 ****
PARAMS ((rtx, int));
static void compute_dominance_frontiers_1
PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
- static void compute_dominance_frontiers
- PARAMS ((sbitmap *frontiers, int *idom));
static void find_evaluations_1
PARAMS ((rtx dest, rtx set, void *data));
static void find_evaluations
--- 170,175 ----
*************** compute_dominance_frontiers_1 (frontiers
*** 561,567 ****
}
}
! static void
compute_dominance_frontiers (frontiers, idom)
sbitmap *frontiers;
int *idom;
--- 559,565 ----
}
}
! void
compute_dominance_frontiers (frontiers, idom)
sbitmap *frontiers;
int *idom;
Index: gcc/ssa.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ssa.h,v
retrieving revision 1.1
diff -d -c -p -r1.1 ssa.h
*** ssa.h 2000/08/02 04:21:27 1.1
--- ssa.h 2001/03/09 21:15:43
*************** typedef int (*successor_phi_fn)
*** 27,32 ****
--- 27,33 ----
extern int for_each_successor_phi PARAMS ((basic_block bb,
successor_phi_fn,
void *));
+ void compute_dominance_frontiers PARAMS ((sbitmap *frontiers, int *idom));
/* Optimizations. */
/* In dce.c */
Index: gcc/toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.435
diff -d -c -p -r1.435 toplev.c
*** toplev.c 2001/03/07 19:29:37 1.435
--- toplev.c 2001/03/09 21:15:44
*************** int flag_bounds_check = 0;
*** 900,905 ****
--- 900,908 ----
one, unconditionally renumber instruction UIDs. */
int flag_renumber_insns = 1;
+ /* Enable tree-based optimizer. */
+ int flag_tree_optimizer = 0;
+
/* Values of the -falign-* flags: how much to align labels in code.
0 means `use default', 1 means `don't align'.
For each variable, there is an _log variant which is the power
*************** lang_independent_options f_options[] =
*** 1174,1179 ****
--- 1177,1184 ----
"Report on permanent memory allocation at end of run"},
{ "trapv", &flag_trapv, 1,
"Trap for signed overflow in addition / subtraction / multiplication." },
+ { "tree-optimizer", &flag_tree_optimizer, 1,
+ "Enable the high-level optimizer." },
};
/* Table of language-specific options. */
Index: gcc/tree-cfg.c
===================================================================
RCS file: tree-cfg.c
diff -N tree-cfg.c
*** /dev/null Tue May 5 13:32:27 1998
--- tree-cfg.c Fri Mar 9 13:15:44 2001
***************
*** 0 ****
--- 1,1105 ----
+ /* Control flow functions for trees.
+ Copyright (C) 2001 Free Software Foundation, Inc.
+ Contributed by Diego Novillo <dnovillo@redhat.com>
+
+ This file is part of GNU CC.
+
+ GNU CC 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.
+
+ GNU CC 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 GNU CC; see the file COPYING. If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+ /* Make sure that structures shared with the RTL optimizer use trees
+ instead of rtx. */
+ #define USE_TREE_IL 1
+
+ #include "config.h"
+ #include "system.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "errors.h"
+ #include "expr.h"
+ #include "c-common.h"
+ #include "ggc.h"
+ #include "tree-opt.h"
+ #include "tree-flow.h"
+
+ #define DEBUG_TREE_FLOW 1 /* Force debugging on. */
+
+ #ifdef DEBUG_TREE_FLOW
+ #undef DEBUG_TREE_FLOW
+ #define DEBUG_TREE_FLOW(level) debug_tree_flow (level, __FILE__, __LINE__)
+
+ static int debug_tree_flow PARAMS ((int, const char *, int));
+
+ static int
+ debug_tree_flow (level, filename, line)
+ int level;
+ const char *filename;
+ int line;
+ {
+ char *trigger = getenv ("DEBUG_TREE_FLOW");
+ if (trigger && atoi (trigger) >= level)
+ {
+ if (atoi (trigger) > level)
+ {
+ fprintf (stderr, "\n----------------------------------------------------------------------------\n\n");
+ fprintf (stderr, "%s:%d\n", filename, line);
+ }
+
+ return 1;
+ }
+
+ return 0;
+
+ }
+ #endif /* DEBUG_TREE_FLOW */
+
+
+
+
+ /* Index number for the next basic block created in create_bb(). Reset
+ to zero by tree_find_basic_blocks_1. */
+
+ static int cur_bb_index = 0;
+
+ /* Structure used in a pre-order traversal of the function tree to count
+ basic blocks. */
+
+ struct bb_count_def
+ {
+ int start_new_bb; /* 1 to start a new block with the next tree. */
+ int n; /* Number of basic blocks. */
+ };
+ typedef struct bb_count_def bb_count;
+
+
+ /* Local helper functions. */
+
+ static int count_basic_blocks PARAMS ((tree));
+ static tree count_bb PARAMS ((tree *, int *, void *));
+ static void create_flowgraph_for PARAMS ((tree, basic_block));
+ static basic_block start_bb_with PARAMS ((tree));
+ static basic_block create_bb PARAMS ((tree, tree));
+ static void map_tree_to_bb PARAMS ((tree, basic_block));
+ static void make_edges PARAMS ((void));
+ static void make_for_stmt_edges PARAMS ((sbitmap *, basic_block));
+ static void make_while_stmt_edges PARAMS ((sbitmap *, basic_block));
+ static void make_do_stmt_edges PARAMS ((sbitmap *, basic_block));
+ static void make_if_stmt_edges PARAMS ((sbitmap *, basic_block));
+ static void make_clause_edges PARAMS ((sbitmap *, basic_block, tree,
+ basic_block));
+ static void make_switch_stmt_edges PARAMS ((sbitmap *, basic_block));
+ static void make_exit_edges PARAMS ((sbitmap *, tree, basic_block));
+ static tree get_last_stmt PARAMS ((tree));
+ static void make_goto_stmt_edges PARAMS ((sbitmap *, basic_block));
+ static void make_break_stmt_edges PARAMS ((sbitmap *, basic_block));
+ static void make_continue_stmt_edges PARAMS ((sbitmap *, basic_block));
+ static basic_block get_successor_block PARAMS ((tree));
+
+ /* Entry point to the CFG builder for trees. */
+
+ void
+ tree_find_basic_blocks (t, nregs, file)
+ tree t;
+ int nregs ATTRIBUTE_UNUSED;
+ FILE *file ATTRIBUTE_UNUSED;
+ {
+ /* Flush out existing data. */
+ if (basic_block_info != NULL)
+ {
+ int i;
+
+ cur_bb_index = 0;
+ clear_edges ();
+
+ for (i = 0; i < n_basic_blocks; ++i)
+ BASIC_BLOCK (i)->aux = NULL;
+
+ VARRAY_FREE (basic_block_info);
+ }
+
+ n_basic_blocks = count_basic_blocks (t);
+
+ VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
+
+ /* Find the basic blocks for the flowgraph. */
+ create_flowgraph_for (t, NULL);
+
+ #ifdef DEBUG_TREE_FLOW
+ if (DEBUG_TREE_FLOW (2))
+ {
+ int i;
+
+ fprintf (stderr, "\n");
+ fprintf (stderr, ";; Function %s\n\n",
+ IDENTIFIER_POINTER (DECL_NAME (current_function_decl)));
+
+ fprintf (stderr, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
+ for (i = 0; i < n_basic_blocks; i++)
+ tree_debug_bb (BASIC_BLOCK (i));
+ }
+ #endif /* DEBUG_TREE_FLOW */
+
+ /* Create the edges of the flowgraph. */
+ make_edges ();
+ mark_critical_edges ();
+
+ #ifdef DEBUG_TREE_FLOW
+ if (DEBUG_TREE_FLOW (1))
+ {
+ int i;
+
+ fprintf (stderr, "\n");
+ fprintf (stderr, ";; Function %s\n\n",
+ IDENTIFIER_POINTER (DECL_NAME (current_function_decl)));
+
+ fprintf (stderr, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
+ for (i = 0; i < n_basic_blocks; i++)
+ tree_debug_bb (BASIC_BLOCK (i));
+ }
+ #endif /* DEBUG_TREE_FLOW */
+ }
+
+
+
+ /* Walk the function tree counting the number of basic blocks. */
+
+ static int
+ count_basic_blocks (t)
+ tree t;
+ {
+ bb_count f;
+
+ f.start_new_bb = 1;
+ f.n = 0;
+ walk_stmt_tree (&t, count_bb, (void *)&f);
+
+ return f.n;
+ }
+
+
+ /* Callback for walk_stmt_tree to count basic blocks. */
+
+ static tree
+ count_bb (tp, walk_subtrees, data)
+ tree *tp;
+ int *walk_subtrees ATTRIBUTE_UNUSED;
+ void *data;
+ {
+ bb_count *f = (bb_count *)data;
+ tree t = *tp;
+
+ if (f->start_new_bb)
+ {
+ if (TREE_CODE (t) != FOR_STMT)
+ f->n++;
+ else
+ {
+ /* A FOR_STMT header needs up to 3 blocks. The FOR_INIT
+ expression will be hit on the next iteration of
+ walk_stmt_tree, so we don't need to consider it now.
+ However, FOR_COND and FOR_EXPR are not traversed. */
+ if (FOR_COND (t)) f->n++;
+ if (FOR_EXPR (t)) f->n++;
+ }
+
+ f->start_new_bb = 0;
+ }
+
+ if (stmt_ends_bb_p (t))
+ f->start_new_bb = 1;
+
+ return NULL_TREE;
+ }
+
+
+ /* Build a flowgraph for the tree starting with t. Make `control_parent'
+ the block dominating all the nodes in the new flowgraph. */
+
+ static void
+ create_flowgraph_for (t, control_parent)
+ tree t;
+ basic_block control_parent;
+ {
+ int start_new_bb = 1;
+ basic_block cur_bb = NULL;
+
+ while (t)
+ {
+ enum tree_code code = TREE_CODE (t);
+
+ if (statement_code_p (code))
+ {
+ /* Is this the first statement of a new basic block? */
+ if (start_new_bb)
+ {
+ cur_bb = start_bb_with (t);
+ set_bb_parent (cur_bb, control_parent);
+ start_new_bb = 0;
+ }
+
+ if (cur_bb == NULL)
+ abort ();
+
+ /* Associate the tree to the current block. */
+ map_tree_to_bb (t, cur_bb);
+
+ /* Is this the last statement of the current block? */
+ if (stmt_ends_bb_p (t))
+ {
+ if (!END_TREE (cur_bb))
+ SET_END_TREE (cur_bb, t);
+
+ start_new_bb = 1;
+ cur_bb = NULL;
+ }
+ }
+
+ if (TREE_CODE (t) == COMPOUND_STMT)
+ t = COMPOUND_BODY (t);
+ else
+ t = TREE_CHAIN (t);
+ }
+
+ /* ??? Special case. If the body of statements was empty, we end up
+ with a half finished block in 'cur_bb'. To avoid unpleasant
+ situations later on, we make the head and the end tree the same. */
+ if (cur_bb && !END_TREE (cur_bb))
+ SET_END_TREE (cur_bb, HEAD_TREE (cur_bb));
+ }
+
+
+ /* Start a new basic block (or blocks) with the given tree. If the
+ tree is a control flow statement, a new subgraph will be created
+ recursively. */
+
+ static basic_block
+ start_bb_with (t)
+ tree t;
+ {
+ basic_block bb;
+
+ /* Special case for blocks whose header is a COMPOUND_STMT tree. We
+ really want the first statement in that compound statement to be the
+ head. */
+ if (TREE_CODE (t) == COMPOUND_STMT)
+ t = COMPOUND_BODY (t);
+
+ /* Also ignore opening scope statements. */
+ if (TREE_CODE (t) == SCOPE_STMT && SCOPE_BEGIN_P (t))
+ t = TREE_CHAIN (t);
+
+ if (!t)
+ abort ();
+
+ switch (TREE_CODE (t))
+ {
+ case FOR_STMT:
+ {
+ basic_block cond, expr;
+
+ bb = create_bb (t, FOR_INIT_STMT (t));
+
+ if (FOR_COND (t))
+ {
+ cond = create_bb (FOR_COND (t), FOR_COND (t));
+ set_bb_parent (cond, bb);
+ }
+
+ if (FOR_EXPR (t))
+ {
+ expr = create_bb (FOR_EXPR (t), FOR_EXPR (t));
+ set_bb_parent (expr, bb);
+ }
+
+ create_flowgraph_for (FOR_BODY (t), bb);
+ break;
+ }
+
+ case IF_STMT:
+ bb = create_bb (t, IF_COND (t));
+ create_flowgraph_for (THEN_CLAUSE (t), bb);
+ create_flowgraph_for (ELSE_CLAUSE (t), bb);
+ break;
+
+ case WHILE_STMT:
+ bb = create_bb (t, WHILE_COND (t));
+ create_flowgraph_for (WHILE_BODY (t), bb);
+ break;
+
+ case SWITCH_STMT:
+ bb = create_bb (t, t);
+ create_flowgraph_for (SWITCH_BODY (t), bb);
+ break;
+
+ case DO_STMT:
+ bb = create_bb (t, DO_COND (t));
+ create_flowgraph_for (DO_BODY (t), bb);
+ break;
+
+ case RETURN_STMT:
+ bb = create_bb (t, RETURN_EXPR (t));
+ break;
+
+ default:
+ bb = create_bb (t, NULL_TREE);
+ }
+
+ return bb;
+ }
+
+
+ /* Creates and returns a new basic block. */
+
+ static basic_block
+ create_bb (head, end)
+ tree head;
+ tree end;
+ {
+ basic_block bb;
+
+ bb = (basic_block) ggc_alloc (sizeof (*bb));
+ memset (bb, 0, sizeof (*bb));
+
+ SET_HEAD_TREE (bb, head);
+ SET_END_TREE (bb, end);
+ bb->index = cur_bb_index;
+
+ /* Associate the newly created block to the head and end tree. */
+ if (head) map_tree_to_bb (head, bb);
+ if (end) map_tree_to_bb (end, bb);
+
+ /* Add the new block to the BASIC_BLOCK array. */
+ BASIC_BLOCK (cur_bb_index++) = bb;
+
+ return bb;
+ }
+
+
+ /* Map a tree and its subtrees to a basic block. */
+
+ static void
+ map_tree_to_bb (t, bb)
+ tree t;
+ basic_block bb;
+ {
+ tree_ann ann;
+
+ if (!t)
+ return;
+
+ ann = get_tree_ann (t);
+ ann->bb = bb;
+ }
+
+
+ /* Set the control parent of a basic block. */
+
+ void
+ set_bb_parent (bb, parent)
+ basic_block bb;
+ basic_block parent;
+ {
+ basic_block_ann ann = get_bb_ann (bb);
+ ann->parent = parent;
+ }
+
+
+ /* Get the annotation for the given block. Create a new one if
+ necessary. */
+
+ basic_block_ann
+ get_bb_ann (bb)
+ basic_block bb;
+ {
+ basic_block_ann ann = BB_ANN (bb);
+
+ if (ann == NULL)
+ {
+ ann = (basic_block_ann) ggc_alloc (sizeof (*ann));
+ memset ((void *)ann, 0, sizeof (*ann));
+
+ bb->aux = (void *)ann;
+ }
+
+ return ann;
+ }
+
+
+
+ /* Join all the blocks in the flowgraph. */
+
+ static void
+ make_edges ()
+ {
+ int i;
+ sbitmap *edge_cache;
+
+ edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ sbitmap_vector_zero (edge_cache, n_basic_blocks);
+
+ /* By nature of the way these get numbered, block 0 is always the entry. */
+ make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ tree head, end;
+ basic_block bb = BASIC_BLOCK (i);
+
+ head = HEAD_TREE (bb);
+ end = END_TREE (bb);
+
+ if (is_ctrl_stmt_p (head))
+ {
+ /* Control nodes define several edges to each of the elements in
+ the control structure. */
+ switch (TREE_CODE (head))
+ {
+ case FOR_STMT:
+ make_for_stmt_edges (edge_cache, bb);
+ break;
+
+ case WHILE_STMT:
+ make_while_stmt_edges (edge_cache, bb);
+ break;
+
+ case DO_STMT:
+ make_do_stmt_edges (edge_cache, bb);
+ break;
+
+ case IF_STMT:
+ make_if_stmt_edges (edge_cache, bb);
+ break;
+
+ case SWITCH_STMT:
+ make_switch_stmt_edges (edge_cache, bb);
+ break;
+
+ default:
+ abort ();
+ }
+ }
+ else
+ {
+ /* Non-control nodes get a fallthru edge to their chain block.
+ (the block for the chain of the last statement in the
+ block). Control flow altering statements (goto, break,
+ continue) need an edge to the corresponding target block. */
+ switch (TREE_CODE (end))
+ {
+ case RETURN_STMT:
+ make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
+ break;
+
+ case BREAK_STMT:
+ make_break_stmt_edges (edge_cache, bb);
+ break;
+
+ case CONTINUE_STMT:
+ make_continue_stmt_edges (edge_cache, bb);
+ break;
+
+ case GOTO_STMT:
+ make_goto_stmt_edges (edge_cache, bb);
+ break;
+
+ default:
+ {
+ tree end = END_TREE (bb);
+ tree chain = TREE_CHAIN (end);
+
+ /* For regular blocks, add a fallthru edge to the next
+ statement's block. */
+ if (chain != NULL_TREE)
+ make_edge (edge_cache, bb, TREE_BB (chain), EDGE_FALLTHRU);
+ }
+ }
+ }
+ }
+
+ if (edge_cache)
+ sbitmap_vector_free (edge_cache);
+ }
+
+
+ /* Create edges for a FOR_STMT structure that starts at basic block bb. */
+
+ static void
+ make_for_stmt_edges (edge_cache, bb)
+ sbitmap *edge_cache;
+ basic_block bb;
+ {
+ tree entry = HEAD_TREE (bb);
+ tree chain = TREE_CHAIN (entry);
+ basic_block cond_bb, expr_bb, body_bb;
+
+ if (TREE_CODE (entry) != FOR_STMT)
+ abort ();
+
+ cond_bb = (FOR_COND (entry)) ? TREE_BB (FOR_COND (entry)) : NULL;
+ expr_bb = (FOR_EXPR (entry)) ? TREE_BB (FOR_EXPR (entry)) : NULL;
+ body_bb = (FOR_BODY (entry)) ? TREE_BB (FOR_BODY (entry)) : NULL;
+
+ /* Create the edges.
+
+ FOR_STMT
+ |
+ v
+ +-- FOR_COND <----------+
+ | | |
+ | | FOR_EXPR
+ | | ^
+ | v |
+ | FOR_BODY -----------+
+ |
+ |
+ +--> EXIT
+
+ - If the loop does not have a condition expression, edges involving
+ the condition block, go to the loop header ("infinite" loops).
+
+ - If the loop does not have an expression block, we replace it with
+ the condition block.
+
+ - Similarly, if the body is empty, we replace it with the
+ expression block. Hence, loops with neither component will reduce
+ to the header block with a self-referencing edge. */
+
+ if (cond_bb == NULL)
+ cond_bb = bb;
+
+ if (expr_bb == NULL)
+ expr_bb = cond_bb;
+
+ if (body_bb == NULL)
+ body_bb = expr_bb;
+
+ make_edge (edge_cache, bb, cond_bb, 0);
+ make_edge (edge_cache, cond_bb, body_bb, 0);
+ make_edge (edge_cache, expr_bb, cond_bb, 0);
+ make_exit_edges (edge_cache, FOR_BODY (entry), expr_bb);
+
+ /* If there are more statements after the loop, join the condition basic
+ block to them. */
+ if (chain)
+ make_edge (edge_cache, cond_bb, TREE_BB (chain), 0);
+ }
+
+
+ /* Create the edges for a WHILE_STMT structure starting with bb. */
+
+ static void
+ make_while_stmt_edges (edge_cache, bb)
+ sbitmap *edge_cache;
+ basic_block bb;
+ {
+ tree entry = HEAD_TREE (bb);
+ tree chain = TREE_CHAIN (entry);
+ basic_block body_bb;
+
+ if (TREE_CODE (entry) != WHILE_STMT)
+ abort ();
+
+ body_bb = (WHILE_BODY (entry)) ? TREE_BB (WHILE_BODY (entry)) : NULL;
+
+ /* Create the edges.
+
+ +-- WHILE_STMT <-+
+ | | |
+ | v |
+ | WHILE_BODY --+
+ |
+ +--> EXIT
+
+ If the body doesn't exist, we use the header instead. */
+
+ if (body_bb == NULL)
+ body_bb = bb;
+
+ make_edge (edge_cache, bb, body_bb, 0);
+ make_exit_edges (edge_cache, WHILE_BODY (entry), bb);
+
+ /* If there are more statements after the loop, join the condition basic
+ block to them. */
+ if (chain)
+ make_edge (edge_cache, bb, TREE_BB (chain), 0);
+ }
+
+
+ /* Create the edges for a DO_STMT structure starting with bb. */
+
+ static void
+ make_do_stmt_edges (edge_cache, bb)
+ sbitmap *edge_cache;
+ basic_block bb;
+ {
+ tree entry = HEAD_TREE (bb);
+ tree chain = TREE_CHAIN (entry);
+ basic_block body_bb;
+ edge e;
+
+ if (TREE_CODE (entry) != DO_STMT)
+ abort ();
+
+ body_bb = TREE_BB (DO_BODY (entry));
+
+ /* Create the edges.
+
+ DO_BODY <-+
+ | |
+ v |
+ DO_STMT --+
+ |
+ v
+ EXIT
+
+ If the body doesn't exist, we use the header instead. */
+
+ if (body_bb == NULL)
+ body_bb = bb;
+
+ /* Before joining the body and the condition blocks, we need to adjust
+ any previous edges coming into the condition block.
+
+ This is necessary because trees are chained such that for a DO
+ loop, the condition comes before the body. If we don't make this
+ transformation, this subgraph will have the semantics of a WHILE
+ loop. */
+
+ for (e = bb->pred; e; )
+ {
+ edge tmp = e;
+ make_edge (edge_cache, e->src, body_bb, e->flags);
+ e = e->pred_next;
+ remove_edge (tmp);
+ }
+
+ make_exit_edges (edge_cache, DO_BODY (entry), bb);
+ make_edge (edge_cache, bb, body_bb, 0);
+
+ /* If there are more statements after the loop, join the condition basic
+ block to them. */
+ if (chain)
+ make_edge (edge_cache, bb, TREE_BB (chain), 0);
+ }
+
+
+ /* Create the edges for an IF_STMT structure starting with bb. */
+
+ static void
+ make_if_stmt_edges (edge_cache, bb)
+ sbitmap *edge_cache;
+ basic_block bb;
+ {
+ tree entry = HEAD_TREE (bb);
+ tree chain = TREE_CHAIN (entry);
+ basic_block post_body_bb = (chain) ? TREE_BB (chain) : NULL;
+
+ make_clause_edges (edge_cache, bb, THEN_CLAUSE (entry), post_body_bb);
+ make_clause_edges (edge_cache, bb, ELSE_CLAUSE (entry), post_body_bb);
+ }
+
+
+ /* Create edges between the predicate of a conditional statement to its
+ THEN_CLAUSE or ELSE_CLAUSE body. `bb' is the basic block for IF_STMT,
+ `clause_bb' is either THEN_CLAUSE or ELSE_CLAUSE */
+
+ static void
+ make_clause_edges (edge_cache, bb, clause_tree, post_body_bb)
+ sbitmap *edge_cache;
+ basic_block bb;
+ tree clause_tree;
+ basic_block post_body_bb;
+ {
+ basic_block clause_bb;
+
+ clause_bb = (clause_tree) ? TREE_BB (clause_tree) : NULL;
+
+ if (clause_bb)
+ {
+ /* Join the conditional node to the first block in the clause body. */
+ make_edge (edge_cache, bb, clause_bb, 0);
+ make_exit_edges (edge_cache, clause_tree, post_body_bb);
+ }
+ else
+ {
+ /* No clause body. Make an edge to the first block after the if()
+ statement (if any). */
+ if (post_body_bb)
+ make_edge (edge_cache, bb, post_body_bb, 0);
+ }
+ }
+
+
+ /* Create edges for a SWITCH_STMT structure starting at block bb. */
+
+ static void
+ make_switch_stmt_edges (edge_cache, bb)
+ sbitmap *edge_cache;
+ basic_block bb;
+ {
+ tree t, body;
+ tree entry = HEAD_TREE (bb);
+
+ if (TREE_CODE (entry) != SWITCH_STMT)
+ abort ();
+
+ /* Make an edge to each case label in the body. */
+ body = SWITCH_BODY (entry);
+ if (TREE_CODE (body) == COMPOUND_STMT)
+ body = COMPOUND_BODY (body);
+
+ for (t = body; t; t = TREE_CHAIN (t))
+ if (TREE_CODE (t) == CASE_LABEL)
+ make_edge (edge_cache, bb, TREE_BB (t), 0);
+
+ /* Add exit edges for all the case labels. */
+ make_exit_edges (edge_cache, body, get_successor_block (entry));
+ }
+
+
+ /* Creates one or more exit edges out of a body of statements (either a
+ single statement or a COMPOUND_STMT) into the given basic block. It
+ looks for the last statement in the body and creates an edge from that
+ statement's block into `post_body_bb'. If the last statement is a
+ control statement (IF_STMT, WHILE_STMT, etc) the process is repeated
+ recursively. */
+
+ static void
+ make_exit_edges (edge_cache, body, post_body_bb)
+ sbitmap *edge_cache;
+ tree body;
+ basic_block post_body_bb;
+ {
+ enum tree_code code;
+ tree last;
+ basic_block last_body_bb;
+
+ if (post_body_bb == NULL || body == NULL_TREE)
+ return;
+
+ /* Look for the last basic block in the body. */
+ last = get_last_stmt (body);
+ last_body_bb = TREE_BB (last);
+ make_edge (edge_cache, last_body_bb, post_body_bb, 0);
+
+ /* If the last statement in the body is a control statement, we
+ also need to join its last node to post_body_bb. We need to do this
+ because the last node of the interior control structure will not have
+ a chain to our successor. */
+ code = TREE_CODE (last);
+
+ if (code == IF_STMT)
+ {
+ make_exit_edges (edge_cache, THEN_CLAUSE (last), post_body_bb);
+ make_exit_edges (edge_cache, ELSE_CLAUSE (last), post_body_bb);
+ }
+
+ else if (code == FOR_STMT)
+ make_exit_edges (edge_cache, FOR_COND (last), post_body_bb);
+
+ else if (code == WHILE_STMT)
+ make_exit_edges (edge_cache, WHILE_COND (last), post_body_bb);
+
+ else if (code == DO_STMT)
+ make_exit_edges (edge_cache, DO_COND (last), post_body_bb);
+
+ else if (code == SWITCH_STMT)
+ make_exit_edges (edge_cache, SWITCH_BODY (last), post_body_bb);
+ }
+
+
+ /* Returns the last statement in the given body of statements. */
+
+ static tree
+ get_last_stmt (body)
+ tree body;
+ {
+ tree last = body;
+
+ if (last == NULL_TREE)
+ return NULL_TREE;
+
+ if (TREE_CODE (last) == COMPOUND_STMT)
+ last = COMPOUND_BODY (last);
+
+ while (TREE_CHAIN (last) != NULL_TREE)
+ last = TREE_CHAIN (last);
+
+ if (last == NULL)
+ abort ();
+
+ return last;
+ }
+
+
+ /* Create edges for a goto statement.
+ ??? [BUG] Computed and non-local gotos are not handled. */
+
+ static void
+ make_goto_stmt_edges (edge_cache, bb)
+ sbitmap *edge_cache;
+ basic_block bb;
+ {
+ tree t = END_TREE (bb);
+ tree destination = GOTO_DESTINATION (t);
+
+ /* Destination is a single label. */
+ if (TREE_CODE (destination) == LABEL_DECL)
+ {
+ int i;
+
+ /* Look for the block starting with the destination label. */
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ basic_block target_bb = BASIC_BLOCK (i);
+ tree target = HEAD_TREE (target_bb);
+
+ if (TREE_CODE (target) == LABEL_STMT
+ && LABEL_STMT_LABEL (target) == destination)
+ {
+ make_edge (edge_cache, bb, target_bb, 0);
+ break;
+ }
+ }
+
+ /* ??? We didn't find anything. Is this a non-local goto? */
+ if (i == n_basic_blocks)
+ abort ();
+ }
+ else
+ /* ??? [BUG] Computed goto. Should make an edge to every label in the
+ function. */
+ abort ();
+ }
+
+
+ /* A break statement creates an edge from the break node to the successor
+ node for the break statement's control parent. */
+
+ static void
+ make_break_stmt_edges (edge_cache, bb)
+ sbitmap *edge_cache;
+ basic_block bb;
+ {
+ basic_block chain_bb;
+ basic_block control_parent = BB_PARENT (bb);
+
+ /* A break statement *must* have an enclosing control structure. */
+ if (control_parent == NULL)
+ abort ();
+
+ /* Look for the innermost containing while, for, do or switch structure
+ (ie, ignore if() statements) */
+ while (TREE_CODE (HEAD_TREE (control_parent)) == IF_STMT)
+ control_parent = BB_PARENT (control_parent);
+
+ chain_bb = get_successor_block (HEAD_TREE (control_parent));
+ make_edge (edge_cache, bb, chain_bb, 0);
+ }
+
+
+ /* A continue statement creates an edge from the continue node to the
+ control parent's expression node. */
+
+ static void
+ make_continue_stmt_edges (edge_cache, bb)
+ sbitmap *edge_cache;
+ basic_block bb;
+ {
+ tree t;
+ basic_block control_parent = BB_PARENT (bb);
+
+ /* A continue statement *must* have an enclosing control structure. */
+ if (control_parent == NULL)
+ abort ();
+
+ /* Look for the innermost containing while, for or do structure (ie,
+ ignore if() and switch() statements) */
+ while (TREE_CODE (HEAD_TREE (control_parent)) == IF_STMT
+ || TREE_CODE (HEAD_TREE (control_parent)) == SWITCH_STMT)
+ control_parent = BB_PARENT (control_parent);
+
+ t = HEAD_TREE (control_parent);
+
+ switch (TREE_CODE (t))
+ {
+ case FOR_STMT:
+ make_edge (edge_cache, bb, TREE_BB (FOR_EXPR (t)), 0);
+ break;
+
+ case WHILE_STMT:
+ make_edge (edge_cache, bb, TREE_BB (WHILE_COND (t)), 0);
+ break;
+
+ case DO_STMT:
+ make_edge (edge_cache, bb, TREE_BB (DO_COND (t)), 0);
+ break;
+
+ default:
+ abort ();
+ }
+ }
+
+
+ /* Return the successor block for the given tree's block. If the block has no
+ successors we try the enclosing control structure until we find one. If
+ we reached nesting level 0, return the exit block. */
+
+ static basic_block
+ get_successor_block (t)
+ tree t;
+ {
+ basic_block bb, parent_bb;
+
+ if (t == NULL_TREE)
+ abort ();
+
+ /* If there is a next statement, return its block. */
+ if (TREE_CHAIN (t))
+ return TREE_BB (TREE_CHAIN (t));
+
+ /* This is the last statement. Walk up the control structure to see if
+ our parent has a successor. Iterate until we find one or we reach
+ nesting level 0. */
+ bb = TREE_BB (t);
+ parent_bb = BB_PARENT (bb);
+
+ while (parent_bb && TREE_CHAIN (HEAD_TREE (parent_bb)) == NULL_TREE)
+ parent_bb = BB_PARENT (parent_bb);
+
+ /* If we found an enclosing control statement with a successor, return
+ the successor's basic block. Otherwise, we must be at the top of
+ the control hierarchy. In that case, return the exit block. */
+ if (parent_bb)
+ return (TREE_BB (TREE_CHAIN (HEAD_TREE (parent_bb))));
+ else
+ return EXIT_BLOCK_PTR;
+ }
+
+
+ /* Return 1 if the given tree represents a control statement. */
+
+ int
+ is_ctrl_stmt_p (t)
+ tree t;
+ {
+ return (t != NULL_TREE
+ && (TREE_CODE (t) == FOR_STMT
+ || TREE_CODE (t) == IF_STMT
+ || TREE_CODE (t) == WHILE_STMT
+ || TREE_CODE (t) == SWITCH_STMT
+ || TREE_CODE (t) == DO_STMT));
+ }
+
+
+ /* Return 1 if the given tree should start a new basic block. */
+
+ int
+ stmt_starts_bb_p (t)
+ tree t;
+ {
+ return (t != NULL_TREE
+ && (TREE_CODE (t) == CASE_LABEL
+ || TREE_CODE (t) == LABEL_STMT
+ || TREE_CODE (t) == RETURN_STMT
+ || is_ctrl_stmt_p (t)));
+ }
+
+
+ /* Return 1 if the given tree should be the last in a basic block. */
+
+ int
+ stmt_ends_bb_p (t)
+ tree t;
+ {
+ return (t == NULL_TREE
+ || (TREE_CHAIN (t) == NULL_TREE && TREE_CODE (t) != COMPOUND_STMT)
+ || TREE_CODE (t) == BREAK_STMT
+ || TREE_CODE (t) == CONTINUE_STMT
+ || TREE_CODE (t) == GOTO_STMT
+ || (stmt_starts_bb_p (TREE_CHAIN (t)) && TREE_CODE (t) != SCOPE_STMT)
+ || is_ctrl_stmt_p (t));
+ }
+
+
+ void
+ tree_dump_bb (outf, prefix, bb, indent)
+ FILE *outf;
+ const char *prefix;
+ basic_block bb;
+ int indent;
+ {
+ edge e;
+ tree head = HEAD_TREE (bb);
+ tree end = END_TREE (bb);
+ char *s_indent;
+
+ s_indent = (char *) alloca ((size_t)indent + 1);
+ memset ((void *)s_indent, ' ', (size_t)indent);
+ s_indent[indent] = '\0';
+
+ fprintf (outf, "%s%sBasic block %d: loop depth %d, count %d\n",
+ s_indent, prefix, bb->index, bb->loop_depth, bb->count);
+
+ fprintf (outf, "%s%sPredecessors: ", s_indent, prefix);
+ for (e = bb->pred; e; e = e->pred_next)
+ dump_edge_info (outf, e, 0);
+ putc ('\n', outf);
+
+ fprintf (outf, "%s%sSuccessors: ", s_indent, prefix);
+ for (e = bb->succ; e; e = e->succ_next)
+ dump_edge_info (outf, e, 1);
+ putc ('\n', outf);
+
+ fprintf (outf, "%s%sHead: ", s_indent, prefix);
+ if (head)
+ {
+ print_node_brief (outf, "", head, 0);
+ fprintf (outf, " (line: %d)\n", STMT_LINENO (head));
+ }
+ else
+ fputs ("nil\n", outf);
+
+ fprintf (outf, "%s%sEnd: ", s_indent, prefix);
+ if (end)
+ {
+ print_node_brief (outf, "", end, 0);
+ fprintf (outf, " (line: %d)\n", STMT_LINENO (end));
+ }
+ else
+ fputs ("nil\n", outf);
+
+ fprintf (outf, "%s%sParent block: ", s_indent, prefix);
+ if (BB_PARENT (bb))
+ fprintf (outf, "%d\n", BB_PARENT (bb)->index);
+ else
+ fputs ("nil\n", outf);
+
+ fputs ("\n", outf);
+ }
+
+
+ void
+ tree_debug_bb (bb)
+ basic_block bb;
+ {
+ tree_dump_bb (stderr, "", bb, 0);
+ }
Index: gcc/tree-dfa.c
===================================================================
RCS file: tree-dfa.c
diff -N tree-dfa.c
*** /dev/null Tue May 5 13:32:27 1998
--- tree-dfa.c Fri Mar 9 13:15:44 2001
***************
*** 0 ****
--- 1,580 ----
+ /* Data flow functions for trees.
+ Copyright (C) 2001 Free Software Foundation, Inc.
+ Contributed by Diego Novillo <dnovillo@redhat.com>
+
+ This file is part of GNU CC.
+
+ GNU CC 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.
+
+ GNU CC 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 GNU CC; see the file COPYING. If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+ /* Make sure that structures shared with the RTL optimizer use trees
+ instead of rtx. */
+ #define USE_TREE_IL 1
+
+ #include "config.h"
+ #include "system.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "errors.h"
+ #include "expr.h"
+ #include "c-common.h"
+ #include "ggc.h"
+ #include "tree-opt.h"
+ #include "tree-flow.h"
+
+ #define DEBUG_TREE_DFA /* Force debugging. */
+
+ #ifdef DEBUG_TREE_DFA
+ #undef DEBUG_TREE_DFA
+ #define DEBUG_TREE_DFA(level) debug_tree_dfa (level, __FILE__, __LINE__)
+
+ static int debug_tree_dfa PARAMS ((int, const char *, int));
+
+ static int
+ debug_tree_dfa (level, filename, line)
+ int level;
+ const char *filename;
+ int line;
+ {
+ char *trigger = getenv ("DEBUG_TREE_DFA");
+ if (trigger && atoi (trigger) >= level)
+ {
+ if (atoi (trigger) > level)
+ {
+ fprintf (stderr, "\n----------------------------------------------------------------------------\n\n");
+ fprintf (stderr, "%s:%d\n", filename, line);
+ }
+
+ return 1;
+ }
+
+ return 0;
+
+ }
+ #endif /* DEBUG_TREE_DFA */
+
+
+ /* Local functions. */
+
+ static tree find_refs PARAMS ((tree *, int *, void *));
+ static void find_refs_in_expr PARAMS ((tree, enum varref_type, tree, tree));
+ static varref_node create_node PARAMS ((varref));
+
+
+
+ /* Main entry point. Walks the given tree looking for variable references. */
+
+ void
+ tree_find_varrefs (t)
+ tree t;
+ {
+ walk_stmt_tree (&t, find_refs, NULL);
+
+ #ifdef DEBUG_TREE_DFA
+ if (DEBUG_TREE_DFA (1))
+ {
+ fprintf (stderr, "Symbols referenced:\n");
+ for (t = ref_symbols_list; t; t = TREE_CHAIN (t))
+ {
+ varref_node i;
+ tree sym = TREE_VALUE (t);
+ print_node_brief (stderr, "\t", sym, 0);
+ fprintf (stderr, "\n");
+
+ for (i = VARREF_LIST_FIRST (TREE_REFS (sym)); i; i = VARREF_NODE_NEXT (i))
+ {
+ varref ref = VARREF_NODE_ELEM (i);
+ fprintf (stderr, "\t ");
+ debug_varref (ref);
+ }
+ fprintf (stderr, "\n");
+ }
+ fprintf (stderr, "\n");
+ }
+ #endif
+ }
+
+
+
+ /* Callback for walk_stmt_tree(). */
+
+ static tree
+ find_refs (tp, walk_subtrees, data)
+ tree *tp;
+ int *walk_subtrees ATTRIBUTE_UNUSED;
+ void *data ATTRIBUTE_UNUSED;
+ {
+ tree t = *tp;
+ enum tree_code code;
+
+ if (!t)
+ return NULL_TREE;
+
+ code = TREE_CODE (t);
+
+ if (code == EXPR_STMT)
+ find_refs_in_expr (EXPR_STMT_EXPR (t), VARUSE, t, t);
+
+ else if (code == IF_STMT)
+ find_refs_in_expr (IF_COND (t), VARUSE, t, t);
+
+ else if (code == SWITCH_STMT)
+ find_refs_in_expr (SWITCH_COND (t), VARUSE, t, t);
+
+ else if (code == FOR_STMT)
+ {
+ find_refs_in_expr (FOR_COND (t), VARUSE, t, t);
+ find_refs_in_expr (FOR_EXPR (t), VARUSE, t, t);
+ }
+
+ else if (code == WHILE_STMT)
+ find_refs_in_expr (WHILE_COND (t), VARUSE, t, t);
+
+ else if (code == DO_STMT)
+ find_refs_in_expr (DO_COND (t), VARUSE, t, t);
+
+ else if (code == ASM_STMT)
+ {
+ find_refs_in_expr (ASM_INPUTS (t), VARUSE, t, t);
+ find_refs_in_expr (ASM_OUTPUTS (t), VARDEF, t, t);
+ find_refs_in_expr (ASM_CLOBBERS (t), VARDEF, t, t);
+ }
+
+ else if (code == RETURN_STMT)
+ find_refs_in_expr (RETURN_EXPR (t), VARUSE, t, t);
+
+ return NULL_TREE;
+ }
+
+
+ /* Recursively scan an expression tree looking for variable
+ definitions and uses. */
+
+ static void
+ find_refs_in_expr (expr, ref_type, par_stmt, par_expr)
+ tree expr;
+ enum varref_type ref_type;
+ tree par_stmt;
+ tree par_expr;
+ {
+ enum tree_code code;
+
+ if (!expr)
+ return;
+
+ code = TREE_CODE (expr);
+
+ if (code == VAR_DECL
+ || code == FUNCTION_DECL
+ || code == PARM_DECL
+ || code == FIELD_DECL)
+ {
+ varref ref = create_varref (expr, ref_type, par_stmt, par_expr);
+
+ #ifdef DEBUG_TREE_DFA
+ if (DEBUG_TREE_DFA (1))
+ debug_varref (ref);
+ #endif
+
+ return;
+ }
+
+ switch (code)
+ {
+ /* Unary expressions. */
+ case COMPLEX_CST:
+ case INTEGER_CST:
+ case REAL_CST:
+ case STRING_CST:
+ case LABEL_DECL:
+ case RESULT_DECL:
+ /* These trees make no memory references. */
+ break;
+
+ case ADDR_EXPR:
+ case CONJ_EXPR:
+ case CONVERT_EXPR:
+ case FIX_TRUNC_EXPR:
+ case FLOAT_EXPR:
+ case IMAGPART_EXPR:
+ case INDIRECT_REF:
+ case NEGATE_EXPR:
+ case NON_LVALUE_EXPR:
+ case NOP_EXPR:
+ case REALPART_EXPR:
+ find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, par_stmt, expr);
+ break;
+
+ case BIT_NOT_EXPR:
+ case TRUTH_NOT_EXPR:
+ find_refs_in_expr (TREE_OPERAND (expr, 0), VARDEF, par_stmt, expr);
+ break;
+
+ case POSTDECREMENT_EXPR:
+ case POSTINCREMENT_EXPR:
+ case PREDECREMENT_EXPR:
+ case PREINCREMENT_EXPR:
+ find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, par_stmt, expr);
+ find_refs_in_expr (TREE_OPERAND (expr, 0), VARDEF, par_stmt, expr);
+ break;
+
+
+ /* Binary expressions. */
+ case ARRAY_REF:
+ case BIT_AND_EXPR:
+ case BIT_IOR_EXPR:
+ case BIT_XOR_EXPR:
+ case COMPLEX_EXPR:
+ case COMPONENT_REF:
+ case COMPOUND_EXPR:
+ case COND_EXPR:
+ case EQ_EXPR:
+ case EXACT_DIV_EXPR:
+ case GE_EXPR:
+ case GT_EXPR:
+ case LE_EXPR:
+ case LSHIFT_EXPR:
+ case LT_EXPR:
+ case MINUS_EXPR:
+ case MULT_EXPR:
+ case NE_EXPR:
+ case PLUS_EXPR:
+ case RDIV_EXPR:
+ case RSHIFT_EXPR:
+ case TRUNC_DIV_EXPR:
+ case TRUNC_MOD_EXPR:
+ case TRUTH_AND_EXPR:
+ case TRUTH_ANDIF_EXPR:
+ case TRUTH_OR_EXPR:
+ case TRUTH_ORIF_EXPR:
+ case TRUTH_XOR_EXPR:
+ find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, par_stmt, expr);
+ find_refs_in_expr (TREE_OPERAND (expr, 1), VARUSE, par_stmt, expr);
+ break;
+
+ case INIT_EXPR:
+ case MODIFY_EXPR:
+ find_refs_in_expr (TREE_OPERAND (expr, 0), VARDEF, par_stmt, expr);
+ find_refs_in_expr (TREE_OPERAND (expr, 1), VARUSE, par_stmt, expr);
+ break;
+
+ /* N-ary operations. */
+ case CALL_EXPR:
+ {
+ tree op;
+
+ find_refs_in_expr (TREE_OPERAND (expr, 0), VARUSE, par_stmt, expr);
+ for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
+ find_refs_in_expr (TREE_VALUE (op), VARUSE, par_stmt, expr);
+ break;
+ }
+
+ default:
+ error ("Unhandled expression in find_refs_in_expr(): ");
+ debug_tree (expr);
+ fprintf (stderr, "\n");
+ abort();
+ }
+ }
+
+
+ /* Create a new variable reference and add it to the list of references
+ for the corresponding symbol and basic block. */
+
+ varref
+ create_varref (sym, ref_type, par_stmt, par_expr)
+ tree sym;
+ enum varref_type ref_type;
+ tree par_stmt;
+ tree par_expr;
+ {
+ basic_block bb = TREE_BB (par_stmt);
+ varref ref = (varref) ggc_alloc (sizeof (*ref));
+ memset ((void *)ref, 0, sizeof (*ref));
+
+ VARREF_SYM (ref) = sym;
+ VARREF_TYPE (ref) = ref_type;
+ VARREF_STMT (ref) = par_stmt;
+ VARREF_BLOCK (ref) = bb;
+ VARREF_EXPR (ref) = par_expr;
+
+ /* Add this reference to the list of references for the symbol. */
+ add_ref_to_sym (ref, sym);
+
+ /* Add this reference to the list of references for the basic block. */
+ add_ref_to_bb (ref, bb);
+
+ /* Finally, add the symbol to the global list of referenced symbols. */
+ add_ref_symbol (sym, &ref_symbols_list);
+
+ return ref;
+ }
+
+
+
+ /* Adds reference 'ref' to the list of references made to symbol 'sym'. */
+
+ void
+ add_ref_to_sym (ref, sym)
+ varref ref;
+ tree sym;
+ {
+ if (TREE_ANN (sym) && TREE_REFS (sym))
+ push_ref (TREE_REFS (sym), ref);
+ else
+ {
+ tree_ann ann = get_tree_ann (sym);
+ ann->refs = create_varref_list (ref);
+ }
+ }
+
+
+
+ /* Adds reference 'ref' to the list of references made in basic block
+ 'bb'. */
+
+ void
+ add_ref_to_bb (ref, bb)
+ varref ref;
+ basic_block bb;
+ {
+ if (BB_ANN (bb) && BB_REFS (bb))
+ push_ref (BB_REFS (bb), ref);
+ else
+ {
+ basic_block_ann ann = get_bb_ann (bb);
+ ann->refs = create_varref_list (ref);
+ }
+ }
+
+
+
+ /* Adds a unique copy of symbol 'sym' to the list of symbols. */
+
+ void
+ add_ref_symbol (sym, listp)
+ tree sym;
+ tree *listp;
+ {
+ tree node = build_tree_list (NULL_TREE, sym);
+
+ if (*listp == NULL_TREE)
+ *listp = node;
+ else
+ {
+ tree last;
+ tree list = *listp;
+
+ if (!chain_member_value (sym, list))
+ {
+ /* Add a new symbol to the list. */
+ last = tree_last (list);
+ TREE_CHAIN (last) = node;
+ }
+ }
+ }
+
+
+ /* Get the annotation for the given tree. Create a new one if necessary */
+
+ tree_ann
+ get_tree_ann (t)
+ tree t;
+ {
+ tree_ann ann = TREE_ANN (t);
+
+ if (ann == NULL)
+ {
+ ann = (tree_ann) ggc_alloc (sizeof (*ann));
+ memset ((void *)ann, 0, sizeof (*ann));
+ t->common.aux = (void *)ann;
+ }
+
+ return ann;
+ }
+
+
+ /* Create a new list of variable references. */
+
+ varref_list
+ create_varref_list (ref)
+ varref ref;
+ {
+ varref_list list;
+ varref_node node;
+
+ if (!ref)
+ abort ();
+
+ list = (varref_list) ggc_alloc (sizeof (*list));
+ memset ((void *)list, 0, sizeof (*list));
+
+ node = create_node (ref);
+
+ list->first = node;
+ list->last = node;
+
+ return list;
+ }
+
+
+ /* Push a variable reference to the end of the list. */
+
+ void
+ push_ref (list, ref)
+ varref_list list;
+ varref ref;
+ {
+ varref_node node, last;
+
+ if (ref == NULL || list == NULL)
+ abort ();
+
+ node = create_node (ref);
+
+ last = VARREF_LIST_LAST (list);
+ last->next = node;
+ node->prev = last;
+ list->last = node;
+ }
+
+
+ /* Create a node holder for a varref object. */
+
+ static varref_node
+ create_node (ref)
+ varref ref;
+ {
+ varref_node node;
+
+ if (ref == NULL)
+ abort ();
+
+ node = (varref_node) ggc_alloc (sizeof (*node));
+ memset ((void *)node, 0, sizeof (*node));
+
+ node->elem = ref;
+
+ return node;
+ }
+
+
+
+ /* Debugging functions. */
+
+ void
+ dump_varref (outf, prefix, ref, indent, details)
+ FILE *outf;
+ const char *prefix;
+ varref ref;
+ int indent;
+ int details;
+ {
+ int lineno, bbix;
+ const char *sym, *type;
+ char *s_indent;
+
+ if (ref == NULL)
+ return;
+
+ s_indent = (char *) alloca ((size_t)indent + 1);
+ memset ((void *)s_indent, ' ', (size_t)indent);
+ s_indent[indent] = '\0';
+
+ lineno = (VARREF_STMT (ref))
+ ? STMT_LINENO (VARREF_STMT (ref))
+ : -1;
+
+ sym = (VARREF_SYM (ref))
+ ? IDENTIFIER_POINTER (DECL_NAME (VARREF_SYM (ref)))
+ : "nil";
+
+ bbix = (VARREF_BLOCK (ref))
+ ? VARREF_BLOCK (ref)->index
+ : -1;
+
+ type = (VARREF_TYPE (ref) == VARDEF)
+ ? "DEF"
+ : (VARREF_TYPE (ref) == VARUSE)
+ ? "USE"
+ : (VARREF_TYPE (ref) == VARPHI)
+ ? "PHI"
+ : "???";
+
+ fprintf (outf, "%s%s%s(%s): line %d, bb %d, ", s_indent, prefix, type,
+ sym, lineno, bbix);
+
+ print_node_brief (outf, "", VARREF_EXPR (ref), 0);
+
+ /* Dump specific contents for the different types of references. */
+
+ if (details)
+ {
+ if (VARREF_TYPE (ref) == VARPHI && VARPHI_CHAIN (ref))
+ {
+ fprintf (outf, " phi-args:\n");
+ dump_varref_list (outf, prefix, VARPHI_CHAIN (ref), indent + 4, 0);
+ }
+ else if (VARREF_TYPE (ref) == VARDEF && VARDEF_IMM_USES (ref))
+ {
+ fprintf (outf, " immediate uses:\n");
+ dump_varref_list (outf, prefix, VARDEF_IMM_USES (ref), indent + 4, 0);
+ }
+ else if (VARREF_TYPE (ref) == VARUSE && VARUSE_CHAIN (ref))
+ {
+ fprintf (outf, " reaching def:\n");
+ dump_varref (outf, prefix, VARUSE_CHAIN (ref), indent + 4, 0);
+ }
+ }
+
+ fprintf (outf, "\n");
+ if (!VARREF_EXPR (ref))
+ fputc ('\n', outf);
+ }
+
+
+ void
+ debug_varref (ref)
+ varref ref;
+ {
+ dump_varref (stderr, "", ref, 0, 1);
+ }
+
+
+ void
+ dump_varref_list (outf, prefix, reflist, indent, details)
+ FILE *outf;
+ const char *prefix;
+ varref_list reflist;
+ int indent;
+ int details;
+ {
+ varref_node v;
+
+ for (v = VARREF_LIST_FIRST (reflist); v; v = VARREF_NODE_NEXT (v))
+ dump_varref (outf, prefix, VARREF_NODE_ELEM (v), indent, details);
+ }
+
+
+ void
+ debug_varref_list (reflist)
+ varref_list reflist;
+ {
+ dump_varref_list (stderr, "", reflist, 0, 1);
+ }
Index: gcc/tree-flow.h
===================================================================
RCS file: tree-flow.h
diff -N tree-flow.h
*** /dev/null Tue May 5 13:32:27 1998
--- tree-flow.h Fri Mar 9 13:15:44 2001
***************
*** 0 ****
--- 1,242 ----
+ /* Data and Control Flow Analysis for Trees.
+ Copyright (C) 2001 Free Software Foundation, Inc.
+ Contributed by Diego Novillo <dnovillo@redhat.com>
+
+ This file is part of GNU CC.
+
+ GNU CC 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.
+
+ GNU CC 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 GNU CC; see the file COPYING. If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+ #ifndef _TREE_FLOW_H
+ #define _TREE_FLOW_H 1
+
+ /* Types of references. */
+
+ enum varref_type { VARDEF, VARUSE, VARPHI };
+
+ struct varref_list_def;
+ union varref_def;
+
+ /* Common features of every variable reference. */
+
+ struct varref_common
+ {
+ /* Base symbol. */
+ tree sym;
+
+ /* Statement containing the reference. */
+ tree stmt;
+
+ /* Sub-tree containing the reference. */
+ tree expr;
+
+ /* Basic block containing the reference. */
+ basic_block bb;
+
+ /* Reference type. */
+ enum varref_type type;
+ };
+
+
+
+ /* Variable definitions. */
+
+ struct vardef
+ {
+ struct varref_common common;
+
+ /* Immediate uses for this definition. */
+ struct varref_list_def *imm_uses;
+
+ /* Saved definition chain. */
+ union varref_def *save_chain;
+ };
+
+ #define VARDEF_IMM_USES(r) (r)->def.imm_uses
+ #define VARDEF_SAVE_CHAIN(r) (r)->def.save_chain
+
+
+
+ /* Variable uses. */
+
+ struct varuse
+ {
+ struct varref_common common;
+
+ /* Definition chain. */
+ union varref_def *chain;
+ };
+
+ #define VARUSE_CHAIN(r) (r)->use.chain
+
+
+
+ /* PHI terms. */
+
+ struct varphi
+ {
+ struct varref_common common;
+
+ /* PHI arguments. */
+ struct varref_list_def *phi_chain;
+ };
+
+ #define VARPHI_CHAIN(r) (r)->phi.phi_chain
+
+
+
+ /* Generic variable reference structure. */
+
+ union varref_def
+ {
+ struct varref_common common;
+ struct vardef def;
+ struct varuse use;
+ struct varphi phi;
+ };
+
+ typedef union varref_def *varref;
+
+ #define VARREF_TYPE(r) (r)->common.type
+ #define VARREF_BLOCK(r) (r)->common.bb
+ #define VARREF_EXPR(r) (r)->common.expr
+ #define VARREF_STMT(r) (r)->common.stmt
+ #define VARREF_SYM(r) (r)->common.sym
+ #define VARREF_NEXT(r) (r)->common.next
+ #define VARREF_PREV(r) (r)->common.prev
+
+
+
+ /* Container types for variable references. */
+
+ struct varref_node_def
+ {
+ varref elem;
+ struct varref_node_def *next;
+ struct varref_node_def *prev;
+ };
+
+ typedef struct varref_node_def *varref_node;
+
+ #define VARREF_NODE_ELEM(n) ((n) ? (n)->elem : NULL)
+ #define VARREF_NODE_NEXT(n) ((n) ? (n)->next : NULL)
+ #define VARREF_NODE_PREV(n) ((n) ? (n)->prev : NULL)
+
+
+ struct varref_list_def
+ {
+ varref_node first;
+ varref_node last;
+ };
+
+ typedef struct varref_list_def *varref_list;
+
+
+ #define VARREF_LIST_FIRST(l) ((l) ? (l)->first : NULL)
+ #define VARREF_LIST_LAST(l) ((l) ? (l)->last : NULL)
+
+
+
+ /* Tree annotations stored in tree_common.aux. */
+
+ struct tree_ann_def
+ {
+ /* Basic block that contains this tree. */
+ basic_block bb;
+
+ /* For _DECL trees, list of references made to this variable. */
+ varref_list refs;
+
+ /* Most recent definition for this symbol. Used when placing FUD
+ chains. */
+ varref currdef;
+ };
+
+ typedef struct tree_ann_def *tree_ann;
+
+ #define TREE_ANN(NODE) ((tree_ann)((NODE)->common.aux))
+ #define TREE_BB(NODE) ((TREE_ANN (NODE)) ? TREE_ANN (NODE)->bb : NULL)
+ #define TREE_CURRDEF(NODE) ((TREE_ANN (NODE)) ? TREE_ANN (NODE)->currdef : NULL)
+ #define TREE_REFS(NODE) ((TREE_ANN (NODE)) ? TREE_ANN (NODE)->refs : NULL)
+
+
+
+ /* Block annotations stored in basic_block.aux. */
+
+ struct basic_block_ann_def
+ {
+ /* Control flow parent. */
+ basic_block parent;
+
+ /* List of references made in this block. */
+ varref_list refs;
+ };
+
+ typedef struct basic_block_ann_def *basic_block_ann;
+
+ #define BB_ANN(NODE) ((basic_block_ann)((NODE)->aux))
+ #define BB_PARENT(NODE) ((BB_ANN (NODE)) ? BB_ANN (NODE)->parent : NULL)
+ #define BB_REFS(NODE) ((BB_ANN (NODE)) ? BB_ANN (NODE)->refs : NULL)
+
+
+
+ /* List of all symbols referenced in the function. */
+
+ tree ref_symbols_list;
+
+
+ /* Accessor macros for basic blocks. */
+
+ #define HEAD_TREE(BB) ((tree) BB->head)
+ #define SET_HEAD_TREE(BB, HEAD) (BB)->head = HEAD
+
+ #define END_TREE(BB) ((tree) BB->end)
+ #define SET_END_TREE(BB, END) (BB)->end = END
+
+
+ /* Functions in tree-cfg.c */
+
+ extern void tree_find_basic_blocks PARAMS ((tree, int, FILE *));
+ extern int is_ctrl_stmt_p PARAMS ((tree));
+ extern int is_exec_stmt_p PARAMS ((tree));
+ extern int stmt_ends_bb_p PARAMS ((tree));
+ extern int stmt_starts_bb_p PARAMS ((tree));
+ extern void set_bb_parent PARAMS ((basic_block, basic_block));
+ extern basic_block_ann get_bb_ann PARAMS ((basic_block));
+ void tree_dump_bb (FILE *, const char *, basic_block, int);
+ void tree_debug_bb (basic_block);
+
+
+ /* Functions in tree-dfa.c */
+
+ void tree_find_varrefs PARAMS ((tree));
+ void add_ref_to_sym PARAMS ((varref, tree sym));
+ void add_ref_to_bb PARAMS ((varref, basic_block));
+ void add_ref_symbol PARAMS ((tree, tree *));
+ tree_ann get_tree_ann PARAMS ((tree));
+ varref create_varref PARAMS ((tree, enum varref_type, tree, tree));
+ varref_list create_varref_list PARAMS ((varref));
+ void push_ref PARAMS ((varref_list, varref));
+ void debug_varref PARAMS ((varref));
+ void dump_varref PARAMS ((FILE *, const char *, varref, int, int));
+ void debug_varref_list PARAMS ((varref_list));
+ void dump_varref_list PARAMS ((FILE *, const char *, varref_list, int, int));
+
+
+ /* Functions in tree-ssa.c */
+
+ void tree_build_ssa PARAMS ((void));
+
+ #endif /* _TREE_FLOW_H */
Index: gcc/tree-opt.c
===================================================================
RCS file: tree-opt.c
diff -N tree-opt.c
*** /dev/null Tue May 5 13:32:27 1998
--- tree-opt.c Fri Mar 9 13:15:44 2001
***************
*** 0 ****
--- 1,54 ----
+ /* Control and data flow functions for trees.
+ Copyright (C) 2001 Free Software Foundation, Inc.
+ Contributed by Diego Novillo <dnovillo@redhat.com>
+
+ This file is part of GNU CC.
+
+ GNU CC 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.
+
+ GNU CC 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 GNU CC; see the file COPYING. If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+ /* Make sure that structures shared with the RTL optimizer use trees
+ instead of rtx. */
+ #define USE_TREE_IL 1
+
+ #include "config.h"
+ #include "system.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "expr.h"
+ #include "c-common.h"
+ #include "tree-opt.h"
+ #include "tree-flow.h"
+
+ void
+ optimize_tree (t)
+ tree t;
+ {
+ tree_find_basic_blocks (t, 0, 0);
+ tree_find_varrefs (t);
+ tree_build_ssa ();
+ }
+
+
+ /* Initialize the tree IL analysis and optimization routines. */
+
+ void
+ init_tree_opt ()
+ {
+ }
Index: gcc/tree-opt.h
===================================================================
RCS file: tree-opt.h
diff -N tree-opt.h
*** /dev/null Tue May 5 13:32:27 1998
--- tree-opt.h Fri Mar 9 13:15:44 2001
***************
*** 0 ****
--- 1,28 ----
+ /* Tree transformation functions.
+ Copyright (C) 2001 Free Software Foundation, Inc.
+ Contributed by Diego Novillo <dnovillo@redhat.com>
+
+ This file is part of GNU CC.
+
+ GNU CC 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.
+
+ GNU CC 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 GNU CC; see the file COPYING. If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+ #ifndef _TREE_OPT_H
+ #define _TREE_OPT_H 1
+
+ void optimize_tree PARAMS ((tree));
+ void init_tree_opt PARAMS ((void));
+
+ #endif /* _TREE_OPT_H */
Index: gcc/tree-ssa.c
===================================================================
RCS file: tree-ssa.c
diff -N tree-ssa.c
*** /dev/null Tue May 5 13:32:27 1998
--- tree-ssa.c Fri Mar 9 13:15:44 2001
***************
*** 0 ****
--- 1,363 ----
+ /* SSA for trees.
+ Copyright (C) 2001 Free Software Foundation, Inc.
+ Contributed by Diego Novillo <dnovillo@redhat.com>
+
+ This file is part of GNU CC.
+
+ GNU CC 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.
+
+ GNU CC 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 GNU CC; see the file COPYING. If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+ /* Make sure that structures shared with the RTL optimizer use trees
+ instead of rtx. */
+ #define USE_TREE_IL 1
+
+ #include "config.h"
+ #include "system.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "errors.h"
+ #include "expr.h"
+ #include "c-common.h"
+ #include "tree-opt.h"
+ #include "tree-flow.h"
+ #include "ssa.h"
+
+ #define DEBUG_TREE_SSA /* Force debugging. */
+
+ #ifdef DEBUG_TREE_SSA
+ #undef DEBUG_TREE_SSA
+ #define DEBUG_TREE_SSA(level) debug_tree_ssa (level, __FILE__, __LINE__)
+
+ static int debug_tree_ssa PARAMS ((int, const char *, int));
+
+ static int
+ debug_tree_ssa (level, filename, line)
+ int level;
+ const char *filename;
+ int line;
+ {
+ char *trigger = getenv ("DEBUG_TREE_SSA");
+ if (trigger && atoi (trigger) >= level)
+ {
+ if (atoi (trigger) > level)
+ {
+ fprintf (stderr, "\n----------------------------------------------------------------------------\n\n");
+ fprintf (stderr, "%s:%d\n", filename, line);
+ }
+
+ return 1;
+ }
+
+ return 0;
+
+ }
+ #endif /* DEBUG_TREE_SSA */
+
+ static void insert_phi_terms PARAMS ((sbitmap *));
+ static void build_fud_chains PARAMS ((int *));
+ static void search_fud_chains PARAMS ((basic_block, int *));
+
+
+ /* Build the SSA form for the given function. This implements Factored
+ Use-Def Chains as described in
+
+ Wolfe, M. J., High Performance Compilers for Parallel Computing,
+ Addison-Wesley, 1996. */
+
+ void
+ tree_build_ssa ()
+ {
+ sbitmap *dfs;
+ int *idom;
+
+ idom = (int *) xmalloc ((size_t)n_basic_blocks * sizeof (int));
+ memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
+ calculate_dominance_info (idom, NULL, CDI_DOMINATORS);
+
+ /* Compute dominance frontiers. */
+ dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ compute_dominance_frontiers (dfs, idom);
+
+ /* Insert the phi nodes and build FUD chains. */
+ insert_phi_terms (dfs);
+ build_fud_chains (idom);
+
+ sbitmap_vector_free (dfs);
+ free (idom);
+
+ #ifdef DEBUG_TREE_SSA
+ if (DEBUG_TREE_SSA (1))
+ {
+ int i;
+
+ fprintf (stderr, "SSA information\n\n");
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ tree_dump_bb (stderr, "\t", bb, 0);
+ dump_varref_list (stderr, "\t", BB_REFS (bb), 0, 1);
+ }
+ }
+ #endif
+ }
+
+
+ /* Insert PHI terms. */
+
+ static void
+ insert_phi_terms (dfs)
+ sbitmap *dfs;
+ {
+ tree m;
+ tree *added;
+ tree *in_work;
+ basic_block *work_list;
+ int work_list_top;
+
+ added = (tree *) xmalloc (n_basic_blocks * sizeof (tree));
+ memset ((void *)added, 0, (size_t)n_basic_blocks * sizeof (tree));
+
+ in_work = (tree *) xmalloc (n_basic_blocks * sizeof (tree));
+ memset ((void *)in_work, 0, (size_t)n_basic_blocks * sizeof (tree));
+
+ work_list = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
+ work_list_top = 0;
+
+ /* Iterate over all referenced symbols in the function. For each
+ symbol, add to the work list all the nodes that have a definition
+ for the symbol. PHI terms will be added to the dominance frontier
+ nodes of each definition node. */
+
+ for (m = ref_symbols_list; m; m = TREE_CHAIN (m))
+ {
+ varref_node i;
+ tree sym = TREE_VALUE (m);
+
+ /* Symbols in ref_symbols_list must have at least 1 reference. */
+ if (TREE_ANN (sym) == NULL)
+ abort ();
+
+ for (i = VARREF_LIST_FIRST (TREE_REFS (sym)); i; i = VARREF_NODE_NEXT (i))
+ {
+ basic_block node;
+ varref ref = VARREF_NODE_ELEM (i);
+
+ if (VARREF_TYPE (ref) != VARDEF)
+ continue;
+
+ node = VARREF_BLOCK (ref);
+ work_list[work_list_top++] = node;
+ in_work[node->index] = sym;
+ }
+
+ while (work_list_top > 0)
+ {
+ int w;
+ basic_block node = work_list[--work_list_top];
+
+ EXECUTE_IF_SET_IN_SBITMAP (dfs[node->index], 0, w,
+ {
+ if (added[w] != sym)
+ {
+ basic_block bb = BASIC_BLOCK (w);
+ varref phi;
+
+ phi = create_varref (sym, VARPHI, HEAD_TREE (bb), NULL);
+ added[w] = sym;
+
+ if (DEBUG_TREE_SSA (2))
+ debug_varref (phi);
+
+ if (in_work[w] != sym)
+ {
+ work_list[work_list_top++] = bb;
+ in_work[w] = sym;
+ }
+ }
+ });
+ }
+ }
+
+ free (added);
+ free (in_work);
+ free (work_list);
+ }
+
+
+ /* Build FUD (Factored Use-Def) chains. */
+
+ static void
+ build_fud_chains (idom)
+ int *idom;
+ {
+ tree m;
+
+ /* Initialize the current definition for all the symbols. */
+
+ for (m = ref_symbols_list; m; m = TREE_CHAIN (m))
+ {
+ tree sym = TREE_VALUE (m);
+ tree_ann ann = TREE_ANN (sym);
+
+ /* Symbols in ref_symbols_list must have at least 1 reference. */
+ if (TREE_ANN (sym) == NULL)
+ abort ();
+
+ ann->currdef = NULL;
+ }
+
+ /* Search FUD chains starting with the entry block. */
+ search_fud_chains (ENTRY_BLOCK_PTR, idom);
+ }
+
+
+
+ /* Perform a depth-first traversal of the dominator tree looking for FUD
+ chains. */
+
+ static void
+ search_fud_chains (bb, idom)
+ basic_block bb;
+ int *idom;
+ {
+ varref_node n;
+ edge e;
+ int i;
+
+ /* for each variable use or def or phi-term R in X do
+ let M be the variable referenced at R
+ if R is a use then
+ Chain(R) = CurrDef(M)
+ else if R is a def or $\phi$-term then
+ SaveChain(R) = CurrDef(M)
+ CurrDef(M) = R
+ endif
+ endfor */
+
+ for (n = VARREF_LIST_FIRST (BB_REFS (bb)); n; n = VARREF_NODE_NEXT (n))
+ {
+ varref currdef;
+ varref ref = VARREF_NODE_ELEM (n);
+ tree m = VARREF_SYM (ref);
+
+ /* Retrieve the current definition for the variable */
+ currdef = TREE_CURRDEF (m);
+
+ if (VARREF_TYPE (ref) == VARUSE)
+ {
+ VARUSE_CHAIN (ref) = currdef;
+
+ /* Besides setting a link back to our immediate control
+ reaching definition (whether a PHI term or an actual
+ definition), we want to link that definition to its
+ immediate use.
+
+ If this use (ref) has a current definition (currdef), we
+ add 'ref' to the list of uses immediately reached by
+ 'currdef'. */
+
+ if (currdef)
+ {
+ if (VARDEF_IMM_USES (currdef))
+ push_ref (VARDEF_IMM_USES (currdef), ref);
+ else
+ VARDEF_IMM_USES (currdef) = create_varref_list (ref);
+ }
+ }
+ else if (VARREF_TYPE (ref) == VARDEF || VARREF_TYPE (ref) == VARPHI)
+ {
+ tree_ann ann;
+
+ VARDEF_SAVE_CHAIN (ref) = currdef;
+
+ /* Replace the current currdef with a new one */
+ ann = TREE_ANN (m);
+ ann->currdef = ref;
+ }
+ }
+
+
+
+ /* for Y in SUCC(X) do
+ J = WhichPred(X -> Y)
+ for each phi-term R in Y do
+ let M be the variable referenced at R
+ phi-chain(R)[J] = CurrDef(M)
+ endfor
+ endfor */
+
+ for (e = bb->succ, i = 0; e; e = e->succ_next, i++)
+ {
+ basic_block y = e->dest;
+
+ for (n = VARREF_LIST_FIRST (BB_REFS (y)); n; n = VARREF_NODE_NEXT (n))
+ {
+ tree sym;
+ varref currdef;
+ varref phi = VARREF_NODE_ELEM (n);
+
+ if (VARREF_TYPE (phi) != VARPHI)
+ continue;
+
+ sym = VARREF_SYM (phi);
+ currdef = TREE_CURRDEF (sym);
+
+ if (VARPHI_CHAIN (phi))
+ push_ref (VARPHI_CHAIN (phi), currdef);
+ else
+ VARPHI_CHAIN (phi) = create_varref_list (currdef);
+ }
+ }
+
+
+
+ /* for Y in Child(X) do <-- Child(X) is the set of dominator
+ Search(Y) children of X in the dominator tree.
+ endfor */
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ if (idom[i] == bb->index)
+ search_fud_chains (BASIC_BLOCK (i), idom);
+ }
+
+
+ /* for each variable use or def or phi-term R in X in reverse order do
+ let M be the variable referenced at R
+ if R is a def or a phi-term then
+ CurrDef(M) = SaveChain(R)
+ endif
+ endfor */
+
+ for (n = VARREF_LIST_LAST (BB_REFS (bb)); n; n = VARREF_NODE_PREV (n))
+ {
+ varref ref = VARREF_NODE_ELEM (n);
+
+ if (VARREF_TYPE (ref) == VARDEF || VARREF_TYPE (ref) == VARPHI)
+ {
+ tree sym = VARREF_SYM (ref);
+ tree_ann ann;
+
+ /* Restore the current definition for the variable */
+ ann = TREE_ANN (sym);
+ ann->currdef = VARDEF_SAVE_CHAIN (ref);
+ }
+ }
+ }
Index: gcc/tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.229
diff -d -c -p -r1.229 tree.h
*** tree.h 2001/03/02 21:41:36 1.229
--- tree.h 2001/03/09 21:15:46
*************** struct tree_common
*** 130,135 ****
--- 130,136 ----
{
union tree_node *chain;
union tree_node *type;
+ void *aux;
ENUM_BITFIELD(tree_code) code : 8;
unsigned side_effects_flag : 1;
unsigned constant_flag : 1;
Index: gcc/cp/Make-lang.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/Make-lang.in,v
retrieving revision 1.78
diff -d -c -p -r1.78 Make-lang.in
*** Make-lang.in 2001/02/16 03:54:00 1.78
--- Make-lang.in 2001/03/09 21:15:49
*************** $(DEMANGLER_PROG): cxxmain.o underscore.
*** 93,99 ****
# The compiler itself.
# Shared with C front end:
! CXX_C_OBJS = c-common.o c-format.o c-pragma.o c-semantics.o c-lex.o c-dump.o $(CXX_TARGET_OBJS)
# Language-specific object files.
CXX_OBJS = cp/call.o cp/decl.o cp/errfn.o cp/expr.o cp/pt.o cp/typeck2.o \
--- 93,100 ----
# The compiler itself.
# Shared with C front end:
! CXX_C_OBJS = c-common.o c-format.o c-pragma.o c-semantics.o c-lex.o c-dump.o $(CXX_TARGET_OBJS) \
! tree-cfg.o tree-dfa.o tree-opt.o tree-ssa.o
# Language-specific object files.
CXX_OBJS = cp/call.o cp/decl.o cp/errfn.o cp/expr.o cp/pt.o cp/typeck2.o \
More information about the Gcc-patches
mailing list