Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-dom.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:39:51 +0900 |
| parents | 3bfb6c00c1e0 |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* SSA Dominator optimizations for trees |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 |
| 0 | 3 Free Software Foundation, Inc. |
| 4 Contributed by Diego Novillo <dnovillo@redhat.com> | |
| 5 | |
| 6 This file is part of GCC. | |
| 7 | |
| 8 GCC is free software; you can redistribute it and/or modify | |
| 9 it under the terms of the GNU General Public License as published by | |
| 10 the Free Software Foundation; either version 3, or (at your option) | |
| 11 any later version. | |
| 12 | |
| 13 GCC is distributed in the hope that it will be useful, | |
| 14 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 16 GNU General Public License for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
| 19 along with GCC; see the file COPYING3. If not see | |
| 20 <http://www.gnu.org/licenses/>. */ | |
| 21 | |
| 22 #include "config.h" | |
| 23 #include "system.h" | |
| 24 #include "coretypes.h" | |
| 25 #include "tm.h" | |
| 26 #include "tree.h" | |
| 27 #include "flags.h" | |
| 28 #include "rtl.h" | |
| 29 #include "tm_p.h" | |
| 30 #include "ggc.h" | |
| 31 #include "basic-block.h" | |
| 32 #include "cfgloop.h" | |
| 33 #include "output.h" | |
| 34 #include "expr.h" | |
| 35 #include "function.h" | |
| 36 #include "diagnostic.h" | |
| 37 #include "timevar.h" | |
| 38 #include "tree-dump.h" | |
| 39 #include "tree-flow.h" | |
| 40 #include "domwalk.h" | |
| 41 #include "real.h" | |
| 42 #include "tree-pass.h" | |
| 43 #include "tree-ssa-propagate.h" | |
| 44 #include "langhooks.h" | |
| 45 #include "params.h" | |
| 46 | |
| 47 /* This file implements optimizations on the dominator tree. */ | |
| 48 | |
| 49 /* Representation of a "naked" right-hand-side expression, to be used | |
| 50 in recording available expressions in the expression hash table. */ | |
| 51 | |
| 52 enum expr_kind | |
| 53 { | |
| 54 EXPR_SINGLE, | |
| 55 EXPR_UNARY, | |
| 56 EXPR_BINARY, | |
| 57 EXPR_CALL | |
| 58 }; | |
| 59 | |
| 60 struct hashable_expr | |
| 61 { | |
| 62 tree type; | |
| 63 enum expr_kind kind; | |
| 64 union { | |
| 65 struct { tree rhs; } single; | |
| 66 struct { enum tree_code op; tree opnd; } unary; | |
| 67 struct { enum tree_code op; tree opnd0; tree opnd1; } binary; | |
| 68 struct { tree fn; bool pure; size_t nargs; tree *args; } call; | |
| 69 } ops; | |
| 70 }; | |
| 71 | |
| 72 /* Structure for recording known values of a conditional expression | |
| 73 at the exits from its block. */ | |
| 74 | |
| 75 struct cond_equivalence | |
| 76 { | |
| 77 struct hashable_expr cond; | |
| 78 tree value; | |
| 79 }; | |
| 80 | |
| 81 /* Structure for recording edge equivalences as well as any pending | |
| 82 edge redirections during the dominator optimizer. | |
| 83 | |
| 84 Computing and storing the edge equivalences instead of creating | |
| 85 them on-demand can save significant amounts of time, particularly | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
86 for pathological cases involving switch statements. |
| 0 | 87 |
| 88 These structures live for a single iteration of the dominator | |
| 89 optimizer in the edge's AUX field. At the end of an iteration we | |
| 90 free each of these structures and update the AUX field to point | |
| 91 to any requested redirection target (the code for updating the | |
| 92 CFG and SSA graph for edge redirection expects redirection edge | |
| 93 targets to be in the AUX field for each edge. */ | |
| 94 | |
| 95 struct edge_info | |
| 96 { | |
| 97 /* If this edge creates a simple equivalence, the LHS and RHS of | |
| 98 the equivalence will be stored here. */ | |
| 99 tree lhs; | |
| 100 tree rhs; | |
| 101 | |
| 102 /* Traversing an edge may also indicate one or more particular conditions | |
| 103 are true or false. The number of recorded conditions can vary, but | |
| 104 can be determined by the condition's code. So we have an array | |
| 105 and its maximum index rather than use a varray. */ | |
| 106 struct cond_equivalence *cond_equivalences; | |
| 107 unsigned int max_cond_equivalences; | |
| 108 }; | |
| 109 | |
| 110 /* Hash table with expressions made available during the renaming process. | |
| 111 When an assignment of the form X_i = EXPR is found, the statement is | |
| 112 stored in this table. If the same expression EXPR is later found on the | |
| 113 RHS of another statement, it is replaced with X_i (thus performing | |
| 114 global redundancy elimination). Similarly as we pass through conditionals | |
| 115 we record the conditional itself as having either a true or false value | |
| 116 in this table. */ | |
| 117 static htab_t avail_exprs; | |
| 118 | |
| 119 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any | |
| 120 expressions it enters into the hash table along with a marker entry | |
| 121 (null). When we finish processing the block, we pop off entries and | |
| 122 remove the expressions from the global hash table until we hit the | |
| 123 marker. */ | |
| 124 typedef struct expr_hash_elt * expr_hash_elt_t; | |
| 125 DEF_VEC_P(expr_hash_elt_t); | |
| 126 DEF_VEC_ALLOC_P(expr_hash_elt_t,heap); | |
| 127 | |
| 128 static VEC(expr_hash_elt_t,heap) *avail_exprs_stack; | |
| 129 | |
| 130 /* Structure for entries in the expression hash table. */ | |
| 131 | |
| 132 struct expr_hash_elt | |
| 133 { | |
| 134 /* The value (lhs) of this expression. */ | |
| 135 tree lhs; | |
| 136 | |
| 137 /* The expression (rhs) we want to record. */ | |
| 138 struct hashable_expr expr; | |
| 139 | |
| 140 /* The stmt pointer if this element corresponds to a statement. */ | |
| 141 gimple stmt; | |
| 142 | |
| 143 /* The hash value for RHS. */ | |
| 144 hashval_t hash; | |
| 145 | |
| 146 /* A unique stamp, typically the address of the hash | |
| 147 element itself, used in removing entries from the table. */ | |
| 148 struct expr_hash_elt *stamp; | |
| 149 }; | |
| 150 | |
| 151 /* Stack of dest,src pairs that need to be restored during finalization. | |
| 152 | |
| 153 A NULL entry is used to mark the end of pairs which need to be | |
| 154 restored during finalization of this block. */ | |
| 155 static VEC(tree,heap) *const_and_copies_stack; | |
| 156 | |
| 157 /* Track whether or not we have changed the control flow graph. */ | |
| 158 static bool cfg_altered; | |
| 159 | |
| 160 /* Bitmap of blocks that have had EH statements cleaned. We should | |
| 161 remove their dead edges eventually. */ | |
| 162 static bitmap need_eh_cleanup; | |
| 163 | |
| 164 /* Statistics for dominator optimizations. */ | |
| 165 struct opt_stats_d | |
| 166 { | |
| 167 long num_stmts; | |
| 168 long num_exprs_considered; | |
| 169 long num_re; | |
| 170 long num_const_prop; | |
| 171 long num_copy_prop; | |
| 172 }; | |
| 173 | |
| 174 static struct opt_stats_d opt_stats; | |
| 175 | |
| 176 /* Local functions. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
177 static void optimize_stmt (basic_block, gimple_stmt_iterator); |
| 0 | 178 static tree lookup_avail_expr (gimple, bool); |
| 179 static hashval_t avail_expr_hash (const void *); | |
| 180 static hashval_t real_avail_expr_hash (const void *); | |
| 181 static int avail_expr_eq (const void *, const void *); | |
| 182 static void htab_statistics (FILE *, htab_t); | |
| 183 static void record_cond (struct cond_equivalence *); | |
| 184 static void record_const_or_copy (tree, tree); | |
| 185 static void record_equality (tree, tree); | |
| 186 static void record_equivalences_from_phis (basic_block); | |
| 187 static void record_equivalences_from_incoming_edge (basic_block); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
188 static void eliminate_redundant_computations (gimple_stmt_iterator *); |
| 0 | 189 static void record_equivalences_from_stmt (gimple, int); |
| 190 static void dom_thread_across_edge (struct dom_walk_data *, edge); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
191 static void dom_opt_leave_block (struct dom_walk_data *, basic_block); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
192 static void dom_opt_enter_block (struct dom_walk_data *, basic_block); |
| 0 | 193 static void remove_local_expressions_from_table (void); |
| 194 static void restore_vars_to_original_value (void); | |
| 195 static edge single_incoming_edge_ignoring_loop_edges (basic_block); | |
| 196 | |
| 197 | |
| 198 /* Given a statement STMT, initialize the hash table element pointed to | |
| 199 by ELEMENT. */ | |
| 200 | |
| 201 static void | |
| 202 initialize_hash_element (gimple stmt, tree lhs, | |
| 203 struct expr_hash_elt *element) | |
| 204 { | |
| 205 enum gimple_code code = gimple_code (stmt); | |
| 206 struct hashable_expr *expr = &element->expr; | |
| 207 | |
| 208 if (code == GIMPLE_ASSIGN) | |
| 209 { | |
| 210 enum tree_code subcode = gimple_assign_rhs_code (stmt); | |
| 211 | |
| 212 expr->type = NULL_TREE; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
213 |
| 0 | 214 switch (get_gimple_rhs_class (subcode)) |
| 215 { | |
| 216 case GIMPLE_SINGLE_RHS: | |
| 217 expr->kind = EXPR_SINGLE; | |
| 218 expr->ops.single.rhs = gimple_assign_rhs1 (stmt); | |
| 219 break; | |
| 220 case GIMPLE_UNARY_RHS: | |
| 221 expr->kind = EXPR_UNARY; | |
| 222 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
| 223 expr->ops.unary.op = subcode; | |
| 224 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt); | |
| 225 break; | |
| 226 case GIMPLE_BINARY_RHS: | |
| 227 expr->kind = EXPR_BINARY; | |
| 228 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
| 229 expr->ops.binary.op = subcode; | |
| 230 expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt); | |
| 231 expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt); | |
| 232 break; | |
| 233 default: | |
| 234 gcc_unreachable (); | |
| 235 } | |
| 236 } | |
| 237 else if (code == GIMPLE_COND) | |
| 238 { | |
| 239 expr->type = boolean_type_node; | |
| 240 expr->kind = EXPR_BINARY; | |
| 241 expr->ops.binary.op = gimple_cond_code (stmt); | |
| 242 expr->ops.binary.opnd0 = gimple_cond_lhs (stmt); | |
| 243 expr->ops.binary.opnd1 = gimple_cond_rhs (stmt); | |
| 244 } | |
| 245 else if (code == GIMPLE_CALL) | |
| 246 { | |
| 247 size_t nargs = gimple_call_num_args (stmt); | |
| 248 size_t i; | |
| 249 | |
| 250 gcc_assert (gimple_call_lhs (stmt)); | |
| 251 | |
| 252 expr->type = TREE_TYPE (gimple_call_lhs (stmt)); | |
| 253 expr->kind = EXPR_CALL; | |
| 254 expr->ops.call.fn = gimple_call_fn (stmt); | |
| 255 | |
| 256 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)) | |
| 257 expr->ops.call.pure = true; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
258 else |
| 0 | 259 expr->ops.call.pure = false; |
| 260 | |
| 261 expr->ops.call.nargs = nargs; | |
| 262 expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree)); | |
| 263 for (i = 0; i < nargs; i++) | |
| 264 expr->ops.call.args[i] = gimple_call_arg (stmt, i); | |
| 265 } | |
| 266 else if (code == GIMPLE_SWITCH) | |
| 267 { | |
| 268 expr->type = TREE_TYPE (gimple_switch_index (stmt)); | |
| 269 expr->kind = EXPR_SINGLE; | |
| 270 expr->ops.single.rhs = gimple_switch_index (stmt); | |
| 271 } | |
| 272 else if (code == GIMPLE_GOTO) | |
| 273 { | |
| 274 expr->type = TREE_TYPE (gimple_goto_dest (stmt)); | |
| 275 expr->kind = EXPR_SINGLE; | |
| 276 expr->ops.single.rhs = gimple_goto_dest (stmt); | |
| 277 } | |
| 278 else | |
| 279 gcc_unreachable (); | |
| 280 | |
| 281 element->lhs = lhs; | |
| 282 element->stmt = stmt; | |
| 283 element->hash = avail_expr_hash (element); | |
| 284 element->stamp = element; | |
| 285 } | |
| 286 | |
| 287 /* Given a conditional expression COND as a tree, initialize | |
| 288 a hashable_expr expression EXPR. The conditional must be a | |
| 289 comparison or logical negation. A constant or a variable is | |
| 290 not permitted. */ | |
| 291 | |
| 292 static void | |
| 293 initialize_expr_from_cond (tree cond, struct hashable_expr *expr) | |
| 294 { | |
| 295 expr->type = boolean_type_node; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
296 |
| 0 | 297 if (COMPARISON_CLASS_P (cond)) |
| 298 { | |
| 299 expr->kind = EXPR_BINARY; | |
| 300 expr->ops.binary.op = TREE_CODE (cond); | |
| 301 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0); | |
| 302 expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1); | |
| 303 } | |
| 304 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) | |
| 305 { | |
| 306 expr->kind = EXPR_UNARY; | |
| 307 expr->ops.unary.op = TRUTH_NOT_EXPR; | |
| 308 expr->ops.unary.opnd = TREE_OPERAND (cond, 0); | |
| 309 } | |
| 310 else | |
| 311 gcc_unreachable (); | |
| 312 } | |
| 313 | |
| 314 /* Given a hashable_expr expression EXPR and an LHS, | |
| 315 initialize the hash table element pointed to by ELEMENT. */ | |
| 316 | |
| 317 static void | |
| 318 initialize_hash_element_from_expr (struct hashable_expr *expr, | |
| 319 tree lhs, | |
| 320 struct expr_hash_elt *element) | |
| 321 { | |
| 322 element->expr = *expr; | |
| 323 element->lhs = lhs; | |
| 324 element->stmt = NULL; | |
| 325 element->hash = avail_expr_hash (element); | |
| 326 element->stamp = element; | |
| 327 } | |
| 328 | |
| 329 /* Compare two hashable_expr structures for equivalence. | |
| 330 They are considered equivalent when the the expressions | |
| 331 they denote must necessarily be equal. The logic is intended | |
| 332 to follow that of operand_equal_p in fold-const.c */ | |
| 333 | |
| 334 static bool | |
| 335 hashable_expr_equal_p (const struct hashable_expr *expr0, | |
| 336 const struct hashable_expr *expr1) | |
| 337 { | |
| 338 tree type0 = expr0->type; | |
| 339 tree type1 = expr1->type; | |
| 340 | |
| 341 /* If either type is NULL, there is nothing to check. */ | |
| 342 if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE)) | |
| 343 return false; | |
| 344 | |
| 345 /* If both types don't have the same signedness, precision, and mode, | |
| 346 then we can't consider them equal. */ | |
| 347 if (type0 != type1 | |
| 348 && (TREE_CODE (type0) == ERROR_MARK | |
| 349 || TREE_CODE (type1) == ERROR_MARK | |
| 350 || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1) | |
| 351 || TYPE_PRECISION (type0) != TYPE_PRECISION (type1) | |
| 352 || TYPE_MODE (type0) != TYPE_MODE (type1))) | |
| 353 return false; | |
| 354 | |
| 355 if (expr0->kind != expr1->kind) | |
| 356 return false; | |
| 357 | |
| 358 switch (expr0->kind) | |
| 359 { | |
| 360 case EXPR_SINGLE: | |
| 361 return operand_equal_p (expr0->ops.single.rhs, | |
| 362 expr1->ops.single.rhs, 0); | |
| 363 | |
| 364 case EXPR_UNARY: | |
| 365 if (expr0->ops.unary.op != expr1->ops.unary.op) | |
| 366 return false; | |
| 367 | |
| 368 if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op) | |
| 369 || expr0->ops.unary.op == NON_LVALUE_EXPR) | |
| 370 && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type)) | |
| 371 return false; | |
| 372 | |
| 373 return operand_equal_p (expr0->ops.unary.opnd, | |
| 374 expr1->ops.unary.opnd, 0); | |
| 375 | |
| 376 case EXPR_BINARY: | |
| 377 { | |
| 378 if (expr0->ops.binary.op != expr1->ops.binary.op) | |
| 379 return false; | |
| 380 | |
| 381 if (operand_equal_p (expr0->ops.binary.opnd0, | |
| 382 expr1->ops.binary.opnd0, 0) | |
| 383 && operand_equal_p (expr0->ops.binary.opnd1, | |
| 384 expr1->ops.binary.opnd1, 0)) | |
| 385 return true; | |
| 386 | |
| 387 /* For commutative ops, allow the other order. */ | |
| 388 return (commutative_tree_code (expr0->ops.binary.op) | |
| 389 && operand_equal_p (expr0->ops.binary.opnd0, | |
| 390 expr1->ops.binary.opnd1, 0) | |
| 391 && operand_equal_p (expr0->ops.binary.opnd1, | |
| 392 expr1->ops.binary.opnd0, 0)); | |
| 393 } | |
| 394 | |
| 395 case EXPR_CALL: | |
| 396 { | |
| 397 size_t i; | |
| 398 | |
| 399 /* If the calls are to different functions, then they | |
| 400 clearly cannot be equal. */ | |
| 401 if (! operand_equal_p (expr0->ops.call.fn, | |
| 402 expr1->ops.call.fn, 0)) | |
| 403 return false; | |
| 404 | |
| 405 if (! expr0->ops.call.pure) | |
| 406 return false; | |
| 407 | |
| 408 if (expr0->ops.call.nargs != expr1->ops.call.nargs) | |
| 409 return false; | |
| 410 | |
| 411 for (i = 0; i < expr0->ops.call.nargs; i++) | |
| 412 if (! operand_equal_p (expr0->ops.call.args[i], | |
| 413 expr1->ops.call.args[i], 0)) | |
| 414 return false; | |
| 415 | |
| 416 return true; | |
| 417 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
418 |
| 0 | 419 default: |
| 420 gcc_unreachable (); | |
| 421 } | |
| 422 } | |
| 423 | |
| 424 /* Compute a hash value for a hashable_expr value EXPR and a | |
| 425 previously accumulated hash value VAL. If two hashable_expr | |
| 426 values compare equal with hashable_expr_equal_p, they must | |
| 427 hash to the same value, given an identical value of VAL. | |
| 428 The logic is intended to follow iterative_hash_expr in tree.c. */ | |
| 429 | |
| 430 static hashval_t | |
| 431 iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val) | |
| 432 { | |
| 433 switch (expr->kind) | |
| 434 { | |
| 435 case EXPR_SINGLE: | |
| 436 val = iterative_hash_expr (expr->ops.single.rhs, val); | |
| 437 break; | |
| 438 | |
| 439 case EXPR_UNARY: | |
| 440 val = iterative_hash_object (expr->ops.unary.op, val); | |
| 441 | |
| 442 /* Make sure to include signedness in the hash computation. | |
| 443 Don't hash the type, that can lead to having nodes which | |
| 444 compare equal according to operand_equal_p, but which | |
| 445 have different hash codes. */ | |
| 446 if (CONVERT_EXPR_CODE_P (expr->ops.unary.op) | |
| 447 || expr->ops.unary.op == NON_LVALUE_EXPR) | |
| 448 val += TYPE_UNSIGNED (expr->type); | |
| 449 | |
| 450 val = iterative_hash_expr (expr->ops.unary.opnd, val); | |
| 451 break; | |
| 452 | |
| 453 case EXPR_BINARY: | |
| 454 val = iterative_hash_object (expr->ops.binary.op, val); | |
| 455 if (commutative_tree_code (expr->ops.binary.op)) | |
| 456 val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0, | |
| 457 expr->ops.binary.opnd1, val); | |
| 458 else | |
| 459 { | |
| 460 val = iterative_hash_expr (expr->ops.binary.opnd0, val); | |
| 461 val = iterative_hash_expr (expr->ops.binary.opnd1, val); | |
| 462 } | |
| 463 break; | |
| 464 | |
| 465 case EXPR_CALL: | |
| 466 { | |
| 467 size_t i; | |
| 468 enum tree_code code = CALL_EXPR; | |
| 469 | |
| 470 val = iterative_hash_object (code, val); | |
| 471 val = iterative_hash_expr (expr->ops.call.fn, val); | |
| 472 for (i = 0; i < expr->ops.call.nargs; i++) | |
| 473 val = iterative_hash_expr (expr->ops.call.args[i], val); | |
| 474 } | |
| 475 break; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
476 |
| 0 | 477 default: |
| 478 gcc_unreachable (); | |
| 479 } | |
| 480 | |
| 481 return val; | |
| 482 } | |
| 483 | |
| 484 /* Print a diagnostic dump of an expression hash table entry. */ | |
| 485 | |
| 486 static void | |
| 487 print_expr_hash_elt (FILE * stream, const struct expr_hash_elt *element) | |
| 488 { | |
| 489 if (element->stmt) | |
| 490 fprintf (stream, "STMT "); | |
| 491 else | |
| 492 fprintf (stream, "COND "); | |
| 493 | |
| 494 if (element->lhs) | |
| 495 { | |
| 496 print_generic_expr (stream, element->lhs, 0); | |
| 497 fprintf (stream, " = "); | |
| 498 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
499 |
| 0 | 500 switch (element->expr.kind) |
| 501 { | |
| 502 case EXPR_SINGLE: | |
| 503 print_generic_expr (stream, element->expr.ops.single.rhs, 0); | |
| 504 break; | |
| 505 | |
| 506 case EXPR_UNARY: | |
| 507 fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]); | |
| 508 print_generic_expr (stream, element->expr.ops.unary.opnd, 0); | |
| 509 break; | |
| 510 | |
| 511 case EXPR_BINARY: | |
| 512 print_generic_expr (stream, element->expr.ops.binary.opnd0, 0); | |
| 513 fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]); | |
| 514 print_generic_expr (stream, element->expr.ops.binary.opnd1, 0); | |
| 515 break; | |
| 516 | |
| 517 case EXPR_CALL: | |
| 518 { | |
| 519 size_t i; | |
| 520 size_t nargs = element->expr.ops.call.nargs; | |
| 521 | |
| 522 print_generic_expr (stream, element->expr.ops.call.fn, 0); | |
| 523 fprintf (stream, " ("); | |
| 524 for (i = 0; i < nargs; i++) | |
| 525 { | |
| 526 print_generic_expr (stream, element->expr.ops.call.args[i], 0); | |
| 527 if (i + 1 < nargs) | |
| 528 fprintf (stream, ", "); | |
| 529 } | |
| 530 fprintf (stream, ")"); | |
| 531 } | |
| 532 break; | |
| 533 } | |
| 534 fprintf (stream, "\n"); | |
| 535 | |
| 536 if (element->stmt) | |
| 537 { | |
| 538 fprintf (stream, " "); | |
| 539 print_gimple_stmt (stream, element->stmt, 0, 0); | |
| 540 } | |
| 541 } | |
| 542 | |
| 543 /* Delete an expr_hash_elt and reclaim its storage. */ | |
| 544 | |
| 545 static void | |
| 546 free_expr_hash_elt (void *elt) | |
| 547 { | |
| 548 struct expr_hash_elt *element = ((struct expr_hash_elt *)elt); | |
| 549 | |
| 550 if (element->expr.kind == EXPR_CALL) | |
| 551 free (element->expr.ops.call.args); | |
| 552 | |
| 553 free (element); | |
| 554 } | |
| 555 | |
| 556 /* Allocate an EDGE_INFO for edge E and attach it to E. | |
| 557 Return the new EDGE_INFO structure. */ | |
| 558 | |
| 559 static struct edge_info * | |
| 560 allocate_edge_info (edge e) | |
| 561 { | |
| 562 struct edge_info *edge_info; | |
| 563 | |
| 564 edge_info = XCNEW (struct edge_info); | |
| 565 | |
| 566 e->aux = edge_info; | |
| 567 return edge_info; | |
| 568 } | |
| 569 | |
| 570 /* Free all EDGE_INFO structures associated with edges in the CFG. | |
| 571 If a particular edge can be threaded, copy the redirection | |
| 572 target from the EDGE_INFO structure into the edge's AUX field | |
| 573 as required by code to update the CFG and SSA graph for | |
| 574 jump threading. */ | |
| 575 | |
| 576 static void | |
| 577 free_all_edge_infos (void) | |
| 578 { | |
| 579 basic_block bb; | |
| 580 edge_iterator ei; | |
| 581 edge e; | |
| 582 | |
| 583 FOR_EACH_BB (bb) | |
| 584 { | |
| 585 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 586 { | |
| 587 struct edge_info *edge_info = (struct edge_info *) e->aux; | |
| 588 | |
| 589 if (edge_info) | |
| 590 { | |
| 591 if (edge_info->cond_equivalences) | |
| 592 free (edge_info->cond_equivalences); | |
| 593 free (edge_info); | |
| 594 e->aux = NULL; | |
| 595 } | |
| 596 } | |
| 597 } | |
| 598 } | |
| 599 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
600 /* Jump threading, redundancy elimination and const/copy propagation. |
| 0 | 601 |
| 602 This pass may expose new symbols that need to be renamed into SSA. For | |
| 603 every new symbol exposed, its corresponding bit will be set in | |
| 604 VARS_TO_RENAME. */ | |
| 605 | |
| 606 static unsigned int | |
| 607 tree_ssa_dominator_optimize (void) | |
| 608 { | |
| 609 struct dom_walk_data walk_data; | |
| 610 | |
| 611 memset (&opt_stats, 0, sizeof (opt_stats)); | |
| 612 | |
| 613 /* Create our hash tables. */ | |
| 614 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt); | |
| 615 avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20); | |
| 616 const_and_copies_stack = VEC_alloc (tree, heap, 20); | |
| 617 need_eh_cleanup = BITMAP_ALLOC (NULL); | |
| 618 | |
| 619 /* Setup callbacks for the generic dominator tree walker. */ | |
| 620 walk_data.dom_direction = CDI_DOMINATORS; | |
| 621 walk_data.initialize_block_local_data = NULL; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
622 walk_data.before_dom_children = dom_opt_enter_block; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
623 walk_data.after_dom_children = dom_opt_leave_block; |
| 0 | 624 /* Right now we only attach a dummy COND_EXPR to the global data pointer. |
| 625 When we attach more stuff we'll need to fill this out with a real | |
| 626 structure. */ | |
| 627 walk_data.global_data = NULL; | |
| 628 walk_data.block_local_data_size = 0; | |
| 629 | |
| 630 /* Now initialize the dominator walker. */ | |
| 631 init_walk_dominator_tree (&walk_data); | |
| 632 | |
| 633 calculate_dominance_info (CDI_DOMINATORS); | |
| 634 cfg_altered = false; | |
| 635 | |
| 636 /* We need to know loop structures in order to avoid destroying them | |
| 637 in jump threading. Note that we still can e.g. thread through loop | |
| 638 headers to an exit edge, or through loop header to the loop body, assuming | |
| 639 that we update the loop info. */ | |
| 640 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES); | |
| 641 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
642 /* Initialize the value-handle array. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
643 threadedge_initialize_values (); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
644 |
| 0 | 645 /* We need accurate information regarding back edges in the CFG |
| 646 for jump threading; this may include back edges that are not part of | |
| 647 a single loop. */ | |
| 648 mark_dfs_back_edges (); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
649 |
| 0 | 650 /* Recursively walk the dominator tree optimizing statements. */ |
| 651 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); | |
| 652 | |
| 653 { | |
| 654 gimple_stmt_iterator gsi; | |
| 655 basic_block bb; | |
| 656 FOR_EACH_BB (bb) | |
| 657 {for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 658 update_stmt_if_modified (gsi_stmt (gsi)); | |
| 659 } | |
| 660 } | |
| 661 | |
| 662 /* If we exposed any new variables, go ahead and put them into | |
| 663 SSA form now, before we handle jump threading. This simplifies | |
| 664 interactions between rewriting of _DECL nodes into SSA form | |
| 665 and rewriting SSA_NAME nodes into SSA form after block | |
| 666 duplication and CFG manipulation. */ | |
| 667 update_ssa (TODO_update_ssa); | |
| 668 | |
| 669 free_all_edge_infos (); | |
| 670 | |
| 671 /* Thread jumps, creating duplicate blocks as needed. */ | |
| 672 cfg_altered |= thread_through_all_blocks (first_pass_instance); | |
| 673 | |
| 674 if (cfg_altered) | |
| 675 free_dominance_info (CDI_DOMINATORS); | |
| 676 | |
| 677 /* Removal of statements may make some EH edges dead. Purge | |
| 678 such edges from the CFG as needed. */ | |
| 679 if (!bitmap_empty_p (need_eh_cleanup)) | |
| 680 { | |
| 681 unsigned i; | |
| 682 bitmap_iterator bi; | |
| 683 | |
| 684 /* Jump threading may have created forwarder blocks from blocks | |
| 685 needing EH cleanup; the new successor of these blocks, which | |
| 686 has inherited from the original block, needs the cleanup. */ | |
| 687 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi) | |
| 688 { | |
| 689 basic_block bb = BASIC_BLOCK (i); | |
| 690 if (single_succ_p (bb) == 1 | |
| 691 && (single_succ_edge (bb)->flags & EDGE_EH) == 0) | |
| 692 { | |
| 693 bitmap_clear_bit (need_eh_cleanup, i); | |
| 694 bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index); | |
| 695 } | |
| 696 } | |
| 697 | |
| 698 gimple_purge_all_dead_eh_edges (need_eh_cleanup); | |
| 699 bitmap_zero (need_eh_cleanup); | |
| 700 } | |
| 701 | |
| 702 statistics_counter_event (cfun, "Redundant expressions eliminated", | |
| 703 opt_stats.num_re); | |
| 704 statistics_counter_event (cfun, "Constants propagated", | |
| 705 opt_stats.num_const_prop); | |
| 706 statistics_counter_event (cfun, "Copies propagated", | |
| 707 opt_stats.num_copy_prop); | |
| 708 | |
| 709 /* Debugging dumps. */ | |
| 710 if (dump_file && (dump_flags & TDF_STATS)) | |
| 711 dump_dominator_optimization_stats (dump_file); | |
| 712 | |
| 713 loop_optimizer_finalize (); | |
| 714 | |
| 715 /* Delete our main hashtable. */ | |
| 716 htab_delete (avail_exprs); | |
| 717 | |
| 718 /* And finalize the dominator walker. */ | |
| 719 fini_walk_dominator_tree (&walk_data); | |
| 720 | |
| 721 /* Free asserted bitmaps and stacks. */ | |
| 722 BITMAP_FREE (need_eh_cleanup); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
723 |
| 0 | 724 VEC_free (expr_hash_elt_t, heap, avail_exprs_stack); |
| 725 VEC_free (tree, heap, const_and_copies_stack); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
726 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
727 /* Free the value-handle array. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
728 threadedge_finalize_values (); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
729 ssa_name_values = NULL; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
730 |
| 0 | 731 return 0; |
| 732 } | |
| 733 | |
| 734 static bool | |
| 735 gate_dominator (void) | |
| 736 { | |
| 737 return flag_tree_dom != 0; | |
| 738 } | |
| 739 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
740 struct gimple_opt_pass pass_dominator = |
| 0 | 741 { |
| 742 { | |
| 743 GIMPLE_PASS, | |
| 744 "dom", /* name */ | |
| 745 gate_dominator, /* gate */ | |
| 746 tree_ssa_dominator_optimize, /* execute */ | |
| 747 NULL, /* sub */ | |
| 748 NULL, /* next */ | |
| 749 0, /* static_pass_number */ | |
| 750 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
751 PROP_cfg | PROP_ssa, /* properties_required */ |
| 0 | 752 0, /* properties_provided */ |
| 753 0, /* properties_destroyed */ | |
| 754 0, /* todo_flags_start */ | |
| 755 TODO_dump_func | |
| 756 | TODO_update_ssa | |
| 757 | TODO_cleanup_cfg | |
| 758 | TODO_verify_ssa /* todo_flags_finish */ | |
| 759 } | |
| 760 }; | |
| 761 | |
| 762 | |
| 763 /* Given a conditional statement CONDSTMT, convert the | |
| 764 condition to a canonical form. */ | |
| 765 | |
| 766 static void | |
| 767 canonicalize_comparison (gimple condstmt) | |
| 768 { | |
| 769 tree op0; | |
| 770 tree op1; | |
| 771 enum tree_code code; | |
| 772 | |
| 773 gcc_assert (gimple_code (condstmt) == GIMPLE_COND); | |
| 774 | |
| 775 op0 = gimple_cond_lhs (condstmt); | |
| 776 op1 = gimple_cond_rhs (condstmt); | |
| 777 | |
| 778 code = gimple_cond_code (condstmt); | |
| 779 | |
| 780 /* If it would be profitable to swap the operands, then do so to | |
| 781 canonicalize the statement, enabling better optimization. | |
| 782 | |
| 783 By placing canonicalization of such expressions here we | |
| 784 transparently keep statements in canonical form, even | |
| 785 when the statement is modified. */ | |
| 786 if (tree_swap_operands_p (op0, op1, false)) | |
| 787 { | |
| 788 /* For relationals we need to swap the operands | |
| 789 and change the code. */ | |
| 790 if (code == LT_EXPR | |
| 791 || code == GT_EXPR | |
| 792 || code == LE_EXPR | |
| 793 || code == GE_EXPR) | |
| 794 { | |
| 795 code = swap_tree_comparison (code); | |
| 796 | |
| 797 gimple_cond_set_code (condstmt, code); | |
| 798 gimple_cond_set_lhs (condstmt, op1); | |
| 799 gimple_cond_set_rhs (condstmt, op0); | |
| 800 | |
| 801 update_stmt (condstmt); | |
| 802 } | |
| 803 } | |
| 804 } | |
| 805 | |
| 806 /* Initialize local stacks for this optimizer and record equivalences | |
| 807 upon entry to BB. Equivalences can come from the edge traversed to | |
| 808 reach BB or they may come from PHI nodes at the start of BB. */ | |
| 809 | |
| 810 /* Remove all the expressions in LOCALS from TABLE, stopping when there are | |
| 811 LIMIT entries left in LOCALs. */ | |
| 812 | |
| 813 static void | |
| 814 remove_local_expressions_from_table (void) | |
| 815 { | |
| 816 /* Remove all the expressions made available in this block. */ | |
| 817 while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0) | |
| 818 { | |
| 819 expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
820 void **slot; |
| 0 | 821 |
| 822 if (victim == NULL) | |
| 823 break; | |
| 824 | |
| 825 /* This must precede the actual removal from the hash table, | |
| 826 as ELEMENT and the table entry may share a call argument | |
| 827 vector which will be freed during removal. */ | |
| 828 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 829 { | |
| 830 fprintf (dump_file, "<<<< "); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
831 print_expr_hash_elt (dump_file, victim); |
| 0 | 832 } |
| 833 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
834 slot = htab_find_slot_with_hash (avail_exprs, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
835 victim, victim->hash, NO_INSERT); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
836 gcc_assert (slot && *slot == (void *) victim); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
837 htab_clear_slot (avail_exprs, slot); |
| 0 | 838 } |
| 839 } | |
| 840 | |
| 841 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore | |
| 842 CONST_AND_COPIES to its original state, stopping when we hit a | |
| 843 NULL marker. */ | |
| 844 | |
| 845 static void | |
| 846 restore_vars_to_original_value (void) | |
| 847 { | |
| 848 while (VEC_length (tree, const_and_copies_stack) > 0) | |
| 849 { | |
| 850 tree prev_value, dest; | |
| 851 | |
| 852 dest = VEC_pop (tree, const_and_copies_stack); | |
| 853 | |
| 854 if (dest == NULL) | |
| 855 break; | |
| 856 | |
| 857 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 858 { | |
| 859 fprintf (dump_file, "<<<< COPY "); | |
| 860 print_generic_expr (dump_file, dest, 0); | |
| 861 fprintf (dump_file, " = "); | |
| 862 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0); | |
| 863 fprintf (dump_file, "\n"); | |
| 864 } | |
| 865 | |
| 866 prev_value = VEC_pop (tree, const_and_copies_stack); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
867 set_ssa_name_value (dest, prev_value); |
| 0 | 868 } |
| 869 } | |
| 870 | |
| 871 /* A trivial wrapper so that we can present the generic jump | |
| 872 threading code with a simple API for simplifying statements. */ | |
| 873 static tree | |
| 874 simplify_stmt_for_jump_threading (gimple stmt, | |
| 875 gimple within_stmt ATTRIBUTE_UNUSED) | |
| 876 { | |
| 877 return lookup_avail_expr (stmt, false); | |
| 878 } | |
| 879 | |
| 880 /* Wrapper for common code to attempt to thread an edge. For example, | |
| 881 it handles lazily building the dummy condition and the bookkeeping | |
| 882 when jump threading is successful. */ | |
| 883 | |
| 884 static void | |
| 885 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e) | |
| 886 { | |
| 887 if (! walk_data->global_data) | |
| 888 { | |
| 889 gimple dummy_cond = | |
| 890 gimple_build_cond (NE_EXPR, | |
| 891 integer_zero_node, integer_zero_node, | |
| 892 NULL, NULL); | |
| 893 walk_data->global_data = dummy_cond; | |
| 894 } | |
| 895 | |
| 896 thread_across_edge ((gimple) walk_data->global_data, e, false, | |
| 897 &const_and_copies_stack, | |
| 898 simplify_stmt_for_jump_threading); | |
| 899 } | |
| 900 | |
| 901 /* PHI nodes can create equivalences too. | |
| 902 | |
| 903 Ignoring any alternatives which are the same as the result, if | |
| 904 all the alternatives are equal, then the PHI node creates an | |
| 905 equivalence. */ | |
| 906 | |
| 907 static void | |
| 908 record_equivalences_from_phis (basic_block bb) | |
| 909 { | |
| 910 gimple_stmt_iterator gsi; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
911 |
| 0 | 912 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
| 913 { | |
| 914 gimple phi = gsi_stmt (gsi); | |
| 915 | |
| 916 tree lhs = gimple_phi_result (phi); | |
| 917 tree rhs = NULL; | |
| 918 size_t i; | |
| 919 | |
| 920 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
| 921 { | |
| 922 tree t = gimple_phi_arg_def (phi, i); | |
| 923 | |
| 924 /* Ignore alternatives which are the same as our LHS. Since | |
| 925 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we | |
| 926 can simply compare pointers. */ | |
| 927 if (lhs == t) | |
| 928 continue; | |
| 929 | |
| 930 /* If we have not processed an alternative yet, then set | |
| 931 RHS to this alternative. */ | |
| 932 if (rhs == NULL) | |
| 933 rhs = t; | |
| 934 /* If we have processed an alternative (stored in RHS), then | |
| 935 see if it is equal to this one. If it isn't, then stop | |
| 936 the search. */ | |
| 937 else if (! operand_equal_for_phi_arg_p (rhs, t)) | |
| 938 break; | |
| 939 } | |
| 940 | |
| 941 /* If we had no interesting alternatives, then all the RHS alternatives | |
| 942 must have been the same as LHS. */ | |
| 943 if (!rhs) | |
| 944 rhs = lhs; | |
| 945 | |
| 946 /* If we managed to iterate through each PHI alternative without | |
| 947 breaking out of the loop, then we have a PHI which may create | |
| 948 a useful equivalence. We do not need to record unwind data for | |
| 949 this, since this is a true assignment and not an equivalence | |
| 950 inferred from a comparison. All uses of this ssa name are dominated | |
| 951 by this assignment, so unwinding just costs time and space. */ | |
| 952 if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs)) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
953 set_ssa_name_value (lhs, rhs); |
| 0 | 954 } |
| 955 } | |
| 956 | |
| 957 /* Ignoring loop backedges, if BB has precisely one incoming edge then | |
| 958 return that edge. Otherwise return NULL. */ | |
| 959 static edge | |
| 960 single_incoming_edge_ignoring_loop_edges (basic_block bb) | |
| 961 { | |
| 962 edge retval = NULL; | |
| 963 edge e; | |
| 964 edge_iterator ei; | |
| 965 | |
| 966 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 967 { | |
| 968 /* A loop back edge can be identified by the destination of | |
| 969 the edge dominating the source of the edge. */ | |
| 970 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) | |
| 971 continue; | |
| 972 | |
| 973 /* If we have already seen a non-loop edge, then we must have | |
| 974 multiple incoming non-loop edges and thus we return NULL. */ | |
| 975 if (retval) | |
| 976 return NULL; | |
| 977 | |
| 978 /* This is the first non-loop incoming edge we have found. Record | |
| 979 it. */ | |
| 980 retval = e; | |
| 981 } | |
| 982 | |
| 983 return retval; | |
| 984 } | |
| 985 | |
| 986 /* Record any equivalences created by the incoming edge to BB. If BB | |
| 987 has more than one incoming edge, then no equivalence is created. */ | |
| 988 | |
| 989 static void | |
| 990 record_equivalences_from_incoming_edge (basic_block bb) | |
| 991 { | |
| 992 edge e; | |
| 993 basic_block parent; | |
| 994 struct edge_info *edge_info; | |
| 995 | |
| 996 /* If our parent block ended with a control statement, then we may be | |
| 997 able to record some equivalences based on which outgoing edge from | |
| 998 the parent was followed. */ | |
| 999 parent = get_immediate_dominator (CDI_DOMINATORS, bb); | |
| 1000 | |
| 1001 e = single_incoming_edge_ignoring_loop_edges (bb); | |
| 1002 | |
| 1003 /* If we had a single incoming edge from our parent block, then enter | |
| 1004 any data associated with the edge into our tables. */ | |
| 1005 if (e && e->src == parent) | |
| 1006 { | |
| 1007 unsigned int i; | |
| 1008 | |
| 1009 edge_info = (struct edge_info *) e->aux; | |
| 1010 | |
| 1011 if (edge_info) | |
| 1012 { | |
| 1013 tree lhs = edge_info->lhs; | |
| 1014 tree rhs = edge_info->rhs; | |
| 1015 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; | |
| 1016 | |
| 1017 if (lhs) | |
| 1018 record_equality (lhs, rhs); | |
| 1019 | |
| 1020 if (cond_equivalences) | |
| 1021 for (i = 0; i < edge_info->max_cond_equivalences; i++) | |
| 1022 record_cond (&cond_equivalences[i]); | |
| 1023 } | |
| 1024 } | |
| 1025 } | |
| 1026 | |
| 1027 /* Dump SSA statistics on FILE. */ | |
| 1028 | |
| 1029 void | |
| 1030 dump_dominator_optimization_stats (FILE *file) | |
| 1031 { | |
| 1032 fprintf (file, "Total number of statements: %6ld\n\n", | |
| 1033 opt_stats.num_stmts); | |
| 1034 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n", | |
| 1035 opt_stats.num_exprs_considered); | |
| 1036 | |
| 1037 fprintf (file, "\nHash table statistics:\n"); | |
| 1038 | |
| 1039 fprintf (file, " avail_exprs: "); | |
| 1040 htab_statistics (file, avail_exprs); | |
| 1041 } | |
| 1042 | |
| 1043 | |
| 1044 /* Dump SSA statistics on stderr. */ | |
| 1045 | |
| 1046 void | |
| 1047 debug_dominator_optimization_stats (void) | |
| 1048 { | |
| 1049 dump_dominator_optimization_stats (stderr); | |
| 1050 } | |
| 1051 | |
| 1052 | |
| 1053 /* Dump statistics for the hash table HTAB. */ | |
| 1054 | |
| 1055 static void | |
| 1056 htab_statistics (FILE *file, htab_t htab) | |
| 1057 { | |
| 1058 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", | |
| 1059 (long) htab_size (htab), | |
| 1060 (long) htab_elements (htab), | |
| 1061 htab_collisions (htab)); | |
| 1062 } | |
| 1063 | |
| 1064 | |
| 1065 /* Enter condition equivalence into the expression hash table. | |
| 1066 This indicates that a conditional expression has a known | |
| 1067 boolean value. */ | |
| 1068 | |
| 1069 static void | |
| 1070 record_cond (struct cond_equivalence *p) | |
| 1071 { | |
| 1072 struct expr_hash_elt *element = XCNEW (struct expr_hash_elt); | |
| 1073 void **slot; | |
| 1074 | |
| 1075 initialize_hash_element_from_expr (&p->cond, p->value, element); | |
| 1076 | |
| 1077 slot = htab_find_slot_with_hash (avail_exprs, (void *)element, | |
| 1078 element->hash, INSERT); | |
| 1079 if (*slot == NULL) | |
| 1080 { | |
| 1081 *slot = (void *) element; | |
| 1082 | |
| 1083 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1084 { | |
| 1085 fprintf (dump_file, "1>>> "); | |
| 1086 print_expr_hash_elt (dump_file, element); | |
| 1087 } | |
| 1088 | |
| 1089 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element); | |
| 1090 } | |
| 1091 else | |
| 1092 free (element); | |
| 1093 } | |
| 1094 | |
| 1095 /* Build a cond_equivalence record indicating that the comparison | |
| 1096 CODE holds between operands OP0 and OP1. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1097 |
| 0 | 1098 static void |
| 1099 build_and_record_new_cond (enum tree_code code, | |
| 1100 tree op0, tree op1, | |
| 1101 struct cond_equivalence *p) | |
| 1102 { | |
| 1103 struct hashable_expr *cond = &p->cond; | |
| 1104 | |
| 1105 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison); | |
| 1106 | |
| 1107 cond->type = boolean_type_node; | |
| 1108 cond->kind = EXPR_BINARY; | |
| 1109 cond->ops.binary.op = code; | |
| 1110 cond->ops.binary.opnd0 = op0; | |
| 1111 cond->ops.binary.opnd1 = op1; | |
| 1112 | |
| 1113 p->value = boolean_true_node; | |
| 1114 } | |
| 1115 | |
| 1116 /* Record that COND is true and INVERTED is false into the edge information | |
| 1117 structure. Also record that any conditions dominated by COND are true | |
| 1118 as well. | |
| 1119 | |
| 1120 For example, if a < b is true, then a <= b must also be true. */ | |
| 1121 | |
| 1122 static void | |
| 1123 record_conditions (struct edge_info *edge_info, tree cond, tree inverted) | |
| 1124 { | |
| 1125 tree op0, op1; | |
| 1126 | |
| 1127 if (!COMPARISON_CLASS_P (cond)) | |
| 1128 return; | |
| 1129 | |
| 1130 op0 = TREE_OPERAND (cond, 0); | |
| 1131 op1 = TREE_OPERAND (cond, 1); | |
| 1132 | |
| 1133 switch (TREE_CODE (cond)) | |
| 1134 { | |
| 1135 case LT_EXPR: | |
| 1136 case GT_EXPR: | |
| 1137 if (FLOAT_TYPE_P (TREE_TYPE (op0))) | |
| 1138 { | |
| 1139 edge_info->max_cond_equivalences = 6; | |
| 1140 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 6); | |
| 1141 build_and_record_new_cond (ORDERED_EXPR, op0, op1, | |
| 1142 &edge_info->cond_equivalences[4]); | |
| 1143 build_and_record_new_cond (LTGT_EXPR, op0, op1, | |
| 1144 &edge_info->cond_equivalences[5]); | |
| 1145 } | |
| 1146 else | |
| 1147 { | |
| 1148 edge_info->max_cond_equivalences = 4; | |
| 1149 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4); | |
| 1150 } | |
| 1151 | |
| 1152 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR | |
| 1153 ? LE_EXPR : GE_EXPR), | |
| 1154 op0, op1, &edge_info->cond_equivalences[2]); | |
| 1155 build_and_record_new_cond (NE_EXPR, op0, op1, | |
| 1156 &edge_info->cond_equivalences[3]); | |
| 1157 break; | |
| 1158 | |
| 1159 case GE_EXPR: | |
| 1160 case LE_EXPR: | |
| 1161 if (FLOAT_TYPE_P (TREE_TYPE (op0))) | |
| 1162 { | |
| 1163 edge_info->max_cond_equivalences = 3; | |
| 1164 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 3); | |
| 1165 build_and_record_new_cond (ORDERED_EXPR, op0, op1, | |
| 1166 &edge_info->cond_equivalences[2]); | |
| 1167 } | |
| 1168 else | |
| 1169 { | |
| 1170 edge_info->max_cond_equivalences = 2; | |
| 1171 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2); | |
| 1172 } | |
| 1173 break; | |
| 1174 | |
| 1175 case EQ_EXPR: | |
| 1176 if (FLOAT_TYPE_P (TREE_TYPE (op0))) | |
| 1177 { | |
| 1178 edge_info->max_cond_equivalences = 5; | |
| 1179 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 5); | |
| 1180 build_and_record_new_cond (ORDERED_EXPR, op0, op1, | |
| 1181 &edge_info->cond_equivalences[4]); | |
| 1182 } | |
| 1183 else | |
| 1184 { | |
| 1185 edge_info->max_cond_equivalences = 4; | |
| 1186 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4); | |
| 1187 } | |
| 1188 build_and_record_new_cond (LE_EXPR, op0, op1, | |
| 1189 &edge_info->cond_equivalences[2]); | |
| 1190 build_and_record_new_cond (GE_EXPR, op0, op1, | |
| 1191 &edge_info->cond_equivalences[3]); | |
| 1192 break; | |
| 1193 | |
| 1194 case UNORDERED_EXPR: | |
| 1195 edge_info->max_cond_equivalences = 8; | |
| 1196 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 8); | |
| 1197 build_and_record_new_cond (NE_EXPR, op0, op1, | |
| 1198 &edge_info->cond_equivalences[2]); | |
| 1199 build_and_record_new_cond (UNLE_EXPR, op0, op1, | |
| 1200 &edge_info->cond_equivalences[3]); | |
| 1201 build_and_record_new_cond (UNGE_EXPR, op0, op1, | |
| 1202 &edge_info->cond_equivalences[4]); | |
| 1203 build_and_record_new_cond (UNEQ_EXPR, op0, op1, | |
| 1204 &edge_info->cond_equivalences[5]); | |
| 1205 build_and_record_new_cond (UNLT_EXPR, op0, op1, | |
| 1206 &edge_info->cond_equivalences[6]); | |
| 1207 build_and_record_new_cond (UNGT_EXPR, op0, op1, | |
| 1208 &edge_info->cond_equivalences[7]); | |
| 1209 break; | |
| 1210 | |
| 1211 case UNLT_EXPR: | |
| 1212 case UNGT_EXPR: | |
| 1213 edge_info->max_cond_equivalences = 4; | |
| 1214 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4); | |
| 1215 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR | |
| 1216 ? UNLE_EXPR : UNGE_EXPR), | |
| 1217 op0, op1, &edge_info->cond_equivalences[2]); | |
| 1218 build_and_record_new_cond (NE_EXPR, op0, op1, | |
| 1219 &edge_info->cond_equivalences[3]); | |
| 1220 break; | |
| 1221 | |
| 1222 case UNEQ_EXPR: | |
| 1223 edge_info->max_cond_equivalences = 4; | |
| 1224 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4); | |
| 1225 build_and_record_new_cond (UNLE_EXPR, op0, op1, | |
| 1226 &edge_info->cond_equivalences[2]); | |
| 1227 build_and_record_new_cond (UNGE_EXPR, op0, op1, | |
| 1228 &edge_info->cond_equivalences[3]); | |
| 1229 break; | |
| 1230 | |
| 1231 case LTGT_EXPR: | |
| 1232 edge_info->max_cond_equivalences = 4; | |
| 1233 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4); | |
| 1234 build_and_record_new_cond (NE_EXPR, op0, op1, | |
| 1235 &edge_info->cond_equivalences[2]); | |
| 1236 build_and_record_new_cond (ORDERED_EXPR, op0, op1, | |
| 1237 &edge_info->cond_equivalences[3]); | |
| 1238 break; | |
| 1239 | |
| 1240 default: | |
| 1241 edge_info->max_cond_equivalences = 2; | |
| 1242 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2); | |
| 1243 break; | |
| 1244 } | |
| 1245 | |
| 1246 /* Now store the original true and false conditions into the first | |
| 1247 two slots. */ | |
| 1248 initialize_expr_from_cond (cond, &edge_info->cond_equivalences[0].cond); | |
| 1249 edge_info->cond_equivalences[0].value = boolean_true_node; | |
| 1250 | |
| 1251 /* It is possible for INVERTED to be the negation of a comparison, | |
| 1252 and not a valid RHS or GIMPLE_COND condition. This happens because | |
| 1253 invert_truthvalue may return such an expression when asked to invert | |
| 1254 a floating-point comparison. These comparisons are not assumed to | |
| 1255 obey the trichotomy law. */ | |
| 1256 initialize_expr_from_cond (inverted, &edge_info->cond_equivalences[1].cond); | |
| 1257 edge_info->cond_equivalences[1].value = boolean_false_node; | |
| 1258 } | |
| 1259 | |
| 1260 /* A helper function for record_const_or_copy and record_equality. | |
| 1261 Do the work of recording the value and undo info. */ | |
| 1262 | |
| 1263 static void | |
| 1264 record_const_or_copy_1 (tree x, tree y, tree prev_x) | |
| 1265 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1266 set_ssa_name_value (x, y); |
| 0 | 1267 |
| 1268 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1269 { | |
| 1270 fprintf (dump_file, "0>>> COPY "); | |
| 1271 print_generic_expr (dump_file, x, 0); | |
| 1272 fprintf (dump_file, " = "); | |
| 1273 print_generic_expr (dump_file, y, 0); | |
| 1274 fprintf (dump_file, "\n"); | |
| 1275 } | |
| 1276 | |
| 1277 VEC_reserve (tree, heap, const_and_copies_stack, 2); | |
| 1278 VEC_quick_push (tree, const_and_copies_stack, prev_x); | |
| 1279 VEC_quick_push (tree, const_and_copies_stack, x); | |
| 1280 } | |
| 1281 | |
| 1282 /* Return the loop depth of the basic block of the defining statement of X. | |
| 1283 This number should not be treated as absolutely correct because the loop | |
| 1284 information may not be completely up-to-date when dom runs. However, it | |
| 1285 will be relatively correct, and as more passes are taught to keep loop info | |
| 1286 up to date, the result will become more and more accurate. */ | |
| 1287 | |
| 1288 int | |
| 1289 loop_depth_of_name (tree x) | |
| 1290 { | |
| 1291 gimple defstmt; | |
| 1292 basic_block defbb; | |
| 1293 | |
| 1294 /* If it's not an SSA_NAME, we have no clue where the definition is. */ | |
| 1295 if (TREE_CODE (x) != SSA_NAME) | |
| 1296 return 0; | |
| 1297 | |
| 1298 /* Otherwise return the loop depth of the defining statement's bb. | |
| 1299 Note that there may not actually be a bb for this statement, if the | |
| 1300 ssa_name is live on entry. */ | |
| 1301 defstmt = SSA_NAME_DEF_STMT (x); | |
| 1302 defbb = gimple_bb (defstmt); | |
| 1303 if (!defbb) | |
| 1304 return 0; | |
| 1305 | |
| 1306 return defbb->loop_depth; | |
| 1307 } | |
| 1308 | |
| 1309 /* Record that X is equal to Y in const_and_copies. Record undo | |
| 1310 information in the block-local vector. */ | |
| 1311 | |
| 1312 static void | |
| 1313 record_const_or_copy (tree x, tree y) | |
| 1314 { | |
| 1315 tree prev_x = SSA_NAME_VALUE (x); | |
| 1316 | |
| 1317 gcc_assert (TREE_CODE (x) == SSA_NAME); | |
| 1318 | |
| 1319 if (TREE_CODE (y) == SSA_NAME) | |
| 1320 { | |
| 1321 tree tmp = SSA_NAME_VALUE (y); | |
| 1322 if (tmp) | |
| 1323 y = tmp; | |
| 1324 } | |
| 1325 | |
| 1326 record_const_or_copy_1 (x, y, prev_x); | |
| 1327 } | |
| 1328 | |
| 1329 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR. | |
| 1330 This constrains the cases in which we may treat this as assignment. */ | |
| 1331 | |
| 1332 static void | |
| 1333 record_equality (tree x, tree y) | |
| 1334 { | |
| 1335 tree prev_x = NULL, prev_y = NULL; | |
| 1336 | |
| 1337 if (TREE_CODE (x) == SSA_NAME) | |
| 1338 prev_x = SSA_NAME_VALUE (x); | |
| 1339 if (TREE_CODE (y) == SSA_NAME) | |
| 1340 prev_y = SSA_NAME_VALUE (y); | |
| 1341 | |
| 1342 /* If one of the previous values is invariant, or invariant in more loops | |
| 1343 (by depth), then use that. | |
| 1344 Otherwise it doesn't matter which value we choose, just so | |
| 1345 long as we canonicalize on one value. */ | |
| 1346 if (is_gimple_min_invariant (y)) | |
| 1347 ; | |
| 1348 else if (is_gimple_min_invariant (x) | |
| 1349 || (loop_depth_of_name (x) <= loop_depth_of_name (y))) | |
| 1350 prev_x = x, x = y, y = prev_x, prev_x = prev_y; | |
| 1351 else if (prev_x && is_gimple_min_invariant (prev_x)) | |
| 1352 x = y, y = prev_x, prev_x = prev_y; | |
| 1353 else if (prev_y) | |
| 1354 y = prev_y; | |
| 1355 | |
| 1356 /* After the swapping, we must have one SSA_NAME. */ | |
| 1357 if (TREE_CODE (x) != SSA_NAME) | |
| 1358 return; | |
| 1359 | |
| 1360 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a | |
| 1361 variable compared against zero. If we're honoring signed zeros, | |
| 1362 then we cannot record this value unless we know that the value is | |
| 1363 nonzero. */ | |
| 1364 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x))) | |
| 1365 && (TREE_CODE (y) != REAL_CST | |
| 1366 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y)))) | |
| 1367 return; | |
| 1368 | |
| 1369 record_const_or_copy_1 (x, y, prev_x); | |
| 1370 } | |
| 1371 | |
| 1372 /* Returns true when STMT is a simple iv increment. It detects the | |
| 1373 following situation: | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1374 |
| 0 | 1375 i_1 = phi (..., i_2) |
| 1376 i_2 = i_1 +/- ... */ | |
| 1377 | |
| 1378 static bool | |
| 1379 simple_iv_increment_p (gimple stmt) | |
| 1380 { | |
| 1381 tree lhs, preinc; | |
| 1382 gimple phi; | |
| 1383 size_t i; | |
| 1384 | |
| 1385 if (gimple_code (stmt) != GIMPLE_ASSIGN) | |
| 1386 return false; | |
| 1387 | |
| 1388 lhs = gimple_assign_lhs (stmt); | |
| 1389 if (TREE_CODE (lhs) != SSA_NAME) | |
| 1390 return false; | |
| 1391 | |
| 1392 if (gimple_assign_rhs_code (stmt) != PLUS_EXPR | |
| 1393 && gimple_assign_rhs_code (stmt) != MINUS_EXPR) | |
| 1394 return false; | |
| 1395 | |
| 1396 preinc = gimple_assign_rhs1 (stmt); | |
| 1397 | |
| 1398 if (TREE_CODE (preinc) != SSA_NAME) | |
| 1399 return false; | |
| 1400 | |
| 1401 phi = SSA_NAME_DEF_STMT (preinc); | |
| 1402 if (gimple_code (phi) != GIMPLE_PHI) | |
| 1403 return false; | |
| 1404 | |
| 1405 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
| 1406 if (gimple_phi_arg_def (phi, i) == lhs) | |
| 1407 return true; | |
| 1408 | |
| 1409 return false; | |
| 1410 } | |
| 1411 | |
| 1412 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1413 known value for that SSA_NAME (or NULL if no value is known). |
| 0 | 1414 |
| 1415 Propagate values from CONST_AND_COPIES into the PHI nodes of the | |
| 1416 successors of BB. */ | |
| 1417 | |
| 1418 static void | |
| 1419 cprop_into_successor_phis (basic_block bb) | |
| 1420 { | |
| 1421 edge e; | |
| 1422 edge_iterator ei; | |
| 1423 | |
| 1424 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 1425 { | |
| 1426 int indx; | |
| 1427 gimple_stmt_iterator gsi; | |
| 1428 | |
| 1429 /* If this is an abnormal edge, then we do not want to copy propagate | |
| 1430 into the PHI alternative associated with this edge. */ | |
| 1431 if (e->flags & EDGE_ABNORMAL) | |
| 1432 continue; | |
| 1433 | |
| 1434 gsi = gsi_start_phis (e->dest); | |
| 1435 if (gsi_end_p (gsi)) | |
| 1436 continue; | |
| 1437 | |
| 1438 indx = e->dest_idx; | |
| 1439 for ( ; !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 1440 { | |
| 1441 tree new_val; | |
| 1442 use_operand_p orig_p; | |
| 1443 tree orig_val; | |
| 1444 gimple phi = gsi_stmt (gsi); | |
| 1445 | |
| 1446 /* The alternative may be associated with a constant, so verify | |
| 1447 it is an SSA_NAME before doing anything with it. */ | |
| 1448 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx); | |
| 1449 orig_val = get_use_from_ptr (orig_p); | |
| 1450 if (TREE_CODE (orig_val) != SSA_NAME) | |
| 1451 continue; | |
| 1452 | |
| 1453 /* If we have *ORIG_P in our constant/copy table, then replace | |
| 1454 ORIG_P with its value in our constant/copy table. */ | |
| 1455 new_val = SSA_NAME_VALUE (orig_val); | |
| 1456 if (new_val | |
| 1457 && new_val != orig_val | |
| 1458 && (TREE_CODE (new_val) == SSA_NAME | |
| 1459 || is_gimple_min_invariant (new_val)) | |
| 1460 && may_propagate_copy (orig_val, new_val)) | |
| 1461 propagate_value (orig_p, new_val); | |
| 1462 } | |
| 1463 } | |
| 1464 } | |
| 1465 | |
| 1466 /* We have finished optimizing BB, record any information implied by | |
| 1467 taking a specific outgoing edge from BB. */ | |
| 1468 | |
| 1469 static void | |
| 1470 record_edge_info (basic_block bb) | |
| 1471 { | |
| 1472 gimple_stmt_iterator gsi = gsi_last_bb (bb); | |
| 1473 struct edge_info *edge_info; | |
| 1474 | |
| 1475 if (! gsi_end_p (gsi)) | |
| 1476 { | |
| 1477 gimple stmt = gsi_stmt (gsi); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1478 location_t loc = gimple_location (stmt); |
| 0 | 1479 |
| 1480 if (gimple_code (stmt) == GIMPLE_SWITCH) | |
| 1481 { | |
| 1482 tree index = gimple_switch_index (stmt); | |
| 1483 | |
| 1484 if (TREE_CODE (index) == SSA_NAME) | |
| 1485 { | |
| 1486 int i; | |
| 1487 int n_labels = gimple_switch_num_labels (stmt); | |
| 1488 tree *info = XCNEWVEC (tree, last_basic_block); | |
| 1489 edge e; | |
| 1490 edge_iterator ei; | |
| 1491 | |
| 1492 for (i = 0; i < n_labels; i++) | |
| 1493 { | |
| 1494 tree label = gimple_switch_label (stmt, i); | |
| 1495 basic_block target_bb = label_to_block (CASE_LABEL (label)); | |
| 1496 if (CASE_HIGH (label) | |
| 1497 || !CASE_LOW (label) | |
| 1498 || info[target_bb->index]) | |
| 1499 info[target_bb->index] = error_mark_node; | |
| 1500 else | |
| 1501 info[target_bb->index] = label; | |
| 1502 } | |
| 1503 | |
| 1504 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 1505 { | |
| 1506 basic_block target_bb = e->dest; | |
| 1507 tree label = info[target_bb->index]; | |
| 1508 | |
| 1509 if (label != NULL && label != error_mark_node) | |
| 1510 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1511 tree x = fold_convert_loc (loc, TREE_TYPE (index), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1512 CASE_LOW (label)); |
| 0 | 1513 edge_info = allocate_edge_info (e); |
| 1514 edge_info->lhs = index; | |
| 1515 edge_info->rhs = x; | |
| 1516 } | |
| 1517 } | |
| 1518 free (info); | |
| 1519 } | |
| 1520 } | |
| 1521 | |
| 1522 /* A COND_EXPR may create equivalences too. */ | |
| 1523 if (gimple_code (stmt) == GIMPLE_COND) | |
| 1524 { | |
| 1525 edge true_edge; | |
| 1526 edge false_edge; | |
| 1527 | |
| 1528 tree op0 = gimple_cond_lhs (stmt); | |
| 1529 tree op1 = gimple_cond_rhs (stmt); | |
| 1530 enum tree_code code = gimple_cond_code (stmt); | |
| 1531 | |
| 1532 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
| 1533 | |
| 1534 /* Special case comparing booleans against a constant as we | |
| 1535 know the value of OP0 on both arms of the branch. i.e., we | |
| 1536 can record an equivalence for OP0 rather than COND. */ | |
| 1537 if ((code == EQ_EXPR || code == NE_EXPR) | |
| 1538 && TREE_CODE (op0) == SSA_NAME | |
| 1539 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE | |
| 1540 && is_gimple_min_invariant (op1)) | |
| 1541 { | |
| 1542 if (code == EQ_EXPR) | |
| 1543 { | |
| 1544 edge_info = allocate_edge_info (true_edge); | |
| 1545 edge_info->lhs = op0; | |
| 1546 edge_info->rhs = (integer_zerop (op1) | |
| 1547 ? boolean_false_node | |
| 1548 : boolean_true_node); | |
| 1549 | |
| 1550 edge_info = allocate_edge_info (false_edge); | |
| 1551 edge_info->lhs = op0; | |
| 1552 edge_info->rhs = (integer_zerop (op1) | |
| 1553 ? boolean_true_node | |
| 1554 : boolean_false_node); | |
| 1555 } | |
| 1556 else | |
| 1557 { | |
| 1558 edge_info = allocate_edge_info (true_edge); | |
| 1559 edge_info->lhs = op0; | |
| 1560 edge_info->rhs = (integer_zerop (op1) | |
| 1561 ? boolean_true_node | |
| 1562 : boolean_false_node); | |
| 1563 | |
| 1564 edge_info = allocate_edge_info (false_edge); | |
| 1565 edge_info->lhs = op0; | |
| 1566 edge_info->rhs = (integer_zerop (op1) | |
| 1567 ? boolean_false_node | |
| 1568 : boolean_true_node); | |
| 1569 } | |
| 1570 } | |
| 1571 else if (is_gimple_min_invariant (op0) | |
| 1572 && (TREE_CODE (op1) == SSA_NAME | |
| 1573 || is_gimple_min_invariant (op1))) | |
| 1574 { | |
| 1575 tree cond = build2 (code, boolean_type_node, op0, op1); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1576 tree inverted = invert_truthvalue_loc (loc, cond); |
| 0 | 1577 struct edge_info *edge_info; |
| 1578 | |
| 1579 edge_info = allocate_edge_info (true_edge); | |
| 1580 record_conditions (edge_info, cond, inverted); | |
| 1581 | |
| 1582 if (code == EQ_EXPR) | |
| 1583 { | |
| 1584 edge_info->lhs = op1; | |
| 1585 edge_info->rhs = op0; | |
| 1586 } | |
| 1587 | |
| 1588 edge_info = allocate_edge_info (false_edge); | |
| 1589 record_conditions (edge_info, inverted, cond); | |
| 1590 | |
| 1591 if (code == NE_EXPR) | |
| 1592 { | |
| 1593 edge_info->lhs = op1; | |
| 1594 edge_info->rhs = op0; | |
| 1595 } | |
| 1596 } | |
| 1597 | |
| 1598 else if (TREE_CODE (op0) == SSA_NAME | |
| 1599 && (is_gimple_min_invariant (op1) | |
| 1600 || TREE_CODE (op1) == SSA_NAME)) | |
| 1601 { | |
| 1602 tree cond = build2 (code, boolean_type_node, op0, op1); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1603 tree inverted = invert_truthvalue_loc (loc, cond); |
| 0 | 1604 struct edge_info *edge_info; |
| 1605 | |
| 1606 edge_info = allocate_edge_info (true_edge); | |
| 1607 record_conditions (edge_info, cond, inverted); | |
| 1608 | |
| 1609 if (code == EQ_EXPR) | |
| 1610 { | |
| 1611 edge_info->lhs = op0; | |
| 1612 edge_info->rhs = op1; | |
| 1613 } | |
| 1614 | |
| 1615 edge_info = allocate_edge_info (false_edge); | |
| 1616 record_conditions (edge_info, inverted, cond); | |
| 1617 | |
| 1618 if (TREE_CODE (cond) == NE_EXPR) | |
| 1619 { | |
| 1620 edge_info->lhs = op0; | |
| 1621 edge_info->rhs = op1; | |
| 1622 } | |
| 1623 } | |
| 1624 } | |
| 1625 | |
| 1626 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ | |
| 1627 } | |
| 1628 } | |
| 1629 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1630 static void |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1631 dom_opt_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1632 basic_block bb) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1633 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1634 gimple_stmt_iterator gsi; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1635 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1636 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1637 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1638 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1639 /* Push a marker on the stacks of local information so that we know how |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1640 far to unwind when we finalize this block. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1641 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1642 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1643 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1644 record_equivalences_from_incoming_edge (bb); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1645 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1646 /* PHI nodes can create equivalences too. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1647 record_equivalences_from_phis (bb); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1648 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1649 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1650 optimize_stmt (bb, gsi); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1651 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1652 /* Now prepare to process dominated blocks. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1653 record_edge_info (bb); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1654 cprop_into_successor_phis (bb); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1655 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1656 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1657 /* We have finished processing the dominator children of BB, perform |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1658 any finalization actions in preparation for leaving this node in |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1659 the dominator tree. */ |
| 0 | 1660 |
| 1661 static void | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1662 dom_opt_leave_block (struct dom_walk_data *walk_data, basic_block bb) |
| 0 | 1663 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1664 gimple last; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1665 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1666 /* If we have an outgoing edge to a block with multiple incoming and |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1667 outgoing edges, then we may be able to thread the edge, i.e., we |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1668 may be able to statically determine which of the outgoing edges |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1669 will be traversed when the incoming edge from BB is traversed. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1670 if (single_succ_p (bb) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1671 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1672 && potentially_threadable_block (single_succ (bb))) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1673 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1674 dom_thread_across_edge (walk_data, single_succ_edge (bb)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1675 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1676 else if ((last = last_stmt (bb)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1677 && gimple_code (last) == GIMPLE_COND |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1678 && EDGE_COUNT (bb->succs) == 2 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1679 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1680 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1681 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1682 edge true_edge, false_edge; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1683 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1684 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1685 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1686 /* Only try to thread the edge if it reaches a target block with |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1687 more than one predecessor and more than one successor. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1688 if (potentially_threadable_block (true_edge->dest)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1689 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1690 struct edge_info *edge_info; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1691 unsigned int i; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1692 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1693 /* Push a marker onto the available expression stack so that we |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1694 unwind any expressions related to the TRUE arm before processing |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1695 the false arm below. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1696 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1697 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1698 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1699 edge_info = (struct edge_info *) true_edge->aux; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1700 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1701 /* If we have info associated with this edge, record it into |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1702 our equivalence tables. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1703 if (edge_info) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1704 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1705 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1706 tree lhs = edge_info->lhs; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1707 tree rhs = edge_info->rhs; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1708 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1709 /* If we have a simple NAME = VALUE equivalence, record it. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1710 if (lhs && TREE_CODE (lhs) == SSA_NAME) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1711 record_const_or_copy (lhs, rhs); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1712 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1713 /* If we have 0 = COND or 1 = COND equivalences, record them |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1714 into our expression hash tables. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1715 if (cond_equivalences) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1716 for (i = 0; i < edge_info->max_cond_equivalences; i++) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1717 record_cond (&cond_equivalences[i]); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1718 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1719 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1720 dom_thread_across_edge (walk_data, true_edge); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1721 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1722 /* And restore the various tables to their state before |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1723 we threaded this edge. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1724 remove_local_expressions_from_table (); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1725 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1726 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1727 /* Similarly for the ELSE arm. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1728 if (potentially_threadable_block (false_edge->dest)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1729 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1730 struct edge_info *edge_info; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1731 unsigned int i; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1732 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1733 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1734 edge_info = (struct edge_info *) false_edge->aux; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1735 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1736 /* If we have info associated with this edge, record it into |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1737 our equivalence tables. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1738 if (edge_info) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1739 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1740 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1741 tree lhs = edge_info->lhs; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1742 tree rhs = edge_info->rhs; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1743 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1744 /* If we have a simple NAME = VALUE equivalence, record it. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1745 if (lhs && TREE_CODE (lhs) == SSA_NAME) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1746 record_const_or_copy (lhs, rhs); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1747 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1748 /* If we have 0 = COND or 1 = COND equivalences, record them |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1749 into our expression hash tables. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1750 if (cond_equivalences) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1751 for (i = 0; i < edge_info->max_cond_equivalences; i++) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1752 record_cond (&cond_equivalences[i]); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1753 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1754 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1755 /* Now thread the edge. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1756 dom_thread_across_edge (walk_data, false_edge); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1757 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1758 /* No need to remove local expressions from our tables |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1759 or restore vars to their original value as that will |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1760 be done immediately below. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1761 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1762 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1763 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1764 remove_local_expressions_from_table (); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1765 restore_vars_to_original_value (); |
| 0 | 1766 } |
| 1767 | |
| 1768 /* Search for redundant computations in STMT. If any are found, then | |
| 1769 replace them with the variable holding the result of the computation. | |
| 1770 | |
| 1771 If safe, record this expression into the available expression hash | |
| 1772 table. */ | |
| 1773 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1774 static void |
| 0 | 1775 eliminate_redundant_computations (gimple_stmt_iterator* gsi) |
| 1776 { | |
| 1777 tree expr_type; | |
| 1778 tree cached_lhs; | |
| 1779 bool insert = true; | |
| 1780 bool assigns_var_p = false; | |
| 1781 | |
| 1782 gimple stmt = gsi_stmt (*gsi); | |
| 1783 | |
| 1784 tree def = gimple_get_lhs (stmt); | |
| 1785 | |
| 1786 /* Certain expressions on the RHS can be optimized away, but can not | |
| 1787 themselves be entered into the hash tables. */ | |
| 1788 if (! def | |
| 1789 || TREE_CODE (def) != SSA_NAME | |
| 1790 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1791 || gimple_vdef (stmt) |
| 0 | 1792 /* Do not record equivalences for increments of ivs. This would create |
| 1793 overlapping live ranges for a very questionable gain. */ | |
| 1794 || simple_iv_increment_p (stmt)) | |
| 1795 insert = false; | |
| 1796 | |
| 1797 /* Check if the expression has been computed before. */ | |
| 1798 cached_lhs = lookup_avail_expr (stmt, insert); | |
| 1799 | |
| 1800 opt_stats.num_exprs_considered++; | |
| 1801 | |
| 1802 /* Get the type of the expression we are trying to optimize. */ | |
| 1803 if (is_gimple_assign (stmt)) | |
| 1804 { | |
| 1805 expr_type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
| 1806 assigns_var_p = true; | |
| 1807 } | |
| 1808 else if (gimple_code (stmt) == GIMPLE_COND) | |
| 1809 expr_type = boolean_type_node; | |
| 1810 else if (is_gimple_call (stmt)) | |
| 1811 { | |
| 1812 gcc_assert (gimple_call_lhs (stmt)); | |
| 1813 expr_type = TREE_TYPE (gimple_call_lhs (stmt)); | |
| 1814 assigns_var_p = true; | |
| 1815 } | |
| 1816 else if (gimple_code (stmt) == GIMPLE_SWITCH) | |
| 1817 expr_type = TREE_TYPE (gimple_switch_index (stmt)); | |
| 1818 else | |
| 1819 gcc_unreachable (); | |
| 1820 | |
| 1821 if (!cached_lhs) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1822 return; |
| 0 | 1823 |
| 1824 /* It is safe to ignore types here since we have already done | |
| 1825 type checking in the hashing and equality routines. In fact | |
| 1826 type checking here merely gets in the way of constant | |
| 1827 propagation. Also, make sure that it is safe to propagate | |
| 1828 CACHED_LHS into the expression in STMT. */ | |
| 1829 if ((TREE_CODE (cached_lhs) != SSA_NAME | |
| 1830 && (assigns_var_p | |
| 1831 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))) | |
| 1832 || may_propagate_copy_into_stmt (stmt, cached_lhs)) | |
| 1833 { | |
| 1834 #if defined ENABLE_CHECKING | |
| 1835 gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME | |
| 1836 || is_gimple_min_invariant (cached_lhs)); | |
| 1837 #endif | |
| 1838 | |
| 1839 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1840 { | |
| 1841 fprintf (dump_file, " Replaced redundant expr '"); | |
| 1842 print_gimple_expr (dump_file, stmt, 0, dump_flags); | |
| 1843 fprintf (dump_file, "' with '"); | |
| 1844 print_generic_expr (dump_file, cached_lhs, dump_flags); | |
| 1845 fprintf (dump_file, "'\n"); | |
| 1846 } | |
| 1847 | |
| 1848 opt_stats.num_re++; | |
| 1849 | |
| 1850 if (assigns_var_p | |
| 1851 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))) | |
| 1852 cached_lhs = fold_convert (expr_type, cached_lhs); | |
| 1853 | |
| 1854 propagate_tree_value_into_stmt (gsi, cached_lhs); | |
| 1855 | |
| 1856 /* Since it is always necessary to mark the result as modified, | |
| 1857 perhaps we should move this into propagate_tree_value_into_stmt | |
| 1858 itself. */ | |
| 1859 gimple_set_modified (gsi_stmt (*gsi), true); | |
| 1860 } | |
| 1861 } | |
| 1862 | |
| 1863 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either | |
| 1864 the available expressions table or the const_and_copies table. | |
| 1865 Detect and record those equivalences. */ | |
| 1866 /* We handle only very simple copy equivalences here. The heavy | |
| 1867 lifing is done by eliminate_redundant_computations. */ | |
| 1868 | |
| 1869 static void | |
| 1870 record_equivalences_from_stmt (gimple stmt, int may_optimize_p) | |
| 1871 { | |
| 1872 tree lhs; | |
| 1873 enum tree_code lhs_code; | |
| 1874 | |
| 1875 gcc_assert (is_gimple_assign (stmt)); | |
| 1876 | |
| 1877 lhs = gimple_assign_lhs (stmt); | |
| 1878 lhs_code = TREE_CODE (lhs); | |
| 1879 | |
| 1880 if (lhs_code == SSA_NAME | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1881 && gimple_assign_single_p (stmt)) |
| 0 | 1882 { |
| 1883 tree rhs = gimple_assign_rhs1 (stmt); | |
| 1884 | |
| 1885 /* If the RHS of the assignment is a constant or another variable that | |
| 1886 may be propagated, register it in the CONST_AND_COPIES table. We | |
| 1887 do not need to record unwind data for this, since this is a true | |
| 1888 assignment and not an equivalence inferred from a comparison. All | |
| 1889 uses of this ssa name are dominated by this assignment, so unwinding | |
| 1890 just costs time and space. */ | |
| 1891 if (may_optimize_p | |
| 1892 && (TREE_CODE (rhs) == SSA_NAME | |
| 1893 || is_gimple_min_invariant (rhs))) | |
| 1894 { | |
| 1895 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1896 { | |
| 1897 fprintf (dump_file, "==== ASGN "); | |
| 1898 print_generic_expr (dump_file, lhs, 0); | |
| 1899 fprintf (dump_file, " = "); | |
| 1900 print_generic_expr (dump_file, rhs, 0); | |
| 1901 fprintf (dump_file, "\n"); | |
| 1902 } | |
| 1903 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1904 set_ssa_name_value (lhs, rhs); |
| 0 | 1905 } |
| 1906 } | |
| 1907 | |
| 1908 /* A memory store, even an aliased store, creates a useful | |
| 1909 equivalence. By exchanging the LHS and RHS, creating suitable | |
| 1910 vops and recording the result in the available expression table, | |
| 1911 we may be able to expose more redundant loads. */ | |
| 1912 if (!gimple_has_volatile_ops (stmt) | |
| 1913 && gimple_references_memory_p (stmt) | |
| 1914 && gimple_assign_single_p (stmt) | |
| 1915 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
| 1916 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) | |
| 1917 && !is_gimple_reg (lhs)) | |
| 1918 { | |
| 1919 tree rhs = gimple_assign_rhs1 (stmt); | |
| 1920 gimple new_stmt; | |
| 1921 | |
| 1922 /* Build a new statement with the RHS and LHS exchanged. */ | |
| 1923 if (TREE_CODE (rhs) == SSA_NAME) | |
| 1924 { | |
| 1925 /* NOTE tuples. The call to gimple_build_assign below replaced | |
| 1926 a call to build_gimple_modify_stmt, which did not set the | |
| 1927 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so | |
| 1928 may cause an SSA validation failure, as the LHS may be a | |
| 1929 default-initialized name and should have no definition. I'm | |
| 1930 a bit dubious of this, as the artificial statement that we | |
| 1931 generate here may in fact be ill-formed, but it is simply | |
| 1932 used as an internal device in this pass, and never becomes | |
| 1933 part of the CFG. */ | |
| 1934 gimple defstmt = SSA_NAME_DEF_STMT (rhs); | |
| 1935 new_stmt = gimple_build_assign (rhs, lhs); | |
| 1936 SSA_NAME_DEF_STMT (rhs) = defstmt; | |
| 1937 } | |
| 1938 else | |
| 1939 new_stmt = gimple_build_assign (rhs, lhs); | |
| 1940 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1941 gimple_set_vuse (new_stmt, gimple_vdef (stmt)); |
| 0 | 1942 |
| 1943 /* Finally enter the statement into the available expression | |
| 1944 table. */ | |
| 1945 lookup_avail_expr (new_stmt, true); | |
| 1946 } | |
| 1947 } | |
| 1948 | |
| 1949 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from | |
| 1950 CONST_AND_COPIES. */ | |
| 1951 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1952 static void |
| 0 | 1953 cprop_operand (gimple stmt, use_operand_p op_p) |
| 1954 { | |
| 1955 tree val; | |
| 1956 tree op = USE_FROM_PTR (op_p); | |
| 1957 | |
| 1958 /* If the operand has a known constant value or it is known to be a | |
| 1959 copy of some other variable, use the value or copy stored in | |
| 1960 CONST_AND_COPIES. */ | |
| 1961 val = SSA_NAME_VALUE (op); | |
| 1962 if (val && val != op) | |
| 1963 { | |
| 1964 /* Do not change the base variable in the virtual operand | |
| 1965 tables. That would make it impossible to reconstruct | |
| 1966 the renamed virtual operand if we later modify this | |
| 1967 statement. Also only allow the new value to be an SSA_NAME | |
| 1968 for propagation into virtual operands. */ | |
| 1969 if (!is_gimple_reg (op) | |
| 1970 && (TREE_CODE (val) != SSA_NAME | |
| 1971 || is_gimple_reg (val) | |
| 1972 || get_virtual_var (val) != get_virtual_var (op))) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1973 return; |
| 0 | 1974 |
| 1975 /* Do not replace hard register operands in asm statements. */ | |
| 1976 if (gimple_code (stmt) == GIMPLE_ASM | |
| 1977 && !may_propagate_copy_into_asm (op)) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1978 return; |
| 0 | 1979 |
| 1980 /* Certain operands are not allowed to be copy propagated due | |
| 1981 to their interaction with exception handling and some GCC | |
| 1982 extensions. */ | |
| 1983 if (!may_propagate_copy (op, val)) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1984 return; |
| 0 | 1985 |
| 1986 /* Do not propagate addresses that point to volatiles into memory | |
| 1987 stmts without volatile operands. */ | |
| 1988 if (POINTER_TYPE_P (TREE_TYPE (val)) | |
| 1989 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val))) | |
| 1990 && gimple_has_mem_ops (stmt) | |
| 1991 && !gimple_has_volatile_ops (stmt)) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1992 return; |
| 0 | 1993 |
| 1994 /* Do not propagate copies if the propagated value is at a deeper loop | |
| 1995 depth than the propagatee. Otherwise, this may move loop variant | |
| 1996 variables outside of their loops and prevent coalescing | |
| 1997 opportunities. If the value was loop invariant, it will be hoisted | |
| 1998 by LICM and exposed for copy propagation. */ | |
| 1999 if (loop_depth_of_name (val) > loop_depth_of_name (op)) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2000 return; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2001 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2002 /* Do not propagate copies into simple IV increment statements. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2003 See PR23821 for how this can disturb IV analysis. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2004 if (TREE_CODE (val) != INTEGER_CST |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2005 && simple_iv_increment_p (stmt)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2006 return; |
| 0 | 2007 |
| 2008 /* Dump details. */ | |
| 2009 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2010 { | |
| 2011 fprintf (dump_file, " Replaced '"); | |
| 2012 print_generic_expr (dump_file, op, dump_flags); | |
| 2013 fprintf (dump_file, "' with %s '", | |
| 2014 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable")); | |
| 2015 print_generic_expr (dump_file, val, dump_flags); | |
| 2016 fprintf (dump_file, "'\n"); | |
| 2017 } | |
| 2018 | |
| 2019 if (TREE_CODE (val) != SSA_NAME) | |
| 2020 opt_stats.num_const_prop++; | |
| 2021 else | |
| 2022 opt_stats.num_copy_prop++; | |
| 2023 | |
| 2024 propagate_value (op_p, val); | |
| 2025 | |
| 2026 /* And note that we modified this statement. This is now | |
| 2027 safe, even if we changed virtual operands since we will | |
| 2028 rescan the statement and rewrite its operands again. */ | |
| 2029 gimple_set_modified (stmt, true); | |
| 2030 } | |
| 2031 } | |
| 2032 | |
| 2033 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2034 known value for that SSA_NAME (or NULL if no value is known). |
| 0 | 2035 |
| 2036 Propagate values from CONST_AND_COPIES into the uses, vuses and | |
| 2037 vdef_ops of STMT. */ | |
| 2038 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2039 static void |
| 0 | 2040 cprop_into_stmt (gimple stmt) |
| 2041 { | |
| 2042 use_operand_p op_p; | |
| 2043 ssa_op_iter iter; | |
| 2044 | |
| 2045 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES) | |
| 2046 { | |
| 2047 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2048 cprop_operand (stmt, op_p); |
| 0 | 2049 } |
| 2050 } | |
| 2051 | |
| 2052 /* Optimize the statement pointed to by iterator SI. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2053 |
| 0 | 2054 We try to perform some simplistic global redundancy elimination and |
| 2055 constant propagation: | |
| 2056 | |
| 2057 1- To detect global redundancy, we keep track of expressions that have | |
| 2058 been computed in this block and its dominators. If we find that the | |
| 2059 same expression is computed more than once, we eliminate repeated | |
| 2060 computations by using the target of the first one. | |
| 2061 | |
| 2062 2- Constant values and copy assignments. This is used to do very | |
| 2063 simplistic constant and copy propagation. When a constant or copy | |
| 2064 assignment is found, we map the value on the RHS of the assignment to | |
| 2065 the variable in the LHS in the CONST_AND_COPIES table. */ | |
| 2066 | |
| 2067 static void | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2068 optimize_stmt (basic_block bb, gimple_stmt_iterator si) |
| 0 | 2069 { |
| 2070 gimple stmt, old_stmt; | |
| 2071 bool may_optimize_p; | |
| 2072 bool modified_p = false; | |
| 2073 | |
| 2074 old_stmt = stmt = gsi_stmt (si); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2075 |
| 0 | 2076 if (gimple_code (stmt) == GIMPLE_COND) |
| 2077 canonicalize_comparison (stmt); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2078 |
| 0 | 2079 update_stmt_if_modified (stmt); |
| 2080 opt_stats.num_stmts++; | |
| 2081 | |
| 2082 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2083 { | |
| 2084 fprintf (dump_file, "Optimizing statement "); | |
| 2085 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 2086 } | |
| 2087 | |
| 2088 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2089 cprop_into_stmt (stmt); |
| 0 | 2090 |
| 2091 /* If the statement has been modified with constant replacements, | |
| 2092 fold its RHS before checking for redundant computations. */ | |
| 2093 if (gimple_modified_p (stmt)) | |
| 2094 { | |
| 2095 tree rhs = NULL; | |
| 2096 | |
| 2097 /* Try to fold the statement making sure that STMT is kept | |
| 2098 up to date. */ | |
| 2099 if (fold_stmt (&si)) | |
| 2100 { | |
| 2101 stmt = gsi_stmt (si); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2102 gimple_set_modified (stmt, true); |
| 0 | 2103 |
| 2104 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2105 { | |
| 2106 fprintf (dump_file, " Folded to: "); | |
| 2107 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 2108 } | |
| 2109 } | |
| 2110 | |
| 2111 /* We only need to consider cases that can yield a gimple operand. */ | |
| 2112 if (gimple_assign_single_p (stmt)) | |
| 2113 rhs = gimple_assign_rhs1 (stmt); | |
| 2114 else if (gimple_code (stmt) == GIMPLE_GOTO) | |
| 2115 rhs = gimple_goto_dest (stmt); | |
| 2116 else if (gimple_code (stmt) == GIMPLE_SWITCH) | |
| 2117 /* This should never be an ADDR_EXPR. */ | |
| 2118 rhs = gimple_switch_index (stmt); | |
| 2119 | |
| 2120 if (rhs && TREE_CODE (rhs) == ADDR_EXPR) | |
| 2121 recompute_tree_invariant_for_addr_expr (rhs); | |
| 2122 | |
| 2123 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called, | |
| 2124 even if fold_stmt updated the stmt already and thus cleared | |
| 2125 gimple_modified_p flag on it. */ | |
| 2126 modified_p = true; | |
| 2127 } | |
| 2128 | |
| 2129 /* Check for redundant computations. Do this optimization only | |
| 2130 for assignments that have no volatile ops and conditionals. */ | |
| 2131 may_optimize_p = (!gimple_has_volatile_ops (stmt) | |
| 2132 && ((is_gimple_assign (stmt) | |
| 2133 && !gimple_rhs_has_side_effects (stmt)) | |
| 2134 || (is_gimple_call (stmt) | |
| 2135 && gimple_call_lhs (stmt) != NULL_TREE | |
| 2136 && !gimple_rhs_has_side_effects (stmt)) | |
| 2137 || gimple_code (stmt) == GIMPLE_COND | |
| 2138 || gimple_code (stmt) == GIMPLE_SWITCH)); | |
| 2139 | |
| 2140 if (may_optimize_p) | |
| 2141 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2142 if (gimple_code (stmt) == GIMPLE_CALL) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2143 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2144 /* Resolve __builtin_constant_p. If it hasn't been |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2145 folded to integer_one_node by now, it's fairly |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2146 certain that the value simply isn't constant. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2147 tree callee = gimple_call_fndecl (stmt); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2148 if (callee |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2149 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2150 && DECL_FUNCTION_CODE (callee) == BUILT_IN_CONSTANT_P) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2151 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2152 propagate_tree_value_into_stmt (&si, integer_zero_node); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2153 stmt = gsi_stmt (si); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2154 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2155 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2156 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2157 update_stmt_if_modified (stmt); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2158 eliminate_redundant_computations (&si); |
| 0 | 2159 stmt = gsi_stmt (si); |
| 2160 } | |
| 2161 | |
| 2162 /* Record any additional equivalences created by this statement. */ | |
| 2163 if (is_gimple_assign (stmt)) | |
| 2164 record_equivalences_from_stmt (stmt, may_optimize_p); | |
| 2165 | |
| 2166 /* If STMT is a COND_EXPR and it was modified, then we may know | |
| 2167 where it goes. If that is the case, then mark the CFG as altered. | |
| 2168 | |
| 2169 This will cause us to later call remove_unreachable_blocks and | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2170 cleanup_tree_cfg when it is safe to do so. It is not safe to |
| 0 | 2171 clean things up here since removal of edges and such can trigger |
| 2172 the removal of PHI nodes, which in turn can release SSA_NAMEs to | |
| 2173 the manager. | |
| 2174 | |
| 2175 That's all fine and good, except that once SSA_NAMEs are released | |
| 2176 to the manager, we must not call create_ssa_name until all references | |
| 2177 to released SSA_NAMEs have been eliminated. | |
| 2178 | |
| 2179 All references to the deleted SSA_NAMEs can not be eliminated until | |
| 2180 we remove unreachable blocks. | |
| 2181 | |
| 2182 We can not remove unreachable blocks until after we have completed | |
| 2183 any queued jump threading. | |
| 2184 | |
| 2185 We can not complete any queued jump threads until we have taken | |
| 2186 appropriate variables out of SSA form. Taking variables out of | |
| 2187 SSA form can call create_ssa_name and thus we lose. | |
| 2188 | |
| 2189 Ultimately I suspect we're going to need to change the interface | |
| 2190 into the SSA_NAME manager. */ | |
| 2191 if (gimple_modified_p (stmt) || modified_p) | |
| 2192 { | |
| 2193 tree val = NULL; | |
| 2194 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2195 update_stmt_if_modified (stmt); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2196 |
| 0 | 2197 if (gimple_code (stmt) == GIMPLE_COND) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2198 val = fold_binary_loc (gimple_location (stmt), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2199 gimple_cond_code (stmt), boolean_type_node, |
| 0 | 2200 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); |
| 2201 else if (gimple_code (stmt) == GIMPLE_SWITCH) | |
| 2202 val = gimple_switch_index (stmt); | |
| 2203 | |
| 2204 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val)) | |
| 2205 cfg_altered = true; | |
| 2206 | |
| 2207 /* If we simplified a statement in such a way as to be shown that it | |
| 2208 cannot trap, update the eh information and the cfg to match. */ | |
| 2209 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) | |
| 2210 { | |
| 2211 bitmap_set_bit (need_eh_cleanup, bb->index); | |
| 2212 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2213 fprintf (dump_file, " Flagged to clear EH edges.\n"); | |
| 2214 } | |
| 2215 } | |
| 2216 } | |
| 2217 | |
| 2218 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. | |
| 2219 If found, return its LHS. Otherwise insert STMT in the table and | |
| 2220 return NULL_TREE. | |
| 2221 | |
| 2222 Also, when an expression is first inserted in the table, it is also | |
| 2223 is also added to AVAIL_EXPRS_STACK, so that it can be removed when | |
| 2224 we finish processing this block and its children. */ | |
| 2225 | |
| 2226 static tree | |
| 2227 lookup_avail_expr (gimple stmt, bool insert) | |
| 2228 { | |
| 2229 void **slot; | |
| 2230 tree lhs; | |
| 2231 tree temp; | |
| 2232 struct expr_hash_elt *element = XNEW (struct expr_hash_elt); | |
| 2233 | |
| 2234 /* Get LHS of assignment or call, else NULL_TREE. */ | |
| 2235 lhs = gimple_get_lhs (stmt); | |
| 2236 | |
| 2237 initialize_hash_element (stmt, lhs, element); | |
| 2238 | |
| 2239 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2240 { | |
| 2241 fprintf (dump_file, "LKUP "); | |
| 2242 print_expr_hash_elt (dump_file, element); | |
| 2243 } | |
| 2244 | |
| 2245 /* Don't bother remembering constant assignments and copy operations. | |
| 2246 Constants and copy operations are handled by the constant/copy propagator | |
| 2247 in optimize_stmt. */ | |
| 2248 if (element->expr.kind == EXPR_SINGLE | |
| 2249 && (TREE_CODE (element->expr.ops.single.rhs) == SSA_NAME | |
| 2250 || is_gimple_min_invariant (element->expr.ops.single.rhs))) | |
| 2251 { | |
| 2252 free (element); | |
| 2253 return NULL_TREE; | |
| 2254 } | |
| 2255 | |
| 2256 /* Finally try to find the expression in the main expression hash table. */ | |
| 2257 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash, | |
| 2258 (insert ? INSERT : NO_INSERT)); | |
| 2259 if (slot == NULL) | |
| 2260 { | |
| 2261 free (element); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2262 return NULL_TREE; |
| 0 | 2263 } |
| 2264 | |
| 2265 if (*slot == NULL) | |
| 2266 { | |
| 2267 *slot = (void *) element; | |
| 2268 | |
| 2269 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2270 { | |
| 2271 fprintf (dump_file, "2>>> "); | |
| 2272 print_expr_hash_elt (dump_file, element); | |
| 2273 } | |
| 2274 | |
| 2275 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element); | |
| 2276 return NULL_TREE; | |
| 2277 } | |
| 2278 | |
| 2279 /* Extract the LHS of the assignment so that it can be used as the current | |
| 2280 definition of another variable. */ | |
| 2281 lhs = ((struct expr_hash_elt *)*slot)->lhs; | |
| 2282 | |
| 2283 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then | |
| 2284 use the value from the const_and_copies table. */ | |
| 2285 if (TREE_CODE (lhs) == SSA_NAME) | |
| 2286 { | |
| 2287 temp = SSA_NAME_VALUE (lhs); | |
| 2288 if (temp) | |
| 2289 lhs = temp; | |
| 2290 } | |
| 2291 | |
| 2292 free (element); | |
| 2293 | |
| 2294 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2295 { | |
| 2296 fprintf (dump_file, "FIND: "); | |
| 2297 print_generic_expr (dump_file, lhs, 0); | |
| 2298 fprintf (dump_file, "\n"); | |
| 2299 } | |
| 2300 | |
| 2301 return lhs; | |
| 2302 } | |
| 2303 | |
| 2304 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number | |
| 2305 for expressions using the code of the expression and the SSA numbers of | |
| 2306 its operands. */ | |
| 2307 | |
| 2308 static hashval_t | |
| 2309 avail_expr_hash (const void *p) | |
| 2310 { | |
| 2311 gimple stmt = ((const struct expr_hash_elt *)p)->stmt; | |
| 2312 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr; | |
| 2313 tree vuse; | |
| 2314 hashval_t val = 0; | |
| 2315 | |
| 2316 val = iterative_hash_hashable_expr (expr, val); | |
| 2317 | |
| 2318 /* If the hash table entry is not associated with a statement, then we | |
| 2319 can just hash the expression and not worry about virtual operands | |
| 2320 and such. */ | |
| 2321 if (!stmt) | |
| 2322 return val; | |
| 2323 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2324 /* Add the SSA version numbers of the vuse operand. This is important |
| 0 | 2325 because compound variables like arrays are not renamed in the |
| 2326 operands. Rather, the rename is done on the virtual variable | |
| 2327 representing all the elements of the array. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2328 if ((vuse = gimple_vuse (stmt))) |
| 0 | 2329 val = iterative_hash_expr (vuse, val); |
| 2330 | |
| 2331 return val; | |
| 2332 } | |
| 2333 | |
| 2334 static hashval_t | |
| 2335 real_avail_expr_hash (const void *p) | |
| 2336 { | |
| 2337 return ((const struct expr_hash_elt *)p)->hash; | |
| 2338 } | |
| 2339 | |
| 2340 static int | |
| 2341 avail_expr_eq (const void *p1, const void *p2) | |
| 2342 { | |
| 2343 gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt; | |
| 2344 const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr; | |
| 2345 const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp; | |
| 2346 gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt; | |
| 2347 const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr; | |
| 2348 const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp; | |
| 2349 | |
| 2350 /* This case should apply only when removing entries from the table. */ | |
| 2351 if (stamp1 == stamp2) | |
| 2352 return true; | |
| 2353 | |
| 2354 /* FIXME tuples: | |
| 2355 We add stmts to a hash table and them modify them. To detect the case | |
| 2356 that we modify a stmt and then search for it, we assume that the hash | |
| 2357 is always modified by that change. | |
| 2358 We have to fully check why this doesn't happen on trunk or rewrite | |
| 2359 this in a more reliable (and easier to understand) way. */ | |
| 2360 if (((const struct expr_hash_elt *)p1)->hash | |
| 2361 != ((const struct expr_hash_elt *)p2)->hash) | |
| 2362 return false; | |
| 2363 | |
| 2364 /* In case of a collision, both RHS have to be identical and have the | |
| 2365 same VUSE operands. */ | |
| 2366 if (hashable_expr_equal_p (expr1, expr2) | |
| 2367 && types_compatible_p (expr1->type, expr2->type)) | |
| 2368 { | |
| 2369 /* Note that STMT1 and/or STMT2 may be NULL. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2370 return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2371 == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE)); |
| 0 | 2372 } |
| 2373 | |
| 2374 return false; | |
| 2375 } | |
| 2376 | |
| 2377 /* PHI-ONLY copy and constant propagation. This pass is meant to clean | |
| 2378 up degenerate PHIs created by or exposed by jump threading. */ | |
| 2379 | |
| 2380 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return | |
| 2381 NULL. */ | |
| 2382 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2383 tree |
| 0 | 2384 degenerate_phi_result (gimple phi) |
| 2385 { | |
| 2386 tree lhs = gimple_phi_result (phi); | |
| 2387 tree val = NULL; | |
| 2388 size_t i; | |
| 2389 | |
| 2390 /* Ignoring arguments which are the same as LHS, if all the remaining | |
| 2391 arguments are the same, then the PHI is a degenerate and has the | |
| 2392 value of that common argument. */ | |
| 2393 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
| 2394 { | |
| 2395 tree arg = gimple_phi_arg_def (phi, i); | |
| 2396 | |
| 2397 if (arg == lhs) | |
| 2398 continue; | |
|
47
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2399 else if (!arg) |
|
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2400 break; |
| 0 | 2401 else if (!val) |
| 2402 val = arg; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2403 else if (arg == val) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2404 continue; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2405 /* We bring in some of operand_equal_p not only to speed things |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2406 up, but also to avoid crashing when dereferencing the type of |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2407 a released SSA name. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2408 else if (TREE_CODE (val) != TREE_CODE (arg) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2409 || TREE_CODE (val) == SSA_NAME |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2410 || !operand_equal_p (arg, val, 0)) |
| 0 | 2411 break; |
| 2412 } | |
| 2413 return (i == gimple_phi_num_args (phi) ? val : NULL); | |
| 2414 } | |
| 2415 | |
| 2416 /* Given a statement STMT, which is either a PHI node or an assignment, | |
| 2417 remove it from the IL. */ | |
| 2418 | |
| 2419 static void | |
| 2420 remove_stmt_or_phi (gimple stmt) | |
| 2421 { | |
| 2422 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
| 2423 | |
| 2424 if (gimple_code (stmt) == GIMPLE_PHI) | |
| 2425 remove_phi_node (&gsi, true); | |
| 2426 else | |
| 2427 { | |
| 2428 gsi_remove (&gsi, true); | |
| 2429 release_defs (stmt); | |
| 2430 } | |
| 2431 } | |
| 2432 | |
| 2433 /* Given a statement STMT, which is either a PHI node or an assignment, | |
| 2434 return the "rhs" of the node, in the case of a non-degenerate | |
| 2435 phi, NULL is returned. */ | |
| 2436 | |
| 2437 static tree | |
| 2438 get_rhs_or_phi_arg (gimple stmt) | |
| 2439 { | |
| 2440 if (gimple_code (stmt) == GIMPLE_PHI) | |
| 2441 return degenerate_phi_result (stmt); | |
| 2442 else if (gimple_assign_single_p (stmt)) | |
| 2443 return gimple_assign_rhs1 (stmt); | |
| 2444 else | |
| 2445 gcc_unreachable (); | |
| 2446 } | |
| 2447 | |
| 2448 | |
| 2449 /* Given a statement STMT, which is either a PHI node or an assignment, | |
| 2450 return the "lhs" of the node. */ | |
| 2451 | |
| 2452 static tree | |
| 2453 get_lhs_or_phi_result (gimple stmt) | |
| 2454 { | |
| 2455 if (gimple_code (stmt) == GIMPLE_PHI) | |
| 2456 return gimple_phi_result (stmt); | |
| 2457 else if (is_gimple_assign (stmt)) | |
| 2458 return gimple_assign_lhs (stmt); | |
| 2459 else | |
| 2460 gcc_unreachable (); | |
| 2461 } | |
| 2462 | |
| 2463 /* Propagate RHS into all uses of LHS (when possible). | |
| 2464 | |
| 2465 RHS and LHS are derived from STMT, which is passed in solely so | |
| 2466 that we can remove it if propagation is successful. | |
| 2467 | |
| 2468 When propagating into a PHI node or into a statement which turns | |
| 2469 into a trivial copy or constant initialization, set the | |
| 2470 appropriate bit in INTERESTING_NAMEs so that we will visit those | |
| 2471 nodes as well in an effort to pick up secondary optimization | |
| 2472 opportunities. */ | |
| 2473 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2474 static void |
| 0 | 2475 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names) |
| 2476 { | |
| 2477 /* First verify that propagation is valid and isn't going to move a | |
| 2478 loop variant variable outside its loop. */ | |
| 2479 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) | |
| 2480 && (TREE_CODE (rhs) != SSA_NAME | |
| 2481 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) | |
| 2482 && may_propagate_copy (lhs, rhs) | |
| 2483 && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs)) | |
| 2484 { | |
| 2485 use_operand_p use_p; | |
| 2486 imm_use_iterator iter; | |
| 2487 gimple use_stmt; | |
| 2488 bool all = true; | |
| 2489 | |
| 2490 /* Dump details. */ | |
| 2491 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2492 { | |
| 2493 fprintf (dump_file, " Replacing '"); | |
| 2494 print_generic_expr (dump_file, lhs, dump_flags); | |
| 2495 fprintf (dump_file, "' with %s '", | |
| 2496 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable")); | |
| 2497 print_generic_expr (dump_file, rhs, dump_flags); | |
| 2498 fprintf (dump_file, "'\n"); | |
| 2499 } | |
| 2500 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2501 /* Walk over every use of LHS and try to replace the use with RHS. |
| 0 | 2502 At this point the only reason why such a propagation would not |
| 2503 be successful would be if the use occurs in an ASM_EXPR. */ | |
| 2504 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) | |
| 2505 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2506 /* Leave debug stmts alone. If we succeed in propagating |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2507 all non-debug uses, we'll drop the DEF, and propagation |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2508 into debug stmts will occur then. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2509 if (gimple_debug_bind_p (use_stmt)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2510 continue; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2511 |
| 0 | 2512 /* It's not always safe to propagate into an ASM_EXPR. */ |
| 2513 if (gimple_code (use_stmt) == GIMPLE_ASM | |
| 2514 && ! may_propagate_copy_into_asm (lhs)) | |
| 2515 { | |
| 2516 all = false; | |
| 2517 continue; | |
| 2518 } | |
| 2519 | |
| 2520 /* Dump details. */ | |
| 2521 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2522 { | |
| 2523 fprintf (dump_file, " Original statement:"); | |
| 2524 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); | |
| 2525 } | |
| 2526 | |
| 2527 /* Propagate the RHS into this use of the LHS. */ | |
| 2528 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) | |
| 2529 propagate_value (use_p, rhs); | |
| 2530 | |
| 2531 /* Special cases to avoid useless calls into the folding | |
| 2532 routines, operand scanning, etc. | |
| 2533 | |
| 2534 First, propagation into a PHI may cause the PHI to become | |
| 2535 a degenerate, so mark the PHI as interesting. No other | |
| 2536 actions are necessary. | |
| 2537 | |
| 2538 Second, if we're propagating a virtual operand and the | |
| 2539 propagation does not change the underlying _DECL node for | |
| 2540 the virtual operand, then no further actions are necessary. */ | |
| 2541 if (gimple_code (use_stmt) == GIMPLE_PHI | |
| 2542 || (! is_gimple_reg (lhs) | |
| 2543 && TREE_CODE (rhs) == SSA_NAME | |
| 2544 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs))) | |
| 2545 { | |
| 2546 /* Dump details. */ | |
| 2547 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2548 { | |
| 2549 fprintf (dump_file, " Updated statement:"); | |
| 2550 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); | |
| 2551 } | |
| 2552 | |
| 2553 /* Propagation into a PHI may expose new degenerate PHIs, | |
| 2554 so mark the result of the PHI as interesting. */ | |
| 2555 if (gimple_code (use_stmt) == GIMPLE_PHI) | |
| 2556 { | |
| 2557 tree result = get_lhs_or_phi_result (use_stmt); | |
| 2558 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); | |
| 2559 } | |
| 2560 | |
| 2561 continue; | |
| 2562 } | |
| 2563 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2564 /* From this point onward we are propagating into a |
| 0 | 2565 real statement. Folding may (or may not) be possible, |
| 2566 we may expose new operands, expose dead EH edges, | |
| 2567 etc. */ | |
| 2568 /* NOTE tuples. In the tuples world, fold_stmt_inplace | |
| 2569 cannot fold a call that simplifies to a constant, | |
| 2570 because the GIMPLE_CALL must be replaced by a | |
| 2571 GIMPLE_ASSIGN, and there is no way to effect such a | |
| 2572 transformation in-place. We might want to consider | |
| 2573 using the more general fold_stmt here. */ | |
| 2574 fold_stmt_inplace (use_stmt); | |
| 2575 | |
| 2576 /* Sometimes propagation can expose new operands to the | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2577 renamer. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2578 update_stmt (use_stmt); |
| 0 | 2579 |
| 2580 /* Dump details. */ | |
| 2581 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2582 { | |
| 2583 fprintf (dump_file, " Updated statement:"); | |
| 2584 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); | |
| 2585 } | |
| 2586 | |
| 2587 /* If we replaced a variable index with a constant, then | |
| 2588 we would need to update the invariant flag for ADDR_EXPRs. */ | |
| 2589 if (gimple_assign_single_p (use_stmt) | |
| 2590 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR) | |
| 2591 recompute_tree_invariant_for_addr_expr | |
| 2592 (gimple_assign_rhs1 (use_stmt)); | |
| 2593 | |
| 2594 /* If we cleaned up EH information from the statement, | |
| 2595 mark its containing block as needing EH cleanups. */ | |
| 2596 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt)) | |
| 2597 { | |
| 2598 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index); | |
| 2599 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2600 fprintf (dump_file, " Flagged to clear EH edges.\n"); | |
| 2601 } | |
| 2602 | |
| 2603 /* Propagation may expose new trivial copy/constant propagation | |
| 2604 opportunities. */ | |
| 2605 if (gimple_assign_single_p (use_stmt) | |
| 2606 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME | |
| 2607 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME | |
| 2608 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt)))) | |
| 2609 { | |
| 2610 tree result = get_lhs_or_phi_result (use_stmt); | |
| 2611 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); | |
| 2612 } | |
| 2613 | |
| 2614 /* Propagation into these nodes may make certain edges in | |
| 2615 the CFG unexecutable. We want to identify them as PHI nodes | |
| 2616 at the destination of those unexecutable edges may become | |
| 2617 degenerates. */ | |
| 2618 else if (gimple_code (use_stmt) == GIMPLE_COND | |
| 2619 || gimple_code (use_stmt) == GIMPLE_SWITCH | |
| 2620 || gimple_code (use_stmt) == GIMPLE_GOTO) | |
| 2621 { | |
| 2622 tree val; | |
| 2623 | |
| 2624 if (gimple_code (use_stmt) == GIMPLE_COND) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2625 val = fold_binary_loc (gimple_location (use_stmt), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2626 gimple_cond_code (use_stmt), |
| 0 | 2627 boolean_type_node, |
| 2628 gimple_cond_lhs (use_stmt), | |
| 2629 gimple_cond_rhs (use_stmt)); | |
| 2630 else if (gimple_code (use_stmt) == GIMPLE_SWITCH) | |
| 2631 val = gimple_switch_index (use_stmt); | |
| 2632 else | |
| 2633 val = gimple_goto_dest (use_stmt); | |
| 2634 | |
| 2635 if (val && is_gimple_min_invariant (val)) | |
| 2636 { | |
| 2637 basic_block bb = gimple_bb (use_stmt); | |
| 2638 edge te = find_taken_edge (bb, val); | |
| 2639 edge_iterator ei; | |
| 2640 edge e; | |
| 2641 gimple_stmt_iterator gsi, psi; | |
| 2642 | |
| 2643 /* Remove all outgoing edges except TE. */ | |
| 2644 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));) | |
| 2645 { | |
| 2646 if (e != te) | |
| 2647 { | |
| 2648 /* Mark all the PHI nodes at the destination of | |
| 2649 the unexecutable edge as interesting. */ | |
| 2650 for (psi = gsi_start_phis (e->dest); | |
| 2651 !gsi_end_p (psi); | |
| 2652 gsi_next (&psi)) | |
| 2653 { | |
| 2654 gimple phi = gsi_stmt (psi); | |
| 2655 | |
| 2656 tree result = gimple_phi_result (phi); | |
| 2657 int version = SSA_NAME_VERSION (result); | |
| 2658 | |
| 2659 bitmap_set_bit (interesting_names, version); | |
| 2660 } | |
| 2661 | |
| 2662 te->probability += e->probability; | |
| 2663 | |
| 2664 te->count += e->count; | |
| 2665 remove_edge (e); | |
| 2666 cfg_altered = true; | |
| 2667 } | |
| 2668 else | |
| 2669 ei_next (&ei); | |
| 2670 } | |
| 2671 | |
| 2672 gsi = gsi_last_bb (gimple_bb (use_stmt)); | |
| 2673 gsi_remove (&gsi, true); | |
| 2674 | |
| 2675 /* And fixup the flags on the single remaining edge. */ | |
| 2676 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); | |
| 2677 te->flags &= ~EDGE_ABNORMAL; | |
| 2678 te->flags |= EDGE_FALLTHRU; | |
| 2679 if (te->probability > REG_BR_PROB_BASE) | |
| 2680 te->probability = REG_BR_PROB_BASE; | |
| 2681 } | |
| 2682 } | |
| 2683 } | |
| 2684 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2685 /* Ensure there is nothing else to do. */ |
| 0 | 2686 gcc_assert (!all || has_zero_uses (lhs)); |
| 2687 | |
| 2688 /* If we were able to propagate away all uses of LHS, then | |
| 2689 we can remove STMT. */ | |
| 2690 if (all) | |
| 2691 remove_stmt_or_phi (stmt); | |
| 2692 } | |
| 2693 } | |
| 2694 | |
| 2695 /* STMT is either a PHI node (potentially a degenerate PHI node) or | |
| 2696 a statement that is a trivial copy or constant initialization. | |
| 2697 | |
| 2698 Attempt to eliminate T by propagating its RHS into all uses of | |
| 2699 its LHS. This may in turn set new bits in INTERESTING_NAMES | |
| 2700 for nodes we want to revisit later. | |
| 2701 | |
| 2702 All exit paths should clear INTERESTING_NAMES for the result | |
| 2703 of STMT. */ | |
| 2704 | |
| 2705 static void | |
| 2706 eliminate_const_or_copy (gimple stmt, bitmap interesting_names) | |
| 2707 { | |
| 2708 tree lhs = get_lhs_or_phi_result (stmt); | |
| 2709 tree rhs; | |
| 2710 int version = SSA_NAME_VERSION (lhs); | |
| 2711 | |
| 2712 /* If the LHS of this statement or PHI has no uses, then we can | |
| 2713 just eliminate it. This can occur if, for example, the PHI | |
| 2714 was created by block duplication due to threading and its only | |
| 2715 use was in the conditional at the end of the block which was | |
| 2716 deleted. */ | |
| 2717 if (has_zero_uses (lhs)) | |
| 2718 { | |
| 2719 bitmap_clear_bit (interesting_names, version); | |
| 2720 remove_stmt_or_phi (stmt); | |
| 2721 return; | |
| 2722 } | |
| 2723 | |
| 2724 /* Get the RHS of the assignment or PHI node if the PHI is a | |
| 2725 degenerate. */ | |
| 2726 rhs = get_rhs_or_phi_arg (stmt); | |
| 2727 if (!rhs) | |
| 2728 { | |
| 2729 bitmap_clear_bit (interesting_names, version); | |
| 2730 return; | |
| 2731 } | |
| 2732 | |
| 2733 propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names); | |
| 2734 | |
| 2735 /* Note that STMT may well have been deleted by now, so do | |
| 2736 not access it, instead use the saved version # to clear | |
| 2737 T's entry in the worklist. */ | |
| 2738 bitmap_clear_bit (interesting_names, version); | |
| 2739 } | |
| 2740 | |
| 2741 /* The first phase in degenerate PHI elimination. | |
| 2742 | |
| 2743 Eliminate the degenerate PHIs in BB, then recurse on the | |
| 2744 dominator children of BB. */ | |
| 2745 | |
| 2746 static void | |
| 2747 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names) | |
| 2748 { | |
| 2749 gimple_stmt_iterator gsi; | |
| 2750 basic_block son; | |
| 2751 | |
| 2752 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 2753 { | |
| 2754 gimple phi = gsi_stmt (gsi); | |
| 2755 | |
| 2756 eliminate_const_or_copy (phi, interesting_names); | |
| 2757 } | |
| 2758 | |
| 2759 /* Recurse into the dominator children of BB. */ | |
| 2760 for (son = first_dom_son (CDI_DOMINATORS, bb); | |
| 2761 son; | |
| 2762 son = next_dom_son (CDI_DOMINATORS, son)) | |
| 2763 eliminate_degenerate_phis_1 (son, interesting_names); | |
| 2764 } | |
| 2765 | |
| 2766 | |
| 2767 /* A very simple pass to eliminate degenerate PHI nodes from the | |
| 2768 IL. This is meant to be fast enough to be able to be run several | |
| 2769 times in the optimization pipeline. | |
| 2770 | |
| 2771 Certain optimizations, particularly those which duplicate blocks | |
| 2772 or remove edges from the CFG can create or expose PHIs which are | |
| 2773 trivial copies or constant initializations. | |
| 2774 | |
| 2775 While we could pick up these optimizations in DOM or with the | |
| 2776 combination of copy-prop and CCP, those solutions are far too | |
| 2777 heavy-weight for our needs. | |
| 2778 | |
| 2779 This implementation has two phases so that we can efficiently | |
| 2780 eliminate the first order degenerate PHIs and second order | |
| 2781 degenerate PHIs. | |
| 2782 | |
| 2783 The first phase performs a dominator walk to identify and eliminate | |
| 2784 the vast majority of the degenerate PHIs. When a degenerate PHI | |
| 2785 is identified and eliminated any affected statements or PHIs | |
| 2786 are put on a worklist. | |
| 2787 | |
| 2788 The second phase eliminates degenerate PHIs and trivial copies | |
| 2789 or constant initializations using the worklist. This is how we | |
| 2790 pick up the secondary optimization opportunities with minimal | |
| 2791 cost. */ | |
| 2792 | |
| 2793 static unsigned int | |
| 2794 eliminate_degenerate_phis (void) | |
| 2795 { | |
| 2796 bitmap interesting_names; | |
| 2797 bitmap interesting_names1; | |
| 2798 | |
| 2799 /* Bitmap of blocks which need EH information updated. We can not | |
| 2800 update it on-the-fly as doing so invalidates the dominator tree. */ | |
| 2801 need_eh_cleanup = BITMAP_ALLOC (NULL); | |
| 2802 | |
| 2803 /* INTERESTING_NAMES is effectively our worklist, indexed by | |
| 2804 SSA_NAME_VERSION. | |
| 2805 | |
| 2806 A set bit indicates that the statement or PHI node which | |
| 2807 defines the SSA_NAME should be (re)examined to determine if | |
| 2808 it has become a degenerate PHI or trivial const/copy propagation | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2809 opportunity. |
| 0 | 2810 |
| 2811 Experiments have show we generally get better compilation | |
| 2812 time behavior with bitmaps rather than sbitmaps. */ | |
| 2813 interesting_names = BITMAP_ALLOC (NULL); | |
| 2814 interesting_names1 = BITMAP_ALLOC (NULL); | |
| 2815 | |
| 2816 calculate_dominance_info (CDI_DOMINATORS); | |
| 2817 cfg_altered = false; | |
| 2818 | |
| 2819 /* First phase. Eliminate degenerate PHIs via a dominator | |
| 2820 walk of the CFG. | |
| 2821 | |
| 2822 Experiments have indicated that we generally get better | |
| 2823 compile-time behavior by visiting blocks in the first | |
| 2824 phase in dominator order. Presumably this is because walking | |
| 2825 in dominator order leaves fewer PHIs for later examination | |
| 2826 by the worklist phase. */ | |
| 2827 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names); | |
| 2828 | |
| 2829 /* Second phase. Eliminate second order degenerate PHIs as well | |
| 2830 as trivial copies or constant initializations identified by | |
| 2831 the first phase or this phase. Basically we keep iterating | |
| 2832 until our set of INTERESTING_NAMEs is empty. */ | |
| 2833 while (!bitmap_empty_p (interesting_names)) | |
| 2834 { | |
| 2835 unsigned int i; | |
| 2836 bitmap_iterator bi; | |
| 2837 | |
| 2838 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap | |
| 2839 changed during the loop. Copy it to another bitmap and | |
| 2840 use that. */ | |
| 2841 bitmap_copy (interesting_names1, interesting_names); | |
| 2842 | |
| 2843 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi) | |
| 2844 { | |
| 2845 tree name = ssa_name (i); | |
| 2846 | |
| 2847 /* Ignore SSA_NAMEs that have been released because | |
| 2848 their defining statement was deleted (unreachable). */ | |
| 2849 if (name) | |
| 2850 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)), | |
| 2851 interesting_names); | |
| 2852 } | |
| 2853 } | |
| 2854 | |
| 2855 if (cfg_altered) | |
| 2856 free_dominance_info (CDI_DOMINATORS); | |
| 2857 | |
| 2858 /* Propagation of const and copies may make some EH edges dead. Purge | |
| 2859 such edges from the CFG as needed. */ | |
| 2860 if (!bitmap_empty_p (need_eh_cleanup)) | |
| 2861 { | |
| 2862 gimple_purge_all_dead_eh_edges (need_eh_cleanup); | |
| 2863 BITMAP_FREE (need_eh_cleanup); | |
| 2864 } | |
| 2865 | |
| 2866 BITMAP_FREE (interesting_names); | |
| 2867 BITMAP_FREE (interesting_names1); | |
| 2868 return 0; | |
| 2869 } | |
| 2870 | |
| 2871 struct gimple_opt_pass pass_phi_only_cprop = | |
| 2872 { | |
| 2873 { | |
| 2874 GIMPLE_PASS, | |
| 2875 "phicprop", /* name */ | |
| 2876 gate_dominator, /* gate */ | |
| 2877 eliminate_degenerate_phis, /* execute */ | |
| 2878 NULL, /* sub */ | |
| 2879 NULL, /* next */ | |
| 2880 0, /* static_pass_number */ | |
| 2881 TV_TREE_PHI_CPROP, /* tv_id */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2882 PROP_cfg | PROP_ssa, /* properties_required */ |
| 0 | 2883 0, /* properties_provided */ |
| 2884 0, /* properties_destroyed */ | |
| 2885 0, /* todo_flags_start */ | |
| 2886 TODO_cleanup_cfg | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2887 | TODO_dump_func |
| 0 | 2888 | TODO_ggc_collect |
| 2889 | TODO_verify_ssa | |
| 2890 | TODO_verify_stmts | |
| 2891 | TODO_update_ssa /* todo_flags_finish */ | |
| 2892 } | |
| 2893 }; |