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