gcc/gimple-range-path.h

   1 /* Header file for jump threading path solver.
   2    Copyright (C) 2021-2022 Free Software Foundation, Inc.
   3    Contributed by Aldy Hernandez <aldyh@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_TREE_SSA_THREADSOLVER_H
  22 #define GCC_TREE_SSA_THREADSOLVER_H
  23
  24 // This class is a basic block path solver.  Given a set of BBs
  25 // indicating a path through the CFG, range_of_expr and range_of_stmt
  26 // will calculate the range of an SSA or STMT as if the BBs in the
  27 // path would have been executed in order.
  28 //
  29 // Note that the blocks are in reverse order, thus the exit block is
  30 // path[0].
  31
  32 class path_range_query : public range_query
  33 {
  34 public:
  35   path_range_query (class gimple_ranger &ranger,
  36                     const vec<basic_block> &path,
  37                     const bitmap_head *dependencies = NULL,
  38                     bool resolve = true);
  39   path_range_query (gimple_ranger &ranger, bool resolve = true);
  40   virtual ~path_range_query ();
  41   void reset_path (const vec<basic_block> &, const bitmap_head *dependencies);
  42   bool range_of_expr (vrange &r, tree name, gimple * = NULL) override;
  43   bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override;
  44   bool unreachable_path_p ();
  45   void dump (FILE *) override;
  46   void debug ();
  47
  48 private:
  49   bool internal_range_of_expr (vrange &r, tree name, gimple *);
  50   void compute_ranges (const bitmap_head *dependencies);
  51   void compute_exit_dependencies (bitmap_head *dependencies);
  52   bool defined_outside_path (tree name);
  53   void range_on_path_entry (vrange &r, tree name);
  54   path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; }
  55
  56   // Cache manipulation.
  57   void set_cache (const vrange &r, tree name);
  58   bool get_cache (vrange &r, tree name);
  59   void clear_cache (tree name);
  60
  61   // Methods to compute ranges for the given path.
  62   bool range_defined_in_block (vrange &, tree name, basic_block bb);
  63   void compute_ranges_in_block (basic_block bb);
  64   void compute_ranges_in_phis (basic_block bb);
  65   void adjust_for_non_null_uses (basic_block bb);
  66   void ssa_range_in_phi (vrange &r, gphi *phi);
  67   void compute_outgoing_relations (basic_block bb, basic_block next);
  68   void compute_phi_relations (basic_block bb, basic_block prev);
  69   void maybe_register_phi_relation (gphi *, edge e);
  70   bool add_to_exit_dependencies (tree name, bitmap dependencies);
  71   bool exit_dependency_p (tree name);
  72   bool ssa_defined_in_bb (tree name, basic_block bb);
  73   bool relations_may_be_invalidated (edge);
  74
  75   // Path navigation.
  76   basic_block entry_bb () { return m_path[m_path.length () - 1]; }
  77   basic_block exit_bb ()  { return m_path[0]; }
  78   basic_block curr_bb ()  { return m_path[m_pos]; }
  79   basic_block prev_bb ()  { return m_path[m_pos + 1]; }
  80   basic_block next_bb ()  { return m_path[m_pos - 1]; }
  81   bool at_entry ()        { return m_pos == m_path.length () - 1; }
  82   bool at_exit ()         { return m_pos == 0; }
  83   void move_next ()       { --m_pos; }
  84
  85   // Range cache for SSA names.
  86   ssa_global_cache *m_cache;
  87
  88   // Set for each SSA that has an active entry in the cache.
  89   bitmap m_has_cache_entry;
  90
  91   // Path being analyzed.
  92   auto_vec<basic_block> m_path;
  93
  94   // This is a list of SSA names that may have relevant context
  95   // information for solving the final conditional along the path.
  96   // Ranges for these SSA names are pre-calculated and cached during a
  97   // top-down traversal of the path, and are then used to answer
  98   // questions at the path exit.
  99   auto_bitmap m_exit_dependencies;
 100
 101   // A ranger used to resolve ranges for SSA names whose values come
 102   // from outside the path.
 103   gimple_ranger &m_ranger;
 104
 105   // Current path position.
 106   unsigned m_pos;
 107
 108   // Use ranger to resolve anything not known on entry.
 109   bool m_resolve;
 110
 111   // Set if there were any undefined expressions while pre-calculating path.
 112   bool m_undefined_path;
 113 };
 114
 115 #endif // GCC_TREE_SSA_THREADSOLVER_H