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