1 /* Routines for discovering and unpropagating edge equivalences. 2 Copyright (C) 2005-2018 Free Software Foundation, Inc. 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 "backend.h" 24 #include "tree.h" 25 #include "gimple.h" 26 #include "tree-pass.h" 27 #include "ssa.h" 28 #include "fold-const.h" 29 #include "cfganal.h" 30 #include "gimple-iterator.h" 31 #include "tree-cfg.h" 32 #include "domwalk.h" 33 #include "tree-hash-traits.h" 34 #include "tree-ssa-live.h" 35 #include "tree-ssa-coalesce.h" 36 37 /* The basic structure describing an equivalency created by traversing 38 an edge. Traversing the edge effectively means that we can assume 39 that we've seen an assignment LHS = RHS. */ 40 struct edge_equivalency 41 { 42 tree rhs; 43 tree lhs; 44 }; 45 46 /* This routine finds and records edge equivalences for every edge 47 in the CFG. 48 49 When complete, each edge that creates an equivalency will have an 50 EDGE_EQUIVALENCY structure hanging off the edge's AUX field. 51 The caller is responsible for freeing the AUX fields. */ 52 53 static void 54 associate_equivalences_with_edges (void) 55 { 56 basic_block bb; 57 58 /* Walk over each block. If the block ends with a control statement, 59 then it might create a useful equivalence. */ 60 FOR_EACH_BB_FN (bb, cfun) 61 { 62 gimple_stmt_iterator gsi = gsi_last_bb (bb); 63 gimple *stmt; 64 65 /* If the block does not end with a COND_EXPR or SWITCH_EXPR 66 then there is nothing to do. */ 67 if (gsi_end_p (gsi)) 68 continue; 69 70 stmt = gsi_stmt (gsi); 71 72 if (!stmt) 73 continue; 74 75 /* A COND_EXPR may create an equivalency in a variety of different 76 ways. */ 77 if (gimple_code (stmt) == GIMPLE_COND) 78 { 79 edge true_edge; 80 edge false_edge; 81 struct edge_equivalency *equivalency; 82 enum tree_code code = gimple_cond_code (stmt); 83 84 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 85 86 /* Equality tests may create one or two equivalences. */ 87 if (code == EQ_EXPR || code == NE_EXPR) 88 { 89 tree op0 = gimple_cond_lhs (stmt); 90 tree op1 = gimple_cond_rhs (stmt); 91 92 /* Special case comparing booleans against a constant as we 93 know the value of OP0 on both arms of the branch. i.e., we 94 can record an equivalence for OP0 rather than COND. */ 95 if (TREE_CODE (op0) == SSA_NAME 96 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) 97 && ssa_name_has_boolean_range (op0) 98 && is_gimple_min_invariant (op1) 99 && (integer_zerop (op1) || integer_onep (op1))) 100 { 101 tree true_val = constant_boolean_node (true, TREE_TYPE (op0)); 102 tree false_val = constant_boolean_node (false, 103 TREE_TYPE (op0)); 104 if (code == EQ_EXPR) 105 { 106 equivalency = XNEW (struct edge_equivalency); 107 equivalency->lhs = op0; 108 equivalency->rhs = (integer_zerop (op1) 109 ? false_val 110 : true_val); 111 true_edge->aux = equivalency; 112 113 equivalency = XNEW (struct edge_equivalency); 114 equivalency->lhs = op0; 115 equivalency->rhs = (integer_zerop (op1) 116 ? true_val 117 : false_val); 118 false_edge->aux = equivalency; 119 } 120 else 121 { 122 equivalency = XNEW (struct edge_equivalency); 123 equivalency->lhs = op0; 124 equivalency->rhs = (integer_zerop (op1) 125 ? true_val 126 : false_val); 127 true_edge->aux = equivalency; 128 129 equivalency = XNEW (struct edge_equivalency); 130 equivalency->lhs = op0; 131 equivalency->rhs = (integer_zerop (op1) 132 ? false_val 133 : true_val); 134 false_edge->aux = equivalency; 135 } 136 } 137 138 else if (TREE_CODE (op0) == SSA_NAME 139 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) 140 && (is_gimple_min_invariant (op1) 141 || (TREE_CODE (op1) == SSA_NAME 142 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)))) 143 { 144 /* For IEEE, -0.0 == 0.0, so we don't necessarily know 145 the sign of a variable compared against zero. If 146 we're honoring signed zeros, then we cannot record 147 this value unless we know that the value is nonzero. */ 148 if (HONOR_SIGNED_ZEROS (op0) 149 && (TREE_CODE (op1) != REAL_CST 150 || real_equal (&dconst0, &TREE_REAL_CST (op1)))) 151 continue; 152 153 equivalency = XNEW (struct edge_equivalency); 154 equivalency->lhs = op0; 155 equivalency->rhs = op1; 156 if (code == EQ_EXPR) 157 true_edge->aux = equivalency; 158 else 159 false_edge->aux = equivalency; 160 161 } 162 } 163 164 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ 165 } 166 167 /* For a SWITCH_EXPR, a case label which represents a single 168 value and which is the only case label which reaches the 169 target block creates an equivalence. */ 170 else if (gimple_code (stmt) == GIMPLE_SWITCH) 171 { 172 gswitch *switch_stmt = as_a <gswitch *> (stmt); 173 tree cond = gimple_switch_index (switch_stmt); 174 175 if (TREE_CODE (cond) == SSA_NAME 176 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond)) 177 { 178 int i, n_labels = gimple_switch_num_labels (switch_stmt); 179 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun)); 180 181 /* Walk over the case label vector. Record blocks 182 which are reached by a single case label which represents 183 a single value. */ 184 for (i = 0; i < n_labels; i++) 185 { 186 tree label = gimple_switch_label (switch_stmt, i); 187 basic_block bb = label_to_block (CASE_LABEL (label)); 188 189 if (CASE_HIGH (label) 190 || !CASE_LOW (label) 191 || info[bb->index]) 192 info[bb->index] = error_mark_node; 193 else 194 info[bb->index] = label; 195 } 196 197 /* Now walk over the blocks to determine which ones were 198 marked as being reached by a useful case label. */ 199 for (i = 0; i < n_basic_blocks_for_fn (cfun); i++) 200 { 201 tree node = info[i]; 202 203 if (node != NULL 204 && node != error_mark_node) 205 { 206 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node)); 207 struct edge_equivalency *equivalency; 208 209 /* Record an equivalency on the edge from BB to basic 210 block I. */ 211 equivalency = XNEW (struct edge_equivalency); 212 equivalency->rhs = x; 213 equivalency->lhs = cond; 214 find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux = 215 equivalency; 216 } 217 } 218 free (info); 219 } 220 } 221 222 } 223 } 224 225 226 /* Translating out of SSA sometimes requires inserting copies and 227 constant initializations on edges to eliminate PHI nodes. 228 229 In some cases those copies and constant initializations are 230 redundant because the target already has the value on the 231 RHS of the assignment. 232 233 We previously tried to catch these cases after translating 234 out of SSA form. However, that code often missed cases. Worse 235 yet, the cases it missed were also often missed by the RTL 236 optimizers. Thus the resulting code had redundant instructions. 237 238 This pass attempts to detect these situations before translating 239 out of SSA form. 240 241 The key concept that this pass is built upon is that these 242 redundant copies and constant initializations often occur 243 due to constant/copy propagating equivalences resulting from 244 COND_EXPRs and SWITCH_EXPRs. 245 246 We want to do those propagations as they can sometimes allow 247 the SSA optimizers to do a better job. However, in the cases 248 where such propagations do not result in further optimization, 249 we would like to "undo" the propagation to avoid the redundant 250 copies and constant initializations. 251 252 This pass works by first associating equivalences with edges in 253 the CFG. For example, the edge leading from a SWITCH_EXPR to 254 its associated CASE_LABEL will have an equivalency between 255 SWITCH_COND and the value in the case label. 256 257 Once we have found the edge equivalences, we proceed to walk 258 the CFG in dominator order. As we traverse edges we record 259 equivalences associated with those edges we traverse. 260 261 When we encounter a PHI node, we walk its arguments to see if we 262 have an equivalence for the PHI argument. If so, then we replace 263 the argument. 264 265 Equivalences are looked up based on their value (think of it as 266 the RHS of an assignment). A value may be an SSA_NAME or an 267 invariant. We may have several SSA_NAMEs with the same value, 268 so with each value we have a list of SSA_NAMEs that have the 269 same value. */ 270 271 /* Traits for the hash_map to record the value to SSA name equivalences 272 mapping. */ 273 struct ssa_equip_hash_traits : default_hash_traits <tree> 274 { 275 static inline hashval_t hash (value_type value) 276 { return iterative_hash_expr (value, 0); } 277 static inline bool equal (value_type existing, value_type candidate) 278 { return operand_equal_p (existing, candidate, 0); } 279 }; 280 281 typedef hash_map<tree, auto_vec<tree>, 282 simple_hashmap_traits <ssa_equip_hash_traits, 283 auto_vec <tree> > > val_ssa_equiv_t; 284 285 /* Global hash table implementing a mapping from invariant values 286 to a list of SSA_NAMEs which have the same value. We might be 287 able to reuse tree-vn for this code. */ 288 val_ssa_equiv_t *val_ssa_equiv; 289 290 static void uncprop_into_successor_phis (basic_block); 291 292 /* Remove the most recently recorded equivalency for VALUE. */ 293 294 static void 295 remove_equivalence (tree value) 296 { 297 val_ssa_equiv->get (value)->pop (); 298 } 299 300 /* Record EQUIVALENCE = VALUE into our hash table. */ 301 302 static void 303 record_equiv (tree value, tree equivalence) 304 { 305 val_ssa_equiv->get_or_insert (value).safe_push (equivalence); 306 } 307 308 class uncprop_dom_walker : public dom_walker 309 { 310 public: 311 uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {} 312 313 virtual edge before_dom_children (basic_block); 314 virtual void after_dom_children (basic_block); 315 316 private: 317 318 /* As we enter each block we record the value for any edge equivalency 319 leading to this block. If no such edge equivalency exists, then we 320 record NULL. These equivalences are live until we leave the dominator 321 subtree rooted at the block where we record the equivalency. */ 322 auto_vec<tree, 2> m_equiv_stack; 323 }; 324 325 /* We have finished processing the dominator children of BB, perform 326 any finalization actions in preparation for leaving this node in 327 the dominator tree. */ 328 329 void 330 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) 331 { 332 /* Pop the topmost value off the equiv stack. */ 333 tree value = m_equiv_stack.pop (); 334 335 /* If that value was non-null, then pop the topmost equivalency off 336 its equivalency stack. */ 337 if (value != NULL) 338 remove_equivalence (value); 339 } 340 341 /* Unpropagate values from PHI nodes in successor blocks of BB. */ 342 343 static void 344 uncprop_into_successor_phis (basic_block bb) 345 { 346 edge e; 347 edge_iterator ei; 348 349 /* For each successor edge, first temporarily record any equivalence 350 on that edge. Then unpropagate values in any PHI nodes at the 351 destination of the edge. Then remove the temporary equivalence. */ 352 FOR_EACH_EDGE (e, ei, bb->succs) 353 { 354 gimple_seq phis = phi_nodes (e->dest); 355 gimple_stmt_iterator gsi; 356 357 /* If there are no PHI nodes in this destination, then there is 358 no sense in recording any equivalences. */ 359 if (gimple_seq_empty_p (phis)) 360 continue; 361 362 /* Record any equivalency associated with E. */ 363 if (e->aux) 364 { 365 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 366 record_equiv (equiv->rhs, equiv->lhs); 367 } 368 369 /* Walk over the PHI nodes, unpropagating values. */ 370 for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi)) 371 { 372 gimple *phi = gsi_stmt (gsi); 373 tree arg = PHI_ARG_DEF (phi, e->dest_idx); 374 tree res = PHI_RESULT (phi); 375 376 /* If the argument is not an invariant and can be potentially 377 coalesced with the result, then there's no point in 378 un-propagating the argument. */ 379 if (!is_gimple_min_invariant (arg) 380 && gimple_can_coalesce_p (arg, res)) 381 continue; 382 383 /* Lookup this argument's value in the hash table. */ 384 vec<tree> *equivalences = val_ssa_equiv->get (arg); 385 if (equivalences) 386 { 387 /* Walk every equivalence with the same value. If we find 388 one that can potentially coalesce with the PHI rsult, 389 then replace the value in the argument with its equivalent 390 SSA_NAME. Use the most recent equivalence as hopefully 391 that results in shortest lifetimes. */ 392 for (int j = equivalences->length () - 1; j >= 0; j--) 393 { 394 tree equiv = (*equivalences)[j]; 395 396 if (gimple_can_coalesce_p (equiv, res)) 397 { 398 SET_PHI_ARG_DEF (phi, e->dest_idx, equiv); 399 break; 400 } 401 } 402 } 403 } 404 405 /* If we had an equivalence associated with this edge, remove it. */ 406 if (e->aux) 407 { 408 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 409 remove_equivalence (equiv->rhs); 410 } 411 } 412 } 413 414 edge 415 uncprop_dom_walker::before_dom_children (basic_block bb) 416 { 417 basic_block parent; 418 bool recorded = false; 419 420 /* If this block is dominated by a single incoming edge and that edge 421 has an equivalency, then record the equivalency and push the 422 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */ 423 parent = get_immediate_dominator (CDI_DOMINATORS, bb); 424 if (parent) 425 { 426 edge e = single_pred_edge_ignoring_loop_edges (bb, false); 427 428 if (e && e->src == parent && e->aux) 429 { 430 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 431 432 record_equiv (equiv->rhs, equiv->lhs); 433 m_equiv_stack.safe_push (equiv->rhs); 434 recorded = true; 435 } 436 } 437 438 if (!recorded) 439 m_equiv_stack.safe_push (NULL_TREE); 440 441 uncprop_into_successor_phis (bb); 442 return NULL; 443 } 444 445 namespace { 446 447 const pass_data pass_data_uncprop = 448 { 449 GIMPLE_PASS, /* type */ 450 "uncprop", /* name */ 451 OPTGROUP_NONE, /* optinfo_flags */ 452 TV_TREE_SSA_UNCPROP, /* tv_id */ 453 ( PROP_cfg | PROP_ssa ), /* properties_required */ 454 0, /* properties_provided */ 455 0, /* properties_destroyed */ 456 0, /* todo_flags_start */ 457 0, /* todo_flags_finish */ 458 }; 459 460 class pass_uncprop : public gimple_opt_pass 461 { 462 public: 463 pass_uncprop (gcc::context *ctxt) 464 : gimple_opt_pass (pass_data_uncprop, ctxt) 465 {} 466 467 /* opt_pass methods: */ 468 opt_pass * clone () { return new pass_uncprop (m_ctxt); } 469 virtual bool gate (function *) { return flag_tree_dom != 0; } 470 virtual unsigned int execute (function *); 471 472 }; // class pass_uncprop 473 474 unsigned int 475 pass_uncprop::execute (function *fun) 476 { 477 basic_block bb; 478 479 associate_equivalences_with_edges (); 480 481 /* Create our global data structures. */ 482 val_ssa_equiv = new val_ssa_equiv_t (1024); 483 484 /* We're going to do a dominator walk, so ensure that we have 485 dominance information. */ 486 calculate_dominance_info (CDI_DOMINATORS); 487 488 /* Recursively walk the dominator tree undoing unprofitable 489 constant/copy propagations. */ 490 uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr); 491 492 /* we just need to empty elements out of the hash table, and cleanup the 493 AUX field on the edges. */ 494 delete val_ssa_equiv; 495 val_ssa_equiv = NULL; 496 FOR_EACH_BB_FN (bb, fun) 497 { 498 edge e; 499 edge_iterator ei; 500 501 FOR_EACH_EDGE (e, ei, bb->succs) 502 { 503 if (e->aux) 504 { 505 free (e->aux); 506 e->aux = NULL; 507 } 508 } 509 } 510 return 0; 511 } 512 513 } // anon namespace 514 515 gimple_opt_pass * 516 make_pass_uncprop (gcc::context *ctxt) 517 { 518 return new pass_uncprop (ctxt); 519 } 520