Index: gcc/sel-sched.c =================================================================== --- gcc/sel-sched.c (revision 131205) +++ gcc/sel-sched.c (working copy) @@ -226,10 +226,11 @@ static int stat_substitutions_total; static bool rtx_search (rtx, rtx); static int sel_rank_for_schedule (const void *, const void *); static bool equal_after_moveup_path_p (rhs_t, ilist_t, rhs_t); +static rtx get_dest_from_orig_ops (av_set_t); static basic_block generate_bookkeeping_insn (rhs_t, insn_t, edge, edge); static bool find_used_regs (insn_t, av_set_t, regset, struct reg_rename *, def_list_t *); -static bool move_op (insn_t, av_set_t, ilist_t, edge, edge, expr_t); +static bool move_op (insn_t, av_set_t, ilist_t, edge, edge, rtx, expr_t); static void sel_sched_region_1 (void); static void sel_sched_region_2 (sel_sched_region_2_data_t); @@ -517,7 +518,7 @@ rtx_search (rtx what, rtx where) /* if INSN is a copy x:=y and if there is an rhs r in AV that uses y, it adds all variants of r to AV derived by replacing one or more occurrences of y by x. */ -static void +ATTRIBUTE_UNUSED static void un_substitute (rhs_t rhs, rtx insn, av_set_t *new_set_ptr) { rtx pat, src_reg, dst_reg; @@ -1468,7 +1469,7 @@ find_best_reg_for_rhs (rhs_t rhs, blist_ /* Flag to enable / disable ia64 speculation. */ static bool sel_speculation_p = true; -static bool speculate_expr (expr_t, ds_t); +static int speculate_expr (expr_t, ds_t); static ds_t get_spec_check_type_for_insn (insn_t, expr_t); /* Return true if dependence described by DS can be overcomed. */ @@ -1579,14 +1580,20 @@ create_speculation_check (expr_t c_rhs, return insn; } -/* Try to transform EXPR to data speculative version. Return true on - success. */ -static bool -apply_spec_to_expr (expr_t expr, ds_t ds) +/* Try to make EXPR speculative. Return true when EXPR's pattern + had to be changed. */ +static int +speculate_expr (expr_t expr, ds_t ds) { int res; rtx orig_insn_rtx; rtx spec_pat; + ds_t target_ds, current_ds; + + /* Obtain the status we need to put on EXPR. */ + target_ds = (ds & SPECULATIVE); + current_ds = EXPR_SPEC_DONE_DS (expr); + ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX); orig_insn_rtx = EXPR_INSN_RTX (expr); @@ -1595,10 +1602,9 @@ apply_spec_to_expr (expr_t expr, ds_t ds switch (res) { case 0: - spec_pat = copy_rtx (PATTERN (orig_insn_rtx)); - - /* FALLTHRU */ - + EXPR_SPEC_DONE_DS (expr) = ds; + return 0; + case 1: { rtx spec_insn_rtx = create_insn_rtx_from_pattern (spec_pat, NULL_RTX); @@ -1609,45 +1615,22 @@ apply_spec_to_expr (expr_t expr, ds_t ds /* Do not allow clobbering the address register of speculative insns. */ - if (res == 1 - && bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)), - expr_dest_regno (expr))) + if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)), + expr_dest_regno (expr))) EXPR_TARGET_AVAILABLE (expr) = false; - return true; + return 1; } case -1: - return false; + return -1; default: gcc_unreachable (); - return false; + return -1; } } -/* Try to make EXPR speculative and on success remove from DSP those - dependencies that were overcame. Return true on success. */ -static bool -speculate_expr (expr_t expr, ds_t ds) -{ - ds_t target_ds = (ds & SPECULATIVE); - ds_t current_ds = EXPR_SPEC_DONE_DS (expr); - ds_t combined_ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX); - - /* ??? Do not allow both kind of speculations when pipelining. */ - if (pipelining_p - && (combined_ds & DATA_SPEC) - && (combined_ds & CONTROL_SPEC)) - return false; - - if (apply_spec_to_expr (expr, combined_ds)) - /* We already have all necessary speculations. */ - return true; - - return false; -} - /* Return true if there is a speculative dependence between INSN and EXPR. */ static ds_t has_spec_dependence_p (expr_t expr, insn_t insn) @@ -1672,7 +1655,7 @@ has_spec_dependence_p (expr_t expr, insn /* Record speculations that EXPR should perform in order to be moved through INSN. */ -static void +ATTRIBUTE_UNUSED static void un_speculate (expr_t expr, insn_t insn) { ds_t expr_spec_done_ds; @@ -1724,7 +1707,6 @@ undo_transformations (av_set_t *av_ptr, { av_set_iterator av_iter; rhs_t rhs; - unsigned hash; av_set_t new_set = NULL; /* First, kill any RHS that uses registers set by an insn. This is @@ -1743,21 +1725,64 @@ undo_transformations (av_set_t *av_ptr, av_set_iter_remove (&av_iter); } - hash = VINSN_HASH (INSN_VINSN (insn)); /* FIXME: we need to determine whether RHS was changed on this insn just once. */ FOR_EACH_RHS (rhs, av_iter, *av_ptr) { - if (find_in_hash_vect (EXPR_CHANGED_ON_INSNS (rhs), hash) >= 0) - un_speculate (rhs, insn); + int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (rhs), + insn, EXPR_VINSN (rhs), true); + + if (index >= 0 && VEC_index (expr_history_def, + EXPR_HISTORY_OF_CHANGES (rhs), + index)->type == TRANS_SPECULATION) + { + ds_t old_ds, new_ds; + + old_ds = VEC_index (expr_history_def, + EXPR_HISTORY_OF_CHANGES (rhs), + index)->spec_ds; + new_ds = EXPR_SPEC_DONE_DS (rhs); + gcc_assert (spec_info && sel_speculation_p + && new_ds + && (old_ds & SPECULATIVE) != (new_ds & SPECULATIVE)); + + old_ds &= SPECULATIVE; + new_ds &= SPECULATIVE; + new_ds &= ~old_ds; + + EXPR_SPEC_TO_CHECK_DS (rhs) |= new_ds; + } } new_set = NULL; FOR_EACH_RHS (rhs, av_iter, *av_ptr) { - if (find_in_hash_vect (EXPR_CHANGED_ON_INSNS (rhs), hash) >= 0) - un_substitute (rhs, insn, &new_set); + int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (rhs), + insn, EXPR_VINSN (rhs), true); + + if (index >= 0 && VEC_index (expr_history_def, + EXPR_HISTORY_OF_CHANGES (rhs), + index)->type == TRANS_SUBSTITUTION) + { + expr_def _tmp_rhs, *tmp_rhs = &_tmp_rhs; + vinsn_t new_vi; + + + new_vi = VEC_index (expr_history_def, + EXPR_HISTORY_OF_CHANGES (rhs), + index)->old_expr_vinsn; + + gcc_assert (VINSN_SEPARABLE_P (new_vi) + == EXPR_SEPARABLE_P (rhs)); + + copy_expr (tmp_rhs, rhs); + change_vinsn_in_expr (tmp_rhs, new_vi); + + av_set_add (&new_set, tmp_rhs); + clear_expr (tmp_rhs); + } + } av_set_union_and_clear (av_ptr, &new_set); @@ -1823,13 +1848,15 @@ moveup_rhs_inside_insn_group (rhs_t insn && !sel_insn_is_speculation_check (through_insn)) /* Modifies INSN_TO_MOVE_UP so it can be moved through the THROUGH_INSN, - performing necessary transformations. When INSIDE_INSN_GROUP, + performing necessary transformations. Record the type of transformation + made in PTRANS_TYPE, when it is not NULL. When INSIDE_INSN_GROUP, permit all dependencies except true ones, and try to remove those too via forward substitution. All cases when a non-eliminable non-zero cost dependency exists inside an insn group will be fixed in tick_check_p instead. */ static enum MOVEUP_RHS_CODE -moveup_rhs (rhs_t insn_to_move_up, insn_t through_insn, bool inside_insn_group) +moveup_rhs (rhs_t insn_to_move_up, insn_t through_insn, bool inside_insn_group, + enum local_trans_type *ptrans_type) { vinsn_t vi = RHS_VINSN (insn_to_move_up); insn_t insn = VINSN_INSN (vi); @@ -1904,11 +1931,16 @@ moveup_rhs (rhs_t insn_to_move_up, insn_ if (full_ds != 0 && can_overcome_dep_p (full_ds)) { - if (speculate_expr (insn_to_move_up, full_ds)) - /* Speculation was successful. */ + int res; + + res = speculate_expr (insn_to_move_up, full_ds); + if (res >= 0) { - full_ds = 0; - was_changed = true; + /* Speculation was successful. */ + full_ds = 0; + was_changed = (res == 1); + if (ptrans_type) + *ptrans_type = TRANS_SPECULATION; sel_clear_has_dependence (); } } @@ -1953,11 +1985,16 @@ moveup_rhs (rhs_t insn_to_move_up, insn_ if (can_overcome_dep_p (*rhs_dsp)) { - if (speculate_expr (insn_to_move_up, *rhs_dsp)) + int res; + + res = speculate_expr (insn_to_move_up, *rhs_dsp); + if (res >= 0) { /* Speculation was successful. */ *rhs_dsp = 0; - was_changed = true; + was_changed = (res == 1); + if (ptrans_type) + *ptrans_type = TRANS_SPECULATION; } else return MOVEUP_RHS_NULL; @@ -1966,27 +2003,17 @@ moveup_rhs (rhs_t insn_to_move_up, insn_ && insn_eligible_for_subst_p (through_insn)) { /* Substitute in vinsn. */ - line_start (); - print ("Substituting in moveup_rhs:\nBefore: "); - sel_print_rtl (insn); - print ("Moving through: "); - sel_print_rtl (through_insn); - print ("After: "); - if (substitute_reg_in_rhs (insn_to_move_up, through_insn)) - { - EXPR_WAS_SUBSTITUTED (insn_to_move_up) = true; - sel_print_rtl (EXPR_INSN_RTX (insn_to_move_up)); - } + EXPR_WAS_SUBSTITUTED (insn_to_move_up) = true; else - { - print ("Can't move up due to architecture constraints.\n"); - line_finish (); - return MOVEUP_RHS_NULL; - } + return MOVEUP_RHS_NULL; + /* ??? We cannot perform substitution AND speculation on the same + insn. */ + gcc_assert (!was_changed); was_changed = true; - line_finish (); + if (ptrans_type) + *ptrans_type = TRANS_SUBSTITUTION; } else return MOVEUP_RHS_NULL; @@ -2018,8 +2045,11 @@ moveup_set_rhs (av_set_t *avp, insn_t in FOR_EACH_RHS_1 (rhs, i, avp) { - int rhs_uid = INSN_UID (EXPR_INSN_RTX (rhs)); - bool unique_p = VINSN_UNIQUE_P (RHS_VINSN (rhs)); + vinsn_t expr_old_vinsn = EXPR_VINSN (rhs); + ds_t expr_old_spec_ds = EXPR_SPEC_DONE_DS (rhs); + int rhs_uid = INSN_UID (VINSN_INSN (expr_old_vinsn)); + bool unique_p = VINSN_UNIQUE_P (expr_old_vinsn); + enum local_trans_type trans_type; line_start (); dump_rhs (rhs); @@ -2046,8 +2076,11 @@ moveup_set_rhs (av_set_t *avp, insn_t in line_finish (); continue; } - - switch (moveup_rhs (rhs, insn, inside_insn_group)) + + /* ??? Invent something better than this. We can't allow old_vinsn + to go, we need it for the history vector. */ + vinsn_attach (expr_old_vinsn); + switch (moveup_rhs (rhs, insn, inside_insn_group, &trans_type)) { case MOVEUP_RHS_NULL: /* Cache that there is a hard dependence. */ @@ -2063,8 +2096,10 @@ moveup_set_rhs (av_set_t *avp, insn_t in gcc_assert (INSN_UID (EXPR_INSN_RTX (rhs)) != rhs_uid); /* Mark that this insn changed this expr. */ - insert_in_hash_vect (&EXPR_CHANGED_ON_INSNS (rhs), - VINSN_HASH (INSN_VINSN (insn))); + insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (rhs), + INSN_UID (insn), trans_type, + expr_old_vinsn, EXPR_VINSN (rhs), + expr_old_spec_ds); rhs = merge_with_other_exprs (avp, &i, rhs); print (" result: "); @@ -2090,6 +2125,7 @@ moveup_set_rhs (av_set_t *avp, insn_t in gcc_unreachable (); } + vinsn_detach (expr_old_vinsn); line_finish (); } @@ -2138,7 +2174,8 @@ equal_after_moveup_path_p_1 (rhs_t rhs, res = true; if (res) - res = (moveup_rhs (rhs, ILIST_INSN (path), true) != MOVEUP_RHS_NULL); + res = (moveup_rhs (rhs, ILIST_INSN (path), true, NULL) + != MOVEUP_RHS_NULL); return res; } @@ -3831,6 +3868,11 @@ find_best_expr (av_set_t *av_vliw_ptr, b /* Functions that implement the core of the scheduler. */ +/* These bitmaps record original instructions scheduled on the current + iteration and bookkeeping copies created by them. */ +static bitmap current_originators = NULL; +static bitmap current_copies = NULL; + /* Emit an instruction from EXPR with SEQNO after PLACE_TO_INSERT. */ static insn_t gen_insn_from_expr_after (expr_t expr, int seqno, insn_t place_to_insert) @@ -4075,6 +4117,10 @@ generate_bookkeeping_insn (rhs_t c_rhs, change_vinsn_in_expr (new_expr, new_vinsn); new_insn = gen_insn_from_expr_after (new_expr, new_seqno, place_to_insert); + INSN_SCHED_TIMES (new_insn) = 0; + bitmap_set_bit (current_copies, INSN_UID (new_insn)); + clear_expr (new_expr); + /* When inserting bookkeeping insn in new block, av sets should be following: old basic block (that now holds bookkeeping) data sets are the same as was before generation of bookkeeping, and new basic block @@ -4087,25 +4133,6 @@ generate_bookkeeping_insn (rhs_t c_rhs, exchange_data_sets (BLOCK_FOR_INSN (new_insn), BLOCK_FOR_INSN (join_point)); - /* Not obvoius. Set sched times of bookkeeping to sched times of join - point if join point is not header of loop while pipelining (in this - case set it to zero). This is done to correctly handle inserting of - bookkeeping in already scheduled code: when bookkeeping is inserted in - code not yet scheduled (including preheader when pipelining) it will - recieve zero sched times (as join point is not scheduled) - and when bookkeeping is inserted in scheduled code there will not be a - gap of sched times in scheduled code, so is_ineligible_successor_p of - path going through bookkeeping will not say that join point is - ineligible. */ - INSN_SCHED_TIMES (new_insn) = - (pipelining_p - && ((flag_sel_sched_pipelining_outer_loops - && join_point == NEXT_INSN (bb_note (EBB_FIRST_BB (1)))) - || (join_point == NEXT_INSN (bb_note (EBB_FIRST_BB (0)))))) - ? 0 : INSN_SCHED_TIMES (join_point); - - clear_expr (new_expr); - gcc_assert ((src == NULL && BB_END (bb) == new_insn && sel_bb_head_p (new_insn)) || (src == NULL && control_flow_insn_p (BB_END (other_block)) @@ -4326,10 +4353,6 @@ fill_insns (fence_t fence, int seqno, il av_set_clear (&BND_AV (bnd)); BND_AV (bnd) = compute_av_set (BND_TO (bnd), NULL, 0, true); -#if 0 - mark_unavailable_targets - (BND_AV (bnd), BB_LV_SET (BLOCK_FOR_INSN (BND_TO (bnd)))); -#endif av_set_clear (&BND_AV1 (bnd)); BND_AV1 (bnd) = av_set_copy (BND_AV (bnd)); @@ -4596,12 +4619,30 @@ fill_insns (fence_t fence, int seqno, il at before BND_TO (BND). */ n_bookkeeping_copies_before_moveop = stat_bookkeeping_copies; max_uid_before_move_op = get_max_uid (); + bitmap_clear (current_copies); + bitmap_clear (current_originators); - b = move_op (BND_TO (bnd), rhs_seq, NULL, NULL, NULL, c_rhs); + b = move_op (BND_TO (bnd), rhs_seq, NULL, NULL, NULL, + get_dest_from_orig_ops (rhs_seq), c_rhs); if (stat_bookkeeping_copies > n_bookkeeping_copies_before_moveop) stat_insns_needed_bookkeeping++; + { + unsigned book_uid; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (current_copies, 0, book_uid, bi) + { + /* We allocate these bitmaps lazily. */ + if (! INSN_ORIGINATORS_BY_UID (book_uid)) + INSN_ORIGINATORS_BY_UID (book_uid) = BITMAP_ALLOC (NULL); + + bitmap_copy (INSN_ORIGINATORS_BY_UID (book_uid), + current_originators); + } + } + /* We should be able to find the expression we've chosen for scheduling. */ gcc_assert (b); @@ -4817,11 +4858,10 @@ get_dest_from_orig_ops (av_set_t orig_op bookkeeping code in the join points. Return the current rhs. */ static bool move_op (insn_t insn, av_set_t orig_ops, ilist_t path, edge e1, edge e2, - rhs_t c_rhs) + rtx dest, rhs_t c_rhs) { rhs_t rhs; bool c_rhs_inited_p; - rtx dest; bool generated_nop_p = false; basic_block book_block = NULL; @@ -4872,8 +4912,6 @@ move_op (insn_t insn, av_set_t orig_ops, /*av_set_leave_one (&orig_ops);*/ } - dest = get_dest_from_orig_ops (orig_ops); - /* Look at the insn and decide if it could be an ancestor of currently scheduling operation. If it is so, then the insn "dest = op" could either be replaced with "dest = reg", because REG now holds the result @@ -4897,28 +4935,15 @@ move_op (insn_t insn, av_set_t orig_ops, copy_expr_onside (c_rhs, INSN_EXPR (insn)); c_rhs_inited_p = true; - - /* When an insn we found is not equal to the insn from the orig_ops - set, this means that we've found previously created bookeeping copy. - We cannot return original insn in C_RHS because it was already - scheduled, and using it would break an assert saying that - insn should not be in stream. We need to replace it in C_RHS with - the exact insn that we found. - - Our infrastructure handles this such case with setting AV_LEVEL () - to -1 in generate_bookkeeping_insn (). - - But when there is identical instructions one of which dominates the - other we have the same assert failing. */ - if (RHS_INSN (c_rhs) != insn) - { - /* We now copy INSN_EXPR (insn) to C_RHS, hence the condition is - always false. */ - gcc_unreachable (); - - change_vinsn_in_expr (c_rhs, INSN_VINSN (insn)); - } + /* This can be previously created bookkeeping copy; do not count + these. */ + if (!bitmap_bit_p (current_copies, INSN_UID (insn))) + bitmap_set_bit (current_originators, INSN_UID (insn)); + else + bitmap_clear_bit (current_copies, INSN_UID (insn)); + + /* For instructions we must immediately remove insn from the stream, so subsequent update_data_sets () won't include this insn into av_set. @@ -5041,7 +5066,7 @@ move_op (insn_t insn, av_set_t orig_ops, && succ_i.e2->dest == BLOCK_FOR_INSN (succ)); } - b = move_op (succ, orig_ops, path, succ_i.e1, succ_i.e2, x); + b = move_op (succ, orig_ops, path, succ_i.e1, succ_i.e2, dest, x); if (b) { @@ -5052,7 +5077,7 @@ move_op (insn_t insn, av_set_t orig_ops, dump_rhs (x); line_finish (); - res = moveup_rhs (x, insn, false); + res = moveup_rhs (x, insn, false, NULL); gcc_assert (res != MOVEUP_RHS_NULL); if (!c_rhs_inited_p) @@ -5440,6 +5465,8 @@ sel_region_init (int rgn) bitmap_clear (forced_ebb_heads); setup_nop_vinsn (); + current_copies = BITMAP_ALLOC (NULL); + current_originators = BITMAP_ALLOC (NULL); return false; } @@ -5456,9 +5483,11 @@ sel_region_finish (void) free_nop_pool (); - /* Free the sort vector. */ + /* Free the vectors. */ if (vec_av_set) VEC_free (rhs_t, heap, vec_av_set); + BITMAP_FREE (current_copies); + BITMAP_FREE (current_originators); /* If LV_SET of the region head should be updated, do it now because there will be no other chance. */ @@ -5772,7 +5801,7 @@ sel_sched_region_2 (sel_sched_region_2_d else if (max_f < seqno) max_f = seqno; } - + fences1 = fences; do { Index: gcc/sel-sched-ir.c =================================================================== --- gcc/sel-sched-ir.c (revision 131205) +++ gcc/sel-sched-ir.c (working copy) @@ -915,8 +915,10 @@ free_regset_pool (void) the data sets. When update is finished, NOPs are deleted. */ static void set_insn_init (expr_t, vinsn_t, int); +#if 0 static void vinsn_attach (vinsn_t); static void vinsn_detach (vinsn_t); +#endif /* A vinsn that is used to represent a nop. This vinsn is shared among all nops sel-sched generates. */ @@ -1376,7 +1378,7 @@ vinsn_init (vinsn_t vi, insn_t insn, boo } /* Indicate that VI has become the part of an rtx object. */ -static void +void vinsn_attach (vinsn_t vi) { /* Assert that VI is not pending for deletion. */ @@ -1417,7 +1419,7 @@ vinsn_delete (vinsn_t vi) /* Indicate that VI is no longer a part of some rtx object. Remove VI if it is no longer needed. */ -static void +void vinsn_detach (vinsn_t vi) { gcc_assert (VINSN_COUNT (vi) > 0); @@ -1555,10 +1557,11 @@ sel_gen_insn_from_expr_after (rhs_t expr when found. Write to INDP the index on which the search has stopped, such that inserting HASH at INDP will retain VECT's sort order. */ static bool -find_in_hash_vect_1 (VEC(unsigned, heap) *vect, unsigned hash, int *indp) +find_in_history_vect_1 (VEC(expr_history_def, heap) *vect, + unsigned uid, vinsn_t new_vinsn, int *indp) { - unsigned *arr; - int i, j, len = VEC_length (unsigned, vect); + expr_history_def *arr; + int i, j, len = VEC_length (expr_history_def, vect); if (len == 0) { @@ -1566,51 +1569,51 @@ find_in_hash_vect_1 (VEC(unsigned, heap) return false; } - arr = VEC_address (unsigned, vect); + arr = VEC_address (expr_history_def, vect); i = 0, j = len - 1; while (i <= j) { -#if 0 - int k = (i + j) / 2; - - if (arr[k] == hash) - { - *indp = k; - return true; - } - - if (arr[k] < hash) - i = k + 1; - else - j = k - 1; -#else - unsigned ahash = arr[i]; + unsigned auid = arr[i].uid; + vinsn_t avinsn = arr[i].new_expr_vinsn; - if (ahash == hash) + if (auid == uid + && (avinsn == new_vinsn + || vinsns_correlate_as_rhses_p (avinsn, new_vinsn))) { *indp = i; return true; } - else if (ahash > hash) + else if (auid > uid) break; i++; -#endif } *indp = i; return false; } -/* Search for a hash value HASH in a sorted vector VECT. Return - the position found or -1, if no such value is in vector. */ +/* Search for a uid of INSN a sorted vector VECT. Return + the position found or -1, if no such value is in vector. + Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */ int -find_in_hash_vect (VEC(unsigned, heap) *vect, unsigned hash) +find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn, + vinsn_t new_vinsn, bool originators_p) { int ind; - if (find_in_hash_vect_1 (vect, hash, &ind)) + if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn, &ind)) return ind; + + if (INSN_ORIGINATORS (insn) && originators_p) + { + unsigned uid; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi) + if (find_in_history_vect_1 (vect, uid, new_vinsn, &ind)) + return ind; + } return -1; } @@ -1618,16 +1621,40 @@ find_in_hash_vect (VEC(unsigned, heap) * /* Insert HASH in a sorted vector pointed to by PVECT, if HASH is not there already. */ void -insert_in_hash_vect (VEC (unsigned, heap) **pvect, unsigned hash) +insert_in_history_vect (VEC (expr_history_def, heap) **pvect, + unsigned uid, enum local_trans_type type, + vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn, + ds_t spec_ds) { - VEC(unsigned, heap) *vect = *pvect; + VEC(expr_history_def, heap) *vect = *pvect; + expr_history_def temp; + bool res; int ind; - if (! find_in_hash_vect_1 (vect, hash, &ind)) + res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, &ind); + + if (res) { - VEC_safe_insert (unsigned, heap, vect, ind, hash); - *pvect = vect; + expr_history_def *phist = VEC_index (expr_history_def, vect, ind); + + gcc_assert (phist->spec_ds == spec_ds + && (phist->old_expr_vinsn == old_expr_vinsn + || (phist->new_expr_vinsn != new_expr_vinsn + && (vinsns_correlate_as_rhses_p + (phist->old_expr_vinsn, old_expr_vinsn))))); + return; } + + temp.uid = uid; + temp.old_expr_vinsn = old_expr_vinsn; + temp.new_expr_vinsn = new_expr_vinsn; + temp.spec_ds = spec_ds; + temp.type = type; + + vinsn_attach (old_expr_vinsn); + vinsn_attach (new_expr_vinsn); + VEC_safe_insert (expr_history_def, heap, vect, ind, &temp); + *pvect = vect; } /* Compare two vinsns as rhses if possible and as vinsns otherwise. */ @@ -1661,7 +1688,7 @@ static void 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(unsigned, heap) *changed_on, bool target_available, + VEC(expr_history_def, heap) *history, bool target_available, bool was_substituted, bool was_renamed) { vinsn_attach (vi); @@ -1676,10 +1703,10 @@ init_expr (expr_t expr, vinsn_t vi, int EXPR_SPEC_DONE_DS (expr) = spec_done_ds; EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds; - if (changed_on) - EXPR_CHANGED_ON_INSNS (expr) = changed_on; + if (history) + EXPR_HISTORY_OF_CHANGES (expr) = history; else - EXPR_CHANGED_ON_INSNS (expr) = NULL; + EXPR_HISTORY_OF_CHANGES (expr) = NULL; EXPR_TARGET_AVAILABLE (expr) = target_available; EXPR_WAS_SUBSTITUTED (expr) = was_substituted; @@ -1690,9 +1717,23 @@ init_expr (expr_t expr, vinsn_t vi, int void copy_expr (expr_t to, expr_t from) { - VEC(unsigned, heap) *temp; + VEC(expr_history_def, heap) *temp = NULL; + + if (EXPR_HISTORY_OF_CHANGES (from)) + { + unsigned i; + expr_history_def *phist; + + temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from)); + for (i = 0; + VEC_iterate (expr_history_def, temp, i, phist); + i++) + { + vinsn_attach (phist->old_expr_vinsn); + vinsn_attach (phist->new_expr_vinsn); + } + } - temp = VEC_copy (unsigned, heap, EXPR_CHANGED_ON_INSNS (from)); init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from), EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from), @@ -1720,8 +1761,8 @@ void merge_expr_data (expr_t to, expr_t from, bool join_point_p) { int i; - unsigned hash; - + expr_history_def *phist; + /* For now, we just set the spec of resulting rhs to be minimum of the specs of merged rhses. */ if (RHS_SPEC (to) > RHS_SPEC (from)) @@ -1788,9 +1829,13 @@ merge_expr_data (expr_t to, expr_t from, /* We keep this vector sorted. */ for (i = 0; - VEC_iterate (unsigned, EXPR_CHANGED_ON_INSNS (from), i, hash); + VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (from), + i, phist); i++) - insert_in_hash_vect (&EXPR_CHANGED_ON_INSNS (to), hash); + insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to), + phist->uid, phist->type, + phist->old_expr_vinsn, phist->new_expr_vinsn, + phist->spec_ds); EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from); EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (to); @@ -1821,9 +1866,27 @@ merge_expr (expr_t to, expr_t from, bool void clear_expr (rhs_t rhs) { + vinsn_detach (RHS_VINSN (rhs)); RHS_VINSN (rhs) = NULL; - VEC_free (unsigned, heap, EXPR_CHANGED_ON_INSNS (rhs)); + + if (EXPR_HISTORY_OF_CHANGES (rhs)) + { + unsigned i; + expr_history_def *phist; + + for (i = 0; + VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (rhs), + i, phist); + i++) + { + vinsn_detach (phist->old_expr_vinsn); + vinsn_detach (phist->new_expr_vinsn); + } + + VEC_free (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (rhs)); + EXPR_HISTORY_OF_CHANGES (rhs) = NULL; + } } /* For a given LV_SET, mark EXPR having unavailable target register. */ @@ -2480,6 +2543,10 @@ free_first_time_insn_data (insn_t insn) BITMAP_FREE (INSN_ANALYZED_DEPS (insn)); BITMAP_FREE (INSN_FOUND_DEPS (insn)); + + /* This is allocated only for bookkeeping insns. */ + if (INSN_ORIGINATORS (insn)) + BITMAP_FREE (INSN_ORIGINATORS (insn)); free_deps (&INSN_DEPS_CONTEXT (insn)); } @@ -4345,8 +4412,9 @@ is_ineligible_successor (insn_t insn, il /* An insn from another fence could also be scheduled earlier even if this insn is not in a fence list right now. Check INSN_SCHED_CYCLE instead. */ - || ((!pipelining_p || !path_contains_back_edge_p (p)) - && path_contains_switch_of_sched_times_p (insn, p))) + || (!pipelining_p + && INSN_SCHED_TIMES (insn) > 0)) + return true; else return false; @@ -4364,7 +4432,7 @@ bb_ends_ebb_p (basic_block bb) if (next_bb == EXIT_BLOCK_PTR || bitmap_bit_p (forced_ebb_heads, next_bb->index) || (LABEL_P (BB_HEAD (next_bb)) - /* NB: LABEL_NUSES () is not maintained outside of jump.c . + /* NB: LABEL_NUSES () is not maintained outside of jump.c. Work around that. */ && !single_pred_p (next_bb))) return true; @@ -4449,7 +4517,6 @@ clear_outdated_rtx_info (basic_block bb) } typedef VEC(rtx, heap) *rtx_vec_t; - static rtx_vec_t bb_note_pool; /* Add BB_NOTE to the pool of available basic block notes. */ Index: gcc/sel-sched-ir.h =================================================================== --- gcc/sel-sched-ir.h (revision 131184) +++ gcc/sel-sched-ir.h (working copy) @@ -78,6 +78,39 @@ typedef _xlist_t ilist_t; #define ILIST_INSN(L) (_XLIST_X (L)) #define ILIST_NEXT(L) (_XLIST_NEXT (L)) +/* This lists possible transformations that done locally, i.e. in + moveup_expr. */ +enum local_trans_type + { + TRANS_SUBSTITUTION, + TRANS_SPECULATION + }; + +/* This struct is used to record the history of expression's + transformations. */ +struct expr_history_def_1 +{ + /* UID of the insn. */ + unsigned uid; + + /* How the expression looked like. */ + vinsn_t old_expr_vinsn; + + /* How the expression looks after the transformation. */ + vinsn_t new_expr_vinsn; + + /* And its speculative status. */ + ds_t spec_ds; + + /* Type of the transformation. */ + enum local_trans_type type; +}; + +typedef struct expr_history_def_1 expr_history_def; + +DEF_VEC_O (expr_history_def); +DEF_VEC_ALLOC_O (expr_history_def, heap); + /* Right hand side information. */ struct _expr { @@ -117,11 +150,8 @@ struct _expr been scheduled or more than one originator. */ int orig_sched_cycle; - /* A vector of insn's hashes on which this expr was changed when - moving up. We can't use bitmap here, because the recorded insn - could be scheduled, and its bookkeeping copies should be checked - instead. */ - VEC(unsigned, heap) *changed_on_insns; + /* 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 is available for scheduling, false otherwise. -1 means we're not sure; @@ -158,7 +188,7 @@ typedef expr_t rhs_t; #define EXPR_ORIG_SCHED_CYCLE(EXPR) ((EXPR)->orig_sched_cycle) #define EXPR_SPEC_DONE_DS(EXPR) ((EXPR)->spec_done_ds) #define EXPR_SPEC_TO_CHECK_DS(EXPR) ((EXPR)->spec_to_check_ds) -#define EXPR_CHANGED_ON_INSNS(EXPR) ((EXPR)->changed_on_insns) +#define EXPR_HISTORY_OF_CHANGES(EXPR) ((EXPR)->history_of_changes) #define EXPR_TARGET_AVAILABLE(EXPR) ((EXPR)->target_available) #define EXPR_WAS_SUBSTITUTED(EXPR) ((EXPR)->was_substituted) #define EXPR_WAS_RENAMED(EXPR) ((EXPR)->was_renamed) @@ -635,14 +665,18 @@ struct _sel_insn_data int seqno; - /* An INSN_LUID bit is set when deps analysis result is already known. */ + /* An INSN_UID bit is set when deps analysis result is already known. */ bitmap analyzed_deps; - /* An INSN_LUID 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. */ + bitmap originators; + /* A context incapsulating this insn. */ struct deps deps_context; @@ -678,6 +712,7 @@ extern VEC (sel_insn_data_def, heap) *s_ /* Accessor macros for s_i_d. */ #define SID(INSN) (VEC_index (sel_insn_data_def, s_i_d, INSN_LUID (INSN))) +#define SID_BY_UID(UID) (VEC_index (sel_insn_data_def, s_i_d, LUID_BY_UID (UID))) extern sel_insn_data_def insn_sid (insn_t); @@ -686,6 +721,9 @@ extern sel_insn_data_def insn_sid (insn_ #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_ORIGINATORS(INSN) (SID (INSN)->originators) +#define INSN_ORIGINATORS_BY_UID(UID) (SID_BY_UID (UID)->originators) + #define INSN_EXPR(INSN) (&SID (INSN)->_expr) #define INSN_VINSN(INSN) (RHS_VINSN (INSN_EXPR (INSN))) @@ -934,6 +972,9 @@ extern int sel_vinsn_cost (vinsn_t); extern insn_t sel_gen_insn_from_rtx_after (rtx, expr_t, int, insn_t); extern insn_t sel_gen_recovery_insn_from_rtx_after (rtx, expr_t, int, insn_t); extern insn_t sel_gen_insn_from_expr_after (expr_t, int, insn_t); +extern void vinsn_attach (vinsn_t); +extern void vinsn_detach (vinsn_t); + /* RHS functions. */ extern bool vinsns_correlate_as_rhses_p (vinsn_t, vinsn_t); @@ -944,8 +985,11 @@ extern void merge_expr (expr_t, expr_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_hash_vect (VEC(unsigned, heap) *, unsigned); -extern void insert_in_hash_vect (VEC(unsigned, heap) **, unsigned); +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, + vinsn_t, vinsn_t, ds_t); extern void mark_unavailable_targets (av_set_t, av_set_t, regset); /* Av set functions. */ Index: gcc/sched-int.h =================================================================== --- gcc/sched-int.h (revision 131205) +++ gcc/sched-int.h (working copy) @@ -129,6 +129,8 @@ extern regset *glat_start, *glat_end; structures should be indexed by luid. */ extern VEC (int, heap) *sched_luids; #define INSN_LUID(INSN) (VEC_index (int, sched_luids, INSN_UID (INSN))) +#define LUID_BY_UID(UID) (VEC_index (int, sched_luids, UID)) + #define SET_INSN_LUID(INSN, LUID) \ (VEC_replace (int, sched_luids, INSN_UID (INSN), (LUID))) Index: gcc/sched-rgn.c =================================================================== --- gcc/sched-rgn.c (revision 131205) +++ gcc/sched-rgn.c (working copy) @@ -2615,7 +2615,9 @@ compute_block_dependences (int bb) } #endif - add_branch_dependences (head, tail); + /* Selective scheduling handles control dependencies by itself. */ + if (!SEL_SCHED_P) + add_branch_dependences (head, tail); if (current_nr_blocks > 1) propagate_deps (bb, &tmp_deps); @@ -2767,7 +2769,6 @@ free_rgn_deps (void) { int bb; - for (bb = 0; bb < current_nr_blocks; bb++) { rtx head, tail; Index: gcc/config/ia64/ia64.c =================================================================== --- gcc/config/ia64/ia64.c (revision 131205) +++ gcc/config/ia64/ia64.c (working copy) @@ -7519,7 +7519,7 @@ ia64_speculate_insn (rtx insn, ds_t ts, point operation that might trap. */ return -1; - if (ia64_get_insn_spec_ds (insn) == ts) + if (ia64_get_insn_spec_ds (insn) == ds_get_speculation_types (ts)) res = 0; else {