/* Instruction scheduling pass. This file contains definitions used
internally in the scheduler.
- Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
This file is part of GCC.
/* For state_t. */
#include "insn-attr.h"
-/* For regset_head. */
+#include "regset.h"
#include "basic-block.h"
/* For reg_note. */
#include "rtl.h"
#define ILIST_INSN(L) (_XLIST_X (L))
#define ILIST_NEXT(L) (_XLIST_NEXT (L))
-/* This lists possible transformations that done locally, i.e. in
+/* This lists possible transformations that done locally, i.e. in
moveup_expr. */
enum local_trans_type
{
TRANS_SPECULATION
};
-/* This struct is used to record the history of expression's
+/* This struct is used to record the history of expression's
transformations. */
struct expr_history_def_1
{
control on scheduling. */
int spec;
- /* Degree of speculativeness measured as probability of executing
- instruction's original basic block given relative to
+ /* Degree of speculativeness measured as probability of executing
+ instruction's original basic block given relative to
the current scheduling point. */
int usefulness;
/* Number of times the insn was scheduled. */
int sched_times;
- /* A basic block index this was originated from. Zero when there is
+ /* A basic block index this was originated from. Zero when there is
more than one originator. */
int orig_bb_index;
(used only during move_op ()). */
ds_t spec_to_check_ds;
- /* Cycle on which original insn was scheduled. Zero when it has not yet
+ /* Cycle on which original insn was scheduled. Zero when it has not yet
been scheduled or more than one originator. */
int orig_sched_cycle;
/* This vector contains the history of insn's transformations. */
VEC(expr_history_def, heap) *history_of_changes;
- /* True (1) when original target (register or memory) of this instruction
+ /* True (1) when original target (register or memory) of this instruction
is available for scheduling, false otherwise. -1 means we're not sure;
please run find_used_regs to clarify. */
signed char target_available;
- /* True when this expression needs a speculation check to be scheduled.
+ /* True when this expression needs a speculation check to be scheduled.
This is used during find_used_regs. */
BOOL_BITFIELD needs_spec_check_p : 1;
- /* True when the expression was substituted. Used for statistical
+ /* True when the expression was substituted. Used for statistical
purposes. */
BOOL_BITFIELD was_substituted : 1;
#define EXPR_CANT_MOVE(EXPR) ((EXPR)->cant_move)
#define EXPR_WAS_CHANGED(EXPR) (VEC_length (expr_history_def, \
- EXPR_HISTORY_OF_CHANGES (EXPR)) > 0)
+ EXPR_HISTORY_OF_CHANGES (EXPR)) > 0)
/* Insn definition for list of original insns in find_used_regs. */
struct _def
/* FIXME: Get rid of CROSSES_CALL in each def, since if we're moving up
rhs from two different places, but only one of the code motion paths
- crosses a call, we can't use any of the call_used_regs, no matter which
+ crosses a call, we can't use any of the call_used_regs, no matter which
path or whether all paths crosses a call. Thus we should move CROSSES_CALL
to static params. */
bool crosses_call;
/* This set moved to the fence. */
av_set_t av1;
-
+
/* Deps context at this boundary. As long as we have one boundary per fence,
this is just a pointer to the same deps context as in the corresponding
fence. */
/* A vector of insns that are scheduled but not yet completed. */
VEC (rtx,gc) *executing_insns;
- /* A vector indexed by UIDs that caches the earliest cycle on which
+ /* A vector indexed by UIDs that caches the earliest cycle on which
an insn can be scheduled on this fence. */
int *ready_ticks;
/* Insn, which has been scheduled last on this fence. */
rtx last_scheduled_insn;
+ /* The last value of can_issue_more variable on this fence. */
+ int issue_more;
+
/* If non-NULL force the next scheduled insn to be SCHED_NEXT. */
rtx sched_next;
#define FENCE_DC(F) ((F)->dc)
#define FENCE_TC(F) ((F)->tc)
#define FENCE_LAST_SCHEDULED_INSN(F) ((F)->last_scheduled_insn)
+#define FENCE_ISSUE_MORE(F) ((F)->issue_more)
#define FENCE_EXECUTING_INSNS(F) ((F)->executing_insns)
#define FENCE_READY_TICKS(F) ((F)->ready_ticks)
#define FENCE_READY_TICKS_SIZE(F) ((F)->ready_ticks_size)
#define _FOR_EACH_1(TYPE, ELEM, I, LP) \
for (_list_iter_start (&(I), (LP), true); \
_list_iter_cond_##TYPE (*(I).lp, &(ELEM)); \
- _list_iter_next (&(I)))
+ _list_iter_next (&(I)))
\f
/* _xlist_t functions. */
#define VINSN_MAY_TRAP_P(VI) ((VI)->may_trap_p)
\f
-/* An entry of the hashtable describing transformations happened when
+/* An entry of the hashtable describing transformations happened when
moving up through an insn. */
struct transformed_insns
{
/* An INSN_UID bit is set when deps analysis result is already known. */
bitmap analyzed_deps;
- /* An INSN_UID bit is set when a hard dep was found, not set when
+ /* An INSN_UID bit is set when a hard dep was found, not set when
no dependence is found. This is meaningful only when the analyzed_deps
bitmap has its bit set. */
bitmap found_deps;
- /* An INSN_UID bit is set when this is a bookkeeping insn generated from
- a parent with this uid. */
+ /* An INSN_UID bit is set when this is a bookkeeping insn generated from
+ a parent with this uid. If a parent is a bookkeeping copy, all its
+ originators are transitively included in this set. */
bitmap originators;
/* A hashtable caching the result of insn transformations through this one. */
htab_t transformed_insns;
-
+
/* A context incapsulating this insn. */
struct deps deps_context;
#define INSN_ASM_P(INSN) (SID (INSN)->asm_p)
#define INSN_SCHED_NEXT(INSN) (SID (INSN)->sched_next)
#define INSN_ANALYZED_DEPS(INSN) (SID (INSN)->analyzed_deps)
-#define INSN_FOUND_DEPS(INSN) (SID (INSN)->found_deps)
-#define INSN_DEPS_CONTEXT(INSN) (SID (INSN)->deps_context)
+#define INSN_FOUND_DEPS(INSN) (SID (INSN)->found_deps)
+#define INSN_DEPS_CONTEXT(INSN) (SID (INSN)->deps_context)
#define INSN_ORIGINATORS(INSN) (SID (INSN)->originators)
#define INSN_ORIGINATORS_BY_UID(UID) (SID_BY_UID (UID)->originators)
#define INSN_TRANSFORMED_INSNS(INSN) (SID (INSN)->transformed_insns)
#define BB_LV_SET_VALID_P(BB) (SEL_GLOBAL_BB_INFO (BB)->lv_set_valid_p)
/* Per basic block data for the region. */
-typedef struct
+typedef struct
{
/* This insn stream is constructed in such a way that it should be
traversed by PREV_INSN field - (*not* NEXT_INSN). */
extern bool enable_moveup_set_path_p;
extern bool pipelining_p;
extern bool bookkeeping_p;
-extern int max_insns_to_rename;
+extern int max_insns_to_rename;
extern bool preheader_removed;
/* Software lookahead window size.
- According to the results in Nakatani and Ebcioglu [1993], window size of 16
+ According to the results in Nakatani and Ebcioglu [1993], window size of 16
is enough to extract most ILP in integer code. */
#define MAX_WS (PARAM_VALUE (PARAM_SELSCHED_MAX_LOOKAHEAD))
/* The previous edge saved after skipping empty blocks. */
edge e2;
-
+
/* Edge iterator used when there are successors in other basic blocks. */
edge_iterator ei;
/* Flags that are passed to the iterator. We return only successors
that comply to these flags. */
short flags;
-
- /* When flags include SUCCS_ALL, this will be set to the exact type
+
+ /* When flags include SUCCS_ALL, this will be set to the exact type
of the sucessor we're traversing now. */
short current_flags;
/* Successors that correspond to the flags. */
insn_vec_t succs_ok;
- /* Their probabilities. As of now, we don't need this for other
+ /* Their probabilities. As of now, we don't need this for other
successors. */
VEC(int,heap) *probs_ok;
static inline bool
inner_loop_header_p (basic_block bb)
{
- struct loop *inner_loop;
+ struct loop *inner_loop;
if (!current_loop_nest)
return false;
return true;
}
- return false;
+ return false;
}
/* Return exit edges of LOOP, filtering out edges with the same dest bb. */
int i;
edge e;
bool was_dest = false;
-
+
for (i = 0; VEC_iterate (edge, edges, i, e); i++)
if (e->dest == exit->e->dest)
{
return true;
}
-/* Collect all loop exits recursively, skipping empty BBs between them.
+/* Collect all loop exits recursively, skipping empty BBs between them.
E.g. if BB is a loop header which has several loop exits,
traverse all of them and if any of them turns out to be another loop header
- (after skipping empty BBs), add its loop exits to the resulting vector
+ (after skipping empty BBs), add its loop exits to the resulting vector
as well. */
static inline VEC(edge, heap) *
get_all_loop_exits (basic_block bb)
struct loop *pred_loop = NULL;
int i;
edge e;
-
+
for (this_loop = bb->loop_father;
this_loop && this_loop != current_loop_nest;
this_loop = loop_outer (this_loop))
pred_loop = this_loop;
-
+
this_loop = pred_loop;
gcc_assert (this_loop != NULL);
/* Traverse all loop headers. */
for (i = 0; VEC_iterate (edge, exits, i, e); i++)
- if (in_current_region_p (e->dest))
+ if (in_current_region_p (e->dest)
+ || inner_loop_header_p (e->dest))
{
VEC(edge, heap) *next_exits = get_all_loop_exits (e->dest);
-
+
if (next_exits)
{
int j;
edge ne;
-
+
/* Add all loop exits for the current edge into the
resulting vector. */
for (j = 0; VEC_iterate (edge, next_exits, j, ne); j++)
VEC_safe_push (edge, heap, exits, ne);
-
+
/* Remove the original edge. */
VEC_ordered_remove (edge, exits, i);
/* Include successors that are outside of the current region. */
#define SUCCS_OUT (4)
-/* When pipelining of the outer loops is enabled, skip innermost loops
+/* When pipelining of the outer loops is enabled, skip innermost loops
to their exits. */
#define SUCCS_SKIP_TO_LOOP_EXITS (8)
}
else
{
- while (1)
+ while (1)
{
edge e_tmp = NULL;
{
do
{
- VEC_iterate (edge, ip->loop_exits,
+ VEC_iterate (edge, ip->loop_exits,
ip->current_exit, e_tmp);
ip->current_exit++;
}
while (e_tmp && !check (e_tmp, ip));
-
+
if (!e_tmp)
VEC_free (edge, heap, ip->loop_exits);
}
/* Consider bb as a possible loop header. */
if ((ip->flags & SUCCS_SKIP_TO_LOOP_EXITS)
&& flag_sel_sched_pipelining_outer_loops
- && (!in_current_region_p (bb)
- || BLOCK_TO_BB (ip->bb->index)
+ && (!in_current_region_p (bb)
+ || BLOCK_TO_BB (ip->bb->index)
< BLOCK_TO_BB (bb->index)))
{
/* Get all loop exits recursively. */
if (ip->loop_exits)
{
ip->current_exit = 0;
- /* Move the iterator now, because we won't do
+ /* Move the iterator now, because we won't do
succ_iter_next until loop exits will end. */
ei_next (&(ip->ei));
break;
bb = nbb;
continue;
}
-
- if (!in_current_region_p (bb)
+
+ if (!in_current_region_p (bb)
&& !(flags & SUCCS_OUT))
return false;
e2 = EDGE_SUCC (bb, 0);
bb = e2->dest;
}
-
+
/* Save the second edge for later checks. */
ip->e2 = e2;
if (in_current_region_p (bb))
{
- /* BLOCK_TO_BB sets topological order of the region here.
- It is important to use real predecessor here, which is ip->bb,
- as we may well have e1->src outside current region,
+ /* BLOCK_TO_BB sets topological order of the region here.
+ It is important to use real predecessor here, which is ip->bb,
+ as we may well have e1->src outside current region,
when skipping to loop exits. */
bool succeeds_in_top_order = (BLOCK_TO_BB (ip->bb->index)
< BLOCK_TO_BB (bb->index));
/* This is true for the all cases except the last one. */
ip->current_flags = SUCCS_NORMAL;
-
+
/* We are advancing forward in the region, as usual. */
if (succeeds_in_top_order)
{
return !!(flags & SUCCS_NORMAL);
}
- /* This is a back edge. During pipelining we ignore back edges,
+ /* This is a back edge. During pipelining we ignore back edges,
but only when it leads to the same loop. It can lead to the header
- of the outer loop, which will also be the preheader of
+ of the outer loop, which will also be the preheader of
the current loop. */
if (pipelining_p
&& e1->src->loop_father == bb->loop_father)
case 0:
return bb->next_bb;
- case 1:
+ case 1:
return single_succ (bb);
case 2:
return FALLTHRU_EDGE (bb)->dest;
-
+
default:
return bb->next_bb;
}
extern void merge_expr (expr_t, expr_t, insn_t);
extern void clear_expr (expr_t);
extern unsigned expr_dest_regno (expr_t);
-extern rtx expr_dest_reg (expr_t);
-extern int find_in_history_vect (VEC(expr_history_def, heap) *,
+extern rtx expr_dest_reg (expr_t);
+extern int find_in_history_vect (VEC(expr_history_def, heap) *,
rtx, vinsn_t, bool);
-extern void insert_in_history_vect (VEC(expr_history_def, heap) **,
- unsigned, enum local_trans_type,
+extern void insert_in_history_vect (VEC(expr_history_def, heap) **,
+ unsigned, enum local_trans_type,
vinsn_t, vinsn_t, ds_t);
extern void mark_unavailable_targets (av_set_t, av_set_t, regset);
extern int speculate_expr (expr_t, ds_t);
extern void free_bb_note_pool (void);
extern void sel_remove_empty_bb (basic_block, bool, bool);
-extern bool maybe_tidy_empty_bb (basic_block bb);
+extern void purge_empty_blocks (void);
extern basic_block sel_split_edge (edge);
extern basic_block sel_create_recovery_block (insn_t);
extern void sel_merge_blocks (basic_block, basic_block);
-extern void sel_redirect_edge_and_branch (edge, basic_block);
+extern bool sel_redirect_edge_and_branch (edge, basic_block);
extern void sel_redirect_edge_and_branch_force (edge, basic_block);
extern void sel_init_pipelining (void);
extern void sel_finish_pipelining (void);
extern void free_lv_sets (void);
extern void setup_nop_and_exit_insns (void);
extern void free_nop_and_exit_insns (void);
+extern void free_data_for_scheduled_insn (insn_t);
extern void setup_nop_vinsn (void);
extern void free_nop_vinsn (void);
extern void sel_set_sched_flags (void);
OSDN Git Service
