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