1 /* Loop optimization definitions for GCC 2 Copyright (C) 1991, 1995, 1998, 1999, 2000, 2001, 2002, 2003, 2004 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 2, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING. If not, write to the Free 19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 20 02111-1307, USA. */ 21 22 #include "bitmap.h" 23 #include "sbitmap.h" 24 #include "hard-reg-set.h" 25 #include "basic-block.h" 26 27 /* Flags passed to loop_optimize. */ 28 #define LOOP_UNROLL 1 29 #define LOOP_BCT 2 30 #define LOOP_PREFETCH 4 31 #define LOOP_AUTO_UNROLL 8 32 33 /* Get the loop info pointer of a loop. */ 34 #define LOOP_INFO(LOOP) ((struct loop_info *) (LOOP)->aux) 35 36 /* Get a pointer to the loop movables structure. */ 37 #define LOOP_MOVABLES(LOOP) (&LOOP_INFO (LOOP)->movables) 38 39 /* Get a pointer to the loop registers structure. */ 40 #define LOOP_REGS(LOOP) (&LOOP_INFO (LOOP)->regs) 41 42 /* Get a pointer to the loop induction variables structure. */ 43 #define LOOP_IVS(LOOP) (&LOOP_INFO (LOOP)->ivs) 44 45 /* Get the luid of an insn. Catch the error of trying to reference the LUID 46 of an insn added during loop, since these don't have LUIDs. */ 47 48 #define INSN_LUID(INSN) \ 49 (INSN_UID (INSN) < max_uid_for_loop ? uid_luid[INSN_UID (INSN)] \ 50 : (abort (), -1)) 51 52 #define REGNO_FIRST_LUID(REGNO) \ 53 (REGNO_FIRST_UID (REGNO) < max_uid_for_loop \ 54 ? uid_luid[REGNO_FIRST_UID (REGNO)] \ 55 : 0) 56 #define REGNO_LAST_LUID(REGNO) \ 57 (REGNO_LAST_UID (REGNO) < max_uid_for_loop \ 58 ? uid_luid[REGNO_LAST_UID (REGNO)] \ 59 : INT_MAX) 60 61 /* A "basic induction variable" or biv is a pseudo reg that is set 62 (within this loop) only by incrementing or decrementing it. */ 63 /* A "general induction variable" or giv is a pseudo reg whose 64 value is a linear function of a biv. */ 65 66 /* Bivs are recognized by `basic_induction_var'; 67 Givs by `general_induction_var'. */ 68 69 /* An enum for the two different types of givs, those that are used 70 as memory addresses and those that are calculated into registers. */ 71 enum g_types 72 { 73 DEST_ADDR, 74 DEST_REG 75 }; 76 77 78 /* A `struct induction' is created for every instruction that sets 79 an induction variable (either a biv or a giv). */ 80 81 struct induction 82 { 83 rtx insn; /* The insn that sets a biv or giv */ 84 rtx new_reg; /* New register, containing strength reduced 85 version of this giv. */ 86 rtx src_reg; /* Biv from which this giv is computed. 87 (If this is a biv, then this is the biv.) */ 88 enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG */ 89 rtx dest_reg; /* Destination register for insn: this is the 90 register which was the biv or giv. 91 For a biv, this equals src_reg. 92 For a DEST_ADDR type giv, this is 0. */ 93 rtx *location; /* Place in the insn where this giv occurs. 94 If GIV_TYPE is DEST_REG, this is 0. */ 95 /* For a biv, this is the place where add_val 96 was found. */ 97 enum machine_mode mode; /* The mode of this biv or giv */ 98 rtx mem; /* For DEST_ADDR, the memory object. */ 99 rtx mult_val; /* Multiplicative factor for src_reg. */ 100 rtx add_val; /* Additive constant for that product. */ 101 int benefit; /* Gain from eliminating this insn. */ 102 rtx final_value; /* If the giv is used outside the loop, and its 103 final value could be calculated, it is put 104 here, and the giv is made replaceable. Set 105 the giv to this value before the loop. */ 106 unsigned combined_with; /* The number of givs this giv has been 107 combined with. If nonzero, this giv 108 cannot combine with any other giv. */ 109 unsigned replaceable : 1; /* 1 if we can substitute the strength-reduced 110 variable for the original variable. 111 0 means they must be kept separate and the 112 new one must be copied into the old pseudo 113 reg each time the old one is set. */ 114 unsigned not_replaceable : 1; /* Used to prevent duplicating work. This is 115 1 if we know that the giv definitely can 116 not be made replaceable, in which case we 117 don't bother checking the variable again 118 even if further info is available. 119 Both this and the above can be zero. */ 120 unsigned ignore : 1; /* 1 prohibits further processing of giv */ 121 unsigned always_computable : 1;/* 1 if this value is computable every 122 iteration. */ 123 unsigned always_executed : 1; /* 1 if this set occurs each iteration. */ 124 unsigned maybe_multiple : 1; /* Only used for a biv and 1 if this biv 125 update may be done multiple times per 126 iteration. */ 127 unsigned cant_derive : 1; /* For giv's, 1 if this giv cannot derive 128 another giv. This occurs in many cases 129 where a giv's lifetime spans an update to 130 a biv. */ 131 unsigned maybe_dead : 1; /* 1 if this giv might be dead. In that case, 132 we won't use it to eliminate a biv, it 133 would probably lose. */ 134 unsigned auto_inc_opt : 1; /* 1 if this giv had its increment output next 135 to it to try to form an auto-inc address. */ 136 unsigned unrolled : 1; /* 1 if new register has been allocated and 137 initialized in unrolled loop. */ 138 unsigned shared : 1; 139 unsigned no_const_addval : 1; /* 1 if add_val does not contain a const. */ 140 int lifetime; /* Length of life of this giv */ 141 rtx derive_adjustment; /* If nonzero, is an adjustment to be 142 subtracted from add_val when this giv 143 derives another. This occurs when the 144 giv spans a biv update by incrementation. */ 145 rtx ext_dependent; /* If nonzero, is a sign or zero extension 146 if a biv on which this giv is dependent. */ 147 struct induction *next_iv; /* For givs, links together all givs that are 148 based on the same biv. For bivs, links 149 together all biv entries that refer to the 150 same biv register. */ 151 struct induction *same; /* For givs, if the giv has been combined with 152 another giv, this points to the base giv. 153 The base giv will have COMBINED_WITH nonzero. 154 For bivs, if the biv has the same LOCATION 155 than another biv, this points to the base 156 biv. */ 157 HOST_WIDE_INT const_adjust; /* Used by loop unrolling, when an address giv 158 is split, and a constant is eliminated from 159 the address, the -constant is stored here 160 for later use. */ 161 struct induction *same_insn; /* If there are multiple identical givs in 162 the same insn, then all but one have this 163 field set, and they all point to the giv 164 that doesn't have this field set. */ 165 rtx last_use; /* For a giv made from a biv increment, this is 166 a substitute for the lifetime information. */ 167 }; 168 169 170 /* A `struct iv_class' is created for each biv. */ 171 172 struct iv_class 173 { 174 unsigned int regno; /* Pseudo reg which is the biv. */ 175 int biv_count; /* Number of insns setting this reg. */ 176 struct induction *biv; /* List of all insns that set this reg. */ 177 int giv_count; /* Number of DEST_REG givs computed from this 178 biv. The resulting count is only used in 179 check_dbra_loop. */ 180 struct induction *giv; /* List of all insns that compute a giv 181 from this reg. */ 182 int total_benefit; /* Sum of BENEFITs of all those givs. */ 183 rtx initial_value; /* Value of reg at loop start. */ 184 rtx initial_test; /* Test performed on BIV before loop. */ 185 rtx final_value; /* Value of reg at loop end, if known. */ 186 struct iv_class *next; /* Links all class structures together. */ 187 rtx init_insn; /* insn which initializes biv, 0 if none. */ 188 rtx init_set; /* SET of INIT_INSN, if any. */ 189 unsigned incremented : 1; /* 1 if somewhere incremented/decremented */ 190 unsigned eliminable : 1; /* 1 if plausible candidate for 191 elimination. */ 192 unsigned nonneg : 1; /* 1 if we added a REG_NONNEG note for 193 this. */ 194 unsigned reversed : 1; /* 1 if we reversed the loop that this 195 biv controls. */ 196 unsigned all_reduced : 1; /* 1 if all givs using this biv have 197 been reduced. */ 198 }; 199 200 201 /* Definitions used by the basic induction variable discovery code. */ 202 enum iv_mode 203 { 204 UNKNOWN_INDUCT, 205 BASIC_INDUCT, 206 NOT_BASIC_INDUCT, 207 GENERAL_INDUCT 208 }; 209 210 211 /* A `struct iv' is created for every register. */ 212 213 struct iv 214 { 215 enum iv_mode type; 216 union 217 { 218 struct iv_class *class; 219 struct induction *info; 220 } iv; 221 }; 222 223 224 #define REG_IV_TYPE(ivs, n) ivs->regs[n].type 225 #define REG_IV_INFO(ivs, n) ivs->regs[n].iv.info 226 #define REG_IV_CLASS(ivs, n) ivs->regs[n].iv.class 227 228 229 struct loop_ivs 230 { 231 /* Indexed by register number, contains pointer to `struct 232 iv' if register is an induction variable. */ 233 struct iv *regs; 234 235 /* Size of regs array. */ 236 unsigned int n_regs; 237 238 /* The head of a list which links together (via the next field) 239 every iv class for the current loop. */ 240 struct iv_class *list; 241 }; 242 243 244 typedef struct loop_mem_info 245 { 246 rtx mem; /* The MEM itself. */ 247 rtx reg; /* Corresponding pseudo, if any. */ 248 int optimize; /* Nonzero if we can optimize access to this MEM. */ 249 } loop_mem_info; 250 251 252 253 struct loop_reg 254 { 255 /* Number of times the reg is set during the loop being scanned. 256 During code motion, a negative value indicates a reg that has 257 been made a candidate; in particular -2 means that it is an 258 candidate that we know is equal to a constant and -1 means that 259 it is a candidate not known equal to a constant. After code 260 motion, regs moved have 0 (which is accurate now) while the 261 failed candidates have the original number of times set. 262 263 Therefore, at all times, == 0 indicates an invariant register; 264 < 0 a conditionally invariant one. */ 265 int set_in_loop; 266 267 /* Original value of set_in_loop; same except that this value 268 is not set negative for a reg whose sets have been made candidates 269 and not set to 0 for a reg that is moved. */ 270 int n_times_set; 271 272 /* Contains the insn in which a register was used if it was used 273 exactly once; contains const0_rtx if it was used more than once. */ 274 rtx single_usage; 275 276 /* Nonzero indicates that the register cannot be moved or strength 277 reduced. */ 278 char may_not_optimize; 279 280 /* Nonzero means reg N has already been moved out of one loop. 281 This reduces the desire to move it out of another. */ 282 char moved_once; 283 }; 284 285 286 struct loop_regs 287 { 288 int num; /* Number of regs used in table. */ 289 int size; /* Size of table. */ 290 struct loop_reg *array; /* Register usage info. array. */ 291 int multiple_uses; /* Nonzero if a reg has multiple uses. */ 292 }; 293 294 295 296 struct loop_movables 297 { 298 /* Head of movable chain. */ 299 struct movable *head; 300 /* Last movable in chain. */ 301 struct movable *last; 302 }; 303 304 305 /* Information pertaining to a loop. */ 306 307 struct loop_info 308 { 309 /* Nonzero if there is a subroutine call in the current loop. */ 310 int has_call; 311 /* Nonzero if there is a libcall in the current loop. */ 312 int has_libcall; 313 /* Nonzero if there is a non constant call in the current loop. */ 314 int has_nonconst_call; 315 /* Nonzero if there is a prefetch instruction in the current loop. */ 316 int has_prefetch; 317 /* Nonzero if there is a volatile memory reference in the current 318 loop. */ 319 int has_volatile; 320 /* Nonzero if there is a tablejump in the current loop. */ 321 int has_tablejump; 322 /* Nonzero if there are ways to leave the loop other than falling 323 off the end. */ 324 int has_multiple_exit_targets; 325 /* Nonzero if there is an indirect jump in the current function. */ 326 int has_indirect_jump; 327 /* Whether loop unrolling has emitted copies of the loop body so 328 that the main loop needs no exit tests. */ 329 int preconditioned; 330 /* Register or constant initial loop value. */ 331 rtx initial_value; 332 /* Register or constant value used for comparison test. */ 333 rtx comparison_value; 334 /* Register or constant approximate final value. */ 335 rtx final_value; 336 /* Register or constant initial loop value with term common to 337 final_value removed. */ 338 rtx initial_equiv_value; 339 /* Register or constant final loop value with term common to 340 initial_value removed. */ 341 rtx final_equiv_value; 342 /* Register corresponding to iteration variable. */ 343 rtx iteration_var; 344 /* Constant loop increment. */ 345 rtx increment; 346 enum rtx_code comparison_code; 347 /* Holds the number of loop iterations. It is zero if the number 348 could not be calculated. Must be unsigned since the number of 349 iterations can be as high as 2^wordsize - 1. For loops with a 350 wider iterator, this number will be zero if the number of loop 351 iterations is too large for an unsigned integer to hold. */ 352 unsigned HOST_WIDE_INT n_iterations; 353 /* The number of times the loop body was unrolled. */ 354 unsigned int unroll_number; 355 int used_count_register; 356 /* The loop iterator induction variable. */ 357 struct iv_class *iv; 358 /* List of MEMs that are stored in this loop. */ 359 rtx store_mems; 360 /* Array of MEMs that are used (read or written) in this loop, but 361 cannot be aliased by anything in this loop, except perhaps 362 themselves. In other words, if mems[i] is altered during 363 the loop, it is altered by an expression that is rtx_equal_p to 364 it. */ 365 loop_mem_info *mems; 366 /* The index of the next available slot in MEMS. */ 367 int mems_idx; 368 /* The number of elements allocated in MEMS. */ 369 int mems_allocated; 370 /* Nonzero if we don't know what MEMs were changed in the current 371 loop. This happens if the loop contains a call (in which case 372 `has_call' will also be set) or if we store into more than 373 NUM_STORES MEMs. */ 374 int unknown_address_altered; 375 /* The above doesn't count any readonly memory locations that are 376 stored. This does. */ 377 int unknown_constant_address_altered; 378 /* Count of memory write instructions discovered in the loop. */ 379 int num_mem_sets; 380 /* The insn where the first of these was found. */ 381 rtx first_loop_store_insn; 382 /* The chain of movable insns in loop. */ 383 struct loop_movables movables; 384 /* The registers used the in loop. */ 385 struct loop_regs regs; 386 /* The induction variable information in loop. */ 387 struct loop_ivs ivs; 388 /* Nonzero if call is in pre_header extended basic block. */ 389 int pre_header_has_call; 390 }; 391 392 393 /* Variables declared in loop.c, but also needed in unroll.c. */ 394 395 extern int *uid_luid; 396 extern int max_uid_for_loop; 397 extern unsigned int max_reg_before_loop; 398 extern struct loop **uid_loop; 399 extern FILE *loop_dump_stream; 400 401 402 /* Forward declarations for non-static functions declared in loop.c and 403 unroll.c. */ 404 extern int loop_invariant_p (const struct loop *, rtx); 405 extern rtx get_condition_for_loop (const struct loop *, rtx); 406 extern void loop_iv_add_mult_hoist (const struct loop *, rtx, rtx, rtx, rtx); 407 extern void loop_iv_add_mult_sink (const struct loop *, rtx, rtx, rtx, rtx); 408 extern void loop_iv_add_mult_emit_before (const struct loop *, rtx, rtx, 409 rtx, rtx, basic_block, rtx); 410 extern rtx express_from (struct induction *, struct induction *); 411 extern rtx extend_value_for_giv (struct induction *, rtx); 412 413 extern void unroll_loop (struct loop *, int, int); 414 extern rtx biv_total_increment (const struct iv_class *); 415 extern unsigned HOST_WIDE_INT loop_iterations (struct loop *); 416 extern int precondition_loop_p (const struct loop *, rtx *, rtx *, rtx *, 417 enum machine_mode *mode); 418 extern rtx final_biv_value (const struct loop *, struct iv_class *); 419 extern rtx final_giv_value (const struct loop *, struct induction *); 420 extern void emit_unrolled_add (rtx, rtx, rtx); 421 extern int back_branch_in_range_p (const struct loop *, rtx); 422 423 extern int loop_insn_first_p (rtx, rtx); 424 typedef rtx (*loop_insn_callback) (struct loop *, rtx, int, int); 425 extern void for_each_insn_in_loop (struct loop *, loop_insn_callback); 426 extern rtx loop_insn_emit_before (const struct loop *, basic_block, rtx, rtx); 427 extern rtx loop_insn_sink (const struct loop *, rtx); 428 extern rtx loop_insn_hoist (const struct loop *, rtx); 429 430 /* Forward declarations for non-static functions declared in doloop.c. */ 431 extern rtx doloop_condition_get (rtx); 432 extern int doloop_optimize (const struct loop *); 433