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