gcc/gimple-range-phi.h

   1 /* Header file for 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 it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15  for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #ifndef GCC_SSA_RANGE_PHI_H
  22 #define GCC_SSA_RANGE_PHI_H
  23
  24 // -------------------------------------------------------------------------
  25
  26 // A PHI_GROUP consists of a set of SSA_NAMES which are all PHI_DEFS, and
  27 // their arguemnts contain nothing but other PHI defintions, with at most
  28 // 2 exceptions:
  29 //  1 - An initial value.  This is either a constant, or another non-phi name
  30 //      with a single incoming edge to the cycle group
  31 //  2 - A modifier statement which adjusts the value.  ie, name2 = phi_name + 1
  32 //  The initial range is used to create one bound and the modifier is examined
  33 //  to determine the other bound.
  34 //  All members of the PHI cycle will be given the same range.
  35 //
  36 // For example, given the follwoing sequences:
  37 // qa_20 = qa_10 + 1;
  38 // qa_9 = PHI <qa_10(3), qa_20(4)>
  39 // qa_10 = PHI <0(2), qa_9(5)>
  40 //
  41 // We can determine the following group:
  42 //
  43 // PHI cycle members qa_9, qa_10
  44 // Initial value : 0
  45 // modifier stmt: qa_20 = qa_10 + 1;
  46 //
  47 // Based on just this analysis, We can project that qa_9 and qa_10 will have
  48 // a range of [0, +INF].
  49
  50 class phi_group
  51 {
  52 public:
  53   phi_group (bitmap bm, tree init_val, edge e, gimple *mod, range_query *q);
  54   phi_group (const phi_group &g);
  55   const_bitmap group () const { return m_group; }
  56   const vrange &range () const { return m_vr; }
  57   tree initial_value () const { return m_initial_value; }
  58   gimple *modifier_stmt () const { return m_modifier; }
  59   void dump (FILE *);
  60 protected:
  61   bool calculate_using_modifier (range_query *q);
  62   bool refine_using_relation (relation_kind k, range_query *q);
  63   static unsigned is_modifier_p (gimple *s, const bitmap bm);
  64   bitmap m_group;
  65   tree m_initial_value;   // Name or constant.
  66   edge m_initial_edge;    // Edge of initial value.
  67   gimple *m_modifier;     // Single stmt which modifies phi group.
  68   unsigned m_modifier_op; // Operand of group member in modifier stmt.
  69   int_range<3> m_vr;
  70   friend class phi_analyzer;
  71 };
  72
  73 // The phi anlyzer will return the group that name belongs to.
  74 // If inforamtion is not known about a name yet, analysis is conducted by
  75 // looking at the arguments to PHIS and following them to their defs to
  76 // determine whether the conditions are met to form a new group.
  77
  78 class phi_analyzer
  79 {
  80 public:
  81   phi_analyzer (range_query &);
  82   ~phi_analyzer ();
  83   phi_group *operator[] (tree name);
  84   void dump (FILE *f);
  85 protected:
  86   phi_group *group (tree name) const;
  87   void process_phi (gphi *phi);
  88   range_query &m_global;
  89   vec<tree> m_work;
  90
  91   bitmap m_simple;       // Processed, not part of a group.
  92   bitmap m_current;      // Potential group currently being analyzed.
  93   vec<phi_group *> m_tab;
  94   bitmap_obstack m_bitmaps;
  95 };
  96
  97 // These are the APIs to start and stop a phi analyzerin a SCEV like manner.
  98 // There can only be one operating at any given time.
  99 // When initialized, a range-query if provided to do lookups of values for
 100 // PHIs and to evaluate modifier and initial value statements.
 101 // To avoid problems, this should be some form of constant query, like
 102 // global_range_query or better yet a const_query from a functioning ranger.
 103
 104 bool phi_analysis_available_p ();
 105 phi_analyzer &phi_analysis ();
 106 void phi_analysis_initialize (range_query &);
 107 void phi_analysis_finalize ();
 108
 109 #endif // GCC_SSA_RANGE_PHI_H