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