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