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