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"
231 #include "hash-set.h"
232 #include "machmode.h"
234 #include "function.h"
235 #include "dominance.h"
238 #include "basic-block.h"
239 #include "insn-config.h"
241 #include "insn-attr.h"
243 #include "diagnostic-core.h"
246 #include "insn-codes.h"
247 #include "rtlhooks-def.h"
249 #include "tree-pass.h"
253 /* This structure represents a candidate for elimination. */
255 typedef struct ext_cand
257 /* The expression. */
260 /* The kind of extension. */
263 /* The destination mode. */
264 enum machine_mode mode;
266 /* The instruction where it lives. */
271 static int max_insn_uid;
273 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND)
274 and a pointer to the SET rtx (ORIG_SET) that needs to be modified,
275 this code modifies the SET rtx to a new SET rtx that extends the
276 right hand expression into a register on the left hand side. Note
277 that multiple assumptions are made about the nature of the set that
278 needs to be true for this to work and is called from merge_def_and_ext.
281 (set (reg a) (expression))
284 (set (reg a) (any_extend (expression)))
287 If the expression is a constant or another extension, then directly
288 assign it to the register. */
291 combine_set_extension (ext_cand *cand, rtx_insn *curr_insn, rtx *orig_set)
293 rtx orig_src = SET_SRC (*orig_set);
295 rtx cand_pat = PATTERN (cand->insn);
297 /* If the extension's source/destination registers are not the same
298 then we need to change the original load to reference the destination
299 of the extension. Then we need to emit a copy from that destination
300 to the original destination of the load. */
303 = (REGNO (SET_DEST (cand_pat)) != REGNO (XEXP (SET_SRC (cand_pat), 0)));
305 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (cand_pat)));
307 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (*orig_set)));
310 /* Rethinking test. Temporarily disabled. */
311 /* We're going to be widening the result of DEF_INSN, ensure that doing so
312 doesn't change the number of hard registers needed for the result. */
313 if (HARD_REGNO_NREGS (REGNO (new_reg), cand->mode)
314 != HARD_REGNO_NREGS (REGNO (SET_DEST (*orig_set)),
315 GET_MODE (SET_DEST (*orig_set))))
319 /* Merge constants by directly moving the constant into the register under
320 some conditions. Recall that RTL constants are sign-extended. */
321 if (GET_CODE (orig_src) == CONST_INT
322 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (cand->mode))
324 if (INTVAL (orig_src) >= 0 || cand->code == SIGN_EXTEND)
325 new_set = gen_rtx_SET (VOIDmode, new_reg, orig_src);
328 /* Zero-extend the negative constant by masking out the bits outside
330 enum machine_mode src_mode = GET_MODE (SET_DEST (*orig_set));
332 = gen_int_mode (INTVAL (orig_src) & GET_MODE_MASK (src_mode),
334 new_set = gen_rtx_SET (VOIDmode, new_reg, new_const_int);
337 else if (GET_MODE (orig_src) == VOIDmode)
339 /* This is mostly due to a call insn that should not be optimized. */
342 else if (GET_CODE (orig_src) == cand->code)
344 /* Here is a sequence of two extensions. Try to merge them. */
346 = gen_rtx_fmt_e (cand->code, cand->mode, XEXP (orig_src, 0));
347 rtx simplified_temp_extension = simplify_rtx (temp_extension);
348 if (simplified_temp_extension)
349 temp_extension = simplified_temp_extension;
350 new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension);
352 else if (GET_CODE (orig_src) == IF_THEN_ELSE)
354 /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
355 in general, IF_THEN_ELSE should not be combined. */
360 /* This is the normal case. */
362 = gen_rtx_fmt_e (cand->code, cand->mode, orig_src);
363 rtx simplified_temp_extension = simplify_rtx (temp_extension);
364 if (simplified_temp_extension)
365 temp_extension = simplified_temp_extension;
366 new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension);
369 /* This change is a part of a group of changes. Hence,
370 validate_change will not try to commit the change. */
371 if (validate_change (curr_insn, orig_set, new_set, true))
376 "Tentatively merged extension with definition %s:\n",
377 (copy_needed) ? "(copy needed)" : "");
378 print_rtl_single (dump_file, curr_insn);
386 /* Treat if_then_else insns, where the operands of both branches
387 are registers, as copies. For instance,
389 (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
391 (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
392 DEF_INSN is the if_then_else insn. */
395 transform_ifelse (ext_cand *cand, rtx_insn *def_insn)
397 rtx set_insn = PATTERN (def_insn);
398 rtx srcreg, dstreg, srcreg2;
399 rtx map_srcreg, map_dstreg, map_srcreg2;
404 gcc_assert (GET_CODE (set_insn) == SET);
406 cond = XEXP (SET_SRC (set_insn), 0);
407 dstreg = SET_DEST (set_insn);
408 srcreg = XEXP (SET_SRC (set_insn), 1);
409 srcreg2 = XEXP (SET_SRC (set_insn), 2);
410 /* If the conditional move already has the right or wider mode,
411 there is nothing to do. */
412 if (GET_MODE_SIZE (GET_MODE (dstreg)) >= GET_MODE_SIZE (cand->mode))
415 map_srcreg = gen_rtx_REG (cand->mode, REGNO (srcreg));
416 map_srcreg2 = gen_rtx_REG (cand->mode, REGNO (srcreg2));
417 map_dstreg = gen_rtx_REG (cand->mode, REGNO (dstreg));
418 ifexpr = gen_rtx_IF_THEN_ELSE (cand->mode, cond, map_srcreg, map_srcreg2);
419 new_set = gen_rtx_SET (VOIDmode, map_dstreg, ifexpr);
421 if (validate_change (def_insn, &PATTERN (def_insn), new_set, true))
426 "Mode of conditional move instruction extended:\n");
427 print_rtl_single (dump_file, def_insn);
435 /* Get all the reaching definitions of an instruction. The definitions are
436 desired for REG used in INSN. Return the definition list or NULL if a
437 definition is missing. If DEST is non-NULL, additionally push the INSN
438 of the definitions onto DEST. */
440 static struct df_link *
441 get_defs (rtx_insn *insn, rtx reg, vec<rtx_insn *> *dest)
444 struct df_link *ref_chain, *ref_link;
446 FOR_EACH_INSN_USE (use, insn)
448 if (GET_CODE (DF_REF_REG (use)) == SUBREG)
450 if (REGNO (DF_REF_REG (use)) == REGNO (reg))
454 gcc_assert (use != NULL);
456 ref_chain = DF_REF_CHAIN (use);
458 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
460 /* Problem getting some definition for this instruction. */
461 if (ref_link->ref == NULL)
463 if (DF_REF_INSN_INFO (ref_link->ref) == NULL)
468 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
469 dest->safe_push (DF_REF_INSN (ref_link->ref));
474 /* Return true if INSN is
475 (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
476 and store x1 and x2 in REG_1 and REG_2. */
479 is_cond_copy_insn (rtx_insn *insn, rtx *reg1, rtx *reg2)
481 rtx expr = single_set (insn);
484 && GET_CODE (expr) == SET
485 && GET_CODE (SET_DEST (expr)) == REG
486 && GET_CODE (SET_SRC (expr)) == IF_THEN_ELSE
487 && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG
488 && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG)
490 *reg1 = XEXP (SET_SRC (expr), 1);
491 *reg2 = XEXP (SET_SRC (expr), 2);
498 enum ext_modified_kind
500 /* The insn hasn't been modified by ree pass yet. */
502 /* Changed into zero extension. */
504 /* Changed into sign extension. */
508 struct ATTRIBUTE_PACKED ext_modified
510 /* Mode from which ree has zero or sign extended the destination. */
511 ENUM_BITFIELD(machine_mode) mode : 8;
513 /* Kind of modification of the insn. */
514 ENUM_BITFIELD(ext_modified_kind) kind : 2;
516 unsigned int do_not_reextend : 1;
518 /* True if the insn is scheduled to be deleted. */
519 unsigned int deleted : 1;
522 /* Vectors used by combine_reaching_defs and its helpers. */
523 typedef struct ext_state
525 /* In order to avoid constant alloc/free, we keep these
526 4 vectors live through the entire find_and_remove_re and just
527 truncate them each time. */
528 vec<rtx_insn *> defs_list;
529 vec<rtx_insn *> copies_list;
530 vec<rtx_insn *> modified_list;
531 vec<rtx_insn *> work_list;
533 /* For instructions that have been successfully modified, this is
534 the original mode from which the insn is extending and
535 kind of extension. */
536 struct ext_modified *modified;
539 /* Reaching Definitions of the extended register could be conditional copies
540 or regular definitions. This function separates the two types into two
541 lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because,
542 if a reaching definition is a conditional copy, merging the extension with
543 this definition is wrong. Conditional copies are merged by transitively
544 merging their definitions. The defs_list is populated with all the reaching
545 definitions of the extension instruction (EXTEND_INSN) which must be merged
546 with an extension. The copies_list contains all the conditional moves that
547 will later be extended into a wider mode conditional move if all the merges
548 are successful. The function returns false upon failure, true upon
552 make_defs_and_copies_lists (rtx_insn *extend_insn, const_rtx set_pat,
555 rtx src_reg = XEXP (SET_SRC (set_pat), 0);
556 bool *is_insn_visited;
559 state->work_list.truncate (0);
561 /* Initialize the work list. */
562 if (!get_defs (extend_insn, src_reg, &state->work_list))
565 is_insn_visited = XCNEWVEC (bool, max_insn_uid);
567 /* Perform transitive closure for conditional copies. */
568 while (!state->work_list.is_empty ())
570 rtx_insn *def_insn = state->work_list.pop ();
573 gcc_assert (INSN_UID (def_insn) < max_insn_uid);
575 if (is_insn_visited[INSN_UID (def_insn)])
577 is_insn_visited[INSN_UID (def_insn)] = true;
579 if (is_cond_copy_insn (def_insn, ®1, ®2))
581 /* Push it onto the copy list first. */
582 state->copies_list.safe_push (def_insn);
584 /* Now perform the transitive closure. */
585 if (!get_defs (def_insn, reg1, &state->work_list)
586 || !get_defs (def_insn, reg2, &state->work_list))
593 state->defs_list.safe_push (def_insn);
596 XDELETEVEC (is_insn_visited);
601 /* If DEF_INSN has single SET expression, possibly buried inside
602 a PARALLEL, return the address of the SET expression, else
603 return NULL. This is similar to single_set, except that
604 single_set allows multiple SETs when all but one is dead. */
606 get_sub_rtx (rtx_insn *def_insn)
608 enum rtx_code code = GET_CODE (PATTERN (def_insn));
611 if (code == PARALLEL)
613 for (int i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++)
615 rtx s_expr = XVECEXP (PATTERN (def_insn), 0, i);
616 if (GET_CODE (s_expr) != SET)
620 sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i);
623 /* PARALLEL with multiple SETs. */
628 else if (code == SET)
629 sub_rtx = &PATTERN (def_insn);
632 /* It is not a PARALLEL or a SET, what could it be ? */
636 gcc_assert (sub_rtx != NULL);
640 /* Merge the DEF_INSN with an extension. Calls combine_set_extension
641 on the SET pattern. */
644 merge_def_and_ext (ext_cand *cand, rtx_insn *def_insn, ext_state *state)
646 enum machine_mode ext_src_mode;
649 ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0));
650 sub_rtx = get_sub_rtx (def_insn);
655 if (REG_P (SET_DEST (*sub_rtx))
656 && (GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode
657 || ((state->modified[INSN_UID (def_insn)].kind
658 == (cand->code == ZERO_EXTEND
659 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT))
660 && state->modified[INSN_UID (def_insn)].mode
663 if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx)))
664 >= GET_MODE_SIZE (cand->mode))
666 /* If def_insn is already scheduled to be deleted, don't attempt
668 if (state->modified[INSN_UID (def_insn)].deleted)
670 if (combine_set_extension (cand, def_insn, sub_rtx))
672 if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE)
673 state->modified[INSN_UID (def_insn)].mode = ext_src_mode;
681 /* Given SRC, which should be one or more extensions of a REG, strip
682 away the extensions and return the REG. */
685 get_extended_src_reg (rtx src)
687 while (GET_CODE (src) == SIGN_EXTEND || GET_CODE (src) == ZERO_EXTEND)
689 gcc_assert (REG_P (src));
693 /* This function goes through all reaching defs of the source
694 of the candidate for elimination (CAND) and tries to combine
695 the extension with the definition instruction. The changes
696 are made as a group so that even if one definition cannot be
697 merged, all reaching definitions end up not being merged.
698 When a conditional copy is encountered, merging is attempted
699 transitively on its definitions. It returns true upon success
700 and false upon failure. */
703 combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state)
706 bool merge_successful = true;
711 state->defs_list.truncate (0);
712 state->copies_list.truncate (0);
714 outcome = make_defs_and_copies_lists (cand->insn, set_pat, state);
719 /* If the destination operand of the extension is a different
720 register than the source operand, then additional restrictions
721 are needed. Note we have to handle cases where we have nested
722 extensions in the source operand. */
724 = (REGNO (SET_DEST (PATTERN (cand->insn)))
725 != REGNO (get_extended_src_reg (SET_SRC (PATTERN (cand->insn)))));
728 /* In theory we could handle more than one reaching def, it
729 just makes the code to update the insn stream more complex. */
730 if (state->defs_list.length () != 1)
733 /* We require the candidate not already be modified. It may,
734 for example have been changed from a (sign_extend (reg))
735 into (zero_extend (sign_extend (reg))).
737 Handling that case shouldn't be terribly difficult, but the code
738 here and the code to emit copies would need auditing. Until
739 we see a need, this is the safe thing to do. */
740 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE)
744 (set (reg1) (expression))
745 (set (reg2) (any_extend (reg1)))
747 (set (reg2) (any_extend (expression)))
749 is only valid for scalar integral modes, as it relies on the low
750 subreg of reg1 to have the value of (expression), which is not true
751 e.g. for vector modes. */
752 if (!SCALAR_INT_MODE_P (GET_MODE (SET_DEST (PATTERN (cand->insn)))))
755 enum machine_mode dst_mode = GET_MODE (SET_DEST (PATTERN (cand->insn)));
756 rtx src_reg = get_extended_src_reg (SET_SRC (PATTERN (cand->insn)));
758 /* Ensure the number of hard registers of the copy match. */
759 if (HARD_REGNO_NREGS (REGNO (src_reg), dst_mode)
760 != HARD_REGNO_NREGS (REGNO (src_reg), GET_MODE (src_reg)))
763 /* There's only one reaching def. */
764 rtx_insn *def_insn = state->defs_list[0];
766 /* The defining statement must not have been modified either. */
767 if (state->modified[INSN_UID (def_insn)].kind != EXT_MODIFIED_NONE)
770 /* The defining statement and candidate insn must be in the same block.
771 This is merely to keep the test for safety and updating the insn
772 stream simple. Also ensure that within the block the candidate
773 follows the defining insn. */
774 basic_block bb = BLOCK_FOR_INSN (cand->insn);
775 if (bb != BLOCK_FOR_INSN (def_insn)
776 || DF_INSN_LUID (def_insn) > DF_INSN_LUID (cand->insn))
779 /* If there is an overlap between the destination of DEF_INSN and
780 CAND->insn, then this transformation is not safe. Note we have
781 to test in the widened mode. */
782 rtx *dest_sub_rtx = get_sub_rtx (def_insn);
783 if (dest_sub_rtx == NULL
784 || !REG_P (SET_DEST (*dest_sub_rtx)))
787 rtx tmp_reg = gen_rtx_REG (GET_MODE (SET_DEST (PATTERN (cand->insn))),
788 REGNO (SET_DEST (*dest_sub_rtx)));
789 if (reg_overlap_mentioned_p (tmp_reg, SET_DEST (PATTERN (cand->insn))))
792 /* The destination register of the extension insn must not be
793 used or set between the def_insn and cand->insn exclusive. */
794 if (reg_used_between_p (SET_DEST (PATTERN (cand->insn)),
795 def_insn, cand->insn)
796 || reg_set_between_p (SET_DEST (PATTERN (cand->insn)),
797 def_insn, cand->insn))
800 /* We must be able to copy between the two registers. Generate,
801 recognize and verify constraints of the copy. Also fail if this
802 generated more than one insn.
804 This generates garbage since we throw away the insn when we're
805 done, only to recreate it later if this test was successful.
807 Make sure to get the mode from the extension (cand->insn). This
808 is different than in the code to emit the copy as we have not
809 modified the defining insn yet. */
811 rtx pat = PATTERN (cand->insn);
812 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (pat)),
813 REGNO (get_extended_src_reg (SET_SRC (pat))));
814 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (pat)),
815 REGNO (SET_DEST (pat)));
816 emit_move_insn (new_dst, new_src);
818 rtx_insn *insn = get_insns();
820 if (NEXT_INSN (insn))
822 if (recog_memoized (insn) == -1)
825 if (!constrain_operands (1, get_preferred_alternatives (insn, bb)))
830 /* If cand->insn has been already modified, update cand->mode to a wider
831 mode if possible, or punt. */
832 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE)
834 enum machine_mode mode;
837 if (state->modified[INSN_UID (cand->insn)].kind
838 != (cand->code == ZERO_EXTEND
839 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT)
840 || state->modified[INSN_UID (cand->insn)].mode != cand->mode
841 || (set = single_set (cand->insn)) == NULL_RTX)
843 mode = GET_MODE (SET_DEST (set));
844 gcc_assert (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (cand->mode));
848 merge_successful = true;
850 /* Go through the defs vector and try to merge all the definitions
852 state->modified_list.truncate (0);
853 FOR_EACH_VEC_ELT (state->defs_list, defs_ix, def_insn)
855 if (merge_def_and_ext (cand, def_insn, state))
856 state->modified_list.safe_push (def_insn);
859 merge_successful = false;
864 /* Now go through the conditional copies vector and try to merge all
865 the copies in this vector. */
866 if (merge_successful)
868 FOR_EACH_VEC_ELT (state->copies_list, i, def_insn)
870 if (transform_ifelse (cand, def_insn))
871 state->modified_list.safe_push (def_insn);
874 merge_successful = false;
880 if (merge_successful)
882 /* Commit the changes here if possible
883 FIXME: It's an all-or-nothing scenario. Even if only one definition
884 cannot be merged, we entirely give up. In the future, we should allow
885 extensions to be partially eliminated along those paths where the
886 definitions could be merged. */
887 if (apply_change_group ())
890 fprintf (dump_file, "All merges were successful.\n");
892 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
894 ext_modified *modified = &state->modified[INSN_UID (def_insn)];
895 if (modified->kind == EXT_MODIFIED_NONE)
896 modified->kind = (cand->code == ZERO_EXTEND ? EXT_MODIFIED_ZEXT
897 : EXT_MODIFIED_SEXT);
900 modified->do_not_reextend = 1;
906 /* Changes need not be cancelled explicitly as apply_change_group
907 does it. Print list of definitions in the dump_file for debug
908 purposes. This extension cannot be deleted. */
912 "Merge cancelled, non-mergeable definitions:\n");
913 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
914 print_rtl_single (dump_file, def_insn);
920 /* Cancel any changes that have been made so far. */
927 /* Add an extension pattern that could be eliminated. */
930 add_removable_extension (const_rtx expr, rtx_insn *insn,
931 vec<ext_cand> *insn_list,
935 enum machine_mode mode;
939 /* We are looking for SET (REG N) (ANY_EXTEND (REG N)). */
940 if (GET_CODE (expr) != SET)
943 src = SET_SRC (expr);
944 code = GET_CODE (src);
945 dest = SET_DEST (expr);
946 mode = GET_MODE (dest);
949 && (code == SIGN_EXTEND || code == ZERO_EXTEND)
950 && REG_P (XEXP (src, 0)))
952 struct df_link *defs, *def;
955 /* First, make sure we can get all the reaching definitions. */
956 defs = get_defs (insn, XEXP (src, 0), NULL);
961 fprintf (dump_file, "Cannot eliminate extension:\n");
962 print_rtl_single (dump_file, insn);
963 fprintf (dump_file, " because of missing definition(s)\n");
968 /* Second, make sure the reaching definitions don't feed another and
969 different extension. FIXME: this obviously can be improved. */
970 for (def = defs; def; def = def->next)
971 if ((idx = def_map[INSN_UID (DF_REF_INSN (def->ref))])
972 && (cand = &(*insn_list)[idx - 1])
973 && cand->code != code)
977 fprintf (dump_file, "Cannot eliminate extension:\n");
978 print_rtl_single (dump_file, insn);
979 fprintf (dump_file, " because of other extension\n");
984 /* Then add the candidate to the list and insert the reaching definitions
985 into the definition map. */
986 ext_cand e = {expr, code, mode, insn};
987 insn_list->safe_push (e);
988 idx = insn_list->length ();
990 for (def = defs; def; def = def->next)
991 def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx;
995 /* Traverse the instruction stream looking for extensions and return the
996 list of candidates. */
999 find_removable_extensions (void)
1001 vec<ext_cand> insn_list = vNULL;
1005 unsigned *def_map = XCNEWVEC (unsigned, max_insn_uid);
1007 FOR_EACH_BB_FN (bb, cfun)
1008 FOR_BB_INSNS (bb, insn)
1010 if (!NONDEBUG_INSN_P (insn))
1013 set = single_set (insn);
1014 if (set == NULL_RTX)
1016 add_removable_extension (set, insn, &insn_list, def_map);
1019 XDELETEVEC (def_map);
1024 /* This is the main function that checks the insn stream for redundant
1025 extensions and tries to remove them if possible. */
1028 find_and_remove_re (void)
1030 ext_cand *curr_cand;
1031 rtx_insn *curr_insn = NULL;
1032 int num_re_opportunities = 0, num_realized = 0, i;
1033 vec<ext_cand> reinsn_list;
1034 auto_vec<rtx_insn *> reinsn_del_list;
1035 auto_vec<rtx_insn *> reinsn_copy_list;
1038 /* Construct DU chain to get all reaching definitions of each
1039 extension instruction. */
1040 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
1041 df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
1043 df_set_flags (DF_DEFER_INSN_RESCAN);
1045 max_insn_uid = get_max_uid ();
1046 reinsn_list = find_removable_extensions ();
1047 state.defs_list.create (0);
1048 state.copies_list.create (0);
1049 state.modified_list.create (0);
1050 state.work_list.create (0);
1051 if (reinsn_list.is_empty ())
1052 state.modified = NULL;
1054 state.modified = XCNEWVEC (struct ext_modified, max_insn_uid);
1056 FOR_EACH_VEC_ELT (reinsn_list, i, curr_cand)
1058 num_re_opportunities++;
1060 /* Try to combine the extension with the definition. */
1063 fprintf (dump_file, "Trying to eliminate extension:\n");
1064 print_rtl_single (dump_file, curr_cand->insn);
1067 if (combine_reaching_defs (curr_cand, curr_cand->expr, &state))
1070 fprintf (dump_file, "Eliminated the extension.\n");
1072 /* If the RHS of the current candidate is not (extend (reg)), then
1073 we do not allow the optimization of extensions where
1074 the source and destination registers do not match. Thus
1075 checking REG_P here is correct. */
1076 if (REG_P (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0))
1077 && (REGNO (SET_DEST (PATTERN (curr_cand->insn)))
1078 != REGNO (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0))))
1080 reinsn_copy_list.safe_push (curr_cand->insn);
1081 reinsn_copy_list.safe_push (state.defs_list[0]);
1083 reinsn_del_list.safe_push (curr_cand->insn);
1084 state.modified[INSN_UID (curr_cand->insn)].deleted = 1;
1088 /* The copy list contains pairs of insns which describe copies we
1089 need to insert into the INSN stream.
1091 The first insn in each pair is the extension insn, from which
1092 we derive the source and destination of the copy.
1094 The second insn in each pair is the memory reference where the
1095 extension will ultimately happen. We emit the new copy
1096 immediately after this insn.
1098 It may first appear that the arguments for the copy are reversed.
1099 Remember that the memory reference will be changed to refer to the
1100 destination of the extention. So we're actually emitting a copy
1101 from the new destination to the old destination. */
1102 for (unsigned int i = 0; i < reinsn_copy_list.length (); i += 2)
1104 rtx_insn *curr_insn = reinsn_copy_list[i];
1105 rtx_insn *def_insn = reinsn_copy_list[i + 1];
1107 /* Use the mode of the destination of the defining insn
1108 for the mode of the copy. This is necessary if the
1109 defining insn was used to eliminate a second extension
1110 that was wider than the first. */
1111 rtx sub_rtx = *get_sub_rtx (def_insn);
1112 rtx pat = PATTERN (curr_insn);
1113 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)),
1114 REGNO (XEXP (SET_SRC (pat), 0)));
1115 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)),
1116 REGNO (SET_DEST (pat)));
1117 rtx set = gen_rtx_SET (VOIDmode, new_dst, new_src);
1118 emit_insn_after (set, def_insn);
1121 /* Delete all useless extensions here in one sweep. */
1122 FOR_EACH_VEC_ELT (reinsn_del_list, i, curr_insn)
1123 delete_insn (curr_insn);
1125 reinsn_list.release ();
1126 state.defs_list.release ();
1127 state.copies_list.release ();
1128 state.modified_list.release ();
1129 state.work_list.release ();
1130 XDELETEVEC (state.modified);
1132 if (dump_file && num_re_opportunities > 0)
1133 fprintf (dump_file, "Elimination opportunities = %d realized = %d\n",
1134 num_re_opportunities, num_realized);
1137 /* Find and remove redundant extensions. */
1140 rest_of_handle_ree (void)
1142 timevar_push (TV_REE);
1143 find_and_remove_re ();
1144 timevar_pop (TV_REE);
1150 const pass_data pass_data_ree =
1152 RTL_PASS, /* type */
1154 OPTGROUP_NONE, /* optinfo_flags */
1156 0, /* properties_required */
1157 0, /* properties_provided */
1158 0, /* properties_destroyed */
1159 0, /* todo_flags_start */
1160 TODO_df_finish, /* todo_flags_finish */
1163 class pass_ree : public rtl_opt_pass
1166 pass_ree (gcc::context *ctxt)
1167 : rtl_opt_pass (pass_data_ree, ctxt)
1170 /* opt_pass methods: */
1171 virtual bool gate (function *) { return (optimize > 0 && flag_ree); }
1172 virtual unsigned int execute (function *) { return rest_of_handle_ree (); }
1174 }; // class pass_ree
1179 make_pass_ree (gcc::context *ctxt)
1181 return new pass_ree (ctxt);