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