[8833] | 1 | /* Loop optimization definitions for GNU C-Compiler |
---|
| 2 | Copyright (C) 1991, 1995 Free Software Foundation, Inc. |
---|
| 3 | |
---|
| 4 | This file is part of GNU CC. |
---|
| 5 | |
---|
| 6 | GNU CC is free software; you can redistribute it and/or modify |
---|
| 7 | it under the terms of the GNU General Public License as published by |
---|
| 8 | the Free Software Foundation; either version 2, or (at your option) |
---|
| 9 | any later version. |
---|
| 10 | |
---|
| 11 | GNU CC is distributed in the hope that it will be useful, |
---|
| 12 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
| 14 | GNU General Public License for more details. |
---|
| 15 | |
---|
| 16 | You should have received a copy of the GNU General Public License |
---|
| 17 | along with GNU CC; see the file COPYING. If not, write to |
---|
| 18 | the Free Software Foundation, 59 Temple Place - Suite 330, |
---|
| 19 | Boston, MA 02111-1307, USA. */ |
---|
| 20 | |
---|
| 21 | /* Get the luid of an insn. Catch the error of trying to reference the LUID |
---|
| 22 | of an insn added during loop, since these don't have LUIDs. */ |
---|
| 23 | |
---|
| 24 | #define INSN_LUID(INSN) \ |
---|
| 25 | (INSN_UID (INSN) < max_uid_for_loop ? uid_luid[INSN_UID (INSN)] \ |
---|
| 26 | : (abort (), -1)) |
---|
| 27 | |
---|
| 28 | /* A "basic induction variable" or biv is a pseudo reg that is set |
---|
| 29 | (within this loop) only by incrementing or decrementing it. */ |
---|
| 30 | /* A "general induction variable" or giv is a pseudo reg whose |
---|
| 31 | value is a linear function of a biv. */ |
---|
| 32 | |
---|
| 33 | /* Bivs are recognized by `basic_induction_var'; |
---|
| 34 | Givs by `general_induct_var'. */ |
---|
| 35 | |
---|
| 36 | /* An enum for the two different types of givs, those that are used |
---|
| 37 | as memory addresses and those that are calculated into registers. */ |
---|
| 38 | enum g_types { DEST_ADDR, DEST_REG }; |
---|
| 39 | |
---|
| 40 | /* A `struct induction' is created for every instruction that sets |
---|
| 41 | an induction variable (either a biv or a giv). */ |
---|
| 42 | |
---|
| 43 | struct induction |
---|
| 44 | { |
---|
| 45 | rtx insn; /* The insn that sets a biv or giv */ |
---|
| 46 | rtx new_reg; /* New register, containing strength reduced |
---|
| 47 | version of this giv. */ |
---|
| 48 | rtx src_reg; /* Biv from which this giv is computed. |
---|
| 49 | (If this is a biv, then this is the biv.) */ |
---|
| 50 | enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG */ |
---|
| 51 | rtx dest_reg; /* Destination register for insn: this is the |
---|
| 52 | register which was the biv or giv. |
---|
| 53 | For a biv, this equals src_reg. |
---|
| 54 | For a DEST_ADDR type giv, this is 0. */ |
---|
| 55 | rtx *location; /* Place in the insn where this giv occurs. |
---|
| 56 | If GIV_TYPE is DEST_REG, this is 0. */ |
---|
| 57 | enum machine_mode mode; /* The mode of this biv or giv */ |
---|
| 58 | enum machine_mode mem_mode; /* For DEST_ADDR, mode of the memory object. */ |
---|
| 59 | rtx mult_val; /* Multiplicative factor for src_reg. */ |
---|
| 60 | rtx add_val; /* Additive constant for that product. */ |
---|
| 61 | int benefit; /* Gain from eliminating this insn. */ |
---|
| 62 | rtx final_value; /* If the giv is used outside the loop, and its |
---|
| 63 | final value could be calculated, it is put |
---|
| 64 | here, and the giv is made replaceable. Set |
---|
| 65 | the giv to this value before the loop. */ |
---|
| 66 | unsigned replaceable : 1; /* 1 if we can substitute the strength-reduced |
---|
| 67 | variable for the original variable. |
---|
| 68 | 0 means they must be kept separate and the |
---|
| 69 | new one must be copied into the old pseudo |
---|
| 70 | reg each time the old one is set. */ |
---|
| 71 | unsigned not_replaceable : 1; /* Used to prevent duplicating work. This is |
---|
| 72 | 1 if we know that the giv definitely can |
---|
| 73 | not be made replaceable, in which case we |
---|
| 74 | don't bother checking the variable again |
---|
| 75 | even if further info is available. |
---|
| 76 | Both this and the above can be zero. */ |
---|
| 77 | unsigned ignore : 1; /* 1 prohibits further processing of giv */ |
---|
| 78 | unsigned always_computable : 1;/* 1 if this set occurs each iteration */ |
---|
| 79 | unsigned maybe_multiple : 1; /* Only used for a biv and 1 if this biv |
---|
| 80 | update may be done multiple times per |
---|
| 81 | iteration. */ |
---|
| 82 | unsigned cant_derive : 1; /* For giv's, 1 if this giv cannot derive |
---|
| 83 | another giv. This occurs in many cases |
---|
| 84 | where a giv's lifetime spans an update to |
---|
| 85 | a biv. */ |
---|
| 86 | unsigned combined_with : 1; /* 1 if this giv has been combined with. It |
---|
| 87 | then cannot combine with any other giv. */ |
---|
| 88 | unsigned maybe_dead : 1; /* 1 if this giv might be dead. In that case, |
---|
| 89 | we won't use it to eliminate a biv, it |
---|
| 90 | would probably lose. */ |
---|
| 91 | int lifetime; /* Length of life of this giv */ |
---|
| 92 | int times_used; /* # times this giv is used. */ |
---|
| 93 | rtx derive_adjustment; /* If nonzero, is an adjustment to be |
---|
| 94 | subtracted from add_val when this giv |
---|
| 95 | derives another. This occurs when the |
---|
| 96 | giv spans a biv update by incrementation. */ |
---|
| 97 | struct induction *next_iv; /* For givs, links together all givs that are |
---|
| 98 | based on the same biv. For bivs, links |
---|
| 99 | together all biv entries that refer to the |
---|
| 100 | same biv register. */ |
---|
| 101 | struct induction *same; /* If this giv has been combined with another |
---|
| 102 | giv, this points to the base giv. The base |
---|
| 103 | giv will have COMBINED_WITH non-zero. */ |
---|
| 104 | HOST_WIDE_INT const_adjust; /* Used by loop unrolling, when an address giv |
---|
| 105 | is split, and a constant is eliminated from |
---|
| 106 | the address, the -constant is stored here |
---|
| 107 | for later use. */ |
---|
| 108 | struct induction *same_insn; /* If there are multiple identical givs in |
---|
| 109 | the same insn, then all but one have this |
---|
| 110 | field set, and they all point to the giv |
---|
| 111 | that doesn't have this field set. */ |
---|
| 112 | }; |
---|
| 113 | |
---|
| 114 | /* A `struct iv_class' is created for each biv. */ |
---|
| 115 | |
---|
| 116 | struct iv_class { |
---|
| 117 | int regno; /* Pseudo reg which is the biv. */ |
---|
| 118 | int biv_count; /* Number of insns setting this reg. */ |
---|
| 119 | struct induction *biv; /* List of all insns that set this reg. */ |
---|
| 120 | int giv_count; /* Number of DEST_REG givs computed from this |
---|
| 121 | biv. The resulting count is only used in |
---|
| 122 | check_dbra_loop. */ |
---|
| 123 | struct induction *giv; /* List of all insns that compute a giv |
---|
| 124 | from this reg. */ |
---|
| 125 | int total_benefit; /* Sum of BENEFITs of all those givs */ |
---|
| 126 | rtx initial_value; /* Value of reg at loop start */ |
---|
| 127 | rtx initial_test; /* Test performed on BIV before loop */ |
---|
| 128 | struct iv_class *next; /* Links all class structures together */ |
---|
| 129 | rtx init_insn; /* insn which initializes biv, 0 if none. */ |
---|
| 130 | rtx init_set; /* SET of INIT_INSN, if any. */ |
---|
| 131 | unsigned incremented : 1; /* 1 if somewhere incremented/decremented */ |
---|
| 132 | unsigned eliminable : 1; /* 1 if plausible candidate for elimination. */ |
---|
| 133 | unsigned nonneg : 1; /* 1 if we added a REG_NONNEG note for this. */ |
---|
| 134 | unsigned reversed : 1; /* 1 if we reversed the loop that this |
---|
| 135 | biv controls. */ |
---|
| 136 | }; |
---|
| 137 | |
---|
| 138 | /* Definitions used by the basic induction variable discovery code. */ |
---|
| 139 | enum iv_mode { UNKNOWN_INDUCT, BASIC_INDUCT, NOT_BASIC_INDUCT, |
---|
| 140 | GENERAL_INDUCT }; |
---|
| 141 | |
---|
| 142 | /* Variables declared in loop.c, but also needed in unroll.c. */ |
---|
| 143 | |
---|
| 144 | extern int *uid_luid; |
---|
| 145 | extern int max_uid_for_loop; |
---|
| 146 | extern int *uid_loop_num; |
---|
| 147 | extern int *loop_outer_loop; |
---|
| 148 | extern rtx *loop_number_exit_labels; |
---|
| 149 | extern int *loop_number_exit_count; |
---|
| 150 | extern unsigned HOST_WIDE_INT loop_n_iterations; |
---|
| 151 | extern int max_reg_before_loop; |
---|
| 152 | |
---|
| 153 | extern FILE *loop_dump_stream; |
---|
| 154 | |
---|
| 155 | extern enum iv_mode *reg_iv_type; |
---|
| 156 | extern struct induction **reg_iv_info; |
---|
| 157 | extern struct iv_class **reg_biv_class; |
---|
| 158 | extern struct iv_class *loop_iv_list; |
---|
| 159 | |
---|
| 160 | /* Forward declarations for non-static functions declared in loop.c and |
---|
| 161 | unroll.c. */ |
---|
| 162 | int invariant_p PROTO((rtx)); |
---|
| 163 | rtx get_condition_for_loop PROTO((rtx)); |
---|
| 164 | void emit_iv_add_mult PROTO((rtx, rtx, rtx, rtx, rtx)); |
---|
| 165 | |
---|
| 166 | /* Forward declarations for non-static functions declared in stmt.c. */ |
---|
| 167 | void find_loop_tree_blocks PROTO((void)); |
---|
| 168 | void unroll_block_trees PROTO((void)); |
---|
| 169 | |
---|
| 170 | void unroll_loop PROTO((rtx, int, rtx, rtx, int)); |
---|
| 171 | rtx biv_total_increment PROTO((struct iv_class *, rtx, rtx)); |
---|
| 172 | unsigned HOST_WIDE_INT loop_iterations PROTO((rtx, rtx)); |
---|
| 173 | rtx final_biv_value PROTO((struct iv_class *, rtx, rtx)); |
---|
| 174 | rtx final_giv_value PROTO((struct induction *, rtx, rtx)); |
---|
| 175 | void emit_unrolled_add PROTO((rtx, rtx, rtx)); |
---|
| 176 | int back_branch_in_range_p PROTO((rtx, rtx, rtx)); |
---|