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