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