Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-dom.c @ 127:4c56639505ff
fix function.c and add CbC-example Makefile
| author | mir3636 |
|---|---|
| date | Wed, 11 Apr 2018 18:46:58 +0900 |
| parents | 04ced10e8804 |
| children | 84e7813d76e9 |
| rev | line source |
|---|---|
| 0 | 1 /* SSA Dominator optimizations for trees |
| 111 | 2 Copyright (C) 2001-2017 Free Software Foundation, Inc. |
| 0 | 3 Contributed by Diego Novillo <dnovillo@redhat.com> |
| 4 | |
| 5 This file is part of GCC. | |
| 6 | |
| 7 GCC is free software; you can redistribute it and/or modify | |
| 8 it under the terms of the GNU General Public License as published by | |
| 9 the Free Software Foundation; either version 3, or (at your option) | |
| 10 any later version. | |
| 11 | |
| 12 GCC is distributed in the hope that it will be useful, | |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 15 GNU General Public License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along with GCC; see the file COPYING3. If not see | |
| 19 <http://www.gnu.org/licenses/>. */ | |
| 20 | |
| 21 #include "config.h" | |
| 22 #include "system.h" | |
| 23 #include "coretypes.h" | |
| 111 | 24 #include "backend.h" |
| 0 | 25 #include "tree.h" |
| 111 | 26 #include "gimple.h" |
| 27 #include "tree-pass.h" | |
| 28 #include "ssa.h" | |
| 29 #include "gimple-pretty-print.h" | |
| 30 #include "fold-const.h" | |
| 31 #include "cfganal.h" | |
| 0 | 32 #include "cfgloop.h" |
| 111 | 33 #include "gimple-fold.h" |
| 34 #include "tree-eh.h" | |
| 35 #include "tree-inline.h" | |
| 36 #include "gimple-iterator.h" | |
| 37 #include "tree-cfg.h" | |
| 38 #include "tree-into-ssa.h" | |
| 0 | 39 #include "domwalk.h" |
| 40 #include "tree-ssa-propagate.h" | |
| 111 | 41 #include "tree-ssa-threadupdate.h" |
| 0 | 42 #include "params.h" |
| 111 | 43 #include "tree-ssa-scopedtables.h" |
| 44 #include "tree-ssa-threadedge.h" | |
| 45 #include "tree-ssa-dom.h" | |
| 46 #include "gimplify.h" | |
| 47 #include "tree-cfgcleanup.h" | |
| 48 #include "dbgcnt.h" | |
| 0 | 49 |
| 50 /* This file implements optimizations on the dominator tree. */ | |
| 51 | |
| 111 | 52 /* Structure for recording edge equivalences. |
| 0 | 53 |
| 54 Computing and storing the edge equivalences instead of creating | |
| 55 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
|
56 for pathological cases involving switch statements. |
| 0 | 57 |
| 58 These structures live for a single iteration of the dominator | |
| 59 optimizer in the edge's AUX field. At the end of an iteration we | |
| 111 | 60 free each of these structures. */ |
| 61 class edge_info | |
| 62 { | |
| 63 public: | |
| 64 typedef std::pair <tree, tree> equiv_pair; | |
| 65 edge_info (edge); | |
| 66 ~edge_info (); | |
| 0 | 67 |
| 111 | 68 /* Record a simple LHS = RHS equivalence. This may trigger |
| 69 calls to derive_equivalences. */ | |
| 70 void record_simple_equiv (tree, tree); | |
| 71 | |
| 72 /* If traversing this edge creates simple equivalences, we store | |
| 73 them as LHS/RHS pairs within this vector. */ | |
| 74 vec<equiv_pair> simple_equivalences; | |
| 0 | 75 |
| 76 /* Traversing an edge may also indicate one or more particular conditions | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
77 are true or false. */ |
| 111 | 78 vec<cond_equivalence> cond_equivalences; |
| 0 | 79 |
| 111 | 80 private: |
| 81 /* Derive equivalences by walking the use-def chains. */ | |
| 82 void derive_equivalences (tree, tree, int); | |
| 0 | 83 }; |
| 84 | |
| 85 /* Track whether or not we have changed the control flow graph. */ | |
| 86 static bool cfg_altered; | |
| 87 | |
| 88 /* Bitmap of blocks that have had EH statements cleaned. We should | |
| 89 remove their dead edges eventually. */ | |
| 90 static bitmap need_eh_cleanup; | |
| 111 | 91 static vec<gimple *> need_noreturn_fixup; |
| 0 | 92 |
| 93 /* Statistics for dominator optimizations. */ | |
| 94 struct opt_stats_d | |
| 95 { | |
| 96 long num_stmts; | |
| 97 long num_exprs_considered; | |
| 98 long num_re; | |
| 99 long num_const_prop; | |
| 100 long num_copy_prop; | |
| 101 }; | |
| 102 | |
| 103 static struct opt_stats_d opt_stats; | |
| 104 | |
| 105 /* Local functions. */ | |
| 111 | 106 static void record_equality (tree, tree, class const_and_copies *); |
| 0 | 107 static void record_equivalences_from_phis (basic_block); |
| 111 | 108 static void record_equivalences_from_incoming_edge (basic_block, |
| 109 class const_and_copies *, | |
| 110 class avail_exprs_stack *); | |
| 111 static void eliminate_redundant_computations (gimple_stmt_iterator *, | |
| 112 class const_and_copies *, | |
| 113 class avail_exprs_stack *); | |
| 114 static void record_equivalences_from_stmt (gimple *, int, | |
| 115 class avail_exprs_stack *); | |
| 0 | 116 static edge single_incoming_edge_ignoring_loop_edges (basic_block); |
| 111 | 117 static void dump_dominator_optimization_stats (FILE *file, |
| 118 hash_table<expr_elt_hasher> *); | |
| 0 | 119 |
| 111 | 120 /* Constructor for EDGE_INFO. An EDGE_INFO instance is always |
| 121 associated with an edge E. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
122 |
| 111 | 123 edge_info::edge_info (edge e) |
| 124 { | |
| 125 /* Free the old one associated with E, if it exists and | |
| 126 associate our new object with E. */ | |
| 127 free_dom_edge_info (e); | |
| 128 e->aux = this; | |
| 0 | 129 |
| 111 | 130 /* And initialize the embedded vectors. */ |
| 131 simple_equivalences = vNULL; | |
| 132 cond_equivalences = vNULL; | |
| 133 } | |
| 0 | 134 |
| 111 | 135 /* Destructor just needs to release the vectors. */ |
| 0 | 136 |
| 111 | 137 edge_info::~edge_info (void) |
| 138 { | |
| 139 this->cond_equivalences.release (); | |
| 140 this->simple_equivalences.release (); | |
| 0 | 141 } |
| 142 | |
| 111 | 143 /* NAME is known to have the value VALUE, which must be a constant. |
| 0 | 144 |
| 111 | 145 Walk through its use-def chain to see if there are other equivalences |
| 146 we might be able to derive. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
147 |
| 111 | 148 RECURSION_LIMIT controls how far back we recurse through the use-def |
| 149 chains. */ | |
| 0 | 150 |
| 111 | 151 void |
| 152 edge_info::derive_equivalences (tree name, tree value, int recursion_limit) | |
| 0 | 153 { |
| 111 | 154 if (TREE_CODE (name) != SSA_NAME || TREE_CODE (value) != INTEGER_CST) |
| 155 return; | |
| 0 | 156 |
| 111 | 157 /* This records the equivalence for the toplevel object. Do |
| 158 this before checking the recursion limit. */ | |
| 159 simple_equivalences.safe_push (equiv_pair (name, value)); | |
| 0 | 160 |
| 111 | 161 /* Limit how far up the use-def chains we are willing to walk. */ |
| 162 if (recursion_limit == 0) | |
| 163 return; | |
| 0 | 164 |
| 111 | 165 /* We can walk up the use-def chains to potentially find more |
| 166 equivalences. */ | |
| 167 gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
| 168 if (is_gimple_assign (def_stmt)) | |
| 0 | 169 { |
| 111 | 170 /* We know the result of DEF_STMT was zero. See if that allows |
| 171 us to deduce anything about the SSA_NAMEs used on the RHS. */ | |
| 172 enum tree_code code = gimple_assign_rhs_code (def_stmt); | |
| 173 switch (code) | |
| 174 { | |
| 175 case BIT_IOR_EXPR: | |
| 176 if (integer_zerop (value)) | |
| 177 { | |
| 178 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
| 179 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
| 0 | 180 |
| 111 | 181 value = build_zero_cst (TREE_TYPE (rhs1)); |
| 182 derive_equivalences (rhs1, value, recursion_limit - 1); | |
| 183 value = build_zero_cst (TREE_TYPE (rhs2)); | |
| 184 derive_equivalences (rhs2, value, recursion_limit - 1); | |
| 185 } | |
| 186 break; | |
| 0 | 187 |
| 111 | 188 /* We know the result of DEF_STMT was one. See if that allows |
| 189 us to deduce anything about the SSA_NAMEs used on the RHS. */ | |
| 190 case BIT_AND_EXPR: | |
| 191 if (!integer_zerop (value)) | |
| 192 { | |
| 193 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
| 194 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
| 0 | 195 |
| 111 | 196 /* If either operand has a boolean range, then we |
| 197 know its value must be one, otherwise we just know it | |
| 198 is nonzero. The former is clearly useful, I haven't | |
| 199 seen cases where the latter is helpful yet. */ | |
| 200 if (TREE_CODE (rhs1) == SSA_NAME) | |
| 201 { | |
| 202 if (ssa_name_has_boolean_range (rhs1)) | |
| 203 { | |
| 204 value = build_one_cst (TREE_TYPE (rhs1)); | |
| 205 derive_equivalences (rhs1, value, recursion_limit - 1); | |
| 206 } | |
| 207 } | |
| 208 if (TREE_CODE (rhs2) == SSA_NAME) | |
| 209 { | |
| 210 if (ssa_name_has_boolean_range (rhs2)) | |
| 211 { | |
| 212 value = build_one_cst (TREE_TYPE (rhs2)); | |
| 213 derive_equivalences (rhs2, value, recursion_limit - 1); | |
| 214 } | |
| 215 } | |
| 216 } | |
| 217 break; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
218 |
| 111 | 219 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was |
| 220 set via a widening type conversion, then we may be able to record | |
| 221 additional equivalences. */ | |
| 222 case NOP_EXPR: | |
| 223 case CONVERT_EXPR: | |
| 224 { | |
| 225 tree rhs = gimple_assign_rhs1 (def_stmt); | |
| 226 tree rhs_type = TREE_TYPE (rhs); | |
| 227 if (INTEGRAL_TYPE_P (rhs_type) | |
| 228 && (TYPE_PRECISION (TREE_TYPE (name)) | |
| 229 >= TYPE_PRECISION (rhs_type)) | |
| 230 && int_fits_type_p (value, rhs_type)) | |
| 231 derive_equivalences (rhs, | |
| 232 fold_convert (rhs_type, value), | |
| 233 recursion_limit - 1); | |
| 234 break; | |
| 235 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
236 |
| 111 | 237 /* We can invert the operation of these codes trivially if |
| 238 one of the RHS operands is a constant to produce a known | |
| 239 value for the other RHS operand. */ | |
| 240 case POINTER_PLUS_EXPR: | |
| 241 case PLUS_EXPR: | |
| 242 { | |
| 243 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
| 244 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
| 245 | |
| 246 /* If either argument is a constant, then we can compute | |
| 247 a constant value for the nonconstant argument. */ | |
| 248 if (TREE_CODE (rhs1) == INTEGER_CST | |
| 249 && TREE_CODE (rhs2) == SSA_NAME) | |
| 250 derive_equivalences (rhs2, | |
| 251 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1), | |
| 252 value, rhs1), | |
| 253 recursion_limit - 1); | |
| 254 else if (TREE_CODE (rhs2) == INTEGER_CST | |
| 255 && TREE_CODE (rhs1) == SSA_NAME) | |
| 256 derive_equivalences (rhs1, | |
| 257 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1), | |
| 258 value, rhs2), | |
| 259 recursion_limit - 1); | |
| 260 break; | |
| 261 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
262 |
| 111 | 263 /* If one of the operands is a constant, then we can compute |
| 264 the value of the other operand. If both operands are | |
| 265 SSA_NAMEs, then they must be equal if the result is zero. */ | |
| 266 case MINUS_EXPR: | |
| 267 { | |
| 268 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
| 269 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
270 |
| 111 | 271 /* If either argument is a constant, then we can compute |
| 272 a constant value for the nonconstant argument. */ | |
| 273 if (TREE_CODE (rhs1) == INTEGER_CST | |
| 274 && TREE_CODE (rhs2) == SSA_NAME) | |
| 275 derive_equivalences (rhs2, | |
| 276 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1), | |
| 277 rhs1, value), | |
| 278 recursion_limit - 1); | |
| 279 else if (TREE_CODE (rhs2) == INTEGER_CST | |
| 280 && TREE_CODE (rhs1) == SSA_NAME) | |
| 281 derive_equivalences (rhs1, | |
| 282 fold_binary (PLUS_EXPR, TREE_TYPE (rhs1), | |
| 283 value, rhs2), | |
| 284 recursion_limit - 1); | |
| 285 else if (integer_zerop (value)) | |
| 286 { | |
| 287 tree cond = build2 (EQ_EXPR, boolean_type_node, | |
| 288 gimple_assign_rhs1 (def_stmt), | |
| 289 gimple_assign_rhs2 (def_stmt)); | |
| 290 tree inverted = invert_truthvalue (cond); | |
| 291 record_conditions (&this->cond_equivalences, cond, inverted); | |
| 292 } | |
| 293 break; | |
| 294 } | |
| 0 | 295 |
| 111 | 296 |
| 297 case EQ_EXPR: | |
| 298 case NE_EXPR: | |
| 299 { | |
| 300 if ((code == EQ_EXPR && integer_onep (value)) | |
| 301 || (code == NE_EXPR && integer_zerop (value))) | |
| 302 { | |
| 303 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
| 304 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
| 305 | |
| 306 /* If either argument is a constant, then record the | |
| 307 other argument as being the same as that constant. | |
| 0 | 308 |
| 111 | 309 If neither operand is a constant, then we have a |
| 310 conditional name == name equivalence. */ | |
| 311 if (TREE_CODE (rhs1) == INTEGER_CST) | |
| 312 derive_equivalences (rhs2, rhs1, recursion_limit - 1); | |
| 313 else if (TREE_CODE (rhs2) == INTEGER_CST) | |
| 314 derive_equivalences (rhs1, rhs2, recursion_limit - 1); | |
| 315 } | |
| 316 else | |
| 317 { | |
| 318 tree cond = build2 (code, boolean_type_node, | |
| 319 gimple_assign_rhs1 (def_stmt), | |
| 320 gimple_assign_rhs2 (def_stmt)); | |
| 321 tree inverted = invert_truthvalue (cond); | |
| 322 if (integer_zerop (value)) | |
| 323 std::swap (cond, inverted); | |
| 324 record_conditions (&this->cond_equivalences, cond, inverted); | |
| 325 } | |
| 326 break; | |
| 327 } | |
| 0 | 328 |
| 111 | 329 /* For BIT_NOT and NEGATE, we can just apply the operation to the |
| 330 VALUE to get the new equivalence. It will always be a constant | |
| 331 so we can recurse. */ | |
| 332 case BIT_NOT_EXPR: | |
| 333 case NEGATE_EXPR: | |
| 334 { | |
| 335 tree rhs = gimple_assign_rhs1 (def_stmt); | |
| 336 tree res = fold_build1 (code, TREE_TYPE (rhs), value); | |
| 337 derive_equivalences (rhs, res, recursion_limit - 1); | |
| 338 break; | |
| 339 } | |
| 0 | 340 |
| 111 | 341 default: |
| 342 { | |
| 343 if (TREE_CODE_CLASS (code) == tcc_comparison) | |
| 344 { | |
| 345 tree cond = build2 (code, boolean_type_node, | |
| 346 gimple_assign_rhs1 (def_stmt), | |
| 347 gimple_assign_rhs2 (def_stmt)); | |
| 348 tree inverted = invert_truthvalue (cond); | |
| 349 if (integer_zerop (value)) | |
| 350 std::swap (cond, inverted); | |
| 351 record_conditions (&this->cond_equivalences, cond, inverted); | |
| 352 break; | |
| 353 } | |
| 354 break; | |
| 355 } | |
| 356 } | |
| 0 | 357 } |
| 358 } | |
| 359 | |
| 111 | 360 void |
| 361 edge_info::record_simple_equiv (tree lhs, tree rhs) | |
| 0 | 362 { |
| 111 | 363 /* If the RHS is a constant, then we may be able to derive |
| 364 further equivalences. Else just record the name = name | |
| 365 equivalence. */ | |
| 366 if (TREE_CODE (rhs) == INTEGER_CST) | |
| 367 derive_equivalences (lhs, rhs, 4); | |
| 368 else | |
| 369 simple_equivalences.safe_push (equiv_pair (lhs, rhs)); | |
| 0 | 370 } |
| 371 | |
| 111 | 372 /* Free the edge_info data attached to E, if it exists. */ |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
373 |
| 111 | 374 void |
| 375 free_dom_edge_info (edge e) | |
| 376 { | |
| 377 class edge_info *edge_info = (struct edge_info *)e->aux; | |
| 0 | 378 |
| 111 | 379 if (edge_info) |
| 380 delete edge_info; | |
| 0 | 381 } |
| 382 | |
| 383 /* Free all EDGE_INFO structures associated with edges in the CFG. | |
| 384 If a particular edge can be threaded, copy the redirection | |
| 385 target from the EDGE_INFO structure into the edge's AUX field | |
| 386 as required by code to update the CFG and SSA graph for | |
| 387 jump threading. */ | |
| 388 | |
| 389 static void | |
| 390 free_all_edge_infos (void) | |
| 391 { | |
| 392 basic_block bb; | |
| 393 edge_iterator ei; | |
| 394 edge e; | |
| 395 | |
| 111 | 396 FOR_EACH_BB_FN (bb, cfun) |
| 0 | 397 { |
| 398 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 399 { | |
| 111 | 400 free_dom_edge_info (e); |
| 401 e->aux = NULL; | |
| 0 | 402 } |
| 403 } | |
| 404 } | |
| 405 | |
| 111 | 406 /* We have finished optimizing BB, record any information implied by |
| 407 taking a specific outgoing edge from BB. */ | |
| 408 | |
| 409 static void | |
| 410 record_edge_info (basic_block bb) | |
| 411 { | |
| 412 gimple_stmt_iterator gsi = gsi_last_bb (bb); | |
| 413 class edge_info *edge_info; | |
| 414 | |
| 415 if (! gsi_end_p (gsi)) | |
| 416 { | |
| 417 gimple *stmt = gsi_stmt (gsi); | |
| 418 location_t loc = gimple_location (stmt); | |
| 419 | |
| 420 if (gimple_code (stmt) == GIMPLE_SWITCH) | |
| 421 { | |
| 422 gswitch *switch_stmt = as_a <gswitch *> (stmt); | |
| 423 tree index = gimple_switch_index (switch_stmt); | |
| 424 | |
| 425 if (TREE_CODE (index) == SSA_NAME) | |
| 426 { | |
| 427 int i; | |
| 428 int n_labels = gimple_switch_num_labels (switch_stmt); | |
| 429 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun)); | |
| 430 edge e; | |
| 431 edge_iterator ei; | |
| 432 | |
| 433 for (i = 0; i < n_labels; i++) | |
| 434 { | |
| 435 tree label = gimple_switch_label (switch_stmt, i); | |
| 436 basic_block target_bb = label_to_block (CASE_LABEL (label)); | |
| 437 if (CASE_HIGH (label) | |
| 438 || !CASE_LOW (label) | |
| 439 || info[target_bb->index]) | |
| 440 info[target_bb->index] = error_mark_node; | |
| 441 else | |
| 442 info[target_bb->index] = label; | |
| 443 } | |
| 444 | |
| 445 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 446 { | |
| 447 basic_block target_bb = e->dest; | |
| 448 tree label = info[target_bb->index]; | |
| 449 | |
| 450 if (label != NULL && label != error_mark_node) | |
| 451 { | |
| 452 tree x = fold_convert_loc (loc, TREE_TYPE (index), | |
| 453 CASE_LOW (label)); | |
| 454 edge_info = new class edge_info (e); | |
| 455 edge_info->record_simple_equiv (index, x); | |
| 456 } | |
| 457 } | |
| 458 free (info); | |
| 459 } | |
| 460 } | |
| 461 | |
| 462 /* A COND_EXPR may create equivalences too. */ | |
| 463 if (gimple_code (stmt) == GIMPLE_COND) | |
| 464 { | |
| 465 edge true_edge; | |
| 466 edge false_edge; | |
| 467 | |
| 468 tree op0 = gimple_cond_lhs (stmt); | |
| 469 tree op1 = gimple_cond_rhs (stmt); | |
| 470 enum tree_code code = gimple_cond_code (stmt); | |
| 471 | |
| 472 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
| 473 | |
| 474 /* Special case comparing booleans against a constant as we | |
| 475 know the value of OP0 on both arms of the branch. i.e., we | |
| 476 can record an equivalence for OP0 rather than COND. | |
| 477 | |
| 478 However, don't do this if the constant isn't zero or one. | |
| 479 Such conditionals will get optimized more thoroughly during | |
| 480 the domwalk. */ | |
| 481 if ((code == EQ_EXPR || code == NE_EXPR) | |
| 482 && TREE_CODE (op0) == SSA_NAME | |
| 483 && ssa_name_has_boolean_range (op0) | |
| 484 && is_gimple_min_invariant (op1) | |
| 485 && (integer_zerop (op1) || integer_onep (op1))) | |
| 486 { | |
| 487 tree true_val = constant_boolean_node (true, TREE_TYPE (op0)); | |
| 488 tree false_val = constant_boolean_node (false, TREE_TYPE (op0)); | |
| 489 | |
| 490 if (code == EQ_EXPR) | |
| 491 { | |
| 492 edge_info = new class edge_info (true_edge); | |
| 493 edge_info->record_simple_equiv (op0, | |
| 494 (integer_zerop (op1) | |
| 495 ? false_val : true_val)); | |
| 496 edge_info = new class edge_info (false_edge); | |
| 497 edge_info->record_simple_equiv (op0, | |
| 498 (integer_zerop (op1) | |
| 499 ? true_val : false_val)); | |
| 500 } | |
| 501 else | |
| 502 { | |
| 503 edge_info = new class edge_info (true_edge); | |
| 504 edge_info->record_simple_equiv (op0, | |
| 505 (integer_zerop (op1) | |
| 506 ? true_val : false_val)); | |
| 507 edge_info = new class edge_info (false_edge); | |
| 508 edge_info->record_simple_equiv (op0, | |
| 509 (integer_zerop (op1) | |
| 510 ? false_val : true_val)); | |
| 511 } | |
| 512 } | |
| 513 /* This can show up in the IL as a result of copy propagation | |
| 514 it will eventually be canonicalized, but we have to cope | |
| 515 with this case within the pass. */ | |
| 516 else if (is_gimple_min_invariant (op0) | |
| 517 && TREE_CODE (op1) == SSA_NAME) | |
| 518 { | |
| 519 tree cond = build2 (code, boolean_type_node, op0, op1); | |
| 520 tree inverted = invert_truthvalue_loc (loc, cond); | |
| 521 bool can_infer_simple_equiv | |
| 522 = !(HONOR_SIGNED_ZEROS (op0) | |
| 523 && real_zerop (op0)); | |
| 524 struct edge_info *edge_info; | |
| 525 | |
| 526 edge_info = new class edge_info (true_edge); | |
| 527 record_conditions (&edge_info->cond_equivalences, cond, inverted); | |
| 528 | |
| 529 if (can_infer_simple_equiv && code == EQ_EXPR) | |
| 530 edge_info->record_simple_equiv (op1, op0); | |
| 531 | |
| 532 edge_info = new class edge_info (false_edge); | |
| 533 record_conditions (&edge_info->cond_equivalences, inverted, cond); | |
| 534 | |
| 535 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) | |
| 536 edge_info->record_simple_equiv (op1, op0); | |
| 537 } | |
| 538 | |
| 539 else if (TREE_CODE (op0) == SSA_NAME | |
| 540 && (TREE_CODE (op1) == SSA_NAME | |
| 541 || is_gimple_min_invariant (op1))) | |
| 542 { | |
| 543 tree cond = build2 (code, boolean_type_node, op0, op1); | |
| 544 tree inverted = invert_truthvalue_loc (loc, cond); | |
| 545 bool can_infer_simple_equiv | |
| 546 = !(HONOR_SIGNED_ZEROS (op1) | |
| 547 && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1))); | |
| 548 struct edge_info *edge_info; | |
| 549 | |
| 550 edge_info = new class edge_info (true_edge); | |
| 551 record_conditions (&edge_info->cond_equivalences, cond, inverted); | |
| 552 | |
| 553 if (can_infer_simple_equiv && code == EQ_EXPR) | |
| 554 edge_info->record_simple_equiv (op0, op1); | |
| 555 | |
| 556 edge_info = new class edge_info (false_edge); | |
| 557 record_conditions (&edge_info->cond_equivalences, inverted, cond); | |
| 558 | |
| 559 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) | |
| 560 edge_info->record_simple_equiv (op0, op1); | |
| 561 } | |
| 562 } | |
| 563 } | |
| 564 } | |
| 565 | |
| 566 | |
| 567 class dom_opt_dom_walker : public dom_walker | |
| 568 { | |
| 569 public: | |
| 570 dom_opt_dom_walker (cdi_direction direction, | |
| 571 class const_and_copies *const_and_copies, | |
| 572 class avail_exprs_stack *avail_exprs_stack, | |
| 573 gcond *dummy_cond) | |
| 574 : dom_walker (direction, true), | |
| 575 m_const_and_copies (const_and_copies), | |
| 576 m_avail_exprs_stack (avail_exprs_stack), | |
| 577 m_dummy_cond (dummy_cond) { } | |
| 578 | |
| 579 virtual edge before_dom_children (basic_block); | |
| 580 virtual void after_dom_children (basic_block); | |
| 581 | |
| 582 private: | |
| 583 | |
| 584 /* Unwindable equivalences, both const/copy and expression varieties. */ | |
| 585 class const_and_copies *m_const_and_copies; | |
| 586 class avail_exprs_stack *m_avail_exprs_stack; | |
| 587 | |
| 588 /* Dummy condition to avoid creating lots of throw away statements. */ | |
| 589 gcond *m_dummy_cond; | |
| 590 | |
| 591 /* Optimize a single statement within a basic block using the | |
| 592 various tables mantained by DOM. Returns the taken edge if | |
| 593 the statement is a conditional with a statically determined | |
| 594 value. */ | |
| 595 edge optimize_stmt (basic_block, gimple_stmt_iterator); | |
| 596 }; | |
| 597 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
598 /* Jump threading, redundancy elimination and const/copy propagation. |
| 0 | 599 |
| 600 This pass may expose new symbols that need to be renamed into SSA. For | |
| 601 every new symbol exposed, its corresponding bit will be set in | |
| 602 VARS_TO_RENAME. */ | |
| 603 | |
| 111 | 604 namespace { |
| 605 | |
| 606 const pass_data pass_data_dominator = | |
| 607 { | |
| 608 GIMPLE_PASS, /* type */ | |
| 609 "dom", /* name */ | |
| 610 OPTGROUP_NONE, /* optinfo_flags */ | |
| 611 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */ | |
| 612 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
| 613 0, /* properties_provided */ | |
| 614 0, /* properties_destroyed */ | |
| 615 0, /* todo_flags_start */ | |
| 616 ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */ | |
| 617 }; | |
| 618 | |
| 619 class pass_dominator : public gimple_opt_pass | |
| 0 | 620 { |
| 111 | 621 public: |
| 622 pass_dominator (gcc::context *ctxt) | |
| 623 : gimple_opt_pass (pass_data_dominator, ctxt), | |
| 624 may_peel_loop_headers_p (false) | |
| 625 {} | |
| 0 | 626 |
| 111 | 627 /* opt_pass methods: */ |
| 628 opt_pass * clone () { return new pass_dominator (m_ctxt); } | |
| 629 void set_pass_param (unsigned int n, bool param) | |
| 630 { | |
| 631 gcc_assert (n == 0); | |
| 632 may_peel_loop_headers_p = param; | |
| 633 } | |
| 634 virtual bool gate (function *) { return flag_tree_dom != 0; } | |
| 635 virtual unsigned int execute (function *); | |
| 636 | |
| 637 private: | |
| 638 /* This flag is used to prevent loops from being peeled repeatedly in jump | |
| 639 threading; it will be removed once we preserve loop structures throughout | |
| 640 the compilation -- we will be able to mark the affected loops directly in | |
| 641 jump threading, and avoid peeling them next time. */ | |
| 642 bool may_peel_loop_headers_p; | |
| 643 }; // class pass_dominator | |
| 644 | |
| 645 unsigned int | |
| 646 pass_dominator::execute (function *fun) | |
| 647 { | |
| 0 | 648 memset (&opt_stats, 0, sizeof (opt_stats)); |
| 649 | |
| 650 /* Create our hash tables. */ | |
| 111 | 651 hash_table<expr_elt_hasher> *avail_exprs |
| 652 = new hash_table<expr_elt_hasher> (1024); | |
| 653 class avail_exprs_stack *avail_exprs_stack | |
| 654 = new class avail_exprs_stack (avail_exprs); | |
| 655 class const_and_copies *const_and_copies = new class const_and_copies (); | |
| 0 | 656 need_eh_cleanup = BITMAP_ALLOC (NULL); |
| 111 | 657 need_noreturn_fixup.create (0); |
| 0 | 658 |
| 659 calculate_dominance_info (CDI_DOMINATORS); | |
| 660 cfg_altered = false; | |
| 661 | |
| 662 /* We need to know loop structures in order to avoid destroying them | |
| 663 in jump threading. Note that we still can e.g. thread through loop | |
| 664 headers to an exit edge, or through loop header to the loop body, assuming | |
| 111 | 665 that we update the loop info. |
| 666 | |
| 667 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due | |
| 668 to several overly conservative bail-outs in jump threading, case | |
| 669 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is | |
| 670 missing. We should improve jump threading in future then | |
| 671 LOOPS_HAVE_PREHEADERS won't be needed here. */ | |
| 672 loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES); | |
| 0 | 673 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
674 /* 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
|
675 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
|
676 |
| 0 | 677 /* We need accurate information regarding back edges in the CFG |
| 678 for jump threading; this may include back edges that are not part of | |
| 679 a single loop. */ | |
| 680 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
|
681 |
| 111 | 682 /* We want to create the edge info structures before the dominator walk |
| 683 so that they'll be in place for the jump threader, particularly when | |
| 684 threading through a join block. | |
| 685 | |
| 686 The conditions will be lazily updated with global equivalences as | |
| 687 we reach them during the dominator walk. */ | |
| 688 basic_block bb; | |
| 689 FOR_EACH_BB_FN (bb, fun) | |
| 690 record_edge_info (bb); | |
| 691 | |
| 692 gcond *dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node, | |
| 693 integer_zero_node, NULL, NULL); | |
| 694 | |
| 0 | 695 /* Recursively walk the dominator tree optimizing statements. */ |
| 111 | 696 dom_opt_dom_walker walker (CDI_DOMINATORS, const_and_copies, |
| 697 avail_exprs_stack, dummy_cond); | |
| 698 walker.walk (fun->cfg->x_entry_block_ptr); | |
| 699 | |
| 700 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing | |
| 701 edge. When found, remove jump threads which contain any outgoing | |
| 702 edge from the affected block. */ | |
| 703 if (cfg_altered) | |
| 704 { | |
| 705 FOR_EACH_BB_FN (bb, fun) | |
| 706 { | |
| 707 edge_iterator ei; | |
| 708 edge e; | |
| 709 | |
| 710 /* First see if there are any edges without EDGE_EXECUTABLE | |
| 711 set. */ | |
| 712 bool found = false; | |
| 713 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 714 { | |
| 715 if ((e->flags & EDGE_EXECUTABLE) == 0) | |
| 716 { | |
| 717 found = true; | |
| 718 break; | |
| 719 } | |
| 720 } | |
| 721 | |
| 722 /* If there were any such edges found, then remove jump threads | |
| 723 containing any edge leaving BB. */ | |
| 724 if (found) | |
| 725 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 726 remove_jump_threads_including (e); | |
| 727 } | |
| 728 } | |
| 0 | 729 |
| 730 { | |
| 731 gimple_stmt_iterator gsi; | |
| 732 basic_block bb; | |
| 111 | 733 FOR_EACH_BB_FN (bb, fun) |
| 734 { | |
| 735 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 0 | 736 update_stmt_if_modified (gsi_stmt (gsi)); |
| 737 } | |
| 738 } | |
| 739 | |
| 740 /* If we exposed any new variables, go ahead and put them into | |
| 741 SSA form now, before we handle jump threading. This simplifies | |
| 742 interactions between rewriting of _DECL nodes into SSA form | |
| 743 and rewriting SSA_NAME nodes into SSA form after block | |
| 744 duplication and CFG manipulation. */ | |
| 745 update_ssa (TODO_update_ssa); | |
| 746 | |
| 747 free_all_edge_infos (); | |
| 748 | |
| 749 /* Thread jumps, creating duplicate blocks as needed. */ | |
| 111 | 750 cfg_altered |= thread_through_all_blocks (may_peel_loop_headers_p); |
| 0 | 751 |
| 752 if (cfg_altered) | |
| 753 free_dominance_info (CDI_DOMINATORS); | |
| 754 | |
| 755 /* Removal of statements may make some EH edges dead. Purge | |
| 756 such edges from the CFG as needed. */ | |
| 757 if (!bitmap_empty_p (need_eh_cleanup)) | |
| 758 { | |
| 759 unsigned i; | |
| 760 bitmap_iterator bi; | |
| 761 | |
| 762 /* Jump threading may have created forwarder blocks from blocks | |
| 763 needing EH cleanup; the new successor of these blocks, which | |
| 111 | 764 has inherited from the original block, needs the cleanup. |
| 765 Don't clear bits in the bitmap, as that can break the bitmap | |
| 766 iterator. */ | |
| 0 | 767 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi) |
| 768 { | |
| 111 | 769 basic_block bb = BASIC_BLOCK_FOR_FN (fun, i); |
| 770 if (bb == NULL) | |
| 771 continue; | |
| 772 while (single_succ_p (bb) | |
| 773 && (single_succ_edge (bb)->flags & EDGE_EH) == 0) | |
| 774 bb = single_succ (bb); | |
| 775 if (bb == EXIT_BLOCK_PTR_FOR_FN (fun)) | |
| 776 continue; | |
| 777 if ((unsigned) bb->index != i) | |
| 778 bitmap_set_bit (need_eh_cleanup, bb->index); | |
| 0 | 779 } |
| 780 | |
| 781 gimple_purge_all_dead_eh_edges (need_eh_cleanup); | |
| 111 | 782 bitmap_clear (need_eh_cleanup); |
| 0 | 783 } |
| 784 | |
| 111 | 785 /* Fixup stmts that became noreturn calls. This may require splitting |
| 786 blocks and thus isn't possible during the dominator walk or before | |
| 787 jump threading finished. Do this in reverse order so we don't | |
| 788 inadvertedly remove a stmt we want to fixup by visiting a dominating | |
| 789 now noreturn call first. */ | |
| 790 while (!need_noreturn_fixup.is_empty ()) | |
| 791 { | |
| 792 gimple *stmt = need_noreturn_fixup.pop (); | |
| 793 if (dump_file && dump_flags & TDF_DETAILS) | |
| 794 { | |
| 795 fprintf (dump_file, "Fixing up noreturn call "); | |
| 796 print_gimple_stmt (dump_file, stmt, 0); | |
| 797 fprintf (dump_file, "\n"); | |
| 798 } | |
| 799 fixup_noreturn_call (stmt); | |
| 800 } | |
| 801 | |
| 802 statistics_counter_event (fun, "Redundant expressions eliminated", | |
| 0 | 803 opt_stats.num_re); |
| 111 | 804 statistics_counter_event (fun, "Constants propagated", |
| 0 | 805 opt_stats.num_const_prop); |
| 111 | 806 statistics_counter_event (fun, "Copies propagated", |
| 0 | 807 opt_stats.num_copy_prop); |
| 808 | |
| 809 /* Debugging dumps. */ | |
| 810 if (dump_file && (dump_flags & TDF_STATS)) | |
| 111 | 811 dump_dominator_optimization_stats (dump_file, avail_exprs); |
| 0 | 812 |
| 813 loop_optimizer_finalize (); | |
| 814 | |
| 815 /* Delete our main hashtable. */ | |
| 111 | 816 delete avail_exprs; |
| 817 avail_exprs = NULL; | |
| 0 | 818 |
| 819 /* Free asserted bitmaps and stacks. */ | |
| 820 BITMAP_FREE (need_eh_cleanup); | |
| 111 | 821 need_noreturn_fixup.release (); |
| 822 delete avail_exprs_stack; | |
| 823 delete const_and_copies; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
824 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
825 /* 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
|
826 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
|
827 |
| 0 | 828 return 0; |
| 829 } | |
| 830 | |
| 111 | 831 } // anon namespace |
| 832 | |
| 833 gimple_opt_pass * | |
| 834 make_pass_dominator (gcc::context *ctxt) | |
| 0 | 835 { |
| 111 | 836 return new pass_dominator (ctxt); |
| 0 | 837 } |
| 838 | |
| 839 | |
| 840 /* A trivial wrapper so that we can present the generic jump | |
| 841 threading code with a simple API for simplifying statements. */ | |
| 842 static tree | |
| 111 | 843 simplify_stmt_for_jump_threading (gimple *stmt, |
| 844 gimple *within_stmt ATTRIBUTE_UNUSED, | |
| 845 class avail_exprs_stack *avail_exprs_stack, | |
| 846 basic_block bb ATTRIBUTE_UNUSED) | |
| 0 | 847 { |
| 111 | 848 return avail_exprs_stack->lookup_avail_expr (stmt, false, true); |
| 849 } | |
| 850 | |
| 851 /* Valueize hook for gimple_fold_stmt_to_constant_1. */ | |
| 852 | |
| 853 static tree | |
| 854 dom_valueize (tree t) | |
| 855 { | |
| 856 if (TREE_CODE (t) == SSA_NAME) | |
| 857 { | |
| 858 tree tem = SSA_NAME_VALUE (t); | |
| 859 if (tem) | |
| 860 return tem; | |
| 861 } | |
| 862 return t; | |
| 0 | 863 } |
| 864 | |
| 111 | 865 /* We have just found an equivalence for LHS on an edge E. |
| 866 Look backwards to other uses of LHS and see if we can derive | |
| 867 additional equivalences that are valid on edge E. */ | |
| 0 | 868 static void |
| 111 | 869 back_propagate_equivalences (tree lhs, edge e, |
| 870 class const_and_copies *const_and_copies) | |
| 0 | 871 { |
| 111 | 872 use_operand_p use_p; |
| 873 imm_use_iterator iter; | |
| 874 bitmap domby = NULL; | |
| 875 basic_block dest = e->dest; | |
| 876 | |
| 877 /* Iterate over the uses of LHS to see if any dominate E->dest. | |
| 878 If so, they may create useful equivalences too. | |
| 879 | |
| 880 ??? If the code gets re-organized to a worklist to catch more | |
| 881 indirect opportunities and it is made to handle PHIs then this | |
| 882 should only consider use_stmts in basic-blocks we have already visited. */ | |
| 883 FOR_EACH_IMM_USE_FAST (use_p, iter, lhs) | |
| 884 { | |
| 885 gimple *use_stmt = USE_STMT (use_p); | |
| 886 | |
| 887 /* Often the use is in DEST, which we trivially know we can't use. | |
| 888 This is cheaper than the dominator set tests below. */ | |
| 889 if (dest == gimple_bb (use_stmt)) | |
| 890 continue; | |
| 891 | |
| 892 /* Filter out statements that can never produce a useful | |
| 893 equivalence. */ | |
| 894 tree lhs2 = gimple_get_lhs (use_stmt); | |
| 895 if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME) | |
| 896 continue; | |
| 897 | |
| 898 /* Profiling has shown the domination tests here can be fairly | |
| 899 expensive. We get significant improvements by building the | |
| 900 set of blocks that dominate BB. We can then just test | |
| 901 for set membership below. | |
| 902 | |
| 903 We also initialize the set lazily since often the only uses | |
| 904 are going to be in the same block as DEST. */ | |
| 905 if (!domby) | |
| 906 { | |
| 907 domby = BITMAP_ALLOC (NULL); | |
| 908 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, dest); | |
| 909 while (bb) | |
| 910 { | |
| 911 bitmap_set_bit (domby, bb->index); | |
| 912 bb = get_immediate_dominator (CDI_DOMINATORS, bb); | |
| 913 } | |
| 914 } | |
| 915 | |
| 916 /* This tests if USE_STMT does not dominate DEST. */ | |
| 917 if (!bitmap_bit_p (domby, gimple_bb (use_stmt)->index)) | |
| 918 continue; | |
| 919 | |
| 920 /* At this point USE_STMT dominates DEST and may result in a | |
| 921 useful equivalence. Try to simplify its RHS to a constant | |
| 922 or SSA_NAME. */ | |
| 923 tree res = gimple_fold_stmt_to_constant_1 (use_stmt, dom_valueize, | |
| 924 no_follow_ssa_edges); | |
| 925 if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res))) | |
| 926 record_equality (lhs2, res, const_and_copies); | |
| 927 } | |
| 928 | |
| 929 if (domby) | |
| 930 BITMAP_FREE (domby); | |
| 931 } | |
| 0 | 932 |
| 111 | 933 /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied |
| 934 by traversing edge E (which are cached in E->aux). | |
| 935 | |
| 936 Callers are responsible for managing the unwinding markers. */ | |
| 937 void | |
| 938 record_temporary_equivalences (edge e, | |
| 939 class const_and_copies *const_and_copies, | |
| 940 class avail_exprs_stack *avail_exprs_stack) | |
| 941 { | |
| 942 int i; | |
| 943 class edge_info *edge_info = (class edge_info *) e->aux; | |
| 944 | |
| 945 /* If we have info associated with this edge, record it into | |
| 946 our equivalence tables. */ | |
| 947 if (edge_info) | |
| 948 { | |
| 949 cond_equivalence *eq; | |
| 950 /* If we have 0 = COND or 1 = COND equivalences, record them | |
| 951 into our expression hash tables. */ | |
| 952 for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i) | |
| 953 avail_exprs_stack->record_cond (eq); | |
| 954 | |
| 955 edge_info::equiv_pair *seq; | |
| 956 for (i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i) | |
| 957 { | |
| 958 tree lhs = seq->first; | |
| 959 if (!lhs || TREE_CODE (lhs) != SSA_NAME) | |
| 960 continue; | |
| 961 | |
| 962 /* Record the simple NAME = VALUE equivalence. */ | |
| 963 tree rhs = seq->second; | |
| 964 | |
| 965 /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is | |
| 966 cheaper to compute than the other, then set up the equivalence | |
| 967 such that we replace the expensive one with the cheap one. | |
| 968 | |
| 969 If they are the same cost to compute, then do not record | |
| 970 anything. */ | |
| 971 if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME) | |
| 972 { | |
| 973 gimple *rhs_def = SSA_NAME_DEF_STMT (rhs); | |
| 974 int rhs_cost = estimate_num_insns (rhs_def, &eni_size_weights); | |
| 975 | |
| 976 gimple *lhs_def = SSA_NAME_DEF_STMT (lhs); | |
| 977 int lhs_cost = estimate_num_insns (lhs_def, &eni_size_weights); | |
| 978 | |
| 979 if (rhs_cost > lhs_cost) | |
| 980 record_equality (rhs, lhs, const_and_copies); | |
| 981 else if (rhs_cost < lhs_cost) | |
| 982 record_equality (lhs, rhs, const_and_copies); | |
| 983 } | |
| 984 else | |
| 985 record_equality (lhs, rhs, const_and_copies); | |
| 986 | |
| 987 | |
| 988 /* Any equivalence found for LHS may result in additional | |
| 989 equivalences for other uses of LHS that we have already | |
| 990 processed. */ | |
| 991 back_propagate_equivalences (lhs, e, const_and_copies); | |
| 992 } | |
| 993 } | |
| 0 | 994 } |
| 995 | |
| 996 /* PHI nodes can create equivalences too. | |
| 997 | |
| 998 Ignoring any alternatives which are the same as the result, if | |
| 999 all the alternatives are equal, then the PHI node creates an | |
| 1000 equivalence. */ | |
| 1001 | |
| 1002 static void | |
| 1003 record_equivalences_from_phis (basic_block bb) | |
| 1004 { | |
| 111 | 1005 gphi_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
|
1006 |
| 0 | 1007 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
| 1008 { | |
| 111 | 1009 gphi *phi = gsi.phi (); |
| 0 | 1010 |
| 1011 tree lhs = gimple_phi_result (phi); | |
| 1012 tree rhs = NULL; | |
| 1013 size_t i; | |
| 1014 | |
| 1015 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
| 1016 { | |
| 1017 tree t = gimple_phi_arg_def (phi, i); | |
| 1018 | |
| 1019 /* Ignore alternatives which are the same as our LHS. Since | |
| 1020 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we | |
| 1021 can simply compare pointers. */ | |
| 1022 if (lhs == t) | |
| 1023 continue; | |
| 1024 | |
| 111 | 1025 /* If the associated edge is not marked as executable, then it |
| 1026 can be ignored. */ | |
| 1027 if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0) | |
| 1028 continue; | |
| 1029 | |
| 1030 t = dom_valueize (t); | |
| 1031 | |
| 0 | 1032 /* If we have not processed an alternative yet, then set |
| 1033 RHS to this alternative. */ | |
| 1034 if (rhs == NULL) | |
| 1035 rhs = t; | |
| 1036 /* If we have processed an alternative (stored in RHS), then | |
| 1037 see if it is equal to this one. If it isn't, then stop | |
| 1038 the search. */ | |
| 1039 else if (! operand_equal_for_phi_arg_p (rhs, t)) | |
| 1040 break; | |
| 1041 } | |
| 1042 | |
| 1043 /* If we had no interesting alternatives, then all the RHS alternatives | |
| 1044 must have been the same as LHS. */ | |
| 1045 if (!rhs) | |
| 1046 rhs = lhs; | |
| 1047 | |
| 1048 /* If we managed to iterate through each PHI alternative without | |
| 1049 breaking out of the loop, then we have a PHI which may create | |
| 1050 a useful equivalence. We do not need to record unwind data for | |
| 1051 this, since this is a true assignment and not an equivalence | |
| 1052 inferred from a comparison. All uses of this ssa name are dominated | |
| 1053 by this assignment, so unwinding just costs time and space. */ | |
| 111 | 1054 if (i == gimple_phi_num_args (phi) |
| 1055 && 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
|
1056 set_ssa_name_value (lhs, rhs); |
| 0 | 1057 } |
| 1058 } | |
| 1059 | |
| 1060 /* Ignoring loop backedges, if BB has precisely one incoming edge then | |
| 1061 return that edge. Otherwise return NULL. */ | |
| 1062 static edge | |
| 1063 single_incoming_edge_ignoring_loop_edges (basic_block bb) | |
| 1064 { | |
| 1065 edge retval = NULL; | |
| 1066 edge e; | |
| 1067 edge_iterator ei; | |
| 1068 | |
| 1069 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 1070 { | |
| 1071 /* A loop back edge can be identified by the destination of | |
| 1072 the edge dominating the source of the edge. */ | |
| 1073 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) | |
| 1074 continue; | |
| 1075 | |
| 111 | 1076 /* We can safely ignore edges that are not executable. */ |
| 1077 if ((e->flags & EDGE_EXECUTABLE) == 0) | |
| 1078 continue; | |
| 1079 | |
| 0 | 1080 /* If we have already seen a non-loop edge, then we must have |
| 1081 multiple incoming non-loop edges and thus we return NULL. */ | |
| 1082 if (retval) | |
| 1083 return NULL; | |
| 1084 | |
| 1085 /* This is the first non-loop incoming edge we have found. Record | |
| 1086 it. */ | |
| 1087 retval = e; | |
| 1088 } | |
| 1089 | |
| 1090 return retval; | |
| 1091 } | |
| 1092 | |
| 111 | 1093 /* Record any equivalences created by the incoming edge to BB into |
| 1094 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one | |
| 1095 incoming edge, then no equivalence is created. */ | |
| 0 | 1096 |
| 1097 static void | |
| 111 | 1098 record_equivalences_from_incoming_edge (basic_block bb, |
| 1099 class const_and_copies *const_and_copies, | |
| 1100 class avail_exprs_stack *avail_exprs_stack) | |
| 0 | 1101 { |
| 1102 edge e; | |
| 1103 basic_block parent; | |
| 1104 | |
| 1105 /* If our parent block ended with a control statement, then we may be | |
| 1106 able to record some equivalences based on which outgoing edge from | |
| 1107 the parent was followed. */ | |
| 1108 parent = get_immediate_dominator (CDI_DOMINATORS, bb); | |
| 1109 | |
| 1110 e = single_incoming_edge_ignoring_loop_edges (bb); | |
| 1111 | |
| 1112 /* If we had a single incoming edge from our parent block, then enter | |
| 1113 any data associated with the edge into our tables. */ | |
| 1114 if (e && e->src == parent) | |
| 111 | 1115 record_temporary_equivalences (e, const_and_copies, avail_exprs_stack); |
| 1116 } | |
| 0 | 1117 |
| 111 | 1118 /* Dump statistics for the hash table HTAB. */ |
| 0 | 1119 |
| 111 | 1120 static void |
| 1121 htab_statistics (FILE *file, const hash_table<expr_elt_hasher> &htab) | |
| 1122 { | |
| 1123 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", | |
| 1124 (long) htab.size (), | |
| 1125 (long) htab.elements (), | |
| 1126 htab.collisions ()); | |
| 0 | 1127 } |
| 1128 | |
| 1129 /* Dump SSA statistics on FILE. */ | |
| 1130 | |
| 111 | 1131 static void |
| 1132 dump_dominator_optimization_stats (FILE *file, | |
| 1133 hash_table<expr_elt_hasher> *avail_exprs) | |
| 0 | 1134 { |
| 1135 fprintf (file, "Total number of statements: %6ld\n\n", | |
| 1136 opt_stats.num_stmts); | |
| 1137 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n", | |
| 1138 opt_stats.num_exprs_considered); | |
| 1139 | |
| 1140 fprintf (file, "\nHash table statistics:\n"); | |
| 1141 | |
| 1142 fprintf (file, " avail_exprs: "); | |
| 111 | 1143 htab_statistics (file, *avail_exprs); |
| 0 | 1144 } |
| 1145 | |
| 1146 | |
| 1147 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR. | |
| 1148 This constrains the cases in which we may treat this as assignment. */ | |
| 1149 | |
| 1150 static void | |
| 111 | 1151 record_equality (tree x, tree y, class const_and_copies *const_and_copies) |
| 0 | 1152 { |
| 1153 tree prev_x = NULL, prev_y = NULL; | |
| 1154 | |
| 111 | 1155 if (tree_swap_operands_p (x, y)) |
| 1156 std::swap (x, y); | |
| 1157 | |
| 1158 /* Most of the time tree_swap_operands_p does what we want. But there | |
| 1159 are cases where we know one operand is better for copy propagation than | |
| 1160 the other. Given no other code cares about ordering of equality | |
| 1161 comparison operators for that purpose, we just handle the special cases | |
| 1162 here. */ | |
| 1163 if (TREE_CODE (x) == SSA_NAME && TREE_CODE (y) == SSA_NAME) | |
| 1164 { | |
| 1165 /* If one operand is a single use operand, then make it | |
| 1166 X. This will preserve its single use properly and if this | |
| 1167 conditional is eliminated, the computation of X can be | |
| 1168 eliminated as well. */ | |
| 1169 if (has_single_use (y) && ! has_single_use (x)) | |
| 1170 std::swap (x, y); | |
| 1171 } | |
| 0 | 1172 if (TREE_CODE (x) == SSA_NAME) |
| 1173 prev_x = SSA_NAME_VALUE (x); | |
| 1174 if (TREE_CODE (y) == SSA_NAME) | |
| 1175 prev_y = SSA_NAME_VALUE (y); | |
| 1176 | |
| 1177 /* If one of the previous values is invariant, or invariant in more loops | |
| 1178 (by depth), then use that. | |
| 1179 Otherwise it doesn't matter which value we choose, just so | |
| 1180 long as we canonicalize on one value. */ | |
| 1181 if (is_gimple_min_invariant (y)) | |
| 1182 ; | |
| 111 | 1183 else if (is_gimple_min_invariant (x)) |
| 0 | 1184 prev_x = x, x = y, y = prev_x, prev_x = prev_y; |
| 1185 else if (prev_x && is_gimple_min_invariant (prev_x)) | |
| 1186 x = y, y = prev_x, prev_x = prev_y; | |
| 1187 else if (prev_y) | |
| 1188 y = prev_y; | |
| 1189 | |
| 1190 /* After the swapping, we must have one SSA_NAME. */ | |
| 1191 if (TREE_CODE (x) != SSA_NAME) | |
| 1192 return; | |
| 1193 | |
| 1194 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a | |
| 1195 variable compared against zero. If we're honoring signed zeros, | |
| 1196 then we cannot record this value unless we know that the value is | |
| 1197 nonzero. */ | |
| 111 | 1198 if (HONOR_SIGNED_ZEROS (x) |
| 0 | 1199 && (TREE_CODE (y) != REAL_CST |
| 111 | 1200 || real_equal (&dconst0, &TREE_REAL_CST (y)))) |
| 0 | 1201 return; |
| 1202 | |
| 111 | 1203 const_and_copies->record_const_or_copy (x, y, prev_x); |
| 0 | 1204 } |
| 1205 | |
| 1206 /* Returns true when STMT is a simple iv increment. It detects the | |
| 1207 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
|
1208 |
| 0 | 1209 i_1 = phi (..., i_2) |
| 1210 i_2 = i_1 +/- ... */ | |
| 1211 | |
| 111 | 1212 bool |
| 1213 simple_iv_increment_p (gimple *stmt) | |
| 0 | 1214 { |
| 111 | 1215 enum tree_code code; |
| 0 | 1216 tree lhs, preinc; |
| 111 | 1217 gimple *phi; |
| 0 | 1218 size_t i; |
| 1219 | |
| 1220 if (gimple_code (stmt) != GIMPLE_ASSIGN) | |
| 1221 return false; | |
| 1222 | |
| 1223 lhs = gimple_assign_lhs (stmt); | |
| 1224 if (TREE_CODE (lhs) != SSA_NAME) | |
| 1225 return false; | |
| 1226 | |
| 111 | 1227 code = gimple_assign_rhs_code (stmt); |
| 1228 if (code != PLUS_EXPR | |
| 1229 && code != MINUS_EXPR | |
| 1230 && code != POINTER_PLUS_EXPR) | |
| 0 | 1231 return false; |
| 1232 | |
| 1233 preinc = gimple_assign_rhs1 (stmt); | |
| 1234 if (TREE_CODE (preinc) != SSA_NAME) | |
| 1235 return false; | |
| 1236 | |
| 1237 phi = SSA_NAME_DEF_STMT (preinc); | |
| 1238 if (gimple_code (phi) != GIMPLE_PHI) | |
| 1239 return false; | |
| 1240 | |
| 1241 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
| 1242 if (gimple_phi_arg_def (phi, i) == lhs) | |
| 1243 return true; | |
| 1244 | |
| 1245 return false; | |
| 1246 } | |
| 1247 | |
| 111 | 1248 /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the |
| 0 | 1249 successors of BB. */ |
| 1250 | |
| 1251 static void | |
| 111 | 1252 cprop_into_successor_phis (basic_block bb, |
| 1253 class const_and_copies *const_and_copies) | |
| 0 | 1254 { |
| 1255 edge e; | |
| 1256 edge_iterator ei; | |
| 1257 | |
| 1258 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 1259 { | |
| 1260 int indx; | |
| 111 | 1261 gphi_iterator gsi; |
| 0 | 1262 |
| 1263 /* If this is an abnormal edge, then we do not want to copy propagate | |
| 1264 into the PHI alternative associated with this edge. */ | |
| 1265 if (e->flags & EDGE_ABNORMAL) | |
| 1266 continue; | |
| 1267 | |
| 1268 gsi = gsi_start_phis (e->dest); | |
| 1269 if (gsi_end_p (gsi)) | |
| 1270 continue; | |
| 1271 | |
| 111 | 1272 /* We may have an equivalence associated with this edge. While |
| 1273 we can not propagate it into non-dominated blocks, we can | |
| 1274 propagate them into PHIs in non-dominated blocks. */ | |
| 1275 | |
| 1276 /* Push the unwind marker so we can reset the const and copies | |
| 1277 table back to its original state after processing this edge. */ | |
| 1278 const_and_copies->push_marker (); | |
| 1279 | |
| 1280 /* Extract and record any simple NAME = VALUE equivalences. | |
| 1281 | |
| 1282 Don't bother with [01] = COND equivalences, they're not useful | |
| 1283 here. */ | |
| 1284 class edge_info *edge_info = (class edge_info *) e->aux; | |
| 1285 | |
| 1286 if (edge_info) | |
| 1287 { | |
| 1288 edge_info::equiv_pair *seq; | |
| 1289 for (int i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i) | |
| 1290 { | |
| 1291 tree lhs = seq->first; | |
| 1292 tree rhs = seq->second; | |
| 1293 | |
| 1294 if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
| 1295 const_and_copies->record_const_or_copy (lhs, rhs); | |
| 1296 } | |
| 1297 | |
| 1298 } | |
| 1299 | |
| 0 | 1300 indx = e->dest_idx; |
| 1301 for ( ; !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 1302 { | |
| 1303 tree new_val; | |
| 1304 use_operand_p orig_p; | |
| 1305 tree orig_val; | |
| 111 | 1306 gphi *phi = gsi.phi (); |
| 0 | 1307 |
| 1308 /* The alternative may be associated with a constant, so verify | |
| 1309 it is an SSA_NAME before doing anything with it. */ | |
| 1310 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx); | |
| 1311 orig_val = get_use_from_ptr (orig_p); | |
| 1312 if (TREE_CODE (orig_val) != SSA_NAME) | |
| 1313 continue; | |
| 1314 | |
| 1315 /* If we have *ORIG_P in our constant/copy table, then replace | |
| 1316 ORIG_P with its value in our constant/copy table. */ | |
| 1317 new_val = SSA_NAME_VALUE (orig_val); | |
| 1318 if (new_val | |
| 1319 && new_val != orig_val | |
| 1320 && may_propagate_copy (orig_val, new_val)) | |
| 1321 propagate_value (orig_p, new_val); | |
| 1322 } | |
| 111 | 1323 |
| 1324 const_and_copies->pop_to_marker (); | |
| 0 | 1325 } |
| 1326 } | |
| 1327 | |
| 111 | 1328 edge |
| 1329 dom_opt_dom_walker::before_dom_children (basic_block bb) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1330 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1331 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
|
1332 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1333 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
|
1334 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
|
1335 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1336 /* 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
|
1337 far to unwind when we finalize this block. */ |
| 111 | 1338 m_avail_exprs_stack->push_marker (); |
| 1339 m_const_and_copies->push_marker (); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1340 |
| 111 | 1341 record_equivalences_from_incoming_edge (bb, m_const_and_copies, |
| 1342 m_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
|
1343 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1344 /* 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
|
1345 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
|
1346 |
| 111 | 1347 /* Create equivalences from redundant PHIs. PHIs are only truly |
| 1348 redundant when they exist in the same block, so push another | |
| 1349 marker and unwind right afterwards. */ | |
| 1350 m_avail_exprs_stack->push_marker (); | |
| 1351 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 1352 eliminate_redundant_computations (&gsi, m_const_and_copies, | |
| 1353 m_avail_exprs_stack); | |
| 1354 m_avail_exprs_stack->pop_to_marker (); | |
| 1355 | |
| 1356 edge taken_edge = NULL; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1357 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
| 111 | 1358 taken_edge = this->optimize_stmt (bb, gsi); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1359 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1360 /* 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
|
1361 record_edge_info (bb); |
| 111 | 1362 cprop_into_successor_phis (bb, m_const_and_copies); |
| 1363 if (taken_edge && !dbg_cnt (dom_unreachable_edges)) | |
| 1364 return NULL; | |
| 1365 | |
| 1366 return taken_edge; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1367 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1368 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1369 /* 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
|
1370 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
|
1371 the dominator tree. */ |
| 0 | 1372 |
| 111 | 1373 void |
| 1374 dom_opt_dom_walker::after_dom_children (basic_block bb) | |
| 0 | 1375 { |
| 111 | 1376 thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies, |
| 1377 m_avail_exprs_stack, | |
| 1378 simplify_stmt_for_jump_threading); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1379 |
| 111 | 1380 /* These remove expressions local to BB from the tables. */ |
| 1381 m_avail_exprs_stack->pop_to_marker (); | |
| 1382 m_const_and_copies->pop_to_marker (); | |
| 0 | 1383 } |
| 1384 | |
| 1385 /* Search for redundant computations in STMT. If any are found, then | |
| 1386 replace them with the variable holding the result of the computation. | |
| 1387 | |
| 111 | 1388 If safe, record this expression into AVAIL_EXPRS_STACK and |
| 1389 CONST_AND_COPIES. */ | |
| 0 | 1390 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1391 static void |
| 111 | 1392 eliminate_redundant_computations (gimple_stmt_iterator* gsi, |
| 1393 class const_and_copies *const_and_copies, | |
| 1394 class avail_exprs_stack *avail_exprs_stack) | |
| 0 | 1395 { |
| 1396 tree expr_type; | |
| 1397 tree cached_lhs; | |
| 111 | 1398 tree def; |
| 0 | 1399 bool insert = true; |
| 1400 bool assigns_var_p = false; | |
| 1401 | |
| 111 | 1402 gimple *stmt = gsi_stmt (*gsi); |
| 0 | 1403 |
| 111 | 1404 if (gimple_code (stmt) == GIMPLE_PHI) |
| 1405 def = gimple_phi_result (stmt); | |
| 1406 else | |
| 1407 def = gimple_get_lhs (stmt); | |
| 0 | 1408 |
| 1409 /* Certain expressions on the RHS can be optimized away, but can not | |
| 1410 themselves be entered into the hash tables. */ | |
| 1411 if (! def | |
| 1412 || TREE_CODE (def) != SSA_NAME | |
| 1413 || 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
|
1414 || gimple_vdef (stmt) |
| 0 | 1415 /* Do not record equivalences for increments of ivs. This would create |
| 1416 overlapping live ranges for a very questionable gain. */ | |
| 1417 || simple_iv_increment_p (stmt)) | |
| 1418 insert = false; | |
| 1419 | |
| 1420 /* Check if the expression has been computed before. */ | |
| 111 | 1421 cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, insert, true); |
| 0 | 1422 |
| 1423 opt_stats.num_exprs_considered++; | |
| 1424 | |
| 1425 /* Get the type of the expression we are trying to optimize. */ | |
| 1426 if (is_gimple_assign (stmt)) | |
| 1427 { | |
| 1428 expr_type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
| 1429 assigns_var_p = true; | |
| 1430 } | |
| 1431 else if (gimple_code (stmt) == GIMPLE_COND) | |
| 1432 expr_type = boolean_type_node; | |
| 1433 else if (is_gimple_call (stmt)) | |
| 1434 { | |
| 1435 gcc_assert (gimple_call_lhs (stmt)); | |
| 1436 expr_type = TREE_TYPE (gimple_call_lhs (stmt)); | |
| 1437 assigns_var_p = true; | |
| 1438 } | |
| 111 | 1439 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) |
| 1440 expr_type = TREE_TYPE (gimple_switch_index (swtch_stmt)); | |
| 1441 else if (gimple_code (stmt) == GIMPLE_PHI) | |
| 1442 /* We can't propagate into a phi, so the logic below doesn't apply. | |
| 1443 Instead record an equivalence between the cached LHS and the | |
| 1444 PHI result of this statement, provided they are in the same block. | |
| 1445 This should be sufficient to kill the redundant phi. */ | |
| 1446 { | |
| 1447 if (def && cached_lhs) | |
| 1448 const_and_copies->record_const_or_copy (def, cached_lhs); | |
| 1449 return; | |
| 1450 } | |
| 0 | 1451 else |
| 1452 gcc_unreachable (); | |
| 1453 | |
| 1454 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
|
1455 return; |
| 0 | 1456 |
| 1457 /* It is safe to ignore types here since we have already done | |
| 1458 type checking in the hashing and equality routines. In fact | |
| 1459 type checking here merely gets in the way of constant | |
| 1460 propagation. Also, make sure that it is safe to propagate | |
| 1461 CACHED_LHS into the expression in STMT. */ | |
| 1462 if ((TREE_CODE (cached_lhs) != SSA_NAME | |
| 1463 && (assigns_var_p | |
| 1464 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))) | |
| 1465 || may_propagate_copy_into_stmt (stmt, cached_lhs)) | |
| 1466 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1467 gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1468 || is_gimple_min_invariant (cached_lhs)); |
| 0 | 1469 |
| 1470 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1471 { | |
| 1472 fprintf (dump_file, " Replaced redundant expr '"); | |
| 1473 print_gimple_expr (dump_file, stmt, 0, dump_flags); | |
| 1474 fprintf (dump_file, "' with '"); | |
| 1475 print_generic_expr (dump_file, cached_lhs, dump_flags); | |
| 1476 fprintf (dump_file, "'\n"); | |
| 1477 } | |
| 1478 | |
| 1479 opt_stats.num_re++; | |
| 1480 | |
| 1481 if (assigns_var_p | |
| 1482 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))) | |
| 1483 cached_lhs = fold_convert (expr_type, cached_lhs); | |
| 1484 | |
| 1485 propagate_tree_value_into_stmt (gsi, cached_lhs); | |
| 1486 | |
| 1487 /* Since it is always necessary to mark the result as modified, | |
| 1488 perhaps we should move this into propagate_tree_value_into_stmt | |
| 1489 itself. */ | |
| 1490 gimple_set_modified (gsi_stmt (*gsi), true); | |
| 1491 } | |
| 1492 } | |
| 1493 | |
| 1494 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either | |
| 1495 the available expressions table or the const_and_copies table. | |
| 111 | 1496 Detect and record those equivalences into AVAIL_EXPRS_STACK. |
| 1497 | |
| 1498 We handle only very simple copy equivalences here. The heavy | |
| 0 | 1499 lifing is done by eliminate_redundant_computations. */ |
| 1500 | |
| 1501 static void | |
| 111 | 1502 record_equivalences_from_stmt (gimple *stmt, int may_optimize_p, |
| 1503 class avail_exprs_stack *avail_exprs_stack) | |
| 0 | 1504 { |
| 1505 tree lhs; | |
| 1506 enum tree_code lhs_code; | |
| 1507 | |
| 1508 gcc_assert (is_gimple_assign (stmt)); | |
| 1509 | |
| 1510 lhs = gimple_assign_lhs (stmt); | |
| 1511 lhs_code = TREE_CODE (lhs); | |
| 1512 | |
| 1513 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
|
1514 && gimple_assign_single_p (stmt)) |
| 0 | 1515 { |
| 1516 tree rhs = gimple_assign_rhs1 (stmt); | |
| 1517 | |
| 1518 /* If the RHS of the assignment is a constant or another variable that | |
| 1519 may be propagated, register it in the CONST_AND_COPIES table. We | |
| 1520 do not need to record unwind data for this, since this is a true | |
| 1521 assignment and not an equivalence inferred from a comparison. All | |
| 1522 uses of this ssa name are dominated by this assignment, so unwinding | |
| 1523 just costs time and space. */ | |
| 1524 if (may_optimize_p | |
| 1525 && (TREE_CODE (rhs) == SSA_NAME | |
| 1526 || is_gimple_min_invariant (rhs))) | |
| 111 | 1527 { |
| 1528 rhs = dom_valueize (rhs); | |
| 1529 | |
| 1530 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1531 { | |
| 1532 fprintf (dump_file, "==== ASGN "); | |
| 1533 print_generic_expr (dump_file, lhs); | |
| 1534 fprintf (dump_file, " = "); | |
| 1535 print_generic_expr (dump_file, rhs); | |
| 1536 fprintf (dump_file, "\n"); | |
| 1537 } | |
| 1538 | |
| 1539 set_ssa_name_value (lhs, rhs); | |
| 1540 } | |
| 1541 } | |
| 0 | 1542 |
| 111 | 1543 /* Make sure we can propagate &x + CST. */ |
| 1544 if (lhs_code == SSA_NAME | |
| 1545 && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR | |
| 1546 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR | |
| 1547 && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST) | |
| 1548 { | |
| 1549 tree op0 = gimple_assign_rhs1 (stmt); | |
| 1550 tree op1 = gimple_assign_rhs2 (stmt); | |
| 1551 tree new_rhs | |
| 1552 = build_fold_addr_expr (fold_build2 (MEM_REF, | |
| 1553 TREE_TYPE (TREE_TYPE (op0)), | |
| 1554 unshare_expr (op0), | |
| 1555 fold_convert (ptr_type_node, | |
| 1556 op1))); | |
| 1557 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1558 { | |
| 1559 fprintf (dump_file, "==== ASGN "); | |
| 1560 print_generic_expr (dump_file, lhs); | |
| 1561 fprintf (dump_file, " = "); | |
| 1562 print_generic_expr (dump_file, new_rhs); | |
| 1563 fprintf (dump_file, "\n"); | |
| 1564 } | |
| 1565 | |
| 1566 set_ssa_name_value (lhs, new_rhs); | |
| 0 | 1567 } |
| 1568 | |
| 1569 /* A memory store, even an aliased store, creates a useful | |
| 1570 equivalence. By exchanging the LHS and RHS, creating suitable | |
| 1571 vops and recording the result in the available expression table, | |
| 1572 we may be able to expose more redundant loads. */ | |
| 1573 if (!gimple_has_volatile_ops (stmt) | |
| 1574 && gimple_references_memory_p (stmt) | |
| 1575 && gimple_assign_single_p (stmt) | |
| 1576 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
| 1577 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) | |
| 1578 && !is_gimple_reg (lhs)) | |
| 1579 { | |
| 1580 tree rhs = gimple_assign_rhs1 (stmt); | |
| 111 | 1581 gassign *new_stmt; |
| 0 | 1582 |
| 1583 /* Build a new statement with the RHS and LHS exchanged. */ | |
| 1584 if (TREE_CODE (rhs) == SSA_NAME) | |
| 1585 { | |
| 1586 /* NOTE tuples. The call to gimple_build_assign below replaced | |
| 1587 a call to build_gimple_modify_stmt, which did not set the | |
| 1588 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so | |
| 1589 may cause an SSA validation failure, as the LHS may be a | |
| 1590 default-initialized name and should have no definition. I'm | |
| 1591 a bit dubious of this, as the artificial statement that we | |
| 1592 generate here may in fact be ill-formed, but it is simply | |
| 1593 used as an internal device in this pass, and never becomes | |
| 1594 part of the CFG. */ | |
| 111 | 1595 gimple *defstmt = SSA_NAME_DEF_STMT (rhs); |
| 0 | 1596 new_stmt = gimple_build_assign (rhs, lhs); |
| 1597 SSA_NAME_DEF_STMT (rhs) = defstmt; | |
| 1598 } | |
| 1599 else | |
| 1600 new_stmt = gimple_build_assign (rhs, lhs); | |
| 1601 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1602 gimple_set_vuse (new_stmt, gimple_vdef (stmt)); |
| 0 | 1603 |
| 1604 /* Finally enter the statement into the available expression | |
| 1605 table. */ | |
| 111 | 1606 avail_exprs_stack->lookup_avail_expr (new_stmt, true, true); |
| 0 | 1607 } |
| 1608 } | |
| 1609 | |
| 1610 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from | |
| 1611 CONST_AND_COPIES. */ | |
| 1612 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1613 static void |
| 111 | 1614 cprop_operand (gimple *stmt, use_operand_p op_p) |
| 0 | 1615 { |
| 1616 tree val; | |
| 1617 tree op = USE_FROM_PTR (op_p); | |
| 1618 | |
| 1619 /* If the operand has a known constant value or it is known to be a | |
| 1620 copy of some other variable, use the value or copy stored in | |
| 1621 CONST_AND_COPIES. */ | |
| 1622 val = SSA_NAME_VALUE (op); | |
| 1623 if (val && val != op) | |
| 1624 { | |
| 1625 /* Do not replace hard register operands in asm statements. */ | |
| 1626 if (gimple_code (stmt) == GIMPLE_ASM | |
| 1627 && !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
|
1628 return; |
| 0 | 1629 |
| 1630 /* Certain operands are not allowed to be copy propagated due | |
| 1631 to their interaction with exception handling and some GCC | |
| 1632 extensions. */ | |
| 1633 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
|
1634 return; |
| 0 | 1635 |
| 111 | 1636 /* Do not propagate copies into BIVs. |
| 1637 See PR23821 and PR62217 for how this can disturb IV and | |
| 1638 number of iteration analysis. */ | |
| 1639 if (TREE_CODE (val) != INTEGER_CST) | |
| 1640 { | |
| 1641 gimple *def = SSA_NAME_DEF_STMT (op); | |
| 1642 if (gimple_code (def) == GIMPLE_PHI | |
| 1643 && gimple_bb (def)->loop_father->header == gimple_bb (def)) | |
| 1644 return; | |
| 1645 } | |
| 0 | 1646 |
| 1647 /* Dump details. */ | |
| 1648 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1649 { | |
| 1650 fprintf (dump_file, " Replaced '"); | |
| 1651 print_generic_expr (dump_file, op, dump_flags); | |
| 1652 fprintf (dump_file, "' with %s '", | |
| 1653 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable")); | |
| 1654 print_generic_expr (dump_file, val, dump_flags); | |
| 1655 fprintf (dump_file, "'\n"); | |
| 1656 } | |
| 1657 | |
| 1658 if (TREE_CODE (val) != SSA_NAME) | |
| 1659 opt_stats.num_const_prop++; | |
| 1660 else | |
| 1661 opt_stats.num_copy_prop++; | |
| 1662 | |
| 1663 propagate_value (op_p, val); | |
| 1664 | |
| 1665 /* And note that we modified this statement. This is now | |
| 1666 safe, even if we changed virtual operands since we will | |
| 1667 rescan the statement and rewrite its operands again. */ | |
| 1668 gimple_set_modified (stmt, true); | |
| 1669 } | |
| 1670 } | |
| 1671 | |
| 1672 /* 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
|
1673 known value for that SSA_NAME (or NULL if no value is known). |
| 0 | 1674 |
| 1675 Propagate values from CONST_AND_COPIES into the uses, vuses and | |
| 1676 vdef_ops of STMT. */ | |
| 1677 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1678 static void |
| 111 | 1679 cprop_into_stmt (gimple *stmt) |
| 0 | 1680 { |
| 1681 use_operand_p op_p; | |
| 1682 ssa_op_iter iter; | |
| 111 | 1683 tree last_copy_propagated_op = NULL; |
| 0 | 1684 |
| 111 | 1685 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE) |
| 0 | 1686 { |
| 111 | 1687 tree old_op = USE_FROM_PTR (op_p); |
| 1688 | |
| 1689 /* If we have A = B and B = A in the copy propagation tables | |
| 1690 (due to an equality comparison), avoid substituting B for A | |
| 1691 then A for B in the trivially discovered cases. This allows | |
| 1692 optimization of statements were A and B appear as input | |
| 1693 operands. */ | |
| 1694 if (old_op != last_copy_propagated_op) | |
| 1695 { | |
| 1696 cprop_operand (stmt, op_p); | |
| 1697 | |
| 1698 tree new_op = USE_FROM_PTR (op_p); | |
| 1699 if (new_op != old_op && TREE_CODE (new_op) == SSA_NAME) | |
| 1700 last_copy_propagated_op = new_op; | |
| 1701 } | |
| 0 | 1702 } |
| 1703 } | |
| 1704 | |
| 111 | 1705 /* If STMT contains a relational test, try to convert it into an |
| 1706 equality test if there is only a single value which can ever | |
| 1707 make the test true. | |
| 1708 | |
| 1709 For example, if the expression hash table contains: | |
| 1710 | |
| 1711 TRUE = (i <= 1) | |
| 1712 | |
| 1713 And we have a test within statement of i >= 1, then we can safely | |
| 1714 rewrite the test as i == 1 since there only a single value where | |
| 1715 the test is true. | |
| 1716 | |
| 1717 This is similar to code in VRP. */ | |
| 1718 | |
| 1719 static void | |
| 1720 test_for_singularity (gimple *stmt, gcond *dummy_cond, | |
| 1721 avail_exprs_stack *avail_exprs_stack) | |
| 1722 { | |
| 1723 /* We want to support gimple conditionals as well as assignments | |
| 1724 where the RHS contains a conditional. */ | |
| 1725 if (is_gimple_assign (stmt) || gimple_code (stmt) == GIMPLE_COND) | |
| 1726 { | |
| 1727 enum tree_code code = ERROR_MARK; | |
| 1728 tree lhs, rhs; | |
| 1729 | |
| 1730 /* Extract the condition of interest from both forms we support. */ | |
| 1731 if (is_gimple_assign (stmt)) | |
| 1732 { | |
| 1733 code = gimple_assign_rhs_code (stmt); | |
| 1734 lhs = gimple_assign_rhs1 (stmt); | |
| 1735 rhs = gimple_assign_rhs2 (stmt); | |
| 1736 } | |
| 1737 else if (gimple_code (stmt) == GIMPLE_COND) | |
| 1738 { | |
| 1739 code = gimple_cond_code (as_a <gcond *> (stmt)); | |
| 1740 lhs = gimple_cond_lhs (as_a <gcond *> (stmt)); | |
| 1741 rhs = gimple_cond_rhs (as_a <gcond *> (stmt)); | |
| 1742 } | |
| 1743 | |
| 1744 /* We're looking for a relational test using LE/GE. Also note we can | |
| 1745 canonicalize LT/GT tests against constants into LE/GT tests. */ | |
| 1746 if (code == LE_EXPR || code == GE_EXPR | |
| 1747 || ((code == LT_EXPR || code == GT_EXPR) | |
| 1748 && TREE_CODE (rhs) == INTEGER_CST)) | |
| 1749 { | |
| 1750 /* For LT_EXPR and GT_EXPR, canonicalize to LE_EXPR and GE_EXPR. */ | |
| 1751 if (code == LT_EXPR) | |
| 1752 rhs = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs), | |
| 1753 rhs, build_int_cst (TREE_TYPE (rhs), 1)); | |
| 1754 | |
| 1755 if (code == GT_EXPR) | |
| 1756 rhs = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs), | |
| 1757 rhs, build_int_cst (TREE_TYPE (rhs), 1)); | |
| 1758 | |
| 1759 /* Determine the code we want to check for in the hash table. */ | |
| 1760 enum tree_code test_code; | |
| 1761 if (code == GE_EXPR || code == GT_EXPR) | |
| 1762 test_code = LE_EXPR; | |
| 1763 else | |
| 1764 test_code = GE_EXPR; | |
| 1765 | |
| 1766 /* Update the dummy statement so we can query the hash tables. */ | |
| 1767 gimple_cond_set_code (dummy_cond, test_code); | |
| 1768 gimple_cond_set_lhs (dummy_cond, lhs); | |
| 1769 gimple_cond_set_rhs (dummy_cond, rhs); | |
| 1770 tree cached_lhs | |
| 1771 = avail_exprs_stack->lookup_avail_expr (dummy_cond, false, false); | |
| 1772 | |
| 1773 /* If the lookup returned 1 (true), then the expression we | |
| 1774 queried was in the hash table. As a result there is only | |
| 1775 one value that makes the original conditional true. Update | |
| 1776 STMT accordingly. */ | |
| 1777 if (cached_lhs && integer_onep (cached_lhs)) | |
| 1778 { | |
| 1779 if (is_gimple_assign (stmt)) | |
| 1780 { | |
| 1781 gimple_assign_set_rhs_code (stmt, EQ_EXPR); | |
| 1782 gimple_assign_set_rhs2 (stmt, rhs); | |
| 1783 gimple_set_modified (stmt, true); | |
| 1784 } | |
| 1785 else | |
| 1786 { | |
| 1787 gimple_set_modified (stmt, true); | |
| 1788 gimple_cond_set_code (as_a <gcond *> (stmt), EQ_EXPR); | |
| 1789 gimple_cond_set_rhs (as_a <gcond *> (stmt), rhs); | |
| 1790 gimple_set_modified (stmt, true); | |
| 1791 } | |
| 1792 } | |
| 1793 } | |
| 1794 } | |
| 1795 } | |
| 1796 | |
| 1797 /* Optimize the statement in block BB 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
|
1798 |
| 0 | 1799 We try to perform some simplistic global redundancy elimination and |
| 1800 constant propagation: | |
| 1801 | |
| 1802 1- To detect global redundancy, we keep track of expressions that have | |
| 1803 been computed in this block and its dominators. If we find that the | |
| 1804 same expression is computed more than once, we eliminate repeated | |
| 1805 computations by using the target of the first one. | |
| 1806 | |
| 1807 2- Constant values and copy assignments. This is used to do very | |
| 1808 simplistic constant and copy propagation. When a constant or copy | |
| 1809 assignment is found, we map the value on the RHS of the assignment to | |
| 111 | 1810 the variable in the LHS in the CONST_AND_COPIES table. |
| 1811 | |
| 1812 3- Very simple redundant store elimination is performed. | |
| 0 | 1813 |
| 111 | 1814 4- We can simpify a condition to a constant or from a relational |
| 1815 condition to an equality condition. */ | |
| 1816 | |
| 1817 edge | |
| 1818 dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator si) | |
| 0 | 1819 { |
| 111 | 1820 gimple *stmt, *old_stmt; |
| 0 | 1821 bool may_optimize_p; |
| 1822 bool modified_p = false; | |
| 111 | 1823 bool was_noreturn; |
| 1824 edge retval = NULL; | |
| 0 | 1825 |
| 1826 old_stmt = stmt = gsi_stmt (si); | |
| 111 | 1827 was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt); |
| 0 | 1828 |
| 1829 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1830 { | |
| 1831 fprintf (dump_file, "Optimizing statement "); | |
| 1832 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 1833 } | |
| 1834 | |
| 111 | 1835 update_stmt_if_modified (stmt); |
| 1836 opt_stats.num_stmts++; | |
| 1837 | |
| 0 | 1838 /* 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
|
1839 cprop_into_stmt (stmt); |
| 0 | 1840 |
| 1841 /* If the statement has been modified with constant replacements, | |
| 1842 fold its RHS before checking for redundant computations. */ | |
| 1843 if (gimple_modified_p (stmt)) | |
| 1844 { | |
| 1845 tree rhs = NULL; | |
| 1846 | |
| 1847 /* Try to fold the statement making sure that STMT is kept | |
| 1848 up to date. */ | |
| 1849 if (fold_stmt (&si)) | |
| 1850 { | |
| 1851 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
|
1852 gimple_set_modified (stmt, true); |
| 0 | 1853 |
| 1854 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1855 { | |
| 1856 fprintf (dump_file, " Folded to: "); | |
| 1857 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 1858 } | |
| 1859 } | |
| 1860 | |
| 1861 /* We only need to consider cases that can yield a gimple operand. */ | |
| 1862 if (gimple_assign_single_p (stmt)) | |
| 1863 rhs = gimple_assign_rhs1 (stmt); | |
| 1864 else if (gimple_code (stmt) == GIMPLE_GOTO) | |
| 1865 rhs = gimple_goto_dest (stmt); | |
| 111 | 1866 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) |
| 0 | 1867 /* This should never be an ADDR_EXPR. */ |
| 111 | 1868 rhs = gimple_switch_index (swtch_stmt); |
| 0 | 1869 |
| 1870 if (rhs && TREE_CODE (rhs) == ADDR_EXPR) | |
| 1871 recompute_tree_invariant_for_addr_expr (rhs); | |
| 1872 | |
| 1873 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called, | |
| 1874 even if fold_stmt updated the stmt already and thus cleared | |
| 1875 gimple_modified_p flag on it. */ | |
| 1876 modified_p = true; | |
| 1877 } | |
| 1878 | |
| 1879 /* Check for redundant computations. Do this optimization only | |
| 1880 for assignments that have no volatile ops and conditionals. */ | |
| 111 | 1881 may_optimize_p = (!gimple_has_side_effects (stmt) |
| 1882 && (is_gimple_assign (stmt) | |
| 0 | 1883 || (is_gimple_call (stmt) |
| 111 | 1884 && gimple_call_lhs (stmt) != NULL_TREE) |
| 0 | 1885 || gimple_code (stmt) == GIMPLE_COND |
| 1886 || gimple_code (stmt) == GIMPLE_SWITCH)); | |
| 1887 | |
| 1888 if (may_optimize_p) | |
| 1889 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1890 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
|
1891 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1892 /* 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
|
1893 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
|
1894 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
|
1895 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
|
1896 if (callee |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1897 && 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
|
1898 && 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
|
1899 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1900 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
|
1901 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
|
1902 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1903 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1904 |
| 111 | 1905 if (gimple_code (stmt) == GIMPLE_COND) |
| 1906 { | |
| 1907 tree lhs = gimple_cond_lhs (stmt); | |
| 1908 tree rhs = gimple_cond_rhs (stmt); | |
| 1909 | |
| 1910 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1], | |
| 1911 then this conditional is computable at compile time. We can just | |
| 1912 shove either 0 or 1 into the LHS, mark the statement as modified | |
| 1913 and all the right things will just happen below. | |
| 1914 | |
| 1915 Note this would apply to any case where LHS has a range | |
| 1916 narrower than its type implies and RHS is outside that | |
| 1917 narrower range. Future work. */ | |
| 1918 if (TREE_CODE (lhs) == SSA_NAME | |
| 1919 && ssa_name_has_boolean_range (lhs) | |
| 1920 && TREE_CODE (rhs) == INTEGER_CST | |
| 1921 && ! (integer_zerop (rhs) || integer_onep (rhs))) | |
| 1922 { | |
| 1923 gimple_cond_set_lhs (as_a <gcond *> (stmt), | |
| 1924 fold_convert (TREE_TYPE (lhs), | |
| 1925 integer_zero_node)); | |
| 1926 gimple_set_modified (stmt, true); | |
| 1927 } | |
| 1928 } | |
| 1929 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1930 update_stmt_if_modified (stmt); |
| 111 | 1931 eliminate_redundant_computations (&si, m_const_and_copies, |
| 1932 m_avail_exprs_stack); | |
| 0 | 1933 stmt = gsi_stmt (si); |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1934 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1935 /* Perform simple redundant store elimination. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1936 if (gimple_assign_single_p (stmt) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1937 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1938 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1939 tree lhs = gimple_assign_lhs (stmt); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1940 tree rhs = gimple_assign_rhs1 (stmt); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1941 tree cached_lhs; |
| 111 | 1942 gassign *new_stmt; |
| 1943 rhs = dom_valueize (rhs); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1944 /* Build a new statement with the RHS and LHS exchanged. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1945 if (TREE_CODE (rhs) == SSA_NAME) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1946 { |
| 111 | 1947 gimple *defstmt = SSA_NAME_DEF_STMT (rhs); |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1948 new_stmt = gimple_build_assign (rhs, lhs); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1949 SSA_NAME_DEF_STMT (rhs) = defstmt; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1950 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1951 else |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1952 new_stmt = gimple_build_assign (rhs, lhs); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1953 gimple_set_vuse (new_stmt, gimple_vuse (stmt)); |
| 111 | 1954 cached_lhs = m_avail_exprs_stack->lookup_avail_expr (new_stmt, false, |
| 1955 false); | |
| 1956 if (cached_lhs && operand_equal_p (rhs, cached_lhs, 0)) | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1957 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1958 basic_block bb = gimple_bb (stmt); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1959 unlink_stmt_vdef (stmt); |
| 111 | 1960 if (gsi_remove (&si, true)) |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1961 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1962 bitmap_set_bit (need_eh_cleanup, bb->index); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1963 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1964 fprintf (dump_file, " Flagged to clear EH edges.\n"); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1965 } |
| 111 | 1966 release_defs (stmt); |
| 1967 return retval; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1968 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1969 } |
| 111 | 1970 |
| 1971 /* If this statement was not redundant, we may still be able to simplify | |
| 1972 it, which may in turn allow other part of DOM or other passes to do | |
| 1973 a better job. */ | |
| 1974 test_for_singularity (stmt, m_dummy_cond, m_avail_exprs_stack); | |
| 0 | 1975 } |
| 1976 | |
| 1977 /* Record any additional equivalences created by this statement. */ | |
| 1978 if (is_gimple_assign (stmt)) | |
| 111 | 1979 record_equivalences_from_stmt (stmt, may_optimize_p, m_avail_exprs_stack); |
| 0 | 1980 |
| 111 | 1981 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may |
| 1982 know where it goes. */ | |
| 0 | 1983 if (gimple_modified_p (stmt) || modified_p) |
| 1984 { | |
| 1985 tree val = NULL; | |
| 1986 | |
| 1987 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
|
1988 val = fold_binary_loc (gimple_location (stmt), |
| 111 | 1989 gimple_cond_code (stmt), boolean_type_node, |
| 1990 gimple_cond_lhs (stmt), | |
| 1991 gimple_cond_rhs (stmt)); | |
| 1992 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) | |
| 1993 val = gimple_switch_index (swtch_stmt); | |
| 0 | 1994 |
| 111 | 1995 if (val && TREE_CODE (val) == INTEGER_CST) |
| 1996 { | |
| 1997 retval = find_taken_edge (bb, val); | |
| 1998 if (retval) | |
| 1999 { | |
| 2000 /* Fix the condition to be either true or false. */ | |
| 2001 if (gimple_code (stmt) == GIMPLE_COND) | |
| 2002 { | |
| 2003 if (integer_zerop (val)) | |
| 2004 gimple_cond_make_false (as_a <gcond *> (stmt)); | |
| 2005 else if (integer_onep (val)) | |
| 2006 gimple_cond_make_true (as_a <gcond *> (stmt)); | |
| 2007 else | |
| 2008 gcc_unreachable (); | |
| 2009 | |
| 2010 gimple_set_modified (stmt, true); | |
| 2011 } | |
| 2012 | |
| 2013 /* Further simplifications may be possible. */ | |
| 2014 cfg_altered = true; | |
| 2015 } | |
| 2016 } | |
| 2017 | |
| 2018 update_stmt_if_modified (stmt); | |
| 0 | 2019 |
| 2020 /* If we simplified a statement in such a way as to be shown that it | |
| 2021 cannot trap, update the eh information and the cfg to match. */ | |
| 2022 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) | |
| 2023 { | |
| 2024 bitmap_set_bit (need_eh_cleanup, bb->index); | |
| 2025 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 2026 fprintf (dump_file, " Flagged to clear EH edges.\n"); | |
| 2027 } | |
| 2028 | |
| 111 | 2029 if (!was_noreturn |
| 2030 && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt)) | |
| 2031 need_noreturn_fixup.safe_push (stmt); | |
| 0 | 2032 } |
| 111 | 2033 return retval; |
| 0 | 2034 } |