gcc/gimple-range-phi.h

   1 /* Header file for gimple range phi analysis.
   2    Copyright (C) 2023-2024 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, irange &init_range, 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   gimple *modifier_stmt () const { return m_modifier; }
  58   void dump (FILE *);
  59 protected:
  60   bool calculate_using_modifier (range_query *q);
  61   bool refine_using_relation (relation_kind k);
  62   static unsigned is_modifier_p (gimple *s, const bitmap bm);
  63   bitmap m_group;
  64   gimple *m_modifier;     // Single stmt which modifies phi group.
  65   unsigned m_modifier_op; // Operand of group member in modifier stmt.
  66   int_range_max m_vr;
  67   friend class phi_analyzer;
  68 };
  69
  70 // The phi anlyzer will return the group that name belongs to.
  71 // If inforamtion is not known about a name yet, analysis is conducted by
  72 // looking at the arguments to PHIS and following them to their defs to
  73 // determine whether the conditions are met to form a new group.
  74
  75 class phi_analyzer
  76 {
  77 public:
  78   phi_analyzer (range_query &);
  79   ~phi_analyzer ();
  80   phi_group *operator[] (tree name);
  81   void dump (FILE *f);
  82 protected:
  83   phi_group *group (tree name) const;
  84   void process_phi (gphi *phi);
  85   range_query &m_global;
  86   vec<tree> m_work;
  87
  88   bitmap m_simple;       // Processed, not part of a group.
  89   bitmap m_current;      // Potential group currently being analyzed.
  90   vec<phi_group *> m_phi_groups;
  91   vec<phi_group *> m_tab;
  92   bitmap_obstack m_bitmaps;
  93 };
  94
  95 // These are the APIs to start and stop a phi analyzerin a SCEV like manner.
  96 // There can only be one operating at any given time.
  97 // When initialized, a range-query if provided to do lookups of values for
  98 // PHIs and to evaluate modifier and initial value statements.
  99 // To avoid problems, this should be some form of constant query, like
 100 // global_range_query or better yet a const_query from a functioning ranger.
 101
 102 bool phi_analysis_available_p ();
 103 phi_analyzer &phi_analysis ();
 104 void phi_analysis_initialize (range_query &);
 105 void phi_analysis_finalize ();
 106
 107 #endif // GCC_SSA_RANGE_PHI_H