Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-if-conv.c @ 59:5b5b9ea5b220
fix
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 15 Feb 2010 17:22:24 +0900 |
| parents | 77e2b8dfacca |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* If-conversion for vectorizer. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 Free Software Foundation, Inc. |
| 0 | 4 Contributed by Devang Patel <dpatel@apple.com> |
| 5 | |
| 6 This file is part of GCC. | |
| 7 | |
| 8 GCC is free software; you can redistribute it and/or modify it under | |
| 9 the terms of the GNU General Public License as published by the Free | |
| 10 Software Foundation; either version 3, or (at your option) any later | |
| 11 version. | |
| 12 | |
| 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
| 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 16 for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
| 19 along with GCC; see the file COPYING3. If not see | |
| 20 <http://www.gnu.org/licenses/>. */ | |
| 21 | |
| 22 /* This pass implements tree level if-conversion transformation of loops. | |
| 23 Initial goal is to help vectorizer vectorize loops with conditions. | |
| 24 | |
| 25 A short description of if-conversion: | |
| 26 | |
| 27 o Decide if a loop is if-convertible or not. | |
| 28 o Walk all loop basic blocks in breadth first order (BFS order). | |
| 29 o Remove conditional statements (at the end of basic block) | |
| 30 and propagate condition into destination basic blocks' | |
| 31 predicate list. | |
| 32 o Replace modify expression with conditional modify expression | |
| 33 using current basic block's condition. | |
| 34 o Merge all basic blocks | |
| 35 o Replace phi nodes with conditional modify expr | |
| 36 o Merge all basic blocks into header | |
| 37 | |
| 38 Sample transformation: | |
| 39 | |
| 40 INPUT | |
| 41 ----- | |
| 42 | |
| 43 # i_23 = PHI <0(0), i_18(10)>; | |
| 44 <L0>:; | |
| 45 j_15 = A[i_23]; | |
| 46 if (j_15 > 41) goto <L1>; else goto <L17>; | |
| 47 | |
| 48 <L17>:; | |
| 49 goto <bb 3> (<L3>); | |
| 50 | |
| 51 <L1>:; | |
| 52 | |
| 53 # iftmp.2_4 = PHI <0(8), 42(2)>; | |
| 54 <L3>:; | |
| 55 A[i_23] = iftmp.2_4; | |
| 56 i_18 = i_23 + 1; | |
| 57 if (i_18 <= 15) goto <L19>; else goto <L18>; | |
| 58 | |
| 59 <L19>:; | |
| 60 goto <bb 1> (<L0>); | |
| 61 | |
| 62 <L18>:; | |
| 63 | |
| 64 OUTPUT | |
| 65 ------ | |
| 66 | |
| 67 # i_23 = PHI <0(0), i_18(10)>; | |
| 68 <L0>:; | |
| 69 j_15 = A[i_23]; | |
| 70 | |
| 71 <L3>:; | |
| 72 iftmp.2_4 = j_15 > 41 ? 42 : 0; | |
| 73 A[i_23] = iftmp.2_4; | |
| 74 i_18 = i_23 + 1; | |
| 75 if (i_18 <= 15) goto <L19>; else goto <L18>; | |
| 76 | |
| 77 <L19>:; | |
| 78 goto <bb 1> (<L0>); | |
| 79 | |
| 80 <L18>:; | |
| 81 */ | |
| 82 | |
| 83 #include "config.h" | |
| 84 #include "system.h" | |
| 85 #include "coretypes.h" | |
| 86 #include "tm.h" | |
| 87 #include "tree.h" | |
| 88 #include "flags.h" | |
| 89 #include "timevar.h" | |
| 90 #include "varray.h" | |
| 91 #include "rtl.h" | |
| 92 #include "basic-block.h" | |
| 93 #include "diagnostic.h" | |
| 94 #include "tree-flow.h" | |
| 95 #include "tree-dump.h" | |
| 96 #include "cfgloop.h" | |
| 97 #include "tree-chrec.h" | |
| 98 #include "tree-data-ref.h" | |
| 99 #include "tree-scalar-evolution.h" | |
| 100 #include "tree-pass.h" | |
| 101 #include "target.h" | |
| 102 | |
| 103 | |
| 104 /* local function prototypes */ | |
| 105 static unsigned int main_tree_if_conversion (void); | |
| 106 static tree tree_if_convert_stmt (struct loop *loop, gimple, tree, | |
| 107 gimple_stmt_iterator *); | |
| 108 static void tree_if_convert_cond_stmt (struct loop *, gimple, tree, | |
| 109 gimple_stmt_iterator *); | |
| 110 static bool if_convertible_phi_p (struct loop *, basic_block, gimple); | |
| 111 static bool if_convertible_gimple_assign_stmt_p (struct loop *, basic_block, | |
| 112 gimple); | |
| 113 static bool if_convertible_stmt_p (struct loop *, basic_block, gimple); | |
| 114 static bool if_convertible_bb_p (struct loop *, basic_block, basic_block); | |
| 115 static bool if_convertible_loop_p (struct loop *, bool); | |
| 116 static void add_to_predicate_list (basic_block, tree); | |
| 117 static tree add_to_dst_predicate_list (struct loop * loop, edge, | |
| 118 tree, tree, | |
| 119 gimple_stmt_iterator *); | |
| 120 static void clean_predicate_lists (struct loop *loop); | |
| 121 static basic_block find_phi_replacement_condition (struct loop *loop, | |
| 122 basic_block, tree *, | |
| 123 gimple_stmt_iterator *); | |
| 124 static void replace_phi_with_cond_gimple_assign_stmt (gimple, tree, | |
| 125 basic_block, | |
| 126 gimple_stmt_iterator *); | |
| 127 static void process_phi_nodes (struct loop *); | |
| 128 static void combine_blocks (struct loop *); | |
| 129 static gimple ifc_temp_var (tree, tree); | |
| 130 static bool pred_blocks_visited_p (basic_block, bitmap *); | |
| 131 static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop); | |
| 132 static bool bb_with_exit_edge_p (struct loop *, basic_block); | |
| 133 | |
| 134 /* List of basic blocks in if-conversion-suitable order. */ | |
| 135 static basic_block *ifc_bbs; | |
| 136 | |
| 137 /* Main entry point. | |
| 138 Apply if-conversion to the LOOP. Return true if successful otherwise return | |
| 139 false. If false is returned then loop remains unchanged. | |
| 140 FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used | |
| 141 for vectorizer or not. If it is used for vectorizer, additional checks are | |
| 142 used. (Vectorization checks are not yet implemented). */ | |
| 143 | |
| 144 static bool | |
| 145 tree_if_conversion (struct loop *loop, bool for_vectorizer) | |
| 146 { | |
| 147 basic_block bb; | |
| 148 gimple_stmt_iterator itr; | |
| 149 unsigned int i; | |
| 150 | |
| 151 ifc_bbs = NULL; | |
| 152 | |
| 153 /* if-conversion is not appropriate for all loops. First, check if loop is | |
| 154 if-convertible or not. */ | |
| 155 if (!if_convertible_loop_p (loop, for_vectorizer)) | |
| 156 { | |
| 157 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 158 fprintf (dump_file,"-------------------------\n"); | |
| 159 if (ifc_bbs) | |
| 160 { | |
| 161 free (ifc_bbs); | |
| 162 ifc_bbs = NULL; | |
| 163 } | |
| 164 free_dominance_info (CDI_POST_DOMINATORS); | |
| 165 return false; | |
| 166 } | |
| 167 | |
| 168 /* Do actual work now. */ | |
| 169 for (i = 0; i < loop->num_nodes; i++) | |
| 170 { | |
| 171 tree cond; | |
| 172 | |
| 173 bb = ifc_bbs [i]; | |
| 174 | |
| 175 /* Update condition using predicate list. */ | |
| 176 cond = (tree) bb->aux; | |
| 177 | |
| 178 /* Process all statements in this basic block. | |
| 179 Remove conditional expression, if any, and annotate | |
| 180 destination basic block(s) appropriately. */ | |
| 181 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */) | |
| 182 { | |
| 183 gimple t = gsi_stmt (itr); | |
| 184 cond = tree_if_convert_stmt (loop, t, cond, &itr); | |
| 185 if (!gsi_end_p (itr)) | |
| 186 gsi_next (&itr); | |
| 187 } | |
| 188 | |
| 189 /* If current bb has only one successor, then consider it as an | |
| 190 unconditional goto. */ | |
| 191 if (single_succ_p (bb)) | |
| 192 { | |
| 193 basic_block bb_n = single_succ (bb); | |
| 194 | |
| 195 /* Successor bb inherits predicate of its predecessor. If there | |
| 196 is no predicate in predecessor bb, then consider successor bb | |
| 197 as always executed. */ | |
| 198 if (cond == NULL_TREE) | |
| 199 cond = boolean_true_node; | |
| 200 | |
| 201 add_to_predicate_list (bb_n, cond); | |
| 202 } | |
| 203 } | |
| 204 | |
| 205 /* Now, all statements are if-converted and basic blocks are | |
| 206 annotated appropriately. Combine all basic block into one huge | |
| 207 basic block. */ | |
| 208 combine_blocks (loop); | |
| 209 | |
| 210 /* clean up */ | |
| 211 clean_predicate_lists (loop); | |
| 212 free (ifc_bbs); | |
| 213 ifc_bbs = NULL; | |
| 214 | |
| 215 return true; | |
| 216 } | |
| 217 | |
| 218 /* if-convert stmt T which is part of LOOP. | |
| 219 If T is a GIMPLE_ASSIGN then it is converted into conditional modify | |
| 220 expression using COND. For conditional expressions, add condition in the | |
| 221 destination basic block's predicate list and remove conditional | |
| 222 expression itself. BSI is the iterator used to traverse statements of | |
| 223 loop. It is used here when it is required to delete current statement. */ | |
| 224 | |
| 225 static tree | |
| 226 tree_if_convert_stmt (struct loop * loop, gimple t, tree cond, | |
| 227 gimple_stmt_iterator *gsi) | |
| 228 { | |
| 229 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 230 { | |
| 231 fprintf (dump_file, "------if-convert stmt\n"); | |
| 232 print_gimple_stmt (dump_file, t, 0, TDF_SLIM); | |
| 233 print_generic_stmt (dump_file, cond, TDF_SLIM); | |
| 234 } | |
| 235 | |
| 236 switch (gimple_code (t)) | |
| 237 { | |
| 238 /* Labels are harmless here. */ | |
| 239 case GIMPLE_LABEL: | |
| 240 break; | |
| 241 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
242 case GIMPLE_DEBUG: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
243 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
244 if (gimple_debug_bind_p (gsi_stmt (*gsi))) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
245 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
246 gimple_debug_bind_reset_value (gsi_stmt (*gsi)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
247 update_stmt (gsi_stmt (*gsi)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
248 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
249 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
250 |
| 0 | 251 case GIMPLE_ASSIGN: |
| 252 /* This GIMPLE_ASSIGN is killing previous value of LHS. Appropriate | |
| 253 value will be selected by PHI node based on condition. It is possible | |
| 254 that before this transformation, PHI nodes was selecting default | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
255 value and now it will use this new value. This is OK because it does |
| 0 | 256 not change validity the program. */ |
| 257 break; | |
| 258 | |
| 259 case GIMPLE_COND: | |
| 260 /* Update destination blocks' predicate list and remove this | |
| 261 condition expression. */ | |
| 262 tree_if_convert_cond_stmt (loop, t, cond, gsi); | |
| 263 cond = NULL_TREE; | |
| 264 break; | |
| 265 | |
| 266 default: | |
| 267 gcc_unreachable (); | |
| 268 } | |
| 269 return cond; | |
| 270 } | |
| 271 | |
| 272 /* STMT is a GIMPLE_COND. Update two destination's predicate list. | |
| 273 Remove COND_EXPR, if it is not the loop exit condition. Otherwise | |
| 274 update loop exit condition appropriately. GSI is the iterator | |
| 275 used to traverse statement list. STMT is part of loop LOOP. */ | |
| 276 | |
| 277 static void | |
| 278 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond, | |
| 279 gimple_stmt_iterator *gsi) | |
| 280 { | |
| 281 tree c, c2; | |
| 282 edge true_edge, false_edge; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
283 location_t loc = gimple_location (stmt); |
| 0 | 284 |
| 285 gcc_assert (gimple_code (stmt) == GIMPLE_COND); | |
| 286 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
287 c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node, |
| 0 | 288 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); |
| 289 | |
| 290 extract_true_false_edges_from_block (gimple_bb (stmt), | |
| 291 &true_edge, &false_edge); | |
| 292 | |
| 293 /* Add new condition into destination's predicate list. */ | |
| 294 | |
| 295 /* If C is true then TRUE_EDGE is taken. */ | |
| 296 add_to_dst_predicate_list (loop, true_edge, cond, c, gsi); | |
| 297 | |
| 298 /* If 'c' is false then FALSE_EDGE is taken. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
299 c2 = invert_truthvalue_loc (loc, unshare_expr (c)); |
| 0 | 300 add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi); |
| 301 | |
| 302 /* Now this conditional statement is redundant. Remove it. | |
| 303 But, do not remove exit condition! Update exit condition | |
| 304 using new condition. */ | |
| 305 if (!bb_with_exit_edge_p (loop, gimple_bb (stmt))) | |
| 306 { | |
| 307 gsi_remove (gsi, true); | |
| 308 cond = NULL_TREE; | |
| 309 } | |
| 310 return; | |
| 311 } | |
| 312 | |
| 313 /* Return true, iff PHI is if-convertible. PHI is part of loop LOOP | |
| 314 and it belongs to basic block BB. | |
| 315 PHI is not if-convertible | |
| 316 - if it has more than 2 arguments. | |
| 317 - Virtual PHI is immediately used in another PHI node. | |
| 318 - Virtual PHI on BB other than header. */ | |
| 319 | |
| 320 static bool | |
| 321 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) | |
| 322 { | |
| 323 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 324 { | |
| 325 fprintf (dump_file, "-------------------------\n"); | |
| 326 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); | |
| 327 } | |
| 328 | |
| 329 if (bb != loop->header && gimple_phi_num_args (phi) != 2) | |
| 330 { | |
| 331 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 332 fprintf (dump_file, "More than two phi node args.\n"); | |
| 333 return false; | |
| 334 } | |
| 335 | |
| 336 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi)))) | |
| 337 { | |
| 338 imm_use_iterator imm_iter; | |
| 339 use_operand_p use_p; | |
| 340 | |
| 341 if (bb != loop->header) | |
| 342 { | |
| 343 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 344 fprintf (dump_file, "Virtual phi not on loop header.\n"); | |
| 345 return false; | |
| 346 } | |
| 347 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi)) | |
| 348 { | |
| 349 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI) | |
| 350 { | |
| 351 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 352 fprintf (dump_file, "Difficult to handle this virtual phi.\n"); | |
| 353 return false; | |
| 354 } | |
| 355 } | |
| 356 } | |
| 357 | |
| 358 return true; | |
| 359 } | |
| 360 | |
| 361 /* Return true, if STMT is if-convertible. | |
| 362 GIMPLE_ASSIGN statement is not if-convertible if, | |
| 363 - It is not movable. | |
| 364 - It could trap. | |
| 365 - LHS is not var decl. | |
| 366 GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */ | |
| 367 | |
| 368 static bool | |
| 369 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb, | |
| 370 gimple stmt) | |
| 371 { | |
| 372 tree lhs; | |
| 373 | |
| 374 if (!is_gimple_assign (stmt)) | |
| 375 return false; | |
| 376 | |
| 377 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 378 { | |
| 379 fprintf (dump_file, "-------------------------\n"); | |
| 380 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 381 } | |
| 382 | |
| 383 lhs = gimple_assign_lhs (stmt); | |
| 384 | |
| 385 /* Some of these constrains might be too conservative. */ | |
| 386 if (stmt_ends_bb_p (stmt) | |
| 387 || gimple_has_volatile_ops (stmt) | |
| 388 || (TREE_CODE (lhs) == SSA_NAME | |
| 389 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) | |
| 390 || gimple_has_side_effects (stmt)) | |
| 391 { | |
| 392 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 393 fprintf (dump_file, "stmt not suitable for ifcvt\n"); | |
| 394 return false; | |
| 395 } | |
| 396 | |
| 397 /* See if it needs speculative loading or not. */ | |
| 398 if (bb != loop->header | |
| 399 && gimple_assign_rhs_could_trap_p (stmt)) | |
| 400 { | |
| 401 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 402 fprintf (dump_file, "tree could trap...\n"); | |
| 403 return false; | |
| 404 } | |
| 405 | |
| 406 if (TREE_CODE (lhs) != SSA_NAME | |
| 407 && bb != loop->header | |
| 408 && !bb_with_exit_edge_p (loop, bb)) | |
| 409 { | |
| 410 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 411 { | |
| 412 fprintf (dump_file, "LHS is not var\n"); | |
| 413 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 414 } | |
| 415 return false; | |
| 416 } | |
| 417 | |
| 418 return true; | |
| 419 } | |
| 420 | |
| 421 /* Return true, iff STMT is if-convertible. | |
| 422 Statement is if-convertible if, | |
| 423 - It is if-convertible GIMPLE_ASSGIN | |
| 424 - It is GIMPLE_LABEL or GIMPLE_COND. | |
| 425 STMT is inside block BB, which is inside loop LOOP. */ | |
| 426 | |
| 427 static bool | |
| 428 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt) | |
| 429 { | |
| 430 switch (gimple_code (stmt)) | |
| 431 { | |
| 432 case GIMPLE_LABEL: | |
| 433 break; | |
| 434 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
435 case GIMPLE_DEBUG: |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
436 break; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
437 |
| 0 | 438 case GIMPLE_ASSIGN: |
| 439 if (!if_convertible_gimple_assign_stmt_p (loop, bb, stmt)) | |
| 440 return false; | |
| 441 break; | |
| 442 | |
| 443 case GIMPLE_COND: | |
| 444 break; | |
| 445 | |
| 446 default: | |
| 447 /* Don't know what to do with 'em so don't do anything. */ | |
| 448 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 449 { | |
| 450 fprintf (dump_file, "don't know what to do\n"); | |
| 451 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
| 452 } | |
| 453 return false; | |
| 454 break; | |
| 455 } | |
| 456 | |
| 457 return true; | |
| 458 } | |
| 459 | |
| 460 /* Return true, iff BB is if-convertible. | |
| 461 Note: This routine does _not_ check basic block statements and phis. | |
| 462 Basic block is not if-convertible if, | |
| 463 - Basic block is non-empty and it is after exit block (in BFS order). | |
| 464 - Basic block is after exit block but before latch. | |
| 465 - Basic block edge(s) is not normal. | |
| 466 EXIT_BB_SEEN is true if basic block with exit edge is already seen. | |
| 467 BB is inside loop LOOP. */ | |
| 468 | |
| 469 static bool | |
| 470 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) | |
| 471 { | |
| 472 edge e; | |
| 473 edge_iterator ei; | |
| 474 | |
| 475 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 476 fprintf (dump_file, "----------[%d]-------------\n", bb->index); | |
| 477 | |
| 478 if (exit_bb) | |
| 479 { | |
| 480 if (bb != loop->latch) | |
| 481 { | |
| 482 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 483 fprintf (dump_file, "basic block after exit bb but before latch\n"); | |
| 484 return false; | |
| 485 } | |
| 486 else if (!empty_block_p (bb)) | |
| 487 { | |
| 488 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 489 fprintf (dump_file, "non empty basic block after exit bb\n"); | |
| 490 return false; | |
| 491 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
492 else if (bb == loop->latch |
| 0 | 493 && bb != exit_bb |
| 494 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) | |
| 495 { | |
| 496 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 497 fprintf (dump_file, "latch is not dominated by exit_block\n"); | |
| 498 return false; | |
| 499 } | |
| 500 } | |
| 501 | |
| 502 /* Be less adventurous and handle only normal edges. */ | |
| 503 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 504 if (e->flags & | |
| 505 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) | |
| 506 { | |
| 507 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 508 fprintf (dump_file,"Difficult to handle edges\n"); | |
| 509 return false; | |
| 510 } | |
| 511 | |
| 512 return true; | |
| 513 } | |
| 514 | |
| 515 /* Return true, iff LOOP is if-convertible. | |
| 516 LOOP is if-convertible if, | |
| 517 - It is innermost. | |
| 518 - It has two or more basic blocks. | |
| 519 - It has only one exit. | |
| 520 - Loop header is not the exit edge. | |
| 521 - If its basic blocks and phi nodes are if convertible. See above for | |
| 522 more info. | |
| 523 FOR_VECTORIZER enables vectorizer specific checks. For example, support | |
| 524 for vector conditions, data dependency checks etc.. (Not implemented yet). */ | |
| 525 | |
| 526 static bool | |
| 527 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) | |
| 528 { | |
| 529 basic_block bb; | |
| 530 gimple_stmt_iterator itr; | |
| 531 unsigned int i; | |
| 532 edge e; | |
| 533 edge_iterator ei; | |
| 534 basic_block exit_bb = NULL; | |
| 535 | |
| 536 /* Handle only inner most loop. */ | |
| 537 if (!loop || loop->inner) | |
| 538 { | |
| 539 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 540 fprintf (dump_file, "not inner most loop\n"); | |
| 541 return false; | |
| 542 } | |
| 543 | |
| 544 /* If only one block, no need for if-conversion. */ | |
| 545 if (loop->num_nodes <= 2) | |
| 546 { | |
| 547 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 548 fprintf (dump_file, "less than 2 basic blocks\n"); | |
| 549 return false; | |
| 550 } | |
| 551 | |
| 552 /* More than one loop exit is too much to handle. */ | |
| 553 if (!single_exit (loop)) | |
| 554 { | |
| 555 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 556 fprintf (dump_file, "multiple exits\n"); | |
| 557 return false; | |
| 558 } | |
| 559 | |
| 560 /* ??? Check target's vector conditional operation support for vectorizer. */ | |
| 561 | |
| 562 /* If one of the loop header's edge is exit edge then do not apply | |
| 563 if-conversion. */ | |
| 564 FOR_EACH_EDGE (e, ei, loop->header->succs) | |
| 565 { | |
| 566 if (loop_exit_edge_p (loop, e)) | |
| 567 return false; | |
| 568 } | |
| 569 | |
| 570 calculate_dominance_info (CDI_DOMINATORS); | |
| 571 calculate_dominance_info (CDI_POST_DOMINATORS); | |
| 572 | |
| 573 /* Allow statements that can be handled during if-conversion. */ | |
| 574 ifc_bbs = get_loop_body_in_if_conv_order (loop); | |
| 575 if (!ifc_bbs) | |
| 576 { | |
| 577 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 578 fprintf (dump_file,"Irreducible loop\n"); | |
| 579 free_dominance_info (CDI_POST_DOMINATORS); | |
| 580 return false; | |
| 581 } | |
| 582 | |
| 583 for (i = 0; i < loop->num_nodes; i++) | |
| 584 { | |
| 585 bb = ifc_bbs[i]; | |
| 586 | |
| 587 if (!if_convertible_bb_p (loop, bb, exit_bb)) | |
| 588 return false; | |
| 589 | |
| 590 /* Check statements. */ | |
| 591 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) | |
| 592 if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr))) | |
| 593 return false; | |
| 594 /* ??? Check data dependency for vectorizer. */ | |
| 595 | |
| 596 /* What about phi nodes ? */ | |
| 597 itr = gsi_start_phis (bb); | |
| 598 | |
| 599 /* Clear aux field of incoming edges to a bb with a phi node. */ | |
| 600 if (!gsi_end_p (itr)) | |
| 601 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 602 e->aux = NULL; | |
| 603 | |
| 604 /* Check statements. */ | |
| 605 for (; !gsi_end_p (itr); gsi_next (&itr)) | |
| 606 if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr))) | |
| 607 return false; | |
| 608 | |
| 609 if (bb_with_exit_edge_p (loop, bb)) | |
| 610 exit_bb = bb; | |
| 611 } | |
| 612 | |
| 613 /* OK. Did not find any potential issues so go ahead in if-convert | |
| 614 this loop. Now there is no looking back. */ | |
| 615 if (dump_file) | |
| 616 fprintf (dump_file,"Applying if-conversion\n"); | |
| 617 | |
| 618 free_dominance_info (CDI_POST_DOMINATORS); | |
| 619 return true; | |
| 620 } | |
| 621 | |
| 622 /* Add condition COND into predicate list of basic block BB. */ | |
| 623 | |
| 624 static void | |
| 625 add_to_predicate_list (basic_block bb, tree new_cond) | |
| 626 { | |
| 627 tree cond = (tree) bb->aux; | |
| 628 | |
| 629 if (cond) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
630 cond = fold_build2_loc (EXPR_LOCATION (cond), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
631 TRUTH_OR_EXPR, boolean_type_node, |
| 0 | 632 unshare_expr (cond), new_cond); |
| 633 else | |
| 634 cond = new_cond; | |
| 635 | |
| 636 bb->aux = cond; | |
| 637 } | |
| 638 | |
| 639 /* Add condition COND into BB's predicate list. PREV_COND is | |
| 640 existing condition. */ | |
| 641 | |
| 642 static tree | |
| 643 add_to_dst_predicate_list (struct loop * loop, edge e, | |
| 644 tree prev_cond, tree cond, | |
| 645 gimple_stmt_iterator *gsi) | |
| 646 { | |
| 647 tree new_cond = NULL_TREE; | |
| 648 | |
| 649 if (!flow_bb_inside_loop_p (loop, e->dest)) | |
| 650 return NULL_TREE; | |
| 651 | |
| 652 if (prev_cond == boolean_true_node || !prev_cond) | |
| 653 new_cond = unshare_expr (cond); | |
| 654 else | |
| 655 { | |
| 656 tree tmp; | |
| 657 gimple tmp_stmt = NULL; | |
| 658 | |
| 659 prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond), | |
| 660 true, NULL, true, GSI_SAME_STMT); | |
| 661 | |
| 662 cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), | |
| 663 true, NULL, true, GSI_SAME_STMT); | |
| 664 | |
| 665 /* Add the condition to aux field of the edge. In case edge | |
| 666 destination is a PHI node, this condition will be ANDed with | |
| 667 block predicate to construct complete condition. */ | |
| 668 e->aux = cond; | |
| 669 | |
| 670 /* new_cond == prev_cond AND cond */ | |
| 671 tmp = build2 (TRUTH_AND_EXPR, boolean_type_node, | |
| 672 unshare_expr (prev_cond), cond); | |
| 673 tmp_stmt = ifc_temp_var (boolean_type_node, tmp); | |
| 674 gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT); | |
| 675 new_cond = gimple_assign_lhs (tmp_stmt); | |
| 676 } | |
| 677 add_to_predicate_list (e->dest, new_cond); | |
| 678 return new_cond; | |
| 679 } | |
| 680 | |
| 681 /* During if-conversion aux field from basic block structure is used to hold | |
| 682 predicate list. Clean each basic block's predicate list for the given LOOP. | |
| 683 Also clean aux field of successor edges, used to hold true and false | |
| 684 condition from conditional expression. */ | |
| 685 | |
| 686 static void | |
| 687 clean_predicate_lists (struct loop *loop) | |
| 688 { | |
| 689 basic_block *bb; | |
| 690 unsigned int i; | |
| 691 edge e; | |
| 692 edge_iterator ei; | |
| 693 | |
| 694 bb = get_loop_body (loop); | |
| 695 for (i = 0; i < loop->num_nodes; i++) | |
| 696 { | |
| 697 bb[i]->aux = NULL; | |
| 698 FOR_EACH_EDGE (e, ei, bb[i]->succs) | |
| 699 e->aux = NULL; | |
| 700 } | |
| 701 free (bb); | |
| 702 } | |
| 703 | |
| 704 /* Basic block BB has two predecessors. Using predecessor's aux field, set | |
| 705 appropriate condition COND for the PHI node replacement. Return true block | |
| 706 whose phi arguments are selected when cond is true. */ | |
| 707 | |
| 708 static basic_block | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
709 find_phi_replacement_condition (struct loop *loop, |
| 0 | 710 basic_block bb, tree *cond, |
| 711 gimple_stmt_iterator *gsi) | |
| 712 { | |
| 713 edge first_edge, second_edge; | |
| 714 tree tmp_cond; | |
| 715 | |
| 716 gcc_assert (EDGE_COUNT (bb->preds) == 2); | |
| 717 first_edge = EDGE_PRED (bb, 0); | |
| 718 second_edge = EDGE_PRED (bb, 1); | |
| 719 | |
| 720 /* Use condition based on following criteria: | |
| 721 1) | |
| 722 S1: x = !c ? a : b; | |
| 723 | |
| 724 S2: x = c ? b : a; | |
| 725 | |
| 726 S2 is preferred over S1. Make 'b' first_bb and use its condition. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
727 |
| 0 | 728 2) Do not make loop header first_bb. |
| 729 | |
| 730 3) | |
| 731 S1: x = !(c == d)? a : b; | |
| 732 | |
| 733 S21: t1 = c == d; | |
| 734 S22: x = t1 ? b : a; | |
| 735 | |
| 736 S3: x = (c == d) ? b : a; | |
| 737 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
738 S3 is preferred over S1 and S2*, Make 'b' first_bb and use |
| 0 | 739 its condition. |
| 740 | |
| 741 4) If pred B is dominated by pred A then use pred B's condition. | |
| 742 See PR23115. */ | |
| 743 | |
| 744 /* Select condition that is not TRUTH_NOT_EXPR. */ | |
| 745 tmp_cond = (tree) (first_edge->src)->aux; | |
| 746 gcc_assert (tmp_cond); | |
| 747 | |
| 748 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) | |
| 749 { | |
| 750 edge tmp_edge; | |
| 751 | |
| 752 tmp_edge = first_edge; | |
| 753 first_edge = second_edge; | |
| 754 second_edge = tmp_edge; | |
| 755 } | |
| 756 | |
| 757 /* Check if FIRST_BB is loop header or not and make sure that | |
| 758 FIRST_BB does not dominate SECOND_BB. */ | |
| 759 if (first_edge->src == loop->header | |
| 760 || dominated_by_p (CDI_DOMINATORS, | |
| 761 second_edge->src, first_edge->src)) | |
| 762 { | |
| 763 *cond = (tree) (second_edge->src)->aux; | |
| 764 | |
| 765 /* If there is a condition on an incoming edge, | |
| 766 AND it with the incoming bb predicate. */ | |
| 767 if (second_edge->aux) | |
| 768 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, | |
| 769 *cond, (tree) second_edge->aux); | |
| 770 | |
| 771 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) | |
| 772 /* We can be smart here and choose inverted | |
| 773 condition without switching bbs. */ | |
| 774 *cond = invert_truthvalue (*cond); | |
| 775 else | |
| 776 /* Select non loop header bb. */ | |
| 777 first_edge = second_edge; | |
| 778 } | |
| 779 else | |
| 780 { | |
| 781 /* FIRST_BB is not loop header */ | |
| 782 *cond = (tree) (first_edge->src)->aux; | |
| 783 | |
| 784 /* If there is a condition on an incoming edge, | |
| 785 AND it with the incoming bb predicate. */ | |
| 786 if (first_edge->aux) | |
| 787 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, | |
| 788 *cond, (tree) first_edge->aux); | |
| 789 } | |
| 790 | |
| 791 /* Create temp. for the condition. Vectorizer prefers to have gimple | |
| 792 value as condition. Various targets use different means to communicate | |
| 793 condition in vector compare operation. Using gimple value allows | |
| 794 compiler to emit vector compare and select RTL without exposing | |
| 795 compare's result. */ | |
| 796 *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond), | |
| 797 false, NULL_TREE, | |
| 798 true, GSI_SAME_STMT); | |
| 799 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) | |
| 800 { | |
| 801 gimple new_stmt; | |
| 802 | |
| 803 new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); | |
| 804 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); | |
| 805 *cond = gimple_assign_lhs (new_stmt); | |
| 806 } | |
| 807 | |
| 808 gcc_assert (*cond); | |
| 809 | |
| 810 return first_edge->src; | |
| 811 } | |
| 812 | |
| 813 | |
| 814 /* Replace PHI node with conditional modify expr using COND. | |
| 815 This routine does not handle PHI nodes with more than two arguments. | |
| 816 For example, | |
| 817 S1: A = PHI <x1(1), x2(5) | |
| 818 is converted into, | |
| 819 S2: A = cond ? x1 : x2; | |
| 820 S2 is inserted at the top of basic block's statement list. | |
| 821 When COND is true, phi arg from TRUE_BB is selected. | |
| 822 */ | |
| 823 | |
| 824 static void | |
| 825 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond, | |
| 826 basic_block true_bb, | |
| 827 gimple_stmt_iterator *gsi) | |
| 828 { | |
| 829 gimple new_stmt; | |
| 830 basic_block bb; | |
| 831 tree rhs; | |
| 832 tree arg_0, arg_1; | |
| 833 | |
| 834 gcc_assert (gimple_code (phi) == GIMPLE_PHI); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
835 |
| 0 | 836 /* If this is not filtered earlier, then now it is too late. */ |
| 837 gcc_assert (gimple_phi_num_args (phi) == 2); | |
| 838 | |
| 839 /* Find basic block and initialize iterator. */ | |
| 840 bb = gimple_bb (phi); | |
| 841 | |
| 842 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ | |
| 843 if (EDGE_PRED (bb, 1)->src == true_bb) | |
| 844 { | |
| 845 arg_0 = gimple_phi_arg_def (phi, 1); | |
| 846 arg_1 = gimple_phi_arg_def (phi, 0); | |
| 847 } | |
| 848 else | |
| 849 { | |
| 850 arg_0 = gimple_phi_arg_def (phi, 0); | |
| 851 arg_1 = gimple_phi_arg_def (phi, 1); | |
| 852 } | |
| 853 | |
| 854 /* Build new RHS using selected condition and arguments. */ | |
| 855 rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), | |
| 856 unshare_expr (cond), unshare_expr (arg_0), | |
| 857 unshare_expr (arg_1)); | |
| 858 | |
| 859 /* Create new GIMPLE_ASSIGN statement using RHS. */ | |
| 860 new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs); | |
| 861 | |
| 862 /* Make new statement definition of the original phi result. */ | |
| 863 SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt; | |
| 864 | |
| 865 /* Insert using iterator. */ | |
| 866 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); | |
| 867 update_stmt (new_stmt); | |
| 868 | |
| 869 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 870 { | |
| 871 fprintf (dump_file, "new phi replacement stmt\n"); | |
| 872 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); | |
| 873 } | |
| 874 } | |
| 875 | |
| 876 /* Process phi nodes for the given LOOP. Replace phi nodes with cond | |
| 877 modify expr. */ | |
| 878 | |
| 879 static void | |
| 880 process_phi_nodes (struct loop *loop) | |
| 881 { | |
| 882 basic_block bb; | |
| 883 unsigned int orig_loop_num_nodes = loop->num_nodes; | |
| 884 unsigned int i; | |
| 885 | |
| 886 /* Replace phi nodes with cond. modify expr. */ | |
| 887 for (i = 1; i < orig_loop_num_nodes; i++) | |
| 888 { | |
| 889 gimple phi; | |
| 890 tree cond = NULL_TREE; | |
| 891 gimple_stmt_iterator gsi, phi_gsi; | |
| 892 basic_block true_bb = NULL; | |
| 893 bb = ifc_bbs[i]; | |
| 894 | |
| 895 if (bb == loop->header) | |
| 896 continue; | |
| 897 | |
| 898 phi_gsi = gsi_start_phis (bb); | |
| 899 gsi = gsi_after_labels (bb); | |
| 900 | |
| 901 /* BB has two predecessors. Using predecessor's aux field, set | |
| 902 appropriate condition for the PHI node replacement. */ | |
| 903 if (!gsi_end_p (phi_gsi)) | |
| 904 true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi); | |
| 905 | |
| 906 while (!gsi_end_p (phi_gsi)) | |
| 907 { | |
| 908 phi = gsi_stmt (phi_gsi); | |
| 909 replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi); | |
| 910 release_phi_node (phi); | |
| 911 gsi_next (&phi_gsi); | |
| 912 } | |
| 913 set_phi_nodes (bb, NULL); | |
| 914 } | |
| 915 return; | |
| 916 } | |
| 917 | |
| 918 /* Combine all basic block from the given LOOP into one or two super | |
| 919 basic block. Replace PHI nodes with conditional modify expression. */ | |
| 920 | |
| 921 static void | |
| 922 combine_blocks (struct loop *loop) | |
| 923 { | |
| 924 basic_block bb, exit_bb, merge_target_bb; | |
| 925 unsigned int orig_loop_num_nodes = loop->num_nodes; | |
| 926 unsigned int i; | |
| 927 edge e; | |
| 928 edge_iterator ei; | |
| 929 | |
| 930 /* Process phi nodes to prepare blocks for merge. */ | |
| 931 process_phi_nodes (loop); | |
| 932 | |
| 933 /* Merge basic blocks. First remove all the edges in the loop, except | |
| 934 for those from the exit block. */ | |
| 935 exit_bb = NULL; | |
| 936 for (i = 0; i < orig_loop_num_nodes; i++) | |
| 937 { | |
| 938 bb = ifc_bbs[i]; | |
| 939 if (bb_with_exit_edge_p (loop, bb)) | |
| 940 { | |
| 941 exit_bb = bb; | |
| 942 break; | |
| 943 } | |
| 944 } | |
| 945 gcc_assert (exit_bb != loop->latch); | |
| 946 | |
| 947 for (i = 1; i < orig_loop_num_nodes; i++) | |
| 948 { | |
| 949 bb = ifc_bbs[i]; | |
| 950 | |
| 951 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) | |
| 952 { | |
| 953 if (e->src == exit_bb) | |
| 954 ei_next (&ei); | |
| 955 else | |
| 956 remove_edge (e); | |
| 957 } | |
| 958 } | |
| 959 | |
| 960 if (exit_bb != NULL) | |
| 961 { | |
| 962 if (exit_bb != loop->header) | |
| 963 { | |
| 964 /* Connect this node with loop header. */ | |
| 965 make_edge (loop->header, exit_bb, EDGE_FALLTHRU); | |
| 966 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); | |
| 967 } | |
| 968 | |
| 969 /* Redirect non-exit edges to loop->latch. */ | |
| 970 FOR_EACH_EDGE (e, ei, exit_bb->succs) | |
| 971 { | |
| 972 if (!loop_exit_edge_p (loop, e)) | |
| 973 redirect_edge_and_branch (e, loop->latch); | |
| 974 } | |
| 975 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); | |
| 976 } | |
| 977 else | |
| 978 { | |
| 979 /* If the loop does not have exit then reconnect header and latch. */ | |
| 980 make_edge (loop->header, loop->latch, EDGE_FALLTHRU); | |
| 981 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); | |
| 982 } | |
| 983 | |
| 984 merge_target_bb = loop->header; | |
| 985 for (i = 1; i < orig_loop_num_nodes; i++) | |
| 986 { | |
| 987 gimple_stmt_iterator gsi; | |
| 988 gimple_stmt_iterator last; | |
| 989 | |
| 990 bb = ifc_bbs[i]; | |
| 991 | |
| 992 if (bb == exit_bb || bb == loop->latch) | |
| 993 continue; | |
| 994 | |
| 995 /* Remove labels and make stmts member of loop->header. */ | |
| 996 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) | |
| 997 { | |
| 998 if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL) | |
| 999 gsi_remove (&gsi, true); | |
| 1000 else | |
| 1001 { | |
| 1002 gimple_set_bb (gsi_stmt (gsi), merge_target_bb); | |
| 1003 gsi_next (&gsi); | |
| 1004 } | |
| 1005 } | |
| 1006 | |
| 1007 /* Update stmt list. */ | |
| 1008 last = gsi_last_bb (merge_target_bb); | |
| 1009 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT); | |
| 1010 set_bb_seq (bb, NULL); | |
| 1011 | |
| 1012 delete_basic_block (bb); | |
| 1013 } | |
| 1014 | |
| 1015 /* Now if possible, merge loop header and block with exit edge. | |
| 1016 This reduces number of basic blocks to 2. Auto vectorizer addresses | |
| 1017 loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */ | |
| 1018 if (exit_bb | |
| 1019 && exit_bb != loop->header | |
| 1020 && can_merge_blocks_p (loop->header, exit_bb)) | |
| 1021 merge_blocks (loop->header, exit_bb); | |
| 1022 } | |
| 1023 | |
| 1024 /* Make a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP | |
| 1025 to the new variable. */ | |
| 1026 | |
| 1027 static gimple | |
| 1028 ifc_temp_var (tree type, tree exp) | |
| 1029 { | |
| 1030 const char *name = "_ifc_"; | |
| 1031 tree var, new_name; | |
| 1032 gimple stmt; | |
| 1033 | |
| 1034 /* Create new temporary variable. */ | |
| 1035 var = create_tmp_var (type, name); | |
| 1036 add_referenced_var (var); | |
| 1037 | |
| 1038 /* Build new statement to assign EXP to new variable. */ | |
| 1039 stmt = gimple_build_assign (var, exp); | |
| 1040 | |
| 1041 /* Get SSA name for the new variable and set make new statement | |
| 1042 its definition statement. */ | |
| 1043 new_name = make_ssa_name (var, stmt); | |
| 1044 gimple_assign_set_lhs (stmt, new_name); | |
| 1045 SSA_NAME_DEF_STMT (new_name) = stmt; | |
| 1046 update_stmt (stmt); | |
| 1047 | |
| 1048 return stmt; | |
| 1049 } | |
| 1050 | |
| 1051 | |
| 1052 /* Return TRUE iff, all pred blocks of BB are visited. | |
| 1053 Bitmap VISITED keeps history of visited blocks. */ | |
| 1054 | |
| 1055 static bool | |
| 1056 pred_blocks_visited_p (basic_block bb, bitmap *visited) | |
| 1057 { | |
| 1058 edge e; | |
| 1059 edge_iterator ei; | |
| 1060 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 1061 if (!bitmap_bit_p (*visited, e->src->index)) | |
| 1062 return false; | |
| 1063 | |
| 1064 return true; | |
| 1065 } | |
| 1066 | |
| 1067 /* Get body of a LOOP in suitable order for if-conversion. | |
| 1068 It is caller's responsibility to deallocate basic block | |
| 1069 list. If-conversion suitable order is, BFS order with one | |
| 1070 additional constraint. Select block in BFS block, if all | |
| 1071 pred are already selected. */ | |
| 1072 | |
| 1073 static basic_block * | |
| 1074 get_loop_body_in_if_conv_order (const struct loop *loop) | |
| 1075 { | |
| 1076 basic_block *blocks, *blocks_in_bfs_order; | |
| 1077 basic_block bb; | |
| 1078 bitmap visited; | |
| 1079 unsigned int index = 0; | |
| 1080 unsigned int visited_count = 0; | |
| 1081 | |
| 1082 gcc_assert (loop->num_nodes); | |
| 1083 gcc_assert (loop->latch != EXIT_BLOCK_PTR); | |
| 1084 | |
| 1085 blocks = XCNEWVEC (basic_block, loop->num_nodes); | |
| 1086 visited = BITMAP_ALLOC (NULL); | |
| 1087 | |
| 1088 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); | |
| 1089 | |
| 1090 index = 0; | |
| 1091 while (index < loop->num_nodes) | |
| 1092 { | |
| 1093 bb = blocks_in_bfs_order [index]; | |
| 1094 | |
| 1095 if (bb->flags & BB_IRREDUCIBLE_LOOP) | |
| 1096 { | |
| 1097 free (blocks_in_bfs_order); | |
| 1098 BITMAP_FREE (visited); | |
| 1099 free (blocks); | |
| 1100 return NULL; | |
| 1101 } | |
| 1102 if (!bitmap_bit_p (visited, bb->index)) | |
| 1103 { | |
| 1104 if (pred_blocks_visited_p (bb, &visited) | |
| 1105 || bb == loop->header) | |
| 1106 { | |
| 1107 /* This block is now visited. */ | |
| 1108 bitmap_set_bit (visited, bb->index); | |
| 1109 blocks[visited_count++] = bb; | |
| 1110 } | |
| 1111 } | |
| 1112 index++; | |
| 1113 if (index == loop->num_nodes | |
| 1114 && visited_count != loop->num_nodes) | |
| 1115 { | |
| 1116 /* Not done yet. */ | |
| 1117 index = 0; | |
| 1118 } | |
| 1119 } | |
| 1120 free (blocks_in_bfs_order); | |
| 1121 BITMAP_FREE (visited); | |
| 1122 return blocks; | |
| 1123 } | |
| 1124 | |
| 1125 /* Return true if one of the basic block BB edge is exit of LOOP. */ | |
| 1126 | |
| 1127 static bool | |
| 1128 bb_with_exit_edge_p (struct loop *loop, basic_block bb) | |
| 1129 { | |
| 1130 edge e; | |
| 1131 edge_iterator ei; | |
| 1132 bool exit_edge_found = false; | |
| 1133 | |
| 1134 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 1135 if (loop_exit_edge_p (loop, e)) | |
| 1136 { | |
| 1137 exit_edge_found = true; | |
| 1138 break; | |
| 1139 } | |
| 1140 | |
| 1141 return exit_edge_found; | |
| 1142 } | |
| 1143 | |
| 1144 /* Tree if-conversion pass management. */ | |
| 1145 | |
| 1146 static unsigned int | |
| 1147 main_tree_if_conversion (void) | |
| 1148 { | |
| 1149 loop_iterator li; | |
| 1150 struct loop *loop; | |
| 1151 | |
| 1152 if (number_of_loops () <= 1) | |
| 1153 return 0; | |
| 1154 | |
| 1155 FOR_EACH_LOOP (li, loop, 0) | |
| 1156 { | |
| 1157 tree_if_conversion (loop, true); | |
| 1158 } | |
| 1159 return 0; | |
| 1160 } | |
| 1161 | |
| 1162 static bool | |
| 1163 gate_tree_if_conversion (void) | |
| 1164 { | |
| 1165 return flag_tree_vectorize != 0; | |
| 1166 } | |
| 1167 | |
| 1168 struct gimple_opt_pass pass_if_conversion = | |
| 1169 { | |
| 1170 { | |
| 1171 GIMPLE_PASS, | |
| 1172 "ifcvt", /* name */ | |
| 1173 gate_tree_if_conversion, /* gate */ | |
| 1174 main_tree_if_conversion, /* execute */ | |
| 1175 NULL, /* sub */ | |
| 1176 NULL, /* next */ | |
| 1177 0, /* static_pass_number */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1178 TV_NONE, /* tv_id */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1179 PROP_cfg | PROP_ssa, /* properties_required */ |
| 0 | 1180 0, /* properties_provided */ |
| 1181 0, /* properties_destroyed */ | |
| 1182 0, /* todo_flags_start */ | |
| 1183 TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow | |
| 1184 /* todo_flags_finish */ | |
| 1185 } | |
| 1186 }; |