00001 /* Loop optimization definitions for GNU C-Compiler 00002 Copyright (C) 1991, 1995, 1998, 1999, 2000, 2001, 2002 00003 Free Software Foundation, Inc. 00004 00005 This file is part of GCC. 00006 00007 GCC is free software; you can redistribute it and/or modify it under 00008 the terms of the GNU General Public License as published by the Free 00009 Software Foundation; either version 2, or (at your option) any later 00010 version. 00011 00012 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 00013 WARRANTY; without even the implied warranty of MERCHANTABILITY or 00014 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 00015 for more details. 00016 00017 You should have received a copy of the GNU General Public License 00018 along with GCC; see the file COPYING. If not, write to the Free 00019 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 00020 02111-1307, USA. */ 00021 00022 #include "bitmap.h" 00023 #include "sbitmap.h" 00024 #include "hard-reg-set.h" 00025 #include "basic-block.h" 00026 00027 /* Flags passed to loop_optimize. */ 00028 #define LOOP_UNROLL 1 00029 #define LOOP_BCT 2 00030 #define LOOP_PREFETCH 4 00031 #define LOOP_AUTO_UNROLL 8 00032 00033 /* Get the loop info pointer of a loop. */ 00034 #define LOOP_INFO(LOOP) ((struct loop_info *) (LOOP)->aux) 00035 00036 /* Get a pointer to the loop movables structure. */ 00037 #define LOOP_MOVABLES(LOOP) (&LOOP_INFO (LOOP)->movables) 00038 00039 /* Get a pointer to the loop registers structure. */ 00040 #define LOOP_REGS(LOOP) (&LOOP_INFO (LOOP)->regs) 00041 00042 /* Get a pointer to the loop induction variables structure. */ 00043 #define LOOP_IVS(LOOP) (&LOOP_INFO (LOOP)->ivs) 00044 00045 /* Get the luid of an insn. Catch the error of trying to reference the LUID 00046 of an insn added during loop, since these don't have LUIDs. */ 00047 00048 #define INSN_LUID(INSN) \ 00049 (INSN_UID (INSN) < max_uid_for_loop ? uid_luid[INSN_UID (INSN)] \ 00050 : (abort (), -1)) 00051 00052 #define REGNO_FIRST_LUID(REGNO) uid_luid[REGNO_FIRST_UID (REGNO)] 00053 #define REGNO_LAST_LUID(REGNO) uid_luid[REGNO_LAST_UID (REGNO)] 00054 00055 00056 /* A "basic induction variable" or biv is a pseudo reg that is set 00057 (within this loop) only by incrementing or decrementing it. */ 00058 /* A "general induction variable" or giv is a pseudo reg whose 00059 value is a linear function of a biv. */ 00060 00061 /* Bivs are recognized by `basic_induction_var'; 00062 Givs by `general_induction_var'. */ 00063 00064 /* An enum for the two different types of givs, those that are used 00065 as memory addresses and those that are calculated into registers. */ 00066 enum g_types 00067 { 00068 DEST_ADDR, 00069 DEST_REG 00070 }; 00071 00072 00073 /* A `struct induction' is created for every instruction that sets 00074 an induction variable (either a biv or a giv). */ 00075 00076 struct induction 00077 { 00078 rtx insn; /* The insn that sets a biv or giv */ 00079 rtx new_reg; /* New register, containing strength reduced 00080 version of this giv. */ 00081 rtx src_reg; /* Biv from which this giv is computed. 00082 (If this is a biv, then this is the biv.) */ 00083 enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG */ 00084 rtx dest_reg; /* Destination register for insn: this is the 00085 register which was the biv or giv. 00086 For a biv, this equals src_reg. 00087 For a DEST_ADDR type giv, this is 0. */ 00088 rtx *location; /* Place in the insn where this giv occurs. 00089 If GIV_TYPE is DEST_REG, this is 0. */ 00090 /* For a biv, this is the place where add_val 00091 was found. */ 00092 enum machine_mode mode; /* The mode of this biv or giv */ 00093 rtx mem; /* For DEST_ADDR, the memory object. */ 00094 rtx mult_val; /* Multiplicative factor for src_reg. */ 00095 rtx add_val; /* Additive constant for that product. */ 00096 int benefit; /* Gain from eliminating this insn. */ 00097 rtx final_value; /* If the giv is used outside the loop, and its 00098 final value could be calculated, it is put 00099 here, and the giv is made replaceable. Set 00100 the giv to this value before the loop. */ 00101 unsigned combined_with; /* The number of givs this giv has been 00102 combined with. If nonzero, this giv 00103 cannot combine with any other giv. */ 00104 unsigned replaceable : 1; /* 1 if we can substitute the strength-reduced 00105 variable for the original variable. 00106 0 means they must be kept separate and the 00107 new one must be copied into the old pseudo 00108 reg each time the old one is set. */ 00109 unsigned not_replaceable : 1; /* Used to prevent duplicating work. This is 00110 1 if we know that the giv definitely can 00111 not be made replaceable, in which case we 00112 don't bother checking the variable again 00113 even if further info is available. 00114 Both this and the above can be zero. */ 00115 unsigned ignore : 1; /* 1 prohibits further processing of giv */ 00116 unsigned always_computable : 1;/* 1 if this value is computable every 00117 iteration. */ 00118 unsigned always_executed : 1; /* 1 if this set occurs each iteration. */ 00119 unsigned maybe_multiple : 1; /* Only used for a biv and 1 if this biv 00120 update may be done multiple times per 00121 iteration. */ 00122 unsigned cant_derive : 1; /* For giv's, 1 if this giv cannot derive 00123 another giv. This occurs in many cases 00124 where a giv's lifetime spans an update to 00125 a biv. */ 00126 unsigned maybe_dead : 1; /* 1 if this giv might be dead. In that case, 00127 we won't use it to eliminate a biv, it 00128 would probably lose. */ 00129 unsigned auto_inc_opt : 1; /* 1 if this giv had its increment output next 00130 to it to try to form an auto-inc address. */ 00131 unsigned unrolled : 1; /* 1 if new register has been allocated and 00132 initialized in unrolled loop. */ 00133 unsigned shared : 1; 00134 unsigned no_const_addval : 1; /* 1 if add_val does not contain a const. */ 00135 int lifetime; /* Length of life of this giv */ 00136 rtx derive_adjustment; /* If nonzero, is an adjustment to be 00137 subtracted from add_val when this giv 00138 derives another. This occurs when the 00139 giv spans a biv update by incrementation. */ 00140 rtx ext_dependent; /* If nonzero, is a sign or zero extension 00141 if a biv on which this giv is dependent. */ 00142 struct induction *next_iv; /* For givs, links together all givs that are 00143 based on the same biv. For bivs, links 00144 together all biv entries that refer to the 00145 same biv register. */ 00146 struct induction *same; /* If this giv has been combined with another 00147 giv, this points to the base giv. The base 00148 giv will have COMBINED_WITH nonzero. */ 00149 HOST_WIDE_INT const_adjust; /* Used by loop unrolling, when an address giv 00150 is split, and a constant is eliminated from 00151 the address, the -constant is stored here 00152 for later use. */ 00153 struct induction *same_insn; /* If there are multiple identical givs in 00154 the same insn, then all but one have this 00155 field set, and they all point to the giv 00156 that doesn't have this field set. */ 00157 rtx last_use; /* For a giv made from a biv increment, this is 00158 a substitute for the lifetime information. */ 00159 }; 00160 00161 00162 /* A `struct iv_class' is created for each biv. */ 00163 00164 struct iv_class 00165 { 00166 unsigned int regno; /* Pseudo reg which is the biv. */ 00167 int biv_count; /* Number of insns setting this reg. */ 00168 struct induction *biv; /* List of all insns that set this reg. */ 00169 int giv_count; /* Number of DEST_REG givs computed from this 00170 biv. The resulting count is only used in 00171 check_dbra_loop. */ 00172 struct induction *giv; /* List of all insns that compute a giv 00173 from this reg. */ 00174 int total_benefit; /* Sum of BENEFITs of all those givs. */ 00175 rtx initial_value; /* Value of reg at loop start. */ 00176 rtx initial_test; /* Test performed on BIV before loop. */ 00177 rtx final_value; /* Value of reg at loop end, if known. */ 00178 struct iv_class *next; /* Links all class structures together. */ 00179 rtx init_insn; /* insn which initializes biv, 0 if none. */ 00180 rtx init_set; /* SET of INIT_INSN, if any. */ 00181 unsigned incremented : 1; /* 1 if somewhere incremented/decremented */ 00182 unsigned eliminable : 1; /* 1 if plausible candidate for 00183 elimination. */ 00184 unsigned nonneg : 1; /* 1 if we added a REG_NONNEG note for 00185 this. */ 00186 unsigned reversed : 1; /* 1 if we reversed the loop that this 00187 biv controls. */ 00188 unsigned all_reduced : 1; /* 1 if all givs using this biv have 00189 been reduced. */ 00190 }; 00191 00192 00193 /* Definitions used by the basic induction variable discovery code. */ 00194 enum iv_mode 00195 { 00196 UNKNOWN_INDUCT, 00197 BASIC_INDUCT, 00198 NOT_BASIC_INDUCT, 00199 GENERAL_INDUCT 00200 }; 00201 00202 00203 /* A `struct iv' is created for every register. */ 00204 00205 struct iv 00206 { 00207 enum iv_mode type; 00208 union 00209 { 00210 struct iv_class *class; 00211 struct induction *info; 00212 } iv; 00213 }; 00214 00215 00216 #define REG_IV_TYPE(ivs, n) ivs->regs[n].type 00217 #define REG_IV_INFO(ivs, n) ivs->regs[n].iv.info 00218 #define REG_IV_CLASS(ivs, n) ivs->regs[n].iv.class 00219 00220 00221 struct loop_ivs 00222 { 00223 /* Indexed by register number, contains pointer to `struct 00224 iv' if register is an induction variable. */ 00225 struct iv *regs; 00226 00227 /* Size of regs array. */ 00228 unsigned int n_regs; 00229 00230 /* The head of a list which links together (via the next field) 00231 every iv class for the current loop. */ 00232 struct iv_class *list; 00233 }; 00234 00235 00236 typedef struct loop_mem_info 00237 { 00238 rtx mem; /* The MEM itself. */ 00239 rtx reg; /* Corresponding pseudo, if any. */ 00240 int optimize; /* Nonzero if we can optimize access to this MEM. */ 00241 } loop_mem_info; 00242 00243 00244 00245 struct loop_reg 00246 { 00247 /* Number of times the reg is set during the loop being scanned. 00248 During code motion, a negative value indicates a reg that has 00249 been made a candidate; in particular -2 means that it is an 00250 candidate that we know is equal to a constant and -1 means that 00251 it is a candidate not known equal to a constant. After code 00252 motion, regs moved have 0 (which is accurate now) while the 00253 failed candidates have the original number of times set. 00254 00255 Therefore, at all times, == 0 indicates an invariant register; 00256 < 0 a conditionally invariant one. */ 00257 int set_in_loop; 00258 00259 /* Original value of set_in_loop; same except that this value 00260 is not set negative for a reg whose sets have been made candidates 00261 and not set to 0 for a reg that is moved. */ 00262 int n_times_set; 00263 00264 /* Contains the insn in which a register was used if it was used 00265 exactly once; contains const0_rtx if it was used more than once. */ 00266 rtx single_usage; 00267 00268 /* Nonzero indicates that the register cannot be moved or strength 00269 reduced. */ 00270 char may_not_optimize; 00271 00272 /* Nonzero means reg N has already been moved out of one loop. 00273 This reduces the desire to move it out of another. */ 00274 char moved_once; 00275 }; 00276 00277 00278 struct loop_regs 00279 { 00280 int num; /* Number of regs used in table. */ 00281 int size; /* Size of table. */ 00282 struct loop_reg *array; /* Register usage info. array. */ 00283 int multiple_uses; /* Nonzero if a reg has multiple uses. */ 00284 }; 00285 00286 00287 00288 struct loop_movables 00289 { 00290 /* Head of movable chain. */ 00291 struct movable *head; 00292 /* Last movable in chain. */ 00293 struct movable *last; 00294 }; 00295 00296 00297 /* Information pertaining to a loop. */ 00298 00299 struct loop_info 00300 { 00301 /* Nonzero if there is a subroutine call in the current loop. */ 00302 int has_call; 00303 /* Nonzero if there is a libcall in the current loop. */ 00304 int has_libcall; 00305 /* Nonzero if there is a non constant call in the current loop. */ 00306 int has_nonconst_call; 00307 /* Nonzero if there is a prefetch instruction in the current loop. */ 00308 int has_prefetch; 00309 /* Nonzero if there is a volatile memory reference in the current 00310 loop. */ 00311 int has_volatile; 00312 /* Nonzero if there is a tablejump in the current loop. */ 00313 int has_tablejump; 00314 /* Nonzero if there are ways to leave the loop other than falling 00315 off the end. */ 00316 int has_multiple_exit_targets; 00317 /* Nonzero if there is an indirect jump in the current function. */ 00318 int has_indirect_jump; 00319 /* Whether loop unrolling has emitted copies of the loop body so 00320 that the main loop needs no exit tests. */ 00321 int preconditioned; 00322 /* Register or constant initial loop value. */ 00323 rtx initial_value; 00324 /* Register or constant value used for comparison test. */ 00325 rtx comparison_value; 00326 /* Register or constant approximate final value. */ 00327 rtx final_value; 00328 /* Register or constant initial loop value with term common to 00329 final_value removed. */ 00330 rtx initial_equiv_value; 00331 /* Register or constant final loop value with term common to 00332 initial_value removed. */ 00333 rtx final_equiv_value; 00334 /* Register corresponding to iteration variable. */ 00335 rtx iteration_var; 00336 /* Constant loop increment. */ 00337 rtx increment; 00338 enum rtx_code comparison_code; 00339 /* Holds the number of loop iterations. It is zero if the number 00340 could not be calculated. Must be unsigned since the number of 00341 iterations can be as high as 2^wordsize - 1. For loops with a 00342 wider iterator, this number will be zero if the number of loop 00343 iterations is too large for an unsigned integer to hold. */ 00344 unsigned HOST_WIDE_INT n_iterations; 00345 /* The number of times the loop body was unrolled. */ 00346 unsigned int unroll_number; 00347 int used_count_register; 00348 /* The loop iterator induction variable. */ 00349 struct iv_class *iv; 00350 /* List of MEMs that are stored in this loop. */ 00351 rtx store_mems; 00352 /* Array of MEMs that are used (read or written) in this loop, but 00353 cannot be aliased by anything in this loop, except perhaps 00354 themselves. In other words, if mems[i] is altered during 00355 the loop, it is altered by an expression that is rtx_equal_p to 00356 it. */ 00357 loop_mem_info *mems; 00358 /* The index of the next available slot in MEMS. */ 00359 int mems_idx; 00360 /* The number of elements allocated in MEMS. */ 00361 int mems_allocated; 00362 /* Nonzero if we don't know what MEMs were changed in the current 00363 loop. This happens if the loop contains a call (in which case 00364 `has_call' will also be set) or if we store into more than 00365 NUM_STORES MEMs. */ 00366 int unknown_address_altered; 00367 /* The above doesn't count any readonly memory locations that are 00368 stored. This does. */ 00369 int unknown_constant_address_altered; 00370 /* Count of memory write instructions discovered in the loop. */ 00371 int num_mem_sets; 00372 /* The insn where the first of these was found. */ 00373 rtx first_loop_store_insn; 00374 /* The chain of movable insns in loop. */ 00375 struct loop_movables movables; 00376 /* The registers used the in loop. */ 00377 struct loop_regs regs; 00378 /* The induction variable information in loop. */ 00379 struct loop_ivs ivs; 00380 /* Nonzero if call is in pre_header extended basic block. */ 00381 int pre_header_has_call; 00382 }; 00383 00384 00385 /* Variables declared in loop.c, but also needed in unroll.c. */ 00386 00387 extern int *uid_luid; 00388 extern int max_uid_for_loop; 00389 extern unsigned int max_reg_before_loop; 00390 extern struct loop **uid_loop; 00391 extern FILE *loop_dump_stream; 00392 00393 00394 /* Forward declarations for non-static functions declared in loop.c and 00395 unroll.c. */ 00396 int loop_invariant_p PARAMS ((const struct loop *, rtx)); 00397 rtx get_condition_for_loop PARAMS ((const struct loop *, rtx)); 00398 void loop_iv_add_mult_hoist PARAMS ((const struct loop *, rtx, rtx, rtx, rtx)); 00399 void loop_iv_add_mult_sink PARAMS ((const struct loop *, rtx, rtx, rtx, rtx)); 00400 void loop_iv_add_mult_emit_before PARAMS ((const struct loop *, rtx, 00401 rtx, rtx, rtx, 00402 basic_block, rtx)); 00403 rtx express_from PARAMS ((struct induction *, struct induction *)); 00404 rtx extend_value_for_giv PARAMS ((struct induction *, rtx)); 00405 00406 void unroll_loop PARAMS ((struct loop *, int, int)); 00407 rtx biv_total_increment PARAMS ((const struct iv_class *)); 00408 unsigned HOST_WIDE_INT loop_iterations PARAMS ((struct loop *)); 00409 int precondition_loop_p PARAMS ((const struct loop *, 00410 rtx *, rtx *, rtx *, 00411 enum machine_mode *mode)); 00412 rtx final_biv_value PARAMS ((const struct loop *, struct iv_class *)); 00413 rtx final_giv_value PARAMS ((const struct loop *, struct induction *)); 00414 void emit_unrolled_add PARAMS ((rtx, rtx, rtx)); 00415 int back_branch_in_range_p PARAMS ((const struct loop *, rtx)); 00416 00417 int loop_insn_first_p PARAMS ((rtx, rtx)); 00418 typedef rtx (*loop_insn_callback) PARAMS ((struct loop *, rtx, int, int)); 00419 void for_each_insn_in_loop PARAMS ((struct loop *, loop_insn_callback)); 00420 rtx loop_insn_emit_before PARAMS((const struct loop *, basic_block, 00421 rtx, rtx)); 00422 rtx loop_insn_sink PARAMS((const struct loop *, rtx)); 00423 rtx loop_insn_hoist PARAMS((const struct loop *, rtx)); 00424 00425 /* Forward declarations for non-static functions declared in doloop.c. */ 00426 int doloop_optimize PARAMS ((const struct loop *));
1.5.6