PR target/61794
[official-gcc.git] / gcc / ree.c
blob856745f5a9f02f32b73b7e2b9b29b965bd1a89ba
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
13 version.
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
18 for more details.
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 :
26 --------------------
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
65 not delete it.
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 :
87 ---------------------
88 For this program :
89 **********************************************
90 bad_code.c
92 int mask[1000];
94 int foo(unsigned x)
96 if (x < 10)
97 x = x * 45;
98 else
99 x = x * 78;
100 return mask[x];
102 **********************************************
104 $ gcc -O2 bad_code.c
105 ........
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
110 400326: c3 retq
111 ......
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
116 400341: c3 retq
118 $ gcc -O2 -free bad_code.c
119 ......
120 400315: 6b ff 4e imul $0x4e,%edi,%edi
121 400318: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax
122 40031f: c3 retq
123 400320: 6b ff 2d imul $0x2d,%edi,%edi
124 400323: 8b 04 bd 40 19 40 00 mov 0x401940(,%rdi,4),%eax
125 40032a: c3 retq
127 Motivating Example II :
128 ---------------------
130 Here is an example with a conditional move.
132 For this program :
133 **********************************************
135 unsigned long long foo(unsigned x , unsigned y)
137 unsigned z;
138 if (x > 100)
139 z = x + y;
140 else
141 z = x - y;
142 return (unsigned long long)(z);
145 $ gcc -O2 bad_code.c
146 ............
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
153 40036f: c3 retq
155 $ gcc -O2 -free bad_code.c
156 .............
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
163 400370: c3 retq
165 Motivating Example III :
166 ---------------------
168 Here is an example with a type cast.
170 For this program :
171 **********************************************
173 void test(int size, unsigned char *in, unsigned char *out)
175 int i;
176 unsigned char xr, xg, xy=0;
178 for (i = 0; i < size; i++) {
179 xr = *in++;
180 xg = *in++;
181 xy = (unsigned char) ((19595*xr + 38470*xg) >> 16);
182 *out++ = xy;
186 $ gcc -O2 bad_code.c
187 ............
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
197 .............
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
204 Usefulness :
205 ----------
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
215 gain 1%. */
218 #include "config.h"
219 #include "system.h"
220 #include "coretypes.h"
221 #include "tm.h"
222 #include "rtl.h"
223 #include "tree.h"
224 #include "tm_p.h"
225 #include "flags.h"
226 #include "regs.h"
227 #include "hard-reg-set.h"
228 #include "basic-block.h"
229 #include "insn-config.h"
230 #include "function.h"
231 #include "expr.h"
232 #include "insn-attr.h"
233 #include "recog.h"
234 #include "diagnostic-core.h"
235 #include "target.h"
236 #include "optabs.h"
237 #include "insn-codes.h"
238 #include "rtlhooks-def.h"
239 #include "params.h"
240 #include "tree-pass.h"
241 #include "df.h"
242 #include "cgraph.h"
244 /* This structure represents a candidate for elimination. */
246 typedef struct ext_cand
248 /* The expression. */
249 const_rtx expr;
251 /* The kind of extension. */
252 enum rtx_code code;
254 /* The destination mode. */
255 enum machine_mode mode;
257 /* The instruction where it lives. */
258 rtx insn;
259 } ext_cand;
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.
271 Original :
272 (set (reg a) (expression))
274 Transform :
275 (set (reg a) (any_extend (expression)))
277 Special Cases :
278 If the expression is a constant or another extension, then directly
279 assign it to the register. */
281 static bool
282 combine_set_extension (ext_cand *cand, rtx curr_insn, rtx *orig_set)
284 rtx orig_src = SET_SRC (*orig_set);
285 rtx new_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. */
292 rtx new_reg;
293 bool copy_needed
294 = (REGNO (SET_DEST (cand_pat)) != REGNO (XEXP (SET_SRC (cand_pat), 0)));
295 if (copy_needed)
296 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (cand_pat)));
297 else
298 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (*orig_set)));
300 #if 0
301 /* Rethinking test. Temporarily disabled. */
302 /* We're going to be widening the result of DEF_INSN, ensure that doing so
303 doesn't change the number of hard registers needed for the result. */
304 if (HARD_REGNO_NREGS (REGNO (new_reg), cand->mode)
305 != HARD_REGNO_NREGS (REGNO (SET_DEST (*orig_set)),
306 GET_MODE (SET_DEST (*orig_set))))
307 return false;
308 #endif
310 /* Merge constants by directly moving the constant into the register under
311 some conditions. Recall that RTL constants are sign-extended. */
312 if (GET_CODE (orig_src) == CONST_INT
313 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (cand->mode))
315 if (INTVAL (orig_src) >= 0 || cand->code == SIGN_EXTEND)
316 new_set = gen_rtx_SET (VOIDmode, new_reg, orig_src);
317 else
319 /* Zero-extend the negative constant by masking out the bits outside
320 the source mode. */
321 enum machine_mode src_mode = GET_MODE (SET_DEST (*orig_set));
322 rtx new_const_int
323 = gen_int_mode (INTVAL (orig_src) & GET_MODE_MASK (src_mode),
324 GET_MODE (new_reg));
325 new_set = gen_rtx_SET (VOIDmode, new_reg, new_const_int);
328 else if (GET_MODE (orig_src) == VOIDmode)
330 /* This is mostly due to a call insn that should not be optimized. */
331 return false;
333 else if (GET_CODE (orig_src) == cand->code)
335 /* Here is a sequence of two extensions. Try to merge them. */
336 rtx temp_extension
337 = gen_rtx_fmt_e (cand->code, cand->mode, XEXP (orig_src, 0));
338 rtx simplified_temp_extension = simplify_rtx (temp_extension);
339 if (simplified_temp_extension)
340 temp_extension = simplified_temp_extension;
341 new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension);
343 else if (GET_CODE (orig_src) == IF_THEN_ELSE)
345 /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
346 in general, IF_THEN_ELSE should not be combined. */
347 return false;
349 else
351 /* This is the normal case. */
352 rtx temp_extension
353 = gen_rtx_fmt_e (cand->code, cand->mode, orig_src);
354 rtx simplified_temp_extension = simplify_rtx (temp_extension);
355 if (simplified_temp_extension)
356 temp_extension = simplified_temp_extension;
357 new_set = gen_rtx_SET (VOIDmode, new_reg, temp_extension);
360 /* This change is a part of a group of changes. Hence,
361 validate_change will not try to commit the change. */
362 if (validate_change (curr_insn, orig_set, new_set, true))
364 if (dump_file)
366 fprintf (dump_file,
367 "Tentatively merged extension with definition %s:\n",
368 (copy_needed) ? "(copy needed)" : "");
369 print_rtl_single (dump_file, curr_insn);
371 return true;
374 return false;
377 /* Treat if_then_else insns, where the operands of both branches
378 are registers, as copies. For instance,
379 Original :
380 (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
381 Transformed :
382 (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
383 DEF_INSN is the if_then_else insn. */
385 static bool
386 transform_ifelse (ext_cand *cand, rtx def_insn)
388 rtx set_insn = PATTERN (def_insn);
389 rtx srcreg, dstreg, srcreg2;
390 rtx map_srcreg, map_dstreg, map_srcreg2;
391 rtx ifexpr;
392 rtx cond;
393 rtx new_set;
395 gcc_assert (GET_CODE (set_insn) == SET);
397 cond = XEXP (SET_SRC (set_insn), 0);
398 dstreg = SET_DEST (set_insn);
399 srcreg = XEXP (SET_SRC (set_insn), 1);
400 srcreg2 = XEXP (SET_SRC (set_insn), 2);
401 /* If the conditional move already has the right or wider mode,
402 there is nothing to do. */
403 if (GET_MODE_SIZE (GET_MODE (dstreg)) >= GET_MODE_SIZE (cand->mode))
404 return true;
406 map_srcreg = gen_rtx_REG (cand->mode, REGNO (srcreg));
407 map_srcreg2 = gen_rtx_REG (cand->mode, REGNO (srcreg2));
408 map_dstreg = gen_rtx_REG (cand->mode, REGNO (dstreg));
409 ifexpr = gen_rtx_IF_THEN_ELSE (cand->mode, cond, map_srcreg, map_srcreg2);
410 new_set = gen_rtx_SET (VOIDmode, map_dstreg, ifexpr);
412 if (validate_change (def_insn, &PATTERN (def_insn), new_set, true))
414 if (dump_file)
416 fprintf (dump_file,
417 "Mode of conditional move instruction extended:\n");
418 print_rtl_single (dump_file, def_insn);
420 return true;
423 return false;
426 /* Get all the reaching definitions of an instruction. The definitions are
427 desired for REG used in INSN. Return the definition list or NULL if a
428 definition is missing. If DEST is non-NULL, additionally push the INSN
429 of the definitions onto DEST. */
431 static struct df_link *
432 get_defs (rtx insn, rtx reg, vec<rtx> *dest)
434 df_ref use;
435 struct df_link *ref_chain, *ref_link;
437 FOR_EACH_INSN_USE (use, insn)
439 if (GET_CODE (DF_REF_REG (use)) == SUBREG)
440 return NULL;
441 if (REGNO (DF_REF_REG (use)) == REGNO (reg))
442 break;
445 gcc_assert (use != NULL);
447 ref_chain = DF_REF_CHAIN (use);
449 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
451 /* Problem getting some definition for this instruction. */
452 if (ref_link->ref == NULL)
453 return NULL;
454 if (DF_REF_INSN_INFO (ref_link->ref) == NULL)
455 return NULL;
458 if (dest)
459 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
460 dest->safe_push (DF_REF_INSN (ref_link->ref));
462 return ref_chain;
465 /* Return true if INSN is
466 (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
467 and store x1 and x2 in REG_1 and REG_2. */
469 static bool
470 is_cond_copy_insn (rtx insn, rtx *reg1, rtx *reg2)
472 rtx expr = single_set (insn);
474 if (expr != NULL_RTX
475 && GET_CODE (expr) == SET
476 && GET_CODE (SET_DEST (expr)) == REG
477 && GET_CODE (SET_SRC (expr)) == IF_THEN_ELSE
478 && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG
479 && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG)
481 *reg1 = XEXP (SET_SRC (expr), 1);
482 *reg2 = XEXP (SET_SRC (expr), 2);
483 return true;
486 return false;
489 enum ext_modified_kind
491 /* The insn hasn't been modified by ree pass yet. */
492 EXT_MODIFIED_NONE,
493 /* Changed into zero extension. */
494 EXT_MODIFIED_ZEXT,
495 /* Changed into sign extension. */
496 EXT_MODIFIED_SEXT
499 struct ATTRIBUTE_PACKED ext_modified
501 /* Mode from which ree has zero or sign extended the destination. */
502 ENUM_BITFIELD(machine_mode) mode : 8;
504 /* Kind of modification of the insn. */
505 ENUM_BITFIELD(ext_modified_kind) kind : 2;
507 unsigned int do_not_reextend : 1;
509 /* True if the insn is scheduled to be deleted. */
510 unsigned int deleted : 1;
513 /* Vectors used by combine_reaching_defs and its helpers. */
514 typedef struct ext_state
516 /* In order to avoid constant alloc/free, we keep these
517 4 vectors live through the entire find_and_remove_re and just
518 truncate them each time. */
519 vec<rtx> defs_list;
520 vec<rtx> copies_list;
521 vec<rtx> modified_list;
522 vec<rtx> work_list;
524 /* For instructions that have been successfully modified, this is
525 the original mode from which the insn is extending and
526 kind of extension. */
527 struct ext_modified *modified;
528 } ext_state;
530 /* Reaching Definitions of the extended register could be conditional copies
531 or regular definitions. This function separates the two types into two
532 lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because,
533 if a reaching definition is a conditional copy, merging the extension with
534 this definition is wrong. Conditional copies are merged by transitively
535 merging their definitions. The defs_list is populated with all the reaching
536 definitions of the extension instruction (EXTEND_INSN) which must be merged
537 with an extension. The copies_list contains all the conditional moves that
538 will later be extended into a wider mode conditional move if all the merges
539 are successful. The function returns false upon failure, true upon
540 success. */
542 static bool
543 make_defs_and_copies_lists (rtx extend_insn, const_rtx set_pat,
544 ext_state *state)
546 rtx src_reg = XEXP (SET_SRC (set_pat), 0);
547 bool *is_insn_visited;
548 bool ret = true;
550 state->work_list.truncate (0);
552 /* Initialize the work list. */
553 if (!get_defs (extend_insn, src_reg, &state->work_list))
554 gcc_unreachable ();
556 is_insn_visited = XCNEWVEC (bool, max_insn_uid);
558 /* Perform transitive closure for conditional copies. */
559 while (!state->work_list.is_empty ())
561 rtx def_insn = state->work_list.pop ();
562 rtx reg1, reg2;
564 gcc_assert (INSN_UID (def_insn) < max_insn_uid);
566 if (is_insn_visited[INSN_UID (def_insn)])
567 continue;
568 is_insn_visited[INSN_UID (def_insn)] = true;
570 if (is_cond_copy_insn (def_insn, &reg1, &reg2))
572 /* Push it onto the copy list first. */
573 state->copies_list.safe_push (def_insn);
575 /* Now perform the transitive closure. */
576 if (!get_defs (def_insn, reg1, &state->work_list)
577 || !get_defs (def_insn, reg2, &state->work_list))
579 ret = false;
580 break;
583 else
584 state->defs_list.safe_push (def_insn);
587 XDELETEVEC (is_insn_visited);
589 return ret;
592 /* If DEF_INSN has single SET expression, possibly buried inside
593 a PARALLEL, return the address of the SET expression, else
594 return NULL. This is similar to single_set, except that
595 single_set allows multiple SETs when all but one is dead. */
596 static rtx *
597 get_sub_rtx (rtx def_insn)
599 enum rtx_code code = GET_CODE (PATTERN (def_insn));
600 rtx *sub_rtx = NULL;
602 if (code == PARALLEL)
604 for (int i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++)
606 rtx s_expr = XVECEXP (PATTERN (def_insn), 0, i);
607 if (GET_CODE (s_expr) != SET)
608 continue;
610 if (sub_rtx == NULL)
611 sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i);
612 else
614 /* PARALLEL with multiple SETs. */
615 return NULL;
619 else if (code == SET)
620 sub_rtx = &PATTERN (def_insn);
621 else
623 /* It is not a PARALLEL or a SET, what could it be ? */
624 return NULL;
627 gcc_assert (sub_rtx != NULL);
628 return sub_rtx;
631 /* Merge the DEF_INSN with an extension. Calls combine_set_extension
632 on the SET pattern. */
634 static bool
635 merge_def_and_ext (ext_cand *cand, rtx def_insn, ext_state *state)
637 enum machine_mode ext_src_mode;
638 rtx *sub_rtx;
640 ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0));
641 sub_rtx = get_sub_rtx (def_insn);
643 if (sub_rtx == NULL)
644 return false;
646 if (REG_P (SET_DEST (*sub_rtx))
647 && (GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode
648 || ((state->modified[INSN_UID (def_insn)].kind
649 == (cand->code == ZERO_EXTEND
650 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT))
651 && state->modified[INSN_UID (def_insn)].mode
652 == ext_src_mode)))
654 if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx)))
655 >= GET_MODE_SIZE (cand->mode))
656 return true;
657 /* If def_insn is already scheduled to be deleted, don't attempt
658 to modify it. */
659 if (state->modified[INSN_UID (def_insn)].deleted)
660 return false;
661 if (combine_set_extension (cand, def_insn, sub_rtx))
663 if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE)
664 state->modified[INSN_UID (def_insn)].mode = ext_src_mode;
665 return true;
669 return false;
672 /* Given SRC, which should be one or more extensions of a REG, strip
673 away the extensions and return the REG. */
675 static inline rtx
676 get_extended_src_reg (rtx src)
678 while (GET_CODE (src) == SIGN_EXTEND || GET_CODE (src) == ZERO_EXTEND)
679 src = XEXP (src, 0);
680 gcc_assert (REG_P (src));
681 return src;
684 /* This function goes through all reaching defs of the source
685 of the candidate for elimination (CAND) and tries to combine
686 the extension with the definition instruction. The changes
687 are made as a group so that even if one definition cannot be
688 merged, all reaching definitions end up not being merged.
689 When a conditional copy is encountered, merging is attempted
690 transitively on its definitions. It returns true upon success
691 and false upon failure. */
693 static bool
694 combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state)
696 rtx def_insn;
697 bool merge_successful = true;
698 int i;
699 int defs_ix;
700 bool outcome;
702 state->defs_list.truncate (0);
703 state->copies_list.truncate (0);
705 outcome = make_defs_and_copies_lists (cand->insn, set_pat, state);
707 if (!outcome)
708 return false;
710 /* If the destination operand of the extension is a different
711 register than the source operand, then additional restrictions
712 are needed. Note we have to handle cases where we have nested
713 extensions in the source operand. */
714 bool copy_needed
715 = (REGNO (SET_DEST (PATTERN (cand->insn)))
716 != REGNO (get_extended_src_reg (SET_SRC (PATTERN (cand->insn)))));
717 if (copy_needed)
719 /* In theory we could handle more than one reaching def, it
720 just makes the code to update the insn stream more complex. */
721 if (state->defs_list.length () != 1)
722 return false;
724 /* We require the candidate not already be modified. It may,
725 for example have been changed from a (sign_extend (reg))
726 into (zero_extend (sign_extend (reg))).
728 Handling that case shouldn't be terribly difficult, but the code
729 here and the code to emit copies would need auditing. Until
730 we see a need, this is the safe thing to do. */
731 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE)
732 return false;
734 /* Transformation of
735 (set (reg1) (expression))
736 (set (reg2) (any_extend (reg1)))
737 into
738 (set (reg2) (any_extend (expression)))
739 (set (reg1) (reg2))
740 is only valid for scalar integral modes, as it relies on the low
741 subreg of reg1 to have the value of (expression), which is not true
742 e.g. for vector modes. */
743 if (!SCALAR_INT_MODE_P (GET_MODE (SET_DEST (PATTERN (cand->insn)))))
744 return false;
746 /* There's only one reaching def. */
747 rtx def_insn = state->defs_list[0];
749 /* The defining statement must not have been modified either. */
750 if (state->modified[INSN_UID (def_insn)].kind != EXT_MODIFIED_NONE)
751 return false;
753 /* The defining statement and candidate insn must be in the same block.
754 This is merely to keep the test for safety and updating the insn
755 stream simple. Also ensure that within the block the candidate
756 follows the defining insn. */
757 if (BLOCK_FOR_INSN (cand->insn) != BLOCK_FOR_INSN (def_insn)
758 || DF_INSN_LUID (def_insn) > DF_INSN_LUID (cand->insn))
759 return false;
761 /* If there is an overlap between the destination of DEF_INSN and
762 CAND->insn, then this transformation is not safe. Note we have
763 to test in the widened mode. */
764 rtx *dest_sub_rtx = get_sub_rtx (def_insn);
765 if (dest_sub_rtx == NULL
766 || !REG_P (SET_DEST (*dest_sub_rtx)))
767 return false;
769 rtx tmp_reg = gen_rtx_REG (GET_MODE (SET_DEST (PATTERN (cand->insn))),
770 REGNO (SET_DEST (*dest_sub_rtx)));
771 if (reg_overlap_mentioned_p (tmp_reg, SET_DEST (PATTERN (cand->insn))))
772 return false;
774 /* The destination register of the extension insn must not be
775 used or set between the def_insn and cand->insn exclusive. */
776 if (reg_used_between_p (SET_DEST (PATTERN (cand->insn)),
777 def_insn, cand->insn)
778 || reg_set_between_p (SET_DEST (PATTERN (cand->insn)),
779 def_insn, cand->insn))
780 return false;
782 /* We must be able to copy between the two registers. Generate,
783 recognize and verify constraints of the copy. Also fail if this
784 generated more than one insn.
786 This generates garbage since we throw away the insn when we're
787 done, only to recreate it later if this test was successful.
789 Make sure to get the mode from the extension (cand->insn). This
790 is different than in the code to emit the copy as we have not
791 modified the defining insn yet. */
792 start_sequence ();
793 rtx pat = PATTERN (cand->insn);
794 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (pat)),
795 REGNO (XEXP (SET_SRC (pat), 0)));
796 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (pat)),
797 REGNO (SET_DEST (pat)));
798 emit_move_insn (new_dst, new_src);
800 rtx insn = get_insns();
801 end_sequence ();
802 if (NEXT_INSN (insn))
803 return false;
804 if (recog_memoized (insn) == -1)
805 return false;
806 extract_insn (insn);
807 if (!constrain_operands (1))
808 return false;
812 /* If cand->insn has been already modified, update cand->mode to a wider
813 mode if possible, or punt. */
814 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE)
816 enum machine_mode mode;
817 rtx set;
819 if (state->modified[INSN_UID (cand->insn)].kind
820 != (cand->code == ZERO_EXTEND
821 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT)
822 || state->modified[INSN_UID (cand->insn)].mode != cand->mode
823 || (set = single_set (cand->insn)) == NULL_RTX)
824 return false;
825 mode = GET_MODE (SET_DEST (set));
826 gcc_assert (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (cand->mode));
827 cand->mode = mode;
830 merge_successful = true;
832 /* Go through the defs vector and try to merge all the definitions
833 in this vector. */
834 state->modified_list.truncate (0);
835 FOR_EACH_VEC_ELT (state->defs_list, defs_ix, def_insn)
837 if (merge_def_and_ext (cand, def_insn, state))
838 state->modified_list.safe_push (def_insn);
839 else
841 merge_successful = false;
842 break;
846 /* Now go through the conditional copies vector and try to merge all
847 the copies in this vector. */
848 if (merge_successful)
850 FOR_EACH_VEC_ELT (state->copies_list, i, def_insn)
852 if (transform_ifelse (cand, def_insn))
853 state->modified_list.safe_push (def_insn);
854 else
856 merge_successful = false;
857 break;
862 if (merge_successful)
864 /* Commit the changes here if possible
865 FIXME: It's an all-or-nothing scenario. Even if only one definition
866 cannot be merged, we entirely give up. In the future, we should allow
867 extensions to be partially eliminated along those paths where the
868 definitions could be merged. */
869 if (apply_change_group ())
871 if (dump_file)
872 fprintf (dump_file, "All merges were successful.\n");
874 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
876 ext_modified *modified = &state->modified[INSN_UID (def_insn)];
877 if (modified->kind == EXT_MODIFIED_NONE)
878 modified->kind = (cand->code == ZERO_EXTEND ? EXT_MODIFIED_ZEXT
879 : EXT_MODIFIED_SEXT);
881 if (copy_needed)
882 modified->do_not_reextend = 1;
884 return true;
886 else
888 /* Changes need not be cancelled explicitly as apply_change_group
889 does it. Print list of definitions in the dump_file for debug
890 purposes. This extension cannot be deleted. */
891 if (dump_file)
893 fprintf (dump_file,
894 "Merge cancelled, non-mergeable definitions:\n");
895 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
896 print_rtl_single (dump_file, def_insn);
900 else
902 /* Cancel any changes that have been made so far. */
903 cancel_changes (0);
906 return false;
909 /* Add an extension pattern that could be eliminated. */
911 static void
912 add_removable_extension (const_rtx expr, rtx insn,
913 vec<ext_cand> *insn_list,
914 unsigned *def_map)
916 enum rtx_code code;
917 enum machine_mode mode;
918 unsigned int idx;
919 rtx src, dest;
921 /* We are looking for SET (REG N) (ANY_EXTEND (REG N)). */
922 if (GET_CODE (expr) != SET)
923 return;
925 src = SET_SRC (expr);
926 code = GET_CODE (src);
927 dest = SET_DEST (expr);
928 mode = GET_MODE (dest);
930 if (REG_P (dest)
931 && (code == SIGN_EXTEND || code == ZERO_EXTEND)
932 && REG_P (XEXP (src, 0)))
934 struct df_link *defs, *def;
935 ext_cand *cand;
937 /* First, make sure we can get all the reaching definitions. */
938 defs = get_defs (insn, XEXP (src, 0), NULL);
939 if (!defs)
941 if (dump_file)
943 fprintf (dump_file, "Cannot eliminate extension:\n");
944 print_rtl_single (dump_file, insn);
945 fprintf (dump_file, " because of missing definition(s)\n");
947 return;
950 /* Second, make sure the reaching definitions don't feed another and
951 different extension. FIXME: this obviously can be improved. */
952 for (def = defs; def; def = def->next)
953 if ((idx = def_map[INSN_UID (DF_REF_INSN (def->ref))])
954 && (cand = &(*insn_list)[idx - 1])
955 && cand->code != code)
957 if (dump_file)
959 fprintf (dump_file, "Cannot eliminate extension:\n");
960 print_rtl_single (dump_file, insn);
961 fprintf (dump_file, " because of other extension\n");
963 return;
966 /* Then add the candidate to the list and insert the reaching definitions
967 into the definition map. */
968 ext_cand e = {expr, code, mode, insn};
969 insn_list->safe_push (e);
970 idx = insn_list->length ();
972 for (def = defs; def; def = def->next)
973 def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx;
977 /* Traverse the instruction stream looking for extensions and return the
978 list of candidates. */
980 static vec<ext_cand>
981 find_removable_extensions (void)
983 vec<ext_cand> insn_list = vNULL;
984 basic_block bb;
985 rtx insn, set;
986 unsigned *def_map = XCNEWVEC (unsigned, max_insn_uid);
988 FOR_EACH_BB_FN (bb, cfun)
989 FOR_BB_INSNS (bb, insn)
991 if (!NONDEBUG_INSN_P (insn))
992 continue;
994 set = single_set (insn);
995 if (set == NULL_RTX)
996 continue;
997 add_removable_extension (set, insn, &insn_list, def_map);
1000 XDELETEVEC (def_map);
1002 return insn_list;
1005 /* This is the main function that checks the insn stream for redundant
1006 extensions and tries to remove them if possible. */
1008 static void
1009 find_and_remove_re (void)
1011 ext_cand *curr_cand;
1012 rtx curr_insn = NULL_RTX;
1013 int num_re_opportunities = 0, num_realized = 0, i;
1014 vec<ext_cand> reinsn_list;
1015 auto_vec<rtx> reinsn_del_list;
1016 auto_vec<rtx> reinsn_copy_list;
1017 ext_state state;
1019 /* Construct DU chain to get all reaching definitions of each
1020 extension instruction. */
1021 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
1022 df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
1023 df_analyze ();
1024 df_set_flags (DF_DEFER_INSN_RESCAN);
1026 max_insn_uid = get_max_uid ();
1027 reinsn_list = find_removable_extensions ();
1028 state.defs_list.create (0);
1029 state.copies_list.create (0);
1030 state.modified_list.create (0);
1031 state.work_list.create (0);
1032 if (reinsn_list.is_empty ())
1033 state.modified = NULL;
1034 else
1035 state.modified = XCNEWVEC (struct ext_modified, max_insn_uid);
1037 FOR_EACH_VEC_ELT (reinsn_list, i, curr_cand)
1039 num_re_opportunities++;
1041 /* Try to combine the extension with the definition. */
1042 if (dump_file)
1044 fprintf (dump_file, "Trying to eliminate extension:\n");
1045 print_rtl_single (dump_file, curr_cand->insn);
1048 if (combine_reaching_defs (curr_cand, curr_cand->expr, &state))
1050 if (dump_file)
1051 fprintf (dump_file, "Eliminated the extension.\n");
1052 num_realized++;
1053 /* If the RHS of the current candidate is not (extend (reg)), then
1054 we do not allow the optimization of extensions where
1055 the source and destination registers do not match. Thus
1056 checking REG_P here is correct. */
1057 if (REG_P (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0))
1058 && (REGNO (SET_DEST (PATTERN (curr_cand->insn)))
1059 != REGNO (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0))))
1061 reinsn_copy_list.safe_push (curr_cand->insn);
1062 reinsn_copy_list.safe_push (state.defs_list[0]);
1064 reinsn_del_list.safe_push (curr_cand->insn);
1065 state.modified[INSN_UID (curr_cand->insn)].deleted = 1;
1069 /* The copy list contains pairs of insns which describe copies we
1070 need to insert into the INSN stream.
1072 The first insn in each pair is the extension insn, from which
1073 we derive the source and destination of the copy.
1075 The second insn in each pair is the memory reference where the
1076 extension will ultimately happen. We emit the new copy
1077 immediately after this insn.
1079 It may first appear that the arguments for the copy are reversed.
1080 Remember that the memory reference will be changed to refer to the
1081 destination of the extention. So we're actually emitting a copy
1082 from the new destination to the old destination. */
1083 for (unsigned int i = 0; i < reinsn_copy_list.length (); i += 2)
1085 rtx curr_insn = reinsn_copy_list[i];
1086 rtx def_insn = reinsn_copy_list[i + 1];
1088 /* Use the mode of the destination of the defining insn
1089 for the mode of the copy. This is necessary if the
1090 defining insn was used to eliminate a second extension
1091 that was wider than the first. */
1092 rtx sub_rtx = *get_sub_rtx (def_insn);
1093 rtx pat = PATTERN (curr_insn);
1094 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)),
1095 REGNO (XEXP (SET_SRC (pat), 0)));
1096 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)),
1097 REGNO (SET_DEST (pat)));
1098 rtx set = gen_rtx_SET (VOIDmode, new_dst, new_src);
1099 emit_insn_after (set, def_insn);
1102 /* Delete all useless extensions here in one sweep. */
1103 FOR_EACH_VEC_ELT (reinsn_del_list, i, curr_insn)
1104 delete_insn (curr_insn);
1106 reinsn_list.release ();
1107 state.defs_list.release ();
1108 state.copies_list.release ();
1109 state.modified_list.release ();
1110 state.work_list.release ();
1111 XDELETEVEC (state.modified);
1113 if (dump_file && num_re_opportunities > 0)
1114 fprintf (dump_file, "Elimination opportunities = %d realized = %d\n",
1115 num_re_opportunities, num_realized);
1118 /* Find and remove redundant extensions. */
1120 static unsigned int
1121 rest_of_handle_ree (void)
1123 timevar_push (TV_REE);
1124 find_and_remove_re ();
1125 timevar_pop (TV_REE);
1126 return 0;
1129 namespace {
1131 const pass_data pass_data_ree =
1133 RTL_PASS, /* type */
1134 "ree", /* name */
1135 OPTGROUP_NONE, /* optinfo_flags */
1136 TV_REE, /* tv_id */
1137 0, /* properties_required */
1138 0, /* properties_provided */
1139 0, /* properties_destroyed */
1140 0, /* todo_flags_start */
1141 TODO_df_finish, /* todo_flags_finish */
1144 class pass_ree : public rtl_opt_pass
1146 public:
1147 pass_ree (gcc::context *ctxt)
1148 : rtl_opt_pass (pass_data_ree, ctxt)
1151 /* opt_pass methods: */
1152 virtual bool gate (function *) { return (optimize > 0 && flag_ree); }
1153 virtual unsigned int execute (function *) { return rest_of_handle_ree (); }
1155 }; // class pass_ree
1157 } // anon namespace
1159 rtl_opt_pass *
1160 make_pass_ree (gcc::context *ctxt)
1162 return new pass_ree (ctxt);