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