1/* Global, SSA-based optimizations using mathematical identities. 2 Copyright (C) 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 2, or (at your option) any 9later version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT 12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-1301, USA. */ 20 21/* Currently, the only mini-pass in this file tries to CSE reciprocal 22 operations. These are common in sequences such as this one: 23 24 modulus = sqrt(x*x + y*y + z*z); 25 x = x / modulus; 26 y = y / modulus; 27 z = z / modulus; 28 29 that can be optimized to 30 31 modulus = sqrt(x*x + y*y + z*z); 32 rmodulus = 1.0 / modulus; 33 x = x * rmodulus; 34 y = y * rmodulus; 35 z = z * rmodulus; 36 37 We do this for loop invariant divisors, and with this pass whenever 38 we notice that a division has the same divisor multiple times. 39 40 Of course, like in PRE, we don't insert a division if a dominator 41 already has one. However, this cannot be done as an extension of 42 PRE for several reasons. 43 44 First of all, with some experiments it was found out that the 45 transformation is not always useful if there are only two divisions 46 hy the same divisor. This is probably because modern processors 47 can pipeline the divisions; on older, in-order processors it should 48 still be effective to optimize two divisions by the same number. 49 We make this a param, and it shall be called N in the remainder of 50 this comment. 51 52 Second, if trapping math is active, we have less freedom on where 53 to insert divisions: we can only do so in basic blocks that already 54 contain one. (If divisions don't trap, instead, we can insert 55 divisions elsewhere, which will be in blocks that are common dominators 56 of those that have the division). 57 58 We really don't want to compute the reciprocal unless a division will 59 be found. To do this, we won't insert the division in a basic block 60 that has less than N divisions *post-dominating* it. 61 62 The algorithm constructs a subset of the dominator tree, holding the 63 blocks containing the divisions and the common dominators to them, 64 and walk it twice. The first walk is in post-order, and it annotates 65 each block with the number of divisions that post-dominate it: this 66 gives information on where divisions can be inserted profitably. 67 The second walk is in pre-order, and it inserts divisions as explained 68 above, and replaces divisions by multiplications. 69 70 In the best case, the cost of the pass is O(n_statements). In the 71 worst-case, the cost is due to creating the dominator tree subset, 72 with a cost of O(n_basic_blocks ^ 2); however this can only happen 73 for n_statements / n_basic_blocks statements. So, the amortized cost 74 of creating the dominator tree subset is O(n_basic_blocks) and the 75 worst-case cost of the pass is O(n_statements * n_basic_blocks). 76 77 More practically, the cost will be small because there are few 78 divisions, and they tend to be in the same basic block, so insert_bb 79 is called very few times. 80 81 If we did this using domwalk.c, an efficient implementation would have 82 to work on all the variables in a single pass, because we could not 83 work on just a subset of the dominator tree, as we do now, and the 84 cost would also be something like O(n_statements * n_basic_blocks). 85 The data structures would be more complex in order to work on all the 86 variables in a single pass. */ 87 88#include "config.h" 89#include "system.h" 90#include "coretypes.h" 91#include "tm.h" 92#include "flags.h" 93#include "tree.h" 94#include "tree-flow.h" 95#include "real.h" 96#include "timevar.h" 97#include "tree-pass.h" 98#include "alloc-pool.h" 99#include "basic-block.h" 100#include "target.h" 101 102 103/* This structure represents one basic block that either computes a 104 division, or is a common dominator for basic block that compute a 105 division. */ 106struct occurrence { 107 /* The basic block represented by this structure. */ 108 basic_block bb; 109 110 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal 111 inserted in BB. */ 112 tree recip_def; 113 114 /* If non-NULL, the MODIFY_EXPR for a reciprocal computation that 115 was inserted in BB. */ 116 tree recip_def_stmt; 117 118 /* Pointer to a list of "struct occurrence"s for blocks dominated 119 by BB. */ 120 struct occurrence *children; 121 122 /* Pointer to the next "struct occurrence"s in the list of blocks 123 sharing a common dominator. */ 124 struct occurrence *next; 125 126 /* The number of divisions that are in BB before compute_merit. The 127 number of divisions that are in BB or post-dominate it after 128 compute_merit. */ 129 int num_divisions; 130 131 /* True if the basic block has a division, false if it is a common 132 dominator for basic blocks that do. If it is false and trapping 133 math is active, BB is not a candidate for inserting a reciprocal. */ 134 bool bb_has_division; 135}; 136 137 138/* The instance of "struct occurrence" representing the highest 139 interesting block in the dominator tree. */ 140static struct occurrence *occ_head; 141 142/* Allocation pool for getting instances of "struct occurrence". */ 143static alloc_pool occ_pool; 144 145 146 147/* Allocate and return a new struct occurrence for basic block BB, and 148 whose children list is headed by CHILDREN. */ 149static struct occurrence * 150occ_new (basic_block bb, struct occurrence *children) 151{ 152 struct occurrence *occ; 153 154 occ = bb->aux = pool_alloc (occ_pool); 155 memset (occ, 0, sizeof (struct occurrence)); 156 157 occ->bb = bb; 158 occ->children = children; 159 return occ; 160} 161 162 163/* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a 164 list of "struct occurrence"s, one per basic block, having IDOM as 165 their common dominator. 166 167 We try to insert NEW_OCC as deep as possible in the tree, and we also 168 insert any other block that is a common dominator for BB and one 169 block already in the tree. */ 170 171static void 172insert_bb (struct occurrence *new_occ, basic_block idom, 173 struct occurrence **p_head) 174{ 175 struct occurrence *occ, **p_occ; 176 177 for (p_occ = p_head; (occ = *p_occ) != NULL; ) 178 { 179 basic_block bb = new_occ->bb, occ_bb = occ->bb; 180 basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb); 181 if (dom == bb) 182 { 183 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC 184 from its list. */ 185 *p_occ = occ->next; 186 occ->next = new_occ->children; 187 new_occ->children = occ; 188 189 /* Try the next block (it may as well be dominated by BB). */ 190 } 191 192 else if (dom == occ_bb) 193 { 194 /* OCC_BB dominates BB. Tail recurse to look deeper. */ 195 insert_bb (new_occ, dom, &occ->children); 196 return; 197 } 198 199 else if (dom != idom) 200 { 201 gcc_assert (!dom->aux); 202 203 /* There is a dominator between IDOM and BB, add it and make 204 two children out of NEW_OCC and OCC. First, remove OCC from 205 its list. */ 206 *p_occ = occ->next; 207 new_occ->next = occ; 208 occ->next = NULL; 209 210 /* None of the previous blocks has DOM as a dominator: if we tail 211 recursed, we would reexamine them uselessly. Just switch BB with 212 DOM, and go on looking for blocks dominated by DOM. */ 213 new_occ = occ_new (dom, new_occ); 214 } 215 216 else 217 { 218 /* Nothing special, go on with the next element. */ 219 p_occ = &occ->next; 220 } 221 } 222 223 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */ 224 new_occ->next = *p_head; 225 *p_head = new_occ; 226} 227 228/* Register that we found a division in BB. */ 229 230static inline void 231register_division_in (basic_block bb) 232{ 233 struct occurrence *occ; 234 235 occ = (struct occurrence *) bb->aux; 236 if (!occ) 237 { 238 occ = occ_new (bb, NULL); 239 insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head); 240 } 241 242 occ->bb_has_division = true; 243 occ->num_divisions++; 244} 245 246 247/* Compute the number of divisions that postdominate each block in OCC and 248 its children. */ 249 250static void 251compute_merit (struct occurrence *occ) 252{ 253 struct occurrence *occ_child; 254 basic_block dom = occ->bb; 255 256 for (occ_child = occ->children; occ_child; occ_child = occ_child->next) 257 { 258 basic_block bb; 259 if (occ_child->children) 260 compute_merit (occ_child); 261 262 if (flag_exceptions) 263 bb = single_noncomplex_succ (dom); 264 else 265 bb = dom; 266 267 if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb)) 268 occ->num_divisions += occ_child->num_divisions; 269 } 270} 271 272 273/* Return whether USE_STMT is a floating-point division by DEF. */ 274static inline bool 275is_division_by (tree use_stmt, tree def) 276{ 277 return TREE_CODE (use_stmt) == MODIFY_EXPR 278 && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR 279 && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def; 280} 281 282/* Return the LHS of a RDIV_EXPR that computes a reciprocal in type TYPE. */ 283static tree 284get_constant_one (tree type) 285{ 286 tree scalar, cst; 287 int i; 288 289 gcc_assert (FLOAT_TYPE_P (type)); 290 switch (TREE_CODE (type)) 291 { 292 case REAL_TYPE: 293 return build_real (type, dconst1); 294 295 case VECTOR_TYPE: 296 scalar = build_real (TREE_TYPE (type), dconst1); 297 298 /* Create 'vect_cst_ = {cst,cst,...,cst}' */ 299 cst = NULL_TREE; 300 for (i = TYPE_VECTOR_SUBPARTS (type); --i >= 0; ) 301 cst = tree_cons (NULL_TREE, scalar, cst); 302 303 return build_vector (type, cst); 304 305 default: 306 /* Complex operations have been split already. */ 307 gcc_unreachable (); 308 } 309} 310 311/* Walk the subset of the dominator tree rooted at OCC, setting the 312 RECIP_DEF field to a definition of 1.0 / DEF that can be used in 313 the given basic block. The field may be left NULL, of course, 314 if it is not possible or profitable to do the optimization. 315 316 DEF_BSI is an iterator pointing at the statement defining DEF. 317 If RECIP_DEF is set, a dominator already has a computation that can 318 be used. */ 319 320static void 321insert_reciprocals (block_stmt_iterator *def_bsi, struct occurrence *occ, 322 tree def, tree recip_def, int threshold) 323{ 324 tree type, new_stmt; 325 block_stmt_iterator bsi; 326 struct occurrence *occ_child; 327 328 if (!recip_def 329 && (occ->bb_has_division || !flag_trapping_math) 330 && occ->num_divisions >= threshold) 331 { 332 /* Make a variable with the replacement and substitute it. */ 333 type = TREE_TYPE (def); 334 recip_def = make_rename_temp (type, "reciptmp"); 335 new_stmt = build2 (MODIFY_EXPR, void_type_node, recip_def, 336 fold_build2 (RDIV_EXPR, type, get_constant_one (type), 337 def)); 338 339 340 if (occ->bb_has_division) 341 { 342 /* Case 1: insert before an existing division. */ 343 bsi = bsi_after_labels (occ->bb); 344 while (!bsi_end_p (bsi) && !is_division_by (bsi_stmt (bsi), def)) 345 bsi_next (&bsi); 346 347 bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT); 348 } 349 else if (def_bsi && occ->bb == def_bsi->bb) 350 { 351 /* Case 2: insert right after the definition. Note that this will 352 never happen if the definition statement can throw, because in 353 that case the sole successor of the statement's basic block will 354 dominate all the uses as well. */ 355 bsi_insert_after (def_bsi, new_stmt, BSI_NEW_STMT); 356 } 357 else 358 { 359 /* Case 3: insert in a basic block not containing defs/uses. */ 360 bsi = bsi_after_labels (occ->bb); 361 bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT); 362 } 363 364 occ->recip_def_stmt = new_stmt; 365 } 366 367 occ->recip_def = recip_def; 368 for (occ_child = occ->children; occ_child; occ_child = occ_child->next) 369 insert_reciprocals (def_bsi, occ_child, def, recip_def, threshold); 370} 371 372 373/* Replace the division at USE_P with a multiplication by the reciprocal, if 374 possible. */ 375 376static inline void 377replace_reciprocal (use_operand_p use_p) 378{ 379 tree use_stmt = USE_STMT (use_p); 380 basic_block bb = bb_for_stmt (use_stmt); 381 struct occurrence *occ = (struct occurrence *) bb->aux; 382 383 if (occ->recip_def && use_stmt != occ->recip_def_stmt) 384 { 385 TREE_SET_CODE (TREE_OPERAND (use_stmt, 1), MULT_EXPR); 386 SET_USE (use_p, occ->recip_def); 387 fold_stmt_inplace (use_stmt); 388 update_stmt (use_stmt); 389 } 390} 391 392 393/* Free OCC and return one more "struct occurrence" to be freed. */ 394 395static struct occurrence * 396free_bb (struct occurrence *occ) 397{ 398 struct occurrence *child, *next; 399 400 /* First get the two pointers hanging off OCC. */ 401 next = occ->next; 402 child = occ->children; 403 occ->bb->aux = NULL; 404 pool_free (occ_pool, occ); 405 406 /* Now ensure that we don't recurse unless it is necessary. */ 407 if (!child) 408 return next; 409 else 410 { 411 while (next) 412 next = free_bb (next); 413 414 return child; 415 } 416} 417 418 419/* Look for floating-point divisions among DEF's uses, and try to 420 replace them by multiplications with the reciprocal. Add 421 as many statements computing the reciprocal as needed. 422 423 DEF must be a GIMPLE register of a floating-point type. */ 424 425static void 426execute_cse_reciprocals_1 (block_stmt_iterator *def_bsi, tree def) 427{ 428 use_operand_p use_p; 429 imm_use_iterator use_iter; 430 struct occurrence *occ; 431 int count = 0, threshold; 432 433 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def)); 434 435 FOR_EACH_IMM_USE_FAST (use_p, use_iter, def) 436 { 437 tree use_stmt = USE_STMT (use_p); 438 if (is_division_by (use_stmt, def)) 439 { 440 register_division_in (bb_for_stmt (use_stmt)); 441 count++; 442 } 443 } 444 445 /* Do the expensive part only if we can hope to optimize something. */ 446 threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def))); 447 if (count >= threshold) 448 { 449 for (occ = occ_head; occ; occ = occ->next) 450 { 451 compute_merit (occ); 452 insert_reciprocals (def_bsi, occ, def, NULL, threshold); 453 } 454 455 FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def) 456 { 457 tree use_stmt = USE_STMT (use_p); 458 if (is_division_by (use_stmt, def)) 459 replace_reciprocal (use_p); 460 } 461 } 462 463 for (occ = occ_head; occ; ) 464 occ = free_bb (occ); 465 466 occ_head = NULL; 467} 468 469 470static bool 471gate_cse_reciprocals (void) 472{ 473 return optimize && !optimize_size && flag_unsafe_math_optimizations; 474} 475 476 477/* Go through all the floating-point SSA_NAMEs, and call 478 execute_cse_reciprocals_1 on each of them. */ 479static void 480execute_cse_reciprocals (void) 481{ 482 basic_block bb; 483 tree arg; 484 485 occ_pool = create_alloc_pool ("dominators for recip", 486 sizeof (struct occurrence), 487 n_basic_blocks / 3 + 1); 488 489 calculate_dominance_info (CDI_DOMINATORS); 490 calculate_dominance_info (CDI_POST_DOMINATORS); 491 492#ifdef ENABLE_CHECKING 493 FOR_EACH_BB (bb) 494 gcc_assert (!bb->aux); 495#endif 496 497 for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg)) 498 if (default_def (arg) 499 && FLOAT_TYPE_P (TREE_TYPE (arg)) 500 && is_gimple_reg (arg)) 501 execute_cse_reciprocals_1 (NULL, default_def (arg)); 502 503 FOR_EACH_BB (bb) 504 { 505 block_stmt_iterator bsi; 506 tree phi, def; 507 508 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 509 { 510 def = PHI_RESULT (phi); 511 if (FLOAT_TYPE_P (TREE_TYPE (def)) 512 && is_gimple_reg (def)) 513 execute_cse_reciprocals_1 (NULL, def); 514 } 515 516 for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 517 { 518 tree stmt = bsi_stmt (bsi); 519 if (TREE_CODE (stmt) == MODIFY_EXPR 520 && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL 521 && FLOAT_TYPE_P (TREE_TYPE (def)) 522 && TREE_CODE (def) == SSA_NAME) 523 execute_cse_reciprocals_1 (&bsi, def); 524 } 525 } 526 527 free_dominance_info (CDI_DOMINATORS); 528 free_dominance_info (CDI_POST_DOMINATORS); 529 free_alloc_pool (occ_pool); 530} 531 532struct tree_opt_pass pass_cse_reciprocals = 533{ 534 "recip", /* name */ 535 gate_cse_reciprocals, /* gate */ 536 execute_cse_reciprocals, /* execute */ 537 NULL, /* sub */ 538 NULL, /* next */ 539 0, /* static_pass_number */ 540 0, /* tv_id */ 541 PROP_ssa, /* properties_required */ 542 0, /* properties_provided */ 543 0, /* properties_destroyed */ 544 0, /* todo_flags_start */ 545 TODO_dump_func | TODO_update_ssa | TODO_verify_ssa 546 | TODO_verify_stmts, /* todo_flags_finish */ 547 0 /* letter */ 548}; 549