This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[ast-optimizer-branch]: Tree SSAPRE
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 27 Apr 2002 15:31:34 -0400 (EDT)
- Subject: [ast-optimizer-branch]: Tree SSAPRE
This patch adds SSAPRE for Tree-SSA. I'll work more on it after finals
(May 10th is when they end).
The only real issues are that it doesn't
1. Insert reload statements that conform to SIMPLE (easy to fix, will do
after finals). Rather than transform
e = a + b
into
T.1 = a + b
e = T.1
It does
e = T.1 = a + b
2. Keep the SSA form valid (easy to fix, will do after finals).
I'll also add strength reduction after finals, as it's very easy to do as
well.
I'll comment it better (though the routines correspond directly with the
algorithms in http://citeseer.nj.nec.com/correct/399268) after finals as
well.
I'll also probably split exprref's out of varrefs after finals as well.
When C++/Java support for tree-ssa is added/finished, we'll want to add
code to prevent hoisting into exception regions.
2002-04-23 Daniel Berlin <dberlin@dberlin.org>
* tree*.[ch]: s/create_varref/create_ref/g.
s/varref_common/treeref_common/g
* tree.h (tree_dump_index): Add TDI_ssa_pre.
* tree-ssa.c (delete_refs): Handle deleting EXPRPHI refs.
* tree-optimize.c (build_tree_ssa): Perform SSA-PRE if requested.
* tree-flow.h: Add EXPRPHI/EXPRDEF/EXPRKILL.
Add exprref_phi, exprref_use, exprref_common.
Add prototype for tree_perform_ssapre.
* tree-dump.c (dump_files): Add ssapre dump.
* tree-dfa.c (create_varref): Handle EXPRPHI.
(dump_varref): Don't try to dump sym for EXPRPHI/EXPRDEF.
It's an expression.
Handle EXPRPHI/EXPRDEF printing.
(dump_varref_list): Only print varref if it's not NULL
(EXPRPHI_PHI_CHAIN has null pointers for non-existent operands).
* Makefile.in (C_AND_OBJC_OBJS): Add tree-ssa-pre.o
(tree-ssa-pre.o): Add dependencies.
* flags.h: Add flag_tree_ssa_pre.
* toplev.c: Add flag_tree_ssa_pre/-ftree-ssa-pre.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.701.2.20
diff -c -3 -p -w -B -b -r1.701.2.20 Makefile.in
*** Makefile.in 19 Apr 2002 19:15:56 -0000 1.701.2.20
--- Makefile.in 27 Apr 2002 16:07:42 -0000
*************** CXX_TARGET_OBJS=@cxx_target_objs@
*** 705,711 ****
C_AND_OBJC_OBJS = attribs.o 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-objc-common.o libcpp.a $(C_TARGET_OBJS) \
! tree-cfg.o tree-dfa.o tree-ssa.o tree-optimize.o c-pretty-print.o \
c-simplify.o c-call-graph.o tree-simple.o
# Language-specific object files for C.
--- 705,711 ----
C_AND_OBJC_OBJS = attribs.o 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-objc-common.o libcpp.a $(C_TARGET_OBJS) \
! tree-cfg.o tree-dfa.o tree-ssa.o tree-ssa-pre.o tree-optimize.o c-pretty-print.o \
c-simplify.o c-call-graph.o tree-simple.o
# Language-specific object files for C.
*************** tree-inline.o : tree-inline.c $(CONFIG_H
*** 1340,1345 ****
--- 1340,1348 ----
print-tree.o : print-tree.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(GGC_H) \
langhooks.h
tree-ssa.o : tree-ssa.c tree-optimize.h tree-flow.h $(CONFIG_H) $(SYSTEM_H) \
+ $(RTL_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) $(EXPR_H) $(C_COMMON_H) \
+ $(GGC_H) output.h diagnostic.h ssa.h errors.h toplev.h
+ tree-ssa-pre.o : tree-ssa-pre.c tree-optimize.h tree-flow.h $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(BASIC_BLOCK_H) $(EXPR_H) $(C_COMMON_H) \
$(GGC_H) output.h diagnostic.h ssa.h errors.h toplev.h
tree-cfg.o : tree-cfg.c tree-optimize.h tree-flow.h $(CONFIG_H) $(SYSTEM_H) \
Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.18.2.4
diff -c -3 -p -w -B -b -r1.18.2.4 cfg.c
*** cfg.c 2 Apr 2002 15:24:40 -0000 1.18.2.4
--- cfg.c 27 Apr 2002 16:07:42 -0000
*************** dump_edge_info (file, e, do_succ)
*** 622,627 ****
--- 622,632 ----
fputc (')', file);
}
+ if (EDGE_CRITICAL_P (e))
+ {
+ fputs (" (critical) ", file);
+ }
+
}
/* Simple routines to easily allocate AUX fields of basic blocks. */
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.65.4.6
diff -c -3 -p -w -B -b -r1.65.4.6 flags.h
*** flags.h 2 Apr 2002 15:25:32 -0000 1.65.4.6
--- flags.h 27 Apr 2002 16:07:42 -0000
*************** extern int flag_non_call_exceptions;
*** 648,653 ****
--- 648,656 ----
/* Enable the SSA tree optimizer. */
extern int flag_tree_ssa;
+ /* Enable the SSA-PRE on trees. */
+ extern int flag_tree_ssa_pre;
+
/* Nonzero means put zero initialized data in the bss section. */
extern int flag_zero_initialized_in_bss;
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.494.2.7
diff -c -3 -p -w -B -b -r1.494.2.7 toplev.c
*** toplev.c 2 Apr 2002 15:26:37 -0000 1.494.2.7
--- toplev.c 27 Apr 2002 16:07:43 -0000
*************** int flag_renumber_insns = 1;
*** 845,850 ****
--- 845,853 ----
/* Enable the SSA tree optimizer. */
int flag_tree_ssa = 0;
+ /* Enable the SSA-PRE tree optimization. */
+ int flag_tree_ssa_pre = 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
*************** static const lang_independent_options f_
*** 1139,1144 ****
--- 1142,1149 ----
N_("Trap for signed overflow in addition / subtraction / multiplication") },
{ "tree-ssa", &flag_tree_ssa, 1,
N_("Enable SSA optimizations on trees") },
+ { "tree-ssa-pre", &flag_tree_ssa_pre, 1,
+ N_("Enable SSA-PRE optimization on trees") },
};
/* Table of language-specific options. */
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.2.16
diff -c -3 -p -w -B -b -r1.1.2.16 tree-dfa.c
*** tree-dfa.c 22 Apr 2002 21:41:59 -0000 1.1.2.16
--- tree-dfa.c 27 Apr 2002 16:07:43 -0000
*************** static int dump_flags;
*** 45,51 ****
/* Local functions. */
static void find_refs_in_stmt PARAMS ((tree, basic_block));
! static void find_refs_in_expr PARAMS ((tree, enum varref_type, basic_block,
tree, tree));
static void create_tree_ann PARAMS ((tree));
static void add_ref_symbol PARAMS ((tree));
--- 45,51 ----
/* Local functions. */
static void find_refs_in_stmt PARAMS ((tree, basic_block));
! static void find_refs_in_expr PARAMS ((tree, enum treeref_type, basic_block,
tree, tree));
static void create_tree_ann PARAMS ((tree));
static void add_ref_symbol PARAMS ((tree));
*************** find_refs_in_stmt (t, bb)
*** 229,235 ****
static void
find_refs_in_expr (expr, ref_type, bb, parent_stmt, parent_expr)
tree expr;
! enum varref_type ref_type;
basic_block bb;
tree parent_stmt;
tree parent_expr;
--- 229,235 ----
static void
find_refs_in_expr (expr, ref_type, bb, parent_stmt, parent_expr)
tree expr;
! enum treeref_type ref_type;
basic_block bb;
tree parent_stmt;
tree parent_expr;
*************** find_refs_in_expr (expr, ref_type, bb, p
*** 246,252 ****
|| code == PARM_DECL
|| code == FIELD_DECL)
{
! create_varref (expr, ref_type, bb, parent_stmt, parent_expr);
return;
}
--- 246,252 ----
|| code == PARM_DECL
|| code == FIELD_DECL)
{
! create_ref (expr, ref_type, bb, parent_stmt, parent_expr);
return;
}
*************** find_refs_in_expr (expr, ref_type, bb, p
*** 450,456 ****
/* Create references and associations to symbols and basic blocks. */
! /* {{{ create_varref()
Create a new variable reference for symbol SYM and add it to the list
of references for SYM and the basic block that holds the reference.
--- 450,456 ----
/* Create references and associations to symbols and basic blocks. */
! /* {{{ create_ref()
Create a new variable reference for symbol SYM and add it to the list
of references for SYM and the basic block that holds the reference.
*************** find_refs_in_expr (expr, ref_type, bb, p
*** 459,467 ****
reference. */
varref
! create_varref (sym, ref_type, bb, parent_stmt, parent_expr)
tree sym;
! enum varref_type ref_type;
basic_block bb;
tree parent_stmt;
tree parent_expr;
--- 459,467 ----
reference. */
varref
! create_ref (sym, ref_type, bb, parent_stmt, parent_expr)
tree sym;
! enum treeref_type ref_type;
basic_block bb;
tree parent_stmt;
tree parent_expr;
*************** create_varref (sym, ref_type, bb, parent
*** 486,496 ****
VARRAY_GENERIC_PTR_INIT (VARDEF_IMM_USES (ref), 3, "imm_uses");
VARRAY_GENERIC_PTR_INIT (VARDEF_RUSES (ref), 5, "ruses");
if (ref_type == VARPHI)
VARRAY_GENERIC_PTR_INIT (VARDEF_PHI_CHAIN (ref), 3, "phi_chain");
}
else if (ref_type == VARUSE)
VARRAY_GENERIC_PTR_INIT (VARUSE_RDEFS (ref), 3, "rdefs");
!
/* Add the symbol to the list of symbols referenced in this function. */
add_ref_symbol (sym);
--- 486,510 ----
VARRAY_GENERIC_PTR_INIT (VARDEF_IMM_USES (ref), 3, "imm_uses");
VARRAY_GENERIC_PTR_INIT (VARDEF_RUSES (ref), 5, "ruses");
if (ref_type == VARPHI)
+ {
VARRAY_GENERIC_PTR_INIT (VARDEF_PHI_CHAIN (ref), 3, "phi_chain");
+ VARRAY_BB_INIT (VARDEF_PHI_CHAIN_BB (ref), 3, "phi_chain_bb");
+ }
}
else if (ref_type == VARUSE)
VARRAY_GENERIC_PTR_INIT (VARUSE_RDEFS (ref), 3, "rdefs");
! else if (ref_type == EXPRPHI)
! {
! VARRAY_GENERIC_PTR_INIT (EXPRPHI_PHI_CHAIN (ref),
! n_basic_blocks, "ephi_chain");
! EXPRPHI_PROCESSED (ref) = BITMAP_XMALLOC ();
! EXPRPHI_DOWNSAFE (ref) = 1;
! EXPRPHI_CANBEAVAIL (ref) = 1;
! EXPRPHI_LATER (ref) = 1;
! EXPRPHI_EXTRANEOUS (ref) = 1;
! }
! if (sym)
! {
/* Add the symbol to the list of symbols referenced in this function. */
add_ref_symbol (sym);
*************** create_varref (sym, ref_type, bb, parent
*** 501,514 ****
statement. */
if (parent_stmt)
VARRAY_PUSH_GENERIC_PTR (get_tree_ann (parent_stmt)->refs, ref);
!
/* Add this reference to the list of references for the basic block. */
VARRAY_PUSH_GENERIC_PTR (get_bb_ann (bb)->refs, ref);
/* Make sure that PHI terms are added at the beginning of the list,
otherwise FUD chaining will fail to link local uses to the PHI
term in this basic block. */
! if (ref_type == VARPHI)
{
varray_type refs = BB_REFS (bb);
char *src = refs->data.c;
--- 515,528 ----
statement. */
if (parent_stmt)
VARRAY_PUSH_GENERIC_PTR (get_tree_ann (parent_stmt)->refs, ref);
! }
/* Add this reference to the list of references for the basic block. */
VARRAY_PUSH_GENERIC_PTR (get_bb_ann (bb)->refs, ref);
/* Make sure that PHI terms are added at the beginning of the list,
otherwise FUD chaining will fail to link local uses to the PHI
term in this basic block. */
! if (ref_type == VARPHI || ref_type == EXPRPHI)
{
varray_type refs = BB_REFS (bb);
char *src = refs->data.c;
*************** dump_varref (outf, prefix, ref, indent,
*** 737,743 ****
lineno = (VARREF_STMT (ref)) ? STMT_LINENO (VARREF_STMT (ref)) : -1;
! sym = (VARREF_SYM (ref))
? IDENTIFIER_POINTER (DECL_NAME (VARREF_SYM (ref))) : "nil";
bbix = (VARREF_BB (ref)) ? VARREF_BB (ref)->index : -1;
--- 751,760 ----
lineno = (VARREF_STMT (ref)) ? STMT_LINENO (VARREF_STMT (ref)) : -1;
! sym = (VARREF_SYM (ref)
! && VARREF_TYPE (ref) != EXPRPHI
! && VARREF_TYPE (ref) != EXPRUSE
! && VARREF_TYPE (ref) != EXPRKILL)
? IDENTIFIER_POINTER (DECL_NAME (VARREF_SYM (ref))) : "nil";
bbix = (VARREF_BB (ref)) ? VARREF_BB (ref)->index : -1;
*************** dump_varref (outf, prefix, ref, indent,
*** 745,750 ****
--- 762,770 ----
type = (VARREF_TYPE (ref) == VARDEF) ? "DEF" :
(VARREF_TYPE (ref) == VARUSE) ? "USE" :
(VARREF_TYPE (ref) == VARPHI) ? "PHI" :
+ (VARREF_TYPE (ref) == EXPRPHI) ? "EXPRPHI" :
+ (VARREF_TYPE (ref) == EXPRUSE) ? "EXPRUSE" :
+ (VARREF_TYPE (ref) == EXPRKILL) ? "EXPRKILL" :
"???";
fprintf (outf, "%s%s%s(%s): line %d, bb %d, ", s_indent, prefix, type,
*************** dump_varref (outf, prefix, ref, indent,
*** 763,768 ****
--- 783,793 ----
fputs (" phi-args:\n", outf);
dump_varref_list (outf, prefix, VARDEF_PHI_CHAIN (ref), indent + 4, 0);
}
+ else if (VARREF_TYPE (ref) == EXPRPHI && EXPRPHI_PHI_CHAIN (ref))
+ {
+ fputs (" exprphi-args:\n", outf);
+ dump_varref_list (outf, prefix, EXPRPHI_PHI_CHAIN (ref), indent + 4, 0);
+ }
else if (VARREF_TYPE (ref) == VARDEF && VARDEF_IMM_USES (ref))
{
fputs (" immediate uses:\n", outf);
*************** dump_varref_list (outf, prefix, reflist,
*** 814,820 ****
if (reflist == NULL)
return;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (reflist); i++)
dump_varref (outf, prefix, VARRAY_GENERIC_PTR (reflist, i),
indent, details);
}
--- 839,846 ----
if (reflist == NULL)
return;
! for (i = 0; i < VARRAY_SIZE (reflist); i++)
! if (VARRAY_GENERIC_PTR (reflist, i))
dump_varref (outf, prefix, VARRAY_GENERIC_PTR (reflist, i),
indent, details);
}
Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
retrieving revision 1.2.4.6
diff -c -3 -p -w -B -b -r1.2.4.6 tree-dump.c
*** tree-dump.c 2 Apr 2002 15:26:40 -0000 1.2.4.6
--- tree-dump.c 27 Apr 2002 16:07:43 -0000
*************** static struct dump_file_info dump_files[
*** 809,814 ****
--- 809,815 ----
{".inlined", "dump-tree-inlined", 0, 0},
{".cfg", "dump-tree-cfg", 0, 0},
{".dot", "dump-tree-graphviz", 0, 0},
+ {".ssapre", "dump-tree-ssapre", 0, 0},
{".ssa", "dump-tree-ssa", 0, 0},
{".simple", "dump-tree-simple", 0, 0},
{".xml", "dump-call-graph", 0, 0},
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.2.11
diff -c -3 -p -w -B -b -r1.1.2.11 tree-flow.h
*** tree-flow.h 22 Apr 2002 21:41:59 -0000 1.1.2.11
--- tree-flow.h 27 Apr 2002 16:07:44 -0000
*************** Boston, MA 02111-1307, USA. */
*** 22,30 ****
#ifndef _TREE_FLOW_H
#define _TREE_FLOW_H 1
/* {{{ Types of references. */
! enum varref_type { VARDEF, VARUSE, VARPHI };
union varref_def;
--- 22,31 ----
#ifndef _TREE_FLOW_H
#define _TREE_FLOW_H 1
+ #include "bitmap.h"
/* {{{ Types of references. */
! enum treeref_type { VARDEF, VARUSE, VARPHI, EXPRPHI, EXPRUSE, EXPRKILL };
union varref_def;
*************** union varref_def;
*** 32,38 ****
/* {{{ Common features of every variable reference. */
! struct varref_common
{
/* Base symbol. */
tree sym;
--- 33,39 ----
/* {{{ Common features of every variable reference. */
! struct treeref_common
{
/* Base symbol. */
tree sym;
*************** struct varref_common
*** 47,62 ****
basic_block bb;
/* Reference type. */
! enum varref_type type;
};
/* }}} */
/* {{{ Variable definitions. */
struct vardef
{
! struct varref_common common;
/* Immediate uses for this definition. */
varray_type imm_uses;
--- 48,92 ----
basic_block bb;
/* Reference type. */
! enum treeref_type type;
!
};
/* }}} */
+ struct exprref_common
+ {
+ struct treeref_common common;
+ int save:1;
+ int reload:1;
+ int inserted:1;
+ int class;
+ };
+
+ struct exprphi
+ {
+ struct exprref_common common;
+ varray_type phi_chain;
+ unsigned int downsafe:1;
+ unsigned int can_be_avail:1;
+ unsigned int later:1;
+ unsigned int extraneous:1;
+ bitmap save_operand;
+ bitmap processed;
+ };
+ #define EXPRPHI_PHI_CHAIN(r) (r)->ephi.phi_chain
+ #define EXPRPHI_DOWNSAFE(r) (r)->ephi.downsafe
+ #define EXPRPHI_CANBEAVAIL(r) (r)->ephi.can_be_avail
+ #define EXPRPHI_LATER(r) (r)->ephi.later
+ #define EXPRPHI_EXTRANEOUS(r) (r)->ephi.extraneous
+ #define EXPRPHI_PROCESSED(r) (r)->ephi.processed
+ #define EXPRPHI_WILLBEAVAIL(r) (EXPRPHI_CANBEAVAIL ((r)) && !EXPRPHI_LATER ((r)))
+
/* {{{ Variable definitions. */
struct vardef
{
! struct treeref_common common;
/* Immediate uses for this definition. */
varray_type imm_uses;
*************** struct vardef
*** 72,79 ****
--- 102,115 ----
/* PHI arguments (not used with real definitions). */
varray_type phi_chain;
+
+ /* PHI argument BB's
+ This is which bb this argument reaches us from, *not* which bb
+ the argument is *in*. */
+ varray_type phi_chain_bb;
};
+
#define VARDEF_IMM_USES(r) (r)->def.imm_uses
#define VARDEF_SAVE_CHAIN(r) (r)->def.save_chain
#define VARDEF_RUSES(r) (r)->def.ruses
*************** struct vardef
*** 79,84 ****
--- 115,121 ----
#define VARDEF_RUSES(r) (r)->def.ruses
#define VARDEF_MARKED(r) (r)->def.marked
#define VARDEF_PHI_CHAIN(r) (r)->def.phi_chain
+ #define VARDEF_PHI_CHAIN_BB(r) (r)->def.phi_chain_bb
/* }}} */
*************** struct vardef
*** 86,92 ****
struct varuse
{
! struct varref_common common;
/* Definition chain. */
union varref_def *chain;
--- 123,129 ----
struct varuse
{
! struct exprref_common common;
/* Definition chain. */
union varref_def *chain;
*************** struct varuse
*** 100,112 ****
/* }}} */
/* {{{ Generic variable reference structure. */
union varref_def
{
! struct varref_common common;
struct vardef def;
struct varuse use;
};
typedef union varref_def *varref;
--- 137,172 ----
/* }}} */
+ /* {{{ Expressions uses. */
+
+ struct expruse
+ {
+ struct exprref_common common;
+
+ /* Definition chain. */
+ union varref_def *def;
+
+ int op_occurrence;
+ int has_real_use;
+ };
+
+ #define EXPRUSE_DEF(r) (r)->euse.def
+ #define EXPRUSE_PHIOP(r) (r)->euse.op_occurrence
+ #define EXPRUSE_HAS_REAL_USE(r) (r)->euse.has_real_use
+
+
+ /* }}} */
+
/* {{{ Generic variable reference structure. */
union varref_def
{
! struct treeref_common common;
! struct exprref_common ecommon;
struct vardef def;
struct varuse use;
+ struct expruse euse;
+ struct exprphi ephi;
};
typedef union varref_def *varref;
*************** typedef union varref_def *varref;
*** 117,122 ****
--- 177,192 ----
#define VARREF_STMT(r) (r)->common.stmt
#define VARREF_SYM(r) (r)->common.sym
+ #define EXPRREF_TYPE(r) (r)->common.type
+ #define EXPRREF_BB(r) (r)->common.bb
+ #define EXPRREF_EXPR(r) (r)->common.expr
+ #define EXPRREF_STMT(r) (r)->common.stmt
+ #define EXPRREF_SYM(r) (r)->common.sym
+ #define EXPRREF_CLASS(r) (r)->ecommon.class
+ #define EXPRREF_INSERTED(r) (r)->ecommon.inserted
+ #define EXPRREF_SAVE(r) (r)->ecommon.save
+ #define EXPRREF_RELOAD(r) (r)->ecommon.reload
+
/* Return nonzero if R is a ghost definition. */
#define IS_GHOST_DEF(R) \
(R && VARREF_TYPE (R) == VARDEF && VARREF_BB (R) == ENTRY_BLOCK_PTR)
*************** extern basic_block tree_split_bb PARAMS
*** 288,294 ****
extern void tree_find_varrefs PARAMS ((void));
extern tree_ann get_tree_ann PARAMS ((tree));
! extern varref create_varref PARAMS ((tree, enum varref_type,
basic_block, tree, tree));
extern void debug_varref PARAMS ((varref));
extern void dump_varref PARAMS ((FILE *, const char *, varref, int, int));
--- 358,364 ----
extern void tree_find_varrefs PARAMS ((void));
extern tree_ann get_tree_ann PARAMS ((tree));
! extern varref create_ref PARAMS ((tree, enum treeref_type,
basic_block, tree, tree));
extern void debug_varref PARAMS ((varref));
extern void dump_varref PARAMS ((FILE *, const char *, varref, int, int));
*************** extern void dump_varref_list PARAMS ((FI
*** 298,303 ****
--- 368,379 ----
extern int function_may_recurse_p PARAMS ((void));
extern void get_fcalls PARAMS ((varray_type *, unsigned));
extern basic_block find_declaration PARAMS ((tree));
+
+ /* }}} */
+
+ /* {{{ Functions in tree-ssa-pre.c */
+
+ extern void tree_perform_ssapre PARAMS ((void));
/* }}} */
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-optimize.c,v
retrieving revision 1.1.2.7
diff -c -3 -p -w -B -b -r1.1.2.7 tree-optimize.c
*** tree-optimize.c 29 Dec 2001 17:41:18 -0000 1.1.2.7
--- tree-optimize.c 27 Apr 2002 16:07:44 -0000
*************** build_tree_ssa (t)
*** 79,84 ****
--- 79,86 ----
tree_find_varrefs ();
tree_build_ssa ();
tree_compute_rdefs ();
+ if (flag_tree_ssa_pre)
+ tree_perform_ssapre ();
}
}
Index: tree-ssa-pre.c
===================================================================
RCS file: tree-ssa-pre.c
diff -N tree-ssa-pre.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- tree-ssa-pre.c 27 Apr 2002 16:07:44 -0000
***************
*** 0 ****
--- 1,1614 ----
+ /* SSA-PRE for trees.
+ Copyright (C) 2001 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dan@dberlin.org>
+
+ 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. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "tree.h"
+ #include "flags.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 "diagnostic.h"
+ #include "tree-optimize.h"
+ #include "tree-simple.h"
+ #include "tree-flow.h"
+ #include "tree-inline.h"
+ #include "ssa.h"
+ #include "varray.h"
+ #include "hashtab.h"
+ #include "splay-tree.h"
+ #include "fibheap.h"
+ /* This should be eventually be generalized to other languages, but
+ this would require a shared function-as-trees infrastructure. */
+ #include "c-common.h"
+ #include "c-tree.h"
+ #include "bitmap.h"
+
+
+ struct expr_info;
+ static hashval_t hash_binary_tree PARAMS ((const void *));
+ static int binexpr_lexically_eq PARAMS ((const void *, const void *));
+ static void free_expr_info PARAMS ((void *));
+ static sbitmap compute_idfs PARAMS ((sbitmap *, tree));
+ static void compute_domchildren PARAMS ((int *, sbitmap *));
+
+ static inline bool a_dom_b PARAMS ((basic_block, basic_block));
+ static void set_var_phis PARAMS ((varref, int));
+ static inline varref find_varref_for_var PARAMS ((struct expr_info *, tree, tree));
+ static inline varref find_def_for_stmt PARAMS ((tree));
+ static void expr_phi_insertion PARAMS ((sbitmap *, struct expr_info *));
+ static int pre_part_1_trav PARAMS ((void **, void *));
+ static int add_call_to_ei PARAMS ((void **, void *));
+ static void reset_down_safe PARAMS ((varref));
+ static void down_safety PARAMS ((struct expr_info *));
+ static void will_be_avail PARAMS ((struct expr_info *));
+ static void compute_can_be_avail PARAMS ((struct expr_info *));
+ static void reset_can_be_avail PARAMS ((struct expr_info *, varref));
+ static void compute_later PARAMS ((struct expr_info *));
+ static void reset_later PARAMS ((struct expr_info *, varref));
+ static void code_motion PARAMS ((struct expr_info *, tree));
+ static bool can_insert PARAMS ((varref));
+ static inline bool defs_match_p PARAMS ((struct expr_info *, tree, tree));
+ static inline bool defs_y_dom_x PARAMS ((varref, varref));
+ static void assign_new_class PARAMS ((varref, varray_type *));
+ static void insert_occ_in_preorder_dt_order_1 PARAMS ((struct expr_info *, fibheap_t, basic_block));
+ static void insert_occ_in_preorder_dt_order PARAMS ((struct expr_info *, fibheap_t));
+ static void insert_euse_in_preorder_dt_order_1 PARAMS ((struct expr_info *, fibheap_t, basic_block));
+ static void insert_euse_in_preorder_dt_order PARAMS ((struct expr_info *, fibheap_t));
+ static inline int opnum_of_phi PARAMS ((varref, int));
+ static varray_type phi_opnd_from_res PARAMS ((varref, int, basic_block));
+ static void rename_2 PARAMS ((struct expr_info *, varray_type *));
+ static void rename_1 PARAMS ((struct expr_info *));
+ static void finalize_2 PARAMS ((struct expr_info *));
+ static void finalize_1 PARAMS ((struct expr_info *, tree));
+ static varref phi_for_operand PARAMS ((struct expr_info *, varref));\
+ static void set_save PARAMS ((struct expr_info *, varref));
+ static void set_replacement PARAMS ((struct expr_info *, varref, varref));
+
+ static int *pre_preorder;
+ static int *pre_idom;
+ static sbitmap *pre_dfs;
+ static sbitmap *pre_doms;
+ static FILE *dump_file;
+ static int dump_flags;
+ static int class_count;
+ static int preorder_count;
+
+ /* sbitmap vector mapping blocks to the child blocks they dominate. */
+ static sbitmap *domchildren;
+ struct expr_info
+ {
+ /* The actual expression. */
+ tree expr;
+ /* The occurrences, which can include calls. */
+ varray_type occurs;
+ /* Statements for the occurrences. */
+ varray_type occurstmts;
+ /* An array of real occurrences. */
+ varray_type reals;
+ /* An array mapping reals to the containing statements (so we can
+ get defs/uses/etc about them. */
+ varray_type realstmts;
+ /* The ephis we've added for this expr. */
+ varray_type phis;
+ /* All the erefs. */
+ varray_type erefs;
+
+ };
+
+ /* Returns true if a dominates b */
+ static inline bool
+ a_dom_b (a, b)
+ basic_block a;
+ basic_block b;
+ {
+ if (a->index < 0 || b->index < 0)
+ abort();
+ return TEST_BIT (pre_doms[b->index], a->index);
+ }
+
+
+ /* Compute the domchildren sbitmap vector from the list of immediate
+ dominators. */
+ static void
+ compute_domchildren (idom, domc)
+ int *idom;
+ sbitmap *domc;
+ {
+ int i;
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ if (idom[i] >= 0)
+ SET_BIT (domc[idom[i]], i);
+ }
+ }
+
+ /* Compute the iterated dominance frontier of a statement. */
+ static sbitmap
+ compute_idfs (dfs, stmt)
+ sbitmap *dfs;
+ tree stmt;
+ {
+ fibheap_t worklist;
+ sbitmap inworklist = sbitmap_alloc (n_basic_blocks);
+ sbitmap idf = sbitmap_alloc (n_basic_blocks);
+ size_t i;
+ basic_block block;
+ worklist = fibheap_new ();
+ sbitmap_zero (inworklist);
+ sbitmap_zero (idf);
+ block = BB_FOR_STMT (stmt);
+ fibheap_insert (worklist, block->index, (void *)block->index);
+ SET_BIT (inworklist, block->index);
+
+ while (!fibheap_empty (worklist))
+ {
+ int a = (int) fibheap_extract_min (worklist);
+ sbitmap_a_or_b (idf, idf, dfs[a]);
+ EXECUTE_IF_SET_IN_SBITMAP (dfs[a], 0, i,
+ {
+ if (!TEST_BIT (inworklist, i))
+ {
+ SET_BIT (inworklist, i);
+ fibheap_insert (worklist, i, (void *)i);
+ }
+ });
+ }
+ fibheap_delete (worklist);
+ sbitmap_free (inworklist);
+ return idf;
+
+ }
+
+ /* We need lexically equivalent expressions to be compared using the
+ equality function, so the hash needs to make sure they end up
+ colliding. */
+ static hashval_t
+ hash_binary_tree (v)
+ const void *v;
+ {
+ tree t = (tree) v;
+ return TREE_CODE (t)
+ + TREE_CODE (TREE_OPERAND (t, 0))
+ + TREE_CODE (TREE_OPERAND (t, 1));
+ }
+
+ /* Determine if two expressions are lexically equivalent.
+ The first argument will be the struct expr_info already in the
+ table, the second argument will be a tree to compare for
+ equality. */
+ static int
+ binexpr_lexically_eq (v1, v2)
+ const void *v1;
+ const void *v2;
+ {
+ struct expr_info *e1 = (struct expr_info *) v1;
+ tree t2 = (tree) v2;
+ /* XXX: Is this too restrictive, not restrictive enough, or just right? */
+ return operand_equal_p (e1->expr, t2, 0);
+ }
+
+ /* Free an expression info structure. */
+ static void
+ free_expr_info (v1)
+ void *v1;
+ {
+ struct expr_info *e1 = (struct expr_info *)v1;
+ VARRAY_FREE (e1->occurs);
+ VARRAY_FREE (e1->occurstmts);
+ VARRAY_FREE (e1->reals);
+ VARRAY_FREE (e1->realstmts);
+ VARRAY_FREE (e1->phis);
+ VARRAY_FREE (e1->erefs);
+ free (e1);
+ }
+
+ /* dfphis and varphis, from the paper. */
+ static sbitmap dfphis;
+ static sbitmap *varphis;
+
+ /* Implementation of set_var_phis, as described in paper. */
+ static void
+ set_var_phis (phi, i)
+ varref phi;
+ int i;
+ {
+ if (!TEST_BIT (varphis[i], VARREF_BB (phi)->index))
+ {
+ varref phi_operand;
+ varray_type phi_chain;
+ size_t curr_phi_operand;
+ SET_BIT (varphis[i], VARREF_BB (phi)->index);
+ phi_chain = VARDEF_PHI_CHAIN (phi);
+ for (curr_phi_operand = 0;
+ curr_phi_operand < VARRAY_ACTIVE_SIZE (phi_chain);
+ curr_phi_operand++)
+ {
+ phi_operand = VARRAY_GENERIC_PTR (phi_chain, curr_phi_operand);
+ if (VARREF_TYPE (phi_operand) == VARPHI)
+ set_var_phis (phi_operand, i);
+ }
+ }
+ }
+
+ /* Helper macro to simplify accessing the phi for a given block. */
+ #define phi_at_block(expr, b) VARRAY_GENERIC_PTR ((expr)->phis, pre_preorder[(b)->index])
+
+ /* Helper macro to simplify accessing a phi operand for a given block. */
+ #define phi_operand(phi, b) VARRAY_GENERIC_PTR (EXPRPHI_PHI_CHAIN (phi), pre_preorder[(b)->index])
+
+ /* Given a statement, find the VARDEF in it. */
+ static inline varref
+ find_def_for_stmt (stmt)
+ tree stmt;
+ {
+ size_t i;
+ varray_type treerefs;
+ treerefs = TREE_REFS (stmt);
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (treerefs); i++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (treerefs, i);
+ if (VARREF_TYPE (ref) == VARDEF)
+ return ref;
+ }
+ return NULL;
+ }
+
+ /* Given the expression info, the real occurrence, and a variable,
+ find the VARUSE of the variable contained in that occurrence. */
+ static inline varref
+ find_varref_for_var (ei, real, var)
+ struct expr_info *ei;
+ tree real;
+ tree var;
+ {
+ size_t i;
+ varray_type treerefs;
+ size_t realnum;
+
+ /* Find the realstmt for the real. */
+ for (realnum = 0; realnum < VARRAY_ACTIVE_SIZE (ei->reals); realnum++)
+ if (VARRAY_TREE (ei->reals, realnum) == real)
+ break;
+
+ /* Abort if we can't find one. */
+ if (realnum == VARRAY_ACTIVE_SIZE (ei->reals))
+ abort();
+
+ /* Now look for the use of var in that statement. */
+ treerefs = TREE_REFS (VARRAY_TREE (ei->realstmts, realnum));
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (treerefs); i++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (treerefs, i);
+ if (VARREF_TYPE (ref) != VARUSE
+ || VARREF_EXPR (ref) != real)
+ continue;
+ if (VARREF_SYM (ref) != var)
+ continue;
+ if (!VARUSE_CHAIN (ref))
+ continue;
+ return ref;
+ }
+ return NULL;
+ }
+ /* Determine if the definitions of variables in Y dominate the basic
+ block of X. */
+ static inline bool
+ defs_y_dom_x ( y, x)
+ varref y;
+ varref x;
+ {
+ size_t i,j;
+ varray_type treerefs;
+
+ treerefs = TREE_REFS (EXPRREF_STMT (y));
+
+ /* It's a binary expression, so it has only two operands. */
+
+ for (i = 0; i < 2; i++)
+ {
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (treerefs) ; j++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (treerefs, j);
+ /* Find the ref for this operand. */
+ if (VARREF_TYPE (ref) != VARUSE
+ || VARREF_EXPR (ref) != EXPRREF_EXPR (y))
+ continue;
+ if (VARREF_SYM (ref) != TREE_OPERAND (EXPRREF_EXPR (y), i))
+ continue;
+ if (!VARUSE_CHAIN (ref))
+ return false;
+ if (!(a_dom_b (VARREF_BB (VARUSE_CHAIN (ref)), EXPRREF_BB (x))))
+ return false;
+ break;
+ }
+ }
+ return true;
+ }
+
+ /* Return true if the variables in t1 have the same defs as the
+ variables in t2. */
+ static inline bool
+ defs_match_p (ei, t1, t2)
+ struct expr_info *ei;
+ tree t1;
+ tree t2;
+ {
+ size_t i;
+ varref use1;
+ varref use2;
+ varray_type refs1 = TREE_REFS (t1);
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (refs1); i++)
+ {
+ use1 = VARRAY_GENERIC_PTR (refs1, i);
+ if (VARREF_TYPE (use1) != VARUSE ||
+ (TREE_CODE (VARREF_EXPR (use1)) != TREE_CODE (t2)))
+ continue;
+ use2 = find_varref_for_var (ei, t2, VARREF_SYM (use1));
+ if (VARUSE_CHAIN (use2) != VARUSE_CHAIN (use1))
+ return false;
+ }
+ return true;
+ }
+
+ /* Assign a new redundancy class to the occurrence, and push it on the
+ stack. */
+ static void
+ assign_new_class (occ, stack)
+ varref occ;
+ varray_type *stack;
+ {
+ EXPRREF_CLASS (occ) = class_count;
+ VARRAY_PUSH_GENERIC_PTR (*stack, occ);
+ class_count++;
+ }
+
+ /* Insert the expressions in preorder DT order in the fibheap. */
+ static void
+ insert_euse_in_preorder_dt_order_1 (ei, fh, block)
+ struct expr_info *ei;
+ fibheap_t fh;
+ basic_block block;
+ {
+ size_t i;
+ varray_type bbrefs = ei->erefs;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (bbrefs); i++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (bbrefs, i);
+ if (EXPRREF_BB (ref) != block)
+ continue;
+ if (EXPRREF_TYPE (ref) == EXPRUSE || EXPRREF_TYPE (ref) == EXPRPHI)
+ {
+ fibheap_insert (fh, preorder_count++, ref);
+ }
+ }
+ EXECUTE_IF_SET_IN_SBITMAP (domchildren[block->index], 0, i,
+ {
+ insert_euse_in_preorder_dt_order_1 (ei, fh, BASIC_BLOCK (i));
+ });
+ }
+
+
+ static void
+ insert_euse_in_preorder_dt_order (ei, fh)
+ struct expr_info *ei;
+ fibheap_t fh;
+ {
+ preorder_count = 0;
+ insert_euse_in_preorder_dt_order_1 (ei, fh, BASIC_BLOCK (0));
+ }
+
+ /* Insert the occurrences in preorder DT order, in the fibheap. */
+ static void
+ insert_occ_in_preorder_dt_order_1 (ei, fh, block)
+ struct expr_info *ei;
+ fibheap_t fh;
+ basic_block block;
+ {
+ size_t i;
+ edge succ;
+ if (phi_at_block (ei, block) != NULL)
+ {
+ fibheap_insert (fh, preorder_count++, phi_at_block (ei, block));
+ }
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->occurs); i++)
+ {
+ varref newref;
+ tree occurstmt = VARRAY_TREE (ei->occurstmts, i);
+ if (BB_FOR_STMT (occurstmt) != block)
+ continue;
+ if (TREE_CODE (VARRAY_TREE (ei->occurs, i)) == CALL_EXPR)
+ {
+ newref = create_ref (VARRAY_TREE (ei->occurs, i),
+ EXPRKILL, block, occurstmt,
+ VARRAY_TREE (ei->occurs, i));
+ VARRAY_PUSH_GENERIC_PTR (ei->erefs, newref);
+ fibheap_insert (fh, preorder_count++, newref);
+ }
+ else
+ {
+ newref = create_ref (VARRAY_TREE (ei->occurs, i),
+ EXPRUSE, block, occurstmt,
+ VARRAY_TREE (ei->occurs, i));
+ VARRAY_PUSH_GENERIC_PTR (ei->erefs, newref);
+ EXPRUSE_DEF (newref) = NULL;
+ EXPRREF_CLASS (newref) = 0;
+ EXPRUSE_PHIOP (newref) = 0;
+ EXPRUSE_HAS_REAL_USE (newref) = 0;
+ fibheap_insert (fh, preorder_count++, newref);
+ }
+ }
+
+ /* Insert the phi operand occurrences's in the heap at the
+ successors.*/
+ for (succ = block->succ; succ; succ = succ->succ_next)
+ {
+ if (succ->dest != EXIT_BLOCK_PTR)
+ {
+ if (phi_at_block (ei, succ->dest) != NULL)
+ {
+ varref newref = create_ref (NULL, EXPRUSE, block, 0, 0);
+ varref phi = phi_at_block (ei, succ->dest);
+ VARRAY_PUSH_GENERIC_PTR (ei->erefs, newref);
+ EXPRUSE_DEF (newref) = NULL;
+ EXPRREF_CLASS (newref) = 0;
+ EXPRUSE_PHIOP (newref) = 1;
+ EXPRUSE_HAS_REAL_USE (newref) = 0;
+ EXPRREF_SAVE (newref) = 0;
+ EXPRREF_RELOAD (newref) = 0;
+ EXPRREF_INSERTED (newref) = 0;
+ phi_operand (phi, block) = newref;
+ fibheap_insert (fh, preorder_count++, newref);
+ }
+ }
+
+ else
+ {
+ fibheap_insert (fh, preorder_count++, (void *) EXIT_BLOCK_PTR);
+ }
+
+ }
+ EXECUTE_IF_SET_IN_SBITMAP (domchildren[block->index], 0, i,
+ {
+ insert_occ_in_preorder_dt_order_1 (ei, fh, BASIC_BLOCK (i));
+ });
+ }
+
+ static void
+ insert_occ_in_preorder_dt_order (ei, fh)
+ struct expr_info *ei;
+ fibheap_t fh;
+ {
+ preorder_count = 0;
+ insert_occ_in_preorder_dt_order_1 (ei, fh, BASIC_BLOCK (0));
+ }
+
+ /* Determine the phi operand index for J, for PHI. */
+ static inline int
+ opnum_of_phi (phi, j)
+ varref phi;
+ int j;
+ {
+ size_t i;
+ /* We can't just count predecessors, since tree-ssa.c generates them
+ when it sees a phi in the successor during it's traversal. So the
+ order is dependent on the traversal order, which i don't feel like
+ duplicating. Thus the existence of VARDEF_PHI_CHAIN_BB. */
+ for (i = 0 ; i < VARRAY_ACTIVE_SIZE (VARDEF_PHI_CHAIN_BB (phi)); i++)
+ {
+ basic_block bb = VARRAY_BB (VARDEF_PHI_CHAIN_BB (phi), i);
+ if (bb->index == j)
+ return i;
+ }
+
+ abort();
+ }
+
+ /* Factor variables through phi operands. */
+ static varray_type
+ phi_opnd_from_res (Z, j, b)
+ varref Z;
+ int j;
+ basic_block b;
+ {
+ varray_type Q;
+ varray_type Zrefs;
+ size_t i;
+ VARRAY_GENERIC_PTR_INIT (Q, 1, "Temp ops");
+ Zrefs = TREE_REFS (EXPRREF_STMT (Z));
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (Zrefs); i++)
+ {
+ VARRAY_PUSH_GENERIC_PTR (Q, VARRAY_GENERIC_PTR (Zrefs, i));
+ }
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (Zrefs); i++)
+ {
+ varref v;
+ v = VARRAY_GENERIC_PTR (Zrefs, i);
+ if (VARREF_TYPE (v) == VARUSE
+ && VARREF_TYPE (VARUSE_CHAIN (v)) == VARPHI)
+ {
+ varref phi = VARUSE_CHAIN (v);
+ if (VARREF_BB (phi) == b)
+ {
+ int opnum = opnum_of_phi (phi, j);
+ varref op = VARRAY_GENERIC_PTR (VARDEF_PHI_CHAIN (phi), opnum);
+ VARRAY_GENERIC_PTR (Q, i) = op;
+ }
+
+ }
+ else if (VARREF_TYPE (v) == VARDEF
+ || VARREF_TYPE (v) == VARPHI
+ || EXPRREF_TYPE (v) == EXPRUSE)
+ {
+ VARRAY_GENERIC_PTR (Q, i) = NULL;
+ }
+ }
+ return Q;
+ }
+
+ /* Second pass of delayed renaming algorithm. */
+ static void
+ rename_2 (ei, rename2_set)
+ struct expr_info *ei;
+ varray_type *rename2_set;
+ {
+ size_t i;
+ for (i = 0; i < VARRAY_SIZE (ei->phis); i++)
+ {
+ varref phi = VARRAY_GENERIC_PTR (ei->phis, i);
+ if (phi != NULL)
+ bitmap_clear (EXPRPHI_PROCESSED(phi));
+ }
+ while (VARRAY_ACTIVE_SIZE (*rename2_set) > 0)
+ {
+ varref Z;
+ varref phiZ;
+ Z = VARRAY_TOP_GENERIC_PTR (*rename2_set);
+ VARRAY_POP (*rename2_set);
+ phiZ = EXPRUSE_DEF (Z);
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ varref w;
+ basic_block blocki = BASIC_BLOCK (i);
+ if (phi_operand (phiZ, blocki) == NULL)
+ continue;
+ w = phi_operand (phiZ, blocki);
+ if (!bitmap_bit_p (EXPRPHI_PROCESSED (phiZ), i))
+ {
+ /* j = i because we lookup the real index in the
+ function. */
+ int j = i;
+ size_t k;
+ varray_type Y;
+ varref X;
+ varray_type Xops;
+ Y = phi_opnd_from_res (Z, j, EXPRREF_BB (phiZ));
+ X = EXPRUSE_DEF (w);
+ if (!X)
+ continue;
+
+ if (EXPRREF_TYPE (X) == EXPRUSE)
+ {
+ bool match = true;
+ Xops = TREE_REFS (EXPRREF_STMT (X));
+ for (k = 0; k < VARRAY_ACTIVE_SIZE (Xops); k++)
+ {
+ varref op1 = VARRAY_GENERIC_PTR (Xops, k);
+ varref op2;
+ if (VARREF_TYPE (op1) != VARUSE)
+ continue;
+ if (VARREF_TYPE (op1) == VARUSE)
+ op1 = VARUSE_CHAIN (op1);
+ op2 = VARRAY_GENERIC_PTR (Y, k);
+
+ if (op2 && VARREF_TYPE (op2) == VARUSE)
+ op2 = VARUSE_CHAIN (op2);
+
+ if (op1 != op2)
+ {
+ match = false;
+ break;
+ }
+ }
+ if (!match)
+ {
+ EXPRUSE_DEF (w) = NULL;
+ EXPRUSE_HAS_REAL_USE (w) = 0;
+ }
+ else
+ {
+ EXPRUSE_HAS_REAL_USE (w) = 1;
+ }
+ }
+ else /* X is a ExprPhi occurrence */
+ {
+ bool match = true;
+ for (k = 0; k < VARRAY_ACTIVE_SIZE (Y); k++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (Y, k);
+ if (!ref)
+ continue;
+ if (VARREF_TYPE (ref) == VARUSE)
+ ref = VARUSE_CHAIN (ref);
+
+ if (!a_dom_b (VARREF_BB (ref), EXPRREF_BB (X)))
+ {
+ match = false;
+ break;
+ }
+ }
+ if (match)
+ {
+ VARRAY_PUSH_GENERIC_PTR (*rename2_set, Z);
+ }
+ else
+ {
+ EXPRUSE_DEF (w) = NULL;
+ EXPRPHI_DOWNSAFE (phiZ) = 0;
+ }
+ }
+ bitmap_set_bit (EXPRPHI_PROCESSED (phiZ), i);
+
+ }
+ }
+ }
+ }
+
+ /* First pass of delayed renaming algorithm. */
+ static void
+ rename_1 (ei)
+ struct expr_info *ei;
+ {
+ fibheap_t fh = fibheap_new ();
+ varref y;
+ varray_type stack;
+ varray_type rename2_set;
+ VARRAY_GENERIC_PTR_INIT (stack, 1, "Stack");
+ VARRAY_GENERIC_PTR_INIT (rename2_set, 1, "Rename2 set");
+ class_count = 1;
+ insert_occ_in_preorder_dt_order (ei, fh);
+ while (!fibheap_empty (fh))
+ {
+ y = fibheap_extract_min (fh);
+ if ((basic_block) y == EXIT_BLOCK_PTR)
+ {
+ if (VARRAY_ACTIVE_SIZE (stack) > 0)
+ {
+ varref stackref = VARRAY_TOP_GENERIC_PTR (stack);
+ if (EXPRREF_TYPE (stackref) == EXPRPHI)
+ EXPRPHI_DOWNSAFE (stackref) = 0;
+ }
+ continue;
+ }
+ if (EXPRREF_TYPE (y) == EXPRKILL
+ && TREE_CODE (EXPRREF_EXPR (y)) == CALL_EXPR)
+ {
+ if (VARRAY_ACTIVE_SIZE (stack) > 0)
+ {
+ varref stackref = VARRAY_TOP_GENERIC_PTR (stack);
+ if (EXPRREF_TYPE (stackref) == EXPRPHI)
+ EXPRPHI_DOWNSAFE (stackref) = 0;
+ VARRAY_POP_ALL (stack);
+ }
+ continue;
+ }
+
+ while (VARRAY_ACTIVE_SIZE (stack) > 0)
+ {
+ varref stackref = VARRAY_TOP_GENERIC_PTR (stack);
+ if (a_dom_b (EXPRREF_BB (stackref), EXPRREF_BB (y)))
+ break;
+ VARRAY_POP (stack);
+ }
+ /* (EXPRPHI == ExprPHI occurrence. */
+ if (EXPRREF_TYPE (y) == EXPRPHI)
+ {
+ assign_new_class (y, &stack);
+ }
+ /* Non-NOP_EXPR == real occurrence */
+ else if (EXPRREF_TYPE (y) == EXPRUSE && EXPRUSE_PHIOP (y) == 0)
+ {
+ /* If stack is empty, assign new class */
+ if (VARRAY_ACTIVE_SIZE (stack) == 0)
+ {
+ assign_new_class ( y, &stack);
+ }
+ else
+ {
+ varref x = VARRAY_TOP_GENERIC_PTR (stack);
+ /* If X is a real occurrence. */
+ if (EXPRREF_TYPE (x) == EXPRUSE)
+ {
+ /* If all corresponding variables in Y and X have
+ the same version. */
+ if (defs_match_p (ei, EXPRREF_STMT (y), EXPRREF_EXPR (x)))
+ {
+ /* class(Y) <- class(X)
+ def(Y) <- X */
+ EXPRREF_CLASS (y) = EXPRREF_CLASS (x);
+ #if not_in_open64
+ EXPRUSE_DEF (y) = x;
+ #else
+ EXPRUSE_DEF (y) = EXPRUSE_DEF (x) != NULL ? EXPRUSE_DEF (x) : x;
+ #endif
+ }
+ else
+ {
+ assign_new_class ( y, &stack);
+ }
+ }
+ else /* X is a ExprPhi occurrence. */
+ {
+ if (EXPRREF_TYPE (x) != EXPRPHI)
+ abort();
+ if (defs_y_dom_x (y, x))
+ {
+ /* class(Y) <- class(X)
+ def(Y) <- X
+ set_for_rename2 <- set_for_rename2 U {Y} */
+ EXPRREF_CLASS (y) = EXPRREF_CLASS (x);
+ EXPRUSE_DEF (y) = x;
+
+
+ /* Open64 does this, and without it, we prevent optimization on the
+ following code:
+
+
+ int a;
+ int b;
+ b = 5;
+ int e = 0;
+ int f = 0;
+ if (argc)
+ {
+ a = 3;
+ e = a + b;
+ }
+ else
+ {
+ a = 4;
+ }
+ f = a + b;
+
+ Without pushing here, the expr-phi that appears right before f = a + b
+ will be at the top of stack when we hit the exit node. Thus, it will
+ be marked *not* down safe. This prevents optimization from occurring
+ anywhere.
+
+ Clearly, however, a + b is partially redundant, and the phi *will* be
+ downsafe at the end of PRE, because we will insert an evaluation right
+ after a = 4;
+ There is provably no harm in pushing anyway, because if the pushed value
+ doesn't dominate whatever occurrences we see while it's at the top,
+ we'll pop it, and if the phi isn't really going to be downsafe, we'll
+ catch it in rename_2 or during downsafety propagation. */
+
+ VARRAY_PUSH_GENERIC_PTR (stack, y);
+
+ VARRAY_PUSH_GENERIC_PTR (rename2_set, y);
+ }
+ else
+ {
+ EXPRPHI_DOWNSAFE (x) = 0;
+ assign_new_class ( y, &stack);
+ }
+ }
+ }
+ }
+ /* ExprPhi operand occurrence. */
+ else if (EXPRREF_TYPE (y) == EXPRUSE && EXPRUSE_PHIOP (y) == 1)
+ {
+ if (VARRAY_ACTIVE_SIZE (stack) == 0)
+ {
+ /* def(Y) <- tack */
+ EXPRUSE_DEF (y) = NULL;
+ }
+ else
+ {
+
+ /* X = Top(stack)
+ class(Y) <- class(X)
+ def(Y) <- X */
+ varref x = VARRAY_TOP_GENERIC_PTR (stack);
+ EXPRREF_CLASS (y) = EXPRREF_CLASS (x);
+ EXPRUSE_DEF (y) = x;
+ }
+ }
+ else
+ abort();
+ }
+ rename_2 (ei, &rename2_set);
+ fibheap_delete (fh);
+ VARRAY_FREE (stack);
+ VARRAY_FREE (rename2_set);
+
+ }
+
+ /* XXX: Do this smarter */
+ /* Figure out which PHI contains the operand. */
+ static varref
+ phi_for_operand (ei, operand)
+ struct expr_info *ei;
+ varref operand;
+ {
+ int i;
+ int count = 0;
+ varref retval = NULL;
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ varref phi = phi_at_block (ei, BASIC_BLOCK (i));
+ if (phi != NULL)
+ {
+ int j;
+ for (j = 0; j < n_basic_blocks; j++)
+ if (phi_operand (phi, BASIC_BLOCK (j)) == operand)
+ {
+ count++;
+ retval = phi;
+ }
+ }
+ }
+ /* Theoretically, phi operand to phi is a 1 to many mapping. But we
+ don't return more than one value right now, so if we found multiple
+ phis containing this operand, abort. */
+ if (count > 1)
+ abort();
+
+ return retval;
+ }
+
+ /* Figure out which expressions need to be saved. */
+ static void
+ set_save (ei, X)
+ struct expr_info *ei;
+ varref X;
+ {
+ if (EXPRREF_TYPE (X) == EXPRUSE && !EXPRUSE_PHIOP (X))
+ EXPRREF_SAVE (X) = 1;
+ else if (EXPRREF_TYPE (X) == EXPRPHI)
+ {
+ int i;
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ varref w = phi_operand (X, BASIC_BLOCK (i));
+ if (w && !bitmap_bit_p (EXPRPHI_PROCESSED (X), i))
+ {
+ bitmap_set_bit (EXPRPHI_PROCESSED (X), i);
+ set_save (ei, EXPRUSE_DEF (w));
+ }
+ }
+ }
+ if (EXPRREF_TYPE (X) == EXPRUSE && !EXPRUSE_PHIOP (X))
+ {
+ sbitmap idfs = compute_idfs (pre_dfs, EXPRREF_STMT (X));
+ int i;
+ EXECUTE_IF_SET_IN_SBITMAP (idfs, 0, i,
+ {
+ varref phi = phi_at_block (ei, BASIC_BLOCK (i));
+ if (phi != NULL && EXPRPHI_WILLBEAVAIL (phi))
+ EXPRPHI_EXTRANEOUS (phi) = 0;
+ });
+ sbitmap_free (idfs);
+ }
+ }
+
+ /* Set replacement for ExprPhi minimization. */
+ static void
+ set_replacement (ei, g, replacing_def)
+ struct expr_info *ei;
+ varref g;
+ varref replacing_def;
+ {
+ int i;
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ int j;
+ size_t k;
+ varref f = phi_at_block (ei, BASIC_BLOCK (i));
+ if (f == NULL || !EXPRPHI_WILLBEAVAIL (f))
+ continue;
+ for (j = 0; j < n_basic_blocks; j++)
+ {
+ varref operand = phi_operand (f, BASIC_BLOCK (j));
+ if (operand && EXPRUSE_DEF (operand) == g)
+ {
+ if (EXPRPHI_EXTRANEOUS (f))
+ set_replacement (ei, f, replacing_def);
+ else
+ phi_operand (f, BASIC_BLOCK (j)) = replacing_def;
+ }
+ }
+ for (k = 0; k < VARRAY_ACTIVE_SIZE (ei->erefs); k++)
+ {
+ varref X = VARRAY_GENERIC_PTR (ei->erefs, k);
+ if (EXPRREF_TYPE (X) == EXPRUSE
+ && EXPRUSE_PHIOP (X) == 0
+ && EXPRREF_RELOAD (X)
+ && EXPRUSE_DEF (X) == g)
+ {
+ EXPRUSE_DEF (X) = replacing_def;
+ }
+ }
+ }
+ phi_at_block (ei, EXPRREF_BB (g)) = NULL;
+
+ }
+
+ /* Second part of finalize algorithm. */
+ static void
+ finalize_2 (ei)
+ struct expr_info *ei;
+ {
+ size_t i;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->erefs); i++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (ei->erefs, i);
+ if (EXPRREF_TYPE (ref) == EXPRPHI)
+ {
+ bitmap_clear (EXPRPHI_PROCESSED (ref));
+ if (EXPRPHI_WILLBEAVAIL (ref))
+ EXPRPHI_EXTRANEOUS (ref) = 1;
+ }
+ else if (EXPRREF_TYPE (ref) == EXPRUSE
+ && EXPRUSE_PHIOP (ref) == 0)
+ {
+ EXPRREF_SAVE (ref) = 0;
+ }
+ }
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->erefs); i++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (ei->erefs, i);
+ if (EXPRREF_TYPE (ref) == EXPRUSE
+ && EXPRUSE_PHIOP (ref) == 0)
+ {
+ if (EXPRREF_RELOAD (ref))
+ set_save (ei, EXPRUSE_DEF (ref));
+ }
+ }
+ /* This is pointless unless we plan on performing more ESSA passes. */
+ #if EXTRANEOUS_EPHI_REMOVAL
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ varref ref = phi_at_block (ei, BASIC_BLOCK (i));
+ if (!ref)
+ continue;
+ if (EXPRPHI_WILLBEAVAIL (ref))
+ {
+ int k;
+ for (k = 0; k < n_basic_blocks; k++)
+ {
+ varref w = phi_operand (ref, BASIC_BLOCK (k));
+ varref defw;
+ if (!w || !EXPRUSE_DEF (w) )
+ continue;
+ defw = EXPRUSE_DEF (w);
+ if ((EXPRREF_TYPE (defw) == EXPRPHI
+ && !EXPRPHI_EXTRANEOUS (defw))
+ || (EXPRREF_TYPE (defw) == EXPRUSE
+ && !EXPRUSE_PHIOP (defw)))
+ set_replacement (ei, ref, EXPRUSE_DEF (w));
+ }
+ }
+ else
+ {
+ phi_at_block (ei, EXPRREF_BB (ref)) = NULL;
+ }
+ }
+ #endif
+ }
+
+ /* First part of finalize algorithm. */
+ static void
+ finalize_1 (ei, temp)
+ struct expr_info *ei;
+ tree temp;
+ {
+ varref *avdefs;
+ varref X;
+ int x;
+ fibheap_t fh;
+ avdefs = xcalloc (class_count + 1,sizeof (varref));
+ fh = fibheap_new ();
+ insert_euse_in_preorder_dt_order (ei, fh);
+ while (!fibheap_empty (fh))
+ {
+ X = fibheap_extract_min (fh);
+ x = EXPRREF_CLASS (X);
+ if (EXPRREF_TYPE (X) == EXPRPHI)
+ {
+ if (EXPRPHI_WILLBEAVAIL (X))
+ avdefs[x] = X;
+ }
+ else if (EXPRREF_TYPE (X) == EXPRUSE && EXPRUSE_PHIOP (X) == 0)
+ {
+ #if 0
+ /* Unnecessary now, because we handle it in renaming. But
+ it would work here as well. */
+ if (TREE_CODE (EXPRREF_EXPR (X)) == CALL_EXPR)
+ {
+ memset (avdefs, 0, sizeof (varref *) * class_count);
+ continue;
+ }
+ #endif
+ if (avdefs[x] == NULL
+ || !a_dom_b (EXPRREF_BB (avdefs[x]), EXPRREF_BB (X)))
+ {
+ EXPRREF_RELOAD (X) = 0;
+ avdefs[x] = X;
+ }
+ else
+ {
+ EXPRREF_RELOAD (X) = 1;
+ EXPRUSE_DEF (X) = avdefs[x];
+ }
+ }
+ else
+ {
+ varref phi = phi_for_operand (ei, X);
+ if (!phi)
+ abort ();
+ if (EXPRPHI_WILLBEAVAIL (phi))
+ {
+ if (can_insert (X))
+ {
+ tree stmt;
+ tree expr;
+ /* Insert definition of expr at end of BB containing X. */
+ if (dump_file)
+ {
+
+ fprintf (dump_file, "In BB %d, insert save of ",
+ EXPRREF_BB (X)->index);
+ print_c_tree (dump_file, ei->expr);
+ fprintf (dump_file, " to ");
+ print_c_tree (dump_file, temp);
+ fprintf (dump_file, " at end of BB, because of ExprPhi");
+ fprintf (dump_file, " in BB %d\n",
+ EXPRREF_BB (phi)->index);
+ }
+ expr = build_modify_expr (temp, NOP_EXPR, ei->expr);
+ stmt = build_stmt (EXPR_STMT, expr);
+ insert_stmt_tree_after (stmt,
+ BLOCK_END_TREE (EXPRREF_BB (X)->index),
+ EXPRREF_BB (X));
+ EXPRUSE_DEF (X) = create_ref (expr, EXPRUSE,
+ EXPRREF_BB (X), stmt, expr);
+ VARRAY_PUSH_GENERIC_PTR (ei->erefs, EXPRUSE_DEF (X));
+ EXPRREF_RELOAD (EXPRUSE_DEF (X)) = 0;
+ EXPRREF_SAVE (EXPRUSE_DEF (X)) = 0;
+ EXPRREF_INSERTED (EXPRUSE_DEF (X)) = 1;
+ EXPRUSE_PHIOP (EXPRUSE_DEF (X)) = 0;
+ EXPRUSE_HAS_REAL_USE (EXPRUSE_DEF (X)) = 0;
+
+ /*
+ EXPRUSE_DEF (X) = new occurrence.
+ */
+ }
+ else
+ {
+ EXPRUSE_DEF (X) = avdefs[x];
+ }
+ }
+ }
+ }
+ fibheap_delete (fh);
+ free (avdefs);
+ }
+
+ /* ExprPhi insertion algorithm. */
+ static void
+ expr_phi_insertion (dfs, ei)
+ sbitmap *dfs;
+ struct expr_info *ei;
+ {
+ size_t i,j;
+ dfphis = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (dfphis);
+ varphis = sbitmap_vector_alloc (2, n_basic_blocks);
+ sbitmap_vector_zero (varphis, 2);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->reals); i++)
+ {
+ tree real = VARRAY_TREE (ei->reals, i);
+ sbitmap temp = compute_idfs (dfs, VARRAY_TREE (ei->realstmts, i));
+ sbitmap_a_or_b (dfphis, dfphis, temp);
+ sbitmap_free (temp);
+ if (DECL_P (TREE_OPERAND (real, 0)) || DECL_P (TREE_OPERAND (real, 1)))
+ {
+ varray_type treerefs;
+ varref ref;
+ int varcount = 0;
+ treerefs = TREE_REFS (VARRAY_TREE (ei->realstmts, i));
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (treerefs); j++)
+ {
+ ref = VARRAY_GENERIC_PTR (treerefs, j);
+ if (VARREF_TYPE (ref) != VARUSE
+ || VARREF_EXPR (ref) != real)
+ continue;
+ if (VARREF_SYM (ref) != TREE_OPERAND (real, 0)
+ && VARREF_SYM (ref) != TREE_OPERAND (real, 1))
+ continue;
+ if (VARREF_TYPE (VARUSE_CHAIN (ref)) != VARPHI)
+ continue;
+ set_var_phis (VARUSE_CHAIN (ref), varcount++);
+ }
+ }
+ }
+ sbitmap_a_or_b (dfphis, dfphis, varphis[0]);
+ sbitmap_a_or_b (dfphis, dfphis, varphis[1]);
+
+ EXECUTE_IF_SET_IN_SBITMAP(dfphis, 0, i,
+ {
+ varref ref = create_ref (NULL, EXPRPHI,
+ BASIC_BLOCK (i),
+ NULL, ei->expr);
+ VARRAY_PUSH_GENERIC_PTR (ei->erefs, ref);
+ EXPRPHI_DOWNSAFE (ref) = 1;
+ EXPRPHI_CANBEAVAIL (ref) = 1;
+ EXPRPHI_LATER (ref) = 1;
+ EXPRPHI_EXTRANEOUS (ref) = 1;
+ VARRAY_GENERIC_PTR (ei->phis, pre_preorder[i]) = ref;
+ });
+ sbitmap_free (dfphis);
+ sbitmap_vector_free (varphis);
+ }
+
+ /* Reset down safety flags. */
+ static void
+ reset_down_safe (phiop)
+ varref phiop;
+ {
+ varref phi;
+ int i;
+
+ if (EXPRUSE_HAS_REAL_USE (phiop))
+ return;
+ phi = EXPRUSE_DEF (phiop);
+ if (!phi || EXPRREF_TYPE (phi) != EXPRPHI)
+ return;
+ if (!EXPRPHI_DOWNSAFE (phi))
+ return;
+ EXPRPHI_DOWNSAFE (phi) = 0;
+ for (i = 0; i < n_basic_blocks; i++)
+ if (phi_operand (phi, BASIC_BLOCK (i)) != NULL)
+ reset_down_safe (phi_operand (phi, BASIC_BLOCK (i)));
+ }
+
+ /* Compute down_safety. */
+ static void
+ down_safety (ei)
+ struct expr_info *ei;
+ {
+ int i;
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ basic_block block = BASIC_BLOCK (i);
+ varref phi = phi_at_block (ei, block);
+ int j;
+ if (phi == NULL || EXPRPHI_DOWNSAFE (phi))
+ continue;
+ for (j = 0; j < n_basic_blocks; j++)
+ if (phi_operand (phi, BASIC_BLOCK (j)) != NULL)
+ reset_down_safe (phi_operand (phi, BASIC_BLOCK (j)));
+ }
+ }
+
+ /* Compute can_be_avail. */
+ static void
+ compute_can_be_avail (ei)
+ struct expr_info *ei;
+ {
+ int i;
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ basic_block block = BASIC_BLOCK (i);
+ varref phi = phi_at_block (ei, block);
+ if (phi == NULL)
+ continue;
+ EXPRPHI_CANBEAVAIL (phi) = 1;
+ }
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ basic_block block = BASIC_BLOCK (i);
+ varref phi = phi_at_block (ei, block);
+ edge pred;
+ if (phi == NULL)
+ continue;
+ if (!EXPRPHI_CANBEAVAIL(phi))
+ continue;
+ if (EXPRPHI_DOWNSAFE (phi))
+ continue;
+
+ for (pred = block->pred; pred; pred = pred->pred_next)
+ {
+ if (pred->src != ENTRY_BLOCK_PTR)
+ {
+ varref operand = phi_operand (phi, pred->src);
+ if (EXPRUSE_DEF (operand) == NULL)
+ {
+ reset_can_be_avail (ei, phi);
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ /* Reset can_be_avail flags. */
+ static void
+ reset_can_be_avail (ei, phi)
+ struct expr_info *ei;
+ varref phi;
+ {
+ int i;
+ EXPRPHI_CANBEAVAIL (phi) = 0;
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ edge pred;
+ basic_block block = BASIC_BLOCK (i);
+ varref other = phi_at_block (ei, block);
+
+ if (other == NULL)
+ continue;
+
+ for (pred = block->pred; pred; pred = pred->pred_next)
+ {
+ if (pred->src != ENTRY_BLOCK_PTR)
+ {
+ varref operand = phi_operand (other, pred->src);
+ if (EXPRUSE_DEF (operand) == phi)
+ {
+ if (!EXPRUSE_HAS_REAL_USE(operand))
+ {
+ /* chow97 has this, kennedy99 does not
+ EXPRUSE_DEF (operand) = NULL;*/
+ if (!EXPRPHI_DOWNSAFE (other)
+ && EXPRPHI_CANBEAVAIL (other))
+ reset_can_be_avail (ei, other);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /* Reset later flags. */
+ static void
+ reset_later (ei, phi)
+ struct expr_info *ei;
+ varref phi;
+ {
+ int i;
+ EXPRPHI_LATER (phi) = 0;
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ edge pred;
+ basic_block block = BASIC_BLOCK (i);
+ varref other = phi_at_block (ei, block);
+
+ if (other == NULL)
+ continue;
+
+ for (pred = block->pred; pred; pred = pred->pred_next)
+ {
+ if (pred->src != ENTRY_BLOCK_PTR)
+ {
+ varref operand = phi_operand (other, pred->src);
+ if (EXPRUSE_DEF (operand) == phi)
+ {
+ if (EXPRPHI_LATER (other))
+ reset_later (ei, other);
+ }
+ }
+ }
+ }
+ }
+
+ /* Compute later flags. */
+ static void
+ compute_later (ei)
+ struct expr_info *ei;
+ {
+ int i;
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ basic_block block = BASIC_BLOCK (i);
+ varref phi = phi_at_block (ei, block);
+ if (phi == NULL)
+ continue;
+ EXPRPHI_LATER (phi) = EXPRPHI_CANBEAVAIL (phi);
+ }
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ basic_block block = BASIC_BLOCK (i);
+ varref phi = phi_at_block (ei, block);
+ edge pred;
+ if (phi == NULL)
+ continue;
+ if (!EXPRPHI_LATER (phi))
+ continue;
+
+ for (pred = block->pred; pred; pred = pred->pred_next)
+ {
+ if (pred->src != ENTRY_BLOCK_PTR)
+ {
+ varref operand = phi_operand (phi, pred->src);
+ if (EXPRUSE_DEF (operand) != NULL
+ && EXPRUSE_HAS_REAL_USE (operand))
+ reset_later (ei, phi);
+ }
+ }
+ }
+ }
+
+ /* Determine if we can insert the phi. */
+ static bool
+ can_insert (op)
+ varref op;
+ {
+
+ varref def;
+ if (EXPRUSE_DEF (op) == NULL)
+ return true;
+ def = EXPRUSE_DEF (op);
+ if (!EXPRUSE_HAS_REAL_USE (op))
+ if (EXPRREF_TYPE (def) == EXPRPHI && !(EXPRPHI_WILLBEAVAIL (def)))
+ return true;
+ return false;
+ }
+
+ /* Perform actual code motion. */
+ static void
+ code_motion (ei, temp)
+ struct expr_info *ei;
+ tree temp;
+ {
+ fibheap_t exprs;
+ varref use;
+
+ exprs = fibheap_new ();
+ insert_euse_in_preorder_dt_order (ei, exprs);
+ while (!fibheap_empty (exprs))
+ {
+ use = fibheap_extract_min (exprs);
+ if (EXPRREF_TYPE (use) == EXPRUSE /*&& !EXPRUSE_PHIOP (use) */
+ && !EXPRREF_INSERTED (use))
+ {
+ if (EXPRREF_SAVE (use))
+ {
+ basic_block use_bb = EXPRREF_BB (use);
+ tree use_stmt = EXPRREF_STMT (use);
+ tree use_expr = EXPRREF_EXPR (use);
+ tree newexpr;
+ if (dump_file)
+ {
+ fprintf (dump_file, "In BB %d, insert save of ",
+ use_bb->index);
+ print_c_tree (dump_file, use_expr);
+ fprintf (dump_file, " to ");
+ print_c_tree (dump_file, temp);
+ fprintf (dump_file, " in statement ");
+ print_c_tree (dump_file, TREE_OPERAND (use_stmt, 0));
+ fprintf (dump_file, " on line %d\n", STMT_LINENO (use_stmt));
+ }
+ newexpr = build_modify_expr (temp, NOP_EXPR, use_expr);
+ replace_expr_in_tree (use_stmt, use_expr, newexpr);
+ }
+ else if (EXPRREF_RELOAD (use))
+ {
+ basic_block use_bb = EXPRREF_BB (use);
+ tree use_stmt = EXPRREF_STMT (use);
+ tree use_expr = EXPRREF_EXPR (use);
+ if (dump_file)
+ {
+ fprintf (dump_file, "In BB %d, insert reload of ",
+ use_bb->index);
+ print_c_tree (dump_file, use_expr);
+ fprintf (dump_file, " from ");
+ print_c_tree (dump_file, temp);
+ fprintf (dump_file, " in statement ");
+ print_c_tree (dump_file, TREE_OPERAND (use_stmt, 0));
+ fprintf (dump_file, " on line %d\n", STMT_LINENO (use_stmt));
+ }
+ replace_expr_in_tree (use_stmt, use_expr, temp);
+ }
+ }
+ }
+ }
+
+ /* Compute will_be_avail. */
+ static void
+ will_be_avail (ei)
+ struct expr_info *ei;
+ {
+ compute_can_be_avail (ei);
+ compute_later (ei);
+ }
+
+ /* Add call expression to expr-infos. */
+ static int
+ add_call_to_ei (slot, data)
+ void **slot;
+ void *data;
+ {
+ varref call = (varref) data;
+ struct expr_info *ei = (struct expr_info *) *slot;
+ VARRAY_PUSH_TREE (ei->occurs, VARREF_EXPR (call));
+ VARRAY_PUSH_TREE (ei->occurstmts, VARREF_STMT (call));
+ return 1;
+ }
+
+ /* Traverse over expressions to perform PRE on. */
+ static int
+ pre_part_1_trav (slot, data)
+ void **slot;
+ void *data;
+ {
+ tree temp;
+ tree temp2;
+ struct expr_info *ei = (struct expr_info *) *slot;
+ if (VARRAY_ACTIVE_SIZE (ei->reals) < 2)
+ return 1;
+ expr_phi_insertion ((sbitmap *)data, ei);
+ rename_1 (ei);
+ down_safety (ei);
+ will_be_avail (ei);
+ {
+ varref def = NULL;
+ tree type_of_expr;
+ size_t i;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->realstmts) && !def; i++)
+ def = find_def_for_stmt (VARRAY_TREE (ei->realstmts, 0));
+
+ if (def != NULL)
+ type_of_expr = TREE_TYPE (VARREF_SYM (def));
+ else
+ type_of_expr = TREE_TYPE (VARRAY_TREE (ei->reals, 0));
+
+ temp2 = build_tree_list (NULL_TREE, NULL_TREE);
+ temp = create_tmp_var (type_of_expr, &temp2);
+ declare_tmp_vars (temp, BLOCK_HEAD_TREE (0));
+ finalize_1 (ei, temp);
+ finalize_2 (ei);
+ code_motion (ei, temp);
+ }
+
+ return 1;
+ }
+
+
+ void
+ tree_perform_ssapre ()
+ {
+ tree fn = DECL_SAVED_TREE (current_function_decl);
+ /* First, we need to find our candidate expressions. */
+ htab_t bexprs = htab_create (37, hash_binary_tree,
+ binexpr_lexically_eq, free_expr_info);
+ htab_t seen = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+ int i;
+ /* Debugging dump before SSA PRE */
+ dump_file = dump_begin (TDI_ssa_pre, &dump_flags);
+ if (dump_file)
+ {
+ fprintf (dump_file, "\n%s() (ORIGINAL)\n",
+ IDENTIFIER_POINTER (DECL_NAME (current_function_decl)));
+
+ if (dump_flags & TDF_UNPARSE)
+ print_c_tree (dump_file, fn);
+ else
+ dump_node (fn, TDF_SLIM | dump_flags, dump_file);
+ }
+
+ /* Compute immediate dominators. */
+ pre_idom = (int *) xmalloc ((size_t) n_basic_blocks * sizeof (int));
+ memset ((void *) pre_idom, -1, (size_t) n_basic_blocks * sizeof (int));
+ pre_doms = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ sbitmap_vector_zero (pre_doms, n_basic_blocks);
+ calculate_dominance_info (pre_idom, pre_doms, CDI_DOMINATORS);
+ domchildren = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ sbitmap_vector_zero (domchildren, n_basic_blocks);
+ compute_domchildren (pre_idom, domchildren);
+ /* Compute dominance frontiers. */
+ pre_dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ compute_dominance_frontiers (pre_dfs, pre_idom);
+
+ pre_preorder = xmalloc (n_basic_blocks * sizeof (int));
+ flow_preorder_transversal_compute (pre_preorder);
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ varray_type bbrefs = BB_REFS (BASIC_BLOCK (i));
+ size_t j;
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (bbrefs); j++)
+ {
+ varref ref = VARRAY_GENERIC_PTR (bbrefs, j);
+ if (VARREF_TYPE (ref) != VARUSE)
+ continue;
+ if (htab_find (seen, VARREF_EXPR (ref)) != NULL)
+ continue;
+ if (is_simple_binary_expr (VARREF_EXPR (ref)))
+ {
+ struct expr_info *slot;
+ slot = (struct expr_info *)htab_find (bexprs, VARREF_EXPR (ref));
+ if (slot)
+ {
+ VARRAY_PUSH_TREE (slot->occurs, VARREF_EXPR (ref));
+ VARRAY_PUSH_TREE (slot->occurstmts, VARREF_STMT (ref));
+ VARRAY_PUSH_TREE (slot->reals, VARREF_EXPR (ref));
+ VARRAY_PUSH_TREE (slot->realstmts, VARREF_STMT (ref));
+ }
+ else
+ {
+ void **newslot;
+ slot = xmalloc (sizeof (struct expr_info));
+ slot->expr = VARREF_EXPR (ref);
+ VARRAY_TREE_INIT (slot->occurs, 1, "Kills and occurrence");
+ VARRAY_TREE_INIT (slot->occurstmts, 1,
+ "Kills and occurrence statements");
+
+ VARRAY_TREE_INIT (slot->reals, 1, "Real occurrences");
+ VARRAY_TREE_INIT (slot->realstmts, 1, "Real occurrence statements");
+ VARRAY_GENERIC_PTR_INIT (slot->phis, n_basic_blocks, "EPHIs");
+ VARRAY_GENERIC_PTR_INIT (slot->erefs, 1, "EREFs");
+ VARRAY_PUSH_TREE (slot->occurs, VARREF_EXPR (ref));
+ VARRAY_PUSH_TREE (slot->occurstmts, VARREF_STMT (ref));
+ VARRAY_PUSH_TREE (slot->reals, VARREF_EXPR (ref));
+ VARRAY_PUSH_TREE (slot->realstmts, VARREF_STMT (ref));
+
+ newslot = htab_find_slot (bexprs, VARREF_EXPR (ref), INSERT);
+ *newslot = slot;
+ }
+ }
+ else if (TREE_CODE (VARREF_EXPR (ref)) == CALL_EXPR)
+ {
+ if (!DECL_IS_PURE (VARREF_SYM (ref)))
+ htab_traverse (bexprs, add_call_to_ei, ref);
+ }
+ *(htab_find_slot (seen, VARREF_EXPR (ref), INSERT)) = VARREF_EXPR (ref);
+
+ }
+ }
+ htab_traverse (bexprs, pre_part_1_trav, pre_dfs);
+ /* simplify_stmt (fn, NULL_TREE); */
+ /* Debugging dump after SSA PRE */
+ if (dump_file)
+ {
+ fprintf (dump_file, "\n%s() (OPTIMIZED)\n",
+ IDENTIFIER_POINTER (DECL_NAME (current_function_decl)));
+
+ if (dump_flags & TDF_UNPARSE)
+ print_c_tree (dump_file, fn);
+ else
+ dump_node (fn, TDF_SLIM | dump_flags, dump_file);
+ dump_end (TDI_ssa_pre, dump_file);
+ }
+
+ htab_delete (bexprs);
+ free (pre_idom);
+ free (pre_preorder);
+ sbitmap_vector_free (pre_doms);
+ sbitmap_vector_free (pre_dfs);
+ sbitmap_vector_free (domchildren);
+ }
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.2.11
diff -c -3 -p -w -B -b -r1.1.2.11 tree-ssa.c
*** tree-ssa.c 22 Apr 2002 21:41:59 -0000 1.1.2.11
--- tree-ssa.c 27 Apr 2002 16:07:45 -0000
*************** Boston, MA 02111-1307, USA. */
*** 33,44 ****
#include "diagnostic.h"
#include "tree-optimize.h"
#include "tree-flow.h"
#include "ssa.h"
!
/* This should be eventually be generalized to other languages, but
this would require a shared function-as-trees infrastructure. */
#include "c-common.h"
!
/* Nonzero to warn about variables used before they are initialized. Used
by analyze_rdefs(). */
--- 33,45 ----
#include "diagnostic.h"
#include "tree-optimize.h"
#include "tree-flow.h"
+ #include "tree-inline.h"
#include "ssa.h"
! #include "varray.h"
/* This should be eventually be generalized to other languages, but
this would require a shared function-as-trees infrastructure. */
#include "c-common.h"
! #include "bitmap.h"
/* Nonzero to warn about variables used before they are initialized. Used
by analyze_rdefs(). */
*************** static void delete_refs PARAMS ((varray_
*** 71,79 ****
void
tree_build_ssa ()
{
- sbitmap *dfs;
int *idom;
size_t i;
/* Compute immediate dominators. */
idom = (int *) xmalloc ((size_t) n_basic_blocks * sizeof (int));
--- 71,79 ----
void
tree_build_ssa ()
{
int *idom;
size_t i;
+ sbitmap *dfs;
/* Compute immediate dominators. */
idom = (int *) xmalloc ((size_t) n_basic_blocks * sizeof (int));
*************** tree_build_ssa ()
*** 92,98 ****
with no statement or expression (to distinguish them from actual
definitions). */
for (i = 0; i < NREF_SYMBOLS; i++)
! create_varref (REF_SYMBOL (i), VARDEF, ENTRY_BLOCK_PTR, NULL, NULL);
/* Insert the PHI terms and build FUD chains. */
insert_phi_terms (dfs);
--- 92,98 ----
with no statement or expression (to distinguish them from actual
definitions). */
for (i = 0; i < NREF_SYMBOLS; i++)
! create_ref (REF_SYMBOL (i), VARDEF, ENTRY_BLOCK_PTR, NULL, NULL);
/* Insert the PHI terms and build FUD chains. */
insert_phi_terms (dfs);
*************** insert_phi_terms (dfs)
*** 212,218 ****
if (stmt_bb == NULL)
abort ();
! phi = create_varref (sym, VARPHI, bb, stmt_bb->head_tree,
NULL);
VARRAY_TREE (added, w) = sym;
--- 211,217 ----
if (stmt_bb == NULL)
abort ();
! phi = create_ref (sym, VARPHI, bb, stmt_bb->head_tree,
NULL);
VARRAY_TREE (added, w) = sym;
*************** search_fud_chains (bb, idom)
*** 341,347 ****
--- 340,349 ----
currdef = TREE_CURRDEF (sym);
if (currdef)
+ {
VARRAY_PUSH_GENERIC_PTR (VARDEF_PHI_CHAIN (phi), currdef);
+ VARRAY_PUSH_BB (VARDEF_PHI_CHAIN_BB (phi), bb);
+ }
}
}
*************** delete_refs (refs)
*** 416,424 ****
--- 418,432 ----
VARRAY_FREE (VARDEF_IMM_USES (ref));
VARRAY_FREE (VARDEF_RUSES (ref));
VARRAY_FREE (VARDEF_PHI_CHAIN (ref));
+ VARRAY_FREE (VARDEF_PHI_CHAIN_BB (ref));
}
else if (VARREF_TYPE (ref) == VARUSE)
VARRAY_FREE (VARUSE_RDEFS (ref));
+ else if (VARREF_TYPE (ref) == EXPRPHI)
+ {
+ BITMAP_XFREE (EXPRPHI_PROCESSED (ref));
+ VARRAY_FREE (EXPRPHI_PHI_CHAIN (ref));
+ }
}
VARRAY_FREE (refs);
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.257.2.7
diff -c -3 -p -w -B -b -r1.257.2.7 tree.h
*** tree.h 2 Apr 2002 15:26:43 -0000 1.257.2.7
--- tree.h 27 Apr 2002 16:07:47 -0000
*************** enum tree_dump_index
*** 3059,3064 ****
--- 3059,3065 ----
TDI_cfg, /* dump the flowgraph for each function. */
TDI_dot, /* create a GraphViz graph file for each
function's flowgraph. */
+ TDI_ssa_pre, /* dump SSA pre information for each function. */
TDI_ssa, /* dump SSA information for each function. */
TDI_simple, /* dump each function before and after
simplifying it. */
Index: cp/Make-lang.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/Make-lang.in,v
retrieving revision 1.88.2.10
diff -c -3 -p -w -B -b -r1.88.2.10 Make-lang.in
*** cp/Make-lang.in 2 Apr 2002 15:31:40 -0000 1.88.2.10
--- cp/Make-lang.in 27 Apr 2002 16:07:49 -0000
*************** $(DEMANGLER_PROG): cxxmain.o underscore.
*** 97,103 ****
# Shared with C front end:
CXX_C_OBJS = attribs.o c-common.o c-format.o c-pragma.o c-semantics.o c-lex.o \
$(CXX_TARGET_OBJS) \
! tree-cfg.o tree-dfa.o tree-optimize.o tree-ssa.o c-simplify.o \
c-pretty-print.o tree-simple.o
# Language-specific object files.
--- 97,103 ----
# Shared with C front end:
CXX_C_OBJS = attribs.o c-common.o c-format.o c-pragma.o c-semantics.o c-lex.o \
$(CXX_TARGET_OBJS) \
! tree-cfg.o tree-dfa.o tree-optimize.o tree-ssa.o tree-ssa-pre.o c-simplify.o \
c-pretty-print.o tree-simple.o
# Language-specific object files.