(Zdenek, I CC'ed you because I need some clarification regarding your
loop-structures-preserving project; please see below)
Hello,
I'd like to provide an update on the ddg-exporting project and request
some more comments. Ian, thanks for your feedback and for catching
redundant code.
Testing on tree-vectorizer testsuite and some of the GCC source files
showed that frequent source of apparent loss of exported information
were passes that performed basic block reordering or jump threading.
The verifier asserted that number of loops was constant and the order
they are visited by FOR_EACH_LOOP remained the same throughout the
compilation.
The number of loops may be changed, for example, when
-- bb1 --
loop:
smth1;
if (cond1) jump out;
-- bb2 --
smth2;
if (..) jump loop;
-- bb3 --
smth3;
jump loop;
--
out:
is transformed into
-- bb1 --
loop:
smth1;
if (cond1) jump out;
-- bb2 --
loop2:
smth2;
if (...) jump loop;
-- bb3 --
smth3;
smth1;
if (!cond1) jump loop2;
In the latter sequence, flow_loops_find would find two loops: bb1-bb2
and bb2-bb3. The other obvious source of changing of number of loops
would be RTL loop unswitching. There was also an example of order of
loops changing after the VRP pass.
Zdenek, could you please clarify whether and how your LoopPreserving
project is going to influence the mentioned problems? Are you
interested in that VRP example? By the way, I'd like you to remind
you that you mentioned before that RTL loop unswitching might be
removed from GCC.
That said, I do not see the mentioned concerns as serious problems,
because the verifier can be made more permissive, and one can search
exported data references in all loops. Even if order and count of
loop changes, if we are able to find data dependency relation for two
given MEMs later, it will still make sense, with this notable
exception: if RTL loop unrolling (or reversal) is performed, then the
found ddr will contain incorrect distance (because the increment of
the index changed). Is that correct? What would be the preferred
approach: fixing up the exported data, or discarding the irrelevant
information?
I mentioned before that I would need to take care of basic block
duplication on tree level, but I have seen no example of that
happening after iv-opts so far. Does anyone know offhand whether it
is possible?
Thanks
--
Alexander Monakov
--- gcc/tree-pass.h (/gcc-local/trunk) (revision 29647)
+++ gcc/tree-pass.h (/gcc-local/export-ddg) (revision 29647)
@@ -226,6 +226,9 @@ struct dump_file_info
/* Internally used for the first instance of a pass. */
#define TODO_mark_first_instance (1 << 17)
+#define TODO_no_verify_trees (1 << 18)
+
+
#define TODO_update_ssa_any \
(TODO_update_ssa \
| TODO_update_ssa_no_phi \
@@ -264,6 +267,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;
--- gcc/tree-ssa-loop-ivopts.c (/gcc-local/trunk) (revision 29647)
+++ gcc/tree-ssa-loop-ivopts.c (/gcc-local/export-ddg) (revision 29647)
@@ -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));
}
}
--- gcc/function.c (/gcc-local/trunk) (revision 29647)
+++ gcc/function.c (/gcc-local/export-ddg) (revision 29647)
@@ -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;
}
--- gcc/function.h (/gcc-local/trunk) (revision 29647)
+++ gcc/function.h (/gcc-local/export-ddg) (revision 29647)
@@ -297,6 +297,14 @@ 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;
+
+ /* This serves as GC root for trees for which data references
+ were exported. */
+ VEC(tree, gc) *ddg_info_root_for_trees;
+
/* Current nesting level for temporaries. */
int x_temp_slot_level;
--- gcc/emit-rtl.c (/gcc-local/trunk) (revision 29647)
+++ gcc/emit-rtl.c (/gcc-local/export-ddg) (revision 29647)
@@ -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;
@@ -1469,6 +1476,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 +1541,8 @@ set_mem_attributes_minus_bitpos (rtx ref
{
tree base;
+ orig_expr = t;
+
if (TREE_THIS_VOLATILE (t))
MEM_VOLATILE_P (ref) = 1;
@@ -1708,11 +1718,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 +1750,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 +1765,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 +1776,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 +1785,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 +1815,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 +1833,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 +1901,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 +1969,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 +2026,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 +2067,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 +2133,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;
}
--- gcc/tree-data-ref-export.c (/gcc-local/trunk) (revision 29647)
+++ gcc/tree-data-ref-export.c (/gcc-local/export-ddg) (revision 29647)
@@ -0,0 +1,486 @@
+#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;
+
+ /* Used by the verifier. */
+ VEC (data_reference_p, heap) *verifier_seen_datarefs;
+
+ int ddrs_known, ddrs_no, ddrs_unknown, ddrs_not_found;
+
+ /* Number of memory references without/with relevant exported info. */
+ int refs_bad, refs_ok;
+};
+
+#define ddg_info (cfun->x_ddg_info)
+
+#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, cfun->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;
+ cfun->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, cfun->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, cfun->ddg_info_root_for_trees, i, t); i++)
+ if (t == from)
+ {
+ found = true;
+ VEC_replace (tree, cfun->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);
+}
+
+/* Search for the dataref for T and return it if found, otherwise return
+ NULL. */
+
+data_reference_p find_dataref (tree);
+
+data_reference_p
+find_dataref (tree t)
+{
+ unsigned int i;
+ data_reference_p drf, ret = NULL;
+ unsigned loop_num = 0;
+
+ for (loop_num = 0; loop_num < ddg_info->loopnum; loop_num++)
+ {
+ for (i = 0;
+ VEC_iterate (data_reference_p, ddg_info->datarefs[loop_num], i, drf);
+ i++)
+ if (drf->ref == t)
+ return drf;
+ }
+
+ return ret;
+}
+
+static ddr_p
+find_ddr (data_reference_p dr1, data_reference_p dr2)
+{
+ unsigned int i;
+ ddr_p ddr, ret = NULL;
+ unsigned loop_num = 0;
+
+ for (loop_num = 0; loop_num < ddg_info->loopnum; loop_num++)
+ {
+ for (i = 0; VEC_iterate (ddr_p, ddg_info->ddrs[loop_num], i, ddr); i++)
+ if ((ddr->a == dr1 && ddr->b == dr2)
+ || (ddr->a == dr2 && ddr->b == dr1))
+ return ddr;
+ }
+
+ return ret;
+}
+
+
+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, ddg_info->verifier_seen_datarefs,
+ dataref);
+
+ for (i = 0;
+ VEC_iterate (data_reference_p, ddg_info->verifier_seen_datarefs, i, dr);
+ i++)
+ if ((ddr = find_ddr (dataref, dr)))
+ {
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ ddg_info->ddrs_known++;
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ ddg_info->ddrs_no++;
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ ddg_info->ddrs_unknown++;
+ }
+ else
+ ddg_info->ddrs_not_found++;
+}
+
+/* Print trees for which we expect to find saved dataref. */
+static tree
+verify_trees_gimple (tree *tp, int *walk_subtrees,
+ void *data ATTRIBUTE_UNUSED)
+{
+ data_reference_p dataref;
+ tree t = *tp;
+
+ if (TREE_CODE (t) == TARGET_MEM_REF)
+ t = TREE_OPERAND (t, 5);
+ if (REFERENCE_CLASS_P (t))
+ {
+ *walk_subtrees = 0;
+ if ((dataref = find_dataref (t)))
+ {
+ print (" DATAREF: (%p) ", (void *)t);
+ print_generic_expr_1 (dump_file, t, TDF_VOPS|TDF_MEMSYMS);
+ print ("\n");
+ ddg_info->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));
+ ddg_info->refs_bad++;
+ }
+ }
+ return NULL_TREE;
+}
+
+
+/* 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;
+ int dummy;
+
+ if (x == NULL_RTX || GET_CODE (x) != MEM)
+ return 0;
+
+ t = MEM_ORIG_EXPR (x);
+
+ if (!t)
+ {
+ print ("!MEM_ORIG_EXPR: (%p) RTX: (%p) ", (void*)t, (void*)x);
+ print_inline_rtx_1 (dump_file, x, 0);
+ print ("\n");
+ ddg_info->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, &dummy, NULL);
+ }
+
+ 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;
+ unsigned cur_loop = 0;
+
+ if (!ddg_info/* || !dump_file*/)
+ return;
+
+ if (!inside_tree_loop_opt_p)
+ loop_optimizer_init(AVOID_CFG_MODIFICATIONS);
+
+
+ FOR_EACH_LOOP (li, loop, 0)
+ {
+ unsigned int i;
+ basic_block *bbs = get_loop_body (loop);
+
+ /* 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. */
+ /* gcc_assert (cur_loop < ddg_info->loopnum); */
+ if (cur_loop == ddg_info->loopnum)
+ break;
+
+ ddg_info->refs_bad = ddg_info->refs_ok = 0;
+ ddg_info->ddrs_known = ddg_info->ddrs_no = ddg_info->ddrs_unknown = 0;
+ ddg_info->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))
+ walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
+ verify_trees_gimple, NULL);
+ }
+ 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, ddg_info->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, ddg_info->refs_bad+ddg_info->refs_ok,
+ ddg_info->refs_ok, ddg_info->refs_bad, ddg_info->ddrs_not_found,
+ ddg_info->ddrs_known, ddg_info->ddrs_no, ddg_info->ddrs_unknown);
+ cur_loop++;
+ }
+
+ if (!inside_tree_loop_opt_p)
+ loop_optimizer_finalize ();
+
+ if (!dom_info_was_avail_p)
+ free_dominance_info (CDI_DOMINATORS);
+}
+
--- gcc/cfgexpand.c (/gcc-local/trunk) (revision 29647)
+++ gcc/cfgexpand.c (/gcc-local/export-ddg) (revision 29647)
@@ -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 */
};
--- gcc/emit-rtl.h (/gcc-local/trunk) (revision 29647)
+++ gcc/emit-rtl.h (/gcc-local/export-ddg) (revision 29647)
@@ -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);
--- gcc/tree-data-ref-export.h (/gcc-local/trunk) (revision 29647)
+++ gcc/tree-data-ref-export.h (/gcc-local/export-ddg) (revision 29647)
@@ -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 */
+
--- gcc/common.opt (/gcc-local/trunk) (revision 29647)
+++ gcc/common.opt (/gcc-local/export-ddg) (revision 29647)
@@ -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
--- gcc/rtl.h (/gcc-local/trunk) (revision 29647)
+++ gcc/rtl.h (/gcc-local/export-ddg) (revision 29647)
@@ -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)
--- gcc/tree-optimize.c (/gcc-local/trunk) (revision 29647)
+++ gcc/tree-optimize.c (/gcc-local/export-ddg) (revision 29647)
@@ -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 */
};
--- gcc/Makefile.in (/gcc-local/trunk) (revision 29647)
+++ gcc/Makefile.in (/gcc-local/export-ddg) (revision 29647)
@@ -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,10 @@ 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
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) \
--- gcc/passes.c (/gcc-local/trunk) (revision 29647)
+++ gcc/passes.c (/gcc-local/export-ddg) (revision 29647)
@@ -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;
Property changes on:
___________________________________________________________________
Name: svk:merge
23c3ee16-a423-49b3-8738-b114dc1aabb6:/local/gcc-clean:839
23c3ee16-a423-49b3-8738-b114dc1aabb6:/local/gcc-pta-dev:259
23c3ee16-a423-49b3-8738-b114dc1aabb6:/local/gcc-trunk:531
+41d2e0e8-8285-4a91-821f-3a5385f608dd:/gcc-local/trunk:29627
+41d2e0e8-8285-4a91-821f-3a5385f608dd:/gcc-local/trunk-patched:18768
7dca8dba-45c1-47dc-8958-1a7301c5ed47:/local-gcc/md-constraint:113709
f367781f-d768-471e-ba66-e306e17dff77:/local/gen-rework-20060122:110130
