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 272 /* Main structure for recording equivalences into our hash table. */ 273 struct equiv_hash_elt 274 { 275 /* The value/key of this entry. */ 276 tree value; 277 278 /* List of SSA_NAMEs which have the same value/key. */ 279 vec<tree> equivalences; 280 }; 281 282 /* Global hash table implementing a mapping from invariant values 283 to a list of SSA_NAMEs which have the same value. We might be 284 able to reuse tree-vn for this code. */ 285 static hash_map<tree, auto_vec<tree> > *val_ssa_equiv; 286 287 static void uncprop_into_successor_phis (basic_block); 288 289 /* Remove the most recently recorded equivalency for VALUE. */ 290 291 static void 292 remove_equivalence (tree value) 293 { 294 val_ssa_equiv->get (value)->pop (); 295 } 296 297 /* Record EQUIVALENCE = VALUE into our hash table. */ 298 299 static void 300 record_equiv (tree value, tree equivalence) 301 { 302 val_ssa_equiv->get_or_insert (value).safe_push (equivalence); 303 } 304 305 class uncprop_dom_walker : public dom_walker 306 { 307 public: 308 uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {} 309 310 virtual edge before_dom_children (basic_block); 311 virtual void after_dom_children (basic_block); 312 313 private: 314 315 /* As we enter each block we record the value for any edge equivalency 316 leading to this block. If no such edge equivalency exists, then we 317 record NULL. These equivalences are live until we leave the dominator 318 subtree rooted at the block where we record the equivalency. */ 319 auto_vec<tree, 2> m_equiv_stack; 320 }; 321 322 /* We have finished processing the dominator children of BB, perform 323 any finalization actions in preparation for leaving this node in 324 the dominator tree. */ 325 326 void 327 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) 328 { 329 /* Pop the topmost value off the equiv stack. */ 330 tree value = m_equiv_stack.pop (); 331 332 /* If that value was non-null, then pop the topmost equivalency off 333 its equivalency stack. */ 334 if (value != NULL) 335 remove_equivalence (value); 336 } 337 338 /* Unpropagate values from PHI nodes in successor blocks of BB. */ 339 340 static void 341 uncprop_into_successor_phis (basic_block bb) 342 { 343 edge e; 344 edge_iterator ei; 345 346 /* For each successor edge, first temporarily record any equivalence 347 on that edge. Then unpropagate values in any PHI nodes at the 348 destination of the edge. Then remove the temporary equivalence. */ 349 FOR_EACH_EDGE (e, ei, bb->succs) 350 { 351 gimple_seq phis = phi_nodes (e->dest); 352 gimple_stmt_iterator gsi; 353 354 /* If there are no PHI nodes in this destination, then there is 355 no sense in recording any equivalences. */ 356 if (gimple_seq_empty_p (phis)) 357 continue; 358 359 /* Record any equivalency associated with E. */ 360 if (e->aux) 361 { 362 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 363 record_equiv (equiv->rhs, equiv->lhs); 364 } 365 366 /* Walk over the PHI nodes, unpropagating values. */ 367 for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi)) 368 { 369 gimple *phi = gsi_stmt (gsi); 370 tree arg = PHI_ARG_DEF (phi, e->dest_idx); 371 tree res = PHI_RESULT (phi); 372 373 /* If the argument is not an invariant and can be potentially 374 coalesced with the result, then there's no point in 375 un-propagating the argument. */ 376 if (!is_gimple_min_invariant (arg) 377 && gimple_can_coalesce_p (arg, res)) 378 continue; 379 380 /* Lookup this argument's value in the hash table. */ 381 vec<tree> *equivalences = val_ssa_equiv->get (arg); 382 if (equivalences) 383 { 384 /* Walk every equivalence with the same value. If we find 385 one that can potentially coalesce with the PHI rsult, 386 then replace the value in the argument with its equivalent 387 SSA_NAME. Use the most recent equivalence as hopefully 388 that results in shortest lifetimes. */ 389 for (int j = equivalences->length () - 1; j >= 0; j--) 390 { 391 tree equiv = (*equivalences)[j]; 392 393 if (gimple_can_coalesce_p (equiv, res)) 394 { 395 SET_PHI_ARG_DEF (phi, e->dest_idx, equiv); 396 break; 397 } 398 } 399 } 400 } 401 402 /* If we had an equivalence associated with this edge, remove it. */ 403 if (e->aux) 404 { 405 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 406 remove_equivalence (equiv->rhs); 407 } 408 } 409 } 410 411 edge 412 uncprop_dom_walker::before_dom_children (basic_block bb) 413 { 414 basic_block parent; 415 bool recorded = false; 416 417 /* If this block is dominated by a single incoming edge and that edge 418 has an equivalency, then record the equivalency and push the 419 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */ 420 parent = get_immediate_dominator (CDI_DOMINATORS, bb); 421 if (parent) 422 { 423 edge e = single_pred_edge_ignoring_loop_edges (bb, false); 424 425 if (e && e->src == parent && e->aux) 426 { 427 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; 428 429 record_equiv (equiv->rhs, equiv->lhs); 430 m_equiv_stack.safe_push (equiv->rhs); 431 recorded = true; 432 } 433 } 434 435 if (!recorded) 436 m_equiv_stack.safe_push (NULL_TREE); 437 438 uncprop_into_successor_phis (bb); 439 return NULL; 440 } 441 442 namespace { 443 444 const pass_data pass_data_uncprop = 445 { 446 GIMPLE_PASS, /* type */ 447 "uncprop", /* name */ 448 OPTGROUP_NONE, /* optinfo_flags */ 449 TV_TREE_SSA_UNCPROP, /* tv_id */ 450 ( PROP_cfg | PROP_ssa ), /* properties_required */ 451 0, /* properties_provided */ 452 0, /* properties_destroyed */ 453 0, /* todo_flags_start */ 454 0, /* todo_flags_finish */ 455 }; 456 457 class pass_uncprop : public gimple_opt_pass 458 { 459 public: 460 pass_uncprop (gcc::context *ctxt) 461 : gimple_opt_pass (pass_data_uncprop, ctxt) 462 {} 463 464 /* opt_pass methods: */ 465 opt_pass * clone () { return new pass_uncprop (m_ctxt); } 466 virtual bool gate (function *) { return flag_tree_dom != 0; } 467 virtual unsigned int execute (function *); 468 469 }; // class pass_uncprop 470 471 unsigned int 472 pass_uncprop::execute (function *fun) 473 { 474 basic_block bb; 475 476 associate_equivalences_with_edges (); 477 478 /* Create our global data structures. */ 479 val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (1024); 480 481 /* We're going to do a dominator walk, so ensure that we have 482 dominance information. */ 483 calculate_dominance_info (CDI_DOMINATORS); 484 485 /* Recursively walk the dominator tree undoing unprofitable 486 constant/copy propagations. */ 487 uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr); 488 489 /* we just need to empty elements out of the hash table, and cleanup the 490 AUX field on the edges. */ 491 delete val_ssa_equiv; 492 val_ssa_equiv = NULL; 493 FOR_EACH_BB_FN (bb, fun) 494 { 495 edge e; 496 edge_iterator ei; 497 498 FOR_EACH_EDGE (e, ei, bb->succs) 499 { 500 if (e->aux) 501 { 502 free (e->aux); 503 e->aux = NULL; 504 } 505 } 506 } 507 return 0; 508 } 509 510 } // anon namespace 511 512 gimple_opt_pass * 513 make_pass_uncprop (gcc::context *ctxt) 514 { 515 return new pass_uncprop (ctxt); 516 } 517