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