1 /* Interprocedural semantic function equality pass 2 Copyright (C) 2014-2018 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 /* 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 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 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 241 private: 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