[GSoC] New static scheduler priority. Final status.
Zhurichin Dmitry
zhur@ispras.ru
Fri Aug 24 15:59:00 GMT 2007
Hi! This is a final status update for my GSoC 2007 project. The
following patches contain code that implements two new approaches to
static priority for Haifa scheduler.
First approach is the speculative yield heuristic. In details it is
desribed in the article "Enhancing Intruction Level Parallelism through
Compiler-Controlled Speculation" by R.A.Bringmann, PhD thesis, 1995 (see
chapter 3.4.2) [ http://citeseer.ist.psu.edu/bringmann95enhancing.html ].
Briefly, first critical path values to each of exits from current
scheduling domain (region or EBB) are computed for each instruction in
this domain. Then priority is set to sum over all exits of this value
multiplied by probability of taking corresponding exit. This means that
instruction which is earlier in path to an exit is prioritized over
instruction which is later on this path; similarly, instruction which is
on path to more probable exit is prioritized over instruction from
path to less probable exit; and, instruction from many paths to different
exits can be prioritized over instruction from lesser number of paths to
some of those exits.
This approach can be used when scheduling is done on regions as well as
on EBBs.
Second approach is the G* heuristic, described in the article "Profile-
Driven Instruction Level Parallel Scheduling with Application to Super
Blocks" by C.Chekuri et al
[ http://citeseer.ist.psu.edu/chekuri96profiledriven.html ]. In few
words, scheduling domain is split into several non-overlapping subsets,
each of them being a subgraph of data dependence graph for
scheduling domain rooted at some exit from this domain. Such
distribution is done iteratively, choosing on each iteration exit with
best computational time required per unit of exit probability (i.e.
exit with minimal ratio of time needed to issue this exit to sum of
probabilities of all exits, including current, that are on paths leading
to current exit). Then all instructions, on which the chosen exit is
dependent, are excluded from consideration, and procedure is repeated
until each instruction was distributed into some subset. After such order
of subsets was created, each instruction is given a priority that is
greater than priorities of instructions from previous subsets and lesser
than priorities of instructions from the following subsets, and inside the
same subset priority of instruction is calculated as critical path value
to the last exit from the subset.
This approach is now working only on EBBs, but my future plans are to
try make it work on regions too.
Attached patches are following: patch 0 contains all code in one file
(other patches are additional in the sense that they are just for easier
understanding of changes); patch 1 contains new flags for turning on
or off those new features; patches 2 and 3 are context diffs and contain
modified parts of scheduler drivers in sched-ebb.c and sched-rgn.c;
patch 4 holds changes to sched-int.h; remaining patches contain diffs to
haifa-sched.c, patch 5 being a context diff of function priority, patch 6
being a common functions of both new approaches for finding exits from
scheduling domain and debug and also contains speculative yield part of
the project; the last patch is a G* heuristic implementation.
Patched version of GCC trunk bootstraps and passes check successfully,
compiles SPEC CPU2000 on ia64, but unfortunately gives no significant
improvements to performance. My guess is that with such number of
processor units, scheduling priority plays secondary factor. Though I
have not got enough time to study results thoroughly and plan to look at
why new priorities do not give improvements on ia64 some time later. In
this context, I will appreciate much if someone can test my patches on
some other platforms (where scheduler plays an important role). Any other
comments are welcome too. Thanks!
Dmitry Zhurikhin
-------------- next part --------------
=== gcc/common.opt
==================================================================
--- gcc/common.opt (revision 30596)
+++ gcc/common.opt (local)
@@ -860,6 +860,18 @@
Common Report Var(flag_sched2_use_superblocks) Optimization
If scheduling post reload, do superblock scheduling
+fsched-spec-yield
+Common Report Var(flag_sched_spec_yield) Init(1)
+Use speculative yield heuristic for priority
+
+fsched-g-star
+Common Report Var(flag_sched_g_star) Init(1)
+Use G* heuristic for priority
+
+fsched-g-star-use-rjbound
+Common Report Var(flag_sched_g_star_use_rjbound) Init(1)
+Use Rim and Jain estimation of execution time while using G* priority
+
fsched2-use-traces
Common Report Var(flag_sched2_use_traces) Optimization
If scheduling post reload, do trace scheduling
=== gcc/haifa-sched.c
==================================================================
--- gcc/haifa-sched.c (revision 30596)
+++ gcc/haifa-sched.c (local)
@@ -504,6 +504,9 @@
static void find_insn_reg_weight1 (rtx);
static void adjust_priority (rtx);
static void advance_one_cycle (void);
+static int g_star_priority (rtx);
+static void create_g_distribution (void);
+static void free_exit_lengths (rtx insn);
/* Notes handling mechanism:
=========================
@@ -704,10 +707,31 @@
return cost;
}
+/* Flags marking if G* r speculative yield heuristics should be used. */
+static bool use_g_star_priority, use_spec_yield_priority;
+/* Vector that holds exit instructions from current scheduling domain. */
+VEC (rtx, heap) *exit_insns;
+#define EXIT_INSN(I) VEC_index (rtx, exit_insns, I)
+/* Vector that holds probability of taking corresponding exit. */
+VEC (int, heap) *exit_probs;
+#define EXIT_PROB(I) VEC_index (int, exit_probs, I)
+static void find_path_length_to_exit_insns (rtx);
+/* Number of exits. */
+#define EXIT_NUM VEC_length (rtx, exit_insns)
+/* Vector of distribution of instructions of scheduling domain over baskets. */
+static int *g_star_distribution;
+/* Gaps of priority between baskets. */
+static int *additions;
+/* Maximal instruction luid at the beginning of scheduling. */
+static int max_insn_luid;
+
/* Return 'true' if DEP should be included in priority calculations. */
static bool
contributes_to_priority_p (dep_t dep)
{
+ if (use_spec_yield_priority || use_g_star_priority)
+ return true;
+
/* Critical path is meaningful in block boundaries only. */
if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
DEP_PRO (dep)))
@@ -731,6 +755,8 @@
static int
priority (rtx insn)
{
+ int this_priority = 0;
+
if (! INSN_P (insn))
return 0;
@@ -739,78 +765,108 @@
if (!INSN_PRIORITY_KNOWN (insn))
{
- int this_priority = 0;
+ if (use_g_star_priority)
+ {
+ insn_cost (insn);
- if (sd_lists_empty_p (insn, SD_LIST_FORW))
- /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
- some forward deps but all of them are ignored by
- contributes_to_priority hook. At the moment we set priority of
- such insn to 0. */
- this_priority = insn_cost (insn);
- else
- {
- rtx prev_first, twin;
- basic_block rec;
+ this_priority = g_star_priority (insn);
- /* For recovery check instructions we calculate priority slightly
- different than that of normal instructions. Instead of walking
- through INSN_FORW_DEPS (check) list, we walk through
- INSN_FORW_DEPS list of each instruction in the corresponding
- recovery block. */
+ gcc_assert (this_priority >= 0);
+ }
+ else if (use_spec_yield_priority)
+ {
+ unsigned int i;
- rec = RECOVERY_BLOCK (insn);
- if (!rec || rec == EXIT_BLOCK_PTR)
- {
- prev_first = PREV_INSN (insn);
- twin = insn;
- }
- else
- {
- prev_first = NEXT_INSN (BB_HEAD (rec));
- twin = PREV_INSN (BB_END (rec));
- }
+ gcc_assert (VEC_length (rtx, exit_insns)
+ == VEC_length (int, exit_probs));
- do
- {
- sd_iterator_def sd_it;
- dep_t dep;
+ insn_cost (insn);
- FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
- {
- rtx next;
- int next_priority;
+ /* Compute path lengths to all exits for INSN. */
+ find_path_length_to_exit_insns (insn);
+ gcc_assert (VEC_length (int, INSN_EXIT_LENGTHS (insn)) == EXIT_NUM);
- next = DEP_CON (dep);
+ /* Calculate priority as sum over all exits of products of critical
+ path length from instruction INSN to exit and probability of
+ taking the exit. */
+ for (i = 0; i < EXIT_NUM; i++)
+ {
+ if (INSN_EXIT_LENGTH (insn, i) >= 0)
+ this_priority += (INSN_EXIT_LENGTH (insn, i) + 1)
+ * EXIT_PROB(i);
+ }
- if (BLOCK_FOR_INSN (next) != rec)
- {
- int cost;
+ gcc_assert (this_priority >= 0);
+ }
+ else /* !use_spec_yield_priority && !use_g_star_priority */
+ {
+ if (sd_lists_empty_p (insn, SD_LIST_FORW))
+ /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
+ some forward deps but all of them are ignored by
+ contributes_to_priority hook. At the moment we set priority of
+ such insn to 0. */
+ this_priority = insn_cost (insn);
+ else
+ {
+ rtx prev_first, twin;
+ basic_block rec;
+ /* For recovery check instructions we calculate priority slightly
+ different than that of normal instructions. Instead of walking
+ through INSN_FORW_DEPS (check) list, we walk through
+ INSN_FORW_DEPS list of each instruction in the corresponding
+ recovery block. */
+ rec = RECOVERY_BLOCK (insn);
+ if (!rec || rec == EXIT_BLOCK_PTR)
+ {
+ prev_first = PREV_INSN (insn);
+ twin = insn;
+ }
+ else
+ {
+ prev_first = NEXT_INSN (BB_HEAD (rec));
+ twin = PREV_INSN (BB_END (rec));
+ }
+ do
+ {
+ sd_iterator_def sd_it;
+ dep_t dep;
- if (!contributes_to_priority_p (dep))
- continue;
+ FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
+ {
+ rtx next;
+ int next_priority;
+ next = DEP_CON (dep);
- if (twin == insn)
- cost = dep_cost (dep);
- else
- {
- struct _dep _dep1, *dep1 = &_dep1;
+ if (BLOCK_FOR_INSN (next) != rec)
+ {
+ int cost;
- init_dep (dep1, insn, next, REG_DEP_ANTI);
+ if (!contributes_to_priority_p (dep))
+ continue;
- cost = dep_cost (dep1);
- }
+ if (twin == insn)
+ cost = dep_cost (dep);
+ else
+ {
+ struct _dep _dep1, *dep1 = &_dep1;
- next_priority = cost + priority (next);
+ init_dep (dep1, insn, next, REG_DEP_ANTI);
- if (next_priority > this_priority)
- this_priority = next_priority;
- }
- }
-
- twin = PREV_INSN (twin);
- }
- while (twin != prev_first);
- }
+ cost = dep_cost (dep1);
+ }
+
+ next_priority = cost + priority (next);
+
+ if (next_priority > this_priority)
+ this_priority = next_priority;
+ }
+ }
+
+ twin = PREV_INSN (twin);
+ }
+ while (twin != prev_first);
+ }
+ }
INSN_PRIORITY (insn) = this_priority;
INSN_PRIORITY_STATUS (insn) = 1;
}
@@ -2544,6 +2600,16 @@
fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
}
+ if (use_spec_yield_priority)
+ {
+ rtx insn;
+ for (insn = last_scheduled_insn;
+ insn != prev_head;
+ insn = PREV_INSN (insn))
+ if (INSN_P (insn) && INSN_EXIT_LENGTHS (insn) != NULL)
+ free_exit_lengths (insn);
+ }
+
if (targetm.sched.md_finish)
{
targetm.sched.md_finish (sched_dump, sched_verbose);
@@ -2615,6 +2681,8 @@
if (head == tail && (! INSN_P (head)))
return 0;
+ use_spec_yield_priority = false;
+ use_g_star_priority = false;
n_insn = 0;
@@ -2638,9 +2706,521 @@
return n_insn;
}
+/* Returns an index of BB inside BBS (greater than BEGIN) or length of BBS
+ if it BB does not belong to BBS vector. */
+
+static inline unsigned int
+find_bb_in_bbs (basic_block bb, VEC (basic_block, heap) *bbs,
+ unsigned int begin)
+{
+ for (; begin < VEC_length (basic_block, bbs); begin++)
+ if (VEC_index (basic_block, bbs, begin) == bb)
+ break;
+
+ return begin;
+}
+
+static int
+sum_of_edge_probabilities (VEC(edge,gc) *vec)
+{
+ edge e;
+ edge_iterator ei;
+ int sum = 0;
+
+ FOR_EACH_EDGE (e, ei, vec)
+ sum += e->probability;
+
+ return sum;
+}
+
+/* Find the probability of control flow reaching basic block TARGET given
+ control flow goes only inside basic blocks of set of basic blocks BBS and
+ no basic blocks can be visited twice (that way loops are discarded). */
+
+static int
+prob_enter_bb (basic_block target, VEC (basic_block, heap) *bbs)
+{
+ int prob = 0;
+ bool found = false;
+ VEC (int, heap) *bb_stack
+ = VEC_alloc (int, heap, VEC_length (basic_block, bbs));
+ VEC (int, heap) *prob_stack
+ = VEC_alloc (int, heap, VEC_length (basic_block, bbs));
+
+ VEC_quick_push (int, bb_stack, 0);
+ VEC_quick_push (int, prob_stack, REG_BR_PROB_BASE);
+
+ while (!VEC_empty (int, bb_stack))
+ {
+ edge e;
+ edge_iterator ei;
+ int cur_prob = VEC_pop (int, prob_stack);
+ int cur_bb_index = VEC_pop (int, bb_stack);
+ basic_block cur_bb = VEC_index (basic_block, bbs, cur_bb_index);
+
+ if (cur_bb == target)
+ {
+ prob += cur_prob;
+ found = true;
+ continue;
+ }
+
+ FOR_EACH_EDGE (e, ei, cur_bb->succs)
+ {
+ unsigned int new_bb_index;
+
+ /* Find a E->DEST block in BBS vector.
+ Note that this search is based on assumption that BBS is
+ topologically sorted and we do not need a backward edge,
+ that can lead only to entry block. */
+ new_bb_index = find_bb_in_bbs (e->dest, bbs, cur_bb_index + 1);
+
+ /* Skip blocks not from scheduling domain. */
+ if (new_bb_index < VEC_length (basic_block, bbs))
+ {
+ VEC_quick_push (int, bb_stack, new_bb_index);
+ VEC_quick_push (int, prob_stack,
+ (e->probability * cur_prob)
+ / sum_of_edge_probabilities (cur_bb->succs));
+ }
+ }
+ }
+
+ gcc_assert (prob <= REG_BR_PROB_BASE);
+ gcc_assert (found);
+ return prob;
+}
+
+/* Returns probability of taking any path leading from BB outside of
+ set of basic blocks BBS. */
+
+static int
+prob_exit_bbs (basic_block bb, VEC (basic_block, heap) *bbs)
+{
+ int prob = 0;
+ edge e;
+ edge_iterator ei;
+ unsigned int bb_index = find_bb_in_bbs (bb, bbs, 0);
+
+ gcc_assert (bb_index < VEC_length (basic_block, bbs));
+
+ /* Skip empty blocks. */
+ while (bb_note (bb) == BB_END (bb))
+ {
+ if (!bb->next_bb || bb->next_bb == EXIT_BLOCK_PTR
+ || find_bb_in_bbs (bb->next_bb, bbs, bb_index + 1)
+ == VEC_length (basic_block, bbs))
+ return REG_BR_PROB_BASE;
+
+ bb = bb->next_bb;
+ }
+
+ /* No-return block. */
+ if (VEC_empty (edge, bb->succs))
+ return REG_BR_PROB_BASE;
+
+ /* Find the probability of exit. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ unsigned int succ_bb_index = find_bb_in_bbs (e->dest, bbs, bb_index + 1);
+
+ if (succ_bb_index < VEC_length (basic_block, bbs))
+ {
+ basic_block succ_bb = e->dest;
+ bool succ_is_exit = (succ_bb == EXIT_BLOCK_PTR);
+
+ /* Skip empty blocks. */
+ while (bb_note (succ_bb) == BB_END (succ_bb))
+ {
+ if (!succ_bb->next_bb || succ_bb->next_bb == EXIT_BLOCK_PTR
+ || find_bb_in_bbs (succ_bb->next_bb, bbs, succ_bb_index + 1)
+ == VEC_length (basic_block, bbs))
+ {
+ succ_is_exit = true;
+ break;
+ }
+
+ succ_bb = succ_bb->next_bb;
+ }
+
+ /* Increase the probability if successor block is not in BBS set. */
+ if (succ_is_exit)
+ prob += e->probability;
+ }
+ else
+ /* Same. */
+ prob += e->probability;
+ }
+
+ if (prob > REG_BR_PROB_BASE)
+ {
+ /* Possible bug - sum of probabilities of outgoing edges of
+ basic block BB is greater than REG_BR_PROB_BASE. */
+ prob = REG_BR_PROB_BASE;
+ }
+ gcc_assert (prob >= 0);
+ return prob;
+}
+
+/* Check if INSN can be an exit from a scheduling domain. */
+
+static bool
+all_forw_deps_in_other_blocks_p (rtx insn)
+{
+ basic_block bb = BLOCK_FOR_INSN (insn);
+ rtx end = BB_END (bb);
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ /* Instructions with forward dependencies to instructions from the same
+ basic block cannot be an exit. */
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ if (bb == BLOCK_FOR_INSN (DEP_CON (dep)))
+ return false;
+
+ /* Instruction from basic block that ends with a jump (except speculation
+ checks) cannot be an exit.*/
+ if (end != insn
+ && JUMP_P (end)
+ && RECOVERY_BLOCK (end) == NULL)
+ return false;
+
+ return true;
+}
+
+/* Find all exit insns from a set of basic blocks BBS. This function fills
+ EXIT_INSNS and EXIT_PROBS vectors. */
+
+static void
+find_exit_insns (VEC (basic_block, heap) *bbs)
+{
+ int i;
+ basic_block bb;
+ rtx insn;
+
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ {
+ int prob_exit_from_bbs = -1;
+ int prob_enter_to_bb = -1;
+
+ for (insn = BB_HEAD (bb);
+ insn != NEXT_INSN (BB_END (bb));
+ insn = NEXT_INSN (insn))
+ {
+ if (!INSN_P (insn))
+ continue;
+
+ /* Check if INSN can be a candidate for exit from BBS. */
+ if (all_forw_deps_in_other_blocks_p (insn))
+ {
+ if (prob_exit_from_bbs == -1)
+ {
+ /* If probability of exiting from BBS starting from BB
+ is not yet computed - do it now. */
+ prob_exit_from_bbs = prob_exit_bbs (bb, bbs);
+ }
+ if (prob_exit_from_bbs > 0)
+ {
+ /* INSN is an exit. */
+ if (prob_enter_to_bb == -1)
+ prob_enter_to_bb = prob_enter_bb (bb, bbs);
+ VEC_safe_push (rtx, heap, exit_insns, insn);
+ /* Probability of the exit is probability of reaching basic
+ block of the exit from the entry of scheduling domain
+ multiplied by probability of leaving scheduling domain
+ from the same basic block. */
+ VEC_safe_push (int, heap, exit_probs,
+ (prob_exit_from_bbs * prob_enter_to_bb)
+ / REG_BR_PROB_BASE);
+ }
+ }
+ }
+ }
+}
+
+/* Finds critical path length from INSN to exit, given by EXIT_INDEX number.
+ Returns -1 if there is no path from INSN to such exit.
+ Also fills INSN_EXIT_LENGTH attribute of INSN. */
+
+static int
+find_path_length_to_exit_insn (rtx insn, unsigned int exit_index)
+{
+ int max_len = -1;
+ sd_iterator_def sd_it;
+ dep_t dep;
+ rtx exit = EXIT_INSN (exit_index);
+
+ /* Case this already has been computed. */
+ if (exit_index < VEC_length (int, INSN_EXIT_LENGTHS (insn)))
+ return INSN_EXIT_LENGTH (insn, exit_index);
+
+ if (insn == exit)
+ max_len = insn_cost (exit);
+ else
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ int len =
+ find_path_length_to_exit_insn (DEP_CON (dep),
+ exit_index);
+ if (len != -1)
+ max_len = MAX (len + dep_cost (dep), max_len);
+ }
+
+ VEC_safe_insert (int, heap, INSN_EXIT_LENGTHS (insn), exit_index, max_len);
+ return max_len;
+}
+
+/* Finds critical path lengths for INSN to each of exits from current
+ scheduling domain. */
+
+static void
+find_path_length_to_exit_insns (rtx insn)
+{
+ unsigned int i;
+
+ /* Already computed. */
+ if (!VEC_empty (int, INSN_EXIT_LENGTHS (insn)))
+ return;
+
+ for (i = 0; i < EXIT_NUM; i++)
+ find_path_length_to_exit_insn (insn, i);
+}
+
+/* Clear INSN_EXIT_LENGTHS attribute for INSN. */
+
+static void
+clear_path_lengths (rtx insn)
+{
+ VEC_truncate (int, INSN_EXIT_LENGTHS (insn), 0);
+}
+
+/* Free INSN_EXIT_LENGTHS attribute of INSN and all its sucessors. */
+
+static void
+free_exit_lengths (rtx insn)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ rtx succ = DEP_CON (dep);
+ if (INSN_EXIT_LENGTHS (succ) != NULL)
+ free_exit_lengths (succ);
+ }
+ VEC_free (int, heap, INSN_EXIT_LENGTHS (insn));
+}
+
+/* Check if exit insns are still exit insns. */
+
+static void
+check_exit_insns (void)
+{
+ int i;
+ rtx exit;
+
+ for (i = 0; VEC_iterate (rtx, exit_insns, i, exit); i++)
+ gcc_assert (INSN_TICK (exit) != INVALID_TICK
+ || all_forw_deps_in_other_blocks_p (exit));
+}
+
+/* Replace an EXIT with REPLACEMENT in EXIT_INSNS vector. */
+
+static void
+replace_exit_insns (rtx exit, rtx replacement)
+{
+ int i;
+ rtx cur_exit;
+ bool replaced = false;
+
+ for (i = 0; VEC_iterate (rtx, exit_insns, i, cur_exit); i++)
+ {
+ if (INSN_UID (exit) == INSN_UID (cur_exit))
+ {
+ gcc_assert (replaced == false);
+ VEC_replace (rtx, exit_insns, i, replacement);
+ replaced = true;
+ }
+ }
+}
+
+/* Computes priorities for all instructions in basic block BB.
+ Returns number of instructions in BB. */
+
+static int
+compute_priority_for_block (basic_block bb)
+{
+ int n = 0;
+ rtx insn;
+ int sched_max_insns_priority =
+ current_sched_info->sched_max_insns_priority;
+
+ /* Compute priorities. */
+ for (insn = BB_END (bb);
+ insn != PREV_INSN (BB_HEAD (bb));
+ insn = PREV_INSN (insn))
+ {
+ if (!INSN_P (insn))
+ continue;
+
+ n++;
+ (void) priority (insn);
+
+ if (INSN_PRIORITY_KNOWN (insn))
+ sched_max_insns_priority =
+ MAX (sched_max_insns_priority, INSN_PRIORITY (insn));
+ }
+
+ current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
+ return n;
+}
+
+/* Fills priorities for all instructions from set of basic blocks BBS. */
+
/* Next LUID to assign to an instruction. */
static int luid;
+/* Sets priorities of all instructions in basic blocks from vector BBS. */
+
+int
+set_priorities_for_bbs (VEC (basic_block, heap) *bbs)
+{
+ int i, n = 0;
+
+ exit_insns = VEC_alloc (rtx, heap, 1);
+ exit_probs = VEC_alloc (int, heap, 1);
+
+ find_exit_insns (bbs);
+
+ if (flag_sched_g_star && reload_completed)
+ {
+ max_insn_luid = luid - 1;
+ use_g_star_priority = true;
+ g_star_distribution = XCNEWVEC (int, max_insn_luid + 1);
+ additions = XCNEWVEC (int, EXIT_NUM);
+ create_g_distribution ();
+ }
+ else
+ use_g_star_priority = false;
+
+ /* There must be only one. */
+ use_spec_yield_priority = !use_g_star_priority;
+
+ for (i = VEC_length (basic_block, bbs) - 1; i >= 0; i--)
+ n += compute_priority_for_block (VEC_index (basic_block, bbs, i));
+
+ return n;
+}
+
+/* Free vectors used for computing priorities. */
+
+void
+finish_priorities (void)
+{
+ VEC_free (rtx, heap, exit_insns);
+ VEC_free (int, heap, exit_probs);
+ if (use_g_star_priority)
+ {
+ free (g_star_distribution);
+ free (additions);
+ }
+}
+
+/* Debug functions. */
+
+static void ATTRIBUTE_UNUSED
+debug_exit_insns (void)
+{
+ unsigned int i;
+ for (i = 0; i < EXIT_NUM; i++)
+ {
+ fprintf (stderr, "exit %d with prob %d: ",
+ i, VEC_index (int, exit_probs, i));
+ debug_insn_slim (EXIT_INSN (i));
+ fprintf (stderr, "\n");
+ }
+}
+
+static void ATTRIBUTE_UNUSED
+debug_path_lengths (basic_block bb)
+{
+ rtx insn;
+ unsigned int i;
+
+ for (insn = BB_HEAD (bb);
+ insn != NEXT_INSN (BB_END (bb));
+ insn = NEXT_INSN (insn))
+ {
+ if (!INSN_P (insn))
+ continue;
+
+ fprintf (stderr, "insn: ");
+ debug_insn_slim (insn);
+ fprintf (stderr, "; path lengths to exits [ ");
+ for (i = 0; i < EXIT_NUM; i++)
+ fprintf (stderr, "%d: %d; ", i, INSN_EXIT_LENGTH (insn, i));
+ fprintf (stderr, "]\n");
+ }
+}
+
+static void ATTRIBUTE_UNUSED
+debug_priorities (basic_block bb)
+{
+ rtx insn;
+
+ for (insn = BB_HEAD (bb);
+ insn != NEXT_INSN (BB_END (bb));
+ insn = NEXT_INSN (insn))
+ {
+ if (!INSN_P (insn))
+ continue;
+
+ fprintf (stderr, "insn: ");
+ debug_insn_slim (insn);
+ if (INSN_PRIORITY_KNOWN (insn))
+ fprintf (stderr, "; priority: %d\n", INSN_PRIORITY (insn));
+ else
+ fprintf (stderr, "; priority: ?\n");
+ }
+}
+
+static void ATTRIBUTE_UNUSED
+debug_priorities_n (int n)
+{
+ debug_priorities (BASIC_BLOCK (n));
+}
+
+static void ATTRIBUTE_UNUSED
+debug_path_lengths_n (int n)
+{
+ debug_path_lengths (BASIC_BLOCK (n));
+}
+
+static void ATTRIBUTE_UNUSED
+debug_priorities_bbs (VEC (basic_block, heap) *bbs)
+{
+ unsigned int i;
+ basic_block bb;
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ {
+ fprintf (stderr, "basic block %d:\n", bb->index);
+ debug_priorities (bb);
+ }
+}
+
+static void ATTRIBUTE_UNUSED
+debug_path_lengths_bbs (VEC (basic_block, heap) *bbs)
+{
+ unsigned int i;
+ basic_block bb;
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ {
+ fprintf (stderr, "basic block %d:\n", bb->index);
+ debug_path_lengths (bb);
+ }
+}
+
/* Initialize some global state for the scheduler. */
void
@@ -3324,7 +3904,7 @@
ds_t ts;
sd_iterator_def sd_it;
dep_t dep;
- rtx twins = NULL;
+ rtx twins = NULL, twins2;
rtx_vec_t priorities_roots;
ts = TODO_SPEC (insn);
@@ -3431,6 +4011,7 @@
}
}
+ twins2 = twins;
/* We couldn't have added the dependencies between INSN and TWINS earlier
because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
while (twins)
@@ -3447,11 +4028,36 @@
}
twin = XEXP (twins, 1);
- free_INSN_LIST_node (twins);
+
+ /* Otherwise we do it later. */
+ if (!use_spec_yield_priority)
+ free_INSN_LIST_node (twins);
twins = twin;
}
calc_priorities (priorities_roots);
+
+ if (use_spec_yield_priority)
+ {
+ /* Clear path lengths of instructions from recovery block as it would
+ be scheduled later. */
+ while (twins2)
+ {
+ rtx twin;
+ basic_block rec = BLOCK_FOR_INSN (XEXP (twins2, 0));
+
+ for (twin = bb_note (rec);
+ twin != NEXT_INSN (BB_END (rec));
+ twin = NEXT_INSN (twin))
+ if (INSN_P (twin))
+ clear_path_lengths (twin);
+
+ twin = XEXP (twins2, 1);
+
+ free_INSN_LIST_node (twins2);
+ twins2 = twin;
+ }
+ }
VEC_free (rtx, heap, priorities_roots);
}
@@ -3911,6 +4517,11 @@
{
init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
sd_add_dep (new_dep, false);
+ if (use_spec_yield_priority)
+ {
+ replace_exit_insns (insn, check);
+ check_exit_insns();
+ }
}
if (!mutate_p)
@@ -3920,6 +4531,11 @@
rtx_vec_t priorities_roots = NULL;
clear_priorities (twin, &priorities_roots);
+ if (use_spec_yield_priority)
+ {
+ find_path_length_to_exit_insns(check);
+ (void) priority (check);
+ }
calc_priorities (priorities_roots);
VEC_free (rtx, heap, priorities_roots);
}
@@ -4328,12 +4944,17 @@
if (contributes_to_priority_p (dep))
insn_is_root_p = false;
- INSN_PRIORITY_STATUS (pro) = -1;
+ if (use_spec_yield_priority)
+ clear_path_lengths (insn);
+ INSN_PRIORITY_STATUS (pro) = -1;
+
clear_priorities (pro, roots_ptr);
}
}
- if (insn_is_root_p)
+ if (insn_is_root_p
+ || use_g_star_priority
+ || use_spec_yield_priority)
VEC_safe_push (rtx, heap, *roots_ptr, insn);
}
@@ -4346,6 +4967,9 @@
int i;
rtx insn;
+ if (use_spec_yield_priority || use_g_star_priority)
+ check_exit_insns ();
+
for (i = 0; VEC_iterate (rtx, roots, i, insn); i++)
priority (insn);
}
@@ -4512,4 +5136,933 @@
}
#endif /* ENABLE_CHECKING */
+/* Data structures for calculation of priority using G* heurisitc and
+ estimation of execution time of set ofinstructions using Rim and Jain bound.
+ See functions g_star_priority and rim_jain_bound in haifa-sched.c. */
+
+/* Structure to represent one instruction of subproblem. */
+struct _subproblem_element
+{
+ /* Instruction itself. */
+ rtx insn;
+
+ /* "As Soon As Possible" attribute means the smallest cycle at which
+ instruction can be issued inside subproblem. */
+ int asap;
+
+ /* "As Late As Possible" attribute means the largest cycle at which
+ instruction can be issued without increasing maximal value of
+ ASAP attricute inside subproblem. */
+ int alap;
+
+ /* Vector of indexes of predecessors (successors) of instruction inside
+ subproblem. */
+ VEC (int, heap) *preds;
+ VEC (int, heap) *succs;
+
+ /* Vector of costs of dependencies between instruction and its predecessors
+ (successors) for each corresponding element of PREDS (SUCCS) vector. */
+ VEC (int, heap) *preds_cost;
+ VEC (int, heap) *succs_cost;
+};
+
+typedef struct _subproblem_element subproblem_element;
+typedef struct _subproblem_element *subproblem_element_p;
+
+DEF_VEC_O (subproblem_element);
+DEF_VEC_ALLOC_O (subproblem_element, heap);
+
+/* Structure to represent set of instructions inside scheduler with additional
+ data about instructions. */
+struct _subproblem_t
+{
+ /* Maximal value of ASAP attribute among all instructions of subproblem.
+ Equals to critical path value inside data dependence graph, composed of
+ all instructions of subproblem. */
+ int max_asap;
+
+ /* Mask of luids of instructions, which can belong to subproblem.*/
+ char *mask;
+ int mask_size;
+
+ /* Instructions of subproblem. */
+ VEC (subproblem_element, heap) *nodes;
+};
+typedef struct _subproblem_t *subproblem_t;
+
+/* Debug function. */
+static void ATTRIBUTE_UNUSED
+debug_subproblem (subproblem_t subproblem)
+{
+ subproblem_element_p cur_element_p;
+
+ if (VEC_length (subproblem_element, subproblem->nodes) > 0)
+ {
+ int i;
+
+ fprintf (stderr, "subproblem: %d elements {\n",
+ VEC_length (subproblem_element, subproblem->nodes));
+ for (i = 0;
+ VEC_iterate (subproblem_element, subproblem->nodes, i, cur_element_p);
+ i++)
+ {
+ int k, cur_index_p;
+ fprintf (stderr, "[%d]\t%d\t%d\t%d\t[", i,
+ INSN_UID (cur_element_p->insn),
+ cur_element_p->asap, cur_element_p->alap);
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->preds, k, cur_index_p);
+ k++)
+ {
+ fprintf (stderr, " %d(%d)", cur_index_p,
+ VEC_index (int, cur_element_p->preds_cost, k));
+ }
+ fprintf (stderr, " ] [");
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->succs, k, cur_index_p);
+ k++)
+ {
+ fprintf (stderr, " %d(%d)", cur_index_p,
+ VEC_index (int, cur_element_p->succs_cost, k));
+ }
+ fprintf (stderr, " ]\n");
+ }
+ fprintf (stderr, "} max_asap: %d;", subproblem->max_asap);
+ }
+ else
+ fprintf (stderr, "subproblem: empty {}\n");
+}
+
+/* Returns index of instruction INSN inside array SUBPROBLEM->NODES or minus
+ one if there is no INSN inside SUBPROBLEM. */
+static int
+find_insn_in_subproblem (subproblem_t subproblem, rtx insn)
+{
+ int i;
+ subproblem_element_p cur_element_p;
+
+ for (i = 0;
+ VEC_iterate (subproblem_element, subproblem->nodes, i, cur_element_p);
+ i++)
+ {
+ if (cur_element_p->insn == insn)
+ return i;
+ }
+
+ return -1;
+}
+
+/* Fills attributes of subproblem elements with default values. ASAP is the
+ minimum over predecessors of ASAP values of predecessor plus dependence
+ cost or zero in case of absent predecessors. ALAP is the maximum over all
+ successors of ALAP values of successor minus dependence cost or maximal
+ value of ASAP in subproblem in case of absent successors. */
+static void
+fill_subproblem_default (subproblem_t subproblem)
+{
+ int i;
+ subproblem_element_p cur_element_p;
+ VEC (int, heap) *stack
+ = VEC_alloc (int, heap, VEC_length (subproblem_element, subproblem->nodes));
+
+ /* Fill asap fields. */
+ for (i = VEC_length (subproblem_element, subproblem->nodes) - 1; i >= 0; i--)
+ {
+ gcc_assert (VEC_empty (int, stack));
+ VEC_safe_push (int, heap, stack, i);
+
+ while (!VEC_empty (int, stack))
+ {
+ int k = 0, cur_pred, max_asap = 0;
+ int cur_index = VEC_pop (int, stack);
+ cur_element_p
+ = VEC_index (subproblem_element, subproblem->nodes, cur_index);
+
+ if (cur_element_p->asap != -1)
+ continue;
+ else if (VEC_empty (int, cur_element_p->preds))
+ {
+ cur_element_p->asap = 0;
+ continue;
+ }
+ else
+ {
+ bool all_preds_ready = true;
+
+ VEC_safe_push (int, heap, stack, i);
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->preds, k, cur_pred);
+ k++)
+ {
+ if (VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_pred)->asap == -1)
+ {
+ VEC_safe_push (int, heap, stack, cur_pred);
+ all_preds_ready = false;
+ }
+ }
+
+ if (!all_preds_ready)
+ continue;
+ else
+ VEC_pop (int, stack);
+
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->preds, k, cur_pred);
+ k++)
+ {
+ int cur_value
+ = VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_pred)->asap
+ + VEC_index (int, cur_element_p->preds_cost, k);
+ gcc_assert (VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_pred)->asap != -1
+ && VEC_index (int,
+ cur_element_p->preds_cost,
+ k) >= 0);
+ max_asap = MAX (max_asap, cur_value);
+ }
+
+ cur_element_p->asap = max_asap;
+ }
+ }
+ }
+
+ for (i = 0;
+ VEC_iterate (subproblem_element, subproblem->nodes, i, cur_element_p);
+ i++)
+ subproblem->max_asap = MAX (subproblem->max_asap, cur_element_p->asap);
+
+ /* Find alap fields. */
+ for (i = 0; i < (int) VEC_length (subproblem_element, subproblem->nodes); i++)
+ {
+ gcc_assert (VEC_empty (int, stack));
+ VEC_safe_push (int, heap, stack, i);
+
+ while (!VEC_empty (int, stack))
+ {
+ int k = 0, cur_succ;
+ int cur_index = VEC_pop (int, stack);
+ cur_element_p = VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_index);
+
+ if (cur_element_p->alap != -1)
+ continue;
+ else if (VEC_empty (int, cur_element_p->succs))
+ {
+ cur_element_p->alap = subproblem->max_asap;
+ continue;
+ }
+ else
+ {
+ bool all_succs_ready = true;
+
+ VEC_safe_push (int, heap, stack, i);
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->succs, k, cur_succ);
+ k++)
+ {
+ if (VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_succ)->alap == -1)
+ {
+ VEC_safe_push (int, heap, stack, cur_succ);
+ all_succs_ready = false;
+ }
+ }
+
+ if (!all_succs_ready)
+ continue;
+ else
+ VEC_pop (int, stack);
+
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->succs, k, cur_succ);
+ k++)
+ {
+ int cur_value
+ = VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_succ)->alap
+ - VEC_index (int, cur_element_p->succs_cost, k);
+ gcc_assert (cur_value >= 0
+ && VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_succ)->alap != -1
+ && VEC_index (int,
+ cur_element_p->succs_cost,
+ k) >= 0);
+ }
+ }
+ }
+ }
+}
+
+/* Sets all values of attributes inside SUBPROBLEM to unknown status. */
+static void
+clear_subproblem_values (subproblem_t subproblem)
+{
+ int i;
+ subproblem_element_p cur_element_p;
+
+ for (i = 0;
+ VEC_iterate (subproblem_element,
+ subproblem->nodes,
+ i,
+ cur_element_p);
+ i++)
+ {
+ cur_element_p->alap = -1;
+ cur_element_p->asap = -1;
+ }
+
+ subproblem->max_asap = -1;
+}
+
+/* Adds new instruction ROOT and all its predecessors (if they are not inside
+ already) to SUBPROBLEM. Only instructions which luids are set in
+ MASK array are added. */
+static void
+add_root_to_subproblem (subproblem_t subproblem, rtx root, char *mask,
+ int mask_size)
+{
+ VEC (rtx, heap) *stack;
+
+ gcc_assert (subproblem->nodes && root && INSN_P (root));
+
+ stack = VEC_alloc (rtx, heap, 1);
+ VEC_safe_push (rtx, heap, stack, root);
+
+ while (!VEC_empty (rtx, stack))
+ {
+ rtx insn = VEC_pop (rtx, stack);
+ subproblem_element_p cur_element_p;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ if (find_insn_in_subproblem (subproblem, insn) != -1)
+ continue;
+
+ cur_element_p = XCNEWVEC (subproblem_element, 1);
+ cur_element_p->insn = insn;
+ cur_element_p->asap = -1;
+ cur_element_p->alap = -1;
+ cur_element_p->preds = VEC_alloc (int, heap, 1);
+ cur_element_p->succs = VEC_alloc (int, heap, 1);
+ cur_element_p->preds_cost = VEC_alloc (int, heap, 1);
+ cur_element_p->succs_cost = VEC_alloc (int, heap, 1);
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ rtx pro = DEP_PRO (dep);
+ int cost, index;
+
+ if (INSN_LUID (pro) > mask_size || !mask [INSN_LUID (pro)])
+ {
+ gcc_assert (find_insn_in_subproblem (subproblem, pro) == -1);
+ continue;
+ }
+
+ index = find_insn_in_subproblem (subproblem, pro);
+ if (index == -1)
+ {
+ VEC_safe_push (rtx, heap, stack, pro);
+ }
+ else
+ {
+ cost = dep_cost (dep);
+ VEC_safe_push (int, heap, cur_element_p->preds, index);
+ VEC_safe_push (int, heap, cur_element_p->preds_cost, cost);
+ VEC_safe_push (int, heap,
+ (VEC_index (subproblem_element,
+ subproblem->nodes,
+ index))->succs,
+ VEC_length (subproblem_element,
+ subproblem->nodes));
+ VEC_safe_push (int, heap,
+ (VEC_index (subproblem_element,
+ subproblem->nodes,
+ index))->succs_cost,
+ cost);
+ }
+ }
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ rtx con = DEP_CON (dep);
+ int cost, index;
+
+ if (INSN_LUID (con) > mask_size || !mask [INSN_LUID (con)])
+ {
+ gcc_assert (find_insn_in_subproblem (subproblem, con) == -1);
+ continue;
+ }
+
+ index = find_insn_in_subproblem (subproblem, con);
+ if (index != -1)
+ {
+ cost = dep_cost (dep);
+ VEC_safe_push (int, heap, cur_element_p->succs, index);
+ VEC_safe_push (int, heap, cur_element_p->succs_cost, cost);
+ VEC_safe_push (int, heap,
+ (VEC_index (subproblem_element,
+ subproblem->nodes,
+ index))->preds,
+ VEC_length (subproblem_element,
+ subproblem->nodes));
+ VEC_safe_push (int, heap,
+ (VEC_index (subproblem_element,
+ subproblem->nodes,
+ index))->preds_cost,
+ cost);
+ }
+ }
+
+ VEC_safe_push (subproblem_element, heap, subproblem->nodes, cur_element_p);
+ free (cur_element_p);
+ }
+
+ VEC_free (rtx, heap, stack);
+
+ clear_subproblem_values(subproblem);
+ fill_subproblem_default (subproblem);
+}
+
+/* Frees memory, allocated under subproblem. */
+static void
+delete_subproblem (subproblem_t subproblem)
+{
+ int i;
+ subproblem_element_p cur_element_p;
+
+ for (i = 0;
+ VEC_iterate (subproblem_element, subproblem->nodes, i, cur_element_p);
+ i++)
+ {
+ VEC_free (int, heap, cur_element_p->preds);
+ VEC_free (int, heap, cur_element_p->succs);
+ VEC_free (int, heap, cur_element_p->preds_cost);
+ VEC_free (int, heap, cur_element_p->succs_cost);
+ /*free (cur_element_p);*/
+ }
+ VEC_free (subproblem_element, heap, subproblem->nodes);
+ free (subproblem->mask);
+ free (subproblem);
+}
+
+/* Creates subproblem, including only instructions, which luids are set in
+ MASK array. */
+static subproblem_t
+create_subproblem_with_mask (rtx root, char *mask, int mask_size)
+{
+ subproblem_t new_problem;
+
+ new_problem = XNEWVEC (struct _subproblem_t, 1);
+ new_problem->mask_size = mask_size;
+ new_problem->mask = XCNEWVEC (char, new_problem->mask_size + 1);
+ memcpy (new_problem->mask, mask, mask_size + 1);
+ new_problem->nodes = VEC_alloc (subproblem_element, heap, 1);
+
+ add_root_to_subproblem (new_problem, root, mask, mask_size);
+
+ return new_problem;
+}
+
+/* Creates subproblem with full mask. */
+static subproblem_t ATTRIBUTE_UNUSED
+create_subproblem (rtx root)
+{
+ int mask_size = max_insn_luid;
+ char *all_mask = XCNEWVEC (char, mask_size + 1);
+ subproblem_t new_problem;
+
+ memset (all_mask, 1, mask_size + 1);
+ new_problem = create_subproblem_with_mask (root, all_mask, mask_size);
+ free (all_mask);
+
+ return new_problem;
+}
+
+static subproblem_t cur_subproblem = NULL;
+
+/* Chooses between two instructions one with lesser ASAP value or in case of
+ equal ASAP attribute values - with lesser ALAP. */
+static int
+rank_by_asap_and_alap (const void *ap, const void *bp)
+{
+ int a = *(int *)ap, b = *(int *)bp;
+ int asap_a, alap_a, asap_b, alap_b;
+
+ gcc_assert (cur_subproblem != NULL && cur_subproblem->nodes != NULL);
+ asap_a = VEC_index (subproblem_element, cur_subproblem->nodes, a)->asap;
+ alap_a = VEC_index (subproblem_element, cur_subproblem->nodes, a)->alap;
+ asap_b = VEC_index (subproblem_element, cur_subproblem->nodes, b)->asap;
+ alap_b = VEC_index (subproblem_element, cur_subproblem->nodes, b)->alap;
+
+ gcc_assert (asap_a != -1 && asap_b != -1 && alap_a != -1 && alap_b != -1);
+
+ if (asap_a > asap_b)
+ return 1;
+ else if (asap_a < asap_b)
+ return -1;
+
+ if (alap_a > alap_b)
+ return 1;
+ else if (alap_a < alap_b)
+ return -1;
+
+ return 0;
+}
+
+/* Returns true if all predecessors of instruction, corresponding to
+ CUR_ELEMENT_P were "scheduled" (indeed, modeled for scheduling in
+ rim_jain_bound). */
+static bool
+check_all_preds_scheduled (subproblem_element_p cur_element_p,
+ int *scheduled, int *insns, int size)
+{
+ bool found;
+ int i, j, cur_pred;
+
+ for (i = 0;
+ VEC_iterate (int, cur_element_p->preds, i, cur_pred);
+ i++)
+ {
+ found = false;
+ for (j = 0; j < size; j++)
+ if (cur_pred == insns[j])
+ {
+ gcc_assert (found == false);
+ found = true;
+ if (!scheduled[j])
+ return false;
+ }
+ gcc_assert (found == true);
+ }
+
+ return true;
+}
+
+/* Returns estimation of execution time of set of instructions given by
+ SUBPROBLEM with consideration of dependencies and processor
+ resources. The whole algorithm is described in article "Lower-bound
+ performance estimation for the high-level synthesis scheduling
+ problem" by M.Rim and R.Jain. The main idea of the algorithm is to
+ discard dependencies and try to model scheduling instructions in
+ special order. The order is given by increasing values of ALAP attributes of
+ instructions. Each instruction is then "scheduled" in the earliest cycle
+ that the processor resources permit and if current modeled processor cycle
+ is not lesser than its ASAP attribute value. After all instructions are
+ "scheduled" the maximal difference between the modelled scheduling cycle of
+ instruction and its ALAP attricute value is computed. This difference
+ represents lag between latest cycle that instruction can be scheduled
+ (to avoid delay of the whole schedule) and cycle on which it can be
+ scheduled when resources permit. Adding this lag to critical path value
+ of subproblem one can get a rough estimation of number of cycles that
+ subproblem needs to be computed. This inplementation has a drawback that
+ it is not a lower-boundm but only an estimation. In original article it
+ seems that processor description is made in form of table reservation.
+ As in GCC there is an automata processor description, on some processors
+ with vital instruction ordering inside one cycle, that has complex
+ corresponding automaton, sometimes it is possible that this function
+ returns value, greater than actual length of optimal schedule for
+ subproblem. Though it can serve as estimator of time for subproblem
+ to be executed. */
+static int
+rim_jain_bound (subproblem_t subproblem)
+{
+ int *insns_by_dh, *scheduled_array;
+ int i, j, sched_more, max_gap = 0,
+ subproblem_size = VEC_length (subproblem_element, subproblem->nodes);
+ int cur_cycle = 0, cur_thresh = 0, best = -1;
+ bool scheduled = false;
+ state_t cur_state = xmalloc (dfa_state_size),
+ tmp_state = xmalloc (dfa_state_size);
+ rtx cur_insn;
+
+ insns_by_dh = XCNEWVEC (int, subproblem_size);
+ scheduled_array = XCNEWVEC (int, subproblem_size);
+
+ for (i = 0; i < subproblem_size; i++)
+ insns_by_dh[i] = i;
+
+ /* All instructions from subproblem are ordered first by their ASAP and then
+ by ALAP attribute values. Then it is possible to easily distinguish
+ which instructions can be executed on current modelled cycle and which of
+ them are more prioritized. */
+ cur_subproblem = subproblem;
+ qsort (insns_by_dh, subproblem_size, sizeof (int), rank_by_asap_and_alap);
+ cur_subproblem = NULL;
+
+ sched_more = subproblem_size;
+ state_reset (cur_state);
+
+ while (sched_more)
+ {
+ scheduled = false;
+ best = -1;
+
+ /* CUR_THRESH marks first instruction from the order that has not been
+ "scheduled" yet. */
+ for (j = cur_thresh; j < subproblem_size; j++)
+ {
+ subproblem_element_p cur_element_p
+ = VEC_index (subproblem_element, subproblem->nodes, insns_by_dh[j]);
+ cur_insn = cur_element_p->insn;
+
+ gcc_assert (cur_element_p->asap != -1 && cur_element_p->alap != -1);
+ if (cur_element_p->asap > cur_cycle)
+ {
+ /* No ready insn that can be computed on this cycle. */
+ break;
+ }
+
+ /* If this insn was already scheduled. */
+ if (scheduled_array[j])
+ continue;
+
+ /* Questionable check. It seems like Rim and Jain ignore dependencies
+ and this check is wrong, though without it estimation is not so
+ tight in many cases. */
+ if (!check_all_preds_scheduled (cur_element_p, scheduled_array,
+ insns_by_dh, subproblem_size))
+ continue;
+
+ /* Try issue this insn on this cycle. */
+ memcpy (tmp_state, cur_state, dfa_state_size);
+ if (recog_memoized (cur_insn) < 0
+ || state_transition (cur_state, cur_insn) < 0)
+ {
+ /* Insn can be scheduled on this cycle. */
+ if (best == -1
+ || cur_element_p->alap
+ < VEC_index (subproblem_element,
+ subproblem->nodes,
+ insns_by_dh[best])->alap)
+ {
+ scheduled = true;
+ best = j;
+ }
+ }
+
+ /* Undo state change. */
+ memcpy (cur_state, tmp_state, dfa_state_size);
+ }
+
+ if (scheduled)
+ {
+ subproblem_element_p best_element_p
+ = VEC_index (subproblem_element,
+ subproblem->nodes,
+ insns_by_dh[best]);
+
+ /* Change state, modelling execution of BEST instruction. */
+ gcc_assert (scheduled_array[best] == 0);
+ scheduled_array[best] = 1;
+
+ if (best_element_p->insn
+ && recog_memoized (best_element_p->insn) > 0)
+ state_transition (cur_state, best_element_p->insn);
+
+ /* New gap found! */
+ max_gap = MAX (max_gap, cur_cycle - best_element_p->alap);
+
+ if (best == cur_thresh)
+ for (; best < subproblem_size; best++)
+ {
+ if (scheduled_array[best])
+ cur_thresh++;
+ else
+ break;
+ }
+ sched_more--;
+ }
+ else
+ {
+ /* Avancing cycle. */
+ if (targetm.sched.dfa_pre_cycle_insn)
+ state_transition (cur_state,
+ targetm.sched.dfa_pre_cycle_insn ());
+
+ state_transition (cur_state, NULL);
+
+ if (targetm.sched.dfa_post_cycle_insn)
+ state_transition (cur_state,
+ targetm.sched.dfa_post_cycle_insn ());
+
+ cur_cycle++;
+ }
+ }
+
+ free (insns_by_dh);
+ free (scheduled_array);
+ free (cur_state);
+ free (tmp_state);
+
+ return max_gap + subproblem->max_asap;
+}
+
+/* Compute rank for subproblem. See comment in FIND_G_STAR. */
+static int
+get_rank_for_subproblem (subproblem_t subproblem)
+{
+ unsigned int i, e, w = 0, t;
+
+ for (e = 0; e < EXIT_NUM; e++)
+ {
+ rtx exit = EXIT_INSN (e);
+ bool inside = false;
+ subproblem_element_p el;
+
+ for (i = 0; VEC_iterate (subproblem_element, subproblem->nodes, i, el);i ++)
+ {
+ if (el->insn == exit)
+ {
+ inside = true;
+ break;
+ }
+ }
+
+ if (inside)
+ {
+ w += EXIT_PROB (e);
+ }
+ }
+ if (w == 0)
+ return INT_MAX;
+ /* T is an estimation of time of executing of all instructions of
+ SUBPROBLEM. The most simple estimation is critical path value of
+ dependence graph, which can be constructed from those instructions.
+ Unfortunately, it does not take available processor resources into
+ account and hence imprecise. More tight estimation is achieved by using
+ procedure, described by Rim and Jain (see comment before rim_jain_bound
+ function). Unfortunately, it is more complex and hence needs more
+ computations. */
+ if (flag_sched_g_star_use_rjbound)
+ t = rim_jain_bound (subproblem);
+ else
+ t = subproblem->max_asap;
+ return (t * REG_BR_PROB_BASE) / w;
+}
+
+/* Finds G* subgraph among marked instructions. See article "Profile-Driven
+ Instruction Level Parallel Scheduling with Application to Super Blocks" by
+ C.Chekuri, R.Johnson, R.Motwani, B.Natarajan, B.R.Rau and M.Schlansker for
+ complete explanation. In several words, G* is a precedence-closed
+ (i.e. along an instruction, it includes all its predecessors) subgraph
+ with minimal rank, where rank is calculated as estimation of execution
+ time of this subgraph divided by sum of probabilities of exits
+ belonging to subgraph. */
+static subproblem_t
+find_g_star (sbitmap exits_marked, char *mask, int mask_size)
+{
+ unsigned int i, min_rank_index = EXIT_NUM;
+ int *rank = XCNEWVEC (int, EXIT_NUM);
+ subproblem_t *subproblems = XCNEWVEC (subproblem_t, EXIT_NUM);
+ subproblem_t g_star;
+ sbitmap_iterator sbi;
+
+ EXECUTE_IF_SET_IN_SBITMAP (exits_marked, 0, i, sbi)
+ {
+ subproblems[i] = create_subproblem_with_mask (EXIT_INSN (i),
+ mask, mask_size);
+ rank[i] = get_rank_for_subproblem (subproblems[i]);
+ /* Choose earliset exit with minimal rank - as exits are recorded
+ beginning from the last, it has the biggest number among exits with
+ minimal rank. */
+ if (min_rank_index == EXIT_NUM)
+ min_rank_index = i;
+ else if (rank[i] <= rank[min_rank_index])
+ {
+ delete_subproblem (subproblems[min_rank_index]);
+ min_rank_index = i;
+ }
+ else
+ delete_subproblem (subproblems[i]);
+ }
+
+ gcc_assert (min_rank_index < EXIT_NUM);
+
+ g_star = subproblems[min_rank_index];
+
+ free (rank);
+ free (subproblems);
+ return g_star;
+}
+
+/* Unmark instructions from G_STAR. */
+static void
+unmark (subproblem_t g_star, char *mask, int mask_size)
+{
+ unsigned int i;
+ subproblem_element_p el;
+
+ for (i = 0; VEC_iterate (subproblem_element, g_star->nodes, i, el);i ++)
+ {
+ gcc_assert (INSN_LUID (el->insn) <= mask_size);
+ mask[INSN_LUID (el->insn)] = 0;
+ }
+}
+
+/* Process instructions from G*. */
+static void
+set_basket (int basket, subproblem_t g_star, sbitmap exits_scheduled)
+{
+ unsigned int i;
+ subproblem_element_p el;
+
+ /* Set basket for all instructions from G_STAR subproblem. */
+ for (i = 0; VEC_iterate (subproblem_element, g_star->nodes, i, el);i ++)
+ {
+ gcc_assert (g_star_distribution[INSN_LUID (el->insn)] == 0);
+ g_star_distribution[INSN_LUID (el->insn)] = basket;
+ }
+
+ /* Unmark exits from G*. */
+ for (i = 0; i < EXIT_NUM; i++)
+ {
+ if (find_insn_in_subproblem (g_star, EXIT_INSN (i)) != -1)
+ {
+ gcc_assert (TEST_BIT (exits_scheduled, i));
+ RESET_BIT (exits_scheduled, i);
+ }
+ }
+}
+
+/* Sorts all instructions from current scheduling domain into "baskets",
+ according to G* heuristic. In several words, basket is a group of
+ instructions with priority greater than of instructions from next
+ basket and lesser than of instructions from previous basket. G*
+ heuristic itself is following:
+
+ I) Mark all instructions.
+ II) While marked exits left do:
+ 1) Find G* subgraph in DDG.
+ 2) Put instructions of G* into new basket.
+ 3) Unmark instructions from G*.*/
+static void
+create_g_distribution (void)
+{
+ int basket = 0, mask_size = max_insn_luid, addition;
+ char *mask = XCNEWVEC (char, mask_size + 1);
+ sbitmap exits_marked;
+
+ exits_marked = sbitmap_alloc (EXIT_NUM);
+ sbitmap_ones (exits_marked);
+ /* Mark all instructions in scheduling domain. */
+ memset (mask, 1, mask_size + 1);
+
+ while (sbitmap_first_set_bit (exits_marked) != -1)
+ {
+ subproblem_t g_star;
+
+ addition = basket == 0 ? 0 : additions[basket - 1];
+ g_star = find_g_star (exits_marked, mask, mask_size);
+ /* Set initially ADDITIONS to be equal ADDITIONS of previous basket plus
+ critical path value of instructions from G* and zero for the first
+ basket. */
+ additions[basket] = addition + g_star->max_asap + 1;
+ set_basket (basket, g_star, exits_marked);
+ unmark (g_star, mask, mask_size);
+ delete_subproblem (g_star);
+ basket++;
+ }
+
+ /* Revert additions so that instructions from first basket recieve the
+ biggest addition. */
+ addition = additions[basket - 1];
+ for (basket--; basket >= 0; basket--)
+ additions[basket] = addition - additions[basket];
+
+ sbitmap_free (exits_marked);
+ free (mask);
+}
+
+/* Finds a basket for INSN. If basket was chosen at the beginning of
+ scheduling - return it's number. If INSN was created during scheduling
+ - choose basket with maximal number among baskets of predecessors (not
+ necessarily direct). */
+static int find_basket (rtx insn)
+{
+ rtx next;
+ int basket = -1;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ if (INSN_LUID (insn) <= max_insn_luid)
+ return g_star_distribution[INSN_LUID (insn)];
+
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
+ {
+ next = DEP_PRO (dep);
+
+ if (INSN_LUID (next) <= max_insn_luid)
+ {
+ if (basket == -1 || basket < g_star_distribution[INSN_LUID (next)])
+ basket = g_star_distribution[INSN_LUID (next)];
+ }
+ }
+ FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
+ {
+ next = DEP_PRO (dep);
+
+ if (INSN_LUID (next) <= max_insn_luid)
+ {
+ if (basket == -1 || basket < g_star_distribution[INSN_LUID (next)])
+ basket = g_star_distribution[INSN_LUID (next)];
+ }
+ }
+
+ gcc_assert (basket != -1);
+ return basket;
+}
+
+/* Calculate priority of INSN using G* heuristic with critical path heuristic
+ as secondary. Basic idea is that all instructions are distributed into
+ baskets - subsets of instructions with the property that instructions
+ from each next basket should be less prioritized than all instructions
+ from previous basket. Inside basket instructions are ordered based on
+ their critical path value. */
+static int
+g_star_priority (rtx insn)
+{
+ int basket = -1, this_priority = -1;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ basket = find_basket (insn);
+
+ gcc_assert (basket != -1);
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ rtx next;
+ int next_priority, cost;
+
+ next = DEP_CON (dep);
+
+ /* Consider instructions only from current basket. */
+ if (find_basket (next) != basket)
+ continue;
+
+ cost = dep_cost (dep);
+ next_priority = cost + priority (next) - additions[basket];
+
+ if (next_priority > this_priority)
+ this_priority = next_priority;
+ }
+
+ /* If no forward dependent instructions from same basket. */
+ if (this_priority == -1)
+ this_priority = insn_cost (insn);
+
+ /* Apply increasing of priority depending of instruction's basket. */
+ this_priority += additions[basket];
+ return this_priority;
+}
+
#endif /* INSN_SCHEDULING */
=== gcc/sched-ebb.c
==================================================================
--- gcc/sched-ebb.c (revision 30596)
+++ gcc/sched-ebb.c (local)
@@ -446,6 +446,7 @@
static basic_block
schedule_ebb (rtx head, rtx tail)
{
+ VEC (basic_block, heap) *bbs;
basic_block first_bb, target_bb;
struct deps tmp_deps;
@@ -480,7 +481,24 @@
/* Set priorities. */
current_sched_info->sched_max_insns_priority = 0;
- n_insns = set_priorities (head, tail);
+ if (flag_sched_spec_yield || flag_sched_g_star)
+ {
+ basic_block cur_bb;
+
+ bbs = VEC_alloc (basic_block, heap, 1);
+ /* Push blocks of current EBB into BBS in topological order. */
+ for (cur_bb = first_bb;
+ cur_bb != last_bb->next_bb;
+ cur_bb = cur_bb->next_bb)
+ {
+ VEC_safe_push (basic_block, heap, bbs, cur_bb);
+ }
+ n_insns = set_priorities_for_bbs (bbs);
+ VEC_free (basic_block, heap, bbs);
+ }
+ else
+ n_insns = set_priorities (head, tail);
+
current_sched_info->sched_max_insns_priority++;
current_sched_info->prev_head = PREV_INSN (head);
@@ -513,6 +531,9 @@
target_bb = first_bb;
schedule_block (&target_bb, n_insns);
+ if (flag_sched_spec_yield || flag_sched_g_star)
+ finish_priorities ();
+
/* We might pack all instructions into fewer blocks,
so we may made some of them empty. Can't assert (b == last_bb). */
=== gcc/sched-int.h
==================================================================
--- gcc/sched-int.h (revision 30596)
+++ gcc/sched-int.h (local)
@@ -29,6 +29,7 @@
/* For reg_note. */
#include "rtl.h"
#include "df.h"
+#include "vecprim.h"
/* Pointer to data describing the current DFA state. */
extern state_t curr_state;
@@ -487,6 +488,9 @@
/* A priority for each insn. */
int priority;
+ /* Array of critical path lengths to exit instructions. */
+ VEC (int, heap) *exit_length;
+
/* Number of instructions referring to this insn. */
int ref_count;
@@ -562,6 +566,8 @@
#define CHECK_SPEC(INSN) (h_i_d[INSN_UID (INSN)].check_spec)
#define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block)
#define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat)
+#define INSN_EXIT_LENGTHS(INSN) (h_i_d[INSN_UID (INSN)].exit_length)
+#define INSN_EXIT_LENGTH(INSN,I) (VEC_index (int, INSN_EXIT_LENGTHS (INSN), I))
/* INSN is either a simple or a branchy speculation check. */
#define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
@@ -849,6 +855,8 @@
extern void unlink_bb_notes (basic_block, basic_block);
extern void add_block (basic_block, basic_block);
extern rtx bb_note (basic_block);
+extern int set_priorities_for_bbs (VEC (basic_block, heap) *);
+extern void finish_priorities (void);
/* Functions in sched-rgn.c. */
=== gcc/sched-rgn.c
==================================================================
--- gcc/sched-rgn.c (revision 30596)
+++ gcc/sched-rgn.c (local)
@@ -2699,15 +2699,32 @@
/* Set priorities. */
current_sched_info->sched_max_insns_priority = 0;
- for (bb = 0; bb < current_nr_blocks; bb++)
+ if (flag_sched_spec_yield)
{
- rtx head, tail;
-
- gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
- get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
+ VEC (basic_block, heap) *bbs
+ = VEC_alloc (basic_block, heap, current_nr_blocks);
- rgn_n_insns += set_priorities (head, tail);
+ /* Push blocks of current region into BBS in topological order. */
+ for (bb = 0; bb < current_nr_blocks; bb++)
+ {
+ VEC_safe_push (basic_block, heap, bbs, EBB_FIRST_BB (bb));
+ }
+ rgn_n_insns = set_priorities_for_bbs (bbs);
+ VEC_free (basic_block, heap, bbs);
}
+ else
+ {
+ for (bb = 0; bb < current_nr_blocks; bb++)
+ {
+ rtx head, tail;
+
+ gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
+ get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb),
+ &head, &tail);
+
+ rgn_n_insns += set_priorities (head, tail);
+ }
+ }
current_sched_info->sched_max_insns_priority++;
/* Compute interblock info: probabilities, split-edges, dominators, etc. */
@@ -2838,6 +2855,8 @@
gcc_assert (sched_rgn_n_insns == rgn_n_insns);
/* Done with this region. */
+ if (flag_sched_spec_yield)
+ finish_priorities ();
if (current_nr_blocks > 1)
{
-------------- next part --------------
--- ./gcc/common.opt 2007-08-24 16:21:13.000000000 +0400
+++ ../gsoc-final/gcc/common.opt 2007-08-21 19:12:46.000000000 +0400
@@ -860,6 +860,18 @@ fsched2-use-superblocks
Common Report Var(flag_sched2_use_superblocks) Optimization
If scheduling post reload, do superblock scheduling
+fsched-spec-yield
+Common Report Var(flag_sched_spec_yield) Init(1)
+Use speculative yield heuristic for priority
+
+fsched-g-star
+Common Report Var(flag_sched_g_star) Init(1)
+Use G* heuristic for priority
+
+fsched-g-star-use-rjbound
+Common Report Var(flag_sched_g_star_use_rjbound) Init(1)
+Use Rim and Jain estimation of execution time while using G* priority
+
fsched2-use-traces
Common Report Var(flag_sched2_use_traces) Optimization
If scheduling post reload, do trace scheduling
-------------- next part --------------
*** ./gcc/sched-ebb.c 2007-08-24 16:21:25.000000000 +0400
--- ../gsoc-final/gcc/sched-ebb.c 2007-08-23 13:47:17.000000000 +0400
*************** add_deps_for_risky_insns (rtx head, rtx
*** 446,451 ****
--- 446,452 ----
static basic_block
schedule_ebb (rtx head, rtx tail)
{
+ VEC (basic_block, heap) *bbs;
basic_block first_bb, target_bb;
struct deps tmp_deps;
*************** schedule_ebb (rtx head, rtx tail)
*** 480,486 ****
/* Set priorities. */
current_sched_info->sched_max_insns_priority = 0;
! n_insns = set_priorities (head, tail);
current_sched_info->sched_max_insns_priority++;
current_sched_info->prev_head = PREV_INSN (head);
--- 481,504 ----
/* Set priorities. */
current_sched_info->sched_max_insns_priority = 0;
! if (flag_sched_spec_yield || flag_sched_g_star)
! {
! basic_block cur_bb;
!
! bbs = VEC_alloc (basic_block, heap, 1);
! /* Push blocks of current EBB into BBS in topological order. */
! for (cur_bb = first_bb;
! cur_bb != last_bb->next_bb;
! cur_bb = cur_bb->next_bb)
! {
! VEC_safe_push (basic_block, heap, bbs, cur_bb);
! }
! n_insns = set_priorities_for_bbs (bbs);
! VEC_free (basic_block, heap, bbs);
! }
! else
! n_insns = set_priorities (head, tail);
!
current_sched_info->sched_max_insns_priority++;
current_sched_info->prev_head = PREV_INSN (head);
*************** schedule_ebb (rtx head, rtx tail)
*** 513,518 ****
--- 531,539 ----
target_bb = first_bb;
schedule_block (&target_bb, n_insns);
+ if (flag_sched_spec_yield || flag_sched_g_star)
+ finish_priorities ();
+
/* We might pack all instructions into fewer blocks,
so we may made some of them empty. Can't assert (b == last_bb). */
-------------- next part --------------
*** ./gcc/sched-rgn.c 2007-08-24 16:21:38.000000000 +0400
--- ../gsoc-final/gcc/sched-rgn.c 2007-08-23 13:38:34.000000000 +0400
*************** schedule_region (int rgn)
*** 2699,2712 ****
/* Set priorities. */
current_sched_info->sched_max_insns_priority = 0;
! for (bb = 0; bb < current_nr_blocks; bb++)
{
! rtx head, tail;
!
! gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
! get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
! rgn_n_insns += set_priorities (head, tail);
}
current_sched_info->sched_max_insns_priority++;
--- 2699,2729 ----
/* Set priorities. */
current_sched_info->sched_max_insns_priority = 0;
! if (flag_sched_spec_yield)
{
! VEC (basic_block, heap) *bbs
! = VEC_alloc (basic_block, heap, current_nr_blocks);
! /* Push blocks of current region into BBS in topological order. */
! for (bb = 0; bb < current_nr_blocks; bb++)
! {
! VEC_safe_push (basic_block, heap, bbs, EBB_FIRST_BB (bb));
! }
! rgn_n_insns = set_priorities_for_bbs (bbs);
! VEC_free (basic_block, heap, bbs);
! }
! else
! {
! for (bb = 0; bb < current_nr_blocks; bb++)
! {
! rtx head, tail;
!
! gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
! get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb),
! &head, &tail);
!
! rgn_n_insns += set_priorities (head, tail);
! }
}
current_sched_info->sched_max_insns_priority++;
*************** schedule_region (int rgn)
*** 2838,2843 ****
--- 2855,2862 ----
gcc_assert (sched_rgn_n_insns == rgn_n_insns);
/* Done with this region. */
+ if (flag_sched_spec_yield)
+ finish_priorities ();
if (current_nr_blocks > 1)
{
-------------- next part --------------
--- ./gcc/sched-int.h 2007-08-24 16:21:31.000000000 +0400
+++ ../gsoc-final/gcc/sched-int.h 2007-08-23 13:30:10.000000000 +0400
@@ -29,6 +29,7 @@ along with GCC; see the file COPYING3.
/* For reg_note. */
#include "rtl.h"
#include "df.h"
+#include "vecprim.h"
/* Pointer to data describing the current DFA state. */
extern state_t curr_state;
@@ -487,6 +488,9 @@ struct haifa_insn_data
/* A priority for each insn. */
int priority;
+ /* Array of critical path lengths to exit instructions. */
+ VEC (int, heap) *exit_length;
+
/* Number of instructions referring to this insn. */
int ref_count;
@@ -562,6 +566,8 @@ extern struct haifa_insn_data *h_i_d;
#define CHECK_SPEC(INSN) (h_i_d[INSN_UID (INSN)].check_spec)
#define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block)
#define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat)
+#define INSN_EXIT_LENGTHS(INSN) (h_i_d[INSN_UID (INSN)].exit_length)
+#define INSN_EXIT_LENGTH(INSN,I) (VEC_index (int, INSN_EXIT_LENGTHS (INSN), I))
/* INSN is either a simple or a branchy speculation check. */
#define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
@@ -849,6 +855,8 @@ extern bool sched_insn_is_legitimate_for
extern void unlink_bb_notes (basic_block, basic_block);
extern void add_block (basic_block, basic_block);
extern rtx bb_note (basic_block);
+extern int set_priorities_for_bbs (VEC (basic_block, heap) *);
+extern void finish_priorities (void);
/* Functions in sched-rgn.c. */
-------------- next part --------------
*** ./gcc/haifa-sched.c 2007-08-24 16:46:11.000000000 +0400
--- ../gsoc-final/gcc/haifa-sched.c 2007-08-23 18:44:52.000000000 +0400
*************** contributes_to_priority_p (dep_t dep)
*** 731,736 ****
--- 755,762 ----
static int
priority (rtx insn)
{
+ int this_priority = 0;
+
if (! INSN_P (insn))
return 0;
*************** priority (rtx insn)
*** 739,816 ****
if (!INSN_PRIORITY_KNOWN (insn))
{
! int this_priority = 0;
! if (sd_lists_empty_p (insn, SD_LIST_FORW))
! /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
! some forward deps but all of them are ignored by
! contributes_to_priority hook. At the moment we set priority of
! such insn to 0. */
! this_priority = insn_cost (insn);
! else
! {
! rtx prev_first, twin;
! basic_block rec;
! /* For recovery check instructions we calculate priority slightly
! different than that of normal instructions. Instead of walking
! through INSN_FORW_DEPS (check) list, we walk through
! INSN_FORW_DEPS list of each instruction in the corresponding
! recovery block. */
! rec = RECOVERY_BLOCK (insn);
! if (!rec || rec == EXIT_BLOCK_PTR)
! {
! prev_first = PREV_INSN (insn);
! twin = insn;
! }
! else
! {
! prev_first = NEXT_INSN (BB_HEAD (rec));
! twin = PREV_INSN (BB_END (rec));
! }
! do
! {
! sd_iterator_def sd_it;
! dep_t dep;
! FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
! {
! rtx next;
! int next_priority;
! next = DEP_CON (dep);
! if (BLOCK_FOR_INSN (next) != rec)
! {
! int cost;
! if (!contributes_to_priority_p (dep))
! continue;
! if (twin == insn)
! cost = dep_cost (dep);
! else
! {
! struct _dep _dep1, *dep1 = &_dep1;
! init_dep (dep1, insn, next, REG_DEP_ANTI);
! cost = dep_cost (dep1);
! }
! next_priority = cost + priority (next);
! if (next_priority > this_priority)
! this_priority = next_priority;
! }
! }
!
! twin = PREV_INSN (twin);
! }
! while (twin != prev_first);
! }
INSN_PRIORITY (insn) = this_priority;
INSN_PRIORITY_STATUS (insn) = 1;
}
--- 765,872 ----
if (!INSN_PRIORITY_KNOWN (insn))
{
! if (use_g_star_priority)
! {
! insn_cost (insn);
! this_priority = g_star_priority (insn);
! gcc_assert (this_priority >= 0);
! }
! else if (use_spec_yield_priority)
! {
! unsigned int i;
! gcc_assert (VEC_length (rtx, exit_insns)
! == VEC_length (int, exit_probs));
! insn_cost (insn);
! /* Compute path lengths to all exits for INSN. */
! find_path_length_to_exit_insns (insn);
! gcc_assert (VEC_length (int, INSN_EXIT_LENGTHS (insn)) == EXIT_NUM);
! /* Calculate priority as sum over all exits of products of critical
! path length from instruction INSN to exit and probability of
! taking the exit. */
! for (i = 0; i < EXIT_NUM; i++)
! {
! if (INSN_EXIT_LENGTH (insn, i) >= 0)
! this_priority += (INSN_EXIT_LENGTH (insn, i) + 1)
! * EXIT_PROB(i);
! }
! gcc_assert (this_priority >= 0);
! }
! else /* !use_spec_yield_priority && !use_g_star_priority */
! {
! if (sd_lists_empty_p (insn, SD_LIST_FORW))
! /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
! some forward deps but all of them are ignored by
! contributes_to_priority hook. At the moment we set priority of
! such insn to 0. */
! this_priority = insn_cost (insn);
! else
! {
! rtx prev_first, twin;
! basic_block rec;
! /* For recovery check instructions we calculate priority slightly
! different than that of normal instructions. Instead of walking
! through INSN_FORW_DEPS (check) list, we walk through
! INSN_FORW_DEPS list of each instruction in the corresponding
! recovery block. */
! rec = RECOVERY_BLOCK (insn);
! if (!rec || rec == EXIT_BLOCK_PTR)
! {
! prev_first = PREV_INSN (insn);
! twin = insn;
! }
! else
! {
! prev_first = NEXT_INSN (BB_HEAD (rec));
! twin = PREV_INSN (BB_END (rec));
! }
! do
! {
! sd_iterator_def sd_it;
! dep_t dep;
! FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
! {
! rtx next;
! int next_priority;
! next = DEP_CON (dep);
! if (BLOCK_FOR_INSN (next) != rec)
! {
! int cost;
! if (!contributes_to_priority_p (dep))
! continue;
! if (twin == insn)
! cost = dep_cost (dep);
! else
! {
! struct _dep _dep1, *dep1 = &_dep1;
! init_dep (dep1, insn, next, REG_DEP_ANTI);
! cost = dep_cost (dep1);
! }
!
! next_priority = cost + priority (next);
!
! if (next_priority > this_priority)
! this_priority = next_priority;
! }
! }
!
! twin = PREV_INSN (twin);
! }
! while (twin != prev_first);
! }
! }
INSN_PRIORITY (insn) = this_priority;
INSN_PRIORITY_STATUS (insn) = 1;
}
-------------- next part --------------
--- ./gcc/haifa-sched.c 2007-08-24 16:46:11.000000000 +0400
+++ ../gsoc-final/gcc/haifa-sched.c 2007-08-23 18:44:52.000000000 +0400
@@ -504,6 +504,9 @@ static void find_insn_reg_weight (basic_
static void find_insn_reg_weight1 (rtx);
static void adjust_priority (rtx);
static void advance_one_cycle (void);
+static int g_star_priority (rtx);
+static void create_g_distribution (void);
+static void free_exit_lengths (rtx insn);
/* Notes handling mechanism:
=========================
@@ -704,10 +707,31 @@ dep_cost (dep_t link)
return cost;
}
+/* Flags marking if G* r speculative yield heuristics should be used. */
+static bool use_g_star_priority, use_spec_yield_priority;
+/* Vector that holds exit instructions from current scheduling domain. */
+VEC (rtx, heap) *exit_insns;
+#define EXIT_INSN(I) VEC_index (rtx, exit_insns, I)
+/* Vector that holds probability of taking corresponding exit. */
+VEC (int, heap) *exit_probs;
+#define EXIT_PROB(I) VEC_index (int, exit_probs, I)
+static void find_path_length_to_exit_insns (rtx);
+/* Number of exits. */
+#define EXIT_NUM VEC_length (rtx, exit_insns)
+/* Vector of distribution of instructions of scheduling domain over baskets. */
+static int *g_star_distribution;
+/* Gaps of priority between baskets. */
+static int *additions;
+/* Maximal instruction luid at the beginning of scheduling. */
+static int max_insn_luid;
+
/* Return 'true' if DEP should be included in priority calculations. */
static bool
contributes_to_priority_p (dep_t dep)
{
+ if (use_spec_yield_priority || use_g_star_priority)
+ return true;
+
/* Critical path is meaningful in block boundaries only. */
if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
DEP_PRO (dep)))
@@ -2544,6 +2600,16 @@ schedule_block (basic_block *target_bb,
fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
}
+ if (use_spec_yield_priority)
+ {
+ rtx insn;
+ for (insn = last_scheduled_insn;
+ insn != prev_head;
+ insn = PREV_INSN (insn))
+ if (INSN_P (insn) && INSN_EXIT_LENGTHS (insn) != NULL)
+ free_exit_lengths (insn);
+ }
+
if (targetm.sched.md_finish)
{
targetm.sched.md_finish (sched_dump, sched_verbose);
@@ -2615,6 +2681,8 @@ set_priorities (rtx head, rtx tail)
if (head == tail && (! INSN_P (head)))
return 0;
+ use_spec_yield_priority = false;
+ use_g_star_priority = false;
n_insn = 0;
@@ -2638,9 +2706,521 @@ set_priorities (rtx head, rtx tail)
return n_insn;
}
+/* Returns an index of BB inside BBS (greater than BEGIN) or length of BBS
+ if it BB does not belong to BBS vector. */
+
+static inline unsigned int
+find_bb_in_bbs (basic_block bb, VEC (basic_block, heap) *bbs,
+ unsigned int begin)
+{
+ for (; begin < VEC_length (basic_block, bbs); begin++)
+ if (VEC_index (basic_block, bbs, begin) == bb)
+ break;
+
+ return begin;
+}
+
+static int
+sum_of_edge_probabilities (VEC(edge,gc) *vec)
+{
+ edge e;
+ edge_iterator ei;
+ int sum = 0;
+
+ FOR_EACH_EDGE (e, ei, vec)
+ sum += e->probability;
+
+ return sum;
+}
+
+/* Find the probability of control flow reaching basic block TARGET given
+ control flow goes only inside basic blocks of set of basic blocks BBS and
+ no basic blocks can be visited twice (that way loops are discarded). */
+
+static int
+prob_enter_bb (basic_block target, VEC (basic_block, heap) *bbs)
+{
+ int prob = 0;
+ bool found = false;
+ VEC (int, heap) *bb_stack
+ = VEC_alloc (int, heap, VEC_length (basic_block, bbs));
+ VEC (int, heap) *prob_stack
+ = VEC_alloc (int, heap, VEC_length (basic_block, bbs));
+
+ VEC_quick_push (int, bb_stack, 0);
+ VEC_quick_push (int, prob_stack, REG_BR_PROB_BASE);
+
+ while (!VEC_empty (int, bb_stack))
+ {
+ edge e;
+ edge_iterator ei;
+ int cur_prob = VEC_pop (int, prob_stack);
+ int cur_bb_index = VEC_pop (int, bb_stack);
+ basic_block cur_bb = VEC_index (basic_block, bbs, cur_bb_index);
+
+ if (cur_bb == target)
+ {
+ prob += cur_prob;
+ found = true;
+ continue;
+ }
+
+ FOR_EACH_EDGE (e, ei, cur_bb->succs)
+ {
+ unsigned int new_bb_index;
+
+ /* Find a E->DEST block in BBS vector.
+ Note that this search is based on assumption that BBS is
+ topologically sorted and we do not need a backward edge,
+ that can lead only to entry block. */
+ new_bb_index = find_bb_in_bbs (e->dest, bbs, cur_bb_index + 1);
+
+ /* Skip blocks not from scheduling domain. */
+ if (new_bb_index < VEC_length (basic_block, bbs))
+ {
+ VEC_quick_push (int, bb_stack, new_bb_index);
+ VEC_quick_push (int, prob_stack,
+ (e->probability * cur_prob)
+ / sum_of_edge_probabilities (cur_bb->succs));
+ }
+ }
+ }
+
+ gcc_assert (prob <= REG_BR_PROB_BASE);
+ gcc_assert (found);
+ return prob;
+}
+
+/* Returns probability of taking any path leading from BB outside of
+ set of basic blocks BBS. */
+
+static int
+prob_exit_bbs (basic_block bb, VEC (basic_block, heap) *bbs)
+{
+ int prob = 0;
+ edge e;
+ edge_iterator ei;
+ unsigned int bb_index = find_bb_in_bbs (bb, bbs, 0);
+
+ gcc_assert (bb_index < VEC_length (basic_block, bbs));
+
+ /* Skip empty blocks. */
+ while (bb_note (bb) == BB_END (bb))
+ {
+ if (!bb->next_bb || bb->next_bb == EXIT_BLOCK_PTR
+ || find_bb_in_bbs (bb->next_bb, bbs, bb_index + 1)
+ == VEC_length (basic_block, bbs))
+ return REG_BR_PROB_BASE;
+
+ bb = bb->next_bb;
+ }
+
+ /* No-return block. */
+ if (VEC_empty (edge, bb->succs))
+ return REG_BR_PROB_BASE;
+
+ /* Find the probability of exit. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ unsigned int succ_bb_index = find_bb_in_bbs (e->dest, bbs, bb_index + 1);
+
+ if (succ_bb_index < VEC_length (basic_block, bbs))
+ {
+ basic_block succ_bb = e->dest;
+ bool succ_is_exit = (succ_bb == EXIT_BLOCK_PTR);
+
+ /* Skip empty blocks. */
+ while (bb_note (succ_bb) == BB_END (succ_bb))
+ {
+ if (!succ_bb->next_bb || succ_bb->next_bb == EXIT_BLOCK_PTR
+ || find_bb_in_bbs (succ_bb->next_bb, bbs, succ_bb_index + 1)
+ == VEC_length (basic_block, bbs))
+ {
+ succ_is_exit = true;
+ break;
+ }
+
+ succ_bb = succ_bb->next_bb;
+ }
+
+ /* Increase the probability if successor block is not in BBS set. */
+ if (succ_is_exit)
+ prob += e->probability;
+ }
+ else
+ /* Same. */
+ prob += e->probability;
+ }
+
+ if (prob > REG_BR_PROB_BASE)
+ {
+ /* Possible bug - sum of probabilities of outgoing edges of
+ basic block BB is greater than REG_BR_PROB_BASE. */
+ prob = REG_BR_PROB_BASE;
+ }
+ gcc_assert (prob >= 0);
+ return prob;
+}
+
+/* Check if INSN can be an exit from a scheduling domain. */
+
+static bool
+all_forw_deps_in_other_blocks_p (rtx insn)
+{
+ basic_block bb = BLOCK_FOR_INSN (insn);
+ rtx end = BB_END (bb);
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ /* Instructions with forward dependencies to instructions from the same
+ basic block cannot be an exit. */
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ if (bb == BLOCK_FOR_INSN (DEP_CON (dep)))
+ return false;
+
+ /* Instruction from basic block that ends with a jump (except speculation
+ checks) cannot be an exit.*/
+ if (end != insn
+ && JUMP_P (end)
+ && RECOVERY_BLOCK (end) == NULL)
+ return false;
+
+ return true;
+}
+
+/* Find all exit insns from a set of basic blocks BBS. This function fills
+ EXIT_INSNS and EXIT_PROBS vectors. */
+
+static void
+find_exit_insns (VEC (basic_block, heap) *bbs)
+{
+ int i;
+ basic_block bb;
+ rtx insn;
+
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ {
+ int prob_exit_from_bbs = -1;
+ int prob_enter_to_bb = -1;
+
+ for (insn = BB_HEAD (bb);
+ insn != NEXT_INSN (BB_END (bb));
+ insn = NEXT_INSN (insn))
+ {
+ if (!INSN_P (insn))
+ continue;
+
+ /* Check if INSN can be a candidate for exit from BBS. */
+ if (all_forw_deps_in_other_blocks_p (insn))
+ {
+ if (prob_exit_from_bbs == -1)
+ {
+ /* If probability of exiting from BBS starting from BB
+ is not yet computed - do it now. */
+ prob_exit_from_bbs = prob_exit_bbs (bb, bbs);
+ }
+ if (prob_exit_from_bbs > 0)
+ {
+ /* INSN is an exit. */
+ if (prob_enter_to_bb == -1)
+ prob_enter_to_bb = prob_enter_bb (bb, bbs);
+ VEC_safe_push (rtx, heap, exit_insns, insn);
+ /* Probability of the exit is probability of reaching basic
+ block of the exit from the entry of scheduling domain
+ multiplied by probability of leaving scheduling domain
+ from the same basic block. */
+ VEC_safe_push (int, heap, exit_probs,
+ (prob_exit_from_bbs * prob_enter_to_bb)
+ / REG_BR_PROB_BASE);
+ }
+ }
+ }
+ }
+}
+
+/* Finds critical path length from INSN to exit, given by EXIT_INDEX number.
+ Returns -1 if there is no path from INSN to such exit.
+ Also fills INSN_EXIT_LENGTH attribute of INSN. */
+
+static int
+find_path_length_to_exit_insn (rtx insn, unsigned int exit_index)
+{
+ int max_len = -1;
+ sd_iterator_def sd_it;
+ dep_t dep;
+ rtx exit = EXIT_INSN (exit_index);
+
+ /* Case this already has been computed. */
+ if (exit_index < VEC_length (int, INSN_EXIT_LENGTHS (insn)))
+ return INSN_EXIT_LENGTH (insn, exit_index);
+
+ if (insn == exit)
+ max_len = insn_cost (exit);
+ else
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ int len =
+ find_path_length_to_exit_insn (DEP_CON (dep),
+ exit_index);
+ if (len != -1)
+ max_len = MAX (len + dep_cost (dep), max_len);
+ }
+
+ VEC_safe_insert (int, heap, INSN_EXIT_LENGTHS (insn), exit_index, max_len);
+ return max_len;
+}
+
+/* Finds critical path lengths for INSN to each of exits from current
+ scheduling domain. */
+
+static void
+find_path_length_to_exit_insns (rtx insn)
+{
+ unsigned int i;
+
+ /* Already computed. */
+ if (!VEC_empty (int, INSN_EXIT_LENGTHS (insn)))
+ return;
+
+ for (i = 0; i < EXIT_NUM; i++)
+ find_path_length_to_exit_insn (insn, i);
+}
+
+/* Clear INSN_EXIT_LENGTHS attribute for INSN. */
+
+static void
+clear_path_lengths (rtx insn)
+{
+ VEC_truncate (int, INSN_EXIT_LENGTHS (insn), 0);
+}
+
+/* Free INSN_EXIT_LENGTHS attribute of INSN and all its sucessors. */
+
+static void
+free_exit_lengths (rtx insn)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ rtx succ = DEP_CON (dep);
+ if (INSN_EXIT_LENGTHS (succ) != NULL)
+ free_exit_lengths (succ);
+ }
+ VEC_free (int, heap, INSN_EXIT_LENGTHS (insn));
+}
+
+/* Check if exit insns are still exit insns. */
+
+static void
+check_exit_insns (void)
+{
+ int i;
+ rtx exit;
+
+ for (i = 0; VEC_iterate (rtx, exit_insns, i, exit); i++)
+ gcc_assert (INSN_TICK (exit) != INVALID_TICK
+ || all_forw_deps_in_other_blocks_p (exit));
+}
+
+/* Replace an EXIT with REPLACEMENT in EXIT_INSNS vector. */
+
+static void
+replace_exit_insns (rtx exit, rtx replacement)
+{
+ int i;
+ rtx cur_exit;
+ bool replaced = false;
+
+ for (i = 0; VEC_iterate (rtx, exit_insns, i, cur_exit); i++)
+ {
+ if (INSN_UID (exit) == INSN_UID (cur_exit))
+ {
+ gcc_assert (replaced == false);
+ VEC_replace (rtx, exit_insns, i, replacement);
+ replaced = true;
+ }
+ }
+}
+
+/* Computes priorities for all instructions in basic block BB.
+ Returns number of instructions in BB. */
+
+static int
+compute_priority_for_block (basic_block bb)
+{
+ int n = 0;
+ rtx insn;
+ int sched_max_insns_priority =
+ current_sched_info->sched_max_insns_priority;
+
+ /* Compute priorities. */
+ for (insn = BB_END (bb);
+ insn != PREV_INSN (BB_HEAD (bb));
+ insn = PREV_INSN (insn))
+ {
+ if (!INSN_P (insn))
+ continue;
+
+ n++;
+ (void) priority (insn);
+
+ if (INSN_PRIORITY_KNOWN (insn))
+ sched_max_insns_priority =
+ MAX (sched_max_insns_priority, INSN_PRIORITY (insn));
+ }
+
+ current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
+ return n;
+}
+
+/* Fills priorities for all instructions from set of basic blocks BBS. */
+
/* Next LUID to assign to an instruction. */
static int luid;
+/* Sets priorities of all instructions in basic blocks from vector BBS. */
+
+int
+set_priorities_for_bbs (VEC (basic_block, heap) *bbs)
+{
+ int i, n = 0;
+
+ exit_insns = VEC_alloc (rtx, heap, 1);
+ exit_probs = VEC_alloc (int, heap, 1);
+
+ find_exit_insns (bbs);
+
+ if (flag_sched_g_star && reload_completed)
+ {
+ max_insn_luid = luid - 1;
+ use_g_star_priority = true;
+ g_star_distribution = XCNEWVEC (int, max_insn_luid + 1);
+ additions = XCNEWVEC (int, EXIT_NUM);
+ create_g_distribution ();
+ }
+ else
+ use_g_star_priority = false;
+
+ /* There must be only one. */
+ use_spec_yield_priority = !use_g_star_priority;
+
+ for (i = VEC_length (basic_block, bbs) - 1; i >= 0; i--)
+ n += compute_priority_for_block (VEC_index (basic_block, bbs, i));
+
+ return n;
+}
+
+/* Free vectors used for computing priorities. */
+
+void
+finish_priorities (void)
+{
+ VEC_free (rtx, heap, exit_insns);
+ VEC_free (int, heap, exit_probs);
+ if (use_g_star_priority)
+ {
+ free (g_star_distribution);
+ free (additions);
+ }
+}
+
+/* Debug functions. */
+
+static void ATTRIBUTE_UNUSED
+debug_exit_insns (void)
+{
+ unsigned int i;
+ for (i = 0; i < EXIT_NUM; i++)
+ {
+ fprintf (stderr, "exit %d with prob %d: ",
+ i, VEC_index (int, exit_probs, i));
+ debug_insn_slim (EXIT_INSN (i));
+ fprintf (stderr, "\n");
+ }
+}
+
+static void ATTRIBUTE_UNUSED
+debug_path_lengths (basic_block bb)
+{
+ rtx insn;
+ unsigned int i;
+
+ for (insn = BB_HEAD (bb);
+ insn != NEXT_INSN (BB_END (bb));
+ insn = NEXT_INSN (insn))
+ {
+ if (!INSN_P (insn))
+ continue;
+
+ fprintf (stderr, "insn: ");
+ debug_insn_slim (insn);
+ fprintf (stderr, "; path lengths to exits [ ");
+ for (i = 0; i < EXIT_NUM; i++)
+ fprintf (stderr, "%d: %d; ", i, INSN_EXIT_LENGTH (insn, i));
+ fprintf (stderr, "]\n");
+ }
+}
+
+static void ATTRIBUTE_UNUSED
+debug_priorities (basic_block bb)
+{
+ rtx insn;
+
+ for (insn = BB_HEAD (bb);
+ insn != NEXT_INSN (BB_END (bb));
+ insn = NEXT_INSN (insn))
+ {
+ if (!INSN_P (insn))
+ continue;
+
+ fprintf (stderr, "insn: ");
+ debug_insn_slim (insn);
+ if (INSN_PRIORITY_KNOWN (insn))
+ fprintf (stderr, "; priority: %d\n", INSN_PRIORITY (insn));
+ else
+ fprintf (stderr, "; priority: ?\n");
+ }
+}
+
+static void ATTRIBUTE_UNUSED
+debug_priorities_n (int n)
+{
+ debug_priorities (BASIC_BLOCK (n));
+}
+
+static void ATTRIBUTE_UNUSED
+debug_path_lengths_n (int n)
+{
+ debug_path_lengths (BASIC_BLOCK (n));
+}
+
+static void ATTRIBUTE_UNUSED
+debug_priorities_bbs (VEC (basic_block, heap) *bbs)
+{
+ unsigned int i;
+ basic_block bb;
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ {
+ fprintf (stderr, "basic block %d:\n", bb->index);
+ debug_priorities (bb);
+ }
+}
+
+static void ATTRIBUTE_UNUSED
+debug_path_lengths_bbs (VEC (basic_block, heap) *bbs)
+{
+ unsigned int i;
+ basic_block bb;
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ {
+ fprintf (stderr, "basic block %d:\n", bb->index);
+ debug_path_lengths (bb);
+ }
+}
+
/* Initialize some global state for the scheduler. */
void
@@ -3324,7 +3904,7 @@ add_to_speculative_block (rtx insn)
ds_t ts;
sd_iterator_def sd_it;
dep_t dep;
- rtx twins = NULL;
+ rtx twins = NULL, twins2;
rtx_vec_t priorities_roots;
ts = TODO_SPEC (insn);
@@ -3431,6 +4011,7 @@ add_to_speculative_block (rtx insn)
}
}
+ twins2 = twins;
/* We couldn't have added the dependencies between INSN and TWINS earlier
because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
while (twins)
@@ -3447,11 +4028,36 @@ add_to_speculative_block (rtx insn)
}
twin = XEXP (twins, 1);
- free_INSN_LIST_node (twins);
+
+ /* Otherwise we do it later. */
+ if (!use_spec_yield_priority)
+ free_INSN_LIST_node (twins);
twins = twin;
}
calc_priorities (priorities_roots);
+
+ if (use_spec_yield_priority)
+ {
+ /* Clear path lengths of instructions from recovery block as it would
+ be scheduled later. */
+ while (twins2)
+ {
+ rtx twin;
+ basic_block rec = BLOCK_FOR_INSN (XEXP (twins2, 0));
+
+ for (twin = bb_note (rec);
+ twin != NEXT_INSN (BB_END (rec));
+ twin = NEXT_INSN (twin))
+ if (INSN_P (twin))
+ clear_path_lengths (twin);
+
+ twin = XEXP (twins2, 1);
+
+ free_INSN_LIST_node (twins2);
+ twins2 = twin;
+ }
+ }
VEC_free (rtx, heap, priorities_roots);
}
@@ -3911,6 +4517,11 @@ create_check_block_twin (rtx insn, bool
{
init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
sd_add_dep (new_dep, false);
+ if (use_spec_yield_priority)
+ {
+ replace_exit_insns (insn, check);
+ check_exit_insns();
+ }
}
if (!mutate_p)
@@ -3920,6 +4531,11 @@ create_check_block_twin (rtx insn, bool
rtx_vec_t priorities_roots = NULL;
clear_priorities (twin, &priorities_roots);
+ if (use_spec_yield_priority)
+ {
+ find_path_length_to_exit_insns(check);
+ (void) priority (check);
+ }
calc_priorities (priorities_roots);
VEC_free (rtx, heap, priorities_roots);
}
@@ -4328,12 +4944,17 @@ clear_priorities (rtx insn, rtx_vec_t *r
if (contributes_to_priority_p (dep))
insn_is_root_p = false;
- INSN_PRIORITY_STATUS (pro) = -1;
+ if (use_spec_yield_priority)
+ clear_path_lengths (insn);
+ INSN_PRIORITY_STATUS (pro) = -1;
+
clear_priorities (pro, roots_ptr);
}
}
- if (insn_is_root_p)
+ if (insn_is_root_p
+ || use_g_star_priority
+ || use_spec_yield_priority)
VEC_safe_push (rtx, heap, *roots_ptr, insn);
}
@@ -4346,6 +4967,9 @@ calc_priorities (rtx_vec_t roots)
int i;
rtx insn;
+ if (use_spec_yield_priority || use_g_star_priority)
+ check_exit_insns ();
+
for (i = 0; VEC_iterate (rtx, roots, i, insn); i++)
priority (insn);
}
-------------- next part --------------
--- ./gcc/haifa-sched.c 2007-08-24 16:46:11.000000000 +0400
+++ ../gsoc-final/gcc/haifa-sched.c 2007-08-23 18:44:52.000000000 +0400
@@ -4512,4 +5136,933 @@ check_sched_flags (void)
}
#endif /* ENABLE_CHECKING */
+/* Data structures for calculation of priority using G* heurisitc and
+ estimation of execution time of set ofinstructions using Rim and Jain bound.
+ See functions g_star_priority and rim_jain_bound in haifa-sched.c. */
+
+/* Structure to represent one instruction of subproblem. */
+struct _subproblem_element
+{
+ /* Instruction itself. */
+ rtx insn;
+
+ /* "As Soon As Possible" attribute means the smallest cycle at which
+ instruction can be issued inside subproblem. */
+ int asap;
+
+ /* "As Late As Possible" attribute means the largest cycle at which
+ instruction can be issued without increasing maximal value of
+ ASAP attricute inside subproblem. */
+ int alap;
+
+ /* Vector of indexes of predecessors (successors) of instruction inside
+ subproblem. */
+ VEC (int, heap) *preds;
+ VEC (int, heap) *succs;
+
+ /* Vector of costs of dependencies between instruction and its predecessors
+ (successors) for each corresponding element of PREDS (SUCCS) vector. */
+ VEC (int, heap) *preds_cost;
+ VEC (int, heap) *succs_cost;
+};
+
+typedef struct _subproblem_element subproblem_element;
+typedef struct _subproblem_element *subproblem_element_p;
+
+DEF_VEC_O (subproblem_element);
+DEF_VEC_ALLOC_O (subproblem_element, heap);
+
+/* Structure to represent set of instructions inside scheduler with additional
+ data about instructions. */
+struct _subproblem_t
+{
+ /* Maximal value of ASAP attribute among all instructions of subproblem.
+ Equals to critical path value inside data dependence graph, composed of
+ all instructions of subproblem. */
+ int max_asap;
+
+ /* Mask of luids of instructions, which can belong to subproblem.*/
+ char *mask;
+ int mask_size;
+
+ /* Instructions of subproblem. */
+ VEC (subproblem_element, heap) *nodes;
+};
+typedef struct _subproblem_t *subproblem_t;
+
+/* Debug function. */
+static void ATTRIBUTE_UNUSED
+debug_subproblem (subproblem_t subproblem)
+{
+ subproblem_element_p cur_element_p;
+
+ if (VEC_length (subproblem_element, subproblem->nodes) > 0)
+ {
+ int i;
+
+ fprintf (stderr, "subproblem: %d elements {\n",
+ VEC_length (subproblem_element, subproblem->nodes));
+ for (i = 0;
+ VEC_iterate (subproblem_element, subproblem->nodes, i, cur_element_p);
+ i++)
+ {
+ int k, cur_index_p;
+ fprintf (stderr, "[%d]\t%d\t%d\t%d\t[", i,
+ INSN_UID (cur_element_p->insn),
+ cur_element_p->asap, cur_element_p->alap);
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->preds, k, cur_index_p);
+ k++)
+ {
+ fprintf (stderr, " %d(%d)", cur_index_p,
+ VEC_index (int, cur_element_p->preds_cost, k));
+ }
+ fprintf (stderr, " ] [");
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->succs, k, cur_index_p);
+ k++)
+ {
+ fprintf (stderr, " %d(%d)", cur_index_p,
+ VEC_index (int, cur_element_p->succs_cost, k));
+ }
+ fprintf (stderr, " ]\n");
+ }
+ fprintf (stderr, "} max_asap: %d;", subproblem->max_asap);
+ }
+ else
+ fprintf (stderr, "subproblem: empty {}\n");
+}
+
+/* Returns index of instruction INSN inside array SUBPROBLEM->NODES or minus
+ one if there is no INSN inside SUBPROBLEM. */
+static int
+find_insn_in_subproblem (subproblem_t subproblem, rtx insn)
+{
+ int i;
+ subproblem_element_p cur_element_p;
+
+ for (i = 0;
+ VEC_iterate (subproblem_element, subproblem->nodes, i, cur_element_p);
+ i++)
+ {
+ if (cur_element_p->insn == insn)
+ return i;
+ }
+
+ return -1;
+}
+
+/* Fills attributes of subproblem elements with default values. ASAP is the
+ minimum over predecessors of ASAP values of predecessor plus dependence
+ cost or zero in case of absent predecessors. ALAP is the maximum over all
+ successors of ALAP values of successor minus dependence cost or maximal
+ value of ASAP in subproblem in case of absent successors. */
+static void
+fill_subproblem_default (subproblem_t subproblem)
+{
+ int i;
+ subproblem_element_p cur_element_p;
+ VEC (int, heap) *stack
+ = VEC_alloc (int, heap, VEC_length (subproblem_element, subproblem->nodes));
+
+ /* Fill asap fields. */
+ for (i = VEC_length (subproblem_element, subproblem->nodes) - 1; i >= 0; i--)
+ {
+ gcc_assert (VEC_empty (int, stack));
+ VEC_safe_push (int, heap, stack, i);
+
+ while (!VEC_empty (int, stack))
+ {
+ int k = 0, cur_pred, max_asap = 0;
+ int cur_index = VEC_pop (int, stack);
+ cur_element_p
+ = VEC_index (subproblem_element, subproblem->nodes, cur_index);
+
+ if (cur_element_p->asap != -1)
+ continue;
+ else if (VEC_empty (int, cur_element_p->preds))
+ {
+ cur_element_p->asap = 0;
+ continue;
+ }
+ else
+ {
+ bool all_preds_ready = true;
+
+ VEC_safe_push (int, heap, stack, i);
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->preds, k, cur_pred);
+ k++)
+ {
+ if (VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_pred)->asap == -1)
+ {
+ VEC_safe_push (int, heap, stack, cur_pred);
+ all_preds_ready = false;
+ }
+ }
+
+ if (!all_preds_ready)
+ continue;
+ else
+ VEC_pop (int, stack);
+
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->preds, k, cur_pred);
+ k++)
+ {
+ int cur_value
+ = VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_pred)->asap
+ + VEC_index (int, cur_element_p->preds_cost, k);
+ gcc_assert (VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_pred)->asap != -1
+ && VEC_index (int,
+ cur_element_p->preds_cost,
+ k) >= 0);
+ max_asap = MAX (max_asap, cur_value);
+ }
+
+ cur_element_p->asap = max_asap;
+ }
+ }
+ }
+
+ for (i = 0;
+ VEC_iterate (subproblem_element, subproblem->nodes, i, cur_element_p);
+ i++)
+ subproblem->max_asap = MAX (subproblem->max_asap, cur_element_p->asap);
+
+ /* Find alap fields. */
+ for (i = 0; i < (int) VEC_length (subproblem_element, subproblem->nodes); i++)
+ {
+ gcc_assert (VEC_empty (int, stack));
+ VEC_safe_push (int, heap, stack, i);
+
+ while (!VEC_empty (int, stack))
+ {
+ int k = 0, cur_succ;
+ int cur_index = VEC_pop (int, stack);
+ cur_element_p = VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_index);
+
+ if (cur_element_p->alap != -1)
+ continue;
+ else if (VEC_empty (int, cur_element_p->succs))
+ {
+ cur_element_p->alap = subproblem->max_asap;
+ continue;
+ }
+ else
+ {
+ bool all_succs_ready = true;
+
+ VEC_safe_push (int, heap, stack, i);
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->succs, k, cur_succ);
+ k++)
+ {
+ if (VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_succ)->alap == -1)
+ {
+ VEC_safe_push (int, heap, stack, cur_succ);
+ all_succs_ready = false;
+ }
+ }
+
+ if (!all_succs_ready)
+ continue;
+ else
+ VEC_pop (int, stack);
+
+ for (k = 0;
+ VEC_iterate (int, cur_element_p->succs, k, cur_succ);
+ k++)
+ {
+ int cur_value
+ = VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_succ)->alap
+ - VEC_index (int, cur_element_p->succs_cost, k);
+ gcc_assert (cur_value >= 0
+ && VEC_index (subproblem_element,
+ subproblem->nodes,
+ cur_succ)->alap != -1
+ && VEC_index (int,
+ cur_element_p->succs_cost,
+ k) >= 0);
+ }
+ }
+ }
+ }
+}
+
+/* Sets all values of attributes inside SUBPROBLEM to unknown status. */
+static void
+clear_subproblem_values (subproblem_t subproblem)
+{
+ int i;
+ subproblem_element_p cur_element_p;
+
+ for (i = 0;
+ VEC_iterate (subproblem_element,
+ subproblem->nodes,
+ i,
+ cur_element_p);
+ i++)
+ {
+ cur_element_p->alap = -1;
+ cur_element_p->asap = -1;
+ }
+
+ subproblem->max_asap = -1;
+}
+
+/* Adds new instruction ROOT and all its predecessors (if they are not inside
+ already) to SUBPROBLEM. Only instructions which luids are set in
+ MASK array are added. */
+static void
+add_root_to_subproblem (subproblem_t subproblem, rtx root, char *mask,
+ int mask_size)
+{
+ VEC (rtx, heap) *stack;
+
+ gcc_assert (subproblem->nodes && root && INSN_P (root));
+
+ stack = VEC_alloc (rtx, heap, 1);
+ VEC_safe_push (rtx, heap, stack, root);
+
+ while (!VEC_empty (rtx, stack))
+ {
+ rtx insn = VEC_pop (rtx, stack);
+ subproblem_element_p cur_element_p;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ if (find_insn_in_subproblem (subproblem, insn) != -1)
+ continue;
+
+ cur_element_p = XCNEWVEC (subproblem_element, 1);
+ cur_element_p->insn = insn;
+ cur_element_p->asap = -1;
+ cur_element_p->alap = -1;
+ cur_element_p->preds = VEC_alloc (int, heap, 1);
+ cur_element_p->succs = VEC_alloc (int, heap, 1);
+ cur_element_p->preds_cost = VEC_alloc (int, heap, 1);
+ cur_element_p->succs_cost = VEC_alloc (int, heap, 1);
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ rtx pro = DEP_PRO (dep);
+ int cost, index;
+
+ if (INSN_LUID (pro) > mask_size || !mask [INSN_LUID (pro)])
+ {
+ gcc_assert (find_insn_in_subproblem (subproblem, pro) == -1);
+ continue;
+ }
+
+ index = find_insn_in_subproblem (subproblem, pro);
+ if (index == -1)
+ {
+ VEC_safe_push (rtx, heap, stack, pro);
+ }
+ else
+ {
+ cost = dep_cost (dep);
+ VEC_safe_push (int, heap, cur_element_p->preds, index);
+ VEC_safe_push (int, heap, cur_element_p->preds_cost, cost);
+ VEC_safe_push (int, heap,
+ (VEC_index (subproblem_element,
+ subproblem->nodes,
+ index))->succs,
+ VEC_length (subproblem_element,
+ subproblem->nodes));
+ VEC_safe_push (int, heap,
+ (VEC_index (subproblem_element,
+ subproblem->nodes,
+ index))->succs_cost,
+ cost);
+ }
+ }
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ rtx con = DEP_CON (dep);
+ int cost, index;
+
+ if (INSN_LUID (con) > mask_size || !mask [INSN_LUID (con)])
+ {
+ gcc_assert (find_insn_in_subproblem (subproblem, con) == -1);
+ continue;
+ }
+
+ index = find_insn_in_subproblem (subproblem, con);
+ if (index != -1)
+ {
+ cost = dep_cost (dep);
+ VEC_safe_push (int, heap, cur_element_p->succs, index);
+ VEC_safe_push (int, heap, cur_element_p->succs_cost, cost);
+ VEC_safe_push (int, heap,
+ (VEC_index (subproblem_element,
+ subproblem->nodes,
+ index))->preds,
+ VEC_length (subproblem_element,
+ subproblem->nodes));
+ VEC_safe_push (int, heap,
+ (VEC_index (subproblem_element,
+ subproblem->nodes,
+ index))->preds_cost,
+ cost);
+ }
+ }
+
+ VEC_safe_push (subproblem_element, heap, subproblem->nodes, cur_element_p);
+ free (cur_element_p);
+ }
+
+ VEC_free (rtx, heap, stack);
+
+ clear_subproblem_values(subproblem);
+ fill_subproblem_default (subproblem);
+}
+
+/* Frees memory, allocated under subproblem. */
+static void
+delete_subproblem (subproblem_t subproblem)
+{
+ int i;
+ subproblem_element_p cur_element_p;
+
+ for (i = 0;
+ VEC_iterate (subproblem_element, subproblem->nodes, i, cur_element_p);
+ i++)
+ {
+ VEC_free (int, heap, cur_element_p->preds);
+ VEC_free (int, heap, cur_element_p->succs);
+ VEC_free (int, heap, cur_element_p->preds_cost);
+ VEC_free (int, heap, cur_element_p->succs_cost);
+ /*free (cur_element_p);*/
+ }
+ VEC_free (subproblem_element, heap, subproblem->nodes);
+ free (subproblem->mask);
+ free (subproblem);
+}
+
+/* Creates subproblem, including only instructions, which luids are set in
+ MASK array. */
+static subproblem_t
+create_subproblem_with_mask (rtx root, char *mask, int mask_size)
+{
+ subproblem_t new_problem;
+
+ new_problem = XNEWVEC (struct _subproblem_t, 1);
+ new_problem->mask_size = mask_size;
+ new_problem->mask = XCNEWVEC (char, new_problem->mask_size + 1);
+ memcpy (new_problem->mask, mask, mask_size + 1);
+ new_problem->nodes = VEC_alloc (subproblem_element, heap, 1);
+
+ add_root_to_subproblem (new_problem, root, mask, mask_size);
+
+ return new_problem;
+}
+
+/* Creates subproblem with full mask. */
+static subproblem_t ATTRIBUTE_UNUSED
+create_subproblem (rtx root)
+{
+ int mask_size = max_insn_luid;
+ char *all_mask = XCNEWVEC (char, mask_size + 1);
+ subproblem_t new_problem;
+
+ memset (all_mask, 1, mask_size + 1);
+ new_problem = create_subproblem_with_mask (root, all_mask, mask_size);
+ free (all_mask);
+
+ return new_problem;
+}
+
+static subproblem_t cur_subproblem = NULL;
+
+/* Chooses between two instructions one with lesser ASAP value or in case of
+ equal ASAP attribute values - with lesser ALAP. */
+static int
+rank_by_asap_and_alap (const void *ap, const void *bp)
+{
+ int a = *(int *)ap, b = *(int *)bp;
+ int asap_a, alap_a, asap_b, alap_b;
+
+ gcc_assert (cur_subproblem != NULL && cur_subproblem->nodes != NULL);
+ asap_a = VEC_index (subproblem_element, cur_subproblem->nodes, a)->asap;
+ alap_a = VEC_index (subproblem_element, cur_subproblem->nodes, a)->alap;
+ asap_b = VEC_index (subproblem_element, cur_subproblem->nodes, b)->asap;
+ alap_b = VEC_index (subproblem_element, cur_subproblem->nodes, b)->alap;
+
+ gcc_assert (asap_a != -1 && asap_b != -1 && alap_a != -1 && alap_b != -1);
+
+ if (asap_a > asap_b)
+ return 1;
+ else if (asap_a < asap_b)
+ return -1;
+
+ if (alap_a > alap_b)
+ return 1;
+ else if (alap_a < alap_b)
+ return -1;
+
+ return 0;
+}
+
+/* Returns true if all predecessors of instruction, corresponding to
+ CUR_ELEMENT_P were "scheduled" (indeed, modeled for scheduling in
+ rim_jain_bound). */
+static bool
+check_all_preds_scheduled (subproblem_element_p cur_element_p,
+ int *scheduled, int *insns, int size)
+{
+ bool found;
+ int i, j, cur_pred;
+
+ for (i = 0;
+ VEC_iterate (int, cur_element_p->preds, i, cur_pred);
+ i++)
+ {
+ found = false;
+ for (j = 0; j < size; j++)
+ if (cur_pred == insns[j])
+ {
+ gcc_assert (found == false);
+ found = true;
+ if (!scheduled[j])
+ return false;
+ }
+ gcc_assert (found == true);
+ }
+
+ return true;
+}
+
+/* Returns estimation of execution time of set of instructions given by
+ SUBPROBLEM with consideration of dependencies and processor
+ resources. The whole algorithm is described in article "Lower-bound
+ performance estimation for the high-level synthesis scheduling
+ problem" by M.Rim and R.Jain. The main idea of the algorithm is to
+ discard dependencies and try to model scheduling instructions in
+ special order. The order is given by increasing values of ALAP attributes of
+ instructions. Each instruction is then "scheduled" in the earliest cycle
+ that the processor resources permit and if current modeled processor cycle
+ is not lesser than its ASAP attribute value. After all instructions are
+ "scheduled" the maximal difference between the modelled scheduling cycle of
+ instruction and its ALAP attricute value is computed. This difference
+ represents lag between latest cycle that instruction can be scheduled
+ (to avoid delay of the whole schedule) and cycle on which it can be
+ scheduled when resources permit. Adding this lag to critical path value
+ of subproblem one can get a rough estimation of number of cycles that
+ subproblem needs to be computed. This inplementation has a drawback that
+ it is not a lower-boundm but only an estimation. In original article it
+ seems that processor description is made in form of table reservation.
+ As in GCC there is an automata processor description, on some processors
+ with vital instruction ordering inside one cycle, that has complex
+ corresponding automaton, sometimes it is possible that this function
+ returns value, greater than actual length of optimal schedule for
+ subproblem. Though it can serve as estimator of time for subproblem
+ to be executed. */
+static int
+rim_jain_bound (subproblem_t subproblem)
+{
+ int *insns_by_dh, *scheduled_array;
+ int i, j, sched_more, max_gap = 0,
+ subproblem_size = VEC_length (subproblem_element, subproblem->nodes);
+ int cur_cycle = 0, cur_thresh = 0, best = -1;
+ bool scheduled = false;
+ state_t cur_state = xmalloc (dfa_state_size),
+ tmp_state = xmalloc (dfa_state_size);
+ rtx cur_insn;
+
+ insns_by_dh = XCNEWVEC (int, subproblem_size);
+ scheduled_array = XCNEWVEC (int, subproblem_size);
+
+ for (i = 0; i < subproblem_size; i++)
+ insns_by_dh[i] = i;
+
+ /* All instructions from subproblem are ordered first by their ASAP and then
+ by ALAP attribute values. Then it is possible to easily distinguish
+ which instructions can be executed on current modelled cycle and which of
+ them are more prioritized. */
+ cur_subproblem = subproblem;
+ qsort (insns_by_dh, subproblem_size, sizeof (int), rank_by_asap_and_alap);
+ cur_subproblem = NULL;
+
+ sched_more = subproblem_size;
+ state_reset (cur_state);
+
+ while (sched_more)
+ {
+ scheduled = false;
+ best = -1;
+
+ /* CUR_THRESH marks first instruction from the order that has not been
+ "scheduled" yet. */
+ for (j = cur_thresh; j < subproblem_size; j++)
+ {
+ subproblem_element_p cur_element_p
+ = VEC_index (subproblem_element, subproblem->nodes, insns_by_dh[j]);
+ cur_insn = cur_element_p->insn;
+
+ gcc_assert (cur_element_p->asap != -1 && cur_element_p->alap != -1);
+ if (cur_element_p->asap > cur_cycle)
+ {
+ /* No ready insn that can be computed on this cycle. */
+ break;
+ }
+
+ /* If this insn was already scheduled. */
+ if (scheduled_array[j])
+ continue;
+
+ /* Questionable check. It seems like Rim and Jain ignore dependencies
+ and this check is wrong, though without it estimation is not so
+ tight in many cases. */
+ if (!check_all_preds_scheduled (cur_element_p, scheduled_array,
+ insns_by_dh, subproblem_size))
+ continue;
+
+ /* Try issue this insn on this cycle. */
+ memcpy (tmp_state, cur_state, dfa_state_size);
+ if (recog_memoized (cur_insn) < 0
+ || state_transition (cur_state, cur_insn) < 0)
+ {
+ /* Insn can be scheduled on this cycle. */
+ if (best == -1
+ || cur_element_p->alap
+ < VEC_index (subproblem_element,
+ subproblem->nodes,
+ insns_by_dh[best])->alap)
+ {
+ scheduled = true;
+ best = j;
+ }
+ }
+
+ /* Undo state change. */
+ memcpy (cur_state, tmp_state, dfa_state_size);
+ }
+
+ if (scheduled)
+ {
+ subproblem_element_p best_element_p
+ = VEC_index (subproblem_element,
+ subproblem->nodes,
+ insns_by_dh[best]);
+
+ /* Change state, modelling execution of BEST instruction. */
+ gcc_assert (scheduled_array[best] == 0);
+ scheduled_array[best] = 1;
+
+ if (best_element_p->insn
+ && recog_memoized (best_element_p->insn) > 0)
+ state_transition (cur_state, best_element_p->insn);
+
+ /* New gap found! */
+ max_gap = MAX (max_gap, cur_cycle - best_element_p->alap);
+
+ if (best == cur_thresh)
+ for (; best < subproblem_size; best++)
+ {
+ if (scheduled_array[best])
+ cur_thresh++;
+ else
+ break;
+ }
+ sched_more--;
+ }
+ else
+ {
+ /* Avancing cycle. */
+ if (targetm.sched.dfa_pre_cycle_insn)
+ state_transition (cur_state,
+ targetm.sched.dfa_pre_cycle_insn ());
+
+ state_transition (cur_state, NULL);
+
+ if (targetm.sched.dfa_post_cycle_insn)
+ state_transition (cur_state,
+ targetm.sched.dfa_post_cycle_insn ());
+
+ cur_cycle++;
+ }
+ }
+
+ free (insns_by_dh);
+ free (scheduled_array);
+ free (cur_state);
+ free (tmp_state);
+
+ return max_gap + subproblem->max_asap;
+}
+
+/* Compute rank for subproblem. See comment in FIND_G_STAR. */
+static int
+get_rank_for_subproblem (subproblem_t subproblem)
+{
+ unsigned int i, e, w = 0, t;
+
+ for (e = 0; e < EXIT_NUM; e++)
+ {
+ rtx exit = EXIT_INSN (e);
+ bool inside = false;
+ subproblem_element_p el;
+
+ for (i = 0; VEC_iterate (subproblem_element, subproblem->nodes, i, el);i ++)
+ {
+ if (el->insn == exit)
+ {
+ inside = true;
+ break;
+ }
+ }
+
+ if (inside)
+ {
+ w += EXIT_PROB (e);
+ }
+ }
+ if (w == 0)
+ return INT_MAX;
+ /* T is an estimation of time of executing of all instructions of
+ SUBPROBLEM. The most simple estimation is critical path value of
+ dependence graph, which can be constructed from those instructions.
+ Unfortunately, it does not take available processor resources into
+ account and hence imprecise. More tight estimation is achieved by using
+ procedure, described by Rim and Jain (see comment before rim_jain_bound
+ function). Unfortunately, it is more complex and hence needs more
+ computations. */
+ if (flag_sched_g_star_use_rjbound)
+ t = rim_jain_bound (subproblem);
+ else
+ t = subproblem->max_asap;
+ return (t * REG_BR_PROB_BASE) / w;
+}
+
+/* Finds G* subgraph among marked instructions. See article "Profile-Driven
+ Instruction Level Parallel Scheduling with Application to Super Blocks" by
+ C.Chekuri, R.Johnson, R.Motwani, B.Natarajan, B.R.Rau and M.Schlansker for
+ complete explanation. In several words, G* is a precedence-closed
+ (i.e. along an instruction, it includes all its predecessors) subgraph
+ with minimal rank, where rank is calculated as estimation of execution
+ time of this subgraph divided by sum of probabilities of exits
+ belonging to subgraph. */
+static subproblem_t
+find_g_star (sbitmap exits_marked, char *mask, int mask_size)
+{
+ unsigned int i, min_rank_index = EXIT_NUM;
+ int *rank = XCNEWVEC (int, EXIT_NUM);
+ subproblem_t *subproblems = XCNEWVEC (subproblem_t, EXIT_NUM);
+ subproblem_t g_star;
+ sbitmap_iterator sbi;
+
+ EXECUTE_IF_SET_IN_SBITMAP (exits_marked, 0, i, sbi)
+ {
+ subproblems[i] = create_subproblem_with_mask (EXIT_INSN (i),
+ mask, mask_size);
+ rank[i] = get_rank_for_subproblem (subproblems[i]);
+ /* Choose earliset exit with minimal rank - as exits are recorded
+ beginning from the last, it has the biggest number among exits with
+ minimal rank. */
+ if (min_rank_index == EXIT_NUM)
+ min_rank_index = i;
+ else if (rank[i] <= rank[min_rank_index])
+ {
+ delete_subproblem (subproblems[min_rank_index]);
+ min_rank_index = i;
+ }
+ else
+ delete_subproblem (subproblems[i]);
+ }
+
+ gcc_assert (min_rank_index < EXIT_NUM);
+
+ g_star = subproblems[min_rank_index];
+
+ free (rank);
+ free (subproblems);
+ return g_star;
+}
+
+/* Unmark instructions from G_STAR. */
+static void
+unmark (subproblem_t g_star, char *mask, int mask_size)
+{
+ unsigned int i;
+ subproblem_element_p el;
+
+ for (i = 0; VEC_iterate (subproblem_element, g_star->nodes, i, el);i ++)
+ {
+ gcc_assert (INSN_LUID (el->insn) <= mask_size);
+ mask[INSN_LUID (el->insn)] = 0;
+ }
+}
+
+/* Process instructions from G*. */
+static void
+set_basket (int basket, subproblem_t g_star, sbitmap exits_scheduled)
+{
+ unsigned int i;
+ subproblem_element_p el;
+
+ /* Set basket for all instructions from G_STAR subproblem. */
+ for (i = 0; VEC_iterate (subproblem_element, g_star->nodes, i, el);i ++)
+ {
+ gcc_assert (g_star_distribution[INSN_LUID (el->insn)] == 0);
+ g_star_distribution[INSN_LUID (el->insn)] = basket;
+ }
+
+ /* Unmark exits from G*. */
+ for (i = 0; i < EXIT_NUM; i++)
+ {
+ if (find_insn_in_subproblem (g_star, EXIT_INSN (i)) != -1)
+ {
+ gcc_assert (TEST_BIT (exits_scheduled, i));
+ RESET_BIT (exits_scheduled, i);
+ }
+ }
+}
+
+/* Sorts all instructions from current scheduling domain into "baskets",
+ according to G* heuristic. In several words, basket is a group of
+ instructions with priority greater than of instructions from next
+ basket and lesser than of instructions from previous basket. G*
+ heuristic itself is following:
+
+ I) Mark all instructions.
+ II) While marked exits left do:
+ 1) Find G* subgraph in DDG.
+ 2) Put instructions of G* into new basket.
+ 3) Unmark instructions from G*.*/
+static void
+create_g_distribution (void)
+{
+ int basket = 0, mask_size = max_insn_luid, addition;
+ char *mask = XCNEWVEC (char, mask_size + 1);
+ sbitmap exits_marked;
+
+ exits_marked = sbitmap_alloc (EXIT_NUM);
+ sbitmap_ones (exits_marked);
+ /* Mark all instructions in scheduling domain. */
+ memset (mask, 1, mask_size + 1);
+
+ while (sbitmap_first_set_bit (exits_marked) != -1)
+ {
+ subproblem_t g_star;
+
+ addition = basket == 0 ? 0 : additions[basket - 1];
+ g_star = find_g_star (exits_marked, mask, mask_size);
+ /* Set initially ADDITIONS to be equal ADDITIONS of previous basket plus
+ critical path value of instructions from G* and zero for the first
+ basket. */
+ additions[basket] = addition + g_star->max_asap + 1;
+ set_basket (basket, g_star, exits_marked);
+ unmark (g_star, mask, mask_size);
+ delete_subproblem (g_star);
+ basket++;
+ }
+
+ /* Revert additions so that instructions from first basket recieve the
+ biggest addition. */
+ addition = additions[basket - 1];
+ for (basket--; basket >= 0; basket--)
+ additions[basket] = addition - additions[basket];
+
+ sbitmap_free (exits_marked);
+ free (mask);
+}
+
+/* Finds a basket for INSN. If basket was chosen at the beginning of
+ scheduling - return it's number. If INSN was created during scheduling
+ - choose basket with maximal number among baskets of predecessors (not
+ necessarily direct). */
+static int find_basket (rtx insn)
+{
+ rtx next;
+ int basket = -1;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ if (INSN_LUID (insn) <= max_insn_luid)
+ return g_star_distribution[INSN_LUID (insn)];
+
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
+ {
+ next = DEP_PRO (dep);
+
+ if (INSN_LUID (next) <= max_insn_luid)
+ {
+ if (basket == -1 || basket < g_star_distribution[INSN_LUID (next)])
+ basket = g_star_distribution[INSN_LUID (next)];
+ }
+ }
+ FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
+ {
+ next = DEP_PRO (dep);
+
+ if (INSN_LUID (next) <= max_insn_luid)
+ {
+ if (basket == -1 || basket < g_star_distribution[INSN_LUID (next)])
+ basket = g_star_distribution[INSN_LUID (next)];
+ }
+ }
+
+ gcc_assert (basket != -1);
+ return basket;
+}
+
+/* Calculate priority of INSN using G* heuristic with critical path heuristic
+ as secondary. Basic idea is that all instructions are distributed into
+ baskets - subsets of instructions with the property that instructions
+ from each next basket should be less prioritized than all instructions
+ from previous basket. Inside basket instructions are ordered based on
+ their critical path value. */
+static int
+g_star_priority (rtx insn)
+{
+ int basket = -1, this_priority = -1;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ basket = find_basket (insn);
+
+ gcc_assert (basket != -1);
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ {
+ rtx next;
+ int next_priority, cost;
+
+ next = DEP_CON (dep);
+
+ /* Consider instructions only from current basket. */
+ if (find_basket (next) != basket)
+ continue;
+
+ cost = dep_cost (dep);
+ next_priority = cost + priority (next) - additions[basket];
+
+ if (next_priority > this_priority)
+ this_priority = next_priority;
+ }
+
+ /* If no forward dependent instructions from same basket. */
+ if (this_priority == -1)
+ this_priority = insn_cost (insn);
+
+ /* Apply increasing of priority depending of instruction's basket. */
+ this_priority += additions[basket];
+ return this_priority;
+}
+
#endif /* INSN_SCHEDULING */
More information about the Gcc
mailing list