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