]>
Commit | Line | Data |
---|---|---|
40923b20 DP |
1 | /* If-conversion for vectorizer. |
2 | Copyright (C) 2004 Free Software Foundation, Inc. | |
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 | ||
27 | o Decide if a loop is if-convertable 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) | |
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 DP |
110 | block_stmt_iterator *); |
111 | static bool if_convertable_phi_p (struct loop *, basic_block, tree); | |
112 | static bool if_convertable_modify_expr_p (struct loop *, basic_block, tree); | |
113 | static bool if_convertable_stmt_p (struct loop *, basic_block, tree); | |
114 | static bool if_convertable_bb_p (struct loop *, basic_block, bool); | |
115 | static bool if_convertable_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, tree, tree, tree, | |
118 | block_stmt_iterator *); | |
119 | static void clean_predicate_lists (struct loop *loop); | |
7f7e0703 DP |
120 | static basic_block find_phi_replacement_condition (basic_block, tree *, |
121 | block_stmt_iterator *); | |
122 | static void replace_phi_with_cond_modify_expr (tree, tree, basic_block, | |
40923b20 DP |
123 | block_stmt_iterator *); |
124 | static void process_phi_nodes (struct loop *); | |
125 | static void combine_blocks (struct loop *); | |
126 | static tree ifc_temp_var (tree, tree); | |
127 | static bool pred_blocks_visited_p (basic_block, bitmap *); | |
128 | static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop); | |
129 | static bool bb_with_exit_edge_p (basic_block); | |
130 | ||
131 | /* List of basic blocks in if-conversion-suitable order. */ | |
132 | static basic_block *ifc_bbs; | |
133 | ||
134 | /* Main entry point. | |
135 | Apply if-conversion to the LOOP. Return true if successful otherwise return | |
61b5f210 | 136 | false. If false is returned then loop remains unchanged. |
40923b20 DP |
137 | FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used |
138 | for vectorizer or not. If it is used for vectorizer, additional checks are | |
61b5f210 | 139 | used. (Vectorization checks are not yet implemented). */ |
40923b20 DP |
140 | |
141 | bool | |
142 | tree_if_conversion (struct loop *loop, bool for_vectorizer) | |
143 | { | |
144 | basic_block bb; | |
145 | block_stmt_iterator itr; | |
146 | tree cond; | |
147 | unsigned int i; | |
148 | ||
149 | ifc_bbs = NULL; | |
150 | ||
151 | /* if-conversion is not appropriate for all loops. First, check if loop is | |
152 | if-convertable or not. */ | |
153 | if (!if_convertable_loop_p (loop, for_vectorizer)) | |
154 | { | |
155 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
156 | fprintf (dump_file,"-------------------------\n"); | |
157 | if (ifc_bbs) | |
158 | { | |
159 | free (ifc_bbs); | |
160 | ifc_bbs = NULL; | |
161 | } | |
162 | free_dominance_info (CDI_POST_DOMINATORS); | |
163 | free_df (); | |
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 DP |
189 | unconditional goto. */ |
190 | if (bb->succ && !bb->succ->succ_next) | |
191 | { | |
192 | basic_block bb_n = bb->succ->dest; | |
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; | |
208 | free_df (); | |
209 | ||
210 | return true; | |
211 | } | |
212 | ||
61b5f210 AJ |
213 | /* if-convert stmt T which is part of LOOP. |
214 | If T is a MODIFY_EXPR than it is converted into conditional modify | |
215 | expression using COND. For conditional expressions, add condition in the | |
216 | destination basic block's predicate list and remove conditional | |
217 | expression itself. BSI is the iterator used to traverse statements of | |
40923b20 DP |
218 | loop. It is used here when it is required to delete current statement. */ |
219 | ||
220 | static tree | |
61b5f210 | 221 | tree_if_convert_stmt (struct loop * loop, tree t, tree cond, |
40923b20 DP |
222 | block_stmt_iterator *bsi) |
223 | { | |
224 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
225 | { | |
226 | fprintf (dump_file, "------if-convert stmt\n"); | |
227 | print_generic_stmt (dump_file, t, TDF_SLIM); | |
228 | print_generic_stmt (dump_file, cond, TDF_SLIM); | |
229 | } | |
230 | ||
231 | switch (TREE_CODE (t)) | |
232 | { | |
233 | /* Labels are harmless here. */ | |
234 | case LABEL_EXPR: | |
235 | break; | |
236 | ||
237 | case MODIFY_EXPR: | |
238 | /* This modify_expr is killing previous value of LHS. Appropriate value will | |
239 | be selected by PHI node based on condition. It is possible that before | |
240 | this transformation, PHI nodes was selecting default value and now it will | |
61b5f210 | 241 | use this new value. This is OK because it does not change validity the |
40923b20 DP |
242 | program. */ |
243 | break; | |
244 | ||
245 | case GOTO_EXPR: | |
246 | /* Unconditional goto */ | |
247 | add_to_predicate_list (bb_for_stmt (TREE_OPERAND (t, 1)), cond); | |
248 | bsi_remove (bsi); | |
249 | cond = NULL_TREE; | |
250 | break; | |
251 | ||
252 | case COND_EXPR: | |
253 | /* Update destination blocks' predicate list and remove this | |
254 | condition expression. */ | |
255 | tree_if_convert_cond_expr (loop, t, cond, bsi); | |
61b5f210 | 256 | cond = NULL_TREE; |
40923b20 | 257 | break; |
61b5f210 AJ |
258 | |
259 | default: | |
1e128c5f | 260 | gcc_unreachable (); |
40923b20 DP |
261 | } |
262 | return cond; | |
263 | } | |
264 | ||
265 | /* STMT is COND_EXPR. Update two destination's predicate list. | |
266 | Remove COND_EXPR, if it is not the loop exit condition. Otherwise | |
61b5f210 | 267 | update loop exit condition appropriately. BSI is the iterator |
40923b20 DP |
268 | used to traverse statement list. STMT is part of loop LOOP. */ |
269 | ||
270 | static void | |
61b5f210 | 271 | tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond, |
40923b20 DP |
272 | block_stmt_iterator *bsi) |
273 | { | |
274 | tree then_clause, else_clause, c, new_cond; | |
275 | new_cond = NULL_TREE; | |
276 | ||
1e128c5f | 277 | gcc_assert (TREE_CODE (stmt) == COND_EXPR); |
40923b20 DP |
278 | |
279 | c = TREE_OPERAND (stmt, 0); | |
280 | then_clause = TREE_OPERAND (stmt, 1); | |
281 | else_clause = TREE_OPERAND (stmt, 2); | |
61b5f210 | 282 | |
40923b20 DP |
283 | /* Create temp. for condition. */ |
284 | if (!is_gimple_reg (c)) | |
285 | { | |
286 | tree new_stmt; | |
287 | new_stmt = ifc_temp_var (TREE_TYPE (c), unshare_expr (c)); | |
288 | bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); | |
289 | c = TREE_OPERAND (new_stmt, 0); | |
290 | } | |
61b5f210 | 291 | |
40923b20 DP |
292 | /* Add new condition into destination's predicate list. */ |
293 | if (then_clause) | |
294 | /* if 'c' is true then then_clause is reached. */ | |
295 | new_cond = add_to_dst_predicate_list (loop, then_clause, cond, c, bsi); | |
61b5f210 | 296 | |
40923b20 DP |
297 | if (else_clause) |
298 | { | |
299 | /* if 'c' is false then else_clause is reached. */ | |
61b5f210 AJ |
300 | tree c2 = build1 (TRUTH_NOT_EXPR, |
301 | boolean_type_node, | |
40923b20 DP |
302 | unshare_expr (c)); |
303 | add_to_dst_predicate_list (loop, else_clause, cond, c2, bsi); | |
304 | } | |
305 | ||
61b5f210 | 306 | /* Now this conditional statement is redundant. Remove it. |
40923b20 DP |
307 | But, do not remove exit condition! Update exit condition |
308 | using new condition. */ | |
309 | if (!bb_with_exit_edge_p (bb_for_stmt (stmt))) | |
310 | { | |
311 | bsi_remove (bsi); | |
312 | cond = NULL_TREE; | |
313 | } | |
314 | else if (new_cond != NULL_TREE) | |
315 | { | |
316 | TREE_OPERAND (stmt, 0) = new_cond; | |
317 | modify_stmt (stmt); | |
318 | } | |
319 | return; | |
320 | } | |
321 | ||
322 | /* Return true, iff PHI is if-convertable. PHI is part of loop LOOP | |
323 | and it belongs to basic block BB. | |
61b5f210 | 324 | PHI is not if-convertable |
40923b20 DP |
325 | - if it has more than 2 arguments. |
326 | - Virtual PHI is immediately used in another PHI node. */ | |
327 | ||
328 | static bool | |
329 | if_convertable_phi_p (struct loop *loop, basic_block bb, tree phi) | |
330 | { | |
331 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
332 | { | |
333 | fprintf (dump_file, "-------------------------\n"); | |
334 | print_generic_stmt (dump_file, phi, TDF_SLIM); | |
335 | } | |
61b5f210 | 336 | |
40923b20 DP |
337 | if (bb != loop->header && PHI_NUM_ARGS (phi) != 2) |
338 | { | |
339 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
340 | fprintf (dump_file, "More than two phi node args.\n"); | |
341 | return false; | |
342 | } | |
61b5f210 | 343 | |
40923b20 DP |
344 | if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) |
345 | { | |
346 | int j; | |
347 | dataflow_t df = get_immediate_uses (phi); | |
348 | int num_uses = num_immediate_uses (df); | |
349 | for (j = 0; j < num_uses; j++) | |
350 | { | |
351 | tree use = immediate_use (df, j); | |
352 | if (TREE_CODE (use) == PHI_NODE) | |
353 | { | |
354 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
355 | fprintf (dump_file, "Difficult to handle this virtual phi.\n"); | |
356 | return false; | |
357 | } | |
358 | } | |
359 | } | |
360 | ||
361 | return true; | |
362 | } | |
363 | ||
61b5f210 | 364 | /* Return true, if M_EXPR is if-convertable. |
40923b20 DP |
365 | MODIFY_EXPR is not if-convertable if, |
366 | - It is not movable. | |
367 | - It could trap. | |
368 | - LHS is not var decl. | |
369 | MODIFY_EXPR is part of block BB, which is inside loop LOOP. | |
370 | */ | |
371 | ||
372 | static bool | |
373 | if_convertable_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr) | |
374 | { | |
375 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
376 | { | |
377 | fprintf (dump_file, "-------------------------\n"); | |
378 | print_generic_stmt (dump_file, m_expr, TDF_SLIM); | |
379 | } | |
61b5f210 | 380 | |
40923b20 DP |
381 | /* Be conservative and do not handle immovable expressions. */ |
382 | if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE) | |
383 | { | |
384 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
385 | fprintf (dump_file, "stmt is movable. Don't take risk\n"); | |
386 | return false; | |
387 | } | |
388 | ||
389 | /* See if it needs speculative loading or not. */ | |
61b5f210 | 390 | if (bb != loop->header |
40923b20 DP |
391 | && tree_could_trap_p (TREE_OPERAND (m_expr, 1))) |
392 | { | |
393 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
394 | fprintf (dump_file, "tree could trap...\n"); | |
395 | return false; | |
396 | } | |
397 | ||
398 | if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR) | |
399 | { | |
400 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
401 | fprintf (dump_file, "CALL_EXPR \n"); | |
402 | return false; | |
403 | } | |
404 | ||
405 | if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME | |
406 | && bb != loop->header | |
407 | && !bb_with_exit_edge_p (bb)) | |
408 | { | |
409 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
410 | { | |
411 | fprintf (dump_file, "LHS is not var\n"); | |
412 | print_generic_stmt (dump_file, m_expr, TDF_SLIM); | |
413 | } | |
414 | return false; | |
415 | } | |
416 | ||
417 | ||
418 | return true; | |
419 | } | |
420 | ||
61b5f210 | 421 | /* Return true, iff STMT is if-convertable. |
40923b20 | 422 | Statement is if-convertable if, |
61b5f210 AJ |
423 | - It is if-convertable MODIFY_EXPR |
424 | - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR. | |
40923b20 DP |
425 | STMT is inside block BB, which is inside loop LOOP. */ |
426 | ||
427 | static bool | |
428 | if_convertable_stmt_p (struct loop *loop, basic_block bb, tree stmt) | |
429 | { | |
430 | switch (TREE_CODE (stmt)) | |
431 | { | |
432 | case LABEL_EXPR: | |
433 | break; | |
61b5f210 | 434 | |
40923b20 | 435 | case MODIFY_EXPR: |
61b5f210 | 436 | |
40923b20 DP |
437 | if (!if_convertable_modify_expr_p (loop, bb, stmt)) |
438 | return false; | |
439 | break; | |
61b5f210 | 440 | |
40923b20 DP |
441 | case GOTO_EXPR: |
442 | case COND_EXPR: | |
443 | break; | |
61b5f210 | 444 | |
40923b20 DP |
445 | default: |
446 | /* Don't know what to do with 'em so don't do anything. */ | |
447 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
448 | { | |
449 | fprintf (dump_file, "don't know what to do\n"); | |
450 | print_generic_stmt (dump_file, stmt, TDF_SLIM); | |
451 | } | |
452 | return false; | |
453 | break; | |
454 | } | |
455 | ||
456 | return true; | |
457 | } | |
458 | ||
61b5f210 | 459 | /* Return true, iff BB is if-convertable. |
40923b20 | 460 | Note: This routine does _not_ check basic block statements and phis. |
61b5f210 AJ |
461 | Basic block is not if-convertable if, |
462 | - Basic block is non-empty and it is after exit block (in BFS order). | |
40923b20 | 463 | - Basic block is after exit block but before latch. |
61b5f210 | 464 | - Basic block edge(s) is not normal. |
40923b20 | 465 | EXIT_BB_SEEN is true if basic block with exit edge is already seen. |
8c27b7d4 | 466 | BB is inside loop LOOP. */ |
40923b20 | 467 | |
61b5f210 | 468 | static bool |
40923b20 DP |
469 | if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen) |
470 | { | |
471 | edge e; | |
472 | ||
473 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
474 | fprintf (dump_file, "----------[%d]-------------\n", bb->index); | |
61b5f210 | 475 | |
40923b20 DP |
476 | if (exit_bb_seen) |
477 | { | |
478 | if (bb != loop->latch) | |
479 | { | |
480 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
481 | fprintf (dump_file, "basic block after exit bb but before latch\n"); | |
482 | return false; | |
483 | } | |
484 | else if (!empty_block_p (bb)) | |
485 | { | |
486 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
487 | fprintf (dump_file, "non empty basic block after exit bb\n"); | |
488 | return false; | |
489 | } | |
490 | } | |
61b5f210 AJ |
491 | |
492 | /* Be less adventurous and handle only normal edges. */ | |
40923b20 | 493 | for (e = bb->succ; e; e = e->succ_next) |
61b5f210 | 494 | if (e->flags & |
40923b20 DP |
495 | (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) |
496 | { | |
497 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
498 | fprintf (dump_file,"Difficult to handle edges\n"); | |
499 | return false; | |
500 | } | |
501 | ||
502 | return true; | |
503 | } | |
504 | ||
61b5f210 | 505 | /* Return true, iff LOOP is if-convertable. |
40923b20 DP |
506 | LOOP is if-convertable if, |
507 | - It is innermost. | |
508 | - It has two or more basic blocks. | |
509 | - It has only one exit. | |
61b5f210 AJ |
510 | - Loop header is not the exit edge. |
511 | - If its basic blocks and phi nodes are if convertable. See above for | |
512 | more info. | |
40923b20 DP |
513 | FOR_VECTORIZER enables vectorizer specific checks. For example, support |
514 | for vector conditions, data dependency checks etc.. (Not implemented yet). */ | |
515 | ||
516 | static bool | |
517 | if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) | |
518 | { | |
519 | tree phi; | |
520 | basic_block bb; | |
521 | block_stmt_iterator itr; | |
522 | unsigned int i; | |
523 | edge e; | |
524 | bool exit_bb_seen = false; | |
525 | ||
526 | /* Handle only inner most loop. */ | |
527 | if (!loop || loop->inner) | |
528 | { | |
529 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
530 | fprintf (dump_file, "not inner most loop\n"); | |
531 | return false; | |
532 | } | |
61b5f210 | 533 | |
40923b20 DP |
534 | flow_loop_scan (loop, LOOP_ALL); |
535 | ||
536 | /* If only one block, no need for if-conversion. */ | |
537 | if (loop->num_nodes <= 2) | |
538 | { | |
539 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
61b5f210 | 540 | fprintf (dump_file, "less than 2 basic blocks\n"); |
40923b20 DP |
541 | return false; |
542 | } | |
61b5f210 | 543 | |
40923b20 DP |
544 | /* More than one loop exit is too much to handle. */ |
545 | if (loop->num_exits > 1) | |
546 | { | |
547 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
548 | fprintf (dump_file, "multiple exits\n"); | |
549 | return false; | |
550 | } | |
551 | ||
552 | /* ??? Check target's vector conditional operation support for vectorizer. */ | |
553 | ||
554 | /* If one of the loop header's edge is exit edge then do not apply | |
555 | if-conversion. */ | |
556 | for (e = loop->header->succ; e; e = e->succ_next) | |
557 | if ( e->flags & EDGE_LOOP_EXIT) | |
558 | return false; | |
559 | ||
560 | compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL); | |
561 | ||
562 | calculate_dominance_info (CDI_DOMINATORS); | |
563 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
564 | ||
565 | /* Allow statements that can be handled during if-conversion. */ | |
566 | ifc_bbs = get_loop_body_in_if_conv_order (loop); | |
567 | if (!ifc_bbs) | |
568 | { | |
569 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
570 | fprintf (dump_file,"Irreducible loop\n"); | |
571 | free_dominance_info (CDI_POST_DOMINATORS); | |
572 | return false; | |
573 | } | |
61b5f210 | 574 | |
40923b20 DP |
575 | for (i = 0; i < loop->num_nodes; i++) |
576 | { | |
577 | bb = ifc_bbs[i]; | |
578 | ||
579 | if (!if_convertable_bb_p (loop, bb, exit_bb_seen)) | |
580 | return false; | |
581 | ||
582 | /* Check statements. */ | |
583 | for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr)) | |
584 | if (!if_convertable_stmt_p (loop, bb, bsi_stmt (itr))) | |
585 | return false; | |
586 | /* ??? Check data dependency for vectorizer. */ | |
587 | ||
588 | /* What about phi nodes ? */ | |
589 | for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) | |
590 | if (!if_convertable_phi_p (loop, bb, phi)) | |
591 | return false; | |
592 | ||
593 | if (bb_with_exit_edge_p (bb)) | |
594 | exit_bb_seen = true; | |
595 | } | |
596 | ||
597 | /* OK. Did not find any potential issues so go ahead in if-convert | |
598 | this loop. Now there is no looking back. */ | |
599 | if (dump_file) | |
600 | fprintf (dump_file,"Applying if-conversion\n"); | |
601 | ||
602 | free_dominance_info (CDI_POST_DOMINATORS); | |
603 | return true; | |
604 | } | |
605 | ||
606 | /* Add condition COND into predicate list of basic block BB. */ | |
607 | ||
608 | static void | |
609 | add_to_predicate_list (basic_block bb, tree new_cond) | |
610 | { | |
611 | tree cond = bb->aux; | |
61b5f210 | 612 | |
40923b20 DP |
613 | if (cond) |
614 | cond = fold (build (TRUTH_OR_EXPR, boolean_type_node, | |
615 | unshare_expr (cond), new_cond)); | |
616 | else | |
617 | cond = new_cond; | |
618 | ||
619 | bb->aux = cond; | |
620 | } | |
621 | ||
622 | /* Add condition COND into DST's predicate list. PREV_COND is | |
623 | existing condition. */ | |
624 | ||
625 | static tree | |
61b5f210 | 626 | add_to_dst_predicate_list (struct loop * loop, tree dst, |
40923b20 DP |
627 | tree prev_cond, tree cond, |
628 | block_stmt_iterator *bsi) | |
629 | { | |
630 | basic_block bb; | |
631 | tree new_cond = NULL_TREE; | |
632 | ||
1e128c5f | 633 | gcc_assert (TREE_CODE (dst) == GOTO_EXPR); |
40923b20 DP |
634 | bb = label_to_block (TREE_OPERAND (dst, 0)); |
635 | if (!flow_bb_inside_loop_p (loop, bb)) | |
636 | return NULL_TREE; | |
637 | ||
638 | if (prev_cond == boolean_true_node || !prev_cond) | |
639 | new_cond = unshare_expr (cond); | |
640 | else | |
641 | { | |
642 | tree tmp_stmt; | |
643 | /* new_cond == prev_cond AND cond */ | |
644 | tree tmp = build (TRUTH_AND_EXPR, boolean_type_node, | |
645 | unshare_expr (prev_cond), cond); | |
646 | tmp_stmt = ifc_temp_var (boolean_type_node, tmp); | |
647 | bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT); | |
648 | new_cond = TREE_OPERAND (tmp_stmt, 0); | |
649 | } | |
650 | add_to_predicate_list (bb, new_cond); | |
651 | return new_cond; | |
652 | } | |
653 | ||
654 | /* During if-conversion aux field from basic block is used to hold predicate | |
655 | list. Clean each basic block's predicate list for the given LOOP. */ | |
656 | ||
657 | static void | |
658 | clean_predicate_lists (struct loop *loop) | |
659 | { | |
660 | unsigned int i; | |
661 | ||
662 | for (i = 0; i < loop->num_nodes; i++) | |
663 | ifc_bbs[i]->aux = NULL; | |
664 | } | |
665 | ||
666 | /* Basic block BB has two predecessors. Using predecessor's aux field, set | |
7f7e0703 DP |
667 | appropriate condition COND for the PHI node replacement. Return true block |
668 | whose phi arguments are selected when cond is true. */ | |
40923b20 | 669 | |
7f7e0703 | 670 | static basic_block |
40923b20 DP |
671 | find_phi_replacement_condition (basic_block bb, tree *cond, |
672 | block_stmt_iterator *bsi) | |
673 | { | |
674 | edge e; | |
675 | basic_block p1 = NULL; | |
676 | basic_block p2 = NULL; | |
7f7e0703 | 677 | basic_block true_bb = NULL; |
40923b20 DP |
678 | tree tmp_cond; |
679 | ||
680 | for (e = bb->pred; e; e = e->pred_next) | |
681 | { | |
682 | if (p1 == NULL) | |
683 | p1 = e->src; | |
1e128c5f GB |
684 | else |
685 | { | |
686 | gcc_assert (!p2); | |
687 | p2 = e->src; | |
688 | } | |
40923b20 DP |
689 | } |
690 | ||
691 | /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ | |
692 | tmp_cond = p1->aux; | |
693 | if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) | |
694 | { | |
695 | *cond = p2->aux; | |
7f7e0703 | 696 | true_bb = p2; |
40923b20 DP |
697 | } |
698 | else | |
699 | { | |
700 | *cond = p1->aux; | |
7f7e0703 | 701 | true_bb = p1; |
40923b20 | 702 | } |
61b5f210 AJ |
703 | |
704 | /* Create temp. for the condition. Vectorizer prefers to have gimple | |
705 | value as condition. Various targets use different means to communicate | |
706 | condition in vector compare operation. Using gimple value allows compiler | |
40923b20 DP |
707 | to emit vector compare and select RTL without exposing compare's result. */ |
708 | if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) | |
709 | { | |
710 | tree new_stmt; | |
711 | ||
712 | new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); | |
713 | bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT); | |
714 | bsi_next (bsi); | |
715 | *cond = TREE_OPERAND (new_stmt, 0); | |
716 | } | |
717 | ||
1e128c5f | 718 | gcc_assert (*cond); |
40923b20 | 719 | |
7f7e0703 | 720 | return true_bb; |
40923b20 DP |
721 | } |
722 | ||
723 | ||
61b5f210 AJ |
724 | /* Replace PHI node with conditional modify expr using COND. |
725 | This routine does not handle PHI nodes with more than two arguments. | |
40923b20 DP |
726 | For example, |
727 | S1: A = PHI <x1(1), x2(5) | |
728 | is converted into, | |
729 | S2: A = cond ? x1 : x2; | |
730 | S2 is inserted at the top of basic block's statement list. | |
7f7e0703 | 731 | When COND is true, phi arg from TRUE_BB is selected. |
40923b20 DP |
732 | */ |
733 | ||
734 | static void | |
7f7e0703 | 735 | replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb, |
40923b20 DP |
736 | block_stmt_iterator *bsi) |
737 | { | |
738 | tree new_stmt; | |
739 | basic_block bb; | |
740 | tree rhs; | |
741 | tree arg_0, arg_1; | |
40923b20 | 742 | |
1e128c5f GB |
743 | gcc_assert (TREE_CODE (phi) == PHI_NODE); |
744 | ||
40923b20 | 745 | /* If this is not filtered earlier, then now it is too late. */ |
1e128c5f | 746 | gcc_assert (PHI_NUM_ARGS (phi) == 2); |
40923b20 DP |
747 | |
748 | /* Find basic block and initialize iterator. */ | |
749 | bb = bb_for_stmt (phi); | |
750 | ||
751 | new_stmt = NULL_TREE; | |
752 | arg_0 = NULL_TREE; | |
753 | arg_1 = NULL_TREE; | |
61b5f210 | 754 | |
40923b20 | 755 | /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ |
7f7e0703 | 756 | if (PHI_ARG_EDGE(phi, 1)->src == true_bb) |
40923b20 DP |
757 | { |
758 | arg_0 = PHI_ARG_DEF (phi, 1); | |
759 | arg_1 = PHI_ARG_DEF (phi, 0); | |
760 | } | |
761 | else | |
762 | { | |
763 | arg_0 = PHI_ARG_DEF (phi, 0); | |
764 | arg_1 = PHI_ARG_DEF (phi, 1); | |
765 | } | |
766 | ||
61b5f210 | 767 | /* Build new RHS using selected condition and arguments. */ |
40923b20 DP |
768 | rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), |
769 | unshare_expr (cond), unshare_expr (arg_0), | |
770 | unshare_expr (arg_1)); | |
771 | ||
61b5f210 | 772 | /* Create new MODIFY expression using RHS. */ |
40923b20 DP |
773 | new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)), |
774 | unshare_expr (PHI_RESULT (phi)), rhs); | |
775 | ||
776 | /* Make new statement definition of the original phi result. */ | |
777 | SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt; | |
778 | ||
779 | /* Set basic block and insert using iterator. */ | |
780 | set_bb_for_stmt (new_stmt, bb); | |
781 | ||
782 | bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT); | |
783 | bsi_next (bsi); | |
784 | ||
785 | modify_stmt (new_stmt); | |
786 | ||
787 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
788 | { | |
789 | fprintf (dump_file, "new phi replacement stmt\n"); | |
790 | print_generic_stmt (dump_file, new_stmt, TDF_SLIM); | |
791 | } | |
792 | } | |
793 | ||
61b5f210 | 794 | /* Process phi nodes for the given LOOP. Replace phi nodes with cond |
40923b20 DP |
795 | modify expr. */ |
796 | ||
797 | static void | |
798 | process_phi_nodes (struct loop *loop) | |
799 | { | |
800 | basic_block bb; | |
801 | unsigned int orig_loop_num_nodes = loop->num_nodes; | |
802 | unsigned int i; | |
803 | ||
804 | /* Replace phi nodes with cond. modify expr. */ | |
805 | for (i = 1; i < orig_loop_num_nodes; i++) | |
806 | { | |
807 | tree phi, cond; | |
808 | block_stmt_iterator bsi; | |
7f7e0703 | 809 | basic_block true_bb = NULL; |
40923b20 | 810 | bb = ifc_bbs[i]; |
61b5f210 | 811 | |
40923b20 DP |
812 | if (bb == loop->header || bb == loop->latch) |
813 | continue; | |
814 | ||
815 | phi = phi_nodes (bb); | |
816 | bsi = bsi_start (bb); | |
817 | ||
818 | /* BB has two predecessors. Using predecessor's aux field, set | |
819 | appropriate condition for the PHI node replacement. */ | |
820 | if (phi) | |
7f7e0703 | 821 | true_bb = find_phi_replacement_condition (bb, &cond, &bsi); |
40923b20 DP |
822 | |
823 | while (phi) | |
824 | { | |
825 | tree next = TREE_CHAIN (phi); | |
7f7e0703 | 826 | replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi); |
40923b20 DP |
827 | release_phi_node (phi); |
828 | phi = next; | |
829 | } | |
830 | bb_ann (bb)->phi_nodes = NULL; | |
831 | } | |
832 | return; | |
833 | } | |
834 | ||
61b5f210 | 835 | /* Combine all basic block from the given LOOP into one or two super |
8c27b7d4 | 836 | basic block. Replace PHI nodes with conditional modify expression. */ |
40923b20 DP |
837 | |
838 | static void | |
839 | combine_blocks (struct loop *loop) | |
840 | { | |
841 | basic_block bb, exit_bb, merge_target_bb; | |
842 | unsigned int orig_loop_num_nodes = loop->num_nodes; | |
843 | unsigned int i; | |
844 | ||
845 | /* Process phi nodes to prepare blocks for merge. */ | |
846 | process_phi_nodes (loop); | |
847 | ||
848 | exit_bb = NULL; | |
849 | ||
850 | /* Merge basic blocks */ | |
851 | merge_target_bb = loop->header; | |
852 | for (i = 1; i < orig_loop_num_nodes; i++) | |
853 | { | |
854 | edge e; | |
855 | block_stmt_iterator bsi; | |
856 | tree_stmt_iterator last; | |
857 | ||
858 | bb = ifc_bbs[i]; | |
859 | ||
860 | if (bb == loop->latch) | |
861 | continue; | |
862 | ||
863 | if (!exit_bb && bb_with_exit_edge_p (bb)) | |
864 | exit_bb = bb; | |
865 | ||
866 | if (bb == exit_bb) | |
867 | { | |
868 | edge new_e; | |
869 | ||
870 | /* Connect this node with loop header. */ | |
871 | new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU); | |
872 | set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]); | |
873 | ||
874 | if (exit_bb != loop->latch) | |
875 | { | |
876 | /* Redirect non-exit edge to loop->latch. */ | |
877 | for (e = bb->succ; e; e = e->succ_next) | |
878 | if (!(e->flags & EDGE_LOOP_EXIT)) | |
879 | { | |
880 | redirect_edge_and_branch (e, loop->latch); | |
881 | set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb); | |
882 | } | |
883 | } | |
884 | continue; | |
885 | } | |
886 | ||
887 | /* It is time to remove this basic block. First remove edges. */ | |
888 | while (bb->succ != NULL) | |
889 | ssa_remove_edge (bb->succ); | |
890 | while (bb->pred != NULL) | |
891 | ssa_remove_edge (bb->pred); | |
892 | ||
893 | /* Remove labels and make stmts member of loop->header. */ | |
894 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) | |
895 | { | |
896 | if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR) | |
897 | bsi_remove (&bsi); | |
898 | else | |
899 | { | |
900 | set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb); | |
901 | bsi_next (&bsi); | |
902 | } | |
903 | } | |
904 | ||
905 | /* Update stmt list. */ | |
906 | last = tsi_last (merge_target_bb->stmt_list); | |
907 | tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT); | |
908 | bb->stmt_list = NULL; | |
909 | ||
910 | /* Update dominator info. */ | |
911 | if (dom_computed[CDI_DOMINATORS]) | |
912 | delete_from_dominance_info (CDI_DOMINATORS, bb); | |
913 | if (dom_computed[CDI_POST_DOMINATORS]) | |
914 | delete_from_dominance_info (CDI_POST_DOMINATORS, bb); | |
61b5f210 | 915 | |
40923b20 DP |
916 | /* Remove basic block. */ |
917 | remove_bb_from_loops (bb); | |
918 | expunge_block (bb); | |
919 | } | |
920 | } | |
921 | ||
61b5f210 | 922 | /* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP |
40923b20 DP |
923 | to the new variable. */ |
924 | ||
925 | static tree | |
926 | ifc_temp_var (tree type, tree exp) | |
927 | { | |
928 | const char *name = "_ifc_"; | |
929 | tree var, stmt, new_name; | |
930 | ||
931 | if (is_gimple_reg (exp)) | |
932 | return exp; | |
933 | ||
934 | /* Create new temporary variable. */ | |
935 | var = create_tmp_var (type, name); | |
936 | add_referenced_tmp_var (var); | |
937 | ||
2a7e31df | 938 | /* Build new statement to assign EXP to new variable. */ |
40923b20 | 939 | stmt = build (MODIFY_EXPR, type, var, exp); |
61b5f210 | 940 | |
40923b20 DP |
941 | /* Get SSA name for the new variable and set make new statement |
942 | its definition statment. */ | |
943 | new_name = make_ssa_name (var, stmt); | |
944 | TREE_OPERAND (stmt, 0) = new_name; | |
945 | SSA_NAME_DEF_STMT (new_name) = stmt; | |
946 | ||
947 | return stmt; | |
948 | } | |
949 | ||
950 | ||
951 | /* Return TRUE iff, all pred blocks of BB are visited. | |
952 | Bitmap VISITED keeps history of visited blocks. */ | |
953 | ||
954 | static bool | |
955 | pred_blocks_visited_p (basic_block bb, bitmap *visited) | |
956 | { | |
957 | edge e; | |
958 | for (e = bb->pred; e; e = e->pred_next) | |
959 | if (!bitmap_bit_p (*visited, e->src->index)) | |
960 | return false; | |
61b5f210 | 961 | |
40923b20 DP |
962 | return true; |
963 | } | |
964 | ||
965 | /* Get body of a LOOP in suitable order for if-conversion. | |
966 | It is caller's responsibility to deallocate basic block | |
967 | list. If-conversion suitable order is, BFS order with one | |
968 | additional constraint. Select block in BFS block, if all | |
969 | pred are already selected. */ | |
970 | ||
61b5f210 | 971 | static basic_block * |
40923b20 DP |
972 | get_loop_body_in_if_conv_order (const struct loop *loop) |
973 | { | |
974 | basic_block *blocks, *blocks_in_bfs_order; | |
975 | basic_block bb; | |
976 | bitmap visited; | |
977 | unsigned int index = 0; | |
978 | unsigned int visited_count = 0; | |
979 | ||
1e128c5f GB |
980 | gcc_assert (loop->num_nodes); |
981 | gcc_assert (loop->latch != EXIT_BLOCK_PTR); | |
40923b20 DP |
982 | |
983 | blocks = xcalloc (loop->num_nodes, sizeof (basic_block)); | |
984 | visited = BITMAP_XMALLOC (); | |
985 | ||
986 | blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); | |
987 | ||
988 | index = 0; | |
989 | while (index < loop->num_nodes) | |
990 | { | |
991 | bb = blocks_in_bfs_order [index]; | |
61b5f210 | 992 | |
40923b20 DP |
993 | if (bb->flags & BB_IRREDUCIBLE_LOOP) |
994 | { | |
995 | free (blocks_in_bfs_order); | |
996 | BITMAP_FREE (visited); | |
997 | free (blocks); | |
998 | return NULL; | |
999 | } | |
1000 | if (!bitmap_bit_p (visited, bb->index)) | |
1001 | { | |
1002 | if (pred_blocks_visited_p (bb, &visited) | |
1003 | || bb == loop->header) | |
1004 | { | |
1005 | /* This block is now visited. */ | |
1006 | bitmap_set_bit (visited, bb->index); | |
1007 | blocks[visited_count++] = bb; | |
1008 | } | |
1009 | } | |
1010 | index++; | |
1011 | if (index == loop->num_nodes | |
1012 | && visited_count != loop->num_nodes) | |
1013 | { | |
1014 | /* Not done yet. */ | |
1015 | index = 0; | |
1016 | } | |
1017 | } | |
1018 | free (blocks_in_bfs_order); | |
1019 | BITMAP_XFREE (visited); | |
1020 | return blocks; | |
1021 | } | |
1022 | ||
1023 | /* Return true if one of the basic block BB edge is loop exit. */ | |
1024 | ||
1025 | static bool | |
1026 | bb_with_exit_edge_p (basic_block bb) | |
1027 | { | |
1028 | edge e; | |
1029 | bool exit_edge_found = false; | |
1030 | ||
1031 | for (e = bb->succ; e && !exit_edge_found ; e = e->succ_next) | |
1032 | if (e->flags & EDGE_LOOP_EXIT) | |
1033 | exit_edge_found = true; | |
1034 | ||
1035 | return exit_edge_found; | |
1036 | } | |
1037 | ||
1038 | /* Tree if-conversion pass management. */ | |
1039 | ||
1040 | static void | |
1041 | main_tree_if_conversion (void) | |
1042 | { | |
1043 | unsigned i, loop_num; | |
1044 | struct loop *loop; | |
1045 | ||
1046 | if (!current_loops) | |
1047 | return; | |
1048 | ||
1049 | loop_num = current_loops->num; | |
1050 | for (i = 0; i < loop_num; i++) | |
1051 | { | |
1052 | loop = current_loops->parray[i]; | |
1053 | if (!loop) | |
1054 | continue; | |
1055 | ||
1056 | tree_if_conversion (loop, true); | |
1057 | } | |
1058 | ||
1059 | } | |
1060 | ||
1061 | static bool | |
1062 | gate_tree_if_conversion (void) | |
1063 | { | |
2addf926 | 1064 | return flag_tree_vectorize != 0; |
40923b20 DP |
1065 | } |
1066 | ||
1067 | struct tree_opt_pass pass_if_conversion = | |
1068 | { | |
1069 | "ifcvt", /* name */ | |
1070 | gate_tree_if_conversion, /* gate */ | |
1071 | main_tree_if_conversion, /* execute */ | |
1072 | NULL, /* sub */ | |
1073 | NULL, /* next */ | |
1074 | 0, /* static_pass_number */ | |
1075 | 0, /* tv_id */ | |
1076 | PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ | |
1077 | 0, /* properties_provided */ | |
1078 | 0, /* properties_destroyed */ | |
1079 | TODO_dump_func, /* todo_flags_start */ | |
61b5f210 | 1080 | TODO_dump_func |
40923b20 | 1081 | | TODO_verify_ssa |
61b5f210 | 1082 | | TODO_verify_stmts |
9f8628ba PB |
1083 | | TODO_verify_flow, /* todo_flags_finish */ |
1084 | 0 /* letter */ | |
40923b20 | 1085 | }; |