]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/df-problems.c
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge dataflow branch into mainline
[thirdparty/gcc.git] / gcc / df-problems.c
CommitLineData
e011eba9 1/* Standard problems for dataflow support routines.
3072d30e 2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
e011eba9 3 Free Software Foundation, Inc.
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
13Software Foundation; either version 2, or (at your option) any later
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
22along with GCC; see the file COPYING. If not, write to the Free
23Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2402110-1301, USA. */
25
26#include "config.h"
27#include "system.h"
28#include "coretypes.h"
29#include "tm.h"
30#include "rtl.h"
31#include "tm_p.h"
32#include "insn-config.h"
33#include "recog.h"
34#include "function.h"
35#include "regs.h"
36#include "output.h"
37#include "alloc-pool.h"
38#include "flags.h"
39#include "hard-reg-set.h"
40#include "basic-block.h"
41#include "sbitmap.h"
42#include "bitmap.h"
43#include "timevar.h"
44#include "df.h"
3e6933a8 45#include "except.h"
3072d30e 46#include "dce.h"
47#include "vecprim.h"
3e6933a8 48
49#if 0
50#define REG_DEAD_DEBUGGING
51#endif
e011eba9 52
53#define DF_SPARSE_THRESHOLD 32
54
55static bitmap seen_in_block = NULL;
56static bitmap seen_in_insn = NULL;
57
58\f
59/*----------------------------------------------------------------------------
60 Public functions access functions for the dataflow problems.
61----------------------------------------------------------------------------*/
3072d30e 62/* Get the live at out set for BB no matter what problem happens to be
63 defined. This function is used by the register allocators who
64 choose different dataflow problems depending on the optimization
65 level. */
e011eba9 66
3072d30e 67bitmap
68df_get_live_out (basic_block bb)
e011eba9 69{
3072d30e 70 gcc_assert (df_lr);
e011eba9 71
3072d30e 72 if (df_urec)
73 return DF_RA_LIVE_OUT (bb);
74 else if (df_live)
75 return DF_LIVE_OUT (bb);
76 else
77 return DF_LR_OUT (bb);
e011eba9 78}
79
3072d30e 80/* Get the live at in set for BB no matter what problem happens to be
81 defined. This function is used by the register allocators who
82 choose different dataflow problems depending on the optimization
83 level. */
e011eba9 84
85bitmap
3072d30e 86df_get_live_in (basic_block bb)
e011eba9 87{
3072d30e 88 gcc_assert (df_lr);
e011eba9 89
3072d30e 90 if (df_urec)
91 return DF_RA_LIVE_IN (bb);
92 else if (df_live)
93 return DF_LIVE_IN (bb);
e011eba9 94 else
3072d30e 95 return DF_LR_IN (bb);
e011eba9 96}
97
3072d30e 98/* Get the live at top set for BB no matter what problem happens to be
99 defined. This function is used by the register allocators who
100 choose different dataflow problems depending on the optimization
101 level. */
e011eba9 102
103bitmap
3072d30e 104df_get_live_top (basic_block bb)
e011eba9 105{
3072d30e 106 gcc_assert (df_lr);
e011eba9 107
3072d30e 108 if (df_urec)
109 return DF_RA_LIVE_TOP (bb);
e011eba9 110 else
3072d30e 111 return DF_LR_TOP (bb);
e011eba9 112}
113
114
115/*----------------------------------------------------------------------------
116 Utility functions.
117----------------------------------------------------------------------------*/
118
119/* Generic versions to get the void* version of the block info. Only
334ec2d8 120 used inside the problem instance vectors. */
e011eba9 121
122/* Grow the bb_info array. */
123
124void
125df_grow_bb_info (struct dataflow *dflow)
126{
127 unsigned int new_size = last_basic_block + 1;
128 if (dflow->block_info_size < new_size)
129 {
130 new_size += new_size / 4;
131 dflow->block_info = xrealloc (dflow->block_info,
132 new_size *sizeof (void*));
133 memset (dflow->block_info + dflow->block_info_size, 0,
134 (new_size - dflow->block_info_size) *sizeof (void *));
135 dflow->block_info_size = new_size;
136 }
137}
138
139/* Dump a def-use or use-def chain for REF to FILE. */
140
141void
3e6933a8 142df_chain_dump (struct df_link *link, FILE *file)
e011eba9 143{
144 fprintf (file, "{ ");
145 for (; link; link = link->next)
146 {
147 fprintf (file, "%c%d(bb %d insn %d) ",
148 DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
149 DF_REF_ID (link->ref),
150 DF_REF_BBNO (link->ref),
151 DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
152 }
153 fprintf (file, "}");
154}
155
156
157/* Print some basic block info as part of df_dump. */
158
159void
160df_print_bb_index (basic_block bb, FILE *file)
161{
162 edge e;
163 edge_iterator ei;
164
3072d30e 165 fprintf (file, "\n( ");
e011eba9 166 FOR_EACH_EDGE (e, ei, bb->preds)
167 {
168 basic_block pred = e->src;
3072d30e 169 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
e011eba9 170 }
171 fprintf (file, ")->[%d]->( ", bb->index);
172 FOR_EACH_EDGE (e, ei, bb->succs)
173 {
174 basic_block succ = e->dest;
3072d30e 175 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
e011eba9 176 }
177 fprintf (file, ")\n");
178}
179
180
e011eba9 181
182/* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
183 up correctly. */
184
185static void
186df_set_seen (void)
187{
3072d30e 188 seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
189 seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
e011eba9 190}
191
192
193static void
194df_unset_seen (void)
195{
196 BITMAP_FREE (seen_in_block);
197 BITMAP_FREE (seen_in_insn);
198}
199
200
201\f
202/*----------------------------------------------------------------------------
203 REACHING USES
204
205 Find the locations in the function where each use site for a pseudo
aa7aac1f 206 can reach backwards. In and out bitvectors are built for each basic
207 block. The id field in the ref is used to index into these sets.
208 See df.h for details.
e011eba9 209
210----------------------------------------------------------------------------*/
211
aa7aac1f 212/* This problem plays a large number of games for the sake of
213 efficiency.
214
215 1) The order of the bits in the bitvectors. After the scanning
216 phase, all of the uses are sorted. All of the uses for the reg 0
217 are first, followed by all uses for reg 1 and so on.
218
219 2) There are two kill sets, one if the number of uses is less or
220 equal to DF_SPARSE_THRESHOLD and another if it is greater.
221
3072d30e 222 <= : Data is built directly in the kill set.
aa7aac1f 223
224 > : One level of indirection is used to keep from generating long
225 strings of 1 bits in the kill sets. Bitvectors that are indexed
226 by the regnum are used to represent that there is a killing def
227 for the register. The confluence and transfer functions use
228 these along with the bitmap_clear_range call to remove ranges of
229 bits without actually generating a knockout vector.
230
231 The kill and sparse_kill and the dense_invalidated_by_call and
3072d30e 232 sparse_invalidated_by_call both play this game. */
aa7aac1f 233
234/* Private data used to compute the solution for this problem. These
554f2707 235 data structures are not accessible outside of this module. */
e011eba9 236struct df_ru_problem_data
237{
e011eba9 238 /* The set of defs to regs invalidated by call. */
239 bitmap sparse_invalidated_by_call;
fcf2ad9f 240 /* The set of defs to regs invalidated by call for ru. */
3072d30e 241 bitmap dense_invalidated_by_call;
242 /* An obstack for the bitmaps we need for this problem. */
243 bitmap_obstack ru_bitmaps;
e011eba9 244};
245
e011eba9 246/* Set basic block info. */
247
248static void
3072d30e 249df_ru_set_bb_info (unsigned int index, struct df_ru_bb_info *bb_info)
e011eba9 250{
3072d30e 251 gcc_assert (df_ru);
252 gcc_assert (index < df_ru->block_info_size);
253 df_ru->block_info[index] = bb_info;
e011eba9 254}
255
256
257/* Free basic block info. */
258
259static void
3072d30e 260df_ru_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
d0802b39 261 void *vbb_info)
e011eba9 262{
263 struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info;
264 if (bb_info)
265 {
266 BITMAP_FREE (bb_info->kill);
267 BITMAP_FREE (bb_info->sparse_kill);
268 BITMAP_FREE (bb_info->gen);
269 BITMAP_FREE (bb_info->in);
270 BITMAP_FREE (bb_info->out);
3072d30e 271 pool_free (df_ru->block_pool, bb_info);
e011eba9 272 }
273}
274
275
3072d30e 276/* Allocate or reset bitmaps for DF_RU blocks. The solution bits are
e011eba9 277 not touched unless the block is new. */
278
279static void
3072d30e 280df_ru_alloc (bitmap all_blocks)
e011eba9 281{
282 unsigned int bb_index;
283 bitmap_iterator bi;
3072d30e 284 struct df_ru_problem_data *problem_data;
e011eba9 285
3072d30e 286 if (!df_ru->block_pool)
287 df_ru->block_pool = create_alloc_pool ("df_ru_block pool",
e011eba9 288 sizeof (struct df_ru_bb_info), 50);
289
3072d30e 290 if (df_ru->problem_data)
e011eba9 291 {
3072d30e 292 problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
e011eba9 293 bitmap_clear (problem_data->sparse_invalidated_by_call);
294 bitmap_clear (problem_data->dense_invalidated_by_call);
295 }
296 else
297 {
3072d30e 298 problem_data = XNEW (struct df_ru_problem_data);
299 df_ru->problem_data = problem_data;
300
301 bitmap_obstack_initialize (&problem_data->ru_bitmaps);
302 problem_data->sparse_invalidated_by_call
303 = BITMAP_ALLOC (&problem_data->ru_bitmaps);
304 problem_data->dense_invalidated_by_call
305 = BITMAP_ALLOC (&problem_data->ru_bitmaps);
e011eba9 306 }
307
3072d30e 308 df_grow_bb_info (df_ru);
e011eba9 309
310 /* Because of the clustering of all def sites for the same pseudo,
311 we have to process all of the blocks before doing the
312 analysis. */
313
3e6933a8 314 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
e011eba9 315 {
3072d30e 316 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
e011eba9 317 if (bb_info)
318 {
319 bitmap_clear (bb_info->kill);
320 bitmap_clear (bb_info->sparse_kill);
321 bitmap_clear (bb_info->gen);
322 }
323 else
324 {
3072d30e 325 bb_info = (struct df_ru_bb_info *) pool_alloc (df_ru->block_pool);
326 df_ru_set_bb_info (bb_index, bb_info);
327 bb_info->kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
328 bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
329 bb_info->gen = BITMAP_ALLOC (&problem_data->ru_bitmaps);
330 bb_info->in = BITMAP_ALLOC (&problem_data->ru_bitmaps);
331 bb_info->out = BITMAP_ALLOC (&problem_data->ru_bitmaps);
e011eba9 332 }
333 }
334}
335
336
337/* Process a list of DEFs for df_ru_bb_local_compute. */
338
339static void
3072d30e 340df_ru_bb_local_compute_process_def (struct df_ru_bb_info *bb_info,
341 struct df_ref **def_rec,
fcf2ad9f 342 enum df_ref_flags top_flag)
e011eba9 343{
3072d30e 344 while (*def_rec)
e011eba9 345 {
3072d30e 346 struct df_ref *def = *def_rec;
3e6933a8 347 if ((top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
348 /* If the def is to only part of the reg, it is as if it did
349 not happen, since some of the bits may get thru. */
3072d30e 350 && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
e011eba9 351 {
fcf2ad9f 352 unsigned int regno = DF_REF_REGNO (def);
3072d30e 353 unsigned int begin = DF_USES_BEGIN (regno);
354 unsigned int n_uses = DF_USES_COUNT (regno);
355
fcf2ad9f 356 if (!bitmap_bit_p (seen_in_block, regno))
e011eba9 357 {
02a8ad7e 358 /* The first def for regno in the insn, causes the kill
359 info to be generated. Do not modify the gen set
360 because the only values in it are the uses from here
361 to the top of the block and this def does not effect
362 them. */
fcf2ad9f 363 if (!bitmap_bit_p (seen_in_insn, regno))
e011eba9 364 {
fcf2ad9f 365 if (n_uses > DF_SPARSE_THRESHOLD)
02a8ad7e 366 bitmap_set_bit (bb_info->sparse_kill, regno);
fcf2ad9f 367 else
3072d30e 368 bitmap_set_range (bb_info->kill, begin, n_uses);
e011eba9 369 }
fcf2ad9f 370 bitmap_set_bit (seen_in_insn, regno);
e011eba9 371 }
e011eba9 372 }
3072d30e 373 def_rec++;
e011eba9 374 }
375}
376
377
378/* Process a list of USEs for df_ru_bb_local_compute. */
379
380static void
381df_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info,
3072d30e 382 struct df_ref **use_rec,
e011eba9 383 enum df_ref_flags top_flag)
384{
3072d30e 385 while (*use_rec)
e011eba9 386 {
3072d30e 387 struct df_ref *use = *use_rec;
e011eba9 388 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
389 {
390 /* Add use to set of gens in this BB unless we have seen a
391 def in a previous instruction. */
392 unsigned int regno = DF_REF_REGNO (use);
393 if (!bitmap_bit_p (seen_in_block, regno))
394 bitmap_set_bit (bb_info->gen, DF_REF_ID (use));
395 }
3072d30e 396 use_rec++;
e011eba9 397 }
398}
399
400/* Compute local reaching use (upward exposed use) info for basic
401 block BB. USE_INFO->REGS[R] caches the set of uses for register R. */
402static void
3072d30e 403df_ru_bb_local_compute (unsigned int bb_index)
e011eba9 404{
e011eba9 405 basic_block bb = BASIC_BLOCK (bb_index);
3072d30e 406 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
e011eba9 407 rtx insn;
408
409 /* Set when a def for regno is seen. */
410 bitmap_clear (seen_in_block);
411 bitmap_clear (seen_in_insn);
412
413#ifdef EH_USES
414 /* Variables defined in the prolog that are used by the exception
415 handler. */
416 df_ru_bb_local_compute_process_use (bb_info,
3072d30e 417 df_get_artificial_uses (bb_index),
e011eba9 418 DF_REF_AT_TOP);
419#endif
3072d30e 420 df_ru_bb_local_compute_process_def (bb_info,
421 df_get_artificial_defs (bb_index),
fcf2ad9f 422 DF_REF_AT_TOP);
e011eba9 423
424 FOR_BB_INSNS (bb, insn)
425 {
426 unsigned int uid = INSN_UID (insn);
3e6933a8 427 if (!INSN_P (insn))
e011eba9 428 continue;
429
e011eba9 430 df_ru_bb_local_compute_process_use (bb_info,
3072d30e 431 DF_INSN_UID_USES (uid), 0);
e011eba9 432
3072d30e 433 if (df->changeable_flags & DF_EQ_NOTES)
434 df_ru_bb_local_compute_process_use (bb_info,
435 DF_INSN_UID_EQ_USES (uid), 0);
436
437 df_ru_bb_local_compute_process_def (bb_info,
438 DF_INSN_UID_DEFS (uid), 0);
02a8ad7e 439
e011eba9 440 bitmap_ior_into (seen_in_block, seen_in_insn);
441 bitmap_clear (seen_in_insn);
442 }
443
444 /* Process the hardware registers that are always live. */
445 df_ru_bb_local_compute_process_use (bb_info,
3072d30e 446 df_get_artificial_uses (bb_index), 0);
fcf2ad9f 447
3072d30e 448 df_ru_bb_local_compute_process_def (bb_info,
449 df_get_artificial_defs (bb_index), 0);
e011eba9 450}
451
452
453/* Compute local reaching use (upward exposed use) info for each basic
454 block within BLOCKS. */
455static void
3072d30e 456df_ru_local_compute (bitmap all_blocks)
e011eba9 457{
e011eba9 458 unsigned int bb_index;
459 bitmap_iterator bi;
460 unsigned int regno;
3e6933a8 461 struct df_ru_problem_data *problem_data
3072d30e 462 = (struct df_ru_problem_data *) df_ru->problem_data;
e011eba9 463 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
464 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
465
466 df_set_seen ();
3072d30e 467
468 df_maybe_reorganize_use_refs (df->changeable_flags & DF_EQ_NOTES ?
469 DF_REF_ORDER_BY_REG_WITH_NOTES : DF_REF_ORDER_BY_REG);
e011eba9 470
471 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
472 {
3072d30e 473 df_ru_bb_local_compute (bb_index);
e011eba9 474 }
475
476 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
477 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
478 {
3072d30e 479 if (DF_USES_COUNT (regno) > DF_SPARSE_THRESHOLD)
e011eba9 480 bitmap_set_bit (sparse_invalidated, regno);
481 else
3072d30e 482 bitmap_set_range (dense_invalidated,
483 DF_USES_BEGIN (regno),
484 DF_USES_COUNT (regno));
e011eba9 485 }
486
487 df_unset_seen ();
488}
489
490
491/* Initialize the solution bit vectors for problem. */
492
493static void
3072d30e 494df_ru_init_solution (bitmap all_blocks)
e011eba9 495{
496 unsigned int bb_index;
497 bitmap_iterator bi;
498
499 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
500 {
3072d30e 501 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
e011eba9 502 bitmap_copy (bb_info->in, bb_info->gen);
503 bitmap_clear (bb_info->out);
504 }
505}
506
507
508/* Out of target gets or of in of source. */
509
510static void
3072d30e 511df_ru_confluence_n (edge e)
e011eba9 512{
3072d30e 513 bitmap op1 = df_ru_get_bb_info (e->src->index)->out;
514 bitmap op2 = df_ru_get_bb_info (e->dest->index)->in;
e011eba9 515
516 if (e->flags & EDGE_EH)
517 {
3e6933a8 518 struct df_ru_problem_data *problem_data
3072d30e 519 = (struct df_ru_problem_data *) df_ru->problem_data;
e011eba9 520 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
521 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
e011eba9 522 bitmap_iterator bi;
523 unsigned int regno;
3072d30e 524 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
716e25d4 525
526 bitmap_copy (tmp, op2);
527 bitmap_and_compl_into (tmp, dense_invalidated);
528
e011eba9 529 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
530 {
716e25d4 531 bitmap_clear_range (tmp,
3072d30e 532 DF_USES_BEGIN (regno),
533 DF_USES_COUNT (regno));
e011eba9 534 }
716e25d4 535 bitmap_ior_into (op1, tmp);
536 BITMAP_FREE (tmp);
e011eba9 537 }
538 else
539 bitmap_ior_into (op1, op2);
540}
541
542
543/* Transfer function. */
544
545static bool
3072d30e 546df_ru_transfer_function (int bb_index)
e011eba9 547{
3072d30e 548 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
e011eba9 549 unsigned int regno;
550 bitmap_iterator bi;
551 bitmap in = bb_info->in;
552 bitmap out = bb_info->out;
553 bitmap gen = bb_info->gen;
554 bitmap kill = bb_info->kill;
555 bitmap sparse_kill = bb_info->sparse_kill;
556
557 if (bitmap_empty_p (sparse_kill))
558 return bitmap_ior_and_compl (in, gen, out, kill);
559 else
560 {
3072d30e 561 struct df_ru_problem_data *problem_data;
562 bitmap tmp;
e011eba9 563 bool changed = false;
3072d30e 564
565 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
566 IN with TMP. Therefore, allocate TMP in the RU bitmaps obstack. */
567 problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
568 tmp = BITMAP_ALLOC (&problem_data->ru_bitmaps);
569
aa7aac1f 570 bitmap_copy (tmp, out);
e011eba9 571 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
572 {
573 bitmap_clear_range (tmp,
3072d30e 574 DF_USES_BEGIN (regno),
575 DF_USES_COUNT (regno));
e011eba9 576 }
577 bitmap_and_compl_into (tmp, kill);
578 bitmap_ior_into (tmp, gen);
716e25d4 579 changed = !bitmap_equal_p (tmp, in);
e011eba9 580 if (changed)
581 {
aa7aac1f 582 BITMAP_FREE (in);
e011eba9 583 bb_info->in = tmp;
584 }
585 else
586 BITMAP_FREE (tmp);
587 return changed;
588 }
589}
590
591
592/* Free all storage associated with the problem. */
593
594static void
3072d30e 595df_ru_free (void)
e011eba9 596{
597 unsigned int i;
3e6933a8 598 struct df_ru_problem_data *problem_data
3072d30e 599 = (struct df_ru_problem_data *) df_ru->problem_data;
e011eba9 600
d0802b39 601 if (problem_data)
e011eba9 602 {
3072d30e 603 for (i = 0; i < df_ru->block_info_size; i++)
e011eba9 604 {
3072d30e 605 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (i);
d0802b39 606 if (bb_info)
607 {
608 BITMAP_FREE (bb_info->kill);
609 BITMAP_FREE (bb_info->sparse_kill);
610 BITMAP_FREE (bb_info->gen);
611 BITMAP_FREE (bb_info->in);
612 BITMAP_FREE (bb_info->out);
613 }
e011eba9 614 }
d0802b39 615
3072d30e 616 free_alloc_pool (df_ru->block_pool);
d0802b39 617 BITMAP_FREE (problem_data->sparse_invalidated_by_call);
618 BITMAP_FREE (problem_data->dense_invalidated_by_call);
3072d30e 619 bitmap_obstack_release (&problem_data->ru_bitmaps);
d0802b39 620
3072d30e 621 df_ru->block_info_size = 0;
622 free (df_ru->block_info);
623 free (df_ru->problem_data);
e011eba9 624 }
3072d30e 625 free (df_ru);
e011eba9 626}
627
628
629/* Debugging info. */
630
631static void
3072d30e 632df_ru_start_dump (FILE *file)
e011eba9 633{
3e6933a8 634 struct df_ru_problem_data *problem_data
3072d30e 635 = (struct df_ru_problem_data *) df_ru->problem_data;
636 unsigned int m = DF_REG_SIZE(df);
e011eba9 637 unsigned int regno;
3e6933a8 638
3072d30e 639 if (!df_ru->block_info)
3e6933a8 640 return;
e011eba9 641
3072d30e 642 fprintf (file, ";; Reaching uses:\n");
e011eba9 643
3072d30e 644 fprintf (file, ";; sparse invalidated \t");
e011eba9 645 dump_bitmap (file, problem_data->sparse_invalidated_by_call);
3072d30e 646 fprintf (file, " dense invalidated \t");
e011eba9 647 dump_bitmap (file, problem_data->dense_invalidated_by_call);
648
649 for (regno = 0; regno < m; regno++)
3072d30e 650 if (DF_USES_COUNT (regno))
e011eba9 651 fprintf (file, "%d[%d,%d] ", regno,
3072d30e 652 DF_USES_BEGIN (regno),
653 DF_USES_COUNT (regno));
e011eba9 654 fprintf (file, "\n");
e011eba9 655}
656
3072d30e 657
658/* Debugging info at top of bb. */
659
660static void
661df_ru_top_dump (basic_block bb, FILE *file)
662{
663 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
664 if (!bb_info || !bb_info->in)
665 return;
666
667 fprintf (file, ";; ru in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
668 dump_bitmap (file, bb_info->in);
669 fprintf (file, ";; ru gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
670 dump_bitmap (file, bb_info->gen);
671 fprintf (file, ";; ru kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
672 dump_bitmap (file, bb_info->kill);
673}
674
675
676/* Debugging info at bottom of bb. */
677
678static void
679df_ru_bottom_dump (basic_block bb, FILE *file)
680{
681 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
682 if (!bb_info || !bb_info->out)
683 return;
684
685 fprintf (file, ";; ru out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
686 dump_bitmap (file, bb_info->out);
687}
688
689
e011eba9 690/* All of the information associated with every instance of the problem. */
691
692static struct df_problem problem_RU =
693{
694 DF_RU, /* Problem id. */
695 DF_BACKWARD, /* Direction. */
696 df_ru_alloc, /* Allocate the problem specific data. */
f64e6a69 697 NULL, /* Reset global information. */
e011eba9 698 df_ru_free_bb_info, /* Free basic block info. */
699 df_ru_local_compute, /* Local compute function. */
700 df_ru_init_solution, /* Init the solution specific data. */
3072d30e 701 df_worklist_dataflow, /* Worklist solver. */
e011eba9 702 NULL, /* Confluence operator 0. */
703 df_ru_confluence_n, /* Confluence operator n. */
704 df_ru_transfer_function, /* Transfer function. */
705 NULL, /* Finalize function. */
706 df_ru_free, /* Free all of the problem information. */
3072d30e 707 df_ru_free, /* Remove this problem from the stack of dataflow problems. */
708 df_ru_start_dump, /* Debugging. */
709 df_ru_top_dump, /* Debugging start block. */
710 df_ru_bottom_dump, /* Debugging end block. */
711 NULL, /* Incremental solution verify start. */
712 NULL, /* Incremental solution verfiy end. */
3e6933a8 713 NULL, /* Dependent problem. */
3072d30e 714 TV_DF_RU /* Timing variable. */
e011eba9 715};
716
717
718
719/* Create a new DATAFLOW instance and add it to an existing instance
720 of DF. The returned structure is what is used to get at the
721 solution. */
722
3072d30e 723void
724df_ru_add_problem (void)
e011eba9 725{
3072d30e 726 df_add_problem (&problem_RU);
e011eba9 727}
728
729\f
730/*----------------------------------------------------------------------------
731 REACHING DEFINITIONS
732
733 Find the locations in the function where each definition site for a
aa7aac1f 734 pseudo reaches. In and out bitvectors are built for each basic
735 block. The id field in the ref is used to index into these sets.
736 See df.h for details.
737 ----------------------------------------------------------------------------*/
738
739/* See the comment at the top of the Reaching Uses problem for how the
740 uses are represented in the kill sets. The same games are played
741 here for the defs. */
e011eba9 742
aa7aac1f 743/* Private data used to compute the solution for this problem. These
554f2707 744 data structures are not accessible outside of this module. */
e011eba9 745struct df_rd_problem_data
746{
e011eba9 747 /* The set of defs to regs invalidated by call. */
748 bitmap sparse_invalidated_by_call;
aa7aac1f 749 /* The set of defs to regs invalidate by call for rd. */
3072d30e 750 bitmap dense_invalidated_by_call;
751 /* An obstack for the bitmaps we need for this problem. */
752 bitmap_obstack rd_bitmaps;
e011eba9 753};
754
e011eba9 755/* Set basic block info. */
756
757static void
3072d30e 758df_rd_set_bb_info (unsigned int index,
e011eba9 759 struct df_rd_bb_info *bb_info)
760{
3072d30e 761 gcc_assert (df_rd);
762 gcc_assert (index < df_rd->block_info_size);
763 df_rd->block_info[index] = bb_info;
e011eba9 764}
765
766
767/* Free basic block info. */
768
769static void
3072d30e 770df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
d0802b39 771 void *vbb_info)
e011eba9 772{
773 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
774 if (bb_info)
775 {
776 BITMAP_FREE (bb_info->kill);
777 BITMAP_FREE (bb_info->sparse_kill);
778 BITMAP_FREE (bb_info->gen);
779 BITMAP_FREE (bb_info->in);
780 BITMAP_FREE (bb_info->out);
3072d30e 781 pool_free (df_rd->block_pool, bb_info);
e011eba9 782 }
783}
784
785
3072d30e 786/* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
e011eba9 787 not touched unless the block is new. */
788
789static void
3072d30e 790df_rd_alloc (bitmap all_blocks)
e011eba9 791{
792 unsigned int bb_index;
793 bitmap_iterator bi;
3072d30e 794 struct df_rd_problem_data *problem_data;
e011eba9 795
3072d30e 796 if (!df_rd->block_pool)
797 df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
e011eba9 798 sizeof (struct df_rd_bb_info), 50);
799
3072d30e 800 if (df_rd->problem_data)
e011eba9 801 {
3072d30e 802 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
e011eba9 803 bitmap_clear (problem_data->sparse_invalidated_by_call);
804 bitmap_clear (problem_data->dense_invalidated_by_call);
805 }
806 else
807 {
3072d30e 808 problem_data = XNEW (struct df_rd_problem_data);
809 df_rd->problem_data = problem_data;
810
811 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
812 problem_data->sparse_invalidated_by_call
813 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
814 problem_data->dense_invalidated_by_call
815 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
e011eba9 816 }
817
3072d30e 818 df_grow_bb_info (df_rd);
e011eba9 819
3e6933a8 820 /* Because of the clustering of all use sites for the same pseudo,
e011eba9 821 we have to process all of the blocks before doing the
822 analysis. */
823
3e6933a8 824 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
e011eba9 825 {
3072d30e 826 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
e011eba9 827 if (bb_info)
828 {
829 bitmap_clear (bb_info->kill);
830 bitmap_clear (bb_info->sparse_kill);
831 bitmap_clear (bb_info->gen);
832 }
833 else
834 {
3072d30e 835 bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
836 df_rd_set_bb_info (bb_index, bb_info);
837 bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
838 bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
839 bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
840 bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
841 bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
e011eba9 842 }
843 }
844}
845
846
847/* Process a list of DEFs for df_rd_bb_local_compute. */
848
849static void
3072d30e 850df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
851 struct df_ref **def_rec,
fcf2ad9f 852 enum df_ref_flags top_flag)
e011eba9 853{
3072d30e 854 while (*def_rec)
e011eba9 855 {
3072d30e 856 struct df_ref *def = *def_rec;
fcf2ad9f 857 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
e011eba9 858 {
fcf2ad9f 859 unsigned int regno = DF_REF_REGNO (def);
3072d30e 860 unsigned int begin = DF_DEFS_BEGIN (regno);
861 unsigned int n_defs = DF_DEFS_COUNT (regno);
fcf2ad9f 862
3072d30e 863 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
864 || (regno >= FIRST_PSEUDO_REGISTER))
e011eba9 865 {
3072d30e 866 /* Only the last def(s) for a regno in the block has any
867 effect. */
868 if (!bitmap_bit_p (seen_in_block, regno))
e011eba9 869 {
3072d30e 870 /* The first def for regno in insn gets to knock out the
871 defs from other instructions. */
872 if ((!bitmap_bit_p (seen_in_insn, regno))
873 /* If the def is to only part of the reg, it does
874 not kill the other defs that reach here. */
875 && (!(DF_REF_FLAGS (def) &
876 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
fcf2ad9f 877 {
3072d30e 878 if (n_defs > DF_SPARSE_THRESHOLD)
879 {
880 bitmap_set_bit (bb_info->sparse_kill, regno);
881 bitmap_clear_range(bb_info->gen, begin, n_defs);
882 }
883 else
884 {
885 bitmap_set_range (bb_info->kill, begin, n_defs);
886 bitmap_clear_range (bb_info->gen, begin, n_defs);
887 }
fcf2ad9f 888 }
3072d30e 889
890 bitmap_set_bit (seen_in_insn, regno);
891 /* All defs for regno in the instruction may be put into
892 the gen set. */
893 if (!(DF_REF_FLAGS (def)
894 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
895 bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
e011eba9 896 }
897 }
e011eba9 898 }
3072d30e 899 def_rec++;
e011eba9 900 }
901}
902
903/* Compute local reaching def info for basic block BB. */
904
905static void
3072d30e 906df_rd_bb_local_compute (unsigned int bb_index)
e011eba9 907{
e011eba9 908 basic_block bb = BASIC_BLOCK (bb_index);
3072d30e 909 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
e011eba9 910 rtx insn;
911
912 bitmap_clear (seen_in_block);
913 bitmap_clear (seen_in_insn);
914
3072d30e 915 /* Artificials are only hard regs. */
916 if (!(df->changeable_flags & DF_NO_HARD_REGS))
917 df_rd_bb_local_compute_process_def (bb_info,
918 df_get_artificial_defs (bb_index),
919 0);
fcf2ad9f 920
e011eba9 921 FOR_BB_INSNS_REVERSE (bb, insn)
922 {
923 unsigned int uid = INSN_UID (insn);
924
3e6933a8 925 if (!INSN_P (insn))
e011eba9 926 continue;
927
3072d30e 928 df_rd_bb_local_compute_process_def (bb_info,
929 DF_INSN_UID_DEFS (uid), 0);
e011eba9 930
931 /* This complex dance with the two bitmaps is required because
932 instructions can assign twice to the same pseudo. This
933 generally happens with calls that will have one def for the
934 result and another def for the clobber. If only one vector
935 is used and the clobber goes first, the result will be
936 lost. */
937 bitmap_ior_into (seen_in_block, seen_in_insn);
938 bitmap_clear (seen_in_insn);
939 }
940
fcf2ad9f 941 /* Process the artificial defs at the top of the block last since we
942 are going backwards through the block and these are logically at
943 the start. */
3072d30e 944 if (!(df->changeable_flags & DF_NO_HARD_REGS))
945 df_rd_bb_local_compute_process_def (bb_info,
946 df_get_artificial_defs (bb_index),
947 DF_REF_AT_TOP);
e011eba9 948}
949
950
951/* Compute local reaching def info for each basic block within BLOCKS. */
952
953static void
3072d30e 954df_rd_local_compute (bitmap all_blocks)
e011eba9 955{
e011eba9 956 unsigned int bb_index;
957 bitmap_iterator bi;
958 unsigned int regno;
3e6933a8 959 struct df_rd_problem_data *problem_data
3072d30e 960 = (struct df_rd_problem_data *) df_rd->problem_data;
e011eba9 961 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
962 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
963
964 df_set_seen ();
3072d30e 965
966 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
e011eba9 967
968 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
969 {
3072d30e 970 df_rd_bb_local_compute (bb_index);
e011eba9 971 }
972
973 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
974 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
975 {
3072d30e 976 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
977 bitmap_set_bit (sparse_invalidated, regno);
e011eba9 978 else
3072d30e 979 bitmap_set_range (dense_invalidated,
980 DF_DEFS_BEGIN (regno),
981 DF_DEFS_COUNT (regno));
e011eba9 982 }
983 df_unset_seen ();
984}
985
986
987/* Initialize the solution bit vectors for problem. */
988
989static void
3072d30e 990df_rd_init_solution (bitmap all_blocks)
e011eba9 991{
992 unsigned int bb_index;
993 bitmap_iterator bi;
994
995 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
996 {
3072d30e 997 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
e011eba9 998
999 bitmap_copy (bb_info->out, bb_info->gen);
1000 bitmap_clear (bb_info->in);
1001 }
1002}
1003
1004/* In of target gets or of out of source. */
1005
1006static void
3072d30e 1007df_rd_confluence_n (edge e)
e011eba9 1008{
3072d30e 1009 bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
1010 bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
e011eba9 1011
1012 if (e->flags & EDGE_EH)
1013 {
3e6933a8 1014 struct df_rd_problem_data *problem_data
3072d30e 1015 = (struct df_rd_problem_data *) df_rd->problem_data;
e011eba9 1016 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
1017 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
e011eba9 1018 bitmap_iterator bi;
1019 unsigned int regno;
3072d30e 1020 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
716e25d4 1021
1022 bitmap_copy (tmp, op2);
1023 bitmap_and_compl_into (tmp, dense_invalidated);
1024
e011eba9 1025 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
1026 {
716e25d4 1027 bitmap_clear_range (tmp,
3072d30e 1028 DF_DEFS_BEGIN (regno),
1029 DF_DEFS_COUNT (regno));
e011eba9 1030 }
716e25d4 1031 bitmap_ior_into (op1, tmp);
1032 BITMAP_FREE (tmp);
e011eba9 1033 }
1034 else
1035 bitmap_ior_into (op1, op2);
1036}
1037
1038
1039/* Transfer function. */
1040
1041static bool
3072d30e 1042df_rd_transfer_function (int bb_index)
e011eba9 1043{
3072d30e 1044 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
e011eba9 1045 unsigned int regno;
1046 bitmap_iterator bi;
1047 bitmap in = bb_info->in;
1048 bitmap out = bb_info->out;
1049 bitmap gen = bb_info->gen;
1050 bitmap kill = bb_info->kill;
1051 bitmap sparse_kill = bb_info->sparse_kill;
1052
1053 if (bitmap_empty_p (sparse_kill))
1054 return bitmap_ior_and_compl (out, gen, in, kill);
1055 else
1056 {
3072d30e 1057 struct df_rd_problem_data *problem_data;
e011eba9 1058 bool changed = false;
3072d30e 1059 bitmap tmp;
1060
1061 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
1062 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
1063 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
1064 tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
1065
e011eba9 1066 bitmap_copy (tmp, in);
1067 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
1068 {
1069 bitmap_clear_range (tmp,
3072d30e 1070 DF_DEFS_BEGIN (regno),
1071 DF_DEFS_COUNT (regno));
e011eba9 1072 }
1073 bitmap_and_compl_into (tmp, kill);
1074 bitmap_ior_into (tmp, gen);
1075 changed = !bitmap_equal_p (tmp, out);
1076 if (changed)
1077 {
1078 BITMAP_FREE (out);
1079 bb_info->out = tmp;
1080 }
1081 else
1082 BITMAP_FREE (tmp);
1083 return changed;
1084 }
1085}
1086
1087
1088/* Free all storage associated with the problem. */
1089
1090static void
3072d30e 1091df_rd_free (void)
e011eba9 1092{
1093 unsigned int i;
3e6933a8 1094 struct df_rd_problem_data *problem_data
3072d30e 1095 = (struct df_rd_problem_data *) df_rd->problem_data;
e011eba9 1096
d0802b39 1097 if (problem_data)
e011eba9 1098 {
3072d30e 1099 for (i = 0; i < df_rd->block_info_size; i++)
e011eba9 1100 {
3072d30e 1101 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i);
d0802b39 1102 if (bb_info)
1103 {
1104 BITMAP_FREE (bb_info->kill);
1105 BITMAP_FREE (bb_info->sparse_kill);
1106 BITMAP_FREE (bb_info->gen);
1107 BITMAP_FREE (bb_info->in);
1108 BITMAP_FREE (bb_info->out);
1109 }
e011eba9 1110 }
d0802b39 1111
3072d30e 1112 free_alloc_pool (df_rd->block_pool);
d0802b39 1113 BITMAP_FREE (problem_data->sparse_invalidated_by_call);
1114 BITMAP_FREE (problem_data->dense_invalidated_by_call);
3072d30e 1115 bitmap_obstack_release (&problem_data->rd_bitmaps);
d0802b39 1116
3072d30e 1117 df_rd->block_info_size = 0;
1118 free (df_rd->block_info);
1119 free (df_rd->problem_data);
e011eba9 1120 }
3072d30e 1121 free (df_rd);
e011eba9 1122}
1123
1124
1125/* Debugging info. */
1126
1127static void
3072d30e 1128df_rd_start_dump (FILE *file)
e011eba9 1129{
3e6933a8 1130 struct df_rd_problem_data *problem_data
3072d30e 1131 = (struct df_rd_problem_data *) df_rd->problem_data;
1132 unsigned int m = DF_REG_SIZE(df);
e011eba9 1133 unsigned int regno;
1134
3072d30e 1135 if (!df_rd->block_info)
3e6933a8 1136 return;
1137
3072d30e 1138 fprintf (file, ";; Reaching defs:\n\n");
e011eba9 1139
1140 fprintf (file, " sparse invalidated \t");
1141 dump_bitmap (file, problem_data->sparse_invalidated_by_call);
1142 fprintf (file, " dense invalidated \t");
1143 dump_bitmap (file, problem_data->dense_invalidated_by_call);
1144
1145 for (regno = 0; regno < m; regno++)
3072d30e 1146 if (DF_DEFS_COUNT (regno))
e011eba9 1147 fprintf (file, "%d[%d,%d] ", regno,
3072d30e 1148 DF_DEFS_BEGIN (regno),
1149 DF_DEFS_COUNT (regno));
e011eba9 1150 fprintf (file, "\n");
1151
3072d30e 1152}
1153
1154
1155/* Debugging info at top of bb. */
1156
1157static void
1158df_rd_top_dump (basic_block bb, FILE *file)
1159{
1160 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
1161 if (!bb_info || !bb_info->in)
1162 return;
1163
1164 fprintf (file, ";; rd in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
1165 dump_bitmap (file, bb_info->in);
1166 fprintf (file, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
1167 dump_bitmap (file, bb_info->gen);
1168 fprintf (file, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
1169 dump_bitmap (file, bb_info->kill);
1170}
1171
1172
1173/* Debugging info at top of bb. */
1174
1175static void
1176df_rd_bottom_dump (basic_block bb, FILE *file)
1177{
1178 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
1179 if (!bb_info || !bb_info->out)
1180 return;
1181
1182 fprintf (file, ";; rd out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
1183 dump_bitmap (file, bb_info->out);
e011eba9 1184}
1185
1186/* All of the information associated with every instance of the problem. */
1187
1188static struct df_problem problem_RD =
1189{
1190 DF_RD, /* Problem id. */
1191 DF_FORWARD, /* Direction. */
1192 df_rd_alloc, /* Allocate the problem specific data. */
f64e6a69 1193 NULL, /* Reset global information. */
e011eba9 1194 df_rd_free_bb_info, /* Free basic block info. */
1195 df_rd_local_compute, /* Local compute function. */
1196 df_rd_init_solution, /* Init the solution specific data. */
3072d30e 1197 df_worklist_dataflow, /* Worklist solver. */
e011eba9 1198 NULL, /* Confluence operator 0. */
1199 df_rd_confluence_n, /* Confluence operator n. */
1200 df_rd_transfer_function, /* Transfer function. */
1201 NULL, /* Finalize function. */
1202 df_rd_free, /* Free all of the problem information. */
3072d30e 1203 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
1204 df_rd_start_dump, /* Debugging. */
1205 df_rd_top_dump, /* Debugging start block. */
1206 df_rd_bottom_dump, /* Debugging end block. */
1207 NULL, /* Incremental solution verify start. */
1208 NULL, /* Incremental solution verfiy end. */
3e6933a8 1209 NULL, /* Dependent problem. */
3072d30e 1210 TV_DF_RD /* Timing variable. */
e011eba9 1211};
1212
1213
1214
1215/* Create a new DATAFLOW instance and add it to an existing instance
1216 of DF. The returned structure is what is used to get at the
1217 solution. */
1218
3072d30e 1219void
1220df_rd_add_problem (void)
e011eba9 1221{
3072d30e 1222 df_add_problem (&problem_RD);
e011eba9 1223}
1224
1225
1226\f
1227/*----------------------------------------------------------------------------
1228 LIVE REGISTERS
1229
aa7aac1f 1230 Find the locations in the function where any use of a pseudo can
1231 reach in the backwards direction. In and out bitvectors are built
1232 for each basic block. The regnum is used to index into these sets.
1233 See df.h for details.
1234 ----------------------------------------------------------------------------*/
e011eba9 1235
3072d30e 1236/* Private data used to verify the solution for this problem. */
1237struct df_lr_problem_data
e011eba9 1238{
3072d30e 1239 bitmap *in;
1240 bitmap *out;
1241};
e011eba9 1242
1243
1244/* Set basic block info. */
1245
1246static void
3072d30e 1247df_lr_set_bb_info (unsigned int index,
e011eba9 1248 struct df_lr_bb_info *bb_info)
1249{
3072d30e 1250 gcc_assert (df_lr);
1251 gcc_assert (index < df_lr->block_info_size);
1252 df_lr->block_info[index] = bb_info;
e011eba9 1253}
1254
1255
1256/* Free basic block info. */
1257
1258static void
3072d30e 1259df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
d0802b39 1260 void *vbb_info)
e011eba9 1261{
1262 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
1263 if (bb_info)
1264 {
1265 BITMAP_FREE (bb_info->use);
1266 BITMAP_FREE (bb_info->def);
3072d30e 1267 if (bb_info->in == bb_info->top)
1268 bb_info->top = NULL;
1269 else
1270 {
1271 BITMAP_FREE (bb_info->top);
1272 BITMAP_FREE (bb_info->ause);
1273 BITMAP_FREE (bb_info->adef);
1274 }
e011eba9 1275 BITMAP_FREE (bb_info->in);
1276 BITMAP_FREE (bb_info->out);
3072d30e 1277 pool_free (df_lr->block_pool, bb_info);
e011eba9 1278 }
1279}
1280
1281
3072d30e 1282/* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
e011eba9 1283 not touched unless the block is new. */
1284
1285static void
3072d30e 1286df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
e011eba9 1287{
1288 unsigned int bb_index;
1289 bitmap_iterator bi;
1290
3072d30e 1291 if (!df_lr->block_pool)
1292 df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
e011eba9 1293 sizeof (struct df_lr_bb_info), 50);
1294
3072d30e 1295 df_grow_bb_info (df_lr);
e011eba9 1296
3072d30e 1297 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
e011eba9 1298 {
3072d30e 1299 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
e011eba9 1300 if (bb_info)
1301 {
1302 bitmap_clear (bb_info->def);
1303 bitmap_clear (bb_info->use);
3072d30e 1304 if (bb_info->adef)
1305 {
1306 bitmap_clear (bb_info->adef);
1307 bitmap_clear (bb_info->ause);
1308 }
e011eba9 1309 }
1310 else
1311 {
3072d30e 1312 bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
1313 df_lr_set_bb_info (bb_index, bb_info);
e011eba9 1314 bb_info->use = BITMAP_ALLOC (NULL);
1315 bb_info->def = BITMAP_ALLOC (NULL);
1316 bb_info->in = BITMAP_ALLOC (NULL);
1317 bb_info->out = BITMAP_ALLOC (NULL);
3072d30e 1318 bb_info->top = bb_info->in;
1319 bb_info->adef = NULL;
1320 bb_info->ause = NULL;
e011eba9 1321 }
1322 }
1323}
1324
1325
3072d30e 1326/* Reset the global solution for recalculation. */
1327
1328static void
1329df_lr_reset (bitmap all_blocks)
1330{
1331 unsigned int bb_index;
1332 bitmap_iterator bi;
1333
1334 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1335 {
1336 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1337 gcc_assert (bb_info);
1338 bitmap_clear (bb_info->in);
1339 bitmap_clear (bb_info->out);
1340 bitmap_clear (bb_info->top);
1341 }
1342}
1343
1344
e011eba9 1345/* Compute local live register info for basic block BB. */
1346
1347static void
3072d30e 1348df_lr_bb_local_compute (unsigned int bb_index)
e011eba9 1349{
1350 basic_block bb = BASIC_BLOCK (bb_index);
3072d30e 1351 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
e011eba9 1352 rtx insn;
3072d30e 1353 struct df_ref **def_rec;
1354 struct df_ref **use_rec;
e011eba9 1355
fcf2ad9f 1356 /* Process the registers set in an exception handler. */
3072d30e 1357 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1358 {
1359 struct df_ref *def = *def_rec;
1360 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
1361 {
1362 unsigned int dregno = DF_REF_REGNO (def);
1363 bitmap_set_bit (bb_info->def, dregno);
1364 bitmap_clear_bit (bb_info->use, dregno);
1365 }
1366 }
fcf2ad9f 1367
e011eba9 1368 /* Process the hardware registers that are always live. */
3072d30e 1369 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
1370 {
1371 struct df_ref *use = *use_rec;
1372 /* Add use to set of uses in this BB. */
1373 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
1374 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
1375 }
e011eba9 1376
1377 FOR_BB_INSNS_REVERSE (bb, insn)
1378 {
1379 unsigned int uid = INSN_UID (insn);
1380
3e6933a8 1381 if (!INSN_P (insn))
e011eba9 1382 continue;
1383
1384 if (CALL_P (insn))
1385 {
3072d30e 1386 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
e011eba9 1387 {
3072d30e 1388 struct df_ref *def = *def_rec;
e011eba9 1389 unsigned int dregno = DF_REF_REGNO (def);
1390
3072d30e 1391 if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
e011eba9 1392 {
3072d30e 1393 if (dregno >= FIRST_PSEUDO_REGISTER
1394 || !(SIBLING_CALL_P (insn)
1395 && bitmap_bit_p (df->exit_block_uses, dregno)
1396 && !refers_to_regno_p (dregno, dregno+1,
1397 current_function_return_rtx,
1398 (rtx *)0)))
3e6933a8 1399 {
3072d30e 1400 /* If the def is to only part of the reg, it does
1401 not kill the other defs that reach here. */
1402 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
1403 {
1404 bitmap_set_bit (bb_info->def, dregno);
1405 bitmap_clear_bit (bb_info->use, dregno);
1406 }
3e6933a8 1407 }
e011eba9 1408 }
3072d30e 1409 else
1410 /* This is the return value. */
1411 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
1412 {
1413 bitmap_set_bit (bb_info->def, dregno);
1414 bitmap_clear_bit (bb_info->use, dregno);
1415 }
e011eba9 1416 }
1417 }
1418 else
1419 {
3072d30e 1420 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
e011eba9 1421 {
3072d30e 1422 struct df_ref *def = *def_rec;
3e6933a8 1423 /* If the def is to only part of the reg, it does
1424 not kill the other defs that reach here. */
3072d30e 1425 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3e6933a8 1426 {
3072d30e 1427 unsigned int dregno = DF_REF_REGNO (def);
3e6933a8 1428 bitmap_set_bit (bb_info->def, dregno);
1429 bitmap_clear_bit (bb_info->use, dregno);
1430 }
e011eba9 1431 }
1432 }
1433
3072d30e 1434 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1435 {
1436 struct df_ref *use = *use_rec;
1437 /* Add use to set of uses in this BB. */
1438 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
1439 }
e011eba9 1440 }
e011eba9 1441 /* Process the registers set in an exception handler. */
3072d30e 1442 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1443 {
1444 struct df_ref *def = *def_rec;
1445 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1446 && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
1447 {
1448 unsigned int dregno = DF_REF_REGNO (def);
1449 if (bb_info->adef == NULL)
1450 {
1451 gcc_assert (bb_info->ause == NULL);
1452 gcc_assert (bb_info->top == bb_info->in);
1453 bb_info->adef = BITMAP_ALLOC (NULL);
1454 bb_info->ause = BITMAP_ALLOC (NULL);
1455 bb_info->top = BITMAP_ALLOC (NULL);
1456 }
1457 bitmap_set_bit (bb_info->adef, dregno);
1458 }
1459 }
fcf2ad9f 1460
e011eba9 1461#ifdef EH_USES
1462 /* Process the uses that are live into an exception handler. */
3072d30e 1463 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
1464 {
1465 struct df_ref *use = *use_rec;
1466 /* Add use to set of uses in this BB. */
1467 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
1468 {
1469 if (bb_info->adef == NULL)
1470 {
1471 gcc_assert (bb_info->ause == NULL);
1472 gcc_assert (bb_info->top == bb_info->in);
1473 bb_info->adef = BITMAP_ALLOC (NULL);
1474 bb_info->ause = BITMAP_ALLOC (NULL);
1475 bb_info->top = BITMAP_ALLOC (NULL);
1476 }
1477 bitmap_set_bit (bb_info->ause, DF_REF_REGNO (use));
1478 }
1479 }
e011eba9 1480#endif
1481}
1482
3e6933a8 1483
e011eba9 1484/* Compute local live register info for each basic block within BLOCKS. */
1485
1486static void
3072d30e 1487df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
e011eba9 1488{
e011eba9 1489 unsigned int bb_index;
1490 bitmap_iterator bi;
1491
e011eba9 1492 bitmap_clear (df->hardware_regs_used);
1493
1494 /* The all-important stack pointer must always be live. */
1495 bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
1496
1497 /* Before reload, there are a few registers that must be forced
1498 live everywhere -- which might not already be the case for
1499 blocks within infinite loops. */
3e6933a8 1500 if (!reload_completed)
e011eba9 1501 {
1502 /* Any reference to any pseudo before reload is a potential
1503 reference of the frame pointer. */
1504 bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
1505
1506#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1507 /* Pseudos with argument area equivalences may require
1508 reloading via the argument pointer. */
1509 if (fixed_regs[ARG_POINTER_REGNUM])
1510 bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
1511#endif
1512
1513 /* Any constant, or pseudo with constant equivalences, may
1514 require reloading from memory using the pic register. */
1515 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
1516 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
1517 bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
1518 }
1519
3072d30e 1520 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
e011eba9 1521 {
1522 if (bb_index == EXIT_BLOCK)
3072d30e 1523 {
1524 /* The exit block is special for this problem and its bits are
1525 computed from thin air. */
1526 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
1527 bitmap_copy (bb_info->use, df->exit_block_uses);
1528 }
1529 else
1530 df_lr_bb_local_compute (bb_index);
e011eba9 1531 }
3072d30e 1532
1533 bitmap_clear (df_lr->out_of_date_transfer_functions);
e011eba9 1534}
1535
1536
1537/* Initialize the solution vectors. */
1538
1539static void
3072d30e 1540df_lr_init (bitmap all_blocks)
e011eba9 1541{
1542 unsigned int bb_index;
1543 bitmap_iterator bi;
1544
1545 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1546 {
3072d30e 1547 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
e011eba9 1548 bitmap_copy (bb_info->in, bb_info->use);
1549 bitmap_clear (bb_info->out);
1550 }
1551}
1552
1553
1554/* Confluence function that processes infinite loops. This might be a
1555 noreturn function that throws. And even if it isn't, getting the
1556 unwind info right helps debugging. */
1557static void
3072d30e 1558df_lr_confluence_0 (basic_block bb)
e011eba9 1559{
3072d30e 1560 bitmap op1 = df_lr_get_bb_info (bb->index)->out;
e011eba9 1561 if (bb != EXIT_BLOCK_PTR)
1562 bitmap_copy (op1, df->hardware_regs_used);
1563}
1564
1565
1566/* Confluence function that ignores fake edges. */
3e6933a8 1567
e011eba9 1568static void
3072d30e 1569df_lr_confluence_n (edge e)
e011eba9 1570{
3072d30e 1571 bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
1572 bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
e011eba9 1573
1574 /* Call-clobbered registers die across exception and call edges. */
1575 /* ??? Abnormal call edges ignored for the moment, as this gets
1576 confused by sibling call edges, which crashes reg-stack. */
1577 if (e->flags & EDGE_EH)
1578 bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
1579 else
1580 bitmap_ior_into (op1, op2);
1581
3072d30e 1582 bitmap_ior_into (op1, df->hardware_regs_used);
e011eba9 1583}
1584
1585
1586/* Transfer function. */
3e6933a8 1587
e011eba9 1588static bool
3072d30e 1589df_lr_transfer_function (int bb_index)
e011eba9 1590{
3072d30e 1591 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
e011eba9 1592 bitmap in = bb_info->in;
1593 bitmap out = bb_info->out;
1594 bitmap use = bb_info->use;
1595 bitmap def = bb_info->def;
3072d30e 1596 bitmap top = bb_info->top;
1597 bitmap ause = bb_info->ause;
1598 bitmap adef = bb_info->adef;
1599 bool changed;
1600
1601 changed = bitmap_ior_and_compl (top, use, out, def);
1602 if (in != top)
1603 {
1604 gcc_assert (ause && adef);
1605 changed |= bitmap_ior_and_compl (in, ause, top, adef);
1606 }
1607
1608 return changed;
1609}
1610
e011eba9 1611
3072d30e 1612/* Run the fast dce as a side effect of building LR. */
1613
1614static void
1615df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1616{
1617 if (df->changeable_flags & DF_LR_RUN_DCE)
1618 {
1619 run_fast_df_dce ();
1620 if (df_lr->problem_data && df_lr->solutions_dirty)
1621 {
1622 /* If we are here, then it is because we are both verifying
1623 the solution and the dce changed the function. In that case
1624 the verification info built will be wrong. So we leave the
1625 dirty flag true so that the verifier will skip the checking
1626 part and just clean up.*/
1627 df_lr->solutions_dirty = true;
1628 }
1629 else
1630 df_lr->solutions_dirty = false;
1631 }
1632 else
1633 df_lr->solutions_dirty = false;
e011eba9 1634}
1635
1636
1637/* Free all storage associated with the problem. */
1638
1639static void
3072d30e 1640df_lr_free (void)
e011eba9 1641{
3072d30e 1642 if (df_lr->block_info)
e011eba9 1643 {
d0802b39 1644 unsigned int i;
3072d30e 1645 for (i = 0; i < df_lr->block_info_size; i++)
e011eba9 1646 {
3072d30e 1647 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
d0802b39 1648 if (bb_info)
1649 {
1650 BITMAP_FREE (bb_info->use);
1651 BITMAP_FREE (bb_info->def);
3072d30e 1652 if (bb_info->in == bb_info->top)
1653 bb_info->top = NULL;
1654 else
1655 {
1656 BITMAP_FREE (bb_info->top);
1657 BITMAP_FREE (bb_info->ause);
1658 BITMAP_FREE (bb_info->adef);
1659 }
d0802b39 1660 BITMAP_FREE (bb_info->in);
1661 BITMAP_FREE (bb_info->out);
1662 }
e011eba9 1663 }
3072d30e 1664 free_alloc_pool (df_lr->block_pool);
d0802b39 1665
3072d30e 1666 df_lr->block_info_size = 0;
1667 free (df_lr->block_info);
e011eba9 1668 }
3e6933a8 1669
3072d30e 1670 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1671 free (df_lr);
e011eba9 1672}
1673
1674
3072d30e 1675/* Debugging info at top of bb. */
e011eba9 1676
1677static void
3072d30e 1678df_lr_top_dump (basic_block bb, FILE *file)
e011eba9 1679{
3072d30e 1680 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1681 struct df_lr_problem_data *problem_data;
1682 if (!bb_info || !bb_info->in)
1683 return;
1684
1685 fprintf (file, ";; lr in \t");
1686 df_print_regset (file, bb_info->in);
1687 if (df_lr->problem_data)
1688 {
1689 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1690 fprintf (file, ";; old in \t");
1691 df_print_regset (file, problem_data->in[bb->index]);
1692 }
1693 fprintf (file, ";; lr use \t");
1694 df_print_regset (file, bb_info->use);
1695 fprintf (file, ";; lr def \t");
1696 df_print_regset (file, bb_info->def);
1697}
1698
1699
1700/* Debugging info at bottom of bb. */
1701
1702static void
1703df_lr_bottom_dump (basic_block bb, FILE *file)
1704{
1705 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1706 struct df_lr_problem_data *problem_data;
1707 if (!bb_info || !bb_info->out)
1708 return;
e011eba9 1709
3072d30e 1710 fprintf (file, ";; lr out \t");
1711 df_print_regset (file, bb_info->out);
1712 if (df_lr->problem_data)
1713 {
1714 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1715 fprintf (file, ";; old out \t");
1716 df_print_regset (file, problem_data->out[bb->index]);
1717 }
1718}
1719
1720
1721/* Build the datastructure to verify that the solution to the dataflow
1722 equations is not dirty. */
1723
1724static void
1725df_lr_verify_solution_start (void)
1726{
1727 basic_block bb;
1728 struct df_lr_problem_data *problem_data;
1729 if (df_lr->solutions_dirty)
1730 {
1731 df_lr->problem_data = NULL;
1732 return;
1733 }
1734
1735 /* Set it true so that the solution is recomputed. */
1736 df_lr->solutions_dirty = true;
1737
1738 problem_data = XNEW (struct df_lr_problem_data);
1739 df_lr->problem_data = problem_data;
1740 problem_data->in = XNEWVEC (bitmap, last_basic_block);
1741 problem_data->out = XNEWVEC (bitmap, last_basic_block);
1742
1743 FOR_ALL_BB (bb)
1744 {
1745 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1746 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1747 bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1748 bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1749 }
1750}
1751
1752
1753/* Compare the saved datastructure and the new solution to the dataflow
1754 equations. */
1755
1756static void
1757df_lr_verify_solution_end (void)
1758{
1759 struct df_lr_problem_data *problem_data;
1760 basic_block bb;
1761
1762 if (df_lr->problem_data == NULL)
3e6933a8 1763 return;
1764
3072d30e 1765 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1766
1767 if (df_lr->solutions_dirty)
1768 /* Do not check if the solution is still dirty. See the comment
1769 in df_lr_local_finalize for details. */
1770 df_lr->solutions_dirty = false;
1771 else
1772 FOR_ALL_BB (bb)
1773 {
1774 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1775 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1776 {
1777 /*df_dump (stderr);*/
1778 gcc_unreachable ();
1779 }
1780 }
1781
1782 /* Cannot delete them immediately because you may want to dump them
1783 if the comparison fails. */
e011eba9 1784 FOR_ALL_BB (bb)
1785 {
3072d30e 1786 BITMAP_FREE (problem_data->in[bb->index]);
1787 BITMAP_FREE (problem_data->out[bb->index]);
e011eba9 1788 }
3072d30e 1789
1790 free (problem_data->in);
1791 free (problem_data->out);
1792 free (problem_data);
1793 df_lr->problem_data = NULL;
e011eba9 1794}
1795
3072d30e 1796
e011eba9 1797/* All of the information associated with every instance of the problem. */
1798
1799static struct df_problem problem_LR =
1800{
1801 DF_LR, /* Problem id. */
1802 DF_BACKWARD, /* Direction. */
1803 df_lr_alloc, /* Allocate the problem specific data. */
3072d30e 1804 df_lr_reset, /* Reset global information. */
e011eba9 1805 df_lr_free_bb_info, /* Free basic block info. */
1806 df_lr_local_compute, /* Local compute function. */
1807 df_lr_init, /* Init the solution specific data. */
3072d30e 1808 df_worklist_dataflow, /* Worklist solver. */
e011eba9 1809 df_lr_confluence_0, /* Confluence operator 0. */
1810 df_lr_confluence_n, /* Confluence operator n. */
1811 df_lr_transfer_function, /* Transfer function. */
3072d30e 1812 df_lr_local_finalize, /* Finalize function. */
e011eba9 1813 df_lr_free, /* Free all of the problem information. */
3072d30e 1814 NULL, /* Remove this problem from the stack of dataflow problems. */
1815 NULL, /* Debugging. */
1816 df_lr_top_dump, /* Debugging start block. */
1817 df_lr_bottom_dump, /* Debugging end block. */
1818 df_lr_verify_solution_start,/* Incremental solution verify start. */
1819 df_lr_verify_solution_end, /* Incremental solution verify end. */
3e6933a8 1820 NULL, /* Dependent problem. */
3072d30e 1821 TV_DF_LR /* Timing variable. */
e011eba9 1822};
1823
1824
1825/* Create a new DATAFLOW instance and add it to an existing instance
1826 of DF. The returned structure is what is used to get at the
1827 solution. */
1828
3072d30e 1829void
1830df_lr_add_problem (void)
1831{
1832 df_add_problem (&problem_LR);
1833 /* These will be initialized when df_scan_blocks processes each
1834 block. */
1835 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1836}
1837
1838
1839/* Verify that all of the lr related info is consistent and
1840 correct. */
1841
1842void
1843df_lr_verify_transfer_functions (void)
e011eba9 1844{
3072d30e 1845 basic_block bb;
1846 bitmap saved_def;
1847 bitmap saved_use;
1848 bitmap saved_adef;
1849 bitmap saved_ause;
1850 bitmap all_blocks;
1851 bool need_as;
1852
1853 if (!df)
1854 return;
1855
1856 saved_def = BITMAP_ALLOC (NULL);
1857 saved_use = BITMAP_ALLOC (NULL);
1858 saved_adef = BITMAP_ALLOC (NULL);
1859 saved_ause = BITMAP_ALLOC (NULL);
1860 all_blocks = BITMAP_ALLOC (NULL);
1861
1862 FOR_ALL_BB (bb)
1863 {
1864 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1865 bitmap_set_bit (all_blocks, bb->index);
1866
1867 if (bb_info)
1868 {
1869 /* Make a copy of the transfer functions and then compute
1870 new ones to see if the transfer functions have
1871 changed. */
1872 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1873 bb->index))
1874 {
1875 bitmap_copy (saved_def, bb_info->def);
1876 bitmap_copy (saved_use, bb_info->use);
1877 bitmap_clear (bb_info->def);
1878 bitmap_clear (bb_info->use);
1879
1880 if (bb_info->adef)
1881 {
1882 need_as = true;
1883 bitmap_copy (saved_adef, bb_info->adef);
1884 bitmap_copy (saved_ause, bb_info->ause);
1885 bitmap_clear (bb_info->adef);
1886 bitmap_clear (bb_info->ause);
1887 }
1888 else
1889 need_as = false;
1890
1891 df_lr_bb_local_compute (bb->index);
1892 gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1893 gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1894
1895 if (need_as)
1896 {
1897 gcc_assert (bb_info->adef);
1898 gcc_assert (bb_info->ause);
1899 gcc_assert (bitmap_equal_p (saved_adef, bb_info->adef));
1900 gcc_assert (bitmap_equal_p (saved_ause, bb_info->ause));
1901 }
1902 else
1903 {
1904 gcc_assert (!bb_info->adef);
1905 gcc_assert (!bb_info->ause);
1906 }
1907 }
1908 }
1909 else
1910 {
1911 /* If we do not have basic block info, the block must be in
1912 the list of dirty blocks or else some one has added a
1913 block behind our backs. */
1914 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1915 bb->index));
1916 }
1917 /* Make sure no one created a block without following
1918 procedures. */
1919 gcc_assert (df_scan_get_bb_info (bb->index));
1920 }
1921
1922 /* Make sure there are no dirty bits in blocks that have been deleted. */
1923 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1924 all_blocks));
1925
1926 BITMAP_FREE (saved_def);
1927 BITMAP_FREE (saved_use);
1928 BITMAP_FREE (saved_adef);
1929 BITMAP_FREE (saved_ause);
1930 BITMAP_FREE (all_blocks);
e011eba9 1931}
1932
1933
1934\f
1935/*----------------------------------------------------------------------------
3072d30e 1936 COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
e011eba9 1937
3072d30e 1938 First find the set of uses for registers that are reachable from
1939 the entry block without passing thru a definition. In and out
1940 bitvectors are built for each basic block. The regnum is used to
1941 index into these sets. See df.h for details.
e011eba9 1942
3072d30e 1943 Then the in and out sets here are the anded results of the in and
1944 out sets from the lr and ur
1945 problems.
1946----------------------------------------------------------------------------*/
e011eba9 1947
3072d30e 1948/* Private data used to verify the solution for this problem. */
1949struct df_live_problem_data
e011eba9 1950{
3072d30e 1951 bitmap *in;
1952 bitmap *out;
1953};
e011eba9 1954
1955
1956/* Set basic block info. */
1957
1958static void
3072d30e 1959df_live_set_bb_info (unsigned int index,
1960 struct df_live_bb_info *bb_info)
e011eba9 1961{
3072d30e 1962 gcc_assert (df_live);
1963 gcc_assert (index < df_live->block_info_size);
1964 df_live->block_info[index] = bb_info;
e011eba9 1965}
1966
1967
1968/* Free basic block info. */
1969
1970static void
3072d30e 1971df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
d0802b39 1972 void *vbb_info)
e011eba9 1973{
3072d30e 1974 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
e011eba9 1975 if (bb_info)
1976 {
1977 BITMAP_FREE (bb_info->gen);
1978 BITMAP_FREE (bb_info->kill);
1979 BITMAP_FREE (bb_info->in);
1980 BITMAP_FREE (bb_info->out);
3072d30e 1981 pool_free (df_live->block_pool, bb_info);
e011eba9 1982 }
1983}
1984
1985
3072d30e 1986/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
e011eba9 1987 not touched unless the block is new. */
1988
1989static void
3072d30e 1990df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
e011eba9 1991{
1992 unsigned int bb_index;
1993 bitmap_iterator bi;
1994
3072d30e 1995 if (!df_live->block_pool)
1996 df_live->block_pool = create_alloc_pool ("df_live_block pool",
1997 sizeof (struct df_live_bb_info), 100);
e011eba9 1998
3072d30e 1999 df_grow_bb_info (df_live);
e011eba9 2000
3072d30e 2001 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
e011eba9 2002 {
3072d30e 2003 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
e011eba9 2004 if (bb_info)
2005 {
2006 bitmap_clear (bb_info->kill);
2007 bitmap_clear (bb_info->gen);
2008 }
2009 else
2010 {
3072d30e 2011 bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
2012 df_live_set_bb_info (bb_index, bb_info);
e011eba9 2013 bb_info->kill = BITMAP_ALLOC (NULL);
2014 bb_info->gen = BITMAP_ALLOC (NULL);
2015 bb_info->in = BITMAP_ALLOC (NULL);
2016 bb_info->out = BITMAP_ALLOC (NULL);
2017 }
2018 }
2019}
2020
2021
3072d30e 2022/* Reset the global solution for recalculation. */
2023
2024static void
2025df_live_reset (bitmap all_blocks)
2026{
2027 unsigned int bb_index;
2028 bitmap_iterator bi;
2029
2030 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2031 {
2032 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
2033 gcc_assert (bb_info);
2034 bitmap_clear (bb_info->in);
2035 bitmap_clear (bb_info->out);
2036 }
2037}
2038
2039
e011eba9 2040/* Compute local uninitialized register info for basic block BB. */
2041
2042static void
3072d30e 2043df_live_bb_local_compute (unsigned int bb_index)
e011eba9 2044{
e011eba9 2045 basic_block bb = BASIC_BLOCK (bb_index);
3072d30e 2046 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
e011eba9 2047 rtx insn;
3072d30e 2048 struct df_ref **def_rec;
2049 int luid = 0;
e011eba9 2050
3072d30e 2051 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2052 {
2053 struct df_ref *def = *def_rec;
2054 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2055 bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
2056 }
fcf2ad9f 2057
3072d30e 2058 FOR_BB_INSNS (bb, insn)
e011eba9 2059 {
2060 unsigned int uid = INSN_UID (insn);
3072d30e 2061 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
2062
2063 /* Inserting labels does not always trigger the incremental
2064 rescanning. */
2065 if (!insn_info)
2066 {
2067 gcc_assert (!INSN_P (insn));
2068 df_insn_create_insn_record (insn);
2069 }
2070
2071 DF_INSN_LUID (insn) = luid;
e011eba9 2072 if (!INSN_P (insn))
2073 continue;
2074
3072d30e 2075 luid++;
2076 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
e011eba9 2077 {
3072d30e 2078 struct df_ref *def = *def_rec;
e011eba9 2079 unsigned int regno = DF_REF_REGNO (def);
3072d30e 2080
2081 if (DF_REF_FLAGS_IS_SET (def,
2082 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2083 /* All partial or conditional def
2084 seen are included in the gen set. */
2085 bitmap_set_bit (bb_info->gen, regno);
2086 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
2087 /* Only must clobbers for the entire reg destroy the
2088 value. */
2089 bitmap_set_bit (bb_info->kill, regno);
2090 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2091 bitmap_set_bit (bb_info->gen, regno);
e011eba9 2092 }
e011eba9 2093 }
2094
3072d30e 2095 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2096 {
2097 struct df_ref *def = *def_rec;
2098 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2099 bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
2100 }
e011eba9 2101}
2102
2103
2104/* Compute local uninitialized register info. */
2105
2106static void
3072d30e 2107df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
e011eba9 2108{
2109 unsigned int bb_index;
2110 bitmap_iterator bi;
2111
3072d30e 2112 df_grow_insn_info ();
e011eba9 2113
3072d30e 2114 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
2115 0, bb_index, bi)
e011eba9 2116 {
3072d30e 2117 df_live_bb_local_compute (bb_index);
e011eba9 2118 }
2119
3072d30e 2120 bitmap_clear (df_live->out_of_date_transfer_functions);
e011eba9 2121}
2122
2123
2124/* Initialize the solution vectors. */
2125
2126static void
3072d30e 2127df_live_init (bitmap all_blocks)
e011eba9 2128{
2129 unsigned int bb_index;
2130 bitmap_iterator bi;
2131
2132 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2133 {
3072d30e 2134 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
e011eba9 2135
2136 bitmap_copy (bb_info->out, bb_info->gen);
2137 bitmap_clear (bb_info->in);
2138 }
2139}
2140
e011eba9 2141/* Confluence function that ignores fake edges. */
2142
2143static void
3072d30e 2144df_live_confluence_n (edge e)
e011eba9 2145{
3072d30e 2146 bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
2147 bitmap op2 = df_live_get_bb_info (e->src->index)->out;
e011eba9 2148
2149 if (e->flags & EDGE_FAKE)
2150 return;
2151
2152 bitmap_ior_into (op1, op2);
2153}
2154
2155
2156/* Transfer function. */
2157
2158static bool
3072d30e 2159df_live_transfer_function (int bb_index)
e011eba9 2160{
3072d30e 2161 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
e011eba9 2162 bitmap in = bb_info->in;
2163 bitmap out = bb_info->out;
2164 bitmap gen = bb_info->gen;
2165 bitmap kill = bb_info->kill;
2166
2167 return bitmap_ior_and_compl (out, gen, in, kill);
2168}
2169
2170
3072d30e 2171/* And the LR and UR info to produce the LIVE info. */
2172
2173static void
2174df_live_local_finalize (bitmap all_blocks)
2175{
2176
2177 if (df_live->solutions_dirty)
2178 {
2179 bitmap_iterator bi;
2180 unsigned int bb_index;
2181
2182 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2183 {
2184 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
2185 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
2186
2187 /* No register may reach a location where it is not used. Thus
2188 we trim the rr result to the places where it is used. */
2189 bitmap_and_into (bb_live_info->in, bb_lr_info->in);
2190 bitmap_and_into (bb_live_info->out, bb_lr_info->out);
2191 }
2192
2193 df_live->solutions_dirty = false;
2194 }
2195}
2196
2197
e011eba9 2198/* Free all storage associated with the problem. */
2199
2200static void
3072d30e 2201df_live_free (void)
e011eba9 2202{
3072d30e 2203 if (df_live->block_info)
e011eba9 2204 {
d0802b39 2205 unsigned int i;
2206
3072d30e 2207 for (i = 0; i < df_live->block_info_size; i++)
e011eba9 2208 {
3072d30e 2209 struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
d0802b39 2210 if (bb_info)
2211 {
2212 BITMAP_FREE (bb_info->gen);
2213 BITMAP_FREE (bb_info->kill);
2214 BITMAP_FREE (bb_info->in);
2215 BITMAP_FREE (bb_info->out);
2216 }
e011eba9 2217 }
d0802b39 2218
3072d30e 2219 free_alloc_pool (df_live->block_pool);
2220 df_live->block_info_size = 0;
2221 free (df_live->block_info);
e011eba9 2222 }
3072d30e 2223 BITMAP_FREE (df_live->out_of_date_transfer_functions);
2224 free (df_live);
e011eba9 2225}
2226
2227
3072d30e 2228/* Debugging info at top of bb. */
e011eba9 2229
2230static void
3072d30e 2231df_live_top_dump (basic_block bb, FILE *file)
e011eba9 2232{
3072d30e 2233 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
2234 struct df_live_problem_data *problem_data;
3e6933a8 2235
3072d30e 2236 if (!bb_info || !bb_info->in)
2237 return;
e011eba9 2238
3072d30e 2239 fprintf (file, ";; live in \t");
2240 df_print_regset (file, bb_info->in);
2241 if (df_live->problem_data)
2242 {
2243 problem_data = (struct df_live_problem_data *)df_live->problem_data;
2244 fprintf (file, ";; old in \t");
2245 df_print_regset (file, problem_data->in[bb->index]);
e011eba9 2246 }
3072d30e 2247 fprintf (file, ";; live gen \t");
2248 df_print_regset (file, bb_info->gen);
2249 fprintf (file, ";; live kill\t");
2250 df_print_regset (file, bb_info->kill);
e011eba9 2251}
2252
e011eba9 2253
3072d30e 2254/* Debugging info at bottom of bb. */
2255
2256static void
2257df_live_bottom_dump (basic_block bb, FILE *file)
e011eba9 2258{
3072d30e 2259 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
2260 struct df_live_problem_data *problem_data;
e011eba9 2261
3072d30e 2262 if (!bb_info || !bb_info->out)
2263 return;
2264
2265 fprintf (file, ";; live out \t");
2266 df_print_regset (file, bb_info->out);
2267 if (df_live->problem_data)
2268 {
2269 problem_data = (struct df_live_problem_data *)df_live->problem_data;
2270 fprintf (file, ";; old out \t");
2271 df_print_regset (file, problem_data->out[bb->index]);
2272 }
2273}
e011eba9 2274
e011eba9 2275
3072d30e 2276/* Build the datastructure to verify that the solution to the dataflow
2277 equations is not dirty. */
2278
2279static void
2280df_live_verify_solution_start (void)
e011eba9 2281{
3072d30e 2282 basic_block bb;
2283 struct df_live_problem_data *problem_data;
2284 if (df_live->solutions_dirty)
2285 {
2286 df_live->problem_data = NULL;
2287 return;
2288 }
2289
2290 /* Set it true so that the solution is recomputed. */
2291 df_live->solutions_dirty = true;
2292
2293 problem_data = XNEW (struct df_live_problem_data);
2294 df_live->problem_data = problem_data;
2295 problem_data->in = XNEWVEC (bitmap, last_basic_block);
2296 problem_data->out = XNEWVEC (bitmap, last_basic_block);
2297
2298 FOR_ALL_BB (bb)
2299 {
2300 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
2301 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
2302 bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
2303 bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
2304 }
e011eba9 2305}
2306
2307
3072d30e 2308/* Compare the saved datastructure and the new solution to the dataflow
2309 equations. */
e011eba9 2310
3072d30e 2311static void
2312df_live_verify_solution_end (void)
2313{
2314 struct df_live_problem_data *problem_data;
2315 basic_block bb;
2316
2317 if (df_live->problem_data == NULL)
2318 return;
2319
2320 problem_data = (struct df_live_problem_data *)df_live->problem_data;
2321
2322 FOR_ALL_BB (bb)
2323 {
2324 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
2325 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
2326 {
2327 /*df_dump (stderr);*/
2328 gcc_unreachable ();
2329 }
2330 }
2331
2332 /* Cannot delete them immediately because you may want to dump them
2333 if the comparison fails. */
2334 FOR_ALL_BB (bb)
2335 {
2336 BITMAP_FREE (problem_data->in[bb->index]);
2337 BITMAP_FREE (problem_data->out[bb->index]);
2338 }
2339
2340 free (problem_data->in);
2341 free (problem_data->out);
2342 free (problem_data);
2343 df_live->problem_data = NULL;
2344}
2345
2346
2347/* All of the information associated with every instance of the problem. */
2348
2349static struct df_problem problem_LIVE =
2350{
2351 DF_LIVE, /* Problem id. */
2352 DF_FORWARD, /* Direction. */
2353 df_live_alloc, /* Allocate the problem specific data. */
2354 df_live_reset, /* Reset global information. */
2355 df_live_free_bb_info, /* Free basic block info. */
2356 df_live_local_compute, /* Local compute function. */
2357 df_live_init, /* Init the solution specific data. */
2358 df_worklist_dataflow, /* Worklist solver. */
2359 NULL, /* Confluence operator 0. */
2360 df_live_confluence_n, /* Confluence operator n. */
2361 df_live_transfer_function, /* Transfer function. */
2362 df_live_local_finalize, /* Finalize function. */
2363 df_live_free, /* Free all of the problem information. */
2364 df_live_free, /* Remove this problem from the stack of dataflow problems. */
2365 NULL, /* Debugging. */
2366 df_live_top_dump, /* Debugging start block. */
2367 df_live_bottom_dump, /* Debugging end block. */
2368 df_live_verify_solution_start,/* Incremental solution verify start. */
2369 df_live_verify_solution_end, /* Incremental solution verify end. */
2370 &problem_LR, /* Dependent problem. */
2371 TV_DF_LIVE /* Timing variable. */
2372};
2373
2374
2375/* Create a new DATAFLOW instance and add it to an existing instance
2376 of DF. The returned structure is what is used to get at the
2377 solution. */
2378
2379void
2380df_live_add_problem (void)
2381{
2382 df_add_problem (&problem_LIVE);
2383 /* These will be initialized when df_scan_blocks processes each
2384 block. */
2385 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2386}
2387
2388
2389/* Verify that all of the lr related info is consistent and
2390 correct. */
2391
2392void
2393df_live_verify_transfer_functions (void)
2394{
2395 basic_block bb;
2396 bitmap saved_gen;
2397 bitmap saved_kill;
2398 bitmap all_blocks;
2399
2400 if (!df)
2401 return;
2402
2403 saved_gen = BITMAP_ALLOC (NULL);
2404 saved_kill = BITMAP_ALLOC (NULL);
2405 all_blocks = BITMAP_ALLOC (NULL);
2406
2407 df_grow_insn_info ();
2408
2409 FOR_ALL_BB (bb)
2410 {
2411 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
2412 bitmap_set_bit (all_blocks, bb->index);
2413
2414 if (bb_info)
2415 {
2416 /* Make a copy of the transfer functions and then compute
2417 new ones to see if the transfer functions have
2418 changed. */
2419 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
2420 bb->index))
2421 {
2422 bitmap_copy (saved_gen, bb_info->gen);
2423 bitmap_copy (saved_kill, bb_info->kill);
2424 bitmap_clear (bb_info->gen);
2425 bitmap_clear (bb_info->kill);
2426
2427 df_live_bb_local_compute (bb->index);
2428 gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
2429 gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
2430 }
2431 }
2432 else
2433 {
2434 /* If we do not have basic block info, the block must be in
2435 the list of dirty blocks or else some one has added a
2436 block behind our backs. */
2437 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
2438 bb->index));
2439 }
2440 /* Make sure no one created a block without following
2441 procedures. */
2442 gcc_assert (df_scan_get_bb_info (bb->index));
2443 }
2444
2445 /* Make sure there are no dirty bits in blocks that have been deleted. */
2446 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
2447 all_blocks));
2448 BITMAP_FREE (saved_gen);
2449 BITMAP_FREE (saved_kill);
2450 BITMAP_FREE (all_blocks);
2451}
2452
2453
2454\f
2455/*----------------------------------------------------------------------------
2456 UNINITIALIZED REGISTERS WITH EARLYCLOBBER
2457
2458 Find the set of uses for registers that are reachable from the entry
2459 block without passing thru a definition. In and out bitvectors are built
aa7aac1f 2460 for each basic block. The regnum is used to index into these sets.
2461 See df.h for details.
e011eba9 2462
2463 This is a variant of the UR problem above that has a lot of special
aa7aac1f 2464 features just for the register allocation phase. This problem
80777cd8 2465 should go away if someone would fix the interference graph.
aa7aac1f 2466
2467 ----------------------------------------------------------------------------*/
e011eba9 2468
aa7aac1f 2469/* Private data used to compute the solution for this problem. These
554f2707 2470 data structures are not accessible outside of this module. */
e011eba9 2471struct df_urec_problem_data
2472{
2473 bool earlyclobbers_found; /* True if any instruction contains an
2474 earlyclobber. */
2475#ifdef STACK_REGS
2476 bitmap stack_regs; /* Registers that may be allocated to a STACK_REGS. */
2477#endif
2478};
2479
2480
e011eba9 2481/* Set basic block info. */
2482
2483static void
3072d30e 2484df_urec_set_bb_info (unsigned int index,
2485 struct df_urec_bb_info *bb_info)
e011eba9 2486{
3072d30e 2487 gcc_assert (df_urec);
2488 gcc_assert (index < df_urec->block_info_size);
2489 df_urec->block_info[index] = bb_info;
e011eba9 2490}
2491
2492
2493/* Free basic block info. */
2494
2495static void
3072d30e 2496df_urec_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
d0802b39 2497 void *vbb_info)
e011eba9 2498{
2499 struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info;
2500 if (bb_info)
2501 {
2502 BITMAP_FREE (bb_info->gen);
2503 BITMAP_FREE (bb_info->kill);
2504 BITMAP_FREE (bb_info->in);
2505 BITMAP_FREE (bb_info->out);
2506 BITMAP_FREE (bb_info->earlyclobber);
3072d30e 2507 pool_free (df_urec->block_pool, bb_info);
e011eba9 2508 }
2509}
2510
2511
3072d30e 2512/* Allocate or reset bitmaps for DF_UREC blocks. The solution bits are
e011eba9 2513 not touched unless the block is new. */
2514
2515static void
3072d30e 2516df_urec_alloc (bitmap all_blocks)
3e6933a8 2517
e011eba9 2518{
2519 unsigned int bb_index;
2520 bitmap_iterator bi;
3e6933a8 2521 struct df_urec_problem_data *problem_data
3072d30e 2522 = (struct df_urec_problem_data *) df_urec->problem_data;
e011eba9 2523
3072d30e 2524 if (!df_urec->block_pool)
2525 df_urec->block_pool = create_alloc_pool ("df_urec_block pool",
e011eba9 2526 sizeof (struct df_urec_bb_info), 50);
2527
3072d30e 2528 if (!df_urec->problem_data)
e011eba9 2529 {
4c36ffe6 2530 problem_data = XNEW (struct df_urec_problem_data);
3072d30e 2531 df_urec->problem_data = problem_data;
e011eba9 2532 }
2533 problem_data->earlyclobbers_found = false;
2534
3072d30e 2535 df_grow_bb_info (df_urec);
e011eba9 2536
3072d30e 2537 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
e011eba9 2538 {
3072d30e 2539 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
e011eba9 2540 if (bb_info)
2541 {
2542 bitmap_clear (bb_info->kill);
2543 bitmap_clear (bb_info->gen);
2544 bitmap_clear (bb_info->earlyclobber);
2545 }
2546 else
2547 {
3072d30e 2548 bb_info = (struct df_urec_bb_info *) pool_alloc (df_urec->block_pool);
2549 df_urec_set_bb_info (bb_index, bb_info);
e011eba9 2550 bb_info->kill = BITMAP_ALLOC (NULL);
2551 bb_info->gen = BITMAP_ALLOC (NULL);
2552 bb_info->in = BITMAP_ALLOC (NULL);
2553 bb_info->out = BITMAP_ALLOC (NULL);
3072d30e 2554 bb_info->top = BITMAP_ALLOC (NULL);
e011eba9 2555 bb_info->earlyclobber = BITMAP_ALLOC (NULL);
2556 }
2557 }
2558}
2559
2560
2561/* The function modifies local info for register REG being changed in
2562 SETTER. DATA is used to pass the current basic block info. */
2563
2564static void
2565df_urec_mark_reg_change (rtx reg, rtx setter, void *data)
2566{
2567 int regno;
2568 int endregno;
2569 int i;
2570 struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2571
2572 if (GET_CODE (reg) == SUBREG)
2573 reg = SUBREG_REG (reg);
2574
2575 if (!REG_P (reg))
2576 return;
2577
a2c6f0b7 2578 regno = REGNO (reg);
e011eba9 2579 if (regno < FIRST_PSEUDO_REGISTER)
2580 {
a2c6f0b7 2581 endregno = END_HARD_REGNO (reg);
e011eba9 2582 for (i = regno; i < endregno; i++)
2583 {
2584 bitmap_set_bit (bb_info->kill, i);
2585
2586 if (GET_CODE (setter) != CLOBBER)
2587 bitmap_set_bit (bb_info->gen, i);
2588 else
2589 bitmap_clear_bit (bb_info->gen, i);
2590 }
2591 }
2592 else
2593 {
2594 bitmap_set_bit (bb_info->kill, regno);
2595
2596 if (GET_CODE (setter) != CLOBBER)
2597 bitmap_set_bit (bb_info->gen, regno);
2598 else
2599 bitmap_clear_bit (bb_info->gen, regno);
2600 }
2601}
2602/* Classes of registers which could be early clobbered in the current
2603 insn. */
2604
e011eba9 2605static VEC(int,heap) *earlyclobber_regclass;
2606
2607/* This function finds and stores register classes that could be early
2608 clobbered in INSN. If any earlyclobber classes are found, the function
2609 returns TRUE, in all other cases it returns FALSE. */
2610
2611static bool
2612df_urec_check_earlyclobber (rtx insn)
2613{
2614 int opno;
2615 bool found = false;
2616
2617 extract_insn (insn);
2618
2619 VEC_truncate (int, earlyclobber_regclass, 0);
2620 for (opno = 0; opno < recog_data.n_operands; opno++)
2621 {
2622 char c;
2623 bool amp_p;
2624 int i;
2625 enum reg_class class;
2626 const char *p = recog_data.constraints[opno];
2627
2628 class = NO_REGS;
2629 amp_p = false;
2630 for (;;)
2631 {
2632 c = *p;
2633 switch (c)
2634 {
2635 case '=': case '+': case '?':
2636 case '#': case '!':
2637 case '*': case '%':
2638 case 'm': case '<': case '>': case 'V': case 'o':
2639 case 'E': case 'F': case 'G': case 'H':
2640 case 's': case 'i': case 'n':
2641 case 'I': case 'J': case 'K': case 'L':
2642 case 'M': case 'N': case 'O': case 'P':
2643 case 'X':
2644 case '0': case '1': case '2': case '3': case '4':
2645 case '5': case '6': case '7': case '8': case '9':
2646 /* These don't say anything we care about. */
2647 break;
2648
2649 case '&':
2650 amp_p = true;
2651 break;
2652 case '\0':
2653 case ',':
2654 if (amp_p && class != NO_REGS)
2655 {
2656 int rc;
2657
2658 found = true;
2659 for (i = 0;
2660 VEC_iterate (int, earlyclobber_regclass, i, rc);
2661 i++)
2662 {
2663 if (rc == (int) class)
2664 goto found_rc;
2665 }
2666
2667 /* We use VEC_quick_push here because
2668 earlyclobber_regclass holds no more than
2669 N_REG_CLASSES elements. */
2670 VEC_quick_push (int, earlyclobber_regclass, (int) class);
2671 found_rc:
2672 ;
2673 }
2674
2675 amp_p = false;
2676 class = NO_REGS;
2677 break;
2678
2679 case 'r':
2680 class = GENERAL_REGS;
2681 break;
2682
2683 default:
2684 class = REG_CLASS_FROM_CONSTRAINT (c, p);
2685 break;
2686 }
2687 if (c == '\0')
2688 break;
2689 p += CONSTRAINT_LEN (c, p);
2690 }
2691 }
2692
2693 return found;
2694}
2695
2696/* The function checks that pseudo-register *X has a class
2697 intersecting with the class of pseudo-register could be early
2698 clobbered in the same insn.
2699
2700 This function is a no-op if earlyclobber_regclass is empty.
2701
2702 Reload can assign the same hard register to uninitialized
2703 pseudo-register and early clobbered pseudo-register in an insn if
2704 the pseudo-register is used first time in given BB and not lived at
2705 the BB start. To prevent this we don't change life information for
2706 such pseudo-registers. */
2707
2708static int
2709df_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data)
2710{
2711 enum reg_class pref_class, alt_class;
2712 int i, regno;
2713 struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2714
2715 if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER)
2716 {
2717 int rc;
2718
2719 regno = REGNO (*x);
2720 if (bitmap_bit_p (bb_info->kill, regno)
2721 || bitmap_bit_p (bb_info->gen, regno))
2722 return 0;
2723 pref_class = reg_preferred_class (regno);
2724 alt_class = reg_alternate_class (regno);
2725 for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++)
2726 {
2727 if (reg_classes_intersect_p (rc, pref_class)
2728 || (rc != NO_REGS
2729 && reg_classes_intersect_p (rc, alt_class)))
2730 {
2731 bitmap_set_bit (bb_info->earlyclobber, regno);
2732 break;
2733 }
2734 }
2735 }
2736 return 0;
2737}
2738
2739/* The function processes all pseudo-registers in *X with the aid of
2740 previous function. */
2741
2742static void
2743df_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data)
2744{
2745 for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data);
2746}
2747
2748
2749/* Compute local uninitialized register info for basic block BB. */
2750
2751static void
3072d30e 2752df_urec_bb_local_compute (unsigned int bb_index)
e011eba9 2753{
e011eba9 2754 basic_block bb = BASIC_BLOCK (bb_index);
3072d30e 2755 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
e011eba9 2756 rtx insn;
3072d30e 2757 struct df_ref **def_rec;
e011eba9 2758
3072d30e 2759 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2760 {
2761 struct df_ref *def = *def_rec;
2762 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2763 {
2764 unsigned int regno = DF_REF_REGNO (def);
2765 bitmap_set_bit (bb_info->gen, regno);
2766 }
2767 }
fcf2ad9f 2768
e011eba9 2769 FOR_BB_INSNS (bb, insn)
2770 {
2771 if (INSN_P (insn))
2772 {
2773 note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info);
3e6933a8 2774 if (df_urec_check_earlyclobber (insn))
e011eba9 2775 {
3e6933a8 2776 struct df_urec_problem_data *problem_data
3072d30e 2777 = (struct df_urec_problem_data *) df_urec->problem_data;
e011eba9 2778 problem_data->earlyclobbers_found = true;
2779 note_uses (&PATTERN (insn),
2780 df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
2781 }
2782 }
2783 }
fcf2ad9f 2784
3072d30e 2785 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2786 {
2787 struct df_ref *def = *def_rec;
2788 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2789 {
2790 unsigned int regno = DF_REF_REGNO (def);
2791 bitmap_set_bit (bb_info->gen, regno);
2792 }
2793 }
e011eba9 2794}
2795
2796
2797/* Compute local uninitialized register info. */
2798
2799static void
3072d30e 2800df_urec_local_compute (bitmap all_blocks)
e011eba9 2801{
2802 unsigned int bb_index;
2803 bitmap_iterator bi;
2804#ifdef STACK_REGS
2805 int i;
ddc556d1 2806 HARD_REG_SET stack_hard_regs, used;
3e6933a8 2807 struct df_urec_problem_data *problem_data
3072d30e 2808 = (struct df_urec_problem_data *) df_urec->problem_data;
e011eba9 2809
2810 /* Any register that MAY be allocated to a register stack (like the
2811 387) is treated poorly. Each such register is marked as being
2812 live everywhere. This keeps the register allocator and the
2813 subsequent passes from doing anything useful with these values.
2814
2815 FIXME: This seems like an incredibly poor idea. */
2816
e011eba9 2817 CLEAR_HARD_REG_SET (stack_hard_regs);
2818 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
2819 SET_HARD_REG_BIT (stack_hard_regs, i);
2820 problem_data->stack_regs = BITMAP_ALLOC (NULL);
2821 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2822 {
2823 COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]);
2824 IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]);
2825 AND_HARD_REG_SET (used, stack_hard_regs);
ddc556d1 2826 if (!hard_reg_set_empty_p (used))
2827 bitmap_set_bit (problem_data->stack_regs, i);
e011eba9 2828 }
2829#endif
2830
2831 /* We know that earlyclobber_regclass holds no more than
2832 N_REG_CLASSES elements. See df_urec_check_earlyclobber. */
2833 earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES);
2834
3072d30e 2835 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
e011eba9 2836 {
3072d30e 2837 df_urec_bb_local_compute (bb_index);
e011eba9 2838 }
2839
2840 VEC_free (int, heap, earlyclobber_regclass);
2841}
2842
2843
2844/* Initialize the solution vectors. */
2845
2846static void
3072d30e 2847df_urec_init (bitmap all_blocks)
e011eba9 2848{
2849 unsigned int bb_index;
2850 bitmap_iterator bi;
2851
2852 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2853 {
3072d30e 2854 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
e011eba9 2855
fcf2ad9f 2856 bitmap_copy (bb_info->out, bb_info->gen);
2857 bitmap_clear (bb_info->in);
e011eba9 2858 }
2859}
2860
2861
85694bac 2862/* Or in the stack regs, hard regs and early clobber regs into the
3072d30e 2863 urec_in sets of all of the blocks. */
2864
e011eba9 2865
2866static void
3072d30e 2867df_urec_local_finalize (bitmap all_blocks)
e011eba9 2868{
e011eba9 2869 bitmap tmp = BITMAP_ALLOC (NULL);
2870 bitmap_iterator bi;
2871 unsigned int bb_index;
3e6933a8 2872 struct df_urec_problem_data *problem_data
3072d30e 2873 = (struct df_urec_problem_data *) df_urec->problem_data;
e011eba9 2874
2875 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2876 {
3072d30e 2877 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2878 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
e011eba9 2879
2880 if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK)
2881 {
2882 if (problem_data->earlyclobbers_found)
2883 bitmap_ior_into (bb_info->in, bb_info->earlyclobber);
2884
2885#ifdef STACK_REGS
2886 /* We can not use the same stack register for uninitialized
2887 pseudo-register and another living pseudo-register
2888 because if the uninitialized pseudo-register dies,
2889 subsequent pass reg-stack will be confused (it will
2890 believe that the other register dies). */
2891 bitmap_ior_into (bb_info->in, problem_data->stack_regs);
2892 bitmap_ior_into (bb_info->out, problem_data->stack_regs);
2893#endif
2894 }
2895
e011eba9 2896 /* No register may reach a location where it is not used. Thus
2897 we trim the rr result to the places where it is used. */
2898 bitmap_and_into (bb_info->in, bb_lr_info->in);
2899 bitmap_and_into (bb_info->out, bb_lr_info->out);
3072d30e 2900 bitmap_copy (bb_info->top, bb_info->in);
2901 if (bb_lr_info->adef)
2902 bitmap_ior_into (bb_info->top, bb_lr_info->adef);
2903 bitmap_and_into (bb_info->top, bb_lr_info->top);
2904#if 0
e011eba9 2905 /* Hard registers may still stick in the ur_out set, but not
2906 be in the ur_in set, if their only mention was in a call
2907 in this block. This is because a call kills in the lr
2908 problem but does not kill in the rr problem. To clean
2909 this up, we execute the transfer function on the lr_in
2910 set and then use that to knock bits out of ur_out. */
2911 bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in,
2912 bb_info->kill);
2913 bitmap_and_into (bb_info->out, tmp);
2914#endif
2915 }
2916
2917#ifdef STACK_REGS
2918 BITMAP_FREE (problem_data->stack_regs);
2919#endif
2920 BITMAP_FREE (tmp);
2921}
2922
2923
2924/* Confluence function that ignores fake edges. */
2925
2926static void
3072d30e 2927df_urec_confluence_n (edge e)
e011eba9 2928{
3072d30e 2929 bitmap op1 = df_urec_get_bb_info (e->dest->index)->in;
2930 bitmap op2 = df_urec_get_bb_info (e->src->index)->out;
e011eba9 2931
2932 if (e->flags & EDGE_FAKE)
2933 return;
2934
2935 bitmap_ior_into (op1, op2);
2936}
2937
2938
2939/* Transfer function. */
2940
2941static bool
3072d30e 2942df_urec_transfer_function (int bb_index)
e011eba9 2943{
3072d30e 2944 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
e011eba9 2945 bitmap in = bb_info->in;
2946 bitmap out = bb_info->out;
2947 bitmap gen = bb_info->gen;
2948 bitmap kill = bb_info->kill;
2949
2950 return bitmap_ior_and_compl (out, gen, in, kill);
2951}
2952
2953
2954/* Free all storage associated with the problem. */
2955
2956static void
3072d30e 2957df_urec_free (void)
e011eba9 2958{
3072d30e 2959 if (df_urec->block_info)
e011eba9 2960 {
d0802b39 2961 unsigned int i;
2962
3072d30e 2963 for (i = 0; i < df_urec->block_info_size; i++)
e011eba9 2964 {
3072d30e 2965 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (i);
d0802b39 2966 if (bb_info)
2967 {
2968 BITMAP_FREE (bb_info->gen);
2969 BITMAP_FREE (bb_info->kill);
2970 BITMAP_FREE (bb_info->in);
2971 BITMAP_FREE (bb_info->out);
2972 BITMAP_FREE (bb_info->earlyclobber);
3072d30e 2973 BITMAP_FREE (bb_info->top);
d0802b39 2974 }
e011eba9 2975 }
d0802b39 2976
3072d30e 2977 free_alloc_pool (df_urec->block_pool);
d0802b39 2978
3072d30e 2979 df_urec->block_info_size = 0;
2980 free (df_urec->block_info);
2981 free (df_urec->problem_data);
e011eba9 2982 }
3072d30e 2983 free (df_urec);
e011eba9 2984}
2985
2986
3072d30e 2987/* Debugging info at top of bb. */
e011eba9 2988
2989static void
3072d30e 2990df_urec_top_dump (basic_block bb, FILE *file)
e011eba9 2991{
3072d30e 2992 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
2993 if (!bb_info || !bb_info->in)
3e6933a8 2994 return;
e011eba9 2995
3072d30e 2996 fprintf (file, ";; urec in \t");
2997 df_print_regset (file, bb_info->in);
2998 fprintf (file, ";; urec gen \t");
2999 df_print_regset (file, bb_info->gen);
3000 fprintf (file, ";; urec kill\t");
3001 df_print_regset (file, bb_info->kill);
3002 fprintf (file, ";; urec ec\t");
3003 df_print_regset (file, bb_info->earlyclobber);
3004}
3005
3006
3007/* Debugging info at bottom of bb. */
3008
3009static void
3010df_urec_bottom_dump (basic_block bb, FILE *file)
3011{
3012 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
3013 if (!bb_info || !bb_info->out)
3014 return;
3015 fprintf (file, ";; urec out \t");
3016 df_print_regset (file, bb_info->out);
e011eba9 3017}
3018
3072d30e 3019
e011eba9 3020/* All of the information associated with every instance of the problem. */
3021
3022static struct df_problem problem_UREC =
3023{
3024 DF_UREC, /* Problem id. */
3025 DF_FORWARD, /* Direction. */
3026 df_urec_alloc, /* Allocate the problem specific data. */
f64e6a69 3027 NULL, /* Reset global information. */
e011eba9 3028 df_urec_free_bb_info, /* Free basic block info. */
3029 df_urec_local_compute, /* Local compute function. */
3030 df_urec_init, /* Init the solution specific data. */
3072d30e 3031 df_worklist_dataflow, /* Worklist solver. */
e011eba9 3032 NULL, /* Confluence operator 0. */
3033 df_urec_confluence_n, /* Confluence operator n. */
3034 df_urec_transfer_function, /* Transfer function. */
3035 df_urec_local_finalize, /* Finalize function. */
3036 df_urec_free, /* Free all of the problem information. */
3072d30e 3037 df_urec_free, /* Remove this problem from the stack of dataflow problems. */
3038 NULL, /* Debugging. */
3039 df_urec_top_dump, /* Debugging start block. */
3040 df_urec_bottom_dump, /* Debugging end block. */
3041 NULL, /* Incremental solution verify start. */
3042 NULL, /* Incremental solution verfiy end. */
3043 &problem_LR, /* Dependent problem. */
3044 TV_DF_UREC /* Timing variable. */
e011eba9 3045};
3046
3047
3048/* Create a new DATAFLOW instance and add it to an existing instance
3049 of DF. The returned structure is what is used to get at the
3050 solution. */
3051
3072d30e 3052void
3053df_urec_add_problem (void)
e011eba9 3054{
3072d30e 3055 df_add_problem (&problem_UREC);
e011eba9 3056}
3057
3058
3059\f
3060/*----------------------------------------------------------------------------
3061 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
3062
3063 Link either the defs to the uses and / or the uses to the defs.
3064
3065 These problems are set up like the other dataflow problems so that
3066 they nicely fit into the framework. They are much simpler and only
3067 involve a single traversal of instructions and an examination of
3068 the reaching defs information (the dependent problem).
3069----------------------------------------------------------------------------*/
3070
3072d30e 3071#define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
e011eba9 3072
3072d30e 3073/* Create a du or ud chain from SRC to DST and link it into SRC. */
3e6933a8 3074
3072d30e 3075struct df_link *
3076df_chain_create (struct df_ref *src, struct df_ref *dst)
e011eba9 3077{
3072d30e 3078 struct df_link *head = DF_REF_CHAIN (src);
3079 struct df_link *link = pool_alloc (df_chain->block_pool);;
3080
3081 DF_REF_CHAIN (src) = link;
3082 link->next = head;
3083 link->ref = dst;
3084 return link;
3085}
e011eba9 3086
e011eba9 3087
3072d30e 3088/* Delete any du or ud chains that start at REF and point to
3089 TARGET. */
3090static void
3091df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
3092{
3093 struct df_link *chain = DF_REF_CHAIN (ref);
3094 struct df_link *prev = NULL;
e011eba9 3095
3072d30e 3096 while (chain)
e011eba9 3097 {
3072d30e 3098 if (chain->ref == target)
e011eba9 3099 {
3072d30e 3100 if (prev)
3101 prev->next = chain->next;
3102 else
3103 DF_REF_CHAIN (ref) = chain->next;
3104 pool_free (df_chain->block_pool, chain);
3105 return;
e011eba9 3106 }
3072d30e 3107 prev = chain;
3108 chain = chain->next;
e011eba9 3109 }
3072d30e 3110}
3111
3112
3113/* Delete a du or ud chain that leave or point to REF. */
3114
3115void
3116df_chain_unlink (struct df_ref *ref)
3117{
3118 struct df_link *chain = DF_REF_CHAIN (ref);
3119 while (chain)
e011eba9 3120 {
3072d30e 3121 struct df_link *next = chain->next;
3122 /* Delete the other side if it exists. */
3123 df_chain_unlink_1 (chain->ref, ref);
3124 pool_free (df_chain->block_pool, chain);
3125 chain = next;
e011eba9 3126 }
3072d30e 3127 DF_REF_CHAIN (ref) = NULL;
e011eba9 3128}
3129
3130
3072d30e 3131/* Copy the du or ud chain starting at FROM_REF and attach it to
3132 TO_REF. */
f64e6a69 3133
3072d30e 3134void
3135df_chain_copy (struct df_ref *to_ref,
3136 struct df_link *from_ref)
f64e6a69 3137{
3072d30e 3138 while (from_ref)
3139 {
3140 df_chain_create (to_ref, from_ref->ref);
3141 from_ref = from_ref->next;
3142 }
3143}
f64e6a69 3144
f64e6a69 3145
3072d30e 3146/* Remove this problem from the stack of dataflow problems. */
3147
3148static void
3149df_chain_remove_problem (void)
3150{
3151 bitmap_iterator bi;
3152 unsigned int bb_index;
3153
3154 /* Wholesale destruction of the old chains. */
3155 if (df_chain->block_pool)
3156 free_alloc_pool (df_chain->block_pool);
f64e6a69 3157
3072d30e 3158 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
3159 {
3160 rtx insn;
3161 struct df_ref **def_rec;
3162 struct df_ref **use_rec;
3163 basic_block bb = BASIC_BLOCK (bb_index);
3164
3165 if (df_chain_problem_p (DF_DU_CHAIN))
3166 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
3167 DF_REF_CHAIN (*def_rec) = NULL;
3168 if (df_chain_problem_p (DF_UD_CHAIN))
3169 for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
3170 DF_REF_CHAIN (*use_rec) = NULL;
3171
3172 FOR_BB_INSNS (bb, insn)
f64e6a69 3173 {
3072d30e 3174 unsigned int uid = INSN_UID (insn);
3175
3176 if (INSN_P (insn))
f64e6a69 3177 {
3072d30e 3178 if (df_chain_problem_p (DF_DU_CHAIN))
3179 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3180 DF_REF_CHAIN (*def_rec) = NULL;
3181 if (df_chain_problem_p (DF_UD_CHAIN))
3182 {
3183 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3184 DF_REF_CHAIN (*use_rec) = NULL;
3185 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
3186 DF_REF_CHAIN (*use_rec) = NULL;
3187 }
f64e6a69 3188 }
3189 }
3190 }
3072d30e 3191
3192 bitmap_clear (df_chain->out_of_date_transfer_functions);
3193 df_chain->block_pool = NULL;
f64e6a69 3194}
3195
3196
3072d30e 3197/* Remove the chain problem completely. */
f64e6a69 3198
3072d30e 3199static void
3200df_chain_fully_remove_problem (void)
f64e6a69 3201{
3072d30e 3202 df_chain_remove_problem ();
3203 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
3204 free (df_chain);
3205}
f64e6a69 3206
f64e6a69 3207
3072d30e 3208/* Create def-use or use-def chains. */
f64e6a69 3209
3072d30e 3210static void
3211df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3212{
3213 df_chain_remove_problem ();
3214 df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
3215 sizeof (struct df_link), 50);
f64e6a69 3216}
3217
3218
3219/* Reset all of the chains when the set of basic blocks changes. */
3220
f64e6a69 3221static void
3072d30e 3222df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
f64e6a69 3223{
3072d30e 3224 df_chain_remove_problem ();
f64e6a69 3225}
3226
3227
e011eba9 3228/* Create the chains for a list of USEs. */
3229
3230static void
3072d30e 3231df_chain_create_bb_process_use (bitmap local_rd,
3232 struct df_ref **use_rec,
e011eba9 3233 enum df_ref_flags top_flag)
3234{
e011eba9 3235 bitmap_iterator bi;
3236 unsigned int def_index;
3237
3072d30e 3238 while (*use_rec)
e011eba9 3239 {
3072d30e 3240 struct df_ref *use = *use_rec;
e011eba9 3241 unsigned int uregno = DF_REF_REGNO (use);
3072d30e 3242 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
3243 || (uregno >= FIRST_PSEUDO_REGISTER))
e011eba9 3244 {
3072d30e 3245 /* Do not want to go through this for an uninitialized var. */
3246 int count = DF_DEFS_COUNT (uregno);
3247 if (count)
e011eba9 3248 {
3072d30e 3249 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
e011eba9 3250 {
3072d30e 3251 unsigned int first_index = DF_DEFS_BEGIN (uregno);
3252 unsigned int last_index = first_index + count - 1;
e011eba9 3253
3072d30e 3254 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
3255 {
3256 struct df_ref *def;
3257 if (def_index > last_index)
3258 break;
3259
3260 def = DF_DEFS_GET (def_index);
3261 if (df_chain_problem_p (DF_DU_CHAIN))
3262 df_chain_create (def, use);
3263 if (df_chain_problem_p (DF_UD_CHAIN))
3264 df_chain_create (use, def);
3265 }
e011eba9 3266 }
3267 }
3268 }
3072d30e 3269
3270 use_rec++;
e011eba9 3271 }
3272}
3273
e011eba9 3274
3275/* Create chains from reaching defs bitmaps for basic block BB. */
3072d30e 3276
e011eba9 3277static void
3072d30e 3278df_chain_create_bb (unsigned int bb_index)
e011eba9 3279{
3280 basic_block bb = BASIC_BLOCK (bb_index);
3072d30e 3281 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
e011eba9 3282 rtx insn;
3283 bitmap cpy = BITMAP_ALLOC (NULL);
3072d30e 3284 struct df_ref **def_rec;
e011eba9 3285
3286 bitmap_copy (cpy, bb_info->in);
3072d30e 3287 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
e011eba9 3288
3289 /* Since we are going forwards, process the artificial uses first
3290 then the artificial defs second. */
3291
3292#ifdef EH_USES
3293 /* Create the chains for the artificial uses from the EH_USES at the
3294 beginning of the block. */
3072d30e 3295
3296 /* Artificials are only hard regs. */
3297 if (!(df->changeable_flags & DF_NO_HARD_REGS))
3298 df_chain_create_bb_process_use (cpy,
3299 df_get_artificial_uses (bb->index),
3300 DF_REF_AT_TOP);
e011eba9 3301#endif
3302
3072d30e 3303 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3304 {
3305 struct df_ref *def = *def_rec;
3306 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3307 {
3308 unsigned int dregno = DF_REF_REGNO (def);
3309 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3310 bitmap_clear_range (cpy,
3311 DF_DEFS_BEGIN (dregno),
3312 DF_DEFS_COUNT (dregno));
3313 bitmap_set_bit (cpy, DF_REF_ID (def));
3314 }
3315 }
e011eba9 3316
3317 /* Process the regular instructions next. */
3318 FOR_BB_INSNS (bb, insn)
3319 {
3072d30e 3320 struct df_ref **def_rec;
e011eba9 3321 unsigned int uid = INSN_UID (insn);
3322
3e6933a8 3323 if (!INSN_P (insn))
e011eba9 3324 continue;
3325
3326 /* Now scan the uses and link them up with the defs that remain
3327 in the cpy vector. */
3328
3072d30e 3329 df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
3330
3331 if (df->changeable_flags & DF_EQ_NOTES)
3332 df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
3333
e011eba9 3334
3335 /* Since we are going forwards, process the defs second. This
3336 pass only changes the bits in cpy. */
3072d30e 3337 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
e011eba9 3338 {
3072d30e 3339 struct df_ref *def = *def_rec;
e011eba9 3340 unsigned int dregno = DF_REF_REGNO (def);
3072d30e 3341 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
3342 || (dregno >= FIRST_PSEUDO_REGISTER))
3343 {
3344 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3345 bitmap_clear_range (cpy,
3346 DF_DEFS_BEGIN (dregno),
3347 DF_DEFS_COUNT (dregno));
3348 if (!(DF_REF_FLAGS (def)
3349 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3350 bitmap_set_bit (cpy, DF_REF_ID (def));
3351 }
e011eba9 3352 }
3353 }
3354
3355 /* Create the chains for the artificial uses of the hard registers
3356 at the end of the block. */
3072d30e 3357 if (!(df->changeable_flags & DF_NO_HARD_REGS))
3358 df_chain_create_bb_process_use (cpy,
3359 df_get_artificial_uses (bb->index),
3360 0);
3361
3362 BITMAP_FREE (cpy);
e011eba9 3363}
3364
3365/* Create def-use chains from reaching use bitmaps for basic blocks
3366 in BLOCKS. */
3367
3368static void
3072d30e 3369df_chain_finalize (bitmap all_blocks)
e011eba9 3370{
3371 unsigned int bb_index;
3372 bitmap_iterator bi;
e011eba9 3373
3374 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3375 {
3072d30e 3376 df_chain_create_bb (bb_index);
e011eba9 3377 }
3378}
3379
3380
3381/* Free all storage associated with the problem. */
3382
3383static void
3072d30e 3384df_chain_free (void)
e011eba9 3385{
3072d30e 3386 free_alloc_pool (df_chain->block_pool);
3387 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
3388 free (df_chain);
e011eba9 3389}
3390
3391
3392/* Debugging info. */
3393
3394static void
3072d30e 3395df_chain_top_dump (basic_block bb, FILE *file)
e011eba9 3396{
3072d30e 3397 if (df_chain_problem_p (DF_DU_CHAIN))
e011eba9 3398 {
3072d30e 3399 rtx insn;
3400 struct df_ref **def_rec = df_get_artificial_defs (bb->index);
3401 if (*def_rec)
e011eba9 3402 {
3072d30e 3403
3404 fprintf (file, ";; DU chains for artificial defs\n");
3405 while (*def_rec)
e011eba9 3406 {
3072d30e 3407 struct df_ref *def = *def_rec;
3408 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
3e6933a8 3409 df_chain_dump (DF_REF_CHAIN (def), file);
e011eba9 3410 fprintf (file, "\n");
3072d30e 3411 def_rec++;
3412 }
3413 }
3414
3415 FOR_BB_INSNS (bb, insn)
3416 {
3417 unsigned int uid = INSN_UID (insn);
3418 if (INSN_P (insn))
3419 {
3420 def_rec = DF_INSN_UID_DEFS (uid);
3421 if (*def_rec)
3422 {
3423 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
3424 DF_INSN_LUID (insn), uid);
3425
3426 while (*def_rec)
3427 {
3428 struct df_ref *def = *def_rec;
3429 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
3430 if (def->flags & DF_REF_READ_WRITE)
3431 fprintf (file, "read/write ");
3432 df_chain_dump (DF_REF_CHAIN (def), file);
3433 fprintf (file, "\n");
3434 def_rec++;
3435 }
3436 }
e011eba9 3437 }
3438 }
3439 }
3072d30e 3440}
3441
e011eba9 3442
3072d30e 3443static void
3444df_chain_bottom_dump (basic_block bb, FILE *file)
3445{
3446 if (df_chain_problem_p (DF_UD_CHAIN))
e011eba9 3447 {
3072d30e 3448 rtx insn;
3449 struct df_ref **use_rec = df_get_artificial_uses (bb->index);
3450
3451 if (*use_rec)
e011eba9 3452 {
3072d30e 3453 fprintf (file, ";; UD chains for artificial uses\n");
3454 while (*use_rec)
e011eba9 3455 {
3072d30e 3456 struct df_ref *use = *use_rec;
3457 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
3e6933a8 3458 df_chain_dump (DF_REF_CHAIN (use), file);
e011eba9 3459 fprintf (file, "\n");
3072d30e 3460 use_rec++;
3461 }
3462 }
3463
3464 FOR_BB_INSNS (bb, insn)
3465 {
3466 unsigned int uid = INSN_UID (insn);
3467 if (INSN_P (insn))
3468 {
3469 struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
3470 use_rec = DF_INSN_UID_USES (uid);
3471 if (*use_rec || *eq_use_rec)
3472 {
3473 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
3474 DF_INSN_LUID (insn), uid);
3475
3476 while (*use_rec)
3477 {
3478 struct df_ref *use = *use_rec;
3479 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
3480 if (use->flags & DF_REF_READ_WRITE)
3481 fprintf (file, "read/write ");
3482 df_chain_dump (DF_REF_CHAIN (use), file);
3483 fprintf (file, "\n");
3484 use_rec++;
3485 }
3486 while (*eq_use_rec)
3487 {
3488 struct df_ref *use = *eq_use_rec;
3489 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
3490 df_chain_dump (DF_REF_CHAIN (use), file);
3491 fprintf (file, "\n");
3492 eq_use_rec++;
3493 }
3494 }
e011eba9 3495 }
3496 }
3497 }
3498}
3499
3500
3501static struct df_problem problem_CHAIN =
3502{
3503 DF_CHAIN, /* Problem id. */
3504 DF_NONE, /* Direction. */
3505 df_chain_alloc, /* Allocate the problem specific data. */
f64e6a69 3506 df_chain_reset, /* Reset global information. */
e011eba9 3507 NULL, /* Free basic block info. */
3508 NULL, /* Local compute function. */
3509 NULL, /* Init the solution specific data. */
3510 NULL, /* Iterative solver. */
3511 NULL, /* Confluence operator 0. */
3512 NULL, /* Confluence operator n. */
3513 NULL, /* Transfer function. */
3514 df_chain_finalize, /* Finalize function. */
3515 df_chain_free, /* Free all of the problem information. */
3072d30e 3516 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
3517 NULL, /* Debugging. */
3518 df_chain_top_dump, /* Debugging start block. */
3519 df_chain_bottom_dump, /* Debugging end block. */
3520 NULL, /* Incremental solution verify start. */
3521 NULL, /* Incremental solution verfiy end. */
3522 &problem_RD, /* Dependent problem. */
3523 TV_DF_CHAIN /* Timing variable. */
e011eba9 3524};
3525
3526
3527/* Create a new DATAFLOW instance and add it to an existing instance
3528 of DF. The returned structure is what is used to get at the
3529 solution. */
3530
3072d30e 3531void
3532df_chain_add_problem (enum df_chain_flags chain_flags)
e011eba9 3533{
3072d30e 3534 df_add_problem (&problem_CHAIN);
3535 df_chain->local_flags = (unsigned int)chain_flags;
3536 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
e011eba9 3537}
3538
3072d30e 3539#undef df_chain_problem_p
e011eba9 3540
3072d30e 3541\f
e011eba9 3542/*----------------------------------------------------------------------------
3072d30e 3543 This pass computes REG_DEAD and REG_UNUSED notes.
3e6933a8 3544 ----------------------------------------------------------------------------*/
e011eba9 3545
3e6933a8 3546#ifdef REG_DEAD_DEBUGGING
3547static void
3072d30e 3548df_print_note (const char *prefix, rtx insn, rtx note)
e011eba9 3549{
3072d30e 3550 if (dump_file)
3551 {
3552 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3553 print_rtl (dump_file, note);
3554 fprintf (dump_file, "\n");
3555 }
3e6933a8 3556}
3557#endif
e011eba9 3558
3e6933a8 3559
3560/* After reg-stack, the x86 floating point stack regs are difficult to
3561 analyze because of all of the pushes, pops and rotations. Thus, we
3562 just leave the notes alone. */
3563
3072d30e 3564#ifdef STACK_REGS
3e6933a8 3565static inline bool
3072d30e 3566df_ignore_stack_reg (int regno)
3e6933a8 3567{
3072d30e 3568 return regstack_completed
3569 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3570}
3e6933a8 3571#else
3072d30e 3572static inline bool
3573df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3574{
3e6933a8 3575 return false;
3e6933a8 3576}
3072d30e 3577#endif
3e6933a8 3578
3579
3072d30e 3580/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3581 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3e6933a8 3582
3583static void
3072d30e 3584df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3e6933a8 3585{
3586 rtx *pprev = &REG_NOTES (insn);
3587 rtx link = *pprev;
3072d30e 3588 rtx dead = NULL;
3589 rtx unused = NULL;
3590
3e6933a8 3591 while (link)
3592 {
3593 switch (REG_NOTE_KIND (link))
3594 {
3595 case REG_DEAD:
3072d30e 3596 /* After reg-stack, we need to ignore any unused notes
3597 for the stack registers. */
3598 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3599 {
3600 pprev = &XEXP (link, 1);
3601 link = *pprev;
3602 }
3603 else
3604 {
3605 rtx next = XEXP (link, 1);
3606#ifdef REG_DEAD_DEBUGGING
3607 df_print_note ("deleting: ", insn, link);
3608#endif
3609 XEXP (link, 1) = dead;
3610 dead = link;
3611 *pprev = link = next;
3612 }
3613 break;
3e6933a8 3614
3e6933a8 3615 case REG_UNUSED:
3072d30e 3616 /* After reg-stack, we need to ignore any unused notes
3617 for the stack registers. */
3618 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3619 {
3620 pprev = &XEXP (link, 1);
3621 link = *pprev;
3622 }
3623 else
3e6933a8 3624 {
3625 rtx next = XEXP (link, 1);
3626#ifdef REG_DEAD_DEBUGGING
3072d30e 3627 df_print_note ("deleting: ", insn, link);
3e6933a8 3628#endif
3072d30e 3629 XEXP (link, 1) = unused;
3630 unused = link;
3e6933a8 3631 *pprev = link = next;
3632 }
3633 break;
3634
3635 default:
3636 pprev = &XEXP (link, 1);
3637 link = *pprev;
3638 break;
3639 }
3640 }
3072d30e 3641
3642 *old_dead_notes = dead;
3643 *old_unused_notes = unused;
3e6933a8 3644}
3645
3646
3072d30e 3647/* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3648 list, otherwise create a new one. */
3649
3650static inline rtx
3651df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3652{
3653 rtx this = old;
3654 rtx prev = NULL;
3655
3656 while (this)
3657 if (XEXP (this, 0) == reg)
3658 {
3659 if (prev)
3660 XEXP (prev, 1) = XEXP (this, 1);
3661 else
3662 old = XEXP (this, 1);
3663 XEXP (this, 1) = REG_NOTES (insn);
3664 REG_NOTES (insn) = this;
3665 return old;
3666 }
3667 else
3668 {
3669 prev = this;
3670 this = XEXP (this, 1);
3671 }
3672
3673 /* Did not find the note. */
3674 REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
3675 return old;
3676}
3677
3e6933a8 3678/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3679 based on the bits in LIVE. Do not generate notes for registers in
3680 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3681 not generated if the reg is both read and written by the
3682 instruction.
3683*/
3684
3072d30e 3685static rtx
3686df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3e6933a8 3687 bitmap live, bitmap do_not_gen,
3072d30e 3688 bitmap artificial_uses)
3e6933a8 3689{
3690 bool all_dead = true;
3072d30e 3691 unsigned int r;
3e6933a8 3692
3693#ifdef REG_DEAD_DEBUGGING
3072d30e 3694 if (dump_file)
3695 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3696 mws->start_regno, mws->end_regno);
3e6933a8 3697#endif
3072d30e 3698 for (r=mws->start_regno; r <= mws->end_regno; r++)
3699 if ((bitmap_bit_p (live, r))
3700 || bitmap_bit_p (artificial_uses, r))
3701 {
3702 all_dead = false;
3703 break;
3704 }
3e6933a8 3705
3706 if (all_dead)
3707 {
3072d30e 3708 unsigned int regno = mws->start_regno;
3709 old = df_set_note (REG_UNUSED, insn, old, *(mws->loc));
3710
3e6933a8 3711#ifdef REG_DEAD_DEBUGGING
3072d30e 3712 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3e6933a8 3713#endif
3714 bitmap_set_bit (do_not_gen, regno);
3715 /* Only do this if the value is totally dead. */
3e6933a8 3716 }
3717 else
3072d30e 3718 for (r=mws->start_regno; r <= mws->end_regno; r++)
3719 {
3720
3721 if ((!bitmap_bit_p (live, r))
3722 && (!bitmap_bit_p (artificial_uses, r)))
3723 {
3724 old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3e6933a8 3725#ifdef REG_DEAD_DEBUGGING
3072d30e 3726 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3e6933a8 3727#endif
3072d30e 3728 }
3729 bitmap_set_bit (do_not_gen, r);
3730 }
3731 return old;
3e6933a8 3732}
3733
3734
3735/* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3736 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3737 from being set if the instruction both reads and writes the
3738 register. */
3739
3072d30e 3740static rtx
3741df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3e6933a8 3742 bitmap live, bitmap do_not_gen,
3072d30e 3743 bitmap artificial_uses)
3e6933a8 3744{
3745 bool all_dead = true;
3072d30e 3746 unsigned int r;
3e6933a8 3747
3748#ifdef REG_DEAD_DEBUGGING
3072d30e 3749 if (dump_file)
3e6933a8 3750 {
3072d30e 3751 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3752 mws->start_regno, mws->end_regno);
3753 df_print_regset (dump_file, do_not_gen);
3754 fprintf (dump_file, " live =");
3755 df_print_regset (dump_file, live);
3756 fprintf (dump_file, " artificial uses =");
3757 df_print_regset (dump_file, artificial_uses);
3e6933a8 3758 }
3072d30e 3759#endif
3760
3761 for (r = mws->start_regno; r <= mws->end_regno; r++)
3762 if ((bitmap_bit_p (live, r))
3763 || bitmap_bit_p (artificial_uses, r)
3764 || bitmap_bit_p (do_not_gen, r))
3765 {
3766 all_dead = false;
3767 break;
3768 }
3e6933a8 3769
3770 if (all_dead)
3771 {
3072d30e 3772 if (!bitmap_bit_p (do_not_gen, mws->start_regno))
3e6933a8 3773 {
3774 /* Add a dead note for the entire multi word register. */
3072d30e 3775 old = df_set_note (REG_DEAD, insn, old, *(mws->loc));
3e6933a8 3776#ifdef REG_DEAD_DEBUGGING
3072d30e 3777 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3e6933a8 3778#endif
3e6933a8 3779 }
3780 }
3781 else
3782 {
3072d30e 3783 for (r = mws->start_regno; r <= mws->end_regno; r++)
3e6933a8 3784 {
3072d30e 3785 if ((!bitmap_bit_p (live, r))
3786 && (!bitmap_bit_p (artificial_uses, r))
3787 && (!bitmap_bit_p (do_not_gen, r)))
3e6933a8 3788 {
3072d30e 3789 old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3e6933a8 3790#ifdef REG_DEAD_DEBUGGING
3072d30e 3791 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3e6933a8 3792#endif
3793 }
3e6933a8 3794 }
3795 }
3072d30e 3796 return old;
3e6933a8 3797}
3798
3799
3800/* Create a REG_UNUSED note if necessary for DEF in INSN updating LIVE
3801 and DO_NOT_GEN. Do not generate notes for registers in artificial
3802 uses. */
3803
3072d30e 3804static rtx
3805df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
3806 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3e6933a8 3807{
3808 unsigned int dregno = DF_REF_REGNO (def);
3809
3810#ifdef REG_DEAD_DEBUGGING
3072d30e 3811 if (dump_file)
3e6933a8 3812 {
3072d30e 3813 fprintf (dump_file, " regular looking at def ");
3814 df_ref_debug (def, dump_file);
3e6933a8 3815 }
3072d30e 3816#endif
3817
3818 if (!(bitmap_bit_p (live, dregno)
3819 || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3820 || bitmap_bit_p (artificial_uses, dregno)
3821 || df_ignore_stack_reg (dregno)))
3e6933a8 3822 {
3072d30e 3823 rtx reg = (DF_REF_LOC (def))
3824 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3825 old = df_set_note (REG_UNUSED, insn, old, reg);
3e6933a8 3826#ifdef REG_DEAD_DEBUGGING
3072d30e 3827 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3e6933a8 3828#endif
3e6933a8 3829 }
3830
3e6933a8 3831 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
3832 bitmap_set_bit (do_not_gen, dregno);
3833
3072d30e 3834 /* Kill this register if it is not a subreg store or conditional store. */
3835 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3e6933a8 3836 bitmap_clear_bit (live, dregno);
3072d30e 3837 return old;
e011eba9 3838}
3839
3e6933a8 3840
3841/* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3842 info: lifetime, bb, and number of defs and uses for basic block
3843 BB. The three bitvectors are scratch regs used here. */
e011eba9 3844
3845static void
3072d30e 3846df_note_bb_compute (unsigned int bb_index,
3847 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
e011eba9 3848{
e011eba9 3849 basic_block bb = BASIC_BLOCK (bb_index);
3850 rtx insn;
3072d30e 3851 struct df_ref **def_rec;
3852 struct df_ref **use_rec;
3e6933a8 3853
3072d30e 3854 bitmap_copy (live, df_get_live_out (bb));
3e6933a8 3855 bitmap_clear (artificial_uses);
3856
3072d30e 3857#ifdef REG_DEAD_DEBUGGING
3858 if (dump_file)
3e6933a8 3859 {
3072d30e 3860 fprintf (dump_file, "live at bottom ");
3861 df_print_regset (dump_file, live);
3e6933a8 3862 }
3072d30e 3863#endif
3e6933a8 3864
3865 /* Process the artificial defs and uses at the bottom of the block
3866 to begin processing. */
3072d30e 3867 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3868 {
3869 struct df_ref *def = *def_rec;
3870 if (dump_file)
3871 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
e011eba9 3872
3072d30e 3873 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3874 bitmap_clear_bit (live, DF_REF_REGNO (def));
3875 }
e011eba9 3876
3072d30e 3877 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3878 {
3879 struct df_ref *use = *use_rec;
3880 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3881 {
3882 unsigned int regno = DF_REF_REGNO (use);
3883 bitmap_set_bit (live, regno);
3884
3885 /* Notes are not generated for any of the artificial registers
3886 at the bottom of the block. */
3887 bitmap_set_bit (artificial_uses, regno);
3888 }
3889 }
3e6933a8 3890
3072d30e 3891#ifdef REG_DEAD_DEBUGGING
3892 if (dump_file)
3893 {
3894 fprintf (dump_file, "live before artificials out ");
3895 df_print_regset (dump_file, live);
3896 }
3897#endif
3898
e011eba9 3899 FOR_BB_INSNS_REVERSE (bb, insn)
3900 {
3901 unsigned int uid = INSN_UID (insn);
3072d30e 3902 struct df_mw_hardreg **mws_rec;
3903 rtx old_dead_notes;
3904 rtx old_unused_notes;
3905
3e6933a8 3906 if (!INSN_P (insn))
e011eba9 3907 continue;
3908
3e6933a8 3909 bitmap_clear (do_not_gen);
3072d30e 3910 df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3e6933a8 3911
3912 /* Process the defs. */
3913 if (CALL_P (insn))
3914 {
3072d30e 3915#ifdef REG_DEAD_DEBUGGING
3916 if (dump_file)
3e6933a8 3917 {
3072d30e 3918 fprintf (dump_file, "processing call %d\n live =", INSN_UID (insn));
3919 df_print_regset (dump_file, live);
3e6933a8 3920 }
3072d30e 3921#endif
3e6933a8 3922 /* We only care about real sets for calls. Clobbers only
3072d30e 3923 may clobbers cannot be depended on. */
3924 mws_rec = DF_INSN_UID_MWS (uid);
3925 while (*mws_rec)
3e6933a8 3926 {
3072d30e 3927 struct df_mw_hardreg *mws = *mws_rec;
3e6933a8 3928 if ((mws->type == DF_REF_REG_DEF)
3929 && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
3072d30e 3930 old_unused_notes
3931 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3932 mws, live, do_not_gen,
3933 artificial_uses);
3934 mws_rec++;
3e6933a8 3935 }
3936
3937 /* All of the defs except the return value are some sort of
3938 clobber. This code is for the return. */
3072d30e 3939 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3940 {
3941 struct df_ref *def = *def_rec;
3942 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3943 old_unused_notes
3944 = df_create_unused_note (insn, old_unused_notes,
3945 def, live, do_not_gen,
3946 artificial_uses);
3947 }
3e6933a8 3948 }
3949 else
3950 {
3951 /* Regular insn. */
3072d30e 3952 mws_rec = DF_INSN_UID_MWS (uid);
3953 while (*mws_rec)
3e6933a8 3954 {
3072d30e 3955 struct df_mw_hardreg *mws = *mws_rec;
3e6933a8 3956 if (mws->type == DF_REF_REG_DEF)
3072d30e 3957 old_unused_notes
3958 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3959 mws, live, do_not_gen,
3960 artificial_uses);
3961 mws_rec++;
3e6933a8 3962 }
3963
3072d30e 3964 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3965 {
3966 struct df_ref *def = *def_rec;
3967 old_unused_notes
3968 = df_create_unused_note (insn, old_unused_notes,
3969 def, live, do_not_gen,
3970 artificial_uses);
3971 }
3e6933a8 3972 }
3973
3974 /* Process the uses. */
3072d30e 3975 mws_rec = DF_INSN_UID_MWS (uid);
3976 while (*mws_rec)
3e6933a8 3977 {
3072d30e 3978 struct df_mw_hardreg *mws = *mws_rec;
3e6933a8 3979 if ((mws->type != DF_REF_REG_DEF)
3980 && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
3072d30e 3981 old_dead_notes
3982 = df_set_dead_notes_for_mw (insn, old_dead_notes,
3983 mws, live, do_not_gen,
3984 artificial_uses);
3985 mws_rec++;
e011eba9 3986 }
3987
3072d30e 3988 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
e011eba9 3989 {
3072d30e 3990 struct df_ref *use = *use_rec;
e011eba9 3991 unsigned int uregno = DF_REF_REGNO (use);
3992
3072d30e 3993#ifdef REG_DEAD_DEBUGGING
3994 if (dump_file)
3e6933a8 3995 {
3072d30e 3996 fprintf (dump_file, " regular looking at use ");
3997 df_ref_debug (use, dump_file);
3e6933a8 3998 }
3e6933a8 3999#endif
fcf2ad9f 4000 if (!bitmap_bit_p (live, uregno))
4001 {
3e6933a8 4002 if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
4003 && (!bitmap_bit_p (do_not_gen, uregno))
4004 && (!bitmap_bit_p (artificial_uses, uregno))
4005 && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
4006 && (!df_ignore_stack_reg (uregno)))
4007 {
3072d30e 4008 rtx reg = (DF_REF_LOC (use))
4009 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
4010 old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3e6933a8 4011
4012#ifdef REG_DEAD_DEBUGGING
3072d30e 4013 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3e6933a8 4014#endif
4015 }
fcf2ad9f 4016 /* This register is now live. */
4017 bitmap_set_bit (live, uregno);
4018 }
e011eba9 4019 }
3072d30e 4020
4021 while (old_unused_notes)
e011eba9 4022 {
3072d30e 4023 rtx next = XEXP (old_unused_notes, 1);
4024 free_EXPR_LIST_node (old_unused_notes);
4025 old_unused_notes = next;
4026 }
4027 while (old_dead_notes)
4028 {
4029 rtx next = XEXP (old_dead_notes, 1);
4030 free_EXPR_LIST_node (old_dead_notes);
4031 old_dead_notes = next;
e011eba9 4032 }
4033 }
4034}
4035
4036
4037/* Compute register info: lifetime, bb, and number of defs and uses. */
4038static void
3072d30e 4039df_note_compute (bitmap all_blocks)
e011eba9 4040{
4041 unsigned int bb_index;
4042 bitmap_iterator bi;
3072d30e 4043 bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
4044 bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
4045 bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
3e6933a8 4046
4047#ifdef REG_DEAD_DEBUGGING
3072d30e 4048 if (dump_file)
4049 print_rtl_with_bb (dump_file, get_insns());
3e6933a8 4050#endif
e011eba9 4051
3072d30e 4052 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
e011eba9 4053 {
3072d30e 4054 df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
e011eba9 4055 }
4056
4057 BITMAP_FREE (live);
3e6933a8 4058 BITMAP_FREE (do_not_gen);
4059 BITMAP_FREE (artificial_uses);
e011eba9 4060}
4061
4062
4063/* Free all storage associated with the problem. */
4064
4065static void
3072d30e 4066df_note_free (void)
e011eba9 4067{
3072d30e 4068 free (df_note);
e011eba9 4069}
4070
4071
e011eba9 4072/* All of the information associated every instance of the problem. */
4073
3072d30e 4074static struct df_problem problem_NOTE =
e011eba9 4075{
3072d30e 4076 DF_NOTE, /* Problem id. */
e011eba9 4077 DF_NONE, /* Direction. */
3072d30e 4078 NULL, /* Allocate the problem specific data. */
f64e6a69 4079 NULL, /* Reset global information. */
e011eba9 4080 NULL, /* Free basic block info. */
3072d30e 4081 df_note_compute, /* Local compute function. */
e011eba9 4082 NULL, /* Init the solution specific data. */
4083 NULL, /* Iterative solver. */
4084 NULL, /* Confluence operator 0. */
4085 NULL, /* Confluence operator n. */
4086 NULL, /* Transfer function. */
4087 NULL, /* Finalize function. */
3072d30e 4088 df_note_free, /* Free all of the problem information. */
4089 df_note_free, /* Remove this problem from the stack of dataflow problems. */
4090 NULL, /* Debugging. */
4091 NULL, /* Debugging start block. */
4092 NULL, /* Debugging end block. */
4093 NULL, /* Incremental solution verify start. */
4094 NULL, /* Incremental solution verfiy end. */
3e6933a8 4095
4096 /* Technically this is only dependent on the live registers problem
554f2707 4097 but it will produce information if built one of uninitialized
3e6933a8 4098 register problems (UR, UREC) is also run. */
3072d30e 4099 &problem_LR, /* Dependent problem. */
4100 TV_DF_NOTE /* Timing variable. */
e011eba9 4101};
4102
4103
4104/* Create a new DATAFLOW instance and add it to an existing instance
4105 of DF. The returned structure is what is used to get at the
4106 solution. */
4107
3072d30e 4108void
4109df_note_add_problem (void)
e011eba9 4110{
3072d30e 4111 df_add_problem (&problem_NOTE);
e011eba9 4112}
3072d30e 4113
4114
4115
4116\f
4117/*----------------------------------------------------------------------------
4118 Functions for simulating the effects of single insns.
4119
4120 You can either simulate in the forwards direction, starting from
4121 the top of a block or the backwards direction from the end of the
4122 block. The main difference is that if you go forwards, the uses
4123 are examined first then the defs, and if you go backwards, the defs
4124 are examined first then the uses.
4125
4126 If you start at the top of the block, use one of DF_LIVE_IN or
4127 DF_LR_IN. If you start at the bottom of the block use one of
4128 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
4129 THEY WILL BE DESTROYED.
4130
4131----------------------------------------------------------------------------*/
4132
4133
4134/* Find the set of DEFs for INSN. */
4135
4136void
4137df_simulate_find_defs (rtx insn, bitmap defs)
4138{
4139 struct df_ref **def_rec;
4140 unsigned int uid = INSN_UID (insn);
4141
4142 if (CALL_P (insn))
4143 {
4144 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4145 {
4146 struct df_ref *def = *def_rec;
4147 unsigned int dregno = DF_REF_REGNO (def);
4148
4149 if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
4150 {
4151 if (dregno >= FIRST_PSEUDO_REGISTER
4152 || !(SIBLING_CALL_P (insn)
4153 && bitmap_bit_p (df->exit_block_uses, dregno)
4154 && !refers_to_regno_p (dregno, dregno+1,
4155 current_function_return_rtx,
4156 (rtx *)0)))
4157 {
4158 /* If the def is to only part of the reg, it does
4159 not kill the other defs that reach here. */
4160 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4161 bitmap_set_bit (defs, dregno);
4162 }
4163 }
4164 else
4165 /* This is the return value. */
4166 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4167 bitmap_set_bit (defs, dregno);
4168 }
4169 }
4170 else
4171 {
4172 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4173 {
4174 struct df_ref *def = *def_rec;
4175 /* If the def is to only part of the reg, it does
4176 not kill the other defs that reach here. */
4177 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4178 bitmap_set_bit (defs, DF_REF_REGNO (def));
4179 }
4180 }
4181}
4182
4183
4184/* Simulate the effects of the defs of INSN on LIVE. */
4185
4186void
4187df_simulate_defs (rtx insn, bitmap live)
4188{
4189 struct df_ref **def_rec;
4190 unsigned int uid = INSN_UID (insn);
4191
4192 if (CALL_P (insn))
4193 {
4194 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4195 {
4196 struct df_ref *def = *def_rec;
4197 unsigned int dregno = DF_REF_REGNO (def);
4198
4199 if (DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
4200 {
4201 if (dregno >= FIRST_PSEUDO_REGISTER
4202 || !(SIBLING_CALL_P (insn)
4203 && bitmap_bit_p (df->exit_block_uses, dregno)
4204 && !refers_to_regno_p (dregno, dregno+1,
4205 current_function_return_rtx,
4206 (rtx *)0)))
4207 {
4208 /* If the def is to only part of the reg, it does
4209 not kill the other defs that reach here. */
4210 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4211 bitmap_clear_bit (live, dregno);
4212 }
4213 }
4214 else
4215 /* This is the return value. */
4216 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4217 bitmap_clear_bit (live, dregno);
4218 }
4219 }
4220 else
4221 {
4222 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4223 {
4224 struct df_ref *def = *def_rec;
4225 unsigned int dregno = DF_REF_REGNO (def);
4226
4227 /* If the def is to only part of the reg, it does
4228 not kill the other defs that reach here. */
4229 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4230 bitmap_clear_bit (live, dregno);
4231 }
4232 }
4233}
4234
4235
4236/* Simulate the effects of the uses of INSN on LIVE. */
4237
4238void
4239df_simulate_uses (rtx insn, bitmap live)
4240{
4241 struct df_ref **use_rec;
4242 unsigned int uid = INSN_UID (insn);
4243
4244 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
4245 {
4246 struct df_ref *use = *use_rec;
4247 /* Add use to set of uses in this BB. */
4248 bitmap_set_bit (live, DF_REF_REGNO (use));
4249 }
4250}
4251
4252
4253/* Add back the always live regs in BB to LIVE. */
4254
4255static inline void
4256df_simulate_fixup_sets (basic_block bb, bitmap live)
4257{
4258 /* These regs are considered always live so if they end up dying
4259 because of some def, we need to bring the back again. */
4260 if (df_has_eh_preds (bb))
4261 bitmap_ior_into (live, df->eh_block_artificial_uses);
4262 else
4263 bitmap_ior_into (live, df->regular_block_artificial_uses);
4264}
4265
4266
4267/* Apply the artifical uses and defs at the top of BB in a forwards
4268 direction. */
4269
4270void
4271df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
4272{
4273 struct df_ref **def_rec;
4274 struct df_ref **use_rec;
4275 int bb_index = bb->index;
4276
4277 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4278 {
4279 struct df_ref *use = *use_rec;
4280 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
4281 bitmap_set_bit (live, DF_REF_REGNO (use));
4282 }
4283
4284 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4285 {
4286 struct df_ref *def = *def_rec;
4287 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4288 bitmap_clear_bit (live, DF_REF_REGNO (def));
4289 }
4290}
4291
4292
4293/* Simulate the forwards effects of INSN on the bitmap LIVE. */
4294
4295void
4296df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
4297{
4298 if (! INSN_P (insn))
4299 return;
4300
4301 df_simulate_uses (insn, live);
4302 df_simulate_defs (insn, live);
4303 df_simulate_fixup_sets (bb, live);
4304}
4305
4306
4307/* Apply the artifical uses and defs at the end of BB in a backwards
4308 direction. */
4309
4310void
4311df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
4312{
4313 struct df_ref **def_rec;
4314 struct df_ref **use_rec;
4315 int bb_index = bb->index;
4316
4317 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4318 {
4319 struct df_ref *def = *def_rec;
4320 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
4321 bitmap_clear_bit (live, DF_REF_REGNO (def));
4322 }
4323
4324 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4325 {
4326 struct df_ref *use = *use_rec;
4327 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
4328 bitmap_set_bit (live, DF_REF_REGNO (use));
4329 }
4330}
4331
4332
4333/* Simulate the backwards effects of INSN on the bitmap LIVE. */
4334
4335void
4336df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
4337{
4338 if (! INSN_P (insn))
4339 return;
4340
4341 df_simulate_defs (insn, live);
4342 df_simulate_uses (insn, live);
4343 df_simulate_fixup_sets (bb, live);
4344}
4345
4346
Mirror of https://gcc.gnu.org/git/gcc.git