| /* Instruction scheduling pass. Selective scheduler and pipeliner. |
| Copyright (C) 2006-2017 Free Software Foundation, Inc. |
| |
| This file is part of GCC. |
| |
| 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 |
| Software Foundation; either version 3, or (at your option) any later |
| version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "tree.h" |
| #include "rtl.h" |
| #include "df.h" |
| #include "memmodel.h" |
| #include "tm_p.h" |
| #include "regs.h" |
| #include "cfgbuild.h" |
| #include "insn-config.h" |
| #include "insn-attr.h" |
| #include "params.h" |
| #include "target.h" |
| #include "sched-int.h" |
| #include "rtlhooks-def.h" |
| #include "ira.h" |
| #include "ira-int.h" |
| #include "rtl-iter.h" |
| |
| #ifdef INSN_SCHEDULING |
| #include "regset.h" |
| #include "cfgloop.h" |
| #include "sel-sched-ir.h" |
| #include "sel-sched-dump.h" |
| #include "sel-sched.h" |
| #include "dbgcnt.h" |
| |
| /* Implementation of selective scheduling approach. |
| The below implementation follows the original approach with the following |
| changes: |
| |
| o the scheduler works after register allocation (but can be also tuned |
| to work before RA); |
| o some instructions are not copied or register renamed; |
| o conditional jumps are not moved with code duplication; |
| o several jumps in one parallel group are not supported; |
| o when pipelining outer loops, code motion through inner loops |
| is not supported; |
| o control and data speculation are supported; |
| o some improvements for better compile time/performance were made. |
| |
| Terminology |
| =========== |
| |
| A vinsn, or virtual insn, is an insn with additional data characterizing |
| insn pattern, such as LHS, RHS, register sets used/set/clobbered, etc. |
| Vinsns also act as smart pointers to save memory by reusing them in |
| different expressions. A vinsn is described by vinsn_t type. |
| |
| An expression is a vinsn with additional data characterizing its properties |
| at some point in the control flow graph. The data may be its usefulness, |
| priority, speculative status, whether it was renamed/subsituted, etc. |
| An expression is described by expr_t type. |
| |
| Availability set (av_set) is a set of expressions at a given control flow |
| point. It is represented as av_set_t. The expressions in av sets are kept |
| sorted in the terms of expr_greater_p function. It allows to truncate |
| the set while leaving the best expressions. |
| |
| A fence is a point through which code motion is prohibited. On each step, |
| we gather a parallel group of insns at a fence. It is possible to have |
| multiple fences. A fence is represented via fence_t. |
| |
| A boundary is the border between the fence group and the rest of the code. |
| Currently, we never have more than one boundary per fence, as we finalize |
| the fence group when a jump is scheduled. A boundary is represented |
| via bnd_t. |
| |
| High-level overview |
| =================== |
| |
| The scheduler finds regions to schedule, schedules each one, and finalizes. |
| The regions are formed starting from innermost loops, so that when the inner |
| loop is pipelined, its prologue can be scheduled together with yet unprocessed |
| outer loop. The rest of acyclic regions are found using extend_rgns: |
| the blocks that are not yet allocated to any regions are traversed in top-down |
| order, and a block is added to a region to which all its predecessors belong; |
| otherwise, the block starts its own region. |
| |
| The main scheduling loop (sel_sched_region_2) consists of just |
| scheduling on each fence and updating fences. For each fence, |
| we fill a parallel group of insns (fill_insns) until some insns can be added. |
| First, we compute available exprs (av-set) at the boundary of the current |
| group. Second, we choose the best expression from it. If the stall is |
| required to schedule any of the expressions, we advance the current cycle |
| appropriately. So, the final group does not exactly correspond to a VLIW |
| word. Third, we move the chosen expression to the boundary (move_op) |
| and update the intermediate av sets and liveness sets. We quit fill_insns |
| when either no insns left for scheduling or we have scheduled enough insns |
| so we feel like advancing a scheduling point. |
| |
| Computing available expressions |
| =============================== |
| |
| The computation (compute_av_set) is a bottom-up traversal. At each insn, |
| we're moving the union of its successors' sets through it via |
| moveup_expr_set. The dependent expressions are removed. Local |
| transformations (substitution, speculation) are applied to move more |
| exprs. Then the expr corresponding to the current insn is added. |
| The result is saved on each basic block header. |
| |
| When traversing the CFG, we're moving down for no more than max_ws insns. |
| Also, we do not move down to ineligible successors (is_ineligible_successor), |
| which include moving along a back-edge, moving to already scheduled code, |
| and moving to another fence. The first two restrictions are lifted during |
| pipelining, which allows us to move insns along a back-edge. We always have |
| an acyclic region for scheduling because we forbid motion through fences. |
| |
| Choosing the best expression |
| ============================ |
| |
| We sort the final availability set via sel_rank_for_schedule, then we remove |
| expressions which are not yet ready (tick_check_p) or which dest registers |
| cannot be used. For some of them, we choose another register via |
| find_best_reg. To do this, we run find_used_regs to calculate the set of |
| registers which cannot be used. The find_used_regs function performs |
| a traversal of code motion paths for an expr. We consider for renaming |
| only registers which are from the same regclass as the original one and |
| using which does not interfere with any live ranges. Finally, we convert |
| the resulting set to the ready list format and use max_issue and reorder* |
| hooks similarly to the Haifa scheduler. |
| |
| Scheduling the best expression |
| ============================== |
| |
| We run the move_op routine to perform the same type of code motion paths |
| traversal as in find_used_regs. (These are working via the same driver, |
| code_motion_path_driver.) When moving down the CFG, we look for original |
| instruction that gave birth to a chosen expression. We undo |
| the transformations performed on an expression via the history saved in it. |
| When found, we remove the instruction or leave a reg-reg copy/speculation |
| check if needed. On a way up, we insert bookkeeping copies at each join |
| point. If a copy is not needed, it will be removed later during this |
| traversal. We update the saved av sets and liveness sets on the way up, too. |
| |
| Finalizing the schedule |
| ======================= |
| |
| When pipelining, we reschedule the blocks from which insns were pipelined |
| to get a tighter schedule. On Itanium, we also perform bundling via |
| the same routine from ia64.c. |
| |
| Dependence analysis changes |
| =========================== |
| |
| We augmented the sched-deps.c with hooks that get called when a particular |
| dependence is found in a particular part of an insn. Using these hooks, we |
| can do several actions such as: determine whether an insn can be moved through |
| another (has_dependence_p, moveup_expr); find out whether an insn can be |
| scheduled on the current cycle (tick_check_p); find out registers that |
| are set/used/clobbered by an insn and find out all the strange stuff that |
| restrict its movement, like SCHED_GROUP_P or CANT_MOVE (done in |
| init_global_and_expr_for_insn). |
| |
| Initialization changes |
| ====================== |
| |
| There are parts of haifa-sched.c, sched-deps.c, and sched-rgn.c that are |
| reused in all of the schedulers. We have split up the initialization of data |
| of such parts into different functions prefixed with scheduler type and |
| postfixed with the type of data initialized: {,sel_,haifa_}sched_{init,finish}, |
| sched_rgn_init/finish, sched_deps_init/finish, sched_init_{luids/bbs}, etc. |
| The same splitting is done with current_sched_info structure: |
| dependence-related parts are in sched_deps_info, common part is in |
| common_sched_info, and haifa/sel/etc part is in current_sched_info. |
| |
| Target contexts |
| =============== |
| |
| As we now have multiple-point scheduling, this would not work with backends |
| which save some of the scheduler state to use it in the target hooks. |
| For this purpose, we introduce a concept of target contexts, which |
| encapsulate such information. The backend should implement simple routines |
| of allocating/freeing/setting such a context. The scheduler calls these |
| as target hooks and handles the target context as an opaque pointer (similar |
| to the DFA state type, state_t). |
| |
| Various speedups |
| ================ |
| |
| As the correct data dependence graph is not supported during scheduling (which |
| is to be changed in mid-term), we cache as much of the dependence analysis |
| results as possible to avoid reanalyzing. This includes: bitmap caches on |
| each insn in stream of the region saying yes/no for a query with a pair of |
| UIDs; hashtables with the previously done transformations on each insn in |
| stream; a vector keeping a history of transformations on each expr. |
| |
| Also, we try to minimize the dependence context used on each fence to check |
| whether the given expression is ready for scheduling by removing from it |
| insns that are definitely completed the execution. The results of |
| tick_check_p checks are also cached in a vector on each fence. |
| |
| We keep a valid liveness set on each insn in a region to avoid the high |
| cost of recomputation on large basic blocks. |
| |
| Finally, we try to minimize the number of needed updates to the availability |
| sets. The updates happen in two cases: when fill_insns terminates, |
| we advance all fences and increase the stage number to show that the region |
| has changed and the sets are to be recomputed; and when the next iteration |
| of a loop in fill_insns happens (but this one reuses the saved av sets |
| on bb headers.) Thus, we try to break the fill_insns loop only when |
| "significant" number of insns from the current scheduling window was |
| scheduled. This should be made a target param. |
| |
| |
| TODO: correctly support the data dependence graph at all stages and get rid |
| of all caches. This should speed up the scheduler. |
| TODO: implement moving cond jumps with bookkeeping copies on both targets. |
| TODO: tune the scheduler before RA so it does not create too much pseudos. |
| |
| |
| References: |
| S.-M. Moon and K. Ebcioglu. Parallelizing nonnumerical code with |
| selective scheduling and software pipelining. |
| ACM TOPLAS, Vol 19, No. 6, pages 853--898, Nov. 1997. |
| |
| Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik, |
| and Dmitry Zhurikhin. An interblock VLIW-targeted instruction scheduler |
| for GCC. In Proceedings of GCC Developers' Summit 2006. |
| |
| Arutyun Avetisyan, Andrey Belevantsev, and Dmitry Melnik. GCC Instruction |
| Scheduler and Software Pipeliner on the Itanium Platform. EPIC-7 Workshop. |
| http://rogue.colorado.edu/EPIC7/. |
| |
| */ |
| |
| /* True when pipelining is enabled. */ |
| bool pipelining_p; |
| |
| /* True if bookkeeping is enabled. */ |
| bool bookkeeping_p; |
| |
| /* Maximum number of insns that are eligible for renaming. */ |
| int max_insns_to_rename; |
| |
| |
| /* Definitions of local types and macros. */ |
| |
| /* Represents possible outcomes of moving an expression through an insn. */ |
| enum MOVEUP_EXPR_CODE |
| { |
| /* The expression is not changed. */ |
| MOVEUP_EXPR_SAME, |
| |
| /* Not changed, but requires a new destination register. */ |
| MOVEUP_EXPR_AS_RHS, |
| |
| /* Cannot be moved. */ |
| MOVEUP_EXPR_NULL, |
| |
| /* Changed (substituted or speculated). */ |
| MOVEUP_EXPR_CHANGED |
| }; |
| |
| /* The container to be passed into rtx search & replace functions. */ |
| struct rtx_search_arg |
| { |
| /* What we are searching for. */ |
| rtx x; |
| |
| /* The occurrence counter. */ |
| int n; |
| }; |
| |
| typedef struct rtx_search_arg *rtx_search_arg_p; |
| |
| /* This struct contains precomputed hard reg sets that are needed when |
| computing registers available for renaming. */ |
| struct hard_regs_data |
| { |
| /* For every mode, this stores registers available for use with |
| that mode. */ |
| HARD_REG_SET regs_for_mode[NUM_MACHINE_MODES]; |
| |
| /* True when regs_for_mode[mode] is initialized. */ |
| bool regs_for_mode_ok[NUM_MACHINE_MODES]; |
| |
| /* For every register, it has regs that are ok to rename into it. |
| The register in question is always set. If not, this means |
| that the whole set is not computed yet. */ |
| HARD_REG_SET regs_for_rename[FIRST_PSEUDO_REGISTER]; |
| |
| /* For every mode, this stores registers not available due to |
| call clobbering. */ |
| HARD_REG_SET regs_for_call_clobbered[NUM_MACHINE_MODES]; |
| |
| /* All registers that are used or call used. */ |
| HARD_REG_SET regs_ever_used; |
| |
| #ifdef STACK_REGS |
| /* Stack registers. */ |
| HARD_REG_SET stack_regs; |
| #endif |
| }; |
| |
| /* Holds the results of computation of available for renaming and |
| unavailable hard registers. */ |
| struct reg_rename |
| { |
| /* These are unavailable due to calls crossing, globalness, etc. */ |
| HARD_REG_SET unavailable_hard_regs; |
| |
| /* These are *available* for renaming. */ |
| HARD_REG_SET available_for_renaming; |
| |
| /* Whether this code motion path crosses a call. */ |
| bool crosses_call; |
| }; |
| |
| /* A global structure that contains the needed information about harg |
| regs. */ |
| static struct hard_regs_data sel_hrd; |
| |
| |
| /* This structure holds local data used in code_motion_path_driver hooks on |
| the same or adjacent levels of recursion. Here we keep those parameters |
| that are not used in code_motion_path_driver routine itself, but only in |
| its hooks. Moreover, all parameters that can be modified in hooks are |
| in this structure, so all other parameters passed explicitly to hooks are |
| read-only. */ |
| struct cmpd_local_params |
| { |
| /* Local params used in move_op_* functions. */ |
| |
| /* Edges for bookkeeping generation. */ |
| edge e1, e2; |
| |
| /* C_EXPR merged from all successors and locally allocated temporary C_EXPR. */ |
| expr_t c_expr_merged, c_expr_local; |
| |
| /* Local params used in fur_* functions. */ |
| /* Copy of the ORIGINAL_INSN list, stores the original insns already |
| found before entering the current level of code_motion_path_driver. */ |
| def_list_t old_original_insns; |
| |
| /* Local params used in move_op_* functions. */ |
| /* True when we have removed last insn in the block which was |
| also a boundary. Do not update anything or create bookkeeping copies. */ |
| BOOL_BITFIELD removed_last_insn : 1; |
| }; |
| |
| /* Stores the static parameters for move_op_* calls. */ |
| struct moveop_static_params |
| { |
| /* Destination register. */ |
| rtx dest; |
| |
| /* Current C_EXPR. */ |
| expr_t c_expr; |
| |
| /* An UID of expr_vliw which is to be moved up. If we find other exprs, |
| they are to be removed. */ |
| int uid; |
| |
| /* This is initialized to the insn on which the driver stopped its traversal. */ |
| insn_t failed_insn; |
| |
| /* True if we scheduled an insn with different register. */ |
| bool was_renamed; |
| }; |
| |
| /* Stores the static parameters for fur_* calls. */ |
| struct fur_static_params |
| { |
| /* Set of registers unavailable on the code motion path. */ |
| regset used_regs; |
| |
| /* Pointer to the list of original insns definitions. */ |
| def_list_t *original_insns; |
| |
| /* True if a code motion path contains a CALL insn. */ |
| bool crosses_call; |
| }; |
| |
| typedef struct fur_static_params *fur_static_params_p; |
| typedef struct cmpd_local_params *cmpd_local_params_p; |
| typedef struct moveop_static_params *moveop_static_params_p; |
| |
| /* Set of hooks and parameters that determine behavior specific to |
| move_op or find_used_regs functions. */ |
| struct code_motion_path_driver_info_def |
| { |
| /* Called on enter to the basic block. */ |
| int (*on_enter) (insn_t, cmpd_local_params_p, void *, bool); |
| |
| /* Called when original expr is found. */ |
| void (*orig_expr_found) (insn_t, expr_t, cmpd_local_params_p, void *); |
| |
| /* Called while descending current basic block if current insn is not |
| the original EXPR we're searching for. */ |
| bool (*orig_expr_not_found) (insn_t, av_set_t, void *); |
| |
| /* Function to merge C_EXPRes from different successors. */ |
| void (*merge_succs) (insn_t, insn_t, int, cmpd_local_params_p, void *); |
| |
| /* Function to finalize merge from different successors and possibly |
| deallocate temporary data structures used for merging. */ |
| void (*after_merge_succs) (cmpd_local_params_p, void *); |
| |
| /* Called on the backward stage of recursion to do moveup_expr. |
| Used only with move_op_*. */ |
| void (*ascend) (insn_t, void *); |
| |
| /* Called on the ascending pass, before returning from the current basic |
| block or from the whole traversal. */ |
| void (*at_first_insn) (insn_t, cmpd_local_params_p, void *); |
| |
| /* When processing successors in move_op we need only descend into |
| SUCCS_NORMAL successors, while in find_used_regs we need SUCCS_ALL. */ |
| int succ_flags; |
| |
| /* The routine name to print in dumps ("move_op" of "find_used_regs"). */ |
| const char *routine_name; |
| }; |
| |
| /* Global pointer to current hooks, either points to MOVE_OP_HOOKS or |
| FUR_HOOKS. */ |
| struct code_motion_path_driver_info_def *code_motion_path_driver_info; |
| |
| /* Set of hooks for performing move_op and find_used_regs routines with |
| code_motion_path_driver. */ |
| extern struct code_motion_path_driver_info_def move_op_hooks, fur_hooks; |
| |
| /* True if/when we want to emulate Haifa scheduler in the common code. |
| This is used in sched_rgn_local_init and in various places in |
| sched-deps.c. */ |
| int sched_emulate_haifa_p; |
| |
| /* GLOBAL_LEVEL is used to discard information stored in basic block headers |
| av_sets. Av_set of bb header is valid if its (bb header's) level is equal |
| to GLOBAL_LEVEL. And invalid if lesser. This is primarily used to advance |
| scheduling window. */ |
| int global_level; |
| |
| /* Current fences. */ |
| flist_t fences; |
| |
| /* True when separable insns should be scheduled as RHSes. */ |
| static bool enable_schedule_as_rhs_p; |
| |
| /* Used in verify_target_availability to assert that target reg is reported |
| unavailabile by both TARGET_UNAVAILABLE and find_used_regs only if |
| we haven't scheduled anything on the previous fence. |
| if scheduled_something_on_previous_fence is true, TARGET_UNAVAILABLE can |
| have more conservative value than the one returned by the |
| find_used_regs, thus we shouldn't assert that these values are equal. */ |
| static bool scheduled_something_on_previous_fence; |
| |
| /* All newly emitted insns will have their uids greater than this value. */ |
| static int first_emitted_uid; |
| |
| /* Set of basic blocks that are forced to start new ebbs. This is a subset |
| of all the ebb heads. */ |
| static bitmap_head _forced_ebb_heads; |
| bitmap_head *forced_ebb_heads = &_forced_ebb_heads; |
| |
| /* Blocks that need to be rescheduled after pipelining. */ |
| bitmap blocks_to_reschedule = NULL; |
| |
| /* True when the first lv set should be ignored when updating liveness. */ |
| static bool ignore_first = false; |
| |
| /* Number of insns max_issue has initialized data structures for. */ |
| static int max_issue_size = 0; |
| |
| /* Whether we can issue more instructions. */ |
| static int can_issue_more; |
| |
| /* Maximum software lookahead window size, reduced when rescheduling after |
| pipelining. */ |
| static int max_ws; |
| |
| /* Number of insns scheduled in current region. */ |
| static int num_insns_scheduled; |
| |
| /* A vector of expressions is used to be able to sort them. */ |
| static vec<expr_t> vec_av_set; |
| |
| /* A vector of vinsns is used to hold temporary lists of vinsns. */ |
| typedef vec<vinsn_t> vinsn_vec_t; |
| |
| /* This vector has the exprs which may still present in av_sets, but actually |
| can't be moved up due to bookkeeping created during code motion to another |
| fence. See comment near the call to update_and_record_unavailable_insns |
| for the detailed explanations. */ |
| static vinsn_vec_t vec_bookkeeping_blocked_vinsns = vinsn_vec_t (); |
| |
| /* This vector has vinsns which are scheduled with renaming on the first fence |
| and then seen on the second. For expressions with such vinsns, target |
| availability information may be wrong. */ |
| static vinsn_vec_t vec_target_unavailable_vinsns = vinsn_vec_t (); |
| |
| /* Vector to store temporary nops inserted in move_op to prevent removal |
| of empty bbs. */ |
| static vec<insn_t> vec_temp_moveop_nops; |
| |
| /* 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; |
| |
| /* This bitmap marks the blocks visited by code_motion_path_driver so we don't |
| visit them afterwards. */ |
| static bitmap code_motion_visited_blocks = NULL; |
| |
| /* Variables to accumulate different statistics. */ |
| |
| /* The number of bookkeeping copies created. */ |
| static int stat_bookkeeping_copies; |
| |
| /* The number of insns that required bookkeeiping for their scheduling. */ |
| static int stat_insns_needed_bookkeeping; |
| |
| /* The number of insns that got renamed. */ |
| static int stat_renamed_scheduled; |
| |
| /* The number of substitutions made during scheduling. */ |
| static int stat_substitutions_total; |
| |
| |
| /* Forward declarations of static functions. */ |
| static bool rtx_ok_for_substitution_p (rtx, rtx); |
| static int sel_rank_for_schedule (const void *, const void *); |
| static av_set_t find_sequential_best_exprs (bnd_t, expr_t, bool); |
| static basic_block find_block_for_bookkeeping (edge e1, edge e2, bool lax); |
| |
| static rtx get_dest_from_orig_ops (av_set_t); |
| static basic_block generate_bookkeeping_insn (expr_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, expr_t, rtx, expr_t, bool*); |
| static int code_motion_path_driver (insn_t, av_set_t, ilist_t, |
| cmpd_local_params_p, void *); |
| static void sel_sched_region_1 (void); |
| static void sel_sched_region_2 (int); |
| static av_set_t compute_av_set_inside_bb (insn_t, ilist_t, int, bool); |
| |
| static void debug_state (state_t); |
| |
| |
| /* Functions that work with fences. */ |
| |
| /* Advance one cycle on FENCE. */ |
| static void |
| advance_one_cycle (fence_t fence) |
| { |
| unsigned i; |
| int cycle; |
| rtx_insn *insn; |
| |
| advance_state (FENCE_STATE (fence)); |
| cycle = ++FENCE_CYCLE (fence); |
| FENCE_ISSUED_INSNS (fence) = 0; |
| FENCE_STARTS_CYCLE_P (fence) = 1; |
| can_issue_more = issue_rate; |
| FENCE_ISSUE_MORE (fence) = can_issue_more; |
| |
| for (i = 0; vec_safe_iterate (FENCE_EXECUTING_INSNS (fence), i, &insn); ) |
| { |
| if (INSN_READY_CYCLE (insn) < cycle) |
| { |
| remove_from_deps (FENCE_DC (fence), insn); |
| FENCE_EXECUTING_INSNS (fence)->unordered_remove (i); |
| continue; |
| } |
| i++; |
| } |
| if (sched_verbose >= 2) |
| { |
| sel_print ("Finished a cycle. Current cycle = %d\n", FENCE_CYCLE (fence)); |
| debug_state (FENCE_STATE (fence)); |
| } |
| } |
| |
| /* Returns true when SUCC in a fallthru bb of INSN, possibly |
| skipping empty basic blocks. */ |
| static bool |
| in_fallthru_bb_p (rtx_insn *insn, rtx succ) |
| { |
| 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)) |
| bb = bb->next_bb; |
| |
| return bb == BLOCK_FOR_INSN (succ); |
| } |
| |
| /* Construct successor fences from OLD_FENCEs and put them in NEW_FENCES. |
| When a successor will continue a ebb, transfer all parameters of a fence |
| to the new fence. ORIG_MAX_SEQNO is the maximal seqno before this round |
| of scheduling helping to distinguish between the old and the new code. */ |
| static void |
| extract_new_fences_from (flist_t old_fences, flist_tail_t new_fences, |
| int orig_max_seqno) |
| { |
| bool was_here_p = false; |
| insn_t insn = NULL; |
| insn_t succ; |
| succ_iterator si; |
| ilist_iterator ii; |
| fence_t fence = FLIST_FENCE (old_fences); |
| basic_block bb; |
| |
| /* Get the only element of FENCE_BNDS (fence). */ |
| FOR_EACH_INSN (insn, ii, FENCE_BNDS (fence)) |
| { |
| gcc_assert (!was_here_p); |
| was_here_p = true; |
| } |
| gcc_assert (was_here_p && insn != NULL_RTX); |
| |
| /* When in the "middle" of the block, just move this fence |
| to the new list. */ |
| bb = BLOCK_FOR_INSN (insn); |
| if (! sel_bb_end_p (insn) |
| || (single_succ_p (bb) |
| && single_pred_p (single_succ (bb)))) |
| { |
| insn_t succ; |
| |
| succ = (sel_bb_end_p (insn) |
| ? sel_bb_head (single_succ (bb)) |
| : NEXT_INSN (insn)); |
| |
| if (INSN_SEQNO (succ) > 0 |
| && INSN_SEQNO (succ) <= orig_max_seqno |
| && INSN_SCHED_TIMES (succ) <= 0) |
| { |
| FENCE_INSN (fence) = succ; |
| move_fence_to_fences (old_fences, new_fences); |
| |
| if (sched_verbose >= 1) |
| sel_print ("Fence %d continues as %d[%d] (state continue)\n", |
| INSN_UID (insn), INSN_UID (succ), BLOCK_NUM (succ)); |
| } |
| return; |
| } |
| |
| /* Otherwise copy fence's structures to (possibly) multiple successors. */ |
| FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS) |
| { |
| int seqno = INSN_SEQNO (succ); |
| |
| if (0 < seqno && seqno <= orig_max_seqno |
| && (pipelining_p || INSN_SCHED_TIMES (succ) <= 0)) |
| { |
| bool b = (in_same_ebb_p (insn, succ) |
| || in_fallthru_bb_p (insn, succ)); |
| |
| if (sched_verbose >= 1) |
| sel_print ("Fence %d continues as %d[%d] (state %s)\n", |
| INSN_UID (insn), INSN_UID (succ), |
| BLOCK_NUM (succ), b ? "continue" : "reset"); |
| |
| if (b) |
| add_dirty_fence_to_fences (new_fences, succ, fence); |
| else |
| { |
| /* Mark block of the SUCC as head of the new ebb. */ |
| bitmap_set_bit (forced_ebb_heads, BLOCK_NUM (succ)); |
| add_clean_fence_to_fences (new_fences, succ, fence); |
| } |
| } |
| } |
| } |
| |
| |
| /* Functions to support substitution. */ |
| |
| /* Returns whether INSN with dependence status DS is eligible for |
| substitution, i.e. it's a copy operation x := y, and RHS that is |
| moved up through this insn should be substituted. */ |
| static bool |
| can_substitute_through_p (insn_t insn, ds_t ds) |
| { |
| /* We can substitute only true dependencies. */ |
| if ((ds & DEP_OUTPUT) |
| || (ds & DEP_ANTI) |
| || ! INSN_RHS (insn) |
| || ! INSN_LHS (insn)) |
| return false; |
| |
| /* Now we just need to make sure the INSN_RHS consists of only one |
| simple REG rtx. */ |
| if (REG_P (INSN_LHS (insn)) |
| && REG_P (INSN_RHS (insn))) |
| return true; |
| return false; |
| } |
| |
| /* Substitute all occurrences of INSN's destination in EXPR' vinsn with INSN's |
| source (if INSN is eligible for substitution). Returns TRUE if |
| substitution was actually performed, FALSE otherwise. Substitution might |
| be not performed because it's either EXPR' vinsn doesn't contain INSN's |
| destination or the resulting insn is invalid for the target machine. |
| When UNDO is true, perform unsubstitution instead (the difference is in |
| the part of rtx on which validate_replace_rtx is called). */ |
| static bool |
| substitute_reg_in_expr (expr_t expr, insn_t insn, bool undo) |
| { |
| rtx *where; |
| bool new_insn_valid; |
| vinsn_t *vi = &EXPR_VINSN (expr); |
| bool has_rhs = VINSN_RHS (*vi) != NULL; |
| rtx old, new_rtx; |
| |
| /* Do not try to replace in SET_DEST. Although we'll choose new |
| register for the RHS, we don't want to change RHS' original reg. |
| If the insn is not SET, we may still be able to substitute something |
| in it, and if we're here (don't have deps), it doesn't write INSN's |
| dest. */ |
| where = (has_rhs |
| ? &VINSN_RHS (*vi) |
| : &PATTERN (VINSN_INSN_RTX (*vi))); |
| old = undo ? INSN_RHS (insn) : INSN_LHS (insn); |
| |
| /* Substitute if INSN has a form of x:=y and LHS(INSN) occurs in *VI. */ |
| if (rtx_ok_for_substitution_p (old, *where)) |
| { |
| rtx_insn *new_insn; |
| rtx *where_replace; |
| |
| /* We should copy these rtxes before substitution. */ |
| new_rtx = copy_rtx (undo ? INSN_LHS (insn) : INSN_RHS (insn)); |
| new_insn = create_copy_of_insn_rtx (VINSN_INSN_RTX (*vi)); |
| |
| /* Where we'll replace. |
| 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)) |
| : &PATTERN (new_insn)); |
| |
| new_insn_valid |
| = validate_replace_rtx_part_nosimplify (old, new_rtx, where_replace, |
| new_insn); |
| |
| /* ??? Actually, constrain_operands result depends upon choice of |
| destination register. E.g. if we allow single register to be an rhs, |
| and if we try to move dx=ax(as rhs) through ax=dx, we'll result |
| in invalid insn dx=dx, so we'll loose this rhs here. |
| Just can't come up with significant testcase for this, so just |
| leaving it for now. */ |
| if (new_insn_valid) |
| { |
| change_vinsn_in_expr (expr, |
| create_vinsn_from_insn_rtx (new_insn, false)); |
| |
| /* Do not allow clobbering the address register of speculative |
| insns. */ |
| if ((EXPR_SPEC_DONE_DS (expr) & SPECULATIVE) |
| && register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)), |
| expr_dest_reg (expr))) |
| EXPR_TARGET_AVAILABLE (expr) = false; |
| |
| return true; |
| } |
| else |
| return false; |
| } |
| else |
| return false; |
| } |
| |
| /* Return the number of places WHAT appears within WHERE. |
| Bail out when we found a reference occupying several hard registers. */ |
| static int |
| count_occurrences_equiv (const_rtx what, const_rtx where) |
| { |
| int count = 0; |
| subrtx_iterator::array_type array; |
| FOR_EACH_SUBRTX (iter, array, where, NONCONST) |
| { |
| const_rtx x = *iter; |
| if (REG_P (x) && REGNO (x) == REGNO (what)) |
| { |
| /* Bail out if mode is different or more than one register is |
| used. */ |
| if (GET_MODE (x) != GET_MODE (what) || REG_NREGS (x) > 1) |
| return 0; |
| count += 1; |
| } |
| else if (GET_CODE (x) == SUBREG |
| && (!REG_P (SUBREG_REG (x)) |
| || REGNO (SUBREG_REG (x)) == REGNO (what))) |
| /* ??? Do not support substituting regs inside subregs. In that case, |
| simplify_subreg will be called by validate_replace_rtx, and |
| unsubstitution will fail later. */ |
| return 0; |
| } |
| return count; |
| } |
| |
| /* Returns TRUE if WHAT is found in WHERE rtx tree. */ |
| static bool |
| rtx_ok_for_substitution_p (rtx what, rtx where) |
| { |
| return (count_occurrences_equiv (what, where) > 0); |
| } |
| |
| |
| /* Functions to support register renaming. */ |
| |
| /* Substitute VI's set source with REGNO. Returns newly created pattern |
| that has REGNO as its source. */ |
| static rtx_insn * |
| create_insn_rtx_with_rhs (vinsn_t vi, rtx rhs_rtx) |
| { |
| rtx lhs_rtx; |
| rtx pattern; |
| rtx_insn *insn_rtx; |
| |
| lhs_rtx = copy_rtx (VINSN_LHS (vi)); |
| |
| pattern = gen_rtx_SET (lhs_rtx, rhs_rtx); |
| insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX); |
| |
| return insn_rtx; |
| } |
| |
| /* Returns whether INSN's src can be replaced with register number |
| NEW_SRC_REG. E.g. the following insn is valid for i386: |
| |
| (insn:HI 2205 6585 2207 727 ../../gcc/libiberty/regex.c:3337 |
| (set (mem/s:QI (plus:SI (plus:SI (reg/f:SI 7 sp) |
| (reg:SI 0 ax [orig:770 c1 ] [770])) |
| (const_int 288 [0x120])) [0 str S1 A8]) |
| (const_int 0 [0x0])) 43 {*movqi_1} (nil) |
| (nil)) |
| |
| But if we change (const_int 0 [0x0]) to (reg:QI 4 si), it will be invalid |
| because of operand constraints: |
| |
| (define_insn "*movqi_1" |
| [(set (match_operand:QI 0 "nonimmediate_operand" "=q,q ,q ,r,r ,?r,m") |
| (match_operand:QI 1 "general_operand" " q,qn,qm,q,rn,qm,qn") |
| )] |
| |
| So do constrain_operands here, before choosing NEW_SRC_REG as best |
| reg for rhs. */ |
| |
| static bool |
| replace_src_with_reg_ok_p (insn_t insn, rtx new_src_reg) |
| { |
| vinsn_t vi = INSN_VINSN (insn); |
| machine_mode mode; |
| rtx dst_loc; |
| bool res; |
| |
| gcc_assert (VINSN_SEPARABLE_P (vi)); |
| |
| get_dest_and_mode (insn, &dst_loc, &mode); |
| gcc_assert (mode == GET_MODE (new_src_reg)); |
| |
| if (REG_P (dst_loc) && REGNO (new_src_reg) == REGNO (dst_loc)) |
| return true; |
| |
| /* See whether SET_SRC can be replaced with this register. */ |
| validate_change (insn, &SET_SRC (PATTERN (insn)), new_src_reg, 1); |
| res = verify_changes (0); |
| cancel_changes (0); |
| |
| return res; |
| } |
| |
| /* Returns whether INSN still be valid after replacing it's DEST with |
| register NEW_REG. */ |
| static bool |
| replace_dest_with_reg_ok_p (insn_t insn, rtx new_reg) |
| { |
| vinsn_t vi = INSN_VINSN (insn); |
| bool res; |
| |
| /* We should deal here only with separable insns. */ |
| gcc_assert (VINSN_SEPARABLE_P (vi)); |
| 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); |
| res = verify_changes (0); |
| cancel_changes (0); |
| |
| return res; |
| } |
| |
| /* Create a pattern with rhs of VI and lhs of LHS_RTX. */ |
| static rtx_insn * |
| create_insn_rtx_with_lhs (vinsn_t vi, rtx lhs_rtx) |
| { |
| rtx rhs_rtx; |
| rtx pattern; |
| rtx_insn *insn_rtx; |
| |
| rhs_rtx = copy_rtx (VINSN_RHS (vi)); |
| |
| pattern = gen_rtx_SET (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. */ |
| static void |
| replace_dest_with_reg_in_expr (expr_t expr, rtx new_reg) |
| { |
| rtx_insn *insn_rtx; |
| vinsn_t vinsn; |
| |
| 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); |
| EXPR_WAS_RENAMED (expr) = 1; |
| EXPR_TARGET_AVAILABLE (expr) = 1; |
| } |
| |
| /* Returns whether VI writes either one of the USED_REGS registers or, |
| if a register is a hard one, one of the UNAVAILABLE_HARD_REGS registers. */ |
| static bool |
| vinsn_writes_one_of_regs_p (vinsn_t vi, regset used_regs, |
| HARD_REG_SET unavailable_hard_regs) |
| { |
| unsigned regno; |
| reg_set_iterator rsi; |
| |
| EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (vi), 0, regno, rsi) |
| { |
| if (REGNO_REG_SET_P (used_regs, regno)) |
| return true; |
| if (HARD_REGISTER_NUM_P (regno) |
| && TEST_HARD_REG_BIT (unavailable_hard_regs, regno)) |
| return true; |
| } |
| |
| EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (vi), 0, regno, rsi) |
| { |
| if (REGNO_REG_SET_P (used_regs, regno)) |
| return true; |
| if (HARD_REGISTER_NUM_P (regno) |
| && TEST_HARD_REG_BIT (unavailable_hard_regs, regno)) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /* Returns register class of the output register in INSN. |
| Returns NO_REGS for call insns because some targets have constraints on |
| destination register of a call insn. |
| |
| Code adopted from regrename.c::build_def_use. */ |
| static enum reg_class |
| get_reg_class (rtx_insn *insn) |
| { |
| int i, n_ops; |
| |
| extract_constrain_insn (insn); |
| preprocess_constraints (insn); |
| n_ops = recog_data.n_operands; |
| |
| const operand_alternative *op_alt = which_op_alt (); |
| if (asm_noperands (PATTERN (insn)) > 0) |
| { |
| for (i = 0; i < n_ops; i++) |
| if (recog_data.operand_type[i] == OP_OUT) |
| { |
| rtx *loc = recog_data.operand_loc[i]; |
| rtx op = *loc; |
| enum reg_class cl = alternative_class (op_alt, i); |
| |
| if (REG_P (op) |
| && REGNO (op) == ORIGINAL_REGNO (op)) |
| continue; |
| |
| return cl; |
| } |
| } |
| else if (!CALL_P (insn)) |
| { |
| for (i = 0; i < n_ops + recog_data.n_dups; i++) |
| { |
| int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; |
| enum reg_class cl = alternative_class (op_alt, opn); |
| |
| if (recog_data.operand_type[opn] == OP_OUT || |
| recog_data.operand_type[opn] == OP_INOUT) |
| return cl; |
| } |
| } |
| |
| /* Insns like |
| (insn (set (reg:CCZ 17 flags) (compare:CCZ ...))) |
| may result in returning NO_REGS, cause flags is written implicitly through |
| CMP insn, which has no OP_OUT | OP_INOUT operands. */ |
| return NO_REGS; |
| } |
| |
| /* Calculate HARD_REGNO_RENAME_OK data for REGNO. */ |
| static void |
| init_hard_regno_rename (int regno) |
| { |
| int cur_reg; |
| |
| SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], regno); |
| |
| for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++) |
| { |
| /* We are not interested in renaming in other regs. */ |
| if (!TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg)) |
| continue; |
| |
| if (HARD_REGNO_RENAME_OK (regno, cur_reg)) |
| SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], cur_reg); |
| } |
| } |
| |
| /* A wrapper around HARD_REGNO_RENAME_OK that will look into the hard regs |
| data first. */ |
| static inline bool |
| sel_hard_regno_rename_ok (int from ATTRIBUTE_UNUSED, int to ATTRIBUTE_UNUSED) |
| { |
| /* Check whether this is all calculated. */ |
| if (TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], from)) |
| return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to); |
| |
| init_hard_regno_rename (from); |
| |
| return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to); |
| } |
| |
| /* Calculate set of registers that are capable of holding MODE. */ |
| static void |
| init_regs_for_mode (machine_mode mode) |
| { |
| int cur_reg; |
| |
| CLEAR_HARD_REG_SET (sel_hrd.regs_for_mode[mode]); |
| CLEAR_HARD_REG_SET (sel_hrd.regs_for_call_clobbered[mode]); |
| |
| for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++) |
| { |
| int nregs; |
| int i; |
| |
| /* See whether it accepts all modes that occur in |
| original insns. */ |
| if (! HARD_REGNO_MODE_OK (cur_reg, mode)) |
| continue; |
| |
| nregs = hard_regno_nregs[cur_reg][mode]; |
| |
| for (i = nregs - 1; i >= 0; --i) |
| if (fixed_regs[cur_reg + i] |
| || global_regs[cur_reg + i] |
| /* Can't use regs which aren't saved by |
| the prologue. */ |
| || !TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg + i) |
| /* Can't use regs with non-null REG_BASE_VALUE, because adjusting |
| it affects aliasing globally and invalidates all AV sets. */ |
| || get_reg_base_value (cur_reg + i) |
| #ifdef LEAF_REGISTERS |
| /* We can't use a non-leaf register if we're in a |
| leaf function. */ |
| || (crtl->is_leaf |
| && !LEAF_REGISTERS[cur_reg + i]) |
| #endif |
| ) |
| break; |
| |
| if (i >= 0) |
| continue; |
| |
| if (HARD_REGNO_CALL_PART_CLOBBERED (cur_reg, mode)) |
| SET_HARD_REG_BIT (sel_hrd.regs_for_call_clobbered[mode], |
| cur_reg); |
| |
| /* If the CUR_REG passed all the checks above, |
| then it's ok. */ |
| SET_HARD_REG_BIT (sel_hrd.regs_for_mode[mode], cur_reg); |
| } |
| |
| sel_hrd.regs_for_mode_ok[mode] = true; |
| } |
| |
| /* Init all register sets gathered in HRD. */ |
| static void |
| init_hard_regs_data (void) |
| { |
| int cur_reg = 0; |
| int cur_mode = 0; |
| |
| CLEAR_HARD_REG_SET (sel_hrd.regs_ever_used); |
| for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++) |
| if (df_regs_ever_live_p (cur_reg) || call_used_regs[cur_reg]) |
| SET_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg); |
| |
| /* Initialize registers that are valid based on mode when this is |
| really needed. */ |
| for (cur_mode = 0; cur_mode < NUM_MACHINE_MODES; cur_mode++) |
| sel_hrd.regs_for_mode_ok[cur_mode] = false; |
| |
| /* Mark that all HARD_REGNO_RENAME_OK is not calculated. */ |
| for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++) |
| CLEAR_HARD_REG_SET (sel_hrd.regs_for_rename[cur_reg]); |
| |
| #ifdef STACK_REGS |
| CLEAR_HARD_REG_SET (sel_hrd.stack_regs); |
| |
| for (cur_reg = FIRST_STACK_REG; cur_reg <= LAST_STACK_REG; cur_reg++) |
| SET_HARD_REG_BIT (sel_hrd.stack_regs, cur_reg); |
| #endif |
| } |
| |
| /* Mark hardware regs in REG_RENAME_P that are not suitable |
| for renaming rhs in INSN due to hardware restrictions (register class, |
| modes compatibility etc). This doesn't affect original insn's dest reg, |
| if it isn't in USED_REGS. DEF is a definition insn of rhs for which the |
| destination register is sought. LHS (DEF->ORIG_INSN) may be REG or MEM. |
| Registers that are in used_regs are always marked in |
| unavailable_hard_regs as well. */ |
| |
| static void |
| mark_unavailable_hard_regs (def_t def, struct reg_rename *reg_rename_p, |
| regset used_regs ATTRIBUTE_UNUSED) |
| { |
| machine_mode mode; |
| enum reg_class cl = NO_REGS; |
| rtx orig_dest; |
| 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)); |
| |
| /* We have decided not to rename 'mem = something;' insns, as 'something' |
| is usually a register. */ |
| if (!REG_P (orig_dest)) |
| return; |
| |
| regno = REGNO (orig_dest); |
| |
| /* If before reload, don't try to work with pseudos. */ |
| if (!reload_completed && !HARD_REGISTER_NUM_P (regno)) |
| return; |
| |
| if (reload_completed) |
| cl = get_reg_class (def->orig_insn); |
| |
| /* Stop if the original register is one of the fixed_regs, global_regs or |
| frame pointer, or we could not discover its class. */ |
| if (fixed_regs[regno] |
| || global_regs[regno] |
| || (!HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed |
| && regno == HARD_FRAME_POINTER_REGNUM) |
| || (HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed |
| && regno == FRAME_POINTER_REGNUM) |
| || (reload_completed && cl == NO_REGS)) |
| { |
| SET_HARD_REG_SET (reg_rename_p->unavailable_hard_regs); |
| |
| /* Give a chance for original register, if it isn't in used_regs. */ |
| if (!def->crosses_call) |
| CLEAR_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno); |
| |
| return; |
| } |
| |
| /* If something allocated on stack in this function, mark frame pointer |
| register unavailable, considering also modes. |
| FIXME: it is enough to do this once per all original defs. */ |
| if (frame_pointer_needed) |
| { |
| add_to_hard_reg_set (®_rename_p->unavailable_hard_regs, |
| Pmode, FRAME_POINTER_REGNUM); |
| |
| if (!HARD_FRAME_POINTER_IS_FRAME_POINTER) |
| add_to_hard_reg_set (®_rename_p->unavailable_hard_regs, |
| Pmode, HARD_FRAME_POINTER_REGNUM); |
| } |
| |
| #ifdef STACK_REGS |
| /* For the stack registers the presence of FIRST_STACK_REG in USED_REGS |
| is equivalent to as if all stack regs were in this set. |
| I.e. no stack register can be renamed, and even if it's an original |
| register here we make sure it won't be lifted over it's previous def |
| (it's previous def will appear as if it's a FIRST_STACK_REG def. |
| The HARD_REGNO_RENAME_OK covers other cases in condition below. */ |
| if (IN_RANGE (REGNO (orig_dest), FIRST_STACK_REG, LAST_STACK_REG) |
| && REGNO_REG_SET_P (used_regs, FIRST_STACK_REG)) |
| IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs, |
| sel_hrd.stack_regs); |
| #endif |
| |
| /* If there's a call on this path, make regs from call_used_reg_set |
| unavailable. */ |
| if (def->crosses_call) |
| IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs, |
| call_used_reg_set); |
| |
| /* Stop here before reload: we need FRAME_REGS, STACK_REGS, and crosses_call, |
| but not register classes. */ |
| if (!reload_completed) |
| return; |
| |
| /* Leave regs as 'available' only from the current |
| register class. */ |
| COPY_HARD_REG_SET (reg_rename_p->available_for_renaming, |
| reg_class_contents[cl]); |
| |
| mode = GET_MODE (orig_dest); |
| |
| /* Leave only registers available for this mode. */ |
| if (!sel_hrd.regs_for_mode_ok[mode]) |
| init_regs_for_mode (mode); |
| AND_HARD_REG_SET (reg_rename_p->available_for_renaming, |
| sel_hrd.regs_for_mode[mode]); |
| |
| /* Exclude registers that are partially call clobbered. */ |
| if (def->crosses_call |
| && ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)) |
| AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming, |
| sel_hrd.regs_for_call_clobbered[mode]); |
| |
| /* Leave only those that are ok to rename. */ |
| EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming, |
| 0, cur_reg, hrsi) |
| { |
| int nregs; |
| int i; |
| |
| nregs = hard_regno_nregs[cur_reg][mode]; |
| gcc_assert (nregs > 0); |
| |
| for (i = nregs - 1; i >= 0; --i) |
| if (! sel_hard_regno_rename_ok (regno + i, cur_reg + i)) |
| break; |
| |
| if (i >= 0) |
| CLEAR_HARD_REG_BIT (reg_rename_p->available_for_renaming, |
| cur_reg); |
| } |
| |
| AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming, |
| reg_rename_p->unavailable_hard_regs); |
| |
| /* Regno is always ok from the renaming part of view, but it really |
| could be in *unavailable_hard_regs already, so set it here instead |
| of there. */ |
| SET_HARD_REG_BIT (reg_rename_p->available_for_renaming, regno); |
| } |
| |
| /* reg_rename_tick[REG1] > reg_rename_tick[REG2] if REG1 was chosen as the |
| best register more recently than REG2. */ |
| static int reg_rename_tick[FIRST_PSEUDO_REGISTER]; |
| |
| /* Indicates the number of times renaming happened before the current one. */ |
| static int reg_rename_this_tick; |
| |
| /* Choose the register among free, that is suitable for storing |
| the rhs value. |
| |
| ORIGINAL_INSNS is the list of insns where the operation (rhs) |
| originally appears. There could be multiple original operations |
| for single rhs since we moving it up and merging along different |
| paths. |
| |
| Some code is adapted from regrename.c (regrename_optimize). |
| If original register is available, function returns it. |
| Otherwise it performs the checks, so the new register should |
| comply with the following: |
| - it should not violate any live ranges (such registers are in |
| REG_RENAME_P->available_for_renaming set); |
| - it should not be in the HARD_REGS_USED regset; |
| - it should be in the class compatible with original uses; |
| - it should not be clobbered through reference with different mode; |
| - if we're in the leaf function, then the new register should |
| not be in the LEAF_REGISTERS; |
| - etc. |
| |
| If several registers meet the conditions, the register with smallest |
| tick is returned to achieve more even register allocation. |
| |
| If original register seems to be ok, we set *IS_ORIG_REG_P_PTR to true. |
| |
| If no register satisfies the above conditions, NULL_RTX is returned. */ |
| static rtx |
| choose_best_reg_1 (HARD_REG_SET hard_regs_used, |
| struct reg_rename *reg_rename_p, |
| def_list_t original_insns, bool *is_orig_reg_p_ptr) |
| { |
| int best_new_reg; |
| unsigned cur_reg; |
| machine_mode mode = VOIDmode; |
| unsigned regno, i, n; |
| hard_reg_set_iterator hrsi; |
| def_list_iterator di; |
| def_t def; |
| |
| /* If original register is available, return it. */ |
| *is_orig_reg_p_ptr = true; |
| |
| FOR_EACH_DEF (def, di, original_insns) |
| { |
| rtx orig_dest = SET_DEST (PATTERN (def->orig_insn)); |
| |
| gcc_assert (REG_P (orig_dest)); |
| |
| /* Check that all original operations have the same mode. |
| This is done for the next loop; if we'd return from this |
| loop, we'd check only part of them, but in this case |
| it doesn't matter. */ |
| if (mode == VOIDmode) |
| mode = GET_MODE (orig_dest); |
| gcc_assert (mode == GET_MODE (orig_dest)); |
| |
| regno = REGNO (orig_dest); |
| for (i = 0, n = hard_regno_nregs[regno][mode]; i < n; i++) |
| if (TEST_HARD_REG_BIT (hard_regs_used, regno + i)) |
| break; |
| |
| /* All hard registers are available. */ |
| if (i == n) |
| { |
| gcc_assert (mode != VOIDmode); |
| |
| /* Hard registers should not be shared. */ |
| return gen_rtx_REG (mode, regno); |
| } |
| } |
| |
| *is_orig_reg_p_ptr = false; |
| best_new_reg = -1; |
| |
| /* Among all available regs choose the register that was |
| allocated earliest. */ |
| EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming, |
| 0, cur_reg, hrsi) |
| if (! TEST_HARD_REG_BIT (hard_regs_used, cur_reg)) |
| { |
| /* Check that all hard regs for mode are available. */ |
| for (i = 1, n = hard_regno_nregs[cur_reg][mode]; i < n; i++) |
| if (TEST_HARD_REG_BIT (hard_regs_used, cur_reg + i) |
| || !TEST_HARD_REG_BIT (reg_rename_p->available_for_renaming, |
| cur_reg + i)) |
| break; |
| |
| if (i < n) |
| continue; |
| |
| /* All hard registers are available. */ |
| if (best_new_reg < 0 |
| || reg_rename_tick[cur_reg] < reg_rename_tick[best_new_reg]) |
| { |
| best_new_reg = cur_reg; |
| |
| /* Return immediately when we know there's no better reg. */ |
| if (! reg_rename_tick[best_new_reg]) |
| break; |
| } |
| } |
| |
| if (best_new_reg >= 0) |
| { |
| /* Use the check from the above loop. */ |
| gcc_assert (mode != VOIDmode); |
| return gen_rtx_REG (mode, best_new_reg); |
| } |
| |
| return NULL_RTX; |
| } |
| |
| /* A wrapper around choose_best_reg_1 () to verify that we make correct |
| assumptions about available registers in the function. */ |
| static rtx |
| choose_best_reg (HARD_REG_SET hard_regs_used, struct reg_rename *reg_rename_p, |
| def_list_t original_insns, bool *is_orig_reg_p_ptr) |
| { |
| rtx best_reg = choose_best_reg_1 (hard_regs_used, reg_rename_p, |
| original_insns, is_orig_reg_p_ptr); |
| |
| /* FIXME loop over hard_regno_nregs here. */ |
| gcc_assert (best_reg == NULL_RTX |
| || TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, REGNO (best_reg))); |
| |
| return best_reg; |
| } |
| |
| /* Choose the pseudo register for storing rhs value. As this is supposed |
| to work before reload, we return either the original register or make |
| the new one. The parameters are the same that in choose_nest_reg_1 |
| functions, except that USED_REGS may contain pseudos. |
| If we work with hard regs, check also REG_RENAME_P->UNAVAILABLE_HARD_REGS. |
| |
| TODO: take into account register pressure while doing this. Up to this |
| moment, this function would never return NULL for pseudos, but we should |
| not rely on this. */ |
| static rtx |
| choose_best_pseudo_reg (regset used_regs, |
| struct reg_rename *reg_rename_p, |
| def_list_t original_insns, bool *is_orig_reg_p_ptr) |
| { |
| def_list_iterator i; |
| def_t def; |
| machine_mode mode = VOIDmode; |
| bool bad_hard_regs = false; |
| |
| /* We should not use this after reload. */ |
| gcc_assert (!reload_completed); |
| |
| /* If original register is available, return it. */ |
| *is_orig_reg_p_ptr = true; |
| |
| FOR_EACH_DEF (def, i, original_insns) |
| { |
| rtx dest = SET_DEST (PATTERN (def->orig_insn)); |
| int orig_regno; |
| |
| gcc_assert (REG_P (dest)); |
| |
| /* Check that all original operations have the same mode. */ |
| if (mode == VOIDmode) |
| mode = GET_MODE (dest); |
| else |
| gcc_assert (mode == GET_MODE (dest)); |
| orig_regno = REGNO (dest); |
| |
| /* Check that nothing in used_regs intersects with orig_regno. When |
| we have a hard reg here, still loop over hard_regno_nregs. */ |
| if (HARD_REGISTER_NUM_P (orig_regno)) |
| { |
| int j, n; |
| for (j = 0, n = hard_regno_nregs[orig_regno][mode]; j < n; j++) |
| if (REGNO_REG_SET_P (used_regs, orig_regno + j)) |
| break; |
| if (j < n) |
| continue; |
| } |
| else |
| { |
| if (REGNO_REG_SET_P (used_regs, orig_regno)) |
| continue; |
| } |
| if (HARD_REGISTER_NUM_P (orig_regno)) |
| { |
| gcc_assert (df_regs_ever_live_p (orig_regno)); |
| |
| /* For hard registers, we have to check hardware imposed |
| limitations (frame/stack registers, calls crossed). */ |
| if (!TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, |
| orig_regno)) |
| { |
| /* Don't let register cross a call if it doesn't already |
| cross one. This condition is written in accordance with |
| that in sched-deps.c sched_analyze_reg(). */ |
| if (!reg_rename_p->crosses_call |
| || REG_N_CALLS_CROSSED (orig_regno) > 0) |
| return gen_rtx_REG (mode, orig_regno); |
| } |
| |
| bad_hard_regs = true; |
| } |
| else |
| return dest; |
| } |
| |
| *is_orig_reg_p_ptr = false; |
| |
| /* We had some original hard registers that couldn't be used. |
| Those were likely special. Don't try to create a pseudo. */ |
| if (bad_hard_regs) |
| return NULL_RTX; |
| |
| /* We haven't found a register from original operations. Get a new one. |
| FIXME: control register pressure somehow. */ |
| { |
| rtx new_reg = gen_reg_rtx (mode); |
| |
| gcc_assert (mode != VOIDmode); |
| |
| max_regno = max_reg_num (); |
| maybe_extend_reg_info_p (); |
| REG_N_CALLS_CROSSED (REGNO (new_reg)) = reg_rename_p->crosses_call ? 1 : 0; |
| |
| return new_reg; |
| } |
| } |
| |
| /* True when target of EXPR is available due to EXPR_TARGET_AVAILABLE, |
| USED_REGS and REG_RENAME_P->UNAVAILABLE_HARD_REGS. */ |
| static void |
| verify_target_availability (expr_t expr, regset used_regs, |
| struct reg_rename *reg_rename_p) |
| { |
| unsigned n, i, regno; |
| machine_mode mode; |
| bool target_available, live_available, hard_available; |
| |
| if (!REG_P (EXPR_LHS (expr)) || EXPR_TARGET_AVAILABLE (expr) < 0) |
| return; |
| |
| regno = expr_dest_regno (expr); |
| mode = GET_MODE (EXPR_LHS (expr)); |
| target_available = EXPR_TARGET_AVAILABLE (expr) == 1; |
| n = HARD_REGISTER_NUM_P (regno) ? hard_regno_nregs[regno][mode] : 1; |
| |
| live_available = hard_available = true; |
| for (i = 0; i < n; i++) |
| { |
| if (bitmap_bit_p (used_regs, regno + i)) |
| live_available = false; |
| if (TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno + i)) |
| hard_available = false; |
| } |
| |
| /* When target is not available, it may be due to hard register |
| restrictions, e.g. crosses calls, so we check hard_available too. */ |
| if (target_available) |
| gcc_assert (live_available); |
| else |
| /* Check only if we haven't scheduled something on the previous fence, |
| cause due to MAX_SOFTWARE_LOOKAHEAD_WINDOW_SIZE issues |
| and having more than one fence, we may end having targ_un in a block |
| in which successors target register is actually available. |
| |
| The last condition handles the case when a dependence from a call insn |
| was created in sched-deps.c for insns with destination registers that |
| never crossed a call before, but do cross one after our code motion. |
| |
| FIXME: in the latter case, we just uselessly called find_used_regs, |
| because we can't move this expression with any other register |
| as well. */ |
| gcc_assert (scheduled_something_on_previous_fence || !live_available |
| || !hard_available |
| || (!reload_completed && reg_rename_p->crosses_call |
| && REG_N_CALLS_CROSSED (regno) == 0)); |
| } |
| |
| /* Collect unavailable registers due to liveness for EXPR from BNDS |
| into USED_REGS. Save additional information about available |
| registers and unavailable due to hardware restriction registers |
| into REG_RENAME_P structure. Save original insns into ORIGINAL_INSNS |
| list. */ |
| static void |
| collect_unavailable_regs_from_bnds (expr_t expr, blist_t bnds, regset used_regs, |
| struct reg_rename *reg_rename_p, |
| def_list_t *original_insns) |
| { |
| for (; bnds; bnds = BLIST_NEXT (bnds)) |
| { |
| bool res; |
| av_set_t orig_ops = NULL; |
| bnd_t bnd = BLIST_BND (bnds); |
| |
| /* If the chosen best expr doesn't belong to current boundary, |
| skip it. */ |
| if (!av_set_is_in_p (BND_AV1 (bnd), EXPR_VINSN (expr))) |
| continue; |
| |
| /* Put in ORIG_OPS all exprs from this boundary that became |
| RES on top. */ |
| orig_ops = find_sequential_best_exprs (bnd, expr, false); |
| |
| /* Compute used regs and OR it into the USED_REGS. */ |
| res = find_used_regs (BND_TO (bnd), orig_ops, used_regs, |
| reg_rename_p, original_insns); |
| |
| /* FIXME: the assert is true until we'd have several boundaries. */ |
| gcc_assert (res); |
| av_set_clear (&orig_ops); |
| } |
| } |
| |
| /* Return TRUE if it is possible to replace LHSes of ORIG_INSNS with BEST_REG. |
| If BEST_REG is valid, replace LHS of EXPR with it. */ |
| static bool |
| try_replace_dest_reg (ilist_t orig_insns, rtx best_reg, expr_t expr) |
| { |
| /* Try whether we'll be able to generate the insn |
| 'dest := best_reg' at the place of the original operation. */ |
| for (; orig_insns; orig_insns = ILIST_NEXT (orig_insns)) |
| { |
| insn_t orig_insn = DEF_LIST_DEF (orig_insns)->orig_insn; |
| |
| gcc_assert (EXPR_SEPARABLE_P (INSN_EXPR (orig_insn))); |
| |
| if (REGNO (best_reg) != REGNO (INSN_LHS (orig_insn)) |
| && (! replace_src_with_reg_ok_p (orig_insn, best_reg) |
| || ! replace_dest_with_reg_ok_p (orig_insn, best_reg))) |
| return false; |
| } |
| |
| /* Make sure that EXPR has the right destination |
| register. */ |
| if (expr_dest_regno (expr) != REGNO (best_reg)) |
| replace_dest_with_reg_in_expr (expr, best_reg); |
| else |
| EXPR_TARGET_AVAILABLE (expr) = 1; |
| |
| return true; |
| } |
| |
| /* Select and assign best register to EXPR searching from BNDS. |
| Set *IS_ORIG_REG_P to TRUE if original register was selected. |
| Return FALSE if no register can be chosen, which could happen when: |
| * EXPR_SEPARABLE_P is true but we were unable to find suitable register; |
| * EXPR_SEPARABLE_P is false but the insn sets/clobbers one of the registers |
| that are used on the moving path. */ |
| static bool |
| find_best_reg_for_expr (expr_t expr, blist_t bnds, bool *is_orig_reg_p) |
| { |
| static struct reg_rename reg_rename_data; |
| |
| regset used_regs; |
| def_list_t original_insns = NULL; |
| bool reg_ok; |
| |
| *is_orig_reg_p = false; |
| |
| /* Don't bother to do anything if this insn doesn't set any registers. */ |
| if (bitmap_empty_p (VINSN_REG_SETS (EXPR_VINSN (expr))) |
| && bitmap_empty_p (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)))) |
| return true; |
| |
| used_regs = get_clear_regset_from_pool (); |
| CLEAR_HARD_REG_SET (reg_rename_data.unavailable_hard_regs); |
| |
| collect_unavailable_regs_from_bnds (expr, bnds, used_regs, ®_rename_data, |
| &original_insns); |
| |
| /* If after reload, make sure we're working with hard regs here. */ |
| if (flag_checking && reload_completed) |
| { |
| reg_set_iterator rsi; |
| unsigned i; |
| |
| EXECUTE_IF_SET_IN_REG_SET (used_regs, FIRST_PSEUDO_REGISTER, i, rsi) |
| gcc_unreachable (); |
| } |
| |
| if (EXPR_SEPARABLE_P (expr)) |
| { |
| rtx best_reg = NULL_RTX; |
| /* Check that we have computed availability of a target register |
| correctly. */ |
| verify_target_availability (expr, used_regs, ®_rename_data); |
| |
| /* Turn everything in hard regs after reload. */ |
| if (reload_completed) |
| { |
| HARD_REG_SET hard_regs_used; |
| REG_SET_TO_HARD_REG_SET (hard_regs_used, used_regs); |
| |
| /* Join hard registers unavailable due to register class |
| restrictions and live range intersection. */ |
| IOR_HARD_REG_SET (hard_regs_used, |
| reg_rename_data.unavailable_hard_regs); |
| |
| best_reg = choose_best_reg (hard_regs_used, ®_rename_data, |
| original_insns, is_orig_reg_p); |
| } |
| else |
| best_reg = choose_best_pseudo_reg (used_regs, ®_rename_data, |
| original_insns, is_orig_reg_p); |
| |
| if (!best_reg) |
| reg_ok = false; |
| else if (*is_orig_reg_p) |
| { |
| /* In case of unification BEST_REG may be different from EXPR's LHS |
| when EXPR's LHS is unavailable, and there is another LHS among |
| ORIGINAL_INSNS. */ |
| reg_ok = try_replace_dest_reg (original_insns, best_reg, expr); |
| } |
| else |
| { |
| /* Forbid renaming of low-cost insns. */ |
| if (sel_vinsn_cost (EXPR_VINSN (expr)) < 2) |
| reg_ok = false; |
| else |
| reg_ok = try_replace_dest_reg (original_insns, best_reg, expr); |
| } |
| } |
| else |
| { |
| /* If !EXPR_SCHEDULE_AS_RHS (EXPR), just make sure INSN doesn't set |
| any of the HARD_REGS_USED set. */ |
| if (vinsn_writes_one_of_regs_p (EXPR_VINSN (expr), used_regs, |
| reg_rename_data.unavailable_hard_regs)) |
| { |
| reg_ok = false; |
| gcc_assert (EXPR_TARGET_AVAILABLE (expr) <= 0); |
| } |
| else |
| { |
| reg_ok = true; |
| gcc_assert (EXPR_TARGET_AVAILABLE (expr) != 0); |
| } |
| } |
| |
| ilist_clear (&original_insns); |
| return_regset_to_pool (used_regs); |
| |
| return reg_ok; |
| } |
| |
| |
| /* Return true if dependence described by DS can be overcomed. */ |
| static bool |
| can_speculate_dep_p (ds_t ds) |
| { |
| if (spec_info == NULL) |
| return false; |
| |
| /* Leave only speculative data. */ |
| ds &= SPECULATIVE; |
| |
| if (ds == 0) |
| return false; |
| |
| { |
| /* FIXME: make sched-deps.c produce only those non-hard dependencies, |
| that we can overcome. */ |
| ds_t spec_mask = spec_info->mask; |
| |
| if ((ds & spec_mask) != ds) |
| return false; |
| } |
| |
| if (ds_weak (ds) < spec_info->data_weakness_cutoff) |
| return false; |
| |
| return true; |
| } |
| |
| /* Get a speculation check instruction. |
| C_EXPR is a speculative expression, |
| CHECK_DS describes speculations that should be checked, |
| ORIG_INSN is the original non-speculative insn in the stream. */ |
| static insn_t |
| create_speculation_check (expr_t c_expr, ds_t check_ds, insn_t orig_insn) |
| { |
| rtx check_pattern; |
| rtx_insn *insn_rtx; |
| insn_t insn; |
| basic_block recovery_block; |
| rtx_insn *label; |
| |
| /* Create a recovery block if target is going to emit branchy check, or if |
| ORIG_INSN was speculative already. */ |
| if (targetm.sched.needs_block_p (check_ds) |
| || EXPR_SPEC_DONE_DS (INSN_EXPR (orig_insn)) != 0) |
| { |
| recovery_block = sel_create_recovery_block (orig_insn); |
| label = BB_HEAD (recovery_block); |
| } |
| else |
| { |
| recovery_block = NULL; |
| label = NULL; |
| } |
| |
| /* Get pattern of the check. */ |
| check_pattern = targetm.sched.gen_spec_check (EXPR_INSN_RTX (c_expr), label, |
| check_ds); |
| |
| gcc_assert (check_pattern != NULL); |
| |
| /* Emit check. */ |
| insn_rtx = create_insn_rtx_from_pattern (check_pattern, label); |
| |
| insn = sel_gen_insn_from_rtx_after (insn_rtx, INSN_EXPR (orig_insn), |
| INSN_SEQNO (orig_insn), orig_insn); |
| |
| /* Make check to be non-speculative. */ |
| EXPR_SPEC_DONE_DS (INSN_EXPR (insn)) = 0; |
| INSN_SPEC_CHECKED_DS (insn) = check_ds; |
| |
| /* Decrease priority of check by difference of load/check instruction |
| latencies. */ |
| EXPR_PRIORITY (INSN_EXPR (insn)) -= (sel_vinsn_cost (INSN_VINSN (orig_insn)) |
| - sel_vinsn_cost (INSN_VINSN (insn))); |
| |
| /* Emit copy of original insn (though with replaced target register, |
| if needed) to the recovery block. */ |
| if (recovery_block != NULL) |
| { |
| rtx twin_rtx; |
| |
| twin_rtx = copy_rtx (PATTERN (EXPR_INSN_RTX (c_expr))); |
| twin_rtx = create_insn_rtx_from_pattern (twin_rtx, NULL_RTX); |
| sel_gen_recovery_insn_from_rtx_after (twin_rtx, |
| INSN_EXPR (orig_insn), |
| INSN_SEQNO (insn), |
| bb_note (recovery_block)); |
| } |
| |
| /* If we've generated a data speculation check, make sure |
| that all the bookkeeping instruction we'll create during |
| this move_op () will allocate an ALAT entry so that the |
| check won't fail. |
| In case of control speculation we must convert C_EXPR to control |
| speculative mode, because failing to do so will bring us an exception |
| thrown by the non-control-speculative load. */ |
| check_ds = ds_get_max_dep_weak (check_ds); |
| speculate_expr (c_expr, check_ds); |
| |
| return insn; |
| } |
| |
| /* True when INSN is a "regN = regN" copy. */ |
| static bool |
| identical_copy_p (rtx_insn *insn) |
| { |
| rtx lhs, rhs, pat; |
| |
| pat = PATTERN (insn); |
| |
| if (GET_CODE (pat) != SET) |
| return false; |
| |
| lhs = SET_DEST (pat); |
| if (!REG_P (lhs)) |
| return false; |
| |
| rhs = SET_SRC (pat); |
| if (!REG_P (rhs)) |
| return false; |
| |
| return REGNO (lhs) == REGNO (rhs); |
| } |
| |
| /* Undo all transformations on *AV_PTR that were done when |
| moving through INSN. */ |
| static void |
| undo_transformations (av_set_t *av_ptr, rtx_insn *insn) |
| { |
| av_set_iterator av_iter; |
| expr_t expr; |
| av_set_t new_set = NULL; |
| |
| /* First, kill any EXPR that uses registers set by an insn. This is |
| required for correctness. */ |
| FOR_EACH_EXPR_1 (expr, av_iter, av_ptr) |
| if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (expr)) |
| && bitmap_intersect_p (INSN_REG_SETS (insn), |
| VINSN_REG_USES (EXPR_VINSN (expr))) |
| /* When an insn looks like 'r1 = r1', we could substitute through |
| it, but the above condition will still hold. This happened with |
| gcc.c-torture/execute/961125-1.c. */ |
| && !identical_copy_p (insn)) |
| { |
| if (sched_verbose >= 6) |
| sel_print ("Expr %d removed due to use/set conflict\n", |
| INSN_UID (EXPR_INSN_RTX (expr))); |
| av_set_iter_remove (&av_iter); |
| } |
| |
| /* Undo transformations looking at the history vector. */ |
| FOR_EACH_EXPR (expr, av_iter, *av_ptr) |
| { |
| int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (expr), |
| insn, EXPR_VINSN (expr), true); |
| |
| if (index >= 0) |
| { |
| expr_history_def *phist; |
| |
| phist = &EXPR_HISTORY_OF_CHANGES (expr)[index]; |
| |
| switch (phist->type) |
| { |
| case TRANS_SPECULATION: |
| { |
| ds_t old_ds, new_ds; |
| |
| /* Compute the difference between old and new speculative |
| statuses: that's what we need to check. |
| Earlier we used to assert that the status will really |
| change. This no longer works because only the probability |
| bits in the status may have changed during compute_av_set, |
| and in the case of merging different probabilities of the |
| same speculative status along different paths we do not |
| record this in the history vector. */ |
| old_ds = phist->spec_ds; |
| new_ds = EXPR_SPEC_DONE_DS (expr); |
| |
| old_ds &= SPECULATIVE; |
| new_ds &= SPECULATIVE; |
| new_ds &= ~old_ds; |
| |
| EXPR_SPEC_TO_CHECK_DS (expr) |= new_ds; |
| break; |
| } |
| case TRANS_SUBSTITUTION: |
| { |
| expr_def _tmp_expr, *tmp_expr = &_tmp_expr; |
| vinsn_t new_vi; |
| bool add = true; |
| |
| new_vi = phist->old_expr_vinsn; |
| |
| gcc_assert (VINSN_SEPARABLE_P (new_vi) |
| == EXPR_SEPARABLE_P (expr)); |
| copy_expr (tmp_expr, expr); |
| |
| if (vinsn_equal_p (phist->new_expr_vinsn, |
| EXPR_VINSN (tmp_expr))) |
| change_vinsn_in_expr (tmp_expr, new_vi); |
| else |
| /* This happens when we're unsubstituting on a bookkeeping |
| copy, which was in turn substituted. The history is wrong |
| in this case. Do it the hard way. */ |
| add = substitute_reg_in_expr (tmp_expr, insn, true); |
| if (add) |
| av_set_add (&new_set, tmp_expr); |
| clear_expr (tmp_expr); |
| break; |
| } |
| default: |
| gcc_unreachable (); |
| } |
| } |
| |
| } |
| |
| av_set_union_and_clear (av_ptr, &new_set, NULL); |
| } |
| |
| |
| /* Moveup_* helpers for code motion and computing av sets. */ |
| |
| /* Propagates EXPR inside an insn group through THROUGH_INSN. |
| The difference from the below function is that only substitution is |
| performed. */ |
| static enum MOVEUP_EXPR_CODE |
| moveup_expr_inside_insn_group (expr_t expr, insn_t through_insn) |
| { |
| vinsn_t vi = EXPR_VINSN (expr); |
| ds_t *has_dep_p; |
| ds_t full_ds; |
| |
| /* Do this only inside insn group. */ |
| gcc_assert (INSN_SCHED_CYCLE (through_insn) > 0); |
| |
| full_ds = has_dependence_p (expr, through_insn, &has_dep_p); |
| if (full_ds == 0) |
| return MOVEUP_EXPR_SAME; |
| |
| /* Substitution is the possible choice in this case. */ |
| if (has_dep_p[DEPS_IN_RHS]) |
| { |
| /* Can't substitute UNIQUE VINSNs. */ |
| gcc_assert (!VINSN_UNIQUE_P (vi)); |
| |
| if (can_substitute_through_p (through_insn, |
| has_dep_p[DEPS_IN_RHS]) |
| && substitute_reg_in_expr (expr, through_insn, false)) |
| { |
| EXPR_WAS_SUBSTITUTED (expr) = true; |
| return MOVEUP_EXPR_CHANGED; |
| } |
| |
| /* Don't care about this, as even true dependencies may be allowed |
| in an insn group. */ |
| return MOVEUP_EXPR_SAME; |
| } |
| |
| /* This can catch output dependencies in COND_EXECs. */ |
| if (has_dep_p[DEPS_IN_INSN]) |
| return MOVEUP_EXPR_NULL; |
| |
| /* This is either an output or an anti dependence, which usually have |
| a zero latency. Allow this here, if we'd be wrong, tick_check_p |
| will fix this. */ |
| gcc_assert (has_dep_p[DEPS_IN_LHS]); |
| return MOVEUP_EXPR_AS_RHS; |
| } |
| |
| /* True when a trapping EXPR cannot be moved through THROUGH_INSN. */ |
| #define CANT_MOVE_TRAPPING(expr, through_insn) \ |
| (VINSN_MAY_TRAP_P (EXPR_VINSN (expr)) \ |
| && !sel_insn_has_single_succ_p ((through_insn), SUCCS_ALL) \ |
| && !sel_insn_is_speculation_check (through_insn)) |
| |
| /* True when a conflict on a target register was found during moveup_expr. */ |
| static bool was_target_conflict = false; |
| |
| /* Return true when moving a debug INSN across THROUGH_INSN will |
| create a bookkeeping block. We don't want to create such blocks, |
| for they would cause codegen differences between compilations with |
| and without debug info. */ |
| |
| static bool |
| moving_insn_creates_bookkeeping_block_p (insn_t insn, |
| insn_t through_insn) |
| { |
| basic_block bbi, bbt; |
| edge e1, e2; |
| edge_iterator ei1, ei2; |
| |
| if (!bookkeeping_can_be_created_if_moved_through_p (through_insn)) |
| { |
| if (sched_verbose >= 9) |
| sel_print ("no bookkeeping required: "); |
| return FALSE; |
| } |
| |
| bbi = BLOCK_FOR_INSN (insn); |
| |
| if (EDGE_COUNT (bbi->preds) == 1) |
| { |
| if (sched_verbose >= 9) |
| sel_print ("only one pred edge: "); |
| return TRUE; |
| } |
| |
| bbt = BLOCK_FOR_INSN (through_insn); |
| |
| FOR_EACH_EDGE (e1, ei1, bbt->succs) |
| { |
| FOR_EACH_EDGE (e2, ei2, bbi->preds) |
| { |
| if (find_block_for_bookkeeping (e1, e2, TRUE)) |
| { |
| if (sched_verbose >= 9) |
| sel_print ("found existing block: "); |
| return FALSE; |
| } |
| } |
| } |
| |
| if (sched_verbose >= 9) |
| sel_print ("would create bookkeeping block: "); |
| |
| return TRUE; |
| } |
| |
| /* Return true when the conflict with newly created implicit clobbers |
| between EXPR and THROUGH_INSN is found because of renaming. */ |
| static bool |
| implicit_clobber_conflict_p (insn_t through_insn, expr_t expr) |
| { |
| HARD_REG_SET temp; |
| rtx_insn *insn; |
| rtx reg, rhs, pat; |
| hard_reg_set_iterator hrsi; |
| unsigned regno; |
| bool valid; |
| |
| /* Make a new pseudo register. */ |
| reg = gen_reg_rtx (GET_MODE (EXPR_LHS (expr))); |
| max_regno = max_reg_num (); |
| maybe_extend_reg_info_p (); |
| |
| /* Validate a change and bail out early. */ |
| insn = EXPR_INSN_RTX (expr); |
| validate_change (insn, &SET_DEST (PATTERN (insn)), reg, true); |
| valid = verify_changes (0); |
| cancel_changes (0); |
| if (!valid) |
| { |
| if (sched_verbose >= 6) |
| sel_print ("implicit clobbers failed validation, "); |
| return true; |
| } |
| |
| /* Make a new insn with it. */ |
| rhs = copy_rtx (VINSN_RHS (EXPR_VINSN (expr))); |
| pat = gen_rtx_SET (reg, rhs); |
| start_sequence (); |
| insn = emit_insn (pat); |
| end_sequence (); |
| |
| /* Calculate implicit clobbers. */ |
| extract_insn (insn); |
| preprocess_constraints (insn); |
| alternative_mask prefrred = get_preferred_alternatives (insn); |
| ira_implicitly_set_insn_hard_regs (&temp, prefrred); |
| AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs); |
| |
| /* If any implicit clobber registers intersect with regular ones in |
| through_insn, we have a dependency and thus bail out. */ |
| EXECUTE_IF_SET_IN_HARD_REG_SET (temp, 0, regno, hrsi) |
| { |
| vinsn_t vi = INSN_VINSN (through_insn); |
| if (bitmap_bit_p (VINSN_REG_SETS (vi), regno) |
| || bitmap_bit_p (VINSN_REG_CLOBBERS (vi), regno) |
| || bitmap_bit_p (VINSN_REG_USES (vi), regno)) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /* Modifies EXPR so it can be moved through the THROUGH_INSN, |
| 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_EXPR_CODE |
| moveup_expr (expr_t expr, insn_t through_insn, bool inside_insn_group, |
| enum local_trans_type *ptrans_type) |
| { |
| vinsn_t vi = EXPR_VINSN (expr); |
| insn_t insn = VINSN_INSN_RTX (vi); |
| bool was_changed = false; |
| bool as_rhs = false; |
| ds_t *has_dep_p; |
| ds_t full_ds; |
| |
| /* ??? We use dependencies of non-debug insns on debug insns to |
| indicate that the debug insns need to be reset if the non-debug |
| insn is pulled ahead of it. It's hard to figure out how to |
| introduce such a notion in sel-sched, but it already fails to |
| support debug insns in other ways, so we just go ahead and |
| let the deug insns go corrupt for now. */ |
| if (DEBUG_INSN_P (through_insn) && !DEBUG_INSN_P (insn)) |
| return MOVEUP_EXPR_SAME; |
| |
| /* When inside_insn_group, delegate to the helper. */ |
| if (inside_insn_group) |
| return moveup_expr_inside_insn_group (expr, through_insn); |
| |
| /* Deal with unique insns and control dependencies. */ |
| if (VINSN_UNIQUE_P (vi)) |
| { |
| /* We can move jumps without side-effects or jumps that are |
| mutually exclusive with instruction THROUGH_INSN (all in cases |
| dependencies allow to do so and jump is not speculative). */ |
| if (control_flow_insn_p (insn)) |
| { |
| basic_block fallthru_bb; |
| |
| /* Do not move checks and do not move jumps through other |
| jumps. */ |
| if (control_flow_insn_p (through_insn) |
| || sel_insn_is_speculation_check (insn)) |
| return MOVEUP_EXPR_NULL; |
| |
| /* Don't move jumps through CFG joins. */ |
| if (bookkeeping_can_be_created_if_moved_through_p (through_insn)) |
| return MOVEUP_EXPR_NULL; |
| |
| /* The jump should have a clear fallthru block, and |
| this block should be in the current region. */ |
| if ((fallthru_bb = fallthru_bb_of_jump (insn)) == NULL |
| || ! in_current_region_p (fallthru_bb)) |
| return MOVEUP_EXPR_NULL; |
| |
| /* And it should be mutually exclusive with through_insn. */ |
| if (! sched_insns_conditions_mutex_p (insn, through_insn) |
| && ! DEBUG_INSN_P (through_insn)) |
| return MOVEUP_EXPR_NULL; |
| } |
| |
| /* Don't move what we can't move. */ |
| if (EXPR_CANT_MOVE (expr) |
| && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn)) |
| return MOVEUP_EXPR_NULL; |
| |
| /* Don't move SCHED_GROUP instruction through anything. |
| If we don't force this, then it will be possible to start |
| scheduling a sched_group before all its dependencies are |
| resolved. |
| ??? Haifa deals with this issue by delaying the SCHED_GROUP |
| as late as possible through rank_for_schedule. */ |
| if (SCHED_GROUP_P (insn)) |
| return MOVEUP_EXPR_NULL; |
| } |
| else |
| gcc_assert (!control_flow_insn_p (insn)); |
| |
| /* Don't move debug insns if this would require bookkeeping. */ |
| if (DEBUG_INSN_P (insn) |
| && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn) |
| && moving_insn_creates_bookkeeping_block_p (insn, through_insn)) |
| return MOVEUP_EXPR_NULL; |
| |
| /* Deal with data dependencies. */ |
| was_target_conflict = false; |
| full_ds = has_dependence_p (expr, through_insn, &has_dep_p); |
| if (full_ds == 0) |
| { |
| if (!CANT_MOVE_TRAPPING (expr, through_insn)) |
| return MOVEUP_EXPR_SAME; |
| } |
| else |
| { |
| /* We can move UNIQUE insn up only as a whole and unchanged, |
| so it shouldn't have any dependencies. */ |
| if (VINSN_UNIQUE_P (vi)) |
| return MOVEUP_EXPR_NULL; |
| } |
| |
| if (full_ds != 0 && can_speculate_dep_p (full_ds)) |
| { |
| int res; |
| |
| res = speculate_expr (expr, full_ds); |
| if (res >= 0) |
| { |
| /* Speculation was successful. */ |
| full_ds = 0; |
| was_changed = (res > 0); |
| if (res == 2) |
| was_target_conflict = true; |
| if (ptrans_type) |
| *ptrans_type = TRANS_SPECULATION; |
| sel_clear_has_dependence (); |
| } |
| } |
| |
| if (has_dep_p[DEPS_IN_INSN]) |
| /* We have some dependency that cannot be discarded. */ |
| return MOVEUP_EXPR_NULL; |
| |
| if (has_dep_p[DEPS_IN_LHS]) |
| { |
| /* Only separable insns can be moved up with the new register. |
| Anyways, we should mark that the original register is |
| unavailable. */ |
| if (!enable_schedule_as_rhs_p || !EXPR_SEPARABLE_P (expr)) |
| return MOVEUP_EXPR_NULL; |
| |
| /* When renaming a hard register to a pseudo before reload, extra |
| dependencies can occur from the implicit clobbers of the insn. |
| Filter out such cases here. */ |
| if (!reload_completed && REG_P (EXPR_LHS (expr)) |
| && HARD_REGISTER_P (EXPR_LHS (expr)) |
| && implicit_clobber_conflict_p (through_insn, expr)) |
| { |
| if (sched_verbose >= 6) |
| sel_print ("implicit clobbers conflict detected, "); |
| return MOVEUP_EXPR_NULL; |
| } |
| EXPR_TARGET_AVAILABLE (expr) = false; |
| was_target_conflict = true; |
| as_rhs = true; |
| } |
| |
| /* At this point we have either separable insns, that will be lifted |
| up only as RHSes, or non-separable insns with no dependency in lhs. |
| If dependency is in RHS, then try to perform substitution and move up |
| substituted RHS: |
| |
| Ex. 1: Ex.2 |
| y = x; y = x; |
| z = y*2; y = y*2; |
| |
| In Ex.1 y*2 can be substituted for x*2 and the whole operation can be |
| moved above y=x assignment as z=x*2. |
| |
| In Ex.2 y*2 also can be substituted for x*2, but only the right hand |
| side can be moved because of the output dependency. The operation was |
| cropped to its rhs above. */ |
| if (has_dep_p[DEPS_IN_RHS]) |
| { |
| ds_t *rhs_dsp = &has_dep_p[DEPS_IN_RHS]; |
| |
| /* Can't substitute UNIQUE VINSNs. */ |
| gcc_assert (!VINSN_UNIQUE_P (vi)); |
| |
| if (can_speculate_dep_p (*rhs_dsp)) |
| { |
| int res; |
| |
| res = speculate_expr (expr, *rhs_dsp); |
| if (res >= 0) |
| { |
| /* Speculation was successful. */ |
| *rhs_dsp = 0; |
| was_changed = (res > 0); |
| if (res == 2) |
| was_target_conflict = true; |
| if (ptrans_type) |
| *ptrans_type = TRANS_SPECULATION; |
| } |
| else |
| return MOVEUP_EXPR_NULL; |
| } |
| else if (can_substitute_through_p (through_insn, |
| *rhs_dsp) |
| && substitute_reg_in_expr (expr, through_insn, false)) |
| { |
| /* ??? We cannot perform substitution AND speculation on the same |
| insn. */ |
| gcc_assert (!was_changed); |
| was_changed = true; |
| if (ptrans_type) |
| *ptrans_type = TRANS_SUBSTITUTION; |
| EXPR_WAS_SUBSTITUTED (expr) = true; |
| } |
| else |
| return MOVEUP_EXPR_NULL; |
| } |
| |
| /* Don't move trapping insns through jumps. |
| This check should be at the end to give a chance to control speculation |
| to perform its duties. */ |
| if (CANT_MOVE_TRAPPING (expr, through_insn)) |
| return MOVEUP_EXPR_NULL; |
| |
| return (was_changed |
| ? MOVEUP_EXPR_CHANGED |
| : (as_rhs |
| ? MOVEUP_EXPR_AS_RHS |
| : MOVEUP_EXPR_SAME)); |
| } |
| |
| /* Try to look at bitmap caches for EXPR and INSN pair, return true |
| if successful. When INSIDE_INSN_GROUP, also try ignore dependencies |
| that can exist within a parallel group. Write to RES the resulting |
| code for moveup_expr. */ |
| static bool |
| try_bitmap_cache (expr_t expr, insn_t insn, |
| bool inside_insn_group, |
| enum MOVEUP_EXPR_CODE *res) |
| { |
| int expr_uid = INSN_UID (EXPR_INSN_RTX (expr)); |
| |
| /* First check whether we've analyzed this situation already. */ |
| if (bitmap_bit_p (INSN_ANALYZED_DEPS (insn), expr_uid)) |
| { |
| if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid)) |
| { |
| if (sched_verbose >= 6) |
| sel_print ("removed (cached)\n"); |
| *res = MOVEUP_EXPR_NULL; |
| return true; |
| } |
| else |
| { |
| if (sched_verbose >= 6) |
| sel_print ("unchanged (cached)\n"); |
| *res = MOVEUP_EXPR_SAME; |
| return true; |
| } |
| } |
| else if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid)) |
| { |
| if (inside_insn_group) |
| { |
| if (sched_verbose >= 6) |
| sel_print ("unchanged (as RHS, cached, inside insn group)\n"); |
| *res = MOVEUP_EXPR_SAME; |
| return true; |
| |
| } |
| else |
| EXPR_TARGET_AVAILABLE (expr) = false; |
| |
| /* This is the only case when propagation result can change over time, |
| as we can dynamically switch off scheduling as RHS. In this case, |
| just check the flag to reach the correct decision. */ |
| if (enable_schedule_as_rhs_p) |
| { |
| if (sched_verbose >= 6) |
| sel_print ("unchanged (as RHS, cached)\n"); |
| *res = MOVEUP_EXPR_AS_RHS; |
| return true; |
| } |
| else |
| { |
| if (sched_verbose >= 6) |
| sel_print ("removed (cached as RHS, but renaming" |
| " is now disabled)\n"); |
| *res = MOVEUP_EXPR_NULL; |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| /* Try to look at bitmap caches for EXPR and INSN pair, return true |
| if successful. Write to RES the resulting code for moveup_expr. */ |
| static bool |
| try_transformation_cache (expr_t expr, insn_t insn, |
| enum MOVEUP_EXPR_CODE *res) |
| { |
| struct transformed_insns *pti |
| = (struct transformed_insns *) |
| htab_find_with_hash (INSN_TRANSFORMED_INSNS (insn), |
| &EXPR_VINSN (expr), |
| VINSN_HASH_RTX (EXPR_VINSN (expr))); |
| if (pti) |
| { |
| /* This EXPR was already moved through this insn and was |
| changed as a result. Fetch the proper data from |
| the hashtable. */ |
| insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr), |
| INSN_UID (insn), pti->type, |
| pti->vinsn_old, pti->vinsn_new, |
| EXPR_SPEC_DONE_DS (expr)); |
| |
| if (INSN_IN_STREAM_P (VINSN_INSN_RTX (pti->vinsn_new))) |
| pti->vinsn_new = vinsn_copy (pti->vinsn_new, true); |
| change_vinsn_in_expr (expr, pti->vinsn_new); |
| if (pti->was_target_conflict) |
| EXPR_TARGET_AVAILABLE (expr) = false; |
| if (pti->type == TRANS_SPECULATION) |
| { |
| EXPR_SPEC_DONE_DS (expr) = pti->ds; |
| EXPR_NEEDS_SPEC_CHECK_P (expr) |= pti->needs_check; |
| } |
| |
| if (sched_verbose >= 6) |
| { |
| sel_print ("changed (cached): "); |
| dump_expr (expr); |
| sel_print ("\n"); |
| } |
| |
| *res = MOVEUP_EXPR_CHANGED; |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /* Update bitmap caches on INSN with result RES of propagating EXPR. */ |
| static void |
| update_bitmap_cache (expr_t expr, insn_t insn, bool inside_insn_group, |
| enum MOVEUP_EXPR_CODE res) |
| { |
| int expr_uid = INSN_UID (EXPR_INSN_RTX (expr)); |
| |
| /* Do not cache result of propagating jumps through an insn group, |
| as it is always true, which is not useful outside the group. */ |
| if (inside_insn_group) |
| return; |
| |
| if (res == MOVEUP_EXPR_NULL) |
| { |
| bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid); |
| bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid); |
| } |
| else if (res == MOVEUP_EXPR_SAME) |
| { |
| bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid); |
| bitmap_clear_bit (INSN_FOUND_DEPS (insn), expr_uid); |
| } |
| else if (res == MOVEUP_EXPR_AS_RHS) |
| { |
| bitmap_clear_bit (INSN_ANALYZED_DEPS (insn), expr_uid); |
| bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid); |
| } |
| else |
| gcc_unreachable (); |
| } |
| |
| /* Update hashtable on INSN with changed EXPR, old EXPR_OLD_VINSN |
| and transformation type TRANS_TYPE. */ |
| static void |
| update_transformation_cache (expr_t expr, insn_t insn, |
| bool inside_insn_group, |
| enum local_trans_type trans_type, |
| vinsn_t expr_old_vinsn) |
| { |
| struct transformed_insns *pti; |
| |
| if (inside_insn_group) |
| return; |
| |
| pti = XNEW (struct transformed_insns); |
| pti->vinsn_old = expr_old_vinsn; |
| pti->vinsn_new = EXPR_VINSN (expr); |
| pti->type = trans_type; |
| pti->was_target_conflict = was_target_conflict; |
| pti->ds = EXPR_SPEC_DONE_DS (expr); |
| pti->needs_check = EXPR_NEEDS_SPEC_CHECK_P (expr); |
| vinsn_attach (pti->vinsn_old); |
| vinsn_attach (pti->vinsn_new); |
| *((struct transformed_insns **) |
| htab_find_slot_with_hash (INSN_TRANSFORMED_INSNS (insn), |
| pti, VINSN_HASH_RTX (expr_old_vinsn), |
| INSERT)) = pti; |
| } |
| |
| /* Same as moveup_expr, but first looks up the result of |
| transformation in caches. */ |
| static enum MOVEUP_EXPR_CODE |
| moveup_expr_cached (expr_t expr, insn_t insn, bool inside_insn_group) |
| { |
| enum MOVEUP_EXPR_CODE res; |
| bool got_answer = false; |
| |
| if (sched_verbose >= 6) |
| { |
| sel_print ("Moving "); |
| dump_expr (expr); |
| sel_print (" through %d: ", INSN_UID (insn)); |
| } |
| |
| if (DEBUG_INSN_P (EXPR_INSN_RTX (expr)) |
| && BLOCK_FOR_INSN (EXPR_INSN_RTX (expr)) |
| && (sel_bb_head (BLOCK_FOR_INSN (EXPR_INSN_RTX (expr))) |
| == EXPR_INSN_RTX (expr))) |
| /* Don't use cached information for debug insns that are heads of |
| basic blocks. */; |
| else if (try_bitmap_cache (expr, insn, inside_insn_group, &res)) |
| /* When inside insn group, we do not want remove stores conflicting |
| with previosly issued loads. */ |
| got_answer = ! inside_insn_group || res != MOVEUP_EXPR_NULL; |
| else if (try_transformation_cache (expr, insn, &res)) |
| got_answer = true; |
| |
| if (! got_answer) |
| { |
| /* Invoke moveup_expr and record the results. */ |
| vinsn_t expr_old_vinsn = EXPR_VINSN (expr); |
| ds_t expr_old_spec_ds = EXPR_SPEC_DONE_DS (expr); |
| int expr_uid = INSN_UID (VINSN_INSN_RTX (expr_old_vinsn)); |
| bool unique_p = VINSN_UNIQUE_P (expr_old_vinsn); |
| enum local_trans_type trans_type = TRANS_SUBSTITUTION; |
| |
| /* ??? 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); |
| |
| res = moveup_expr (expr, insn, inside_insn_group, |
| &trans_type); |
| switch (res) |
| { |
| case MOVEUP_EXPR_NULL: |
| update_bitmap_cache (expr, insn, inside_insn_group, res); |
| if (sched_verbose >= 6) |
| sel_print ("removed\n"); |
| break; |
| |
| case MOVEUP_EXPR_SAME: |
| update_bitmap_cache (expr, insn, inside_insn_group, res); |
| if (sched_verbose >= 6) |
| sel_print ("unchanged\n"); |
| break; |
| |
| case MOVEUP_EXPR_AS_RHS: |
| gcc_assert (!unique_p || inside_insn_group); |
| update_bitmap_cache (expr, insn, inside_insn_group, res); |
| if (sched_verbose >= 6) |
| sel_print ("unchanged (as RHS)\n"); |
| break; |
| |
| case MOVEUP_EXPR_CHANGED: |
| gcc_assert (INSN_UID (EXPR_INSN_RTX (expr)) != expr_uid |
| || EXPR_SPEC_DONE_DS (expr) != expr_old_spec_ds); |
| insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr), |
| INSN_UID (insn), trans_type, |
| expr_old_vinsn, EXPR_VINSN (expr), |
| expr_old_spec_ds); |
| update_transformation_cache (expr, insn, inside_insn_group, |
| trans_type, expr_old_vinsn); |
| if (sched_verbose >= 6) |
| { |
| sel_print ("changed: "); |
| dump_expr (expr); |
| sel_print ("\n"); |
| } |
| break; |
| default: |
| gcc_unreachable (); |
| } |
| |
| vinsn_detach (expr_old_vinsn); |
| } |
| |
| return res; |
| } |
| |
| /* Moves an av set AVP up through INSN, performing necessary |
| transformations. */ |
| static void |
| moveup_set_expr (av_set_t *avp, insn_t insn, bool inside_insn_group) |
| { |
| av_set_iterator i; |
| expr_t expr; |
| |
| FOR_EACH_EXPR_1 (expr, i, avp) |
| { |
| |
| switch (moveup_expr_cached (expr, insn, inside_insn_group)) |
| { |
| case MOVEUP_EXPR_SAME: |
| case MOVEUP_EXPR_AS_RHS: |
| break; |
| |
| case MOVEUP_EXPR_NULL: |
| av_set_iter_remove (&i); |
| break; |
| |
| case MOVEUP_EXPR_CHANGED: |
| expr = merge_with_other_exprs (avp, &i, expr); |
| break; |
| |
| default: |
| gcc_unreachable (); |
| } |
| } |
| } |
| |
| /* Moves AVP set along PATH. */ |
| static void |
| moveup_set_inside_insn_group (av_set_t *avp, ilist_t path) |
| { |
| int last_cycle; |
| |
| if (sched_verbose >= 6) |
| sel_print ("Moving expressions up in the insn group...\n"); |
| if (! path) |
| return; |
| last_cycle = INSN_SCHED_CYCLE (ILIST_INSN (path)); |
| while (path |
| && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle) |
| { |
| moveup_set_expr (avp, ILIST_INSN (path), true); |
| path = ILIST_NEXT (path); |
| } |
| } |
| |
| /* Returns true if after moving EXPR along PATH it equals to EXPR_VLIW. */ |
| static bool |
| equal_after_moveup_path_p (expr_t expr, ilist_t path, expr_t expr_vliw) |
| { |
| expr_def _tmp, *tmp = &_tmp; |
| int last_cycle; |
| bool res = true; |
| |
| copy_expr_onside (tmp, expr); |
| last_cycle = path ? INSN_SCHED_CYCLE (ILIST_INSN (path)) : 0; |
| while (path |
| && res |
| && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle) |
| { |
| res = (moveup_expr_cached (tmp, ILIST_INSN (path), true) |
| != MOVEUP_EXPR_NULL); |
| path = ILIST_NEXT (path); |
| } |
| |
| if (res) |
| { |
| vinsn_t tmp_vinsn = EXPR_VINSN (tmp); |
| vinsn_t expr_vliw_vinsn = EXPR_VINSN (expr_vliw); |
| |
| if (tmp_vinsn != expr_vliw_vinsn) |
| res = vinsn_equal_p (tmp_vinsn, expr_vliw_vinsn); |
| } |
| |
| clear_expr (tmp); |
| return res; |
| } |
| |
| |
| /* Functions that compute av and lv sets. */ |
| |
| /* Returns true if INSN is not a downward continuation of the given path P in |
| the current stage. */ |
| static bool |
| is_ineligible_successor (insn_t insn, ilist_t p) |
| { |
| insn_t prev_insn; |
| |
| /* Check if insn is not deleted. */ |
| if (PREV_INSN (insn) && NEXT_INSN (PREV_INSN (insn)) != insn) |
| gcc_unreachable (); |
| else if (NEXT_INSN (insn) && PREV_INSN (NEXT_INSN (insn)) != insn) |
| gcc_unreachable (); |
| |
| /* If it's the first insn visited, then the successor is ok. */ |
| if (!p) |
| return false; |
| |
| prev_insn = ILIST_INSN (p); |
| |
| if (/* a backward edge. */ |
| INSN_SEQNO (insn) < INSN_SEQNO (prev_insn) |
| /* is already visited. */ |
| || (INSN_SEQNO (insn) == INSN_SEQNO (prev_insn) |
| && (ilist_is_in_p (p, insn) |
| /* We can reach another fence here and still seqno of insn |
| would be equal to seqno of prev_insn. This is possible |
| when prev_insn is a previously created bookkeeping copy. |
| In that case it'd get a seqno of insn. Thus, check here |
| whether insn is in current fence too. */ |
| || IN_CURRENT_FENCE_P (insn))) |
| /* Was already scheduled on this round. */ |
| || (INSN_SEQNO (insn) > INSN_SEQNO (prev_insn) |
| && IN_CURRENT_FENCE_P (insn)) |
| /* 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 |
| && INSN_SCHED_TIMES (insn) > 0)) |
| return true; |
| else |
| return false; |
| } |
| |
| /* 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. |
| Return the av set computed. */ |
| static av_set_t |
| compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws) |
| { |
| struct succs_info *sinfo; |
| av_set_t expr_in_all_succ_branches = NULL; |
| int is; |
| insn_t succ, zero_succ = NULL; |
| av_set_t av1 = NULL; |
| |
| gcc_assert (sel_bb_end_p (insn)); |
| |
| /* Find different kind of successors needed for correct computing of |
| SPEC and TARGET_AVAILABLE attributes. */ |
| sinfo = compute_succs_info (insn, SUCCS_NORMAL); |
| |
| /* Debug output. */ |
| if (sched_verbose >= 6) |
| { |
| sel_print ("successors of bb end (%d): ", INSN_UID (insn)); |
| dump_insn_vector (sinfo->succs_ok); |
| sel_print ("\n"); |
| if (sinfo->succs_ok_n != sinfo->all_succs_n) |
| sel_print ("real successors num: %d\n", sinfo->all_succs_n); |
| } |
| |
| /* Add insn to the tail of current path. */ |
| ilist_add (&p, insn); |
| |
| FOR_EACH_VEC_ELT (sinfo->succs_ok, is, succ) |
| { |
| av_set_t succ_set; |
| |
| /* We will edit SUCC_SET and EXPR_SPEC field of its elements. */ |
| succ_set = compute_av_set_inside_bb (succ, p, ws, true); |
| |
| av_set_split_usefulness (succ_set, |
| sinfo->probs_ok[is], |
| sinfo->all_prob); |
| |
| if (sinfo->all_succs_n > 1) |
| { |
| /* Find EXPR'es that came from *all* successors and save them |
| into expr_in_all_succ_branches. This set will be used later |
| for calculating speculation attributes of EXPR'es. */ |
| if (is == 0) |
| { |
| expr_in_all_succ_branches = av_set_copy (succ_set); |
| |
| /* Remember the first successor for later. */ |
| zero_succ = succ; |
| } |
| else |
| { |
| av_set_iterator i; |
| expr_t expr; |
| |
| FOR_EACH_EXPR_1 (expr, i, &expr_in_all_succ_branches) |
| if (!av_set_is_in_p (succ_set, EXPR_VINSN (expr))) |
| av_set_iter_remove (&i); |
| } |
| } |
| |
| /* Union the av_sets. Check liveness restrictions on target registers |
| in special case of two successors. */ |
| if (sinfo->succs_ok_n == 2 && is == 1) |
| { |
| basic_block bb0 = BLOCK_FOR_INSN (zero_succ); |
| basic_block bb1 = BLOCK_FOR_INSN (succ); |
| |
| 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); |
| } |
| else |
| av_set_union_and_clear (&av1, &succ_set, insn); |
| } |
| |
| /* Check liveness restrictions via hard way when there are more than |
| two successors. */ |
| if (sinfo->succs_ok_n > 2) |
| FOR_EACH_VEC_ELT (sinfo->succs_ok, is, succ) |
| { |
| basic_block succ_bb = BLOCK_FOR_INSN (succ); |
| |
| gcc_assert (BB_LV_SET_VALID_P (succ_bb)); |
| mark_unavailable_targets (av1, BB_AV_SET (succ_bb), |
| BB_LV_SET (succ_bb)); |
| } |
| |
| /* Finally, check liveness restrictions on paths leaving the region. */ |
| if (sinfo->all_succs_n > sinfo->succs_ok_n) |
| FOR_EACH_VEC_ELT (sinfo->succs_other, is, succ) |
| mark_unavailable_targets |
| (av1, NULL, BB_LV_SET (BLOCK_FOR_INSN (succ))); |
| |
| if (sinfo->all_succs_n > 1) |
| { |
| av_set_iterator i; |
| expr_t expr; |
| |
| /* Increase the spec attribute of all EXPR'es that didn't come |
| from all successors. */ |
| FOR_EACH_EXPR (expr, i, av1) |
| if (!av_set_is_in_p (expr_in_all_succ_branches, EXPR_VINSN (expr))) |
| EXPR_SPEC (expr)++; |
| |
| av_set_clear (&expr_in_all_succ_branches); |
| |
| /* Do not move conditional branches through other |
| conditional branches. So, remove all conditional |
| branches from av_set if current operator is a conditional |
| branch. */ |
| av_set_substract_cond_branches (&av1); |
| } |
| |
| ilist_remove (&p); |
| free_succs_info (sinfo); |
| |
| if (sched_verbose >= 6) |
| { |
| sel_print ("av_succs (%d): ", INSN_UID (insn)); |
| dump_av_set (av1); |
| sel_print ("\n"); |
| } |
| |
| return av1; |
| } |
| |
| /* This function computes av_set for the FIRST_INSN by dragging valid |
| av_set through all basic block insns either from the end of basic block |
| (computed using compute_av_set_at_bb_end) or from the insn on which |
| MAX_WS was exceeded. It uses compute_av_set_at_bb_end to compute av_set |
| below the basic block and handling conditional branches. |
| FIRST_INSN - the basic block head, P - path consisting of the insns |
| traversed on the way to the FIRST_INSN (the path is sparse, only bb heads |
| and bb ends are added to the path), WS - current window size, |
| NEED_COPY_P - true if we'll make a copy of av_set before returning it. */ |
| static av_set_t |
| compute_av_set_inside_bb (insn_t first_insn, ilist_t p, int ws, |
| bool need_copy_p) |
| { |
| insn_t cur_insn; |
| int end_ws = ws; |
| insn_t bb_end = sel_bb_end (BLOCK_FOR_INSN (first_insn)); |
| insn_t after_bb_end = NEXT_INSN (bb_end); |
| insn_t last_insn; |
| av_set_t av = NULL; |
| basic_block cur_bb = BLOCK_FOR_INSN (first_insn); |
| |
| /* Return NULL if insn is not on the legitimate downward path. */ |
| if (is_ineligible_successor (first_insn, p)) |
| { |
| if (sched_verbose >= 6) |
| sel_print ("Insn %d is ineligible_successor\n", INSN_UID (first_insn)); |
| |
| return NULL; |
| } |
| |
| /* If insn already has valid av(insn) computed, just return it. */ |
| if (AV_SET_VALID_P (first_insn)) |
| { |
| av_set_t av_set; |
| |
| if (sel_bb_head_p (first_insn)) |
| av_set = BB_AV_SET (BLOCK_FOR_INSN (first_insn)); |
| else |
| av_set = NULL; |
| |
| if (sched_verbose >= 6) |
| { |
| sel_print ("Insn %d has a valid av set: ", INSN_UID (first_insn)); |
| dump_av_set (av_set); |
| sel_print ("\n"); |
| } |
| |
| return need_copy_p ? av_set_copy (av_set) : av_set; |
| } |
| |
| ilist_add (&p, first_insn); |
| |
| /* As the result after this loop have completed, in LAST_INSN we'll |
| have the insn which has valid av_set to start backward computation |
| from: it either will be NULL because on it the window size was exceeded |
| or other valid av_set as returned by compute_av_set for the last insn |
| of the basic block. */ |
| for (last_insn = first_insn; last_insn != after_bb_end; |
| last_insn = NEXT_INSN (last_insn)) |
| { |
| /* We may encounter valid av_set not only on bb_head, but also on |
| those insns on which previously MAX_WS was exceeded. */ |
| if (AV_SET_VALID_P (last_insn)) |
| { |
| if (sched_verbose >= 6) |
| sel_print ("Insn %d has a valid empty av set\n", INSN_UID (last_insn)); |
| break; |
| } |
| |
| /* The special case: the last insn of the BB may be an |
| ineligible_successor due to its SEQ_NO that was set on |
| it as a bookkeeping. */ |
| if (last_insn != first_insn |
| && is_ineligible_successor (last_insn, p)) |
| { |
| if (sched_verbose >= 6) |
| sel_print ("Insn %d is ineligible_successor\n", INSN_UID (last_insn)); |
| break; |
| } |
| |
| if (DEBUG_INSN_P (last_insn)) |
| continue; |
| |
| if (end_ws > max_ws) |
| { |
| /* We can reach max lookahead size at bb_header, so clean av_set |
| first. */ |
| INSN_WS_LEVEL (last_insn) = global_level; |
| |
| if (sched_verbose >= 6) |
| sel_print ("Insn %d is beyond the software lookahead window size\n", |
| INSN_UID (last_insn)); |
| break; |
| } |
| |
| end_ws++; |
| } |
| |
| /* Get the valid av_set into AV above the LAST_INSN to start backward |
| computation from. It either will be empty av_set or av_set computed from |
| the successors on the last insn of the current bb. */ |
| if (last_insn != after_bb_end) |
| { |
| av = NULL; |
| |
| /* This is needed only to obtain av_sets that are identical to |
| those computed by the old compute_av_set version. */ |
| if (last_insn == first_insn && !INSN_NOP_P (last_insn)) |
| av_set_add (&av, INSN_EXPR (last_insn)); |
| } |
| else |
| /* END_WS is always already increased by 1 if LAST_INSN == AFTER_BB_END. */ |
| av = compute_av_set_at_bb_end (bb_end, p, end_ws); |
| |
| /* Compute av_set in AV starting from below the LAST_INSN up to |
| location above the FIRST_INSN. */ |
| for (cur_insn = PREV_INSN (last_insn); cur_insn != PREV_INSN (first_insn); |
| cur_insn = PREV_INSN (cur_insn)) |
| if (!INSN_NOP_P (cur_insn)) |
| { |
| expr_t expr; |
| |
| moveup_set_expr (&av, cur_insn, false); |
| |
| /* If the expression for CUR_INSN is already in the set, |
| replace it by the new one. */ |
| expr = av_set_lookup (av, INSN_VINSN (cur_insn)); |
| if (expr != NULL) |
| { |
| clear_expr (expr); |
| copy_expr (expr, INSN_EXPR (cur_insn)); |
| } |
| else |
| av_set_add (&av, INSN_EXPR (cur_insn)); |
| } |
| |
| /* Clear stale bb_av_set. */ |
| if (sel_bb_head_p (first_insn)) |
| { |
| av_set_clear (&BB_AV_SET (cur_bb)); |
| BB_AV_SET (cur_bb) = need_copy_p ? av_set_copy (av) : av; |
| BB_AV_LEVEL (cur_bb) = global_level; |
| } |
| |
| if (sched_verbose >= 6) |
| { |
| sel_print ("Computed av set for insn %d: ", INSN_UID (first_insn)); |
| dump_av_set (av); |
| sel_print ("\n"); |
| } |
| |
| ilist_remove (&p); |
| return av; |
| } |
| |
| /* Compute av set before INSN. |
| INSN - the current operation (actual rtx INSN) |
| P - the current path, which is list of insns visited so far |
| WS - software lookahead window size. |
| UNIQUE_P - TRUE, if returned av_set will be changed, hence |
| if we want to save computed av_set in s_i_d, we should make a copy of it. |
| |
| In the resulting set we will have only expressions that don't have delay |
| stalls and nonsubstitutable dependences. */ |
| static av_set_t |
| compute_av_set (insn_t insn, ilist_t p, int ws, bool unique_p) |
| { |
| return compute_av_set_inside_bb (insn, p, ws, unique_p); |
| } |
| |
| /* Propagate a liveness set LV through INSN. */ |
| static void |
| propagate_lv_set (regset lv, insn_t insn) |
| { |
| gcc_assert (INSN_P (insn)); |
| |
| if (INSN_NOP_P (insn)) |
| return; |
| |
| df_simulate_one_insn_backwards (BLOCK_FOR_INSN (insn), insn, lv); |
| } |
| |
| /* Return livness set at the end of BB. */ |
| static regset |
| compute_live_after_bb (basic_block bb) |
| { |
| edge e; |
| edge_iterator ei; |
| regset lv = get_clear_regset_from_pool (); |
| |
| gcc_assert (!ignore_first); |
| |
| FOR_EACH_EDGE (e, ei, bb->succs) |
| if (sel_bb_empty_p (e->dest)) |
| { |
| if (! BB_LV_SET_VALID_P (e->dest)) |
| { |
| gcc_unreachable (); |
| gcc_assert (BB_LV_SET (e->dest) == NULL); |
| BB_LV_SET (e->dest) = compute_live_after_bb (e->dest); |
| BB_LV_SET_VALID_P (e->dest) = true; |
| } |
| IOR_REG_SET (lv, BB_LV_SET (e->dest)); |
| } |
| else |
| IOR_REG_SET (lv, compute_live (sel_bb_head (e->dest))); |
| |
| return lv; |
| } |
| |
| /* Compute the set of all live registers at the point before INSN and save |
| it at INSN if INSN is bb header. */ |
| regset |
| compute_live (insn_t insn) |
| { |
| basic_block bb = BLOCK_FOR_INSN (insn); |
| insn_t final, temp; |
| regset lv; |
| |
| /* Return the valid set if we're already on it. */ |
| if (!ignore_first) |
| { |
| regset src = NULL; |
| |
| if (sel_bb_head_p (insn) && BB_LV_SET_VALID_P (bb)) |
| src = BB_LV_SET (bb); |
| else |
| { |
| gcc_assert (in_current_region_p (bb)); |
| if (INSN_LIVE_VALID_P (insn)) |
| src = INSN_LIVE (insn); |
| } |
| |
| if (src) |
| { |
| lv = get_regset_from_pool (); |
| COPY_REG_SET (lv, src); |
| |
| if (sel_bb_head_p (insn) && ! BB_LV_SET_VALID_P (bb)) |
| { |
| COPY_REG_SET (BB_LV_SET (bb), lv); |
| BB_LV_SET_VALID_P (bb) = true; |
| } |
| |
| return_regset_to_pool (lv); |
| return lv; |
| } |
| } |
| |
| /* We've skipped the wrong lv_set. Don't skip the right one. */ |
| ignore_first = false; |
| gcc_assert (in_current_region_p (bb)); |
| |
| /* Find a valid LV set in this block or below, if needed. |
| Start searching from the next insn: either ignore_first is true, or |
| INSN doesn't have a correct live set. */ |
| temp = NEXT_INSN (insn); |
| final = NEXT_INSN (BB_END (bb)); |
| while (temp != final && ! INSN_LIVE_VALID_P (temp)) |
| temp = NEXT_INSN (temp); |
| if (temp == final) |
| { |
| lv = compute_live_after_bb (bb); |
| temp = PREV_INSN (temp); |
| } |
| else |
| { |
| lv = get_regset_from_pool (); |
| COPY_REG_SET (lv, INSN_LIVE (temp)); |
| } |
| |
| /* Put correct lv sets on the insns which have bad sets. */ |
| final = PREV_INSN (insn); |
| while (temp != final) |
| { |
| propagate_lv_set (lv, temp); |
| COPY_REG_SET (INSN_LIVE (temp), lv); |
| INSN_LIVE_VALID_P (temp) = true; |
| temp = PREV_INSN (temp); |
| } |
| |
| /* Also put it in a BB. */ |
| if (sel_bb_head_p (insn)) |
| { |
| basic_block bb = BLOCK_FOR_INSN (insn); |
| |
| COPY_REG_SET (BB_LV_SET (bb), lv); |
| BB_LV_SET_VALID_P (bb) = true; |
| } |
| |
| /* We return LV to the pool, but will not clear it there. Thus we can |
| legimatelly use LV till the next use of regset_pool_get (). */ |
| return_regset_to_pool (lv); |
| return lv; |
| } |
| |
| /* Update liveness sets for INSN. */ |
| static inline void |
| update_liveness_on_insn (rtx_insn *insn) |
| { |
| ignore_first = true; |
| compute_live (insn); |
| } |
| |
| /* Compute liveness below INSN and write it into REGS. */ |
| static inline void |
| compute_live_below_insn (rtx_insn *insn, regset regs) |
| { |
| rtx_insn *succ; |
| succ_iterator si; |
| |
| FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL) |
| IOR_REG_SET (regs, compute_live (succ)); |
| } |
| |
| /* Update the data gathered in av and lv sets starting from INSN. */ |
| static void |
| update_data_sets (rtx_insn *insn) |
| { |
| update_liveness_on_insn (insn); |
| if (sel_bb_head_p (insn)) |
| { |
| gcc_assert (AV_LEVEL (insn) != 0); |
| BB_AV_LEVEL (BLOCK_FOR_INSN (insn)) = -1; |
| compute_av_set (insn, NULL, 0, 0); |
| } |
| } |
| |
| |
| /* Helper for move_op () and find_used_regs (). |
| Return speculation type for which a check should be created on the place |
| of INSN. EXPR is one of the original ops we are searching for. */ |
| static ds_t |
| get_spec_check_type_for_insn (insn_t insn, expr_t expr) |
| { |
| ds_t to_check_ds; |
| ds_t already_checked_ds = EXPR_SPEC_DONE_DS (INSN_EXPR (insn)); |
| |
| to_check_ds = EXPR_SPEC_TO_CHECK_DS (expr); |
| |
| if (targetm.sched.get_insn_checked_ds) |
| already_checked_ds |= targetm.sched.get_insn_checked_ds (insn); |
| |
| if (spec_info != NULL |
| && (spec_info->flags & SEL_SCHED_SPEC_DONT_CHECK_CONTROL)) |
| already_checked_ds |= BEGIN_CONTROL; |
| |
| already_checked_ds = ds_get_speculation_types (already_checked_ds); |
| |
| to_check_ds &= ~already_checked_ds; |
| |
| return to_check_ds; |
| } |
| |
| /* Find the set of registers that are unavailable for storing expres |
| while moving ORIG_OPS up on the path starting from INSN due to |
| liveness (USED_REGS) or hardware restrictions (REG_RENAME_P). |
| |
| All the original operations found during the traversal are saved in the |
| ORIGINAL_INSNS list. |
| |
| REG_RENAME_P denotes the set of hardware registers that |
| can not be used with renaming due to the register class restrictions, |
| mode restrictions and other (the register we'll choose should be |
| compatible class with the original uses, shouldn't be in call_used_regs, |
| should be HARD_REGNO_RENAME_OK etc). |
| |
| Returns TRUE if we've found all original insns, FALSE otherwise. |
| |
| This function utilizes code_motion_path_driver (formerly find_used_regs_1) |
| to traverse the code motion paths. This helper function finds registers |
| that are not available for storing expres while moving ORIG_OPS up on the |
| path starting from INSN. A register considered as used on the moving path, |
| if one of the following conditions is not satisfied: |
| |
| (1) a register not set or read on any path from xi to an instance of |
| the original operation, |
| (2) not among the live registers of the point immediately following the |
| first original operation on a given downward path, except for the |
| original target register of the operation, |
| (3) not live on the other path of any conditional branch that is passed |
| by the operation, in case original operations are not present on |
| both paths of the conditional branch. |
| |
| All the original operations found during the traversal are saved in the |
| ORIGINAL_INSNS list. |
| |
| REG_RENAME_P->CROSSES_CALL is true, if there is a call insn on the path |
| from INSN to original insn. In this case CALL_USED_REG_SET will be added |
| to unavailable hard regs at the point original operation is found. */ |
| |
| static bool |
| find_used_regs (insn_t insn, av_set_t orig_ops, regset used_regs, |
| struct reg_rename *reg_rename_p, def_list_t *original_insns) |
| { |
| def_list_iterator i; |
| def_t def; |
| int res; |
| bool needs_spec_check_p = false; |
| expr_t expr; |
| av_set_iterator expr_iter; |
| struct fur_static_params sparams; |
| struct cmpd_local_params lparams; |
| |
| /* We haven't visited any blocks yet. */ |
| bitmap_clear (code_motion_visited_blocks); |
| |
| /* Init parameters for code_motion_path_driver. */ |
| sparams.crosses_call = false; |
| sparams.original_insns = original_insns; |
| sparams.used_regs = used_regs; |
| |
| /* Set the appropriate hooks and data. */ |
| code_motion_path_driver_info = &fur_hooks; |
| |
| res = code_motion_path_driver (insn, orig_ops, NULL, &lparams, &sparams); |
| |
| reg_rename_p->crosses_call |= sparams.crosses_call; |
| |
| gcc_assert (res == 1); |
| gcc_assert (original_insns && *original_insns); |
| |
| /* ??? We calculate whether an expression needs a check when computing |
| av sets. This information is not as precise as it could be due to |
| merging this bit in merge_expr. We can do better in find_used_regs, |
| but we want to avoid multiple traversals of the same code motion |
| paths. */ |
| FOR_EACH_EXPR (expr, expr_iter, orig_ops) |
| needs_spec_check_p |= EXPR_NEEDS_SPEC_CHECK_P (expr); |
| |
| /* Mark hardware regs in REG_RENAME_P that are not suitable |
| for renaming expr in INSN due to hardware restrictions (register class, |
| modes compatibility etc). */ |
| FOR_EACH_DEF (def, i, *original_insns) |
| { |
| vinsn_t vinsn = INSN_VINSN (def->orig_insn); |
| |
| if (VINSN_SEPARABLE_P (vinsn)) |
| mark_unavailable_hard_regs (def, reg_rename_p, used_regs); |
| |
| /* Do not allow clobbering of ld.[sa] address in case some of the |
| original operations need a check. */ |
| if (needs_spec_check_p) |
| IOR_REG_SET (used_regs, VINSN_REG_USES (vinsn)); |
| } |
| |
| return true; |
| } |
| |
| |
| /* Functions to choose the best insn from available ones. */ |
| |
| /* Adjusts the priority for EXPR using the backend *_adjust_priority hook. */ |
| static int |
| sel_target_adjust_priority (expr_t expr) |
| { |
| int priority = EXPR_PRIORITY (expr); |
| int new_priority; |
| |
| if (targetm.sched.adjust_priority) |
| new_priority = targetm.sched.adjust_priority (EXPR_INSN_RTX (expr), priority); |
| else |
| new_priority = priority; |
| |
| /* If the priority has changed, adjust EXPR_PRIORITY_ADJ accordingly. */ |
| EXPR_PRIORITY_ADJ (expr) = new_priority - EXPR_PRIORITY (expr); |
| |
| gcc_assert (EXPR_PRIORITY_ADJ (expr) >= 0); |
| |
| if (sched_verbose >= 4) |
| sel_print ("sel_target_adjust_priority: insn %d, %d+%d = %d.\n", |
| INSN_UID (EXPR_INSN_RTX (expr)), EXPR_PRIORITY (expr), |
| EXPR_PRIORITY_ADJ (expr), new_priority); |
| |
| return new_priority; |
| } |
| |
| /* Rank two available exprs for schedule. Never return 0 here. */ |
| static int |
| sel_rank_for_schedule (const void *x, const void *y) |
| { |
| expr_t tmp = *(const expr_t *) y; |
| expr_t tmp2 = *(const expr_t *) x; |
| insn_t tmp_insn, tmp2_insn; |
| vinsn_t tmp_vinsn, tmp2_vinsn; |
| int val; |
| |
| tmp_vinsn = EXPR_VINSN (tmp); |
| tmp2_vinsn = EXPR_VINSN (tmp2); |
| tmp_insn = EXPR_INSN_RTX (tmp); |
| tmp2_insn = EXPR_INSN_RTX (tmp2); |
| |
| /* Schedule debug insns as early as possible. */ |
| if (DEBUG_INSN_P (tmp_insn) && !DEBUG_INSN_P (tmp2_insn)) |
|
|