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 "toplev.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 "timevar.h" 52 #include "tree-pass.h" 53 54 55 /* Find the root of unionfind tree (the representative of set). */ 56 57 struct web_entry * 58 unionfind_root (struct web_entry *element) 59 { 60 struct web_entry *element1 = element, *element2; 61 62 while (element->pred) 63 element = element->pred; 64 while (element1->pred) 65 { 66 element2 = element1->pred; 67 element1->pred = element; 68 element1 = element2; 69 } 70 return element; 71 } 72 73 /* Union sets. 74 Return true if FIRST and SECOND points to the same web entry structure and 75 nothing is done. Otherwise, return false. */ 76 77 bool 78 unionfind_union (struct web_entry *first, struct web_entry *second) 79 { 80 first = unionfind_root (first); 81 second = unionfind_root (second); 82 if (first == second) 83 return true; 84 second->pred = first; 85 return false; 86 } 87 88 /* For each use, all possible defs reaching it must come in the same 89 register, union them. 90 FUN is the function that does the union. 91 92 In USED, we keep the DF_REF_ID of the first uninitialized uses of a 93 register, so that all uninitialized uses of the register can be 94 combined into a single web. We actually offset it by 2, because 95 the values 0 and 1 are reserved for use by entry_register. */ 96 97 void 98 union_defs (df_ref use, struct web_entry *def_entry, 99 unsigned int *used, struct web_entry *use_entry, 100 bool (*fun) (struct web_entry *, struct web_entry *)) 101 { 102 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use); 103 struct df_link *link = DF_REF_CHAIN (use); 104 df_ref *use_link; 105 df_ref *eq_use_link; 106 df_ref *def_link; 107 rtx set; 108 109 if (insn_info) 110 { 111 rtx insn = insn_info->insn; 112 use_link = DF_INSN_INFO_USES (insn_info); 113 eq_use_link = DF_INSN_INFO_EQ_USES (insn_info); 114 def_link = DF_INSN_INFO_DEFS (insn_info); 115 set = single_set (insn); 116 } 117 else 118 { 119 /* An artificial use. It links up with nothing. */ 120 use_link = NULL; 121 eq_use_link = NULL; 122 def_link = NULL; 123 set = NULL; 124 } 125 126 /* Some instructions may use match_dup for their operands. In case the 127 operands are dead, we will assign them different pseudos, creating 128 invalid instructions, so union all uses of the same operand for each 129 insn. */ 130 131 if (use_link) 132 while (*use_link) 133 { 134 if (use != *use_link 135 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*use_link)) 136 (*fun) (use_entry + DF_REF_ID (use), 137 use_entry + DF_REF_ID (*use_link)); 138 use_link++; 139 } 140 141 if (eq_use_link) 142 while (*eq_use_link) 143 { 144 if (use != *eq_use_link 145 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link)) 146 (*fun) (use_entry + DF_REF_ID (use), 147 use_entry + DF_REF_ID (*eq_use_link)); 148 eq_use_link++; 149 } 150 151 /* Recognize trivial noop moves and attempt to keep them as noop. */ 152 153 if (set 154 && SET_SRC (set) == DF_REF_REG (use) 155 && SET_SRC (set) == SET_DEST (set)) 156 { 157 if (def_link) 158 while (*def_link) 159 { 160 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link)) 161 (*fun) (use_entry + DF_REF_ID (use), 162 def_entry + DF_REF_ID (*def_link)); 163 def_link++; 164 } 165 } 166 167 /* UD chains of uninitialized REGs are empty. Keeping all uses of 168 the same uninitialized REG in a single web is not necessary for 169 correctness, since the uses are undefined, but it's wasteful to 170 allocate one register or slot for each reference. Furthermore, 171 creating new pseudos for uninitialized references in debug insns 172 (see PR 42631) causes -fcompare-debug failures. We record the 173 number of the first uninitialized reference we found, and merge 174 with it any other uninitialized references to the same 175 register. */ 176 if (!link) 177 { 178 int regno = REGNO (DF_REF_REAL_REG (use)); 179 if (used[regno]) 180 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2); 181 else 182 used[regno] = DF_REF_ID (use) + 2; 183 } 184 185 while (link) 186 { 187 (*fun) (use_entry + DF_REF_ID (use), 188 def_entry + DF_REF_ID (link->ref)); 189 link = link->next; 190 } 191 192 /* A READ_WRITE use requires the corresponding def to be in the same 193 register. Find it and union. */ 194 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) 195 { 196 df_ref *link; 197 198 if (insn_info) 199 link = DF_INSN_INFO_DEFS (insn_info); 200 else 201 link = NULL; 202 203 if (link) 204 while (*link) 205 { 206 if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use)) 207 (*fun) (use_entry + DF_REF_ID (use), 208 def_entry + DF_REF_ID (*link)); 209 link++; 210 } 211 } 212 } 213 214 /* Find the corresponding register for the given entry. */ 215 216 static rtx 217 entry_register (struct web_entry *entry, df_ref ref, unsigned int *used) 218 { 219 struct web_entry *root; 220 rtx reg, newreg; 221 222 /* Find the corresponding web and see if it has been visited. */ 223 root = unionfind_root (entry); 224 if (root->reg) 225 return root->reg; 226 227 /* We are seeing this web for the first time, do the assignment. */ 228 reg = DF_REF_REAL_REG (ref); 229 230 /* In case the original register is already assigned, generate new 231 one. Since we use USED to merge uninitialized refs into a single 232 web, we might found an element to be nonzero without our having 233 used it. Test for 1, because union_defs saves it for our use, 234 and there won't be any use for the other values when we get to 235 this point. */ 236 if (used[REGNO (reg)] != 1) 237 newreg = reg, used[REGNO (reg)] = 1; 238 else 239 { 240 newreg = gen_reg_rtx (GET_MODE (reg)); 241 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg); 242 REG_POINTER (newreg) = REG_POINTER (reg); 243 REG_ATTRS (newreg) = REG_ATTRS (reg); 244 if (dump_file) 245 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg), 246 REGNO (newreg)); 247 } 248 249 root->reg = newreg; 250 return newreg; 251 } 252 253 /* Replace the reference by REG. */ 254 255 static void 256 replace_ref (df_ref ref, rtx reg) 257 { 258 rtx oldreg = DF_REF_REAL_REG (ref); 259 rtx *loc = DF_REF_REAL_LOC (ref); 260 unsigned int uid = DF_REF_INSN_UID (ref); 261 262 if (oldreg == reg) 263 return; 264 if (dump_file) 265 fprintf (dump_file, "Updating insn %i (%i->%i)\n", 266 uid, REGNO (oldreg), REGNO (reg)); 267 *loc = reg; 268 df_insn_rescan (DF_REF_INSN (ref)); 269 } 270 271 272 static bool 273 gate_handle_web (void) 274 { 275 return (optimize > 0 && flag_web); 276 } 277 278 /* Main entry point. */ 279 280 static unsigned int 281 web_main (void) 282 { 283 struct web_entry *def_entry; 284 struct web_entry *use_entry; 285 unsigned int max = max_reg_num (); 286 unsigned int *used; 287 basic_block bb; 288 unsigned int uses_num = 0; 289 rtx insn; 290 291 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES); 292 df_chain_add_problem (DF_UD_CHAIN); 293 df_analyze (); 294 df_set_flags (DF_DEFER_INSN_RESCAN); 295 296 /* Assign ids to the uses. */ 297 FOR_ALL_BB (bb) 298 FOR_BB_INSNS (bb, insn) 299 { 300 unsigned int uid = INSN_UID (insn); 301 if (NONDEBUG_INSN_P (insn)) 302 { 303 df_ref *use_rec; 304 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) 305 { 306 df_ref use = *use_rec; 307 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 308 DF_REF_ID (use) = uses_num++; 309 } 310 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) 311 { 312 df_ref use = *use_rec; 313 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 314 DF_REF_ID (use) = uses_num++; 315 } 316 } 317 } 318 319 /* Record the number of uses and defs at the beginning of the optimization. */ 320 def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE()); 321 used = XCNEWVEC (unsigned, max); 322 use_entry = XCNEWVEC (struct web_entry, uses_num); 323 324 /* Produce the web. */ 325 FOR_ALL_BB (bb) 326 FOR_BB_INSNS (bb, insn) 327 { 328 unsigned int uid = INSN_UID (insn); 329 if (NONDEBUG_INSN_P (insn)) 330 { 331 df_ref *use_rec; 332 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) 333 { 334 df_ref use = *use_rec; 335 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 336 union_defs (use, def_entry, used, use_entry, unionfind_union); 337 } 338 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) 339 { 340 df_ref use = *use_rec; 341 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 342 union_defs (use, def_entry, used, use_entry, unionfind_union); 343 } 344 } 345 } 346 347 /* Update the instruction stream, allocating new registers for split pseudos 348 in progress. */ 349 FOR_ALL_BB (bb) 350 FOR_BB_INSNS (bb, insn) 351 { 352 unsigned int uid = INSN_UID (insn); 353 if (NONDEBUG_INSN_P (insn)) 354 { 355 df_ref *use_rec; 356 df_ref *def_rec; 357 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) 358 { 359 df_ref use = *use_rec; 360 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 361 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used)); 362 } 363 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) 364 { 365 df_ref use = *use_rec; 366 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) 367 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used)); 368 } 369 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) 370 { 371 df_ref def = *def_rec; 372 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER) 373 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used)); 374 } 375 } 376 } 377 378 free (def_entry); 379 free (use_entry); 380 free (used); 381 return 0; 382 } 383 384 struct rtl_opt_pass pass_web = 385 { 386 { 387 RTL_PASS, 388 "web", /* name */ 389 gate_handle_web, /* gate */ 390 web_main, /* execute */ 391 NULL, /* sub */ 392 NULL, /* next */ 393 0, /* static_pass_number */ 394 TV_WEB, /* tv_id */ 395 0, /* properties_required */ 396 0, /* properties_provided */ 397 0, /* properties_destroyed */ 398 0, /* todo_flags_start */ 399 TODO_df_finish | TODO_verify_rtl_sharing | 400 TODO_dump_func /* todo_flags_finish */ 401 } 402 }; 403 404