1 /* Web construction code for GNU compiler. 2 Contributed by Jan Hubicka. 3 Copyright (C) 2001-2017 Free Software Foundation, Inc. 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 /* Simple optimization pass that splits independent uses of each pseudo, 22 increasing effectiveness of other optimizations. The optimization can 23 serve as an example of use for the dataflow module. 24 25 We don't split registers with REG_USERVAR set unless -fmessy-debugging 26 is specified, because debugging information about such split variables 27 is almost unusable. 28 29 TODO 30 - We may use profile information and ignore infrequent use for the 31 purpose of web unifying, inserting the compensation code later to 32 implement full induction variable expansion for loops (currently 33 we expand only if the induction variable is dead afterward, which 34 is often the case). */ 35 36 #include "config.h" 37 #include "system.h" 38 #include "coretypes.h" 39 #include "backend.h" 40 #include "rtl.h" 41 #include "df.h" 42 #include "insn-config.h" 43 #include "recog.h" 44 45 #include "tree-pass.h" 46 47 48 /* Find the root of unionfind tree (the representative of set). */ 49 50 web_entry_base * 51 web_entry_base::unionfind_root () 52 { 53 web_entry_base *element = this, *element1 = this, *element2; 54 55 while (element->pred ()) 56 element = element->pred (); 57 while (element1->pred ()) 58 { 59 element2 = element1->pred (); 60 element1->set_pred (element); 61 element1 = element2; 62 } 63 return element; 64 } 65 66 /* Union sets. 67 Return true if FIRST and SECOND points to the same web entry structure and 68 nothing is done. Otherwise, return false. */ 69 70 bool 71 unionfind_union (web_entry_base *first, web_entry_base *second) 72 { 73 first = first->unionfind_root (); 74 second = second->unionfind_root (); 75 if (first == second) 76 return true; 77 second->set_pred (first); 78 return false; 79 } 80 81 class web_entry : public web_entry_base 82 { 83 private: 84 rtx reg_pvt; 85 86 public: 87 rtx reg () { return reg_pvt; } 88 void set_reg (rtx r) { reg_pvt = r; } 89 }; 90 91 /* For INSN, union all defs and uses that are linked by match_dup. 92 FUN is the function that does the union. */ 93 94 static void 95 union_match_dups (rtx_insn *insn, web_entry *def_entry, web_entry *use_entry, 96 bool (*fun) (web_entry_base *, web_entry_base *)) 97 { 98 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 99 df_ref use_link = DF_INSN_INFO_USES (insn_info); 100 df_ref def_link = DF_INSN_INFO_DEFS (insn_info); 101 struct web_entry *dup_entry; 102 int i; 103 104 extract_insn (insn); 105 106 for (i = 0; i < recog_data.n_dups; i++) 107 { 108 int op = recog_data.dup_num[i]; 109 enum op_type type = recog_data.operand_type[op]; 110 df_ref ref, dupref; 111 struct web_entry *entry; 112 113 dup_entry = use_entry; 114 for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref)) 115 if (DF_REF_LOC (dupref) == recog_data.dup_loc[i]) 116 break; 117 118 if (dupref == NULL && type == OP_INOUT) 119 { 120 dup_entry = def_entry; 121 for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref)) 122 if (DF_REF_LOC (dupref) == recog_data.dup_loc[i]) 123 break; 124 } 125 /* ??? *DUPREF can still be zero, because when an operand matches 126 a memory, DF_REF_LOC (use_link[n]) points to the register part 127 of the address, whereas recog_data.dup_loc[m] points to the 128 entire memory ref, thus we fail to find the duplicate entry, 129 even though it is there. 130 Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c 131 -O3 -fomit-frame-pointer -funroll-loops */ 132 if (dupref == NULL 133 || DF_REF_REGNO (dupref) < FIRST_PSEUDO_REGISTER) 134 continue; 135 136 ref = type == OP_IN ? use_link : def_link; 137 entry = type == OP_IN ? use_entry : def_entry; 138 for (; ref; ref = DF_REF_NEXT_LOC (ref)) 139 { 140 rtx *l = DF_REF_LOC (ref); 141 if (l == recog_data.operand_loc[op]) 142 break; 143 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op]) 144 break; 145 } 146 147 if (!ref && type == OP_INOUT) 148 { 149 entry = use_entry; 150 for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref)) 151 { 152 rtx *l = DF_REF_LOC (ref); 153 if (l == recog_data.operand_loc[op]) 154 break; 155 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op]) 156 break; 157 } 158 } 159 160 gcc_assert (ref); 161 (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref)); 162 } 163 } 164 165 /* For each use, all possible defs reaching it must come in the same 166 register, union them. 167 FUN is the function that does the union. 168 169 In USED, we keep the DF_REF_ID of the first uninitialized uses of a 170 register, so that all uninitialized uses of the register can be 171 combined into a single web. We actually offset it by 2, because 172 the values 0 and 1 are reserved for use by entry_register. */ 173 174 void 175 union_defs (df_ref use, web_entry *def_entry, 176 unsigned int *used, web_entry *use_entry, 177 bool (*fun) (web_entry_base *, web_entry_base *)) 178 { 179 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use); 180 struct df_link *link = DF_REF_CHAIN (use); 181 rtx set; 182 183 if (insn_info) 184 { 185 df_ref eq_use; 186 187 set = single_set (insn_info->insn); 188 FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info) 189 if (use != eq_use 190 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use)) 191 (*fun) (use_entry + DF_REF_ID (use), use_entry + DF_REF_ID (eq_use)); 192 } 193 else 194 set = NULL; 195 196 /* Union all occurrences of the same register in reg notes. */ 197 198 /* Recognize trivial noop moves and attempt to keep them as noop. */ 199 200 if (set 201 && SET_SRC (set) == DF_REF_REG (use) 202 && SET_SRC (set) == SET_DEST (set)) 203 { 204 df_ref def; 205 206 FOR_EACH_INSN_INFO_DEF (def, insn_info) 207 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def)) 208 (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def)); 209 } 210 211 /* UD chains of uninitialized REGs are empty. Keeping all uses of 212 the same uninitialized REG in a single web is not necessary for 213 correctness, since the uses are undefined, but it's wasteful to 214 allocate one register or slot for each reference. Furthermore, 215 creating new pseudos for uninitialized references in debug insns 216 (see PR 42631) causes -fcompare-debug failures. We record the 217 number of the first uninitialized reference we found, and merge 218 with it any other uninitialized references to the same 219 register. */ 220 if (!link) 221 { 222 int regno = REGNO (DF_REF_REAL_REG (use)); 223 if (used[regno]) 224 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2); 225 else 226 used[regno] = DF_REF_ID (use) + 2; 227 } 228 229 while (link) 230 { 231 (*fun) (use_entry + DF_REF_ID (use), 232 def_entry + DF_REF_ID (link->ref)); 233 link = link->next; 234 } 235 236 /* A READ_WRITE use requires the corresponding def to be in the same 237 register. Find it and union. */ 238 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) 239 if (insn_info) 240 { 241 df_ref def; 242 243 FOR_EACH_INSN_INFO_DEF (def, insn_info) 244 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def)) 245 (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def)); 246 } 247 } 248 249 /* Find the corresponding register for the given entry. */ 250 251 static rtx 252 entry_register (web_entry *entry, df_ref ref, unsigned int *used) 253 { 254 web_entry *root; 255 rtx reg, newreg; 256 257 /* Find the corresponding web and see if it has been visited. */ 258 root = (web_entry *)entry->unionfind_root (); 259 if (root->reg ()) 260 return root->reg (); 261 262 /* We are seeing this web for the first time, do the assignment. */ 263 reg = DF_REF_REAL_REG (ref); 264 265 /* In case the original register is already assigned, generate new 266 one. Since we use USED to merge uninitialized refs into a single 267 web, we might found an element to be nonzero without our having 268 used it. Test for 1, because union_defs saves it for our use, 269 and there won't be any use for the other values when we get to 270 this point. */ 271 if (used[REGNO (reg)] != 1) 272 newreg = reg, used[REGNO (reg)] = 1; 273 else 274 { 275 newreg = gen_reg_rtx (GET_MODE (reg)); 276 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg); 277 REG_POINTER (newreg) = REG_POINTER (reg); 278 REG_ATTRS (newreg) = REG_ATTRS (reg); 279 if (dump_file) 280 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg), 281 REGNO (newreg)); 282 } 283 284 root->set_reg (newreg); 285 return newreg; 286 } 287 288 /* Replace the reference by REG. */ 289 290 static void 291 replace_ref (df_ref ref, rtx reg) 292 { 293 rtx oldreg = DF_REF_REAL_REG (ref); 294 rtx *loc = DF_REF_REAL_LOC (ref); 295 unsigned int uid = DF_REF_INSN_UID (ref); 296 297 if (oldreg == reg) 298 return; 299 if (dump_file) 300 fprintf (dump_file, "Updating insn %i (%i->%i)\n", 301 uid, REGNO (oldreg), REGNO (reg)); 302 *loc = reg; 303 df_insn_rescan (DF_REF_INSN (ref)); 304 } 305 306 307 namespace { 308 309 const pass_data pass_data_web = 310 { 311 RTL_PASS, /* type */ 312 "web", /* name */ 313 OPTGROUP_NONE, /* optinfo_flags */ 314 TV_WEB, /* tv_id */ 315 0, /* properties_required */ 316 0, /* properties_provided */ 317 0, /* properties_destroyed */ 318 0, /* todo_flags_start */ 319 TODO_df_finish, /* todo_flags_finish */ 320 }; 321 322 class pass_web : public rtl_opt_pass 323 { 324 public: 325 pass_web (gcc::context *ctxt) 326 : rtl_opt_pass (pass_data_web, ctxt) 327 {} 328 329 /* opt_pass methods: */ 330 virtual bool gate (function *) { return (optimize > 0 && flag_web); } 331 virtual unsigned int execute (function *); 332 333 }; // class pass_web 334 335 unsigned int 336 pass_web::execute (function *fun) 337 { 338 web_entry *def_entry; 339 web_entry *use_entry; 340 unsigned int max = max_reg_num (); 341 unsigned int *used; 342 basic_block bb; 343 unsigned int uses_num = 0; 344 rtx_insn *insn; 345 346 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES); 347 df_set_flags (DF_RD_PRUNE_DEAD_DEFS); 348 df_chain_add_problem (DF_UD_CHAIN); 349 df_analyze (); 350 df_set_flags (DF_DEFER_INSN_RESCAN); 351 352 /* Assign ids to the uses. */ 353 FOR_ALL_BB_FN (bb, fun) 354 FOR_BB_INSNS (bb, insn) 355 { 356 if (NONDEBUG_INSN_P (insn)) 357 { 358 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 359 df_ref use; 360 FOR_EACH_INSN_INFO_USE (use, insn_info) 361 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 362 DF_REF_ID (use) = uses_num++; 363 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 364 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 365 DF_REF_ID (use) = uses_num++; 366 } 367 } 368 369 /* Record the number of uses and defs at the beginning of the optimization. */ 370 def_entry = XCNEWVEC (web_entry, DF_DEFS_TABLE_SIZE ()); 371 used = XCNEWVEC (unsigned, max); 372 use_entry = XCNEWVEC (web_entry, uses_num); 373 374 /* Produce the web. */ 375 FOR_ALL_BB_FN (bb, fun) 376 FOR_BB_INSNS (bb, insn) 377 if (NONDEBUG_INSN_P (insn)) 378 { 379 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 380 df_ref use; 381 union_match_dups (insn, def_entry, use_entry, unionfind_union); 382 FOR_EACH_INSN_INFO_USE (use, insn_info) 383 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 384 union_defs (use, def_entry, used, use_entry, unionfind_union); 385 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 386 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 387 union_defs (use, def_entry, used, use_entry, unionfind_union); 388 } 389 390 /* Update the instruction stream, allocating new registers for split pseudos 391 in progress. */ 392 FOR_ALL_BB_FN (bb, fun) 393 FOR_BB_INSNS (bb, insn) 394 if (NONDEBUG_INSN_P (insn) 395 /* Ignore naked clobber. For example, reg 134 in the second insn 396 of the following sequence will not be replaced. 397 398 (insn (clobber (reg:SI 134))) 399 400 (insn (set (reg:SI 0 r0) (reg:SI 134))) 401 402 Thus the later passes can optimize them away. */ 403 && GET_CODE (PATTERN (insn)) != CLOBBER) 404 { 405 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 406 df_ref def, use; 407 FOR_EACH_INSN_INFO_USE (use, insn_info) 408 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 409 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), 410 use, used)); 411 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 412 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 413 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), 414 use, used)); 415 FOR_EACH_INSN_INFO_DEF (def, insn_info) 416 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER) 417 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), 418 def, used)); 419 } 420 421 free (def_entry); 422 free (use_entry); 423 free (used); 424 return 0; 425 } 426 427 } // anon namespace 428 429 rtl_opt_pass * 430 make_pass_web (gcc::context *ctxt) 431 { 432 return new pass_web (ctxt); 433 } 434