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