1/* Interprocedural semantic function equality pass
2   Copyright (C) 2014-2015 Free Software Foundation, Inc.
3
4   Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
42static inline void
43dump_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
55static inline bool
56return_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
74static inline bool
75return_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
89static inline bool
90return_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
109namespace ipa_icf_gimple {
110
111/* Basic block struct for semantic equality pass.  */
112class sem_bb
113{
114public:
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.  */
130class func_checker
131{
132public:
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  /* Function visits all gimple labels and creates corresponding
149     mapping between basic blocks and labels.  */
150  void parse_labels (sem_bb *bb);
151
152  /* Basic block equivalence comparison function that returns true if
153     basic blocks BB1 and BB2 correspond.  */
154  bool compare_bb (sem_bb *bb1, sem_bb *bb2);
155
156  /* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
157  bool compare_ssa_name (tree t1, tree t2);
158
159  /* Verification function for edges E1 and E2.  */
160  bool compare_edge (edge e1, edge e2);
161
162  /* Verifies for given GIMPLEs S1 and S2 that
163     call statements are semantically equivalent.  */
164  bool compare_gimple_call (gcall *s1, gcall *s2);
165
166  /* Verifies for given GIMPLEs S1 and S2 that
167     assignment statements are semantically equivalent.  */
168  bool compare_gimple_assign (gimple s1, gimple s2);
169
170  /* Verifies for given GIMPLEs S1 and S2 that
171     condition statements are semantically equivalent.  */
172  bool compare_gimple_cond (gimple s1, gimple s2);
173
174  /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
175     label statements are semantically equivalent.  */
176  bool compare_gimple_label (const glabel *s1, const glabel *s2);
177
178  /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
179     switch statements are semantically equivalent.  */
180  bool compare_gimple_switch (const gswitch *s1, const gswitch *s2);
181
182  /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
183     return statements are semantically equivalent.  */
184  bool compare_gimple_return (const greturn *s1, const greturn *s2);
185
186  /* Verifies for given GIMPLEs S1 and S2 that
187     goto statements are semantically equivalent.  */
188  bool compare_gimple_goto (gimple s1, gimple s2);
189
190  /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
191     resx statements are semantically equivalent.  */
192  bool compare_gimple_resx (const gresx *s1, const gresx *s2);
193
194  /* Verifies for given GIMPLE_ASM stmts S1 and S2 that ASM statements
195     are equivalent.
196     For the beginning, the pass only supports equality for
197     '__asm__ __volatile__ ("", "", "", "memory")'.  */
198  bool compare_gimple_asm (const gasm *s1, const gasm *s2);
199
200  /* Verification function for declaration trees T1 and T2.  */
201  bool compare_decl (tree t1, tree t2);
202
203  /* Verifies that tree labels T1 and T2 correspond.  */
204  bool compare_tree_ssa_label (tree t1, tree t2);
205
206  /* Function compare for equality given memory operands T1 and T2.  */
207  bool compare_memory_operand (tree t1, tree t2);
208
209  /* Function compare for equality given trees T1 and T2 which
210     can be either a constant or a declaration type.  */
211  bool compare_cst_or_decl (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);
217
218  /* Compares two tree list operands T1 and T2 and returns true if these
219     two trees are semantically equivalent.  */
220  bool compare_tree_list_operand (tree t1, tree t2);
221
222  /* Verifies that trees T1 and T2, representing function declarations
223     are equivalent from perspective of ICF.  */
224  bool compare_function_decl (tree t1, tree t2);
225
226  /* Verifies that trees T1 and T2 do correspond.  */
227  bool compare_variable_decl (tree t1, tree t2);
228
229  /* Return true if types are compatible for polymorphic call analysis.
230     COMPARE_PTR indicates if polymorphic type comparsion should be
231     done for pointers, too.  */
232  static bool compatible_polymorphic_types_p (tree t1, tree t2,
233					      bool compare_ptr);
234
235  /* Return true if types are compatible from perspective of ICF.
236     FIRST_ARGUMENT indicates if the comparison is called for
237     first parameter of a function.  */
238  static bool compatible_types_p (tree t1, tree t2);
239
240
241private:
242  /* Vector mapping source SSA names to target ones.  */
243  vec <int> m_source_ssa_names;
244
245  /* Vector mapping target SSA names to source ones.  */
246  vec <int> m_target_ssa_names;
247
248  /* Source TREE function declaration.  */
249  tree m_source_func_decl;
250
251  /* Target TREE function declaration.  */
252  tree m_target_func_decl;
253
254  /* Source symbol nodes that should be skipped by
255     declaration comparison.  */
256  hash_set<symtab_node *> *m_ignored_source_nodes;
257
258  /* Target symbol nodes that should be skipped by
259     declaration comparison.  */
260  hash_set<symtab_node *> *m_ignored_target_nodes;
261
262  /* Source to target edge map.  */
263  hash_map <edge, edge> m_edge_map;
264
265  /* Source to target declaration map.  */
266  hash_map <tree, tree> m_decl_map;
267
268  /* Label to basic block index mapping.  */
269  hash_map <tree, int> m_label_bb_map;
270
271  /* Flag if polymorphic comparison should be executed.  */
272  bool m_compare_polymorphic;
273
274  /* Flag if ignore labels in comparison.  */
275  bool m_ignore_labels;
276};
277
278} // ipa_icf_gimple namespace
279