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