* tree-if-conv.c: Fix various typos in comments.
[official-gcc.git] / gcc / ree.c
blob016659c6cb191033418be457cc83fa6cad918f68
1 /* Redundant Extension Elimination pass for the GNU compiler.
2 Copyright (C) 2010-2015 Free Software Foundation, Inc.
3 Contributed by Ilya Enkovich (ilya.enkovich@intel.com)
5 Based on the Redundant Zero-extension elimination pass contributed by
6 Sriraman Tallam (tmsriram@google.com) and Silvius Rus (rus@google.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
13 version.
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 for more details.
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
25 /* Problem Description :
26 --------------------
27 This pass is intended to remove redundant extension instructions.
28 Such instructions appear for different reasons. We expect some of
29 them due to implicit zero-extension in 64-bit registers after writing
30 to their lower 32-bit half (e.g. for the x86-64 architecture).
31 Another possible reason is a type cast which follows a load (for
32 instance a register restore) and which can be combined into a single
33 instruction, and for which earlier local passes, e.g. the combiner,
34 weren't able to optimize.
36 How does this pass work ?
37 --------------------------
39 This pass is run after register allocation. Hence, all registers that
40 this pass deals with are hard registers. This pass first looks for an
41 extension instruction that could possibly be redundant. Such extension
42 instructions show up in RTL with the pattern :
43 (set (reg:<SWI248> x) (any_extend:<SWI248> (reg:<SWI124> x))),
44 where x can be any hard register.
45 Now, this pass tries to eliminate this instruction by merging the
46 extension with the definitions of register x. For instance, if
47 one of the definitions of register x was :
48 (set (reg:SI x) (plus:SI (reg:SI z1) (reg:SI z2))),
49 followed by extension :
50 (set (reg:DI x) (zero_extend:DI (reg:SI x)))
51 then the combination converts this into :
52 (set (reg:DI x) (zero_extend:DI (plus:SI (reg:SI z1) (reg:SI z2)))).
53 If all the merged definitions are recognizable assembly instructions,
54 the extension is effectively eliminated.
56 For example, for the x86-64 architecture, implicit zero-extensions
57 are captured with appropriate patterns in the i386.md file. Hence,
58 these merged definition can be matched to a single assembly instruction.
59 The original extension instruction is then deleted if all the
60 definitions can be merged.
62 However, there are cases where the definition instruction cannot be
63 merged with an extension. Examples are CALL instructions. In such
64 cases, the original extension is not redundant and this pass does
65 not delete it.
67 Handling conditional moves :
68 ----------------------------
70 Architectures like x86-64 support conditional moves whose semantics for
71 extension differ from the other instructions. For instance, the
72 instruction *cmov ebx, eax*
73 zero-extends eax onto rax only when the move from ebx to eax happens.
74 Otherwise, eax may not be zero-extended. Consider conditional moves as
75 RTL instructions of the form
76 (set (reg:SI x) (if_then_else (cond) (reg:SI y) (reg:SI z))).
77 This pass tries to merge an extension with a conditional move by
78 actually merging the definitions of y and z with an extension and then
79 converting the conditional move into :
80 (set (reg:DI x) (if_then_else (cond) (reg:DI y) (reg:DI z))).
81 Since registers y and z are extended, register x will also be extended
82 after the conditional move. Note that this step has to be done
83 transitively since the definition of a conditional copy can be
84 another conditional copy.
86 Motivating Example I :
87 ---------------------
88 For this program :
89 **********************************************
90 bad_code.c
92 int mask[1000];
94 int foo(unsigned x)
96 if (x < 10)
97 x = x * 45;
98 else
99 x = x * 78;
100 return mask[x];
102 **********************************************
104 $ gcc -O2 bad_code.c
105 ........
106 400315: b8 4e 00 00 00 mov $0x4e,%eax
107 40031a: 0f af f8 imul %eax,%edi
108 40031d: 89 ff mov %edi,%edi - useless extension
109 40031f: 8b 04 bd 60 19 40 00 mov 0x401960(,%rdi,4),%eax
110 400326: c3 retq
111 ......
112 400330: ba 2d 00 00 00 mov $0x2d,%edx
113 400335: 0f af fa imul %edx,%edi
114 400338: 89 ff mov %edi,%edi - useless extension
115 40033a: 8b 04 bd 60 19 40 00 mov 0x401960(,%rdi,4),%eax
116 400341: c3 retq
118 $ gcc -O2 -free bad_code.c
119 ......
120 400315: 6b ff 4e imul $0x4e,%edi,%edi
121 400318: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax
122 40031f: c3 retq
123 400320: 6b ff 2d imul $0x2d,%edi,%edi
124 400323: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax
125 40032a: c3 retq
127 Motivating Example II :
128 ---------------------
130 Here is an example with a conditional move.
132 For this program :
133 **********************************************
135 unsigned long long foo(unsigned x , unsigned y)
137 unsigned z;
138 if (x > 100)
139 z = x + y;
140 else
141 z = x - y;
142 return (unsigned long long)(z);
145 $ gcc -O2 bad_code.c
146 ............
147 400360: 8d 14 3e lea (%rsi,%rdi,1),%edx
148 400363: 89 f8 mov %edi,%eax
149 400365: 29 f0 sub %esi,%eax
150 400367: 83 ff 65 cmp $0x65,%edi
151 40036a: 0f 43 c2 cmovae %edx,%eax
152 40036d: 89 c0 mov %eax,%eax - useless extension
153 40036f: c3 retq
155 $ gcc -O2 -free bad_code.c
156 .............
157 400360: 89 fa mov %edi,%edx
158 400362: 8d 04 3e lea (%rsi,%rdi,1),%eax
159 400365: 29 f2 sub %esi,%edx
160 400367: 83 ff 65 cmp $0x65,%edi
161 40036a: 89 d6 mov %edx,%esi
162 40036c: 48 0f 42 c6 cmovb %rsi,%rax
163 400370: c3 retq
165 Motivating Example III :
166 ---------------------
168 Here is an example with a type cast.
170 For this program :
171 **********************************************
173 void test(int size, unsigned char *in, unsigned char *out)
175 int i;
176 unsigned char xr, xg, xy=0;
178 for (i = 0; i < size; i++) {
179 xr = *in++;
180 xg = *in++;
181 xy = (unsigned char) ((19595*xr + 38470*xg) >> 16);
182 *out++ = xy;
186 $ gcc -O2 bad_code.c
187 ............
188 10: 0f b6 0e movzbl (%rsi),%ecx
189 13: 0f b6 46 01 movzbl 0x1(%rsi),%eax
190 17: 48 83 c6 02 add $0x2,%rsi
191 1b: 0f b6 c9 movzbl %cl,%ecx - useless extension
192 1e: 0f b6 c0 movzbl %al,%eax - useless extension
193 21: 69 c9 8b 4c 00 00 imul $0x4c8b,%ecx,%ecx
194 27: 69 c0 46 96 00 00 imul $0x9646,%eax,%eax
196 $ gcc -O2 -free bad_code.c
197 .............
198 10: 0f b6 0e movzbl (%rsi),%ecx
199 13: 0f b6 46 01 movzbl 0x1(%rsi),%eax
200 17: 48 83 c6 02 add $0x2,%rsi
201 1b: 69 c9 8b 4c 00 00 imul $0x4c8b,%ecx,%ecx
202 21: 69 c0 46 96 00 00 imul $0x9646,%eax,%eax
204 Usefulness :
205 ----------
207 The original redundant zero-extension elimination pass reported reduction
208 of the dynamic instruction count of a compression benchmark by 2.8% and
209 improvement of its run time by about 1%.
211 The additional performance gain with the enhanced pass is mostly expected
212 on in-order architectures where redundancy cannot be compensated by out of
213 order execution. Measurements showed up to 10% performance gain (reduced
214 run time) on EEMBC 2.0 benchmarks on Atom processor with geomean performance
215 gain 1%. */
218 #include "config.h"
219 #include "system.h"
220 #include "coretypes.h"
221 #include "backend.h"
222 #include "tree.h"
223 #include "rtl.h"
224 #include "df.h"
225 #include "alias.h"
226 #include "tm_p.h"
227 #include "flags.h"
228 #include "regs.h"
229 #include "cfgrtl.h"
230 #include "insn-config.h"
231 #include "expmed.h"
232 #include "dojump.h"
233 #include "explow.h"
234 #include "calls.h"
235 #include "emit-rtl.h"
236 #include "varasm.h"
237 #include "stmt.h"
238 #include "expr.h"
239 #include "insn-attr.h"
240 #include "recog.h"
241 #include "diagnostic-core.h"
242 #include "target.h"
243 #include "insn-codes.h"
244 #include "optabs.h"
245 #include "rtlhooks-def.h"
246 #include "params.h"
247 #include "tree-pass.h"
248 #include "cgraph.h"
250 /* This structure represents a candidate for elimination. */
252 typedef struct ext_cand
254 /* The expression. */
255 const_rtx expr;
257 /* The kind of extension. */
258 enum rtx_code code;
260 /* The destination mode. */
261 machine_mode mode;
263 /* The instruction where it lives. */
264 rtx_insn *insn;
265 } ext_cand;
268 static int max_insn_uid;
270 /* Update or remove REG_EQUAL or REG_EQUIV notes for INSN. */
272 static bool
273 update_reg_equal_equiv_notes (rtx_insn *insn, machine_mode new_mode,
274 machine_mode old_mode, enum rtx_code code)
276 rtx *loc = &REG_NOTES (insn);
277 while (*loc)
279 enum reg_note kind = REG_NOTE_KIND (*loc);
280 if (kind == REG_EQUAL || kind == REG_EQUIV)
282 rtx orig_src = XEXP (*loc, 0);
283 /* Update equivalency constants. Recall that RTL constants are
284 sign-extended. */
285 if (GET_CODE (orig_src) == CONST_INT
286 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (new_mode))
288 if (INTVAL (orig_src) >= 0 || code == SIGN_EXTEND)
289 /* Nothing needed. */;
290 else
292 /* Zero-extend the negative constant by masking out the
293 bits outside the source mode. */
294 rtx new_const_int
295 = gen_int_mode (INTVAL (orig_src)
296 & GET_MODE_MASK (old_mode),
297 new_mode);
298 if (!validate_change (insn, &XEXP (*loc, 0),
299 new_const_int, true))
300 return false;
302 loc = &XEXP (*loc, 1);
304 /* Drop all other notes, they assume a wrong mode. */
305 else if (!validate_change (insn, loc, XEXP (*loc, 1), true))
306 return false;
308 else
309 loc = &XEXP (*loc, 1);
311 return true;
314 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND)
315 and a pointer to the SET rtx (ORIG_SET) that needs to be modified,
316 this code modifies the SET rtx to a new SET rtx that extends the
317 right hand expression into a register on the left hand side. Note
318 that multiple assumptions are made about the nature of the set that
319 needs to be true for this to work and is called from merge_def_and_ext.
321 Original :
322 (set (reg a) (expression))
324 Transform :
325 (set (reg a) (any_extend (expression)))
327 Special Cases :
328 If the expression is a constant or another extension, then directly
329 assign it to the register. */
331 static bool
332 combine_set_extension (ext_cand *cand, rtx_insn *curr_insn, rtx *orig_set)
334 rtx orig_src = SET_SRC (*orig_set);
335 machine_mode orig_mode = GET_MODE (SET_DEST (*orig_set));
336 rtx new_set;
337 rtx cand_pat = PATTERN (cand->insn);
339 /* If the extension's source/destination registers are not the same
340 then we need to change the original load to reference the destination
341 of the extension. Then we need to emit a copy from that destination
342 to the original destination of the load. */
343 rtx new_reg;
344 bool copy_needed
345 = (REGNO (SET_DEST (cand_pat)) != REGNO (XEXP (SET_SRC (cand_pat), 0)));
346 if (copy_needed)
347 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (cand_pat)));
348 else
349 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (*orig_set)));
351 #if 0
352 /* Rethinking test. Temporarily disabled. */
353 /* We're going to be widening the result of DEF_INSN, ensure that doing so
354 doesn't change the number of hard registers needed for the result. */
355 if (HARD_REGNO_NREGS (REGNO (new_reg), cand->mode)
356 != HARD_REGNO_NREGS (REGNO (SET_DEST (*orig_set)),
357 GET_MODE (SET_DEST (*orig_set))))
358 return false;
359 #endif
361 /* Merge constants by directly moving the constant into the register under
362 some conditions. Recall that RTL constants are sign-extended. */
363 if (GET_CODE (orig_src) == CONST_INT
364 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (cand->mode))
366 if (INTVAL (orig_src) >= 0 || cand->code == SIGN_EXTEND)
367 new_set = gen_rtx_SET (new_reg, orig_src);
368 else
370 /* Zero-extend the negative constant by masking out the bits outside
371 the source mode. */
372 rtx new_const_int
373 = gen_int_mode (INTVAL (orig_src) & GET_MODE_MASK (orig_mode),
374 GET_MODE (new_reg));
375 new_set = gen_rtx_SET (new_reg, new_const_int);
378 else if (GET_MODE (orig_src) == VOIDmode)
380 /* This is mostly due to a call insn that should not be optimized. */
381 return false;
383 else if (GET_CODE (orig_src) == cand->code)
385 /* Here is a sequence of two extensions. Try to merge them. */
386 rtx temp_extension
387 = gen_rtx_fmt_e (cand->code, cand->mode, XEXP (orig_src, 0));
388 rtx simplified_temp_extension = simplify_rtx (temp_extension);
389 if (simplified_temp_extension)
390 temp_extension = simplified_temp_extension;
391 new_set = gen_rtx_SET (new_reg, temp_extension);
393 else if (GET_CODE (orig_src) == IF_THEN_ELSE)
395 /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
396 in general, IF_THEN_ELSE should not be combined. */
397 return false;
399 else
401 /* This is the normal case. */
402 rtx temp_extension
403 = gen_rtx_fmt_e (cand->code, cand->mode, orig_src);
404 rtx simplified_temp_extension = simplify_rtx (temp_extension);
405 if (simplified_temp_extension)
406 temp_extension = simplified_temp_extension;
407 new_set = gen_rtx_SET (new_reg, temp_extension);
410 /* This change is a part of a group of changes. Hence,
411 validate_change will not try to commit the change. */
412 if (validate_change (curr_insn, orig_set, new_set, true)
413 && update_reg_equal_equiv_notes (curr_insn, cand->mode, orig_mode,
414 cand->code))
416 if (dump_file)
418 fprintf (dump_file,
419 "Tentatively merged extension with definition %s:\n",
420 (copy_needed) ? "(copy needed)" : "");
421 print_rtl_single (dump_file, curr_insn);
423 return true;
426 return false;
429 /* Treat if_then_else insns, where the operands of both branches
430 are registers, as copies. For instance,
431 Original :
432 (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
433 Transformed :
434 (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
435 DEF_INSN is the if_then_else insn. */
437 static bool
438 transform_ifelse (ext_cand *cand, rtx_insn *def_insn)
440 rtx set_insn = PATTERN (def_insn);
441 rtx srcreg, dstreg, srcreg2;
442 rtx map_srcreg, map_dstreg, map_srcreg2;
443 rtx ifexpr;
444 rtx cond;
445 rtx new_set;
447 gcc_assert (GET_CODE (set_insn) == SET);
449 cond = XEXP (SET_SRC (set_insn), 0);
450 dstreg = SET_DEST (set_insn);
451 srcreg = XEXP (SET_SRC (set_insn), 1);
452 srcreg2 = XEXP (SET_SRC (set_insn), 2);
453 /* If the conditional move already has the right or wider mode,
454 there is nothing to do. */
455 if (GET_MODE_SIZE (GET_MODE (dstreg)) >= GET_MODE_SIZE (cand->mode))
456 return true;
458 map_srcreg = gen_rtx_REG (cand->mode, REGNO (srcreg));
459 map_srcreg2 = gen_rtx_REG (cand->mode, REGNO (srcreg2));
460 map_dstreg = gen_rtx_REG (cand->mode, REGNO (dstreg));
461 ifexpr = gen_rtx_IF_THEN_ELSE (cand->mode, cond, map_srcreg, map_srcreg2);
462 new_set = gen_rtx_SET (map_dstreg, ifexpr);
464 if (validate_change (def_insn, &PATTERN (def_insn), new_set, true)
465 && update_reg_equal_equiv_notes (def_insn, cand->mode, GET_MODE (dstreg),
466 cand->code))
468 if (dump_file)
470 fprintf (dump_file,
471 "Mode of conditional move instruction extended:\n");
472 print_rtl_single (dump_file, def_insn);
474 return true;
477 return false;
480 /* Get all the reaching definitions of an instruction. The definitions are
481 desired for REG used in INSN. Return the definition list or NULL if a
482 definition is missing. If DEST is non-NULL, additionally push the INSN
483 of the definitions onto DEST. */
485 static struct df_link *
486 get_defs (rtx_insn *insn, rtx reg, vec<rtx_insn *> *dest)
488 df_ref use;
489 struct df_link *ref_chain, *ref_link;
491 FOR_EACH_INSN_USE (use, insn)
493 if (GET_CODE (DF_REF_REG (use)) == SUBREG)
494 return NULL;
495 if (REGNO (DF_REF_REG (use)) == REGNO (reg))
496 break;
499 gcc_assert (use != NULL);
501 ref_chain = DF_REF_CHAIN (use);
503 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
505 /* Problem getting some definition for this instruction. */
506 if (ref_link->ref == NULL)
507 return NULL;
508 if (DF_REF_INSN_INFO (ref_link->ref) == NULL)
509 return NULL;
512 if (dest)
513 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
514 dest->safe_push (DF_REF_INSN (ref_link->ref));
516 return ref_chain;
519 /* Return true if INSN is
520 (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
521 and store x1 and x2 in REG_1 and REG_2. */
523 static bool
524 is_cond_copy_insn (rtx_insn *insn, rtx *reg1, rtx *reg2)
526 rtx expr = single_set (insn);
528 if (expr != NULL_RTX
529 && GET_CODE (expr) == SET
530 && GET_CODE (SET_DEST (expr)) == REG
531 && GET_CODE (SET_SRC (expr)) == IF_THEN_ELSE
532 && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG
533 && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG)
535 *reg1 = XEXP (SET_SRC (expr), 1);
536 *reg2 = XEXP (SET_SRC (expr), 2);
537 return true;
540 return false;
543 enum ext_modified_kind
545 /* The insn hasn't been modified by ree pass yet. */
546 EXT_MODIFIED_NONE,
547 /* Changed into zero extension. */
548 EXT_MODIFIED_ZEXT,
549 /* Changed into sign extension. */
550 EXT_MODIFIED_SEXT
553 struct ATTRIBUTE_PACKED ext_modified
555 /* Mode from which ree has zero or sign extended the destination. */
556 ENUM_BITFIELD(machine_mode) mode : 8;
558 /* Kind of modification of the insn. */
559 ENUM_BITFIELD(ext_modified_kind) kind : 2;
561 unsigned int do_not_reextend : 1;
563 /* True if the insn is scheduled to be deleted. */
564 unsigned int deleted : 1;
567 /* Vectors used by combine_reaching_defs and its helpers. */
568 typedef struct ext_state
570 /* In order to avoid constant alloc/free, we keep these
571 4 vectors live through the entire find_and_remove_re and just
572 truncate them each time. */
573 vec<rtx_insn *> defs_list;
574 vec<rtx_insn *> copies_list;
575 vec<rtx_insn *> modified_list;
576 vec<rtx_insn *> work_list;
578 /* For instructions that have been successfully modified, this is
579 the original mode from which the insn is extending and
580 kind of extension. */
581 struct ext_modified *modified;
582 } ext_state;
584 /* Reaching Definitions of the extended register could be conditional copies
585 or regular definitions. This function separates the two types into two
586 lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because,
587 if a reaching definition is a conditional copy, merging the extension with
588 this definition is wrong. Conditional copies are merged by transitively
589 merging their definitions. The defs_list is populated with all the reaching
590 definitions of the extension instruction (EXTEND_INSN) which must be merged
591 with an extension. The copies_list contains all the conditional moves that
592 will later be extended into a wider mode conditional move if all the merges
593 are successful. The function returns false upon failure, true upon
594 success. */
596 static bool
597 make_defs_and_copies_lists (rtx_insn *extend_insn, const_rtx set_pat,
598 ext_state *state)
600 rtx src_reg = XEXP (SET_SRC (set_pat), 0);
601 bool *is_insn_visited;
602 bool ret = true;
604 state->work_list.truncate (0);
606 /* Initialize the work list. */
607 if (!get_defs (extend_insn, src_reg, &state->work_list))
608 gcc_unreachable ();
610 is_insn_visited = XCNEWVEC (bool, max_insn_uid);
612 /* Perform transitive closure for conditional copies. */
613 while (!state->work_list.is_empty ())
615 rtx_insn *def_insn = state->work_list.pop ();
616 rtx reg1, reg2;
618 gcc_assert (INSN_UID (def_insn) < max_insn_uid);
620 if (is_insn_visited[INSN_UID (def_insn)])
621 continue;
622 is_insn_visited[INSN_UID (def_insn)] = true;
624 if (is_cond_copy_insn (def_insn, &reg1, &reg2))
626 /* Push it onto the copy list first. */
627 state->copies_list.safe_push (def_insn);
629 /* Now perform the transitive closure. */
630 if (!get_defs (def_insn, reg1, &state->work_list)
631 || !get_defs (def_insn, reg2, &state->work_list))
633 ret = false;
634 break;
637 else
638 state->defs_list.safe_push (def_insn);
641 XDELETEVEC (is_insn_visited);
643 return ret;
646 /* If DEF_INSN has single SET expression, possibly buried inside
647 a PARALLEL, return the address of the SET expression, else
648 return NULL. This is similar to single_set, except that
649 single_set allows multiple SETs when all but one is dead. */
650 static rtx *
651 get_sub_rtx (rtx_insn *def_insn)
653 enum rtx_code code = GET_CODE (PATTERN (def_insn));
654 rtx *sub_rtx = NULL;
656 if (code == PARALLEL)
658 for (int i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++)
660 rtx s_expr = XVECEXP (PATTERN (def_insn), 0, i);
661 if (GET_CODE (s_expr) != SET)
662 continue;
664 if (sub_rtx == NULL)
665 sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i);
666 else
668 /* PARALLEL with multiple SETs. */
669 return NULL;
673 else if (code == SET)
674 sub_rtx = &PATTERN (def_insn);
675 else
677 /* It is not a PARALLEL or a SET, what could it be ? */
678 return NULL;
681 gcc_assert (sub_rtx != NULL);
682 return sub_rtx;
685 /* Merge the DEF_INSN with an extension. Calls combine_set_extension
686 on the SET pattern. */
688 static bool
689 merge_def_and_ext (ext_cand *cand, rtx_insn *def_insn, ext_state *state)
691 machine_mode ext_src_mode;
692 rtx *sub_rtx;
694 ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0));
695 sub_rtx = get_sub_rtx (def_insn);
697 if (sub_rtx == NULL)
698 return false;
700 if (REG_P (SET_DEST (*sub_rtx))
701 && (GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode
702 || ((state->modified[INSN_UID (def_insn)].kind
703 == (cand->code == ZERO_EXTEND
704 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT))
705 && state->modified[INSN_UID (def_insn)].mode
706 == ext_src_mode)))
708 if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx)))
709 >= GET_MODE_SIZE (cand->mode))
710 return true;
711 /* If def_insn is already scheduled to be deleted, don't attempt
712 to modify it. */
713 if (state->modified[INSN_UID (def_insn)].deleted)
714 return false;
715 if (combine_set_extension (cand, def_insn, sub_rtx))
717 if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE)
718 state->modified[INSN_UID (def_insn)].mode = ext_src_mode;
719 return true;
723 return false;
726 /* Given SRC, which should be one or more extensions of a REG, strip
727 away the extensions and return the REG. */
729 static inline rtx
730 get_extended_src_reg (rtx src)
732 while (GET_CODE (src) == SIGN_EXTEND || GET_CODE (src) == ZERO_EXTEND)
733 src = XEXP (src, 0);
734 gcc_assert (REG_P (src));
735 return src;
738 /* This function goes through all reaching defs of the source
739 of the candidate for elimination (CAND) and tries to combine
740 the extension with the definition instruction. The changes
741 are made as a group so that even if one definition cannot be
742 merged, all reaching definitions end up not being merged.
743 When a conditional copy is encountered, merging is attempted
744 transitively on its definitions. It returns true upon success
745 and false upon failure. */
747 static bool
748 combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state)
750 rtx_insn *def_insn;
751 bool merge_successful = true;
752 int i;
753 int defs_ix;
754 bool outcome;
756 state->defs_list.truncate (0);
757 state->copies_list.truncate (0);
759 outcome = make_defs_and_copies_lists (cand->insn, set_pat, state);
761 if (!outcome)
762 return false;
764 /* If the destination operand of the extension is a different
765 register than the source operand, then additional restrictions
766 are needed. Note we have to handle cases where we have nested
767 extensions in the source operand. */
768 bool copy_needed
769 = (REGNO (SET_DEST (PATTERN (cand->insn)))
770 != REGNO (get_extended_src_reg (SET_SRC (PATTERN (cand->insn)))));
771 if (copy_needed)
773 /* Considering transformation of
774 (set (reg1) (expression))
776 (set (reg2) (any_extend (reg1)))
778 into
780 (set (reg2) (any_extend (expression)))
781 (set (reg1) (reg2))
782 ... */
784 /* In theory we could handle more than one reaching def, it
785 just makes the code to update the insn stream more complex. */
786 if (state->defs_list.length () != 1)
787 return false;
789 /* We require the candidate not already be modified. It may,
790 for example have been changed from a (sign_extend (reg))
791 into (zero_extend (sign_extend (reg))).
793 Handling that case shouldn't be terribly difficult, but the code
794 here and the code to emit copies would need auditing. Until
795 we see a need, this is the safe thing to do. */
796 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE)
797 return false;
799 machine_mode dst_mode = GET_MODE (SET_DEST (PATTERN (cand->insn)));
800 rtx src_reg = get_extended_src_reg (SET_SRC (PATTERN (cand->insn)));
802 /* Ensure the number of hard registers of the copy match. */
803 if (HARD_REGNO_NREGS (REGNO (src_reg), dst_mode)
804 != HARD_REGNO_NREGS (REGNO (src_reg), GET_MODE (src_reg)))
805 return false;
807 /* There's only one reaching def. */
808 rtx_insn *def_insn = state->defs_list[0];
810 /* The defining statement must not have been modified either. */
811 if (state->modified[INSN_UID (def_insn)].kind != EXT_MODIFIED_NONE)
812 return false;
814 /* The defining statement and candidate insn must be in the same block.
815 This is merely to keep the test for safety and updating the insn
816 stream simple. Also ensure that within the block the candidate
817 follows the defining insn. */
818 basic_block bb = BLOCK_FOR_INSN (cand->insn);
819 if (bb != BLOCK_FOR_INSN (def_insn)
820 || DF_INSN_LUID (def_insn) > DF_INSN_LUID (cand->insn))
821 return false;
823 /* If there is an overlap between the destination of DEF_INSN and
824 CAND->insn, then this transformation is not safe. Note we have
825 to test in the widened mode. */
826 rtx *dest_sub_rtx = get_sub_rtx (def_insn);
827 if (dest_sub_rtx == NULL
828 || !REG_P (SET_DEST (*dest_sub_rtx)))
829 return false;
831 rtx tmp_reg = gen_rtx_REG (GET_MODE (SET_DEST (PATTERN (cand->insn))),
832 REGNO (SET_DEST (*dest_sub_rtx)));
833 if (reg_overlap_mentioned_p (tmp_reg, SET_DEST (PATTERN (cand->insn))))
834 return false;
836 /* The destination register of the extension insn must not be
837 used or set between the def_insn and cand->insn exclusive. */
838 if (reg_used_between_p (SET_DEST (PATTERN (cand->insn)),
839 def_insn, cand->insn)
840 || reg_set_between_p (SET_DEST (PATTERN (cand->insn)),
841 def_insn, cand->insn))
842 return false;
844 /* We must be able to copy between the two registers. Generate,
845 recognize and verify constraints of the copy. Also fail if this
846 generated more than one insn.
848 This generates garbage since we throw away the insn when we're
849 done, only to recreate it later if this test was successful.
851 Make sure to get the mode from the extension (cand->insn). This
852 is different than in the code to emit the copy as we have not
853 modified the defining insn yet. */
854 start_sequence ();
855 rtx pat = PATTERN (cand->insn);
856 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (pat)),
857 REGNO (get_extended_src_reg (SET_SRC (pat))));
858 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (pat)),
859 REGNO (SET_DEST (pat)));
860 emit_move_insn (new_dst, new_src);
862 rtx_insn *insn = get_insns();
863 end_sequence ();
864 if (NEXT_INSN (insn))
865 return false;
866 if (recog_memoized (insn) == -1)
867 return false;
868 extract_insn (insn);
869 if (!constrain_operands (1, get_preferred_alternatives (insn, bb)))
870 return false;
874 /* If cand->insn has been already modified, update cand->mode to a wider
875 mode if possible, or punt. */
876 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE)
878 machine_mode mode;
879 rtx set;
881 if (state->modified[INSN_UID (cand->insn)].kind
882 != (cand->code == ZERO_EXTEND
883 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT)
884 || state->modified[INSN_UID (cand->insn)].mode != cand->mode
885 || (set = single_set (cand->insn)) == NULL_RTX)
886 return false;
887 mode = GET_MODE (SET_DEST (set));
888 gcc_assert (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (cand->mode));
889 cand->mode = mode;
892 merge_successful = true;
894 /* Go through the defs vector and try to merge all the definitions
895 in this vector. */
896 state->modified_list.truncate (0);
897 FOR_EACH_VEC_ELT (state->defs_list, defs_ix, def_insn)
899 if (merge_def_and_ext (cand, def_insn, state))
900 state->modified_list.safe_push (def_insn);
901 else
903 merge_successful = false;
904 break;
908 /* Now go through the conditional copies vector and try to merge all
909 the copies in this vector. */
910 if (merge_successful)
912 FOR_EACH_VEC_ELT (state->copies_list, i, def_insn)
914 if (transform_ifelse (cand, def_insn))
915 state->modified_list.safe_push (def_insn);
916 else
918 merge_successful = false;
919 break;
924 if (merge_successful)
926 /* Commit the changes here if possible
927 FIXME: It's an all-or-nothing scenario. Even if only one definition
928 cannot be merged, we entirely give up. In the future, we should allow
929 extensions to be partially eliminated along those paths where the
930 definitions could be merged. */
931 if (apply_change_group ())
933 if (dump_file)
934 fprintf (dump_file, "All merges were successful.\n");
936 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
938 ext_modified *modified = &state->modified[INSN_UID (def_insn)];
939 if (modified->kind == EXT_MODIFIED_NONE)
940 modified->kind = (cand->code == ZERO_EXTEND ? EXT_MODIFIED_ZEXT
941 : EXT_MODIFIED_SEXT);
943 if (copy_needed)
944 modified->do_not_reextend = 1;
946 return true;
948 else
950 /* Changes need not be cancelled explicitly as apply_change_group
951 does it. Print list of definitions in the dump_file for debug
952 purposes. This extension cannot be deleted. */
953 if (dump_file)
955 fprintf (dump_file,
956 "Merge cancelled, non-mergeable definitions:\n");
957 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
958 print_rtl_single (dump_file, def_insn);
962 else
964 /* Cancel any changes that have been made so far. */
965 cancel_changes (0);
968 return false;
971 /* Add an extension pattern that could be eliminated. */
973 static void
974 add_removable_extension (const_rtx expr, rtx_insn *insn,
975 vec<ext_cand> *insn_list,
976 unsigned *def_map)
978 enum rtx_code code;
979 machine_mode mode;
980 unsigned int idx;
981 rtx src, dest;
983 /* We are looking for SET (REG N) (ANY_EXTEND (REG N)). */
984 if (GET_CODE (expr) != SET)
985 return;
987 src = SET_SRC (expr);
988 code = GET_CODE (src);
989 dest = SET_DEST (expr);
990 mode = GET_MODE (dest);
992 if (REG_P (dest)
993 && (code == SIGN_EXTEND || code == ZERO_EXTEND)
994 && REG_P (XEXP (src, 0)))
996 struct df_link *defs, *def;
997 ext_cand *cand;
999 /* First, make sure we can get all the reaching definitions. */
1000 defs = get_defs (insn, XEXP (src, 0), NULL);
1001 if (!defs)
1003 if (dump_file)
1005 fprintf (dump_file, "Cannot eliminate extension:\n");
1006 print_rtl_single (dump_file, insn);
1007 fprintf (dump_file, " because of missing definition(s)\n");
1009 return;
1012 /* Second, make sure the reaching definitions don't feed another and
1013 different extension. FIXME: this obviously can be improved. */
1014 for (def = defs; def; def = def->next)
1015 if ((idx = def_map[INSN_UID (DF_REF_INSN (def->ref))])
1016 && idx != -1U
1017 && (cand = &(*insn_list)[idx - 1])
1018 && cand->code != code)
1020 if (dump_file)
1022 fprintf (dump_file, "Cannot eliminate extension:\n");
1023 print_rtl_single (dump_file, insn);
1024 fprintf (dump_file, " because of other extension\n");
1026 return;
1028 /* For vector mode extensions, ensure that all uses of the
1029 XEXP (src, 0) register are the same extension (both code
1030 and to which mode), as unlike integral extensions lowpart
1031 subreg of the sign/zero extended register are not equal
1032 to the original register, so we have to change all uses or
1033 none. */
1034 else if (VECTOR_MODE_P (GET_MODE (XEXP (src, 0))))
1036 if (idx == 0)
1038 struct df_link *ref_chain, *ref_link;
1040 ref_chain = DF_REF_CHAIN (def->ref);
1041 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
1043 if (ref_link->ref == NULL
1044 || DF_REF_INSN_INFO (ref_link->ref) == NULL)
1046 idx = -1U;
1047 break;
1049 rtx_insn *use_insn = DF_REF_INSN (ref_link->ref);
1050 const_rtx use_set;
1051 if (use_insn == insn || DEBUG_INSN_P (use_insn))
1052 continue;
1053 if (!(use_set = single_set (use_insn))
1054 || !REG_P (SET_DEST (use_set))
1055 || GET_MODE (SET_DEST (use_set)) != GET_MODE (dest)
1056 || GET_CODE (SET_SRC (use_set)) != code
1057 || !rtx_equal_p (XEXP (SET_SRC (use_set), 0),
1058 XEXP (src, 0)))
1060 idx = -1U;
1061 break;
1064 if (idx == -1U)
1065 def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx;
1067 if (idx == -1U)
1069 if (dump_file)
1071 fprintf (dump_file, "Cannot eliminate extension:\n");
1072 print_rtl_single (dump_file, insn);
1073 fprintf (dump_file,
1074 " because some vector uses aren't extension\n");
1076 return;
1080 /* Then add the candidate to the list and insert the reaching definitions
1081 into the definition map. */
1082 ext_cand e = {expr, code, mode, insn};
1083 insn_list->safe_push (e);
1084 idx = insn_list->length ();
1086 for (def = defs; def; def = def->next)
1087 def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx;
1091 /* Traverse the instruction stream looking for extensions and return the
1092 list of candidates. */
1094 static vec<ext_cand>
1095 find_removable_extensions (void)
1097 vec<ext_cand> insn_list = vNULL;
1098 basic_block bb;
1099 rtx_insn *insn;
1100 rtx set;
1101 unsigned *def_map = XCNEWVEC (unsigned, max_insn_uid);
1103 FOR_EACH_BB_FN (bb, cfun)
1104 FOR_BB_INSNS (bb, insn)
1106 if (!NONDEBUG_INSN_P (insn))
1107 continue;
1109 set = single_set (insn);
1110 if (set == NULL_RTX)
1111 continue;
1112 add_removable_extension (set, insn, &insn_list, def_map);
1115 XDELETEVEC (def_map);
1117 return insn_list;
1120 /* This is the main function that checks the insn stream for redundant
1121 extensions and tries to remove them if possible. */
1123 static void
1124 find_and_remove_re (void)
1126 ext_cand *curr_cand;
1127 rtx_insn *curr_insn = NULL;
1128 int num_re_opportunities = 0, num_realized = 0, i;
1129 vec<ext_cand> reinsn_list;
1130 auto_vec<rtx_insn *> reinsn_del_list;
1131 auto_vec<rtx_insn *> reinsn_copy_list;
1132 ext_state state;
1134 /* Construct DU chain to get all reaching definitions of each
1135 extension instruction. */
1136 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
1137 df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
1138 df_analyze ();
1139 df_set_flags (DF_DEFER_INSN_RESCAN);
1141 max_insn_uid = get_max_uid ();
1142 reinsn_list = find_removable_extensions ();
1143 state.defs_list.create (0);
1144 state.copies_list.create (0);
1145 state.modified_list.create (0);
1146 state.work_list.create (0);
1147 if (reinsn_list.is_empty ())
1148 state.modified = NULL;
1149 else
1150 state.modified = XCNEWVEC (struct ext_modified, max_insn_uid);
1152 FOR_EACH_VEC_ELT (reinsn_list, i, curr_cand)
1154 num_re_opportunities++;
1156 /* Try to combine the extension with the definition. */
1157 if (dump_file)
1159 fprintf (dump_file, "Trying to eliminate extension:\n");
1160 print_rtl_single (dump_file, curr_cand->insn);
1163 if (combine_reaching_defs (curr_cand, curr_cand->expr, &state))
1165 if (dump_file)
1166 fprintf (dump_file, "Eliminated the extension.\n");
1167 num_realized++;
1168 /* If the RHS of the current candidate is not (extend (reg)), then
1169 we do not allow the optimization of extensions where
1170 the source and destination registers do not match. Thus
1171 checking REG_P here is correct. */
1172 if (REG_P (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0))
1173 && (REGNO (SET_DEST (PATTERN (curr_cand->insn)))
1174 != REGNO (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0))))
1176 reinsn_copy_list.safe_push (curr_cand->insn);
1177 reinsn_copy_list.safe_push (state.defs_list[0]);
1179 reinsn_del_list.safe_push (curr_cand->insn);
1180 state.modified[INSN_UID (curr_cand->insn)].deleted = 1;
1184 /* The copy list contains pairs of insns which describe copies we
1185 need to insert into the INSN stream.
1187 The first insn in each pair is the extension insn, from which
1188 we derive the source and destination of the copy.
1190 The second insn in each pair is the memory reference where the
1191 extension will ultimately happen. We emit the new copy
1192 immediately after this insn.
1194 It may first appear that the arguments for the copy are reversed.
1195 Remember that the memory reference will be changed to refer to the
1196 destination of the extention. So we're actually emitting a copy
1197 from the new destination to the old destination. */
1198 for (unsigned int i = 0; i < reinsn_copy_list.length (); i += 2)
1200 rtx_insn *curr_insn = reinsn_copy_list[i];
1201 rtx_insn *def_insn = reinsn_copy_list[i + 1];
1203 /* Use the mode of the destination of the defining insn
1204 for the mode of the copy. This is necessary if the
1205 defining insn was used to eliminate a second extension
1206 that was wider than the first. */
1207 rtx sub_rtx = *get_sub_rtx (def_insn);
1208 rtx pat = PATTERN (curr_insn);
1209 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)),
1210 REGNO (XEXP (SET_SRC (pat), 0)));
1211 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)),
1212 REGNO (SET_DEST (pat)));
1213 rtx set = gen_rtx_SET (new_dst, new_src);
1214 emit_insn_after (set, def_insn);
1217 /* Delete all useless extensions here in one sweep. */
1218 FOR_EACH_VEC_ELT (reinsn_del_list, i, curr_insn)
1219 delete_insn (curr_insn);
1221 reinsn_list.release ();
1222 state.defs_list.release ();
1223 state.copies_list.release ();
1224 state.modified_list.release ();
1225 state.work_list.release ();
1226 XDELETEVEC (state.modified);
1228 if (dump_file && num_re_opportunities > 0)
1229 fprintf (dump_file, "Elimination opportunities = %d realized = %d\n",
1230 num_re_opportunities, num_realized);
1233 /* Find and remove redundant extensions. */
1235 static unsigned int
1236 rest_of_handle_ree (void)
1238 timevar_push (TV_REE);
1239 find_and_remove_re ();
1240 timevar_pop (TV_REE);
1241 return 0;
1244 namespace {
1246 const pass_data pass_data_ree =
1248 RTL_PASS, /* type */
1249 "ree", /* name */
1250 OPTGROUP_NONE, /* optinfo_flags */
1251 TV_REE, /* tv_id */
1252 0, /* properties_required */
1253 0, /* properties_provided */
1254 0, /* properties_destroyed */
1255 0, /* todo_flags_start */
1256 TODO_df_finish, /* todo_flags_finish */
1259 class pass_ree : public rtl_opt_pass
1261 public:
1262 pass_ree (gcc::context *ctxt)
1263 : rtl_opt_pass (pass_data_ree, ctxt)
1266 /* opt_pass methods: */
1267 virtual bool gate (function *) { return (optimize > 0 && flag_ree); }
1268 virtual unsigned int execute (function *) { return rest_of_handle_ree (); }
1270 }; // class pass_ree
1272 } // anon namespace
1274 rtl_opt_pass *
1275 make_pass_ree (gcc::context *ctxt)
1277 return new pass_ree (ctxt);