|
0
|
1 /* Form lists of pseudo register references for autoinc optimization
|
|
|
2 for GNU compiler. This is part of flow optimization.
|
|
|
3 Copyright (C) 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009
|
|
|
4 Free Software Foundation, Inc.
|
|
|
5 Originally contributed by Michael P. Hayes
|
|
|
6 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
|
|
|
7 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
|
|
|
8 and Kenneth Zadeck (zadeck@naturalbridge.com).
|
|
|
9
|
|
|
10 This file is part of GCC.
|
|
|
11
|
|
|
12 GCC is free software; you can redistribute it and/or modify it under
|
|
|
13 the terms of the GNU General Public License as published by the Free
|
|
|
14 Software Foundation; either version 3, or (at your option) any later
|
|
|
15 version.
|
|
|
16
|
|
|
17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
19 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
20 for more details.
|
|
|
21
|
|
|
22 You should have received a copy of the GNU General Public License
|
|
|
23 along with GCC; see the file COPYING3. If not see
|
|
|
24 <http://www.gnu.org/licenses/>. */
|
|
|
25
|
|
|
26 #ifndef GCC_DF_H
|
|
|
27 #define GCC_DF_H
|
|
|
28
|
|
|
29 #include "bitmap.h"
|
|
|
30 #include "basic-block.h"
|
|
|
31 #include "alloc-pool.h"
|
|
|
32
|
|
|
33 struct dataflow;
|
|
|
34 struct df;
|
|
|
35 struct df_problem;
|
|
|
36 struct df_link;
|
|
|
37 struct df_insn_info;
|
|
|
38 union df_ref_d;
|
|
|
39
|
|
|
40 /* Data flow problems. All problems must have a unique id here. */
|
|
|
41
|
|
|
42 /* Scanning is not really a dataflow problem, but it is useful to have
|
|
|
43 the basic block functions in the vector so that things get done in
|
|
|
44 a uniform manner. The last four problems can be added or deleted
|
|
|
45 at any time are always defined (though LIVE is always there at -O2
|
|
|
46 or higher); the others are always there. */
|
|
|
47 #define DF_SCAN 0
|
|
|
48 #define DF_LR 1 /* Live Registers backward. */
|
|
|
49 #define DF_LIVE 2 /* Live Registers & Uninitialized Registers */
|
|
|
50 #define DF_RD 3 /* Reaching Defs. */
|
|
|
51 #define DF_CHAIN 4 /* Def-Use and/or Use-Def Chains. */
|
|
|
52 #define DF_BYTE_LR 5 /* Subreg tracking lr. */
|
|
|
53 #define DF_NOTE 6 /* REG_DEF and REG_UNUSED notes. */
|
|
|
54
|
|
|
55 #define DF_LAST_PROBLEM_PLUS1 (DF_NOTE + 1)
|
|
|
56
|
|
|
57 /* Dataflow direction. */
|
|
|
58 enum df_flow_dir
|
|
|
59 {
|
|
|
60 DF_NONE,
|
|
|
61 DF_FORWARD,
|
|
|
62 DF_BACKWARD
|
|
|
63 };
|
|
|
64
|
|
|
65 /* Used in the byte scanning to determine if may or must info is to be
|
|
|
66 returned. */
|
|
|
67 enum df_mm
|
|
|
68 {
|
|
|
69 DF_MM_MAY,
|
|
|
70 DF_MM_MUST
|
|
|
71 };
|
|
|
72
|
|
|
73 /* Descriminator for the various df_ref types. */
|
|
|
74 enum df_ref_class {DF_REF_BASE, DF_REF_ARTIFICIAL, DF_REF_REGULAR, DF_REF_EXTRACT};
|
|
|
75
|
|
|
76 /* The first of these us a set of a registers. The remaining three
|
|
|
77 are all uses of a register (the mem_load and mem_store relate to
|
|
|
78 how the register as an addressing operand). */
|
|
|
79 enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE,
|
|
|
80 DF_REF_REG_MEM_LOAD, DF_REF_REG_MEM_STORE};
|
|
|
81
|
|
|
82 enum df_ref_flags
|
|
|
83 {
|
|
|
84 /* This flag is set if this ref occurs inside of a conditional
|
|
|
85 execution instruction. */
|
|
|
86 DF_REF_CONDITIONAL = 1 << 0,
|
|
|
87
|
|
|
88 /* If this flag is set for an artificial use or def, that ref
|
|
|
89 logically happens at the top of the block. If it is not set
|
|
|
90 for an artificial use or def, that ref logically happens at the
|
|
|
91 bottom of the block. This is never set for regular refs. */
|
|
|
92 DF_REF_AT_TOP = 1 << 1,
|
|
|
93
|
|
|
94 /* This flag is set if the use is inside a REG_EQUAL or REG_EQUIV
|
|
|
95 note. */
|
|
|
96 DF_REF_IN_NOTE = 1 << 2,
|
|
|
97
|
|
|
98 /* This bit is true if this ref can make regs_ever_live true for
|
|
|
99 this regno. */
|
|
|
100 DF_HARD_REG_LIVE = 1 << 3,
|
|
|
101
|
|
|
102
|
|
|
103 /* This flag is set if this ref is a partial use or def of the
|
|
|
104 associated register. */
|
|
|
105 DF_REF_PARTIAL = 1 << 4,
|
|
|
106
|
|
|
107 /* Read-modify-write refs generate both a use and a def and
|
|
|
108 these are marked with this flag to show that they are not
|
|
|
109 independent. */
|
|
|
110 DF_REF_READ_WRITE = 1 << 5,
|
|
|
111
|
|
|
112 /* This flag is set if this ref, generally a def, may clobber the
|
|
|
113 referenced register. This is generally only set for hard
|
|
|
114 registers that cross a call site. With better information
|
|
|
115 about calls, some of these could be changed in the future to
|
|
|
116 DF_REF_MUST_CLOBBER. */
|
|
|
117 DF_REF_MAY_CLOBBER = 1 << 6,
|
|
|
118
|
|
|
119 /* This flag is set if this ref, generally a def, is a real
|
|
|
120 clobber. This is not currently set for registers live across a
|
|
|
121 call because that clobbering may or may not happen.
|
|
|
122
|
|
|
123 Most of the uses of this are with sets that have a
|
|
|
124 GET_CODE(..)==CLOBBER. Note that this is set even if the
|
|
|
125 clobber is to a subreg. So in order to tell if the clobber
|
|
|
126 wipes out the entire register, it is necessary to also check
|
|
|
127 the DF_REF_PARTIAL flag. */
|
|
|
128 DF_REF_MUST_CLOBBER = 1 << 7,
|
|
|
129
|
|
|
130
|
|
|
131 /* If the ref has one of the following two flags set, then the
|
|
|
132 struct df_ref can be cast to struct df_ref_extract to access
|
|
|
133 the width and offset fields. */
|
|
|
134
|
|
|
135 /* This flag is set if the ref contains a SIGN_EXTRACT. */
|
|
|
136 DF_REF_SIGN_EXTRACT = 1 << 8,
|
|
|
137
|
|
|
138 /* This flag is set if the ref contains a ZERO_EXTRACT. */
|
|
|
139 DF_REF_ZERO_EXTRACT = 1 << 9,
|
|
|
140
|
|
|
141 /* This flag is set if the ref contains a STRICT_LOW_PART. */
|
|
|
142 DF_REF_STRICT_LOW_PART = 1 << 10,
|
|
|
143
|
|
|
144 /* This flag is set if the ref contains a SUBREG. */
|
|
|
145 DF_REF_SUBREG = 1 << 11,
|
|
|
146
|
|
|
147
|
|
|
148 /* This bit is true if this ref is part of a multiword hardreg. */
|
|
|
149 DF_REF_MW_HARDREG = 1 << 12,
|
|
|
150
|
|
|
151 /* This flag is set if this ref is a usage of the stack pointer by
|
|
|
152 a function call. */
|
|
|
153 DF_REF_CALL_STACK_USAGE = 1 << 13,
|
|
|
154
|
|
|
155 /* This flag is used for verification of existing refs. */
|
|
|
156 DF_REF_REG_MARKER = 1 << 14,
|
|
|
157
|
|
|
158 /* This flag is set if this ref is inside a pre/post modify. */
|
|
|
159 DF_REF_PRE_POST_MODIFY = 1 << 15
|
|
|
160
|
|
|
161 };
|
|
|
162
|
|
|
163 /* The possible ordering of refs within the df_ref_info. */
|
|
|
164 enum df_ref_order
|
|
|
165 {
|
|
|
166 /* There is not table. */
|
|
|
167 DF_REF_ORDER_NO_TABLE,
|
|
|
168
|
|
|
169 /* There is a table of refs but it is not (or no longer) organized
|
|
|
170 by one of the following methods. */
|
|
|
171 DF_REF_ORDER_UNORDERED,
|
|
|
172 DF_REF_ORDER_UNORDERED_WITH_NOTES,
|
|
|
173
|
|
|
174 /* Organize the table by reg order, all of the refs with regno 0
|
|
|
175 followed by all of the refs with regno 1 ... . Within all of
|
|
|
176 the regs for a particular regno, the refs are unordered. */
|
|
|
177 DF_REF_ORDER_BY_REG,
|
|
|
178
|
|
|
179 /* For uses, the refs within eq notes may be added for
|
|
|
180 DF_REF_ORDER_BY_REG. */
|
|
|
181 DF_REF_ORDER_BY_REG_WITH_NOTES,
|
|
|
182
|
|
|
183 /* Organize the refs in insn order. The insns are ordered within a
|
|
|
184 block, and the blocks are ordered by FOR_ALL_BB. */
|
|
|
185 DF_REF_ORDER_BY_INSN,
|
|
|
186
|
|
|
187 /* For uses, the refs within eq notes may be added for
|
|
|
188 DF_REF_ORDER_BY_INSN. */
|
|
|
189 DF_REF_ORDER_BY_INSN_WITH_NOTES
|
|
|
190 };
|
|
|
191
|
|
|
192 /* Function prototypes added to df_problem instance. */
|
|
|
193
|
|
|
194 /* Allocate the problem specific data. */
|
|
|
195 typedef void (*df_alloc_function) (bitmap);
|
|
|
196
|
|
|
197 /* This function is called if the problem has global data that needs
|
|
|
198 to be cleared when ever the set of blocks changes. The bitmap
|
|
|
199 contains the set of blocks that may require special attention.
|
|
|
200 This call is only made if some of the blocks are going to change.
|
|
|
201 If everything is to be deleted, the wholesale deletion mechanisms
|
|
|
202 apply. */
|
|
|
203 typedef void (*df_reset_function) (bitmap);
|
|
|
204
|
|
|
205 /* Free the basic block info. Called from the block reordering code
|
|
|
206 to get rid of the blocks that have been squished down. */
|
|
|
207 typedef void (*df_free_bb_function) (basic_block, void *);
|
|
|
208
|
|
|
209 /* Local compute function. */
|
|
|
210 typedef void (*df_local_compute_function) (bitmap);
|
|
|
211
|
|
|
212 /* Init the solution specific data. */
|
|
|
213 typedef void (*df_init_function) (bitmap);
|
|
|
214
|
|
|
215 /* Iterative dataflow function. */
|
|
|
216 typedef void (*df_dataflow_function) (struct dataflow *, bitmap, int *, int);
|
|
|
217
|
|
|
218 /* Confluence operator for blocks with 0 out (or in) edges. */
|
|
|
219 typedef void (*df_confluence_function_0) (basic_block);
|
|
|
220
|
|
|
221 /* Confluence operator for blocks with 1 or more out (or in) edges. */
|
|
|
222 typedef void (*df_confluence_function_n) (edge);
|
|
|
223
|
|
|
224 /* Transfer function for blocks. */
|
|
|
225 typedef bool (*df_transfer_function) (int);
|
|
|
226
|
|
|
227 /* Function to massage the information after the problem solving. */
|
|
|
228 typedef void (*df_finalizer_function) (bitmap);
|
|
|
229
|
|
|
230 /* Function to free all of the problem specific datastructures. */
|
|
|
231 typedef void (*df_free_function) (void);
|
|
|
232
|
|
|
233 /* Function to remove this problem from the stack of dataflow problems
|
|
|
234 without effecting the other problems in the stack except for those
|
|
|
235 that depend on this problem. */
|
|
|
236 typedef void (*df_remove_problem_function) (void);
|
|
|
237
|
|
|
238 /* Function to dump basic block independent results to FILE. */
|
|
|
239 typedef void (*df_dump_problem_function) (FILE *);
|
|
|
240
|
|
|
241 /* Function to dump top or bottom of basic block results to FILE. */
|
|
|
242 typedef void (*df_dump_bb_problem_function) (basic_block, FILE *);
|
|
|
243
|
|
|
244 /* Function to dump top or bottom of basic block results to FILE. */
|
|
|
245 typedef void (*df_verify_solution_start) (void);
|
|
|
246
|
|
|
247 /* Function to dump top or bottom of basic block results to FILE. */
|
|
|
248 typedef void (*df_verify_solution_end) (void);
|
|
|
249
|
|
|
250 /* The static description of a dataflow problem to solve. See above
|
|
|
251 typedefs for doc for the function fields. */
|
|
|
252
|
|
|
253 struct df_problem {
|
|
|
254 /* The unique id of the problem. This is used it index into
|
|
|
255 df->defined_problems to make accessing the problem data easy. */
|
|
|
256 unsigned int id;
|
|
|
257 enum df_flow_dir dir; /* Dataflow direction. */
|
|
|
258 df_alloc_function alloc_fun;
|
|
|
259 df_reset_function reset_fun;
|
|
|
260 df_free_bb_function free_bb_fun;
|
|
|
261 df_local_compute_function local_compute_fun;
|
|
|
262 df_init_function init_fun;
|
|
|
263 df_dataflow_function dataflow_fun;
|
|
|
264 df_confluence_function_0 con_fun_0;
|
|
|
265 df_confluence_function_n con_fun_n;
|
|
|
266 df_transfer_function trans_fun;
|
|
|
267 df_finalizer_function finalize_fun;
|
|
|
268 df_free_function free_fun;
|
|
|
269 df_remove_problem_function remove_problem_fun;
|
|
|
270 df_dump_problem_function dump_start_fun;
|
|
|
271 df_dump_bb_problem_function dump_top_fun;
|
|
|
272 df_dump_bb_problem_function dump_bottom_fun;
|
|
|
273 df_verify_solution_start verify_start_fun;
|
|
|
274 df_verify_solution_end verify_end_fun;
|
|
|
275 struct df_problem *dependent_problem;
|
|
|
276
|
|
|
277 /* The timevar id associated with this pass. */
|
|
|
278 unsigned int tv_id;
|
|
|
279
|
|
|
280 /* True if the df_set_blocks should null out the basic block info if
|
|
|
281 this block drops out of df->blocks_to_analyze. */
|
|
|
282 bool free_blocks_on_set_blocks;
|
|
|
283 };
|
|
|
284
|
|
|
285
|
|
|
286 /* The specific instance of the problem to solve. */
|
|
|
287 struct dataflow
|
|
|
288 {
|
|
|
289 struct df_problem *problem; /* The problem to be solved. */
|
|
|
290
|
|
|
291 /* Array indexed by bb->index, that contains basic block problem and
|
|
|
292 solution specific information. */
|
|
|
293 void **block_info;
|
|
|
294 unsigned int block_info_size;
|
|
|
295
|
|
|
296 /* The pool to allocate the block_info from. */
|
|
|
297 alloc_pool block_pool;
|
|
|
298
|
|
|
299 /* The lr and live problems have their transfer functions recomputed
|
|
|
300 only if necessary. This is possible for them because, the
|
|
|
301 problems are kept active for the entire backend and their
|
|
|
302 transfer functions are indexed by the REGNO. These are not
|
|
|
303 defined for any other problem. */
|
|
|
304 bitmap out_of_date_transfer_functions;
|
|
|
305
|
|
|
306 /* Other problem specific data that is not on a per basic block
|
|
|
307 basis. The structure is generally defined privately for the
|
|
|
308 problem. The exception being the scanning problem where it is
|
|
|
309 fully public. */
|
|
|
310 void *problem_data;
|
|
|
311
|
|
|
312 /* Local flags for some of the problems. */
|
|
|
313 unsigned int local_flags;
|
|
|
314
|
|
|
315 /* True if this problem of this instance has been initialized. This
|
|
|
316 is used by the dumpers to keep garbage out of the dumps if, for
|
|
|
317 debugging a dump is produced before the first call to
|
|
|
318 df_analyze after a new problem is added. */
|
|
|
319 bool computed;
|
|
|
320
|
|
|
321 /* True if the something has changed which invalidates the dataflow
|
|
|
322 solutions. Note that this bit is always true for all problems except
|
|
|
323 lr and live. */
|
|
|
324 bool solutions_dirty;
|
|
|
325
|
|
|
326 /* If true, this pass is deleted by df_finish_pass. This is never
|
|
|
327 true for DF_SCAN and DF_LR. It is true for DF_LIVE if optimize >
|
|
|
328 1. It is always true for the other problems. */
|
|
|
329 bool optional_p;
|
|
|
330 };
|
|
|
331
|
|
|
332
|
|
|
333 /* The set of multiword hardregs used as operands to this
|
|
|
334 instruction. These are factored into individual uses and defs but
|
|
|
335 the aggregate is still needed to service the REG_DEAD and
|
|
|
336 REG_UNUSED notes. */
|
|
|
337 struct df_mw_hardreg
|
|
|
338 {
|
|
|
339 rtx mw_reg; /* The multiword hardreg. */
|
|
|
340 /* These two bitfields are intentionally oversized, in the hope that
|
|
|
341 accesses to 16-bit fields will usually be quicker. */
|
|
|
342 ENUM_BITFIELD(df_ref_type) type : 16;
|
|
|
343 /* Used to see if the ref is read or write. */
|
|
|
344 ENUM_BITFIELD(df_ref_flags) flags : 16;
|
|
|
345 /* Various flags. */
|
|
|
346 unsigned int start_regno; /* First word of the multi word subreg. */
|
|
|
347 unsigned int end_regno; /* Last word of the multi word subreg. */
|
|
|
348 unsigned int mw_order; /* Same as df_ref.ref_order. */
|
|
|
349 };
|
|
|
350
|
|
|
351
|
|
|
352 /* Define a register reference structure. One of these is allocated
|
|
|
353 for every register reference (use or def). Note some register
|
|
|
354 references (e.g., post_inc, subreg) generate both a def and a use. */
|
|
|
355 struct df_base_ref
|
|
|
356 {
|
|
|
357 /* These three bitfields are intentionally oversized, in the hope that
|
|
|
358 accesses to 8 and 16-bit fields will usually be quicker. */
|
|
|
359 ENUM_BITFIELD(df_ref_class) cl : 8;
|
|
|
360
|
|
|
361 ENUM_BITFIELD(df_ref_type) type : 8;
|
|
|
362 /* Type of ref. */
|
|
|
363 ENUM_BITFIELD(df_ref_flags) flags : 16;
|
|
|
364 /* Various flags. */
|
|
|
365 rtx reg; /* The register referenced. */
|
|
|
366 struct df_link *chain; /* Head of def-use, use-def. */
|
|
|
367 /* Pointer to the insn info of the containing instruction. FIXME!
|
|
|
368 Currently this is NULL for artificial refs but this will be used
|
|
|
369 when FUDs are added. */
|
|
|
370 struct df_insn_info *insn_info;
|
|
|
371 /* For each regno, there are three chains of refs, one for the uses,
|
|
|
372 the eq_uses and the defs. These chains go thru the refs
|
|
|
373 themselves rather than using an external structure. */
|
|
|
374 union df_ref_d *next_reg; /* Next ref with same regno and type. */
|
|
|
375 union df_ref_d *prev_reg; /* Prev ref with same regno and type. */
|
|
|
376 unsigned int regno; /* The register number referenced. */
|
|
|
377 /* Location in the ref table. This is only valid after a call to
|
|
|
378 df_maybe_reorganize_[use,def]_refs which is an expensive operation. */
|
|
|
379 int id;
|
|
|
380 /* The index at which the operand was scanned in the insn. This is
|
|
|
381 used to totally order the refs in an insn. */
|
|
|
382 unsigned int ref_order;
|
|
|
383 };
|
|
|
384
|
|
|
385
|
|
|
386 /* The three types of df_refs. Note that the df_ref_extract is an
|
|
|
387 extension of the df_regular_ref, not the df_base_ref. */
|
|
|
388 struct df_artificial_ref
|
|
|
389 {
|
|
|
390 struct df_base_ref base;
|
|
|
391
|
|
|
392 /* Artificial refs do not have an insn, so to get the basic block,
|
|
|
393 it must be explicitly here. */
|
|
|
394 basic_block bb;
|
|
|
395 };
|
|
|
396
|
|
|
397
|
|
|
398 struct df_regular_ref
|
|
|
399 {
|
|
|
400 struct df_base_ref base;
|
|
|
401 /* The loc is the address in the insn of the reg. This is not
|
|
|
402 defined for special registers, such as clobbers and stack
|
|
|
403 pointers that are also associated with call insns and so those
|
|
|
404 just use the base. */
|
|
|
405 rtx *loc;
|
|
|
406 };
|
|
|
407
|
|
|
408
|
|
|
409 /* A df_ref_extract is just a df_ref with a width and offset field at
|
|
|
410 the end of it. It is used to hold this information if the ref was
|
|
|
411 wrapped by a SIGN_EXTRACT or a ZERO_EXTRACT and to pass this info
|
|
|
412 to passes that wish to process partial regs precisely. */
|
|
|
413 struct df_extract_ref
|
|
|
414 {
|
|
|
415 struct df_regular_ref base;
|
|
|
416 int width;
|
|
|
417 int offset;
|
|
|
418 enum machine_mode mode;
|
|
|
419 };
|
|
|
420
|
|
|
421 /* Union of the different kinds of defs/uses placeholders. */
|
|
|
422 union df_ref_d
|
|
|
423 {
|
|
|
424 struct df_base_ref base;
|
|
|
425 struct df_regular_ref regular_ref;
|
|
|
426 struct df_artificial_ref artificial_ref;
|
|
|
427 struct df_extract_ref extract_ref;
|
|
|
428 };
|
|
|
429 typedef union df_ref_d *df_ref;
|
|
|
430
|
|
|
431
|
|
|
432 /* One of these structures is allocated for every insn. */
|
|
|
433 struct df_insn_info
|
|
|
434 {
|
|
|
435 rtx insn; /* The insn this info comes from. */
|
|
|
436 df_ref *defs; /* Head of insn-def chain. */
|
|
|
437 df_ref *uses; /* Head of insn-use chain. */
|
|
|
438 /* Head of insn-use chain for uses in REG_EQUAL/EQUIV notes. */
|
|
|
439 df_ref *eq_uses;
|
|
|
440 struct df_mw_hardreg **mw_hardregs;
|
|
|
441 /* The logical uid of the insn in the basic block. This is valid
|
|
|
442 after any call to df_analyze but may rot after insns are added,
|
|
|
443 deleted or moved. */
|
|
|
444 int luid;
|
|
|
445 };
|
|
|
446
|
|
|
447 /* These links are used for ref-ref chains. Currently only DEF-USE and
|
|
|
448 USE-DEF chains can be built by DF. */
|
|
|
449 struct df_link
|
|
|
450 {
|
|
|
451 df_ref ref;
|
|
|
452 struct df_link *next;
|
|
|
453 };
|
|
|
454
|
|
|
455
|
|
|
456 enum df_chain_flags
|
|
|
457 {
|
|
|
458 /* Flags that control the building of chains. */
|
|
|
459 DF_DU_CHAIN = 1, /* Build DU chains. */
|
|
|
460 DF_UD_CHAIN = 2 /* Build UD chains. */
|
|
|
461 };
|
|
|
462
|
|
|
463 enum df_changeable_flags
|
|
|
464 {
|
|
|
465 /* Scanning flags. */
|
|
|
466 /* Flag to control the running of dce as a side effect of building LR. */
|
|
|
467 DF_LR_RUN_DCE = 1 << 0, /* Run DCE. */
|
|
|
468 DF_NO_HARD_REGS = 1 << 1, /* Skip hard registers in RD and CHAIN Building. */
|
|
|
469
|
|
|
470 DF_EQ_NOTES = 1 << 2, /* Build chains with uses present in EQUIV/EQUAL notes. */
|
|
|
471 DF_NO_REGS_EVER_LIVE = 1 << 3, /* Do not compute the regs_ever_live. */
|
|
|
472
|
|
|
473 /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to
|
|
|
474 return immediately. This is used by passes that know how to update
|
|
|
475 the scanning them selves. */
|
|
|
476 DF_NO_INSN_RESCAN = 1 << 4,
|
|
|
477
|
|
|
478 /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to
|
|
|
479 return after marking the insn for later processing. This allows all
|
|
|
480 rescans to be batched. */
|
|
|
481 DF_DEFER_INSN_RESCAN = 1 << 5,
|
|
|
482
|
|
|
483 DF_VERIFY_SCHEDULED = 1 << 6
|
|
|
484 };
|
|
|
485
|
|
|
486 /* Two of these structures are inline in df, one for the uses and one
|
|
|
487 for the defs. This structure is only contains the refs within the
|
|
|
488 boundary of the df_set_blocks if that has been defined. */
|
|
|
489 struct df_ref_info
|
|
|
490 {
|
|
|
491 df_ref *refs; /* Ref table, indexed by id. */
|
|
|
492 unsigned int *begin; /* First ref_index for this pseudo. */
|
|
|
493 unsigned int *count; /* Count of refs for this pseudo. */
|
|
|
494 unsigned int refs_size; /* Size of currently allocated refs table. */
|
|
|
495
|
|
|
496 /* Table_size is the number of elements in the refs table. This
|
|
|
497 will also be the width of the bitvectors in the rd and ru
|
|
|
498 problems. Total_size is the number of refs. These will be the
|
|
|
499 same if the focus has not been reduced by df_set_blocks. If the
|
|
|
500 focus has been reduced, table_size will be smaller since it only
|
|
|
501 contains the refs in the set blocks. */
|
|
|
502 unsigned int table_size;
|
|
|
503 unsigned int total_size;
|
|
|
504
|
|
|
505 enum df_ref_order ref_order;
|
|
|
506 };
|
|
|
507
|
|
|
508 /* Three of these structures are allocated for every pseudo reg. One
|
|
|
509 for the uses, one for the eq_uses and one for the defs. */
|
|
|
510 struct df_reg_info
|
|
|
511 {
|
|
|
512 /* Head of chain for refs of that type and regno. */
|
|
|
513 df_ref reg_chain;
|
|
|
514 /* Number of refs in the chain. */
|
|
|
515 unsigned int n_refs;
|
|
|
516 };
|
|
|
517
|
|
|
518
|
|
|
519 /*----------------------------------------------------------------------------
|
|
|
520 Problem data for the scanning dataflow problem. Unlike the other
|
|
|
521 dataflow problems, the problem data for scanning is fully exposed and
|
|
|
522 used by owners of the problem.
|
|
|
523 ----------------------------------------------------------------------------*/
|
|
|
524
|
|
|
525 struct df
|
|
|
526 {
|
|
|
527
|
|
|
528 /* The set of problems to be solved is stored in two arrays. In
|
|
|
529 PROBLEMS_IN_ORDER, the problems are stored in the order that they
|
|
|
530 are solved. This is an internally dense array that may have
|
|
|
531 nulls at the end of it. In PROBLEMS_BY_INDEX, the problem is
|
|
|
532 stored by the value in df_problem.id. These are used to access
|
|
|
533 the problem local data without having to search the first
|
|
|
534 array. */
|
|
|
535
|
|
|
536 struct dataflow *problems_in_order[DF_LAST_PROBLEM_PLUS1];
|
|
|
537 struct dataflow *problems_by_index[DF_LAST_PROBLEM_PLUS1];
|
|
|
538
|
|
|
539 /* If not NULL, this subset of blocks of the program to be
|
|
|
540 considered for analysis. At certain times, this will contain all
|
|
|
541 the blocks in the function so it cannot be used as an indicator
|
|
|
542 of if we are analyzing a subset. See analyze_subset. */
|
|
|
543 bitmap blocks_to_analyze;
|
|
|
544
|
|
|
545 /* The following information is really the problem data for the
|
|
|
546 scanning instance but it is used too often by the other problems
|
|
|
547 to keep getting it from there. */
|
|
|
548 struct df_ref_info def_info; /* Def info. */
|
|
|
549 struct df_ref_info use_info; /* Use info. */
|
|
|
550
|
|
|
551 /* The following three arrays are allocated in parallel. They contain
|
|
|
552 the sets of refs of each type for each reg. */
|
|
|
553 struct df_reg_info **def_regs; /* Def reg info. */
|
|
|
554 struct df_reg_info **use_regs; /* Eq_use reg info. */
|
|
|
555 struct df_reg_info **eq_use_regs; /* Eq_use info. */
|
|
|
556 unsigned int regs_size; /* Size of currently allocated regs table. */
|
|
|
557 unsigned int regs_inited; /* Number of regs with reg_infos allocated. */
|
|
|
558
|
|
|
559
|
|
|
560 struct df_insn_info **insns; /* Insn table, indexed by insn UID. */
|
|
|
561 unsigned int insns_size; /* Size of insn table. */
|
|
|
562
|
|
|
563 int num_problems_defined;
|
|
|
564
|
|
|
565 bitmap hardware_regs_used; /* The set of hardware registers used. */
|
|
|
566 /* The set of hard regs that are in the artificial uses at the end
|
|
|
567 of a regular basic block. */
|
|
|
568 bitmap regular_block_artificial_uses;
|
|
|
569 /* The set of hard regs that are in the artificial uses at the end
|
|
|
570 of a basic block that has an EH pred. */
|
|
|
571 bitmap eh_block_artificial_uses;
|
|
|
572 /* The set of hardware registers live on entry to the function. */
|
|
|
573 bitmap entry_block_defs;
|
|
|
574 bitmap exit_block_uses; /* The set of hardware registers used in exit block. */
|
|
|
575
|
|
|
576 /* Insns to delete, rescan or reprocess the notes at next
|
|
|
577 df_rescan_all or df_process_deferred_rescans. */
|
|
|
578 bitmap insns_to_delete;
|
|
|
579 bitmap insns_to_rescan;
|
|
|
580 bitmap insns_to_notes_rescan;
|
|
|
581 int *postorder; /* The current set of basic blocks
|
|
|
582 in reverse postorder. */
|
|
|
583 int *postorder_inverted; /* The current set of basic blocks
|
|
|
584 in reverse postorder of inverted CFG. */
|
|
|
585 int n_blocks; /* The number of blocks in reverse postorder. */
|
|
|
586 int n_blocks_inverted; /* The number of blocks
|
|
|
587 in reverse postorder of inverted CFG. */
|
|
|
588
|
|
|
589 /* An array [FIRST_PSEUDO_REGISTER], indexed by regno, of the number
|
|
|
590 of refs that qualify as being real hard regs uses. Artificial
|
|
|
591 uses and defs as well as refs in eq notes are ignored. If the
|
|
|
592 ref is a def, it cannot be a MAY_CLOBBER def. If the ref is a
|
|
|
593 use, it cannot be the emim_reg_set or be the frame or arg pointer
|
|
|
594 register.
|
|
|
595
|
|
|
596 IT IS NOT ACCEPTABLE TO MANUALLY CHANGE THIS ARRAY. This array
|
|
|
597 always reflects the actual number of refs in the insn stream that
|
|
|
598 satisfy the above criteria. */
|
|
|
599 unsigned int *hard_regs_live_count;
|
|
|
600
|
|
|
601 /* This counter provides a way to totally order refs without using
|
|
|
602 addresses. It is incremented whenever a ref is created. */
|
|
|
603 unsigned int ref_order;
|
|
|
604
|
|
|
605 /* Problem specific control information. */
|
|
|
606 ENUM_BITFIELD (df_changeable_flags) changeable_flags : 8;
|
|
|
607
|
|
|
608 /* If this is true, then only a subset of the blocks of the program
|
|
|
609 is considered to compute the solutions of dataflow problems. */
|
|
|
610 bool analyze_subset;
|
|
|
611
|
|
|
612 /* True if someone added or deleted something from regs_ever_live so
|
|
|
613 that the entry and exit blocks need be reprocessed. */
|
|
|
614 bool redo_entry_and_exit;
|
|
|
615 };
|
|
|
616
|
|
|
617 #define DF_SCAN_BB_INFO(BB) (df_scan_get_bb_info((BB)->index))
|
|
|
618 #define DF_RD_BB_INFO(BB) (df_rd_get_bb_info((BB)->index))
|
|
|
619 #define DF_LR_BB_INFO(BB) (df_lr_get_bb_info((BB)->index))
|
|
|
620 #define DF_LIVE_BB_INFO(BB) (df_live_get_bb_info((BB)->index))
|
|
|
621 #define DF_BYTE_LR_BB_INFO(BB) (df_byte_lr_get_bb_info((BB)->index))
|
|
|
622
|
|
|
623 /* Most transformations that wish to use live register analysis will
|
|
|
624 use these macros. This info is the and of the lr and live sets. */
|
|
|
625 #define DF_LIVE_IN(BB) (DF_LIVE_BB_INFO(BB)->in)
|
|
|
626 #define DF_LIVE_OUT(BB) (DF_LIVE_BB_INFO(BB)->out)
|
|
|
627
|
|
|
628 /* These macros are used by passes that are not tolerant of
|
|
|
629 uninitialized variables. This intolerance should eventually
|
|
|
630 be fixed. */
|
|
|
631 #define DF_LR_IN(BB) (DF_LR_BB_INFO(BB)->in)
|
|
|
632 #define DF_LR_OUT(BB) (DF_LR_BB_INFO(BB)->out)
|
|
|
633
|
|
|
634 /* These macros are used by passes that are not tolerant of
|
|
|
635 uninitialized variables. This intolerance should eventually
|
|
|
636 be fixed. */
|
|
|
637 #define DF_BYTE_LR_IN(BB) (DF_BYTE_LR_BB_INFO(BB)->in)
|
|
|
638 #define DF_BYTE_LR_OUT(BB) (DF_BYTE_LR_BB_INFO(BB)->out)
|
|
|
639
|
|
|
640 /* Macros to access the elements within the ref structure. */
|
|
|
641
|
|
|
642
|
|
|
643 #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->base.reg) == SUBREG \
|
|
|
644 ? SUBREG_REG ((REF)->base.reg) : ((REF)->base.reg))
|
|
|
645 #define DF_REF_REGNO(REF) ((REF)->base.regno)
|
|
|
646 #define DF_REF_REAL_LOC(REF) (GET_CODE (*((REF)->regular_ref.loc)) == SUBREG \
|
|
|
647 ? &SUBREG_REG (*((REF)->regular_ref.loc)) : ((REF)->regular_ref.loc))
|
|
|
648 #define DF_REF_REG(REF) ((REF)->base.reg)
|
|
|
649 #define DF_REF_LOC(REF) ((DF_REF_CLASS(REF) == DF_REF_REGULAR || DF_REF_CLASS(REF) == DF_REF_EXTRACT) ? \
|
|
|
650 (REF)->regular_ref.loc : NULL)
|
|
|
651 #define DF_REF_BB(REF) (DF_REF_IS_ARTIFICIAL(REF) ? \
|
|
|
652 (REF)->artificial_ref.bb : BLOCK_FOR_INSN (DF_REF_INSN(REF)))
|
|
|
653 #define DF_REF_BBNO(REF) (DF_REF_BB (REF)->index)
|
|
|
654 #define DF_REF_INSN_INFO(REF) ((REF)->base.insn_info)
|
|
|
655 #define DF_REF_INSN(REF) ((REF)->base.insn_info->insn)
|
|
|
656 #define DF_REF_INSN_UID(REF) (INSN_UID (DF_REF_INSN(REF)))
|
|
|
657 #define DF_REF_CLASS(REF) ((REF)->base.cl)
|
|
|
658 #define DF_REF_TYPE(REF) ((REF)->base.type)
|
|
|
659 #define DF_REF_CHAIN(REF) ((REF)->base.chain)
|
|
|
660 #define DF_REF_ID(REF) ((REF)->base.id)
|
|
|
661 #define DF_REF_FLAGS(REF) ((REF)->base.flags)
|
|
|
662 #define DF_REF_FLAGS_IS_SET(REF, v) ((DF_REF_FLAGS (REF) & (v)) != 0)
|
|
|
663 #define DF_REF_FLAGS_SET(REF, v) (DF_REF_FLAGS (REF) |= (v))
|
|
|
664 #define DF_REF_FLAGS_CLEAR(REF, v) (DF_REF_FLAGS (REF) &= ~(v))
|
|
|
665 #define DF_REF_ORDER(REF) ((REF)->base.ref_order)
|
|
|
666 /* If DF_REF_IS_ARTIFICIAL () is true, this is not a real
|
|
|
667 definition/use, but an artificial one created to model always live
|
|
|
668 registers, eh uses, etc. */
|
|
|
669 #define DF_REF_IS_ARTIFICIAL(REF) (DF_REF_CLASS(REF) == DF_REF_ARTIFICIAL)
|
|
|
670 #define DF_REF_REG_MARK(REF) (DF_REF_FLAGS_SET ((REF),DF_REF_REG_MARKER))
|
|
|
671 #define DF_REF_REG_UNMARK(REF) (DF_REF_FLAGS_CLEAR ((REF),DF_REF_REG_MARKER))
|
|
|
672 #define DF_REF_IS_REG_MARKED(REF) (DF_REF_FLAGS_IS_SET ((REF),DF_REF_REG_MARKER))
|
|
|
673 #define DF_REF_NEXT_REG(REF) ((REF)->base.next_reg)
|
|
|
674 #define DF_REF_PREV_REG(REF) ((REF)->base.prev_reg)
|
|
|
675 /* The following two macros may only be applied if one of
|
|
|
676 DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT is true. */
|
|
|
677 #define DF_REF_EXTRACT_WIDTH(REF) ((REF)->extract_ref.width)
|
|
|
678 #define DF_REF_EXTRACT_OFFSET(REF) ((REF)->extract_ref.offset)
|
|
|
679 #define DF_REF_EXTRACT_MODE(REF) ((REF)->extract_ref.mode)
|
|
|
680
|
|
|
681 /* Macros to determine the reference type. */
|
|
|
682 #define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF)
|
|
|
683 #define DF_REF_REG_USE_P(REF) ((REF) && !DF_REF_REG_DEF_P (REF))
|
|
|
684 #define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE)
|
|
|
685 #define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD)
|
|
|
686 #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \
|
|
|
687 || DF_REF_REG_MEM_LOAD_P (REF))
|
|
|
688
|
|
|
689 #define DF_MWS_REG_DEF_P(MREF) (DF_MWS_TYPE (MREF) == DF_REF_REG_DEF)
|
|
|
690 #define DF_MWS_REG_USE_P(MREF) ((MREF) && !DF_MWS_REG_DEF_P (MREF))
|
|
|
691 #define DF_MWS_TYPE(MREF) ((MREF)->type)
|
|
|
692
|
|
|
693 /* Macros to get the refs out of def_info or use_info refs table. If
|
|
|
694 the focus of the dataflow has been set to some subset of blocks
|
|
|
695 with df_set_blocks, these macros will only find the uses and defs
|
|
|
696 in that subset of blocks.
|
|
|
697
|
|
|
698 These macros should be used with care. The def macros are only
|
|
|
699 usable after a call to df_maybe_reorganize_def_refs and the use
|
|
|
700 macros are only usable after a call to
|
|
|
701 df_maybe_reorganize_use_refs. HOWEVER, BUILDING AND USING THESE
|
|
|
702 ARRAYS ARE A CACHE LOCALITY KILLER. */
|
|
|
703
|
|
|
704 #define DF_DEFS_TABLE_SIZE() (df->def_info.table_size)
|
|
|
705 #define DF_DEFS_GET(ID) (df->def_info.refs[(ID)])
|
|
|
706 #define DF_DEFS_SET(ID,VAL) (df->def_info.refs[(ID)]=(VAL))
|
|
|
707 #define DF_DEFS_COUNT(ID) (df->def_info.count[(ID)])
|
|
|
708 #define DF_DEFS_BEGIN(ID) (df->def_info.begin[(ID)])
|
|
|
709 #define DF_USES_TABLE_SIZE() (df->use_info.table_size)
|
|
|
710 #define DF_USES_GET(ID) (df->use_info.refs[(ID)])
|
|
|
711 #define DF_USES_SET(ID,VAL) (df->use_info.refs[(ID)]=(VAL))
|
|
|
712 #define DF_USES_COUNT(ID) (df->use_info.count[(ID)])
|
|
|
713 #define DF_USES_BEGIN(ID) (df->use_info.begin[(ID)])
|
|
|
714
|
|
|
715 /* Macros to access the register information from scan dataflow record. */
|
|
|
716
|
|
|
717 #define DF_REG_SIZE(DF) (df->regs_inited)
|
|
|
718 #define DF_REG_DEF_GET(REG) (df->def_regs[(REG)])
|
|
|
719 #define DF_REG_DEF_CHAIN(REG) (df->def_regs[(REG)]->reg_chain)
|
|
|
720 #define DF_REG_DEF_COUNT(REG) (df->def_regs[(REG)]->n_refs)
|
|
|
721 #define DF_REG_USE_GET(REG) (df->use_regs[(REG)])
|
|
|
722 #define DF_REG_USE_CHAIN(REG) (df->use_regs[(REG)]->reg_chain)
|
|
|
723 #define DF_REG_USE_COUNT(REG) (df->use_regs[(REG)]->n_refs)
|
|
|
724 #define DF_REG_EQ_USE_GET(REG) (df->eq_use_regs[(REG)])
|
|
|
725 #define DF_REG_EQ_USE_CHAIN(REG) (df->eq_use_regs[(REG)]->reg_chain)
|
|
|
726 #define DF_REG_EQ_USE_COUNT(REG) (df->eq_use_regs[(REG)]->n_refs)
|
|
|
727
|
|
|
728 /* Macros to access the elements within the reg_info structure table. */
|
|
|
729
|
|
|
730 #define DF_REGNO_FIRST_DEF(REGNUM) \
|
|
|
731 (DF_REG_DEF_GET(REGNUM) ? DF_REG_DEF_GET(REGNUM) : 0)
|
|
|
732 #define DF_REGNO_LAST_USE(REGNUM) \
|
|
|
733 (DF_REG_USE_GET(REGNUM) ? DF_REG_USE_GET(REGNUM) : 0)
|
|
|
734
|
|
|
735 /* Macros to access the elements within the insn_info structure table. */
|
|
|
736
|
|
|
737 #define DF_INSN_SIZE() ((df)->insns_size)
|
|
|
738 #define DF_INSN_INFO_GET(INSN) (df->insns[(INSN_UID(INSN))])
|
|
|
739 #define DF_INSN_INFO_SET(INSN,VAL) (df->insns[(INSN_UID (INSN))]=(VAL))
|
|
|
740 #define DF_INSN_INFO_LUID(II) ((II)->luid)
|
|
|
741 #define DF_INSN_INFO_DEFS(II) ((II)->defs)
|
|
|
742 #define DF_INSN_INFO_USES(II) ((II)->uses)
|
|
|
743 #define DF_INSN_INFO_EQ_USES(II) ((II)->eq_uses)
|
|
|
744
|
|
|
745 #define DF_INSN_LUID(INSN) (DF_INSN_INFO_LUID (DF_INSN_INFO_GET(INSN)))
|
|
|
746 #define DF_INSN_DEFS(INSN) (DF_INSN_INFO_DEFS (DF_INSN_INFO_GET(INSN)))
|
|
|
747 #define DF_INSN_USES(INSN) (DF_INSN_INFO_USES (DF_INSN_INFO_GET(INSN)))
|
|
|
748 #define DF_INSN_EQ_USES(INSN) (DF_INSN_INFO_EQ_USES (DF_INSN_INFO_GET(INSN)))
|
|
|
749
|
|
|
750 #define DF_INSN_UID_GET(UID) (df->insns[(UID)])
|
|
|
751 #define DF_INSN_UID_SET(UID,VAL) (df->insns[(UID)]=(VAL))
|
|
|
752 #define DF_INSN_UID_SAFE_GET(UID) (((unsigned)(UID) < DF_INSN_SIZE()) \
|
|
|
753 ? DF_INSN_UID_GET (UID) \
|
|
|
754 : NULL)
|
|
|
755 #define DF_INSN_UID_LUID(INSN) (DF_INSN_UID_GET(INSN)->luid)
|
|
|
756 #define DF_INSN_UID_DEFS(INSN) (DF_INSN_UID_GET(INSN)->defs)
|
|
|
757 #define DF_INSN_UID_USES(INSN) (DF_INSN_UID_GET(INSN)->uses)
|
|
|
758 #define DF_INSN_UID_EQ_USES(INSN) (DF_INSN_UID_GET(INSN)->eq_uses)
|
|
|
759 #define DF_INSN_UID_MWS(INSN) (DF_INSN_UID_GET(INSN)->mw_hardregs)
|
|
|
760
|
|
|
761 /* An obstack for bitmap not related to specific dataflow problems.
|
|
|
762 This obstack should e.g. be used for bitmaps with a short life time
|
|
|
763 such as temporary bitmaps. This obstack is declared in df-core.c. */
|
|
|
764
|
|
|
765 extern bitmap_obstack df_bitmap_obstack;
|
|
|
766
|
|
|
767
|
|
|
768 /* One of these structures is allocated for every basic block. */
|
|
|
769 struct df_scan_bb_info
|
|
|
770 {
|
|
|
771 /* The entry block has many artificial defs and these are at the
|
|
|
772 bottom of the block.
|
|
|
773
|
|
|
774 Blocks that are targets of exception edges may have some
|
|
|
775 artificial defs. These are logically located at the top of the
|
|
|
776 block.
|
|
|
777
|
|
|
778 Blocks that are the targets of non-local goto's have the hard
|
|
|
779 frame pointer defined at the top of the block. */
|
|
|
780 df_ref *artificial_defs;
|
|
|
781
|
|
|
782 /* Blocks that are targets of exception edges may have some
|
|
|
783 artificial uses. These are logically at the top of the block.
|
|
|
784
|
|
|
785 Most blocks have artificial uses at the bottom of the block. */
|
|
|
786 df_ref *artificial_uses;
|
|
|
787 };
|
|
|
788
|
|
|
789
|
|
|
790 /* Reaching definitions. All bitmaps are indexed by the id field of
|
|
|
791 the ref except sparse_kill which is indexed by regno. */
|
|
|
792 struct df_rd_bb_info
|
|
|
793 {
|
|
|
794 /* Local sets to describe the basic blocks. */
|
|
|
795 bitmap kill;
|
|
|
796 bitmap sparse_kill;
|
|
|
797 bitmap gen; /* The set of defs generated in this block. */
|
|
|
798
|
|
|
799 /* The results of the dataflow problem. */
|
|
|
800 bitmap in; /* At the top of the block. */
|
|
|
801 bitmap out; /* At the bottom of the block. */
|
|
|
802 };
|
|
|
803
|
|
|
804
|
|
|
805 /* Live registers, a backwards dataflow problem. All bitmaps are
|
|
|
806 referenced by the register number. */
|
|
|
807
|
|
|
808 struct df_lr_bb_info
|
|
|
809 {
|
|
|
810 /* Local sets to describe the basic blocks. */
|
|
|
811 bitmap def; /* The set of registers set in this block
|
|
|
812 - except artificial defs at the top. */
|
|
|
813 bitmap use; /* The set of registers used in this block. */
|
|
|
814
|
|
|
815 /* The results of the dataflow problem. */
|
|
|
816 bitmap in; /* Just before the block itself. */
|
|
|
817 bitmap out; /* At the bottom of the block. */
|
|
|
818 };
|
|
|
819
|
|
|
820
|
|
|
821 /* Uninitialized registers. All bitmaps are referenced by the
|
|
|
822 register number. Anded results of the forwards and backward live
|
|
|
823 info. Note that the forwards live information is not available
|
|
|
824 separately. */
|
|
|
825 struct df_live_bb_info
|
|
|
826 {
|
|
|
827 /* Local sets to describe the basic blocks. */
|
|
|
828 bitmap kill; /* The set of registers unset in this block. Calls,
|
|
|
829 for instance, unset registers. */
|
|
|
830 bitmap gen; /* The set of registers set in this block. */
|
|
|
831
|
|
|
832 /* The results of the dataflow problem. */
|
|
|
833 bitmap in; /* At the top of the block. */
|
|
|
834 bitmap out; /* At the bottom of the block. */
|
|
|
835 };
|
|
|
836
|
|
|
837
|
|
|
838 /* Live registers, a backwards dataflow problem. These bitmaps are
|
|
|
839 indexed by the df_byte_lr_offset array which is indexed by pseudo. */
|
|
|
840
|
|
|
841 struct df_byte_lr_bb_info
|
|
|
842 {
|
|
|
843 /* Local sets to describe the basic blocks. */
|
|
|
844 bitmap def; /* The set of registers set in this block
|
|
|
845 - except artificial defs at the top. */
|
|
|
846 bitmap use; /* The set of registers used in this block. */
|
|
|
847
|
|
|
848 /* The results of the dataflow problem. */
|
|
|
849 bitmap in; /* Just before the block itself. */
|
|
|
850 bitmap out; /* At the bottom of the block. */
|
|
|
851 };
|
|
|
852
|
|
|
853
|
|
|
854 /* This is used for debugging and for the dumpers to find the latest
|
|
|
855 instance so that the df info can be added to the dumps. This
|
|
|
856 should not be used by regular code. */
|
|
|
857 extern struct df *df;
|
|
|
858 #define df_scan (df->problems_by_index[DF_SCAN])
|
|
|
859 #define df_rd (df->problems_by_index[DF_RD])
|
|
|
860 #define df_lr (df->problems_by_index[DF_LR])
|
|
|
861 #define df_live (df->problems_by_index[DF_LIVE])
|
|
|
862 #define df_chain (df->problems_by_index[DF_CHAIN])
|
|
|
863 #define df_byte_lr (df->problems_by_index[DF_BYTE_LR])
|
|
|
864 #define df_note (df->problems_by_index[DF_NOTE])
|
|
|
865
|
|
|
866 /* This symbol turns on checking that each modification of the cfg has
|
|
|
867 been identified to the appropriate df routines. It is not part of
|
|
|
868 verification per se because the check that the final solution has
|
|
|
869 not changed covers this. However, if the solution is not being
|
|
|
870 properly recomputed because the cfg is being modified, adding in
|
|
|
871 calls to df_check_cfg_clean can be used to find the source of that
|
|
|
872 kind of problem. */
|
|
|
873 #if 0
|
|
|
874 #define DF_DEBUG_CFG
|
|
|
875 #endif
|
|
|
876
|
|
|
877
|
|
|
878 /* Functions defined in df-core.c. */
|
|
|
879
|
|
|
880 extern void df_add_problem (struct df_problem *);
|
|
|
881 extern enum df_changeable_flags df_set_flags (enum df_changeable_flags);
|
|
|
882 extern enum df_changeable_flags df_clear_flags (enum df_changeable_flags);
|
|
|
883 extern void df_set_blocks (bitmap);
|
|
|
884 extern void df_remove_problem (struct dataflow *);
|
|
|
885 extern void df_finish_pass (bool);
|
|
|
886 extern void df_analyze_problem (struct dataflow *, bitmap, int *, int);
|
|
|
887 extern void df_analyze (void);
|
|
|
888 extern int df_get_n_blocks (enum df_flow_dir);
|
|
|
889 extern int *df_get_postorder (enum df_flow_dir);
|
|
|
890 extern void df_simple_dataflow (enum df_flow_dir, df_init_function,
|
|
|
891 df_confluence_function_0, df_confluence_function_n,
|
|
|
892 df_transfer_function, bitmap, int *, int);
|
|
|
893 extern void df_mark_solutions_dirty (void);
|
|
|
894 extern bool df_get_bb_dirty (basic_block);
|
|
|
895 extern void df_set_bb_dirty (basic_block);
|
|
|
896 extern void df_compact_blocks (void);
|
|
|
897 extern void df_bb_replace (int, basic_block);
|
|
|
898 extern void df_bb_delete (int);
|
|
|
899 extern void df_verify (void);
|
|
|
900 #ifdef DF_DEBUG_CFG
|
|
|
901 extern void df_check_cfg_clean (void);
|
|
|
902 #endif
|
|
|
903 extern df_ref df_bb_regno_first_def_find (basic_block, unsigned int);
|
|
|
904 extern df_ref df_bb_regno_last_def_find (basic_block, unsigned int);
|
|
|
905 extern df_ref df_find_def (rtx, rtx);
|
|
|
906 extern bool df_reg_defined (rtx, rtx);
|
|
|
907 extern df_ref df_find_use (rtx, rtx);
|
|
|
908 extern bool df_reg_used (rtx, rtx);
|
|
|
909 extern void df_worklist_dataflow (struct dataflow *,bitmap, int *, int);
|
|
|
910 extern void df_print_regset (FILE *file, bitmap r);
|
|
|
911 extern void df_print_byte_regset (FILE *file, bitmap r);
|
|
|
912 extern void df_dump (FILE *);
|
|
|
913 extern void df_dump_region (FILE *);
|
|
|
914 extern void df_dump_start (FILE *);
|
|
|
915 extern void df_dump_top (basic_block, FILE *);
|
|
|
916 extern void df_dump_bottom (basic_block, FILE *);
|
|
|
917 extern void df_refs_chain_dump (df_ref *, bool, FILE *);
|
|
|
918 extern void df_regs_chain_dump (df_ref, FILE *);
|
|
|
919 extern void df_insn_debug (rtx, bool, FILE *);
|
|
|
920 extern void df_insn_debug_regno (rtx, FILE *);
|
|
|
921 extern void df_regno_debug (unsigned int, FILE *);
|
|
|
922 extern void df_ref_debug (df_ref, FILE *);
|
|
|
923 extern void debug_df_insn (rtx);
|
|
|
924 extern void debug_df_regno (unsigned int);
|
|
|
925 extern void debug_df_reg (rtx);
|
|
|
926 extern void debug_df_defno (unsigned int);
|
|
|
927 extern void debug_df_useno (unsigned int);
|
|
|
928 extern void debug_df_ref (df_ref);
|
|
|
929 extern void debug_df_chain (struct df_link *);
|
|
|
930
|
|
|
931 /* Functions defined in df-problems.c. */
|
|
|
932
|
|
|
933 extern struct df_link *df_chain_create (df_ref, df_ref);
|
|
|
934 extern void df_chain_unlink (df_ref);
|
|
|
935 extern void df_chain_copy (df_ref, struct df_link *);
|
|
|
936 extern bitmap df_get_live_in (basic_block);
|
|
|
937 extern bitmap df_get_live_out (basic_block);
|
|
|
938 extern void df_grow_bb_info (struct dataflow *);
|
|
|
939 extern void df_chain_dump (struct df_link *, FILE *);
|
|
|
940 extern void df_print_bb_index (basic_block bb, FILE *file);
|
|
|
941 extern void df_rd_add_problem (void);
|
|
|
942 extern void df_lr_add_problem (void);
|
|
|
943 extern void df_lr_verify_transfer_functions (void);
|
|
|
944 extern void df_live_verify_transfer_functions (void);
|
|
|
945 extern void df_live_add_problem (void);
|
|
|
946 extern void df_live_set_all_dirty (void);
|
|
|
947 extern void df_chain_add_problem (enum df_chain_flags);
|
|
|
948 extern void df_byte_lr_add_problem (void);
|
|
|
949 extern int df_byte_lr_get_regno_start (unsigned int);
|
|
|
950 extern int df_byte_lr_get_regno_len (unsigned int);
|
|
|
951 extern void df_byte_lr_simulate_defs (rtx, bitmap);
|
|
|
952 extern void df_byte_lr_simulate_uses (rtx, bitmap);
|
|
|
953 extern void df_byte_lr_simulate_artificial_refs_at_top (basic_block, bitmap);
|
|
|
954 extern void df_byte_lr_simulate_artificial_refs_at_end (basic_block, bitmap);
|
|
|
955 extern void df_note_add_problem (void);
|
|
|
956 extern void df_simulate_find_defs (rtx, bitmap);
|
|
|
957 extern void df_simulate_defs (rtx, bitmap);
|
|
|
958 extern void df_simulate_uses (rtx, bitmap);
|
|
|
959 extern void df_simulate_initialize_backwards (basic_block, bitmap);
|
|
|
960 extern void df_simulate_one_insn_backwards (basic_block, rtx, bitmap);
|
|
|
961 extern void df_simulate_finalize_backwards (basic_block, bitmap);
|
|
|
962 extern void df_simulate_initialize_forwards (basic_block, bitmap);
|
|
|
963 extern void df_simulate_one_insn_forwards (basic_block, rtx, bitmap);
|
|
|
964 extern void df_simulate_finalize_forwards (basic_block, bitmap);
|
|
|
965
|
|
|
966 /* Functions defined in df-scan.c. */
|
|
|
967
|
|
|
968 extern void df_scan_alloc (bitmap);
|
|
|
969 extern void df_scan_add_problem (void);
|
|
|
970 extern void df_grow_reg_info (void);
|
|
|
971 extern void df_grow_insn_info (void);
|
|
|
972 extern void df_scan_blocks (void);
|
|
|
973 extern df_ref df_ref_create (rtx, rtx *, rtx,basic_block,
|
|
|
974 enum df_ref_type, enum df_ref_flags,
|
|
|
975 int, int, enum machine_mode);
|
|
|
976 extern void df_ref_remove (df_ref);
|
|
|
977 extern struct df_insn_info * df_insn_create_insn_record (rtx);
|
|
|
978 extern void df_insn_delete (basic_block, unsigned int);
|
|
|
979 extern void df_bb_refs_record (int, bool);
|
|
|
980 extern bool df_insn_rescan (rtx);
|
|
|
981 extern void df_insn_rescan_all (void);
|
|
|
982 extern void df_process_deferred_rescans (void);
|
|
|
983 extern void df_recompute_luids (basic_block);
|
|
|
984 extern void df_insn_change_bb (rtx, basic_block);
|
|
|
985 extern void df_maybe_reorganize_use_refs (enum df_ref_order);
|
|
|
986 extern void df_maybe_reorganize_def_refs (enum df_ref_order);
|
|
|
987 extern void df_ref_change_reg_with_loc (int, int, rtx);
|
|
|
988 extern void df_notes_rescan (rtx);
|
|
|
989 extern void df_hard_reg_init (void);
|
|
|
990 extern void df_update_entry_block_defs (void);
|
|
|
991 extern void df_update_exit_block_uses (void);
|
|
|
992 extern void df_update_entry_exit_and_calls (void);
|
|
|
993 extern bool df_hard_reg_used_p (unsigned int);
|
|
|
994 extern unsigned int df_hard_reg_used_count (unsigned int);
|
|
|
995 extern bool df_regs_ever_live_p (unsigned int);
|
|
|
996 extern void df_set_regs_ever_live (unsigned int, bool);
|
|
|
997 extern void df_compute_regs_ever_live (bool);
|
|
|
998 extern bool df_read_modify_subreg_p (rtx);
|
|
|
999 extern void df_scan_verify (void);
|
|
|
1000
|
|
|
1001 /* Functions defined in df-byte-scan.c. */
|
|
|
1002 extern bool df_compute_accessed_bytes (df_ref, enum df_mm,
|
|
|
1003 unsigned int *, unsigned int *);
|
|
|
1004
|
|
|
1005
|
|
|
1006 /* Get basic block info. */
|
|
|
1007
|
|
|
1008 static inline struct df_scan_bb_info *
|
|
|
1009 df_scan_get_bb_info (unsigned int index)
|
|
|
1010 {
|
|
|
1011 if (index < df_scan->block_info_size)
|
|
|
1012 return (struct df_scan_bb_info *) df_scan->block_info[index];
|
|
|
1013 else
|
|
|
1014 return NULL;
|
|
|
1015 }
|
|
|
1016
|
|
|
1017 static inline struct df_rd_bb_info *
|
|
|
1018 df_rd_get_bb_info (unsigned int index)
|
|
|
1019 {
|
|
|
1020 if (index < df_rd->block_info_size)
|
|
|
1021 return (struct df_rd_bb_info *) df_rd->block_info[index];
|
|
|
1022 else
|
|
|
1023 return NULL;
|
|
|
1024 }
|
|
|
1025
|
|
|
1026 static inline struct df_lr_bb_info *
|
|
|
1027 df_lr_get_bb_info (unsigned int index)
|
|
|
1028 {
|
|
|
1029 if (index < df_lr->block_info_size)
|
|
|
1030 return (struct df_lr_bb_info *) df_lr->block_info[index];
|
|
|
1031 else
|
|
|
1032 return NULL;
|
|
|
1033 }
|
|
|
1034
|
|
|
1035 static inline struct df_live_bb_info *
|
|
|
1036 df_live_get_bb_info (unsigned int index)
|
|
|
1037 {
|
|
|
1038 if (index < df_live->block_info_size)
|
|
|
1039 return (struct df_live_bb_info *) df_live->block_info[index];
|
|
|
1040 else
|
|
|
1041 return NULL;
|
|
|
1042 }
|
|
|
1043
|
|
|
1044 static inline struct df_byte_lr_bb_info *
|
|
|
1045 df_byte_lr_get_bb_info (unsigned int index)
|
|
|
1046 {
|
|
|
1047 if (index < df_byte_lr->block_info_size)
|
|
|
1048 return (struct df_byte_lr_bb_info *) df_byte_lr->block_info[index];
|
|
|
1049 else
|
|
|
1050 return NULL;
|
|
|
1051 }
|
|
|
1052
|
|
|
1053 /* Get the artificial defs for a basic block. */
|
|
|
1054
|
|
|
1055 static inline df_ref *
|
|
|
1056 df_get_artificial_defs (unsigned int bb_index)
|
|
|
1057 {
|
|
|
1058 return df_scan_get_bb_info (bb_index)->artificial_defs;
|
|
|
1059 }
|
|
|
1060
|
|
|
1061
|
|
|
1062 /* Get the artificial uses for a basic block. */
|
|
|
1063
|
|
|
1064 static inline df_ref *
|
|
|
1065 df_get_artificial_uses (unsigned int bb_index)
|
|
|
1066 {
|
|
|
1067 return df_scan_get_bb_info (bb_index)->artificial_uses;
|
|
|
1068 }
|
|
|
1069
|
|
|
1070
|
|
|
1071 /* web */
|
|
|
1072
|
|
|
1073 /* This entry is allocated for each reference in the insn stream. */
|
|
|
1074 struct web_entry
|
|
|
1075 {
|
|
|
1076 /* Pointer to the parent in the union/find tree. */
|
|
|
1077 struct web_entry *pred;
|
|
|
1078 /* Newly assigned register to the entry. Set only for roots. */
|
|
|
1079 rtx reg;
|
|
|
1080 void* extra_info;
|
|
|
1081 };
|
|
|
1082
|
|
|
1083 extern struct web_entry *unionfind_root (struct web_entry *);
|
|
|
1084 extern bool unionfind_union (struct web_entry *, struct web_entry *);
|
|
|
1085 extern void union_defs (df_ref,
|
|
|
1086 struct web_entry *, struct web_entry *,
|
|
|
1087 bool (*fun) (struct web_entry *, struct web_entry *));
|
|
|
1088
|
|
|
1089 #endif /* GCC_DF_H */
|
