Here's the patch for sms-and-memory-dependencies. The idea is to bypass the sched-deps.c {output,read,anti,true}_dependence tests altogether -- which is easy to do thanks to the note_mem_dep hook -- and instead handle them in ddg.c. The ddg.c tests then use RTL loop iv analysis to try to get longer distances on the memory dependencies. (Note that other memory-related dependencies, such as those between volatile MEMs and other volatile instructions, are still handled by sched-deps.c.)

Dependencies are now always created in pairs, so there's no need for get_sched_window to set an upper bound when processing incoming MEM_DEPs, or a lower bound when processing outgoing MEM_DEPs; we can rely on the partnering edge to do that instead.

Richard

gcc/ * Makefile.in (ddg.o): Depend on $(TREE_PASS_H). * ddg.h (REG_OR_MEM_DEP, REG_AND_MEM_DEP): Delete. (ddg_mem_ref): New structure. (ddg): Add loads and stores array. (create_ddg): Add a loop argument. (add_edges_to_ddg): Declare. (MAX_DDG_DISTANCE): New macro. * ddg.c: Include tree-pass.h. (mem_ref_p, mark_mem_use, mark_mem_use_1, mem_read_insn_p) (mark_mem_store, mem_write_insn_p, rtx_mem_access_p) (mem_access_insn_p): Delete. (create_mem_ref): New function. (graph_and_node): New structure. (record_loads, record_stores): New functions. (create_ddg_dep_from_intra_loop_link): Treat all dependencies as register dependencies. (walk_mems_2, walk_mems_1, insns_may_alias_p, add_intra_loop_mem_dep) (add_inter_loop_mem_dep): Delete. (build_intra_loop_deps): Ignore memory dependencies created by sched-deps.c. Don't handle memory dependencies here. (measure_mem_distance, add_memory_dep): New functions. (FOR_EACH_LATER_MEM_REF): New macro. (build_memory_deps): New function. (create_ddg): Take the loop as argument. Don't count loads and stores here. Call iv_analysis_loop_init. Pass all loads to record_loads and all stores to record_stores. Move edge creation to... (add_edges_to_ddg): ...this new function. Also call build_memory_deps. * modulo-sched.c (sat_mulpp, sat_addsp, sat_subsp): New functions. (schedule_reg_moves): Only handle register dependencies. (sms_schedule): Update call to create_ddg. Call iv_analysis_done after creating all ddgs. Only set issue_rate if there are ddgs. Only call setup_sched_infos and haifa_sched_init if there are ddgs. Call add_edges_to_ddg before processing each ddg. (get_sched_window): Use saturating arithmetic. Do not add an implicit upper bound for incoming MEM_DEPs, or an implicit lower bound for outgoing MEM_DEPs. Rework calculation of final window. (calculate_must_precede_follow, compute_split_row): Use saturating arithmetic.

Index: gcc/Makefile.in =================================================================== --- gcc/Makefile.in 2011-12-30 13:13:45.077544981 +0000 +++ gcc/Makefile.in 2011-12-30 13:24:57.330195801 +0000 @@ -3316,7 +3316,7 @@ ddg.o : ddg.c $(DDG_H) $(CONFIG_H) $(SYS $(DIAGNOSTIC_CORE_H) $(RTL_H) $(TM_P_H) $(REGS_H) $(FUNCTION_H) \ $(FLAGS_H) insn-config.h $(INSN_ATTR_H) $(EXCEPT_H) $(RECOG_H) \ $(SCHED_INT_H) $(CFGLAYOUT_H) $(CFGLOOP_H) $(EXPR_H) $(BITMAP_H) \ - hard-reg-set.h sbitmap.h $(TM_H) + hard-reg-set.h sbitmap.h $(TM_H) $(TREE_PASS_H) modulo-sched.o : modulo-sched.c $(DDG_H) $(CONFIG_H) $(CONFIG_H) $(SYSTEM_H) \ coretypes.h $(TARGET_H) $(DIAGNOSTIC_CORE_H) $(RTL_H) $(TM_P_H) $(REGS_H) $(FUNCTION_H) \ $(FLAGS_H) insn-config.h $(INSN_ATTR_H) $(EXCEPT_H) $(RECOG_H) \ Index: gcc/ddg.h =================================================================== --- gcc/ddg.h 2011-12-30 13:13:45.077544981 +0000 +++ gcc/ddg.h 2011-12-30 13:24:57.324195831 +0000 @@ -35,8 +35,7 @@ typedef struct ddg_scc *ddg_scc_ptr; typedef struct ddg_all_sccs *ddg_all_sccs_ptr;

typedef enum {TRUE_DEP, OUTPUT_DEP, ANTI_DEP} dep_type; -typedef enum {REG_OR_MEM_DEP, REG_DEP, MEM_DEP, REG_AND_MEM_DEP} - dep_data_type; +typedef enum {REG_DEP, MEM_DEP} dep_data_type;

/* The following two macros enables direct access to the successors and predecessors bitmaps held in each ddg_node. Do not make changes to @@ -44,6 +43,28 @@ typedef enum {REG_OR_MEM_DEP, REG_DEP, M #define NODE_SUCCESSORS(x) ((x)->successors) #define NODE_PREDECESSORS(x) ((x)->predecessors)

+/* A structure that represents a memory read or write in the DDG; + context decides which. */ +struct ddg_mem_ref { + /* The previous reference of the same type (read or write) in the DDG. */ + struct ddg_mem_ref *prev; + + /* The DDG node that contains the memory reference. */ + ddg_node_ptr node; + + /* The memory reference itself. */ + rtx mem; + + /* If the address is a known induction variable, its value in iteration + I is given by: + + BASE + OFFSET + I * STEP + + In other cases BASE is null. */ + rtx base; + HOST_WIDE_INT offset, step; +}; + /* A structure that represents a node in the DDG. */ struct ddg_node { @@ -117,6 +138,11 @@ struct ddg /* Number of instructions in the basic block. */ int num_nodes;

+ /* The loads and stores in the BB, from the end of the block to + the beginning. */ + struct ddg_mem_ref *loads; + struct ddg_mem_ref *stores; + /* Number of load/store instructions in the BB - statistics. */ int num_loads; int num_stores; @@ -167,7 +193,9 @@ struct ddg_all_sccs };

-ddg_ptr create_ddg (basic_block, int closing_branch_deps); +struct loop; +ddg_ptr create_ddg (struct loop *, basic_block, int closing_branch_deps); +void add_edges_to_ddg (ddg_ptr); void free_ddg (ddg_ptr);

void print_ddg (FILE *, ddg_ptr); @@ -188,4 +216,7 @@ int longest_simple_path (ddg_ptr, int fr

bool autoinc_var_is_used_p (rtx, rtx);

+/* The maximum allowable distance on a DDG edge. */ +#define MAX_DDG_DISTANCE INT_MAX + #endif /* GCC_DDG_H */ Index: gcc/ddg.c =================================================================== --- gcc/ddg.c 2011-12-30 13:13:45.077544981 +0000 +++ gcc/ddg.c 2011-12-30 13:36:35.005498271 +0000 @@ -43,6 +43,7 @@ Software Foundation; either version 3, o #include "expr.h" #include "bitmap.h" #include "ddg.h" +#include "tree-pass.h"

#ifdef INSN_SCHEDULING

@@ -61,88 +62,102 @@ static ddg_edge_ptr create_ddg_edge (ddg dep_data_type, int, int); static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr);  -/* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */ -static bool mem_ref_p; +/* Create a memory reference record for MEM, which occurs in NODE. + PREV is the previous reference of the same type. */ +static struct ddg_mem_ref * +create_mem_ref (struct ddg_mem_ref *prev, ddg_node_ptr node, rtx mem) +{ + struct ddg_mem_ref *entry; + enum machine_mode pmode; + struct rtx_iv iv; + rtx x; + + entry = XCNEW (struct ddg_mem_ref); + entry->prev = prev; + entry->node = node; + entry->mem = mem; + + pmode = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mem)); + if (iv_analyze_expr (node->insn, XEXP (mem, 0), pmode, &iv) + && iv.extend == UNKNOWN + && CONST_INT_P (iv.step)) + { + x = iv.base; + if (GET_CODE (x) == PLUS && CONST_INT_P (XEXP (x, 1))) + { + entry->base = XEXP (x, 0); + entry->offset = INTVAL (XEXP (x, 1)); + } + else + { + entry->base = x; + entry->offset = 0; + } + entry->step = INTVAL (iv.step); + }

-/* Auxiliary function for mem_read_insn_p. */ -static int -mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED) -{ - if (MEM_P (*x)) - mem_ref_p = true; - return 0; + if (dump_file) + { + fprintf (dump_file, "Found memory reference in insn %d:\n", + INSN_UID (node->insn)); + print_rtl (dump_file, mem); + if (entry->base) + { + fprintf (dump_file, "\nwith base:"); + print_rtl (dump_file, entry->base); + fprintf (dump_file, "\noffset " HOST_WIDE_INT_PRINT_DEC + " and step " HOST_WIDE_INT_PRINT_DEC "\n\n", + entry->offset, entry->step); + } + else + fprintf (dump_file, "\nwhich isn't a recognized iv\n\n"); + } + return entry; }

-/* Auxiliary function for mem_read_insn_p. */ -static void -mark_mem_use_1 (rtx *x, void *data) -{ - for_each_rtx (x, mark_mem_use, data); -} +/* A structure for pairing a node and the graph to which it belongs. */ +struct graph_and_node { + ddg_ptr g; + ddg_node_ptr node; +};

-/* Returns nonzero if INSN reads from memory. */ -static bool -mem_read_insn_p (rtx insn) +/* A for_each_rtx callback. Record all loads in an instruction. + DATA points to a graph_and_node. */ +static int +record_loads_1 (rtx *loc, void *data) { - mem_ref_p = false; - note_uses (&PATTERN (insn), mark_mem_use_1, NULL); - return mem_ref_p; -} + struct graph_and_node *gn;

-static void -mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) -{ - if (MEM_P (loc)) - mem_ref_p = true; + if (MEM_P (*loc)) + { + gn = (struct graph_and_node *) data; + gn->g->loads = create_mem_ref (gn->g->loads, gn->node, *loc); + gn->g->num_loads++; + } + return 0; }

-/* Returns nonzero if INSN writes to memory. */ -static bool -mem_write_insn_p (rtx insn) +/* A note_uses callback. Record all loads in an instruction. + DATA points to a graph_and_node. */ +static void +record_loads (rtx *loc, void *data) { - mem_ref_p = false; - note_stores (PATTERN (insn), mark_mem_store, NULL); - return mem_ref_p; + for_each_rtx (loc, record_loads_1, data); }

-/* Returns nonzero if X has access to memory. */ -static bool -rtx_mem_access_p (rtx x) +/* A note_stores callback. Record all stores in an instruction. + DATA points to a graph_and_node. */ +static void +record_stores (rtx x, const_rtx setter ATTRIBUTE_UNUSED, void *data) { - int i, j; - const char *fmt; - enum rtx_code code; - - if (x == 0) - return false; + struct graph_and_node *gn;

if (MEM_P (x)) - return true; - - code = GET_CODE (x); - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) { - if (fmt[i] == 'e') - { - if (rtx_mem_access_p (XEXP (x, i))) - return true; - } - else if (fmt[i] == 'E') - for (j = 0; j < XVECLEN (x, i); j++) - { - if (rtx_mem_access_p (XVECEXP (x, i, j))) - return true; - } + gn = (struct graph_and_node *) data; + gn->g->stores = create_mem_ref (gn->g->stores, gn->node, x); + gn->g->num_stores++; } - return false; -} - -/* Returns nonzero if INSN reads to or writes from memory. */ -static bool -mem_access_insn_p (rtx insn) -{ - return rtx_mem_access_p (PATTERN (insn)); }

/* Return true if DEF_INSN contains address being auto-inc or auto-dec @@ -175,9 +190,6 @@ create_ddg_dep_from_intra_loop_link (ddg ddg_edge_ptr e; int latency, distance = 0; dep_type t = TRUE_DEP; - dep_data_type dt = (mem_access_insn_p (src_node->insn) - && mem_access_insn_p (dest_node->insn) ? MEM_DEP - : REG_DEP); gcc_assert (src_node->cuid < dest_node->cuid); gcc_assert (link);

@@ -201,7 +213,7 @@ create_ddg_dep_from_intra_loop_link (ddg TODO: support the removal of all anti-deps edges, i.e. including those whose register has multiple defs in the loop. */ if (flag_modulo_sched_allow_regmoves - && (t == ANTI_DEP && dt == REG_DEP) + && t == ANTI_DEP && !autoinc_var_is_used_p (dest_node->insn, src_node->insn)) { rtx set; @@ -224,7 +236,7 @@ create_ddg_dep_from_intra_loop_link (ddg }

latency = dep_cost (link); - e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance); + e = create_ddg_edge (src_node, dest_node, t, REG_DEP, latency, distance); add_edge_to_ddg (g, e); }

@@ -380,107 +392,6 @@ build_inter_loop_deps (ddg_ptr g) } }

- -static int -walk_mems_2 (rtx *x, rtx mem) -{ - if (MEM_P (*x)) - { - if (may_alias_p (*x, mem)) - return 1; - - return -1; - } - return 0; -} - -static int -walk_mems_1 (rtx *x, rtx *pat) -{ - if (MEM_P (*x)) - { - /* Visit all MEMs in *PAT and check indepedence. */ - if (for_each_rtx (pat, (rtx_function) walk_mems_2, *x)) - /* Indicate that dependence was determined and stop traversal. */ - return 1; - - return -1; - } - return 0; -} - -/* Return 1 if two specified instructions have mem expr with conflict alias sets*/ -static int -insns_may_alias_p (rtx insn1, rtx insn2) -{ - /* For each pair of MEMs in INSN1 and INSN2 check their independence. */ - return for_each_rtx (&PATTERN (insn1), (rtx_function) walk_mems_1, - &PATTERN (insn2)); -} - -/* Given two nodes, analyze their RTL insns and add intra-loop mem deps - to ddg G. */ -static void -add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) -{ - - if ((from->cuid == to->cuid) - || !insns_may_alias_p (from->insn, to->insn)) - /* Do not create edge if memory references have disjoint alias sets - or 'to' and 'from' are the same instruction. */ - return; - - if (mem_write_insn_p (from->insn)) - { - if (mem_read_insn_p (to->insn)) - create_ddg_dep_no_link (g, from, to, - DEBUG_INSN_P (to->insn) - ? ANTI_DEP : TRUE_DEP, MEM_DEP, 0); - else - create_ddg_dep_no_link (g, from, to, - DEBUG_INSN_P (to->insn) - ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 0); - } - else if (!mem_read_insn_p (to->insn)) - create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 0); -} - -/* Given two nodes, analyze their RTL insns and add inter-loop mem deps - to ddg G. */ -static void -add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) -{ - if (!insns_may_alias_p (from->insn, to->insn)) - /* Do not create edge if memory references have disjoint alias sets. */ - return; - - if (mem_write_insn_p (from->insn)) - { - if (mem_read_insn_p (to->insn)) - create_ddg_dep_no_link (g, from, to, - DEBUG_INSN_P (to->insn) - ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1); - else if (from->cuid != to->cuid) - create_ddg_dep_no_link (g, from, to, - DEBUG_INSN_P (to->insn) - ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1); - } - else - { - if (mem_read_insn_p (to->insn)) - return; - else if (from->cuid != to->cuid) - { - create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1); - if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn)) - create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1); - else - create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1); - } - } - -} - /* Perform intra-block Data Dependency analysis and connect the nodes in the DDG. We assume the loop has a single basic block. */ static void @@ -493,6 +404,9 @@ build_intra_loop_deps (ddg_ptr g)

/* Build the dependence information, using the sched_analyze function. */ init_deps_global (); + /* Ignore the usual dependencies between two MEM rtxes. We still rely + on sched_analyze to handle memory barriers and the like. */ + sched_deps_info->note_mem_dep = 0; init_deps (&tmp_deps, false);

/* Do the intra-block data dependence analysis for the given block. */ @@ -519,37 +433,6 @@ build_intra_loop_deps (ddg_ptr g)

create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep); } - - /* If this insn modifies memory, add an edge to all insns that access - memory. */ - if (mem_access_insn_p (dest_node->insn)) - { - int j; - - for (j = 0; j <= i; j++) - { - ddg_node_ptr j_node = &g->nodes[j]; - if (DEBUG_INSN_P (j_node->insn)) - continue; - if (mem_access_insn_p (j_node->insn)) - { - /* Don't bother calculating inter-loop dep if an intra-loop dep - already exists. */ - if (! TEST_BIT (dest_node->successors, j)) - add_inter_loop_mem_dep (g, dest_node, j_node); - /* If -fmodulo-sched-allow-regmoves - is set certain anti-dep edges are not created. - It might be that these anti-dep edges are on the - path from one memory instruction to another such that - removing these edges could cause a violation of the - memory dependencies. Thus we add intra edges between - every two memory instructions in this case. */ - if (flag_modulo_sched_allow_regmoves - && !TEST_BIT (dest_node->predecessors, j)) - add_intra_loop_mem_dep (g, j_node, dest_node); - } - } - } }

/* Free the INSN_LISTs. */ @@ -560,13 +443,187 @@ build_intra_loop_deps (ddg_ptr g) sched_free_deps (head, tail, false); }

+/* Given a "source" memory reference from iteration 0 and a "target" + memory reference from iteration BASE_DISTANCE, return the first + N >= BASE_DISTANCE such that the source reference in iteration 0 + overlaps the target reference in iteration N. + + FROM_OFFSET is the offset of the source reference from an unspecified + base, while TO_OFFSET is the offset of the target reference from that + same base. FROM_SIZE and TO_SIZE are the sizes of the two references + in bytes. + + PMODE is the mode of both addresses, and STEP is the amount that + will be added to each address by one loop iteration. */ +static int +measure_mem_distance (enum machine_mode pmode, + unsigned HOST_WIDE_INT from_offset, + unsigned HOST_WIDE_INT from_size, + unsigned HOST_WIDE_INT to_offset, + unsigned HOST_WIDE_INT to_size, + unsigned HOST_WIDE_INT base_distance, + HOST_WIDE_INT step) +{ + unsigned HOST_WIDE_INT extra, from2to, to2from; + + from2to = (to_offset - from_offset) & GET_MODE_MASK (pmode); + to2from = (from_offset - to_offset) & GET_MODE_MASK (pmode); + if (from2to < from_size || to2from < to_size) + /* The source reference in iteration 0 overlaps the target reference + in iteration BASE_DISTANCE. The check is written this way to cope + with cases where offset + size overflows. */ + return base_distance; + + /* N > BASE_DISTANCE. To cope more easily with cases where the round-up + divisions: + + (to2from - (to_size - 1) + (step - 1)) / step + (from2to - (from_size - 1) + (step - 1)) / step + + would overflow, bump BASE_DISTANCE and subtract STEP from each + dividend to compensate. */ + base_distance++; + if (step > 0) + extra = (to2from - to_size) / (unsigned HOST_WIDE_INT) step; + else + extra = (from2to - from_size) / (unsigned HOST_WIDE_INT) -step; + if (extra > MAX_DDG_DISTANCE || base_distance + extra > MAX_DDG_DISTANCE) + return MAX_DDG_DISTANCE; + return base_distance + extra; +} + +/* If FROM and TO might alias, record memory dependencies: + + FROM--(FORWARD_TYPE)-->TO + and TO--(BACKWARD_TYPE)-->FROM + + FROM comes before TO in the original loop, and both belong to G. + FORWARD_DISTANCE is the minimum distance of the FROM--->TO dependence. */ +static void +add_memory_dep (ddg_ptr g, struct ddg_mem_ref *from, + struct ddg_mem_ref *to, dep_type forward_type, + dep_type backward_type, int forward_distance) +{ + HOST_WIDE_INT step; + unsigned HOST_WIDE_INT from_size, to_size, to_disp, abs_step, future_offset; + enum machine_mode pmode; + int backward_distance; + + gcc_checking_assert (from->node->cuid < to->node->cuid); + + if (!may_alias_p (from->mem, to->mem)) + return; + + /* In the worst case, the TO---->FROM edge has a distance of 1. */ + backward_distance = 1; + + /* See if we can get more accurate distances. Look for cases where + the addresses of FROM and TO are ivs with the same base and step. */ + if (from->base + && to->base + && from->step + && from->step == to->step + && !MEM_VOLATILE_P (from->mem) + && !MEM_VOLATILE_P (to->mem) + && MEM_SIZE_KNOWN_P (from->mem) + && MEM_SIZE_KNOWN_P (to->mem) + && MEM_ADDR_SPACE (from->mem) == MEM_ADDR_SPACE (to->mem) + && rtx_equal_p (from->base, to->base)) + { + step = to->step; + abs_step = (step < 0 ? -step : step); + from_size = MEM_SIZE (from->mem); + to_size = MEM_SIZE (to->mem); + + /* If the step is a power of two, or the negative of a power of two, + see whether we can prove that the references never overlap. */ + if (abs_step == (abs_step & -abs_step)) + { + to_disp = (to->offset - from->offset) % abs_step; + if (from_size <= to_disp && to_disp + to_size <= abs_step) + return; + } + + pmode = targetm.addr_space.address_mode (MEM_ADDR_SPACE (to->mem)); + future_offset = to->offset + forward_distance * step; + forward_distance = measure_mem_distance (pmode, + from->offset, from_size, + future_offset, to_size, + forward_distance, step); + future_offset = from->offset + backward_distance * step; + backward_distance = measure_mem_distance (pmode, + to->offset, to_size, + future_offset, from_size, + backward_distance, step); + } + + if (DEBUG_INSN_P (from->node->insn) || DEBUG_INSN_P (to->node->insn)) + { + forward_type = ANTI_DEP; + backward_type = ANTI_DEP; + } + create_ddg_dep_no_link (g, from->node, to->node, forward_type, MEM_DEP, + forward_distance); + create_ddg_dep_no_link (g, to->node, from->node, backward_type, MEM_DEP, + backward_distance); +} + +/* Make REF2 iterate over all entries in ddg_mem_ref list LIST + that come later than ddg_mem_ref REF1. */ +#define FOR_EACH_LATER_MEM_REF(REF2, REF1, LIST) \ + for (REF2 = (LIST); \ + REF2 && REF2->node->cuid > REF1->node->cuid; \ + REF2 = REF2->prev) + +/* Check for dependencies between pairs of memory rtxes. */ +static void +build_memory_deps (ddg_ptr g) +{ + struct ddg_mem_ref *ref1, *ref2; + int distance; + + for (ref1 = g->loads; ref1; ref1 = ref1->prev) + { + /* LOAD--->LOAD. */ + if (MEM_VOLATILE_P (ref1->mem)) + FOR_EACH_LATER_MEM_REF (ref2, ref1, g->loads) + if (MEM_VOLATILE_P (ref2->mem)) + add_memory_dep (g, ref1, ref2, ANTI_DEP, ANTI_DEP, 0); + + /* LOAD--->STORE. */ + FOR_EACH_LATER_MEM_REF (ref2, ref1, g->stores) + { + distance = anti_dependence (ref1->mem, ref2->mem) ? 0 : 1; + add_memory_dep (g, ref1, ref2, ANTI_DEP, TRUE_DEP, distance); + } + } + + for (ref1 = g->stores; ref1; ref1 = ref1->prev) + { + /* STORE--->LOAD. */ + FOR_EACH_LATER_MEM_REF (ref2, ref1, g->loads) + { + distance = true_dependence (ref1->mem, VOIDmode, + ref2->mem, rtx_varies_p) ? 0 : 1; + add_memory_dep (g, ref1, ref2, TRUE_DEP, ANTI_DEP, distance); + } + + /* STORE--->STORE. */ + FOR_EACH_LATER_MEM_REF (ref2, ref1, g->stores) + { + distance = output_dependence (ref1->mem, ref2->mem) ? 0 : 1; + add_memory_dep (g, ref1, ref2, OUTPUT_DEP, OUTPUT_DEP, distance); + } + } +}

-/* Given a basic block, create its DDG and return a pointer to a variable - of ddg type that represents it. +/* Given a basic block, create the nodes of its DDG and return a pointer + to a variable of ddg type that represents it. Initialize the ddg structure fields to the appropriate values. */ ddg_ptr -create_ddg (basic_block bb, int closing_branch_deps) +create_ddg (struct loop *loop, basic_block bb, int closing_branch_deps) { + struct graph_and_node gn; ddg_ptr g; rtx insn, first_note; int i; @@ -586,13 +643,6 @@ create_ddg (basic_block bb, int closing_

if (DEBUG_INSN_P (insn)) g->num_debug++; - else - { - if (mem_read_insn_p (insn)) - g->num_loads++; - if (mem_write_insn_p (insn)) - g->num_stores++; - } num_nodes++; }

@@ -603,6 +653,8 @@ create_ddg (basic_block bb, int closing_ return NULL; }

+ iv_analysis_loop_init (loop); + /* Allocate the nodes array, and initialize the nodes. */ g->num_nodes = num_nodes; g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node)); @@ -637,18 +689,31 @@ create_ddg (basic_block bb, int closing_ g->nodes[i].predecessors = sbitmap_alloc (num_nodes); sbitmap_zero (g->nodes[i].predecessors); g->nodes[i].first_note = (first_note ? first_note : insn); - g->nodes[i++].insn = insn; + g->nodes[i].insn = insn; first_note = NULL_RTX; + + gn.g = g; + gn.node = &g->nodes[i]; + note_uses (&PATTERN (insn), record_loads, &gn); + note_stores (PATTERN (insn), record_stores, &gn); + + i++; }

/* We must have found a branch in DDG. */ gcc_assert (g->closing_branch); + return g; +}

+/* Add the edges to a DDG that was previously created by create_ddg. + This function relies on scheduler dependencies. */

- /* Build the data dependency graph. */ +void +add_edges_to_ddg (ddg_ptr g) +{ build_intra_loop_deps (g); build_inter_loop_deps (g); - return g; + build_memory_deps (g); }

/* Free all the memory allocated for the DDG. */ Index: gcc/modulo-sched.c =================================================================== --- gcc/modulo-sched.c 2011-12-30 13:13:45.077544981 +0000 +++ gcc/modulo-sched.c 2011-12-30 13:24:57.327195816 +0000 @@ -345,6 +345,38 @@ ps_num_consecutive_stages (partial_sched return ps_reg_move (ps, id)->num_consecutive_stages; }

+/* Perform a saturating multiplication of nonnegative values A and B. */ + +static inline int +sat_mulpp (unsigned int a, unsigned int b) +{ + if ((unsigned int) INT_MAX / b <= a) + return INT_MAX; + else + return a * b; +} + +/* Perform a saturating addition of signed value A and nonnegative value B. */ + +static inline int +sat_addsp (int a, int b) +{ + if (INT_MAX - b <= a) + return INT_MAX; + return a + b; +} + +/* Perform a saturating subtraction of signed value A and nonnegative + value B. */ + +static inline int +sat_subsp (int a, int b) +{ + if (INT_MIN + b >= a) + return INT_MIN; + return a - b; +} + /* Given HEAD and TAIL which are the first and last insns in a loop; return the register which controls the loop. Return zero if it has more than one occurrence in the loop besides the control part or the @@ -709,7 +741,9 @@ schedule_reg_moves (partial_schedule_ptr ranges started at u (excluding self-loops). */ distances[0] = distances[1] = false; for (e = u->out; e; e = e->next_out) - if (e->type == TRUE_DEP && e->dest != e->src) + if (e->data_type == REG_DEP + && e->type == TRUE_DEP + && e->dest != e->src) { int nreg_moves4e = (SCHED_TIME (e->dest->cuid) - SCHED_TIME (e->src->cuid)) / ii; @@ -781,7 +815,9 @@ schedule_reg_moves (partial_schedule_ptr copy of this register, depending on the time the use is scheduled. Record which uses require which move results. */ for (e = u->out; e; e = e->next_out) - if (e->type == TRUE_DEP && e->dest != e->src) + if (e->data_type == REG_DEP + && e->type == TRUE_DEP + && e->dest != e->src) { int dest_copy = (SCHED_TIME (e->dest->cuid) - SCHED_TIME (e->src->cuid)) / ii; @@ -1355,6 +1391,7 @@ sms_schedule (void) basic_block condition_bb = NULL; edge latch_edge; gcov_type trip_count = 0; + int num_ddgs;

loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_RECORDED_EXITS); @@ -1364,34 +1401,19 @@ sms_schedule (void) return; /* There are no loops to schedule. */ }

- /* Initialize issue_rate. */ - if (targetm.sched.issue_rate) - { - int temp = reload_completed; - - reload_completed = 1; - issue_rate = targetm.sched.issue_rate (); - reload_completed = temp; - } - else - issue_rate = 1; - - /* Initialize the scheduler. */ - setup_sched_infos (); - haifa_sched_init (); - /* Allocate memory to hold the DDG array one entry for each loop. We use loop->num as index into this array. */ g_arr = XCNEWVEC (ddg_ptr, number_of_loops ());

if (dump_file) - { - fprintf (dump_file, "\n\nSMS analysis phase\n"); - fprintf (dump_file, "===================\n\n"); - } + { + fprintf (dump_file, "\n\nSMS loop discovery phase\n"); + fprintf (dump_file, "========================\n\n"); + }

/* Build DDGs for all the relevant loops and hold them in G_ARR indexed by the loop index. */ + num_ddgs = 0; FOR_EACH_LOOP (li, loop, 0) { rtx head, tail; @@ -1512,7 +1534,7 @@ sms_schedule (void) instructions. The branch is rotated to be in row ii-1 at the end of the scheduling procedure to make sure it's the last instruction in the iteration. */ - if (! (g = create_ddg (bb, 1))) + if (! (g = create_ddg (loop, bb, 1))) { if (dump_file) fprintf (dump_file, "SMS create_ddg failed\n"); @@ -1523,12 +1545,38 @@ sms_schedule (void) if (dump_file) fprintf (dump_file, "...OK\n");

+ num_ddgs++; + } + iv_analysis_done (); + + if (num_ddgs == 0) + { + if (dump_file) + fprintf (dump_file, "No suitable loops\n"); + goto done; } + + /* Initialize issue_rate. */ + if (targetm.sched.issue_rate) + { + int temp = reload_completed; + + reload_completed = 1; + issue_rate = targetm.sched.issue_rate (); + reload_completed = temp; + } + else + issue_rate = 1; + + /* Initialize the scheduler. */ + setup_sched_infos (); + haifa_sched_init (); + if (dump_file) - { - fprintf (dump_file, "\nSMS transformation phase\n"); - fprintf (dump_file, "=========================\n\n"); - } + { + fprintf (dump_file, "\nSMS transformation phase\n"); + fprintf (dump_file, "=========================\n\n"); + }

/* We don't want to perform SMS on new loops - created by versioning. */ FOR_EACH_LOOP (li, loop, 0) @@ -1542,6 +1590,8 @@ sms_schedule (void) if (! (g = g_arr[loop->num])) continue;

+ add_edges_to_ddg (g); + if (dump_file) { rtx insn = BB_END (loop->header); @@ -1754,10 +1804,12 @@ sms_schedule (void) free_ddg (g); }

- free (g_arr); - /* Release scheduler data, needed until now because of DFA. */ haifa_sched_finish (); + + done: + free (g_arr); + loop_optimizer_finalize (); }

@@ -1844,6 +1896,7 @@ #define DFA_HISTORY SMS_DFA_HISTORY /* A threshold for the number of repeated unsuccessful attempts to insert an empty row, before we flush the partial schedule and start over. */ #define MAX_SPLIT_NUM 10 + /* Given the partial schedule PS, this function calculates and returns the cycles in which we can schedule the node with the given index I. NOTE: Here we do the backtracking in SMS, in some special cases. We have @@ -1896,7 +1949,7 @@ get_sched_window (partial_schedule_ptr p fprintf (dump_file, "=========== =========== =========== ===========" " =====\n"); } - /* Calculate early_start and limit end. Both bounds are inclusive. */ + /* Calculate early_start and limit start. Both bounds are inclusive. */ if (psp_not_empty) for (e = u_node->in; e != 0; e = e->next_in) { @@ -1905,26 +1958,36 @@ get_sched_window (partial_schedule_ptr p if (TEST_BIT (sched_nodes, v)) { int p_st = SCHED_TIME (v); - int earliest = p_st + e->latency - (e->distance * ii); - int latest = (e->data_type == MEM_DEP ? p_st + ii - 1 : INT_MAX); + int earliest = sat_subsp (sat_addsp (p_st, e->latency), + sat_mulpp (e->distance, ii));

+ if (e->data_type == MEM_DEP) + { + start = MAX (start, earliest); + if (dump_file) + fprintf (dump_file, "%11d %11s %11s %11s", + earliest, "", "", ""); + } + else + { + early_start = MAX (early_start, earliest); + if (dump_file) + fprintf (dump_file, "%11s %11d %11s %11s", + "", earliest, "", ""); + } if (dump_file) { - fprintf (dump_file, "%11s %11d %11s %11d %5d", - "", earliest, "", latest, p_st); + fprintf (dump_file, " %5d", p_st); print_ddg_edge (dump_file, e); fprintf (dump_file, "\n"); }

- early_start = MAX (early_start, earliest); - end = MIN (end, latest); - if (e->type == TRUE_DEP && e->data_type == REG_DEP) count_preds++; } }

- /* Calculate late_start and limit start. Both bounds are inclusive. */ + /* Calculate late_start and limit end. Both bounds are inclusive. */ if (pss_not_empty) for (e = u_node->out; e != 0; e = e->next_out) { @@ -1933,20 +1996,30 @@ get_sched_window (partial_schedule_ptr p if (TEST_BIT (sched_nodes, v)) { int s_st = SCHED_TIME (v); - int earliest = (e->data_type == MEM_DEP ? s_st - ii + 1 : INT_MIN); - int latest = s_st - e->latency + (e->distance * ii); + int latest = sat_addsp (sat_subsp (s_st, e->latency), + sat_mulpp (e->distance, ii));

+ if (e->data_type == MEM_DEP) + { + end = MIN (end, latest); + if (dump_file) + fprintf (dump_file, "%11s %11s %11s %11d", + "", "", "", latest); + } + else + { + late_start = MIN (late_start, latest); + if (dump_file) + fprintf (dump_file, "%11s %11s %11d %11s", + "", "", latest, ""); + } if (dump_file) { - fprintf (dump_file, "%11d %11s %11d %11s %5d", - earliest, "", latest, "", s_st); + fprintf (dump_file, " %5d", s_st); print_ddg_edge (dump_file, e); fprintf (dump_file, "\n"); }

- start = MAX (start, earliest); - late_start = MIN (late_start, latest); - if (e->type == TRUE_DEP && e->data_type == REG_DEP) count_succs++; } @@ -1963,14 +2036,22 @@ get_sched_window (partial_schedule_ptr p

/* Get a target scheduling window no bigger than ii. */ if (early_start == INT_MIN && late_start == INT_MAX) - early_start = NODE_ASAP (u_node); - else if (early_start == INT_MIN) - early_start = late_start - (ii - 1); - late_start = MIN (late_start, early_start + (ii - 1)); - - /* Apply memory dependence limits. */ - start = MAX (start, early_start); - end = MIN (end, late_start); + { + /* The default window (as given in the paper) is based on + the node's ASAP value, but shift or shrink it as necessary + in order to honor memory dependencies. */ + early_start = MIN (NODE_ASAP (u_node), end - (ii - 1)); + start = MAX (early_start, start); + } + else + { + end = MIN (end, late_start); + if (early_start == INT_MIN) + start = MAX (start, end - (ii - 1)); + else + start = MAX (start, early_start); + } + end = MIN (end, start + (ii - 1));

if (dump_file && (psp_not_empty || pss_not_empty)) fprintf (dump_file, "%11s %11d %11d %11s %5s final window\n", @@ -2060,8 +2141,8 @@ calculate_must_precede_follow (ddg_node_ SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */ for (e = u_node->in; e != 0; e = e->next_in) if (TEST_BIT (sched_nodes, e->src->cuid) - && ((SCHED_TIME (e->src->cuid) - (e->distance * ii)) == - first_cycle_in_window)) + && (sat_subsp (SCHED_TIME (e->src->cuid), sat_mulpp (e->distance, ii)) + == first_cycle_in_window)) { if (dump_file) fprintf (dump_file, "%d ", e->src->cuid); @@ -2371,7 +2452,8 @@ compute_split_row (sbitmap sched_nodes, int v = e->src->cuid;

if (TEST_BIT (sched_nodes, v) - && (low == SCHED_TIME (v) + e->latency - (e->distance * ii))) + && low == sat_subsp (sat_addsp (SCHED_TIME (v), e->latency), + sat_mulpp (e->distance, ii))) if (SCHED_TIME (v) > lower) { crit_pred = v;