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