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