]>
Commit | Line | Data |
---|---|---|
ac973375 | 1 | /* An SH specific RTL pass that tries to optimize clrt and sett insns. |
5624e564 | 2 | Copyright (C) 2013-2015 Free Software Foundation, Inc. |
ac973375 OE |
3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 3, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING3. If not see | |
18 | <http://www.gnu.org/licenses/>. */ | |
19 | ||
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
c7131fb2 | 23 | #include "backend.h" |
e11c4407 | 24 | #include "target.h" |
c7131fb2 AM |
25 | #include "rtl.h" |
26 | #include "df.h" | |
60393bbc | 27 | #include "cfgrtl.h" |
ac973375 | 28 | #include "tree-pass.h" |
ac973375 OE |
29 | |
30 | #include <vector> | |
aaa57c69 | 31 | #include <algorithm> |
ac973375 OE |
32 | |
33 | /* | |
34 | This pass tries to eliminate unnecessary sett or clrt instructions in cases | |
35 | where the ccreg value is already known to be the same as the constant set | |
36 | would set it to. This is done as follows: | |
37 | ||
38 | Check every BB's insn and see if it's a sett or clrt. | |
39 | Once a sett or clrt insn is hit, walk insns and predecessor basic blocks | |
40 | backwards from that insn and determine all possible ccreg values from all | |
41 | basic block paths. | |
42 | Insns that set the ccreg value in some way (simple set, clobber etc) are | |
43 | recorded. Conditional branches where one edge leads to the sett / clrt insn | |
44 | are also recorded, since for each edge in the conditional branch the ccreg | |
45 | value is known constant. | |
46 | After collecting all possible ccreg values at the sett / clrt insn, check that | |
47 | all the values are the same. If that value is the same as the sett / clrt | |
48 | insn would set the ccreg to, the sett / clrt insn can be eliminated. | |
49 | */ | |
50 | ||
51 | ||
52 | // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - | |
53 | // Helper functions | |
54 | ||
55 | #define log_msg(...)\ | |
56 | do { if (dump_file != NULL) fprintf (dump_file, __VA_ARGS__); } while (0) | |
57 | ||
58 | #define log_insn(i)\ | |
59 | do { if (dump_file != NULL) print_rtl_single (dump_file, \ | |
60 | (const_rtx)i); } while (0) | |
61 | ||
62 | #define log_rtx(r)\ | |
63 | do { if (dump_file != NULL) print_rtl (dump_file, (const_rtx)r); } while (0) | |
64 | ||
65 | #define log_return(retval, ...)\ | |
66 | do { if (dump_file != NULL) fprintf (dump_file, __VA_ARGS__); \ | |
67 | return retval; } while (0) | |
68 | ||
69 | #define log_return_void(...)\ | |
70 | do { if (dump_file != NULL) fprintf (dump_file, __VA_ARGS__); \ | |
71 | return; } while (0) | |
72 | ||
73 | // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - | |
74 | // RTL pass class | |
75 | ||
76 | class sh_optimize_sett_clrt : public rtl_opt_pass | |
77 | { | |
78 | public: | |
79 | sh_optimize_sett_clrt (gcc::context* ctx, const char* name); | |
80 | virtual ~sh_optimize_sett_clrt (void); | |
579f4e64 OE |
81 | virtual bool gate (function*); |
82 | virtual unsigned int execute (function* fun); | |
ac973375 OE |
83 | |
84 | private: | |
85 | static const pass_data default_pass_data; | |
86 | ||
87 | struct ccreg_value | |
88 | { | |
89 | // The insn at which the ccreg value was determined. | |
b32d5189 | 90 | // Might be NULL if e.g. an unknown value is recorded for an |
aaa57c69 | 91 | // empty basic block. |
b32d5189 | 92 | rtx_insn *insn; |
ac973375 OE |
93 | |
94 | // The basic block where the insn was discovered. | |
ac973375 OE |
95 | basic_block bb; |
96 | ||
aaa57c69 OE |
97 | // The value of ccreg. If NULL_RTX, the exact value is not known, but |
98 | // the ccreg is changed in some way (e.g. clobbered). | |
ac973375 OE |
99 | rtx value; |
100 | }; | |
101 | ||
102 | // Update the mode of the captured m_ccreg with the specified mode. | |
103 | void update_ccreg_mode (machine_mode m); | |
104 | ||
105 | // Given an insn pattern, check if it sets the ccreg to a constant value | |
106 | // of either zero or STORE_FLAG_VALUE. If so, return the value rtx, | |
107 | // NULL_RTX otherwise. | |
108 | rtx const_setcc_value (rtx pat) const; | |
109 | ||
110 | // Given a start insn and its basic block, recursively determine all | |
111 | // possible ccreg values in all basic block paths that can lead to the | |
112 | // start insn. | |
8be6500b | 113 | bool find_last_ccreg_values (rtx_insn *start_insn, basic_block bb, |
ac973375 | 114 | std::vector<ccreg_value>& values_out, |
aaa57c69 | 115 | std::vector<basic_block>& prev_visited_bb) const; |
ac973375 OE |
116 | |
117 | // Given a cbranch insn, its basic block and another basic block, determine | |
118 | // the value to which the ccreg will be set after jumping/falling through to | |
119 | // the specified target basic block. | |
68a1a6c0 | 120 | bool sh_cbranch_ccreg_value (rtx_insn *cbranch_insn, |
ac973375 OE |
121 | basic_block cbranch_insn_bb, |
122 | basic_block branch_target_bb) const; | |
123 | ||
124 | // Check whether all of the ccreg values are the same. | |
125 | static bool all_ccreg_values_equal (const std::vector<ccreg_value>& values); | |
126 | ||
127 | // Remove REG_DEAD and REG_UNUSED notes from insns of the specified | |
128 | // ccreg_value entries. | |
129 | void remove_ccreg_dead_unused_notes (std::vector<ccreg_value>& values) const; | |
130 | ||
131 | // rtx of the ccreg that is obtained from the target. | |
132 | rtx m_ccreg; | |
133 | }; | |
134 | ||
135 | const pass_data sh_optimize_sett_clrt::default_pass_data = | |
136 | { | |
137 | RTL_PASS, // type | |
138 | "", // name (overwritten by the constructor) | |
139 | OPTGROUP_NONE, // optinfo_flags | |
ac973375 OE |
140 | TV_OPTIMIZE, // tv_id |
141 | 0, // properties_required | |
142 | 0, // properties_provided | |
143 | 0, // properties_destroyed | |
144 | 0, // todo_flags_start | |
145 | 0 // todo_flags_finish | |
146 | }; | |
147 | ||
148 | sh_optimize_sett_clrt::sh_optimize_sett_clrt (gcc::context* ctx, | |
149 | const char* name) | |
150 | : rtl_opt_pass (default_pass_data, ctx), | |
151 | m_ccreg (NULL_RTX) | |
152 | { | |
153 | // Overwrite default name in pass_data base class. | |
154 | this->name = name; | |
155 | } | |
156 | ||
157 | sh_optimize_sett_clrt::~sh_optimize_sett_clrt (void) | |
158 | { | |
159 | } | |
160 | ||
161 | bool | |
579f4e64 | 162 | sh_optimize_sett_clrt::gate (function*) |
ac973375 OE |
163 | { |
164 | return optimize > 0; | |
165 | } | |
166 | ||
167 | unsigned int | |
579f4e64 | 168 | sh_optimize_sett_clrt::execute (function* fun) |
ac973375 OE |
169 | { |
170 | unsigned int ccr0 = INVALID_REGNUM; | |
171 | unsigned int ccr1 = INVALID_REGNUM; | |
172 | ||
173 | if (targetm.fixed_condition_code_regs (&ccr0, &ccr1) | |
174 | && ccr0 != INVALID_REGNUM) | |
175 | { | |
176 | // Initially create a reg rtx with VOIDmode. | |
177 | // When the constant setcc is discovered, the mode is changed | |
178 | // to the mode that is actually used by the target. | |
179 | m_ccreg = gen_rtx_REG (VOIDmode, ccr0); | |
180 | } | |
181 | ||
182 | if (m_ccreg == NULL_RTX) | |
183 | log_return (0, "no ccreg.\n\n"); | |
184 | ||
185 | if (STORE_FLAG_VALUE != 1) | |
186 | log_return (0, "unsupported STORE_FLAG_VALUE %d", STORE_FLAG_VALUE); | |
187 | ||
188 | log_msg ("ccreg: "); | |
189 | log_rtx (m_ccreg); | |
190 | log_msg (" STORE_FLAG_VALUE = %d\n", STORE_FLAG_VALUE); | |
191 | ||
192 | if (!df_regs_ever_live_p (ccr0)) | |
193 | log_return (0, "ccreg never live\n\n"); | |
194 | ||
195 | // Output vector for find_known_ccreg_values. | |
196 | std::vector<ccreg_value> ccreg_values; | |
197 | ccreg_values.reserve (32); | |
198 | ||
aaa57c69 OE |
199 | // Something for recording visited basic blocks to avoid infinite recursion. |
200 | std::vector<basic_block> visited_bbs; | |
201 | visited_bbs.reserve (32); | |
202 | ||
ac973375 OE |
203 | // Look for insns that set the ccreg to a constant value and see if it can |
204 | // be optimized. | |
205 | basic_block bb; | |
579f4e64 | 206 | FOR_EACH_BB_REVERSE_FN (bb, fun) |
b32d5189 | 207 | for (rtx_insn *next_i, *i = NEXT_INSN (BB_HEAD (bb)); |
ac973375 OE |
208 | i != NULL_RTX && i != BB_END (bb); i = next_i) |
209 | { | |
210 | next_i = NEXT_INSN (i); | |
211 | ||
212 | if (!INSN_P (i) || !NONDEBUG_INSN_P (i)) | |
213 | continue; | |
214 | ||
215 | rtx setcc_val = const_setcc_value (PATTERN (i)); | |
216 | if (setcc_val != NULL_RTX) | |
217 | { | |
218 | update_ccreg_mode (GET_MODE (XEXP (PATTERN (i), 0))); | |
219 | ||
220 | log_msg ("\n\nfound const setcc insn in [bb %d]: \n", bb->index); | |
221 | log_insn (i); | |
222 | log_msg ("\n"); | |
223 | ||
224 | ccreg_values.clear (); | |
aaa57c69 | 225 | visited_bbs.clear (); |
8be6500b OE |
226 | bool ok = find_last_ccreg_values (PREV_INSN (i), bb, ccreg_values, |
227 | visited_bbs); | |
ac973375 OE |
228 | |
229 | log_msg ("number of ccreg values collected: %u\n", | |
230 | (unsigned int)ccreg_values.size ()); | |
231 | ||
232 | // If all the collected values are equal and are equal to the | |
233 | // constant value of the setcc insn, the setcc insn can be | |
234 | // removed. | |
8be6500b | 235 | if (ok && all_ccreg_values_equal (ccreg_values) |
ac973375 OE |
236 | && rtx_equal_p (ccreg_values.front ().value, setcc_val)) |
237 | { | |
238 | log_msg ("all values are "); | |
239 | log_rtx (setcc_val); | |
240 | log_msg ("\n"); | |
241 | ||
242 | delete_insn (i); | |
243 | remove_ccreg_dead_unused_notes (ccreg_values); | |
244 | } | |
245 | } | |
246 | } | |
247 | ||
248 | log_return (0, "\n\n"); | |
249 | } | |
250 | ||
251 | void | |
252 | sh_optimize_sett_clrt::update_ccreg_mode (machine_mode m) | |
253 | { | |
254 | if (GET_MODE (m_ccreg) == m) | |
255 | return; | |
256 | ||
257 | PUT_MODE (m_ccreg, m); | |
258 | log_msg ("updated ccreg mode: "); | |
259 | log_rtx (m_ccreg); | |
260 | log_msg ("\n\n"); | |
261 | } | |
262 | ||
263 | rtx | |
264 | sh_optimize_sett_clrt::const_setcc_value (rtx pat) const | |
265 | { | |
266 | if (GET_CODE (pat) == SET | |
267 | && REG_P (XEXP (pat, 0)) && REGNO (XEXP (pat, 0)) == REGNO (m_ccreg) | |
268 | && CONST_INT_P (XEXP (pat, 1)) | |
269 | && (INTVAL (XEXP (pat, 1)) == 0 | |
270 | || INTVAL (XEXP (pat, 1)) == STORE_FLAG_VALUE)) | |
271 | return XEXP (pat, 1); | |
272 | else | |
273 | return NULL_RTX; | |
274 | } | |
275 | ||
276 | bool | |
277 | sh_optimize_sett_clrt | |
68a1a6c0 | 278 | ::sh_cbranch_ccreg_value (rtx_insn *cbranch_insn, basic_block cbranch_insn_bb, |
ac973375 OE |
279 | basic_block branch_target_bb) const |
280 | { | |
281 | rtx pc_set_rtx = pc_set (cbranch_insn); | |
282 | gcc_assert (pc_set_rtx != NULL_RTX); | |
283 | gcc_assert (branch_target_bb != NULL); | |
284 | ||
285 | rtx cond = XEXP (XEXP (pc_set_rtx, 1), 0); | |
286 | bool branch_if; | |
287 | ||
288 | if (GET_CODE (cond) == NE | |
289 | && REG_P (XEXP (cond, 0)) && REGNO (XEXP (cond, 0)) == REGNO (m_ccreg) | |
290 | && XEXP (cond, 1) == const0_rtx) | |
291 | branch_if = true; | |
292 | ||
293 | else if (GET_CODE (cond) == EQ | |
294 | && REG_P (XEXP (cond, 0)) && REGNO (XEXP (cond, 0)) == REGNO (m_ccreg) | |
295 | && XEXP (cond, 1) == const0_rtx) | |
296 | branch_if = false; | |
297 | ||
298 | else | |
299 | gcc_unreachable (); | |
300 | ||
301 | if (branch_target_bb == BRANCH_EDGE (cbranch_insn_bb)->dest) | |
302 | return branch_if; | |
303 | else if (branch_target_bb == FALLTHRU_EDGE (cbranch_insn_bb)->dest) | |
304 | return !branch_if; | |
305 | else | |
306 | gcc_unreachable (); | |
307 | } | |
308 | ||
8be6500b | 309 | bool |
ac973375 | 310 | sh_optimize_sett_clrt |
b32d5189 | 311 | ::find_last_ccreg_values (rtx_insn *start_insn, basic_block bb, |
ac973375 | 312 | std::vector<ccreg_value>& values_out, |
aaa57c69 | 313 | std::vector<basic_block>& prev_visited_bb) const |
ac973375 | 314 | { |
aaa57c69 OE |
315 | // FIXME: For larger CFGs this will unnecessarily re-visit basic blocks. |
316 | // Once a basic block has been visited, the result should be stored in | |
317 | // some container so that it can be looked up quickly eliminating the | |
318 | // re-visits. | |
319 | log_msg ("looking for ccreg values in [bb %d] ", bb->index); | |
320 | if (!prev_visited_bb.empty ()) | |
321 | log_msg ("(prev visited [bb %d])", prev_visited_bb.back ()->index); | |
322 | log_msg ("\n"); | |
ac973375 | 323 | |
b32d5189 | 324 | for (rtx_insn *i = start_insn; i != NULL && i != PREV_INSN (BB_HEAD (bb)); |
ac973375 OE |
325 | i = PREV_INSN (i)) |
326 | { | |
327 | if (!INSN_P (i)) | |
328 | continue; | |
329 | ||
330 | if (reg_set_p (m_ccreg, i)) | |
331 | { | |
332 | const_rtx set_rtx = set_of (m_ccreg, i); | |
333 | ||
334 | ccreg_value v; | |
335 | v.insn = i; | |
336 | v.bb = bb; | |
337 | v.value = set_rtx != NULL_RTX && GET_CODE (set_rtx) == SET | |
338 | ? XEXP (set_rtx, 1) | |
339 | : NULL_RTX; | |
340 | ||
341 | log_msg ("found setcc in [bb %d] in insn:\n", bb->index); | |
342 | log_insn (i); | |
343 | log_msg ("\nccreg value: "); | |
344 | log_rtx (v.value); | |
345 | log_msg ("\n"); | |
346 | ||
347 | values_out.push_back (v); | |
8be6500b | 348 | return true; |
ac973375 OE |
349 | } |
350 | ||
aaa57c69 | 351 | if (any_condjump_p (i) && onlyjump_p (i) && !prev_visited_bb.empty ()) |
ac973375 OE |
352 | { |
353 | // For a conditional branch the ccreg value will be a known constant | |
354 | // of either 0 or STORE_FLAG_VALUE after branching/falling through | |
355 | // to one of the two successor BBs. Record the value for the BB | |
356 | // where we came from. | |
357 | log_msg ("found cbranch in [bb %d]:\n", bb->index); | |
358 | log_insn (i); | |
359 | ||
360 | ccreg_value v; | |
361 | v.insn = i; | |
362 | v.bb = bb; | |
aaa57c69 OE |
363 | v.value = GEN_INT (sh_cbranch_ccreg_value (i, bb, |
364 | prev_visited_bb.back ())); | |
ac973375 OE |
365 | |
366 | log_msg (" branches to [bb %d] with ccreg value ", | |
aaa57c69 | 367 | prev_visited_bb.back ()->index); |
ac973375 OE |
368 | log_rtx (v.value); |
369 | log_msg ("\n"); | |
370 | ||
371 | values_out.push_back (v); | |
8be6500b | 372 | return true; |
ac973375 OE |
373 | } |
374 | } | |
375 | ||
376 | // If here, we've walked up all the insns of the current basic block | |
377 | // and none of them seems to modify the ccreg. | |
378 | // In this case, check the predecessor basic blocks. | |
379 | unsigned int pred_bb_count = 0; | |
380 | ||
aaa57c69 OE |
381 | // If the current basic block is not in the stack of previously visited |
382 | // basic blocks yet, we can recursively check the predecessor basic blocks. | |
383 | // Otherwise we have a loop in the CFG and recursing again will result in | |
384 | // an infinite loop. | |
385 | if (std::find (prev_visited_bb.rbegin (), prev_visited_bb.rend (), bb) | |
386 | == prev_visited_bb.rend ()) | |
387 | { | |
388 | prev_visited_bb.push_back (bb); | |
ac973375 | 389 | |
aaa57c69 OE |
390 | for (edge_iterator ei = ei_start (bb->preds); !ei_end_p (ei); |
391 | ei_next (&ei)) | |
392 | { | |
8be6500b OE |
393 | if (ei_edge (ei)->flags & EDGE_COMPLEX) |
394 | log_return (false, "aborting due to complex edge\n"); | |
395 | ||
aaa57c69 OE |
396 | basic_block pred_bb = ei_edge (ei)->src; |
397 | pred_bb_count += 1; | |
8be6500b OE |
398 | if (!find_last_ccreg_values (BB_END (pred_bb), pred_bb, values_out, |
399 | prev_visited_bb)) | |
400 | return false; | |
aaa57c69 OE |
401 | } |
402 | ||
403 | prev_visited_bb.pop_back (); | |
404 | } | |
405 | else | |
406 | log_msg ("loop detected for [bb %d]\n", bb->index); | |
ac973375 OE |
407 | |
408 | log_msg ("[bb %d] pred_bb_count = %u\n", bb->index, pred_bb_count); | |
409 | ||
ac973375 OE |
410 | if (pred_bb_count == 0) |
411 | { | |
aaa57c69 OE |
412 | // If we haven't checked a single predecessor basic block, the current |
413 | // basic block is probably a leaf block and we don't know the ccreg value. | |
ac973375 OE |
414 | log_msg ("unknown ccreg value for [bb %d]\n", bb->index); |
415 | ||
416 | ccreg_value v; | |
417 | v.insn = BB_END (bb); | |
418 | v.bb = bb; | |
419 | v.value = NULL_RTX; | |
420 | ||
421 | values_out.push_back (v); | |
422 | } | |
8be6500b OE |
423 | |
424 | return true; | |
ac973375 OE |
425 | } |
426 | ||
427 | bool | |
428 | sh_optimize_sett_clrt | |
429 | ::all_ccreg_values_equal (const std::vector<ccreg_value>& values) | |
430 | { | |
431 | if (values.empty ()) | |
432 | return false; | |
433 | ||
434 | rtx last_value = values.front ().value; | |
435 | ||
436 | // If the ccreg is modified in the insn but the exact value is not known | |
437 | // the value rtx might be null. | |
438 | if (last_value == NULL_RTX) | |
439 | return false; | |
440 | ||
441 | for (std::vector<ccreg_value>::const_iterator i = values.begin (); | |
442 | i != values.end (); ++i) | |
443 | if (i->value == NULL_RTX || !rtx_equal_p (last_value, i->value)) | |
444 | return false; | |
445 | ||
446 | return true; | |
447 | } | |
448 | ||
449 | void | |
450 | sh_optimize_sett_clrt | |
451 | ::remove_ccreg_dead_unused_notes (std::vector<ccreg_value>& values) const | |
452 | { | |
453 | for (std::vector<ccreg_value>::iterator i = values.begin (); | |
454 | i != values.end (); ++i) | |
455 | { | |
456 | if (i->insn == NULL_RTX) | |
457 | continue; | |
458 | ||
459 | rtx n = find_regno_note (i->insn, REG_DEAD, REGNO (m_ccreg)); | |
460 | if (n != NULL_RTX) | |
461 | remove_note (i->insn, n); | |
462 | ||
463 | n = find_regno_note (i->insn, REG_UNUSED, REGNO (m_ccreg)); | |
464 | if (n != NULL_RTX) | |
465 | remove_note (i->insn, n); | |
466 | } | |
467 | } | |
468 | ||
469 | // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - | |
470 | // This allows instantiating the pass somewhere else without having to pull | |
471 | // in a header file. | |
472 | opt_pass* | |
473 | make_pass_sh_optimize_sett_clrt (gcc::context* ctx, const char* name) | |
474 | { | |
475 | return new sh_optimize_sett_clrt (ctx, name); | |
476 | } |