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