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