1 /* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001-2018 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Simple optimization pass that splits independent uses of each pseudo,
22 increasing effectiveness of other optimizations. The optimization can
23 serve as an example of use for the dataflow module.
26 - We may use profile information and ignore infrequent use for the
27 purpose of web unifying, inserting the compensation code later to
28 implement full induction variable expansion for loops (currently
29 we expand only if the induction variable is dead afterward, which
30 is often the case). */
34 #include "coretypes.h"
38 #include "insn-config.h"
41 #include "tree-pass.h"
44 /* Find the root of unionfind tree (the representative of set). */
47 web_entry_base::unionfind_root ()
49 web_entry_base
*element
= this, *element1
= this, *element2
;
51 while (element
->pred ())
52 element
= element
->pred ();
53 while (element1
->pred ())
55 element2
= element1
->pred ();
56 element1
->set_pred (element
);
63 Return true if FIRST and SECOND points to the same web entry structure and
64 nothing is done. Otherwise, return false. */
67 unionfind_union (web_entry_base
*first
, web_entry_base
*second
)
69 first
= first
->unionfind_root ();
70 second
= second
->unionfind_root ();
73 second
->set_pred (first
);
77 class web_entry
: public web_entry_base
83 rtx
reg () { return reg_pvt
; }
84 void set_reg (rtx r
) { reg_pvt
= r
; }
87 /* For INSN, union all defs and uses that are linked by match_dup.
88 FUN is the function that does the union. */
91 union_match_dups (rtx_insn
*insn
, web_entry
*def_entry
, web_entry
*use_entry
,
92 bool (*fun
) (web_entry_base
*, web_entry_base
*))
94 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
95 df_ref use_link
= DF_INSN_INFO_USES (insn_info
);
96 df_ref def_link
= DF_INSN_INFO_DEFS (insn_info
);
97 struct web_entry
*dup_entry
;
102 for (i
= 0; i
< recog_data
.n_dups
; i
++)
104 int op
= recog_data
.dup_num
[i
];
105 enum op_type type
= recog_data
.operand_type
[op
];
107 struct web_entry
*entry
;
109 dup_entry
= use_entry
;
110 for (dupref
= use_link
; dupref
; dupref
= DF_REF_NEXT_LOC (dupref
))
111 if (DF_REF_LOC (dupref
) == recog_data
.dup_loc
[i
])
114 if (dupref
== NULL
&& type
== OP_INOUT
)
116 dup_entry
= def_entry
;
117 for (dupref
= def_link
; dupref
; dupref
= DF_REF_NEXT_LOC (dupref
))
118 if (DF_REF_LOC (dupref
) == recog_data
.dup_loc
[i
])
121 /* ??? *DUPREF can still be zero, because when an operand matches
122 a memory, DF_REF_LOC (use_link[n]) points to the register part
123 of the address, whereas recog_data.dup_loc[m] points to the
124 entire memory ref, thus we fail to find the duplicate entry,
125 even though it is there.
126 Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
127 -O3 -fomit-frame-pointer -funroll-loops */
129 || DF_REF_REGNO (dupref
) < FIRST_PSEUDO_REGISTER
)
132 ref
= type
== OP_IN
? use_link
: def_link
;
133 entry
= type
== OP_IN
? use_entry
: def_entry
;
134 for (; ref
; ref
= DF_REF_NEXT_LOC (ref
))
136 rtx
*l
= DF_REF_LOC (ref
);
137 if (l
== recog_data
.operand_loc
[op
])
139 if (l
&& DF_REF_REAL_LOC (ref
) == recog_data
.operand_loc
[op
])
143 if (!ref
&& type
== OP_INOUT
)
146 for (ref
= use_link
; ref
; ref
= DF_REF_NEXT_LOC (ref
))
148 rtx
*l
= DF_REF_LOC (ref
);
149 if (l
== recog_data
.operand_loc
[op
])
151 if (l
&& DF_REF_REAL_LOC (ref
) == recog_data
.operand_loc
[op
])
157 (*fun
) (dup_entry
+ DF_REF_ID (dupref
), entry
+ DF_REF_ID (ref
));
161 /* For each use, all possible defs reaching it must come in the same
162 register, union them.
163 FUN is the function that does the union.
165 In USED, we keep the DF_REF_ID of the first uninitialized uses of a
166 register, so that all uninitialized uses of the register can be
167 combined into a single web. We actually offset it by 2, because
168 the values 0 and 1 are reserved for use by entry_register. */
171 union_defs (df_ref use
, web_entry
*def_entry
,
172 unsigned int *used
, web_entry
*use_entry
,
173 bool (*fun
) (web_entry_base
*, web_entry_base
*))
175 struct df_insn_info
*insn_info
= DF_REF_INSN_INFO (use
);
176 struct df_link
*link
= DF_REF_CHAIN (use
);
183 set
= single_set (insn_info
->insn
);
184 FOR_EACH_INSN_INFO_EQ_USE (eq_use
, insn_info
)
186 && DF_REF_REAL_REG (use
) == DF_REF_REAL_REG (eq_use
))
187 (*fun
) (use_entry
+ DF_REF_ID (use
), use_entry
+ DF_REF_ID (eq_use
));
192 /* Union all occurrences of the same register in reg notes. */
194 /* Recognize trivial noop moves and attempt to keep them as noop. */
197 && SET_SRC (set
) == DF_REF_REG (use
)
198 && SET_SRC (set
) == SET_DEST (set
))
202 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
203 if (DF_REF_REAL_REG (use
) == DF_REF_REAL_REG (def
))
204 (*fun
) (use_entry
+ DF_REF_ID (use
), def_entry
+ DF_REF_ID (def
));
207 /* UD chains of uninitialized REGs are empty. Keeping all uses of
208 the same uninitialized REG in a single web is not necessary for
209 correctness, since the uses are undefined, but it's wasteful to
210 allocate one register or slot for each reference. Furthermore,
211 creating new pseudos for uninitialized references in debug insns
212 (see PR 42631) causes -fcompare-debug failures. We record the
213 number of the first uninitialized reference we found, and merge
214 with it any other uninitialized references to the same
218 int regno
= REGNO (DF_REF_REAL_REG (use
));
220 (*fun
) (use_entry
+ DF_REF_ID (use
), use_entry
+ used
[regno
] - 2);
222 used
[regno
] = DF_REF_ID (use
) + 2;
227 (*fun
) (use_entry
+ DF_REF_ID (use
),
228 def_entry
+ DF_REF_ID (link
->ref
));
232 /* A READ_WRITE use requires the corresponding def to be in the same
233 register. Find it and union. */
234 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
239 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
240 if (DF_REF_REAL_REG (use
) == DF_REF_REAL_REG (def
))
241 (*fun
) (use_entry
+ DF_REF_ID (use
), def_entry
+ DF_REF_ID (def
));
245 /* Find the corresponding register for the given entry. */
248 entry_register (web_entry
*entry
, df_ref ref
, unsigned int *used
)
253 /* Find the corresponding web and see if it has been visited. */
254 root
= (web_entry
*)entry
->unionfind_root ();
258 /* We are seeing this web for the first time, do the assignment. */
259 reg
= DF_REF_REAL_REG (ref
);
261 /* In case the original register is already assigned, generate new
262 one. Since we use USED to merge uninitialized refs into a single
263 web, we might found an element to be nonzero without our having
264 used it. Test for 1, because union_defs saves it for our use,
265 and there won't be any use for the other values when we get to
267 if (used
[REGNO (reg
)] != 1)
268 newreg
= reg
, used
[REGNO (reg
)] = 1;
271 newreg
= gen_reg_rtx (GET_MODE (reg
));
272 REG_USERVAR_P (newreg
) = REG_USERVAR_P (reg
);
273 REG_POINTER (newreg
) = REG_POINTER (reg
);
274 REG_ATTRS (newreg
) = REG_ATTRS (reg
);
276 fprintf (dump_file
, "Web oldreg=%i newreg=%i\n", REGNO (reg
),
280 root
->set_reg (newreg
);
284 /* Replace the reference by REG. */
287 replace_ref (df_ref ref
, rtx reg
)
289 rtx oldreg
= DF_REF_REAL_REG (ref
);
290 rtx
*loc
= DF_REF_REAL_LOC (ref
);
291 unsigned int uid
= DF_REF_INSN_UID (ref
);
296 fprintf (dump_file
, "Updating insn %i (%i->%i)\n",
297 uid
, REGNO (oldreg
), REGNO (reg
));
299 df_insn_rescan (DF_REF_INSN (ref
));
305 const pass_data pass_data_web
=
309 OPTGROUP_NONE
, /* optinfo_flags */
311 0, /* properties_required */
312 0, /* properties_provided */
313 0, /* properties_destroyed */
314 0, /* todo_flags_start */
315 TODO_df_finish
, /* todo_flags_finish */
318 class pass_web
: public rtl_opt_pass
321 pass_web (gcc::context
*ctxt
)
322 : rtl_opt_pass (pass_data_web
, ctxt
)
325 /* opt_pass methods: */
326 virtual bool gate (function
*) { return (optimize
> 0 && flag_web
); }
327 virtual unsigned int execute (function
*);
332 pass_web::execute (function
*fun
)
334 web_entry
*def_entry
;
335 web_entry
*use_entry
;
336 unsigned int max
= max_reg_num ();
339 unsigned int uses_num
= 0;
342 df_set_flags (DF_NO_HARD_REGS
+ DF_EQ_NOTES
);
343 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
344 df_chain_add_problem (DF_UD_CHAIN
);
346 df_set_flags (DF_DEFER_INSN_RESCAN
);
348 /* Assign ids to the uses. */
349 FOR_ALL_BB_FN (bb
, fun
)
350 FOR_BB_INSNS (bb
, insn
)
352 if (NONDEBUG_INSN_P (insn
))
354 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
356 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
357 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
358 DF_REF_ID (use
) = uses_num
++;
359 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
360 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
361 DF_REF_ID (use
) = uses_num
++;
365 /* Record the number of uses and defs at the beginning of the optimization. */
366 def_entry
= XCNEWVEC (web_entry
, DF_DEFS_TABLE_SIZE ());
367 used
= XCNEWVEC (unsigned, max
);
368 use_entry
= XCNEWVEC (web_entry
, uses_num
);
370 /* Produce the web. */
371 FOR_ALL_BB_FN (bb
, fun
)
372 FOR_BB_INSNS (bb
, insn
)
373 if (NONDEBUG_INSN_P (insn
))
375 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
377 union_match_dups (insn
, def_entry
, use_entry
, unionfind_union
);
378 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
379 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
380 union_defs (use
, def_entry
, used
, use_entry
, unionfind_union
);
381 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
382 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
383 union_defs (use
, def_entry
, used
, use_entry
, unionfind_union
);
386 /* Update the instruction stream, allocating new registers for split pseudos
388 FOR_ALL_BB_FN (bb
, fun
)
389 FOR_BB_INSNS (bb
, insn
)
390 if (NONDEBUG_INSN_P (insn
)
391 /* Ignore naked clobber. For example, reg 134 in the second insn
392 of the following sequence will not be replaced.
394 (insn (clobber (reg:SI 134)))
396 (insn (set (reg:SI 0 r0) (reg:SI 134)))
398 Thus the later passes can optimize them away. */
399 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
401 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
403 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
404 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
405 replace_ref (use
, entry_register (use_entry
+ DF_REF_ID (use
),
407 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
408 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
409 replace_ref (use
, entry_register (use_entry
+ DF_REF_ID (use
),
411 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
412 if (DF_REF_REGNO (def
) >= FIRST_PSEUDO_REGISTER
)
413 replace_ref (def
, entry_register (def_entry
+ DF_REF_ID (def
),
426 make_pass_web (gcc::context
*ctxt
)
428 return new pass_web (ctxt
);