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