Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-ifcombine.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:39:51 +0900 |
| parents | 855418dad1a3 |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* Combining of if-expressions on trees. |
| 2 Copyright (C) 2007, 2008 Free Software Foundation, Inc. | |
| 3 Contributed by Richard Guenther <rguenther@suse.de> | |
| 4 | |
| 5 This file is part of GCC. | |
| 6 | |
| 7 GCC is free software; you can redistribute it and/or modify | |
| 8 it under the terms of the GNU General Public License as published by | |
| 9 the Free Software Foundation; either version 3, or (at your option) | |
| 10 any later version. | |
| 11 | |
| 12 GCC is distributed in the hope that it will be useful, | |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 15 GNU General Public License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along with GCC; see the file COPYING3. If not see | |
| 19 <http://www.gnu.org/licenses/>. */ | |
| 20 | |
| 21 #include "config.h" | |
| 22 #include "system.h" | |
| 23 #include "coretypes.h" | |
| 24 #include "tm.h" | |
| 25 #include "tree.h" | |
| 26 #include "basic-block.h" | |
| 27 #include "timevar.h" | |
| 28 #include "diagnostic.h" | |
| 29 #include "tree-flow.h" | |
| 30 #include "tree-pass.h" | |
| 31 #include "tree-dump.h" | |
| 32 | |
| 33 /* This pass combines COND_EXPRs to simplify control flow. It | |
| 34 currently recognizes bit tests and comparisons in chains that | |
| 35 represent logical and or logical or of two COND_EXPRs. | |
| 36 | |
| 37 It does so by walking basic blocks in a approximate reverse | |
| 38 post-dominator order and trying to match CFG patterns that | |
| 39 represent logical and or logical or of two COND_EXPRs. | |
| 40 Transformations are done if the COND_EXPR conditions match | |
| 41 either | |
| 42 | |
| 43 1. two single bit tests X & (1 << Yn) (for logical and) | |
| 44 | |
| 45 2. two bit tests X & Yn (for logical or) | |
| 46 | |
| 47 3. two comparisons X OPn Y (for logical or) | |
| 48 | |
| 49 To simplify this pass, removing basic blocks and dead code | |
| 50 is left to CFG cleanup and DCE. */ | |
| 51 | |
| 52 | |
| 53 /* Recognize a if-then-else CFG pattern starting to match with the | |
| 54 COND_BB basic-block containing the COND_EXPR. The recognized | |
| 55 then end else blocks are stored to *THEN_BB and *ELSE_BB. If | |
| 56 *THEN_BB and/or *ELSE_BB are already set, they are required to | |
| 57 match the then and else basic-blocks to make the pattern match. | |
| 58 Returns true if the pattern matched, false otherwise. */ | |
| 59 | |
| 60 static bool | |
| 61 recognize_if_then_else (basic_block cond_bb, | |
| 62 basic_block *then_bb, basic_block *else_bb) | |
| 63 { | |
| 64 edge t, e; | |
| 65 | |
| 66 if (EDGE_COUNT (cond_bb->succs) != 2) | |
| 67 return false; | |
| 68 | |
| 69 /* Find the then/else edges. */ | |
| 70 t = EDGE_SUCC (cond_bb, 0); | |
| 71 e = EDGE_SUCC (cond_bb, 1); | |
| 72 if (!(t->flags & EDGE_TRUE_VALUE)) | |
| 73 { | |
| 74 edge tmp = t; | |
| 75 t = e; | |
| 76 e = tmp; | |
| 77 } | |
| 78 if (!(t->flags & EDGE_TRUE_VALUE) | |
| 79 || !(e->flags & EDGE_FALSE_VALUE)) | |
| 80 return false; | |
| 81 | |
| 82 /* Check if the edge destinations point to the required block. */ | |
| 83 if (*then_bb | |
| 84 && t->dest != *then_bb) | |
| 85 return false; | |
| 86 if (*else_bb | |
| 87 && e->dest != *else_bb) | |
| 88 return false; | |
| 89 | |
| 90 if (!*then_bb) | |
| 91 *then_bb = t->dest; | |
| 92 if (!*else_bb) | |
| 93 *else_bb = e->dest; | |
| 94 | |
| 95 return true; | |
| 96 } | |
| 97 | |
| 98 /* Verify if the basic block BB does not have side-effects. Return | |
| 99 true in this case, else false. */ | |
| 100 | |
| 101 static bool | |
| 102 bb_no_side_effects_p (basic_block bb) | |
| 103 { | |
| 104 gimple_stmt_iterator gsi; | |
| 105 | |
| 106 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 107 { | |
| 108 gimple stmt = gsi_stmt (gsi); | |
| 109 | |
| 110 if (gimple_has_volatile_ops (stmt) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
111 || gimple_vuse (stmt)) |
| 0 | 112 return false; |
| 113 } | |
| 114 | |
| 115 return true; | |
| 116 } | |
| 117 | |
| 118 /* Verify if all PHI node arguments in DEST for edges from BB1 or | |
| 119 BB2 to DEST are the same. This makes the CFG merge point | |
| 120 free from side-effects. Return true in this case, else false. */ | |
| 121 | |
| 122 static bool | |
| 123 same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest) | |
| 124 { | |
| 125 edge e1 = find_edge (bb1, dest); | |
| 126 edge e2 = find_edge (bb2, dest); | |
| 127 gimple_stmt_iterator gsi; | |
| 128 gimple phi; | |
| 129 | |
| 130 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 131 { | |
| 132 phi = gsi_stmt (gsi); | |
| 133 if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1), | |
| 134 PHI_ARG_DEF_FROM_EDGE (phi, e2), 0)) | |
| 135 return false; | |
| 136 } | |
| 137 | |
| 138 return true; | |
| 139 } | |
| 140 | |
| 141 /* Return the best representative SSA name for CANDIDATE which is used | |
| 142 in a bit test. */ | |
| 143 | |
| 144 static tree | |
| 145 get_name_for_bit_test (tree candidate) | |
| 146 { | |
| 147 /* Skip single-use names in favor of using the name from a | |
| 148 non-widening conversion definition. */ | |
| 149 if (TREE_CODE (candidate) == SSA_NAME | |
| 150 && has_single_use (candidate)) | |
| 151 { | |
| 152 gimple def_stmt = SSA_NAME_DEF_STMT (candidate); | |
| 153 if (is_gimple_assign (def_stmt) | |
| 36 | 154 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))) |
| 0 | 155 { |
| 156 if (TYPE_PRECISION (TREE_TYPE (candidate)) | |
| 157 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))) | |
| 158 return gimple_assign_rhs1 (def_stmt); | |
| 159 } | |
| 160 } | |
| 161 | |
| 162 return candidate; | |
| 163 } | |
| 164 | |
| 165 /* Recognize a single bit test pattern in GIMPLE_COND and its defining | |
| 166 statements. Store the name being tested in *NAME and the bit | |
| 167 in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT). | |
| 168 Returns true if the pattern matched, false otherwise. */ | |
| 169 | |
| 170 static bool | |
| 171 recognize_single_bit_test (gimple cond, tree *name, tree *bit) | |
| 172 { | |
| 173 gimple stmt; | |
| 174 | |
| 175 /* Get at the definition of the result of the bit test. */ | |
| 176 if (gimple_cond_code (cond) != NE_EXPR | |
| 177 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME | |
| 178 || !integer_zerop (gimple_cond_rhs (cond))) | |
| 179 return false; | |
| 180 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)); | |
| 181 if (!is_gimple_assign (stmt)) | |
| 182 return false; | |
| 183 | |
| 184 /* Look at which bit is tested. One form to recognize is | |
| 185 D.1985_5 = state_3(D) >> control1_4(D); | |
| 186 D.1986_6 = (int) D.1985_5; | |
| 187 D.1987_7 = op0 & 1; | |
| 188 if (D.1987_7 != 0) */ | |
| 189 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR | |
| 190 && integer_onep (gimple_assign_rhs2 (stmt)) | |
| 191 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) | |
| 192 { | |
| 193 tree orig_name = gimple_assign_rhs1 (stmt); | |
| 194 | |
| 195 /* Look through copies and conversions to eventually | |
| 196 find the stmt that computes the shift. */ | |
| 197 stmt = SSA_NAME_DEF_STMT (orig_name); | |
| 198 | |
| 199 while (is_gimple_assign (stmt) | |
| 36 | 200 && ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)) |
| 201 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt))) | |
| 202 <= TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt))))) | |
| 203 || gimple_assign_ssa_name_copy_p (stmt))) | |
| 204 stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); | |
| 0 | 205 |
| 206 /* If we found such, decompose it. */ | |
| 207 if (is_gimple_assign (stmt) | |
| 208 && gimple_assign_rhs_code (stmt) == RSHIFT_EXPR) | |
| 209 { | |
| 210 /* op0 & (1 << op1) */ | |
| 211 *bit = gimple_assign_rhs2 (stmt); | |
| 212 *name = gimple_assign_rhs1 (stmt); | |
| 213 } | |
| 214 else | |
| 215 { | |
| 216 /* t & 1 */ | |
| 217 *bit = integer_zero_node; | |
| 218 *name = get_name_for_bit_test (orig_name); | |
| 219 } | |
| 220 | |
| 221 return true; | |
| 222 } | |
| 223 | |
| 224 /* Another form is | |
| 225 D.1987_7 = op0 & (1 << CST) | |
| 226 if (D.1987_7 != 0) */ | |
| 227 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR | |
| 228 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
| 229 && integer_pow2p (gimple_assign_rhs2 (stmt))) | |
| 230 { | |
| 231 *name = gimple_assign_rhs1 (stmt); | |
| 232 *bit = build_int_cst (integer_type_node, | |
| 233 tree_log2 (gimple_assign_rhs2 (stmt))); | |
| 234 return true; | |
| 235 } | |
| 236 | |
| 237 /* Another form is | |
| 238 D.1986_6 = 1 << control1_4(D) | |
| 239 D.1987_7 = op0 & D.1986_6 | |
| 240 if (D.1987_7 != 0) */ | |
| 241 if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR | |
| 242 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
| 243 && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME) | |
| 244 { | |
| 245 gimple tmp; | |
| 246 | |
| 247 /* Both arguments of the BIT_AND_EXPR can be the single-bit | |
| 248 specifying expression. */ | |
| 249 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); | |
| 250 if (is_gimple_assign (tmp) | |
| 251 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR | |
| 252 && integer_onep (gimple_assign_rhs1 (tmp))) | |
| 253 { | |
| 254 *name = gimple_assign_rhs2 (stmt); | |
| 255 *bit = gimple_assign_rhs2 (tmp); | |
| 256 return true; | |
| 257 } | |
| 258 | |
| 259 tmp = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)); | |
| 260 if (is_gimple_assign (tmp) | |
| 261 && gimple_assign_rhs_code (tmp) == LSHIFT_EXPR | |
| 262 && integer_onep (gimple_assign_rhs1 (tmp))) | |
| 263 { | |
| 264 *name = gimple_assign_rhs1 (stmt); | |
| 265 *bit = gimple_assign_rhs2 (tmp); | |
| 266 return true; | |
| 267 } | |
| 268 } | |
| 269 | |
| 270 return false; | |
| 271 } | |
| 272 | |
| 273 /* Recognize a bit test pattern in a GIMPLE_COND and its defining | |
| 274 statements. Store the name being tested in *NAME and the bits | |
| 275 in *BITS. The COND_EXPR computes *NAME & *BITS. | |
| 276 Returns true if the pattern matched, false otherwise. */ | |
| 277 | |
| 278 static bool | |
| 279 recognize_bits_test (gimple cond, tree *name, tree *bits) | |
| 280 { | |
| 281 gimple stmt; | |
| 282 | |
| 283 /* Get at the definition of the result of the bit test. */ | |
| 284 if (gimple_cond_code (cond) != NE_EXPR | |
| 285 || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME | |
| 286 || !integer_zerop (gimple_cond_rhs (cond))) | |
| 287 return false; | |
| 288 stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)); | |
| 289 if (!is_gimple_assign (stmt) | |
| 290 || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR) | |
| 291 return false; | |
| 292 | |
| 293 *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt)); | |
| 294 *bits = gimple_assign_rhs2 (stmt); | |
| 295 | |
| 296 return true; | |
| 297 } | |
| 298 | |
| 299 /* If-convert on a and pattern with a common else block. The inner | |
| 300 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB. | |
| 301 Returns true if the edges to the common else basic-block were merged. */ | |
| 302 | |
| 303 static bool | |
| 304 ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb) | |
| 305 { | |
| 306 gimple_stmt_iterator gsi; | |
| 307 gimple inner_cond, outer_cond; | |
| 308 tree name1, name2, bit1, bit2; | |
| 309 | |
| 310 inner_cond = last_stmt (inner_cond_bb); | |
| 311 if (!inner_cond | |
| 312 || gimple_code (inner_cond) != GIMPLE_COND) | |
| 313 return false; | |
| 314 | |
| 315 outer_cond = last_stmt (outer_cond_bb); | |
| 316 if (!outer_cond | |
| 317 || gimple_code (outer_cond) != GIMPLE_COND) | |
| 318 return false; | |
| 319 | |
| 320 /* See if we test a single bit of the same name in both tests. In | |
| 321 that case remove the outer test, merging both else edges, | |
| 322 and change the inner one to test for | |
| 323 name & (bit1 | bit2) == (bit1 | bit2). */ | |
| 324 if (recognize_single_bit_test (inner_cond, &name1, &bit1) | |
| 325 && recognize_single_bit_test (outer_cond, &name2, &bit2) | |
| 326 && name1 == name2) | |
| 327 { | |
| 328 tree t, t2; | |
| 329 | |
| 330 /* Do it. */ | |
| 331 gsi = gsi_for_stmt (inner_cond); | |
| 332 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1), | |
| 333 build_int_cst (TREE_TYPE (name1), 1), bit1); | |
| 334 t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1), | |
| 335 build_int_cst (TREE_TYPE (name1), 1), bit2); | |
| 336 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2); | |
| 337 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, | |
| 338 true, GSI_SAME_STMT); | |
| 339 t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); | |
| 340 t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE, | |
| 341 true, GSI_SAME_STMT); | |
| 342 t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
343 t = canonicalize_cond_expr_cond (t); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
344 if (!t) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
345 return false; |
| 0 | 346 gimple_cond_set_condition_from_tree (inner_cond, t); |
| 347 update_stmt (inner_cond); | |
| 348 | |
| 349 /* Leave CFG optimization to cfg_cleanup. */ | |
| 350 gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node); | |
| 351 update_stmt (outer_cond); | |
| 352 | |
| 353 if (dump_file) | |
| 354 { | |
| 355 fprintf (dump_file, "optimizing double bit test to "); | |
| 356 print_generic_expr (dump_file, name1, 0); | |
| 357 fprintf (dump_file, " & T == T\nwith temporary T = (1 << "); | |
| 358 print_generic_expr (dump_file, bit1, 0); | |
| 359 fprintf (dump_file, ") | (1 << "); | |
| 360 print_generic_expr (dump_file, bit2, 0); | |
| 361 fprintf (dump_file, ")\n"); | |
| 362 } | |
| 363 | |
| 364 return true; | |
| 365 } | |
| 366 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
367 /* See if we have two comparisons that we can merge into one. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
368 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
369 && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
370 && operand_equal_p (gimple_cond_lhs (inner_cond), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
371 gimple_cond_lhs (outer_cond), 0) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
372 && operand_equal_p (gimple_cond_rhs (inner_cond), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
373 gimple_cond_rhs (outer_cond), 0)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
374 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
375 enum tree_code code1 = gimple_cond_code (inner_cond); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
376 enum tree_code code2 = gimple_cond_code (outer_cond); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
377 tree t; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
378 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
379 if (!(t = combine_comparisons (UNKNOWN_LOCATION, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
380 TRUTH_ANDIF_EXPR, code1, code2, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
381 boolean_type_node, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
382 gimple_cond_lhs (outer_cond), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
383 gimple_cond_rhs (outer_cond)))) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
384 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
385 t = canonicalize_cond_expr_cond (t); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
386 if (!t) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
387 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
388 gimple_cond_set_condition_from_tree (inner_cond, t); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
389 update_stmt (inner_cond); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
390 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
391 /* Leave CFG optimization to cfg_cleanup. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
392 gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
393 update_stmt (outer_cond); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
394 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
395 if (dump_file) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
396 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
397 fprintf (dump_file, "optimizing two comparisons to "); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
398 print_generic_expr (dump_file, t, 0); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
399 fprintf (dump_file, "\n"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
400 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
401 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
402 return true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
403 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
404 |
| 0 | 405 return false; |
| 406 } | |
| 407 | |
| 408 /* If-convert on a or pattern with a common then block. The inner | |
| 409 if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB. | |
| 410 Returns true, if the edges leading to the common then basic-block | |
| 411 were merged. */ | |
| 412 | |
| 413 static bool | |
| 414 ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb) | |
| 415 { | |
| 416 gimple inner_cond, outer_cond; | |
| 417 tree name1, name2, bits1, bits2; | |
| 418 | |
| 419 inner_cond = last_stmt (inner_cond_bb); | |
| 420 if (!inner_cond | |
| 421 || gimple_code (inner_cond) != GIMPLE_COND) | |
| 422 return false; | |
| 423 | |
| 424 outer_cond = last_stmt (outer_cond_bb); | |
| 425 if (!outer_cond | |
| 426 || gimple_code (outer_cond) != GIMPLE_COND) | |
| 427 return false; | |
| 428 | |
| 429 /* See if we have two bit tests of the same name in both tests. | |
| 430 In that case remove the outer test and change the inner one to | |
| 431 test for name & (bits1 | bits2) != 0. */ | |
| 432 if (recognize_bits_test (inner_cond, &name1, &bits1) | |
| 433 && recognize_bits_test (outer_cond, &name2, &bits2)) | |
| 434 { | |
| 435 gimple_stmt_iterator gsi; | |
| 436 tree t; | |
| 437 | |
| 438 /* Find the common name which is bit-tested. */ | |
| 439 if (name1 == name2) | |
| 440 ; | |
| 441 else if (bits1 == bits2) | |
| 442 { | |
| 443 t = name2; | |
| 444 name2 = bits2; | |
| 445 bits2 = t; | |
| 446 t = name1; | |
| 447 name1 = bits1; | |
| 448 bits1 = t; | |
| 449 } | |
| 450 else if (name1 == bits2) | |
| 451 { | |
| 452 t = name2; | |
| 453 name2 = bits2; | |
| 454 bits2 = t; | |
| 455 } | |
| 456 else if (bits1 == name2) | |
| 457 { | |
| 458 t = name1; | |
| 459 name1 = bits1; | |
| 460 bits1 = t; | |
| 461 } | |
| 462 else | |
| 463 return false; | |
| 464 | |
| 465 /* As we strip non-widening conversions in finding a common | |
| 466 name that is tested make sure to end up with an integral | |
| 467 type for building the bit operations. */ | |
| 468 if (TYPE_PRECISION (TREE_TYPE (bits1)) | |
| 469 >= TYPE_PRECISION (TREE_TYPE (bits2))) | |
| 470 { | |
| 471 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1); | |
| 472 name1 = fold_convert (TREE_TYPE (bits1), name1); | |
| 473 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2); | |
| 474 bits2 = fold_convert (TREE_TYPE (bits1), bits2); | |
| 475 } | |
| 476 else | |
| 477 { | |
| 478 bits2 = fold_convert (unsigned_type_for (TREE_TYPE (bits2)), bits2); | |
| 479 name1 = fold_convert (TREE_TYPE (bits2), name1); | |
| 480 bits1 = fold_convert (unsigned_type_for (TREE_TYPE (bits1)), bits1); | |
| 481 bits1 = fold_convert (TREE_TYPE (bits2), bits1); | |
| 482 } | |
| 483 | |
| 484 /* Do it. */ | |
| 485 gsi = gsi_for_stmt (inner_cond); | |
| 486 t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2); | |
| 487 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, | |
| 488 true, GSI_SAME_STMT); | |
| 489 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t); | |
| 490 t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE, | |
| 491 true, GSI_SAME_STMT); | |
| 492 t = fold_build2 (NE_EXPR, boolean_type_node, t, | |
| 493 build_int_cst (TREE_TYPE (t), 0)); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
494 t = canonicalize_cond_expr_cond (t); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
495 if (!t) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
496 return false; |
| 0 | 497 gimple_cond_set_condition_from_tree (inner_cond, t); |
| 498 update_stmt (inner_cond); | |
| 499 | |
| 500 /* Leave CFG optimization to cfg_cleanup. */ | |
| 501 gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node); | |
| 502 update_stmt (outer_cond); | |
| 503 | |
| 504 if (dump_file) | |
| 505 { | |
| 506 fprintf (dump_file, "optimizing bits or bits test to "); | |
| 507 print_generic_expr (dump_file, name1, 0); | |
| 508 fprintf (dump_file, " & T != 0\nwith temporary T = "); | |
| 509 print_generic_expr (dump_file, bits1, 0); | |
| 510 fprintf (dump_file, " | "); | |
| 511 print_generic_expr (dump_file, bits2, 0); | |
| 512 fprintf (dump_file, "\n"); | |
| 513 } | |
| 514 | |
| 515 return true; | |
| 516 } | |
| 517 | |
| 518 /* See if we have two comparisons that we can merge into one. | |
| 519 This happens for C++ operator overloading where for example | |
| 520 GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */ | |
| 521 else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison | |
| 522 && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison | |
| 523 && operand_equal_p (gimple_cond_lhs (inner_cond), | |
| 524 gimple_cond_lhs (outer_cond), 0) | |
| 525 && operand_equal_p (gimple_cond_rhs (inner_cond), | |
| 526 gimple_cond_rhs (outer_cond), 0)) | |
| 527 { | |
| 528 enum tree_code code1 = gimple_cond_code (inner_cond); | |
| 529 enum tree_code code2 = gimple_cond_code (outer_cond); | |
| 530 tree t; | |
| 531 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
532 if (!(t = combine_comparisons (UNKNOWN_LOCATION, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
533 TRUTH_ORIF_EXPR, code1, code2, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
534 boolean_type_node, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
535 gimple_cond_lhs (outer_cond), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
536 gimple_cond_rhs (outer_cond)))) |
| 0 | 537 return false; |
| 538 t = canonicalize_cond_expr_cond (t); | |
| 539 if (!t) | |
| 540 return false; | |
| 541 gimple_cond_set_condition_from_tree (inner_cond, t); | |
| 542 update_stmt (inner_cond); | |
| 543 | |
| 544 /* Leave CFG optimization to cfg_cleanup. */ | |
| 545 gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node); | |
| 546 update_stmt (outer_cond); | |
| 547 | |
| 548 if (dump_file) | |
| 549 { | |
| 550 fprintf (dump_file, "optimizing two comparisons to "); | |
| 551 print_generic_expr (dump_file, t, 0); | |
| 552 fprintf (dump_file, "\n"); | |
| 553 } | |
| 554 | |
| 555 return true; | |
| 556 } | |
| 557 | |
| 558 return false; | |
| 559 } | |
| 560 | |
| 561 /* Recognize a CFG pattern and dispatch to the appropriate | |
| 562 if-conversion helper. We start with BB as the innermost | |
| 563 worker basic-block. Returns true if a transformation was done. */ | |
| 564 | |
| 565 static bool | |
| 566 tree_ssa_ifcombine_bb (basic_block inner_cond_bb) | |
| 567 { | |
| 568 basic_block then_bb = NULL, else_bb = NULL; | |
| 569 | |
| 570 if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb)) | |
| 571 return false; | |
| 572 | |
| 573 /* Recognize && and || of two conditions with a common | |
| 574 then/else block which entry edges we can merge. That is: | |
| 575 if (a || b) | |
| 576 ; | |
| 577 and | |
| 578 if (a && b) | |
| 579 ; | |
| 580 This requires a single predecessor of the inner cond_bb. */ | |
| 581 if (single_pred_p (inner_cond_bb)) | |
| 582 { | |
| 583 basic_block outer_cond_bb = single_pred (inner_cond_bb); | |
| 584 | |
| 585 /* The && form is characterized by a common else_bb with | |
| 586 the two edges leading to it mergable. The latter is | |
| 587 guaranteed by matching PHI arguments in the else_bb and | |
| 588 the inner cond_bb having no side-effects. */ | |
| 589 if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb) | |
| 590 && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb) | |
| 591 && bb_no_side_effects_p (inner_cond_bb)) | |
| 592 { | |
| 593 /* We have | |
| 594 <outer_cond_bb> | |
| 595 if (q) goto inner_cond_bb; else goto else_bb; | |
| 596 <inner_cond_bb> | |
| 597 if (p) goto ...; else goto else_bb; | |
| 598 ... | |
| 599 <else_bb> | |
| 600 ... | |
| 601 */ | |
| 602 return ifcombine_ifandif (inner_cond_bb, outer_cond_bb); | |
| 603 } | |
| 604 | |
| 605 /* The || form is characterized by a common then_bb with the | |
| 606 two edges leading to it mergable. The latter is guaranteed | |
| 607 by matching PHI arguments in the then_bb and the inner cond_bb | |
| 608 having no side-effects. */ | |
| 609 if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb) | |
| 610 && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb) | |
| 611 && bb_no_side_effects_p (inner_cond_bb)) | |
| 612 { | |
| 613 /* We have | |
| 614 <outer_cond_bb> | |
| 615 if (q) goto then_bb; else goto inner_cond_bb; | |
| 616 <inner_cond_bb> | |
| 617 if (q) goto then_bb; else goto ...; | |
| 618 <then_bb> | |
| 619 ... | |
| 620 */ | |
| 621 return ifcombine_iforif (inner_cond_bb, outer_cond_bb); | |
| 622 } | |
| 623 } | |
| 624 | |
| 625 return false; | |
| 626 } | |
| 627 | |
| 628 /* Main entry for the tree if-conversion pass. */ | |
| 629 | |
| 630 static unsigned int | |
| 631 tree_ssa_ifcombine (void) | |
| 632 { | |
| 633 basic_block *bbs; | |
| 634 bool cfg_changed = false; | |
| 635 int i; | |
| 636 | |
| 637 bbs = blocks_in_phiopt_order (); | |
| 638 | |
| 639 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i) | |
| 640 { | |
| 641 basic_block bb = bbs[i]; | |
| 642 gimple stmt = last_stmt (bb); | |
| 643 | |
| 644 if (stmt | |
| 645 && gimple_code (stmt) == GIMPLE_COND) | |
| 646 cfg_changed |= tree_ssa_ifcombine_bb (bb); | |
| 647 } | |
| 648 | |
| 649 free (bbs); | |
| 650 | |
| 651 return cfg_changed ? TODO_cleanup_cfg : 0; | |
| 652 } | |
| 653 | |
| 654 static bool | |
| 655 gate_ifcombine (void) | |
| 656 { | |
| 657 return 1; | |
| 658 } | |
| 659 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
660 struct gimple_opt_pass pass_tree_ifcombine = |
| 0 | 661 { |
| 662 { | |
| 663 GIMPLE_PASS, | |
| 664 "ifcombine", /* name */ | |
| 665 gate_ifcombine, /* gate */ | |
| 666 tree_ssa_ifcombine, /* execute */ | |
| 667 NULL, /* sub */ | |
| 668 NULL, /* next */ | |
| 669 0, /* static_pass_number */ | |
| 670 TV_TREE_IFCOMBINE, /* tv_id */ | |
| 671 PROP_cfg | PROP_ssa, /* properties_required */ | |
| 672 0, /* properties_provided */ | |
| 673 0, /* properties_destroyed */ | |
| 674 0, /* todo_flags_start */ | |
| 675 TODO_dump_func | |
| 676 | TODO_ggc_collect | |
| 677 | TODO_update_ssa | |
| 678 | TODO_verify_ssa /* todo_flags_finish */ | |
| 679 } | |
| 680 }; |