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 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND)
265 and a pointer to the SET rtx (ORIG_SET) that needs to be modified,
266 this code modifies the SET rtx to a new SET rtx that extends the
267 right hand expression into a register on the left hand side. Note
268 that multiple assumptions are made about the nature of the set that
269 needs to be true for this to work and is called from merge_def_and_ext.
272 (set (reg a) (expression))
275 (set (reg a) (any_extend (expression)))
278 If the expression is a constant or another extension, then directly
279 assign it to the register. */
282 combine_set_extension (ext_cand
*cand
, rtx curr_insn
, rtx
*orig_set
)
284 rtx orig_src
= SET_SRC (*orig_set
);
286 rtx cand_pat
= PATTERN (cand
->insn
);
288 /* If the extension's source/destination registers are not the same
289 then we need to change the original load to reference the destination
290 of the extension. Then we need to emit a copy from that destination
291 to the original destination of the load. */
294 = (REGNO (SET_DEST (cand_pat
)) != REGNO (XEXP (SET_SRC (cand_pat
), 0)));
296 new_reg
= gen_rtx_REG (cand
->mode
, REGNO (SET_DEST (cand_pat
)));
298 new_reg
= gen_rtx_REG (cand
->mode
, REGNO (SET_DEST (*orig_set
)));
300 /* Merge constants by directly moving the constant into the register under
301 some conditions. Recall that RTL constants are sign-extended. */
302 if (GET_CODE (orig_src
) == CONST_INT
303 && HOST_BITS_PER_WIDE_INT
>= GET_MODE_BITSIZE (cand
->mode
))
305 if (INTVAL (orig_src
) >= 0 || cand
->code
== SIGN_EXTEND
)
306 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, orig_src
);
309 /* Zero-extend the negative constant by masking out the bits outside
311 enum machine_mode src_mode
= GET_MODE (SET_DEST (*orig_set
));
313 = gen_int_mode (INTVAL (orig_src
) & GET_MODE_MASK (src_mode
),
315 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, new_const_int
);
318 else if (GET_MODE (orig_src
) == VOIDmode
)
320 /* This is mostly due to a call insn that should not be optimized. */
323 else if (GET_CODE (orig_src
) == cand
->code
)
325 /* Here is a sequence of two extensions. Try to merge them. */
327 = gen_rtx_fmt_e (cand
->code
, cand
->mode
, XEXP (orig_src
, 0));
328 rtx simplified_temp_extension
= simplify_rtx (temp_extension
);
329 if (simplified_temp_extension
)
330 temp_extension
= simplified_temp_extension
;
331 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, temp_extension
);
333 else if (GET_CODE (orig_src
) == IF_THEN_ELSE
)
335 /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
336 in general, IF_THEN_ELSE should not be combined. */
341 /* This is the normal case. */
343 = gen_rtx_fmt_e (cand
->code
, cand
->mode
, orig_src
);
344 rtx simplified_temp_extension
= simplify_rtx (temp_extension
);
345 if (simplified_temp_extension
)
346 temp_extension
= simplified_temp_extension
;
347 new_set
= gen_rtx_SET (VOIDmode
, new_reg
, temp_extension
);
350 /* This change is a part of a group of changes. Hence,
351 validate_change will not try to commit the change. */
352 if (validate_change (curr_insn
, orig_set
, new_set
, true))
357 "Tentatively merged extension with definition %s:\n",
358 (copy_needed
) ? "(copy needed)" : "");
359 print_rtl_single (dump_file
, curr_insn
);
367 /* Treat if_then_else insns, where the operands of both branches
368 are registers, as copies. For instance,
370 (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
372 (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
373 DEF_INSN is the if_then_else insn. */
376 transform_ifelse (ext_cand
*cand
, rtx def_insn
)
378 rtx set_insn
= PATTERN (def_insn
);
379 rtx srcreg
, dstreg
, srcreg2
;
380 rtx map_srcreg
, map_dstreg
, map_srcreg2
;
385 gcc_assert (GET_CODE (set_insn
) == SET
);
387 cond
= XEXP (SET_SRC (set_insn
), 0);
388 dstreg
= SET_DEST (set_insn
);
389 srcreg
= XEXP (SET_SRC (set_insn
), 1);
390 srcreg2
= XEXP (SET_SRC (set_insn
), 2);
391 /* If the conditional move already has the right or wider mode,
392 there is nothing to do. */
393 if (GET_MODE_SIZE (GET_MODE (dstreg
)) >= GET_MODE_SIZE (cand
->mode
))
396 map_srcreg
= gen_rtx_REG (cand
->mode
, REGNO (srcreg
));
397 map_srcreg2
= gen_rtx_REG (cand
->mode
, REGNO (srcreg2
));
398 map_dstreg
= gen_rtx_REG (cand
->mode
, REGNO (dstreg
));
399 ifexpr
= gen_rtx_IF_THEN_ELSE (cand
->mode
, cond
, map_srcreg
, map_srcreg2
);
400 new_set
= gen_rtx_SET (VOIDmode
, map_dstreg
, ifexpr
);
402 if (validate_change (def_insn
, &PATTERN (def_insn
), new_set
, true))
407 "Mode of conditional move instruction extended:\n");
408 print_rtl_single (dump_file
, def_insn
);
416 /* Get all the reaching definitions of an instruction. The definitions are
417 desired for REG used in INSN. Return the definition list or NULL if a
418 definition is missing. If DEST is non-NULL, additionally push the INSN
419 of the definitions onto DEST. */
421 static struct df_link
*
422 get_defs (rtx insn
, rtx reg
, vec
<rtx
> *dest
)
424 df_ref reg_info
, *uses
;
425 struct df_link
*ref_chain
, *ref_link
;
429 for (uses
= DF_INSN_USES (insn
); *uses
; uses
++)
432 if (GET_CODE (DF_REF_REG (reg_info
)) == SUBREG
)
434 if (REGNO (DF_REF_REG (reg_info
)) == REGNO (reg
))
438 gcc_assert (reg_info
!= NULL
&& uses
!= NULL
);
440 ref_chain
= DF_REF_CHAIN (reg_info
);
442 for (ref_link
= ref_chain
; ref_link
; ref_link
= ref_link
->next
)
444 /* Problem getting some definition for this instruction. */
445 if (ref_link
->ref
== NULL
)
447 if (DF_REF_INSN_INFO (ref_link
->ref
) == NULL
)
452 for (ref_link
= ref_chain
; ref_link
; ref_link
= ref_link
->next
)
453 dest
->safe_push (DF_REF_INSN (ref_link
->ref
));
458 /* Return true if INSN is
459 (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
460 and store x1 and x2 in REG_1 and REG_2. */
463 is_cond_copy_insn (rtx insn
, rtx
*reg1
, rtx
*reg2
)
465 rtx expr
= single_set (insn
);
468 && GET_CODE (expr
) == SET
469 && GET_CODE (SET_DEST (expr
)) == REG
470 && GET_CODE (SET_SRC (expr
)) == IF_THEN_ELSE
471 && GET_CODE (XEXP (SET_SRC (expr
), 1)) == REG
472 && GET_CODE (XEXP (SET_SRC (expr
), 2)) == REG
)
474 *reg1
= XEXP (SET_SRC (expr
), 1);
475 *reg2
= XEXP (SET_SRC (expr
), 2);
482 enum ext_modified_kind
484 /* The insn hasn't been modified by ree pass yet. */
486 /* Changed into zero extension. */
488 /* Changed into sign extension. */
492 struct ATTRIBUTE_PACKED ext_modified
494 /* Mode from which ree has zero or sign extended the destination. */
495 ENUM_BITFIELD(machine_mode
) mode
: 8;
497 /* Kind of modification of the insn. */
498 ENUM_BITFIELD(ext_modified_kind
) kind
: 2;
500 /* True if the insn is scheduled to be deleted. */
501 unsigned int deleted
: 1;
504 /* Vectors used by combine_reaching_defs and its helpers. */
505 typedef struct ext_state
507 /* In order to avoid constant alloc/free, we keep these
508 4 vectors live through the entire find_and_remove_re and just
509 truncate them each time. */
511 vec
<rtx
> copies_list
;
512 vec
<rtx
> modified_list
;
515 /* For instructions that have been successfully modified, this is
516 the original mode from which the insn is extending and
517 kind of extension. */
518 struct ext_modified
*modified
;
521 /* Reaching Definitions of the extended register could be conditional copies
522 or regular definitions. This function separates the two types into two
523 lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because,
524 if a reaching definition is a conditional copy, merging the extension with
525 this definition is wrong. Conditional copies are merged by transitively
526 merging their definitions. The defs_list is populated with all the reaching
527 definitions of the extension instruction (EXTEND_INSN) which must be merged
528 with an extension. The copies_list contains all the conditional moves that
529 will later be extended into a wider mode conditional move if all the merges
530 are successful. The function returns false upon failure, true upon
534 make_defs_and_copies_lists (rtx extend_insn
, const_rtx set_pat
,
537 rtx src_reg
= XEXP (SET_SRC (set_pat
), 0);
538 bool *is_insn_visited
;
541 state
->work_list
.truncate (0);
543 /* Initialize the work list. */
544 if (!get_defs (extend_insn
, src_reg
, &state
->work_list
))
547 is_insn_visited
= XCNEWVEC (bool, max_insn_uid
);
549 /* Perform transitive closure for conditional copies. */
550 while (!state
->work_list
.is_empty ())
552 rtx def_insn
= state
->work_list
.pop ();
555 gcc_assert (INSN_UID (def_insn
) < max_insn_uid
);
557 if (is_insn_visited
[INSN_UID (def_insn
)])
559 is_insn_visited
[INSN_UID (def_insn
)] = true;
561 if (is_cond_copy_insn (def_insn
, ®1
, ®2
))
563 /* Push it onto the copy list first. */
564 state
->copies_list
.safe_push (def_insn
);
566 /* Now perform the transitive closure. */
567 if (!get_defs (def_insn
, reg1
, &state
->work_list
)
568 || !get_defs (def_insn
, reg2
, &state
->work_list
))
575 state
->defs_list
.safe_push (def_insn
);
578 XDELETEVEC (is_insn_visited
);
583 /* If DEF_INSN has single SET expression, possibly buried inside
584 a PARALLEL, return the address of the SET expression, else
585 return NULL. This is similar to single_set, except that
586 single_set allows multiple SETs when all but one is dead. */
588 get_sub_rtx (rtx def_insn
)
590 enum rtx_code code
= GET_CODE (PATTERN (def_insn
));
593 if (code
== PARALLEL
)
595 for (int i
= 0; i
< XVECLEN (PATTERN (def_insn
), 0); i
++)
597 rtx s_expr
= XVECEXP (PATTERN (def_insn
), 0, i
);
598 if (GET_CODE (s_expr
) != SET
)
602 sub_rtx
= &XVECEXP (PATTERN (def_insn
), 0, i
);
605 /* PARALLEL with multiple SETs. */
610 else if (code
== SET
)
611 sub_rtx
= &PATTERN (def_insn
);
614 /* It is not a PARALLEL or a SET, what could it be ? */
618 gcc_assert (sub_rtx
!= NULL
);
622 /* Merge the DEF_INSN with an extension. Calls combine_set_extension
623 on the SET pattern. */
626 merge_def_and_ext (ext_cand
*cand
, rtx def_insn
, ext_state
*state
)
628 enum machine_mode ext_src_mode
;
631 ext_src_mode
= GET_MODE (XEXP (SET_SRC (cand
->expr
), 0));
632 sub_rtx
= get_sub_rtx (def_insn
);
637 if (REG_P (SET_DEST (*sub_rtx
))
638 && (GET_MODE (SET_DEST (*sub_rtx
)) == ext_src_mode
639 || ((state
->modified
[INSN_UID (def_insn
)].kind
640 == (cand
->code
== ZERO_EXTEND
641 ? EXT_MODIFIED_ZEXT
: EXT_MODIFIED_SEXT
))
642 && state
->modified
[INSN_UID (def_insn
)].mode
645 if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx
)))
646 >= GET_MODE_SIZE (cand
->mode
))
648 /* If def_insn is already scheduled to be deleted, don't attempt
650 if (state
->modified
[INSN_UID (def_insn
)].deleted
)
652 if (combine_set_extension (cand
, def_insn
, sub_rtx
))
654 if (state
->modified
[INSN_UID (def_insn
)].kind
== EXT_MODIFIED_NONE
)
655 state
->modified
[INSN_UID (def_insn
)].mode
= ext_src_mode
;
663 /* This function goes through all reaching defs of the source
664 of the candidate for elimination (CAND) and tries to combine
665 the extension with the definition instruction. The changes
666 are made as a group so that even if one definition cannot be
667 merged, all reaching definitions end up not being merged.
668 When a conditional copy is encountered, merging is attempted
669 transitively on its definitions. It returns true upon success
670 and false upon failure. */
673 combine_reaching_defs (ext_cand
*cand
, const_rtx set_pat
, ext_state
*state
)
676 bool merge_successful
= true;
681 state
->defs_list
.truncate (0);
682 state
->copies_list
.truncate (0);
684 outcome
= make_defs_and_copies_lists (cand
->insn
, set_pat
, state
);
689 /* If the destination operand of the extension is a different
690 register than the source operand, then additional restrictions
692 if ((REGNO (SET_DEST (PATTERN (cand
->insn
)))
693 != REGNO (XEXP (SET_SRC (PATTERN (cand
->insn
)), 0))))
695 /* In theory we could handle more than one reaching def, it
696 just makes the code to update the insn stream more complex. */
697 if (state
->defs_list
.length () != 1)
700 /* We require the candidate not already be modified. This may
701 be overly conservative. */
702 if (state
->modified
[INSN_UID (cand
->insn
)].kind
!= EXT_MODIFIED_NONE
)
706 (set (reg1) (expression))
707 (set (reg2) (any_extend (reg1)))
709 (set (reg2) (any_extend (expression)))
711 is only valid for scalar integral modes, as it relies on the low
712 subreg of reg1 to have the value of (expression), which is not true
713 e.g. for vector modes. */
714 if (!SCALAR_INT_MODE_P (GET_MODE (SET_DEST (PATTERN (cand
->insn
)))))
717 /* There's only one reaching def. */
718 rtx def_insn
= state
->defs_list
[0];
720 /* The defining statement must not have been modified either. */
721 if (state
->modified
[INSN_UID (def_insn
)].kind
!= EXT_MODIFIED_NONE
)
724 /* The defining statement and candidate insn must be in the same block.
725 This is merely to keep the test for safety and updating the insn
726 stream simple. Also ensure that within the block the candidate
727 follows the defining insn. */
728 if (BLOCK_FOR_INSN (cand
->insn
) != BLOCK_FOR_INSN (def_insn
)
729 || DF_INSN_LUID (def_insn
) > DF_INSN_LUID (cand
->insn
))
732 /* If there is an overlap between the destination of DEF_INSN and
733 CAND->insn, then this transformation is not safe. Note we have
734 to test in the widened mode. */
735 rtx
*dest_sub_rtx
= get_sub_rtx (def_insn
);
736 if (dest_sub_rtx
== NULL
737 || !REG_P (SET_DEST (*dest_sub_rtx
)))
740 rtx tmp_reg
= gen_rtx_REG (GET_MODE (SET_DEST (PATTERN (cand
->insn
))),
741 REGNO (SET_DEST (*dest_sub_rtx
)));
742 if (reg_overlap_mentioned_p (tmp_reg
, SET_DEST (PATTERN (cand
->insn
))))
745 /* The destination register of the extension insn must not be
746 used or set between the def_insn and cand->insn exclusive. */
747 if (reg_used_between_p (SET_DEST (PATTERN (cand
->insn
)),
748 def_insn
, cand
->insn
)
749 || reg_set_between_p (SET_DEST (PATTERN (cand
->insn
)),
750 def_insn
, cand
->insn
))
755 /* If cand->insn has been already modified, update cand->mode to a wider
756 mode if possible, or punt. */
757 if (state
->modified
[INSN_UID (cand
->insn
)].kind
!= EXT_MODIFIED_NONE
)
759 enum machine_mode mode
;
762 if (state
->modified
[INSN_UID (cand
->insn
)].kind
763 != (cand
->code
== ZERO_EXTEND
764 ? EXT_MODIFIED_ZEXT
: EXT_MODIFIED_SEXT
)
765 || state
->modified
[INSN_UID (cand
->insn
)].mode
!= cand
->mode
766 || (set
= single_set (cand
->insn
)) == NULL_RTX
)
768 mode
= GET_MODE (SET_DEST (set
));
769 gcc_assert (GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (cand
->mode
));
773 merge_successful
= true;
775 /* Go through the defs vector and try to merge all the definitions
777 state
->modified_list
.truncate (0);
778 FOR_EACH_VEC_ELT (state
->defs_list
, defs_ix
, def_insn
)
780 if (merge_def_and_ext (cand
, def_insn
, state
))
781 state
->modified_list
.safe_push (def_insn
);
784 merge_successful
= false;
789 /* Now go through the conditional copies vector and try to merge all
790 the copies in this vector. */
791 if (merge_successful
)
793 FOR_EACH_VEC_ELT (state
->copies_list
, i
, def_insn
)
795 if (transform_ifelse (cand
, def_insn
))
796 state
->modified_list
.safe_push (def_insn
);
799 merge_successful
= false;
805 if (merge_successful
)
807 /* Commit the changes here if possible
808 FIXME: It's an all-or-nothing scenario. Even if only one definition
809 cannot be merged, we entirely give up. In the future, we should allow
810 extensions to be partially eliminated along those paths where the
811 definitions could be merged. */
812 if (apply_change_group ())
815 fprintf (dump_file
, "All merges were successful.\n");
817 FOR_EACH_VEC_ELT (state
->modified_list
, i
, def_insn
)
818 if (state
->modified
[INSN_UID (def_insn
)].kind
== EXT_MODIFIED_NONE
)
819 state
->modified
[INSN_UID (def_insn
)].kind
820 = (cand
->code
== ZERO_EXTEND
821 ? EXT_MODIFIED_ZEXT
: EXT_MODIFIED_SEXT
);
827 /* Changes need not be cancelled explicitly as apply_change_group
828 does it. Print list of definitions in the dump_file for debug
829 purposes. This extension cannot be deleted. */
833 "Merge cancelled, non-mergeable definitions:\n");
834 FOR_EACH_VEC_ELT (state
->modified_list
, i
, def_insn
)
835 print_rtl_single (dump_file
, def_insn
);
841 /* Cancel any changes that have been made so far. */
848 /* Add an extension pattern that could be eliminated. */
851 add_removable_extension (const_rtx expr
, rtx insn
,
852 vec
<ext_cand
> *insn_list
,
856 enum machine_mode mode
;
860 /* We are looking for SET (REG N) (ANY_EXTEND (REG N)). */
861 if (GET_CODE (expr
) != SET
)
864 src
= SET_SRC (expr
);
865 code
= GET_CODE (src
);
866 dest
= SET_DEST (expr
);
867 mode
= GET_MODE (dest
);
870 && (code
== SIGN_EXTEND
|| code
== ZERO_EXTEND
)
871 && REG_P (XEXP (src
, 0)))
873 struct df_link
*defs
, *def
;
876 /* First, make sure we can get all the reaching definitions. */
877 defs
= get_defs (insn
, XEXP (src
, 0), NULL
);
882 fprintf (dump_file
, "Cannot eliminate extension:\n");
883 print_rtl_single (dump_file
, insn
);
884 fprintf (dump_file
, " because of missing definition(s)\n");
889 /* Second, make sure the reaching definitions don't feed another and
890 different extension. FIXME: this obviously can be improved. */
891 for (def
= defs
; def
; def
= def
->next
)
892 if ((idx
= def_map
[INSN_UID (DF_REF_INSN (def
->ref
))])
893 && (cand
= &(*insn_list
)[idx
- 1])
894 && cand
->code
!= code
)
898 fprintf (dump_file
, "Cannot eliminate extension:\n");
899 print_rtl_single (dump_file
, insn
);
900 fprintf (dump_file
, " because of other extension\n");
905 /* Then add the candidate to the list and insert the reaching definitions
906 into the definition map. */
907 ext_cand e
= {expr
, code
, mode
, insn
};
908 insn_list
->safe_push (e
);
909 idx
= insn_list
->length ();
911 for (def
= defs
; def
; def
= def
->next
)
912 def_map
[INSN_UID (DF_REF_INSN (def
->ref
))] = idx
;
916 /* Traverse the instruction stream looking for extensions and return the
917 list of candidates. */
920 find_removable_extensions (void)
922 vec
<ext_cand
> insn_list
= vNULL
;
925 unsigned *def_map
= XCNEWVEC (unsigned, max_insn_uid
);
927 FOR_EACH_BB_FN (bb
, cfun
)
928 FOR_BB_INSNS (bb
, insn
)
930 if (!NONDEBUG_INSN_P (insn
))
933 set
= single_set (insn
);
936 add_removable_extension (set
, insn
, &insn_list
, def_map
);
939 XDELETEVEC (def_map
);
944 /* This is the main function that checks the insn stream for redundant
945 extensions and tries to remove them if possible. */
948 find_and_remove_re (void)
951 rtx curr_insn
= NULL_RTX
;
952 int num_re_opportunities
= 0, num_realized
= 0, i
;
953 vec
<ext_cand
> reinsn_list
;
954 auto_vec
<rtx
> reinsn_del_list
;
955 auto_vec
<rtx
> reinsn_copy_list
;
958 /* Construct DU chain to get all reaching definitions of each
959 extension instruction. */
960 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
961 df_chain_add_problem (DF_UD_CHAIN
+ DF_DU_CHAIN
);
963 df_set_flags (DF_DEFER_INSN_RESCAN
);
965 max_insn_uid
= get_max_uid ();
966 reinsn_list
= find_removable_extensions ();
967 state
.defs_list
.create (0);
968 state
.copies_list
.create (0);
969 state
.modified_list
.create (0);
970 state
.work_list
.create (0);
971 if (reinsn_list
.is_empty ())
972 state
.modified
= NULL
;
974 state
.modified
= XCNEWVEC (struct ext_modified
, max_insn_uid
);
976 FOR_EACH_VEC_ELT (reinsn_list
, i
, curr_cand
)
978 num_re_opportunities
++;
980 /* Try to combine the extension with the definition. */
983 fprintf (dump_file
, "Trying to eliminate extension:\n");
984 print_rtl_single (dump_file
, curr_cand
->insn
);
987 if (combine_reaching_defs (curr_cand
, curr_cand
->expr
, &state
))
990 fprintf (dump_file
, "Eliminated the extension.\n");
992 if (REGNO (SET_DEST (PATTERN (curr_cand
->insn
)))
993 != REGNO (XEXP (SET_SRC (PATTERN (curr_cand
->insn
)), 0)))
995 reinsn_copy_list
.safe_push (curr_cand
->insn
);
996 reinsn_copy_list
.safe_push (state
.defs_list
[0]);
998 reinsn_del_list
.safe_push (curr_cand
->insn
);
999 state
.modified
[INSN_UID (curr_cand
->insn
)].deleted
= 1;
1003 /* The copy list contains pairs of insns which describe copies we
1004 need to insert into the INSN stream.
1006 The first insn in each pair is the extension insn, from which
1007 we derive the source and destination of the copy.
1009 The second insn in each pair is the memory reference where the
1010 extension will ultimately happen. We emit the new copy
1011 immediately after this insn.
1013 It may first appear that the arguments for the copy are reversed.
1014 Remember that the memory reference will be changed to refer to the
1015 destination of the extention. So we're actually emitting a copy
1016 from the new destination to the old destination. */
1017 for (unsigned int i
= 0; i
< reinsn_copy_list
.length (); i
+= 2)
1019 rtx curr_insn
= reinsn_copy_list
[i
];
1020 rtx pat
= PATTERN (curr_insn
);
1021 rtx new_reg
= gen_rtx_REG (GET_MODE (SET_DEST (pat
)),
1022 REGNO (XEXP (SET_SRC (pat
), 0)));
1023 rtx set
= gen_rtx_SET (VOIDmode
, new_reg
, SET_DEST (pat
));
1024 emit_insn_after (set
, reinsn_copy_list
[i
+ 1]);
1027 /* Delete all useless extensions here in one sweep. */
1028 FOR_EACH_VEC_ELT (reinsn_del_list
, i
, curr_insn
)
1029 delete_insn (curr_insn
);
1031 reinsn_list
.release ();
1032 state
.defs_list
.release ();
1033 state
.copies_list
.release ();
1034 state
.modified_list
.release ();
1035 state
.work_list
.release ();
1036 XDELETEVEC (state
.modified
);
1038 if (dump_file
&& num_re_opportunities
> 0)
1039 fprintf (dump_file
, "Elimination opportunities = %d realized = %d\n",
1040 num_re_opportunities
, num_realized
);
1043 /* Find and remove redundant extensions. */
1046 rest_of_handle_ree (void)
1048 timevar_push (TV_REE
);
1049 find_and_remove_re ();
1050 timevar_pop (TV_REE
);
1054 /* Run REE pass when flag_ree is set at optimization level > 0. */
1057 gate_handle_ree (void)
1059 return (optimize
> 0 && flag_ree
);
1064 const pass_data pass_data_ree
=
1066 RTL_PASS
, /* type */
1068 OPTGROUP_NONE
, /* optinfo_flags */
1069 true, /* has_gate */
1070 true, /* has_execute */
1072 0, /* properties_required */
1073 0, /* properties_provided */
1074 0, /* properties_destroyed */
1075 0, /* todo_flags_start */
1076 ( TODO_df_finish
| TODO_verify_rtl_sharing
), /* todo_flags_finish */
1079 class pass_ree
: public rtl_opt_pass
1082 pass_ree (gcc::context
*ctxt
)
1083 : rtl_opt_pass (pass_data_ree
, ctxt
)
1086 /* opt_pass methods: */
1087 bool gate () { return gate_handle_ree (); }
1088 unsigned int execute () { return rest_of_handle_ree (); }
1090 }; // class pass_ree
1095 make_pass_ree (gcc::context
*ctxt
)
1097 return new pass_ree (ctxt
);