1132718Skan/* Web construction code for GNU compiler. 2132718Skan Contributed by Jan Hubicka. 3169689Skan Copyright (C) 2001, 2002, 2004, 2006 4169689Skan Free Software Foundation, Inc. 5132718Skan 6132718SkanThis file is part of GCC. 7132718Skan 8132718SkanGCC is free software; you can redistribute it and/or modify it under 9132718Skanthe terms of the GNU General Public License as published by the Free 10132718SkanSoftware Foundation; either version 2, or (at your option) any later 11132718Skanversion. 12132718Skan 13132718SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 14132718SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 15132718SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16132718Skanfor more details. 17132718Skan 18132718SkanYou should have received a copy of the GNU General Public License 19132718Skanalong with GCC; see the file COPYING. If not, write to the Free 20169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21169689Skan02110-1301, USA. */ 22132718Skan 23132718Skan/* Simple optimization pass that splits independent uses of each pseudo, 24132718Skan increasing effectiveness of other optimizations. The optimization can 25132718Skan serve as an example of use for the dataflow module. 26132718Skan 27132718Skan We don't split registers with REG_USERVAR set unless -fmessy-debugging 28132718Skan is specified, because debugging information about such split variables 29132718Skan is almost unusable. 30132718Skan 31132718Skan TODO 32132718Skan - Add code to keep debugging up-to-date after splitting user variable 33132718Skan pseudos. This can be done by keeping track of all the pseudos used 34132718Skan for the variable and using life analysis information before reload 35132718Skan to determine which one is live and, in case more than one are live, 36132718Skan choose the one with the latest definition. 37132718Skan 38132718Skan Other optimization passes can benefit from the infrastructure too. 39132718Skan 40132718Skan - We may use profile information and ignore infrequent use for the 41132718Skan purpose of web unifying, inserting the compensation code later to 42132718Skan implement full induction variable expansion for loops (currently 43132718Skan we expand only if the induction variable is dead afterward, which 44132718Skan is often the case). */ 45132718Skan 46132718Skan#include "config.h" 47132718Skan#include "system.h" 48132718Skan#include "coretypes.h" 49132718Skan#include "tm.h" 50132718Skan#include "toplev.h" 51132718Skan 52132718Skan#include "rtl.h" 53132718Skan#include "hard-reg-set.h" 54132718Skan#include "flags.h" 55169689Skan#include "obstack.h" 56132718Skan#include "basic-block.h" 57132718Skan#include "output.h" 58132718Skan#include "df.h" 59132718Skan#include "function.h" 60169689Skan#include "timevar.h" 61169689Skan#include "tree-pass.h" 62132718Skan 63132718Skan 64169689Skanstatic rtx entry_register (struct web_entry *, struct df_ref *, char *); 65169689Skanstatic void replace_ref (struct df_ref *, rtx); 66132718Skan 67132718Skan/* Find the root of unionfind tree (the representative of set). */ 68132718Skan 69169689Skanstruct web_entry * 70132718Skanunionfind_root (struct web_entry *element) 71132718Skan{ 72132718Skan struct web_entry *element1 = element, *element2; 73132718Skan 74132718Skan while (element->pred) 75132718Skan element = element->pred; 76132718Skan while (element1->pred) 77132718Skan { 78132718Skan element2 = element1->pred; 79132718Skan element1->pred = element; 80132718Skan element1 = element2; 81132718Skan } 82132718Skan return element; 83132718Skan} 84132718Skan 85169689Skan/* Union sets. 86169689Skan Return true if FIRST and SECOND points to the same web entry structure and 87169689Skan nothing is done. Otherwise, return false. */ 88132718Skan 89169689Skanbool 90132718Skanunionfind_union (struct web_entry *first, struct web_entry *second) 91132718Skan{ 92132718Skan first = unionfind_root (first); 93132718Skan second = unionfind_root (second); 94132718Skan if (first == second) 95169689Skan return true; 96132718Skan second->pred = first; 97169689Skan return false; 98132718Skan} 99132718Skan 100132718Skan/* For each use, all possible defs reaching it must come in the same 101169689Skan register, union them. 102169689Skan FUN is the function that does the union. */ 103132718Skan 104169689Skanvoid 105169689Skanunion_defs (struct df *df, struct df_ref *use, struct web_entry *def_entry, 106169689Skan struct web_entry *use_entry, 107169689Skan bool (*fun) (struct web_entry *, struct web_entry *)) 108132718Skan{ 109132718Skan rtx insn = DF_REF_INSN (use); 110132718Skan struct df_link *link = DF_REF_CHAIN (use); 111169689Skan struct df_ref *use_link; 112169689Skan struct df_ref *def_link; 113169689Skan rtx set; 114132718Skan 115169689Skan if (insn) 116169689Skan { 117169689Skan use_link = DF_INSN_USES (df, insn); 118169689Skan def_link = DF_INSN_DEFS (df, insn); 119169689Skan set = single_set (insn); 120169689Skan } 121169689Skan else 122169689Skan { 123169689Skan use_link = NULL; 124169689Skan def_link = NULL; 125169689Skan set = NULL; 126169689Skan } 127169689Skan 128132718Skan /* Some instructions may use match_dup for their operands. In case the 129132718Skan operands are dead, we will assign them different pseudos, creating 130132718Skan invalid instructions, so union all uses of the same operand for each 131132718Skan insn. */ 132132718Skan 133132718Skan while (use_link) 134132718Skan { 135169689Skan if (use != use_link 136169689Skan && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (use_link)) 137169689Skan (*fun) (use_entry + DF_REF_ID (use), 138169689Skan use_entry + DF_REF_ID (use_link)); 139169689Skan use_link = use_link->next_ref; 140132718Skan } 141132718Skan 142132718Skan /* Recognize trivial noop moves and attempt to keep them as noop. 143132718Skan While most of noop moves should be removed, we still keep some 144132718Skan of them at libcall boundaries and such. */ 145132718Skan 146132718Skan if (set 147132718Skan && SET_SRC (set) == DF_REF_REG (use) 148132718Skan && SET_SRC (set) == SET_DEST (set)) 149132718Skan { 150132718Skan while (def_link) 151132718Skan { 152169689Skan if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def_link)) 153169689Skan (*fun) (use_entry + DF_REF_ID (use), 154169689Skan def_entry + DF_REF_ID (def_link)); 155169689Skan def_link = def_link->next_ref; 156132718Skan } 157132718Skan } 158132718Skan while (link) 159132718Skan { 160169689Skan (*fun) (use_entry + DF_REF_ID (use), 161169689Skan def_entry + DF_REF_ID (link->ref)); 162132718Skan link = link->next; 163132718Skan } 164132718Skan 165132718Skan /* A READ_WRITE use requires the corresponding def to be in the same 166132718Skan register. Find it and union. */ 167132718Skan if (use->flags & DF_REF_READ_WRITE) 168132718Skan { 169169689Skan struct df_ref *link; 170132718Skan 171169689Skan if (DF_REF_INSN (use)) 172169689Skan link = DF_INSN_DEFS (df, DF_REF_INSN (use)); 173169689Skan else 174169689Skan link = NULL; 175132718Skan 176169689Skan while (link) 177169689Skan { 178169689Skan if (DF_REF_REAL_REG (link) == DF_REF_REAL_REG (use)) 179169689Skan (*fun) (use_entry + DF_REF_ID (use), 180169689Skan def_entry + DF_REF_ID (link)); 181169689Skan link = link->next_ref; 182169689Skan } 183132718Skan } 184132718Skan} 185132718Skan 186132718Skan/* Find the corresponding register for the given entry. */ 187132718Skan 188132718Skanstatic rtx 189169689Skanentry_register (struct web_entry *entry, struct df_ref *ref, char *used) 190132718Skan{ 191132718Skan struct web_entry *root; 192132718Skan rtx reg, newreg; 193132718Skan 194132718Skan /* Find the corresponding web and see if it has been visited. */ 195132718Skan root = unionfind_root (entry); 196132718Skan if (root->reg) 197132718Skan return root->reg; 198132718Skan 199132718Skan /* We are seeing this web for the first time, do the assignment. */ 200132718Skan reg = DF_REF_REAL_REG (ref); 201132718Skan 202132718Skan /* In case the original register is already assigned, generate new one. */ 203132718Skan if (!used[REGNO (reg)]) 204132718Skan newreg = reg, used[REGNO (reg)] = 1; 205132718Skan else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/) 206132718Skan { 207132718Skan newreg = reg; 208169689Skan if (dump_file) 209169689Skan fprintf (dump_file, 210132718Skan "New web forced to keep reg=%i (user variable)\n", 211132718Skan REGNO (reg)); 212132718Skan } 213132718Skan else 214132718Skan { 215132718Skan newreg = gen_reg_rtx (GET_MODE (reg)); 216132718Skan REG_USERVAR_P (newreg) = REG_USERVAR_P (reg); 217132718Skan REG_POINTER (newreg) = REG_POINTER (reg); 218132718Skan REG_ATTRS (newreg) = REG_ATTRS (reg); 219169689Skan if (dump_file) 220169689Skan fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg), 221132718Skan REGNO (newreg)); 222132718Skan } 223132718Skan 224132718Skan root->reg = newreg; 225132718Skan return newreg; 226132718Skan} 227132718Skan 228132718Skan/* Replace the reference by REG. */ 229132718Skan 230132718Skanstatic void 231169689Skanreplace_ref (struct df_ref *ref, rtx reg) 232132718Skan{ 233132718Skan rtx oldreg = DF_REF_REAL_REG (ref); 234132718Skan rtx *loc = DF_REF_REAL_LOC (ref); 235132718Skan 236132718Skan if (oldreg == reg) 237132718Skan return; 238169689Skan if (dump_file) 239169689Skan fprintf (dump_file, "Updating insn %i (%i->%i)\n", 240132718Skan INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg)); 241132718Skan *loc = reg; 242132718Skan} 243132718Skan 244132718Skan/* Main entry point. */ 245132718Skan 246169689Skanstatic void 247132718Skanweb_main (void) 248132718Skan{ 249132718Skan struct df *df; 250132718Skan struct web_entry *def_entry; 251132718Skan struct web_entry *use_entry; 252132718Skan unsigned int i; 253132718Skan int max = max_reg_num (); 254132718Skan char *used; 255132718Skan 256169689Skan df = df_init (DF_EQUIV_NOTES); 257169689Skan df_chain_add_problem (df, DF_UD_CHAIN); 258169689Skan df_analyze (df); 259169689Skan df_reorganize_refs (&df->def_info); 260169689Skan df_reorganize_refs (&df->use_info); 261132718Skan 262169689Skan def_entry = XCNEWVEC (struct web_entry, DF_DEFS_SIZE (df)); 263169689Skan use_entry = XCNEWVEC (struct web_entry, DF_USES_SIZE (df)); 264169689Skan used = XCNEWVEC (char, max); 265132718Skan 266169689Skan if (dump_file) 267169689Skan df_dump (df, dump_file); 268132718Skan 269132718Skan /* Produce the web. */ 270169689Skan for (i = 0; i < DF_USES_SIZE (df); i++) 271169689Skan union_defs (df, DF_USES_GET (df, i), def_entry, use_entry, unionfind_union); 272132718Skan 273132718Skan /* Update the instruction stream, allocating new registers for split pseudos 274132718Skan in progress. */ 275169689Skan for (i = 0; i < DF_USES_SIZE (df); i++) 276169689Skan replace_ref (DF_USES_GET (df, i), 277169689Skan entry_register (use_entry + i, DF_USES_GET (df, i), used)); 278169689Skan for (i = 0; i < DF_DEFS_SIZE (df); i++) 279169689Skan replace_ref (DF_DEFS_GET (df, i), 280169689Skan entry_register (def_entry + i, DF_DEFS_GET (df, i), used)); 281132718Skan 282132718Skan /* Dataflow information is corrupt here, but it can be easily updated 283132718Skan by creating new entries for new registers and updates or calling 284132718Skan df_insns_modify. */ 285132718Skan free (def_entry); 286132718Skan free (use_entry); 287132718Skan free (used); 288132718Skan df_finish (df); 289169689Skan df = NULL; 290132718Skan} 291169689Skan 292169689Skanstatic bool 293169689Skangate_handle_web (void) 294169689Skan{ 295169689Skan return (optimize > 0 && flag_web); 296169689Skan} 297169689Skan 298169689Skanstatic unsigned int 299169689Skanrest_of_handle_web (void) 300169689Skan{ 301169689Skan web_main (); 302169689Skan delete_trivially_dead_insns (get_insns (), max_reg_num ()); 303169689Skan cleanup_cfg (CLEANUP_EXPENSIVE); 304169689Skan reg_scan (get_insns (), max_reg_num ()); 305169689Skan return 0; 306169689Skan} 307169689Skan 308169689Skanstruct tree_opt_pass pass_web = 309169689Skan{ 310169689Skan "web", /* name */ 311169689Skan gate_handle_web, /* gate */ 312169689Skan rest_of_handle_web, /* execute */ 313169689Skan NULL, /* sub */ 314169689Skan NULL, /* next */ 315169689Skan 0, /* static_pass_number */ 316169689Skan TV_WEB, /* tv_id */ 317169689Skan 0, /* properties_required */ 318169689Skan 0, /* properties_provided */ 319169689Skan 0, /* properties_destroyed */ 320169689Skan 0, /* todo_flags_start */ 321169689Skan TODO_dump_func, /* todo_flags_finish */ 322169689Skan 'Z' /* letter */ 323169689Skan}; 324169689Skan 325