Line data    Source code

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