]>
Commit | Line | Data |
---|---|---|
26cd9add | 1 | /* Redundant Extension Elimination pass for the GNU compiler. |
818ab71a | 2 | Copyright (C) 2010-2016 Free Software Foundation, Inc. |
282bc7b4 | 3 | Contributed by Ilya Enkovich (ilya.enkovich@intel.com) |
26cd9add | 4 | |
282bc7b4 EB |
5 | Based on the Redundant Zero-extension elimination pass contributed by |
6 | Sriraman Tallam (tmsriram@google.com) and Silvius Rus (rus@google.com). | |
87a0ebfd ST |
7 | |
8 | This file is part of GCC. | |
9 | ||
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. | |
14 | ||
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. | |
19 | ||
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/>. */ | |
23 | ||
24 | ||
25 | /* Problem Description : | |
26 | -------------------- | |
26cd9add EI |
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. | |
87a0ebfd ST |
35 | |
36 | How does this pass work ? | |
37 | -------------------------- | |
38 | ||
39 | This pass is run after register allocation. Hence, all registers that | |
26cd9add EI |
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. | |
87a0ebfd | 45 | Now, this pass tries to eliminate this instruction by merging the |
26cd9add | 46 | extension with the definitions of register x. For instance, if |
87a0ebfd ST |
47 | one of the definitions of register x was : |
48 | (set (reg:SI x) (plus:SI (reg:SI z1) (reg:SI z2))), | |
26cd9add EI |
49 | followed by extension : |
50 | (set (reg:DI x) (zero_extend:DI (reg:SI x))) | |
87a0ebfd ST |
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, | |
26cd9add EI |
54 | the extension is effectively eliminated. |
55 | ||
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. | |
87a0ebfd ST |
61 | |
62 | However, there are cases where the definition instruction cannot be | |
26cd9add EI |
63 | merged with an extension. Examples are CALL instructions. In such |
64 | cases, the original extension is not redundant and this pass does | |
87a0ebfd ST |
65 | not delete it. |
66 | ||
67 | Handling conditional moves : | |
68 | ---------------------------- | |
69 | ||
26cd9add EI |
70 | Architectures like x86-64 support conditional moves whose semantics for |
71 | extension differ from the other instructions. For instance, the | |
87a0ebfd ST |
72 | instruction *cmov ebx, eax* |
73 | zero-extends eax onto rax only when the move from ebx to eax happens. | |
282bc7b4 | 74 | Otherwise, eax may not be zero-extended. Consider conditional moves as |
87a0ebfd ST |
75 | RTL instructions of the form |
76 | (set (reg:SI x) (if_then_else (cond) (reg:SI y) (reg:SI z))). | |
26cd9add | 77 | This pass tries to merge an extension with a conditional move by |
282bc7b4 | 78 | actually merging the definitions of y and z with an extension and then |
87a0ebfd ST |
79 | converting the conditional move into : |
80 | (set (reg:DI x) (if_then_else (cond) (reg:DI y) (reg:DI z))). | |
26cd9add EI |
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 | |
87a0ebfd ST |
84 | another conditional copy. |
85 | ||
86 | Motivating Example I : | |
87 | --------------------- | |
88 | For this program : | |
89 | ********************************************** | |
90 | bad_code.c | |
91 | ||
92 | int mask[1000]; | |
93 | ||
94 | int foo(unsigned x) | |
95 | { | |
96 | if (x < 10) | |
97 | x = x * 45; | |
98 | else | |
99 | x = x * 78; | |
100 | return mask[x]; | |
101 | } | |
102 | ********************************************** | |
103 | ||
26cd9add | 104 | $ gcc -O2 bad_code.c |
87a0ebfd ST |
105 | ........ |
106 | 400315: b8 4e 00 00 00 mov $0x4e,%eax | |
107 | 40031a: 0f af f8 imul %eax,%edi | |
282bc7b4 | 108 | 40031d: 89 ff mov %edi,%edi - useless extension |
87a0ebfd ST |
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 | |
282bc7b4 | 114 | 400338: 89 ff mov %edi,%edi - useless extension |
87a0ebfd ST |
115 | 40033a: 8b 04 bd 60 19 40 00 mov 0x401960(,%rdi,4),%eax |
116 | 400341: c3 retq | |
117 | ||
26cd9add | 118 | $ gcc -O2 -free bad_code.c |
87a0ebfd ST |
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 | |
126 | ||
127 | Motivating Example II : | |
128 | --------------------- | |
129 | ||
130 | Here is an example with a conditional move. | |
131 | ||
132 | For this program : | |
133 | ********************************************** | |
134 | ||
135 | unsigned long long foo(unsigned x , unsigned y) | |
136 | { | |
137 | unsigned z; | |
138 | if (x > 100) | |
139 | z = x + y; | |
140 | else | |
141 | z = x - y; | |
142 | return (unsigned long long)(z); | |
143 | } | |
144 | ||
26cd9add | 145 | $ gcc -O2 bad_code.c |
87a0ebfd ST |
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 | |
282bc7b4 | 152 | 40036d: 89 c0 mov %eax,%eax - useless extension |
87a0ebfd ST |
153 | 40036f: c3 retq |
154 | ||
26cd9add | 155 | $ gcc -O2 -free bad_code.c |
87a0ebfd ST |
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 | |
164 | ||
26cd9add EI |
165 | Motivating Example III : |
166 | --------------------- | |
167 | ||
168 | Here is an example with a type cast. | |
169 | ||
170 | For this program : | |
171 | ********************************************** | |
172 | ||
173 | void test(int size, unsigned char *in, unsigned char *out) | |
174 | { | |
175 | int i; | |
176 | unsigned char xr, xg, xy=0; | |
177 | ||
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; | |
183 | } | |
184 | } | |
185 | ||
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 | |
282bc7b4 EB |
191 | 1b: 0f b6 c9 movzbl %cl,%ecx - useless extension |
192 | 1e: 0f b6 c0 movzbl %al,%eax - useless extension | |
26cd9add EI |
193 | 21: 69 c9 8b 4c 00 00 imul $0x4c8b,%ecx,%ecx |
194 | 27: 69 c0 46 96 00 00 imul $0x9646,%eax,%eax | |
195 | ||
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 | |
87a0ebfd ST |
203 | |
204 | Usefulness : | |
205 | ---------- | |
206 | ||
26cd9add EI |
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%. | |
87a0ebfd | 210 | |
26cd9add EI |
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%. */ | |
87a0ebfd ST |
216 | |
217 | ||
218 | #include "config.h" | |
219 | #include "system.h" | |
220 | #include "coretypes.h" | |
c7131fb2 | 221 | #include "backend.h" |
957060b5 | 222 | #include "target.h" |
87a0ebfd | 223 | #include "rtl.h" |
957060b5 | 224 | #include "tree.h" |
c7131fb2 | 225 | #include "df.h" |
87a0ebfd | 226 | #include "tm_p.h" |
957060b5 | 227 | #include "optabs.h" |
957060b5 AM |
228 | #include "emit-rtl.h" |
229 | #include "recog.h" | |
60393bbc | 230 | #include "cfgrtl.h" |
87a0ebfd | 231 | #include "expr.h" |
87a0ebfd | 232 | #include "tree-pass.h" |
87a0ebfd | 233 | |
282bc7b4 | 234 | /* This structure represents a candidate for elimination. */ |
87a0ebfd | 235 | |
50686850 | 236 | struct ext_cand |
87a0ebfd | 237 | { |
282bc7b4 EB |
238 | /* The expression. */ |
239 | const_rtx expr; | |
87a0ebfd | 240 | |
282bc7b4 EB |
241 | /* The kind of extension. */ |
242 | enum rtx_code code; | |
26cd9add | 243 | |
282bc7b4 | 244 | /* The destination mode. */ |
ef4bddc2 | 245 | machine_mode mode; |
282bc7b4 EB |
246 | |
247 | /* The instruction where it lives. */ | |
59a0c032 | 248 | rtx_insn *insn; |
50686850 | 249 | }; |
26cd9add | 250 | |
26cd9add | 251 | |
87a0ebfd ST |
252 | static int max_insn_uid; |
253 | ||
73c49bf5 JJ |
254 | /* Update or remove REG_EQUAL or REG_EQUIV notes for INSN. */ |
255 | ||
256 | static bool | |
257 | update_reg_equal_equiv_notes (rtx_insn *insn, machine_mode new_mode, | |
258 | machine_mode old_mode, enum rtx_code code) | |
259 | { | |
260 | rtx *loc = ®_NOTES (insn); | |
261 | while (*loc) | |
262 | { | |
263 | enum reg_note kind = REG_NOTE_KIND (*loc); | |
264 | if (kind == REG_EQUAL || kind == REG_EQUIV) | |
265 | { | |
266 | rtx orig_src = XEXP (*loc, 0); | |
267 | /* Update equivalency constants. Recall that RTL constants are | |
268 | sign-extended. */ | |
269 | if (GET_CODE (orig_src) == CONST_INT | |
270 | && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (new_mode)) | |
271 | { | |
272 | if (INTVAL (orig_src) >= 0 || code == SIGN_EXTEND) | |
273 | /* Nothing needed. */; | |
274 | else | |
275 | { | |
276 | /* Zero-extend the negative constant by masking out the | |
277 | bits outside the source mode. */ | |
278 | rtx new_const_int | |
279 | = gen_int_mode (INTVAL (orig_src) | |
280 | & GET_MODE_MASK (old_mode), | |
281 | new_mode); | |
282 | if (!validate_change (insn, &XEXP (*loc, 0), | |
283 | new_const_int, true)) | |
284 | return false; | |
285 | } | |
286 | loc = &XEXP (*loc, 1); | |
287 | } | |
288 | /* Drop all other notes, they assume a wrong mode. */ | |
289 | else if (!validate_change (insn, loc, XEXP (*loc, 1), true)) | |
290 | return false; | |
291 | } | |
292 | else | |
293 | loc = &XEXP (*loc, 1); | |
294 | } | |
295 | return true; | |
296 | } | |
297 | ||
26cd9add EI |
298 | /* Given a insn (CURR_INSN), an extension candidate for removal (CAND) |
299 | and a pointer to the SET rtx (ORIG_SET) that needs to be modified, | |
300 | this code modifies the SET rtx to a new SET rtx that extends the | |
301 | right hand expression into a register on the left hand side. Note | |
302 | that multiple assumptions are made about the nature of the set that | |
303 | needs to be true for this to work and is called from merge_def_and_ext. | |
87a0ebfd ST |
304 | |
305 | Original : | |
26cd9add | 306 | (set (reg a) (expression)) |
87a0ebfd ST |
307 | |
308 | Transform : | |
282bc7b4 | 309 | (set (reg a) (any_extend (expression))) |
87a0ebfd ST |
310 | |
311 | Special Cases : | |
282bc7b4 | 312 | If the expression is a constant or another extension, then directly |
26cd9add | 313 | assign it to the register. */ |
87a0ebfd ST |
314 | |
315 | static bool | |
59a0c032 | 316 | combine_set_extension (ext_cand *cand, rtx_insn *curr_insn, rtx *orig_set) |
87a0ebfd | 317 | { |
282bc7b4 | 318 | rtx orig_src = SET_SRC (*orig_set); |
73c49bf5 | 319 | machine_mode orig_mode = GET_MODE (SET_DEST (*orig_set)); |
282bc7b4 | 320 | rtx new_set; |
3c92da90 JL |
321 | rtx cand_pat = PATTERN (cand->insn); |
322 | ||
323 | /* If the extension's source/destination registers are not the same | |
324 | then we need to change the original load to reference the destination | |
325 | of the extension. Then we need to emit a copy from that destination | |
326 | to the original destination of the load. */ | |
327 | rtx new_reg; | |
328 | bool copy_needed | |
329 | = (REGNO (SET_DEST (cand_pat)) != REGNO (XEXP (SET_SRC (cand_pat), 0))); | |
330 | if (copy_needed) | |
331 | new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (cand_pat))); | |
332 | else | |
333 | new_reg = gen_rtx_REG (cand->mode, REGNO (SET_DEST (*orig_set))); | |
87a0ebfd | 334 | |
282bc7b4 EB |
335 | /* Merge constants by directly moving the constant into the register under |
336 | some conditions. Recall that RTL constants are sign-extended. */ | |
26cd9add | 337 | if (GET_CODE (orig_src) == CONST_INT |
282bc7b4 | 338 | && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (cand->mode)) |
26cd9add | 339 | { |
282bc7b4 | 340 | if (INTVAL (orig_src) >= 0 || cand->code == SIGN_EXTEND) |
f7df4a84 | 341 | new_set = gen_rtx_SET (new_reg, orig_src); |
87a0ebfd | 342 | else |
26cd9add EI |
343 | { |
344 | /* Zero-extend the negative constant by masking out the bits outside | |
345 | the source mode. */ | |
282bc7b4 | 346 | rtx new_const_int |
73c49bf5 | 347 | = gen_int_mode (INTVAL (orig_src) & GET_MODE_MASK (orig_mode), |
69db2d57 | 348 | GET_MODE (new_reg)); |
f7df4a84 | 349 | new_set = gen_rtx_SET (new_reg, new_const_int); |
26cd9add EI |
350 | } |
351 | } | |
352 | else if (GET_MODE (orig_src) == VOIDmode) | |
353 | { | |
282bc7b4 | 354 | /* This is mostly due to a call insn that should not be optimized. */ |
26cd9add | 355 | return false; |
87a0ebfd | 356 | } |
282bc7b4 | 357 | else if (GET_CODE (orig_src) == cand->code) |
87a0ebfd | 358 | { |
282bc7b4 EB |
359 | /* Here is a sequence of two extensions. Try to merge them. */ |
360 | rtx temp_extension | |
361 | = gen_rtx_fmt_e (cand->code, cand->mode, XEXP (orig_src, 0)); | |
362 | rtx simplified_temp_extension = simplify_rtx (temp_extension); | |
87a0ebfd ST |
363 | if (simplified_temp_extension) |
364 | temp_extension = simplified_temp_extension; | |
f7df4a84 | 365 | new_set = gen_rtx_SET (new_reg, temp_extension); |
87a0ebfd ST |
366 | } |
367 | else if (GET_CODE (orig_src) == IF_THEN_ELSE) | |
368 | { | |
26cd9add | 369 | /* Only IF_THEN_ELSE of phi-type copies are combined. Otherwise, |
87a0ebfd | 370 | in general, IF_THEN_ELSE should not be combined. */ |
87a0ebfd ST |
371 | return false; |
372 | } | |
373 | else | |
374 | { | |
282bc7b4 EB |
375 | /* This is the normal case. */ |
376 | rtx temp_extension | |
377 | = gen_rtx_fmt_e (cand->code, cand->mode, orig_src); | |
378 | rtx simplified_temp_extension = simplify_rtx (temp_extension); | |
87a0ebfd ST |
379 | if (simplified_temp_extension) |
380 | temp_extension = simplified_temp_extension; | |
f7df4a84 | 381 | new_set = gen_rtx_SET (new_reg, temp_extension); |
87a0ebfd ST |
382 | } |
383 | ||
26cd9add | 384 | /* This change is a part of a group of changes. Hence, |
87a0ebfd | 385 | validate_change will not try to commit the change. */ |
73c49bf5 JJ |
386 | if (validate_change (curr_insn, orig_set, new_set, true) |
387 | && update_reg_equal_equiv_notes (curr_insn, cand->mode, orig_mode, | |
388 | cand->code)) | |
87a0ebfd ST |
389 | { |
390 | if (dump_file) | |
391 | { | |
ca10595c | 392 | fprintf (dump_file, |
3c92da90 JL |
393 | "Tentatively merged extension with definition %s:\n", |
394 | (copy_needed) ? "(copy needed)" : ""); | |
87a0ebfd ST |
395 | print_rtl_single (dump_file, curr_insn); |
396 | } | |
397 | return true; | |
398 | } | |
282bc7b4 | 399 | |
87a0ebfd ST |
400 | return false; |
401 | } | |
402 | ||
87a0ebfd | 403 | /* Treat if_then_else insns, where the operands of both branches |
26cd9add | 404 | are registers, as copies. For instance, |
87a0ebfd ST |
405 | Original : |
406 | (set (reg:SI a) (if_then_else (cond) (reg:SI b) (reg:SI c))) | |
407 | Transformed : | |
408 | (set (reg:DI a) (if_then_else (cond) (reg:DI b) (reg:DI c))) | |
409 | DEF_INSN is the if_then_else insn. */ | |
410 | ||
411 | static bool | |
59a0c032 | 412 | transform_ifelse (ext_cand *cand, rtx_insn *def_insn) |
87a0ebfd ST |
413 | { |
414 | rtx set_insn = PATTERN (def_insn); | |
415 | rtx srcreg, dstreg, srcreg2; | |
416 | rtx map_srcreg, map_dstreg, map_srcreg2; | |
417 | rtx ifexpr; | |
418 | rtx cond; | |
419 | rtx new_set; | |
420 | ||
421 | gcc_assert (GET_CODE (set_insn) == SET); | |
282bc7b4 | 422 | |
87a0ebfd ST |
423 | cond = XEXP (SET_SRC (set_insn), 0); |
424 | dstreg = SET_DEST (set_insn); | |
425 | srcreg = XEXP (SET_SRC (set_insn), 1); | |
426 | srcreg2 = XEXP (SET_SRC (set_insn), 2); | |
b57cca0b JJ |
427 | /* If the conditional move already has the right or wider mode, |
428 | there is nothing to do. */ | |
429 | if (GET_MODE_SIZE (GET_MODE (dstreg)) >= GET_MODE_SIZE (cand->mode)) | |
430 | return true; | |
431 | ||
282bc7b4 EB |
432 | map_srcreg = gen_rtx_REG (cand->mode, REGNO (srcreg)); |
433 | map_srcreg2 = gen_rtx_REG (cand->mode, REGNO (srcreg2)); | |
434 | map_dstreg = gen_rtx_REG (cand->mode, REGNO (dstreg)); | |
435 | ifexpr = gen_rtx_IF_THEN_ELSE (cand->mode, cond, map_srcreg, map_srcreg2); | |
f7df4a84 | 436 | new_set = gen_rtx_SET (map_dstreg, ifexpr); |
87a0ebfd | 437 | |
73c49bf5 JJ |
438 | if (validate_change (def_insn, &PATTERN (def_insn), new_set, true) |
439 | && update_reg_equal_equiv_notes (def_insn, cand->mode, GET_MODE (dstreg), | |
440 | cand->code)) | |
87a0ebfd ST |
441 | { |
442 | if (dump_file) | |
443 | { | |
282bc7b4 EB |
444 | fprintf (dump_file, |
445 | "Mode of conditional move instruction extended:\n"); | |
87a0ebfd ST |
446 | print_rtl_single (dump_file, def_insn); |
447 | } | |
448 | return true; | |
449 | } | |
282bc7b4 EB |
450 | |
451 | return false; | |
87a0ebfd ST |
452 | } |
453 | ||
282bc7b4 EB |
454 | /* Get all the reaching definitions of an instruction. The definitions are |
455 | desired for REG used in INSN. Return the definition list or NULL if a | |
456 | definition is missing. If DEST is non-NULL, additionally push the INSN | |
457 | of the definitions onto DEST. */ | |
87a0ebfd | 458 | |
282bc7b4 | 459 | static struct df_link * |
59a0c032 | 460 | get_defs (rtx_insn *insn, rtx reg, vec<rtx_insn *> *dest) |
87a0ebfd | 461 | { |
bfac633a | 462 | df_ref use; |
282bc7b4 | 463 | struct df_link *ref_chain, *ref_link; |
87a0ebfd | 464 | |
bfac633a | 465 | FOR_EACH_INSN_USE (use, insn) |
87a0ebfd | 466 | { |
bfac633a | 467 | if (GET_CODE (DF_REF_REG (use)) == SUBREG) |
282bc7b4 | 468 | return NULL; |
bfac633a RS |
469 | if (REGNO (DF_REF_REG (use)) == REGNO (reg)) |
470 | break; | |
87a0ebfd ST |
471 | } |
472 | ||
bfac633a | 473 | gcc_assert (use != NULL); |
87a0ebfd | 474 | |
bfac633a | 475 | ref_chain = DF_REF_CHAIN (use); |
282bc7b4 EB |
476 | |
477 | for (ref_link = ref_chain; ref_link; ref_link = ref_link->next) | |
87a0ebfd ST |
478 | { |
479 | /* Problem getting some definition for this instruction. */ | |
282bc7b4 EB |
480 | if (ref_link->ref == NULL) |
481 | return NULL; | |
482 | if (DF_REF_INSN_INFO (ref_link->ref) == NULL) | |
483 | return NULL; | |
87a0ebfd ST |
484 | } |
485 | ||
282bc7b4 EB |
486 | if (dest) |
487 | for (ref_link = ref_chain; ref_link; ref_link = ref_link->next) | |
9771b263 | 488 | dest->safe_push (DF_REF_INSN (ref_link->ref)); |
87a0ebfd | 489 | |
282bc7b4 | 490 | return ref_chain; |
87a0ebfd ST |
491 | } |
492 | ||
282bc7b4 EB |
493 | /* Return true if INSN is |
494 | (SET (reg REGNO (def_reg)) (if_then_else (cond) (REG x1) (REG x2))) | |
495 | and store x1 and x2 in REG_1 and REG_2. */ | |
87a0ebfd | 496 | |
282bc7b4 | 497 | static bool |
59a0c032 | 498 | is_cond_copy_insn (rtx_insn *insn, rtx *reg1, rtx *reg2) |
87a0ebfd | 499 | { |
282bc7b4 | 500 | rtx expr = single_set (insn); |
87a0ebfd | 501 | |
282bc7b4 EB |
502 | if (expr != NULL_RTX |
503 | && GET_CODE (expr) == SET | |
87a0ebfd | 504 | && GET_CODE (SET_DEST (expr)) == REG |
87a0ebfd ST |
505 | && GET_CODE (SET_SRC (expr)) == IF_THEN_ELSE |
506 | && GET_CODE (XEXP (SET_SRC (expr), 1)) == REG | |
26cd9add | 507 | && GET_CODE (XEXP (SET_SRC (expr), 2)) == REG) |
87a0ebfd | 508 | { |
282bc7b4 EB |
509 | *reg1 = XEXP (SET_SRC (expr), 1); |
510 | *reg2 = XEXP (SET_SRC (expr), 2); | |
511 | return true; | |
87a0ebfd ST |
512 | } |
513 | ||
282bc7b4 | 514 | return false; |
87a0ebfd ST |
515 | } |
516 | ||
b57cca0b JJ |
517 | enum ext_modified_kind |
518 | { | |
519 | /* The insn hasn't been modified by ree pass yet. */ | |
520 | EXT_MODIFIED_NONE, | |
521 | /* Changed into zero extension. */ | |
522 | EXT_MODIFIED_ZEXT, | |
523 | /* Changed into sign extension. */ | |
524 | EXT_MODIFIED_SEXT | |
525 | }; | |
526 | ||
925e30ff | 527 | struct ATTRIBUTE_PACKED ext_modified |
b57cca0b JJ |
528 | { |
529 | /* Mode from which ree has zero or sign extended the destination. */ | |
530 | ENUM_BITFIELD(machine_mode) mode : 8; | |
531 | ||
532 | /* Kind of modification of the insn. */ | |
533 | ENUM_BITFIELD(ext_modified_kind) kind : 2; | |
534 | ||
0d732cca JL |
535 | unsigned int do_not_reextend : 1; |
536 | ||
b57cca0b JJ |
537 | /* True if the insn is scheduled to be deleted. */ |
538 | unsigned int deleted : 1; | |
539 | }; | |
540 | ||
541 | /* Vectors used by combine_reaching_defs and its helpers. */ | |
50686850 | 542 | struct ext_state |
b57cca0b | 543 | { |
9771b263 | 544 | /* In order to avoid constant alloc/free, we keep these |
b57cca0b | 545 | 4 vectors live through the entire find_and_remove_re and just |
9771b263 | 546 | truncate them each time. */ |
59a0c032 DM |
547 | vec<rtx_insn *> defs_list; |
548 | vec<rtx_insn *> copies_list; | |
549 | vec<rtx_insn *> modified_list; | |
550 | vec<rtx_insn *> work_list; | |
b57cca0b JJ |
551 | |
552 | /* For instructions that have been successfully modified, this is | |
553 | the original mode from which the insn is extending and | |
554 | kind of extension. */ | |
555 | struct ext_modified *modified; | |
50686850 | 556 | }; |
b57cca0b | 557 | |
26cd9add EI |
558 | /* Reaching Definitions of the extended register could be conditional copies |
559 | or regular definitions. This function separates the two types into two | |
b57cca0b JJ |
560 | lists, STATE->DEFS_LIST and STATE->COPIES_LIST. This is necessary because, |
561 | if a reaching definition is a conditional copy, merging the extension with | |
562 | this definition is wrong. Conditional copies are merged by transitively | |
563 | merging their definitions. The defs_list is populated with all the reaching | |
564 | definitions of the extension instruction (EXTEND_INSN) which must be merged | |
565 | with an extension. The copies_list contains all the conditional moves that | |
566 | will later be extended into a wider mode conditional move if all the merges | |
567 | are successful. The function returns false upon failure, true upon | |
568 | success. */ | |
569 | ||
570 | static bool | |
59a0c032 | 571 | make_defs_and_copies_lists (rtx_insn *extend_insn, const_rtx set_pat, |
b57cca0b | 572 | ext_state *state) |
87a0ebfd | 573 | { |
282bc7b4 | 574 | rtx src_reg = XEXP (SET_SRC (set_pat), 0); |
87a0ebfd | 575 | bool *is_insn_visited; |
b57cca0b JJ |
576 | bool ret = true; |
577 | ||
9771b263 | 578 | state->work_list.truncate (0); |
87a0ebfd | 579 | |
282bc7b4 | 580 | /* Initialize the work list. */ |
b57cca0b JJ |
581 | if (!get_defs (extend_insn, src_reg, &state->work_list)) |
582 | gcc_unreachable (); | |
87a0ebfd | 583 | |
282bc7b4 | 584 | is_insn_visited = XCNEWVEC (bool, max_insn_uid); |
87a0ebfd ST |
585 | |
586 | /* Perform transitive closure for conditional copies. */ | |
9771b263 | 587 | while (!state->work_list.is_empty ()) |
87a0ebfd | 588 | { |
59a0c032 | 589 | rtx_insn *def_insn = state->work_list.pop (); |
282bc7b4 EB |
590 | rtx reg1, reg2; |
591 | ||
87a0ebfd ST |
592 | gcc_assert (INSN_UID (def_insn) < max_insn_uid); |
593 | ||
594 | if (is_insn_visited[INSN_UID (def_insn)]) | |
282bc7b4 | 595 | continue; |
87a0ebfd | 596 | is_insn_visited[INSN_UID (def_insn)] = true; |
87a0ebfd | 597 | |
282bc7b4 EB |
598 | if (is_cond_copy_insn (def_insn, ®1, ®2)) |
599 | { | |
600 | /* Push it onto the copy list first. */ | |
9771b263 | 601 | state->copies_list.safe_push (def_insn); |
282bc7b4 EB |
602 | |
603 | /* Now perform the transitive closure. */ | |
b57cca0b JJ |
604 | if (!get_defs (def_insn, reg1, &state->work_list) |
605 | || !get_defs (def_insn, reg2, &state->work_list)) | |
282bc7b4 | 606 | { |
b57cca0b | 607 | ret = false; |
282bc7b4 EB |
608 | break; |
609 | } | |
87a0ebfd ST |
610 | } |
611 | else | |
9771b263 | 612 | state->defs_list.safe_push (def_insn); |
87a0ebfd ST |
613 | } |
614 | ||
87a0ebfd | 615 | XDELETEVEC (is_insn_visited); |
282bc7b4 EB |
616 | |
617 | return ret; | |
87a0ebfd ST |
618 | } |
619 | ||
650c4c85 JL |
620 | /* If DEF_INSN has single SET expression, possibly buried inside |
621 | a PARALLEL, return the address of the SET expression, else | |
622 | return NULL. This is similar to single_set, except that | |
623 | single_set allows multiple SETs when all but one is dead. */ | |
624 | static rtx * | |
59a0c032 | 625 | get_sub_rtx (rtx_insn *def_insn) |
87a0ebfd | 626 | { |
650c4c85 JL |
627 | enum rtx_code code = GET_CODE (PATTERN (def_insn)); |
628 | rtx *sub_rtx = NULL; | |
87a0ebfd ST |
629 | |
630 | if (code == PARALLEL) | |
631 | { | |
650c4c85 | 632 | for (int i = 0; i < XVECLEN (PATTERN (def_insn), 0); i++) |
87a0ebfd | 633 | { |
650c4c85 | 634 | rtx s_expr = XVECEXP (PATTERN (def_insn), 0, i); |
87a0ebfd ST |
635 | if (GET_CODE (s_expr) != SET) |
636 | continue; | |
637 | ||
638 | if (sub_rtx == NULL) | |
639 | sub_rtx = &XVECEXP (PATTERN (def_insn), 0, i); | |
640 | else | |
641 | { | |
642 | /* PARALLEL with multiple SETs. */ | |
650c4c85 | 643 | return NULL; |
87a0ebfd ST |
644 | } |
645 | } | |
646 | } | |
647 | else if (code == SET) | |
648 | sub_rtx = &PATTERN (def_insn); | |
649 | else | |
650 | { | |
651 | /* It is not a PARALLEL or a SET, what could it be ? */ | |
650c4c85 | 652 | return NULL; |
87a0ebfd ST |
653 | } |
654 | ||
655 | gcc_assert (sub_rtx != NULL); | |
650c4c85 JL |
656 | return sub_rtx; |
657 | } | |
658 | ||
659 | /* Merge the DEF_INSN with an extension. Calls combine_set_extension | |
660 | on the SET pattern. */ | |
661 | ||
662 | static bool | |
59a0c032 | 663 | merge_def_and_ext (ext_cand *cand, rtx_insn *def_insn, ext_state *state) |
650c4c85 | 664 | { |
ef4bddc2 | 665 | machine_mode ext_src_mode; |
650c4c85 JL |
666 | rtx *sub_rtx; |
667 | ||
668 | ext_src_mode = GET_MODE (XEXP (SET_SRC (cand->expr), 0)); | |
669 | sub_rtx = get_sub_rtx (def_insn); | |
670 | ||
671 | if (sub_rtx == NULL) | |
672 | return false; | |
87a0ebfd | 673 | |
b57cca0b JJ |
674 | if (REG_P (SET_DEST (*sub_rtx)) |
675 | && (GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode | |
676 | || ((state->modified[INSN_UID (def_insn)].kind | |
677 | == (cand->code == ZERO_EXTEND | |
678 | ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT)) | |
679 | && state->modified[INSN_UID (def_insn)].mode | |
680 | == ext_src_mode))) | |
87a0ebfd | 681 | { |
b57cca0b JJ |
682 | if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx))) |
683 | >= GET_MODE_SIZE (cand->mode)) | |
684 | return true; | |
685 | /* If def_insn is already scheduled to be deleted, don't attempt | |
686 | to modify it. */ | |
687 | if (state->modified[INSN_UID (def_insn)].deleted) | |
688 | return false; | |
689 | if (combine_set_extension (cand, def_insn, sub_rtx)) | |
690 | { | |
691 | if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE) | |
692 | state->modified[INSN_UID (def_insn)].mode = ext_src_mode; | |
693 | return true; | |
694 | } | |
87a0ebfd | 695 | } |
26cd9add EI |
696 | |
697 | return false; | |
87a0ebfd ST |
698 | } |
699 | ||
059742a4 JL |
700 | /* Given SRC, which should be one or more extensions of a REG, strip |
701 | away the extensions and return the REG. */ | |
702 | ||
703 | static inline rtx | |
704 | get_extended_src_reg (rtx src) | |
705 | { | |
706 | while (GET_CODE (src) == SIGN_EXTEND || GET_CODE (src) == ZERO_EXTEND) | |
707 | src = XEXP (src, 0); | |
708 | gcc_assert (REG_P (src)); | |
709 | return src; | |
710 | } | |
711 | ||
87a0ebfd | 712 | /* This function goes through all reaching defs of the source |
26cd9add EI |
713 | of the candidate for elimination (CAND) and tries to combine |
714 | the extension with the definition instruction. The changes | |
715 | are made as a group so that even if one definition cannot be | |
716 | merged, all reaching definitions end up not being merged. | |
717 | When a conditional copy is encountered, merging is attempted | |
718 | transitively on its definitions. It returns true upon success | |
719 | and false upon failure. */ | |
87a0ebfd ST |
720 | |
721 | static bool | |
089dacc5 | 722 | combine_reaching_defs (ext_cand *cand, const_rtx set_pat, ext_state *state) |
87a0ebfd | 723 | { |
59a0c032 | 724 | rtx_insn *def_insn; |
87a0ebfd ST |
725 | bool merge_successful = true; |
726 | int i; | |
727 | int defs_ix; | |
b57cca0b | 728 | bool outcome; |
87a0ebfd | 729 | |
9771b263 DN |
730 | state->defs_list.truncate (0); |
731 | state->copies_list.truncate (0); | |
87a0ebfd | 732 | |
b57cca0b | 733 | outcome = make_defs_and_copies_lists (cand->insn, set_pat, state); |
87a0ebfd | 734 | |
b57cca0b JJ |
735 | if (!outcome) |
736 | return false; | |
87a0ebfd | 737 | |
3c92da90 JL |
738 | /* If the destination operand of the extension is a different |
739 | register than the source operand, then additional restrictions | |
059742a4 JL |
740 | are needed. Note we have to handle cases where we have nested |
741 | extensions in the source operand. */ | |
0d732cca JL |
742 | bool copy_needed |
743 | = (REGNO (SET_DEST (PATTERN (cand->insn))) | |
744 | != REGNO (get_extended_src_reg (SET_SRC (PATTERN (cand->insn))))); | |
745 | if (copy_needed) | |
3c92da90 | 746 | { |
860dadcb JJ |
747 | /* Considering transformation of |
748 | (set (reg1) (expression)) | |
749 | ... | |
750 | (set (reg2) (any_extend (reg1))) | |
751 | ||
752 | into | |
753 | ||
754 | (set (reg2) (any_extend (expression))) | |
755 | (set (reg1) (reg2)) | |
756 | ... */ | |
757 | ||
3c92da90 JL |
758 | /* In theory we could handle more than one reaching def, it |
759 | just makes the code to update the insn stream more complex. */ | |
760 | if (state->defs_list.length () != 1) | |
761 | return false; | |
762 | ||
8632824e KT |
763 | /* We don't have the structure described above if there are |
764 | conditional moves in between the def and the candidate, | |
765 | and we will not handle them correctly. See PR68194. */ | |
766 | if (state->copies_list.length () > 0) | |
767 | return false; | |
768 | ||
059742a4 JL |
769 | /* We require the candidate not already be modified. It may, |
770 | for example have been changed from a (sign_extend (reg)) | |
0d732cca | 771 | into (zero_extend (sign_extend (reg))). |
059742a4 JL |
772 | |
773 | Handling that case shouldn't be terribly difficult, but the code | |
774 | here and the code to emit copies would need auditing. Until | |
775 | we see a need, this is the safe thing to do. */ | |
3c92da90 JL |
776 | if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE) |
777 | return false; | |
778 | ||
ef4bddc2 | 779 | machine_mode dst_mode = GET_MODE (SET_DEST (PATTERN (cand->insn))); |
e533e26c WD |
780 | rtx src_reg = get_extended_src_reg (SET_SRC (PATTERN (cand->insn))); |
781 | ||
782 | /* Ensure the number of hard registers of the copy match. */ | |
783 | if (HARD_REGNO_NREGS (REGNO (src_reg), dst_mode) | |
784 | != HARD_REGNO_NREGS (REGNO (src_reg), GET_MODE (src_reg))) | |
785 | return false; | |
786 | ||
3c92da90 | 787 | /* There's only one reaching def. */ |
59a0c032 | 788 | rtx_insn *def_insn = state->defs_list[0]; |
3c92da90 JL |
789 | |
790 | /* The defining statement must not have been modified either. */ | |
791 | if (state->modified[INSN_UID (def_insn)].kind != EXT_MODIFIED_NONE) | |
792 | return false; | |
793 | ||
794 | /* The defining statement and candidate insn must be in the same block. | |
795 | This is merely to keep the test for safety and updating the insn | |
7e41c852 JL |
796 | stream simple. Also ensure that within the block the candidate |
797 | follows the defining insn. */ | |
daca1a96 RS |
798 | basic_block bb = BLOCK_FOR_INSN (cand->insn); |
799 | if (bb != BLOCK_FOR_INSN (def_insn) | |
7e41c852 | 800 | || DF_INSN_LUID (def_insn) > DF_INSN_LUID (cand->insn)) |
3c92da90 JL |
801 | return false; |
802 | ||
803 | /* If there is an overlap between the destination of DEF_INSN and | |
804 | CAND->insn, then this transformation is not safe. Note we have | |
805 | to test in the widened mode. */ | |
650c4c85 JL |
806 | rtx *dest_sub_rtx = get_sub_rtx (def_insn); |
807 | if (dest_sub_rtx == NULL | |
808 | || !REG_P (SET_DEST (*dest_sub_rtx))) | |
809 | return false; | |
810 | ||
3c92da90 | 811 | rtx tmp_reg = gen_rtx_REG (GET_MODE (SET_DEST (PATTERN (cand->insn))), |
650c4c85 | 812 | REGNO (SET_DEST (*dest_sub_rtx))); |
3c92da90 JL |
813 | if (reg_overlap_mentioned_p (tmp_reg, SET_DEST (PATTERN (cand->insn)))) |
814 | return false; | |
815 | ||
816 | /* The destination register of the extension insn must not be | |
817 | used or set between the def_insn and cand->insn exclusive. */ | |
818 | if (reg_used_between_p (SET_DEST (PATTERN (cand->insn)), | |
819 | def_insn, cand->insn) | |
820 | || reg_set_between_p (SET_DEST (PATTERN (cand->insn)), | |
821 | def_insn, cand->insn)) | |
822 | return false; | |
0d732cca JL |
823 | |
824 | /* We must be able to copy between the two registers. Generate, | |
825 | recognize and verify constraints of the copy. Also fail if this | |
826 | generated more than one insn. | |
827 | ||
828 | This generates garbage since we throw away the insn when we're | |
c7ece684 JL |
829 | done, only to recreate it later if this test was successful. |
830 | ||
831 | Make sure to get the mode from the extension (cand->insn). This | |
832 | is different than in the code to emit the copy as we have not | |
833 | modified the defining insn yet. */ | |
0d732cca | 834 | start_sequence (); |
0d732cca | 835 | rtx pat = PATTERN (cand->insn); |
c7ece684 | 836 | rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (pat)), |
e533e26c | 837 | REGNO (get_extended_src_reg (SET_SRC (pat)))); |
c7ece684 | 838 | rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (pat)), |
0d732cca JL |
839 | REGNO (SET_DEST (pat))); |
840 | emit_move_insn (new_dst, new_src); | |
841 | ||
b32d5189 | 842 | rtx_insn *insn = get_insns(); |
0d732cca JL |
843 | end_sequence (); |
844 | if (NEXT_INSN (insn)) | |
845 | return false; | |
846 | if (recog_memoized (insn) == -1) | |
847 | return false; | |
848 | extract_insn (insn); | |
daca1a96 | 849 | if (!constrain_operands (1, get_preferred_alternatives (insn, bb))) |
0d732cca | 850 | return false; |
3c92da90 JL |
851 | } |
852 | ||
853 | ||
6aae324c JJ |
854 | /* If cand->insn has been already modified, update cand->mode to a wider |
855 | mode if possible, or punt. */ | |
856 | if (state->modified[INSN_UID (cand->insn)].kind != EXT_MODIFIED_NONE) | |
857 | { | |
ef4bddc2 | 858 | machine_mode mode; |
6aae324c JJ |
859 | rtx set; |
860 | ||
861 | if (state->modified[INSN_UID (cand->insn)].kind | |
862 | != (cand->code == ZERO_EXTEND | |
863 | ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT) | |
864 | || state->modified[INSN_UID (cand->insn)].mode != cand->mode | |
865 | || (set = single_set (cand->insn)) == NULL_RTX) | |
866 | return false; | |
867 | mode = GET_MODE (SET_DEST (set)); | |
868 | gcc_assert (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (cand->mode)); | |
869 | cand->mode = mode; | |
870 | } | |
871 | ||
87a0ebfd ST |
872 | merge_successful = true; |
873 | ||
874 | /* Go through the defs vector and try to merge all the definitions | |
875 | in this vector. */ | |
9771b263 DN |
876 | state->modified_list.truncate (0); |
877 | FOR_EACH_VEC_ELT (state->defs_list, defs_ix, def_insn) | |
87a0ebfd | 878 | { |
b57cca0b | 879 | if (merge_def_and_ext (cand, def_insn, state)) |
9771b263 | 880 | state->modified_list.safe_push (def_insn); |
87a0ebfd ST |
881 | else |
882 | { | |
883 | merge_successful = false; | |
884 | break; | |
885 | } | |
886 | } | |
887 | ||
888 | /* Now go through the conditional copies vector and try to merge all | |
889 | the copies in this vector. */ | |
87a0ebfd ST |
890 | if (merge_successful) |
891 | { | |
9771b263 | 892 | FOR_EACH_VEC_ELT (state->copies_list, i, def_insn) |
87a0ebfd | 893 | { |
26cd9add | 894 | if (transform_ifelse (cand, def_insn)) |
9771b263 | 895 | state->modified_list.safe_push (def_insn); |
87a0ebfd ST |
896 | else |
897 | { | |
898 | merge_successful = false; | |
899 | break; | |
900 | } | |
901 | } | |
902 | } | |
903 | ||
904 | if (merge_successful) | |
905 | { | |
282bc7b4 EB |
906 | /* Commit the changes here if possible |
907 | FIXME: It's an all-or-nothing scenario. Even if only one definition | |
908 | cannot be merged, we entirely give up. In the future, we should allow | |
909 | extensions to be partially eliminated along those paths where the | |
910 | definitions could be merged. */ | |
87a0ebfd ST |
911 | if (apply_change_group ()) |
912 | { | |
913 | if (dump_file) | |
282bc7b4 | 914 | fprintf (dump_file, "All merges were successful.\n"); |
87a0ebfd | 915 | |
9771b263 | 916 | FOR_EACH_VEC_ELT (state->modified_list, i, def_insn) |
0d732cca JL |
917 | { |
918 | ext_modified *modified = &state->modified[INSN_UID (def_insn)]; | |
919 | if (modified->kind == EXT_MODIFIED_NONE) | |
920 | modified->kind = (cand->code == ZERO_EXTEND ? EXT_MODIFIED_ZEXT | |
921 | : EXT_MODIFIED_SEXT); | |
b57cca0b | 922 | |
0d732cca JL |
923 | if (copy_needed) |
924 | modified->do_not_reextend = 1; | |
925 | } | |
87a0ebfd ST |
926 | return true; |
927 | } | |
928 | else | |
929 | { | |
0acba2b4 EB |
930 | /* Changes need not be cancelled explicitly as apply_change_group |
931 | does it. Print list of definitions in the dump_file for debug | |
26cd9add | 932 | purposes. This extension cannot be deleted. */ |
87a0ebfd ST |
933 | if (dump_file) |
934 | { | |
ca10595c EB |
935 | fprintf (dump_file, |
936 | "Merge cancelled, non-mergeable definitions:\n"); | |
9771b263 | 937 | FOR_EACH_VEC_ELT (state->modified_list, i, def_insn) |
ca10595c | 938 | print_rtl_single (dump_file, def_insn); |
87a0ebfd ST |
939 | } |
940 | } | |
941 | } | |
942 | else | |
943 | { | |
944 | /* Cancel any changes that have been made so far. */ | |
945 | cancel_changes (0); | |
946 | } | |
947 | ||
87a0ebfd ST |
948 | return false; |
949 | } | |
950 | ||
089dacc5 | 951 | /* Add an extension pattern that could be eliminated. */ |
0acba2b4 EB |
952 | |
953 | static void | |
59a0c032 | 954 | add_removable_extension (const_rtx expr, rtx_insn *insn, |
9771b263 | 955 | vec<ext_cand> *insn_list, |
524d9b4b PMR |
956 | unsigned *def_map, |
957 | bitmap init_regs) | |
0acba2b4 | 958 | { |
282bc7b4 | 959 | enum rtx_code code; |
ef4bddc2 | 960 | machine_mode mode; |
68c8a824 | 961 | unsigned int idx; |
0acba2b4 EB |
962 | rtx src, dest; |
963 | ||
282bc7b4 | 964 | /* We are looking for SET (REG N) (ANY_EXTEND (REG N)). */ |
0acba2b4 EB |
965 | if (GET_CODE (expr) != SET) |
966 | return; | |
967 | ||
968 | src = SET_SRC (expr); | |
282bc7b4 | 969 | code = GET_CODE (src); |
0acba2b4 | 970 | dest = SET_DEST (expr); |
282bc7b4 | 971 | mode = GET_MODE (dest); |
0acba2b4 EB |
972 | |
973 | if (REG_P (dest) | |
282bc7b4 | 974 | && (code == SIGN_EXTEND || code == ZERO_EXTEND) |
3c92da90 | 975 | && REG_P (XEXP (src, 0))) |
0acba2b4 | 976 | { |
524d9b4b | 977 | rtx reg = XEXP (src, 0); |
282bc7b4 EB |
978 | struct df_link *defs, *def; |
979 | ext_cand *cand; | |
980 | ||
524d9b4b PMR |
981 | /* Zero-extension of an undefined value is partly defined (it's |
982 | completely undefined for sign-extension, though). So if there exists | |
983 | a path from the entry to this zero-extension that leaves this register | |
984 | uninitialized, removing the extension could change the behavior of | |
985 | correct programs. So first, check it is not the case. */ | |
986 | if (code == ZERO_EXTEND && !bitmap_bit_p (init_regs, REGNO (reg))) | |
987 | { | |
988 | if (dump_file) | |
989 | { | |
990 | fprintf (dump_file, "Cannot eliminate extension:\n"); | |
991 | print_rtl_single (dump_file, insn); | |
992 | fprintf (dump_file, " because it can operate on uninitialized" | |
993 | " data\n"); | |
994 | } | |
995 | return; | |
996 | } | |
997 | ||
998 | /* Second, make sure we can get all the reaching definitions. */ | |
999 | defs = get_defs (insn, reg, NULL); | |
282bc7b4 | 1000 | if (!defs) |
0acba2b4 | 1001 | { |
282bc7b4 EB |
1002 | if (dump_file) |
1003 | { | |
1004 | fprintf (dump_file, "Cannot eliminate extension:\n"); | |
089dacc5 | 1005 | print_rtl_single (dump_file, insn); |
282bc7b4 EB |
1006 | fprintf (dump_file, " because of missing definition(s)\n"); |
1007 | } | |
1008 | return; | |
0acba2b4 | 1009 | } |
282bc7b4 | 1010 | |
524d9b4b | 1011 | /* Third, make sure the reaching definitions don't feed another and |
282bc7b4 EB |
1012 | different extension. FIXME: this obviously can be improved. */ |
1013 | for (def = defs; def; def = def->next) | |
c3284718 | 1014 | if ((idx = def_map[INSN_UID (DF_REF_INSN (def->ref))]) |
860dadcb | 1015 | && idx != -1U |
9771b263 | 1016 | && (cand = &(*insn_list)[idx - 1]) |
ca3f371f | 1017 | && cand->code != code) |
282bc7b4 EB |
1018 | { |
1019 | if (dump_file) | |
1020 | { | |
1021 | fprintf (dump_file, "Cannot eliminate extension:\n"); | |
089dacc5 | 1022 | print_rtl_single (dump_file, insn); |
282bc7b4 EB |
1023 | fprintf (dump_file, " because of other extension\n"); |
1024 | } | |
1025 | return; | |
1026 | } | |
860dadcb JJ |
1027 | /* For vector mode extensions, ensure that all uses of the |
1028 | XEXP (src, 0) register are the same extension (both code | |
1029 | and to which mode), as unlike integral extensions lowpart | |
1030 | subreg of the sign/zero extended register are not equal | |
1031 | to the original register, so we have to change all uses or | |
1032 | none. */ | |
1033 | else if (VECTOR_MODE_P (GET_MODE (XEXP (src, 0)))) | |
1034 | { | |
1035 | if (idx == 0) | |
1036 | { | |
1037 | struct df_link *ref_chain, *ref_link; | |
1038 | ||
1039 | ref_chain = DF_REF_CHAIN (def->ref); | |
1040 | for (ref_link = ref_chain; ref_link; ref_link = ref_link->next) | |
1041 | { | |
1042 | if (ref_link->ref == NULL | |
1043 | || DF_REF_INSN_INFO (ref_link->ref) == NULL) | |
1044 | { | |
1045 | idx = -1U; | |
1046 | break; | |
1047 | } | |
1048 | rtx_insn *use_insn = DF_REF_INSN (ref_link->ref); | |
1049 | const_rtx use_set; | |
1050 | if (use_insn == insn || DEBUG_INSN_P (use_insn)) | |
1051 | continue; | |
1052 | if (!(use_set = single_set (use_insn)) | |
1053 | || !REG_P (SET_DEST (use_set)) | |
1054 | || GET_MODE (SET_DEST (use_set)) != GET_MODE (dest) | |
1055 | || GET_CODE (SET_SRC (use_set)) != code | |
1056 | || !rtx_equal_p (XEXP (SET_SRC (use_set), 0), | |
1057 | XEXP (src, 0))) | |
1058 | { | |
1059 | idx = -1U; | |
1060 | break; | |
1061 | } | |
1062 | } | |
1063 | if (idx == -1U) | |
1064 | def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx; | |
1065 | } | |
1066 | if (idx == -1U) | |
1067 | { | |
1068 | if (dump_file) | |
1069 | { | |
1070 | fprintf (dump_file, "Cannot eliminate extension:\n"); | |
1071 | print_rtl_single (dump_file, insn); | |
1072 | fprintf (dump_file, | |
1073 | " because some vector uses aren't extension\n"); | |
1074 | } | |
1075 | return; | |
1076 | } | |
1077 | } | |
282bc7b4 | 1078 | |
d2c9e8ed NC |
1079 | /* Fourth, if the extended version occupies more registers than the |
1080 | original and the source of the extension is the same hard register | |
1081 | as the destination of the extension, then we can not eliminate | |
1082 | the extension without deep analysis, so just punt. | |
1083 | ||
1084 | We allow this when the registers are different because the | |
1085 | code in combine_reaching_defs will handle that case correctly. */ | |
1086 | if ((HARD_REGNO_NREGS (REGNO (dest), mode) | |
1087 | != HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg))) | |
60b5526f | 1088 | && reg_overlap_mentioned_p (dest, reg)) |
d2c9e8ed NC |
1089 | return; |
1090 | ||
282bc7b4 EB |
1091 | /* Then add the candidate to the list and insert the reaching definitions |
1092 | into the definition map. */ | |
f32682ca | 1093 | ext_cand e = {expr, code, mode, insn}; |
9771b263 DN |
1094 | insn_list->safe_push (e); |
1095 | idx = insn_list->length (); | |
282bc7b4 EB |
1096 | |
1097 | for (def = defs; def; def = def->next) | |
c3284718 | 1098 | def_map[INSN_UID (DF_REF_INSN (def->ref))] = idx; |
0acba2b4 EB |
1099 | } |
1100 | } | |
1101 | ||
26cd9add | 1102 | /* Traverse the instruction stream looking for extensions and return the |
0acba2b4 | 1103 | list of candidates. */ |
87a0ebfd | 1104 | |
9771b263 | 1105 | static vec<ext_cand> |
26cd9add | 1106 | find_removable_extensions (void) |
87a0ebfd | 1107 | { |
6e1aa848 | 1108 | vec<ext_cand> insn_list = vNULL; |
0acba2b4 | 1109 | basic_block bb; |
59a0c032 DM |
1110 | rtx_insn *insn; |
1111 | rtx set; | |
68c8a824 | 1112 | unsigned *def_map = XCNEWVEC (unsigned, max_insn_uid); |
524d9b4b PMR |
1113 | bitmap_head init, kill, gen, tmp; |
1114 | ||
1115 | bitmap_initialize (&init, NULL); | |
1116 | bitmap_initialize (&kill, NULL); | |
1117 | bitmap_initialize (&gen, NULL); | |
1118 | bitmap_initialize (&tmp, NULL); | |
87a0ebfd | 1119 | |
11cd3bed | 1120 | FOR_EACH_BB_FN (bb, cfun) |
524d9b4b PMR |
1121 | { |
1122 | bitmap_copy (&init, DF_MIR_IN (bb)); | |
1123 | bitmap_clear (&kill); | |
1124 | bitmap_clear (&gen); | |
87a0ebfd | 1125 | |
524d9b4b PMR |
1126 | FOR_BB_INSNS (bb, insn) |
1127 | { | |
1128 | if (NONDEBUG_INSN_P (insn)) | |
1129 | { | |
1130 | set = single_set (insn); | |
1131 | if (set != NULL_RTX) | |
1132 | add_removable_extension (set, insn, &insn_list, def_map, | |
1133 | &init); | |
1134 | df_mir_simulate_one_insn (bb, insn, &kill, &gen); | |
1135 | bitmap_ior_and_compl (&tmp, &gen, &init, &kill); | |
1136 | bitmap_copy (&init, &tmp); | |
1137 | } | |
1138 | } | |
1139 | } | |
0acba2b4 | 1140 | |
089dacc5 | 1141 | XDELETEVEC (def_map); |
282bc7b4 | 1142 | |
089dacc5 | 1143 | return insn_list; |
87a0ebfd ST |
1144 | } |
1145 | ||
1146 | /* This is the main function that checks the insn stream for redundant | |
26cd9add | 1147 | extensions and tries to remove them if possible. */ |
87a0ebfd | 1148 | |
282bc7b4 | 1149 | static void |
26cd9add | 1150 | find_and_remove_re (void) |
87a0ebfd | 1151 | { |
282bc7b4 | 1152 | ext_cand *curr_cand; |
59a0c032 | 1153 | rtx_insn *curr_insn = NULL; |
282bc7b4 | 1154 | int num_re_opportunities = 0, num_realized = 0, i; |
9771b263 | 1155 | vec<ext_cand> reinsn_list; |
59a0c032 DM |
1156 | auto_vec<rtx_insn *> reinsn_del_list; |
1157 | auto_vec<rtx_insn *> reinsn_copy_list; | |
b57cca0b | 1158 | ext_state state; |
87a0ebfd ST |
1159 | |
1160 | /* Construct DU chain to get all reaching definitions of each | |
26cd9add | 1161 | extension instruction. */ |
7b19209f | 1162 | df_set_flags (DF_RD_PRUNE_DEAD_DEFS); |
87a0ebfd | 1163 | df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN); |
524d9b4b | 1164 | df_mir_add_problem (); |
87a0ebfd | 1165 | df_analyze (); |
b57cca0b | 1166 | df_set_flags (DF_DEFER_INSN_RESCAN); |
87a0ebfd ST |
1167 | |
1168 | max_insn_uid = get_max_uid (); | |
26cd9add | 1169 | reinsn_list = find_removable_extensions (); |
9771b263 DN |
1170 | state.defs_list.create (0); |
1171 | state.copies_list.create (0); | |
1172 | state.modified_list.create (0); | |
1173 | state.work_list.create (0); | |
1174 | if (reinsn_list.is_empty ()) | |
b57cca0b JJ |
1175 | state.modified = NULL; |
1176 | else | |
1177 | state.modified = XCNEWVEC (struct ext_modified, max_insn_uid); | |
87a0ebfd | 1178 | |
9771b263 | 1179 | FOR_EACH_VEC_ELT (reinsn_list, i, curr_cand) |
87a0ebfd | 1180 | { |
26cd9add | 1181 | num_re_opportunities++; |
87a0ebfd | 1182 | |
282bc7b4 | 1183 | /* Try to combine the extension with the definition. */ |
87a0ebfd ST |
1184 | if (dump_file) |
1185 | { | |
282bc7b4 EB |
1186 | fprintf (dump_file, "Trying to eliminate extension:\n"); |
1187 | print_rtl_single (dump_file, curr_cand->insn); | |
87a0ebfd ST |
1188 | } |
1189 | ||
089dacc5 | 1190 | if (combine_reaching_defs (curr_cand, curr_cand->expr, &state)) |
87a0ebfd ST |
1191 | { |
1192 | if (dump_file) | |
282bc7b4 | 1193 | fprintf (dump_file, "Eliminated the extension.\n"); |
87a0ebfd | 1194 | num_realized++; |
059742a4 JL |
1195 | /* If the RHS of the current candidate is not (extend (reg)), then |
1196 | we do not allow the optimization of extensions where | |
1197 | the source and destination registers do not match. Thus | |
1198 | checking REG_P here is correct. */ | |
1199 | if (REG_P (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0)) | |
1200 | && (REGNO (SET_DEST (PATTERN (curr_cand->insn))) | |
1201 | != REGNO (XEXP (SET_SRC (PATTERN (curr_cand->insn)), 0)))) | |
3c92da90 JL |
1202 | { |
1203 | reinsn_copy_list.safe_push (curr_cand->insn); | |
1204 | reinsn_copy_list.safe_push (state.defs_list[0]); | |
1205 | } | |
1206 | reinsn_del_list.safe_push (curr_cand->insn); | |
b57cca0b | 1207 | state.modified[INSN_UID (curr_cand->insn)].deleted = 1; |
87a0ebfd ST |
1208 | } |
1209 | } | |
1210 | ||
3c92da90 JL |
1211 | /* The copy list contains pairs of insns which describe copies we |
1212 | need to insert into the INSN stream. | |
1213 | ||
1214 | The first insn in each pair is the extension insn, from which | |
1215 | we derive the source and destination of the copy. | |
1216 | ||
1217 | The second insn in each pair is the memory reference where the | |
1218 | extension will ultimately happen. We emit the new copy | |
1219 | immediately after this insn. | |
1220 | ||
1221 | It may first appear that the arguments for the copy are reversed. | |
1222 | Remember that the memory reference will be changed to refer to the | |
1223 | destination of the extention. So we're actually emitting a copy | |
1224 | from the new destination to the old destination. */ | |
1225 | for (unsigned int i = 0; i < reinsn_copy_list.length (); i += 2) | |
1226 | { | |
59a0c032 DM |
1227 | rtx_insn *curr_insn = reinsn_copy_list[i]; |
1228 | rtx_insn *def_insn = reinsn_copy_list[i + 1]; | |
a6a2d67b JL |
1229 | |
1230 | /* Use the mode of the destination of the defining insn | |
1231 | for the mode of the copy. This is necessary if the | |
1232 | defining insn was used to eliminate a second extension | |
1233 | that was wider than the first. */ | |
1234 | rtx sub_rtx = *get_sub_rtx (def_insn); | |
3c92da90 | 1235 | rtx pat = PATTERN (curr_insn); |
a6a2d67b | 1236 | rtx new_dst = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)), |
3c92da90 | 1237 | REGNO (XEXP (SET_SRC (pat), 0))); |
a6a2d67b JL |
1238 | rtx new_src = gen_rtx_REG (GET_MODE (SET_DEST (sub_rtx)), |
1239 | REGNO (SET_DEST (pat))); | |
f7df4a84 | 1240 | rtx set = gen_rtx_SET (new_dst, new_src); |
a6a2d67b | 1241 | emit_insn_after (set, def_insn); |
3c92da90 JL |
1242 | } |
1243 | ||
26cd9add | 1244 | /* Delete all useless extensions here in one sweep. */ |
9771b263 | 1245 | FOR_EACH_VEC_ELT (reinsn_del_list, i, curr_insn) |
0acba2b4 | 1246 | delete_insn (curr_insn); |
87a0ebfd | 1247 | |
9771b263 | 1248 | reinsn_list.release (); |
9771b263 DN |
1249 | state.defs_list.release (); |
1250 | state.copies_list.release (); | |
1251 | state.modified_list.release (); | |
1252 | state.work_list.release (); | |
b57cca0b | 1253 | XDELETEVEC (state.modified); |
87a0ebfd | 1254 | |
26cd9add | 1255 | if (dump_file && num_re_opportunities > 0) |
282bc7b4 EB |
1256 | fprintf (dump_file, "Elimination opportunities = %d realized = %d\n", |
1257 | num_re_opportunities, num_realized); | |
87a0ebfd ST |
1258 | } |
1259 | ||
26cd9add | 1260 | /* Find and remove redundant extensions. */ |
87a0ebfd ST |
1261 | |
1262 | static unsigned int | |
26cd9add | 1263 | rest_of_handle_ree (void) |
87a0ebfd | 1264 | { |
26cd9add EI |
1265 | timevar_push (TV_REE); |
1266 | find_and_remove_re (); | |
1267 | timevar_pop (TV_REE); | |
87a0ebfd ST |
1268 | return 0; |
1269 | } | |
1270 | ||
27a4cd48 DM |
1271 | namespace { |
1272 | ||
1273 | const pass_data pass_data_ree = | |
87a0ebfd | 1274 | { |
27a4cd48 DM |
1275 | RTL_PASS, /* type */ |
1276 | "ree", /* name */ | |
1277 | OPTGROUP_NONE, /* optinfo_flags */ | |
27a4cd48 DM |
1278 | TV_REE, /* tv_id */ |
1279 | 0, /* properties_required */ | |
1280 | 0, /* properties_provided */ | |
1281 | 0, /* properties_destroyed */ | |
1282 | 0, /* todo_flags_start */ | |
3bea341f | 1283 | TODO_df_finish, /* todo_flags_finish */ |
87a0ebfd | 1284 | }; |
27a4cd48 DM |
1285 | |
1286 | class pass_ree : public rtl_opt_pass | |
1287 | { | |
1288 | public: | |
c3284718 RS |
1289 | pass_ree (gcc::context *ctxt) |
1290 | : rtl_opt_pass (pass_data_ree, ctxt) | |
27a4cd48 DM |
1291 | {} |
1292 | ||
1293 | /* opt_pass methods: */ | |
1a3d085c | 1294 | virtual bool gate (function *) { return (optimize > 0 && flag_ree); } |
be55bfe6 | 1295 | virtual unsigned int execute (function *) { return rest_of_handle_ree (); } |
27a4cd48 DM |
1296 | |
1297 | }; // class pass_ree | |
1298 | ||
1299 | } // anon namespace | |
1300 | ||
1301 | rtl_opt_pass * | |
1302 | make_pass_ree (gcc::context *ctxt) | |
1303 | { | |
1304 | return new pass_ree (ctxt); | |
1305 | } |