Branch data Line data Source code
1 : : /* If-conversion for vectorizer.
2 : : Copyright (C) 2004-2024 Free Software Foundation, Inc.
3 : : Contributed by Devang Patel <dpatel@apple.com>
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it under
8 : : the terms of the GNU General Public License as published by the Free
9 : : Software Foundation; either version 3, or (at your option) any later
10 : : version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : : for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
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.
24 : :
25 : : A short description of if-conversion:
26 : :
27 : : o Decide if a loop is if-convertible or not.
28 : : o Walk all loop basic blocks in breadth first order (BFS order).
29 : : o Remove conditional statements (at the end of basic block)
30 : : and propagate condition into destination basic blocks'
31 : : predicate list.
32 : : o Replace modify expression with conditional modify expression
33 : : using current basic block's condition.
34 : : o Merge all basic blocks
35 : : o Replace phi nodes with conditional modify expr
36 : : o Merge all basic blocks into header
37 : :
38 : : Sample transformation:
39 : :
40 : : INPUT
41 : : -----
42 : :
43 : : # i_23 = PHI <0(0), i_18(10)>;
44 : : <L0>:;
45 : : j_15 = A[i_23];
46 : : if (j_15 > 41) goto <L1>; else goto <L17>;
47 : :
48 : : <L17>:;
49 : : goto <bb 3> (<L3>);
50 : :
51 : : <L1>:;
52 : :
53 : : # iftmp.2_4 = PHI <0(8), 42(2)>;
54 : : <L3>:;
55 : : A[i_23] = iftmp.2_4;
56 : : i_18 = i_23 + 1;
57 : : if (i_18 <= 15) goto <L19>; else goto <L18>;
58 : :
59 : : <L19>:;
60 : : goto <bb 1> (<L0>);
61 : :
62 : : <L18>:;
63 : :
64 : : OUTPUT
65 : : ------
66 : :
67 : : # i_23 = PHI <0(0), i_18(10)>;
68 : : <L0>:;
69 : : j_15 = A[i_23];
70 : :
71 : : <L3>:;
72 : : iftmp.2_4 = j_15 > 41 ? 42 : 0;
73 : : A[i_23] = iftmp.2_4;
74 : : i_18 = i_23 + 1;
75 : : if (i_18 <= 15) goto <L19>; else goto <L18>;
76 : :
77 : : <L19>:;
78 : : goto <bb 1> (<L0>);
79 : :
80 : : <L18>:;
81 : : */
82 : :
83 : : #include "config.h"
84 : : #include "system.h"
85 : : #include "coretypes.h"
86 : : #include "backend.h"
87 : : #include "rtl.h"
88 : : #include "tree.h"
89 : : #include "gimple.h"
90 : : #include "cfghooks.h"
91 : : #include "tree-pass.h"
92 : : #include "ssa.h"
93 : : #include "expmed.h"
94 : : #include "expr.h"
95 : : #include "optabs-tree.h"
96 : : #include "gimple-pretty-print.h"
97 : : #include "alias.h"
98 : : #include "fold-const.h"
99 : : #include "stor-layout.h"
100 : : #include "gimple-iterator.h"
101 : : #include "gimple-fold.h"
102 : : #include "gimplify.h"
103 : : #include "gimplify-me.h"
104 : : #include "tree-cfg.h"
105 : : #include "tree-into-ssa.h"
106 : : #include "tree-ssa.h"
107 : : #include "cfgloop.h"
108 : : #include "tree-data-ref.h"
109 : : #include "tree-scalar-evolution.h"
110 : : #include "tree-ssa-loop.h"
111 : : #include "tree-ssa-loop-niter.h"
112 : : #include "tree-ssa-loop-ivopts.h"
113 : : #include "tree-ssa-address.h"
114 : : #include "dbgcnt.h"
115 : : #include "tree-hash-traits.h"
116 : : #include "varasm.h"
117 : : #include "builtins.h"
118 : : #include "cfganal.h"
119 : : #include "internal-fn.h"
120 : : #include "fold-const.h"
121 : : #include "tree-ssa-sccvn.h"
122 : : #include "tree-cfgcleanup.h"
123 : : #include "tree-ssa-dse.h"
124 : : #include "tree-vectorizer.h"
125 : : #include "tree-eh.h"
126 : : #include "cgraph.h"
127 : :
128 : : /* For lang_hooks.types.type_for_mode. */
129 : : #include "langhooks.h"
130 : :
131 : : /* Only handle PHIs with no more arguments unless we are asked to by
132 : : simd pragma. */
133 : : #define MAX_PHI_ARG_NUM \
134 : : ((unsigned) param_max_tree_if_conversion_phi_args)
135 : :
136 : : /* True if we've converted a statement that was only executed when some
137 : : condition C was true, and if for correctness we need to predicate the
138 : : statement to ensure that it is a no-op when C is false. See
139 : : predicate_statements for the kinds of predication we support. */
140 : : static bool need_to_predicate;
141 : :
142 : : /* True if we have to rewrite stmts that may invoke undefined behavior
143 : : when a condition C was false so it doesn't if it is always executed.
144 : : See predicate_statements for the kinds of predication we support. */
145 : : static bool need_to_rewrite_undefined;
146 : :
147 : : /* Indicate if there are any complicated PHIs that need to be handled in
148 : : if-conversion. Complicated PHI has more than two arguments and can't
149 : : be degenerated to two arguments PHI. See more information in comment
150 : : before phi_convertible_by_degenerating_args. */
151 : : static bool any_complicated_phi;
152 : :
153 : : /* True if we have bitfield accesses we can lower. */
154 : : static bool need_to_lower_bitfields;
155 : :
156 : : /* True if there is any ifcvting to be done. */
157 : : static bool need_to_ifcvt;
158 : :
159 : : /* Hash for struct innermost_loop_behavior. It depends on the user to
160 : : free the memory. */
161 : :
162 : : struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior>
163 : : {
164 : : static inline hashval_t hash (const value_type &);
165 : : static inline bool equal (const value_type &,
166 : : const compare_type &);
167 : : };
168 : :
169 : : inline hashval_t
170 : 353146 : innermost_loop_behavior_hash::hash (const value_type &e)
171 : : {
172 : 353146 : hashval_t hash;
173 : :
174 : 353146 : hash = iterative_hash_expr (e->base_address, 0);
175 : 353146 : hash = iterative_hash_expr (e->offset, hash);
176 : 353146 : hash = iterative_hash_expr (e->init, hash);
177 : 353146 : return iterative_hash_expr (e->step, hash);
178 : : }
179 : :
180 : : inline bool
181 : 251067 : innermost_loop_behavior_hash::equal (const value_type &e1,
182 : : const compare_type &e2)
183 : : {
184 : 251067 : if ((e1->base_address && !e2->base_address)
185 : 251067 : || (!e1->base_address && e2->base_address)
186 : 251067 : || (!e1->offset && e2->offset)
187 : 231496 : || (e1->offset && !e2->offset)
188 : 201580 : || (!e1->init && e2->init)
189 : 201580 : || (e1->init && !e2->init)
190 : 201580 : || (!e1->step && e2->step)
191 : 201580 : || (e1->step && !e2->step))
192 : : return false;
193 : :
194 : 201580 : if (e1->base_address && e2->base_address
195 : 403160 : && !operand_equal_p (e1->base_address, e2->base_address, 0))
196 : : return false;
197 : 32167 : if (e1->offset && e2->offset
198 : 95354 : && !operand_equal_p (e1->offset, e2->offset, 0))
199 : : return false;
200 : 31942 : if (e1->init && e2->init
201 : 94904 : && !operand_equal_p (e1->init, e2->init, 0))
202 : : return false;
203 : 15196 : if (e1->step && e2->step
204 : 61412 : && !operand_equal_p (e1->step, e2->step, 0))
205 : : return false;
206 : :
207 : : return true;
208 : : }
209 : :
210 : : /* List of basic blocks in if-conversion-suitable order. */
211 : : static basic_block *ifc_bbs;
212 : :
213 : : /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
214 : : static hash_map<innermost_loop_behavior_hash,
215 : : data_reference_p> *innermost_DR_map;
216 : :
217 : : /* Hash table to store <base reference, DR> pairs. */
218 : : static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map;
219 : :
220 : : /* List of redundant SSA names: the first should be replaced by the second. */
221 : : static vec< std::pair<tree, tree> > redundant_ssa_names;
222 : :
223 : : /* Structure used to predicate basic blocks. This is attached to the
224 : : ->aux field of the BBs in the loop to be if-converted. */
225 : : struct bb_predicate {
226 : :
227 : : /* The condition under which this basic block is executed. */
228 : : tree predicate;
229 : :
230 : : /* PREDICATE is gimplified, and the sequence of statements is
231 : : recorded here, in order to avoid the duplication of computations
232 : : that occur in previous conditions. See PR44483. */
233 : : gimple_seq predicate_gimplified_stmts;
234 : :
235 : : /* Records the number of statements recorded into
236 : : PREDICATE_GIMPLIFIED_STMTS. */
237 : : unsigned no_predicate_stmts;
238 : : };
239 : :
240 : : /* Returns true when the basic block BB has a predicate. */
241 : :
242 : : static inline bool
243 : 1700077 : bb_has_predicate (basic_block bb)
244 : : {
245 : 1700077 : return bb->aux != NULL;
246 : : }
247 : :
248 : : /* Returns the gimplified predicate for basic block BB. */
249 : :
250 : : static inline tree
251 : 698408 : bb_predicate (basic_block bb)
252 : : {
253 : 698408 : return ((struct bb_predicate *) bb->aux)->predicate;
254 : : }
255 : :
256 : : /* Sets the gimplified predicate COND for basic block BB. */
257 : :
258 : : static inline void
259 : 381948 : set_bb_predicate (basic_block bb, tree cond)
260 : : {
261 : 381948 : auto aux = (struct bb_predicate *) bb->aux;
262 : 381948 : gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
263 : : && is_gimple_val (TREE_OPERAND (cond, 0)))
264 : : || is_gimple_val (cond));
265 : 381948 : aux->predicate = cond;
266 : 381948 : aux->no_predicate_stmts++;
267 : :
268 : 381948 : if (dump_file && (dump_flags & TDF_DETAILS))
269 : 198 : fprintf (dump_file, "Recording block %d value %d\n", bb->index,
270 : : aux->no_predicate_stmts);
271 : 381948 : }
272 : :
273 : : /* Returns the sequence of statements of the gimplification of the
274 : : predicate for basic block BB. */
275 : :
276 : : static inline gimple_seq
277 : 472207 : bb_predicate_gimplified_stmts (basic_block bb)
278 : : {
279 : 472207 : return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts;
280 : : }
281 : :
282 : : /* Sets the sequence of statements STMTS of the gimplification of the
283 : : predicate for basic block BB. If PRESERVE_COUNTS then don't clear the predicate
284 : : counts. */
285 : :
286 : : static inline void
287 : 222597 : set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts,
288 : : bool preserve_counts)
289 : : {
290 : 222597 : ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts;
291 : 222597 : if (stmts == NULL && !preserve_counts)
292 : 181590 : ((struct bb_predicate *) bb->aux)->no_predicate_stmts = 0;
293 : 64785 : }
294 : :
295 : : /* Adds the sequence of statements STMTS to the sequence of statements
296 : : of the predicate for basic block BB. */
297 : :
298 : : static inline void
299 : 66106 : add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
300 : : {
301 : : /* We might have updated some stmts in STMTS via force_gimple_operand
302 : : calling fold_stmt and that producing multiple stmts. Delink immediate
303 : : uses so update_ssa after loop versioning doesn't get confused for
304 : : the not yet inserted predicates.
305 : : ??? This should go away once we reliably avoid updating stmts
306 : : not in any BB. */
307 : 66106 : for (gimple_stmt_iterator gsi = gsi_start (stmts);
308 : 160370 : !gsi_end_p (gsi); gsi_next (&gsi))
309 : : {
310 : 94264 : gimple *stmt = gsi_stmt (gsi);
311 : 94264 : delink_stmt_imm_use (stmt);
312 : 94264 : gimple_set_modified (stmt, true);
313 : 94264 : ((struct bb_predicate *) bb->aux)->no_predicate_stmts++;
314 : : }
315 : 66106 : gimple_seq_add_seq_without_update
316 : 66106 : (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts);
317 : 66106 : }
318 : :
319 : : /* Return the number of statements the predicate of the basic block consists
320 : : of. */
321 : :
322 : : static inline unsigned
323 : 15293 : get_bb_num_predicate_stmts (basic_block bb)
324 : : {
325 : 15293 : return ((struct bb_predicate *) bb->aux)->no_predicate_stmts;
326 : : }
327 : :
328 : : /* Initializes to TRUE the predicate of basic block BB. */
329 : :
330 : : static inline void
331 : 157812 : init_bb_predicate (basic_block bb)
332 : : {
333 : 157812 : bb->aux = XNEW (struct bb_predicate);
334 : 157812 : set_bb_predicate_gimplified_stmts (bb, NULL, false);
335 : 157812 : set_bb_predicate (bb, boolean_true_node);
336 : 157812 : }
337 : :
338 : : /* Release the SSA_NAMEs associated with the predicate of basic block BB. */
339 : :
340 : : static inline void
341 : 309016 : release_bb_predicate (basic_block bb)
342 : : {
343 : 309016 : gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
344 : 309016 : if (stmts)
345 : : {
346 : : /* Ensure that these stmts haven't yet been added to a bb. */
347 : 23778 : if (flag_checking)
348 : : for (gimple_stmt_iterator i = gsi_start (stmts);
349 : 63673 : !gsi_end_p (i); gsi_next (&i))
350 : 39895 : gcc_assert (! gimple_bb (gsi_stmt (i)));
351 : :
352 : : /* Discard them. */
353 : 23778 : gimple_seq_discard (stmts);
354 : 23778 : set_bb_predicate_gimplified_stmts (bb, NULL, false);
355 : : }
356 : 309016 : }
357 : :
358 : : /* Free the predicate of basic block BB. */
359 : :
360 : : static inline void
361 : 1548873 : free_bb_predicate (basic_block bb)
362 : : {
363 : 1548873 : if (!bb_has_predicate (bb))
364 : : return;
365 : :
366 : 157812 : release_bb_predicate (bb);
367 : 157812 : free (bb->aux);
368 : 157812 : bb->aux = NULL;
369 : : }
370 : :
371 : : /* Reinitialize predicate of BB with the true predicate. */
372 : :
373 : : static inline void
374 : 151204 : reset_bb_predicate (basic_block bb)
375 : : {
376 : 151204 : if (!bb_has_predicate (bb))
377 : 0 : init_bb_predicate (bb);
378 : : else
379 : : {
380 : 151204 : release_bb_predicate (bb);
381 : 151204 : set_bb_predicate (bb, boolean_true_node);
382 : : }
383 : 151204 : }
384 : :
385 : : /* Returns a new SSA_NAME of type TYPE that is assigned the value of
386 : : the expression EXPR. Inserts the statement created for this
387 : : computation before GSI and leaves the iterator GSI at the same
388 : : statement. */
389 : :
390 : : static tree
391 : 2439 : ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
392 : : {
393 : 2439 : tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
394 : 2439 : gimple *stmt = gimple_build_assign (new_name, expr);
395 : 4878 : gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi)));
396 : 2439 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
397 : 2439 : return new_name;
398 : : }
399 : :
400 : : /* Return true when COND is a false predicate. */
401 : :
402 : : static inline bool
403 : 56569 : is_false_predicate (tree cond)
404 : : {
405 : 56569 : return (cond != NULL_TREE
406 : 56569 : && (cond == boolean_false_node
407 : 56569 : || integer_zerop (cond)));
408 : : }
409 : :
410 : : /* Return true when COND is a true predicate. */
411 : :
412 : : static inline bool
413 : 824061 : is_true_predicate (tree cond)
414 : : {
415 : 824061 : return (cond == NULL_TREE
416 : 824061 : || cond == boolean_true_node
417 : 1187661 : || integer_onep (cond));
418 : : }
419 : :
420 : : /* Returns true when BB has a predicate that is not trivial: true or
421 : : NULL_TREE. */
422 : :
423 : : static inline bool
424 : 388883 : is_predicated (basic_block bb)
425 : : {
426 : 7662 : return !is_true_predicate (bb_predicate (bb));
427 : : }
428 : :
429 : : /* Parses the predicate COND and returns its comparison code and
430 : : operands OP0 and OP1. */
431 : :
432 : : static enum tree_code
433 : 370904 : parse_predicate (tree cond, tree *op0, tree *op1)
434 : : {
435 : 370904 : gimple *s;
436 : :
437 : 370904 : if (TREE_CODE (cond) == SSA_NAME
438 : 370904 : && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
439 : : {
440 : 52996 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
441 : : {
442 : 26407 : *op0 = gimple_assign_rhs1 (s);
443 : 26407 : *op1 = gimple_assign_rhs2 (s);
444 : 26407 : return gimple_assign_rhs_code (s);
445 : : }
446 : :
447 : 26589 : else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
448 : : {
449 : 0 : tree op = gimple_assign_rhs1 (s);
450 : 0 : tree type = TREE_TYPE (op);
451 : 0 : enum tree_code code = parse_predicate (op, op0, op1);
452 : :
453 : 0 : return code == ERROR_MARK ? ERROR_MARK
454 : 0 : : invert_tree_comparison (code, HONOR_NANS (type));
455 : : }
456 : :
457 : : return ERROR_MARK;
458 : : }
459 : :
460 : 317908 : if (COMPARISON_CLASS_P (cond))
461 : : {
462 : 619 : *op0 = TREE_OPERAND (cond, 0);
463 : 619 : *op1 = TREE_OPERAND (cond, 1);
464 : 619 : return TREE_CODE (cond);
465 : : }
466 : :
467 : : return ERROR_MARK;
468 : : }
469 : :
470 : : /* Returns the fold of predicate C1 OR C2 at location LOC. */
471 : :
472 : : static tree
473 : 185452 : fold_or_predicates (location_t loc, tree c1, tree c2)
474 : : {
475 : 185452 : tree op1a, op1b, op2a, op2b;
476 : 185452 : enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
477 : 185452 : enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
478 : :
479 : 185452 : if (code1 != ERROR_MARK && code2 != ERROR_MARK)
480 : : {
481 : 2121 : tree t = maybe_fold_or_comparisons (boolean_type_node, code1, op1a, op1b,
482 : : code2, op2a, op2b);
483 : 2121 : if (t)
484 : : return t;
485 : : }
486 : :
487 : 183404 : return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
488 : : }
489 : :
490 : : /* Returns either a COND_EXPR or the folded expression if the folded
491 : : expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
492 : : a constant or a SSA_NAME. */
493 : :
494 : : static tree
495 : 32586 : fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
496 : : {
497 : : /* If COND is comparison r != 0 and r has boolean type, convert COND
498 : : to SSA_NAME to accept by vect bool pattern. */
499 : 32586 : if (TREE_CODE (cond) == NE_EXPR)
500 : : {
501 : 0 : tree op0 = TREE_OPERAND (cond, 0);
502 : 0 : tree op1 = TREE_OPERAND (cond, 1);
503 : 0 : if (TREE_CODE (op0) == SSA_NAME
504 : 0 : && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
505 : 0 : && (integer_zerop (op1)))
506 : : cond = op0;
507 : : }
508 : :
509 : 32586 : gimple_match_op cexpr (gimple_match_cond::UNCOND, COND_EXPR,
510 : 32586 : type, cond, rhs, lhs);
511 : 32586 : if (cexpr.resimplify (NULL, follow_all_ssa_edges))
512 : : {
513 : 2966 : if (gimple_simplified_result_is_gimple_val (&cexpr))
514 : 513 : return cexpr.ops[0];
515 : 2453 : else if (cexpr.code == ABS_EXPR)
516 : 2 : return build1 (ABS_EXPR, type, cexpr.ops[0]);
517 : 2451 : else if (cexpr.code == MIN_EXPR
518 : 2451 : || cexpr.code == MAX_EXPR)
519 : 0 : return build2 ((tree_code)cexpr.code, type, cexpr.ops[0], cexpr.ops[1]);
520 : : }
521 : :
522 : 32071 : return build3 (COND_EXPR, type, cond, rhs, lhs);
523 : : }
524 : :
525 : : /* Add condition NC to the predicate list of basic block BB. LOOP is
526 : : the loop to be if-converted. Use predicate of cd-equivalent block
527 : : for join bb if it exists: we call basic blocks bb1 and bb2
528 : : cd-equivalent if they are executed under the same condition. */
529 : :
530 : : static inline void
531 : 124669 : add_to_predicate_list (class loop *loop, basic_block bb, tree nc)
532 : : {
533 : 124669 : tree bc, *tp;
534 : 124669 : basic_block dom_bb;
535 : :
536 : 124669 : if (is_true_predicate (nc))
537 : 57245 : return;
538 : :
539 : : /* If dominance tells us this basic block is always executed,
540 : : don't record any predicates for it. */
541 : 124667 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
542 : : return;
543 : :
544 : 72932 : dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
545 : : /* We use notion of cd equivalence to get simpler predicate for
546 : : join block, e.g. if join block has 2 predecessors with predicates
547 : : p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
548 : : p1 & p2 | p1 & !p2. */
549 : 72932 : if (dom_bb != loop->header
550 : 72932 : && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
551 : : {
552 : 5508 : gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
553 : 5508 : bc = bb_predicate (dom_bb);
554 : 5508 : if (!is_true_predicate (bc))
555 : 5508 : set_bb_predicate (bb, bc);
556 : : else
557 : 0 : gcc_assert (is_true_predicate (bb_predicate (bb)));
558 : 5508 : if (dump_file && (dump_flags & TDF_DETAILS))
559 : 4 : fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
560 : : dom_bb->index, bb->index);
561 : 5508 : return;
562 : : }
563 : :
564 : 67424 : if (!is_predicated (bb))
565 : 64785 : bc = nc;
566 : : else
567 : : {
568 : 2639 : bc = bb_predicate (bb);
569 : 2639 : bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
570 : 2639 : if (is_true_predicate (bc))
571 : : {
572 : 0 : reset_bb_predicate (bb);
573 : 0 : return;
574 : : }
575 : : }
576 : :
577 : : /* Allow a TRUTH_NOT_EXPR around the main predicate. */
578 : 67424 : if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
579 : 24225 : tp = &TREE_OPERAND (bc, 0);
580 : : else
581 : : tp = &bc;
582 : 67424 : if (!is_gimple_val (*tp))
583 : : {
584 : 66106 : gimple_seq stmts;
585 : 66106 : *tp = force_gimple_operand (*tp, &stmts, true, NULL_TREE);
586 : 66106 : add_bb_predicate_gimplified_stmts (bb, stmts);
587 : : }
588 : 67424 : set_bb_predicate (bb, bc);
589 : : }
590 : :
591 : : /* Add the condition COND to the previous condition PREV_COND, and add
592 : : this to the predicate list of the destination of edge E. LOOP is
593 : : the loop to be if-converted. */
594 : :
595 : : static void
596 : 80726 : add_to_dst_predicate_list (class loop *loop, edge e,
597 : : tree prev_cond, tree cond)
598 : : {
599 : 80726 : if (!flow_bb_inside_loop_p (loop, e->dest))
600 : : return;
601 : :
602 : 80726 : if (!is_true_predicate (prev_cond))
603 : 17308 : cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
604 : : prev_cond, cond);
605 : :
606 : 80726 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
607 : 65812 : add_to_predicate_list (loop, e->dest, cond);
608 : : }
609 : :
610 : : /* Return true if one of the successor edges of BB exits LOOP. */
611 : :
612 : : static bool
613 : 2991840 : bb_with_exit_edge_p (const class loop *loop, basic_block bb)
614 : : {
615 : 2991840 : edge e;
616 : 2991840 : edge_iterator ei;
617 : :
618 : 5987262 : FOR_EACH_EDGE (e, ei, bb->succs)
619 : 4222717 : if (loop_exit_edge_p (loop, e))
620 : : return true;
621 : :
622 : : return false;
623 : : }
624 : :
625 : : /* Given PHI which has more than two arguments, this function checks if
626 : : it's if-convertible by degenerating its arguments. Specifically, if
627 : : below two conditions are satisfied:
628 : :
629 : : 1) Number of PHI arguments with different values equals to 2 and one
630 : : argument has the only occurrence.
631 : : 2) The edge corresponding to the unique argument isn't critical edge.
632 : :
633 : : Such PHI can be handled as PHIs have only two arguments. For example,
634 : : below PHI:
635 : :
636 : : res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
637 : :
638 : : can be transformed into:
639 : :
640 : : res = (predicate of e3) ? A_2 : A_1;
641 : :
642 : : Return TRUE if it is the case, FALSE otherwise. */
643 : :
644 : : static bool
645 : 5227 : phi_convertible_by_degenerating_args (gphi *phi)
646 : : {
647 : 5227 : edge e;
648 : 5227 : tree arg, t1 = NULL, t2 = NULL;
649 : 5227 : unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0;
650 : 5227 : unsigned int num_args = gimple_phi_num_args (phi);
651 : :
652 : 5227 : gcc_assert (num_args > 2);
653 : :
654 : 18823 : for (i = 0; i < num_args; i++)
655 : : {
656 : 15785 : arg = gimple_phi_arg_def (phi, i);
657 : 15785 : if (t1 == NULL || operand_equal_p (t1, arg, 0))
658 : : {
659 : 8168 : n1++;
660 : 8168 : i1 = i;
661 : 8168 : t1 = arg;
662 : : }
663 : 7617 : else if (t2 == NULL || operand_equal_p (t2, arg, 0))
664 : : {
665 : 5428 : n2++;
666 : 5428 : i2 = i;
667 : 5428 : t2 = arg;
668 : : }
669 : : else
670 : : return false;
671 : : }
672 : :
673 : 3038 : if (n1 != 1 && n2 != 1)
674 : : return false;
675 : :
676 : : /* Check if the edge corresponding to the unique arg is critical. */
677 : 2999 : e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2);
678 : 2999 : if (EDGE_COUNT (e->src->succs) > 1)
679 : : return false;
680 : :
681 : : return true;
682 : : }
683 : :
684 : : /* Return true when PHI is if-convertible. PHI is part of loop LOOP
685 : : and it belongs to basic block BB. Note at this point, it is sure
686 : : that PHI is if-convertible. This function updates global variable
687 : : ANY_COMPLICATED_PHI if PHI is complicated. */
688 : :
689 : : static bool
690 : 92063 : if_convertible_phi_p (class loop *loop, basic_block bb, gphi *phi)
691 : : {
692 : 92063 : if (dump_file && (dump_flags & TDF_DETAILS))
693 : : {
694 : 60 : fprintf (dump_file, "-------------------------\n");
695 : 60 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
696 : : }
697 : :
698 : 92063 : if (bb != loop->header
699 : 33152 : && gimple_phi_num_args (phi) > 2
700 : 97290 : && !phi_convertible_by_degenerating_args (phi))
701 : 2228 : any_complicated_phi = true;
702 : :
703 : 92063 : return true;
704 : : }
705 : :
706 : : /* Records the status of a data reference. This struct is attached to
707 : : each DR->aux field. */
708 : :
709 : : struct ifc_dr {
710 : : bool rw_unconditionally;
711 : : bool w_unconditionally;
712 : : bool written_at_least_once;
713 : :
714 : : tree rw_predicate;
715 : : tree w_predicate;
716 : : tree base_w_predicate;
717 : : };
718 : :
719 : : #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
720 : : #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
721 : : #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
722 : : #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
723 : :
724 : : /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
725 : : HASH tables. While storing them in HASH table, it checks if the
726 : : reference is unconditionally read or written and stores that as a flag
727 : : information. For base reference it checks if it is written atlest once
728 : : unconditionally and stores it as flag information along with DR.
729 : : In other words for every data reference A in STMT there exist other
730 : : accesses to a data reference with the same base with predicates that
731 : : add up (OR-up) to the true predicate: this ensures that the data
732 : : reference A is touched (read or written) on every iteration of the
733 : : if-converted loop. */
734 : : static void
735 : 108139 : hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a)
736 : : {
737 : :
738 : 108139 : data_reference_p *master_dr, *base_master_dr;
739 : 108139 : tree base_ref = DR_BASE_OBJECT (a);
740 : 108139 : innermost_loop_behavior *innermost = &DR_INNERMOST (a);
741 : 108139 : tree ca = bb_predicate (gimple_bb (DR_STMT (a)));
742 : 108139 : bool exist1, exist2;
743 : :
744 : 108139 : master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1);
745 : 108139 : if (!exist1)
746 : 78350 : *master_dr = a;
747 : :
748 : 108139 : if (DR_IS_WRITE (a))
749 : : {
750 : 37318 : IFC_DR (*master_dr)->w_predicate
751 : 74636 : = fold_or_predicates (UNKNOWN_LOCATION, ca,
752 : 37318 : IFC_DR (*master_dr)->w_predicate);
753 : 37318 : if (is_true_predicate (IFC_DR (*master_dr)->w_predicate))
754 : 23164 : DR_W_UNCONDITIONALLY (*master_dr) = true;
755 : : }
756 : 108139 : IFC_DR (*master_dr)->rw_predicate
757 : 216278 : = fold_or_predicates (UNKNOWN_LOCATION, ca,
758 : 108139 : IFC_DR (*master_dr)->rw_predicate);
759 : 108139 : if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate))
760 : 78376 : DR_RW_UNCONDITIONALLY (*master_dr) = true;
761 : :
762 : 108139 : if (DR_IS_WRITE (a))
763 : : {
764 : 37318 : base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2);
765 : 37318 : if (!exist2)
766 : 28455 : *base_master_dr = a;
767 : 37318 : IFC_DR (*base_master_dr)->base_w_predicate
768 : 74636 : = fold_or_predicates (UNKNOWN_LOCATION, ca,
769 : 37318 : IFC_DR (*base_master_dr)->base_w_predicate);
770 : 37318 : if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate))
771 : 23388 : DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true;
772 : : }
773 : 108139 : }
774 : :
775 : : /* Return TRUE if can prove the index IDX of an array reference REF is
776 : : within array bound. Return false otherwise. */
777 : :
778 : : static bool
779 : 125641 : idx_within_array_bound (tree ref, tree *idx, void *dta)
780 : : {
781 : 125641 : wi::overflow_type overflow;
782 : 125641 : widest_int niter, valid_niter, delta, wi_step;
783 : 125641 : tree ev, init, step;
784 : 125641 : tree low, high;
785 : 125641 : class loop *loop = (class loop*) dta;
786 : :
787 : : /* Only support within-bound access for array references. */
788 : 125641 : if (TREE_CODE (ref) != ARRAY_REF)
789 : : return false;
790 : :
791 : : /* For arrays that might have flexible sizes, it is not guaranteed that they
792 : : do not extend over their declared size. */
793 : 87429 : if (array_ref_flexible_size_p (ref))
794 : : return false;
795 : :
796 : 69092 : ev = analyze_scalar_evolution (loop, *idx);
797 : 69092 : ev = instantiate_parameters (loop, ev);
798 : 69092 : init = initial_condition (ev);
799 : 69092 : step = evolution_part_in_loop_num (ev, loop->num);
800 : :
801 : 69092 : if (!init || TREE_CODE (init) != INTEGER_CST
802 : 64224 : || (step && TREE_CODE (step) != INTEGER_CST))
803 : : return false;
804 : :
805 : 64224 : low = array_ref_low_bound (ref);
806 : 64224 : high = array_ref_up_bound (ref);
807 : :
808 : : /* The case of nonconstant bounds could be handled, but it would be
809 : : complicated. */
810 : 64224 : if (TREE_CODE (low) != INTEGER_CST
811 : 64224 : || !high || TREE_CODE (high) != INTEGER_CST)
812 : : return false;
813 : :
814 : : /* Check if the intial idx is within bound. */
815 : 64197 : if (wi::to_widest (init) < wi::to_widest (low)
816 : 128387 : || wi::to_widest (init) > wi::to_widest (high))
817 : 14 : return false;
818 : :
819 : : /* The idx is always within bound. */
820 : 64183 : if (!step || integer_zerop (step))
821 : 846 : return true;
822 : :
823 : 63337 : if (!max_loop_iterations (loop, &niter))
824 : : return false;
825 : :
826 : 63337 : if (wi::to_widest (step) < 0)
827 : : {
828 : 299 : delta = wi::to_widest (init) - wi::to_widest (low);
829 : 299 : wi_step = -wi::to_widest (step);
830 : : }
831 : : else
832 : : {
833 : 63038 : delta = wi::to_widest (high) - wi::to_widest (init);
834 : 63038 : wi_step = wi::to_widest (step);
835 : : }
836 : :
837 : 63337 : valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow);
838 : : /* The iteration space of idx is within array bound. */
839 : 126674 : if (!overflow && niter <= valid_niter)
840 : : return true;
841 : :
842 : : return false;
843 : 125641 : }
844 : :
845 : : /* Return TRUE if ref is a within bound array reference. */
846 : :
847 : : bool
848 : 122593 : ref_within_array_bound (gimple *stmt, tree ref)
849 : : {
850 : 122593 : class loop *loop = loop_containing_stmt (stmt);
851 : :
852 : 122593 : gcc_assert (loop != NULL);
853 : 122593 : return for_each_index (&ref, idx_within_array_bound, loop);
854 : : }
855 : :
856 : :
857 : : /* Given a memory reference expression T, return TRUE if base object
858 : : it refers to is writable. The base object of a memory reference
859 : : is the main object being referenced, which is returned by function
860 : : get_base_address. */
861 : :
862 : : static bool
863 : 1740 : base_object_writable (tree ref)
864 : : {
865 : 1740 : tree base_tree = get_base_address (ref);
866 : :
867 : 1740 : return (base_tree
868 : 1740 : && DECL_P (base_tree)
869 : 1425 : && decl_binds_to_current_def_p (base_tree)
870 : 3162 : && !TREE_READONLY (base_tree));
871 : : }
872 : :
873 : : /* Return true when the memory references of STMT won't trap in the
874 : : if-converted code. There are two things that we have to check for:
875 : :
876 : : - writes to memory occur to writable memory: if-conversion of
877 : : memory writes transforms the conditional memory writes into
878 : : unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
879 : : into "A[i] = cond ? foo : A[i]", and as the write to memory may not
880 : : be executed at all in the original code, it may be a readonly
881 : : memory. To check that A is not const-qualified, we check that
882 : : there exists at least an unconditional write to A in the current
883 : : function.
884 : :
885 : : - reads or writes to memory are valid memory accesses for every
886 : : iteration. To check that the memory accesses are correctly formed
887 : : and that we are allowed to read and write in these locations, we
888 : : check that the memory accesses to be if-converted occur at every
889 : : iteration unconditionally.
890 : :
891 : : Returns true for the memory reference in STMT, same memory reference
892 : : is read or written unconditionally atleast once and the base memory
893 : : reference is written unconditionally once. This is to check reference
894 : : will not write fault. Also retuns true if the memory reference is
895 : : unconditionally read once then we are conditionally writing to memory
896 : : which is defined as read and write and is bound to the definition
897 : : we are seeing. */
898 : : static bool
899 : 16250 : ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs)
900 : : {
901 : : /* If DR didn't see a reference here we can't use it to tell
902 : : whether the ref traps or not. */
903 : 16250 : if (gimple_uid (stmt) == 0)
904 : : return false;
905 : :
906 : 16249 : data_reference_p *master_dr, *base_master_dr;
907 : 16249 : data_reference_p a = drs[gimple_uid (stmt) - 1];
908 : :
909 : 16249 : tree base = DR_BASE_OBJECT (a);
910 : 16249 : innermost_loop_behavior *innermost = &DR_INNERMOST (a);
911 : :
912 : 16249 : gcc_assert (DR_STMT (a) == stmt);
913 : 16249 : gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a)
914 : : || DR_INIT (a) || DR_STEP (a));
915 : :
916 : 16249 : master_dr = innermost_DR_map->get (innermost);
917 : 16249 : gcc_assert (master_dr != NULL);
918 : :
919 : 16249 : base_master_dr = baseref_DR_map->get (base);
920 : :
921 : : /* If a is unconditionally written to it doesn't trap. */
922 : 16249 : if (DR_W_UNCONDITIONALLY (*master_dr))
923 : : return true;
924 : :
925 : : /* If a is unconditionally accessed then ...
926 : :
927 : : Even a is conditional access, we can treat it as an unconditional
928 : : one if it's an array reference and all its index are within array
929 : : bound. */
930 : 14474 : if (DR_RW_UNCONDITIONALLY (*master_dr)
931 : 14474 : || ref_within_array_bound (stmt, DR_REF (a)))
932 : : {
933 : : /* an unconditional read won't trap. */
934 : 5687 : if (DR_IS_READ (a))
935 : : return true;
936 : :
937 : : /* an unconditionaly write won't trap if the base is written
938 : : to unconditionally. */
939 : 1781 : if (base_master_dr
940 : 1781 : && DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
941 : 41 : return flag_store_data_races;
942 : : /* or the base is known to be not readonly. */
943 : 1740 : else if (base_object_writable (DR_REF (a)))
944 : 1422 : return flag_store_data_races;
945 : : }
946 : :
947 : : return false;
948 : : }
949 : :
950 : : /* Return true if STMT could be converted into a masked load or store
951 : : (conditional load or store based on a mask computed from bb predicate). */
952 : :
953 : : static bool
954 : 10038 : ifcvt_can_use_mask_load_store (gimple *stmt)
955 : : {
956 : : /* Check whether this is a load or store. */
957 : 10038 : tree lhs = gimple_assign_lhs (stmt);
958 : 10038 : bool is_load;
959 : 10038 : tree ref;
960 : 10038 : if (gimple_store_p (stmt))
961 : : {
962 : 3040 : if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
963 : : return false;
964 : : is_load = false;
965 : : ref = lhs;
966 : : }
967 : 6998 : else if (gimple_assign_load_p (stmt))
968 : : {
969 : 6997 : is_load = true;
970 : 6997 : ref = gimple_assign_rhs1 (stmt);
971 : : }
972 : : else
973 : : return false;
974 : :
975 : 10037 : if (may_be_nonaddressable_p (ref))
976 : : return false;
977 : :
978 : : /* Mask should be integer mode of the same size as the load/store
979 : : mode. */
980 : 9995 : machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
981 : 9995 : if (!int_mode_for_mode (mode).exists () || VECTOR_MODE_P (mode))
982 : 31 : return false;
983 : :
984 : 9964 : if (can_vec_mask_load_store_p (mode, VOIDmode, is_load))
985 : : return true;
986 : :
987 : : return false;
988 : : }
989 : :
990 : : /* Return true if STMT could be converted from an operation that is
991 : : unconditional to one that is conditional on a bb predicate mask. */
992 : :
993 : : static bool
994 : 11639 : ifcvt_can_predicate (gimple *stmt)
995 : : {
996 : 11639 : basic_block bb = gimple_bb (stmt);
997 : :
998 : 396 : if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
999 : 11639 : || bb->loop_father->dont_vectorize
1000 : 23278 : || gimple_has_volatile_ops (stmt))
1001 : : return false;
1002 : :
1003 : 11639 : if (gimple_assign_single_p (stmt))
1004 : 10038 : return ifcvt_can_use_mask_load_store (stmt);
1005 : :
1006 : 1601 : tree_code code = gimple_assign_rhs_code (stmt);
1007 : 1601 : tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
1008 : 1601 : tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1009 : 1601 : if (!types_compatible_p (lhs_type, rhs_type))
1010 : : return false;
1011 : 1067 : internal_fn cond_fn = get_conditional_internal_fn (code);
1012 : 1067 : return (cond_fn != IFN_LAST
1013 : 1067 : && vectorized_internal_fn_supported_p (cond_fn, lhs_type));
1014 : : }
1015 : :
1016 : : /* Return true when STMT is if-convertible.
1017 : :
1018 : : GIMPLE_ASSIGN statement is not if-convertible if,
1019 : : - it is not movable,
1020 : : - it could trap,
1021 : : - LHS is not var decl. */
1022 : :
1023 : : static bool
1024 : 55920 : if_convertible_gimple_assign_stmt_p (gimple *stmt,
1025 : : vec<data_reference_p> refs)
1026 : : {
1027 : 55920 : tree lhs = gimple_assign_lhs (stmt);
1028 : :
1029 : 55920 : if (dump_file && (dump_flags & TDF_DETAILS))
1030 : : {
1031 : 27 : fprintf (dump_file, "-------------------------\n");
1032 : 27 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1033 : : }
1034 : :
1035 : 55920 : if (!is_gimple_reg_type (TREE_TYPE (lhs)))
1036 : : return false;
1037 : :
1038 : : /* Some of these constrains might be too conservative. */
1039 : 55653 : if (stmt_ends_bb_p (stmt)
1040 : 55653 : || gimple_has_volatile_ops (stmt)
1041 : 55592 : || (TREE_CODE (lhs) == SSA_NAME
1042 : 51992 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1043 : 111245 : || gimple_has_side_effects (stmt))
1044 : : {
1045 : 61 : if (dump_file && (dump_flags & TDF_DETAILS))
1046 : 0 : fprintf (dump_file, "stmt not suitable for ifcvt\n");
1047 : 61 : return false;
1048 : : }
1049 : :
1050 : : /* tree-into-ssa.cc uses GF_PLF_1, so avoid it, because
1051 : : in between if_convertible_loop_p and combine_blocks
1052 : : we can perform loop versioning. */
1053 : 55592 : gimple_set_plf (stmt, GF_PLF_2, false);
1054 : :
1055 : 55592 : if ((! gimple_vuse (stmt)
1056 : 16250 : || gimple_could_trap_p_1 (stmt, false, false)
1057 : 16250 : || ! ifcvt_memrefs_wont_trap (stmt, refs))
1058 : 66147 : && gimple_could_trap_p (stmt))
1059 : : {
1060 : 11639 : if (ifcvt_can_predicate (stmt))
1061 : : {
1062 : 3217 : gimple_set_plf (stmt, GF_PLF_2, true);
1063 : 3217 : need_to_predicate = true;
1064 : 3217 : return true;
1065 : : }
1066 : 8422 : if (dump_file && (dump_flags & TDF_DETAILS))
1067 : 0 : fprintf (dump_file, "tree could trap...\n");
1068 : 8422 : return false;
1069 : : }
1070 : 87906 : else if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1071 : 6007 : || POINTER_TYPE_P (TREE_TYPE (lhs)))
1072 : 83366 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs))
1073 : 112728 : && arith_code_with_undefined_signed_overflow
1074 : 27092 : (gimple_assign_rhs_code (stmt)))
1075 : : /* We have to rewrite stmts with undefined overflow. */
1076 : 16134 : need_to_rewrite_undefined = true;
1077 : :
1078 : : /* When if-converting stores force versioning, likewise if we
1079 : : ended up generating store data races. */
1080 : 87906 : if (gimple_vdef (stmt))
1081 : 560 : need_to_predicate = true;
1082 : :
1083 : : return true;
1084 : : }
1085 : :
1086 : : /* Return true when STMT is if-convertible.
1087 : :
1088 : : A statement is if-convertible if:
1089 : : - it is an if-convertible GIMPLE_ASSIGN,
1090 : : - it is a GIMPLE_LABEL or a GIMPLE_COND,
1091 : : - it is builtins call,
1092 : : - it is a call to a function with a SIMD clone. */
1093 : :
1094 : : static bool
1095 : 92773 : if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs)
1096 : : {
1097 : 92773 : switch (gimple_code (stmt))
1098 : : {
1099 : : case GIMPLE_LABEL:
1100 : : case GIMPLE_DEBUG:
1101 : : case GIMPLE_COND:
1102 : : return true;
1103 : :
1104 : 55920 : case GIMPLE_ASSIGN:
1105 : 55920 : return if_convertible_gimple_assign_stmt_p (stmt, refs);
1106 : :
1107 : 1390 : case GIMPLE_CALL:
1108 : 1390 : {
1109 : : /* There are some IFN_s that are used to replace builtins but have the
1110 : : same semantics. Even if MASK_CALL cannot handle them vectorable_call
1111 : : will insert the proper selection, so do not block conversion. */
1112 : 1390 : int flags = gimple_call_flags (stmt);
1113 : 1390 : if ((flags & ECF_CONST)
1114 : : && !(flags & ECF_LOOPING_CONST_OR_PURE)
1115 : 1390 : && gimple_call_combined_fn (stmt) != CFN_LAST)
1116 : : return true;
1117 : :
1118 : 988 : tree fndecl = gimple_call_fndecl (stmt);
1119 : 988 : if (fndecl)
1120 : : {
1121 : : /* We can vectorize some builtins and functions with SIMD
1122 : : "inbranch" clones. */
1123 : 988 : struct cgraph_node *node = cgraph_node::get (fndecl);
1124 : 988 : if (node && node->simd_clones != NULL)
1125 : : /* Ensure that at least one clone can be "inbranch". */
1126 : 1930 : for (struct cgraph_node *n = node->simd_clones; n != NULL;
1127 : 944 : n = n->simdclone->next_clone)
1128 : 1930 : if (n->simdclone->inbranch)
1129 : : {
1130 : 986 : gimple_set_plf (stmt, GF_PLF_2, true);
1131 : 986 : need_to_predicate = true;
1132 : 986 : return true;
1133 : : }
1134 : : }
1135 : :
1136 : : return false;
1137 : : }
1138 : :
1139 : 0 : default:
1140 : : /* Don't know what to do with 'em so don't do anything. */
1141 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1142 : : {
1143 : 0 : fprintf (dump_file, "don't know what to do\n");
1144 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1145 : : }
1146 : : return false;
1147 : : }
1148 : : }
1149 : :
1150 : : /* Assumes that BB has more than 1 predecessors.
1151 : : Returns false if at least one successor is not on critical edge
1152 : : and true otherwise. */
1153 : :
1154 : : static inline bool
1155 : 77613 : all_preds_critical_p (basic_block bb)
1156 : : {
1157 : 77613 : edge e;
1158 : 77613 : edge_iterator ei;
1159 : :
1160 : 151536 : FOR_EACH_EDGE (e, ei, bb->preds)
1161 : 131941 : if (EDGE_COUNT (e->src->succs) == 1)
1162 : : return false;
1163 : : return true;
1164 : : }
1165 : :
1166 : : /* Return true when BB is if-convertible. This routine does not check
1167 : : basic block's statements and phis.
1168 : :
1169 : : A basic block is not if-convertible if:
1170 : : - it is non-empty and it is after the exit block (in BFS order),
1171 : : - it is after the exit block but before the latch,
1172 : : - its edges are not normal.
1173 : :
1174 : : EXIT_BB is the basic block containing the exit of the LOOP. BB is
1175 : : inside LOOP. */
1176 : :
1177 : : static bool
1178 : 162054 : if_convertible_bb_p (class loop *loop, basic_block bb, basic_block exit_bb)
1179 : : {
1180 : 162054 : edge e;
1181 : 162054 : edge_iterator ei;
1182 : :
1183 : 162054 : if (dump_file && (dump_flags & TDF_DETAILS))
1184 : 77 : fprintf (dump_file, "----------[%d]-------------\n", bb->index);
1185 : :
1186 : 162054 : if (EDGE_COUNT (bb->succs) > 2)
1187 : : return false;
1188 : :
1189 : 426974 : if (gcall *call = safe_dyn_cast <gcall *> (*gsi_last_bb (bb)))
1190 : 180 : if (gimple_call_ctrl_altering_p (call))
1191 : : return false;
1192 : :
1193 : 162054 : if (exit_bb)
1194 : : {
1195 : 30236 : if (bb != loop->latch)
1196 : : {
1197 : 329 : if (dump_file && (dump_flags & TDF_DETAILS))
1198 : 0 : fprintf (dump_file, "basic block after exit bb but before latch\n");
1199 : 329 : return false;
1200 : : }
1201 : 29907 : else if (!empty_block_p (bb))
1202 : : {
1203 : 603 : if (dump_file && (dump_flags & TDF_DETAILS))
1204 : 0 : fprintf (dump_file, "non empty basic block after exit bb\n");
1205 : 603 : return false;
1206 : : }
1207 : 29304 : else if (bb == loop->latch
1208 : 29304 : && bb != exit_bb
1209 : 58608 : && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
1210 : : {
1211 : 8 : if (dump_file && (dump_flags & TDF_DETAILS))
1212 : 0 : fprintf (dump_file, "latch is not dominated by exit_block\n");
1213 : 8 : return false;
1214 : : }
1215 : : }
1216 : :
1217 : : /* Be less adventurous and handle only normal edges. */
1218 : 393965 : FOR_EACH_EDGE (e, ei, bb->succs)
1219 : 232859 : if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
1220 : : {
1221 : 8 : if (dump_file && (dump_flags & TDF_DETAILS))
1222 : 0 : fprintf (dump_file, "Difficult to handle edges\n");
1223 : 8 : return false;
1224 : : }
1225 : :
1226 : : return true;
1227 : : }
1228 : :
1229 : : /* Return true when all predecessor blocks of BB are visited. The
1230 : : VISITED bitmap keeps track of the visited blocks. */
1231 : :
1232 : : static bool
1233 : 2138412 : pred_blocks_visited_p (basic_block bb, bitmap *visited)
1234 : : {
1235 : 2138412 : edge e;
1236 : 2138412 : edge_iterator ei;
1237 : 3665976 : FOR_EACH_EDGE (e, ei, bb->preds)
1238 : 2430143 : if (!bitmap_bit_p (*visited, e->src->index))
1239 : : return false;
1240 : :
1241 : : return true;
1242 : : }
1243 : :
1244 : : /* Get body of a LOOP in suitable order for if-conversion. It is
1245 : : caller's responsibility to deallocate basic block list.
1246 : : If-conversion suitable order is, breadth first sort (BFS) order
1247 : : with an additional constraint: select a block only if all its
1248 : : predecessors are already selected. */
1249 : :
1250 : : static basic_block *
1251 : 346150 : get_loop_body_in_if_conv_order (const class loop *loop)
1252 : : {
1253 : 346150 : basic_block *blocks, *blocks_in_bfs_order;
1254 : 346150 : basic_block bb;
1255 : 346150 : bitmap visited;
1256 : 346150 : unsigned int index = 0;
1257 : 346150 : unsigned int visited_count = 0;
1258 : :
1259 : 346150 : gcc_assert (loop->num_nodes);
1260 : 346150 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1261 : :
1262 : 346150 : blocks = XCNEWVEC (basic_block, loop->num_nodes);
1263 : 346150 : visited = BITMAP_ALLOC (NULL);
1264 : :
1265 : 346150 : blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1266 : :
1267 : 346150 : index = 0;
1268 : 3776064 : while (index < loop->num_nodes)
1269 : : {
1270 : 3083805 : bb = blocks_in_bfs_order [index];
1271 : :
1272 : 3083805 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1273 : : {
1274 : 41 : free (blocks_in_bfs_order);
1275 : 41 : BITMAP_FREE (visited);
1276 : 41 : free (blocks);
1277 : 41 : return NULL;
1278 : : }
1279 : :
1280 : 3083764 : if (!bitmap_bit_p (visited, bb->index))
1281 : : {
1282 : 2138412 : if (pred_blocks_visited_p (bb, &visited)
1283 : 2138412 : || bb == loop->header)
1284 : : {
1285 : : /* This block is now visited. */
1286 : 1581983 : bitmap_set_bit (visited, bb->index);
1287 : 1581983 : blocks[visited_count++] = bb;
1288 : : }
1289 : : }
1290 : :
1291 : 3083764 : index++;
1292 : :
1293 : 3083764 : if (index == loop->num_nodes
1294 : 405221 : && visited_count != loop->num_nodes)
1295 : : /* Not done yet. */
1296 : 3083764 : index = 0;
1297 : : }
1298 : 346109 : free (blocks_in_bfs_order);
1299 : 346109 : BITMAP_FREE (visited);
1300 : :
1301 : : /* Go through loop and reject if-conversion or lowering of bitfields if we
1302 : : encounter statements we do not believe the vectorizer will be able to
1303 : : handle. If adding a new type of statement here, make sure
1304 : : 'ifcvt_local_dce' is also able to handle it propertly. */
1305 : 1900229 : for (index = 0; index < loop->num_nodes; index++)
1306 : : {
1307 : 1558666 : basic_block bb = blocks[index];
1308 : 1558666 : gimple_stmt_iterator gsi;
1309 : :
1310 : 1558666 : bool may_have_nonlocal_labels
1311 : 1558666 : = bb_with_exit_edge_p (loop, bb) || bb == loop->latch;
1312 : 13129717 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1313 : 10016931 : switch (gimple_code (gsi_stmt (gsi)))
1314 : : {
1315 : 33985 : case GIMPLE_LABEL:
1316 : 33985 : if (!may_have_nonlocal_labels)
1317 : : {
1318 : 3817 : tree label
1319 : 3817 : = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi)));
1320 : 7634 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1321 : : {
1322 : 40 : free (blocks);
1323 : 40 : return NULL;
1324 : : }
1325 : : }
1326 : : /* Fallthru. */
1327 : 10012385 : case GIMPLE_ASSIGN:
1328 : 10012385 : case GIMPLE_CALL:
1329 : 10012385 : case GIMPLE_DEBUG:
1330 : 10012385 : case GIMPLE_COND:
1331 : 10012385 : gimple_set_uid (gsi_stmt (gsi), 0);
1332 : 10012385 : break;
1333 : 4506 : default:
1334 : 4506 : free (blocks);
1335 : 4506 : return NULL;
1336 : : }
1337 : : }
1338 : : return blocks;
1339 : : }
1340 : :
1341 : : /* Returns true when the analysis of the predicates for all the basic
1342 : : blocks in LOOP succeeded.
1343 : :
1344 : : predicate_bbs first allocates the predicates of the basic blocks.
1345 : : These fields are then initialized with the tree expressions
1346 : : representing the predicates under which a basic block is executed
1347 : : in the LOOP. As the loop->header is executed at each iteration, it
1348 : : has the "true" predicate. Other statements executed under a
1349 : : condition are predicated with that condition, for example
1350 : :
1351 : : | if (x)
1352 : : | S1;
1353 : : | else
1354 : : | S2;
1355 : :
1356 : : S1 will be predicated with "x", and
1357 : : S2 will be predicated with "!x". */
1358 : :
1359 : : static void
1360 : 29296 : predicate_bbs (loop_p loop)
1361 : : {
1362 : 29296 : unsigned int i;
1363 : :
1364 : 187108 : for (i = 0; i < loop->num_nodes; i++)
1365 : 157812 : init_bb_predicate (ifc_bbs[i]);
1366 : :
1367 : 187108 : for (i = 0; i < loop->num_nodes; i++)
1368 : : {
1369 : 157812 : basic_block bb = ifc_bbs[i];
1370 : 157812 : tree cond;
1371 : :
1372 : : /* The loop latch and loop exit block are always executed and
1373 : : have no extra conditions to be processed: skip them. */
1374 : 216404 : if (bb == loop->latch
1375 : 157812 : || bb_with_exit_edge_p (loop, bb))
1376 : : {
1377 : 58592 : reset_bb_predicate (bb);
1378 : 58592 : continue;
1379 : : }
1380 : :
1381 : 99220 : cond = bb_predicate (bb);
1382 : 198440 : if (gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
1383 : : {
1384 : 40363 : tree c2;
1385 : 40363 : edge true_edge, false_edge;
1386 : 40363 : location_t loc = gimple_location (stmt);
1387 : 40363 : tree c;
1388 : : /* gcc.dg/fold-bopcond-1.c shows that despite all forwprop passes
1389 : : conditions can remain unfolded because of multiple uses so
1390 : : try to re-fold here, especially to get precision changing
1391 : : conversions sorted out. Do not simply fold the stmt since
1392 : : this is analysis only. When conditions were embedded in
1393 : : COND_EXPRs those were folded separately before folding the
1394 : : COND_EXPR but as they are now outside we have to make sure
1395 : : to fold them. Do it here - another opportunity would be to
1396 : : fold predicates as they are inserted. */
1397 : 40363 : gimple_match_op cexpr (gimple_match_cond::UNCOND,
1398 : : gimple_cond_code (stmt),
1399 : : boolean_type_node,
1400 : : gimple_cond_lhs (stmt),
1401 : 40363 : gimple_cond_rhs (stmt));
1402 : 40363 : if (cexpr.resimplify (NULL, follow_all_ssa_edges)
1403 : 3008 : && cexpr.code.is_tree_code ()
1404 : 43371 : && TREE_CODE_CLASS ((tree_code)cexpr.code) == tcc_comparison)
1405 : 151 : c = build2_loc (loc, (tree_code)cexpr.code, boolean_type_node,
1406 : : cexpr.ops[0], cexpr.ops[1]);
1407 : : else
1408 : 40212 : c = build2_loc (loc, gimple_cond_code (stmt),
1409 : : boolean_type_node,
1410 : : gimple_cond_lhs (stmt),
1411 : : gimple_cond_rhs (stmt));
1412 : :
1413 : : /* Add new condition into destination's predicate list. */
1414 : 40363 : extract_true_false_edges_from_block (gimple_bb (stmt),
1415 : : &true_edge, &false_edge);
1416 : :
1417 : : /* If C is true, then TRUE_EDGE is taken. */
1418 : 40363 : add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1419 : : unshare_expr (c));
1420 : :
1421 : : /* If C is false, then FALSE_EDGE is taken. */
1422 : 40363 : c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1423 : : unshare_expr (c));
1424 : 40363 : add_to_dst_predicate_list (loop, false_edge,
1425 : : unshare_expr (cond), c2);
1426 : :
1427 : 40363 : cond = NULL_TREE;
1428 : : }
1429 : :
1430 : : /* If current bb has only one successor, then consider it as an
1431 : : unconditional goto. */
1432 : 216669 : if (single_succ_p (bb))
1433 : : {
1434 : 58857 : basic_block bb_n = single_succ (bb);
1435 : :
1436 : : /* The successor bb inherits the predicate of its
1437 : : predecessor. If there is no predicate in the predecessor
1438 : : bb, then consider the successor bb as always executed. */
1439 : 58857 : if (cond == NULL_TREE)
1440 : 0 : cond = boolean_true_node;
1441 : :
1442 : 58857 : add_to_predicate_list (loop, bb_n, cond);
1443 : : }
1444 : : }
1445 : :
1446 : : /* The loop header is always executed. */
1447 : 29296 : reset_bb_predicate (loop->header);
1448 : 29296 : gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1449 : : && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1450 : 29296 : }
1451 : :
1452 : : /* Build region by adding loop pre-header and post-header blocks. */
1453 : :
1454 : : static vec<basic_block>
1455 : 29296 : build_region (class loop *loop)
1456 : : {
1457 : 29296 : vec<basic_block> region = vNULL;
1458 : 29296 : basic_block exit_bb = NULL;
1459 : :
1460 : 29296 : gcc_assert (ifc_bbs);
1461 : : /* The first element is loop pre-header. */
1462 : 29296 : region.safe_push (loop_preheader_edge (loop)->src);
1463 : :
1464 : 187108 : for (unsigned int i = 0; i < loop->num_nodes; i++)
1465 : : {
1466 : 157812 : basic_block bb = ifc_bbs[i];
1467 : 157812 : region.safe_push (bb);
1468 : : /* Find loop postheader. */
1469 : 157812 : edge e;
1470 : 157812 : edge_iterator ei;
1471 : 351130 : FOR_EACH_EDGE (e, ei, bb->succs)
1472 : 222614 : if (loop_exit_edge_p (loop, e))
1473 : : {
1474 : 29296 : exit_bb = e->dest;
1475 : 29296 : break;
1476 : : }
1477 : : }
1478 : : /* The last element is loop post-header. */
1479 : 29296 : gcc_assert (exit_bb);
1480 : 29296 : region.safe_push (exit_bb);
1481 : 29296 : return region;
1482 : : }
1483 : :
1484 : : /* Return true when LOOP is if-convertible. This is a helper function
1485 : : for if_convertible_loop_p. REFS and DDRS are initialized and freed
1486 : : in if_convertible_loop_p. */
1487 : :
1488 : : static bool
1489 : 30244 : if_convertible_loop_p_1 (class loop *loop, vec<data_reference_p> *refs)
1490 : : {
1491 : 30244 : unsigned int i;
1492 : 30244 : basic_block exit_bb = NULL;
1493 : 30244 : vec<basic_block> region;
1494 : :
1495 : 30244 : calculate_dominance_info (CDI_DOMINATORS);
1496 : :
1497 : 191350 : for (i = 0; i < loop->num_nodes; i++)
1498 : : {
1499 : 162054 : basic_block bb = ifc_bbs[i];
1500 : :
1501 : 162054 : if (!if_convertible_bb_p (loop, bb, exit_bb))
1502 : : return false;
1503 : :
1504 : 161106 : if (bb_with_exit_edge_p (loop, bb))
1505 : 30236 : exit_bb = bb;
1506 : : }
1507 : :
1508 : 29296 : data_reference_p dr;
1509 : :
1510 : 29296 : innermost_DR_map
1511 : 29296 : = new hash_map<innermost_loop_behavior_hash, data_reference_p>;
1512 : 29296 : baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>;
1513 : :
1514 : : /* Compute post-dominator tree locally. */
1515 : 29296 : region = build_region (loop);
1516 : 29296 : calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region);
1517 : :
1518 : 29296 : predicate_bbs (loop);
1519 : :
1520 : : /* Free post-dominator tree since it is not used after predication. */
1521 : 29296 : free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region);
1522 : 29296 : region.release ();
1523 : :
1524 : 137435 : for (i = 0; refs->iterate (i, &dr); i++)
1525 : : {
1526 : 108139 : tree ref = DR_REF (dr);
1527 : :
1528 : 108139 : dr->aux = XNEW (struct ifc_dr);
1529 : 108139 : DR_BASE_W_UNCONDITIONALLY (dr) = false;
1530 : 108139 : DR_RW_UNCONDITIONALLY (dr) = false;
1531 : 108139 : DR_W_UNCONDITIONALLY (dr) = false;
1532 : 108139 : IFC_DR (dr)->rw_predicate = boolean_false_node;
1533 : 108139 : IFC_DR (dr)->w_predicate = boolean_false_node;
1534 : 108139 : IFC_DR (dr)->base_w_predicate = boolean_false_node;
1535 : 108139 : if (gimple_uid (DR_STMT (dr)) == 0)
1536 : 107419 : gimple_set_uid (DR_STMT (dr), i + 1);
1537 : :
1538 : : /* If DR doesn't have innermost loop behavior or it's a compound
1539 : : memory reference, we synthesize its innermost loop behavior
1540 : : for hashing. */
1541 : 108139 : if (TREE_CODE (ref) == COMPONENT_REF
1542 : : || TREE_CODE (ref) == IMAGPART_EXPR
1543 : : || TREE_CODE (ref) == REALPART_EXPR
1544 : 67191 : || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr)
1545 : 16389 : || DR_INIT (dr) || DR_STEP (dr)))
1546 : : {
1547 : 104963 : while (TREE_CODE (ref) == COMPONENT_REF
1548 : 58552 : || TREE_CODE (ref) == IMAGPART_EXPR
1549 : 162909 : || TREE_CODE (ref) == REALPART_EXPR)
1550 : 47626 : ref = TREE_OPERAND (ref, 0);
1551 : :
1552 : 57337 : memset (&DR_INNERMOST (dr), 0, sizeof (DR_INNERMOST (dr)));
1553 : 57337 : DR_BASE_ADDRESS (dr) = ref;
1554 : : }
1555 : 108139 : hash_memrefs_baserefs_and_store_DRs_read_written_info (dr);
1556 : : }
1557 : :
1558 : 144891 : for (i = 0; i < loop->num_nodes; i++)
1559 : : {
1560 : 124347 : basic_block bb = ifc_bbs[i];
1561 : 124347 : gimple_stmt_iterator itr;
1562 : :
1563 : : /* Check the if-convertibility of statements in predicated BBs. */
1564 : 124347 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1565 : 188351 : for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1566 : 92773 : if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
1567 : 9700 : return false;
1568 : : }
1569 : :
1570 : : /* Checking PHIs needs to be done after stmts, as the fact whether there
1571 : : are any masked loads or stores affects the tests. */
1572 : 125143 : for (i = 0; i < loop->num_nodes; i++)
1573 : : {
1574 : 104599 : basic_block bb = ifc_bbs[i];
1575 : 104599 : gphi_iterator itr;
1576 : :
1577 : 196662 : for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1578 : 92063 : if (!if_convertible_phi_p (loop, bb, itr.phi ()))
1579 : 0 : return false;
1580 : : }
1581 : :
1582 : 20544 : if (dump_file)
1583 : 27 : fprintf (dump_file, "Applying if-conversion\n");
1584 : :
1585 : : return true;
1586 : : }
1587 : :
1588 : : /* Return true when LOOP is if-convertible.
1589 : : LOOP is if-convertible if:
1590 : : - it is innermost,
1591 : : - it has two or more basic blocks,
1592 : : - it has only one exit,
1593 : : - loop header is not the exit edge,
1594 : : - if its basic blocks and phi nodes are if convertible. */
1595 : :
1596 : : static bool
1597 : 30380 : if_convertible_loop_p (class loop *loop, vec<data_reference_p> *refs)
1598 : : {
1599 : 30380 : edge e;
1600 : 30380 : edge_iterator ei;
1601 : 30380 : bool res = false;
1602 : :
1603 : : /* Handle only innermost loop. */
1604 : 30380 : if (!loop || loop->inner)
1605 : : {
1606 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1607 : 0 : fprintf (dump_file, "not innermost loop\n");
1608 : 0 : return false;
1609 : : }
1610 : :
1611 : : /* If only one block, no need for if-conversion. */
1612 : 30380 : if (loop->num_nodes <= 2)
1613 : : {
1614 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1615 : 0 : fprintf (dump_file, "less than 2 basic blocks\n");
1616 : 0 : return false;
1617 : : }
1618 : :
1619 : : /* If one of the loop header's edge is an exit edge then do not
1620 : : apply if-conversion. */
1621 : 90944 : FOR_EACH_EDGE (e, ei, loop->header->succs)
1622 : 60700 : if (loop_exit_edge_p (loop, e))
1623 : : return false;
1624 : :
1625 : 30244 : res = if_convertible_loop_p_1 (loop, refs);
1626 : :
1627 : 59540 : delete innermost_DR_map;
1628 : 30244 : innermost_DR_map = NULL;
1629 : :
1630 : 59540 : delete baseref_DR_map;
1631 : 30244 : baseref_DR_map = NULL;
1632 : :
1633 : 30244 : return res;
1634 : : }
1635 : :
1636 : : /* Return reduc_1 if has_nop.
1637 : :
1638 : : if (...)
1639 : : tmp1 = (unsigned type) reduc_1;
1640 : : tmp2 = tmp1 + rhs2;
1641 : : reduc_3 = (signed type) tmp2. */
1642 : : static tree
1643 : 9908 : strip_nop_cond_scalar_reduction (bool has_nop, tree op)
1644 : : {
1645 : 9908 : if (!has_nop)
1646 : : return op;
1647 : :
1648 : 266 : if (TREE_CODE (op) != SSA_NAME)
1649 : : return NULL_TREE;
1650 : :
1651 : 227 : gassign *stmt = safe_dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op));
1652 : 227 : if (!stmt
1653 : 227 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
1654 : 158 : || !tree_nop_conversion_p (TREE_TYPE (op), TREE_TYPE
1655 : : (gimple_assign_rhs1 (stmt))))
1656 : 80 : return NULL_TREE;
1657 : :
1658 : 147 : return gimple_assign_rhs1 (stmt);
1659 : : }
1660 : :
1661 : : /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1662 : : which is in predicated basic block.
1663 : : In fact, the following PHI pattern is searching:
1664 : : loop-header:
1665 : : reduc_1 = PHI <..., reduc_2>
1666 : : ...
1667 : : if (...)
1668 : : reduc_3 = ...
1669 : : reduc_2 = PHI <reduc_1, reduc_3>
1670 : :
1671 : : ARG_0 and ARG_1 are correspondent PHI arguments.
1672 : : REDUC, OP0 and OP1 contain reduction stmt and its operands.
1673 : : EXTENDED is true if PHI has > 2 arguments. */
1674 : :
1675 : : static bool
1676 : 29071 : is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1,
1677 : : tree *op0, tree *op1, bool extended, bool* has_nop,
1678 : : gimple **nop_reduc)
1679 : : {
1680 : 29071 : tree lhs, r_op1, r_op2, r_nop1, r_nop2;
1681 : 29071 : gimple *stmt;
1682 : 29071 : gimple *header_phi = NULL;
1683 : 29071 : enum tree_code reduction_op;
1684 : 29071 : basic_block bb = gimple_bb (phi);
1685 : 29071 : class loop *loop = bb->loop_father;
1686 : 29071 : edge latch_e = loop_latch_edge (loop);
1687 : 29071 : imm_use_iterator imm_iter;
1688 : 29071 : use_operand_p use_p;
1689 : 29071 : edge e;
1690 : 29071 : edge_iterator ei;
1691 : 29071 : bool result = *has_nop = false;
1692 : 29071 : if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
1693 : : return false;
1694 : :
1695 : 18255 : if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
1696 : : {
1697 : 3688 : lhs = arg_1;
1698 : 3688 : header_phi = SSA_NAME_DEF_STMT (arg_0);
1699 : 3688 : stmt = SSA_NAME_DEF_STMT (arg_1);
1700 : : }
1701 : 14567 : else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
1702 : : {
1703 : 7294 : lhs = arg_0;
1704 : 7294 : header_phi = SSA_NAME_DEF_STMT (arg_1);
1705 : 7294 : stmt = SSA_NAME_DEF_STMT (arg_0);
1706 : : }
1707 : : else
1708 : : return false;
1709 : 10982 : if (gimple_bb (header_phi) != loop->header)
1710 : : return false;
1711 : :
1712 : 10907 : if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
1713 : : return false;
1714 : :
1715 : 7848 : if (gimple_code (stmt) != GIMPLE_ASSIGN
1716 : 7848 : || gimple_has_volatile_ops (stmt))
1717 : : return false;
1718 : :
1719 : 7738 : if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1720 : : return false;
1721 : :
1722 : 7662 : if (!is_predicated (gimple_bb (stmt)))
1723 : : return false;
1724 : :
1725 : : /* Check that stmt-block is predecessor of phi-block. */
1726 : 6624 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1727 : 6561 : if (e->dest == bb)
1728 : : {
1729 : : result = true;
1730 : : break;
1731 : : }
1732 : 6498 : if (!result)
1733 : : return false;
1734 : :
1735 : 6435 : if (!has_single_use (lhs))
1736 : : return false;
1737 : :
1738 : 6370 : reduction_op = gimple_assign_rhs_code (stmt);
1739 : :
1740 : : /* Catch something like below
1741 : :
1742 : : loop-header:
1743 : : reduc_1 = PHI <..., reduc_2>
1744 : : ...
1745 : : if (...)
1746 : : tmp1 = (unsigned type) reduc_1;
1747 : : tmp2 = tmp1 + rhs2;
1748 : : reduc_3 = (signed type) tmp2;
1749 : :
1750 : : reduc_2 = PHI <reduc_1, reduc_3>
1751 : :
1752 : : and convert to
1753 : :
1754 : : reduc_2 = PHI <0, reduc_1>
1755 : : tmp1 = (unsigned type)reduc_1;
1756 : : ifcvt = cond_expr ? rhs2 : 0
1757 : : tmp2 = tmp1 +/- ifcvt;
1758 : : reduc_1 = (signed type)tmp2; */
1759 : :
1760 : 6370 : if (CONVERT_EXPR_CODE_P (reduction_op))
1761 : : {
1762 : 266 : lhs = gimple_assign_rhs1 (stmt);
1763 : 266 : if (TREE_CODE (lhs) != SSA_NAME
1764 : 266 : || !has_single_use (lhs))
1765 : : return false;
1766 : :
1767 : 148 : *nop_reduc = stmt;
1768 : 148 : stmt = SSA_NAME_DEF_STMT (lhs);
1769 : 148 : if (gimple_bb (stmt) != gimple_bb (*nop_reduc)
1770 : 148 : || !is_gimple_assign (stmt))
1771 : : return false;
1772 : :
1773 : 145 : *has_nop = true;
1774 : 145 : reduction_op = gimple_assign_rhs_code (stmt);
1775 : : }
1776 : :
1777 : 6249 : if (reduction_op != PLUS_EXPR
1778 : : && reduction_op != MINUS_EXPR
1779 : 6249 : && reduction_op != MULT_EXPR
1780 : 6249 : && reduction_op != BIT_IOR_EXPR
1781 : : && reduction_op != BIT_XOR_EXPR
1782 : 1400 : && reduction_op != BIT_AND_EXPR)
1783 : : return false;
1784 : 4954 : r_op1 = gimple_assign_rhs1 (stmt);
1785 : 4954 : r_op2 = gimple_assign_rhs2 (stmt);
1786 : :
1787 : 4954 : r_nop1 = strip_nop_cond_scalar_reduction (*has_nop, r_op1);
1788 : 4954 : r_nop2 = strip_nop_cond_scalar_reduction (*has_nop, r_op2);
1789 : :
1790 : : /* Make R_OP1 to hold reduction variable. */
1791 : 4954 : if (r_nop2 == PHI_RESULT (header_phi)
1792 : 4954 : && commutative_tree_code (reduction_op))
1793 : : {
1794 : : std::swap (r_op1, r_op2);
1795 : : std::swap (r_nop1, r_nop2);
1796 : : }
1797 : 4106 : else if (r_nop1 != PHI_RESULT (header_phi))
1798 : : return false;
1799 : :
1800 : 4771 : if (*has_nop)
1801 : : {
1802 : : /* Check that R_NOP1 is used in nop_stmt or in PHI only. */
1803 : 217 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_nop1)
1804 : : {
1805 : 161 : gimple *use_stmt = USE_STMT (use_p);
1806 : 161 : if (is_gimple_debug (use_stmt))
1807 : 0 : continue;
1808 : 161 : if (use_stmt == SSA_NAME_DEF_STMT (r_op1))
1809 : 56 : continue;
1810 : 105 : if (use_stmt != phi)
1811 : : return false;
1812 : : }
1813 : : }
1814 : :
1815 : : /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1816 : 14528 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
1817 : : {
1818 : 10133 : gimple *use_stmt = USE_STMT (use_p);
1819 : 10133 : if (is_gimple_debug (use_stmt))
1820 : 29 : continue;
1821 : 10104 : if (use_stmt == stmt)
1822 : 4414 : continue;
1823 : 5690 : if (gimple_code (use_stmt) != GIMPLE_PHI)
1824 : : return false;
1825 : : }
1826 : :
1827 : 4395 : *op0 = r_op1; *op1 = r_op2;
1828 : 4395 : *reduc = stmt;
1829 : 4395 : return true;
1830 : : }
1831 : :
1832 : : /* Converts conditional scalar reduction into unconditional form, e.g.
1833 : : bb_4
1834 : : if (_5 != 0) goto bb_5 else goto bb_6
1835 : : end_bb_4
1836 : : bb_5
1837 : : res_6 = res_13 + 1;
1838 : : end_bb_5
1839 : : bb_6
1840 : : # res_2 = PHI <res_13(4), res_6(5)>
1841 : : end_bb_6
1842 : :
1843 : : will be converted into sequence
1844 : : _ifc__1 = _5 != 0 ? 1 : 0;
1845 : : res_2 = res_13 + _ifc__1;
1846 : : Argument SWAP tells that arguments of conditional expression should be
1847 : : swapped.
1848 : : If LOOP_VERSIONED is true if we assume that we versioned the loop for
1849 : : vectorization. In that case we can create a COND_OP.
1850 : : Returns rhs of resulting PHI assignment. */
1851 : :
1852 : : static tree
1853 : 4395 : convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi,
1854 : : tree cond, tree op0, tree op1, bool swap,
1855 : : bool has_nop, gimple* nop_reduc,
1856 : : bool loop_versioned)
1857 : : {
1858 : 4395 : gimple_stmt_iterator stmt_it;
1859 : 4395 : gimple *new_assign;
1860 : 4395 : tree rhs;
1861 : 4395 : tree rhs1 = gimple_assign_rhs1 (reduc);
1862 : 4395 : tree lhs = gimple_assign_lhs (reduc);
1863 : 4395 : tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
1864 : 4395 : tree c;
1865 : 4395 : enum tree_code reduction_op = gimple_assign_rhs_code (reduc);
1866 : 4395 : tree op_nochange = neutral_op_for_reduction (TREE_TYPE (rhs1), reduction_op,
1867 : : NULL, false);
1868 : 4395 : gimple_seq stmts = NULL;
1869 : :
1870 : 4395 : if (dump_file && (dump_flags & TDF_DETAILS))
1871 : : {
1872 : 2 : fprintf (dump_file, "Found cond scalar reduction.\n");
1873 : 2 : print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
1874 : : }
1875 : :
1876 : : /* If possible create a COND_OP instead of a COND_EXPR and an OP_EXPR.
1877 : : The COND_OP will have a neutral_op else value. */
1878 : 4395 : internal_fn ifn;
1879 : 4395 : ifn = get_conditional_internal_fn (reduction_op);
1880 : 4395 : if (loop_versioned && ifn != IFN_LAST
1881 : 4393 : && vectorized_internal_fn_supported_p (ifn, TREE_TYPE (lhs))
1882 : 5492 : && !swap)
1883 : : {
1884 : 1079 : gcall *cond_call = gimple_build_call_internal (ifn, 4,
1885 : : unshare_expr (cond),
1886 : : op0, op1, op0);
1887 : 1079 : gsi_insert_before (gsi, cond_call, GSI_SAME_STMT);
1888 : 1079 : gimple_call_set_lhs (cond_call, tmp);
1889 : : rhs = tmp;
1890 : : }
1891 : : else
1892 : : {
1893 : : /* Build cond expression using COND and constant operand
1894 : : of reduction rhs. */
1895 : 6285 : c = fold_build_cond_expr (TREE_TYPE (rhs1),
1896 : : unshare_expr (cond),
1897 : : swap ? op_nochange : op1,
1898 : : swap ? op1 : op_nochange);
1899 : : /* Create assignment stmt and insert it at GSI. */
1900 : 3316 : new_assign = gimple_build_assign (tmp, c);
1901 : 3316 : gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
1902 : : /* Build rhs for unconditional increment/decrement/logic_operation. */
1903 : 3316 : rhs = gimple_build (&stmts, reduction_op,
1904 : 3316 : TREE_TYPE (rhs1), op0, tmp);
1905 : : }
1906 : :
1907 : 4395 : if (has_nop)
1908 : : {
1909 : 56 : rhs = gimple_convert (&stmts,
1910 : 56 : TREE_TYPE (gimple_assign_lhs (nop_reduc)), rhs);
1911 : 56 : stmt_it = gsi_for_stmt (nop_reduc);
1912 : 56 : gsi_remove (&stmt_it, true);
1913 : 56 : release_defs (nop_reduc);
1914 : : }
1915 : 4395 : gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
1916 : :
1917 : : /* Delete original reduction stmt. */
1918 : 4395 : stmt_it = gsi_for_stmt (reduc);
1919 : 4395 : gsi_remove (&stmt_it, true);
1920 : 4395 : release_defs (reduc);
1921 : 4395 : return rhs;
1922 : : }
1923 : :
1924 : : /* Generate a simplified conditional. */
1925 : :
1926 : : static tree
1927 : 34817 : gen_simplified_condition (tree cond, scalar_cond_masked_set_type &cond_set)
1928 : : {
1929 : : /* Check if the value is already live in a previous branch. This resolves
1930 : : nested conditionals from diamond PHI reductions. */
1931 : 34817 : if (TREE_CODE (cond) == SSA_NAME)
1932 : : {
1933 : 34817 : gimple *stmt = SSA_NAME_DEF_STMT (cond);
1934 : 34817 : gassign *assign = NULL;
1935 : 34817 : if ((assign = as_a <gassign *> (stmt))
1936 : 69634 : && gimple_assign_rhs_code (assign) == BIT_AND_EXPR)
1937 : : {
1938 : 3242 : tree arg1 = gimple_assign_rhs1 (assign);
1939 : 3242 : tree arg2 = gimple_assign_rhs2 (assign);
1940 : 3242 : if (cond_set.contains ({ arg1, 1 }))
1941 : 119 : arg1 = boolean_true_node;
1942 : : else
1943 : 3123 : arg1 = gen_simplified_condition (arg1, cond_set);
1944 : :
1945 : 3242 : if (cond_set.contains ({ arg2, 1 }))
1946 : 1804 : arg2 = boolean_true_node;
1947 : : else
1948 : 1438 : arg2 = gen_simplified_condition (arg2, cond_set);
1949 : :
1950 : 3242 : cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, arg1, arg2);
1951 : : }
1952 : : }
1953 : 34817 : return cond;
1954 : : }
1955 : :
1956 : : /* Structure used to track meta-data on PHI arguments used to generate
1957 : : most efficient comparison sequence to slatten a PHI node. */
1958 : :
1959 : : typedef struct ifcvt_arg_entry
1960 : : {
1961 : : /* The PHI node argument value. */
1962 : : tree arg;
1963 : :
1964 : : /* The number of compares required to reach this PHI node from start of the
1965 : : BB being if-converted. */
1966 : : unsigned num_compares;
1967 : :
1968 : : /* The number of times this PHI node argument appears in the current PHI
1969 : : node. */
1970 : : unsigned occurs;
1971 : :
1972 : : /* The indices at which this PHI arg occurs inside the PHI node. */
1973 : : vec <int> *indexes;
1974 : : } ifcvt_arg_entry_t;
1975 : :
1976 : : /* Produce condition for all occurrences of ARG in PHI node. Set *INVERT
1977 : : as to whether the condition is inverted. */
1978 : :
1979 : : static tree
1980 : 4131 : gen_phi_arg_condition (gphi *phi, ifcvt_arg_entry_t &arg,
1981 : : gimple_stmt_iterator *gsi,
1982 : : scalar_cond_masked_set_type &cond_set, bool *invert)
1983 : : {
1984 : 4131 : int len;
1985 : 4131 : int i;
1986 : 4131 : tree cond = NULL_TREE;
1987 : 4131 : tree c;
1988 : 4131 : edge e;
1989 : :
1990 : 4131 : *invert = false;
1991 : 4131 : len = arg.indexes->length ();
1992 : 4131 : gcc_assert (len > 0);
1993 : 8300 : for (i = 0; i < len; i++)
1994 : : {
1995 : 4169 : e = gimple_phi_arg_edge (phi, (*arg.indexes)[i]);
1996 : 4169 : c = bb_predicate (e->src);
1997 : 4169 : if (is_true_predicate (c))
1998 : : {
1999 : 0 : cond = c;
2000 : 0 : break;
2001 : : }
2002 : : /* If we have just a single inverted predicate, signal that and
2003 : : instead invert the COND_EXPR arms. */
2004 : 4169 : if (len == 1 && TREE_CODE (c) == TRUTH_NOT_EXPR)
2005 : : {
2006 : 87 : c = TREE_OPERAND (c, 0);
2007 : 87 : *invert = true;
2008 : : }
2009 : :
2010 : 4169 : c = gen_simplified_condition (c, cond_set);
2011 : 4169 : c = force_gimple_operand_gsi (gsi, unshare_expr (c),
2012 : : true, NULL_TREE, true, GSI_SAME_STMT);
2013 : 4169 : if (cond != NULL_TREE)
2014 : : {
2015 : : /* Must build OR expression. */
2016 : 38 : cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
2017 : 38 : cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
2018 : : NULL_TREE, true, GSI_SAME_STMT);
2019 : : }
2020 : : else
2021 : : cond = c;
2022 : :
2023 : : /* Register the new possibly simplified conditional. When more than 2
2024 : : entries in a phi node we chain entries in the false branch, so the
2025 : : inverted condition is active. */
2026 : 4169 : scalar_cond_masked_key pred_cond ({ cond, 1 });
2027 : 4169 : if (!*invert)
2028 : 4082 : pred_cond.inverted_p = !pred_cond.inverted_p;
2029 : 4169 : cond_set.add (pred_cond);
2030 : : }
2031 : 4131 : gcc_assert (cond != NULL_TREE);
2032 : 4131 : return cond;
2033 : : }
2034 : :
2035 : : /* Create the smallest nested conditional possible. On pre-order we record
2036 : : which conditionals are live, and on post-order rewrite the chain by removing
2037 : : already active conditions.
2038 : :
2039 : : As an example we simplify:
2040 : :
2041 : : _7 = a_10 < 0;
2042 : : _21 = a_10 >= 0;
2043 : : _22 = a_10 < e_11(D);
2044 : : _23 = _21 & _22;
2045 : : _ifc__42 = _23 ? t_13 : 0;
2046 : : t_6 = _7 ? 1 : _ifc__42
2047 : :
2048 : : into
2049 : :
2050 : : _7 = a_10 < 0;
2051 : : _22 = a_10 < e_11(D);
2052 : : _ifc__42 = _22 ? t_13 : 0;
2053 : : t_6 = _7 ? 1 : _ifc__42;
2054 : :
2055 : : which produces better code. */
2056 : :
2057 : : static tree
2058 : 6192 : gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi,
2059 : : scalar_cond_masked_set_type &cond_set, tree type,
2060 : : gimple **res_stmt, tree lhs0,
2061 : : vec<struct ifcvt_arg_entry> &args, unsigned idx)
2062 : : {
2063 : 12384 : if (idx == args.length ())
2064 : 2061 : return args[idx - 1].arg;
2065 : :
2066 : 4131 : bool invert;
2067 : 4131 : tree cond = gen_phi_arg_condition (phi, args[idx - 1], gsi, cond_set,
2068 : : &invert);
2069 : 4131 : tree arg1 = gen_phi_nest_statement (phi, gsi, cond_set, type, res_stmt, lhs0,
2070 : : args, idx + 1);
2071 : :
2072 : 4131 : unsigned prev = idx;
2073 : 4131 : unsigned curr = prev - 1;
2074 : 4131 : tree arg0 = args[curr].arg;
2075 : 4131 : tree rhs, lhs;
2076 : 4131 : if (idx > 1)
2077 : 2070 : lhs = make_temp_ssa_name (type, NULL, "_ifc_");
2078 : : else
2079 : : lhs = lhs0;
2080 : :
2081 : 4131 : if (invert)
2082 : 87 : rhs = fold_build_cond_expr (type, unshare_expr (cond),
2083 : : arg1, arg0);
2084 : : else
2085 : 4044 : rhs = fold_build_cond_expr (type, unshare_expr (cond),
2086 : : arg0, arg1);
2087 : 4131 : gassign *new_stmt = gimple_build_assign (lhs, rhs);
2088 : 4131 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2089 : 4131 : update_stmt (new_stmt);
2090 : 4131 : *res_stmt = new_stmt;
2091 : 4131 : return lhs;
2092 : : }
2093 : :
2094 : : /* When flattening a PHI node we have a choice of which conditions to test to
2095 : : for all the paths from the start of the dominator block of the BB with the
2096 : : PHI node. If the PHI node has X arguments we have to only test X - 1
2097 : : conditions as the last one is implicit. It does matter which conditions we
2098 : : test first. We should test the shortest condition first (distance here is
2099 : : measures in the number of logical operators in the condition) and the
2100 : : longest one last. This allows us to skip testing the most expensive
2101 : : condition. To accomplish this we need to sort the conditions. P1 and P2
2102 : : are sorted first based on the number of logical operations (num_compares)
2103 : : and then by how often they occur in the PHI node. */
2104 : :
2105 : : static int
2106 : 34769 : cmp_arg_entry (const void *p1, const void *p2, void * /* data. */)
2107 : : {
2108 : 34769 : const ifcvt_arg_entry sval1 = *(const ifcvt_arg_entry *)p1;
2109 : 34769 : const ifcvt_arg_entry sval2 = *(const ifcvt_arg_entry *)p2;
2110 : :
2111 : 34769 : if (sval1.num_compares < sval2.num_compares)
2112 : : return -1;
2113 : 12223 : else if (sval1.num_compares > sval2.num_compares)
2114 : : return 1;
2115 : :
2116 : 659 : if (sval1.occurs < sval2.occurs)
2117 : : return -1;
2118 : 659 : else if (sval1.occurs > sval2.occurs)
2119 : 0 : return 1;
2120 : :
2121 : : return 0;
2122 : : }
2123 : :
2124 : : /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
2125 : : This routine can handle PHI nodes with more than two arguments.
2126 : :
2127 : : For example,
2128 : : S1: A = PHI <x1(1), x2(5)>
2129 : : is converted into,
2130 : : S2: A = cond ? x1 : x2;
2131 : :
2132 : : The generated code is inserted at GSI that points to the top of
2133 : : basic block's statement list.
2134 : : If PHI node has more than two arguments a chain of conditional
2135 : : expression is produced.
2136 : : LOOP_VERSIONED should be true if we know that the loop was versioned for
2137 : : vectorization. */
2138 : :
2139 : :
2140 : : static void
2141 : 31181 : predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi, bool loop_versioned)
2142 : : {
2143 : 31181 : gimple *new_stmt = NULL, *reduc, *nop_reduc;
2144 : 31181 : tree rhs, res, arg0, arg1, op0, op1, scev;
2145 : 31181 : tree cond;
2146 : 31181 : unsigned int index0;
2147 : 31181 : edge e;
2148 : 31181 : basic_block bb;
2149 : 31181 : unsigned int i;
2150 : 31181 : bool has_nop;
2151 : :
2152 : 31181 : res = gimple_phi_result (phi);
2153 : 62362 : if (virtual_operand_p (res))
2154 : 26136 : return;
2155 : :
2156 : 31181 : if ((rhs = degenerate_phi_result (phi))
2157 : 31181 : || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
2158 : : res))
2159 : 31142 : && !chrec_contains_undetermined (scev)
2160 : 31142 : && scev != res
2161 : 10 : && (rhs = gimple_phi_arg_def (phi, 0))))
2162 : : {
2163 : 49 : if (dump_file && (dump_flags & TDF_DETAILS))
2164 : : {
2165 : 0 : fprintf (dump_file, "Degenerate phi!\n");
2166 : 0 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
2167 : : }
2168 : 49 : new_stmt = gimple_build_assign (res, rhs);
2169 : 49 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2170 : 49 : update_stmt (new_stmt);
2171 : 49 : return;
2172 : : }
2173 : :
2174 : 31132 : bb = gimple_bb (phi);
2175 : : /* Keep track of conditionals already seen. */
2176 : 31132 : scalar_cond_masked_set_type cond_set;
2177 : 31132 : if (EDGE_COUNT (bb->preds) == 2)
2178 : : {
2179 : : /* Predicate ordinary PHI node with 2 arguments. */
2180 : 26087 : edge first_edge, second_edge;
2181 : 26087 : basic_block true_bb;
2182 : 26087 : first_edge = EDGE_PRED (bb, 0);
2183 : 26087 : second_edge = EDGE_PRED (bb, 1);
2184 : 26087 : cond = bb_predicate (first_edge->src);
2185 : 26087 : cond_set.add ({ cond, 1 });
2186 : 26087 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2187 : 13204 : std::swap (first_edge, second_edge);
2188 : 26087 : if (EDGE_COUNT (first_edge->src->succs) > 1)
2189 : : {
2190 : 11418 : cond = bb_predicate (second_edge->src);
2191 : 11418 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2192 : 6944 : cond = TREE_OPERAND (cond, 0);
2193 : : else
2194 : : first_edge = second_edge;
2195 : : }
2196 : : else
2197 : 14669 : cond = bb_predicate (first_edge->src);
2198 : :
2199 : : /* Gimplify the condition to a valid cond-expr conditonal operand. */
2200 : 26087 : cond = gen_simplified_condition (cond, cond_set);
2201 : 26087 : cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
2202 : : NULL_TREE, true, GSI_SAME_STMT);
2203 : 26087 : true_bb = first_edge->src;
2204 : 26087 : if (EDGE_PRED (bb, 1)->src == true_bb)
2205 : : {
2206 : 17678 : arg0 = gimple_phi_arg_def (phi, 1);
2207 : 17678 : arg1 = gimple_phi_arg_def (phi, 0);
2208 : : }
2209 : : else
2210 : : {
2211 : 8409 : arg0 = gimple_phi_arg_def (phi, 0);
2212 : 8409 : arg1 = gimple_phi_arg_def (phi, 1);
2213 : : }
2214 : 26087 : if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
2215 : : &op0, &op1, false, &has_nop,
2216 : : &nop_reduc))
2217 : : {
2218 : : /* Convert reduction stmt into vectorizable form. */
2219 : 6940 : rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
2220 : 3470 : true_bb != gimple_bb (reduc),
2221 : : has_nop, nop_reduc,
2222 : : loop_versioned);
2223 : 3470 : redundant_ssa_names.safe_push (std::make_pair (res, rhs));
2224 : : }
2225 : : else
2226 : : /* Build new RHS using selected condition and arguments. */
2227 : 22617 : rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
2228 : : arg0, arg1);
2229 : 26087 : new_stmt = gimple_build_assign (res, rhs);
2230 : 26087 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2231 : 26087 : gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt);
2232 : 26087 : if (fold_stmt (&new_gsi, follow_all_ssa_edges))
2233 : : {
2234 : 5307 : new_stmt = gsi_stmt (new_gsi);
2235 : 5307 : update_stmt (new_stmt);
2236 : : }
2237 : :
2238 : 26087 : if (dump_file && (dump_flags & TDF_DETAILS))
2239 : : {
2240 : 14 : fprintf (dump_file, "new phi replacement stmt\n");
2241 : 14 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
2242 : : }
2243 : 26087 : return;
2244 : : }
2245 : :
2246 : : /* Create hashmap for PHI node which contain vector of argument indexes
2247 : : having the same value. */
2248 : 5045 : bool swap = false;
2249 : 5045 : hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
2250 : 5045 : unsigned int num_args = gimple_phi_num_args (phi);
2251 : : /* Vector of different PHI argument values. */
2252 : 5045 : auto_vec<ifcvt_arg_entry_t> args;
2253 : :
2254 : : /* Compute phi_arg_map, determine the list of unique PHI args and the indices
2255 : : where they are in the PHI node. The indices will be used to determine
2256 : : the conditions to apply and their complexity. */
2257 : 20338 : for (i = 0; i < num_args; i++)
2258 : : {
2259 : 15293 : tree arg;
2260 : :
2261 : 15293 : arg = gimple_phi_arg_def (phi, i);
2262 : 15293 : if (!phi_arg_map.get (arg))
2263 : 12160 : args.safe_push ({ arg, 0, 0, NULL });
2264 : 15293 : phi_arg_map.get_or_insert (arg).safe_push (i);
2265 : : }
2266 : :
2267 : : /* Determine element with max number of occurrences and complexity. Looking
2268 : : at only number of occurrences as a measure for complexity isn't enough as
2269 : : all usages can be unique but the comparisons to reach the PHI node differ
2270 : : per branch. */
2271 : 34410 : for (unsigned i = 0; i < args.length (); i++)
2272 : : {
2273 : 12160 : unsigned int len = 0;
2274 : 12160 : vec<int> *indices = phi_arg_map.get (args[i].arg);
2275 : 51773 : for (int index : *indices)
2276 : : {
2277 : 15293 : edge e = gimple_phi_arg_edge (phi, index);
2278 : 15293 : len += get_bb_num_predicate_stmts (e->src);
2279 : : }
2280 : :
2281 : 12160 : unsigned occur = indices->length ();
2282 : 12160 : if (dump_file && (dump_flags & TDF_DETAILS))
2283 : 7 : fprintf (dump_file, "Ranking %d as len=%d, idx=%d\n", i, len, occur);
2284 : 12160 : args[i].num_compares = len;
2285 : 12160 : args[i].occurs = occur;
2286 : 12160 : args[i].indexes = indices;
2287 : : }
2288 : :
2289 : : /* Sort elements based on rankings ARGS. */
2290 : 5045 : args.stablesort (cmp_arg_entry, NULL);
2291 : :
2292 : : /* Handle one special case when number of arguments with different values
2293 : : is equal 2 and one argument has the only occurrence. Such PHI can be
2294 : : handled as if would have only 2 arguments. */
2295 : 5045 : if (args.length () == 2
2296 : 8067 : && args[0].indexes->length () == 1)
2297 : : {
2298 : 2984 : index0 = (*args[0].indexes)[0];
2299 : 2984 : arg0 = args[0].arg;
2300 : 2984 : arg1 = args[1].arg;
2301 : 2984 : e = gimple_phi_arg_edge (phi, index0);
2302 : 2984 : cond = bb_predicate (e->src);
2303 : 2984 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2304 : : {
2305 : 21 : swap = true;
2306 : 21 : cond = TREE_OPERAND (cond, 0);
2307 : : }
2308 : : /* Gimplify the condition to a valid cond-expr conditonal operand. */
2309 : 2984 : cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
2310 : : NULL_TREE, true, GSI_SAME_STMT);
2311 : 2984 : if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
2312 : : &op0, &op1, true, &has_nop, &nop_reduc)))
2313 : 4099 : rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
2314 : : swap ? arg1 : arg0,
2315 : : swap ? arg0 : arg1);
2316 : : else
2317 : : {
2318 : : /* Convert reduction stmt into vectorizable form. */
2319 : 925 : rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
2320 : : swap, has_nop, nop_reduc,
2321 : : loop_versioned);
2322 : 925 : redundant_ssa_names.safe_push (std::make_pair (res, rhs));
2323 : : }
2324 : 2984 : new_stmt = gimple_build_assign (res, rhs);
2325 : 2984 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2326 : 2984 : update_stmt (new_stmt);
2327 : : }
2328 : : else
2329 : : {
2330 : : /* Common case. */
2331 : 2061 : tree type = TREE_TYPE (gimple_phi_result (phi));
2332 : 2061 : gen_phi_nest_statement (phi, gsi, cond_set, type, &new_stmt, res,
2333 : : args, 1);
2334 : : }
2335 : :
2336 : 5045 : if (dump_file && (dump_flags & TDF_DETAILS))
2337 : : {
2338 : 3 : fprintf (dump_file, "new extended phi replacement stmt\n");
2339 : 3 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
2340 : : }
2341 : 31132 : }
2342 : :
2343 : : /* Replaces in LOOP all the scalar phi nodes other than those in the
2344 : : LOOP->header block with conditional modify expressions.
2345 : : LOOP_VERSIONED should be true if we know that the loop was versioned for
2346 : : vectorization. */
2347 : :
2348 : : static void
2349 : 20544 : predicate_all_scalar_phis (class loop *loop, bool loop_versioned)
2350 : : {
2351 : 20544 : basic_block bb;
2352 : 20544 : unsigned int orig_loop_num_nodes = loop->num_nodes;
2353 : 20544 : unsigned int i;
2354 : :
2355 : 104599 : for (i = 1; i < orig_loop_num_nodes; i++)
2356 : : {
2357 : 84055 : gphi *phi;
2358 : 84055 : gimple_stmt_iterator gsi;
2359 : 84055 : gphi_iterator phi_gsi;
2360 : 84055 : bb = ifc_bbs[i];
2361 : :
2362 : 84055 : if (bb == loop->header)
2363 : 60977 : continue;
2364 : :
2365 : 84055 : phi_gsi = gsi_start_phis (bb);
2366 : 84055 : if (gsi_end_p (phi_gsi))
2367 : 60977 : continue;
2368 : :
2369 : 23078 : gsi = gsi_after_labels (bb);
2370 : 56230 : while (!gsi_end_p (phi_gsi))
2371 : : {
2372 : 33152 : phi = phi_gsi.phi ();
2373 : 66304 : if (virtual_operand_p (gimple_phi_result (phi)))
2374 : 1971 : gsi_next (&phi_gsi);
2375 : : else
2376 : : {
2377 : 31181 : predicate_scalar_phi (phi, &gsi, loop_versioned);
2378 : 31181 : remove_phi_node (&phi_gsi, false);
2379 : : }
2380 : : }
2381 : : }
2382 : 20544 : }
2383 : :
2384 : : /* Insert in each basic block of LOOP the statements produced by the
2385 : : gimplification of the predicates. */
2386 : :
2387 : : static void
2388 : 20544 : insert_gimplified_predicates (loop_p loop)
2389 : : {
2390 : 20544 : unsigned int i;
2391 : :
2392 : 125143 : for (i = 0; i < loop->num_nodes; i++)
2393 : : {
2394 : 104599 : basic_block bb = ifc_bbs[i];
2395 : 104599 : gimple_seq stmts;
2396 : 104599 : if (!is_predicated (bb))
2397 : 63316 : gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
2398 : 104599 : if (!is_predicated (bb))
2399 : : {
2400 : : /* Do not insert statements for a basic block that is not
2401 : : predicated. Also make sure that the predicate of the
2402 : : basic block is set to true. */
2403 : 63316 : reset_bb_predicate (bb);
2404 : 63316 : continue;
2405 : : }
2406 : :
2407 : 41283 : stmts = bb_predicate_gimplified_stmts (bb);
2408 : 41283 : if (stmts)
2409 : : {
2410 : 41007 : if (need_to_predicate)
2411 : : {
2412 : : /* Insert the predicate of the BB just after the label,
2413 : : as the if-conversion of memory writes will use this
2414 : : predicate. */
2415 : 4967 : gimple_stmt_iterator gsi = gsi_after_labels (bb);
2416 : 4967 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2417 : : }
2418 : : else
2419 : : {
2420 : : /* Insert the predicate of the BB at the end of the BB
2421 : : as this would reduce the register pressure: the only
2422 : : use of this predicate will be in successor BBs. */
2423 : 36040 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2424 : :
2425 : 36040 : if (gsi_end_p (gsi)
2426 : 36040 : || stmt_ends_bb_p (gsi_stmt (gsi)))
2427 : 19261 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2428 : : else
2429 : 16779 : gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
2430 : : }
2431 : :
2432 : : /* Once the sequence is code generated, set it to NULL. */
2433 : 41007 : set_bb_predicate_gimplified_stmts (bb, NULL, true);
2434 : : }
2435 : : }
2436 : 20544 : }
2437 : :
2438 : : /* Helper function for predicate_statements. Returns index of existent
2439 : : mask if it was created for given SIZE and -1 otherwise. */
2440 : :
2441 : : static int
2442 : 1079 : mask_exists (int size, const vec<int> &vec)
2443 : : {
2444 : 1079 : unsigned int ix;
2445 : 1079 : int v;
2446 : 1168 : FOR_EACH_VEC_ELT (vec, ix, v)
2447 : 1107 : if (v == size)
2448 : 1018 : return (int) ix;
2449 : : return -1;
2450 : : }
2451 : :
2452 : : /* Helper function for predicate_statements. STMT is a memory read or
2453 : : write and it needs to be predicated by MASK. Return a statement
2454 : : that does so. */
2455 : :
2456 : : static gimple *
2457 : 2503 : predicate_load_or_store (gimple_stmt_iterator *gsi, gassign *stmt, tree mask)
2458 : : {
2459 : 2503 : gcall *new_stmt;
2460 : :
2461 : 2503 : tree lhs = gimple_assign_lhs (stmt);
2462 : 2503 : tree rhs = gimple_assign_rhs1 (stmt);
2463 : 2503 : tree ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
2464 : 2503 : mark_addressable (ref);
2465 : 2503 : tree addr = force_gimple_operand_gsi (gsi, build_fold_addr_expr (ref),
2466 : : true, NULL_TREE, true, GSI_SAME_STMT);
2467 : 2503 : tree ptr = build_int_cst (reference_alias_ptr_type (ref),
2468 : 2503 : get_object_alignment (ref));
2469 : : /* Copy points-to info if possible. */
2470 : 2503 : if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
2471 : 1121 : copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
2472 : : ref);
2473 : 2503 : if (TREE_CODE (lhs) == SSA_NAME)
2474 : : {
2475 : 1113 : new_stmt
2476 : 1113 : = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
2477 : : ptr, mask);
2478 : 1113 : gimple_call_set_lhs (new_stmt, lhs);
2479 : 2226 : gimple_set_vuse (new_stmt, gimple_vuse (stmt));
2480 : : }
2481 : : else
2482 : : {
2483 : 1390 : new_stmt
2484 : 1390 : = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
2485 : : mask, rhs);
2486 : 1390 : gimple_move_vops (new_stmt, stmt);
2487 : : }
2488 : 2503 : gimple_call_set_nothrow (new_stmt, true);
2489 : 2503 : return new_stmt;
2490 : : }
2491 : :
2492 : : /* STMT uses OP_LHS. Check whether it is equivalent to:
2493 : :
2494 : : ... = OP_MASK ? OP_LHS : X;
2495 : :
2496 : : Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is
2497 : : known to have value OP_COND. */
2498 : :
2499 : : static tree
2500 : 672 : check_redundant_cond_expr (gimple *stmt, tree op_mask, tree op_cond,
2501 : : tree op_lhs)
2502 : : {
2503 : 1325 : gassign *assign = dyn_cast <gassign *> (stmt);
2504 : 868 : if (!assign || gimple_assign_rhs_code (assign) != COND_EXPR)
2505 : : return NULL_TREE;
2506 : :
2507 : 91 : tree use_cond = gimple_assign_rhs1 (assign);
2508 : 91 : tree if_true = gimple_assign_rhs2 (assign);
2509 : 91 : tree if_false = gimple_assign_rhs3 (assign);
2510 : :
2511 : 72 : if ((use_cond == op_mask || operand_equal_p (use_cond, op_cond, 0))
2512 : 91 : && if_true == op_lhs)
2513 : : return if_false;
2514 : :
2515 : 72 : if (inverse_conditions_p (use_cond, op_cond) && if_false == op_lhs)
2516 : : return if_true;
2517 : :
2518 : : return NULL_TREE;
2519 : : }
2520 : :
2521 : : /* Return true if VALUE is available for use at STMT. SSA_NAMES is
2522 : : the set of SSA names defined earlier in STMT's block. */
2523 : :
2524 : : static bool
2525 : 19 : value_available_p (gimple *stmt, hash_set<tree_ssa_name_hash> *ssa_names,
2526 : : tree value)
2527 : : {
2528 : 19 : if (is_gimple_min_invariant (value))
2529 : : return true;
2530 : :
2531 : 19 : if (TREE_CODE (value) == SSA_NAME)
2532 : : {
2533 : 19 : if (SSA_NAME_IS_DEFAULT_DEF (value))
2534 : : return true;
2535 : :
2536 : 19 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
2537 : 19 : basic_block use_bb = gimple_bb (stmt);
2538 : 19 : return (def_bb == use_bb
2539 : 19 : ? ssa_names->contains (value)
2540 : 19 : : dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
2541 : : }
2542 : :
2543 : : return false;
2544 : : }
2545 : :
2546 : : /* Helper function for predicate_statements. STMT is a potentially-trapping
2547 : : arithmetic operation that needs to be predicated by MASK, an SSA_NAME that
2548 : : has value COND. Return a statement that does so. SSA_NAMES is the set of
2549 : : SSA names defined earlier in STMT's block. */
2550 : :
2551 : : static gimple *
2552 : 473 : predicate_rhs_code (gassign *stmt, tree mask, tree cond,
2553 : : hash_set<tree_ssa_name_hash> *ssa_names)
2554 : : {
2555 : 473 : tree lhs = gimple_assign_lhs (stmt);
2556 : 473 : tree_code code = gimple_assign_rhs_code (stmt);
2557 : 473 : unsigned int nops = gimple_num_ops (stmt);
2558 : 473 : internal_fn cond_fn = get_conditional_internal_fn (code);
2559 : :
2560 : : /* Construct the arguments to the conditional internal function. */
2561 : 473 : auto_vec<tree, 8> args;
2562 : 473 : args.safe_grow (nops + 1, true);
2563 : 473 : args[0] = mask;
2564 : 1419 : for (unsigned int i = 1; i < nops; ++i)
2565 : 946 : args[i] = gimple_op (stmt, i);
2566 : 473 : args[nops] = NULL_TREE;
2567 : :
2568 : : /* Look for uses of the result to see whether they are COND_EXPRs that can
2569 : : be folded into the conditional call. */
2570 : 473 : imm_use_iterator imm_iter;
2571 : 473 : gimple *use_stmt;
2572 : 1145 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
2573 : : {
2574 : 672 : tree new_else = check_redundant_cond_expr (use_stmt, mask, cond, lhs);
2575 : 672 : if (new_else && value_available_p (stmt, ssa_names, new_else))
2576 : : {
2577 : 0 : if (!args[nops])
2578 : 0 : args[nops] = new_else;
2579 : 0 : if (operand_equal_p (new_else, args[nops], 0))
2580 : : {
2581 : : /* We have:
2582 : :
2583 : : LHS = IFN_COND (MASK, ..., ELSE);
2584 : : X = MASK ? LHS : ELSE;
2585 : :
2586 : : which makes X equivalent to LHS. */
2587 : 0 : tree use_lhs = gimple_assign_lhs (use_stmt);
2588 : 0 : redundant_ssa_names.safe_push (std::make_pair (use_lhs, lhs));
2589 : : }
2590 : : }
2591 : 473 : }
2592 : 473 : if (!args[nops])
2593 : 946 : args[nops] = targetm.preferred_else_value (cond_fn, TREE_TYPE (lhs),
2594 : 473 : nops - 1, &args[1]);
2595 : :
2596 : : /* Create and insert the call. */
2597 : 473 : gcall *new_stmt = gimple_build_call_internal_vec (cond_fn, args);
2598 : 473 : gimple_call_set_lhs (new_stmt, lhs);
2599 : 473 : gimple_call_set_nothrow (new_stmt, true);
2600 : :
2601 : 473 : return new_stmt;
2602 : 473 : }
2603 : :
2604 : : /* Predicate each write to memory in LOOP.
2605 : :
2606 : : This function transforms control flow constructs containing memory
2607 : : writes of the form:
2608 : :
2609 : : | for (i = 0; i < N; i++)
2610 : : | if (cond)
2611 : : | A[i] = expr;
2612 : :
2613 : : into the following form that does not contain control flow:
2614 : :
2615 : : | for (i = 0; i < N; i++)
2616 : : | A[i] = cond ? expr : A[i];
2617 : :
2618 : : The original CFG looks like this:
2619 : :
2620 : : | bb_0
2621 : : | i = 0
2622 : : | end_bb_0
2623 : : |
2624 : : | bb_1
2625 : : | if (i < N) goto bb_5 else goto bb_2
2626 : : | end_bb_1
2627 : : |
2628 : : | bb_2
2629 : : | cond = some_computation;
2630 : : | if (cond) goto bb_3 else goto bb_4
2631 : : | end_bb_2
2632 : : |
2633 : : | bb_3
2634 : : | A[i] = expr;
2635 : : | goto bb_4
2636 : : | end_bb_3
2637 : : |
2638 : : | bb_4
2639 : : | goto bb_1
2640 : : | end_bb_4
2641 : :
2642 : : insert_gimplified_predicates inserts the computation of the COND
2643 : : expression at the beginning of the destination basic block:
2644 : :
2645 : : | bb_0
2646 : : | i = 0
2647 : : | end_bb_0
2648 : : |
2649 : : | bb_1
2650 : : | if (i < N) goto bb_5 else goto bb_2
2651 : : | end_bb_1
2652 : : |
2653 : : | bb_2
2654 : : | cond = some_computation;
2655 : : | if (cond) goto bb_3 else goto bb_4
2656 : : | end_bb_2
2657 : : |
2658 : : | bb_3
2659 : : | cond = some_computation;
2660 : : | A[i] = expr;
2661 : : | goto bb_4
2662 : : | end_bb_3
2663 : : |
2664 : : | bb_4
2665 : : | goto bb_1
2666 : : | end_bb_4
2667 : :
2668 : : predicate_statements is then predicating the memory write as follows:
2669 : :
2670 : : | bb_0
2671 : : | i = 0
2672 : : | end_bb_0
2673 : : |
2674 : : | bb_1
2675 : : | if (i < N) goto bb_5 else goto bb_2
2676 : : | end_bb_1
2677 : : |
2678 : : | bb_2
2679 : : | if (cond) goto bb_3 else goto bb_4
2680 : : | end_bb_2
2681 : : |
2682 : : | bb_3
2683 : : | cond = some_computation;
2684 : : | A[i] = cond ? expr : A[i];
2685 : : | goto bb_4
2686 : : | end_bb_3
2687 : : |
2688 : : | bb_4
2689 : : | goto bb_1
2690 : : | end_bb_4
2691 : :
2692 : : and finally combine_blocks removes the basic block boundaries making
2693 : : the loop vectorizable:
2694 : :
2695 : : | bb_0
2696 : : | i = 0
2697 : : | if (i < N) goto bb_5 else goto bb_1
2698 : : | end_bb_0
2699 : : |
2700 : : | bb_1
2701 : : | cond = some_computation;
2702 : : | A[i] = cond ? expr : A[i];
2703 : : | if (i < N) goto bb_5 else goto bb_4
2704 : : | end_bb_1
2705 : : |
2706 : : | bb_4
2707 : : | goto bb_1
2708 : : | end_bb_4
2709 : : */
2710 : :
2711 : : static void
2712 : 7644 : predicate_statements (loop_p loop)
2713 : : {
2714 : 7644 : unsigned int i, orig_loop_num_nodes = loop->num_nodes;
2715 : 7644 : auto_vec<int, 1> vect_sizes;
2716 : 7644 : auto_vec<tree, 1> vect_masks;
2717 : 7644 : hash_set<tree_ssa_name_hash> ssa_names;
2718 : :
2719 : 42336 : for (i = 1; i < orig_loop_num_nodes; i++)
2720 : : {
2721 : 34692 : gimple_stmt_iterator gsi;
2722 : 34692 : basic_block bb = ifc_bbs[i];
2723 : 34692 : tree cond = bb_predicate (bb);
2724 : 34692 : bool swap;
2725 : 34692 : int index;
2726 : :
2727 : 34692 : if (is_true_predicate (cond))
2728 : 16216 : continue;
2729 : :
2730 : 18476 : swap = false;
2731 : 18476 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2732 : : {
2733 : 6810 : swap = true;
2734 : 6810 : cond = TREE_OPERAND (cond, 0);
2735 : : }
2736 : :
2737 : 18476 : vect_sizes.truncate (0);
2738 : 18476 : vect_masks.truncate (0);
2739 : :
2740 : 109268 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2741 : : {
2742 : 72316 : gassign *stmt = dyn_cast <gassign *> (gsi_stmt (gsi));
2743 : 56569 : tree lhs;
2744 : 56569 : if (!stmt)
2745 : : ;
2746 : 56569 : else if (is_false_predicate (cond)
2747 : 56569 : && gimple_vdef (stmt))
2748 : : {
2749 : 0 : unlink_stmt_vdef (stmt);
2750 : 0 : gsi_remove (&gsi, true);
2751 : 0 : release_defs (stmt);
2752 : 0 : continue;
2753 : : }
2754 : 56569 : else if (gimple_plf (stmt, GF_PLF_2)
2755 : 56569 : && is_gimple_assign (stmt))
2756 : : {
2757 : 2976 : tree lhs = gimple_assign_lhs (stmt);
2758 : 2976 : tree mask;
2759 : 2976 : gimple *new_stmt;
2760 : 2976 : gimple_seq stmts = NULL;
2761 : 2976 : machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
2762 : : /* We checked before setting GF_PLF_2 that an equivalent
2763 : : integer mode exists. */
2764 : 2976 : int bitsize = GET_MODE_BITSIZE (mode).to_constant ();
2765 : 2976 : if (!vect_sizes.is_empty ()
2766 : 1079 : && (index = mask_exists (bitsize, vect_sizes)) != -1)
2767 : : /* Use created mask. */
2768 : 1018 : mask = vect_masks[index];
2769 : : else
2770 : : {
2771 : 1958 : if (COMPARISON_CLASS_P (cond))
2772 : 0 : mask = gimple_build (&stmts, TREE_CODE (cond),
2773 : : boolean_type_node,
2774 : 0 : TREE_OPERAND (cond, 0),
2775 : 0 : TREE_OPERAND (cond, 1));
2776 : : else
2777 : 1958 : mask = cond;
2778 : :
2779 : 1958 : if (swap)
2780 : : {
2781 : 614 : tree true_val
2782 : 614 : = constant_boolean_node (true, TREE_TYPE (mask));
2783 : 614 : mask = gimple_build (&stmts, BIT_XOR_EXPR,
2784 : 614 : TREE_TYPE (mask), mask, true_val);
2785 : : }
2786 : 1958 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2787 : :
2788 : : /* Save mask and its size for further use. */
2789 : 1958 : vect_sizes.safe_push (bitsize);
2790 : 1958 : vect_masks.safe_push (mask);
2791 : : }
2792 : 2976 : if (gimple_assign_single_p (stmt))
2793 : 2503 : new_stmt = predicate_load_or_store (&gsi, stmt, mask);
2794 : : else
2795 : 473 : new_stmt = predicate_rhs_code (stmt, mask, cond, &ssa_names);
2796 : :
2797 : 2976 : gsi_replace (&gsi, new_stmt, true);
2798 : : }
2799 : 53593 : else if (((lhs = gimple_assign_lhs (stmt)), true)
2800 : 53593 : && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2801 : 5746 : || POINTER_TYPE_P (TREE_TYPE (lhs)))
2802 : 105882 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs))
2803 : 75637 : && arith_code_with_undefined_signed_overflow
2804 : 22696 : (gimple_assign_rhs_code (stmt)))
2805 : 8359 : rewrite_to_defined_overflow (&gsi);
2806 : 90468 : else if (gimple_vdef (stmt))
2807 : : {
2808 : 463 : tree lhs = gimple_assign_lhs (stmt);
2809 : 463 : tree rhs = gimple_assign_rhs1 (stmt);
2810 : 463 : tree type = TREE_TYPE (lhs);
2811 : :
2812 : 463 : lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
2813 : 463 : rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
2814 : 463 : if (swap)
2815 : 65 : std::swap (lhs, rhs);
2816 : 463 : cond = force_gimple_operand_gsi (&gsi, unshare_expr (cond), true,
2817 : : NULL_TREE, true, GSI_SAME_STMT);
2818 : 463 : rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
2819 : 463 : gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
2820 : 463 : update_stmt (stmt);
2821 : : }
2822 : :
2823 : 72316 : if (gimple_plf (gsi_stmt (gsi), GF_PLF_2)
2824 : 72316 : && is_gimple_call (gsi_stmt (gsi)))
2825 : : {
2826 : : /* Convert functions that have a SIMD clone to IFN_MASK_CALL.
2827 : : This will cause the vectorizer to match the "in branch"
2828 : : clone variants, and serves to build the mask vector
2829 : : in a natural way. */
2830 : 985 : gcall *call = dyn_cast <gcall *> (gsi_stmt (gsi));
2831 : 985 : tree orig_fn = gimple_call_fn (call);
2832 : 985 : int orig_nargs = gimple_call_num_args (call);
2833 : 985 : auto_vec<tree> args;
2834 : 985 : args.safe_push (orig_fn);
2835 : 1991 : for (int i = 0; i < orig_nargs; i++)
2836 : 1006 : args.safe_push (gimple_call_arg (call, i));
2837 : 985 : args.safe_push (cond);
2838 : :
2839 : : /* Replace the call with a IFN_MASK_CALL that has the extra
2840 : : condition parameter. */
2841 : 985 : gcall *new_call = gimple_build_call_internal_vec (IFN_MASK_CALL,
2842 : : args);
2843 : 985 : gimple_call_set_lhs (new_call, gimple_call_lhs (call));
2844 : 985 : gsi_replace (&gsi, new_call, true);
2845 : 985 : }
2846 : :
2847 : 72316 : lhs = gimple_get_lhs (gsi_stmt (gsi));
2848 : 72316 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
2849 : 54785 : ssa_names.add (lhs);
2850 : 72316 : gsi_next (&gsi);
2851 : : }
2852 : 36928 : ssa_names.empty ();
2853 : : }
2854 : 7644 : }
2855 : :
2856 : : /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2857 : : other than the exit and latch of the LOOP. Also resets the
2858 : : GIMPLE_DEBUG information. */
2859 : :
2860 : : static void
2861 : 20544 : remove_conditions_and_labels (loop_p loop)
2862 : : {
2863 : 20544 : gimple_stmt_iterator gsi;
2864 : 20544 : unsigned int i;
2865 : :
2866 : 125143 : for (i = 0; i < loop->num_nodes; i++)
2867 : : {
2868 : 104599 : basic_block bb = ifc_bbs[i];
2869 : :
2870 : 104599 : if (bb_with_exit_edge_p (loop, bb)
2871 : 104599 : || bb == loop->latch)
2872 : 41088 : continue;
2873 : :
2874 : 398042 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2875 : 271020 : switch (gimple_code (gsi_stmt (gsi)))
2876 : : {
2877 : 25635 : case GIMPLE_COND:
2878 : 25635 : case GIMPLE_LABEL:
2879 : 25635 : gsi_remove (&gsi, true);
2880 : 25635 : break;
2881 : :
2882 : 112745 : case GIMPLE_DEBUG:
2883 : : /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2884 : 112745 : if (gimple_debug_bind_p (gsi_stmt (gsi)))
2885 : : {
2886 : 78723 : gimple_debug_bind_reset_value (gsi_stmt (gsi));
2887 : 78723 : update_stmt (gsi_stmt (gsi));
2888 : : }
2889 : 112745 : gsi_next (&gsi);
2890 : 112745 : break;
2891 : :
2892 : 132640 : default:
2893 : 132640 : gsi_next (&gsi);
2894 : : }
2895 : : }
2896 : 20544 : }
2897 : :
2898 : : /* Combine all the basic blocks from LOOP into one or two super basic
2899 : : blocks. Replace PHI nodes with conditional modify expressions.
2900 : : LOOP_VERSIONED should be true if we know that the loop was versioned for
2901 : : vectorization. */
2902 : :
2903 : : static void
2904 : 20544 : combine_blocks (class loop *loop, bool loop_versioned)
2905 : : {
2906 : 20544 : basic_block bb, exit_bb, merge_target_bb;
2907 : 20544 : unsigned int orig_loop_num_nodes = loop->num_nodes;
2908 : 20544 : unsigned int i;
2909 : 20544 : edge e;
2910 : 20544 : edge_iterator ei;
2911 : :
2912 : : /* Reset flow-sensitive info before predicating stmts or PHIs we
2913 : : might fold. */
2914 : 20544 : bool *predicated = XNEWVEC (bool, orig_loop_num_nodes);
2915 : 125143 : for (i = 0; i < orig_loop_num_nodes; i++)
2916 : : {
2917 : 104599 : bb = ifc_bbs[i];
2918 : 104599 : predicated[i] = is_predicated (bb);
2919 : 104599 : if (predicated[i])
2920 : : {
2921 : 41283 : for (auto gsi = gsi_start_phis (bb);
2922 : 42429 : !gsi_end_p (gsi); gsi_next (&gsi))
2923 : 1146 : reset_flow_sensitive_info (gimple_phi_result (*gsi));
2924 : 145086 : for (auto gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2925 : : {
2926 : 62520 : gimple *stmt = gsi_stmt (gsi);
2927 : 62520 : ssa_op_iter i;
2928 : 62520 : tree op;
2929 : 98300 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
2930 : 35780 : reset_flow_sensitive_info (op);
2931 : : }
2932 : : }
2933 : : }
2934 : :
2935 : 20544 : remove_conditions_and_labels (loop);
2936 : 20544 : insert_gimplified_predicates (loop);
2937 : 20544 : predicate_all_scalar_phis (loop, loop_versioned);
2938 : :
2939 : 20544 : if (need_to_predicate || need_to_rewrite_undefined)
2940 : 7644 : predicate_statements (loop);
2941 : :
2942 : : /* Merge basic blocks. */
2943 : 20544 : exit_bb = single_exit (loop)->src;
2944 : 20544 : gcc_assert (exit_bb != loop->latch);
2945 : 125143 : for (i = 0; i < orig_loop_num_nodes; i++)
2946 : : {
2947 : 104599 : bb = ifc_bbs[i];
2948 : 104599 : free_bb_predicate (bb);
2949 : : }
2950 : :
2951 : 20544 : merge_target_bb = loop->header;
2952 : :
2953 : : /* Get at the virtual def valid for uses starting at the first block
2954 : : we merge into the header. Without a virtual PHI the loop has the
2955 : : same virtual use on all stmts. */
2956 : 20544 : gphi *vphi = get_virtual_phi (loop->header);
2957 : 20544 : tree last_vdef = NULL_TREE;
2958 : 20544 : if (vphi)
2959 : : {
2960 : 12077 : last_vdef = gimple_phi_result (vphi);
2961 : 24154 : for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header);
2962 : 109156 : ! gsi_end_p (gsi); gsi_next (&gsi))
2963 : 162673 : if (gimple_vdef (gsi_stmt (gsi)))
2964 : 4280 : last_vdef = gimple_vdef (gsi_stmt (gsi));
2965 : : }
2966 : 104599 : for (i = 1; i < orig_loop_num_nodes; i++)
2967 : : {
2968 : 84055 : gimple_stmt_iterator gsi;
2969 : 84055 : gimple_stmt_iterator last;
2970 : :
2971 : 84055 : bb = ifc_bbs[i];
2972 : :
2973 : 84055 : if (bb == exit_bb || bb == loop->latch)
2974 : 41088 : continue;
2975 : :
2976 : : /* We release virtual PHIs late because we have to propagate them
2977 : : out using the current VUSE. The def might be the one used
2978 : : after the loop. */
2979 : 42967 : vphi = get_virtual_phi (bb);
2980 : 42967 : if (vphi)
2981 : : {
2982 : : /* When there's just loads inside the loop a stray virtual
2983 : : PHI merging the uses can appear, update last_vdef from
2984 : : it. */
2985 : 521 : if (!last_vdef)
2986 : 0 : last_vdef = gimple_phi_arg_def (vphi, 0);
2987 : 521 : imm_use_iterator iter;
2988 : 521 : use_operand_p use_p;
2989 : 521 : gimple *use_stmt;
2990 : 1406 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
2991 : : {
2992 : 2657 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2993 : 886 : SET_USE (use_p, last_vdef);
2994 : 521 : }
2995 : 521 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
2996 : 0 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
2997 : 521 : gsi = gsi_for_stmt (vphi);
2998 : 521 : remove_phi_node (&gsi, true);
2999 : : }
3000 : :
3001 : : /* Make stmts member of loop->header and clear range info from all stmts
3002 : : in BB which is now no longer executed conditional on a predicate we
3003 : : could have derived it from. */
3004 : 238073 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3005 : : {
3006 : 152139 : gimple *stmt = gsi_stmt (gsi);
3007 : 152139 : gimple_set_bb (stmt, merge_target_bb);
3008 : : /* Update virtual operands. */
3009 : 152139 : if (last_vdef)
3010 : : {
3011 : 117680 : use_operand_p use_p = ssa_vuse_operand (stmt);
3012 : 9760 : if (use_p
3013 : 9760 : && USE_FROM_PTR (use_p) != last_vdef)
3014 : 418 : SET_USE (use_p, last_vdef);
3015 : 363395 : if (gimple_vdef (stmt))
3016 : 152139 : last_vdef = gimple_vdef (stmt);
3017 : : }
3018 : : else
3019 : : /* If this is the first load we arrive at update last_vdef
3020 : : so we handle stray PHIs correctly. */
3021 : 176406 : last_vdef = gimple_vuse (stmt);
3022 : : }
3023 : :
3024 : : /* Update stmt list. */
3025 : 42967 : last = gsi_last_bb (merge_target_bb);
3026 : 85934 : gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT);
3027 : 42967 : set_bb_seq (bb, NULL);
3028 : : }
3029 : :
3030 : : /* Fixup virtual operands in the exit block. */
3031 : 20544 : if (exit_bb
3032 : 20544 : && exit_bb != loop->header)
3033 : : {
3034 : : /* We release virtual PHIs late because we have to propagate them
3035 : : out using the current VUSE. The def might be the one used
3036 : : after the loop. */
3037 : 20544 : vphi = get_virtual_phi (exit_bb);
3038 : 20544 : if (vphi)
3039 : : {
3040 : : /* When there's just loads inside the loop a stray virtual
3041 : : PHI merging the uses can appear, update last_vdef from
3042 : : it. */
3043 : 1450 : if (!last_vdef)
3044 : 0 : last_vdef = gimple_phi_arg_def (vphi, 0);
3045 : 1450 : imm_use_iterator iter;
3046 : 1450 : use_operand_p use_p;
3047 : 1450 : gimple *use_stmt;
3048 : 4357 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
3049 : : {
3050 : 8721 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3051 : 2907 : SET_USE (use_p, last_vdef);
3052 : 1450 : }
3053 : 1450 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
3054 : 0 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
3055 : 1450 : gimple_stmt_iterator gsi = gsi_for_stmt (vphi);
3056 : 1450 : remove_phi_node (&gsi, true);
3057 : : }
3058 : : }
3059 : :
3060 : : /* Now remove all the edges in the loop, except for those from the exit
3061 : : block and delete the blocks we elided. */
3062 : 104599 : for (i = 1; i < orig_loop_num_nodes; i++)
3063 : : {
3064 : 84055 : bb = ifc_bbs[i];
3065 : :
3066 : 193442 : for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
3067 : : {
3068 : 109387 : if (e->src == exit_bb)
3069 : 20544 : ei_next (&ei);
3070 : : else
3071 : 88843 : remove_edge (e);
3072 : : }
3073 : : }
3074 : 104599 : for (i = 1; i < orig_loop_num_nodes; i++)
3075 : : {
3076 : 84055 : bb = ifc_bbs[i];
3077 : :
3078 : 84055 : if (bb == exit_bb || bb == loop->latch)
3079 : 41088 : continue;
3080 : :
3081 : 42967 : delete_basic_block (bb);
3082 : : }
3083 : :
3084 : : /* Re-connect the exit block. */
3085 : 20544 : if (exit_bb != NULL)
3086 : : {
3087 : 20544 : if (exit_bb != loop->header)
3088 : : {
3089 : : /* Connect this node to loop header. */
3090 : 20544 : make_single_succ_edge (loop->header, exit_bb, EDGE_FALLTHRU);
3091 : 20544 : set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
3092 : : }
3093 : :
3094 : : /* Redirect non-exit edges to loop->latch. */
3095 : 61632 : FOR_EACH_EDGE (e, ei, exit_bb->succs)
3096 : : {
3097 : 41088 : if (!loop_exit_edge_p (loop, e))
3098 : 20544 : redirect_edge_and_branch (e, loop->latch);
3099 : : }
3100 : 20544 : set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
3101 : : }
3102 : : else
3103 : : {
3104 : : /* If the loop does not have an exit, reconnect header and latch. */
3105 : 0 : make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
3106 : 0 : set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
3107 : : }
3108 : :
3109 : : /* If possible, merge loop header to the block with the exit edge.
3110 : : This reduces the number of basic blocks to two, to please the
3111 : : vectorizer that handles only loops with two nodes. */
3112 : 20544 : if (exit_bb
3113 : 20544 : && exit_bb != loop->header)
3114 : : {
3115 : 20544 : if (can_merge_blocks_p (loop->header, exit_bb))
3116 : 20542 : merge_blocks (loop->header, exit_bb);
3117 : : }
3118 : :
3119 : 20544 : free (ifc_bbs);
3120 : 20544 : ifc_bbs = NULL;
3121 : 20544 : free (predicated);
3122 : 20544 : }
3123 : :
3124 : : /* Version LOOP before if-converting it; the original loop
3125 : : will be if-converted, the new copy of the loop will not,
3126 : : and the LOOP_VECTORIZED internal call will be guarding which
3127 : : loop to execute. The vectorizer pass will fold this
3128 : : internal call into either true or false.
3129 : :
3130 : : Note that this function intentionally invalidates profile. Both edges
3131 : : out of LOOP_VECTORIZED must have 100% probability so the profile remains
3132 : : consistent after the condition is folded in the vectorizer. */
3133 : :
3134 : : static class loop *
3135 : 20721 : version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds)
3136 : : {
3137 : 20721 : basic_block cond_bb;
3138 : 20721 : tree cond = make_ssa_name (boolean_type_node);
3139 : 20721 : class loop *new_loop;
3140 : 20721 : gimple *g;
3141 : 20721 : gimple_stmt_iterator gsi;
3142 : 20721 : unsigned int save_length = 0;
3143 : :
3144 : 20721 : g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
3145 : 20721 : build_int_cst (integer_type_node, loop->num),
3146 : : integer_zero_node);
3147 : 20721 : gimple_call_set_lhs (g, cond);
3148 : :
3149 : 20721 : void **saved_preds = NULL;
3150 : 20721 : if (any_complicated_phi || need_to_predicate)
3151 : : {
3152 : : /* Save BB->aux around loop_version as that uses the same field. */
3153 : 3024 : save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes;
3154 : 3024 : saved_preds = XALLOCAVEC (void *, save_length);
3155 : 23226 : for (unsigned i = 0; i < save_length; i++)
3156 : 20202 : saved_preds[i] = ifc_bbs[i]->aux;
3157 : : }
3158 : :
3159 : 20721 : initialize_original_copy_tables ();
3160 : : /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED
3161 : : is re-merged in the vectorizer. */
3162 : 20721 : new_loop = loop_version (loop, cond, &cond_bb,
3163 : : profile_probability::always (),
3164 : : profile_probability::always (),
3165 : : profile_probability::always (),
3166 : : profile_probability::always (), true);
3167 : 20721 : free_original_copy_tables ();
3168 : :
3169 : 20721 : if (any_complicated_phi || need_to_predicate)
3170 : 23226 : for (unsigned i = 0; i < save_length; i++)
3171 : 20202 : ifc_bbs[i]->aux = saved_preds[i];
3172 : :
3173 : 20721 : if (new_loop == NULL)
3174 : : return NULL;
3175 : :
3176 : 20721 : new_loop->dont_vectorize = true;
3177 : 20721 : new_loop->force_vectorize = false;
3178 : 20721 : gsi = gsi_last_bb (cond_bb);
3179 : 20721 : gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
3180 : 20721 : if (preds)
3181 : 20721 : preds->safe_push (g);
3182 : 20721 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3183 : 20721 : update_ssa (TODO_update_ssa_no_phi);
3184 : 20721 : return new_loop;
3185 : : }
3186 : :
3187 : : /* Return true when LOOP satisfies the follow conditions that will
3188 : : allow it to be recognized by the vectorizer for outer-loop
3189 : : vectorization:
3190 : : - The loop is not the root node of the loop tree.
3191 : : - The loop has exactly one inner loop.
3192 : : - The loop has a single exit.
3193 : : - The loop header has a single successor, which is the inner
3194 : : loop header.
3195 : : - Each of the inner and outer loop latches have a single
3196 : : predecessor.
3197 : : - The loop exit block has a single predecessor, which is the
3198 : : inner loop's exit block. */
3199 : :
3200 : : static bool
3201 : 20721 : versionable_outer_loop_p (class loop *loop)
3202 : : {
3203 : 20721 : if (!loop_outer (loop)
3204 : 3800 : || loop->dont_vectorize
3205 : 3331 : || !loop->inner
3206 : 3331 : || loop->inner->next
3207 : 1495 : || !single_exit (loop)
3208 : 2554 : || !single_succ_p (loop->header)
3209 : 439 : || single_succ (loop->header) != loop->inner->header
3210 : 878 : || !single_pred_p (loop->latch)
3211 : 21599 : || !single_pred_p (loop->inner->latch))
3212 : 20282 : return false;
3213 : :
3214 : 439 : basic_block outer_exit = single_pred (loop->latch);
3215 : 439 : basic_block inner_exit = single_pred (loop->inner->latch);
3216 : :
3217 : 1300 : if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit)
3218 : : return false;
3219 : :
3220 : 421 : if (dump_file)
3221 : 0 : fprintf (dump_file, "Found vectorizable outer loop for versioning\n");
3222 : :
3223 : : return true;
3224 : : }
3225 : :
3226 : : /* Performs splitting of critical edges. Skip splitting and return false
3227 : : if LOOP will not be converted because:
3228 : :
3229 : : - LOOP is not well formed.
3230 : : - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
3231 : :
3232 : : Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
3233 : :
3234 : : static bool
3235 : 265989 : ifcvt_split_critical_edges (class loop *loop, bool aggressive_if_conv)
3236 : : {
3237 : 265989 : basic_block *body;
3238 : 265989 : basic_block bb;
3239 : 265989 : unsigned int num = loop->num_nodes;
3240 : 265989 : unsigned int i;
3241 : 265989 : edge e;
3242 : 265989 : edge_iterator ei;
3243 : 265989 : auto_vec<edge> critical_edges;
3244 : :
3245 : : /* Loop is not well formed. */
3246 : 265989 : if (loop->inner)
3247 : : return false;
3248 : :
3249 : 189644 : body = get_loop_body (loop);
3250 : 1606780 : for (i = 0; i < num; i++)
3251 : : {
3252 : 1231577 : bb = body[i];
3253 : 1231577 : if (!aggressive_if_conv
3254 : 1223438 : && phi_nodes (bb)
3255 : 1986237 : && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM)
3256 : : {
3257 : 4085 : if (dump_file && (dump_flags & TDF_DETAILS))
3258 : 0 : fprintf (dump_file,
3259 : : "BB %d has complicated PHI with more than %u args.\n",
3260 : : bb->index, MAX_PHI_ARG_NUM);
3261 : :
3262 : 4085 : free (body);
3263 : 4085 : return false;
3264 : : }
3265 : 1227492 : if (bb == loop->latch || bb_with_exit_edge_p (loop, bb))
3266 : 690688 : continue;
3267 : :
3268 : : /* Skip basic blocks not ending with conditional branch. */
3269 : 1073608 : if (!safe_is_a <gcond *> (*gsi_last_bb (bb)))
3270 : 300671 : continue;
3271 : :
3272 : 708399 : FOR_EACH_EDGE (e, ei, bb->succs)
3273 : 579433 : if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
3274 : 107167 : critical_edges.safe_push (e);
3275 : : }
3276 : 185559 : free (body);
3277 : :
3278 : 371608 : while (critical_edges.length () > 0)
3279 : : {
3280 : 105619 : e = critical_edges.pop ();
3281 : : /* Don't split if bb can be predicated along non-critical edge. */
3282 : 105619 : if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest))
3283 : 47601 : split_edge (e);
3284 : : }
3285 : :
3286 : : return true;
3287 : 265989 : }
3288 : :
3289 : : /* Delete redundant statements produced by predication which prevents
3290 : : loop vectorization. */
3291 : :
3292 : : static void
3293 : 20770 : ifcvt_local_dce (class loop *loop)
3294 : : {
3295 : 20770 : gimple *stmt;
3296 : 20770 : gimple *stmt1;
3297 : 20770 : gimple *phi;
3298 : 20770 : gimple_stmt_iterator gsi;
3299 : 20770 : auto_vec<gimple *> worklist;
3300 : 20770 : enum gimple_code code;
3301 : 20770 : use_operand_p use_p;
3302 : 20770 : imm_use_iterator imm_iter;
3303 : :
3304 : : /* The loop has a single BB only. */
3305 : 20770 : basic_block bb = loop->header;
3306 : 20770 : tree latch_vdef = NULL_TREE;
3307 : :
3308 : 20770 : worklist.create (64);
3309 : : /* Consider all phi as live statements. */
3310 : 80349 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3311 : : {
3312 : 59579 : phi = gsi_stmt (gsi);
3313 : 59579 : gimple_set_plf (phi, GF_PLF_2, true);
3314 : 59579 : worklist.safe_push (phi);
3315 : 131419 : if (virtual_operand_p (gimple_phi_result (phi)))
3316 : 12261 : latch_vdef = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
3317 : : }
3318 : : /* Consider load/store statements, CALL and COND as live. */
3319 : 492569 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3320 : : {
3321 : 451029 : stmt = gsi_stmt (gsi);
3322 : 451029 : if (is_gimple_debug (stmt))
3323 : : {
3324 : 162159 : gimple_set_plf (stmt, GF_PLF_2, true);
3325 : 162159 : continue;
3326 : : }
3327 : 288870 : if (gimple_store_p (stmt) || gimple_assign_load_p (stmt))
3328 : : {
3329 : 57595 : gimple_set_plf (stmt, GF_PLF_2, true);
3330 : 57595 : worklist.safe_push (stmt);
3331 : 57595 : continue;
3332 : : }
3333 : 231275 : code = gimple_code (stmt);
3334 : 231275 : if (code == GIMPLE_COND || code == GIMPLE_CALL)
3335 : : {
3336 : 26350 : gimple_set_plf (stmt, GF_PLF_2, true);
3337 : 26350 : worklist.safe_push (stmt);
3338 : 26350 : continue;
3339 : : }
3340 : 204925 : gimple_set_plf (stmt, GF_PLF_2, false);
3341 : :
3342 : 204925 : if (code == GIMPLE_ASSIGN)
3343 : : {
3344 : 204925 : tree lhs = gimple_assign_lhs (stmt);
3345 : 480466 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
3346 : : {
3347 : 287337 : stmt1 = USE_STMT (use_p);
3348 : 287337 : if (!is_gimple_debug (stmt1) && gimple_bb (stmt1) != bb)
3349 : : {
3350 : 11796 : gimple_set_plf (stmt, GF_PLF_2, true);
3351 : 11796 : worklist.safe_push (stmt);
3352 : 11796 : break;
3353 : : }
3354 : : }
3355 : : }
3356 : : }
3357 : : /* Propagate liveness through arguments of live stmt. */
3358 : 357754 : while (worklist.length () > 0)
3359 : : {
3360 : 336984 : ssa_op_iter iter;
3361 : 336984 : use_operand_p use_p;
3362 : 336984 : tree use;
3363 : :
3364 : 336984 : stmt = worklist.pop ();
3365 : 1184361 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3366 : : {
3367 : 510393 : use = USE_FROM_PTR (use_p);
3368 : 510393 : if (TREE_CODE (use) != SSA_NAME)
3369 : 30264 : continue;
3370 : 480129 : stmt1 = SSA_NAME_DEF_STMT (use);
3371 : 480129 : if (gimple_bb (stmt1) != bb || gimple_plf (stmt1, GF_PLF_2))
3372 : 298465 : continue;
3373 : 181664 : gimple_set_plf (stmt1, GF_PLF_2, true);
3374 : 181664 : worklist.safe_push (stmt1);
3375 : : }
3376 : : }
3377 : : /* Delete dead statements. */
3378 : 20770 : gsi = gsi_last_bb (bb);
3379 : 471799 : while (!gsi_end_p (gsi))
3380 : : {
3381 : 451029 : gimple_stmt_iterator gsiprev = gsi;
3382 : 451029 : gsi_prev (&gsiprev);
3383 : 451029 : stmt = gsi_stmt (gsi);
3384 : 466881 : if (gimple_store_p (stmt) && gimple_vdef (stmt))
3385 : : {
3386 : 15852 : tree lhs = gimple_get_lhs (stmt);
3387 : 15852 : ao_ref write;
3388 : 15852 : ao_ref_init (&write, lhs);
3389 : :
3390 : 15852 : if (dse_classify_store (&write, stmt, false, NULL, NULL, latch_vdef)
3391 : : == DSE_STORE_DEAD)
3392 : 336 : delete_dead_or_redundant_assignment (&gsi, "dead");
3393 : 15852 : gsi = gsiprev;
3394 : 15852 : continue;
3395 : 15852 : }
3396 : :
3397 : 435177 : if (gimple_plf (stmt, GF_PLF_2))
3398 : : {
3399 : 423712 : gsi = gsiprev;
3400 : 423712 : continue;
3401 : : }
3402 : 11465 : if (dump_file && (dump_flags & TDF_DETAILS))
3403 : : {
3404 : 13 : fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
3405 : 13 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3406 : : }
3407 : 11465 : gsi_remove (&gsi, true);
3408 : 11465 : release_defs (stmt);
3409 : 11465 : gsi = gsiprev;
3410 : : }
3411 : 20770 : }
3412 : :
3413 : : /* Return true if VALUE is already available on edge PE. */
3414 : :
3415 : : static bool
3416 : 179540 : ifcvt_available_on_edge_p (edge pe, tree value)
3417 : : {
3418 : 179540 : if (is_gimple_min_invariant (value))
3419 : : return true;
3420 : :
3421 : 174776 : if (TREE_CODE (value) == SSA_NAME)
3422 : : {
3423 : 173140 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
3424 : 173140 : if (!def_bb || dominated_by_p (CDI_DOMINATORS, pe->dest, def_bb))
3425 : 19049 : return true;
3426 : : }
3427 : :
3428 : : return false;
3429 : : }
3430 : :
3431 : : /* Return true if STMT can be hoisted from if-converted loop LOOP to
3432 : : edge PE. */
3433 : :
3434 : : static bool
3435 : 439228 : ifcvt_can_hoist (class loop *loop, edge pe, gimple *stmt)
3436 : : {
3437 : 439228 : if (auto *call = dyn_cast<gcall *> (stmt))
3438 : : {
3439 : 5584 : if (gimple_call_internal_p (call)
3440 : 5584 : && internal_fn_mask_index (gimple_call_internal_fn (call)) >= 0)
3441 : : return false;
3442 : : }
3443 : 685915 : else if (auto *assign = dyn_cast<gassign *> (stmt))
3444 : : {
3445 : 309670 : if (gimple_assign_rhs_code (assign) == COND_EXPR)
3446 : : return false;
3447 : : }
3448 : : else
3449 : : return false;
3450 : :
3451 : 225638 : if (gimple_has_side_effects (stmt)
3452 : 224403 : || gimple_could_trap_p (stmt)
3453 : 164412 : || stmt_could_throw_p (cfun, stmt)
3454 : 164395 : || gimple_vdef (stmt)
3455 : 389383 : || gimple_vuse (stmt))
3456 : 62808 : return false;
3457 : :
3458 : 162830 : int num_args = gimple_num_args (stmt);
3459 : 162830 : if (pe != loop_preheader_edge (loop))
3460 : : {
3461 : 183325 : for (int i = 0; i < num_args; ++i)
3462 : 179540 : if (!ifcvt_available_on_edge_p (pe, gimple_arg (stmt, i)))
3463 : : return false;
3464 : : }
3465 : : else
3466 : : {
3467 : 4066 : for (int i = 0; i < num_args; ++i)
3468 : 3821 : if (!expr_invariant_in_loop_p (loop, gimple_arg (stmt, i)))
3469 : : return false;
3470 : : }
3471 : :
3472 : : return true;
3473 : : }
3474 : :
3475 : : /* Hoist invariant statements from LOOP to edge PE. */
3476 : :
3477 : : static void
3478 : 20770 : ifcvt_hoist_invariants (class loop *loop, edge pe)
3479 : : {
3480 : : /* Only hoist from the now unconditionally executed part of the loop. */
3481 : 20770 : basic_block bb = loop->header;
3482 : 20770 : gimple_stmt_iterator hoist_gsi = {};
3483 : 480768 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
3484 : : {
3485 : 439228 : gimple *stmt = gsi_stmt (gsi);
3486 : 439228 : if (ifcvt_can_hoist (loop, pe, stmt))
3487 : : {
3488 : : /* Once we've hoisted one statement, insert other statements
3489 : : after it. */
3490 : 4030 : gsi_remove (&gsi, false);
3491 : 4030 : if (hoist_gsi.ptr)
3492 : 1841 : gsi_insert_after (&hoist_gsi, stmt, GSI_NEW_STMT);
3493 : : else
3494 : : {
3495 : 2189 : gsi_insert_on_edge_immediate (pe, stmt);
3496 : 2189 : hoist_gsi = gsi_for_stmt (stmt);
3497 : : }
3498 : 4030 : continue;
3499 : : }
3500 : 435198 : gsi_next (&gsi);
3501 : : }
3502 : 20770 : }
3503 : :
3504 : : /* Returns the DECL_FIELD_BIT_OFFSET of the bitfield accesse in stmt iff its
3505 : : type mode is not BLKmode. If BITPOS is not NULL it will hold the poly_int64
3506 : : value of the DECL_FIELD_BIT_OFFSET of the bitfield access and STRUCT_EXPR,
3507 : : if not NULL, will hold the tree representing the base struct of this
3508 : : bitfield. */
3509 : :
3510 : : static tree
3511 : 1077 : get_bitfield_rep (gassign *stmt, bool write, tree *bitpos,
3512 : : tree *struct_expr)
3513 : : {
3514 : 1077 : tree comp_ref = write ? gimple_assign_lhs (stmt)
3515 : 354 : : gimple_assign_rhs1 (stmt);
3516 : :
3517 : 1077 : tree field_decl = TREE_OPERAND (comp_ref, 1);
3518 : 1077 : tree ref_offset = component_ref_field_offset (comp_ref);
3519 : 1077 : tree rep_decl = DECL_BIT_FIELD_REPRESENTATIVE (field_decl);
3520 : :
3521 : : /* Bail out if the representative is not a suitable type for a scalar
3522 : : register variable. */
3523 : 1077 : if (!is_gimple_reg_type (TREE_TYPE (rep_decl)))
3524 : : return NULL_TREE;
3525 : :
3526 : : /* Bail out if the DECL_SIZE of the field_decl isn't the same as the BF's
3527 : : precision. */
3528 : 1052 : unsigned HOST_WIDE_INT bf_prec
3529 : 1052 : = TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)));
3530 : 1052 : if (compare_tree_int (DECL_SIZE (field_decl), bf_prec) != 0)
3531 : : return NULL_TREE;
3532 : :
3533 : 1052 : if (TREE_CODE (DECL_FIELD_OFFSET (rep_decl)) != INTEGER_CST
3534 : 1052 : || TREE_CODE (ref_offset) != INTEGER_CST)
3535 : : {
3536 : 2 : if (dump_file && (dump_flags & TDF_DETAILS))
3537 : 2 : fprintf (dump_file, "\t Bitfield NOT OK to lower,"
3538 : : " offset is non-constant.\n");
3539 : 2 : return NULL_TREE;
3540 : : }
3541 : :
3542 : 1050 : if (struct_expr)
3543 : 525 : *struct_expr = TREE_OPERAND (comp_ref, 0);
3544 : :
3545 : 1050 : if (bitpos)
3546 : : {
3547 : : /* To calculate the bitposition of the BITFIELD_REF we have to determine
3548 : : where our bitfield starts in relation to the container REP_DECL. The
3549 : : DECL_FIELD_OFFSET of the original bitfield's member FIELD_DECL tells
3550 : : us how many bytes from the start of the structure there are until the
3551 : : start of the group of bitfield members the FIELD_DECL belongs to,
3552 : : whereas DECL_FIELD_BIT_OFFSET will tell us how many bits from that
3553 : : position our actual bitfield member starts. For the container
3554 : : REP_DECL adding DECL_FIELD_OFFSET and DECL_FIELD_BIT_OFFSET will tell
3555 : : us the distance between the start of the structure and the start of
3556 : : the container, though the first is in bytes and the later other in
3557 : : bits. With this in mind we calculate the bit position of our new
3558 : : BITFIELD_REF by subtracting the number of bits between the start of
3559 : : the structure and the container from the number of bits from the start
3560 : : of the structure and the actual bitfield member. */
3561 : 525 : tree bf_pos = fold_build2 (MULT_EXPR, bitsizetype,
3562 : : ref_offset,
3563 : : build_int_cst (bitsizetype, BITS_PER_UNIT));
3564 : 525 : bf_pos = fold_build2 (PLUS_EXPR, bitsizetype, bf_pos,
3565 : : DECL_FIELD_BIT_OFFSET (field_decl));
3566 : 525 : tree rep_pos = fold_build2 (MULT_EXPR, bitsizetype,
3567 : : DECL_FIELD_OFFSET (rep_decl),
3568 : : build_int_cst (bitsizetype, BITS_PER_UNIT));
3569 : 525 : rep_pos = fold_build2 (PLUS_EXPR, bitsizetype, rep_pos,
3570 : : DECL_FIELD_BIT_OFFSET (rep_decl));
3571 : :
3572 : 525 : *bitpos = fold_build2 (MINUS_EXPR, bitsizetype, bf_pos, rep_pos);
3573 : : }
3574 : :
3575 : : return rep_decl;
3576 : :
3577 : : }
3578 : :
3579 : : /* Lowers the bitfield described by DATA.
3580 : : For a write like:
3581 : :
3582 : : struct.bf = _1;
3583 : :
3584 : : lower to:
3585 : :
3586 : : __ifc_1 = struct.<representative>;
3587 : : __ifc_2 = BIT_INSERT_EXPR (__ifc_1, _1, bitpos);
3588 : : struct.<representative> = __ifc_2;
3589 : :
3590 : : For a read:
3591 : :
3592 : : _1 = struct.bf;
3593 : :
3594 : : lower to:
3595 : :
3596 : : __ifc_1 = struct.<representative>;
3597 : : _1 = BIT_FIELD_REF (__ifc_1, bitsize, bitpos);
3598 : :
3599 : : where representative is a legal load that contains the bitfield value,
3600 : : bitsize is the size of the bitfield and bitpos the offset to the start of
3601 : : the bitfield within the representative. */
3602 : :
3603 : : static void
3604 : 525 : lower_bitfield (gassign *stmt, bool write)
3605 : : {
3606 : 525 : tree struct_expr;
3607 : 525 : tree bitpos;
3608 : 525 : tree rep_decl = get_bitfield_rep (stmt, write, &bitpos, &struct_expr);
3609 : 525 : tree rep_type = TREE_TYPE (rep_decl);
3610 : 525 : tree bf_type = TREE_TYPE (gimple_assign_lhs (stmt));
3611 : :
3612 : 525 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
3613 : 525 : if (dump_file && (dump_flags & TDF_DETAILS))
3614 : : {
3615 : 6 : fprintf (dump_file, "Lowering:\n");
3616 : 6 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3617 : 6 : fprintf (dump_file, "to:\n");
3618 : : }
3619 : :
3620 : : /* REP_COMP_REF is a COMPONENT_REF for the representative. NEW_VAL is it's
3621 : : defining SSA_NAME. */
3622 : 525 : tree rep_comp_ref = build3 (COMPONENT_REF, rep_type, struct_expr, rep_decl,
3623 : : NULL_TREE);
3624 : 525 : tree new_val = ifc_temp_var (rep_type, rep_comp_ref, &gsi);
3625 : :
3626 : 525 : if (dump_file && (dump_flags & TDF_DETAILS))
3627 : 6 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (new_val), 0, TDF_SLIM);
3628 : :
3629 : 525 : if (write)
3630 : : {
3631 : 353 : new_val = ifc_temp_var (rep_type,
3632 : : build3 (BIT_INSERT_EXPR, rep_type, new_val,
3633 : : unshare_expr (gimple_assign_rhs1 (stmt)),
3634 : : bitpos), &gsi);
3635 : :
3636 : 353 : if (dump_file && (dump_flags & TDF_DETAILS))
3637 : 0 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (new_val), 0, TDF_SLIM);
3638 : :
3639 : 353 : gimple *new_stmt = gimple_build_assign (unshare_expr (rep_comp_ref),
3640 : : new_val);
3641 : 353 : gimple_move_vops (new_stmt, stmt);
3642 : 353 : gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
3643 : :
3644 : 353 : if (dump_file && (dump_flags & TDF_DETAILS))
3645 : 0 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
3646 : : }
3647 : : else
3648 : : {
3649 : 172 : tree bfr = build3 (BIT_FIELD_REF, bf_type, new_val,
3650 : 172 : build_int_cst (bitsizetype, TYPE_PRECISION (bf_type)),
3651 : : bitpos);
3652 : 172 : new_val = ifc_temp_var (bf_type, bfr, &gsi);
3653 : :
3654 : 172 : gimple *new_stmt = gimple_build_assign (gimple_assign_lhs (stmt),
3655 : : new_val);
3656 : 172 : gimple_move_vops (new_stmt, stmt);
3657 : 172 : gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
3658 : :
3659 : 172 : if (dump_file && (dump_flags & TDF_DETAILS))
3660 : 6 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
3661 : : }
3662 : :
3663 : 525 : gsi_remove (&gsi, true);
3664 : 525 : }
3665 : :
3666 : : /* Return TRUE if there are bitfields to lower in this LOOP. Fill TO_LOWER
3667 : : with data structures representing these bitfields. */
3668 : :
3669 : : static bool
3670 : 194133 : bitfields_to_lower_p (class loop *loop,
3671 : : vec <gassign *> &reads_to_lower,
3672 : : vec <gassign *> &writes_to_lower)
3673 : : {
3674 : 194133 : gimple_stmt_iterator gsi;
3675 : :
3676 : 194133 : if (dump_file && (dump_flags & TDF_DETAILS))
3677 : : {
3678 : 23 : fprintf (dump_file, "Analyzing loop %d for bitfields:\n", loop->num);
3679 : : }
3680 : :
3681 : 809273 : for (unsigned i = 0; i < loop->num_nodes; ++i)
3682 : : {
3683 : 615171 : basic_block bb = ifc_bbs[i];
3684 : 4603333 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3685 : : {
3686 : 3373022 : gassign *stmt = dyn_cast<gassign*> (gsi_stmt (gsi));
3687 : 3373022 : if (!stmt)
3688 : 3274795 : continue;
3689 : :
3690 : 1670413 : tree op = gimple_assign_lhs (stmt);
3691 : 1670413 : bool write = TREE_CODE (op) == COMPONENT_REF;
3692 : :
3693 : 1670413 : if (!write)
3694 : 1645532 : op = gimple_assign_rhs1 (stmt);
3695 : :
3696 : 1670413 : if (TREE_CODE (op) != COMPONENT_REF)
3697 : 1572186 : continue;
3698 : :
3699 : 98227 : if (DECL_BIT_FIELD_TYPE (TREE_OPERAND (op, 1)))
3700 : : {
3701 : 556 : if (dump_file && (dump_flags & TDF_DETAILS))
3702 : 8 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3703 : :
3704 : 556 : if (TREE_THIS_VOLATILE (op))
3705 : : {
3706 : 4 : if (dump_file && (dump_flags & TDF_DETAILS))
3707 : 0 : fprintf (dump_file, "\t Bitfield NO OK to lower,"
3708 : : " the access is volatile.\n");
3709 : 31 : return false;
3710 : : }
3711 : :
3712 : 552 : if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
3713 : : {
3714 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
3715 : 0 : fprintf (dump_file, "\t Bitfield NO OK to lower,"
3716 : : " field type is not Integral.\n");
3717 : 0 : return false;
3718 : : }
3719 : :
3720 : 552 : if (!get_bitfield_rep (stmt, write, NULL, NULL))
3721 : : {
3722 : 27 : if (dump_file && (dump_flags & TDF_DETAILS))
3723 : 2 : fprintf (dump_file, "\t Bitfield NOT OK to lower,"
3724 : : " representative is BLKmode.\n");
3725 : 27 : return false;
3726 : : }
3727 : :
3728 : 525 : if (dump_file && (dump_flags & TDF_DETAILS))
3729 : 6 : fprintf (dump_file, "\tBitfield OK to lower.\n");
3730 : 525 : if (write)
3731 : 353 : writes_to_lower.safe_push (stmt);
3732 : : else
3733 : 172 : reads_to_lower.safe_push (stmt);
3734 : : }
3735 : : }
3736 : : }
3737 : 388062 : return !reads_to_lower.is_empty () || !writes_to_lower.is_empty ();
3738 : : }
3739 : :
3740 : :
3741 : : /* If-convert LOOP when it is legal. For the moment this pass has no
3742 : : profitability analysis. Returns non-zero todo flags when something
3743 : : changed. */
3744 : :
3745 : : unsigned int
3746 : 426159 : tree_if_conversion (class loop *loop, vec<gimple *> *preds)
3747 : : {
3748 : 426159 : unsigned int todo = 0;
3749 : 426159 : bool aggressive_if_conv;
3750 : 426159 : class loop *rloop;
3751 : 426159 : auto_vec <gassign *, 4> reads_to_lower;
3752 : 426159 : auto_vec <gassign *, 4> writes_to_lower;
3753 : 426159 : bitmap exit_bbs;
3754 : 426159 : edge pe;
3755 : 426159 : auto_vec<data_reference_p, 10> refs;
3756 : 426580 : bool loop_versioned;
3757 : :
3758 : 426580 : again:
3759 : 426580 : rloop = NULL;
3760 : 426580 : ifc_bbs = NULL;
3761 : 426580 : need_to_lower_bitfields = false;
3762 : 426580 : need_to_ifcvt = false;
3763 : 426580 : need_to_predicate = false;
3764 : 426580 : need_to_rewrite_undefined = false;
3765 : 426580 : any_complicated_phi = false;
3766 : 426580 : loop_versioned = false;
3767 : :
3768 : : /* Apply more aggressive if-conversion when loop or its outer loop were
3769 : : marked with simd pragma. When that's the case, we try to if-convert
3770 : : loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
3771 : 426580 : aggressive_if_conv = loop->force_vectorize;
3772 : 426580 : if (!aggressive_if_conv)
3773 : : {
3774 : 418289 : class loop *outer_loop = loop_outer (loop);
3775 : 418289 : if (outer_loop && outer_loop->force_vectorize)
3776 : 8556 : aggressive_if_conv = true;
3777 : : }
3778 : :
3779 : : /* If there are more than two BBs in the loop then there is at least one if
3780 : : to convert. */
3781 : 426580 : if (loop->num_nodes > 2
3782 : 426580 : && !ifcvt_split_critical_edges (loop, aggressive_if_conv))
3783 : 80430 : goto cleanup;
3784 : :
3785 : 346150 : ifc_bbs = get_loop_body_in_if_conv_order (loop);
3786 : 346150 : if (!ifc_bbs)
3787 : : {
3788 : 4587 : if (dump_file && (dump_flags & TDF_DETAILS))
3789 : 6 : fprintf (dump_file, "Irreducible loop\n");
3790 : 4587 : goto cleanup;
3791 : : }
3792 : :
3793 : 341563 : if (find_data_references_in_loop (loop, &refs) == chrec_dont_know)
3794 : 137536 : goto cleanup;
3795 : :
3796 : 204027 : if (loop->num_nodes > 2)
3797 : : {
3798 : : /* More than one loop exit is too much to handle. */
3799 : 105885 : if (!single_exit (loop))
3800 : : {
3801 : 75505 : if (dump_file && (dump_flags & TDF_DETAILS))
3802 : 7 : fprintf (dump_file, "Can not ifcvt due to multiple exits\n");
3803 : : }
3804 : : else
3805 : : {
3806 : 30380 : need_to_ifcvt = true;
3807 : :
3808 : 30380 : if (!if_convertible_loop_p (loop, &refs)
3809 : 30380 : || !dbg_cnt (if_conversion_tree))
3810 : 9836 : goto cleanup;
3811 : :
3812 : 20544 : if ((need_to_predicate || any_complicated_phi)
3813 : 3024 : && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
3814 : 3024 : || loop->dont_vectorize))
3815 : 0 : goto cleanup;
3816 : : }
3817 : : }
3818 : :
3819 : 194191 : if ((flag_tree_loop_vectorize || loop->force_vectorize)
3820 : 194133 : && !loop->dont_vectorize)
3821 : 194133 : need_to_lower_bitfields = bitfields_to_lower_p (loop, reads_to_lower,
3822 : : writes_to_lower);
3823 : :
3824 : 194191 : if (!need_to_ifcvt && !need_to_lower_bitfields)
3825 : 173421 : goto cleanup;
3826 : :
3827 : : /* The edge to insert invariant stmts on. */
3828 : 20770 : pe = loop_preheader_edge (loop);
3829 : :
3830 : : /* Since we have no cost model, always version loops unless the user
3831 : : specified -ftree-loop-if-convert or unless versioning is required.
3832 : : Either version this loop, or if the pattern is right for outer-loop
3833 : : vectorization, version the outer loop. In the latter case we will
3834 : : still if-convert the original inner loop. */
3835 : 20770 : if (need_to_lower_bitfields
3836 : 20543 : || need_to_predicate
3837 : 18846 : || any_complicated_phi
3838 : 17520 : || flag_tree_loop_if_convert != 1)
3839 : : {
3840 : 20721 : class loop *vloop
3841 : 20721 : = (versionable_outer_loop_p (loop_outer (loop))
3842 : 20721 : ? loop_outer (loop) : loop);
3843 : 20721 : class loop *nloop = version_loop_for_if_conversion (vloop, preds);
3844 : 20721 : if (nloop == NULL)
3845 : 0 : goto cleanup;
3846 : 20721 : if (vloop != loop)
3847 : : {
3848 : : /* If versionable_outer_loop_p decided to version the
3849 : : outer loop, version also the inner loop of the non-vectorized
3850 : : loop copy. So we transform:
3851 : : loop1
3852 : : loop2
3853 : : into:
3854 : : if (LOOP_VECTORIZED (1, 3))
3855 : : {
3856 : : loop1
3857 : : loop2
3858 : : }
3859 : : else
3860 : : loop3 (copy of loop1)
3861 : : if (LOOP_VECTORIZED (4, 5))
3862 : : loop4 (copy of loop2)
3863 : : else
3864 : : loop5 (copy of loop4) */
3865 : 421 : gcc_assert (nloop->inner && nloop->inner->next == NULL);
3866 : : rloop = nloop->inner;
3867 : : }
3868 : : else
3869 : : /* If we versioned loop then make sure to insert invariant
3870 : : stmts before the .LOOP_VECTORIZED check since the vectorizer
3871 : : will re-use that for things like runtime alias versioning
3872 : : whose condition can end up using those invariants. */
3873 : 20300 : pe = single_pred_edge (gimple_bb (preds->last ()));
3874 : :
3875 : : loop_versioned = true;
3876 : : }
3877 : :
3878 : 20770 : if (need_to_lower_bitfields)
3879 : : {
3880 : 227 : if (dump_file && (dump_flags & TDF_DETAILS))
3881 : : {
3882 : 6 : fprintf (dump_file, "-------------------------\n");
3883 : 6 : fprintf (dump_file, "Start lowering bitfields\n");
3884 : : }
3885 : 399 : while (!reads_to_lower.is_empty ())
3886 : 172 : lower_bitfield (reads_to_lower.pop (), false);
3887 : 580 : while (!writes_to_lower.is_empty ())
3888 : 353 : lower_bitfield (writes_to_lower.pop (), true);
3889 : :
3890 : 227 : if (dump_file && (dump_flags & TDF_DETAILS))
3891 : : {
3892 : 6 : fprintf (dump_file, "Done lowering bitfields\n");
3893 : 6 : fprintf (dump_file, "-------------------------\n");
3894 : : }
3895 : : }
3896 : 20770 : if (need_to_ifcvt)
3897 : : {
3898 : : /* Before we rewrite edges we'll record their original position in the
3899 : : edge map such that we can map the edges between the ifcvt and the
3900 : : non-ifcvt loop during peeling. */
3901 : 20544 : uintptr_t idx = 0;
3902 : 82176 : for (edge exit : get_loop_exit_edges (loop))
3903 : 20544 : exit->aux = (void*)idx++;
3904 : :
3905 : : /* Now all statements are if-convertible. Combine all the basic
3906 : : blocks into one huge basic block doing the if-conversion
3907 : : on-the-fly. */
3908 : 20544 : combine_blocks (loop, loop_versioned);
3909 : : }
3910 : :
3911 : : std::pair <tree, tree> *name_pair;
3912 : : unsigned ssa_names_idx;
3913 : 25165 : FOR_EACH_VEC_ELT (redundant_ssa_names, ssa_names_idx, name_pair)
3914 : 4395 : replace_uses_by (name_pair->first, name_pair->second);
3915 : 20770 : redundant_ssa_names.release ();
3916 : :
3917 : : /* Perform local CSE, this esp. helps the vectorizer analysis if loads
3918 : : and stores are involved. CSE only the loop body, not the entry
3919 : : PHIs, those are to be kept in sync with the non-if-converted copy.
3920 : : ??? We'll still keep dead stores though. */
3921 : 20770 : exit_bbs = BITMAP_ALLOC (NULL);
3922 : 83203 : for (edge exit : get_loop_exit_edges (loop))
3923 : 20907 : bitmap_set_bit (exit_bbs, exit->dest->index);
3924 : 20770 : todo |= do_rpo_vn (cfun, loop_preheader_edge (loop), exit_bbs,
3925 : : false, true, true);
3926 : :
3927 : : /* Delete dead predicate computations. */
3928 : 20770 : ifcvt_local_dce (loop);
3929 : 20770 : BITMAP_FREE (exit_bbs);
3930 : :
3931 : 20770 : ifcvt_hoist_invariants (loop, pe);
3932 : :
3933 : 20770 : todo |= TODO_cleanup_cfg;
3934 : :
3935 : 426580 : cleanup:
3936 : 426580 : data_reference_p dr;
3937 : 426580 : unsigned int i;
3938 : 1446146 : for (i = 0; refs.iterate (i, &dr); i++)
3939 : : {
3940 : 1019566 : free (dr->aux);
3941 : 1019566 : free_data_ref (dr);
3942 : : }
3943 : 426580 : refs.truncate (0);
3944 : :
3945 : 426580 : if (ifc_bbs)
3946 : : {
3947 : : unsigned int i;
3948 : :
3949 : 1765293 : for (i = 0; i < loop->num_nodes; i++)
3950 : 1444274 : free_bb_predicate (ifc_bbs[i]);
3951 : :
3952 : 321019 : free (ifc_bbs);
3953 : 321019 : ifc_bbs = NULL;
3954 : : }
3955 : 426580 : if (rloop != NULL)
3956 : : {
3957 : 421 : loop = rloop;
3958 : 421 : reads_to_lower.truncate (0);
3959 : 421 : writes_to_lower.truncate (0);
3960 : 421 : goto again;
3961 : : }
3962 : :
3963 : 426159 : return todo;
3964 : 426159 : }
3965 : :
3966 : : /* Tree if-conversion pass management. */
3967 : :
3968 : : namespace {
3969 : :
3970 : : const pass_data pass_data_if_conversion =
3971 : : {
3972 : : GIMPLE_PASS, /* type */
3973 : : "ifcvt", /* name */
3974 : : OPTGROUP_NONE, /* optinfo_flags */
3975 : : TV_TREE_LOOP_IFCVT, /* tv_id */
3976 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
3977 : : 0, /* properties_provided */
3978 : : 0, /* properties_destroyed */
3979 : : 0, /* todo_flags_start */
3980 : : 0, /* todo_flags_finish */
3981 : : };
3982 : :
3983 : : class pass_if_conversion : public gimple_opt_pass
3984 : : {
3985 : : public:
3986 : 281914 : pass_if_conversion (gcc::context *ctxt)
3987 : 563828 : : gimple_opt_pass (pass_data_if_conversion, ctxt)
3988 : : {}
3989 : :
3990 : : /* opt_pass methods: */
3991 : : bool gate (function *) final override;
3992 : : unsigned int execute (function *) final override;
3993 : :
3994 : : }; // class pass_if_conversion
3995 : :
3996 : : bool
3997 : 219536 : pass_if_conversion::gate (function *fun)
3998 : : {
3999 : 31053 : return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
4000 : 190182 : && flag_tree_loop_if_convert != 0)
4001 : 248897 : || flag_tree_loop_if_convert == 1);
4002 : : }
4003 : :
4004 : : unsigned int
4005 : 190197 : pass_if_conversion::execute (function *fun)
4006 : : {
4007 : 190197 : unsigned todo = 0;
4008 : :
4009 : 380394 : if (number_of_loops (fun) <= 1)
4010 : : return 0;
4011 : :
4012 : 190197 : auto_vec<gimple *> preds;
4013 : 1003075 : for (auto loop : loops_list (cfun, 0))
4014 : 432484 : if (flag_tree_loop_if_convert == 1
4015 : 432203 : || ((flag_tree_loop_vectorize || loop->force_vectorize)
4016 : 429570 : && !loop->dont_vectorize))
4017 : 426159 : todo |= tree_if_conversion (loop, &preds);
4018 : :
4019 : 190197 : if (todo)
4020 : : {
4021 : 14993 : free_numbers_of_iterations_estimates (fun);
4022 : 14993 : scev_reset ();
4023 : : }
4024 : :
4025 : 190197 : if (flag_checking)
4026 : : {
4027 : 190193 : basic_block bb;
4028 : 6432821 : FOR_EACH_BB_FN (bb, fun)
4029 : 6242628 : gcc_assert (!bb->aux);
4030 : : }
4031 : :
4032 : : /* Perform IL update now, it might elide some loops. */
4033 : 190197 : if (todo & TODO_cleanup_cfg)
4034 : : {
4035 : 14993 : cleanup_tree_cfg ();
4036 : 14993 : if (need_ssa_update_p (fun))
4037 : 0 : todo |= TODO_update_ssa;
4038 : : }
4039 : 190197 : if (todo & TODO_update_ssa_any)
4040 : 0 : update_ssa (todo & TODO_update_ssa_any);
4041 : :
4042 : : /* If if-conversion elided the loop fall back to the original one. Likewise
4043 : : if the loops are not nested in the same outer loop. */
4044 : 246583 : for (unsigned i = 0; i < preds.length (); ++i)
4045 : : {
4046 : 20721 : gimple *g = preds[i];
4047 : 20721 : if (!gimple_bb (g))
4048 : 0 : continue;
4049 : 20721 : auto ifcvt_loop = get_loop (fun, tree_to_uhwi (gimple_call_arg (g, 0)));
4050 : 20721 : auto orig_loop = get_loop (fun, tree_to_uhwi (gimple_call_arg (g, 1)));
4051 : 20721 : if (!ifcvt_loop || !orig_loop)
4052 : : {
4053 : 2 : if (dump_file)
4054 : 0 : fprintf (dump_file, "If-converted loop vanished\n");
4055 : 2 : fold_loop_internal_call (g, boolean_false_node);
4056 : : }
4057 : 20719 : else if (loop_outer (ifcvt_loop) != loop_outer (orig_loop))
4058 : : {
4059 : 0 : if (dump_file)
4060 : 0 : fprintf (dump_file, "If-converted loop in different outer loop\n");
4061 : 0 : fold_loop_internal_call (g, boolean_false_node);
4062 : : }
4063 : : }
4064 : :
4065 : 190197 : return 0;
4066 : 190197 : }
4067 : :
4068 : : } // anon namespace
4069 : :
4070 : : gimple_opt_pass *
4071 : 281914 : make_pass_if_conversion (gcc::context *ctxt)
4072 : : {
4073 : 281914 : return new pass_if_conversion (ctxt);
4074 : : }
|
