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