1 /* Redundant Extension Elimination pass for the GNU compiler.
2 Copyright (C) 2010-2011 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 move 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 defintions 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 extend
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 extend
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 extend
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 extend
192 1e: 0f b6 c0 movzbl %al,%eax --> Useless extend
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"
238 #include "insn-codes.h"
239 #include "rtlhooks-def.h"
240 /* Include output.h for dump_file. */
244 #include "tree-pass.h"
248 /* This says if a register is newly created for the purpose of
253 MERGE_NOT_ATTEMPTED = 0,
257 /* This structure is used to hold data about candidate for
260 typedef struct GTY(()) ext_cand
264 enum machine_mode src_mode;
265 } ext_cand, *ext_cand_ref;
268 DEF_VEC_ALLOC_O(ext_cand, heap);
270 /* This says if a INSN UID or its definition has already been merged
271 with a extension or not. */
273 static enum insn_merge_code *is_insn_merge_attempted;
274 static int max_insn_uid;
276 /* Return the merge code status for INSN. */
278 static enum insn_merge_code
279 get_insn_status (rtx insn)
281 gcc_assert (INSN_UID (insn) < max_insn_uid);
282 return is_insn_merge_attempted[INSN_UID (insn)];
285 /* Set the merge code status of INSN to CODE. */
288 set_insn_status (rtx insn, enum insn_merge_code code)
290 gcc_assert (INSN_UID (insn) < max_insn_uid);
291 is_insn_merge_attempted[INSN_UID (insn)] = code;
294 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND)
295 and a pointer to the SET rtx (ORIG_SET) that needs to be modified,
296 this code modifies the SET rtx to a new SET rtx that extends the
297 right hand expression into a register on the left hand side. Note
298 that multiple assumptions are made about the nature of the set that
299 needs to be true for this to work and is called from merge_def_and_ext.
302 (set (reg a) (expression))
305 (set (reg a) (extend (expression)))
308 If the expression is a constant or another extend directly
309 assign it to the register. */
312 combine_set_extend (ext_cand_ref cand, rtx curr_insn, rtx *orig_set)
314 rtx temp_extension, simplified_temp_extension, new_set, new_const_int;
315 rtx orig_src, cand_src;
317 enum machine_mode dst_mode = GET_MODE (SET_DEST (cand->expr));
319 /* Change the SET rtx and validate it. */
320 orig_src = SET_SRC (*orig_set);
321 cand_src = SET_SRC (cand->expr);
324 newreg = gen_rtx_REG (dst_mode, REGNO (SET_DEST (*orig_set)));
326 /* Merge constants by directly moving the constant into the
327 register under some conditions. */
329 if (GET_CODE (orig_src) == CONST_INT
330 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (dst_mode))
332 if (INTVAL (orig_src) >= 0 || GET_CODE (cand_src) == SIGN_EXTEND)
333 new_set = gen_rtx_SET (VOIDmode, newreg, orig_src);
336 /* Zero-extend the negative constant by masking out the bits outside
338 enum machine_mode src_mode = GET_MODE (SET_DEST (*orig_set));
340 = GEN_INT (INTVAL (orig_src) & GET_MODE_MASK (src_mode));
341 new_set = gen_rtx_SET (VOIDmode, newreg, new_const_int);
344 else if (GET_MODE (orig_src) == VOIDmode)
346 /* This is mostly due to a call insn that should not be
351 else if (GET_CODE (orig_src) == GET_CODE (cand_src))
353 /* Here is a sequence of two extensions. Try to merge them into a
357 = gen_rtx_fmt_e (GET_CODE (orig_src), dst_mode, XEXP (orig_src, 0));
358 simplified_temp_extension = simplify_rtx (temp_extension);
359 if (simplified_temp_extension)
360 temp_extension = simplified_temp_extension;
361 new_set = gen_rtx_SET (VOIDmode, newreg, temp_extension);
363 else if (GET_CODE (orig_src) == IF_THEN_ELSE)
365 /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
366 in general, IF_THEN_ELSE should not be combined. */
372 /* This is the normal case we expect. */
375 = gen_rtx_fmt_e (GET_CODE (cand_src), dst_mode, orig_src);
376 simplified_temp_extension = simplify_rtx (temp_extension);
377 if (simplified_temp_extension)
378 temp_extension = simplified_temp_extension;
379 new_set = gen_rtx_SET (VOIDmode, newreg, temp_extension);
382 gcc_assert (new_set != NULL_RTX);
384 /* This change is a part of a group of changes. Hence,
385 validate_change will not try to commit the change. */
387 if (validate_change (curr_insn, orig_set, new_set, true))
391 fprintf (dump_file, "Merged Instruction with EXTEND:\n");
392 print_rtl_single (dump_file, curr_insn);
399 /* Treat if_then_else insns, where the operands of both branches
400 are registers, as copies. For instance,
402 (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
404 (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
405 DEF_INSN is the if_then_else insn. */
408 transform_ifelse (ext_cand_ref cand, rtx def_insn)
410 rtx set_insn = PATTERN (def_insn);
411 rtx srcreg, dstreg, srcreg2;
412 rtx map_srcreg, map_dstreg, map_srcreg2;
416 enum machine_mode dst_mode = GET_MODE (SET_DEST (cand->expr));
418 gcc_assert (GET_CODE (set_insn) == SET);
419 cond = XEXP (SET_SRC (set_insn), 0);
420 dstreg = SET_DEST (set_insn);
421 srcreg = XEXP (SET_SRC (set_insn), 1);
422 srcreg2 = XEXP (SET_SRC (set_insn), 2);
423 map_srcreg = gen_rtx_REG (dst_mode, REGNO (srcreg));
424 map_srcreg2 = gen_rtx_REG (dst_mode, REGNO (srcreg2));
425 map_dstreg = gen_rtx_REG (dst_mode, REGNO (dstreg));
426 ifexpr = gen_rtx_IF_THEN_ELSE (dst_mode, cond, map_srcreg, map_srcreg2);
427 new_set = gen_rtx_SET (VOIDmode, map_dstreg, ifexpr);
429 if (validate_change (def_insn, &PATTERN (def_insn), new_set, true))
433 fprintf (dump_file, "Cond_Move Instruction's mode extended :\n");
434 print_rtl_single (dump_file, def_insn);
442 /* Function to get all the immediate definitions of an instruction.
443 The reaching definitions are desired for WHICH_REG used in
444 CURR_INSN. This function returns 0 if there was an error getting
445 a definition. Upon success, this function returns the number of
446 definitions and stores the definitions in DEST. */
449 get_defs (rtx curr_insn, rtx which_reg, VEC (rtx,heap) **dest)
451 df_ref reg_info, *defs;
452 struct df_link *def_chain;
455 defs = DF_INSN_USES (curr_insn);
461 if (GET_CODE (DF_REF_REG (reg_info)) == SUBREG)
463 if (REGNO (DF_REF_REG (reg_info)) == REGNO (which_reg))
468 gcc_assert (reg_info != NULL && defs != NULL);
469 def_chain = DF_REF_CHAIN (reg_info);
473 /* Problem getting some definition for this instruction. */
475 if (def_chain->ref == NULL)
477 if (DF_REF_INSN_INFO (def_chain->ref) == NULL)
479 def_chain = def_chain->next;
482 def_chain = DF_REF_CHAIN (reg_info);
489 VEC_safe_push (rtx, heap, *dest, DF_REF_INSN (def_chain->ref));
490 def_chain = def_chain->next;
496 /* rtx function to check if this SET insn, EXPR, is a conditional copy insn :
497 (set (reg a ) (IF_THEN_ELSE (cond) (reg b) (reg c)))
498 Called from is_insn_cond_copy. DATA stores the two registers on each
499 side of the condition. */
502 is_this_a_cmove (rtx expr, void *data)
504 /* Check for conditional (if-then-else) copy. */
506 if (GET_CODE (expr) == SET
507 && GET_CODE (SET_DEST (expr)) == REG
508 && GET_CODE (SET_SRC (expr)) == IF_THEN_ELSE
509 && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG
510 && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG)
512 ((rtx *)data)[0] = XEXP (SET_SRC (expr), 1);
513 ((rtx *)data)[1] = XEXP (SET_SRC (expr), 2);
519 /* This returns 1 if it found
520 (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
521 in the DEF_INSN pattern. It stores the x1 and x2 in COPY_REG_1
525 is_insn_cond_copy (rtx def_insn, rtx *copy_reg_1, rtx *copy_reg_2)
531 srcreg[0] = NULL_RTX;
532 srcreg[1] = NULL_RTX;
534 set_expr = single_set (def_insn);
536 if (set_expr == NULL_RTX)
539 type = is_this_a_cmove (set_expr, (void *) srcreg);
543 *copy_reg_1 = srcreg[0];
544 *copy_reg_2 = srcreg[1];
551 /* Reaching Definitions of the extended register could be conditional copies
552 or regular definitions. This function separates the two types into two
553 lists, DEFS_LIST and COPIES_LIST. This is necessary because, if a reaching
554 definition is a conditional copy, combining the extend with this definition
555 is wrong. Conditional copies are merged by transitively merging its
556 definitions. The defs_list is populated with all the reaching definitions
557 of the extension instruction (EXTEND_INSN) which must be merged with an
558 extension. The copies_list contains all the conditional moves that will
559 later be extended into a wider mode conditonal move if all the merges are
560 successful. The function returns false when there is a failure in getting
561 some definitions, like that of parameters. It returns 1 upon success, 0
562 upon failure and 2 when all definitions of the EXTEND_INSN were merged
566 make_defs_and_copies_lists (rtx extend_insn, rtx set_pat,
567 VEC (rtx,heap) **defs_list,
568 VEC (rtx,heap) **copies_list)
570 bool *is_insn_visited;
571 VEC (rtx,heap) *work_list;
572 rtx srcreg, copy_reg_1, copy_reg_2;
579 srcreg = XEXP (SET_SRC (set_pat), 0);
580 work_list = VEC_alloc (rtx, heap, 8);
582 /* Initialize the Work List */
583 n_worklist = get_defs (extend_insn, srcreg, &work_list);
587 VEC_free (rtx, heap, work_list);
588 /* The number of defs being equal to zero can only imply that all of its
589 definitions have been previously merged. */
593 is_insn_visited = XNEWVEC (bool, max_insn_uid);
595 for (i = 0; i < max_insn_uid; i++)
596 is_insn_visited[i] = false;
599 /* Perform transitive closure for conditional copies. */
600 while (n_worklist > vec_index)
602 def_insn = VEC_index (rtx, work_list, vec_index);
603 gcc_assert (INSN_UID (def_insn) < max_insn_uid);
605 if (is_insn_visited[INSN_UID (def_insn)])
611 is_insn_visited[INSN_UID (def_insn)] = true;
612 copy_reg_1 = copy_reg_2 = NULL_RTX;
613 is_copy = is_insn_cond_copy (def_insn, ©_reg_1, ©_reg_2);
616 gcc_assert (copy_reg_1 && copy_reg_2);
618 /* Push it into the copy list first. */
620 VEC_safe_push (rtx, heap, *copies_list, def_insn);
622 /* Perform transitive closure here */
624 n_defs = get_defs (def_insn, copy_reg_1, &work_list);
628 VEC_free (rtx, heap, work_list);
629 XDELETEVEC (is_insn_visited);
632 n_worklist += n_defs;
634 n_defs = get_defs (def_insn, copy_reg_2, &work_list);
637 VEC_free (rtx, heap, work_list);
638 XDELETEVEC (is_insn_visited);
641 n_worklist += n_defs;
645 VEC_safe_push (rtx, heap, *defs_list, def_insn);
650 VEC_free (rtx, heap, work_list);
651 XDELETEVEC (is_insn_visited);
655 /* Merge the DEF_INSN with an extension. Calls combine_set_extend
656 on the SET pattern. */
659 merge_def_and_ext (ext_cand_ref cand, rtx def_insn)
661 enum machine_mode ext_src_mode;
667 ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0));
668 code = GET_CODE (PATTERN (def_insn));
671 if (code == PARALLEL)
673 for (i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++)
675 s_expr = XVECEXP (PATTERN (def_insn), 0, i);
676 if (GET_CODE (s_expr) != SET)
680 sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i);
683 /* PARALLEL with multiple SETs. */
688 else if (code == SET)
689 sub_rtx = &PATTERN (def_insn);
692 /* It is not a PARALLEL or a SET, what could it be ? */
696 gcc_assert (sub_rtx != NULL);
698 if (GET_CODE (SET_DEST (*sub_rtx)) == REG
699 && GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode)
701 return combine_set_extend (cand, def_insn, sub_rtx);
707 /* This function goes through all reaching defs of the source
708 of the candidate for elimination (CAND) and tries to combine
709 the extension with the definition instruction. The changes
710 are made as a group so that even if one definition cannot be
711 merged, all reaching definitions end up not being merged.
712 When a conditional copy is encountered, merging is attempted
713 transitively on its definitions. It returns true upon success
714 and false upon failure. */
717 combine_reaching_defs (ext_cand_ref cand, rtx set_pat)
720 bool merge_successful = true;
725 /* To store the definitions that have been merged. */
727 VEC (rtx, heap) *defs_list, *copies_list, *vec;
728 enum insn_merge_code merge_code;
730 defs_list = VEC_alloc (rtx, heap, 8);
731 copies_list = VEC_alloc (rtx, heap, 8);
733 outcome = make_defs_and_copies_lists (cand->insn,
734 set_pat, &defs_list, &copies_list);
736 /* outcome == 2 implies that all the definitions for this extension were
737 merged while previously when handling other extension. */
741 VEC_free (rtx, heap, defs_list);
742 VEC_free (rtx, heap, copies_list);
744 fprintf (dump_file, "All definitions have been merged previously.\n");
750 VEC_free (rtx, heap, defs_list);
751 VEC_free (rtx, heap, copies_list);
755 merge_successful = true;
757 /* Go through the defs vector and try to merge all the definitions
760 vec = VEC_alloc (rtx, heap, 8);
761 FOR_EACH_VEC_ELT (rtx, defs_list, defs_ix, def_insn)
763 merge_code = get_insn_status (def_insn);
764 gcc_assert (merge_code == MERGE_NOT_ATTEMPTED);
766 if (merge_def_and_ext (cand, def_insn))
767 VEC_safe_push (rtx, heap, vec, def_insn);
770 merge_successful = false;
775 /* Now go through the conditional copies vector and try to merge all
776 the copies in this vector. */
778 if (merge_successful)
780 FOR_EACH_VEC_ELT (rtx, copies_list, i, def_insn)
782 if (transform_ifelse (cand, def_insn))
784 VEC_safe_push (rtx, heap, vec, def_insn);
788 merge_successful = false;
794 if (merge_successful)
796 /* Commit the changes here if possible */
797 /* XXX : Now, it is an all or nothing scenario. Even if one definition
798 cannot be merged we totally fail. In future, allow extensions to
799 be partially eliminated along those paths where the definitions could
802 if (apply_change_group ())
805 fprintf (dump_file, "All merges were successful ....\n");
807 FOR_EACH_VEC_ELT (rtx, vec, i, def_insn)
809 set_insn_status (def_insn, MERGE_SUCCESS);
812 VEC_free (rtx, heap, vec);
813 VEC_free (rtx, heap, defs_list);
814 VEC_free (rtx, heap, copies_list);
819 /* Changes need not be cancelled explicitly as apply_change_group
820 does it. Print list of definitions in the dump_file for debug
821 purposes. This extension cannot be deleted. */
825 FOR_EACH_VEC_ELT (rtx, vec, i, def_insn)
827 fprintf (dump_file, " Ummergable definitions : \n");
828 print_rtl_single (dump_file, def_insn);
835 /* Cancel any changes that have been made so far. */
839 VEC_free (rtx, heap, vec);
840 VEC_free (rtx, heap, defs_list);
841 VEC_free (rtx, heap, copies_list);
845 /* Carry information about extensions while walking the RTL. */
849 /* The insn where the extension is. */
852 /* The list of candidates. */
853 VEC (ext_cand, heap) *insn_list;
857 add_ext_candidate (VEC (ext_cand, heap) **exts,
858 rtx insn, const_rtx expr)
860 ext_cand_ref ec = VEC_safe_push (ext_cand, heap, *exts, NULL);
865 /* Add an extension pattern that could be eliminated. This is called via
866 note_stores from find_removable_extensions. */
869 add_removable_extension (rtx x ATTRIBUTE_UNUSED, const_rtx expr, void *data)
871 struct extend_info *rei = (struct extend_info *)data;
874 /* We are looking for SET (REG N) (EXTEND (REG N)). */
875 if (GET_CODE (expr) != SET)
878 src = SET_SRC (expr);
879 dest = SET_DEST (expr);
882 && (GET_CODE (src) == ZERO_EXTEND || GET_CODE (src) == SIGN_EXTEND)
883 && REG_P (XEXP (src, 0))
884 && REGNO (dest) == REGNO (XEXP (src, 0)))
886 if (get_defs (rei->insn, XEXP (src, 0), NULL))
887 add_ext_candidate (&rei->insn_list, rei->insn, expr);
890 fprintf (dump_file, "Cannot eliminate extension: \n");
891 print_rtl_single (dump_file, rei->insn);
892 fprintf (dump_file, "No defs. Could be extending parameters.\n");
897 /* Traverse the instruction stream looking for extensions and return the
898 list of candidates. */
900 static VEC (ext_cand, heap)*
901 find_removable_extensions (void)
903 struct extend_info rei;
907 rei.insn_list = VEC_alloc (ext_cand, heap, 8);
910 FOR_BB_INSNS (bb, insn)
912 if (!NONDEBUG_INSN_P (insn))
916 note_stores (PATTERN (insn), add_removable_extension, &rei);
919 return rei.insn_list;
922 /* This is the main function that checks the insn stream for redundant
923 extensions and tries to remove them if possible. */
926 find_and_remove_re (void)
928 ext_cand_ref curr_cand;
929 rtx curr_insn = NULL_RTX;
932 long num_realized = 0;
933 long num_re_opportunities = 0;
934 VEC (ext_cand, heap) *reinsn_list;
935 VEC (rtx, heap) *reinsn_del_list;
937 /* Construct DU chain to get all reaching definitions of each
938 extension instruction. */
940 df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
943 max_insn_uid = get_max_uid ();
945 is_insn_merge_attempted
946 = XNEWVEC (enum insn_merge_code,
947 sizeof (enum insn_merge_code) * max_insn_uid);
949 for (i = 0; i < max_insn_uid; i++)
950 is_insn_merge_attempted[i] = MERGE_NOT_ATTEMPTED;
952 num_re_opportunities = num_realized = 0;
954 reinsn_del_list = VEC_alloc (rtx, heap, 4);
956 reinsn_list = find_removable_extensions ();
958 FOR_EACH_VEC_ELT (ext_cand, reinsn_list, ix, curr_cand)
960 num_re_opportunities++;
961 /* Try to combine the extension with the definition here. */
965 fprintf (dump_file, "Trying to eliminate extension : \n");
966 print_rtl_single (dump_file, curr_insn);
969 if (combine_reaching_defs (curr_cand, PATTERN (curr_cand->insn)))
972 fprintf (dump_file, "Eliminated the extension...\n");
974 VEC_safe_push (rtx, heap, reinsn_del_list, curr_cand->insn);
978 /* Delete all useless extensions here in one sweep. */
979 FOR_EACH_VEC_ELT (rtx, reinsn_del_list, ix, curr_insn)
980 delete_insn (curr_insn);
982 free (is_insn_merge_attempted);
983 VEC_free (ext_cand, heap, reinsn_list);
984 VEC_free (rtx, heap, reinsn_del_list);
986 if (dump_file && num_re_opportunities > 0)
987 fprintf (dump_file, "\n %s : num_re_opportunities = %ld "
988 "num_realized = %ld \n",
989 current_function_name (),
990 num_re_opportunities, num_realized);
992 df_finish_pass (false);
996 /* Find and remove redundant extensions. */
999 rest_of_handle_ree (void)
1001 timevar_push (TV_REE);
1002 find_and_remove_re ();
1003 timevar_pop (TV_REE);
1007 /* Run REE pass when flag_ree is set at optimization level > 0. */
1010 gate_handle_ree (void)
1012 return (optimize > 0 && flag_ree);
1015 struct rtl_opt_pass pass_ree =
1020 gate_handle_ree, /* gate */
1021 rest_of_handle_ree, /* execute */
1024 0, /* static_pass_number */
1026 0, /* properties_required */
1027 0, /* properties_provided */
1028 0, /* properties_destroyed */
1029 0, /* todo_flags_start */
1031 TODO_verify_rtl_sharing, /* todo_flags_finish */