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