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
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
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 :
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
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 :
89 **********************************************
102 **********************************************
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
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
118 $ gcc -O2 -free bad_code.c
120 400315: 6b ff 4e imul $0x4e,%edi,%edi
121 400318: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax
123 400320: 6b ff 2d imul $0x2d,%edi,%edi
124 400323: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax
127 Motivating Example II :
128 ---------------------
130 Here is an example with a conditional move.
133 **********************************************
135 unsigned long long foo(unsigned x , unsigned y)
142 return (unsigned long long)(z);
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
155 $ gcc -O2 -free bad_code.c
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
165 Motivating Example III :
166 ---------------------
168 Here is an example with a type cast.
171 **********************************************
173 void test(int size, unsigned char *in, unsigned char *out)
176 unsigned char xr, xg, xy=0;
178 for (i = 0; i < size; i++) {
181 xy = (unsigned char) ((19595*xr + 38470*xg) >> 16);
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
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
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
220 #include "coretypes.h"
223 #include "hash-set.h"
224 #include "machmode.h"
226 #include "double-int.h"
230 #include "wide-int.h"
236 #include "hard-reg-set.h"
238 #include "function.h"
239 #include "dominance.h"
242 #include "basic-block.h"
243 #include "insn-config.h"
245 #include "statistics.h"
247 #include "fixed-value.h"
252 #include "emit-rtl.h"
256 #include "insn-attr.h"
258 #include "diagnostic-core.h"
260 #include "insn-codes.h"
262 #include "rtlhooks-def.h"
264 #include "tree-pass.h"
266 #include "hash-map.h"
268 #include "plugin-api.h"
272 /* This structure represents a candidate for elimination. */
274 typedef struct ext_cand
276 /* The expression. */
279 /* The kind of extension. */
282 /* The destination mode. */
285 /* The instruction where it lives. */
290 static int max_insn_uid
;
292 /* Update or remove REG_EQUAL or REG_EQUIV notes for INSN. */
295 update_reg_equal_equiv_notes (rtx_insn
*insn
, machine_mode new_mode
,
296 machine_mode old_mode
, enum rtx_code code
)
298 rtx
*loc
= ®_NOTES (insn
);
301 enum reg_note kind
= REG_NOTE_KIND (*loc
);
302 if (kind
== REG_EQUAL
|| kind
== REG_EQUIV
)
304 rtx orig_src
= XEXP (*loc
, 0);
305 /* Update equivalency constants. Recall that RTL constants are
307 if (GET_CODE (orig_src
) == CONST_INT
308 && HOST_BITS_PER_WIDE_INT
>= GET_MODE_BITSIZE (new_mode
))
310 if (INTVAL (orig_src
) >= 0 || code
== SIGN_EXTEND
)
311 /* Nothing needed. */;
314 /* Zero-extend the negative constant by masking out the
315 bits outside the source mode. */
317 = gen_int_mode (INTVAL (orig_src
)
318 & GET_MODE_MASK (old_mode
),
320 if (!validate_change (insn
, &XEXP (*loc
, 0),
321 new_const_int
, true))
324 loc
= &XEXP (*loc
, 1);
326 /* Drop all other notes, they assume a wrong mode. */
327 else if (!validate_change (insn
, loc
, XEXP (*loc
, 1), true))
331 loc
= &XEXP (*loc
, 1);
336 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND)
337 and a pointer to the SET rtx (ORIG_SET) that needs to be modified,
338 this code modifies the SET rtx to a new SET rtx that extends the
339 right hand expression into a register on the left hand side. Note
340 that multiple assumptions are made about the nature of the set that
341 needs to be true for this to work and is called from merge_def_and_ext.
344 (set (reg a) (expression))
347 (set (reg a) (any_extend (expression)))
350 If the expression is a constant or another extension, then directly
351 assign it to the register. */
354 combine_set_extension (ext_cand
*cand
, rtx_insn
*curr_insn
, rtx
*orig_set
)
356 rtx orig_src
= SET_SRC (*orig_set
);
357 machine_mode orig_mode
= GET_MODE (SET_DEST (*orig_set
));
359 rtx cand_pat
= PATTERN (cand
->insn
);
361 /* If the extension's source/destination registers are not the same
362 then we need to change the original load to reference the destination
363 of the extension. Then we need to emit a copy from that destination
364 to the original destination of the load. */
367 = (REGNO (SET_DEST (cand_pat
)) != REGNO (XEXP (SET_SRC (cand_pat
), 0)));
369 new_reg
= gen_rtx_REG (cand
->mode
, REGNO (SET_DEST (cand_pat
)));
371 new_reg
= gen_rtx_REG (cand
->mode
, REGNO (SET_DEST (*orig_set
)));
374 /* Rethinking test. Temporarily disabled. */
375 /* We're going to be widening the result of DEF_INSN, ensure that doing so
376 doesn't change the number of hard registers needed for the result. */
377 if (HARD_REGNO_NREGS (REGNO (new_reg
), cand
->mode
)
378 != HARD_REGNO_NREGS (REGNO (SET_DEST (*orig_set
)),
379 GET_MODE (SET_DEST (*orig_set
))))
383 /* Merge constants by directly moving the constant into the register under
384 some conditions. Recall that RTL constants are sign-extended. */
385 if (GET_CODE (orig_src
) == CONST_INT
386 && HOST_BITS_PER_WIDE_INT
>= GET_MODE_BITSIZE (cand
->mode
))
388 if (INTVAL (orig_src
) >= 0 || cand
->code
== SIGN_EXTEND
)
389 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, orig_src
);
392 /* Zero-extend the negative constant by masking out the bits outside
395 = gen_int_mode (INTVAL (orig_src
) & GET_MODE_MASK (orig_mode
),
397 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, new_const_int
);
400 else if (GET_MODE (orig_src
) == VOIDmode
)
402 /* This is mostly due to a call insn that should not be optimized. */
405 else if (GET_CODE (orig_src
) == cand
->code
)
407 /* Here is a sequence of two extensions. Try to merge them. */
409 = gen_rtx_fmt_e (cand
->code
, cand
->mode
, XEXP (orig_src
, 0));
410 rtx simplified_temp_extension
= simplify_rtx (temp_extension
);
411 if (simplified_temp_extension
)
412 temp_extension
= simplified_temp_extension
;
413 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, temp_extension
);
415 else if (GET_CODE (orig_src
) == IF_THEN_ELSE
)
417 /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
418 in general, IF_THEN_ELSE should not be combined. */
423 /* This is the normal case. */
425 = gen_rtx_fmt_e (cand
->code
, cand
->mode
, orig_src
);
426 rtx simplified_temp_extension
= simplify_rtx (temp_extension
);
427 if (simplified_temp_extension
)
428 temp_extension
= simplified_temp_extension
;
429 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, temp_extension
);
432 /* This change is a part of a group of changes. Hence,
433 validate_change will not try to commit the change. */
434 if (validate_change (curr_insn
, orig_set
, new_set
, true)
435 && update_reg_equal_equiv_notes (curr_insn
, cand
->mode
, orig_mode
,
441 "Tentatively merged extension with definition %s:\n",
442 (copy_needed
) ? "(copy needed)" : "");
443 print_rtl_single (dump_file
, curr_insn
);
451 /* Treat if_then_else insns, where the operands of both branches
452 are registers, as copies. For instance,
454 (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
456 (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
457 DEF_INSN is the if_then_else insn. */
460 transform_ifelse (ext_cand
*cand
, rtx_insn
*def_insn
)
462 rtx set_insn
= PATTERN (def_insn
);
463 rtx srcreg
, dstreg
, srcreg2
;
464 rtx map_srcreg
, map_dstreg
, map_srcreg2
;
469 gcc_assert (GET_CODE (set_insn
) == SET
);
471 cond
= XEXP (SET_SRC (set_insn
), 0);
472 dstreg
= SET_DEST (set_insn
);
473 srcreg
= XEXP (SET_SRC (set_insn
), 1);
474 srcreg2
= XEXP (SET_SRC (set_insn
), 2);
475 /* If the conditional move already has the right or wider mode,
476 there is nothing to do. */
477 if (GET_MODE_SIZE (GET_MODE (dstreg
)) >= GET_MODE_SIZE (cand
->mode
))
480 map_srcreg
= gen_rtx_REG (cand
->mode
, REGNO (srcreg
));
481 map_srcreg2
= gen_rtx_REG (cand
->mode
, REGNO (srcreg2
));
482 map_dstreg
= gen_rtx_REG (cand
->mode
, REGNO (dstreg
));
483 ifexpr
= gen_rtx_IF_THEN_ELSE (cand
->mode
, cond
, map_srcreg
, map_srcreg2
);
484 new_set
= gen_rtx_SET (VOIDmode
, map_dstreg
, ifexpr
);
486 if (validate_change (def_insn
, &PATTERN (def_insn
), new_set
, true)
487 && update_reg_equal_equiv_notes (def_insn
, cand
->mode
, GET_MODE (dstreg
),
493 "Mode of conditional move instruction extended:\n");
494 print_rtl_single (dump_file
, def_insn
);
502 /* Get all the reaching definitions of an instruction. The definitions are
503 desired for REG used in INSN. Return the definition list or NULL if a
504 definition is missing. If DEST is non-NULL, additionally push the INSN
505 of the definitions onto DEST. */
507 static struct df_link
*
508 get_defs (rtx_insn
*insn
, rtx reg
, vec
<rtx_insn
*> *dest
)
511 struct df_link
*ref_chain
, *ref_link
;
513 FOR_EACH_INSN_USE (use
, insn
)
515 if (GET_CODE (DF_REF_REG (use
)) == SUBREG
)
517 if (REGNO (DF_REF_REG (use
)) == REGNO (reg
))
521 gcc_assert (use
!= NULL
);
523 ref_chain
= DF_REF_CHAIN (use
);
525 for (ref_link
= ref_chain
; ref_link
; ref_link
= ref_link
->next
)
527 /* Problem getting some definition for this instruction. */
528 if (ref_link
->ref
== NULL
)
530 if (DF_REF_INSN_INFO (ref_link
->ref
) == NULL
)
535 for (ref_link
= ref_chain
; ref_link
; ref_link
= ref_link
->next
)
536 dest
->safe_push (DF_REF_INSN (ref_link
->ref
));
541 /* Return true if INSN is
542 (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
543 and store x1 and x2 in REG_1 and REG_2. */
546 is_cond_copy_insn (rtx_insn
*insn
, rtx
*reg1
, rtx
*reg2
)
548 rtx expr
= single_set (insn
);
551 && GET_CODE (expr
) == SET
552 && GET_CODE (SET_DEST (expr
)) == REG
553 && GET_CODE (SET_SRC (expr
)) == IF_THEN_ELSE
554 && GET_CODE (XEXP (SET_SRC (expr
), 1)) == REG
555 && GET_CODE (XEXP (SET_SRC (expr
), 2)) == REG
)
557 *reg1
= XEXP (SET_SRC (expr
), 1);
558 *reg2
= XEXP (SET_SRC (expr
), 2);
565 enum ext_modified_kind
567 /* The insn hasn't been modified by ree pass yet. */
569 /* Changed into zero extension. */
571 /* Changed into sign extension. */
575 struct ATTRIBUTE_PACKED ext_modified
577 /* Mode from which ree has zero or sign extended the destination. */
578 ENUM_BITFIELD(machine_mode
) mode
: 8;
580 /* Kind of modification of the insn. */
581 ENUM_BITFIELD(ext_modified_kind
) kind
: 2;
583 unsigned int do_not_reextend
: 1;
585 /* True if the insn is scheduled to be deleted. */
586 unsigned int deleted
: 1;
589 /* Vectors used by combine_reaching_defs and its helpers. */
590 typedef struct ext_state
592 /* In order to avoid constant alloc/free, we keep these
593 4 vectors live through the entire find_and_remove_re and just
594 truncate them each time. */
595 vec
<rtx_insn
*> defs_list
;
596 vec
<rtx_insn
*> copies_list
;
597 vec
<rtx_insn
*> modified_list
;
598 vec
<rtx_insn
*> work_list
;
600 /* For instructions that have been successfully modified, this is
601 the original mode from which the insn is extending and
602 kind of extension. */
603 struct ext_modified
*modified
;
606 /* Reaching Definitions of the extended register could be conditional copies
607 or regular definitions. This function separates the two types into two
608 lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because,
609 if a reaching definition is a conditional copy, merging the extension with
610 this definition is wrong. Conditional copies are merged by transitively
611 merging their definitions. The defs_list is populated with all the reaching
612 definitions of the extension instruction (EXTEND_INSN) which must be merged
613 with an extension. The copies_list contains all the conditional moves that
614 will later be extended into a wider mode conditional move if all the merges
615 are successful. The function returns false upon failure, true upon
619 make_defs_and_copies_lists (rtx_insn
*extend_insn
, const_rtx set_pat
,
622 rtx src_reg
= XEXP (SET_SRC (set_pat
), 0);
623 bool *is_insn_visited
;
626 state
->work_list
.truncate (0);
628 /* Initialize the work list. */
629 if (!get_defs (extend_insn
, src_reg
, &state
->work_list
))
632 is_insn_visited
= XCNEWVEC (bool, max_insn_uid
);
634 /* Perform transitive closure for conditional copies. */
635 while (!state
->work_list
.is_empty ())
637 rtx_insn
*def_insn
= state
->work_list
.pop ();
640 gcc_assert (INSN_UID (def_insn
) < max_insn_uid
);
642 if (is_insn_visited
[INSN_UID (def_insn
)])
644 is_insn_visited
[INSN_UID (def_insn
)] = true;
646 if (is_cond_copy_insn (def_insn
, ®1
, ®2
))
648 /* Push it onto the copy list first. */
649 state
->copies_list
.safe_push (def_insn
);
651 /* Now perform the transitive closure. */
652 if (!get_defs (def_insn
, reg1
, &state
->work_list
)
653 || !get_defs (def_insn
, reg2
, &state
->work_list
))
660 state
->defs_list
.safe_push (def_insn
);
663 XDELETEVEC (is_insn_visited
);
668 /* If DEF_INSN has single SET expression, possibly buried inside
669 a PARALLEL, return the address of the SET expression, else
670 return NULL. This is similar to single_set, except that
671 single_set allows multiple SETs when all but one is dead. */
673 get_sub_rtx (rtx_insn
*def_insn
)
675 enum rtx_code code
= GET_CODE (PATTERN (def_insn
));
678 if (code
== PARALLEL
)
680 for (int i
= 0; i
< XVECLEN (PATTERN (def_insn
), 0); i
++)
682 rtx s_expr
= XVECEXP (PATTERN (def_insn
), 0, i
);
683 if (GET_CODE (s_expr
) != SET
)
687 sub_rtx
= &XVECEXP (PATTERN (def_insn
), 0, i
);
690 /* PARALLEL with multiple SETs. */
695 else if (code
== SET
)
696 sub_rtx
= &PATTERN (def_insn
);
699 /* It is not a PARALLEL or a SET, what could it be ? */
703 gcc_assert (sub_rtx
!= NULL
);
707 /* Merge the DEF_INSN with an extension. Calls combine_set_extension
708 on the SET pattern. */
711 merge_def_and_ext (ext_cand
*cand
, rtx_insn
*def_insn
, ext_state
*state
)
713 machine_mode ext_src_mode
;
716 ext_src_mode
= GET_MODE (XEXP (SET_SRC (cand
->expr
), 0));
717 sub_rtx
= get_sub_rtx (def_insn
);
722 if (REG_P (SET_DEST (*sub_rtx
))
723 && (GET_MODE (SET_DEST (*sub_rtx
)) == ext_src_mode
724 || ((state
->modified
[INSN_UID (def_insn
)].kind
725 == (cand
->code
== ZERO_EXTEND
726 ? EXT_MODIFIED_ZEXT
: EXT_MODIFIED_SEXT
))
727 && state
->modified
[INSN_UID (def_insn
)].mode
730 if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx
)))
731 >= GET_MODE_SIZE (cand
->mode
))
733 /* If def_insn is already scheduled to be deleted, don't attempt
735 if (state
->modified
[INSN_UID (def_insn
)].deleted
)
737 if (combine_set_extension (cand
, def_insn
, sub_rtx
))
739 if (state
->modified
[INSN_UID (def_insn
)].kind
== EXT_MODIFIED_NONE
)
740 state
->modified
[INSN_UID (def_insn
)].mode
= ext_src_mode
;
748 /* Given SRC, which should be one or more extensions of a REG, strip
749 away the extensions and return the REG. */
752 get_extended_src_reg (rtx src
)
754 while (GET_CODE (src
) == SIGN_EXTEND
|| GET_CODE (src
) == ZERO_EXTEND
)
756 gcc_assert (REG_P (src
));
760 /* This function goes through all reaching defs of the source
761 of the candidate for elimination (CAND) and tries to combine
762 the extension with the definition instruction. The changes
763 are made as a group so that even if one definition cannot be
764 merged, all reaching definitions end up not being merged.
765 When a conditional copy is encountered, merging is attempted
766 transitively on its definitions. It returns true upon success
767 and false upon failure. */
770 combine_reaching_defs (ext_cand
*cand
, const_rtx set_pat
, ext_state
*state
)
773 bool merge_successful
= true;
778 state
->defs_list
.truncate (0);
779 state
->copies_list
.truncate (0);
781 outcome
= make_defs_and_copies_lists (cand
->insn
, set_pat
, state
);
786 /* If the destination operand of the extension is a different
787 register than the source operand, then additional restrictions
788 are needed. Note we have to handle cases where we have nested
789 extensions in the source operand. */
791 = (REGNO (SET_DEST (PATTERN (cand
->insn
)))
792 != REGNO (get_extended_src_reg (SET_SRC (PATTERN (cand
->insn
)))));
795 /* Considering transformation of
796 (set (reg1) (expression))
798 (set (reg2) (any_extend (reg1)))
802 (set (reg2) (any_extend (expression)))
806 /* In theory we could handle more than one reaching def, it
807 just makes the code to update the insn stream more complex. */
808 if (state
->defs_list
.length () != 1)
811 /* We don't have the structure described above if there are
812 conditional moves in between the def and the candidate,
813 and we will not handle them correctly. See PR68194. */
814 if (state
->copies_list
.length () > 0)
817 /* We require the candidate not already be modified. It may,
818 for example have been changed from a (sign_extend (reg))
819 into (zero_extend (sign_extend (reg))).
821 Handling that case shouldn't be terribly difficult, but the code
822 here and the code to emit copies would need auditing. Until
823 we see a need, this is the safe thing to do. */
824 if (state
->modified
[INSN_UID (cand
->insn
)].kind
!= EXT_MODIFIED_NONE
)
827 machine_mode dst_mode
= GET_MODE (SET_DEST (PATTERN (cand
->insn
)));
828 rtx src_reg
= get_extended_src_reg (SET_SRC (PATTERN (cand
->insn
)));
830 /* Ensure the number of hard registers of the copy match. */
831 if (HARD_REGNO_NREGS (REGNO (src_reg
), dst_mode
)
832 != HARD_REGNO_NREGS (REGNO (src_reg
), GET_MODE (src_reg
)))
835 /* There's only one reaching def. */
836 rtx_insn
*def_insn
= state
->defs_list
[0];
838 /* The defining statement must not have been modified either. */
839 if (state
->modified
[INSN_UID (def_insn
)].kind
!= EXT_MODIFIED_NONE
)
842 /* The defining statement and candidate insn must be in the same block.
843 This is merely to keep the test for safety and updating the insn
844 stream simple. Also ensure that within the block the candidate
845 follows the defining insn. */
846 basic_block bb
= BLOCK_FOR_INSN (cand
->insn
);
847 if (bb
!= BLOCK_FOR_INSN (def_insn
)
848 || DF_INSN_LUID (def_insn
) > DF_INSN_LUID (cand
->insn
))
851 /* If there is an overlap between the destination of DEF_INSN and
852 CAND->insn, then this transformation is not safe. Note we have
853 to test in the widened mode. */
854 rtx
*dest_sub_rtx
= get_sub_rtx (def_insn
);
855 if (dest_sub_rtx
== NULL
856 || !REG_P (SET_DEST (*dest_sub_rtx
)))
859 rtx tmp_reg
= gen_rtx_REG (GET_MODE (SET_DEST (PATTERN (cand
->insn
))),
860 REGNO (SET_DEST (*dest_sub_rtx
)));
861 if (reg_overlap_mentioned_p (tmp_reg
, SET_DEST (PATTERN (cand
->insn
))))
864 /* The destination register of the extension insn must not be
865 used or set between the def_insn and cand->insn exclusive. */
866 if (reg_used_between_p (SET_DEST (PATTERN (cand
->insn
)),
867 def_insn
, cand
->insn
)
868 || reg_set_between_p (SET_DEST (PATTERN (cand
->insn
)),
869 def_insn
, cand
->insn
))
872 /* We must be able to copy between the two registers. Generate,
873 recognize and verify constraints of the copy. Also fail if this
874 generated more than one insn.
876 This generates garbage since we throw away the insn when we're
877 done, only to recreate it later if this test was successful.
879 Make sure to get the mode from the extension (cand->insn). This
880 is different than in the code to emit the copy as we have not
881 modified the defining insn yet. */
883 rtx pat
= PATTERN (cand
->insn
);
884 rtx new_dst
= gen_rtx_REG (GET_MODE (SET_DEST (pat
)),
885 REGNO (get_extended_src_reg (SET_SRC (pat
))));
886 rtx new_src
= gen_rtx_REG (GET_MODE (SET_DEST (pat
)),
887 REGNO (SET_DEST (pat
)));
888 emit_move_insn (new_dst
, new_src
);
890 rtx_insn
*insn
= get_insns();
892 if (NEXT_INSN (insn
))
894 if (recog_memoized (insn
) == -1)
897 if (!constrain_operands (1, get_preferred_alternatives (insn
, bb
)))
902 /* If cand->insn has been already modified, update cand->mode to a wider
903 mode if possible, or punt. */
904 if (state
->modified
[INSN_UID (cand
->insn
)].kind
!= EXT_MODIFIED_NONE
)
909 if (state
->modified
[INSN_UID (cand
->insn
)].kind
910 != (cand
->code
== ZERO_EXTEND
911 ? EXT_MODIFIED_ZEXT
: EXT_MODIFIED_SEXT
)
912 || state
->modified
[INSN_UID (cand
->insn
)].mode
!= cand
->mode
913 || (set
= single_set (cand
->insn
)) == NULL_RTX
)
915 mode
= GET_MODE (SET_DEST (set
));
916 gcc_assert (GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (cand
->mode
));
920 merge_successful
= true;
922 /* Go through the defs vector and try to merge all the definitions
924 state
->modified_list
.truncate (0);
925 FOR_EACH_VEC_ELT (state
->defs_list
, defs_ix
, def_insn
)
927 if (merge_def_and_ext (cand
, def_insn
, state
))
928 state
->modified_list
.safe_push (def_insn
);
931 merge_successful
= false;
936 /* Now go through the conditional copies vector and try to merge all
937 the copies in this vector. */
938 if (merge_successful
)
940 FOR_EACH_VEC_ELT (state
->copies_list
, i
, def_insn
)
942 if (transform_ifelse (cand
, def_insn
))
943 state
->modified_list
.safe_push (def_insn
);
946 merge_successful
= false;
952 if (merge_successful
)
954 /* Commit the changes here if possible
955 FIXME: It's an all-or-nothing scenario. Even if only one definition
956 cannot be merged, we entirely give up. In the future, we should allow
957 extensions to be partially eliminated along those paths where the
958 definitions could be merged. */
959 if (apply_change_group ())
962 fprintf (dump_file
, "All merges were successful.\n");
964 FOR_EACH_VEC_ELT (state
->modified_list
, i
, def_insn
)
966 ext_modified
*modified
= &state
->modified
[INSN_UID (def_insn
)];
967 if (modified
->kind
== EXT_MODIFIED_NONE
)
968 modified
->kind
= (cand
->code
== ZERO_EXTEND
? EXT_MODIFIED_ZEXT
969 : EXT_MODIFIED_SEXT
);
972 modified
->do_not_reextend
= 1;
978 /* Changes need not be cancelled explicitly as apply_change_group
979 does it. Print list of definitions in the dump_file for debug
980 purposes. This extension cannot be deleted. */
984 "Merge cancelled, non-mergeable definitions:\n");
985 FOR_EACH_VEC_ELT (state
->modified_list
, i
, def_insn
)
986 print_rtl_single (dump_file
, def_insn
);
992 /* Cancel any changes that have been made so far. */
999 /* Add an extension pattern that could be eliminated. */
1002 add_removable_extension (const_rtx expr
, rtx_insn
*insn
,
1003 vec
<ext_cand
> *insn_list
,
1011 /* We are looking for SET (REG N) (ANY_EXTEND (REG N)). */
1012 if (GET_CODE (expr
) != SET
)
1015 src
= SET_SRC (expr
);
1016 code
= GET_CODE (src
);
1017 dest
= SET_DEST (expr
);
1018 mode
= GET_MODE (dest
);
1021 && (code
== SIGN_EXTEND
|| code
== ZERO_EXTEND
)
1022 && REG_P (XEXP (src
, 0)))
1024 struct df_link
*defs
, *def
;
1027 /* First, make sure we can get all the reaching definitions. */
1028 defs
= get_defs (insn
, XEXP (src
, 0), NULL
);
1033 fprintf (dump_file
, "Cannot eliminate extension:\n");
1034 print_rtl_single (dump_file
, insn
);
1035 fprintf (dump_file
, " because of missing definition(s)\n");
1040 /* Second, make sure the reaching definitions don't feed another and
1041 different extension. FIXME: this obviously can be improved. */
1042 for (def
= defs
; def
; def
= def
->next
)
1043 if ((idx
= def_map
[INSN_UID (DF_REF_INSN (def
->ref
))])
1045 && (cand
= &(*insn_list
)[idx
- 1])
1046 && cand
->code
!= code
)
1050 fprintf (dump_file
, "Cannot eliminate extension:\n");
1051 print_rtl_single (dump_file
, insn
);
1052 fprintf (dump_file
, " because of other extension\n");
1056 /* For vector mode extensions, ensure that all uses of the
1057 XEXP (src, 0) register are the same extension (both code
1058 and to which mode), as unlike integral extensions lowpart
1059 subreg of the sign/zero extended register are not equal
1060 to the original register, so we have to change all uses or
1062 else if (VECTOR_MODE_P (GET_MODE (XEXP (src
, 0))))
1066 struct df_link
*ref_chain
, *ref_link
;
1068 ref_chain
= DF_REF_CHAIN (def
->ref
);
1069 for (ref_link
= ref_chain
; ref_link
; ref_link
= ref_link
->next
)
1071 if (ref_link
->ref
== NULL
1072 || DF_REF_INSN_INFO (ref_link
->ref
) == NULL
)
1077 rtx_insn
*use_insn
= DF_REF_INSN (ref_link
->ref
);
1079 if (use_insn
== insn
|| DEBUG_INSN_P (use_insn
))
1081 if (!(use_set
= single_set (use_insn
))
1082 || !REG_P (SET_DEST (use_set
))
1083 || GET_MODE (SET_DEST (use_set
)) != GET_MODE (dest
)
1084 || GET_CODE (SET_SRC (use_set
)) != code
1085 || !rtx_equal_p (XEXP (SET_SRC (use_set
), 0),
1093 def_map
[INSN_UID (DF_REF_INSN (def
->ref
))] = idx
;
1099 fprintf (dump_file
, "Cannot eliminate extension:\n");
1100 print_rtl_single (dump_file
, insn
);
1102 " because some vector uses aren't extension\n");
1108 /* Then add the candidate to the list and insert the reaching definitions
1109 into the definition map. */
1110 ext_cand e
= {expr
, code
, mode
, insn
};
1111 insn_list
->safe_push (e
);
1112 idx
= insn_list
->length ();
1114 for (def
= defs
; def
; def
= def
->next
)
1115 def_map
[INSN_UID (DF_REF_INSN (def
->ref
))] = idx
;
1119 /* Traverse the instruction stream looking for extensions and return the
1120 list of candidates. */
1122 static vec
<ext_cand
>
1123 find_removable_extensions (void)
1125 vec
<ext_cand
> insn_list
= vNULL
;
1129 unsigned *def_map
= XCNEWVEC (unsigned, max_insn_uid
);
1131 FOR_EACH_BB_FN (bb
, cfun
)
1132 FOR_BB_INSNS (bb
, insn
)
1134 if (!NONDEBUG_INSN_P (insn
))
1137 set
= single_set (insn
);
1138 if (set
== NULL_RTX
)
1140 add_removable_extension (set
, insn
, &insn_list
, def_map
);
1143 XDELETEVEC (def_map
);
1148 /* This is the main function that checks the insn stream for redundant
1149 extensions and tries to remove them if possible. */
1152 find_and_remove_re (void)
1154 ext_cand
*curr_cand
;
1155 rtx_insn
*curr_insn
= NULL
;
1156 int num_re_opportunities
= 0, num_realized
= 0, i
;
1157 vec
<ext_cand
> reinsn_list
;
1158 auto_vec
<rtx_insn
*> reinsn_del_list
;
1159 auto_vec
<rtx_insn
*> reinsn_copy_list
;
1162 /* Construct DU chain to get all reaching definitions of each
1163 extension instruction. */
1164 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
1165 df_chain_add_problem (DF_UD_CHAIN
+ DF_DU_CHAIN
);
1167 df_set_flags (DF_DEFER_INSN_RESCAN
);
1169 max_insn_uid
= get_max_uid ();
1170 reinsn_list
= find_removable_extensions ();
1171 state
.defs_list
.create (0);
1172 state
.copies_list
.create (0);
1173 state
.modified_list
.create (0);
1174 state
.work_list
.create (0);
1175 if (reinsn_list
.is_empty ())
1176 state
.modified
= NULL
;
1178 state
.modified
= XCNEWVEC (struct ext_modified
, max_insn_uid
);
1180 FOR_EACH_VEC_ELT (reinsn_list
, i
, curr_cand
)
1182 num_re_opportunities
++;
1184 /* Try to combine the extension with the definition. */
1187 fprintf (dump_file
, "Trying to eliminate extension:\n");
1188 print_rtl_single (dump_file
, curr_cand
->insn
);
1191 if (combine_reaching_defs (curr_cand
, curr_cand
->expr
, &state
))
1194 fprintf (dump_file
, "Eliminated the extension.\n");
1196 /* If the RHS of the current candidate is not (extend (reg)), then
1197 we do not allow the optimization of extensions where
1198 the source and destination registers do not match. Thus
1199 checking REG_P here is correct. */
1200 if (REG_P (XEXP (SET_SRC (PATTERN (curr_cand
->insn
)), 0))
1201 && (REGNO (SET_DEST (PATTERN (curr_cand
->insn
)))
1202 != REGNO (XEXP (SET_SRC (PATTERN (curr_cand
->insn
)), 0))))
1204 reinsn_copy_list
.safe_push (curr_cand
->insn
);
1205 reinsn_copy_list
.safe_push (state
.defs_list
[0]);
1207 reinsn_del_list
.safe_push (curr_cand
->insn
);
1208 state
.modified
[INSN_UID (curr_cand
->insn
)].deleted
= 1;
1212 /* The copy list contains pairs of insns which describe copies we
1213 need to insert into the INSN stream.
1215 The first insn in each pair is the extension insn, from which
1216 we derive the source and destination of the copy.
1218 The second insn in each pair is the memory reference where the
1219 extension will ultimately happen. We emit the new copy
1220 immediately after this insn.
1222 It may first appear that the arguments for the copy are reversed.
1223 Remember that the memory reference will be changed to refer to the
1224 destination of the extention. So we're actually emitting a copy
1225 from the new destination to the old destination. */
1226 for (unsigned int i
= 0; i
< reinsn_copy_list
.length (); i
+= 2)
1228 rtx_insn
*curr_insn
= reinsn_copy_list
[i
];
1229 rtx_insn
*def_insn
= reinsn_copy_list
[i
+ 1];
1231 /* Use the mode of the destination of the defining insn
1232 for the mode of the copy. This is necessary if the
1233 defining insn was used to eliminate a second extension
1234 that was wider than the first. */
1235 rtx sub_rtx
= *get_sub_rtx (def_insn
);
1236 rtx pat
= PATTERN (curr_insn
);
1237 rtx new_dst
= gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx
)),
1238 REGNO (XEXP (SET_SRC (pat
), 0)));
1239 rtx new_src
= gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx
)),
1240 REGNO (SET_DEST (pat
)));
1241 rtx set
= gen_rtx_SET (VOIDmode
, new_dst
, new_src
);
1242 emit_insn_after (set
, def_insn
);
1245 /* Delete all useless extensions here in one sweep. */
1246 FOR_EACH_VEC_ELT (reinsn_del_list
, i
, curr_insn
)
1247 delete_insn (curr_insn
);
1249 reinsn_list
.release ();
1250 state
.defs_list
.release ();
1251 state
.copies_list
.release ();
1252 state
.modified_list
.release ();
1253 state
.work_list
.release ();
1254 XDELETEVEC (state
.modified
);
1256 if (dump_file
&& num_re_opportunities
> 0)
1257 fprintf (dump_file
, "Elimination opportunities = %d realized = %d\n",
1258 num_re_opportunities
, num_realized
);
1261 /* Find and remove redundant extensions. */
1264 rest_of_handle_ree (void)
1266 timevar_push (TV_REE
);
1267 find_and_remove_re ();
1268 timevar_pop (TV_REE
);
1274 const pass_data pass_data_ree
=
1276 RTL_PASS
, /* type */
1278 OPTGROUP_NONE
, /* optinfo_flags */
1280 0, /* properties_required */
1281 0, /* properties_provided */
1282 0, /* properties_destroyed */
1283 0, /* todo_flags_start */
1284 TODO_df_finish
, /* todo_flags_finish */
1287 class pass_ree
: public rtl_opt_pass
1290 pass_ree (gcc::context
*ctxt
)
1291 : rtl_opt_pass (pass_data_ree
, ctxt
)
1294 /* opt_pass methods: */
1295 virtual bool gate (function
*) { return (optimize
> 0 && flag_ree
); }
1296 virtual unsigned int execute (function
*) { return rest_of_handle_ree (); }
1298 }; // class pass_ree
1303 make_pass_ree (gcc::context
*ctxt
)
1305 return new pass_ree (ctxt
);