| /* Gimple range phi analysis. | |
| Copyright (C) 2023-2026 Free Software Foundation, Inc. | |
| Contributed by Andrew MacLeod <amacleod@redhat.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/>. */ | |
| #include "config.h" | |
| #include "system.h" | |
| #include "coretypes.h" | |
| #include "backend.h" | |
| #include "insn-codes.h" | |
| #include "tree.h" | |
| #include "gimple.h" | |
| #include "ssa.h" | |
| #include "gimple-pretty-print.h" | |
| #include "gimple-range.h" | |
| #include "gimple-range-cache.h" | |
| #include "value-range-storage.h" | |
| #include "tree-cfg.h" | |
| #include "target.h" | |
| #include "attribs.h" | |
| #include "gimple-iterator.h" | |
| #include "gimple-walk.h" | |
| #include "cfganal.h" | |
| // Invoke a phi analyzer. It will process all the current PHI groups | |
| // and export any ranges found to set_range_info. | |
| // When finished, it will simply dispose of itself. | |
| void | |
| phi_analysis (range_query &q) | |
| { | |
| phi_analyzer analyze (q); | |
| } | |
| // Initialize a phi_group from another group G. | |
| phi_group::phi_group (const phi_group &g) | |
| { | |
| m_group = g.m_group; | |
| m_modifier = g.m_modifier; | |
| m_modifier_op = g.m_modifier_op; | |
| m_vr = g.m_vr; | |
| } | |
| // Create a new phi_group with members BM, initial range INIT_RANGE, modifier | |
| // statement MOD on edge MOD_EDGE, and resolve values using query Q. Calculate | |
| // the range for the group if possible, otherwise set it to VARYING. | |
| phi_group::phi_group (bitmap bm, irange &init_range, gimple *mod, | |
| range_query *q) | |
| { | |
| // We don't expect a modifier and no initial value, so trap to have a look. | |
| // perhaps they are dead cycles and we can just used UNDEFINED. | |
| gcc_checking_assert (!init_range.undefined_p ()); | |
| gcc_checking_assert (!init_range.varying_p ()); | |
| m_modifier_name = NULL_TREE; | |
| m_modifier_op = is_modifier_p (mod, bm, &m_modifier_name); | |
| m_group = bm; | |
| m_vr = init_range; | |
| m_modifier = mod; | |
| // No modifier means the initial range is the full range. | |
| // Otherwise try to calculate a range. | |
| if (!m_modifier_op || calculate_using_modifier (q)) | |
| return; | |
| // Couldn't calculate a range, set to varying. | |
| m_vr.set_varying (init_range.type ()); | |
| } | |
| // Return 0 if S is not a modifier statement for group members BM. | |
| // If it could be a modifier, return which operand position (1 or 2) | |
| // the phi member occurs in. | |
| unsigned | |
| phi_group::is_modifier_p (gimple *s, const bitmap bm, tree *op) | |
| { | |
| if (!s) | |
| return 0; | |
| gimple_range_op_handler handler (s); | |
| if (handler) | |
| { | |
| tree op1 = gimple_range_ssa_p (handler.operand1 ()); | |
| tree op2 = gimple_range_ssa_p (handler.operand2 ()); | |
| // Also disallow modifiers that have 2 ssa-names. | |
| if (op1 && !op2 && bitmap_bit_p (bm, SSA_NAME_VERSION (op1))) | |
| { | |
| if (op) | |
| *op = op1; | |
| return 1; | |
| } | |
| else if (op2 && !op1 && bitmap_bit_p (bm, SSA_NAME_VERSION (op2))) | |
| { | |
| if (op) | |
| *op = op2; | |
| return 2; | |
| } | |
| } | |
| return 0; | |
| } | |
| // Calulcate the range of the phi group using range_query Q. | |
| bool | |
| phi_group::calculate_using_modifier (range_query *q) | |
| { | |
| // Look at the modifier for any relation | |
| relation_trio trio = fold_relations (m_modifier, q); | |
| relation_kind k = VREL_VARYING; | |
| if (m_modifier_op == 1) | |
| k = trio.lhs_op1 (); | |
| else if (m_modifier_op == 2) | |
| k = trio.lhs_op2 (); | |
| else | |
| return false; | |
| // If we can resolve the range using relations, use that range. | |
| if (refine_using_relation (k)) | |
| return true; | |
| // Examine modifier and run iteration evaluations to see if it convergences. | |
| // The constructor initialized m_vr to the initial value already. | |
| int_range_max nv; | |
| int_range_max iter_value = m_vr; | |
| int_range_max iter_reach; | |
| // Determine the maximum range of the var reaching here. The back edge | |
| // usually has a guard restircting the range. Default to VARYING. | |
| if (!m_modifier_name | |
| || !q->range_of_expr (iter_reach, m_modifier_name, m_modifier)) | |
| iter_reach.set_varying (m_vr.type ()); | |
| // Iterative evaluation can be expensive, so heuristically : | |
| // - PLUS and MINUS are 98% of the cases, and usually handled well enough | |
| // by loop analysis, The exception is if the reaching range has multiple | |
| // subranges, those are often worth examining. | |
| // - All other operations (2%) are worth checking. | |
| bool do_iterative = false; | |
| if (gimple_code (m_modifier) == GIMPLE_ASSIGN) | |
| switch (gimple_assign_rhs_code (m_modifier)) | |
| { | |
| case PLUS_EXPR: | |
| case MINUS_EXPR: | |
| if (iter_reach.num_pairs () > 1) | |
| do_iterative = true; | |
| break; | |
| default: | |
| do_iterative = true; | |
| } | |
| // Limit iterations to 1 more than the number of bits. | |
| unsigned num_iter; | |
| if (do_iterative) | |
| num_iter = MIN (TYPE_PRECISION (m_vr.type ()), MAX_FIXED_MODE_SIZE) + 1; | |
| else | |
| num_iter = 0; | |
| for (unsigned x = 0; x < num_iter; x++) | |
| { | |
| if (!fold_range (nv, m_modifier, iter_value, q)) | |
| break; | |
| // Ensure nothing calculated is outside outside the reaching range. | |
| nv.intersect (iter_reach); | |
| // If union does nothing, then we have convergence. | |
| if (!iter_value.union_ (nv)) | |
| { | |
| if (iter_value.varying_p ()) | |
| break; | |
| // The last iteration Will also reach the PHI node, add it in. | |
| fold_range (nv, m_modifier, iter_value, q); | |
| iter_value.union_ (nv); | |
| m_vr = iter_value; | |
| return true; | |
| } | |
| } | |
| // Never converged, so bail for now. we could examine the pattern | |
| // from m_initial to m_vr as an extension Especially if we had a way | |
| // to project the actual number of iterations (SCEV?) | |
| // | |
| // We can also try to identify "parallel" phis to get loop counts and | |
| // determine the number of iterations of these parallel PHIs. | |
| return false; | |
| } | |
| // IF the modifier statement has a relation K between the modifier and the | |
| // PHI member in it, we can project a range based on that. | |
| // ie, a_2 = PHI <0, a_3> and a_3 = a_2 + 1 | |
| // if the relation a_3 > a_2 is present, the know the range is [0, +INF] | |
| // m_vr contains the initial value for the PHI range. | |
| bool | |
| phi_group::refine_using_relation (relation_kind k) | |
| { | |
| if (k == VREL_VARYING) | |
| return false; | |
| tree type = m_vr.type (); | |
| // If the type wraps, then relations dont tell us much. | |
| if (TYPE_OVERFLOW_WRAPS (type)) | |
| return false; | |
| int_range<2> type_range; | |
| type_range.set_varying (type); | |
| switch (k) | |
| { | |
| case VREL_LT: | |
| case VREL_LE: | |
| { | |
| // Value always decreases. | |
| m_vr.set (type, type_range.lower_bound (), m_vr.upper_bound ()); | |
| return true; | |
| } | |
| case VREL_GT: | |
| case VREL_GE: | |
| { | |
| // Value always increases. | |
| m_vr.set (type, m_vr.lower_bound (), type_range.upper_bound ()); | |
| return true; | |
| } | |
| // If its always equal, then its simply the initial value. | |
| // which is what m_vr has already been set to. | |
| case VREL_EQ: | |
| return true; | |
| default: | |
| break; | |
| } | |
| return false; | |
| } | |
| // Dump the information for a phi group to file F. | |
| void | |
| phi_group::dump (FILE *f) | |
| { | |
| unsigned i; | |
| bitmap_iterator bi; | |
| fprintf (f, "PHI GROUP < "); | |
| EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi) | |
| { | |
| print_generic_expr (f, ssa_name (i), TDF_SLIM); | |
| fputc (' ',f); | |
| } | |
| fprintf (f, "> : range : "); | |
| m_vr.dump (f); | |
| fprintf (f, "\n Modifier : "); | |
| if (m_modifier) | |
| print_gimple_stmt (f, m_modifier, 0, TDF_SLIM); | |
| else | |
| fprintf (f, "NONE\n"); | |
| } | |
| // ------------------------------------------------------------------------- | |
| // Construct a phi analyzer which uses range_query G to pick up values. | |
| phi_analyzer::phi_analyzer (range_query &query) : m_phi_groups (vNULL) | |
| { | |
| m_work.create (0); | |
| m_work.safe_grow (20); | |
| m_tab.create (0); | |
| m_tab.safe_grow_cleared (num_ssa_names + 10); | |
| bitmap_obstack_initialize (&m_bitmaps); | |
| m_simple = BITMAP_ALLOC (&m_bitmaps); | |
| m_current = BITMAP_ALLOC (&m_bitmaps); | |
| basic_block bb; | |
| gphi_iterator gphi; | |
| if (dump_file && (dump_flags & TDF_DETAILS)) | |
| fprintf (dump_file, "PHI ANALYZER : processing PHIS.\n"); | |
| // Process each PHI node to see if it belongs in a group with others. | |
| // Then calculate an initial value for the group. | |
| FOR_EACH_BB_FN (bb, cfun) | |
| { | |
| for (gphi = gsi_start_nonvirtual_phis (bb); | |
| !gsi_end_p (gphi); | |
| gsi_next_nonvirtual_phi (&gphi)) | |
| process_phi (gphi.phi (), query); | |
| } | |
| if (dump_file && (dump_flags & TDF_DETAILS)) | |
| fprintf (dump_file, "PHI ANALYZER : Finished processing PHIS.\n"); | |
| } | |
| // Destruct a PHI analyzer. | |
| phi_analyzer::~phi_analyzer () | |
| { | |
| bitmap_obstack_release (&m_bitmaps); | |
| m_tab.release (); | |
| m_work.release (); | |
| for (auto grp : m_phi_groups) | |
| delete grp; | |
| m_phi_groups.release (); | |
| } | |
| // Return the group, if any, that NAME is part of. Do no analysis. | |
| phi_group * | |
| phi_analyzer::group (tree name) const | |
| { | |
| gcc_checking_assert (TREE_CODE (name) == SSA_NAME); | |
| if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name))) | |
| return NULL; | |
| unsigned v = SSA_NAME_VERSION (name); | |
| if (v >= m_tab.length ()) | |
| return NULL; | |
| return m_tab[v]; | |
| } | |
| // Return the group NAME is associated with, if any. If name has not been | |
| // procvessed yet, do the analysis to determine if it is part of a group | |
| // and return that. | |
| phi_group * | |
| phi_analyzer::operator[] (tree name) | |
| { | |
| gcc_checking_assert (TREE_CODE (name) == SSA_NAME); | |
| // Initial support for irange only. | |
| if (!irange::supports_p (TREE_TYPE (name))) | |
| return NULL; | |
| if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name))) | |
| return NULL; | |
| unsigned v = SSA_NAME_VERSION (name); | |
| if (v >= m_tab.length ()) | |
| return NULL; | |
| return m_tab[v]; | |
| } | |
| // Process phi node PHI to see if it is part of a group. Use QUERY | |
| // to determine ranges. | |
| void | |
| phi_analyzer::process_phi (gphi *phi, range_query &query) | |
| { | |
| tree def = gimple_phi_result (phi); | |
| unsigned v = SSA_NAME_VERSION (def); | |
| gcc_checking_assert (v < m_tab.length ()); | |
| // If this is already on a group, or identified as a simple phi, or | |
| // not an irange, do not process it. | |
| if (m_tab[v] || bitmap_bit_p (m_simple, v) | |
| || !irange::supports_p (TREE_TYPE (def))) | |
| return; | |
| bool cycle_p = true; | |
| // Start with the LHS of the PHI in the worklist. | |
| unsigned x; | |
| m_work.truncate (0); | |
| m_work.safe_push (def); | |
| unsigned phi_count = 1; | |
| bitmap_clear (m_current); | |
| // We can only have 2 externals: an initial value and a modifier. | |
| // Any more than that and this fails to be a group. | |
| unsigned m_num_extern = 0; | |
| tree m_external[2]; | |
| edge m_ext_edge[2]; | |
| int_range_max init_range; | |
| init_range.set_undefined (); | |
| while (m_work.length () > 0) | |
| { | |
| tree phi_def = m_work.pop (); | |
| gphi *phi_stmt = as_a<gphi *> (SSA_NAME_DEF_STMT (phi_def)); | |
| // if the phi is already in a different cycle, we don't try to merge. | |
| if (group (phi_def)) | |
| { | |
| cycle_p = false; | |
| break; | |
| } | |
| // If the PHI is already processed, no need to scan it again. | |
| if (!bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def))) | |
| continue; | |
| // Process the args. | |
| for (x = 0; x < gimple_phi_num_args (phi_stmt); x++) | |
| { | |
| tree arg = gimple_phi_arg_def (phi_stmt, x); | |
| if (arg == phi_def) | |
| continue; | |
| enum tree_code code = TREE_CODE (arg); | |
| if (code == SSA_NAME) | |
| { | |
| unsigned v = SSA_NAME_VERSION (arg); | |
| // Already a member of this potential group. | |
| if (bitmap_bit_p (m_current, v)) | |
| continue; | |
| // Part of a different group ends cycle possibility. | |
| if (group (arg) || bitmap_bit_p (m_simple, v)) | |
| { | |
| cycle_p = false; | |
| break; | |
| } | |
| // Check if its a PHI to examine. | |
| gimple *arg_stmt = SSA_NAME_DEF_STMT (arg); | |
| if (arg_stmt && is_a<gphi *> (arg_stmt)) | |
| { | |
| phi_count++; | |
| m_work.safe_push (arg); | |
| continue; | |
| } | |
| // More than 2 outside names is too complicated. | |
| if (m_num_extern >= 2) | |
| { | |
| cycle_p = false; | |
| break; | |
| } | |
| m_external[m_num_extern] = arg; | |
| m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x); | |
| } | |
| else if (code == INTEGER_CST) | |
| { | |
| // Constants are just added to the initialization value. | |
| int_range<1> val (TREE_TYPE (arg), wi::to_wide (arg), | |
| wi::to_wide (arg)); | |
| init_range.union_ (val); | |
| } | |
| else | |
| { | |
| // Everything else terminates the cycle. | |
| cycle_p = false; | |
| break; | |
| } | |
| } | |
| } | |
| if (phi_count < 1) | |
| return; | |
| gcc_checking_assert (!bitmap_empty_p (m_current)); | |
| phi_group *g = NULL; | |
| gimple *mod = NULL; | |
| bool valid = false; | |
| signed init_idx = -1; | |
| int_range_max init_sym; | |
| if (cycle_p) | |
| { | |
| valid = true; | |
| // At this point all the PHIs have been added to the bitmap. | |
| // the external list needs to be checked for initial values and modifiers. | |
| for (x = 0; x < m_num_extern; x++) | |
| { | |
| tree name = m_external[x]; | |
| if (TREE_CODE (name) == SSA_NAME | |
| && phi_group::is_modifier_p (SSA_NAME_DEF_STMT (name), m_current)) | |
| { | |
| // Can't have multiple modifiers. | |
| if (mod) | |
| valid = false; | |
| mod = SSA_NAME_DEF_STMT (name); | |
| continue; | |
| } | |
| // Can't have 2 initializers either. | |
| if (init_idx != -1) | |
| valid = false; | |
| init_idx = x; | |
| } | |
| // If there is an symbolic initializer as well, include it here. | |
| if (valid && init_idx != -1) | |
| { | |
| if (query.range_on_edge (init_sym, m_ext_edge[init_idx], | |
| m_external[init_idx])) | |
| init_range.union_ (init_sym); | |
| else | |
| valid = false; | |
| } | |
| } | |
| // If there are less than 2 names, . This PHI may be included | |
| // by another PHI, making it simple or a group of one will prevent a larger | |
| // group from being formed. | |
| // The exception will be pattern matching: | |
| // a_1 = a_2 OP X | |
| // a_2 = PHI <const, a_1> | |
| if (phi_count == 1 | |
| && (m_num_extern != 1 || init_range.undefined_p () || !mod)) | |
| valid = false; | |
| if (valid && !init_range.varying_p () && !init_range.undefined_p ()) | |
| { | |
| // Try to create a group based on m_current. If a result comes back | |
| // with a range that isn't varying, create the group. | |
| phi_group cyc (m_current, init_range, mod, &query); | |
| if (!cyc.range ().varying_p ()) | |
| { | |
| g = new phi_group (cyc); | |
| m_phi_groups.safe_push (g); | |
| if (dump_file && (dump_flags & TDF_DETAILS)) | |
| { | |
| fprintf (dump_file, "PHI ANALYZER : New "); | |
| g->dump (dump_file); | |
| fprintf (dump_file," Initial range was "); | |
| init_range.dump (dump_file); | |
| if (init_idx != -1) | |
| { | |
| fprintf (dump_file, " including symbolic "); | |
| print_generic_expr (dump_file, m_external[init_idx], | |
| TDF_SLIM); | |
| fprintf (dump_file, " on edge %d->%d with range ", | |
| m_ext_edge[init_idx]->src->index, | |
| m_ext_edge[init_idx]->dest->index); | |
| init_sym.dump (dump_file); | |
| } | |
| fputc ('\n',dump_file); | |
| } | |
| } | |
| } | |
| // If this doesn't form a group, all members are instead simple phis. | |
| if (!g) | |
| { | |
| bitmap_ior_into (m_simple, m_current); | |
| return; | |
| } | |
| // Now set all entries in the group to this record. | |
| unsigned i; | |
| bitmap_iterator bi; | |
| EXECUTE_IF_SET_IN_BITMAP (m_current, 0, i, bi) | |
| { | |
| // Can't be in more than one group. | |
| gcc_checking_assert (m_tab[i] == NULL); | |
| m_tab[i] = g; | |
| // Set the new range in the range query. | |
| query.update_range_info (ssa_name (i), g->range ()); | |
| } | |
| // Allocate a new bitmap for the next time as the original one is now part | |
| // of the new phi group. | |
| m_current = BITMAP_ALLOC (&m_bitmaps); | |
| } | |
| void | |
| phi_analyzer::dump (FILE *f) | |
| { | |
| bool header = false; | |
| bitmap_clear (m_current); | |
| for (unsigned x = 0; x < m_tab.length (); x++) | |
| { | |
| if (bitmap_bit_p (m_simple, x)) | |
| continue; | |
| if (bitmap_bit_p (m_current, x)) | |
| continue; | |
| if (m_tab[x] == NULL) | |
| continue; | |
| phi_group *g = m_tab[x]; | |
| bitmap_ior_into (m_current, g->group ()); | |
| if (!header) | |
| { | |
| header = true; | |
| fprintf (f, "\nPHI GROUPS:\n"); | |
| } | |
| g->dump (f); | |
| } | |
| } |