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