?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
PR C++/689
[official-gcc.git] / gcc / df.c
blobb23c2862b1707a891ee2b61f03be62091b7e166f
1 /* Dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
3 Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz,
4 mhayes@redhat.com)
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
21 02111-1307, USA.
22
23
24 OVERVIEW:
25
26 This file provides some dataflow routines for computing reaching defs,
27 upward exposed uses, live variables, def-use chains, and use-def
28 chains. The global dataflow is performed using simple iterative
29 methods with a worklist and could be sped up by ordering the blocks
30 with a depth first search order.
31
32 A `struct ref' data structure (ref) is allocated for every register
33 reference (def or use) and this records the insn and bb the ref is
34 found within. The refs are linked together in chains of uses and defs
35 for each insn and for each register. Each ref also has a chain field
36 that links all the use refs for a def or all the def refs for a use.
37 This is used to create use-def or def-use chains.
38
39
40 USAGE:
41
42 Here's an example of using the dataflow routines.
43
44 struct df *df;
45
46 df = df_init ();
47
48 df_analyse (df, 0, DF_ALL);
49
50 df_dump (df, DF_ALL, stderr);
51
52 df_finish (df);
53
54
55 df_init simply creates a poor man's object (df) that needs to be
56 passed to all the dataflow routines. df_finish destroys this
57 object and frees up any allocated memory. DF_ALL says to analyse
58 everything.
59
60 df_analyse performs the following:
61
62 1. Records defs and uses by scanning the insns in each basic block
63 or by scanning the insns queued by df_insn_modify.
64 2. Links defs and uses into insn-def and insn-use chains.
65 3. Links defs and uses into reg-def and reg-use chains.
66 4. Assigns LUIDs to each insn (for modified blocks).
67 5. Calculates local reaching definitions.
68 6. Calculates global reaching definitions.
69 7. Creates use-def chains.
70 8. Calculates local reaching uses (upwards exposed uses).
71 9. Calculates global reaching uses.
72 10. Creates def-use chains.
73 11. Calculates local live registers.
74 12. Calculates global live registers.
75 13. Calculates register lifetimes and determines local registers.
76
77
78 PHILOSOPHY:
79
80 Note that the dataflow information is not updated for every newly
81 deleted or created insn. If the dataflow information requires
82 updating then all the changed, new, or deleted insns needs to be
83 marked with df_insn_modify (or df_insns_modify) either directly or
84 indirectly (say through calling df_insn_delete). df_insn_modify
85 marks all the modified insns to get processed the next time df_analyse
86 is called.
87
88 Beware that tinkering with insns may invalidate the dataflow information.
89 The philosophy behind these routines is that once the dataflow
90 information has been gathered, the user should store what they require
91 before they tinker with any insn. Once a reg is replaced, for example,
92 then the reg-def/reg-use chains will point to the wrong place. Once a
93 whole lot of changes have been made, df_analyse can be called again
94 to update the dataflow information. Currently, this is not very smart
95 with regard to propagating changes to the dataflow so it should not
96 be called very often.
97
98
99 DATA STRUCTURES:
100
101 The basic object is a REF (reference) and this may either be a DEF
102 (definition) or a USE of a register.
103
104 These are linked into a variety of lists; namely reg-def, reg-use,
105 insn-def, insn-use, def-use, and use-def lists. For example,
106 the reg-def lists contain all the refs that define a given register
107 while the insn-use lists contain all the refs used by an insn.
108
109 Note that the reg-def and reg-use chains are generally short (except for the
110 hard registers) and thus it is much faster to search these chains
111 rather than searching the def or use bitmaps.
112
113 If the insns are in SSA form then the reg-def and use-def lists
114 should only contain the single defining ref.
115
116
117 TODO:
118
119 1) Incremental dataflow analysis.
120
121 Note that if a loop invariant insn is hoisted (or sunk), we do not
122 need to change the def-use or use-def chains. All we have to do is to
123 change the bb field for all the associated defs and uses and to
124 renumber the LUIDs for the original and new basic blocks of the insn.
125
126 When shadowing loop mems we create new uses and defs for new pseudos
127 so we do not affect the existing dataflow information.
128
129 My current strategy is to queue up all modified, created, or deleted
130 insns so when df_analyse is called we can easily determine all the new
131 or deleted refs. Currently the global dataflow information is
132 recomputed from scratch but this could be propagated more efficiently.
133
134 2) Reduced memory requirements.
135
136 We could operate a pool of ref structures. When a ref is deleted it
137 gets returned to the pool (say by linking on to a chain of free refs).
138 This will require a pair of bitmaps for defs and uses so that we can
139 tell which ones have been changed. Alternatively, we could
140 periodically squeeze the def and use tables and associated bitmaps and
141 renumber the def and use ids.
142
143 3) Ordering of reg-def and reg-use lists.
144
145 Should the first entry in the def list be the first def (within a BB)?
146 Similarly, should the first entry in the use list be the last use
147 (within a BB)?
148
149 4) Working with a sub-CFG.
150
151 Often the whole CFG does not need to be analyzed, for example,
152 when optimising a loop, only certain registers are of interest.
153 Perhaps there should be a bitmap argument to df_analyse to specify
154 which registers should be analyzed?
155
156
157 NOTES:
158
159 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
160 both a use and a def. These are both marked read/write to show that they
161 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
162 will generate a use of reg 42 followed by a def of reg 42 (both marked
163 read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
164 generates a use of reg 41 then a def of reg 41 (both marked read/write),
165 even though reg 41 is decremented before it is used for the memory
166 address in this second example.
167
168 A set to a REG inside a ZERO_EXTRACT, SIGN_EXTRACT, or SUBREG invokes
169 a read-modify write operation. We generate both a use and a def
170 and again mark them read/write.
171 */
172
173 #include "config.h"
174 #include "system.h"
175 #include "coretypes.h"
176 #include "tm.h"
177 #include "rtl.h"
178 #include "tm_p.h"
179 #include "insn-config.h"
180 #include "recog.h"
181 #include "function.h"
182 #include "regs.h"
183 #include "alloc-pool.h"
184 #include "hard-reg-set.h"
185 #include "basic-block.h"
186 #include "sbitmap.h"
187 #include "bitmap.h"
188 #include "df.h"
189 #include "fibheap.h"
190
191 #define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
192 do \
193 { \
194 unsigned int node_; \
195 EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, \
196 {(BB) = BASIC_BLOCK (node_); CODE;}); \
197 } \
198 while (0)
199
200 static alloc_pool df_ref_pool;
201 static alloc_pool df_link_pool;
202 static struct df *ddf;
203
204 static void df_reg_table_realloc PARAMS((struct df *, int));
205 static void df_insn_table_realloc PARAMS((struct df *, unsigned int));
206 static void df_bitmaps_alloc PARAMS((struct df *, int));
207 static void df_bitmaps_free PARAMS((struct df *, int));
208 static void df_free PARAMS((struct df *));
209 static void df_alloc PARAMS((struct df *, int));
210
211 static rtx df_reg_clobber_gen PARAMS((unsigned int));
212 static rtx df_reg_use_gen PARAMS((unsigned int));
213
214 static inline struct df_link *df_link_create PARAMS((struct ref *,
215 struct df_link *));
216 static struct df_link *df_ref_unlink PARAMS((struct df_link **, struct ref *));
217 static void df_def_unlink PARAMS((struct df *, struct ref *));
218 static void df_use_unlink PARAMS((struct df *, struct ref *));
219 static void df_insn_refs_unlink PARAMS ((struct df *, basic_block, rtx));
220 #if 0
221 static void df_bb_refs_unlink PARAMS ((struct df *, basic_block));
222 static void df_refs_unlink PARAMS ((struct df *, bitmap));
223 #endif
224
225 static struct ref *df_ref_create PARAMS((struct df *,
226 rtx, rtx *, rtx,
227 enum df_ref_type, enum df_ref_flags));
228 static void df_ref_record_1 PARAMS((struct df *, rtx, rtx *,
229 rtx, enum df_ref_type,
230 enum df_ref_flags));
231 static void df_ref_record PARAMS((struct df *, rtx, rtx *,
232 rtx, enum df_ref_type,
233 enum df_ref_flags));
234 static void df_def_record_1 PARAMS((struct df *, rtx, basic_block, rtx));
235 static void df_defs_record PARAMS((struct df *, rtx, basic_block, rtx));
236 static void df_uses_record PARAMS((struct df *, rtx *,
237 enum df_ref_type, basic_block, rtx,
238 enum df_ref_flags));
239 static void df_insn_refs_record PARAMS((struct df *, basic_block, rtx));
240 static void df_bb_refs_record PARAMS((struct df *, basic_block));
241 static void df_refs_record PARAMS((struct df *, bitmap));
242
243 static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block));
244 static void df_reg_def_chain_create PARAMS((struct df *, bitmap));
245 static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block));
246 static void df_reg_use_chain_create PARAMS((struct df *, bitmap));
247 static void df_bb_du_chain_create PARAMS((struct df *, basic_block, bitmap));
248 static void df_du_chain_create PARAMS((struct df *, bitmap));
249 static void df_bb_ud_chain_create PARAMS((struct df *, basic_block));
250 static void df_ud_chain_create PARAMS((struct df *, bitmap));
251 static void df_bb_rd_local_compute PARAMS((struct df *, basic_block));
252 static void df_rd_local_compute PARAMS((struct df *, bitmap));
253 static void df_bb_ru_local_compute PARAMS((struct df *, basic_block));
254 static void df_ru_local_compute PARAMS((struct df *, bitmap));
255 static void df_bb_lr_local_compute PARAMS((struct df *, basic_block));
256 static void df_lr_local_compute PARAMS((struct df *, bitmap));
257 static void df_bb_reg_info_compute PARAMS((struct df *, basic_block, bitmap));
258 static void df_reg_info_compute PARAMS((struct df *, bitmap));
259
260 static int df_bb_luids_set PARAMS((struct df *df, basic_block));
261 static int df_luids_set PARAMS((struct df *df, bitmap));
262
263 static int df_modified_p PARAMS ((struct df *, bitmap));
264 static int df_refs_queue PARAMS ((struct df *));
265 static int df_refs_process PARAMS ((struct df *));
266 static int df_bb_refs_update PARAMS ((struct df *, basic_block));
267 static int df_refs_update PARAMS ((struct df *));
268 static void df_analyse_1 PARAMS((struct df *, bitmap, int, int));
269
270 static void df_insns_modify PARAMS((struct df *, basic_block,
271 rtx, rtx));
272 static int df_rtx_mem_replace PARAMS ((rtx *, void *));
273 static int df_rtx_reg_replace PARAMS ((rtx *, void *));
274 void df_refs_reg_replace PARAMS ((struct df *, bitmap,
275 struct df_link *, rtx, rtx));
276
277 static int df_def_dominates_all_uses_p PARAMS((struct df *, struct ref *def));
278 static int df_def_dominates_uses_p PARAMS((struct df *,
279 struct ref *def, bitmap));
280 static struct ref *df_bb_regno_last_use_find PARAMS((struct df *, basic_block,
281 unsigned int));
282 static struct ref *df_bb_regno_first_def_find PARAMS((struct df *, basic_block,
283 unsigned int));
284 static struct ref *df_bb_insn_regno_last_use_find PARAMS((struct df *,
285 basic_block,
286 rtx, unsigned int));
287 static struct ref *df_bb_insn_regno_first_def_find PARAMS((struct df *,
288 basic_block,
289 rtx, unsigned int));
290
291 static void df_chain_dump PARAMS((struct df_link *, FILE *file));
292 static void df_chain_dump_regno PARAMS((struct df_link *, FILE *file));
293 static void df_regno_debug PARAMS ((struct df *, unsigned int, FILE *));
294 static void df_ref_debug PARAMS ((struct df *, struct ref *, FILE *));
295 static void df_rd_transfer_function PARAMS ((int, int *, bitmap, bitmap,
296 bitmap, bitmap, void *));
297 static void df_ru_transfer_function PARAMS ((int, int *, bitmap, bitmap,
298 bitmap, bitmap, void *));
299 static void df_lr_transfer_function PARAMS ((int, int *, bitmap, bitmap,
300 bitmap, bitmap, void *));
301 static void hybrid_search_bitmap PARAMS ((basic_block, bitmap *, bitmap *,
302 bitmap *, bitmap *, enum df_flow_dir,
303 enum df_confluence_op,
304 transfer_function_bitmap,
305 sbitmap, sbitmap, void *));
306 static void hybrid_search_sbitmap PARAMS ((basic_block, sbitmap *, sbitmap *,
307 sbitmap *, sbitmap *, enum df_flow_dir,
308 enum df_confluence_op,
309 transfer_function_sbitmap,
310 sbitmap, sbitmap, void *));
311
312 \f
313 /* Local memory allocation/deallocation routines. */
314
315
316 /* Increase the insn info table to have space for at least SIZE + 1
317 elements. */
318 static void
319 df_insn_table_realloc (df, size)
320 struct df *df;
321 unsigned int size;
322 {
323 size++;
324 if (size <= df->insn_size)
325 return;
326
327 /* Make the table a little larger than requested, so we do not need
328 to enlarge it so often. */
329 size += df->insn_size / 4;
330
331 df->insns = (struct insn_info *)
332 xrealloc (df->insns, size * sizeof (struct insn_info));
333
334 memset (df->insns + df->insn_size, 0,
335 (size - df->insn_size) * sizeof (struct insn_info));
336
337 df->insn_size = size;
338
339 if (! df->insns_modified)
340 {
341 df->insns_modified = BITMAP_XMALLOC ();
342 bitmap_zero (df->insns_modified);
343 }
344 }
345
346
347 /* Increase the reg info table by SIZE more elements. */
348 static void
349 df_reg_table_realloc (df, size)
350 struct df *df;
351 int size;
352 {
353 /* Make table 25 percent larger by default. */
354 if (! size)
355 size = df->reg_size / 4;
356
357 size += df->reg_size;
358 if (size < max_reg_num ())
359 size = max_reg_num ();
360
361 df->regs = (struct reg_info *)
362 xrealloc (df->regs, size * sizeof (struct reg_info));
363
364 /* Zero the new entries. */
365 memset (df->regs + df->reg_size, 0,
366 (size - df->reg_size) * sizeof (struct reg_info));
367
368 df->reg_size = size;
369 }
370
371
372 /* Allocate bitmaps for each basic block. */
373 static void
374 df_bitmaps_alloc (df, flags)
375 struct df *df;
376 int flags;
377 {
378 int dflags = 0;
379 basic_block bb;
380
381 /* Free the bitmaps if they need resizing. */
382 if ((flags & DF_LR) && df->n_regs < (unsigned int) max_reg_num ())
383 dflags |= DF_LR | DF_RU;
384 if ((flags & DF_RU) && df->n_uses < df->use_id)
385 dflags |= DF_RU;
386 if ((flags & DF_RD) && df->n_defs < df->def_id)
387 dflags |= DF_RD;
388
389 if (dflags)
390 df_bitmaps_free (df, dflags);
391
392 df->n_defs = df->def_id;
393 df->n_uses = df->use_id;
394
395 FOR_EACH_BB (bb)
396 {
397 struct bb_info *bb_info = DF_BB_INFO (df, bb);
398
399 if (flags & DF_RD && ! bb_info->rd_in)
400 {
401 /* Allocate bitmaps for reaching definitions. */
402 bb_info->rd_kill = BITMAP_XMALLOC ();
403 bitmap_zero (bb_info->rd_kill);
404 bb_info->rd_gen = BITMAP_XMALLOC ();
405 bitmap_zero (bb_info->rd_gen);
406 bb_info->rd_in = BITMAP_XMALLOC ();
407 bb_info->rd_out = BITMAP_XMALLOC ();
408 bb_info->rd_valid = 0;
409 }
410
411 if (flags & DF_RU && ! bb_info->ru_in)
412 {
413 /* Allocate bitmaps for upward exposed uses. */
414 bb_info->ru_kill = BITMAP_XMALLOC ();
415 bitmap_zero (bb_info->ru_kill);
416 /* Note the lack of symmetry. */
417 bb_info->ru_gen = BITMAP_XMALLOC ();
418 bitmap_zero (bb_info->ru_gen);
419 bb_info->ru_in = BITMAP_XMALLOC ();
420 bb_info->ru_out = BITMAP_XMALLOC ();
421 bb_info->ru_valid = 0;
422 }
423
424 if (flags & DF_LR && ! bb_info->lr_in)
425 {
426 /* Allocate bitmaps for live variables. */
427 bb_info->lr_def = BITMAP_XMALLOC ();
428 bitmap_zero (bb_info->lr_def);
429 bb_info->lr_use = BITMAP_XMALLOC ();
430 bitmap_zero (bb_info->lr_use);
431 bb_info->lr_in = BITMAP_XMALLOC ();
432 bb_info->lr_out = BITMAP_XMALLOC ();
433 bb_info->lr_valid = 0;
434 }
435 }
436 }
437
438
439 /* Free bitmaps for each basic block. */
440 static void
441 df_bitmaps_free (df, flags)
442 struct df *df ATTRIBUTE_UNUSED;
443 int flags;
444 {
445 basic_block bb;
446
447 FOR_EACH_BB (bb)
448 {
449 struct bb_info *bb_info = DF_BB_INFO (df, bb);
450
451 if (!bb_info)
452 continue;
453
454 if ((flags & DF_RD) && bb_info->rd_in)
455 {
456 /* Free bitmaps for reaching definitions. */
457 BITMAP_XFREE (bb_info->rd_kill);
458 bb_info->rd_kill = NULL;
459 BITMAP_XFREE (bb_info->rd_gen);
460 bb_info->rd_gen = NULL;
461 BITMAP_XFREE (bb_info->rd_in);
462 bb_info->rd_in = NULL;
463 BITMAP_XFREE (bb_info->rd_out);
464 bb_info->rd_out = NULL;
465 }
466
467 if ((flags & DF_RU) && bb_info->ru_in)
468 {
469 /* Free bitmaps for upward exposed uses. */
470 BITMAP_XFREE (bb_info->ru_kill);
471 bb_info->ru_kill = NULL;
472 BITMAP_XFREE (bb_info->ru_gen);
473 bb_info->ru_gen = NULL;
474 BITMAP_XFREE (bb_info->ru_in);
475 bb_info->ru_in = NULL;
476 BITMAP_XFREE (bb_info->ru_out);
477 bb_info->ru_out = NULL;
478 }
479
480 if ((flags & DF_LR) && bb_info->lr_in)
481 {
482 /* Free bitmaps for live variables. */
483 BITMAP_XFREE (bb_info->lr_def);
484 bb_info->lr_def = NULL;
485 BITMAP_XFREE (bb_info->lr_use);
486 bb_info->lr_use = NULL;
487 BITMAP_XFREE (bb_info->lr_in);
488 bb_info->lr_in = NULL;
489 BITMAP_XFREE (bb_info->lr_out);
490 bb_info->lr_out = NULL;
491 }
492 }
493 df->flags &= ~(flags & (DF_RD | DF_RU | DF_LR));
494 }
495
496
497 /* Allocate and initialize dataflow memory. */
498 static void
499 df_alloc (df, n_regs)
500 struct df *df;
501 int n_regs;
502 {
503 int n_insns;
504 basic_block bb;
505
506 df_link_pool = create_alloc_pool ("df_link pool", sizeof (struct df_link),
507 100);
508 df_ref_pool = create_alloc_pool ("df_ref pool", sizeof (struct ref), 100);
509
510 /* Perhaps we should use LUIDs to save memory for the insn_refs
511 table. This is only a small saving; a few pointers. */
512 n_insns = get_max_uid () + 1;
513
514 df->def_id = 0;
515 df->n_defs = 0;
516 /* Approximate number of defs by number of insns. */
517 df->def_size = n_insns;
518 df->defs = xmalloc (df->def_size * sizeof (*df->defs));
519
520 df->use_id = 0;
521 df->n_uses = 0;
522 /* Approximate number of uses by twice number of insns. */
523 df->use_size = n_insns * 2;
524 df->uses = xmalloc (df->use_size * sizeof (*df->uses));
525
526 df->n_regs = n_regs;
527 df->n_bbs = last_basic_block;
528
529 /* Allocate temporary working array used during local dataflow analysis. */
530 df->reg_def_last = xmalloc (df->n_regs * sizeof (struct ref *));
531
532 df_insn_table_realloc (df, n_insns);
533
534 df_reg_table_realloc (df, df->n_regs);
535
536 df->bbs_modified = BITMAP_XMALLOC ();
537 bitmap_zero (df->bbs_modified);
538
539 df->flags = 0;
540
541 df->bbs = xcalloc (last_basic_block, sizeof (struct bb_info));
542
543 df->all_blocks = BITMAP_XMALLOC ();
544 FOR_EACH_BB (bb)
545 bitmap_set_bit (df->all_blocks, bb->index);
546 }
547
548
549 /* Free all the dataflow info. */
550 static void
551 df_free (df)
552 struct df *df;
553 {
554 df_bitmaps_free (df, DF_ALL);
555
556 if (df->bbs)
557 free (df->bbs);
558 df->bbs = 0;
559
560 if (df->insns)
561 free (df->insns);
562 df->insns = 0;
563 df->insn_size = 0;
564
565 if (df->defs)
566 free (df->defs);
567 df->defs = 0;
568 df->def_size = 0;
569 df->def_id = 0;
570
571 if (df->uses)
572 free (df->uses);
573 df->uses = 0;
574 df->use_size = 0;
575 df->use_id = 0;
576
577 if (df->regs)
578 free (df->regs);
579 df->regs = 0;
580 df->reg_size = 0;
581
582 if (df->bbs_modified)
583 BITMAP_XFREE (df->bbs_modified);
584 df->bbs_modified = 0;
585
586 if (df->insns_modified)
587 BITMAP_XFREE (df->insns_modified);
588 df->insns_modified = 0;
589
590 BITMAP_XFREE (df->all_blocks);
591 df->all_blocks = 0;
592
593 free_alloc_pool (df_ref_pool);
594 free_alloc_pool (df_link_pool);
595
596 }
597 \f
598 /* Local miscellaneous routines. */
599
600 /* Return a USE for register REGNO. */
601 static rtx df_reg_use_gen (regno)
602 unsigned int regno;
603 {
604 rtx reg;
605 rtx use;
606
607 reg = regno_reg_rtx[regno];
608
609 use = gen_rtx_USE (GET_MODE (reg), reg);
610 return use;
611 }
612
613
614 /* Return a CLOBBER for register REGNO. */
615 static rtx df_reg_clobber_gen (regno)
616 unsigned int regno;
617 {
618 rtx reg;
619 rtx use;
620
621 reg = regno_reg_rtx[regno];
622
623 use = gen_rtx_CLOBBER (GET_MODE (reg), reg);
624 return use;
625 }
626 \f
627 /* Local chain manipulation routines. */
628
629 /* Create a link in a def-use or use-def chain. */
630 static inline struct df_link *
631 df_link_create (ref, next)
632 struct ref *ref;
633 struct df_link *next;
634 {
635 struct df_link *link;
636
637 link = pool_alloc (df_link_pool);
638 link->next = next;
639 link->ref = ref;
640 return link;
641 }
642
643
644 /* Add REF to chain head pointed to by PHEAD. */
645 static struct df_link *
646 df_ref_unlink (phead, ref)
647 struct df_link **phead;
648 struct ref *ref;
649 {
650 struct df_link *link = *phead;
651
652 if (link)
653 {
654 if (! link->next)
655 {
656 /* Only a single ref. It must be the one we want.
657 If not, the def-use and use-def chains are likely to
658 be inconsistent. */
659 if (link->ref != ref)
660 abort ();
661 /* Now have an empty chain. */
662 *phead = NULL;
663 }
664 else
665 {
666 /* Multiple refs. One of them must be us. */
667 if (link->ref == ref)
668 *phead = link->next;
669 else
670 {
671 /* Follow chain. */
672 for (; link->next; link = link->next)
673 {
674 if (link->next->ref == ref)
675 {
676 /* Unlink from list. */
677 link->next = link->next->next;
678 return link->next;
679 }
680 }
681 }
682 }
683 }
684 return link;
685 }
686
687
688 /* Unlink REF from all def-use/use-def chains, etc. */
689 int
690 df_ref_remove (df, ref)
691 struct df *df;
692 struct ref *ref;
693 {
694 if (DF_REF_REG_DEF_P (ref))
695 {
696 df_def_unlink (df, ref);
697 df_ref_unlink (&df->insns[DF_REF_INSN_UID (ref)].defs, ref);
698 }
699 else
700 {
701 df_use_unlink (df, ref);
702 df_ref_unlink (&df->insns[DF_REF_INSN_UID (ref)].uses, ref);
703 }
704 return 1;
705 }
706
707
708 /* Unlink DEF from use-def and reg-def chains. */
709 static void
710 df_def_unlink (df, def)
711 struct df *df ATTRIBUTE_UNUSED;
712 struct ref *def;
713 {
714 struct df_link *du_link;
715 unsigned int dregno = DF_REF_REGNO (def);
716
717 /* Follow def-use chain to find all the uses of this def. */
718 for (du_link = DF_REF_CHAIN (def); du_link; du_link = du_link->next)
719 {
720 struct ref *use = du_link->ref;
721
722 /* Unlink this def from the use-def chain. */
723 df_ref_unlink (&DF_REF_CHAIN (use), def);
724 }
725 DF_REF_CHAIN (def) = 0;
726
727 /* Unlink def from reg-def chain. */
728 df_ref_unlink (&df->regs[dregno].defs, def);
729
730 df->defs[DF_REF_ID (def)] = 0;
731 }
732
733
734 /* Unlink use from def-use and reg-use chains. */
735 static void
736 df_use_unlink (df, use)
737 struct df *df ATTRIBUTE_UNUSED;
738 struct ref *use;
739 {
740 struct df_link *ud_link;
741 unsigned int uregno = DF_REF_REGNO (use);
742
743 /* Follow use-def chain to find all the defs of this use. */
744 for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
745 {
746 struct ref *def = ud_link->ref;
747
748 /* Unlink this use from the def-use chain. */
749 df_ref_unlink (&DF_REF_CHAIN (def), use);
750 }
751 DF_REF_CHAIN (use) = 0;
752
753 /* Unlink use from reg-use chain. */
754 df_ref_unlink (&df->regs[uregno].uses, use);
755
756 df->uses[DF_REF_ID (use)] = 0;
757 }
758 \f
759 /* Local routines for recording refs. */
760
761
762 /* Create a new ref of type DF_REF_TYPE for register REG at address
763 LOC within INSN of BB. */
764 static struct ref *
765 df_ref_create (df, reg, loc, insn, ref_type, ref_flags)
766 struct df *df;
767 rtx reg;
768 rtx *loc;
769 rtx insn;
770 enum df_ref_type ref_type;
771 enum df_ref_flags ref_flags;
772 {
773 struct ref *this_ref;
774
775 this_ref = pool_alloc (df_ref_pool);
776 DF_REF_REG (this_ref) = reg;
777 DF_REF_LOC (this_ref) = loc;
778 DF_REF_INSN (this_ref) = insn;
779 DF_REF_CHAIN (this_ref) = 0;
780 DF_REF_TYPE (this_ref) = ref_type;
781 DF_REF_FLAGS (this_ref) = ref_flags;
782
783 if (ref_type == DF_REF_REG_DEF)
784 {
785 if (df->def_id >= df->def_size)
786 {
787 /* Make table 25 percent larger. */
788 df->def_size += (df->def_size / 4);
789 df->defs = xrealloc (df->defs,
790 df->def_size * sizeof (*df->defs));
791 }
792 DF_REF_ID (this_ref) = df->def_id;
793 df->defs[df->def_id++] = this_ref;
794 }
795 else
796 {
797 if (df->use_id >= df->use_size)
798 {
799 /* Make table 25 percent larger. */
800 df->use_size += (df->use_size / 4);
801 df->uses = xrealloc (df->uses,
802 df->use_size * sizeof (*df->uses));
803 }
804 DF_REF_ID (this_ref) = df->use_id;
805 df->uses[df->use_id++] = this_ref;
806 }
807 return this_ref;
808 }
809
810
811 /* Create a new reference of type DF_REF_TYPE for a single register REG,
812 used inside the LOC rtx of INSN. */
813 static void
814 df_ref_record_1 (df, reg, loc, insn, ref_type, ref_flags)
815 struct df *df;
816 rtx reg;
817 rtx *loc;
818 rtx insn;
819 enum df_ref_type ref_type;
820 enum df_ref_flags ref_flags;
821 {
822 df_ref_create (df, reg, loc, insn, ref_type, ref_flags);
823 }
824
825
826 /* Create new references of type DF_REF_TYPE for each part of register REG
827 at address LOC within INSN of BB. */
828 static void
829 df_ref_record (df, reg, loc, insn, ref_type, ref_flags)
830 struct df *df;
831 rtx reg;
832 rtx *loc;
833 rtx insn;
834 enum df_ref_type ref_type;
835 enum df_ref_flags ref_flags;
836 {
837 unsigned int regno;
838
839 if (GET_CODE (reg) != REG && GET_CODE (reg) != SUBREG)
840 abort ();
841
842 /* For the reg allocator we are interested in some SUBREG rtx's, but not
843 all. Notably only those representing a word extraction from a multi-word
844 reg. As written in the docu those should have the form
845 (subreg:SI (reg:M A) N), with size(SImode) > size(Mmode).
846 XXX Is that true? We could also use the global word_mode variable. */
847 if (GET_CODE (reg) == SUBREG
848 && (GET_MODE_SIZE (GET_MODE (reg)) < GET_MODE_SIZE (word_mode)
849 || GET_MODE_SIZE (GET_MODE (reg))
850 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (reg)))))
851 {
852 loc = &SUBREG_REG (reg);
853 reg = *loc;
854 ref_flags |= DF_REF_STRIPPED;
855 }
856
857 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
858 if (regno < FIRST_PSEUDO_REGISTER)
859 {
860 int i;
861 int endregno;
862
863 if (! (df->flags & DF_HARD_REGS))
864 return;
865
866 /* GET_MODE (reg) is correct here. We do not want to go into a SUBREG
867 for the mode, because we only want to add references to regs, which
868 are really referenced. E.g., a (subreg:SI (reg:DI 0) 0) does _not_
869 reference the whole reg 0 in DI mode (which would also include
870 reg 1, at least, if 0 and 1 are SImode registers). */
871 endregno = HARD_REGNO_NREGS (regno, GET_MODE (reg));
872 if (GET_CODE (reg) == SUBREG)
873 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
874 SUBREG_BYTE (reg), GET_MODE (reg));
875 endregno += regno;
876
877 for (i = regno; i < endregno; i++)
878 df_ref_record_1 (df, regno_reg_rtx[i],
879 loc, insn, ref_type, ref_flags);
880 }
881 else
882 {
883 df_ref_record_1 (df, reg, loc, insn, ref_type, ref_flags);
884 }
885 }
886
887
888 /* Return non-zero if writes to paradoxical SUBREGs, or SUBREGs which
889 are too narrow, are read-modify-write. */
890 bool
891 read_modify_subreg_p (x)
892 rtx x;
893 {
894 unsigned int isize, osize;
895 if (GET_CODE (x) != SUBREG)
896 return false;
897 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
898 osize = GET_MODE_SIZE (GET_MODE (x));
899 /* Paradoxical subreg writes don't leave a trace of the old content. */
900 return (isize > osize && isize > UNITS_PER_WORD);
901 }
902
903
904 /* Process all the registers defined in the rtx, X. */
905 static void
906 df_def_record_1 (df, x, bb, insn)
907 struct df *df;
908 rtx x;
909 basic_block bb;
910 rtx insn;
911 {
912 rtx *loc;
913 rtx dst;
914 enum df_ref_flags flags = 0;
915
916 /* We may recursivly call ourselves on EXPR_LIST when dealing with PARALLEL
917 construct. */
918 if (GET_CODE (x) == EXPR_LIST || GET_CODE (x) == CLOBBER)
919 loc = &XEXP (x, 0);
920 else
921 loc = &SET_DEST (x);
922 dst = *loc;
923
924 /* Some targets place small structures in registers for
925 return values of functions. */
926 if (GET_CODE (dst) == PARALLEL && GET_MODE (dst) == BLKmode)
927 {
928 int i;
929
930 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
931 {
932 rtx temp = XVECEXP (dst, 0, i);
933 if (GET_CODE (temp) == EXPR_LIST || GET_CODE (temp) == CLOBBER
934 || GET_CODE (temp) == SET)
935 df_def_record_1 (df, temp, bb, insn);
936 }
937 return;
938 }
939
940 #ifdef CLASS_CANNOT_CHANGE_MODE
941 if (GET_CODE (dst) == SUBREG
942 && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (dst),
943 GET_MODE (SUBREG_REG (dst))))
944 flags |= DF_REF_MODE_CHANGE;
945 #endif
946
947 /* Maybe, we should flag the use of STRICT_LOW_PART somehow. It might
948 be handy for the reg allocator. */
949 while (GET_CODE (dst) == STRICT_LOW_PART
950 || GET_CODE (dst) == ZERO_EXTRACT
951 || GET_CODE (dst) == SIGN_EXTRACT
952 || ((df->flags & DF_FOR_REGALLOC) == 0
953 && read_modify_subreg_p (dst)))
954 {
955 /* Strict low part always contains SUBREG, but we do not want to make
956 it appear outside, as whole register is always considered. */
957 if (GET_CODE (dst) == STRICT_LOW_PART)
958 {
959 loc = &XEXP (dst, 0);
960 dst = *loc;
961 }
962 #ifdef CLASS_CANNOT_CHANGE_MODE
963 if (GET_CODE (dst) == SUBREG
964 && CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (dst),
965 GET_MODE (SUBREG_REG (dst))))
966 flags |= DF_REF_MODE_CHANGE;
967 #endif
968 loc = &XEXP (dst, 0);
969 dst = *loc;
970 flags |= DF_REF_READ_WRITE;
971 }
972
973 if (GET_CODE (dst) == REG
974 || (GET_CODE (dst) == SUBREG && GET_CODE (SUBREG_REG (dst)) == REG))
975 df_ref_record (df, dst, loc, insn, DF_REF_REG_DEF, flags);
976 }
977
978
979 /* Process all the registers defined in the pattern rtx, X. */
980 static void
981 df_defs_record (df, x, bb, insn)
982 struct df *df;
983 rtx x;
984 basic_block bb;
985 rtx insn;
986 {
987 RTX_CODE code = GET_CODE (x);
988
989 if (code == SET || code == CLOBBER)
990 {
991 /* Mark the single def within the pattern. */
992 df_def_record_1 (df, x, bb, insn);
993 }
994 else if (code == PARALLEL)
995 {
996 int i;
997
998 /* Mark the multiple defs within the pattern. */
999 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1000 {
1001 code = GET_CODE (XVECEXP (x, 0, i));
1002 if (code == SET || code == CLOBBER)
1003 df_def_record_1 (df, XVECEXP (x, 0, i), bb, insn);
1004 }
1005 }
1006 }
1007
1008
1009 /* Process all the registers used in the rtx at address LOC. */
1010 static void
1011 df_uses_record (df, loc, ref_type, bb, insn, flags)
1012 struct df *df;
1013 rtx *loc;
1014 enum df_ref_type ref_type;
1015 basic_block bb;
1016 rtx insn;
1017 enum df_ref_flags flags;
1018 {
1019 RTX_CODE code;
1020 rtx x;
1021 retry:
1022 x = *loc;
1023 if (!x)
1024 return;
1025 code = GET_CODE (x);
1026 switch (code)
1027 {
1028 case LABEL_REF:
1029 case SYMBOL_REF:
1030 case CONST_INT:
1031 case CONST:
1032 case CONST_DOUBLE:
1033 case CONST_VECTOR:
1034 case PC:
1035 case CC0:
1036 case ADDR_VEC:
1037 case ADDR_DIFF_VEC:
1038 return;
1039
1040 case CLOBBER:
1041 /* If we are clobbering a MEM, mark any registers inside the address
1042 as being used. */
1043 if (GET_CODE (XEXP (x, 0)) == MEM)
1044 df_uses_record (df, &XEXP (XEXP (x, 0), 0),
1045 DF_REF_REG_MEM_STORE, bb, insn, flags);
1046
1047 /* If we're clobbering a REG then we have a def so ignore. */
1048 return;
1049
1050 case MEM:
1051 df_uses_record (df, &XEXP (x, 0), DF_REF_REG_MEM_LOAD, bb, insn, flags);
1052 return;
1053
1054 case SUBREG:
1055 /* While we're here, optimize this case. */
1056
1057 /* In case the SUBREG is not of a REG, do not optimize. */
1058 if (GET_CODE (SUBREG_REG (x)) != REG)
1059 {
1060 loc = &SUBREG_REG (x);
1061 df_uses_record (df, loc, ref_type, bb, insn, flags);
1062 return;
1063 }
1064 #ifdef CLASS_CANNOT_CHANGE_MODE
1065 if (CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (x),
1066 GET_MODE (SUBREG_REG (x))))
1067 flags |= DF_REF_MODE_CHANGE;
1068 #endif
1069
1070 /* ... Fall through ... */
1071
1072 case REG:
1073 /* See a REG (or SUBREG) other than being set. */
1074 df_ref_record (df, x, loc, insn, ref_type, flags);
1075 return;
1076
1077 case SET:
1078 {
1079 rtx dst = SET_DEST (x);
1080
1081 df_uses_record (df, &SET_SRC (x), DF_REF_REG_USE, bb, insn, 0);
1082
1083 switch (GET_CODE (dst))
1084 {
1085 enum df_ref_flags use_flags;
1086 case SUBREG:
1087 if ((df->flags & DF_FOR_REGALLOC) == 0
1088 && read_modify_subreg_p (dst))
1089 {
1090 use_flags = DF_REF_READ_WRITE;
1091 #ifdef CLASS_CANNOT_CHANGE_MODE
1092 if (CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (dst),
1093 GET_MODE (SUBREG_REG (dst))))
1094 use_flags |= DF_REF_MODE_CHANGE;
1095 #endif
1096 df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
1097 insn, use_flags);
1098 break;
1099 }
1100 /* ... FALLTHRU ... */
1101 case REG:
1102 case PARALLEL:
1103 case PC:
1104 case CC0:
1105 break;
1106 case MEM:
1107 df_uses_record (df, &XEXP (dst, 0),
1108 DF_REF_REG_MEM_STORE,
1109 bb, insn, 0);
1110 break;
1111 case STRICT_LOW_PART:
1112 /* A strict_low_part uses the whole REG and not just the SUBREG. */
1113 dst = XEXP (dst, 0);
1114 if (GET_CODE (dst) != SUBREG)
1115 abort ();
1116 use_flags = DF_REF_READ_WRITE;
1117 #ifdef CLASS_CANNOT_CHANGE_MODE
1118 if (CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (dst),
1119 GET_MODE (SUBREG_REG (dst))))
1120 use_flags |= DF_REF_MODE_CHANGE;
1121 #endif
1122 df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
1123 insn, use_flags);
1124 break;
1125 case ZERO_EXTRACT:
1126 case SIGN_EXTRACT:
1127 df_uses_record (df, &XEXP (dst, 0), DF_REF_REG_USE, bb, insn,
1128 DF_REF_READ_WRITE);
1129 df_uses_record (df, &XEXP (dst, 1), DF_REF_REG_USE, bb, insn, 0);
1130 df_uses_record (df, &XEXP (dst, 2), DF_REF_REG_USE, bb, insn, 0);
1131 dst = XEXP (dst, 0);
1132 break;
1133 default:
1134 abort ();
1135 }
1136 return;
1137 }
1138
1139 case RETURN:
1140 break;
1141
1142 case ASM_OPERANDS:
1143 case UNSPEC_VOLATILE:
1144 case TRAP_IF:
1145 case ASM_INPUT:
1146 {
1147 /* Traditional and volatile asm instructions must be considered to use
1148 and clobber all hard registers, all pseudo-registers and all of
1149 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
1150
1151 Consider for instance a volatile asm that changes the fpu rounding
1152 mode. An insn should not be moved across this even if it only uses
1153 pseudo-regs because it might give an incorrectly rounded result.
1154
1155 For now, just mark any regs we can find in ASM_OPERANDS as
1156 used. */
1157
1158 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1159 We can not just fall through here since then we would be confused
1160 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1161 traditional asms unlike their normal usage. */
1162 if (code == ASM_OPERANDS)
1163 {
1164 int j;
1165
1166 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1167 df_uses_record (df, &ASM_OPERANDS_INPUT (x, j),
1168 DF_REF_REG_USE, bb, insn, 0);
1169 return;
1170 }
1171 break;
1172 }
1173
1174 case PRE_DEC:
1175 case POST_DEC:
1176 case PRE_INC:
1177 case POST_INC:
1178 case PRE_MODIFY:
1179 case POST_MODIFY:
1180 /* Catch the def of the register being modified. */
1181 df_ref_record (df, XEXP (x, 0), &XEXP (x, 0), insn, DF_REF_REG_DEF, DF_REF_READ_WRITE);
1182
1183 /* ... Fall through to handle uses ... */
1184
1185 default:
1186 break;
1187 }
1188
1189 /* Recursively scan the operands of this expression. */
1190 {
1191 const char *fmt = GET_RTX_FORMAT (code);
1192 int i;
1193
1194 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1195 {
1196 if (fmt[i] == 'e')
1197 {
1198 /* Tail recursive case: save a function call level. */
1199 if (i == 0)
1200 {
1201 loc = &XEXP (x, 0);
1202 goto retry;
1203 }
1204 df_uses_record (df, &XEXP (x, i), ref_type, bb, insn, flags);
1205 }
1206 else if (fmt[i] == 'E')
1207 {
1208 int j;
1209 for (j = 0; j < XVECLEN (x, i); j++)
1210 df_uses_record (df, &XVECEXP (x, i, j), ref_type,
1211 bb, insn, flags);
1212 }
1213 }
1214 }
1215 }
1216
1217
1218 /* Record all the df within INSN of basic block BB. */
1219 static void
1220 df_insn_refs_record (df, bb, insn)
1221 struct df *df;
1222 basic_block bb;
1223 rtx insn;
1224 {
1225 int i;
1226
1227 if (INSN_P (insn))
1228 {
1229 rtx note;
1230
1231 /* Record register defs */
1232 df_defs_record (df, PATTERN (insn), bb, insn);
1233
1234 if (df->flags & DF_EQUIV_NOTES)
1235 for (note = REG_NOTES (insn); note;
1236 note = XEXP (note, 1))
1237 {
1238 switch (REG_NOTE_KIND (note))
1239 {
1240 case REG_EQUIV:
1241 case REG_EQUAL:
1242 df_uses_record (df, &XEXP (note, 0), DF_REF_REG_USE,
1243 bb, insn, 0);
1244 default:
1245 break;
1246 }
1247 }
1248
1249 if (GET_CODE (insn) == CALL_INSN)
1250 {
1251 rtx note;
1252 rtx x;
1253
1254 /* Record the registers used to pass arguments. */
1255 for (note = CALL_INSN_FUNCTION_USAGE (insn); note;
1256 note = XEXP (note, 1))
1257 {
1258 if (GET_CODE (XEXP (note, 0)) == USE)
1259 df_uses_record (df, &XEXP (XEXP (note, 0), 0), DF_REF_REG_USE,
1260 bb, insn, 0);
1261 }
1262
1263 /* The stack ptr is used (honorarily) by a CALL insn. */
1264 x = df_reg_use_gen (STACK_POINTER_REGNUM);
1265 df_uses_record (df, &XEXP (x, 0), DF_REF_REG_USE, bb, insn, 0);
1266
1267 if (df->flags & DF_HARD_REGS)
1268 {
1269 /* Calls may also reference any of the global registers,
1270 so they are recorded as used. */
1271 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1272 if (global_regs[i])
1273 {
1274 x = df_reg_use_gen (i);
1275 df_uses_record (df, &SET_DEST (x),
1276 DF_REF_REG_USE, bb, insn, 0);
1277 }
1278 }
1279 }
1280
1281 /* Record the register uses. */
1282 df_uses_record (df, &PATTERN (insn),
1283 DF_REF_REG_USE, bb, insn, 0);
1284
1285 if (GET_CODE (insn) == CALL_INSN)
1286 {
1287 rtx note;
1288
1289 if (df->flags & DF_HARD_REGS)
1290 {
1291 /* Kill all registers invalidated by a call. */
1292 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1293 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1294 {
1295 rtx reg_clob = df_reg_clobber_gen (i);
1296 df_defs_record (df, reg_clob, bb, insn);
1297 }
1298 }
1299
1300 /* There may be extra registers to be clobbered. */
1301 for (note = CALL_INSN_FUNCTION_USAGE (insn);
1302 note;
1303 note = XEXP (note, 1))
1304 if (GET_CODE (XEXP (note, 0)) == CLOBBER)
1305 df_defs_record (df, XEXP (note, 0), bb, insn);
1306 }
1307 }
1308 }
1309
1310
1311 /* Record all the refs within the basic block BB. */
1312 static void
1313 df_bb_refs_record (df, bb)
1314 struct df *df;
1315 basic_block bb;
1316 {
1317 rtx insn;
1318
1319 /* Scan the block an insn at a time from beginning to end. */
1320 for (insn = bb->head; ; insn = NEXT_INSN (insn))
1321 {
1322 if (INSN_P (insn))
1323 {
1324 /* Record defs within INSN. */
1325 df_insn_refs_record (df, bb, insn);
1326 }
1327 if (insn == bb->end)
1328 break;
1329 }
1330 }
1331
1332
1333 /* Record all the refs in the basic blocks specified by BLOCKS. */
1334 static void
1335 df_refs_record (df, blocks)
1336 struct df *df;
1337 bitmap blocks;
1338 {
1339 basic_block bb;
1340
1341 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1342 {
1343 df_bb_refs_record (df, bb);
1344 });
1345 }
1346 \f
1347 /* Dataflow analysis routines. */
1348
1349
1350 /* Create reg-def chains for basic block BB. These are a list of
1351 definitions for each register. */
1352 static void
1353 df_bb_reg_def_chain_create (df, bb)
1354 struct df *df;
1355 basic_block bb;
1356 {
1357 rtx insn;
1358
1359 /* Perhaps the defs should be sorted using a depth first search
1360 of the CFG (or possibly a breadth first search). We currently
1361 scan the basic blocks in reverse order so that the first defs
1362 appear at the start of the chain. */
1363
1364 for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
1365 insn = PREV_INSN (insn))
1366 {
1367 struct df_link *link;
1368 unsigned int uid = INSN_UID (insn);
1369
1370 if (! INSN_P (insn))
1371 continue;
1372
1373 for (link = df->insns[uid].defs; link; link = link->next)
1374 {
1375 struct ref *def = link->ref;
1376 unsigned int dregno = DF_REF_REGNO (def);
1377
1378 /* Do not add ref's to the chain twice, i.e., only add new
1379 refs. XXX the same could be done by testing if the
1380 current insn is a modified (or a new) one. This would be
1381 faster. */
1382 if (DF_REF_ID (def) < df->def_id_save)
1383 continue;
1384
1385 df->regs[dregno].defs
1386 = df_link_create (def, df->regs[dregno].defs);
1387 }
1388 }
1389 }
1390
1391
1392 /* Create reg-def chains for each basic block within BLOCKS. These
1393 are a list of definitions for each register. */
1394 static void
1395 df_reg_def_chain_create (df, blocks)
1396 struct df *df;
1397 bitmap blocks;
1398 {
1399 basic_block bb;
1400
1401 FOR_EACH_BB_IN_BITMAP/*_REV*/ (blocks, 0, bb,
1402 {
1403 df_bb_reg_def_chain_create (df, bb);
1404 });
1405 }
1406
1407
1408 /* Create reg-use chains for basic block BB. These are a list of uses
1409 for each register. */
1410 static void
1411 df_bb_reg_use_chain_create (df, bb)
1412 struct df *df;
1413 basic_block bb;
1414 {
1415 rtx insn;
1416
1417 /* Scan in forward order so that the last uses appear at the start
1418 of the chain. */
1419
1420 for (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
1421 insn = NEXT_INSN (insn))
1422 {
1423 struct df_link *link;
1424 unsigned int uid = INSN_UID (insn);
1425
1426 if (! INSN_P (insn))
1427 continue;
1428
1429 for (link = df->insns[uid].uses; link; link = link->next)
1430 {
1431 struct ref *use = link->ref;
1432 unsigned int uregno = DF_REF_REGNO (use);
1433
1434 /* Do not add ref's to the chain twice, i.e., only add new
1435 refs. XXX the same could be done by testing if the
1436 current insn is a modified (or a new) one. This would be
1437 faster. */
1438 if (DF_REF_ID (use) < df->use_id_save)
1439 continue;
1440
1441 df->regs[uregno].uses
1442 = df_link_create (use, df->regs[uregno].uses);
1443 }
1444 }
1445 }
1446
1447
1448 /* Create reg-use chains for each basic block within BLOCKS. These
1449 are a list of uses for each register. */
1450 static void
1451 df_reg_use_chain_create (df, blocks)
1452 struct df *df;
1453 bitmap blocks;
1454 {
1455 basic_block bb;
1456
1457 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1458 {
1459 df_bb_reg_use_chain_create (df, bb);
1460 });
1461 }
1462
1463
1464 /* Create def-use chains from reaching use bitmaps for basic block BB. */
1465 static void
1466 df_bb_du_chain_create (df, bb, ru)
1467 struct df *df;
1468 basic_block bb;
1469 bitmap ru;
1470 {
1471 struct bb_info *bb_info = DF_BB_INFO (df, bb);
1472 rtx insn;
1473
1474 bitmap_copy (ru, bb_info->ru_out);
1475
1476 /* For each def in BB create a linked list (chain) of uses
1477 reached from the def. */
1478 for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
1479 insn = PREV_INSN (insn))
1480 {
1481 struct df_link *def_link;
1482 struct df_link *use_link;
1483 unsigned int uid = INSN_UID (insn);
1484
1485 if (! INSN_P (insn))
1486 continue;
1487
1488 /* For each def in insn... */
1489 for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
1490 {
1491 struct ref *def = def_link->ref;
1492 unsigned int dregno = DF_REF_REGNO (def);
1493
1494 DF_REF_CHAIN (def) = 0;
1495
1496 /* While the reg-use chains are not essential, it
1497 is _much_ faster to search these short lists rather
1498 than all the reaching uses, especially for large functions. */
1499 for (use_link = df->regs[dregno].uses; use_link;
1500 use_link = use_link->next)
1501 {
1502 struct ref *use = use_link->ref;
1503
1504 if (bitmap_bit_p (ru, DF_REF_ID (use)))
1505 {
1506 DF_REF_CHAIN (def)
1507 = df_link_create (use, DF_REF_CHAIN (def));
1508
1509 bitmap_clear_bit (ru, DF_REF_ID (use));
1510 }
1511 }
1512 }
1513
1514 /* For each use in insn... */
1515 for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
1516 {
1517 struct ref *use = use_link->ref;
1518 bitmap_set_bit (ru, DF_REF_ID (use));
1519 }
1520 }
1521 }
1522
1523
1524 /* Create def-use chains from reaching use bitmaps for basic blocks
1525 in BLOCKS. */
1526 static void
1527 df_du_chain_create (df, blocks)
1528 struct df *df;
1529 bitmap blocks;
1530 {
1531 bitmap ru;
1532 basic_block bb;
1533
1534 ru = BITMAP_XMALLOC ();
1535
1536 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1537 {
1538 df_bb_du_chain_create (df, bb, ru);
1539 });
1540
1541 BITMAP_XFREE (ru);
1542 }
1543
1544
1545 /* Create use-def chains from reaching def bitmaps for basic block BB. */
1546 static void
1547 df_bb_ud_chain_create (df, bb)
1548 struct df *df;
1549 basic_block bb;
1550 {
1551 struct bb_info *bb_info = DF_BB_INFO (df, bb);
1552 struct ref **reg_def_last = df->reg_def_last;
1553 rtx insn;
1554
1555 memset (reg_def_last, 0, df->n_regs * sizeof (struct ref *));
1556
1557 /* For each use in BB create a linked list (chain) of defs
1558 that reach the use. */
1559 for (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
1560 insn = NEXT_INSN (insn))
1561 {
1562 unsigned int uid = INSN_UID (insn);
1563 struct df_link *use_link;
1564 struct df_link *def_link;
1565
1566 if (! INSN_P (insn))
1567 continue;
1568
1569 /* For each use in insn... */
1570 for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
1571 {
1572 struct ref *use = use_link->ref;
1573 unsigned int regno = DF_REF_REGNO (use);
1574
1575 DF_REF_CHAIN (use) = 0;
1576
1577 /* Has regno been defined in this BB yet? If so, use
1578 the last def as the single entry for the use-def
1579 chain for this use. Otherwise, we need to add all
1580 the defs using this regno that reach the start of
1581 this BB. */
1582 if (reg_def_last[regno])
1583 {
1584 DF_REF_CHAIN (use)
1585 = df_link_create (reg_def_last[regno], 0);
1586 }
1587 else
1588 {
1589 /* While the reg-def chains are not essential, it is
1590 _much_ faster to search these short lists rather than
1591 all the reaching defs, especially for large
1592 functions. */
1593 for (def_link = df->regs[regno].defs; def_link;
1594 def_link = def_link->next)
1595 {
1596 struct ref *def = def_link->ref;
1597
1598 if (bitmap_bit_p (bb_info->rd_in, DF_REF_ID (def)))
1599 {
1600 DF_REF_CHAIN (use)
1601 = df_link_create (def, DF_REF_CHAIN (use));
1602 }
1603 }
1604 }
1605 }
1606
1607
1608 /* For each def in insn... record the last def of each reg. */
1609 for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
1610 {
1611 struct ref *def = def_link->ref;
1612 int dregno = DF_REF_REGNO (def);
1613
1614 reg_def_last[dregno] = def;
1615 }
1616 }
1617 }
1618
1619
1620 /* Create use-def chains from reaching def bitmaps for basic blocks
1621 within BLOCKS. */
1622 static void
1623 df_ud_chain_create (df, blocks)
1624 struct df *df;
1625 bitmap blocks;
1626 {
1627 basic_block bb;
1628
1629 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1630 {
1631 df_bb_ud_chain_create (df, bb);
1632 });
1633 }
1634 \f
1635
1636
1637 static void
1638 df_rd_transfer_function (bb, changed, in, out, gen, kill, data)
1639 int bb ATTRIBUTE_UNUSED;
1640 int *changed;
1641 bitmap in, out, gen, kill;
1642 void *data ATTRIBUTE_UNUSED;
1643 {
1644 *changed = bitmap_union_of_diff (out, gen, in, kill);
1645 }
1646
1647
1648 static void
1649 df_ru_transfer_function (bb, changed, in, out, gen, kill, data)
1650 int bb ATTRIBUTE_UNUSED;
1651 int *changed;
1652 bitmap in, out, gen, kill;
1653 void *data ATTRIBUTE_UNUSED;
1654 {
1655 *changed = bitmap_union_of_diff (in, gen, out, kill);
1656 }
1657
1658
1659 static void
1660 df_lr_transfer_function (bb, changed, in, out, use, def, data)
1661 int bb ATTRIBUTE_UNUSED;
1662 int *changed;
1663 bitmap in, out, use, def;
1664 void *data ATTRIBUTE_UNUSED;
1665 {
1666 *changed = bitmap_union_of_diff (in, use, out, def);
1667 }
1668
1669
1670 /* Compute local reaching def info for basic block BB. */
1671 static void
1672 df_bb_rd_local_compute (df, bb)
1673 struct df *df;
1674 basic_block bb;
1675 {
1676 struct bb_info *bb_info = DF_BB_INFO (df, bb);
1677 rtx insn;
1678
1679 for (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
1680 insn = NEXT_INSN (insn))
1681 {
1682 unsigned int uid = INSN_UID (insn);
1683 struct df_link *def_link;
1684
1685 if (! INSN_P (insn))
1686 continue;
1687
1688 for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
1689 {
1690 struct ref *def = def_link->ref;
1691 unsigned int regno = DF_REF_REGNO (def);
1692 struct df_link *def2_link;
1693
1694 for (def2_link = df->regs[regno].defs; def2_link;
1695 def2_link = def2_link->next)
1696 {
1697 struct ref *def2 = def2_link->ref;
1698
1699 /* Add all defs of this reg to the set of kills. This
1700 is greedy since many of these defs will not actually
1701 be killed by this BB but it keeps things a lot
1702 simpler. */
1703 bitmap_set_bit (bb_info->rd_kill, DF_REF_ID (def2));
1704
1705 /* Zap from the set of gens for this BB. */
1706 bitmap_clear_bit (bb_info->rd_gen, DF_REF_ID (def2));
1707 }
1708
1709 bitmap_set_bit (bb_info->rd_gen, DF_REF_ID (def));
1710 }
1711 }
1712
1713 bb_info->rd_valid = 1;
1714 }
1715
1716
1717 /* Compute local reaching def info for each basic block within BLOCKS. */
1718 static void
1719 df_rd_local_compute (df, blocks)
1720 struct df *df;
1721 bitmap blocks;
1722 {
1723 basic_block bb;
1724
1725 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1726 {
1727 df_bb_rd_local_compute (df, bb);
1728 });
1729 }
1730
1731
1732 /* Compute local reaching use (upward exposed use) info for basic
1733 block BB. */
1734 static void
1735 df_bb_ru_local_compute (df, bb)
1736 struct df *df;
1737 basic_block bb;
1738 {
1739 /* This is much more tricky than computing reaching defs. With
1740 reaching defs, defs get killed by other defs. With upwards
1741 exposed uses, these get killed by defs with the same regno. */
1742
1743 struct bb_info *bb_info = DF_BB_INFO (df, bb);
1744 rtx insn;
1745
1746
1747 for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
1748 insn = PREV_INSN (insn))
1749 {
1750 unsigned int uid = INSN_UID (insn);
1751 struct df_link *def_link;
1752 struct df_link *use_link;
1753
1754 if (! INSN_P (insn))
1755 continue;
1756
1757 for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
1758 {
1759 struct ref *def = def_link->ref;
1760 unsigned int dregno = DF_REF_REGNO (def);
1761
1762 for (use_link = df->regs[dregno].uses; use_link;
1763 use_link = use_link->next)
1764 {
1765 struct ref *use = use_link->ref;
1766
1767 /* Add all uses of this reg to the set of kills. This
1768 is greedy since many of these uses will not actually
1769 be killed by this BB but it keeps things a lot
1770 simpler. */
1771 bitmap_set_bit (bb_info->ru_kill, DF_REF_ID (use));
1772
1773 /* Zap from the set of gens for this BB. */
1774 bitmap_clear_bit (bb_info->ru_gen, DF_REF_ID (use));
1775 }
1776 }
1777
1778 for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
1779 {
1780 struct ref *use = use_link->ref;
1781 /* Add use to set of gens in this BB. */
1782 bitmap_set_bit (bb_info->ru_gen, DF_REF_ID (use));
1783 }
1784 }
1785 bb_info->ru_valid = 1;
1786 }
1787
1788
1789 /* Compute local reaching use (upward exposed use) info for each basic
1790 block within BLOCKS. */
1791 static void
1792 df_ru_local_compute (df, blocks)
1793 struct df *df;
1794 bitmap blocks;
1795 {
1796 basic_block bb;
1797
1798 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1799 {
1800 df_bb_ru_local_compute (df, bb);
1801 });
1802 }
1803
1804
1805 /* Compute local live variable info for basic block BB. */
1806 static void
1807 df_bb_lr_local_compute (df, bb)
1808 struct df *df;
1809 basic_block bb;
1810 {
1811 struct bb_info *bb_info = DF_BB_INFO (df, bb);
1812 rtx insn;
1813
1814 for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
1815 insn = PREV_INSN (insn))
1816 {
1817 unsigned int uid = INSN_UID (insn);
1818 struct df_link *link;
1819
1820 if (! INSN_P (insn))
1821 continue;
1822
1823 for (link = df->insns[uid].defs; link; link = link->next)
1824 {
1825 struct ref *def = link->ref;
1826 unsigned int dregno = DF_REF_REGNO (def);
1827
1828 /* Add def to set of defs in this BB. */
1829 bitmap_set_bit (bb_info->lr_def, dregno);
1830
1831 bitmap_clear_bit (bb_info->lr_use, dregno);
1832 }
1833
1834 for (link = df->insns[uid].uses; link; link = link->next)
1835 {
1836 struct ref *use = link->ref;
1837 /* Add use to set of uses in this BB. */
1838 bitmap_set_bit (bb_info->lr_use, DF_REF_REGNO (use));
1839 }
1840 }
1841 bb_info->lr_valid = 1;
1842 }
1843
1844
1845 /* Compute local live variable info for each basic block within BLOCKS. */
1846 static void
1847 df_lr_local_compute (df, blocks)
1848 struct df *df;
1849 bitmap blocks;
1850 {
1851 basic_block bb;
1852
1853 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1854 {
1855 df_bb_lr_local_compute (df, bb);
1856 });
1857 }
1858
1859
1860 /* Compute register info: lifetime, bb, and number of defs and uses
1861 for basic block BB. */
1862 static void
1863 df_bb_reg_info_compute (df, bb, live)
1864 struct df *df;
1865 basic_block bb;
1866 bitmap live;
1867 {
1868 struct reg_info *reg_info = df->regs;
1869 struct bb_info *bb_info = DF_BB_INFO (df, bb);
1870 rtx insn;
1871
1872 bitmap_copy (live, bb_info->lr_out);
1873
1874 for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
1875 insn = PREV_INSN (insn))
1876 {
1877 unsigned int uid = INSN_UID (insn);
1878 unsigned int regno;
1879 struct df_link *link;
1880
1881 if (! INSN_P (insn))
1882 continue;
1883
1884 for (link = df->insns[uid].defs; link; link = link->next)
1885 {
1886 struct ref *def = link->ref;
1887 unsigned int dregno = DF_REF_REGNO (def);
1888
1889 /* Kill this register. */
1890 bitmap_clear_bit (live, dregno);
1891 reg_info[dregno].n_defs++;
1892 }
1893
1894 for (link = df->insns[uid].uses; link; link = link->next)
1895 {
1896 struct ref *use = link->ref;
1897 unsigned int uregno = DF_REF_REGNO (use);
1898
1899 /* This register is now live. */
1900 bitmap_set_bit (live, uregno);
1901 reg_info[uregno].n_uses++;
1902 }
1903
1904 /* Increment lifetimes of all live registers. */
1905 EXECUTE_IF_SET_IN_BITMAP (live, 0, regno,
1906 {
1907 reg_info[regno].lifetime++;
1908 });
1909 }
1910 }
1911
1912
1913 /* Compute register info: lifetime, bb, and number of defs and uses. */
1914 static void
1915 df_reg_info_compute (df, blocks)
1916 struct df *df;
1917 bitmap blocks;
1918 {
1919 basic_block bb;
1920 bitmap live;
1921
1922 live = BITMAP_XMALLOC ();
1923
1924 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1925 {
1926 df_bb_reg_info_compute (df, bb, live);
1927 });
1928
1929 BITMAP_XFREE (live);
1930 }
1931
1932
1933 /* Assign LUIDs for BB. */
1934 static int
1935 df_bb_luids_set (df, bb)
1936 struct df *df;
1937 basic_block bb;
1938 {
1939 rtx insn;
1940 int luid = 0;
1941
1942 /* The LUIDs are monotonically increasing for each basic block. */
1943
1944 for (insn = bb->head; ; insn = NEXT_INSN (insn))
1945 {
1946 if (INSN_P (insn))
1947 DF_INSN_LUID (df, insn) = luid++;
1948 DF_INSN_LUID (df, insn) = luid;
1949
1950 if (insn == bb->end)
1951 break;
1952 }
1953 return luid;
1954 }
1955
1956
1957 /* Assign LUIDs for each basic block within BLOCKS. */
1958 static int
1959 df_luids_set (df, blocks)
1960 struct df *df;
1961 bitmap blocks;
1962 {
1963 basic_block bb;
1964 int total = 0;
1965
1966 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
1967 {
1968 total += df_bb_luids_set (df, bb);
1969 });
1970 return total;
1971 }
1972
1973
1974 /* Perform dataflow analysis using existing DF structure for blocks
1975 within BLOCKS. If BLOCKS is zero, use all basic blocks in the CFG. */
1976 static void
1977 df_analyse_1 (df, blocks, flags, update)
1978 struct df *df;
1979 bitmap blocks;
1980 int flags;
1981 int update;
1982 {
1983 int aflags;
1984 int dflags;
1985 int i;
1986 basic_block bb;
1987
1988 dflags = 0;
1989 aflags = flags;
1990 if (flags & DF_UD_CHAIN)
1991 aflags |= DF_RD | DF_RD_CHAIN;
1992
1993 if (flags & DF_DU_CHAIN)
1994 aflags |= DF_RU;
1995
1996 if (flags & DF_RU)
1997 aflags |= DF_RU_CHAIN;
1998
1999 if (flags & DF_REG_INFO)
2000 aflags |= DF_LR;
2001
2002 if (! blocks)
2003 blocks = df->all_blocks;
2004
2005 df->flags = flags;
2006 if (update)
2007 {
2008 df_refs_update (df);
2009 /* More fine grained incremental dataflow analysis would be
2010 nice. For now recompute the whole shebang for the
2011 modified blocks. */
2012 #if 0
2013 df_refs_unlink (df, blocks);
2014 #endif
2015 /* All the def-use, use-def chains can be potentially
2016 modified by changes in one block. The size of the
2017 bitmaps can also change. */
2018 }
2019 else
2020 {
2021 /* Scan the function for all register defs and uses. */
2022 df_refs_queue (df);
2023 df_refs_record (df, blocks);
2024
2025 /* Link all the new defs and uses to the insns. */
2026 df_refs_process (df);
2027 }
2028
2029 /* Allocate the bitmaps now the total number of defs and uses are
2030 known. If the number of defs or uses have changed, then
2031 these bitmaps need to be reallocated. */
2032 df_bitmaps_alloc (df, aflags);
2033
2034 /* Set the LUIDs for each specified basic block. */
2035 df_luids_set (df, blocks);
2036
2037 /* Recreate reg-def and reg-use chains from scratch so that first
2038 def is at the head of the reg-def chain and the last use is at
2039 the head of the reg-use chain. This is only important for
2040 regs local to a basic block as it speeds up searching. */
2041 if (aflags & DF_RD_CHAIN)
2042 {
2043 df_reg_def_chain_create (df, blocks);
2044 }
2045
2046 if (aflags & DF_RU_CHAIN)
2047 {
2048 df_reg_use_chain_create (df, blocks);
2049 }
2050
2051 df->dfs_order = xmalloc (sizeof (int) * n_basic_blocks);
2052 df->rc_order = xmalloc (sizeof (int) * n_basic_blocks);
2053 df->rts_order = xmalloc (sizeof (int) * n_basic_blocks);
2054 df->inverse_dfs_map = xmalloc (sizeof (int) * last_basic_block);
2055 df->inverse_rc_map = xmalloc (sizeof (int) * last_basic_block);
2056 df->inverse_rts_map = xmalloc (sizeof (int) * last_basic_block);
2057
2058 flow_depth_first_order_compute (df->dfs_order, df->rc_order);
2059 flow_reverse_top_sort_order_compute (df->rts_order);
2060 for (i = 0; i < n_basic_blocks; i++)
2061 {
2062 df->inverse_dfs_map[df->dfs_order[i]] = i;
2063 df->inverse_rc_map[df->rc_order[i]] = i;
2064 df->inverse_rts_map[df->rts_order[i]] = i;
2065 }
2066 if (aflags & DF_RD)
2067 {
2068 /* Compute the sets of gens and kills for the defs of each bb. */
2069 df_rd_local_compute (df, df->flags & DF_RD ? blocks : df->all_blocks);
2070 {
2071 bitmap *in = xmalloc (sizeof (bitmap) * last_basic_block);
2072 bitmap *out = xmalloc (sizeof (bitmap) * last_basic_block);
2073 bitmap *gen = xmalloc (sizeof (bitmap) * last_basic_block);
2074 bitmap *kill = xmalloc (sizeof (bitmap) * last_basic_block);
2075 FOR_EACH_BB (bb)
2076 {
2077 in[bb->index] = DF_BB_INFO (df, bb)->rd_in;
2078 out[bb->index] = DF_BB_INFO (df, bb)->rd_out;
2079 gen[bb->index] = DF_BB_INFO (df, bb)->rd_gen;
2080 kill[bb->index] = DF_BB_INFO (df, bb)->rd_kill;
2081 }
2082 iterative_dataflow_bitmap (in, out, gen, kill, df->all_blocks,
2083 DF_FORWARD, DF_UNION, df_rd_transfer_function,
2084 df->inverse_rc_map, NULL);
2085 free (in);
2086 free (out);
2087 free (gen);
2088 free (kill);
2089 }
2090 }
2091
2092 if (aflags & DF_UD_CHAIN)
2093 {
2094 /* Create use-def chains. */
2095 df_ud_chain_create (df, df->all_blocks);
2096
2097 if (! (flags & DF_RD))
2098 dflags |= DF_RD;
2099 }
2100
2101 if (aflags & DF_RU)
2102 {
2103 /* Compute the sets of gens and kills for the upwards exposed
2104 uses in each bb. */
2105 df_ru_local_compute (df, df->flags & DF_RU ? blocks : df->all_blocks);
2106 {
2107 bitmap *in = xmalloc (sizeof (bitmap) * last_basic_block);
2108 bitmap *out = xmalloc (sizeof (bitmap) * last_basic_block);
2109 bitmap *gen = xmalloc (sizeof (bitmap) * last_basic_block);
2110 bitmap *kill = xmalloc (sizeof (bitmap) * last_basic_block);
2111 FOR_EACH_BB (bb)
2112 {
2113 in[bb->index] = DF_BB_INFO (df, bb)->ru_in;
2114 out[bb->index] = DF_BB_INFO (df, bb)->ru_out;
2115 gen[bb->index] = DF_BB_INFO (df, bb)->ru_gen;
2116 kill[bb->index] = DF_BB_INFO (df, bb)->ru_kill;
2117 }
2118 iterative_dataflow_bitmap (in, out, gen, kill, df->all_blocks,
2119 DF_BACKWARD, DF_UNION, df_ru_transfer_function,
2120 df->inverse_rts_map, NULL);
2121 free (in);
2122 free (out);
2123 free (gen);
2124 free (kill);
2125 }
2126 }
2127
2128 if (aflags & DF_DU_CHAIN)
2129 {
2130 /* Create def-use chains. */
2131 df_du_chain_create (df, df->all_blocks);
2132
2133 if (! (flags & DF_RU))
2134 dflags |= DF_RU;
2135 }
2136
2137 /* Free up bitmaps that are no longer required. */
2138 if (dflags)
2139 df_bitmaps_free (df, dflags);
2140
2141 if (aflags & DF_LR)
2142 {
2143 /* Compute the sets of defs and uses of live variables. */
2144 df_lr_local_compute (df, df->flags & DF_LR ? blocks : df->all_blocks);
2145 {
2146 bitmap *in = xmalloc (sizeof (bitmap) * last_basic_block);
2147 bitmap *out = xmalloc (sizeof (bitmap) * last_basic_block);
2148 bitmap *use = xmalloc (sizeof (bitmap) * last_basic_block);
2149 bitmap *def = xmalloc (sizeof (bitmap) * last_basic_block);
2150 FOR_EACH_BB (bb)
2151 {
2152 in[bb->index] = DF_BB_INFO (df, bb)->lr_in;
2153 out[bb->index] = DF_BB_INFO (df, bb)->lr_out;
2154 use[bb->index] = DF_BB_INFO (df, bb)->lr_use;
2155 def[bb->index] = DF_BB_INFO (df, bb)->lr_def;
2156 }
2157 iterative_dataflow_bitmap (in, out, use, def, df->all_blocks,
2158 DF_BACKWARD, DF_UNION, df_lr_transfer_function,
2159 df->inverse_rts_map, NULL);
2160 free (in);
2161 free (out);
2162 free (use);
2163 free (def);
2164 }
2165 }
2166
2167 if (aflags & DF_REG_INFO)
2168 {
2169 df_reg_info_compute (df, df->all_blocks);
2170 }
2171
2172 free (df->dfs_order);
2173 free (df->rc_order);
2174 free (df->rts_order);
2175 free (df->inverse_rc_map);
2176 free (df->inverse_dfs_map);
2177 free (df->inverse_rts_map);
2178 }
2179
2180
2181 /* Initialize dataflow analysis. */
2182 struct df *
2183 df_init ()
2184 {
2185 struct df *df;
2186
2187 df = xcalloc (1, sizeof (struct df));
2188
2189 /* Squirrel away a global for debugging. */
2190 ddf = df;
2191
2192 return df;
2193 }
2194
2195
2196 /* Start queuing refs. */
2197 static int
2198 df_refs_queue (df)
2199 struct df *df;
2200 {
2201 df->def_id_save = df->def_id;
2202 df->use_id_save = df->use_id;
2203 /* ???? Perhaps we should save current obstack state so that we can
2204 unwind it. */
2205 return 0;
2206 }
2207
2208
2209 /* Process queued refs. */
2210 static int
2211 df_refs_process (df)
2212 struct df *df;
2213 {
2214 unsigned int i;
2215
2216 /* Build new insn-def chains. */
2217 for (i = df->def_id_save; i != df->def_id; i++)
2218 {
2219 struct ref *def = df->defs[i];
2220 unsigned int uid = DF_REF_INSN_UID (def);
2221
2222 /* Add def to head of def list for INSN. */
2223 df->insns[uid].defs
2224 = df_link_create (def, df->insns[uid].defs);
2225 }
2226
2227 /* Build new insn-use chains. */
2228 for (i = df->use_id_save; i != df->use_id; i++)
2229 {
2230 struct ref *use = df->uses[i];
2231 unsigned int uid = DF_REF_INSN_UID (use);
2232
2233 /* Add use to head of use list for INSN. */
2234 df->insns[uid].uses
2235 = df_link_create (use, df->insns[uid].uses);
2236 }
2237 return 0;
2238 }
2239
2240
2241 /* Update refs for basic block BB. */
2242 static int
2243 df_bb_refs_update (df, bb)
2244 struct df *df;
2245 basic_block bb;
2246 {
2247 rtx insn;
2248 int count = 0;
2249
2250 /* While we have to scan the chain of insns for this BB, we do not
2251 need to allocate and queue a long chain of BB/INSN pairs. Using
2252 a bitmap for insns_modified saves memory and avoids queuing
2253 duplicates. */
2254
2255 for (insn = bb->head; ; insn = NEXT_INSN (insn))
2256 {
2257 unsigned int uid;
2258
2259 uid = INSN_UID (insn);
2260
2261 if (bitmap_bit_p (df->insns_modified, uid))
2262 {
2263 /* Delete any allocated refs of this insn. MPH, FIXME. */
2264 df_insn_refs_unlink (df, bb, insn);
2265
2266 /* Scan the insn for refs. */
2267 df_insn_refs_record (df, bb, insn);
2268
2269 count++;
2270 }
2271 if (insn == bb->end)
2272 break;
2273 }
2274 return count;
2275 }
2276
2277
2278 /* Process all the modified/deleted insns that were queued. */
2279 static int
2280 df_refs_update (df)
2281 struct df *df;
2282 {
2283 basic_block bb;
2284 int count = 0;
2285
2286 if ((unsigned int) max_reg_num () >= df->reg_size)
2287 df_reg_table_realloc (df, 0);
2288
2289 df_refs_queue (df);
2290
2291 FOR_EACH_BB_IN_BITMAP (df->bbs_modified, 0, bb,
2292 {
2293 count += df_bb_refs_update (df, bb);
2294 });
2295
2296 df_refs_process (df);
2297 return count;
2298 }
2299
2300
2301 /* Return nonzero if any of the requested blocks in the bitmap
2302 BLOCKS have been modified. */
2303 static int
2304 df_modified_p (df, blocks)
2305 struct df *df;
2306 bitmap blocks;
2307 {
2308 int update = 0;
2309 basic_block bb;
2310
2311 if (!df->n_bbs)
2312 return 0;
2313
2314 FOR_EACH_BB (bb)
2315 if (bitmap_bit_p (df->bbs_modified, bb->index)
2316 && (! blocks || (blocks == (bitmap) -1) || bitmap_bit_p (blocks, bb->index)))
2317 {
2318 update = 1;
2319 break;
2320 }
2321
2322 return update;
2323 }
2324
2325
2326 /* Analyze dataflow info for the basic blocks specified by the bitmap
2327 BLOCKS, or for the whole CFG if BLOCKS is zero, or just for the
2328 modified blocks if BLOCKS is -1. */
2329 int
2330 df_analyse (df, blocks, flags)
2331 struct df *df;
2332 bitmap blocks;
2333 int flags;
2334 {
2335 int update;
2336
2337 /* We could deal with additional basic blocks being created by
2338 rescanning everything again. */
2339 if (df->n_bbs && df->n_bbs != (unsigned int) last_basic_block)
2340 abort ();
2341
2342 update = df_modified_p (df, blocks);
2343 if (update || (flags != df->flags))
2344 {
2345 if (! blocks)
2346 {
2347 if (df->n_bbs)
2348 {
2349 /* Recompute everything from scratch. */
2350 df_free (df);
2351 }
2352 /* Allocate and initialize data structures. */
2353 df_alloc (df, max_reg_num ());
2354 df_analyse_1 (df, 0, flags, 0);
2355 update = 1;
2356 }
2357 else
2358 {
2359 if (blocks == (bitmap) -1)
2360 blocks = df->bbs_modified;
2361
2362 if (! df->n_bbs)
2363 abort ();
2364
2365 df_analyse_1 (df, blocks, flags, 1);
2366 bitmap_zero (df->bbs_modified);
2367 bitmap_zero (df->insns_modified);
2368 }
2369 }
2370 return update;
2371 }
2372
2373
2374 /* Free all the dataflow info and the DF structure. */
2375 void
2376 df_finish (df)
2377 struct df *df;
2378 {
2379 df_free (df);
2380 free (df);
2381 }
2382
2383
2384 /* Unlink INSN from its reference information. */
2385 static void
2386 df_insn_refs_unlink (df, bb, insn)
2387 struct df *df;
2388 basic_block bb ATTRIBUTE_UNUSED;
2389 rtx insn;
2390 {
2391 struct df_link *link;
2392 unsigned int uid;
2393
2394 uid = INSN_UID (insn);
2395
2396 /* Unlink all refs defined by this insn. */
2397 for (link = df->insns[uid].defs; link; link = link->next)
2398 df_def_unlink (df, link->ref);
2399
2400 /* Unlink all refs used by this insn. */
2401 for (link = df->insns[uid].uses; link; link = link->next)
2402 df_use_unlink (df, link->ref);
2403
2404 df->insns[uid].defs = 0;
2405 df->insns[uid].uses = 0;
2406 }
2407
2408
2409 #if 0
2410 /* Unlink all the insns within BB from their reference information. */
2411 static void
2412 df_bb_refs_unlink (df, bb)
2413 struct df *df;
2414 basic_block bb;
2415 {
2416 rtx insn;
2417
2418 /* Scan the block an insn at a time from beginning to end. */
2419 for (insn = bb->head; ; insn = NEXT_INSN (insn))
2420 {
2421 if (INSN_P (insn))
2422 {
2423 /* Unlink refs for INSN. */
2424 df_insn_refs_unlink (df, bb, insn);
2425 }
2426 if (insn == bb->end)
2427 break;
2428 }
2429 }
2430
2431
2432 /* Unlink all the refs in the basic blocks specified by BLOCKS.
2433 Not currently used. */
2434 static void
2435 df_refs_unlink (df, blocks)
2436 struct df *df;
2437 bitmap blocks;
2438 {
2439 basic_block bb;
2440
2441 if (blocks)
2442 {
2443 FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
2444 {
2445 df_bb_refs_unlink (df, bb);
2446 });
2447 }
2448 else
2449 {
2450 FOR_EACH_BB (bb)
2451 df_bb_refs_unlink (df, bb);
2452 }
2453 }
2454 #endif
2455 \f
2456 /* Functions to modify insns. */
2457
2458
2459 /* Delete INSN and all its reference information. */
2460 rtx
2461 df_insn_delete (df, bb, insn)
2462 struct df *df;
2463 basic_block bb ATTRIBUTE_UNUSED;
2464 rtx insn;
2465 {
2466 /* If the insn is a jump, we should perhaps call delete_insn to
2467 handle the JUMP_LABEL? */
2468
2469 /* We should not be deleting the NOTE_INSN_BASIC_BLOCK or label. */
2470 if (insn == bb->head)
2471 abort ();
2472
2473 /* Delete the insn. */
2474 delete_insn (insn);
2475
2476 df_insn_modify (df, bb, insn);
2477
2478 return NEXT_INSN (insn);
2479 }
2480
2481
2482 /* Mark that INSN within BB may have changed (created/modified/deleted).
2483 This may be called multiple times for the same insn. There is no
2484 harm calling this function if the insn wasn't changed; it will just
2485 slow down the rescanning of refs. */
2486 void
2487 df_insn_modify (df, bb, insn)
2488 struct df *df;
2489 basic_block bb;
2490 rtx insn;
2491 {
2492 unsigned int uid;
2493
2494 uid = INSN_UID (insn);
2495 if (uid >= df->insn_size)
2496 df_insn_table_realloc (df, uid);
2497
2498 bitmap_set_bit (df->bbs_modified, bb->index);
2499 bitmap_set_bit (df->insns_modified, uid);
2500
2501 /* For incremental updating on the fly, perhaps we could make a copy
2502 of all the refs of the original insn and turn them into
2503 anti-refs. When df_refs_update finds these anti-refs, it annihilates
2504 the original refs. If validate_change fails then these anti-refs
2505 will just get ignored. */
2506 }
2507
2508
2509 typedef struct replace_args
2510 {
2511 rtx match;
2512 rtx replacement;
2513 rtx insn;
2514 int modified;
2515 } replace_args;
2516
2517
2518 /* Replace mem pointed to by PX with its associated pseudo register.
2519 DATA is actually a pointer to a structure describing the
2520 instruction currently being scanned and the MEM we are currently
2521 replacing. */
2522 static int
2523 df_rtx_mem_replace (px, data)
2524 rtx *px;
2525 void *data;
2526 {
2527 replace_args *args = (replace_args *) data;
2528 rtx mem = *px;
2529
2530 if (mem == NULL_RTX)
2531 return 0;
2532
2533 switch (GET_CODE (mem))
2534 {
2535 case MEM:
2536 break;
2537
2538 case CONST_DOUBLE:
2539 /* We're not interested in the MEM associated with a
2540 CONST_DOUBLE, so there's no need to traverse into one. */
2541 return -1;
2542
2543 default:
2544 /* This is not a MEM. */
2545 return 0;
2546 }
2547
2548 if (!rtx_equal_p (args->match, mem))
2549 /* This is not the MEM we are currently replacing. */
2550 return 0;
2551
2552 /* Actually replace the MEM. */
2553 validate_change (args->insn, px, args->replacement, 1);
2554 args->modified++;
2555
2556 return 0;
2557 }
2558
2559
2560 int
2561 df_insn_mem_replace (df, bb, insn, mem, reg)
2562 struct df *df;
2563 basic_block bb;
2564 rtx insn;
2565 rtx mem;
2566 rtx reg;
2567 {
2568 replace_args args;
2569
2570 args.insn = insn;
2571 args.match = mem;
2572 args.replacement = reg;
2573 args.modified = 0;
2574
2575 /* Search and replace all matching mems within insn. */
2576 for_each_rtx (&insn, df_rtx_mem_replace, &args);
2577
2578 if (args.modified)
2579 df_insn_modify (df, bb, insn);
2580
2581 /* ???? FIXME. We may have a new def or one or more new uses of REG
2582 in INSN. REG should be a new pseudo so it won't affect the
2583 dataflow information that we currently have. We should add
2584 the new uses and defs to INSN and then recreate the chains
2585 when df_analyse is called. */
2586 return args.modified;
2587 }
2588
2589
2590 /* Replace one register with another. Called through for_each_rtx; PX
2591 points to the rtx being scanned. DATA is actually a pointer to a
2592 structure of arguments. */
2593 static int
2594 df_rtx_reg_replace (px, data)
2595 rtx *px;
2596 void *data;
2597 {
2598 rtx x = *px;
2599 replace_args *args = (replace_args *) data;
2600
2601 if (x == NULL_RTX)
2602 return 0;
2603
2604 if (x == args->match)
2605 {
2606 validate_change (args->insn, px, args->replacement, 1);
2607 args->modified++;
2608 }
2609
2610 return 0;
2611 }
2612
2613
2614 /* Replace the reg within every ref on CHAIN that is within the set
2615 BLOCKS of basic blocks with NEWREG. Also update the regs within
2616 REG_NOTES. */
2617 void
2618 df_refs_reg_replace (df, blocks, chain, oldreg, newreg)
2619 struct df *df;
2620 bitmap blocks;
2621 struct df_link *chain;
2622 rtx oldreg;
2623 rtx newreg;
2624 {
2625 struct df_link *link;
2626 replace_args args;
2627
2628 if (! blocks)
2629 blocks = df->all_blocks;
2630
2631 args.match = oldreg;
2632 args.replacement = newreg;
2633 args.modified = 0;
2634
2635 for (link = chain; link; link = link->next)
2636 {
2637 struct ref *ref = link->ref;
2638 rtx insn = DF_REF_INSN (ref);
2639
2640 if (! INSN_P (insn))
2641 continue;
2642
2643 if (bitmap_bit_p (blocks, DF_REF_BBNO (ref)))
2644 {
2645 df_ref_reg_replace (df, ref, oldreg, newreg);
2646
2647 /* Replace occurrences of the reg within the REG_NOTES. */
2648 if ((! link->next || DF_REF_INSN (ref)
2649 != DF_REF_INSN (link->next->ref))
2650 && REG_NOTES (insn))
2651 {
2652 args.insn = insn;
2653 for_each_rtx (&REG_NOTES (insn), df_rtx_reg_replace, &args);
2654 }
2655 }
2656 else
2657 {
2658 /* Temporary check to ensure that we have a grip on which
2659 regs should be replaced. */
2660 abort ();
2661 }
2662 }
2663 }
2664
2665
2666 /* Replace all occurrences of register OLDREG with register NEWREG in
2667 blocks defined by bitmap BLOCKS. This also replaces occurrences of
2668 OLDREG in the REG_NOTES but only for insns containing OLDREG. This
2669 routine expects the reg-use and reg-def chains to be valid. */
2670 int
2671 df_reg_replace (df, blocks, oldreg, newreg)
2672 struct df *df;
2673 bitmap blocks;
2674 rtx oldreg;
2675 rtx newreg;
2676 {
2677 unsigned int oldregno = REGNO (oldreg);
2678
2679 df_refs_reg_replace (df, blocks, df->regs[oldregno].defs, oldreg, newreg);
2680 df_refs_reg_replace (df, blocks, df->regs[oldregno].uses, oldreg, newreg);
2681 return 1;
2682 }
2683
2684
2685 /* Try replacing the reg within REF with NEWREG. Do not modify
2686 def-use/use-def chains. */
2687 int
2688 df_ref_reg_replace (df, ref, oldreg, newreg)
2689 struct df *df;
2690 struct ref *ref;
2691 rtx oldreg;
2692 rtx newreg;
2693 {
2694 /* Check that insn was deleted by being converted into a NOTE. If
2695 so ignore this insn. */
2696 if (! INSN_P (DF_REF_INSN (ref)))
2697 return 0;
2698
2699 if (oldreg && oldreg != DF_REF_REG (ref))
2700 abort ();
2701
2702 if (! validate_change (DF_REF_INSN (ref), DF_REF_LOC (ref), newreg, 1))
2703 return 0;
2704
2705 df_insn_modify (df, DF_REF_BB (ref), DF_REF_INSN (ref));
2706 return 1;
2707 }
2708
2709
2710 struct ref*
2711 df_bb_def_use_swap (df, bb, def_insn, use_insn, regno)
2712 struct df * df;
2713 basic_block bb;
2714 rtx def_insn;
2715 rtx use_insn;
2716 unsigned int regno;
2717 {
2718 struct ref *def;
2719 struct ref *use;
2720 int def_uid;
2721 int use_uid;
2722 struct df_link *link;
2723
2724 def = df_bb_insn_regno_first_def_find (df, bb, def_insn, regno);
2725 if (! def)
2726 return 0;
2727
2728 use = df_bb_insn_regno_last_use_find (df, bb, use_insn, regno);
2729 if (! use)
2730 return 0;
2731
2732 /* The USE no longer exists. */
2733 use_uid = INSN_UID (use_insn);
2734 df_use_unlink (df, use);
2735 df_ref_unlink (&df->insns[use_uid].uses, use);
2736
2737 /* The DEF requires shifting so remove it from DEF_INSN
2738 and add it to USE_INSN by reusing LINK. */
2739 def_uid = INSN_UID (def_insn);
2740 link = df_ref_unlink (&df->insns[def_uid].defs, def);
2741 link->ref = def;
2742 link->next = df->insns[use_uid].defs;
2743 df->insns[use_uid].defs = link;
2744
2745 #if 0
2746 link = df_ref_unlink (&df->regs[regno].defs, def);
2747 link->ref = def;
2748 link->next = df->regs[regno].defs;
2749 df->insns[regno].defs = link;
2750 #endif
2751
2752 DF_REF_INSN (def) = use_insn;
2753 return def;
2754 }
2755
2756
2757 /* Record df between FIRST_INSN and LAST_INSN inclusive. All new
2758 insns must be processed by this routine. */
2759 static void
2760 df_insns_modify (df, bb, first_insn, last_insn)
2761 struct df *df;
2762 basic_block bb;
2763 rtx first_insn;
2764 rtx last_insn;
2765 {
2766 rtx insn;
2767
2768 for (insn = first_insn; ; insn = NEXT_INSN (insn))
2769 {
2770 unsigned int uid;
2771
2772 /* A non-const call should not have slipped through the net. If
2773 it does, we need to create a new basic block. Ouch. The
2774 same applies for a label. */
2775 if ((GET_CODE (insn) == CALL_INSN
2776 && ! CONST_OR_PURE_CALL_P (insn))
2777 || GET_CODE (insn) == CODE_LABEL)
2778 abort ();
2779
2780 uid = INSN_UID (insn);
2781
2782 if (uid >= df->insn_size)
2783 df_insn_table_realloc (df, uid);
2784
2785 df_insn_modify (df, bb, insn);
2786
2787 if (insn == last_insn)
2788 break;
2789 }
2790 }
2791
2792
2793 /* Emit PATTERN before INSN within BB. */
2794 rtx
2795 df_pattern_emit_before (df, pattern, bb, insn)
2796 struct df *df ATTRIBUTE_UNUSED;
2797 rtx pattern;
2798 basic_block bb;
2799 rtx insn;
2800 {
2801 rtx ret_insn;
2802 rtx prev_insn = PREV_INSN (insn);
2803
2804 /* We should not be inserting before the start of the block. */
2805 if (insn == bb->head)
2806 abort ();
2807 ret_insn = emit_insn_before (pattern, insn);
2808 if (ret_insn == insn)
2809 return ret_insn;
2810
2811 df_insns_modify (df, bb, NEXT_INSN (prev_insn), ret_insn);
2812 return ret_insn;
2813 }
2814
2815
2816 /* Emit PATTERN after INSN within BB. */
2817 rtx
2818 df_pattern_emit_after (df, pattern, bb, insn)
2819 struct df *df;
2820 rtx pattern;
2821 basic_block bb;
2822 rtx insn;
2823 {
2824 rtx ret_insn;
2825
2826 ret_insn = emit_insn_after (pattern, insn);
2827 if (ret_insn == insn)
2828 return ret_insn;
2829
2830 df_insns_modify (df, bb, NEXT_INSN (insn), ret_insn);
2831 return ret_insn;
2832 }
2833
2834
2835 /* Emit jump PATTERN after INSN within BB. */
2836 rtx
2837 df_jump_pattern_emit_after (df, pattern, bb, insn)
2838 struct df *df;
2839 rtx pattern;
2840 basic_block bb;
2841 rtx insn;
2842 {
2843 rtx ret_insn;
2844
2845 ret_insn = emit_jump_insn_after (pattern, insn);
2846 if (ret_insn == insn)
2847 return ret_insn;
2848
2849 df_insns_modify (df, bb, NEXT_INSN (insn), ret_insn);
2850 return ret_insn;
2851 }
2852
2853
2854 /* Move INSN within BB before BEFORE_INSN within BEFORE_BB.
2855
2856 This function should only be used to move loop invariant insns
2857 out of a loop where it has been proven that the def-use info
2858 will still be valid. */
2859 rtx
2860 df_insn_move_before (df, bb, insn, before_bb, before_insn)
2861 struct df *df;
2862 basic_block bb;
2863 rtx insn;
2864 basic_block before_bb;
2865 rtx before_insn;
2866 {
2867 struct df_link *link;
2868 unsigned int uid;
2869
2870 if (! bb)
2871 return df_pattern_emit_before (df, insn, before_bb, before_insn);
2872
2873 uid = INSN_UID (insn);
2874
2875 /* Change bb for all df defined and used by this insn. */
2876 for (link = df->insns[uid].defs; link; link = link->next)
2877 DF_REF_BB (link->ref) = before_bb;
2878 for (link = df->insns[uid].uses; link; link = link->next)
2879 DF_REF_BB (link->ref) = before_bb;
2880
2881 /* The lifetimes of the registers used in this insn will be reduced
2882 while the lifetimes of the registers defined in this insn
2883 are likely to be increased. */
2884
2885 /* ???? Perhaps all the insns moved should be stored on a list
2886 which df_analyse removes when it recalculates data flow. */
2887
2888 return emit_insn_before (insn, before_insn);
2889 }
2890 \f
2891 /* Functions to query dataflow information. */
2892
2893
2894 int
2895 df_insn_regno_def_p (df, bb, insn, regno)
2896 struct df *df;
2897 basic_block bb ATTRIBUTE_UNUSED;
2898 rtx insn;
2899 unsigned int regno;
2900 {
2901 unsigned int uid;
2902 struct df_link *link;
2903
2904 uid = INSN_UID (insn);
2905
2906 for (link = df->insns[uid].defs; link; link = link->next)
2907 {
2908 struct ref *def = link->ref;
2909
2910 if (DF_REF_REGNO (def) == regno)
2911 return 1;
2912 }
2913
2914 return 0;
2915 }
2916
2917
2918 static int
2919 df_def_dominates_all_uses_p (df, def)
2920 struct df *df ATTRIBUTE_UNUSED;
2921 struct ref *def;
2922 {
2923 struct df_link *du_link;
2924
2925 /* Follow def-use chain to find all the uses of this def. */
2926 for (du_link = DF_REF_CHAIN (def); du_link; du_link = du_link->next)
2927 {
2928 struct ref *use = du_link->ref;
2929 struct df_link *ud_link;
2930
2931 /* Follow use-def chain to check all the defs for this use. */
2932 for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
2933 if (ud_link->ref != def)
2934 return 0;
2935 }
2936 return 1;
2937 }
2938
2939
2940 int
2941 df_insn_dominates_all_uses_p (df, bb, insn)
2942 struct df *df;
2943 basic_block bb ATTRIBUTE_UNUSED;
2944 rtx insn;
2945 {
2946 unsigned int uid;
2947 struct df_link *link;
2948
2949 uid = INSN_UID (insn);
2950
2951 for (link = df->insns[uid].defs; link; link = link->next)
2952 {
2953 struct ref *def = link->ref;
2954
2955 if (! df_def_dominates_all_uses_p (df, def))
2956 return 0;
2957 }
2958
2959 return 1;
2960 }
2961
2962
2963 /* Return nonzero if all DF dominates all the uses within the bitmap
2964 BLOCKS. */
2965 static int
2966 df_def_dominates_uses_p (df, def, blocks)
2967 struct df *df ATTRIBUTE_UNUSED;
2968 struct ref *def;
2969 bitmap blocks;
2970 {
2971 struct df_link *du_link;
2972
2973 /* Follow def-use chain to find all the uses of this def. */
2974 for (du_link = DF_REF_CHAIN (def); du_link; du_link = du_link->next)
2975 {
2976 struct ref *use = du_link->ref;
2977 struct df_link *ud_link;
2978
2979 /* Only worry about the uses within BLOCKS. For example,
2980 consider a register defined within a loop that is live at the
2981 loop exits. */
2982 if (bitmap_bit_p (blocks, DF_REF_BBNO (use)))
2983 {
2984 /* Follow use-def chain to check all the defs for this use. */
2985 for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
2986 if (ud_link->ref != def)
2987 return 0;
2988 }
2989 }
2990 return 1;
2991 }
2992
2993
2994 /* Return nonzero if all the defs of INSN within BB dominates
2995 all the corresponding uses. */
2996 int
2997 df_insn_dominates_uses_p (df, bb, insn, blocks)
2998 struct df *df;
2999 basic_block bb ATTRIBUTE_UNUSED;
3000 rtx insn;
3001 bitmap blocks;
3002 {
3003 unsigned int uid;
3004 struct df_link *link;
3005
3006 uid = INSN_UID (insn);
3007
3008 for (link = df->insns[uid].defs; link; link = link->next)
3009 {
3010 struct ref *def = link->ref;
3011
3012 /* Only consider the defs within BLOCKS. */
3013 if (bitmap_bit_p (blocks, DF_REF_BBNO (def))
3014 && ! df_def_dominates_uses_p (df, def, blocks))
3015 return 0;
3016 }
3017 return 1;
3018 }
3019
3020
3021 /* Return the basic block that REG referenced in or NULL if referenced
3022 in multiple basic blocks. */
3023 basic_block
3024 df_regno_bb (df, regno)
3025 struct df *df;
3026 unsigned int regno;
3027 {
3028 struct df_link *defs = df->regs[regno].defs;
3029 struct df_link *uses = df->regs[regno].uses;
3030 struct ref *def = defs ? defs->ref : 0;
3031 struct ref *use = uses ? uses->ref : 0;
3032 basic_block bb_def = def ? DF_REF_BB (def) : 0;
3033 basic_block bb_use = use ? DF_REF_BB (use) : 0;
3034
3035 /* Compare blocks of first def and last use. ???? FIXME. What if
3036 the reg-def and reg-use lists are not correctly ordered. */
3037 return bb_def == bb_use ? bb_def : 0;
3038 }
3039
3040
3041 /* Return nonzero if REG used in multiple basic blocks. */
3042 int
3043 df_reg_global_p (df, reg)
3044 struct df *df;
3045 rtx reg;
3046 {
3047 return df_regno_bb (df, REGNO (reg)) != 0;
3048 }
3049
3050
3051 /* Return total lifetime (in insns) of REG. */
3052 int
3053 df_reg_lifetime (df, reg)
3054 struct df *df;
3055 rtx reg;
3056 {
3057 return df->regs[REGNO (reg)].lifetime;
3058 }
3059
3060
3061 /* Return nonzero if REG live at start of BB. */
3062 int
3063 df_bb_reg_live_start_p (df, bb, reg)
3064 struct df *df ATTRIBUTE_UNUSED;
3065 basic_block bb;
3066 rtx reg;
3067 {
3068 struct bb_info *bb_info = DF_BB_INFO (df, bb);
3069
3070 #ifdef ENABLE_CHECKING
3071 if (! bb_info->lr_in)
3072 abort ();
3073 #endif
3074
3075 return bitmap_bit_p (bb_info->lr_in, REGNO (reg));
3076 }
3077
3078
3079 /* Return nonzero if REG live at end of BB. */
3080 int
3081 df_bb_reg_live_end_p (df, bb, reg)
3082 struct df *df ATTRIBUTE_UNUSED;
3083 basic_block bb;
3084 rtx reg;
3085 {
3086 struct bb_info *bb_info = DF_BB_INFO (df, bb);
3087
3088 #ifdef ENABLE_CHECKING
3089 if (! bb_info->lr_in)
3090 abort ();
3091 #endif
3092
3093 return bitmap_bit_p (bb_info->lr_out, REGNO (reg));
3094 }
3095
3096
3097 /* Return -1 if life of REG1 before life of REG2, 1 if life of REG1
3098 after life of REG2, or 0, if the lives overlap. */
3099 int
3100 df_bb_regs_lives_compare (df, bb, reg1, reg2)
3101 struct df *df;
3102 basic_block bb;
3103 rtx reg1;
3104 rtx reg2;
3105 {
3106 unsigned int regno1 = REGNO (reg1);
3107 unsigned int regno2 = REGNO (reg2);
3108 struct ref *def1;
3109 struct ref *use1;
3110 struct ref *def2;
3111 struct ref *use2;
3112
3113
3114 /* The regs must be local to BB. */
3115 if (df_regno_bb (df, regno1) != bb
3116 || df_regno_bb (df, regno2) != bb)
3117 abort ();
3118
3119 def2 = df_bb_regno_first_def_find (df, bb, regno2);
3120 use1 = df_bb_regno_last_use_find (df, bb, regno1);
3121
3122 if (DF_INSN_LUID (df, DF_REF_INSN (def2))
3123 > DF_INSN_LUID (df, DF_REF_INSN (use1)))
3124 return -1;
3125
3126 def1 = df_bb_regno_first_def_find (df, bb, regno1);
3127 use2 = df_bb_regno_last_use_find (df, bb, regno2);
3128
3129 if (DF_INSN_LUID (df, DF_REF_INSN (def1))
3130 > DF_INSN_LUID (df, DF_REF_INSN (use2)))
3131 return 1;
3132
3133 return 0;
3134 }
3135
3136
3137 /* Return last use of REGNO within BB. */
3138 static struct ref *
3139 df_bb_regno_last_use_find (df, bb, regno)
3140 struct df * df;
3141 basic_block bb ATTRIBUTE_UNUSED;
3142 unsigned int regno;
3143 {
3144 struct df_link *link;
3145
3146 /* This assumes that the reg-use list is ordered such that for any
3147 BB, the last use is found first. However, since the BBs are not
3148 ordered, the first use in the chain is not necessarily the last
3149 use in the function. */
3150 for (link = df->regs[regno].uses; link; link = link->next)
3151 {
3152 struct ref *use = link->ref;
3153
3154 if (DF_REF_BB (use) == bb)
3155 return use;
3156 }
3157 return 0;
3158 }
3159
3160
3161 /* Return first def of REGNO within BB. */
3162 static struct ref *
3163 df_bb_regno_first_def_find (df, bb, regno)
3164 struct df * df;
3165 basic_block bb ATTRIBUTE_UNUSED;
3166 unsigned int regno;
3167 {
3168 struct df_link *link;
3169
3170 /* This assumes that the reg-def list is ordered such that for any
3171 BB, the first def is found first. However, since the BBs are not
3172 ordered, the first def in the chain is not necessarily the first
3173 def in the function. */
3174 for (link = df->regs[regno].defs; link; link = link->next)
3175 {
3176 struct ref *def = link->ref;
3177
3178 if (DF_REF_BB (def) == bb)
3179 return def;
3180 }
3181 return 0;
3182 }
3183
3184
3185 /* Return first use of REGNO inside INSN within BB. */
3186 static struct ref *
3187 df_bb_insn_regno_last_use_find (df, bb, insn, regno)
3188 struct df * df;
3189 basic_block bb ATTRIBUTE_UNUSED;
3190 rtx insn;
3191 unsigned int regno;
3192 {
3193 unsigned int uid;
3194 struct df_link *link;
3195
3196 uid = INSN_UID (insn);
3197
3198 for (link = df->insns[uid].uses; link; link = link->next)
3199 {
3200 struct ref *use = link->ref;
3201
3202 if (DF_REF_REGNO (use) == regno)
3203 return use;
3204 }
3205
3206 return 0;
3207 }
3208
3209
3210 /* Return first def of REGNO inside INSN within BB. */
3211 static struct ref *
3212 df_bb_insn_regno_first_def_find (df, bb, insn, regno)
3213 struct df * df;
3214 basic_block bb ATTRIBUTE_UNUSED;
3215 rtx insn;
3216 unsigned int regno;
3217 {
3218 unsigned int uid;
3219 struct df_link *link;
3220
3221 uid = INSN_UID (insn);
3222
3223 for (link = df->insns[uid].defs; link; link = link->next)
3224 {
3225 struct ref *def = link->ref;
3226
3227 if (DF_REF_REGNO (def) == regno)
3228 return def;
3229 }
3230
3231 return 0;
3232 }
3233
3234
3235 /* Return insn using REG if the BB contains only a single
3236 use and def of REG. */
3237 rtx
3238 df_bb_single_def_use_insn_find (df, bb, insn, reg)
3239 struct df * df;
3240 basic_block bb;
3241 rtx insn;
3242 rtx reg;
3243 {
3244 struct ref *def;
3245 struct ref *use;
3246 struct df_link *du_link;
3247
3248 def = df_bb_insn_regno_first_def_find (df, bb, insn, REGNO (reg));
3249
3250 if (! def)
3251 abort ();
3252
3253 du_link = DF_REF_CHAIN (def);
3254
3255 if (! du_link)
3256 return NULL_RTX;
3257
3258 use = du_link->ref;
3259
3260 /* Check if def is dead. */
3261 if (! use)
3262 return NULL_RTX;
3263
3264 /* Check for multiple uses. */
3265 if (du_link->next)
3266 return NULL_RTX;
3267
3268 return DF_REF_INSN (use);
3269 }
3270 \f
3271 /* Functions for debugging/dumping dataflow information. */
3272
3273
3274 /* Dump a def-use or use-def chain for REF to FILE. */
3275 static void
3276 df_chain_dump (link, file)
3277 struct df_link *link;
3278 FILE *file;
3279 {
3280 fprintf (file, "{ ");
3281 for (; link; link = link->next)
3282 {
3283 fprintf (file, "%c%d ",
3284 DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
3285 DF_REF_ID (link->ref));
3286 }
3287 fprintf (file, "}");
3288 }
3289
3290
3291 /* Dump a chain of refs with the associated regno. */
3292 static void
3293 df_chain_dump_regno (link, file)
3294 struct df_link *link;
3295 FILE *file;
3296 {
3297 fprintf (file, "{ ");
3298 for (; link; link = link->next)
3299 {
3300 fprintf (file, "%c%d(%d) ",
3301 DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
3302 DF_REF_ID (link->ref),
3303 DF_REF_REGNO (link->ref));
3304 }
3305 fprintf (file, "}");
3306 }
3307
3308
3309 /* Dump dataflow info. */
3310 void
3311 df_dump (df, flags, file)
3312 struct df *df;
3313 int flags;
3314 FILE *file;
3315 {
3316 unsigned int j;
3317 basic_block bb;
3318
3319 if (! df || ! file)
3320 return;
3321
3322 fprintf (file, "\nDataflow summary:\n");
3323 fprintf (file, "n_regs = %d, n_defs = %d, n_uses = %d, n_bbs = %d\n",
3324 df->n_regs, df->n_defs, df->n_uses, df->n_bbs);
3325
3326 if (flags & DF_RD)
3327 {
3328 basic_block bb;
3329
3330 fprintf (file, "Reaching defs:\n");
3331 FOR_EACH_BB (bb)
3332 {
3333 struct bb_info *bb_info = DF_BB_INFO (df, bb);
3334
3335 if (! bb_info->rd_in)
3336 continue;
3337
3338 fprintf (file, "bb %d in \t", bb->index);
3339 dump_bitmap (file, bb_info->rd_in);
3340 fprintf (file, "bb %d gen \t", bb->index);
3341 dump_bitmap (file, bb_info->rd_gen);
3342 fprintf (file, "bb %d kill\t", bb->index);
3343 dump_bitmap (file, bb_info->rd_kill);
3344 fprintf (file, "bb %d out \t", bb->index);
3345 dump_bitmap (file, bb_info->rd_out);
3346 }
3347 }
3348
3349 if (flags & DF_UD_CHAIN)
3350 {
3351 fprintf (file, "Use-def chains:\n");
3352 for (j = 0; j < df->n_defs; j++)
3353 {
3354 if (df->defs[j])
3355 {
3356 fprintf (file, "d%d bb %d luid %d insn %d reg %d ",
3357 j, DF_REF_BBNO (df->defs[j]),
3358 DF_INSN_LUID (df, DF_REF_INSN (df->defs[j])),
3359 DF_REF_INSN_UID (df->defs[j]),
3360 DF_REF_REGNO (df->defs[j]));
3361 if (df->defs[j]->flags & DF_REF_READ_WRITE)
3362 fprintf (file, "read/write ");
3363 df_chain_dump (DF_REF_CHAIN (df->defs[j]), file);
3364 fprintf (file, "\n");
3365 }
3366 }
3367 }
3368
3369 if (flags & DF_RU)
3370 {
3371 fprintf (file, "Reaching uses:\n");
3372 FOR_EACH_BB (bb)
3373 {
3374 struct bb_info *bb_info = DF_BB_INFO (df, bb);
3375
3376 if (! bb_info->ru_in)
3377 continue;
3378
3379 fprintf (file, "bb %d in \t", bb->index);
3380 dump_bitmap (file, bb_info->ru_in);
3381 fprintf (file, "bb %d gen \t", bb->index);
3382 dump_bitmap (file, bb_info->ru_gen);
3383 fprintf (file, "bb %d kill\t", bb->index);
3384 dump_bitmap (file, bb_info->ru_kill);
3385 fprintf (file, "bb %d out \t", bb->index);
3386 dump_bitmap (file, bb_info->ru_out);
3387 }
3388 }
3389
3390 if (flags & DF_DU_CHAIN)
3391 {
3392 fprintf (file, "Def-use chains:\n");
3393 for (j = 0; j < df->n_uses; j++)
3394 {
3395 if (df->uses[j])
3396 {
3397 fprintf (file, "u%d bb %d luid %d insn %d reg %d ",
3398 j, DF_REF_BBNO (df->uses[j]),
3399 DF_INSN_LUID (df, DF_REF_INSN (df->uses[j])),
3400 DF_REF_INSN_UID (df->uses[j]),
3401 DF_REF_REGNO (df->uses[j]));
3402 if (df->uses[j]->flags & DF_REF_READ_WRITE)
3403 fprintf (file, "read/write ");
3404 df_chain_dump (DF_REF_CHAIN (df->uses[j]), file);
3405 fprintf (file, "\n");
3406 }
3407 }
3408 }
3409
3410 if (flags & DF_LR)
3411 {
3412 fprintf (file, "Live regs:\n");
3413 FOR_EACH_BB (bb)
3414 {
3415 struct bb_info *bb_info = DF_BB_INFO (df, bb);
3416
3417 if (! bb_info->lr_in)
3418 continue;
3419
3420 fprintf (file, "bb %d in \t", bb->index);
3421 dump_bitmap (file, bb_info->lr_in);
3422 fprintf (file, "bb %d use \t", bb->index);
3423 dump_bitmap (file, bb_info->lr_use);
3424 fprintf (file, "bb %d def \t", bb->index);
3425 dump_bitmap (file, bb_info->lr_def);
3426 fprintf (file, "bb %d out \t", bb->index);
3427 dump_bitmap (file, bb_info->lr_out);
3428 }
3429 }
3430
3431 if (flags & (DF_REG_INFO | DF_RD_CHAIN | DF_RU_CHAIN))
3432 {
3433 struct reg_info *reg_info = df->regs;
3434
3435 fprintf (file, "Register info:\n");
3436 for (j = 0; j < df->n_regs; j++)
3437 {
3438 if (((flags & DF_REG_INFO)
3439 && (reg_info[j].n_uses || reg_info[j].n_defs))
3440 || ((flags & DF_RD_CHAIN) && reg_info[j].defs)
3441 || ((flags & DF_RU_CHAIN) && reg_info[j].uses))
3442 {
3443 fprintf (file, "reg %d", j);
3444 if ((flags & DF_RD_CHAIN) && (flags & DF_RU_CHAIN))
3445 {
3446 basic_block bb = df_regno_bb (df, j);
3447
3448 if (bb)
3449 fprintf (file, " bb %d", bb->index);
3450 else
3451 fprintf (file, " bb ?");
3452 }
3453 if (flags & DF_REG_INFO)
3454 {
3455 fprintf (file, " life %d", reg_info[j].lifetime);
3456 }
3457
3458 if ((flags & DF_REG_INFO) || (flags & DF_RD_CHAIN))
3459 {
3460 fprintf (file, " defs ");
3461 if (flags & DF_REG_INFO)
3462 fprintf (file, "%d ", reg_info[j].n_defs);
3463 if (flags & DF_RD_CHAIN)
3464 df_chain_dump (reg_info[j].defs, file);
3465 }
3466
3467 if ((flags & DF_REG_INFO) || (flags & DF_RU_CHAIN))
3468 {
3469 fprintf (file, " uses ");
3470 if (flags & DF_REG_INFO)
3471 fprintf (file, "%d ", reg_info[j].n_uses);
3472 if (flags & DF_RU_CHAIN)
3473 df_chain_dump (reg_info[j].uses, file);
3474 }
3475
3476 fprintf (file, "\n");
3477 }
3478 }
3479 }
3480 fprintf (file, "\n");
3481 }
3482
3483
3484 void
3485 df_insn_debug (df, insn, file)
3486 struct df *df;
3487 rtx insn;
3488 FILE *file;
3489 {
3490 unsigned int uid;
3491 int bbi;
3492
3493 uid = INSN_UID (insn);
3494 if (uid >= df->insn_size)
3495 return;
3496
3497 if (df->insns[uid].defs)
3498 bbi = DF_REF_BBNO (df->insns[uid].defs->ref);
3499 else if (df->insns[uid].uses)
3500 bbi = DF_REF_BBNO (df->insns[uid].uses->ref);
3501 else
3502 bbi = -1;
3503
3504 fprintf (file, "insn %d bb %d luid %d defs ",
3505 uid, bbi, DF_INSN_LUID (df, insn));
3506 df_chain_dump (df->insns[uid].defs, file);
3507 fprintf (file, " uses ");
3508 df_chain_dump (df->insns[uid].uses, file);
3509 fprintf (file, "\n");
3510 }
3511
3512
3513 void
3514 df_insn_debug_regno (df, insn, file)
3515 struct df *df;
3516 rtx insn;
3517 FILE *file;
3518 {
3519 unsigned int uid;
3520 int bbi;
3521
3522 uid = INSN_UID (insn);
3523 if (uid >= df->insn_size)
3524 return;
3525
3526 if (df->insns[uid].defs)
3527 bbi = DF_REF_BBNO (df->insns[uid].defs->ref);
3528 else if (df->insns[uid].uses)
3529 bbi = DF_REF_BBNO (df->insns[uid].uses->ref);
3530 else
3531 bbi = -1;
3532
3533 fprintf (file, "insn %d bb %d luid %d defs ",
3534 uid, bbi, DF_INSN_LUID (df, insn));
3535 df_chain_dump_regno (df->insns[uid].defs, file);
3536 fprintf (file, " uses ");
3537 df_chain_dump_regno (df->insns[uid].uses, file);
3538 fprintf (file, "\n");
3539 }
3540
3541
3542 static void
3543 df_regno_debug (df, regno, file)
3544 struct df *df;
3545 unsigned int regno;
3546 FILE *file;
3547 {
3548 if (regno >= df->reg_size)
3549 return;
3550
3551 fprintf (file, "reg %d life %d defs ",
3552 regno, df->regs[regno].lifetime);
3553 df_chain_dump (df->regs[regno].defs, file);
3554 fprintf (file, " uses ");
3555 df_chain_dump (df->regs[regno].uses, file);
3556 fprintf (file, "\n");
3557 }
3558
3559
3560 static void
3561 df_ref_debug (df, ref, file)
3562 struct df *df;
3563 struct ref *ref;
3564 FILE *file;
3565 {
3566 fprintf (file, "%c%d ",
3567 DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
3568 DF_REF_ID (ref));
3569 fprintf (file, "reg %d bb %d luid %d insn %d chain ",
3570 DF_REF_REGNO (ref),
3571 DF_REF_BBNO (ref),
3572 DF_INSN_LUID (df, DF_REF_INSN (ref)),
3573 INSN_UID (DF_REF_INSN (ref)));
3574 df_chain_dump (DF_REF_CHAIN (ref), file);
3575 fprintf (file, "\n");
3576 }
3577 \f
3578 /* Functions for debugging from GDB. */
3579
3580 void
3581 debug_df_insn (insn)
3582 rtx insn;
3583 {
3584 df_insn_debug (ddf, insn, stderr);
3585 debug_rtx (insn);
3586 }
3587
3588
3589 void
3590 debug_df_reg (reg)
3591 rtx reg;
3592 {
3593 df_regno_debug (ddf, REGNO (reg), stderr);
3594 }
3595
3596
3597 void
3598 debug_df_regno (regno)
3599 unsigned int regno;
3600 {
3601 df_regno_debug (ddf, regno, stderr);
3602 }
3603
3604
3605 void
3606 debug_df_ref (ref)
3607 struct ref *ref;
3608 {
3609 df_ref_debug (ddf, ref, stderr);
3610 }
3611
3612
3613 void
3614 debug_df_defno (defno)
3615 unsigned int defno;
3616 {
3617 df_ref_debug (ddf, ddf->defs[defno], stderr);
3618 }
3619
3620
3621 void
3622 debug_df_useno (defno)
3623 unsigned int defno;
3624 {
3625 df_ref_debug (ddf, ddf->uses[defno], stderr);
3626 }
3627
3628
3629 void
3630 debug_df_chain (link)
3631 struct df_link *link;
3632 {
3633 df_chain_dump (link, stderr);
3634 fputc ('\n', stderr);
3635 }
3636 \f
3637
3638 /* Hybrid search algorithm from "Implementation Techniques for
3639 Efficient Data-Flow Analysis of Large Programs". */
3640 static void
3641 hybrid_search_bitmap (block, in, out, gen, kill, dir,
3642 conf_op, transfun, visited, pending,
3643 data)
3644 basic_block block;
3645 bitmap *in, *out, *gen, *kill;
3646 enum df_flow_dir dir;
3647 enum df_confluence_op conf_op;
3648 transfer_function_bitmap transfun;
3649 sbitmap visited;
3650 sbitmap pending;
3651 void *data;
3652 {
3653 int changed;
3654 int i = block->index;
3655 edge e;
3656 basic_block bb = block;
3657
3658 SET_BIT (visited, block->index);
3659 if (TEST_BIT (pending, block->index))
3660 {
3661 if (dir == DF_FORWARD)
3662 {
3663 /* Calculate <conf_op> of predecessor_outs. */
3664 bitmap_zero (in[i]);
3665 for (e = bb->pred; e != 0; e = e->pred_next)
3666 {
3667 if (e->src == ENTRY_BLOCK_PTR)
3668 continue;
3669 switch (conf_op)
3670 {
3671 case DF_UNION:
3672 bitmap_a_or_b (in[i], in[i], out[e->src->index]);
3673 break;
3674 case DF_INTERSECTION:
3675 bitmap_a_and_b (in[i], in[i], out[e->src->index]);
3676 break;
3677 }
3678 }
3679 }
3680 else
3681 {
3682 /* Calculate <conf_op> of successor ins. */
3683 bitmap_zero (out[i]);
3684 for (e = bb->succ; e != 0; e = e->succ_next)
3685 {
3686 if (e->dest == EXIT_BLOCK_PTR)
3687 continue;
3688 switch (conf_op)
3689 {
3690 case DF_UNION:
3691 bitmap_a_or_b (out[i], out[i], in[e->dest->index]);
3692 break;
3693 case DF_INTERSECTION:
3694 bitmap_a_and_b (out[i], out[i], in[e->dest->index]);
3695 break;
3696 }
3697 }
3698 }
3699 /* Common part */
3700 (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
3701 RESET_BIT (pending, i);
3702 if (changed)
3703 {
3704 if (dir == DF_FORWARD)
3705 {
3706 for (e = bb->succ; e != 0; e = e->succ_next)
3707 {
3708 if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
3709 continue;
3710 SET_BIT (pending, e->dest->index);
3711 }
3712 }
3713 else
3714 {
3715 for (e = bb->pred; e != 0; e = e->pred_next)
3716 {
3717 if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
3718 continue;
3719 SET_BIT (pending, e->src->index);
3720 }
3721 }
3722 }
3723 }
3724 if (dir == DF_FORWARD)
3725 {
3726 for (e = bb->succ; e != 0; e = e->succ_next)
3727 {
3728 if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
3729 continue;
3730 if (!TEST_BIT (visited, e->dest->index))
3731 hybrid_search_bitmap (e->dest, in, out, gen, kill, dir,
3732 conf_op, transfun, visited, pending,
3733 data);
3734 }
3735 }
3736 else
3737 {
3738 for (e = bb->pred; e != 0; e = e->pred_next)
3739 {
3740 if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
3741 continue;
3742 if (!TEST_BIT (visited, e->src->index))
3743 hybrid_search_bitmap (e->src, in, out, gen, kill, dir,
3744 conf_op, transfun, visited, pending,
3745 data);
3746 }
3747 }
3748 }
3749
3750
3751 /* Hybrid search for sbitmaps, rather than bitmaps. */
3752 static void
3753 hybrid_search_sbitmap (block, in, out, gen, kill, dir,
3754 conf_op, transfun, visited, pending,
3755 data)
3756 basic_block block;
3757 sbitmap *in, *out, *gen, *kill;
3758 enum df_flow_dir dir;
3759 enum df_confluence_op conf_op;
3760 transfer_function_sbitmap transfun;
3761 sbitmap visited;
3762 sbitmap pending;
3763 void *data;
3764 {
3765 int changed;
3766 int i = block->index;
3767 edge e;
3768 basic_block bb = block;
3769
3770 SET_BIT (visited, block->index);
3771 if (TEST_BIT (pending, block->index))
3772 {
3773 if (dir == DF_FORWARD)
3774 {
3775 /* Calculate <conf_op> of predecessor_outs. */
3776 sbitmap_zero (in[i]);
3777 for (e = bb->pred; e != 0; e = e->pred_next)
3778 {
3779 if (e->src == ENTRY_BLOCK_PTR)
3780 continue;
3781 switch (conf_op)
3782 {
3783 case DF_UNION:
3784 sbitmap_a_or_b (in[i], in[i], out[e->src->index]);
3785 break;
3786 case DF_INTERSECTION:
3787 sbitmap_a_and_b (in[i], in[i], out[e->src->index]);
3788 break;
3789 }
3790 }
3791 }
3792 else
3793 {
3794 /* Calculate <conf_op> of successor ins. */
3795 sbitmap_zero (out[i]);
3796 for (e = bb->succ; e != 0; e = e->succ_next)
3797 {
3798 if (e->dest == EXIT_BLOCK_PTR)
3799 continue;
3800 switch (conf_op)
3801 {
3802 case DF_UNION:
3803 sbitmap_a_or_b (out[i], out[i], in[e->dest->index]);
3804 break;
3805 case DF_INTERSECTION:
3806 sbitmap_a_and_b (out[i], out[i], in[e->dest->index]);
3807 break;
3808 }
3809 }
3810 }
3811 /* Common part. */
3812 (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
3813 RESET_BIT (pending, i);
3814 if (changed)
3815 {
3816 if (dir == DF_FORWARD)
3817 {
3818 for (e = bb->succ; e != 0; e = e->succ_next)
3819 {
3820 if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
3821 continue;
3822 SET_BIT (pending, e->dest->index);
3823 }
3824 }
3825 else
3826 {
3827 for (e = bb->pred; e != 0; e = e->pred_next)
3828 {
3829 if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
3830 continue;
3831 SET_BIT (pending, e->src->index);
3832 }
3833 }
3834 }
3835 }
3836 if (dir == DF_FORWARD)
3837 {
3838 for (e = bb->succ; e != 0; e = e->succ_next)
3839 {
3840 if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
3841 continue;
3842 if (!TEST_BIT (visited, e->dest->index))
3843 hybrid_search_sbitmap (e->dest, in, out, gen, kill, dir,
3844 conf_op, transfun, visited, pending,
3845 data);
3846 }
3847 }
3848 else
3849 {
3850 for (e = bb->pred; e != 0; e = e->pred_next)
3851 {
3852 if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
3853 continue;
3854 if (!TEST_BIT (visited, e->src->index))
3855 hybrid_search_sbitmap (e->src, in, out, gen, kill, dir,
3856 conf_op, transfun, visited, pending,
3857 data);
3858 }
3859 }
3860 }
3861
3862
3863 /* gen = GEN set.
3864 kill = KILL set.
3865 in, out = Filled in by function.
3866 blocks = Blocks to analyze.
3867 dir = Dataflow direction.
3868 conf_op = Confluence operation.
3869 transfun = Transfer function.
3870 order = Order to iterate in. (Should map block numbers -> order)
3871 data = Whatever you want. It's passed to the transfer function.
3872
3873 This function will perform iterative bitvector dataflow, producing
3874 the in and out sets. Even if you only want to perform it for a
3875 small number of blocks, the vectors for in and out must be large
3876 enough for *all* blocks, because changing one block might affect
3877 others. However, it'll only put what you say to analyze on the
3878 initial worklist.
3879
3880 For forward problems, you probably want to pass in a mapping of
3881 block number to rc_order (like df->inverse_rc_map).
3882 */
3883 void
3884 iterative_dataflow_sbitmap (in, out, gen, kill, blocks,
3885 dir, conf_op, transfun, order, data)
3886 sbitmap *in, *out, *gen, *kill;
3887 bitmap blocks;
3888 enum df_flow_dir dir;
3889 enum df_confluence_op conf_op;
3890 transfer_function_sbitmap transfun;
3891 int *order;
3892 void *data;
3893 {
3894 int i;
3895 fibheap_t worklist;
3896 basic_block bb;
3897 sbitmap visited, pending;
3898
3899 pending = sbitmap_alloc (last_basic_block);
3900 visited = sbitmap_alloc (last_basic_block);
3901 sbitmap_zero (pending);
3902 sbitmap_zero (visited);
3903 worklist = fibheap_new ();
3904
3905 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
3906 {
3907 fibheap_insert (worklist, order[i], (void *) (size_t) i);
3908 SET_BIT (pending, i);
3909 if (dir == DF_FORWARD)
3910 sbitmap_copy (out[i], gen[i]);
3911 else
3912 sbitmap_copy (in[i], gen[i]);
3913 });
3914
3915 while (sbitmap_first_set_bit (pending) != -1)
3916 {
3917 while (!fibheap_empty (worklist))
3918 {
3919 i = (size_t) fibheap_extract_min (worklist);
3920 bb = BASIC_BLOCK (i);
3921 if (!TEST_BIT (visited, bb->index))
3922 hybrid_search_sbitmap (bb, in, out, gen, kill, dir,
3923 conf_op, transfun, visited, pending, data);
3924 }
3925
3926 if (sbitmap_first_set_bit (pending) != -1)
3927 {
3928 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
3929 {
3930 fibheap_insert (worklist, order[i], (void *) (size_t) i);
3931 });
3932 sbitmap_zero (visited);
3933 }
3934 else
3935 {
3936 break;
3937 }
3938 }
3939
3940 sbitmap_free (pending);
3941 sbitmap_free (visited);
3942 fibheap_delete (worklist);
3943 }
3944
3945
3946 /* Exactly the same as iterative_dataflow_sbitmap, except it works on
3947 bitmaps instead. */
3948 void
3949 iterative_dataflow_bitmap (in, out, gen, kill, blocks,
3950 dir, conf_op, transfun, order, data)
3951 bitmap *in, *out, *gen, *kill;
3952 bitmap blocks;
3953 enum df_flow_dir dir;
3954 enum df_confluence_op conf_op;
3955 transfer_function_bitmap transfun;
3956 int *order;
3957 void *data;
3958 {
3959 int i;
3960 fibheap_t worklist;
3961 basic_block bb;
3962 sbitmap visited, pending;
3963
3964 pending = sbitmap_alloc (last_basic_block);
3965 visited = sbitmap_alloc (last_basic_block);
3966 sbitmap_zero (pending);
3967 sbitmap_zero (visited);
3968 worklist = fibheap_new ();
3969
3970 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
3971 {
3972 fibheap_insert (worklist, order[i], (void *) (size_t) i);
3973 SET_BIT (pending, i);
3974 if (dir == DF_FORWARD)
3975 bitmap_copy (out[i], gen[i]);
3976 else
3977 bitmap_copy (in[i], gen[i]);
3978 });
3979
3980 while (sbitmap_first_set_bit (pending) != -1)
3981 {
3982 while (!fibheap_empty (worklist))
3983 {
3984 i = (size_t) fibheap_extract_min (worklist);
3985 bb = BASIC_BLOCK (i);
3986 if (!TEST_BIT (visited, bb->index))
3987 hybrid_search_bitmap (bb, in, out, gen, kill, dir,
3988 conf_op, transfun, visited, pending, data);
3989 }
3990
3991 if (sbitmap_first_set_bit (pending) != -1)
3992 {
3993 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
3994 {
3995 fibheap_insert (worklist, order[i], (void *) (size_t) i);
3996 });
3997 sbitmap_zero (visited);
3998 }
3999 else
4000 {
4001 break;
4002 }
4003 }
4004 sbitmap_free (pending);
4005 sbitmap_free (visited);
4006 fibheap_delete (worklist);
4007 }
Mirror of the offical gcc git repository hosted at gcc.gnu.org