Hello,
The attached patch implements (partially) the first part of proposed
work: exporting and verification of data dependence information.
The implementation follows the outline presented in my initial message
on the project, here: http://gcc.gnu.org/ml/gcc/2007-03/msg00900.html
. Data references and data dependency relations obtained via
compute_dependencies_for_loop are copied into containing struct (which
is a member of struct function). This containing struct is marked
GTY((skip)), because its lifetime and lifetime of its components is
known (from the moment of export until destruction late in the RTL
pipeline). However, I need to preserve trees that are referenced in
the exported datarefs (to be able to bind MEMs to datarefs later), so
I need to put them into a GC-visible array. For now that array is
global. Can it be done better?
MEMs are bound to datarefs by means of saving original trees for MEMs
during expand. This is a large part of the attached patch with
changes to emit-rtl.[ch], which adds new field to struct mem_attrs
(mem_orig_expr), initializes it and propagates through various RTL
transformations. Notice that it has stricter hashing (as compared to
orig_expr part of the same struct), so it will reduce sharing of
mem_attrs (and also increase size of the struct, obviously). Can it
be a problem? Please also note that this patch is a part of aliasing
information exporting patch by Dmitry Melnik, which available now in
alias-export branch.
After original tree is found, a corresponding dataref is looked up in
exported info. I guess I will need here hashtabs for fast lookup
(also for searching ddrs for pairs of datarefs), am I right?
The only place that required patching so far wrt. exporting was
iv-opts pass (we need to rewrite TARGET_MEM_REFs to their respective
TMR_ORIGINALs, because that's what MEM_ORIG_EXPR will provide binding
to later). However, the issue of basic block duplication is not
addressed yet in this patch, I will be looking into it shortly.
The verification routines walk all loops and memory references in
function, and provide counters of references with/without relevant
exported dataref, and also count number of exported ddrs. They are
run after every pass, both GIMPLE and RTL. On GIMLPE, verifier looks
into REFERENCE_CLASS_P trees being LHSs and RHSs of MODIFY_STMTs (as
compute_dependencies_for_loop does), on RTL simply all MEMs are
visited. However, I just noticed that 'optimized' dump may contain
D.2108 = (short unsigned int) shortsum + (short unsigned int)
MEM[symbol: data_ch, index: (unsigned int) i];
which is not verifier expects.
The verifier also frequently breaks on passes that create unreachable
basic blocks (because dominator analysis called from flow_loops_find
asserts there are none). For now I just place
delete_unreachable_blocks in such passes, is that ok?
I'm proceeding with testing on small examples (tree-vectorizer
testsuite provides plenty :) ).
Thanks in advance for comments
--
Alexander Monakov
diff -puN trunk/gcc/cfgexpand.c export-ddg/gcc/cfgexpand.c
--- trunk/gcc/cfgexpand.c 2007-06-22 20:19:52.000000000 +0400
+++ export-ddg/gcc/cfgexpand.c 2007-06-29 17:34:20.000000000 +0400
@@ -1988,6 +1988,7 @@ tree_expand_cfg (void)
/* Tag the blocks with a depth number so that change_scope can find
the common parent easily. */
set_block_levels (DECL_INITIAL (cfun->decl), 0);
+ delete_unreachable_blocks ();
return 0;
}
@@ -2004,7 +2005,7 @@ struct tree_opt_pass pass_expand =
PROP_gimple_leh | PROP_cfg, /* properties_required */
PROP_rtl, /* properties_provided */
PROP_trees, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_dump_func, /* todo_flags_finish */
+ TODO_no_verify_trees, /* todo_flags_start */
+ TODO_dump_func|TODO_no_verify_trees, /* todo_flags_finish */
'r' /* letter */
};
diff -puN trunk/gcc/common.opt export-ddg/gcc/common.opt
--- trunk/gcc/common.opt 2007-06-29 19:31:47.000000000 +0400
+++ export-ddg/gcc/common.opt 2007-07-02 17:54:00.000000000 +0400
@@ -462,6 +462,10 @@ fexpensive-optimizations
Common Report Var(flag_expensive_optimizations) Optimization
Perform a number of minor, expensive optimizations
+fexport-ddg
+Common Report Var(flag_export_ddg) Init(1)
+Gather and export data relation information
+
ffast-math
Common
diff -puN trunk/gcc/emit-rtl.c export-ddg/gcc/emit-rtl.c
--- trunk/gcc/emit-rtl.c 2007-07-02 14:55:16.000000000 +0400
+++ export-ddg/gcc/emit-rtl.c 2007-07-02 17:53:53.000000000 +0400
@@ -177,8 +177,8 @@ static int const_double_htab_eq (const v
static rtx lookup_const_double (rtx);
static hashval_t mem_attrs_htab_hash (const void *);
static int mem_attrs_htab_eq (const void *, const void *);
-static mem_attrs *get_mem_attrs (HOST_WIDE_INT, tree, rtx, rtx, unsigned int,
- enum machine_mode);
+static mem_attrs *get_mem_attrs (HOST_WIDE_INT, tree, tree, rtx, rtx,
+ unsigned int, enum machine_mode);
static hashval_t reg_attrs_htab_hash (const void *);
static int reg_attrs_htab_eq (const void *, const void *);
static reg_attrs *get_reg_attrs (tree, int);
@@ -253,7 +253,8 @@ mem_attrs_htab_hash (const void *x)
return (p->alias ^ (p->align * 1000)
^ ((p->offset ? INTVAL (p->offset) : 0) * 50000)
^ ((p->size ? INTVAL (p->size) : 0) * 2500000)
- ^ (size_t) iterative_hash_expr (p->expr, 0));
+ ^ (size_t) iterative_hash_expr (p->expr,
+ iterative_hash_expr (p->orig_expr, 0)));
}
/* Returns nonzero if the value represented by X (which is really a
@@ -270,7 +271,12 @@ mem_attrs_htab_eq (const void *x, const
&& p->size == q->size && p->align == q->align
&& (p->expr == q->expr
|| (p->expr != NULL_TREE && q->expr != NULL_TREE
- && operand_equal_p (p->expr, q->expr, 0))));
+ && operand_equal_p (p->expr, q->expr, 0)))
+ /* We do not use operand_equal_p for ORIG_EXPRs because we need to
+ distinguish memory references at different points of the loop (which
+ would have different indices in SSA form, like a[i_1] and a[i_2], but
+ were later rewritten to same a[i]). */
+ && (p->orig_expr == q->orig_expr));
}
/* Allocate a new mem_attrs structure and insert it into the hash table if
@@ -278,8 +284,8 @@ mem_attrs_htab_eq (const void *x, const
MEM of mode MODE. */
static mem_attrs *
-get_mem_attrs (HOST_WIDE_INT alias, tree expr, rtx offset, rtx size,
- unsigned int align, enum machine_mode mode)
+get_mem_attrs (HOST_WIDE_INT alias, tree expr, tree orig_expr, rtx offset,
+ rtx size, unsigned int align, enum machine_mode mode)
{
mem_attrs attrs;
void **slot;
@@ -287,7 +293,7 @@ get_mem_attrs (HOST_WIDE_INT alias, tree
/* If everything is the default, we can just return zero.
This must match what the corresponding MEM_* macros return when the
field is not present. */
- if (alias == 0 && expr == 0 && offset == 0
+ if (alias == 0 && expr == 0 && orig_expr == 0 && offset == 0
&& (size == 0
|| (mode != BLKmode && GET_MODE_SIZE (mode) == INTVAL (size)))
&& (STRICT_ALIGNMENT && mode != BLKmode
@@ -296,6 +302,7 @@ get_mem_attrs (HOST_WIDE_INT alias, tree
attrs.alias = alias;
attrs.expr = expr;
+ attrs.orig_expr = orig_expr;
attrs.offset = offset;
attrs.size = size;
attrs.align = align;
@@ -1392,6 +1399,54 @@ operand_subword_force (rtx op, unsigned
return result;
}
+
+/* If EXPR contains conversions at the root of the tree, all of them
+ will be removed. */
+
+static tree
+skip_conversions (tree expr)
+{
+ tree inner = expr;
+ /* Remove any conversions: they don't change what the underlying
+ object is. Likewise for SAVE_EXPR. */
+ while (TREE_CODE (inner) == NOP_EXPR || TREE_CODE (inner) == CONVERT_EXPR
+ || TREE_CODE (inner) == NON_LVALUE_EXPR
+ || TREE_CODE (inner) == VIEW_CONVERT_EXPR
+ || TREE_CODE (inner) == SAVE_EXPR)
+ inner = TREE_OPERAND (inner, 0);
+ return inner;
+}
+
+/* Remove conversions from the expression tree. */
+
+static tree
+cleanup_tree_from_conversions (tree ref)
+{
+ tree inner;
+ tree res = NULL;
+
+ if (EXPR_P (ref))
+ inner = TREE_OPERAND (ref, 0);
+ else
+ inner = NULL;
+
+ if (inner == NULL)
+ return ref;
+
+ inner = skip_conversions (inner);
+
+ res = cleanup_tree_from_conversions (inner);
+
+ if (res != TREE_OPERAND (ref, 0))
+ {
+ tree new_tree = copy_node (ref);
+ TREE_OPERAND (new_tree, 0) = res;
+ return new_tree;
+ }
+ else
+ return ref;
+}
+
/* Within a MEM_EXPR, we care about either (1) a component ref of a decl,
or (2) a component ref of something variable. Represent the later with
a NULL expression. */
@@ -1401,27 +1456,36 @@ component_ref_for_mem_expr (tree ref)
{
tree inner = TREE_OPERAND (ref, 0);
- if (TREE_CODE (inner) == COMPONENT_REF)
+ /* Remove any conversions: they don't change what the underlying
+ object is. Likewise for SAVE_EXPR. */
+ while (TREE_CODE (inner) == NOP_EXPR || TREE_CODE (inner) == CONVERT_EXPR
+ || TREE_CODE (inner) == NON_LVALUE_EXPR
+ || TREE_CODE (inner) == VIEW_CONVERT_EXPR
+ || TREE_CODE (inner) == SAVE_EXPR)
+ inner = TREE_OPERAND (inner, 0);
+
+ if (TREE_CODE (inner) == COMPONENT_REF || TREE_CODE (inner) == INDIRECT_REF)
inner = component_ref_for_mem_expr (inner);
else
{
- /* Now remove any conversions: they don't change what the underlying
- object is. Likewise for SAVE_EXPR. */
- while (TREE_CODE (inner) == NOP_EXPR || TREE_CODE (inner) == CONVERT_EXPR
- || TREE_CODE (inner) == NON_LVALUE_EXPR
- || TREE_CODE (inner) == VIEW_CONVERT_EXPR
- || TREE_CODE (inner) == SAVE_EXPR)
- inner = TREE_OPERAND (inner, 0);
-
if (! DECL_P (inner))
inner = NULL_TREE;
}
if (inner == TREE_OPERAND (ref, 0))
return ref;
- else
- return build3 (COMPONENT_REF, TREE_TYPE (ref), inner,
- TREE_OPERAND (ref, 1), NULL_TREE);
+ else if (TREE_CODE (ref) == COMPONENT_REF)
+ {
+ return build3 (COMPONENT_REF, TREE_TYPE (ref), inner,
+ TREE_OPERAND (ref, 1), NULL_TREE);
+ }
+ else /* INDIRECT_REF. */
+ {
+ if (inner == NULL_TREE)
+ return NULL_TREE;
+ else
+ return build1 (INDIRECT_REF, TREE_TYPE (ref), inner);
+ }
}
/* Returns 1 if both MEM_EXPR can be considered equal
@@ -1469,6 +1533,7 @@ set_mem_attributes_minus_bitpos (rtx ref
{
HOST_WIDE_INT alias = MEM_ALIAS_SET (ref);
tree expr = MEM_EXPR (ref);
+ tree orig_expr = NULL;
rtx offset = MEM_OFFSET (ref);
rtx size = MEM_SIZE (ref);
unsigned int align = MEM_ALIGN (ref);
@@ -1533,6 +1598,8 @@ set_mem_attributes_minus_bitpos (rtx ref
{
tree base;
+ orig_expr = cleanup_tree_from_conversions (t);
+
if (TREE_THIS_VOLATILE (t))
MEM_VOLATILE_P (ref) = 1;
@@ -1708,11 +1775,13 @@ set_mem_attributes_minus_bitpos (rtx ref
we're overlapping. */
offset = NULL;
expr = NULL;
+ orig_expr = NULL;
}
/* Now set the attributes we computed above. */
MEM_ATTRS (ref)
- = get_mem_attrs (alias, expr, offset, size, align, GET_MODE (ref));
+ = get_mem_attrs (alias, expr, orig_expr, offset, size, align,
+ GET_MODE (ref));
/* If this is already known to be a scalar or aggregate, we are done. */
if (MEM_IN_STRUCT_P (ref) || MEM_SCALAR_P (ref))
@@ -1738,7 +1807,7 @@ void
set_mem_attrs_from_reg (rtx mem, rtx reg)
{
MEM_ATTRS (mem)
- = get_mem_attrs (MEM_ALIAS_SET (mem), REG_EXPR (reg),
+ = get_mem_attrs (MEM_ALIAS_SET (mem), REG_EXPR (reg), NULL_TREE,
GEN_INT (REG_OFFSET (reg)),
MEM_SIZE (mem), MEM_ALIGN (mem), GET_MODE (mem));
}
@@ -1753,9 +1822,9 @@ set_mem_alias_set (rtx mem, HOST_WIDE_IN
gcc_assert (alias_sets_conflict_p (set, MEM_ALIAS_SET (mem)));
#endif
- MEM_ATTRS (mem) = get_mem_attrs (set, MEM_EXPR (mem), MEM_OFFSET (mem),
- MEM_SIZE (mem), MEM_ALIGN (mem),
- GET_MODE (mem));
+ MEM_ATTRS (mem) = get_mem_attrs (set, MEM_EXPR (mem), MEM_ORIG_EXPR (mem),
+ MEM_OFFSET (mem), MEM_SIZE (mem),
+ MEM_ALIGN (mem), GET_MODE (mem));
}
/* Set the alignment of MEM to ALIGN bits. */
@@ -1764,8 +1833,8 @@ void
set_mem_align (rtx mem, unsigned int align)
{
MEM_ATTRS (mem) = get_mem_attrs (MEM_ALIAS_SET (mem), MEM_EXPR (mem),
- MEM_OFFSET (mem), MEM_SIZE (mem), align,
- GET_MODE (mem));
+ MEM_ORIG_EXPR (mem), MEM_OFFSET (mem),
+ MEM_SIZE (mem), align, GET_MODE (mem));
}
/* Set the expr for MEM to EXPR. */
@@ -1773,9 +1842,29 @@ set_mem_align (rtx mem, unsigned int ali
void
set_mem_expr (rtx mem, tree expr)
{
+ tree orig_expr = MEM_ORIG_EXPR (mem);
+
+ /* If MEM_EXPR changes, clear MEM_ORIG_EXPR. If we still can preserve it,
+ we insert set_mem_orig_expr call right after this function call. */
+ if (!expr || !mem_expr_equal_p (MEM_EXPR (mem), expr))
+ orig_expr = NULL_TREE;
+
MEM_ATTRS (mem)
- = get_mem_attrs (MEM_ALIAS_SET (mem), expr, MEM_OFFSET (mem),
- MEM_SIZE (mem), MEM_ALIGN (mem), GET_MODE (mem));
+ = get_mem_attrs (MEM_ALIAS_SET (mem), expr, orig_expr,
+ MEM_OFFSET (mem), MEM_SIZE (mem), MEM_ALIGN (mem),
+ GET_MODE (mem));
+}
+
+
+/* Set the original expr for MEM to ORIG_EXPR. */
+
+void
+set_mem_orig_expr (rtx mem, tree orig_expr)
+{
+ MEM_ATTRS (mem)
+ = get_mem_attrs (MEM_ALIAS_SET (mem), MEM_EXPR (mem), orig_expr,
+ MEM_OFFSET (mem), MEM_SIZE (mem), MEM_ALIGN (mem),
+ GET_MODE (mem));
}
/* Set the offset of MEM to OFFSET. */
@@ -1783,9 +1872,16 @@ set_mem_expr (rtx mem, tree expr)
void
set_mem_offset (rtx mem, rtx offset)
{
+ tree orig_expr = MEM_ORIG_EXPR (mem);
+
+ /* If MEM_EXPR changes, clear MEM_ORIG_EXPR. If we still can preserve it,
+ we insert set_mem_orig_expr call right after this function call. */
+ if (offset != MEM_OFFSET (mem))
+ orig_expr = NULL_TREE;
+
MEM_ATTRS (mem) = get_mem_attrs (MEM_ALIAS_SET (mem), MEM_EXPR (mem),
- offset, MEM_SIZE (mem), MEM_ALIGN (mem),
- GET_MODE (mem));
+ orig_expr, offset, MEM_SIZE (mem),
+ MEM_ALIGN (mem), GET_MODE (mem));
}
/* Set the size of MEM to SIZE. */
@@ -1794,8 +1890,8 @@ void
set_mem_size (rtx mem, rtx size)
{
MEM_ATTRS (mem) = get_mem_attrs (MEM_ALIAS_SET (mem), MEM_EXPR (mem),
- MEM_OFFSET (mem), size, MEM_ALIGN (mem),
- GET_MODE (mem));
+ MEM_ORIG_EXPR (mem), MEM_OFFSET (mem),
+ size, MEM_ALIGN (mem), GET_MODE (mem));
}
/* Return a memory reference like MEMREF, but with its mode changed to MODE
@@ -1862,7 +1958,8 @@ change_address (rtx memref, enum machine
}
MEM_ATTRS (new)
- = get_mem_attrs (MEM_ALIAS_SET (memref), 0, 0, size, align, mmode);
+ = get_mem_attrs (MEM_ALIAS_SET (memref), NULL_TREE, NULL_TREE, 0,
+ size, align, mmode);
return new;
}
@@ -1929,7 +2026,8 @@ adjust_address_1 (rtx memref, enum machi
size = plus_constant (MEM_SIZE (memref), -offset);
MEM_ATTRS (new) = get_mem_attrs (MEM_ALIAS_SET (memref), MEM_EXPR (memref),
- memoffset, size, memalign, GET_MODE (new));
+ MEM_ORIG_EXPR (memref), memoffset, size,
+ memalign, GET_MODE (new));
/* At some point, we should validate that this offset is within the object,
if all the appropriate values are known. */
@@ -1985,7 +2083,8 @@ offset_address (rtx memref, rtx offset,
/* Update the alignment to reflect the offset. Reset the offset, which
we don't know. */
MEM_ATTRS (new)
- = get_mem_attrs (MEM_ALIAS_SET (memref), MEM_EXPR (memref), 0, 0,
+ = get_mem_attrs (MEM_ALIAS_SET (memref), MEM_EXPR (memref),
+ MEM_ORIG_EXPR (memref), 0, 0,
MIN (MEM_ALIGN (memref), pow2 * BITS_PER_UNIT),
GET_MODE (new));
return new;
@@ -2025,6 +2124,7 @@ widen_memory_access (rtx memref, enum ma
tree expr = MEM_EXPR (new);
rtx memoffset = MEM_OFFSET (new);
unsigned int size = GET_MODE_SIZE (mode);
+ tree orig_expr = MEM_ORIG_EXPR (new);
/* If there are no changes, just return the original memory reference. */
if (new == memref)
@@ -2090,8 +2190,11 @@ widen_memory_access (rtx memref, enum ma
/* The widened memory may alias other stuff, so zap the alias set. */
/* ??? Maybe use get_alias_set on any remaining expression. */
- MEM_ATTRS (new) = get_mem_attrs (0, expr, memoffset, GEN_INT (size),
- MEM_ALIGN (new), mode);
+ if (expr != MEM_EXPR (new))
+ orig_expr = NULL_TREE;
+
+ MEM_ATTRS (new) = get_mem_attrs (0, expr, orig_expr, memoffset,
+ GEN_INT (size), MEM_ALIGN (new), mode);
return new;
}
diff -puN trunk/gcc/emit-rtl.h export-ddg/gcc/emit-rtl.h
--- trunk/gcc/emit-rtl.h 2007-06-22 20:19:52.000000000 +0400
+++ export-ddg/gcc/emit-rtl.h 2007-06-20 20:46:42.000000000 +0400
@@ -30,6 +30,9 @@ extern void set_mem_align (rtx, unsigned
/* Set the expr for MEM to EXPR. */
extern void set_mem_expr (rtx, tree);
+/* Set the original expr for MEM to ORIG_EXPR. */
+extern void set_mem_orig_expr (rtx, tree);
+
/* Set the offset for MEM to OFFSET. */
extern void set_mem_offset (rtx, rtx);
diff -puN trunk/gcc/function.c export-ddg/gcc/function.c
--- trunk/gcc/function.c 2007-06-22 20:19:47.000000000 +0400
+++ export-ddg/gcc/function.c 2007-07-02 21:24:56.000000000 +0400
@@ -2968,7 +2968,10 @@ assign_parms_unsplit_complex (struct ass
/* Set MEM_EXPR to the original decl, i.e. to PARM,
instead of the copy of decl, i.e. FNARGS. */
if (DECL_INCOMING_RTL (parm) && MEM_P (DECL_INCOMING_RTL (parm)))
- set_mem_expr (DECL_INCOMING_RTL (parm), parm);
+ {
+ set_mem_expr (DECL_INCOMING_RTL (parm), parm);
+ set_mem_orig_expr (DECL_INCOMING_RTL (parm), parm);
+ }
}
fnargs = TREE_CHAIN (fnargs);
@@ -5483,6 +5486,7 @@ rest_of_handle_thread_prologue_and_epilo
scheduling to operate in the epilogue. */
thread_prologue_and_epilogue_insns ();
+ delete_unreachable_blocks ();
return 0;
}
diff -puN trunk/gcc/function.h export-ddg/gcc/function.h
--- trunk/gcc/function.h 2007-06-22 20:19:48.000000000 +0400
+++ export-ddg/gcc/function.h 2007-07-02 17:53:49.000000000 +0400
@@ -297,6 +297,10 @@ struct function GTY(())
during the nested function. */
struct var_refs_queue *fixup_var_refs_queue;
+ /* Data references and data dependence relations exported from Tree-SSA
+ level for use on RTL level. */
+ struct ddg_info_def * GTY((skip)) x_ddg_info;
+
/* Current nesting level for temporaries. */
int x_temp_slot_level;
diff -puN trunk/gcc/Makefile.in export-ddg/gcc/Makefile.in
--- trunk/gcc/Makefile.in 2007-07-02 14:55:16.000000000 +0400
+++ export-ddg/gcc/Makefile.in 2007-07-02 17:54:02.000000000 +0400
@@ -783,6 +783,7 @@ C_PRETTY_PRINT_H = c-pretty-print.h $(PR
SCEV_H = tree-scalar-evolution.h $(GGC_H) tree-chrec.h $(PARAMS_H)
LAMBDA_H = lambda.h $(TREE_H) vec.h $(GGC_H)
TREE_DATA_REF_H = tree-data-ref.h $(LAMBDA_H) omega.h
+TREE_DATA_REF_EXPORT_H = tree-data-ref-export.h $(TREE_DATA_REF_H)
VARRAY_H = varray.h $(MACHMODE_H) $(SYSTEM_H) coretypes.h $(TM_H)
TREE_INLINE_H = tree-inline.h $(VARRAY_H) pointer-set.h
REAL_H = real.h $(MACHMODE_H)
@@ -1090,6 +1091,7 @@ OBJS-common = \
tree-chrec.o \
tree-complex.o \
tree-data-ref.o \
+ tree-data-ref-export.o \
tree-dfa.o \
tree-dump.o \
tree-eh.o \
@@ -2191,6 +2193,11 @@ tree-data-ref.o: tree-data-ref.c $(CONFI
$(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
$(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h langhooks.h
+tree-data-ref-export.o: tree-data-ref-export.c $(CONFIG_H) $(SYSTEM_H) \
+ coretypes.h $(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) \
+ $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
+ $(TREE_DATA_REF_EXPORT_H) $(SCEV_H) tree-pass.h tree-chrec.h langhooks.h \
+ gt-tree-data-ref-export.h
tree-vect-analyze.o: tree-vect-analyze.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(TM_H) $(GGC_H) $(OPTABS_H) $(TREE_H) $(BASIC_BLOCK_H) \
$(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
@@ -3032,6 +3039,7 @@ GTFILES = $(srcdir)/input.h $(srcdir)/co
$(srcdir)/tree-ssa-structalias.c \
$(srcdir)/omp-low.c $(srcdir)/varpool.c \
$(srcdir)/targhooks.c $(out_file) $(srcdir)/passes.c $(srcdir)/cgraphunit.c \
+ $(srcdir)/tree-data-ref-export.c \
@all_gtfiles@
GTFILES_H = $(subst /,-, $(subst $(srcdir)/,gt-, $(subst .c,.h, \
diff -puN trunk/gcc/passes.c export-ddg/gcc/passes.c
--- trunk/gcc/passes.c 2007-06-22 20:20:02.000000000 +0400
+++ export-ddg/gcc/passes.c 2007-07-02 17:54:03.000000000 +0400
@@ -85,6 +85,7 @@ Software Foundation, 51 Franklin Street,
#include "tree-dump.h"
#include "df.h"
#include "predict.h"
+#include "tree-data-ref-export.h"
#if defined (DWARF2_UNWIND_INFO) || defined (DWARF2_DEBUGGING_INFO)
#include "dwarf2out.h"
@@ -643,6 +644,7 @@ init_optimization_passes (void)
pass_may_alias. */
NEXT_PASS (pass_complete_unroll);
NEXT_PASS (pass_loop_prefetch);
+ NEXT_PASS (pass_gather_ddg_info);
NEXT_PASS (pass_iv_optimize);
NEXT_PASS (pass_tree_loop_done);
}
@@ -775,6 +777,7 @@ init_optimization_passes (void)
}
NEXT_PASS (pass_compute_alignments);
NEXT_PASS (pass_duplicate_computed_gotos);
+ NEXT_PASS (pass_free_ddg_info);
NEXT_PASS (pass_variable_tracking);
NEXT_PASS (pass_free_cfg);
NEXT_PASS (pass_machine_reorg);
@@ -976,6 +979,8 @@ execute_function_todo (void *data)
verify_stmts ();
if (flags & TODO_verify_loops)
verify_loop_closed_ssa ();
+ if (flag_export_ddg && !(flags & TODO_no_verify_trees))
+ verify_trees ();
#endif
cfun->last_verified = flags & TODO_verify_all;
diff -puN trunk/gcc/rtl.h export-ddg/gcc/rtl.h
--- trunk/gcc/rtl.h 2007-06-22 20:20:01.000000000 +0400
+++ export-ddg/gcc/rtl.h 2007-07-02 17:54:01.000000000 +0400
@@ -145,6 +145,7 @@ typedef struct mem_attrs GTY(())
rtx offset; /* Offset from start of DECL, as CONST_INT. */
rtx size; /* Size in bytes, as a CONST_INT. */
unsigned int align; /* Alignment of MEM in bits. */
+ tree orig_expr; /* Explicit original tree expression. */
} mem_attrs;
/* Structure used to describe the attributes of a REG in similar way as
@@ -1171,6 +1172,11 @@ do { \
: (STRICT_ALIGNMENT && GET_MODE (RTX) != BLKmode \
? GET_MODE_ALIGNMENT (GET_MODE (RTX)) : BITS_PER_UNIT))
+/* For a MEM rtx, the decl it is known to refer to, if it is known to
+ refer to part of a DECL. It may also be a COMPONENT_REF. */
+#define MEM_ORIG_EXPR(RTX) \
+(MEM_ATTRS (RTX) == 0 ? 0 : MEM_ATTRS (RTX)->orig_expr)
+
/* For a REG rtx, the decl it is known to refer to, if it is known to
refer to part of a DECL. */
#define REG_EXPR(RTX) (REG_ATTRS (RTX) == 0 ? 0 : REG_ATTRS (RTX)->decl)
--- trunk/gcc/tree-data-ref-export.c 1970-01-01 03:00:00.000000000 +0300
+++ export-ddg/gcc/tree-data-ref-export.c 2007-07-02 21:10:13.000000000
+0400
@@ -0,0 +1,485 @@
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "ggc.h"
+#include "tree.h"
+
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "timevar.h"
+#include "cfgloop.h"
+#include "tree-chrec.h"
+#include "tree-data-ref.h"
+#include "tree-scalar-evolution.h"
+#include "tree-pass.h"
+#include "langhooks.h"
+
+#include "tree-data-ref-export.h"
+
+/* Holds exported data references and relations. */
+struct ddg_info_def
+{
+ /* Lists of data references and data relation between them for all loops in
+ the function. */
+ VEC(data_reference_p,heap) **datarefs;
+ VEC(ddr_p,heap) **ddrs;
+
+ /* Number of loops in the function at the time of export. */
+ unsigned int loopnum;
+};
+
+#define ddg_info (cfun->x_ddg_info)
+
+/* We hold here all trees for which data references were computed so that
+ they not eventually get GCed. */
+static GTY(()) VEC(tree, gc) *ddg_info_root_for_trees;
+
+#define print(...) \
+do \
+ if (dump_file) \
+ fprintf (dump_file, __VA_ARGS__); \
+while (0)
+
+static void
+print_generic_expr_1 (FILE *dump_file, tree t, int flags)
+{
+ if (dump_file)
+ print_generic_expr (dump_file, t, flags);
+}
+
+static void
+print_inline_rtx_1 (FILE *dump_file, rtx x, int ind)
+{
+ if (dump_file)
+ print_inline_rtx (dump_file, x, ind);
+}
+
+/* For each loop in function, save datarefs and ddrs obtained via
+ compute_dependencies_for_loop into ddg_info. */
+static void
+gather_ddg_info (void)
+{
+ bool inside_tree_loop_opt_p = !!current_loops;
+ bool dom_info_was_avail_p = dom_info_available_p (CDI_DOMINATORS);
+ unsigned int n_loops;
+ struct loop *loop;
+ loop_iterator li;
+
+ gcc_assert (!ddg_info);
+ ddg_info = XCNEW (struct ddg_info_def);
+
+ if(!inside_tree_loop_opt_p)
+ loop_optimizer_init(AVOID_CFG_MODIFICATIONS);
+
+ /* This can be less than actual number of loops, because number_of_loops ()
+ includes deleted loops. */
+ n_loops = number_of_loops () - 1;
+
+ if (n_loops > 0)
+ {
+ if (!inside_tree_loop_opt_p)
+ scev_initialize ();
+
+ ddg_info->datarefs = XNEWVEC (VEC (data_reference_p, heap) *, n_loops);
+ ddg_info->ddrs = XNEWVEC (VEC (ddr_p, heap) *, n_loops);
+
+ print ("gather_ddg_info: <=%d loops:\n", n_loops);
+
+ FOR_EACH_LOOP (li, loop, 0)
+ {
+ unsigned int i;
+ ddr_p ddr;
+ int cur_loop = ddg_info->loopnum++;
+ int n_dep_known = 0;
+ int n_dep_no = 0;
+ int n_dep_unknown = 0;
+
+ ddg_info->datarefs[cur_loop] = NULL;
+ ddg_info->ddrs[cur_loop] = NULL;
+
+ compute_data_dependences_for_loop (loop, true,
+ &(ddg_info->datarefs[cur_loop]),
+ &(ddg_info->ddrs[cur_loop]));
+
+ for (i = 0; VEC_iterate (ddr_p, ddg_info->ddrs[cur_loop], i, ddr);
+ i++)
+ {
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ n_dep_known++;
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ n_dep_no++;
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ n_dep_unknown++;
+ }
+
+ print ("%2d: %d datarefs, %d ddrs (%d known, %d no, %d unknown)\n",
+ cur_loop,
+ VEC_length (data_reference_p, ddg_info->datarefs[cur_loop]),
+ VEC_length (ddr_p, ddg_info->ddrs[cur_loop]),
+ n_dep_known, n_dep_no, n_dep_unknown);
+ }
+
+ if (!inside_tree_loop_opt_p)
+ scev_finalize ();
+ }
+
+ if (!inside_tree_loop_opt_p)
+ loop_optimizer_finalize ();
+
+ if (!dom_info_was_avail_p)
+ free_dominance_info (CDI_DOMINATORS);
+}
+
+static void
+add_new_tree_to_ggc_root (tree t)
+{
+ VEC_safe_push (tree, gc, ddg_info_root_for_trees, t);
+}
+
+/* Save into ddg_info_root_for_trees all trees for which datarefs were saved.
*/
+static void
+gather_trees_to_ggc_root (void)
+{
+ unsigned int l;
+ ddg_info_root_for_trees = NULL;
+
+ print ("gather_trees_to_ggc_root:\n");
+
+ for (l = 0; l < ddg_info->loopnum; l++)
+ {
+ unsigned int i;
+ struct data_reference *drf;
+
+ for (i = 0; VEC_iterate (data_reference_p, ddg_info->datarefs[l], i,
drf); i++)
+ {
+ add_new_tree_to_ggc_root (drf->ref);
+ print (" (%p) ", (void *) (drf->ref));
+ print_generic_expr_1 (dump_file, drf->ref, TDF_VOPS|TDF_MEMSYMS);
+ print ("\n");
+ }
+ print ("loop %2d: %2d trees\n", l, i);
+ }
+}
+
+static unsigned int
+main_export_ddg (void)
+{
+ gather_ddg_info ();
+ gather_trees_to_ggc_root ();
+ return 0;
+}
+
+static bool
+gate_export_ddg(void)
+{
+ return flag_export_ddg != 0;
+}
+
+struct tree_opt_pass pass_gather_ddg_info =
+{
+ "export-ddg", /* name */
+ gate_export_ddg, /* gate */
+ main_export_ddg, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+static unsigned int
+free_ddg_info (void)
+{
+ unsigned int l;
+
+ if (!ddg_info)
+ return 0;
+
+ for (l = 0; l < ddg_info->loopnum; l++)
+ {
+ free_dependence_relations (ddg_info->ddrs[l]);
+ free_data_refs (ddg_info->datarefs[l]);
+ }
+ free (ddg_info->ddrs);
+ free (ddg_info->datarefs);
+ free (ddg_info);
+ ddg_info = NULL;
+ VEC_free (tree, gc, ddg_info_root_for_trees);
+ return 0;
+}
+
+struct tree_opt_pass pass_free_ddg_info =
+{
+ NULL, /* name */
+ NULL, /* gate */
+ free_ddg_info, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+/* Replace all occurences of FROM tree to TO in ddg_info_root_for_trees. */
+static void
+replace_tree_in_ggc_root (tree from, tree to)
+{
+ int i;
+ tree t;
+ bool found = false;
+
+ for (i = 0; VEC_iterate (tree, ddg_info_root_for_trees, i, t); i++)
+ if (t == from)
+ {
+ found = true;
+ VEC_replace (tree, ddg_info_root_for_trees, i, to);
+ }
+
+ gcc_assert (found);
+}
+
+/* Replace FROM tree to TO in ref fields of saved datarefs. */
+void
+replace_var_in_datarefs (tree from, tree to)
+{
+ struct data_reference *drf;
+ unsigned int i, j;
+ bool found = false;
+
+ for (i = 0; i < ddg_info->loopnum; i++)
+ for (j = 0; VEC_iterate (data_reference_p, ddg_info->datarefs[i], j, drf);
+ j++)
+ if (drf->ref == from)
+ {
+ found = true;
+ drf->ref = to;
+ }
+
+ /* We cannot gcc_assert (found) here, because IVOPTS might want to change a
+ memory reference for which no dataref was produced. However, it would be
+ nice to enable this assert and see in what cases it happens. */
+
+ /* gcc_assert (found); */
+
+ if (found)
+ replace_tree_in_ggc_root (from, to);
+}
+
+
+/* Number of loop currently being verified. */
+static int cur_loop;
+
+/* Search for the dataref for T and return it if found, otherwise return
+ NULL. */
+static data_reference_p
+find_dataref (tree t)
+{
+ unsigned int i;
+ data_reference_p drf, ret = NULL;
+
+ for (i = 0;
+ VEC_iterate (data_reference_p, ddg_info->datarefs[cur_loop], i, drf);
+ i++)
+ if (drf->ref == t)
+ {
+ gcc_assert (!ret);
+ ret = drf;
+ }
+
+ return ret;
+}
+
+static ddr_p
+find_ddr (data_reference_p dr1, data_reference_p dr2)
+{
+ unsigned int i;
+ ddr_p ddr, ret = NULL;
+
+ for (i = 0; VEC_iterate (ddr_p, ddg_info->ddrs[cur_loop], i, ddr); i++)
+ if ((ddr->a == dr1 && ddr->b == dr2)
+ || (ddr->a == dr2 && ddr->b == dr1))
+ {
+ gcc_assert (!ret);
+ ret = ddr;
+ }
+
+ return ret;
+}
+
+static VEC (data_reference_p, heap) *verifier_seen_datarefs = NULL;
+
+static int ddrs_known, ddrs_no, ddrs_unknown, ddrs_not_found;
+
+static void
+verify_ddrs (data_reference_p dataref)
+{
+ unsigned int i;
+ data_reference_p dr;
+ ddr_p ddr;
+
+ VEC_safe_push (data_reference_p, heap, verifier_seen_datarefs, dataref);
+
+ for (i = 0; VEC_iterate (data_reference_p, verifier_seen_datarefs, i, dr);
+ i++)
+ if ((ddr = find_ddr (dataref, dr)))
+ {
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ ddrs_known++;
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ ddrs_no++;
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ ddrs_unknown++;
+ }
+ else
+ ddrs_not_found++;
+}
+
+/* Number of memory references without/with relevant exported info. */
+static int refs_bad, refs_ok;
+
+/* Print trees for which we expect to find saved dataref. */
+static void
+verify_trees_gimple (tree t)
+{
+ data_reference_p dataref;
+
+ if (TREE_CODE (t) == TARGET_MEM_REF)
+ t = TREE_OPERAND (t, 5);
+ if (REFERENCE_CLASS_P (t))
+ {
+ if ((dataref = find_dataref (t)))
+ {
+ print (" DATAREF: (%p) ", (void *)t);
+ print_generic_expr_1 (dump_file, t, TDF_VOPS|TDF_MEMSYMS);
+ print ("\n");
+ refs_ok++;
+ verify_ddrs (dataref);
+ }
+ else
+ {
+ print ("!DATAREF: (%p) ", (void *)t);
+ print_generic_expr_1 (dump_file, t, TDF_VOPS|TDF_MEMSYMS);
+ print (" %d\n", TREE_CODE (t));
+ refs_bad++;
+ }
+ }
+}
+
+
+/* Print MEMs for which we expect to have MEM_ORIG_EXPR. */
+static int
+verify_trees_rtl (rtx *px, void *data ATTRIBUTE_UNUSED)
+{
+ rtx x = *px;
+ tree t;
+
+ if (x == NULL_RTX || GET_CODE (x) != MEM)
+ return 0;
+
+ t = MEM_ORIG_EXPR (x);
+
+ if (!t)
+ {
+ print ("!MEM_ORIG_EXPR: ");
+ print_inline_rtx_1 (dump_file, x, 0);
+ print ("\n");
+ refs_bad++;
+ }
+ else
+ {
+ print (" MEM_ORIG_EXPR: ");
+ print_inline_rtx_1 (dump_file, x, 0);
+ print (" -> ");
+ print_generic_expr_1 (dump_file, t, TDF_VOPS|TDF_MEMSYMS);
+ print (" (%p)\n", (void *) t);
+ verify_trees_gimple (t);
+ }
+
+ return 0;
+}
+
+/* Depending on current IR, either check that we have saved datarefs for all
+ memory references, or we have MEM_ORIG_EXPRs for MEMs. */
+void
+verify_trees (void)
+{
+ bool inside_tree_loop_opt_p = !!current_loops;
+ bool dom_info_was_avail_p = dom_info_available_p (CDI_DOMINATORS);
+ loop_iterator li;
+ struct loop *loop;
+
+ if (!ddg_info/* || !dump_file*/)
+ return;
+
+ if (!inside_tree_loop_opt_p)
+ loop_optimizer_init(AVOID_CFG_MODIFICATIONS);
+
+ cur_loop = 0;
+
+ FOR_EACH_LOOP (li, loop, 0)
+ {
+ /* We are trying to verify datarefs for a loop that was not processed
+ during export. We must have noticed it and adjust exported data
+ accordingly. Just break for now. */
+ if (cur_loop == ddg_info->loopnum)
+ break;
+ /* gcc_assert (cur_loop < ddg_info->loopnum); */
+
+ basic_block *bbs = get_loop_body (loop);
+ unsigned int i;
+
+ refs_bad = refs_ok = 0;
+ ddrs_known = ddrs_no = ddrs_unknown = ddrs_not_found = 0;
+
+ for (i = 0; i < loop->num_nodes; i++)
+ if (current_ir_type () == IR_GIMPLE)
+ {
+ block_stmt_iterator bsi;
+ for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ {
+ verify_trees_gimple (GIMPLE_STMT_OPERAND (stmt, 0));
+ verify_trees_gimple (GIMPLE_STMT_OPERAND (stmt, 1));
+ }
+ }
+ }
+ else
+ {
+ rtx insn;
+
+ FOR_BB_INSNS (bbs[i], insn)
+ if (INSN_P (insn) && !CALL_P (insn))
+ for_each_rtx (&PATTERN (insn), verify_trees_rtl, NULL);
+ }
+
+ VEC_free (data_reference_p, heap, verifier_seen_datarefs);
+ print ("<ddg> loop %d: %d refs, %d ok, %d bad; %d not found ddrs, "
+ "%d known deps, %d no deps, %d unknown deps\n",
+ cur_loop, refs_bad+refs_ok, refs_ok, refs_bad, ddrs_not_found,
+ ddrs_known, ddrs_no, ddrs_unknown);
+ cur_loop++;
+ }
+
+ if (!inside_tree_loop_opt_p)
+ loop_optimizer_finalize ();
+
+ if (!dom_info_was_avail_p)
+ free_dominance_info (CDI_DOMINATORS);
+}
+
+#include "gt-tree-data-ref-export.h"
+
diff -puN trunk/gcc/tree-data-ref-export.h export-ddg/gcc/tree-data-ref-export.h
--- trunk/gcc/tree-data-ref-export.h 1970-01-01 03:00:00.000000000 +0300
+++ export-ddg/gcc/tree-data-ref-export.h 2007-06-29 12:58:53.000000000
+0400
@@ -0,0 +1,10 @@
+#ifndef TREE_DATA_REF_EXPORT_H
+#define TREE_DATA_REF_EXPORT_H
+
+#include "tree-data-ref.h"
+
+extern void verify_trees (void);
+extern void replace_var_in_datarefs (tree, tree);
+
+#endif /* TREE_DATA_REF_EXPORT_H */
+
diff -puN trunk/gcc/tree-optimize.c export-ddg/gcc/tree-optimize.c
--- trunk/gcc/tree-optimize.c 2007-06-22 20:20:01.000000000 +0400
+++ export-ddg/gcc/tree-optimize.c 2007-06-29 17:33:14.000000000 +0400
@@ -257,7 +257,7 @@ struct tree_opt_pass pass_free_cfg_annot
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- 0, /* todo_flags_finish */
+ TODO_no_verify_trees, /* todo_flags_finish */
0 /* letter */
};
diff -puN trunk/gcc/tree-pass.h export-ddg/gcc/tree-pass.h
--- trunk/gcc/tree-pass.h 2007-06-22 20:16:21.000000000 +0400
+++ export-ddg/gcc/tree-pass.h 2007-07-02 17:53:32.000000000 +0400
@@ -171,6 +171,7 @@ struct dump_file_info
#define TODO_dump_cgraph (1 << 7)
#define TODO_remove_functions (1 << 8)
#define TODO_rebuild_frequencies (1 << 9)
+#define TODO_no_verify_trees (1 << 10)
/* To-do flags for calls to update_ssa. */
@@ -264,6 +265,8 @@ extern struct tree_opt_pass pass_if_conv
extern struct tree_opt_pass pass_vectorize;
extern struct tree_opt_pass pass_complete_unroll;
extern struct tree_opt_pass pass_loop_prefetch;
+extern struct tree_opt_pass pass_gather_ddg_info;
+extern struct tree_opt_pass pass_free_ddg_info;
extern struct tree_opt_pass pass_iv_optimize;
extern struct tree_opt_pass pass_tree_loop_done;
extern struct tree_opt_pass pass_ch;
diff -puN trunk/gcc/tree-ssa-loop-ivopts.c export-ddg/gcc/tree-ssa-loop-ivopts.c
--- trunk/gcc/tree-ssa-loop-ivopts.c 2007-06-22 20:19:11.000000000 +0400
+++ export-ddg/gcc/tree-ssa-loop-ivopts.c 2007-07-02 17:53:43.000000000
+0400
@@ -92,6 +92,7 @@ Software Foundation, 51 Franklin Street,
#include "langhooks.h"
#include "tree-affine.h"
#include "target.h"
+#include "tree-data-ref-export.h"
/* The infinite cost. */
#define INFTY 10000000
@@ -5069,6 +5070,11 @@ copy_ref_info (tree new_ref, tree old_re
{
TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
+ /* As MEM_ORIG_EXPR binds MEM to TMR_ORIGINAL of TARGET_MEM_REF it was
+ produced from, we need to change all occurences of OLD_REF to
+ TMR_ORIGINAL (NEW_REF) in exported data. */
+ if (flag_export_ddg)
+ replace_var_in_datarefs (old_ref, TMR_ORIGINAL (new_ref));
}
}
