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