gcc/ipa-icf-gimple.h

   1 /* Interprocedural semantic function equality pass
   2    Copyright (C) 2014-2024 Free Software Foundation, Inc.
   3
   4    Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* Gimple identical code folding (class func_checker) is an infrastructure
  23    capable of comparing two given functions. The class compares every
  24    gimple statement and uses many dictionaries to map source and target
  25    SSA_NAMEs, declarations and other components.
  26
  27    To use the infrastructure, create an instance of func_checker and call
  28    a comparison function based on type of gimple statement.  */
  29
  30 /* Prints string STRING to a FILE with a given number of SPACE_COUNT.  */
  31 #define FPUTS_SPACES(file, space_count, string) \
  32   fprintf (file, "%*s" string, space_count, " ");
  33
  34 /* fprintf function wrapper that transforms given FORMAT to follow given
  35    number for SPACE_COUNT and call fprintf for a FILE.  */
  36 #define FPRINTF_SPACES(file, space_count, format, ...) \
  37   fprintf (file, "%*s" format, space_count, " ", ##__VA_ARGS__);
  38
  39 /* Logs a MESSAGE to dump_file if exists and returns false. FUNC is name
  40    of function and LINE is location in the source file.  */
  41
  42 inline bool
  43 return_false_with_message_1 (const char *message, const char *filename,
  44                              const char *func, unsigned int line)
  45 {
  46   if (dump_file && (dump_flags & TDF_DETAILS))
  47     fprintf (dump_file, "  false returned: '%s' in %s at %s:%u\n", message, func,
  48              filename, line);
  49   return false;
  50 }
  51
  52 /* Logs a MESSAGE to dump_file if exists and returns false.  */
  53 #define return_false_with_msg(message) \
  54   return_false_with_message_1 (message, __FILE__, __func__, __LINE__)
  55
  56 /* Return false and log that false value is returned.  */
  57 #define return_false() return_false_with_msg ("")
  58
  59 /* Logs return value if RESULT is false. FUNC is name of function and LINE
  60    is location in the source file.  */
  61
  62 inline bool
  63 return_with_result (bool result, const char *filename,
  64                     const char *func, unsigned int line)
  65 {
  66   if (!result && dump_file && (dump_flags & TDF_DETAILS))
  67     fprintf (dump_file, "  false returned: '' in %s at %s:%u\n", func,
  68              filename, line);
  69
  70   return result;
  71 }
  72
  73 /* Logs return value if RESULT is false.  */
  74 #define return_with_debug(result) return_with_result \
  75   (result, __FILE__, __func__, __LINE__)
  76
  77 /* Verbose logging function logging statements S1 and S2 of a CODE.
  78    FUNC is name of function and LINE is location in the source file.  */
  79
  80 inline bool
  81 return_different_stmts_1 (gimple *s1, gimple *s2, const char *code,
  82                           const char *func, unsigned int line)
  83 {
  84   if (dump_file && (dump_flags & TDF_DETAILS))
  85     {
  86       fprintf (dump_file, "  different statement for code: %s (%s:%u):\n",
  87                code, func, line);
  88
  89       print_gimple_stmt (dump_file, s1, 3, TDF_DETAILS);
  90       print_gimple_stmt (dump_file, s2, 3, TDF_DETAILS);
  91     }
  92
  93   return false;
  94 }
  95
  96 /* Verbose logging function logging statements S1 and S2 of a CODE.  */
  97 #define return_different_stmts(s1, s2, code) \
  98   return_different_stmts_1 (s1, s2, code, __func__, __LINE__)
  99
 100 namespace ipa_icf_gimple {
 101
 102 /* Basic block struct for semantic equality pass.  */
 103 class sem_bb
 104 {
 105 public:
 106   sem_bb (basic_block bb_, unsigned nondbg_stmt_count_, unsigned edge_count_):
 107     bb (bb_), nondbg_stmt_count (nondbg_stmt_count_), edge_count (edge_count_) {}
 108
 109   /* Basic block the structure belongs to.  */
 110   basic_block bb;
 111
 112   /* Number of non-debug statements in the basic block.  */
 113   unsigned nondbg_stmt_count;
 114
 115   /* Number of edges connected to the block.  */
 116   unsigned edge_count;
 117 };
 118
 119 /* A class aggregating all connections and semantic equivalents
 120    for a given pair of semantic function candidates.  */
 121 class func_checker : ao_compare
 122 {
 123 public:
 124   /* Default constructor.  */
 125   func_checker ():
 126     m_source_func_decl (NULL_TREE), m_target_func_decl (NULL_TREE),
 127     m_ignored_source_nodes (NULL), m_ignored_target_nodes (NULL),
 128     m_ignore_labels (false), m_tbaa (true),
 129     m_total_scalarization_limit_known_p (false)
 130   {
 131     m_source_ssa_names.create (0);
 132     m_target_ssa_names.create (0);
 133   }
 134
 135   /* Initialize internal structures for a given SOURCE_FUNC_DECL and
 136      TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
 137      an option COMPARE_POLYMORPHIC is true. For special cases, one can
 138      set IGNORE_LABELS to skip label comparison.
 139      Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets
 140      of declarations that can be skipped.  */
 141   func_checker (tree source_func_decl, tree target_func_decl,
 142                 bool ignore_labels = false,
 143                 bool tbaa = true,
 144                 hash_set<symtab_node *> *ignored_source_nodes = NULL,
 145                 hash_set<symtab_node *> *ignored_target_nodes = NULL);
 146
 147   /* Memory release routine.  */
 148   virtual ~func_checker ();
 149
 150   /* Function visits all gimple labels and creates corresponding
 151      mapping between basic blocks and labels.  */
 152   void parse_labels (sem_bb *bb);
 153
 154   /* Basic block equivalence comparison function that returns true if
 155      basic blocks BB1 and BB2 correspond.  */
 156   bool compare_bb (sem_bb *bb1, sem_bb *bb2);
 157
 158   /* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
 159   bool compare_ssa_name (const_tree t1, const_tree t2);
 160
 161   /* Verification function for edges E1 and E2.  */
 162   bool compare_edge (edge e1, edge e2);
 163
 164   /* Verifies for given GIMPLEs S1 and S2 that
 165      call statements are semantically equivalent.  */
 166   bool compare_gimple_call (gcall *s1, gcall *s2);
 167
 168   /* Verifies for given GIMPLEs S1 and S2 that
 169      assignment statements are semantically equivalent.  */
 170   bool compare_gimple_assign (gimple *s1, gimple *s2);
 171
 172   /* Verifies for given GIMPLEs S1 and S2 that
 173      condition statements are semantically equivalent.  */
 174   bool compare_gimple_cond (gimple *s1, gimple *s2);
 175
 176   /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
 177      label statements are semantically equivalent.  */
 178   bool compare_gimple_label (const glabel *s1, const glabel *s2);
 179
 180   /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
 181      switch statements are semantically equivalent.  */
 182   bool compare_gimple_switch (const gswitch *s1, const gswitch *s2);
 183
 184   /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
 185      return statements are semantically equivalent.  */
 186   bool compare_gimple_return (const greturn *s1, const greturn *s2);
 187
 188   /* Verifies for given GIMPLEs S1 and S2 that
 189      goto statements are semantically equivalent.  */
 190   bool compare_gimple_goto (gimple *s1, gimple *s2);
 191
 192   /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
 193      resx statements are semantically equivalent.  */
 194   bool compare_gimple_resx (const gresx *s1, const gresx *s2);
 195
 196   /* Verifies for given GIMPLE_ASM stmts S1 and S2 that ASM statements
 197      are equivalent.
 198      For the beginning, the pass only supports equality for
 199      '__asm__ __volatile__ ("", "", "", "memory")'.  */
 200   bool compare_gimple_asm (const gasm *s1, const gasm *s2);
 201
 202   /* Verification function for declaration trees T1 and T2.  */
 203   bool compare_decl (const_tree t1, const_tree t2);
 204
 205   /* Compute hash map MAP that determines loads and stores of STMT.  */
 206   enum operand_access_type {OP_MEMORY, OP_NORMAL};
 207   typedef hash_set<tree> operand_access_type_map;
 208
 209   /* Return true if either T1 and T2 cannot be totally scalarized or if doing
 210      so would result in copying the same memory.  Otherwise return false.  */
 211   bool safe_for_total_scalarization_p (tree t1, tree t2);
 212
 213   /* Function responsible for comparison of various operands T1 and T2.
 214      If these components, from functions FUNC1 and FUNC2, are equal, true
 215      is returned.  */
 216   bool compare_operand (tree t1, tree t2, operand_access_type type);
 217
 218   /* Compares GIMPLE ASM inputs (or outputs) where we iterate tree chain
 219      and compare both TREE_PURPOSEs and TREE_VALUEs.  */
 220   bool compare_asm_inputs_outputs (tree t1, tree t2,
 221                                    operand_access_type_map *map);
 222
 223   /* Verifies that trees T1 and T2, representing function declarations
 224      are equivalent from perspective of ICF.  */
 225   bool compare_function_decl (tree t1, tree t2);
 226
 227   /* Verifies that trees T1 and T2 do correspond.  */
 228   bool compare_variable_decl (const_tree t1, const_tree t2);
 229
 230   /* Compare loop information for basic blocks BB1 and BB2.  */
 231   bool compare_loops (basic_block bb1, basic_block bb2);
 232
 233   /* Return true if types are compatible for polymorphic call analysis.
 234      COMPARE_PTR indicates if polymorphic type comparison should be
 235      done for pointers, too.  */
 236   static bool compatible_polymorphic_types_p (tree t1, tree t2,
 237                                               bool compare_ptr);
 238
 239   /* Return true if types are compatible from perspective of ICF.
 240      FIRST_ARGUMENT indicates if the comparison is called for
 241      first parameter of a function.  */
 242   static bool compatible_types_p (tree t1, tree t2);
 243
 244   /* Compute hash map determining access types of operands.  */
 245   static void classify_operands (const gimple *stmt,
 246                                  operand_access_type_map *map);
 247
 248   /* Return access type of a given operand.  */
 249   static operand_access_type get_operand_access_type
 250                  (operand_access_type_map *map, tree);
 251 private:
 252   /* Vector mapping source SSA names to target ones.  */
 253   vec <int> m_source_ssa_names;
 254
 255   /* Vector mapping target SSA names to source ones.  */
 256   vec <int> m_target_ssa_names;
 257
 258   /* Source TREE function declaration.  */
 259   tree m_source_func_decl;
 260
 261   /* Target TREE function declaration.  */
 262   tree m_target_func_decl;
 263
 264   /* Source symbol nodes that should be skipped by
 265      declaration comparison.  */
 266   hash_set<symtab_node *> *m_ignored_source_nodes;
 267
 268   /* Target symbol nodes that should be skipped by
 269      declaration comparison.  */
 270   hash_set<symtab_node *> *m_ignored_target_nodes;
 271
 272   /* Source to target edge map.  */
 273   hash_map <edge, edge> m_edge_map;
 274
 275   /* Source to target declaration map.  */
 276   hash_map <const_tree, const_tree> m_decl_map;
 277
 278   /* Label to basic block index mapping.  */
 279   hash_map <const_tree, int> m_label_bb_map;
 280
 281   /* Flag if ignore labels in comparison.  */
 282   bool m_ignore_labels;
 283
 284   /* Flag if we should compare type based alias analysis info.  */
 285   bool m_tbaa;
 286
 287   /* Set to true when total scalarization size has already been determined for
 288      the functions.  */
 289   bool m_total_scalarization_limit_known_p;
 290
 291   /* When the above it set to true the determiend total scalarization
 292      limit.  */
 293   unsigned HOST_WIDE_INT m_total_scalarization_limit;
 294
 295 public:
 296   /* Return true if two operands are equal.  The flags fields can be used
 297      to specify OEP flags described above.  */
 298   bool operand_equal_p (const_tree, const_tree, unsigned int flags)
 299     final override;
 300
 301   /* Generate a hash value for an expression.  This can be used iteratively
 302      by passing a previous result as the HSTATE argument.  */
 303   void hash_operand (const_tree, inchash::hash &, unsigned flags)
 304     final override;
 305   void hash_operand (const_tree, inchash::hash &, unsigned flags,
 306                      operand_access_type access);
 307 };
 308
 309 } // ipa_icf_gimple namespace