gcc/gimple-range-phi.cc

   1 /* Gimple range phi analysis.
   2    Copyright (C) 2023 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod <amacleod@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "insn-codes.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "ssa.h"
  29 #include "gimple-pretty-print.h"
  30 #include "gimple-range.h"
  31 #include "gimple-range-cache.h"
  32 #include "value-range-storage.h"
  33 #include "tree-cfg.h"
  34 #include "target.h"
  35 #include "attribs.h"
  36 #include "gimple-iterator.h"
  37 #include "gimple-walk.h"
  38 #include "cfganal.h"
  39
  40 // There can be only one running at a time.
  41 static phi_analyzer *phi_analysis_object = NULL;
  42
  43 // Initialize a PHI analyzer with range query Q.
  44
  45 void
  46 phi_analysis_initialize (range_query &q)
  47 {
  48   gcc_checking_assert (!phi_analysis_object);
  49   phi_analysis_object = new phi_analyzer (q);
  50 }
  51
  52 // Terminate the current PHI analyzer.  if F is non-null, dump the tables
  53
  54 void
  55 phi_analysis_finalize ()
  56 {
  57   gcc_checking_assert (phi_analysis_object);
  58   delete phi_analysis_object;
  59   phi_analysis_object = NULL;
  60 }
  61
  62 // Return TRUE is there is a PHI analyzer operating.
  63 bool
  64 phi_analysis_available_p ()
  65 {
  66   return phi_analysis_object != NULL;
  67 }
  68
  69 // Return the phi analyzer object.
  70
  71 phi_analyzer &phi_analysis ()
  72 {
  73   gcc_checking_assert (phi_analysis_object);
  74   return *phi_analysis_object;
  75 }
  76
  77 // Initialize a phi_group from another group G.
  78
  79 phi_group::phi_group (const phi_group &g)
  80 {
  81   m_group = g.m_group;
  82   m_initial_value = g.m_initial_value;
  83   m_initial_edge = g.m_initial_edge;
  84   m_modifier = g.m_modifier;
  85   m_modifier_op = g.m_modifier_op;
  86   m_vr = g.m_vr;
  87 }
  88
  89 // Create a new phi_group with members BM, initialvalue INIT_VAL, modifier
  90 // statement MOD, and resolve values using query Q.
  91 // Calculate the range for the gropup if possible, otherwise set it to
  92 // VARYING.
  93
  94 phi_group::phi_group (bitmap bm, tree init_val, edge e, gimple *mod,
  95                       range_query *q)
  96 {
  97   // we dont expect a modifer and no inital value, so trap to have a look.
  98   // perhaps they are dead cycles and we can just used UNDEFINED.
  99   gcc_checking_assert (init_val);
 100
 101   m_modifier_op = is_modifier_p (mod, bm);
 102   m_group = bm;
 103   m_initial_value = init_val;
 104   m_initial_edge = e;
 105   m_modifier = mod;
 106   if (q->range_on_edge (m_vr, m_initial_edge, m_initial_value))
 107     {
 108       // No modifier means the initial range is the full range.
 109       // Otherwise try to calculate a range.
 110       if (!m_modifier_op || calculate_using_modifier (q))
 111         return;
 112     }
 113   // Couldn't calculate a range, set to varying.
 114   m_vr.set_varying (TREE_TYPE (init_val));
 115 }
 116
 117 // Return 0 if S is not a modifier statment for group members BM.
 118 // If it could be a modifier, return which operand position (1 or 2)
 119 // the phi member occurs in.
 120 unsigned
 121 phi_group::is_modifier_p (gimple *s, const bitmap bm)
 122 {
 123   if (!s)
 124     return 0;
 125   gimple_range_op_handler handler (s);
 126   if (handler)
 127     {
 128       tree op1 = gimple_range_ssa_p (handler.operand1 ());
 129       tree op2 = gimple_range_ssa_p (handler.operand2 ());
 130       // Also disallow modifiers that have 2 ssa-names.
 131       if (op1 && !op2 && bitmap_bit_p (bm, SSA_NAME_VERSION (op1)))
 132         return 1;
 133       else if (op2 && !op1 && bitmap_bit_p (bm, SSA_NAME_VERSION (op2)))
 134         return 2;
 135     }
 136   return 0;
 137 }
 138
 139 // Calulcate the range of the phi group using range_query Q.
 140
 141 bool
 142 phi_group::calculate_using_modifier (range_query *q)
 143 {
 144   // Look at the modifier for any relation
 145   relation_trio trio = fold_relations (m_modifier, q);
 146   relation_kind k = VREL_VARYING;
 147   if (m_modifier_op == 1)
 148     k = trio.lhs_op1 ();
 149   else if (m_modifier_op == 2)
 150     k = trio.lhs_op2 ();
 151   else
 152     return false;
 153
 154   // If we can resolve the range using relations, use that range.
 155   if (refine_using_relation (k, q))
 156     return true;
 157
 158  // If the initial value is undefined, do not calculate a range.
 159   if (m_vr.undefined_p ())
 160     return false;
 161
 162   // Examine modifier and run X iterations to see if it convergences.
 163   // The constructor initilaized m_vr to the initial value already.
 164   int_range_max nv;
 165   for (unsigned x = 0; x< 10; x++)
 166     {
 167       if (!fold_range (nv, m_modifier, m_vr, q))
 168         return false;
 169       // If they are equal, then we have convergence.
 170       if (nv == m_vr)
 171         return true;
 172       // Update range and try again.
 173       m_vr.union_ (nv);
 174     }
 175   // Never converged, so bail for now. we could examine the pattern
 176   // from m_initial to m_vr as an extension  Especially if we had a way
 177   // to project the actual number of iterations (SCEV?)
 178   //
 179   //  We can also try to identify "parallel" phis to get loop counts and
 180   //  determine the number of iterations of these parallel PHIs.
 181   //
 182   return false;
 183 }
 184
 185
 186 // IF the modifier statement has a relation K between the modifier and the
 187 // PHI member in it, we can project a range based on that.
 188 // Use range_query Q to resolve values.
 189 // ie,  a_2 = PHI <0, a_3>   and a_3 = a_2 + 1
 190 // if the relation a_3 > a_2 is present, the know the range is [0, +INF]
 191
 192 bool
 193 phi_group::refine_using_relation (relation_kind k, range_query *q)
 194 {
 195   if (k == VREL_VARYING)
 196     return false;
 197   tree type = TREE_TYPE (m_initial_value);
 198   // If the type wraps, then relations dont tell us much.
 199   if (TYPE_OVERFLOW_WRAPS (type))
 200     return false;
 201
 202   switch (k)
 203     {
 204     case VREL_LT:
 205     case VREL_LE:
 206       {
 207         // Value always decreases.
 208         int_range<2> lb;
 209         int_range<2> ub;
 210         if (!q->range_on_edge (ub, m_initial_edge, m_initial_value))
 211           break;
 212         if (ub.undefined_p ())
 213           return false;
 214         lb.set_varying (type);
 215         m_vr.set (type, lb.lower_bound (), ub.upper_bound ());
 216         return true;
 217       }
 218
 219     case VREL_GT:
 220     case VREL_GE:
 221       {
 222         // Value always increases.
 223         int_range<2> lb;
 224         int_range<2> ub;
 225         if (!q->range_on_edge (lb, m_initial_edge, m_initial_value))
 226           break;
 227         if (lb.undefined_p ())
 228           return false;
 229         ub.set_varying (type);
 230         m_vr.set (type, lb.lower_bound (), ub.upper_bound ());
 231         return true;
 232       }
 233
 234       // If its always equal, then its simply the initial value.
 235       // which is what m_vr has already been set to.
 236     case VREL_EQ:
 237       return true;
 238
 239     default:
 240       break;
 241     }
 242
 243   return false;
 244 }
 245
 246 // Dump the information for a phi group to file F.
 247
 248 void
 249 phi_group::dump (FILE *f)
 250 {
 251   unsigned i;
 252   bitmap_iterator bi;
 253   fprintf (f, "PHI GROUP <");
 254
 255   EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi)
 256     {
 257       print_generic_expr (f, ssa_name (i), TDF_SLIM);
 258       fputc (' ',f);
 259     }
 260
 261   fprintf (f, ">\n - Initial value : ");
 262   if (m_initial_value)
 263     {
 264       if (TREE_CODE (m_initial_value) == SSA_NAME)
 265         print_gimple_stmt (f, SSA_NAME_DEF_STMT (m_initial_value), 0, TDF_SLIM);
 266       else
 267         print_generic_expr (f, m_initial_value, TDF_SLIM);
 268       fprintf (f, " on edge %d->%d", m_initial_edge->src->index,
 269                m_initial_edge->dest->index);
 270     }
 271   else
 272     fprintf (f, "NONE");
 273   fprintf (f, "\n - Modifier : ");
 274   if (m_modifier)
 275     print_gimple_stmt (f, m_modifier, 0, TDF_SLIM);
 276   else
 277     fprintf (f, "NONE\n");
 278   fprintf (f, " - Range : ");
 279   m_vr.dump (f);
 280   fputc ('\n', f);
 281 }
 282
 283 // -------------------------------------------------------------------------
 284
 285 // Construct a phi analyzer which uses range_query G to pick up values.
 286
 287 phi_analyzer::phi_analyzer (range_query &g) : m_global (g)
 288 {
 289   m_work.create (0);
 290   m_work.safe_grow (20);
 291
 292   m_tab.create (0);
 293 //   m_tab.safe_grow_cleared (num_ssa_names + 100);
 294   bitmap_obstack_initialize (&m_bitmaps);
 295   m_simple = BITMAP_ALLOC (&m_bitmaps);
 296   m_current = BITMAP_ALLOC (&m_bitmaps);
 297 }
 298
 299 // Destruct a PHI analyzer.
 300
 301 phi_analyzer::~phi_analyzer ()
 302 {
 303   bitmap_obstack_release (&m_bitmaps);
 304   m_tab.release ();
 305   m_work.release ();
 306 }
 307
 308 //  Return the group, if any, that NAME is part of.  Do no analysis.
 309
 310 phi_group *
 311 phi_analyzer::group (tree name) const
 312 {
 313   gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
 314   if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
 315     return NULL;
 316   unsigned v = SSA_NAME_VERSION (name);
 317   if (v >= m_tab.length ())
 318     return NULL;
 319   return m_tab[v];
 320 }
 321
 322 // Return the group NAME is associated with, if any.  If name has not been
 323 // procvessed yet, do the analysis to determine if it is part of a group
 324 // and return that.
 325
 326 phi_group *
 327 phi_analyzer::operator[] (tree name)
 328 {
 329   gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
 330
 331   //  Initial support for irange only.
 332   if (!irange::supports_p (TREE_TYPE (name)))
 333     return NULL;
 334   if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
 335     return NULL;
 336
 337   unsigned v = SSA_NAME_VERSION (name);
 338   // Already been processed and not part of a group.
 339   if (bitmap_bit_p (m_simple, v))
 340     return NULL;
 341
 342   if (v >= m_tab.length () || !m_tab[v])
 343     {
 344       process_phi (as_a<gphi *> (SSA_NAME_DEF_STMT (name)));
 345       if (bitmap_bit_p (m_simple, v))
 346         return  NULL;
 347       // If m_simple bit isn't set, then process_phi allocated the table
 348       // and should have a group.
 349       gcc_checking_assert (v < m_tab.length ());
 350     }
 351   return m_tab[v];
 352 }
 353
 354 // Process phi node PHI to see if it it part of a group.
 355
 356 void
 357 phi_analyzer::process_phi (gphi *phi)
 358 {
 359   gcc_checking_assert (!group (gimple_phi_result (phi)));
 360   bool cycle_p = true;
 361
 362   // Start with the LHS of the PHI in the worklist.
 363   unsigned x;
 364   m_work.truncate (0);
 365   m_work.safe_push (gimple_phi_result (phi));
 366   bitmap_clear (m_current);
 367
 368   // We can only have 2 externals: an initial value and a modifier.
 369   // Any more than that and this fails to be a group.
 370   unsigned m_num_extern = 0;
 371   tree m_external[2];
 372   edge m_ext_edge[2];
 373
 374   while (m_work.length () > 0)
 375     {
 376       tree phi_def = m_work.pop ();
 377       gphi *phi_stmt = as_a<gphi *> (SSA_NAME_DEF_STMT (phi_def));
 378       // if the phi is already in a cycle, its a complex situation, so revert
 379       // to simple.
 380       if (group (phi_def))
 381         {
 382           cycle_p = false;
 383           continue;
 384         }
 385       bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def));
 386       // Process the args.
 387       for (x = 0; x < gimple_phi_num_args (phi_stmt); x++)
 388         {
 389           tree arg = gimple_phi_arg_def (phi_stmt, x);
 390           if (arg == phi_def)
 391             continue;
 392           enum tree_code code = TREE_CODE (arg);
 393           if (code == SSA_NAME)
 394             {
 395               unsigned v = SSA_NAME_VERSION (arg);
 396               // Already a member of this potential group.
 397               if (bitmap_bit_p (m_current, v))
 398                 continue;
 399               // Part of a different group ends cycle possibility.
 400               if (group (arg) || bitmap_bit_p (m_simple, v))
 401                 {
 402                   cycle_p = false;
 403                   break;
 404                 }
 405               // Check if its a PHI to examine.
 406               // *FIX* Will miss initial values that originate from a PHI.
 407               gimple *arg_stmt = SSA_NAME_DEF_STMT (arg);
 408               if (arg_stmt && is_a<gphi *> (arg_stmt))
 409                 {
 410                   m_work.safe_push (arg);
 411                   continue;
 412                 }
 413             }
 414           // Other non-ssa names that arent constants are not understood
 415           // and terminate analysis.
 416           else if (code != INTEGER_CST && code != REAL_CST)
 417             {
 418               cycle_p = false;
 419               continue;
 420             }
 421           // More than 2 outside names/CONST is too complicated.
 422           if (m_num_extern >= 2)
 423             {
 424               cycle_p = false;
 425               break;
 426             }
 427
 428           m_external[m_num_extern] = arg;
 429           m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x);
 430         }
 431     }
 432
 433   // If there are no names in the group, we're done.
 434   if (bitmap_empty_p (m_current))
 435     return;
 436
 437   phi_group *g = NULL;
 438   if (cycle_p)
 439     {
 440       bool valid = true;
 441       gimple *mod = NULL;
 442       signed init_idx = -1;
 443       // At this point all the PHIs have been added to the bitmap.
 444       // the external list needs to be checked for initial values and modifiers.
 445       for (x = 0; x < m_num_extern; x++)
 446         {
 447           tree name = m_external[x];
 448           if (TREE_CODE (name) == SSA_NAME
 449               && phi_group::is_modifier_p (SSA_NAME_DEF_STMT (name), m_current))
 450             {
 451               // Can't have multiple modifiers.
 452               if (mod)
 453                 valid = false;
 454               mod = SSA_NAME_DEF_STMT (name);
 455               continue;
 456             }
 457           // Can't have 2 initializers either.
 458           if (init_idx != -1)
 459             valid = false;
 460           init_idx = x;
 461         }
 462       if (valid)
 463         {
 464           // Try to create a group based on m_current. If a result comes back
 465           // with a range that isn't varying, create the group.
 466           phi_group cyc (m_current, m_external[init_idx],
 467                          m_ext_edge[init_idx], mod, &m_global);
 468           if (!cyc.range ().varying_p ())
 469             g = new phi_group (cyc);
 470         }
 471     }
 472   // If this dpoesn;t form a group, all members are instead simple phis.
 473   if (!g)
 474     {
 475       bitmap_ior_into (m_simple, m_current);
 476       return;
 477     }
 478
 479   if (num_ssa_names >= m_tab.length ())
 480     m_tab.safe_grow_cleared (num_ssa_names + 100);
 481
 482   // Now set all entries in the group to this record.
 483   unsigned i;
 484   bitmap_iterator bi;
 485   EXECUTE_IF_SET_IN_BITMAP (m_current, 0, i, bi)
 486     {
 487       // Can't be in more than one group.
 488       gcc_checking_assert (m_tab[i] == NULL);
 489       m_tab[i] = g;
 490     }
 491   // Allocate a new bitmap for the next time as the original one is now part
 492   // of the new phi group.
 493   m_current = BITMAP_ALLOC (&m_bitmaps);
 494 }
 495
 496 void
 497 phi_analyzer::dump (FILE *f)
 498 {
 499   bool header = false;
 500   bitmap_clear (m_current);
 501   for (unsigned x = 0; x < m_tab.length (); x++)
 502     {
 503       if (bitmap_bit_p (m_simple, x))
 504         continue;
 505       if (bitmap_bit_p (m_current, x))
 506         continue;
 507       if (m_tab[x] == NULL)
 508         continue;
 509       phi_group *g = m_tab[x];
 510       bitmap_ior_into (m_current, g->group ());
 511       if (!header)
 512         {
 513           header = true;
 514           fprintf (dump_file, "\nPHI GROUPS:\n");
 515         }
 516       g->dump (f);
 517     }
 518 }