]>
Commit | Line | Data |
---|---|---|
07c03fb0 | 1 | /* If-conversion for vectorizer. |
c2c4377d | 2 | Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 |
0b1615c1 | 3 | Free Software Foundation, Inc. |
07c03fb0 | 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 | |
8c4c00c1 | 10 | Software Foundation; either version 3, or (at your option) any later |
07c03fb0 | 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 | |
8c4c00c1 | 19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
07c03fb0 | 21 | |
b01e3c9b | 22 | /* This pass implements a tree level if-conversion of loops. Its |
23 | initial goal is to help the vectorizer to vectorize loops with | |
24 | conditions. | |
07c03fb0 | 25 | |
26 | A short description of if-conversion: | |
27 | ||
9b482bc6 | 28 | o Decide if a loop is if-convertible or not. |
07c03fb0 | 29 | o Walk all loop basic blocks in breadth first order (BFS order). |
30 | o Remove conditional statements (at the end of basic block) | |
35a40aad | 31 | and propagate condition into destination basic blocks' |
07c03fb0 | 32 | predicate list. |
33 | o Replace modify expression with conditional modify expression | |
34 | using current basic block's condition. | |
35 | o Merge all basic blocks | |
36 | o Replace phi nodes with conditional modify expr | |
37 | o Merge all basic blocks into header | |
38 | ||
39 | Sample transformation: | |
40 | ||
41 | INPUT | |
42 | ----- | |
43 | ||
44 | # i_23 = PHI <0(0), i_18(10)>; | |
45 | <L0>:; | |
46 | j_15 = A[i_23]; | |
47 | if (j_15 > 41) goto <L1>; else goto <L17>; | |
48 | ||
49 | <L17>:; | |
50 | goto <bb 3> (<L3>); | |
51 | ||
52 | <L1>:; | |
53 | ||
54 | # iftmp.2_4 = PHI <0(8), 42(2)>; | |
55 | <L3>:; | |
56 | A[i_23] = iftmp.2_4; | |
57 | i_18 = i_23 + 1; | |
58 | if (i_18 <= 15) goto <L19>; else goto <L18>; | |
59 | ||
60 | <L19>:; | |
61 | goto <bb 1> (<L0>); | |
62 | ||
63 | <L18>:; | |
64 | ||
65 | OUTPUT | |
66 | ------ | |
67 | ||
68 | # i_23 = PHI <0(0), i_18(10)>; | |
69 | <L0>:; | |
70 | j_15 = A[i_23]; | |
35a40aad | 71 | |
07c03fb0 | 72 | <L3>:; |
73 | iftmp.2_4 = j_15 > 41 ? 42 : 0; | |
74 | A[i_23] = iftmp.2_4; | |
75 | i_18 = i_23 + 1; | |
76 | if (i_18 <= 15) goto <L19>; else goto <L18>; | |
35a40aad | 77 | |
07c03fb0 | 78 | <L19>:; |
79 | goto <bb 1> (<L0>); | |
80 | ||
81 | <L18>:; | |
82 | */ | |
83 | ||
84 | #include "config.h" | |
85 | #include "system.h" | |
86 | #include "coretypes.h" | |
87 | #include "tm.h" | |
07c03fb0 | 88 | #include "tree.h" |
07c03fb0 | 89 | #include "flags.h" |
07c03fb0 | 90 | #include "basic-block.h" |
ce084dfc | 91 | #include "gimple-pretty-print.h" |
07c03fb0 | 92 | #include "tree-flow.h" |
07c03fb0 | 93 | #include "cfgloop.h" |
94 | #include "tree-chrec.h" | |
95 | #include "tree-data-ref.h" | |
96 | #include "tree-scalar-evolution.h" | |
97 | #include "tree-pass.h" | |
4bd0f929 | 98 | #include "dbgcnt.h" |
07c03fb0 | 99 | |
07c03fb0 | 100 | /* List of basic blocks in if-conversion-suitable order. */ |
101 | static basic_block *ifc_bbs; | |
102 | ||
fa683b76 | 103 | /* Structure used to predicate basic blocks. This is attached to the |
104 | ->aux field of the BBs in the loop to be if-converted. */ | |
105 | typedef struct bb_predicate_s { | |
106 | ||
107 | /* The condition under which this basic block is executed. */ | |
108 | tree predicate; | |
109 | ||
110 | /* PREDICATE is gimplified, and the sequence of statements is | |
111 | recorded here, in order to avoid the duplication of computations | |
112 | that occur in previous conditions. See PR44483. */ | |
113 | gimple_seq predicate_gimplified_stmts; | |
114 | } *bb_predicate_p; | |
115 | ||
116 | /* Returns true when the basic block BB has a predicate. */ | |
117 | ||
118 | static inline bool | |
119 | bb_has_predicate (basic_block bb) | |
120 | { | |
121 | return bb->aux != NULL; | |
122 | } | |
123 | ||
124 | /* Returns the gimplified predicate for basic block BB. */ | |
125 | ||
126 | static inline tree | |
127 | bb_predicate (basic_block bb) | |
128 | { | |
129 | return ((bb_predicate_p) bb->aux)->predicate; | |
130 | } | |
131 | ||
132 | /* Sets the gimplified predicate COND for basic block BB. */ | |
133 | ||
134 | static inline void | |
135 | set_bb_predicate (basic_block bb, tree cond) | |
136 | { | |
56db02b2 | 137 | gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR |
138 | && is_gimple_condexpr (TREE_OPERAND (cond, 0))) | |
139 | || is_gimple_condexpr (cond)); | |
fa683b76 | 140 | ((bb_predicate_p) bb->aux)->predicate = cond; |
141 | } | |
142 | ||
143 | /* Returns the sequence of statements of the gimplification of the | |
144 | predicate for basic block BB. */ | |
145 | ||
146 | static inline gimple_seq | |
147 | bb_predicate_gimplified_stmts (basic_block bb) | |
148 | { | |
149 | return ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts; | |
150 | } | |
151 | ||
152 | /* Sets the sequence of statements STMTS of the gimplification of the | |
153 | predicate for basic block BB. */ | |
154 | ||
155 | static inline void | |
156 | set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) | |
157 | { | |
158 | ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts = stmts; | |
159 | } | |
160 | ||
161 | /* Adds the sequence of statements STMTS to the sequence of statements | |
162 | of the predicate for basic block BB. */ | |
163 | ||
164 | static inline void | |
165 | add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) | |
166 | { | |
167 | gimple_seq_add_seq | |
168 | (&(((bb_predicate_p) bb->aux)->predicate_gimplified_stmts), stmts); | |
169 | } | |
170 | ||
171 | /* Initializes to TRUE the predicate of basic block BB. */ | |
172 | ||
173 | static inline void | |
174 | init_bb_predicate (basic_block bb) | |
175 | { | |
176 | bb->aux = XNEW (struct bb_predicate_s); | |
177 | set_bb_predicate_gimplified_stmts (bb, NULL); | |
48c9b1fe | 178 | set_bb_predicate (bb, boolean_true_node); |
fa683b76 | 179 | } |
180 | ||
181 | /* Free the predicate of basic block BB. */ | |
182 | ||
183 | static inline void | |
184 | free_bb_predicate (basic_block bb) | |
185 | { | |
186 | gimple_seq stmts; | |
187 | ||
188 | if (!bb_has_predicate (bb)) | |
189 | return; | |
190 | ||
191 | /* Release the SSA_NAMEs created for the gimplification of the | |
192 | predicate. */ | |
193 | stmts = bb_predicate_gimplified_stmts (bb); | |
194 | if (stmts) | |
195 | { | |
196 | gimple_stmt_iterator i; | |
197 | ||
198 | for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i)) | |
199 | free_stmt_operands (gsi_stmt (i)); | |
200 | } | |
201 | ||
202 | free (bb->aux); | |
203 | bb->aux = NULL; | |
204 | } | |
205 | ||
48c9b1fe | 206 | /* Free the predicate of BB and reinitialize it with the true |
207 | predicate. */ | |
208 | ||
209 | static inline void | |
210 | reset_bb_predicate (basic_block bb) | |
211 | { | |
212 | free_bb_predicate (bb); | |
213 | init_bb_predicate (bb); | |
214 | } | |
215 | ||
3b91ccd9 | 216 | /* Returns a new SSA_NAME of type TYPE that is assigned the value of |
217 | the expression EXPR. Inserts the statement created for this | |
218 | computation before GSI and leaves the iterator GSI at the same | |
219 | statement. */ | |
07c03fb0 | 220 | |
3b91ccd9 | 221 | static tree |
222 | ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi) | |
07c03fb0 | 223 | { |
03d37e4e | 224 | tree new_name = make_temp_ssa_name (type, NULL, "_ifc_"); |
225 | gimple stmt = gimple_build_assign (new_name, expr); | |
3b91ccd9 | 226 | gsi_insert_before (gsi, stmt, GSI_SAME_STMT); |
03d37e4e | 227 | return new_name; |
1055d96a | 228 | } |
229 | ||
16d6ea49 | 230 | /* Return true when COND is a true predicate. */ |
231 | ||
232 | static inline bool | |
233 | is_true_predicate (tree cond) | |
234 | { | |
235 | return (cond == NULL_TREE | |
236 | || cond == boolean_true_node | |
237 | || integer_onep (cond)); | |
238 | } | |
239 | ||
240 | /* Returns true when BB has a predicate that is not trivial: true or | |
241 | NULL_TREE. */ | |
242 | ||
243 | static inline bool | |
244 | is_predicated (basic_block bb) | |
245 | { | |
fa683b76 | 246 | return !is_true_predicate (bb_predicate (bb)); |
16d6ea49 | 247 | } |
248 | ||
74a43fe9 | 249 | /* Parses the predicate COND and returns its comparison code and |
250 | operands OP0 and OP1. */ | |
251 | ||
252 | static enum tree_code | |
253 | parse_predicate (tree cond, tree *op0, tree *op1) | |
254 | { | |
255 | gimple s; | |
256 | ||
257 | if (TREE_CODE (cond) == SSA_NAME | |
258 | && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond))) | |
259 | { | |
260 | if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison) | |
261 | { | |
262 | *op0 = gimple_assign_rhs1 (s); | |
263 | *op1 = gimple_assign_rhs2 (s); | |
264 | return gimple_assign_rhs_code (s); | |
265 | } | |
266 | ||
267 | else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR) | |
268 | { | |
269 | tree op = gimple_assign_rhs1 (s); | |
270 | tree type = TREE_TYPE (op); | |
271 | enum tree_code code = parse_predicate (op, op0, op1); | |
272 | ||
273 | return code == ERROR_MARK ? ERROR_MARK | |
274 | : invert_tree_comparison (code, HONOR_NANS (TYPE_MODE (type))); | |
275 | } | |
276 | ||
277 | return ERROR_MARK; | |
278 | } | |
279 | ||
280 | if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison) | |
281 | { | |
282 | *op0 = TREE_OPERAND (cond, 0); | |
283 | *op1 = TREE_OPERAND (cond, 1); | |
284 | return TREE_CODE (cond); | |
285 | } | |
286 | ||
287 | return ERROR_MARK; | |
288 | } | |
289 | ||
4be7307c | 290 | /* Returns the fold of predicate C1 OR C2 at location LOC. */ |
291 | ||
292 | static tree | |
293 | fold_or_predicates (location_t loc, tree c1, tree c2) | |
294 | { | |
295 | tree op1a, op1b, op2a, op2b; | |
296 | enum tree_code code1 = parse_predicate (c1, &op1a, &op1b); | |
297 | enum tree_code code2 = parse_predicate (c2, &op2a, &op2b); | |
298 | ||
299 | if (code1 != ERROR_MARK && code2 != ERROR_MARK) | |
300 | { | |
301 | tree t = maybe_fold_or_comparisons (code1, op1a, op1b, | |
302 | code2, op2a, op2b); | |
303 | if (t) | |
304 | return t; | |
305 | } | |
306 | ||
307 | return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2); | |
308 | } | |
309 | ||
74a43fe9 | 310 | /* Add condition NC to the predicate list of basic block BB. */ |
1055d96a | 311 | |
16d6ea49 | 312 | static inline void |
74a43fe9 | 313 | add_to_predicate_list (basic_block bb, tree nc) |
1055d96a | 314 | { |
56db02b2 | 315 | tree bc, *tp; |
74a43fe9 | 316 | |
317 | if (is_true_predicate (nc)) | |
318 | return; | |
319 | ||
320 | if (!is_predicated (bb)) | |
321 | bc = nc; | |
322 | else | |
323 | { | |
74a43fe9 | 324 | bc = bb_predicate (bb); |
4be7307c | 325 | bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc); |
56db02b2 | 326 | if (is_true_predicate (bc)) |
327 | { | |
328 | reset_bb_predicate (bb); | |
329 | return; | |
330 | } | |
74a43fe9 | 331 | } |
332 | ||
56db02b2 | 333 | /* Allow a TRUTH_NOT_EXPR around the main predicate. */ |
334 | if (TREE_CODE (bc) == TRUTH_NOT_EXPR) | |
335 | tp = &TREE_OPERAND (bc, 0); | |
336 | else | |
337 | tp = &bc; | |
338 | if (!is_gimple_condexpr (*tp)) | |
74a43fe9 | 339 | { |
340 | gimple_seq stmts; | |
56db02b2 | 341 | *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE); |
74a43fe9 | 342 | add_bb_predicate_gimplified_stmts (bb, stmts); |
343 | } | |
56db02b2 | 344 | set_bb_predicate (bb, bc); |
1055d96a | 345 | } |
346 | ||
60e0f7c4 | 347 | /* Add the condition COND to the previous condition PREV_COND, and add |
348 | this to the predicate list of the destination of edge E. LOOP is | |
349 | the loop to be if-converted. */ | |
1055d96a | 350 | |
16d6ea49 | 351 | static void |
1055d96a | 352 | add_to_dst_predicate_list (struct loop *loop, edge e, |
60e0f7c4 | 353 | tree prev_cond, tree cond) |
1055d96a | 354 | { |
1055d96a | 355 | if (!flow_bb_inside_loop_p (loop, e->dest)) |
16d6ea49 | 356 | return; |
1055d96a | 357 | |
16d6ea49 | 358 | if (!is_true_predicate (prev_cond)) |
359 | cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, | |
360 | prev_cond, cond); | |
07c03fb0 | 361 | |
16d6ea49 | 362 | add_to_predicate_list (e->dest, cond); |
1055d96a | 363 | } |
58bc8309 | 364 | |
b01e3c9b | 365 | /* Return true if one of the successor edges of BB exits LOOP. */ |
07c03fb0 | 366 | |
1055d96a | 367 | static bool |
368 | bb_with_exit_edge_p (struct loop *loop, basic_block bb) | |
369 | { | |
370 | edge e; | |
371 | edge_iterator ei; | |
07c03fb0 | 372 | |
1055d96a | 373 | FOR_EACH_EDGE (e, ei, bb->succs) |
374 | if (loop_exit_edge_p (loop, e)) | |
b01e3c9b | 375 | return true; |
07c03fb0 | 376 | |
b01e3c9b | 377 | return false; |
1055d96a | 378 | } |
63a1777b | 379 | |
b01e3c9b | 380 | /* Return true when PHI is if-convertible. PHI is part of loop LOOP |
07c03fb0 | 381 | and it belongs to basic block BB. |
b01e3c9b | 382 | |
383 | PHI is not if-convertible if: | |
3b91ccd9 | 384 | - it has more than 2 arguments. |
385 | ||
386 | When the flag_tree_loop_if_convert_stores is not set, PHI is not | |
387 | if-convertible if: | |
388 | - a virtual PHI is immediately used in another PHI node, | |
389 | - there is a virtual PHI in a BB other than the loop->header. */ | |
07c03fb0 | 390 | |
391 | static bool | |
75a70cf9 | 392 | if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) |
07c03fb0 | 393 | { |
394 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
395 | { | |
396 | fprintf (dump_file, "-------------------------\n"); | |
75a70cf9 | 397 | print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); |
07c03fb0 | 398 | } |
35a40aad | 399 | |
75a70cf9 | 400 | if (bb != loop->header && gimple_phi_num_args (phi) != 2) |
07c03fb0 | 401 | { |
402 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
403 | fprintf (dump_file, "More than two phi node args.\n"); | |
404 | return false; | |
405 | } | |
35a40aad | 406 | |
3b91ccd9 | 407 | if (flag_tree_loop_if_convert_stores) |
408 | return true; | |
409 | ||
410 | /* When the flag_tree_loop_if_convert_stores is not set, check | |
411 | that there are no memory writes in the branches of the loop to be | |
412 | if-converted. */ | |
7c782c9b | 413 | if (virtual_operand_p (gimple_phi_result (phi))) |
07c03fb0 | 414 | { |
22aa74c4 | 415 | imm_use_iterator imm_iter; |
416 | use_operand_p use_p; | |
296c44f8 | 417 | |
418 | if (bb != loop->header) | |
419 | { | |
420 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3b91ccd9 | 421 | fprintf (dump_file, "Virtual phi not on loop->header.\n"); |
296c44f8 | 422 | return false; |
423 | } | |
3b91ccd9 | 424 | |
75a70cf9 | 425 | FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi)) |
07c03fb0 | 426 | { |
75a70cf9 | 427 | if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI) |
07c03fb0 | 428 | { |
429 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
430 | fprintf (dump_file, "Difficult to handle this virtual phi.\n"); | |
431 | return false; | |
432 | } | |
433 | } | |
434 | } | |
435 | ||
436 | return true; | |
437 | } | |
438 | ||
9cabbd00 | 439 | /* Records the status of a data reference. This struct is attached to |
440 | each DR->aux field. */ | |
441 | ||
442 | struct ifc_dr { | |
443 | /* -1 when not initialized, 0 when false, 1 when true. */ | |
444 | int written_at_least_once; | |
445 | ||
446 | /* -1 when not initialized, 0 when false, 1 when true. */ | |
447 | int rw_unconditionally; | |
448 | }; | |
449 | ||
450 | #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux) | |
451 | #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once) | |
452 | #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally) | |
453 | ||
e1cc68bd | 454 | /* Returns true when the memory references of STMT are read or written |
455 | unconditionally. In other words, this function returns true when | |
456 | for every data reference A in STMT there exist other accesses to | |
e257cde2 | 457 | a data reference with the same base with predicates that add up (OR-up) to |
458 | the true predicate: this ensures that the data reference A is touched | |
e1cc68bd | 459 | (read or written) on every iteration of the if-converted loop. */ |
460 | ||
461 | static bool | |
462 | memrefs_read_or_written_unconditionally (gimple stmt, | |
463 | VEC (data_reference_p, heap) *drs) | |
464 | { | |
465 | int i, j; | |
466 | data_reference_p a, b; | |
467 | tree ca = bb_predicate (gimple_bb (stmt)); | |
468 | ||
469 | for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++) | |
470 | if (DR_STMT (a) == stmt) | |
471 | { | |
472 | bool found = false; | |
9cabbd00 | 473 | int x = DR_RW_UNCONDITIONALLY (a); |
474 | ||
475 | if (x == 0) | |
476 | return false; | |
477 | ||
478 | if (x == 1) | |
479 | continue; | |
e1cc68bd | 480 | |
481 | for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++) | |
e257cde2 | 482 | { |
483 | tree ref_base_a = DR_REF (a); | |
484 | tree ref_base_b = DR_REF (b); | |
485 | ||
486 | if (DR_STMT (b) == stmt) | |
487 | continue; | |
488 | ||
489 | while (TREE_CODE (ref_base_a) == COMPONENT_REF | |
490 | || TREE_CODE (ref_base_a) == IMAGPART_EXPR | |
491 | || TREE_CODE (ref_base_a) == REALPART_EXPR) | |
492 | ref_base_a = TREE_OPERAND (ref_base_a, 0); | |
493 | ||
494 | while (TREE_CODE (ref_base_b) == COMPONENT_REF | |
495 | || TREE_CODE (ref_base_b) == IMAGPART_EXPR | |
496 | || TREE_CODE (ref_base_b) == REALPART_EXPR) | |
497 | ref_base_b = TREE_OPERAND (ref_base_b, 0); | |
498 | ||
499 | if (!operand_equal_p (ref_base_a, ref_base_b, 0)) | |
500 | { | |
501 | tree cb = bb_predicate (gimple_bb (DR_STMT (b))); | |
502 | ||
503 | if (DR_RW_UNCONDITIONALLY (b) == 1 | |
504 | || is_true_predicate (cb) | |
505 | || is_true_predicate (ca | |
506 | = fold_or_predicates (EXPR_LOCATION (cb), ca, cb))) | |
507 | { | |
508 | DR_RW_UNCONDITIONALLY (a) = 1; | |
509 | DR_RW_UNCONDITIONALLY (b) = 1; | |
510 | found = true; | |
511 | break; | |
512 | } | |
513 | } | |
e1cc68bd | 514 | } |
515 | ||
516 | if (!found) | |
9cabbd00 | 517 | { |
518 | DR_RW_UNCONDITIONALLY (a) = 0; | |
519 | return false; | |
520 | } | |
e1cc68bd | 521 | } |
522 | ||
523 | return true; | |
524 | } | |
525 | ||
526 | /* Returns true when the memory references of STMT are unconditionally | |
527 | written. In other words, this function returns true when for every | |
528 | data reference A written in STMT, there exist other writes to the | |
529 | same data reference with predicates that add up (OR-up) to the true | |
530 | predicate: this ensures that the data reference A is written on | |
531 | every iteration of the if-converted loop. */ | |
532 | ||
533 | static bool | |
534 | write_memrefs_written_at_least_once (gimple stmt, | |
535 | VEC (data_reference_p, heap) *drs) | |
536 | { | |
537 | int i, j; | |
538 | data_reference_p a, b; | |
539 | tree ca = bb_predicate (gimple_bb (stmt)); | |
540 | ||
541 | for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++) | |
542 | if (DR_STMT (a) == stmt | |
9ff25603 | 543 | && DR_IS_WRITE (a)) |
e1cc68bd | 544 | { |
545 | bool found = false; | |
9cabbd00 | 546 | int x = DR_WRITTEN_AT_LEAST_ONCE (a); |
547 | ||
548 | if (x == 0) | |
549 | return false; | |
550 | ||
551 | if (x == 1) | |
552 | continue; | |
e1cc68bd | 553 | |
554 | for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++) | |
555 | if (DR_STMT (b) != stmt | |
9ff25603 | 556 | && DR_IS_WRITE (b) |
e1cc68bd | 557 | && same_data_refs_base_objects (a, b)) |
558 | { | |
559 | tree cb = bb_predicate (gimple_bb (DR_STMT (b))); | |
560 | ||
9cabbd00 | 561 | if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1 |
562 | || is_true_predicate (cb) | |
e1cc68bd | 563 | || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb), |
564 | ca, cb))) | |
565 | { | |
9cabbd00 | 566 | DR_WRITTEN_AT_LEAST_ONCE (a) = 1; |
567 | DR_WRITTEN_AT_LEAST_ONCE (b) = 1; | |
e1cc68bd | 568 | found = true; |
569 | break; | |
570 | } | |
571 | } | |
572 | ||
573 | if (!found) | |
9cabbd00 | 574 | { |
575 | DR_WRITTEN_AT_LEAST_ONCE (a) = 0; | |
576 | return false; | |
577 | } | |
e1cc68bd | 578 | } |
579 | ||
580 | return true; | |
581 | } | |
582 | ||
583 | /* Return true when the memory references of STMT won't trap in the | |
584 | if-converted code. There are two things that we have to check for: | |
585 | ||
586 | - writes to memory occur to writable memory: if-conversion of | |
587 | memory writes transforms the conditional memory writes into | |
588 | unconditional writes, i.e. "if (cond) A[i] = foo" is transformed | |
589 | into "A[i] = cond ? foo : A[i]", and as the write to memory may not | |
590 | be executed at all in the original code, it may be a readonly | |
591 | memory. To check that A is not const-qualified, we check that | |
592 | there exists at least an unconditional write to A in the current | |
593 | function. | |
594 | ||
595 | - reads or writes to memory are valid memory accesses for every | |
596 | iteration. To check that the memory accesses are correctly formed | |
597 | and that we are allowed to read and write in these locations, we | |
598 | check that the memory accesses to be if-converted occur at every | |
599 | iteration unconditionally. */ | |
600 | ||
601 | static bool | |
602 | ifcvt_memrefs_wont_trap (gimple stmt, VEC (data_reference_p, heap) *refs) | |
603 | { | |
604 | return write_memrefs_written_at_least_once (stmt, refs) | |
605 | && memrefs_read_or_written_unconditionally (stmt, refs); | |
606 | } | |
607 | ||
608 | /* Wrapper around gimple_could_trap_p refined for the needs of the | |
609 | if-conversion. Try to prove that the memory accesses of STMT could | |
610 | not trap in the innermost loop containing STMT. */ | |
611 | ||
612 | static bool | |
613 | ifcvt_could_trap_p (gimple stmt, VEC (data_reference_p, heap) *refs) | |
614 | { | |
615 | if (gimple_vuse (stmt) | |
616 | && !gimple_could_trap_p_1 (stmt, false, false) | |
617 | && ifcvt_memrefs_wont_trap (stmt, refs)) | |
618 | return false; | |
619 | ||
620 | return gimple_could_trap_p (stmt); | |
621 | } | |
622 | ||
b01e3c9b | 623 | /* Return true when STMT is if-convertible. |
624 | ||
75a70cf9 | 625 | GIMPLE_ASSIGN statement is not if-convertible if, |
a1660ced | 626 | - it is not movable, |
627 | - it could trap, | |
3b91ccd9 | 628 | - LHS is not var decl. */ |
07c03fb0 | 629 | |
630 | static bool | |
e1cc68bd | 631 | if_convertible_gimple_assign_stmt_p (gimple stmt, |
632 | VEC (data_reference_p, heap) *refs) | |
07c03fb0 | 633 | { |
b01e3c9b | 634 | tree lhs = gimple_assign_lhs (stmt); |
3b91ccd9 | 635 | basic_block bb; |
73772494 | 636 | |
07c03fb0 | 637 | if (dump_file && (dump_flags & TDF_DETAILS)) |
638 | { | |
639 | fprintf (dump_file, "-------------------------\n"); | |
75a70cf9 | 640 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
07c03fb0 | 641 | } |
35a40aad | 642 | |
3b91ccd9 | 643 | if (!is_gimple_reg_type (TREE_TYPE (lhs))) |
644 | return false; | |
645 | ||
73772494 | 646 | /* Some of these constrains might be too conservative. */ |
75a70cf9 | 647 | if (stmt_ends_bb_p (stmt) |
648 | || gimple_has_volatile_ops (stmt) | |
73772494 | 649 | || (TREE_CODE (lhs) == SSA_NAME |
650 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) | |
75a70cf9 | 651 | || gimple_has_side_effects (stmt)) |
07c03fb0 | 652 | { |
653 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
73772494 | 654 | fprintf (dump_file, "stmt not suitable for ifcvt\n"); |
07c03fb0 | 655 | return false; |
656 | } | |
657 | ||
3b91ccd9 | 658 | if (flag_tree_loop_if_convert_stores) |
659 | { | |
e1cc68bd | 660 | if (ifcvt_could_trap_p (stmt, refs)) |
3b91ccd9 | 661 | { |
662 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
663 | fprintf (dump_file, "tree could trap...\n"); | |
664 | return false; | |
665 | } | |
666 | return true; | |
667 | } | |
668 | ||
12ec13df | 669 | if (gimple_assign_rhs_could_trap_p (stmt)) |
07c03fb0 | 670 | { |
671 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
672 | fprintf (dump_file, "tree could trap...\n"); | |
673 | return false; | |
674 | } | |
675 | ||
3b91ccd9 | 676 | bb = gimple_bb (stmt); |
677 | ||
75a70cf9 | 678 | if (TREE_CODE (lhs) != SSA_NAME |
3b91ccd9 | 679 | && bb != bb->loop_father->header |
680 | && !bb_with_exit_edge_p (bb->loop_father, bb)) | |
07c03fb0 | 681 | { |
682 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
683 | { | |
684 | fprintf (dump_file, "LHS is not var\n"); | |
75a70cf9 | 685 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
07c03fb0 | 686 | } |
687 | return false; | |
688 | } | |
689 | ||
07c03fb0 | 690 | return true; |
691 | } | |
692 | ||
b01e3c9b | 693 | /* Return true when STMT is if-convertible. |
694 | ||
695 | A statement is if-convertible if: | |
c2c4377d | 696 | - it is an if-convertible GIMPLE_ASSIGN, |
3b91ccd9 | 697 | - it is a GIMPLE_LABEL or a GIMPLE_COND. */ |
07c03fb0 | 698 | |
699 | static bool | |
e1cc68bd | 700 | if_convertible_stmt_p (gimple stmt, VEC (data_reference_p, heap) *refs) |
07c03fb0 | 701 | { |
75a70cf9 | 702 | switch (gimple_code (stmt)) |
07c03fb0 | 703 | { |
75a70cf9 | 704 | case GIMPLE_LABEL: |
9845d120 | 705 | case GIMPLE_DEBUG: |
b01e3c9b | 706 | case GIMPLE_COND: |
707 | return true; | |
35a40aad | 708 | |
9845d120 | 709 | case GIMPLE_ASSIGN: |
e1cc68bd | 710 | return if_convertible_gimple_assign_stmt_p (stmt, refs); |
35a40aad | 711 | |
2cac353d | 712 | case GIMPLE_CALL: |
713 | { | |
714 | tree fndecl = gimple_call_fndecl (stmt); | |
715 | if (fndecl) | |
716 | { | |
717 | int flags = gimple_call_flags (stmt); | |
718 | if ((flags & ECF_CONST) | |
719 | && !(flags & ECF_LOOPING_CONST_OR_PURE) | |
720 | /* We can only vectorize some builtins at the moment, | |
721 | so restrict if-conversion to those. */ | |
722 | && DECL_BUILT_IN (fndecl)) | |
723 | return true; | |
724 | } | |
725 | return false; | |
726 | } | |
727 | ||
07c03fb0 | 728 | default: |
729 | /* Don't know what to do with 'em so don't do anything. */ | |
730 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
731 | { | |
732 | fprintf (dump_file, "don't know what to do\n"); | |
75a70cf9 | 733 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
07c03fb0 | 734 | } |
735 | return false; | |
736 | break; | |
737 | } | |
738 | ||
739 | return true; | |
740 | } | |
741 | ||
5790abbc | 742 | /* Return true when BB post-dominates all its predecessors. */ |
743 | ||
744 | static bool | |
745 | bb_postdominates_preds (basic_block bb) | |
746 | { | |
747 | unsigned i; | |
748 | ||
749 | for (i = 0; i < EDGE_COUNT (bb->preds); i++) | |
750 | if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb)) | |
751 | return false; | |
752 | ||
753 | return true; | |
754 | } | |
755 | ||
b01e3c9b | 756 | /* Return true when BB is if-convertible. This routine does not check |
757 | basic block's statements and phis. | |
758 | ||
759 | A basic block is not if-convertible if: | |
760 | - it is non-empty and it is after the exit block (in BFS order), | |
761 | - it is after the exit block but before the latch, | |
762 | - its edges are not normal. | |
763 | ||
764 | EXIT_BB is the basic block containing the exit of the LOOP. BB is | |
765 | inside LOOP. */ | |
07c03fb0 | 766 | |
35a40aad | 767 | static bool |
ea3f88a7 | 768 | if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) |
07c03fb0 | 769 | { |
770 | edge e; | |
cd665a06 | 771 | edge_iterator ei; |
07c03fb0 | 772 | |
773 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
774 | fprintf (dump_file, "----------[%d]-------------\n", bb->index); | |
35a40aad | 775 | |
cedd9a27 | 776 | if (EDGE_COUNT (bb->preds) > 2 |
777 | || EDGE_COUNT (bb->succs) > 2) | |
778 | return false; | |
779 | ||
ea3f88a7 | 780 | if (exit_bb) |
07c03fb0 | 781 | { |
782 | if (bb != loop->latch) | |
783 | { | |
784 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
785 | fprintf (dump_file, "basic block after exit bb but before latch\n"); | |
786 | return false; | |
787 | } | |
788 | else if (!empty_block_p (bb)) | |
789 | { | |
1055d96a | 790 | if (dump_file && (dump_flags & TDF_DETAILS)) |
791 | fprintf (dump_file, "non empty basic block after exit bb\n"); | |
792 | return false; | |
793 | } | |
794 | else if (bb == loop->latch | |
795 | && bb != exit_bb | |
796 | && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) | |
797 | { | |
798 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
799 | fprintf (dump_file, "latch is not dominated by exit_block\n"); | |
800 | return false; | |
801 | } | |
802 | } | |
803 | ||
804 | /* Be less adventurous and handle only normal edges. */ | |
805 | FOR_EACH_EDGE (e, ei, bb->succs) | |
5147ec07 | 806 | if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) |
1055d96a | 807 | { |
808 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
b01e3c9b | 809 | fprintf (dump_file, "Difficult to handle edges\n"); |
1055d96a | 810 | return false; |
811 | } | |
812 | ||
5790abbc | 813 | if (EDGE_COUNT (bb->preds) == 2 |
814 | && bb != loop->header | |
815 | && !bb_postdominates_preds (bb)) | |
816 | return false; | |
817 | ||
1055d96a | 818 | return true; |
819 | } | |
820 | ||
b01e3c9b | 821 | /* Return true when all predecessor blocks of BB are visited. The |
822 | VISITED bitmap keeps track of the visited blocks. */ | |
1055d96a | 823 | |
824 | static bool | |
825 | pred_blocks_visited_p (basic_block bb, bitmap *visited) | |
826 | { | |
827 | edge e; | |
828 | edge_iterator ei; | |
829 | FOR_EACH_EDGE (e, ei, bb->preds) | |
830 | if (!bitmap_bit_p (*visited, e->src->index)) | |
831 | return false; | |
832 | ||
833 | return true; | |
834 | } | |
835 | ||
836 | /* Get body of a LOOP in suitable order for if-conversion. It is | |
837 | caller's responsibility to deallocate basic block list. | |
838 | If-conversion suitable order is, breadth first sort (BFS) order | |
839 | with an additional constraint: select a block only if all its | |
840 | predecessors are already selected. */ | |
841 | ||
842 | static basic_block * | |
843 | get_loop_body_in_if_conv_order (const struct loop *loop) | |
844 | { | |
845 | basic_block *blocks, *blocks_in_bfs_order; | |
846 | basic_block bb; | |
847 | bitmap visited; | |
848 | unsigned int index = 0; | |
849 | unsigned int visited_count = 0; | |
850 | ||
851 | gcc_assert (loop->num_nodes); | |
852 | gcc_assert (loop->latch != EXIT_BLOCK_PTR); | |
853 | ||
854 | blocks = XCNEWVEC (basic_block, loop->num_nodes); | |
855 | visited = BITMAP_ALLOC (NULL); | |
856 | ||
857 | blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); | |
858 | ||
859 | index = 0; | |
860 | while (index < loop->num_nodes) | |
861 | { | |
862 | bb = blocks_in_bfs_order [index]; | |
863 | ||
864 | if (bb->flags & BB_IRREDUCIBLE_LOOP) | |
865 | { | |
866 | free (blocks_in_bfs_order); | |
867 | BITMAP_FREE (visited); | |
868 | free (blocks); | |
869 | return NULL; | |
870 | } | |
871 | ||
872 | if (!bitmap_bit_p (visited, bb->index)) | |
873 | { | |
874 | if (pred_blocks_visited_p (bb, &visited) | |
875 | || bb == loop->header) | |
876 | { | |
877 | /* This block is now visited. */ | |
878 | bitmap_set_bit (visited, bb->index); | |
879 | blocks[visited_count++] = bb; | |
880 | } | |
07c03fb0 | 881 | } |
35a40aad | 882 | |
1055d96a | 883 | index++; |
07c03fb0 | 884 | |
1055d96a | 885 | if (index == loop->num_nodes |
886 | && visited_count != loop->num_nodes) | |
887 | /* Not done yet. */ | |
888 | index = 0; | |
889 | } | |
890 | free (blocks_in_bfs_order); | |
891 | BITMAP_FREE (visited); | |
892 | return blocks; | |
07c03fb0 | 893 | } |
894 | ||
60e0f7c4 | 895 | /* Returns true when the analysis of the predicates for all the basic |
896 | blocks in LOOP succeeded. | |
897 | ||
fa683b76 | 898 | predicate_bbs first allocates the predicates of the basic blocks. |
c814c39c | 899 | These fields are then initialized with the tree expressions |
900 | representing the predicates under which a basic block is executed | |
901 | in the LOOP. As the loop->header is executed at each iteration, it | |
902 | has the "true" predicate. Other statements executed under a | |
903 | condition are predicated with that condition, for example | |
60e0f7c4 | 904 | |
905 | | if (x) | |
906 | | S1; | |
907 | | else | |
908 | | S2; | |
909 | ||
5f7a9884 | 910 | S1 will be predicated with "x", and |
911 | S2 will be predicated with "!x". */ | |
60e0f7c4 | 912 | |
913 | static bool | |
914 | predicate_bbs (loop_p loop) | |
915 | { | |
916 | unsigned int i; | |
917 | ||
918 | for (i = 0; i < loop->num_nodes; i++) | |
fa683b76 | 919 | init_bb_predicate (ifc_bbs[i]); |
60e0f7c4 | 920 | |
921 | for (i = 0; i < loop->num_nodes; i++) | |
922 | { | |
fa683b76 | 923 | basic_block bb = ifc_bbs[i]; |
924 | tree cond; | |
60e0f7c4 | 925 | gimple_stmt_iterator itr; |
926 | ||
fa683b76 | 927 | /* The loop latch is always executed and has no extra conditions |
928 | to be processed: skip it. */ | |
929 | if (bb == loop->latch) | |
930 | { | |
48c9b1fe | 931 | reset_bb_predicate (loop->latch); |
fa683b76 | 932 | continue; |
933 | } | |
934 | ||
935 | cond = bb_predicate (bb); | |
fa683b76 | 936 | |
60e0f7c4 | 937 | for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) |
938 | { | |
939 | gimple stmt = gsi_stmt (itr); | |
940 | ||
941 | switch (gimple_code (stmt)) | |
942 | { | |
943 | case GIMPLE_LABEL: | |
944 | case GIMPLE_ASSIGN: | |
945 | case GIMPLE_CALL: | |
60e0f7c4 | 946 | case GIMPLE_DEBUG: |
60e0f7c4 | 947 | break; |
948 | ||
949 | case GIMPLE_COND: | |
950 | { | |
06734da8 | 951 | tree c2; |
60e0f7c4 | 952 | edge true_edge, false_edge; |
953 | location_t loc = gimple_location (stmt); | |
954 | tree c = fold_build2_loc (loc, gimple_cond_code (stmt), | |
955 | boolean_type_node, | |
956 | gimple_cond_lhs (stmt), | |
957 | gimple_cond_rhs (stmt)); | |
958 | ||
fa683b76 | 959 | /* Add new condition into destination's predicate list. */ |
60e0f7c4 | 960 | extract_true_false_edges_from_block (gimple_bb (stmt), |
961 | &true_edge, &false_edge); | |
962 | ||
60e0f7c4 | 963 | /* If C is true, then TRUE_EDGE is taken. */ |
56db02b2 | 964 | add_to_dst_predicate_list (loop, true_edge, |
965 | unshare_expr (cond), | |
966 | unshare_expr (c)); | |
60e0f7c4 | 967 | |
968 | /* If C is false, then FALSE_EDGE is taken. */ | |
06734da8 | 969 | c2 = build1_loc (loc, TRUTH_NOT_EXPR, |
970 | boolean_type_node, unshare_expr (c)); | |
56db02b2 | 971 | add_to_dst_predicate_list (loop, false_edge, |
972 | unshare_expr (cond), c2); | |
60e0f7c4 | 973 | |
974 | cond = NULL_TREE; | |
975 | break; | |
976 | } | |
977 | ||
5f7a9884 | 978 | default: |
60e0f7c4 | 979 | /* Not handled yet in if-conversion. */ |
980 | return false; | |
60e0f7c4 | 981 | } |
982 | } | |
983 | ||
984 | /* If current bb has only one successor, then consider it as an | |
985 | unconditional goto. */ | |
986 | if (single_succ_p (bb)) | |
987 | { | |
988 | basic_block bb_n = single_succ (bb); | |
989 | ||
990 | /* The successor bb inherits the predicate of its | |
991 | predecessor. If there is no predicate in the predecessor | |
992 | bb, then consider the successor bb as always executed. */ | |
993 | if (cond == NULL_TREE) | |
994 | cond = boolean_true_node; | |
995 | ||
996 | add_to_predicate_list (bb_n, cond); | |
997 | } | |
998 | } | |
999 | ||
1000 | /* The loop header is always executed. */ | |
48c9b1fe | 1001 | reset_bb_predicate (loop->header); |
fa683b76 | 1002 | gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL |
1003 | && bb_predicate_gimplified_stmts (loop->latch) == NULL); | |
60e0f7c4 | 1004 | |
1005 | return true; | |
1006 | } | |
1007 | ||
e1cc68bd | 1008 | /* Return true when LOOP is if-convertible. This is a helper function |
1009 | for if_convertible_loop_p. REFS and DDRS are initialized and freed | |
1010 | in if_convertible_loop_p. */ | |
07c03fb0 | 1011 | |
1012 | static bool | |
e1cc68bd | 1013 | if_convertible_loop_p_1 (struct loop *loop, |
a8af2e86 | 1014 | VEC (loop_p, heap) **loop_nest, |
e1cc68bd | 1015 | VEC (data_reference_p, heap) **refs, |
1016 | VEC (ddr_p, heap) **ddrs) | |
07c03fb0 | 1017 | { |
e1cc68bd | 1018 | bool res; |
07c03fb0 | 1019 | unsigned int i; |
ea3f88a7 | 1020 | basic_block exit_bb = NULL; |
07c03fb0 | 1021 | |
fa6e55f9 | 1022 | /* Don't if-convert the loop when the data dependences cannot be |
1023 | computed: the loop won't be vectorized in that case. */ | |
a8af2e86 | 1024 | res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs); |
e1cc68bd | 1025 | if (!res) |
1026 | return false; | |
fa6e55f9 | 1027 | |
07c03fb0 | 1028 | calculate_dominance_info (CDI_DOMINATORS); |
5790abbc | 1029 | calculate_dominance_info (CDI_POST_DOMINATORS); |
07c03fb0 | 1030 | |
1031 | /* Allow statements that can be handled during if-conversion. */ | |
1032 | ifc_bbs = get_loop_body_in_if_conv_order (loop); | |
1033 | if (!ifc_bbs) | |
1034 | { | |
1035 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
d11c70fa | 1036 | fprintf (dump_file, "Irreducible loop\n"); |
07c03fb0 | 1037 | return false; |
1038 | } | |
35a40aad | 1039 | |
07c03fb0 | 1040 | for (i = 0; i < loop->num_nodes; i++) |
1041 | { | |
60e0f7c4 | 1042 | basic_block bb = ifc_bbs[i]; |
07c03fb0 | 1043 | |
ea3f88a7 | 1044 | if (!if_convertible_bb_p (loop, bb, exit_bb)) |
07c03fb0 | 1045 | return false; |
1046 | ||
60e0f7c4 | 1047 | if (bb_with_exit_edge_p (loop, bb)) |
1048 | exit_bb = bb; | |
1049 | } | |
1050 | ||
e1cc68bd | 1051 | res = predicate_bbs (loop); |
1052 | if (!res) | |
60e0f7c4 | 1053 | return false; |
1054 | ||
9cabbd00 | 1055 | if (flag_tree_loop_if_convert_stores) |
1056 | { | |
1057 | data_reference_p dr; | |
1058 | ||
1059 | for (i = 0; VEC_iterate (data_reference_p, *refs, i, dr); i++) | |
1060 | { | |
1061 | dr->aux = XNEW (struct ifc_dr); | |
1062 | DR_WRITTEN_AT_LEAST_ONCE (dr) = -1; | |
1063 | DR_RW_UNCONDITIONALLY (dr) = -1; | |
1064 | } | |
1065 | } | |
1066 | ||
60e0f7c4 | 1067 | for (i = 0; i < loop->num_nodes; i++) |
1068 | { | |
1069 | basic_block bb = ifc_bbs[i]; | |
1070 | gimple_stmt_iterator itr; | |
1071 | ||
7f6dfba2 | 1072 | for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr)) |
1073 | if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr))) | |
1074 | return false; | |
1075 | ||
e1cc68bd | 1076 | /* Check the if-convertibility of statements in predicated BBs. */ |
1077 | if (is_predicated (bb)) | |
1078 | for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) | |
1079 | if (!if_convertible_stmt_p (gsi_stmt (itr), *refs)) | |
1080 | return false; | |
07c03fb0 | 1081 | } |
1082 | ||
07c03fb0 | 1083 | if (dump_file) |
d11c70fa | 1084 | fprintf (dump_file, "Applying if-conversion\n"); |
07c03fb0 | 1085 | |
07c03fb0 | 1086 | return true; |
1087 | } | |
1088 | ||
e1cc68bd | 1089 | /* Return true when LOOP is if-convertible. |
1090 | LOOP is if-convertible if: | |
1091 | - it is innermost, | |
1092 | - it has two or more basic blocks, | |
1093 | - it has only one exit, | |
1094 | - loop header is not the exit edge, | |
1095 | - if its basic blocks and phi nodes are if convertible. */ | |
1096 | ||
1097 | static bool | |
1098 | if_convertible_loop_p (struct loop *loop) | |
1099 | { | |
1100 | edge e; | |
1101 | edge_iterator ei; | |
1102 | bool res = false; | |
1103 | VEC (data_reference_p, heap) *refs; | |
1104 | VEC (ddr_p, heap) *ddrs; | |
a8af2e86 | 1105 | VEC (loop_p, heap) *loop_nest; |
e1cc68bd | 1106 | |
1107 | /* Handle only innermost loop. */ | |
1108 | if (!loop || loop->inner) | |
1109 | { | |
1110 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1111 | fprintf (dump_file, "not innermost loop\n"); | |
1112 | return false; | |
1113 | } | |
1114 | ||
1115 | /* If only one block, no need for if-conversion. */ | |
1116 | if (loop->num_nodes <= 2) | |
1117 | { | |
1118 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1119 | fprintf (dump_file, "less than 2 basic blocks\n"); | |
1120 | return false; | |
1121 | } | |
1122 | ||
1123 | /* More than one loop exit is too much to handle. */ | |
1124 | if (!single_exit (loop)) | |
1125 | { | |
1126 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1127 | fprintf (dump_file, "multiple exits\n"); | |
1128 | return false; | |
1129 | } | |
1130 | ||
1131 | /* If one of the loop header's edge is an exit edge then do not | |
1132 | apply if-conversion. */ | |
1133 | FOR_EACH_EDGE (e, ei, loop->header->succs) | |
1134 | if (loop_exit_edge_p (loop, e)) | |
1135 | return false; | |
1136 | ||
1137 | refs = VEC_alloc (data_reference_p, heap, 5); | |
1138 | ddrs = VEC_alloc (ddr_p, heap, 25); | |
a8af2e86 | 1139 | loop_nest = VEC_alloc (loop_p, heap, 3); |
1140 | res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs); | |
e1cc68bd | 1141 | |
9cabbd00 | 1142 | if (flag_tree_loop_if_convert_stores) |
1143 | { | |
1144 | data_reference_p dr; | |
1145 | unsigned int i; | |
1146 | ||
1147 | for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++) | |
1148 | free (dr->aux); | |
1149 | } | |
1150 | ||
a8af2e86 | 1151 | VEC_free (loop_p, heap, loop_nest); |
e1cc68bd | 1152 | free_data_refs (refs); |
1153 | free_dependence_relations (ddrs); | |
1154 | return res; | |
1155 | } | |
1156 | ||
fa683b76 | 1157 | /* Basic block BB has two predecessors. Using predecessor's bb |
1158 | predicate, set an appropriate condition COND for the PHI node | |
1159 | replacement. Return the true block whose phi arguments are | |
1160 | selected when cond is true. LOOP is the loop containing the | |
1161 | if-converted region, GSI is the place to insert the code for the | |
1162 | if-conversion. */ | |
07c03fb0 | 1163 | |
5f4df34e | 1164 | static basic_block |
48e1416a | 1165 | find_phi_replacement_condition (struct loop *loop, |
88dbf20f | 1166 | basic_block bb, tree *cond, |
3b91ccd9 | 1167 | gimple_stmt_iterator *gsi) |
07c03fb0 | 1168 | { |
58bc8309 | 1169 | edge first_edge, second_edge; |
0d734975 | 1170 | tree tmp_cond; |
07c03fb0 | 1171 | |
dea55b96 | 1172 | gcc_assert (EDGE_COUNT (bb->preds) == 2); |
58bc8309 | 1173 | first_edge = EDGE_PRED (bb, 0); |
1174 | second_edge = EDGE_PRED (bb, 1); | |
07c03fb0 | 1175 | |
dea55b96 | 1176 | /* Use condition based on following criteria: |
1177 | 1) | |
1178 | S1: x = !c ? a : b; | |
1179 | ||
1180 | S2: x = c ? b : a; | |
1181 | ||
1182 | S2 is preferred over S1. Make 'b' first_bb and use its condition. | |
48e1416a | 1183 | |
dea55b96 | 1184 | 2) Do not make loop header first_bb. |
1185 | ||
1186 | 3) | |
1187 | S1: x = !(c == d)? a : b; | |
1188 | ||
1189 | S21: t1 = c == d; | |
1190 | S22: x = t1 ? b : a; | |
1191 | ||
1192 | S3: x = (c == d) ? b : a; | |
1193 | ||
48e1416a | 1194 | S3 is preferred over S1 and S2*, Make 'b' first_bb and use |
58bc8309 | 1195 | its condition. |
663ac2be | 1196 | |
1197 | 4) If pred B is dominated by pred A then use pred B's condition. | |
1198 | See PR23115. */ | |
dea55b96 | 1199 | |
1200 | /* Select condition that is not TRUTH_NOT_EXPR. */ | |
fa683b76 | 1201 | tmp_cond = bb_predicate (first_edge->src); |
63a1777b | 1202 | gcc_assert (tmp_cond); |
1203 | ||
07c03fb0 | 1204 | if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) |
1205 | { | |
58bc8309 | 1206 | edge tmp_edge; |
1207 | ||
1208 | tmp_edge = first_edge; | |
1209 | first_edge = second_edge; | |
1210 | second_edge = tmp_edge; | |
07c03fb0 | 1211 | } |
dea55b96 | 1212 | |
663ac2be | 1213 | /* Check if FIRST_BB is loop header or not and make sure that |
1214 | FIRST_BB does not dominate SECOND_BB. */ | |
58bc8309 | 1215 | if (first_edge->src == loop->header |
1216 | || dominated_by_p (CDI_DOMINATORS, | |
1217 | second_edge->src, first_edge->src)) | |
07c03fb0 | 1218 | { |
fa683b76 | 1219 | *cond = bb_predicate (second_edge->src); |
58bc8309 | 1220 | |
58bc8309 | 1221 | if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) |
56db02b2 | 1222 | *cond = TREE_OPERAND (*cond, 0); |
88dbf20f | 1223 | else |
58bc8309 | 1224 | /* Select non loop header bb. */ |
1225 | first_edge = second_edge; | |
07c03fb0 | 1226 | } |
dea55b96 | 1227 | else |
fa683b76 | 1228 | *cond = bb_predicate (first_edge->src); |
35a40aad | 1229 | |
56db02b2 | 1230 | /* Gimplify the condition to a valid cond-expr conditonal operand. */ |
1231 | *cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (*cond), | |
1232 | is_gimple_condexpr, NULL_TREE, | |
1233 | true, GSI_SAME_STMT); | |
07c03fb0 | 1234 | |
58bc8309 | 1235 | return first_edge->src; |
07c03fb0 | 1236 | } |
1237 | ||
3b91ccd9 | 1238 | /* Replace a scalar PHI node with a COND_EXPR using COND as condition. |
1239 | This routine does not handle PHI nodes with more than two | |
1240 | arguments. | |
07c03fb0 | 1241 | |
07c03fb0 | 1242 | For example, |
10b55fcb | 1243 | S1: A = PHI <x1(1), x2(5)> |
07c03fb0 | 1244 | is converted into, |
1245 | S2: A = cond ? x1 : x2; | |
b01e3c9b | 1246 | |
1247 | The generated code is inserted at GSI that points to the top of | |
1248 | basic block's statement list. When COND is true, phi arg from | |
1249 | TRUE_BB is selected. */ | |
07c03fb0 | 1250 | |
1251 | static void | |
3b91ccd9 | 1252 | predicate_scalar_phi (gimple phi, tree cond, |
1253 | basic_block true_bb, | |
1254 | gimple_stmt_iterator *gsi) | |
07c03fb0 | 1255 | { |
75a70cf9 | 1256 | gimple new_stmt; |
07c03fb0 | 1257 | basic_block bb; |
119cb9ea | 1258 | tree rhs, res, arg, scev; |
07c03fb0 | 1259 | |
b01e3c9b | 1260 | gcc_assert (gimple_code (phi) == GIMPLE_PHI |
1261 | && gimple_phi_num_args (phi) == 2); | |
48e1416a | 1262 | |
3b91ccd9 | 1263 | res = gimple_phi_result (phi); |
1264 | /* Do not handle virtual phi nodes. */ | |
7c782c9b | 1265 | if (virtual_operand_p (res)) |
3b91ccd9 | 1266 | return; |
1267 | ||
75a70cf9 | 1268 | bb = gimple_bb (phi); |
07c03fb0 | 1269 | |
119cb9ea | 1270 | if ((arg = degenerate_phi_result (phi)) |
1271 | || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father, | |
1272 | res)) | |
1273 | && !chrec_contains_undetermined (scev) | |
1274 | && scev != res | |
1275 | && (arg = gimple_phi_arg_def (phi, 0)))) | |
9fc1b637 | 1276 | rhs = arg; |
07c03fb0 | 1277 | else |
1278 | { | |
9fc1b637 | 1279 | tree arg_0, arg_1; |
1280 | /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ | |
1281 | if (EDGE_PRED (bb, 1)->src == true_bb) | |
1282 | { | |
1283 | arg_0 = gimple_phi_arg_def (phi, 1); | |
1284 | arg_1 = gimple_phi_arg_def (phi, 0); | |
1285 | } | |
1286 | else | |
1287 | { | |
1288 | arg_0 = gimple_phi_arg_def (phi, 0); | |
1289 | arg_1 = gimple_phi_arg_def (phi, 1); | |
1290 | } | |
07c03fb0 | 1291 | |
5790abbc | 1292 | gcc_checking_assert (bb == bb->loop_father->header |
1293 | || bb_postdominates_preds (bb)); | |
1294 | ||
9fc1b637 | 1295 | /* Build new RHS using selected condition and arguments. */ |
3b91ccd9 | 1296 | rhs = build3 (COND_EXPR, TREE_TYPE (res), |
9fc1b637 | 1297 | unshare_expr (cond), arg_0, arg_1); |
1298 | } | |
07c03fb0 | 1299 | |
3b91ccd9 | 1300 | new_stmt = gimple_build_assign (res, rhs); |
75a70cf9 | 1301 | SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt; |
75a70cf9 | 1302 | gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); |
22aa74c4 | 1303 | update_stmt (new_stmt); |
07c03fb0 | 1304 | |
1305 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1306 | { | |
1307 | fprintf (dump_file, "new phi replacement stmt\n"); | |
75a70cf9 | 1308 | print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); |
07c03fb0 | 1309 | } |
1310 | } | |
1311 | ||
3b91ccd9 | 1312 | /* Replaces in LOOP all the scalar phi nodes other than those in the |
fa683b76 | 1313 | LOOP->header block with conditional modify expressions. */ |
07c03fb0 | 1314 | |
1315 | static void | |
3b91ccd9 | 1316 | predicate_all_scalar_phis (struct loop *loop) |
07c03fb0 | 1317 | { |
1318 | basic_block bb; | |
1319 | unsigned int orig_loop_num_nodes = loop->num_nodes; | |
1320 | unsigned int i; | |
1321 | ||
07c03fb0 | 1322 | for (i = 1; i < orig_loop_num_nodes; i++) |
1323 | { | |
75a70cf9 | 1324 | gimple phi; |
1325 | tree cond = NULL_TREE; | |
1326 | gimple_stmt_iterator gsi, phi_gsi; | |
5f4df34e | 1327 | basic_block true_bb = NULL; |
07c03fb0 | 1328 | bb = ifc_bbs[i]; |
35a40aad | 1329 | |
c077abad | 1330 | if (bb == loop->header) |
07c03fb0 | 1331 | continue; |
1332 | ||
75a70cf9 | 1333 | phi_gsi = gsi_start_phis (bb); |
fa683b76 | 1334 | if (gsi_end_p (phi_gsi)) |
1335 | continue; | |
07c03fb0 | 1336 | |
9cfdcdb1 | 1337 | /* BB has two predecessors. Using predecessor's aux field, set |
07c03fb0 | 1338 | appropriate condition for the PHI node replacement. */ |
fa683b76 | 1339 | gsi = gsi_after_labels (bb); |
1340 | true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi); | |
07c03fb0 | 1341 | |
75a70cf9 | 1342 | while (!gsi_end_p (phi_gsi)) |
07c03fb0 | 1343 | { |
75a70cf9 | 1344 | phi = gsi_stmt (phi_gsi); |
3b91ccd9 | 1345 | predicate_scalar_phi (phi, cond, true_bb, &gsi); |
07c03fb0 | 1346 | release_phi_node (phi); |
75a70cf9 | 1347 | gsi_next (&phi_gsi); |
07c03fb0 | 1348 | } |
fa683b76 | 1349 | |
75a70cf9 | 1350 | set_phi_nodes (bb, NULL); |
07c03fb0 | 1351 | } |
07c03fb0 | 1352 | } |
1353 | ||
fa683b76 | 1354 | /* Insert in each basic block of LOOP the statements produced by the |
1355 | gimplification of the predicates. */ | |
1356 | ||
1357 | static void | |
1358 | insert_gimplified_predicates (loop_p loop) | |
1359 | { | |
1360 | unsigned int i; | |
1361 | ||
1362 | for (i = 0; i < loop->num_nodes; i++) | |
1363 | { | |
1364 | basic_block bb = ifc_bbs[i]; | |
3b91ccd9 | 1365 | gimple_seq stmts; |
fa683b76 | 1366 | |
a560ff2b | 1367 | if (!is_predicated (bb)) |
1368 | { | |
1369 | /* Do not insert statements for a basic block that is not | |
1370 | predicated. Also make sure that the predicate of the | |
1371 | basic block is set to true. */ | |
1372 | reset_bb_predicate (bb); | |
1373 | continue; | |
1374 | } | |
1375 | ||
3b91ccd9 | 1376 | stmts = bb_predicate_gimplified_stmts (bb); |
fa683b76 | 1377 | if (stmts) |
1378 | { | |
3b91ccd9 | 1379 | if (flag_tree_loop_if_convert_stores) |
1380 | { | |
1381 | /* Insert the predicate of the BB just after the label, | |
1382 | as the if-conversion of memory writes will use this | |
1383 | predicate. */ | |
1384 | gimple_stmt_iterator gsi = gsi_after_labels (bb); | |
1385 | gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); | |
1386 | } | |
fa683b76 | 1387 | else |
3b91ccd9 | 1388 | { |
1389 | /* Insert the predicate of the BB at the end of the BB | |
1390 | as this would reduce the register pressure: the only | |
1391 | use of this predicate will be in successor BBs. */ | |
1392 | gimple_stmt_iterator gsi = gsi_last_bb (bb); | |
1393 | ||
1394 | if (gsi_end_p (gsi) | |
1395 | || stmt_ends_bb_p (gsi_stmt (gsi))) | |
1396 | gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); | |
1397 | else | |
1398 | gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT); | |
1399 | } | |
fa683b76 | 1400 | |
1401 | /* Once the sequence is code generated, set it to NULL. */ | |
1402 | set_bb_predicate_gimplified_stmts (bb, NULL); | |
1403 | } | |
1404 | } | |
1405 | } | |
1406 | ||
3b91ccd9 | 1407 | /* Predicate each write to memory in LOOP. |
1408 | ||
1409 | This function transforms control flow constructs containing memory | |
1410 | writes of the form: | |
1411 | ||
1412 | | for (i = 0; i < N; i++) | |
1413 | | if (cond) | |
1414 | | A[i] = expr; | |
1415 | ||
1416 | into the following form that does not contain control flow: | |
1417 | ||
1418 | | for (i = 0; i < N; i++) | |
1419 | | A[i] = cond ? expr : A[i]; | |
1420 | ||
1421 | The original CFG looks like this: | |
1422 | ||
1423 | | bb_0 | |
1424 | | i = 0 | |
1425 | | end_bb_0 | |
1426 | | | |
1427 | | bb_1 | |
1428 | | if (i < N) goto bb_5 else goto bb_2 | |
1429 | | end_bb_1 | |
1430 | | | |
1431 | | bb_2 | |
1432 | | cond = some_computation; | |
1433 | | if (cond) goto bb_3 else goto bb_4 | |
1434 | | end_bb_2 | |
1435 | | | |
1436 | | bb_3 | |
1437 | | A[i] = expr; | |
1438 | | goto bb_4 | |
1439 | | end_bb_3 | |
1440 | | | |
1441 | | bb_4 | |
1442 | | goto bb_1 | |
1443 | | end_bb_4 | |
1444 | ||
1445 | insert_gimplified_predicates inserts the computation of the COND | |
1446 | expression at the beginning of the destination basic block: | |
1447 | ||
1448 | | bb_0 | |
1449 | | i = 0 | |
1450 | | end_bb_0 | |
1451 | | | |
1452 | | bb_1 | |
1453 | | if (i < N) goto bb_5 else goto bb_2 | |
1454 | | end_bb_1 | |
1455 | | | |
1456 | | bb_2 | |
1457 | | cond = some_computation; | |
1458 | | if (cond) goto bb_3 else goto bb_4 | |
1459 | | end_bb_2 | |
1460 | | | |
1461 | | bb_3 | |
1462 | | cond = some_computation; | |
1463 | | A[i] = expr; | |
1464 | | goto bb_4 | |
1465 | | end_bb_3 | |
1466 | | | |
1467 | | bb_4 | |
1468 | | goto bb_1 | |
1469 | | end_bb_4 | |
1470 | ||
1471 | predicate_mem_writes is then predicating the memory write as follows: | |
1472 | ||
1473 | | bb_0 | |
1474 | | i = 0 | |
1475 | | end_bb_0 | |
1476 | | | |
1477 | | bb_1 | |
1478 | | if (i < N) goto bb_5 else goto bb_2 | |
1479 | | end_bb_1 | |
1480 | | | |
1481 | | bb_2 | |
1482 | | if (cond) goto bb_3 else goto bb_4 | |
1483 | | end_bb_2 | |
1484 | | | |
1485 | | bb_3 | |
1486 | | cond = some_computation; | |
1487 | | A[i] = cond ? expr : A[i]; | |
1488 | | goto bb_4 | |
1489 | | end_bb_3 | |
1490 | | | |
1491 | | bb_4 | |
1492 | | goto bb_1 | |
1493 | | end_bb_4 | |
1494 | ||
1495 | and finally combine_blocks removes the basic block boundaries making | |
1496 | the loop vectorizable: | |
1497 | ||
1498 | | bb_0 | |
1499 | | i = 0 | |
1500 | | if (i < N) goto bb_5 else goto bb_1 | |
1501 | | end_bb_0 | |
1502 | | | |
1503 | | bb_1 | |
1504 | | cond = some_computation; | |
1505 | | A[i] = cond ? expr : A[i]; | |
1506 | | if (i < N) goto bb_5 else goto bb_4 | |
1507 | | end_bb_1 | |
1508 | | | |
1509 | | bb_4 | |
1510 | | goto bb_1 | |
1511 | | end_bb_4 | |
1512 | */ | |
1513 | ||
1514 | static void | |
1515 | predicate_mem_writes (loop_p loop) | |
1516 | { | |
1517 | unsigned int i, orig_loop_num_nodes = loop->num_nodes; | |
1518 | ||
1519 | for (i = 1; i < orig_loop_num_nodes; i++) | |
1520 | { | |
1521 | gimple_stmt_iterator gsi; | |
1522 | basic_block bb = ifc_bbs[i]; | |
1523 | tree cond = bb_predicate (bb); | |
2df61941 | 1524 | bool swap; |
3b91ccd9 | 1525 | gimple stmt; |
1526 | ||
1527 | if (is_true_predicate (cond)) | |
1528 | continue; | |
1529 | ||
2df61941 | 1530 | swap = false; |
1531 | if (TREE_CODE (cond) == TRUTH_NOT_EXPR) | |
1532 | { | |
1533 | swap = true; | |
1534 | cond = TREE_OPERAND (cond, 0); | |
1535 | } | |
1536 | ||
3b91ccd9 | 1537 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
1538 | if ((stmt = gsi_stmt (gsi)) | |
1539 | && gimple_assign_single_p (stmt) | |
1540 | && gimple_vdef (stmt)) | |
1541 | { | |
1542 | tree lhs = gimple_assign_lhs (stmt); | |
1543 | tree rhs = gimple_assign_rhs1 (stmt); | |
1544 | tree type = TREE_TYPE (lhs); | |
1545 | ||
1546 | lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi); | |
1547 | rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi); | |
2df61941 | 1548 | if (swap) |
1549 | { | |
1550 | tree tem = lhs; | |
1551 | lhs = rhs; | |
1552 | rhs = tem; | |
1553 | } | |
1554 | cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond), | |
1555 | is_gimple_condexpr, NULL_TREE, | |
1556 | true, GSI_SAME_STMT); | |
3b91ccd9 | 1557 | rhs = build3 (COND_EXPR, type, unshare_expr (cond), rhs, lhs); |
1558 | gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi)); | |
1559 | update_stmt (stmt); | |
1560 | } | |
1561 | } | |
1562 | } | |
1563 | ||
01c40c0b | 1564 | /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks |
08129148 | 1565 | other than the exit and latch of the LOOP. Also resets the |
1566 | GIMPLE_DEBUG information. */ | |
01c40c0b | 1567 | |
1568 | static void | |
1569 | remove_conditions_and_labels (loop_p loop) | |
1570 | { | |
1571 | gimple_stmt_iterator gsi; | |
1572 | unsigned int i; | |
1573 | ||
1574 | for (i = 0; i < loop->num_nodes; i++) | |
1575 | { | |
fa683b76 | 1576 | basic_block bb = ifc_bbs[i]; |
01c40c0b | 1577 | |
1578 | if (bb_with_exit_edge_p (loop, bb) | |
1579 | || bb == loop->latch) | |
1580 | continue; | |
1581 | ||
1582 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) | |
08129148 | 1583 | switch (gimple_code (gsi_stmt (gsi))) |
1584 | { | |
1585 | case GIMPLE_COND: | |
1586 | case GIMPLE_LABEL: | |
1587 | gsi_remove (&gsi, true); | |
1588 | break; | |
1589 | ||
1590 | case GIMPLE_DEBUG: | |
1591 | /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ | |
1592 | if (gimple_debug_bind_p (gsi_stmt (gsi))) | |
1593 | { | |
1594 | gimple_debug_bind_reset_value (gsi_stmt (gsi)); | |
1595 | update_stmt (gsi_stmt (gsi)); | |
1596 | } | |
1597 | gsi_next (&gsi); | |
1598 | break; | |
1599 | ||
1600 | default: | |
1601 | gsi_next (&gsi); | |
1602 | } | |
01c40c0b | 1603 | } |
1604 | } | |
1605 | ||
9cfdcdb1 | 1606 | /* Combine all the basic blocks from LOOP into one or two super basic |
1607 | blocks. Replace PHI nodes with conditional modify expressions. */ | |
07c03fb0 | 1608 | |
1609 | static void | |
1610 | combine_blocks (struct loop *loop) | |
1611 | { | |
1612 | basic_block bb, exit_bb, merge_target_bb; | |
1613 | unsigned int orig_loop_num_nodes = loop->num_nodes; | |
1614 | unsigned int i; | |
71cfcaa2 | 1615 | edge e; |
1616 | edge_iterator ei; | |
fa717aca | 1617 | |
01c40c0b | 1618 | remove_conditions_and_labels (loop); |
fa683b76 | 1619 | insert_gimplified_predicates (loop); |
3b91ccd9 | 1620 | predicate_all_scalar_phis (loop); |
1621 | ||
1622 | if (flag_tree_loop_if_convert_stores) | |
1623 | predicate_mem_writes (loop); | |
07c03fb0 | 1624 | |
b01e3c9b | 1625 | /* Merge basic blocks: first remove all the edges in the loop, |
1626 | except for those from the exit block. */ | |
07c03fb0 | 1627 | exit_bb = NULL; |
71cfcaa2 | 1628 | for (i = 0; i < orig_loop_num_nodes; i++) |
1629 | { | |
1630 | bb = ifc_bbs[i]; | |
39760a87 | 1631 | free_bb_predicate (bb); |
71cfcaa2 | 1632 | if (bb_with_exit_edge_p (loop, bb)) |
1633 | { | |
53a87a4b | 1634 | gcc_assert (exit_bb == NULL); |
71cfcaa2 | 1635 | exit_bb = bb; |
71cfcaa2 | 1636 | } |
1637 | } | |
1638 | gcc_assert (exit_bb != loop->latch); | |
07c03fb0 | 1639 | |
07c03fb0 | 1640 | for (i = 1; i < orig_loop_num_nodes; i++) |
1641 | { | |
07c03fb0 | 1642 | bb = ifc_bbs[i]; |
1643 | ||
71cfcaa2 | 1644 | for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) |
07c03fb0 | 1645 | { |
71cfcaa2 | 1646 | if (e->src == exit_bb) |
1647 | ei_next (&ei); | |
1648 | else | |
1649 | remove_edge (e); | |
1650 | } | |
1651 | } | |
07c03fb0 | 1652 | |
71cfcaa2 | 1653 | if (exit_bb != NULL) |
1654 | { | |
1655 | if (exit_bb != loop->header) | |
1656 | { | |
b01e3c9b | 1657 | /* Connect this node to loop header. */ |
71cfcaa2 | 1658 | make_edge (loop->header, exit_bb, EDGE_FALLTHRU); |
1659 | set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); | |
07c03fb0 | 1660 | } |
1661 | ||
71cfcaa2 | 1662 | /* Redirect non-exit edges to loop->latch. */ |
1663 | FOR_EACH_EDGE (e, ei, exit_bb->succs) | |
1664 | { | |
1665 | if (!loop_exit_edge_p (loop, e)) | |
1666 | redirect_edge_and_branch (e, loop->latch); | |
1667 | } | |
1668 | set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); | |
1669 | } | |
1670 | else | |
1671 | { | |
b01e3c9b | 1672 | /* If the loop does not have an exit, reconnect header and latch. */ |
71cfcaa2 | 1673 | make_edge (loop->header, loop->latch, EDGE_FALLTHRU); |
1674 | set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); | |
1675 | } | |
c077abad | 1676 | |
71cfcaa2 | 1677 | merge_target_bb = loop->header; |
1678 | for (i = 1; i < orig_loop_num_nodes; i++) | |
1679 | { | |
75a70cf9 | 1680 | gimple_stmt_iterator gsi; |
1681 | gimple_stmt_iterator last; | |
46d1d560 | 1682 | |
71cfcaa2 | 1683 | bb = ifc_bbs[i]; |
65b9482a | 1684 | |
71cfcaa2 | 1685 | if (bb == exit_bb || bb == loop->latch) |
1686 | continue; | |
65b9482a | 1687 | |
01c40c0b | 1688 | /* Make stmts member of loop->header. */ |
1689 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
1690 | gimple_set_bb (gsi_stmt (gsi), merge_target_bb); | |
07c03fb0 | 1691 | |
1692 | /* Update stmt list. */ | |
75a70cf9 | 1693 | last = gsi_last_bb (merge_target_bb); |
1694 | gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT); | |
1695 | set_bb_seq (bb, NULL); | |
07c03fb0 | 1696 | |
88e6f696 | 1697 | delete_basic_block (bb); |
07c03fb0 | 1698 | } |
e9437a8f | 1699 | |
b01e3c9b | 1700 | /* If possible, merge loop header to the block with the exit edge. |
1701 | This reduces the number of basic blocks to two, to please the | |
b519e9db | 1702 | vectorizer that handles only loops with two nodes. */ |
c077abad | 1703 | if (exit_bb |
71cfcaa2 | 1704 | && exit_bb != loop->header |
1705 | && can_merge_blocks_p (loop->header, exit_bb)) | |
88e6f696 | 1706 | merge_blocks (loop->header, exit_bb); |
39760a87 | 1707 | |
1708 | free (ifc_bbs); | |
1709 | ifc_bbs = NULL; | |
821ac701 | 1710 | |
1711 | /* Post-dominators are corrupt now. */ | |
1712 | free_dominance_info (CDI_POST_DOMINATORS); | |
07c03fb0 | 1713 | } |
1714 | ||
dd3354aa | 1715 | /* If-convert LOOP when it is legal. For the moment this pass has no |
b519e9db | 1716 | profitability analysis. Returns true when something changed. */ |
07c03fb0 | 1717 | |
b519e9db | 1718 | static bool |
5ead86d3 | 1719 | tree_if_conversion (struct loop *loop) |
07c03fb0 | 1720 | { |
b519e9db | 1721 | bool changed = false; |
1055d96a | 1722 | ifc_bbs = NULL; |
07c03fb0 | 1723 | |
4bd0f929 | 1724 | if (!if_convertible_loop_p (loop) |
1725 | || !dbg_cnt (if_conversion_tree)) | |
60e0f7c4 | 1726 | goto cleanup; |
a1660ced | 1727 | |
60e0f7c4 | 1728 | /* Now all statements are if-convertible. Combine all the basic |
1729 | blocks into one huge basic block doing the if-conversion | |
1730 | on-the-fly. */ | |
1055d96a | 1731 | combine_blocks (loop); |
3b91ccd9 | 1732 | |
1733 | if (flag_tree_loop_if_convert_stores) | |
278611f2 | 1734 | mark_virtual_operands_for_renaming (cfun); |
3b91ccd9 | 1735 | |
b519e9db | 1736 | changed = true; |
07c03fb0 | 1737 | |
60e0f7c4 | 1738 | cleanup: |
60e0f7c4 | 1739 | if (ifc_bbs) |
1740 | { | |
fa683b76 | 1741 | unsigned int i; |
1742 | ||
1743 | for (i = 0; i < loop->num_nodes; i++) | |
1744 | free_bb_predicate (ifc_bbs[i]); | |
1745 | ||
60e0f7c4 | 1746 | free (ifc_bbs); |
1747 | ifc_bbs = NULL; | |
1748 | } | |
b519e9db | 1749 | |
1750 | return changed; | |
07c03fb0 | 1751 | } |
1752 | ||
1753 | /* Tree if-conversion pass management. */ | |
1754 | ||
2a1990e9 | 1755 | static unsigned int |
07c03fb0 | 1756 | main_tree_if_conversion (void) |
1757 | { | |
17519ba0 | 1758 | loop_iterator li; |
07c03fb0 | 1759 | struct loop *loop; |
b519e9db | 1760 | bool changed = false; |
3b91ccd9 | 1761 | unsigned todo = 0; |
07c03fb0 | 1762 | |
7a3bf727 | 1763 | if (number_of_loops () <= 1) |
2a1990e9 | 1764 | return 0; |
07c03fb0 | 1765 | |
17519ba0 | 1766 | FOR_EACH_LOOP (li, loop, 0) |
b519e9db | 1767 | changed |= tree_if_conversion (loop); |
5ead86d3 | 1768 | |
3b91ccd9 | 1769 | if (changed) |
1770 | todo |= TODO_cleanup_cfg; | |
1771 | ||
1772 | if (changed && flag_tree_loop_if_convert_stores) | |
1773 | todo |= TODO_update_ssa_only_virtuals; | |
1774 | ||
1d9199d5 | 1775 | free_dominance_info (CDI_POST_DOMINATORS); |
1776 | ||
53a87a4b | 1777 | #ifdef ENABLE_CHECKING |
630fd6e1 | 1778 | { |
1779 | basic_block bb; | |
1780 | FOR_EACH_BB (bb) | |
1781 | gcc_assert (!bb->aux); | |
1782 | } | |
53a87a4b | 1783 | #endif |
1784 | ||
3b91ccd9 | 1785 | return todo; |
07c03fb0 | 1786 | } |
1787 | ||
0cb1935d | 1788 | /* Returns true when the if-conversion pass is enabled. */ |
1789 | ||
07c03fb0 | 1790 | static bool |
1791 | gate_tree_if_conversion (void) | |
1792 | { | |
0cb1935d | 1793 | return ((flag_tree_vectorize && flag_tree_loop_if_convert != 0) |
3b91ccd9 | 1794 | || flag_tree_loop_if_convert == 1 |
1795 | || flag_tree_loop_if_convert_stores == 1); | |
07c03fb0 | 1796 | } |
1797 | ||
20099e35 | 1798 | struct gimple_opt_pass pass_if_conversion = |
07c03fb0 | 1799 | { |
20099e35 | 1800 | { |
1801 | GIMPLE_PASS, | |
88dbf20f | 1802 | "ifcvt", /* name */ |
1803 | gate_tree_if_conversion, /* gate */ | |
1804 | main_tree_if_conversion, /* execute */ | |
1805 | NULL, /* sub */ | |
1806 | NULL, /* next */ | |
1807 | 0, /* static_pass_number */ | |
0b1615c1 | 1808 | TV_NONE, /* tv_id */ |
2f8eb909 | 1809 | PROP_cfg | PROP_ssa, /* properties_required */ |
88dbf20f | 1810 | 0, /* properties_provided */ |
1811 | 0, /* properties_destroyed */ | |
1812 | 0, /* todo_flags_start */ | |
771e2890 | 1813 | TODO_verify_stmts | TODO_verify_flow |
dea55b96 | 1814 | /* todo_flags_finish */ |
20099e35 | 1815 | } |
07c03fb0 | 1816 | }; |