/* Instruction scheduling pass.
|
/* Instruction scheduling pass.
|
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
|
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
|
1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
|
1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
|
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
|
and currently maintained by, Jim Wilson (wilson@cygnus.com)
|
and currently maintained by, Jim Wilson (wilson@cygnus.com)
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
GCC is free software; you can redistribute it and/or modify it under
|
the terms of the GNU General Public License as published by the Free
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "tm_p.h"
|
#include "tm_p.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "regs.h"
|
#include "regs.h"
|
#include "function.h"
|
#include "function.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "insn-config.h"
|
#include "insn-config.h"
|
#include "insn-attr.h"
|
#include "insn-attr.h"
|
#include "except.h"
|
#include "except.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "recog.h"
|
#include "recog.h"
|
#include "cfglayout.h"
|
#include "cfglayout.h"
|
#include "params.h"
|
#include "params.h"
|
#include "sched-int.h"
|
#include "sched-int.h"
|
#include "target.h"
|
#include "target.h"
|
#include "output.h"
|
#include "output.h"
|
|
|
|
|
#ifdef INSN_SCHEDULING
|
#ifdef INSN_SCHEDULING
|
|
|
/* The number of insns to be scheduled in total. */
|
/* The number of insns to be scheduled in total. */
|
static int rgn_n_insns;
|
static int rgn_n_insns;
|
|
|
/* The number of insns scheduled so far. */
|
/* The number of insns scheduled so far. */
|
static int sched_rgn_n_insns;
|
static int sched_rgn_n_insns;
|
|
|
/* Set of blocks, that already have their dependencies calculated. */
|
/* Set of blocks, that already have their dependencies calculated. */
|
static bitmap_head dont_calc_deps;
|
static bitmap_head dont_calc_deps;
|
|
|
/* Last basic block in current ebb. */
|
/* Last basic block in current ebb. */
|
static basic_block last_bb;
|
static basic_block last_bb;
|
|
|
/* Implementations of the sched_info functions for region scheduling. */
|
/* Implementations of the sched_info functions for region scheduling. */
|
static void init_ready_list (void);
|
static void init_ready_list (void);
|
static void begin_schedule_ready (rtx, rtx);
|
static void begin_schedule_ready (rtx, rtx);
|
static int schedule_more_p (void);
|
static int schedule_more_p (void);
|
static const char *ebb_print_insn (const_rtx, int);
|
static const char *ebb_print_insn (const_rtx, int);
|
static int rank (rtx, rtx);
|
static int rank (rtx, rtx);
|
static int ebb_contributes_to_priority (rtx, rtx);
|
static int ebb_contributes_to_priority (rtx, rtx);
|
static basic_block earliest_block_with_similiar_load (basic_block, rtx);
|
static basic_block earliest_block_with_similiar_load (basic_block, rtx);
|
static void add_deps_for_risky_insns (rtx, rtx);
|
static void add_deps_for_risky_insns (rtx, rtx);
|
static basic_block schedule_ebb (rtx, rtx);
|
static basic_block schedule_ebb (rtx, rtx);
|
static void debug_ebb_dependencies (rtx, rtx);
|
static void debug_ebb_dependencies (rtx, rtx);
|
|
|
static void ebb_add_remove_insn (rtx, int);
|
static void ebb_add_remove_insn (rtx, int);
|
static void ebb_add_block (basic_block, basic_block);
|
static void ebb_add_block (basic_block, basic_block);
|
static basic_block advance_target_bb (basic_block, rtx);
|
static basic_block advance_target_bb (basic_block, rtx);
|
static void ebb_fix_recovery_cfg (int, int, int);
|
static void ebb_fix_recovery_cfg (int, int, int);
|
|
|
/* Return nonzero if there are more insns that should be scheduled. */
|
/* Return nonzero if there are more insns that should be scheduled. */
|
|
|
static int
|
static int
|
schedule_more_p (void)
|
schedule_more_p (void)
|
{
|
{
|
return sched_rgn_n_insns < rgn_n_insns;
|
return sched_rgn_n_insns < rgn_n_insns;
|
}
|
}
|
|
|
/* Print dependency information about ebb between HEAD and TAIL. */
|
/* Print dependency information about ebb between HEAD and TAIL. */
|
static void
|
static void
|
debug_ebb_dependencies (rtx head, rtx tail)
|
debug_ebb_dependencies (rtx head, rtx tail)
|
{
|
{
|
fprintf (sched_dump,
|
fprintf (sched_dump,
|
";; --------------- forward dependences: ------------ \n");
|
";; --------------- forward dependences: ------------ \n");
|
|
|
fprintf (sched_dump, "\n;; --- EBB Dependences --- from bb%d to bb%d \n",
|
fprintf (sched_dump, "\n;; --- EBB Dependences --- from bb%d to bb%d \n",
|
BLOCK_NUM (head), BLOCK_NUM (tail));
|
BLOCK_NUM (head), BLOCK_NUM (tail));
|
|
|
debug_dependencies (head, tail);
|
debug_dependencies (head, tail);
|
}
|
}
|
|
|
/* Add all insns that are initially ready to the ready list READY. Called
|
/* Add all insns that are initially ready to the ready list READY. Called
|
once before scheduling a set of insns. */
|
once before scheduling a set of insns. */
|
|
|
static void
|
static void
|
init_ready_list (void)
|
init_ready_list (void)
|
{
|
{
|
int n = 0;
|
int n = 0;
|
rtx prev_head = current_sched_info->prev_head;
|
rtx prev_head = current_sched_info->prev_head;
|
rtx next_tail = current_sched_info->next_tail;
|
rtx next_tail = current_sched_info->next_tail;
|
rtx insn;
|
rtx insn;
|
|
|
sched_rgn_n_insns = 0;
|
sched_rgn_n_insns = 0;
|
|
|
/* Print debugging information. */
|
/* Print debugging information. */
|
if (sched_verbose >= 5)
|
if (sched_verbose >= 5)
|
debug_ebb_dependencies (NEXT_INSN (prev_head), PREV_INSN (next_tail));
|
debug_ebb_dependencies (NEXT_INSN (prev_head), PREV_INSN (next_tail));
|
|
|
/* Initialize ready list with all 'ready' insns in target block.
|
/* Initialize ready list with all 'ready' insns in target block.
|
Count number of insns in the target block being scheduled. */
|
Count number of insns in the target block being scheduled. */
|
for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
|
for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
|
{
|
{
|
try_ready (insn);
|
try_ready (insn);
|
n++;
|
n++;
|
}
|
}
|
|
|
gcc_assert (n == rgn_n_insns);
|
gcc_assert (n == rgn_n_insns);
|
}
|
}
|
|
|
/* INSN is being scheduled after LAST. Update counters. */
|
/* INSN is being scheduled after LAST. Update counters. */
|
static void
|
static void
|
begin_schedule_ready (rtx insn, rtx last)
|
begin_schedule_ready (rtx insn, rtx last)
|
{
|
{
|
sched_rgn_n_insns++;
|
sched_rgn_n_insns++;
|
|
|
if (BLOCK_FOR_INSN (insn) == last_bb
|
if (BLOCK_FOR_INSN (insn) == last_bb
|
/* INSN is a jump in the last block, ... */
|
/* INSN is a jump in the last block, ... */
|
&& control_flow_insn_p (insn)
|
&& control_flow_insn_p (insn)
|
/* that is going to be moved over some instructions. */
|
/* that is going to be moved over some instructions. */
|
&& last != PREV_INSN (insn))
|
&& last != PREV_INSN (insn))
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
basic_block bb;
|
basic_block bb;
|
|
|
/* An obscure special case, where we do have partially dead
|
/* An obscure special case, where we do have partially dead
|
instruction scheduled after last control flow instruction.
|
instruction scheduled after last control flow instruction.
|
In this case we can create new basic block. It is
|
In this case we can create new basic block. It is
|
always exactly one basic block last in the sequence. */
|
always exactly one basic block last in the sequence. */
|
|
|
FOR_EACH_EDGE (e, ei, last_bb->succs)
|
FOR_EACH_EDGE (e, ei, last_bb->succs)
|
if (e->flags & EDGE_FALLTHRU)
|
if (e->flags & EDGE_FALLTHRU)
|
break;
|
break;
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
gcc_assert (!e || !(e->flags & EDGE_COMPLEX));
|
gcc_assert (!e || !(e->flags & EDGE_COMPLEX));
|
|
|
gcc_assert (BLOCK_FOR_INSN (insn) == last_bb
|
gcc_assert (BLOCK_FOR_INSN (insn) == last_bb
|
&& !IS_SPECULATION_CHECK_P (insn)
|
&& !IS_SPECULATION_CHECK_P (insn)
|
&& BB_HEAD (last_bb) != insn
|
&& BB_HEAD (last_bb) != insn
|
&& BB_END (last_bb) == insn);
|
&& BB_END (last_bb) == insn);
|
|
|
{
|
{
|
rtx x;
|
rtx x;
|
|
|
x = NEXT_INSN (insn);
|
x = NEXT_INSN (insn);
|
if (e)
|
if (e)
|
gcc_assert (NOTE_P (x) || LABEL_P (x));
|
gcc_assert (NOTE_P (x) || LABEL_P (x));
|
else
|
else
|
gcc_assert (BARRIER_P (x));
|
gcc_assert (BARRIER_P (x));
|
}
|
}
|
#endif
|
#endif
|
|
|
if (e)
|
if (e)
|
{
|
{
|
bb = split_edge (e);
|
bb = split_edge (e);
|
gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_END (bb)));
|
gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_END (bb)));
|
}
|
}
|
else
|
else
|
/* Create an empty unreachable block after the INSN. */
|
/* Create an empty unreachable block after the INSN. */
|
bb = create_basic_block (NEXT_INSN (insn), NULL_RTX, last_bb);
|
bb = create_basic_block (NEXT_INSN (insn), NULL_RTX, last_bb);
|
|
|
/* split_edge () creates BB before E->DEST. Keep in mind, that
|
/* split_edge () creates BB before E->DEST. Keep in mind, that
|
this operation extends scheduling region till the end of BB.
|
this operation extends scheduling region till the end of BB.
|
Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
|
Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
|
of the scheduling region. */
|
of the scheduling region. */
|
current_sched_info->next_tail = NEXT_INSN (BB_END (bb));
|
current_sched_info->next_tail = NEXT_INSN (BB_END (bb));
|
gcc_assert (current_sched_info->next_tail);
|
gcc_assert (current_sched_info->next_tail);
|
|
|
/* Append new basic block to the end of the ebb. */
|
/* Append new basic block to the end of the ebb. */
|
sched_init_only_bb (bb, last_bb);
|
sched_init_only_bb (bb, last_bb);
|
gcc_assert (last_bb == bb);
|
gcc_assert (last_bb == bb);
|
}
|
}
|
}
|
}
|
|
|
/* Return a string that contains the insn uid and optionally anything else
|
/* Return a string that contains the insn uid and optionally anything else
|
necessary to identify this insn in an output. It's valid to use a
|
necessary to identify this insn in an output. It's valid to use a
|
static buffer for this. The ALIGNED parameter should cause the string
|
static buffer for this. The ALIGNED parameter should cause the string
|
to be formatted so that multiple output lines will line up nicely. */
|
to be formatted so that multiple output lines will line up nicely. */
|
|
|
static const char *
|
static const char *
|
ebb_print_insn (const_rtx insn, int aligned ATTRIBUTE_UNUSED)
|
ebb_print_insn (const_rtx insn, int aligned ATTRIBUTE_UNUSED)
|
{
|
{
|
static char tmp[80];
|
static char tmp[80];
|
|
|
/* '+' before insn means it is a new cycle start. */
|
/* '+' before insn means it is a new cycle start. */
|
if (GET_MODE (insn) == TImode)
|
if (GET_MODE (insn) == TImode)
|
sprintf (tmp, "+ %4d", INSN_UID (insn));
|
sprintf (tmp, "+ %4d", INSN_UID (insn));
|
else
|
else
|
sprintf (tmp, " %4d", INSN_UID (insn));
|
sprintf (tmp, " %4d", INSN_UID (insn));
|
|
|
return tmp;
|
return tmp;
|
}
|
}
|
|
|
/* Compare priority of two insns. Return a positive number if the second
|
/* Compare priority of two insns. Return a positive number if the second
|
insn is to be preferred for scheduling, and a negative one if the first
|
insn is to be preferred for scheduling, and a negative one if the first
|
is to be preferred. Zero if they are equally good. */
|
is to be preferred. Zero if they are equally good. */
|
|
|
static int
|
static int
|
rank (rtx insn1, rtx insn2)
|
rank (rtx insn1, rtx insn2)
|
{
|
{
|
basic_block bb1 = BLOCK_FOR_INSN (insn1);
|
basic_block bb1 = BLOCK_FOR_INSN (insn1);
|
basic_block bb2 = BLOCK_FOR_INSN (insn2);
|
basic_block bb2 = BLOCK_FOR_INSN (insn2);
|
|
|
if (bb1->count > bb2->count
|
if (bb1->count > bb2->count
|
|| bb1->frequency > bb2->frequency)
|
|| bb1->frequency > bb2->frequency)
|
return -1;
|
return -1;
|
if (bb1->count < bb2->count
|
if (bb1->count < bb2->count
|
|| bb1->frequency < bb2->frequency)
|
|| bb1->frequency < bb2->frequency)
|
return 1;
|
return 1;
|
return 0;
|
return 0;
|
}
|
}
|
|
|
/* NEXT is an instruction that depends on INSN (a backward dependence);
|
/* NEXT is an instruction that depends on INSN (a backward dependence);
|
return nonzero if we should include this dependence in priority
|
return nonzero if we should include this dependence in priority
|
calculations. */
|
calculations. */
|
|
|
static int
|
static int
|
ebb_contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
|
ebb_contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
|
rtx insn ATTRIBUTE_UNUSED)
|
rtx insn ATTRIBUTE_UNUSED)
|
{
|
{
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* INSN is a JUMP_INSN, COND_SET is the set of registers that are
|
/* INSN is a JUMP_INSN, COND_SET is the set of registers that are
|
conditionally set before INSN. Store the set of registers that
|
conditionally set before INSN. Store the set of registers that
|
must be considered as used by this jump in USED and that of
|
must be considered as used by this jump in USED and that of
|
registers that must be considered as set in SET. */
|
registers that must be considered as set in SET. */
|
|
|
void
|
void
|
ebb_compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
|
ebb_compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
|
regset set)
|
regset set)
|
{
|
{
|
basic_block b = BLOCK_FOR_INSN (insn);
|
basic_block b = BLOCK_FOR_INSN (insn);
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
FOR_EACH_EDGE (e, ei, b->succs)
|
FOR_EACH_EDGE (e, ei, b->succs)
|
if (e->flags & EDGE_FALLTHRU)
|
if (e->flags & EDGE_FALLTHRU)
|
/* The jump may be a by-product of a branch that has been merged
|
/* The jump may be a by-product of a branch that has been merged
|
in the main codepath after being conditionalized. Therefore
|
in the main codepath after being conditionalized. Therefore
|
it may guard the fallthrough block from using a value that has
|
it may guard the fallthrough block from using a value that has
|
conditionally overwritten that of the main codepath. So we
|
conditionally overwritten that of the main codepath. So we
|
consider that it restores the value of the main codepath. */
|
consider that it restores the value of the main codepath. */
|
bitmap_and (set, df_get_live_in (e->dest), cond_set);
|
bitmap_and (set, df_get_live_in (e->dest), cond_set);
|
else
|
else
|
bitmap_ior_into (used, df_get_live_in (e->dest));
|
bitmap_ior_into (used, df_get_live_in (e->dest));
|
}
|
}
|
|
|
/* Used in schedule_insns to initialize current_sched_info for scheduling
|
/* Used in schedule_insns to initialize current_sched_info for scheduling
|
regions (or single basic blocks). */
|
regions (or single basic blocks). */
|
|
|
static struct common_sched_info_def ebb_common_sched_info;
|
static struct common_sched_info_def ebb_common_sched_info;
|
|
|
static struct sched_deps_info_def ebb_sched_deps_info =
|
static struct sched_deps_info_def ebb_sched_deps_info =
|
{
|
{
|
ebb_compute_jump_reg_dependencies,
|
ebb_compute_jump_reg_dependencies,
|
NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
|
NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
|
NULL,
|
NULL,
|
1, 0, 0
|
1, 0, 0
|
};
|
};
|
|
|
static struct haifa_sched_info ebb_sched_info =
|
static struct haifa_sched_info ebb_sched_info =
|
{
|
{
|
init_ready_list,
|
init_ready_list,
|
NULL,
|
NULL,
|
schedule_more_p,
|
schedule_more_p,
|
NULL,
|
NULL,
|
rank,
|
rank,
|
ebb_print_insn,
|
ebb_print_insn,
|
ebb_contributes_to_priority,
|
ebb_contributes_to_priority,
|
NULL, /* insn_finishes_block_p */
|
NULL, /* insn_finishes_block_p */
|
|
|
NULL, NULL,
|
NULL, NULL,
|
NULL, NULL,
|
NULL, NULL,
|
1, 0,
|
1, 0,
|
|
|
ebb_add_remove_insn,
|
ebb_add_remove_insn,
|
begin_schedule_ready,
|
begin_schedule_ready,
|
advance_target_bb,
|
advance_target_bb,
|
SCHED_EBB
|
SCHED_EBB
|
/* We can create new blocks in begin_schedule_ready (). */
|
/* We can create new blocks in begin_schedule_ready (). */
|
| NEW_BBS
|
| NEW_BBS
|
};
|
};
|
|
|
/* Returns the earliest block in EBB currently being processed where a
|
/* Returns the earliest block in EBB currently being processed where a
|
"similar load" 'insn2' is found, and hence LOAD_INSN can move
|
"similar load" 'insn2' is found, and hence LOAD_INSN can move
|
speculatively into the found block. All the following must hold:
|
speculatively into the found block. All the following must hold:
|
|
|
(1) both loads have 1 base register (PFREE_CANDIDATEs).
|
(1) both loads have 1 base register (PFREE_CANDIDATEs).
|
(2) load_insn and load2 have a def-use dependence upon
|
(2) load_insn and load2 have a def-use dependence upon
|
the same insn 'insn1'.
|
the same insn 'insn1'.
|
|
|
From all these we can conclude that the two loads access memory
|
From all these we can conclude that the two loads access memory
|
addresses that differ at most by a constant, and hence if moving
|
addresses that differ at most by a constant, and hence if moving
|
load_insn would cause an exception, it would have been caused by
|
load_insn would cause an exception, it would have been caused by
|
load2 anyhow.
|
load2 anyhow.
|
|
|
The function uses list (given by LAST_BLOCK) of already processed
|
The function uses list (given by LAST_BLOCK) of already processed
|
blocks in EBB. The list is formed in `add_deps_for_risky_insns'. */
|
blocks in EBB. The list is formed in `add_deps_for_risky_insns'. */
|
|
|
static basic_block
|
static basic_block
|
earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
|
earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
|
{
|
{
|
sd_iterator_def back_sd_it;
|
sd_iterator_def back_sd_it;
|
dep_t back_dep;
|
dep_t back_dep;
|
basic_block bb, earliest_block = NULL;
|
basic_block bb, earliest_block = NULL;
|
|
|
FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
|
FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
|
{
|
{
|
rtx insn1 = DEP_PRO (back_dep);
|
rtx insn1 = DEP_PRO (back_dep);
|
|
|
if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
|
if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
|
/* Found a DEF-USE dependence (insn1, load_insn). */
|
/* Found a DEF-USE dependence (insn1, load_insn). */
|
{
|
{
|
sd_iterator_def fore_sd_it;
|
sd_iterator_def fore_sd_it;
|
dep_t fore_dep;
|
dep_t fore_dep;
|
|
|
FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
|
FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
|
{
|
{
|
rtx insn2 = DEP_CON (fore_dep);
|
rtx insn2 = DEP_CON (fore_dep);
|
basic_block insn2_block = BLOCK_FOR_INSN (insn2);
|
basic_block insn2_block = BLOCK_FOR_INSN (insn2);
|
|
|
if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
|
if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
|
{
|
{
|
if (earliest_block != NULL
|
if (earliest_block != NULL
|
&& earliest_block->index < insn2_block->index)
|
&& earliest_block->index < insn2_block->index)
|
continue;
|
continue;
|
|
|
/* Found a DEF-USE dependence (insn1, insn2). */
|
/* Found a DEF-USE dependence (insn1, insn2). */
|
if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
|
if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
|
/* insn2 not guaranteed to be a 1 base reg load. */
|
/* insn2 not guaranteed to be a 1 base reg load. */
|
continue;
|
continue;
|
|
|
for (bb = last_block; bb; bb = (basic_block) bb->aux)
|
for (bb = last_block; bb; bb = (basic_block) bb->aux)
|
if (insn2_block == bb)
|
if (insn2_block == bb)
|
break;
|
break;
|
|
|
if (!bb)
|
if (!bb)
|
/* insn2 is the similar load. */
|
/* insn2 is the similar load. */
|
earliest_block = insn2_block;
|
earliest_block = insn2_block;
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
return earliest_block;
|
return earliest_block;
|
}
|
}
|
|
|
/* The following function adds dependencies between jumps and risky
|
/* The following function adds dependencies between jumps and risky
|
insns in given ebb. */
|
insns in given ebb. */
|
|
|
static void
|
static void
|
add_deps_for_risky_insns (rtx head, rtx tail)
|
add_deps_for_risky_insns (rtx head, rtx tail)
|
{
|
{
|
rtx insn, prev;
|
rtx insn, prev;
|
int classification;
|
int classification;
|
rtx last_jump = NULL_RTX;
|
rtx last_jump = NULL_RTX;
|
rtx next_tail = NEXT_INSN (tail);
|
rtx next_tail = NEXT_INSN (tail);
|
basic_block last_block = NULL, bb;
|
basic_block last_block = NULL, bb;
|
|
|
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
|
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
|
if (control_flow_insn_p (insn))
|
if (control_flow_insn_p (insn))
|
{
|
{
|
bb = BLOCK_FOR_INSN (insn);
|
bb = BLOCK_FOR_INSN (insn);
|
bb->aux = last_block;
|
bb->aux = last_block;
|
last_block = bb;
|
last_block = bb;
|
last_jump = insn;
|
last_jump = insn;
|
}
|
}
|
else if (INSN_P (insn) && last_jump != NULL_RTX)
|
else if (INSN_P (insn) && last_jump != NULL_RTX)
|
{
|
{
|
classification = haifa_classify_insn (insn);
|
classification = haifa_classify_insn (insn);
|
prev = last_jump;
|
prev = last_jump;
|
switch (classification)
|
switch (classification)
|
{
|
{
|
case PFREE_CANDIDATE:
|
case PFREE_CANDIDATE:
|
if (flag_schedule_speculative_load)
|
if (flag_schedule_speculative_load)
|
{
|
{
|
bb = earliest_block_with_similiar_load (last_block, insn);
|
bb = earliest_block_with_similiar_load (last_block, insn);
|
if (bb)
|
if (bb)
|
{
|
{
|
bb = (basic_block) bb->aux;
|
bb = (basic_block) bb->aux;
|
if (!bb)
|
if (!bb)
|
break;
|
break;
|
prev = BB_END (bb);
|
prev = BB_END (bb);
|
}
|
}
|
}
|
}
|
/* Fall through. */
|
/* Fall through. */
|
case TRAP_RISKY:
|
case TRAP_RISKY:
|
case IRISKY:
|
case IRISKY:
|
case PRISKY_CANDIDATE:
|
case PRISKY_CANDIDATE:
|
/* ??? We could implement better checking PRISKY_CANDIDATEs
|
/* ??? We could implement better checking PRISKY_CANDIDATEs
|
analogous to sched-rgn.c. */
|
analogous to sched-rgn.c. */
|
/* We can not change the mode of the backward
|
/* We can not change the mode of the backward
|
dependency because REG_DEP_ANTI has the lowest
|
dependency because REG_DEP_ANTI has the lowest
|
rank. */
|
rank. */
|
if (! sched_insns_conditions_mutex_p (insn, prev))
|
if (! sched_insns_conditions_mutex_p (insn, prev))
|
{
|
{
|
dep_def _dep, *dep = &_dep;
|
dep_def _dep, *dep = &_dep;
|
|
|
init_dep (dep, prev, insn, REG_DEP_ANTI);
|
init_dep (dep, prev, insn, REG_DEP_ANTI);
|
|
|
if (!(current_sched_info->flags & USE_DEPS_LIST))
|
if (!(current_sched_info->flags & USE_DEPS_LIST))
|
{
|
{
|
enum DEPS_ADJUST_RESULT res;
|
enum DEPS_ADJUST_RESULT res;
|
|
|
res = sd_add_or_update_dep (dep, false);
|
res = sd_add_or_update_dep (dep, false);
|
|
|
/* We can't change an existing dependency with
|
/* We can't change an existing dependency with
|
DEP_ANTI. */
|
DEP_ANTI. */
|
gcc_assert (res != DEP_CHANGED);
|
gcc_assert (res != DEP_CHANGED);
|
}
|
}
|
else
|
else
|
{
|
{
|
if ((current_sched_info->flags & DO_SPECULATION)
|
if ((current_sched_info->flags & DO_SPECULATION)
|
&& (spec_info->mask & BEGIN_CONTROL))
|
&& (spec_info->mask & BEGIN_CONTROL))
|
DEP_STATUS (dep) = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
|
DEP_STATUS (dep) = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
|
MAX_DEP_WEAK);
|
MAX_DEP_WEAK);
|
|
|
sd_add_or_update_dep (dep, false);
|
sd_add_or_update_dep (dep, false);
|
|
|
/* Dep_status could have been changed.
|
/* Dep_status could have been changed.
|
No assertion here. */
|
No assertion here. */
|
}
|
}
|
}
|
}
|
|
|
break;
|
break;
|
|
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
}
|
}
|
/* Maintain the invariant that bb->aux is clear after use. */
|
/* Maintain the invariant that bb->aux is clear after use. */
|
while (last_block)
|
while (last_block)
|
{
|
{
|
bb = (basic_block) last_block->aux;
|
bb = (basic_block) last_block->aux;
|
last_block->aux = NULL;
|
last_block->aux = NULL;
|
last_block = bb;
|
last_block = bb;
|
}
|
}
|
}
|
}
|
|
|
/* Schedule a single extended basic block, defined by the boundaries HEAD
|
/* Schedule a single extended basic block, defined by the boundaries HEAD
|
and TAIL. */
|
and TAIL. */
|
|
|
static basic_block
|
static basic_block
|
schedule_ebb (rtx head, rtx tail)
|
schedule_ebb (rtx head, rtx tail)
|
{
|
{
|
basic_block first_bb, target_bb;
|
basic_block first_bb, target_bb;
|
struct deps_desc tmp_deps;
|
struct deps_desc tmp_deps;
|
|
|
first_bb = BLOCK_FOR_INSN (head);
|
first_bb = BLOCK_FOR_INSN (head);
|
last_bb = BLOCK_FOR_INSN (tail);
|
last_bb = BLOCK_FOR_INSN (tail);
|
|
|
if (no_real_insns_p (head, tail))
|
if (no_real_insns_p (head, tail))
|
return BLOCK_FOR_INSN (tail);
|
return BLOCK_FOR_INSN (tail);
|
|
|
gcc_assert (INSN_P (head) && INSN_P (tail));
|
gcc_assert (INSN_P (head) && INSN_P (tail));
|
|
|
if (!bitmap_bit_p (&dont_calc_deps, first_bb->index))
|
if (!bitmap_bit_p (&dont_calc_deps, first_bb->index))
|
{
|
{
|
init_deps_global ();
|
init_deps_global ();
|
|
|
/* Compute dependencies. */
|
/* Compute dependencies. */
|
init_deps (&tmp_deps, false);
|
init_deps (&tmp_deps, false);
|
sched_analyze (&tmp_deps, head, tail);
|
sched_analyze (&tmp_deps, head, tail);
|
free_deps (&tmp_deps);
|
free_deps (&tmp_deps);
|
|
|
add_deps_for_risky_insns (head, tail);
|
add_deps_for_risky_insns (head, tail);
|
|
|
if (targetm.sched.dependencies_evaluation_hook)
|
if (targetm.sched.dependencies_evaluation_hook)
|
targetm.sched.dependencies_evaluation_hook (head, tail);
|
targetm.sched.dependencies_evaluation_hook (head, tail);
|
|
|
finish_deps_global ();
|
finish_deps_global ();
|
}
|
}
|
else
|
else
|
/* Only recovery blocks can have their dependencies already calculated,
|
/* Only recovery blocks can have their dependencies already calculated,
|
and they always are single block ebbs. */
|
and they always are single block ebbs. */
|
gcc_assert (first_bb == last_bb);
|
gcc_assert (first_bb == last_bb);
|
|
|
/* Set priorities. */
|
/* Set priorities. */
|
current_sched_info->sched_max_insns_priority = 0;
|
current_sched_info->sched_max_insns_priority = 0;
|
rgn_n_insns = set_priorities (head, tail);
|
rgn_n_insns = set_priorities (head, tail);
|
current_sched_info->sched_max_insns_priority++;
|
current_sched_info->sched_max_insns_priority++;
|
|
|
current_sched_info->prev_head = PREV_INSN (head);
|
current_sched_info->prev_head = PREV_INSN (head);
|
current_sched_info->next_tail = NEXT_INSN (tail);
|
current_sched_info->next_tail = NEXT_INSN (tail);
|
|
|
remove_notes (head, tail);
|
remove_notes (head, tail);
|
|
|
unlink_bb_notes (first_bb, last_bb);
|
unlink_bb_notes (first_bb, last_bb);
|
|
|
target_bb = first_bb;
|
target_bb = first_bb;
|
|
|
/* Make ready list big enough to hold all the instructions from the ebb. */
|
/* Make ready list big enough to hold all the instructions from the ebb. */
|
sched_extend_ready_list (rgn_n_insns);
|
sched_extend_ready_list (rgn_n_insns);
|
schedule_block (&target_bb);
|
schedule_block (&target_bb);
|
/* Free ready list. */
|
/* Free ready list. */
|
sched_finish_ready_list ();
|
sched_finish_ready_list ();
|
|
|
/* We might pack all instructions into fewer blocks,
|
/* We might pack all instructions into fewer blocks,
|
so we may made some of them empty. Can't assert (b == last_bb). */
|
so we may made some of them empty. Can't assert (b == last_bb). */
|
|
|
/* Sanity check: verify that all region insns were scheduled. */
|
/* Sanity check: verify that all region insns were scheduled. */
|
gcc_assert (sched_rgn_n_insns == rgn_n_insns);
|
gcc_assert (sched_rgn_n_insns == rgn_n_insns);
|
|
|
/* Free dependencies. */
|
/* Free dependencies. */
|
sched_free_deps (current_sched_info->head, current_sched_info->tail, true);
|
sched_free_deps (current_sched_info->head, current_sched_info->tail, true);
|
|
|
gcc_assert (haifa_recovery_bb_ever_added_p
|
gcc_assert (haifa_recovery_bb_ever_added_p
|
|| deps_pools_are_empty_p ());
|
|| deps_pools_are_empty_p ());
|
|
|
if (EDGE_COUNT (last_bb->preds) == 0)
|
if (EDGE_COUNT (last_bb->preds) == 0)
|
/* LAST_BB is unreachable. */
|
/* LAST_BB is unreachable. */
|
{
|
{
|
gcc_assert (first_bb != last_bb
|
gcc_assert (first_bb != last_bb
|
&& EDGE_COUNT (last_bb->succs) == 0);
|
&& EDGE_COUNT (last_bb->succs) == 0);
|
last_bb = last_bb->prev_bb;
|
last_bb = last_bb->prev_bb;
|
delete_basic_block (last_bb->next_bb);
|
delete_basic_block (last_bb->next_bb);
|
}
|
}
|
|
|
return last_bb;
|
return last_bb;
|
}
|
}
|
|
|
/* The one entry point in this file. */
|
/* The one entry point in this file. */
|
|
|
void
|
void
|
schedule_ebbs (void)
|
schedule_ebbs (void)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
int probability_cutoff;
|
int probability_cutoff;
|
rtx tail;
|
rtx tail;
|
|
|
if (profile_info && flag_branch_probabilities)
|
if (profile_info && flag_branch_probabilities)
|
probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
|
probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
|
else
|
else
|
probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
|
probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
|
probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
|
probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
|
|
|
/* Taking care of this degenerate case makes the rest of
|
/* Taking care of this degenerate case makes the rest of
|
this code simpler. */
|
this code simpler. */
|
if (n_basic_blocks == NUM_FIXED_BLOCKS)
|
if (n_basic_blocks == NUM_FIXED_BLOCKS)
|
return;
|
return;
|
|
|
/* Setup infos. */
|
/* Setup infos. */
|
{
|
{
|
memcpy (&ebb_common_sched_info, &haifa_common_sched_info,
|
memcpy (&ebb_common_sched_info, &haifa_common_sched_info,
|
sizeof (ebb_common_sched_info));
|
sizeof (ebb_common_sched_info));
|
|
|
ebb_common_sched_info.fix_recovery_cfg = ebb_fix_recovery_cfg;
|
ebb_common_sched_info.fix_recovery_cfg = ebb_fix_recovery_cfg;
|
ebb_common_sched_info.add_block = ebb_add_block;
|
ebb_common_sched_info.add_block = ebb_add_block;
|
ebb_common_sched_info.sched_pass_id = SCHED_EBB_PASS;
|
ebb_common_sched_info.sched_pass_id = SCHED_EBB_PASS;
|
|
|
common_sched_info = &ebb_common_sched_info;
|
common_sched_info = &ebb_common_sched_info;
|
sched_deps_info = &ebb_sched_deps_info;
|
sched_deps_info = &ebb_sched_deps_info;
|
current_sched_info = &ebb_sched_info;
|
current_sched_info = &ebb_sched_info;
|
}
|
}
|
|
|
haifa_sched_init ();
|
haifa_sched_init ();
|
|
|
compute_bb_for_insn ();
|
compute_bb_for_insn ();
|
|
|
/* Initialize DONT_CALC_DEPS and ebb-{start, end} markers. */
|
/* Initialize DONT_CALC_DEPS and ebb-{start, end} markers. */
|
bitmap_initialize (&dont_calc_deps, 0);
|
bitmap_initialize (&dont_calc_deps, 0);
|
bitmap_clear (&dont_calc_deps);
|
bitmap_clear (&dont_calc_deps);
|
|
|
/* Schedule every region in the subroutine. */
|
/* Schedule every region in the subroutine. */
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
rtx head = BB_HEAD (bb);
|
rtx head = BB_HEAD (bb);
|
|
|
for (;;)
|
for (;;)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
tail = BB_END (bb);
|
tail = BB_END (bb);
|
if (bb->next_bb == EXIT_BLOCK_PTR
|
if (bb->next_bb == EXIT_BLOCK_PTR
|
|| LABEL_P (BB_HEAD (bb->next_bb)))
|
|| LABEL_P (BB_HEAD (bb->next_bb)))
|
break;
|
break;
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
if ((e->flags & EDGE_FALLTHRU) != 0)
|
if ((e->flags & EDGE_FALLTHRU) != 0)
|
break;
|
break;
|
if (! e)
|
if (! e)
|
break;
|
break;
|
if (e->probability <= probability_cutoff)
|
if (e->probability <= probability_cutoff)
|
break;
|
break;
|
bb = bb->next_bb;
|
bb = bb->next_bb;
|
}
|
}
|
|
|
/* Blah. We should fix the rest of the code not to get confused by
|
/* Blah. We should fix the rest of the code not to get confused by
|
a note or two. */
|
a note or two. */
|
while (head != tail)
|
while (head != tail)
|
{
|
{
|
if (NOTE_P (head) || BOUNDARY_DEBUG_INSN_P (head))
|
if (NOTE_P (head) || BOUNDARY_DEBUG_INSN_P (head))
|
head = NEXT_INSN (head);
|
head = NEXT_INSN (head);
|
else if (NOTE_P (tail) || BOUNDARY_DEBUG_INSN_P (tail))
|
else if (NOTE_P (tail) || BOUNDARY_DEBUG_INSN_P (tail))
|
tail = PREV_INSN (tail);
|
tail = PREV_INSN (tail);
|
else if (LABEL_P (head))
|
else if (LABEL_P (head))
|
head = NEXT_INSN (head);
|
head = NEXT_INSN (head);
|
else
|
else
|
break;
|
break;
|
}
|
}
|
|
|
bb = schedule_ebb (head, tail);
|
bb = schedule_ebb (head, tail);
|
}
|
}
|
bitmap_clear (&dont_calc_deps);
|
bitmap_clear (&dont_calc_deps);
|
|
|
/* Reposition the prologue and epilogue notes in case we moved the
|
/* Reposition the prologue and epilogue notes in case we moved the
|
prologue/epilogue insns. */
|
prologue/epilogue insns. */
|
if (reload_completed)
|
if (reload_completed)
|
reposition_prologue_and_epilogue_notes ();
|
reposition_prologue_and_epilogue_notes ();
|
|
|
haifa_sched_finish ();
|
haifa_sched_finish ();
|
}
|
}
|
|
|
/* INSN has been added to/removed from current ebb. */
|
/* INSN has been added to/removed from current ebb. */
|
static void
|
static void
|
ebb_add_remove_insn (rtx insn ATTRIBUTE_UNUSED, int remove_p)
|
ebb_add_remove_insn (rtx insn ATTRIBUTE_UNUSED, int remove_p)
|
{
|
{
|
if (!remove_p)
|
if (!remove_p)
|
rgn_n_insns++;
|
rgn_n_insns++;
|
else
|
else
|
rgn_n_insns--;
|
rgn_n_insns--;
|
}
|
}
|
|
|
/* BB was added to ebb after AFTER. */
|
/* BB was added to ebb after AFTER. */
|
static void
|
static void
|
ebb_add_block (basic_block bb, basic_block after)
|
ebb_add_block (basic_block bb, basic_block after)
|
{
|
{
|
/* Recovery blocks are always bounded by BARRIERS,
|
/* Recovery blocks are always bounded by BARRIERS,
|
therefore, they always form single block EBB,
|
therefore, they always form single block EBB,
|
therefore, we can use rec->index to identify such EBBs. */
|
therefore, we can use rec->index to identify such EBBs. */
|
if (after == EXIT_BLOCK_PTR)
|
if (after == EXIT_BLOCK_PTR)
|
bitmap_set_bit (&dont_calc_deps, bb->index);
|
bitmap_set_bit (&dont_calc_deps, bb->index);
|
else if (after == last_bb)
|
else if (after == last_bb)
|
last_bb = bb;
|
last_bb = bb;
|
}
|
}
|
|
|
/* Return next block in ebb chain. For parameter meaning please refer to
|
/* Return next block in ebb chain. For parameter meaning please refer to
|
sched-int.h: struct sched_info: advance_target_bb. */
|
sched-int.h: struct sched_info: advance_target_bb. */
|
static basic_block
|
static basic_block
|
advance_target_bb (basic_block bb, rtx insn)
|
advance_target_bb (basic_block bb, rtx insn)
|
{
|
{
|
if (insn)
|
if (insn)
|
{
|
{
|
if (BLOCK_FOR_INSN (insn) != bb
|
if (BLOCK_FOR_INSN (insn) != bb
|
&& control_flow_insn_p (insn)
|
&& control_flow_insn_p (insn)
|
/* We handle interblock movement of the speculation check
|
/* We handle interblock movement of the speculation check
|
or over a speculation check in
|
or over a speculation check in
|
haifa-sched.c: move_block_after_check (). */
|
haifa-sched.c: move_block_after_check (). */
|
&& !IS_SPECULATION_BRANCHY_CHECK_P (insn)
|
&& !IS_SPECULATION_BRANCHY_CHECK_P (insn)
|
&& !IS_SPECULATION_BRANCHY_CHECK_P (BB_END (bb)))
|
&& !IS_SPECULATION_BRANCHY_CHECK_P (BB_END (bb)))
|
{
|
{
|
/* Assert that we don't move jumps across blocks. */
|
/* Assert that we don't move jumps across blocks. */
|
gcc_assert (!control_flow_insn_p (BB_END (bb))
|
gcc_assert (!control_flow_insn_p (BB_END (bb))
|
&& NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb->next_bb)));
|
&& NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb->next_bb)));
|
return bb;
|
return bb;
|
}
|
}
|
else
|
else
|
return 0;
|
return 0;
|
}
|
}
|
else
|
else
|
/* Return next non empty block. */
|
/* Return next non empty block. */
|
{
|
{
|
do
|
do
|
{
|
{
|
gcc_assert (bb != last_bb);
|
gcc_assert (bb != last_bb);
|
|
|
bb = bb->next_bb;
|
bb = bb->next_bb;
|
}
|
}
|
while (bb_note (bb) == BB_END (bb));
|
while (bb_note (bb) == BB_END (bb));
|
|
|
return bb;
|
return bb;
|
}
|
}
|
}
|
}
|
|
|
/* Fix internal data after interblock movement of jump instruction.
|
/* Fix internal data after interblock movement of jump instruction.
|
For parameter meaning please refer to
|
For parameter meaning please refer to
|
sched-int.h: struct sched_info: fix_recovery_cfg. */
|
sched-int.h: struct sched_info: fix_recovery_cfg. */
|
static void
|
static void
|
ebb_fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED, int jump_bbi,
|
ebb_fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED, int jump_bbi,
|
int jump_bb_nexti)
|
int jump_bb_nexti)
|
{
|
{
|
gcc_assert (last_bb->index != bbi);
|
gcc_assert (last_bb->index != bbi);
|
|
|
if (jump_bb_nexti == last_bb->index)
|
if (jump_bb_nexti == last_bb->index)
|
last_bb = BASIC_BLOCK (jump_bbi);
|
last_bb = BASIC_BLOCK (jump_bbi);
|
}
|
}
|
|
|
#endif /* INSN_SCHEDULING */
|
#endif /* INSN_SCHEDULING */
|
|
|
