Branch data Line data Source code
1 : : /* If-conversion for vectorizer.
2 : : Copyright (C) 2004-2025 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 : 416103 : innermost_loop_behavior_hash::hash (const value_type &e)
171 : : {
172 : 416103 : hashval_t hash;
173 : :
174 : 416103 : hash = iterative_hash_expr (e->base_address, 0);
175 : 416103 : hash = iterative_hash_expr (e->offset, hash);
176 : 416103 : hash = iterative_hash_expr (e->init, hash);
177 : 416103 : return iterative_hash_expr (e->step, hash);
178 : : }
179 : :
180 : : inline bool
181 : 295832 : innermost_loop_behavior_hash::equal (const value_type &e1,
182 : : const compare_type &e2)
183 : : {
184 : 295832 : if ((e1->base_address && !e2->base_address)
185 : 295832 : || (!e1->base_address && e2->base_address)
186 : 295832 : || (!e1->offset && e2->offset)
187 : 271511 : || (e1->offset && !e2->offset)
188 : 237696 : || (!e1->init && e2->init)
189 : 237696 : || (e1->init && !e2->init)
190 : 237696 : || (!e1->step && e2->step)
191 : 237696 : || (e1->step && !e2->step))
192 : : return false;
193 : :
194 : 237696 : if (e1->base_address && e2->base_address
195 : 475392 : && !operand_equal_p (e1->base_address, e2->base_address, 0))
196 : : return false;
197 : 41860 : if (e1->offset && e2->offset
198 : 119854 : && !operand_equal_p (e1->offset, e2->offset, 0))
199 : : return false;
200 : 41625 : if (e1->init && e2->init
201 : 119384 : && !operand_equal_p (e1->init, e2->init, 0))
202 : : return false;
203 : 16697 : if (e1->step && e2->step
204 : 69528 : && !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 : 1965164 : bb_has_predicate (basic_block bb)
244 : : {
245 : 1965164 : return bb->aux != NULL;
246 : : }
247 : :
248 : : /* Returns the gimplified predicate for basic block BB. */
249 : :
250 : : static inline tree
251 : 890704 : bb_predicate (basic_block bb)
252 : : {
253 : 890704 : 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 : 485869 : set_bb_predicate (basic_block bb, tree cond)
260 : : {
261 : 485869 : auto aux = (struct bb_predicate *) bb->aux;
262 : 485869 : gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
263 : : && is_gimple_val (TREE_OPERAND (cond, 0)))
264 : : || is_gimple_val (cond));
265 : 485869 : aux->predicate = cond;
266 : 485869 : aux->no_predicate_stmts++;
267 : :
268 : 485869 : 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 : 485869 : }
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 : 600043 : bb_predicate_gimplified_stmts (basic_block bb)
278 : : {
279 : 600043 : 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 : 284141 : set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts,
288 : : bool preserve_counts)
289 : : {
290 : 284141 : ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts;
291 : 284141 : if (stmts == NULL && !preserve_counts)
292 : 232540 : ((struct bb_predicate *) bb->aux)->no_predicate_stmts = 0;
293 : 83258 : }
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 : 85392 : 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 : 85392 : for (gimple_stmt_iterator gsi = gsi_start (stmts);
308 : 207653 : !gsi_end_p (gsi); gsi_next (&gsi))
309 : : {
310 : 122261 : gimple *stmt = gsi_stmt (gsi);
311 : 122261 : delink_stmt_imm_use (stmt);
312 : 122261 : gimple_set_modified (stmt, true);
313 : 122261 : ((struct bb_predicate *) bb->aux)->no_predicate_stmts++;
314 : : }
315 : 85392 : gimple_seq_add_seq_without_update
316 : 85392 : (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts);
317 : 85392 : }
318 : :
319 : : /* Return the number of statements the predicate of the basic block consists
320 : : of. */
321 : :
322 : : static inline unsigned
323 : 15723 : get_bb_num_predicate_stmts (basic_block bb)
324 : : {
325 : 15723 : 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 : 200883 : init_bb_predicate (basic_block bb)
332 : : {
333 : 200883 : bb->aux = XNEW (struct bb_predicate);
334 : 200883 : set_bb_predicate_gimplified_stmts (bb, NULL, false);
335 : 200883 : set_bb_predicate (bb, boolean_true_node);
336 : 200883 : }
337 : :
338 : : /* Release the SSA_NAMEs associated with the predicate of basic block BB. */
339 : :
340 : : static inline void
341 : 392933 : release_bb_predicate (basic_block bb)
342 : : {
343 : 392933 : gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
344 : 392933 : if (stmts)
345 : : {
346 : : /* Ensure that these stmts haven't yet been added to a bb. */
347 : 31657 : if (flag_checking)
348 : : for (gimple_stmt_iterator i = gsi_start (stmts);
349 : 86982 : !gsi_end_p (i); gsi_next (&i))
350 : 55325 : gcc_assert (! gimple_bb (gsi_stmt (i)));
351 : :
352 : : /* Discard them. */
353 : 31657 : gimple_seq_discard (stmts);
354 : 31657 : set_bb_predicate_gimplified_stmts (bb, NULL, false);
355 : : }
356 : 392933 : }
357 : :
358 : : /* Free the predicate of basic block BB. */
359 : :
360 : : static inline void
361 : 1773114 : free_bb_predicate (basic_block bb)
362 : : {
363 : 1773114 : if (!bb_has_predicate (bb))
364 : : return;
365 : :
366 : 200883 : release_bb_predicate (bb);
367 : 200883 : free (bb->aux);
368 : 200883 : bb->aux = NULL;
369 : : }
370 : :
371 : : /* Reinitialize predicate of BB with the true predicate. */
372 : :
373 : : static inline void
374 : 192050 : reset_bb_predicate (basic_block bb)
375 : : {
376 : 192050 : if (!bb_has_predicate (bb))
377 : 0 : init_bb_predicate (bb);
378 : : else
379 : : {
380 : 192050 : release_bb_predicate (bb);
381 : 192050 : set_bb_predicate (bb, boolean_true_node);
382 : : }
383 : 192050 : }
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 : 5677 : ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
392 : : {
393 : 5677 : tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
394 : 5677 : gimple *stmt = gimple_build_assign (new_name, expr);
395 : 11354 : gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi)));
396 : 5677 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
397 : 5677 : return new_name;
398 : : }
399 : :
400 : : /* Return true when COND is a false predicate. */
401 : :
402 : : static inline bool
403 : 64241 : is_false_predicate (tree cond)
404 : : {
405 : 64241 : return (cond != NULL_TREE
406 : 64241 : && (cond == boolean_false_node
407 : 64241 : || integer_zerop (cond)));
408 : : }
409 : :
410 : : /* Return true when COND is a true predicate. */
411 : :
412 : : static inline bool
413 : 1029305 : is_true_predicate (tree cond)
414 : : {
415 : 1029305 : return (cond == NULL_TREE
416 : 1029305 : || cond == boolean_true_node
417 : 1476723 : || 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 : 496897 : is_predicated (basic_block bb)
425 : : {
426 : 9833 : 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 : 441288 : parse_predicate (tree cond, tree *op0, tree *op1)
434 : : {
435 : 441288 : gimple *s;
436 : :
437 : 441288 : if (TREE_CODE (cond) == SSA_NAME
438 : 441288 : && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
439 : : {
440 : 61366 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
441 : : {
442 : 29274 : *op0 = gimple_assign_rhs1 (s);
443 : 29274 : *op1 = gimple_assign_rhs2 (s);
444 : 29274 : return gimple_assign_rhs_code (s);
445 : : }
446 : :
447 : 32092 : 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 : 379922 : if (COMPARISON_CLASS_P (cond))
461 : : {
462 : 575 : *op0 = TREE_OPERAND (cond, 0);
463 : 575 : *op1 = TREE_OPERAND (cond, 1);
464 : 575 : 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 : 220644 : fold_or_predicates (location_t loc, tree c1, tree c2)
474 : : {
475 : 220644 : tree op1a, op1b, op2a, op2b;
476 : 220644 : enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
477 : 220644 : enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
478 : :
479 : 220644 : if (code1 != ERROR_MARK && code2 != ERROR_MARK)
480 : : {
481 : 2106 : tree t = maybe_fold_or_comparisons (boolean_type_node, code1, op1a, op1b,
482 : : code2, op2a, op2b);
483 : 2106 : if (t)
484 : : return t;
485 : : }
486 : :
487 : 218607 : 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 : 47826 : 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 : 47826 : 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 : 47826 : gimple_match_op cexpr (gimple_match_cond::UNCOND, COND_EXPR,
510 : 47826 : type, cond, rhs, lhs);
511 : 47826 : if (cexpr.resimplify (NULL, follow_all_ssa_edges))
512 : : {
513 : 10752 : if (gimple_simplified_result_is_gimple_val (&cexpr))
514 : 582 : return cexpr.ops[0];
515 : 10170 : else if (cexpr.code == ABS_EXPR)
516 : 2 : return build1 (ABS_EXPR, type, cexpr.ops[0]);
517 : 10168 : else if (cexpr.code == MIN_EXPR
518 : 10168 : || cexpr.code == MAX_EXPR)
519 : 7171 : return build2 ((tree_code)cexpr.code, type, cexpr.ops[0], cexpr.ops[1]);
520 : : }
521 : :
522 : 40071 : 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 : 158947 : add_to_predicate_list (class loop *loop, basic_block bb, tree nc)
532 : : {
533 : 158947 : tree bc, *tp;
534 : 158947 : basic_block dom_bb;
535 : :
536 : 158947 : if (is_true_predicate (nc))
537 : 71903 : return;
538 : :
539 : : /* If dominance tells us this basic block is always executed,
540 : : don't record any predicates for it. */
541 : 158945 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
542 : : return;
543 : :
544 : 92936 : 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 : 92936 : if (dom_bb != loop->header
550 : 92936 : && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
551 : : {
552 : 5892 : gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
553 : 5892 : bc = bb_predicate (dom_bb);
554 : 5892 : if (!is_true_predicate (bc))
555 : 5892 : set_bb_predicate (bb, bc);
556 : : else
557 : 0 : gcc_assert (is_true_predicate (bb_predicate (bb)));
558 : 5892 : 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 : 5892 : return;
562 : : }
563 : :
564 : 87044 : if (!is_predicated (bb))
565 : 83258 : bc = nc;
566 : : else
567 : : {
568 : 3786 : bc = bb_predicate (bb);
569 : 3786 : bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
570 : 3786 : 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 : 87044 : if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
579 : 31331 : tp = &TREE_OPERAND (bc, 0);
580 : : else
581 : : tp = &bc;
582 : 87044 : if (!is_gimple_val (*tp))
583 : : {
584 : 85392 : gimple_seq stmts;
585 : 85392 : *tp = force_gimple_operand (*tp, &stmts, true, NULL_TREE);
586 : 85392 : add_bb_predicate_gimplified_stmts (bb, stmts);
587 : : }
588 : 87044 : 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 : 104046 : add_to_dst_predicate_list (class loop *loop, edge e,
597 : : tree prev_cond, tree cond)
598 : : {
599 : 104046 : if (!flow_bb_inside_loop_p (loop, e->dest))
600 : : return;
601 : :
602 : 104046 : if (!is_true_predicate (prev_cond))
603 : 22118 : cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
604 : : prev_cond, cond);
605 : :
606 : 104046 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
607 : 83857 : 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 : 3448250 : bb_with_exit_edge_p (const class loop *loop, basic_block bb)
614 : : {
615 : 3448250 : edge e;
616 : 3448250 : edge_iterator ei;
617 : :
618 : 6859662 : FOR_EACH_EDGE (e, ei, bb->succs)
619 : 4839328 : 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 : 5349 : phi_convertible_by_degenerating_args (gphi *phi)
646 : : {
647 : 5349 : edge e;
648 : 5349 : tree arg, t1 = NULL, t2 = NULL;
649 : 5349 : unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0;
650 : 5349 : unsigned int num_args = gimple_phi_num_args (phi);
651 : :
652 : 5349 : gcc_assert (num_args > 2);
653 : :
654 : 19378 : for (i = 0; i < num_args; i++)
655 : : {
656 : 16158 : arg = gimple_phi_arg_def (phi, i);
657 : 16158 : if (t1 == NULL || operand_equal_p (t1, arg, 0))
658 : : {
659 : 8423 : n1++;
660 : 8423 : i1 = i;
661 : 8423 : t1 = arg;
662 : : }
663 : 7735 : else if (t2 == NULL || operand_equal_p (t2, arg, 0))
664 : : {
665 : 5606 : n2++;
666 : 5606 : i2 = i;
667 : 5606 : t2 = arg;
668 : : }
669 : : else
670 : : return false;
671 : : }
672 : :
673 : 3220 : if (n1 != 1 && n2 != 1)
674 : : return false;
675 : :
676 : : /* Check if the edge corresponding to the unique arg is critical. */
677 : 3181 : e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2);
678 : 3181 : 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 : 122919 : if_convertible_phi_p (class loop *loop, basic_block bb, gphi *phi)
691 : : {
692 : 122919 : 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 : 122919 : if (bb != loop->header
699 : 47708 : && gimple_phi_num_args (phi) > 2
700 : 128268 : && !phi_convertible_by_degenerating_args (phi))
701 : 2168 : any_complicated_phi = true;
702 : :
703 : 122919 : 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 : 130518 : hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a)
736 : : {
737 : :
738 : 130518 : data_reference_p *master_dr, *base_master_dr;
739 : 130518 : tree base_ref = DR_BASE_OBJECT (a);
740 : 130518 : innermost_loop_behavior *innermost = &DR_INNERMOST (a);
741 : 130518 : tree ca = bb_predicate (gimple_bb (DR_STMT (a)));
742 : 130518 : bool exist1, exist2;
743 : :
744 : 130518 : master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1);
745 : 130518 : if (!exist1)
746 : 96632 : *master_dr = a;
747 : :
748 : 130518 : if (DR_IS_WRITE (a))
749 : : {
750 : 43151 : IFC_DR (*master_dr)->w_predicate
751 : 86302 : = fold_or_predicates (UNKNOWN_LOCATION, ca,
752 : 43151 : IFC_DR (*master_dr)->w_predicate);
753 : 43151 : if (is_true_predicate (IFC_DR (*master_dr)->w_predicate))
754 : 27656 : DR_W_UNCONDITIONALLY (*master_dr) = true;
755 : : }
756 : 130518 : IFC_DR (*master_dr)->rw_predicate
757 : 261036 : = fold_or_predicates (UNKNOWN_LOCATION, ca,
758 : 130518 : IFC_DR (*master_dr)->rw_predicate);
759 : 130518 : if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate))
760 : 96190 : DR_RW_UNCONDITIONALLY (*master_dr) = true;
761 : :
762 : 130518 : if (DR_IS_WRITE (a))
763 : : {
764 : 43151 : base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2);
765 : 43151 : if (!exist2)
766 : 32891 : *base_master_dr = a;
767 : 43151 : IFC_DR (*base_master_dr)->base_w_predicate
768 : 86302 : = fold_or_predicates (UNKNOWN_LOCATION, ca,
769 : 43151 : IFC_DR (*base_master_dr)->base_w_predicate);
770 : 43151 : if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate))
771 : 27890 : DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true;
772 : : }
773 : 130518 : }
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 : 210785 : idx_within_array_bound (tree ref, tree *idx, void *dta)
780 : : {
781 : 210785 : wi::overflow_type overflow;
782 : 210785 : widest_int niter, valid_niter, delta, wi_step;
783 : 210785 : tree ev, init, step;
784 : 210785 : tree low, high;
785 : 210785 : class loop *loop = (class loop*) dta;
786 : :
787 : : /* Only support within-bound access for array references. */
788 : 210785 : 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 : 132625 : if (array_ref_flexible_size_p (ref))
794 : : return false;
795 : :
796 : 86838 : ev = analyze_scalar_evolution (loop, *idx);
797 : 86838 : ev = instantiate_parameters (loop, ev);
798 : 86838 : init = initial_condition (ev);
799 : 86838 : step = evolution_part_in_loop_num (ev, loop->num);
800 : :
801 : 86838 : if (!init || TREE_CODE (init) != INTEGER_CST
802 : 77589 : || (step && TREE_CODE (step) != INTEGER_CST))
803 : : return false;
804 : :
805 : 77583 : low = array_ref_low_bound (ref);
806 : 77583 : high = array_ref_up_bound (ref);
807 : :
808 : : /* The case of nonconstant bounds could be handled, but it would be
809 : : complicated. */
810 : 77583 : if (TREE_CODE (low) != INTEGER_CST
811 : 77583 : || !high || TREE_CODE (high) != INTEGER_CST)
812 : : return false;
813 : :
814 : : /* Check if the intial idx is within bound. */
815 : 77515 : if (wi::to_widest (init) < wi::to_widest (low)
816 : 155022 : || wi::to_widest (init) > wi::to_widest (high))
817 : 15 : return false;
818 : :
819 : : /* The idx is always within bound. */
820 : 77500 : if (!step || integer_zerop (step))
821 : 1958 : return true;
822 : :
823 : 75542 : if (!max_loop_iterations (loop, &niter))
824 : : return false;
825 : :
826 : 75542 : if (wi::to_widest (step) < 0)
827 : : {
828 : 300 : delta = wi::to_widest (init) - wi::to_widest (low);
829 : 300 : wi_step = -wi::to_widest (step);
830 : : }
831 : : else
832 : : {
833 : 75242 : delta = wi::to_widest (high) - wi::to_widest (init);
834 : 75242 : wi_step = wi::to_widest (step);
835 : : }
836 : :
837 : 75542 : valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow);
838 : : /* The iteration space of idx is within array bound. */
839 : 151084 : if (!overflow && niter <= valid_niter)
840 : : return true;
841 : :
842 : : return false;
843 : 210785 : }
844 : :
845 : : /* Return TRUE if ref is a within bound array reference. */
846 : :
847 : : bool
848 : 205432 : ref_within_array_bound (gimple *stmt, tree ref)
849 : : {
850 : 205432 : class loop *loop = loop_containing_stmt (stmt);
851 : :
852 : 205432 : gcc_assert (loop != NULL);
853 : 205432 : 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 : 1966 : base_object_writable (tree ref)
864 : : {
865 : 1966 : tree base_tree = get_base_address (ref);
866 : :
867 : 1966 : return (base_tree
868 : 1966 : && DECL_P (base_tree)
869 : 1625 : && decl_binds_to_current_def_p (base_tree)
870 : 3587 : && !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 : 18773 : 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 : 18773 : if (gimple_uid (stmt) == 0)
904 : : return false;
905 : :
906 : 18772 : data_reference_p *master_dr, *base_master_dr;
907 : 18772 : data_reference_p a = drs[gimple_uid (stmt) - 1];
908 : :
909 : 18772 : tree base = DR_BASE_OBJECT (a);
910 : 18772 : innermost_loop_behavior *innermost = &DR_INNERMOST (a);
911 : :
912 : 18772 : gcc_assert (DR_STMT (a) == stmt);
913 : 18772 : gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a)
914 : : || DR_INIT (a) || DR_STEP (a));
915 : :
916 : 18772 : master_dr = innermost_DR_map->get (innermost);
917 : 18772 : gcc_assert (master_dr != NULL);
918 : :
919 : 18772 : base_master_dr = baseref_DR_map->get (base);
920 : :
921 : : /* If a is unconditionally written to it doesn't trap. */
922 : 18772 : 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 : 17079 : if (DR_RW_UNCONDITIONALLY (*master_dr)
931 : 17079 : || ref_within_array_bound (stmt, DR_REF (a)))
932 : : {
933 : : /* an unconditional read won't trap. */
934 : 5952 : 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 : 2011 : if ((base_master_dr
940 : 2011 : && DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
941 : : /* or the base is known to be not readonly. */
942 : 3977 : || base_object_writable (DR_REF (a)))
943 : 1666 : return !ref_can_have_store_data_races (base);
944 : : }
945 : :
946 : : return false;
947 : : }
948 : :
949 : : /* Return true if STMT could be converted into a masked load or store
950 : : (conditional load or store based on a mask computed from bb predicate). */
951 : :
952 : : static bool
953 : 11387 : ifcvt_can_use_mask_load_store (gimple *stmt)
954 : : {
955 : : /* Check whether this is a load or store. */
956 : 11387 : tree lhs = gimple_assign_lhs (stmt);
957 : 11387 : bool is_load;
958 : 11387 : tree ref;
959 : 11387 : if (gimple_store_p (stmt))
960 : : {
961 : 2083 : if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
962 : : return false;
963 : : is_load = false;
964 : : ref = lhs;
965 : : }
966 : 9304 : else if (gimple_assign_load_p (stmt))
967 : : {
968 : 9303 : is_load = true;
969 : 9303 : ref = gimple_assign_rhs1 (stmt);
970 : : }
971 : : else
972 : : return false;
973 : :
974 : 11386 : if (may_be_nonaddressable_p (ref))
975 : : return false;
976 : :
977 : : /* Mask should be integer mode of the same size as the load/store
978 : : mode. */
979 : 11326 : machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
980 : 11326 : if (!int_mode_for_mode (mode).exists () || VECTOR_MODE_P (mode))
981 : 31 : return false;
982 : :
983 : 11295 : if (can_vec_mask_load_store_p (mode, VOIDmode, is_load))
984 : : return true;
985 : :
986 : : return false;
987 : : }
988 : :
989 : : /* Return true if STMT could be converted from an operation that is
990 : : unconditional to one that is conditional on a bb predicate mask. */
991 : :
992 : : static bool
993 : 13107 : ifcvt_can_predicate (gimple *stmt)
994 : : {
995 : 13107 : basic_block bb = gimple_bb (stmt);
996 : :
997 : 320 : if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
998 : 13107 : || bb->loop_father->dont_vectorize
999 : 26214 : || gimple_has_volatile_ops (stmt))
1000 : : return false;
1001 : :
1002 : 13107 : if (gimple_assign_single_p (stmt))
1003 : 11387 : return ifcvt_can_use_mask_load_store (stmt);
1004 : :
1005 : 1720 : tree_code code = gimple_assign_rhs_code (stmt);
1006 : 1720 : tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
1007 : 1720 : tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1008 : 1720 : if (!types_compatible_p (lhs_type, rhs_type))
1009 : : return false;
1010 : 1089 : internal_fn cond_fn = get_conditional_internal_fn (code);
1011 : 1089 : return (cond_fn != IFN_LAST
1012 : 1089 : && vectorized_internal_fn_supported_p (cond_fn, lhs_type));
1013 : : }
1014 : :
1015 : : /* Return true when STMT is if-convertible.
1016 : :
1017 : : GIMPLE_ASSIGN statement is not if-convertible if,
1018 : : - it is not movable,
1019 : : - it could trap,
1020 : : - LHS is not var decl. */
1021 : :
1022 : : static bool
1023 : 63589 : if_convertible_gimple_assign_stmt_p (gimple *stmt,
1024 : : vec<data_reference_p> refs)
1025 : : {
1026 : 63589 : tree lhs = gimple_assign_lhs (stmt);
1027 : :
1028 : 63589 : if (dump_file && (dump_flags & TDF_DETAILS))
1029 : : {
1030 : 26 : fprintf (dump_file, "-------------------------\n");
1031 : 26 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1032 : : }
1033 : :
1034 : 63589 : if (!is_gimple_reg_type (TREE_TYPE (lhs)))
1035 : : return false;
1036 : :
1037 : : /* Some of these constrains might be too conservative. */
1038 : 63331 : if (stmt_ends_bb_p (stmt)
1039 : 63331 : || gimple_has_volatile_ops (stmt)
1040 : 63250 : || (TREE_CODE (lhs) == SSA_NAME
1041 : 59491 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1042 : 126581 : || gimple_has_side_effects (stmt))
1043 : : {
1044 : 81 : if (dump_file && (dump_flags & TDF_DETAILS))
1045 : 0 : fprintf (dump_file, "stmt not suitable for ifcvt\n");
1046 : 81 : return false;
1047 : : }
1048 : :
1049 : : /* tree-into-ssa.cc uses GF_PLF_1, so avoid it, because
1050 : : in between if_convertible_loop_p and combine_blocks
1051 : : we can perform loop versioning. */
1052 : 63250 : gimple_set_plf (stmt, GF_PLF_2, false);
1053 : :
1054 : 63250 : if ((! gimple_vuse (stmt)
1055 : 18773 : || gimple_could_trap_p_1 (stmt, false, false)
1056 : 18773 : || ! ifcvt_memrefs_wont_trap (stmt, refs))
1057 : 75159 : && gimple_could_trap_p (stmt))
1058 : : {
1059 : 13107 : if (ifcvt_can_predicate (stmt))
1060 : : {
1061 : 2548 : gimple_set_plf (stmt, GF_PLF_2, true);
1062 : 2548 : need_to_predicate = true;
1063 : 2548 : return true;
1064 : : }
1065 : 10559 : if (dump_file && (dump_flags & TDF_DETAILS))
1066 : 0 : fprintf (dump_file, "tree could trap...\n");
1067 : 10559 : return false;
1068 : : }
1069 : 50143 : else if (gimple_needing_rewrite_undefined (stmt))
1070 : : /* We have to rewrite stmts with undefined overflow. */
1071 : 18991 : need_to_rewrite_undefined = true;
1072 : :
1073 : : /* When if-converting stores force versioning, likewise if we
1074 : : ended up generating store data races. */
1075 : 100286 : if (gimple_vdef (stmt))
1076 : 1676 : need_to_predicate = true;
1077 : :
1078 : : return true;
1079 : : }
1080 : :
1081 : : /* Return true when SW switch statement is equivalent to cond, that
1082 : : all non default labels point to the same label.
1083 : :
1084 : : Fallthrough is not checked for and could even happen
1085 : : with cond (using goto), so is handled.
1086 : :
1087 : : This is intended for switches created by the if-switch-conversion
1088 : : pass, but can handle some programmer supplied cases too. */
1089 : :
1090 : : static bool
1091 : 14 : if_convertible_switch_p (gswitch *sw)
1092 : : {
1093 : 14 : if (gimple_switch_num_labels (sw) <= 1)
1094 : : return false;
1095 : 14 : tree label = CASE_LABEL (gimple_switch_label (sw, 1));
1096 : 43 : for (unsigned i = 1; i < gimple_switch_num_labels (sw); i++)
1097 : : {
1098 : 29 : if (CASE_LABEL (gimple_switch_label (sw, i)) != label)
1099 : : return false;
1100 : : }
1101 : : return true;
1102 : : }
1103 : :
1104 : : /* Return true when STMT is if-convertible.
1105 : :
1106 : : A statement is if-convertible if:
1107 : : - it is an if-convertible GIMPLE_ASSIGN,
1108 : : - it is a GIMPLE_LABEL or a GIMPLE_COND,
1109 : : - it is a switch equivalent to COND
1110 : : - it is builtins call,
1111 : : - it is a call to a function with a SIMD clone. */
1112 : :
1113 : : static bool
1114 : 124572 : if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs)
1115 : : {
1116 : 124572 : switch (gimple_code (stmt))
1117 : : {
1118 : : case GIMPLE_LABEL:
1119 : : case GIMPLE_DEBUG:
1120 : : case GIMPLE_COND:
1121 : : return true;
1122 : :
1123 : 14 : case GIMPLE_SWITCH:
1124 : 14 : return if_convertible_switch_p (as_a <gswitch *> (stmt));
1125 : :
1126 : 63589 : case GIMPLE_ASSIGN:
1127 : 63589 : return if_convertible_gimple_assign_stmt_p (stmt, refs);
1128 : :
1129 : 1416 : case GIMPLE_CALL:
1130 : 1416 : {
1131 : 1416 : tree fndecl = gimple_call_fndecl (stmt);
1132 : 1416 : if (fndecl)
1133 : : {
1134 : : /* We can vectorize some builtins and functions with SIMD
1135 : : "inbranch" clones. */
1136 : 1168 : struct cgraph_node *node = cgraph_node::get (fndecl);
1137 : 1168 : if (node && node->simd_clones != NULL)
1138 : : /* Ensure that at least one clone can be "inbranch". */
1139 : 1927 : for (struct cgraph_node *n = node->simd_clones; n != NULL;
1140 : 944 : n = n->simdclone->next_clone)
1141 : 1926 : if (n->simdclone->inbranch)
1142 : : {
1143 : 982 : gimple_set_plf (stmt, GF_PLF_2, true);
1144 : 982 : need_to_predicate = true;
1145 : 982 : return true;
1146 : : }
1147 : : }
1148 : :
1149 : : /* There are some IFN_s that are used to replace builtins but have the
1150 : : same semantics. Even if MASK_CALL cannot handle them vectorable_call
1151 : : will insert the proper selection, so do not block conversion. */
1152 : 434 : int flags = gimple_call_flags (stmt);
1153 : 434 : if ((flags & ECF_CONST)
1154 : 434 : && !(flags & ECF_LOOPING_CONST_OR_PURE)
1155 : 868 : && gimple_call_combined_fn (stmt) != CFN_LAST)
1156 : : return true;
1157 : :
1158 : : return false;
1159 : : }
1160 : :
1161 : 0 : default:
1162 : : /* Don't know what to do with 'em so don't do anything. */
1163 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1164 : : {
1165 : 0 : fprintf (dump_file, "don't know what to do\n");
1166 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1167 : : }
1168 : : return false;
1169 : : }
1170 : : }
1171 : :
1172 : : /* Assumes that BB has more than 1 predecessors.
1173 : : Returns false if at least one successor is not on critical edge
1174 : : and true otherwise. */
1175 : :
1176 : : static inline bool
1177 : 84367 : all_preds_critical_p (basic_block bb)
1178 : : {
1179 : 84367 : edge e;
1180 : 84367 : edge_iterator ei;
1181 : :
1182 : 164103 : FOR_EACH_EDGE (e, ei, bb->preds)
1183 : 144151 : if (EDGE_COUNT (e->src->succs) == 1)
1184 : : return false;
1185 : : return true;
1186 : : }
1187 : :
1188 : : /* Return true when BB is if-convertible. This routine does not check
1189 : : basic block's statements and phis.
1190 : :
1191 : : A basic block is not if-convertible if:
1192 : : - it is non-empty and it is after the exit block (in BFS order),
1193 : : - it is after the exit block but before the latch,
1194 : : - its edges are not normal.
1195 : :
1196 : : EXIT_BB is the basic block containing the exit of the LOOP. BB is
1197 : : inside LOOP. */
1198 : :
1199 : : static bool
1200 : 206937 : if_convertible_bb_p (class loop *loop, basic_block bb, basic_block exit_bb)
1201 : : {
1202 : 206937 : edge e;
1203 : 206937 : edge_iterator ei;
1204 : :
1205 : 206937 : if (dump_file && (dump_flags & TDF_DETAILS))
1206 : 77 : fprintf (dump_file, "----------[%d]-------------\n", bb->index);
1207 : :
1208 : 206937 : if (EDGE_COUNT (bb->succs) > 2)
1209 : : return false;
1210 : :
1211 : 413760 : if (gcall *call = safe_dyn_cast <gcall *> (*gsi_last_bb (bb)))
1212 : 185 : if (gimple_call_ctrl_altering_p (call))
1213 : : return false;
1214 : :
1215 : 206880 : if (exit_bb)
1216 : : {
1217 : 38186 : if (bb != loop->latch)
1218 : : {
1219 : 541 : if (dump_file && (dump_flags & TDF_DETAILS))
1220 : 0 : fprintf (dump_file, "basic block after exit bb but before latch\n");
1221 : 541 : return false;
1222 : : }
1223 : 37645 : else if (!empty_block_p (bb))
1224 : : {
1225 : 752 : if (dump_file && (dump_flags & TDF_DETAILS))
1226 : 0 : fprintf (dump_file, "non empty basic block after exit bb\n");
1227 : 752 : return false;
1228 : : }
1229 : 36893 : else if (bb == loop->latch
1230 : 36893 : && bb != exit_bb
1231 : 73786 : && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
1232 : : {
1233 : 8 : if (dump_file && (dump_flags & TDF_DETAILS))
1234 : 0 : fprintf (dump_file, "latch is not dominated by exit_block\n");
1235 : 8 : return false;
1236 : : }
1237 : : }
1238 : :
1239 : : /* Be less adventurous and handle only normal edges. */
1240 : 503047 : FOR_EACH_EDGE (e, ei, bb->succs)
1241 : 297476 : if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
1242 : : {
1243 : 8 : if (dump_file && (dump_flags & TDF_DETAILS))
1244 : 0 : fprintf (dump_file, "Difficult to handle edges\n");
1245 : 8 : return false;
1246 : : }
1247 : :
1248 : : return true;
1249 : : }
1250 : :
1251 : : /* Return true when all predecessor blocks of BB are visited. The
1252 : : VISITED bitmap keeps track of the visited blocks. */
1253 : :
1254 : : static bool
1255 : 2356443 : pred_blocks_visited_p (basic_block bb, bitmap *visited)
1256 : : {
1257 : 2356443 : edge e;
1258 : 2356443 : edge_iterator ei;
1259 : 4057858 : FOR_EACH_EDGE (e, ei, bb->preds)
1260 : 2672179 : if (!bitmap_bit_p (*visited, e->src->index))
1261 : : return false;
1262 : :
1263 : : return true;
1264 : : }
1265 : :
1266 : : /* Get body of a LOOP in suitable order for if-conversion. It is
1267 : : caller's responsibility to deallocate basic block list.
1268 : : If-conversion suitable order is, breadth first sort (BFS) order
1269 : : with an additional constraint: select a block only if all its
1270 : : predecessors are already selected. */
1271 : :
1272 : : static basic_block *
1273 : 399337 : get_loop_body_in_if_conv_order (const class loop *loop)
1274 : : {
1275 : 399337 : basic_block *blocks, *blocks_in_bfs_order;
1276 : 399337 : basic_block bb;
1277 : 399337 : bitmap visited;
1278 : 399337 : unsigned int index = 0;
1279 : 399337 : unsigned int visited_count = 0;
1280 : :
1281 : 399337 : gcc_assert (loop->num_nodes);
1282 : 399337 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1283 : :
1284 : 399337 : blocks = XCNEWVEC (basic_block, loop->num_nodes);
1285 : 399337 : visited = BITMAP_ALLOC (NULL);
1286 : :
1287 : 399337 : blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1288 : :
1289 : 399337 : index = 0;
1290 : 4148968 : while (index < loop->num_nodes)
1291 : : {
1292 : 3350337 : bb = blocks_in_bfs_order [index];
1293 : :
1294 : 3350337 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1295 : : {
1296 : 43 : free (blocks_in_bfs_order);
1297 : 43 : BITMAP_FREE (visited);
1298 : 43 : free (blocks);
1299 : 43 : return NULL;
1300 : : }
1301 : :
1302 : 3350294 : if (!bitmap_bit_p (visited, bb->index))
1303 : : {
1304 : 2356443 : if (pred_blocks_visited_p (bb, &visited)
1305 : 2356443 : || bb == loop->header)
1306 : : {
1307 : : /* This block is now visited. */
1308 : 1785016 : bitmap_set_bit (visited, bb->index);
1309 : 1785016 : blocks[visited_count++] = bb;
1310 : : }
1311 : : }
1312 : :
1313 : 3350294 : index++;
1314 : :
1315 : 3350294 : if (index == loop->num_nodes
1316 : 466157 : && visited_count != loop->num_nodes)
1317 : : /* Not done yet. */
1318 : 3350294 : index = 0;
1319 : : }
1320 : 399294 : free (blocks_in_bfs_order);
1321 : 399294 : BITMAP_FREE (visited);
1322 : :
1323 : : /* Go through loop and reject if-conversion or lowering of bitfields if we
1324 : : encounter statements we do not believe the vectorizer will be able to
1325 : : handle. If adding a new type of statement here, make sure
1326 : : 'ifcvt_local_dce' is also able to handle it propertly. */
1327 : 2173741 : for (index = 0; index < loop->num_nodes; index++)
1328 : : {
1329 : 1776916 : basic_block bb = blocks[index];
1330 : 1776916 : gimple_stmt_iterator gsi;
1331 : :
1332 : 1776916 : bool may_have_nonlocal_labels
1333 : 1776916 : = bb_with_exit_edge_p (loop, bb) || bb == loop->latch;
1334 : 15659626 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1335 : 12108263 : switch (gimple_code (gsi_stmt (gsi)))
1336 : : {
1337 : 39994 : case GIMPLE_LABEL:
1338 : 39994 : if (!may_have_nonlocal_labels)
1339 : : {
1340 : 6905 : tree label
1341 : 6905 : = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi)));
1342 : 13810 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1343 : : {
1344 : 47 : free (blocks);
1345 : 47 : return NULL;
1346 : : }
1347 : : }
1348 : : /* Fallthru. */
1349 : 12105794 : case GIMPLE_ASSIGN:
1350 : 12105794 : case GIMPLE_CALL:
1351 : 12105794 : case GIMPLE_DEBUG:
1352 : 12105794 : case GIMPLE_COND:
1353 : 12105794 : case GIMPLE_SWITCH:
1354 : 12105794 : gimple_set_uid (gsi_stmt (gsi), 0);
1355 : 12105794 : break;
1356 : 2422 : default:
1357 : 2422 : free (blocks);
1358 : 2422 : return NULL;
1359 : : }
1360 : : }
1361 : : return blocks;
1362 : : }
1363 : :
1364 : : /* Returns true when the analysis of the predicates for all the basic
1365 : : blocks in LOOP succeeded.
1366 : :
1367 : : predicate_bbs first allocates the predicates of the basic blocks.
1368 : : These fields are then initialized with the tree expressions
1369 : : representing the predicates under which a basic block is executed
1370 : : in the LOOP. As the loop->header is executed at each iteration, it
1371 : : has the "true" predicate. Other statements executed under a
1372 : : condition are predicated with that condition, for example
1373 : :
1374 : : | if (x)
1375 : : | S1;
1376 : : | else
1377 : : | S2;
1378 : :
1379 : : S1 will be predicated with "x", and
1380 : : S2 will be predicated with "!x". */
1381 : :
1382 : : static void
1383 : 36885 : predicate_bbs (loop_p loop)
1384 : : {
1385 : 36885 : unsigned int i;
1386 : :
1387 : 237768 : for (i = 0; i < loop->num_nodes; i++)
1388 : 200883 : init_bb_predicate (ifc_bbs[i]);
1389 : :
1390 : 237768 : for (i = 0; i < loop->num_nodes; i++)
1391 : : {
1392 : 200883 : basic_block bb = ifc_bbs[i];
1393 : 200883 : tree cond;
1394 : :
1395 : : /* The loop latch and loop exit block are always executed and
1396 : : have no extra conditions to be processed: skip them. */
1397 : 274653 : if (bb == loop->latch
1398 : 200883 : || bb_with_exit_edge_p (loop, bb))
1399 : : {
1400 : 73770 : reset_bb_predicate (bb);
1401 : 73770 : continue;
1402 : : }
1403 : :
1404 : 127113 : cond = bb_predicate (bb);
1405 : 254226 : if (gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
1406 : : {
1407 : 51951 : tree c2;
1408 : 51951 : edge true_edge, false_edge;
1409 : 51951 : location_t loc = gimple_location (stmt);
1410 : 51951 : tree c;
1411 : : /* gcc.dg/fold-bopcond-1.c shows that despite all forwprop passes
1412 : : conditions can remain unfolded because of multiple uses so
1413 : : try to re-fold here, especially to get precision changing
1414 : : conversions sorted out. Do not simply fold the stmt since
1415 : : this is analysis only. When conditions were embedded in
1416 : : COND_EXPRs those were folded separately before folding the
1417 : : COND_EXPR but as they are now outside we have to make sure
1418 : : to fold them. Do it here - another opportunity would be to
1419 : : fold predicates as they are inserted. */
1420 : 51951 : gimple_match_op cexpr (gimple_match_cond::UNCOND,
1421 : 51951 : gimple_cond_code (stmt),
1422 : : boolean_type_node,
1423 : : gimple_cond_lhs (stmt),
1424 : 51951 : gimple_cond_rhs (stmt));
1425 : 51951 : if (cexpr.resimplify (NULL, follow_all_ssa_edges)
1426 : 3735 : && cexpr.code.is_tree_code ()
1427 : 55686 : && TREE_CODE_CLASS ((tree_code)cexpr.code) == tcc_comparison)
1428 : 565 : c = build2_loc (loc, (tree_code)cexpr.code, boolean_type_node,
1429 : : cexpr.ops[0], cexpr.ops[1]);
1430 : : else
1431 : 51386 : c = build2_loc (loc, gimple_cond_code (stmt),
1432 : : boolean_type_node,
1433 : : gimple_cond_lhs (stmt),
1434 : : gimple_cond_rhs (stmt));
1435 : :
1436 : : /* Add new condition into destination's predicate list. */
1437 : 51951 : extract_true_false_edges_from_block (gimple_bb (stmt),
1438 : : &true_edge, &false_edge);
1439 : :
1440 : : /* If C is true, then TRUE_EDGE is taken. */
1441 : 51951 : add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1442 : : unshare_expr (c));
1443 : :
1444 : : /* If C is false, then FALSE_EDGE is taken. */
1445 : 51951 : c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1446 : : unshare_expr (c));
1447 : 51951 : add_to_dst_predicate_list (loop, false_edge,
1448 : : unshare_expr (cond), c2);
1449 : :
1450 : 51951 : cond = NULL_TREE;
1451 : : }
1452 : :
1453 : : /* Assumes the limited COND like switches checked for earlier. */
1454 : 75162 : else if (gswitch *sw = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
1455 : : {
1456 : 72 : location_t loc = gimple_location (*gsi_last_bb (bb));
1457 : :
1458 : 72 : tree default_label = CASE_LABEL (gimple_switch_default_label (sw));
1459 : 72 : tree cond_label = CASE_LABEL (gimple_switch_label (sw, 1));
1460 : :
1461 : 72 : edge false_edge = find_edge (bb, label_to_block (cfun, default_label));
1462 : 72 : edge true_edge = find_edge (bb, label_to_block (cfun, cond_label));
1463 : :
1464 : : /* Create chain of switch tests for each case. */
1465 : 72 : tree switch_cond = NULL_TREE;
1466 : 72 : tree index = gimple_switch_index (sw);
1467 : 278 : for (unsigned i = 1; i < gimple_switch_num_labels (sw); i++)
1468 : : {
1469 : 206 : tree label = gimple_switch_label (sw, i);
1470 : 206 : tree case_cond;
1471 : 206 : if (CASE_HIGH (label))
1472 : : {
1473 : 7 : tree low = build2_loc (loc, GE_EXPR,
1474 : : boolean_type_node,
1475 : 7 : index, fold_convert_loc (loc, TREE_TYPE (index),
1476 : 7 : CASE_LOW (label)));
1477 : 14 : tree high = build2_loc (loc, LE_EXPR,
1478 : : boolean_type_node,
1479 : 7 : index, fold_convert_loc (loc, TREE_TYPE (index),
1480 : 7 : CASE_HIGH (label)));
1481 : 7 : case_cond = build2_loc (loc, TRUTH_AND_EXPR,
1482 : : boolean_type_node,
1483 : : low, high);
1484 : : }
1485 : : else
1486 : 199 : case_cond = build2_loc (loc, EQ_EXPR,
1487 : : boolean_type_node,
1488 : : index,
1489 : 199 : fold_convert_loc (loc, TREE_TYPE (index),
1490 : 199 : CASE_LOW (label)));
1491 : 206 : if (i > 1)
1492 : 134 : switch_cond = build2_loc (loc, TRUTH_OR_EXPR,
1493 : : boolean_type_node,
1494 : : case_cond, switch_cond);
1495 : : else
1496 : : switch_cond = case_cond;
1497 : : }
1498 : :
1499 : 72 : add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1500 : : unshare_expr (switch_cond));
1501 : 72 : switch_cond = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1502 : : unshare_expr (switch_cond));
1503 : 72 : add_to_dst_predicate_list (loop, false_edge,
1504 : : unshare_expr (cond), switch_cond);
1505 : 72 : cond = NULL_TREE;
1506 : : }
1507 : :
1508 : : /* If current bb has only one successor, then consider it as an
1509 : : unconditional goto. */
1510 : 275973 : if (single_succ_p (bb))
1511 : : {
1512 : 75090 : basic_block bb_n = single_succ (bb);
1513 : :
1514 : : /* The successor bb inherits the predicate of its
1515 : : predecessor. If there is no predicate in the predecessor
1516 : : bb, then consider the successor bb as always executed. */
1517 : 75090 : if (cond == NULL_TREE)
1518 : 0 : cond = boolean_true_node;
1519 : :
1520 : 75090 : add_to_predicate_list (loop, bb_n, cond);
1521 : : }
1522 : : }
1523 : :
1524 : : /* The loop header is always executed. */
1525 : 36885 : reset_bb_predicate (loop->header);
1526 : 36885 : gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1527 : : && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1528 : 36885 : }
1529 : :
1530 : : /* Build region by adding loop pre-header and post-header blocks. */
1531 : :
1532 : : static vec<basic_block>
1533 : 36885 : build_region (class loop *loop)
1534 : : {
1535 : 36885 : vec<basic_block> region = vNULL;
1536 : 36885 : basic_block exit_bb = NULL;
1537 : :
1538 : 36885 : gcc_assert (ifc_bbs);
1539 : : /* The first element is loop pre-header. */
1540 : 36885 : region.safe_push (loop_preheader_edge (loop)->src);
1541 : :
1542 : 237768 : for (unsigned int i = 0; i < loop->num_nodes; i++)
1543 : : {
1544 : 200883 : basic_block bb = ifc_bbs[i];
1545 : 200883 : region.safe_push (bb);
1546 : : /* Find loop postheader. */
1547 : 200883 : edge e;
1548 : 200883 : edge_iterator ei;
1549 : 445667 : FOR_EACH_EDGE (e, ei, bb->succs)
1550 : 281669 : if (loop_exit_edge_p (loop, e))
1551 : : {
1552 : 36885 : exit_bb = e->dest;
1553 : 36885 : break;
1554 : : }
1555 : : }
1556 : : /* The last element is loop post-header. */
1557 : 36885 : gcc_assert (exit_bb);
1558 : 36885 : region.safe_push (exit_bb);
1559 : 36885 : return region;
1560 : : }
1561 : :
1562 : : /* Return true when LOOP is if-convertible. This is a helper function
1563 : : for if_convertible_loop_p. REFS and DDRS are initialized and freed
1564 : : in if_convertible_loop_p. */
1565 : :
1566 : : static bool
1567 : 38251 : if_convertible_loop_p_1 (class loop *loop, vec<data_reference_p> *refs)
1568 : : {
1569 : 38251 : unsigned int i;
1570 : 38251 : basic_block exit_bb = NULL;
1571 : 38251 : vec<basic_block> region;
1572 : :
1573 : 38251 : calculate_dominance_info (CDI_DOMINATORS);
1574 : :
1575 : 243822 : for (i = 0; i < loop->num_nodes; i++)
1576 : : {
1577 : 206937 : basic_block bb = ifc_bbs[i];
1578 : :
1579 : 206937 : if (!if_convertible_bb_p (loop, bb, exit_bb))
1580 : : return false;
1581 : :
1582 : 205571 : if (bb_with_exit_edge_p (loop, bb))
1583 : 38186 : exit_bb = bb;
1584 : : }
1585 : :
1586 : 36885 : data_reference_p dr;
1587 : :
1588 : 36885 : innermost_DR_map
1589 : 36885 : = new hash_map<innermost_loop_behavior_hash, data_reference_p>;
1590 : 36885 : baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>;
1591 : :
1592 : : /* Compute post-dominator tree locally. */
1593 : 36885 : region = build_region (loop);
1594 : 36885 : calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region);
1595 : :
1596 : 36885 : predicate_bbs (loop);
1597 : :
1598 : : /* Free post-dominator tree since it is not used after predication. */
1599 : 36885 : free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region);
1600 : 36885 : region.release ();
1601 : :
1602 : 167403 : for (i = 0; refs->iterate (i, &dr); i++)
1603 : : {
1604 : 130518 : tree ref = DR_REF (dr);
1605 : :
1606 : 130518 : dr->aux = XNEW (struct ifc_dr);
1607 : 130518 : DR_BASE_W_UNCONDITIONALLY (dr) = false;
1608 : 130518 : DR_RW_UNCONDITIONALLY (dr) = false;
1609 : 130518 : DR_W_UNCONDITIONALLY (dr) = false;
1610 : 130518 : IFC_DR (dr)->rw_predicate = boolean_false_node;
1611 : 130518 : IFC_DR (dr)->w_predicate = boolean_false_node;
1612 : 130518 : IFC_DR (dr)->base_w_predicate = boolean_false_node;
1613 : 130518 : if (gimple_uid (DR_STMT (dr)) == 0)
1614 : 129761 : gimple_set_uid (DR_STMT (dr), i + 1);
1615 : :
1616 : : /* If DR doesn't have innermost loop behavior or it's a compound
1617 : : memory reference, we synthesize its innermost loop behavior
1618 : : for hashing. */
1619 : 130518 : if (TREE_CODE (ref) == COMPONENT_REF
1620 : : || TREE_CODE (ref) == IMAGPART_EXPR
1621 : : || TREE_CODE (ref) == REALPART_EXPR
1622 : 81742 : || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr)
1623 : 20846 : || DR_INIT (dr) || DR_STEP (dr)))
1624 : : {
1625 : 126514 : while (TREE_CODE (ref) == COMPONENT_REF
1626 : 70781 : || TREE_CODE (ref) == IMAGPART_EXPR
1627 : 196717 : || TREE_CODE (ref) == REALPART_EXPR)
1628 : 56892 : ref = TREE_OPERAND (ref, 0);
1629 : :
1630 : 69622 : memset (&DR_INNERMOST (dr), 0, sizeof (DR_INNERMOST (dr)));
1631 : 69622 : DR_BASE_ADDRESS (dr) = ref;
1632 : : }
1633 : 130518 : hash_memrefs_baserefs_and_store_DRs_read_written_info (dr);
1634 : : }
1635 : :
1636 : 183724 : for (i = 0; i < loop->num_nodes; i++)
1637 : : {
1638 : 157739 : basic_block bb = ifc_bbs[i];
1639 : 157739 : gimple_stmt_iterator itr;
1640 : :
1641 : : /* Check the if-convertibility of statements in predicated BBs. */
1642 : 157739 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1643 : 244442 : for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1644 : 124572 : if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
1645 : 12266 : return false;
1646 : : }
1647 : :
1648 : : /* Checking PHIs needs to be done after stmts, as the fact whether there
1649 : : are any masked loads or stores affects the tests. */
1650 : 159325 : for (i = 0; i < loop->num_nodes; i++)
1651 : : {
1652 : 133340 : basic_block bb = ifc_bbs[i];
1653 : 133340 : gphi_iterator itr;
1654 : :
1655 : 256259 : for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1656 : 122919 : if (!if_convertible_phi_p (loop, bb, itr.phi ()))
1657 : : return false;
1658 : : }
1659 : :
1660 : 25985 : if (dump_file)
1661 : 28 : fprintf (dump_file, "Applying if-conversion\n");
1662 : :
1663 : : return true;
1664 : : }
1665 : :
1666 : : /* Return true when LOOP is if-convertible.
1667 : : LOOP is if-convertible if:
1668 : : - it is innermost,
1669 : : - it has two or more basic blocks,
1670 : : - it has only one exit,
1671 : : - loop header is not the exit edge,
1672 : : - if its basic blocks and phi nodes are if convertible. */
1673 : :
1674 : : static bool
1675 : 38432 : if_convertible_loop_p (class loop *loop, vec<data_reference_p> *refs)
1676 : : {
1677 : 38432 : edge e;
1678 : 38432 : edge_iterator ei;
1679 : 38432 : bool res = false;
1680 : :
1681 : : /* Handle only innermost loop. */
1682 : 38432 : if (!loop || loop->inner)
1683 : : {
1684 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1685 : 0 : fprintf (dump_file, "not innermost loop\n");
1686 : 0 : return false;
1687 : : }
1688 : :
1689 : : /* If only one block, no need for if-conversion. */
1690 : 38432 : if (loop->num_nodes <= 2)
1691 : : {
1692 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1693 : 0 : fprintf (dump_file, "less than 2 basic blocks\n");
1694 : 0 : return false;
1695 : : }
1696 : :
1697 : : /* If one of the loop header's edge is an exit edge then do not
1698 : : apply if-conversion. */
1699 : 115128 : FOR_EACH_EDGE (e, ei, loop->header->succs)
1700 : 76877 : if (loop_exit_edge_p (loop, e))
1701 : : return false;
1702 : :
1703 : 38251 : res = if_convertible_loop_p_1 (loop, refs);
1704 : :
1705 : 75136 : delete innermost_DR_map;
1706 : 38251 : innermost_DR_map = NULL;
1707 : :
1708 : 75136 : delete baseref_DR_map;
1709 : 38251 : baseref_DR_map = NULL;
1710 : :
1711 : 38251 : return res;
1712 : : }
1713 : :
1714 : : /* Return reduc_1 if has_nop.
1715 : :
1716 : : if (...)
1717 : : tmp1 = (unsigned type) reduc_1;
1718 : : tmp2 = tmp1 + rhs2;
1719 : : reduc_3 = (signed type) tmp2. */
1720 : : static tree
1721 : 11922 : strip_nop_cond_scalar_reduction (bool has_nop, tree op)
1722 : : {
1723 : 11922 : if (!has_nop)
1724 : : return op;
1725 : :
1726 : 420 : if (TREE_CODE (op) != SSA_NAME)
1727 : : return NULL_TREE;
1728 : :
1729 : 374 : gassign *stmt = safe_dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op));
1730 : 374 : if (!stmt
1731 : 374 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
1732 : 220 : || !tree_nop_conversion_p (TREE_TYPE (op), TREE_TYPE
1733 : : (gimple_assign_rhs1 (stmt))))
1734 : 165 : return NULL_TREE;
1735 : :
1736 : 209 : return gimple_assign_rhs1 (stmt);
1737 : : }
1738 : :
1739 : : /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1740 : : which is in predicated basic block.
1741 : : In fact, the following PHI pattern is searching:
1742 : : loop-header:
1743 : : reduc_1 = PHI <..., reduc_2>
1744 : : ...
1745 : : if (...)
1746 : : reduc_3 = ...
1747 : : reduc_2 = PHI <reduc_1, reduc_3>
1748 : :
1749 : : ARG_0 and ARG_1 are correspondent PHI arguments.
1750 : : REDUC, OP0 and OP1 contain reduction stmt and its operands.
1751 : : EXTENDED is true if PHI has > 2 arguments. */
1752 : :
1753 : : static bool
1754 : 43373 : is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1,
1755 : : tree *op0, tree *op1, bool extended, bool* has_nop,
1756 : : gimple **nop_reduc)
1757 : : {
1758 : 43373 : tree lhs, r_op1, r_op2, r_nop1, r_nop2;
1759 : 43373 : gimple *stmt;
1760 : 43373 : gimple *header_phi = NULL;
1761 : 43373 : enum tree_code reduction_op;
1762 : 43373 : basic_block bb = gimple_bb (phi);
1763 : 43373 : class loop *loop = bb->loop_father;
1764 : 43373 : edge latch_e = loop_latch_edge (loop);
1765 : 43373 : imm_use_iterator imm_iter;
1766 : 43373 : use_operand_p use_p;
1767 : 43373 : edge e;
1768 : 43373 : edge_iterator ei;
1769 : 43373 : bool result = *has_nop = false;
1770 : 43373 : if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
1771 : : return false;
1772 : :
1773 : 27893 : if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
1774 : : {
1775 : 7377 : lhs = arg_1;
1776 : 7377 : header_phi = SSA_NAME_DEF_STMT (arg_0);
1777 : 7377 : stmt = SSA_NAME_DEF_STMT (arg_1);
1778 : : }
1779 : 20516 : else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
1780 : : {
1781 : 9470 : lhs = arg_0;
1782 : 9470 : header_phi = SSA_NAME_DEF_STMT (arg_1);
1783 : 9470 : stmt = SSA_NAME_DEF_STMT (arg_0);
1784 : : }
1785 : : else
1786 : : return false;
1787 : 16847 : if (gimple_bb (header_phi) != loop->header)
1788 : : return false;
1789 : :
1790 : 15964 : if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
1791 : : return false;
1792 : :
1793 : 10041 : if (gimple_code (stmt) != GIMPLE_ASSIGN
1794 : 10041 : || gimple_has_volatile_ops (stmt))
1795 : : return false;
1796 : :
1797 : 9921 : if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1798 : : return false;
1799 : :
1800 : 9833 : if (!is_predicated (gimple_bb (stmt)))
1801 : : return false;
1802 : :
1803 : : /* Check that stmt-block is predecessor of phi-block. */
1804 : 7706 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1805 : 7643 : if (e->dest == bb)
1806 : : {
1807 : : result = true;
1808 : : break;
1809 : : }
1810 : 7580 : if (!result)
1811 : : return false;
1812 : :
1813 : 7517 : if (!has_single_use (lhs))
1814 : : return false;
1815 : :
1816 : 7473 : reduction_op = gimple_assign_rhs_code (stmt);
1817 : :
1818 : : /* Catch something like below
1819 : :
1820 : : loop-header:
1821 : : reduc_1 = PHI <..., reduc_2>
1822 : : ...
1823 : : if (...)
1824 : : tmp1 = (unsigned type) reduc_1;
1825 : : tmp2 = tmp1 + rhs2;
1826 : : reduc_3 = (signed type) tmp2;
1827 : :
1828 : : reduc_2 = PHI <reduc_1, reduc_3>
1829 : :
1830 : : and convert to
1831 : :
1832 : : reduc_2 = PHI <0, reduc_1>
1833 : : tmp1 = (unsigned type)reduc_1;
1834 : : ifcvt = cond_expr ? rhs2 : 0
1835 : : tmp2 = tmp1 +/- ifcvt;
1836 : : reduc_1 = (signed type)tmp2; */
1837 : :
1838 : 7473 : if (CONVERT_EXPR_CODE_P (reduction_op))
1839 : : {
1840 : 397 : lhs = gimple_assign_rhs1 (stmt);
1841 : 397 : if (TREE_CODE (lhs) != SSA_NAME
1842 : 397 : || !has_single_use (lhs))
1843 : : return false;
1844 : :
1845 : 225 : *nop_reduc = stmt;
1846 : 225 : stmt = SSA_NAME_DEF_STMT (lhs);
1847 : 225 : if (gimple_bb (stmt) != gimple_bb (*nop_reduc)
1848 : 225 : || !is_gimple_assign (stmt))
1849 : : return false;
1850 : :
1851 : 222 : *has_nop = true;
1852 : 222 : reduction_op = gimple_assign_rhs_code (stmt);
1853 : : }
1854 : :
1855 : 7298 : if (reduction_op != PLUS_EXPR
1856 : : && reduction_op != MINUS_EXPR
1857 : 7298 : && reduction_op != MULT_EXPR
1858 : 7298 : && reduction_op != BIT_IOR_EXPR
1859 : : && reduction_op != BIT_XOR_EXPR
1860 : 1467 : && reduction_op != BIT_AND_EXPR)
1861 : : return false;
1862 : 5961 : r_op1 = gimple_assign_rhs1 (stmt);
1863 : 5961 : r_op2 = gimple_assign_rhs2 (stmt);
1864 : :
1865 : 5961 : r_nop1 = strip_nop_cond_scalar_reduction (*has_nop, r_op1);
1866 : 5961 : r_nop2 = strip_nop_cond_scalar_reduction (*has_nop, r_op2);
1867 : :
1868 : : /* Make R_OP1 to hold reduction variable. */
1869 : 5961 : if (r_nop2 == PHI_RESULT (header_phi)
1870 : 5961 : && commutative_tree_code (reduction_op))
1871 : : {
1872 : : std::swap (r_op1, r_op2);
1873 : : std::swap (r_nop1, r_nop2);
1874 : : }
1875 : 4949 : else if (r_nop1 != PHI_RESULT (header_phi))
1876 : : return false;
1877 : :
1878 : 5645 : if (*has_nop)
1879 : : {
1880 : : /* Check that R_NOP1 is used in nop_stmt or in PHI only. */
1881 : 415 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_nop1)
1882 : : {
1883 : 294 : gimple *use_stmt = USE_STMT (use_p);
1884 : 294 : if (is_gimple_debug (use_stmt))
1885 : 0 : continue;
1886 : 294 : if (use_stmt == SSA_NAME_DEF_STMT (r_op1))
1887 : 121 : continue;
1888 : 173 : if (use_stmt != phi)
1889 : : return false;
1890 : : }
1891 : : }
1892 : :
1893 : : /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1894 : 16961 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
1895 : : {
1896 : 11780 : gimple *use_stmt = USE_STMT (use_p);
1897 : 11780 : if (is_gimple_debug (use_stmt))
1898 : 29 : continue;
1899 : 11751 : if (use_stmt == stmt)
1900 : 5206 : continue;
1901 : 6545 : if (gimple_code (use_stmt) != GIMPLE_PHI)
1902 : : return false;
1903 : : }
1904 : :
1905 : 5181 : *op0 = r_op1; *op1 = r_op2;
1906 : 5181 : *reduc = stmt;
1907 : 5181 : return true;
1908 : : }
1909 : :
1910 : : /* Converts conditional scalar reduction into unconditional form, e.g.
1911 : : bb_4
1912 : : if (_5 != 0) goto bb_5 else goto bb_6
1913 : : end_bb_4
1914 : : bb_5
1915 : : res_6 = res_13 + 1;
1916 : : end_bb_5
1917 : : bb_6
1918 : : # res_2 = PHI <res_13(4), res_6(5)>
1919 : : end_bb_6
1920 : :
1921 : : will be converted into sequence
1922 : : _ifc__1 = _5 != 0 ? 1 : 0;
1923 : : res_2 = res_13 + _ifc__1;
1924 : : Argument SWAP tells that arguments of conditional expression should be
1925 : : swapped.
1926 : : If LOOP_VERSIONED is true if we assume that we versioned the loop for
1927 : : vectorization. In that case we can create a COND_OP.
1928 : : Returns rhs of resulting PHI assignment. */
1929 : :
1930 : : static tree
1931 : 5181 : convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi,
1932 : : tree cond, tree op0, tree op1, bool swap,
1933 : : bool has_nop, gimple* nop_reduc,
1934 : : bool loop_versioned)
1935 : : {
1936 : 5181 : gimple_stmt_iterator stmt_it;
1937 : 5181 : gimple *new_assign;
1938 : 5181 : tree rhs;
1939 : 5181 : tree rhs1 = gimple_assign_rhs1 (reduc);
1940 : 5181 : tree lhs = gimple_assign_lhs (reduc);
1941 : 5181 : tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
1942 : 5181 : tree c;
1943 : 5181 : enum tree_code reduction_op = gimple_assign_rhs_code (reduc);
1944 : 5181 : tree op_nochange = neutral_op_for_reduction (TREE_TYPE (rhs1), reduction_op,
1945 : : NULL, false);
1946 : 5181 : gimple_seq stmts = NULL;
1947 : :
1948 : 5181 : if (dump_file && (dump_flags & TDF_DETAILS))
1949 : : {
1950 : 2 : fprintf (dump_file, "Found cond scalar reduction.\n");
1951 : 2 : print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
1952 : : }
1953 : :
1954 : : /* If possible create a COND_OP instead of a COND_EXPR and an OP_EXPR.
1955 : : The COND_OP will have a neutral_op else value. */
1956 : 5181 : internal_fn ifn;
1957 : 5181 : ifn = get_conditional_internal_fn (reduction_op);
1958 : 5181 : if (loop_versioned && ifn != IFN_LAST
1959 : 5179 : && vectorized_internal_fn_supported_p (ifn, TREE_TYPE (lhs))
1960 : 6332 : && !swap)
1961 : : {
1962 : 1131 : gcall *cond_call = gimple_build_call_internal (ifn, 4,
1963 : : unshare_expr (cond),
1964 : : op0, op1, op0);
1965 : 1131 : gsi_insert_before (gsi, cond_call, GSI_SAME_STMT);
1966 : 1131 : gimple_call_set_lhs (cond_call, tmp);
1967 : : rhs = tmp;
1968 : : }
1969 : : else
1970 : : {
1971 : : /* Build cond expression using COND and constant operand
1972 : : of reduction rhs. */
1973 : 7660 : c = fold_build_cond_expr (TREE_TYPE (rhs1),
1974 : : unshare_expr (cond),
1975 : : swap ? op_nochange : op1,
1976 : : swap ? op1 : op_nochange);
1977 : : /* Create assignment stmt and insert it at GSI. */
1978 : 4050 : new_assign = gimple_build_assign (tmp, c);
1979 : 4050 : gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
1980 : : /* Build rhs for unconditional increment/decrement/logic_operation. */
1981 : 4050 : rhs = gimple_build (&stmts, reduction_op,
1982 : 4050 : TREE_TYPE (rhs1), op0, tmp);
1983 : : }
1984 : :
1985 : 5181 : if (has_nop)
1986 : : {
1987 : 121 : rhs = gimple_convert (&stmts,
1988 : 121 : TREE_TYPE (gimple_assign_lhs (nop_reduc)), rhs);
1989 : 121 : stmt_it = gsi_for_stmt (nop_reduc);
1990 : 121 : gsi_remove (&stmt_it, true);
1991 : 121 : release_defs (nop_reduc);
1992 : : }
1993 : 5181 : gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
1994 : :
1995 : : /* Delete original reduction stmt. */
1996 : 5181 : stmt_it = gsi_for_stmt (reduc);
1997 : 5181 : gsi_remove (&stmt_it, true);
1998 : 5181 : release_defs (reduc);
1999 : 5181 : return rhs;
2000 : : }
2001 : :
2002 : : /* Generate a simplified conditional. */
2003 : :
2004 : : static tree
2005 : 49166 : gen_simplified_condition (tree cond, scalar_cond_masked_set_type &cond_set)
2006 : : {
2007 : : /* Check if the value is already live in a previous branch. This resolves
2008 : : nested conditionals from diamond PHI reductions. */
2009 : 49166 : if (TREE_CODE (cond) == SSA_NAME)
2010 : : {
2011 : 49166 : gimple *stmt = SSA_NAME_DEF_STMT (cond);
2012 : 49166 : gassign *assign = NULL;
2013 : 49166 : if ((assign = as_a <gassign *> (stmt))
2014 : 49166 : && gimple_assign_rhs_code (assign) == BIT_AND_EXPR)
2015 : : {
2016 : 3385 : tree arg1 = gimple_assign_rhs1 (assign);
2017 : 3385 : tree arg2 = gimple_assign_rhs2 (assign);
2018 : 3385 : if (cond_set.contains ({ arg1, 1 }))
2019 : 115 : arg1 = boolean_true_node;
2020 : : else
2021 : 3270 : arg1 = gen_simplified_condition (arg1, cond_set);
2022 : :
2023 : 3385 : if (cond_set.contains ({ arg2, 1 }))
2024 : 1786 : arg2 = boolean_true_node;
2025 : : else
2026 : 1599 : arg2 = gen_simplified_condition (arg2, cond_set);
2027 : :
2028 : 3385 : cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, arg1, arg2);
2029 : : }
2030 : : }
2031 : 49166 : return cond;
2032 : : }
2033 : :
2034 : : /* Structure used to track meta-data on PHI arguments used to generate
2035 : : most efficient comparison sequence to slatten a PHI node. */
2036 : :
2037 : : typedef struct ifcvt_arg_entry
2038 : : {
2039 : : /* The PHI node argument value. */
2040 : : tree arg;
2041 : :
2042 : : /* The number of compares required to reach this PHI node from start of the
2043 : : BB being if-converted. */
2044 : : unsigned num_compares;
2045 : :
2046 : : /* The number of times this PHI node argument appears in the current PHI
2047 : : node. */
2048 : : unsigned occurs;
2049 : :
2050 : : /* The indices at which this PHI arg occurs inside the PHI node. */
2051 : : vec <int> *indexes;
2052 : : } ifcvt_arg_entry_t;
2053 : :
2054 : : /* Produce condition for all occurrences of ARG in PHI node. Set *INVERT
2055 : : as to whether the condition is inverted. */
2056 : :
2057 : : static tree
2058 : 4051 : gen_phi_arg_condition (gphi *phi, ifcvt_arg_entry_t &arg,
2059 : : gimple_stmt_iterator *gsi,
2060 : : scalar_cond_masked_set_type &cond_set, bool *invert)
2061 : : {
2062 : 4051 : int len;
2063 : 4051 : int i;
2064 : 4051 : tree cond = NULL_TREE;
2065 : 4051 : tree c;
2066 : 4051 : edge e;
2067 : :
2068 : 4051 : *invert = false;
2069 : 4051 : len = arg.indexes->length ();
2070 : 4051 : gcc_assert (len > 0);
2071 : 8140 : for (i = 0; i < len; i++)
2072 : : {
2073 : 4089 : e = gimple_phi_arg_edge (phi, (*arg.indexes)[i]);
2074 : 4089 : c = bb_predicate (e->src);
2075 : 4089 : if (is_true_predicate (c))
2076 : : {
2077 : 0 : cond = c;
2078 : 0 : break;
2079 : : }
2080 : : /* If we have just a single inverted predicate, signal that and
2081 : : instead invert the COND_EXPR arms. */
2082 : 4089 : if (len == 1 && TREE_CODE (c) == TRUTH_NOT_EXPR)
2083 : : {
2084 : 56 : c = TREE_OPERAND (c, 0);
2085 : 56 : *invert = true;
2086 : : }
2087 : :
2088 : 4089 : c = gen_simplified_condition (c, cond_set);
2089 : 4089 : c = force_gimple_operand_gsi (gsi, unshare_expr (c),
2090 : : true, NULL_TREE, true, GSI_SAME_STMT);
2091 : 4089 : if (cond != NULL_TREE)
2092 : : {
2093 : : /* Must build OR expression. */
2094 : 38 : cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
2095 : 38 : cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
2096 : : NULL_TREE, true, GSI_SAME_STMT);
2097 : : }
2098 : : else
2099 : : cond = c;
2100 : :
2101 : : /* Register the new possibly simplified conditional. When more than 2
2102 : : entries in a phi node we chain entries in the false branch, so the
2103 : : inverted condition is active. */
2104 : 4089 : scalar_cond_masked_key pred_cond ({ cond, 1 });
2105 : 4089 : if (!*invert)
2106 : 4033 : pred_cond.inverted_p = !pred_cond.inverted_p;
2107 : 4089 : cond_set.add (pred_cond);
2108 : : }
2109 : 4051 : gcc_assert (cond != NULL_TREE);
2110 : 4051 : return cond;
2111 : : }
2112 : :
2113 : : /* Create the smallest nested conditional possible. On pre-order we record
2114 : : which conditionals are live, and on post-order rewrite the chain by removing
2115 : : already active conditions.
2116 : :
2117 : : As an example we simplify:
2118 : :
2119 : : _7 = a_10 < 0;
2120 : : _21 = a_10 >= 0;
2121 : : _22 = a_10 < e_11(D);
2122 : : _23 = _21 & _22;
2123 : : _ifc__42 = _23 ? t_13 : 0;
2124 : : t_6 = _7 ? 1 : _ifc__42
2125 : :
2126 : : into
2127 : :
2128 : : _7 = a_10 < 0;
2129 : : _22 = a_10 < e_11(D);
2130 : : _ifc__42 = _22 ? t_13 : 0;
2131 : : t_6 = _7 ? 1 : _ifc__42;
2132 : :
2133 : : which produces better code. */
2134 : :
2135 : : static tree
2136 : 6072 : gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi,
2137 : : scalar_cond_masked_set_type &cond_set, tree type,
2138 : : gimple **res_stmt, tree lhs0,
2139 : : vec<struct ifcvt_arg_entry> &args, unsigned idx)
2140 : : {
2141 : 12144 : if (idx == args.length ())
2142 : 2021 : return args[idx - 1].arg;
2143 : :
2144 : 4051 : bool invert;
2145 : 4051 : tree cond = gen_phi_arg_condition (phi, args[idx - 1], gsi, cond_set,
2146 : : &invert);
2147 : 4051 : tree arg1 = gen_phi_nest_statement (phi, gsi, cond_set, type, res_stmt, lhs0,
2148 : : args, idx + 1);
2149 : :
2150 : 4051 : unsigned prev = idx;
2151 : 4051 : unsigned curr = prev - 1;
2152 : 4051 : tree arg0 = args[curr].arg;
2153 : 4051 : tree rhs, lhs;
2154 : 4051 : if (idx > 1)
2155 : 2030 : lhs = make_temp_ssa_name (type, NULL, "_ifc_");
2156 : : else
2157 : : lhs = lhs0;
2158 : :
2159 : 4051 : if (invert)
2160 : 56 : rhs = fold_build_cond_expr (type, unshare_expr (cond),
2161 : : arg1, arg0);
2162 : : else
2163 : 3995 : rhs = fold_build_cond_expr (type, unshare_expr (cond),
2164 : : arg0, arg1);
2165 : 4051 : gassign *new_stmt = gimple_build_assign (lhs, rhs);
2166 : 4051 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2167 : 4051 : update_stmt (new_stmt);
2168 : 4051 : *res_stmt = new_stmt;
2169 : 4051 : return lhs;
2170 : : }
2171 : :
2172 : : /* When flattening a PHI node we have a choice of which conditions to test to
2173 : : for all the paths from the start of the dominator block of the BB with the
2174 : : PHI node. If the PHI node has X arguments we have to only test X - 1
2175 : : conditions as the last one is implicit. It does matter which conditions we
2176 : : test first. We should test the shortest condition first (distance here is
2177 : : measures in the number of logical operators in the condition) and the
2178 : : longest one last. This allows us to skip testing the most expensive
2179 : : condition. To accomplish this we need to sort the conditions. P1 and P2
2180 : : are sorted first based on the number of logical operations (num_compares)
2181 : : and then by how often they occur in the PHI node. */
2182 : :
2183 : : static int
2184 : 35114 : cmp_arg_entry (const void *p1, const void *p2, void * /* data. */)
2185 : : {
2186 : 35114 : const ifcvt_arg_entry sval1 = *(const ifcvt_arg_entry *)p1;
2187 : 35114 : const ifcvt_arg_entry sval2 = *(const ifcvt_arg_entry *)p2;
2188 : :
2189 : 35114 : if (sval1.num_compares < sval2.num_compares)
2190 : : return -1;
2191 : 12269 : else if (sval1.num_compares > sval2.num_compares)
2192 : : return 1;
2193 : :
2194 : 541 : if (sval1.occurs < sval2.occurs)
2195 : : return -1;
2196 : 541 : else if (sval1.occurs > sval2.occurs)
2197 : 0 : return 1;
2198 : :
2199 : : return 0;
2200 : : }
2201 : :
2202 : : /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
2203 : : This routine can handle PHI nodes with more than two arguments.
2204 : :
2205 : : For example,
2206 : : S1: A = PHI <x1(1), x2(5)>
2207 : : is converted into,
2208 : : S2: A = cond ? x1 : x2;
2209 : :
2210 : : The generated code is inserted at GSI that points to the top of
2211 : : basic block's statement list.
2212 : : If PHI node has more than two arguments a chain of conditional
2213 : : expression is produced.
2214 : : LOOP_VERSIONED should be true if we know that the loop was versioned for
2215 : : vectorization. */
2216 : :
2217 : :
2218 : : static void
2219 : 45445 : predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi, bool loop_versioned)
2220 : : {
2221 : 45445 : gimple *new_stmt = NULL, *reduc, *nop_reduc;
2222 : 45445 : tree rhs, res, arg0, arg1, op0, op1, scev;
2223 : 45445 : tree cond;
2224 : 45445 : unsigned int index0;
2225 : 45445 : edge e;
2226 : 45445 : basic_block bb;
2227 : 45445 : unsigned int i;
2228 : 45445 : bool has_nop;
2229 : :
2230 : 45445 : res = gimple_phi_result (phi);
2231 : 90890 : if (virtual_operand_p (res))
2232 : 40259 : return;
2233 : :
2234 : 45445 : if ((rhs = degenerate_phi_result (phi))
2235 : 45445 : || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
2236 : : res))
2237 : 45404 : && !chrec_contains_undetermined (scev)
2238 : 45404 : && scev != res
2239 : 10 : && (rhs = gimple_phi_arg_def (phi, 0))))
2240 : : {
2241 : 51 : if (dump_file && (dump_flags & TDF_DETAILS))
2242 : : {
2243 : 0 : fprintf (dump_file, "Degenerate phi!\n");
2244 : 0 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
2245 : : }
2246 : 51 : new_stmt = gimple_build_assign (res, rhs);
2247 : 51 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2248 : 51 : update_stmt (new_stmt);
2249 : 51 : return;
2250 : : }
2251 : :
2252 : 45394 : bb = gimple_bb (phi);
2253 : : /* Keep track of conditionals already seen. */
2254 : 45394 : scalar_cond_masked_set_type cond_set;
2255 : 45394 : if (EDGE_COUNT (bb->preds) == 2)
2256 : : {
2257 : : /* Predicate ordinary PHI node with 2 arguments. */
2258 : 40208 : edge first_edge, second_edge;
2259 : 40208 : basic_block true_bb;
2260 : 40208 : first_edge = EDGE_PRED (bb, 0);
2261 : 40208 : second_edge = EDGE_PRED (bb, 1);
2262 : 40208 : cond = bb_predicate (first_edge->src);
2263 : 40208 : cond_set.add ({ cond, 1 });
2264 : 40208 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2265 : 21569 : std::swap (first_edge, second_edge);
2266 : 40208 : if (EDGE_COUNT (first_edge->src->succs) > 1)
2267 : : {
2268 : 17849 : cond = bb_predicate (second_edge->src);
2269 : 17849 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2270 : 10310 : cond = TREE_OPERAND (cond, 0);
2271 : : else
2272 : : first_edge = second_edge;
2273 : : }
2274 : : else
2275 : 22359 : cond = bb_predicate (first_edge->src);
2276 : :
2277 : : /* Gimplify the condition to a valid cond-expr conditonal operand. */
2278 : 40208 : cond = gen_simplified_condition (cond, cond_set);
2279 : 40208 : cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
2280 : : NULL_TREE, true, GSI_SAME_STMT);
2281 : 40208 : true_bb = first_edge->src;
2282 : 40208 : if (EDGE_PRED (bb, 1)->src == true_bb)
2283 : : {
2284 : 29108 : arg0 = gimple_phi_arg_def (phi, 1);
2285 : 29108 : arg1 = gimple_phi_arg_def (phi, 0);
2286 : : }
2287 : : else
2288 : : {
2289 : 11100 : arg0 = gimple_phi_arg_def (phi, 0);
2290 : 11100 : arg1 = gimple_phi_arg_def (phi, 1);
2291 : : }
2292 : 40208 : if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
2293 : : &op0, &op1, false, &has_nop,
2294 : : &nop_reduc))
2295 : : {
2296 : : /* Convert reduction stmt into vectorizable form. */
2297 : 8462 : rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
2298 : 4231 : true_bb != gimple_bb (reduc),
2299 : : has_nop, nop_reduc,
2300 : : loop_versioned);
2301 : 4231 : redundant_ssa_names.safe_push (std::make_pair (res, rhs));
2302 : : }
2303 : : else
2304 : : /* Build new RHS using selected condition and arguments. */
2305 : 35977 : rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
2306 : : arg0, arg1);
2307 : 40208 : new_stmt = gimple_build_assign (res, rhs);
2308 : 40208 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2309 : 40208 : gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt);
2310 : 40208 : if (fold_stmt (&new_gsi, follow_all_ssa_edges))
2311 : : {
2312 : 1555 : new_stmt = gsi_stmt (new_gsi);
2313 : 1555 : update_stmt (new_stmt);
2314 : : }
2315 : :
2316 : 40208 : if (dump_file && (dump_flags & TDF_DETAILS))
2317 : : {
2318 : 14 : fprintf (dump_file, "new phi replacement stmt\n");
2319 : 14 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
2320 : : }
2321 : 40208 : return;
2322 : : }
2323 : :
2324 : : /* Create hashmap for PHI node which contain vector of argument indexes
2325 : : having the same value. */
2326 : 5186 : bool swap = false;
2327 : 5186 : hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
2328 : 5186 : unsigned int num_args = gimple_phi_num_args (phi);
2329 : : /* Vector of different PHI argument values. */
2330 : 5186 : auto_vec<ifcvt_arg_entry_t> args;
2331 : :
2332 : : /* Compute phi_arg_map, determine the list of unique PHI args and the indices
2333 : : where they are in the PHI node. The indices will be used to determine
2334 : : the conditions to apply and their complexity. */
2335 : 20909 : for (i = 0; i < num_args; i++)
2336 : : {
2337 : 15723 : tree arg;
2338 : :
2339 : 15723 : arg = gimple_phi_arg_def (phi, i);
2340 : 15723 : if (!phi_arg_map.get (arg))
2341 : 12402 : args.safe_push ({ arg, 0, 0, NULL });
2342 : 15723 : phi_arg_map.get_or_insert (arg).safe_push (i);
2343 : : }
2344 : :
2345 : : /* Determine element with max number of occurrences and complexity. Looking
2346 : : at only number of occurrences as a measure for complexity isn't enough as
2347 : : all usages can be unique but the comparisons to reach the PHI node differ
2348 : : per branch. */
2349 : 17588 : for (unsigned i = 0; i < args.length (); i++)
2350 : : {
2351 : 12402 : unsigned int len = 0;
2352 : 12402 : vec<int> *indices = phi_arg_map.get (args[i].arg);
2353 : 52929 : for (int index : *indices)
2354 : : {
2355 : 15723 : edge e = gimple_phi_arg_edge (phi, index);
2356 : 15723 : len += get_bb_num_predicate_stmts (e->src);
2357 : : }
2358 : :
2359 : 12402 : unsigned occur = indices->length ();
2360 : 12402 : if (dump_file && (dump_flags & TDF_DETAILS))
2361 : 7 : fprintf (dump_file, "Ranking %d as len=%d, idx=%d\n", i, len, occur);
2362 : 12402 : args[i].num_compares = len;
2363 : 12402 : args[i].occurs = occur;
2364 : 12402 : args[i].indexes = indices;
2365 : : }
2366 : :
2367 : : /* Sort elements based on rankings ARGS. */
2368 : 5186 : args.stablesort (cmp_arg_entry, NULL);
2369 : :
2370 : : /* Handle one special case when number of arguments with different values
2371 : : is equal 2 and one argument has the only occurrence. Such PHI can be
2372 : : handled as if would have only 2 arguments. */
2373 : 5186 : if (args.length () == 2
2374 : 8389 : && args[0].indexes->length () == 1)
2375 : : {
2376 : 3165 : index0 = (*args[0].indexes)[0];
2377 : 3165 : arg0 = args[0].arg;
2378 : 3165 : arg1 = args[1].arg;
2379 : 3165 : e = gimple_phi_arg_edge (phi, index0);
2380 : 3165 : cond = bb_predicate (e->src);
2381 : 3165 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2382 : : {
2383 : 21 : swap = true;
2384 : 21 : cond = TREE_OPERAND (cond, 0);
2385 : : }
2386 : : /* Gimplify the condition to a valid cond-expr conditonal operand. */
2387 : 3165 : cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
2388 : : NULL_TREE, true, GSI_SAME_STMT);
2389 : 3165 : if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
2390 : : &op0, &op1, true, &has_nop, &nop_reduc)))
2391 : 4411 : rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
2392 : : swap ? arg1 : arg0,
2393 : : swap ? arg0 : arg1);
2394 : : else
2395 : : {
2396 : : /* Convert reduction stmt into vectorizable form. */
2397 : 950 : rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
2398 : : swap, has_nop, nop_reduc,
2399 : : loop_versioned);
2400 : 950 : redundant_ssa_names.safe_push (std::make_pair (res, rhs));
2401 : : }
2402 : 3165 : new_stmt = gimple_build_assign (res, rhs);
2403 : 3165 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2404 : 3165 : update_stmt (new_stmt);
2405 : : }
2406 : : else
2407 : : {
2408 : : /* Common case. */
2409 : 2021 : tree type = TREE_TYPE (gimple_phi_result (phi));
2410 : 2021 : gen_phi_nest_statement (phi, gsi, cond_set, type, &new_stmt, res,
2411 : : args, 1);
2412 : : }
2413 : :
2414 : 5186 : if (dump_file && (dump_flags & TDF_DETAILS))
2415 : : {
2416 : 3 : fprintf (dump_file, "new extended phi replacement stmt\n");
2417 : 3 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
2418 : : }
2419 : 45394 : }
2420 : :
2421 : : /* Replaces in LOOP all the scalar phi nodes other than those in the
2422 : : LOOP->header block with conditional modify expressions.
2423 : : LOOP_VERSIONED should be true if we know that the loop was versioned for
2424 : : vectorization. */
2425 : :
2426 : : static void
2427 : 25985 : predicate_all_scalar_phis (class loop *loop, bool loop_versioned)
2428 : : {
2429 : 25985 : basic_block bb;
2430 : 25985 : unsigned int orig_loop_num_nodes = loop->num_nodes;
2431 : 25985 : unsigned int i;
2432 : :
2433 : 133340 : for (i = 1; i < orig_loop_num_nodes; i++)
2434 : : {
2435 : 107355 : gphi *phi;
2436 : 107355 : gimple_stmt_iterator gsi;
2437 : 107355 : gphi_iterator phi_gsi;
2438 : 107355 : bb = ifc_bbs[i];
2439 : :
2440 : 107355 : if (bb == loop->header)
2441 : 76968 : continue;
2442 : :
2443 : 107355 : phi_gsi = gsi_start_phis (bb);
2444 : 107355 : if (gsi_end_p (phi_gsi))
2445 : 76968 : continue;
2446 : :
2447 : 30387 : gsi = gsi_after_labels (bb);
2448 : 78095 : while (!gsi_end_p (phi_gsi))
2449 : : {
2450 : 47708 : phi = phi_gsi.phi ();
2451 : 95416 : if (virtual_operand_p (gimple_phi_result (phi)))
2452 : 2263 : gsi_next (&phi_gsi);
2453 : : else
2454 : : {
2455 : 45445 : predicate_scalar_phi (phi, &gsi, loop_versioned);
2456 : 45445 : remove_phi_node (&phi_gsi, false);
2457 : : }
2458 : : }
2459 : : }
2460 : 25985 : }
2461 : :
2462 : : /* Insert in each basic block of LOOP the statements produced by the
2463 : : gimplification of the predicates. */
2464 : :
2465 : : static void
2466 : 25985 : insert_gimplified_predicates (loop_p loop)
2467 : : {
2468 : 25985 : unsigned int i;
2469 : :
2470 : 159325 : for (i = 0; i < loop->num_nodes; i++)
2471 : : {
2472 : 133340 : basic_block bb = ifc_bbs[i];
2473 : 133340 : gimple_seq stmts;
2474 : 133340 : if (!is_predicated (bb))
2475 : 81395 : gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
2476 : 133340 : if (!is_predicated (bb))
2477 : : {
2478 : : /* Do not insert statements for a basic block that is not
2479 : : predicated. Also make sure that the predicate of the
2480 : : basic block is set to true. */
2481 : 81395 : reset_bb_predicate (bb);
2482 : 81395 : continue;
2483 : : }
2484 : :
2485 : 51945 : stmts = bb_predicate_gimplified_stmts (bb);
2486 : 51945 : if (stmts)
2487 : : {
2488 : 51601 : if (need_to_predicate)
2489 : : {
2490 : : /* Insert the predicate of the BB just after the label,
2491 : : as the if-conversion of memory writes will use this
2492 : : predicate. */
2493 : 5384 : gimple_stmt_iterator gsi = gsi_after_labels (bb);
2494 : 5384 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2495 : : }
2496 : : else
2497 : : {
2498 : : /* Insert the predicate of the BB at the end of the BB
2499 : : as this would reduce the register pressure: the only
2500 : : use of this predicate will be in successor BBs. */
2501 : 46217 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2502 : :
2503 : 46217 : if (gsi_end_p (gsi)
2504 : 46217 : || stmt_ends_bb_p (gsi_stmt (gsi)))
2505 : 28023 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2506 : : else
2507 : 18194 : gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
2508 : : }
2509 : :
2510 : : /* Once the sequence is code generated, set it to NULL. */
2511 : 51601 : set_bb_predicate_gimplified_stmts (bb, NULL, true);
2512 : : }
2513 : : }
2514 : 25985 : }
2515 : :
2516 : : /* Helper function for predicate_statements. Returns index of existent
2517 : : mask if it was created for given SIZE and -1 otherwise. */
2518 : :
2519 : : static int
2520 : 904 : mask_exists (int size, const vec<int> &vec)
2521 : : {
2522 : 904 : unsigned int ix;
2523 : 904 : int v;
2524 : 993 : FOR_EACH_VEC_ELT (vec, ix, v)
2525 : 932 : if (v == size)
2526 : 843 : return (int) ix;
2527 : : return -1;
2528 : : }
2529 : :
2530 : : /* Helper function for predicate_statements. STMT is a memory read or
2531 : : write and it needs to be predicated by MASK. Return a statement
2532 : : that does so. */
2533 : :
2534 : : static gimple *
2535 : 1808 : predicate_load_or_store (gimple_stmt_iterator *gsi, gassign *stmt, tree mask)
2536 : : {
2537 : 1808 : gcall *new_stmt;
2538 : :
2539 : 1808 : tree lhs = gimple_assign_lhs (stmt);
2540 : 1808 : tree rhs = gimple_assign_rhs1 (stmt);
2541 : 1808 : tree ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
2542 : 1808 : mark_addressable (ref);
2543 : 1808 : tree addr = force_gimple_operand_gsi (gsi, build_fold_addr_expr (ref),
2544 : : true, NULL_TREE, true, GSI_SAME_STMT);
2545 : 1808 : tree ptr = build_int_cst (reference_alias_ptr_type (ref),
2546 : 1808 : get_object_alignment (ref));
2547 : : /* Copy points-to info if possible. */
2548 : 1808 : if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
2549 : 384 : copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
2550 : : ref);
2551 : 1808 : if (TREE_CODE (lhs) == SSA_NAME)
2552 : : {
2553 : : /* Get a zero else value. This might not be what a target actually uses
2554 : : but we cannot be sure about which vector mode the vectorizer will
2555 : : choose. Therefore, leave the decision whether we need to force the
2556 : : inactive elements to zero to the vectorizer. */
2557 : 1082 : tree els = vect_get_mask_load_else (MASK_LOAD_ELSE_ZERO,
2558 : 1082 : TREE_TYPE (lhs));
2559 : :
2560 : 1082 : new_stmt
2561 : 1082 : = gimple_build_call_internal (IFN_MASK_LOAD, 4, addr,
2562 : : ptr, mask, els);
2563 : :
2564 : 1082 : gimple_call_set_lhs (new_stmt, lhs);
2565 : 2164 : gimple_set_vuse (new_stmt, gimple_vuse (stmt));
2566 : : }
2567 : : else
2568 : : {
2569 : 726 : new_stmt
2570 : 726 : = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
2571 : : mask, rhs);
2572 : 726 : gimple_move_vops (new_stmt, stmt);
2573 : : }
2574 : 1808 : gimple_call_set_nothrow (new_stmt, true);
2575 : 1808 : return new_stmt;
2576 : : }
2577 : :
2578 : : /* STMT uses OP_LHS. Check whether it is equivalent to:
2579 : :
2580 : : ... = OP_MASK ? OP_LHS : X;
2581 : :
2582 : : Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is
2583 : : known to have value OP_COND. */
2584 : :
2585 : : static tree
2586 : 712 : check_redundant_cond_expr (gimple *stmt, tree op_mask, tree op_cond,
2587 : : tree op_lhs)
2588 : : {
2589 : 1397 : gassign *assign = dyn_cast <gassign *> (stmt);
2590 : 918 : if (!assign || gimple_assign_rhs_code (assign) != COND_EXPR)
2591 : : return NULL_TREE;
2592 : :
2593 : 97 : tree use_cond = gimple_assign_rhs1 (assign);
2594 : 97 : tree if_true = gimple_assign_rhs2 (assign);
2595 : 97 : tree if_false = gimple_assign_rhs3 (assign);
2596 : :
2597 : 74 : if ((use_cond == op_mask || operand_equal_p (use_cond, op_cond, 0))
2598 : 97 : && if_true == op_lhs)
2599 : : return if_false;
2600 : :
2601 : 74 : if (inverse_conditions_p (use_cond, op_cond) && if_false == op_lhs)
2602 : : return if_true;
2603 : :
2604 : : return NULL_TREE;
2605 : : }
2606 : :
2607 : : /* Return true if VALUE is available for use at STMT. SSA_NAMES is
2608 : : the set of SSA names defined earlier in STMT's block. */
2609 : :
2610 : : static bool
2611 : 23 : value_available_p (gimple *stmt, hash_set<tree_ssa_name_hash> *ssa_names,
2612 : : tree value)
2613 : : {
2614 : 23 : if (is_gimple_min_invariant (value))
2615 : : return true;
2616 : :
2617 : 23 : if (TREE_CODE (value) == SSA_NAME)
2618 : : {
2619 : 23 : if (SSA_NAME_IS_DEFAULT_DEF (value))
2620 : : return true;
2621 : :
2622 : 23 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
2623 : 23 : basic_block use_bb = gimple_bb (stmt);
2624 : 23 : return (def_bb == use_bb
2625 : 23 : ? ssa_names->contains (value)
2626 : 23 : : dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
2627 : : }
2628 : :
2629 : : return false;
2630 : : }
2631 : :
2632 : : /* Helper function for predicate_statements. STMT is a potentially-trapping
2633 : : arithmetic operation that needs to be predicated by MASK, an SSA_NAME that
2634 : : has value COND. Return a statement that does so. SSA_NAMES is the set of
2635 : : SSA names defined earlier in STMT's block. */
2636 : :
2637 : : static gimple *
2638 : 507 : predicate_rhs_code (gassign *stmt, tree mask, tree cond,
2639 : : hash_set<tree_ssa_name_hash> *ssa_names)
2640 : : {
2641 : 507 : tree lhs = gimple_assign_lhs (stmt);
2642 : 507 : tree_code code = gimple_assign_rhs_code (stmt);
2643 : 507 : unsigned int nops = gimple_num_ops (stmt);
2644 : 507 : internal_fn cond_fn = get_conditional_internal_fn (code);
2645 : :
2646 : : /* Construct the arguments to the conditional internal function. */
2647 : 507 : auto_vec<tree, 8> args;
2648 : 507 : args.safe_grow (nops + 1, true);
2649 : 507 : args[0] = mask;
2650 : 1521 : for (unsigned int i = 1; i < nops; ++i)
2651 : 1014 : args[i] = gimple_op (stmt, i);
2652 : 507 : args[nops] = NULL_TREE;
2653 : :
2654 : : /* Look for uses of the result to see whether they are COND_EXPRs that can
2655 : : be folded into the conditional call. */
2656 : 507 : imm_use_iterator imm_iter;
2657 : 507 : gimple *use_stmt;
2658 : 1219 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
2659 : : {
2660 : 712 : tree new_else = check_redundant_cond_expr (use_stmt, mask, cond, lhs);
2661 : 712 : if (new_else && value_available_p (stmt, ssa_names, new_else))
2662 : : {
2663 : 2 : if (!args[nops])
2664 : 2 : args[nops] = new_else;
2665 : 2 : if (operand_equal_p (new_else, args[nops], 0))
2666 : : {
2667 : : /* We have:
2668 : :
2669 : : LHS = IFN_COND (MASK, ..., ELSE);
2670 : : X = MASK ? LHS : ELSE;
2671 : :
2672 : : which makes X equivalent to LHS. */
2673 : 2 : tree use_lhs = gimple_assign_lhs (use_stmt);
2674 : 2 : redundant_ssa_names.safe_push (std::make_pair (use_lhs, lhs));
2675 : : }
2676 : : }
2677 : 507 : }
2678 : 507 : if (!args[nops])
2679 : 1010 : args[nops] = targetm.preferred_else_value (cond_fn, TREE_TYPE (lhs),
2680 : 505 : nops - 1, &args[1]);
2681 : :
2682 : : /* Create and insert the call. */
2683 : 507 : gcall *new_stmt = gimple_build_call_internal_vec (cond_fn, args);
2684 : 507 : gimple_call_set_lhs (new_stmt, lhs);
2685 : 507 : gimple_call_set_nothrow (new_stmt, true);
2686 : :
2687 : 507 : return new_stmt;
2688 : 507 : }
2689 : :
2690 : : /* Predicate each write to memory in LOOP.
2691 : :
2692 : : This function transforms control flow constructs containing memory
2693 : : writes of the form:
2694 : :
2695 : : | for (i = 0; i < N; i++)
2696 : : | if (cond)
2697 : : | A[i] = expr;
2698 : :
2699 : : into the following form that does not contain control flow:
2700 : :
2701 : : | for (i = 0; i < N; i++)
2702 : : | A[i] = cond ? expr : A[i];
2703 : :
2704 : : The original CFG looks like this:
2705 : :
2706 : : | bb_0
2707 : : | i = 0
2708 : : | end_bb_0
2709 : : |
2710 : : | bb_1
2711 : : | if (i < N) goto bb_5 else goto bb_2
2712 : : | end_bb_1
2713 : : |
2714 : : | bb_2
2715 : : | cond = some_computation;
2716 : : | if (cond) goto bb_3 else goto bb_4
2717 : : | end_bb_2
2718 : : |
2719 : : | bb_3
2720 : : | A[i] = expr;
2721 : : | goto bb_4
2722 : : | end_bb_3
2723 : : |
2724 : : | bb_4
2725 : : | goto bb_1
2726 : : | end_bb_4
2727 : :
2728 : : insert_gimplified_predicates inserts the computation of the COND
2729 : : expression at the beginning of the destination basic block:
2730 : :
2731 : : | bb_0
2732 : : | i = 0
2733 : : | end_bb_0
2734 : : |
2735 : : | bb_1
2736 : : | if (i < N) goto bb_5 else goto bb_2
2737 : : | end_bb_1
2738 : : |
2739 : : | bb_2
2740 : : | cond = some_computation;
2741 : : | if (cond) goto bb_3 else goto bb_4
2742 : : | end_bb_2
2743 : : |
2744 : : | bb_3
2745 : : | cond = some_computation;
2746 : : | A[i] = expr;
2747 : : | goto bb_4
2748 : : | end_bb_3
2749 : : |
2750 : : | bb_4
2751 : : | goto bb_1
2752 : : | end_bb_4
2753 : :
2754 : : predicate_statements is then predicating the memory write as follows:
2755 : :
2756 : : | bb_0
2757 : : | i = 0
2758 : : | end_bb_0
2759 : : |
2760 : : | bb_1
2761 : : | if (i < N) goto bb_5 else goto bb_2
2762 : : | end_bb_1
2763 : : |
2764 : : | bb_2
2765 : : | if (cond) goto bb_3 else goto bb_4
2766 : : | end_bb_2
2767 : : |
2768 : : | bb_3
2769 : : | cond = some_computation;
2770 : : | A[i] = cond ? expr : A[i];
2771 : : | goto bb_4
2772 : : | end_bb_3
2773 : : |
2774 : : | bb_4
2775 : : | goto bb_1
2776 : : | end_bb_4
2777 : :
2778 : : and finally combine_blocks removes the basic block boundaries making
2779 : : the loop vectorizable:
2780 : :
2781 : : | bb_0
2782 : : | i = 0
2783 : : | if (i < N) goto bb_5 else goto bb_1
2784 : : | end_bb_0
2785 : : |
2786 : : | bb_1
2787 : : | cond = some_computation;
2788 : : | A[i] = cond ? expr : A[i];
2789 : : | if (i < N) goto bb_5 else goto bb_4
2790 : : | end_bb_1
2791 : : |
2792 : : | bb_4
2793 : : | goto bb_1
2794 : : | end_bb_4
2795 : : */
2796 : :
2797 : : static void
2798 : 8864 : predicate_statements (loop_p loop)
2799 : : {
2800 : 8864 : unsigned int i, orig_loop_num_nodes = loop->num_nodes;
2801 : 8864 : auto_vec<int, 1> vect_sizes;
2802 : 8864 : auto_vec<tree, 1> vect_masks;
2803 : 8864 : hash_set<tree_ssa_name_hash> ssa_names;
2804 : :
2805 : 47692 : for (i = 1; i < orig_loop_num_nodes; i++)
2806 : : {
2807 : 38828 : gimple_stmt_iterator gsi;
2808 : 38828 : basic_block bb = ifc_bbs[i];
2809 : 38828 : tree cond = bb_predicate (bb);
2810 : 38828 : bool swap;
2811 : 38828 : int index;
2812 : :
2813 : 38828 : if (is_true_predicate (cond))
2814 : 18525 : continue;
2815 : :
2816 : 20303 : swap = false;
2817 : 20303 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2818 : : {
2819 : 7331 : swap = true;
2820 : 7331 : cond = TREE_OPERAND (cond, 0);
2821 : : }
2822 : :
2823 : 20303 : vect_sizes.truncate (0);
2824 : 20303 : vect_masks.truncate (0);
2825 : :
2826 : 136319 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2827 : : {
2828 : 95713 : gassign *stmt = dyn_cast <gassign *> (gsi_stmt (gsi));
2829 : 64241 : if (!stmt)
2830 : : ;
2831 : 64241 : else if (is_false_predicate (cond)
2832 : 64241 : && gimple_vdef (stmt))
2833 : : {
2834 : 0 : unlink_stmt_vdef (stmt);
2835 : 0 : gsi_remove (&gsi, true);
2836 : 0 : release_defs (stmt);
2837 : 0 : continue;
2838 : : }
2839 : 64241 : else if (gimple_plf (stmt, GF_PLF_2)
2840 : 64241 : && is_gimple_assign (stmt))
2841 : : {
2842 : 2315 : tree lhs = gimple_assign_lhs (stmt);
2843 : 2315 : tree mask;
2844 : 2315 : gimple *new_stmt;
2845 : 2315 : gimple_seq stmts = NULL;
2846 : 2315 : machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
2847 : : /* We checked before setting GF_PLF_2 that an equivalent
2848 : : integer mode exists. */
2849 : 2315 : int bitsize = GET_MODE_BITSIZE (mode).to_constant ();
2850 : 2315 : if (!vect_sizes.is_empty ()
2851 : 904 : && (index = mask_exists (bitsize, vect_sizes)) != -1)
2852 : : /* Use created mask. */
2853 : 843 : mask = vect_masks[index];
2854 : : else
2855 : : {
2856 : 1472 : if (COMPARISON_CLASS_P (cond))
2857 : 0 : mask = gimple_build (&stmts, TREE_CODE (cond),
2858 : : boolean_type_node,
2859 : 0 : TREE_OPERAND (cond, 0),
2860 : 0 : TREE_OPERAND (cond, 1));
2861 : : else
2862 : 1472 : mask = cond;
2863 : :
2864 : 1472 : if (swap)
2865 : : {
2866 : 438 : tree true_val
2867 : 438 : = constant_boolean_node (true, TREE_TYPE (mask));
2868 : 438 : mask = gimple_build (&stmts, BIT_XOR_EXPR,
2869 : 438 : TREE_TYPE (mask), mask, true_val);
2870 : : }
2871 : 1472 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2872 : :
2873 : : /* Save mask and its size for further use. */
2874 : 1472 : vect_sizes.safe_push (bitsize);
2875 : 1472 : vect_masks.safe_push (mask);
2876 : : }
2877 : 2315 : if (gimple_assign_single_p (stmt))
2878 : 1808 : new_stmt = predicate_load_or_store (&gsi, stmt, mask);
2879 : : else
2880 : 507 : new_stmt = predicate_rhs_code (stmt, mask, cond, &ssa_names);
2881 : :
2882 : 2315 : gsi_replace (&gsi, new_stmt, true);
2883 : : }
2884 : 61926 : else if (gimple_needing_rewrite_undefined (stmt))
2885 : 9757 : rewrite_to_defined_unconditional (&gsi);
2886 : 104338 : else if (gimple_vdef (stmt))
2887 : : {
2888 : 1533 : tree lhs = gimple_assign_lhs (stmt);
2889 : 1533 : tree rhs = gimple_assign_rhs1 (stmt);
2890 : 1533 : tree type = TREE_TYPE (lhs);
2891 : :
2892 : 1533 : lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
2893 : 1533 : rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
2894 : 1533 : if (swap)
2895 : 543 : std::swap (lhs, rhs);
2896 : 1533 : cond = force_gimple_operand_gsi (&gsi, unshare_expr (cond), true,
2897 : : NULL_TREE, true, GSI_SAME_STMT);
2898 : 1533 : rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
2899 : 1533 : gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
2900 : 1533 : update_stmt (stmt);
2901 : : }
2902 : :
2903 : 95713 : if (gimple_plf (gsi_stmt (gsi), GF_PLF_2)
2904 : 95713 : && is_gimple_call (gsi_stmt (gsi)))
2905 : : {
2906 : : /* Convert functions that have a SIMD clone to IFN_MASK_CALL.
2907 : : This will cause the vectorizer to match the "in branch"
2908 : : clone variants, and serves to build the mask vector
2909 : : in a natural way. */
2910 : 982 : tree mask = cond;
2911 : 982 : gcall *call = dyn_cast <gcall *> (gsi_stmt (gsi));
2912 : 982 : tree orig_fn = gimple_call_fn (call);
2913 : 982 : int orig_nargs = gimple_call_num_args (call);
2914 : 982 : auto_vec<tree> args;
2915 : 982 : args.safe_push (orig_fn);
2916 : 1985 : for (int i = 0; i < orig_nargs; i++)
2917 : 1003 : args.safe_push (gimple_call_arg (call, i));
2918 : : /* If `swap', we invert the mask used for the if branch for use
2919 : : when masking the function call. */
2920 : 982 : if (swap)
2921 : : {
2922 : 936 : gimple_seq stmts = NULL;
2923 : 936 : tree true_val
2924 : 936 : = constant_boolean_node (true, TREE_TYPE (mask));
2925 : 936 : mask = gimple_build (&stmts, BIT_XOR_EXPR,
2926 : 936 : TREE_TYPE (mask), mask, true_val);
2927 : 936 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2928 : : }
2929 : 982 : args.safe_push (mask);
2930 : :
2931 : : /* Replace the call with a IFN_MASK_CALL that has the extra
2932 : : condition parameter. */
2933 : 982 : gcall *new_call = gimple_build_call_internal_vec (IFN_MASK_CALL,
2934 : : args);
2935 : 982 : gimple_call_set_lhs (new_call, gimple_call_lhs (call));
2936 : 982 : gsi_replace (&gsi, new_call, true);
2937 : 982 : }
2938 : :
2939 : 95713 : tree lhs = gimple_get_lhs (gsi_stmt (gsi));
2940 : 95713 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
2941 : 62048 : ssa_names.add (lhs);
2942 : 95713 : gsi_next (&gsi);
2943 : : }
2944 : 40581 : ssa_names.empty ();
2945 : : }
2946 : 8864 : }
2947 : :
2948 : : /* Remove all GIMPLE_CONDs and GIMPLE_LABELs and GIMPLE_SWITCH of all
2949 : : the basic blocks other than the exit and latch of the LOOP. Also
2950 : : resets the GIMPLE_DEBUG information. */
2951 : :
2952 : : static void
2953 : 25985 : remove_conditions_and_labels (loop_p loop)
2954 : : {
2955 : 25985 : gimple_stmt_iterator gsi;
2956 : 25985 : unsigned int i;
2957 : :
2958 : 159325 : for (i = 0; i < loop->num_nodes; i++)
2959 : : {
2960 : 133340 : basic_block bb = ifc_bbs[i];
2961 : :
2962 : 133340 : if (bb_with_exit_edge_p (loop, bb)
2963 : 133340 : || bb == loop->latch)
2964 : 51970 : continue;
2965 : :
2966 : 576917 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2967 : 414177 : switch (gimple_code (gsi_stmt (gsi)))
2968 : : {
2969 : 33278 : case GIMPLE_COND:
2970 : 33278 : case GIMPLE_LABEL:
2971 : 33278 : case GIMPLE_SWITCH:
2972 : 33278 : gsi_remove (&gsi, true);
2973 : 33278 : break;
2974 : :
2975 : 216382 : case GIMPLE_DEBUG:
2976 : : /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2977 : 216382 : if (gimple_debug_bind_p (gsi_stmt (gsi)))
2978 : : {
2979 : 165187 : gimple_debug_bind_reset_value (gsi_stmt (gsi));
2980 : 165187 : update_stmt (gsi_stmt (gsi));
2981 : : }
2982 : 216382 : gsi_next (&gsi);
2983 : 216382 : break;
2984 : :
2985 : 164517 : default:
2986 : 164517 : gsi_next (&gsi);
2987 : : }
2988 : : }
2989 : 25985 : }
2990 : :
2991 : : /* Combine all the basic blocks from LOOP into one or two super basic
2992 : : blocks. Replace PHI nodes with conditional modify expressions.
2993 : : LOOP_VERSIONED should be true if we know that the loop was versioned for
2994 : : vectorization. */
2995 : :
2996 : : static void
2997 : 25985 : combine_blocks (class loop *loop, bool loop_versioned)
2998 : : {
2999 : 25985 : basic_block bb, exit_bb, merge_target_bb;
3000 : 25985 : unsigned int orig_loop_num_nodes = loop->num_nodes;
3001 : 25985 : unsigned int i;
3002 : 25985 : edge e;
3003 : 25985 : edge_iterator ei;
3004 : :
3005 : : /* Reset flow-sensitive info before predicating stmts or PHIs we
3006 : : might fold. */
3007 : 25985 : bool *predicated = XNEWVEC (bool, orig_loop_num_nodes);
3008 : 159325 : for (i = 0; i < orig_loop_num_nodes; i++)
3009 : : {
3010 : 133340 : bb = ifc_bbs[i];
3011 : 133340 : predicated[i] = is_predicated (bb);
3012 : 133340 : if (predicated[i])
3013 : : {
3014 : 51945 : for (auto gsi = gsi_start_phis (bb);
3015 : 53404 : !gsi_end_p (gsi); gsi_next (&gsi))
3016 : 1459 : reset_flow_sensitive_info (gimple_phi_result (*gsi));
3017 : 187187 : for (auto gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3018 : : {
3019 : 83297 : gimple *stmt = gsi_stmt (gsi);
3020 : 83297 : ssa_op_iter i;
3021 : 83297 : tree op;
3022 : 122787 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
3023 : 39490 : reset_flow_sensitive_info (op);
3024 : : }
3025 : : }
3026 : : }
3027 : :
3028 : 25985 : remove_conditions_and_labels (loop);
3029 : 25985 : insert_gimplified_predicates (loop);
3030 : 25985 : predicate_all_scalar_phis (loop, loop_versioned);
3031 : :
3032 : 25985 : if (need_to_predicate || need_to_rewrite_undefined)
3033 : 8864 : predicate_statements (loop);
3034 : :
3035 : : /* Merge basic blocks. */
3036 : 25985 : exit_bb = single_exit (loop)->src;
3037 : 25985 : gcc_assert (exit_bb != loop->latch);
3038 : 159325 : for (i = 0; i < orig_loop_num_nodes; i++)
3039 : : {
3040 : 133340 : bb = ifc_bbs[i];
3041 : 133340 : free_bb_predicate (bb);
3042 : : }
3043 : :
3044 : 25985 : merge_target_bb = loop->header;
3045 : :
3046 : : /* Get at the virtual def valid for uses starting at the first block
3047 : : we merge into the header. Without a virtual PHI the loop has the
3048 : : same virtual use on all stmts. */
3049 : 25985 : gphi *vphi = get_virtual_phi (loop->header);
3050 : 25985 : tree last_vdef = NULL_TREE;
3051 : 25985 : if (vphi)
3052 : : {
3053 : 14435 : last_vdef = gimple_phi_result (vphi);
3054 : 28870 : for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header);
3055 : 162777 : ! gsi_end_p (gsi); gsi_next (&gsi))
3056 : 230374 : if (gimple_vdef (gsi_stmt (gsi)))
3057 : 5055 : last_vdef = gimple_vdef (gsi_stmt (gsi));
3058 : : }
3059 : 133340 : for (i = 1; i < orig_loop_num_nodes; i++)
3060 : : {
3061 : 107355 : gimple_stmt_iterator gsi;
3062 : 107355 : gimple_stmt_iterator last;
3063 : :
3064 : 107355 : bb = ifc_bbs[i];
3065 : :
3066 : 107355 : if (bb == exit_bb || bb == loop->latch)
3067 : 51970 : continue;
3068 : :
3069 : : /* We release virtual PHIs late because we have to propagate them
3070 : : out using the current VUSE. The def might be the one used
3071 : : after the loop. */
3072 : 55385 : vphi = get_virtual_phi (bb);
3073 : 55385 : if (vphi)
3074 : : {
3075 : : /* When there's just loads inside the loop a stray virtual
3076 : : PHI merging the uses can appear, update last_vdef from
3077 : : it. */
3078 : 557 : if (!last_vdef)
3079 : 0 : last_vdef = gimple_phi_arg_def (vphi, 0);
3080 : 557 : imm_use_iterator iter;
3081 : 557 : use_operand_p use_p;
3082 : 557 : gimple *use_stmt;
3083 : 1839 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
3084 : : {
3085 : 3848 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3086 : 1283 : SET_USE (use_p, last_vdef);
3087 : 557 : }
3088 : 557 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
3089 : 0 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
3090 : 557 : gsi = gsi_for_stmt (vphi);
3091 : 557 : remove_phi_node (&gsi, true);
3092 : : }
3093 : :
3094 : : /* Make stmts member of loop->header and clear range info from all stmts
3095 : : in BB which is now no longer executed conditional on a predicate we
3096 : : could have derived it from. */
3097 : 306672 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3098 : : {
3099 : 195902 : gimple *stmt = gsi_stmt (gsi);
3100 : 195902 : gimple_set_bb (stmt, merge_target_bb);
3101 : : /* Update virtual operands. */
3102 : 195902 : if (last_vdef)
3103 : : {
3104 : 140845 : use_operand_p use_p = ssa_vuse_operand (stmt);
3105 : 13603 : if (use_p
3106 : 13603 : && USE_FROM_PTR (use_p) != last_vdef)
3107 : 720 : SET_USE (use_p, last_vdef);
3108 : 450970 : if (gimple_vdef (stmt))
3109 : 195902 : last_vdef = gimple_vdef (stmt);
3110 : : }
3111 : : else
3112 : : /* If this is the first load we arrive at update last_vdef
3113 : : so we handle stray PHIs correctly. */
3114 : 231727 : last_vdef = gimple_vuse (stmt);
3115 : : }
3116 : :
3117 : : /* Update stmt list. */
3118 : 55385 : last = gsi_last_bb (merge_target_bb);
3119 : 110770 : gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT);
3120 : 55385 : set_bb_seq (bb, NULL);
3121 : : }
3122 : :
3123 : : /* Fixup virtual operands in the exit block. */
3124 : 25985 : if (exit_bb
3125 : 25985 : && exit_bb != loop->header)
3126 : : {
3127 : : /* We release virtual PHIs late because we have to propagate them
3128 : : out using the current VUSE. The def might be the one used
3129 : : after the loop. */
3130 : 25985 : vphi = get_virtual_phi (exit_bb);
3131 : 25985 : if (vphi)
3132 : : {
3133 : : /* When there's just loads inside the loop a stray virtual
3134 : : PHI merging the uses can appear, update last_vdef from
3135 : : it. */
3136 : 1706 : if (!last_vdef)
3137 : 0 : last_vdef = gimple_phi_arg_def (vphi, 0);
3138 : 1706 : imm_use_iterator iter;
3139 : 1706 : use_operand_p use_p;
3140 : 1706 : gimple *use_stmt;
3141 : 5135 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
3142 : : {
3143 : 10287 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3144 : 3429 : SET_USE (use_p, last_vdef);
3145 : 1706 : }
3146 : 1706 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
3147 : 0 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
3148 : 1706 : gimple_stmt_iterator gsi = gsi_for_stmt (vphi);
3149 : 1706 : remove_phi_node (&gsi, true);
3150 : : }
3151 : : }
3152 : :
3153 : : /* Now remove all the edges in the loop, except for those from the exit
3154 : : block and delete the blocks we elided. */
3155 : 133340 : for (i = 1; i < orig_loop_num_nodes; i++)
3156 : : {
3157 : 107355 : bb = ifc_bbs[i];
3158 : :
3159 : 247591 : for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
3160 : : {
3161 : 140236 : if (e->src == exit_bb)
3162 : 25985 : ei_next (&ei);
3163 : : else
3164 : 114251 : remove_edge (e);
3165 : : }
3166 : : }
3167 : 133340 : for (i = 1; i < orig_loop_num_nodes; i++)
3168 : : {
3169 : 107355 : bb = ifc_bbs[i];
3170 : :
3171 : 107355 : if (bb == exit_bb || bb == loop->latch)
3172 : 51970 : continue;
3173 : :
3174 : 55385 : delete_basic_block (bb);
3175 : : }
3176 : :
3177 : : /* Re-connect the exit block. */
3178 : 25985 : if (exit_bb != NULL)
3179 : : {
3180 : 25985 : if (exit_bb != loop->header)
3181 : : {
3182 : : /* Connect this node to loop header. */
3183 : 25985 : make_single_succ_edge (loop->header, exit_bb, EDGE_FALLTHRU);
3184 : 25985 : set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
3185 : : }
3186 : :
3187 : : /* Redirect non-exit edges to loop->latch. */
3188 : 77955 : FOR_EACH_EDGE (e, ei, exit_bb->succs)
3189 : : {
3190 : 51970 : if (!loop_exit_edge_p (loop, e))
3191 : 25985 : redirect_edge_and_branch (e, loop->latch);
3192 : : }
3193 : 25985 : set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
3194 : : }
3195 : : else
3196 : : {
3197 : : /* If the loop does not have an exit, reconnect header and latch. */
3198 : 0 : make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
3199 : 0 : set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
3200 : : }
3201 : :
3202 : : /* If possible, merge loop header to the block with the exit edge.
3203 : : This reduces the number of basic blocks to two, to please the
3204 : : vectorizer that handles only loops with two nodes. */
3205 : 25985 : if (exit_bb
3206 : 25985 : && exit_bb != loop->header)
3207 : : {
3208 : 25985 : if (can_merge_blocks_p (loop->header, exit_bb))
3209 : 25983 : merge_blocks (loop->header, exit_bb);
3210 : : }
3211 : :
3212 : 25985 : free (ifc_bbs);
3213 : 25985 : ifc_bbs = NULL;
3214 : 25985 : free (predicated);
3215 : 25985 : }
3216 : :
3217 : : /* Version LOOP before if-converting it; the original loop
3218 : : will be if-converted, the new copy of the loop will not,
3219 : : and the LOOP_VECTORIZED internal call will be guarding which
3220 : : loop to execute. The vectorizer pass will fold this
3221 : : internal call into either true or false.
3222 : :
3223 : : Note that this function intentionally invalidates profile. Both edges
3224 : : out of LOOP_VECTORIZED must have 100% probability so the profile remains
3225 : : consistent after the condition is folded in the vectorizer. */
3226 : :
3227 : : static class loop *
3228 : 26160 : version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds)
3229 : : {
3230 : 26160 : basic_block cond_bb;
3231 : 26160 : tree cond = make_ssa_name (boolean_type_node);
3232 : 26160 : class loop *new_loop;
3233 : 26160 : gimple *g;
3234 : 26160 : gimple_stmt_iterator gsi;
3235 : 26160 : unsigned int save_length = 0;
3236 : :
3237 : 26160 : g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
3238 : 26160 : build_int_cst (integer_type_node, loop->num),
3239 : : integer_zero_node);
3240 : 26160 : gimple_call_set_lhs (g, cond);
3241 : :
3242 : 26160 : void **saved_preds = NULL;
3243 : 26160 : if (any_complicated_phi || need_to_predicate)
3244 : : {
3245 : : /* Save BB->aux around loop_version as that uses the same field. */
3246 : 3288 : save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes;
3247 : 3288 : saved_preds = XALLOCAVEC (void *, save_length);
3248 : 24726 : for (unsigned i = 0; i < save_length; i++)
3249 : 21438 : saved_preds[i] = ifc_bbs[i]->aux;
3250 : : }
3251 : :
3252 : 26160 : initialize_original_copy_tables ();
3253 : : /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED
3254 : : is re-merged in the vectorizer. */
3255 : 26160 : new_loop = loop_version (loop, cond, &cond_bb,
3256 : : profile_probability::always (),
3257 : : profile_probability::always (),
3258 : : profile_probability::always (),
3259 : : profile_probability::always (), true);
3260 : 26160 : free_original_copy_tables ();
3261 : :
3262 : 26160 : if (any_complicated_phi || need_to_predicate)
3263 : 24726 : for (unsigned i = 0; i < save_length; i++)
3264 : 21438 : ifc_bbs[i]->aux = saved_preds[i];
3265 : :
3266 : 26160 : if (new_loop == NULL)
3267 : : return NULL;
3268 : :
3269 : 26160 : new_loop->dont_vectorize = true;
3270 : 26160 : new_loop->force_vectorize = false;
3271 : 26160 : gsi = gsi_last_bb (cond_bb);
3272 : 26160 : gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
3273 : 26160 : if (preds)
3274 : 26160 : preds->safe_push (g);
3275 : 26160 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3276 : 26160 : update_ssa (TODO_update_ssa_no_phi);
3277 : 26160 : return new_loop;
3278 : : }
3279 : :
3280 : : /* Return true when LOOP satisfies the follow conditions that will
3281 : : allow it to be recognized by the vectorizer for outer-loop
3282 : : vectorization:
3283 : : - The loop is not the root node of the loop tree.
3284 : : - The loop has exactly one inner loop.
3285 : : - The loop has a single exit.
3286 : : - The loop header has a single successor, which is the inner
3287 : : loop header.
3288 : : - Each of the inner and outer loop latches have a single
3289 : : predecessor.
3290 : : - The loop exit block has a single predecessor, which is the
3291 : : inner loop's exit block. */
3292 : :
3293 : : static bool
3294 : 26160 : versionable_outer_loop_p (class loop *loop)
3295 : : {
3296 : 26160 : if (!loop_outer (loop)
3297 : 6680 : || loop->dont_vectorize
3298 : 5725 : || !loop->inner
3299 : 5725 : || loop->inner->next
3300 : 2560 : || !single_exit (loop)
3301 : 2069 : || !single_succ_p (loop->header)
3302 : 915 : || single_succ (loop->header) != loop->inner->header
3303 : 915 : || !single_pred_p (loop->latch)
3304 : 32840 : || !single_pred_p (loop->inner->latch))
3305 : 25245 : return false;
3306 : :
3307 : 915 : basic_block outer_exit = single_pred (loop->latch);
3308 : 915 : basic_block inner_exit = single_pred (loop->inner->latch);
3309 : :
3310 : 27068 : if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit)
3311 : : return false;
3312 : :
3313 : 907 : if (dump_file)
3314 : 0 : fprintf (dump_file, "Found vectorizable outer loop for versioning\n");
3315 : :
3316 : : return true;
3317 : : }
3318 : :
3319 : : /* Performs splitting of critical edges. Skip splitting and return false
3320 : : if LOOP will not be converted because:
3321 : :
3322 : : - LOOP is not well formed.
3323 : : - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
3324 : :
3325 : : Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
3326 : :
3327 : : static bool
3328 : 316420 : ifcvt_split_critical_edges (class loop *loop, bool aggressive_if_conv)
3329 : : {
3330 : 316420 : basic_block *body;
3331 : 316420 : basic_block bb;
3332 : 316420 : unsigned int num = loop->num_nodes;
3333 : 316420 : unsigned int i;
3334 : 316420 : edge e;
3335 : 316420 : edge_iterator ei;
3336 : 316420 : auto_vec<edge> critical_edges;
3337 : :
3338 : : /* Loop is not well formed. */
3339 : 316420 : if (loop->inner)
3340 : : return false;
3341 : :
3342 : 223573 : body = get_loop_body (loop);
3343 : 1837973 : for (i = 0; i < num; i++)
3344 : : {
3345 : 1395086 : bb = body[i];
3346 : 1395086 : if (!aggressive_if_conv
3347 : 1386921 : && phi_nodes (bb)
3348 : 1821623 : && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM)
3349 : : {
3350 : 4259 : if (dump_file && (dump_flags & TDF_DETAILS))
3351 : 0 : fprintf (dump_file,
3352 : : "BB %d has complicated PHI with more than %u args.\n",
3353 : : bb->index, MAX_PHI_ARG_NUM);
3354 : :
3355 : 4259 : free (body);
3356 : 4259 : return false;
3357 : : }
3358 : 1390827 : if (bb == loop->latch || bb_with_exit_edge_p (loop, bb))
3359 : 802072 : continue;
3360 : :
3361 : : /* Skip basic blocks not ending with conditional branch. */
3362 : 1396920 : if (!safe_is_a <gcond *> (*gsi_last_bb (bb))
3363 : 588755 : && !safe_is_a <gswitch *> (*gsi_last_bb (bb)))
3364 : 332658 : continue;
3365 : :
3366 : 770012 : FOR_EACH_EDGE (e, ei, bb->succs)
3367 : 629729 : if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
3368 : 115814 : critical_edges.safe_push (e);
3369 : : }
3370 : 219314 : free (body);
3371 : :
3372 : 430473 : while (critical_edges.length () > 0)
3373 : : {
3374 : 114053 : e = critical_edges.pop ();
3375 : : /* Don't split if bb can be predicated along non-critical edge. */
3376 : 114053 : if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest))
3377 : 49638 : split_edge (e);
3378 : : }
3379 : :
3380 : : return true;
3381 : 316420 : }
3382 : :
3383 : : /* Delete redundant statements produced by predication which prevents
3384 : : loop vectorization. */
3385 : :
3386 : : static void
3387 : 26208 : ifcvt_local_dce (class loop *loop)
3388 : : {
3389 : 26208 : gimple *stmt;
3390 : 26208 : gimple *stmt1;
3391 : 26208 : gimple *phi;
3392 : 26208 : gimple_stmt_iterator gsi;
3393 : 26208 : auto_vec<gimple *> worklist;
3394 : 26208 : enum gimple_code code;
3395 : 26208 : use_operand_p use_p;
3396 : 26208 : imm_use_iterator imm_iter;
3397 : :
3398 : : /* The loop has a single BB only. */
3399 : 26208 : basic_block bb = loop->header;
3400 : 26208 : tree latch_vdef = NULL_TREE;
3401 : :
3402 : 26208 : worklist.create (64);
3403 : : /* Consider all phi as live statements. */
3404 : 102020 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3405 : : {
3406 : 75812 : phi = gsi_stmt (gsi);
3407 : 75812 : gimple_set_plf (phi, GF_PLF_2, true);
3408 : 75812 : worklist.safe_push (phi);
3409 : 166216 : if (virtual_operand_p (gimple_phi_result (phi)))
3410 : 14592 : latch_vdef = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
3411 : : }
3412 : : /* Consider load/store statements, CALL and COND as live. */
3413 : 725694 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3414 : : {
3415 : 673278 : stmt = gsi_stmt (gsi);
3416 : 673278 : if (is_gimple_debug (stmt))
3417 : : {
3418 : 309276 : gimple_set_plf (stmt, GF_PLF_2, true);
3419 : 309276 : continue;
3420 : : }
3421 : 364002 : if (gimple_store_p (stmt) || gimple_assign_load_p (stmt))
3422 : : {
3423 : 72694 : gimple_set_plf (stmt, GF_PLF_2, true);
3424 : 72694 : worklist.safe_push (stmt);
3425 : 72694 : continue;
3426 : : }
3427 : 291308 : code = gimple_code (stmt);
3428 : 291308 : if (code == GIMPLE_COND || code == GIMPLE_CALL || code == GIMPLE_SWITCH)
3429 : : {
3430 : 31275 : gimple_set_plf (stmt, GF_PLF_2, true);
3431 : 31275 : worklist.safe_push (stmt);
3432 : 31275 : continue;
3433 : : }
3434 : 260033 : gimple_set_plf (stmt, GF_PLF_2, false);
3435 : :
3436 : 260033 : if (code == GIMPLE_ASSIGN)
3437 : : {
3438 : 260024 : tree lhs = gimple_assign_lhs (stmt);
3439 : 609067 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
3440 : : {
3441 : 366309 : stmt1 = USE_STMT (use_p);
3442 : 366309 : if (!is_gimple_debug (stmt1) && gimple_bb (stmt1) != bb)
3443 : : {
3444 : 17266 : gimple_set_plf (stmt, GF_PLF_2, true);
3445 : 17266 : worklist.safe_push (stmt);
3446 : 17266 : break;
3447 : : }
3448 : : }
3449 : : }
3450 : : }
3451 : : /* Propagate liveness through arguments of live stmt. */
3452 : 452487 : while (worklist.length () > 0)
3453 : : {
3454 : 426279 : ssa_op_iter iter;
3455 : 426279 : use_operand_p use_p;
3456 : 426279 : tree use;
3457 : :
3458 : 426279 : stmt = worklist.pop ();
3459 : 1507029 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3460 : : {
3461 : 654471 : use = USE_FROM_PTR (use_p);
3462 : 654471 : if (TREE_CODE (use) != SSA_NAME)
3463 : 39587 : continue;
3464 : 614884 : stmt1 = SSA_NAME_DEF_STMT (use);
3465 : 614884 : if (gimple_bb (stmt1) != bb || gimple_plf (stmt1, GF_PLF_2))
3466 : 385652 : continue;
3467 : 229232 : gimple_set_plf (stmt1, GF_PLF_2, true);
3468 : 229232 : worklist.safe_push (stmt1);
3469 : : }
3470 : : }
3471 : : /* Delete dead statements. */
3472 : 26208 : gsi = gsi_last_bb (bb);
3473 : 699486 : while (!gsi_end_p (gsi))
3474 : : {
3475 : 673278 : gimple_stmt_iterator gsiprev = gsi;
3476 : 673278 : gsi_prev (&gsiprev);
3477 : 673278 : stmt = gsi_stmt (gsi);
3478 : 673278 : if (!gimple_has_volatile_ops (stmt)
3479 : 673106 : && gimple_store_p (stmt)
3480 : 377539 : && gimple_vdef (stmt))
3481 : : {
3482 : 19875 : tree lhs = gimple_get_lhs (stmt);
3483 : 19875 : ao_ref write;
3484 : 19875 : ao_ref_init (&write, lhs);
3485 : :
3486 : 19875 : if (dse_classify_store (&write, stmt, false, NULL, NULL, latch_vdef)
3487 : : == DSE_STORE_DEAD)
3488 : 316 : delete_dead_or_redundant_assignment (&gsi, "dead");
3489 : 19875 : gsi = gsiprev;
3490 : 19875 : continue;
3491 : 19875 : }
3492 : :
3493 : 653403 : if (gimple_plf (stmt, GF_PLF_2))
3494 : : {
3495 : 639868 : gsi = gsiprev;
3496 : 639868 : continue;
3497 : : }
3498 : 13535 : if (dump_file && (dump_flags & TDF_DETAILS))
3499 : : {
3500 : 16 : fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
3501 : 16 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3502 : : }
3503 : 13535 : gsi_remove (&gsi, true);
3504 : 13535 : release_defs (stmt);
3505 : 13535 : gsi = gsiprev;
3506 : : }
3507 : 26208 : }
3508 : :
3509 : : /* Return true if VALUE is already available on edge PE. */
3510 : :
3511 : : static bool
3512 : 222462 : ifcvt_available_on_edge_p (edge pe, tree value)
3513 : : {
3514 : 222462 : if (is_gimple_min_invariant (value))
3515 : : return true;
3516 : :
3517 : 216890 : if (TREE_CODE (value) == SSA_NAME)
3518 : : {
3519 : 215766 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
3520 : 215766 : if (!def_bb || dominated_by_p (CDI_DOMINATORS, pe->dest, def_bb))
3521 : 23509 : return true;
3522 : : }
3523 : :
3524 : : return false;
3525 : : }
3526 : :
3527 : : /* Return true if STMT can be hoisted from if-converted loop LOOP to
3528 : : edge PE. */
3529 : :
3530 : : static bool
3531 : 659427 : ifcvt_can_hoist (class loop *loop, edge pe, gimple *stmt)
3532 : : {
3533 : 659427 : if (auto *call = dyn_cast<gcall *> (stmt))
3534 : : {
3535 : 5073 : if (gimple_call_internal_p (call)
3536 : 5073 : && internal_fn_mask_index (gimple_call_internal_fn (call)) >= 0)
3537 : : return false;
3538 : : }
3539 : 974106 : else if (auto *assign = dyn_cast<gassign *> (stmt))
3540 : : {
3541 : 392385 : if (gimple_assign_rhs_code (assign) == COND_EXPR)
3542 : : return false;
3543 : : }
3544 : : else
3545 : : return false;
3546 : :
3547 : 282083 : if (gimple_has_side_effects (stmt)
3548 : 280845 : || gimple_could_trap_p (stmt)
3549 : 205157 : || stmt_could_throw_p (cfun, stmt)
3550 : 205155 : || gimple_vdef (stmt)
3551 : 486598 : || gimple_vuse (stmt))
3552 : 78558 : return false;
3553 : :
3554 : 203525 : int num_args = gimple_num_args (stmt);
3555 : 203525 : if (pe != loop_preheader_edge (loop))
3556 : : {
3557 : 226402 : for (int i = 0; i < num_args; ++i)
3558 : 222462 : if (!ifcvt_available_on_edge_p (pe, gimple_arg (stmt, i)))
3559 : : return false;
3560 : : }
3561 : : else
3562 : : {
3563 : 7861 : for (int i = 0; i < num_args; ++i)
3564 : 7606 : if (!expr_invariant_in_loop_p (loop, gimple_arg (stmt, i)))
3565 : : return false;
3566 : : }
3567 : :
3568 : : return true;
3569 : : }
3570 : :
3571 : : /* Hoist invariant statements from LOOP to edge PE. */
3572 : :
3573 : : static void
3574 : 26208 : ifcvt_hoist_invariants (class loop *loop, edge pe)
3575 : : {
3576 : : /* Only hoist from the now unconditionally executed part of the loop. */
3577 : 26208 : basic_block bb = loop->header;
3578 : 26208 : gimple_stmt_iterator hoist_gsi = {};
3579 : 711843 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
3580 : : {
3581 : 659427 : gimple *stmt = gsi_stmt (gsi);
3582 : 659427 : if (ifcvt_can_hoist (loop, pe, stmt))
3583 : : {
3584 : : /* Once we've hoisted one statement, insert other statements
3585 : : after it. */
3586 : 4195 : gsi_remove (&gsi, false);
3587 : 4195 : if (hoist_gsi.ptr)
3588 : 1836 : gsi_insert_after (&hoist_gsi, stmt, GSI_NEW_STMT);
3589 : : else
3590 : : {
3591 : 2359 : gsi_insert_on_edge_immediate (pe, stmt);
3592 : 2359 : hoist_gsi = gsi_for_stmt (stmt);
3593 : : }
3594 : 4195 : continue;
3595 : : }
3596 : 655232 : gsi_next (&gsi);
3597 : : }
3598 : 26208 : }
3599 : :
3600 : : /* Returns the DECL_FIELD_BIT_OFFSET of the bitfield accesse in stmt iff its
3601 : : type mode is not BLKmode. If BITPOS is not NULL it will hold the poly_int64
3602 : : value of the DECL_FIELD_BIT_OFFSET of the bitfield access and STRUCT_EXPR,
3603 : : if not NULL, will hold the tree representing the base struct of this
3604 : : bitfield. */
3605 : :
3606 : : static tree
3607 : 1096 : get_bitfield_rep (gassign *stmt, bool write, tree *bitpos,
3608 : : tree *struct_expr)
3609 : : {
3610 : 1096 : tree comp_ref = write ? gimple_assign_lhs (stmt)
3611 : 366 : : gimple_assign_rhs1 (stmt);
3612 : :
3613 : 1096 : tree field_decl = TREE_OPERAND (comp_ref, 1);
3614 : 1096 : tree ref_offset = component_ref_field_offset (comp_ref);
3615 : 1096 : tree rep_decl = DECL_BIT_FIELD_REPRESENTATIVE (field_decl);
3616 : :
3617 : : /* Bail out if the representative is not a suitable type for a scalar
3618 : : register variable. */
3619 : 1096 : if (!is_gimple_reg_type (TREE_TYPE (rep_decl)))
3620 : : return NULL_TREE;
3621 : :
3622 : : /* Bail out if the DECL_SIZE of the field_decl isn't the same as the BF's
3623 : : precision. */
3624 : 1080 : unsigned HOST_WIDE_INT bf_prec
3625 : 1080 : = TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)));
3626 : 1080 : if (compare_tree_int (DECL_SIZE (field_decl), bf_prec) != 0)
3627 : : return NULL_TREE;
3628 : :
3629 : 1080 : if (TREE_CODE (DECL_FIELD_OFFSET (rep_decl)) != INTEGER_CST
3630 : 1080 : || TREE_CODE (ref_offset) != INTEGER_CST)
3631 : : {
3632 : 2 : if (dump_file && (dump_flags & TDF_DETAILS))
3633 : 2 : fprintf (dump_file, "\t Bitfield NOT OK to lower,"
3634 : : " offset is non-constant.\n");
3635 : 2 : return NULL_TREE;
3636 : : }
3637 : :
3638 : 1078 : if (struct_expr)
3639 : 539 : *struct_expr = TREE_OPERAND (comp_ref, 0);
3640 : :
3641 : 1078 : if (bitpos)
3642 : : {
3643 : : /* To calculate the bitposition of the BITFIELD_REF we have to determine
3644 : : where our bitfield starts in relation to the container REP_DECL. The
3645 : : DECL_FIELD_OFFSET of the original bitfield's member FIELD_DECL tells
3646 : : us how many bytes from the start of the structure there are until the
3647 : : start of the group of bitfield members the FIELD_DECL belongs to,
3648 : : whereas DECL_FIELD_BIT_OFFSET will tell us how many bits from that
3649 : : position our actual bitfield member starts. For the container
3650 : : REP_DECL adding DECL_FIELD_OFFSET and DECL_FIELD_BIT_OFFSET will tell
3651 : : us the distance between the start of the structure and the start of
3652 : : the container, though the first is in bytes and the later other in
3653 : : bits. With this in mind we calculate the bit position of our new
3654 : : BITFIELD_REF by subtracting the number of bits between the start of
3655 : : the structure and the container from the number of bits from the start
3656 : : of the structure and the actual bitfield member. */
3657 : 539 : tree bf_pos = fold_build2 (MULT_EXPR, bitsizetype,
3658 : : ref_offset,
3659 : : build_int_cst (bitsizetype, BITS_PER_UNIT));
3660 : 539 : bf_pos = fold_build2 (PLUS_EXPR, bitsizetype, bf_pos,
3661 : : DECL_FIELD_BIT_OFFSET (field_decl));
3662 : 539 : tree rep_pos = fold_build2 (MULT_EXPR, bitsizetype,
3663 : : DECL_FIELD_OFFSET (rep_decl),
3664 : : build_int_cst (bitsizetype, BITS_PER_UNIT));
3665 : 539 : rep_pos = fold_build2 (PLUS_EXPR, bitsizetype, rep_pos,
3666 : : DECL_FIELD_BIT_OFFSET (rep_decl));
3667 : :
3668 : 539 : *bitpos = fold_build2 (MINUS_EXPR, bitsizetype, bf_pos, rep_pos);
3669 : : }
3670 : :
3671 : : return rep_decl;
3672 : :
3673 : : }
3674 : :
3675 : : /* Lowers the bitfield described by DATA.
3676 : : For a write like:
3677 : :
3678 : : struct.bf = _1;
3679 : :
3680 : : lower to:
3681 : :
3682 : : __ifc_1 = struct.<representative>;
3683 : : __ifc_2 = BIT_INSERT_EXPR (__ifc_1, _1, bitpos);
3684 : : struct.<representative> = __ifc_2;
3685 : :
3686 : : For a read:
3687 : :
3688 : : _1 = struct.bf;
3689 : :
3690 : : lower to:
3691 : :
3692 : : __ifc_1 = struct.<representative>;
3693 : : _1 = BIT_FIELD_REF (__ifc_1, bitsize, bitpos);
3694 : :
3695 : : where representative is a legal load that contains the bitfield value,
3696 : : bitsize is the size of the bitfield and bitpos the offset to the start of
3697 : : the bitfield within the representative. */
3698 : :
3699 : : static void
3700 : 539 : lower_bitfield (gassign *stmt, bool write)
3701 : : {
3702 : 539 : tree struct_expr;
3703 : 539 : tree bitpos;
3704 : 539 : tree rep_decl = get_bitfield_rep (stmt, write, &bitpos, &struct_expr);
3705 : 539 : tree rep_type = TREE_TYPE (rep_decl);
3706 : 539 : tree bf_type = TREE_TYPE (gimple_assign_lhs (stmt));
3707 : :
3708 : 539 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
3709 : 539 : if (dump_file && (dump_flags & TDF_DETAILS))
3710 : : {
3711 : 9 : fprintf (dump_file, "Lowering:\n");
3712 : 9 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3713 : 9 : fprintf (dump_file, "to:\n");
3714 : : }
3715 : :
3716 : : /* REP_COMP_REF is a COMPONENT_REF for the representative. NEW_VAL is it's
3717 : : defining SSA_NAME. */
3718 : 539 : tree rep_comp_ref = build3 (COMPONENT_REF, rep_type, struct_expr, rep_decl,
3719 : : NULL_TREE);
3720 : 539 : tree new_val = ifc_temp_var (rep_type, rep_comp_ref, &gsi);
3721 : :
3722 : 539 : if (dump_file && (dump_flags & TDF_DETAILS))
3723 : 9 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (new_val), 0, TDF_SLIM);
3724 : :
3725 : 539 : if (write)
3726 : : {
3727 : 360 : new_val = ifc_temp_var (rep_type,
3728 : : build3 (BIT_INSERT_EXPR, rep_type, new_val,
3729 : : unshare_expr (gimple_assign_rhs1 (stmt)),
3730 : : bitpos), &gsi);
3731 : :
3732 : 360 : if (dump_file && (dump_flags & TDF_DETAILS))
3733 : 0 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (new_val), 0, TDF_SLIM);
3734 : :
3735 : 360 : gimple *new_stmt = gimple_build_assign (unshare_expr (rep_comp_ref),
3736 : : new_val);
3737 : 360 : gimple_move_vops (new_stmt, stmt);
3738 : 360 : gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
3739 : :
3740 : 360 : if (dump_file && (dump_flags & TDF_DETAILS))
3741 : 0 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
3742 : : }
3743 : : else
3744 : : {
3745 : 179 : tree bfr = build3 (BIT_FIELD_REF, bf_type, new_val,
3746 : 179 : build_int_cst (bitsizetype, TYPE_PRECISION (bf_type)),
3747 : : bitpos);
3748 : 179 : new_val = ifc_temp_var (bf_type, bfr, &gsi);
3749 : :
3750 : 179 : gimple *new_stmt = gimple_build_assign (gimple_assign_lhs (stmt),
3751 : : new_val);
3752 : 179 : gimple_move_vops (new_stmt, stmt);
3753 : 179 : gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
3754 : :
3755 : 179 : if (dump_file && (dump_flags & TDF_DETAILS))
3756 : 9 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
3757 : : }
3758 : :
3759 : 539 : gsi_remove (&gsi, true);
3760 : 539 : }
3761 : :
3762 : : /* Return TRUE if there are bitfields to lower in this LOOP. Fill TO_LOWER
3763 : : with data structures representing these bitfields. */
3764 : :
3765 : : static bool
3766 : 231949 : bitfields_to_lower_p (class loop *loop,
3767 : : vec <gassign *> &reads_to_lower,
3768 : : vec <gassign *> &writes_to_lower)
3769 : : {
3770 : 231949 : gimple_stmt_iterator gsi;
3771 : :
3772 : 231949 : if (dump_file && (dump_flags & TDF_DETAILS))
3773 : : {
3774 : 26 : fprintf (dump_file, "Analyzing loop %d for bitfields:\n", loop->num);
3775 : : }
3776 : :
3777 : 990597 : for (unsigned i = 0; i < loop->num_nodes; ++i)
3778 : : {
3779 : 758670 : basic_block bb = ifc_bbs[i];
3780 : 6253573 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3781 : : {
3782 : 4736255 : gassign *stmt = dyn_cast<gassign*> (gsi_stmt (gsi));
3783 : 4736255 : if (!stmt)
3784 : 4614424 : continue;
3785 : :
3786 : 1991243 : tree op = gimple_assign_lhs (stmt);
3787 : 1991243 : bool write = TREE_CODE (op) == COMPONENT_REF;
3788 : :
3789 : 1991243 : if (!write)
3790 : 1966806 : op = gimple_assign_rhs1 (stmt);
3791 : :
3792 : 1991243 : if (TREE_CODE (op) != COMPONENT_REF)
3793 : 1869412 : continue;
3794 : :
3795 : 121831 : if (DECL_BIT_FIELD_TYPE (TREE_OPERAND (op, 1)))
3796 : : {
3797 : 561 : if (dump_file && (dump_flags & TDF_DETAILS))
3798 : 11 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3799 : :
3800 : 561 : if (TREE_THIS_VOLATILE (op))
3801 : : {
3802 : 4 : if (dump_file && (dump_flags & TDF_DETAILS))
3803 : 0 : fprintf (dump_file, "\t Bitfield NO OK to lower,"
3804 : : " the access is volatile.\n");
3805 : 22 : return false;
3806 : : }
3807 : :
3808 : 557 : if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
3809 : : {
3810 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
3811 : 0 : fprintf (dump_file, "\t Bitfield NO OK to lower,"
3812 : : " field type is not Integral.\n");
3813 : 0 : return false;
3814 : : }
3815 : :
3816 : 557 : if (!get_bitfield_rep (stmt, write, NULL, NULL))
3817 : : {
3818 : 18 : if (dump_file && (dump_flags & TDF_DETAILS))
3819 : 2 : fprintf (dump_file, "\t Bitfield NOT OK to lower,"
3820 : : " representative is BLKmode.\n");
3821 : 18 : return false;
3822 : : }
3823 : :
3824 : 539 : if (dump_file && (dump_flags & TDF_DETAILS))
3825 : 9 : fprintf (dump_file, "\tBitfield OK to lower.\n");
3826 : 539 : if (write)
3827 : 360 : writes_to_lower.safe_push (stmt);
3828 : : else
3829 : 179 : reads_to_lower.safe_push (stmt);
3830 : : }
3831 : : }
3832 : : }
3833 : 463727 : return !reads_to_lower.is_empty () || !writes_to_lower.is_empty ();
3834 : : }
3835 : :
3836 : :
3837 : : /* If-convert LOOP when it is legal. For the moment this pass has no
3838 : : profitability analysis. Returns non-zero todo flags when something
3839 : : changed. */
3840 : :
3841 : : unsigned int
3842 : 495536 : tree_if_conversion (class loop *loop, vec<gimple *> *preds)
3843 : : {
3844 : 495536 : unsigned int todo = 0;
3845 : 495536 : bool aggressive_if_conv;
3846 : 495536 : class loop *rloop;
3847 : 495536 : auto_vec <gassign *, 4> reads_to_lower;
3848 : 495536 : auto_vec <gassign *, 4> writes_to_lower;
3849 : 495536 : bitmap exit_bbs;
3850 : 495536 : edge pe;
3851 : 495536 : auto_vec<data_reference_p, 10> refs;
3852 : 496443 : bool loop_versioned;
3853 : :
3854 : 496443 : again:
3855 : 496443 : rloop = NULL;
3856 : 496443 : ifc_bbs = NULL;
3857 : 496443 : need_to_lower_bitfields = false;
3858 : 496443 : need_to_ifcvt = false;
3859 : 496443 : need_to_predicate = false;
3860 : 496443 : need_to_rewrite_undefined = false;
3861 : 496443 : any_complicated_phi = false;
3862 : 496443 : loop_versioned = false;
3863 : :
3864 : : /* Apply more aggressive if-conversion when loop or its outer loop were
3865 : : marked with simd pragma. When that's the case, we try to if-convert
3866 : : loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
3867 : 496443 : aggressive_if_conv = loop->force_vectorize;
3868 : 496443 : if (!aggressive_if_conv)
3869 : : {
3870 : 488135 : class loop *outer_loop = loop_outer (loop);
3871 : 488135 : if (outer_loop && outer_loop->force_vectorize)
3872 : 8624 : aggressive_if_conv = true;
3873 : : }
3874 : :
3875 : : /* If there are more than two BBs in the loop then there is at least one if
3876 : : to convert. */
3877 : 496443 : if (loop->num_nodes > 2
3878 : 496443 : && !ifcvt_split_critical_edges (loop, aggressive_if_conv))
3879 : 97106 : goto cleanup;
3880 : :
3881 : 399337 : ifc_bbs = get_loop_body_in_if_conv_order (loop);
3882 : 399337 : if (!ifc_bbs)
3883 : : {
3884 : 2512 : if (dump_file && (dump_flags & TDF_DETAILS))
3885 : 3 : fprintf (dump_file, "Irreducible loop\n");
3886 : 2512 : goto cleanup;
3887 : : }
3888 : :
3889 : 396825 : if (find_data_references_in_loop (loop, &refs) == chrec_dont_know)
3890 : 152376 : goto cleanup;
3891 : :
3892 : 244449 : if (loop->num_nodes > 2)
3893 : : {
3894 : : /* More than one loop exit is too much to handle. */
3895 : 134854 : if (!single_exit (loop))
3896 : : {
3897 : 96422 : if (dump_file && (dump_flags & TDF_DETAILS))
3898 : 10 : fprintf (dump_file, "Can not ifcvt due to multiple exits\n");
3899 : : }
3900 : : else
3901 : : {
3902 : 38432 : need_to_ifcvt = true;
3903 : :
3904 : 38432 : if (!if_convertible_loop_p (loop, &refs)
3905 : 38432 : || !dbg_cnt (if_conversion_tree))
3906 : 12447 : goto cleanup;
3907 : :
3908 : 25985 : if ((need_to_predicate || any_complicated_phi)
3909 : 3288 : && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
3910 : 3288 : || loop->dont_vectorize))
3911 : 0 : goto cleanup;
3912 : : }
3913 : : }
3914 : :
3915 : 232002 : if ((flag_tree_loop_vectorize || loop->force_vectorize)
3916 : 231949 : && !loop->dont_vectorize)
3917 : 231949 : need_to_lower_bitfields = bitfields_to_lower_p (loop, reads_to_lower,
3918 : : writes_to_lower);
3919 : :
3920 : 232002 : if (!need_to_ifcvt && !need_to_lower_bitfields)
3921 : 205794 : goto cleanup;
3922 : :
3923 : : /* The edge to insert invariant stmts on. */
3924 : 26208 : pe = loop_preheader_edge (loop);
3925 : :
3926 : : /* Since we have no cost model, always version loops unless the user
3927 : : specified -ftree-loop-if-convert or unless versioning is required.
3928 : : Either version this loop, or if the pattern is right for outer-loop
3929 : : vectorization, version the outer loop. In the latter case we will
3930 : : still if-convert the original inner loop. */
3931 : 26208 : if (need_to_lower_bitfields
3932 : 25984 : || need_to_predicate
3933 : 24037 : || any_complicated_phi
3934 : 22697 : || flag_tree_loop_if_convert != 1)
3935 : : {
3936 : 26160 : class loop *vloop
3937 : 26160 : = (versionable_outer_loop_p (loop_outer (loop))
3938 : 26160 : ? loop_outer (loop) : loop);
3939 : 26160 : class loop *nloop = version_loop_for_if_conversion (vloop, preds);
3940 : 26160 : if (nloop == NULL)
3941 : 0 : goto cleanup;
3942 : 26160 : if (vloop != loop)
3943 : : {
3944 : : /* If versionable_outer_loop_p decided to version the
3945 : : outer loop, version also the inner loop of the non-vectorized
3946 : : loop copy. So we transform:
3947 : : loop1
3948 : : loop2
3949 : : into:
3950 : : if (LOOP_VECTORIZED (1, 3))
3951 : : {
3952 : : loop1
3953 : : loop2
3954 : : }
3955 : : else
3956 : : loop3 (copy of loop1)
3957 : : if (LOOP_VECTORIZED (4, 5))
3958 : : loop4 (copy of loop2)
3959 : : else
3960 : : loop5 (copy of loop4) */
3961 : 907 : gcc_assert (nloop->inner && nloop->inner->next == NULL);
3962 : : rloop = nloop->inner;
3963 : : }
3964 : : else
3965 : : /* If we versioned loop then make sure to insert invariant
3966 : : stmts before the .LOOP_VECTORIZED check since the vectorizer
3967 : : will re-use that for things like runtime alias versioning
3968 : : whose condition can end up using those invariants. */
3969 : 25253 : pe = single_pred_edge (gimple_bb (preds->last ()));
3970 : :
3971 : : loop_versioned = true;
3972 : : }
3973 : :
3974 : 26208 : if (need_to_lower_bitfields)
3975 : : {
3976 : 224 : if (dump_file && (dump_flags & TDF_DETAILS))
3977 : : {
3978 : 9 : fprintf (dump_file, "-------------------------\n");
3979 : 9 : fprintf (dump_file, "Start lowering bitfields\n");
3980 : : }
3981 : 403 : while (!reads_to_lower.is_empty ())
3982 : 179 : lower_bitfield (reads_to_lower.pop (), false);
3983 : 584 : while (!writes_to_lower.is_empty ())
3984 : 360 : lower_bitfield (writes_to_lower.pop (), true);
3985 : :
3986 : 224 : if (dump_file && (dump_flags & TDF_DETAILS))
3987 : : {
3988 : 9 : fprintf (dump_file, "Done lowering bitfields\n");
3989 : 9 : fprintf (dump_file, "-------------------------\n");
3990 : : }
3991 : : }
3992 : 26208 : if (need_to_ifcvt)
3993 : : {
3994 : : /* Before we rewrite edges we'll record their original position in the
3995 : : edge map such that we can map the edges between the ifcvt and the
3996 : : non-ifcvt loop during peeling. */
3997 : 25985 : uintptr_t idx = 0;
3998 : 103940 : for (edge exit : get_loop_exit_edges (loop))
3999 : 25985 : exit->aux = (void*)idx++;
4000 : :
4001 : : /* Now all statements are if-convertible. Combine all the basic
4002 : : blocks into one huge basic block doing the if-conversion
4003 : : on-the-fly. */
4004 : 25985 : combine_blocks (loop, loop_versioned);
4005 : : }
4006 : :
4007 : : std::pair <tree, tree> *name_pair;
4008 : : unsigned ssa_names_idx;
4009 : 31391 : FOR_EACH_VEC_ELT (redundant_ssa_names, ssa_names_idx, name_pair)
4010 : 5183 : replace_uses_by (name_pair->first, name_pair->second);
4011 : 26208 : redundant_ssa_names.release ();
4012 : :
4013 : : /* Perform local CSE, this esp. helps the vectorizer analysis if loads
4014 : : and stores are involved. CSE only the loop body, not the entry
4015 : : PHIs, those are to be kept in sync with the non-if-converted copy.
4016 : : ??? We'll still keep dead stores though. */
4017 : 26208 : exit_bbs = BITMAP_ALLOC (NULL);
4018 : 104959 : for (edge exit : get_loop_exit_edges (loop))
4019 : 26353 : bitmap_set_bit (exit_bbs, exit->dest->index);
4020 : 26208 : todo |= do_rpo_vn (cfun, loop_preheader_edge (loop), exit_bbs,
4021 : : false, true, true);
4022 : :
4023 : : /* Delete dead predicate computations. */
4024 : 26208 : ifcvt_local_dce (loop);
4025 : 26208 : BITMAP_FREE (exit_bbs);
4026 : :
4027 : 26208 : ifcvt_hoist_invariants (loop, pe);
4028 : :
4029 : 26208 : todo |= TODO_cleanup_cfg;
4030 : :
4031 : 496443 : cleanup:
4032 : 496443 : data_reference_p dr;
4033 : 496443 : unsigned int i;
4034 : 1664536 : for (i = 0; refs.iterate (i, &dr); i++)
4035 : : {
4036 : 1168093 : free (dr->aux);
4037 : 1168093 : free_data_ref (dr);
4038 : : }
4039 : 496443 : refs.truncate (0);
4040 : :
4041 : 496443 : if (ifc_bbs)
4042 : : {
4043 : : unsigned int i;
4044 : :
4045 : 2010614 : for (i = 0; i < loop->num_nodes; i++)
4046 : 1639774 : free_bb_predicate (ifc_bbs[i]);
4047 : :
4048 : 370840 : free (ifc_bbs);
4049 : 370840 : ifc_bbs = NULL;
4050 : : }
4051 : 496443 : if (rloop != NULL)
4052 : : {
4053 : 907 : loop = rloop;
4054 : 907 : reads_to_lower.truncate (0);
4055 : 907 : writes_to_lower.truncate (0);
4056 : 907 : goto again;
4057 : : }
4058 : :
4059 : 495536 : return todo;
4060 : 495536 : }
4061 : :
4062 : : /* Tree if-conversion pass management. */
4063 : :
4064 : : namespace {
4065 : :
4066 : : const pass_data pass_data_if_conversion =
4067 : : {
4068 : : GIMPLE_PASS, /* type */
4069 : : "ifcvt", /* name */
4070 : : OPTGROUP_NONE, /* optinfo_flags */
4071 : : TV_TREE_LOOP_IFCVT, /* tv_id */
4072 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
4073 : : 0, /* properties_provided */
4074 : : 0, /* properties_destroyed */
4075 : : 0, /* todo_flags_start */
4076 : : 0, /* todo_flags_finish */
4077 : : };
4078 : :
4079 : : class pass_if_conversion : public gimple_opt_pass
4080 : : {
4081 : : public:
4082 : 285081 : pass_if_conversion (gcc::context *ctxt)
4083 : 570162 : : gimple_opt_pass (pass_data_if_conversion, ctxt)
4084 : : {}
4085 : :
4086 : : /* opt_pass methods: */
4087 : : bool gate (function *) final override;
4088 : : unsigned int execute (function *) final override;
4089 : :
4090 : : }; // class pass_if_conversion
4091 : :
4092 : : bool
4093 : 237971 : pass_if_conversion::gate (function *fun)
4094 : : {
4095 : 33154 : return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
4096 : 206624 : && flag_tree_loop_if_convert != 0)
4097 : 269327 : || flag_tree_loop_if_convert == 1);
4098 : : }
4099 : :
4100 : : unsigned int
4101 : 206636 : pass_if_conversion::execute (function *fun)
4102 : : {
4103 : 206636 : unsigned todo = 0;
4104 : :
4105 : 413272 : if (number_of_loops (fun) <= 1)
4106 : : return 0;
4107 : :
4108 : 206636 : auto_vec<gimple *> preds;
4109 : 1122147 : for (auto loop : loops_list (cfun, 0))
4110 : 502239 : if (flag_tree_loop_if_convert == 1
4111 : 501996 : || ((flag_tree_loop_vectorize || loop->force_vectorize)
4112 : 499175 : && !loop->dont_vectorize))
4113 : 495536 : todo |= tree_if_conversion (loop, &preds);
4114 : :
4115 : 206636 : if (todo)
4116 : : {
4117 : 17304 : free_numbers_of_iterations_estimates (fun);
4118 : 17304 : scev_reset ();
4119 : : }
4120 : :
4121 : 206636 : if (flag_checking)
4122 : : {
4123 : 206632 : basic_block bb;
4124 : 7377025 : FOR_EACH_BB_FN (bb, fun)
4125 : 7170393 : gcc_assert (!bb->aux);
4126 : : }
4127 : :
4128 : : /* Perform IL update now, it might elide some loops. */
4129 : 206636 : if (todo & TODO_cleanup_cfg)
4130 : : {
4131 : 17304 : cleanup_tree_cfg ();
4132 : 17304 : if (need_ssa_update_p (fun))
4133 : 0 : todo |= TODO_update_ssa;
4134 : : }
4135 : 206636 : if (todo & TODO_update_ssa_any)
4136 : 0 : update_ssa (todo & TODO_update_ssa_any);
4137 : :
4138 : : /* If if-conversion elided the loop fall back to the original one. Likewise
4139 : : if the loops are not nested in the same outer loop. */
4140 : 232796 : for (unsigned i = 0; i < preds.length (); ++i)
4141 : : {
4142 : 26160 : gimple *g = preds[i];
4143 : 26160 : if (!gimple_bb (g))
4144 : 0 : continue;
4145 : 26160 : auto ifcvt_loop = get_loop (fun, tree_to_uhwi (gimple_call_arg (g, 0)));
4146 : 26160 : auto orig_loop = get_loop (fun, tree_to_uhwi (gimple_call_arg (g, 1)));
4147 : 26160 : if (!ifcvt_loop || !orig_loop)
4148 : : {
4149 : 2 : if (dump_file)
4150 : 0 : fprintf (dump_file, "If-converted loop vanished\n");
4151 : 2 : fold_loop_internal_call (g, boolean_false_node);
4152 : : }
4153 : 26158 : else if (loop_outer (ifcvt_loop) != loop_outer (orig_loop))
4154 : : {
4155 : 0 : if (dump_file)
4156 : 0 : fprintf (dump_file, "If-converted loop in different outer loop\n");
4157 : 0 : fold_loop_internal_call (g, boolean_false_node);
4158 : : }
4159 : : }
4160 : :
4161 : 206636 : return 0;
4162 : 206636 : }
4163 : :
4164 : : } // anon namespace
4165 : :
4166 : : gimple_opt_pass *
4167 : 285081 : make_pass_if_conversion (gcc::context *ctxt)
4168 : : {
4169 : 285081 : return new pass_if_conversion (ctxt);
4170 : : }
|
