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