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 Free Software Foundation, Inc.
4 Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
24 #define DF_RD 1 /* Reaching definitions. */
25 #define DF_RU 2 /* Reaching uses. */
26 #define DF_LR 4 /* Live registers. */
27 #define DF_DU_CHAIN 8 /* Def-use chain. */
28 #define DF_UD_CHAIN 16 /* Use-def chain. */
29 #define DF_REG_INFO 32 /* Register info. */
30 #define DF_RD_CHAIN 64 /* Reg-def chain. */
31 #define DF_RU_CHAIN 128 /* Reg-use chain. */
33 #define DF_HARD_REGS 1024
35 enum df_ref_type
{DF_REF_REG_DEF
, DF_REF_REG_USE
, DF_REF_REG_MEM_LOAD
,
36 DF_REF_REG_MEM_STORE
};
38 #define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"}
40 /* ???> Perhaps all these data structures should be made private
41 to enforce the interface. */
44 /* Link on a def-use or use-def chain. */
52 /* Define a register reference structure. */
55 rtx reg
; /* The register referenced. */
56 basic_block bb
; /* BB containing ref. */
57 rtx insn
; /* Insn containing ref. */
58 rtx
*loc
; /* Loc is the location of the reg. */
59 struct df_link
*chain
; /* Head of def-use or use-def chain. */
60 enum df_ref_type type
; /* Type of ref. */
61 int id
; /* Ref index. */
65 /* One of these structures is allocated for every insn. */
68 struct df_link
*defs
; /* Head of insn-def chain. */
69 struct df_link
*uses
; /* Head of insn-use chain. */
70 /* ???? The following luid field should be considerd private so that
71 we can change it on the fly to accomodate new insns? */
72 int luid
; /* Logical UID. */
74 rtx insn
; /* Backpointer to the insn. */
79 /* One of these structures is allocated for every reg. */
82 struct df_link
*defs
; /* Head of reg-def chain. */
83 struct df_link
*uses
; /* Head of reg-use chain. */
90 /* One of these structures is allocated for every basic block. */
93 /* Reaching def bitmaps have def_id elements. */
98 /* Reaching use bitmaps have use_id elements. */
103 /* Live variable bitmaps have n_regs elements. */
116 int flags
; /* Indicates what's recorded. */
117 struct bb_info
*bbs
; /* Basic block table. */
118 struct ref
**defs
; /* Def table, indexed by def_id. */
119 struct ref
**uses
; /* Use table, indexed by use_id. */
120 struct ref
**reg_def_last
; /* Indexed by regno. */
121 struct reg_info
*regs
; /* Regs table, index by regno. */
122 unsigned int reg_size
; /* Size of regs table. */
123 struct insn_info
*insns
; /* Insn table, indexed by insn UID. */
124 unsigned int insn_size
; /* Size of insn table. */
125 unsigned int def_id
; /* Next def ID. */
126 unsigned int def_size
; /* Size of def table. */
127 unsigned int n_defs
; /* Size of def bitmaps. */
128 unsigned int use_id
; /* Next use ID. */
129 unsigned int use_size
; /* Size of use table. */
130 unsigned int n_uses
; /* Size of use bitmaps. */
131 unsigned int n_bbs
; /* Number of basic blocks. */
132 unsigned int n_regs
; /* Number of regs. */
133 unsigned int def_id_save
; /* Saved next def ID. */
134 unsigned int use_id_save
; /* Saved next use ID. */
135 bitmap insns_modified
; /* Insns that (may) have changed. */
136 bitmap bbs_modified
; /* Blocks that (may) have changed. */
137 bitmap all_blocks
; /* All blocks in CFG. */
138 /* The bitmap vector of dominators or NULL if not computed.
139 Ideally, this should be a pointer to a CFG object. */
153 #define DF_BB_INFO(REFS, BB) (&REFS->bbs[(BB)->index])
156 /* Macros to access the elements within the ref structure. */
157 #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->reg) == SUBREG \
158 ? SUBREG_REG ((REF)->reg) : ((REF)->reg))
159 #define DF_REF_REGNO(REF) REGNO (DF_REF_REAL_REG (REF))
160 #define DF_REF_REAL_LOC(REF) (GET_CODE ((REF)->reg) == SUBREG \
161 ? &SUBREG_REG ((REF)->reg) : ((REF)->loc))
162 #ifdef OLD_DF_INTERFACE
163 #define DF_REF_REG(REF) DF_REF_REAL_REG(REF)
164 #define DF_REF_LOC(REF) DF_REF_REAL_LOC(REF)
166 #define DF_REF_REG(REF) ((REF)->reg)
167 #define DF_REF_LOC(REF) ((REF)->loc)
169 #define DF_REF_BB(REF) ((REF)->bb)
170 #define DF_REF_BBNO(REF) ((REF)->bb->index)
171 #define DF_REF_INSN(REF) ((REF)->insn)
172 #define DF_REF_INSN_UID(REF) (INSN_UID ((REF)->insn))
173 #define DF_REF_TYPE(REF) ((REF)->type)
174 #define DF_REF_CHAIN(REF) ((REF)->chain)
175 #define DF_REF_ID(REF) ((REF)->id)
177 /* Macros to determine the reference type. */
179 #define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF)
180 #define DF_REF_REG_USE_P(REF) ((REF) && ! DF_REF_REG_DEF_P (REF))
181 #define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE)
182 #define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD)
183 #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \
184 || DF_REF_REG_MEM_LOAD_P (REF))
187 /* Macros to access the elements within the reg_info structure table. */
189 #define DF_REGNO_FIRST_DEF(DF, REGNUM) \
190 ((DF)->regs[REGNUM].defs ? (DF)->regs[REGNUM].defs->ref : 0)
191 #define DF_REGNO_LAST_USE(DF, REGNUM) \
192 ((DF)->regs[REGNUM].uses ? (DF)->regs[REGNUM].uses->ref : 0)
194 #define DF_REGNO_FIRST_BB(DF, REGNUM) \
195 (DF_REGNO_FIRST_DEF (DF, REGNUM) \
196 ? DF_REF_BB (DF_REGNO_FIRST_DEF (DF, REGNUM)) : 0)
197 #define DF_REGNO_LAST_BB(DF, REGNUM) \
198 (DF_REGNO_LAST_USE (DF, REGNUM) \
199 ? DF_REF_BB (DF_REGNO_LAST_USE (DF, REGNUM)) : 0)
202 /* Macros to access the elements within the insn_info structure table. */
204 #define DF_INSN_LUID(DF, INSN) ((DF)->insns[INSN_UID (INSN)].luid)
205 #define DF_INSN_DEFS(DF, INSN) ((DF)->insns[INSN_UID (INSN)].defs)
206 #define DF_INSN_USES(DF, INSN) ((DF)->insns[INSN_UID (INSN)].uses)
209 /* Functions to build and analyse dataflow information. */
211 extern struct df
*df_init
PARAMS ((void));
213 extern int df_analyse
PARAMS ((struct df
*, bitmap
, int));
215 extern void df_finish
PARAMS ((struct df
*));
217 extern void df_dump
PARAMS ((struct df
*, int, FILE *));
219 /* Functions to modify insns. */
221 extern void df_insn_modify
PARAMS ((struct df
*, basic_block
, rtx
));
223 extern rtx df_insn_delete
PARAMS ((struct df
*, basic_block
, rtx
));
225 extern rtx df_pattern_emit_before
PARAMS ((struct df
*, rtx
,
228 extern rtx df_jump_pattern_emit_after
PARAMS ((struct df
*, rtx
,
231 extern rtx df_pattern_emit_after
PARAMS ((struct df
*, rtx
,
234 extern rtx df_insn_move_before
PARAMS ((struct df
*, basic_block
, rtx
,
237 extern int df_reg_replace
PARAMS ((struct df
*, bitmap
, rtx
, rtx
));
239 extern int df_ref_reg_replace
PARAMS ((struct df
*, struct ref
*, rtx
, rtx
));
241 extern int df_ref_remove
PARAMS ((struct df
*, struct ref
*));
243 extern int df_insn_reg_replace
PARAMS ((struct df
*, basic_block
,
246 extern int df_insn_mem_replace
PARAMS ((struct df
*, basic_block
,
249 extern struct ref
*df_bb_def_use_swap
PARAMS ((struct df
*, basic_block
,
250 rtx
, rtx
, unsigned int));
253 /* Functions to query dataflow information. */
255 extern basic_block df_regno_bb
PARAMS((struct df
*, unsigned int));
257 extern int df_reg_lifetime
PARAMS ((struct df
*, rtx
));
259 extern int df_reg_global_p
PARAMS ((struct df
*, rtx
));
261 extern int df_insn_regno_def_p
PARAMS ((struct df
*,
262 basic_block
, rtx
, unsigned int));
264 extern int df_insn_dominates_all_uses_p
PARAMS ((struct df
*,
267 extern int df_insn_dominates_uses_p
PARAMS ((struct df
*, basic_block
,
270 extern int df_bb_reg_live_start_p
PARAMS ((struct df
*, basic_block
, rtx
));
272 extern int df_bb_reg_live_end_p
PARAMS ((struct df
*, basic_block
, rtx
));
274 extern int df_bb_regs_lives_compare
PARAMS ((struct df
*, basic_block
,
277 extern rtx df_bb_single_def_use_insn_find
PARAMS((struct df
*, basic_block
,
281 /* Functions for debugging from GDB. */
283 extern void debug_df_insn
PARAMS ((rtx
));
285 extern void debug_df_regno
PARAMS ((unsigned int));
287 extern void debug_df_reg
PARAMS ((rtx
));
289 extern void debug_df_defno
PARAMS ((unsigned int));
291 extern void debug_df_useno
PARAMS ((unsigned int));
293 extern void debug_df_ref
PARAMS ((struct ref
*));
295 extern void debug_df_chain
PARAMS ((struct df_link
*));
296 extern void df_insn_debug
PARAMS ((struct df
*, rtx
, FILE *));
297 extern void df_insn_debug_regno
PARAMS ((struct df
*, rtx
, FILE *));