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