Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-forwprop.c @ 48:9907f3135723
update CbC on GCC from 4.4.2 to 4.4.3.
| author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sun, 07 Feb 2010 17:48:31 +0900 |
| parents | 58ad6c70ea60 |
| children | 77e2b8dfacca |
| rev | line source |
|---|---|
| 0 | 1 /* Forward propagation of expressions for single use variables. |
| 2 Copyright (C) 2004, 2005, 2007, 2008, 2009 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 "tm.h" | |
| 24 #include "ggc.h" | |
| 25 #include "tree.h" | |
| 26 #include "rtl.h" | |
| 27 #include "tm_p.h" | |
| 28 #include "basic-block.h" | |
| 29 #include "timevar.h" | |
| 30 #include "diagnostic.h" | |
| 31 #include "tree-flow.h" | |
| 32 #include "tree-pass.h" | |
| 33 #include "tree-dump.h" | |
| 34 #include "langhooks.h" | |
| 35 #include "flags.h" | |
| 36 #include "gimple.h" | |
| 37 | |
| 38 /* This pass propagates the RHS of assignment statements into use | |
| 39 sites of the LHS of the assignment. It's basically a specialized | |
| 40 form of tree combination. It is hoped all of this can disappear | |
| 41 when we have a generalized tree combiner. | |
| 42 | |
| 43 One class of common cases we handle is forward propagating a single use | |
| 44 variable into a COND_EXPR. | |
| 45 | |
| 46 bb0: | |
| 47 x = a COND b; | |
| 48 if (x) goto ... else goto ... | |
| 49 | |
| 50 Will be transformed into: | |
| 51 | |
| 52 bb0: | |
| 53 if (a COND b) goto ... else goto ... | |
| 54 | |
| 55 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). | |
| 56 | |
| 57 Or (assuming c1 and c2 are constants): | |
| 58 | |
| 59 bb0: | |
| 60 x = a + c1; | |
| 61 if (x EQ/NEQ c2) goto ... else goto ... | |
| 62 | |
| 63 Will be transformed into: | |
| 64 | |
| 65 bb0: | |
| 66 if (a EQ/NEQ (c2 - c1)) goto ... else goto ... | |
| 67 | |
| 68 Similarly for x = a - c1. | |
| 69 | |
| 70 Or | |
| 71 | |
| 72 bb0: | |
| 73 x = !a | |
| 74 if (x) goto ... else goto ... | |
| 75 | |
| 76 Will be transformed into: | |
| 77 | |
| 78 bb0: | |
| 79 if (a == 0) goto ... else goto ... | |
| 80 | |
| 81 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). | |
| 82 For these cases, we propagate A into all, possibly more than one, | |
| 83 COND_EXPRs that use X. | |
| 84 | |
| 85 Or | |
| 86 | |
| 87 bb0: | |
| 88 x = (typecast) a | |
| 89 if (x) goto ... else goto ... | |
| 90 | |
| 91 Will be transformed into: | |
| 92 | |
| 93 bb0: | |
| 94 if (a != 0) goto ... else goto ... | |
| 95 | |
| 96 (Assuming a is an integral type and x is a boolean or x is an | |
| 97 integral and a is a boolean.) | |
| 98 | |
| 99 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1). | |
| 100 For these cases, we propagate A into all, possibly more than one, | |
| 101 COND_EXPRs that use X. | |
| 102 | |
| 103 In addition to eliminating the variable and the statement which assigns | |
| 104 a value to the variable, we may be able to later thread the jump without | |
| 105 adding insane complexity in the dominator optimizer. | |
| 106 | |
| 107 Also note these transformations can cascade. We handle this by having | |
| 108 a worklist of COND_EXPR statements to examine. As we make a change to | |
| 109 a statement, we put it back on the worklist to examine on the next | |
| 110 iteration of the main loop. | |
| 111 | |
| 112 A second class of propagation opportunities arises for ADDR_EXPR | |
| 113 nodes. | |
| 114 | |
| 115 ptr = &x->y->z; | |
| 116 res = *ptr; | |
| 117 | |
| 118 Will get turned into | |
| 119 | |
| 120 res = x->y->z; | |
| 121 | |
| 122 Or | |
| 123 ptr = (type1*)&type2var; | |
| 124 res = *ptr | |
| 125 | |
| 126 Will get turned into (if type1 and type2 are the same size | |
| 127 and neither have volatile on them): | |
| 128 res = VIEW_CONVERT_EXPR<type1>(type2var) | |
| 129 | |
| 130 Or | |
| 131 | |
| 132 ptr = &x[0]; | |
| 133 ptr2 = ptr + <constant>; | |
| 134 | |
| 135 Will get turned into | |
| 136 | |
| 137 ptr2 = &x[constant/elementsize]; | |
| 138 | |
| 139 Or | |
| 140 | |
| 141 ptr = &x[0]; | |
| 142 offset = index * element_size; | |
| 143 offset_p = (pointer) offset; | |
| 144 ptr2 = ptr + offset_p | |
| 145 | |
| 146 Will get turned into: | |
| 147 | |
| 148 ptr2 = &x[index]; | |
| 149 | |
| 150 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to | |
| 151 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent | |
| 152 {NOT_EXPR,NEG_EXPR}. | |
| 153 | |
| 154 This will (of course) be extended as other needs arise. */ | |
| 155 | |
| 156 static bool forward_propagate_addr_expr (tree name, tree rhs); | |
| 157 | |
| 158 /* Set to true if we delete EH edges during the optimization. */ | |
| 159 static bool cfg_changed; | |
| 160 | |
| 161 static tree rhs_to_tree (tree type, gimple stmt); | |
| 162 | |
| 163 /* Get the next statement we can propagate NAME's value into skipping | |
| 164 trivial copies. Returns the statement that is suitable as a | |
| 165 propagation destination or NULL_TREE if there is no such one. | |
| 166 This only returns destinations in a single-use chain. FINAL_NAME_P | |
| 167 if non-NULL is written to the ssa name that represents the use. */ | |
| 168 | |
| 169 static gimple | |
| 170 get_prop_dest_stmt (tree name, tree *final_name_p) | |
| 171 { | |
| 172 use_operand_p use; | |
| 173 gimple use_stmt; | |
| 174 | |
| 175 do { | |
| 176 /* If name has multiple uses, bail out. */ | |
| 177 if (!single_imm_use (name, &use, &use_stmt)) | |
| 178 return NULL; | |
| 179 | |
| 180 /* If this is not a trivial copy, we found it. */ | |
| 181 if (!gimple_assign_copy_p (use_stmt) | |
| 182 || TREE_CODE (gimple_assign_lhs (use_stmt)) != SSA_NAME | |
| 183 || gimple_assign_rhs1 (use_stmt) != name) | |
| 184 break; | |
| 185 | |
| 186 /* Continue searching uses of the copy destination. */ | |
| 187 name = gimple_assign_lhs (use_stmt); | |
| 188 } while (1); | |
| 189 | |
| 190 if (final_name_p) | |
| 191 *final_name_p = name; | |
| 192 | |
| 193 return use_stmt; | |
| 194 } | |
| 195 | |
| 196 /* Get the statement we can propagate from into NAME skipping | |
| 197 trivial copies. Returns the statement which defines the | |
| 198 propagation source or NULL_TREE if there is no such one. | |
| 199 If SINGLE_USE_ONLY is set considers only sources which have | |
| 200 a single use chain up to NAME. If SINGLE_USE_P is non-null, | |
| 201 it is set to whether the chain to NAME is a single use chain | |
| 202 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */ | |
| 203 | |
| 204 static gimple | |
| 205 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p) | |
| 206 { | |
| 207 bool single_use = true; | |
| 208 | |
| 209 do { | |
| 210 gimple def_stmt = SSA_NAME_DEF_STMT (name); | |
| 211 | |
| 212 if (!has_single_use (name)) | |
| 213 { | |
| 214 single_use = false; | |
| 215 if (single_use_only) | |
| 216 return NULL; | |
| 217 } | |
| 218 | |
| 219 /* If name is defined by a PHI node or is the default def, bail out. */ | |
| 220 if (gimple_code (def_stmt) != GIMPLE_ASSIGN) | |
| 221 return NULL; | |
| 222 | |
| 223 /* If name is not a simple copy destination, we found it. */ | |
| 224 if (!gimple_assign_copy_p (def_stmt) | |
| 225 || TREE_CODE (gimple_assign_rhs1 (def_stmt)) != SSA_NAME) | |
| 226 { | |
| 227 tree rhs; | |
| 228 | |
| 229 if (!single_use_only && single_use_p) | |
| 230 *single_use_p = single_use; | |
| 231 | |
| 232 /* We can look through pointer conversions in the search | |
| 233 for a useful stmt for the comparison folding. */ | |
| 234 rhs = gimple_assign_rhs1 (def_stmt); | |
| 235 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)) | |
| 236 && TREE_CODE (rhs) == SSA_NAME | |
| 237 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt))) | |
| 238 && POINTER_TYPE_P (TREE_TYPE (rhs))) | |
| 239 name = rhs; | |
| 240 else | |
| 241 return def_stmt; | |
| 242 } | |
| 243 else | |
| 244 { | |
| 245 /* Continue searching the def of the copy source name. */ | |
| 246 name = gimple_assign_rhs1 (def_stmt); | |
| 247 } | |
| 248 } while (1); | |
| 249 } | |
| 250 | |
| 251 /* Checks if the destination ssa name in DEF_STMT can be used as | |
| 252 propagation source. Returns true if so, otherwise false. */ | |
| 253 | |
| 254 static bool | |
| 255 can_propagate_from (gimple def_stmt) | |
| 256 { | |
| 257 use_operand_p use_p; | |
| 258 ssa_op_iter iter; | |
| 259 | |
| 260 gcc_assert (is_gimple_assign (def_stmt)); | |
| 261 /* If the rhs has side-effects we cannot propagate from it. */ | |
| 262 if (gimple_has_volatile_ops (def_stmt)) | |
| 263 return false; | |
| 264 | |
| 265 /* If the rhs is a load we cannot propagate from it. */ | |
| 266 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference | |
| 267 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration) | |
| 268 return false; | |
| 269 | |
| 270 /* Constants can be always propagated. */ | |
| 271 if (is_gimple_min_invariant | |
| 272 (rhs_to_tree (TREE_TYPE (gimple_assign_lhs (def_stmt)), def_stmt))) | |
| 273 return true; | |
| 274 | |
| 275 /* We cannot propagate ssa names that occur in abnormal phi nodes. */ | |
| 276 FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_USE) | |
| 277 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p))) | |
| 278 return false; | |
| 279 | |
| 280 /* If the definition is a conversion of a pointer to a function type, | |
| 281 then we can not apply optimizations as some targets require | |
| 282 function pointers to be canonicalized and in this case this | |
| 283 optimization could eliminate a necessary canonicalization. */ | |
| 284 if (is_gimple_assign (def_stmt) | |
| 285 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))) | |
| 286 { | |
| 287 tree rhs = gimple_assign_rhs1 (def_stmt); | |
| 288 if (POINTER_TYPE_P (TREE_TYPE (rhs)) | |
| 289 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE) | |
| 290 return false; | |
| 291 } | |
| 292 return true; | |
| 293 } | |
| 294 | |
| 295 /* Remove a copy chain ending in NAME along the defs but not | |
| 296 further or including UP_TO_STMT. If NAME was replaced in | |
| 297 its only use then this function can be used to clean up | |
| 298 dead stmts. Returns true if UP_TO_STMT can be removed | |
| 299 as well, otherwise false. */ | |
| 300 | |
| 301 static bool | |
| 302 remove_prop_source_from_use (tree name, gimple up_to_stmt) | |
| 303 { | |
| 304 gimple_stmt_iterator gsi; | |
| 305 gimple stmt; | |
| 306 | |
| 307 do { | |
| 308 if (!has_zero_uses (name)) | |
| 309 return false; | |
| 310 | |
| 311 stmt = SSA_NAME_DEF_STMT (name); | |
| 312 if (stmt == up_to_stmt) | |
| 313 return true; | |
| 314 | |
| 315 gsi = gsi_for_stmt (stmt); | |
| 316 release_defs (stmt); | |
| 317 gsi_remove (&gsi, true); | |
| 318 | |
| 319 name = (gimple_assign_copy_p (stmt)) ? gimple_assign_rhs1 (stmt) : NULL; | |
| 320 } while (name && TREE_CODE (name) == SSA_NAME); | |
| 321 | |
| 322 return false; | |
| 323 } | |
| 324 | |
| 325 /* Return the rhs of a gimple_assign STMT in a form of a single tree, | |
| 326 converted to type TYPE. | |
| 327 | |
| 328 This should disappear, but is needed so we can combine expressions and use | |
| 329 the fold() interfaces. Long term, we need to develop folding and combine | |
| 330 routines that deal with gimple exclusively . */ | |
| 331 | |
| 332 static tree | |
| 333 rhs_to_tree (tree type, gimple stmt) | |
| 334 { | |
| 335 enum tree_code code = gimple_assign_rhs_code (stmt); | |
| 336 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS) | |
| 337 return fold_build2 (code, type, gimple_assign_rhs1 (stmt), | |
| 338 gimple_assign_rhs2 (stmt)); | |
| 339 else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS) | |
| 340 return build1 (code, type, gimple_assign_rhs1 (stmt)); | |
| 341 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) | |
| 342 return gimple_assign_rhs1 (stmt); | |
| 343 else | |
| 344 gcc_unreachable (); | |
| 345 } | |
| 346 | |
| 347 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns | |
| 348 the folded result in a form suitable for COND_EXPR_COND or | |
| 349 NULL_TREE, if there is no suitable simplified form. If | |
| 350 INVARIANT_ONLY is true only gimple_min_invariant results are | |
| 351 considered simplified. */ | |
| 352 | |
| 353 static tree | |
| 354 combine_cond_expr_cond (enum tree_code code, tree type, | |
| 355 tree op0, tree op1, bool invariant_only) | |
| 356 { | |
| 357 tree t; | |
| 358 | |
| 359 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison); | |
| 360 | |
| 361 t = fold_binary (code, type, op0, op1); | |
| 362 if (!t) | |
| 363 return NULL_TREE; | |
| 364 | |
| 365 /* Require that we got a boolean type out if we put one in. */ | |
| 366 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type)); | |
| 367 | |
| 368 /* Canonicalize the combined condition for use in a COND_EXPR. */ | |
| 369 t = canonicalize_cond_expr_cond (t); | |
| 370 | |
| 371 /* Bail out if we required an invariant but didn't get one. */ | |
| 372 if (!t || (invariant_only && !is_gimple_min_invariant (t))) | |
| 373 return NULL_TREE; | |
| 374 | |
| 375 return t; | |
| 376 } | |
| 377 | |
| 378 /* Propagate from the ssa name definition statements of COND_EXPR | |
| 379 in GIMPLE_COND statement STMT into the conditional if that simplifies it. | |
| 380 Returns zero if no statement was changed, one if there were | |
| 381 changes and two if cfg_cleanup needs to run. | |
| 382 | |
| 383 This must be kept in sync with forward_propagate_into_cond. */ | |
| 384 | |
| 385 static int | |
| 386 forward_propagate_into_gimple_cond (gimple stmt) | |
| 387 { | |
| 388 int did_something = 0; | |
| 389 | |
| 390 do { | |
| 391 tree tmp = NULL_TREE; | |
| 392 tree name, rhs0 = NULL_TREE, rhs1 = NULL_TREE; | |
| 393 gimple def_stmt; | |
| 394 bool single_use0_p = false, single_use1_p = false; | |
| 395 enum tree_code code = gimple_cond_code (stmt); | |
| 396 | |
| 397 /* We can do tree combining on SSA_NAME and comparison expressions. */ | |
| 398 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) == tcc_comparison | |
| 399 && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME) | |
| 400 { | |
| 401 /* For comparisons use the first operand, that is likely to | |
| 402 simplify comparisons against constants. */ | |
| 403 name = gimple_cond_lhs (stmt); | |
| 404 def_stmt = get_prop_source_stmt (name, false, &single_use0_p); | |
| 405 if (def_stmt && can_propagate_from (def_stmt)) | |
| 406 { | |
| 407 tree op1 = gimple_cond_rhs (stmt); | |
| 408 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt); | |
| 409 tmp = combine_cond_expr_cond (code, boolean_type_node, rhs0, | |
| 410 op1, !single_use0_p); | |
| 411 } | |
| 412 /* If that wasn't successful, try the second operand. */ | |
| 413 if (tmp == NULL_TREE | |
| 414 && TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME) | |
| 415 { | |
| 416 tree op0 = gimple_cond_lhs (stmt); | |
| 417 name = gimple_cond_rhs (stmt); | |
| 418 def_stmt = get_prop_source_stmt (name, false, &single_use1_p); | |
| 419 if (!def_stmt || !can_propagate_from (def_stmt)) | |
| 420 return did_something; | |
| 421 | |
| 422 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt); | |
| 423 tmp = combine_cond_expr_cond (code, boolean_type_node, op0, rhs1, | |
| 424 !single_use1_p); | |
| 425 } | |
| 426 /* If that wasn't successful either, try both operands. */ | |
| 427 if (tmp == NULL_TREE | |
| 428 && rhs0 != NULL_TREE | |
| 429 && rhs1 != NULL_TREE) | |
| 430 tmp = combine_cond_expr_cond (code, boolean_type_node, rhs0, | |
| 431 fold_convert (TREE_TYPE (rhs0), rhs1), | |
| 432 !(single_use0_p && single_use1_p)); | |
| 433 } | |
| 434 | |
| 435 if (tmp) | |
| 436 { | |
| 437 if (dump_file && tmp) | |
| 438 { | |
| 439 tree cond = build2 (gimple_cond_code (stmt), | |
| 440 boolean_type_node, | |
| 441 gimple_cond_lhs (stmt), | |
| 442 gimple_cond_rhs (stmt)); | |
| 443 fprintf (dump_file, " Replaced '"); | |
| 444 print_generic_expr (dump_file, cond, 0); | |
| 445 fprintf (dump_file, "' with '"); | |
| 446 print_generic_expr (dump_file, tmp, 0); | |
| 447 fprintf (dump_file, "'\n"); | |
| 448 } | |
| 449 | |
| 450 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp)); | |
| 451 update_stmt (stmt); | |
| 452 | |
| 453 /* Remove defining statements. */ | |
| 454 remove_prop_source_from_use (name, NULL); | |
| 455 | |
| 456 if (is_gimple_min_invariant (tmp)) | |
| 457 did_something = 2; | |
| 458 else if (did_something == 0) | |
| 459 did_something = 1; | |
| 460 | |
| 461 /* Continue combining. */ | |
| 462 continue; | |
| 463 } | |
| 464 | |
| 465 break; | |
| 466 } while (1); | |
| 467 | |
| 468 return did_something; | |
| 469 } | |
| 470 | |
| 471 | |
| 472 /* Propagate from the ssa name definition statements of COND_EXPR | |
| 473 in the rhs of statement STMT into the conditional if that simplifies it. | |
| 474 Returns zero if no statement was changed, one if there were | |
| 475 changes and two if cfg_cleanup needs to run. | |
| 476 | |
| 477 This must be kept in sync with forward_propagate_into_gimple_cond. */ | |
| 478 | |
| 479 static int | |
| 480 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p) | |
| 481 { | |
| 482 gimple stmt = gsi_stmt (*gsi_p); | |
| 483 int did_something = 0; | |
| 484 | |
| 485 do { | |
| 486 tree tmp = NULL_TREE; | |
| 487 tree cond = gimple_assign_rhs1 (stmt); | |
| 488 tree name, rhs0 = NULL_TREE, rhs1 = NULL_TREE; | |
| 489 gimple def_stmt; | |
| 490 bool single_use0_p = false, single_use1_p = false; | |
| 491 | |
| 492 /* We can do tree combining on SSA_NAME and comparison expressions. */ | |
| 493 if (COMPARISON_CLASS_P (cond) | |
| 494 && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME) | |
| 495 { | |
| 496 /* For comparisons use the first operand, that is likely to | |
| 497 simplify comparisons against constants. */ | |
| 498 name = TREE_OPERAND (cond, 0); | |
| 499 def_stmt = get_prop_source_stmt (name, false, &single_use0_p); | |
| 500 if (def_stmt && can_propagate_from (def_stmt)) | |
| 501 { | |
| 502 tree op1 = TREE_OPERAND (cond, 1); | |
| 503 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt); | |
| 504 tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node, | |
| 505 rhs0, op1, !single_use0_p); | |
| 506 } | |
| 507 /* If that wasn't successful, try the second operand. */ | |
| 508 if (tmp == NULL_TREE | |
| 509 && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME) | |
| 510 { | |
| 511 tree op0 = TREE_OPERAND (cond, 0); | |
| 512 name = TREE_OPERAND (cond, 1); | |
| 513 def_stmt = get_prop_source_stmt (name, false, &single_use1_p); | |
| 514 if (!def_stmt || !can_propagate_from (def_stmt)) | |
| 515 return did_something; | |
| 516 | |
| 517 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt); | |
| 518 tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node, | |
| 519 op0, rhs1, !single_use1_p); | |
| 520 } | |
| 521 /* If that wasn't successful either, try both operands. */ | |
| 522 if (tmp == NULL_TREE | |
| 523 && rhs0 != NULL_TREE | |
| 524 && rhs1 != NULL_TREE) | |
| 525 tmp = combine_cond_expr_cond (TREE_CODE (cond), boolean_type_node, | |
| 526 rhs0, fold_convert (TREE_TYPE (rhs0), | |
| 527 rhs1), | |
| 528 !(single_use0_p && single_use1_p)); | |
| 529 } | |
| 530 else if (TREE_CODE (cond) == SSA_NAME) | |
| 531 { | |
| 532 name = cond; | |
| 533 def_stmt = get_prop_source_stmt (name, true, NULL); | |
| 534 if (def_stmt || !can_propagate_from (def_stmt)) | |
| 535 return did_something; | |
| 536 | |
| 537 rhs0 = gimple_assign_rhs1 (def_stmt); | |
| 538 tmp = combine_cond_expr_cond (NE_EXPR, boolean_type_node, rhs0, | |
| 539 build_int_cst (TREE_TYPE (rhs0), 0), | |
| 540 false); | |
| 541 } | |
| 542 | |
| 543 if (tmp) | |
| 544 { | |
| 545 if (dump_file && tmp) | |
| 546 { | |
| 547 fprintf (dump_file, " Replaced '"); | |
| 548 print_generic_expr (dump_file, cond, 0); | |
| 549 fprintf (dump_file, "' with '"); | |
| 550 print_generic_expr (dump_file, tmp, 0); | |
| 551 fprintf (dump_file, "'\n"); | |
| 552 } | |
| 553 | |
| 554 gimple_assign_set_rhs_from_tree (gsi_p, unshare_expr (tmp)); | |
| 555 stmt = gsi_stmt (*gsi_p); | |
| 556 update_stmt (stmt); | |
| 557 | |
| 558 /* Remove defining statements. */ | |
| 559 remove_prop_source_from_use (name, NULL); | |
| 560 | |
| 561 if (is_gimple_min_invariant (tmp)) | |
| 562 did_something = 2; | |
| 563 else if (did_something == 0) | |
| 564 did_something = 1; | |
| 565 | |
| 566 /* Continue combining. */ | |
| 567 continue; | |
| 568 } | |
| 569 | |
| 570 break; | |
| 571 } while (1); | |
| 572 | |
| 573 return did_something; | |
| 574 } | |
| 575 | |
| 576 /* We've just substituted an ADDR_EXPR into stmt. Update all the | |
| 577 relevant data structures to match. */ | |
| 578 | |
| 579 static void | |
| 580 tidy_after_forward_propagate_addr (gimple stmt) | |
| 581 { | |
| 582 /* We may have turned a trapping insn into a non-trapping insn. */ | |
| 583 if (maybe_clean_or_replace_eh_stmt (stmt, stmt) | |
| 584 && gimple_purge_dead_eh_edges (gimple_bb (stmt))) | |
| 585 cfg_changed = true; | |
| 586 | |
| 587 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR) | |
| 588 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt)); | |
| 589 | |
| 590 mark_symbols_for_renaming (stmt); | |
| 591 } | |
| 592 | |
| 593 /* DEF_RHS contains the address of the 0th element in an array. | |
| 594 USE_STMT uses type of DEF_RHS to compute the address of an | |
| 595 arbitrary element within the array. The (variable) byte offset | |
| 596 of the element is contained in OFFSET. | |
| 597 | |
| 598 We walk back through the use-def chains of OFFSET to verify that | |
| 599 it is indeed computing the offset of an element within the array | |
| 600 and extract the index corresponding to the given byte offset. | |
| 601 | |
| 602 We then try to fold the entire address expression into a form | |
| 603 &array[index]. | |
| 604 | |
| 605 If we are successful, we replace the right hand side of USE_STMT | |
| 606 with the new address computation. */ | |
| 607 | |
| 608 static bool | |
| 609 forward_propagate_addr_into_variable_array_index (tree offset, | |
| 610 tree def_rhs, | |
| 611 gimple_stmt_iterator *use_stmt_gsi) | |
| 612 { | |
| 613 tree index; | |
| 614 gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi); | |
| 615 | |
| 616 /* Get the offset's defining statement. */ | |
| 617 offset_def = SSA_NAME_DEF_STMT (offset); | |
| 618 | |
| 619 /* Try to find an expression for a proper index. This is either a | |
| 620 multiplication expression by the element size or just the ssa name we came | |
| 621 along in case the element size is one. In that case, however, we do not | |
| 622 allow multiplications because they can be computing index to a higher | |
| 623 level dimension (PR 37861). */ | |
| 624 if (integer_onep (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs))))) | |
| 625 { | |
| 626 if (is_gimple_assign (offset_def) | |
| 627 && gimple_assign_rhs_code (offset_def) == MULT_EXPR) | |
| 628 return false; | |
| 629 | |
| 630 index = offset; | |
| 631 } | |
| 632 else | |
| 633 { | |
| 634 /* The statement which defines OFFSET before type conversion | |
| 635 must be a simple GIMPLE_ASSIGN. */ | |
| 636 if (!is_gimple_assign (offset_def)) | |
| 637 return false; | |
| 638 | |
| 639 /* The RHS of the statement which defines OFFSET must be a | |
| 640 multiplication of an object by the size of the array elements. | |
| 641 This implicitly verifies that the size of the array elements | |
| 642 is constant. */ | |
| 643 offset = gimple_assign_rhs1 (offset_def); | |
| 644 if (gimple_assign_rhs_code (offset_def) != MULT_EXPR | |
| 645 || TREE_CODE (gimple_assign_rhs2 (offset_def)) != INTEGER_CST | |
| 646 || !simple_cst_equal (gimple_assign_rhs2 (offset_def), | |
| 647 TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs))))) | |
| 648 return false; | |
| 649 | |
| 650 /* The first operand to the MULT_EXPR is the desired index. */ | |
| 651 index = offset; | |
| 652 } | |
| 653 | |
| 654 /* Replace the pointer addition with array indexing. */ | |
| 655 gimple_assign_set_rhs_from_tree (use_stmt_gsi, unshare_expr (def_rhs)); | |
| 656 use_stmt = gsi_stmt (*use_stmt_gsi); | |
| 657 TREE_OPERAND (TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0), 1) | |
| 658 = index; | |
| 659 | |
| 660 /* That should have created gimple, so there is no need to | |
| 661 record information to undo the propagation. */ | |
| 662 fold_stmt_inplace (use_stmt); | |
| 663 tidy_after_forward_propagate_addr (use_stmt); | |
| 664 return true; | |
| 665 } | |
| 666 | |
| 667 /* NAME is a SSA_NAME representing DEF_RHS which is of the form | |
| 668 ADDR_EXPR <whatever>. | |
| 669 | |
| 670 Try to forward propagate the ADDR_EXPR into the use USE_STMT. | |
| 671 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF | |
| 672 node or for recovery of array indexing from pointer arithmetic. | |
| 673 | |
| 674 Return true if the propagation was successful (the propagation can | |
| 675 be not totally successful, yet things may have been changed). */ | |
| 676 | |
| 677 static bool | |
| 678 forward_propagate_addr_expr_1 (tree name, tree def_rhs, | |
| 679 gimple_stmt_iterator *use_stmt_gsi, | |
| 680 bool single_use_p) | |
| 681 { | |
| 682 tree lhs, rhs, rhs2, array_ref; | |
| 683 tree *rhsp, *lhsp; | |
| 684 gimple use_stmt = gsi_stmt (*use_stmt_gsi); | |
| 685 enum tree_code rhs_code; | |
|
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
686 bool res = true; |
| 0 | 687 |
| 688 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR); | |
| 689 | |
| 690 lhs = gimple_assign_lhs (use_stmt); | |
| 691 rhs_code = gimple_assign_rhs_code (use_stmt); | |
| 692 rhs = gimple_assign_rhs1 (use_stmt); | |
| 693 | |
| 694 /* Trivial cases. The use statement could be a trivial copy or a | |
| 695 useless conversion. Recurse to the uses of the lhs as copyprop does | |
| 696 not copy through different variant pointers and FRE does not catch | |
| 697 all useless conversions. Treat the case of a single-use name and | |
| 698 a conversion to def_rhs type separate, though. */ | |
| 699 if (TREE_CODE (lhs) == SSA_NAME | |
| 700 && ((rhs_code == SSA_NAME && rhs == name) | |
| 701 || CONVERT_EXPR_CODE_P (rhs_code))) | |
| 702 { | |
| 703 /* Only recurse if we don't deal with a single use or we cannot | |
| 704 do the propagation to the current statement. In particular | |
| 705 we can end up with a conversion needed for a non-invariant | |
| 706 address which we cannot do in a single statement. */ | |
| 707 if (!single_use_p | |
| 708 || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)) | |
| 709 && !is_gimple_min_invariant (def_rhs))) | |
| 710 return forward_propagate_addr_expr (lhs, def_rhs); | |
| 711 | |
| 712 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs)); | |
| 713 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))) | |
| 714 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs)); | |
| 715 else | |
| 716 gimple_assign_set_rhs_code (use_stmt, NOP_EXPR); | |
| 717 return true; | |
| 718 } | |
| 719 | |
| 720 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS. | |
| 721 ADDR_EXPR will not appear on the LHS. */ | |
| 722 lhsp = gimple_assign_lhs_ptr (use_stmt); | |
| 723 while (handled_component_p (*lhsp)) | |
| 724 lhsp = &TREE_OPERAND (*lhsp, 0); | |
| 725 lhs = *lhsp; | |
| 726 | |
| 727 /* Now see if the LHS node is an INDIRECT_REF using NAME. If so, | |
| 728 propagate the ADDR_EXPR into the use of NAME and fold the result. */ | |
| 729 if (TREE_CODE (lhs) == INDIRECT_REF | |
|
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
730 && TREE_OPERAND (lhs, 0) == name) |
| 0 | 731 { |
|
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
732 if (may_propagate_address_into_dereference (def_rhs, lhs) |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
733 && (lhsp != gimple_assign_lhs_ptr (use_stmt) |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
734 || useless_type_conversion_p |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
735 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)), TREE_TYPE (rhs)))) |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
736 { |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
737 *lhsp = unshare_expr (TREE_OPERAND (def_rhs, 0)); |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
738 fold_stmt_inplace (use_stmt); |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
739 tidy_after_forward_propagate_addr (use_stmt); |
| 0 | 740 |
|
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
741 /* Continue propagating into the RHS if this was not the only use. */ |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
742 if (single_use_p) |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
743 return true; |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
744 } |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
745 else |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
746 /* We can have a struct assignment dereferencing our name twice. |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
747 Note that we didn't propagate into the lhs to not falsely |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
748 claim we did when propagating into the rhs. */ |
|
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
749 res = false; |
| 0 | 750 } |
| 751 | |
| 752 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR | |
| 753 nodes from the RHS. */ | |
| 754 rhsp = gimple_assign_rhs1_ptr (use_stmt); | |
| 755 while (handled_component_p (*rhsp) | |
| 756 || TREE_CODE (*rhsp) == ADDR_EXPR) | |
| 757 rhsp = &TREE_OPERAND (*rhsp, 0); | |
| 758 rhs = *rhsp; | |
| 759 | |
| 760 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so, | |
| 761 propagate the ADDR_EXPR into the use of NAME and fold the result. */ | |
| 762 if (TREE_CODE (rhs) == INDIRECT_REF | |
| 763 && TREE_OPERAND (rhs, 0) == name | |
| 764 && may_propagate_address_into_dereference (def_rhs, rhs)) | |
| 765 { | |
| 766 *rhsp = unshare_expr (TREE_OPERAND (def_rhs, 0)); | |
| 767 fold_stmt_inplace (use_stmt); | |
| 768 tidy_after_forward_propagate_addr (use_stmt); | |
|
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
769 return res; |
| 0 | 770 } |
| 771 | |
| 772 /* Now see if the RHS node is an INDIRECT_REF using NAME. If so, | |
| 773 propagate the ADDR_EXPR into the use of NAME and try to | |
| 774 create a VCE and fold the result. */ | |
| 775 if (TREE_CODE (rhs) == INDIRECT_REF | |
| 776 && TREE_OPERAND (rhs, 0) == name | |
| 777 && TYPE_SIZE (TREE_TYPE (rhs)) | |
| 778 && TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) | |
| 779 /* Function decls should not be used for VCE either as it could be a | |
| 780 function descriptor that we want and not the actual function code. */ | |
| 781 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) != FUNCTION_DECL | |
| 782 /* We should not convert volatile loads to non volatile loads. */ | |
| 783 && !TYPE_VOLATILE (TREE_TYPE (rhs)) | |
| 784 && !TYPE_VOLATILE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) | |
| 785 && operand_equal_p (TYPE_SIZE (TREE_TYPE (rhs)), | |
| 786 TYPE_SIZE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))), 0)) | |
| 787 { | |
| 788 tree def_rhs_base, new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0)); | |
| 789 new_rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), new_rhs); | |
| 790 if (TREE_CODE (new_rhs) != VIEW_CONVERT_EXPR) | |
| 791 { | |
| 792 /* If we have folded the VIEW_CONVERT_EXPR then the result is only | |
| 793 valid if we can replace the whole rhs of the use statement. */ | |
| 794 if (rhs != gimple_assign_rhs1 (use_stmt)) | |
| 795 return false; | |
| 796 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true, NULL, | |
| 797 true, GSI_NEW_STMT); | |
| 798 gimple_assign_set_rhs1 (use_stmt, new_rhs); | |
| 799 tidy_after_forward_propagate_addr (use_stmt); | |
|
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
800 return res; |
| 0 | 801 } |
| 802 /* If the defining rhs comes from an indirect reference, then do not | |
| 803 convert into a VIEW_CONVERT_EXPR. */ | |
| 804 def_rhs_base = TREE_OPERAND (def_rhs, 0); | |
| 805 while (handled_component_p (def_rhs_base)) | |
| 806 def_rhs_base = TREE_OPERAND (def_rhs_base, 0); | |
| 807 if (!INDIRECT_REF_P (def_rhs_base)) | |
| 808 { | |
| 809 /* We may have arbitrary VIEW_CONVERT_EXPRs in a nested component | |
| 810 reference. Place it there and fold the thing. */ | |
| 811 *rhsp = new_rhs; | |
| 812 fold_stmt_inplace (use_stmt); | |
| 813 tidy_after_forward_propagate_addr (use_stmt); | |
|
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
814 return res; |
| 0 | 815 } |
| 816 } | |
| 817 | |
| 818 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there | |
| 819 is nothing to do. */ | |
| 820 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR | |
| 821 || gimple_assign_rhs1 (use_stmt) != name) | |
| 822 return false; | |
| 823 | |
| 824 /* The remaining cases are all for turning pointer arithmetic into | |
| 825 array indexing. They only apply when we have the address of | |
| 826 element zero in an array. If that is not the case then there | |
| 827 is nothing to do. */ | |
| 828 array_ref = TREE_OPERAND (def_rhs, 0); | |
| 829 if (TREE_CODE (array_ref) != ARRAY_REF | |
| 830 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE | |
| 831 || !integer_zerop (TREE_OPERAND (array_ref, 1))) | |
| 832 return false; | |
| 833 | |
| 834 rhs2 = gimple_assign_rhs2 (use_stmt); | |
| 835 /* Try to optimize &x[0] p+ C where C is a multiple of the size | |
| 836 of the elements in X into &x[C/element size]. */ | |
| 837 if (TREE_CODE (rhs2) == INTEGER_CST) | |
| 838 { | |
| 839 tree new_rhs = maybe_fold_stmt_addition (gimple_expr_type (use_stmt), | |
| 840 array_ref, rhs2); | |
| 841 if (new_rhs) | |
| 842 { | |
| 843 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs); | |
| 844 use_stmt = gsi_stmt (*use_stmt_gsi); | |
| 845 update_stmt (use_stmt); | |
| 846 tidy_after_forward_propagate_addr (use_stmt); | |
| 847 return true; | |
| 848 } | |
| 849 } | |
| 850 | |
| 851 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by | |
| 852 converting a multiplication of an index by the size of the | |
| 853 array elements, then the result is converted into the proper | |
| 854 type for the arithmetic. */ | |
| 855 if (TREE_CODE (rhs2) == SSA_NAME | |
| 856 && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs)) | |
| 857 /* Avoid problems with IVopts creating PLUS_EXPRs with a | |
| 858 different type than their operands. */ | |
| 859 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))) | |
| 860 return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs, | |
| 861 use_stmt_gsi); | |
| 862 return false; | |
| 863 } | |
| 864 | |
| 865 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>. | |
| 866 | |
| 867 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME. | |
| 868 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF | |
| 869 node or for recovery of array indexing from pointer arithmetic. | |
| 870 Returns true, if all uses have been propagated into. */ | |
| 871 | |
| 872 static bool | |
| 873 forward_propagate_addr_expr (tree name, tree rhs) | |
| 874 { | |
| 875 int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth; | |
| 876 imm_use_iterator iter; | |
| 877 gimple use_stmt; | |
| 878 bool all = true; | |
| 879 bool single_use_p = has_single_use (name); | |
| 880 | |
| 881 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name) | |
| 882 { | |
| 883 bool result; | |
| 884 tree use_rhs; | |
| 885 | |
| 886 /* If the use is not in a simple assignment statement, then | |
| 887 there is nothing we can do. */ | |
| 888 if (gimple_code (use_stmt) != GIMPLE_ASSIGN) | |
| 889 { | |
| 890 all = false; | |
| 891 continue; | |
| 892 } | |
| 893 | |
| 894 /* If the use is in a deeper loop nest, then we do not want | |
| 895 to propagate the ADDR_EXPR into the loop as that is likely | |
| 896 adding expression evaluations into the loop. */ | |
| 897 if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth) | |
| 898 { | |
| 899 all = false; | |
| 900 continue; | |
| 901 } | |
| 902 | |
| 903 push_stmt_changes (&use_stmt); | |
| 904 | |
| 905 { | |
| 906 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); | |
| 907 result = forward_propagate_addr_expr_1 (name, rhs, &gsi, | |
| 908 single_use_p); | |
| 909 use_stmt = gsi_stmt (gsi); | |
| 910 } | |
| 911 all &= result; | |
| 912 | |
| 913 pop_stmt_changes (&use_stmt); | |
| 914 | |
| 915 /* Remove intermediate now unused copy and conversion chains. */ | |
| 916 use_rhs = gimple_assign_rhs1 (use_stmt); | |
| 917 if (result | |
| 918 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME | |
| 919 && (TREE_CODE (use_rhs) == SSA_NAME | |
| 920 || (CONVERT_EXPR_P (use_rhs) | |
| 921 && TREE_CODE (TREE_OPERAND (use_rhs, 0)) == SSA_NAME))) | |
| 922 { | |
| 923 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); | |
| 924 release_defs (use_stmt); | |
| 925 gsi_remove (&gsi, true); | |
| 926 } | |
| 927 } | |
| 928 | |
| 929 return all; | |
| 930 } | |
| 931 | |
| 932 /* Forward propagate the comparison defined in STMT like | |
| 933 cond_1 = x CMP y to uses of the form | |
| 934 a_1 = (T')cond_1 | |
| 935 a_1 = !cond_1 | |
| 936 a_1 = cond_1 != 0 | |
| 937 Returns true if stmt is now unused. */ | |
| 938 | |
| 939 static bool | |
| 940 forward_propagate_comparison (gimple stmt) | |
| 941 { | |
| 942 tree name = gimple_assign_lhs (stmt); | |
| 943 gimple use_stmt; | |
| 944 tree tmp = NULL_TREE; | |
| 945 | |
| 946 /* Don't propagate ssa names that occur in abnormal phis. */ | |
| 947 if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
| 948 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))) | |
| 949 || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME | |
| 950 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt)))) | |
| 951 return false; | |
| 952 | |
| 953 /* Do not un-cse comparisons. But propagate through copies. */ | |
| 954 use_stmt = get_prop_dest_stmt (name, &name); | |
| 955 if (!use_stmt) | |
| 956 return false; | |
| 957 | |
| 958 /* Conversion of the condition result to another integral type. */ | |
| 959 if (is_gimple_assign (use_stmt) | |
| 960 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)) | |
| 961 || TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt)) | |
| 962 == tcc_comparison | |
| 963 || gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR) | |
| 964 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (use_stmt)))) | |
| 965 { | |
| 966 tree lhs = gimple_assign_lhs (use_stmt); | |
| 967 | |
| 968 /* We can propagate the condition into a conversion. */ | |
| 969 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))) | |
| 970 { | |
| 971 /* Avoid using fold here as that may create a COND_EXPR with | |
| 972 non-boolean condition as canonical form. */ | |
| 973 tmp = build2 (gimple_assign_rhs_code (stmt), TREE_TYPE (lhs), | |
| 974 gimple_assign_rhs1 (stmt), gimple_assign_rhs2 (stmt)); | |
| 975 } | |
| 976 /* We can propagate the condition into X op CST where op | |
| 977 is EQ_EXPR or NE_EXPR and CST is either one or zero. */ | |
| 978 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (use_stmt)) | |
| 979 == tcc_comparison | |
| 980 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME | |
| 981 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST) | |
| 982 { | |
| 983 enum tree_code code = gimple_assign_rhs_code (use_stmt); | |
| 984 tree cst = gimple_assign_rhs2 (use_stmt); | |
| 985 tree cond; | |
| 986 | |
| 987 cond = build2 (gimple_assign_rhs_code (stmt), | |
| 988 TREE_TYPE (cst), | |
| 989 gimple_assign_rhs1 (stmt), | |
| 990 gimple_assign_rhs2 (stmt)); | |
| 991 | |
| 992 tmp = combine_cond_expr_cond (code, TREE_TYPE (lhs), cond, cst, false); | |
| 993 if (tmp == NULL_TREE) | |
| 994 return false; | |
| 995 } | |
| 996 /* We can propagate the condition into a statement that | |
| 997 computes the logical negation of the comparison result. */ | |
| 998 else if (gimple_assign_rhs_code (use_stmt) == TRUTH_NOT_EXPR) | |
| 999 { | |
| 1000 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt)); | |
| 1001 bool nans = HONOR_NANS (TYPE_MODE (type)); | |
| 1002 enum tree_code code; | |
| 1003 code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans); | |
| 1004 if (code == ERROR_MARK) | |
| 1005 return false; | |
| 1006 | |
| 1007 tmp = build2 (code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt), | |
| 1008 gimple_assign_rhs2 (stmt)); | |
| 1009 } | |
| 1010 else | |
| 1011 return false; | |
| 1012 | |
| 1013 { | |
| 1014 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); | |
| 1015 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp)); | |
| 1016 use_stmt = gsi_stmt (gsi); | |
| 1017 update_stmt (use_stmt); | |
| 1018 } | |
| 1019 | |
| 1020 /* Remove defining statements. */ | |
| 1021 remove_prop_source_from_use (name, stmt); | |
| 1022 | |
| 1023 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1024 { | |
| 1025 tree old_rhs = rhs_to_tree (TREE_TYPE (gimple_assign_lhs (stmt)), | |
| 1026 stmt); | |
| 1027 fprintf (dump_file, " Replaced '"); | |
| 1028 print_generic_expr (dump_file, old_rhs, dump_flags); | |
| 1029 fprintf (dump_file, "' with '"); | |
| 1030 print_generic_expr (dump_file, tmp, dump_flags); | |
| 1031 fprintf (dump_file, "'\n"); | |
| 1032 } | |
| 1033 | |
| 1034 return true; | |
| 1035 } | |
| 1036 | |
| 1037 return false; | |
| 1038 } | |
| 1039 | |
| 1040 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y. | |
| 1041 If so, we can change STMT into lhs = y which can later be copy | |
| 1042 propagated. Similarly for negation. | |
| 1043 | |
| 1044 This could trivially be formulated as a forward propagation | |
| 1045 to immediate uses. However, we already had an implementation | |
| 1046 from DOM which used backward propagation via the use-def links. | |
| 1047 | |
| 1048 It turns out that backward propagation is actually faster as | |
| 1049 there's less work to do for each NOT/NEG expression we find. | |
| 1050 Backwards propagation needs to look at the statement in a single | |
| 1051 backlink. Forward propagation needs to look at potentially more | |
| 1052 than one forward link. */ | |
| 1053 | |
| 1054 static void | |
| 1055 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p) | |
| 1056 { | |
| 1057 gimple stmt = gsi_stmt (*gsi_p); | |
| 1058 tree rhs = gimple_assign_rhs1 (stmt); | |
| 1059 gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs); | |
| 1060 | |
| 1061 /* See if the RHS_DEF_STMT has the same form as our statement. */ | |
| 1062 if (is_gimple_assign (rhs_def_stmt) | |
| 1063 && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt)) | |
| 1064 { | |
| 1065 tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt); | |
| 1066 | |
| 1067 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */ | |
| 1068 if (TREE_CODE (rhs_def_operand) == SSA_NAME | |
| 1069 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand)) | |
| 1070 { | |
| 1071 gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand); | |
| 1072 stmt = gsi_stmt (*gsi_p); | |
| 1073 update_stmt (stmt); | |
| 1074 } | |
| 1075 } | |
| 1076 } | |
| 1077 | |
| 1078 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of | |
| 1079 the condition which we may be able to optimize better. */ | |
| 1080 | |
| 1081 static void | |
| 1082 simplify_gimple_switch (gimple stmt) | |
| 1083 { | |
| 1084 tree cond = gimple_switch_index (stmt); | |
| 1085 tree def, to, ti; | |
| 1086 gimple def_stmt; | |
| 1087 | |
| 1088 /* The optimization that we really care about is removing unnecessary | |
| 1089 casts. That will let us do much better in propagating the inferred | |
| 1090 constant at the switch target. */ | |
| 1091 if (TREE_CODE (cond) == SSA_NAME) | |
| 1092 { | |
| 1093 def_stmt = SSA_NAME_DEF_STMT (cond); | |
| 1094 if (is_gimple_assign (def_stmt)) | |
| 1095 { | |
| 1096 if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR) | |
| 1097 { | |
| 1098 int need_precision; | |
| 1099 bool fail; | |
| 1100 | |
| 1101 def = gimple_assign_rhs1 (def_stmt); | |
| 1102 | |
| 1103 #ifdef ENABLE_CHECKING | |
| 1104 /* ??? Why was Jeff testing this? We are gimple... */ | |
| 1105 gcc_assert (is_gimple_val (def)); | |
| 1106 #endif | |
| 1107 | |
| 1108 to = TREE_TYPE (cond); | |
| 1109 ti = TREE_TYPE (def); | |
| 1110 | |
| 1111 /* If we have an extension that preserves value, then we | |
| 1112 can copy the source value into the switch. */ | |
| 1113 | |
| 1114 need_precision = TYPE_PRECISION (ti); | |
| 1115 fail = false; | |
| 1116 if (! INTEGRAL_TYPE_P (ti)) | |
| 1117 fail = true; | |
| 1118 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti)) | |
| 1119 fail = true; | |
| 1120 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti)) | |
| 1121 need_precision += 1; | |
| 1122 if (TYPE_PRECISION (to) < need_precision) | |
| 1123 fail = true; | |
| 1124 | |
| 1125 if (!fail) | |
| 1126 { | |
| 1127 gimple_switch_set_index (stmt, def); | |
| 1128 update_stmt (stmt); | |
| 1129 } | |
| 1130 } | |
| 1131 } | |
| 1132 } | |
| 1133 } | |
| 1134 | |
| 1135 /* Main entry point for the forward propagation optimizer. */ | |
| 1136 | |
| 1137 static unsigned int | |
| 1138 tree_ssa_forward_propagate_single_use_vars (void) | |
| 1139 { | |
| 1140 basic_block bb; | |
| 1141 unsigned int todoflags = 0; | |
| 1142 | |
| 1143 cfg_changed = false; | |
| 1144 | |
| 1145 FOR_EACH_BB (bb) | |
| 1146 { | |
| 1147 gimple_stmt_iterator gsi; | |
| 1148 | |
| 1149 /* Note we update GSI within the loop as necessary. */ | |
| 1150 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) | |
| 1151 { | |
| 1152 gimple stmt = gsi_stmt (gsi); | |
| 1153 | |
| 1154 /* If this statement sets an SSA_NAME to an address, | |
| 1155 try to propagate the address into the uses of the SSA_NAME. */ | |
| 1156 if (is_gimple_assign (stmt)) | |
| 1157 { | |
| 1158 tree lhs = gimple_assign_lhs (stmt); | |
| 1159 tree rhs = gimple_assign_rhs1 (stmt); | |
| 1160 | |
| 1161 if (TREE_CODE (lhs) != SSA_NAME) | |
| 1162 { | |
| 1163 gsi_next (&gsi); | |
| 1164 continue; | |
| 1165 } | |
| 1166 | |
| 1167 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR | |
| 1168 /* Handle pointer conversions on invariant addresses | |
| 1169 as well, as this is valid gimple. */ | |
| 1170 || (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)) | |
| 1171 && TREE_CODE (rhs) == ADDR_EXPR | |
| 1172 && POINTER_TYPE_P (TREE_TYPE (lhs)))) | |
| 1173 { | |
| 1174 STRIP_NOPS (rhs); | |
| 1175 if (!stmt_references_abnormal_ssa_name (stmt) | |
| 1176 && forward_propagate_addr_expr (lhs, rhs)) | |
| 1177 { | |
| 1178 release_defs (stmt); | |
| 1179 todoflags |= TODO_remove_unused_locals; | |
| 1180 gsi_remove (&gsi, true); | |
| 1181 } | |
| 1182 else | |
| 1183 gsi_next (&gsi); | |
| 1184 } | |
| 1185 else if ((gimple_assign_rhs_code (stmt) == BIT_NOT_EXPR | |
| 1186 || gimple_assign_rhs_code (stmt) == NEGATE_EXPR) | |
| 1187 && TREE_CODE (rhs) == SSA_NAME) | |
| 1188 { | |
| 1189 simplify_not_neg_expr (&gsi); | |
| 1190 gsi_next (&gsi); | |
| 1191 } | |
| 1192 else if (gimple_assign_rhs_code (stmt) == COND_EXPR) | |
| 1193 { | |
| 1194 /* In this case the entire COND_EXPR is in rhs1. */ | |
| 1195 int did_something; | |
| 1196 fold_defer_overflow_warnings (); | |
| 1197 did_something = forward_propagate_into_cond (&gsi); | |
| 1198 stmt = gsi_stmt (gsi); | |
| 1199 if (did_something == 2) | |
| 1200 cfg_changed = true; | |
| 1201 fold_undefer_overflow_warnings (!TREE_NO_WARNING (rhs) | |
| 1202 && did_something, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL); | |
| 1203 gsi_next (&gsi); | |
| 1204 } | |
| 1205 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) | |
| 1206 == tcc_comparison) | |
| 1207 { | |
| 1208 if (forward_propagate_comparison (stmt)) | |
| 1209 { | |
| 1210 release_defs (stmt); | |
| 1211 todoflags |= TODO_remove_unused_locals; | |
| 1212 gsi_remove (&gsi, true); | |
| 1213 } | |
| 1214 else | |
| 1215 gsi_next (&gsi); | |
| 1216 } | |
| 1217 else | |
| 1218 gsi_next (&gsi); | |
| 1219 } | |
| 1220 else if (gimple_code (stmt) == GIMPLE_SWITCH) | |
| 1221 { | |
| 1222 simplify_gimple_switch (stmt); | |
| 1223 gsi_next (&gsi); | |
| 1224 } | |
| 1225 else if (gimple_code (stmt) == GIMPLE_COND) | |
| 1226 { | |
| 1227 int did_something; | |
| 1228 fold_defer_overflow_warnings (); | |
| 1229 did_something = forward_propagate_into_gimple_cond (stmt); | |
| 1230 if (did_something == 2) | |
| 1231 cfg_changed = true; | |
| 1232 fold_undefer_overflow_warnings (did_something, stmt, | |
| 1233 WARN_STRICT_OVERFLOW_CONDITIONAL); | |
| 1234 gsi_next (&gsi); | |
| 1235 } | |
| 1236 else | |
| 1237 gsi_next (&gsi); | |
| 1238 } | |
| 1239 } | |
| 1240 | |
| 1241 if (cfg_changed) | |
| 1242 todoflags |= TODO_cleanup_cfg; | |
| 1243 return todoflags; | |
| 1244 } | |
| 1245 | |
| 1246 | |
| 1247 static bool | |
| 1248 gate_forwprop (void) | |
| 1249 { | |
| 1250 return 1; | |
| 1251 } | |
| 1252 | |
| 1253 struct gimple_opt_pass pass_forwprop = | |
| 1254 { | |
| 1255 { | |
| 1256 GIMPLE_PASS, | |
| 1257 "forwprop", /* name */ | |
| 1258 gate_forwprop, /* gate */ | |
| 1259 tree_ssa_forward_propagate_single_use_vars, /* execute */ | |
| 1260 NULL, /* sub */ | |
| 1261 NULL, /* next */ | |
| 1262 0, /* static_pass_number */ | |
| 1263 TV_TREE_FORWPROP, /* tv_id */ | |
| 1264 PROP_cfg | PROP_ssa, /* properties_required */ | |
| 1265 0, /* properties_provided */ | |
| 1266 0, /* properties_destroyed */ | |
| 1267 0, /* todo_flags_start */ | |
| 1268 TODO_dump_func | |
| 1269 | TODO_ggc_collect | |
| 1270 | TODO_update_ssa | |
| 1271 | TODO_verify_ssa /* todo_flags_finish */ | |
| 1272 } | |
| 1273 }; | |
| 1274 |