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