diff options
Diffstat (limited to 'gcc/tree-if-conv.c')
| -rw-r--r-- | gcc/tree-if-conv.c | 3510 |
1 files changed, 0 insertions, 3510 deletions
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c deleted file mode 100644 index 8baecea..0000000 --- a/gcc/tree-if-conv.c +++ /dev/null @@ -1,3510 +0,0 @@ -/* If-conversion for vectorizer. - Copyright (C) 2004-2022 Free Software Foundation, Inc. - Contributed by Devang Patel <dpatel@apple.com> - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it under -the terms of the GNU General Public License as published by the Free -Software Foundation; either version 3, or (at your option) any later -version. - -GCC is distributed in the hope that it will be useful, but WITHOUT ANY -WARRANTY; without even the implied warranty of MERCHANTABILITY or -FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -<http://www.gnu.org/licenses/>. */ - -/* This pass implements a tree level if-conversion of loops. Its - initial goal is to help the vectorizer to vectorize loops with - conditions. - - A short description of if-conversion: - - o Decide if a loop is if-convertible or not. - o Walk all loop basic blocks in breadth first order (BFS order). - o Remove conditional statements (at the end of basic block) - and propagate condition into destination basic blocks' - predicate list. - o Replace modify expression with conditional modify expression - using current basic block's condition. - o Merge all basic blocks - o Replace phi nodes with conditional modify expr - o Merge all basic blocks into header - - Sample transformation: - - INPUT - ----- - - # i_23 = PHI <0(0), i_18(10)>; - <L0>:; - j_15 = A[i_23]; - if (j_15 > 41) goto <L1>; else goto <L17>; - - <L17>:; - goto <bb 3> (<L3>); - - <L1>:; - - # iftmp.2_4 = PHI <0(8), 42(2)>; - <L3>:; - A[i_23] = iftmp.2_4; - i_18 = i_23 + 1; - if (i_18 <= 15) goto <L19>; else goto <L18>; - - <L19>:; - goto <bb 1> (<L0>); - - <L18>:; - - OUTPUT - ------ - - # i_23 = PHI <0(0), i_18(10)>; - <L0>:; - j_15 = A[i_23]; - - <L3>:; - iftmp.2_4 = j_15 > 41 ? 42 : 0; - A[i_23] = iftmp.2_4; - i_18 = i_23 + 1; - if (i_18 <= 15) goto <L19>; else goto <L18>; - - <L19>:; - goto <bb 1> (<L0>); - - <L18>:; -*/ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "backend.h" -#include "rtl.h" -#include "tree.h" -#include "gimple.h" -#include "cfghooks.h" -#include "tree-pass.h" -#include "ssa.h" -#include "expmed.h" -#include "optabs-query.h" -#include "gimple-pretty-print.h" -#include "alias.h" -#include "fold-const.h" -#include "stor-layout.h" -#include "gimple-fold.h" -#include "gimplify.h" -#include "gimple-iterator.h" -#include "gimplify-me.h" -#include "tree-cfg.h" -#include "tree-into-ssa.h" -#include "tree-ssa.h" -#include "cfgloop.h" -#include "tree-data-ref.h" -#include "tree-scalar-evolution.h" -#include "tree-ssa-loop.h" -#include "tree-ssa-loop-niter.h" -#include "tree-ssa-loop-ivopts.h" -#include "tree-ssa-address.h" -#include "dbgcnt.h" -#include "tree-hash-traits.h" -#include "varasm.h" -#include "builtins.h" -#include "cfganal.h" -#include "internal-fn.h" -#include "fold-const.h" -#include "tree-ssa-sccvn.h" -#include "tree-cfgcleanup.h" -#include "tree-ssa-dse.h" -#include "tree-vectorizer.h" -#include "tree-eh.h" - -/* Only handle PHIs with no more arguments unless we are asked to by - simd pragma. */ -#define MAX_PHI_ARG_NUM \ - ((unsigned) param_max_tree_if_conversion_phi_args) - -/* True if we've converted a statement that was only executed when some - condition C was true, and if for correctness we need to predicate the - statement to ensure that it is a no-op when C is false. See - predicate_statements for the kinds of predication we support. */ -static bool need_to_predicate; - -/* True if we have to rewrite stmts that may invoke undefined behavior - when a condition C was false so it doesn't if it is always executed. - See predicate_statements for the kinds of predication we support. */ -static bool need_to_rewrite_undefined; - -/* Indicate if there are any complicated PHIs that need to be handled in - if-conversion. Complicated PHI has more than two arguments and can't - be degenerated to two arguments PHI. See more information in comment - before phi_convertible_by_degenerating_args. */ -static bool any_complicated_phi; - -/* Hash for struct innermost_loop_behavior. It depends on the user to - free the memory. */ - -struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior> -{ - static inline hashval_t hash (const value_type &); - static inline bool equal (const value_type &, - const compare_type &); -}; - -inline hashval_t -innermost_loop_behavior_hash::hash (const value_type &e) -{ - hashval_t hash; - - hash = iterative_hash_expr (e->base_address, 0); - hash = iterative_hash_expr (e->offset, hash); - hash = iterative_hash_expr (e->init, hash); - return iterative_hash_expr (e->step, hash); -} - -inline bool -innermost_loop_behavior_hash::equal (const value_type &e1, - const compare_type &e2) -{ - if ((e1->base_address && !e2->base_address) - || (!e1->base_address && e2->base_address) - || (!e1->offset && e2->offset) - || (e1->offset && !e2->offset) - || (!e1->init && e2->init) - || (e1->init && !e2->init) - || (!e1->step && e2->step) - || (e1->step && !e2->step)) - return false; - - if (e1->base_address && e2->base_address - && !operand_equal_p (e1->base_address, e2->base_address, 0)) - return false; - if (e1->offset && e2->offset - && !operand_equal_p (e1->offset, e2->offset, 0)) - return false; - if (e1->init && e2->init - && !operand_equal_p (e1->init, e2->init, 0)) - return false; - if (e1->step && e2->step - && !operand_equal_p (e1->step, e2->step, 0)) - return false; - - return true; -} - -/* List of basic blocks in if-conversion-suitable order. */ -static basic_block *ifc_bbs; - -/* Hash table to store <DR's innermost loop behavior, DR> pairs. */ -static hash_map<innermost_loop_behavior_hash, - data_reference_p> *innermost_DR_map; - -/* Hash table to store <base reference, DR> pairs. */ -static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map; - -/* List of redundant SSA names: the first should be replaced by the second. */ -static vec< std::pair<tree, tree> > redundant_ssa_names; - -/* Structure used to predicate basic blocks. This is attached to the - ->aux field of the BBs in the loop to be if-converted. */ -struct bb_predicate { - - /* The condition under which this basic block is executed. */ - tree predicate; - - /* PREDICATE is gimplified, and the sequence of statements is - recorded here, in order to avoid the duplication of computations - that occur in previous conditions. See PR44483. */ - gimple_seq predicate_gimplified_stmts; -}; - -/* Returns true when the basic block BB has a predicate. */ - -static inline bool -bb_has_predicate (basic_block bb) -{ - return bb->aux != NULL; -} - -/* Returns the gimplified predicate for basic block BB. */ - -static inline tree -bb_predicate (basic_block bb) -{ - return ((struct bb_predicate *) bb->aux)->predicate; -} - -/* Sets the gimplified predicate COND for basic block BB. */ - -static inline void -set_bb_predicate (basic_block bb, tree cond) -{ - gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR - && is_gimple_condexpr (TREE_OPERAND (cond, 0))) - || is_gimple_condexpr (cond)); - ((struct bb_predicate *) bb->aux)->predicate = cond; -} - -/* Returns the sequence of statements of the gimplification of the - predicate for basic block BB. */ - -static inline gimple_seq -bb_predicate_gimplified_stmts (basic_block bb) -{ - return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts; -} - -/* Sets the sequence of statements STMTS of the gimplification of the - predicate for basic block BB. */ - -static inline void -set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) -{ - ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts; -} - -/* Adds the sequence of statements STMTS to the sequence of statements - of the predicate for basic block BB. */ - -static inline void -add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) -{ - /* We might have updated some stmts in STMTS via force_gimple_operand - calling fold_stmt and that producing multiple stmts. Delink immediate - uses so update_ssa after loop versioning doesn't get confused for - the not yet inserted predicates. - ??? This should go away once we reliably avoid updating stmts - not in any BB. */ - for (gimple_stmt_iterator gsi = gsi_start (stmts); - !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple *stmt = gsi_stmt (gsi); - delink_stmt_imm_use (stmt); - gimple_set_modified (stmt, true); - } - gimple_seq_add_seq_without_update - (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts); -} - -/* Initializes to TRUE the predicate of basic block BB. */ - -static inline void -init_bb_predicate (basic_block bb) -{ - bb->aux = XNEW (struct bb_predicate); - set_bb_predicate_gimplified_stmts (bb, NULL); - set_bb_predicate (bb, boolean_true_node); -} - -/* Release the SSA_NAMEs associated with the predicate of basic block BB. */ - -static inline void -release_bb_predicate (basic_block bb) -{ - gimple_seq stmts = bb_predicate_gimplified_stmts (bb); - if (stmts) - { - /* Ensure that these stmts haven't yet been added to a bb. */ - if (flag_checking) - for (gimple_stmt_iterator i = gsi_start (stmts); - !gsi_end_p (i); gsi_next (&i)) - gcc_assert (! gimple_bb (gsi_stmt (i))); - - /* Discard them. */ - gimple_seq_discard (stmts); - set_bb_predicate_gimplified_stmts (bb, NULL); - } -} - -/* Free the predicate of basic block BB. */ - -static inline void -free_bb_predicate (basic_block bb) -{ - if (!bb_has_predicate (bb)) - return; - - release_bb_predicate (bb); - free (bb->aux); - bb->aux = NULL; -} - -/* Reinitialize predicate of BB with the true predicate. */ - -static inline void -reset_bb_predicate (basic_block bb) -{ - if (!bb_has_predicate (bb)) - init_bb_predicate (bb); - else - { - release_bb_predicate (bb); - set_bb_predicate (bb, boolean_true_node); - } -} - -/* Returns a new SSA_NAME of type TYPE that is assigned the value of - the expression EXPR. Inserts the statement created for this - computation before GSI and leaves the iterator GSI at the same - statement. */ - -static tree -ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi) -{ - tree new_name = make_temp_ssa_name (type, NULL, "_ifc_"); - gimple *stmt = gimple_build_assign (new_name, expr); - gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi))); - gsi_insert_before (gsi, stmt, GSI_SAME_STMT); - return new_name; -} - -/* Return true when COND is a false predicate. */ - -static inline bool -is_false_predicate (tree cond) -{ - return (cond != NULL_TREE - && (cond == boolean_false_node - || integer_zerop (cond))); -} - -/* Return true when COND is a true predicate. */ - -static inline bool -is_true_predicate (tree cond) -{ - return (cond == NULL_TREE - || cond == boolean_true_node - || integer_onep (cond)); -} - -/* Returns true when BB has a predicate that is not trivial: true or - NULL_TREE. */ - -static inline bool -is_predicated (basic_block bb) -{ - return !is_true_predicate (bb_predicate (bb)); -} - -/* Parses the predicate COND and returns its comparison code and - operands OP0 and OP1. */ - -static enum tree_code -parse_predicate (tree cond, tree *op0, tree *op1) -{ - gimple *s; - - if (TREE_CODE (cond) == SSA_NAME - && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond))) - { - if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison) - { - *op0 = gimple_assign_rhs1 (s); - *op1 = gimple_assign_rhs2 (s); - return gimple_assign_rhs_code (s); - } - - else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR) - { - tree op = gimple_assign_rhs1 (s); - tree type = TREE_TYPE (op); - enum tree_code code = parse_predicate (op, op0, op1); - - return code == ERROR_MARK ? ERROR_MARK - : invert_tree_comparison (code, HONOR_NANS (type)); - } - - return ERROR_MARK; - } - - if (COMPARISON_CLASS_P (cond)) - { - *op0 = TREE_OPERAND (cond, 0); - *op1 = TREE_OPERAND (cond, 1); - return TREE_CODE (cond); - } - - return ERROR_MARK; -} - -/* Returns the fold of predicate C1 OR C2 at location LOC. */ - -static tree -fold_or_predicates (location_t loc, tree c1, tree c2) -{ - tree op1a, op1b, op2a, op2b; - enum tree_code code1 = parse_predicate (c1, &op1a, &op1b); - enum tree_code code2 = parse_predicate (c2, &op2a, &op2b); - - if (code1 != ERROR_MARK && code2 != ERROR_MARK) - { - tree t = maybe_fold_or_comparisons (boolean_type_node, code1, op1a, op1b, - code2, op2a, op2b); - if (t) - return t; - } - - return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2); -} - -/* Returns either a COND_EXPR or the folded expression if the folded - expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR, - a constant or a SSA_NAME. */ - -static tree -fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs) -{ - tree rhs1, lhs1, cond_expr; - - /* If COND is comparison r != 0 and r has boolean type, convert COND - to SSA_NAME to accept by vect bool pattern. */ - if (TREE_CODE (cond) == NE_EXPR) - { - tree op0 = TREE_OPERAND (cond, 0); - tree op1 = TREE_OPERAND (cond, 1); - if (TREE_CODE (op0) == SSA_NAME - && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE - && (integer_zerop (op1))) - cond = op0; - } - cond_expr = fold_ternary (COND_EXPR, type, cond, rhs, lhs); - - if (cond_expr == NULL_TREE) - return build3 (COND_EXPR, type, cond, rhs, lhs); - - STRIP_USELESS_TYPE_CONVERSION (cond_expr); - - if (is_gimple_val (cond_expr)) - return cond_expr; - - if (TREE_CODE (cond_expr) == ABS_EXPR) - { - rhs1 = TREE_OPERAND (cond_expr, 1); - STRIP_USELESS_TYPE_CONVERSION (rhs1); - if (is_gimple_val (rhs1)) - return build1 (ABS_EXPR, type, rhs1); - } - - if (TREE_CODE (cond_expr) == MIN_EXPR - || TREE_CODE (cond_expr) == MAX_EXPR) - { - lhs1 = TREE_OPERAND (cond_expr, 0); - STRIP_USELESS_TYPE_CONVERSION (lhs1); - rhs1 = TREE_OPERAND (cond_expr, 1); - STRIP_USELESS_TYPE_CONVERSION (rhs1); - if (is_gimple_val (rhs1) && is_gimple_val (lhs1)) - return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1); - } - return build3 (COND_EXPR, type, cond, rhs, lhs); -} - -/* Add condition NC to the predicate list of basic block BB. LOOP is - the loop to be if-converted. Use predicate of cd-equivalent block - for join bb if it exists: we call basic blocks bb1 and bb2 - cd-equivalent if they are executed under the same condition. */ - -static inline void -add_to_predicate_list (class loop *loop, basic_block bb, tree nc) -{ - tree bc, *tp; - basic_block dom_bb; - - if (is_true_predicate (nc)) - return; - - /* If dominance tells us this basic block is always executed, - don't record any predicates for it. */ - if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) - return; - - dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); - /* We use notion of cd equivalence to get simpler predicate for - join block, e.g. if join block has 2 predecessors with predicates - p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of - p1 & p2 | p1 & !p2. */ - if (dom_bb != loop->header - && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb) - { - gcc_assert (flow_bb_inside_loop_p (loop, dom_bb)); - bc = bb_predicate (dom_bb); - if (!is_true_predicate (bc)) - set_bb_predicate (bb, bc); - else - gcc_assert (is_true_predicate (bb_predicate (bb))); - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n", - dom_bb->index, bb->index); - return; - } - - if (!is_predicated (bb)) - bc = nc; - else - { - bc = bb_predicate (bb); - bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc); - if (is_true_predicate (bc)) - { - reset_bb_predicate (bb); - return; - } - } - - /* Allow a TRUTH_NOT_EXPR around the main predicate. */ - if (TREE_CODE (bc) == TRUTH_NOT_EXPR) - tp = &TREE_OPERAND (bc, 0); - else - tp = &bc; - if (!is_gimple_condexpr (*tp)) - { - gimple_seq stmts; - *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE); - add_bb_predicate_gimplified_stmts (bb, stmts); - } - set_bb_predicate (bb, bc); -} - -/* Add the condition COND to the previous condition PREV_COND, and add - this to the predicate list of the destination of edge E. LOOP is - the loop to be if-converted. */ - -static void -add_to_dst_predicate_list (class loop *loop, edge e, - tree prev_cond, tree cond) -{ - if (!flow_bb_inside_loop_p (loop, e->dest)) - return; - - if (!is_true_predicate (prev_cond)) - cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, - prev_cond, cond); - - if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest)) - add_to_predicate_list (loop, e->dest, cond); -} - -/* Return true if one of the successor edges of BB exits LOOP. */ - -static bool -bb_with_exit_edge_p (class loop *loop, basic_block bb) -{ - edge e; - edge_iterator ei; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (loop_exit_edge_p (loop, e)) - return true; - - return false; -} - -/* Given PHI which has more than two arguments, this function checks if - it's if-convertible by degenerating its arguments. Specifically, if - below two conditions are satisfied: - - 1) Number of PHI arguments with different values equals to 2 and one - argument has the only occurrence. - 2) The edge corresponding to the unique argument isn't critical edge. - - Such PHI can be handled as PHIs have only two arguments. For example, - below PHI: - - res = PHI <A_1(e1), A_1(e2), A_2(e3)>; - - can be transformed into: - - res = (predicate of e3) ? A_2 : A_1; - - Return TRUE if it is the case, FALSE otherwise. */ - -static bool -phi_convertible_by_degenerating_args (gphi *phi) -{ - edge e; - tree arg, t1 = NULL, t2 = NULL; - unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0; - unsigned int num_args = gimple_phi_num_args (phi); - - gcc_assert (num_args > 2); - - for (i = 0; i < num_args; i++) - { - arg = gimple_phi_arg_def (phi, i); - if (t1 == NULL || operand_equal_p (t1, arg, 0)) - { - n1++; - i1 = i; - t1 = arg; - } - else if (t2 == NULL || operand_equal_p (t2, arg, 0)) - { - n2++; - i2 = i; - t2 = arg; - } - else - return false; - } - - if (n1 != 1 && n2 != 1) - return false; - - /* Check if the edge corresponding to the unique arg is critical. */ - e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2); - if (EDGE_COUNT (e->src->succs) > 1) - return false; - - return true; -} - -/* Return true when PHI is if-convertible. PHI is part of loop LOOP - and it belongs to basic block BB. Note at this point, it is sure - that PHI is if-convertible. This function updates global variable - ANY_COMPLICATED_PHI if PHI is complicated. */ - -static bool -if_convertible_phi_p (class loop *loop, basic_block bb, gphi *phi) -{ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "-------------------------\n"); - print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); - } - - if (bb != loop->header - && gimple_phi_num_args (phi) > 2 - && !phi_convertible_by_degenerating_args (phi)) - any_complicated_phi = true; - - return true; -} - -/* Records the status of a data reference. This struct is attached to - each DR->aux field. */ - -struct ifc_dr { - bool rw_unconditionally; - bool w_unconditionally; - bool written_at_least_once; - - tree rw_predicate; - tree w_predicate; - tree base_w_predicate; -}; - -#define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux) -#define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once) -#define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally) -#define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally) - -/* Iterates over DR's and stores refs, DR and base refs, DR pairs in - HASH tables. While storing them in HASH table, it checks if the - reference is unconditionally read or written and stores that as a flag - information. For base reference it checks if it is written atlest once - unconditionally and stores it as flag information along with DR. - In other words for every data reference A in STMT there exist other - accesses to a data reference with the same base with predicates that - add up (OR-up) to the true predicate: this ensures that the data - reference A is touched (read or written) on every iteration of the - if-converted loop. */ -static void -hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a) -{ - - data_reference_p *master_dr, *base_master_dr; - tree base_ref = DR_BASE_OBJECT (a); - innermost_loop_behavior *innermost = &DR_INNERMOST (a); - tree ca = bb_predicate (gimple_bb (DR_STMT (a))); - bool exist1, exist2; - - master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1); - if (!exist1) - *master_dr = a; - - if (DR_IS_WRITE (a)) - { - IFC_DR (*master_dr)->w_predicate - = fold_or_predicates (UNKNOWN_LOCATION, ca, - IFC_DR (*master_dr)->w_predicate); - if (is_true_predicate (IFC_DR (*master_dr)->w_predicate)) - DR_W_UNCONDITIONALLY (*master_dr) = true; - } - IFC_DR (*master_dr)->rw_predicate - = fold_or_predicates (UNKNOWN_LOCATION, ca, - IFC_DR (*master_dr)->rw_predicate); - if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate)) - DR_RW_UNCONDITIONALLY (*master_dr) = true; - - if (DR_IS_WRITE (a)) - { - base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2); - if (!exist2) - *base_master_dr = a; - IFC_DR (*base_master_dr)->base_w_predicate - = fold_or_predicates (UNKNOWN_LOCATION, ca, - IFC_DR (*base_master_dr)->base_w_predicate); - if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate)) - DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true; - } -} - -/* Return TRUE if can prove the index IDX of an array reference REF is - within array bound. Return false otherwise. */ - -static bool -idx_within_array_bound (tree ref, tree *idx, void *dta) -{ - wi::overflow_type overflow; - widest_int niter, valid_niter, delta, wi_step; - tree ev, init, step; - tree low, high; - class loop *loop = (class loop*) dta; - - /* Only support within-bound access for array references. */ - if (TREE_CODE (ref) != ARRAY_REF) - return false; - - /* For arrays at the end of the structure, we are not guaranteed that they - do not really extend over their declared size. However, for arrays of - size greater than one, this is unlikely to be intended. */ - if (array_at_struct_end_p (ref)) - return false; - - ev = analyze_scalar_evolution (loop, *idx); - ev = instantiate_parameters (loop, ev); - init = initial_condition (ev); - step = evolution_part_in_loop_num (ev, loop->num); - - if (!init || TREE_CODE (init) != INTEGER_CST - || (step && TREE_CODE (step) != INTEGER_CST)) - return false; - - low = array_ref_low_bound (ref); - high = array_ref_up_bound (ref); - - /* The case of nonconstant bounds could be handled, but it would be - complicated. */ - if (TREE_CODE (low) != INTEGER_CST - || !high || TREE_CODE (high) != INTEGER_CST) - return false; - - /* Check if the intial idx is within bound. */ - if (wi::to_widest (init) < wi::to_widest (low) - || wi::to_widest (init) > wi::to_widest (high)) - return false; - - /* The idx is always within bound. */ - if (!step || integer_zerop (step)) - return true; - - if (!max_loop_iterations (loop, &niter)) - return false; - - if (wi::to_widest (step) < 0) - { - delta = wi::to_widest (init) - wi::to_widest (low); - wi_step = -wi::to_widest (step); - } - else - { - delta = wi::to_widest (high) - wi::to_widest (init); - wi_step = wi::to_widest (step); - } - - valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow); - /* The iteration space of idx is within array bound. */ - if (!overflow && niter <= valid_niter) - return true; - - return false; -} - -/* Return TRUE if ref is a within bound array reference. */ - -static bool -ref_within_array_bound (gimple *stmt, tree ref) -{ - class loop *loop = loop_containing_stmt (stmt); - - gcc_assert (loop != NULL); - return for_each_index (&ref, idx_within_array_bound, loop); -} - - -/* Given a memory reference expression T, return TRUE if base object - it refers to is writable. The base object of a memory reference - is the main object being referenced, which is returned by function - get_base_address. */ - -static bool -base_object_writable (tree ref) -{ - tree base_tree = get_base_address (ref); - - return (base_tree - && DECL_P (base_tree) - && decl_binds_to_current_def_p (base_tree) - && !TREE_READONLY (base_tree)); -} - -/* Return true when the memory references of STMT won't trap in the - if-converted code. There are two things that we have to check for: - - - writes to memory occur to writable memory: if-conversion of - memory writes transforms the conditional memory writes into - unconditional writes, i.e. "if (cond) A[i] = foo" is transformed - into "A[i] = cond ? foo : A[i]", and as the write to memory may not - be executed at all in the original code, it may be a readonly - memory. To check that A is not const-qualified, we check that - there exists at least an unconditional write to A in the current - function. - - - reads or writes to memory are valid memory accesses for every - iteration. To check that the memory accesses are correctly formed - and that we are allowed to read and write in these locations, we - check that the memory accesses to be if-converted occur at every - iteration unconditionally. - - Returns true for the memory reference in STMT, same memory reference - is read or written unconditionally atleast once and the base memory - reference is written unconditionally once. This is to check reference - will not write fault. Also retuns true if the memory reference is - unconditionally read once then we are conditionally writing to memory - which is defined as read and write and is bound to the definition - we are seeing. */ -static bool -ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs) -{ - /* If DR didn't see a reference here we can't use it to tell - whether the ref traps or not. */ - if (gimple_uid (stmt) == 0) - return false; - - data_reference_p *master_dr, *base_master_dr; - data_reference_p a = drs[gimple_uid (stmt) - 1]; - - tree base = DR_BASE_OBJECT (a); - innermost_loop_behavior *innermost = &DR_INNERMOST (a); - - gcc_assert (DR_STMT (a) == stmt); - gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a) - || DR_INIT (a) || DR_STEP (a)); - - master_dr = innermost_DR_map->get (innermost); - gcc_assert (master_dr != NULL); - - base_master_dr = baseref_DR_map->get (base); - - /* If a is unconditionally written to it doesn't trap. */ - if (DR_W_UNCONDITIONALLY (*master_dr)) - return true; - - /* If a is unconditionally accessed then ... - - Even a is conditional access, we can treat it as an unconditional - one if it's an array reference and all its index are within array - bound. */ - if (DR_RW_UNCONDITIONALLY (*master_dr) - || ref_within_array_bound (stmt, DR_REF (a))) - { - /* an unconditional read won't trap. */ - if (DR_IS_READ (a)) - return true; - - /* an unconditionaly write won't trap if the base is written - to unconditionally. */ - if (base_master_dr - && DR_BASE_W_UNCONDITIONALLY (*base_master_dr)) - return flag_store_data_races; - /* or the base is known to be not readonly. */ - else if (base_object_writable (DR_REF (a))) - return flag_store_data_races; - } - - return false; -} - -/* Return true if STMT could be converted into a masked load or store - (conditional load or store based on a mask computed from bb predicate). */ - -static bool -ifcvt_can_use_mask_load_store (gimple *stmt) -{ - /* Check whether this is a load or store. */ - tree lhs = gimple_assign_lhs (stmt); - bool is_load; - tree ref; - if (gimple_store_p (stmt)) - { - if (!is_gimple_val (gimple_assign_rhs1 (stmt))) - return false; - is_load = false; - ref = lhs; - } - else if (gimple_assign_load_p (stmt)) - { - is_load = true; - ref = gimple_assign_rhs1 (stmt); - } - else - return false; - - if (may_be_nonaddressable_p (ref)) - return false; - - /* Mask should be integer mode of the same size as the load/store - mode. */ - machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); - if (!int_mode_for_mode (mode).exists () || VECTOR_MODE_P (mode)) - return false; - - if (can_vec_mask_load_store_p (mode, VOIDmode, is_load)) - return true; - - return false; -} - -/* Return true if STMT could be converted from an operation that is - unconditional to one that is conditional on a bb predicate mask. */ - -static bool -ifcvt_can_predicate (gimple *stmt) -{ - basic_block bb = gimple_bb (stmt); - - if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize) - || bb->loop_father->dont_vectorize - || gimple_has_volatile_ops (stmt)) - return false; - - if (gimple_assign_single_p (stmt)) - return ifcvt_can_use_mask_load_store (stmt); - - tree_code code = gimple_assign_rhs_code (stmt); - tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt)); - tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt)); - if (!types_compatible_p (lhs_type, rhs_type)) - return false; - internal_fn cond_fn = get_conditional_internal_fn (code); - return (cond_fn != IFN_LAST - && vectorized_internal_fn_supported_p (cond_fn, lhs_type)); -} - -/* Return true when STMT is if-convertible. - - GIMPLE_ASSIGN statement is not if-convertible if, - - it is not movable, - - it could trap, - - LHS is not var decl. */ - -static bool -if_convertible_gimple_assign_stmt_p (gimple *stmt, - vec<data_reference_p> refs) -{ - tree lhs = gimple_assign_lhs (stmt); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "-------------------------\n"); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); - } - - if (!is_gimple_reg_type (TREE_TYPE (lhs))) - return false; - - /* Some of these constrains might be too conservative. */ - if (stmt_ends_bb_p (stmt) - || gimple_has_volatile_ops (stmt) - || (TREE_CODE (lhs) == SSA_NAME - && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) - || gimple_has_side_effects (stmt)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "stmt not suitable for ifcvt\n"); - return false; - } - - /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because - in between if_convertible_loop_p and combine_blocks - we can perform loop versioning. */ - gimple_set_plf (stmt, GF_PLF_2, false); - - if ((! gimple_vuse (stmt) - || gimple_could_trap_p_1 (stmt, false, false) - || ! ifcvt_memrefs_wont_trap (stmt, refs)) - && gimple_could_trap_p (stmt)) - { - if (ifcvt_can_predicate (stmt)) - { - gimple_set_plf (stmt, GF_PLF_2, true); - need_to_predicate = true; - return true; - } - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "tree could trap...\n"); - return false; - } - else if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) - || POINTER_TYPE_P (TREE_TYPE (lhs))) - && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs)) - && arith_code_with_undefined_signed_overflow - (gimple_assign_rhs_code (stmt))) - /* We have to rewrite stmts with undefined overflow. */ - need_to_rewrite_undefined = true; - - /* When if-converting stores force versioning, likewise if we - ended up generating store data races. */ - if (gimple_vdef (stmt)) - need_to_predicate = true; - - return true; -} - -/* Return true when STMT is if-convertible. - - A statement is if-convertible if: - - it is an if-convertible GIMPLE_ASSIGN, - - it is a GIMPLE_LABEL or a GIMPLE_COND, - - it is builtins call. */ - -static bool -if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs) -{ - switch (gimple_code (stmt)) - { - case GIMPLE_LABEL: - case GIMPLE_DEBUG: - case GIMPLE_COND: - return true; - - case GIMPLE_ASSIGN: - return if_convertible_gimple_assign_stmt_p (stmt, refs); - - case GIMPLE_CALL: - { - tree fndecl = gimple_call_fndecl (stmt); - if (fndecl) - { - int flags = gimple_call_flags (stmt); - if ((flags & ECF_CONST) - && !(flags & ECF_LOOPING_CONST_OR_PURE) - /* We can only vectorize some builtins at the moment, - so restrict if-conversion to those. */ - && fndecl_built_in_p (fndecl)) - return true; - } - return false; - } - - default: - /* Don't know what to do with 'em so don't do anything. */ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "don't know what to do\n"); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); - } - return false; - } -} - -/* Assumes that BB has more than 1 predecessors. - Returns false if at least one successor is not on critical edge - and true otherwise. */ - -static inline bool -all_preds_critical_p (basic_block bb) -{ - edge e; - edge_iterator ei; - - FOR_EACH_EDGE (e, ei, bb->preds) - if (EDGE_COUNT (e->src->succs) == 1) - return false; - return true; -} - -/* Return true when BB is if-convertible. This routine does not check - basic block's statements and phis. - - A basic block is not if-convertible if: - - it is non-empty and it is after the exit block (in BFS order), - - it is after the exit block but before the latch, - - its edges are not normal. - - EXIT_BB is the basic block containing the exit of the LOOP. BB is - inside LOOP. */ - -static bool -if_convertible_bb_p (class loop *loop, basic_block bb, basic_block exit_bb) -{ - edge e; - edge_iterator ei; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "----------[%d]-------------\n", bb->index); - - if (EDGE_COUNT (bb->succs) > 2) - return false; - - gimple *last = last_stmt (bb); - if (gcall *call = safe_dyn_cast <gcall *> (last)) - if (gimple_call_ctrl_altering_p (call)) - return false; - - if (exit_bb) - { - if (bb != loop->latch) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "basic block after exit bb but before latch\n"); - return false; - } - else if (!empty_block_p (bb)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "non empty basic block after exit bb\n"); - return false; - } - else if (bb == loop->latch - && bb != exit_bb - && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "latch is not dominated by exit_block\n"); - return false; - } - } - - /* Be less adventurous and handle only normal edges. */ - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Difficult to handle edges\n"); - return false; - } - - return true; -} - -/* Return true when all predecessor blocks of BB are visited. The - VISITED bitmap keeps track of the visited blocks. */ - -static bool -pred_blocks_visited_p (basic_block bb, bitmap *visited) -{ - edge e; - edge_iterator ei; - FOR_EACH_EDGE (e, ei, bb->preds) - if (!bitmap_bit_p (*visited, e->src->index)) - return false; - - return true; -} - -/* Get body of a LOOP in suitable order for if-conversion. It is - caller's responsibility to deallocate basic block list. - If-conversion suitable order is, breadth first sort (BFS) order - with an additional constraint: select a block only if all its - predecessors are already selected. */ - -static basic_block * -get_loop_body_in_if_conv_order (const class loop *loop) -{ - basic_block *blocks, *blocks_in_bfs_order; - basic_block bb; - bitmap visited; - unsigned int index = 0; - unsigned int visited_count = 0; - - gcc_assert (loop->num_nodes); - gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)); - - blocks = XCNEWVEC (basic_block, loop->num_nodes); - visited = BITMAP_ALLOC (NULL); - - blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); - - index = 0; - while (index < loop->num_nodes) - { - bb = blocks_in_bfs_order [index]; - - if (bb->flags & BB_IRREDUCIBLE_LOOP) - { - free (blocks_in_bfs_order); - BITMAP_FREE (visited); - free (blocks); - return NULL; - } - - if (!bitmap_bit_p (visited, bb->index)) - { - if (pred_blocks_visited_p (bb, &visited) - || bb == loop->header) - { - /* This block is now visited. */ - bitmap_set_bit (visited, bb->index); - blocks[visited_count++] = bb; - } - } - - index++; - - if (index == loop->num_nodes - && visited_count != loop->num_nodes) - /* Not done yet. */ - index = 0; - } - free (blocks_in_bfs_order); - BITMAP_FREE (visited); - return blocks; -} - -/* Returns true when the analysis of the predicates for all the basic - blocks in LOOP succeeded. - - predicate_bbs first allocates the predicates of the basic blocks. - These fields are then initialized with the tree expressions - representing the predicates under which a basic block is executed - in the LOOP. As the loop->header is executed at each iteration, it - has the "true" predicate. Other statements executed under a - condition are predicated with that condition, for example - - | if (x) - | S1; - | else - | S2; - - S1 will be predicated with "x", and - S2 will be predicated with "!x". */ - -static void -predicate_bbs (loop_p loop) -{ - unsigned int i; - - for (i = 0; i < loop->num_nodes; i++) - init_bb_predicate (ifc_bbs[i]); - - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = ifc_bbs[i]; - tree cond; - gimple *stmt; - - /* The loop latch and loop exit block are always executed and - have no extra conditions to be processed: skip them. */ - if (bb == loop->latch - || bb_with_exit_edge_p (loop, bb)) - { - reset_bb_predicate (bb); - continue; - } - - cond = bb_predicate (bb); - stmt = last_stmt (bb); - if (stmt && gimple_code (stmt) == GIMPLE_COND) - { - tree c2; - edge true_edge, false_edge; - location_t loc = gimple_location (stmt); - tree c = build2_loc (loc, gimple_cond_code (stmt), - boolean_type_node, - gimple_cond_lhs (stmt), - gimple_cond_rhs (stmt)); - - /* Add new condition into destination's predicate list. */ - extract_true_false_edges_from_block (gimple_bb (stmt), - &true_edge, &false_edge); - - /* If C is true, then TRUE_EDGE is taken. */ - add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond), - unshare_expr (c)); - - /* If C is false, then FALSE_EDGE is taken. */ - c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node, - unshare_expr (c)); - add_to_dst_predicate_list (loop, false_edge, - unshare_expr (cond), c2); - - cond = NULL_TREE; - } - - /* If current bb has only one successor, then consider it as an - unconditional goto. */ - if (single_succ_p (bb)) - { - basic_block bb_n = single_succ (bb); - - /* The successor bb inherits the predicate of its - predecessor. If there is no predicate in the predecessor - bb, then consider the successor bb as always executed. */ - if (cond == NULL_TREE) - cond = boolean_true_node; - - add_to_predicate_list (loop, bb_n, cond); - } - } - - /* The loop header is always executed. */ - reset_bb_predicate (loop->header); - gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL - && bb_predicate_gimplified_stmts (loop->latch) == NULL); -} - -/* Build region by adding loop pre-header and post-header blocks. */ - -static vec<basic_block> -build_region (class loop *loop) -{ - vec<basic_block> region = vNULL; - basic_block exit_bb = NULL; - - gcc_assert (ifc_bbs); - /* The first element is loop pre-header. */ - region.safe_push (loop_preheader_edge (loop)->src); - - for (unsigned int i = 0; i < loop->num_nodes; i++) - { - basic_block bb = ifc_bbs[i]; - region.safe_push (bb); - /* Find loop postheader. */ - edge e; - edge_iterator ei; - FOR_EACH_EDGE (e, ei, bb->succs) - if (loop_exit_edge_p (loop, e)) - { - exit_bb = e->dest; - break; - } - } - /* The last element is loop post-header. */ - gcc_assert (exit_bb); - region.safe_push (exit_bb); - return region; -} - -/* Return true when LOOP is if-convertible. This is a helper function - for if_convertible_loop_p. REFS and DDRS are initialized and freed - in if_convertible_loop_p. */ - -static bool -if_convertible_loop_p_1 (class loop *loop, vec<data_reference_p> *refs) -{ - unsigned int i; - basic_block exit_bb = NULL; - vec<basic_block> region; - - if (find_data_references_in_loop (loop, refs) == chrec_dont_know) - return false; - - calculate_dominance_info (CDI_DOMINATORS); - - /* Allow statements that can be handled during if-conversion. */ - ifc_bbs = get_loop_body_in_if_conv_order (loop); - if (!ifc_bbs) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Irreducible loop\n"); - return false; - } - - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = ifc_bbs[i]; - - if (!if_convertible_bb_p (loop, bb, exit_bb)) - return false; - - if (bb_with_exit_edge_p (loop, bb)) - exit_bb = bb; - } - - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = ifc_bbs[i]; - gimple_stmt_iterator gsi; - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - switch (gimple_code (gsi_stmt (gsi))) - { - case GIMPLE_LABEL: - case GIMPLE_ASSIGN: - case GIMPLE_CALL: - case GIMPLE_DEBUG: - case GIMPLE_COND: - gimple_set_uid (gsi_stmt (gsi), 0); - break; - default: - return false; - } - } - - data_reference_p dr; - - innermost_DR_map - = new hash_map<innermost_loop_behavior_hash, data_reference_p>; - baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>; - - /* Compute post-dominator tree locally. */ - region = build_region (loop); - calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region); - - predicate_bbs (loop); - - /* Free post-dominator tree since it is not used after predication. */ - free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region); - region.release (); - - for (i = 0; refs->iterate (i, &dr); i++) - { - tree ref = DR_REF (dr); - - dr->aux = XNEW (struct ifc_dr); - DR_BASE_W_UNCONDITIONALLY (dr) = false; - DR_RW_UNCONDITIONALLY (dr) = false; - DR_W_UNCONDITIONALLY (dr) = false; - IFC_DR (dr)->rw_predicate = boolean_false_node; - IFC_DR (dr)->w_predicate = boolean_false_node; - IFC_DR (dr)->base_w_predicate = boolean_false_node; - if (gimple_uid (DR_STMT (dr)) == 0) - gimple_set_uid (DR_STMT (dr), i + 1); - - /* If DR doesn't have innermost loop behavior or it's a compound - memory reference, we synthesize its innermost loop behavior - for hashing. */ - if (TREE_CODE (ref) == COMPONENT_REF - || TREE_CODE (ref) == IMAGPART_EXPR - || TREE_CODE (ref) == REALPART_EXPR - || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr) - || DR_INIT (dr) || DR_STEP (dr))) - { - while (TREE_CODE (ref) == COMPONENT_REF - || TREE_CODE (ref) == IMAGPART_EXPR - || TREE_CODE (ref) == REALPART_EXPR) - ref = TREE_OPERAND (ref, 0); - - memset (&DR_INNERMOST (dr), 0, sizeof (DR_INNERMOST (dr))); - DR_BASE_ADDRESS (dr) = ref; - } - hash_memrefs_baserefs_and_store_DRs_read_written_info (dr); - } - - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = ifc_bbs[i]; - gimple_stmt_iterator itr; - - /* Check the if-convertibility of statements in predicated BBs. */ - if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) - for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) - if (!if_convertible_stmt_p (gsi_stmt (itr), *refs)) - return false; - } - - /* Checking PHIs needs to be done after stmts, as the fact whether there - are any masked loads or stores affects the tests. */ - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = ifc_bbs[i]; - gphi_iterator itr; - - for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr)) - if (!if_convertible_phi_p (loop, bb, itr.phi ())) - return false; - } - - if (dump_file) - fprintf (dump_file, "Applying if-conversion\n"); - - return true; -} - -/* Return true when LOOP is if-convertible. - LOOP is if-convertible if: - - it is innermost, - - it has two or more basic blocks, - - it has only one exit, - - loop header is not the exit edge, - - if its basic blocks and phi nodes are if convertible. */ - -static bool -if_convertible_loop_p (class loop *loop) -{ - edge e; - edge_iterator ei; - bool res = false; - vec<data_reference_p> refs; - - /* Handle only innermost loop. */ - if (!loop || loop->inner) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "not innermost loop\n"); - return false; - } - - /* If only one block, no need for if-conversion. */ - if (loop->num_nodes <= 2) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "less than 2 basic blocks\n"); - return false; - } - - /* More than one loop exit is too much to handle. */ - if (!single_exit (loop)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "multiple exits\n"); - return false; - } - - /* If one of the loop header's edge is an exit edge then do not - apply if-conversion. */ - FOR_EACH_EDGE (e, ei, loop->header->succs) - if (loop_exit_edge_p (loop, e)) - return false; - - refs.create (5); - res = if_convertible_loop_p_1 (loop, &refs); - - data_reference_p dr; - unsigned int i; - for (i = 0; refs.iterate (i, &dr); i++) - free (dr->aux); - - free_data_refs (refs); - - delete innermost_DR_map; - innermost_DR_map = NULL; - - delete baseref_DR_map; - baseref_DR_map = NULL; - - return res; -} - -/* Return reduc_1 if has_nop. - - if (...) - tmp1 = (unsigned type) reduc_1; - tmp2 = tmp1 + rhs2; - reduc_3 = (signed type) tmp2. */ -static tree -strip_nop_cond_scalar_reduction (bool has_nop, tree op) -{ - if (!has_nop) - return op; - - if (TREE_CODE (op) != SSA_NAME) - return NULL_TREE; - - gassign *stmt = safe_dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op)); - if (!stmt - || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)) - || !tree_nop_conversion_p (TREE_TYPE (op), TREE_TYPE - (gimple_assign_rhs1 (stmt)))) - return NULL_TREE; - - return gimple_assign_rhs1 (stmt); -} - -/* Returns true if def-stmt for phi argument ARG is simple increment/decrement - which is in predicated basic block. - In fact, the following PHI pattern is searching: - loop-header: - reduc_1 = PHI <..., reduc_2> - ... - if (...) - reduc_3 = ... - reduc_2 = PHI <reduc_1, reduc_3> - - ARG_0 and ARG_1 are correspondent PHI arguments. - REDUC, OP0 and OP1 contain reduction stmt and its operands. - EXTENDED is true if PHI has > 2 arguments. */ - -static bool -is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1, - tree *op0, tree *op1, bool extended, bool* has_nop, - gimple **nop_reduc) -{ - tree lhs, r_op1, r_op2, r_nop1, r_nop2; - gimple *stmt; - gimple *header_phi = NULL; - enum tree_code reduction_op; - basic_block bb = gimple_bb (phi); - class loop *loop = bb->loop_father; - edge latch_e = loop_latch_edge (loop); - imm_use_iterator imm_iter; - use_operand_p use_p; - edge e; - edge_iterator ei; - bool result = *has_nop = false; - if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME) - return false; - - if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI) - { - lhs = arg_1; - header_phi = SSA_NAME_DEF_STMT (arg_0); - stmt = SSA_NAME_DEF_STMT (arg_1); - } - else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI) - { - lhs = arg_0; - header_phi = SSA_NAME_DEF_STMT (arg_1); - stmt = SSA_NAME_DEF_STMT (arg_0); - } - else - return false; - if (gimple_bb (header_phi) != loop->header) - return false; - - if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi)) - return false; - - if (gimple_code (stmt) != GIMPLE_ASSIGN - || gimple_has_volatile_ops (stmt)) - return false; - - if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) - return false; - - if (!is_predicated (gimple_bb (stmt))) - return false; - - /* Check that stmt-block is predecessor of phi-block. */ - FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs) - if (e->dest == bb) - { - result = true; - break; - } - if (!result) - return false; - - if (!has_single_use (lhs)) - return false; - - reduction_op = gimple_assign_rhs_code (stmt); - - /* Catch something like below - - loop-header: - reduc_1 = PHI <..., reduc_2> - ... - if (...) - tmp1 = (unsigned type) reduc_1; - tmp2 = tmp1 + rhs2; - reduc_3 = (signed type) tmp2; - - reduc_2 = PHI <reduc_1, reduc_3> - - and convert to - - reduc_2 = PHI <0, reduc_3> - tmp1 = (unsigned type)reduce_1; - ifcvt = cond_expr ? rhs2 : 0 - tmp2 = tmp1 +/- ifcvt; - reduce_1 = (signed type)tmp2; */ - - if (CONVERT_EXPR_CODE_P (reduction_op)) - { - lhs = gimple_assign_rhs1 (stmt); - if (TREE_CODE (lhs) != SSA_NAME - || !has_single_use (lhs)) - return false; - - *nop_reduc = stmt; - stmt = SSA_NAME_DEF_STMT (lhs); - if (gimple_bb (stmt) != gimple_bb (*nop_reduc) - || !is_gimple_assign (stmt)) - return false; - - *has_nop = true; - reduction_op = gimple_assign_rhs_code (stmt); - } - - if (reduction_op != PLUS_EXPR - && reduction_op != MINUS_EXPR - && reduction_op != BIT_IOR_EXPR - && reduction_op != BIT_XOR_EXPR - && reduction_op != BIT_AND_EXPR) - return false; - r_op1 = gimple_assign_rhs1 (stmt); - r_op2 = gimple_assign_rhs2 (stmt); - - r_nop1 = strip_nop_cond_scalar_reduction (*has_nop, r_op1); - r_nop2 = strip_nop_cond_scalar_reduction (*has_nop, r_op2); - - /* Make R_OP1 to hold reduction variable. */ - if (r_nop2 == PHI_RESULT (header_phi) - && commutative_tree_code (reduction_op)) - { - std::swap (r_op1, r_op2); - std::swap (r_nop1, r_nop2); - } - else if (r_nop1 != PHI_RESULT (header_phi)) - return false; - - if (*has_nop) - { - /* Check that R_NOP1 is used in nop_stmt or in PHI only. */ - FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_nop1) - { - gimple *use_stmt = USE_STMT (use_p); - if (is_gimple_debug (use_stmt)) - continue; - if (use_stmt == SSA_NAME_DEF_STMT (r_op1)) - continue; - if (use_stmt != phi) - return false; - } - } - - /* Check that R_OP1 is used in reduction stmt or in PHI only. */ - FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1) - { - gimple *use_stmt = USE_STMT (use_p); - if (is_gimple_debug (use_stmt)) - continue; - if (use_stmt == stmt) - continue; - if (gimple_code (use_stmt) != GIMPLE_PHI) - return false; - } - - *op0 = r_op1; *op1 = r_op2; - *reduc = stmt; - return true; -} - -/* Converts conditional scalar reduction into unconditional form, e.g. - bb_4 - if (_5 != 0) goto bb_5 else goto bb_6 - end_bb_4 - bb_5 - res_6 = res_13 + 1; - end_bb_5 - bb_6 - # res_2 = PHI <res_13(4), res_6(5)> - end_bb_6 - - will be converted into sequence - _ifc__1 = _5 != 0 ? 1 : 0; - res_2 = res_13 + _ifc__1; - Argument SWAP tells that arguments of conditional expression should be - swapped. - Returns rhs of resulting PHI assignment. */ - -static tree -convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi, - tree cond, tree op0, tree op1, bool swap, - bool has_nop, gimple* nop_reduc) -{ - gimple_stmt_iterator stmt_it; - gimple *new_assign; - tree rhs; - tree rhs1 = gimple_assign_rhs1 (reduc); - tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_"); - tree c; - enum tree_code reduction_op = gimple_assign_rhs_code (reduc); - tree op_nochange = neutral_op_for_reduction (TREE_TYPE (rhs1), reduction_op, NULL); - gimple_seq stmts = NULL; - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Found cond scalar reduction.\n"); - print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM); - } - - /* Build cond expression using COND and constant operand - of reduction rhs. */ - c = fold_build_cond_expr (TREE_TYPE (rhs1), - unshare_expr (cond), - swap ? op_nochange : op1, - swap ? op1 : op_nochange); - - /* Create assignment stmt and insert it at GSI. */ - new_assign = gimple_build_assign (tmp, c); - gsi_insert_before (gsi, new_assign, GSI_SAME_STMT); - /* Build rhs for unconditional increment/decrement/logic_operation. */ - rhs = gimple_build (&stmts, reduction_op, - TREE_TYPE (rhs1), op0, tmp); - - if (has_nop) - { - rhs = gimple_convert (&stmts, - TREE_TYPE (gimple_assign_lhs (nop_reduc)), rhs); - stmt_it = gsi_for_stmt (nop_reduc); - gsi_remove (&stmt_it, true); - release_defs (nop_reduc); - } - gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT); - - /* Delete original reduction stmt. */ - stmt_it = gsi_for_stmt (reduc); - gsi_remove (&stmt_it, true); - release_defs (reduc); - return rhs; -} - -/* Produce condition for all occurrences of ARG in PHI node. */ - -static tree -gen_phi_arg_condition (gphi *phi, vec<int> *occur, - gimple_stmt_iterator *gsi) -{ - int len; - int i; - tree cond = NULL_TREE; - tree c; - edge e; - - len = occur->length (); - gcc_assert (len > 0); - for (i = 0; i < len; i++) - { - e = gimple_phi_arg_edge (phi, (*occur)[i]); - c = bb_predicate (e->src); - if (is_true_predicate (c)) - { - cond = c; - break; - } - c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c), - is_gimple_condexpr, NULL_TREE, - true, GSI_SAME_STMT); - if (cond != NULL_TREE) - { - /* Must build OR expression. */ - cond = fold_or_predicates (EXPR_LOCATION (c), c, cond); - cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), - is_gimple_condexpr, NULL_TREE, - true, GSI_SAME_STMT); - } - else - cond = c; - } - gcc_assert (cond != NULL_TREE); - return cond; -} - -/* Local valueization callback that follows all-use SSA edges. */ - -static tree -ifcvt_follow_ssa_use_edges (tree val) -{ - return val; -} - -/* Replace a scalar PHI node with a COND_EXPR using COND as condition. - This routine can handle PHI nodes with more than two arguments. - - For example, - S1: A = PHI <x1(1), x2(5)> - is converted into, - S2: A = cond ? x1 : x2; - - The generated code is inserted at GSI that points to the top of - basic block's statement list. - If PHI node has more than two arguments a chain of conditional - expression is produced. */ - - -static void -predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) -{ - gimple *new_stmt = NULL, *reduc, *nop_reduc; - tree rhs, res, arg0, arg1, op0, op1, scev; - tree cond; - unsigned int index0; - unsigned int max, args_len; - edge e; - basic_block bb; - unsigned int i; - bool has_nop; - - res = gimple_phi_result (phi); - if (virtual_operand_p (res)) - return; - - if ((rhs = degenerate_phi_result (phi)) - || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father, - res)) - && !chrec_contains_undetermined (scev) - && scev != res - && (rhs = gimple_phi_arg_def (phi, 0)))) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Degenerate phi!\n"); - print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); - } - new_stmt = gimple_build_assign (res, rhs); - gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); - update_stmt (new_stmt); - return; - } - - bb = gimple_bb (phi); - if (EDGE_COUNT (bb->preds) == 2) - { - /* Predicate ordinary PHI node with 2 arguments. */ - edge first_edge, second_edge; - basic_block true_bb; - first_edge = EDGE_PRED (bb, 0); - second_edge = EDGE_PRED (bb, 1); - cond = bb_predicate (first_edge->src); - if (TREE_CODE (cond) == TRUTH_NOT_EXPR) - std::swap (first_edge, second_edge); - if (EDGE_COUNT (first_edge->src->succs) > 1) - { - cond = bb_predicate (second_edge->src); - if (TREE_CODE (cond) == TRUTH_NOT_EXPR) - cond = TREE_OPERAND (cond, 0); - else - first_edge = second_edge; - } - else - cond = bb_predicate (first_edge->src); - /* Gimplify the condition to a valid cond-expr conditonal operand. */ - cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), - is_gimple_condexpr, NULL_TREE, - true, GSI_SAME_STMT); - true_bb = first_edge->src; - if (EDGE_PRED (bb, 1)->src == true_bb) - { - arg0 = gimple_phi_arg_def (phi, 1); - arg1 = gimple_phi_arg_def (phi, 0); - } - else - { - arg0 = gimple_phi_arg_def (phi, 0); - arg1 = gimple_phi_arg_def (phi, 1); - } - if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1, - &op0, &op1, false, &has_nop, - &nop_reduc)) - { - /* Convert reduction stmt into vectorizable form. */ - rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1, - true_bb != gimple_bb (reduc), - has_nop, nop_reduc); - redundant_ssa_names.safe_push (std::make_pair (res, rhs)); - } - else - /* Build new RHS using selected condition and arguments. */ - rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond), - arg0, arg1); - new_stmt = gimple_build_assign (res, rhs); - gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); - gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt); - if (fold_stmt (&new_gsi, ifcvt_follow_ssa_use_edges)) - { - new_stmt = gsi_stmt (new_gsi); - update_stmt (new_stmt); - } - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "new phi replacement stmt\n"); - print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); - } - return; - } - - /* Create hashmap for PHI node which contain vector of argument indexes - having the same value. */ - bool swap = false; - hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map; - unsigned int num_args = gimple_phi_num_args (phi); - int max_ind = -1; - /* Vector of different PHI argument values. */ - auto_vec<tree> args (num_args); - - /* Compute phi_arg_map. */ - for (i = 0; i < num_args; i++) - { - tree arg; - - arg = gimple_phi_arg_def (phi, i); - if (!phi_arg_map.get (arg)) - args.quick_push (arg); - phi_arg_map.get_or_insert (arg).safe_push (i); - } - - /* Determine element with max number of occurrences. */ - max_ind = -1; - max = 1; - args_len = args.length (); - for (i = 0; i < args_len; i++) - { - unsigned int len; - if ((len = phi_arg_map.get (args[i])->length ()) > max) - { - max_ind = (int) i; - max = len; - } - } - - /* Put element with max number of occurences to the end of ARGS. */ - if (max_ind != -1 && max_ind +1 != (int) args_len) - std::swap (args[args_len - 1], args[max_ind]); - - /* Handle one special case when number of arguments with different values - is equal 2 and one argument has the only occurrence. Such PHI can be - handled as if would have only 2 arguments. */ - if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1) - { - vec<int> *indexes; - indexes = phi_arg_map.get (args[0]); - index0 = (*indexes)[0]; - arg0 = args[0]; - arg1 = args[1]; - e = gimple_phi_arg_edge (phi, index0); - cond = bb_predicate (e->src); - if (TREE_CODE (cond) == TRUTH_NOT_EXPR) - { - swap = true; - cond = TREE_OPERAND (cond, 0); - } - /* Gimplify the condition to a valid cond-expr conditonal operand. */ - cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), - is_gimple_condexpr, NULL_TREE, - true, GSI_SAME_STMT); - if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1, - &op0, &op1, true, &has_nop, &nop_reduc))) - rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond), - swap? arg1 : arg0, - swap? arg0 : arg1); - else - { - /* Convert reduction stmt into vectorizable form. */ - rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1, - swap,has_nop, nop_reduc); - redundant_ssa_names.safe_push (std::make_pair (res, rhs)); - } - new_stmt = gimple_build_assign (res, rhs); - gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); - update_stmt (new_stmt); - } - else - { - /* Common case. */ - vec<int> *indexes; - tree type = TREE_TYPE (gimple_phi_result (phi)); - tree lhs; - arg1 = args[1]; - for (i = 0; i < args_len; i++) - { - arg0 = args[i]; - indexes = phi_arg_map.get (args[i]); - if (i != args_len - 1) - lhs = make_temp_ssa_name (type, NULL, "_ifc_"); - else - lhs = res; - cond = gen_phi_arg_condition (phi, indexes, gsi); - rhs = fold_build_cond_expr (type, unshare_expr (cond), - arg0, arg1); - new_stmt = gimple_build_assign (lhs, rhs); - gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); - update_stmt (new_stmt); - arg1 = lhs; - } - } - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "new extended phi replacement stmt\n"); - print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); - } -} - -/* Replaces in LOOP all the scalar phi nodes other than those in the - LOOP->header block with conditional modify expressions. */ - -static void -predicate_all_scalar_phis (class loop *loop) -{ - basic_block bb; - unsigned int orig_loop_num_nodes = loop->num_nodes; - unsigned int i; - - for (i = 1; i < orig_loop_num_nodes; i++) - { - gphi *phi; - gimple_stmt_iterator gsi; - gphi_iterator phi_gsi; - bb = ifc_bbs[i]; - - if (bb == loop->header) - continue; - - phi_gsi = gsi_start_phis (bb); - if (gsi_end_p (phi_gsi)) - continue; - - gsi = gsi_after_labels (bb); - while (!gsi_end_p (phi_gsi)) - { - phi = phi_gsi.phi (); - if (virtual_operand_p (gimple_phi_result (phi))) - gsi_next (&phi_gsi); - else - { - predicate_scalar_phi (phi, &gsi); - remove_phi_node (&phi_gsi, false); - } - } - } -} - -/* Insert in each basic block of LOOP the statements produced by the - gimplification of the predicates. */ - -static void -insert_gimplified_predicates (loop_p loop) -{ - unsigned int i; - - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = ifc_bbs[i]; - gimple_seq stmts; - if (!is_predicated (bb)) - gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL); - if (!is_predicated (bb)) - { - /* Do not insert statements for a basic block that is not - predicated. Also make sure that the predicate of the - basic block is set to true. */ - reset_bb_predicate (bb); - continue; - } - - stmts = bb_predicate_gimplified_stmts (bb); - if (stmts) - { - if (need_to_predicate) - { - /* Insert the predicate of the BB just after the label, - as the if-conversion of memory writes will use this - predicate. */ - gimple_stmt_iterator gsi = gsi_after_labels (bb); - gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); - } - else - { - /* Insert the predicate of the BB at the end of the BB - as this would reduce the register pressure: the only - use of this predicate will be in successor BBs. */ - gimple_stmt_iterator gsi = gsi_last_bb (bb); - - if (gsi_end_p (gsi) - || stmt_ends_bb_p (gsi_stmt (gsi))) - gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); - else - gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT); - } - - /* Once the sequence is code generated, set it to NULL. */ - set_bb_predicate_gimplified_stmts (bb, NULL); - } - } -} - -/* Helper function for predicate_statements. Returns index of existent - mask if it was created for given SIZE and -1 otherwise. */ - -static int -mask_exists (int size, const vec<int> &vec) -{ - unsigned int ix; - int v; - FOR_EACH_VEC_ELT (vec, ix, v) - if (v == size) - return (int) ix; - return -1; -} - -/* Helper function for predicate_statements. STMT is a memory read or - write and it needs to be predicated by MASK. Return a statement - that does so. */ - -static gimple * -predicate_load_or_store (gimple_stmt_iterator *gsi, gassign *stmt, tree mask) -{ - gcall *new_stmt; - - tree lhs = gimple_assign_lhs (stmt); - tree rhs = gimple_assign_rhs1 (stmt); - tree ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs; - mark_addressable (ref); - tree addr = force_gimple_operand_gsi (gsi, build_fold_addr_expr (ref), - true, NULL_TREE, true, GSI_SAME_STMT); - tree ptr = build_int_cst (reference_alias_ptr_type (ref), - get_object_alignment (ref)); - /* Copy points-to info if possible. */ - if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr)) - copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr), - ref); - if (TREE_CODE (lhs) == SSA_NAME) - { - new_stmt - = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr, - ptr, mask); - gimple_call_set_lhs (new_stmt, lhs); - gimple_set_vuse (new_stmt, gimple_vuse (stmt)); - } - else - { - new_stmt - = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr, - mask, rhs); - gimple_move_vops (new_stmt, stmt); - } - gimple_call_set_nothrow (new_stmt, true); - return new_stmt; -} - -/* STMT uses OP_LHS. Check whether it is equivalent to: - - ... = OP_MASK ? OP_LHS : X; - - Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is - known to have value OP_COND. */ - -static tree -check_redundant_cond_expr (gimple *stmt, tree op_mask, tree op_cond, - tree op_lhs) -{ - gassign *assign = dyn_cast <gassign *> (stmt); - if (!assign || gimple_assign_rhs_code (assign) != COND_EXPR) - return NULL_TREE; - - tree use_cond = gimple_assign_rhs1 (assign); - tree if_true = gimple_assign_rhs2 (assign); - tree if_false = gimple_assign_rhs3 (assign); - - if ((use_cond == op_mask || operand_equal_p (use_cond, op_cond, 0)) - && if_true == op_lhs) - return if_false; - - if (inverse_conditions_p (use_cond, op_cond) && if_false == op_lhs) - return if_true; - - return NULL_TREE; -} - -/* Return true if VALUE is available for use at STMT. SSA_NAMES is - the set of SSA names defined earlier in STMT's block. */ - -static bool -value_available_p (gimple *stmt, hash_set<tree_ssa_name_hash> *ssa_names, - tree value) -{ - if (is_gimple_min_invariant (value)) - return true; - - if (TREE_CODE (value) == SSA_NAME) - { - if (SSA_NAME_IS_DEFAULT_DEF (value)) - return true; - - basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value)); - basic_block use_bb = gimple_bb (stmt); - return (def_bb == use_bb - ? ssa_names->contains (value) - : dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)); - } - - return false; -} - -/* Helper function for predicate_statements. STMT is a potentially-trapping - arithmetic operation that needs to be predicated by MASK, an SSA_NAME that - has value COND. Return a statement that does so. SSA_NAMES is the set of - SSA names defined earlier in STMT's block. */ - -static gimple * -predicate_rhs_code (gassign *stmt, tree mask, tree cond, - hash_set<tree_ssa_name_hash> *ssa_names) -{ - tree lhs = gimple_assign_lhs (stmt); - tree_code code = gimple_assign_rhs_code (stmt); - unsigned int nops = gimple_num_ops (stmt); - internal_fn cond_fn = get_conditional_internal_fn (code); - - /* Construct the arguments to the conditional internal function. */ - auto_vec<tree, 8> args; - args.safe_grow (nops + 1, true); - args[0] = mask; - for (unsigned int i = 1; i < nops; ++i) - args[i] = gimple_op (stmt, i); - args[nops] = NULL_TREE; - - /* Look for uses of the result to see whether they are COND_EXPRs that can - be folded into the conditional call. */ - imm_use_iterator imm_iter; - gimple *use_stmt; - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs) - { - tree new_else = check_redundant_cond_expr (use_stmt, mask, cond, lhs); - if (new_else && value_available_p (stmt, ssa_names, new_else)) - { - if (!args[nops]) - args[nops] = new_else; - if (operand_equal_p (new_else, args[nops], 0)) - { - /* We have: - - LHS = IFN_COND (MASK, ..., ELSE); - X = MASK ? LHS : ELSE; - - which makes X equivalent to LHS. */ - tree use_lhs = gimple_assign_lhs (use_stmt); - redundant_ssa_names.safe_push (std::make_pair (use_lhs, lhs)); - } - } - } - if (!args[nops]) - args[nops] = targetm.preferred_else_value (cond_fn, TREE_TYPE (lhs), - nops - 1, &args[1]); - - /* Create and insert the call. */ - gcall *new_stmt = gimple_build_call_internal_vec (cond_fn, args); - gimple_call_set_lhs (new_stmt, lhs); - gimple_call_set_nothrow (new_stmt, true); - - return new_stmt; -} - -/* Predicate each write to memory in LOOP. - - This function transforms control flow constructs containing memory - writes of the form: - - | for (i = 0; i < N; i++) - | if (cond) - | A[i] = expr; - - into the following form that does not contain control flow: - - | for (i = 0; i < N; i++) - | A[i] = cond ? expr : A[i]; - - The original CFG looks like this: - - | bb_0 - | i = 0 - | end_bb_0 - | - | bb_1 - | if (i < N) goto bb_5 else goto bb_2 - | end_bb_1 - | - | bb_2 - | cond = some_computation; - | if (cond) goto bb_3 else goto bb_4 - | end_bb_2 - | - | bb_3 - | A[i] = expr; - | goto bb_4 - | end_bb_3 - | - | bb_4 - | goto bb_1 - | end_bb_4 - - insert_gimplified_predicates inserts the computation of the COND - expression at the beginning of the destination basic block: - - | bb_0 - | i = 0 - | end_bb_0 - | - | bb_1 - | if (i < N) goto bb_5 else goto bb_2 - | end_bb_1 - | - | bb_2 - | cond = some_computation; - | if (cond) goto bb_3 else goto bb_4 - | end_bb_2 - | - | bb_3 - | cond = some_computation; - | A[i] = expr; - | goto bb_4 - | end_bb_3 - | - | bb_4 - | goto bb_1 - | end_bb_4 - - predicate_statements is then predicating the memory write as follows: - - | bb_0 - | i = 0 - | end_bb_0 - | - | bb_1 - | if (i < N) goto bb_5 else goto bb_2 - | end_bb_1 - | - | bb_2 - | if (cond) goto bb_3 else goto bb_4 - | end_bb_2 - | - | bb_3 - | cond = some_computation; - | A[i] = cond ? expr : A[i]; - | goto bb_4 - | end_bb_3 - | - | bb_4 - | goto bb_1 - | end_bb_4 - - and finally combine_blocks removes the basic block boundaries making - the loop vectorizable: - - | bb_0 - | i = 0 - | if (i < N) goto bb_5 else goto bb_1 - | end_bb_0 - | - | bb_1 - | cond = some_computation; - | A[i] = cond ? expr : A[i]; - | if (i < N) goto bb_5 else goto bb_4 - | end_bb_1 - | - | bb_4 - | goto bb_1 - | end_bb_4 -*/ - -static void -predicate_statements (loop_p loop) -{ - unsigned int i, orig_loop_num_nodes = loop->num_nodes; - auto_vec<int, 1> vect_sizes; - auto_vec<tree, 1> vect_masks; - hash_set<tree_ssa_name_hash> ssa_names; - - for (i = 1; i < orig_loop_num_nodes; i++) - { - gimple_stmt_iterator gsi; - basic_block bb = ifc_bbs[i]; - tree cond = bb_predicate (bb); - bool swap; - int index; - - if (is_true_predicate (cond)) - continue; - - swap = false; - if (TREE_CODE (cond) == TRUTH_NOT_EXPR) - { - swap = true; - cond = TREE_OPERAND (cond, 0); - } - - vect_sizes.truncate (0); - vect_masks.truncate (0); - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) - { - gassign *stmt = dyn_cast <gassign *> (gsi_stmt (gsi)); - tree lhs; - if (!stmt) - ; - else if (is_false_predicate (cond) - && gimple_vdef (stmt)) - { - unlink_stmt_vdef (stmt); - gsi_remove (&gsi, true); - release_defs (stmt); - continue; - } - else if (gimple_plf (stmt, GF_PLF_2)) - { - tree lhs = gimple_assign_lhs (stmt); - tree mask; - gimple *new_stmt; - gimple_seq stmts = NULL; - machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); - /* We checked before setting GF_PLF_2 that an equivalent - integer mode exists. */ - int bitsize = GET_MODE_BITSIZE (mode).to_constant (); - if (!vect_sizes.is_empty () - && (index = mask_exists (bitsize, vect_sizes)) != -1) - /* Use created mask. */ - mask = vect_masks[index]; - else - { - if (COMPARISON_CLASS_P (cond)) - mask = gimple_build (&stmts, TREE_CODE (cond), - boolean_type_node, - TREE_OPERAND (cond, 0), - TREE_OPERAND (cond, 1)); - else - mask = cond; - - if (swap) - { - tree true_val - = constant_boolean_node (true, TREE_TYPE (mask)); - mask = gimple_build (&stmts, BIT_XOR_EXPR, - TREE_TYPE (mask), mask, true_val); - } - gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); - - /* Save mask and its size for further use. */ - vect_sizes.safe_push (bitsize); - vect_masks.safe_push (mask); - } - if (gimple_assign_single_p (stmt)) - new_stmt = predicate_load_or_store (&gsi, stmt, mask); - else - new_stmt = predicate_rhs_code (stmt, mask, cond, &ssa_names); - - gsi_replace (&gsi, new_stmt, true); - } - else if (((lhs = gimple_assign_lhs (stmt)), true) - && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) - || POINTER_TYPE_P (TREE_TYPE (lhs))) - && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs)) - && arith_code_with_undefined_signed_overflow - (gimple_assign_rhs_code (stmt))) - { - gsi_remove (&gsi, true); - gimple_seq stmts = rewrite_to_defined_overflow (stmt); - bool first = true; - for (gimple_stmt_iterator gsi2 = gsi_start (stmts); - !gsi_end_p (gsi2);) - { - gassign *stmt2 = as_a <gassign *> (gsi_stmt (gsi2)); - gsi_remove (&gsi2, false); - if (first) - { - gsi_insert_before (&gsi, stmt2, GSI_NEW_STMT); - first = false; - } - else - gsi_insert_after (&gsi, stmt2, GSI_NEW_STMT); - } - } - else if (gimple_vdef (stmt)) - { - tree lhs = gimple_assign_lhs (stmt); - tree rhs = gimple_assign_rhs1 (stmt); - tree type = TREE_TYPE (lhs); - - lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi); - rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi); - if (swap) - std::swap (lhs, rhs); - cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond), - is_gimple_condexpr, NULL_TREE, - true, GSI_SAME_STMT); - rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs); - gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi)); - update_stmt (stmt); - } - lhs = gimple_get_lhs (gsi_stmt (gsi)); - if (lhs && TREE_CODE (lhs) == SSA_NAME) - ssa_names.add (lhs); - gsi_next (&gsi); - } - ssa_names.empty (); - } -} - -/* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks - other than the exit and latch of the LOOP. Also resets the - GIMPLE_DEBUG information. */ - -static void -remove_conditions_and_labels (loop_p loop) -{ - gimple_stmt_iterator gsi; - unsigned int i; - - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = ifc_bbs[i]; - - if (bb_with_exit_edge_p (loop, bb) - || bb == loop->latch) - continue; - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) - switch (gimple_code (gsi_stmt (gsi))) - { - case GIMPLE_COND: - case GIMPLE_LABEL: - gsi_remove (&gsi, true); - break; - - case GIMPLE_DEBUG: - /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ - if (gimple_debug_bind_p (gsi_stmt (gsi))) - { - gimple_debug_bind_reset_value (gsi_stmt (gsi)); - update_stmt (gsi_stmt (gsi)); - } - gsi_next (&gsi); - break; - - default: - gsi_next (&gsi); - } - } -} - -/* Combine all the basic blocks from LOOP into one or two super basic - blocks. Replace PHI nodes with conditional modify expressions. */ - -static void -combine_blocks (class loop *loop) -{ - basic_block bb, exit_bb, merge_target_bb; - unsigned int orig_loop_num_nodes = loop->num_nodes; - unsigned int i; - edge e; - edge_iterator ei; - - remove_conditions_and_labels (loop); - insert_gimplified_predicates (loop); - predicate_all_scalar_phis (loop); - - if (need_to_predicate || need_to_rewrite_undefined) - predicate_statements (loop); - - /* Merge basic blocks. */ - exit_bb = NULL; - bool *predicated = XNEWVEC (bool, orig_loop_num_nodes); - for (i = 0; i < orig_loop_num_nodes; i++) - { - bb = ifc_bbs[i]; - predicated[i] = !is_true_predicate (bb_predicate (bb)); - free_bb_predicate (bb); - if (bb_with_exit_edge_p (loop, bb)) - { - gcc_assert (exit_bb == NULL); - exit_bb = bb; - } - } - gcc_assert (exit_bb != loop->latch); - - merge_target_bb = loop->header; - - /* Get at the virtual def valid for uses starting at the first block - we merge into the header. Without a virtual PHI the loop has the - same virtual use on all stmts. */ - gphi *vphi = get_virtual_phi (loop->header); - tree last_vdef = NULL_TREE; - if (vphi) - { - last_vdef = gimple_phi_result (vphi); - for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header); - ! gsi_end_p (gsi); gsi_next (&gsi)) - if (gimple_vdef (gsi_stmt (gsi))) - last_vdef = gimple_vdef (gsi_stmt (gsi)); - } - for (i = 1; i < orig_loop_num_nodes; i++) - { - gimple_stmt_iterator gsi; - gimple_stmt_iterator last; - - bb = ifc_bbs[i]; - - if (bb == exit_bb || bb == loop->latch) - continue; - - /* We release virtual PHIs late because we have to propagate them - out using the current VUSE. The def might be the one used - after the loop. */ - vphi = get_virtual_phi (bb); - if (vphi) - { - /* When there's just loads inside the loop a stray virtual - PHI merging the uses can appear, update last_vdef from - it. */ - if (!last_vdef) - last_vdef = gimple_phi_arg_def (vphi, 0); - imm_use_iterator iter; - use_operand_p use_p; - gimple *use_stmt; - FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi)) - { - FOR_EACH_IMM_USE_ON_STMT (use_p, iter) - SET_USE (use_p, last_vdef); - } - if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi))) - SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1; - gsi = gsi_for_stmt (vphi); - remove_phi_node (&gsi, true); - } - - /* Make stmts member of loop->header and clear range info from all stmts - in BB which is now no longer executed conditional on a predicate we - could have derived it from. */ - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple *stmt = gsi_stmt (gsi); - gimple_set_bb (stmt, merge_target_bb); - /* Update virtual operands. */ - if (last_vdef) - { - use_operand_p use_p = ssa_vuse_operand (stmt); - if (use_p - && USE_FROM_PTR (use_p) != last_vdef) - SET_USE (use_p, last_vdef); - if (gimple_vdef (stmt)) - last_vdef = gimple_vdef (stmt); - } - else - /* If this is the first load we arrive at update last_vdef - so we handle stray PHIs correctly. */ - last_vdef = gimple_vuse (stmt); - if (predicated[i]) - { - ssa_op_iter i; - tree op; - FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF) - reset_flow_sensitive_info (op); - } - } - - /* Update stmt list. */ - last = gsi_last_bb (merge_target_bb); - gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT); - set_bb_seq (bb, NULL); - } - - /* Fixup virtual operands in the exit block. */ - if (exit_bb - && exit_bb != loop->header) - { - /* We release virtual PHIs late because we have to propagate them - out using the current VUSE. The def might be the one used - after the loop. */ - vphi = get_virtual_phi (exit_bb); - if (vphi) - { - /* When there's just loads inside the loop a stray virtual - PHI merging the uses can appear, update last_vdef from - it. */ - if (!last_vdef) - last_vdef = gimple_phi_arg_def (vphi, 0); - imm_use_iterator iter; - use_operand_p use_p; - gimple *use_stmt; - FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi)) - { - FOR_EACH_IMM_USE_ON_STMT (use_p, iter) - SET_USE (use_p, last_vdef); - } - if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi))) - SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1; - gimple_stmt_iterator gsi = gsi_for_stmt (vphi); - remove_phi_node (&gsi, true); - } - } - - /* Now remove all the edges in the loop, except for those from the exit - block and delete the blocks we elided. */ - for (i = 1; i < orig_loop_num_nodes; i++) - { - bb = ifc_bbs[i]; - - for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) - { - if (e->src == exit_bb) - ei_next (&ei); - else - remove_edge (e); - } - } - for (i = 1; i < orig_loop_num_nodes; i++) - { - bb = ifc_bbs[i]; - - if (bb == exit_bb || bb == loop->latch) - continue; - - delete_basic_block (bb); - } - - /* Re-connect the exit block. */ - if (exit_bb != NULL) - { - if (exit_bb != loop->header) - { - /* Connect this node to loop header. */ - make_single_succ_edge (loop->header, exit_bb, EDGE_FALLTHRU); - set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); - } - - /* Redirect non-exit edges to loop->latch. */ - FOR_EACH_EDGE (e, ei, exit_bb->succs) - { - if (!loop_exit_edge_p (loop, e)) - redirect_edge_and_branch (e, loop->latch); - } - set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); - } - else - { - /* If the loop does not have an exit, reconnect header and latch. */ - make_edge (loop->header, loop->latch, EDGE_FALLTHRU); - set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); - } - - /* If possible, merge loop header to the block with the exit edge. - This reduces the number of basic blocks to two, to please the - vectorizer that handles only loops with two nodes. */ - if (exit_bb - && exit_bb != loop->header) - { - if (can_merge_blocks_p (loop->header, exit_bb)) - merge_blocks (loop->header, exit_bb); - } - - free (ifc_bbs); - ifc_bbs = NULL; - free (predicated); -} - -/* Version LOOP before if-converting it; the original loop - will be if-converted, the new copy of the loop will not, - and the LOOP_VECTORIZED internal call will be guarding which - loop to execute. The vectorizer pass will fold this - internal call into either true or false. - - Note that this function intentionally invalidates profile. Both edges - out of LOOP_VECTORIZED must have 100% probability so the profile remains - consistent after the condition is folded in the vectorizer. */ - -static class loop * -version_loop_for_if_conversion (class loop *loop, vec<gimple *> *preds) -{ - basic_block cond_bb; - tree cond = make_ssa_name (boolean_type_node); - class loop *new_loop; - gimple *g; - gimple_stmt_iterator gsi; - unsigned int save_length; - - g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2, - build_int_cst (integer_type_node, loop->num), - integer_zero_node); - gimple_call_set_lhs (g, cond); - - /* Save BB->aux around loop_version as that uses the same field. */ - save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes; - void **saved_preds = XALLOCAVEC (void *, save_length); - for (unsigned i = 0; i < save_length; i++) - saved_preds[i] = ifc_bbs[i]->aux; - - initialize_original_copy_tables (); - /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED - is re-merged in the vectorizer. */ - new_loop = loop_version (loop, cond, &cond_bb, - profile_probability::always (), - profile_probability::always (), - profile_probability::always (), - profile_probability::always (), true); - free_original_copy_tables (); - - for (unsigned i = 0; i < save_length; i++) - ifc_bbs[i]->aux = saved_preds[i]; - - if (new_loop == NULL) - return NULL; - - new_loop->dont_vectorize = true; - new_loop->force_vectorize = false; - gsi = gsi_last_bb (cond_bb); - gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num)); - if (preds) - preds->safe_push (g); - gsi_insert_before (&gsi, g, GSI_SAME_STMT); - update_ssa (TODO_update_ssa); - return new_loop; -} - -/* Return true when LOOP satisfies the follow conditions that will - allow it to be recognized by the vectorizer for outer-loop - vectorization: - - The loop is not the root node of the loop tree. - - The loop has exactly one inner loop. - - The loop has a single exit. - - The loop header has a single successor, which is the inner - loop header. - - Each of the inner and outer loop latches have a single - predecessor. - - The loop exit block has a single predecessor, which is the - inner loop's exit block. */ - -static bool -versionable_outer_loop_p (class loop *loop) -{ - if (!loop_outer (loop) - || loop->dont_vectorize - || !loop->inner - || loop->inner->next - || !single_exit (loop) - || !single_succ_p (loop->header) - || single_succ (loop->header) != loop->inner->header - || !single_pred_p (loop->latch) - || !single_pred_p (loop->inner->latch)) - return false; - - basic_block outer_exit = single_pred (loop->latch); - basic_block inner_exit = single_pred (loop->inner->latch); - - if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit) - return false; - - if (dump_file) - fprintf (dump_file, "Found vectorizable outer loop for versioning\n"); - - return true; -} - -/* Performs splitting of critical edges. Skip splitting and return false - if LOOP will not be converted because: - - - LOOP is not well formed. - - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments. - - Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */ - -static bool -ifcvt_split_critical_edges (class loop *loop, bool aggressive_if_conv) -{ - basic_block *body; - basic_block bb; - unsigned int num = loop->num_nodes; - unsigned int i; - gimple *stmt; - edge e; - edge_iterator ei; - auto_vec<edge> critical_edges; - - /* Loop is not well formed. */ - if (num <= 2 || loop->inner || !single_exit (loop)) - return false; - - body = get_loop_body (loop); - for (i = 0; i < num; i++) - { - bb = body[i]; - if (!aggressive_if_conv - && phi_nodes (bb) - && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "BB %d has complicated PHI with more than %u args.\n", - bb->index, MAX_PHI_ARG_NUM); - - free (body); - return false; - } - if (bb == loop->latch || bb_with_exit_edge_p (loop, bb)) - continue; - - stmt = last_stmt (bb); - /* Skip basic blocks not ending with conditional branch. */ - if (!stmt || gimple_code (stmt) != GIMPLE_COND) - continue; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop) - critical_edges.safe_push (e); - } - free (body); - - while (critical_edges.length () > 0) - { - e = critical_edges.pop (); - /* Don't split if bb can be predicated along non-critical edge. */ - if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest)) - split_edge (e); - } - - return true; -} - -/* Delete redundant statements produced by predication which prevents - loop vectorization. */ - -static void -ifcvt_local_dce (class loop *loop) -{ - gimple *stmt; - gimple *stmt1; - gimple *phi; - gimple_stmt_iterator gsi; - auto_vec<gimple *> worklist; - enum gimple_code code; - use_operand_p use_p; - imm_use_iterator imm_iter; - - /* The loop has a single BB only. */ - basic_block bb = loop->header; - tree latch_vdef = NULL_TREE; - - worklist.create (64); - /* Consider all phi as live statements. */ - for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - phi = gsi_stmt (gsi); - gimple_set_plf (phi, GF_PLF_2, true); - worklist.safe_push (phi); - if (virtual_operand_p (gimple_phi_result (phi))) - latch_vdef = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); - } - /* Consider load/store statements, CALL and COND as live. */ - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - stmt = gsi_stmt (gsi); - if (is_gimple_debug (stmt)) - { - gimple_set_plf (stmt, GF_PLF_2, true); - continue; - } - if (gimple_store_p (stmt) || gimple_assign_load_p (stmt)) - { - gimple_set_plf (stmt, GF_PLF_2, true); - worklist.safe_push (stmt); - continue; - } - code = gimple_code (stmt); - if (code == GIMPLE_COND || code == GIMPLE_CALL) - { - gimple_set_plf (stmt, GF_PLF_2, true); - worklist.safe_push (stmt); - continue; - } - gimple_set_plf (stmt, GF_PLF_2, false); - - if (code == GIMPLE_ASSIGN) - { - tree lhs = gimple_assign_lhs (stmt); - FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs) - { - stmt1 = USE_STMT (use_p); - if (!is_gimple_debug (stmt1) && gimple_bb (stmt1) != bb) - { - gimple_set_plf (stmt, GF_PLF_2, true); - worklist.safe_push (stmt); - break; - } - } - } - } - /* Propagate liveness through arguments of live stmt. */ - while (worklist.length () > 0) - { - ssa_op_iter iter; - use_operand_p use_p; - tree use; - - stmt = worklist.pop (); - FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) - { - use = USE_FROM_PTR (use_p); - if (TREE_CODE (use) != SSA_NAME) - continue; - stmt1 = SSA_NAME_DEF_STMT (use); - if (gimple_bb (stmt1) != bb || gimple_plf (stmt1, GF_PLF_2)) - continue; - gimple_set_plf (stmt1, GF_PLF_2, true); - worklist.safe_push (stmt1); - } - } - /* Delete dead statements. */ - gsi = gsi_last_bb (bb); - while (!gsi_end_p (gsi)) - { - gimple_stmt_iterator gsiprev = gsi; - gsi_prev (&gsiprev); - stmt = gsi_stmt (gsi); - if (gimple_store_p (stmt)) - { - tree lhs = gimple_get_lhs (stmt); - ao_ref write; - ao_ref_init (&write, lhs); - - if (dse_classify_store (&write, stmt, false, NULL, NULL, latch_vdef) - == DSE_STORE_DEAD) - delete_dead_or_redundant_assignment (&gsi, "dead"); - gsi = gsiprev; - continue; - } - - if (gimple_plf (stmt, GF_PLF_2)) - { - gsi = gsiprev; - continue; - } - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); - } - gsi_remove (&gsi, true); - release_defs (stmt); - gsi = gsiprev; - } -} - -/* Return true if VALUE is already available on edge PE. */ - -static bool -ifcvt_available_on_edge_p (edge pe, tree value) -{ - if (is_gimple_min_invariant (value)) - return true; - - if (TREE_CODE (value) == SSA_NAME) - { - basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value)); - if (!def_bb || dominated_by_p (CDI_DOMINATORS, pe->dest, def_bb)) - return true; - } - - return false; -} - -/* Return true if STMT can be hoisted from if-converted loop LOOP to - edge PE. */ - -static bool -ifcvt_can_hoist (class loop *loop, edge pe, gimple *stmt) -{ - if (auto *call = dyn_cast<gcall *> (stmt)) - { - if (gimple_call_internal_p (call) - && internal_fn_mask_index (gimple_call_internal_fn (call)) >= 0) - return false; - } - else if (auto *assign = dyn_cast<gassign *> (stmt)) - { - if (gimple_assign_rhs_code (assign) == COND_EXPR) - return false; - } - else - return false; - - if (gimple_has_side_effects (stmt) - || gimple_could_trap_p (stmt) - || stmt_could_throw_p (cfun, stmt) - || gimple_vdef (stmt) - || gimple_vuse (stmt)) - return false; - - int num_args = gimple_num_args (stmt); - if (pe != loop_preheader_edge (loop)) - { - for (int i = 0; i < num_args; ++i) - if (!ifcvt_available_on_edge_p (pe, gimple_arg (stmt, i))) - return false; - } - else - { - for (int i = 0; i < num_args; ++i) - if (!expr_invariant_in_loop_p (loop, gimple_arg (stmt, i))) - return false; - } - - return true; -} - -/* Hoist invariant statements from LOOP to edge PE. */ - -static void -ifcvt_hoist_invariants (class loop *loop, edge pe) -{ - gimple_stmt_iterator hoist_gsi = {}; - unsigned int num_blocks = loop->num_nodes; - basic_block *body = get_loop_body (loop); - for (unsigned int i = 0; i < num_blocks; ++i) - for (gimple_stmt_iterator gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi);) - { - gimple *stmt = gsi_stmt (gsi); - if (ifcvt_can_hoist (loop, pe, stmt)) - { - /* Once we've hoisted one statement, insert other statements - after it. */ - gsi_remove (&gsi, false); - if (hoist_gsi.ptr) - gsi_insert_after (&hoist_gsi, stmt, GSI_NEW_STMT); - else - { - gsi_insert_on_edge_immediate (pe, stmt); - hoist_gsi = gsi_for_stmt (stmt); - } - continue; - } - gsi_next (&gsi); - } - free (body); -} - -/* If-convert LOOP when it is legal. For the moment this pass has no - profitability analysis. Returns non-zero todo flags when something - changed. */ - -unsigned int -tree_if_conversion (class loop *loop, vec<gimple *> *preds) -{ - unsigned int todo = 0; - bool aggressive_if_conv; - class loop *rloop; - bitmap exit_bbs; - edge pe; - - again: - rloop = NULL; - ifc_bbs = NULL; - need_to_predicate = false; - need_to_rewrite_undefined = false; - any_complicated_phi = false; - - /* Apply more aggressive if-conversion when loop or its outer loop were - marked with simd pragma. When that's the case, we try to if-convert - loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */ - aggressive_if_conv = loop->force_vectorize; - if (!aggressive_if_conv) - { - class loop *outer_loop = loop_outer (loop); - if (outer_loop && outer_loop->force_vectorize) - aggressive_if_conv = true; - } - - if (!ifcvt_split_critical_edges (loop, aggressive_if_conv)) - goto cleanup; - - if (!if_convertible_loop_p (loop) - || !dbg_cnt (if_conversion_tree)) - goto cleanup; - - if ((need_to_predicate || any_complicated_phi) - && ((!flag_tree_loop_vectorize && !loop->force_vectorize) - || loop->dont_vectorize)) - goto cleanup; - - /* The edge to insert invariant stmts on. */ - pe = loop_preheader_edge (loop); - - /* Since we have no cost model, always version loops unless the user - specified -ftree-loop-if-convert or unless versioning is required. - Either version this loop, or if the pattern is right for outer-loop - vectorization, version the outer loop. In the latter case we will - still if-convert the original inner loop. */ - if (need_to_predicate - || any_complicated_phi - || flag_tree_loop_if_convert != 1) - { - class loop *vloop - = (versionable_outer_loop_p (loop_outer (loop)) - ? loop_outer (loop) : loop); - class loop *nloop = version_loop_for_if_conversion (vloop, preds); - if (nloop == NULL) - goto cleanup; - if (vloop != loop) - { - /* If versionable_outer_loop_p decided to version the - outer loop, version also the inner loop of the non-vectorized - loop copy. So we transform: - loop1 - loop2 - into: - if (LOOP_VECTORIZED (1, 3)) - { - loop1 - loop2 - } - else - loop3 (copy of loop1) - if (LOOP_VECTORIZED (4, 5)) - loop4 (copy of loop2) - else - loop5 (copy of loop4) */ - gcc_assert (nloop->inner && nloop->inner->next == NULL); - rloop = nloop->inner; - } - else - /* If we versioned loop then make sure to insert invariant - stmts before the .LOOP_VECTORIZED check since the vectorizer - will re-use that for things like runtime alias versioning - whose condition can end up using those invariants. */ - pe = single_pred_edge (gimple_bb (preds->last ())); - } - - /* Now all statements are if-convertible. Combine all the basic - blocks into one huge basic block doing the if-conversion - on-the-fly. */ - combine_blocks (loop); - - /* Perform local CSE, this esp. helps the vectorizer analysis if loads - and stores are involved. CSE only the loop body, not the entry - PHIs, those are to be kept in sync with the non-if-converted copy. - ??? We'll still keep dead stores though. */ - exit_bbs = BITMAP_ALLOC (NULL); - bitmap_set_bit (exit_bbs, single_exit (loop)->dest->index); - bitmap_set_bit (exit_bbs, loop->latch->index); - - std::pair <tree, tree> *name_pair; - unsigned ssa_names_idx; - FOR_EACH_VEC_ELT (redundant_ssa_names, ssa_names_idx, name_pair) - replace_uses_by (name_pair->first, name_pair->second); - redundant_ssa_names.release (); - - todo |= do_rpo_vn (cfun, loop_preheader_edge (loop), exit_bbs); - - /* Delete dead predicate computations. */ - ifcvt_local_dce (loop); - BITMAP_FREE (exit_bbs); - - ifcvt_hoist_invariants (loop, pe); - - todo |= TODO_cleanup_cfg; - - cleanup: - if (ifc_bbs) - { - unsigned int i; - - for (i = 0; i < loop->num_nodes; i++) - free_bb_predicate (ifc_bbs[i]); - - free (ifc_bbs); - ifc_bbs = NULL; - } - if (rloop != NULL) - { - loop = rloop; - goto again; - } - - return todo; -} - -/* Tree if-conversion pass management. */ - -namespace { - -const pass_data pass_data_if_conversion = -{ - GIMPLE_PASS, /* type */ - "ifcvt", /* name */ - OPTGROUP_NONE, /* optinfo_flags */ - TV_TREE_LOOP_IFCVT, /* tv_id */ - ( PROP_cfg | PROP_ssa ), /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ -}; - -class pass_if_conversion : public gimple_opt_pass -{ -public: - pass_if_conversion (gcc::context *ctxt) - : gimple_opt_pass (pass_data_if_conversion, ctxt) - {} - - /* opt_pass methods: */ - virtual bool gate (function *); - virtual unsigned int execute (function *); - -}; // class pass_if_conversion - -bool -pass_if_conversion::gate (function *fun) -{ - return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops) - && flag_tree_loop_if_convert != 0) - || flag_tree_loop_if_convert == 1); -} - -unsigned int -pass_if_conversion::execute (function *fun) -{ - unsigned todo = 0; - - if (number_of_loops (fun) <= 1) - return 0; - - auto_vec<gimple *> preds; - for (auto loop : loops_list (cfun, 0)) - if (flag_tree_loop_if_convert == 1 - || ((flag_tree_loop_vectorize || loop->force_vectorize) - && !loop->dont_vectorize)) - todo |= tree_if_conversion (loop, &preds); - - if (todo) - { - free_numbers_of_iterations_estimates (fun); - scev_reset (); - } - - if (flag_checking) - { - basic_block bb; - FOR_EACH_BB_FN (bb, fun) - gcc_assert (!bb->aux); - } - - /* Perform IL update now, it might elide some loops. */ - if (todo & TODO_cleanup_cfg) - { - cleanup_tree_cfg (); - if (need_ssa_update_p (fun)) - todo |= TODO_update_ssa; - } - if (todo & TODO_update_ssa_any) - update_ssa (todo & TODO_update_ssa_any); - - /* If if-conversion elided the loop fall back to the original one. */ - for (unsigned i = 0; i < preds.length (); ++i) - { - gimple *g = preds[i]; - if (!gimple_bb (g)) - continue; - unsigned ifcvt_loop = tree_to_uhwi (gimple_call_arg (g, 0)); - if (!get_loop (fun, ifcvt_loop)) - { - if (dump_file) - fprintf (dump_file, "If-converted loop vanished\n"); - fold_loop_internal_call (g, boolean_false_node); - } - } - - return 0; -} - -} // anon namespace - -gimple_opt_pass * -make_pass_if_conversion (gcc::context *ctxt) -{ - return new pass_if_conversion (ctxt); -} |