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 (" 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)); } }