1 /* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001-2014 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.
25 We don't split registers with REG_USERVAR set unless -fmessy-debugging
26 is specified, because debugging information about such split variables
30 - We may use profile information and ignore infrequent use for the
31 purpose of web unifying, inserting the compensation code later to
32 implement full induction variable expansion for loops (currently
33 we expand only if the induction variable is dead afterward, which
34 is often the case). */
38 #include "coretypes.h"
40 #include "diagnostic-core.h"
43 #include "hard-reg-set.h"
46 #include "basic-block.h"
49 #include "insn-config.h"
51 #include "tree-pass.h"
54 /* Find the root of unionfind tree (the representative of set). */
57 web_entry_base::unionfind_root ()
59 web_entry_base
*element
= this, *element1
= this, *element2
;
61 while (element
->pred ())
62 element
= element
->pred ();
63 while (element1
->pred ())
65 element2
= element1
->pred ();
66 element1
->set_pred (element
);
73 Return true if FIRST and SECOND points to the same web entry structure and
74 nothing is done. Otherwise, return false. */
77 unionfind_union (web_entry_base
*first
, web_entry_base
*second
)
79 first
= first
->unionfind_root ();
80 second
= second
->unionfind_root ();
83 second
->set_pred (first
);
87 class web_entry
: public web_entry_base
93 rtx
reg () { return reg_pvt
; }
94 void set_reg (rtx r
) { reg_pvt
= r
; }
97 /* For INSN, union all defs and uses that are linked by match_dup.
98 FUN is the function that does the union. */
101 union_match_dups (rtx insn
, web_entry
*def_entry
, web_entry
*use_entry
,
102 bool (*fun
) (web_entry_base
*, web_entry_base
*))
104 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
105 df_ref
*use_link
= DF_INSN_INFO_USES (insn_info
);
106 df_ref
*def_link
= DF_INSN_INFO_DEFS (insn_info
);
107 struct web_entry
*dup_entry
;
112 for (i
= 0; i
< recog_data
.n_dups
; i
++)
114 int op
= recog_data
.dup_num
[i
];
115 enum op_type type
= recog_data
.operand_type
[op
];
116 df_ref
*ref
, *dupref
;
117 struct web_entry
*entry
;
119 for (dup_entry
= use_entry
, dupref
= use_link
; *dupref
; dupref
++)
120 if (DF_REF_LOC (*dupref
) == recog_data
.dup_loc
[i
])
123 if (*dupref
== NULL
&& type
== OP_INOUT
)
126 for (dup_entry
= def_entry
, dupref
= def_link
; *dupref
; dupref
++)
127 if (DF_REF_LOC (*dupref
) == recog_data
.dup_loc
[i
])
130 /* ??? *DUPREF can still be zero, because when an operand matches
131 a memory, DF_REF_LOC (use_link[n]) points to the register part
132 of the address, whereas recog_data.dup_loc[m] points to the
133 entire memory ref, thus we fail to find the duplicate entry,
134 even though it is there.
135 Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
136 -O3 -fomit-frame-pointer -funroll-loops */
138 || DF_REF_REGNO (*dupref
) < FIRST_PSEUDO_REGISTER
)
141 ref
= type
== OP_IN
? use_link
: def_link
;
142 entry
= type
== OP_IN
? use_entry
: def_entry
;
145 rtx
*l
= DF_REF_LOC (*ref
);
146 if (l
== recog_data
.operand_loc
[op
])
148 if (l
&& DF_REF_REAL_LOC (*ref
) == recog_data
.operand_loc
[op
])
152 if (!*ref
&& type
== OP_INOUT
)
154 for (ref
= use_link
, entry
= use_entry
; *ref
; ref
++)
156 rtx
*l
= DF_REF_LOC (*ref
);
157 if (l
== recog_data
.operand_loc
[op
])
159 if (l
&& DF_REF_REAL_LOC (*ref
) == recog_data
.operand_loc
[op
])
165 (*fun
) (dup_entry
+ DF_REF_ID (*dupref
), entry
+ DF_REF_ID (*ref
));
169 /* For each use, all possible defs reaching it must come in the same
170 register, union them.
171 FUN is the function that does the union.
173 In USED, we keep the DF_REF_ID of the first uninitialized uses of a
174 register, so that all uninitialized uses of the register can be
175 combined into a single web. We actually offset it by 2, because
176 the values 0 and 1 are reserved for use by entry_register. */
179 union_defs (df_ref use
, web_entry
*def_entry
,
180 unsigned int *used
, web_entry
*use_entry
,
181 bool (*fun
) (web_entry_base
*, web_entry_base
*))
183 struct df_insn_info
*insn_info
= DF_REF_INSN_INFO (use
);
184 struct df_link
*link
= DF_REF_CHAIN (use
);
191 rtx insn
= insn_info
->insn
;
192 eq_use_link
= DF_INSN_INFO_EQ_USES (insn_info
);
193 def_link
= DF_INSN_INFO_DEFS (insn_info
);
194 set
= single_set (insn
);
198 /* An artificial use. It links up with nothing. */
204 /* Union all occurrences of the same register in reg notes. */
209 if (use
!= *eq_use_link
210 && DF_REF_REAL_REG (use
) == DF_REF_REAL_REG (*eq_use_link
))
211 (*fun
) (use_entry
+ DF_REF_ID (use
),
212 use_entry
+ DF_REF_ID (*eq_use_link
));
216 /* Recognize trivial noop moves and attempt to keep them as noop. */
219 && SET_SRC (set
) == DF_REF_REG (use
)
220 && SET_SRC (set
) == SET_DEST (set
))
225 if (DF_REF_REAL_REG (use
) == DF_REF_REAL_REG (*def_link
))
226 (*fun
) (use_entry
+ DF_REF_ID (use
),
227 def_entry
+ DF_REF_ID (*def_link
));
232 /* UD chains of uninitialized REGs are empty. Keeping all uses of
233 the same uninitialized REG in a single web is not necessary for
234 correctness, since the uses are undefined, but it's wasteful to
235 allocate one register or slot for each reference. Furthermore,
236 creating new pseudos for uninitialized references in debug insns
237 (see PR 42631) causes -fcompare-debug failures. We record the
238 number of the first uninitialized reference we found, and merge
239 with it any other uninitialized references to the same
243 int regno
= REGNO (DF_REF_REAL_REG (use
));
245 (*fun
) (use_entry
+ DF_REF_ID (use
), use_entry
+ used
[regno
] - 2);
247 used
[regno
] = DF_REF_ID (use
) + 2;
252 (*fun
) (use_entry
+ DF_REF_ID (use
),
253 def_entry
+ DF_REF_ID (link
->ref
));
257 /* A READ_WRITE use requires the corresponding def to be in the same
258 register. Find it and union. */
259 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
264 link
= DF_INSN_INFO_DEFS (insn_info
);
271 if (DF_REF_REAL_REG (*link
) == DF_REF_REAL_REG (use
))
272 (*fun
) (use_entry
+ DF_REF_ID (use
),
273 def_entry
+ DF_REF_ID (*link
));
279 /* Find the corresponding register for the given entry. */
282 entry_register (web_entry
*entry
, df_ref ref
, unsigned int *used
)
287 /* Find the corresponding web and see if it has been visited. */
288 root
= (web_entry
*)entry
->unionfind_root ();
292 /* We are seeing this web for the first time, do the assignment. */
293 reg
= DF_REF_REAL_REG (ref
);
295 /* In case the original register is already assigned, generate new
296 one. Since we use USED to merge uninitialized refs into a single
297 web, we might found an element to be nonzero without our having
298 used it. Test for 1, because union_defs saves it for our use,
299 and there won't be any use for the other values when we get to
301 if (used
[REGNO (reg
)] != 1)
302 newreg
= reg
, used
[REGNO (reg
)] = 1;
305 newreg
= gen_reg_rtx (GET_MODE (reg
));
306 REG_USERVAR_P (newreg
) = REG_USERVAR_P (reg
);
307 REG_POINTER (newreg
) = REG_POINTER (reg
);
308 REG_ATTRS (newreg
) = REG_ATTRS (reg
);
310 fprintf (dump_file
, "Web oldreg=%i newreg=%i\n", REGNO (reg
),
314 root
->set_reg (newreg
);
318 /* Replace the reference by REG. */
321 replace_ref (df_ref ref
, rtx reg
)
323 rtx oldreg
= DF_REF_REAL_REG (ref
);
324 rtx
*loc
= DF_REF_REAL_LOC (ref
);
325 unsigned int uid
= DF_REF_INSN_UID (ref
);
330 fprintf (dump_file
, "Updating insn %i (%i->%i)\n",
331 uid
, REGNO (oldreg
), REGNO (reg
));
333 df_insn_rescan (DF_REF_INSN (ref
));
338 gate_handle_web (void)
340 return (optimize
> 0 && flag_web
);
343 /* Main entry point. */
348 web_entry
*def_entry
;
349 web_entry
*use_entry
;
350 unsigned int max
= max_reg_num ();
353 unsigned int uses_num
= 0;
356 df_set_flags (DF_NO_HARD_REGS
+ DF_EQ_NOTES
);
357 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
358 df_chain_add_problem (DF_UD_CHAIN
);
360 df_set_flags (DF_DEFER_INSN_RESCAN
);
362 /* Assign ids to the uses. */
363 FOR_ALL_BB_FN (bb
, cfun
)
364 FOR_BB_INSNS (bb
, insn
)
366 unsigned int uid
= INSN_UID (insn
);
367 if (NONDEBUG_INSN_P (insn
))
370 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
372 df_ref use
= *use_rec
;
373 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
374 DF_REF_ID (use
) = uses_num
++;
376 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
378 df_ref use
= *use_rec
;
379 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
380 DF_REF_ID (use
) = uses_num
++;
385 /* Record the number of uses and defs at the beginning of the optimization. */
386 def_entry
= XCNEWVEC (web_entry
, DF_DEFS_TABLE_SIZE ());
387 used
= XCNEWVEC (unsigned, max
);
388 use_entry
= XCNEWVEC (web_entry
, uses_num
);
390 /* Produce the web. */
391 FOR_ALL_BB_FN (bb
, cfun
)
392 FOR_BB_INSNS (bb
, insn
)
394 unsigned int uid
= INSN_UID (insn
);
395 if (NONDEBUG_INSN_P (insn
))
398 union_match_dups (insn
, def_entry
, use_entry
, unionfind_union
);
399 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
401 df_ref use
= *use_rec
;
402 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
403 union_defs (use
, def_entry
, used
, use_entry
, unionfind_union
);
405 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
407 df_ref use
= *use_rec
;
408 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
409 union_defs (use
, def_entry
, used
, use_entry
, unionfind_union
);
414 /* Update the instruction stream, allocating new registers for split pseudos
416 FOR_ALL_BB_FN (bb
, cfun
)
417 FOR_BB_INSNS (bb
, insn
)
419 unsigned int uid
= INSN_UID (insn
);
421 if (NONDEBUG_INSN_P (insn
)
422 /* Ignore naked clobber. For example, reg 134 in the second insn
423 of the following sequence will not be replaced.
425 (insn (clobber (reg:SI 134)))
427 (insn (set (reg:SI 0 r0) (reg:SI 134)))
429 Thus the later passes can optimize them away. */
430 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
434 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
436 df_ref use
= *use_rec
;
437 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
438 replace_ref (use
, entry_register (use_entry
+ DF_REF_ID (use
), use
, used
));
440 for (use_rec
= DF_INSN_UID_EQ_USES (uid
); *use_rec
; use_rec
++)
442 df_ref use
= *use_rec
;
443 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
)
444 replace_ref (use
, entry_register (use_entry
+ DF_REF_ID (use
), use
, used
));
446 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
448 df_ref def
= *def_rec
;
449 if (DF_REF_REGNO (def
) >= FIRST_PSEUDO_REGISTER
)
450 replace_ref (def
, entry_register (def_entry
+ DF_REF_ID (def
), def
, used
));
463 const pass_data pass_data_web
=
467 OPTGROUP_NONE
, /* optinfo_flags */
469 true, /* has_execute */
471 0, /* properties_required */
472 0, /* properties_provided */
473 0, /* properties_destroyed */
474 0, /* todo_flags_start */
475 ( TODO_df_finish
| TODO_verify_rtl_sharing
), /* todo_flags_finish */
478 class pass_web
: public rtl_opt_pass
481 pass_web (gcc::context
*ctxt
)
482 : rtl_opt_pass (pass_data_web
, ctxt
)
485 /* opt_pass methods: */
486 bool gate () { return gate_handle_web (); }
487 unsigned int execute () { return web_main (); }
494 make_pass_web (gcc::context
*ctxt
)
496 return new pass_web (ctxt
);