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