Line data Source code
1 : /* If-conversion for vectorizer.
2 : Copyright (C) 2004-2026 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 "tree-ssa-sccvn.h"
121 : #include "tree-cfgcleanup.h"
122 : #include "tree-ssa-dse.h"
123 : #include "tree-vectorizer.h"
124 : #include "tree-eh.h"
125 : #include "cgraph.h"
126 :
127 : /* For lang_hooks.types.type_for_mode. */
128 : #include "langhooks.h"
129 :
130 : /* Only handle PHIs with no more arguments unless we are asked to by
131 : simd pragma. */
132 : #define MAX_PHI_ARG_NUM \
133 : ((unsigned) param_max_tree_if_conversion_phi_args)
134 :
135 : /* True if we've converted a statement that was only executed when some
136 : condition C was true, and if for correctness we need to predicate the
137 : statement to ensure that it is a no-op when C is false. See
138 : predicate_statements for the kinds of predication we support. */
139 : static bool need_to_predicate;
140 :
141 : /* True if we have to rewrite stmts that may invoke undefined behavior
142 : when a condition C was false so it doesn't if it is always executed.
143 : See predicate_statements for the kinds of predication we support. */
144 : static bool need_to_rewrite_undefined;
145 :
146 : /* Indicate if there are any complicated PHIs that need to be handled in
147 : if-conversion. Complicated PHI has more than two arguments and can't
148 : be degenerated to two arguments PHI. See more information in comment
149 : before phi_convertible_by_degenerating_args. */
150 : static bool any_complicated_phi;
151 :
152 : /* True if we have bitfield accesses we can lower. */
153 : static bool need_to_lower_bitfields;
154 :
155 : /* True if there is any ifcvting to be done. */
156 : static bool need_to_ifcvt;
157 :
158 : /* Hash for struct innermost_loop_behavior. It depends on the user to
159 : free the memory. */
160 :
161 : struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior>
162 : {
163 : static inline hashval_t hash (const value_type &);
164 : static inline bool equal (const value_type &,
165 : const compare_type &);
166 : };
167 :
168 : inline hashval_t
169 401554 : innermost_loop_behavior_hash::hash (const value_type &e)
170 : {
171 401554 : hashval_t hash;
172 :
173 401554 : hash = iterative_hash_expr (e->base_address, 0);
174 401554 : hash = iterative_hash_expr (e->offset, hash);
175 401554 : hash = iterative_hash_expr (e->init, hash);
176 401554 : return iterative_hash_expr (e->step, hash);
177 : }
178 :
179 : inline bool
180 288849 : innermost_loop_behavior_hash::equal (const value_type &e1,
181 : const compare_type &e2)
182 : {
183 288849 : if ((e1->base_address && !e2->base_address)
184 288849 : || (!e1->base_address && e2->base_address)
185 288849 : || (!e1->offset && e2->offset)
186 273129 : || (e1->offset && !e2->offset)
187 244768 : || (!e1->init && e2->init)
188 244768 : || (e1->init && !e2->init)
189 244768 : || (!e1->step && e2->step)
190 244768 : || (e1->step && !e2->step))
191 : return false;
192 :
193 244768 : if (e1->base_address && e2->base_address
194 489536 : && !operand_equal_p (e1->base_address, e2->base_address, 0))
195 : return false;
196 47446 : if (e1->offset && e2->offset
197 125427 : && !operand_equal_p (e1->offset, e2->offset, 0))
198 : return false;
199 47184 : if (e1->init && e2->init
200 124903 : && !operand_equal_p (e1->init, e2->init, 0))
201 : return false;
202 17679 : if (e1->step && e2->step
203 65893 : && !operand_equal_p (e1->step, e2->step, 0))
204 : return false;
205 :
206 : return true;
207 : }
208 :
209 : /* List of basic blocks in if-conversion-suitable order. */
210 : static basic_block *ifc_bbs;
211 :
212 : /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
213 : static hash_map<innermost_loop_behavior_hash,
214 : data_reference_p> *innermost_DR_map;
215 :
216 : /* Hash table to store <base reference, DR> pairs. */
217 : static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map;
218 :
219 : /* List of redundant SSA names: the first should be replaced by the second. */
220 : static vec< std::pair<tree, tree> > redundant_ssa_names;
221 :
222 : /* Structure used to predicate basic blocks. This is attached to the
223 : ->aux field of the BBs in the loop to be if-converted. */
224 : struct bb_predicate {
225 :
226 : /* The condition under which this basic block is executed. */
227 : tree predicate;
228 :
229 : /* PREDICATE is gimplified, and the sequence of statements is
230 : recorded here, in order to avoid the duplication of computations
231 : that occur in previous conditions. See PR44483. */
232 : gimple_seq predicate_gimplified_stmts;
233 :
234 : /* Records the number of statements recorded into
235 : PREDICATE_GIMPLIFIED_STMTS. */
236 : unsigned no_predicate_stmts;
237 : };
238 :
239 : /* Returns true when the basic block BB has a predicate. */
240 :
241 : static inline bool
242 1970138 : bb_has_predicate (basic_block bb)
243 : {
244 1970138 : return bb->aux != NULL;
245 : }
246 :
247 : /* Returns the gimplified predicate for basic block BB. */
248 :
249 : static inline tree
250 919307 : bb_predicate (basic_block bb)
251 : {
252 919307 : return ((struct bb_predicate *) bb->aux)->predicate;
253 : }
254 :
255 : /* Sets the gimplified predicate COND for basic block BB. */
256 :
257 : static inline void
258 494200 : set_bb_predicate (basic_block bb, tree cond)
259 : {
260 494200 : auto aux = (struct bb_predicate *) bb->aux;
261 494200 : gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
262 : && is_gimple_val (TREE_OPERAND (cond, 0)))
263 : || is_gimple_val (cond));
264 494200 : aux->predicate = cond;
265 494200 : aux->no_predicate_stmts++;
266 :
267 494200 : if (dump_file && (dump_flags & TDF_DETAILS))
268 378 : fprintf (dump_file, "Recording block %d value %d\n", bb->index,
269 : aux->no_predicate_stmts);
270 494200 : }
271 :
272 : /* Returns the sequence of statements of the gimplification of the
273 : predicate for basic block BB. */
274 :
275 : static inline gimple_seq
276 608212 : bb_predicate_gimplified_stmts (basic_block bb)
277 : {
278 608212 : return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts;
279 : }
280 :
281 : /* Sets the sequence of statements STMTS of the gimplification of the
282 : predicate for basic block BB. If PRESERVE_COUNTS then don't clear the predicate
283 : counts. */
284 :
285 : static inline void
286 293510 : set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts,
287 : bool preserve_counts)
288 : {
289 293510 : ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts;
290 293510 : if (stmts == NULL && !preserve_counts)
291 240009 : ((struct bb_predicate *) bb->aux)->no_predicate_stmts = 0;
292 : }
293 :
294 : /* Adds the sequence of statements STMTS to the sequence of statements
295 : of the predicate for basic block BB. */
296 :
297 : static inline void
298 89571 : add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
299 : {
300 : /* We might have updated some stmts in STMTS via force_gimple_operand
301 : calling fold_stmt and that producing multiple stmts. Delink immediate
302 : uses so update_ssa after loop versioning doesn't get confused for
303 : the not yet inserted predicates.
304 : ??? This should go away once we reliably avoid updating stmts
305 : not in any BB. */
306 89571 : for (gimple_stmt_iterator gsi = gsi_start (stmts);
307 220852 : !gsi_end_p (gsi); gsi_next (&gsi))
308 : {
309 131281 : gimple *stmt = gsi_stmt (gsi);
310 131281 : delink_stmt_imm_use (stmt);
311 131281 : gimple_set_modified (stmt, true);
312 131281 : ((struct bb_predicate *) bb->aux)->no_predicate_stmts++;
313 : }
314 89571 : gimple_seq_add_seq_without_update
315 89571 : (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts);
316 89571 : }
317 :
318 : /* Return the number of statements the predicate of the basic block consists
319 : of. */
320 :
321 : static inline unsigned
322 16292 : get_bb_num_predicate_stmts (basic_block bb)
323 : {
324 16292 : return ((struct bb_predicate *) bb->aux)->no_predicate_stmts;
325 : }
326 :
327 : /* Initializes to TRUE the predicate of basic block BB. */
328 :
329 : static inline void
330 206098 : init_bb_predicate (basic_block bb)
331 : {
332 206098 : bb->aux = XNEW (struct bb_predicate);
333 206098 : set_bb_predicate_gimplified_stmts (bb, NULL, false);
334 206098 : set_bb_predicate (bb, boolean_true_node);
335 206098 : }
336 :
337 : /* Release the SSA_NAMEs associated with the predicate of basic block BB. */
338 :
339 : static inline void
340 398771 : release_bb_predicate (basic_block bb)
341 : {
342 398771 : gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
343 398771 : if (stmts)
344 : {
345 : /* Ensure that these stmts haven't yet been added to a bb. */
346 33911 : if (flag_checking)
347 94234 : for (gimple_stmt_iterator i = gsi_start (stmts);
348 94234 : !gsi_end_p (i); gsi_next (&i))
349 60323 : gcc_assert (! gimple_bb (gsi_stmt (i)));
350 :
351 : /* Discard them. */
352 33911 : gimple_seq_discard (stmts);
353 33911 : set_bb_predicate_gimplified_stmts (bb, NULL, false);
354 : }
355 398771 : }
356 :
357 : /* Free the predicate of basic block BB. */
358 :
359 : static inline void
360 1777465 : free_bb_predicate (basic_block bb)
361 : {
362 1777465 : if (!bb_has_predicate (bb))
363 : return;
364 :
365 206098 : release_bb_predicate (bb);
366 206098 : free (bb->aux);
367 206098 : bb->aux = NULL;
368 : }
369 :
370 : /* Reinitialize predicate of BB with the true predicate. */
371 :
372 : static inline void
373 192673 : reset_bb_predicate (basic_block bb)
374 : {
375 192673 : if (!bb_has_predicate (bb))
376 0 : init_bb_predicate (bb);
377 : else
378 : {
379 192673 : release_bb_predicate (bb);
380 192673 : set_bb_predicate (bb, boolean_true_node);
381 : }
382 192673 : }
383 :
384 : /* Returns a new SSA_NAME of type TYPE that is assigned the value of
385 : the expression EXPR. Inserts the statement created for this
386 : computation before GSI and leaves the iterator GSI at the same
387 : statement. */
388 :
389 : static tree
390 5377 : ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
391 : {
392 5377 : tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
393 5377 : gimple *stmt = gimple_build_assign (new_name, expr);
394 10754 : gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi)));
395 5377 : gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
396 5377 : return new_name;
397 : }
398 :
399 : /* Return true when COND is a false predicate. */
400 :
401 : static inline bool
402 92118 : is_false_predicate (tree cond)
403 : {
404 92118 : return (cond != NULL_TREE
405 92118 : && (cond == boolean_false_node
406 92118 : || integer_zerop (cond)));
407 : }
408 :
409 : /* Return true when COND is a true predicate. */
410 :
411 : static inline bool
412 1043705 : is_true_predicate (tree cond)
413 : {
414 1043705 : return (cond == NULL_TREE
415 1043705 : || cond == boolean_true_node
416 1513991 : || integer_onep (cond));
417 : }
418 :
419 : /* Returns true when BB has a predicate that is not trivial: true or
420 : NULL_TREE. */
421 :
422 : static inline bool
423 511429 : is_predicated (basic_block bb)
424 : {
425 14609 : return !is_true_predicate (bb_predicate (bb));
426 : }
427 :
428 : /* Parses the predicate COND and returns its comparison code and
429 : operands OP0 and OP1. */
430 :
431 : static enum tree_code
432 399806 : parse_predicate (tree cond, tree *op0, tree *op1)
433 : {
434 399806 : gimple *s;
435 :
436 399806 : if (TREE_CODE (cond) == SSA_NAME
437 399806 : && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
438 : {
439 63617 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
440 : {
441 32290 : *op0 = gimple_assign_rhs1 (s);
442 32290 : *op1 = gimple_assign_rhs2 (s);
443 32290 : return gimple_assign_rhs_code (s);
444 : }
445 :
446 31327 : else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
447 : {
448 0 : tree op = gimple_assign_rhs1 (s);
449 0 : tree type = TREE_TYPE (op);
450 0 : enum tree_code code = parse_predicate (op, op0, op1);
451 :
452 0 : return code == ERROR_MARK ? ERROR_MARK
453 0 : : invert_tree_comparison (code, HONOR_NANS (type));
454 : }
455 :
456 : return ERROR_MARK;
457 : }
458 :
459 336189 : if (COMPARISON_CLASS_P (cond))
460 : {
461 483 : *op0 = TREE_OPERAND (cond, 0);
462 483 : *op1 = TREE_OPERAND (cond, 1);
463 483 : return TREE_CODE (cond);
464 : }
465 :
466 : return ERROR_MARK;
467 : }
468 :
469 : /* Returns the fold of predicate C1 OR C2 at location LOC. */
470 :
471 : static tree
472 199903 : fold_or_predicates (location_t loc, tree c1, tree c2)
473 : {
474 199903 : tree op1a, op1b, op2a, op2b;
475 199903 : enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
476 199903 : enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
477 :
478 199903 : if (code1 != ERROR_MARK && code2 != ERROR_MARK)
479 : {
480 2273 : tree t = maybe_fold_or_comparisons (boolean_type_node, TRUTH_OR_EXPR,
481 : code1, op1a, op1b, code2, op2a, op2b);
482 2273 : if (t)
483 : return t;
484 : }
485 :
486 197725 : return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
487 : }
488 :
489 : /* Returns either a COND_EXPR or the folded expression if the folded
490 : expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
491 : a constant or a SSA_NAME. */
492 :
493 : static tree
494 51824 : fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
495 : {
496 : /* Short cut the case where both rhs and lhs are the same. */
497 51824 : if (operand_equal_p (rhs, lhs))
498 : return rhs;
499 :
500 : /* If COND is comparison r != 0 and r has boolean type, convert COND
501 : to SSA_NAME to accept by vect bool pattern. */
502 51824 : if (TREE_CODE (cond) == NE_EXPR)
503 : {
504 0 : tree op0 = TREE_OPERAND (cond, 0);
505 0 : tree op1 = TREE_OPERAND (cond, 1);
506 0 : if (TREE_CODE (op0) == SSA_NAME
507 0 : && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
508 0 : && (integer_zerop (op1)))
509 : cond = op0;
510 : }
511 :
512 51824 : gimple_match_op cexpr (gimple_match_cond::UNCOND, COND_EXPR,
513 51824 : type, cond, rhs, lhs);
514 51824 : if (cexpr.resimplify (NULL, follow_all_ssa_edges))
515 : {
516 6743 : if (gimple_simplified_result_is_gimple_val (&cexpr))
517 567 : return cexpr.ops[0];
518 6176 : else if (cexpr.code == ABS_EXPR)
519 2 : return build1 (ABS_EXPR, type, cexpr.ops[0]);
520 6174 : else if (cexpr.code == MIN_EXPR
521 6174 : || cexpr.code == MAX_EXPR)
522 3322 : return build2 ((tree_code)cexpr.code, type, cexpr.ops[0], cexpr.ops[1]);
523 : }
524 :
525 47933 : return build3 (COND_EXPR, type, cond, rhs, lhs);
526 : }
527 :
528 : /* Add condition NC to the predicate list of basic block BB. LOOP is
529 : the loop to be if-converted. Use predicate of cd-equivalent block
530 : for join bb if it exists: we call basic blocks bb1 and bb2
531 : cd-equivalent if they are executed under the same condition. */
532 :
533 : static inline void
534 165019 : add_to_predicate_list (class loop *loop, basic_block bb, tree nc)
535 : {
536 165019 : tree bc, *tp;
537 165019 : basic_block dom_bb;
538 :
539 165019 : if (is_true_predicate (nc))
540 73676 : return;
541 :
542 : /* If dominance tells us this basic block is always executed,
543 : don't record any predicates for it. */
544 165007 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
545 : return;
546 :
547 95429 : dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
548 : /* We use notion of cd equivalence to get simpler predicate for
549 : join block, e.g. if join block has 2 predecessors with predicates
550 : p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
551 : p1 & p2 | p1 & !p2. */
552 95429 : if (dom_bb != loop->header
553 95429 : && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
554 : {
555 4086 : gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
556 4086 : bc = bb_predicate (dom_bb);
557 4086 : if (!is_true_predicate (bc))
558 4086 : set_bb_predicate (bb, bc);
559 : else
560 0 : gcc_assert (is_true_predicate (bb_predicate (bb)));
561 4086 : if (dump_file && (dump_flags & TDF_DETAILS))
562 4 : fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
563 : dom_bb->index, bb->index);
564 : return;
565 : }
566 :
567 91343 : if (!is_predicated (bb))
568 87412 : bc = nc;
569 : else
570 : {
571 3931 : bc = bb_predicate (bb);
572 3931 : bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
573 3931 : if (is_true_predicate (bc))
574 : {
575 0 : reset_bb_predicate (bb);
576 0 : return;
577 : }
578 : }
579 :
580 : /* Allow a TRUTH_NOT_EXPR around the main predicate. */
581 91343 : if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
582 32978 : tp = &TREE_OPERAND (bc, 0);
583 : else
584 : tp = &bc;
585 91343 : if (!is_gimple_val (*tp))
586 : {
587 89571 : gimple_seq stmts;
588 89571 : *tp = force_gimple_operand (*tp, &stmts, true, NULL_TREE);
589 89571 : add_bb_predicate_gimplified_stmts (bb, stmts);
590 : }
591 91343 : set_bb_predicate (bb, bc);
592 : }
593 :
594 : /* Add the condition COND to the previous condition PREV_COND, and add
595 : this to the predicate list of the destination of edge E. LOOP is
596 : the loop to be if-converted. */
597 :
598 : static void
599 107358 : add_to_dst_predicate_list (class loop *loop, edge e,
600 : tree prev_cond, tree cond)
601 : {
602 107358 : if (!flow_bb_inside_loop_p (loop, e->dest))
603 : return;
604 :
605 107358 : if (!is_true_predicate (prev_cond))
606 22580 : cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
607 : prev_cond, cond);
608 :
609 107358 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
610 86882 : add_to_predicate_list (loop, e->dest, cond);
611 : }
612 :
613 : /* Return true if one of the successor edges of BB exits LOOP. */
614 :
615 : static bool
616 3438210 : bb_with_exit_edge_p (const class loop *loop, basic_block bb)
617 : {
618 3438210 : edge e;
619 3438210 : edge_iterator ei;
620 :
621 6943394 : FOR_EACH_EDGE (e, ei, bb->succs)
622 4896566 : if (loop_exit_edge_p (loop, e))
623 : return true;
624 :
625 : return false;
626 : }
627 :
628 : /* Given PHI which has more than two arguments, this function checks if
629 : it's if-convertible by degenerating its arguments. Specifically, if
630 : below two conditions are satisfied:
631 :
632 : 1) Number of PHI arguments with different values equals to 2 and one
633 : argument has the only occurrence.
634 : 2) The edge corresponding to the unique argument isn't critical edge.
635 :
636 : Such PHI can be handled as PHIs have only two arguments. For example,
637 : below PHI:
638 :
639 : res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
640 :
641 : can be transformed into:
642 :
643 : res = (predicate of e3) ? A_2 : A_1;
644 :
645 : Return TRUE if it is the case, FALSE otherwise. */
646 :
647 : static bool
648 5539 : phi_convertible_by_degenerating_args (gphi *phi)
649 : {
650 5539 : edge e;
651 5539 : tree arg, t1 = NULL, t2 = NULL;
652 5539 : unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0;
653 5539 : unsigned int num_args = gimple_phi_num_args (phi);
654 :
655 5539 : gcc_assert (num_args > 2);
656 :
657 20116 : for (i = 0; i < num_args; i++)
658 : {
659 16803 : arg = gimple_phi_arg_def (phi, i);
660 16803 : if (t1 == NULL || operand_equal_p (t1, arg, 0))
661 : {
662 7615 : n1++;
663 7615 : i1 = i;
664 7615 : t1 = arg;
665 : }
666 9188 : else if (t2 == NULL || operand_equal_p (t2, arg, 0))
667 : {
668 6962 : n2++;
669 6962 : i2 = i;
670 6962 : t2 = arg;
671 : }
672 : else
673 : return false;
674 : }
675 :
676 3313 : if (n1 != 1 && n2 != 1)
677 : return false;
678 :
679 : /* Check if the edge corresponding to the unique arg is critical. */
680 3253 : e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2);
681 3253 : if (EDGE_COUNT (e->src->succs) > 1)
682 0 : return false;
683 :
684 : return true;
685 : }
686 :
687 : /* Return true when PHI is if-convertible. PHI is part of loop LOOP
688 : and it belongs to basic block BB. Note at this point, it is sure
689 : that PHI is if-convertible. This function updates global variable
690 : ANY_COMPLICATED_PHI if PHI is complicated. */
691 :
692 : static bool
693 130013 : if_convertible_phi_p (class loop *loop, basic_block bb, gphi *phi)
694 : {
695 130013 : if (dump_file && (dump_flags & TDF_DETAILS))
696 : {
697 103 : fprintf (dump_file, "-------------------------\n");
698 103 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
699 : }
700 :
701 130013 : if (bb != loop->header
702 52070 : && gimple_phi_num_args (phi) > 2
703 135552 : && !phi_convertible_by_degenerating_args (phi))
704 2286 : any_complicated_phi = true;
705 :
706 130013 : return true;
707 : }
708 :
709 : /* Records the status of a data reference. This struct is attached to
710 : each DR->aux field. */
711 :
712 : struct ifc_dr {
713 : bool rw_unconditionally;
714 : bool w_unconditionally;
715 : bool written_at_least_once;
716 :
717 : tree rw_predicate;
718 : tree w_predicate;
719 : tree base_w_predicate;
720 : };
721 :
722 : #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
723 : #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
724 : #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
725 : #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
726 :
727 : /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
728 : HASH tables. While storing them in HASH table, it checks if the
729 : reference is unconditionally read or written and stores that as a flag
730 : information. For base reference it checks if it is written atlest once
731 : unconditionally and stores it as flag information along with DR.
732 : In other words for every data reference A in STMT there exist other
733 : accesses to a data reference with the same base with predicates that
734 : add up (OR-up) to the true predicate: this ensures that the data
735 : reference A is touched (read or written) on every iteration of the
736 : if-converted loop. */
737 : static void
738 120228 : hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a)
739 : {
740 :
741 120228 : data_reference_p *master_dr, *base_master_dr;
742 120228 : tree base_ref = DR_BASE_OBJECT (a);
743 120228 : innermost_loop_behavior *innermost = &DR_INNERMOST (a);
744 120228 : tree ca = bb_predicate (gimple_bb (DR_STMT (a)));
745 120228 : bool exist1, exist2;
746 :
747 120228 : master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1);
748 120228 : if (!exist1)
749 92273 : *master_dr = a;
750 :
751 120228 : if (DR_IS_WRITE (a))
752 : {
753 37843 : IFC_DR (*master_dr)->w_predicate
754 75686 : = fold_or_predicates (UNKNOWN_LOCATION, ca,
755 37843 : IFC_DR (*master_dr)->w_predicate);
756 37843 : if (is_true_predicate (IFC_DR (*master_dr)->w_predicate))
757 21851 : DR_W_UNCONDITIONALLY (*master_dr) = true;
758 : }
759 120228 : IFC_DR (*master_dr)->rw_predicate
760 240456 : = fold_or_predicates (UNKNOWN_LOCATION, ca,
761 120228 : IFC_DR (*master_dr)->rw_predicate);
762 120228 : if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate))
763 84317 : DR_RW_UNCONDITIONALLY (*master_dr) = true;
764 :
765 120228 : if (DR_IS_WRITE (a))
766 : {
767 37843 : base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2);
768 37843 : if (!exist2)
769 27693 : *base_master_dr = a;
770 37843 : IFC_DR (*base_master_dr)->base_w_predicate
771 75686 : = fold_or_predicates (UNKNOWN_LOCATION, ca,
772 37843 : IFC_DR (*base_master_dr)->base_w_predicate);
773 37843 : if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate))
774 22114 : DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true;
775 : }
776 120228 : }
777 :
778 : /* Return TRUE if can prove the index IDX of an array reference REF is
779 : within array bound. Return false otherwise. */
780 :
781 : static bool
782 269593 : idx_within_array_bound (tree ref, tree *idx, void *dta)
783 : {
784 269593 : wi::overflow_type overflow;
785 269593 : widest_int niter, valid_niter, delta, wi_step;
786 269593 : tree ev, init, step;
787 269593 : tree low, high;
788 269593 : class loop *loop = (class loop*) dta;
789 :
790 : /* Only support within-bound access for array references. */
791 269593 : if (TREE_CODE (ref) != ARRAY_REF)
792 : return false;
793 :
794 : /* For arrays that might have flexible sizes, it is not guaranteed that they
795 : do not extend over their declared size. */
796 150013 : if (array_ref_flexible_size_p (ref))
797 : return false;
798 :
799 96823 : ev = analyze_scalar_evolution (loop, *idx);
800 96823 : ev = instantiate_parameters (loop, ev);
801 96823 : init = initial_condition (ev);
802 96823 : step = evolution_part_in_loop_num (ev, loop->num);
803 :
804 96823 : if (!init || TREE_CODE (init) != INTEGER_CST
805 84453 : || (step && TREE_CODE (step) != INTEGER_CST))
806 : return false;
807 :
808 84447 : low = array_ref_low_bound (ref);
809 84447 : high = array_ref_up_bound (ref);
810 :
811 : /* The case of nonconstant bounds could be handled, but it would be
812 : complicated. */
813 84447 : if (TREE_CODE (low) != INTEGER_CST
814 84447 : || !high || TREE_CODE (high) != INTEGER_CST)
815 : return false;
816 :
817 : /* Check if the initial idx is within bound. */
818 84379 : if (wi::to_widest (init) < wi::to_widest (low)
819 168750 : || wi::to_widest (init) > wi::to_widest (high))
820 : return false;
821 :
822 : /* The idx is always within bound. */
823 84363 : if (!step || integer_zerop (step))
824 : return true;
825 :
826 82285 : if (!max_loop_iterations (loop, &niter))
827 : return false;
828 :
829 82285 : if (wi::to_widest (step) < 0)
830 : {
831 303 : delta = wi::to_widest (init) - wi::to_widest (low);
832 303 : wi_step = -wi::to_widest (step);
833 : }
834 : else
835 : {
836 81982 : delta = wi::to_widest (high) - wi::to_widest (init);
837 81982 : wi_step = wi::to_widest (step);
838 : }
839 :
840 82285 : valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow);
841 : /* The iteration space of idx is within array bound. */
842 164570 : if (!overflow && niter <= valid_niter)
843 81804 : return true;
844 :
845 : return false;
846 269593 : }
847 :
848 : /* Return TRUE if ref is a within bound array reference. */
849 :
850 : bool
851 262577 : ref_within_array_bound (gimple *stmt, tree ref)
852 : {
853 262577 : class loop *loop = loop_containing_stmt (stmt);
854 :
855 262577 : gcc_assert (loop != NULL);
856 262577 : return for_each_index (&ref, idx_within_array_bound, loop);
857 : }
858 :
859 :
860 : /* Given a memory reference expression T, return TRUE if base object
861 : it refers to is writable. The base object of a memory reference
862 : is the main object being referenced, which is returned by function
863 : get_base_address. */
864 :
865 : static bool
866 2353 : base_object_writable (tree ref)
867 : {
868 2353 : tree base_tree = get_base_address (ref);
869 :
870 2353 : return (base_tree
871 2353 : && DECL_P (base_tree)
872 1459 : && decl_binds_to_current_def_p (base_tree)
873 3808 : && !TREE_READONLY (base_tree));
874 : }
875 :
876 : /* Return true when the memory references of STMT won't trap in the
877 : if-converted code. There are two things that we have to check for:
878 :
879 : - writes to memory occur to writable memory: if-conversion of
880 : memory writes transforms the conditional memory writes into
881 : unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
882 : into "A[i] = cond ? foo : A[i]", and as the write to memory may not
883 : be executed at all in the original code, it may be a readonly
884 : memory. To check that A is not const-qualified, we check that
885 : there exists at least an unconditional write to A in the current
886 : function.
887 :
888 : - reads or writes to memory are valid memory accesses for every
889 : iteration. To check that the memory accesses are correctly formed
890 : and that we are allowed to read and write in these locations, we
891 : check that the memory accesses to be if-converted occur at every
892 : iteration unconditionally.
893 :
894 : Returns true for the memory reference in STMT, same memory reference
895 : is read or written unconditionally at least once and the base memory
896 : reference is written unconditionally once. This is to check reference
897 : will not write fault. Also returns true if the memory reference is
898 : unconditionally read once then we are conditionally writing to memory
899 : which is defined as read and write and is bound to the definition
900 : we are seeing. */
901 : static bool
902 20079 : ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs)
903 : {
904 : /* If DR didn't see a reference here we can't use it to tell
905 : whether the ref traps or not. */
906 20079 : if (gimple_uid (stmt) == 0)
907 : return false;
908 :
909 20078 : data_reference_p *master_dr, *base_master_dr;
910 20078 : data_reference_p a = drs[gimple_uid (stmt) - 1];
911 :
912 20078 : tree base = DR_BASE_OBJECT (a);
913 20078 : innermost_loop_behavior *innermost = &DR_INNERMOST (a);
914 :
915 20078 : gcc_assert (DR_STMT (a) == stmt);
916 20078 : gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a)
917 : || DR_INIT (a) || DR_STEP (a));
918 :
919 20078 : master_dr = innermost_DR_map->get (innermost);
920 20078 : gcc_assert (master_dr != NULL);
921 :
922 20078 : base_master_dr = baseref_DR_map->get (base);
923 :
924 : /* If a is unconditionally written to it doesn't trap. */
925 20078 : if (DR_W_UNCONDITIONALLY (*master_dr))
926 : return true;
927 :
928 : /* If a is unconditionally accessed then ...
929 :
930 : Even a is conditional access, we can treat it as an unconditional
931 : one if it's an array reference and all its index are within array
932 : bound. */
933 18215 : if (DR_RW_UNCONDITIONALLY (*master_dr)
934 18215 : || ref_within_array_bound (stmt, DR_REF (a)))
935 : {
936 : /* an unconditional read won't trap. */
937 6586 : if (DR_IS_READ (a))
938 : return true;
939 :
940 : /* an unconditionally write won't trap if the base is written
941 : to unconditionally. */
942 2390 : if ((base_master_dr
943 2390 : && DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
944 : /* or the base is known to be not readonly. */
945 4743 : || base_object_writable (DR_REF (a)))
946 1492 : return !ref_can_have_store_data_races (base);
947 : }
948 :
949 : return false;
950 : }
951 :
952 : /* Return true if STMT could be converted into a masked load or store
953 : (conditional load or store based on a mask computed from bb predicate). */
954 :
955 : static bool
956 11939 : ifcvt_can_use_mask_load_store (gimple *stmt)
957 : {
958 : /* Check whether this is a load or store. */
959 11939 : tree lhs = gimple_assign_lhs (stmt);
960 11939 : bool is_load;
961 11939 : tree ref;
962 11939 : if (gimple_store_p (stmt))
963 : {
964 2780 : if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
965 : return false;
966 : is_load = false;
967 : ref = lhs;
968 : }
969 9159 : else if (gimple_assign_load_p (stmt))
970 : {
971 9158 : is_load = true;
972 9158 : ref = gimple_assign_rhs1 (stmt);
973 : }
974 : else
975 : return false;
976 :
977 11938 : if (may_be_nonaddressable_p (ref))
978 : return false;
979 :
980 : /* Mask should be integer mode of the same size as the load/store
981 : mode. */
982 11879 : machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
983 11879 : if (!int_mode_for_mode (mode).exists () || VECTOR_MODE_P (mode))
984 : return false;
985 :
986 11848 : if (can_vec_mask_load_store_p (mode, VOIDmode, is_load))
987 : return true;
988 :
989 : return false;
990 : }
991 :
992 : /* Return true if STMT could be converted from an operation that is
993 : unconditional to one that is conditional on a bb predicate mask. */
994 :
995 : static bool
996 13935 : ifcvt_can_predicate (gimple *stmt)
997 : {
998 13935 : basic_block bb = gimple_bb (stmt);
999 :
1000 285 : if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
1001 13935 : || bb->loop_father->dont_vectorize
1002 27870 : || gimple_has_volatile_ops (stmt))
1003 : return false;
1004 :
1005 13935 : if (gimple_assign_single_p (stmt))
1006 11939 : return ifcvt_can_use_mask_load_store (stmt);
1007 :
1008 1996 : tree callee;
1009 1996 : if (gimple_call_builtin_p (stmt))
1010 155 : if ((callee = gimple_call_fndecl (stmt))
1011 155 : && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
1012 : {
1013 149 : auto ifn = associated_internal_fn (callee);
1014 149 : auto cond_ifn = get_conditional_internal_fn (ifn);
1015 149 : tree type = TREE_TYPE (gimple_call_fntype (stmt));
1016 149 : return (cond_ifn != IFN_LAST
1017 149 : && vectorized_internal_fn_supported_p (cond_ifn, type));
1018 : }
1019 :
1020 1847 : if (!is_gimple_assign (stmt))
1021 : return false;
1022 :
1023 1841 : tree_code code = gimple_assign_rhs_code (stmt);
1024 1841 : tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
1025 1841 : tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1026 1841 : if (!types_compatible_p (lhs_type, rhs_type))
1027 : return false;
1028 1181 : internal_fn cond_fn = get_conditional_internal_fn (code);
1029 1181 : return (cond_fn != IFN_LAST
1030 1181 : && vectorized_internal_fn_supported_p (cond_fn, lhs_type));
1031 : }
1032 :
1033 : /* Return true when STMT is if-convertible.
1034 :
1035 : GIMPLE_ASSIGN statement is not if-convertible if,
1036 : - it is not movable,
1037 : - it could trap,
1038 : - LHS is not var decl. */
1039 :
1040 : static bool
1041 77777 : if_convertible_gimple_assign_stmt_p (gimple *stmt,
1042 : vec<data_reference_p> refs)
1043 : {
1044 77777 : tree lhs = gimple_assign_lhs (stmt);
1045 :
1046 77777 : if (dump_file && (dump_flags & TDF_DETAILS))
1047 : {
1048 38 : fprintf (dump_file, "-------------------------\n");
1049 38 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1050 : }
1051 :
1052 77777 : if (!is_gimple_reg_type (TREE_TYPE (lhs)))
1053 : return false;
1054 :
1055 : /* Some of these constrains might be too conservative. */
1056 77504 : if (stmt_ends_bb_p (stmt)
1057 77504 : || gimple_has_volatile_ops (stmt)
1058 77429 : || (TREE_CODE (lhs) == SSA_NAME
1059 73126 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1060 154933 : || gimple_has_side_effects (stmt))
1061 : {
1062 75 : if (dump_file && (dump_flags & TDF_DETAILS))
1063 0 : fprintf (dump_file, "stmt not suitable for ifcvt\n");
1064 : return false;
1065 : }
1066 :
1067 : /* tree-into-ssa.cc uses GF_PLF_1, so avoid it, because
1068 : in between if_convertible_loop_p and combine_blocks
1069 : we can perform loop versioning. */
1070 77429 : gimple_set_plf (stmt, GF_PLF_2, false);
1071 :
1072 77429 : if ((! gimple_vuse (stmt)
1073 20079 : || gimple_could_trap_p_1 (stmt, false, false)
1074 20079 : || ! ifcvt_memrefs_wont_trap (stmt, refs))
1075 90268 : && gimple_could_trap_p (stmt))
1076 : {
1077 13780 : if (ifcvt_can_predicate (stmt))
1078 : {
1079 2768 : gimple_set_plf (stmt, GF_PLF_2, true);
1080 2768 : need_to_predicate = true;
1081 2768 : return true;
1082 : }
1083 11012 : if (dump_file && (dump_flags & TDF_DETAILS))
1084 0 : fprintf (dump_file, "tree could trap...\n");
1085 : return false;
1086 : }
1087 63649 : else if (gimple_needing_rewrite_undefined (stmt))
1088 : /* We have to rewrite stmts with undefined overflow. */
1089 28628 : need_to_rewrite_undefined = true;
1090 :
1091 : /* When if-converting stores force versioning, likewise if we
1092 : ended up generating store data races. */
1093 127298 : if (gimple_vdef (stmt))
1094 1523 : need_to_predicate = true;
1095 :
1096 : return true;
1097 : }
1098 :
1099 : /* Return true when SW switch statement is equivalent to cond, that
1100 : all non default labels point to the same label.
1101 :
1102 : Fallthrough is not checked for and could even happen
1103 : with cond (using goto), so is handled.
1104 :
1105 : This is intended for switches created by the if-switch-conversion
1106 : pass, but can handle some programmer supplied cases too. */
1107 :
1108 : static bool
1109 70 : if_convertible_switch_p (gswitch *sw)
1110 : {
1111 70 : if (gimple_switch_num_labels (sw) <= 1)
1112 : return false;
1113 70 : tree label = CASE_LABEL (gimple_switch_label (sw, 1));
1114 762 : for (unsigned i = 1; i < gimple_switch_num_labels (sw); i++)
1115 : {
1116 698 : if (CASE_LABEL (gimple_switch_label (sw, i)) != label)
1117 : return false;
1118 : }
1119 : return true;
1120 : }
1121 :
1122 : /* Return true when STMT is an if-convertible SIMD clone stmts.
1123 :
1124 : A SIMD clone statement is if-convertible if:
1125 : - it is an GIMPLE_CALL,
1126 : - it has a FNDECL,
1127 : - it has SIMD clones,
1128 : - it has at least one inbranch clone. */
1129 : static bool
1130 1622 : if_convertible_simdclone_stmt_p (gimple *stmt)
1131 : {
1132 1622 : if (!is_gimple_call (stmt))
1133 : return false;
1134 :
1135 1622 : tree fndecl = gimple_call_fndecl (stmt);
1136 1622 : if (fndecl)
1137 : {
1138 : /* We can vectorize some builtins and functions with SIMD "inbranch"
1139 : clones. */
1140 1342 : struct cgraph_node *node = cgraph_node::get (fndecl);
1141 1342 : if (node && node->simd_clones != NULL)
1142 : /* Ensure that at least one clone can be "inbranch". */
1143 1972 : for (struct cgraph_node *n = node->simd_clones; n != NULL;
1144 963 : n = n->simdclone->next_clone)
1145 1970 : if (n->simdclone->inbranch)
1146 : return true;
1147 : }
1148 :
1149 : return false;
1150 : }
1151 :
1152 : /* Return true when STMT is if-convertible.
1153 :
1154 : A statement is if-convertible if:
1155 : - it is an if-convertible GIMPLE_ASSIGN,
1156 : - it is a GIMPLE_LABEL or a GIMPLE_COND,
1157 : - it is a switch equivalent to COND
1158 : - it is builtins call,
1159 : - it is a call to a function with a SIMD clone. */
1160 :
1161 : static bool
1162 169077 : if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs)
1163 : {
1164 169077 : switch (gimple_code (stmt))
1165 : {
1166 : case GIMPLE_LABEL:
1167 : case GIMPLE_DEBUG:
1168 : case GIMPLE_COND:
1169 : return true;
1170 :
1171 : case GIMPLE_SWITCH:
1172 : /* Checked elsewhere. */
1173 : return true;
1174 :
1175 77777 : case GIMPLE_ASSIGN:
1176 77777 : return if_convertible_gimple_assign_stmt_p (stmt, refs);
1177 :
1178 1514 : case GIMPLE_CALL:
1179 1514 : {
1180 : /* Check if stmt is a simd clone first. */
1181 1514 : if (if_convertible_simdclone_stmt_p (stmt))
1182 : {
1183 1007 : gimple_set_plf (stmt, GF_PLF_2, true);
1184 1007 : need_to_predicate = true;
1185 1007 : return true;
1186 : }
1187 :
1188 : /* Check if the call can trap and if so require predication. */
1189 507 : if (gimple_could_trap_p (stmt))
1190 : {
1191 155 : if (ifcvt_can_predicate (stmt))
1192 : {
1193 108 : gimple_set_plf (stmt, GF_PLF_2, true);
1194 108 : need_to_predicate = true;
1195 108 : return true;
1196 : }
1197 : else
1198 : {
1199 47 : if (dump_file && (dump_flags & TDF_DETAILS))
1200 0 : fprintf (dump_file, "stmt could trap...\n");
1201 : return false;
1202 : }
1203 : }
1204 :
1205 : /* Check if it's a prefetch. Many ISAs contain vectorized and/or
1206 : conditional prefetches so if-convert should convert them or remove
1207 : them. Mark them as supported. */
1208 352 : if (gimple_call_builtin_p (stmt, BUILT_IN_PREFETCH))
1209 : return true;
1210 :
1211 : /* There are some IFN_s that are used to replace builtins but have the
1212 : same semantics. Even if MASK_CALL cannot handle them vectorable_call
1213 : will insert the proper selection, so do not block conversion. */
1214 350 : int flags = gimple_call_flags (stmt);
1215 350 : if ((flags & ECF_CONST)
1216 350 : && !(flags & ECF_LOOPING_CONST_OR_PURE)
1217 700 : && gimple_call_combined_fn (stmt) != CFN_LAST)
1218 336 : return true;
1219 :
1220 : return false;
1221 : }
1222 :
1223 0 : default:
1224 : /* Don't know what to do with 'em so don't do anything. */
1225 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1226 : {
1227 0 : fprintf (dump_file, "don't know what to do\n");
1228 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1229 : }
1230 : return false;
1231 : }
1232 : }
1233 :
1234 : /* Assumes that BB has more than 1 predecessors.
1235 : Returns false if at least one successor is not on critical edge
1236 : and true otherwise. */
1237 :
1238 : static inline bool
1239 81693 : all_preds_critical_p (basic_block bb)
1240 : {
1241 81693 : edge e;
1242 81693 : edge_iterator ei;
1243 :
1244 160134 : FOR_EACH_EDGE (e, ei, bb->preds)
1245 141074 : if (EDGE_COUNT (e->src->succs) == 1)
1246 : return false;
1247 : return true;
1248 : }
1249 :
1250 : /* Return true when BB is if-convertible. This routine does not check
1251 : basic block's statements and phis.
1252 :
1253 : A basic block is not if-convertible if:
1254 : - it is non-empty and it is after the exit block (in BFS order),
1255 : - it is after the exit block but before the latch,
1256 : - its edges are not normal.
1257 :
1258 : EXIT_BB is the basic block containing the exit of the LOOP. BB is
1259 : inside LOOP. */
1260 :
1261 : static bool
1262 211909 : if_convertible_bb_p (class loop *loop, basic_block bb, basic_block exit_bb)
1263 : {
1264 211909 : edge e;
1265 211909 : edge_iterator ei;
1266 :
1267 211909 : if (dump_file && (dump_flags & TDF_DETAILS))
1268 146 : fprintf (dump_file, "----------[%d]-------------\n", bb->index);
1269 :
1270 211909 : if (EDGE_COUNT (bb->succs) > 2)
1271 : return false;
1272 :
1273 423690 : if (gcall *call = safe_dyn_cast <gcall *> (*gsi_last_bb (bb)))
1274 202 : if (gimple_call_ctrl_altering_p (call))
1275 : return false;
1276 :
1277 211845 : if (exit_bb)
1278 : {
1279 38335 : if (bb != loop->latch)
1280 : {
1281 538 : if (dump_file && (dump_flags & TDF_DETAILS))
1282 0 : fprintf (dump_file, "basic block after exit bb but before latch\n");
1283 : return false;
1284 : }
1285 37797 : else if (!empty_block_p (bb))
1286 : {
1287 645 : if (dump_file && (dump_flags & TDF_DETAILS))
1288 0 : fprintf (dump_file, "non empty basic block after exit bb\n");
1289 : return false;
1290 : }
1291 37152 : else if (bb == loop->latch
1292 37152 : && bb != exit_bb
1293 74304 : && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
1294 : {
1295 11 : if (dump_file && (dump_flags & TDF_DETAILS))
1296 0 : fprintf (dump_file, "latch is not dominated by exit_block\n");
1297 : return false;
1298 : }
1299 : }
1300 :
1301 : /* Be less adventurous and handle only normal edges. */
1302 514975 : FOR_EACH_EDGE (e, ei, bb->succs)
1303 304336 : if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
1304 : {
1305 12 : if (dump_file && (dump_flags & TDF_DETAILS))
1306 0 : fprintf (dump_file, "Difficult to handle edges\n");
1307 : return false;
1308 : }
1309 :
1310 : return true;
1311 : }
1312 :
1313 : /* Return true when all predecessor blocks of BB are visited. The
1314 : VISITED bitmap keeps track of the visited blocks. */
1315 :
1316 : static bool
1317 2330839 : pred_blocks_visited_p (basic_block bb, bitmap *visited)
1318 : {
1319 2330839 : edge e;
1320 2330839 : edge_iterator ei;
1321 4015680 : FOR_EACH_EDGE (e, ei, bb->preds)
1322 2639263 : if (!bitmap_bit_p (*visited, e->src->index))
1323 : return false;
1324 :
1325 : return true;
1326 : }
1327 :
1328 : /* Get body of a LOOP in suitable order for if-conversion. It is
1329 : caller's responsibility to deallocate basic block list.
1330 : If-conversion suitable order is, breadth first sort (BFS) order
1331 : with an additional constraint: select a block only if all its
1332 : predecessors are already selected. */
1333 :
1334 : static basic_block *
1335 414581 : get_loop_body_in_if_conv_order (const class loop *loop)
1336 : {
1337 414581 : basic_block *blocks, *blocks_in_bfs_order;
1338 414581 : basic_block bb;
1339 414581 : bitmap visited;
1340 414581 : unsigned int index = 0;
1341 414581 : unsigned int visited_count = 0;
1342 :
1343 414581 : gcc_assert (loop->num_nodes);
1344 414581 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1345 :
1346 414581 : blocks = XCNEWVEC (basic_block, loop->num_nodes);
1347 414581 : visited = BITMAP_ALLOC (NULL);
1348 :
1349 414581 : blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1350 :
1351 414581 : index = 0;
1352 4060438 : while (index < loop->num_nodes)
1353 : {
1354 3231328 : bb = blocks_in_bfs_order [index];
1355 :
1356 3231328 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1357 : {
1358 52 : free (blocks_in_bfs_order);
1359 52 : BITMAP_FREE (visited);
1360 52 : free (blocks);
1361 52 : return NULL;
1362 : }
1363 :
1364 3231276 : if (!bitmap_bit_p (visited, bb->index))
1365 : {
1366 2330839 : if (pred_blocks_visited_p (bb, &visited)
1367 2330839 : || bb == loop->header)
1368 : {
1369 : /* This block is now visited. */
1370 1790998 : bitmap_set_bit (visited, bb->index);
1371 1790998 : blocks[visited_count++] = bb;
1372 : }
1373 : }
1374 :
1375 3231276 : index++;
1376 :
1377 3231276 : if (index == loop->num_nodes
1378 477266 : && visited_count != loop->num_nodes)
1379 : /* Not done yet. */
1380 3231276 : index = 0;
1381 : }
1382 414529 : free (blocks_in_bfs_order);
1383 414529 : BITMAP_FREE (visited);
1384 :
1385 : /* Go through loop and reject if-conversion or lowering of bitfields if we
1386 : encounter statements we do not believe the vectorizer will be able to
1387 : handle. If adding a new type of statement here, make sure
1388 : 'ifcvt_local_dce' is also able to handle it properly. */
1389 2607906 : for (index = 0; index < loop->num_nodes; index++)
1390 : {
1391 1781443 : basic_block bb = blocks[index];
1392 1781443 : gimple_stmt_iterator gsi;
1393 :
1394 1781443 : bool may_have_nonlocal_labels
1395 1781443 : = bb_with_exit_edge_p (loop, bb) || bb == loop->latch;
1396 16589331 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1397 13029040 : switch (gimple_code (gsi_stmt (gsi)))
1398 : {
1399 41226 : case GIMPLE_LABEL:
1400 41226 : if (!may_have_nonlocal_labels)
1401 : {
1402 6916 : tree label
1403 6916 : = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi)));
1404 13832 : if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
1405 : {
1406 49 : free (blocks);
1407 49 : return NULL;
1408 : }
1409 : }
1410 : /* Fallthru. */
1411 13026445 : case GIMPLE_ASSIGN:
1412 13026445 : case GIMPLE_CALL:
1413 13026445 : case GIMPLE_DEBUG:
1414 13026445 : case GIMPLE_COND:
1415 13026445 : case GIMPLE_SWITCH:
1416 13026445 : gimple_set_uid (gsi_stmt (gsi), 0);
1417 13026445 : break;
1418 2546 : default:
1419 2546 : free (blocks);
1420 2546 : return NULL;
1421 : }
1422 : }
1423 : return blocks;
1424 : }
1425 :
1426 : /* Returns true when the analysis of the predicates for all the basic
1427 : blocks in LOOP succeeded.
1428 :
1429 : predicate_bbs first allocates the predicates of the basic blocks.
1430 : These fields are then initialized with the tree expressions
1431 : representing the predicates under which a basic block is executed
1432 : in the LOOP. As the loop->header is executed at each iteration, it
1433 : has the "true" predicate. Other statements executed under a
1434 : condition are predicated with that condition, for example
1435 :
1436 : | if (x)
1437 : | S1;
1438 : | else
1439 : | S2;
1440 :
1441 : S1 will be predicated with "x", and
1442 : S2 will be predicated with "!x". */
1443 :
1444 : static void
1445 37141 : predicate_bbs (loop_p loop)
1446 : {
1447 37141 : unsigned int i;
1448 :
1449 243239 : for (i = 0; i < loop->num_nodes; i++)
1450 206098 : init_bb_predicate (ifc_bbs[i]);
1451 :
1452 243239 : for (i = 0; i < loop->num_nodes; i++)
1453 : {
1454 206098 : basic_block bb = ifc_bbs[i];
1455 206098 : tree cond;
1456 :
1457 : /* The loop latch and loop exit block are always executed and
1458 : have no extra conditions to be processed: skip them. */
1459 280380 : if (bb == loop->latch
1460 206098 : || bb_with_exit_edge_p (loop, bb))
1461 : {
1462 74282 : reset_bb_predicate (bb);
1463 74282 : continue;
1464 : }
1465 :
1466 131816 : cond = bb_predicate (bb);
1467 263632 : if (gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
1468 : {
1469 53600 : tree c2;
1470 53600 : edge true_edge, false_edge;
1471 53600 : location_t loc = gimple_location (stmt);
1472 53600 : tree c;
1473 : /* gcc.dg/fold-bopcond-1.c shows that despite all forwprop passes
1474 : conditions can remain unfolded because of multiple uses so
1475 : try to re-fold here, especially to get precision changing
1476 : conversions sorted out. Do not simply fold the stmt since
1477 : this is analysis only. When conditions were embedded in
1478 : COND_EXPRs those were folded separately before folding the
1479 : COND_EXPR but as they are now outside we have to make sure
1480 : to fold them. Do it here - another opportunity would be to
1481 : fold predicates as they are inserted. */
1482 53600 : gimple_match_op cexpr (gimple_match_cond::UNCOND,
1483 53600 : gimple_cond_code (stmt),
1484 : boolean_type_node,
1485 : gimple_cond_lhs (stmt),
1486 53600 : gimple_cond_rhs (stmt));
1487 53600 : if (cexpr.resimplify (NULL, follow_all_ssa_edges)
1488 4096 : && cexpr.code.is_tree_code ()
1489 57696 : && TREE_CODE_CLASS ((tree_code)cexpr.code) == tcc_comparison)
1490 560 : c = build2_loc (loc, (tree_code)cexpr.code, boolean_type_node,
1491 : cexpr.ops[0], cexpr.ops[1]);
1492 : else
1493 53040 : c = build2_loc (loc, gimple_cond_code (stmt),
1494 : boolean_type_node,
1495 : gimple_cond_lhs (stmt),
1496 : gimple_cond_rhs (stmt));
1497 :
1498 : /* Add new condition into destination's predicate list. */
1499 53600 : extract_true_false_edges_from_block (gimple_bb (stmt),
1500 : &true_edge, &false_edge);
1501 :
1502 : /* If C is true, then TRUE_EDGE is taken. */
1503 53600 : add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1504 : unshare_expr (c));
1505 :
1506 : /* If C is false, then FALSE_EDGE is taken. */
1507 53600 : c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1508 : unshare_expr (c));
1509 53600 : add_to_dst_predicate_list (loop, false_edge,
1510 : unshare_expr (cond), c2);
1511 :
1512 53600 : cond = NULL_TREE;
1513 : }
1514 :
1515 : /* Assumes the limited COND like switches checked for earlier. */
1516 78216 : else if (gswitch *sw = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
1517 : {
1518 79 : location_t loc = gimple_location (*gsi_last_bb (bb));
1519 :
1520 79 : tree default_label = CASE_LABEL (gimple_switch_default_label (sw));
1521 79 : tree cond_label = CASE_LABEL (gimple_switch_label (sw, 1));
1522 :
1523 79 : edge false_edge = find_edge (bb, label_to_block (cfun, default_label));
1524 79 : edge true_edge = find_edge (bb, label_to_block (cfun, cond_label));
1525 :
1526 : /* Create chain of switch tests for each case. */
1527 79 : tree switch_cond = NULL_TREE;
1528 79 : tree index = gimple_switch_index (sw);
1529 802 : for (unsigned i = 1; i < gimple_switch_num_labels (sw); i++)
1530 : {
1531 723 : tree label = gimple_switch_label (sw, i);
1532 723 : tree case_cond;
1533 723 : if (CASE_HIGH (label))
1534 : {
1535 7 : tree low = build2_loc (loc, GE_EXPR,
1536 : boolean_type_node,
1537 7 : index, fold_convert_loc (loc, TREE_TYPE (index),
1538 7 : CASE_LOW (label)));
1539 14 : tree high = build2_loc (loc, LE_EXPR,
1540 : boolean_type_node,
1541 7 : index, fold_convert_loc (loc, TREE_TYPE (index),
1542 7 : CASE_HIGH (label)));
1543 7 : case_cond = build2_loc (loc, TRUTH_AND_EXPR,
1544 : boolean_type_node,
1545 : low, high);
1546 : }
1547 : else
1548 716 : case_cond = build2_loc (loc, EQ_EXPR,
1549 : boolean_type_node,
1550 : index,
1551 716 : fold_convert_loc (loc, TREE_TYPE (index),
1552 716 : CASE_LOW (label)));
1553 723 : if (i > 1)
1554 644 : switch_cond = build2_loc (loc, TRUTH_OR_EXPR,
1555 : boolean_type_node,
1556 : case_cond, switch_cond);
1557 : else
1558 : switch_cond = case_cond;
1559 : }
1560 :
1561 79 : add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1562 : unshare_expr (switch_cond));
1563 79 : switch_cond = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1564 : unshare_expr (switch_cond));
1565 79 : add_to_dst_predicate_list (loop, false_edge,
1566 : unshare_expr (cond), switch_cond);
1567 79 : cond = NULL_TREE;
1568 : }
1569 :
1570 : /* If current bb has only one successor, then consider it as an
1571 : unconditional goto. */
1572 284235 : if (single_succ_p (bb))
1573 : {
1574 78137 : basic_block bb_n = single_succ (bb);
1575 :
1576 : /* The successor bb inherits the predicate of its
1577 : predecessor. If there is no predicate in the predecessor
1578 : bb, then consider the successor bb as always executed. */
1579 78137 : if (cond == NULL_TREE)
1580 0 : cond = boolean_true_node;
1581 :
1582 78137 : add_to_predicate_list (loop, bb_n, cond);
1583 : }
1584 : }
1585 :
1586 : /* The loop header is always executed. */
1587 37141 : reset_bb_predicate (loop->header);
1588 37141 : gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1589 : && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1590 37141 : }
1591 :
1592 : /* Build region by adding loop pre-header and post-header blocks. */
1593 :
1594 : static vec<basic_block>
1595 37141 : build_region (class loop *loop)
1596 : {
1597 37141 : vec<basic_block> region = vNULL;
1598 37141 : basic_block exit_bb = NULL;
1599 :
1600 37141 : gcc_assert (ifc_bbs);
1601 : /* The first element is loop pre-header. */
1602 37141 : region.safe_push (loop_preheader_edge (loop)->src);
1603 :
1604 280380 : for (unsigned int i = 0; i < loop->num_nodes; i++)
1605 : {
1606 206098 : basic_block bb = ifc_bbs[i];
1607 206098 : region.safe_push (bb);
1608 : /* Find loop postheader. */
1609 206098 : edge e;
1610 206098 : edge_iterator ei;
1611 457262 : FOR_EACH_EDGE (e, ei, bb->succs)
1612 288305 : if (loop_exit_edge_p (loop, e))
1613 : {
1614 37141 : exit_bb = e->dest;
1615 37141 : break;
1616 : }
1617 : }
1618 : /* The last element is loop post-header. */
1619 37141 : gcc_assert (exit_bb);
1620 37141 : region.safe_push (exit_bb);
1621 37141 : return region;
1622 : }
1623 :
1624 : /* Return true when LOOP is if-convertible. This is a helper function
1625 : for if_convertible_loop_p. REFS and DDRS are initialized and freed
1626 : in if_convertible_loop_p. */
1627 :
1628 : static bool
1629 38411 : if_convertible_loop_p_1 (class loop *loop, vec<data_reference_p> *refs)
1630 : {
1631 38411 : unsigned int i;
1632 38411 : basic_block exit_bb = NULL;
1633 38411 : vec<basic_block> region;
1634 :
1635 38411 : calculate_dominance_info (CDI_DOMINATORS);
1636 :
1637 287461 : for (i = 0; i < loop->num_nodes; i++)
1638 : {
1639 211909 : basic_block bb = ifc_bbs[i];
1640 :
1641 211909 : if (!if_convertible_bb_p (loop, bb, exit_bb))
1642 : return false;
1643 :
1644 210639 : if (bb_with_exit_edge_p (loop, bb))
1645 38335 : exit_bb = bb;
1646 : }
1647 :
1648 37141 : data_reference_p dr;
1649 :
1650 37141 : innermost_DR_map
1651 37141 : = new hash_map<innermost_loop_behavior_hash, data_reference_p>;
1652 37141 : baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>;
1653 :
1654 : /* Compute post-dominator tree locally. */
1655 37141 : region = build_region (loop);
1656 37141 : calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region);
1657 :
1658 37141 : predicate_bbs (loop);
1659 :
1660 : /* Free post-dominator tree since it is not used after predication. */
1661 37141 : free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region);
1662 37141 : region.release ();
1663 :
1664 194510 : for (i = 0; refs->iterate (i, &dr); i++)
1665 : {
1666 120228 : tree ref = DR_REF (dr);
1667 :
1668 120228 : dr->aux = XNEW (struct ifc_dr);
1669 120228 : DR_BASE_W_UNCONDITIONALLY (dr) = false;
1670 120228 : DR_RW_UNCONDITIONALLY (dr) = false;
1671 120228 : DR_W_UNCONDITIONALLY (dr) = false;
1672 120228 : IFC_DR (dr)->rw_predicate = boolean_false_node;
1673 120228 : IFC_DR (dr)->w_predicate = boolean_false_node;
1674 120228 : IFC_DR (dr)->base_w_predicate = boolean_false_node;
1675 120228 : if (gimple_uid (DR_STMT (dr)) == 0)
1676 119545 : gimple_set_uid (DR_STMT (dr), i + 1);
1677 :
1678 : /* If DR doesn't have innermost loop behavior or it's a compound
1679 : memory reference, we synthesize its innermost loop behavior
1680 : for hashing. */
1681 120228 : if (TREE_CODE (ref) == COMPONENT_REF
1682 : || TREE_CODE (ref) == IMAGPART_EXPR
1683 : || TREE_CODE (ref) == REALPART_EXPR
1684 83179 : || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr)
1685 26534 : || DR_INIT (dr) || DR_STEP (dr)))
1686 : {
1687 108667 : while (TREE_CODE (ref) == COMPONENT_REF
1688 64742 : || TREE_CODE (ref) == IMAGPART_EXPR
1689 172831 : || TREE_CODE (ref) == REALPART_EXPR)
1690 45084 : ref = TREE_OPERAND (ref, 0);
1691 :
1692 63583 : memset (&DR_INNERMOST (dr), 0, sizeof (DR_INNERMOST (dr)));
1693 63583 : DR_BASE_ADDRESS (dr) = ref;
1694 : }
1695 120228 : hash_memrefs_baserefs_and_store_DRs_read_written_info (dr);
1696 : }
1697 :
1698 186363 : for (i = 0; i < loop->num_nodes; i++)
1699 : {
1700 160643 : basic_block bb = ifc_bbs[i];
1701 160643 : gimple_stmt_iterator itr;
1702 :
1703 : /* Check the if-convertibility of statements in predicated BBs. */
1704 160643 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1705 293430 : for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1706 169077 : if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
1707 38411 : return false;
1708 : }
1709 :
1710 : /* Checking PHIs needs to be done after stmts, as the fact whether there
1711 : are any masked loads or stores affects the tests. Also check switch
1712 : stmts for supported shape as that cannot be skipped for always
1713 : executed blocks. */
1714 160879 : for (i = 0; i < loop->num_nodes; i++)
1715 : {
1716 135165 : basic_block bb = ifc_bbs[i];
1717 135165 : gphi_iterator itr;
1718 :
1719 265178 : for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1720 130013 : if (!if_convertible_phi_p (loop, bb, itr.phi ()))
1721 6 : return false;
1722 352643 : if (gswitch *s = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
1723 70 : if (!if_convertible_switch_p (s))
1724 6 : return false;
1725 : }
1726 :
1727 25714 : if (dump_file)
1728 42 : fprintf (dump_file, "Applying if-conversion\n");
1729 :
1730 : return true;
1731 : }
1732 :
1733 : /* Return true when LOOP is if-convertible.
1734 : LOOP is if-convertible if:
1735 : - it is innermost,
1736 : - it has two or more basic blocks,
1737 : - it has only one exit,
1738 : - loop header is not the exit edge,
1739 : - if its basic blocks and phi nodes are if convertible. */
1740 :
1741 : static bool
1742 38552 : if_convertible_loop_p (class loop *loop, vec<data_reference_p> *refs)
1743 : {
1744 38552 : edge e;
1745 38552 : edge_iterator ei;
1746 38552 : bool res = false;
1747 :
1748 : /* Handle only innermost loop. */
1749 38552 : if (!loop || loop->inner)
1750 : {
1751 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1752 0 : fprintf (dump_file, "not innermost loop\n");
1753 : return false;
1754 : }
1755 :
1756 : /* If only one block, no need for if-conversion. */
1757 38552 : if (loop->num_nodes <= 2)
1758 : {
1759 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1760 0 : fprintf (dump_file, "less than 2 basic blocks\n");
1761 : return false;
1762 : }
1763 :
1764 : /* If one of the loop header's edge is an exit edge then do not
1765 : apply if-conversion. */
1766 115536 : FOR_EACH_EDGE (e, ei, loop->header->succs)
1767 77125 : if (loop_exit_edge_p (loop, e))
1768 : return false;
1769 :
1770 38411 : res = if_convertible_loop_p_1 (loop, refs);
1771 :
1772 75552 : delete innermost_DR_map;
1773 38411 : innermost_DR_map = NULL;
1774 :
1775 75552 : delete baseref_DR_map;
1776 38411 : baseref_DR_map = NULL;
1777 :
1778 38411 : return res;
1779 : }
1780 :
1781 : /* Return reduc_1 if has_nop.
1782 :
1783 : if (...)
1784 : tmp1 = (unsigned type) reduc_1;
1785 : tmp2 = tmp1 + rhs2;
1786 : reduc_3 = (signed type) tmp2. */
1787 : static tree
1788 11654 : strip_nop_cond_scalar_reduction (bool has_nop, tree op)
1789 : {
1790 11654 : if (!has_nop)
1791 : return op;
1792 :
1793 414 : if (TREE_CODE (op) != SSA_NAME)
1794 : return NULL_TREE;
1795 :
1796 368 : gassign *stmt = safe_dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op));
1797 368 : if (!stmt
1798 368 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
1799 230 : || !tree_nop_conversion_p (TREE_TYPE (op), TREE_TYPE
1800 : (gimple_assign_rhs1 (stmt))))
1801 : return NULL_TREE;
1802 :
1803 219 : return gimple_assign_rhs1 (stmt);
1804 : }
1805 :
1806 : /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1807 : which is in predicated basic block.
1808 : In fact, the following PHI pattern is searching:
1809 : loop-header:
1810 : reduc_1 = PHI <..., reduc_2>
1811 : ...
1812 : if (...)
1813 : reduc_3 = ...
1814 : reduc_2 = PHI <reduc_1, reduc_3>
1815 :
1816 : ARG_0 and ARG_1 are correspondent PHI arguments.
1817 : REDUC, OP0 and OP1 contain reduction stmt and its operands.
1818 : INTERMEDIATE is true if PHI does not directly feed the loop-header PHI.
1819 : EXTENDED is true if PHI has > 2 arguments. */
1820 :
1821 : static bool
1822 47533 : is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1,
1823 : tree *op0, tree *op1, bool extended, bool* has_nop,
1824 : gimple **nop_reduc, bool *intermediate)
1825 : {
1826 47533 : tree lhs, r_op1, r_op2, r_nop1, r_nop2;
1827 47533 : gimple *stmt;
1828 47533 : gimple *header_phi = NULL;
1829 47533 : enum tree_code reduction_op;
1830 47533 : basic_block bb = gimple_bb (phi);
1831 47533 : class loop *loop = bb->loop_father;
1832 47533 : edge latch_e = loop_latch_edge (loop);
1833 47533 : imm_use_iterator imm_iter;
1834 47533 : use_operand_p use_p;
1835 47533 : edge e;
1836 47533 : edge_iterator ei;
1837 47533 : bool result = *has_nop = *intermediate = false;
1838 47533 : if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
1839 : return false;
1840 :
1841 34851 : if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
1842 : {
1843 8756 : lhs = arg_1;
1844 8756 : header_phi = SSA_NAME_DEF_STMT (arg_0);
1845 8756 : stmt = SSA_NAME_DEF_STMT (arg_1);
1846 : }
1847 26095 : else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
1848 : {
1849 11461 : lhs = arg_0;
1850 11461 : header_phi = SSA_NAME_DEF_STMT (arg_1);
1851 11461 : stmt = SSA_NAME_DEF_STMT (arg_0);
1852 : }
1853 : else
1854 : return false;
1855 20217 : if (gimple_bb (header_phi) != loop->header)
1856 : return false;
1857 :
1858 19331 : tree latch_value = PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e);
1859 19331 : *intermediate = latch_value != PHI_RESULT (phi);
1860 :
1861 19331 : if (gimple_code (stmt) != GIMPLE_ASSIGN
1862 19331 : || gimple_has_volatile_ops (stmt))
1863 : return false;
1864 :
1865 14714 : if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1866 : return false;
1867 :
1868 14609 : if (!is_predicated (gimple_bb (stmt)))
1869 : return false;
1870 :
1871 : /* Check that stmt-block is predecessor of phi-block. */
1872 11610 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1873 11357 : if (e->dest == bb)
1874 : {
1875 : result = true;
1876 : break;
1877 : }
1878 11104 : if (!result)
1879 : return false;
1880 :
1881 10851 : if (!has_single_use (lhs))
1882 : return false;
1883 :
1884 10781 : reduction_op = gimple_assign_rhs_code (stmt);
1885 :
1886 : /* Catch something like below
1887 :
1888 : loop-header:
1889 : reduc_1 = PHI <..., reduc_2>
1890 : ...
1891 : if (...)
1892 : tmp1 = (unsigned type) reduc_1;
1893 : tmp2 = tmp1 + rhs2;
1894 : reduc_3 = (signed type) tmp2;
1895 :
1896 : reduc_2 = PHI <reduc_1, reduc_3>
1897 :
1898 : and convert to
1899 :
1900 : reduc_2 = PHI <0, reduc_1>
1901 : tmp1 = (unsigned type)reduc_1;
1902 : ifcvt = cond_expr ? rhs2 : 0
1903 : tmp2 = tmp1 +/- ifcvt;
1904 : reduc_1 = (signed type)tmp2; */
1905 :
1906 10781 : if (CONVERT_EXPR_CODE_P (reduction_op))
1907 : {
1908 449 : lhs = gimple_assign_rhs1 (stmt);
1909 449 : if (TREE_CODE (lhs) != SSA_NAME
1910 449 : || !has_single_use (lhs))
1911 : return false;
1912 :
1913 255 : *nop_reduc = stmt;
1914 255 : stmt = SSA_NAME_DEF_STMT (lhs);
1915 255 : if (gimple_bb (stmt) != gimple_bb (*nop_reduc)
1916 255 : || !is_gimple_assign (stmt))
1917 : return false;
1918 :
1919 246 : *has_nop = true;
1920 246 : reduction_op = gimple_assign_rhs_code (stmt);
1921 : }
1922 :
1923 : /* A reduction with a further latch update must keep the PLUS outside
1924 : the conditional expression. The no-op conversion case is not needed
1925 : for this form. */
1926 10578 : if (*intermediate && (*has_nop || reduction_op != PLUS_EXPR))
1927 : return false;
1928 :
1929 10346 : if (reduction_op != PLUS_EXPR
1930 : && reduction_op != MINUS_EXPR
1931 10346 : && reduction_op != MULT_EXPR
1932 10346 : && reduction_op != BIT_IOR_EXPR
1933 : && reduction_op != BIT_XOR_EXPR
1934 4639 : && reduction_op != BIT_AND_EXPR)
1935 : return false;
1936 5827 : r_op1 = gimple_assign_rhs1 (stmt);
1937 5827 : r_op2 = gimple_assign_rhs2 (stmt);
1938 :
1939 5827 : r_nop1 = strip_nop_cond_scalar_reduction (*has_nop, r_op1);
1940 5827 : r_nop2 = strip_nop_cond_scalar_reduction (*has_nop, r_op2);
1941 :
1942 : /* Make R_OP1 to hold reduction variable. */
1943 5827 : if (r_nop2 == PHI_RESULT (header_phi)
1944 5827 : && commutative_tree_code (reduction_op))
1945 : {
1946 : std::swap (r_op1, r_op2);
1947 : std::swap (r_nop1, r_nop2);
1948 : }
1949 4665 : else if (r_nop1 != PHI_RESULT (header_phi))
1950 : return false;
1951 :
1952 5501 : if (*intermediate)
1953 : {
1954 120 : tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1955 120 : if (!SCALAR_FLOAT_TYPE_P (type)
1956 120 : && (!INTEGRAL_TYPE_P (type) || TYPE_OVERFLOW_TRAPS (type)))
1957 : return false;
1958 :
1959 120 : tree zero = neutral_op_for_reduction (type, PLUS_EXPR, NULL_TREE,
1960 : false);
1961 : /* The inactive addend must leave the reduction value unchanged. */
1962 120 : if (SCALAR_FLOAT_TYPE_P (type)
1963 120 : && !fold_real_zero_addition_p (type, r_op1, zero, 0))
1964 : return false;
1965 : }
1966 :
1967 5499 : if (*has_nop)
1968 : {
1969 : /* Check that R_NOP1 is used in nop_stmt or in PHI only. */
1970 430 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_nop1)
1971 : {
1972 304 : gimple *use_stmt = USE_STMT (use_p);
1973 304 : if (is_gimple_debug (use_stmt))
1974 0 : continue;
1975 304 : if (use_stmt == SSA_NAME_DEF_STMT (r_op1))
1976 126 : continue;
1977 178 : if (use_stmt != phi)
1978 42 : return false;
1979 168 : }
1980 : }
1981 :
1982 : /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1983 16891 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
1984 : {
1985 11702 : gimple *use_stmt = USE_STMT (use_p);
1986 11702 : if (is_gimple_debug (use_stmt))
1987 29 : continue;
1988 11673 : if (use_stmt == stmt)
1989 5214 : continue;
1990 6459 : if (gimple_code (use_stmt) != GIMPLE_PHI)
1991 268 : return false;
1992 268 : }
1993 :
1994 5189 : *op0 = r_op1; *op1 = r_op2;
1995 5189 : *reduc = stmt;
1996 5189 : return true;
1997 : }
1998 :
1999 : /* Converts conditional scalar reduction into unconditional form, e.g.
2000 : bb_4
2001 : if (_5 != 0) goto bb_5 else goto bb_6
2002 : end_bb_4
2003 : bb_5
2004 : res_6 = res_13 + 1;
2005 : end_bb_5
2006 : bb_6
2007 : # res_2 = PHI <res_13(4), res_6(5)>
2008 : end_bb_6
2009 :
2010 : will be converted into sequence
2011 : _ifc__1 = _5 != 0 ? 1 : 0;
2012 : res_2 = res_13 + _ifc__1;
2013 : Argument SWAP tells that arguments of conditional expression should be
2014 : swapped. INTERMEDIATE says that this is not the latch value, so the
2015 : PLUS must remain unconditional.
2016 : We can assume that we versioned the loop for vectorization, so can
2017 : create a COND_OP.
2018 : Returns rhs of resulting PHI assignment. */
2019 :
2020 : static tree
2021 5189 : convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi,
2022 : tree cond, tree op0, tree op1, bool swap,
2023 : bool has_nop, gimple* nop_reduc,
2024 : bool intermediate)
2025 : {
2026 5189 : gimple_stmt_iterator stmt_it;
2027 5189 : gimple *new_assign;
2028 5189 : tree rhs;
2029 5189 : tree rhs1 = gimple_assign_rhs1 (reduc);
2030 5189 : tree lhs = gimple_assign_lhs (reduc);
2031 5189 : tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
2032 5189 : tree c;
2033 5189 : enum tree_code reduction_op = gimple_assign_rhs_code (reduc);
2034 5189 : tree op_nochange = neutral_op_for_reduction (TREE_TYPE (rhs1), reduction_op,
2035 : NULL, false);
2036 5189 : gimple_seq stmts = NULL;
2037 :
2038 5189 : if (dump_file && (dump_flags & TDF_DETAILS))
2039 : {
2040 12 : fprintf (dump_file, "Found cond scalar reduction.\n");
2041 12 : print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
2042 : }
2043 :
2044 : /* If possible create a COND_OP instead of a COND_EXPR and an OP_EXPR.
2045 : The COND_OP will have a neutral_op else value. */
2046 5189 : internal_fn ifn;
2047 5189 : ifn = get_conditional_internal_fn (reduction_op);
2048 5189 : if (!intermediate
2049 5189 : && ifn != IFN_LAST
2050 5080 : && vectorized_internal_fn_supported_p (ifn, TREE_TYPE (lhs))
2051 1363 : && !VECTOR_TYPE_P (TREE_TYPE (lhs))
2052 6552 : && !swap)
2053 : {
2054 1343 : gcall *cond_call = gimple_build_call_internal (ifn, 4,
2055 : unshare_expr (cond),
2056 : op0, op1, op0);
2057 1343 : gsi_insert_before (gsi, cond_call, GSI_SAME_STMT);
2058 1343 : gimple_call_set_lhs (cond_call, tmp);
2059 : rhs = tmp;
2060 : }
2061 : else
2062 : {
2063 : /* Build cond expression using COND and constant operand
2064 : of reduction rhs. */
2065 7427 : c = fold_build_cond_expr (TREE_TYPE (rhs1),
2066 : unshare_expr (cond),
2067 : swap ? op_nochange : op1,
2068 : swap ? op1 : op_nochange);
2069 : /* Create assignment stmt and insert it at GSI. */
2070 3846 : new_assign = gimple_build_assign (tmp, c);
2071 3846 : gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
2072 : /* Build rhs for unconditional increment/decrement/logic_operation. */
2073 3846 : rhs = gimple_build (&stmts, reduction_op,
2074 3846 : TREE_TYPE (rhs1), op0, tmp);
2075 : }
2076 :
2077 5189 : if (has_nop)
2078 : {
2079 126 : rhs = gimple_convert (&stmts,
2080 126 : TREE_TYPE (gimple_assign_lhs (nop_reduc)), rhs);
2081 126 : stmt_it = gsi_for_stmt (nop_reduc);
2082 126 : gsi_remove (&stmt_it, true);
2083 126 : release_defs (nop_reduc);
2084 : }
2085 5189 : gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
2086 :
2087 : /* Delete original reduction stmt. */
2088 5189 : stmt_it = gsi_for_stmt (reduc);
2089 5189 : gsi_remove (&stmt_it, true);
2090 5189 : release_defs (reduc);
2091 5189 : return rhs;
2092 : }
2093 :
2094 : /* Generate a simplified conditional. */
2095 :
2096 : static tree
2097 53823 : gen_simplified_condition (tree cond, scalar_cond_masked_set_type &cond_set)
2098 : {
2099 : /* Check if the value is already live in a previous branch. This resolves
2100 : nested conditionals from diamond PHI reductions. */
2101 53823 : if (TREE_CODE (cond) == SSA_NAME)
2102 : {
2103 53815 : gimple *stmt = SSA_NAME_DEF_STMT (cond);
2104 53815 : gassign *assign = NULL;
2105 53815 : if ((assign = as_a <gassign *> (stmt))
2106 53815 : && gimple_assign_rhs_code (assign) == BIT_AND_EXPR)
2107 : {
2108 3573 : tree arg1 = gimple_assign_rhs1 (assign);
2109 3573 : tree arg2 = gimple_assign_rhs2 (assign);
2110 3573 : if (cond_set.contains ({ arg1, 1 }))
2111 162 : arg1 = boolean_true_node;
2112 : else
2113 3411 : arg1 = gen_simplified_condition (arg1, cond_set);
2114 :
2115 3573 : if (cond_set.contains ({ arg2, 1 }))
2116 1788 : arg2 = boolean_true_node;
2117 : else
2118 1785 : arg2 = gen_simplified_condition (arg2, cond_set);
2119 :
2120 3573 : cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, arg1, arg2);
2121 : }
2122 : }
2123 53823 : return cond;
2124 : }
2125 :
2126 : /* Structure used to track meta-data on PHI arguments used to generate
2127 : most efficient comparison sequence to slatten a PHI node. */
2128 :
2129 : typedef struct ifcvt_arg_entry
2130 : {
2131 : /* The PHI node argument value. */
2132 : tree arg;
2133 :
2134 : /* The number of compares required to reach this PHI node from start of the
2135 : BB being if-converted. */
2136 : unsigned num_compares;
2137 :
2138 : /* The number of times this PHI node argument appears in the current PHI
2139 : node. */
2140 : unsigned occurs;
2141 :
2142 : /* The indices at which this PHI arg occurs inside the PHI node. */
2143 : vec <int> *indexes;
2144 : } ifcvt_arg_entry_t;
2145 :
2146 : /* Produce condition for all occurrences of ARG in PHI node. Set *INVERT
2147 : as to whether the condition is inverted. */
2148 :
2149 : static tree
2150 4253 : gen_phi_arg_condition (gphi *phi, ifcvt_arg_entry_t &arg,
2151 : gimple_stmt_iterator *gsi,
2152 : scalar_cond_masked_set_type &cond_set, bool *invert)
2153 : {
2154 4253 : int len;
2155 4253 : int i;
2156 4253 : tree cond = NULL_TREE;
2157 4253 : tree c;
2158 4253 : edge e;
2159 :
2160 4253 : *invert = false;
2161 4253 : len = arg.indexes->length ();
2162 4253 : gcc_assert (len > 0);
2163 8564 : for (i = 0; i < len; i++)
2164 : {
2165 4311 : e = gimple_phi_arg_edge (phi, (*arg.indexes)[i]);
2166 4311 : c = bb_predicate (e->src);
2167 4311 : if (is_true_predicate (c))
2168 : {
2169 0 : cond = c;
2170 0 : break;
2171 : }
2172 : /* If we have just a single inverted predicate, signal that and
2173 : instead invert the COND_EXPR arms. */
2174 4311 : if (len == 1 && TREE_CODE (c) == TRUTH_NOT_EXPR)
2175 : {
2176 93 : c = TREE_OPERAND (c, 0);
2177 93 : *invert = true;
2178 : }
2179 :
2180 4311 : c = gen_simplified_condition (c, cond_set);
2181 4311 : c = force_gimple_operand_gsi (gsi, unshare_expr (c),
2182 : true, NULL_TREE, true, GSI_SAME_STMT);
2183 4311 : if (cond != NULL_TREE)
2184 : {
2185 : /* Must build OR expression. */
2186 58 : cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
2187 58 : cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
2188 : NULL_TREE, true, GSI_SAME_STMT);
2189 : }
2190 : else
2191 : cond = c;
2192 :
2193 : /* Register the new possibly simplified conditional. When more than 2
2194 : entries in a phi node we chain entries in the false branch, so the
2195 : inverted condition is active. */
2196 4311 : scalar_cond_masked_key pred_cond ({ cond, 1 });
2197 4311 : if (!*invert)
2198 4218 : pred_cond.inverted_p = !pred_cond.inverted_p;
2199 4311 : cond_set.add (pred_cond);
2200 : }
2201 4253 : gcc_assert (cond != NULL_TREE);
2202 4253 : return cond;
2203 : }
2204 :
2205 : /* Factors out an operation from *ARG0 and *ARG1 and
2206 : create the new statement at GSI. *RES is the
2207 : result of that new statement. Update *ARG0 and *ARG1
2208 : and *RES to the new values if the factoring happened.
2209 : Loops until all of the factoring is completed. */
2210 :
2211 : static void
2212 44316 : factor_out_operators (tree *res, gimple_stmt_iterator *gsi,
2213 : tree *arg0, tree *arg1, gphi *phi)
2214 : {
2215 44316 : gimple_match_op arg0_op, arg1_op;
2216 44316 : bool repeated = false;
2217 :
2218 44909 : again:
2219 44909 : if (TREE_CODE (*arg0) != SSA_NAME || TREE_CODE (*arg1) != SSA_NAME)
2220 : return;
2221 :
2222 33228 : if (operand_equal_p (*arg0, *arg1))
2223 : return;
2224 :
2225 : /* If either args have > 1 use, then this transformation actually
2226 : increases the number of expressions evaluated at runtime. */
2227 33228 : if (repeated
2228 33228 : ? (!has_zero_uses (*arg0) || !has_zero_uses (*arg1))
2229 32687 : : (!has_single_use (*arg0) || !has_single_use (*arg1)))
2230 : return;
2231 :
2232 5291 : gimple *arg0_def_stmt = SSA_NAME_DEF_STMT (*arg0);
2233 5291 : if (!gimple_extract_op (arg0_def_stmt, &arg0_op))
2234 : return;
2235 :
2236 : /* Might pick up abnormals from previous bbs so stop the loop. */
2237 2013 : if (arg0_op.operands_occurs_in_abnormal_phi ())
2238 : return;
2239 :
2240 2011 : gimple *arg1_def_stmt = SSA_NAME_DEF_STMT (*arg1);
2241 2011 : if (!gimple_extract_op (arg1_def_stmt, &arg1_op))
2242 : return;
2243 :
2244 : /* Might pick up abnormals from previous bbs so stop the loop. */
2245 1692 : if (arg1_op.operands_occurs_in_abnormal_phi ())
2246 : return;
2247 :
2248 : /* No factoring can happen if the codes are different
2249 : or the number operands. */
2250 1692 : if (arg1_op.code != arg0_op.code
2251 1692 : || arg1_op.num_ops != arg0_op.num_ops)
2252 : return;
2253 :
2254 723 : tree new_arg0, new_arg1;
2255 723 : int opnum = find_different_opnum (arg0_op, arg1_op, &new_arg0, &new_arg1);
2256 723 : if (opnum == -1)
2257 : return;
2258 :
2259 614 : tree args[2] = { new_arg0, new_arg1 };
2260 614 : location_t locs[2];
2261 614 : locs[0] = gimple_location (arg0_def_stmt);
2262 614 : locs[1] = gimple_location (arg1_def_stmt);
2263 614 : if (!factor_operation_ok (arg1_op.code, opnum, args, locs, 2, true, true))
2264 : return;
2265 :
2266 593 : tree new_res = make_ssa_name (TREE_TYPE (new_arg0), NULL);
2267 :
2268 : /* Create the operation stmt if possible and insert it. */
2269 :
2270 593 : gimple_match_op new_op = arg0_op;
2271 593 : new_op.ops[opnum] = new_res;
2272 593 : gimple_seq seq = NULL;
2273 593 : tree result = *res;
2274 593 : result = maybe_push_res_to_seq (&new_op, &seq, result);
2275 :
2276 : /* If we can't create the new statement, release the temp name
2277 : and return back. */
2278 593 : if (!result)
2279 : {
2280 0 : release_ssa_name (new_res);
2281 0 : return;
2282 : }
2283 593 : gsi_insert_seq_before (gsi, seq, GSI_CONTINUE_LINKING);
2284 :
2285 593 : if (dump_file && (dump_flags & TDF_DETAILS))
2286 : {
2287 1 : fprintf (dump_file, "PHI ");
2288 1 : print_generic_expr (dump_file, gimple_phi_result (phi));
2289 1 : fprintf (dump_file,
2290 : " changed to factor operation out from COND_EXPR.\n");
2291 1 : fprintf (dump_file, "New stmt with OPERATION that defines ");
2292 1 : print_generic_expr (dump_file, result);
2293 1 : fprintf (dump_file, ".\n");
2294 : }
2295 :
2296 : /* Remove the old operation(s) that has single use. */
2297 593 : gimple_stmt_iterator gsi_for_def;
2298 :
2299 593 : gsi_for_def = gsi_for_stmt (arg0_def_stmt);
2300 593 : gsi_remove (&gsi_for_def, true);
2301 593 : release_defs (arg0_def_stmt);
2302 593 : gsi_for_def = gsi_for_stmt (arg1_def_stmt);
2303 593 : gsi_remove (&gsi_for_def, true);
2304 593 : release_defs (arg1_def_stmt);
2305 :
2306 : /* Update the arguments and try again. */
2307 593 : *arg0 = new_arg0;
2308 593 : *arg1 = new_arg1;
2309 593 : *res = new_res;
2310 :
2311 : /* Update the phi node too. */
2312 593 : gimple_phi_set_result (phi, new_res);
2313 593 : SET_PHI_ARG_DEF (phi, 0, new_arg0);
2314 593 : SET_PHI_ARG_DEF (phi, 1, new_arg1);
2315 593 : update_stmt (phi);
2316 :
2317 593 : repeated = true;
2318 593 : goto again;
2319 : }
2320 :
2321 : /* Create the smallest nested conditional possible. On pre-order we record
2322 : which conditionals are live, and on post-order rewrite the chain by removing
2323 : already active conditions.
2324 :
2325 : As an example we simplify:
2326 :
2327 : _7 = a_10 < 0;
2328 : _21 = a_10 >= 0;
2329 : _22 = a_10 < e_11(D);
2330 : _23 = _21 & _22;
2331 : _ifc__42 = _23 ? t_13 : 0;
2332 : t_6 = _7 ? 1 : _ifc__42
2333 :
2334 : into
2335 :
2336 : _7 = a_10 < 0;
2337 : _22 = a_10 < e_11(D);
2338 : _ifc__42 = _22 ? t_13 : 0;
2339 : t_6 = _7 ? 1 : _ifc__42;
2340 :
2341 : which produces better code. */
2342 :
2343 : static tree
2344 6377 : gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi,
2345 : scalar_cond_masked_set_type &cond_set, tree type,
2346 : gimple **res_stmt, tree lhs0,
2347 : vec<struct ifcvt_arg_entry> &args, unsigned idx)
2348 : {
2349 12754 : if (idx == args.length ())
2350 2124 : return args[idx - 1].arg;
2351 :
2352 4253 : bool invert;
2353 4253 : tree cond = gen_phi_arg_condition (phi, args[idx - 1], gsi, cond_set,
2354 : &invert);
2355 4253 : tree arg1 = gen_phi_nest_statement (phi, gsi, cond_set, type, res_stmt, lhs0,
2356 : args, idx + 1);
2357 :
2358 4253 : unsigned prev = idx;
2359 4253 : unsigned curr = prev - 1;
2360 4253 : tree arg0 = args[curr].arg;
2361 4253 : tree rhs, lhs;
2362 4253 : if (idx > 1)
2363 2129 : lhs = make_temp_ssa_name (type, NULL, "_ifc_");
2364 : else
2365 : lhs = lhs0;
2366 :
2367 4253 : if (invert)
2368 93 : rhs = fold_build_cond_expr (type, unshare_expr (cond),
2369 : arg1, arg0);
2370 : else
2371 4160 : rhs = fold_build_cond_expr (type, unshare_expr (cond),
2372 : arg0, arg1);
2373 4253 : gassign *new_stmt = gimple_build_assign (lhs, rhs);
2374 4253 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2375 4253 : update_stmt (new_stmt);
2376 4253 : *res_stmt = new_stmt;
2377 4253 : return lhs;
2378 : }
2379 :
2380 : /* When flattening a PHI node we have a choice of which conditions to test to
2381 : for all the paths from the start of the dominator block of the BB with the
2382 : PHI node. If the PHI node has X arguments we have to only test X - 1
2383 : conditions as the last one is implicit. It does matter which conditions we
2384 : test first. We should test the shortest condition first (distance here is
2385 : measures in the number of logical operators in the condition) and the
2386 : longest one last. This allows us to skip testing the most expensive
2387 : condition. To accomplish this we need to sort the conditions. P1 and P2
2388 : are sorted first based on the number of logical operations (num_compares)
2389 : and then by how often they occur in the PHI node. */
2390 :
2391 : static int
2392 36416 : cmp_arg_entry (const void *p1, const void *p2, void * /* data. */)
2393 : {
2394 36416 : const ifcvt_arg_entry sval1 = *(const ifcvt_arg_entry *)p1;
2395 36416 : const ifcvt_arg_entry sval2 = *(const ifcvt_arg_entry *)p2;
2396 :
2397 36416 : if (sval1.num_compares < sval2.num_compares)
2398 : return -1;
2399 12360 : else if (sval1.num_compares > sval2.num_compares)
2400 : return 1;
2401 :
2402 648 : if (sval1.occurs < sval2.occurs)
2403 : return -1;
2404 648 : else if (sval1.occurs > sval2.occurs)
2405 0 : return 1;
2406 :
2407 : return 0;
2408 : }
2409 :
2410 : /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
2411 : This routine can handle PHI nodes with more than two arguments.
2412 :
2413 : For example,
2414 : S1: A = PHI <x1(1), x2(5)>
2415 : is converted into,
2416 : S2: A = cond ? x1 : x2;
2417 :
2418 : The generated code is inserted at GSI that points to the top of
2419 : basic block's statement list.
2420 : If PHI node has more than two arguments a chain of conditional
2421 : expression is produced. */
2422 :
2423 :
2424 : static void
2425 49716 : predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
2426 : {
2427 49716 : gimple *new_stmt = NULL, *reduc, *nop_reduc;
2428 49716 : tree rhs, res, arg0, arg1, op0, op1, scev;
2429 49716 : tree cond;
2430 49716 : unsigned int index0;
2431 49716 : edge e;
2432 49716 : basic_block bb;
2433 49716 : unsigned int i;
2434 49716 : bool has_nop, intermediate;
2435 :
2436 49716 : res = gimple_phi_result (phi);
2437 99432 : if (virtual_operand_p (res))
2438 44375 : return;
2439 :
2440 49716 : if ((rhs = degenerate_phi_result (phi))
2441 49716 : || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
2442 : res))
2443 49674 : && !chrec_contains_undetermined (scev)
2444 49674 : && scev != res
2445 17 : && (rhs = gimple_phi_arg_def (phi, 0))))
2446 : {
2447 59 : if (dump_file && (dump_flags & TDF_DETAILS))
2448 : {
2449 0 : fprintf (dump_file, "Degenerate phi!\n");
2450 0 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
2451 : }
2452 59 : new_stmt = gimple_build_assign (res, rhs);
2453 59 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2454 59 : update_stmt (new_stmt);
2455 59 : return;
2456 : }
2457 :
2458 49657 : bb = gimple_bb (phi);
2459 : /* Keep track of conditionals already seen. */
2460 49657 : scalar_cond_masked_set_type cond_set;
2461 49657 : if (EDGE_COUNT (bb->preds) == 2)
2462 : {
2463 : /* Predicate ordinary PHI node with 2 arguments. */
2464 44316 : edge first_edge, second_edge;
2465 44316 : basic_block true_bb;
2466 44316 : first_edge = EDGE_PRED (bb, 0);
2467 44316 : second_edge = EDGE_PRED (bb, 1);
2468 44316 : cond = bb_predicate (first_edge->src);
2469 44316 : cond_set.add ({ cond, 1 });
2470 44316 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2471 22853 : std::swap (first_edge, second_edge);
2472 44316 : if (EDGE_COUNT (first_edge->src->succs) > 1)
2473 : {
2474 19675 : cond = bb_predicate (second_edge->src);
2475 19675 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2476 10489 : cond = TREE_OPERAND (cond, 0);
2477 : else
2478 : first_edge = second_edge;
2479 : }
2480 : else
2481 24641 : cond = bb_predicate (first_edge->src);
2482 :
2483 : /* Gimplify the condition to a valid cond-expr conditional operand. */
2484 44316 : cond = gen_simplified_condition (cond, cond_set);
2485 44316 : cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
2486 : NULL_TREE, true, GSI_SAME_STMT);
2487 44316 : true_bb = first_edge->src;
2488 44316 : if (EDGE_PRED (bb, 1)->src == true_bb)
2489 : {
2490 32039 : arg0 = gimple_phi_arg_def (phi, 1);
2491 32039 : arg1 = gimple_phi_arg_def (phi, 0);
2492 : }
2493 : else
2494 : {
2495 12277 : arg0 = gimple_phi_arg_def (phi, 0);
2496 12277 : arg1 = gimple_phi_arg_def (phi, 1);
2497 : }
2498 :
2499 : /* Factor out operand if possible. This can only be done easily
2500 : for PHI with 2 elements. */
2501 44316 : factor_out_operators (&res, gsi, &arg0, &arg1, phi);
2502 :
2503 44316 : if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
2504 : &op0, &op1, false, &has_nop,
2505 : &nop_reduc, &intermediate))
2506 : {
2507 : /* Convert reduction stmt into vectorizable form. */
2508 8462 : rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
2509 4231 : true_bb != gimple_bb (reduc),
2510 : has_nop, nop_reduc, intermediate);
2511 4231 : redundant_ssa_names.safe_push (std::make_pair (res, rhs));
2512 : }
2513 : else
2514 : /* Build new RHS using selected condition and arguments. */
2515 40085 : rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
2516 : arg0, arg1);
2517 44316 : new_stmt = gimple_build_assign (res, rhs);
2518 44316 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2519 44316 : gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt);
2520 44316 : if (fold_stmt (&new_gsi, follow_all_ssa_edges))
2521 : {
2522 1559 : new_stmt = gsi_stmt (new_gsi);
2523 1559 : update_stmt (new_stmt);
2524 : }
2525 :
2526 44316 : if (dump_file && (dump_flags & TDF_DETAILS))
2527 : {
2528 28 : fprintf (dump_file, "new phi replacement stmt\n");
2529 28 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
2530 : }
2531 44316 : return;
2532 : }
2533 :
2534 : /* Create hashmap for PHI node which contain vector of argument indexes
2535 : having the same value. */
2536 5341 : bool swap = false;
2537 5341 : hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
2538 5341 : unsigned int num_args = gimple_phi_num_args (phi);
2539 : /* Vector of different PHI argument values. */
2540 5341 : auto_vec<ifcvt_arg_entry_t> args;
2541 :
2542 : /* Compute phi_arg_map, determine the list of unique PHI args and the indices
2543 : where they are in the PHI node. The indices will be used to determine
2544 : the conditions to apply and their complexity. */
2545 21633 : for (i = 0; i < num_args; i++)
2546 : {
2547 16292 : tree arg;
2548 :
2549 16292 : arg = gimple_phi_arg_def (phi, i);
2550 16292 : if (!phi_arg_map.get (arg))
2551 12811 : args.safe_push ({ arg, 0, 0, NULL });
2552 16292 : phi_arg_map.get_or_insert (arg).safe_push (i);
2553 : }
2554 :
2555 : /* Determine element with max number of occurrences and complexity. Looking
2556 : at only number of occurrences as a measure for complexity isn't enough as
2557 : all usages can be unique but the comparisons to reach the PHI node differ
2558 : per branch. */
2559 18152 : for (unsigned i = 0; i < args.length (); i++)
2560 : {
2561 12811 : unsigned int len = 0;
2562 12811 : vec<int> *indices = phi_arg_map.get (args[i].arg);
2563 54725 : for (int index : *indices)
2564 : {
2565 16292 : edge e = gimple_phi_arg_edge (phi, index);
2566 16292 : len += get_bb_num_predicate_stmts (e->src);
2567 : }
2568 :
2569 12811 : unsigned occur = indices->length ();
2570 12811 : if (dump_file && (dump_flags & TDF_DETAILS))
2571 7 : fprintf (dump_file, "Ranking %d as len=%d, idx=%d\n", i, len, occur);
2572 12811 : args[i].num_compares = len;
2573 12811 : args[i].occurs = occur;
2574 12811 : args[i].indexes = indices;
2575 : }
2576 :
2577 : /* Sort elements based on rankings ARGS. */
2578 5341 : args.stablesort (cmp_arg_entry, NULL);
2579 :
2580 : /* Handle one special case when number of arguments with different values
2581 : is equal 2 and one argument has the only occurrence. Such PHI can be
2582 : handled as if would have only 2 arguments. */
2583 5341 : if (args.length () == 2
2584 8616 : && args[0].indexes->length () == 1)
2585 : {
2586 3217 : index0 = (*args[0].indexes)[0];
2587 3217 : arg0 = args[0].arg;
2588 3217 : arg1 = args[1].arg;
2589 3217 : e = gimple_phi_arg_edge (phi, index0);
2590 3217 : cond = bb_predicate (e->src);
2591 3217 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2592 : {
2593 36 : swap = true;
2594 36 : cond = TREE_OPERAND (cond, 0);
2595 : }
2596 : /* Gimplify the condition to a valid cond-expr conditional operand. */
2597 3217 : cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true,
2598 : NULL_TREE, true, GSI_SAME_STMT);
2599 3217 : if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
2600 : &op0, &op1, true, &has_nop, &nop_reduc,
2601 : &intermediate)))
2602 4484 : rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
2603 : swap ? arg1 : arg0,
2604 : swap ? arg0 : arg1);
2605 : else
2606 : {
2607 : /* Convert reduction stmt into vectorizable form. */
2608 958 : rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
2609 : swap, has_nop, nop_reduc,
2610 : intermediate);
2611 958 : redundant_ssa_names.safe_push (std::make_pair (res, rhs));
2612 : }
2613 3217 : new_stmt = gimple_build_assign (res, rhs);
2614 3217 : gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
2615 3217 : update_stmt (new_stmt);
2616 : }
2617 : else
2618 : {
2619 : /* Common case. */
2620 2124 : tree type = TREE_TYPE (gimple_phi_result (phi));
2621 2124 : gen_phi_nest_statement (phi, gsi, cond_set, type, &new_stmt, res,
2622 : args, 1);
2623 : }
2624 :
2625 5341 : if (dump_file && (dump_flags & TDF_DETAILS))
2626 : {
2627 3 : fprintf (dump_file, "new extended phi replacement stmt\n");
2628 3 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
2629 : }
2630 49657 : }
2631 :
2632 : /* Replaces in LOOP all the scalar phi nodes other than those in the
2633 : LOOP->header block with conditional modify expressions. */
2634 :
2635 : static void
2636 25714 : predicate_all_scalar_phis (class loop *loop)
2637 : {
2638 25714 : basic_block bb;
2639 25714 : unsigned int orig_loop_num_nodes = loop->num_nodes;
2640 25714 : unsigned int i;
2641 :
2642 135159 : for (i = 1; i < orig_loop_num_nodes; i++)
2643 : {
2644 109445 : gphi *phi;
2645 109445 : gimple_stmt_iterator gsi;
2646 109445 : gphi_iterator phi_gsi;
2647 109445 : bb = ifc_bbs[i];
2648 :
2649 109445 : if (bb == loop->header)
2650 78608 : continue;
2651 :
2652 109445 : phi_gsi = gsi_start_phis (bb);
2653 109445 : if (gsi_end_p (phi_gsi))
2654 78608 : continue;
2655 :
2656 30837 : gsi = gsi_after_labels (bb);
2657 82907 : while (!gsi_end_p (phi_gsi))
2658 : {
2659 52070 : phi = phi_gsi.phi ();
2660 104140 : if (virtual_operand_p (gimple_phi_result (phi)))
2661 2354 : gsi_next (&phi_gsi);
2662 : else
2663 : {
2664 49716 : predicate_scalar_phi (phi, &gsi);
2665 49716 : remove_phi_node (&phi_gsi, false);
2666 : }
2667 : }
2668 : }
2669 25714 : }
2670 :
2671 : /* Insert in each basic block of LOOP the statements produced by the
2672 : gimplification of the predicates. */
2673 :
2674 : static void
2675 25714 : insert_gimplified_predicates (loop_p loop)
2676 : {
2677 25714 : unsigned int i;
2678 :
2679 160873 : for (i = 0; i < loop->num_nodes; i++)
2680 : {
2681 135159 : basic_block bb = ifc_bbs[i];
2682 135159 : gimple_seq stmts;
2683 135159 : if (!is_predicated (bb))
2684 81250 : gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
2685 135159 : if (!is_predicated (bb))
2686 : {
2687 : /* Do not insert statements for a basic block that is not
2688 : predicated. Also make sure that the predicate of the
2689 : basic block is set to true. */
2690 81250 : reset_bb_predicate (bb);
2691 81250 : continue;
2692 : }
2693 :
2694 53909 : stmts = bb_predicate_gimplified_stmts (bb);
2695 53909 : if (stmts)
2696 : {
2697 53501 : if (need_to_predicate)
2698 : {
2699 : /* Insert the predicate of the BB just after the label,
2700 : as the if-conversion of memory writes will use this
2701 : predicate. */
2702 5783 : gimple_stmt_iterator gsi = gsi_after_labels (bb);
2703 5783 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2704 : }
2705 : else
2706 : {
2707 : /* Insert the predicate of the BB at the end of the BB
2708 : as this would reduce the register pressure: the only
2709 : use of this predicate will be in successor BBs. */
2710 47718 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2711 :
2712 47718 : if (gsi_end_p (gsi)
2713 47718 : || stmt_ends_bb_p (gsi_stmt (gsi)))
2714 25386 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2715 : else
2716 22332 : gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
2717 : }
2718 :
2719 : /* Once the sequence is code generated, set it to NULL. */
2720 135159 : set_bb_predicate_gimplified_stmts (bb, NULL, true);
2721 : }
2722 : }
2723 25714 : }
2724 :
2725 : /* Helper function for predicate_statements. Returns index of existent
2726 : mask if it was created for given SIZE and -1 otherwise. */
2727 :
2728 : static int
2729 966 : mask_exists (int size, const vec<int> &vec)
2730 : {
2731 966 : unsigned int ix;
2732 966 : int v;
2733 1055 : FOR_EACH_VEC_ELT (vec, ix, v)
2734 994 : if (v == size)
2735 905 : return (int) ix;
2736 : return -1;
2737 : }
2738 :
2739 : /* Helper function for predicate_statements. STMT is a memory read or
2740 : write and it needs to be predicated by MASK. Return a statement
2741 : that does so. */
2742 :
2743 : static gimple *
2744 2002 : predicate_load_or_store (gimple_stmt_iterator *gsi, gassign *stmt, tree mask)
2745 : {
2746 2002 : gcall *new_stmt;
2747 :
2748 2002 : tree lhs = gimple_assign_lhs (stmt);
2749 2002 : tree rhs = gimple_assign_rhs1 (stmt);
2750 2002 : tree ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
2751 2002 : mark_addressable (ref);
2752 2002 : tree addr = force_gimple_operand_gsi (gsi, build_fold_addr_expr (ref),
2753 : true, NULL_TREE, true, GSI_SAME_STMT);
2754 2002 : tree ptr = build_int_cst (reference_alias_ptr_type (ref),
2755 2002 : get_object_alignment (ref));
2756 : /* Copy points-to info if possible. */
2757 3403 : if (TREE_CODE (addr) == SSA_NAME && !ssa_name_pt_solution (addr))
2758 600 : copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
2759 : ref);
2760 2002 : if (TREE_CODE (lhs) == SSA_NAME)
2761 : {
2762 : /* Get a zero else value. This might not be what a target actually uses
2763 : but we cannot be sure about which vector mode the vectorizer will
2764 : choose. Therefore, leave the decision whether we need to force the
2765 : inactive elements to zero to the vectorizer. */
2766 1161 : tree els = vect_get_mask_load_else (MASK_LOAD_ELSE_ZERO,
2767 1161 : TREE_TYPE (lhs));
2768 :
2769 1161 : new_stmt
2770 1161 : = gimple_build_call_internal (IFN_MASK_LOAD, 4, addr,
2771 : ptr, mask, els);
2772 :
2773 1161 : gimple_call_set_lhs (new_stmt, lhs);
2774 2322 : gimple_set_vuse (new_stmt, gimple_vuse (stmt));
2775 : }
2776 : else
2777 : {
2778 841 : new_stmt
2779 841 : = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
2780 : mask, rhs);
2781 841 : gimple_move_vops (new_stmt, stmt);
2782 : }
2783 2002 : gimple_call_set_nothrow (new_stmt, true);
2784 2002 : return new_stmt;
2785 : }
2786 :
2787 : /* STMT uses OP_LHS. Check whether it is equivalent to:
2788 :
2789 : ... = OP_MASK ? OP_LHS : X;
2790 :
2791 : Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is
2792 : known to have value OP_COND. */
2793 :
2794 : static tree
2795 879 : check_redundant_cond_expr (gimple *stmt, tree op_mask, tree op_cond,
2796 : tree op_lhs)
2797 : {
2798 879 : gassign *assign = dyn_cast <gassign *> (stmt);
2799 1089 : if (!assign || gimple_assign_rhs_code (assign) != COND_EXPR)
2800 : return NULL_TREE;
2801 :
2802 230 : tree use_cond = gimple_assign_rhs1 (assign);
2803 230 : tree if_true = gimple_assign_rhs2 (assign);
2804 230 : tree if_false = gimple_assign_rhs3 (assign);
2805 :
2806 71 : if ((use_cond == op_mask || operand_equal_p (use_cond, op_cond, 0))
2807 230 : && if_true == op_lhs)
2808 : return if_false;
2809 :
2810 71 : if (inverse_conditions_p (use_cond, op_cond) && if_false == op_lhs)
2811 0 : return if_true;
2812 :
2813 : return NULL_TREE;
2814 : }
2815 :
2816 : /* Return true if VALUE is available for use at STMT. SSA_NAMES is
2817 : the set of SSA names defined earlier in STMT's block. */
2818 :
2819 : static bool
2820 159 : value_available_p (gimple *stmt, hash_set<tree_ssa_name_hash> *ssa_names,
2821 : tree value)
2822 : {
2823 159 : if (is_gimple_min_invariant (value))
2824 : return true;
2825 :
2826 115 : if (TREE_CODE (value) == SSA_NAME)
2827 : {
2828 115 : if (SSA_NAME_IS_DEFAULT_DEF (value))
2829 : return true;
2830 :
2831 107 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
2832 107 : basic_block use_bb = gimple_bb (stmt);
2833 107 : return (def_bb == use_bb
2834 107 : ? ssa_names->contains (value)
2835 107 : : dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
2836 : }
2837 :
2838 : return false;
2839 : }
2840 :
2841 : /* Helper function for predicate_statements. STMT is a potentially-trapping
2842 : arithmetic operation that needs to be predicated by MASK, an SSA_NAME that
2843 : has value COND. Return a statement that does so. SSA_NAMES is the set of
2844 : SSA names defined earlier in STMT's block. */
2845 :
2846 : static gimple *
2847 674 : predicate_rhs_code (gimple *stmt, tree mask, tree cond,
2848 : hash_set<tree_ssa_name_hash> *ssa_names)
2849 : {
2850 674 : internal_fn cond_fn;
2851 674 : if (is_gimple_assign (stmt))
2852 : {
2853 566 : tree_code code = gimple_assign_rhs_code (stmt);
2854 566 : cond_fn = get_conditional_internal_fn (code);
2855 : }
2856 108 : else if (tree callee = gimple_call_fndecl (stmt))
2857 : {
2858 108 : auto ifn = associated_internal_fn (callee);
2859 108 : cond_fn = get_conditional_internal_fn (ifn);
2860 : }
2861 : else
2862 : return NULL;
2863 :
2864 674 : if (cond_fn == IFN_LAST)
2865 : {
2866 0 : gcc_assert (!gimple_could_trap_p (stmt));
2867 : return NULL;
2868 : }
2869 :
2870 674 : tree lhs = gimple_get_lhs (stmt);
2871 674 : unsigned int nops = gimple_num_args (stmt) + 1;
2872 :
2873 : /* Construct the arguments to the conditional internal function. */
2874 674 : auto_vec<tree, 8> args;
2875 674 : args.safe_grow (nops + 1, true);
2876 674 : args[0] = mask;
2877 2130 : for (unsigned int i = 0; i < nops - 1; ++i)
2878 1456 : args[i+1] = gimple_arg (stmt, i);
2879 674 : args[nops] = NULL_TREE;
2880 :
2881 : /* Look for uses of the result to see whether they are COND_EXPRs that can
2882 : be folded into the conditional call. */
2883 674 : imm_use_iterator imm_iter;
2884 674 : gimple *use_stmt;
2885 1553 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
2886 : {
2887 879 : tree new_else = check_redundant_cond_expr (use_stmt, mask, cond, lhs);
2888 879 : if (new_else && value_available_p (stmt, ssa_names, new_else))
2889 : {
2890 138 : if (!args[nops])
2891 138 : args[nops] = new_else;
2892 138 : if (operand_equal_p (new_else, args[nops], 0))
2893 : {
2894 : /* We have:
2895 :
2896 : LHS = IFN_COND (MASK, ..., ELSE);
2897 : X = MASK ? LHS : ELSE;
2898 :
2899 : which makes X equivalent to LHS. */
2900 138 : tree use_lhs = gimple_assign_lhs (use_stmt);
2901 138 : redundant_ssa_names.safe_push (std::make_pair (use_lhs, lhs));
2902 : }
2903 : }
2904 674 : }
2905 674 : if (!args[nops])
2906 1072 : args[nops] = targetm.preferred_else_value (cond_fn, TREE_TYPE (lhs),
2907 536 : nops - 1, &args[1]);
2908 :
2909 : /* Create and insert the call. */
2910 674 : gcall *new_stmt = gimple_build_call_internal_vec (cond_fn, args);
2911 674 : gimple_call_set_lhs (new_stmt, lhs);
2912 674 : gimple_call_set_nothrow (new_stmt, true);
2913 :
2914 674 : return new_stmt;
2915 674 : }
2916 :
2917 : /* Predicate each write to memory in LOOP.
2918 :
2919 : This function transforms control flow constructs containing memory
2920 : writes of the form:
2921 :
2922 : | for (i = 0; i < N; i++)
2923 : | if (cond)
2924 : | A[i] = expr;
2925 :
2926 : into the following form that does not contain control flow:
2927 :
2928 : | for (i = 0; i < N; i++)
2929 : | A[i] = cond ? expr : A[i];
2930 :
2931 : The original CFG looks like this:
2932 :
2933 : | bb_0
2934 : | i = 0
2935 : | end_bb_0
2936 : |
2937 : | bb_1
2938 : | if (i < N) goto bb_5 else goto bb_2
2939 : | end_bb_1
2940 : |
2941 : | bb_2
2942 : | cond = some_computation;
2943 : | if (cond) goto bb_3 else goto bb_4
2944 : | end_bb_2
2945 : |
2946 : | bb_3
2947 : | A[i] = expr;
2948 : | goto bb_4
2949 : | end_bb_3
2950 : |
2951 : | bb_4
2952 : | goto bb_1
2953 : | end_bb_4
2954 :
2955 : insert_gimplified_predicates inserts the computation of the COND
2956 : expression at the beginning of the destination basic block:
2957 :
2958 : | bb_0
2959 : | i = 0
2960 : | end_bb_0
2961 : |
2962 : | bb_1
2963 : | if (i < N) goto bb_5 else goto bb_2
2964 : | end_bb_1
2965 : |
2966 : | bb_2
2967 : | cond = some_computation;
2968 : | if (cond) goto bb_3 else goto bb_4
2969 : | end_bb_2
2970 : |
2971 : | bb_3
2972 : | cond = some_computation;
2973 : | A[i] = expr;
2974 : | goto bb_4
2975 : | end_bb_3
2976 : |
2977 : | bb_4
2978 : | goto bb_1
2979 : | end_bb_4
2980 :
2981 : predicate_statements is then predicating the memory write as follows:
2982 :
2983 : | bb_0
2984 : | i = 0
2985 : | end_bb_0
2986 : |
2987 : | bb_1
2988 : | if (i < N) goto bb_5 else goto bb_2
2989 : | end_bb_1
2990 : |
2991 : | bb_2
2992 : | if (cond) goto bb_3 else goto bb_4
2993 : | end_bb_2
2994 : |
2995 : | bb_3
2996 : | cond = some_computation;
2997 : | A[i] = cond ? expr : A[i];
2998 : | goto bb_4
2999 : | end_bb_3
3000 : |
3001 : | bb_4
3002 : | goto bb_1
3003 : | end_bb_4
3004 :
3005 : and finally combine_blocks removes the basic block boundaries making
3006 : the loop vectorizable:
3007 :
3008 : | bb_0
3009 : | i = 0
3010 : | if (i < N) goto bb_5 else goto bb_1
3011 : | end_bb_0
3012 : |
3013 : | bb_1
3014 : | cond = some_computation;
3015 : | A[i] = cond ? expr : A[i];
3016 : | if (i < N) goto bb_5 else goto bb_4
3017 : | end_bb_1
3018 : |
3019 : | bb_4
3020 : | goto bb_1
3021 : | end_bb_4
3022 : */
3023 :
3024 : static void
3025 12179 : predicate_statements (loop_p loop)
3026 : {
3027 12179 : unsigned int i, orig_loop_num_nodes = loop->num_nodes;
3028 12179 : auto_vec<int, 1> vect_sizes;
3029 12179 : auto_vec<tree, 1> vect_masks;
3030 12179 : hash_set<tree_ssa_name_hash> ssa_names;
3031 :
3032 76015 : for (i = 1; i < orig_loop_num_nodes; i++)
3033 : {
3034 51657 : gimple_stmt_iterator gsi;
3035 51657 : basic_block bb = ifc_bbs[i];
3036 51657 : tree cond = bb_predicate (bb);
3037 51657 : bool swap;
3038 51657 : int index;
3039 :
3040 51657 : if (is_true_predicate (cond))
3041 25680 : continue;
3042 :
3043 25977 : swap = false;
3044 25977 : if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
3045 : {
3046 9913 : swap = true;
3047 9913 : cond = TREE_OPERAND (cond, 0);
3048 : }
3049 :
3050 25977 : vect_sizes.truncate (0);
3051 25977 : vect_masks.truncate (0);
3052 :
3053 201986 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
3054 : {
3055 150032 : gimple *stmt = gsi_stmt (gsi);
3056 150032 : if (!is_gimple_assign (stmt)
3057 150032 : && !gimple_call_builtin_p (stmt))
3058 : ;
3059 92118 : else if (is_false_predicate (cond)
3060 92118 : && gimple_vdef (stmt))
3061 : {
3062 0 : unlink_stmt_vdef (stmt);
3063 0 : gsi_remove (&gsi, true);
3064 0 : release_defs (stmt);
3065 2 : continue;
3066 : }
3067 : /* For now, just drop prefetches. Do it now to remove any possible
3068 : aliasing check failures from the address calculations of the
3069 : prefetch. Vect would be too late in that regard. */
3070 92118 : else if (gimple_call_builtin_p (stmt, BUILT_IN_PREFETCH))
3071 : {
3072 2 : unlink_stmt_vdef (stmt);
3073 2 : gsi_remove (&gsi, true);
3074 2 : release_defs (stmt);
3075 2 : continue;
3076 : }
3077 92116 : else if (gimple_plf (stmt, GF_PLF_2)
3078 92116 : && (is_gimple_assign (stmt)
3079 108 : || (gimple_call_builtin_p (stmt)
3080 108 : && !if_convertible_simdclone_stmt_p (stmt))))
3081 : {
3082 2676 : tree lhs = gimple_get_lhs (stmt);
3083 : /* ?? Assume that calls without an LHS are not data processing
3084 : and so no issues with traps. */
3085 2676 : if (!lhs)
3086 0 : continue;
3087 2676 : tree mask;
3088 2676 : gimple *new_stmt;
3089 2676 : gimple_seq stmts = NULL;
3090 2676 : machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
3091 : /* We checked before setting GF_PLF_2 that an equivalent
3092 : integer mode exists. */
3093 2676 : int bitsize = GET_MODE_BITSIZE (mode).to_constant ();
3094 2676 : if (!vect_sizes.is_empty ()
3095 966 : && (index = mask_exists (bitsize, vect_sizes)) != -1)
3096 : /* Use created mask. */
3097 905 : mask = vect_masks[index];
3098 : else
3099 : {
3100 1771 : if (COMPARISON_CLASS_P (cond))
3101 0 : mask = gimple_build (&stmts, TREE_CODE (cond),
3102 : boolean_type_node,
3103 0 : TREE_OPERAND (cond, 0),
3104 0 : TREE_OPERAND (cond, 1));
3105 : else
3106 : mask = cond;
3107 :
3108 1771 : if (swap)
3109 : {
3110 391 : tree true_val
3111 391 : = constant_boolean_node (true, TREE_TYPE (mask));
3112 391 : mask = gimple_build (&stmts, BIT_XOR_EXPR,
3113 391 : TREE_TYPE (mask), mask, true_val);
3114 : }
3115 1771 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
3116 :
3117 : /* Save mask and its size for further use. */
3118 1771 : vect_sizes.safe_push (bitsize);
3119 1771 : vect_masks.safe_push (mask);
3120 : }
3121 2676 : if (gimple_assign_single_p (stmt))
3122 2002 : new_stmt = predicate_load_or_store (&gsi,
3123 : as_a <gassign *> (stmt),
3124 : mask);
3125 : else
3126 674 : new_stmt = predicate_rhs_code (stmt, mask, cond, &ssa_names);
3127 :
3128 2676 : if (new_stmt)
3129 2676 : gsi_replace (&gsi, new_stmt, true);
3130 : }
3131 89440 : else if (gimple_needing_rewrite_undefined (stmt))
3132 18536 : rewrite_to_defined_unconditional (&gsi);
3133 141808 : else if (gimple_vdef (stmt))
3134 : {
3135 1381 : tree lhs = gimple_assign_lhs (stmt);
3136 1381 : tree rhs = gimple_assign_rhs1 (stmt);
3137 1381 : tree type = TREE_TYPE (lhs);
3138 :
3139 1381 : lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
3140 1381 : rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
3141 1381 : if (swap)
3142 481 : std::swap (lhs, rhs);
3143 1381 : cond = force_gimple_operand_gsi (&gsi, unshare_expr (cond), true,
3144 : NULL_TREE, true, GSI_SAME_STMT);
3145 1381 : rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
3146 1381 : gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
3147 1381 : update_stmt (stmt);
3148 : }
3149 :
3150 150030 : if (gimple_plf (gsi_stmt (gsi), GF_PLF_2)
3151 150030 : && is_gimple_call (gsi_stmt (gsi)))
3152 : {
3153 : /* Convert functions that have a SIMD clone to IFN_MASK_CALL.
3154 : This will cause the vectorizer to match the "in branch"
3155 : clone variants, and serves to build the mask vector
3156 : in a natural way. */
3157 1007 : tree mask = cond;
3158 1007 : gcall *call = dyn_cast <gcall *> (gsi_stmt (gsi));
3159 1007 : tree orig_fn = gimple_call_fn (call);
3160 1007 : int orig_nargs = gimple_call_num_args (call);
3161 1007 : auto_vec<tree> args;
3162 1007 : args.safe_push (orig_fn);
3163 3036 : for (int i = 0; i < orig_nargs; i++)
3164 1022 : args.safe_push (gimple_call_arg (call, i));
3165 : /* If `swap', we invert the mask used for the if branch for use
3166 : when masking the function call. */
3167 1007 : if (swap)
3168 : {
3169 948 : gimple_seq stmts = NULL;
3170 948 : tree true_val
3171 948 : = constant_boolean_node (true, TREE_TYPE (mask));
3172 948 : mask = gimple_build (&stmts, BIT_XOR_EXPR,
3173 948 : TREE_TYPE (mask), mask, true_val);
3174 948 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
3175 : }
3176 1007 : args.safe_push (mask);
3177 :
3178 : /* Replace the call with a IFN_MASK_CALL that has the extra
3179 : condition parameter. */
3180 1007 : gcall *new_call = gimple_build_call_internal_vec (IFN_MASK_CALL,
3181 : args);
3182 1007 : gimple_call_set_lhs (new_call, gimple_call_lhs (call));
3183 1007 : gsi_replace (&gsi, new_call, true);
3184 1007 : }
3185 :
3186 150030 : tree lhs = gimple_get_lhs (gsi_stmt (gsi));
3187 150030 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
3188 90003 : ssa_names.add (lhs);
3189 150030 : gsi_next (&gsi);
3190 : }
3191 51932 : ssa_names.empty ();
3192 : }
3193 12179 : }
3194 :
3195 : /* Remove all GIMPLE_CONDs and GIMPLE_LABELs and GIMPLE_SWITCH of all
3196 : the basic blocks other than the exit and latch of the LOOP. Also
3197 : resets the GIMPLE_DEBUG information. */
3198 :
3199 : static void
3200 25714 : remove_conditions_and_labels (loop_p loop)
3201 : {
3202 25714 : gimple_stmt_iterator gsi;
3203 25714 : unsigned int i;
3204 :
3205 160873 : for (i = 0; i < loop->num_nodes; i++)
3206 : {
3207 135159 : basic_block bb = ifc_bbs[i];
3208 :
3209 135159 : if (bb_with_exit_edge_p (loop, bb)
3210 135159 : || bb == loop->latch)
3211 51428 : continue;
3212 :
3213 713488 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
3214 546026 : switch (gimple_code (gsi_stmt (gsi)))
3215 : {
3216 33793 : case GIMPLE_COND:
3217 33793 : case GIMPLE_LABEL:
3218 33793 : case GIMPLE_SWITCH:
3219 33793 : gsi_remove (&gsi, true);
3220 33793 : break;
3221 :
3222 345137 : case GIMPLE_DEBUG:
3223 : /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
3224 345137 : if (gimple_debug_bind_p (gsi_stmt (gsi)))
3225 : {
3226 276027 : gimple_debug_bind_reset_value (gsi_stmt (gsi));
3227 276027 : update_stmt (gsi_stmt (gsi));
3228 : }
3229 345137 : gsi_next (&gsi);
3230 345137 : break;
3231 :
3232 167096 : default:
3233 167096 : gsi_next (&gsi);
3234 : }
3235 : }
3236 25714 : }
3237 :
3238 : /* Combine all the basic blocks from LOOP into one or two super basic
3239 : blocks. Replace PHI nodes with conditional modify expressions. */
3240 :
3241 : static void
3242 25714 : combine_blocks (class loop *loop)
3243 : {
3244 25714 : basic_block bb, exit_bb, merge_target_bb;
3245 25714 : unsigned int orig_loop_num_nodes = loop->num_nodes;
3246 25714 : unsigned int i;
3247 25714 : edge e;
3248 25714 : edge_iterator ei;
3249 :
3250 : /* Reset flow-sensitive info before predicating stmts or PHIs we
3251 : might fold. */
3252 160873 : for (i = 0; i < orig_loop_num_nodes; i++)
3253 : {
3254 135159 : bb = ifc_bbs[i];
3255 135159 : if (is_predicated (bb))
3256 : {
3257 53909 : for (auto gsi = gsi_start_phis (bb);
3258 55471 : !gsi_end_p (gsi); gsi_next (&gsi))
3259 1562 : reset_flow_sensitive_info (gimple_phi_result (*gsi));
3260 228051 : for (auto gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3261 : {
3262 120233 : gimple *stmt = gsi_stmt (gsi);
3263 120233 : ssa_op_iter i;
3264 120233 : tree op;
3265 171805 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
3266 51572 : reset_flow_sensitive_info (op);
3267 : }
3268 : }
3269 : }
3270 :
3271 25714 : remove_conditions_and_labels (loop);
3272 25714 : insert_gimplified_predicates (loop);
3273 25714 : predicate_all_scalar_phis (loop);
3274 :
3275 25714 : if (need_to_predicate || need_to_rewrite_undefined)
3276 12179 : predicate_statements (loop);
3277 :
3278 : /* Merge basic blocks. */
3279 25714 : exit_bb = single_exit (loop)->src;
3280 25714 : gcc_assert (exit_bb != loop->latch);
3281 160873 : for (i = 0; i < orig_loop_num_nodes; i++)
3282 : {
3283 135159 : bb = ifc_bbs[i];
3284 135159 : free_bb_predicate (bb);
3285 : }
3286 :
3287 25714 : merge_target_bb = loop->header;
3288 :
3289 : /* Get at the virtual def valid for uses starting at the first block
3290 : we merge into the header. Without a virtual PHI the loop has the
3291 : same virtual use on all stmts. */
3292 25714 : gphi *vphi = get_virtual_phi (loop->header);
3293 25714 : tree last_vdef = NULL_TREE;
3294 25714 : if (vphi)
3295 : {
3296 13805 : last_vdef = gimple_phi_result (vphi);
3297 27610 : for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header);
3298 237291 : ! gsi_end_p (gsi); gsi_next (&gsi))
3299 287548 : if (gimple_vdef (gsi_stmt (gsi)))
3300 223486 : last_vdef = gimple_vdef (gsi_stmt (gsi));
3301 : }
3302 135159 : for (i = 1; i < orig_loop_num_nodes; i++)
3303 : {
3304 109445 : gimple_stmt_iterator gsi;
3305 109445 : gimple_stmt_iterator last;
3306 :
3307 109445 : bb = ifc_bbs[i];
3308 :
3309 109445 : if (bb == exit_bb || bb == loop->latch)
3310 51428 : continue;
3311 :
3312 : /* We release virtual PHIs late because we have to propagate them
3313 : out using the current VUSE. The def might be the one used
3314 : after the loop. */
3315 58017 : vphi = get_virtual_phi (bb);
3316 58017 : if (vphi)
3317 : {
3318 : /* When there's just loads inside the loop a stray virtual
3319 : PHI merging the uses can appear, update last_vdef from
3320 : it. */
3321 674 : if (!last_vdef)
3322 0 : last_vdef = gimple_phi_arg_def (vphi, 0);
3323 674 : imm_use_iterator iter;
3324 674 : use_operand_p use_p;
3325 674 : gimple *use_stmt;
3326 2349 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
3327 : {
3328 3356 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3329 1678 : SET_USE (use_p, last_vdef);
3330 674 : }
3331 674 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
3332 0 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
3333 674 : gsi = gsi_for_stmt (vphi);
3334 674 : remove_phi_node (&gsi, true);
3335 : }
3336 :
3337 : /* Make stmts member of loop->header and clear range info from all stmts
3338 : in BB which is now no longer executed conditional on a predicate we
3339 : could have derived it from. */
3340 381522 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3341 : {
3342 265488 : gimple *stmt = gsi_stmt (gsi);
3343 265488 : gimple_set_bb (stmt, merge_target_bb);
3344 : /* Update virtual operands. */
3345 265488 : if (last_vdef)
3346 : {
3347 204930 : use_operand_p use_p = ssa_vuse_operand (stmt);
3348 14426 : if (use_p
3349 14426 : && USE_FROM_PTR (use_p) != last_vdef)
3350 522 : SET_USE (use_p, last_vdef);
3351 617039 : if (gimple_vdef (stmt))
3352 : last_vdef = gimple_vdef (stmt);
3353 : }
3354 : else
3355 : /* If this is the first load we arrive at update last_vdef
3356 : so we handle stray PHIs correctly. */
3357 306584 : last_vdef = gimple_vuse (stmt);
3358 : }
3359 :
3360 : /* Update stmt list. */
3361 58017 : last = gsi_last_bb (merge_target_bb);
3362 116034 : gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT);
3363 58017 : set_bb_seq (bb, NULL);
3364 : }
3365 :
3366 : /* Fixup virtual operands in the exit block. */
3367 25714 : if (exit_bb
3368 25714 : && exit_bb != loop->header)
3369 : {
3370 : /* We release virtual PHIs late because we have to propagate them
3371 : out using the current VUSE. The def might be the one used
3372 : after the loop. */
3373 25714 : vphi = get_virtual_phi (exit_bb);
3374 25714 : if (vphi)
3375 : {
3376 : /* When there's just loads inside the loop a stray virtual
3377 : PHI merging the uses can appear, update last_vdef from
3378 : it. */
3379 1680 : if (!last_vdef)
3380 0 : last_vdef = gimple_phi_arg_def (vphi, 0);
3381 1680 : imm_use_iterator iter;
3382 1680 : use_operand_p use_p;
3383 1680 : gimple *use_stmt;
3384 5034 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
3385 : {
3386 6708 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3387 3354 : SET_USE (use_p, last_vdef);
3388 1680 : }
3389 1680 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
3390 0 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
3391 1680 : gimple_stmt_iterator gsi = gsi_for_stmt (vphi);
3392 1680 : remove_phi_node (&gsi, true);
3393 : }
3394 : }
3395 :
3396 : /* Now remove all the edges in the loop, except for those from the exit
3397 : block and delete the blocks we elided. */
3398 135159 : for (i = 1; i < orig_loop_num_nodes; i++)
3399 : {
3400 109445 : bb = ifc_bbs[i];
3401 :
3402 252301 : for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
3403 : {
3404 142856 : if (e->src == exit_bb)
3405 25714 : ei_next (&ei);
3406 : else
3407 117142 : remove_edge (e);
3408 : }
3409 : }
3410 135159 : for (i = 1; i < orig_loop_num_nodes; i++)
3411 : {
3412 109445 : bb = ifc_bbs[i];
3413 :
3414 109445 : if (bb == exit_bb || bb == loop->latch)
3415 51428 : continue;
3416 :
3417 58017 : delete_basic_block (bb);
3418 : }
3419 :
3420 : /* Re-connect the exit block. */
3421 25714 : if (exit_bb != NULL)
3422 : {
3423 25714 : if (exit_bb != loop->header)
3424 : {
3425 : /* Connect this node to loop header. */
3426 25714 : make_single_succ_edge (loop->header, exit_bb, EDGE_FALLTHRU);
3427 25714 : set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
3428 : }
3429 :
3430 : /* Redirect non-exit edges to loop->latch. */
3431 77142 : FOR_EACH_EDGE (e, ei, exit_bb->succs)
3432 : {
3433 51428 : if (!loop_exit_edge_p (loop, e))
3434 25714 : redirect_edge_and_branch (e, loop->latch);
3435 : }
3436 25714 : set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
3437 : }
3438 : else
3439 : {
3440 : /* If the loop does not have an exit, reconnect header and latch. */
3441 0 : make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
3442 0 : set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
3443 : }
3444 :
3445 : /* If possible, merge loop header to the block with the exit edge.
3446 : This reduces the number of basic blocks to two, to please the
3447 : vectorizer that handles only loops with two nodes. */
3448 25714 : if (exit_bb
3449 25714 : && exit_bb != loop->header)
3450 : {
3451 25714 : if (can_merge_blocks_p (loop->header, exit_bb))
3452 25712 : merge_blocks (loop->header, exit_bb);
3453 : }
3454 :
3455 25714 : free (ifc_bbs);
3456 25714 : ifc_bbs = NULL;
3457 25714 : }
3458 :
3459 : /* Version LOOP before if-converting it; the original loop
3460 : will be if-converted, the new copy of the loop will not,
3461 : and the LOOP_VECTORIZED internal call will be guarding which
3462 : loop to execute. The vectorizer pass will fold this
3463 : internal call into either true or false.
3464 :
3465 : Note that this function intentionally invalidates profile. Both edges
3466 : out of LOOP_VECTORIZED must have 100% probability so the profile remains
3467 : consistent after the condition is folded in the vectorizer. */
3468 :
3469 : static class loop *
3470 25979 : version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds)
3471 : {
3472 25979 : basic_block cond_bb;
3473 25979 : tree cond = make_ssa_name (boolean_type_node);
3474 25979 : class loop *new_loop;
3475 25979 : gimple *g;
3476 25979 : gimple_stmt_iterator gsi;
3477 25979 : unsigned int save_length = 0;
3478 :
3479 25979 : g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
3480 25979 : build_int_cst (integer_type_node, loop->num),
3481 : integer_zero_node);
3482 25979 : gimple_call_set_lhs (g, cond);
3483 :
3484 25979 : void **saved_preds = NULL;
3485 25979 : if (any_complicated_phi || need_to_predicate)
3486 : {
3487 : /* Save BB->aux around loop_version as that uses the same field. */
3488 3424 : save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes;
3489 3424 : saved_preds = XALLOCAVEC (void *, save_length);
3490 26037 : for (unsigned i = 0; i < save_length; i++)
3491 22613 : saved_preds[i] = ifc_bbs[i]->aux;
3492 : }
3493 :
3494 25979 : initialize_original_copy_tables ();
3495 : /* At this point we invalidate profile consistency until IFN_LOOP_VECTORIZED
3496 : is re-merged in the vectorizer. */
3497 25979 : new_loop = loop_version (loop, cond, &cond_bb,
3498 : profile_probability::always (),
3499 : profile_probability::always (),
3500 : profile_probability::always (),
3501 : profile_probability::always (), true);
3502 25979 : free_original_copy_tables ();
3503 :
3504 25979 : if (any_complicated_phi || need_to_predicate)
3505 26037 : for (unsigned i = 0; i < save_length; i++)
3506 22613 : ifc_bbs[i]->aux = saved_preds[i];
3507 :
3508 25979 : if (new_loop == NULL)
3509 : return NULL;
3510 :
3511 25979 : new_loop->dont_vectorize = true;
3512 25979 : new_loop->force_vectorize = false;
3513 25979 : gsi = gsi_last_bb (cond_bb);
3514 25979 : gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
3515 25979 : if (preds)
3516 25979 : preds->safe_push (g);
3517 25979 : gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3518 25979 : update_ssa (TODO_update_ssa_no_phi);
3519 25979 : return new_loop;
3520 : }
3521 :
3522 : /* Return true when LOOP satisfies the follow conditions that will
3523 : allow it to be recognized by the vectorizer for outer-loop
3524 : vectorization:
3525 : - The loop is not the root node of the loop tree.
3526 : - The loop has exactly one inner loop.
3527 : - The loop has a single exit.
3528 : - The loop header has a single successor, which is the inner
3529 : loop header.
3530 : - Each of the inner and outer loop latches have a single
3531 : predecessor.
3532 : - The loop exit block has a single predecessor, which is the
3533 : inner loop's exit block. */
3534 :
3535 : static bool
3536 25979 : versionable_outer_loop_p (class loop *loop)
3537 : {
3538 25979 : if (!loop_outer (loop)
3539 8089 : || loop->dont_vectorize
3540 7105 : || !loop->inner
3541 7105 : || loop->inner->next
3542 2943 : || !single_exit (loop)
3543 2248 : || !single_succ_p (loop->header)
3544 934 : || single_succ (loop->header) != loop->inner->header
3545 934 : || !single_pred_p (loop->latch)
3546 26913 : || !single_pred_p (loop->inner->latch))
3547 : return false;
3548 :
3549 934 : basic_block outer_exit = single_pred (loop->latch);
3550 934 : basic_block inner_exit = single_pred (loop->inner->latch);
3551 :
3552 1859 : if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit)
3553 : return false;
3554 :
3555 924 : if (dump_file)
3556 0 : fprintf (dump_file, "Found vectorizable outer loop for versioning\n");
3557 :
3558 : return true;
3559 : }
3560 :
3561 : /* Performs splitting of critical edges. Skip splitting and return false
3562 : if LOOP will not be converted because:
3563 :
3564 : - LOOP is not well formed.
3565 : - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
3566 :
3567 : Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
3568 :
3569 : static bool
3570 321471 : ifcvt_split_critical_edges (class loop *loop, bool aggressive_if_conv)
3571 : {
3572 321471 : basic_block *body;
3573 321471 : basic_block bb;
3574 321471 : unsigned int num = loop->num_nodes;
3575 321471 : unsigned int i;
3576 321471 : edge e;
3577 321471 : edge_iterator ei;
3578 321471 : auto_vec<edge> critical_edges;
3579 :
3580 : /* Loop is not well formed. */
3581 321471 : if (loop->inner)
3582 : return false;
3583 :
3584 229630 : body = get_loop_body (loop);
3585 1829602 : for (i = 0; i < num; i++)
3586 : {
3587 1376897 : bb = body[i];
3588 1376897 : if (!aggressive_if_conv
3589 1368708 : && phi_nodes (bb)
3590 1805446 : && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM)
3591 : {
3592 6555 : if (dump_file && (dump_flags & TDF_DETAILS))
3593 0 : fprintf (dump_file,
3594 : "BB %d has complicated PHI with more than %u args.\n",
3595 : bb->index, MAX_PHI_ARG_NUM);
3596 :
3597 6555 : free (body);
3598 6555 : return false;
3599 : }
3600 1370342 : if (bb == loop->latch || bb_with_exit_edge_p (loop, bb))
3601 783591 : continue;
3602 :
3603 : /* Skip basic blocks not ending with conditional branch. */
3604 1406192 : if (!safe_is_a <gcond *> (*gsi_last_bb (bb))
3605 586751 : && !safe_is_a <gswitch *> (*gsi_last_bb (bb)))
3606 325291 : continue;
3607 :
3608 796442 : FOR_EACH_EDGE (e, ei, bb->succs)
3609 658702 : if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
3610 123720 : critical_edges.safe_push (e);
3611 : }
3612 223075 : free (body);
3613 :
3614 441076 : while (critical_edges.length () > 0)
3615 : {
3616 119605 : e = critical_edges.pop ();
3617 : /* Don't split if bb can be predicated along non-critical edge. */
3618 119605 : if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest))
3619 56972 : split_edge (e);
3620 : }
3621 :
3622 : return true;
3623 321471 : }
3624 :
3625 : /* Delete redundant statements produced by predication which prevents
3626 : loop vectorization. */
3627 :
3628 : static void
3629 25979 : ifcvt_local_dce (class loop *loop)
3630 : {
3631 25979 : gimple *stmt;
3632 25979 : gimple *stmt1;
3633 25979 : gimple *phi;
3634 25979 : gimple_stmt_iterator gsi;
3635 25979 : auto_vec<gimple *> worklist;
3636 25979 : enum gimple_code code;
3637 25979 : use_operand_p use_p;
3638 25979 : imm_use_iterator imm_iter;
3639 :
3640 : /* The loop has a single BB only. */
3641 25979 : basic_block bb = loop->header;
3642 25979 : tree latch_vdef = NULL_TREE;
3643 :
3644 25979 : worklist.create (64);
3645 : /* Consider all phi as live statements. */
3646 104698 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3647 : {
3648 78719 : phi = gsi_stmt (gsi);
3649 78719 : gimple_set_plf (phi, GF_PLF_2, true);
3650 78719 : worklist.safe_push (phi);
3651 171441 : if (virtual_operand_p (gimple_phi_result (phi)))
3652 14003 : latch_vdef = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
3653 : }
3654 : /* Consider load/store statements, CALL and COND as live. */
3655 875917 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3656 : {
3657 823959 : stmt = gsi_stmt (gsi);
3658 823959 : if (is_gimple_debug (stmt))
3659 : {
3660 442494 : gimple_set_plf (stmt, GF_PLF_2, true);
3661 442494 : continue;
3662 : }
3663 381465 : if (gimple_store_p (stmt) || gimple_assign_load_p (stmt))
3664 : {
3665 59328 : gimple_set_plf (stmt, GF_PLF_2, true);
3666 59328 : worklist.safe_push (stmt);
3667 59328 : continue;
3668 : }
3669 322137 : code = gimple_code (stmt);
3670 322137 : if (code == GIMPLE_COND || code == GIMPLE_CALL || code == GIMPLE_SWITCH)
3671 : {
3672 31528 : gimple_set_plf (stmt, GF_PLF_2, true);
3673 31528 : worklist.safe_push (stmt);
3674 31528 : continue;
3675 : }
3676 290609 : gimple_set_plf (stmt, GF_PLF_2, false);
3677 :
3678 290609 : if (code == GIMPLE_ASSIGN)
3679 : {
3680 290600 : tree lhs = gimple_assign_lhs (stmt);
3681 673541 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
3682 : {
3683 402878 : stmt1 = USE_STMT (use_p);
3684 402878 : if (!is_gimple_debug (stmt1) && gimple_bb (stmt1) != bb)
3685 : {
3686 19937 : gimple_set_plf (stmt, GF_PLF_2, true);
3687 19937 : worklist.safe_push (stmt);
3688 19937 : break;
3689 : }
3690 290600 : }
3691 : }
3692 : }
3693 : /* Propagate liveness through arguments of live stmt. */
3694 473789 : while (worklist.length () > 0)
3695 : {
3696 447810 : ssa_op_iter iter;
3697 447810 : use_operand_p use_p;
3698 447810 : tree use;
3699 :
3700 447810 : stmt = worklist.pop ();
3701 1575739 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
3702 : {
3703 680119 : use = USE_FROM_PTR (use_p);
3704 680119 : if (TREE_CODE (use) != SSA_NAME)
3705 43391 : continue;
3706 636728 : stmt1 = SSA_NAME_DEF_STMT (use);
3707 636728 : if (gimple_bb (stmt1) != bb || gimple_plf (stmt1, GF_PLF_2))
3708 378430 : continue;
3709 258298 : gimple_set_plf (stmt1, GF_PLF_2, true);
3710 258298 : worklist.safe_push (stmt1);
3711 : }
3712 : }
3713 : /* Delete dead statements. */
3714 25979 : gsi = gsi_last_bb (bb);
3715 849938 : while (!gsi_end_p (gsi))
3716 : {
3717 823959 : gimple_stmt_iterator gsiprev = gsi;
3718 823959 : gsi_prev (&gsiprev);
3719 823959 : stmt = gsi_stmt (gsi);
3720 823959 : if (!gimple_has_volatile_ops (stmt)
3721 823814 : && gimple_store_p (stmt)
3722 381569 : && gimple_vdef (stmt))
3723 : {
3724 13044 : tree lhs = gimple_get_lhs (stmt);
3725 13044 : ao_ref write;
3726 13044 : ao_ref_init (&write, lhs);
3727 :
3728 13044 : if (dse_classify_store (&write, stmt, false, NULL, NULL, latch_vdef)
3729 : == DSE_STORE_DEAD)
3730 270 : delete_dead_or_redundant_assignment (&gsi, "dead");
3731 13044 : gsi = gsiprev;
3732 13044 : continue;
3733 13044 : }
3734 :
3735 810915 : if (gimple_plf (stmt, GF_PLF_2))
3736 : {
3737 798541 : gsi = gsiprev;
3738 798541 : continue;
3739 : }
3740 12374 : if (dump_file && (dump_flags & TDF_DETAILS))
3741 : {
3742 28 : fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
3743 28 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3744 : }
3745 12374 : gsi_remove (&gsi, true);
3746 12374 : release_defs (stmt);
3747 12374 : gsi = gsiprev;
3748 : }
3749 25979 : }
3750 :
3751 : /* Return true if VALUE is already available on edge PE. */
3752 :
3753 : static bool
3754 250798 : ifcvt_available_on_edge_p (edge pe, tree value)
3755 : {
3756 250798 : if (is_gimple_min_invariant (value))
3757 : return true;
3758 :
3759 244220 : if (TREE_CODE (value) == SSA_NAME)
3760 : {
3761 242989 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
3762 242989 : if (!def_bb || dominated_by_p (CDI_DOMINATORS, pe->dest, def_bb))
3763 27030 : return true;
3764 : }
3765 :
3766 : return false;
3767 : }
3768 :
3769 : /* Return true if STMT can be hoisted from if-converted loop LOOP to
3770 : edge PE. */
3771 :
3772 : static bool
3773 811315 : ifcvt_can_hoist (class loop *loop, edge pe, gimple *stmt)
3774 : {
3775 811315 : if (auto *call = dyn_cast<gcall *> (stmt))
3776 : {
3777 5555 : if (gimple_call_internal_p (call)
3778 5555 : && internal_fn_mask_index (gimple_call_internal_fn (call)) >= 0)
3779 : return false;
3780 : }
3781 805760 : else if (auto *assign = dyn_cast<gassign *> (stmt))
3782 : {
3783 397690 : if (gimple_assign_rhs_code (assign) == COND_EXPR)
3784 : return false;
3785 : }
3786 : else
3787 : return false;
3788 :
3789 293214 : if (gimple_has_side_effects (stmt)
3790 292030 : || gimple_could_trap_p (stmt)
3791 229985 : || stmt_could_throw_p (cfun, stmt)
3792 229983 : || gimple_vdef (stmt)
3793 522699 : || gimple_vuse (stmt))
3794 : return false;
3795 :
3796 228574 : int num_args = gimple_num_args (stmt);
3797 228574 : if (pe != loop_preheader_edge (loop))
3798 : {
3799 255713 : for (int i = 0; i < num_args; ++i)
3800 250798 : if (!ifcvt_available_on_edge_p (pe, gimple_arg (stmt, i)))
3801 : return false;
3802 : }
3803 : else
3804 : {
3805 8052 : for (int i = 0; i < num_args; ++i)
3806 7860 : if (!expr_invariant_in_loop_p (loop, gimple_arg (stmt, i)))
3807 : return false;
3808 : }
3809 :
3810 : return true;
3811 : }
3812 :
3813 : /* Hoist invariant statements from LOOP to edge PE. */
3814 :
3815 : static void
3816 25979 : ifcvt_hoist_invariants (class loop *loop, edge pe)
3817 : {
3818 : /* Only hoist from the now unconditionally executed part of the loop. */
3819 25979 : basic_block bb = loop->header;
3820 25979 : gimple_stmt_iterator hoist_gsi = {};
3821 863273 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
3822 : {
3823 811315 : gimple *stmt = gsi_stmt (gsi);
3824 811315 : if (ifcvt_can_hoist (loop, pe, stmt))
3825 : {
3826 : /* Once we've hoisted one statement, insert other statements
3827 : after it. */
3828 5107 : gsi_remove (&gsi, false);
3829 5107 : if (hoist_gsi.ptr)
3830 2699 : gsi_insert_after (&hoist_gsi, stmt, GSI_NEW_STMT);
3831 : else
3832 : {
3833 2408 : gsi_insert_on_edge_immediate (pe, stmt);
3834 2408 : hoist_gsi = gsi_for_stmt (stmt);
3835 : }
3836 5107 : continue;
3837 : }
3838 806208 : gsi_next (&gsi);
3839 : }
3840 25979 : }
3841 :
3842 : /* Returns the DECL_FIELD_BIT_OFFSET of the bitfield accesse in stmt iff its
3843 : type mode is not BLKmode. If BITPOS is not NULL it will hold the poly_int64
3844 : value of the DECL_FIELD_BIT_OFFSET of the bitfield access and STRUCT_EXPR,
3845 : if not NULL, will hold the tree representing the base struct of this
3846 : bitfield. */
3847 :
3848 : static tree
3849 1251 : get_bitfield_rep (gassign *stmt, bool write, tree *bitpos,
3850 : tree *struct_expr)
3851 : {
3852 1251 : tree comp_ref = write ? gimple_assign_lhs (stmt)
3853 384 : : gimple_assign_rhs1 (stmt);
3854 :
3855 1251 : tree field_decl = TREE_OPERAND (comp_ref, 1);
3856 1251 : tree ref_offset = component_ref_field_offset (comp_ref);
3857 1251 : tree rep_decl = DECL_BIT_FIELD_REPRESENTATIVE (field_decl);
3858 :
3859 : /* Bail out if the representative is not a suitable type for a scalar
3860 : register variable. */
3861 1251 : if (!is_gimple_reg_type (TREE_TYPE (rep_decl)))
3862 : return NULL_TREE;
3863 :
3864 : /* Bail out if the DECL_SIZE of the field_decl isn't the same as the BF's
3865 : precision. */
3866 1236 : unsigned HOST_WIDE_INT bf_prec
3867 1236 : = TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt)));
3868 1236 : if (compare_tree_int (DECL_SIZE (field_decl), bf_prec) != 0)
3869 : return NULL_TREE;
3870 :
3871 1236 : if (TREE_CODE (DECL_FIELD_OFFSET (rep_decl)) != INTEGER_CST
3872 1236 : || TREE_CODE (ref_offset) != INTEGER_CST)
3873 : {
3874 2 : if (dump_file && (dump_flags & TDF_DETAILS))
3875 2 : fprintf (dump_file, "\t Bitfield NOT OK to lower,"
3876 : " offset is non-constant.\n");
3877 : return NULL_TREE;
3878 : }
3879 :
3880 1234 : if (struct_expr)
3881 617 : *struct_expr = TREE_OPERAND (comp_ref, 0);
3882 :
3883 1234 : if (bitpos)
3884 : {
3885 : /* To calculate the bitposition of the BITFIELD_REF we have to determine
3886 : where our bitfield starts in relation to the container REP_DECL. The
3887 : DECL_FIELD_OFFSET of the original bitfield's member FIELD_DECL tells
3888 : us how many bytes from the start of the structure there are until the
3889 : start of the group of bitfield members the FIELD_DECL belongs to,
3890 : whereas DECL_FIELD_BIT_OFFSET will tell us how many bits from that
3891 : position our actual bitfield member starts. For the container
3892 : REP_DECL adding DECL_FIELD_OFFSET and DECL_FIELD_BIT_OFFSET will tell
3893 : us the distance between the start of the structure and the start of
3894 : the container, though the first is in bytes and the later other in
3895 : bits. With this in mind we calculate the bit position of our new
3896 : BITFIELD_REF by subtracting the number of bits between the start of
3897 : the structure and the container from the number of bits from the start
3898 : of the structure and the actual bitfield member. */
3899 617 : tree bf_pos = fold_build2 (MULT_EXPR, bitsizetype,
3900 : ref_offset,
3901 : build_int_cst (bitsizetype, BITS_PER_UNIT));
3902 617 : bf_pos = fold_build2 (PLUS_EXPR, bitsizetype, bf_pos,
3903 : DECL_FIELD_BIT_OFFSET (field_decl));
3904 617 : tree rep_pos = fold_build2 (MULT_EXPR, bitsizetype,
3905 : DECL_FIELD_OFFSET (rep_decl),
3906 : build_int_cst (bitsizetype, BITS_PER_UNIT));
3907 617 : rep_pos = fold_build2 (PLUS_EXPR, bitsizetype, rep_pos,
3908 : DECL_FIELD_BIT_OFFSET (rep_decl));
3909 :
3910 617 : *bitpos = fold_build2 (MINUS_EXPR, bitsizetype, bf_pos, rep_pos);
3911 : }
3912 :
3913 : return rep_decl;
3914 :
3915 : }
3916 :
3917 : /* Lowers the bitfield described by DATA.
3918 : For a write like:
3919 :
3920 : struct.bf = _1;
3921 :
3922 : lower to:
3923 :
3924 : __ifc_1 = struct.<representative>;
3925 : __ifc_2 = BIT_INSERT_EXPR (__ifc_1, _1, bitpos);
3926 : struct.<representative> = __ifc_2;
3927 :
3928 : For a read:
3929 :
3930 : _1 = struct.bf;
3931 :
3932 : lower to:
3933 :
3934 : __ifc_1 = struct.<representative>;
3935 : _1 = BIT_FIELD_REF (__ifc_1, bitsize, bitpos);
3936 :
3937 : where representative is a legal load that contains the bitfield value,
3938 : bitsize is the size of the bitfield and bitpos the offset to the start of
3939 : the bitfield within the representative. */
3940 :
3941 : static void
3942 617 : lower_bitfield (gassign *stmt, bool write)
3943 : {
3944 617 : tree struct_expr;
3945 617 : tree bitpos;
3946 617 : tree rep_decl = get_bitfield_rep (stmt, write, &bitpos, &struct_expr);
3947 617 : tree rep_type = TREE_TYPE (rep_decl);
3948 617 : tree bf_type = TREE_TYPE (gimple_assign_lhs (stmt));
3949 :
3950 617 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
3951 617 : if (dump_file && (dump_flags & TDF_DETAILS))
3952 : {
3953 9 : fprintf (dump_file, "Lowering:\n");
3954 9 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3955 9 : fprintf (dump_file, "to:\n");
3956 : }
3957 :
3958 : /* REP_COMP_REF is a COMPONENT_REF for the representative. NEW_VAL is it's
3959 : defining SSA_NAME. */
3960 617 : tree rep_comp_ref = build3 (COMPONENT_REF, rep_type, struct_expr, rep_decl,
3961 : NULL_TREE);
3962 617 : tree new_val = ifc_temp_var (rep_type, rep_comp_ref, &gsi);
3963 :
3964 617 : if (dump_file && (dump_flags & TDF_DETAILS))
3965 9 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (new_val), 0, TDF_SLIM);
3966 :
3967 617 : if (write)
3968 : {
3969 429 : new_val = ifc_temp_var (rep_type,
3970 : build3 (BIT_INSERT_EXPR, rep_type, new_val,
3971 : unshare_expr (gimple_assign_rhs1 (stmt)),
3972 : bitpos), &gsi);
3973 :
3974 429 : if (dump_file && (dump_flags & TDF_DETAILS))
3975 0 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (new_val), 0, TDF_SLIM);
3976 :
3977 429 : gimple *new_stmt = gimple_build_assign (unshare_expr (rep_comp_ref),
3978 : new_val);
3979 429 : gimple_move_vops (new_stmt, stmt);
3980 429 : gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
3981 :
3982 429 : if (dump_file && (dump_flags & TDF_DETAILS))
3983 0 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
3984 : }
3985 : else
3986 : {
3987 188 : tree bfr = build3 (BIT_FIELD_REF, bf_type, new_val,
3988 188 : build_int_cst (bitsizetype, TYPE_PRECISION (bf_type)),
3989 : bitpos);
3990 188 : new_val = ifc_temp_var (bf_type, bfr, &gsi);
3991 :
3992 188 : gimple *new_stmt = gimple_build_assign (gimple_assign_lhs (stmt),
3993 : new_val);
3994 188 : gimple_move_vops (new_stmt, stmt);
3995 188 : gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
3996 :
3997 188 : if (dump_file && (dump_flags & TDF_DETAILS))
3998 9 : print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
3999 : }
4000 :
4001 617 : gsi_remove (&gsi, true);
4002 617 : }
4003 :
4004 : /* Return TRUE if there are bitfields to lower in this LOOP. Fill TO_LOWER
4005 : with data structures representing these bitfields. */
4006 :
4007 : static bool
4008 247871 : bitfields_to_lower_p (class loop *loop,
4009 : vec <gassign *> &reads_to_lower,
4010 : vec <gassign *> &writes_to_lower)
4011 : {
4012 247871 : gimple_stmt_iterator gsi;
4013 :
4014 247871 : if (dump_file && (dump_flags & TDF_DETAILS))
4015 : {
4016 40 : fprintf (dump_file, "Analyzing loop %d for bitfields:\n", loop->num);
4017 : }
4018 :
4019 1038160 : for (unsigned i = 0; i < loop->num_nodes; ++i)
4020 : {
4021 790313 : basic_block bb = ifc_bbs[i];
4022 6849846 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4023 : {
4024 5269244 : gassign *stmt = dyn_cast<gassign*> (gsi_stmt (gsi));
4025 5269244 : if (!stmt)
4026 5141227 : continue;
4027 :
4028 2095032 : tree op = gimple_assign_lhs (stmt);
4029 2095032 : bool write = TREE_CODE (op) == COMPONENT_REF;
4030 :
4031 2095032 : if (!write)
4032 2063222 : op = gimple_assign_rhs1 (stmt);
4033 :
4034 2095032 : if (TREE_CODE (op) != COMPONENT_REF)
4035 1967015 : continue;
4036 :
4037 128017 : if (DECL_BIT_FIELD_TYPE (TREE_OPERAND (op, 1)))
4038 : {
4039 641 : if (dump_file && (dump_flags & TDF_DETAILS))
4040 11 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
4041 :
4042 641 : if (TREE_THIS_VOLATILE (op)
4043 641 : || reverse_storage_order_for_component_p (op))
4044 : {
4045 7 : if (dump_file && (dump_flags & TDF_DETAILS))
4046 0 : fprintf (dump_file, "\t Bitfield NO OK to lower,"
4047 : " the access is volatile or"
4048 : " has reverse storage-order.\n");
4049 24 : return false;
4050 : }
4051 :
4052 634 : if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
4053 : {
4054 0 : if (dump_file && (dump_flags & TDF_DETAILS))
4055 0 : fprintf (dump_file, "\t Bitfield NO OK to lower,"
4056 : " field type is not Integral.\n");
4057 : return false;
4058 : }
4059 :
4060 634 : if (!get_bitfield_rep (stmt, write, NULL, NULL))
4061 : {
4062 17 : if (dump_file && (dump_flags & TDF_DETAILS))
4063 2 : fprintf (dump_file, "\t Bitfield NOT OK to lower,"
4064 : " representative is BLKmode.\n");
4065 : return false;
4066 : }
4067 :
4068 617 : if (dump_file && (dump_flags & TDF_DETAILS))
4069 9 : fprintf (dump_file, "\tBitfield OK to lower.\n");
4070 617 : if (write)
4071 429 : writes_to_lower.safe_push (stmt);
4072 : else
4073 188 : reads_to_lower.safe_push (stmt);
4074 : }
4075 : }
4076 : }
4077 495559 : return !reads_to_lower.is_empty () || !writes_to_lower.is_empty ();
4078 : }
4079 :
4080 :
4081 : /* If-convert LOOP when it is legal. For the moment this pass has no
4082 : profitability analysis. Returns non-zero todo flags when something
4083 : changed. */
4084 :
4085 : unsigned int
4086 512053 : tree_if_conversion (class loop *loop, vec<gimple *> *preds)
4087 : {
4088 512053 : unsigned int todo = 0;
4089 512053 : bool aggressive_if_conv;
4090 512053 : class loop *rloop;
4091 512053 : auto_vec <gassign *, 4> reads_to_lower;
4092 512053 : auto_vec <gassign *, 4> writes_to_lower;
4093 512053 : bitmap exit_bbs;
4094 512053 : edge pe;
4095 512053 : auto_vec<data_reference_p, 10> refs;
4096 512977 : class loop *vloop, *nloop;
4097 :
4098 512977 : again:
4099 512977 : rloop = NULL;
4100 512977 : ifc_bbs = NULL;
4101 512977 : need_to_lower_bitfields = false;
4102 512977 : need_to_ifcvt = false;
4103 512977 : need_to_predicate = false;
4104 512977 : need_to_rewrite_undefined = false;
4105 512977 : any_complicated_phi = false;
4106 :
4107 : /* Apply more aggressive if-conversion when loop or its outer loop were
4108 : marked with simd pragma. When that's the case, we try to if-convert
4109 : loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
4110 512977 : aggressive_if_conv = loop->force_vectorize;
4111 512977 : if (!aggressive_if_conv)
4112 : {
4113 504537 : class loop *outer_loop = loop_outer (loop);
4114 504537 : if (outer_loop && outer_loop->force_vectorize)
4115 8696 : aggressive_if_conv = true;
4116 : }
4117 :
4118 : /* If there are more than two BBs in the loop then there is at least one if
4119 : to convert. */
4120 512977 : if (loop->num_nodes > 2
4121 512977 : && !ifcvt_split_critical_edges (loop, aggressive_if_conv))
4122 98396 : goto cleanup;
4123 :
4124 414581 : ifc_bbs = get_loop_body_in_if_conv_order (loop);
4125 414581 : if (!ifc_bbs)
4126 : {
4127 2647 : if (dump_file && (dump_flags & TDF_DETAILS))
4128 3 : fprintf (dump_file, "Irreducible loop\n");
4129 2647 : goto cleanup;
4130 : }
4131 :
4132 411934 : if (find_data_references_in_loop (loop, &refs) == chrec_dont_know)
4133 151225 : goto cleanup;
4134 :
4135 260709 : if (loop->num_nodes > 2)
4136 : {
4137 : /* More than one loop exit is too much to handle. */
4138 138132 : if (!single_exit (loop))
4139 : {
4140 99580 : if (dump_file && (dump_flags & TDF_DETAILS))
4141 10 : fprintf (dump_file, "Can not ifcvt due to multiple exits\n");
4142 : }
4143 : else
4144 : {
4145 38552 : need_to_ifcvt = true;
4146 :
4147 38552 : if (!if_convertible_loop_p (loop, &refs)
4148 38552 : || !dbg_cnt (if_conversion_tree))
4149 12838 : goto cleanup;
4150 : }
4151 : }
4152 :
4153 247871 : need_to_lower_bitfields = bitfields_to_lower_p (loop, reads_to_lower,
4154 : writes_to_lower);
4155 :
4156 247871 : if (!need_to_ifcvt && !need_to_lower_bitfields)
4157 221892 : goto cleanup;
4158 :
4159 : /* The edge to insert invariant stmts on. */
4160 25979 : pe = loop_preheader_edge (loop);
4161 :
4162 : /* Since we have no cost model, always version loops.
4163 : Either version this loop, or if the pattern is right for outer-loop
4164 : vectorization, version the outer loop. In the latter case we will
4165 : still if-convert the original inner loop. */
4166 25979 : vloop = (versionable_outer_loop_p (loop_outer (loop))
4167 25979 : ? loop_outer (loop) : loop);
4168 25979 : nloop = version_loop_for_if_conversion (vloop, preds);
4169 25979 : if (nloop == NULL)
4170 0 : goto cleanup;
4171 25979 : if (vloop != loop)
4172 : {
4173 : /* If versionable_outer_loop_p decided to version the
4174 : outer loop, version also the inner loop of the non-vectorized
4175 : loop copy. So we transform:
4176 : loop1
4177 : loop2
4178 : into:
4179 : if (LOOP_VECTORIZED (1, 3))
4180 : {
4181 : loop1
4182 : loop2
4183 : }
4184 : else
4185 : loop3 (copy of loop1)
4186 : if (LOOP_VECTORIZED (4, 5))
4187 : loop4 (copy of loop2)
4188 : else
4189 : loop5 (copy of loop4) */
4190 924 : gcc_assert (nloop->inner && nloop->inner->next == NULL);
4191 : rloop = nloop->inner;
4192 : }
4193 : else
4194 : /* If we versioned loop then make sure to insert invariant
4195 : stmts before the .LOOP_VECTORIZED check since the vectorizer
4196 : will re-use that for things like runtime alias versioning
4197 : whose condition can end up using those invariants. */
4198 25055 : pe = single_pred_edge (gimple_bb (preds->last ()));
4199 :
4200 25979 : if (need_to_lower_bitfields)
4201 : {
4202 266 : if (dump_file && (dump_flags & TDF_DETAILS))
4203 : {
4204 9 : fprintf (dump_file, "-------------------------\n");
4205 9 : fprintf (dump_file, "Start lowering bitfields\n");
4206 : }
4207 454 : while (!reads_to_lower.is_empty ())
4208 188 : lower_bitfield (reads_to_lower.pop (), false);
4209 695 : while (!writes_to_lower.is_empty ())
4210 429 : lower_bitfield (writes_to_lower.pop (), true);
4211 :
4212 266 : if (dump_file && (dump_flags & TDF_DETAILS))
4213 : {
4214 9 : fprintf (dump_file, "Done lowering bitfields\n");
4215 9 : fprintf (dump_file, "-------------------------\n");
4216 : }
4217 : }
4218 25979 : if (need_to_ifcvt)
4219 : {
4220 : /* Before we rewrite edges we'll record their original position in the
4221 : edge map such that we can map the edges between the ifcvt and the
4222 : non-ifcvt loop during peeling. */
4223 25714 : uintptr_t idx = 0;
4224 102856 : for (edge exit : get_loop_exit_edges (loop))
4225 25714 : exit->aux = (void*)idx++;
4226 :
4227 : /* Now all statements are if-convertible. Combine all the basic
4228 : blocks into one huge basic block doing the if-conversion
4229 : on-the-fly. */
4230 25714 : combine_blocks (loop);
4231 : }
4232 :
4233 25979 : std::pair <tree, tree> *name_pair;
4234 25979 : unsigned ssa_names_idx;
4235 31306 : FOR_EACH_VEC_ELT (redundant_ssa_names, ssa_names_idx, name_pair)
4236 5327 : replace_uses_by (name_pair->first, name_pair->second);
4237 25979 : redundant_ssa_names.release ();
4238 :
4239 : /* Perform local CSE, this esp. helps the vectorizer analysis if loads
4240 : and stores are involved. CSE only the loop body, not the entry
4241 : PHIs, those are to be kept in sync with the non-if-converted copy.
4242 : ??? We'll still keep dead stores though. */
4243 25979 : exit_bbs = BITMAP_ALLOC (NULL);
4244 104098 : for (edge exit : get_loop_exit_edges (loop))
4245 26179 : bitmap_set_bit (exit_bbs, exit->dest->index);
4246 25979 : todo |= do_rpo_vn (cfun, loop_preheader_edge (loop), exit_bbs,
4247 : false, true, true);
4248 :
4249 : /* Delete dead predicate computations. */
4250 25979 : ifcvt_local_dce (loop);
4251 25979 : BITMAP_FREE (exit_bbs);
4252 :
4253 25979 : ifcvt_hoist_invariants (loop, pe);
4254 :
4255 25979 : todo |= TODO_cleanup_cfg;
4256 :
4257 512977 : cleanup:
4258 512977 : data_reference_p dr;
4259 512977 : unsigned int i;
4260 1685435 : for (i = 0; refs.iterate (i, &dr); i++)
4261 : {
4262 1172458 : free (dr->aux);
4263 1172458 : free_data_ref (dr);
4264 : }
4265 512977 : refs.truncate (0);
4266 :
4267 512977 : if (ifc_bbs)
4268 : {
4269 : unsigned int i;
4270 :
4271 2028526 : for (i = 0; i < loop->num_nodes; i++)
4272 1642306 : free_bb_predicate (ifc_bbs[i]);
4273 :
4274 386220 : free (ifc_bbs);
4275 386220 : ifc_bbs = NULL;
4276 : }
4277 512977 : if (rloop != NULL)
4278 : {
4279 924 : loop = rloop;
4280 924 : reads_to_lower.truncate (0);
4281 924 : writes_to_lower.truncate (0);
4282 924 : goto again;
4283 : }
4284 :
4285 512053 : return todo;
4286 512053 : }
4287 :
4288 : /* Tree if-conversion pass management. */
4289 :
4290 : namespace {
4291 :
4292 : const pass_data pass_data_if_conversion =
4293 : {
4294 : GIMPLE_PASS, /* type */
4295 : "ifcvt", /* name */
4296 : OPTGROUP_NONE, /* optinfo_flags */
4297 : TV_TREE_LOOP_IFCVT, /* tv_id */
4298 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4299 : 0, /* properties_provided */
4300 : 0, /* properties_destroyed */
4301 : 0, /* todo_flags_start */
4302 : 0, /* todo_flags_finish */
4303 : };
4304 :
4305 : class pass_if_conversion : public gimple_opt_pass
4306 : {
4307 : public:
4308 297180 : pass_if_conversion (gcc::context *ctxt)
4309 594360 : : gimple_opt_pass (pass_data_if_conversion, ctxt)
4310 : {}
4311 :
4312 : /* opt_pass methods: */
4313 : bool gate (function *) final override;
4314 : unsigned int execute (function *) final override;
4315 :
4316 : }; // class pass_if_conversion
4317 :
4318 : bool
4319 248475 : pass_if_conversion::gate (function *fun)
4320 : {
4321 248475 : return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
4322 : }
4323 :
4324 : unsigned int
4325 214144 : pass_if_conversion::execute (function *fun)
4326 : {
4327 214144 : unsigned todo = 0;
4328 :
4329 428288 : if (number_of_loops (fun) <= 1)
4330 : return 0;
4331 :
4332 214144 : auto_vec<gimple *> preds;
4333 1162116 : for (auto loop : loops_list (cfun, 0))
4334 519684 : if ((flag_tree_loop_vectorize || loop->force_vectorize)
4335 516820 : && !loop->dont_vectorize)
4336 512053 : todo |= tree_if_conversion (loop, &preds);
4337 :
4338 214144 : if (todo)
4339 : {
4340 17757 : free_numbers_of_iterations_estimates (fun);
4341 17757 : scev_reset ();
4342 : }
4343 :
4344 214144 : if (flag_checking)
4345 : {
4346 214140 : basic_block bb;
4347 7208183 : FOR_EACH_BB_FN (bb, fun)
4348 6994043 : gcc_assert (!bb->aux);
4349 : }
4350 :
4351 : /* Perform IL update now, it might elide some loops. */
4352 214144 : if (todo & TODO_cleanup_cfg)
4353 : {
4354 17757 : cleanup_tree_cfg ();
4355 17757 : if (need_ssa_update_p (fun))
4356 0 : todo |= TODO_update_ssa;
4357 : }
4358 214144 : if (todo & TODO_update_ssa_any)
4359 0 : update_ssa (todo & TODO_update_ssa_any);
4360 :
4361 : /* If if-conversion elided the loop fall back to the original one. Likewise
4362 : if the loops are not nested in the same outer loop. */
4363 240123 : for (unsigned i = 0; i < preds.length (); ++i)
4364 : {
4365 25979 : gimple *g = preds[i];
4366 25979 : if (!gimple_bb (g))
4367 0 : continue;
4368 25979 : auto ifcvt_loop = get_loop (fun, tree_to_uhwi (gimple_call_arg (g, 0)));
4369 25979 : auto orig_loop = get_loop (fun, tree_to_uhwi (gimple_call_arg (g, 1)));
4370 25979 : if (!ifcvt_loop || !orig_loop)
4371 : {
4372 2 : if (dump_file)
4373 0 : fprintf (dump_file, "If-converted loop vanished\n");
4374 2 : fold_loop_internal_call (g, boolean_false_node);
4375 : }
4376 25977 : else if (loop_outer (ifcvt_loop) != loop_outer (orig_loop))
4377 : {
4378 0 : if (dump_file)
4379 0 : fprintf (dump_file, "If-converted loop in different outer loop\n");
4380 0 : fold_loop_internal_call (g, boolean_false_node);
4381 : }
4382 : }
4383 :
4384 214144 : return 0;
4385 214144 : }
4386 :
4387 : } // anon namespace
4388 :
4389 : gimple_opt_pass *
4390 297180 : make_pass_if_conversion (gcc::context *ctxt)
4391 : {
4392 297180 : return new pass_if_conversion (ctxt);
4393 : }
|