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