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