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