00001 /* Instruction scheduling pass. This file contains definitions used 00002 internally in the scheduler. 00003 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 00004 1999, 2000, 2001 Free Software Foundation, Inc. 00005 00006 This file is part of GCC. 00007 00008 GCC is free software; you can redistribute it and/or modify it under 00009 the terms of the GNU General Public License as published by the Free 00010 Software Foundation; either version 2, or (at your option) any later 00011 version. 00012 00013 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 00014 WARRANTY; without even the implied warranty of MERCHANTABILITY or 00015 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 00016 for more details. 00017 00018 You should have received a copy of the GNU General Public License 00019 along with GCC; see the file COPYING. If not, write to the Free 00020 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 00021 02111-1307, USA. */ 00022 00023 /* Pointer to data describing the current DFA state. */ 00024 extern state_t curr_state; 00025 00026 /* Forward declaration. */ 00027 struct ready_list; 00028 00029 /* Describe state of dependencies used during sched_analyze phase. */ 00030 struct deps 00031 { 00032 /* The *_insns and *_mems are paired lists. Each pending memory operation 00033 will have a pointer to the MEM rtx on one list and a pointer to the 00034 containing insn on the other list in the same place in the list. */ 00035 00036 /* We can't use add_dependence like the old code did, because a single insn 00037 may have multiple memory accesses, and hence needs to be on the list 00038 once for each memory access. Add_dependence won't let you add an insn 00039 to a list more than once. */ 00040 00041 /* An INSN_LIST containing all insns with pending read operations. */ 00042 rtx pending_read_insns; 00043 00044 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ 00045 rtx pending_read_mems; 00046 00047 /* An INSN_LIST containing all insns with pending write operations. */ 00048 rtx pending_write_insns; 00049 00050 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ 00051 rtx pending_write_mems; 00052 00053 /* Indicates the combined length of the two pending lists. We must prevent 00054 these lists from ever growing too large since the number of dependencies 00055 produced is at least O(N*N), and execution time is at least O(4*N*N), as 00056 a function of the length of these pending lists. */ 00057 int pending_lists_length; 00058 00059 /* Length of the pending memory flush list. Large functions with no 00060 calls may build up extremely large lists. */ 00061 int pending_flush_length; 00062 00063 /* The last insn upon which all memory references must depend. 00064 This is an insn which flushed the pending lists, creating a dependency 00065 between it and all previously pending memory references. This creates 00066 a barrier (or a checkpoint) which no memory reference is allowed to cross. 00067 00068 This includes all non constant CALL_INSNs. When we do interprocedural 00069 alias analysis, this restriction can be relaxed. 00070 This may also be an INSN that writes memory if the pending lists grow 00071 too large. */ 00072 rtx last_pending_memory_flush; 00073 00074 /* A list of the last function calls we have seen. We use a list to 00075 represent last function calls from multiple predecessor blocks. 00076 Used to prevent register lifetimes from expanding unnecessarily. */ 00077 rtx last_function_call; 00078 00079 /* A list of insns which use a pseudo register that does not already 00080 cross a call. We create dependencies between each of those insn 00081 and the next call insn, to ensure that they won't cross a call after 00082 scheduling is done. */ 00083 rtx sched_before_next_call; 00084 00085 /* Used to keep post-call psuedo/hard reg movements together with 00086 the call. */ 00087 bool in_post_call_group_p; 00088 00089 /* Set to the tail insn of the outermost libcall block. 00090 00091 When nonzero, we will mark each insn processed by sched_analyze_insn 00092 with SCHED_GROUP_P to ensure libcalls are scheduled as a unit. */ 00093 rtx libcall_block_tail_insn; 00094 00095 /* The maximum register number for the following arrays. Before reload 00096 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */ 00097 int max_reg; 00098 00099 /* Element N is the next insn that sets (hard or pseudo) register 00100 N within the current basic block; or zero, if there is no 00101 such insn. Needed for new registers which may be introduced 00102 by splitting insns. */ 00103 struct deps_reg 00104 { 00105 rtx uses; 00106 rtx sets; 00107 rtx clobbers; 00108 int uses_length; 00109 int clobbers_length; 00110 } *reg_last; 00111 00112 /* Element N is set for each register that has any nonzero element 00113 in reg_last[N].{uses,sets,clobbers}. */ 00114 regset_head reg_last_in_use; 00115 00116 /* Element N is set for each register that is conditionally set. */ 00117 regset_head reg_conditional_sets; 00118 }; 00119 00120 /* This structure holds some state of the current scheduling pass, and 00121 contains some function pointers that abstract out some of the non-generic 00122 functionality from functions such as schedule_block or schedule_insn. 00123 There is one global variable, current_sched_info, which points to the 00124 sched_info structure currently in use. */ 00125 struct sched_info 00126 { 00127 /* Add all insns that are initially ready to the ready list. Called once 00128 before scheduling a set of insns. */ 00129 void (*init_ready_list) PARAMS ((struct ready_list *)); 00130 /* Called after taking an insn from the ready list. Returns nonzero if 00131 this insn can be scheduled, nonzero if we should silently discard it. */ 00132 int (*can_schedule_ready_p) PARAMS ((rtx)); 00133 /* Return nonzero if there are more insns that should be scheduled. */ 00134 int (*schedule_more_p) PARAMS ((void)); 00135 /* Called after an insn has all its dependencies resolved. Return nonzero 00136 if it should be moved to the ready list or the queue, or zero if we 00137 should silently discard it. */ 00138 int (*new_ready) PARAMS ((rtx)); 00139 /* Compare priority of two insns. Return a positive number if the second 00140 insn is to be preferred for scheduling, and a negative one if the first 00141 is to be preferred. Zero if they are equally good. */ 00142 int (*rank) PARAMS ((rtx, rtx)); 00143 /* Return a string that contains the insn uid and optionally anything else 00144 necessary to identify this insn in an output. It's valid to use a 00145 static buffer for this. The ALIGNED parameter should cause the string 00146 to be formatted so that multiple output lines will line up nicely. */ 00147 const char *(*print_insn) PARAMS ((rtx, int)); 00148 /* Return nonzero if an insn should be included in priority 00149 calculations. */ 00150 int (*contributes_to_priority) PARAMS ((rtx, rtx)); 00151 /* Called when computing dependencies for a JUMP_INSN. This function 00152 should store the set of registers that must be considered as used 00153 and the set of registers that must be considered as set by the jump. */ 00154 void (*compute_jump_reg_dependencies) PARAMS ((rtx, regset, regset, regset)); 00155 00156 /* The boundaries of the set of insns to be scheduled. */ 00157 rtx prev_head, next_tail; 00158 00159 /* Filled in after the schedule is finished; the first and last scheduled 00160 insns. */ 00161 rtx head, tail; 00162 00163 /* If nonzero, enables an additional sanity check in schedule_block. */ 00164 unsigned int queue_must_finish_empty:1; 00165 /* Nonzero if we should use cselib for better alias analysis. This 00166 must be 0 if the dependency information is used after sched_analyze 00167 has completed, e.g. if we're using it to initialize state for successor 00168 blocks in region scheduling. */ 00169 unsigned int use_cselib:1; 00170 }; 00171 00172 extern struct sched_info *current_sched_info; 00173 00174 /* Indexed by INSN_UID, the collection of all data associated with 00175 a single instruction. */ 00176 00177 struct haifa_insn_data 00178 { 00179 /* A list of insns which depend on the instruction. Unlike LOG_LINKS, 00180 it represents forward dependencies. */ 00181 rtx depend; 00182 00183 /* The line number note in effect for each insn. For line number 00184 notes, this indicates whether the note may be reused. */ 00185 rtx line_note; 00186 00187 /* Logical uid gives the original ordering of the insns. */ 00188 int luid; 00189 00190 /* A priority for each insn. */ 00191 int priority; 00192 00193 /* The number of incoming edges in the forward dependency graph. 00194 As scheduling proceds, counts are decreased. An insn moves to 00195 the ready queue when its counter reaches zero. */ 00196 int dep_count; 00197 00198 /* An encoding of the blockage range function. Both unit and range 00199 are coded. This member is used only for old pipeline interface. */ 00200 unsigned int blockage; 00201 00202 /* Number of instructions referring to this insn. */ 00203 int ref_count; 00204 00205 /* The minimum clock tick at which the insn becomes ready. This is 00206 used to note timing constraints for the insns in the pending list. */ 00207 int tick; 00208 00209 short cost; 00210 00211 /* An encoding of the function units used. This member is used only 00212 for old pipeline interface. */ 00213 short units; 00214 00215 /* This weight is an estimation of the insn's contribution to 00216 register pressure. */ 00217 short reg_weight; 00218 00219 /* Some insns (e.g. call) are not allowed to move across blocks. */ 00220 unsigned int cant_move : 1; 00221 00222 /* Set if there's DEF-USE dependence between some speculatively 00223 moved load insn and this one. */ 00224 unsigned int fed_by_spec_load : 1; 00225 unsigned int is_load_insn : 1; 00226 00227 /* Nonzero if priority has been computed already. */ 00228 unsigned int priority_known : 1; 00229 }; 00230 00231 extern struct haifa_insn_data *h_i_d; 00232 00233 /* Accessor macros for h_i_d. There are more in haifa-sched.c and 00234 sched-rgn.c. */ 00235 #define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) 00236 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) 00237 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) 00238 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) 00239 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) 00240 #define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known) 00241 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) 00242 #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units) 00243 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) 00244 00245 #define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage) 00246 #define UNIT_BITS 5 00247 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1) 00248 #define ENCODE_BLOCKAGE(U, R) \ 00249 (((U) << BLOCKAGE_BITS \ 00250 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \ 00251 | MAX_BLOCKAGE_COST (R)) 00252 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS)) 00253 #define BLOCKAGE_RANGE(B) \ 00254 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \ 00255 | ((B) & BLOCKAGE_MASK)) 00256 00257 /* Encodings of the `<name>_unit_blockage_range' function. */ 00258 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2)) 00259 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1)) 00260 00261 extern FILE *sched_dump; 00262 extern int sched_verbose; 00263 00264 /* Exception Free Loads: 00265 00266 We define five classes of speculative loads: IFREE, IRISKY, 00267 PFREE, PRISKY, and MFREE. 00268 00269 IFREE loads are loads that are proved to be exception-free, just 00270 by examining the load insn. Examples for such loads are loads 00271 from TOC and loads of global data. 00272 00273 IRISKY loads are loads that are proved to be exception-risky, 00274 just by examining the load insn. Examples for such loads are 00275 volatile loads and loads from shared memory. 00276 00277 PFREE loads are loads for which we can prove, by examining other 00278 insns, that they are exception-free. Currently, this class consists 00279 of loads for which we are able to find a "similar load", either in 00280 the target block, or, if only one split-block exists, in that split 00281 block. Load2 is similar to load1 if both have same single base 00282 register. We identify only part of the similar loads, by finding 00283 an insn upon which both load1 and load2 have a DEF-USE dependence. 00284 00285 PRISKY loads are loads for which we can prove, by examining other 00286 insns, that they are exception-risky. Currently we have two proofs for 00287 such loads. The first proof detects loads that are probably guarded by a 00288 test on the memory address. This proof is based on the 00289 backward and forward data dependence information for the region. 00290 Let load-insn be the examined load. 00291 Load-insn is PRISKY iff ALL the following hold: 00292 00293 - insn1 is not in the same block as load-insn 00294 - there is a DEF-USE dependence chain (insn1, ..., load-insn) 00295 - test-insn is either a compare or a branch, not in the same block 00296 as load-insn 00297 - load-insn is reachable from test-insn 00298 - there is a DEF-USE dependence chain (insn1, ..., test-insn) 00299 00300 This proof might fail when the compare and the load are fed 00301 by an insn not in the region. To solve this, we will add to this 00302 group all loads that have no input DEF-USE dependence. 00303 00304 The second proof detects loads that are directly or indirectly 00305 fed by a speculative load. This proof is affected by the 00306 scheduling process. We will use the flag fed_by_spec_load. 00307 Initially, all insns have this flag reset. After a speculative 00308 motion of an insn, if insn is either a load, or marked as 00309 fed_by_spec_load, we will also mark as fed_by_spec_load every 00310 insn1 for which a DEF-USE dependence (insn, insn1) exists. A 00311 load which is fed_by_spec_load is also PRISKY. 00312 00313 MFREE (maybe-free) loads are all the remaining loads. They may be 00314 exception-free, but we cannot prove it. 00315 00316 Now, all loads in IFREE and PFREE classes are considered 00317 exception-free, while all loads in IRISKY and PRISKY classes are 00318 considered exception-risky. As for loads in the MFREE class, 00319 these are considered either exception-free or exception-risky, 00320 depending on whether we are pessimistic or optimistic. We have 00321 to take the pessimistic approach to assure the safety of 00322 speculative scheduling, but we can take the optimistic approach 00323 by invoking the -fsched_spec_load_dangerous option. */ 00324 00325 enum INSN_TRAP_CLASS 00326 { 00327 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2, 00328 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5 00329 }; 00330 00331 #define WORST_CLASS(class1, class2) \ 00332 ((class1 > class2) ? class1 : class2) 00333 00334 #ifndef __GNUC__ 00335 #define __inline 00336 #endif 00337 00338 #ifndef HAIFA_INLINE 00339 #define HAIFA_INLINE __inline 00340 #endif 00341 00342 /* Functions in sched-vis.c. */ 00343 extern void init_target_units PARAMS ((void)); 00344 extern void insn_print_units PARAMS ((rtx)); 00345 extern void init_block_visualization PARAMS ((void)); 00346 extern void print_block_visualization PARAMS ((const char *)); 00347 extern void visualize_scheduled_insns PARAMS ((int)); 00348 extern void visualize_no_unit PARAMS ((rtx)); 00349 extern void visualize_stall_cycles PARAMS ((int)); 00350 extern void visualize_alloc PARAMS ((void)); 00351 extern void visualize_free PARAMS ((void)); 00352 00353 /* Functions in sched-deps.c. */ 00354 extern int add_dependence PARAMS ((rtx, rtx, enum reg_note)); 00355 extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx, 00356 rtx)); 00357 extern void sched_analyze PARAMS ((struct deps *, rtx, rtx)); 00358 extern void init_deps PARAMS ((struct deps *)); 00359 extern void free_deps PARAMS ((struct deps *)); 00360 extern void init_deps_global PARAMS ((void)); 00361 extern void finish_deps_global PARAMS ((void)); 00362 extern void add_forward_dependence PARAMS ((rtx, rtx, enum reg_note)); 00363 extern void compute_forward_dependences PARAMS ((rtx, rtx)); 00364 extern rtx find_insn_list PARAMS ((rtx, rtx)); 00365 extern void init_dependency_caches PARAMS ((int)); 00366 extern void free_dependency_caches PARAMS ((void)); 00367 00368 /* Functions in haifa-sched.c. */ 00369 extern int haifa_classify_insn PARAMS ((rtx)); 00370 extern void get_block_head_tail PARAMS ((int, rtx *, rtx *)); 00371 extern int no_real_insns_p PARAMS ((rtx, rtx)); 00372 00373 extern void rm_line_notes PARAMS ((rtx, rtx)); 00374 extern void save_line_notes PARAMS ((int, rtx, rtx)); 00375 extern void restore_line_notes PARAMS ((rtx, rtx)); 00376 extern void rm_redundant_line_notes PARAMS ((void)); 00377 extern void rm_other_notes PARAMS ((rtx, rtx)); 00378 00379 extern int insn_issue_delay PARAMS ((rtx)); 00380 extern int set_priorities PARAMS ((rtx, rtx)); 00381 00382 extern rtx sched_emit_insn PARAMS ((rtx)); 00383 extern void schedule_block PARAMS ((int, int)); 00384 extern void sched_init PARAMS ((FILE *)); 00385 extern void sched_finish PARAMS ((void)); 00386 00387 extern void ready_add PARAMS ((struct ready_list *, rtx)); 00388 00389 /* The following are exported for the benefit of debugging functions. It 00390 would be nicer to keep them private to haifa-sched.c. */ 00391 extern int insn_unit PARAMS ((rtx)); 00392 extern int insn_cost PARAMS ((rtx, rtx, rtx)); 00393 extern rtx get_unit_last_insn PARAMS ((int)); 00394 extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int)); 00395 extern void print_insn PARAMS ((char *, rtx, int));
1.5.6