?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
PR rtl-optimization/86620
[official-gcc.git] / gcc / df-scan.c
blob95e1e0df2d5bc78f7f3d5eafaa3ee433a14d23dc
1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 1999-2018 Free Software Foundation, Inc.
3 Originally contributed by Michael P. Hayes
4 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
5 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
6 and Kenneth Zadeck (zadeck@naturalbridge.com).
7
8 This file is part of GCC.
9
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
13 version.
14
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
23
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "backend.h"
28 #include "target.h"
29 #include "rtl.h"
30 #include "tree.h"
31 #include "df.h"
32 #include "memmodel.h"
33 #include "tm_p.h"
34 #include "regs.h"
35 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
36 #include "dumpfile.h"
37 #include "calls.h"
38
39
40 /* The set of hard registers in eliminables[i].from. */
41
42 static HARD_REG_SET elim_reg_set;
43
44 /* Initialize ur_in and ur_out as if all hard registers were partially
45 available. */
46
47 struct df_collection_rec
48 {
49 auto_vec<df_ref, 128> def_vec;
50 auto_vec<df_ref, 32> use_vec;
51 auto_vec<df_ref, 32> eq_use_vec;
52 auto_vec<df_mw_hardreg *, 32> mw_vec;
53 };
54
55 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
56 rtx, rtx *,
57 basic_block, struct df_insn_info *,
58 enum df_ref_type, int ref_flags);
59 static void df_def_record_1 (struct df_collection_rec *, rtx *,
60 basic_block, struct df_insn_info *,
61 int ref_flags);
62 static void df_defs_record (struct df_collection_rec *, rtx,
63 basic_block, struct df_insn_info *,
64 int ref_flags);
65 static void df_uses_record (struct df_collection_rec *,
66 rtx *, enum df_ref_type,
67 basic_block, struct df_insn_info *,
68 int ref_flags);
69
70 static void df_install_ref_incremental (df_ref);
71 static void df_insn_refs_collect (struct df_collection_rec*,
72 basic_block, struct df_insn_info *);
73 static void df_canonize_collection_rec (struct df_collection_rec *);
74
75 static void df_get_regular_block_artificial_uses (bitmap);
76 static void df_get_eh_block_artificial_uses (bitmap);
77
78 static void df_record_entry_block_defs (bitmap);
79 static void df_record_exit_block_uses (bitmap);
80 static void df_get_exit_block_use_set (bitmap);
81 static void df_get_entry_block_def_set (bitmap);
82 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
83 static void df_ref_chain_delete_du_chain (df_ref);
84 static void df_ref_chain_delete (df_ref);
85
86 static void df_refs_add_to_chains (struct df_collection_rec *,
87 basic_block, rtx_insn *, unsigned int);
88
89 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block,
90 rtx_insn *, bool);
91 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
92 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
93 static void df_install_ref (df_ref, struct df_reg_info *,
94 struct df_ref_info *, bool);
95
96 static int df_ref_compare (df_ref, df_ref);
97 static int df_ref_ptr_compare (const void *, const void *);
98 static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *);
99 static int df_mw_ptr_compare (const void *, const void *);
100
101 static void df_insn_info_delete (unsigned int);
102
103 /* Indexed by hardware reg number, is true if that register is ever
104 used in the current function.
105
106 In df-scan.c, this is set up to record the hard regs used
107 explicitly. Reload adds in the hard regs used for holding pseudo
108 regs. Final uses it to generate the code in the function prologue
109 and epilogue to save and restore registers as needed. */
110
111 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
112
113 /* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */
114 static const unsigned int copy_defs = 0x1;
115 static const unsigned int copy_uses = 0x2;
116 static const unsigned int copy_eq_uses = 0x4;
117 static const unsigned int copy_mw = 0x8;
118 static const unsigned int copy_all = copy_defs | copy_uses | copy_eq_uses
119 | copy_mw;
120 \f
121 /*----------------------------------------------------------------------------
122 SCANNING DATAFLOW PROBLEM
123
124 There are several ways in which scanning looks just like the other
125 dataflow problems. It shares the all the mechanisms for local info
126 as well as basic block info. Where it differs is when and how often
127 it gets run. It also has no need for the iterative solver.
128 ----------------------------------------------------------------------------*/
129
130 /* Problem data for the scanning dataflow function. */
131 struct df_scan_problem_data
132 {
133 object_allocator<df_base_ref> *ref_base_pool;
134 object_allocator<df_artificial_ref> *ref_artificial_pool;
135 object_allocator<df_regular_ref> *ref_regular_pool;
136 object_allocator<df_insn_info> *insn_pool;
137 object_allocator<df_reg_info> *reg_pool;
138 object_allocator<df_mw_hardreg> *mw_reg_pool;
139
140 bitmap_obstack reg_bitmaps;
141 bitmap_obstack insn_bitmaps;
142 };
143
144 /* Internal function to shut down the scanning problem. */
145 static void
146 df_scan_free_internal (void)
147 {
148 struct df_scan_problem_data *problem_data
149 = (struct df_scan_problem_data *) df_scan->problem_data;
150
151 free (df->def_info.refs);
152 free (df->def_info.begin);
153 free (df->def_info.count);
154 memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
155
156 free (df->use_info.refs);
157 free (df->use_info.begin);
158 free (df->use_info.count);
159 memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
160
161 free (df->def_regs);
162 df->def_regs = NULL;
163 free (df->use_regs);
164 df->use_regs = NULL;
165 free (df->eq_use_regs);
166 df->eq_use_regs = NULL;
167 df->regs_size = 0;
168 DF_REG_SIZE (df) = 0;
169
170 free (df->insns);
171 df->insns = NULL;
172 DF_INSN_SIZE () = 0;
173
174 free (df_scan->block_info);
175 df_scan->block_info = NULL;
176 df_scan->block_info_size = 0;
177
178 bitmap_clear (&df->hardware_regs_used);
179 bitmap_clear (&df->regular_block_artificial_uses);
180 bitmap_clear (&df->eh_block_artificial_uses);
181 BITMAP_FREE (df->entry_block_defs);
182 BITMAP_FREE (df->exit_block_uses);
183 bitmap_clear (&df->insns_to_delete);
184 bitmap_clear (&df->insns_to_rescan);
185 bitmap_clear (&df->insns_to_notes_rescan);
186
187 delete problem_data->ref_base_pool;
188 delete problem_data->ref_artificial_pool;
189 delete problem_data->ref_regular_pool;
190 delete problem_data->insn_pool;
191 delete problem_data->reg_pool;
192 delete problem_data->mw_reg_pool;
193 bitmap_obstack_release (&problem_data->reg_bitmaps);
194 bitmap_obstack_release (&problem_data->insn_bitmaps);
195 free (df_scan->problem_data);
196 }
197
198
199 /* Free basic block info. */
200
201 static void
202 df_scan_free_bb_info (basic_block bb, void *vbb_info)
203 {
204 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
205 unsigned int bb_index = bb->index;
206 rtx_insn *insn;
207
208 FOR_BB_INSNS (bb, insn)
209 if (INSN_P (insn))
210 df_insn_info_delete (INSN_UID (insn));
211
212 if (bb_index < df_scan->block_info_size)
213 bb_info = df_scan_get_bb_info (bb_index);
214
215 /* Get rid of any artificial uses or defs. */
216 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
217 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
218 df_ref_chain_delete (bb_info->artificial_defs);
219 df_ref_chain_delete (bb_info->artificial_uses);
220 bb_info->artificial_defs = NULL;
221 bb_info->artificial_uses = NULL;
222 }
223
224
225 /* Allocate the problem data for the scanning problem. This should be
226 called when the problem is created or when the entire function is to
227 be rescanned. */
228 void
229 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
230 {
231 struct df_scan_problem_data *problem_data;
232 unsigned int insn_num = get_max_uid () + 1;
233 basic_block bb;
234
235 /* Given the number of pools, this is really faster than tearing
236 everything apart. */
237 if (df_scan->problem_data)
238 df_scan_free_internal ();
239
240 problem_data = XNEW (struct df_scan_problem_data);
241 df_scan->problem_data = problem_data;
242 df_scan->computed = true;
243
244 problem_data->ref_base_pool = new object_allocator<df_base_ref>
245 ("df_scan ref base");
246 problem_data->ref_artificial_pool = new object_allocator<df_artificial_ref>
247 ("df_scan ref artificial");
248 problem_data->ref_regular_pool = new object_allocator<df_regular_ref>
249 ("df_scan ref regular");
250 problem_data->insn_pool = new object_allocator<df_insn_info>
251 ("df_scan insn");
252 problem_data->reg_pool = new object_allocator<df_reg_info>
253 ("df_scan reg");
254 problem_data->mw_reg_pool = new object_allocator<df_mw_hardreg>
255 ("df_scan mw_reg");
256
257 bitmap_obstack_initialize (&problem_data->reg_bitmaps);
258 bitmap_obstack_initialize (&problem_data->insn_bitmaps);
259
260 insn_num += insn_num / 4;
261 df_grow_reg_info ();
262
263 df_grow_insn_info ();
264 df_grow_bb_info (df_scan);
265
266 FOR_ALL_BB_FN (bb, cfun)
267 {
268 unsigned int bb_index = bb->index;
269 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
270 bb_info->artificial_defs = NULL;
271 bb_info->artificial_uses = NULL;
272 }
273
274 bitmap_initialize (&df->hardware_regs_used, &problem_data->reg_bitmaps);
275 bitmap_initialize (&df->regular_block_artificial_uses, &problem_data->reg_bitmaps);
276 bitmap_initialize (&df->eh_block_artificial_uses, &problem_data->reg_bitmaps);
277 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
278 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
279 bitmap_initialize (&df->insns_to_delete, &problem_data->insn_bitmaps);
280 bitmap_initialize (&df->insns_to_rescan, &problem_data->insn_bitmaps);
281 bitmap_initialize (&df->insns_to_notes_rescan, &problem_data->insn_bitmaps);
282 df_scan->optional_p = false;
283 }
284
285
286 /* Free all of the data associated with the scan problem. */
287
288 static void
289 df_scan_free (void)
290 {
291 if (df_scan->problem_data)
292 df_scan_free_internal ();
293
294 if (df->blocks_to_analyze)
295 {
296 BITMAP_FREE (df->blocks_to_analyze);
297 df->blocks_to_analyze = NULL;
298 }
299
300 free (df_scan);
301 }
302
303 /* Dump the preamble for DF_SCAN dump. */
304 static void
305 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
306 {
307 int i;
308 int dcount = 0;
309 int ucount = 0;
310 int ecount = 0;
311 int icount = 0;
312 int ccount = 0;
313 basic_block bb;
314 rtx_insn *insn;
315
316 fprintf (file, ";; invalidated by call \t");
317 df_print_regset (file, regs_invalidated_by_call_regset);
318 fprintf (file, ";; hardware regs used \t");
319 df_print_regset (file, &df->hardware_regs_used);
320 fprintf (file, ";; regular block artificial uses \t");
321 df_print_regset (file, &df->regular_block_artificial_uses);
322 fprintf (file, ";; eh block artificial uses \t");
323 df_print_regset (file, &df->eh_block_artificial_uses);
324 fprintf (file, ";; entry block defs \t");
325 df_print_regset (file, df->entry_block_defs);
326 fprintf (file, ";; exit block uses \t");
327 df_print_regset (file, df->exit_block_uses);
328 fprintf (file, ";; regs ever live \t");
329 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
330 if (df_regs_ever_live_p (i))
331 fprintf (file, " %d [%s]", i, reg_names[i]);
332 fprintf (file, "\n;; ref usage \t");
333
334 for (i = 0; i < (int)df->regs_inited; i++)
335 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
336 {
337 const char * sep = "";
338
339 fprintf (file, "r%d={", i);
340 if (DF_REG_DEF_COUNT (i))
341 {
342 fprintf (file, "%dd", DF_REG_DEF_COUNT (i));
343 sep = ",";
344 dcount += DF_REG_DEF_COUNT (i);
345 }
346 if (DF_REG_USE_COUNT (i))
347 {
348 fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i));
349 sep = ",";
350 ucount += DF_REG_USE_COUNT (i);
351 }
352 if (DF_REG_EQ_USE_COUNT (i))
353 {
354 fprintf (file, "%s%de", sep, DF_REG_EQ_USE_COUNT (i));
355 ecount += DF_REG_EQ_USE_COUNT (i);
356 }
357 fprintf (file, "} ");
358 }
359
360 FOR_EACH_BB_FN (bb, cfun)
361 FOR_BB_INSNS (bb, insn)
362 if (INSN_P (insn))
363 {
364 if (CALL_P (insn))
365 ccount++;
366 else
367 icount++;
368 }
369
370 fprintf (file, "\n;; total ref usage %d{%dd,%du,%de}"
371 " in %d{%d regular + %d call} insns.\n",
372 dcount + ucount + ecount, dcount, ucount, ecount,
373 icount + ccount, icount, ccount);
374 }
375
376 /* Dump the bb_info for a given basic block. */
377 static void
378 df_scan_start_block (basic_block bb, FILE *file)
379 {
380 struct df_scan_bb_info *bb_info
381 = df_scan_get_bb_info (bb->index);
382
383 if (bb_info)
384 {
385 fprintf (file, ";; bb %d artificial_defs: ", bb->index);
386 df_refs_chain_dump (bb_info->artificial_defs, true, file);
387 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
388 df_refs_chain_dump (bb_info->artificial_uses, true, file);
389 fprintf (file, "\n");
390 }
391 #if 0
392 {
393 rtx_insn *insn;
394 FOR_BB_INSNS (bb, insn)
395 if (INSN_P (insn))
396 df_insn_debug (insn, false, file);
397 }
398 #endif
399 }
400
401 static const struct df_problem problem_SCAN =
402 {
403 DF_SCAN, /* Problem id. */
404 DF_NONE, /* Direction. */
405 df_scan_alloc, /* Allocate the problem specific data. */
406 NULL, /* Reset global information. */
407 df_scan_free_bb_info, /* Free basic block info. */
408 NULL, /* Local compute function. */
409 NULL, /* Init the solution specific data. */
410 NULL, /* Iterative solver. */
411 NULL, /* Confluence operator 0. */
412 NULL, /* Confluence operator n. */
413 NULL, /* Transfer function. */
414 NULL, /* Finalize function. */
415 df_scan_free, /* Free all of the problem information. */
416 NULL, /* Remove this problem from the stack of dataflow problems. */
417 df_scan_start_dump, /* Debugging. */
418 df_scan_start_block, /* Debugging start block. */
419 NULL, /* Debugging end block. */
420 NULL, /* Debugging start insn. */
421 NULL, /* Debugging end insn. */
422 NULL, /* Incremental solution verify start. */
423 NULL, /* Incremental solution verify end. */
424 NULL, /* Dependent problem. */
425 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
426 TV_DF_SCAN, /* Timing variable. */
427 false /* Reset blocks on dropping out of blocks_to_analyze. */
428 };
429
430
431 /* Create a new DATAFLOW instance and add it to an existing instance
432 of DF. The returned structure is what is used to get at the
433 solution. */
434
435 void
436 df_scan_add_problem (void)
437 {
438 df_add_problem (&problem_SCAN);
439 }
440
441 \f
442 /*----------------------------------------------------------------------------
443 Storage Allocation Utilities
444 ----------------------------------------------------------------------------*/
445
446
447 /* First, grow the reg_info information. If the current size is less than
448 the number of pseudos, grow to 25% more than the number of
449 pseudos.
450
451 Second, assure that all of the slots up to max_reg_num have been
452 filled with reg_info structures. */
453
454 void
455 df_grow_reg_info (void)
456 {
457 unsigned int max_reg = max_reg_num ();
458 unsigned int new_size = max_reg;
459 struct df_scan_problem_data *problem_data
460 = (struct df_scan_problem_data *) df_scan->problem_data;
461 unsigned int i;
462
463 if (df->regs_size < new_size)
464 {
465 new_size += new_size / 4;
466 df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
467 df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
468 df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
469 new_size);
470 df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
471 df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
472 df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
473 df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
474 df->regs_size = new_size;
475 }
476
477 for (i = df->regs_inited; i < max_reg; i++)
478 {
479 struct df_reg_info *reg_info;
480
481 // TODO
482 reg_info = problem_data->reg_pool->allocate ();
483 memset (reg_info, 0, sizeof (struct df_reg_info));
484 df->def_regs[i] = reg_info;
485 reg_info = problem_data->reg_pool->allocate ();
486 memset (reg_info, 0, sizeof (struct df_reg_info));
487 df->use_regs[i] = reg_info;
488 reg_info = problem_data->reg_pool->allocate ();
489 memset (reg_info, 0, sizeof (struct df_reg_info));
490 df->eq_use_regs[i] = reg_info;
491 df->def_info.begin[i] = 0;
492 df->def_info.count[i] = 0;
493 df->use_info.begin[i] = 0;
494 df->use_info.count[i] = 0;
495 }
496
497 df->regs_inited = max_reg;
498 }
499
500
501 /* Grow the ref information. */
502
503 static void
504 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
505 {
506 if (ref_info->refs_size < new_size)
507 {
508 ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
509 memset (ref_info->refs + ref_info->refs_size, 0,
510 (new_size - ref_info->refs_size) *sizeof (df_ref));
511 ref_info->refs_size = new_size;
512 }
513 }
514
515
516 /* Check and grow the ref information if necessary. This routine
517 guarantees total_size + BITMAP_ADDEND amount of entries in refs
518 array. It updates ref_info->refs_size only and does not change
519 ref_info->total_size. */
520
521 static void
522 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
523 unsigned bitmap_addend)
524 {
525 if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
526 {
527 int new_size = ref_info->total_size + bitmap_addend;
528 new_size += ref_info->total_size / 4;
529 df_grow_ref_info (ref_info, new_size);
530 }
531 }
532
533
534 /* Grow the ref information. If the current size is less than the
535 number of instructions, grow to 25% more than the number of
536 instructions. */
537
538 void
539 df_grow_insn_info (void)
540 {
541 unsigned int new_size = get_max_uid () + 1;
542 if (DF_INSN_SIZE () < new_size)
543 {
544 new_size += new_size / 4;
545 df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
546 memset (df->insns + df->insns_size, 0,
547 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
548 DF_INSN_SIZE () = new_size;
549 }
550 }
551
552
553
554 \f
555 /*----------------------------------------------------------------------------
556 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
557 ----------------------------------------------------------------------------*/
558
559 /* Rescan all of the block_to_analyze or all of the blocks in the
560 function if df_set_blocks if blocks_to_analyze is NULL; */
561
562 void
563 df_scan_blocks (void)
564 {
565 basic_block bb;
566
567 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
568 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
569
570 df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses);
571 df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses);
572
573 bitmap_ior_into (&df->eh_block_artificial_uses,
574 &df->regular_block_artificial_uses);
575
576 /* ENTRY and EXIT blocks have special defs/uses. */
577 df_get_entry_block_def_set (df->entry_block_defs);
578 df_record_entry_block_defs (df->entry_block_defs);
579 df_get_exit_block_use_set (df->exit_block_uses);
580 df_record_exit_block_uses (df->exit_block_uses);
581 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
582 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
583
584 /* Regular blocks */
585 FOR_EACH_BB_FN (bb, cfun)
586 {
587 unsigned int bb_index = bb->index;
588 df_bb_refs_record (bb_index, true);
589 }
590 }
591
592 /* Create new refs under address LOC within INSN. This function is
593 only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
594 depending on whether LOC is inside PATTERN (INSN) or a note. */
595
596 void
597 df_uses_create (rtx *loc, rtx_insn *insn, int ref_flags)
598 {
599 gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE));
600 df_uses_record (NULL, loc, DF_REF_REG_USE,
601 BLOCK_FOR_INSN (insn),
602 DF_INSN_INFO_GET (insn),
603 ref_flags);
604 }
605
606 static void
607 df_install_ref_incremental (df_ref ref)
608 {
609 struct df_reg_info **reg_info;
610 struct df_ref_info *ref_info;
611 df_ref *ref_ptr;
612 bool add_to_table;
613
614 rtx_insn *insn = DF_REF_INSN (ref);
615 basic_block bb = BLOCK_FOR_INSN (insn);
616
617 if (DF_REF_REG_DEF_P (ref))
618 {
619 reg_info = df->def_regs;
620 ref_info = &df->def_info;
621 ref_ptr = &DF_INSN_DEFS (insn);
622 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
623 }
624 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
625 {
626 reg_info = df->eq_use_regs;
627 ref_info = &df->use_info;
628 ref_ptr = &DF_INSN_EQ_USES (insn);
629 switch (ref_info->ref_order)
630 {
631 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
632 case DF_REF_ORDER_BY_REG_WITH_NOTES:
633 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
634 add_to_table = true;
635 break;
636 default:
637 add_to_table = false;
638 break;
639 }
640 }
641 else
642 {
643 reg_info = df->use_regs;
644 ref_info = &df->use_info;
645 ref_ptr = &DF_INSN_USES (insn);
646 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
647 }
648
649 /* Do not add if ref is not in the right blocks. */
650 if (add_to_table && df->analyze_subset)
651 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
652
653 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
654
655 if (add_to_table)
656 switch (ref_info->ref_order)
657 {
658 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
659 case DF_REF_ORDER_BY_REG_WITH_NOTES:
660 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
661 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
662 break;
663 default:
664 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
665 break;
666 }
667
668 while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0)
669 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
670
671 DF_REF_NEXT_LOC (ref) = *ref_ptr;
672 *ref_ptr = ref;
673
674 #if 0
675 if (dump_file)
676 {
677 fprintf (dump_file, "adding ref ");
678 df_ref_debug (ref, dump_file);
679 }
680 #endif
681 /* By adding the ref directly, df_insn_rescan my not find any
682 differences even though the block will have changed. So we need
683 to mark the block dirty ourselves. */
684 if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
685 df_set_bb_dirty (bb);
686 }
687
688
689 \f
690 /*----------------------------------------------------------------------------
691 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
692 ----------------------------------------------------------------------------*/
693
694 static void
695 df_free_ref (df_ref ref)
696 {
697 struct df_scan_problem_data *problem_data
698 = (struct df_scan_problem_data *) df_scan->problem_data;
699
700 switch (DF_REF_CLASS (ref))
701 {
702 case DF_REF_BASE:
703 problem_data->ref_base_pool->remove ((df_base_ref *) (ref));
704 break;
705
706 case DF_REF_ARTIFICIAL:
707 problem_data->ref_artificial_pool->remove
708 ((df_artificial_ref *) (ref));
709 break;
710
711 case DF_REF_REGULAR:
712 problem_data->ref_regular_pool->remove
713 ((df_regular_ref *) (ref));
714 break;
715 }
716 }
717
718
719 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
720 Also delete the def-use or use-def chain if it exists. */
721
722 static void
723 df_reg_chain_unlink (df_ref ref)
724 {
725 df_ref next = DF_REF_NEXT_REG (ref);
726 df_ref prev = DF_REF_PREV_REG (ref);
727 int id = DF_REF_ID (ref);
728 struct df_reg_info *reg_info;
729 df_ref *refs = NULL;
730
731 if (DF_REF_REG_DEF_P (ref))
732 {
733 int regno = DF_REF_REGNO (ref);
734 reg_info = DF_REG_DEF_GET (regno);
735 refs = df->def_info.refs;
736 }
737 else
738 {
739 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
740 {
741 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
742 switch (df->use_info.ref_order)
743 {
744 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
745 case DF_REF_ORDER_BY_REG_WITH_NOTES:
746 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
747 refs = df->use_info.refs;
748 break;
749 default:
750 break;
751 }
752 }
753 else
754 {
755 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
756 refs = df->use_info.refs;
757 }
758 }
759
760 if (refs)
761 {
762 if (df->analyze_subset)
763 {
764 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
765 refs[id] = NULL;
766 }
767 else
768 refs[id] = NULL;
769 }
770
771 /* Delete any def-use or use-def chains that start here. It is
772 possible that there is trash in this field. This happens for
773 insns that have been deleted when rescanning has been deferred
774 and the chain problem has also been deleted. The chain tear down
775 code skips deleted insns. */
776 if (df_chain && DF_REF_CHAIN (ref))
777 df_chain_unlink (ref);
778
779 reg_info->n_refs--;
780 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
781 {
782 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
783 df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
784 }
785
786 /* Unlink from the reg chain. If there is no prev, this is the
787 first of the list. If not, just join the next and prev. */
788 if (prev)
789 DF_REF_NEXT_REG (prev) = next;
790 else
791 {
792 gcc_assert (reg_info->reg_chain == ref);
793 reg_info->reg_chain = next;
794 }
795 if (next)
796 DF_REF_PREV_REG (next) = prev;
797
798 df_free_ref (ref);
799 }
800
801 /* Initialize INSN_INFO to describe INSN. */
802
803 static void
804 df_insn_info_init_fields (df_insn_info *insn_info, rtx_insn *insn)
805 {
806 memset (insn_info, 0, sizeof (struct df_insn_info));
807 insn_info->insn = insn;
808 }
809
810 /* Create the insn record for INSN. If there was one there, zero it
811 out. */
812
813 struct df_insn_info *
814 df_insn_create_insn_record (rtx_insn *insn)
815 {
816 struct df_scan_problem_data *problem_data
817 = (struct df_scan_problem_data *) df_scan->problem_data;
818 struct df_insn_info *insn_rec;
819
820 df_grow_insn_info ();
821 insn_rec = DF_INSN_INFO_GET (insn);
822 if (!insn_rec)
823 {
824 insn_rec = problem_data->insn_pool->allocate ();
825 DF_INSN_INFO_SET (insn, insn_rec);
826 }
827 df_insn_info_init_fields (insn_rec, insn);
828 return insn_rec;
829 }
830
831
832 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
833
834 static void
835 df_ref_chain_delete_du_chain (df_ref ref)
836 {
837 for (; ref; ref = DF_REF_NEXT_LOC (ref))
838 /* CHAIN is allocated by DF_CHAIN. So make sure to
839 pass df_scan instance for the problem. */
840 if (DF_REF_CHAIN (ref))
841 df_chain_unlink (ref);
842 }
843
844
845 /* Delete all refs in the ref chain. */
846
847 static void
848 df_ref_chain_delete (df_ref ref)
849 {
850 df_ref next;
851 for (; ref; ref = next)
852 {
853 next = DF_REF_NEXT_LOC (ref);
854 df_reg_chain_unlink (ref);
855 }
856 }
857
858
859 /* Delete the hardreg chain. */
860
861 static void
862 df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs)
863 {
864 struct df_scan_problem_data *problem_data
865 = (struct df_scan_problem_data *) df_scan->problem_data;
866 df_mw_hardreg *next;
867
868 for (; hardregs; hardregs = next)
869 {
870 next = DF_MWS_NEXT (hardregs);
871 problem_data->mw_reg_pool->remove (hardregs);
872 }
873 }
874
875 /* Remove the contents of INSN_INFO (but don't free INSN_INFO itself). */
876
877 static void
878 df_insn_info_free_fields (df_insn_info *insn_info)
879 {
880 /* In general, notes do not have the insn_info fields
881 initialized. However, combine deletes insns by changing them
882 to notes. How clever. So we cannot just check if it is a
883 valid insn before short circuiting this code, we need to see
884 if we actually initialized it. */
885 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
886
887 if (df_chain)
888 {
889 df_ref_chain_delete_du_chain (insn_info->defs);
890 df_ref_chain_delete_du_chain (insn_info->uses);
891 df_ref_chain_delete_du_chain (insn_info->eq_uses);
892 }
893
894 df_ref_chain_delete (insn_info->defs);
895 df_ref_chain_delete (insn_info->uses);
896 df_ref_chain_delete (insn_info->eq_uses);
897 }
898
899 /* Delete all of the refs information from the insn with UID.
900 Internal helper for df_insn_delete, df_insn_rescan, and other
901 df-scan routines that don't have to work in deferred mode
902 and do not have to mark basic blocks for re-processing. */
903
904 static void
905 df_insn_info_delete (unsigned int uid)
906 {
907 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
908
909 bitmap_clear_bit (&df->insns_to_delete, uid);
910 bitmap_clear_bit (&df->insns_to_rescan, uid);
911 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
912 if (insn_info)
913 {
914 struct df_scan_problem_data *problem_data
915 = (struct df_scan_problem_data *) df_scan->problem_data;
916
917 df_insn_info_free_fields (insn_info);
918 problem_data->insn_pool->remove (insn_info);
919 DF_INSN_UID_SET (uid, NULL);
920 }
921 }
922
923 /* Delete all of the refs information from INSN, either right now
924 or marked for later in deferred mode. */
925
926 void
927 df_insn_delete (rtx_insn *insn)
928 {
929 unsigned int uid;
930 basic_block bb;
931
932 gcc_checking_assert (INSN_P (insn));
933
934 if (!df)
935 return;
936
937 uid = INSN_UID (insn);
938 bb = BLOCK_FOR_INSN (insn);
939
940 /* ??? bb can be NULL after pass_free_cfg. At that point, DF should
941 not exist anymore (as mentioned in df-core.c: "The only requirement
942 [for DF] is that there be a correct control flow graph." Clearly
943 that isn't the case after pass_free_cfg. But DF is freed much later
944 because some back-ends want to use DF info even though the CFG is
945 already gone. It's not clear to me whether that is safe, actually.
946 In any case, we expect BB to be non-NULL at least up to register
947 allocation, so disallow a non-NULL BB up to there. Not perfect
948 but better than nothing... */
949 gcc_checking_assert (bb != NULL || reload_completed);
950
951 df_grow_bb_info (df_scan);
952 df_grow_reg_info ();
953
954 /* The block must be marked as dirty now, rather than later as in
955 df_insn_rescan and df_notes_rescan because it may not be there at
956 rescanning time and the mark would blow up.
957 DEBUG_INSNs do not make a block's data flow solution dirty (at
958 worst the LUIDs are no longer contiguous). */
959 if (bb != NULL && NONDEBUG_INSN_P (insn))
960 df_set_bb_dirty (bb);
961
962 /* The client has deferred rescanning. */
963 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
964 {
965 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
966 if (insn_info)
967 {
968 bitmap_clear_bit (&df->insns_to_rescan, uid);
969 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
970 bitmap_set_bit (&df->insns_to_delete, uid);
971 }
972 if (dump_file)
973 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
974 return;
975 }
976
977 if (dump_file)
978 fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
979
980 df_insn_info_delete (uid);
981 }
982
983
984 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
985
986 static void
987 df_free_collection_rec (struct df_collection_rec *collection_rec)
988 {
989 unsigned int ix;
990 struct df_scan_problem_data *problem_data
991 = (struct df_scan_problem_data *) df_scan->problem_data;
992 df_ref ref;
993 struct df_mw_hardreg *mw;
994
995 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
996 df_free_ref (ref);
997 FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref)
998 df_free_ref (ref);
999 FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref)
1000 df_free_ref (ref);
1001 FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw)
1002 problem_data->mw_reg_pool->remove (mw);
1003
1004 collection_rec->def_vec.release ();
1005 collection_rec->use_vec.release ();
1006 collection_rec->eq_use_vec.release ();
1007 collection_rec->mw_vec.release ();
1008 }
1009
1010 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1011
1012 bool
1013 df_insn_rescan (rtx_insn *insn)
1014 {
1015 unsigned int uid = INSN_UID (insn);
1016 struct df_insn_info *insn_info = NULL;
1017 basic_block bb = BLOCK_FOR_INSN (insn);
1018 struct df_collection_rec collection_rec;
1019
1020 if ((!df) || (!INSN_P (insn)))
1021 return false;
1022
1023 if (!bb)
1024 {
1025 if (dump_file)
1026 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1027 return false;
1028 }
1029
1030 /* The client has disabled rescanning and plans to do it itself. */
1031 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1032 return false;
1033
1034 df_grow_bb_info (df_scan);
1035 df_grow_reg_info ();
1036
1037 insn_info = DF_INSN_UID_SAFE_GET (uid);
1038
1039 /* The client has deferred rescanning. */
1040 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1041 {
1042 if (!insn_info)
1043 {
1044 insn_info = df_insn_create_insn_record (insn);
1045 insn_info->defs = 0;
1046 insn_info->uses = 0;
1047 insn_info->eq_uses = 0;
1048 insn_info->mw_hardregs = 0;
1049 }
1050 if (dump_file)
1051 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1052
1053 bitmap_clear_bit (&df->insns_to_delete, uid);
1054 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1055 bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn));
1056 return false;
1057 }
1058
1059 bitmap_clear_bit (&df->insns_to_delete, uid);
1060 bitmap_clear_bit (&df->insns_to_rescan, uid);
1061 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1062 if (insn_info)
1063 {
1064 int luid;
1065 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1066 /* If there's no change, return false. */
1067 if (the_same)
1068 {
1069 df_free_collection_rec (&collection_rec);
1070 if (dump_file)
1071 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1072 return false;
1073 }
1074 if (dump_file)
1075 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1076
1077 /* There's change - we need to delete the existing info.
1078 Since the insn isn't moved, we can salvage its LUID. */
1079 luid = DF_INSN_LUID (insn);
1080 df_insn_info_free_fields (insn_info);
1081 df_insn_info_init_fields (insn_info, insn);
1082 DF_INSN_LUID (insn) = luid;
1083 }
1084 else
1085 {
1086 struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1087 df_insn_refs_collect (&collection_rec, bb, insn_info);
1088 if (dump_file)
1089 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1090 }
1091
1092 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
1093 if (!DEBUG_INSN_P (insn))
1094 df_set_bb_dirty (bb);
1095
1096 return true;
1097 }
1098
1099 /* Same as df_insn_rescan, but don't mark the basic block as
1100 dirty. */
1101
1102 bool
1103 df_insn_rescan_debug_internal (rtx_insn *insn)
1104 {
1105 unsigned int uid = INSN_UID (insn);
1106 struct df_insn_info *insn_info;
1107
1108 gcc_assert (DEBUG_INSN_P (insn)
1109 && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)));
1110
1111 if (!df)
1112 return false;
1113
1114 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1115 if (!insn_info)
1116 return false;
1117
1118 if (dump_file)
1119 fprintf (dump_file, "deleting debug_insn with uid = %d.\n", uid);
1120
1121 bitmap_clear_bit (&df->insns_to_delete, uid);
1122 bitmap_clear_bit (&df->insns_to_rescan, uid);
1123 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1124
1125 if (insn_info->defs == 0
1126 && insn_info->uses == 0
1127 && insn_info->eq_uses == 0
1128 && insn_info->mw_hardregs == 0)
1129 return false;
1130
1131 df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1132
1133 if (df_chain)
1134 {
1135 df_ref_chain_delete_du_chain (insn_info->defs);
1136 df_ref_chain_delete_du_chain (insn_info->uses);
1137 df_ref_chain_delete_du_chain (insn_info->eq_uses);
1138 }
1139
1140 df_ref_chain_delete (insn_info->defs);
1141 df_ref_chain_delete (insn_info->uses);
1142 df_ref_chain_delete (insn_info->eq_uses);
1143
1144 insn_info->defs = 0;
1145 insn_info->uses = 0;
1146 insn_info->eq_uses = 0;
1147 insn_info->mw_hardregs = 0;
1148
1149 return true;
1150 }
1151
1152
1153 /* Rescan all of the insns in the function. Note that the artificial
1154 uses and defs are not touched. This function will destroy def-use
1155 or use-def chains. */
1156
1157 void
1158 df_insn_rescan_all (void)
1159 {
1160 bool no_insn_rescan = false;
1161 bool defer_insn_rescan = false;
1162 basic_block bb;
1163 bitmap_iterator bi;
1164 unsigned int uid;
1165
1166 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1167 {
1168 df_clear_flags (DF_NO_INSN_RESCAN);
1169 no_insn_rescan = true;
1170 }
1171
1172 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1173 {
1174 df_clear_flags (DF_DEFER_INSN_RESCAN);
1175 defer_insn_rescan = true;
1176 }
1177
1178 auto_bitmap tmp (&df_bitmap_obstack);
1179 bitmap_copy (tmp, &df->insns_to_delete);
1180 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1181 {
1182 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1183 if (insn_info)
1184 df_insn_info_delete (uid);
1185 }
1186
1187 bitmap_clear (&df->insns_to_delete);
1188 bitmap_clear (&df->insns_to_rescan);
1189 bitmap_clear (&df->insns_to_notes_rescan);
1190
1191 FOR_EACH_BB_FN (bb, cfun)
1192 {
1193 rtx_insn *insn;
1194 FOR_BB_INSNS (bb, insn)
1195 {
1196 df_insn_rescan (insn);
1197 }
1198 }
1199
1200 if (no_insn_rescan)
1201 df_set_flags (DF_NO_INSN_RESCAN);
1202 if (defer_insn_rescan)
1203 df_set_flags (DF_DEFER_INSN_RESCAN);
1204 }
1205
1206
1207 /* Process all of the deferred rescans or deletions. */
1208
1209 void
1210 df_process_deferred_rescans (void)
1211 {
1212 bool no_insn_rescan = false;
1213 bool defer_insn_rescan = false;
1214 bitmap_iterator bi;
1215 unsigned int uid;
1216
1217 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1218 {
1219 df_clear_flags (DF_NO_INSN_RESCAN);
1220 no_insn_rescan = true;
1221 }
1222
1223 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1224 {
1225 df_clear_flags (DF_DEFER_INSN_RESCAN);
1226 defer_insn_rescan = true;
1227 }
1228
1229 if (dump_file)
1230 fprintf (dump_file, "starting the processing of deferred insns\n");
1231
1232 auto_bitmap tmp (&df_bitmap_obstack);
1233 bitmap_copy (tmp, &df->insns_to_delete);
1234 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1235 {
1236 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1237 if (insn_info)
1238 df_insn_info_delete (uid);
1239 }
1240
1241 bitmap_copy (tmp, &df->insns_to_rescan);
1242 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1243 {
1244 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1245 if (insn_info)
1246 df_insn_rescan (insn_info->insn);
1247 }
1248
1249 bitmap_copy (tmp, &df->insns_to_notes_rescan);
1250 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1251 {
1252 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1253 if (insn_info)
1254 df_notes_rescan (insn_info->insn);
1255 }
1256
1257 if (dump_file)
1258 fprintf (dump_file, "ending the processing of deferred insns\n");
1259
1260 bitmap_clear (&df->insns_to_delete);
1261 bitmap_clear (&df->insns_to_rescan);
1262 bitmap_clear (&df->insns_to_notes_rescan);
1263
1264 if (no_insn_rescan)
1265 df_set_flags (DF_NO_INSN_RESCAN);
1266 if (defer_insn_rescan)
1267 df_set_flags (DF_DEFER_INSN_RESCAN);
1268
1269 /* If someone changed regs_ever_live during this pass, fix up the
1270 entry and exit blocks. */
1271 if (df->redo_entry_and_exit)
1272 {
1273 df_update_entry_exit_and_calls ();
1274 df->redo_entry_and_exit = false;
1275 }
1276 }
1277
1278
1279 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1280 the uses if INCLUDE_USES. Include the eq_uses if
1281 INCLUDE_EQ_USES. */
1282
1283 static unsigned int
1284 df_count_refs (bool include_defs, bool include_uses,
1285 bool include_eq_uses)
1286 {
1287 unsigned int regno;
1288 int size = 0;
1289 unsigned int m = df->regs_inited;
1290
1291 for (regno = 0; regno < m; regno++)
1292 {
1293 if (include_defs)
1294 size += DF_REG_DEF_COUNT (regno);
1295 if (include_uses)
1296 size += DF_REG_USE_COUNT (regno);
1297 if (include_eq_uses)
1298 size += DF_REG_EQ_USE_COUNT (regno);
1299 }
1300 return size;
1301 }
1302
1303
1304 /* Take build ref table for either the uses or defs from the reg-use
1305 or reg-def chains. This version processes the refs in reg order
1306 which is likely to be best if processing the whole function. */
1307
1308 static void
1309 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1310 bool include_defs,
1311 bool include_uses,
1312 bool include_eq_uses)
1313 {
1314 unsigned int m = df->regs_inited;
1315 unsigned int regno;
1316 unsigned int offset = 0;
1317 unsigned int start;
1318
1319 if (df->changeable_flags & DF_NO_HARD_REGS)
1320 {
1321 start = FIRST_PSEUDO_REGISTER;
1322 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1323 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1324 }
1325 else
1326 start = 0;
1327
1328 ref_info->total_size
1329 = df_count_refs (include_defs, include_uses, include_eq_uses);
1330
1331 df_check_and_grow_ref_info (ref_info, 1);
1332
1333 for (regno = start; regno < m; regno++)
1334 {
1335 int count = 0;
1336 ref_info->begin[regno] = offset;
1337 if (include_defs)
1338 {
1339 df_ref ref = DF_REG_DEF_CHAIN (regno);
1340 while (ref)
1341 {
1342 ref_info->refs[offset] = ref;
1343 DF_REF_ID (ref) = offset++;
1344 count++;
1345 ref = DF_REF_NEXT_REG (ref);
1346 gcc_checking_assert (offset < ref_info->refs_size);
1347 }
1348 }
1349 if (include_uses)
1350 {
1351 df_ref ref = DF_REG_USE_CHAIN (regno);
1352 while (ref)
1353 {
1354 ref_info->refs[offset] = ref;
1355 DF_REF_ID (ref) = offset++;
1356 count++;
1357 ref = DF_REF_NEXT_REG (ref);
1358 gcc_checking_assert (offset < ref_info->refs_size);
1359 }
1360 }
1361 if (include_eq_uses)
1362 {
1363 df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1364 while (ref)
1365 {
1366 ref_info->refs[offset] = ref;
1367 DF_REF_ID (ref) = offset++;
1368 count++;
1369 ref = DF_REF_NEXT_REG (ref);
1370 gcc_checking_assert (offset < ref_info->refs_size);
1371 }
1372 }
1373 ref_info->count[regno] = count;
1374 }
1375
1376 /* The bitmap size is not decremented when refs are deleted. So
1377 reset it now that we have squished out all of the empty
1378 slots. */
1379 ref_info->table_size = offset;
1380 }
1381
1382
1383 /* Take build ref table for either the uses or defs from the reg-use
1384 or reg-def chains. This version processes the refs in insn order
1385 which is likely to be best if processing some segment of the
1386 function. */
1387
1388 static void
1389 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1390 bool include_defs,
1391 bool include_uses,
1392 bool include_eq_uses)
1393 {
1394 bitmap_iterator bi;
1395 unsigned int bb_index;
1396 unsigned int m = df->regs_inited;
1397 unsigned int offset = 0;
1398 unsigned int r;
1399 unsigned int start
1400 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1401
1402 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1403 memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1404
1405 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1406 df_check_and_grow_ref_info (ref_info, 1);
1407
1408 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1409 {
1410 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1411 rtx_insn *insn;
1412 df_ref def, use;
1413
1414 if (include_defs)
1415 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1416 {
1417 unsigned int regno = DF_REF_REGNO (def);
1418 ref_info->count[regno]++;
1419 }
1420 if (include_uses)
1421 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1422 {
1423 unsigned int regno = DF_REF_REGNO (use);
1424 ref_info->count[regno]++;
1425 }
1426
1427 FOR_BB_INSNS (bb, insn)
1428 {
1429 if (INSN_P (insn))
1430 {
1431 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1432
1433 if (include_defs)
1434 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1435 {
1436 unsigned int regno = DF_REF_REGNO (def);
1437 ref_info->count[regno]++;
1438 }
1439 if (include_uses)
1440 FOR_EACH_INSN_INFO_USE (use, insn_info)
1441 {
1442 unsigned int regno = DF_REF_REGNO (use);
1443 ref_info->count[regno]++;
1444 }
1445 if (include_eq_uses)
1446 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1447 {
1448 unsigned int regno = DF_REF_REGNO (use);
1449 ref_info->count[regno]++;
1450 }
1451 }
1452 }
1453 }
1454
1455 for (r = start; r < m; r++)
1456 {
1457 ref_info->begin[r] = offset;
1458 offset += ref_info->count[r];
1459 ref_info->count[r] = 0;
1460 }
1461
1462 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1463 {
1464 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1465 rtx_insn *insn;
1466 df_ref def, use;
1467
1468 if (include_defs)
1469 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1470 {
1471 unsigned int regno = DF_REF_REGNO (def);
1472 if (regno >= start)
1473 {
1474 unsigned int id
1475 = ref_info->begin[regno] + ref_info->count[regno]++;
1476 DF_REF_ID (def) = id;
1477 ref_info->refs[id] = def;
1478 }
1479 }
1480 if (include_uses)
1481 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1482 {
1483 unsigned int regno = DF_REF_REGNO (def);
1484 if (regno >= start)
1485 {
1486 unsigned int id
1487 = ref_info->begin[regno] + ref_info->count[regno]++;
1488 DF_REF_ID (use) = id;
1489 ref_info->refs[id] = use;
1490 }
1491 }
1492
1493 FOR_BB_INSNS (bb, insn)
1494 {
1495 if (INSN_P (insn))
1496 {
1497 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1498
1499 if (include_defs)
1500 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1501 {
1502 unsigned int regno = DF_REF_REGNO (def);
1503 if (regno >= start)
1504 {
1505 unsigned int id
1506 = ref_info->begin[regno] + ref_info->count[regno]++;
1507 DF_REF_ID (def) = id;
1508 ref_info->refs[id] = def;
1509 }
1510 }
1511 if (include_uses)
1512 FOR_EACH_INSN_INFO_USE (use, insn_info)
1513 {
1514 unsigned int regno = DF_REF_REGNO (use);
1515 if (regno >= start)
1516 {
1517 unsigned int id
1518 = ref_info->begin[regno] + ref_info->count[regno]++;
1519 DF_REF_ID (use) = id;
1520 ref_info->refs[id] = use;
1521 }
1522 }
1523 if (include_eq_uses)
1524 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1525 {
1526 unsigned int regno = DF_REF_REGNO (use);
1527 if (regno >= start)
1528 {
1529 unsigned int id
1530 = ref_info->begin[regno] + ref_info->count[regno]++;
1531 DF_REF_ID (use) = id;
1532 ref_info->refs[id] = use;
1533 }
1534 }
1535 }
1536 }
1537 }
1538
1539 /* The bitmap size is not decremented when refs are deleted. So
1540 reset it now that we have squished out all of the empty
1541 slots. */
1542
1543 ref_info->table_size = offset;
1544 }
1545
1546 /* Take build ref table for either the uses or defs from the reg-use
1547 or reg-def chains. */
1548
1549 static void
1550 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1551 bool include_defs,
1552 bool include_uses,
1553 bool include_eq_uses)
1554 {
1555 if (df->analyze_subset)
1556 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1557 include_uses, include_eq_uses);
1558 else
1559 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1560 include_uses, include_eq_uses);
1561 }
1562
1563
1564 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1565 static unsigned int
1566 df_add_refs_to_table (unsigned int offset,
1567 struct df_ref_info *ref_info,
1568 df_ref ref)
1569 {
1570 for (; ref; ref = DF_REF_NEXT_LOC (ref))
1571 if (!(df->changeable_flags & DF_NO_HARD_REGS)
1572 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1573 {
1574 ref_info->refs[offset] = ref;
1575 DF_REF_ID (ref) = offset++;
1576 }
1577 return offset;
1578 }
1579
1580
1581 /* Count the number of refs in all of the insns of BB. Include the
1582 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1583 eq_uses if INCLUDE_EQ_USES. */
1584
1585 static unsigned int
1586 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1587 struct df_ref_info *ref_info,
1588 bool include_defs, bool include_uses,
1589 bool include_eq_uses)
1590 {
1591 rtx_insn *insn;
1592
1593 if (include_defs)
1594 offset = df_add_refs_to_table (offset, ref_info,
1595 df_get_artificial_defs (bb->index));
1596 if (include_uses)
1597 offset = df_add_refs_to_table (offset, ref_info,
1598 df_get_artificial_uses (bb->index));
1599
1600 FOR_BB_INSNS (bb, insn)
1601 if (INSN_P (insn))
1602 {
1603 unsigned int uid = INSN_UID (insn);
1604 if (include_defs)
1605 offset = df_add_refs_to_table (offset, ref_info,
1606 DF_INSN_UID_DEFS (uid));
1607 if (include_uses)
1608 offset = df_add_refs_to_table (offset, ref_info,
1609 DF_INSN_UID_USES (uid));
1610 if (include_eq_uses)
1611 offset = df_add_refs_to_table (offset, ref_info,
1612 DF_INSN_UID_EQ_USES (uid));
1613 }
1614 return offset;
1615 }
1616
1617
1618 /* Organize the refs by insn into the table in REF_INFO. If
1619 blocks_to_analyze is defined, use that set, otherwise the entire
1620 program. Include the defs if INCLUDE_DEFS. Include the uses if
1621 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1622
1623 static void
1624 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1625 bool include_defs, bool include_uses,
1626 bool include_eq_uses)
1627 {
1628 basic_block bb;
1629 unsigned int offset = 0;
1630
1631 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1632 df_check_and_grow_ref_info (ref_info, 1);
1633 if (df->blocks_to_analyze)
1634 {
1635 bitmap_iterator bi;
1636 unsigned int index;
1637
1638 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1639 {
1640 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun,
1641 index),
1642 offset, ref_info,
1643 include_defs, include_uses,
1644 include_eq_uses);
1645 }
1646
1647 ref_info->table_size = offset;
1648 }
1649 else
1650 {
1651 FOR_ALL_BB_FN (bb, cfun)
1652 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1653 include_defs, include_uses,
1654 include_eq_uses);
1655 ref_info->table_size = offset;
1656 }
1657 }
1658
1659
1660 /* If the use refs in DF are not organized, reorganize them. */
1661
1662 void
1663 df_maybe_reorganize_use_refs (enum df_ref_order order)
1664 {
1665 if (order == df->use_info.ref_order)
1666 return;
1667
1668 switch (order)
1669 {
1670 case DF_REF_ORDER_BY_REG:
1671 df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1672 break;
1673
1674 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1675 df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1676 break;
1677
1678 case DF_REF_ORDER_BY_INSN:
1679 df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1680 break;
1681
1682 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1683 df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1684 break;
1685
1686 case DF_REF_ORDER_NO_TABLE:
1687 free (df->use_info.refs);
1688 df->use_info.refs = NULL;
1689 df->use_info.refs_size = 0;
1690 break;
1691
1692 case DF_REF_ORDER_UNORDERED:
1693 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1694 gcc_unreachable ();
1695 break;
1696 }
1697
1698 df->use_info.ref_order = order;
1699 }
1700
1701
1702 /* If the def refs in DF are not organized, reorganize them. */
1703
1704 void
1705 df_maybe_reorganize_def_refs (enum df_ref_order order)
1706 {
1707 if (order == df->def_info.ref_order)
1708 return;
1709
1710 switch (order)
1711 {
1712 case DF_REF_ORDER_BY_REG:
1713 df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1714 break;
1715
1716 case DF_REF_ORDER_BY_INSN:
1717 df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1718 break;
1719
1720 case DF_REF_ORDER_NO_TABLE:
1721 free (df->def_info.refs);
1722 df->def_info.refs = NULL;
1723 df->def_info.refs_size = 0;
1724 break;
1725
1726 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1727 case DF_REF_ORDER_BY_REG_WITH_NOTES:
1728 case DF_REF_ORDER_UNORDERED:
1729 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1730 gcc_unreachable ();
1731 break;
1732 }
1733
1734 df->def_info.ref_order = order;
1735 }
1736
1737
1738 /* Change all of the basic block references in INSN to use the insn's
1739 current basic block. This function is called from routines that move
1740 instructions from one block to another. */
1741
1742 void
1743 df_insn_change_bb (rtx_insn *insn, basic_block new_bb)
1744 {
1745 basic_block old_bb = BLOCK_FOR_INSN (insn);
1746 struct df_insn_info *insn_info;
1747 unsigned int uid = INSN_UID (insn);
1748
1749 if (old_bb == new_bb)
1750 return;
1751
1752 set_block_for_insn (insn, new_bb);
1753
1754 if (!df)
1755 return;
1756
1757 if (dump_file)
1758 fprintf (dump_file, "changing bb of uid %d\n", uid);
1759
1760 insn_info = DF_INSN_UID_SAFE_GET (uid);
1761 if (insn_info == NULL)
1762 {
1763 if (dump_file)
1764 fprintf (dump_file, " unscanned insn\n");
1765 df_insn_rescan (insn);
1766 return;
1767 }
1768
1769 if (!INSN_P (insn))
1770 return;
1771
1772 df_set_bb_dirty (new_bb);
1773 if (old_bb)
1774 {
1775 if (dump_file)
1776 fprintf (dump_file, " from %d to %d\n",
1777 old_bb->index, new_bb->index);
1778 df_set_bb_dirty (old_bb);
1779 }
1780 else
1781 if (dump_file)
1782 fprintf (dump_file, " to %d\n", new_bb->index);
1783 }
1784
1785
1786 /* Helper function for df_ref_change_reg_with_loc. */
1787
1788 static void
1789 df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1790 struct df_reg_info *new_df,
1791 unsigned int new_regno, rtx loc)
1792 {
1793 df_ref the_ref = old_df->reg_chain;
1794
1795 while (the_ref)
1796 {
1797 if ((!DF_REF_IS_ARTIFICIAL (the_ref))
1798 && DF_REF_LOC (the_ref)
1799 && (*DF_REF_LOC (the_ref) == loc))
1800 {
1801 df_ref next_ref = DF_REF_NEXT_REG (the_ref);
1802 df_ref prev_ref = DF_REF_PREV_REG (the_ref);
1803 df_ref *ref_ptr;
1804 struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
1805
1806 DF_REF_REGNO (the_ref) = new_regno;
1807 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1808
1809 /* Pull the_ref out of the old regno chain. */
1810 if (prev_ref)
1811 DF_REF_NEXT_REG (prev_ref) = next_ref;
1812 else
1813 old_df->reg_chain = next_ref;
1814 if (next_ref)
1815 DF_REF_PREV_REG (next_ref) = prev_ref;
1816 old_df->n_refs--;
1817
1818 /* Put the ref into the new regno chain. */
1819 DF_REF_PREV_REG (the_ref) = NULL;
1820 DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
1821 if (new_df->reg_chain)
1822 DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
1823 new_df->reg_chain = the_ref;
1824 new_df->n_refs++;
1825 if (DF_REF_BB (the_ref))
1826 df_set_bb_dirty (DF_REF_BB (the_ref));
1827
1828 /* Need to sort the record again that the ref was in because
1829 the regno is a sorting key. First, find the right
1830 record. */
1831 if (DF_REF_REG_DEF_P (the_ref))
1832 ref_ptr = &insn_info->defs;
1833 else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1834 ref_ptr = &insn_info->eq_uses;
1835 else
1836 ref_ptr = &insn_info->uses;
1837 if (dump_file)
1838 fprintf (dump_file, "changing reg in insn %d\n",
1839 DF_REF_INSN_UID (the_ref));
1840
1841 /* Stop if we find the current reference or where the reference
1842 needs to be. */
1843 while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0)
1844 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1845 if (*ref_ptr != the_ref)
1846 {
1847 /* The reference needs to be promoted up the list. */
1848 df_ref next = DF_REF_NEXT_LOC (the_ref);
1849 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1850 *ref_ptr = the_ref;
1851 do
1852 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1853 while (*ref_ptr != the_ref);
1854 *ref_ptr = next;
1855 }
1856 else if (DF_REF_NEXT_LOC (the_ref)
1857 && df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0)
1858 {
1859 /* The reference needs to be demoted down the list. */
1860 *ref_ptr = DF_REF_NEXT_LOC (the_ref);
1861 do
1862 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1863 while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0);
1864 DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1865 *ref_ptr = the_ref;
1866 }
1867
1868 the_ref = next_ref;
1869 }
1870 else
1871 the_ref = DF_REF_NEXT_REG (the_ref);
1872 }
1873 }
1874
1875
1876 /* Change the regno of register LOC to NEW_REGNO and update the df
1877 information accordingly. Refs that do not match LOC are not changed
1878 which means that artificial refs are not changed since they have no loc.
1879 This call is to support the SET_REGNO macro. */
1880
1881 void
1882 df_ref_change_reg_with_loc (rtx loc, unsigned int new_regno)
1883 {
1884 unsigned int old_regno = REGNO (loc);
1885 if (old_regno == new_regno)
1886 return;
1887
1888 if (df)
1889 {
1890 df_grow_reg_info ();
1891
1892 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1893 DF_REG_DEF_GET (new_regno),
1894 new_regno, loc);
1895 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1896 DF_REG_USE_GET (new_regno),
1897 new_regno, loc);
1898 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1899 DF_REG_EQ_USE_GET (new_regno),
1900 new_regno, loc);
1901 }
1902 set_mode_and_regno (loc, GET_MODE (loc), new_regno);
1903 }
1904
1905
1906 /* Delete the mw_hardregs that point into the eq_notes. */
1907
1908 static void
1909 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1910 {
1911 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs;
1912 struct df_scan_problem_data *problem_data
1913 = (struct df_scan_problem_data *) df_scan->problem_data;
1914
1915 while (*mw_ptr)
1916 {
1917 df_mw_hardreg *mw = *mw_ptr;
1918 if (mw->flags & DF_REF_IN_NOTE)
1919 {
1920 *mw_ptr = DF_MWS_NEXT (mw);
1921 problem_data->mw_reg_pool->remove (mw);
1922 }
1923 else
1924 mw_ptr = &DF_MWS_NEXT (mw);
1925 }
1926 }
1927
1928
1929 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1930
1931 void
1932 df_notes_rescan (rtx_insn *insn)
1933 {
1934 struct df_insn_info *insn_info;
1935 unsigned int uid = INSN_UID (insn);
1936
1937 if (!df)
1938 return;
1939
1940 /* The client has disabled rescanning and plans to do it itself. */
1941 if (df->changeable_flags & DF_NO_INSN_RESCAN)
1942 return;
1943
1944 /* Do nothing if the insn hasn't been emitted yet. */
1945 if (!BLOCK_FOR_INSN (insn))
1946 return;
1947
1948 df_grow_bb_info (df_scan);
1949 df_grow_reg_info ();
1950
1951 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1952
1953 /* The client has deferred rescanning. */
1954 if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1955 {
1956 if (!insn_info)
1957 {
1958 insn_info = df_insn_create_insn_record (insn);
1959 insn_info->defs = 0;
1960 insn_info->uses = 0;
1961 insn_info->eq_uses = 0;
1962 insn_info->mw_hardregs = 0;
1963 }
1964
1965 bitmap_clear_bit (&df->insns_to_delete, uid);
1966 /* If the insn is set to be rescanned, it does not need to also
1967 be notes rescanned. */
1968 if (!bitmap_bit_p (&df->insns_to_rescan, uid))
1969 bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn));
1970 return;
1971 }
1972
1973 bitmap_clear_bit (&df->insns_to_delete, uid);
1974 bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1975
1976 if (insn_info)
1977 {
1978 basic_block bb = BLOCK_FOR_INSN (insn);
1979 rtx note;
1980 struct df_collection_rec collection_rec;
1981 unsigned int i;
1982
1983 df_mw_hardreg_chain_delete_eq_uses (insn_info);
1984 df_ref_chain_delete (insn_info->eq_uses);
1985 insn_info->eq_uses = NULL;
1986
1987 /* Process REG_EQUIV/REG_EQUAL notes */
1988 for (note = REG_NOTES (insn); note;
1989 note = XEXP (note, 1))
1990 {
1991 switch (REG_NOTE_KIND (note))
1992 {
1993 case REG_EQUIV:
1994 case REG_EQUAL:
1995 df_uses_record (&collection_rec,
1996 &XEXP (note, 0), DF_REF_REG_USE,
1997 bb, insn_info, DF_REF_IN_NOTE);
1998 default:
1999 break;
2000 }
2001 }
2002
2003 /* Find some place to put any new mw_hardregs. */
2004 df_canonize_collection_rec (&collection_rec);
2005 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw;
2006 FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw)
2007 {
2008 while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0)
2009 mw_ptr = &DF_MWS_NEXT (*mw_ptr);
2010 DF_MWS_NEXT (mw) = *mw_ptr;
2011 *mw_ptr = mw;
2012 mw_ptr = &DF_MWS_NEXT (mw);
2013 }
2014 df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses);
2015 }
2016 else
2017 df_insn_rescan (insn);
2018
2019 }
2020
2021 \f
2022 /*----------------------------------------------------------------------------
2023 Hard core instruction scanning code. No external interfaces here,
2024 just a lot of routines that look inside insns.
2025 ----------------------------------------------------------------------------*/
2026
2027
2028 /* Return true if the contents of two df_ref's are identical.
2029 It ignores DF_REF_MARKER. */
2030
2031 static bool
2032 df_ref_equal_p (df_ref ref1, df_ref ref2)
2033 {
2034 if (!ref2)
2035 return false;
2036
2037 if (ref1 == ref2)
2038 return true;
2039
2040 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2041 || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2042 || DF_REF_REG (ref1) != DF_REF_REG (ref2)
2043 || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2044 || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2045 != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2046 || DF_REF_BB (ref1) != DF_REF_BB (ref2)
2047 || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2048 return false;
2049
2050 switch (DF_REF_CLASS (ref1))
2051 {
2052 case DF_REF_ARTIFICIAL:
2053 case DF_REF_BASE:
2054 return true;
2055
2056 case DF_REF_REGULAR:
2057 return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2058
2059 default:
2060 gcc_unreachable ();
2061 }
2062 return false;
2063 }
2064
2065
2066 /* Compare REF1 and REF2 for sorting. This is only called from places
2067 where all of the refs are of the same type, in the same insn, and
2068 have the same bb. So these fields are not checked. */
2069
2070 static int
2071 df_ref_compare (df_ref ref1, df_ref ref2)
2072 {
2073 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2074 return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2075
2076 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2077 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2078
2079 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2080 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2081
2082 if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2083 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2084
2085 /* Cannot look at the LOC field on artificial refs. */
2086 if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2087 && DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2088 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2089
2090 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2091 {
2092 /* If two refs are identical except that one of them has is from
2093 a mw and one is not, we need to have the one with the mw
2094 first. */
2095 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2096 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2097 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2098 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2099 return -1;
2100 else
2101 return 1;
2102 }
2103
2104 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2105 }
2106
2107 /* Like df_ref_compare, but compare two df_ref* pointers R1 and R2. */
2108
2109 static int
2110 df_ref_ptr_compare (const void *r1, const void *r2)
2111 {
2112 return df_ref_compare (*(const df_ref *) r1, *(const df_ref *) r2);
2113 }
2114
2115 /* Sort and compress a set of refs. */
2116
2117 static void
2118 df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
2119 {
2120 unsigned int count;
2121 unsigned int i;
2122 unsigned int dist = 0;
2123
2124 count = ref_vec->length ();
2125
2126 /* If there are 1 or 0 elements, there is nothing to do. */
2127 if (count < 2)
2128 return;
2129 else if (count == 2)
2130 {
2131 df_ref r0 = (*ref_vec)[0];
2132 df_ref r1 = (*ref_vec)[1];
2133 if (df_ref_compare (r0, r1) > 0)
2134 std::swap ((*ref_vec)[0], (*ref_vec)[1]);
2135 }
2136 else
2137 {
2138 for (i = 0; i < count - 1; i++)
2139 {
2140 df_ref r0 = (*ref_vec)[i];
2141 df_ref r1 = (*ref_vec)[i + 1];
2142 if (df_ref_compare (r0, r1) >= 0)
2143 break;
2144 }
2145 /* If the array is already strictly ordered,
2146 which is the most common case for large COUNT case
2147 (which happens for CALL INSNs),
2148 no need to sort and filter out duplicate.
2149 Simply return the count.
2150 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2151 of DF_REF_COMPARE. */
2152 if (i == count - 1)
2153 return;
2154 ref_vec->qsort (df_ref_ptr_compare);
2155 }
2156
2157 for (i=0; i<count-dist; i++)
2158 {
2159 /* Find the next ref that is not equal to the current ref. */
2160 while (i + dist + 1 < count
2161 && df_ref_equal_p ((*ref_vec)[i],
2162 (*ref_vec)[i + dist + 1]))
2163 {
2164 df_free_ref ((*ref_vec)[i + dist + 1]);
2165 dist++;
2166 }
2167 /* Copy it down to the next position. */
2168 if (dist && i + dist + 1 < count)
2169 (*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1];
2170 }
2171
2172 count -= dist;
2173 ref_vec->truncate (count);
2174 }
2175
2176
2177 /* Return true if the contents of two df_ref's are identical.
2178 It ignores DF_REF_MARKER. */
2179
2180 static bool
2181 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2182 {
2183 if (!mw2)
2184 return false;
2185 return (mw1 == mw2) ||
2186 (mw1->mw_reg == mw2->mw_reg
2187 && mw1->type == mw2->type
2188 && mw1->flags == mw2->flags
2189 && mw1->start_regno == mw2->start_regno
2190 && mw1->end_regno == mw2->end_regno);
2191 }
2192
2193
2194 /* Compare MW1 and MW2 for sorting. */
2195
2196 static int
2197 df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2)
2198 {
2199 if (mw1->type != mw2->type)
2200 return mw1->type - mw2->type;
2201
2202 if (mw1->flags != mw2->flags)
2203 return mw1->flags - mw2->flags;
2204
2205 if (mw1->start_regno != mw2->start_regno)
2206 return mw1->start_regno - mw2->start_regno;
2207
2208 if (mw1->end_regno != mw2->end_regno)
2209 return mw1->end_regno - mw2->end_regno;
2210
2211 if (mw1->mw_reg != mw2->mw_reg)
2212 return mw1->mw_order - mw2->mw_order;
2213
2214 return 0;
2215 }
2216
2217 /* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2. */
2218
2219 static int
2220 df_mw_ptr_compare (const void *m1, const void *m2)
2221 {
2222 return df_mw_compare (*(const df_mw_hardreg *const *) m1,
2223 *(const df_mw_hardreg *const *) m2);
2224 }
2225
2226 /* Sort and compress a set of refs. */
2227
2228 static void
2229 df_sort_and_compress_mws (vec<df_mw_hardreg *, va_heap> *mw_vec)
2230 {
2231 unsigned int count;
2232 struct df_scan_problem_data *problem_data
2233 = (struct df_scan_problem_data *) df_scan->problem_data;
2234 unsigned int i;
2235 unsigned int dist = 0;
2236
2237 count = mw_vec->length ();
2238 if (count < 2)
2239 return;
2240 else if (count == 2)
2241 {
2242 struct df_mw_hardreg *m0 = (*mw_vec)[0];
2243 struct df_mw_hardreg *m1 = (*mw_vec)[1];
2244 if (df_mw_compare (m0, m1) > 0)
2245 {
2246 struct df_mw_hardreg *tmp = (*mw_vec)[0];
2247 (*mw_vec)[0] = (*mw_vec)[1];
2248 (*mw_vec)[1] = tmp;
2249 }
2250 }
2251 else
2252 mw_vec->qsort (df_mw_ptr_compare);
2253
2254 for (i=0; i<count-dist; i++)
2255 {
2256 /* Find the next ref that is not equal to the current ref. */
2257 while (i + dist + 1 < count
2258 && df_mw_equal_p ((*mw_vec)[i], (*mw_vec)[i + dist + 1]))
2259 {
2260 problem_data->mw_reg_pool->remove ((*mw_vec)[i + dist + 1]);
2261 dist++;
2262 }
2263 /* Copy it down to the next position. */
2264 if (dist && i + dist + 1 < count)
2265 (*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1];
2266 }
2267
2268 count -= dist;
2269 mw_vec->truncate (count);
2270 }
2271
2272
2273 /* Sort and remove duplicates from the COLLECTION_REC. */
2274
2275 static void
2276 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2277 {
2278 df_sort_and_compress_refs (&collection_rec->def_vec);
2279 df_sort_and_compress_refs (&collection_rec->use_vec);
2280 df_sort_and_compress_refs (&collection_rec->eq_use_vec);
2281 df_sort_and_compress_mws (&collection_rec->mw_vec);
2282 }
2283
2284
2285 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2286
2287 static void
2288 df_install_ref (df_ref this_ref,
2289 struct df_reg_info *reg_info,
2290 struct df_ref_info *ref_info,
2291 bool add_to_table)
2292 {
2293 unsigned int regno = DF_REF_REGNO (this_ref);
2294 /* Add the ref to the reg_{def,use,eq_use} chain. */
2295 df_ref head = reg_info->reg_chain;
2296
2297 reg_info->reg_chain = this_ref;
2298 reg_info->n_refs++;
2299
2300 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2301 {
2302 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2303 df->hard_regs_live_count[regno]++;
2304 }
2305
2306 gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL
2307 && DF_REF_PREV_REG (this_ref) == NULL);
2308
2309 DF_REF_NEXT_REG (this_ref) = head;
2310
2311 /* We cannot actually link to the head of the chain. */
2312 DF_REF_PREV_REG (this_ref) = NULL;
2313
2314 if (head)
2315 DF_REF_PREV_REG (head) = this_ref;
2316
2317 if (add_to_table)
2318 {
2319 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2320 df_check_and_grow_ref_info (ref_info, 1);
2321 DF_REF_ID (this_ref) = ref_info->table_size;
2322 /* Add the ref to the big array of defs. */
2323 ref_info->refs[ref_info->table_size] = this_ref;
2324 ref_info->table_size++;
2325 }
2326 else
2327 DF_REF_ID (this_ref) = -1;
2328
2329 ref_info->total_size++;
2330 }
2331
2332
2333 /* This function takes one of the groups of refs (defs, uses or
2334 eq_uses) and installs the entire group into the insn. It also adds
2335 each of these refs into the appropriate chains. */
2336
2337 static df_ref
2338 df_install_refs (basic_block bb,
2339 const vec<df_ref, va_heap> *old_vec,
2340 struct df_reg_info **reg_info,
2341 struct df_ref_info *ref_info,
2342 bool is_notes)
2343 {
2344 unsigned int count = old_vec->length ();
2345 if (count)
2346 {
2347 bool add_to_table;
2348 df_ref this_ref;
2349 unsigned int ix;
2350
2351 switch (ref_info->ref_order)
2352 {
2353 case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2354 case DF_REF_ORDER_BY_REG_WITH_NOTES:
2355 case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2356 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2357 add_to_table = true;
2358 break;
2359 case DF_REF_ORDER_UNORDERED:
2360 case DF_REF_ORDER_BY_REG:
2361 case DF_REF_ORDER_BY_INSN:
2362 ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2363 add_to_table = !is_notes;
2364 break;
2365 default:
2366 add_to_table = false;
2367 break;
2368 }
2369
2370 /* Do not add if ref is not in the right blocks. */
2371 if (add_to_table && df->analyze_subset)
2372 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2373
2374 FOR_EACH_VEC_ELT (*old_vec, ix, this_ref)
2375 {
2376 DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length ()
2377 ? (*old_vec)[ix + 1]
2378 : NULL);
2379 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2380 ref_info, add_to_table);
2381 }
2382 return (*old_vec)[0];
2383 }
2384 else
2385 return 0;
2386 }
2387
2388
2389 /* This function takes the mws installs the entire group into the
2390 insn. */
2391
2392 static struct df_mw_hardreg *
2393 df_install_mws (const vec<df_mw_hardreg *, va_heap> *old_vec)
2394 {
2395 unsigned int count = old_vec->length ();
2396 if (count)
2397 {
2398 for (unsigned int i = 0; i < count - 1; i++)
2399 DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1];
2400 DF_MWS_NEXT ((*old_vec)[count - 1]) = 0;
2401 return (*old_vec)[0];
2402 }
2403 else
2404 return 0;
2405 }
2406
2407
2408 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2409 chains and update other necessary information. */
2410
2411 static void
2412 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2413 basic_block bb, rtx_insn *insn, unsigned int flags)
2414 {
2415 if (insn)
2416 {
2417 struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2418 /* If there is a vector in the collection rec, add it to the
2419 insn. A null rec is a signal that the caller will handle the
2420 chain specially. */
2421 if (flags & copy_defs)
2422 {
2423 gcc_checking_assert (!insn_rec->defs);
2424 insn_rec->defs
2425 = df_install_refs (bb, &collection_rec->def_vec,
2426 df->def_regs,
2427 &df->def_info, false);
2428 }
2429 if (flags & copy_uses)
2430 {
2431 gcc_checking_assert (!insn_rec->uses);
2432 insn_rec->uses
2433 = df_install_refs (bb, &collection_rec->use_vec,
2434 df->use_regs,
2435 &df->use_info, false);
2436 }
2437 if (flags & copy_eq_uses)
2438 {
2439 gcc_checking_assert (!insn_rec->eq_uses);
2440 insn_rec->eq_uses
2441 = df_install_refs (bb, &collection_rec->eq_use_vec,
2442 df->eq_use_regs,
2443 &df->use_info, true);
2444 }
2445 if (flags & copy_mw)
2446 {
2447 gcc_checking_assert (!insn_rec->mw_hardregs);
2448 insn_rec->mw_hardregs
2449 = df_install_mws (&collection_rec->mw_vec);
2450 }
2451 }
2452 else
2453 {
2454 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2455
2456 gcc_checking_assert (!bb_info->artificial_defs);
2457 bb_info->artificial_defs
2458 = df_install_refs (bb, &collection_rec->def_vec,
2459 df->def_regs,
2460 &df->def_info, false);
2461 gcc_checking_assert (!bb_info->artificial_uses);
2462 bb_info->artificial_uses
2463 = df_install_refs (bb, &collection_rec->use_vec,
2464 df->use_regs,
2465 &df->use_info, false);
2466 }
2467 }
2468
2469
2470 /* Allocate a ref and initialize its fields. */
2471
2472 static df_ref
2473 df_ref_create_structure (enum df_ref_class cl,
2474 struct df_collection_rec *collection_rec,
2475 rtx reg, rtx *loc,
2476 basic_block bb, struct df_insn_info *info,
2477 enum df_ref_type ref_type,
2478 int ref_flags)
2479 {
2480 df_ref this_ref = NULL;
2481 unsigned int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2482 struct df_scan_problem_data *problem_data
2483 = (struct df_scan_problem_data *) df_scan->problem_data;
2484
2485 switch (cl)
2486 {
2487 case DF_REF_BASE:
2488 this_ref = (df_ref) (problem_data->ref_base_pool->allocate ());
2489 gcc_checking_assert (loc == NULL);
2490 break;
2491
2492 case DF_REF_ARTIFICIAL:
2493 this_ref = (df_ref) (problem_data->ref_artificial_pool->allocate ());
2494 this_ref->artificial_ref.bb = bb;
2495 gcc_checking_assert (loc == NULL);
2496 break;
2497
2498 case DF_REF_REGULAR:
2499 this_ref = (df_ref) (problem_data->ref_regular_pool->allocate ());
2500 this_ref->regular_ref.loc = loc;
2501 gcc_checking_assert (loc);
2502 break;
2503 }
2504
2505 DF_REF_CLASS (this_ref) = cl;
2506 DF_REF_ID (this_ref) = -1;
2507 DF_REF_REG (this_ref) = reg;
2508 DF_REF_REGNO (this_ref) = regno;
2509 DF_REF_TYPE (this_ref) = ref_type;
2510 DF_REF_INSN_INFO (this_ref) = info;
2511 DF_REF_CHAIN (this_ref) = NULL;
2512 DF_REF_FLAGS (this_ref) = ref_flags;
2513 DF_REF_NEXT_REG (this_ref) = NULL;
2514 DF_REF_PREV_REG (this_ref) = NULL;
2515 DF_REF_ORDER (this_ref) = df->ref_order++;
2516
2517 /* We need to clear this bit because fwprop, and in the future
2518 possibly other optimizations sometimes create new refs using ond
2519 refs as the model. */
2520 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2521
2522 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2523 if (regno < FIRST_PSEUDO_REGISTER
2524 && !DF_REF_IS_ARTIFICIAL (this_ref)
2525 && !DEBUG_INSN_P (DF_REF_INSN (this_ref)))
2526 {
2527 if (DF_REF_REG_DEF_P (this_ref))
2528 {
2529 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2530 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2531 }
2532 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2533 && (regno == FRAME_POINTER_REGNUM
2534 || regno == ARG_POINTER_REGNUM)))
2535 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2536 }
2537
2538 if (collection_rec)
2539 {
2540 if (DF_REF_REG_DEF_P (this_ref))
2541 collection_rec->def_vec.safe_push (this_ref);
2542 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2543 collection_rec->eq_use_vec.safe_push (this_ref);
2544 else
2545 collection_rec->use_vec.safe_push (this_ref);
2546 }
2547 else
2548 df_install_ref_incremental (this_ref);
2549
2550 return this_ref;
2551 }
2552
2553
2554 /* Create new references of type DF_REF_TYPE for each part of register REG
2555 at address LOC within INSN of BB. */
2556
2557
2558 static void
2559 df_ref_record (enum df_ref_class cl,
2560 struct df_collection_rec *collection_rec,
2561 rtx reg, rtx *loc,
2562 basic_block bb, struct df_insn_info *insn_info,
2563 enum df_ref_type ref_type,
2564 int ref_flags)
2565 {
2566 unsigned int regno;
2567
2568 gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2569
2570 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2571 if (regno < FIRST_PSEUDO_REGISTER)
2572 {
2573 struct df_mw_hardreg *hardreg = NULL;
2574 struct df_scan_problem_data *problem_data
2575 = (struct df_scan_problem_data *) df_scan->problem_data;
2576 unsigned int i;
2577 unsigned int endregno;
2578 df_ref ref;
2579
2580 if (GET_CODE (reg) == SUBREG)
2581 {
2582 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2583 SUBREG_BYTE (reg), GET_MODE (reg));
2584 endregno = regno + subreg_nregs (reg);
2585 }
2586 else
2587 endregno = END_REGNO (reg);
2588
2589 /* If this is a multiword hardreg, we create some extra
2590 datastructures that will enable us to easily build REG_DEAD
2591 and REG_UNUSED notes. */
2592 if (collection_rec
2593 && (endregno != regno + 1) && insn_info)
2594 {
2595 /* Sets to a subreg of a multiword register are partial.
2596 Sets to a non-subreg of a multiword register are not. */
2597 if (GET_CODE (reg) == SUBREG)
2598 ref_flags |= DF_REF_PARTIAL;
2599 ref_flags |= DF_REF_MW_HARDREG;
2600
2601 hardreg = problem_data->mw_reg_pool->allocate ();
2602 hardreg->type = ref_type;
2603 hardreg->flags = ref_flags;
2604 hardreg->mw_reg = reg;
2605 hardreg->start_regno = regno;
2606 hardreg->end_regno = endregno - 1;
2607 hardreg->mw_order = df->ref_order++;
2608 collection_rec->mw_vec.safe_push (hardreg);
2609 }
2610
2611 for (i = regno; i < endregno; i++)
2612 {
2613 ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc,
2614 bb, insn_info, ref_type, ref_flags);
2615
2616 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2617 }
2618 }
2619 else
2620 {
2621 df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info,
2622 ref_type, ref_flags);
2623 }
2624 }
2625
2626
2627 /* Process all the registers defined in the rtx pointed by LOC.
2628 Autoincrement/decrement definitions will be picked up by df_uses_record.
2629 Any change here has to be matched in df_find_hard_reg_defs_1. */
2630
2631 static void
2632 df_def_record_1 (struct df_collection_rec *collection_rec,
2633 rtx *loc, basic_block bb, struct df_insn_info *insn_info,
2634 int flags)
2635 {
2636 rtx dst = *loc;
2637
2638 /* It is legal to have a set destination be a parallel. */
2639 if (GET_CODE (dst) == PARALLEL)
2640 {
2641 int i;
2642 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2643 {
2644 rtx temp = XVECEXP (dst, 0, i);
2645 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2646 df_def_record_1 (collection_rec, &XEXP (temp, 0),
2647 bb, insn_info, flags);
2648 }
2649 return;
2650 }
2651
2652 if (GET_CODE (dst) == STRICT_LOW_PART)
2653 {
2654 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2655
2656 loc = &XEXP (dst, 0);
2657 dst = *loc;
2658 }
2659
2660 if (GET_CODE (dst) == ZERO_EXTRACT)
2661 {
2662 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2663
2664 loc = &XEXP (dst, 0);
2665 dst = *loc;
2666 }
2667
2668 /* At this point if we do not have a reg or a subreg, just return. */
2669 if (REG_P (dst))
2670 {
2671 df_ref_record (DF_REF_REGULAR, collection_rec,
2672 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2673
2674 /* We want to keep sp alive everywhere - by making all
2675 writes to sp also use of sp. */
2676 if (REGNO (dst) == STACK_POINTER_REGNUM)
2677 df_ref_record (DF_REF_BASE, collection_rec,
2678 dst, NULL, bb, insn_info, DF_REF_REG_USE, flags);
2679 }
2680 else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2681 {
2682 if (read_modify_subreg_p (dst))
2683 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2684
2685 flags |= DF_REF_SUBREG;
2686
2687 df_ref_record (DF_REF_REGULAR, collection_rec,
2688 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2689 }
2690 }
2691
2692
2693 /* Process all the registers defined in the pattern rtx, X. Any change
2694 here has to be matched in df_find_hard_reg_defs. */
2695
2696 static void
2697 df_defs_record (struct df_collection_rec *collection_rec,
2698 rtx x, basic_block bb, struct df_insn_info *insn_info,
2699 int flags)
2700 {
2701 RTX_CODE code = GET_CODE (x);
2702 int i;
2703
2704 switch (code)
2705 {
2706 case SET:
2707 df_def_record_1 (collection_rec, &SET_DEST (x), bb, insn_info, flags);
2708 break;
2709
2710 case CLOBBER:
2711 flags |= DF_REF_MUST_CLOBBER;
2712 df_def_record_1 (collection_rec, &XEXP (x, 0), bb, insn_info, flags);
2713 break;
2714
2715 case COND_EXEC:
2716 df_defs_record (collection_rec, COND_EXEC_CODE (x),
2717 bb, insn_info, DF_REF_CONDITIONAL);
2718 break;
2719
2720 case PARALLEL:
2721 for (i = 0; i < XVECLEN (x, 0); i++)
2722 df_defs_record (collection_rec, XVECEXP (x, 0, i),
2723 bb, insn_info, flags);
2724 break;
2725 default:
2726 /* No DEFs to record in other cases */
2727 break;
2728 }
2729 }
2730
2731 /* Set bits in *DEFS for hard registers found in the rtx DST, which is the
2732 destination of a set or clobber. This has to match the logic in
2733 df_defs_record_1. */
2734
2735 static void
2736 df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs)
2737 {
2738 /* It is legal to have a set destination be a parallel. */
2739 if (GET_CODE (dst) == PARALLEL)
2740 {
2741 int i;
2742 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2743 {
2744 rtx temp = XVECEXP (dst, 0, i);
2745 gcc_assert (GET_CODE (temp) == EXPR_LIST);
2746 df_find_hard_reg_defs_1 (XEXP (temp, 0), defs);
2747 }
2748 return;
2749 }
2750
2751 if (GET_CODE (dst) == STRICT_LOW_PART)
2752 dst = XEXP (dst, 0);
2753
2754 if (GET_CODE (dst) == ZERO_EXTRACT)
2755 dst = XEXP (dst, 0);
2756
2757 /* At this point if we do not have a reg or a subreg, just return. */
2758 if (REG_P (dst) && HARD_REGISTER_P (dst))
2759 SET_HARD_REG_BIT (*defs, REGNO (dst));
2760 else if (GET_CODE (dst) == SUBREG
2761 && REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst))
2762 SET_HARD_REG_BIT (*defs, REGNO (SUBREG_REG (dst)));
2763 }
2764
2765 /* Set bits in *DEFS for hard registers defined in the pattern X. This
2766 has to match the logic in df_defs_record. */
2767
2768 static void
2769 df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs)
2770 {
2771 RTX_CODE code = GET_CODE (x);
2772 int i;
2773
2774 switch (code)
2775 {
2776 case SET:
2777 df_find_hard_reg_defs_1 (SET_DEST (x), defs);
2778 break;
2779
2780 case CLOBBER:
2781 df_find_hard_reg_defs_1 (XEXP (x, 0), defs);
2782 break;
2783
2784 case COND_EXEC:
2785 df_find_hard_reg_defs (COND_EXEC_CODE (x), defs);
2786 break;
2787
2788 case PARALLEL:
2789 for (i = 0; i < XVECLEN (x, 0); i++)
2790 df_find_hard_reg_defs (XVECEXP (x, 0, i), defs);
2791 break;
2792 default:
2793 /* No DEFs to record in other cases */
2794 break;
2795 }
2796 }
2797
2798
2799 /* Process all the registers used in the rtx at address LOC. */
2800
2801 static void
2802 df_uses_record (struct df_collection_rec *collection_rec,
2803 rtx *loc, enum df_ref_type ref_type,
2804 basic_block bb, struct df_insn_info *insn_info,
2805 int flags)
2806 {
2807 RTX_CODE code;
2808 rtx x;
2809
2810 retry:
2811 x = *loc;
2812 if (!x)
2813 return;
2814 code = GET_CODE (x);
2815 switch (code)
2816 {
2817 case LABEL_REF:
2818 case SYMBOL_REF:
2819 case CONST:
2820 CASE_CONST_ANY:
2821 case PC:
2822 case CC0:
2823 case ADDR_VEC:
2824 case ADDR_DIFF_VEC:
2825 return;
2826
2827 case CLOBBER:
2828 /* If we are clobbering a MEM, mark any registers inside the address
2829 as being used. */
2830 if (MEM_P (XEXP (x, 0)))
2831 df_uses_record (collection_rec,
2832 &XEXP (XEXP (x, 0), 0),
2833 DF_REF_REG_MEM_STORE,
2834 bb, insn_info,
2835 flags);
2836
2837 /* If we're clobbering a REG then we have a def so ignore. */
2838 return;
2839
2840 case MEM:
2841 df_uses_record (collection_rec,
2842 &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2843 bb, insn_info, flags & DF_REF_IN_NOTE);
2844 return;
2845
2846 case SUBREG:
2847 /* While we're here, optimize this case. */
2848 flags |= DF_REF_PARTIAL;
2849 /* In case the SUBREG is not of a REG, do not optimize. */
2850 if (!REG_P (SUBREG_REG (x)))
2851 {
2852 loc = &SUBREG_REG (x);
2853 df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags);
2854 return;
2855 }
2856 /* Fall through */
2857
2858 case REG:
2859 df_ref_record (DF_REF_REGULAR, collection_rec,
2860 x, loc, bb, insn_info,
2861 ref_type, flags);
2862 return;
2863
2864 case SIGN_EXTRACT:
2865 case ZERO_EXTRACT:
2866 {
2867 df_uses_record (collection_rec,
2868 &XEXP (x, 1), ref_type, bb, insn_info, flags);
2869 df_uses_record (collection_rec,
2870 &XEXP (x, 2), ref_type, bb, insn_info, flags);
2871
2872 /* If the parameters to the zero or sign extract are
2873 constants, strip them off and recurse, otherwise there is
2874 no information that we can gain from this operation. */
2875 if (code == ZERO_EXTRACT)
2876 flags |= DF_REF_ZERO_EXTRACT;
2877 else
2878 flags |= DF_REF_SIGN_EXTRACT;
2879
2880 df_uses_record (collection_rec,
2881 &XEXP (x, 0), ref_type, bb, insn_info, flags);
2882 return;
2883 }
2884 break;
2885
2886 case SET:
2887 {
2888 rtx dst = SET_DEST (x);
2889 gcc_assert (!(flags & DF_REF_IN_NOTE));
2890 df_uses_record (collection_rec,
2891 &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags);
2892
2893 switch (GET_CODE (dst))
2894 {
2895 case SUBREG:
2896 if (read_modify_subreg_p (dst))
2897 {
2898 df_uses_record (collection_rec, &SUBREG_REG (dst),
2899 DF_REF_REG_USE, bb, insn_info,
2900 flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
2901 break;
2902 }
2903 /* Fall through. */
2904 case REG:
2905 case PARALLEL:
2906 case SCRATCH:
2907 case PC:
2908 case CC0:
2909 break;
2910 case MEM:
2911 df_uses_record (collection_rec, &XEXP (dst, 0),
2912 DF_REF_REG_MEM_STORE, bb, insn_info, flags);
2913 break;
2914 case STRICT_LOW_PART:
2915 {
2916 rtx *temp = &XEXP (dst, 0);
2917 /* A strict_low_part uses the whole REG and not just the
2918 SUBREG. */
2919 dst = XEXP (dst, 0);
2920 df_uses_record (collection_rec,
2921 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2922 DF_REF_REG_USE, bb, insn_info,
2923 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART);
2924 }
2925 break;
2926 case ZERO_EXTRACT:
2927 {
2928 df_uses_record (collection_rec, &XEXP (dst, 1),
2929 DF_REF_REG_USE, bb, insn_info, flags);
2930 df_uses_record (collection_rec, &XEXP (dst, 2),
2931 DF_REF_REG_USE, bb, insn_info, flags);
2932 if (GET_CODE (XEXP (dst,0)) == MEM)
2933 df_uses_record (collection_rec, &XEXP (dst, 0),
2934 DF_REF_REG_USE, bb, insn_info,
2935 flags);
2936 else
2937 df_uses_record (collection_rec, &XEXP (dst, 0),
2938 DF_REF_REG_USE, bb, insn_info,
2939 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT);
2940 }
2941 break;
2942
2943 default:
2944 gcc_unreachable ();
2945 }
2946 return;
2947 }
2948
2949 case RETURN:
2950 case SIMPLE_RETURN:
2951 break;
2952
2953 case ASM_OPERANDS:
2954 case UNSPEC_VOLATILE:
2955 case TRAP_IF:
2956 case ASM_INPUT:
2957 {
2958 /* Traditional and volatile asm instructions must be
2959 considered to use and clobber all hard registers, all
2960 pseudo-registers and all of memory. So must TRAP_IF and
2961 UNSPEC_VOLATILE operations.
2962
2963 Consider for instance a volatile asm that changes the fpu
2964 rounding mode. An insn should not be moved across this
2965 even if it only uses pseudo-regs because it might give an
2966 incorrectly rounded result.
2967
2968 However, flow.c's liveness computation did *not* do this,
2969 giving the reasoning as " ?!? Unfortunately, marking all
2970 hard registers as live causes massive problems for the
2971 register allocator and marking all pseudos as live creates
2972 mountains of uninitialized variable warnings."
2973
2974 In order to maintain the status quo with regard to liveness
2975 and uses, we do what flow.c did and just mark any regs we
2976 can find in ASM_OPERANDS as used. In global asm insns are
2977 scanned and regs_asm_clobbered is filled out.
2978
2979 For all ASM_OPERANDS, we must traverse the vector of input
2980 operands. We can not just fall through here since then we
2981 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
2982 which do not indicate traditional asms unlike their normal
2983 usage. */
2984 if (code == ASM_OPERANDS)
2985 {
2986 int j;
2987
2988 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2989 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
2990 DF_REF_REG_USE, bb, insn_info, flags);
2991 return;
2992 }
2993 break;
2994 }
2995
2996 case VAR_LOCATION:
2997 df_uses_record (collection_rec,
2998 &PAT_VAR_LOCATION_LOC (x),
2999 DF_REF_REG_USE, bb, insn_info, flags);
3000 return;
3001
3002 case PRE_DEC:
3003 case POST_DEC:
3004 case PRE_INC:
3005 case POST_INC:
3006 case PRE_MODIFY:
3007 case POST_MODIFY:
3008 gcc_assert (!DEBUG_INSN_P (insn_info->insn));
3009 /* Catch the def of the register being modified. */
3010 df_ref_record (DF_REF_REGULAR, collection_rec, XEXP (x, 0), &XEXP (x, 0),
3011 bb, insn_info,
3012 DF_REF_REG_DEF,
3013 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
3014
3015 /* ... Fall through to handle uses ... */
3016
3017 default:
3018 break;
3019 }
3020
3021 /* Recursively scan the operands of this expression. */
3022 {
3023 const char *fmt = GET_RTX_FORMAT (code);
3024 int i;
3025
3026 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3027 {
3028 if (fmt[i] == 'e')
3029 {
3030 /* Tail recursive case: save a function call level. */
3031 if (i == 0)
3032 {
3033 loc = &XEXP (x, 0);
3034 goto retry;
3035 }
3036 df_uses_record (collection_rec, &XEXP (x, i), ref_type,
3037 bb, insn_info, flags);
3038 }
3039 else if (fmt[i] == 'E')
3040 {
3041 int j;
3042 for (j = 0; j < XVECLEN (x, i); j++)
3043 df_uses_record (collection_rec,
3044 &XVECEXP (x, i, j), ref_type,
3045 bb, insn_info, flags);
3046 }
3047 }
3048 }
3049
3050 return;
3051 }
3052
3053
3054 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3055
3056 static void
3057 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3058 {
3059 unsigned int ix;
3060 df_ref ref;
3061
3062 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
3063 {
3064 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3065 {
3066 df_ref use;
3067
3068 use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3069 DF_REF_LOC (ref), DF_REF_BB (ref),
3070 DF_REF_INSN_INFO (ref), DF_REF_REG_USE,
3071 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3072 DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3073 }
3074 }
3075 }
3076
3077
3078 /* Get call's extra defs and uses (track caller-saved registers). */
3079
3080 static void
3081 df_get_call_refs (struct df_collection_rec *collection_rec,
3082 basic_block bb,
3083 struct df_insn_info *insn_info,
3084 int flags)
3085 {
3086 rtx note;
3087 bool is_sibling_call;
3088 unsigned int i;
3089 HARD_REG_SET defs_generated;
3090 HARD_REG_SET fn_reg_set_usage;
3091
3092 CLEAR_HARD_REG_SET (defs_generated);
3093 df_find_hard_reg_defs (PATTERN (insn_info->insn), &defs_generated);
3094 is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3095 get_call_reg_set_usage (insn_info->insn, &fn_reg_set_usage,
3096 regs_invalidated_by_call);
3097
3098 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3099 {
3100 if (i == STACK_POINTER_REGNUM)
3101 /* The stack ptr is used (honorarily) by a CALL insn. */
3102 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3103 NULL, bb, insn_info, DF_REF_REG_USE,
3104 DF_REF_CALL_STACK_USAGE | flags);
3105 else if (global_regs[i])
3106 {
3107 /* Calls to const functions cannot access any global registers and
3108 calls to pure functions cannot set them. All other calls may
3109 reference any of the global registers, so they are recorded as
3110 used. */
3111 if (!RTL_CONST_CALL_P (insn_info->insn))
3112 {
3113 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3114 NULL, bb, insn_info, DF_REF_REG_USE, flags);
3115 if (!RTL_PURE_CALL_P (insn_info->insn))
3116 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3117 NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3118 }
3119 }
3120 else if (TEST_HARD_REG_BIT (fn_reg_set_usage, i)
3121 /* no clobbers for regs that are the result of the call */
3122 && !TEST_HARD_REG_BIT (defs_generated, i)
3123 && (!is_sibling_call
3124 || !bitmap_bit_p (df->exit_block_uses, i)
3125 || refers_to_regno_p (i, crtl->return_rtx)))
3126 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3127 NULL, bb, insn_info, DF_REF_REG_DEF,
3128 DF_REF_MAY_CLOBBER | flags);
3129 }
3130
3131 /* Record the registers used to pass arguments, and explicitly
3132 noted as clobbered. */
3133 for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3134 note = XEXP (note, 1))
3135 {
3136 if (GET_CODE (XEXP (note, 0)) == USE)
3137 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3138 DF_REF_REG_USE, bb, insn_info, flags);
3139 else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3140 {
3141 if (REG_P (XEXP (XEXP (note, 0), 0)))
3142 {
3143 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3144 if (!TEST_HARD_REG_BIT (defs_generated, regno))
3145 df_defs_record (collection_rec, XEXP (note, 0), bb,
3146 insn_info, flags);
3147 }
3148 else
3149 df_uses_record (collection_rec, &XEXP (note, 0),
3150 DF_REF_REG_USE, bb, insn_info, flags);
3151 }
3152 }
3153
3154 return;
3155 }
3156
3157 /* Collect all refs in the INSN. This function is free of any
3158 side-effect - it will create and return a lists of df_ref's in the
3159 COLLECTION_REC without putting those refs into existing ref chains
3160 and reg chains. */
3161
3162 static void
3163 df_insn_refs_collect (struct df_collection_rec *collection_rec,
3164 basic_block bb, struct df_insn_info *insn_info)
3165 {
3166 rtx note;
3167 bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3168
3169 /* Clear out the collection record. */
3170 collection_rec->def_vec.truncate (0);
3171 collection_rec->use_vec.truncate (0);
3172 collection_rec->eq_use_vec.truncate (0);
3173 collection_rec->mw_vec.truncate (0);
3174
3175 /* Process REG_EQUIV/REG_EQUAL notes. */
3176 for (note = REG_NOTES (insn_info->insn); note;
3177 note = XEXP (note, 1))
3178 {
3179 switch (REG_NOTE_KIND (note))
3180 {
3181 case REG_EQUIV:
3182 case REG_EQUAL:
3183 df_uses_record (collection_rec,
3184 &XEXP (note, 0), DF_REF_REG_USE,
3185 bb, insn_info, DF_REF_IN_NOTE);
3186 break;
3187 case REG_NON_LOCAL_GOTO:
3188 /* The frame ptr is used by a non-local goto. */
3189 df_ref_record (DF_REF_BASE, collection_rec,
3190 regno_reg_rtx[FRAME_POINTER_REGNUM],
3191 NULL, bb, insn_info,
3192 DF_REF_REG_USE, 0);
3193 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3194 df_ref_record (DF_REF_BASE, collection_rec,
3195 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3196 NULL, bb, insn_info,
3197 DF_REF_REG_USE, 0);
3198 break;
3199 default:
3200 break;
3201 }
3202 }
3203
3204 int flags = (is_cond_exec) ? DF_REF_CONDITIONAL : 0;
3205 /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3206 uses from CALL_INSN_FUNCTION_USAGE. */
3207 if (CALL_P (insn_info->insn))
3208 df_get_call_refs (collection_rec, bb, insn_info, flags);
3209
3210 if (asm_noperands (PATTERN (insn_info->insn)) >= 0)
3211 for (unsigned i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3212 if (global_regs[i])
3213 {
3214 /* As with calls, asm statements reference all global regs. */
3215 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3216 NULL, bb, insn_info, DF_REF_REG_USE, flags);
3217 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3218 NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3219 }
3220
3221 /* Record other defs. These should be mostly for DF_REF_REGULAR, so
3222 that a qsort on the defs is unnecessary in most cases. */
3223 df_defs_record (collection_rec,
3224 PATTERN (insn_info->insn), bb, insn_info, 0);
3225
3226 /* Record the register uses. */
3227 df_uses_record (collection_rec,
3228 &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0);
3229
3230 /* DF_REF_CONDITIONAL needs corresponding USES. */
3231 if (is_cond_exec)
3232 df_get_conditional_uses (collection_rec);
3233
3234 df_canonize_collection_rec (collection_rec);
3235 }
3236
3237 /* Recompute the luids for the insns in BB. */
3238
3239 void
3240 df_recompute_luids (basic_block bb)
3241 {
3242 rtx_insn *insn;
3243 int luid = 0;
3244
3245 df_grow_insn_info ();
3246
3247 /* Scan the block an insn at a time from beginning to end. */
3248 FOR_BB_INSNS (bb, insn)
3249 {
3250 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3251 /* Inserting labels does not always trigger the incremental
3252 rescanning. */
3253 if (!insn_info)
3254 {
3255 gcc_assert (!INSN_P (insn));
3256 insn_info = df_insn_create_insn_record (insn);
3257 }
3258
3259 DF_INSN_INFO_LUID (insn_info) = luid;
3260 if (INSN_P (insn))
3261 luid++;
3262 }
3263 }
3264
3265
3266 /* Collect all artificial refs at the block level for BB and add them
3267 to COLLECTION_REC. */
3268
3269 static void
3270 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3271 {
3272 collection_rec->def_vec.truncate (0);
3273 collection_rec->use_vec.truncate (0);
3274 collection_rec->eq_use_vec.truncate (0);
3275 collection_rec->mw_vec.truncate (0);
3276
3277 if (bb->index == ENTRY_BLOCK)
3278 {
3279 df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3280 return;
3281 }
3282 else if (bb->index == EXIT_BLOCK)
3283 {
3284 df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3285 return;
3286 }
3287
3288 if (bb_has_eh_pred (bb))
3289 {
3290 unsigned int i;
3291 /* Mark the registers that will contain data for the handler. */
3292 for (i = 0; ; ++i)
3293 {
3294 unsigned regno = EH_RETURN_DATA_REGNO (i);
3295 if (regno == INVALID_REGNUM)
3296 break;
3297 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3298 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3299 }
3300 }
3301
3302 /* Add the hard_frame_pointer if this block is the target of a
3303 non-local goto. */
3304 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3305 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3306 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3307
3308 /* Add the artificial uses. */
3309 if (bb->index >= NUM_FIXED_BLOCKS)
3310 {
3311 bitmap_iterator bi;
3312 unsigned int regno;
3313 bitmap au = bb_has_eh_pred (bb)
3314 ? &df->eh_block_artificial_uses
3315 : &df->regular_block_artificial_uses;
3316
3317 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3318 {
3319 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3320 bb, NULL, DF_REF_REG_USE, 0);
3321 }
3322 }
3323
3324 df_canonize_collection_rec (collection_rec);
3325 }
3326
3327
3328 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3329
3330 void
3331 df_bb_refs_record (int bb_index, bool scan_insns)
3332 {
3333 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3334 rtx_insn *insn;
3335 int luid = 0;
3336
3337 if (!df)
3338 return;
3339
3340 df_collection_rec collection_rec;
3341 df_grow_bb_info (df_scan);
3342 if (scan_insns)
3343 /* Scan the block an insn at a time from beginning to end. */
3344 FOR_BB_INSNS (bb, insn)
3345 {
3346 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3347 gcc_assert (!insn_info);
3348
3349 insn_info = df_insn_create_insn_record (insn);
3350 if (INSN_P (insn))
3351 {
3352 /* Record refs within INSN. */
3353 DF_INSN_INFO_LUID (insn_info) = luid++;
3354 df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3355 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
3356 }
3357 DF_INSN_INFO_LUID (insn_info) = luid;
3358 }
3359
3360 /* Other block level artificial refs */
3361 df_bb_refs_collect (&collection_rec, bb);
3362 df_refs_add_to_chains (&collection_rec, bb, NULL, copy_all);
3363
3364 /* Now that the block has been processed, set the block as dirty so
3365 LR and LIVE will get it processed. */
3366 df_set_bb_dirty (bb);
3367 }
3368
3369
3370 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3371 block. */
3372
3373 static void
3374 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3375 {
3376 #ifdef EH_USES
3377 unsigned int i;
3378 #endif
3379
3380 bitmap_clear (regular_block_artificial_uses);
3381
3382 if (reload_completed)
3383 {
3384 if (frame_pointer_needed)
3385 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3386 }
3387 else
3388 /* Before reload, there are a few registers that must be forced
3389 live everywhere -- which might not already be the case for
3390 blocks within infinite loops. */
3391 {
3392 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3393
3394 /* Any reference to any pseudo before reload is a potential
3395 reference of the frame pointer. */
3396 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3397
3398 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3399 bitmap_set_bit (regular_block_artificial_uses,
3400 HARD_FRAME_POINTER_REGNUM);
3401
3402 /* Pseudos with argument area equivalences may require
3403 reloading via the argument pointer. */
3404 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3405 && fixed_regs[ARG_POINTER_REGNUM])
3406 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3407
3408 /* Any constant, or pseudo with constant equivalences, may
3409 require reloading from memory using the pic register. */
3410 if (picreg != INVALID_REGNUM
3411 && fixed_regs[picreg])
3412 bitmap_set_bit (regular_block_artificial_uses, picreg);
3413 }
3414 /* The all-important stack pointer must always be live. */
3415 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3416
3417 #ifdef EH_USES
3418 /* EH_USES registers are used:
3419 1) at all insns that might throw (calls or with -fnon-call-exceptions
3420 trapping insns)
3421 2) in all EH edges
3422 3) to support backtraces and/or debugging, anywhere between their
3423 initialization and where they the saved registers are restored
3424 from them, including the cases where we don't reach the epilogue
3425 (noreturn call or infinite loop). */
3426 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3427 if (EH_USES (i))
3428 bitmap_set_bit (regular_block_artificial_uses, i);
3429 #endif
3430 }
3431
3432
3433 /* Get the artificial use set for an eh block. */
3434
3435 static void
3436 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3437 {
3438 bitmap_clear (eh_block_artificial_uses);
3439
3440 /* The following code (down through the arg_pointer setting APPEARS
3441 to be necessary because there is nothing that actually
3442 describes what the exception handling code may actually need
3443 to keep alive. */
3444 if (reload_completed)
3445 {
3446 if (frame_pointer_needed)
3447 {
3448 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3449 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3450 bitmap_set_bit (eh_block_artificial_uses,
3451 HARD_FRAME_POINTER_REGNUM);
3452 }
3453 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3454 && fixed_regs[ARG_POINTER_REGNUM])
3455 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3456 }
3457 }
3458
3459
3460 \f
3461 /*----------------------------------------------------------------------------
3462 Specialized hard register scanning functions.
3463 ----------------------------------------------------------------------------*/
3464
3465
3466 /* Mark a register in SET. Hard registers in large modes get all
3467 of their component registers set as well. */
3468
3469 static void
3470 df_mark_reg (rtx reg, void *vset)
3471 {
3472 bitmap_set_range ((bitmap) vset, REGNO (reg), REG_NREGS (reg));
3473 }
3474
3475
3476 /* Set the bit for regs that are considered being defined at the entry. */
3477
3478 static void
3479 df_get_entry_block_def_set (bitmap entry_block_defs)
3480 {
3481 rtx r;
3482 int i;
3483
3484 bitmap_clear (entry_block_defs);
3485
3486 /* For separate shrink-wrapping we use LIVE to analyze which basic blocks
3487 need a prologue for some component to be executed before that block,
3488 and we do not care about any other registers. Hence, we do not want
3489 any register for any component defined in the entry block, and we can
3490 just leave all registers undefined. */
3491 if (df_scan->local_flags & DF_SCAN_EMPTY_ENTRY_EXIT)
3492 return;
3493
3494 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3495 {
3496 if (global_regs[i])
3497 bitmap_set_bit (entry_block_defs, i);
3498 if (FUNCTION_ARG_REGNO_P (i))
3499 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3500 }
3501
3502 /* The always important stack pointer. */
3503 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3504
3505 /* Once the prologue has been generated, all of these registers
3506 should just show up in the first regular block. */
3507 if (targetm.have_prologue () && epilogue_completed)
3508 {
3509 /* Defs for the callee saved registers are inserted so that the
3510 pushes have some defining location. */
3511 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3512 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3513 bitmap_set_bit (entry_block_defs, i);
3514 }
3515
3516 r = targetm.calls.struct_value_rtx (current_function_decl, true);
3517 if (r && REG_P (r))
3518 bitmap_set_bit (entry_block_defs, REGNO (r));
3519
3520 /* If the function has an incoming STATIC_CHAIN, it has to show up
3521 in the entry def set. */
3522 r = rtx_for_static_chain (current_function_decl, true);
3523 if (r && REG_P (r))
3524 bitmap_set_bit (entry_block_defs, REGNO (r));
3525
3526 if ((!reload_completed) || frame_pointer_needed)
3527 {
3528 /* Any reference to any pseudo before reload is a potential
3529 reference of the frame pointer. */
3530 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3531
3532 /* If they are different, also mark the hard frame pointer as live. */
3533 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3534 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3535 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3536 }
3537
3538 /* These registers are live everywhere. */
3539 if (!reload_completed)
3540 {
3541 /* Pseudos with argument area equivalences may require
3542 reloading via the argument pointer. */
3543 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3544 && fixed_regs[ARG_POINTER_REGNUM])
3545 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3546
3547 /* Any constant, or pseudo with constant equivalences, may
3548 require reloading from memory using the pic register. */
3549 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3550 if (picreg != INVALID_REGNUM
3551 && fixed_regs[picreg])
3552 bitmap_set_bit (entry_block_defs, picreg);
3553 }
3554
3555 #ifdef INCOMING_RETURN_ADDR_RTX
3556 if (REG_P (INCOMING_RETURN_ADDR_RTX))
3557 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3558 #endif
3559
3560 targetm.extra_live_on_entry (entry_block_defs);
3561 }
3562
3563
3564 /* Return the (conservative) set of hard registers that are defined on
3565 entry to the function.
3566 It uses df->entry_block_defs to determine which register
3567 reference to include. */
3568
3569 static void
3570 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3571 bitmap entry_block_defs)
3572 {
3573 unsigned int i;
3574 bitmap_iterator bi;
3575
3576 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3577 {
3578 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3579 ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_DEF, 0);
3580 }
3581
3582 df_canonize_collection_rec (collection_rec);
3583 }
3584
3585
3586 /* Record the (conservative) set of hard registers that are defined on
3587 entry to the function. */
3588
3589 static void
3590 df_record_entry_block_defs (bitmap entry_block_defs)
3591 {
3592 struct df_collection_rec collection_rec;
3593 df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3594
3595 /* Process bb_refs chain */
3596 df_refs_add_to_chains (&collection_rec,
3597 BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK),
3598 NULL,
3599 copy_defs);
3600 }
3601
3602
3603 /* Update the defs in the entry block. */
3604
3605 void
3606 df_update_entry_block_defs (void)
3607 {
3608 bool changed = false;
3609
3610 auto_bitmap refs (&df_bitmap_obstack);
3611 df_get_entry_block_def_set (refs);
3612 if (df->entry_block_defs)
3613 {
3614 if (!bitmap_equal_p (df->entry_block_defs, refs))
3615 {
3616 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3617 df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3618 df_ref_chain_delete (bb_info->artificial_defs);
3619 bb_info->artificial_defs = NULL;
3620 changed = true;
3621 }
3622 }
3623 else
3624 {
3625 struct df_scan_problem_data *problem_data
3626 = (struct df_scan_problem_data *) df_scan->problem_data;
3627 gcc_unreachable ();
3628 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3629 changed = true;
3630 }
3631
3632 if (changed)
3633 {
3634 df_record_entry_block_defs (refs);
3635 bitmap_copy (df->entry_block_defs, refs);
3636 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
3637 }
3638 }
3639
3640
3641 /* Set the bit for regs that are considered being used at the exit. */
3642
3643 static void
3644 df_get_exit_block_use_set (bitmap exit_block_uses)
3645 {
3646 unsigned int i;
3647 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3648
3649 bitmap_clear (exit_block_uses);
3650
3651 /* For separate shrink-wrapping we use LIVE to analyze which basic blocks
3652 need an epilogue for some component to be executed after that block,
3653 and we do not care about any other registers. Hence, we do not want
3654 any register for any component seen as used in the exit block, and we
3655 can just say no registers at all are used. */
3656 if (df_scan->local_flags & DF_SCAN_EMPTY_ENTRY_EXIT)
3657 return;
3658
3659 /* Stack pointer is always live at the exit. */
3660 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3661
3662 /* Mark the frame pointer if needed at the end of the function.
3663 If we end up eliminating it, it will be removed from the live
3664 list of each basic block by reload. */
3665
3666 if ((!reload_completed) || frame_pointer_needed)
3667 {
3668 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3669
3670 /* If they are different, also mark the hard frame pointer as live. */
3671 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3672 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3673 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3674 }
3675
3676 /* Many architectures have a GP register even without flag_pic.
3677 Assume the pic register is not in use, or will be handled by
3678 other means, if it is not fixed. */
3679 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3680 && picreg != INVALID_REGNUM
3681 && fixed_regs[picreg])
3682 bitmap_set_bit (exit_block_uses, picreg);
3683
3684 /* Mark all global registers, and all registers used by the
3685 epilogue as being live at the end of the function since they
3686 may be referenced by our caller. */
3687 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3688 if (global_regs[i] || EPILOGUE_USES (i))
3689 bitmap_set_bit (exit_block_uses, i);
3690
3691 if (targetm.have_epilogue () && epilogue_completed)
3692 {
3693 /* Mark all call-saved registers that we actually used. */
3694 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3695 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3696 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3697 bitmap_set_bit (exit_block_uses, i);
3698 }
3699
3700 /* Mark the registers that will contain data for the handler. */
3701 if (reload_completed && crtl->calls_eh_return)
3702 for (i = 0; ; ++i)
3703 {
3704 unsigned regno = EH_RETURN_DATA_REGNO (i);
3705 if (regno == INVALID_REGNUM)
3706 break;
3707 bitmap_set_bit (exit_block_uses, regno);
3708 }
3709
3710 #ifdef EH_RETURN_STACKADJ_RTX
3711 if ((!targetm.have_epilogue () || ! epilogue_completed)
3712 && crtl->calls_eh_return)
3713 {
3714 rtx tmp = EH_RETURN_STACKADJ_RTX;
3715 if (tmp && REG_P (tmp))
3716 df_mark_reg (tmp, exit_block_uses);
3717 }
3718 #endif
3719
3720 if ((!targetm.have_epilogue () || ! epilogue_completed)
3721 && crtl->calls_eh_return)
3722 {
3723 rtx tmp = EH_RETURN_HANDLER_RTX;
3724 if (tmp && REG_P (tmp))
3725 df_mark_reg (tmp, exit_block_uses);
3726 }
3727
3728 /* Mark function return value. */
3729 diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3730 }
3731
3732
3733 /* Return the refs of hard registers that are used in the exit block.
3734 It uses df->exit_block_uses to determine register to include. */
3735
3736 static void
3737 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
3738 {
3739 unsigned int i;
3740 bitmap_iterator bi;
3741
3742 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3743 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3744 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3745
3746 /* It is deliberate that this is not put in the exit block uses but
3747 I do not know why. */
3748 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3749 && reload_completed
3750 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3751 && bb_has_eh_pred (EXIT_BLOCK_PTR_FOR_FN (cfun))
3752 && fixed_regs[ARG_POINTER_REGNUM])
3753 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3754 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3755
3756 df_canonize_collection_rec (collection_rec);
3757 }
3758
3759
3760 /* Record the set of hard registers that are used in the exit block.
3761 It uses df->exit_block_uses to determine which bit to include. */
3762
3763 static void
3764 df_record_exit_block_uses (bitmap exit_block_uses)
3765 {
3766 struct df_collection_rec collection_rec;
3767 df_exit_block_uses_collect (&collection_rec, exit_block_uses);
3768
3769 /* Process bb_refs chain */
3770 df_refs_add_to_chains (&collection_rec,
3771 BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK),
3772 NULL,
3773 copy_uses);
3774 }
3775
3776
3777 /* Update the uses in the exit block. */
3778
3779 void
3780 df_update_exit_block_uses (void)
3781 {
3782 bool changed = false;
3783
3784 auto_bitmap refs (&df_bitmap_obstack);
3785 df_get_exit_block_use_set (refs);
3786 if (df->exit_block_uses)
3787 {
3788 if (!bitmap_equal_p (df->exit_block_uses, refs))
3789 {
3790 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3791 df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3792 df_ref_chain_delete (bb_info->artificial_uses);
3793 bb_info->artificial_uses = NULL;
3794 changed = true;
3795 }
3796 }
3797 else
3798 {
3799 struct df_scan_problem_data *problem_data
3800 = (struct df_scan_problem_data *) df_scan->problem_data;
3801 gcc_unreachable ();
3802 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3803 changed = true;
3804 }
3805
3806 if (changed)
3807 {
3808 df_record_exit_block_uses (refs);
3809 bitmap_copy (df->exit_block_uses, refs);
3810 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
3811 }
3812 }
3813
3814 static bool initialized = false;
3815
3816
3817 /* Initialize some platform specific structures. */
3818
3819 void
3820 df_hard_reg_init (void)
3821 {
3822 int i;
3823 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3824
3825 if (initialized)
3826 return;
3827
3828 /* Record which registers will be eliminated. We use this in
3829 mark_used_regs. */
3830 CLEAR_HARD_REG_SET (elim_reg_set);
3831
3832 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3833 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3834
3835 initialized = true;
3836 }
3837
3838
3839 /* Recompute the parts of scanning that are based on regs_ever_live
3840 because something changed in that array. */
3841
3842 void
3843 df_update_entry_exit_and_calls (void)
3844 {
3845 basic_block bb;
3846
3847 df_update_entry_block_defs ();
3848 df_update_exit_block_uses ();
3849
3850 /* The call insns need to be rescanned because there may be changes
3851 in the set of registers clobbered across the call. */
3852 FOR_EACH_BB_FN (bb, cfun)
3853 {
3854 rtx_insn *insn;
3855 FOR_BB_INSNS (bb, insn)
3856 {
3857 if (INSN_P (insn) && CALL_P (insn))
3858 df_insn_rescan (insn);
3859 }
3860 }
3861 }
3862
3863
3864 /* Return true if hard REG is actually used in the some instruction.
3865 There are a fair number of conditions that affect the setting of
3866 this array. See the comment in df.h for df->hard_regs_live_count
3867 for the conditions that this array is set. */
3868
3869 bool
3870 df_hard_reg_used_p (unsigned int reg)
3871 {
3872 return df->hard_regs_live_count[reg] != 0;
3873 }
3874
3875
3876 /* A count of the number of times REG is actually used in the some
3877 instruction. There are a fair number of conditions that affect the
3878 setting of this array. See the comment in df.h for
3879 df->hard_regs_live_count for the conditions that this array is
3880 set. */
3881
3882
3883 unsigned int
3884 df_hard_reg_used_count (unsigned int reg)
3885 {
3886 return df->hard_regs_live_count[reg];
3887 }
3888
3889
3890 /* Get the value of regs_ever_live[REGNO]. */
3891
3892 bool
3893 df_regs_ever_live_p (unsigned int regno)
3894 {
3895 return regs_ever_live[regno];
3896 }
3897
3898
3899 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3900 to change, schedule that change for the next update. */
3901
3902 void
3903 df_set_regs_ever_live (unsigned int regno, bool value)
3904 {
3905 if (regs_ever_live[regno] == value)
3906 return;
3907
3908 regs_ever_live[regno] = value;
3909 if (df)
3910 df->redo_entry_and_exit = true;
3911 }
3912
3913
3914 /* Compute "regs_ever_live" information from the underlying df
3915 information. Set the vector to all false if RESET. */
3916
3917 void
3918 df_compute_regs_ever_live (bool reset)
3919 {
3920 unsigned int i;
3921 bool changed = df->redo_entry_and_exit;
3922
3923 if (reset)
3924 memset (regs_ever_live, 0, sizeof (regs_ever_live));
3925
3926 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3927 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3928 {
3929 regs_ever_live[i] = true;
3930 changed = true;
3931 }
3932 if (changed)
3933 df_update_entry_exit_and_calls ();
3934 df->redo_entry_and_exit = false;
3935 }
3936
3937 \f
3938 /*----------------------------------------------------------------------------
3939 Dataflow ref information verification functions.
3940
3941 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3942 df_reg_chain_verify_unmarked (refs)
3943 df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
3944 df_mws_verify (mw*, mw*, bool)
3945 df_insn_refs_verify (collection_rec, bb, insn, bool)
3946 df_bb_refs_verify (bb, refs, bool)
3947 df_bb_verify (bb)
3948 df_exit_block_bitmap_verify (bool)
3949 df_entry_block_bitmap_verify (bool)
3950 df_scan_verify ()
3951 ----------------------------------------------------------------------------*/
3952
3953
3954 /* Mark all refs in the reg chain. Verify that all of the registers
3955 are in the correct chain. */
3956
3957 static unsigned int
3958 df_reg_chain_mark (df_ref refs, unsigned int regno,
3959 bool is_def, bool is_eq_use)
3960 {
3961 unsigned int count = 0;
3962 df_ref ref;
3963 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
3964 {
3965 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
3966
3967 /* If there are no def-use or use-def chains, make sure that all
3968 of the chains are clear. */
3969 if (!df_chain)
3970 gcc_assert (!DF_REF_CHAIN (ref));
3971
3972 /* Check to make sure the ref is in the correct chain. */
3973 gcc_assert (DF_REF_REGNO (ref) == regno);
3974 if (is_def)
3975 gcc_assert (DF_REF_REG_DEF_P (ref));
3976 else
3977 gcc_assert (!DF_REF_REG_DEF_P (ref));
3978
3979 if (is_eq_use)
3980 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
3981 else
3982 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
3983
3984 if (DF_REF_NEXT_REG (ref))
3985 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
3986 count++;
3987 DF_REF_REG_MARK (ref);
3988 }
3989 return count;
3990 }
3991
3992
3993 /* Verify that all of the registers in the chain are unmarked. */
3994
3995 static void
3996 df_reg_chain_verify_unmarked (df_ref refs)
3997 {
3998 df_ref ref;
3999 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4000 gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4001 }
4002
4003
4004 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4005
4006 static bool
4007 df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec,
4008 bool abort_if_fail)
4009 {
4010 unsigned int ix;
4011 df_ref new_ref;
4012
4013 FOR_EACH_VEC_ELT (*new_rec, ix, new_ref)
4014 {
4015 if (old_rec == NULL || !df_ref_equal_p (new_ref, old_rec))
4016 {
4017 if (abort_if_fail)
4018 gcc_assert (0);
4019 else
4020 return false;
4021 }
4022
4023 /* Abort if fail is called from the function level verifier. If
4024 that is the context, mark this reg as being seem. */
4025 if (abort_if_fail)
4026 {
4027 gcc_assert (DF_REF_IS_REG_MARKED (old_rec));
4028 DF_REF_REG_UNMARK (old_rec);
4029 }
4030
4031 old_rec = DF_REF_NEXT_LOC (old_rec);
4032 }
4033
4034 if (abort_if_fail)
4035 gcc_assert (old_rec == NULL);
4036 else
4037 return old_rec == NULL;
4038 return false;
4039 }
4040
4041
4042 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4043
4044 static bool
4045 df_mws_verify (const vec<df_mw_hardreg *, va_heap> *new_rec,
4046 struct df_mw_hardreg *old_rec,
4047 bool abort_if_fail)
4048 {
4049 unsigned int ix;
4050 struct df_mw_hardreg *new_reg;
4051
4052 FOR_EACH_VEC_ELT (*new_rec, ix, new_reg)
4053 {
4054 if (old_rec == NULL || !df_mw_equal_p (new_reg, old_rec))
4055 {
4056 if (abort_if_fail)
4057 gcc_assert (0);
4058 else
4059 return false;
4060 }
4061 old_rec = DF_MWS_NEXT (old_rec);
4062 }
4063
4064 if (abort_if_fail)
4065 gcc_assert (old_rec == NULL);
4066 else
4067 return old_rec == NULL;
4068 return false;
4069 }
4070
4071
4072 /* Return true if the existing insn refs information is complete and
4073 correct. Otherwise (i.e. if there's any missing or extra refs),
4074 return the correct df_ref chain in REFS_RETURN.
4075
4076 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4077 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4078 verification mode instead of the whole function, so unmark
4079 everything.
4080
4081 If ABORT_IF_FAIL is set, this function never returns false. */
4082
4083 static bool
4084 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4085 basic_block bb,
4086 rtx_insn *insn,
4087 bool abort_if_fail)
4088 {
4089 bool ret1, ret2, ret3;
4090 unsigned int uid = INSN_UID (insn);
4091 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4092
4093 df_insn_refs_collect (collection_rec, bb, insn_info);
4094
4095 /* Unfortunately we cannot opt out early if one of these is not
4096 right and abort_if_fail is set because the marks will not get cleared. */
4097 ret1 = df_refs_verify (&collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4098 abort_if_fail);
4099 if (!ret1 && !abort_if_fail)
4100 return false;
4101 ret2 = df_refs_verify (&collection_rec->use_vec, DF_INSN_UID_USES (uid),
4102 abort_if_fail);
4103 if (!ret2 && !abort_if_fail)
4104 return false;
4105 ret3 = df_refs_verify (&collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4106 abort_if_fail);
4107 if (!ret3 && !abort_if_fail)
4108 return false;
4109 if (! df_mws_verify (&collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4110 abort_if_fail))
4111 return false;
4112 return (ret1 && ret2 && ret3);
4113 }
4114
4115
4116 /* Return true if all refs in the basic block are correct and complete.
4117 Due to df_ref_chain_verify, it will cause all refs
4118 that are verified to have DF_REF_MARK bit set. */
4119
4120 static bool
4121 df_bb_verify (basic_block bb)
4122 {
4123 rtx_insn *insn;
4124 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4125 struct df_collection_rec collection_rec;
4126
4127 gcc_assert (bb_info);
4128
4129 /* Scan the block, one insn at a time, from beginning to end. */
4130 FOR_BB_INSNS_REVERSE (bb, insn)
4131 {
4132 if (!INSN_P (insn))
4133 continue;
4134 df_insn_refs_verify (&collection_rec, bb, insn, true);
4135 df_free_collection_rec (&collection_rec);
4136 }
4137
4138 /* Do the artificial defs and uses. */
4139 df_bb_refs_collect (&collection_rec, bb);
4140 df_refs_verify (&collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4141 df_refs_verify (&collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4142 df_free_collection_rec (&collection_rec);
4143
4144 return true;
4145 }
4146
4147
4148 /* Returns true if the entry block has correct and complete df_ref set.
4149 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4150
4151 static bool
4152 df_entry_block_bitmap_verify (bool abort_if_fail)
4153 {
4154 bool is_eq;
4155
4156 auto_bitmap entry_block_defs (&df_bitmap_obstack);
4157 df_get_entry_block_def_set (entry_block_defs);
4158
4159 is_eq = bitmap_equal_p (entry_block_defs, df->entry_block_defs);
4160
4161 if (!is_eq && abort_if_fail)
4162 {
4163 fprintf (stderr, "entry_block_defs = ");
4164 df_print_regset (stderr, entry_block_defs);
4165 fprintf (stderr, "df->entry_block_defs = ");
4166 df_print_regset (stderr, df->entry_block_defs);
4167 gcc_assert (0);
4168 }
4169
4170 return is_eq;
4171 }
4172
4173
4174 /* Returns true if the exit block has correct and complete df_ref set.
4175 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4176
4177 static bool
4178 df_exit_block_bitmap_verify (bool abort_if_fail)
4179 {
4180 bool is_eq;
4181
4182 auto_bitmap exit_block_uses (&df_bitmap_obstack);
4183 df_get_exit_block_use_set (exit_block_uses);
4184
4185 is_eq = bitmap_equal_p (exit_block_uses, df->exit_block_uses);
4186
4187 if (!is_eq && abort_if_fail)
4188 {
4189 fprintf (stderr, "exit_block_uses = ");
4190 df_print_regset (stderr, exit_block_uses);
4191 fprintf (stderr, "df->exit_block_uses = ");
4192 df_print_regset (stderr, df->exit_block_uses);
4193 gcc_assert (0);
4194 }
4195
4196 return is_eq;
4197 }
4198
4199
4200 /* Return true if df_ref information for all insns in all blocks are
4201 correct and complete. */
4202
4203 void
4204 df_scan_verify (void)
4205 {
4206 unsigned int i;
4207 basic_block bb;
4208
4209 if (!df)
4210 return;
4211
4212 /* Verification is a 4 step process. */
4213
4214 /* (1) All of the refs are marked by going through the reg chains. */
4215 for (i = 0; i < DF_REG_SIZE (df); i++)
4216 {
4217 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4218 == DF_REG_DEF_COUNT (i));
4219 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4220 == DF_REG_USE_COUNT (i));
4221 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4222 == DF_REG_EQ_USE_COUNT (i));
4223 }
4224
4225 /* (2) There are various bitmaps whose value may change over the
4226 course of the compilation. This step recomputes them to make
4227 sure that they have not slipped out of date. */
4228 auto_bitmap regular_block_artificial_uses (&df_bitmap_obstack);
4229 auto_bitmap eh_block_artificial_uses (&df_bitmap_obstack);
4230
4231 df_get_regular_block_artificial_uses (regular_block_artificial_uses);
4232 df_get_eh_block_artificial_uses (eh_block_artificial_uses);
4233
4234 bitmap_ior_into (eh_block_artificial_uses,
4235 regular_block_artificial_uses);
4236
4237 /* Check artificial_uses bitmaps didn't change. */
4238 gcc_assert (bitmap_equal_p (regular_block_artificial_uses,
4239 &df->regular_block_artificial_uses));
4240 gcc_assert (bitmap_equal_p (eh_block_artificial_uses,
4241 &df->eh_block_artificial_uses));
4242
4243 /* Verify entry block and exit block. These only verify the bitmaps,
4244 the refs are verified in df_bb_verify. */
4245 df_entry_block_bitmap_verify (true);
4246 df_exit_block_bitmap_verify (true);
4247
4248 /* (3) All of the insns in all of the blocks are traversed and the
4249 marks are cleared both in the artificial refs attached to the
4250 blocks and the real refs inside the insns. It is a failure to
4251 clear a mark that has not been set as this means that the ref in
4252 the block or insn was not in the reg chain. */
4253
4254 FOR_ALL_BB_FN (bb, cfun)
4255 df_bb_verify (bb);
4256
4257 /* (4) See if all reg chains are traversed a second time. This time
4258 a check is made that the marks are clear. A set mark would be a
4259 from a reg that is not in any insn or basic block. */
4260
4261 for (i = 0; i < DF_REG_SIZE (df); i++)
4262 {
4263 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4264 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4265 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));
4266 }
4267 }
Mirror of the offical gcc git repository hosted at gcc.gnu.org