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