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