/* Support routines for Value Range Propagation (VRP). Copyright (C) 2005-2023 Free Software Foundation, Inc. Contributed by Diego Novillo . 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 . */ #include "config.h" #include "system.h" #include "coretypes.h" #include "basic-block.h" #include "bitmap.h" #include "sbitmap.h" #include "options.h" #include "dominance.h" #include "function.h" #include "cfg.h" #include "tree.h" #include "gimple.h" #include "tree-pass.h" #include "ssa.h" #include "gimple-pretty-print.h" #include "fold-const.h" #include "cfganal.h" #include "gimple-iterator.h" #include "tree-cfg.h" #include "tree-ssa-loop-manip.h" #include "tree-ssa-loop-niter.h" #include "tree-into-ssa.h" #include "cfgloop.h" #include "tree-scalar-evolution.h" #include "tree-ssa-propagate.h" #include "domwalk.h" #include "vr-values.h" #include "gimple-array-bounds.h" #include "gimple-range.h" #include "gimple-range-path.h" #include "value-pointer-equiv.h" #include "gimple-fold.h" #include "tree-dfa.h" #include "tree-ssa-dce.h" // This class is utilized by VRP and ranger to remove __builtin_unreachable // calls, and reflect any resulting global ranges. // // maybe_register() is called on condition statements , and if that // matches the pattern of one branch being a builtin_unreachable, either check // for early removal or register the resulting executable edge in a list. // // During early/non-final processing, we check to see if ALL exports from the // block can be safely updated with a new global value. If they can, then // we rewrite the condition and update those values immediately. Otherwise // the unreachable condition is left in the IL until the final pass. // // During final processing, after all blocks have been registered, // remove_and_update_globals() will // - check all exports from registered blocks // - ensure the cache entry of each export is set with the appropriate range // - rewrite the conditions to take the executable edge // - perform DCE on any feeding instructions to those rewritten conditions // // Then each of the immediate use chain of each export is walked, and a new // global range created by unioning the ranges at all remaining use locations. class remove_unreachable { public: remove_unreachable (gimple_ranger &r, bool all) : m_ranger (r), final_p (all) { m_list.create (30); } ~remove_unreachable () { m_list.release (); } void handle_early (gimple *s, edge e); void maybe_register (gimple *s); bool remove_and_update_globals (); vec > m_list; gimple_ranger &m_ranger; bool final_p; }; // Check if block BB has a __builtin_unreachable () call on one arm, and // register the executable edge if so. void remove_unreachable::maybe_register (gimple *s) { gcc_checking_assert (gimple_code (s) == GIMPLE_COND); basic_block bb = gimple_bb (s); edge e0 = EDGE_SUCC (bb, 0); basic_block bb0 = e0->dest; bool un0 = EDGE_COUNT (bb0->succs) == 0 && gimple_seq_unreachable_p (bb_seq (bb0)); edge e1 = EDGE_SUCC (bb, 1); basic_block bb1 = e1->dest; bool un1 = EDGE_COUNT (bb1->succs) == 0 && gimple_seq_unreachable_p (bb_seq (bb1)); // If the 2 blocks are not different, ignore. if (un0 == un1) return; // Constant expressions are ignored. if (TREE_CODE (gimple_cond_lhs (s)) != SSA_NAME && TREE_CODE (gimple_cond_rhs (s)) != SSA_NAME) return; edge e = un0 ? e1 : e0; if (!final_p) handle_early (s, e); else m_list.safe_push (std::make_pair (e->src->index, e->dest->index)); } // Return true if all uses of NAME are dominated by by block BB. 1 use // is allowed in block BB, This is one we hope to remove. // ie // _2 = _1 & 7; // if (_2 != 0) // goto ; [0.00%] // Any additional use of _1 or _2 in this block invalidates early replacement. static bool fully_replaceable (tree name, basic_block bb) { use_operand_p use_p; imm_use_iterator iter; bool saw_in_bb = false; // If a name loads from memory, we may lose information used in // commoning opportunities later. See tree-ssa/ssa-pre-34.c. gimple *def_stmt = SSA_NAME_DEF_STMT (name); if (gimple_vuse (def_stmt)) return false; FOR_EACH_IMM_USE_FAST (use_p, iter, name) { gimple *use_stmt = USE_STMT (use_p); // Ignore debug stmts and the branch. if (is_gimple_debug (use_stmt)) continue; basic_block use_bb = gimple_bb (use_stmt); // Only one use in the block allowed to avoid complicated cases. if (use_bb == bb) { if (saw_in_bb) return false; else saw_in_bb = true; } else if (!dominated_by_p (CDI_DOMINATORS, use_bb, bb)) return false; } return true; } // This routine is called to check builtin_unreachable calls during any // time before final removal. The only way we can be sure it does not // provide any additional information is to expect that we can update the // global values of all exports from a block. This means the branch // to the unreachable call must dominate all uses of those ssa-names, with // the exception that there can be a single use in the block containing // the branch. IF the name used in the branch is defined in the block, it may // contain the name of something else that will be an export. And likewise // that may also use another name that is an export etc. // // As long as there is only a single use, we can be sure that there are no other // side effects (like being passed to a call, or stored to a global, etc. // This means we will miss cases where there are 2 or more uses that have // no interveneing statements that may had side effects, but it catches most // of the caes we care about, and prevents expensive in depth analysis. // // Ranger will still reflect the proper ranges at other places in these missed // cases, we simply will not remove/set globals early. void remove_unreachable::handle_early (gimple *s, edge e) { bool lhs_p = TREE_CODE (gimple_cond_lhs (s)) == SSA_NAME; bool rhs_p = TREE_CODE (gimple_cond_rhs (s)) == SSA_NAME; // Do not remove __builtin_unreachable if it confers a relation, or // that relation may be lost in subsequent passes. if (lhs_p && rhs_p) return; // Do not remove addresses early. ie if (x == &y) if (lhs_p && TREE_CODE (gimple_cond_rhs (s)) == ADDR_EXPR) return; gcc_checking_assert (gimple_outgoing_range_stmt_p (e->src) == s); gcc_checking_assert (!final_p); // Check if every export use is dominated by this branch. tree name; FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori (), e->src, name) { if (!fully_replaceable (name, e->src)) return; } // Set the global value for each. FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori (), e->src, name) { Value_Range r (TREE_TYPE (name)); m_ranger.range_on_entry (r, e->dest, name); // Nothing at this late stage we can do if the write fails. if (!set_range_info (name, r)) continue; if (dump_file) { fprintf (dump_file, "Global Exported (via early unreachable): "); print_generic_expr (dump_file, name, TDF_SLIM); fprintf (dump_file, " = "); gimple_range_global (r, name); r.dump (dump_file); fputc ('\n', dump_file); } } tree ssa = lhs_p ? gimple_cond_lhs (s) : gimple_cond_rhs (s); // Rewrite the condition. if (e->flags & EDGE_TRUE_VALUE) gimple_cond_make_true (as_a (s)); else gimple_cond_make_false (as_a (s)); update_stmt (s); // If the name on S is defined in this block, see if there is DCE work to do. if (gimple_bb (SSA_NAME_DEF_STMT (ssa)) == e->src) { auto_bitmap dce; bitmap_set_bit (dce, SSA_NAME_VERSION (ssa)); simple_dce_from_worklist (dce); } } // Process the edges in the list, change the conditions and removing any // dead code feeding those conditions. Calculate the range of any // names that may have been exported from those blocks, and determine if // there is any updates to their global ranges.. // Return true if any builtin_unreachables/globals eliminated/updated. bool remove_unreachable::remove_and_update_globals () { if (m_list.length () == 0) return false; // Ensure the cache in SCEV has been cleared before processing // globals to be removed. scev_reset (); bool change = false; tree name; unsigned i; bitmap_iterator bi; auto_bitmap all_exports; for (i = 0; i < m_list.length (); i++) { auto eb = m_list[i]; basic_block src = BASIC_BLOCK_FOR_FN (cfun, eb.first); basic_block dest = BASIC_BLOCK_FOR_FN (cfun, eb.second); if (!src || !dest) continue; edge e = find_edge (src, dest); gimple *s = gimple_outgoing_range_stmt_p (e->src); gcc_checking_assert (gimple_code (s) == GIMPLE_COND); bool dominate_exit_p = true; FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori (), e->src, name) { // Ensure the cache is set for NAME in the succ block. Value_Range r(TREE_TYPE (name)); Value_Range ex(TREE_TYPE (name)); m_ranger.range_on_entry (r, e->dest, name); m_ranger.range_on_entry (ex, EXIT_BLOCK_PTR_FOR_FN (cfun), name); // If the range produced by this __builtin_unreachacble expression // is not fully reflected in the range at exit, then it does not // dominate the exit of the function. if (ex.intersect (r)) dominate_exit_p = false; } // If the exit is dominated, add to the export list. Otherwise if this // isn't the final VRP pass, leave the call in the IL. if (dominate_exit_p) bitmap_ior_into (all_exports, m_ranger.gori ().exports (e->src)); else if (!final_p) continue; change = true; // Rewrite the condition. if (e->flags & EDGE_TRUE_VALUE) gimple_cond_make_true (as_a (s)); else gimple_cond_make_false (as_a (s)); update_stmt (s); } if (bitmap_empty_p (all_exports)) return false; // Invoke DCE on all exported names to eliminate dead feeding defs. auto_bitmap dce; bitmap_copy (dce, all_exports); // Don't attempt to DCE parameters. EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi) if (!ssa_name (i) || SSA_NAME_IS_DEFAULT_DEF (ssa_name (i))) bitmap_clear_bit (dce, i); simple_dce_from_worklist (dce); // Loop over all uses of each name and find maximal range. This is the // new global range. use_operand_p use_p; imm_use_iterator iter; EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi) { name = ssa_name (i); if (!name || SSA_NAME_IN_FREE_LIST (name)) continue; Value_Range r (TREE_TYPE (name)); Value_Range exp_range (TREE_TYPE (name)); r.set_undefined (); FOR_EACH_IMM_USE_FAST (use_p, iter, name) { gimple *use_stmt = USE_STMT (use_p); if (is_gimple_debug (use_stmt)) continue; if (!m_ranger.range_of_expr (exp_range, name, use_stmt)) exp_range.set_varying (TREE_TYPE (name)); r.union_ (exp_range); if (r.varying_p ()) break; } // Include the on-exit range to ensure non-dominated unreachables // don't incorrectly impact the global range. m_ranger.range_on_entry (exp_range, EXIT_BLOCK_PTR_FOR_FN (cfun), name); r.union_ (exp_range); if (r.varying_p () || r.undefined_p ()) continue; if (!set_range_info (name, r)) continue; change = true; if (dump_file) { fprintf (dump_file, "Global Exported (via unreachable): "); print_generic_expr (dump_file, name, TDF_SLIM); fprintf (dump_file, " = "); gimple_range_global (r, name); r.dump (dump_file); fputc ('\n', dump_file); } } return change; } /* VR_TYPE describes a range with minimum value *MIN and maximum value *MAX. Restrict the range to the set of values that have no bits set outside NONZERO_BITS. Update *MIN and *MAX and return the new range type. SGN gives the sign of the values described by the range. */ enum value_range_kind intersect_range_with_nonzero_bits (enum value_range_kind vr_type, wide_int *min, wide_int *max, const wide_int &nonzero_bits, signop sgn) { if (vr_type == VR_ANTI_RANGE) { /* The VR_ANTI_RANGE is equivalent to the union of the ranges A: [-INF, *MIN) and B: (*MAX, +INF]. First use NONZERO_BITS to create an inclusive upper bound for A and an inclusive lower bound for B. */ wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits); wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits); /* If the calculation of A_MAX wrapped, A is effectively empty and A_MAX is the highest value that satisfies NONZERO_BITS. Likewise if the calculation of B_MIN wrapped, B is effectively empty and B_MIN is the lowest value that satisfies NONZERO_BITS. */ bool a_empty = wi::ge_p (a_max, *min, sgn); bool b_empty = wi::le_p (b_min, *max, sgn); /* If both A and B are empty, there are no valid values. */ if (a_empty && b_empty) return VR_UNDEFINED; /* If exactly one of A or B is empty, return a VR_RANGE for the other one. */ if (a_empty || b_empty) { *min = b_min; *max = a_max; gcc_checking_assert (wi::le_p (*min, *max, sgn)); return VR_RANGE; } /* Update the VR_ANTI_RANGE bounds. */ *min = a_max + 1; *max = b_min - 1; gcc_checking_assert (wi::le_p (*min, *max, sgn)); /* Now check whether the excluded range includes any values that satisfy NONZERO_BITS. If not, switch to a full VR_RANGE. */ if (wi::round_up_for_mask (*min, nonzero_bits) == b_min) { unsigned int precision = min->get_precision (); *min = wi::min_value (precision, sgn); *max = wi::max_value (precision, sgn); vr_type = VR_RANGE; } } if (vr_type == VR_RANGE || vr_type == VR_VARYING) { *max = wi::round_down_for_mask (*max, nonzero_bits); /* Check that the range contains at least one valid value. */ if (wi::gt_p (*min, *max, sgn)) return VR_UNDEFINED; *min = wi::round_up_for_mask (*min, nonzero_bits); gcc_checking_assert (wi::le_p (*min, *max, sgn)); } return vr_type; } /* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE otherwise. We only handle additive operations and set NEG to true if the symbol is negated and INV to the invariant part, if any. */ static tree get_single_symbol (tree t, bool *neg, tree *inv) { bool neg_; tree inv_; *inv = NULL_TREE; *neg = false; if (TREE_CODE (t) == PLUS_EXPR || TREE_CODE (t) == POINTER_PLUS_EXPR || TREE_CODE (t) == MINUS_EXPR) { if (is_gimple_min_invariant (TREE_OPERAND (t, 0))) { neg_ = (TREE_CODE (t) == MINUS_EXPR); inv_ = TREE_OPERAND (t, 0); t = TREE_OPERAND (t, 1); } else if (is_gimple_min_invariant (TREE_OPERAND (t, 1))) { neg_ = false; inv_ = TREE_OPERAND (t, 1); t = TREE_OPERAND (t, 0); } else return NULL_TREE; } else { neg_ = false; inv_ = NULL_TREE; } if (TREE_CODE (t) == NEGATE_EXPR) { t = TREE_OPERAND (t, 0); neg_ = !neg_; } if (TREE_CODE (t) != SSA_NAME) return NULL_TREE; if (inv_ && TREE_OVERFLOW_P (inv_)) inv_ = drop_tree_overflow (inv_); *neg = neg_; *inv = inv_; return t; } /* Compare two values VAL1 and VAL2. Return -2 if VAL1 and VAL2 cannot be compared at compile-time, -1 if VAL1 < VAL2, 0 if VAL1 == VAL2, +1 if VAL1 > VAL2, and +2 if VAL1 != VAL2 This is similar to tree_int_cst_compare but supports pointer values and values that cannot be compared at compile time. If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to true if the return value is only valid if we assume that signed overflow is undefined. */ int compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p) { if (val1 == val2) return 0; /* Below we rely on the fact that VAL1 and VAL2 are both pointers or both integers. */ gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1)) == POINTER_TYPE_P (TREE_TYPE (val2))); /* Convert the two values into the same type. This is needed because sizetype causes sign extension even for unsigned types. */ if (!useless_type_conversion_p (TREE_TYPE (val1), TREE_TYPE (val2))) val2 = fold_convert (TREE_TYPE (val1), val2); const bool overflow_undefined = INTEGRAL_TYPE_P (TREE_TYPE (val1)) && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)); tree inv1, inv2; bool neg1, neg2; tree sym1 = get_single_symbol (val1, &neg1, &inv1); tree sym2 = get_single_symbol (val2, &neg2, &inv2); /* If VAL1 and VAL2 are of the form '[-]NAME [+ CST]', return -1 or +1 accordingly. If VAL1 and VAL2 don't use the same name, return -2. */ if (sym1 && sym2) { /* Both values must use the same name with the same sign. */ if (sym1 != sym2 || neg1 != neg2) return -2; /* [-]NAME + CST == [-]NAME + CST. */ if (inv1 == inv2) return 0; /* If overflow is defined we cannot simplify more. */ if (!overflow_undefined) return -2; if (strict_overflow_p != NULL /* Symbolic range building sets the no-warning bit to declare that overflow doesn't happen. */ && (!inv1 || !warning_suppressed_p (val1, OPT_Woverflow)) && (!inv2 || !warning_suppressed_p (val2, OPT_Woverflow))) *strict_overflow_p = true; if (!inv1) inv1 = build_int_cst (TREE_TYPE (val1), 0); if (!inv2) inv2 = build_int_cst (TREE_TYPE (val2), 0); return wi::cmp (wi::to_wide (inv1), wi::to_wide (inv2), TYPE_SIGN (TREE_TYPE (val1))); } const bool cst1 = is_gimple_min_invariant (val1); const bool cst2 = is_gimple_min_invariant (val2); /* If one is of the form '[-]NAME + CST' and the other is constant, then it might be possible to say something depending on the constants. */ if ((sym1 && inv1 && cst2) || (sym2 && inv2 && cst1)) { if (!overflow_undefined) return -2; if (strict_overflow_p != NULL /* Symbolic range building sets the no-warning bit to declare that overflow doesn't happen. */ && (!sym1 || !warning_suppressed_p (val1, OPT_Woverflow)) && (!sym2 || !warning_suppressed_p (val2, OPT_Woverflow))) *strict_overflow_p = true; const signop sgn = TYPE_SIGN (TREE_TYPE (val1)); tree cst = cst1 ? val1 : val2; tree inv = cst1 ? inv2 : inv1; /* Compute the difference between the constants. If it overflows or underflows, this means that we can trivially compare the NAME with it and, consequently, the two values with each other. */ wide_int diff = wi::to_wide (cst) - wi::to_wide (inv); if (wi::cmp (0, wi::to_wide (inv), sgn) != wi::cmp (diff, wi::to_wide (cst), sgn)) { const int res = wi::cmp (wi::to_wide (cst), wi::to_wide (inv), sgn); return cst1 ? res : -res; } return -2; } /* We cannot say anything more for non-constants. */ if (!cst1 || !cst2) return -2; if (!POINTER_TYPE_P (TREE_TYPE (val1))) { /* We cannot compare overflowed values. */ if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2)) return -2; if (TREE_CODE (val1) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST) return tree_int_cst_compare (val1, val2); if (poly_int_tree_p (val1) && poly_int_tree_p (val2)) { if (known_eq (wi::to_poly_widest (val1), wi::to_poly_widest (val2))) return 0; if (known_lt (wi::to_poly_widest (val1), wi::to_poly_widest (val2))) return -1; if (known_gt (wi::to_poly_widest (val1), wi::to_poly_widest (val2))) return 1; } return -2; } else { if (TREE_CODE (val1) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST) { /* We cannot compare overflowed values. */ if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2)) return -2; return tree_int_cst_compare (val1, val2); } /* First see if VAL1 and VAL2 are not the same. */ if (operand_equal_p (val1, val2, 0)) return 0; fold_defer_overflow_warnings (); /* If VAL1 is a lower address than VAL2, return -1. */ tree t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val1, val2); if (t && integer_onep (t)) { fold_undefer_and_ignore_overflow_warnings (); return -1; } /* If VAL1 is a higher address than VAL2, return +1. */ t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val2, val1); if (t && integer_onep (t)) { fold_undefer_and_ignore_overflow_warnings (); return 1; } /* If VAL1 is different than VAL2, return +2. */ t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2); fold_undefer_and_ignore_overflow_warnings (); if (t && integer_onep (t)) return 2; return -2; } } /* Compare values like compare_values_warnv. */ int compare_values (tree val1, tree val2) { bool sop; return compare_values_warnv (val1, val2, &sop); } /* Helper for overflow_comparison_p OP0 CODE OP1 is a comparison. Examine the comparison and potentially OP1's defining statement to see if it ultimately has the form OP0 CODE (OP0 PLUS INTEGER_CST) If so, return TRUE indicating this is an overflow test and store into *NEW_CST an updated constant that can be used in a narrowed range test. REVERSED indicates if the comparison was originally: OP1 CODE' OP0. This affects how we build the updated constant. */ static bool overflow_comparison_p_1 (enum tree_code code, tree op0, tree op1, bool reversed, tree *new_cst) { /* See if this is a relational operation between two SSA_NAMES with unsigned, overflow wrapping values. If so, check it more deeply. */ if ((code == LT_EXPR || code == LE_EXPR || code == GE_EXPR || code == GT_EXPR) && TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (op0)) && TYPE_UNSIGNED (TREE_TYPE (op0)) && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op0))) { gimple *op1_def = SSA_NAME_DEF_STMT (op1); /* Now look at the defining statement of OP1 to see if it adds or subtracts a nonzero constant from another operand. */ if (op1_def && is_gimple_assign (op1_def) && gimple_assign_rhs_code (op1_def) == PLUS_EXPR && TREE_CODE (gimple_assign_rhs2 (op1_def)) == INTEGER_CST && !integer_zerop (gimple_assign_rhs2 (op1_def))) { tree target = gimple_assign_rhs1 (op1_def); /* If we did not find our target SSA_NAME, then this is not an overflow test. */ if (op0 != target) return false; tree type = TREE_TYPE (op0); wide_int max = wi::max_value (TYPE_PRECISION (type), UNSIGNED); tree inc = gimple_assign_rhs2 (op1_def); if (reversed) *new_cst = wide_int_to_tree (type, max + wi::to_wide (inc)); else *new_cst = wide_int_to_tree (type, max - wi::to_wide (inc)); return true; } } return false; } /* OP0 CODE OP1 is a comparison. Examine the comparison and potentially OP1's defining statement to see if it ultimately has the form OP0 CODE (OP0 PLUS INTEGER_CST) If so, return TRUE indicating this is an overflow test and store into *NEW_CST an updated constant that can be used in a narrowed range test. These statements are left as-is in the IL to facilitate discovery of {ADD,SUB}_OVERFLOW sequences later in the optimizer pipeline. But the alternate range representation is often useful within VRP. */ bool overflow_comparison_p (tree_code code, tree name, tree val, tree *new_cst) { if (overflow_comparison_p_1 (code, name, val, false, new_cst)) return true; return overflow_comparison_p_1 (swap_tree_comparison (code), val, name, true, new_cst); } /* Searches the case label vector VEC for the index *IDX of the CASE_LABEL that includes the value VAL. The search is restricted to the range [START_IDX, n - 1] where n is the size of VEC. If there is a CASE_LABEL for VAL, its index is placed in IDX and true is returned. If there is no CASE_LABEL for VAL and there is one that is larger than VAL, it is placed in IDX and false is returned. If VAL is larger than any CASE_LABEL, n is placed on IDX and false is returned. */ bool find_case_label_index (gswitch *stmt, size_t start_idx, tree val, size_t *idx) { size_t n = gimple_switch_num_labels (stmt); size_t low, high; /* Find case label for minimum of the value range or the next one. At each iteration we are searching in [low, high - 1]. */ for (low = start_idx, high = n; high != low; ) { tree t; int cmp; /* Note that i != high, so we never ask for n. */ size_t i = (high + low) / 2; t = gimple_switch_label (stmt, i); /* Cache the result of comparing CASE_LOW and val. */ cmp = tree_int_cst_compare (CASE_LOW (t), val); if (cmp == 0) { /* Ranges cannot be empty. */ *idx = i; return true; } else if (cmp > 0) high = i; else { low = i + 1; if (CASE_HIGH (t) != NULL && tree_int_cst_compare (CASE_HIGH (t), val) >= 0) { *idx = i; return true; } } } *idx = high; return false; } /* Searches the case label vector VEC for the range of CASE_LABELs that is used for values between MIN and MAX. The first index is placed in MIN_IDX. The last index is placed in MAX_IDX. If the range of CASE_LABELs is empty then MAX_IDX < MIN_IDX. Returns true if the default label is not needed. */ bool find_case_label_range (gswitch *stmt, tree min, tree max, size_t *min_idx, size_t *max_idx) { size_t i, j; bool min_take_default = !find_case_label_index (stmt, 1, min, &i); bool max_take_default = !find_case_label_index (stmt, i, max, &j); if (i == j && min_take_default && max_take_default) { /* Only the default case label reached. Return an empty range. */ *min_idx = 1; *max_idx = 0; return false; } else { bool take_default = min_take_default || max_take_default; tree low, high; size_t k; if (max_take_default) j--; /* If the case label range is continuous, we do not need the default case label. Verify that. */ high = CASE_LOW (gimple_switch_label (stmt, i)); if (CASE_HIGH (gimple_switch_label (stmt, i))) high = CASE_HIGH (gimple_switch_label (stmt, i)); for (k = i + 1; k <= j; ++k) { low = CASE_LOW (gimple_switch_label (stmt, k)); if (!integer_onep (int_const_binop (MINUS_EXPR, low, high))) { take_default = true; break; } high = low; if (CASE_HIGH (gimple_switch_label (stmt, k))) high = CASE_HIGH (gimple_switch_label (stmt, k)); } *min_idx = i; *max_idx = j; return !take_default; } } /* Given a SWITCH_STMT, return the case label that encompasses the known possible values for the switch operand. RANGE_OF_OP is a range for the known values of the switch operand. */ tree find_case_label_range (gswitch *switch_stmt, const irange *range_of_op) { if (range_of_op->undefined_p () || range_of_op->varying_p ()) return NULL_TREE; size_t i, j; tree op = gimple_switch_index (switch_stmt); tree type = TREE_TYPE (op); unsigned prec = TYPE_PRECISION (type); signop sign = TYPE_SIGN (type); tree tmin = wide_int_to_tree (type, range_of_op->lower_bound ()); tree tmax = wide_int_to_tree (type, range_of_op->upper_bound ()); find_case_label_range (switch_stmt, tmin, tmax, &i, &j); if (i == j) { /* Look for exactly one label that encompasses the range of the operand. */ tree label = gimple_switch_label (switch_stmt, i); tree case_high = CASE_HIGH (label) ? CASE_HIGH (label) : CASE_LOW (label); wide_int wlow = wi::to_wide (CASE_LOW (label)); wide_int whigh = wi::to_wide (case_high); int_range_max label_range (type, wide_int::from (wlow, prec, sign), wide_int::from (whigh, prec, sign)); if (!types_compatible_p (label_range.type (), range_of_op->type ())) range_cast (label_range, range_of_op->type ()); label_range.intersect (*range_of_op); if (label_range == *range_of_op) return label; } else if (i > j) { /* If there are no labels at all, take the default. */ return gimple_switch_label (switch_stmt, 0); } else { /* Otherwise, there are various labels that can encompass the range of operand. In which case, see if the range of the operand is entirely *outside* the bounds of all the (non-default) case labels. If so, take the default. */ unsigned n = gimple_switch_num_labels (switch_stmt); tree min_label = gimple_switch_label (switch_stmt, 1); tree max_label = gimple_switch_label (switch_stmt, n - 1); tree case_high = CASE_HIGH (max_label); if (!case_high) case_high = CASE_LOW (max_label); int_range_max label_range (TREE_TYPE (CASE_LOW (min_label)), wi::to_wide (CASE_LOW (min_label)), wi::to_wide (case_high)); if (!types_compatible_p (label_range.type (), range_of_op->type ())) range_cast (label_range, range_of_op->type ()); label_range.intersect (*range_of_op); if (label_range.undefined_p ()) return gimple_switch_label (switch_stmt, 0); } return NULL_TREE; } struct case_info { tree expr; basic_block bb; }; // This is a ranger based folder which continues to use the dominator // walk to access the substitute and fold machinery. Ranges are calculated // on demand. class rvrp_folder : public substitute_and_fold_engine { public: rvrp_folder (gimple_ranger *r, bool all) : substitute_and_fold_engine (), m_unreachable (*r, all), m_simplifier (r, r->non_executable_edge_flag) { m_ranger = r; m_pta = new pointer_equiv_analyzer (m_ranger); m_last_bb_stmt = NULL; } ~rvrp_folder () { delete m_pta; } tree value_of_expr (tree name, gimple *s = NULL) override { // Shortcircuit subst_and_fold callbacks for abnormal ssa_names. if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) return NULL; tree ret = m_ranger->value_of_expr (name, s); if (!ret && supported_pointer_equiv_p (name)) ret = m_pta->get_equiv (name); return ret; } tree value_on_edge (edge e, tree name) override { // Shortcircuit subst_and_fold callbacks for abnormal ssa_names. if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) return NULL; tree ret = m_ranger->value_on_edge (e, name); if (!ret && supported_pointer_equiv_p (name)) ret = m_pta->get_equiv (name); return ret; } tree value_of_stmt (gimple *s, tree name = NULL) override { // Shortcircuit subst_and_fold callbacks for abnormal ssa_names. if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) return NULL; return m_ranger->value_of_stmt (s, name); } void pre_fold_bb (basic_block bb) override { m_pta->enter (bb); for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) m_ranger->register_inferred_ranges (gsi.phi ()); m_last_bb_stmt = last_nondebug_stmt (bb); } void post_fold_bb (basic_block bb) override { m_pta->leave (bb); } void pre_fold_stmt (gimple *stmt) override { m_pta->visit_stmt (stmt); // If this is the last stmt and there are inferred ranges, reparse the // block for transitive inferred ranges that occur earlier in the block. if (stmt == m_last_bb_stmt) { m_ranger->register_transitive_inferred_ranges (gimple_bb (stmt)); // Also check for builtin_unreachable calls. if (cfun->after_inlining && gimple_code (stmt) == GIMPLE_COND) m_unreachable.maybe_register (stmt); } } bool fold_stmt (gimple_stmt_iterator *gsi) override { bool ret = m_simplifier.simplify (gsi); if (!ret) ret = m_ranger->fold_stmt (gsi, follow_single_use_edges); m_ranger->register_inferred_ranges (gsi_stmt (*gsi)); return ret; } remove_unreachable m_unreachable; private: DISABLE_COPY_AND_ASSIGN (rvrp_folder); gimple_ranger *m_ranger; simplify_using_ranges m_simplifier; pointer_equiv_analyzer *m_pta; gimple *m_last_bb_stmt; }; /* Main entry point for a VRP pass using just ranger. This can be called from anywhere to perform a VRP pass, including from EVRP. */ unsigned int execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p, bool final_p) { loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); scev_initialize (); calculate_dominance_info (CDI_DOMINATORS); set_all_edges_as_executable (fun); gimple_ranger *ranger = enable_ranger (fun, false); rvrp_folder folder (ranger, final_p); phi_analysis_initialize (ranger->const_query ()); folder.substitute_and_fold (); // Remove tagged builtin-unreachable and maybe update globals. folder.m_unreachable.remove_and_update_globals (); if (dump_file && (dump_flags & TDF_DETAILS)) ranger->dump (dump_file); if ((warn_array_bounds || warn_strict_flex_arrays) && warn_array_bounds_p) { // Set all edges as executable, except those ranger says aren't. int non_exec_flag = ranger->non_executable_edge_flag; basic_block bb; FOR_ALL_BB_FN (bb, fun) { edge_iterator ei; edge e; FOR_EACH_EDGE (e, ei, bb->succs) if (e->flags & non_exec_flag) e->flags &= ~EDGE_EXECUTABLE; else e->flags |= EDGE_EXECUTABLE; } scev_reset (); array_bounds_checker array_checker (fun, ranger); array_checker.check (); } phi_analysis_finalize (); disable_ranger (fun); scev_finalize (); loop_optimizer_finalize (); return 0; } // Implement a Fast VRP folder. Not quite as effective but faster. class fvrp_folder : public substitute_and_fold_engine { public: fvrp_folder (dom_ranger *dr) : substitute_and_fold_engine (), m_simplifier (dr) { m_dom_ranger = dr; } ~fvrp_folder () { } tree value_of_expr (tree name, gimple *s = NULL) override { // Shortcircuit subst_and_fold callbacks for abnormal ssa_names. if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) return NULL; return m_dom_ranger->value_of_expr (name, s); } tree value_on_edge (edge e, tree name) override { // Shortcircuit subst_and_fold callbacks for abnormal ssa_names. if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) return NULL; return m_dom_ranger->value_on_edge (e, name); } tree value_of_stmt (gimple *s, tree name = NULL) override { // Shortcircuit subst_and_fold callbacks for abnormal ssa_names. if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) return NULL; return m_dom_ranger->value_of_stmt (s, name); } void pre_fold_bb (basic_block bb) override { m_dom_ranger->pre_bb (bb); // Now process the PHIs in advance. gphi_iterator psi = gsi_start_phis (bb); for ( ; !gsi_end_p (psi); gsi_next (&psi)) { tree name = gimple_range_ssa_p (PHI_RESULT (psi.phi ())); if (name) { Value_Range vr(TREE_TYPE (name)); m_dom_ranger->range_of_stmt (vr, psi.phi (), name); } } } void post_fold_bb (basic_block bb) override { m_dom_ranger->post_bb (bb); } void pre_fold_stmt (gimple *s) override { // Ensure range_of_stmt has been called. tree type = gimple_range_type (s); if (type) { Value_Range vr(type); m_dom_ranger->range_of_stmt (vr, s); } } bool fold_stmt (gimple_stmt_iterator *gsi) override { bool ret = m_simplifier.simplify (gsi); if (!ret) ret = ::fold_stmt (gsi, follow_single_use_edges); return ret; } private: DISABLE_COPY_AND_ASSIGN (fvrp_folder); simplify_using_ranges m_simplifier; dom_ranger *m_dom_ranger; }; // Main entry point for a FAST VRP pass using a dom ranger. unsigned int execute_fast_vrp (struct function *fun) { calculate_dominance_info (CDI_DOMINATORS); dom_ranger dr; fvrp_folder folder (&dr); gcc_checking_assert (!fun->x_range_query); fun->x_range_query = &dr; folder.substitute_and_fold (); fun->x_range_query = NULL; return 0; } namespace { const pass_data pass_data_vrp = { GIMPLE_PASS, /* type */ "vrp", /* name */ OPTGROUP_NONE, /* optinfo_flags */ TV_TREE_VRP, /* tv_id */ PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */ }; const pass_data pass_data_early_vrp = { GIMPLE_PASS, /* type */ "evrp", /* name */ OPTGROUP_NONE, /* optinfo_flags */ TV_TREE_EARLY_VRP, /* tv_id */ PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ), }; const pass_data pass_data_fast_vrp = { GIMPLE_PASS, /* type */ "fvrp", /* name */ OPTGROUP_NONE, /* optinfo_flags */ TV_TREE_FAST_VRP, /* tv_id */ PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ), }; class pass_vrp : public gimple_opt_pass { public: pass_vrp (gcc::context *ctxt, const pass_data &data_, bool warn_p) : gimple_opt_pass (data_, ctxt), data (data_), warn_array_bounds_p (warn_p), final_p (false) { } /* opt_pass methods: */ opt_pass * clone () final override { return new pass_vrp (m_ctxt, data, false); } void set_pass_param (unsigned int n, bool param) final override { gcc_assert (n == 0); final_p = param; } bool gate (function *) final override { return flag_tree_vrp != 0; } unsigned int execute (function *fun) final override { // Check for fast vrp. if (&data == &pass_data_fast_vrp) return execute_fast_vrp (fun); return execute_ranger_vrp (fun, warn_array_bounds_p, final_p); } private: const pass_data &data; bool warn_array_bounds_p; bool final_p; }; // class pass_vrp const pass_data pass_data_assumptions = { GIMPLE_PASS, /* type */ "assumptions", /* name */ OPTGROUP_NONE, /* optinfo_flags */ TV_TREE_ASSUMPTIONS, /* tv_id */ PROP_ssa, /* properties_required */ PROP_assumptions_done, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ 0, /* todo_flags_end */ }; class pass_assumptions : public gimple_opt_pass { public: pass_assumptions (gcc::context *ctxt) : gimple_opt_pass (pass_data_assumptions, ctxt) {} /* opt_pass methods: */ bool gate (function *fun) final override { return fun->assume_function; } unsigned int execute (function *) final override { assume_query query; if (dump_file) fprintf (dump_file, "Assumptions :\n--------------\n"); for (tree arg = DECL_ARGUMENTS (cfun->decl); arg; arg = DECL_CHAIN (arg)) { tree name = ssa_default_def (cfun, arg); if (!name || !gimple_range_ssa_p (name)) continue; tree type = TREE_TYPE (name); if (!Value_Range::supports_type_p (type)) continue; Value_Range assume_range (type); if (query.assume_range_p (assume_range, name)) { // Set the global range of NAME to anything calculated. set_range_info (name, assume_range); if (dump_file) { print_generic_expr (dump_file, name, TDF_SLIM); fprintf (dump_file, " -> "); assume_range.dump (dump_file); fputc ('\n', dump_file); } } } if (dump_file) { fputc ('\n', dump_file); gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); if (dump_flags & TDF_DETAILS) query.dump (dump_file); } return TODO_discard_function; } }; // class pass_assumptions } // anon namespace gimple_opt_pass * make_pass_vrp (gcc::context *ctxt) { return new pass_vrp (ctxt, pass_data_vrp, true); } gimple_opt_pass * make_pass_early_vrp (gcc::context *ctxt) { return new pass_vrp (ctxt, pass_data_early_vrp, false); } gimple_opt_pass * make_pass_fast_vrp (gcc::context *ctxt) { return new pass_vrp (ctxt, pass_data_fast_vrp, false); } gimple_opt_pass * make_pass_assumptions (gcc::context *ctx) { return new pass_assumptions (ctx); }