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