]> 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
Really commit rs6000.opt
[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;
f883e0a7 112 dflow->block_info = XRESIZEVEC (void *, dflow->block_info, new_size);
4d779342
DB		 113 memset (dflow->block_info + dflow->block_info_size, 0,
114 (new_size - dflow->block_info_size) *sizeof (void *));
115 dflow->block_info_size = new_size;
116 }
117}
118
119/* Dump a def-use or use-def chain for REF to FILE. */
120
121void
23249ac4 122df_chain_dump (struct df_link *link, FILE *file)
4d779342
DB		 123{
124 fprintf (file, "{ ");
125 for (; link; link = link->next)
126 {
127 fprintf (file, "%c%d(bb %d insn %d) ",
128 DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
129 DF_REF_ID (link->ref),
130 DF_REF_BBNO (link->ref),
50e94c7e 131 DF_REF_INSN_INFO (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
4d779342
DB		 132 }
133 fprintf (file, "}");
134}
135
136
137/* Print some basic block info as part of df_dump. */
138
139void
140df_print_bb_index (basic_block bb, FILE *file)
141{
142 edge e;
143 edge_iterator ei;
144
6fb5fa3c 145 fprintf (file, "\n( ");
4d779342
DB		 146 FOR_EACH_EDGE (e, ei, bb->preds)
147 {
148 basic_block pred = e->src;
6fb5fa3c 149 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
4d779342
DB		 150 }
151 fprintf (file, ")->[%d]->( ", bb->index);
152 FOR_EACH_EDGE (e, ei, bb->succs)
153 {
154 basic_block succ = e->dest;
6fb5fa3c 155 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
4d779342
DB		 156 }
157 fprintf (file, ")\n");
158}
159
160
4d779342
DB		 161
162/* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
163 up correctly. */
164
165static void
166df_set_seen (void)
167{
6fb5fa3c
DB		 168 seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
169 seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
4d779342
DB		 170}
171
172
173static void
174df_unset_seen (void)
175{
176 BITMAP_FREE (seen_in_block);
177 BITMAP_FREE (seen_in_insn);
178}
179
180
4d779342
DB		 181\f
182/*----------------------------------------------------------------------------
183 REACHING DEFINITIONS
184
185 Find the locations in the function where each definition site for a
b11550aa
KZ		 186 pseudo reaches. In and out bitvectors are built for each basic
187 block. The id field in the ref is used to index into these sets.
188 See df.h for details.
189 ----------------------------------------------------------------------------*/
190
ba49cb7b
KZ		 191/* This problem plays a large number of games for the sake of
192 efficiency.
193
194 1) The order of the bits in the bitvectors. After the scanning
195 phase, all of the defs are sorted. All of the defs for the reg 0
196 are first, followed by all defs for reg 1 and so on.
197
198 2) There are two kill sets, one if the number of defs is less or
199 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
200 greater.
201
202 <= : Data is built directly in the kill set.
203
204 > : One level of indirection is used to keep from generating long
205 strings of 1 bits in the kill sets. Bitvectors that are indexed
206 by the regnum are used to represent that there is a killing def
207 for the register. The confluence and transfer functions use
208 these along with the bitmap_clear_range call to remove ranges of
209 bits without actually generating a knockout vector.
210
211 The kill and sparse_kill and the dense_invalidated_by_call and
212 sparse_invalidated_by_call both play this game. */
4d779342 213
b11550aa 214/* Private data used to compute the solution for this problem. These
6fc0bb99 215 data structures are not accessible outside of this module. */
4d779342
DB		 216struct df_rd_problem_data
217{
4d779342
DB		 218 /* The set of defs to regs invalidated by call. */
219 bitmap sparse_invalidated_by_call;
b11550aa 220 /* The set of defs to regs invalidate by call for rd. */
6fb5fa3c
DB		 221 bitmap dense_invalidated_by_call;
222 /* An obstack for the bitmaps we need for this problem. */
223 bitmap_obstack rd_bitmaps;
4d779342
DB		 224};
225
4d779342
DB		 226/* Set basic block info. */
227
228static void
6fb5fa3c 229df_rd_set_bb_info (unsigned int index,
4d779342
DB		 230 struct df_rd_bb_info *bb_info)
231{
6fb5fa3c
DB		 232 gcc_assert (df_rd);
233 gcc_assert (index < df_rd->block_info_size);
234 df_rd->block_info[index] = bb_info;
4d779342
DB		 235}
236
237
238/* Free basic block info. */
239
240static void
6fb5fa3c 241df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
3b8266e2 242 void *vbb_info)
4d779342
DB		 243{
244 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
245 if (bb_info)
246 {
247 BITMAP_FREE (bb_info->kill);
248 BITMAP_FREE (bb_info->sparse_kill);
249 BITMAP_FREE (bb_info->gen);
250 BITMAP_FREE (bb_info->in);
251 BITMAP_FREE (bb_info->out);
6fb5fa3c 252 pool_free (df_rd->block_pool, bb_info);
4d779342
DB		 253 }
254}
255
256
6fb5fa3c 257/* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
4d779342
DB		 258 not touched unless the block is new. */
259
260static void
6fb5fa3c 261df_rd_alloc (bitmap all_blocks)
4d779342
DB		 262{
263 unsigned int bb_index;
264 bitmap_iterator bi;
6fb5fa3c 265 struct df_rd_problem_data *problem_data;
4d779342 266
6fb5fa3c
DB		 267 if (!df_rd->block_pool)
268 df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
4d779342
DB		 269 sizeof (struct df_rd_bb_info), 50);
270
6fb5fa3c 271 if (df_rd->problem_data)
4d779342 272 {
6fb5fa3c 273 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
4d779342
DB		 274 bitmap_clear (problem_data->sparse_invalidated_by_call);
275 bitmap_clear (problem_data->dense_invalidated_by_call);
276 }
277 else
278 {
6fb5fa3c
DB		 279 problem_data = XNEW (struct df_rd_problem_data);
280 df_rd->problem_data = problem_data;
281
282 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
283 problem_data->sparse_invalidated_by_call
284 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
285 problem_data->dense_invalidated_by_call
286 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
4d779342
DB		 287 }
288
6fb5fa3c 289 df_grow_bb_info (df_rd);
4d779342 290
23249ac4 291 /* Because of the clustering of all use sites for the same pseudo,
4d779342
DB		 292 we have to process all of the blocks before doing the
293 analysis. */
294
23249ac4 295 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4d779342 296 {
6fb5fa3c 297 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
4d779342
DB		 298 if (bb_info)
299 {
300 bitmap_clear (bb_info->kill);
301 bitmap_clear (bb_info->sparse_kill);
302 bitmap_clear (bb_info->gen);
303 }
304 else
305 {
6fb5fa3c
DB		 306 bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
307 df_rd_set_bb_info (bb_index, bb_info);
308 bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
309 bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
310 bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
311 bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
312 bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
4d779342
DB		 313 }
314 }
89a95777 315 df_rd->optional_p = true;
4d779342
DB		 316}
317
318
319/* Process a list of DEFs for df_rd_bb_local_compute. */
320
321static void
963acd6f 322df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
6fb5fa3c 323 struct df_ref **def_rec,
912f2dac 324 enum df_ref_flags top_flag)
4d779342 325{
963acd6f 326 while (*def_rec)
4d779342 327 {
6fb5fa3c 328 struct df_ref *def = *def_rec;
963acd6f 329 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4d779342 330 {
963acd6f 331 unsigned int regno = DF_REF_REGNO (def);
6fb5fa3c
DB		 332 unsigned int begin = DF_DEFS_BEGIN (regno);
333 unsigned int n_defs = DF_DEFS_COUNT (regno);
963acd6f
KZ		 334
335 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
336 || (regno >= FIRST_PSEUDO_REGISTER))
337 {
338 /* Only the last def(s) for a regno in the block has any
339 effect. */
340 if (!bitmap_bit_p (seen_in_block, regno))
341 {
342 /* The first def for regno in insn gets to knock out the
343 defs from other instructions. */
344 if ((!bitmap_bit_p (seen_in_insn, regno))
345 /* If the def is to only part of the reg, it does
346 not kill the other defs that reach here. */
347 && (!(DF_REF_FLAGS (def) &
348 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
349 {
350 if (n_defs > DF_SPARSE_THRESHOLD)
351 {
352 bitmap_set_bit (bb_info->sparse_kill, regno);
353 bitmap_clear_range(bb_info->gen, begin, n_defs);
354 }
355 else
356 {
357 bitmap_set_range (bb_info->kill, begin, n_defs);
358 bitmap_clear_range (bb_info->gen, begin, n_defs);
359 }
360 }
361
362 bitmap_set_bit (seen_in_insn, regno);
363 /* All defs for regno in the instruction may be put into
364 the gen set. */
365 if (!(DF_REF_FLAGS (def)
366 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
367 bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
368 }
369 }
4d779342 370 }
963acd6f 371 def_rec++;
4d779342
DB		 372 }
373}
374
375/* Compute local reaching def info for basic block BB. */
376
377static void
6fb5fa3c 378df_rd_bb_local_compute (unsigned int bb_index)
4d779342 379{
4d779342 380 basic_block bb = BASIC_BLOCK (bb_index);
6fb5fa3c 381 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
4d779342
DB		 382 rtx insn;
383
384 bitmap_clear (seen_in_block);
385 bitmap_clear (seen_in_insn);
386
6fb5fa3c
DB		 387 /* Artificials are only hard regs. */
388 if (!(df->changeable_flags & DF_NO_HARD_REGS))
963acd6f 389 df_rd_bb_local_compute_process_def (bb_info,
6fb5fa3c
DB		 390 df_get_artificial_defs (bb_index),
391 0);
912f2dac 392
4d779342
DB		 393 FOR_BB_INSNS_REVERSE (bb, insn)
394 {
395 unsigned int uid = INSN_UID (insn);
396
23249ac4 397 if (!INSN_P (insn))
4d779342
DB		 398 continue;
399
6fb5fa3c
DB		 400 df_rd_bb_local_compute_process_def (bb_info,
401 DF_INSN_UID_DEFS (uid), 0);
4d779342
DB		 402
403 /* This complex dance with the two bitmaps is required because
404 instructions can assign twice to the same pseudo. This
405 generally happens with calls that will have one def for the
406 result and another def for the clobber. If only one vector
407 is used and the clobber goes first, the result will be
408 lost. */
409 bitmap_ior_into (seen_in_block, seen_in_insn);
410 bitmap_clear (seen_in_insn);
411 }
412
912f2dac
DB		 413 /* Process the artificial defs at the top of the block last since we
414 are going backwards through the block and these are logically at
415 the start. */
6fb5fa3c
DB		 416 if (!(df->changeable_flags & DF_NO_HARD_REGS))
417 df_rd_bb_local_compute_process_def (bb_info,
418 df_get_artificial_defs (bb_index),
419 DF_REF_AT_TOP);
4d779342
DB		 420}
421
422
423/* Compute local reaching def info for each basic block within BLOCKS. */
424
425static void
6fb5fa3c 426df_rd_local_compute (bitmap all_blocks)
4d779342 427{
4d779342
DB		 428 unsigned int bb_index;
429 bitmap_iterator bi;
430 unsigned int regno;
23249ac4 431 struct df_rd_problem_data *problem_data
6fb5fa3c 432 = (struct df_rd_problem_data *) df_rd->problem_data;
4d779342
DB		 433 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
434 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
435
436 df_set_seen ();
6fb5fa3c
DB		 437
438 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
4d779342
DB		 439
440 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
441 {
6fb5fa3c 442 df_rd_bb_local_compute (bb_index);
4d779342
DB		 443 }
444
445 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
446 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
447 {
6fb5fa3c
DB		 448 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
449 bitmap_set_bit (sparse_invalidated, regno);
4d779342 450 else
6fb5fa3c
DB		 451 bitmap_set_range (dense_invalidated,
452 DF_DEFS_BEGIN (regno),
453 DF_DEFS_COUNT (regno));
4d779342
DB		 454 }
455 df_unset_seen ();
456}
457
458
459/* Initialize the solution bit vectors for problem. */
460
461static void
6fb5fa3c 462df_rd_init_solution (bitmap all_blocks)
4d779342
DB		 463{
464 unsigned int bb_index;
465 bitmap_iterator bi;
466
467 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
468 {
6fb5fa3c 469 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
4d779342
DB		 470
471 bitmap_copy (bb_info->out, bb_info->gen);
472 bitmap_clear (bb_info->in);
473 }
474}
475
476/* In of target gets or of out of source. */
477
478static void
6fb5fa3c 479df_rd_confluence_n (edge e)
4d779342 480{
6fb5fa3c
DB		 481 bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
482 bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
4d779342 483
2b49e1a0
KZ		 484 if (e->flags & EDGE_FAKE)
485 return;
486
963acd6f 487 if (e->flags & EDGE_EH)
4d779342 488 {
23249ac4 489 struct df_rd_problem_data *problem_data
6fb5fa3c 490 = (struct df_rd_problem_data *) df_rd->problem_data;
4d779342
DB		 491 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
492 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
4d779342
DB		 493 bitmap_iterator bi;
494 unsigned int regno;
963acd6f 495 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
59c52af4
KZ		 496
497 bitmap_copy (tmp, op2);
498 bitmap_and_compl_into (tmp, dense_invalidated);
499
4d779342
DB		 500 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
501 {
59c52af4 502 bitmap_clear_range (tmp,
6fb5fa3c
DB		 503 DF_DEFS_BEGIN (regno),
504 DF_DEFS_COUNT (regno));
4d779342 505 }
59c52af4
KZ		 506 bitmap_ior_into (op1, tmp);
507 BITMAP_FREE (tmp);
4d779342
DB		 508 }
509 else
510 bitmap_ior_into (op1, op2);
511}
512
513
514/* Transfer function. */
515
516static bool
6fb5fa3c 517df_rd_transfer_function (int bb_index)
4d779342 518{
6fb5fa3c 519 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
4d779342
DB		 520 unsigned int regno;
521 bitmap_iterator bi;
522 bitmap in = bb_info->in;
523 bitmap out = bb_info->out;
524 bitmap gen = bb_info->gen;
525 bitmap kill = bb_info->kill;
526 bitmap sparse_kill = bb_info->sparse_kill;
527
963acd6f
KZ		 528 if (bitmap_empty_p (sparse_kill))
529 return bitmap_ior_and_compl (out, gen, in, kill);
4d779342
DB		 530 else
531 {
6fb5fa3c 532 struct df_rd_problem_data *problem_data;
963acd6f 533 bool changed = false;
6fb5fa3c
DB		 534 bitmap tmp;
535
536 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
537 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
538 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
539 tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
540
4d779342
DB		 541 bitmap_copy (tmp, in);
542 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
543 {
544 bitmap_clear_range (tmp,
6fb5fa3c
DB		 545 DF_DEFS_BEGIN (regno),
546 DF_DEFS_COUNT (regno));
4d779342
DB		 547 }
548 bitmap_and_compl_into (tmp, kill);
549 bitmap_ior_into (tmp, gen);
550 changed = !bitmap_equal_p (tmp, out);
551 if (changed)
552 {
553 BITMAP_FREE (out);
554 bb_info->out = tmp;
555 }
556 else
963acd6f
KZ		 557 BITMAP_FREE (tmp);
558 return changed;
4d779342
DB		 559 }
560}
561
562
563/* Free all storage associated with the problem. */
564
565static void
6fb5fa3c 566df_rd_free (void)
4d779342 567{
23249ac4 568 struct df_rd_problem_data *problem_data
6fb5fa3c 569 = (struct df_rd_problem_data *) df_rd->problem_data;
4d779342 570
3b8266e2 571 if (problem_data)
4d779342 572 {
6fb5fa3c 573 free_alloc_pool (df_rd->block_pool);
6fb5fa3c 574 bitmap_obstack_release (&problem_data->rd_bitmaps);
3b8266e2 575
6fb5fa3c
DB		 576 df_rd->block_info_size = 0;
577 free (df_rd->block_info);
578 free (df_rd->problem_data);
4d779342 579 }
6fb5fa3c 580 free (df_rd);
4d779342
DB		 581}
582
583
584/* Debugging info. */
585
586static void
6fb5fa3c 587df_rd_start_dump (FILE *file)
4d779342 588{
23249ac4 589 struct df_rd_problem_data *problem_data
6fb5fa3c
DB		 590 = (struct df_rd_problem_data *) df_rd->problem_data;
591 unsigned int m = DF_REG_SIZE(df);
4d779342
DB		 592 unsigned int regno;
593
6fb5fa3c 594 if (!df_rd->block_info)
23249ac4
DB		 595 return;
596
6fb5fa3c 597 fprintf (file, ";; Reaching defs:\n\n");
4d779342
DB		 598
599 fprintf (file, " sparse invalidated \t");
600 dump_bitmap (file, problem_data->sparse_invalidated_by_call);
601 fprintf (file, " dense invalidated \t");
602 dump_bitmap (file, problem_data->dense_invalidated_by_call);
603
604 for (regno = 0; regno < m; regno++)
6fb5fa3c 605 if (DF_DEFS_COUNT (regno))
4d779342 606 fprintf (file, "%d[%d,%d] ", regno,
6fb5fa3c
DB		 607 DF_DEFS_BEGIN (regno),
608 DF_DEFS_COUNT (regno));
4d779342
DB		 609 fprintf (file, "\n");
610
6fb5fa3c
DB		 611}
612
613
614/* Debugging info at top of bb. */
615
616static void
617df_rd_top_dump (basic_block bb, FILE *file)
618{
619 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
620 if (!bb_info || !bb_info->in)
621 return;
622
623 fprintf (file, ";; rd in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
624 dump_bitmap (file, bb_info->in);
625 fprintf (file, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
626 dump_bitmap (file, bb_info->gen);
627 fprintf (file, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
628 dump_bitmap (file, bb_info->kill);
629}
630
631
632/* Debugging info at top of bb. */
633
634static void
635df_rd_bottom_dump (basic_block bb, FILE *file)
636{
637 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
638 if (!bb_info || !bb_info->out)
639 return;
640
641 fprintf (file, ";; rd out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
642 dump_bitmap (file, bb_info->out);
4d779342
DB		 643}
644
645/* All of the information associated with every instance of the problem. */
646
647static struct df_problem problem_RD =
648{
649 DF_RD, /* Problem id. */
650 DF_FORWARD, /* Direction. */
651 df_rd_alloc, /* Allocate the problem specific data. */
30cb87a0 652 NULL, /* Reset global information. */
4d779342
DB		 653 df_rd_free_bb_info, /* Free basic block info. */
654 df_rd_local_compute, /* Local compute function. */
655 df_rd_init_solution, /* Init the solution specific data. */
6fb5fa3c 656 df_worklist_dataflow, /* Worklist solver. */
4d779342
DB		 657 NULL, /* Confluence operator 0. */
658 df_rd_confluence_n, /* Confluence operator n. */
659 df_rd_transfer_function, /* Transfer function. */
660 NULL, /* Finalize function. */
661 df_rd_free, /* Free all of the problem information. */
6fb5fa3c
DB		 662 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
663 df_rd_start_dump, /* Debugging. */
664 df_rd_top_dump, /* Debugging start block. */
665 df_rd_bottom_dump, /* Debugging end block. */
666 NULL, /* Incremental solution verify start. */
6ed3da00 667 NULL, /* Incremental solution verify end. */
23249ac4 668 NULL, /* Dependent problem. */
89a95777
KZ		 669 TV_DF_RD, /* Timing variable. */
670 true /* Reset blocks on dropping out of blocks_to_analyze. */
4d779342
DB		 671};
672
673
674
675/* Create a new DATAFLOW instance and add it to an existing instance
676 of DF. The returned structure is what is used to get at the
677 solution. */
678
6fb5fa3c
DB		 679void
680df_rd_add_problem (void)
4d779342 681{
6fb5fa3c 682 df_add_problem (&problem_RD);
4d779342
DB		 683}
684
685
686\f
687/*----------------------------------------------------------------------------
688 LIVE REGISTERS
689
b11550aa
KZ		 690 Find the locations in the function where any use of a pseudo can
691 reach in the backwards direction. In and out bitvectors are built
cc806ac1 692 for each basic block. The regno is used to index into these sets.
b11550aa
KZ		 693 See df.h for details.
694 ----------------------------------------------------------------------------*/
4d779342 695
6fb5fa3c
DB		 696/* Private data used to verify the solution for this problem. */
697struct df_lr_problem_data
4d779342 698{
6fb5fa3c
DB		 699 bitmap *in;
700 bitmap *out;
701};
4d779342
DB		 702
703
704/* Set basic block info. */
705
706static void
6fb5fa3c 707df_lr_set_bb_info (unsigned int index,
4d779342
DB		 708 struct df_lr_bb_info *bb_info)
709{
6fb5fa3c
DB		 710 gcc_assert (df_lr);
711 gcc_assert (index < df_lr->block_info_size);
712 df_lr->block_info[index] = bb_info;
4d779342
DB		 713}
714
715
716/* Free basic block info. */
717
718static void
6fb5fa3c 719df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
3b8266e2 720 void *vbb_info)
4d779342
DB		 721{
722 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
723 if (bb_info)
724 {
725 BITMAP_FREE (bb_info->use);
726 BITMAP_FREE (bb_info->def);
727 BITMAP_FREE (bb_info->in);
728 BITMAP_FREE (bb_info->out);
6fb5fa3c 729 pool_free (df_lr->block_pool, bb_info);
4d779342
DB		 730 }
731}
732
733
6fb5fa3c 734/* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
4d779342
DB		 735 not touched unless the block is new. */
736
737static void
6fb5fa3c 738df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
4d779342
DB		 739{
740 unsigned int bb_index;
741 bitmap_iterator bi;
742
6fb5fa3c
DB		 743 if (!df_lr->block_pool)
744 df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
4d779342
DB		 745 sizeof (struct df_lr_bb_info), 50);
746
6fb5fa3c 747 df_grow_bb_info (df_lr);
4d779342 748
6fb5fa3c 749 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
4d779342 750 {
6fb5fa3c 751 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
4d779342
DB		 752 if (bb_info)
753 {
754 bitmap_clear (bb_info->def);
755 bitmap_clear (bb_info->use);
756 }
757 else
758 {
6fb5fa3c
DB		 759 bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
760 df_lr_set_bb_info (bb_index, bb_info);
4d779342
DB		 761 bb_info->use = BITMAP_ALLOC (NULL);
762 bb_info->def = BITMAP_ALLOC (NULL);
763 bb_info->in = BITMAP_ALLOC (NULL);
764 bb_info->out = BITMAP_ALLOC (NULL);
765 }
766 }
89a95777
KZ		 767
768 df_lr->optional_p = false;
4d779342
DB		 769}
770
771
6fb5fa3c
DB		 772/* Reset the global solution for recalculation. */
773
774static void
775df_lr_reset (bitmap all_blocks)
776{
777 unsigned int bb_index;
778 bitmap_iterator bi;
779
780 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
781 {
782 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
783 gcc_assert (bb_info);
784 bitmap_clear (bb_info->in);
785 bitmap_clear (bb_info->out);
6fb5fa3c
DB		 786 }
787}
788
789
4d779342
DB		 790/* Compute local live register info for basic block BB. */
791
792static void
6fb5fa3c 793df_lr_bb_local_compute (unsigned int bb_index)
4d779342
DB		 794{
795 basic_block bb = BASIC_BLOCK (bb_index);
6fb5fa3c 796 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
4d779342 797 rtx insn;
6fb5fa3c
DB		 798 struct df_ref **def_rec;
799 struct df_ref **use_rec;
4d779342 800
912f2dac 801 /* Process the registers set in an exception handler. */
6fb5fa3c
DB		 802 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
803 {
804 struct df_ref *def = *def_rec;
805 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
806 {
807 unsigned int dregno = DF_REF_REGNO (def);
808 bitmap_set_bit (bb_info->def, dregno);
809 bitmap_clear_bit (bb_info->use, dregno);
810 }
811 }
912f2dac 812
4d779342 813 /* Process the hardware registers that are always live. */
6fb5fa3c
DB		 814 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
815 {
816 struct df_ref *use = *use_rec;
817 /* Add use to set of uses in this BB. */
818 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
819 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
820 }
4d779342
DB		 821
822 FOR_BB_INSNS_REVERSE (bb, insn)
823 {
824 unsigned int uid = INSN_UID (insn);
825
23249ac4 826 if (!INSN_P (insn))
4d779342
DB		 827 continue;
828
5d545bf1 829 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4d779342 830 {
5d545bf1
SP		 831 struct df_ref *def = *def_rec;
832 /* If the def is to only part of the reg, it does
833 not kill the other defs that reach here. */
834 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4d779342
DB		 835 {
836 unsigned int dregno = DF_REF_REGNO (def);
5d545bf1
SP		 837 bitmap_set_bit (bb_info->def, dregno);
838 bitmap_clear_bit (bb_info->use, dregno);
4d779342
DB		 839 }
840 }
841
6fb5fa3c
DB		 842 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
843 {
844 struct df_ref *use = *use_rec;
845 /* Add use to set of uses in this BB. */
846 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
847 }
4d779342 848 }
ba49cb7b
KZ		 849
850 /* Process the registers set in an exception handler or the hard
851 frame pointer if this block is the target of a non local
852 goto. */
6fb5fa3c
DB		 853 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
854 {
855 struct df_ref *def = *def_rec;
ba49cb7b 856 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
6fb5fa3c
DB		 857 {
858 unsigned int dregno = DF_REF_REGNO (def);
ba49cb7b
KZ		 859 bitmap_set_bit (bb_info->def, dregno);
860 bitmap_clear_bit (bb_info->use, dregno);
6fb5fa3c
DB		 861 }
862 }
912f2dac 863
4d779342
DB		 864#ifdef EH_USES
865 /* Process the uses that are live into an exception handler. */
6fb5fa3c
DB		 866 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
867 {
868 struct df_ref *use = *use_rec;
869 /* Add use to set of uses in this BB. */
870 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
ba49cb7b 871 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
6fb5fa3c 872 }
4d779342 873#endif
89a95777
KZ		 874
875 /* If the df_live problem is not defined, such as at -O0 and -O1, we
876 still need to keep the luids up to date. This is normally done
877 in the df_live problem since this problem has a forwards
878 scan. */
879 if (!df_live)
880 df_recompute_luids (bb);
4d779342
DB		 881}
882
23249ac4 883
4d779342
DB		 884/* Compute local live register info for each basic block within BLOCKS. */
885
886static void
6fb5fa3c 887df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
4d779342 888{
4d779342
DB		 889 unsigned int bb_index;
890 bitmap_iterator bi;
891
4d779342
DB		 892 bitmap_clear (df->hardware_regs_used);
893
894 /* The all-important stack pointer must always be live. */
895 bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
896
897 /* Before reload, there are a few registers that must be forced
898 live everywhere -- which might not already be the case for
899 blocks within infinite loops. */
23249ac4 900 if (!reload_completed)
4d779342
DB		 901 {
902 /* Any reference to any pseudo before reload is a potential
903 reference of the frame pointer. */
904 bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
905
906#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
907 /* Pseudos with argument area equivalences may require
908 reloading via the argument pointer. */
909 if (fixed_regs[ARG_POINTER_REGNUM])
910 bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
911#endif
912
913 /* Any constant, or pseudo with constant equivalences, may
914 require reloading from memory using the pic register. */
915 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
916 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
917 bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
918 }
919
6fb5fa3c 920 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
4d779342
DB		 921 {
922 if (bb_index == EXIT_BLOCK)
6fb5fa3c
DB		 923 {
924 /* The exit block is special for this problem and its bits are
925 computed from thin air. */
926 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
927 bitmap_copy (bb_info->use, df->exit_block_uses);
928 }
929 else
930 df_lr_bb_local_compute (bb_index);
4d779342 931 }
6fb5fa3c
DB		 932
933 bitmap_clear (df_lr->out_of_date_transfer_functions);
4d779342
DB		 934}
935
936
937/* Initialize the solution vectors. */
938
939static void
6fb5fa3c 940df_lr_init (bitmap all_blocks)
4d779342
DB		 941{
942 unsigned int bb_index;
943 bitmap_iterator bi;
944
945 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
946 {
6fb5fa3c 947 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
4d779342
DB		 948 bitmap_copy (bb_info->in, bb_info->use);
949 bitmap_clear (bb_info->out);
950 }
951}
952
953
954/* Confluence function that processes infinite loops. This might be a
955 noreturn function that throws. And even if it isn't, getting the
956 unwind info right helps debugging. */
957static void
6fb5fa3c 958df_lr_confluence_0 (basic_block bb)
4d779342 959{
6fb5fa3c 960 bitmap op1 = df_lr_get_bb_info (bb->index)->out;
4d779342
DB		 961 if (bb != EXIT_BLOCK_PTR)
962 bitmap_copy (op1, df->hardware_regs_used);
963}
964
965
966/* Confluence function that ignores fake edges. */
23249ac4 967
4d779342 968static void
6fb5fa3c 969df_lr_confluence_n (edge e)
4d779342 970{
6fb5fa3c
DB		 971 bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
972 bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
4d779342
DB		 973
974 /* Call-clobbered registers die across exception and call edges. */
975 /* ??? Abnormal call edges ignored for the moment, as this gets
976 confused by sibling call edges, which crashes reg-stack. */
977 if (e->flags & EDGE_EH)
978 bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
979 else
980 bitmap_ior_into (op1, op2);
981
6fb5fa3c 982 bitmap_ior_into (op1, df->hardware_regs_used);
4d779342
DB		 983}
984
985
986/* Transfer function. */
23249ac4 987
4d779342 988static bool
6fb5fa3c 989df_lr_transfer_function (int bb_index)
4d779342 990{
6fb5fa3c 991 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
4d779342
DB		 992 bitmap in = bb_info->in;
993 bitmap out = bb_info->out;
994 bitmap use = bb_info->use;
995 bitmap def = bb_info->def;
6fb5fa3c 996
ba49cb7b 997 return bitmap_ior_and_compl (in, use, out, def);
6fb5fa3c
DB		 998}
999
4d779342 1000
6fb5fa3c
DB		 1001/* Run the fast dce as a side effect of building LR. */
1002
1003static void
2b49e1a0 1004df_lr_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
6fb5fa3c
DB		 1005{
1006 if (df->changeable_flags & DF_LR_RUN_DCE)
1007 {
1008 run_fast_df_dce ();
1009 if (df_lr->problem_data && df_lr->solutions_dirty)
1010 {
1011 /* If we are here, then it is because we are both verifying
1012 the solution and the dce changed the function. In that case
1013 the verification info built will be wrong. So we leave the
1014 dirty flag true so that the verifier will skip the checking
1015 part and just clean up.*/
1016 df_lr->solutions_dirty = true;
1017 }
1018 else
1019 df_lr->solutions_dirty = false;
1020 }
1021 else
1022 df_lr->solutions_dirty = false;
4d779342
DB		 1023}
1024
1025
1026/* Free all storage associated with the problem. */
1027
1028static void
6fb5fa3c 1029df_lr_free (void)
4d779342 1030{
6fb5fa3c 1031 if (df_lr->block_info)
4d779342 1032 {
3b8266e2 1033 unsigned int i;
6fb5fa3c 1034 for (i = 0; i < df_lr->block_info_size; i++)
4d779342 1035 {
6fb5fa3c 1036 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
3b8266e2
KZ		 1037 if (bb_info)
1038 {
1039 BITMAP_FREE (bb_info->use);
1040 BITMAP_FREE (bb_info->def);
1041 BITMAP_FREE (bb_info->in);
1042 BITMAP_FREE (bb_info->out);
1043 }
4d779342 1044 }
6fb5fa3c 1045 free_alloc_pool (df_lr->block_pool);
3b8266e2 1046
6fb5fa3c
DB		 1047 df_lr->block_info_size = 0;
1048 free (df_lr->block_info);
4d779342 1049 }
23249ac4 1050
6fb5fa3c
DB		 1051 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1052 free (df_lr);
4d779342
DB		 1053}
1054
1055
6fb5fa3c 1056/* Debugging info at top of bb. */
4d779342
DB		 1057
1058static void
6fb5fa3c 1059df_lr_top_dump (basic_block bb, FILE *file)
4d779342 1060{
6fb5fa3c
DB		 1061 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1062 struct df_lr_problem_data *problem_data;
1063 if (!bb_info || !bb_info->in)
1064 return;
1065
1066 fprintf (file, ";; lr in \t");
1067 df_print_regset (file, bb_info->in);
1068 if (df_lr->problem_data)
1069 {
1070 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1071 fprintf (file, ";; old in \t");
1072 df_print_regset (file, problem_data->in[bb->index]);
1073 }
1074 fprintf (file, ";; lr use \t");
1075 df_print_regset (file, bb_info->use);
1076 fprintf (file, ";; lr def \t");
1077 df_print_regset (file, bb_info->def);
1078}
1079
1080
1081/* Debugging info at bottom of bb. */
1082
1083static void
1084df_lr_bottom_dump (basic_block bb, FILE *file)
1085{
1086 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1087 struct df_lr_problem_data *problem_data;
1088 if (!bb_info || !bb_info->out)
1089 return;
4d779342 1090
6fb5fa3c
DB		 1091 fprintf (file, ";; lr out \t");
1092 df_print_regset (file, bb_info->out);
1093 if (df_lr->problem_data)
1094 {
1095 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1096 fprintf (file, ";; old out \t");
1097 df_print_regset (file, problem_data->out[bb->index]);
1098 }
1099}
1100
1101
1102/* Build the datastructure to verify that the solution to the dataflow
1103 equations is not dirty. */
1104
1105static void
1106df_lr_verify_solution_start (void)
1107{
1108 basic_block bb;
1109 struct df_lr_problem_data *problem_data;
1110 if (df_lr->solutions_dirty)
1111 {
1112 df_lr->problem_data = NULL;
1113 return;
1114 }
1115
1116 /* Set it true so that the solution is recomputed. */
1117 df_lr->solutions_dirty = true;
1118
1119 problem_data = XNEW (struct df_lr_problem_data);
1120 df_lr->problem_data = problem_data;
1121 problem_data->in = XNEWVEC (bitmap, last_basic_block);
1122 problem_data->out = XNEWVEC (bitmap, last_basic_block);
1123
1124 FOR_ALL_BB (bb)
1125 {
1126 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1127 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1128 bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1129 bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1130 }
1131}
1132
1133
1134/* Compare the saved datastructure and the new solution to the dataflow
1135 equations. */
1136
1137static void
1138df_lr_verify_solution_end (void)
1139{
1140 struct df_lr_problem_data *problem_data;
1141 basic_block bb;
1142
1143 if (df_lr->problem_data == NULL)
23249ac4
DB		 1144 return;
1145
6fb5fa3c
DB		 1146 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1147
1148 if (df_lr->solutions_dirty)
1149 /* Do not check if the solution is still dirty. See the comment
2b49e1a0 1150 in df_lr_finalize for details. */
6fb5fa3c
DB		 1151 df_lr->solutions_dirty = false;
1152 else
1153 FOR_ALL_BB (bb)
1154 {
1155 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1156 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1157 {
1158 /*df_dump (stderr);*/
1159 gcc_unreachable ();
1160 }
1161 }
1162
1163 /* Cannot delete them immediately because you may want to dump them
1164 if the comparison fails. */
4d779342
DB		 1165 FOR_ALL_BB (bb)
1166 {
6fb5fa3c
DB		 1167 BITMAP_FREE (problem_data->in[bb->index]);
1168 BITMAP_FREE (problem_data->out[bb->index]);
4d779342 1169 }
6fb5fa3c
DB		 1170
1171 free (problem_data->in);
1172 free (problem_data->out);
1173 free (problem_data);
1174 df_lr->problem_data = NULL;
4d779342
DB		 1175}
1176
6fb5fa3c 1177
4d779342
DB		 1178/* All of the information associated with every instance of the problem. */
1179
1180static struct df_problem problem_LR =
1181{
1182 DF_LR, /* Problem id. */
1183 DF_BACKWARD, /* Direction. */
1184 df_lr_alloc, /* Allocate the problem specific data. */
6fb5fa3c 1185 df_lr_reset, /* Reset global information. */
4d779342
DB		 1186 df_lr_free_bb_info, /* Free basic block info. */
1187 df_lr_local_compute, /* Local compute function. */
1188 df_lr_init, /* Init the solution specific data. */
6fb5fa3c 1189 df_worklist_dataflow, /* Worklist solver. */
4d779342
DB		 1190 df_lr_confluence_0, /* Confluence operator 0. */
1191 df_lr_confluence_n, /* Confluence operator n. */
1192 df_lr_transfer_function, /* Transfer function. */
2b49e1a0 1193 df_lr_finalize, /* Finalize function. */
4d779342 1194 df_lr_free, /* Free all of the problem information. */
6fb5fa3c
DB		 1195 NULL, /* Remove this problem from the stack of dataflow problems. */
1196 NULL, /* Debugging. */
1197 df_lr_top_dump, /* Debugging start block. */
1198 df_lr_bottom_dump, /* Debugging end block. */
1199 df_lr_verify_solution_start,/* Incremental solution verify start. */
1200 df_lr_verify_solution_end, /* Incremental solution verify end. */
23249ac4 1201 NULL, /* Dependent problem. */
89a95777
KZ		 1202 TV_DF_LR, /* Timing variable. */
1203 false /* Reset blocks on dropping out of blocks_to_analyze. */
4d779342
DB		 1204};
1205
1206
1207/* Create a new DATAFLOW instance and add it to an existing instance
1208 of DF. The returned structure is what is used to get at the
1209 solution. */
1210
6fb5fa3c
DB		 1211void
1212df_lr_add_problem (void)
1213{
1214 df_add_problem (&problem_LR);
1215 /* These will be initialized when df_scan_blocks processes each
1216 block. */
1217 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1218}
1219
1220
1221/* Verify that all of the lr related info is consistent and
1222 correct. */
1223
1224void
1225df_lr_verify_transfer_functions (void)
4d779342 1226{
6fb5fa3c
DB		 1227 basic_block bb;
1228 bitmap saved_def;
1229 bitmap saved_use;
1230 bitmap saved_adef;
1231 bitmap saved_ause;
1232 bitmap all_blocks;
6fb5fa3c
DB		 1233
1234 if (!df)
1235 return;
1236
1237 saved_def = BITMAP_ALLOC (NULL);
1238 saved_use = BITMAP_ALLOC (NULL);
1239 saved_adef = BITMAP_ALLOC (NULL);
1240 saved_ause = BITMAP_ALLOC (NULL);
1241 all_blocks = BITMAP_ALLOC (NULL);
1242
1243 FOR_ALL_BB (bb)
1244 {
1245 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1246 bitmap_set_bit (all_blocks, bb->index);
1247
1248 if (bb_info)
1249 {
1250 /* Make a copy of the transfer functions and then compute
1251 new ones to see if the transfer functions have
1252 changed. */
1253 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1254 bb->index))
1255 {
1256 bitmap_copy (saved_def, bb_info->def);
1257 bitmap_copy (saved_use, bb_info->use);
1258 bitmap_clear (bb_info->def);
1259 bitmap_clear (bb_info->use);
1260
6fb5fa3c
DB		 1261 df_lr_bb_local_compute (bb->index);
1262 gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1263 gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
6fb5fa3c
DB		 1264 }
1265 }
1266 else
1267 {
1268 /* If we do not have basic block info, the block must be in
1269 the list of dirty blocks or else some one has added a
1270 block behind our backs. */
1271 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1272 bb->index));
1273 }
1274 /* Make sure no one created a block without following
1275 procedures. */
1276 gcc_assert (df_scan_get_bb_info (bb->index));
1277 }
1278
1279 /* Make sure there are no dirty bits in blocks that have been deleted. */
1280 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1281 all_blocks));
1282
1283 BITMAP_FREE (saved_def);
1284 BITMAP_FREE (saved_use);
1285 BITMAP_FREE (saved_adef);
1286 BITMAP_FREE (saved_ause);
1287 BITMAP_FREE (all_blocks);
4d779342
DB		 1288}
1289
1290
1291\f
1292/*----------------------------------------------------------------------------
05c219bb
PB		 1293 LIVE AND MUST-INITIALIZED REGISTERS.
1294
1295 This problem first computes the IN and OUT bitvectors for the
1296 must-initialized registers problems, which is a forward problem.
1297 It gives the set of registers for which we MUST have an available
1298 definition on any path from the entry block to the entry/exit of
1299 a basic block. Sets generate a definition, while clobbers kill
1300 a definition.
1301
1302 In and out bitvectors are built for each basic block and are indexed by
1303 regnum (see df.h for details). In and out bitvectors in struct
1304 df_live_bb_info actually refers to the must-initialized problem;
1305
1306 Then, the in and out sets for the LIVE problem itself are computed.
1307 These are the logical AND of the IN and OUT sets from the LR problem
1308 and the must-initialized problem.
6fb5fa3c 1309----------------------------------------------------------------------------*/
4d779342 1310
6fb5fa3c
DB		 1311/* Private data used to verify the solution for this problem. */
1312struct df_live_problem_data
4d779342 1313{
6fb5fa3c
DB		 1314 bitmap *in;
1315 bitmap *out;
1316};
4d779342 1317
5aa52064
KZ		 1318/* Scratch var used by transfer functions. This is used to implement
1319 an optimization to reduce the amount of space used to compute the
1320 combined lr and live analysis. */
1321static bitmap df_live_scratch;
4d779342
DB		 1322
1323/* Set basic block info. */
1324
1325static void
6fb5fa3c
DB		 1326df_live_set_bb_info (unsigned int index,
1327 struct df_live_bb_info *bb_info)
4d779342 1328{
6fb5fa3c
DB		 1329 gcc_assert (df_live);
1330 gcc_assert (index < df_live->block_info_size);
1331 df_live->block_info[index] = bb_info;
4d779342
DB		 1332}
1333
1334
1335/* Free basic block info. */
1336
1337static void
6fb5fa3c 1338df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
3b8266e2 1339 void *vbb_info)
4d779342 1340{
6fb5fa3c 1341 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
4d779342
DB		 1342 if (bb_info)
1343 {
1344 BITMAP_FREE (bb_info->gen);
1345 BITMAP_FREE (bb_info->kill);
1346 BITMAP_FREE (bb_info->in);
1347 BITMAP_FREE (bb_info->out);
6fb5fa3c 1348 pool_free (df_live->block_pool, bb_info);
4d779342
DB		 1349 }
1350}
1351
1352
6fb5fa3c 1353/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
4d779342
DB		 1354 not touched unless the block is new. */
1355
1356static void
6fb5fa3c 1357df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
4d779342
DB		 1358{
1359 unsigned int bb_index;
1360 bitmap_iterator bi;
1361
6fb5fa3c
DB		 1362 if (!df_live->block_pool)
1363 df_live->block_pool = create_alloc_pool ("df_live_block pool",
1364 sizeof (struct df_live_bb_info), 100);
5aa52064
KZ		 1365 if (!df_live_scratch)
1366 df_live_scratch = BITMAP_ALLOC (NULL);
4d779342 1367
6fb5fa3c 1368 df_grow_bb_info (df_live);
4d779342 1369
6fb5fa3c 1370 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
4d779342 1371 {
6fb5fa3c 1372 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
4d779342
DB		 1373 if (bb_info)
1374 {
1375 bitmap_clear (bb_info->kill);
1376 bitmap_clear (bb_info->gen);
1377 }
1378 else
1379 {
6fb5fa3c
DB		 1380 bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1381 df_live_set_bb_info (bb_index, bb_info);
4d779342
DB		 1382 bb_info->kill = BITMAP_ALLOC (NULL);
1383 bb_info->gen = BITMAP_ALLOC (NULL);
1384 bb_info->in = BITMAP_ALLOC (NULL);
1385 bb_info->out = BITMAP_ALLOC (NULL);
1386 }
1387 }
89a95777 1388 df_live->optional_p = (optimize <= 1);
4d779342
DB		 1389}
1390
1391
6fb5fa3c
DB		 1392/* Reset the global solution for recalculation. */
1393
1394static void
1395df_live_reset (bitmap all_blocks)
1396{
1397 unsigned int bb_index;
1398 bitmap_iterator bi;
1399
1400 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1401 {
5aa52064 1402 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
6fb5fa3c
DB		 1403 gcc_assert (bb_info);
1404 bitmap_clear (bb_info->in);
1405 bitmap_clear (bb_info->out);
1406 }
1407}
1408
1409
4d779342
DB		 1410/* Compute local uninitialized register info for basic block BB. */
1411
1412static void
6fb5fa3c 1413df_live_bb_local_compute (unsigned int bb_index)
4d779342 1414{
4d779342 1415 basic_block bb = BASIC_BLOCK (bb_index);
6fb5fa3c 1416 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
4d779342 1417 rtx insn;
6fb5fa3c
DB		 1418 struct df_ref **def_rec;
1419 int luid = 0;
4d779342 1420
6fb5fa3c 1421 FOR_BB_INSNS (bb, insn)
4d779342
DB		 1422 {
1423 unsigned int uid = INSN_UID (insn);
6fb5fa3c
DB		 1424 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1425
1426 /* Inserting labels does not always trigger the incremental
1427 rescanning. */
1428 if (!insn_info)
1429 {
1430 gcc_assert (!INSN_P (insn));
50e94c7e 1431 insn_info = df_insn_create_insn_record (insn);
6fb5fa3c
DB		 1432 }
1433
50e94c7e 1434 DF_INSN_INFO_LUID (insn_info) = luid;
4d779342
DB		 1435 if (!INSN_P (insn))
1436 continue;
1437
6fb5fa3c 1438 luid++;
50e94c7e 1439 for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
4d779342 1440 {
6fb5fa3c 1441 struct df_ref *def = *def_rec;
4d779342 1442 unsigned int regno = DF_REF_REGNO (def);
6fb5fa3c
DB		 1443
1444 if (DF_REF_FLAGS_IS_SET (def,
1445 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1446 /* All partial or conditional def
1447 seen are included in the gen set. */
1448 bitmap_set_bit (bb_info->gen, regno);
1449 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1450 /* Only must clobbers for the entire reg destroy the
1451 value. */
1452 bitmap_set_bit (bb_info->kill, regno);
1453 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1454 bitmap_set_bit (bb_info->gen, regno);
4d779342 1455 }
4d779342
DB		 1456 }
1457
6fb5fa3c
DB		 1458 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1459 {
1460 struct df_ref *def = *def_rec;
5aa52064 1461 bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
6fb5fa3c 1462 }
4d779342
DB		 1463}
1464
1465
1466/* Compute local uninitialized register info. */
1467
1468static void
6fb5fa3c 1469df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
4d779342
DB		 1470{
1471 unsigned int bb_index;
1472 bitmap_iterator bi;
1473
6fb5fa3c 1474 df_grow_insn_info ();
4d779342 1475
6fb5fa3c
DB		 1476 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1477 0, bb_index, bi)
4d779342 1478 {
6fb5fa3c 1479 df_live_bb_local_compute (bb_index);
4d779342
DB		 1480 }
1481
6fb5fa3c 1482 bitmap_clear (df_live->out_of_date_transfer_functions);
4d779342
DB		 1483}
1484
1485
1486/* Initialize the solution vectors. */
1487
1488static void
6fb5fa3c 1489df_live_init (bitmap all_blocks)
4d779342
DB		 1490{
1491 unsigned int bb_index;
1492 bitmap_iterator bi;
1493
1494 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1495 {
6fb5fa3c 1496 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
5aa52064 1497 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
4d779342 1498
5aa52064
KZ		 1499 /* No register may reach a location where it is not used. Thus
1500 we trim the rr result to the places where it is used. */
1501 bitmap_and (bb_info->out, bb_info->gen, bb_lr_info->out);
4d779342
DB		 1502 bitmap_clear (bb_info->in);
1503 }
1504}
1505
05c219bb 1506/* Forward confluence function that ignores fake edges. */
4d779342
DB		 1507
1508static void
6fb5fa3c 1509df_live_confluence_n (edge e)
4d779342 1510{
6fb5fa3c
DB		 1511 bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
1512 bitmap op2 = df_live_get_bb_info (e->src->index)->out;
4d779342
DB		 1513
1514 if (e->flags & EDGE_FAKE)
1515 return;
1516
1517 bitmap_ior_into (op1, op2);
1518}
1519
1520
05c219bb 1521/* Transfer function for the forwards must-initialized problem. */
4d779342
DB		 1522
1523static bool
6fb5fa3c 1524df_live_transfer_function (int bb_index)
4d779342 1525{
6fb5fa3c 1526 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
5aa52064 1527 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
4d779342
DB		 1528 bitmap in = bb_info->in;
1529 bitmap out = bb_info->out;
1530 bitmap gen = bb_info->gen;
1531 bitmap kill = bb_info->kill;
1532
5aa52064
KZ		 1533 /* We need to use a scratch set here so that the value returned from
1534 this function invocation properly reflects if the sets changed in
1535 a significant way; i.e. not just because the lr set was anded
1536 in. */
1537 bitmap_and (df_live_scratch, gen, bb_lr_info->out);
1538 /* No register may reach a location where it is not used. Thus
1539 we trim the rr result to the places where it is used. */
1540 bitmap_and_into (in, bb_lr_info->in);
1541
1542 return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
4d779342
DB		 1543}
1544
1545
05c219bb 1546/* And the LR info with the must-initialized registers, to produce the LIVE info. */
6fb5fa3c
DB		 1547
1548static void
2b49e1a0 1549df_live_finalize (bitmap all_blocks)
6fb5fa3c
DB		 1550{
1551
1552 if (df_live->solutions_dirty)
1553 {
1554 bitmap_iterator bi;
1555 unsigned int bb_index;
1556
1557 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1558 {
1559 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1560 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
ba49cb7b 1561
6fb5fa3c
DB		 1562 /* No register may reach a location where it is not used. Thus
1563 we trim the rr result to the places where it is used. */
1564 bitmap_and_into (bb_live_info->in, bb_lr_info->in);
1565 bitmap_and_into (bb_live_info->out, bb_lr_info->out);
1566 }
1567
1568 df_live->solutions_dirty = false;
1569 }
1570}
1571
1572
4d779342
DB		 1573/* Free all storage associated with the problem. */
1574
1575static void
6fb5fa3c 1576df_live_free (void)
4d779342 1577{
6fb5fa3c 1578 if (df_live->block_info)
4d779342 1579 {
3b8266e2
KZ		 1580 unsigned int i;
1581
6fb5fa3c 1582 for (i = 0; i < df_live->block_info_size; i++)
4d779342 1583 {
6fb5fa3c 1584 struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
3b8266e2
KZ		 1585 if (bb_info)
1586 {
1587 BITMAP_FREE (bb_info->gen);
1588 BITMAP_FREE (bb_info->kill);
1589 BITMAP_FREE (bb_info->in);
1590 BITMAP_FREE (bb_info->out);
1591 }
4d779342 1592 }
3b8266e2 1593
6fb5fa3c
DB		 1594 free_alloc_pool (df_live->block_pool);
1595 df_live->block_info_size = 0;
1596 free (df_live->block_info);
5aa52064
KZ		 1597
1598 if (df_live_scratch)
1599 BITMAP_FREE (df_live_scratch);
4d779342 1600 }
6fb5fa3c
DB		 1601 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1602 free (df_live);
4d779342
DB		 1603}
1604
1605
6fb5fa3c 1606/* Debugging info at top of bb. */
4d779342
DB		 1607
1608static void
6fb5fa3c 1609df_live_top_dump (basic_block bb, FILE *file)
4d779342 1610{
6fb5fa3c
DB		 1611 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1612 struct df_live_problem_data *problem_data;
23249ac4 1613
6fb5fa3c
DB		 1614 if (!bb_info || !bb_info->in)
1615 return;
4d779342 1616
6fb5fa3c
DB		 1617 fprintf (file, ";; live in \t");
1618 df_print_regset (file, bb_info->in);
1619 if (df_live->problem_data)
1620 {
1621 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1622 fprintf (file, ";; old in \t");
1623 df_print_regset (file, problem_data->in[bb->index]);
4d779342 1624 }
6fb5fa3c
DB		 1625 fprintf (file, ";; live gen \t");
1626 df_print_regset (file, bb_info->gen);
1627 fprintf (file, ";; live kill\t");
1628 df_print_regset (file, bb_info->kill);
4d779342
DB		 1629}
1630
4d779342 1631
6fb5fa3c
DB		 1632/* Debugging info at bottom of bb. */
1633
1634static void
1635df_live_bottom_dump (basic_block bb, FILE *file)
4d779342 1636{
6fb5fa3c
DB		 1637 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1638 struct df_live_problem_data *problem_data;
4d779342 1639
6fb5fa3c
DB		 1640 if (!bb_info || !bb_info->out)
1641 return;
1642
1643 fprintf (file, ";; live out \t");
1644 df_print_regset (file, bb_info->out);
1645 if (df_live->problem_data)
1646 {
1647 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1648 fprintf (file, ";; old out \t");
1649 df_print_regset (file, problem_data->out[bb->index]);
1650 }
1651}
4d779342 1652
4d779342 1653
6fb5fa3c
DB		 1654/* Build the datastructure to verify that the solution to the dataflow
1655 equations is not dirty. */
1656
1657static void
1658df_live_verify_solution_start (void)
4d779342 1659{
6fb5fa3c
DB		 1660 basic_block bb;
1661 struct df_live_problem_data *problem_data;
1662 if (df_live->solutions_dirty)
1663 {
1664 df_live->problem_data = NULL;
1665 return;
1666 }
1667
1668 /* Set it true so that the solution is recomputed. */
1669 df_live->solutions_dirty = true;
1670
1671 problem_data = XNEW (struct df_live_problem_data);
1672 df_live->problem_data = problem_data;
1673 problem_data->in = XNEWVEC (bitmap, last_basic_block);
1674 problem_data->out = XNEWVEC (bitmap, last_basic_block);
1675
1676 FOR_ALL_BB (bb)
1677 {
1678 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1679 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1680 bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
1681 bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
1682 }
4d779342
DB		 1683}
1684
1685
6fb5fa3c
DB		 1686/* Compare the saved datastructure and the new solution to the dataflow
1687 equations. */
4d779342 1688
6fb5fa3c
DB		 1689static void
1690df_live_verify_solution_end (void)
1691{
1692 struct df_live_problem_data *problem_data;
1693 basic_block bb;
1694
1695 if (df_live->problem_data == NULL)
1696 return;
1697
1698 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1699
1700 FOR_ALL_BB (bb)
1701 {
1702 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
1703 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1704 {
1705 /*df_dump (stderr);*/
1706 gcc_unreachable ();
1707 }
1708 }
1709
1710 /* Cannot delete them immediately because you may want to dump them
1711 if the comparison fails. */
1712 FOR_ALL_BB (bb)
1713 {
1714 BITMAP_FREE (problem_data->in[bb->index]);
1715 BITMAP_FREE (problem_data->out[bb->index]);
1716 }
1717
1718 free (problem_data->in);
1719 free (problem_data->out);
1720 free (problem_data);
1721 df_live->problem_data = NULL;
1722}
1723
1724
1725/* All of the information associated with every instance of the problem. */
1726
1727static struct df_problem problem_LIVE =
1728{
1729 DF_LIVE, /* Problem id. */
1730 DF_FORWARD, /* Direction. */
1731 df_live_alloc, /* Allocate the problem specific data. */
1732 df_live_reset, /* Reset global information. */
1733 df_live_free_bb_info, /* Free basic block info. */
1734 df_live_local_compute, /* Local compute function. */
1735 df_live_init, /* Init the solution specific data. */
1736 df_worklist_dataflow, /* Worklist solver. */
1737 NULL, /* Confluence operator 0. */
1738 df_live_confluence_n, /* Confluence operator n. */
1739 df_live_transfer_function, /* Transfer function. */
2b49e1a0 1740 df_live_finalize, /* Finalize function. */
6fb5fa3c
DB		 1741 df_live_free, /* Free all of the problem information. */
1742 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1743 NULL, /* Debugging. */
1744 df_live_top_dump, /* Debugging start block. */
1745 df_live_bottom_dump, /* Debugging end block. */
1746 df_live_verify_solution_start,/* Incremental solution verify start. */
1747 df_live_verify_solution_end, /* Incremental solution verify end. */
1748 &problem_LR, /* Dependent problem. */
89a95777
KZ		 1749 TV_DF_LIVE, /* Timing variable. */
1750 false /* Reset blocks on dropping out of blocks_to_analyze. */
6fb5fa3c
DB		 1751};
1752
1753
1754/* Create a new DATAFLOW instance and add it to an existing instance
1755 of DF. The returned structure is what is used to get at the
1756 solution. */
1757
1758void
1759df_live_add_problem (void)
1760{
1761 df_add_problem (&problem_LIVE);
1762 /* These will be initialized when df_scan_blocks processes each
1763 block. */
1764 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1765}
1766
1767
89a95777
KZ		 1768/* Set all of the blocks as dirty. This needs to be done if this
1769 problem is added after all of the insns have been scanned. */
1770
1771void
1772df_live_set_all_dirty (void)
1773{
1774 basic_block bb;
1775 FOR_ALL_BB (bb)
1776 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1777 bb->index);
1778}
1779
1780
6fb5fa3c
DB		 1781/* Verify that all of the lr related info is consistent and
1782 correct. */
1783
1784void
1785df_live_verify_transfer_functions (void)
1786{
1787 basic_block bb;
1788 bitmap saved_gen;
1789 bitmap saved_kill;
1790 bitmap all_blocks;
1791
1792 if (!df)
1793 return;
1794
1795 saved_gen = BITMAP_ALLOC (NULL);
1796 saved_kill = BITMAP_ALLOC (NULL);
1797 all_blocks = BITMAP_ALLOC (NULL);
1798
1799 df_grow_insn_info ();
1800
1801 FOR_ALL_BB (bb)
1802 {
1803 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1804 bitmap_set_bit (all_blocks, bb->index);
1805
1806 if (bb_info)
1807 {
1808 /* Make a copy of the transfer functions and then compute
1809 new ones to see if the transfer functions have
1810 changed. */
1811 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1812 bb->index))
1813 {
1814 bitmap_copy (saved_gen, bb_info->gen);
1815 bitmap_copy (saved_kill, bb_info->kill);
1816 bitmap_clear (bb_info->gen);
1817 bitmap_clear (bb_info->kill);
1818
1819 df_live_bb_local_compute (bb->index);
1820 gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
1821 gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
1822 }
1823 }
1824 else
1825 {
1826 /* If we do not have basic block info, the block must be in
1827 the list of dirty blocks or else some one has added a
1828 block behind our backs. */
1829 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1830 bb->index));
1831 }
1832 /* Make sure no one created a block without following
1833 procedures. */
1834 gcc_assert (df_scan_get_bb_info (bb->index));
1835 }
1836
1837 /* Make sure there are no dirty bits in blocks that have been deleted. */
1838 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1839 all_blocks));
1840 BITMAP_FREE (saved_gen);
1841 BITMAP_FREE (saved_kill);
1842 BITMAP_FREE (all_blocks);
1843}
4d779342
DB		 1844\f
1845/*----------------------------------------------------------------------------
1846 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1847
1848 Link either the defs to the uses and / or the uses to the defs.
1849
1850 These problems are set up like the other dataflow problems so that
1851 they nicely fit into the framework. They are much simpler and only
1852 involve a single traversal of instructions and an examination of
1853 the reaching defs information (the dependent problem).
1854----------------------------------------------------------------------------*/
1855
6fb5fa3c 1856#define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
4d779342 1857
6fb5fa3c 1858/* Create a du or ud chain from SRC to DST and link it into SRC. */
23249ac4 1859
6fb5fa3c
DB		 1860struct df_link *
1861df_chain_create (struct df_ref *src, struct df_ref *dst)
4d779342 1862{
6fb5fa3c 1863 struct df_link *head = DF_REF_CHAIN (src);
f883e0a7 1864 struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);
6fb5fa3c
DB		 1865
1866 DF_REF_CHAIN (src) = link;
1867 link->next = head;
1868 link->ref = dst;
1869 return link;
1870}
4d779342 1871
4d779342 1872
6fb5fa3c
DB		 1873/* Delete any du or ud chains that start at REF and point to
1874 TARGET. */
1875static void
1876df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
1877{
1878 struct df_link *chain = DF_REF_CHAIN (ref);
1879 struct df_link *prev = NULL;
4d779342 1880
6fb5fa3c 1881 while (chain)
4d779342 1882 {
6fb5fa3c 1883 if (chain->ref == target)
4d779342 1884 {
6fb5fa3c
DB		 1885 if (prev)
1886 prev->next = chain->next;
1887 else
1888 DF_REF_CHAIN (ref) = chain->next;
1889 pool_free (df_chain->block_pool, chain);
1890 return;
4d779342 1891 }
6fb5fa3c
DB		 1892 prev = chain;
1893 chain = chain->next;
4d779342 1894 }
6fb5fa3c
DB		 1895}
1896
1897
1898/* Delete a du or ud chain that leave or point to REF. */
1899
1900void
1901df_chain_unlink (struct df_ref *ref)
1902{
1903 struct df_link *chain = DF_REF_CHAIN (ref);
1904 while (chain)
4d779342 1905 {
6fb5fa3c
DB		 1906 struct df_link *next = chain->next;
1907 /* Delete the other side if it exists. */
1908 df_chain_unlink_1 (chain->ref, ref);
1909 pool_free (df_chain->block_pool, chain);
1910 chain = next;
4d779342 1911 }
6fb5fa3c 1912 DF_REF_CHAIN (ref) = NULL;
4d779342
DB		 1913}
1914
1915
6fb5fa3c
DB		 1916/* Copy the du or ud chain starting at FROM_REF and attach it to
1917 TO_REF. */
30cb87a0 1918
6fb5fa3c
DB		 1919void
1920df_chain_copy (struct df_ref *to_ref,
1921 struct df_link *from_ref)
30cb87a0 1922{
6fb5fa3c
DB		 1923 while (from_ref)
1924 {
1925 df_chain_create (to_ref, from_ref->ref);
1926 from_ref = from_ref->next;
1927 }
1928}
30cb87a0 1929
30cb87a0 1930
6fb5fa3c
DB		 1931/* Remove this problem from the stack of dataflow problems. */
1932
1933static void
1934df_chain_remove_problem (void)
1935{
1936 bitmap_iterator bi;
1937 unsigned int bb_index;
1938
1939 /* Wholesale destruction of the old chains. */
1940 if (df_chain->block_pool)
1941 free_alloc_pool (df_chain->block_pool);
30cb87a0 1942
6fb5fa3c
DB		 1943 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1944 {
1945 rtx insn;
1946 struct df_ref **def_rec;
1947 struct df_ref **use_rec;
1948 basic_block bb = BASIC_BLOCK (bb_index);
1949
1950 if (df_chain_problem_p (DF_DU_CHAIN))
1951 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1952 DF_REF_CHAIN (*def_rec) = NULL;
1953 if (df_chain_problem_p (DF_UD_CHAIN))
1954 for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1955 DF_REF_CHAIN (*use_rec) = NULL;
1956
1957 FOR_BB_INSNS (bb, insn)
30cb87a0 1958 {
6fb5fa3c
DB		 1959 unsigned int uid = INSN_UID (insn);
1960
1961 if (INSN_P (insn))
30cb87a0 1962 {
6fb5fa3c
DB		 1963 if (df_chain_problem_p (DF_DU_CHAIN))
1964 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1965 DF_REF_CHAIN (*def_rec) = NULL;
1966 if (df_chain_problem_p (DF_UD_CHAIN))
1967 {
1968 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1969 DF_REF_CHAIN (*use_rec) = NULL;
1970 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1971 DF_REF_CHAIN (*use_rec) = NULL;
1972 }
30cb87a0
KZ		 1973 }
1974 }
1975 }
6fb5fa3c
DB		 1976
1977 bitmap_clear (df_chain->out_of_date_transfer_functions);
1978 df_chain->block_pool = NULL;
30cb87a0
KZ		 1979}
1980
1981
6fb5fa3c 1982/* Remove the chain problem completely. */
30cb87a0 1983
6fb5fa3c
DB		 1984static void
1985df_chain_fully_remove_problem (void)
30cb87a0 1986{
6fb5fa3c
DB		 1987 df_chain_remove_problem ();
1988 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
1989 free (df_chain);
1990}
30cb87a0 1991
30cb87a0 1992
6fb5fa3c 1993/* Create def-use or use-def chains. */
30cb87a0 1994
6fb5fa3c
DB		 1995static void
1996df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1997{
1998 df_chain_remove_problem ();
1999 df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2000 sizeof (struct df_link), 50);
89a95777 2001 df_chain->optional_p = true;
30cb87a0
KZ		 2002}
2003
2004
2005/* Reset all of the chains when the set of basic blocks changes. */
2006
30cb87a0 2007static void
6fb5fa3c 2008df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
30cb87a0 2009{
6fb5fa3c 2010 df_chain_remove_problem ();
30cb87a0
KZ		 2011}
2012
2013
4d779342
DB		 2014/* Create the chains for a list of USEs. */
2015
2016static void
6fb5fa3c
DB		 2017df_chain_create_bb_process_use (bitmap local_rd,
2018 struct df_ref **use_rec,
4d779342
DB		 2019 enum df_ref_flags top_flag)
2020{
4d779342
DB		 2021 bitmap_iterator bi;
2022 unsigned int def_index;
2023
6fb5fa3c 2024 while (*use_rec)
4d779342 2025 {
6fb5fa3c 2026 struct df_ref *use = *use_rec;
4d779342 2027 unsigned int uregno = DF_REF_REGNO (use);
6fb5fa3c
DB		 2028 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2029 || (uregno >= FIRST_PSEUDO_REGISTER))
4d779342 2030 {
6fb5fa3c
DB		 2031 /* Do not want to go through this for an uninitialized var. */
2032 int count = DF_DEFS_COUNT (uregno);
2033 if (count)
4d779342 2034 {
6fb5fa3c 2035 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
4d779342 2036 {
6fb5fa3c
DB		 2037 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2038 unsigned int last_index = first_index + count - 1;
4d779342 2039
6fb5fa3c
DB		 2040 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2041 {
2042 struct df_ref *def;
2043 if (def_index > last_index)
2044 break;
2045
2046 def = DF_DEFS_GET (def_index);
2047 if (df_chain_problem_p (DF_DU_CHAIN))
2048 df_chain_create (def, use);
2049 if (df_chain_problem_p (DF_UD_CHAIN))
2050 df_chain_create (use, def);
2051 }
4d779342
DB		 2052 }
2053 }
2054 }
6fb5fa3c
DB		 2055
2056 use_rec++;
4d779342
DB		 2057 }
2058}
2059
4d779342
DB		 2060
2061/* Create chains from reaching defs bitmaps for basic block BB. */
6fb5fa3c 2062
4d779342 2063static void
6fb5fa3c 2064df_chain_create_bb (unsigned int bb_index)
4d779342
DB		 2065{
2066 basic_block bb = BASIC_BLOCK (bb_index);
6fb5fa3c 2067 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
4d779342
DB		 2068 rtx insn;
2069 bitmap cpy = BITMAP_ALLOC (NULL);
6fb5fa3c 2070 struct df_ref **def_rec;
4d779342
DB		 2071
2072 bitmap_copy (cpy, bb_info->in);
6fb5fa3c 2073 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
4d779342
DB		 2074
2075 /* Since we are going forwards, process the artificial uses first
2076 then the artificial defs second. */
2077
2078#ifdef EH_USES
2079 /* Create the chains for the artificial uses from the EH_USES at the
2080 beginning of the block. */
6fb5fa3c
DB		 2081
2082 /* Artificials are only hard regs. */
2083 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2084 df_chain_create_bb_process_use (cpy,
2085 df_get_artificial_uses (bb->index),
2086 DF_REF_AT_TOP);
4d779342
DB		 2087#endif
2088
6fb5fa3c
DB		 2089 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2090 {
2091 struct df_ref *def = *def_rec;
2092 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2093 {
2094 unsigned int dregno = DF_REF_REGNO (def);
2095 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2096 bitmap_clear_range (cpy,
2097 DF_DEFS_BEGIN (dregno),
2098 DF_DEFS_COUNT (dregno));
2099 bitmap_set_bit (cpy, DF_REF_ID (def));
2100 }
2101 }
4d779342
DB		 2102
2103 /* Process the regular instructions next. */
2104 FOR_BB_INSNS (bb, insn)
2105 {
6fb5fa3c 2106 struct df_ref **def_rec;
4d779342
DB		 2107 unsigned int uid = INSN_UID (insn);
2108
23249ac4 2109 if (!INSN_P (insn))
4d779342
DB		 2110 continue;
2111
2112 /* Now scan the uses and link them up with the defs that remain
2113 in the cpy vector. */
2114
6fb5fa3c
DB		 2115 df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2116
2117 if (df->changeable_flags & DF_EQ_NOTES)
2118 df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2119
4d779342
DB		 2120
2121 /* Since we are going forwards, process the defs second. This
2122 pass only changes the bits in cpy. */
6fb5fa3c 2123 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4d779342 2124 {
6fb5fa3c 2125 struct df_ref *def = *def_rec;
4d779342 2126 unsigned int dregno = DF_REF_REGNO (def);
6fb5fa3c
DB		 2127 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2128 || (dregno >= FIRST_PSEUDO_REGISTER))
2129 {
2130 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2131 bitmap_clear_range (cpy,
2132 DF_DEFS_BEGIN (dregno),
2133 DF_DEFS_COUNT (dregno));
2134 if (!(DF_REF_FLAGS (def)
2135 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
2136 bitmap_set_bit (cpy, DF_REF_ID (def));
2137 }
4d779342
DB		 2138 }
2139 }
2140
2141 /* Create the chains for the artificial uses of the hard registers
2142 at the end of the block. */
6fb5fa3c
DB		 2143 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2144 df_chain_create_bb_process_use (cpy,
2145 df_get_artificial_uses (bb->index),
2146 0);
2147
2148 BITMAP_FREE (cpy);
4d779342
DB		 2149}
2150
2151/* Create def-use chains from reaching use bitmaps for basic blocks
2152 in BLOCKS. */
2153
2154static void
6fb5fa3c 2155df_chain_finalize (bitmap all_blocks)
4d779342
DB		 2156{
2157 unsigned int bb_index;
2158 bitmap_iterator bi;
4d779342
DB		 2159
2160 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2161 {
6fb5fa3c 2162 df_chain_create_bb (bb_index);
4d779342
DB		 2163 }
2164}
2165
2166
2167/* Free all storage associated with the problem. */
2168
2169static void
6fb5fa3c 2170df_chain_free (void)
4d779342 2171{
6fb5fa3c
DB		 2172 free_alloc_pool (df_chain->block_pool);
2173 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2174 free (df_chain);
4d779342
DB		 2175}
2176
2177
2178/* Debugging info. */
2179
2180static void
6fb5fa3c 2181df_chain_top_dump (basic_block bb, FILE *file)
4d779342 2182{
6fb5fa3c 2183 if (df_chain_problem_p (DF_DU_CHAIN))
4d779342 2184 {
6fb5fa3c
DB		 2185 rtx insn;
2186 struct df_ref **def_rec = df_get_artificial_defs (bb->index);
2187 if (*def_rec)
4d779342 2188 {
6fb5fa3c
DB		 2189
2190 fprintf (file, ";; DU chains for artificial defs\n");
2191 while (*def_rec)
4d779342 2192 {
6fb5fa3c
DB		 2193 struct df_ref *def = *def_rec;
2194 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
23249ac4 2195 df_chain_dump (DF_REF_CHAIN (def), file);
4d779342 2196 fprintf (file, "\n");
6fb5fa3c
DB		 2197 def_rec++;
2198 }
2199 }
2200
2201 FOR_BB_INSNS (bb, insn)
2202 {
6fb5fa3c
DB		 2203 if (INSN_P (insn))
2204 {
50e94c7e
SB		 2205 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2206 def_rec = DF_INSN_INFO_DEFS (insn_info);
6fb5fa3c
DB		 2207 if (*def_rec)
2208 {
2209 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
50e94c7e 2210 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
6fb5fa3c
DB		 2211
2212 while (*def_rec)
2213 {
2214 struct df_ref *def = *def_rec;
2215 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2216 if (def->flags & DF_REF_READ_WRITE)
2217 fprintf (file, "read/write ");
2218 df_chain_dump (DF_REF_CHAIN (def), file);
2219 fprintf (file, "\n");
2220 def_rec++;
2221 }
2222 }
4d779342
DB		 2223 }
2224 }
2225 }
6fb5fa3c
DB		 2226}
2227
4d779342 2228
6fb5fa3c
DB		 2229static void
2230df_chain_bottom_dump (basic_block bb, FILE *file)
2231{
2232 if (df_chain_problem_p (DF_UD_CHAIN))
4d779342 2233 {
6fb5fa3c
DB		 2234 rtx insn;
2235 struct df_ref **use_rec = df_get_artificial_uses (bb->index);
2236
2237 if (*use_rec)
4d779342 2238 {
6fb5fa3c
DB		 2239 fprintf (file, ";; UD chains for artificial uses\n");
2240 while (*use_rec)
4d779342 2241 {
6fb5fa3c
DB		 2242 struct df_ref *use = *use_rec;
2243 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
23249ac4 2244 df_chain_dump (DF_REF_CHAIN (use), file);
4d779342 2245 fprintf (file, "\n");
6fb5fa3c
DB		 2246 use_rec++;
2247 }
2248 }
2249
2250 FOR_BB_INSNS (bb, insn)
2251 {
6fb5fa3c
DB		 2252 if (INSN_P (insn))
2253 {
50e94c7e
SB		 2254 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2255 struct df_ref **eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
2256 use_rec = DF_INSN_INFO_USES (insn_info);
6fb5fa3c
DB		 2257 if (*use_rec || *eq_use_rec)
2258 {
2259 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
50e94c7e 2260 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
6fb5fa3c
DB		 2261
2262 while (*use_rec)
2263 {
2264 struct df_ref *use = *use_rec;
2265 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2266 if (use->flags & DF_REF_READ_WRITE)
2267 fprintf (file, "read/write ");
2268 df_chain_dump (DF_REF_CHAIN (use), file);
2269 fprintf (file, "\n");
2270 use_rec++;
2271 }
2272 while (*eq_use_rec)
2273 {
2274 struct df_ref *use = *eq_use_rec;
2275 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2276 df_chain_dump (DF_REF_CHAIN (use), file);
2277 fprintf (file, "\n");
2278 eq_use_rec++;
2279 }
2280 }
4d779342
DB		 2281 }
2282 }
2283 }
2284}
2285
2286
2287static struct df_problem problem_CHAIN =
2288{
2289 DF_CHAIN, /* Problem id. */
2290 DF_NONE, /* Direction. */
2291 df_chain_alloc, /* Allocate the problem specific data. */
30cb87a0 2292 df_chain_reset, /* Reset global information. */
4d779342
DB		 2293 NULL, /* Free basic block info. */
2294 NULL, /* Local compute function. */
2295 NULL, /* Init the solution specific data. */
2296 NULL, /* Iterative solver. */
2297 NULL, /* Confluence operator 0. */
2298 NULL, /* Confluence operator n. */
2299 NULL, /* Transfer function. */
2300 df_chain_finalize, /* Finalize function. */
2301 df_chain_free, /* Free all of the problem information. */
6fb5fa3c
DB		 2302 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2303 NULL, /* Debugging. */
2304 df_chain_top_dump, /* Debugging start block. */
2305 df_chain_bottom_dump, /* Debugging end block. */
2306 NULL, /* Incremental solution verify start. */
6ed3da00 2307 NULL, /* Incremental solution verify end. */
6fb5fa3c 2308 &problem_RD, /* Dependent problem. */
89a95777
KZ		 2309 TV_DF_CHAIN, /* Timing variable. */
2310 false /* Reset blocks on dropping out of blocks_to_analyze. */
4d779342
DB		 2311};
2312
2313
2314/* Create a new DATAFLOW instance and add it to an existing instance
2315 of DF. The returned structure is what is used to get at the
2316 solution. */
2317
6fb5fa3c
DB		 2318void
2319df_chain_add_problem (enum df_chain_flags chain_flags)
4d779342 2320{
6fb5fa3c
DB		 2321 df_add_problem (&problem_CHAIN);
2322 df_chain->local_flags = (unsigned int)chain_flags;
2323 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
4d779342
DB		 2324}
2325
6fb5fa3c 2326#undef df_chain_problem_p
4d779342 2327
6fb5fa3c 2328\f
4d779342 2329/*----------------------------------------------------------------------------
cc806ac1
RS		 2330 BYTE LEVEL LIVE REGISTERS
2331
2332 Find the locations in the function where any use of a pseudo can
2333 reach in the backwards direction. In and out bitvectors are built
2334 for each basic block. There are two mapping functions,
2335 df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
fa10beec 2336 used to map regnos into bit vector positions.
cc806ac1
RS		 2337
2338 This problem differs from the regular df_lr function in the way
2339 that subregs, *_extracts and strict_low_parts are handled. In lr
2340 these are consider partial kills, here, the exact set of bytes is
2341 modeled. Note that any reg that has none of these operations is
2342 only modeled with a single bit since all operations access the
2343 entire register.
2344
2345 This problem is more brittle that the regular lr. It currently can
2346 be used in dce incrementally, but cannot be used in an environment
2347 where insns are created or modified. The problem is that the
2348 mapping of regnos to bitmap positions is relatively compact, in
2349 that if a pseudo does not do any of the byte wise operations, only
2350 one slot is allocated, rather than a slot for each byte. If insn
2351 are created, where a subreg is used for a reg that had no subregs,
2352 the mapping would be wrong. Likewise, there are no checks to see
2353 that new pseudos have been added. These issues could be addressed
2354 by adding a problem specific flag to not use the compact mapping,
2355 if there was a need to do so.
2356
2357 ----------------------------------------------------------------------------*/
2358
2359/* Private data used to verify the solution for this problem. */
2360struct df_byte_lr_problem_data
2361{
2362 /* Expanded versions of bitvectors used in lr. */
2363 bitmap invalidated_by_call;
2364 bitmap hardware_regs_used;
2365
2366 /* Indexed by regno, this is true if there are subregs, extracts or
2367 strict_low_parts for this regno. */
2368 bitmap needs_expansion;
2369
2370 /* The start position and len for each regno in the various bit
2371 vectors. */
2372 unsigned int* regno_start;
2373 unsigned int* regno_len;
2374 /* An obstack for the bitmaps we need for this problem. */
2375 bitmap_obstack byte_lr_bitmaps;
2376};
2377
2378
2379/* Get the starting location for REGNO in the df_byte_lr bitmaps. */
2380
2381int
2382df_byte_lr_get_regno_start (unsigned int regno)
2383{
2384 struct df_byte_lr_problem_data *problem_data
2385 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2386 return problem_data->regno_start[regno];
2387}
2388
2389
2390/* Get the len for REGNO in the df_byte_lr bitmaps. */
2391
2392int
2393df_byte_lr_get_regno_len (unsigned int regno)
2394{
2395 struct df_byte_lr_problem_data *problem_data
2396 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2397 return problem_data->regno_len[regno];
2398}
2399
2400
2401/* Set basic block info. */
2402
2403static void
2404df_byte_lr_set_bb_info (unsigned int index,
2405 struct df_byte_lr_bb_info *bb_info)
2406{
2407 gcc_assert (df_byte_lr);
2408 gcc_assert (index < df_byte_lr->block_info_size);
2409 df_byte_lr->block_info[index] = bb_info;
2410}
2411
2412
2413/* Free basic block info. */
2414
2415static void
2416df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2417 void *vbb_info)
2418{
2419 struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info;
2420 if (bb_info)
2421 {
2422 BITMAP_FREE (bb_info->use);
2423 BITMAP_FREE (bb_info->def);
2424 BITMAP_FREE (bb_info->in);
2425 BITMAP_FREE (bb_info->out);
2426 pool_free (df_byte_lr->block_pool, bb_info);
2427 }
2428}
2429
2430
2431/* Check all of the refs in REF_REC to see if any of them are
2432 extracts, subregs or strict_low_parts. */
2433
2434static void
2435df_byte_lr_check_regs (struct df_ref **ref_rec)
2436{
2437 struct df_byte_lr_problem_data *problem_data
2438 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2439
2440 for (; *ref_rec; ref_rec++)
2441 {
2442 struct df_ref *ref = *ref_rec;
2443 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT
2444 | DF_REF_ZERO_EXTRACT
2445 | DF_REF_STRICT_LOW_PART)
2446 || GET_CODE (DF_REF_REG (ref)) == SUBREG)
2447 bitmap_set_bit (problem_data->needs_expansion, DF_REF_REGNO (ref));
2448 }
2449}
2450
2451
2452/* Expand bitmap SRC which is indexed by regno to DEST which is indexed by
2453 regno_start and regno_len. */
2454
2455static void
2456df_byte_lr_expand_bitmap (bitmap dest, bitmap src)
2457{
2458 struct df_byte_lr_problem_data *problem_data
2459 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2460 bitmap_iterator bi;
2461 unsigned int i;
2462
2463 bitmap_clear (dest);
2464 EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi)
2465 {
2466 bitmap_set_range (dest, problem_data->regno_start[i],
2467 problem_data->regno_len[i]);
2468 }
2469}
2470
2471
2472/* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2473 not touched unless the block is new. */
2474
2475static void
2476df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2477{
2478 unsigned int bb_index;
2479 bitmap_iterator bi;
2480 basic_block bb;
2481 unsigned int regno;
2482 unsigned int index = 0;
2483 unsigned int max_reg = max_reg_num();
2484 struct df_byte_lr_problem_data *problem_data
2485 = problem_data = XNEW (struct df_byte_lr_problem_data);
2486
2487 df_byte_lr->problem_data = problem_data;
2488
2489 if (!df_byte_lr->block_pool)
2490 df_byte_lr->block_pool = create_alloc_pool ("df_byte_lr_block pool",
2491 sizeof (struct df_byte_lr_bb_info), 50);
2492
2493 df_grow_bb_info (df_byte_lr);
2494
2495 /* Create the mapping from regnos to slots. This does not change
2496 unless the problem is destroyed and recreated. In particular, if
2497 we end up deleting the only insn that used a subreg, we do not
2498 want to redo the mapping because this would invalidate everything
2499 else. */
2500
2501 bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps);
2502 problem_data->regno_start = XNEWVEC (unsigned int, max_reg);
2503 problem_data->regno_len = XNEWVEC (unsigned int, max_reg);
2504 problem_data->hardware_regs_used = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2505 problem_data->invalidated_by_call = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2506 problem_data->needs_expansion = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2507
2508 /* Discover which regno's use subregs, extracts or
2509 strict_low_parts. */
2510 FOR_EACH_BB (bb)
2511 {
2512 rtx insn;
2513 FOR_BB_INSNS (bb, insn)
2514 {
2515 if (INSN_P (insn))
2516 {
50e94c7e
SB		 2517 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2518 df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info));
2519 df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info));
cc806ac1
RS		 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{
60564289 3173 rtx curr = old;
6fb5fa3c
DB		 3174 rtx prev = NULL;
3175
60564289
KG		 3176 while (curr)
3177 if (XEXP (curr, 0) == reg)
6fb5fa3c
DB		 3178 {
3179 if (prev)
60564289 3180 XEXP (prev, 1) = XEXP (curr, 1);
6fb5fa3c 3181 else
60564289
KG		 3182 old = XEXP (curr, 1);
3183 XEXP (curr, 1) = REG_NOTES (insn);
3184 REG_NOTES (insn) = curr;
6fb5fa3c
DB		 3185 return old;
3186 }
3187 else
3188 {
60564289
KG		 3189 prev = curr;
3190 curr = XEXP (curr, 1);
6fb5fa3c
DB		 3191 }
3192
3193 /* Did not find the note. */
65c5f2a6 3194 add_reg_note (insn, note_type, reg);
6fb5fa3c
DB		 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.176865 seconds and 5 git commands to generate.