gcc/ipa-icf-gimple.h

   1 /* Interprocedural semantic function equality pass
   2    Copyright (C) 2014 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 infastructure
  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 instanse of func_checker and call
  28    a comparsion 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 /* Prints a MESSAGE to dump_file if exists. FUNC is name of function and
  40    LINE is location in the source file.  */
  41
  42 static inline void
  43 dump_message_1 (const char *message, const char *func, unsigned int line)
  44 {
  45   if (dump_file && (dump_flags & TDF_DETAILS))
  46     fprintf (dump_file, "  debug message: %s (%s:%u)\n", message, func, line);
  47 }
  48
  49 /* Prints a MESSAGE to dump_file if exists.  */
  50 #define dump_message(message) dump_message_1 (message, __func__, __LINE__)
  51
  52 /* Logs a MESSAGE to dump_file if exists and returns false. FUNC is name
  53    of function and LINE is location in the source file.  */
  54
  55 static inline bool
  56 return_false_with_message_1 (const char *message, const char *func,
  57                              unsigned int line)
  58 {
  59   if (dump_file && (dump_flags & TDF_DETAILS))
  60     fprintf (dump_file, "  false returned: '%s' (%s:%u)\n", message, func, line);
  61   return false;
  62 }
  63
  64 /* Logs a MESSAGE to dump_file if exists and returns false.  */
  65 #define return_false_with_msg(message) \
  66   return_false_with_message_1 (message, __func__, __LINE__)
  67
  68 /* Return false and log that false value is returned.  */
  69 #define return_false() return_false_with_msg ("")
  70
  71 /* Logs return value if RESULT is false. FUNC is name of function and LINE
  72    is location in the source file.  */
  73
  74 static inline bool
  75 return_with_result (bool result, const char *func, unsigned int line)
  76 {
  77   if (!result && dump_file && (dump_flags & TDF_DETAILS))
  78     fprintf (dump_file, "  false returned (%s:%u)\n", func, line);
  79
  80   return result;
  81 }
  82
  83 /* Logs return value if RESULT is false.  */
  84 #define return_with_debug(result) return_with_result (result, __func__, __LINE__)
  85
  86 /* Verbose logging function logging statements S1 and S2 of a CODE.
  87    FUNC is name of function and LINE is location in the source file.  */
  88
  89 static inline bool
  90 return_different_stmts_1 (gimple s1, gimple s2, const char *code,
  91                           const char *func, unsigned int line)
  92 {
  93   if (dump_file && (dump_flags & TDF_DETAILS))
  94     {
  95       fprintf (dump_file, "  different statement for code: %s (%s:%u):\n",
  96                code, func, line);
  97
  98       print_gimple_stmt (dump_file, s1, 3, TDF_DETAILS);
  99       print_gimple_stmt (dump_file, s2, 3, TDF_DETAILS);
 100     }
 101
 102   return false;
 103 }
 104
 105 /* Verbose logging function logging statements S1 and S2 of a CODE.  */
 106 #define return_different_stmts(s1, s2, code) \
 107   return_different_stmts_1 (s1, s2, code, __func__, __LINE__)
 108
 109 namespace ipa_icf_gimple {
 110
 111 /* Basic block struct for semantic equality pass.  */
 112 class sem_bb
 113 {
 114 public:
 115   sem_bb (basic_block bb_, unsigned nondbg_stmt_count_, unsigned edge_count_):
 116     bb (bb_), nondbg_stmt_count (nondbg_stmt_count_), edge_count (edge_count_) {}
 117
 118   /* Basic block the structure belongs to.  */
 119   basic_block bb;
 120
 121   /* Number of non-debug statements in the basic block.  */
 122   unsigned nondbg_stmt_count;
 123
 124   /* Number of edges connected to the block.  */
 125   unsigned edge_count;
 126 };
 127
 128 /* A class aggregating all connections and semantic equivalents
 129    for a given pair of semantic function candidates.  */
 130 class func_checker
 131 {
 132 public:
 133   /* Initialize internal structures for a given SOURCE_FUNC_DECL and
 134      TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
 135      an option COMPARE_POLYMORPHIC is true. For special cases, one can
 136      set IGNORE_LABELS to skip label comparison.
 137      Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets
 138      of declarations that can be skipped.  */
 139   func_checker (tree source_func_decl, tree target_func_decl,
 140                 bool compare_polymorphic,
 141                 bool ignore_labels = false,
 142                 hash_set<symtab_node *> *ignored_source_nodes = NULL,
 143                 hash_set<symtab_node *> *ignored_target_nodes = NULL);
 144
 145   /* Memory release routine.  */
 146   ~func_checker();
 147
 148   void parse_labels (sem_bb *bb);
 149
 150   /* Basic block equivalence comparison function that returns true if
 151      basic blocks BB1 and BB2 correspond.  */
 152   bool compare_bb (sem_bb *bb1, sem_bb *bb2);
 153
 154   /* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
 155   bool compare_ssa_name (tree t1, tree t2);
 156
 157   /* Verification function for edges E1 and E2.  */
 158   bool compare_edge (edge e1, edge e2);
 159
 160   /* Verifies for given GIMPLEs S1 and S2 that
 161      call statements are semantically equivalent.  */
 162   bool compare_gimple_call (gimple s1, gimple s2);
 163
 164   /* Verifies for given GIMPLEs S1 and S2 that
 165      assignment statements are semantically equivalent.  */
 166   bool compare_gimple_assign (gimple s1, gimple s2);
 167
 168   /* Verifies for given GIMPLEs S1 and S2 that
 169      condition statements are semantically equivalent.  */
 170   bool compare_gimple_cond (gimple s1, gimple s2);
 171
 172   /* Verifies for given GIMPLEs S1 and S2 that
 173      label statements are semantically equivalent.  */
 174   bool compare_gimple_label (gimple s1, gimple s2);
 175
 176   /* Verifies for given GIMPLEs S1 and S2 that
 177      switch statements are semantically equivalent.  */
 178   bool compare_gimple_switch (gimple s1, gimple s2);
 179
 180   /* Verifies for given GIMPLEs S1 and S2 that
 181      return statements are semantically equivalent.  */
 182   bool compare_gimple_return (gimple s1, gimple s2);
 183
 184   /* Verifies for given GIMPLEs S1 and S2 that
 185      goto statements are semantically equivalent.  */
 186   bool compare_gimple_goto (gimple s1, gimple s2);
 187
 188   /* Verifies for given GIMPLEs S1 and S2 that
 189      resx statements are semantically equivalent.  */
 190   bool compare_gimple_resx (gimple s1, gimple s2);
 191
 192   /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
 193      For the beginning, the pass only supports equality for
 194      '__asm__ __volatile__ ("", "", "", "memory")'.  */
 195   bool compare_gimple_asm (gimple s1, gimple s2);
 196
 197   /* Verification function for declaration trees T1 and T2.  */
 198   bool compare_decl (tree t1, tree t2);
 199
 200   /* Verifies that tree labels T1 and T2 correspond.  */
 201   bool compare_tree_ssa_label (tree t1, tree t2);
 202
 203   /* Function responsible for comparison of handled components T1 and T2.
 204      If these components, from functions FUNC1 and FUNC2, are equal, true
 205      is returned.  */
 206   bool compare_operand (tree t1, tree t2);
 207
 208   /* Compares two tree list operands T1 and T2 and returns true if these
 209      two trees are semantically equivalent.  */
 210   bool compare_tree_list_operand (tree t1, tree t2);
 211
 212   /* Verifies that trees T1 and T2, representing function declarations
 213      are equivalent from perspective of ICF.  */
 214   bool compare_function_decl (tree t1, tree t2);
 215
 216   /* Verifies that trees T1 and T2 do correspond.  */
 217   bool compare_variable_decl (tree t1, tree t2);
 218
 219   /* Return true if types are compatible from perspective of ICF.
 220      FIRST_ARGUMENT indicates if the comparison is called for
 221      first parameter of a function.  */
 222   static bool compatible_types_p (tree t1, tree t2,
 223                                   bool compare_polymorphic = true,
 224                                   bool first_argument = false);
 225
 226
 227 private:
 228   /* Vector mapping source SSA names to target ones.  */
 229   vec <int> m_source_ssa_names;
 230
 231   /* Vector mapping target SSA names to source ones.  */
 232   vec <int> m_target_ssa_names;
 233
 234   /* Source TREE function declaration.  */
 235   tree m_source_func_decl;
 236
 237   /* Target TREE function declaration.  */
 238   tree m_target_func_decl;
 239
 240   /* Source symbol nodes that should be skipped by
 241      declaration comparison.  */
 242   hash_set<symtab_node *> *m_ignored_source_nodes;
 243
 244   /* Target symbol nodes that should be skipped by
 245      declaration comparison.  */
 246   hash_set<symtab_node *> *m_ignored_target_nodes;
 247
 248   /* Source to target edge map.  */
 249   hash_map <edge, edge> m_edge_map;
 250
 251   /* Source to target declaration map.  */
 252   hash_map <tree, tree> m_decl_map;
 253
 254   /* Label to basic block index mapping.  */
 255   hash_map <tree, int> m_label_bb_map;
 256
 257   /* Flag if polymorphic comparison should be executed.  */
 258   bool m_compare_polymorphic;
 259
 260   /* Flag if ignore labels in comparison.  */
 261   bool m_ignore_labels;
 262 };
 263
 264 } // ipa_icf_gimple namespace