1 /* Backward propagation of indirect loads through PHIs. 2 Copyright (C) 2007-2018 Free Software Foundation, Inc. 3 Contributed by Richard Guenther <rguenther@suse.de> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "backend.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "tree-pass.h" 28 #include "ssa.h" 29 #include "gimple-pretty-print.h" 30 #include "fold-const.h" 31 #include "tree-eh.h" 32 #include "gimplify.h" 33 #include "gimple-iterator.h" 34 #include "stor-layout.h" 35 #include "tree-ssa-loop.h" 36 37 /* This pass propagates indirect loads through the PHI node for its 38 address to make the load source possibly non-addressable and to 39 allow for PHI optimization to trigger. 40 41 For example the pass changes 42 43 # addr_1 = PHI <&a, &b> 44 tmp_1 = *addr_1; 45 46 to 47 48 # tmp_1 = PHI <a, b> 49 50 but also handles more complex scenarios like 51 52 D.2077_2 = &this_1(D)->a1; 53 ... 54 55 # b_12 = PHI <&c(2), D.2077_2(3)> 56 D.2114_13 = *b_12; 57 ... 58 59 # b_15 = PHI <b_12(4), &b(5)> 60 D.2080_5 = &this_1(D)->a0; 61 ... 62 63 # b_18 = PHI <D.2080_5(6), &c(7)> 64 ... 65 66 # b_21 = PHI <b_15(8), b_18(9)> 67 D.2076_8 = *b_21; 68 69 where the addresses loaded are defined by PHIs itself. 70 The above happens for 71 72 std::max(std::min(a0, c), std::min(std::max(a1, c), b)) 73 74 where this pass transforms it to a form later PHI optimization 75 recognizes and transforms it to the simple 76 77 D.2109_10 = this_1(D)->a1; 78 D.2110_11 = c; 79 D.2114_31 = MAX_EXPR <D.2109_10, D.2110_11>; 80 D.2115_14 = b; 81 D.2125_17 = MIN_EXPR <D.2115_14, D.2114_31>; 82 D.2119_16 = this_1(D)->a0; 83 D.2124_32 = MIN_EXPR <D.2110_11, D.2119_16>; 84 D.2076_33 = MAX_EXPR <D.2125_17, D.2124_32>; 85 86 The pass does a dominator walk processing loads using a basic-block 87 local analysis and stores the result for use by transformations on 88 dominated basic-blocks. */ 89 90 91 /* Structure to keep track of the value of a dereferenced PHI result 92 and the virtual operand used for that dereference. */ 93 94 struct phiprop_d 95 { 96 tree value; 97 tree vuse; 98 }; 99 100 /* Verify if the value recorded for NAME in PHIVN is still valid at 101 the start of basic block BB. */ 102 103 static bool 104 phivn_valid_p (struct phiprop_d *phivn, tree name, basic_block bb) 105 { 106 tree vuse = phivn[SSA_NAME_VERSION (name)].vuse; 107 gimple *use_stmt; 108 imm_use_iterator ui2; 109 bool ok = true; 110 111 /* The def stmts of the virtual uses need to be dominated by bb. */ 112 gcc_assert (vuse != NULL_TREE); 113 114 FOR_EACH_IMM_USE_STMT (use_stmt, ui2, vuse) 115 { 116 /* If BB does not dominate a VDEF, the value is invalid. */ 117 if ((gimple_vdef (use_stmt) != NULL_TREE 118 || gimple_code (use_stmt) == GIMPLE_PHI) 119 && !dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb)) 120 { 121 ok = false; 122 BREAK_FROM_IMM_USE_STMT (ui2); 123 } 124 } 125 126 return ok; 127 } 128 129 /* Insert a new phi node for the dereference of PHI at basic_block 130 BB with the virtual operands from USE_STMT. */ 131 132 static tree 133 phiprop_insert_phi (basic_block bb, gphi *phi, gimple *use_stmt, 134 struct phiprop_d *phivn, size_t n) 135 { 136 tree res; 137 gphi *new_phi = NULL; 138 edge_iterator ei; 139 edge e; 140 141 gcc_assert (is_gimple_assign (use_stmt) 142 && gimple_assign_rhs_code (use_stmt) == MEM_REF); 143 144 /* Build a new PHI node to replace the definition of 145 the indirect reference lhs. */ 146 res = gimple_assign_lhs (use_stmt); 147 if (TREE_CODE (res) == SSA_NAME) 148 new_phi = create_phi_node (res, bb); 149 150 if (dump_file && (dump_flags & TDF_DETAILS)) 151 { 152 fprintf (dump_file, "Inserting PHI for result of load "); 153 print_gimple_stmt (dump_file, use_stmt, 0); 154 } 155 156 /* Add PHI arguments for each edge inserting loads of the 157 addressable operands. */ 158 FOR_EACH_EDGE (e, ei, bb->preds) 159 { 160 tree old_arg, new_var; 161 gassign *tmp; 162 source_location locus; 163 164 old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e); 165 locus = gimple_phi_arg_location_from_edge (phi, e); 166 while (TREE_CODE (old_arg) == SSA_NAME 167 && (SSA_NAME_VERSION (old_arg) >= n 168 || phivn[SSA_NAME_VERSION (old_arg)].value == NULL_TREE)) 169 { 170 gimple *def_stmt = SSA_NAME_DEF_STMT (old_arg); 171 old_arg = gimple_assign_rhs1 (def_stmt); 172 locus = gimple_location (def_stmt); 173 } 174 175 if (TREE_CODE (old_arg) == SSA_NAME) 176 { 177 if (dump_file && (dump_flags & TDF_DETAILS)) 178 { 179 fprintf (dump_file, " for edge defining "); 180 print_generic_expr (dump_file, PHI_ARG_DEF_FROM_EDGE (phi, e)); 181 fprintf (dump_file, " reusing PHI result "); 182 print_generic_expr (dump_file, 183 phivn[SSA_NAME_VERSION (old_arg)].value); 184 fprintf (dump_file, "\n"); 185 } 186 /* Reuse a formerly created dereference. */ 187 new_var = phivn[SSA_NAME_VERSION (old_arg)].value; 188 } 189 else 190 { 191 tree rhs = gimple_assign_rhs1 (use_stmt); 192 gcc_assert (TREE_CODE (old_arg) == ADDR_EXPR); 193 if (TREE_CODE (res) == SSA_NAME) 194 new_var = make_ssa_name (TREE_TYPE (rhs)); 195 else 196 new_var = unshare_expr (res); 197 if (!is_gimple_min_invariant (old_arg)) 198 old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e); 199 else 200 old_arg = unshare_expr (old_arg); 201 tmp = gimple_build_assign (new_var, 202 fold_build2 (MEM_REF, TREE_TYPE (rhs), 203 old_arg, 204 TREE_OPERAND (rhs, 1))); 205 gimple_set_location (tmp, locus); 206 207 gsi_insert_on_edge (e, tmp); 208 update_stmt (tmp); 209 210 if (dump_file && (dump_flags & TDF_DETAILS)) 211 { 212 fprintf (dump_file, " for edge defining "); 213 print_generic_expr (dump_file, PHI_ARG_DEF_FROM_EDGE (phi, e)); 214 fprintf (dump_file, " inserting load "); 215 print_gimple_stmt (dump_file, tmp, 0); 216 } 217 } 218 219 if (new_phi) 220 add_phi_arg (new_phi, new_var, e, locus); 221 } 222 223 if (new_phi) 224 { 225 update_stmt (new_phi); 226 227 if (dump_file && (dump_flags & TDF_DETAILS)) 228 print_gimple_stmt (dump_file, new_phi, 0); 229 } 230 231 return res; 232 } 233 234 /* Verify if *idx is available at *DATA. */ 235 236 static bool 237 chk_uses (tree, tree *idx, void *data) 238 { 239 basic_block dom = (basic_block) data; 240 if (TREE_CODE (*idx) == SSA_NAME) 241 return (SSA_NAME_IS_DEFAULT_DEF (*idx) 242 || ! dominated_by_p (CDI_DOMINATORS, 243 gimple_bb (SSA_NAME_DEF_STMT (*idx)), dom)); 244 return true; 245 } 246 247 /* Propagate between the phi node arguments of PHI in BB and phi result 248 users. For now this matches 249 # p_2 = PHI <&x, &y> 250 <Lx>:; 251 p_3 = p_2; 252 z_2 = *p_3; 253 and converts it to 254 # z_2 = PHI <x, y> 255 <Lx>:; 256 Returns true if a transformation was done and edge insertions 257 need to be committed. Global data PHIVN and N is used to track 258 past transformation results. We need to be especially careful here 259 with aliasing issues as we are moving memory reads. */ 260 261 static bool 262 propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn, 263 size_t n) 264 { 265 tree ptr = PHI_RESULT (phi); 266 gimple *use_stmt; 267 tree res = NULL_TREE; 268 gimple_stmt_iterator gsi; 269 imm_use_iterator ui; 270 use_operand_p arg_p, use; 271 ssa_op_iter i; 272 bool phi_inserted; 273 bool changed; 274 tree type = NULL_TREE; 275 276 if (!POINTER_TYPE_P (TREE_TYPE (ptr)) 277 || (!is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr))) 278 && TYPE_MODE (TREE_TYPE (TREE_TYPE (ptr))) == BLKmode)) 279 return false; 280 281 /* Check if we can "cheaply" dereference all phi arguments. */ 282 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) 283 { 284 tree arg = USE_FROM_PTR (arg_p); 285 /* Walk the ssa chain until we reach a ssa name we already 286 created a value for or we reach a definition of the form 287 ssa_name_n = &var; */ 288 while (TREE_CODE (arg) == SSA_NAME 289 && !SSA_NAME_IS_DEFAULT_DEF (arg) 290 && (SSA_NAME_VERSION (arg) >= n 291 || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE)) 292 { 293 gimple *def_stmt = SSA_NAME_DEF_STMT (arg); 294 if (!gimple_assign_single_p (def_stmt)) 295 return false; 296 arg = gimple_assign_rhs1 (def_stmt); 297 } 298 if (TREE_CODE (arg) != ADDR_EXPR 299 && !(TREE_CODE (arg) == SSA_NAME 300 && SSA_NAME_VERSION (arg) < n 301 && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE 302 && (!type 303 || types_compatible_p 304 (type, TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value))) 305 && phivn_valid_p (phivn, arg, bb))) 306 return false; 307 if (!type 308 && TREE_CODE (arg) == SSA_NAME) 309 type = TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value); 310 } 311 312 /* Find a dereferencing use. First follow (single use) ssa 313 copy chains for ptr. */ 314 while (single_imm_use (ptr, &use, &use_stmt) 315 && gimple_assign_ssa_name_copy_p (use_stmt)) 316 ptr = gimple_assign_lhs (use_stmt); 317 318 /* Replace the first dereference of *ptr if there is one and if we 319 can move the loads to the place of the ptr phi node. */ 320 phi_inserted = false; 321 changed = false; 322 FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr) 323 { 324 gimple *def_stmt; 325 tree vuse; 326 327 /* Only replace loads in blocks that post-dominate the PHI node. That 328 makes sure we don't end up speculating loads. */ 329 if (!dominated_by_p (CDI_POST_DOMINATORS, 330 bb, gimple_bb (use_stmt))) 331 continue; 332 333 /* Check whether this is a load of *ptr. */ 334 if (!(is_gimple_assign (use_stmt) 335 && gimple_assign_rhs_code (use_stmt) == MEM_REF 336 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == ptr 337 && integer_zerop (TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 1)) 338 && (!type 339 || types_compatible_p 340 (TREE_TYPE (gimple_assign_lhs (use_stmt)), type)) 341 /* We cannot replace a load that may throw or is volatile. */ 342 && !stmt_can_throw_internal (use_stmt))) 343 continue; 344 345 /* Check if we can move the loads. The def stmt of the virtual use 346 needs to be in a different basic block dominating bb. When the 347 def is an edge-inserted one we know it dominates us. */ 348 vuse = gimple_vuse (use_stmt); 349 def_stmt = SSA_NAME_DEF_STMT (vuse); 350 if (!SSA_NAME_IS_DEFAULT_DEF (vuse) 351 && (gimple_bb (def_stmt) == bb 352 || (gimple_bb (def_stmt) 353 && !dominated_by_p (CDI_DOMINATORS, 354 bb, gimple_bb (def_stmt))))) 355 goto next; 356 357 /* Found a proper dereference with an aggregate copy. Just 358 insert aggregate copies on the edges instead. */ 359 if (!is_gimple_reg_type (TREE_TYPE (gimple_assign_lhs (use_stmt)))) 360 { 361 if (!gimple_vdef (use_stmt)) 362 goto next; 363 364 /* As we replicate the lhs on each incoming edge all 365 used SSA names have to be available there. */ 366 if (! for_each_index (gimple_assign_lhs_ptr (use_stmt), 367 chk_uses, 368 get_immediate_dominator (CDI_DOMINATORS, 369 gimple_bb (phi)))) 370 goto next; 371 372 gimple *vuse_stmt; 373 imm_use_iterator vui; 374 use_operand_p vuse_p; 375 /* In order to move the aggregate copies earlier, make sure 376 there are no statements that could read from memory 377 aliasing the lhs in between the start of bb and use_stmt. 378 As we require use_stmt to have a VDEF above, loads after 379 use_stmt will use a different virtual SSA_NAME. */ 380 FOR_EACH_IMM_USE_FAST (vuse_p, vui, vuse) 381 { 382 vuse_stmt = USE_STMT (vuse_p); 383 if (vuse_stmt == use_stmt) 384 continue; 385 if (!dominated_by_p (CDI_DOMINATORS, 386 gimple_bb (vuse_stmt), bb)) 387 continue; 388 if (ref_maybe_used_by_stmt_p (vuse_stmt, 389 gimple_assign_lhs (use_stmt))) 390 goto next; 391 } 392 393 phiprop_insert_phi (bb, phi, use_stmt, phivn, n); 394 395 /* Remove old stmt. The phi is taken care of by DCE. */ 396 gsi = gsi_for_stmt (use_stmt); 397 /* Unlinking the VDEF here is fine as we are sure that we process 398 stmts in execution order due to aggregate copies having VDEFs 399 and we emit loads on the edges in the very same order. 400 We get multiple copies (or intermediate register loads) handled 401 only by walking PHIs or immediate uses in a lucky order though, 402 so we could signal the caller to re-start iterating over PHIs 403 when we come here which would make it quadratic in the number 404 of PHIs. */ 405 unlink_stmt_vdef (use_stmt); 406 gsi_remove (&gsi, true); 407 408 changed = true; 409 } 410 411 /* Found a proper dereference. Insert a phi node if this 412 is the first load transformation. */ 413 else if (!phi_inserted) 414 { 415 res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n); 416 type = TREE_TYPE (res); 417 418 /* Remember the value we created for *ptr. */ 419 phivn[SSA_NAME_VERSION (ptr)].value = res; 420 phivn[SSA_NAME_VERSION (ptr)].vuse = vuse; 421 422 /* Remove old stmt. The phi is taken care of by DCE, if we 423 want to delete it here we also have to delete all intermediate 424 copies. */ 425 gsi = gsi_for_stmt (use_stmt); 426 gsi_remove (&gsi, true); 427 428 phi_inserted = true; 429 changed = true; 430 } 431 else 432 { 433 /* Further replacements are easy, just make a copy out of the 434 load. */ 435 gimple_assign_set_rhs1 (use_stmt, res); 436 update_stmt (use_stmt); 437 changed = true; 438 } 439 440 next:; 441 /* Continue searching for a proper dereference. */ 442 } 443 444 return changed; 445 } 446 447 /* Main entry for phiprop pass. */ 448 449 namespace { 450 451 const pass_data pass_data_phiprop = 452 { 453 GIMPLE_PASS, /* type */ 454 "phiprop", /* name */ 455 OPTGROUP_NONE, /* optinfo_flags */ 456 TV_TREE_PHIPROP, /* tv_id */ 457 ( PROP_cfg | PROP_ssa ), /* properties_required */ 458 0, /* properties_provided */ 459 0, /* properties_destroyed */ 460 0, /* todo_flags_start */ 461 TODO_update_ssa, /* todo_flags_finish */ 462 }; 463 464 class pass_phiprop : public gimple_opt_pass 465 { 466 public: 467 pass_phiprop (gcc::context *ctxt) 468 : gimple_opt_pass (pass_data_phiprop, ctxt) 469 {} 470 471 /* opt_pass methods: */ 472 virtual bool gate (function *) { return flag_tree_phiprop; } 473 virtual unsigned int execute (function *); 474 475 }; // class pass_phiprop 476 477 unsigned int 478 pass_phiprop::execute (function *fun) 479 { 480 vec<basic_block> bbs; 481 struct phiprop_d *phivn; 482 bool did_something = false; 483 basic_block bb; 484 gphi_iterator gsi; 485 unsigned i; 486 size_t n; 487 488 calculate_dominance_info (CDI_DOMINATORS); 489 calculate_dominance_info (CDI_POST_DOMINATORS); 490 491 n = num_ssa_names; 492 phivn = XCNEWVEC (struct phiprop_d, n); 493 494 /* Walk the dominator tree in preorder. */ 495 bbs = get_all_dominated_blocks (CDI_DOMINATORS, 496 single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun))); 497 FOR_EACH_VEC_ELT (bbs, i, bb) 498 { 499 /* Since we're going to move dereferences across predecessor 500 edges avoid blocks with abnormal predecessors. */ 501 if (bb_has_abnormal_pred (bb)) 502 continue; 503 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 504 did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n); 505 } 506 507 if (did_something) 508 gsi_commit_edge_inserts (); 509 510 bbs.release (); 511 free (phivn); 512 513 free_dominance_info (CDI_POST_DOMINATORS); 514 515 return 0; 516 } 517 518 } // anon namespace 519 520 gimple_opt_pass * 521 make_pass_phiprop (gcc::context *ctxt) 522 { 523 return new pass_phiprop (ctxt); 524 } 525