1 /* Redundant Extension Elimination pass for the GNU compiler.
2 Copyright (C) 2010-2014 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"
227 #include "hard-reg-set.h"
228 #include "basic-block.h"
229 #include "insn-config.h"
230 #include "function.h"
232 #include "insn-attr.h"
234 #include "diagnostic-core.h"
237 #include "insn-codes.h"
238 #include "rtlhooks-def.h"
240 #include "tree-pass.h"
244 /* This structure represents a candidate for elimination. */
246 typedef struct ext_cand
248 /* The expression. */
251 /* The kind of extension. */
254 /* The destination mode. */
255 enum machine_mode mode
;
257 /* The instruction where it lives. */
262 static int max_insn_uid
;
264 /* Update or remove REG_EQUAL or REG_EQUIV notes for INSN. */
267 update_reg_equal_equiv_notes (rtx insn
, enum machine_mode new_mode
,
268 enum machine_mode old_mode
, enum rtx_code code
)
270 rtx
*loc
= ®_NOTES (insn
);
273 enum reg_note kind
= REG_NOTE_KIND (*loc
);
274 if (kind
== REG_EQUAL
|| kind
== REG_EQUIV
)
276 rtx orig_src
= XEXP (*loc
, 0);
277 /* Update equivalency constants. Recall that RTL constants are
279 if (GET_CODE (orig_src
) == CONST_INT
280 && HOST_BITS_PER_WIDE_INT
>= GET_MODE_BITSIZE (new_mode
))
282 if (INTVAL (orig_src
) >= 0 || code
== SIGN_EXTEND
)
283 /* Nothing needed. */;
286 /* Zero-extend the negative constant by masking out the
287 bits outside the source mode. */
289 = gen_int_mode (INTVAL (orig_src
)
290 & GET_MODE_MASK (old_mode
),
292 if (!validate_change (insn
, &XEXP (*loc
, 0),
293 new_const_int
, true))
296 loc
= &XEXP (*loc
, 1);
298 /* Drop all other notes, they assume a wrong mode. */
299 else if (!validate_change (insn
, loc
, XEXP (*loc
, 1), true))
303 loc
= &XEXP (*loc
, 1);
308 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND)
309 and a pointer to the SET rtx (ORIG_SET) that needs to be modified,
310 this code modifies the SET rtx to a new SET rtx that extends the
311 right hand expression into a register on the left hand side. Note
312 that multiple assumptions are made about the nature of the set that
313 needs to be true for this to work and is called from merge_def_and_ext.
316 (set (reg a) (expression))
319 (set (reg a) (any_extend (expression)))
322 If the expression is a constant or another extension, then directly
323 assign it to the register. */
326 combine_set_extension (ext_cand
*cand
, rtx curr_insn
, rtx
*orig_set
)
328 rtx orig_src
= SET_SRC (*orig_set
);
329 enum machine_mode orig_mode
= GET_MODE (SET_DEST (*orig_set
));
331 rtx cand_pat
= PATTERN (cand
->insn
);
333 /* If the extension's source/destination registers are not the same
334 then we need to change the original load to reference the destination
335 of the extension. Then we need to emit a copy from that destination
336 to the original destination of the load. */
339 = (REGNO (SET_DEST (cand_pat
)) != REGNO (XEXP (SET_SRC (cand_pat
), 0)));
341 new_reg
= gen_rtx_REG (cand
->mode
, REGNO (SET_DEST (cand_pat
)));
343 new_reg
= gen_rtx_REG (cand
->mode
, REGNO (SET_DEST (*orig_set
)));
346 /* Rethinking test. Temporarily disabled. */
347 /* We're going to be widening the result of DEF_INSN, ensure that doing so
348 doesn't change the number of hard registers needed for the result. */
349 if (HARD_REGNO_NREGS (REGNO (new_reg
), cand
->mode
)
350 != HARD_REGNO_NREGS (REGNO (SET_DEST (*orig_set
)),
351 GET_MODE (SET_DEST (*orig_set
))))
355 /* Merge constants by directly moving the constant into the register under
356 some conditions. Recall that RTL constants are sign-extended. */
357 if (GET_CODE (orig_src
) == CONST_INT
358 && HOST_BITS_PER_WIDE_INT
>= GET_MODE_BITSIZE (cand
->mode
))
360 if (INTVAL (orig_src
) >= 0 || cand
->code
== SIGN_EXTEND
)
361 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, orig_src
);
364 /* Zero-extend the negative constant by masking out the bits outside
367 = gen_int_mode (INTVAL (orig_src
) & GET_MODE_MASK (orig_mode
),
369 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, new_const_int
);
372 else if (GET_MODE (orig_src
) == VOIDmode
)
374 /* This is mostly due to a call insn that should not be optimized. */
377 else if (GET_CODE (orig_src
) == cand
->code
)
379 /* Here is a sequence of two extensions. Try to merge them. */
381 = gen_rtx_fmt_e (cand
->code
, cand
->mode
, XEXP (orig_src
, 0));
382 rtx simplified_temp_extension
= simplify_rtx (temp_extension
);
383 if (simplified_temp_extension
)
384 temp_extension
= simplified_temp_extension
;
385 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, temp_extension
);
387 else if (GET_CODE (orig_src
) == IF_THEN_ELSE
)
389 /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
390 in general, IF_THEN_ELSE should not be combined. */
395 /* This is the normal case. */
397 = gen_rtx_fmt_e (cand
->code
, cand
->mode
, orig_src
);
398 rtx simplified_temp_extension
= simplify_rtx (temp_extension
);
399 if (simplified_temp_extension
)
400 temp_extension
= simplified_temp_extension
;
401 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, temp_extension
);
404 /* This change is a part of a group of changes. Hence,
405 validate_change will not try to commit the change. */
406 if (validate_change (curr_insn
, orig_set
, new_set
, true)
407 && update_reg_equal_equiv_notes (curr_insn
, cand
->mode
, orig_mode
,
413 "Tentatively merged extension with definition %s:\n",
414 (copy_needed
) ? "(copy needed)" : "");
415 print_rtl_single (dump_file
, curr_insn
);
423 /* Treat if_then_else insns, where the operands of both branches
424 are registers, as copies. For instance,
426 (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
428 (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
429 DEF_INSN is the if_then_else insn. */
432 transform_ifelse (ext_cand
*cand
, rtx def_insn
)
434 rtx set_insn
= PATTERN (def_insn
);
435 rtx srcreg
, dstreg
, srcreg2
;
436 rtx map_srcreg
, map_dstreg
, map_srcreg2
;
441 gcc_assert (GET_CODE (set_insn
) == SET
);
443 cond
= XEXP (SET_SRC (set_insn
), 0);
444 dstreg
= SET_DEST (set_insn
);
445 srcreg
= XEXP (SET_SRC (set_insn
), 1);
446 srcreg2
= XEXP (SET_SRC (set_insn
), 2);
447 /* If the conditional move already has the right or wider mode,
448 there is nothing to do. */
449 if (GET_MODE_SIZE (GET_MODE (dstreg
)) >= GET_MODE_SIZE (cand
->mode
))
452 map_srcreg
= gen_rtx_REG (cand
->mode
, REGNO (srcreg
));
453 map_srcreg2
= gen_rtx_REG (cand
->mode
, REGNO (srcreg2
));
454 map_dstreg
= gen_rtx_REG (cand
->mode
, REGNO (dstreg
));
455 ifexpr
= gen_rtx_IF_THEN_ELSE (cand
->mode
, cond
, map_srcreg
, map_srcreg2
);
456 new_set
= gen_rtx_SET (VOIDmode
, map_dstreg
, ifexpr
);
458 if (validate_change (def_insn
, &PATTERN (def_insn
), new_set
, true)
459 && update_reg_equal_equiv_notes (def_insn
, cand
->mode
, GET_MODE (dstreg
),
465 "Mode of conditional move instruction extended:\n");
466 print_rtl_single (dump_file
, def_insn
);
474 /* Get all the reaching definitions of an instruction. The definitions are
475 desired for REG used in INSN. Return the definition list or NULL if a
476 definition is missing. If DEST is non-NULL, additionally push the INSN
477 of the definitions onto DEST. */
479 static struct df_link
*
480 get_defs (rtx insn
, rtx reg
, vec
<rtx
> *dest
)
482 df_ref reg_info
, *uses
;
483 struct df_link
*ref_chain
, *ref_link
;
487 for (uses
= DF_INSN_USES (insn
); *uses
; uses
++)
490 if (GET_CODE (DF_REF_REG (reg_info
)) == SUBREG
)
492 if (REGNO (DF_REF_REG (reg_info
)) == REGNO (reg
))
496 gcc_assert (reg_info
!= NULL
&& uses
!= NULL
);
498 ref_chain
= DF_REF_CHAIN (reg_info
);
500 for (ref_link
= ref_chain
; ref_link
; ref_link
= ref_link
->next
)
502 /* Problem getting some definition for this instruction. */
503 if (ref_link
->ref
== NULL
)
505 if (DF_REF_INSN_INFO (ref_link
->ref
) == NULL
)
510 for (ref_link
= ref_chain
; ref_link
; ref_link
= ref_link
->next
)
511 dest
->safe_push (DF_REF_INSN (ref_link
->ref
));
516 /* Return true if INSN is
517 (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
518 and store x1 and x2 in REG_1 and REG_2. */
521 is_cond_copy_insn (rtx insn
, rtx
*reg1
, rtx
*reg2
)
523 rtx expr
= single_set (insn
);
526 && GET_CODE (expr
) == SET
527 && GET_CODE (SET_DEST (expr
)) == REG
528 && GET_CODE (SET_SRC (expr
)) == IF_THEN_ELSE
529 && GET_CODE (XEXP (SET_SRC (expr
), 1)) == REG
530 && GET_CODE (XEXP (SET_SRC (expr
), 2)) == REG
)
532 *reg1
= XEXP (SET_SRC (expr
), 1);
533 *reg2
= XEXP (SET_SRC (expr
), 2);
540 enum ext_modified_kind
542 /* The insn hasn't been modified by ree pass yet. */
544 /* Changed into zero extension. */
546 /* Changed into sign extension. */
550 struct ATTRIBUTE_PACKED ext_modified
552 /* Mode from which ree has zero or sign extended the destination. */
553 ENUM_BITFIELD(machine_mode
) mode
: 8;
555 /* Kind of modification of the insn. */
556 ENUM_BITFIELD(ext_modified_kind
) kind
: 2;
558 unsigned int do_not_reextend
: 1;
560 /* True if the insn is scheduled to be deleted. */
561 unsigned int deleted
: 1;
564 /* Vectors used by combine_reaching_defs and its helpers. */
565 typedef struct ext_state
567 /* In order to avoid constant alloc/free, we keep these
568 4 vectors live through the entire find_and_remove_re and just
569 truncate them each time. */
571 vec
<rtx
> copies_list
;
572 vec
<rtx
> modified_list
;
575 /* For instructions that have been successfully modified, this is
576 the original mode from which the insn is extending and
577 kind of extension. */
578 struct ext_modified
*modified
;
581 /* Reaching Definitions of the extended register could be conditional copies
582 or regular definitions. This function separates the two types into two
583 lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because,
584 if a reaching definition is a conditional copy, merging the extension with
585 this definition is wrong. Conditional copies are merged by transitively
586 merging their definitions. The defs_list is populated with all the reaching
587 definitions of the extension instruction (EXTEND_INSN) which must be merged
588 with an extension. The copies_list contains all the conditional moves that
589 will later be extended into a wider mode conditional move if all the merges
590 are successful. The function returns false upon failure, true upon
594 make_defs_and_copies_lists (rtx extend_insn
, const_rtx set_pat
,
597 rtx src_reg
= XEXP (SET_SRC (set_pat
), 0);
598 bool *is_insn_visited
;
601 state
->work_list
.truncate (0);
603 /* Initialize the work list. */
604 if (!get_defs (extend_insn
, src_reg
, &state
->work_list
))
607 is_insn_visited
= XCNEWVEC (bool, max_insn_uid
);
609 /* Perform transitive closure for conditional copies. */
610 while (!state
->work_list
.is_empty ())
612 rtx def_insn
= state
->work_list
.pop ();
615 gcc_assert (INSN_UID (def_insn
) < max_insn_uid
);
617 if (is_insn_visited
[INSN_UID (def_insn
)])
619 is_insn_visited
[INSN_UID (def_insn
)] = true;
621 if (is_cond_copy_insn (def_insn
, ®1
, ®2
))
623 /* Push it onto the copy list first. */
624 state
->copies_list
.safe_push (def_insn
);
626 /* Now perform the transitive closure. */
627 if (!get_defs (def_insn
, reg1
, &state
->work_list
)
628 || !get_defs (def_insn
, reg2
, &state
->work_list
))
635 state
->defs_list
.safe_push (def_insn
);
638 XDELETEVEC (is_insn_visited
);
643 /* If DEF_INSN has single SET expression, possibly buried inside
644 a PARALLEL, return the address of the SET expression, else
645 return NULL. This is similar to single_set, except that
646 single_set allows multiple SETs when all but one is dead. */
648 get_sub_rtx (rtx def_insn
)
650 enum rtx_code code
= GET_CODE (PATTERN (def_insn
));
653 if (code
== PARALLEL
)
655 for (int i
= 0; i
< XVECLEN (PATTERN (def_insn
), 0); i
++)
657 rtx s_expr
= XVECEXP (PATTERN (def_insn
), 0, i
);
658 if (GET_CODE (s_expr
) != SET
)
662 sub_rtx
= &XVECEXP (PATTERN (def_insn
), 0, i
);
665 /* PARALLEL with multiple SETs. */
670 else if (code
== SET
)
671 sub_rtx
= &PATTERN (def_insn
);
674 /* It is not a PARALLEL or a SET, what could it be ? */
678 gcc_assert (sub_rtx
!= NULL
);
682 /* Merge the DEF_INSN with an extension. Calls combine_set_extension
683 on the SET pattern. */
686 merge_def_and_ext (ext_cand
*cand
, rtx def_insn
, ext_state
*state
)
688 enum machine_mode ext_src_mode
;
691 ext_src_mode
= GET_MODE (XEXP (SET_SRC (cand
->expr
), 0));
692 sub_rtx
= get_sub_rtx (def_insn
);
697 if (REG_P (SET_DEST (*sub_rtx
))
698 && (GET_MODE (SET_DEST (*sub_rtx
)) == ext_src_mode
699 || ((state
->modified
[INSN_UID (def_insn
)].kind
700 == (cand
->code
== ZERO_EXTEND
701 ? EXT_MODIFIED_ZEXT
: EXT_MODIFIED_SEXT
))
702 && state
->modified
[INSN_UID (def_insn
)].mode
705 if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx
)))
706 >= GET_MODE_SIZE (cand
->mode
))
708 /* If def_insn is already scheduled to be deleted, don't attempt
710 if (state
->modified
[INSN_UID (def_insn
)].deleted
)
712 if (combine_set_extension (cand
, def_insn
, sub_rtx
))
714 if (state
->modified
[INSN_UID (def_insn
)].kind
== EXT_MODIFIED_NONE
)
715 state
->modified
[INSN_UID (def_insn
)].mode
= ext_src_mode
;
723 /* Given SRC, which should be one or more extensions of a REG, strip
724 away the extensions and return the REG. */
727 get_extended_src_reg (rtx src
)
729 while (GET_CODE (src
) == SIGN_EXTEND
|| GET_CODE (src
) == ZERO_EXTEND
)
731 gcc_assert (REG_P (src
));
735 /* This function goes through all reaching defs of the source
736 of the candidate for elimination (CAND) and tries to combine
737 the extension with the definition instruction. The changes
738 are made as a group so that even if one definition cannot be
739 merged, all reaching definitions end up not being merged.
740 When a conditional copy is encountered, merging is attempted
741 transitively on its definitions. It returns true upon success
742 and false upon failure. */
745 combine_reaching_defs (ext_cand
*cand
, const_rtx set_pat
, ext_state
*state
)
748 bool merge_successful
= true;
753 state
->defs_list
.truncate (0);
754 state
->copies_list
.truncate (0);
756 outcome
= make_defs_and_copies_lists (cand
->insn
, set_pat
, state
);
761 /* If the destination operand of the extension is a different
762 register than the source operand, then additional restrictions
763 are needed. Note we have to handle cases where we have nested
764 extensions in the source operand. */
766 = (REGNO (SET_DEST (PATTERN (cand
->insn
)))
767 != REGNO (get_extended_src_reg (SET_SRC (PATTERN (cand
->insn
)))));
770 /* In theory we could handle more than one reaching def, it
771 just makes the code to update the insn stream more complex. */
772 if (state
->defs_list
.length () != 1)
775 /* We require the candidate not already be modified. It may,
776 for example have been changed from a (sign_extend (reg))
777 into (zero_extend (sign_extend (reg))).
779 Handling that case shouldn't be terribly difficult, but the code
780 here and the code to emit copies would need auditing. Until
781 we see a need, this is the safe thing to do. */
782 if (state
->modified
[INSN_UID (cand
->insn
)].kind
!= EXT_MODIFIED_NONE
)
786 (set (reg1) (expression))
787 (set (reg2) (any_extend (reg1)))
789 (set (reg2) (any_extend (expression)))
791 is only valid for scalar integral modes, as it relies on the low
792 subreg of reg1 to have the value of (expression), which is not true
793 e.g. for vector modes. */
794 if (!SCALAR_INT_MODE_P (GET_MODE (SET_DEST (PATTERN (cand
->insn
)))))
797 /* There's only one reaching def. */
798 rtx def_insn
= state
->defs_list
[0];
800 /* The defining statement must not have been modified either. */
801 if (state
->modified
[INSN_UID (def_insn
)].kind
!= EXT_MODIFIED_NONE
)
804 /* The defining statement and candidate insn must be in the same block.
805 This is merely to keep the test for safety and updating the insn
806 stream simple. Also ensure that within the block the candidate
807 follows the defining insn. */
808 if (BLOCK_FOR_INSN (cand
->insn
) != BLOCK_FOR_INSN (def_insn
)
809 || DF_INSN_LUID (def_insn
) > DF_INSN_LUID (cand
->insn
))
812 /* If there is an overlap between the destination of DEF_INSN and
813 CAND->insn, then this transformation is not safe. Note we have
814 to test in the widened mode. */
815 rtx
*dest_sub_rtx
= get_sub_rtx (def_insn
);
816 if (dest_sub_rtx
== NULL
817 || !REG_P (SET_DEST (*dest_sub_rtx
)))
820 rtx tmp_reg
= gen_rtx_REG (GET_MODE (SET_DEST (PATTERN (cand
->insn
))),
821 REGNO (SET_DEST (*dest_sub_rtx
)));
822 if (reg_overlap_mentioned_p (tmp_reg
, SET_DEST (PATTERN (cand
->insn
))))
825 /* The destination register of the extension insn must not be
826 used or set between the def_insn and cand->insn exclusive. */
827 if (reg_used_between_p (SET_DEST (PATTERN (cand
->insn
)),
828 def_insn
, cand
->insn
)
829 || reg_set_between_p (SET_DEST (PATTERN (cand
->insn
)),
830 def_insn
, cand
->insn
))
833 /* We must be able to copy between the two registers. Generate,
834 recognize and verify constraints of the copy. Also fail if this
835 generated more than one insn.
837 This generates garbage since we throw away the insn when we're
838 done, only to recreate it later if this test was successful.
840 Make sure to get the mode from the extension (cand->insn). This
841 is different than in the code to emit the copy as we have not
842 modified the defining insn yet. */
844 rtx pat
= PATTERN (cand
->insn
);
845 rtx new_dst
= gen_rtx_REG (GET_MODE (SET_DEST (pat
)),
846 REGNO (XEXP (SET_SRC (pat
), 0)));
847 rtx new_src
= gen_rtx_REG (GET_MODE (SET_DEST (pat
)),
848 REGNO (SET_DEST (pat
)));
849 emit_move_insn (new_dst
, new_src
);
851 rtx insn
= get_insns();
853 if (NEXT_INSN (insn
))
855 if (recog_memoized (insn
) == -1)
858 if (!constrain_operands (1))
863 /* If cand->insn has been already modified, update cand->mode to a wider
864 mode if possible, or punt. */
865 if (state
->modified
[INSN_UID (cand
->insn
)].kind
!= EXT_MODIFIED_NONE
)
867 enum machine_mode mode
;
870 if (state
->modified
[INSN_UID (cand
->insn
)].kind
871 != (cand
->code
== ZERO_EXTEND
872 ? EXT_MODIFIED_ZEXT
: EXT_MODIFIED_SEXT
)
873 || state
->modified
[INSN_UID (cand
->insn
)].mode
!= cand
->mode
874 || (set
= single_set (cand
->insn
)) == NULL_RTX
)
876 mode
= GET_MODE (SET_DEST (set
));
877 gcc_assert (GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (cand
->mode
));
881 merge_successful
= true;
883 /* Go through the defs vector and try to merge all the definitions
885 state
->modified_list
.truncate (0);
886 FOR_EACH_VEC_ELT (state
->defs_list
, defs_ix
, def_insn
)
888 if (merge_def_and_ext (cand
, def_insn
, state
))
889 state
->modified_list
.safe_push (def_insn
);
892 merge_successful
= false;
897 /* Now go through the conditional copies vector and try to merge all
898 the copies in this vector. */
899 if (merge_successful
)
901 FOR_EACH_VEC_ELT (state
->copies_list
, i
, def_insn
)
903 if (transform_ifelse (cand
, def_insn
))
904 state
->modified_list
.safe_push (def_insn
);
907 merge_successful
= false;
913 if (merge_successful
)
915 /* Commit the changes here if possible
916 FIXME: It's an all-or-nothing scenario. Even if only one definition
917 cannot be merged, we entirely give up. In the future, we should allow
918 extensions to be partially eliminated along those paths where the
919 definitions could be merged. */
920 if (apply_change_group ())
923 fprintf (dump_file
, "All merges were successful.\n");
925 FOR_EACH_VEC_ELT (state
->modified_list
, i
, def_insn
)
927 ext_modified
*modified
= &state
->modified
[INSN_UID (def_insn
)];
928 if (modified
->kind
== EXT_MODIFIED_NONE
)
929 modified
->kind
= (cand
->code
== ZERO_EXTEND
? EXT_MODIFIED_ZEXT
930 : EXT_MODIFIED_SEXT
);
933 modified
->do_not_reextend
= 1;
939 /* Changes need not be cancelled explicitly as apply_change_group
940 does it. Print list of definitions in the dump_file for debug
941 purposes. This extension cannot be deleted. */
945 "Merge cancelled, non-mergeable definitions:\n");
946 FOR_EACH_VEC_ELT (state
->modified_list
, i
, def_insn
)
947 print_rtl_single (dump_file
, def_insn
);
953 /* Cancel any changes that have been made so far. */
960 /* Add an extension pattern that could be eliminated. */
963 add_removable_extension (const_rtx expr
, rtx insn
,
964 vec
<ext_cand
> *insn_list
,
968 enum machine_mode mode
;
972 /* We are looking for SET (REG N) (ANY_EXTEND (REG N)). */
973 if (GET_CODE (expr
) != SET
)
976 src
= SET_SRC (expr
);
977 code
= GET_CODE (src
);
978 dest
= SET_DEST (expr
);
979 mode
= GET_MODE (dest
);
982 && (code
== SIGN_EXTEND
|| code
== ZERO_EXTEND
)
983 && REG_P (XEXP (src
, 0)))
985 struct df_link
*defs
, *def
;
988 /* First, make sure we can get all the reaching definitions. */
989 defs
= get_defs (insn
, XEXP (src
, 0), NULL
);
994 fprintf (dump_file
, "Cannot eliminate extension:\n");
995 print_rtl_single (dump_file
, insn
);
996 fprintf (dump_file
, " because of missing definition(s)\n");
1001 /* Second, make sure the reaching definitions don't feed another and
1002 different extension. FIXME: this obviously can be improved. */
1003 for (def
= defs
; def
; def
= def
->next
)
1004 if ((idx
= def_map
[INSN_UID (DF_REF_INSN (def
->ref
))])
1005 && (cand
= &(*insn_list
)[idx
- 1])
1006 && cand
->code
!= code
)
1010 fprintf (dump_file
, "Cannot eliminate extension:\n");
1011 print_rtl_single (dump_file
, insn
);
1012 fprintf (dump_file
, " because of other extension\n");
1017 /* Then add the candidate to the list and insert the reaching definitions
1018 into the definition map. */
1019 ext_cand e
= {expr
, code
, mode
, insn
};
1020 insn_list
->safe_push (e
);
1021 idx
= insn_list
->length ();
1023 for (def
= defs
; def
; def
= def
->next
)
1024 def_map
[INSN_UID (DF_REF_INSN (def
->ref
))] = idx
;
1028 /* Traverse the instruction stream looking for extensions and return the
1029 list of candidates. */
1031 static vec
<ext_cand
>
1032 find_removable_extensions (void)
1034 vec
<ext_cand
> insn_list
= vNULL
;
1037 unsigned *def_map
= XCNEWVEC (unsigned, max_insn_uid
);
1039 FOR_EACH_BB_FN (bb
, cfun
)
1040 FOR_BB_INSNS (bb
, insn
)
1042 if (!NONDEBUG_INSN_P (insn
))
1045 set
= single_set (insn
);
1046 if (set
== NULL_RTX
)
1048 add_removable_extension (set
, insn
, &insn_list
, def_map
);
1051 XDELETEVEC (def_map
);
1056 /* This is the main function that checks the insn stream for redundant
1057 extensions and tries to remove them if possible. */
1060 find_and_remove_re (void)
1062 ext_cand
*curr_cand
;
1063 rtx curr_insn
= NULL_RTX
;
1064 int num_re_opportunities
= 0, num_realized
= 0, i
;
1065 vec
<ext_cand
> reinsn_list
;
1066 auto_vec
<rtx
> reinsn_del_list
;
1067 auto_vec
<rtx
> reinsn_copy_list
;
1070 /* Construct DU chain to get all reaching definitions of each
1071 extension instruction. */
1072 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
1073 df_chain_add_problem (DF_UD_CHAIN
+ DF_DU_CHAIN
);
1075 df_set_flags (DF_DEFER_INSN_RESCAN
);
1077 max_insn_uid
= get_max_uid ();
1078 reinsn_list
= find_removable_extensions ();
1079 state
.defs_list
.create (0);
1080 state
.copies_list
.create (0);
1081 state
.modified_list
.create (0);
1082 state
.work_list
.create (0);
1083 if (reinsn_list
.is_empty ())
1084 state
.modified
= NULL
;
1086 state
.modified
= XCNEWVEC (struct ext_modified
, max_insn_uid
);
1088 FOR_EACH_VEC_ELT (reinsn_list
, i
, curr_cand
)
1090 num_re_opportunities
++;
1092 /* Try to combine the extension with the definition. */
1095 fprintf (dump_file
, "Trying to eliminate extension:\n");
1096 print_rtl_single (dump_file
, curr_cand
->insn
);
1099 if (combine_reaching_defs (curr_cand
, curr_cand
->expr
, &state
))
1102 fprintf (dump_file
, "Eliminated the extension.\n");
1104 /* If the RHS of the current candidate is not (extend (reg)), then
1105 we do not allow the optimization of extensions where
1106 the source and destination registers do not match. Thus
1107 checking REG_P here is correct. */
1108 if (REG_P (XEXP (SET_SRC (PATTERN (curr_cand
->insn
)), 0))
1109 && (REGNO (SET_DEST (PATTERN (curr_cand
->insn
)))
1110 != REGNO (XEXP (SET_SRC (PATTERN (curr_cand
->insn
)), 0))))
1112 reinsn_copy_list
.safe_push (curr_cand
->insn
);
1113 reinsn_copy_list
.safe_push (state
.defs_list
[0]);
1115 reinsn_del_list
.safe_push (curr_cand
->insn
);
1116 state
.modified
[INSN_UID (curr_cand
->insn
)].deleted
= 1;
1120 /* The copy list contains pairs of insns which describe copies we
1121 need to insert into the INSN stream.
1123 The first insn in each pair is the extension insn, from which
1124 we derive the source and destination of the copy.
1126 The second insn in each pair is the memory reference where the
1127 extension will ultimately happen. We emit the new copy
1128 immediately after this insn.
1130 It may first appear that the arguments for the copy are reversed.
1131 Remember that the memory reference will be changed to refer to the
1132 destination of the extention. So we're actually emitting a copy
1133 from the new destination to the old destination. */
1134 for (unsigned int i
= 0; i
< reinsn_copy_list
.length (); i
+= 2)
1136 rtx curr_insn
= reinsn_copy_list
[i
];
1137 rtx def_insn
= reinsn_copy_list
[i
+ 1];
1139 /* Use the mode of the destination of the defining insn
1140 for the mode of the copy. This is necessary if the
1141 defining insn was used to eliminate a second extension
1142 that was wider than the first. */
1143 rtx sub_rtx
= *get_sub_rtx (def_insn
);
1144 rtx pat
= PATTERN (curr_insn
);
1145 rtx new_dst
= gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx
)),
1146 REGNO (XEXP (SET_SRC (pat
), 0)));
1147 rtx new_src
= gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx
)),
1148 REGNO (SET_DEST (pat
)));
1149 rtx set
= gen_rtx_SET (VOIDmode
, new_dst
, new_src
);
1150 emit_insn_after (set
, def_insn
);
1153 /* Delete all useless extensions here in one sweep. */
1154 FOR_EACH_VEC_ELT (reinsn_del_list
, i
, curr_insn
)
1155 delete_insn (curr_insn
);
1157 reinsn_list
.release ();
1158 state
.defs_list
.release ();
1159 state
.copies_list
.release ();
1160 state
.modified_list
.release ();
1161 state
.work_list
.release ();
1162 XDELETEVEC (state
.modified
);
1164 if (dump_file
&& num_re_opportunities
> 0)
1165 fprintf (dump_file
, "Elimination opportunities = %d realized = %d\n",
1166 num_re_opportunities
, num_realized
);
1169 /* Find and remove redundant extensions. */
1172 rest_of_handle_ree (void)
1174 timevar_push (TV_REE
);
1175 find_and_remove_re ();
1176 timevar_pop (TV_REE
);
1180 /* Run REE pass when flag_ree is set at optimization level > 0. */
1183 gate_handle_ree (void)
1185 return (optimize
> 0 && flag_ree
);
1190 const pass_data pass_data_ree
=
1192 RTL_PASS
, /* type */
1194 OPTGROUP_NONE
, /* optinfo_flags */
1195 true, /* has_gate */
1196 true, /* has_execute */
1198 0, /* properties_required */
1199 0, /* properties_provided */
1200 0, /* properties_destroyed */
1201 0, /* todo_flags_start */
1202 ( TODO_df_finish
| TODO_verify_rtl_sharing
), /* todo_flags_finish */
1205 class pass_ree
: public rtl_opt_pass
1208 pass_ree (gcc::context
*ctxt
)
1209 : rtl_opt_pass (pass_data_ree
, ctxt
)
1212 /* opt_pass methods: */
1213 bool gate () { return gate_handle_ree (); }
1214 unsigned int execute () { return rest_of_handle_ree (); }
1216 }; // class pass_ree
1221 make_pass_ree (gcc::context
*ctxt
)
1223 return new pass_ree (ctxt
);