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 value is computable every |
---|
79 | iteration. */ |
---|
80 | unsigned always_executed : 1; /* 1 if this set occurs each iteration. */ |
---|
81 | unsigned maybe_multiple : 1; /* Only used for a biv and 1 if this biv |
---|
82 | update may be done multiple times per |
---|
83 | iteration. */ |
---|
84 | unsigned cant_derive : 1; /* For giv's, 1 if this giv cannot derive |
---|
85 | another giv. This occurs in many cases |
---|
86 | where a giv's lifetime spans an update to |
---|
87 | a biv. */ |
---|
88 | unsigned combined_with : 1; /* 1 if this giv has been combined with. It |
---|
89 | then cannot combine with any other giv. */ |
---|
90 | unsigned maybe_dead : 1; /* 1 if this giv might be dead. In that case, |
---|
91 | we won't use it to eliminate a biv, it |
---|
92 | would probably lose. */ |
---|
93 | unsigned auto_inc_opt : 1; /* 1 if this giv had its increment output next |
---|
94 | to it to try to form an auto-inc address. */ |
---|
95 | int lifetime; /* Length of life of this giv */ |
---|
96 | int times_used; /* # times this giv is used. */ |
---|
97 | rtx derive_adjustment; /* If nonzero, is an adjustment to be |
---|
98 | subtracted from add_val when this giv |
---|
99 | derives another. This occurs when the |
---|
100 | giv spans a biv update by incrementation. */ |
---|
101 | struct induction *next_iv; /* For givs, links together all givs that are |
---|
102 | based on the same biv. For bivs, links |
---|
103 | together all biv entries that refer to the |
---|
104 | same biv register. */ |
---|
105 | struct induction *same; /* If this giv has been combined with another |
---|
106 | giv, this points to the base giv. The base |
---|
107 | giv will have COMBINED_WITH non-zero. */ |
---|
108 | HOST_WIDE_INT const_adjust; /* Used by loop unrolling, when an address giv |
---|
109 | is split, and a constant is eliminated from |
---|
110 | the address, the -constant is stored here |
---|
111 | for later use. */ |
---|
112 | struct induction *same_insn; /* If there are multiple identical givs in |
---|
113 | the same insn, then all but one have this |
---|
114 | field set, and they all point to the giv |
---|
115 | that doesn't have this field set. */ |
---|
116 | }; |
---|
117 | |
---|
118 | /* A `struct iv_class' is created for each biv. */ |
---|
119 | |
---|
120 | struct iv_class { |
---|
121 | int regno; /* Pseudo reg which is the biv. */ |
---|
122 | int biv_count; /* Number of insns setting this reg. */ |
---|
123 | struct induction *biv; /* List of all insns that set this reg. */ |
---|
124 | int giv_count; /* Number of DEST_REG givs computed from this |
---|
125 | biv. The resulting count is only used in |
---|
126 | check_dbra_loop. */ |
---|
127 | struct induction *giv; /* List of all insns that compute a giv |
---|
128 | from this reg. */ |
---|
129 | int total_benefit; /* Sum of BENEFITs of all those givs */ |
---|
130 | rtx initial_value; /* Value of reg at loop start */ |
---|
131 | rtx initial_test; /* Test performed on BIV before loop */ |
---|
132 | struct iv_class *next; /* Links all class structures together */ |
---|
133 | rtx init_insn; /* insn which initializes biv, 0 if none. */ |
---|
134 | rtx init_set; /* SET of INIT_INSN, if any. */ |
---|
135 | unsigned incremented : 1; /* 1 if somewhere incremented/decremented */ |
---|
136 | unsigned eliminable : 1; /* 1 if plausible candidate for elimination. */ |
---|
137 | unsigned nonneg : 1; /* 1 if we added a REG_NONNEG note for this. */ |
---|
138 | unsigned reversed : 1; /* 1 if we reversed the loop that this |
---|
139 | biv controls. */ |
---|
140 | }; |
---|
141 | |
---|
142 | /* Definitions used by the basic induction variable discovery code. */ |
---|
143 | enum iv_mode { UNKNOWN_INDUCT, BASIC_INDUCT, NOT_BASIC_INDUCT, |
---|
144 | GENERAL_INDUCT }; |
---|
145 | |
---|
146 | /* Variables declared in loop.c, but also needed in unroll.c. */ |
---|
147 | |
---|
148 | extern int *uid_luid; |
---|
149 | extern int max_uid_for_loop; |
---|
150 | extern int *uid_loop_num; |
---|
151 | extern int *loop_outer_loop; |
---|
152 | extern rtx *loop_number_exit_labels; |
---|
153 | extern int *loop_number_exit_count; |
---|
154 | extern unsigned HOST_WIDE_INT loop_n_iterations; |
---|
155 | extern int max_reg_before_loop; |
---|
156 | |
---|
157 | extern FILE *loop_dump_stream; |
---|
158 | |
---|
159 | extern enum iv_mode *reg_iv_type; |
---|
160 | extern struct induction **reg_iv_info; |
---|
161 | extern struct iv_class **reg_biv_class; |
---|
162 | extern struct iv_class *loop_iv_list; |
---|
163 | |
---|
164 | /* Forward declarations for non-static functions declared in loop.c and |
---|
165 | unroll.c. */ |
---|
166 | int invariant_p PROTO((rtx)); |
---|
167 | rtx get_condition_for_loop PROTO((rtx)); |
---|
168 | void emit_iv_add_mult PROTO((rtx, rtx, rtx, rtx, rtx)); |
---|
169 | |
---|
170 | /* Forward declarations for non-static functions declared in stmt.c. */ |
---|
171 | void find_loop_tree_blocks PROTO((void)); |
---|
172 | void unroll_block_trees PROTO((void)); |
---|
173 | |
---|
174 | void unroll_loop PROTO((rtx, int, rtx, rtx, int)); |
---|
175 | rtx biv_total_increment PROTO((struct iv_class *, rtx, rtx)); |
---|
176 | unsigned HOST_WIDE_INT loop_iterations PROTO((rtx, rtx)); |
---|
177 | rtx final_biv_value PROTO((struct iv_class *, rtx, rtx)); |
---|
178 | rtx final_giv_value PROTO((struct induction *, rtx, rtx)); |
---|
179 | void emit_unrolled_add PROTO((rtx, rtx, rtx)); |
---|
180 | int back_branch_in_range_p PROTO((rtx, rtx, rtx)); |
---|