1 /* Global constant/copy propagation for RTL.
2 Copyright (C) 1997-2018 Free Software Foundation, Inc.
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 *
cprop_alloc(unsigned long size)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
reg_available_p(const_rtx x,const rtx_insn * insn ATTRIBUTE_UNUSED)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
hash_mod(int regno,int hash_table_size)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
insert_set_in_table(rtx dest,rtx src,rtx_insn * insn,struct hash_table_d * table,bool implicit)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
cprop_constant_p(const_rtx x)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
cprop_reg_p(const_rtx x)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
hash_scan_set(rtx set,rtx_insn * insn,struct hash_table_d * table,bool implicit)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
hash_scan_insn(rtx_insn * insn,struct hash_table_d * table)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
dump_hash_table(FILE * file,const char * name,struct hash_table_d * table)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
make_set_regs_unavailable(rtx_insn * insn)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
compute_hash_table_work(struct hash_table_d * table)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
alloc_hash_table(struct hash_table_d * table)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
free_hash_table(struct hash_table_d * table)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
compute_hash_table(struct hash_table_d * table)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 *
lookup_set(unsigned int regno,struct hash_table_d * table)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 *
next_set(unsigned int regno,struct cprop_expr * 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
reset_opr_set_tables(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
reg_not_set_p(const_rtx x,const rtx_insn * insn ATTRIBUTE_UNUSED)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
mark_oprs_set(rtx_insn * insn)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
alloc_cprop_mem(int n_blocks,int n_sets)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
free_cprop_mem(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
compute_local_properties(sbitmap * kill,sbitmap * comp,struct hash_table_d * table)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
compute_cprop_data(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
find_used_regs(rtx * xptr,void * data ATTRIBUTE_UNUSED)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
try_replace_reg(rtx from,rtx to,rtx_insn * insn)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
find_avail_set(int regno,rtx_insn * insn,struct cprop_expr * set_ret[2])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
cprop_jump(basic_block bb,rtx_insn * setcc,rtx_insn * jump,rtx from,rtx src)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
constprop_register(rtx from,rtx src,rtx_insn * insn)1008 constprop_register (rtx from, rtx src, rtx_insn *insn)
1009 {
1010 rtx sset;
1011 rtx_insn *next_insn;
1012
1013 /* Check for reg or cc0 setting instructions followed by
1014 conditional branch instructions first. */
1015 if ((sset = single_set (insn)) != NULL
1016 && (next_insn = next_nondebug_insn (insn)) != NULL
1017 && any_condjump_p (next_insn)
1018 && onlyjump_p (next_insn))
1019 {
1020 rtx dest = SET_DEST (sset);
1021 if ((REG_P (dest) || CC0_P (dest))
1022 && cprop_jump (BLOCK_FOR_INSN (insn), insn, next_insn,
1023 from, src))
1024 return 1;
1025 }
1026
1027 /* Handle normal insns next. */
1028 if (NONJUMP_INSN_P (insn) && try_replace_reg (from, src, insn))
1029 return 1;
1030
1031 /* Try to propagate a CONST_INT into a conditional jump.
1032 We're pretty specific about what we will handle in this
1033 code, we can extend this as necessary over time.
1034
1035 Right now the insn in question must look like
1036 (set (pc) (if_then_else ...)) */
1037 else if (any_condjump_p (insn) && onlyjump_p (insn))
1038 return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, src);
1039 return 0;
1040 }
1041
1042 /* Perform constant and copy propagation on INSN.
1043 Return nonzero if a change was made. */
1044
1045 static int
cprop_insn(rtx_insn * insn)1046 cprop_insn (rtx_insn *insn)
1047 {
1048 unsigned i;
1049 int changed = 0, changed_this_round;
1050 rtx note;
1051
1052 do
1053 {
1054 changed_this_round = 0;
1055 reg_use_count = 0;
1056 note_uses (&PATTERN (insn), find_used_regs, NULL);
1057
1058 /* We may win even when propagating constants into notes. */
1059 note = find_reg_equal_equiv_note (insn);
1060 if (note)
1061 find_used_regs (&XEXP (note, 0), NULL);
1062
1063 for (i = 0; i < reg_use_count; i++)
1064 {
1065 rtx reg_used = reg_use_table[i];
1066 unsigned int regno = REGNO (reg_used);
1067 rtx src_cst = NULL, src_reg = NULL;
1068 struct cprop_expr *set[2];
1069
1070 /* If the register has already been set in this block, there's
1071 nothing we can do. */
1072 if (! reg_not_set_p (reg_used, insn))
1073 continue;
1074
1075 /* Find an assignment that sets reg_used and is available
1076 at the start of the block. */
1077 find_avail_set (regno, insn, set);
1078 if (set[0])
1079 src_reg = set[0]->src;
1080 if (set[1])
1081 src_cst = set[1]->src;
1082
1083 /* Constant propagation. */
1084 if (src_cst && cprop_constant_p (src_cst)
1085 && constprop_register (reg_used, src_cst, insn))
1086 {
1087 changed_this_round = changed = 1;
1088 global_const_prop_count++;
1089 if (dump_file != NULL)
1090 {
1091 fprintf (dump_file,
1092 "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
1093 fprintf (dump_file, "insn %d with constant ",
1094 INSN_UID (insn));
1095 print_rtl (dump_file, src_cst);
1096 fprintf (dump_file, "\n");
1097 }
1098 if (insn->deleted ())
1099 return 1;
1100 }
1101 /* Copy propagation. */
1102 else if (src_reg && cprop_reg_p (src_reg)
1103 && REGNO (src_reg) != regno
1104 && try_replace_reg (reg_used, src_reg, insn))
1105 {
1106 changed_this_round = changed = 1;
1107 global_copy_prop_count++;
1108 if (dump_file != NULL)
1109 {
1110 fprintf (dump_file,
1111 "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1112 regno, INSN_UID (insn));
1113 fprintf (dump_file, " with reg %d\n", REGNO (src_reg));
1114 }
1115
1116 /* The original insn setting reg_used may or may not now be
1117 deletable. We leave the deletion to DCE. */
1118 /* FIXME: If it turns out that the insn isn't deletable,
1119 then we may have unnecessarily extended register lifetimes
1120 and made things worse. */
1121 }
1122 }
1123 }
1124 /* If try_replace_reg simplified the insn, the regs found by find_used_regs
1125 may not be valid anymore. Start over. */
1126 while (changed_this_round);
1127
1128 if (changed && DEBUG_INSN_P (insn))
1129 return 0;
1130
1131 return changed;
1132 }
1133
1134 /* Like find_used_regs, but avoid recording uses that appear in
1135 input-output contexts such as zero_extract or pre_dec. This
1136 restricts the cases we consider to those for which local cprop
1137 can legitimately make replacements. */
1138
1139 static void
local_cprop_find_used_regs(rtx * xptr,void * data)1140 local_cprop_find_used_regs (rtx *xptr, void *data)
1141 {
1142 rtx x = *xptr;
1143
1144 if (x == 0)
1145 return;
1146
1147 switch (GET_CODE (x))
1148 {
1149 case ZERO_EXTRACT:
1150 case SIGN_EXTRACT:
1151 case STRICT_LOW_PART:
1152 return;
1153
1154 case PRE_DEC:
1155 case PRE_INC:
1156 case POST_DEC:
1157 case POST_INC:
1158 case PRE_MODIFY:
1159 case POST_MODIFY:
1160 /* Can only legitimately appear this early in the context of
1161 stack pushes for function arguments, but handle all of the
1162 codes nonetheless. */
1163 return;
1164
1165 case SUBREG:
1166 if (read_modify_subreg_p (x))
1167 return;
1168 break;
1169
1170 default:
1171 break;
1172 }
1173
1174 find_used_regs (xptr, data);
1175 }
1176
1177 /* Try to perform local const/copy propagation on X in INSN. */
1178
1179 static bool
do_local_cprop(rtx x,rtx_insn * insn)1180 do_local_cprop (rtx x, rtx_insn *insn)
1181 {
1182 rtx newreg = NULL, newcnst = NULL;
1183
1184 /* Rule out USE instructions and ASM statements as we don't want to
1185 change the hard registers mentioned. */
1186 if (REG_P (x)
1187 && (cprop_reg_p (x)
1188 || (GET_CODE (PATTERN (insn)) != USE
1189 && asm_noperands (PATTERN (insn)) < 0)))
1190 {
1191 cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode);
1192 struct elt_loc_list *l;
1193
1194 if (!val)
1195 return false;
1196 for (l = val->locs; l; l = l->next)
1197 {
1198 rtx this_rtx = l->loc;
1199 rtx note;
1200
1201 if (cprop_constant_p (this_rtx))
1202 newcnst = this_rtx;
1203 if (cprop_reg_p (this_rtx)
1204 /* Don't copy propagate if it has attached REG_EQUIV note.
1205 At this point this only function parameters should have
1206 REG_EQUIV notes and if the argument slot is used somewhere
1207 explicitly, it means address of parameter has been taken,
1208 so we should not extend the lifetime of the pseudo. */
1209 && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
1210 || ! MEM_P (XEXP (note, 0))))
1211 newreg = this_rtx;
1212 }
1213 if (newcnst && constprop_register (x, newcnst, insn))
1214 {
1215 if (dump_file != NULL)
1216 {
1217 fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
1218 REGNO (x));
1219 fprintf (dump_file, "insn %d with constant ",
1220 INSN_UID (insn));
1221 print_rtl (dump_file, newcnst);
1222 fprintf (dump_file, "\n");
1223 }
1224 local_const_prop_count++;
1225 return true;
1226 }
1227 else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
1228 {
1229 if (dump_file != NULL)
1230 {
1231 fprintf (dump_file,
1232 "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1233 REGNO (x), INSN_UID (insn));
1234 fprintf (dump_file, " with reg %d\n", REGNO (newreg));
1235 }
1236 local_copy_prop_count++;
1237 return true;
1238 }
1239 }
1240 return false;
1241 }
1242
1243 /* Do local const/copy propagation (i.e. within each basic block). */
1244
1245 static int
local_cprop_pass(void)1246 local_cprop_pass (void)
1247 {
1248 basic_block bb;
1249 rtx_insn *insn;
1250 bool changed = false;
1251 unsigned i;
1252
1253 auto_vec<rtx_insn *> uncond_traps;
1254
1255 cselib_init (0);
1256 FOR_EACH_BB_FN (bb, cfun)
1257 {
1258 FOR_BB_INSNS (bb, insn)
1259 {
1260 if (INSN_P (insn))
1261 {
1262 bool was_uncond_trap
1263 = (GET_CODE (PATTERN (insn)) == TRAP_IF
1264 && XEXP (PATTERN (insn), 0) == const1_rtx);
1265 rtx note = find_reg_equal_equiv_note (insn);
1266 do
1267 {
1268 reg_use_count = 0;
1269 note_uses (&PATTERN (insn), local_cprop_find_used_regs,
1270 NULL);
1271 if (note)
1272 local_cprop_find_used_regs (&XEXP (note, 0), NULL);
1273
1274 for (i = 0; i < reg_use_count; i++)
1275 {
1276 if (do_local_cprop (reg_use_table[i], insn))
1277 {
1278 if (!DEBUG_INSN_P (insn))
1279 changed = true;
1280 break;
1281 }
1282 }
1283 if (!was_uncond_trap
1284 && GET_CODE (PATTERN (insn)) == TRAP_IF
1285 && XEXP (PATTERN (insn), 0) == const1_rtx)
1286 {
1287 uncond_traps.safe_push (insn);
1288 break;
1289 }
1290 if (insn->deleted ())
1291 break;
1292 }
1293 while (i < reg_use_count);
1294 }
1295 cselib_process_insn (insn);
1296 }
1297
1298 /* Forget everything at the end of a basic block. */
1299 cselib_clear_table ();
1300 }
1301
1302 cselib_finish ();
1303
1304 while (!uncond_traps.is_empty ())
1305 {
1306 rtx_insn *insn = uncond_traps.pop ();
1307 basic_block to_split = BLOCK_FOR_INSN (insn);
1308 remove_edge (split_block (to_split, insn));
1309 emit_barrier_after_bb (to_split);
1310 }
1311
1312 return changed;
1313 }
1314
1315 /* Similar to get_condition, only the resulting condition must be
1316 valid at JUMP, instead of at EARLIEST.
1317
1318 This differs from noce_get_condition in ifcvt.c in that we prefer not to
1319 settle for the condition variable in the jump instruction being integral.
1320 We prefer to be able to record the value of a user variable, rather than
1321 the value of a temporary used in a condition. This could be solved by
1322 recording the value of *every* register scanned by canonicalize_condition,
1323 but this would require some code reorganization. */
1324
1325 rtx
fis_get_condition(rtx_insn * jump)1326 fis_get_condition (rtx_insn *jump)
1327 {
1328 return get_condition (jump, NULL, false, true);
1329 }
1330
1331 /* Check the comparison COND to see if we can safely form an implicit
1332 set from it. */
1333
1334 static bool
implicit_set_cond_p(const_rtx cond)1335 implicit_set_cond_p (const_rtx cond)
1336 {
1337 machine_mode mode;
1338 rtx cst;
1339
1340 /* COND must be either an EQ or NE comparison. */
1341 if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
1342 return false;
1343
1344 /* The first operand of COND must be a register we can propagate. */
1345 if (!cprop_reg_p (XEXP (cond, 0)))
1346 return false;
1347
1348 /* The second operand of COND must be a suitable constant. */
1349 mode = GET_MODE (XEXP (cond, 0));
1350 cst = XEXP (cond, 1);
1351
1352 /* We can't perform this optimization if either operand might be or might
1353 contain a signed zero. */
1354 if (HONOR_SIGNED_ZEROS (mode))
1355 {
1356 /* It is sufficient to check if CST is or contains a zero. We must
1357 handle float, complex, and vector. If any subpart is a zero, then
1358 the optimization can't be performed. */
1359 /* ??? The complex and vector checks are not implemented yet. We just
1360 always return zero for them. */
1361 if (CONST_DOUBLE_AS_FLOAT_P (cst)
1362 && real_equal (CONST_DOUBLE_REAL_VALUE (cst), &dconst0))
1363 return 0;
1364 else
1365 return 0;
1366 }
1367
1368 return cprop_constant_p (cst);
1369 }
1370
1371 /* Find the implicit sets of a function. An "implicit set" is a constraint
1372 on the value of a variable, implied by a conditional jump. For example,
1373 following "if (x == 2)", the then branch may be optimized as though the
1374 conditional performed an "explicit set", in this example, "x = 2". This
1375 function records the set patterns that are implicit at the start of each
1376 basic block.
1377
1378 If an implicit set is found but the set is implicit on a critical edge,
1379 this critical edge is split.
1380
1381 Return true if the CFG was modified, false otherwise. */
1382
1383 static bool
find_implicit_sets(void)1384 find_implicit_sets (void)
1385 {
1386 basic_block bb, dest;
1387 rtx cond, new_rtx;
1388 unsigned int count = 0;
1389 bool edges_split = false;
1390 size_t implicit_sets_size = last_basic_block_for_fn (cfun) + 10;
1391
1392 implicit_sets = XCNEWVEC (rtx, implicit_sets_size);
1393
1394 FOR_EACH_BB_FN (bb, cfun)
1395 {
1396 /* Check for more than one successor. */
1397 if (EDGE_COUNT (bb->succs) <= 1)
1398 continue;
1399
1400 cond = fis_get_condition (BB_END (bb));
1401
1402 /* If no condition is found or if it isn't of a suitable form,
1403 ignore it. */
1404 if (! cond || ! implicit_set_cond_p (cond))
1405 continue;
1406
1407 dest = GET_CODE (cond) == EQ
1408 ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest;
1409
1410 /* If DEST doesn't go anywhere, ignore it. */
1411 if (! dest || dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1412 continue;
1413
1414 /* We have found a suitable implicit set. Try to record it now as
1415 a SET in DEST. If DEST has more than one predecessor, the edge
1416 between BB and DEST is a critical edge and we must split it,
1417 because we can only record one implicit set per DEST basic block. */
1418 if (! single_pred_p (dest))
1419 {
1420 dest = split_edge (find_edge (bb, dest));
1421 edges_split = true;
1422 }
1423
1424 if (implicit_sets_size <= (size_t) dest->index)
1425 {
1426 size_t old_implicit_sets_size = implicit_sets_size;
1427 implicit_sets_size *= 2;
1428 implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size);
1429 memset (implicit_sets + old_implicit_sets_size, 0,
1430 (implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
1431 }
1432
1433 new_rtx = gen_rtx_SET (XEXP (cond, 0), XEXP (cond, 1));
1434 implicit_sets[dest->index] = new_rtx;
1435 if (dump_file)
1436 {
1437 fprintf (dump_file, "Implicit set of reg %d in ",
1438 REGNO (XEXP (cond, 0)));
1439 fprintf (dump_file, "basic block %d\n", dest->index);
1440 }
1441 count++;
1442 }
1443
1444 if (dump_file)
1445 fprintf (dump_file, "Found %d implicit sets\n", count);
1446
1447 /* Confess our sins. */
1448 return edges_split;
1449 }
1450
1451 /* Bypass conditional jumps. */
1452
1453 /* The value of last_basic_block at the beginning of the jump_bypass
1454 pass. The use of redirect_edge_and_branch_force may introduce new
1455 basic blocks, but the data flow analysis is only valid for basic
1456 block indices less than bypass_last_basic_block. */
1457
1458 static int bypass_last_basic_block;
1459
1460 /* Find a set of REGNO to a constant that is available at the end of basic
1461 block BB. Return NULL if no such set is found. Based heavily upon
1462 find_avail_set. */
1463
1464 static struct cprop_expr *
find_bypass_set(int regno,int bb)1465 find_bypass_set (int regno, int bb)
1466 {
1467 struct cprop_expr *result = 0;
1468
1469 for (;;)
1470 {
1471 rtx src;
1472 struct cprop_expr *set = lookup_set (regno, &set_hash_table);
1473
1474 while (set)
1475 {
1476 if (bitmap_bit_p (cprop_avout[bb], set->bitmap_index))
1477 break;
1478 set = next_set (regno, set);
1479 }
1480
1481 if (set == 0)
1482 break;
1483
1484 src = set->src;
1485 if (cprop_constant_p (src))
1486 result = set;
1487
1488 if (! REG_P (src))
1489 break;
1490
1491 regno = REGNO (src);
1492 }
1493 return result;
1494 }
1495
1496 /* Subroutine of bypass_block that checks whether a pseudo is killed by
1497 any of the instructions inserted on an edge. Jump bypassing places
1498 condition code setters on CFG edges using insert_insn_on_edge. This
1499 function is required to check that our data flow analysis is still
1500 valid prior to commit_edge_insertions. */
1501
1502 static bool
reg_killed_on_edge(const_rtx reg,const_edge e)1503 reg_killed_on_edge (const_rtx reg, const_edge e)
1504 {
1505 rtx_insn *insn;
1506
1507 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
1508 if (INSN_P (insn) && reg_set_p (reg, insn))
1509 return true;
1510
1511 return false;
1512 }
1513
1514 /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1515 basic block BB which has more than one predecessor. If not NULL, SETCC
1516 is the first instruction of BB, which is immediately followed by JUMP_INSN
1517 JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1518 Returns nonzero if a change was made.
1519
1520 During the jump bypassing pass, we may place copies of SETCC instructions
1521 on CFG edges. The following routine must be careful to pay attention to
1522 these inserted insns when performing its transformations. */
1523
1524 static int
bypass_block(basic_block bb,rtx_insn * setcc,rtx_insn * jump)1525 bypass_block (basic_block bb, rtx_insn *setcc, rtx_insn *jump)
1526 {
1527 rtx_insn *insn;
1528 rtx note;
1529 edge e, edest;
1530 int change;
1531 int may_be_loop_header = false;
1532 unsigned removed_p;
1533 unsigned i;
1534 edge_iterator ei;
1535
1536 insn = (setcc != NULL) ? setcc : jump;
1537
1538 /* Determine set of register uses in INSN. */
1539 reg_use_count = 0;
1540 note_uses (&PATTERN (insn), find_used_regs, NULL);
1541 note = find_reg_equal_equiv_note (insn);
1542 if (note)
1543 find_used_regs (&XEXP (note, 0), NULL);
1544
1545 if (current_loops)
1546 {
1547 /* If we are to preserve loop structure then do not bypass
1548 a loop header. This will either rotate the loop, create
1549 multiple entry loops or even irreducible regions. */
1550 if (bb == bb->loop_father->header)
1551 return 0;
1552 }
1553 else
1554 {
1555 FOR_EACH_EDGE (e, ei, bb->preds)
1556 if (e->flags & EDGE_DFS_BACK)
1557 {
1558 may_be_loop_header = true;
1559 break;
1560 }
1561 }
1562
1563 change = 0;
1564 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
1565 {
1566 removed_p = 0;
1567
1568 if (e->flags & EDGE_COMPLEX)
1569 {
1570 ei_next (&ei);
1571 continue;
1572 }
1573
1574 /* We can't redirect edges from new basic blocks. */
1575 if (e->src->index >= bypass_last_basic_block)
1576 {
1577 ei_next (&ei);
1578 continue;
1579 }
1580
1581 /* The irreducible loops created by redirecting of edges entering the
1582 loop from outside would decrease effectiveness of some of the
1583 following optimizations, so prevent this. */
1584 if (may_be_loop_header
1585 && !(e->flags & EDGE_DFS_BACK))
1586 {
1587 ei_next (&ei);
1588 continue;
1589 }
1590
1591 for (i = 0; i < reg_use_count; i++)
1592 {
1593 rtx reg_used = reg_use_table[i];
1594 unsigned int regno = REGNO (reg_used);
1595 basic_block dest, old_dest;
1596 struct cprop_expr *set;
1597 rtx src, new_rtx;
1598
1599 set = find_bypass_set (regno, e->src->index);
1600
1601 if (! set)
1602 continue;
1603
1604 /* Check the data flow is valid after edge insertions. */
1605 if (e->insns.r && reg_killed_on_edge (reg_used, e))
1606 continue;
1607
1608 src = SET_SRC (pc_set (jump));
1609
1610 if (setcc != NULL)
1611 src = simplify_replace_rtx (src,
1612 SET_DEST (PATTERN (setcc)),
1613 SET_SRC (PATTERN (setcc)));
1614
1615 new_rtx = simplify_replace_rtx (src, reg_used, set->src);
1616
1617 /* Jump bypassing may have already placed instructions on
1618 edges of the CFG. We can't bypass an outgoing edge that
1619 has instructions associated with it, as these insns won't
1620 get executed if the incoming edge is redirected. */
1621 if (new_rtx == pc_rtx)
1622 {
1623 edest = FALLTHRU_EDGE (bb);
1624 dest = edest->insns.r ? NULL : edest->dest;
1625 }
1626 else if (GET_CODE (new_rtx) == LABEL_REF)
1627 {
1628 dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
1629 /* Don't bypass edges containing instructions. */
1630 edest = find_edge (bb, dest);
1631 if (edest && edest->insns.r)
1632 dest = NULL;
1633 }
1634 else
1635 dest = NULL;
1636
1637 /* Avoid unification of the edge with other edges from original
1638 branch. We would end up emitting the instruction on "both"
1639 edges. */
1640 if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
1641 && find_edge (e->src, dest))
1642 dest = NULL;
1643
1644 old_dest = e->dest;
1645 if (dest != NULL
1646 && dest != old_dest
1647 && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1648 {
1649 redirect_edge_and_branch_force (e, dest);
1650
1651 /* Copy the register setter to the redirected edge.
1652 Don't copy CC0 setters, as CC0 is dead after jump. */
1653 if (setcc)
1654 {
1655 rtx pat = PATTERN (setcc);
1656 if (!CC0_P (SET_DEST (pat)))
1657 insert_insn_on_edge (copy_insn (pat), e);
1658 }
1659
1660 if (dump_file != NULL)
1661 {
1662 fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
1663 "in jump_insn %d equals constant ",
1664 regno, INSN_UID (jump));
1665 print_rtl (dump_file, set->src);
1666 fprintf (dump_file, "\n\t when BB %d is entered from "
1667 "BB %d. Redirect edge %d->%d to %d.\n",
1668 old_dest->index, e->src->index, e->src->index,
1669 old_dest->index, dest->index);
1670 }
1671 change = 1;
1672 removed_p = 1;
1673 break;
1674 }
1675 }
1676 if (!removed_p)
1677 ei_next (&ei);
1678 }
1679 return change;
1680 }
1681
1682 /* Find basic blocks with more than one predecessor that only contain a
1683 single conditional jump. If the result of the comparison is known at
1684 compile-time from any incoming edge, redirect that edge to the
1685 appropriate target. Return nonzero if a change was made.
1686
1687 This function is now mis-named, because we also handle indirect jumps. */
1688
1689 static int
bypass_conditional_jumps(void)1690 bypass_conditional_jumps (void)
1691 {
1692 basic_block bb;
1693 int changed;
1694 rtx_insn *setcc;
1695 rtx_insn *insn;
1696 rtx dest;
1697
1698 /* Note we start at block 1. */
1699 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1700 return 0;
1701
1702 mark_dfs_back_edges ();
1703
1704 changed = 0;
1705 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1706 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1707 {
1708 /* Check for more than one predecessor. */
1709 if (!single_pred_p (bb))
1710 {
1711 setcc = NULL;
1712 FOR_BB_INSNS (bb, insn)
1713 if (DEBUG_INSN_P (insn))
1714 continue;
1715 else if (NONJUMP_INSN_P (insn))
1716 {
1717 if (setcc)
1718 break;
1719 if (GET_CODE (PATTERN (insn)) != SET)
1720 break;
1721
1722 dest = SET_DEST (PATTERN (insn));
1723 if (REG_P (dest) || CC0_P (dest))
1724 setcc = insn;
1725 else
1726 break;
1727 }
1728 else if (JUMP_P (insn))
1729 {
1730 if ((any_condjump_p (insn) || computed_jump_p (insn))
1731 && onlyjump_p (insn))
1732 changed |= bypass_block (bb, setcc, insn);
1733 break;
1734 }
1735 else if (INSN_P (insn))
1736 break;
1737 }
1738 }
1739
1740 /* If we bypassed any register setting insns, we inserted a
1741 copy on the redirected edge. These need to be committed. */
1742 if (changed)
1743 commit_edge_insertions ();
1744
1745 return changed;
1746 }
1747
1748 /* Main function for the CPROP pass. */
1749
1750 static int
one_cprop_pass(void)1751 one_cprop_pass (void)
1752 {
1753 int i;
1754 int changed = 0;
1755
1756 /* Return if there's nothing to do, or it is too expensive. */
1757 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
1758 || gcse_or_cprop_is_too_expensive (_ ("const/copy propagation disabled")))
1759 return 0;
1760
1761 global_const_prop_count = local_const_prop_count = 0;
1762 global_copy_prop_count = local_copy_prop_count = 0;
1763
1764 bytes_used = 0;
1765 gcc_obstack_init (&cprop_obstack);
1766
1767 /* Do a local const/copy propagation pass first. The global pass
1768 only handles global opportunities.
1769 If the local pass changes something, remove any unreachable blocks
1770 because the CPROP global dataflow analysis may get into infinite
1771 loops for CFGs with unreachable blocks.
1772
1773 FIXME: This local pass should not be necessary after CSE (but for
1774 some reason it still is). It is also (proven) not necessary
1775 to run the local pass right after FWPWOP.
1776
1777 FIXME: The global analysis would not get into infinite loops if it
1778 would use the DF solver (via df_simple_dataflow) instead of
1779 the solver implemented in this file. */
1780 changed |= local_cprop_pass ();
1781 if (changed)
1782 delete_unreachable_blocks ();
1783
1784 /* Determine implicit sets. This may change the CFG (split critical
1785 edges if that exposes an implicit set).
1786 Note that find_implicit_sets() does not rely on up-to-date DF caches
1787 so that we do not have to re-run df_analyze() even if local CPROP
1788 changed something.
1789 ??? This could run earlier so that any uncovered implicit sets
1790 sets could be exploited in local_cprop_pass() also. Later. */
1791 changed |= find_implicit_sets ();
1792
1793 /* If local_cprop_pass() or find_implicit_sets() changed something,
1794 run df_analyze() to bring all insn caches up-to-date, and to take
1795 new basic blocks from edge splitting on the DF radar.
1796 NB: This also runs the fast DCE pass, because execute_rtl_cprop
1797 sets DF_LR_RUN_DCE. */
1798 if (changed)
1799 df_analyze ();
1800
1801 /* Initialize implicit_set_indexes array. */
1802 implicit_set_indexes = XNEWVEC (int, last_basic_block_for_fn (cfun));
1803 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
1804 implicit_set_indexes[i] = -1;
1805
1806 alloc_hash_table (&set_hash_table);
1807 compute_hash_table (&set_hash_table);
1808
1809 /* Free implicit_sets before peak usage. */
1810 free (implicit_sets);
1811 implicit_sets = NULL;
1812
1813 if (dump_file)
1814 dump_hash_table (dump_file, "SET", &set_hash_table);
1815 if (set_hash_table.n_elems > 0)
1816 {
1817 basic_block bb;
1818 auto_vec<rtx_insn *> uncond_traps;
1819
1820 alloc_cprop_mem (last_basic_block_for_fn (cfun),
1821 set_hash_table.n_elems);
1822 compute_cprop_data ();
1823
1824 free (implicit_set_indexes);
1825 implicit_set_indexes = NULL;
1826
1827 /* Allocate vars to track sets of regs. */
1828 reg_set_bitmap = ALLOC_REG_SET (NULL);
1829
1830 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1831 EXIT_BLOCK_PTR_FOR_FN (cfun),
1832 next_bb)
1833 {
1834 bool seen_uncond_trap = false;
1835 rtx_insn *insn;
1836
1837 /* Reset tables used to keep track of what's still valid [since
1838 the start of the block]. */
1839 reset_opr_set_tables ();
1840
1841 FOR_BB_INSNS (bb, insn)
1842 if (INSN_P (insn))
1843 {
1844 bool was_uncond_trap
1845 = (GET_CODE (PATTERN (insn)) == TRAP_IF
1846 && XEXP (PATTERN (insn), 0) == const1_rtx);
1847
1848 changed |= cprop_insn (insn);
1849
1850 /* Keep track of everything modified by this insn. */
1851 /* ??? Need to be careful w.r.t. mods done to INSN.
1852 Don't call mark_oprs_set if we turned the
1853 insn into a NOTE, or deleted the insn. */
1854 if (! NOTE_P (insn) && ! insn->deleted ())
1855 mark_oprs_set (insn);
1856
1857 if (!was_uncond_trap
1858 && GET_CODE (PATTERN (insn)) == TRAP_IF
1859 && XEXP (PATTERN (insn), 0) == const1_rtx)
1860 {
1861 /* If we have already seen an unconditional trap
1862 earlier, the rest of the bb is going to be removed
1863 as unreachable. Just turn it into a note, so that
1864 RTL verification doesn't complain about it before
1865 it is finally removed. */
1866 if (seen_uncond_trap)
1867 set_insn_deleted (insn);
1868 else
1869 {
1870 seen_uncond_trap = true;
1871 uncond_traps.safe_push (insn);
1872 }
1873 }
1874 }
1875 }
1876
1877 /* Make sure bypass_conditional_jumps will ignore not just its new
1878 basic blocks, but also the ones after unconditional traps (those are
1879 unreachable and will be eventually removed as such). */
1880 bypass_last_basic_block = last_basic_block_for_fn (cfun);
1881
1882 while (!uncond_traps.is_empty ())
1883 {
1884 rtx_insn *insn = uncond_traps.pop ();
1885 basic_block to_split = BLOCK_FOR_INSN (insn);
1886 remove_edge (split_block (to_split, insn));
1887 emit_barrier_after_bb (to_split);
1888 }
1889
1890 changed |= bypass_conditional_jumps ();
1891
1892 FREE_REG_SET (reg_set_bitmap);
1893 free_cprop_mem ();
1894 }
1895 else
1896 {
1897 free (implicit_set_indexes);
1898 implicit_set_indexes = NULL;
1899 }
1900
1901 free_hash_table (&set_hash_table);
1902 obstack_free (&cprop_obstack, NULL);
1903
1904 if (dump_file)
1905 {
1906 fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1907 current_function_name (), n_basic_blocks_for_fn (cfun),
1908 bytes_used);
1909 fprintf (dump_file, "%d local const props, %d local copy props, ",
1910 local_const_prop_count, local_copy_prop_count);
1911 fprintf (dump_file, "%d global const props, %d global copy props\n\n",
1912 global_const_prop_count, global_copy_prop_count);
1913 }
1914
1915 return changed;
1916 }
1917
1918 /* All the passes implemented in this file. Each pass has its
1919 own gate and execute function, and at the end of the file a
1920 pass definition for passes.c.
1921
1922 We do not construct an accurate cfg in functions which call
1923 setjmp, so none of these passes runs if the function calls
1924 setjmp.
1925 FIXME: Should just handle setjmp via REG_SETJMP notes. */
1926
1927 static unsigned int
execute_rtl_cprop(void)1928 execute_rtl_cprop (void)
1929 {
1930 int changed;
1931 delete_unreachable_blocks ();
1932 df_set_flags (DF_LR_RUN_DCE);
1933 df_analyze ();
1934 changed = one_cprop_pass ();
1935 flag_rerun_cse_after_global_opts |= changed;
1936 if (changed)
1937 cleanup_cfg (CLEANUP_CFG_CHANGED);
1938 return 0;
1939 }
1940
1941 namespace {
1942
1943 const pass_data pass_data_rtl_cprop =
1944 {
1945 RTL_PASS, /* type */
1946 "cprop", /* name */
1947 OPTGROUP_NONE, /* optinfo_flags */
1948 TV_CPROP, /* tv_id */
1949 PROP_cfglayout, /* properties_required */
1950 0, /* properties_provided */
1951 0, /* properties_destroyed */
1952 0, /* todo_flags_start */
1953 TODO_df_finish, /* todo_flags_finish */
1954 };
1955
1956 class pass_rtl_cprop : public rtl_opt_pass
1957 {
1958 public:
pass_rtl_cprop(gcc::context * ctxt)1959 pass_rtl_cprop (gcc::context *ctxt)
1960 : rtl_opt_pass (pass_data_rtl_cprop, ctxt)
1961 {}
1962
1963 /* opt_pass methods: */
clone()1964 opt_pass * clone () { return new pass_rtl_cprop (m_ctxt); }
gate(function * fun)1965 virtual bool gate (function *fun)
1966 {
1967 return optimize > 0 && flag_gcse
1968 && !fun->calls_setjmp
1969 && dbg_cnt (cprop);
1970 }
1971
execute(function *)1972 virtual unsigned int execute (function *) { return execute_rtl_cprop (); }
1973
1974 }; // class pass_rtl_cprop
1975
1976 } // anon namespace
1977
1978 rtl_opt_pass *
make_pass_rtl_cprop(gcc::context * ctxt)1979 make_pass_rtl_cprop (gcc::context *ctxt)
1980 {
1981 return new pass_rtl_cprop (ctxt);
1982 }
1983