diff --git a/gcc/common.opt b/gcc/common.opt index d1f286f..3a7114d 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1695,6 +1695,10 @@ fsel-sched-reschedule-pipelined Common Report Var(flag_sel_sched_reschedule_pipelined) Init(0) Optimization Reschedule pipelined regions without pipelining +fsel-sched-predication +Common Report Var(flag_sel_sched_predication) Init(0) Optimization +Perform predication in selective scheduling + ; sched_stalled_insns means that insns can be moved prematurely from the queue ; of stalled insns into the ready list. fsched-stalled-insns diff --git a/gcc/config/ia64/ia64.c b/gcc/config/ia64/ia64.c index 78d2441..94dbff2 100644 --- a/gcc/config/ia64/ia64.c +++ b/gcc/config/ia64/ia64.c @@ -7640,6 +7640,15 @@ get_mode_no_for_insn (rtx insn) int mode_no; bool extend_p; + /* Extract mode of predicated loads to allow transforming them into a + speculative form. */ + if (flag_sel_sched_predication && GET_CODE (PATTERN (insn)) == COND_EXEC) + { + rtx cond = COND_EXEC_TEST (PATTERN (insn)); + if (GET_CODE (cond) != UNSPEC) + insn = make_insn_raw (COND_EXEC_CODE (PATTERN (insn))); + } + extract_insn_cached (insn); /* We use WHICH_ALTERNATIVE only after reload. This will diff --git a/gcc/rtl.h b/gcc/rtl.h index f2c2983..ec76b0c 100644 --- a/gcc/rtl.h +++ b/gcc/rtl.h @@ -1378,6 +1378,16 @@ do { \ #define COND_EXEC_TEST(RTX) XCEXP (RTX, 0, COND_EXEC) #define COND_EXEC_CODE(RTX) XCEXP (RTX, 1, COND_EXEC) +/* Obtain a pointer to SET_SRC or SET_DEST of a SET which may be wrapped + in a COND_EXEC. */ +#define COND_SET_SRC_PTR(x) (GET_CODE (x) == COND_EXEC \ + ? &SET_SRC (COND_EXEC_CODE (x)) \ + : &SET_SRC (x)) + +#define COND_SET_DEST_PTR(x) (GET_CODE (x) == COND_EXEC \ + ? &SET_DEST (COND_EXEC_CODE (x)) \ + : &SET_DEST (x)) + /* 1 if RTX is a symbol_ref that addresses this function's rtl constants pool. */ #define CONSTANT_POOL_ADDRESS_P(RTX) \ diff --git a/gcc/sched-deps.c b/gcc/sched-deps.c index a82df5d..92f4b7c 100644 --- a/gcc/sched-deps.c +++ b/gcc/sched-deps.c @@ -459,7 +459,6 @@ static void sched_analyze_2 (struct deps_desc *, rtx, rtx); static void sched_analyze_insn (struct deps_desc *, rtx, rtx); static bool sched_has_condition_p (const_rtx); -static int conditions_mutex_p (const_rtx, const_rtx, bool, bool); static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool, rtx, rtx); @@ -571,7 +570,7 @@ sched_has_condition_p (const_rtx insn) /* Return nonzero if conditions COND1 and COND2 can never be both true. */ static int -conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2) +conditions_mutex_with_rev_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2) { if (COMPARISON_P (cond1) && COMPARISON_P (cond2) @@ -585,6 +584,27 @@ conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2) return 0; } +/* Return true iff COND1 and COND2 are opposite. */ +bool +conditions_mutex_p (const_rtx cond1, const_rtx cond2) +{ + return conditions_mutex_with_rev_p (cond1, cond2, false, false); +} + +/* Return true iff COND1 and COND2 are equal. */ +bool +conditions_same_p (const_rtx cond1, const_rtx cond2) +{ + return conditions_mutex_with_rev_p (cond1, cond2, false, true); +} + +/* Return true iff COND1 and COND2 are either equal or opposite. */ +bool +conditions_same_or_mutex_p (const_rtx cond1, const_rtx cond2) +{ + return conditions_mutex_p (cond1, cond2) || conditions_same_p (cond1, cond2); +} + /* Return true if insn1 and insn2 can never depend on one another because the conditions under which they are executed are mutually exclusive. */ bool @@ -600,7 +620,7 @@ sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2) cond1 = sched_get_condition_with_rev (insn1, &rev1); cond2 = sched_get_condition_with_rev (insn2, &rev2); if (cond1 && cond2 - && conditions_mutex_p (cond1, cond2, rev1, rev2) + && conditions_mutex_with_rev_p (cond1, cond2, rev1, rev2) /* Make sure first instruction doesn't affect condition of second instruction if switched. */ && !modified_in_p (cond1, insn2) @@ -2673,6 +2693,10 @@ sched_analyze_insn (struct deps_desc *deps, rtx x, rtx insn) false dependencies. */ x = COND_EXEC_CODE (x); code = GET_CODE (x); + + if (flag_sel_sched_predication) + can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn) + && code == SET); } if (code == SET || code == CLOBBER) { diff --git a/gcc/sched-int.h b/gcc/sched-int.h index b8240d7..a81a7a1 100644 --- a/gcc/sched-int.h +++ b/gcc/sched-int.h @@ -1172,6 +1172,9 @@ extern struct sched_deps_info_def *sched_deps_info; /* Functions in sched-deps.c. */ +extern bool conditions_mutex_p (const_rtx, const_rtx); +extern bool conditions_same_p (const_rtx, const_rtx); +extern bool conditions_same_or_mutex_p (const_rtx, const_rtx); extern bool sched_insns_conditions_mutex_p (const_rtx, const_rtx); extern bool sched_insn_is_legitimate_for_speculation_p (const_rtx, ds_t); extern void add_dependence (rtx, rtx, enum reg_note); diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c index 1a73308..85e469a 100644 --- a/gcc/sel-sched-ir.c +++ b/gcc/sel-sched-ir.c @@ -1584,6 +1584,8 @@ bool vinsn_equal_p (vinsn_t x, vinsn_t y) { rtx_equal_p_callback_function repcf; + rtx condx = VINSN_COND (x); + rtx condy = VINSN_COND (y); if (x == y) return true; @@ -1594,6 +1596,11 @@ vinsn_equal_p (vinsn_t x, vinsn_t y) if (VINSN_HASH (x) != VINSN_HASH (y)) return false; + /* If only one vinsn is predicated, they are not equal. If both are + predicated, the conditions need to be equivalent. */ + if (condx != condy && !(condx && condy && conditions_same_p (condx, condy))) + return false; + repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL; if (VINSN_SEPARABLE_P (x)) { @@ -1607,6 +1614,39 @@ vinsn_equal_p (vinsn_t x, vinsn_t y) return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf); } +/* Compare two vinsns as rhses if possible and as vinsns otherwise. + Ignore potential differences in conditions. */ +bool +vinsn_equal_skip_cond_p (vinsn_t x, vinsn_t y) +{ + rtx_equal_p_callback_function repcf; + rtx patx = VINSN_PATTERN (x); + rtx paty = VINSN_PATTERN (y); + + if (x == y) + return true; + + if (VINSN_TYPE (x) != VINSN_TYPE (y)) + return false; + + repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL; + if (VINSN_SEPARABLE_P (x)) + { + /* Compare RHSes of VINSNs. */ + gcc_assert (VINSN_RHS (x)); + gcc_assert (VINSN_RHS (y)); + + return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf); + } + + if (GET_CODE (patx) == COND_EXEC) + patx = COND_EXEC_CODE (patx); + + if (GET_CODE (paty) == COND_EXEC) + paty = COND_EXEC_CODE (paty); + + return rtx_equal_p_cb (patx, paty, repcf); +} /* Functions for working with expressions. */ @@ -1616,8 +1656,8 @@ init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority, int sched_times, int orig_bb_index, ds_t spec_done_ds, ds_t spec_to_check_ds, int orig_sched_cycle, VEC(expr_history_def, heap) *history, signed char target_available, - bool was_substituted, bool was_renamed, bool needs_spec_check_p, - bool cant_move) + bool was_substituted, bool was_renamed, bool was_predicated, + bool needs_spec_check_p, bool cant_move) { vinsn_attach (vi); @@ -1638,6 +1678,7 @@ init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority, EXPR_TARGET_AVAILABLE (expr) = target_available; EXPR_WAS_SUBSTITUTED (expr) = was_substituted; EXPR_WAS_RENAMED (expr) = was_renamed; + EXPR_WAS_PREDICATED (expr) = was_predicated; EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p; EXPR_CANT_MOVE (expr) = cant_move; } @@ -1672,8 +1713,8 @@ copy_expr (expr_t to, expr_t from) EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), EXPR_ORIG_SCHED_CYCLE (from), NULL, EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from), - EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from), - EXPR_CANT_MOVE (from)); + EXPR_WAS_RENAMED (from), EXPR_WAS_PREDICATED (from), + EXPR_NEEDS_SPEC_CHECK_P (from), EXPR_CANT_MOVE (from)); copy_history_of_changes (to, from); } @@ -1686,8 +1727,8 @@ copy_expr_onside (expr_t to, expr_t from) EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0, EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0, NULL, EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from), - EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from), - EXPR_CANT_MOVE (from)); + EXPR_WAS_RENAMED (from), EXPR_WAS_PREDICATED (from), + EXPR_NEEDS_SPEC_CHECK_P (from), EXPR_CANT_MOVE (from)); } /* Prepare the expr of INSN for scheduling. Used when moving insn and when @@ -1841,6 +1882,11 @@ merge_expr_data (expr_t to, expr_t from, insn_t split_point) merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to), EXPR_HISTORY_OF_CHANGES (from)); + + if (EXPR_COND (to) || EXPR_COND (from)) + gcc_assert (EXPR_COND (to) && EXPR_COND (from) + && conditions_same_p (EXPR_COND (to), EXPR_COND (from))); + update_target_availability (to, from, split_point); update_speculative_bits (to, from, split_point); } @@ -2071,7 +2117,7 @@ av_set_add (av_set_t *setp, expr_t expr) } /* Same, but do not copy EXPR. */ -static void +void av_set_add_nocopy (av_set_t *setp, expr_t expr) { av_set_t elem; @@ -2189,7 +2235,7 @@ av_set_copy (av_set_t set) /* Join two av sets that do not have common elements by attaching second set (pointed to by FROMP) to the end of first set (TO_TAILP must point to _AV_SET_NEXT of first set's last element). */ -static void +void join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp) { gcc_assert (*to_tailp == NULL); @@ -2197,6 +2243,26 @@ join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp) *fromp = NULL; } +/* Return the pointer to _AV_SET_NEXT of the last element of AV. */ +static av_set_t * +av_set_tail (av_set_t *av) +{ + av_set_iterator avi; + expr_t expr; + + FOR_EACH_EXPR (expr, avi, *av) + {} + return avi.lp; +} + +/* Concatenate two av sets that do not have common elements by attaching second set + (pointed to by FROMP) to the end of first set (pointed to by TOP). */ +void +av_set_concat (av_set_t *top, av_set_t *fromp) +{ + join_distinct_sets (av_set_tail (top), fromp); +} + /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set pointed to by FROMP afterwards. */ void @@ -2221,22 +2287,41 @@ av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn) } /* Same as above, but also update availability of target register in - TOP judging by TO_LV_SET and FROM_LV_SET. */ + TOP judging by TO_LV_SET and FROM_LV_SET. INSN is the conditional branch, + and TO_FALLTHRU_P indicates whether TOP is from the fallthrough arm. */ void av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set, - regset from_lv_set, insn_t insn) + regset from_lv_set, insn_t insn, bool to_fallthru_p) { expr_t expr1; av_set_iterator i; - av_set_t *to_tailp, in_both_set = NULL; + av_set_t *to_tailp, in_both_set = NULL, pred_forms_set = NULL; + rtx cond = INSN_COND (insn), to_cond, from_cond; + + /* It may happen that cond is not NULL for a speculation check when that + check itself was predicated earlier. Unlike for normal jumps, we cannot + use its condition for predication. */ + if (sel_insn_is_speculation_check (insn)) + cond = NULL; + + if (cond) + { + rtx inv_cond = reversed_comparison (cond, GET_MODE (cond)); + to_cond = to_fallthru_p ? cond : inv_cond; + from_cond = to_fallthru_p ? inv_cond : cond; + } + else + to_cond = from_cond = NULL; /* Delete from TOP all expres, that present in FROMP. */ FOR_EACH_EXPR_1 (expr1, i, top) { expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1)); + maybe_predicate_expr_into (&pred_forms_set, expr1, insn, to_cond); if (expr2) { + maybe_predicate_expr_into (&pred_forms_set, expr2, insn, from_cond); /* It may be that the expressions have different destination registers, in which case we need to check liveness here. */ if (EXPR_SEPARABLE_P (expr1)) @@ -2266,12 +2351,17 @@ av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set, } to_tailp = i.lp; + av_set_concat (&pred_forms_set, &in_both_set); + /* These expressions are not present in TOP. Check liveness restrictions on TO_LV_SET. */ FOR_EACH_EXPR (expr1, i, *fromp) - set_unavailable_target_for_expr (expr1, to_lv_set); + { + maybe_predicate_expr_into (&pred_forms_set, expr1, insn, from_cond); + set_unavailable_target_for_expr (expr1, to_lv_set); + } - join_distinct_sets (i.lp, &in_both_set); + join_distinct_sets (i.lp, &pred_forms_set); join_distinct_sets (to_tailp, fromp); } @@ -2577,6 +2667,8 @@ static void setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p) { rtx pat = PATTERN (insn); + if (flag_sel_sched_predication && GET_CODE (pat) == COND_EXEC) + pat = COND_EXEC_CODE (pat); if (NONJUMP_INSN_P (insn) && GET_CODE (pat) == SET @@ -2695,6 +2787,29 @@ setup_id_reg_sets (idata_t id, insn_t insn) return_regset_to_pool (tmp); } +/* Setup predicate data for INSN in ID. */ +static void +setup_id_cond (idata_t id, insn_t insn) +{ + if (flag_sel_sched_predication) + { + rtx pat = PATTERN (insn); + if (GET_CODE (pat) == COND_EXEC) + IDATA_COND (id) = COND_EXEC_TEST (pat); + else if (GET_CODE (pat) == SET && SET_DEST (pat) == pc_rtx + && GET_CODE (SET_SRC (pat)) == IF_THEN_ELSE) + { + rtx cond = XEXP (SET_SRC (pat), 0); + if (GET_CODE (XEXP (cond, 0)) != UNSPEC) + { + if (XEXP (SET_SRC (pat), 2) == pc_rtx) + cond = reversed_comparison (cond, GET_MODE (cond)); + IDATA_COND (id) = cond; + } + } + } +} + /* Initialize instruction data for INSN in ID using DF's data. */ static void init_id_from_df (idata_t id, insn_t insn, bool force_unique_p) @@ -2703,6 +2818,7 @@ init_id_from_df (idata_t id, insn_t insn, bool force_unique_p) setup_id_for_insn (id, insn, force_unique_p); setup_id_lhs_rhs (id, insn, force_unique_p); + setup_id_cond (id, insn); if (INSN_NOP_P (insn)) return; @@ -2735,6 +2851,8 @@ deps_init_id (idata_t id, insn_t insn, bool force_unique_p) deps_analyze_insn (dc, insn); + setup_id_cond (id, insn); + free_deps (dc); deps_init_id_data.id = NULL; @@ -2996,7 +3114,7 @@ init_global_and_expr_for_insn (insn_t insn) /* Initialize INSN's expr. */ init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0, REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn), - spec_done_ds, 0, 0, NULL, true, false, false, false, + spec_done_ds, 0, 0, NULL, true, false, false, false, false, CANT_MOVE (insn)); } @@ -3567,6 +3685,10 @@ get_dest_and_mode (rtx insn, rtx *dst_loc, enum machine_mode *mode) rtx pat = PATTERN (insn); gcc_assert (dst_loc); + + if (GET_CODE (pat) == COND_EXEC) + pat = COND_EXEC_CODE (pat); + gcc_assert (GET_CODE (pat) == SET); *dst_loc = SET_DEST (pat); @@ -4224,7 +4349,7 @@ init_simplejump_data (insn_t insn) { init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0, REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0, NULL, true, false, false, - false, true); + false, false, true); INSN_SEQNO (insn) = get_seqno_for_a_jump (insn); init_first_time_insn_data (insn); } diff --git a/gcc/sel-sched-ir.h b/gcc/sel-sched-ir.h index bcb47c6..dc5ee76 100644 --- a/gcc/sel-sched-ir.h +++ b/gcc/sel-sched-ir.h @@ -73,7 +73,8 @@ typedef _xlist_t ilist_t; enum local_trans_type { TRANS_SUBSTITUTION, - TRANS_SPECULATION + TRANS_SPECULATION, + TRANS_PREDICATION }; /* This struct is used to record the history of expression's @@ -166,6 +167,9 @@ struct _expr /* True when the expression was renamed. */ BOOL_BITFIELD was_renamed : 1; + /* True when the expression was predicated. */ + BOOL_BITFIELD was_predicated : 1; + /* True when expression can't be moved. */ BOOL_BITFIELD cant_move : 1; }; @@ -178,6 +182,7 @@ typedef expr_def *expr_t; #define EXPR_PATTERN(EXPR) (VINSN_PATTERN (EXPR_VINSN (EXPR))) #define EXPR_LHS(EXPR) (VINSN_LHS (EXPR_VINSN (EXPR))) #define EXPR_RHS(EXPR) (VINSN_RHS (EXPR_VINSN (EXPR))) +#define EXPR_COND(EXPR) (VINSN_COND (EXPR_VINSN (EXPR))) #define EXPR_TYPE(EXPR) (VINSN_TYPE (EXPR_VINSN (EXPR))) #define EXPR_SEPARABLE_P(EXPR) (VINSN_SEPARABLE_P (EXPR_VINSN (EXPR))) @@ -195,6 +200,7 @@ typedef expr_def *expr_t; #define EXPR_NEEDS_SPEC_CHECK_P(EXPR) ((EXPR)->needs_spec_check_p) #define EXPR_WAS_SUBSTITUTED(EXPR) ((EXPR)->was_substituted) #define EXPR_WAS_RENAMED(EXPR) ((EXPR)->was_renamed) +#define EXPR_WAS_PREDICATED(EXPR) ((EXPR)->was_predicated) #define EXPR_CANT_MOVE(EXPR) ((EXPR)->cant_move) #define EXPR_WAS_CHANGED(EXPR) (VEC_length (expr_history_def, \ @@ -593,6 +599,9 @@ struct idata_def /* If insn is a SET, this is its right hand side. */ rtx rhs; + /* If insn is conditionally executed, this is its controlling predicate. */ + rtx cond; + /* Registers that are set/used by this insn. This info is now gathered via sched-deps.c. The downside of this is that we also use live info from flow that is accumulated in the basic blocks. These two infos @@ -612,6 +621,7 @@ struct idata_def #define IDATA_TYPE(ID) ((ID)->type) #define IDATA_LHS(ID) ((ID)->lhs) #define IDATA_RHS(ID) ((ID)->rhs) +#define IDATA_COND(ID) ((ID)->cond) #define IDATA_REG_SETS(ID) ((ID)->reg_sets) #define IDATA_REG_USES(ID) ((ID)->reg_uses) #define IDATA_REG_CLOBBERS(ID) ((ID)->reg_clobbers) @@ -666,6 +676,7 @@ struct vinsn_def #define VINSN_UNIQUE_P(VI) (!VINSN_CLONABLE_P (VI)) #define VINSN_LHS(VI) (IDATA_LHS (VINSN_ID (VI))) #define VINSN_RHS(VI) (IDATA_RHS (VINSN_ID (VI))) +#define VINSN_COND(VI) (IDATA_COND (VINSN_ID (VI))) #define VINSN_REG_SETS(VI) (IDATA_REG_SETS (VINSN_ID (VI))) #define VINSN_REG_USES(VI) (IDATA_REG_USES (VINSN_ID (VI))) #define VINSN_REG_CLOBBERS(VI) (IDATA_REG_CLOBBERS (VINSN_ID (VI))) @@ -789,6 +800,7 @@ extern sel_insn_data_def insn_sid (insn_t); #define INSN_SIMPLEJUMP_P(INSN) (INSN_TYPE (INSN) == PC) #define INSN_LHS(INSN) (VINSN_LHS (INSN_VINSN (INSN))) #define INSN_RHS(INSN) (VINSN_RHS (INSN_VINSN (INSN))) +#define INSN_COND(INSN) (VINSN_COND (INSN_VINSN (INSN))) #define INSN_REG_SETS(INSN) (VINSN_REG_SETS (INSN_VINSN (INSN))) #define INSN_REG_CLOBBERS(INSN) (VINSN_REG_CLOBBERS (INSN_VINSN (INSN))) #define INSN_REG_USES(INSN) (VINSN_REG_USES (INSN_VINSN (INSN))) @@ -1537,6 +1549,7 @@ extern void vinsn_attach (vinsn_t); extern void vinsn_detach (vinsn_t); extern vinsn_t vinsn_copy (vinsn_t, bool); extern bool vinsn_equal_p (vinsn_t, vinsn_t); +extern bool vinsn_equal_skip_cond_p (vinsn_t x, vinsn_t y); /* EXPR functions. */ extern void copy_expr (expr_t, expr_t); @@ -1555,22 +1568,27 @@ extern void insert_in_history_vect (VEC(expr_history_def, heap) **, vinsn_t, vinsn_t, ds_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 maybe_predicate_expr_into (av_set_t *, expr_t, insn_t, rtx); /* Av set functions. */ extern void av_set_add (av_set_t *, expr_t); +extern void av_set_add_nocopy (av_set_t *, expr_t); extern void av_set_iter_remove (av_set_iterator *); extern expr_t av_set_lookup (av_set_t, vinsn_t); extern expr_t merge_with_other_exprs (av_set_t *, av_set_iterator *, expr_t); extern bool av_set_is_in_p (av_set_t, vinsn_t); extern av_set_t av_set_copy (av_set_t); extern void av_set_union_and_clear (av_set_t *, av_set_t *, insn_t); -extern void av_set_union_and_live (av_set_t *, av_set_t *, regset, regset, insn_t); +extern void av_set_union_and_live (av_set_t *, av_set_t *, regset, regset, insn_t, bool); extern void av_set_clear (av_set_t *); extern void av_set_leave_one_nonspec (av_set_t *); extern expr_t av_set_element (av_set_t, int); extern void av_set_substract_cond_branches (av_set_t *); extern void av_set_split_usefulness (av_set_t, int, int); extern void av_set_code_motion_filter (av_set_t *, av_set_t); +extern void av_set_intersect (av_set_t *, av_set_t); +extern void join_distinct_sets (av_set_t *, av_set_t *); +extern void av_set_concat (av_set_t *, av_set_t *); extern void sel_save_haifa_priorities (void); diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c index 91fb0fe..f5c6f8b 100644 --- a/gcc/sel-sched.c +++ b/gcc/sel-sched.c @@ -607,24 +607,23 @@ advance_one_cycle (fence_t fence) } } -/* Returns true when SUCC in a fallthru bb of INSN, possibly - skipping empty basic blocks. */ +/* Returns true when SUCC in a fallthru bb of INSN, possibly skipping empty + basic blocks. Blocks with a nop are also skipped if SKIP_NOPS_P is set. */ static bool -in_fallthru_bb_p (rtx insn, rtx succ) +in_fallthru_bb_p (rtx insn, rtx succ, bool skip_nops_p) { basic_block bb = BLOCK_FOR_INSN (insn); edge e; - if (bb == BLOCK_FOR_INSN (succ)) - return true; - e = find_fallthru_edge_from (bb); if (e) bb = e->dest; else return false; - while (sel_bb_empty_p (bb)) + while (skip_nops_p + ? sel_bb_empty_or_nop_p (bb) + : sel_bb_empty_p (bb)) bb = bb->next_bb; return bb == BLOCK_FOR_INSN (succ); @@ -690,7 +689,7 @@ extract_new_fences_from (flist_t old_fences, flist_tail_t new_fences, && (pipelining_p || INSN_SCHED_TIMES (succ) <= 0)) { bool b = (in_same_ebb_p (insn, succ) - || in_fallthru_bb_p (insn, succ)); + || in_fallthru_bb_p (insn, succ, false)); if (sched_verbose >= 1) sel_print ("Fence %d continues as %d[%d] (state %s)\n", @@ -722,7 +721,8 @@ can_substitute_through_p (insn_t insn, ds_t ds) if ((ds & DEP_OUTPUT) || (ds & DEP_ANTI) || ! INSN_RHS (insn) - || ! INSN_LHS (insn)) + || ! INSN_LHS (insn) + || INSN_COND (insn)) return false; /* Now we just need to make sure the INSN_RHS consists of only one @@ -773,7 +773,7 @@ substitute_reg_in_expr (expr_t expr, insn_t insn, bool undo) WHERE_REPLACE should point inside NEW_INSN, so INSN_RHS couldn't be used instead of SET_SRC. */ where_replace = (has_rhs - ? &SET_SRC (PATTERN (new_insn)) + ? COND_SET_SRC_PTR (PATTERN (new_insn)) : &PATTERN (new_insn)); new_insn_valid @@ -882,15 +882,13 @@ rtx_ok_for_substitution_p (rtx what, rtx where) static rtx create_insn_rtx_with_rhs (vinsn_t vi, rtx rhs_rtx) { - rtx lhs_rtx; - rtx pattern; rtx insn_rtx; + bool res; - lhs_rtx = copy_rtx (VINSN_LHS (vi)); - - pattern = gen_rtx_SET (VOIDmode, lhs_rtx, rhs_rtx); - insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX); + insn_rtx = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi)); + res = validate_change (insn_rtx, COND_SET_SRC_PTR (PATTERN (insn_rtx)), rhs_rtx, 0); + gcc_assert (res); return insn_rtx; } @@ -932,7 +930,7 @@ replace_src_with_reg_ok_p (insn_t insn, rtx new_src_reg) return true; /* See whether SET_SRC can be replaced with this register. */ - validate_change (insn, &SET_SRC (PATTERN (insn)), new_src_reg, 1); + validate_change (insn, COND_SET_SRC_PTR (PATTERN (insn)), new_src_reg, 1); res = verify_changes (0); cancel_changes (0); @@ -952,38 +950,26 @@ replace_dest_with_reg_ok_p (insn_t insn, rtx new_reg) gcc_assert (GET_MODE (VINSN_LHS (vi)) == GET_MODE (new_reg)); /* See whether SET_DEST can be replaced with this register. */ - validate_change (insn, &SET_DEST (PATTERN (insn)), new_reg, 1); + validate_change (insn, COND_SET_DEST_PTR (PATTERN (insn)), new_reg, 1); res = verify_changes (0); cancel_changes (0); return res; } -/* Create a pattern with rhs of VI and lhs of LHS_RTX. */ -static rtx -create_insn_rtx_with_lhs (vinsn_t vi, rtx lhs_rtx) -{ - rtx rhs_rtx; - rtx pattern; - rtx insn_rtx; - - rhs_rtx = copy_rtx (VINSN_RHS (vi)); - - pattern = gen_rtx_SET (VOIDmode, lhs_rtx, rhs_rtx); - insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX); - - return insn_rtx; -} - -/* Substitute lhs in the given expression EXPR for the register with number - NEW_REGNO. SET_DEST may be arbitrary rtx, not only register. */ +/* Substitute lhs in the given expression EXPR with register NEW_REG. */ static void replace_dest_with_reg_in_expr (expr_t expr, rtx new_reg) { rtx insn_rtx; vinsn_t vinsn; + bool res; + + insn_rtx = create_copy_of_insn_rtx (EXPR_INSN_RTX (expr)); + + res = validate_change (insn_rtx, COND_SET_DEST_PTR (PATTERN (insn_rtx)), new_reg, 0); + gcc_assert (res); - insn_rtx = create_insn_rtx_with_lhs (EXPR_VINSN (expr), new_reg); vinsn = create_vinsn_from_insn_rtx (insn_rtx, false); change_vinsn_in_expr (expr, vinsn); @@ -1219,10 +1205,9 @@ mark_unavailable_hard_regs (def_t def, struct reg_rename *reg_rename_p, unsigned cur_reg, regno; hard_reg_set_iterator hrsi; - gcc_assert (GET_CODE (PATTERN (def->orig_insn)) == SET); gcc_assert (reg_rename_p); - orig_dest = SET_DEST (PATTERN (def->orig_insn)); + orig_dest = INSN_LHS (def->orig_insn); /* We have decided not to rename 'mem = something;' insns, as 'something' is usually a register. */ @@ -1394,7 +1379,7 @@ choose_best_reg_1 (HARD_REG_SET hard_regs_used, FOR_EACH_DEF (def, di, original_insns) { - rtx orig_dest = SET_DEST (PATTERN (def->orig_insn)); + rtx orig_dest = INSN_LHS (def->orig_insn); gcc_assert (REG_P (orig_dest)); @@ -1505,7 +1490,7 @@ choose_best_pseudo_reg (regset used_regs, FOR_EACH_DEF (def, i, original_insns) { - rtx dest = SET_DEST (PATTERN (def->orig_insn)); + rtx dest = *COND_SET_DEST_PTR (PATTERN (def->orig_insn)); int orig_regno; gcc_assert (REG_P (dest)); @@ -1577,6 +1562,10 @@ verify_target_availability (expr_t expr, regset used_regs, if (!REG_P (EXPR_LHS (expr)) || EXPR_TARGET_AVAILABLE (expr) < 0) return; + /* Making an expression predicated when moving it up across a branch + does not affect liveness on the predicated-off path. */ + if (EXPR_COND (expr)) + return; regno = expr_dest_regno (expr); mode = GET_MODE (EXPR_LHS (expr)); @@ -2000,6 +1989,11 @@ undo_transformations (av_set_t *av_ptr, rtx insn) clear_expr (tmp_expr); break; } + case TRANS_PREDICATION: + { + change_vinsn_in_expr (expr, phist->old_expr_vinsn); + break; + } default: gcc_unreachable (); } @@ -2205,6 +2199,16 @@ moveup_expr (expr_t expr, insn_t through_insn, bool inside_insn_group, && moving_insn_creates_bookkeeping_block_p (insn, through_insn)) return MOVEUP_EXPR_NULL; + if (flag_sel_sched_predication && any_condjump_p (through_insn) + && EXPR_COND (expr) && INSN_COND (through_insn) + && !modified_in_p (INSN_COND (through_insn), EXPR_INSN_RTX (expr))) + { + if (conditions_same_or_mutex_p (INSN_COND (through_insn), EXPR_COND (expr))) + return MOVEUP_EXPR_SAME; + else + return MOVEUP_EXPR_NULL; + } + /* Deal with data dependencies. */ was_target_conflict = false; full_ds = has_dependence_p (expr, through_insn, &has_dep_p); @@ -2712,6 +2716,181 @@ is_ineligible_successor (insn_t insn, ilist_t p) return false; } +/* An entry in the predication cache. */ +struct predication_cache +{ + /* A predicate that would be added. */ + rtx cond; + /* Original vinsn. */ + vinsn_t vinsn_old; + /* The vinsn resulting from applying predicate COND to vinsn VINSN_OLD. */ + vinsn_t vinsn_new; +}; + +static htab_t predication_cache; + +/* Hash function for predication cache entries. */ +static hashval_t +predication_cache_hash (const void *p) +{ + const struct predication_cache *data = (const struct predication_cache *)p; + return iterative_hash_rtx (data->cond, VINSN_HASH_RTX (data->vinsn_old)); +} + +/* Free function for predication cache entries. */ +static void +predication_cache_free (void *p) +{ + struct predication_cache *data = (struct predication_cache *)p; + vinsn_detach (data->vinsn_old); + if (data->vinsn_new) + vinsn_detach (data->vinsn_new); + free (p); +} + +/* Comparison function for predication cache entries. */ +static int +predication_cache_eq (const void *p, const void *q) +{ + const struct predication_cache *data1 = (const struct predication_cache *)p; + const struct predication_cache *data2 = (const struct predication_cache *)q; + rtx i1, i2; + if (!conditions_same_p (data1->cond, data2->cond)) + return false; + i1 = VINSN_INSN_RTX (data1->vinsn_old); + i2 = VINSN_INSN_RTX (data2->vinsn_old); + return (INSN_UID (i1) == INSN_UID (i2) + || rtx_equal_p (PATTERN (i1), PATTERN (i2))); +} + +/* Find an entry for applying predicate COND to vinsn VI in the predication + cache. */ +static struct predication_cache* +find_in_predication_cache (rtx cond, vinsn_t vi) +{ + struct predication_cache key; + key.cond = cond; + key.vinsn_old = vi; + return (struct predication_cache *) htab_find (predication_cache, &key); +} + +/* Try to construct NEW_EXPR as the result of applying predicate COND to + EXPR, using uid of INSN to record the transformation in the history vector. + Return value indicates whether transformation is valid. */ +static bool +predicate_expr (expr_t new_expr, expr_t expr, insn_t insn, rtx cond) +{ + struct predication_cache *entry; + vinsn_t vi = EXPR_VINSN (expr), new_vi; + rtx pat = PATTERN (EXPR_INSN_RTX (expr)); + + if (VINSN_UNIQUE_P (vi) + || modified_in_p (cond, EXPR_INSN_RTX (expr))) + return false; + + entry = find_in_predication_cache (cond, vi); + + if (entry) + { + new_vi = entry->vinsn_new; + if (!new_vi) + return false; + if (INSN_IN_STREAM_P (VINSN_INSN_RTX (new_vi))) + new_vi = vinsn_copy (new_vi, false); + } + else + { + entry = XNEW (struct predication_cache); + entry->cond = cond; + entry->vinsn_old = vi; + vinsn_attach (vi); + + pat = gen_rtx_COND_EXEC (VOIDmode, copy_rtx (cond), copy_rtx (pat)); + if (insn_invalid_p (make_insn_raw (pat))) + { + entry->vinsn_new = NULL; + *(struct predication_cache **) htab_find_slot (predication_cache, + entry, + INSERT) = entry; + return false; + } + pat = create_insn_rtx_from_pattern (pat, NULL_RTX); + new_vi = entry->vinsn_new = create_vinsn_from_insn_rtx (pat, false); + vinsn_attach (new_vi); + *(struct predication_cache **) htab_find_slot (predication_cache, entry, + INSERT) = entry; + } + + if (sched_verbose >= 6) + { + sel_print (" new from pred: "); + dump_vinsn (new_vi); + sel_print ("\n"); + } + copy_expr (new_expr, expr); + change_vinsn_in_expr (new_expr, new_vi); + insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (new_expr), + INSN_UID (insn), TRANS_PREDICATION, + vi, new_vi, EXPR_SPEC_DONE_DS (expr), + EXPR_SPEC_DONE_DS (expr)); + return true; +} + +/* Invoke predicate_expr on EXPR, INSN, COND, and if the transformation is + valid, add the resulting expression into av set pointed by TOP. */ +void +maybe_predicate_expr_into (av_set_t *top, expr_t expr, insn_t insn, rtx cond) +{ + expr_def _tmp_expr, *tmp_expr = &_tmp_expr; + + if (!cond) + return; + if (predicate_expr (tmp_expr, expr, insn, cond)) + av_set_add_nocopy (top, tmp_expr); +} + +/* Add to av set pointed by TOP expressions from AV predicated by INSN's + condition (or its inversion, if SUCC is not in the fallthru block). */ +static void +populate_av_set_with_predicated (av_set_t *top, av_set_t av, insn_t insn, insn_t succ) +{ + av_set_iterator avi; + expr_t expr; + rtx cond = INSN_COND (insn); + + if (!cond || !any_condjump_p (insn) + || EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) != 2) + return; + + if (!in_fallthru_bb_p (insn, succ, true)) + cond = reversed_comparison (cond, GET_MODE (cond)); + + FOR_EACH_EXPR (expr, avi, av) + maybe_predicate_expr_into (top, expr, insn, cond); +} + +/* Remove from av set pointed by AV expressions predicated by INSN's + condition (or its inverse, if SUCC is not in the fallthru block). */ +static void +filter_av_set_by_predicate (av_set_t *av, insn_t insn, insn_t succ) +{ + av_set_iterator avi; + expr_t expr; + rtx cond = INSN_COND (insn); + + if (!cond || !any_condjump_p (insn) + || EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) != 2) + return; + + if (!in_fallthru_bb_p (insn, succ, true)) + cond = reversed_comparison (cond, GET_MODE (cond)); + + FOR_EACH_EXPR_1 (expr, avi, av) + if (EXPR_COND (expr) + && conditions_mutex_p (EXPR_COND (expr), cond)) + av_set_iter_remove (&avi); +} + /* Computes the av_set below the last bb insn INSN, doing all the 'dirty work' of handling multiple successors and properly merging its av_sets. P is the current path traversed. WS is the size of lookahead window. @@ -2723,7 +2902,7 @@ compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws) av_set_t expr_in_all_succ_branches = NULL; int is; insn_t succ, zero_succ = NULL; - av_set_t av1 = NULL; + av_set_t av1 = NULL, pred_forms_set = NULL; gcc_assert (sel_bb_end_p (insn)); @@ -2751,6 +2930,12 @@ compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws) /* We will edit SUCC_SET and EXPR_SPEC field of its elements. */ succ_set = compute_av_set_inside_bb (succ, p, ws, true); + /* Remove insns that are predicated-off for the current successor. */ + filter_av_set_by_predicate (&succ_set, insn, succ); + + if (sinfo->succs_ok_n == 1) + populate_av_set_with_predicated (&pred_forms_set, succ_set, insn, succ); + av_set_split_usefulness (succ_set, VEC_index (int, sinfo->probs_ok, is), sinfo->all_prob); @@ -2784,12 +2969,13 @@ compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws) { basic_block bb0 = BLOCK_FOR_INSN (zero_succ); basic_block bb1 = BLOCK_FOR_INSN (succ); + bool to_fallthru_p = in_fallthru_bb_p (insn, zero_succ, true); gcc_assert (BB_LV_SET_VALID_P (bb0) && BB_LV_SET_VALID_P (bb1)); av_set_union_and_live (&av1, &succ_set, BB_LV_SET (bb0), BB_LV_SET (bb1), - insn); + insn, to_fallthru_p); } else av_set_union_and_clear (&av1, &succ_set, insn); @@ -2813,6 +2999,8 @@ compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws) mark_unavailable_targets (av1, NULL, BB_LV_SET (BLOCK_FOR_INSN (succ))); + av_set_concat (&av1, &pred_forms_set); + if (sinfo->all_succs_n > 1) { av_set_iterator i; @@ -3391,6 +3579,12 @@ sel_rank_for_schedule (const void *x, const void *y) if (val) return val; + /* Prefer an expr that would not need renaming. */ + if (EXPR_TARGET_AVAILABLE (tmp) >= 0 && EXPR_TARGET_AVAILABLE (tmp2) >= 0) + val = EXPR_TARGET_AVAILABLE (tmp2) - EXPR_TARGET_AVAILABLE (tmp); + if (val) + return val; + if (spec_info != NULL && spec_info->mask != 0) /* This code was taken from haifa-sched.c: rank_for_schedule (). */ { @@ -3415,6 +3609,11 @@ sel_rank_for_schedule (const void *x, const void *y) return dw; } + /* Prefer a conditionally executed expr. */ + val = !EXPR_COND (tmp) - !EXPR_COND(tmp2); + if (val) + return val; + /* Prefer an old insn to a bookkeeping insn. */ if (INSN_UID (tmp_insn) < first_emitted_uid && INSN_UID (tmp2_insn) >= first_emitted_uid) @@ -3581,7 +3780,12 @@ vinsn_vec_has_expr_p (vinsn_vec_t vinsn_vec, expr_t expr) int n; FOR_EACH_VEC_ELT (vinsn_t, vinsn_vec, n, vinsn) - if (VINSN_SEPARABLE_P (vinsn)) + if (EXPR_COND (expr) || VINSN_COND (vinsn)) + { + if (vinsn_equal_skip_cond_p (vinsn, EXPR_VINSN (expr))) + return true; + } + else if (VINSN_SEPARABLE_P (vinsn)) { if (vinsn_equal_p (vinsn, EXPR_VINSN (expr))) return true; @@ -6179,6 +6383,7 @@ redo_transformations (expr_t expr, insn_t insn) EXPR_SPEC_DONE_DS (expr) = hist->new_spec_ds; /* Fallthru. */ case TRANS_SUBSTITUTION: + case TRANS_PREDICATION: change_vinsn_in_expr (expr, hist->new_expr_vinsn); break; default: @@ -6275,16 +6480,27 @@ static bool move_op_orig_expr_not_found (insn_t insn, av_set_t orig_ops ATTRIBUTE_UNUSED, void *static_params) { + bool mutexed; + expr_t r; + av_set_iterator avi; moveop_static_params_p sparams = (moveop_static_params_p) static_params; #ifdef ENABLE_CHECKING sparams->failed_insn = insn; #endif + mutexed = true; + FOR_EACH_EXPR (r, avi, orig_ops) + if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (r))) + { + mutexed = false; + break; + } + /* If we're scheduling separate expr, in order to generate correct code we need to stop the search at bookkeeping code generated with the same destination register or memory. */ - if (lhs_of_insn_equals_to_dest_p (insn, sparams->dest)) + if (!mutexed && lhs_of_insn_equals_to_dest_p (insn, sparams->dest)) return false; return true; } @@ -6370,13 +6586,14 @@ struct code_motion_path_driver_info_def fur_hooks = { was found at least on one path that is starting with one of INSN's successors (this fact is asserted). ORIG_OPS is expressions we're looking for, PATH is the path we've traversed, STATIC_PARAMS is the parameters - of either move_op or find_used_regs depending on the caller. + of either move_op or find_used_regs depending on the caller. COND, if not + null, is the common predicate of expressions in ORIG_OPS. Return 0 if we haven't found expression, 1 if we found it, -1 if we don't know for sure at this point. */ static int code_motion_process_successors (insn_t insn, av_set_t orig_ops, - ilist_t path, void *static_params) + ilist_t path, void *static_params, rtx cond) { int res = 0; succ_iterator succ_i; @@ -6409,6 +6626,17 @@ code_motion_process_successors (insn_t insn, av_set_t orig_ops, { int b; + if (cond + && conditions_same_or_mutex_p (cond, INSN_COND (insn)) + && !(single_succ_p (succ_i.e1->src)) + && (((succ_i.e1->flags & EDGE_FALLTHRU) != 0) + == conditions_mutex_p (cond, INSN_COND (insn)))) + { + if (sched_verbose >= 6) + sel_print ("Not following predicated-off path from %d\n", + INSN_UID (succ)); + continue; + } lparams.e1 = succ_i.e1; lparams.e2 = succ_i.e2; @@ -6472,6 +6700,27 @@ code_motion_path_driver_cleanup (av_set_t *orig_ops_p, ilist_t *path_p) av_set_clear (orig_ops_p); } +/* Verify that all elements of AV have the same predicate. Return the + common predicate. */ +static rtx +av_set_common_cond (av_set_t av) +{ + av_set_iterator i; + expr_t expr; + bool first_p = true; + rtx cond = NULL; + + FOR_EACH_EXPR (expr, i, av) + if (first_p) + { + first_p = false; + cond = EXPR_COND (expr); + } + else + gcc_assert (cond == EXPR_COND (expr) || conditions_same_p (cond, EXPR_COND (expr))); + return cond; +} + /* The driver function that implements move_op or find_used_regs functionality dependent whether code_motion_path_driver_INFO is set to &MOVE_OP_HOOKS or &FUR_HOOKS. This function implements the common parts @@ -6492,6 +6741,7 @@ code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path, basic_block bb = BLOCK_FOR_INSN (insn); insn_t first_insn, bb_tail, before_first; bool removed_last_insn = false; + rtx orig_cond; if (sched_verbose >= 6) { @@ -6571,6 +6821,8 @@ code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path, /* It is not possible that all ORIG_OPS are filtered out. */ gcc_assert (orig_ops); + orig_cond = av_set_common_cond (orig_ops); + /* It is enough to place only heads and tails of visited basic blocks into the PATH. */ ilist_add (&path, insn); @@ -6659,6 +6911,12 @@ code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path, gcc_assert (insn == sel_bb_end (bb)); + if (orig_cond && av_set_common_cond (orig_ops)) + orig_cond = NULL; + if (orig_cond) + gcc_assert (INSN_COND (insn) + && conditions_same_or_mutex_p (orig_cond, INSN_COND (insn))); + /* Add bb tail to PATH (but it doesn't make any sense if it's a bb_head - it's already in PATH then). */ if (insn != first_insn) @@ -6672,7 +6930,7 @@ code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path, /* Process_successors should be able to find at least one successor for which code_motion_path_driver returns TRUE. */ res = code_motion_process_successors (insn, orig_ops, - path, static_params); + path, static_params, orig_cond); /* Jump in the end of basic block could have been removed or replaced during code_motion_process_successors, so recompute insn as the @@ -7004,6 +7262,9 @@ sel_region_init (int rgn) current_copies = BITMAP_ALLOC (NULL); current_originators = BITMAP_ALLOC (NULL); code_motion_visited_blocks = BITMAP_ALLOC (NULL); + predication_cache = htab_create (16, predication_cache_hash, + predication_cache_eq, + predication_cache_free); return false; } @@ -7299,6 +7560,7 @@ sel_region_target_finish (bool reset_sched_cycles_p) static void sel_region_finish (bool reset_sched_cycles_p) { + htab_delete (predication_cache); simplify_changed_insns (); sched_finish_ready_list (); free_nop_pool ();