1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2019 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 "optabs-query.h"
95 #include "gimple-pretty-print.h"
96 #include "alias.h"
97 #include "fold-const.h"
98 #include "stor-layout.h"
99 #include "gimple-fold.h"
100 #include "gimplify.h"
101 #include "gimple-iterator.h"
102 #include "gimplify-me.h"
103 #include "tree-cfg.h"
104 #include "tree-into-ssa.h"
105 #include "tree-ssa.h"
106 #include "cfgloop.h"
107 #include "tree-data-ref.h"
108 #include "tree-scalar-evolution.h"
109 #include "tree-ssa-loop.h"
110 #include "tree-ssa-loop-niter.h"
111 #include "tree-ssa-loop-ivopts.h"
112 #include "tree-ssa-address.h"
113 #include "dbgcnt.h"
114 #include "tree-hash-traits.h"
115 #include "varasm.h"
116 #include "builtins.h"
117 #include "params.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
124 /* Only handle PHIs with no more arguments unless we are asked to by
125 simd pragma. */
126 #define MAX_PHI_ARG_NUM \
127 ((unsigned) PARAM_VALUE (PARAM_MAX_TREE_IF_CONVERSION_PHI_ARGS))
128
129 /* True if we've converted a statement that was only executed when some
130 condition C was true, and if for correctness we need to predicate the
131 statement to ensure that it is a no-op when C is false. See
132 predicate_statements for the kinds of predication we support. */
133 static bool need_to_predicate;
134
135 /* Indicate if there are any complicated PHIs that need to be handled in
136 if-conversion. Complicated PHI has more than two arguments and can't
137 be degenerated to two arguments PHI. See more information in comment
138 before phi_convertible_by_degenerating_args. */
139 static bool any_complicated_phi;
140
141 /* Hash for struct innermost_loop_behavior. It depends on the user to
142 free the memory. */
143
144 struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior>
145 {
146 static inline hashval_t hash (const value_type &);
147 static inline bool equal (const value_type &,
148 const compare_type &);
149 };
150
151 inline hashval_t
hash(const value_type & e)152 innermost_loop_behavior_hash::hash (const value_type &e)
153 {
154 hashval_t hash;
155
156 hash = iterative_hash_expr (e->base_address, 0);
157 hash = iterative_hash_expr (e->offset, hash);
158 hash = iterative_hash_expr (e->init, hash);
159 return iterative_hash_expr (e->step, hash);
160 }
161
162 inline bool
equal(const value_type & e1,const compare_type & e2)163 innermost_loop_behavior_hash::equal (const value_type &e1,
164 const compare_type &e2)
165 {
166 if ((e1->base_address && !e2->base_address)
167 || (!e1->base_address && e2->base_address)
168 || (!e1->offset && e2->offset)
169 || (e1->offset && !e2->offset)
170 || (!e1->init && e2->init)
171 || (e1->init && !e2->init)
172 || (!e1->step && e2->step)
173 || (e1->step && !e2->step))
174 return false;
175
176 if (e1->base_address && e2->base_address
177 && !operand_equal_p (e1->base_address, e2->base_address, 0))
178 return false;
179 if (e1->offset && e2->offset
180 && !operand_equal_p (e1->offset, e2->offset, 0))
181 return false;
182 if (e1->init && e2->init
183 && !operand_equal_p (e1->init, e2->init, 0))
184 return false;
185 if (e1->step && e2->step
186 && !operand_equal_p (e1->step, e2->step, 0))
187 return false;
188
189 return true;
190 }
191
192 /* List of basic blocks in if-conversion-suitable order. */
193 static basic_block *ifc_bbs;
194
195 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
196 static hash_map<innermost_loop_behavior_hash,
197 data_reference_p> *innermost_DR_map;
198
199 /* Hash table to store <base reference, DR> pairs. */
200 static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map;
201
202 /* List of redundant SSA names: the first should be replaced by the second. */
203 static vec< std::pair<tree, tree> > redundant_ssa_names;
204
205 /* Structure used to predicate basic blocks. This is attached to the
206 ->aux field of the BBs in the loop to be if-converted. */
207 struct bb_predicate {
208
209 /* The condition under which this basic block is executed. */
210 tree predicate;
211
212 /* PREDICATE is gimplified, and the sequence of statements is
213 recorded here, in order to avoid the duplication of computations
214 that occur in previous conditions. See PR44483. */
215 gimple_seq predicate_gimplified_stmts;
216 };
217
218 /* Returns true when the basic block BB has a predicate. */
219
220 static inline bool
bb_has_predicate(basic_block bb)221 bb_has_predicate (basic_block bb)
222 {
223 return bb->aux != NULL;
224 }
225
226 /* Returns the gimplified predicate for basic block BB. */
227
228 static inline tree
bb_predicate(basic_block bb)229 bb_predicate (basic_block bb)
230 {
231 return ((struct bb_predicate *) bb->aux)->predicate;
232 }
233
234 /* Sets the gimplified predicate COND for basic block BB. */
235
236 static inline void
set_bb_predicate(basic_block bb,tree cond)237 set_bb_predicate (basic_block bb, tree cond)
238 {
239 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
240 && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
241 || is_gimple_condexpr (cond));
242 ((struct bb_predicate *) bb->aux)->predicate = cond;
243 }
244
245 /* Returns the sequence of statements of the gimplification of the
246 predicate for basic block BB. */
247
248 static inline gimple_seq
bb_predicate_gimplified_stmts(basic_block bb)249 bb_predicate_gimplified_stmts (basic_block bb)
250 {
251 return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts;
252 }
253
254 /* Sets the sequence of statements STMTS of the gimplification of the
255 predicate for basic block BB. */
256
257 static inline void
set_bb_predicate_gimplified_stmts(basic_block bb,gimple_seq stmts)258 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
259 {
260 ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts;
261 }
262
263 /* Adds the sequence of statements STMTS to the sequence of statements
264 of the predicate for basic block BB. */
265
266 static inline void
add_bb_predicate_gimplified_stmts(basic_block bb,gimple_seq stmts)267 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
268 {
269 /* We might have updated some stmts in STMTS via force_gimple_operand
270 calling fold_stmt and that producing multiple stmts. Delink immediate
271 uses so update_ssa after loop versioning doesn't get confused for
272 the not yet inserted predicates.
273 ??? This should go away once we reliably avoid updating stmts
274 not in any BB. */
275 for (gimple_stmt_iterator gsi = gsi_start (stmts);
276 !gsi_end_p (gsi); gsi_next (&gsi))
277 {
278 gimple *stmt = gsi_stmt (gsi);
279 delink_stmt_imm_use (stmt);
280 gimple_set_modified (stmt, true);
281 }
282 gimple_seq_add_seq_without_update
283 (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts);
284 }
285
286 /* Initializes to TRUE the predicate of basic block BB. */
287
288 static inline void
init_bb_predicate(basic_block bb)289 init_bb_predicate (basic_block bb)
290 {
291 bb->aux = XNEW (struct bb_predicate);
292 set_bb_predicate_gimplified_stmts (bb, NULL);
293 set_bb_predicate (bb, boolean_true_node);
294 }
295
296 /* Release the SSA_NAMEs associated with the predicate of basic block BB. */
297
298 static inline void
release_bb_predicate(basic_block bb)299 release_bb_predicate (basic_block bb)
300 {
301 gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
302 if (stmts)
303 {
304 /* Ensure that these stmts haven't yet been added to a bb. */
305 if (flag_checking)
306 for (gimple_stmt_iterator i = gsi_start (stmts);
307 !gsi_end_p (i); gsi_next (&i))
308 gcc_assert (! gimple_bb (gsi_stmt (i)));
309
310 /* Discard them. */
311 gimple_seq_discard (stmts);
312 set_bb_predicate_gimplified_stmts (bb, NULL);
313 }
314 }
315
316 /* Free the predicate of basic block BB. */
317
318 static inline void
free_bb_predicate(basic_block bb)319 free_bb_predicate (basic_block bb)
320 {
321 if (!bb_has_predicate (bb))
322 return;
323
324 release_bb_predicate (bb);
325 free (bb->aux);
326 bb->aux = NULL;
327 }
328
329 /* Reinitialize predicate of BB with the true predicate. */
330
331 static inline void
reset_bb_predicate(basic_block bb)332 reset_bb_predicate (basic_block bb)
333 {
334 if (!bb_has_predicate (bb))
335 init_bb_predicate (bb);
336 else
337 {
338 release_bb_predicate (bb);
339 set_bb_predicate (bb, boolean_true_node);
340 }
341 }
342
343 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
344 the expression EXPR. Inserts the statement created for this
345 computation before GSI and leaves the iterator GSI at the same
346 statement. */
347
348 static tree
ifc_temp_var(tree type,tree expr,gimple_stmt_iterator * gsi)349 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
350 {
351 tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
352 gimple *stmt = gimple_build_assign (new_name, expr);
353 gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi)));
354 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
355 return new_name;
356 }
357
358 /* Return true when COND is a false predicate. */
359
360 static inline bool
is_false_predicate(tree cond)361 is_false_predicate (tree cond)
362 {
363 return (cond != NULL_TREE
364 && (cond == boolean_false_node
365 || integer_zerop (cond)));
366 }
367
368 /* Return true when COND is a true predicate. */
369
370 static inline bool
is_true_predicate(tree cond)371 is_true_predicate (tree cond)
372 {
373 return (cond == NULL_TREE
374 || cond == boolean_true_node
375 || integer_onep (cond));
376 }
377
378 /* Returns true when BB has a predicate that is not trivial: true or
379 NULL_TREE. */
380
381 static inline bool
is_predicated(basic_block bb)382 is_predicated (basic_block bb)
383 {
384 return !is_true_predicate (bb_predicate (bb));
385 }
386
387 /* Parses the predicate COND and returns its comparison code and
388 operands OP0 and OP1. */
389
390 static enum tree_code
parse_predicate(tree cond,tree * op0,tree * op1)391 parse_predicate (tree cond, tree *op0, tree *op1)
392 {
393 gimple *s;
394
395 if (TREE_CODE (cond) == SSA_NAME
396 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
397 {
398 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
399 {
400 *op0 = gimple_assign_rhs1 (s);
401 *op1 = gimple_assign_rhs2 (s);
402 return gimple_assign_rhs_code (s);
403 }
404
405 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
406 {
407 tree op = gimple_assign_rhs1 (s);
408 tree type = TREE_TYPE (op);
409 enum tree_code code = parse_predicate (op, op0, op1);
410
411 return code == ERROR_MARK ? ERROR_MARK
412 : invert_tree_comparison (code, HONOR_NANS (type));
413 }
414
415 return ERROR_MARK;
416 }
417
418 if (COMPARISON_CLASS_P (cond))
419 {
420 *op0 = TREE_OPERAND (cond, 0);
421 *op1 = TREE_OPERAND (cond, 1);
422 return TREE_CODE (cond);
423 }
424
425 return ERROR_MARK;
426 }
427
428 /* Returns the fold of predicate C1 OR C2 at location LOC. */
429
430 static tree
fold_or_predicates(location_t loc,tree c1,tree c2)431 fold_or_predicates (location_t loc, tree c1, tree c2)
432 {
433 tree op1a, op1b, op2a, op2b;
434 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
435 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
436
437 if (code1 != ERROR_MARK && code2 != ERROR_MARK)
438 {
439 tree t = maybe_fold_or_comparisons (code1, op1a, op1b,
440 code2, op2a, op2b);
441 if (t)
442 return t;
443 }
444
445 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
446 }
447
448 /* Returns either a COND_EXPR or the folded expression if the folded
449 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
450 a constant or a SSA_NAME. */
451
452 static tree
fold_build_cond_expr(tree type,tree cond,tree rhs,tree lhs)453 fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
454 {
455 tree rhs1, lhs1, cond_expr;
456
457 /* If COND is comparison r != 0 and r has boolean type, convert COND
458 to SSA_NAME to accept by vect bool pattern. */
459 if (TREE_CODE (cond) == NE_EXPR)
460 {
461 tree op0 = TREE_OPERAND (cond, 0);
462 tree op1 = TREE_OPERAND (cond, 1);
463 if (TREE_CODE (op0) == SSA_NAME
464 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
465 && (integer_zerop (op1)))
466 cond = op0;
467 }
468 cond_expr = fold_ternary (COND_EXPR, type, cond, rhs, lhs);
469
470 if (cond_expr == NULL_TREE)
471 return build3 (COND_EXPR, type, cond, rhs, lhs);
472
473 STRIP_USELESS_TYPE_CONVERSION (cond_expr);
474
475 if (is_gimple_val (cond_expr))
476 return cond_expr;
477
478 if (TREE_CODE (cond_expr) == ABS_EXPR)
479 {
480 rhs1 = TREE_OPERAND (cond_expr, 1);
481 STRIP_USELESS_TYPE_CONVERSION (rhs1);
482 if (is_gimple_val (rhs1))
483 return build1 (ABS_EXPR, type, rhs1);
484 }
485
486 if (TREE_CODE (cond_expr) == MIN_EXPR
487 || TREE_CODE (cond_expr) == MAX_EXPR)
488 {
489 lhs1 = TREE_OPERAND (cond_expr, 0);
490 STRIP_USELESS_TYPE_CONVERSION (lhs1);
491 rhs1 = TREE_OPERAND (cond_expr, 1);
492 STRIP_USELESS_TYPE_CONVERSION (rhs1);
493 if (is_gimple_val (rhs1) && is_gimple_val (lhs1))
494 return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1);
495 }
496 return build3 (COND_EXPR, type, cond, rhs, lhs);
497 }
498
499 /* Add condition NC to the predicate list of basic block BB. LOOP is
500 the loop to be if-converted. Use predicate of cd-equivalent block
501 for join bb if it exists: we call basic blocks bb1 and bb2
502 cd-equivalent if they are executed under the same condition. */
503
504 static inline void
add_to_predicate_list(struct loop * loop,basic_block bb,tree nc)505 add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
506 {
507 tree bc, *tp;
508 basic_block dom_bb;
509
510 if (is_true_predicate (nc))
511 return;
512
513 /* If dominance tells us this basic block is always executed,
514 don't record any predicates for it. */
515 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
516 return;
517
518 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
519 /* We use notion of cd equivalence to get simpler predicate for
520 join block, e.g. if join block has 2 predecessors with predicates
521 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
522 p1 & p2 | p1 & !p2. */
523 if (dom_bb != loop->header
524 && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
525 {
526 gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
527 bc = bb_predicate (dom_bb);
528 if (!is_true_predicate (bc))
529 set_bb_predicate (bb, bc);
530 else
531 gcc_assert (is_true_predicate (bb_predicate (bb)));
532 if (dump_file && (dump_flags & TDF_DETAILS))
533 fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
534 dom_bb->index, bb->index);
535 return;
536 }
537
538 if (!is_predicated (bb))
539 bc = nc;
540 else
541 {
542 bc = bb_predicate (bb);
543 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
544 if (is_true_predicate (bc))
545 {
546 reset_bb_predicate (bb);
547 return;
548 }
549 }
550
551 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
552 if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
553 tp = &TREE_OPERAND (bc, 0);
554 else
555 tp = &bc;
556 if (!is_gimple_condexpr (*tp))
557 {
558 gimple_seq stmts;
559 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
560 add_bb_predicate_gimplified_stmts (bb, stmts);
561 }
562 set_bb_predicate (bb, bc);
563 }
564
565 /* Add the condition COND to the previous condition PREV_COND, and add
566 this to the predicate list of the destination of edge E. LOOP is
567 the loop to be if-converted. */
568
569 static void
add_to_dst_predicate_list(struct loop * loop,edge e,tree prev_cond,tree cond)570 add_to_dst_predicate_list (struct loop *loop, edge e,
571 tree prev_cond, tree cond)
572 {
573 if (!flow_bb_inside_loop_p (loop, e->dest))
574 return;
575
576 if (!is_true_predicate (prev_cond))
577 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
578 prev_cond, cond);
579
580 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
581 add_to_predicate_list (loop, e->dest, cond);
582 }
583
584 /* Return true if one of the successor edges of BB exits LOOP. */
585
586 static bool
bb_with_exit_edge_p(struct loop * loop,basic_block bb)587 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
588 {
589 edge e;
590 edge_iterator ei;
591
592 FOR_EACH_EDGE (e, ei, bb->succs)
593 if (loop_exit_edge_p (loop, e))
594 return true;
595
596 return false;
597 }
598
599 /* Given PHI which has more than two arguments, this function checks if
600 it's if-convertible by degenerating its arguments. Specifically, if
601 below two conditions are satisfied:
602
603 1) Number of PHI arguments with different values equals to 2 and one
604 argument has the only occurrence.
605 2) The edge corresponding to the unique argument isn't critical edge.
606
607 Such PHI can be handled as PHIs have only two arguments. For example,
608 below PHI:
609
610 res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
611
612 can be transformed into:
613
614 res = (predicate of e3) ? A_2 : A_1;
615
616 Return TRUE if it is the case, FALSE otherwise. */
617
618 static bool
phi_convertible_by_degenerating_args(gphi * phi)619 phi_convertible_by_degenerating_args (gphi *phi)
620 {
621 edge e;
622 tree arg, t1 = NULL, t2 = NULL;
623 unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0;
624 unsigned int num_args = gimple_phi_num_args (phi);
625
626 gcc_assert (num_args > 2);
627
628 for (i = 0; i < num_args; i++)
629 {
630 arg = gimple_phi_arg_def (phi, i);
631 if (t1 == NULL || operand_equal_p (t1, arg, 0))
632 {
633 n1++;
634 i1 = i;
635 t1 = arg;
636 }
637 else if (t2 == NULL || operand_equal_p (t2, arg, 0))
638 {
639 n2++;
640 i2 = i;
641 t2 = arg;
642 }
643 else
644 return false;
645 }
646
647 if (n1 != 1 && n2 != 1)
648 return false;
649
650 /* Check if the edge corresponding to the unique arg is critical. */
651 e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2);
652 if (EDGE_COUNT (e->src->succs) > 1)
653 return false;
654
655 return true;
656 }
657
658 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
659 and it belongs to basic block BB. Note at this point, it is sure
660 that PHI is if-convertible. This function updates global variable
661 ANY_COMPLICATED_PHI if PHI is complicated. */
662
663 static bool
if_convertible_phi_p(struct loop * loop,basic_block bb,gphi * phi)664 if_convertible_phi_p (struct loop *loop, basic_block bb, gphi *phi)
665 {
666 if (dump_file && (dump_flags & TDF_DETAILS))
667 {
668 fprintf (dump_file, "-------------------------\n");
669 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
670 }
671
672 if (bb != loop->header
673 && gimple_phi_num_args (phi) > 2
674 && !phi_convertible_by_degenerating_args (phi))
675 any_complicated_phi = true;
676
677 return true;
678 }
679
680 /* Records the status of a data reference. This struct is attached to
681 each DR->aux field. */
682
683 struct ifc_dr {
684 bool rw_unconditionally;
685 bool w_unconditionally;
686 bool written_at_least_once;
687
688 tree rw_predicate;
689 tree w_predicate;
690 tree base_w_predicate;
691 };
692
693 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
694 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
695 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
696 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
697
698 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
699 HASH tables. While storing them in HASH table, it checks if the
700 reference is unconditionally read or written and stores that as a flag
701 information. For base reference it checks if it is written atlest once
702 unconditionally and stores it as flag information along with DR.
703 In other words for every data reference A in STMT there exist other
704 accesses to a data reference with the same base with predicates that
705 add up (OR-up) to the true predicate: this ensures that the data
706 reference A is touched (read or written) on every iteration of the
707 if-converted loop. */
708 static void
hash_memrefs_baserefs_and_store_DRs_read_written_info(data_reference_p a)709 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a)
710 {
711
712 data_reference_p *master_dr, *base_master_dr;
713 tree base_ref = DR_BASE_OBJECT (a);
714 innermost_loop_behavior *innermost = &DR_INNERMOST (a);
715 tree ca = bb_predicate (gimple_bb (DR_STMT (a)));
716 bool exist1, exist2;
717
718 master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1);
719 if (!exist1)
720 *master_dr = a;
721
722 if (DR_IS_WRITE (a))
723 {
724 IFC_DR (*master_dr)->w_predicate
725 = fold_or_predicates (UNKNOWN_LOCATION, ca,
726 IFC_DR (*master_dr)->w_predicate);
727 if (is_true_predicate (IFC_DR (*master_dr)->w_predicate))
728 DR_W_UNCONDITIONALLY (*master_dr) = true;
729 }
730 IFC_DR (*master_dr)->rw_predicate
731 = fold_or_predicates (UNKNOWN_LOCATION, ca,
732 IFC_DR (*master_dr)->rw_predicate);
733 if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate))
734 DR_RW_UNCONDITIONALLY (*master_dr) = true;
735
736 if (DR_IS_WRITE (a))
737 {
738 base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2);
739 if (!exist2)
740 *base_master_dr = a;
741 IFC_DR (*base_master_dr)->base_w_predicate
742 = fold_or_predicates (UNKNOWN_LOCATION, ca,
743 IFC_DR (*base_master_dr)->base_w_predicate);
744 if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate))
745 DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true;
746 }
747 }
748
749 /* Return TRUE if can prove the index IDX of an array reference REF is
750 within array bound. Return false otherwise. */
751
752 static bool
idx_within_array_bound(tree ref,tree * idx,void * dta)753 idx_within_array_bound (tree ref, tree *idx, void *dta)
754 {
755 wi::overflow_type overflow;
756 widest_int niter, valid_niter, delta, wi_step;
757 tree ev, init, step;
758 tree low, high;
759 struct loop *loop = (struct loop*) dta;
760
761 /* Only support within-bound access for array references. */
762 if (TREE_CODE (ref) != ARRAY_REF)
763 return false;
764
765 /* For arrays at the end of the structure, we are not guaranteed that they
766 do not really extend over their declared size. However, for arrays of
767 size greater than one, this is unlikely to be intended. */
768 if (array_at_struct_end_p (ref))
769 return false;
770
771 ev = analyze_scalar_evolution (loop, *idx);
772 ev = instantiate_parameters (loop, ev);
773 init = initial_condition (ev);
774 step = evolution_part_in_loop_num (ev, loop->num);
775
776 if (!init || TREE_CODE (init) != INTEGER_CST
777 || (step && TREE_CODE (step) != INTEGER_CST))
778 return false;
779
780 low = array_ref_low_bound (ref);
781 high = array_ref_up_bound (ref);
782
783 /* The case of nonconstant bounds could be handled, but it would be
784 complicated. */
785 if (TREE_CODE (low) != INTEGER_CST
786 || !high || TREE_CODE (high) != INTEGER_CST)
787 return false;
788
789 /* Check if the intial idx is within bound. */
790 if (wi::to_widest (init) < wi::to_widest (low)
791 || wi::to_widest (init) > wi::to_widest (high))
792 return false;
793
794 /* The idx is always within bound. */
795 if (!step || integer_zerop (step))
796 return true;
797
798 if (!max_loop_iterations (loop, &niter))
799 return false;
800
801 if (wi::to_widest (step) < 0)
802 {
803 delta = wi::to_widest (init) - wi::to_widest (low);
804 wi_step = -wi::to_widest (step);
805 }
806 else
807 {
808 delta = wi::to_widest (high) - wi::to_widest (init);
809 wi_step = wi::to_widest (step);
810 }
811
812 valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow);
813 /* The iteration space of idx is within array bound. */
814 if (!overflow && niter <= valid_niter)
815 return true;
816
817 return false;
818 }
819
820 /* Return TRUE if ref is a within bound array reference. */
821
822 static bool
ref_within_array_bound(gimple * stmt,tree ref)823 ref_within_array_bound (gimple *stmt, tree ref)
824 {
825 struct loop *loop = loop_containing_stmt (stmt);
826
827 gcc_assert (loop != NULL);
828 return for_each_index (&ref, idx_within_array_bound, loop);
829 }
830
831
832 /* Given a memory reference expression T, return TRUE if base object
833 it refers to is writable. The base object of a memory reference
834 is the main object being referenced, which is returned by function
835 get_base_address. */
836
837 static bool
base_object_writable(tree ref)838 base_object_writable (tree ref)
839 {
840 tree base_tree = get_base_address (ref);
841
842 return (base_tree
843 && DECL_P (base_tree)
844 && decl_binds_to_current_def_p (base_tree)
845 && !TREE_READONLY (base_tree));
846 }
847
848 /* Return true when the memory references of STMT won't trap in the
849 if-converted code. There are two things that we have to check for:
850
851 - writes to memory occur to writable memory: if-conversion of
852 memory writes transforms the conditional memory writes into
853 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
854 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
855 be executed at all in the original code, it may be a readonly
856 memory. To check that A is not const-qualified, we check that
857 there exists at least an unconditional write to A in the current
858 function.
859
860 - reads or writes to memory are valid memory accesses for every
861 iteration. To check that the memory accesses are correctly formed
862 and that we are allowed to read and write in these locations, we
863 check that the memory accesses to be if-converted occur at every
864 iteration unconditionally.
865
866 Returns true for the memory reference in STMT, same memory reference
867 is read or written unconditionally atleast once and the base memory
868 reference is written unconditionally once. This is to check reference
869 will not write fault. Also retuns true if the memory reference is
870 unconditionally read once then we are conditionally writing to memory
871 which is defined as read and write and is bound to the definition
872 we are seeing. */
873 static bool
ifcvt_memrefs_wont_trap(gimple * stmt,vec<data_reference_p> drs)874 ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs)
875 {
876 /* If DR didn't see a reference here we can't use it to tell
877 whether the ref traps or not. */
878 if (gimple_uid (stmt) == 0)
879 return false;
880
881 data_reference_p *master_dr, *base_master_dr;
882 data_reference_p a = drs[gimple_uid (stmt) - 1];
883
884 tree base = DR_BASE_OBJECT (a);
885 innermost_loop_behavior *innermost = &DR_INNERMOST (a);
886
887 gcc_assert (DR_STMT (a) == stmt);
888 gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a)
889 || DR_INIT (a) || DR_STEP (a));
890
891 master_dr = innermost_DR_map->get (innermost);
892 gcc_assert (master_dr != NULL);
893
894 base_master_dr = baseref_DR_map->get (base);
895
896 /* If a is unconditionally written to it doesn't trap. */
897 if (DR_W_UNCONDITIONALLY (*master_dr))
898 return true;
899
900 /* If a is unconditionally accessed then ...
901
902 Even a is conditional access, we can treat it as an unconditional
903 one if it's an array reference and all its index are within array
904 bound. */
905 if (DR_RW_UNCONDITIONALLY (*master_dr)
906 || ref_within_array_bound (stmt, DR_REF (a)))
907 {
908 /* an unconditional read won't trap. */
909 if (DR_IS_READ (a))
910 return true;
911
912 /* an unconditionaly write won't trap if the base is written
913 to unconditionally. */
914 if (base_master_dr
915 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
916 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
917 /* or the base is known to be not readonly. */
918 else if (base_object_writable (DR_REF (a)))
919 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
920 }
921
922 return false;
923 }
924
925 /* Return true if STMT could be converted into a masked load or store
926 (conditional load or store based on a mask computed from bb predicate). */
927
928 static bool
ifcvt_can_use_mask_load_store(gimple * stmt)929 ifcvt_can_use_mask_load_store (gimple *stmt)
930 {
931 /* Check whether this is a load or store. */
932 tree lhs = gimple_assign_lhs (stmt);
933 bool is_load;
934 tree ref;
935 if (gimple_store_p (stmt))
936 {
937 if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
938 return false;
939 is_load = false;
940 ref = lhs;
941 }
942 else if (gimple_assign_load_p (stmt))
943 {
944 is_load = true;
945 ref = gimple_assign_rhs1 (stmt);
946 }
947 else
948 return false;
949
950 if (may_be_nonaddressable_p (ref))
951 return false;
952
953 /* Mask should be integer mode of the same size as the load/store
954 mode. */
955 machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
956 if (!int_mode_for_mode (mode).exists () || VECTOR_MODE_P (mode))
957 return false;
958
959 if (can_vec_mask_load_store_p (mode, VOIDmode, is_load))
960 return true;
961
962 return false;
963 }
964
965 /* Return true if STMT could be converted from an operation that is
966 unconditional to one that is conditional on a bb predicate mask. */
967
968 static bool
ifcvt_can_predicate(gimple * stmt)969 ifcvt_can_predicate (gimple *stmt)
970 {
971 basic_block bb = gimple_bb (stmt);
972
973 if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
974 || bb->loop_father->dont_vectorize
975 || gimple_has_volatile_ops (stmt))
976 return false;
977
978 if (gimple_assign_single_p (stmt))
979 return ifcvt_can_use_mask_load_store (stmt);
980
981 tree_code code = gimple_assign_rhs_code (stmt);
982 tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
983 tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
984 if (!types_compatible_p (lhs_type, rhs_type))
985 return false;
986 internal_fn cond_fn = get_conditional_internal_fn (code);
987 return (cond_fn != IFN_LAST
988 && vectorized_internal_fn_supported_p (cond_fn, lhs_type));
989 }
990
991 /* Return true when STMT is if-convertible.
992
993 GIMPLE_ASSIGN statement is not if-convertible if,
994 - it is not movable,
995 - it could trap,
996 - LHS is not var decl. */
997
998 static bool
if_convertible_gimple_assign_stmt_p(gimple * stmt,vec<data_reference_p> refs)999 if_convertible_gimple_assign_stmt_p (gimple *stmt,
1000 vec<data_reference_p> refs)
1001 {
1002 tree lhs = gimple_assign_lhs (stmt);
1003
1004 if (dump_file && (dump_flags & TDF_DETAILS))
1005 {
1006 fprintf (dump_file, "-------------------------\n");
1007 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1008 }
1009
1010 if (!is_gimple_reg_type (TREE_TYPE (lhs)))
1011 return false;
1012
1013 /* Some of these constrains might be too conservative. */
1014 if (stmt_ends_bb_p (stmt)
1015 || gimple_has_volatile_ops (stmt)
1016 || (TREE_CODE (lhs) == SSA_NAME
1017 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1018 || gimple_has_side_effects (stmt))
1019 {
1020 if (dump_file && (dump_flags & TDF_DETAILS))
1021 fprintf (dump_file, "stmt not suitable for ifcvt\n");
1022 return false;
1023 }
1024
1025 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
1026 in between if_convertible_loop_p and combine_blocks
1027 we can perform loop versioning. */
1028 gimple_set_plf (stmt, GF_PLF_2, false);
1029
1030 if ((! gimple_vuse (stmt)
1031 || gimple_could_trap_p_1 (stmt, false, false)
1032 || ! ifcvt_memrefs_wont_trap (stmt, refs))
1033 && gimple_could_trap_p (stmt))
1034 {
1035 if (ifcvt_can_predicate (stmt))
1036 {
1037 gimple_set_plf (stmt, GF_PLF_2, true);
1038 need_to_predicate = true;
1039 return true;
1040 }
1041 if (dump_file && (dump_flags & TDF_DETAILS))
1042 fprintf (dump_file, "tree could trap...\n");
1043 return false;
1044 }
1045
1046 /* When if-converting stores force versioning, likewise if we
1047 ended up generating store data races. */
1048 if (gimple_vdef (stmt))
1049 need_to_predicate = true;
1050
1051 return true;
1052 }
1053
1054 /* Return true when STMT is if-convertible.
1055
1056 A statement is if-convertible if:
1057 - it is an if-convertible GIMPLE_ASSIGN,
1058 - it is a GIMPLE_LABEL or a GIMPLE_COND,
1059 - it is builtins call. */
1060
1061 static bool
if_convertible_stmt_p(gimple * stmt,vec<data_reference_p> refs)1062 if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs)
1063 {
1064 switch (gimple_code (stmt))
1065 {
1066 case GIMPLE_LABEL:
1067 case GIMPLE_DEBUG:
1068 case GIMPLE_COND:
1069 return true;
1070
1071 case GIMPLE_ASSIGN:
1072 return if_convertible_gimple_assign_stmt_p (stmt, refs);
1073
1074 case GIMPLE_CALL:
1075 {
1076 tree fndecl = gimple_call_fndecl (stmt);
1077 if (fndecl)
1078 {
1079 int flags = gimple_call_flags (stmt);
1080 if ((flags & ECF_CONST)
1081 && !(flags & ECF_LOOPING_CONST_OR_PURE)
1082 /* We can only vectorize some builtins at the moment,
1083 so restrict if-conversion to those. */
1084 && fndecl_built_in_p (fndecl))
1085 return true;
1086 }
1087 return false;
1088 }
1089
1090 default:
1091 /* Don't know what to do with 'em so don't do anything. */
1092 if (dump_file && (dump_flags & TDF_DETAILS))
1093 {
1094 fprintf (dump_file, "don't know what to do\n");
1095 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1096 }
1097 return false;
1098 }
1099
1100 return true;
1101 }
1102
1103 /* Assumes that BB has more than 1 predecessors.
1104 Returns false if at least one successor is not on critical edge
1105 and true otherwise. */
1106
1107 static inline bool
all_preds_critical_p(basic_block bb)1108 all_preds_critical_p (basic_block bb)
1109 {
1110 edge e;
1111 edge_iterator ei;
1112
1113 FOR_EACH_EDGE (e, ei, bb->preds)
1114 if (EDGE_COUNT (e->src->succs) == 1)
1115 return false;
1116 return true;
1117 }
1118
1119 /* Return true when BB is if-convertible. This routine does not check
1120 basic block's statements and phis.
1121
1122 A basic block is not if-convertible if:
1123 - it is non-empty and it is after the exit block (in BFS order),
1124 - it is after the exit block but before the latch,
1125 - its edges are not normal.
1126
1127 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1128 inside LOOP. */
1129
1130 static bool
if_convertible_bb_p(struct loop * loop,basic_block bb,basic_block exit_bb)1131 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
1132 {
1133 edge e;
1134 edge_iterator ei;
1135
1136 if (dump_file && (dump_flags & TDF_DETAILS))
1137 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
1138
1139 if (EDGE_COUNT (bb->succs) > 2)
1140 return false;
1141
1142 gimple *last = last_stmt (bb);
1143 if (gcall *call = safe_dyn_cast <gcall *> (last))
1144 if (gimple_call_ctrl_altering_p (call))
1145 return false;
1146
1147 if (exit_bb)
1148 {
1149 if (bb != loop->latch)
1150 {
1151 if (dump_file && (dump_flags & TDF_DETAILS))
1152 fprintf (dump_file, "basic block after exit bb but before latch\n");
1153 return false;
1154 }
1155 else if (!empty_block_p (bb))
1156 {
1157 if (dump_file && (dump_flags & TDF_DETAILS))
1158 fprintf (dump_file, "non empty basic block after exit bb\n");
1159 return false;
1160 }
1161 else if (bb == loop->latch
1162 && bb != exit_bb
1163 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
1164 {
1165 if (dump_file && (dump_flags & TDF_DETAILS))
1166 fprintf (dump_file, "latch is not dominated by exit_block\n");
1167 return false;
1168 }
1169 }
1170
1171 /* Be less adventurous and handle only normal edges. */
1172 FOR_EACH_EDGE (e, ei, bb->succs)
1173 if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
1174 {
1175 if (dump_file && (dump_flags & TDF_DETAILS))
1176 fprintf (dump_file, "Difficult to handle edges\n");
1177 return false;
1178 }
1179
1180 return true;
1181 }
1182
1183 /* Return true when all predecessor blocks of BB are visited. The
1184 VISITED bitmap keeps track of the visited blocks. */
1185
1186 static bool
pred_blocks_visited_p(basic_block bb,bitmap * visited)1187 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1188 {
1189 edge e;
1190 edge_iterator ei;
1191 FOR_EACH_EDGE (e, ei, bb->preds)
1192 if (!bitmap_bit_p (*visited, e->src->index))
1193 return false;
1194
1195 return true;
1196 }
1197
1198 /* Get body of a LOOP in suitable order for if-conversion. It is
1199 caller's responsibility to deallocate basic block list.
1200 If-conversion suitable order is, breadth first sort (BFS) order
1201 with an additional constraint: select a block only if all its
1202 predecessors are already selected. */
1203
1204 static basic_block *
get_loop_body_in_if_conv_order(const struct loop * loop)1205 get_loop_body_in_if_conv_order (const struct loop *loop)
1206 {
1207 basic_block *blocks, *blocks_in_bfs_order;
1208 basic_block bb;
1209 bitmap visited;
1210 unsigned int index = 0;
1211 unsigned int visited_count = 0;
1212
1213 gcc_assert (loop->num_nodes);
1214 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1215
1216 blocks = XCNEWVEC (basic_block, loop->num_nodes);
1217 visited = BITMAP_ALLOC (NULL);
1218
1219 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1220
1221 index = 0;
1222 while (index < loop->num_nodes)
1223 {
1224 bb = blocks_in_bfs_order [index];
1225
1226 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1227 {
1228 free (blocks_in_bfs_order);
1229 BITMAP_FREE (visited);
1230 free (blocks);
1231 return NULL;
1232 }
1233
1234 if (!bitmap_bit_p (visited, bb->index))
1235 {
1236 if (pred_blocks_visited_p (bb, &visited)
1237 || bb == loop->header)
1238 {
1239 /* This block is now visited. */
1240 bitmap_set_bit (visited, bb->index);
1241 blocks[visited_count++] = bb;
1242 }
1243 }
1244
1245 index++;
1246
1247 if (index == loop->num_nodes
1248 && visited_count != loop->num_nodes)
1249 /* Not done yet. */
1250 index = 0;
1251 }
1252 free (blocks_in_bfs_order);
1253 BITMAP_FREE (visited);
1254 return blocks;
1255 }
1256
1257 /* Returns true when the analysis of the predicates for all the basic
1258 blocks in LOOP succeeded.
1259
1260 predicate_bbs first allocates the predicates of the basic blocks.
1261 These fields are then initialized with the tree expressions
1262 representing the predicates under which a basic block is executed
1263 in the LOOP. As the loop->header is executed at each iteration, it
1264 has the "true" predicate. Other statements executed under a
1265 condition are predicated with that condition, for example
1266
1267 | if (x)
1268 | S1;
1269 | else
1270 | S2;
1271
1272 S1 will be predicated with "x", and
1273 S2 will be predicated with "!x". */
1274
1275 static void
predicate_bbs(loop_p loop)1276 predicate_bbs (loop_p loop)
1277 {
1278 unsigned int i;
1279
1280 for (i = 0; i < loop->num_nodes; i++)
1281 init_bb_predicate (ifc_bbs[i]);
1282
1283 for (i = 0; i < loop->num_nodes; i++)
1284 {
1285 basic_block bb = ifc_bbs[i];
1286 tree cond;
1287 gimple *stmt;
1288
1289 /* The loop latch and loop exit block are always executed and
1290 have no extra conditions to be processed: skip them. */
1291 if (bb == loop->latch
1292 || bb_with_exit_edge_p (loop, bb))
1293 {
1294 reset_bb_predicate (bb);
1295 continue;
1296 }
1297
1298 cond = bb_predicate (bb);
1299 stmt = last_stmt (bb);
1300 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1301 {
1302 tree c2;
1303 edge true_edge, false_edge;
1304 location_t loc = gimple_location (stmt);
1305 tree c = build2_loc (loc, gimple_cond_code (stmt),
1306 boolean_type_node,
1307 gimple_cond_lhs (stmt),
1308 gimple_cond_rhs (stmt));
1309
1310 /* Add new condition into destination's predicate list. */
1311 extract_true_false_edges_from_block (gimple_bb (stmt),
1312 &true_edge, &false_edge);
1313
1314 /* If C is true, then TRUE_EDGE is taken. */
1315 add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1316 unshare_expr (c));
1317
1318 /* If C is false, then FALSE_EDGE is taken. */
1319 c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1320 unshare_expr (c));
1321 add_to_dst_predicate_list (loop, false_edge,
1322 unshare_expr (cond), c2);
1323
1324 cond = NULL_TREE;
1325 }
1326
1327 /* If current bb has only one successor, then consider it as an
1328 unconditional goto. */
1329 if (single_succ_p (bb))
1330 {
1331 basic_block bb_n = single_succ (bb);
1332
1333 /* The successor bb inherits the predicate of its
1334 predecessor. If there is no predicate in the predecessor
1335 bb, then consider the successor bb as always executed. */
1336 if (cond == NULL_TREE)
1337 cond = boolean_true_node;
1338
1339 add_to_predicate_list (loop, bb_n, cond);
1340 }
1341 }
1342
1343 /* The loop header is always executed. */
1344 reset_bb_predicate (loop->header);
1345 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1346 && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1347 }
1348
1349 /* Build region by adding loop pre-header and post-header blocks. */
1350
1351 static vec<basic_block>
build_region(struct loop * loop)1352 build_region (struct loop *loop)
1353 {
1354 vec<basic_block> region = vNULL;
1355 basic_block exit_bb = NULL;
1356
1357 gcc_assert (ifc_bbs);
1358 /* The first element is loop pre-header. */
1359 region.safe_push (loop_preheader_edge (loop)->src);
1360
1361 for (unsigned int i = 0; i < loop->num_nodes; i++)
1362 {
1363 basic_block bb = ifc_bbs[i];
1364 region.safe_push (bb);
1365 /* Find loop postheader. */
1366 edge e;
1367 edge_iterator ei;
1368 FOR_EACH_EDGE (e, ei, bb->succs)
1369 if (loop_exit_edge_p (loop, e))
1370 {
1371 exit_bb = e->dest;
1372 break;
1373 }
1374 }
1375 /* The last element is loop post-header. */
1376 gcc_assert (exit_bb);
1377 region.safe_push (exit_bb);
1378 return region;
1379 }
1380
1381 /* Return true when LOOP is if-convertible. This is a helper function
1382 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1383 in if_convertible_loop_p. */
1384
1385 static bool
if_convertible_loop_p_1(struct loop * loop,vec<data_reference_p> * refs)1386 if_convertible_loop_p_1 (struct loop *loop, vec<data_reference_p> *refs)
1387 {
1388 unsigned int i;
1389 basic_block exit_bb = NULL;
1390 vec<basic_block> region;
1391
1392 if (find_data_references_in_loop (loop, refs) == chrec_dont_know)
1393 return false;
1394
1395 calculate_dominance_info (CDI_DOMINATORS);
1396
1397 /* Allow statements that can be handled during if-conversion. */
1398 ifc_bbs = get_loop_body_in_if_conv_order (loop);
1399 if (!ifc_bbs)
1400 {
1401 if (dump_file && (dump_flags & TDF_DETAILS))
1402 fprintf (dump_file, "Irreducible loop\n");
1403 return false;
1404 }
1405
1406 for (i = 0; i < loop->num_nodes; i++)
1407 {
1408 basic_block bb = ifc_bbs[i];
1409
1410 if (!if_convertible_bb_p (loop, bb, exit_bb))
1411 return false;
1412
1413 if (bb_with_exit_edge_p (loop, bb))
1414 exit_bb = bb;
1415 }
1416
1417 for (i = 0; i < loop->num_nodes; i++)
1418 {
1419 basic_block bb = ifc_bbs[i];
1420 gimple_stmt_iterator gsi;
1421
1422 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1423 switch (gimple_code (gsi_stmt (gsi)))
1424 {
1425 case GIMPLE_LABEL:
1426 case GIMPLE_ASSIGN:
1427 case GIMPLE_CALL:
1428 case GIMPLE_DEBUG:
1429 case GIMPLE_COND:
1430 gimple_set_uid (gsi_stmt (gsi), 0);
1431 break;
1432 default:
1433 return false;
1434 }
1435 }
1436
1437 data_reference_p dr;
1438
1439 innermost_DR_map
1440 = new hash_map<innermost_loop_behavior_hash, data_reference_p>;
1441 baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>;
1442
1443 /* Compute post-dominator tree locally. */
1444 region = build_region (loop);
1445 calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region);
1446
1447 predicate_bbs (loop);
1448
1449 /* Free post-dominator tree since it is not used after predication. */
1450 free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region);
1451 region.release ();
1452
1453 for (i = 0; refs->iterate (i, &dr); i++)
1454 {
1455 tree ref = DR_REF (dr);
1456
1457 dr->aux = XNEW (struct ifc_dr);
1458 DR_BASE_W_UNCONDITIONALLY (dr) = false;
1459 DR_RW_UNCONDITIONALLY (dr) = false;
1460 DR_W_UNCONDITIONALLY (dr) = false;
1461 IFC_DR (dr)->rw_predicate = boolean_false_node;
1462 IFC_DR (dr)->w_predicate = boolean_false_node;
1463 IFC_DR (dr)->base_w_predicate = boolean_false_node;
1464 if (gimple_uid (DR_STMT (dr)) == 0)
1465 gimple_set_uid (DR_STMT (dr), i + 1);
1466
1467 /* If DR doesn't have innermost loop behavior or it's a compound
1468 memory reference, we synthesize its innermost loop behavior
1469 for hashing. */
1470 if (TREE_CODE (ref) == COMPONENT_REF
1471 || TREE_CODE (ref) == IMAGPART_EXPR
1472 || TREE_CODE (ref) == REALPART_EXPR
1473 || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr)
1474 || DR_INIT (dr) || DR_STEP (dr)))
1475 {
1476 while (TREE_CODE (ref) == COMPONENT_REF
1477 || TREE_CODE (ref) == IMAGPART_EXPR
1478 || TREE_CODE (ref) == REALPART_EXPR)
1479 ref = TREE_OPERAND (ref, 0);
1480
1481 memset (&DR_INNERMOST (dr), 0, sizeof (DR_INNERMOST (dr)));
1482 DR_BASE_ADDRESS (dr) = ref;
1483 }
1484 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr);
1485 }
1486
1487 for (i = 0; i < loop->num_nodes; i++)
1488 {
1489 basic_block bb = ifc_bbs[i];
1490 gimple_stmt_iterator itr;
1491
1492 /* Check the if-convertibility of statements in predicated BBs. */
1493 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1494 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1495 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
1496 return false;
1497 }
1498
1499 /* Checking PHIs needs to be done after stmts, as the fact whether there
1500 are any masked loads or stores affects the tests. */
1501 for (i = 0; i < loop->num_nodes; i++)
1502 {
1503 basic_block bb = ifc_bbs[i];
1504 gphi_iterator itr;
1505
1506 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1507 if (!if_convertible_phi_p (loop, bb, itr.phi ()))
1508 return false;
1509 }
1510
1511 if (dump_file)
1512 fprintf (dump_file, "Applying if-conversion\n");
1513
1514 return true;
1515 }
1516
1517 /* Return true when LOOP is if-convertible.
1518 LOOP is if-convertible if:
1519 - it is innermost,
1520 - it has two or more basic blocks,
1521 - it has only one exit,
1522 - loop header is not the exit edge,
1523 - if its basic blocks and phi nodes are if convertible. */
1524
1525 static bool
if_convertible_loop_p(struct loop * loop)1526 if_convertible_loop_p (struct loop *loop)
1527 {
1528 edge e;
1529 edge_iterator ei;
1530 bool res = false;
1531 vec<data_reference_p> refs;
1532
1533 /* Handle only innermost loop. */
1534 if (!loop || loop->inner)
1535 {
1536 if (dump_file && (dump_flags & TDF_DETAILS))
1537 fprintf (dump_file, "not innermost loop\n");
1538 return false;
1539 }
1540
1541 /* If only one block, no need for if-conversion. */
1542 if (loop->num_nodes <= 2)
1543 {
1544 if (dump_file && (dump_flags & TDF_DETAILS))
1545 fprintf (dump_file, "less than 2 basic blocks\n");
1546 return false;
1547 }
1548
1549 /* More than one loop exit is too much to handle. */
1550 if (!single_exit (loop))
1551 {
1552 if (dump_file && (dump_flags & TDF_DETAILS))
1553 fprintf (dump_file, "multiple exits\n");
1554 return false;
1555 }
1556
1557 /* If one of the loop header's edge is an exit edge then do not
1558 apply if-conversion. */
1559 FOR_EACH_EDGE (e, ei, loop->header->succs)
1560 if (loop_exit_edge_p (loop, e))
1561 return false;
1562
1563 refs.create (5);
1564 res = if_convertible_loop_p_1 (loop, &refs);
1565
1566 data_reference_p dr;
1567 unsigned int i;
1568 for (i = 0; refs.iterate (i, &dr); i++)
1569 free (dr->aux);
1570
1571 free_data_refs (refs);
1572
1573 delete innermost_DR_map;
1574 innermost_DR_map = NULL;
1575
1576 delete baseref_DR_map;
1577 baseref_DR_map = NULL;
1578
1579 return res;
1580 }
1581
1582 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1583 which is in predicated basic block.
1584 In fact, the following PHI pattern is searching:
1585 loop-header:
1586 reduc_1 = PHI <..., reduc_2>
1587 ...
1588 if (...)
1589 reduc_3 = ...
1590 reduc_2 = PHI <reduc_1, reduc_3>
1591
1592 ARG_0 and ARG_1 are correspondent PHI arguments.
1593 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1594 EXTENDED is true if PHI has > 2 arguments. */
1595
1596 static bool
is_cond_scalar_reduction(gimple * phi,gimple ** reduc,tree arg_0,tree arg_1,tree * op0,tree * op1,bool extended)1597 is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1,
1598 tree *op0, tree *op1, bool extended)
1599 {
1600 tree lhs, r_op1, r_op2;
1601 gimple *stmt;
1602 gimple *header_phi = NULL;
1603 enum tree_code reduction_op;
1604 basic_block bb = gimple_bb (phi);
1605 struct loop *loop = bb->loop_father;
1606 edge latch_e = loop_latch_edge (loop);
1607 imm_use_iterator imm_iter;
1608 use_operand_p use_p;
1609 edge e;
1610 edge_iterator ei;
1611 bool result = false;
1612 if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
1613 return false;
1614
1615 if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
1616 {
1617 lhs = arg_1;
1618 header_phi = SSA_NAME_DEF_STMT (arg_0);
1619 stmt = SSA_NAME_DEF_STMT (arg_1);
1620 }
1621 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
1622 {
1623 lhs = arg_0;
1624 header_phi = SSA_NAME_DEF_STMT (arg_1);
1625 stmt = SSA_NAME_DEF_STMT (arg_0);
1626 }
1627 else
1628 return false;
1629 if (gimple_bb (header_phi) != loop->header)
1630 return false;
1631
1632 if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
1633 return false;
1634
1635 if (gimple_code (stmt) != GIMPLE_ASSIGN
1636 || gimple_has_volatile_ops (stmt))
1637 return false;
1638
1639 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1640 return false;
1641
1642 if (!is_predicated (gimple_bb (stmt)))
1643 return false;
1644
1645 /* Check that stmt-block is predecessor of phi-block. */
1646 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1647 if (e->dest == bb)
1648 {
1649 result = true;
1650 break;
1651 }
1652 if (!result)
1653 return false;
1654
1655 if (!has_single_use (lhs))
1656 return false;
1657
1658 reduction_op = gimple_assign_rhs_code (stmt);
1659 if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
1660 return false;
1661 r_op1 = gimple_assign_rhs1 (stmt);
1662 r_op2 = gimple_assign_rhs2 (stmt);
1663
1664 /* Make R_OP1 to hold reduction variable. */
1665 if (r_op2 == PHI_RESULT (header_phi)
1666 && reduction_op == PLUS_EXPR)
1667 std::swap (r_op1, r_op2);
1668 else if (r_op1 != PHI_RESULT (header_phi))
1669 return false;
1670
1671 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1672 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
1673 {
1674 gimple *use_stmt = USE_STMT (use_p);
1675 if (is_gimple_debug (use_stmt))
1676 continue;
1677 if (use_stmt == stmt)
1678 continue;
1679 if (gimple_code (use_stmt) != GIMPLE_PHI)
1680 return false;
1681 }
1682
1683 *op0 = r_op1; *op1 = r_op2;
1684 *reduc = stmt;
1685 return true;
1686 }
1687
1688 /* Converts conditional scalar reduction into unconditional form, e.g.
1689 bb_4
1690 if (_5 != 0) goto bb_5 else goto bb_6
1691 end_bb_4
1692 bb_5
1693 res_6 = res_13 + 1;
1694 end_bb_5
1695 bb_6
1696 # res_2 = PHI <res_13(4), res_6(5)>
1697 end_bb_6
1698
1699 will be converted into sequence
1700 _ifc__1 = _5 != 0 ? 1 : 0;
1701 res_2 = res_13 + _ifc__1;
1702 Argument SWAP tells that arguments of conditional expression should be
1703 swapped.
1704 Returns rhs of resulting PHI assignment. */
1705
1706 static tree
convert_scalar_cond_reduction(gimple * reduc,gimple_stmt_iterator * gsi,tree cond,tree op0,tree op1,bool swap)1707 convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi,
1708 tree cond, tree op0, tree op1, bool swap)
1709 {
1710 gimple_stmt_iterator stmt_it;
1711 gimple *new_assign;
1712 tree rhs;
1713 tree rhs1 = gimple_assign_rhs1 (reduc);
1714 tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
1715 tree c;
1716 tree zero = build_zero_cst (TREE_TYPE (rhs1));
1717
1718 if (dump_file && (dump_flags & TDF_DETAILS))
1719 {
1720 fprintf (dump_file, "Found cond scalar reduction.\n");
1721 print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
1722 }
1723
1724 /* Build cond expression using COND and constant operand
1725 of reduction rhs. */
1726 c = fold_build_cond_expr (TREE_TYPE (rhs1),
1727 unshare_expr (cond),
1728 swap ? zero : op1,
1729 swap ? op1 : zero);
1730
1731 /* Create assignment stmt and insert it at GSI. */
1732 new_assign = gimple_build_assign (tmp, c);
1733 gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
1734 /* Build rhs for unconditional increment/decrement. */
1735 rhs = fold_build2 (gimple_assign_rhs_code (reduc),
1736 TREE_TYPE (rhs1), op0, tmp);
1737
1738 /* Delete original reduction stmt. */
1739 stmt_it = gsi_for_stmt (reduc);
1740 gsi_remove (&stmt_it, true);
1741 release_defs (reduc);
1742 return rhs;
1743 }
1744
1745 /* Produce condition for all occurrences of ARG in PHI node. */
1746
1747 static tree
gen_phi_arg_condition(gphi * phi,vec<int> * occur,gimple_stmt_iterator * gsi)1748 gen_phi_arg_condition (gphi *phi, vec<int> *occur,
1749 gimple_stmt_iterator *gsi)
1750 {
1751 int len;
1752 int i;
1753 tree cond = NULL_TREE;
1754 tree c;
1755 edge e;
1756
1757 len = occur->length ();
1758 gcc_assert (len > 0);
1759 for (i = 0; i < len; i++)
1760 {
1761 e = gimple_phi_arg_edge (phi, (*occur)[i]);
1762 c = bb_predicate (e->src);
1763 if (is_true_predicate (c))
1764 {
1765 cond = c;
1766 break;
1767 }
1768 c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c),
1769 is_gimple_condexpr, NULL_TREE,
1770 true, GSI_SAME_STMT);
1771 if (cond != NULL_TREE)
1772 {
1773 /* Must build OR expression. */
1774 cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
1775 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1776 is_gimple_condexpr, NULL_TREE,
1777 true, GSI_SAME_STMT);
1778 }
1779 else
1780 cond = c;
1781 }
1782 gcc_assert (cond != NULL_TREE);
1783 return cond;
1784 }
1785
1786 /* Local valueization callback that follows all-use SSA edges. */
1787
1788 static tree
ifcvt_follow_ssa_use_edges(tree val)1789 ifcvt_follow_ssa_use_edges (tree val)
1790 {
1791 return val;
1792 }
1793
1794 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1795 This routine can handle PHI nodes with more than two arguments.
1796
1797 For example,
1798 S1: A = PHI <x1(1), x2(5)>
1799 is converted into,
1800 S2: A = cond ? x1 : x2;
1801
1802 The generated code is inserted at GSI that points to the top of
1803 basic block's statement list.
1804 If PHI node has more than two arguments a chain of conditional
1805 expression is produced. */
1806
1807
1808 static void
predicate_scalar_phi(gphi * phi,gimple_stmt_iterator * gsi)1809 predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
1810 {
1811 gimple *new_stmt = NULL, *reduc;
1812 tree rhs, res, arg0, arg1, op0, op1, scev;
1813 tree cond;
1814 unsigned int index0;
1815 unsigned int max, args_len;
1816 edge e;
1817 basic_block bb;
1818 unsigned int i;
1819
1820 res = gimple_phi_result (phi);
1821 if (virtual_operand_p (res))
1822 return;
1823
1824 if ((rhs = degenerate_phi_result (phi))
1825 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
1826 res))
1827 && !chrec_contains_undetermined (scev)
1828 && scev != res
1829 && (rhs = gimple_phi_arg_def (phi, 0))))
1830 {
1831 if (dump_file && (dump_flags & TDF_DETAILS))
1832 {
1833 fprintf (dump_file, "Degenerate phi!\n");
1834 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
1835 }
1836 new_stmt = gimple_build_assign (res, rhs);
1837 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1838 update_stmt (new_stmt);
1839 return;
1840 }
1841
1842 bb = gimple_bb (phi);
1843 if (EDGE_COUNT (bb->preds) == 2)
1844 {
1845 /* Predicate ordinary PHI node with 2 arguments. */
1846 edge first_edge, second_edge;
1847 basic_block true_bb;
1848 first_edge = EDGE_PRED (bb, 0);
1849 second_edge = EDGE_PRED (bb, 1);
1850 cond = bb_predicate (first_edge->src);
1851 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1852 std::swap (first_edge, second_edge);
1853 if (EDGE_COUNT (first_edge->src->succs) > 1)
1854 {
1855 cond = bb_predicate (second_edge->src);
1856 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1857 cond = TREE_OPERAND (cond, 0);
1858 else
1859 first_edge = second_edge;
1860 }
1861 else
1862 cond = bb_predicate (first_edge->src);
1863 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1864 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1865 is_gimple_condexpr, NULL_TREE,
1866 true, GSI_SAME_STMT);
1867 true_bb = first_edge->src;
1868 if (EDGE_PRED (bb, 1)->src == true_bb)
1869 {
1870 arg0 = gimple_phi_arg_def (phi, 1);
1871 arg1 = gimple_phi_arg_def (phi, 0);
1872 }
1873 else
1874 {
1875 arg0 = gimple_phi_arg_def (phi, 0);
1876 arg1 = gimple_phi_arg_def (phi, 1);
1877 }
1878 if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
1879 &op0, &op1, false))
1880 /* Convert reduction stmt into vectorizable form. */
1881 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1882 true_bb != gimple_bb (reduc));
1883 else
1884 /* Build new RHS using selected condition and arguments. */
1885 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1886 arg0, arg1);
1887 new_stmt = gimple_build_assign (res, rhs);
1888 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1889 gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt);
1890 if (fold_stmt (&new_gsi, ifcvt_follow_ssa_use_edges))
1891 {
1892 new_stmt = gsi_stmt (new_gsi);
1893 update_stmt (new_stmt);
1894 }
1895
1896 if (dump_file && (dump_flags & TDF_DETAILS))
1897 {
1898 fprintf (dump_file, "new phi replacement stmt\n");
1899 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1900 }
1901 return;
1902 }
1903
1904 /* Create hashmap for PHI node which contain vector of argument indexes
1905 having the same value. */
1906 bool swap = false;
1907 hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
1908 unsigned int num_args = gimple_phi_num_args (phi);
1909 int max_ind = -1;
1910 /* Vector of different PHI argument values. */
1911 auto_vec<tree> args (num_args);
1912
1913 /* Compute phi_arg_map. */
1914 for (i = 0; i < num_args; i++)
1915 {
1916 tree arg;
1917
1918 arg = gimple_phi_arg_def (phi, i);
1919 if (!phi_arg_map.get (arg))
1920 args.quick_push (arg);
1921 phi_arg_map.get_or_insert (arg).safe_push (i);
1922 }
1923
1924 /* Determine element with max number of occurrences. */
1925 max_ind = -1;
1926 max = 1;
1927 args_len = args.length ();
1928 for (i = 0; i < args_len; i++)
1929 {
1930 unsigned int len;
1931 if ((len = phi_arg_map.get (args[i])->length ()) > max)
1932 {
1933 max_ind = (int) i;
1934 max = len;
1935 }
1936 }
1937
1938 /* Put element with max number of occurences to the end of ARGS. */
1939 if (max_ind != -1 && max_ind +1 != (int) args_len)
1940 std::swap (args[args_len - 1], args[max_ind]);
1941
1942 /* Handle one special case when number of arguments with different values
1943 is equal 2 and one argument has the only occurrence. Such PHI can be
1944 handled as if would have only 2 arguments. */
1945 if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1)
1946 {
1947 vec<int> *indexes;
1948 indexes = phi_arg_map.get (args[0]);
1949 index0 = (*indexes)[0];
1950 arg0 = args[0];
1951 arg1 = args[1];
1952 e = gimple_phi_arg_edge (phi, index0);
1953 cond = bb_predicate (e->src);
1954 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1955 {
1956 swap = true;
1957 cond = TREE_OPERAND (cond, 0);
1958 }
1959 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1960 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1961 is_gimple_condexpr, NULL_TREE,
1962 true, GSI_SAME_STMT);
1963 if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
1964 &op0, &op1, true)))
1965 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1966 swap? arg1 : arg0,
1967 swap? arg0 : arg1);
1968 else
1969 /* Convert reduction stmt into vectorizable form. */
1970 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1971 swap);
1972 new_stmt = gimple_build_assign (res, rhs);
1973 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1974 update_stmt (new_stmt);
1975 }
1976 else
1977 {
1978 /* Common case. */
1979 vec<int> *indexes;
1980 tree type = TREE_TYPE (gimple_phi_result (phi));
1981 tree lhs;
1982 arg1 = args[1];
1983 for (i = 0; i < args_len; i++)
1984 {
1985 arg0 = args[i];
1986 indexes = phi_arg_map.get (args[i]);
1987 if (i != args_len - 1)
1988 lhs = make_temp_ssa_name (type, NULL, "_ifc_");
1989 else
1990 lhs = res;
1991 cond = gen_phi_arg_condition (phi, indexes, gsi);
1992 rhs = fold_build_cond_expr (type, unshare_expr (cond),
1993 arg0, arg1);
1994 new_stmt = gimple_build_assign (lhs, rhs);
1995 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1996 update_stmt (new_stmt);
1997 arg1 = lhs;
1998 }
1999 }
2000
2001 if (dump_file && (dump_flags & TDF_DETAILS))
2002 {
2003 fprintf (dump_file, "new extended phi replacement stmt\n");
2004 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
2005 }
2006 }
2007
2008 /* Replaces in LOOP all the scalar phi nodes other than those in the
2009 LOOP->header block with conditional modify expressions. */
2010
2011 static void
predicate_all_scalar_phis(struct loop * loop)2012 predicate_all_scalar_phis (struct loop *loop)
2013 {
2014 basic_block bb;
2015 unsigned int orig_loop_num_nodes = loop->num_nodes;
2016 unsigned int i;
2017
2018 for (i = 1; i < orig_loop_num_nodes; i++)
2019 {
2020 gphi *phi;
2021 gimple_stmt_iterator gsi;
2022 gphi_iterator phi_gsi;
2023 bb = ifc_bbs[i];
2024
2025 if (bb == loop->header)
2026 continue;
2027
2028 phi_gsi = gsi_start_phis (bb);
2029 if (gsi_end_p (phi_gsi))
2030 continue;
2031
2032 gsi = gsi_after_labels (bb);
2033 while (!gsi_end_p (phi_gsi))
2034 {
2035 phi = phi_gsi.phi ();
2036 if (virtual_operand_p (gimple_phi_result (phi)))
2037 gsi_next (&phi_gsi);
2038 else
2039 {
2040 predicate_scalar_phi (phi, &gsi);
2041 remove_phi_node (&phi_gsi, false);
2042 }
2043 }
2044 }
2045 }
2046
2047 /* Insert in each basic block of LOOP the statements produced by the
2048 gimplification of the predicates. */
2049
2050 static void
insert_gimplified_predicates(loop_p loop)2051 insert_gimplified_predicates (loop_p loop)
2052 {
2053 unsigned int i;
2054
2055 for (i = 0; i < loop->num_nodes; i++)
2056 {
2057 basic_block bb = ifc_bbs[i];
2058 gimple_seq stmts;
2059 if (!is_predicated (bb))
2060 gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
2061 if (!is_predicated (bb))
2062 {
2063 /* Do not insert statements for a basic block that is not
2064 predicated. Also make sure that the predicate of the
2065 basic block is set to true. */
2066 reset_bb_predicate (bb);
2067 continue;
2068 }
2069
2070 stmts = bb_predicate_gimplified_stmts (bb);
2071 if (stmts)
2072 {
2073 if (need_to_predicate)
2074 {
2075 /* Insert the predicate of the BB just after the label,
2076 as the if-conversion of memory writes will use this
2077 predicate. */
2078 gimple_stmt_iterator gsi = gsi_after_labels (bb);
2079 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2080 }
2081 else
2082 {
2083 /* Insert the predicate of the BB at the end of the BB
2084 as this would reduce the register pressure: the only
2085 use of this predicate will be in successor BBs. */
2086 gimple_stmt_iterator gsi = gsi_last_bb (bb);
2087
2088 if (gsi_end_p (gsi)
2089 || stmt_ends_bb_p (gsi_stmt (gsi)))
2090 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2091 else
2092 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
2093 }
2094
2095 /* Once the sequence is code generated, set it to NULL. */
2096 set_bb_predicate_gimplified_stmts (bb, NULL);
2097 }
2098 }
2099 }
2100
2101 /* Helper function for predicate_statements. Returns index of existent
2102 mask if it was created for given SIZE and -1 otherwise. */
2103
2104 static int
mask_exists(int size,vec<int> vec)2105 mask_exists (int size, vec<int> vec)
2106 {
2107 unsigned int ix;
2108 int v;
2109 FOR_EACH_VEC_ELT (vec, ix, v)
2110 if (v == size)
2111 return (int) ix;
2112 return -1;
2113 }
2114
2115 /* Helper function for predicate_statements. STMT is a memory read or
2116 write and it needs to be predicated by MASK. Return a statement
2117 that does so. */
2118
2119 static gimple *
predicate_load_or_store(gimple_stmt_iterator * gsi,gassign * stmt,tree mask)2120 predicate_load_or_store (gimple_stmt_iterator *gsi, gassign *stmt, tree mask)
2121 {
2122 gcall *new_stmt;
2123
2124 tree lhs = gimple_assign_lhs (stmt);
2125 tree rhs = gimple_assign_rhs1 (stmt);
2126 tree ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
2127 mark_addressable (ref);
2128 tree addr = force_gimple_operand_gsi (gsi, build_fold_addr_expr (ref),
2129 true, NULL_TREE, true, GSI_SAME_STMT);
2130 tree ptr = build_int_cst (reference_alias_ptr_type (ref),
2131 get_object_alignment (ref));
2132 /* Copy points-to info if possible. */
2133 if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
2134 copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
2135 ref);
2136 if (TREE_CODE (lhs) == SSA_NAME)
2137 {
2138 new_stmt
2139 = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
2140 ptr, mask);
2141 gimple_call_set_lhs (new_stmt, lhs);
2142 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
2143 }
2144 else
2145 {
2146 new_stmt
2147 = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
2148 mask, rhs);
2149 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
2150 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
2151 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
2152 }
2153 gimple_call_set_nothrow (new_stmt, true);
2154 return new_stmt;
2155 }
2156
2157 /* STMT uses OP_LHS. Check whether it is equivalent to:
2158
2159 ... = OP_MASK ? OP_LHS : X;
2160
2161 Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is
2162 known to have value OP_COND. */
2163
2164 static tree
check_redundant_cond_expr(gimple * stmt,tree op_mask,tree op_cond,tree op_lhs)2165 check_redundant_cond_expr (gimple *stmt, tree op_mask, tree op_cond,
2166 tree op_lhs)
2167 {
2168 gassign *assign = dyn_cast <gassign *> (stmt);
2169 if (!assign || gimple_assign_rhs_code (assign) != COND_EXPR)
2170 return NULL_TREE;
2171
2172 tree use_cond = gimple_assign_rhs1 (assign);
2173 tree if_true = gimple_assign_rhs2 (assign);
2174 tree if_false = gimple_assign_rhs3 (assign);
2175
2176 if ((use_cond == op_mask || operand_equal_p (use_cond, op_cond, 0))
2177 && if_true == op_lhs)
2178 return if_false;
2179
2180 if (inverse_conditions_p (use_cond, op_cond) && if_false == op_lhs)
2181 return if_true;
2182
2183 return NULL_TREE;
2184 }
2185
2186 /* Return true if VALUE is available for use at STMT. SSA_NAMES is
2187 the set of SSA names defined earlier in STMT's block. */
2188
2189 static bool
value_available_p(gimple * stmt,hash_set<tree_ssa_name_hash> * ssa_names,tree value)2190 value_available_p (gimple *stmt, hash_set<tree_ssa_name_hash> *ssa_names,
2191 tree value)
2192 {
2193 if (is_gimple_min_invariant (value))
2194 return true;
2195
2196 if (TREE_CODE (value) == SSA_NAME)
2197 {
2198 if (SSA_NAME_IS_DEFAULT_DEF (value))
2199 return true;
2200
2201 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value));
2202 basic_block use_bb = gimple_bb (stmt);
2203 return (def_bb == use_bb
2204 ? ssa_names->contains (value)
2205 : dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
2206 }
2207
2208 return false;
2209 }
2210
2211 /* Helper function for predicate_statements. STMT is a potentially-trapping
2212 arithmetic operation that needs to be predicated by MASK, an SSA_NAME that
2213 has value COND. Return a statement that does so. SSA_NAMES is the set of
2214 SSA names defined earlier in STMT's block. */
2215
2216 static gimple *
predicate_rhs_code(gassign * stmt,tree mask,tree cond,hash_set<tree_ssa_name_hash> * ssa_names)2217 predicate_rhs_code (gassign *stmt, tree mask, tree cond,
2218 hash_set<tree_ssa_name_hash> *ssa_names)
2219 {
2220 tree lhs = gimple_assign_lhs (stmt);
2221 tree_code code = gimple_assign_rhs_code (stmt);
2222 unsigned int nops = gimple_num_ops (stmt);
2223 internal_fn cond_fn = get_conditional_internal_fn (code);
2224
2225 /* Construct the arguments to the conditional internal function. */
2226 auto_vec<tree, 8> args;
2227 args.safe_grow (nops + 1);
2228 args[0] = mask;
2229 for (unsigned int i = 1; i < nops; ++i)
2230 args[i] = gimple_op (stmt, i);
2231 args[nops] = NULL_TREE;
2232
2233 /* Look for uses of the result to see whether they are COND_EXPRs that can
2234 be folded into the conditional call. */
2235 imm_use_iterator imm_iter;
2236 gimple *use_stmt;
2237 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
2238 {
2239 tree new_else = check_redundant_cond_expr (use_stmt, mask, cond, lhs);
2240 if (new_else && value_available_p (stmt, ssa_names, new_else))
2241 {
2242 if (!args[nops])
2243 args[nops] = new_else;
2244 if (operand_equal_p (new_else, args[nops], 0))
2245 {
2246 /* We have:
2247
2248 LHS = IFN_COND (MASK, ..., ELSE);
2249 X = MASK ? LHS : ELSE;
2250
2251 which makes X equivalent to LHS. */
2252 tree use_lhs = gimple_assign_lhs (use_stmt);
2253 redundant_ssa_names.safe_push (std::make_pair (use_lhs, lhs));
2254 }
2255 }
2256 }
2257 if (!args[nops])
2258 args[nops] = targetm.preferred_else_value (cond_fn, TREE_TYPE (lhs),
2259 nops - 1, &args[1]);
2260
2261 /* Create and insert the call. */
2262 gcall *new_stmt = gimple_build_call_internal_vec (cond_fn, args);
2263 gimple_call_set_lhs (new_stmt, lhs);
2264 gimple_call_set_nothrow (new_stmt, true);
2265
2266 return new_stmt;
2267 }
2268
2269 /* Predicate each write to memory in LOOP.
2270
2271 This function transforms control flow constructs containing memory
2272 writes of the form:
2273
2274 | for (i = 0; i < N; i++)
2275 | if (cond)
2276 | A[i] = expr;
2277
2278 into the following form that does not contain control flow:
2279
2280 | for (i = 0; i < N; i++)
2281 | A[i] = cond ? expr : A[i];
2282
2283 The original CFG looks like this:
2284
2285 | bb_0
2286 | i = 0
2287 | end_bb_0
2288 |
2289 | bb_1
2290 | if (i < N) goto bb_5 else goto bb_2
2291 | end_bb_1
2292 |
2293 | bb_2
2294 | cond = some_computation;
2295 | if (cond) goto bb_3 else goto bb_4
2296 | end_bb_2
2297 |
2298 | bb_3
2299 | A[i] = expr;
2300 | goto bb_4
2301 | end_bb_3
2302 |
2303 | bb_4
2304 | goto bb_1
2305 | end_bb_4
2306
2307 insert_gimplified_predicates inserts the computation of the COND
2308 expression at the beginning of the destination basic block:
2309
2310 | bb_0
2311 | i = 0
2312 | end_bb_0
2313 |
2314 | bb_1
2315 | if (i < N) goto bb_5 else goto bb_2
2316 | end_bb_1
2317 |
2318 | bb_2
2319 | cond = some_computation;
2320 | if (cond) goto bb_3 else goto bb_4
2321 | end_bb_2
2322 |
2323 | bb_3
2324 | cond = some_computation;
2325 | A[i] = expr;
2326 | goto bb_4
2327 | end_bb_3
2328 |
2329 | bb_4
2330 | goto bb_1
2331 | end_bb_4
2332
2333 predicate_statements is then predicating the memory write as follows:
2334
2335 | bb_0
2336 | i = 0
2337 | end_bb_0
2338 |
2339 | bb_1
2340 | if (i < N) goto bb_5 else goto bb_2
2341 | end_bb_1
2342 |
2343 | bb_2
2344 | if (cond) goto bb_3 else goto bb_4
2345 | end_bb_2
2346 |
2347 | bb_3
2348 | cond = some_computation;
2349 | A[i] = cond ? expr : A[i];
2350 | goto bb_4
2351 | end_bb_3
2352 |
2353 | bb_4
2354 | goto bb_1
2355 | end_bb_4
2356
2357 and finally combine_blocks removes the basic block boundaries making
2358 the loop vectorizable:
2359
2360 | bb_0
2361 | i = 0
2362 | if (i < N) goto bb_5 else goto bb_1
2363 | end_bb_0
2364 |
2365 | bb_1
2366 | cond = some_computation;
2367 | A[i] = cond ? expr : A[i];
2368 | if (i < N) goto bb_5 else goto bb_4
2369 | end_bb_1
2370 |
2371 | bb_4
2372 | goto bb_1
2373 | end_bb_4
2374 */
2375
2376 static void
predicate_statements(loop_p loop)2377 predicate_statements (loop_p loop)
2378 {
2379 unsigned int i, orig_loop_num_nodes = loop->num_nodes;
2380 auto_vec<int, 1> vect_sizes;
2381 auto_vec<tree, 1> vect_masks;
2382 hash_set<tree_ssa_name_hash> ssa_names;
2383
2384 for (i = 1; i < orig_loop_num_nodes; i++)
2385 {
2386 gimple_stmt_iterator gsi;
2387 basic_block bb = ifc_bbs[i];
2388 tree cond = bb_predicate (bb);
2389 bool swap;
2390 int index;
2391
2392 if (is_true_predicate (cond))
2393 continue;
2394
2395 swap = false;
2396 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2397 {
2398 swap = true;
2399 cond = TREE_OPERAND (cond, 0);
2400 }
2401
2402 vect_sizes.truncate (0);
2403 vect_masks.truncate (0);
2404
2405 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2406 {
2407 gassign *stmt = dyn_cast <gassign *> (gsi_stmt (gsi));
2408 if (!stmt)
2409 ;
2410 else if (is_false_predicate (cond)
2411 && gimple_vdef (stmt))
2412 {
2413 unlink_stmt_vdef (stmt);
2414 gsi_remove (&gsi, true);
2415 release_defs (stmt);
2416 continue;
2417 }
2418 else if (gimple_plf (stmt, GF_PLF_2))
2419 {
2420 tree lhs = gimple_assign_lhs (stmt);
2421 tree mask;
2422 gimple *new_stmt;
2423 gimple_seq stmts = NULL;
2424 machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
2425 /* We checked before setting GF_PLF_2 that an equivalent
2426 integer mode exists. */
2427 int bitsize = GET_MODE_BITSIZE (mode).to_constant ();
2428 if (!vect_sizes.is_empty ()
2429 && (index = mask_exists (bitsize, vect_sizes)) != -1)
2430 /* Use created mask. */
2431 mask = vect_masks[index];
2432 else
2433 {
2434 if (COMPARISON_CLASS_P (cond))
2435 mask = gimple_build (&stmts, TREE_CODE (cond),
2436 boolean_type_node,
2437 TREE_OPERAND (cond, 0),
2438 TREE_OPERAND (cond, 1));
2439 else
2440 mask = cond;
2441
2442 if (swap)
2443 {
2444 tree true_val
2445 = constant_boolean_node (true, TREE_TYPE (mask));
2446 mask = gimple_build (&stmts, BIT_XOR_EXPR,
2447 TREE_TYPE (mask), mask, true_val);
2448 }
2449 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2450
2451 /* Save mask and its size for further use. */
2452 vect_sizes.safe_push (bitsize);
2453 vect_masks.safe_push (mask);
2454 }
2455 if (gimple_assign_single_p (stmt))
2456 new_stmt = predicate_load_or_store (&gsi, stmt, mask);
2457 else
2458 new_stmt = predicate_rhs_code (stmt, mask, cond, &ssa_names);
2459
2460 gsi_replace (&gsi, new_stmt, true);
2461 }
2462 else if (gimple_vdef (stmt))
2463 {
2464 tree lhs = gimple_assign_lhs (stmt);
2465 tree rhs = gimple_assign_rhs1 (stmt);
2466 tree type = TREE_TYPE (lhs);
2467
2468 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
2469 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
2470 if (swap)
2471 std::swap (lhs, rhs);
2472 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
2473 is_gimple_condexpr, NULL_TREE,
2474 true, GSI_SAME_STMT);
2475 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
2476 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
2477 update_stmt (stmt);
2478 }
2479 tree lhs = gimple_get_lhs (gsi_stmt (gsi));
2480 if (lhs && TREE_CODE (lhs) == SSA_NAME)
2481 ssa_names.add (lhs);
2482 gsi_next (&gsi);
2483 }
2484 ssa_names.empty ();
2485 }
2486 }
2487
2488 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2489 other than the exit and latch of the LOOP. Also resets the
2490 GIMPLE_DEBUG information. */
2491
2492 static void
remove_conditions_and_labels(loop_p loop)2493 remove_conditions_and_labels (loop_p loop)
2494 {
2495 gimple_stmt_iterator gsi;
2496 unsigned int i;
2497
2498 for (i = 0; i < loop->num_nodes; i++)
2499 {
2500 basic_block bb = ifc_bbs[i];
2501
2502 if (bb_with_exit_edge_p (loop, bb)
2503 || bb == loop->latch)
2504 continue;
2505
2506 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2507 switch (gimple_code (gsi_stmt (gsi)))
2508 {
2509 case GIMPLE_COND:
2510 case GIMPLE_LABEL:
2511 gsi_remove (&gsi, true);
2512 break;
2513
2514 case GIMPLE_DEBUG:
2515 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2516 if (gimple_debug_bind_p (gsi_stmt (gsi)))
2517 {
2518 gimple_debug_bind_reset_value (gsi_stmt (gsi));
2519 update_stmt (gsi_stmt (gsi));
2520 }
2521 gsi_next (&gsi);
2522 break;
2523
2524 default:
2525 gsi_next (&gsi);
2526 }
2527 }
2528 }
2529
2530 /* Combine all the basic blocks from LOOP into one or two super basic
2531 blocks. Replace PHI nodes with conditional modify expressions. */
2532
2533 static void
combine_blocks(struct loop * loop)2534 combine_blocks (struct loop *loop)
2535 {
2536 basic_block bb, exit_bb, merge_target_bb;
2537 unsigned int orig_loop_num_nodes = loop->num_nodes;
2538 unsigned int i;
2539 edge e;
2540 edge_iterator ei;
2541
2542 remove_conditions_and_labels (loop);
2543 insert_gimplified_predicates (loop);
2544 predicate_all_scalar_phis (loop);
2545
2546 if (need_to_predicate)
2547 predicate_statements (loop);
2548
2549 /* Merge basic blocks: first remove all the edges in the loop,
2550 except for those from the exit block. */
2551 exit_bb = NULL;
2552 bool *predicated = XNEWVEC (bool, orig_loop_num_nodes);
2553 for (i = 0; i < orig_loop_num_nodes; i++)
2554 {
2555 bb = ifc_bbs[i];
2556 predicated[i] = !is_true_predicate (bb_predicate (bb));
2557 free_bb_predicate (bb);
2558 if (bb_with_exit_edge_p (loop, bb))
2559 {
2560 gcc_assert (exit_bb == NULL);
2561 exit_bb = bb;
2562 }
2563 }
2564 gcc_assert (exit_bb != loop->latch);
2565
2566 for (i = 1; i < orig_loop_num_nodes; i++)
2567 {
2568 bb = ifc_bbs[i];
2569
2570 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
2571 {
2572 if (e->src == exit_bb)
2573 ei_next (&ei);
2574 else
2575 remove_edge (e);
2576 }
2577 }
2578
2579 if (exit_bb != NULL)
2580 {
2581 if (exit_bb != loop->header)
2582 {
2583 /* Connect this node to loop header. */
2584 make_single_succ_edge (loop->header, exit_bb, EDGE_FALLTHRU);
2585 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
2586 }
2587
2588 /* Redirect non-exit edges to loop->latch. */
2589 FOR_EACH_EDGE (e, ei, exit_bb->succs)
2590 {
2591 if (!loop_exit_edge_p (loop, e))
2592 redirect_edge_and_branch (e, loop->latch);
2593 }
2594 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
2595 }
2596 else
2597 {
2598 /* If the loop does not have an exit, reconnect header and latch. */
2599 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
2600 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
2601 }
2602
2603 merge_target_bb = loop->header;
2604
2605 /* Get at the virtual def valid for uses starting at the first block
2606 we merge into the header. Without a virtual PHI the loop has the
2607 same virtual use on all stmts. */
2608 gphi *vphi = get_virtual_phi (loop->header);
2609 tree last_vdef = NULL_TREE;
2610 if (vphi)
2611 {
2612 last_vdef = gimple_phi_result (vphi);
2613 for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header);
2614 ! gsi_end_p (gsi); gsi_next (&gsi))
2615 if (gimple_vdef (gsi_stmt (gsi)))
2616 last_vdef = gimple_vdef (gsi_stmt (gsi));
2617 }
2618 for (i = 1; i < orig_loop_num_nodes; i++)
2619 {
2620 gimple_stmt_iterator gsi;
2621 gimple_stmt_iterator last;
2622
2623 bb = ifc_bbs[i];
2624
2625 if (bb == exit_bb || bb == loop->latch)
2626 continue;
2627
2628 /* We release virtual PHIs late because we have to propagate them
2629 out using the current VUSE. The def might be the one used
2630 after the loop. */
2631 vphi = get_virtual_phi (bb);
2632 if (vphi)
2633 {
2634 /* When there's just loads inside the loop a stray virtual
2635 PHI merging the uses can appear, update last_vdef from
2636 it. */
2637 if (!last_vdef)
2638 last_vdef = gimple_phi_arg_def (vphi, 0);
2639 imm_use_iterator iter;
2640 use_operand_p use_p;
2641 gimple *use_stmt;
2642 FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
2643 {
2644 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2645 SET_USE (use_p, last_vdef);
2646 }
2647 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
2648 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
2649 gsi = gsi_for_stmt (vphi);
2650 remove_phi_node (&gsi, true);
2651 }
2652
2653 /* Make stmts member of loop->header and clear range info from all stmts
2654 in BB which is now no longer executed conditional on a predicate we
2655 could have derived it from. */
2656 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2657 {
2658 gimple *stmt = gsi_stmt (gsi);
2659 gimple_set_bb (stmt, merge_target_bb);
2660 /* Update virtual operands. */
2661 if (last_vdef)
2662 {
2663 use_operand_p use_p = ssa_vuse_operand (stmt);
2664 if (use_p
2665 && USE_FROM_PTR (use_p) != last_vdef)
2666 SET_USE (use_p, last_vdef);
2667 if (gimple_vdef (stmt))
2668 last_vdef = gimple_vdef (stmt);
2669 }
2670 else
2671 /* If this is the first load we arrive at update last_vdef
2672 so we handle stray PHIs correctly. */
2673 last_vdef = gimple_vuse (stmt);
2674 if (predicated[i])
2675 {
2676 ssa_op_iter i;
2677 tree op;
2678 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
2679 reset_flow_sensitive_info (op);
2680 }
2681 }
2682
2683 /* Update stmt list. */
2684 last = gsi_last_bb (merge_target_bb);
2685 gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT);
2686 set_bb_seq (bb, NULL);
2687
2688 delete_basic_block (bb);
2689 }
2690
2691 /* If possible, merge loop header to the block with the exit edge.
2692 This reduces the number of basic blocks to two, to please the
2693 vectorizer that handles only loops with two nodes. */
2694 if (exit_bb
2695 && exit_bb != loop->header)
2696 {
2697 /* We release virtual PHIs late because we have to propagate them
2698 out using the current VUSE. The def might be the one used
2699 after the loop. */
2700 vphi = get_virtual_phi (exit_bb);
2701 if (vphi)
2702 {
2703 imm_use_iterator iter;
2704 use_operand_p use_p;
2705 gimple *use_stmt;
2706 FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi))
2707 {
2708 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2709 SET_USE (use_p, last_vdef);
2710 }
2711 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi)))
2712 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1;
2713 gimple_stmt_iterator gsi = gsi_for_stmt (vphi);
2714 remove_phi_node (&gsi, true);
2715 }
2716
2717 if (can_merge_blocks_p (loop->header, exit_bb))
2718 merge_blocks (loop->header, exit_bb);
2719 }
2720
2721 free (ifc_bbs);
2722 ifc_bbs = NULL;
2723 free (predicated);
2724 }
2725
2726 /* Version LOOP before if-converting it; the original loop
2727 will be if-converted, the new copy of the loop will not,
2728 and the LOOP_VECTORIZED internal call will be guarding which
2729 loop to execute. The vectorizer pass will fold this
2730 internal call into either true or false.
2731
2732 Note that this function intentionally invalidates profile. Both edges
2733 out of LOOP_VECTORIZED must have 100% probability so the profile remains
2734 consistent after the condition is folded in the vectorizer. */
2735
2736 static struct loop *
version_loop_for_if_conversion(struct loop * loop,vec<gimple * > * preds)2737 version_loop_for_if_conversion (struct loop *loop, vec<gimple *> *preds)
2738 {
2739 basic_block cond_bb;
2740 tree cond = make_ssa_name (boolean_type_node);
2741 struct loop *new_loop;
2742 gimple *g;
2743 gimple_stmt_iterator gsi;
2744 unsigned int save_length;
2745
2746 g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
2747 build_int_cst (integer_type_node, loop->num),
2748 integer_zero_node);
2749 gimple_call_set_lhs (g, cond);
2750
2751 /* Save BB->aux around loop_version as that uses the same field. */
2752 save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes;
2753 void **saved_preds = XALLOCAVEC (void *, save_length);
2754 for (unsigned i = 0; i < save_length; i++)
2755 saved_preds[i] = ifc_bbs[i]->aux;
2756
2757 initialize_original_copy_tables ();
2758 /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED
2759 is re-merged in the vectorizer. */
2760 new_loop = loop_version (loop, cond, &cond_bb,
2761 profile_probability::always (),
2762 profile_probability::always (),
2763 profile_probability::always (),
2764 profile_probability::always (), true);
2765 free_original_copy_tables ();
2766
2767 for (unsigned i = 0; i < save_length; i++)
2768 ifc_bbs[i]->aux = saved_preds[i];
2769
2770 if (new_loop == NULL)
2771 return NULL;
2772
2773 new_loop->dont_vectorize = true;
2774 new_loop->force_vectorize = false;
2775 gsi = gsi_last_bb (cond_bb);
2776 gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
2777 if (preds)
2778 preds->safe_push (g);
2779 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2780 update_ssa (TODO_update_ssa);
2781 return new_loop;
2782 }
2783
2784 /* Return true when LOOP satisfies the follow conditions that will
2785 allow it to be recognized by the vectorizer for outer-loop
2786 vectorization:
2787 - The loop is not the root node of the loop tree.
2788 - The loop has exactly one inner loop.
2789 - The loop has a single exit.
2790 - The loop header has a single successor, which is the inner
2791 loop header.
2792 - Each of the inner and outer loop latches have a single
2793 predecessor.
2794 - The loop exit block has a single predecessor, which is the
2795 inner loop's exit block. */
2796
2797 static bool
versionable_outer_loop_p(struct loop * loop)2798 versionable_outer_loop_p (struct loop *loop)
2799 {
2800 if (!loop_outer (loop)
2801 || loop->dont_vectorize
2802 || !loop->inner
2803 || loop->inner->next
2804 || !single_exit (loop)
2805 || !single_succ_p (loop->header)
2806 || single_succ (loop->header) != loop->inner->header
2807 || !single_pred_p (loop->latch)
2808 || !single_pred_p (loop->inner->latch))
2809 return false;
2810
2811 basic_block outer_exit = single_pred (loop->latch);
2812 basic_block inner_exit = single_pred (loop->inner->latch);
2813
2814 if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit)
2815 return false;
2816
2817 if (dump_file)
2818 fprintf (dump_file, "Found vectorizable outer loop for versioning\n");
2819
2820 return true;
2821 }
2822
2823 /* Performs splitting of critical edges. Skip splitting and return false
2824 if LOOP will not be converted because:
2825
2826 - LOOP is not well formed.
2827 - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
2828
2829 Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
2830
2831 static bool
ifcvt_split_critical_edges(struct loop * loop,bool aggressive_if_conv)2832 ifcvt_split_critical_edges (struct loop *loop, bool aggressive_if_conv)
2833 {
2834 basic_block *body;
2835 basic_block bb;
2836 unsigned int num = loop->num_nodes;
2837 unsigned int i;
2838 gimple *stmt;
2839 edge e;
2840 edge_iterator ei;
2841 auto_vec<edge> critical_edges;
2842
2843 /* Loop is not well formed. */
2844 if (num <= 2 || loop->inner || !single_exit (loop))
2845 return false;
2846
2847 body = get_loop_body (loop);
2848 for (i = 0; i < num; i++)
2849 {
2850 bb = body[i];
2851 if (!aggressive_if_conv
2852 && phi_nodes (bb)
2853 && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM)
2854 {
2855 if (dump_file && (dump_flags & TDF_DETAILS))
2856 fprintf (dump_file,
2857 "BB %d has complicated PHI with more than %u args.\n",
2858 bb->index, MAX_PHI_ARG_NUM);
2859
2860 free (body);
2861 return false;
2862 }
2863 if (bb == loop->latch || bb_with_exit_edge_p (loop, bb))
2864 continue;
2865
2866 stmt = last_stmt (bb);
2867 /* Skip basic blocks not ending with conditional branch. */
2868 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
2869 continue;
2870
2871 FOR_EACH_EDGE (e, ei, bb->succs)
2872 if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
2873 critical_edges.safe_push (e);
2874 }
2875 free (body);
2876
2877 while (critical_edges.length () > 0)
2878 {
2879 e = critical_edges.pop ();
2880 /* Don't split if bb can be predicated along non-critical edge. */
2881 if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest))
2882 split_edge (e);
2883 }
2884
2885 return true;
2886 }
2887
2888 /* Delete redundant statements produced by predication which prevents
2889 loop vectorization. */
2890
2891 static void
ifcvt_local_dce(basic_block bb)2892 ifcvt_local_dce (basic_block bb)
2893 {
2894 gimple *stmt;
2895 gimple *stmt1;
2896 gimple *phi;
2897 gimple_stmt_iterator gsi;
2898 auto_vec<gimple *> worklist;
2899 enum gimple_code code;
2900 use_operand_p use_p;
2901 imm_use_iterator imm_iter;
2902 std::pair <tree, tree> *name_pair;
2903 unsigned int i;
2904
2905 FOR_EACH_VEC_ELT (redundant_ssa_names, i, name_pair)
2906 replace_uses_by (name_pair->first, name_pair->second);
2907 redundant_ssa_names.release ();
2908
2909 worklist.create (64);
2910 /* Consider all phi as live statements. */
2911 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2912 {
2913 phi = gsi_stmt (gsi);
2914 gimple_set_plf (phi, GF_PLF_2, true);
2915 worklist.safe_push (phi);
2916 }
2917 /* Consider load/store statements, CALL and COND as live. */
2918 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2919 {
2920 stmt = gsi_stmt (gsi);
2921 if (is_gimple_debug (stmt))
2922 {
2923 gimple_set_plf (stmt, GF_PLF_2, true);
2924 continue;
2925 }
2926 if (gimple_store_p (stmt) || gimple_assign_load_p (stmt))
2927 {
2928 gimple_set_plf (stmt, GF_PLF_2, true);
2929 worklist.safe_push (stmt);
2930 continue;
2931 }
2932 code = gimple_code (stmt);
2933 if (code == GIMPLE_COND || code == GIMPLE_CALL)
2934 {
2935 gimple_set_plf (stmt, GF_PLF_2, true);
2936 worklist.safe_push (stmt);
2937 continue;
2938 }
2939 gimple_set_plf (stmt, GF_PLF_2, false);
2940
2941 if (code == GIMPLE_ASSIGN)
2942 {
2943 tree lhs = gimple_assign_lhs (stmt);
2944 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
2945 {
2946 stmt1 = USE_STMT (use_p);
2947 if (!is_gimple_debug (stmt1) && gimple_bb (stmt1) != bb)
2948 {
2949 gimple_set_plf (stmt, GF_PLF_2, true);
2950 worklist.safe_push (stmt);
2951 break;
2952 }
2953 }
2954 }
2955 }
2956 /* Propagate liveness through arguments of live stmt. */
2957 while (worklist.length () > 0)
2958 {
2959 ssa_op_iter iter;
2960 use_operand_p use_p;
2961 tree use;
2962
2963 stmt = worklist.pop ();
2964 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2965 {
2966 use = USE_FROM_PTR (use_p);
2967 if (TREE_CODE (use) != SSA_NAME)
2968 continue;
2969 stmt1 = SSA_NAME_DEF_STMT (use);
2970 if (gimple_bb (stmt1) != bb || gimple_plf (stmt1, GF_PLF_2))
2971 continue;
2972 gimple_set_plf (stmt1, GF_PLF_2, true);
2973 worklist.safe_push (stmt1);
2974 }
2975 }
2976 /* Delete dead statements. */
2977 gsi = gsi_last_bb (bb);
2978 while (!gsi_end_p (gsi))
2979 {
2980 gimple_stmt_iterator gsiprev = gsi;
2981 gsi_prev (&gsiprev);
2982 stmt = gsi_stmt (gsi);
2983 if (gimple_plf (stmt, GF_PLF_2))
2984 {
2985 gsi = gsiprev;
2986 continue;
2987 }
2988 if (dump_file && (dump_flags & TDF_DETAILS))
2989 {
2990 fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
2991 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2992 }
2993 gsi_remove (&gsi, true);
2994 release_defs (stmt);
2995 gsi = gsiprev;
2996 }
2997 }
2998
2999 /* If-convert LOOP when it is legal. For the moment this pass has no
3000 profitability analysis. Returns non-zero todo flags when something
3001 changed. */
3002
3003 unsigned int
tree_if_conversion(struct loop * loop,vec<gimple * > * preds)3004 tree_if_conversion (struct loop *loop, vec<gimple *> *preds)
3005 {
3006 unsigned int todo = 0;
3007 bool aggressive_if_conv;
3008 struct loop *rloop;
3009 bitmap exit_bbs;
3010
3011 again:
3012 rloop = NULL;
3013 ifc_bbs = NULL;
3014 need_to_predicate = false;
3015 any_complicated_phi = false;
3016
3017 /* Apply more aggressive if-conversion when loop or its outer loop were
3018 marked with simd pragma. When that's the case, we try to if-convert
3019 loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
3020 aggressive_if_conv = loop->force_vectorize;
3021 if (!aggressive_if_conv)
3022 {
3023 struct loop *outer_loop = loop_outer (loop);
3024 if (outer_loop && outer_loop->force_vectorize)
3025 aggressive_if_conv = true;
3026 }
3027
3028 if (!ifcvt_split_critical_edges (loop, aggressive_if_conv))
3029 goto cleanup;
3030
3031 if (!if_convertible_loop_p (loop)
3032 || !dbg_cnt (if_conversion_tree))
3033 goto cleanup;
3034
3035 if ((need_to_predicate || any_complicated_phi)
3036 && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
3037 || loop->dont_vectorize))
3038 goto cleanup;
3039
3040 /* Since we have no cost model, always version loops unless the user
3041 specified -ftree-loop-if-convert or unless versioning is required.
3042 Either version this loop, or if the pattern is right for outer-loop
3043 vectorization, version the outer loop. In the latter case we will
3044 still if-convert the original inner loop. */
3045 if (need_to_predicate
3046 || any_complicated_phi
3047 || flag_tree_loop_if_convert != 1)
3048 {
3049 struct loop *vloop
3050 = (versionable_outer_loop_p (loop_outer (loop))
3051 ? loop_outer (loop) : loop);
3052 struct loop *nloop = version_loop_for_if_conversion (vloop, preds);
3053 if (nloop == NULL)
3054 goto cleanup;
3055 if (vloop != loop)
3056 {
3057 /* If versionable_outer_loop_p decided to version the
3058 outer loop, version also the inner loop of the non-vectorized
3059 loop copy. So we transform:
3060 loop1
3061 loop2
3062 into:
3063 if (LOOP_VECTORIZED (1, 3))
3064 {
3065 loop1
3066 loop2
3067 }
3068 else
3069 loop3 (copy of loop1)
3070 if (LOOP_VECTORIZED (4, 5))
3071 loop4 (copy of loop2)
3072 else
3073 loop5 (copy of loop4) */
3074 gcc_assert (nloop->inner && nloop->inner->next == NULL);
3075 rloop = nloop->inner;
3076 }
3077 }
3078
3079 /* Now all statements are if-convertible. Combine all the basic
3080 blocks into one huge basic block doing the if-conversion
3081 on-the-fly. */
3082 combine_blocks (loop);
3083
3084 /* Delete dead predicate computations. */
3085 ifcvt_local_dce (loop->header);
3086
3087 /* Perform local CSE, this esp. helps the vectorizer analysis if loads
3088 and stores are involved. CSE only the loop body, not the entry
3089 PHIs, those are to be kept in sync with the non-if-converted copy.
3090 ??? We'll still keep dead stores though. */
3091 exit_bbs = BITMAP_ALLOC (NULL);
3092 bitmap_set_bit (exit_bbs, single_exit (loop)->dest->index);
3093 bitmap_set_bit (exit_bbs, loop->latch->index);
3094 todo |= do_rpo_vn (cfun, loop_preheader_edge (loop), exit_bbs);
3095 BITMAP_FREE (exit_bbs);
3096
3097 todo |= TODO_cleanup_cfg;
3098
3099 cleanup:
3100 if (ifc_bbs)
3101 {
3102 unsigned int i;
3103
3104 for (i = 0; i < loop->num_nodes; i++)
3105 free_bb_predicate (ifc_bbs[i]);
3106
3107 free (ifc_bbs);
3108 ifc_bbs = NULL;
3109 }
3110 if (rloop != NULL)
3111 {
3112 loop = rloop;
3113 goto again;
3114 }
3115
3116 return todo;
3117 }
3118
3119 /* Tree if-conversion pass management. */
3120
3121 namespace {
3122
3123 const pass_data pass_data_if_conversion =
3124 {
3125 GIMPLE_PASS, /* type */
3126 "ifcvt", /* name */
3127 OPTGROUP_NONE, /* optinfo_flags */
3128 TV_TREE_LOOP_IFCVT, /* tv_id */
3129 ( PROP_cfg | PROP_ssa ), /* properties_required */
3130 0, /* properties_provided */
3131 0, /* properties_destroyed */
3132 0, /* todo_flags_start */
3133 0, /* todo_flags_finish */
3134 };
3135
3136 class pass_if_conversion : public gimple_opt_pass
3137 {
3138 public:
pass_if_conversion(gcc::context * ctxt)3139 pass_if_conversion (gcc::context *ctxt)
3140 : gimple_opt_pass (pass_data_if_conversion, ctxt)
3141 {}
3142
3143 /* opt_pass methods: */
3144 virtual bool gate (function *);
3145 virtual unsigned int execute (function *);
3146
3147 }; // class pass_if_conversion
3148
3149 bool
gate(function * fun)3150 pass_if_conversion::gate (function *fun)
3151 {
3152 return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
3153 && flag_tree_loop_if_convert != 0)
3154 || flag_tree_loop_if_convert == 1);
3155 }
3156
3157 unsigned int
execute(function * fun)3158 pass_if_conversion::execute (function *fun)
3159 {
3160 struct loop *loop;
3161 unsigned todo = 0;
3162
3163 if (number_of_loops (fun) <= 1)
3164 return 0;
3165
3166 auto_vec<gimple *> preds;
3167 FOR_EACH_LOOP (loop, 0)
3168 if (flag_tree_loop_if_convert == 1
3169 || ((flag_tree_loop_vectorize || loop->force_vectorize)
3170 && !loop->dont_vectorize))
3171 todo |= tree_if_conversion (loop, &preds);
3172
3173 if (todo)
3174 {
3175 free_numbers_of_iterations_estimates (fun);
3176 scev_reset ();
3177 }
3178
3179 if (flag_checking)
3180 {
3181 basic_block bb;
3182 FOR_EACH_BB_FN (bb, fun)
3183 gcc_assert (!bb->aux);
3184 }
3185
3186 /* Perform IL update now, it might elide some loops. */
3187 if (todo & TODO_cleanup_cfg)
3188 {
3189 cleanup_tree_cfg ();
3190 if (need_ssa_update_p (fun))
3191 todo |= TODO_update_ssa;
3192 }
3193 if (todo & TODO_update_ssa_any)
3194 update_ssa (todo & TODO_update_ssa_any);
3195
3196 /* If if-conversion elided the loop fall back to the original one. */
3197 for (unsigned i = 0; i < preds.length (); ++i)
3198 {
3199 gimple *g = preds[i];
3200 if (!gimple_bb (g))
3201 continue;
3202 unsigned ifcvt_loop = tree_to_uhwi (gimple_call_arg (g, 0));
3203 if (!get_loop (fun, ifcvt_loop))
3204 {
3205 if (dump_file)
3206 fprintf (dump_file, "If-converted loop vanished\n");
3207 fold_loop_internal_call (g, boolean_false_node);
3208 }
3209 }
3210
3211 return 0;
3212 }
3213
3214 } // anon namespace
3215
3216 gimple_opt_pass *
make_pass_if_conversion(gcc::context * ctxt)3217 make_pass_if_conversion (gcc::context *ctxt)
3218 {
3219 return new pass_if_conversion (ctxt);
3220 }
3221