|
111
|
1 /* Global constant/copy propagation for RTL.
|
|
131
|
2 Copyright (C) 1997-2018 Free Software Foundation, Inc.
|
|
111
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify it under
|
|
|
7 the terms of the GNU General Public License as published by the Free
|
|
|
8 Software Foundation; either version 3, or (at your option) any later
|
|
|
9 version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "system.h"
|
|
|
22 #include "coretypes.h"
|
|
|
23 #include "backend.h"
|
|
|
24 #include "rtl.h"
|
|
|
25 #include "cfghooks.h"
|
|
|
26 #include "df.h"
|
|
|
27 #include "insn-config.h"
|
|
|
28 #include "memmodel.h"
|
|
|
29 #include "emit-rtl.h"
|
|
|
30 #include "recog.h"
|
|
|
31 #include "diagnostic-core.h"
|
|
|
32 #include "toplev.h"
|
|
|
33 #include "cfgrtl.h"
|
|
|
34 #include "cfganal.h"
|
|
|
35 #include "lcm.h"
|
|
|
36 #include "cfgcleanup.h"
|
|
|
37 #include "params.h"
|
|
|
38 #include "cselib.h"
|
|
|
39 #include "intl.h"
|
|
|
40 #include "tree-pass.h"
|
|
|
41 #include "dbgcnt.h"
|
|
|
42 #include "cfgloop.h"
|
|
|
43 #include "gcse.h"
|
|
|
44
|
|
|
45
|
|
|
46 /* An obstack for our working variables. */
|
|
|
47 static struct obstack cprop_obstack;
|
|
|
48
|
|
|
49 /* Occurrence of an expression.
|
|
|
50 There is one per basic block. If a pattern appears more than once the
|
|
|
51 last appearance is used. */
|
|
|
52
|
|
|
53 struct cprop_occr
|
|
|
54 {
|
|
|
55 /* Next occurrence of this expression. */
|
|
|
56 struct cprop_occr *next;
|
|
|
57 /* The insn that computes the expression. */
|
|
|
58 rtx_insn *insn;
|
|
|
59 };
|
|
|
60
|
|
|
61 /* Hash table entry for assignment expressions. */
|
|
|
62
|
|
|
63 struct cprop_expr
|
|
|
64 {
|
|
|
65 /* The expression (DEST := SRC). */
|
|
|
66 rtx dest;
|
|
|
67 rtx src;
|
|
|
68
|
|
|
69 /* Index in the available expression bitmaps. */
|
|
|
70 int bitmap_index;
|
|
|
71 /* Next entry with the same hash. */
|
|
|
72 struct cprop_expr *next_same_hash;
|
|
|
73 /* List of available occurrence in basic blocks in the function.
|
|
|
74 An "available occurrence" is one that is the last occurrence in the
|
|
|
75 basic block and whose operands are not modified by following statements
|
|
|
76 in the basic block [including this insn]. */
|
|
|
77 struct cprop_occr *avail_occr;
|
|
|
78 };
|
|
|
79
|
|
|
80 /* Hash table for copy propagation expressions.
|
|
|
81 Each hash table is an array of buckets.
|
|
|
82 ??? It is known that if it were an array of entries, structure elements
|
|
|
83 `next_same_hash' and `bitmap_index' wouldn't be necessary. However, it is
|
|
|
84 not clear whether in the final analysis a sufficient amount of memory would
|
|
|
85 be saved as the size of the available expression bitmaps would be larger
|
|
|
86 [one could build a mapping table without holes afterwards though].
|
|
|
87 Someday I'll perform the computation and figure it out. */
|
|
|
88
|
|
|
89 struct hash_table_d
|
|
|
90 {
|
|
|
91 /* The table itself.
|
|
|
92 This is an array of `set_hash_table_size' elements. */
|
|
|
93 struct cprop_expr **table;
|
|
|
94
|
|
|
95 /* Size of the hash table, in elements. */
|
|
|
96 unsigned int size;
|
|
|
97
|
|
|
98 /* Number of hash table elements. */
|
|
|
99 unsigned int n_elems;
|
|
|
100 };
|
|
|
101
|
|
|
102 /* Copy propagation hash table. */
|
|
|
103 static struct hash_table_d set_hash_table;
|
|
|
104
|
|
|
105 /* Array of implicit set patterns indexed by basic block index. */
|
|
|
106 static rtx *implicit_sets;
|
|
|
107
|
|
|
108 /* Array of indexes of expressions for implicit set patterns indexed by basic
|
|
|
109 block index. In other words, implicit_set_indexes[i] is the bitmap_index
|
|
|
110 of the expression whose RTX is implicit_sets[i]. */
|
|
|
111 static int *implicit_set_indexes;
|
|
|
112
|
|
|
113 /* Bitmap containing one bit for each register in the program.
|
|
|
114 Used when performing GCSE to track which registers have been set since
|
|
|
115 the start or end of the basic block while traversing that block. */
|
|
|
116 static regset reg_set_bitmap;
|
|
|
117
|
|
|
118 /* Various variables for statistics gathering. */
|
|
|
119
|
|
|
120 /* Memory used in a pass.
|
|
|
121 This isn't intended to be absolutely precise. Its intent is only
|
|
|
122 to keep an eye on memory usage. */
|
|
|
123 static int bytes_used;
|
|
|
124
|
|
|
125 /* Number of local constants propagated. */
|
|
|
126 static int local_const_prop_count;
|
|
|
127 /* Number of local copies propagated. */
|
|
|
128 static int local_copy_prop_count;
|
|
|
129 /* Number of global constants propagated. */
|
|
|
130 static int global_const_prop_count;
|
|
|
131 /* Number of global copies propagated. */
|
|
|
132 static int global_copy_prop_count;
|
|
|
133
|
|
|
134 #define GOBNEW(T) ((T *) cprop_alloc (sizeof (T)))
|
|
|
135 #define GOBNEWVAR(T, S) ((T *) cprop_alloc ((S)))
|
|
|
136
|
|
|
137 /* Cover function to obstack_alloc. */
|
|
|
138
|
|
|
139 static void *
|
|
|
140 cprop_alloc (unsigned long size)
|
|
|
141 {
|
|
|
142 bytes_used += size;
|
|
|
143 return obstack_alloc (&cprop_obstack, size);
|
|
|
144 }
|
|
|
145
|
|
|
146 /* Return nonzero if register X is unchanged from INSN to the end
|
|
|
147 of INSN's basic block. */
|
|
|
148
|
|
|
149 static int
|
|
|
150 reg_available_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED)
|
|
|
151 {
|
|
|
152 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
|
|
|
153 }
|
|
|
154
|
|
|
155 /* Hash a set of register REGNO.
|
|
|
156
|
|
|
157 Sets are hashed on the register that is set. This simplifies the PRE copy
|
|
|
158 propagation code.
|
|
|
159
|
|
|
160 ??? May need to make things more elaborate. Later, as necessary. */
|
|
|
161
|
|
|
162 static unsigned int
|
|
|
163 hash_mod (int regno, int hash_table_size)
|
|
|
164 {
|
|
|
165 return (unsigned) regno % hash_table_size;
|
|
|
166 }
|
|
|
167
|
|
|
168 /* Insert assignment DEST:=SET from INSN in the hash table.
|
|
|
169 DEST is a register and SET is a register or a suitable constant.
|
|
|
170 If the assignment is already present in the table, record it as
|
|
|
171 the last occurrence in INSN's basic block.
|
|
|
172 IMPLICIT is true if it's an implicit set, false otherwise. */
|
|
|
173
|
|
|
174 static void
|
|
|
175 insert_set_in_table (rtx dest, rtx src, rtx_insn *insn,
|
|
|
176 struct hash_table_d *table, bool implicit)
|
|
|
177 {
|
|
|
178 bool found = false;
|
|
|
179 unsigned int hash;
|
|
|
180 struct cprop_expr *cur_expr, *last_expr = NULL;
|
|
|
181 struct cprop_occr *cur_occr;
|
|
|
182
|
|
|
183 hash = hash_mod (REGNO (dest), table->size);
|
|
|
184
|
|
|
185 for (cur_expr = table->table[hash]; cur_expr;
|
|
|
186 cur_expr = cur_expr->next_same_hash)
|
|
|
187 {
|
|
|
188 if (dest == cur_expr->dest
|
|
|
189 && src == cur_expr->src)
|
|
|
190 {
|
|
|
191 found = true;
|
|
|
192 break;
|
|
|
193 }
|
|
|
194 last_expr = cur_expr;
|
|
|
195 }
|
|
|
196
|
|
|
197 if (! found)
|
|
|
198 {
|
|
|
199 cur_expr = GOBNEW (struct cprop_expr);
|
|
|
200 bytes_used += sizeof (struct cprop_expr);
|
|
|
201 if (table->table[hash] == NULL)
|
|
|
202 /* This is the first pattern that hashed to this index. */
|
|
|
203 table->table[hash] = cur_expr;
|
|
|
204 else
|
|
|
205 /* Add EXPR to end of this hash chain. */
|
|
|
206 last_expr->next_same_hash = cur_expr;
|
|
|
207
|
|
|
208 /* Set the fields of the expr element.
|
|
|
209 We must copy X because it can be modified when copy propagation is
|
|
|
210 performed on its operands. */
|
|
|
211 cur_expr->dest = copy_rtx (dest);
|
|
|
212 cur_expr->src = copy_rtx (src);
|
|
|
213 cur_expr->bitmap_index = table->n_elems++;
|
|
|
214 cur_expr->next_same_hash = NULL;
|
|
|
215 cur_expr->avail_occr = NULL;
|
|
|
216 }
|
|
|
217
|
|
|
218 /* Now record the occurrence. */
|
|
|
219 cur_occr = cur_expr->avail_occr;
|
|
|
220
|
|
|
221 if (cur_occr
|
|
|
222 && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn))
|
|
|
223 {
|
|
|
224 /* Found another instance of the expression in the same basic block.
|
|
|
225 Prefer this occurrence to the currently recorded one. We want
|
|
|
226 the last one in the block and the block is scanned from start
|
|
|
227 to end. */
|
|
|
228 cur_occr->insn = insn;
|
|
|
229 }
|
|
|
230 else
|
|
|
231 {
|
|
|
232 /* First occurrence of this expression in this basic block. */
|
|
|
233 cur_occr = GOBNEW (struct cprop_occr);
|
|
|
234 bytes_used += sizeof (struct cprop_occr);
|
|
|
235 cur_occr->insn = insn;
|
|
|
236 cur_occr->next = cur_expr->avail_occr;
|
|
|
237 cur_expr->avail_occr = cur_occr;
|
|
|
238 }
|
|
|
239
|
|
|
240 /* Record bitmap_index of the implicit set in implicit_set_indexes. */
|
|
|
241 if (implicit)
|
|
|
242 implicit_set_indexes[BLOCK_FOR_INSN (insn)->index]
|
|
|
243 = cur_expr->bitmap_index;
|
|
|
244 }
|
|
|
245
|
|
|
246 /* Determine whether the rtx X should be treated as a constant for CPROP.
|
|
|
247 Since X might be inserted more than once we have to take care that it
|
|
|
248 is sharable. */
|
|
|
249
|
|
|
250 static bool
|
|
|
251 cprop_constant_p (const_rtx x)
|
|
|
252 {
|
|
|
253 return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
|
|
|
254 }
|
|
|
255
|
|
|
256 /* Determine whether the rtx X should be treated as a register that can
|
|
|
257 be propagated. Any pseudo-register is fine. */
|
|
|
258
|
|
|
259 static bool
|
|
|
260 cprop_reg_p (const_rtx x)
|
|
|
261 {
|
|
|
262 return REG_P (x) && !HARD_REGISTER_P (x);
|
|
|
263 }
|
|
|
264
|
|
|
265 /* Scan SET present in INSN and add an entry to the hash TABLE.
|
|
|
266 IMPLICIT is true if it's an implicit set, false otherwise. */
|
|
|
267
|
|
|
268 static void
|
|
|
269 hash_scan_set (rtx set, rtx_insn *insn, struct hash_table_d *table,
|
|
|
270 bool implicit)
|
|
|
271 {
|
|
|
272 rtx src = SET_SRC (set);
|
|
|
273 rtx dest = SET_DEST (set);
|
|
|
274
|
|
|
275 if (cprop_reg_p (dest)
|
|
|
276 && reg_available_p (dest, insn)
|
|
|
277 && can_copy_p (GET_MODE (dest)))
|
|
|
278 {
|
|
|
279 /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
|
|
|
280
|
|
|
281 This allows us to do a single CPROP pass and still eliminate
|
|
|
282 redundant constants, addresses or other expressions that are
|
|
|
283 constructed with multiple instructions.
|
|
|
284
|
|
|
285 However, keep the original SRC if INSN is a simple reg-reg move. In
|
|
|
286 In this case, there will almost always be a REG_EQUAL note on the
|
|
|
287 insn that sets SRC. By recording the REG_EQUAL value here as SRC
|
|
|
288 for INSN, we miss copy propagation opportunities.
|
|
|
289
|
|
|
290 Note that this does not impede profitable constant propagations. We
|
|
|
291 "look through" reg-reg sets in lookup_set. */
|
|
|
292 rtx note = find_reg_equal_equiv_note (insn);
|
|
|
293 if (note != 0
|
|
|
294 && REG_NOTE_KIND (note) == REG_EQUAL
|
|
|
295 && !REG_P (src)
|
|
|
296 && cprop_constant_p (XEXP (note, 0)))
|
|
|
297 src = XEXP (note, 0), set = gen_rtx_SET (dest, src);
|
|
|
298
|
|
|
299 /* Record sets for constant/copy propagation. */
|
|
|
300 if ((cprop_reg_p (src)
|
|
|
301 && src != dest
|
|
|
302 && reg_available_p (src, insn))
|
|
|
303 || cprop_constant_p (src))
|
|
|
304 insert_set_in_table (dest, src, insn, table, implicit);
|
|
|
305 }
|
|
|
306 }
|
|
|
307
|
|
|
308 /* Process INSN and add hash table entries as appropriate. */
|
|
|
309
|
|
|
310 static void
|
|
|
311 hash_scan_insn (rtx_insn *insn, struct hash_table_d *table)
|
|
|
312 {
|
|
|
313 rtx pat = PATTERN (insn);
|
|
|
314 int i;
|
|
|
315
|
|
|
316 /* Pick out the sets of INSN and for other forms of instructions record
|
|
|
317 what's been modified. */
|
|
|
318
|
|
|
319 if (GET_CODE (pat) == SET)
|
|
|
320 hash_scan_set (pat, insn, table, false);
|
|
|
321 else if (GET_CODE (pat) == PARALLEL)
|
|
|
322 for (i = 0; i < XVECLEN (pat, 0); i++)
|
|
|
323 {
|
|
|
324 rtx x = XVECEXP (pat, 0, i);
|
|
|
325
|
|
|
326 if (GET_CODE (x) == SET)
|
|
|
327 hash_scan_set (x, insn, table, false);
|
|
|
328 }
|
|
|
329 }
|
|
|
330
|
|
|
331 /* Dump the hash table TABLE to file FILE under the name NAME. */
|
|
|
332
|
|
|
333 static void
|
|
|
334 dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
|
|
|
335 {
|
|
|
336 int i;
|
|
|
337 /* Flattened out table, so it's printed in proper order. */
|
|
|
338 struct cprop_expr **flat_table;
|
|
|
339 unsigned int *hash_val;
|
|
|
340 struct cprop_expr *expr;
|
|
|
341
|
|
|
342 flat_table = XCNEWVEC (struct cprop_expr *, table->n_elems);
|
|
|
343 hash_val = XNEWVEC (unsigned int, table->n_elems);
|
|
|
344
|
|
|
345 for (i = 0; i < (int) table->size; i++)
|
|
|
346 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
|
|
|
347 {
|
|
|
348 flat_table[expr->bitmap_index] = expr;
|
|
|
349 hash_val[expr->bitmap_index] = i;
|
|
|
350 }
|
|
|
351
|
|
|
352 fprintf (file, "%s hash table (%d buckets, %d entries)\n",
|
|
|
353 name, table->size, table->n_elems);
|
|
|
354
|
|
|
355 for (i = 0; i < (int) table->n_elems; i++)
|
|
|
356 if (flat_table[i] != 0)
|
|
|
357 {
|
|
|
358 expr = flat_table[i];
|
|
|
359 fprintf (file, "Index %d (hash value %d)\n ",
|
|
|
360 expr->bitmap_index, hash_val[i]);
|
|
|
361 print_rtl (file, expr->dest);
|
|
|
362 fprintf (file, " := ");
|
|
|
363 print_rtl (file, expr->src);
|
|
|
364 fprintf (file, "\n");
|
|
|
365 }
|
|
|
366
|
|
|
367 fprintf (file, "\n");
|
|
|
368
|
|
|
369 free (flat_table);
|
|
|
370 free (hash_val);
|
|
|
371 }
|
|
|
372
|
|
|
373 /* Record as unavailable all registers that are DEF operands of INSN. */
|
|
|
374
|
|
|
375 static void
|
|
|
376 make_set_regs_unavailable (rtx_insn *insn)
|
|
|
377 {
|
|
|
378 df_ref def;
|
|
|
379
|
|
|
380 FOR_EACH_INSN_DEF (def, insn)
|
|
|
381 SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def));
|
|
|
382 }
|
|
|
383
|
|
|
384 /* Top level function to create an assignment hash table.
|
|
|
385
|
|
|
386 Assignment entries are placed in the hash table if
|
|
|
387 - they are of the form (set (pseudo-reg) src),
|
|
|
388 - src is something we want to perform const/copy propagation on,
|
|
|
389 - none of the operands or target are subsequently modified in the block
|
|
|
390
|
|
|
391 Currently src must be a pseudo-reg or a const_int.
|
|
|
392
|
|
|
393 TABLE is the table computed. */
|
|
|
394
|
|
|
395 static void
|
|
|
396 compute_hash_table_work (struct hash_table_d *table)
|
|
|
397 {
|
|
|
398 basic_block bb;
|
|
|
399
|
|
|
400 /* Allocate vars to track sets of regs. */
|
|
|
401 reg_set_bitmap = ALLOC_REG_SET (NULL);
|
|
|
402
|
|
|
403 FOR_EACH_BB_FN (bb, cfun)
|
|
|
404 {
|
|
|
405 rtx_insn *insn;
|
|
|
406
|
|
|
407 /* Reset tables used to keep track of what's not yet invalid [since
|
|
|
408 the end of the block]. */
|
|
|
409 CLEAR_REG_SET (reg_set_bitmap);
|
|
|
410
|
|
|
411 /* Go over all insns from the last to the first. This is convenient
|
|
|
412 for tracking available registers, i.e. not set between INSN and
|
|
|
413 the end of the basic block BB. */
|
|
|
414 FOR_BB_INSNS_REVERSE (bb, insn)
|
|
|
415 {
|
|
|
416 /* Only real insns are interesting. */
|
|
|
417 if (!NONDEBUG_INSN_P (insn))
|
|
|
418 continue;
|
|
|
419
|
|
|
420 /* Record interesting sets from INSN in the hash table. */
|
|
|
421 hash_scan_insn (insn, table);
|
|
|
422
|
|
|
423 /* Any registers set in INSN will make SETs above it not AVAIL. */
|
|
|
424 make_set_regs_unavailable (insn);
|
|
|
425 }
|
|
|
426
|
|
|
427 /* Insert implicit sets in the hash table, pretending they appear as
|
|
|
428 insns at the head of the basic block. */
|
|
|
429 if (implicit_sets[bb->index] != NULL_RTX)
|
|
|
430 hash_scan_set (implicit_sets[bb->index], BB_HEAD (bb), table, true);
|
|
|
431 }
|
|
|
432
|
|
|
433 FREE_REG_SET (reg_set_bitmap);
|
|
|
434 }
|
|
|
435
|
|
|
436 /* Allocate space for the set/expr hash TABLE.
|
|
|
437 It is used to determine the number of buckets to use. */
|
|
|
438
|
|
|
439 static void
|
|
|
440 alloc_hash_table (struct hash_table_d *table)
|
|
|
441 {
|
|
|
442 int n;
|
|
|
443
|
|
|
444 n = get_max_insn_count ();
|
|
|
445
|
|
|
446 table->size = n / 4;
|
|
|
447 if (table->size < 11)
|
|
|
448 table->size = 11;
|
|
|
449
|
|
|
450 /* Attempt to maintain efficient use of hash table.
|
|
|
451 Making it an odd number is simplest for now.
|
|
|
452 ??? Later take some measurements. */
|
|
|
453 table->size |= 1;
|
|
|
454 n = table->size * sizeof (struct cprop_expr *);
|
|
|
455 table->table = XNEWVAR (struct cprop_expr *, n);
|
|
|
456 }
|
|
|
457
|
|
|
458 /* Free things allocated by alloc_hash_table. */
|
|
|
459
|
|
|
460 static void
|
|
|
461 free_hash_table (struct hash_table_d *table)
|
|
|
462 {
|
|
|
463 free (table->table);
|
|
|
464 }
|
|
|
465
|
|
|
466 /* Compute the hash TABLE for doing copy/const propagation or
|
|
|
467 expression hash table. */
|
|
|
468
|
|
|
469 static void
|
|
|
470 compute_hash_table (struct hash_table_d *table)
|
|
|
471 {
|
|
|
472 /* Initialize count of number of entries in hash table. */
|
|
|
473 table->n_elems = 0;
|
|
|
474 memset (table->table, 0, table->size * sizeof (struct cprop_expr *));
|
|
|
475
|
|
|
476 compute_hash_table_work (table);
|
|
|
477 }
|
|
|
478
|
|
|
479 /* Expression tracking support. */
|
|
|
480
|
|
|
481 /* Lookup REGNO in the set TABLE. The result is a pointer to the
|
|
|
482 table entry, or NULL if not found. */
|
|
|
483
|
|
|
484 static struct cprop_expr *
|
|
|
485 lookup_set (unsigned int regno, struct hash_table_d *table)
|
|
|
486 {
|
|
|
487 unsigned int hash = hash_mod (regno, table->size);
|
|
|
488 struct cprop_expr *expr;
|
|
|
489
|
|
|
490 expr = table->table[hash];
|
|
|
491
|
|
|
492 while (expr && REGNO (expr->dest) != regno)
|
|
|
493 expr = expr->next_same_hash;
|
|
|
494
|
|
|
495 return expr;
|
|
|
496 }
|
|
|
497
|
|
|
498 /* Return the next entry for REGNO in list EXPR. */
|
|
|
499
|
|
|
500 static struct cprop_expr *
|
|
|
501 next_set (unsigned int regno, struct cprop_expr *expr)
|
|
|
502 {
|
|
|
503 do
|
|
|
504 expr = expr->next_same_hash;
|
|
|
505 while (expr && REGNO (expr->dest) != regno);
|
|
|
506
|
|
|
507 return expr;
|
|
|
508 }
|
|
|
509
|
|
|
510 /* Reset tables used to keep track of what's still available [since the
|
|
|
511 start of the block]. */
|
|
|
512
|
|
|
513 static void
|
|
|
514 reset_opr_set_tables (void)
|
|
|
515 {
|
|
|
516 /* Maintain a bitmap of which regs have been set since beginning of
|
|
|
517 the block. */
|
|
|
518 CLEAR_REG_SET (reg_set_bitmap);
|
|
|
519 }
|
|
|
520
|
|
|
521 /* Return nonzero if the register X has not been set yet [since the
|
|
|
522 start of the basic block containing INSN]. */
|
|
|
523
|
|
|
524 static int
|
|
|
525 reg_not_set_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED)
|
|
|
526 {
|
|
|
527 return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
|
|
|
528 }
|
|
|
529
|
|
|
530 /* Record things set by INSN.
|
|
|
531 This data is used by reg_not_set_p. */
|
|
|
532
|
|
|
533 static void
|
|
|
534 mark_oprs_set (rtx_insn *insn)
|
|
|
535 {
|
|
|
536 df_ref def;
|
|
|
537
|
|
|
538 FOR_EACH_INSN_DEF (def, insn)
|
|
|
539 SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def));
|
|
|
540 }
|
|
|
541
|
|
|
542 /* Compute copy/constant propagation working variables. */
|
|
|
543
|
|
|
544 /* Local properties of assignments. */
|
|
|
545 static sbitmap *cprop_avloc;
|
|
|
546 static sbitmap *cprop_kill;
|
|
|
547
|
|
|
548 /* Global properties of assignments (computed from the local properties). */
|
|
|
549 static sbitmap *cprop_avin;
|
|
|
550 static sbitmap *cprop_avout;
|
|
|
551
|
|
|
552 /* Allocate vars used for copy/const propagation. N_BLOCKS is the number of
|
|
|
553 basic blocks. N_SETS is the number of sets. */
|
|
|
554
|
|
|
555 static void
|
|
|
556 alloc_cprop_mem (int n_blocks, int n_sets)
|
|
|
557 {
|
|
|
558 cprop_avloc = sbitmap_vector_alloc (n_blocks, n_sets);
|
|
|
559 cprop_kill = sbitmap_vector_alloc (n_blocks, n_sets);
|
|
|
560
|
|
|
561 cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
|
|
|
562 cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
|
|
|
563 }
|
|
|
564
|
|
|
565 /* Free vars used by copy/const propagation. */
|
|
|
566
|
|
|
567 static void
|
|
|
568 free_cprop_mem (void)
|
|
|
569 {
|
|
|
570 sbitmap_vector_free (cprop_avloc);
|
|
|
571 sbitmap_vector_free (cprop_kill);
|
|
|
572 sbitmap_vector_free (cprop_avin);
|
|
|
573 sbitmap_vector_free (cprop_avout);
|
|
|
574 }
|
|
|
575
|
|
|
576 /* Compute the local properties of each recorded expression.
|
|
|
577
|
|
|
578 Local properties are those that are defined by the block, irrespective of
|
|
|
579 other blocks.
|
|
|
580
|
|
|
581 An expression is killed in a block if its operands, either DEST or SRC, are
|
|
|
582 modified in the block.
|
|
|
583
|
|
|
584 An expression is computed (locally available) in a block if it is computed
|
|
|
585 at least once and expression would contain the same value if the
|
|
|
586 computation was moved to the end of the block.
|
|
|
587
|
|
|
588 KILL and COMP are destination sbitmaps for recording local properties. */
|
|
|
589
|
|
|
590 static void
|
|
|
591 compute_local_properties (sbitmap *kill, sbitmap *comp,
|
|
|
592 struct hash_table_d *table)
|
|
|
593 {
|
|
|
594 unsigned int i;
|
|
|
595
|
|
|
596 /* Initialize the bitmaps that were passed in. */
|
|
|
597 bitmap_vector_clear (kill, last_basic_block_for_fn (cfun));
|
|
|
598 bitmap_vector_clear (comp, last_basic_block_for_fn (cfun));
|
|
|
599
|
|
|
600 for (i = 0; i < table->size; i++)
|
|
|
601 {
|
|
|
602 struct cprop_expr *expr;
|
|
|
603
|
|
|
604 for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
|
|
|
605 {
|
|
|
606 int indx = expr->bitmap_index;
|
|
|
607 df_ref def;
|
|
|
608 struct cprop_occr *occr;
|
|
|
609
|
|
|
610 /* For each definition of the destination pseudo-reg, the expression
|
|
|
611 is killed in the block where the definition is. */
|
|
|
612 for (def = DF_REG_DEF_CHAIN (REGNO (expr->dest));
|
|
|
613 def; def = DF_REF_NEXT_REG (def))
|
|
|
614 bitmap_set_bit (kill[DF_REF_BB (def)->index], indx);
|
|
|
615
|
|
|
616 /* If the source is a pseudo-reg, for each definition of the source,
|
|
|
617 the expression is killed in the block where the definition is. */
|
|
|
618 if (REG_P (expr->src))
|
|
|
619 for (def = DF_REG_DEF_CHAIN (REGNO (expr->src));
|
|
|
620 def; def = DF_REF_NEXT_REG (def))
|
|
|
621 bitmap_set_bit (kill[DF_REF_BB (def)->index], indx);
|
|
|
622
|
|
|
623 /* The occurrences recorded in avail_occr are exactly those that
|
|
|
624 are locally available in the block where they are. */
|
|
|
625 for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
|
|
|
626 {
|
|
|
627 bitmap_set_bit (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
|
|
|
628 }
|
|
|
629 }
|
|
|
630 }
|
|
|
631 }
|
|
|
632
|
|
|
633 /* Hash table support. */
|
|
|
634
|
|
|
635 /* Top level routine to do the dataflow analysis needed by copy/const
|
|
|
636 propagation. */
|
|
|
637
|
|
|
638 static void
|
|
|
639 compute_cprop_data (void)
|
|
|
640 {
|
|
|
641 basic_block bb;
|
|
|
642
|
|
|
643 compute_local_properties (cprop_kill, cprop_avloc, &set_hash_table);
|
|
|
644 compute_available (cprop_avloc, cprop_kill, cprop_avout, cprop_avin);
|
|
|
645
|
|
|
646 /* Merge implicit sets into CPROP_AVIN. They are always available at the
|
|
|
647 entry of their basic block. We need to do this because 1) implicit sets
|
|
|
648 aren't recorded for the local pass so they cannot be propagated within
|
|
|
649 their basic block by this pass and 2) the global pass would otherwise
|
|
|
650 propagate them only in the successors of their basic block. */
|
|
|
651 FOR_EACH_BB_FN (bb, cfun)
|
|
|
652 {
|
|
|
653 int index = implicit_set_indexes[bb->index];
|
|
|
654 if (index != -1)
|
|
|
655 bitmap_set_bit (cprop_avin[bb->index], index);
|
|
|
656 }
|
|
|
657 }
|
|
|
658
|
|
|
659 /* Copy/constant propagation. */
|
|
|
660
|
|
|
661 /* Maximum number of register uses in an insn that we handle. */
|
|
|
662 #define MAX_USES 8
|
|
|
663
|
|
|
664 /* Table of uses (registers, both hard and pseudo) found in an insn.
|
|
|
665 Allocated statically to avoid alloc/free complexity and overhead. */
|
|
|
666 static rtx reg_use_table[MAX_USES];
|
|
|
667
|
|
|
668 /* Index into `reg_use_table' while building it. */
|
|
|
669 static unsigned reg_use_count;
|
|
|
670
|
|
|
671 /* Set up a list of register numbers used in INSN. The found uses are stored
|
|
|
672 in `reg_use_table'. `reg_use_count' is initialized to zero before entry,
|
|
|
673 and contains the number of uses in the table upon exit.
|
|
|
674
|
|
|
675 ??? If a register appears multiple times we will record it multiple times.
|
|
|
676 This doesn't hurt anything but it will slow things down. */
|
|
|
677
|
|
|
678 static void
|
|
|
679 find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
|
|
|
680 {
|
|
|
681 int i, j;
|
|
|
682 enum rtx_code code;
|
|
|
683 const char *fmt;
|
|
|
684 rtx x = *xptr;
|
|
|
685
|
|
|
686 /* repeat is used to turn tail-recursion into iteration since GCC
|
|
|
687 can't do it when there's no return value. */
|
|
|
688 repeat:
|
|
|
689 if (x == 0)
|
|
|
690 return;
|
|
|
691
|
|
|
692 code = GET_CODE (x);
|
|
|
693 if (REG_P (x))
|
|
|
694 {
|
|
|
695 if (reg_use_count == MAX_USES)
|
|
|
696 return;
|
|
|
697
|
|
|
698 reg_use_table[reg_use_count] = x;
|
|
|
699 reg_use_count++;
|
|
|
700 }
|
|
|
701
|
|
|
702 /* Recursively scan the operands of this expression. */
|
|
|
703
|
|
|
704 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
|
|
|
705 {
|
|
|
706 if (fmt[i] == 'e')
|
|
|
707 {
|
|
|
708 /* If we are about to do the last recursive call
|
|
|
709 needed at this level, change it into iteration.
|
|
|
710 This function is called enough to be worth it. */
|
|
|
711 if (i == 0)
|
|
|
712 {
|
|
|
713 x = XEXP (x, 0);
|
|
|
714 goto repeat;
|
|
|
715 }
|
|
|
716
|
|
|
717 find_used_regs (&XEXP (x, i), data);
|
|
|
718 }
|
|
|
719 else if (fmt[i] == 'E')
|
|
|
720 for (j = 0; j < XVECLEN (x, i); j++)
|
|
|
721 find_used_regs (&XVECEXP (x, i, j), data);
|
|
|
722 }
|
|
|
723 }
|
|
|
724
|
|
|
725 /* Try to replace all uses of FROM in INSN with TO.
|
|
|
726 Return nonzero if successful. */
|
|
|
727
|
|
|
728 static int
|
|
|
729 try_replace_reg (rtx from, rtx to, rtx_insn *insn)
|
|
|
730 {
|
|
|
731 rtx note = find_reg_equal_equiv_note (insn);
|
|
|
732 rtx src = 0;
|
|
|
733 int success = 0;
|
|
|
734 rtx set = single_set (insn);
|
|
|
735
|
|
|
736 bool check_rtx_costs = true;
|
|
|
737 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
|
|
|
738 int old_cost = set ? set_rtx_cost (set, speed) : 0;
|
|
|
739
|
|
|
740 if (!set
|
|
|
741 || CONSTANT_P (SET_SRC (set))
|
|
|
742 || (note != 0
|
|
|
743 && REG_NOTE_KIND (note) == REG_EQUAL
|
|
|
744 && (GET_CODE (XEXP (note, 0)) == CONST
|
|
|
745 || CONSTANT_P (XEXP (note, 0)))))
|
|
|
746 check_rtx_costs = false;
|
|
|
747
|
|
|
748 /* Usually we substitute easy stuff, so we won't copy everything.
|
|
|
749 We however need to take care to not duplicate non-trivial CONST
|
|
|
750 expressions. */
|
|
|
751 to = copy_rtx (to);
|
|
|
752
|
|
|
753 validate_replace_src_group (from, to, insn);
|
|
|
754
|
|
|
755 /* If TO is a constant, check the cost of the set after propagation
|
|
|
756 to the cost of the set before the propagation. If the cost is
|
|
|
757 higher, then do not replace FROM with TO. */
|
|
|
758
|
|
|
759 if (check_rtx_costs
|
|
|
760 && CONSTANT_P (to)
|
|
|
761 && set_rtx_cost (set, speed) > old_cost)
|
|
|
762 {
|
|
|
763 cancel_changes (0);
|
|
|
764 return false;
|
|
|
765 }
|
|
|
766
|
|
|
767
|
|
|
768 if (num_changes_pending () && apply_change_group ())
|
|
|
769 success = 1;
|
|
|
770
|
|
|
771 /* Try to simplify SET_SRC if we have substituted a constant. */
|
|
|
772 if (success && set && CONSTANT_P (to))
|
|
|
773 {
|
|
|
774 src = simplify_rtx (SET_SRC (set));
|
|
|
775
|
|
|
776 if (src)
|
|
|
777 validate_change (insn, &SET_SRC (set), src, 0);
|
|
|
778 }
|
|
|
779
|
|
|
780 /* If there is already a REG_EQUAL note, update the expression in it
|
|
|
781 with our replacement. */
|
|
|
782 if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
|
|
|
783 set_unique_reg_note (insn, REG_EQUAL,
|
|
|
784 simplify_replace_rtx (XEXP (note, 0), from, to));
|
|
|
785 if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
|
|
|
786 {
|
|
|
787 /* If above failed and this is a single set, try to simplify the source
|
|
|
788 of the set given our substitution. We could perhaps try this for
|
|
|
789 multiple SETs, but it probably won't buy us anything. */
|
|
|
790 src = simplify_replace_rtx (SET_SRC (set), from, to);
|
|
|
791
|
|
|
792 if (!rtx_equal_p (src, SET_SRC (set))
|
|
|
793 && validate_change (insn, &SET_SRC (set), src, 0))
|
|
|
794 success = 1;
|
|
|
795
|
|
|
796 /* If we've failed perform the replacement, have a single SET to
|
|
|
797 a REG destination and don't yet have a note, add a REG_EQUAL note
|
|
|
798 to not lose information. */
|
|
|
799 if (!success && note == 0 && set != 0 && REG_P (SET_DEST (set)))
|
|
|
800 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
|
|
|
801 }
|
|
|
802
|
|
|
803 if (set && MEM_P (SET_DEST (set)) && reg_mentioned_p (from, SET_DEST (set)))
|
|
|
804 {
|
|
|
805 /* Registers can also appear as uses in SET_DEST if it is a MEM.
|
|
|
806 We could perhaps try this for multiple SETs, but it probably
|
|
|
807 won't buy us anything. */
|
|
|
808 rtx dest = simplify_replace_rtx (SET_DEST (set), from, to);
|
|
|
809
|
|
|
810 if (!rtx_equal_p (dest, SET_DEST (set))
|
|
|
811 && validate_change (insn, &SET_DEST (set), dest, 0))
|
|
|
812 success = 1;
|
|
|
813 }
|
|
|
814
|
|
|
815 /* REG_EQUAL may get simplified into register.
|
|
|
816 We don't allow that. Remove that note. This code ought
|
|
|
817 not to happen, because previous code ought to synthesize
|
|
|
818 reg-reg move, but be on the safe side. */
|
|
|
819 if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
|
|
|
820 remove_note (insn, note);
|
|
|
821
|
|
|
822 return success;
|
|
|
823 }
|
|
|
824
|
|
|
825 /* Find a set of REGNOs that are available on entry to INSN's block. If found,
|
|
|
826 SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
|
|
|
827 set with a constant source. If not found the corresponding entry is set to
|
|
|
828 NULL. */
|
|
|
829
|
|
|
830 static void
|
|
|
831 find_avail_set (int regno, rtx_insn *insn, struct cprop_expr *set_ret[2])
|
|
|
832 {
|
|
|
833 set_ret[0] = set_ret[1] = NULL;
|
|
|
834
|
|
|
835 /* Loops are not possible here. To get a loop we would need two sets
|
|
|
836 available at the start of the block containing INSN. i.e. we would
|
|
|
837 need two sets like this available at the start of the block:
|
|
|
838
|
|
|
839 (set (reg X) (reg Y))
|
|
|
840 (set (reg Y) (reg X))
|
|
|
841
|
|
|
842 This can not happen since the set of (reg Y) would have killed the
|
|
|
843 set of (reg X) making it unavailable at the start of this block. */
|
|
|
844 while (1)
|
|
|
845 {
|
|
|
846 rtx src;
|
|
|
847 struct cprop_expr *set = lookup_set (regno, &set_hash_table);
|
|
|
848
|
|
|
849 /* Find a set that is available at the start of the block
|
|
|
850 which contains INSN. */
|
|
|
851 while (set)
|
|
|
852 {
|
|
|
853 if (bitmap_bit_p (cprop_avin[BLOCK_FOR_INSN (insn)->index],
|
|
|
854 set->bitmap_index))
|
|
|
855 break;
|
|
|
856 set = next_set (regno, set);
|
|
|
857 }
|
|
|
858
|
|
|
859 /* If no available set was found we've reached the end of the
|
|
|
860 (possibly empty) copy chain. */
|
|
|
861 if (set == 0)
|
|
|
862 break;
|
|
|
863
|
|
|
864 src = set->src;
|
|
|
865
|
|
|
866 /* We know the set is available.
|
|
|
867 Now check that SRC is locally anticipatable (i.e. none of the
|
|
|
868 source operands have changed since the start of the block).
|
|
|
869
|
|
|
870 If the source operand changed, we may still use it for the next
|
|
|
871 iteration of this loop, but we may not use it for substitutions. */
|
|
|
872
|
|
|
873 if (cprop_constant_p (src))
|
|
|
874 set_ret[1] = set;
|
|
|
875 else if (reg_not_set_p (src, insn))
|
|
|
876 set_ret[0] = set;
|
|
|
877
|
|
|
878 /* If the source of the set is anything except a register, then
|
|
|
879 we have reached the end of the copy chain. */
|
|
|
880 if (! REG_P (src))
|
|
|
881 break;
|
|
|
882
|
|
|
883 /* Follow the copy chain, i.e. start another iteration of the loop
|
|
|
884 and see if we have an available copy into SRC. */
|
|
|
885 regno = REGNO (src);
|
|
|
886 }
|
|
|
887 }
|
|
|
888
|
|
|
889 /* Subroutine of cprop_insn that tries to propagate constants into
|
|
|
890 JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
|
|
|
891 it is the instruction that immediately precedes JUMP, and must be a
|
|
|
892 single SET of a register. FROM is what we will try to replace,
|
|
|
893 SRC is the constant we will try to substitute for it. Return nonzero
|
|
|
894 if a change was made. */
|
|
|
895
|
|
|
896 static int
|
|
|
897 cprop_jump (basic_block bb, rtx_insn *setcc, rtx_insn *jump, rtx from, rtx src)
|
|
|
898 {
|
|
|
899 rtx new_rtx, set_src, note_src;
|
|
|
900 rtx set = pc_set (jump);
|
|
|
901 rtx note = find_reg_equal_equiv_note (jump);
|
|
|
902
|
|
|
903 if (note)
|
|
|
904 {
|
|
|
905 note_src = XEXP (note, 0);
|
|
|
906 if (GET_CODE (note_src) == EXPR_LIST)
|
|
|
907 note_src = NULL_RTX;
|
|
|
908 }
|
|
|
909 else note_src = NULL_RTX;
|
|
|
910
|
|
|
911 /* Prefer REG_EQUAL notes except those containing EXPR_LISTs. */
|
|
|
912 set_src = note_src ? note_src : SET_SRC (set);
|
|
|
913
|
|
|
914 /* First substitute the SETCC condition into the JUMP instruction,
|
|
|
915 then substitute that given values into this expanded JUMP. */
|
|
|
916 if (setcc != NULL_RTX
|
|
|
917 && !modified_between_p (from, setcc, jump)
|
|
|
918 && !modified_between_p (src, setcc, jump))
|
|
|
919 {
|
|
|
920 rtx setcc_src;
|
|
|
921 rtx setcc_set = single_set (setcc);
|
|
|
922 rtx setcc_note = find_reg_equal_equiv_note (setcc);
|
|
|
923 setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
|
|
|
924 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
|
|
|
925 set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
|
|
|
926 setcc_src);
|
|
|
927 }
|
|
|
928 else
|
|
|
929 setcc = NULL;
|
|
|
930
|
|
|
931 new_rtx = simplify_replace_rtx (set_src, from, src);
|
|
|
932
|
|
|
933 /* If no simplification can be made, then try the next register. */
|
|
|
934 if (rtx_equal_p (new_rtx, SET_SRC (set)))
|
|
|
935 return 0;
|
|
|
936
|
|
|
937 /* If this is now a no-op delete it, otherwise this must be a valid insn. */
|
|
|
938 if (new_rtx == pc_rtx)
|
|
|
939 delete_insn (jump);
|
|
|
940 else
|
|
|
941 {
|
|
|
942 /* Ensure the value computed inside the jump insn to be equivalent
|
|
|
943 to one computed by setcc. */
|
|
|
944 if (setcc && modified_in_p (new_rtx, setcc))
|
|
|
945 return 0;
|
|
|
946 if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0))
|
|
|
947 {
|
|
|
948 /* When (some) constants are not valid in a comparison, and there
|
|
|
949 are two registers to be replaced by constants before the entire
|
|
|
950 comparison can be folded into a constant, we need to keep
|
|
|
951 intermediate information in REG_EQUAL notes. For targets with
|
|
|
952 separate compare insns, such notes are added by try_replace_reg.
|
|
|
953 When we have a combined compare-and-branch instruction, however,
|
|
|
954 we need to attach a note to the branch itself to make this
|
|
|
955 optimization work. */
|
|
|
956
|
|
|
957 if (!rtx_equal_p (new_rtx, note_src))
|
|
|
958 set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx));
|
|
|
959 return 0;
|
|
|
960 }
|
|
|
961
|
|
|
962 /* Remove REG_EQUAL note after simplification. */
|
|
|
963 if (note_src)
|
|
|
964 remove_note (jump, note);
|
|
|
965 }
|
|
|
966
|
|
|
967 /* Delete the cc0 setter. */
|
|
|
968 if (HAVE_cc0 && setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
|
|
|
969 delete_insn (setcc);
|
|
|
970
|
|
|
971 global_const_prop_count++;
|
|
|
972 if (dump_file != NULL)
|
|
|
973 {
|
|
|
974 fprintf (dump_file,
|
|
|
975 "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with "
|
|
|
976 "constant ", REGNO (from), INSN_UID (jump));
|
|
|
977 print_rtl (dump_file, src);
|
|
|
978 fprintf (dump_file, "\n");
|
|
|
979 }
|
|
|
980 purge_dead_edges (bb);
|
|
|
981
|
|
|
982 /* If a conditional jump has been changed into unconditional jump, remove
|
|
|
983 the jump and make the edge fallthru - this is always called in
|
|
|
984 cfglayout mode. */
|
|
|
985 if (new_rtx != pc_rtx && simplejump_p (jump))
|
|
|
986 {
|
|
|
987 edge e;
|
|
|
988 edge_iterator ei;
|
|
|
989
|
|
|
990 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
991 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
|
|
|
992 && BB_HEAD (e->dest) == JUMP_LABEL (jump))
|
|
|
993 {
|
|
|
994 e->flags |= EDGE_FALLTHRU;
|
|
|
995 break;
|
|
|
996 }
|
|
|
997 delete_insn (jump);
|
|
|
998 }
|
|
|
999
|
|
|
1000 return 1;
|
|
|
1001 }
|
|
|
1002
|
|
|
1003 /* Subroutine of cprop_insn that tries to propagate constants. FROM is what
|
|
|
1004 we will try to replace, SRC is the constant we will try to substitute for
|
|
|
1005 it and INSN is the instruction where this will be happening. */
|
|
|
1006
|
|
|
1007 static int
|
|
|
1008 constprop_register (rtx from, rtx src, rtx_insn *insn)
|
|
|
1009 {
|
|
|
1010 rtx sset;
|
|
|
1011
|
|
|
1012 /* Check for reg or cc0 setting instructions followed by
|
|
|
1013 conditional branch instructions first. */
|
|
|
1014 if ((sset = single_set (insn)) != NULL
|
|
|
1015 && NEXT_INSN (insn)
|
|
|
1016 && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
|
|
|
1017 {
|
|
|
1018 rtx dest = SET_DEST (sset);
|
|
|
1019 if ((REG_P (dest) || CC0_P (dest))
|
|
|
1020 && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn),
|
|
|
1021 from, src))
|
|
|
1022 return 1;
|
|
|
1023 }
|
|
|
1024
|
|
|
1025 /* Handle normal insns next. */
|
|
|
1026 if (NONJUMP_INSN_P (insn) && try_replace_reg (from, src, insn))
|
|
|
1027 return 1;
|
|
|
1028
|
|
|
1029 /* Try to propagate a CONST_INT into a conditional jump.
|
|
|
1030 We're pretty specific about what we will handle in this
|
|
|
1031 code, we can extend this as necessary over time.
|
|
|
1032
|
|
|
1033 Right now the insn in question must look like
|
|
|
1034 (set (pc) (if_then_else ...)) */
|
|
|
1035 else if (any_condjump_p (insn) && onlyjump_p (insn))
|
|
|
1036 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, src);
|
|
|
1037 return 0;
|
|
|
1038 }
|
|
|
1039
|
|
|
1040 /* Perform constant and copy propagation on INSN.
|
|
|
1041 Return nonzero if a change was made. */
|
|
|
1042
|
|
|
1043 static int
|
|
|
1044 cprop_insn (rtx_insn *insn)
|
|
|
1045 {
|
|
|
1046 unsigned i;
|
|
|
1047 int changed = 0, changed_this_round;
|
|
|
1048 rtx note;
|
|
|
1049
|
|
|
1050 do
|
|
|
1051 {
|
|
|
1052 changed_this_round = 0;
|
|
|
1053 reg_use_count = 0;
|
|
|
1054 note_uses (&PATTERN (insn), find_used_regs, NULL);
|
|
|
1055
|
|
|
1056 /* We may win even when propagating constants into notes. */
|
|
|
1057 note = find_reg_equal_equiv_note (insn);
|
|
|
1058 if (note)
|
|
|
1059 find_used_regs (&XEXP (note, 0), NULL);
|
|
|
1060
|
|
|
1061 for (i = 0; i < reg_use_count; i++)
|
|
|
1062 {
|
|
|
1063 rtx reg_used = reg_use_table[i];
|
|
|
1064 unsigned int regno = REGNO (reg_used);
|
|
|
1065 rtx src_cst = NULL, src_reg = NULL;
|
|
|
1066 struct cprop_expr *set[2];
|
|
|
1067
|
|
|
1068 /* If the register has already been set in this block, there's
|
|
|
1069 nothing we can do. */
|
|
|
1070 if (! reg_not_set_p (reg_used, insn))
|
|
|
1071 continue;
|
|
|
1072
|
|
|
1073 /* Find an assignment that sets reg_used and is available
|
|
|
1074 at the start of the block. */
|
|
|
1075 find_avail_set (regno, insn, set);
|
|
|
1076 if (set[0])
|
|
|
1077 src_reg = set[0]->src;
|
|
|
1078 if (set[1])
|
|
|
1079 src_cst = set[1]->src;
|
|
|
1080
|
|
|
1081 /* Constant propagation. */
|
|
|
1082 if (src_cst && cprop_constant_p (src_cst)
|
|
|
1083 && constprop_register (reg_used, src_cst, insn))
|
|
|
1084 {
|
|
|
1085 changed_this_round = changed = 1;
|
|
|
1086 global_const_prop_count++;
|
|
|
1087 if (dump_file != NULL)
|
|
|
1088 {
|
|
|
1089 fprintf (dump_file,
|
|
|
1090 "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
|
|
|
1091 fprintf (dump_file, "insn %d with constant ",
|
|
|
1092 INSN_UID (insn));
|
|
|
1093 print_rtl (dump_file, src_cst);
|
|
|
1094 fprintf (dump_file, "\n");
|
|
|
1095 }
|
|
|
1096 if (insn->deleted ())
|
|
|
1097 return 1;
|
|
|
1098 }
|
|
|
1099 /* Copy propagation. */
|
|
|
1100 else if (src_reg && cprop_reg_p (src_reg)
|
|
|
1101 && REGNO (src_reg) != regno
|
|
|
1102 && try_replace_reg (reg_used, src_reg, insn))
|
|
|
1103 {
|
|
|
1104 changed_this_round = changed = 1;
|
|
|
1105 global_copy_prop_count++;
|
|
|
1106 if (dump_file != NULL)
|
|
|
1107 {
|
|
|
1108 fprintf (dump_file,
|
|
|
1109 "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
|
|
|
1110 regno, INSN_UID (insn));
|
|
|
1111 fprintf (dump_file, " with reg %d\n", REGNO (src_reg));
|
|
|
1112 }
|
|
|
1113
|
|
|
1114 /* The original insn setting reg_used may or may not now be
|
|
|
1115 deletable. We leave the deletion to DCE. */
|
|
|
1116 /* FIXME: If it turns out that the insn isn't deletable,
|
|
|
1117 then we may have unnecessarily extended register lifetimes
|
|
|
1118 and made things worse. */
|
|
|
1119 }
|
|
|
1120 }
|
|
|
1121 }
|
|
|
1122 /* If try_replace_reg simplified the insn, the regs found by find_used_regs
|
|
|
1123 may not be valid anymore. Start over. */
|
|
|
1124 while (changed_this_round);
|
|
|
1125
|
|
|
1126 if (changed && DEBUG_INSN_P (insn))
|
|
|
1127 return 0;
|
|
|
1128
|
|
|
1129 return changed;
|
|
|
1130 }
|
|
|
1131
|
|
|
1132 /* Like find_used_regs, but avoid recording uses that appear in
|
|
|
1133 input-output contexts such as zero_extract or pre_dec. This
|
|
|
1134 restricts the cases we consider to those for which local cprop
|
|
|
1135 can legitimately make replacements. */
|
|
|
1136
|
|
|
1137 static void
|
|
|
1138 local_cprop_find_used_regs (rtx *xptr, void *data)
|
|
|
1139 {
|
|
|
1140 rtx x = *xptr;
|
|
|
1141
|
|
|
1142 if (x == 0)
|
|
|
1143 return;
|
|
|
1144
|
|
|
1145 switch (GET_CODE (x))
|
|
|
1146 {
|
|
|
1147 case ZERO_EXTRACT:
|
|
|
1148 case SIGN_EXTRACT:
|
|
|
1149 case STRICT_LOW_PART:
|
|
|
1150 return;
|
|
|
1151
|
|
|
1152 case PRE_DEC:
|
|
|
1153 case PRE_INC:
|
|
|
1154 case POST_DEC:
|
|
|
1155 case POST_INC:
|
|
|
1156 case PRE_MODIFY:
|
|
|
1157 case POST_MODIFY:
|
|
|
1158 /* Can only legitimately appear this early in the context of
|
|
|
1159 stack pushes for function arguments, but handle all of the
|
|
|
1160 codes nonetheless. */
|
|
|
1161 return;
|
|
|
1162
|
|
|
1163 case SUBREG:
|
|
|
1164 if (read_modify_subreg_p (x))
|
|
|
1165 return;
|
|
|
1166 break;
|
|
|
1167
|
|
|
1168 default:
|
|
|
1169 break;
|
|
|
1170 }
|
|
|
1171
|
|
|
1172 find_used_regs (xptr, data);
|
|
|
1173 }
|
|
|
1174
|
|
|
1175 /* Try to perform local const/copy propagation on X in INSN. */
|
|
|
1176
|
|
|
1177 static bool
|
|
|
1178 do_local_cprop (rtx x, rtx_insn *insn)
|
|
|
1179 {
|
|
|
1180 rtx newreg = NULL, newcnst = NULL;
|
|
|
1181
|
|
|
1182 /* Rule out USE instructions and ASM statements as we don't want to
|
|
|
1183 change the hard registers mentioned. */
|
|
|
1184 if (REG_P (x)
|
|
|
1185 && (cprop_reg_p (x)
|
|
|
1186 || (GET_CODE (PATTERN (insn)) != USE
|
|
|
1187 && asm_noperands (PATTERN (insn)) < 0)))
|
|
|
1188 {
|
|
|
1189 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode);
|
|
|
1190 struct elt_loc_list *l;
|
|
|
1191
|
|
|
1192 if (!val)
|
|
|
1193 return false;
|
|
|
1194 for (l = val->locs; l; l = l->next)
|
|
|
1195 {
|
|
|
1196 rtx this_rtx = l->loc;
|
|
|
1197 rtx note;
|
|
|
1198
|
|
|
1199 if (cprop_constant_p (this_rtx))
|
|
|
1200 newcnst = this_rtx;
|
|
|
1201 if (cprop_reg_p (this_rtx)
|
|
|
1202 /* Don't copy propagate if it has attached REG_EQUIV note.
|
|
|
1203 At this point this only function parameters should have
|
|
|
1204 REG_EQUIV notes and if the argument slot is used somewhere
|
|
|
1205 explicitly, it means address of parameter has been taken,
|
|
|
1206 so we should not extend the lifetime of the pseudo. */
|
|
|
1207 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
|
|
|
1208 || ! MEM_P (XEXP (note, 0))))
|
|
|
1209 newreg = this_rtx;
|
|
|
1210 }
|
|
|
1211 if (newcnst && constprop_register (x, newcnst, insn))
|
|
|
1212 {
|
|
|
1213 if (dump_file != NULL)
|
|
|
1214 {
|
|
|
1215 fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
|
|
|
1216 REGNO (x));
|
|
|
1217 fprintf (dump_file, "insn %d with constant ",
|
|
|
1218 INSN_UID (insn));
|
|
|
1219 print_rtl (dump_file, newcnst);
|
|
|
1220 fprintf (dump_file, "\n");
|
|
|
1221 }
|
|
|
1222 local_const_prop_count++;
|
|
|
1223 return true;
|
|
|
1224 }
|
|
|
1225 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
|
|
|
1226 {
|
|
|
1227 if (dump_file != NULL)
|
|
|
1228 {
|
|
|
1229 fprintf (dump_file,
|
|
|
1230 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
|
|
|
1231 REGNO (x), INSN_UID (insn));
|
|
|
1232 fprintf (dump_file, " with reg %d\n", REGNO (newreg));
|
|
|
1233 }
|
|
|
1234 local_copy_prop_count++;
|
|
|
1235 return true;
|
|
|
1236 }
|
|
|
1237 }
|
|
|
1238 return false;
|
|
|
1239 }
|
|
|
1240
|
|
|
1241 /* Do local const/copy propagation (i.e. within each basic block). */
|
|
|
1242
|
|
|
1243 static int
|
|
|
1244 local_cprop_pass (void)
|
|
|
1245 {
|
|
|
1246 basic_block bb;
|
|
|
1247 rtx_insn *insn;
|
|
|
1248 bool changed = false;
|
|
|
1249 unsigned i;
|
|
|
1250
|
|
|
1251 auto_vec<rtx_insn *> uncond_traps;
|
|
|
1252
|
|
|
1253 cselib_init (0);
|
|
|
1254 FOR_EACH_BB_FN (bb, cfun)
|
|
|
1255 {
|
|
|
1256 FOR_BB_INSNS (bb, insn)
|
|
|
1257 {
|
|
|
1258 if (INSN_P (insn))
|
|
|
1259 {
|
|
|
1260 bool was_uncond_trap
|
|
|
1261 = (GET_CODE (PATTERN (insn)) == TRAP_IF
|
|
|
1262 && XEXP (PATTERN (insn), 0) == const1_rtx);
|
|
|
1263 rtx note = find_reg_equal_equiv_note (insn);
|
|
|
1264 do
|
|
|
1265 {
|
|
|
1266 reg_use_count = 0;
|
|
|
1267 note_uses (&PATTERN (insn), local_cprop_find_used_regs,
|
|
|
1268 NULL);
|
|
|
1269 if (note)
|
|
|
1270 local_cprop_find_used_regs (&XEXP (note, 0), NULL);
|
|
|
1271
|
|
|
1272 for (i = 0; i < reg_use_count; i++)
|
|
|
1273 {
|
|
|
1274 if (do_local_cprop (reg_use_table[i], insn))
|
|
|
1275 {
|
|
|
1276 if (!DEBUG_INSN_P (insn))
|
|
|
1277 changed = true;
|
|
|
1278 break;
|
|
|
1279 }
|
|
|
1280 }
|
|
|
1281 if (!was_uncond_trap
|
|
|
1282 && GET_CODE (PATTERN (insn)) == TRAP_IF
|
|
|
1283 && XEXP (PATTERN (insn), 0) == const1_rtx)
|
|
|
1284 {
|
|
|
1285 uncond_traps.safe_push (insn);
|
|
|
1286 break;
|
|
|
1287 }
|
|
|
1288 if (insn->deleted ())
|
|
|
1289 break;
|
|
|
1290 }
|
|
|
1291 while (i < reg_use_count);
|
|
|
1292 }
|
|
|
1293 cselib_process_insn (insn);
|
|
|
1294 }
|
|
|
1295
|
|
|
1296 /* Forget everything at the end of a basic block. */
|
|
|
1297 cselib_clear_table ();
|
|
|
1298 }
|
|
|
1299
|
|
|
1300 cselib_finish ();
|
|
|
1301
|
|
|
1302 while (!uncond_traps.is_empty ())
|
|
|
1303 {
|
|
|
1304 rtx_insn *insn = uncond_traps.pop ();
|
|
|
1305 basic_block to_split = BLOCK_FOR_INSN (insn);
|
|
|
1306 remove_edge (split_block (to_split, insn));
|
|
|
1307 emit_barrier_after_bb (to_split);
|
|
|
1308 }
|
|
|
1309
|
|
|
1310 return changed;
|
|
|
1311 }
|
|
|
1312
|
|
|
1313 /* Similar to get_condition, only the resulting condition must be
|
|
|
1314 valid at JUMP, instead of at EARLIEST.
|
|
|
1315
|
|
|
1316 This differs from noce_get_condition in ifcvt.c in that we prefer not to
|
|
|
1317 settle for the condition variable in the jump instruction being integral.
|
|
|
1318 We prefer to be able to record the value of a user variable, rather than
|
|
|
1319 the value of a temporary used in a condition. This could be solved by
|
|
|
1320 recording the value of *every* register scanned by canonicalize_condition,
|
|
|
1321 but this would require some code reorganization. */
|
|
|
1322
|
|
|
1323 rtx
|
|
|
1324 fis_get_condition (rtx_insn *jump)
|
|
|
1325 {
|
|
|
1326 return get_condition (jump, NULL, false, true);
|
|
|
1327 }
|
|
|
1328
|
|
|
1329 /* Check the comparison COND to see if we can safely form an implicit
|
|
|
1330 set from it. */
|
|
|
1331
|
|
|
1332 static bool
|
|
|
1333 implicit_set_cond_p (const_rtx cond)
|
|
|
1334 {
|
|
|
1335 machine_mode mode;
|
|
|
1336 rtx cst;
|
|
|
1337
|
|
|
1338 /* COND must be either an EQ or NE comparison. */
|
|
|
1339 if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
|
|
|
1340 return false;
|
|
|
1341
|
|
|
1342 /* The first operand of COND must be a register we can propagate. */
|
|
|
1343 if (!cprop_reg_p (XEXP (cond, 0)))
|
|
|
1344 return false;
|
|
|
1345
|
|
|
1346 /* The second operand of COND must be a suitable constant. */
|
|
|
1347 mode = GET_MODE (XEXP (cond, 0));
|
|
|
1348 cst = XEXP (cond, 1);
|
|
|
1349
|
|
|
1350 /* We can't perform this optimization if either operand might be or might
|
|
|
1351 contain a signed zero. */
|
|
|
1352 if (HONOR_SIGNED_ZEROS (mode))
|
|
|
1353 {
|
|
|
1354 /* It is sufficient to check if CST is or contains a zero. We must
|
|
|
1355 handle float, complex, and vector. If any subpart is a zero, then
|
|
|
1356 the optimization can't be performed. */
|
|
|
1357 /* ??? The complex and vector checks are not implemented yet. We just
|
|
|
1358 always return zero for them. */
|
|
|
1359 if (CONST_DOUBLE_AS_FLOAT_P (cst)
|
|
|
1360 && real_equal (CONST_DOUBLE_REAL_VALUE (cst), &dconst0))
|
|
|
1361 return 0;
|
|
|
1362 else
|
|
|
1363 return 0;
|
|
|
1364 }
|
|
|
1365
|
|
|
1366 return cprop_constant_p (cst);
|
|
|
1367 }
|
|
|
1368
|
|
|
1369 /* Find the implicit sets of a function. An "implicit set" is a constraint
|
|
|
1370 on the value of a variable, implied by a conditional jump. For example,
|
|
|
1371 following "if (x == 2)", the then branch may be optimized as though the
|
|
|
1372 conditional performed an "explicit set", in this example, "x = 2". This
|
|
|
1373 function records the set patterns that are implicit at the start of each
|
|
|
1374 basic block.
|
|
|
1375
|
|
|
1376 If an implicit set is found but the set is implicit on a critical edge,
|
|
|
1377 this critical edge is split.
|
|
|
1378
|
|
|
1379 Return true if the CFG was modified, false otherwise. */
|
|
|
1380
|
|
|
1381 static bool
|
|
|
1382 find_implicit_sets (void)
|
|
|
1383 {
|
|
|
1384 basic_block bb, dest;
|
|
|
1385 rtx cond, new_rtx;
|
|
|
1386 unsigned int count = 0;
|
|
|
1387 bool edges_split = false;
|
|
|
1388 size_t implicit_sets_size = last_basic_block_for_fn (cfun) + 10;
|
|
|
1389
|
|
|
1390 implicit_sets = XCNEWVEC (rtx, implicit_sets_size);
|
|
|
1391
|
|
|
1392 FOR_EACH_BB_FN (bb, cfun)
|
|
|
1393 {
|
|
|
1394 /* Check for more than one successor. */
|
|
|
1395 if (EDGE_COUNT (bb->succs) <= 1)
|
|
|
1396 continue;
|
|
|
1397
|
|
|
1398 cond = fis_get_condition (BB_END (bb));
|
|
|
1399
|
|
|
1400 /* If no condition is found or if it isn't of a suitable form,
|
|
|
1401 ignore it. */
|
|
|
1402 if (! cond || ! implicit_set_cond_p (cond))
|
|
|
1403 continue;
|
|
|
1404
|
|
|
1405 dest = GET_CODE (cond) == EQ
|
|
|
1406 ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest;
|
|
|
1407
|
|
|
1408 /* If DEST doesn't go anywhere, ignore it. */
|
|
|
1409 if (! dest || dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
|
|
|
1410 continue;
|
|
|
1411
|
|
|
1412 /* We have found a suitable implicit set. Try to record it now as
|
|
|
1413 a SET in DEST. If DEST has more than one predecessor, the edge
|
|
|
1414 between BB and DEST is a critical edge and we must split it,
|
|
|
1415 because we can only record one implicit set per DEST basic block. */
|
|
|
1416 if (! single_pred_p (dest))
|
|
|
1417 {
|
|
|
1418 dest = split_edge (find_edge (bb, dest));
|
|
|
1419 edges_split = true;
|
|
|
1420 }
|
|
|
1421
|
|
|
1422 if (implicit_sets_size <= (size_t) dest->index)
|
|
|
1423 {
|
|
|
1424 size_t old_implicit_sets_size = implicit_sets_size;
|
|
|
1425 implicit_sets_size *= 2;
|
|
|
1426 implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size);
|
|
|
1427 memset (implicit_sets + old_implicit_sets_size, 0,
|
|
|
1428 (implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
|
|
|
1429 }
|
|
|
1430
|
|
|
1431 new_rtx = gen_rtx_SET (XEXP (cond, 0), XEXP (cond, 1));
|
|
|
1432 implicit_sets[dest->index] = new_rtx;
|
|
|
1433 if (dump_file)
|
|
|
1434 {
|
|
|
1435 fprintf (dump_file, "Implicit set of reg %d in ",
|
|
|
1436 REGNO (XEXP (cond, 0)));
|
|
|
1437 fprintf (dump_file, "basic block %d\n", dest->index);
|
|
|
1438 }
|
|
|
1439 count++;
|
|
|
1440 }
|
|
|
1441
|
|
|
1442 if (dump_file)
|
|
|
1443 fprintf (dump_file, "Found %d implicit sets\n", count);
|
|
|
1444
|
|
|
1445 /* Confess our sins. */
|
|
|
1446 return edges_split;
|
|
|
1447 }
|
|
|
1448
|
|
|
1449 /* Bypass conditional jumps. */
|
|
|
1450
|
|
|
1451 /* The value of last_basic_block at the beginning of the jump_bypass
|
|
|
1452 pass. The use of redirect_edge_and_branch_force may introduce new
|
|
|
1453 basic blocks, but the data flow analysis is only valid for basic
|
|
|
1454 block indices less than bypass_last_basic_block. */
|
|
|
1455
|
|
|
1456 static int bypass_last_basic_block;
|
|
|
1457
|
|
|
1458 /* Find a set of REGNO to a constant that is available at the end of basic
|
|
|
1459 block BB. Return NULL if no such set is found. Based heavily upon
|
|
|
1460 find_avail_set. */
|
|
|
1461
|
|
|
1462 static struct cprop_expr *
|
|
|
1463 find_bypass_set (int regno, int bb)
|
|
|
1464 {
|
|
|
1465 struct cprop_expr *result = 0;
|
|
|
1466
|
|
|
1467 for (;;)
|
|
|
1468 {
|
|
|
1469 rtx src;
|
|
|
1470 struct cprop_expr *set = lookup_set (regno, &set_hash_table);
|
|
|
1471
|
|
|
1472 while (set)
|
|
|
1473 {
|
|
|
1474 if (bitmap_bit_p (cprop_avout[bb], set->bitmap_index))
|
|
|
1475 break;
|
|
|
1476 set = next_set (regno, set);
|
|
|
1477 }
|
|
|
1478
|
|
|
1479 if (set == 0)
|
|
|
1480 break;
|
|
|
1481
|
|
|
1482 src = set->src;
|
|
|
1483 if (cprop_constant_p (src))
|
|
|
1484 result = set;
|
|
|
1485
|
|
|
1486 if (! REG_P (src))
|
|
|
1487 break;
|
|
|
1488
|
|
|
1489 regno = REGNO (src);
|
|
|
1490 }
|
|
|
1491 return result;
|
|
|
1492 }
|
|
|
1493
|
|
|
1494 /* Subroutine of bypass_block that checks whether a pseudo is killed by
|
|
|
1495 any of the instructions inserted on an edge. Jump bypassing places
|
|
|
1496 condition code setters on CFG edges using insert_insn_on_edge. This
|
|
|
1497 function is required to check that our data flow analysis is still
|
|
|
1498 valid prior to commit_edge_insertions. */
|
|
|
1499
|
|
|
1500 static bool
|
|
|
1501 reg_killed_on_edge (const_rtx reg, const_edge e)
|
|
|
1502 {
|
|
|
1503 rtx_insn *insn;
|
|
|
1504
|
|
|
1505 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
|
|
|
1506 if (INSN_P (insn) && reg_set_p (reg, insn))
|
|
|
1507 return true;
|
|
|
1508
|
|
|
1509 return false;
|
|
|
1510 }
|
|
|
1511
|
|
|
1512 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
|
|
|
1513 basic block BB which has more than one predecessor. If not NULL, SETCC
|
|
|
1514 is the first instruction of BB, which is immediately followed by JUMP_INSN
|
|
|
1515 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
|
|
|
1516 Returns nonzero if a change was made.
|
|
|
1517
|
|
|
1518 During the jump bypassing pass, we may place copies of SETCC instructions
|
|
|
1519 on CFG edges. The following routine must be careful to pay attention to
|
|
|
1520 these inserted insns when performing its transformations. */
|
|
|
1521
|
|
|
1522 static int
|
|
|
1523 bypass_block (basic_block bb, rtx_insn *setcc, rtx_insn *jump)
|
|
|
1524 {
|
|
|
1525 rtx_insn *insn;
|
|
|
1526 rtx note;
|
|
|
1527 edge e, edest;
|
|
|
1528 int change;
|
|
|
1529 int may_be_loop_header = false;
|
|
|
1530 unsigned removed_p;
|
|
|
1531 unsigned i;
|
|
|
1532 edge_iterator ei;
|
|
|
1533
|
|
|
1534 insn = (setcc != NULL) ? setcc : jump;
|
|
|
1535
|
|
|
1536 /* Determine set of register uses in INSN. */
|
|
|
1537 reg_use_count = 0;
|
|
|
1538 note_uses (&PATTERN (insn), find_used_regs, NULL);
|
|
|
1539 note = find_reg_equal_equiv_note (insn);
|
|
|
1540 if (note)
|
|
|
1541 find_used_regs (&XEXP (note, 0), NULL);
|
|
|
1542
|
|
|
1543 if (current_loops)
|
|
|
1544 {
|
|
|
1545 /* If we are to preserve loop structure then do not bypass
|
|
|
1546 a loop header. This will either rotate the loop, create
|
|
|
1547 multiple entry loops or even irreducible regions. */
|
|
|
1548 if (bb == bb->loop_father->header)
|
|
|
1549 return 0;
|
|
|
1550 }
|
|
|
1551 else
|
|
|
1552 {
|
|
|
1553 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1554 if (e->flags & EDGE_DFS_BACK)
|
|
|
1555 {
|
|
|
1556 may_be_loop_header = true;
|
|
|
1557 break;
|
|
|
1558 }
|
|
|
1559 }
|
|
|
1560
|
|
|
1561 change = 0;
|
|
|
1562 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
|
|
|
1563 {
|
|
|
1564 removed_p = 0;
|
|
|
1565
|
|
|
1566 if (e->flags & EDGE_COMPLEX)
|
|
|
1567 {
|
|
|
1568 ei_next (&ei);
|
|
|
1569 continue;
|
|
|
1570 }
|
|
|
1571
|
|
|
1572 /* We can't redirect edges from new basic blocks. */
|
|
|
1573 if (e->src->index >= bypass_last_basic_block)
|
|
|
1574 {
|
|
|
1575 ei_next (&ei);
|
|
|
1576 continue;
|
|
|
1577 }
|
|
|
1578
|
|
|
1579 /* The irreducible loops created by redirecting of edges entering the
|
|
|
1580 loop from outside would decrease effectiveness of some of the
|
|
|
1581 following optimizations, so prevent this. */
|
|
|
1582 if (may_be_loop_header
|
|
|
1583 && !(e->flags & EDGE_DFS_BACK))
|
|
|
1584 {
|
|
|
1585 ei_next (&ei);
|
|
|
1586 continue;
|
|
|
1587 }
|
|
|
1588
|
|
|
1589 for (i = 0; i < reg_use_count; i++)
|
|
|
1590 {
|
|
|
1591 rtx reg_used = reg_use_table[i];
|
|
|
1592 unsigned int regno = REGNO (reg_used);
|
|
|
1593 basic_block dest, old_dest;
|
|
|
1594 struct cprop_expr *set;
|
|
|
1595 rtx src, new_rtx;
|
|
|
1596
|
|
|
1597 set = find_bypass_set (regno, e->src->index);
|
|
|
1598
|
|
|
1599 if (! set)
|
|
|
1600 continue;
|
|
|
1601
|
|
|
1602 /* Check the data flow is valid after edge insertions. */
|
|
|
1603 if (e->insns.r && reg_killed_on_edge (reg_used, e))
|
|
|
1604 continue;
|
|
|
1605
|
|
|
1606 src = SET_SRC (pc_set (jump));
|
|
|
1607
|
|
|
1608 if (setcc != NULL)
|
|
|
1609 src = simplify_replace_rtx (src,
|
|
|
1610 SET_DEST (PATTERN (setcc)),
|
|
|
1611 SET_SRC (PATTERN (setcc)));
|
|
|
1612
|
|
|
1613 new_rtx = simplify_replace_rtx (src, reg_used, set->src);
|
|
|
1614
|
|
|
1615 /* Jump bypassing may have already placed instructions on
|
|
|
1616 edges of the CFG. We can't bypass an outgoing edge that
|
|
|
1617 has instructions associated with it, as these insns won't
|
|
|
1618 get executed if the incoming edge is redirected. */
|
|
|
1619 if (new_rtx == pc_rtx)
|
|
|
1620 {
|
|
|
1621 edest = FALLTHRU_EDGE (bb);
|
|
|
1622 dest = edest->insns.r ? NULL : edest->dest;
|
|
|
1623 }
|
|
|
1624 else if (GET_CODE (new_rtx) == LABEL_REF)
|
|
|
1625 {
|
|
|
1626 dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
|
|
|
1627 /* Don't bypass edges containing instructions. */
|
|
|
1628 edest = find_edge (bb, dest);
|
|
|
1629 if (edest && edest->insns.r)
|
|
|
1630 dest = NULL;
|
|
|
1631 }
|
|
|
1632 else
|
|
|
1633 dest = NULL;
|
|
|
1634
|
|
|
1635 /* Avoid unification of the edge with other edges from original
|
|
|
1636 branch. We would end up emitting the instruction on "both"
|
|
|
1637 edges. */
|
|
|
1638 if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
|
|
|
1639 && find_edge (e->src, dest))
|
|
|
1640 dest = NULL;
|
|
|
1641
|
|
|
1642 old_dest = e->dest;
|
|
|
1643 if (dest != NULL
|
|
|
1644 && dest != old_dest
|
|
|
1645 && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
|
|
|
1646 {
|
|
|
1647 redirect_edge_and_branch_force (e, dest);
|
|
|
1648
|
|
|
1649 /* Copy the register setter to the redirected edge.
|
|
|
1650 Don't copy CC0 setters, as CC0 is dead after jump. */
|
|
|
1651 if (setcc)
|
|
|
1652 {
|
|
|
1653 rtx pat = PATTERN (setcc);
|
|
|
1654 if (!CC0_P (SET_DEST (pat)))
|
|
|
1655 insert_insn_on_edge (copy_insn (pat), e);
|
|
|
1656 }
|
|
|
1657
|
|
|
1658 if (dump_file != NULL)
|
|
|
1659 {
|
|
|
1660 fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
|
|
|
1661 "in jump_insn %d equals constant ",
|
|
|
1662 regno, INSN_UID (jump));
|
|
|
1663 print_rtl (dump_file, set->src);
|
|
|
1664 fprintf (dump_file, "\n\t when BB %d is entered from "
|
|
|
1665 "BB %d. Redirect edge %d->%d to %d.\n",
|
|
|
1666 old_dest->index, e->src->index, e->src->index,
|
|
|
1667 old_dest->index, dest->index);
|
|
|
1668 }
|
|
|
1669 change = 1;
|
|
|
1670 removed_p = 1;
|
|
|
1671 break;
|
|
|
1672 }
|
|
|
1673 }
|
|
|
1674 if (!removed_p)
|
|
|
1675 ei_next (&ei);
|
|
|
1676 }
|
|
|
1677 return change;
|
|
|
1678 }
|
|
|
1679
|
|
|
1680 /* Find basic blocks with more than one predecessor that only contain a
|
|
|
1681 single conditional jump. If the result of the comparison is known at
|
|
|
1682 compile-time from any incoming edge, redirect that edge to the
|
|
|
1683 appropriate target. Return nonzero if a change was made.
|
|
|
1684
|
|
|
1685 This function is now mis-named, because we also handle indirect jumps. */
|
|
|
1686
|
|
|
1687 static int
|
|
|
1688 bypass_conditional_jumps (void)
|
|
|
1689 {
|
|
|
1690 basic_block bb;
|
|
|
1691 int changed;
|
|
|
1692 rtx_insn *setcc;
|
|
|
1693 rtx_insn *insn;
|
|
|
1694 rtx dest;
|
|
|
1695
|
|
|
1696 /* Note we start at block 1. */
|
|
|
1697 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
|
|
|
1698 return 0;
|
|
|
1699
|
|
|
1700 mark_dfs_back_edges ();
|
|
|
1701
|
|
|
1702 changed = 0;
|
|
|
1703 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
|
|
|
1704 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
|
|
|
1705 {
|
|
|
1706 /* Check for more than one predecessor. */
|
|
|
1707 if (!single_pred_p (bb))
|
|
|
1708 {
|
|
|
1709 setcc = NULL;
|
|
|
1710 FOR_BB_INSNS (bb, insn)
|
|
|
1711 if (DEBUG_INSN_P (insn))
|
|
|
1712 continue;
|
|
|
1713 else if (NONJUMP_INSN_P (insn))
|
|
|
1714 {
|
|
|
1715 if (setcc)
|
|
|
1716 break;
|
|
|
1717 if (GET_CODE (PATTERN (insn)) != SET)
|
|
|
1718 break;
|
|
|
1719
|
|
|
1720 dest = SET_DEST (PATTERN (insn));
|
|
|
1721 if (REG_P (dest) || CC0_P (dest))
|
|
|
1722 setcc = insn;
|
|
|
1723 else
|
|
|
1724 break;
|
|
|
1725 }
|
|
|
1726 else if (JUMP_P (insn))
|
|
|
1727 {
|
|
|
1728 if ((any_condjump_p (insn) || computed_jump_p (insn))
|
|
|
1729 && onlyjump_p (insn))
|
|
|
1730 changed |= bypass_block (bb, setcc, insn);
|
|
|
1731 break;
|
|
|
1732 }
|
|
|
1733 else if (INSN_P (insn))
|
|
|
1734 break;
|
|
|
1735 }
|
|
|
1736 }
|
|
|
1737
|
|
|
1738 /* If we bypassed any register setting insns, we inserted a
|
|
|
1739 copy on the redirected edge. These need to be committed. */
|
|
|
1740 if (changed)
|
|
|
1741 commit_edge_insertions ();
|
|
|
1742
|
|
|
1743 return changed;
|
|
|
1744 }
|
|
|
1745
|
|
|
1746 /* Main function for the CPROP pass. */
|
|
|
1747
|
|
|
1748 static int
|
|
|
1749 one_cprop_pass (void)
|
|
|
1750 {
|
|
|
1751 int i;
|
|
|
1752 int changed = 0;
|
|
|
1753
|
|
|
1754 /* Return if there's nothing to do, or it is too expensive. */
|
|
|
1755 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
|
|
|
1756 || gcse_or_cprop_is_too_expensive (_ ("const/copy propagation disabled")))
|
|
|
1757 return 0;
|
|
|
1758
|
|
|
1759 global_const_prop_count = local_const_prop_count = 0;
|
|
|
1760 global_copy_prop_count = local_copy_prop_count = 0;
|
|
|
1761
|
|
|
1762 bytes_used = 0;
|
|
|
1763 gcc_obstack_init (&cprop_obstack);
|
|
|
1764
|
|
|
1765 /* Do a local const/copy propagation pass first. The global pass
|
|
|
1766 only handles global opportunities.
|
|
|
1767 If the local pass changes something, remove any unreachable blocks
|
|
|
1768 because the CPROP global dataflow analysis may get into infinite
|
|
|
1769 loops for CFGs with unreachable blocks.
|
|
|
1770
|
|
|
1771 FIXME: This local pass should not be necessary after CSE (but for
|
|
|
1772 some reason it still is). It is also (proven) not necessary
|
|
|
1773 to run the local pass right after FWPWOP.
|
|
|
1774
|
|
|
1775 FIXME: The global analysis would not get into infinite loops if it
|
|
|
1776 would use the DF solver (via df_simple_dataflow) instead of
|
|
|
1777 the solver implemented in this file. */
|
|
|
1778 changed |= local_cprop_pass ();
|
|
|
1779 if (changed)
|
|
|
1780 delete_unreachable_blocks ();
|
|
|
1781
|
|
|
1782 /* Determine implicit sets. This may change the CFG (split critical
|
|
|
1783 edges if that exposes an implicit set).
|
|
|
1784 Note that find_implicit_sets() does not rely on up-to-date DF caches
|
|
|
1785 so that we do not have to re-run df_analyze() even if local CPROP
|
|
|
1786 changed something.
|
|
|
1787 ??? This could run earlier so that any uncovered implicit sets
|
|
|
1788 sets could be exploited in local_cprop_pass() also. Later. */
|
|
|
1789 changed |= find_implicit_sets ();
|
|
|
1790
|
|
|
1791 /* If local_cprop_pass() or find_implicit_sets() changed something,
|
|
|
1792 run df_analyze() to bring all insn caches up-to-date, and to take
|
|
|
1793 new basic blocks from edge splitting on the DF radar.
|
|
|
1794 NB: This also runs the fast DCE pass, because execute_rtl_cprop
|
|
|
1795 sets DF_LR_RUN_DCE. */
|
|
|
1796 if (changed)
|
|
|
1797 df_analyze ();
|
|
|
1798
|
|
|
1799 /* Initialize implicit_set_indexes array. */
|
|
|
1800 implicit_set_indexes = XNEWVEC (int, last_basic_block_for_fn (cfun));
|
|
|
1801 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
|
|
|
1802 implicit_set_indexes[i] = -1;
|
|
|
1803
|
|
|
1804 alloc_hash_table (&set_hash_table);
|
|
|
1805 compute_hash_table (&set_hash_table);
|
|
|
1806
|
|
|
1807 /* Free implicit_sets before peak usage. */
|
|
|
1808 free (implicit_sets);
|
|
|
1809 implicit_sets = NULL;
|
|
|
1810
|
|
|
1811 if (dump_file)
|
|
|
1812 dump_hash_table (dump_file, "SET", &set_hash_table);
|
|
|
1813 if (set_hash_table.n_elems > 0)
|
|
|
1814 {
|
|
|
1815 basic_block bb;
|
|
|
1816 auto_vec<rtx_insn *> uncond_traps;
|
|
|
1817
|
|
|
1818 alloc_cprop_mem (last_basic_block_for_fn (cfun),
|
|
|
1819 set_hash_table.n_elems);
|
|
|
1820 compute_cprop_data ();
|
|
|
1821
|
|
|
1822 free (implicit_set_indexes);
|
|
|
1823 implicit_set_indexes = NULL;
|
|
|
1824
|
|
|
1825 /* Allocate vars to track sets of regs. */
|
|
|
1826 reg_set_bitmap = ALLOC_REG_SET (NULL);
|
|
|
1827
|
|
|
1828 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
|
|
|
1829 EXIT_BLOCK_PTR_FOR_FN (cfun),
|
|
|
1830 next_bb)
|
|
|
1831 {
|
|
|
1832 bool seen_uncond_trap = false;
|
|
|
1833 rtx_insn *insn;
|
|
|
1834
|
|
|
1835 /* Reset tables used to keep track of what's still valid [since
|
|
|
1836 the start of the block]. */
|
|
|
1837 reset_opr_set_tables ();
|
|
|
1838
|
|
|
1839 FOR_BB_INSNS (bb, insn)
|
|
|
1840 if (INSN_P (insn))
|
|
|
1841 {
|
|
|
1842 bool was_uncond_trap
|
|
|
1843 = (GET_CODE (PATTERN (insn)) == TRAP_IF
|
|
|
1844 && XEXP (PATTERN (insn), 0) == const1_rtx);
|
|
|
1845
|
|
|
1846 changed |= cprop_insn (insn);
|
|
|
1847
|
|
|
1848 /* Keep track of everything modified by this insn. */
|
|
|
1849 /* ??? Need to be careful w.r.t. mods done to INSN.
|
|
|
1850 Don't call mark_oprs_set if we turned the
|
|
|
1851 insn into a NOTE, or deleted the insn. */
|
|
|
1852 if (! NOTE_P (insn) && ! insn->deleted ())
|
|
|
1853 mark_oprs_set (insn);
|
|
|
1854
|
|
|
1855 if (!was_uncond_trap
|
|
|
1856 && GET_CODE (PATTERN (insn)) == TRAP_IF
|
|
|
1857 && XEXP (PATTERN (insn), 0) == const1_rtx)
|
|
|
1858 {
|
|
|
1859 /* If we have already seen an unconditional trap
|
|
|
1860 earlier, the rest of the bb is going to be removed
|
|
|
1861 as unreachable. Just turn it into a note, so that
|
|
|
1862 RTL verification doesn't complain about it before
|
|
|
1863 it is finally removed. */
|
|
|
1864 if (seen_uncond_trap)
|
|
|
1865 set_insn_deleted (insn);
|
|
|
1866 else
|
|
|
1867 {
|
|
|
1868 seen_uncond_trap = true;
|
|
|
1869 uncond_traps.safe_push (insn);
|
|
|
1870 }
|
|
|
1871 }
|
|
|
1872 }
|
|
|
1873 }
|
|
|
1874
|
|
|
1875 /* Make sure bypass_conditional_jumps will ignore not just its new
|
|
|
1876 basic blocks, but also the ones after unconditional traps (those are
|
|
|
1877 unreachable and will be eventually removed as such). */
|
|
|
1878 bypass_last_basic_block = last_basic_block_for_fn (cfun);
|
|
|
1879
|
|
|
1880 while (!uncond_traps.is_empty ())
|
|
|
1881 {
|
|
|
1882 rtx_insn *insn = uncond_traps.pop ();
|
|
|
1883 basic_block to_split = BLOCK_FOR_INSN (insn);
|
|
|
1884 remove_edge (split_block (to_split, insn));
|
|
|
1885 emit_barrier_after_bb (to_split);
|
|
|
1886 }
|
|
|
1887
|
|
|
1888 changed |= bypass_conditional_jumps ();
|
|
|
1889
|
|
|
1890 FREE_REG_SET (reg_set_bitmap);
|
|
|
1891 free_cprop_mem ();
|
|
|
1892 }
|
|
|
1893 else
|
|
|
1894 {
|
|
|
1895 free (implicit_set_indexes);
|
|
|
1896 implicit_set_indexes = NULL;
|
|
|
1897 }
|
|
|
1898
|
|
|
1899 free_hash_table (&set_hash_table);
|
|
|
1900 obstack_free (&cprop_obstack, NULL);
|
|
|
1901
|
|
|
1902 if (dump_file)
|
|
|
1903 {
|
|
|
1904 fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
|
|
|
1905 current_function_name (), n_basic_blocks_for_fn (cfun),
|
|
|
1906 bytes_used);
|
|
|
1907 fprintf (dump_file, "%d local const props, %d local copy props, ",
|
|
|
1908 local_const_prop_count, local_copy_prop_count);
|
|
|
1909 fprintf (dump_file, "%d global const props, %d global copy props\n\n",
|
|
|
1910 global_const_prop_count, global_copy_prop_count);
|
|
|
1911 }
|
|
|
1912
|
|
|
1913 return changed;
|
|
|
1914 }
|
|
|
1915
|
|
|
1916 /* All the passes implemented in this file. Each pass has its
|
|
|
1917 own gate and execute function, and at the end of the file a
|
|
|
1918 pass definition for passes.c.
|
|
|
1919
|
|
|
1920 We do not construct an accurate cfg in functions which call
|
|
|
1921 setjmp, so none of these passes runs if the function calls
|
|
|
1922 setjmp.
|
|
|
1923 FIXME: Should just handle setjmp via REG_SETJMP notes. */
|
|
|
1924
|
|
|
1925 static unsigned int
|
|
|
1926 execute_rtl_cprop (void)
|
|
|
1927 {
|
|
|
1928 int changed;
|
|
|
1929 delete_unreachable_blocks ();
|
|
|
1930 df_set_flags (DF_LR_RUN_DCE);
|
|
|
1931 df_analyze ();
|
|
|
1932 changed = one_cprop_pass ();
|
|
|
1933 flag_rerun_cse_after_global_opts |= changed;
|
|
|
1934 if (changed)
|
|
|
1935 cleanup_cfg (CLEANUP_CFG_CHANGED);
|
|
|
1936 return 0;
|
|
|
1937 }
|
|
|
1938
|
|
|
1939 namespace {
|
|
|
1940
|
|
|
1941 const pass_data pass_data_rtl_cprop =
|
|
|
1942 {
|
|
|
1943 RTL_PASS, /* type */
|
|
|
1944 "cprop", /* name */
|
|
|
1945 OPTGROUP_NONE, /* optinfo_flags */
|
|
|
1946 TV_CPROP, /* tv_id */
|
|
|
1947 PROP_cfglayout, /* properties_required */
|
|
|
1948 0, /* properties_provided */
|
|
|
1949 0, /* properties_destroyed */
|
|
|
1950 0, /* todo_flags_start */
|
|
|
1951 TODO_df_finish, /* todo_flags_finish */
|
|
|
1952 };
|
|
|
1953
|
|
|
1954 class pass_rtl_cprop : public rtl_opt_pass
|
|
|
1955 {
|
|
|
1956 public:
|
|
|
1957 pass_rtl_cprop (gcc::context *ctxt)
|
|
|
1958 : rtl_opt_pass (pass_data_rtl_cprop, ctxt)
|
|
|
1959 {}
|
|
|
1960
|
|
|
1961 /* opt_pass methods: */
|
|
|
1962 opt_pass * clone () { return new pass_rtl_cprop (m_ctxt); }
|
|
|
1963 virtual bool gate (function *fun)
|
|
|
1964 {
|
|
|
1965 return optimize > 0 && flag_gcse
|
|
|
1966 && !fun->calls_setjmp
|
|
|
1967 && dbg_cnt (cprop);
|
|
|
1968 }
|
|
|
1969
|
|
|
1970 virtual unsigned int execute (function *) { return execute_rtl_cprop (); }
|
|
|
1971
|
|
|
1972 }; // class pass_rtl_cprop
|
|
|
1973
|
|
|
1974 } // anon namespace
|
|
|
1975
|
|
|
1976 rtl_opt_pass *
|
|
|
1977 make_pass_rtl_cprop (gcc::context *ctxt)
|
|
|
1978 {
|
|
|
1979 return new pass_rtl_cprop (ctxt);
|
|
|
1980 }
|
