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