[RS6000] PR79144, cmpstrnsi optimization breaks glibc
[official-gcc.git] / gcc / ree.c
blob40b4041ef874b954bff311982fec6de14a16b867
1 /* Redundant Extension Elimination pass for the GNU compiler.
2 Copyright (C) 2010-2017 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 "backend.h"
222 #include "target.h"
223 #include "rtl.h"
224 #include "tree.h"
225 #include "df.h"
226 #include "memmodel.h"
227 #include "tm_p.h"
228 #include "optabs.h"
229 #include "emit-rtl.h"
230 #include "recog.h"
231 #include "cfgrtl.h"
232 #include "expr.h"
233 #include "tree-pass.h"
235 /* This structure represents a candidate for elimination. */
237 struct ext_cand
239 /* The expression. */
240 const_rtx expr;
242 /* The kind of extension. */
243 enum rtx_code code;
245 /* The destination mode. */
246 machine_mode mode;
248 /* The instruction where it lives. */
249 rtx_insn *insn;
253 static int max_insn_uid;
255 /* Update or remove REG_EQUAL or REG_EQUIV notes for INSN. */
257 static bool
258 update_reg_equal_equiv_notes (rtx_insn *insn, machine_mode new_mode,
259 machine_mode old_mode, enum rtx_code code)
261 rtx *loc = &REG_NOTES (insn);
262 while (*loc)
264 enum reg_note kind = REG_NOTE_KIND (*loc);
265 if (kind == REG_EQUAL || kind == REG_EQUIV)
267 rtx orig_src = XEXP (*loc, 0);
268 /* Update equivalency constants. Recall that RTL constants are
269 sign-extended. */
270 if (GET_CODE (orig_src) == CONST_INT
271 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (new_mode))
273 if (INTVAL (orig_src) >= 0 || code == SIGN_EXTEND)
274 /* Nothing needed. */;
275 else
277 /* Zero-extend the negative constant by masking out the
278 bits outside the source mode. */
279 rtx new_const_int
280 = gen_int_mode (INTVAL (orig_src)
281 & GET_MODE_MASK (old_mode),
282 new_mode);
283 if (!validate_change (insn, &XEXP (*loc, 0),
284 new_const_int, true))
285 return false;
287 loc = &XEXP (*loc, 1);
289 /* Drop all other notes, they assume a wrong mode. */
290 else if (!validate_change (insn, loc, XEXP (*loc, 1), true))
291 return false;
293 else
294 loc = &XEXP (*loc, 1);
296 return true;
299 /* Given a insn (CURR_INSN), an extension candidate for removal (CAND)
300 and a pointer to the SET rtx (ORIG_SET) that needs to be modified,
301 this code modifies the SET rtx to a new SET rtx that extends the
302 right hand expression into a register on the left hand side. Note
303 that multiple assumptions are made about the nature of the set that
304 needs to be true for this to work and is called from merge_def_and_ext.
306 Original :
307 (set (reg a) (expression))
309 Transform :
310 (set (reg a) (any_extend (expression)))
312 Special Cases :
313 If the expression is a constant or another extension, then directly
314 assign it to the register. */
316 static bool
317 combine_set_extension (ext_cand *cand, rtx_insn *curr_insn, rtx *orig_set)
319 rtx orig_src = SET_SRC (*orig_set);
320 machine_mode orig_mode = GET_MODE (SET_DEST (*orig_set));
321 rtx new_set;
322 rtx cand_pat = PATTERN (cand->insn);
324 /* If the extension's source/destination registers are not the same
325 then we need to change the original load to reference the destination
326 of the extension. Then we need to emit a copy from that destination
327 to the original destination of the load. */
328 rtx new_reg;
329 bool copy_needed
330 = (REGNO (SET_DEST (cand_pat)) != REGNO (XEXP (SET_SRC (cand_pat), 0)));
331 if (copy_needed)
332 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (cand_pat)));
333 else
334 new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (*orig_set)));
336 /* Merge constants by directly moving the constant into the register under
337 some conditions. Recall that RTL constants are sign-extended. */
338 if (GET_CODE (orig_src) == CONST_INT
339 && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (cand->mode))
341 if (INTVAL (orig_src) >= 0 || cand->code == SIGN_EXTEND)
342 new_set = gen_rtx_SET (new_reg, orig_src);
343 else
345 /* Zero-extend the negative constant by masking out the bits outside
346 the source mode. */
347 rtx new_const_int
348 = gen_int_mode (INTVAL (orig_src) & GET_MODE_MASK (orig_mode),
349 GET_MODE (new_reg));
350 new_set = gen_rtx_SET (new_reg, new_const_int);
353 else if (GET_MODE (orig_src) == VOIDmode)
355 /* This is mostly due to a call insn that should not be optimized. */
356 return false;
358 else if (GET_CODE (orig_src) == cand->code)
360 /* Here is a sequence of two extensions. Try to merge them. */
361 rtx temp_extension
362 = gen_rtx_fmt_e (cand->code, cand->mode, XEXP (orig_src, 0));
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 (new_reg, temp_extension);
368 else if (GET_CODE (orig_src) == IF_THEN_ELSE)
370 /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise,
371 in general, IF_THEN_ELSE should not be combined. */
372 return false;
374 else
376 /* This is the normal case. */
377 rtx temp_extension
378 = gen_rtx_fmt_e (cand->code, cand->mode, orig_src);
379 rtx simplified_temp_extension = simplify_rtx (temp_extension);
380 if (simplified_temp_extension)
381 temp_extension = simplified_temp_extension;
382 new_set = gen_rtx_SET (new_reg, temp_extension);
385 /* This change is a part of a group of changes. Hence,
386 validate_change will not try to commit the change. */
387 if (validate_change (curr_insn, orig_set, new_set, true)
388 && update_reg_equal_equiv_notes (curr_insn, cand->mode, orig_mode,
389 cand->code))
391 if (dump_file)
393 fprintf (dump_file,
394 "Tentatively merged extension with definition %s:\n",
395 (copy_needed) ? "(copy needed)" : "");
396 print_rtl_single (dump_file, curr_insn);
398 return true;
401 return false;
404 /* Treat if_then_else insns, where the operands of both branches
405 are registers, as copies. For instance,
406 Original :
407 (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c)))
408 Transformed :
409 (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c)))
410 DEF_INSN is the if_then_else insn. */
412 static bool
413 transform_ifelse (ext_cand *cand, rtx_insn *def_insn)
415 rtx set_insn = PATTERN (def_insn);
416 rtx srcreg, dstreg, srcreg2;
417 rtx map_srcreg, map_dstreg, map_srcreg2;
418 rtx ifexpr;
419 rtx cond;
420 rtx new_set;
422 gcc_assert (GET_CODE (set_insn) == SET);
424 cond = XEXP (SET_SRC (set_insn), 0);
425 dstreg = SET_DEST (set_insn);
426 srcreg = XEXP (SET_SRC (set_insn), 1);
427 srcreg2 = XEXP (SET_SRC (set_insn), 2);
428 /* If the conditional move already has the right or wider mode,
429 there is nothing to do. */
430 if (GET_MODE_SIZE (GET_MODE (dstreg)) >= GET_MODE_SIZE (cand->mode))
431 return true;
433 map_srcreg = gen_rtx_REG (cand->mode, REGNO (srcreg));
434 map_srcreg2 = gen_rtx_REG (cand->mode, REGNO (srcreg2));
435 map_dstreg = gen_rtx_REG (cand->mode, REGNO (dstreg));
436 ifexpr = gen_rtx_IF_THEN_ELSE (cand->mode, cond, map_srcreg, map_srcreg2);
437 new_set = gen_rtx_SET (map_dstreg, ifexpr);
439 if (validate_change (def_insn, &PATTERN (def_insn), new_set, true)
440 && update_reg_equal_equiv_notes (def_insn, cand->mode, GET_MODE (dstreg),
441 cand->code))
443 if (dump_file)
445 fprintf (dump_file,
446 "Mode of conditional move instruction extended:\n");
447 print_rtl_single (dump_file, def_insn);
449 return true;
452 return false;
455 /* Get all the reaching definitions of an instruction. The definitions are
456 desired for REG used in INSN. Return the definition list or NULL if a
457 definition is missing. If DEST is non-NULL, additionally push the INSN
458 of the definitions onto DEST. */
460 static struct df_link *
461 get_defs (rtx_insn *insn, rtx reg, vec<rtx_insn *> *dest)
463 df_ref use;
464 struct df_link *ref_chain, *ref_link;
466 FOR_EACH_INSN_USE (use, insn)
468 if (GET_CODE (DF_REF_REG (use)) == SUBREG)
469 return NULL;
470 if (REGNO (DF_REF_REG (use)) == REGNO (reg))
471 break;
474 gcc_assert (use != NULL);
476 ref_chain = DF_REF_CHAIN (use);
478 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
480 /* Problem getting some definition for this instruction. */
481 if (ref_link->ref == NULL)
482 return NULL;
483 if (DF_REF_INSN_INFO (ref_link->ref) == NULL)
484 return NULL;
485 /* As global regs are assumed to be defined at each function call
486 dataflow can report a call_insn as being a definition of REG.
487 But we can't do anything with that in this pass so proceed only
488 if the instruction really sets REG in a way that can be deduced
489 from the RTL structure. */
490 if (global_regs[REGNO (reg)]
491 && !set_of (reg, DF_REF_INSN (ref_link->ref)))
492 return NULL;
495 if (dest)
496 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
497 dest->safe_push (DF_REF_INSN (ref_link->ref));
499 return ref_chain;
502 /* Get all the reaching uses of an instruction. The uses are desired for REG
503 set in INSN. Return use list or NULL if a use is missing or irregular. */
505 static struct df_link *
506 get_uses (rtx_insn *insn, rtx reg)
508 df_ref def;
509 struct df_link *ref_chain, *ref_link;
511 FOR_EACH_INSN_DEF (def, insn)
512 if (REGNO (DF_REF_REG (def)) == REGNO (reg))
513 break;
515 gcc_assert (def != NULL);
517 ref_chain = DF_REF_CHAIN (def);
519 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
521 /* Problem getting some use for this instruction. */
522 if (ref_link->ref == NULL)
523 return NULL;
524 if (DF_REF_CLASS (ref_link->ref) != DF_REF_REGULAR)
525 return NULL;
528 return ref_chain;
531 /* Return true if INSN is
532 (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2)))
533 and store x1 and x2 in REG_1 and REG_2. */
535 static bool
536 is_cond_copy_insn (rtx_insn *insn, rtx *reg1, rtx *reg2)
538 rtx expr = single_set (insn);
540 if (expr != NULL_RTX
541 && GET_CODE (expr) == SET
542 && GET_CODE (SET_DEST (expr)) == REG
543 && GET_CODE (SET_SRC (expr)) == IF_THEN_ELSE
544 && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG
545 && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG)
547 *reg1 = XEXP (SET_SRC (expr), 1);
548 *reg2 = XEXP (SET_SRC (expr), 2);
549 return true;
552 return false;
555 enum ext_modified_kind
557 /* The insn hasn't been modified by ree pass yet. */
558 EXT_MODIFIED_NONE,
559 /* Changed into zero extension. */
560 EXT_MODIFIED_ZEXT,
561 /* Changed into sign extension. */
562 EXT_MODIFIED_SEXT
565 struct ATTRIBUTE_PACKED ext_modified
567 /* Mode from which ree has zero or sign extended the destination. */
568 ENUM_BITFIELD(machine_mode) mode : 8;
570 /* Kind of modification of the insn. */
571 ENUM_BITFIELD(ext_modified_kind) kind : 2;
573 unsigned int do_not_reextend : 1;
575 /* True if the insn is scheduled to be deleted. */
576 unsigned int deleted : 1;
579 /* Vectors used by combine_reaching_defs and its helpers. */
580 struct ext_state
582 /* In order to avoid constant alloc/free, we keep these
583 4 vectors live through the entire find_and_remove_re and just
584 truncate them each time. */
585 auto_vec<rtx_insn *> defs_list;
586 auto_vec<rtx_insn *> copies_list;
587 auto_vec<rtx_insn *> modified_list;
588 auto_vec<rtx_insn *> work_list;
590 /* For instructions that have been successfully modified, this is
591 the original mode from which the insn is extending and
592 kind of extension. */
593 struct ext_modified *modified;
596 /* Reaching Definitions of the extended register could be conditional copies
597 or regular definitions. This function separates the two types into two
598 lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because,
599 if a reaching definition is a conditional copy, merging the extension with
600 this definition is wrong. Conditional copies are merged by transitively
601 merging their definitions. The defs_list is populated with all the reaching
602 definitions of the extension instruction (EXTEND_INSN) which must be merged
603 with an extension. The copies_list contains all the conditional moves that
604 will later be extended into a wider mode conditional move if all the merges
605 are successful. The function returns false upon failure, true upon
606 success. */
608 static bool
609 make_defs_and_copies_lists (rtx_insn *extend_insn, const_rtx set_pat,
610 ext_state *state)
612 rtx src_reg = XEXP (SET_SRC (set_pat), 0);
613 bool *is_insn_visited;
614 bool ret = true;
616 state->work_list.truncate (0);
618 /* Initialize the work list. */
619 if (!get_defs (extend_insn, src_reg, &state->work_list))
620 return false;
622 is_insn_visited = XCNEWVEC (bool, max_insn_uid);
624 /* Perform transitive closure for conditional copies. */
625 while (!state->work_list.is_empty ())
627 rtx_insn *def_insn = state->work_list.pop ();
628 rtx reg1, reg2;
630 gcc_assert (INSN_UID (def_insn) < max_insn_uid);
632 if (is_insn_visited[INSN_UID (def_insn)])
633 continue;
634 is_insn_visited[INSN_UID (def_insn)] = true;
636 if (is_cond_copy_insn (def_insn, &reg1, &reg2))
638 /* Push it onto the copy list first. */
639 state->copies_list.safe_push (def_insn);
641 /* Now perform the transitive closure. */
642 if (!get_defs (def_insn, reg1, &state->work_list)
643 || !get_defs (def_insn, reg2, &state->work_list))
645 ret = false;
646 break;
649 else
650 state->defs_list.safe_push (def_insn);
653 XDELETEVEC (is_insn_visited);
655 return ret;
658 /* If DEF_INSN has single SET expression, possibly buried inside
659 a PARALLEL, return the address of the SET expression, else
660 return NULL. This is similar to single_set, except that
661 single_set allows multiple SETs when all but one is dead. */
662 static rtx *
663 get_sub_rtx (rtx_insn *def_insn)
665 enum rtx_code code = GET_CODE (PATTERN (def_insn));
666 rtx *sub_rtx = NULL;
668 if (code == PARALLEL)
670 for (int i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++)
672 rtx s_expr = XVECEXP (PATTERN (def_insn), 0, i);
673 if (GET_CODE (s_expr) != SET)
674 continue;
676 if (sub_rtx == NULL)
677 sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i);
678 else
680 /* PARALLEL with multiple SETs. */
681 return NULL;
685 else if (code == SET)
686 sub_rtx = &PATTERN (def_insn);
687 else
689 /* It is not a PARALLEL or a SET, what could it be ? */
690 return NULL;
693 gcc_assert (sub_rtx != NULL);
694 return sub_rtx;
697 /* Merge the DEF_INSN with an extension. Calls combine_set_extension
698 on the SET pattern. */
700 static bool
701 merge_def_and_ext (ext_cand *cand, rtx_insn *def_insn, ext_state *state)
703 machine_mode ext_src_mode;
704 rtx *sub_rtx;
706 ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0));
707 sub_rtx = get_sub_rtx (def_insn);
709 if (sub_rtx == NULL)
710 return false;
712 if (REG_P (SET_DEST (*sub_rtx))
713 && (GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode
714 || ((state->modified[INSN_UID (def_insn)].kind
715 == (cand->code == ZERO_EXTEND
716 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT))
717 && state->modified[INSN_UID (def_insn)].mode
718 == ext_src_mode)))
720 if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx)))
721 >= GET_MODE_SIZE (cand->mode))
722 return true;
723 /* If def_insn is already scheduled to be deleted, don't attempt
724 to modify it. */
725 if (state->modified[INSN_UID (def_insn)].deleted)
726 return false;
727 if (combine_set_extension (cand, def_insn, sub_rtx))
729 if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE)
730 state->modified[INSN_UID (def_insn)].mode = ext_src_mode;
731 return true;
735 return false;
738 /* Given SRC, which should be one or more extensions of a REG, strip
739 away the extensions and return the REG. */
741 static inline rtx
742 get_extended_src_reg (rtx src)
744 while (GET_CODE (src) == SIGN_EXTEND || GET_CODE (src) == ZERO_EXTEND)
745 src = XEXP (src, 0);
746 gcc_assert (REG_P (src));
747 return src;
750 /* This function goes through all reaching defs of the source
751 of the candidate for elimination (CAND) and tries to combine
752 the extension with the definition instruction. The changes
753 are made as a group so that even if one definition cannot be
754 merged, all reaching definitions end up not being merged.
755 When a conditional copy is encountered, merging is attempted
756 transitively on its definitions. It returns true upon success
757 and false upon failure. */
759 static bool
760 combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state)
762 rtx_insn *def_insn;
763 bool merge_successful = true;
764 int i;
765 int defs_ix;
766 bool outcome;
768 state->defs_list.truncate (0);
769 state->copies_list.truncate (0);
771 outcome = make_defs_and_copies_lists (cand->insn, set_pat, state);
773 if (!outcome)
774 return false;
776 /* If the destination operand of the extension is a different
777 register than the source operand, then additional restrictions
778 are needed. Note we have to handle cases where we have nested
779 extensions in the source operand. */
780 bool copy_needed
781 = (REGNO (SET_DEST (PATTERN (cand->insn)))
782 != REGNO (get_extended_src_reg (SET_SRC (PATTERN (cand->insn)))));
783 if (copy_needed)
785 /* Considering transformation of
786 (set (reg1) (expression))
788 (set (reg2) (any_extend (reg1)))
790 into
792 (set (reg2) (any_extend (expression)))
793 (set (reg1) (reg2))
794 ... */
796 /* In theory we could handle more than one reaching def, it
797 just makes the code to update the insn stream more complex. */
798 if (state->defs_list.length () != 1)
799 return false;
801 /* We don't have the structure described above if there are
802 conditional moves in between the def and the candidate,
803 and we will not handle them correctly. See PR68194. */
804 if (state->copies_list.length () > 0)
805 return false;
807 /* We require the candidate not already be modified. It may,
808 for example have been changed from a (sign_extend (reg))
809 into (zero_extend (sign_extend (reg))).
811 Handling that case shouldn't be terribly difficult, but the code
812 here and the code to emit copies would need auditing. Until
813 we see a need, this is the safe thing to do. */
814 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE)
815 return false;
817 machine_mode dst_mode = GET_MODE (SET_DEST (PATTERN (cand->insn)));
818 rtx src_reg = get_extended_src_reg (SET_SRC (PATTERN (cand->insn)));
820 /* Ensure we can use the src_reg in dst_mode (needed for
821 the (set (reg1) (reg2)) insn mentioned above). */
822 if (!HARD_REGNO_MODE_OK (REGNO (src_reg), dst_mode))
823 return false;
825 /* Ensure the number of hard registers of the copy match. */
826 if (HARD_REGNO_NREGS (REGNO (src_reg), dst_mode)
827 != HARD_REGNO_NREGS (REGNO (src_reg), GET_MODE (src_reg)))
828 return false;
830 /* There's only one reaching def. */
831 rtx_insn *def_insn = state->defs_list[0];
833 /* The defining statement must not have been modified either. */
834 if (state->modified[INSN_UID (def_insn)].kind != EXT_MODIFIED_NONE)
835 return false;
837 /* The defining statement and candidate insn must be in the same block.
838 This is merely to keep the test for safety and updating the insn
839 stream simple. Also ensure that within the block the candidate
840 follows the defining insn. */
841 basic_block bb = BLOCK_FOR_INSN (cand->insn);
842 if (bb != BLOCK_FOR_INSN (def_insn)
843 || DF_INSN_LUID (def_insn) > DF_INSN_LUID (cand->insn))
844 return false;
846 /* If there is an overlap between the destination of DEF_INSN and
847 CAND->insn, then this transformation is not safe. Note we have
848 to test in the widened mode. */
849 rtx *dest_sub_rtx = get_sub_rtx (def_insn);
850 if (dest_sub_rtx == NULL
851 || !REG_P (SET_DEST (*dest_sub_rtx)))
852 return false;
854 rtx tmp_reg = gen_rtx_REG (GET_MODE (SET_DEST (PATTERN (cand->insn))),
855 REGNO (SET_DEST (*dest_sub_rtx)));
856 if (reg_overlap_mentioned_p (tmp_reg, SET_DEST (PATTERN (cand->insn))))
857 return false;
859 /* On RISC machines we must make sure that changing the mode of SRC_REG
860 as destination register will not affect its reaching uses, which may
861 read its value in a larger mode because DEF_INSN implicitly sets it
862 in word mode. */
863 const unsigned int prec
864 = GET_MODE_PRECISION (GET_MODE (SET_DEST (*dest_sub_rtx)));
865 if (WORD_REGISTER_OPERATIONS && prec < BITS_PER_WORD)
867 struct df_link *uses = get_uses (def_insn, src_reg);
868 if (!uses)
869 return false;
871 for (df_link *use = uses; use; use = use->next)
872 if (GET_MODE_PRECISION (GET_MODE (*DF_REF_LOC (use->ref))) > prec)
873 return false;
876 /* The destination register of the extension insn must not be
877 used or set between the def_insn and cand->insn exclusive. */
878 if (reg_used_between_p (SET_DEST (PATTERN (cand->insn)),
879 def_insn, cand->insn)
880 || reg_set_between_p (SET_DEST (PATTERN (cand->insn)),
881 def_insn, cand->insn))
882 return false;
884 /* We must be able to copy between the two registers. Generate,
885 recognize and verify constraints of the copy. Also fail if this
886 generated more than one insn.
888 This generates garbage since we throw away the insn when we're
889 done, only to recreate it later if this test was successful.
891 Make sure to get the mode from the extension (cand->insn). This
892 is different than in the code to emit the copy as we have not
893 modified the defining insn yet. */
894 start_sequence ();
895 rtx pat = PATTERN (cand->insn);
896 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (pat)),
897 REGNO (get_extended_src_reg (SET_SRC (pat))));
898 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (pat)),
899 REGNO (SET_DEST (pat)));
900 emit_move_insn (new_dst, new_src);
902 rtx_insn *insn = get_insns();
903 end_sequence ();
904 if (NEXT_INSN (insn))
905 return false;
906 if (recog_memoized (insn) == -1)
907 return false;
908 extract_insn (insn);
909 if (!constrain_operands (1, get_preferred_alternatives (insn, bb)))
910 return false;
914 /* If cand->insn has been already modified, update cand->mode to a wider
915 mode if possible, or punt. */
916 if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE)
918 machine_mode mode;
919 rtx set;
921 if (state->modified[INSN_UID (cand->insn)].kind
922 != (cand->code == ZERO_EXTEND
923 ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT)
924 || state->modified[INSN_UID (cand->insn)].mode != cand->mode
925 || (set = single_set (cand->insn)) == NULL_RTX)
926 return false;
927 mode = GET_MODE (SET_DEST (set));
928 gcc_assert (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (cand->mode));
929 cand->mode = mode;
932 merge_successful = true;
934 /* Go through the defs vector and try to merge all the definitions
935 in this vector. */
936 state->modified_list.truncate (0);
937 FOR_EACH_VEC_ELT (state->defs_list, defs_ix, def_insn)
939 if (merge_def_and_ext (cand, def_insn, state))
940 state->modified_list.safe_push (def_insn);
941 else
943 merge_successful = false;
944 break;
948 /* Now go through the conditional copies vector and try to merge all
949 the copies in this vector. */
950 if (merge_successful)
952 FOR_EACH_VEC_ELT (state->copies_list, i, def_insn)
954 if (transform_ifelse (cand, def_insn))
955 state->modified_list.safe_push (def_insn);
956 else
958 merge_successful = false;
959 break;
964 if (merge_successful)
966 /* Commit the changes here if possible
967 FIXME: It's an all-or-nothing scenario. Even if only one definition
968 cannot be merged, we entirely give up. In the future, we should allow
969 extensions to be partially eliminated along those paths where the
970 definitions could be merged. */
971 if (apply_change_group ())
973 if (dump_file)
974 fprintf (dump_file, "All merges were successful.\n");
976 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
978 ext_modified *modified = &state->modified[INSN_UID (def_insn)];
979 if (modified->kind == EXT_MODIFIED_NONE)
980 modified->kind = (cand->code == ZERO_EXTEND ? EXT_MODIFIED_ZEXT
981 : EXT_MODIFIED_SEXT);
983 if (copy_needed)
984 modified->do_not_reextend = 1;
986 return true;
988 else
990 /* Changes need not be cancelled explicitly as apply_change_group
991 does it. Print list of definitions in the dump_file for debug
992 purposes. This extension cannot be deleted. */
993 if (dump_file)
995 fprintf (dump_file,
996 "Merge cancelled, non-mergeable definitions:\n");
997 FOR_EACH_VEC_ELT (state->modified_list, i, def_insn)
998 print_rtl_single (dump_file, def_insn);
1002 else
1004 /* Cancel any changes that have been made so far. */
1005 cancel_changes (0);
1008 return false;
1011 /* Add an extension pattern that could be eliminated. */
1013 static void
1014 add_removable_extension (const_rtx expr, rtx_insn *insn,
1015 vec<ext_cand> *insn_list,
1016 unsigned *def_map,
1017 bitmap init_regs)
1019 enum rtx_code code;
1020 machine_mode mode;
1021 unsigned int idx;
1022 rtx src, dest;
1024 /* We are looking for SET (REG N) (ANY_EXTEND (REG N)). */
1025 if (GET_CODE (expr) != SET)
1026 return;
1028 src = SET_SRC (expr);
1029 code = GET_CODE (src);
1030 dest = SET_DEST (expr);
1031 mode = GET_MODE (dest);
1033 if (REG_P (dest)
1034 && (code == SIGN_EXTEND || code == ZERO_EXTEND)
1035 && REG_P (XEXP (src, 0)))
1037 rtx reg = XEXP (src, 0);
1038 struct df_link *defs, *def;
1039 ext_cand *cand;
1041 /* Zero-extension of an undefined value is partly defined (it's
1042 completely undefined for sign-extension, though). So if there exists
1043 a path from the entry to this zero-extension that leaves this register
1044 uninitialized, removing the extension could change the behavior of
1045 correct programs. So first, check it is not the case. */
1046 if (code == ZERO_EXTEND && !bitmap_bit_p (init_regs, REGNO (reg)))
1048 if (dump_file)
1050 fprintf (dump_file, "Cannot eliminate extension:\n");
1051 print_rtl_single (dump_file, insn);
1052 fprintf (dump_file, " because it can operate on uninitialized"
1053 " data\n");
1055 return;
1058 /* Second, make sure we can get all the reaching definitions. */
1059 defs = get_defs (insn, reg, NULL);
1060 if (!defs)
1062 if (dump_file)
1064 fprintf (dump_file, "Cannot eliminate extension:\n");
1065 print_rtl_single (dump_file, insn);
1066 fprintf (dump_file, " because of missing definition(s)\n");
1068 return;
1071 /* Third, make sure the reaching definitions don't feed another and
1072 different extension. FIXME: this obviously can be improved. */
1073 for (def = defs; def; def = def->next)
1074 if ((idx = def_map[INSN_UID (DF_REF_INSN (def->ref))])
1075 && idx != -1U
1076 && (cand = &(*insn_list)[idx - 1])
1077 && cand->code != code)
1079 if (dump_file)
1081 fprintf (dump_file, "Cannot eliminate extension:\n");
1082 print_rtl_single (dump_file, insn);
1083 fprintf (dump_file, " because of other extension\n");
1085 return;
1087 /* For vector mode extensions, ensure that all uses of the
1088 XEXP (src, 0) register are in insn or debug insns, as unlike
1089 integral extensions lowpart subreg of the sign/zero extended
1090 register are not equal to the original register, so we have
1091 to change all uses or none and the current code isn't able
1092 to change them all at once in one transaction. */
1093 else if (VECTOR_MODE_P (GET_MODE (XEXP (src, 0))))
1095 if (idx == 0)
1097 struct df_link *ref_chain, *ref_link;
1099 ref_chain = DF_REF_CHAIN (def->ref);
1100 for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
1102 if (ref_link->ref == NULL
1103 || DF_REF_INSN_INFO (ref_link->ref) == NULL)
1105 idx = -1U;
1106 break;
1108 rtx_insn *use_insn = DF_REF_INSN (ref_link->ref);
1109 if (use_insn != insn && !DEBUG_INSN_P (use_insn))
1111 idx = -1U;
1112 break;
1115 if (idx == -1U)
1116 def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx;
1118 if (idx == -1U)
1120 if (dump_file)
1122 fprintf (dump_file, "Cannot eliminate extension:\n");
1123 print_rtl_single (dump_file, insn);
1124 fprintf (dump_file,
1125 " because some vector uses aren't extension\n");
1127 return;
1131 /* Fourth, if the extended version occupies more registers than the
1132 original and the source of the extension is the same hard register
1133 as the destination of the extension, then we can not eliminate
1134 the extension without deep analysis, so just punt.
1136 We allow this when the registers are different because the
1137 code in combine_reaching_defs will handle that case correctly. */
1138 if ((HARD_REGNO_NREGS (REGNO (dest), mode)
1139 != HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)))
1140 && reg_overlap_mentioned_p (dest, reg))
1141 return;
1143 /* Then add the candidate to the list and insert the reaching definitions
1144 into the definition map. */
1145 ext_cand e = {expr, code, mode, insn};
1146 insn_list->safe_push (e);
1147 idx = insn_list->length ();
1149 for (def = defs; def; def = def->next)
1150 def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx;
1154 /* Traverse the instruction stream looking for extensions and return the
1155 list of candidates. */
1157 static vec<ext_cand>
1158 find_removable_extensions (void)
1160 vec<ext_cand> insn_list = vNULL;
1161 basic_block bb;
1162 rtx_insn *insn;
1163 rtx set;
1164 unsigned *def_map = XCNEWVEC (unsigned, max_insn_uid);
1165 bitmap_head init, kill, gen, tmp;
1167 bitmap_initialize (&init, NULL);
1168 bitmap_initialize (&kill, NULL);
1169 bitmap_initialize (&gen, NULL);
1170 bitmap_initialize (&tmp, NULL);
1172 FOR_EACH_BB_FN (bb, cfun)
1174 bitmap_copy (&init, DF_MIR_IN (bb));
1175 bitmap_clear (&kill);
1176 bitmap_clear (&gen);
1178 FOR_BB_INSNS (bb, insn)
1180 if (NONDEBUG_INSN_P (insn))
1182 set = single_set (insn);
1183 if (set != NULL_RTX)
1184 add_removable_extension (set, insn, &insn_list, def_map,
1185 &init);
1186 df_mir_simulate_one_insn (bb, insn, &kill, &gen);
1187 bitmap_ior_and_compl (&tmp, &gen, &init, &kill);
1188 bitmap_copy (&init, &tmp);
1193 XDELETEVEC (def_map);
1195 return insn_list;
1198 /* This is the main function that checks the insn stream for redundant
1199 extensions and tries to remove them if possible. */
1201 static void
1202 find_and_remove_re (void)
1204 ext_cand *curr_cand;
1205 rtx_insn *curr_insn = NULL;
1206 int num_re_opportunities = 0, num_realized = 0, i;
1207 vec<ext_cand> reinsn_list;
1208 auto_vec<rtx_insn *> reinsn_del_list;
1209 auto_vec<rtx_insn *> reinsn_copy_list;
1211 /* Construct DU chain to get all reaching definitions of each
1212 extension instruction. */
1213 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
1214 df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
1215 df_mir_add_problem ();
1216 df_analyze ();
1217 df_set_flags (DF_DEFER_INSN_RESCAN);
1219 max_insn_uid = get_max_uid ();
1220 reinsn_list = find_removable_extensions ();
1222 ext_state state;
1223 if (reinsn_list.is_empty ())
1224 state.modified = NULL;
1225 else
1226 state.modified = XCNEWVEC (struct ext_modified, max_insn_uid);
1228 FOR_EACH_VEC_ELT (reinsn_list, i, curr_cand)
1230 num_re_opportunities++;
1232 /* Try to combine the extension with the definition. */
1233 if (dump_file)
1235 fprintf (dump_file, "Trying to eliminate extension:\n");
1236 print_rtl_single (dump_file, curr_cand->insn);
1239 if (combine_reaching_defs (curr_cand, curr_cand->expr, &state))
1241 if (dump_file)
1242 fprintf (dump_file, "Eliminated the extension.\n");
1243 num_realized++;
1244 /* If the RHS of the current candidate is not (extend (reg)), then
1245 we do not allow the optimization of extensions where
1246 the source and destination registers do not match. Thus
1247 checking REG_P here is correct. */
1248 if (REG_P (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0))
1249 && (REGNO (SET_DEST (PATTERN (curr_cand->insn)))
1250 != REGNO (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0))))
1252 reinsn_copy_list.safe_push (curr_cand->insn);
1253 reinsn_copy_list.safe_push (state.defs_list[0]);
1255 reinsn_del_list.safe_push (curr_cand->insn);
1256 state.modified[INSN_UID (curr_cand->insn)].deleted = 1;
1260 /* The copy list contains pairs of insns which describe copies we
1261 need to insert into the INSN stream.
1263 The first insn in each pair is the extension insn, from which
1264 we derive the source and destination of the copy.
1266 The second insn in each pair is the memory reference where the
1267 extension will ultimately happen. We emit the new copy
1268 immediately after this insn.
1270 It may first appear that the arguments for the copy are reversed.
1271 Remember that the memory reference will be changed to refer to the
1272 destination of the extention. So we're actually emitting a copy
1273 from the new destination to the old destination. */
1274 for (unsigned int i = 0; i < reinsn_copy_list.length (); i += 2)
1276 rtx_insn *curr_insn = reinsn_copy_list[i];
1277 rtx_insn *def_insn = reinsn_copy_list[i + 1];
1279 /* Use the mode of the destination of the defining insn
1280 for the mode of the copy. This is necessary if the
1281 defining insn was used to eliminate a second extension
1282 that was wider than the first. */
1283 rtx sub_rtx = *get_sub_rtx (def_insn);
1284 rtx pat = PATTERN (curr_insn);
1285 rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)),
1286 REGNO (XEXP (SET_SRC (pat), 0)));
1287 rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)),
1288 REGNO (SET_DEST (pat)));
1289 rtx set = gen_rtx_SET (new_dst, new_src);
1290 emit_insn_after (set, def_insn);
1293 /* Delete all useless extensions here in one sweep. */
1294 FOR_EACH_VEC_ELT (reinsn_del_list, i, curr_insn)
1295 delete_insn (curr_insn);
1297 reinsn_list.release ();
1298 XDELETEVEC (state.modified);
1300 if (dump_file && num_re_opportunities > 0)
1301 fprintf (dump_file, "Elimination opportunities = %d realized = %d\n",
1302 num_re_opportunities, num_realized);
1305 /* Find and remove redundant extensions. */
1307 static unsigned int
1308 rest_of_handle_ree (void)
1310 find_and_remove_re ();
1311 return 0;
1314 namespace {
1316 const pass_data pass_data_ree =
1318 RTL_PASS, /* type */
1319 "ree", /* name */
1320 OPTGROUP_NONE, /* optinfo_flags */
1321 TV_REE, /* tv_id */
1322 0, /* properties_required */
1323 0, /* properties_provided */
1324 0, /* properties_destroyed */
1325 0, /* todo_flags_start */
1326 TODO_df_finish, /* todo_flags_finish */
1329 class pass_ree : public rtl_opt_pass
1331 public:
1332 pass_ree (gcc::context *ctxt)
1333 : rtl_opt_pass (pass_data_ree, ctxt)
1336 /* opt_pass methods: */
1337 virtual bool gate (function *) { return (optimize > 0 && flag_ree); }
1338 virtual unsigned int execute (function *) { return rest_of_handle_ree (); }
1340 }; // class pass_ree
1342 } // anon namespace
1344 rtl_opt_pass *
1345 make_pass_ree (gcc::context *ctxt)
1347 return new pass_ree (ctxt);